Weighted tree: Add the data structure
This adds and ITree<T> interface to convey a parent/child relationship
to any class. And a WeightedTree<T> class to extend for weighted tree,
ie a parent/child data structure where each element has a weight, that
can represent anything.
It also adds an IWeightedTreeProvider interface that analysis providing
a weighted tree can implement to indicate what the data represents.
[added] A weighted tree data structure to display as flame graphs/tree
Change-Id: I10a8b7adf5c9a8ee1436a5e054bfca9e9a20123d
Signed-off-by: Geneviève Bastien <gbastien+lttng@versatic.net>
Reviewed-on: https://git.eclipse.org/r/133216
Tested-by: CI Bot
Reviewed-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
Tested-by: Matthew Khouzam <matthew.khouzam@ericsson.com>
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/META-INF/MANIFEST.MF b/callstack/org.eclipse.tracecompass.incubator.analysis.core/META-INF/MANIFEST.MF
index 4923cd9..ca80ce5 100644
--- a/callstack/org.eclipse.tracecompass.incubator.analysis.core/META-INF/MANIFEST.MF
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/META-INF/MANIFEST.MF
@@ -21,7 +21,9 @@
Export-Package: org.eclipse.tracecompass.incubator.analysis.core.aspects,
org.eclipse.tracecompass.incubator.analysis.core.concepts,
org.eclipse.tracecompass.incubator.analysis.core.model,
+ org.eclipse.tracecompass.incubator.analysis.core.weighted.tree,
org.eclipse.tracecompass.incubator.internal.analysis.core;x-internal:=true,
+ org.eclipse.tracecompass.incubator.internal.analysis.core.aspects;x-internal:=true,
org.eclipse.tracecompass.incubator.internal.analysis.core.model;x-friends:="org.eclipse.tracecompass.incubator.analysis.core.tests,org.eclipse.tracecompass.incubator.callstack.core.tests"
Import-Package: com.google.common.collect
Automatic-Module-Name: org.eclipse.tracecompass.incubator.analysis.core
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/ITree.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/ITree.java
new file mode 100644
index 0000000..11a2785
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/ITree.java
@@ -0,0 +1,52 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.incubator.analysis.core.weighted.tree;
+
+import java.util.Collection;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+
+/**
+ * A basic interface for a tree structure, ie hierarchical data where each node
+ * can be linked to a specific object.
+ *
+ * This interface is meant to be used for consuming the tree structure, the
+ * implementations can add their own tree building methods.
+ *
+ * @author Geneviève Bastien
+ *
+ * @param <T>
+ * The type of objects contained in this tree
+ */
+public interface ITree<@NonNull T> {
+
+ /**
+ * Get the symbol associated with this callsite
+ *
+ * @return The symbol for this callsite
+ */
+ T getObject();
+
+ /**
+ * Get the caller of this callsite (parent)
+ *
+ * @return The caller of this callsite
+ */
+ @Nullable ITree<T> getParent();
+
+ /**
+ * Get the callees of this callsite, ie the functions called by this one
+ *
+ * @return A collection of callees' callsites
+ */
+ Collection<ITree<T>> getChildren();
+
+}
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/IWeightedTreeProvider.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/IWeightedTreeProvider.java
new file mode 100644
index 0000000..4cee4a3
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/IWeightedTreeProvider.java
@@ -0,0 +1,281 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.incubator.analysis.core.weighted.tree;
+
+import java.text.FieldPosition;
+import java.text.Format;
+import java.text.ParsePosition;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.Objects;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+import org.eclipse.tracecompass.common.core.format.DecimalUnitFormat;
+import org.eclipse.tracecompass.common.core.format.SubSecondTimeWithUnitFormat;
+import org.eclipse.tracecompass.common.core.format.DataSizeWithUnitFormat;
+import org.eclipse.tracecompass.common.core.format.DataSpeedWithUnitFormat;
+import org.eclipse.tracecompass.tmf.core.timestamp.ITmfTimestamp;
+
+/**
+ * An interface that classes and analyses providing weighted trees can
+ * implement. This interface allows to add extra information about the specific
+ * trees that it provides.
+ *
+ * The trees are associated with elements that are used to group them. The
+ * elements can implement the {@link ITree} class if there is a hierarchy in the
+ * groupings.
+ *
+ * @author Geneviève Bastien
+ *
+ * @param <N>
+ * The type of objects represented by each node in the tree
+ * @param <E>
+ * The type of elements used to group the trees
+ * @param <T>
+ * The type of the tree provided
+ */
+public interface IWeightedTreeProvider<@NonNull N, E, @NonNull T extends WeightedTree<N>> {
+
+ /**
+ * The type of data that a value represents. Mostly for numeric value, as
+ * the data type will help decide how to format the data to be displayed to
+ * the user
+ */
+ public enum DataType {
+ /**
+ * Data represent a decimal number
+ */
+ NUMBER(new DecimalUnitFormat()),
+ /**
+ * Data represent a time in nanoseconds, can be negative
+ */
+ NANOSECONDS(SubSecondTimeWithUnitFormat.getInstance()),
+ /**
+ * Data represent a binary size, in bytes
+ */
+ BYTES(DataSizeWithUnitFormat.getInstance()),
+ /**
+ * Data represent a binary speed, in bytes/second
+ */
+ BINARY_SPEED(DataSpeedWithUnitFormat.getInstance()),
+ /**
+ * Any other type of data. Metric that use this data type may use
+ * additional formatter.
+ */
+ OTHER(new Format() {
+
+ /**
+ *
+ */
+ private static final long serialVersionUID = 1L;
+
+ @Override
+ public StringBuffer format(@Nullable Object obj, @Nullable StringBuffer toAppendTo, @Nullable FieldPosition pos) {
+ if (toAppendTo == null) {
+ return new StringBuffer(String.valueOf(obj));
+ }
+ return Objects.requireNonNull(toAppendTo.append(String.valueOf(obj)));
+ }
+
+ @Override
+ public @Nullable Object parseObject(@Nullable String source, @Nullable ParsePosition pos) {
+ return null;
+ }
+
+ });
+
+ private Format fFormatter;
+
+ private DataType(Format formatter) {
+ fFormatter = formatter;
+ }
+
+ /**
+ * Formats an object according to the specified formatter
+ *
+ * @param object
+ * The object to format
+ * @return The formatted string
+ */
+ public String format(Object object) {
+ return fFormatter.format(object);
+ }
+ }
+
+ /**
+ * This class associate a title to a data type for tree metrics
+ */
+ public static class MetricType {
+ private final String fTitle;
+ private final DataType fDataType;
+ private final @Nullable Format fFormatter;
+
+ /**
+ * Constructor
+ *
+ * @param title
+ * The title of this metric (a string meant for end users)
+ * @param dataType
+ * The type of data this metric represent
+ * @param format
+ * The formatter for this metric. If <code>null</code>,
+ * formatting will use the {@link DataType}'s default
+ * formatter
+ */
+ public MetricType(String title, DataType dataType, @Nullable Format format) {
+ fTitle = title;
+ fDataType = dataType;
+ fFormatter = format;
+ }
+
+ /**
+ * Get the title of this metric, for the user
+ *
+ * @return The title
+ */
+ public String getTitle() {
+ return fTitle;
+ }
+
+ /**
+ * Get the type of data of this metric
+ *
+ * @return The data type of the metric
+ */
+ public DataType getDataType() {
+ return fDataType;
+ }
+
+ /**
+ * Formats an object for this metric
+ *
+ * @param obj
+ * The object to format
+ * @return The formatted string
+ */
+ public String format(Object obj) {
+ if (fFormatter != null) {
+ return Objects.requireNonNull(fFormatter.format(obj));
+ }
+ return fDataType.format(obj);
+ }
+
+ }
+
+ /**
+ * The default metric type for the tree's weight
+ */
+ MetricType WEIGHT_TYPE = new MetricType("Weight", DataType.NUMBER, null); //$NON-NLS-1$
+
+ /**
+ * Get the trees provided by this analysis. This should return all the trees
+ * for the whole trace
+ *
+ * @param element
+ * The element for which to get the trees
+ * @return A collection of trees provided by this class
+ */
+ Collection<T> getTreesFor(E element);
+
+ /**
+ * Get the trees for a certain time range. If a provider does not support
+ * ranged trees, this method can just return an empty collection
+ *
+ * @param element
+ * The element for which to get the trees
+ * @param start
+ * The timestamp of the start of the range
+ * @param end
+ * The timestamp of the end of the range
+ * @return A collection of trees whose values span from start to end
+ */
+ default Collection<T> getTrees(E element, ITmfTimestamp start, ITmfTimestamp end) {
+ return Collections.emptySet();
+ }
+
+ /**
+ * Get the elements under which are the trees. It can be a single constant
+ * element if this provider does not have the concept of grouping the trees.
+ *
+ * @return The elements used to group the trees
+ */
+ Collection<E> getElements();
+
+ /**
+ * Get the metric type for the weight value. The default metric is called
+ * "Weight" and is a number
+ *
+ * @return The metric type for the weight value.
+ */
+ default MetricType getWeightType() {
+ return WEIGHT_TYPE;
+ }
+
+ /**
+ * Get a list of additional metrics that are provided by this tree.
+ *
+ * @return A list of metrics provided by the trees, in addition to the
+ * weight
+ */
+ default List<MetricType> getAdditionalMetrics() {
+ return Collections.emptyList();
+ }
+
+ /**
+ * Get an additional metric for a tree. The metric index corresponds to the
+ * position of the desired metric in the list of metric returned by the
+ * {@link #getAdditionalMetrics()} method and the return value should be of
+ * the proper data type
+ *
+ * @param object
+ * The tree object for which to get the metric
+ * @param metricIndex
+ * The index in the list of the metric metric to get
+ * @return The value of the metric for the tree in parameter
+ */
+ default Object getAdditionalMetric(T object, int metricIndex) {
+ throw new UnsupportedOperationException("If the tree provider has metric, it should implement this method, or it should not be called"); //$NON-NLS-1$
+ }
+
+ /**
+ * Return a list of additional data sets' titles. These sets will be available
+ * by calling {@link WeightedTree#getExtraDataTrees(int)} on the trees,
+ * where the index in the list is the parameter that the children set should
+ * match
+ *
+ * @return The title of each child set
+ */
+ default List<String> getExtraDataSets() {
+ return Collections.emptyList();
+ }
+
+ /**
+ * Get a user-facing text to identify a tree object. By default, it is the
+ * string representation of the object.
+ *
+ * @param tree
+ * The tree whose value to display
+ * @return A user-facing string to identify this node
+ */
+ default String toDisplayString(T tree) {
+ return String.valueOf(tree.getObject());
+ }
+
+ /**
+ * A title for this tree provider. This title will be visible by users and
+ * should describe what this tree provider's data represent.
+ *
+ * @return The title of this provider
+ */
+ String getTitle();
+
+}
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTree.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTree.java
new file mode 100644
index 0000000..0113e40
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/WeightedTree.java
@@ -0,0 +1,272 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are
+ * made available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+package org.eclipse.tracecompass.incubator.analysis.core.weighted.tree;
+
+import java.util.Collection;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
+import org.eclipse.jdt.annotation.NonNull;
+import org.eclipse.jdt.annotation.Nullable;
+
+/**
+ * A Weighted Tree class to describe hierarchical data with a weight. This class
+ * is a concrete class to describe a simple weighted tree, but it is also meant
+ * to be extended to support other metrics associated with each tree, apart from
+ * the weight.
+ *
+ * Note that the weight is such that the sum of the weight of the children is
+ * smaller or equal to the weight of the parent. Failure to comply to this will
+ * result in undefined behaviors when viewing the results.
+ *
+ * Also, if a child is added to the weighted tree for an object that is already
+ * present in the children of this tree, their data will be merged.
+ *
+ * @author Geneviève Bastien
+ * @param <T>
+ * The type of objects in this tree
+ */
+public class WeightedTree<@NonNull T> implements Comparable<WeightedTree<T>> {
+
+ private final T fObject;
+ private final Map<Object, WeightedTree<T>> fChildren = new HashMap<>();
+ private @Nullable WeightedTree<T> fParent;
+ private long fWeight = 0;
+
+ /**
+ * Constructor
+ *
+ * @param symbol
+ * The symbol of the call site. It can eventually be resolved to
+ * a string using the symbol providers
+ */
+ public WeightedTree(T symbol) {
+ this(symbol, 0);
+ }
+
+ /**
+ * Constructor
+ *
+ * @param symbol
+ * The symbol of the call site. It can eventually be resolved to
+ * a string using the symbol providers
+ * @param initialWeight
+ * The initial length of this object
+ */
+ public WeightedTree(T symbol, long initialWeight) {
+ fObject = symbol;
+ fParent = null;
+ fWeight = initialWeight;
+ }
+
+ /**
+ * Copy constructor
+ *
+ * @param copy
+ * The call site to copy
+ */
+ protected WeightedTree(WeightedTree<T> copy) {
+ fObject = copy.fObject;
+ for (WeightedTree<T> entry : copy.fChildren.values()) {
+ fChildren.put(entry.getObject(), entry.copyOf());
+ }
+ fParent = copy.fParent;
+ fWeight = copy.fWeight;
+ }
+
+ /**
+ * Get the aggregated value of this callsite. The units of this length will
+ * depend on the time of callstack. Typically, for sampled, it will be the
+ * number of times this symbol was hit, while for instrumented, it can be
+ * the total time spent in this callstack element
+ *
+ * @return The aggregated value of this callsite
+ */
+ public long getWeight() {
+ return fWeight;
+ }
+
+ /**
+ * Make a copy of this callsite, with its statistics. Implementing classes
+ * should make sure they copy all fields of the callsite, including the
+ * statistics.
+ *
+ * @return A copy of this aggregated call site
+ */
+ public WeightedTree<T> copyOf() {
+ return new WeightedTree<>(this);
+ }
+
+ /**
+ * Get the symbol associated with this callsite
+ *
+ * @return The symbol for this callsite
+ */
+ public T getObject() {
+ return fObject;
+ }
+
+ /**
+ * Get the caller of this callsite (parent)
+ *
+ * @return The caller of this callsite
+ */
+ protected @Nullable WeightedTree<T> getParent() {
+ return fParent;
+ }
+
+ /**
+ * Sets the parent of this tree
+ *
+ * @param parent
+ * The parent tree
+ */
+ protected void setParent(WeightedTree<T> parent) {
+ fParent = parent;
+ }
+
+ /**
+ * Get the callees of this callsite, ie the functions called by this one
+ *
+ * @return A collection of callees' callsites
+ */
+ public Collection<WeightedTree<T>> getChildren() {
+ return fChildren.values();
+ }
+
+ /**
+ * Add value to the length of this callsite
+ *
+ * @param weight
+ * the amount to add to the length
+ */
+ public void addToWeight(long weight) {
+ fWeight += weight;
+ }
+
+ /**
+ * Add a callee to this callsite. If a callee for the same object already
+ * exists, the data for both callees will be merged.
+ *
+ * @param callee
+ * the call site of the callee
+ */
+ public void addChild(WeightedTree<T> callee) {
+ WeightedTree<T> callsite = fChildren.get(callee.getObject());
+ if (callsite == null) {
+ callee.setParent(this);
+ fChildren.put(callee.getObject(), callee);
+ return;
+ }
+ callsite.merge(callee);
+ }
+
+ /**
+ * Merge a callsite's data with this one. This method will modify the
+ * current callsite.
+ *
+ * It will first call {@link #mergeData(WeightedTree)} that needs to be
+ * implemented for each implementation of this class.
+ *
+ * It will then merge the callees of both callsites by adding the other's
+ * callees to this one.
+ *
+ * @param other
+ * The call site to merge. It has to have the same symbol as the
+ * current callsite otherwise it will throw an
+ * {@link IllegalArgumentException}
+ */
+ public final void merge(WeightedTree<T> other) {
+ if (!other.getObject().equals(getObject())) {
+ throw new IllegalArgumentException("AggregatedStackTraces: trying to merge stack traces of different symbols"); //$NON-NLS-1$
+ }
+ fWeight += other.fWeight;
+ mergeData(other);
+ mergeChildren(other);
+ }
+
+ /**
+ * Merge the data of two callsites. This should modify the current
+ * callsite's specific data. It is called by {@link #merge(WeightedTree)}
+ * and this method MUST NOT touch the callees of the callsites.
+ *
+ * @param other
+ * The call site to merge to this one
+ */
+ protected void mergeData(WeightedTree<T> other) {
+ // Nothing to do in main class
+ }
+
+ /**
+ * Merge the children callsites
+ *
+ * @param other
+ * The call site to merge to this one
+ */
+ private void mergeChildren(WeightedTree<T> other) {
+ for (WeightedTree<T> otherChildSite : other.fChildren.values()) {
+ T childSymbol = otherChildSite.getObject();
+ WeightedTree<T> childSite = fChildren.get(childSymbol);
+ if (childSite == null) {
+ fChildren.put(childSymbol, otherChildSite.copyOf());
+ } else {
+ // combine children
+ childSite.merge(otherChildSite);
+ }
+ }
+ }
+
+ /**
+ * Get the maximum depth under and including this aggregated callsite. A
+ * depth of 1 means there is one element under and including this element.
+ *
+ * @return The maximum depth under and including this aggregated call site.
+ * The minimal value for the depth is 1.
+ */
+ public int getMaxDepth() {
+ int maxDepth = 0;
+ for (WeightedTree<T> child : getChildren()) {
+ maxDepth = Math.max(maxDepth, child.getMaxDepth());
+ }
+ return maxDepth + 1;
+ }
+
+ /**
+ * Get other children of this tree that are not its direct descendants. It
+ * can be used for instance to represent extra data, for example kernel
+ * statuses for a callstack.
+ * <p>
+ * A weighted tree provider will advertise those potential children data
+ * that come with this tree, and consumers can then call this method with
+ * the index of this extra type, if the tree has more than one extra data
+ * set
+ *
+ * @param index
+ * The index of this extra children set, as provided by the
+ * {@link IWeightedTreeProvider#getExtraDataSets()} method.
+ *
+ * @return The extra children sites
+ */
+ public Collection<WeightedTree<@NonNull T>> getExtraDataTrees(int index) {
+ return Collections.emptyList();
+ }
+
+ @Override
+ public String toString() {
+ return "WeightedTreeNode: " + fObject; //$NON-NLS-1$
+ }
+
+ @Override
+ public int compareTo(WeightedTree<@NonNull T> o) {
+ return Long.compare(fWeight, o.fWeight);
+ }
+
+}
diff --git a/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/package-info.java b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/package-info.java
new file mode 100644
index 0000000..41e95ad
--- /dev/null
+++ b/callstack/org.eclipse.tracecompass.incubator.analysis.core/src/org/eclipse/tracecompass/incubator/analysis/core/weighted/tree/package-info.java
@@ -0,0 +1,16 @@
+/*******************************************************************************
+ * Copyright (c) 2019 École Polytechnique de Montréal
+ *
+ * All rights reserved. This program and the accompanying materials are made
+ * available under the terms of the Eclipse Public License v1.0 which
+ * accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *******************************************************************************/
+
+/**
+ * This package contains classes describing a weighted tree data structure, and
+ * interfaces to implement for analysis or components that provide weighted
+ * trees.
+ */
+@org.eclipse.jdt.annotation.NonNullByDefault
+package org.eclipse.tracecompass.incubator.analysis.core.weighted.tree;
