Differential D3095 Diff 13993 libraries/source/spidermonkey/include-win32-debug/js/UbiNodePostOrder.h
Changeset View
Changeset View
Standalone View
Standalone View
libraries/source/spidermonkey/include-win32-debug/js/UbiNodePostOrder.h
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- | ||||
* vim: set ts=8 sts=4 et sw=4 tw=99: | * vim: set ts=8 sts=4 et sw=4 tw=99: | ||||
* This Source Code Form is subject to the terms of the Mozilla Public | * 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 | * 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/. */ | * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | ||||
#ifndef js_UbiNodePostOrder_h | #ifndef js_UbiNodePostOrder_h | ||||
#define js_UbiNodePostOrder_h | #define js_UbiNodePostOrder_h | ||||
#include "mozilla/DebugOnly.h" | #include "mozilla/Attributes.h" | ||||
#include "mozilla/Maybe.h" | #include "mozilla/Maybe.h" | ||||
#include "mozilla/Move.h" | #include "mozilla/Move.h" | ||||
#include "jsalloc.h" | #include "jsalloc.h" | ||||
#include "js/UbiNode.h" | #include "js/UbiNode.h" | ||||
#include "js/Utility.h" | #include "js/Utility.h" | ||||
#include "js/Vector.h" | #include "js/Vector.h" | ||||
▲ Show 20 Lines • Show All 59 Lines • ▼ Show 20 Lines | struct OriginAndEdges { | ||||
new (this) OriginAndEdges(mozilla::Move(rhs)); | new (this) OriginAndEdges(mozilla::Move(rhs)); | ||||
return *this; | return *this; | ||||
} | } | ||||
}; | }; | ||||
using Stack = js::Vector<OriginAndEdges, 256, js::SystemAllocPolicy>; | using Stack = js::Vector<OriginAndEdges, 256, js::SystemAllocPolicy>; | ||||
using Set = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>; | using Set = js::HashSet<Node, js::DefaultHasher<Node>, js::SystemAllocPolicy>; | ||||
JSRuntime* rt; | JSContext* cx; | ||||
Set seen; | Set seen; | ||||
Stack stack; | Stack stack; | ||||
mozilla::DebugOnly<bool> traversed; | #ifdef DEBUG | ||||
bool traversed; | |||||
#endif | |||||
private: | private: | ||||
bool fillEdgesFromRange(EdgeVector& edges, UniquePtr<EdgeRange>& range) { | MOZ_MUST_USE bool fillEdgesFromRange(EdgeVector& edges, js::UniquePtr<EdgeRange>& range) { | ||||
MOZ_ASSERT(range); | MOZ_ASSERT(range); | ||||
for ( ; !range->empty(); range->popFront()) { | for ( ; !range->empty(); range->popFront()) { | ||||
if (!edges.append(mozilla::Move(range->front()))) | if (!edges.append(mozilla::Move(range->front()))) | ||||
return false; | return false; | ||||
} | } | ||||
return true; | return true; | ||||
} | } | ||||
bool pushForTraversing(const Node& node) { | MOZ_MUST_USE bool pushForTraversing(const Node& node) { | ||||
EdgeVector edges; | EdgeVector edges; | ||||
auto range = node.edges(rt, /* wantNames */ false); | auto range = node.edges(cx, /* wantNames */ false); | ||||
return range && | return range && | ||||
fillEdgesFromRange(edges, range) && | fillEdgesFromRange(edges, range) && | ||||
stack.append(OriginAndEdges(node, mozilla::Move(edges))); | stack.append(OriginAndEdges(node, mozilla::Move(edges))); | ||||
} | } | ||||
public: | public: | ||||
// Construct a post-order traversal object. | // Construct a post-order traversal object. | ||||
// | // | ||||
// The traversal asserts that no GC happens in its runtime during its | // The traversal asserts that no GC happens in its runtime during its | ||||
// lifetime via the `AutoCheckCannotGC&` parameter. We do nothing with it, | // lifetime via the `AutoCheckCannotGC&` parameter. We do nothing with it, | ||||
// other than require it to exist with a lifetime that encloses our own. | // other than require it to exist with a lifetime that encloses our own. | ||||
PostOrder(JSRuntime* rt, AutoCheckCannotGC&) | PostOrder(JSContext* cx, AutoCheckCannotGC&) | ||||
: rt(rt) | : cx(cx) | ||||
, seen() | , seen() | ||||
, stack() | , stack() | ||||
#ifdef DEBUG | |||||
, traversed(false) | , traversed(false) | ||||
#endif | |||||
{ } | { } | ||||
// Initialize this traversal object. Return false on OOM. | // Initialize this traversal object. Return false on OOM. | ||||
bool init() { return seen.init(); } | MOZ_MUST_USE bool init() { return seen.init(); } | ||||
// Add `node` as a starting point for the traversal. You may add | // Add `node` as a starting point for the traversal. You may add | ||||
// as many starting points as you like. Returns false on OOM. | // as many starting points as you like. Returns false on OOM. | ||||
bool addStart(const Node& node) { | MOZ_MUST_USE bool addStart(const Node& node) { | ||||
if (!seen.put(node)) | if (!seen.put(node)) | ||||
return false; | return false; | ||||
return pushForTraversing(node); | return pushForTraversing(node); | ||||
} | } | ||||
// Traverse the graph in post-order, starting with the set of nodes passed | // Traverse the graph in post-order, starting with the set of nodes passed | ||||
// to `addStart` and applying `onNode::operator()` for each node in the | // to `addStart` and applying `onNode::operator()` for each node in the | ||||
// graph and `onEdge::operator()` for each edge in the graph, as described | // graph and `onEdge::operator()` for each edge in the graph, as described | ||||
// above. | // above. | ||||
// | // | ||||
// This should be called only once per instance of this class. | // This should be called only once per instance of this class. | ||||
// | // | ||||
// Return false on OOM or error return from `onNode::operator()` or | // Return false on OOM or error return from `onNode::operator()` or | ||||
// `onEdge::operator()`. | // `onEdge::operator()`. | ||||
template<typename NodeVisitor, typename EdgeVisitor> | template<typename NodeVisitor, typename EdgeVisitor> | ||||
bool traverse(NodeVisitor onNode, EdgeVisitor onEdge) { | MOZ_MUST_USE bool traverse(NodeVisitor onNode, EdgeVisitor onEdge) { | ||||
#ifdef DEBUG | |||||
MOZ_ASSERT(!traversed, "Can only traverse() once!"); | MOZ_ASSERT(!traversed, "Can only traverse() once!"); | ||||
traversed = true; | traversed = true; | ||||
#endif | |||||
while (!stack.empty()) { | while (!stack.empty()) { | ||||
auto& origin = stack.back().origin; | auto& origin = stack.back().origin; | ||||
auto& edges = stack.back().edges; | auto& edges = stack.back().edges; | ||||
if (edges.empty()) { | if (edges.empty()) { | ||||
if (!onNode(origin)) | if (!onNode(origin)) | ||||
return false; | return false; | ||||
Show All 31 Lines |
Wildfire Games · Phabricator