Bug 1206290 - Part 1: Implement a JS::ubi::PostOrder depth first traversal; r=sfink
authorNick Fitzgerald <fitzgen@gmail.com>
Thu, 24 Sep 2015 14:01:22 -0700
changeset 264312 8bdf0fb54af38f04133f875afe3fbe9e84576273
parent 264311 b9b74d5bd4230bab9f761a32711ae28555645e28
child 264313 a99bc6984c8632063ad625e35940e90df7fea9da
push id29436
push usercbook@mozilla.com
push dateFri, 25 Sep 2015 12:39:56 +0000
treeherdermozilla-central@543e1b3a2588 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssfink
bugs1206290
milestone44.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1206290 - Part 1: Implement a JS::ubi::PostOrder depth first traversal; r=sfink
js/public/UbiNode.h
js/public/UbiNodePostOrder.h
js/src/jsapi-tests/testUbiNode.cpp
js/src/moz.build
--- a/js/public/UbiNode.h
+++ b/js/public/UbiNode.h
@@ -851,17 +851,18 @@ class EdgeRange {
     virtual ~EdgeRange() { }
 
     // True if there are no more edges in this range.
     bool empty() const { return !front_; }
 
     // The front edge of this range. This is owned by the EdgeRange, and is
     // only guaranteed to live until the next call to popFront, or until
     // the EdgeRange is destructed.
-    const Edge& front() { return *front_; }
+    const Edge& front() const { return *front_; }
+    Edge& front() { return *front_; }
 
     // Remove the front edge from this range. This should only be called if
     // !empty().
     virtual void popFront() = 0;
 
   private:
     EdgeRange(const EdgeRange&) = delete;
     EdgeRange& operator=(const EdgeRange&) = delete;
new file mode 100644
--- /dev/null
+++ b/js/public/UbiNodePostOrder.h
@@ -0,0 +1,165 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef js_UbiNodePostOrder_h
+#define js_UbiNodePostOrder_h
+
+#include "mozilla/DebugOnly.h"
+#include "mozilla/Move.h"
+
+#include "jsalloc.h"
+
+#include "js/UbiNode.h"
+#include "js/Utility.h"
+#include "js/Vector.h"
+
+namespace JS {
+namespace ubi {
+
+// A post-order depth-first traversal of `ubi::Node` graphs.
+//
+// NB: This traversal visits each node reachable from the start set exactly
+// once, and does not visit edges at all. Therefore, this traversal would be a
+// very poor choice for recording multiple paths to the same node, for example.
+// If your analysis needs to consider edges, use `JS::ubi::BreadthFirst`
+// instead.
+//
+// No GC may occur while an instance of `PostOrder` is live.
+//
+// The `Visitor` type provided to `PostOrder::traverse` must have the following
+// member:
+//
+//   bool operator()(Node& node)
+//
+//     The visitor method. This method is called once for each `node` reachable
+//     from the start set in post-order.
+//
+//     The visitor function should return true on success, or false if an error
+//     occurs. A false return value terminates the traversal immediately, and
+//     causes `PostOrder::traverse` to return false.
+struct PostOrder {
+  private:
+    struct OriginAndEdges {
+        Node       origin;
+        EdgeVector edges;
+
+        OriginAndEdges(const Node& node, EdgeVector&& edges)
+          : origin(node)
+          , edges(mozilla::Move(edges))
+        { }
+
+        OriginAndEdges(const OriginAndEdges& rhs) = delete;
+        OriginAndEdges& operator=(const OriginAndEdges& rhs) = delete;
+
+        OriginAndEdges(OriginAndEdges&& rhs)
+          : origin(rhs.origin)
+          , edges(mozilla::Move(rhs.edges))
+        {
+            MOZ_ASSERT(&rhs != this, "self-move disallowed");
+        }
+
+        OriginAndEdges& operator=(OriginAndEdges&& rhs) {
+            this->~OriginAndEdges();
+            new (this) OriginAndEdges(mozilla::Move(rhs));
+            return *this;
+        }
+    };
+
+    using Stack = js::Vector<OriginAndEdges, 256, js::SystemAllocPolicy>;
+    using Set = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>;
+
+    JSRuntime*               rt;
+    Set                      seen;
+    Stack                    stack;
+    mozilla::DebugOnly<bool> traversed;
+
+  private:
+    bool fillEdgesFromRange(EdgeVector& edges, UniquePtr<EdgeRange>& range) {
+        MOZ_ASSERT(range);
+        for ( ; !range->empty(); range->popFront()) {
+            if (!edges.append(mozilla::Move(range->front())))
+                return false;
+        }
+        return true;
+    }
+
+    bool pushForTraversing(const Node& node) {
+        EdgeVector edges;
+        auto range = node.edges(rt, /* wantNames */ false);
+        return range &&
+            fillEdgesFromRange(edges, range) &&
+            stack.append(OriginAndEdges(node, mozilla::Move(edges)));
+    }
+
+
+  public:
+    // Construct a post-order traversal object.
+    //
+    // The traversal asserts that no GC happens in its runtime during its
+    // lifetime via the `AutoCheckCannotGC&` parameter. We do nothing with it,
+    // other than require it to exist with a lifetime that encloses our own.
+    PostOrder(JSRuntime* rt, AutoCheckCannotGC&)
+      : rt(rt)
+      , seen()
+      , stack()
+      , traversed(false)
+    { }
+
+    // Initialize this traversal object. Return false on OOM.
+    bool init() { return seen.init(); }
+
+    // Add `node` as a starting point for the traversal. You may add
+    // as many starting points as you like. Returns false on OOM.
+    bool addStart(const Node& node) {
+        if (!seen.put(node))
+            return false;
+        return pushForTraversing(node);
+    }
+
+    // Traverse the graph in post-order, starting with the set of nodes passed
+    // to `addStart` and applying `visitor::operator()` for each node in
+    // the graph, as described above.
+    //
+    // This should be called only once per instance of this class.
+    //
+    // Return false on OOM or error return from `visitor::operator()`.
+    template<typename Visitor>
+    bool traverse(Visitor visitor) {
+        MOZ_ASSERT(!traversed, "Can only traverse() once!");
+        traversed = true;
+
+        while (!stack.empty()) {
+            auto& origin = stack.back().origin;
+            auto& edges = stack.back().edges;
+
+            if (edges.empty()) {
+                if (!visitor(origin))
+                    return false;
+                stack.popBack();
+                continue;
+            }
+
+            Edge edge = mozilla::Move(edges.back());
+            edges.popBack();
+
+            auto ptr = seen.lookupForAdd(edge.referent);
+            // We've already seen this node, don't follow its edges.
+            if (ptr)
+                continue;
+
+            // Mark the referent as seen and follow its edges.
+            if (!seen.add(ptr, edge.referent) || !pushForTraversing(edge.referent))
+                return false;
+        }
+
+        return true;
+    }
+};
+
+} // namespace ubi
+} // namespace JS
+
+#endif // js_UbiNodePostOrder_h
--- a/js/src/jsapi-tests/testUbiNode.cpp
+++ b/js/src/jsapi-tests/testUbiNode.cpp
@@ -1,21 +1,62 @@
 /* This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "builtin/TestingFunctions.h"
 #include "js/UbiNode.h"
+#include "js/UbiNodePostOrder.h"
 #include "jsapi-tests/tests.h"
 #include "vm/SavedFrame.h"
 
 using JS::RootedObject;
 using JS::RootedScript;
 using JS::RootedString;
 
+// A helper JS::ubi::Node concrete implementation that can be used to make mock
+// graphs for testing traversals with.
+struct FakeNode
+{
+    char                name;
+    JS::ubi::EdgeVector edges;
+
+    explicit FakeNode(char name) : name(name), edges() { }
+
+    bool addEdgeTo(FakeNode& referent) {
+        JS::ubi::Node node(&referent);
+        return edges.emplaceBack(nullptr, node);
+    }
+};
+
+namespace JS {
+namespace ubi {
+
+template<>
+struct Concrete<FakeNode> : public Base
+{
+    static const char16_t concreteTypeName[];
+    const char16_t* typeName() const { return concreteTypeName; }
+
+    UniquePtr<EdgeRange> edges(JSRuntime* rt, bool wantNames) const {
+        return UniquePtr<EdgeRange>(js_new<PreComputedEdgeRange>(get().edges));
+    }
+
+    static void construct(void* storage, FakeNode* ptr) { new (storage) Concrete(ptr); }
+
+  protected:
+    explicit Concrete(FakeNode* ptr) : Base(ptr) { }
+    FakeNode& get() const { return *static_cast<FakeNode*>(ptr); }
+};
+
+const char16_t Concrete<FakeNode>::concreteTypeName[] = MOZ_UTF16("FakeNode");
+
+} // namespace ubi
+} // namespace JS
+
 // ubi::Node::zone works
 BEGIN_TEST(test_ubiNodeZone)
 {
     RootedObject global1(cx, JS::CurrentGlobalOrNull(cx));
     CHECK(global1);
     CHECK(JS::ubi::Node(global1).zone() == cx->zone());
 
     RootedObject global2(cx, JS_NewGlobalObject(cx, getGlobalClass(), nullptr,
@@ -218,8 +259,89 @@ BEGIN_TEST(test_ubiCoarseType)
     // Test that the default when coarseType() is not overridden is Other.
 
     JS::Symbol* sym = nullptr;
     CHECK(JS::ubi::Node(sym).coarseType() == JS::ubi::CoarseType::Other);
 
     return true;
 }
 END_TEST(test_ubiCoarseType)
+
+BEGIN_TEST(test_ubiPostOrder)
+{
+    // Construct the following graph:
+    //
+    //                          .-----.
+    //                          |     |
+    //                  .-------|  r  |---------------.
+    //                  |       |     |               |
+    //                  |       '-----'               |
+    //                  |                             |
+    //               .--V--.                       .--V--.
+    //               |     |                       |     |
+    //        .------|  a  |------.           .----|  e  |----.
+    //        |      |     |      |           |    |     |    |
+    //        |      '--^--'      |           |    '-----'    |
+    //        |         |         |           |               |
+    //     .--V--.      |      .--V--.     .--V--.         .--V--.
+    //     |     |      |      |     |     |     |         |     |
+    //     |  b  |      '------|  c  |----->  f  |--------->  g  |
+    //     |     |             |     |     |     |         |     |
+    //     '-----'             '-----'     '-----'         '-----'
+    //        |                   |
+    //        |      .-----.      |
+    //        |      |     |      |
+    //        '------>  d  <------'
+    //               |     |
+    //               '-----'
+    //
+
+    FakeNode r('r');
+    FakeNode a('a');
+    FakeNode b('b');
+    FakeNode c('c');
+    FakeNode d('d');
+    FakeNode e('e');
+    FakeNode f('f');
+    FakeNode g('g');
+
+    r.addEdgeTo(a);
+    r.addEdgeTo(e);
+    a.addEdgeTo(b);
+    a.addEdgeTo(c);
+    b.addEdgeTo(d);
+    c.addEdgeTo(a);
+    c.addEdgeTo(d);
+    c.addEdgeTo(f);
+    e.addEdgeTo(f);
+    e.addEdgeTo(g);
+    f.addEdgeTo(g);
+
+    js::Vector<char, 8, js::SystemAllocPolicy> visited;
+    {
+        // Do a PostOrder traversal, starting from r. Accumulate the names of
+        // the nodes we visit in `visited`.
+        JS::AutoCheckCannotGC nogc(rt);
+        JS::ubi::PostOrder traversal(rt, nogc);
+        CHECK(traversal.init());
+        CHECK(traversal.addStart(&r));
+        CHECK(traversal.traverse([&](const JS::ubi::Node& node) {
+            return visited.append(node.as<FakeNode>()->name);
+        }));
+    }
+
+    fprintf(stderr, "visited.length() = %lu\n", (unsigned long) visited.length());
+    for (size_t i = 0; i < visited.length(); i++)
+        fprintf(stderr, "visited[%lu] = '%c'\n", (unsigned long) i, visited[i]);
+
+    CHECK(visited.length() == 8);
+    CHECK(visited[0] == 'g');
+    CHECK(visited[1] == 'f');
+    CHECK(visited[2] == 'e');
+    CHECK(visited[3] == 'd');
+    CHECK(visited[4] == 'c');
+    CHECK(visited[5] == 'b');
+    CHECK(visited[6] == 'a');
+    CHECK(visited[7] == 'r');
+
+    return true;
+}
+END_TEST(test_ubiPostOrder)
--- a/js/src/moz.build
+++ b/js/src/moz.build
@@ -126,16 +126,17 @@ EXPORTS.js += [
     '../public/TraceableVector.h',
     '../public/TraceKind.h',
     '../public/TracingAPI.h',
     '../public/TrackedOptimizationInfo.h',
     '../public/TypeDecls.h',
     '../public/UbiNode.h',
     '../public/UbiNodeBreadthFirst.h',
     '../public/UbiNodeCensus.h',
+    '../public/UbiNodePostOrder.h',
     '../public/Utility.h',
     '../public/Value.h',
     '../public/Vector.h',
     '../public/WeakMapPtr.h',
 ]
 
 UNIFIED_SOURCES += [
     'asmjs/AsmJSCompile.cpp',