summaryrefslogtreecommitdiffstats
path: root/js/public/UbiNodeShortestPaths.h
diff options
context:
space:
mode:
authorMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
committerMatt A. Tobin <mattatobin@localhost.localdomain>2018-02-02 04:16:08 -0500
commit5f8de423f190bbb79a62f804151bc24824fa32d8 (patch)
tree10027f336435511475e392454359edea8e25895d /js/public/UbiNodeShortestPaths.h
parent49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff)
downloadUXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz
UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip
Add m-esr52 at 52.6.0
Diffstat (limited to 'js/public/UbiNodeShortestPaths.h')
-rw-r--r--js/public/UbiNodeShortestPaths.h350
1 files changed, 350 insertions, 0 deletions
diff --git a/js/public/UbiNodeShortestPaths.h b/js/public/UbiNodeShortestPaths.h
new file mode 100644
index 000000000..edd5aebbe
--- /dev/null
+++ b/js/public/UbiNodeShortestPaths.h
@@ -0,0 +1,350 @@
+/* -*- 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_UbiNodeShortestPaths_h
+#define js_UbiNodeShortestPaths_h
+
+#include "mozilla/Attributes.h"
+#include "mozilla/Maybe.h"
+#include "mozilla/Move.h"
+
+#include "jsalloc.h"
+
+#include "js/UbiNodeBreadthFirst.h"
+#include "js/Vector.h"
+
+namespace JS {
+namespace ubi {
+
+/**
+ * A back edge along a path in the heap graph.
+ */
+struct JS_PUBLIC_API(BackEdge)
+{
+ private:
+ Node predecessor_;
+ EdgeName name_;
+
+ public:
+ using Ptr = mozilla::UniquePtr<BackEdge, JS::DeletePolicy<BackEdge>>;
+
+ BackEdge() : predecessor_(), name_(nullptr) { }
+
+ MOZ_MUST_USE bool init(const Node& predecessor, Edge& edge) {
+ MOZ_ASSERT(!predecessor_);
+ MOZ_ASSERT(!name_);
+
+ predecessor_ = predecessor;
+ name_ = mozilla::Move(edge.name);
+ return true;
+ }
+
+ BackEdge(const BackEdge&) = delete;
+ BackEdge& operator=(const BackEdge&) = delete;
+
+ BackEdge(BackEdge&& rhs)
+ : predecessor_(rhs.predecessor_)
+ , name_(mozilla::Move(rhs.name_))
+ {
+ MOZ_ASSERT(&rhs != this);
+ }
+
+ BackEdge& operator=(BackEdge&& rhs) {
+ this->~BackEdge();
+ new(this) BackEdge(Move(rhs));
+ return *this;
+ }
+
+ Ptr clone() const;
+
+ const EdgeName& name() const { return name_; }
+ EdgeName& name() { return name_; }
+
+ const JS::ubi::Node& predecessor() const { return predecessor_; }
+};
+
+/**
+ * A path is a series of back edges from which we discovered a target node.
+ */
+using Path = JS::ubi::Vector<BackEdge*>;
+
+/**
+ * The `JS::ubi::ShortestPaths` type represents a collection of up to N shortest
+ * retaining paths for each of a target set of nodes, starting from the same
+ * root node.
+ */
+struct JS_PUBLIC_API(ShortestPaths)
+{
+ private:
+ // Types, type aliases, and data members.
+
+ using BackEdgeVector = JS::ubi::Vector<BackEdge::Ptr>;
+ using NodeToBackEdgeVectorMap = js::HashMap<Node, BackEdgeVector, js::DefaultHasher<Node>,
+ js::SystemAllocPolicy>;
+
+ struct Handler;
+ using Traversal = BreadthFirst<Handler>;
+
+ /**
+ * A `JS::ubi::BreadthFirst` traversal handler that records back edges for
+ * how we reached each node, allowing us to reconstruct the shortest
+ * retaining paths after the traversal.
+ */
+ struct Handler
+ {
+ using NodeData = BackEdge;
+
+ ShortestPaths& shortestPaths;
+ size_t totalMaxPathsToRecord;
+ size_t totalPathsRecorded;
+
+ explicit Handler(ShortestPaths& shortestPaths)
+ : shortestPaths(shortestPaths)
+ , totalMaxPathsToRecord(shortestPaths.targets_.count() * shortestPaths.maxNumPaths_)
+ , totalPathsRecorded(0)
+ {
+ }
+
+ bool
+ operator()(Traversal& traversal, JS::ubi::Node origin, JS::ubi::Edge& edge,
+ BackEdge* back, bool first)
+ {
+ MOZ_ASSERT(back);
+ MOZ_ASSERT(origin == shortestPaths.root_ || traversal.visited.has(origin));
+ MOZ_ASSERT(totalPathsRecorded < totalMaxPathsToRecord);
+
+ if (first && !back->init(origin, edge))
+ return false;
+
+ if (!shortestPaths.targets_.has(edge.referent))
+ return true;
+
+ // If `first` is true, then we moved the edge's name into `back` in
+ // the above call to `init`. So clone that back edge to get the
+ // correct edge name. If `first` is not true, then our edge name is
+ // still in `edge`. This accounts for the asymmetry between
+ // `back->clone()` in the first branch, and the `init` call in the
+ // second branch.
+
+ if (first) {
+ BackEdgeVector paths;
+ if (!paths.reserve(shortestPaths.maxNumPaths_))
+ return false;
+ auto cloned = back->clone();
+ if (!cloned)
+ return false;
+ paths.infallibleAppend(mozilla::Move(cloned));
+ if (!shortestPaths.paths_.putNew(edge.referent, mozilla::Move(paths)))
+ return false;
+ totalPathsRecorded++;
+ } else {
+ auto ptr = shortestPaths.paths_.lookup(edge.referent);
+ MOZ_ASSERT(ptr,
+ "This isn't the first time we have seen the target node `edge.referent`. "
+ "We should have inserted it into shortestPaths.paths_ the first time we "
+ "saw it.");
+
+ if (ptr->value().length() < shortestPaths.maxNumPaths_) {
+ BackEdge::Ptr thisBackEdge(js_new<BackEdge>());
+ if (!thisBackEdge || !thisBackEdge->init(origin, edge))
+ return false;
+ ptr->value().infallibleAppend(mozilla::Move(thisBackEdge));
+ totalPathsRecorded++;
+ }
+ }
+
+ MOZ_ASSERT(totalPathsRecorded <= totalMaxPathsToRecord);
+ if (totalPathsRecorded == totalMaxPathsToRecord)
+ traversal.stop();
+
+ return true;
+ }
+
+ };
+
+ // The maximum number of paths to record for each node.
+ uint32_t maxNumPaths_;
+
+ // The root node we are starting the search from.
+ Node root_;
+
+ // The set of nodes we are searching for paths to.
+ NodeSet targets_;
+
+ // The resulting paths.
+ NodeToBackEdgeVectorMap paths_;
+
+ // Need to keep alive the traversal's back edges so we can walk them later
+ // when the traversal is over when recreating the shortest paths.
+ Traversal::NodeMap backEdges_;
+
+ private:
+ // Private methods.
+
+ ShortestPaths(uint32_t maxNumPaths, const Node& root, NodeSet&& targets)
+ : maxNumPaths_(maxNumPaths)
+ , root_(root)
+ , targets_(mozilla::Move(targets))
+ , paths_()
+ , backEdges_()
+ {
+ MOZ_ASSERT(maxNumPaths_ > 0);
+ MOZ_ASSERT(root_);
+ MOZ_ASSERT(targets_.initialized());
+ }
+
+ bool initialized() const {
+ return targets_.initialized() &&
+ paths_.initialized() &&
+ backEdges_.initialized();
+ }
+
+ public:
+ // Public methods.
+
+ ShortestPaths(ShortestPaths&& rhs)
+ : maxNumPaths_(rhs.maxNumPaths_)
+ , root_(rhs.root_)
+ , targets_(mozilla::Move(rhs.targets_))
+ , paths_(mozilla::Move(rhs.paths_))
+ , backEdges_(mozilla::Move(rhs.backEdges_))
+ {
+ MOZ_ASSERT(this != &rhs, "self-move is not allowed");
+ }
+
+ ShortestPaths& operator=(ShortestPaths&& rhs) {
+ this->~ShortestPaths();
+ new (this) ShortestPaths(mozilla::Move(rhs));
+ return *this;
+ }
+
+ ShortestPaths(const ShortestPaths&) = delete;
+ ShortestPaths& operator=(const ShortestPaths&) = delete;
+
+ /**
+ * Construct a new `JS::ubi::ShortestPaths`, finding up to `maxNumPaths`
+ * shortest retaining paths for each target node in `targets` starting from
+ * `root`.
+ *
+ * The resulting `ShortestPaths` instance must not outlive the
+ * `JS::ubi::Node` graph it was constructed from.
+ *
+ * - For `JS::ubi::Node` graphs backed by the live heap graph, this means
+ * that the `ShortestPaths`'s lifetime _must_ be contained within the
+ * scope of the provided `AutoCheckCannotGC` reference because a GC will
+ * invalidate the nodes.
+ *
+ * - For `JS::ubi::Node` graphs backed by some other offline structure
+ * provided by the embedder, the resulting `ShortestPaths`'s lifetime is
+ * bounded by that offline structure's lifetime.
+ *
+ * Returns `mozilla::Nothing()` on OOM failure. It is the caller's
+ * responsibility to handle and report the OOM.
+ */
+ static mozilla::Maybe<ShortestPaths>
+ Create(JSContext* cx, AutoCheckCannotGC& noGC, uint32_t maxNumPaths, const Node& root, NodeSet&& targets) {
+ MOZ_ASSERT(targets.count() > 0);
+ MOZ_ASSERT(maxNumPaths > 0);
+
+ size_t count = targets.count();
+ ShortestPaths paths(maxNumPaths, root, mozilla::Move(targets));
+ if (!paths.paths_.init(count))
+ return mozilla::Nothing();
+
+ Handler handler(paths);
+ Traversal traversal(cx, handler, noGC);
+ traversal.wantNames = true;
+ if (!traversal.init() || !traversal.addStart(root) || !traversal.traverse())
+ return mozilla::Nothing();
+
+ // Take ownership of the back edges we created while traversing the
+ // graph so that we can follow them from `paths_` and don't
+ // use-after-free.
+ paths.backEdges_ = mozilla::Move(traversal.visited);
+
+ MOZ_ASSERT(paths.initialized());
+ return mozilla::Some(mozilla::Move(paths));
+ }
+
+ /**
+ * Get a range that iterates over each target node we searched for retaining
+ * paths for. The returned range must not outlive the `ShortestPaths`
+ * instance.
+ */
+ NodeSet::Range eachTarget() const {
+ MOZ_ASSERT(initialized());
+ return targets_.all();
+ }
+
+ /**
+ * Invoke the provided functor/lambda/callable once for each retaining path
+ * discovered for `target`. The `func` is passed a single `JS::ubi::Path&`
+ * argument, which contains each edge along the path ordered starting from
+ * the root and ending at the target, and must not outlive the scope of the
+ * call.
+ *
+ * Note that it is possible that we did not find any paths from the root to
+ * the given target, in which case `func` will not be invoked.
+ */
+ template <class Func>
+ MOZ_MUST_USE bool forEachPath(const Node& target, Func func) {
+ MOZ_ASSERT(initialized());
+ MOZ_ASSERT(targets_.has(target));
+
+ auto ptr = paths_.lookup(target);
+
+ // We didn't find any paths to this target, so nothing to do here.
+ if (!ptr)
+ return true;
+
+ MOZ_ASSERT(ptr->value().length() <= maxNumPaths_);
+
+ Path path;
+ for (const auto& backEdge : ptr->value()) {
+ path.clear();
+
+ if (!path.append(backEdge.get()))
+ return false;
+
+ Node here = backEdge->predecessor();
+ MOZ_ASSERT(here);
+
+ while (here != root_) {
+ auto p = backEdges_.lookup(here);
+ MOZ_ASSERT(p);
+ if (!path.append(&p->value()))
+ return false;
+ here = p->value().predecessor();
+ MOZ_ASSERT(here);
+ }
+
+ path.reverse();
+
+ if (!func(path))
+ return false;
+ }
+
+ return true;
+ }
+};
+
+#ifdef DEBUG
+// A helper function to dump the first `maxNumPaths` shortest retaining paths to
+// `node` from the GC roots. Useful when GC things you expect to have been
+// reclaimed by the collector haven't been!
+//
+// Usage:
+//
+// JSObject* foo = ...;
+// JS::ubi::dumpPaths(rt, JS::ubi::Node(foo));
+JS_PUBLIC_API(void)
+dumpPaths(JSRuntime* rt, Node node, uint32_t maxNumPaths = 10);
+#endif
+
+} // namespace ubi
+} // namespace JS
+
+#endif // js_UbiNodeShortestPaths_h