Publish

23 files changed, 1577 insertions, 0 deletions

diff --git a/yolean/src/main/java/com/yahoo/yolean/Exceptions.java b/yolean/src/main/java/com/yahoo/yolean/Exceptions.java
new file mode 100644
index 00000000000..51e8332809b
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/Exceptions.java
@@ -0,0 +1,47 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean;
+
+/**
+ * Helper methods for handling exceptions
+ *
+ * @author bratseth
+ */
+public class Exceptions {
+
+    /**
+     * <p>Returns a user friendly error message string which includes information from all nested exceptions.</p>
+     *
+     * <p>The form of this string is
+     * <code>e.getMessage(): e.getCause().getMessage(): e.getCause().getCause().getMessage()...</code>
+     * In addition, some heuristics are used to clean up common cases where exception nesting causes bad messages.
+     */
+    public static String toMessageString(Throwable t) {
+        StringBuilder b = new StringBuilder();
+        String lastMessage = null;
+        String message;
+        for (; t != null; t = t.getCause()) {
+            message = getMessage(t);
+            if (message == null) continue;
+            if (message.equals(lastMessage)) continue;
+            if (b.length() > 0) {
+                b.append(": ");
+            }
+            b.append(message);
+            lastMessage = message;
+        }
+        return b.toString();
+    }
+
+    /** Returns a useful message from *this* exception, or null if there is nothing useful to return */
+    private static String getMessage(Throwable t) {
+        String message = t.getMessage();
+        if (t.getCause() == null) {
+            if (message == null) return t.getClass().getSimpleName();
+        } else {
+            if (message == null) return null;
+            if (message.equals(t.getCause().getClass().getName() + ": " + t.getCause().getMessage())) return null;
+        }
+        return message;
+    }
+
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/After.java b/yolean/src/main/java/com/yahoo/yolean/chain/After.java
new file mode 100644
index 00000000000..7664f30cc6b
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/After.java
@@ -0,0 +1,23 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Inherited;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+/**
+ * <p>The component that is annotated with this must be placed later than the components or phases providing names
+ * contained in the given list.</p>
+ *
+ * @author tonytv
+ * @since 5.1.18
+ */
+@Retention(RetentionPolicy.RUNTIME)
+@Target(ElementType.TYPE)
+@Inherited
+public @interface After {
+
+    public abstract String[] value() default { };
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/Before.java b/yolean/src/main/java/com/yahoo/yolean/chain/Before.java
new file mode 100644
index 00000000000..cd8c90be085
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/Before.java
@@ -0,0 +1,23 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Inherited;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+/**
+ * <p>The component that is annotated with this must be placed earlier than the components or phases providing names
+ * contained in the given list.</p>
+ *
+ * @author tonytv
+ * @since 5.1.18
+ */
+@Retention(RetentionPolicy.RUNTIME)
+@Target(ElementType.TYPE)
+@Inherited
+public @interface Before {
+
+    public abstract String[] value() default { };
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/Chain.java b/yolean/src/main/java/com/yahoo/yolean/chain/Chain.java
new file mode 100644
index 00000000000..86ff0e07d00
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/Chain.java
@@ -0,0 +1,98 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+import static java.util.Objects.requireNonNull;
+
+/**
+ * An immutable and ordered list of components
+ *
+ * @author tonytv
+ */
+public final class Chain<T> implements Iterable<T> {
+
+    private final String id;
+    private final Collection<T> components;
+
+    @SafeVarargs
+    public Chain(String id, T... components) {
+        this(id, Arrays.asList(components));
+    }
+
+    public Chain(String id, List<? extends T> components) {
+        requireNonNull(id, "id must be non-null.");
+        requireNonNull(components, "components must be non-null");
+
+        this.components = ImmutableList.copyOf(components);
+        this.id = id;
+    }
+
+    public String id() {
+        return id;
+    }
+
+    public boolean isEmpty() {
+        return components.isEmpty();
+    }
+
+    @Override
+    public Iterator<T> iterator() {
+        return components.iterator();
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder b = new StringBuilder();
+        b.append("chain '").append(id).append("'{");
+        boolean first = true;
+        for (T component : components) {
+            if (!first) {
+                b.append("->");
+            } else {
+                first = false;
+            }
+            b.append(" ").append(component.getClass().getSimpleName()).append(" ");
+        }
+        b.append("}");
+        return b.toString();
+    }
+
+    @Override
+    public int hashCode() {
+        return id.hashCode();
+    }
+
+    @Override
+    public boolean equals(Object other) {
+        return other instanceof Chain && equals((Chain<?>)other);
+    }
+
+    public boolean equals(Chain<?> other) {
+        return id.equals(other.id) && componentsIdentical(components, other.components);
+    }
+
+    private boolean componentsIdentical(Collection<T> components1, Collection<?> components2) {
+        if (components1.size() != components2.size()) {
+            return false;
+        }
+        Iterator<T> iterator1 = components1.iterator();
+        Iterator<?> iterator2 = components2.iterator();
+        while (iterator1.hasNext()) {
+            T c1 = iterator1.next();
+            Object c2 = iterator2.next();
+
+            if (c1 != c2) {
+                return false;
+            }
+        }
+        return true;
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/ChainBuilder.java b/yolean/src/main/java/com/yahoo/yolean/chain/ChainBuilder.java
new file mode 100644
index 00000000000..ad44f2416d4
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/ChainBuilder.java
@@ -0,0 +1,247 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * @author tonytv
+ * @author gjoranv
+ */
+public final class ChainBuilder<T> {
+
+    private final String chainId;
+    private final List<T> components = new ArrayList<>();
+    private final IdentityHashMap<T, Dependencies<T>> dependencies = new IdentityHashMap<>();
+
+    public ChainBuilder(String chainId) {
+        this.chainId = chainId;
+    }
+
+    @SafeVarargs
+    public final ChainBuilder<T> add(T component, Dependencies<? extends T>... dependenciesList) {
+        if (dependencies.containsKey(component)) {
+            throw new IllegalArgumentException("The same component cannot be added twice: " + component);
+        }
+        components.add(component);
+
+        List<Dependencies<? extends T>> allDependencies =
+                Dependencies.allOf(dependenciesList, Dependencies.getAnnotatedDependencies(component));
+        dependencies.put(component, Dependencies.union(allDependencies));
+
+        return this;
+    }
+
+    public Chain<T> build() {
+        DirectedGraph graph = buildGraph();
+        List<Vertex> sortedVertices = graph.topologicalSort();
+        return new Chain<>(chainId, components(sortedVertices));
+    }
+
+    private DirectedGraph buildGraph() {
+        DirectedGraph graph = new DirectedGraph();
+        List<ComponentVertex<T>> vertices = createVertices();
+
+        addVertices(graph, vertices);
+        addEdges(graph, vertices, dependencies);
+
+        return graph;
+    }
+
+    private List<ComponentVertex<T>> createVertices() {
+        List<ComponentVertex<T>> vertices = new ArrayList<>();
+        for (T component : components) {
+            vertices.add(new ComponentVertex<>(component));
+        }
+        return vertices;
+    }
+
+    @SuppressWarnings("unchecked")
+    private List<T> components(List<Vertex> sortedVertices) {
+        List<T> result = new ArrayList<>();
+        for (Vertex vertex : sortedVertices) {
+            if (vertex instanceof ComponentVertex) {
+                result.add((T)((ComponentVertex)vertex).component);
+            }
+        }
+        return result;
+    }
+
+    // TODO: create subclasses Beginning/EdingVertex instead? We could then create the correct class in createVertices,
+    // TODO: and call the same method in DirGraph for all types.
+    private void addVertices(DirectedGraph graph, List<ComponentVertex<T>> vertices) {
+        for (ComponentVertex<T> v : vertices) {
+            if (isBeginningVertex(v)) {
+                graph.addBeginningVertex(v);
+            } else if (isEndingVertex(v)) {
+                graph.addEndingVertex(v);
+            } else {
+                graph.addVertex(v);
+            }
+        }
+    }
+
+    private boolean isBeginningVertex(ComponentVertex<T> v) {
+        return dependencies.get(v.component).before.providedNames.contains("*");
+    }
+
+    private boolean isEndingVertex(ComponentVertex<T> v) {
+        return dependencies.get(v.component).after.providedNames.contains("*");
+    }
+
+    private static <T> void addEdges(DirectedGraph graph,
+                                     List<ComponentVertex<T>> vertices,
+                                     IdentityHashMap<T, Dependencies<T>> dependencies) {
+        addBeforeInstanceEdges(graph, vertices, dependencies);
+        addAfterInstanceEdges(graph, vertices, dependencies);
+        addBeforeClassEdges(graph, vertices, dependencies);
+        addAfterClassEdges(graph, vertices, dependencies);
+        addBeforeProvidedEdges(graph, vertices, dependencies);
+        addAfterProvidedEdges(graph, vertices, dependencies);
+    }
+
+    // NOTE: When reading 'beforeVertex' below, think that 'vertex' should be _before_ beforeVertex.
+
+    private static <T> void addBeforeClassEdges(DirectedGraph graph,
+                                                List<ComponentVertex<T>> vertices,
+                                                IdentityHashMap<T, Dependencies<T>> dependencies) {
+        for (ComponentVertex<T> vertex : vertices) {
+            for (Class<? extends T> beforeClass : dependencies.get(vertex.component).before.classes) {
+                for (Vertex beforeVertex : componentsWithClass(vertices, beforeClass)) {
+                    graph.addEdge(vertex, beforeVertex);
+                }
+            }
+        }
+    }
+
+    private static <T> void addAfterClassEdges(DirectedGraph graph,
+                                               List<ComponentVertex<T>> vertices,
+                                               IdentityHashMap<T, Dependencies<T>> dependencies) {
+        for (ComponentVertex<T> vertex : vertices) {
+            for (Class<? extends T> afterClass : dependencies.get(vertex.component).after.classes) {
+                for (Vertex afterVertex : componentsWithClass(vertices, afterClass)) {
+                    graph.addEdge(afterVertex, vertex);
+                }
+            }
+        }
+    }
+
+    private static <T> List<Vertex> componentsWithClass(List<ComponentVertex<T>> vertices,
+                                                        Class<? extends T> beforeClass) {
+        List<Vertex> result = new ArrayList<>();
+        for (ComponentVertex<T> vertex : vertices) {
+            if (beforeClass.isInstance(vertex.component)) {
+                result.add(vertex);
+            }
+        }
+        return result;
+    }
+
+    private static <T> void addBeforeInstanceEdges(DirectedGraph graph,
+                                                   List<ComponentVertex<T>> vertices,
+                                                   IdentityHashMap<T, Dependencies<T>> dependencies) {
+        IdentityHashMap<T, Vertex> componentToVertex = getComponentToVertex(vertices);
+        for (ComponentVertex<T> vertex : vertices) {
+            for (T before : dependencies.get(vertex.component).before.instances) {
+                Vertex beforeVertex = componentToVertex.get(before);
+                if (beforeVertex != null) {
+                    graph.addEdge(vertex, beforeVertex);
+                }
+            }
+        }
+    }
+
+    private static <T> void addAfterInstanceEdges(DirectedGraph graph,
+                                                  List<ComponentVertex<T>> vertices,
+                                                  IdentityHashMap<T, Dependencies<T>> dependencies) {
+        IdentityHashMap<T, Vertex> componentToVertex = getComponentToVertex(vertices);
+        for (ComponentVertex<T> vertex : vertices) {
+            for (T after : dependencies.get(vertex.component).after.instances) {
+                Vertex afterVertex = componentToVertex.get(after);
+                if (afterVertex != null) {
+                    graph.addEdge(afterVertex, vertex);
+                }
+            }
+        }
+    }
+
+    private static <T> IdentityHashMap<T, Vertex> getComponentToVertex(List<ComponentVertex<T>> vertices) {
+        IdentityHashMap<T, Vertex> result = new IdentityHashMap<>();
+        for (ComponentVertex<T> vertex : vertices) {
+            result.put(vertex.component, vertex);
+        }
+        return result;
+    }
+
+    private static <T> void addBeforeProvidedEdges(DirectedGraph graph,
+                                                   List<ComponentVertex<T>> vertices,
+                                                   IdentityHashMap<T, Dependencies<T>> dependencies) {
+        Map<String, Set<Vertex>> providedNames = getProvidedNames(vertices, dependencies);
+        for (ComponentVertex<T> vertex : vertices) {
+            for (String name : dependencies.get(vertex.component).before.providedNames) {
+                for (Vertex beforeVertex : emptyIfNull(providedNames.get(name))) {
+                    graph.addEdge(vertex, beforeVertex);
+                }
+            }
+        }
+    }
+
+    private static <T> void addAfterProvidedEdges(DirectedGraph graph,
+                                                  List<ComponentVertex<T>> vertices,
+                                                  IdentityHashMap<T, Dependencies<T>> dependencies) {
+        Map<String, Set<Vertex>> providedNames = getProvidedNames(vertices, dependencies);
+        for (ComponentVertex<T> vertex : vertices) {
+            for (String name : dependencies.get(vertex.component).after.providedNames) {
+                for (Vertex afterVertex : emptyIfNull(providedNames.get(name))) {
+                    graph.addEdge(afterVertex, vertex);
+                }
+            }
+        }
+    }
+
+    private static <T> Map<String, Set<Vertex>> getProvidedNames(List<ComponentVertex<T>> vertices,
+                                                                 IdentityHashMap<T, Dependencies<T>> dependencies) {
+        Map<String, Set<Vertex>> result = new HashMap<>();
+        for (ComponentVertex<T> vertex : vertices) {
+            for (String providedName : dependencies.get(vertex.component).provided) {
+                getIdentitySet(result, providedName).add(vertex);
+            }
+            addClassName(result, vertex);
+        }
+        return result;
+    }
+
+    private static void addClassName(Map<String, Set<Vertex>> providedNamesToVertex, ComponentVertex vertex) {
+        String className = vertex.component.getClass().getName();
+        getIdentitySet(providedNamesToVertex, className).add(vertex);
+    }
+
+    private static <T> Set<T> getIdentitySet(Map<String, Set<T>> map, String key) {
+        Set<T> result = map.get(key);
+        if (result == null) {
+            result = Collections.newSetFromMap(new IdentityHashMap<T, Boolean>());
+            map.put(key, result);
+        }
+        return result;
+    }
+
+    private static <T> Set<T> emptyIfNull(Set<T> set) {
+        return set != null ?
+               set :
+               Collections.<T>emptySet();
+    }
+
+    private static class ComponentVertex<T> implements Vertex {
+
+        final T component;
+
+        private ComponentVertex(T component) {
+            this.component = component;
+        }
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/ChainCycleException.java b/yolean/src/main/java/com/yahoo/yolean/chain/ChainCycleException.java
new file mode 100644
index 00000000000..b92df20ab8c
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/ChainCycleException.java
@@ -0,0 +1,24 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import com.google.common.collect.ImmutableList;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * @author tonytv
+ */
+public class ChainCycleException extends RuntimeException {
+
+    private final List<?> components;
+
+    public ChainCycleException(List<?> components) {
+        this.components = ImmutableList.copyOf(components);
+    }
+
+    public List<?> components() {
+        return components;
+    }
+}
\ No newline at end of file
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/Dependencies.java b/yolean/src/main/java/com/yahoo/yolean/chain/Dependencies.java
new file mode 100644
index 00000000000..ca59c373351
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/Dependencies.java
@@ -0,0 +1,191 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import java.lang.annotation.Annotation;
+import java.lang.reflect.InvocationTargetException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * @author tonytv
+ * @author gjoranv
+ */
+public class Dependencies<T> {
+
+    final Order<T> before;
+    final Order<T> after;
+    final List<String> provided;
+
+    private Dependencies(Order<T> before, Order<T> after, String[] provided) {
+        this.before = before;
+        this.after = after;
+        this.provided = copyList(provided);
+    }
+
+    @SafeVarargs
+    public static <T> Dependencies<T> before(T... components) {
+        return new Dependencies<>(new Order<>(components, null, null), Order.<T>emptyOrder(), null);
+    }
+
+    @SafeVarargs
+    public static <T> Dependencies<T> before(Class<? extends T>... classes) {
+        return new Dependencies<>(new Order<>(null, classes, null), Order.<T>emptyOrder(), null);
+    }
+
+    @SuppressWarnings("unchecked")
+    public static Dependencies before(String... providedNames) {
+        // Does not use type parameters due to Javas limited type inference.
+        return new Dependencies(new Order(null, null, providedNames), Order.emptyOrder(), null);
+    }
+
+    @SafeVarargs
+    public static <T> Dependencies<T> after(T... components) {
+        return new Dependencies<>(Order.<T>emptyOrder(), new Order<>(components, null, null), null);
+    }
+
+    @SafeVarargs
+    public static <T> Dependencies<T> after(Class<? extends T>... classes) {
+        return new Dependencies<>(Order.<T>emptyOrder(), new Order<>(null, classes, null), null);
+    }
+
+    @SuppressWarnings("unchecked")
+    public static Dependencies after(String... providedNames) {
+        // Does not use type parameters due to Javas limited type inference.
+        return new Dependencies(Order.emptyOrder(), new Order(null, null, providedNames), null);
+    }
+
+    @SuppressWarnings("unchecked")
+    public static Dependencies provides(String... names) {
+        // Does not use type parameters due to Javas limited type inference.
+        return new Dependencies(Order.emptyOrder(), Order.emptyOrder(), names);
+    }
+
+    public static <T> Dependencies<T> emptyDependencies() {
+        return new Dependencies<>(Order.<T>emptyOrder(), Order.<T>emptyOrder(), null);
+    }
+
+    @SuppressWarnings("unchecked")
+    static <T> Dependencies<T> union(List<Dependencies<? extends T>> dependenciesList) {
+        if (dependenciesList.size() > 1) {
+            Dependencies<T> result = emptyDependencies();
+            for (Dependencies<? extends T> dependencies : dependenciesList) {
+                result = result.union(dependencies);
+            }
+            return result;
+        } else if (dependenciesList.size() == 0) {
+            return emptyDependencies();
+        } else {
+            return (Dependencies<T>)dependenciesList.get(0); // Dependencies<T> is covariant for T, the cast is valid.
+        }
+    }
+
+    private Dependencies<T> union(Dependencies<? extends T> other) {
+        List<String> lst = listUnion(provided, other.provided);
+        return new Dependencies<>(before.union(other.before),
+                                  after.union(other.after),
+                                  lst.toArray(new String[lst.size()]));
+    }
+
+    private static <T> List<T> listUnion(List<? extends T> list1, List<? extends T> list2) {
+        List<T> union = new ArrayList<>(list1);
+        union.removeAll(list2);
+        union.addAll(list2);
+        return union;
+    }
+
+    static <T> Dependencies<T> getAnnotatedDependencies(T component) {
+        return new Dependencies<>(
+                new Order<T>(null, null, getSymbols(component, Before.class)),
+                new Order<T>(null, null, getSymbols(component, After.class)),
+                getProvidedSymbols(component));
+    }
+
+    private static <T> String[] getProvidedSymbols(T component) {
+        List<String> lst = allOf(getSymbols(component, Provides.class), component.getClass().getName());
+        return lst.toArray(new String[lst.size()]);
+    }
+
+    @SafeVarargs
+    static <T> List<T> allOf(List<T> elements, T... otherElements) {
+        List<T> result = new ArrayList<>(elements);
+        result.addAll(Arrays.asList(otherElements));
+        return result;
+    }
+
+    @SafeVarargs
+    static <T> List<T> allOf(T[] elements, T... otherElements) {
+        return allOf(Arrays.asList(elements), otherElements);
+    }
+
+    private static <T> List<String> getSymbols(T component, Class<? extends Annotation> annotationClass) {
+        List<String> result = new ArrayList<>();
+
+        result.addAll(annotationSymbols(component, annotationClass));
+        return result;
+    }
+
+    private static <T> Collection<String> annotationSymbols(T component, Class<? extends Annotation> annotationClass) {
+        try {
+            List<String> values = new ArrayList<>();
+
+            Class clazz = component.getClass();
+            while (clazz != null) {
+                Annotation annotation = clazz.getAnnotation(annotationClass);
+                if (annotation != null) {
+                    values.addAll(Arrays.asList((String[])annotationClass.getMethod("value").invoke(annotation)));
+                }
+                clazz = clazz.getSuperclass();
+            }
+            return values;
+        } catch (IllegalAccessException | NoSuchMethodException | InvocationTargetException e) {
+            throw new RuntimeException(e);
+        }
+    }
+
+    private static <U> List<U> copyList(List<U> list) {
+        return list == null ?
+               Collections.<U>emptyList() :
+               new ArrayList<>(list);
+    }
+
+    private static <U> List<U> copyList(U[] array) {
+        return array == null ?
+               Collections.<U>emptyList() :
+               new ArrayList<>(Arrays.<U>asList(array));
+    }
+
+    static final class Order<T> {
+
+        final List<T> instances;
+        final List<Class<? extends T>> classes;
+        final List<String> providedNames;
+
+        private Order(T[] instances, Class<? extends T>[] classes, String[] providedNames) {
+            this.instances = copyList(instances);
+            this.classes = copyList(classes);
+            this.providedNames = copyList(providedNames);
+        }
+
+        private Order(List<T> instances, List<Class<? extends T>> classes, List<String> providedNames) {
+            this.instances = copyList(instances);
+            this.classes = copyList(classes);
+            this.providedNames = copyList(providedNames);
+        }
+
+        // TODO: unit test
+        private Order<T> union(Order<? extends T> other) {
+            return new Order<>(
+                    listUnion(instances, other.instances),
+                    listUnion(classes, other.classes),
+                    listUnion(providedNames, other.providedNames));
+        }
+
+        // TODO: try to make it possible to use 'null' Order in Dependencies instead.
+        private static <U> Order<U> emptyOrder() {
+            return new Order<>((U[])null, null, null);
+        }
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/DirectedGraph.java b/yolean/src/main/java/com/yahoo/yolean/chain/DirectedGraph.java
new file mode 100644
index 00000000000..260ffe33b5f
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/DirectedGraph.java
@@ -0,0 +1,106 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * TODO: prioritize vertices in edge map.
+ *
+ * @author tonytv
+ */
+class DirectedGraph {
+
+    private IdentityHashMap<Vertex, List<Vertex>> incommingEdges = new IdentityHashMap<>();
+    private List<Vertex> vertices = new ArrayList<>();
+    private List<Vertex> beginningVertices = new ArrayList<>();
+    private List<Vertex> endingVertices = new ArrayList<>();
+
+    public void addVertex(Vertex vertex) {
+        vertices.add(vertex);
+    }
+
+    public void addBeginningVertex(Vertex vertex) {
+        beginningVertices.add(vertex);
+    }
+
+    public void addEndingVertex(Vertex vertex) {
+        endingVertices.add(vertex);
+    }
+
+    public void addEdge(Vertex start, Vertex end) {
+        get(incommingEdges, end).add(start);
+    }
+
+    private static List<Vertex> get(Map<Vertex, List<Vertex>> edgeMap, Vertex key) {
+        List<Vertex> value = edgeMap.get(key);
+        return value == null ?
+               addEmptyList(edgeMap, key) :
+               value;
+    }
+
+    private static List<Vertex> addEmptyList(Map<Vertex, List<Vertex>> edgeMap, Vertex key) {
+        List<Vertex> value = new ArrayList<>();
+        edgeMap.put(key, value);
+        return value;
+    }
+
+    public List<Vertex> topologicalSort() {
+        EnumeratedIdentitySet<Vertex> visitedVertices = new EnumeratedIdentitySet<>();
+
+        for (Vertex v : beginningVertices) {
+            topologicalSortVisit(v, visitedVertices);
+        }
+
+        warnIfVisitedEndVertices(visitedVertices);
+
+        for (Vertex v : vertices) {
+            topologicalSortVisit(v, visitedVertices);
+        }
+
+        // TODO: review this!
+        for (Vertex v : endingVertices) {
+            topologicalSortVisit(v, visitedVertices);
+        }
+
+        return visitedVertices.insertionOrderedList();
+    }
+
+    private void warnIfVisitedEndVertices(EnumeratedIdentitySet<Vertex> visitedVertices) {
+        //TVT:
+    }
+
+    private void topologicalSortVisit(Vertex vertex, Set<Vertex> visitedVertices) {
+        topologicalSortVisitImpl(vertex, visitedVertices, new EnumeratedIdentitySet<Vertex>());
+    }
+
+    private void topologicalSortVisitImpl(Vertex vertex, Set<Vertex> visitedVertices,
+                                          EnumeratedIdentitySet<Vertex> cycleDetector) {
+        if (cycleDetector.contains(vertex)) {
+            throw new ChainCycleException(cycleDetector.insertionOrderedList());
+        }
+
+        if (visitedVertices.contains(vertex)) {
+            return;
+        }
+
+        cycleDetector.add(vertex);
+
+        for (Vertex endVertex : emptyIfNull(incommingEdges.get(vertex))) {
+            topologicalSortVisitImpl(endVertex, visitedVertices, cycleDetector);
+        }
+
+        visitedVertices.add(vertex);
+        cycleDetector.remove(vertex);
+    }
+
+    private <T> List<T> emptyIfNull(List<T> list) {
+        return list == null ?
+               Collections.<T>emptyList() :
+               list;
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/EnumeratedIdentitySet.java b/yolean/src/main/java/com/yahoo/yolean/chain/EnumeratedIdentitySet.java
new file mode 100644
index 00000000000..902391e7d24
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/EnumeratedIdentitySet.java
@@ -0,0 +1,183 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import java.lang.reflect.Array;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.TreeMap;
+
+/**
+ * A set using identity comparison.
+ * Keeps track of insertion order, which is available by calling insertionOrderedList.
+ *
+ * @author tonytv
+ */
+class EnumeratedIdentitySet<T> implements Set<T> {
+
+    private int counter = 0;
+    private final Map<T, Integer> set = new IdentityHashMap<>();
+
+    public EnumeratedIdentitySet(Collection<? extends T> collection) {
+        addAll(collection);
+    }
+
+    public EnumeratedIdentitySet() {
+        // empty
+    }
+
+    @Override
+    public int size() {
+        return set.size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return set.isEmpty();
+    }
+
+    @Override
+    public boolean contains(Object o) {
+        return set.containsKey(o);
+    }
+
+    @Override
+    public Iterator<T> iterator() {
+        return set.keySet().iterator();
+    }
+
+    @Override
+    public Object[] toArray() {
+        return set.keySet().toArray();
+    }
+
+    @Override
+    public <T1> T1[] toArray(T1[] a) {
+        return set.keySet().toArray(a);
+    }
+
+    @Override
+    public boolean add(T t) {
+        if (set.containsKey(t)) {
+            return false;
+        } else {
+            set.put(t, counter++);
+            return true;
+        }
+    }
+
+    @Override
+    public boolean remove(Object o) {
+        return set.remove(o) != null;
+    }
+
+    @Override
+    public boolean containsAll(Collection<?> c) {
+        return set.keySet().containsAll(c);
+    }
+
+    @Override
+    public boolean addAll(Collection<? extends T> collection) {
+        boolean changed = false;
+
+        for (T t : collection) {
+            changed |= add(t);
+        }
+
+        return changed;
+    }
+
+    @Override
+    public boolean retainAll(Collection<?> collection) {
+        return set.keySet().retainAll(collection);
+    }
+
+    @Override
+    public boolean removeAll(Collection<?> collection) {
+        boolean changed = false;
+
+        for (Object o : collection) {
+            changed |= remove(o);
+        }
+
+        return changed;
+    }
+
+    @Override
+    public void clear() {
+        set.clear();
+        counter = 0;
+    }
+
+    public List<T> insertionOrderedList() {
+        if (set.isEmpty()) {
+            counter = 0;
+            return Collections.emptyList();
+        }
+
+        if (counter >= set.size() * 2 + 20) {
+            renumber();
+        }
+
+        return getKeysSortedByValue(set, counter);
+    }
+
+    private static <KEY> List<KEY> getKeysSortedByValue(Map<KEY, Integer> set, int maxValue) {
+        @SuppressWarnings("unchecked")
+        KEY[] result = (KEY[])Array.newInstance(headKey(set).getClass(), maxValue);
+
+        for (Map.Entry<KEY, Integer> entry : set.entrySet()) {
+            result[entry.getValue()] = entry.getKey();
+        }
+
+        return removeNulls(result);
+    }
+
+    private static <T> T headKey(Map<T, ?> map) {
+        return map.entrySet().iterator().next().getKey();
+    }
+
+    static <T> List<T> removeNulls(T[] list) {
+        int insertionSpot = 0;
+        for (int i = 0; i < list.length; i++) {
+            T element = list[i];
+            if (element != null) {
+                list[insertionSpot] = element;
+                insertionSpot++;
+            }
+        }
+        return Arrays.asList(list).subList(0, insertionSpot);
+    }
+
+    //only for testing
+    List<Integer> numbers() {
+        return new ArrayList<>(set.values());
+    }
+
+    private void renumber() {
+        SortedMap<Integer, T> invertedSet = invertedSortedMap(set);
+
+        int i = 0;
+        for (Map.Entry<Integer, T> entry : invertedSet.entrySet()) {
+            set.put(entry.getValue(), i++);
+        }
+        counter = i;
+    }
+
+    private static <K, V> SortedMap<V, K> invertedSortedMap(Map<K, V> map) {
+        SortedMap<V, K> result = new TreeMap<>();
+
+        for (Map.Entry<K, V> entry : map.entrySet()) {
+            result.put(entry.getValue(), entry.getKey());
+        }
+
+        return result;
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/Provides.java b/yolean/src/main/java/com/yahoo/yolean/chain/Provides.java
new file mode 100644
index 00000000000..99cfaf1fef2
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/Provides.java
@@ -0,0 +1,23 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Inherited;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+/**
+ * <p>Mark this component as providing some named functionality. Other components can then mark themselves as "before"
+ * and "after" the string provided here, to impose constraints on ordering.</p>
+ *
+ * @author tonytv
+ * @since 5.1.18
+ */
+@Retention(RetentionPolicy.RUNTIME)
+@Target(ElementType.TYPE)
+@Inherited
+public @interface Provides {
+
+    public abstract String[] value() default { };
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/Vertex.java b/yolean/src/main/java/com/yahoo/yolean/chain/Vertex.java
new file mode 100644
index 00000000000..57de9c3d81c
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/Vertex.java
@@ -0,0 +1,9 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.chain;
+
+/**
+ * @author tonytv
+ */
+interface Vertex {
+
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/chain/package-info.java b/yolean/src/main/java/com/yahoo/yolean/chain/package-info.java
new file mode 100644
index 00000000000..a17b39169c7
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/chain/package-info.java
@@ -0,0 +1,6 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+@ExportPackage
+@PublicApi package com.yahoo.yolean.chain;
+
+import com.yahoo.api.annotations.PublicApi;
+import com.yahoo.osgi.annotation.ExportPackage;
diff --git a/yolean/src/main/java/com/yahoo/yolean/concurrent/CopyOnWriteHashMap.java b/yolean/src/main/java/com/yahoo/yolean/concurrent/CopyOnWriteHashMap.java
new file mode 100644
index 00000000000..38c6abf055b
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/concurrent/CopyOnWriteHashMap.java
@@ -0,0 +1,94 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.concurrent;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * <p>This is a thread hash map for small collections that are stable once built. Until it is stable there will be a
+ * race among all threads missing something in the map. They will then clone the map add the missing stuff and then put
+ * it back as active again. Here are no locks, but the cost is that inserts will happen a lot more than necessary. The
+ * map reference is volatile, but on most multi-cpu machines that has no cost unless modified.</p>
+ *
+ * @author <a href="mailto:balder@yahoo-inc.com">Henning Baldersheim</a>
+ * @since 5.2
+ */
+public class CopyOnWriteHashMap<K, V> implements Map<K, V> {
+
+    private volatile HashMap<K, V> map = new HashMap<>();
+
+    @Override
+    public int size() {
+        return map.size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return map.isEmpty();
+    }
+
+    @Override
+    public boolean containsKey(Object key) {
+        return map.containsKey(key);
+    }
+
+    @Override
+    public boolean containsValue(Object value) {
+        return map.containsValue(value);
+    }
+
+    @Override
+    public V get(Object key) {
+        return map.get(key);
+    }
+
+    @Override
+    public V put(K key, V value) {
+        HashMap<K, V> next = new HashMap<>(map);
+        V old = next.put(key, value);
+        map = next;
+        return old;
+    }
+
+    @Override
+    @SuppressWarnings("SuspiciousMethodCalls")
+    public V remove(Object key) {
+        HashMap<K, V> prev = map;
+        if (!prev.containsKey(key)) {
+            return null;
+        }
+        HashMap<K, V> next = new HashMap<>(prev);
+        V old = next.remove(key);
+        map = next;
+        return old;
+    }
+
+    @Override
+    public void putAll(Map<? extends K, ? extends V> m) {
+        HashMap<K, V> next = new HashMap<>(map);
+        next.putAll(m);
+        map = next;
+    }
+
+    @Override
+    public void clear() {
+        map = new HashMap<>();
+    }
+
+    @Override
+    public Set<K> keySet() {
+        return map.keySet();
+    }
+
+    @Override
+    public Collection<V> values() {
+        return map.values();
+    }
+
+    @Override
+    public Set<Entry<K, V>> entrySet() {
+        return map.entrySet();
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/concurrent/ThreadRobustList.java b/yolean/src/main/java/com/yahoo/yolean/concurrent/ThreadRobustList.java
new file mode 100644
index 00000000000..5060ed8ef6a
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/concurrent/ThreadRobustList.java
@@ -0,0 +1,122 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.concurrent;
+
+import java.util.Arrays;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * <p>This class implements a thread-safe, lock-free list of Objects that supports multiple readers and a single writer.
+ * Because there are no locks or other memory barriers involved, there exists no <i>happens-before</i> relationship
+ * among calls to either methods of the <tt>ThreadRobustList</tt>. This means that there are no guarantees as to when
+ * (or even if) an item {@link #add(Object)}ed becomes visible through {@link #iterator()}. If visibility is required,
+ * either use explicit synchronization between reader and writer thread, or move to a different concurrent collection
+ * (e.g. <tt>CopyOnWriteArrayList</tt>).</p>
+ * <p>Because it is lock-free, the <tt>ThreadRobustList</tt> has minimal overhead to both reading and writing. The
+ * iterator offered by this class always observes the list in a consistent state, and it never throws a
+ * <tt>ConcurrentModificationException</tt>.</p>
+ * <p>The <tt>ThreadRobustList</tt> does not permit adding <tt>null</tt> items.</p>
+ * <p>The usage of <tt>ThreadRobustList</tt> has no memory consistency effects. </p>
+ *
+ * @author <a href="mailto:steinar@yahoo-inc.com">Steinar Knutsen</a>
+ * @author <a href="mailto:bratseth@yahoo-inc.com">Jon Bratseth</a>
+ * @since 5.1.15
+ */
+public class ThreadRobustList<T> implements Iterable<T> {
+
+    private Object[] items;
+    private int next = 0;
+
+    /**
+     * <p>Constructs a new instance of this class with an initial capacity of <tt>10</tt>.</p>
+     */
+    public ThreadRobustList() {
+        this(10);
+    }
+
+    /**
+     * <p>Constructs a new instance of this class with a given initial capacity.</p>
+     *
+     * @param initialCapacity the initial capacity of this list
+     */
+    public ThreadRobustList(int initialCapacity) {
+        items = new Object[initialCapacity];
+    }
+
+    /**
+     * <p>Returns whether or not this list is empty.</p>
+     *
+     * @return <tt>true</tt> if this list has zero items
+     */
+    public boolean isEmpty() {
+        return next == 0;
+    }
+
+    /**
+     * <p>Adds an item to this list. As opposed to <tt>CopyOnWriteArrayList</tt>, items added to this list may become
+     * visible to iterators created <em>before</em> a call to this method.</p>
+     *
+     * @param item the item to add
+     * @throws NullPointerException if <tt>item</tt> is <tt>null</tt>
+     */
+    public void add(T item) {
+        if (item == null) {
+            throw new NullPointerException();
+        }
+        Object[] workItems = items;
+        if (next >= items.length) {
+            workItems = Arrays.copyOf(workItems, 20 + items.length * 2);
+            workItems[next++] = item;
+            items = workItems;
+        } else {
+            workItems[next++] = item;
+        }
+    }
+
+    /**
+     * <p>Returns an iterator over the items in this list. As opposed to <tt>CopyOnWriteArrayList</tt>, this iterator
+     * may see items added to the <tt>ThreadRobustList</tt> even if they occur <em>after</em> a call to this method.</p>
+     * <p>The returned iterator does not support <tt>remove()</tt>.</p>
+     *
+     * @return an iterator over this list
+     */
+    @Override
+    public Iterator<T> iterator() {
+        return new ThreadRobustIterator<>(items);
+    }
+
+    private static class ThreadRobustIterator<T> implements Iterator<T> {
+
+        final Object[] items;
+        int nextIndex = 0;
+
+        ThreadRobustIterator(Object[] items) {
+            this.items = items;
+        }
+
+        @Override
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+
+        @SuppressWarnings("unchecked")
+        @Override
+        public T next() {
+            if (!hasNext()) {
+                throw new NoSuchElementException();
+            }
+            return (T)items[nextIndex++];
+        }
+
+        @Override
+        public boolean hasNext() {
+            if (nextIndex >= items.length) {
+                return false;
+            }
+            if (items[nextIndex] == null) {
+                return false;
+            }
+            return true;
+        }
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/concurrent/package-info.java b/yolean/src/main/java/com/yahoo/yolean/concurrent/package-info.java
new file mode 100644
index 00000000000..2062e224f79
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/concurrent/package-info.java
@@ -0,0 +1,7 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+@ExportPackage
+@PublicApi
+package com.yahoo.yolean.concurrent;
+
+import com.yahoo.api.annotations.PublicApi;
+import com.yahoo.osgi.annotation.ExportPackage;
diff --git a/yolean/src/main/java/com/yahoo/yolean/function/ThrowingConsumer.java b/yolean/src/main/java/com/yahoo/yolean/function/ThrowingConsumer.java
new file mode 100644
index 00000000000..1ba28d27c4c
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/function/ThrowingConsumer.java
@@ -0,0 +1,20 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.function;
+
+import java.util.Objects;
+
+/**
+ * Functional interface that mirrors the Consumer interface, but allows for an
+ * exception to be thrown.
+ *
+ * @author oyving
+ */
+@FunctionalInterface
+public interface ThrowingConsumer<T, E extends Throwable> {
+    void accept(T input) throws E;
+
+    default ThrowingConsumer<T, E> andThen(ThrowingConsumer<? super T, ? extends E> after) {
+        Objects.requireNonNull(after);
+        return (T t) -> { accept(t); after.accept(t); };
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/function/ThrowingFunction.java b/yolean/src/main/java/com/yahoo/yolean/function/ThrowingFunction.java
new file mode 100644
index 00000000000..3db84c6ba95
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/function/ThrowingFunction.java
@@ -0,0 +1,25 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.function;
+
+import java.util.Objects;
+
+/**
+ * Functional interface that mirrors the Function interface, but allows for an
+ * exception to be thrown.
+ *
+ * @author oyving
+ */
+@FunctionalInterface
+public interface ThrowingFunction<T, R, E extends Throwable> {
+    R apply(T input) throws E;
+
+    default <V> ThrowingFunction<T, V, E> andThen(ThrowingFunction<? super R, ? extends V, ? extends E> after) {
+        Objects.requireNonNull(after);
+        return (T t) -> after.apply(apply(t));
+    }
+
+    default <V> ThrowingFunction<V, R, E> compose(ThrowingFunction<? super V, ? extends T, ? extends E> before) {
+        Objects.requireNonNull(before);
+        return (V v) -> apply(before.apply(v));
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/function/ThrowingSupplier.java b/yolean/src/main/java/com/yahoo/yolean/function/ThrowingSupplier.java
new file mode 100644
index 00000000000..bee32af563b
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/function/ThrowingSupplier.java
@@ -0,0 +1,13 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.function;
+
+/**
+ * Functional interface that mirrors the Supplier interface, but allows for an
+ * exception to be thrown.
+ *
+ * @author oyving
+ */
+@FunctionalInterface
+public interface ThrowingSupplier<R, E extends Throwable> {
+    R get() throws E;
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/function/package-info.java b/yolean/src/main/java/com/yahoo/yolean/function/package-info.java
new file mode 100644
index 00000000000..38f7effc2bb
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/function/package-info.java
@@ -0,0 +1,10 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+/**
+ * @author oyving
+ */
+@ExportPackage
+@PublicApi
+package com.yahoo.yolean.function;
+
+import com.yahoo.api.annotations.PublicApi;
+import com.yahoo.osgi.annotation.ExportPackage;
diff --git a/yolean/src/main/java/com/yahoo/yolean/package-info.java b/yolean/src/main/java/com/yahoo/yolean/package-info.java
new file mode 100644
index 00000000000..444ed2496be
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/package-info.java
@@ -0,0 +1,7 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+@ExportPackage
+@PublicApi
+package com.yahoo.yolean;
+
+import com.yahoo.api.annotations.PublicApi;
+import com.yahoo.osgi.annotation.ExportPackage;
diff --git a/yolean/src/main/java/com/yahoo/yolean/trace/TraceNode.java b/yolean/src/main/java/com/yahoo/yolean/trace/TraceNode.java
new file mode 100644
index 00000000000..d7e9d128ebd
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/trace/TraceNode.java
@@ -0,0 +1,247 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.trace;
+
+import com.yahoo.yolean.concurrent.ThreadRobustList;
+
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+/**
+ * <p>This class represents a single node in a tree of <tt>TraceNodes</tt>. The trace forms a tree where there is a
+ * branch for each parallel execution, and a node within such a branch for each traced event. As each <tt>TraceNode</tt>
+ * may contain a payload of any type, the trace tree can be used to exchange any thread-safe state between producers and
+ * consumers in different threads, whether or not the shape of the trace tree is relevant to the particular
+ * information.</p>
+ * <p>This class uses a {@link ThreadRobustList} for its children. That list allows multiple threads to inspect the
+ * hierarchy of a <tt>TraceNode</tt> tree while there are other threads concurrently modifying it, without incurring the
+ * cost of memory synchronization. The only caveat being that for each <tt>TraceNode</tt> there can never be more than
+ * exactly one writer thread. If multiple threads need to mutate a single <tt>TraceNode</tt>, then the writer threads
+ * need to synchronize their access on the <tt>TraceNode</tt>.</p>
+ *
+ * @author <a href="mailto:steinar@yahoo-inc.com">Steinar Knutsen</a>
+ * @author <a href="mailto:bratseth@yahoo-inc.com">Jon Bratseth</a>
+ * @since 5.1.15
+ */
+public class TraceNode {
+
+    private final Object payload;
+    private final long timestamp;
+    private ThreadRobustList<TraceNode> children;
+    private TraceNode parent;
+
+    /**
+     * <p>Creates a new instance of this class.</p>
+     *
+     * @param payload   the payload to assign to this, may be <tt>null</tt>
+     * @param timestamp the timestamp to assign to this
+     */
+    public TraceNode(Object payload, long timestamp) {
+        this.payload = payload;
+        this.timestamp = timestamp;
+    }
+
+    /**
+     * <p>Adds another <tt>TraceNode</tt> as a child to this.</p>
+     *
+     * @param child the TraceNode to add
+     * @return this, to allow chaining
+     * @throws IllegalArgumentException if <tt>child</tt> is not a root TraceNode
+     * @see #isRoot()
+     */
+    public TraceNode add(TraceNode child) {
+        if (child.parent != null) {
+            throw new IllegalArgumentException("Can not add " + child + " to " + this + "; it is not a root.");
+        }
+        child.parent = this;
+        if (children == null) {
+            children = new ThreadRobustList<>();
+        }
+        children.add(child);
+        return this;
+    }
+
+    /**
+     * <p>Returns a read-only iterable of all {@link #payload() payloads} that are instances of <tt>payloadType</tt>,
+     * in all its decendants. The payload of <em>this</em> <tt>TraceNode</tt> is ignored.</p>
+     * <p>The payloads are retrieved in depth-first, prefix order.</p>
+     *
+     * @param payloadType the type of payloads to retrieve
+     * @return the payloads, never <tt>null</tt>
+     */
+    public <PAYLOADTYPE> Iterable<PAYLOADTYPE> descendants(final Class<PAYLOADTYPE> payloadType) {
+        if (children == null) {
+            return Collections.emptyList();
+        }
+        return new Iterable<PAYLOADTYPE>() {
+
+            @Override
+            public Iterator<PAYLOADTYPE> iterator() {
+                return new PayloadIterator<>(TraceNode.this, payloadType);
+            }
+        };
+    }
+
+    /**
+     * <p>Returns the payload of this <tt>TraceNode</tt>, or null if none.</p>
+     *
+     * @return the payload
+     */
+    public Object payload() {
+        return payload;
+    }
+
+    /**
+     * <p>Returns the timestamp of this <tt>TraceNode</tt>.</p>
+     *
+     * @return the timestamp
+     */
+    public long timestamp() {
+        return timestamp;
+    }
+
+    /**
+     * <p>Returns the parent <tt>TraceNode</tt> of this.</p>
+     *
+     * @return the parent
+     */
+    public TraceNode parent() {
+        return parent;
+    }
+
+    /**
+     * <p>Returns the child <tt>TraceNodes</tt> of this.</p>
+     *
+     * @return the children
+     */
+    public Iterable<TraceNode> children() {
+        if (children == null) {
+            return Collections.emptyList();
+        }
+        return children;
+    }
+
+    /**
+     * <p>Returns whether or not this <tt>TraceNode</tt> is a root node (i.e. it has no parent).</p>
+     *
+     * @return <tt>true</tt> if {@link #parent()} returns <tt>null</tt>
+     */
+    public boolean isRoot() {
+        return parent == null;
+    }
+
+    /**
+     * <p>Returns the root <tt>TraceNode</tt> of the tree that this <tt>TraceNode</tt> belongs to.</p>
+     *
+     * @return the root
+     */
+    public TraceNode root() {
+        TraceNode node = this;
+        while (node.parent != null) {
+            node = node.parent;
+        }
+        return node;
+    }
+
+    /**
+     * <p>Visits this <tt>TraceNode</tt> and all of its descendants in depth-first, prefix order.</p>
+     *
+     * @param visitor The visitor to accept.
+     * @return The <code>visitor</code> parameter.
+     */
+    public <T extends TraceVisitor> T accept(T visitor) {
+        visitor.visit(this);
+        if (children == null || children.isEmpty()) {
+            return visitor;
+        }
+        visitor.entering(this);
+        for (TraceNode child : children) {
+            child.accept(visitor);
+        }
+        visitor.leaving(this);
+        return visitor;
+    }
+
+    @Override
+    public String toString() {
+        final StringBuilder out = new StringBuilder("[ ");
+        accept(new TraceVisitor() {
+
+            @Override
+            public void visit(TraceNode node) {
+                if (node.payload != null) {
+                    out.append(node.payload).append(" ");
+                }
+            }
+
+            @Override
+            public void entering(TraceNode node) {
+                out.append("[ ");
+            }
+
+            @Override
+            public void leaving(TraceNode node) {
+                out.append("] ");
+            }
+        });
+        return out.append("]").toString();
+    }
+
+    private static class PayloadIterator<PAYLOADTYPE> implements Iterator<PAYLOADTYPE> {
+
+        final List<TraceNode> unexploredNodes = new LinkedList<>();
+        final Class<PAYLOADTYPE> payloadType;
+        PAYLOADTYPE next;
+
+        PayloadIterator(TraceNode root, Class<PAYLOADTYPE> payloadType) {
+            payloadType.getClass(); // throws NullPointerException
+            this.payloadType = payloadType;
+            unexploredNodes.add(root);
+            next = advance();
+        }
+
+        @Override
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean hasNext() {
+            return next != null;
+        }
+
+        @Override
+        public PAYLOADTYPE next() {
+            if (next == null) {
+                throw new NoSuchElementException();
+            }
+            PAYLOADTYPE current = next;
+            next = advance();
+            return current;
+        }
+
+        PAYLOADTYPE advance() {
+            // Current node is depleted, find next
+            while (unexploredNodes.size() > 0) {
+                // Take the next node
+                TraceNode node = unexploredNodes.remove(0);
+
+                // Add its children to the list of nodes we1'll look at
+                if (node.children != null) {
+                    int i = 0; // used to fabricate depth-first traversal order
+                    for (TraceNode child : node.children) {
+                        unexploredNodes.add(i++, child);
+                    }
+                }
+
+                Object payload = node.payload();
+                if (payloadType.isInstance(payload)) {
+                    return payloadType.cast(payload);
+                }
+            }
+            return null;
+        }
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/trace/TraceVisitor.java b/yolean/src/main/java/com/yahoo/yolean/trace/TraceVisitor.java
new file mode 100644
index 00000000000..2cb48616e56
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/trace/TraceVisitor.java
@@ -0,0 +1,45 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.yolean.trace;
+
+/**
+ * <p>This class is an abstract visitor of {@link TraceNode}. See {@link TraceNode#accept(TraceVisitor)}.</p>
+ *
+ * @author <a href="mailto:bratseth@yahoo-inc.com">Jon Bratseth</a>
+ * @since 5.1.15
+ */
+public abstract class TraceVisitor {
+
+    /**
+     * <p>Visits a {@link TraceNode}. Called by {@link TraceNode#accept(TraceVisitor)}, before visiting its
+     * children.</p>
+     *
+     * @param node the <tt>TraceNode</tt> being visited
+     * @see TraceNode#accept(TraceVisitor)
+     */
+    public abstract void visit(TraceNode node);
+
+    /**
+     * <p>Enters a {@link TraceNode}. This method is called after {@link #visit(TraceNode)}, but before visiting its
+     * children. Note that this method is NOT called if a <tt>TraceNode</tt> has zero children.</p>
+     * <p>The default implementation of this method does nothing.</p>
+     *
+     * @param node the <tt>TraceNode</tt> being entered
+     * @see #leaving(TraceNode)
+     */
+    @SuppressWarnings("UnusedParameters")
+    public void entering(TraceNode node) {
+        // empty
+    }
+
+    /**
+     * <p>Leaves a {@link TraceNode}. This method is called after {@link #entering(TraceNode)}, and after visiting its
+     * children. Note that this method is NOT called if a <tt>TraceNode</tt> has zero children.</p>
+     * <p>The default implementation of this method does nothing.</p>
+     *
+     * @param node the <tt>TraceNode</tt> being left
+     */
+    @SuppressWarnings("UnusedParameters")
+    public void leaving(TraceNode node) {
+        // empty
+    }
+}
diff --git a/yolean/src/main/java/com/yahoo/yolean/trace/package-info.java b/yolean/src/main/java/com/yahoo/yolean/trace/package-info.java
new file mode 100644
index 00000000000..7032992628c
--- /dev/null
+++ b/yolean/src/main/java/com/yahoo/yolean/trace/package-info.java
@@ -0,0 +1,7 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+@ExportPackage
+@PublicApi
+package com.yahoo.yolean.trace;
+
+import com.yahoo.api.annotations.PublicApi;
+import com.yahoo.osgi.annotation.ExportPackage;