/work/obj-fuzz/dist/include/js/UbiNodeBreadthFirst.h

Source (jump to first uncovered line)
/* -*- 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_UbiNodeBreadthFirst_h
#define js_UbiNodeBreadthFirst_h

#include "js/UbiNode.h"
#include "js/Utility.h"
#include "js/Vector.h"

namespace JS {
namespace ubi {

// A breadth-first traversal template for graphs of ubi::Nodes.
//
// No GC may occur while an instance of this template is live.
//
// The provided Handler type should have two members:
//
//   typename NodeData;
//
//      The value type of |BreadthFirst<Handler>::visited|, the HashMap of
//      ubi::Nodes that have been visited so far. Since the algorithm needs a
//      hash table like this for its own use anyway, it is simple to let
//      Handler store its own metadata about each node in the same table.
//
//      For example, if you want to find a shortest path to each node from any
//      traversal starting point, your |NodeData| type could record the first
//      edge to reach each node, and the node from which it originates. Then,
//      when the traversal is complete, you can walk backwards from any node
//      to some starting point, and the path recorded will be a shortest path.
//
//      This type must have a default constructor. If this type owns any other
//      resources, move constructors and assignment operators are probably a
//      good idea, too.
//
//   bool operator() (BreadthFirst& traversal,
//                    Node origin, const Edge& edge,
//                    Handler::NodeData* referentData, bool first);
//
//      The visitor function, called to report that we have traversed
//      |edge| from |origin|. This is called once for each edge we traverse.
//      As this is a breadth-first search, any prior calls to the visitor function
//      were for origin nodes not further from the start nodes than |origin|.
//
//      |traversal| is this traversal object, passed along for convenience.
//
//      |referentData| is a pointer to the value of the entry in
//      |traversal.visited| for |edge.referent|; the visitor function can
//      store whatever metadata it likes about |edge.referent| there.
//
//      |first| is true if this is the first time we have visited an edge
//      leading to |edge.referent|. This could be stored in NodeData, but
//      the algorithm knows whether it has just created the entry in
//      |traversal.visited|, so it passes it along for convenience.
//
//      The visitor function may call |traversal.abandonReferent()| if it
//      doesn't want to traverse the outgoing edges of |edge.referent|. You can
//      use this to limit the traversal to a given portion of the graph: it will
//      never visit nodes reachable only through nodes that you have abandoned.
//      Note that |abandonReferent| must be called the first time the given node
//      is reached; that is, |first| must be true.
//
//      The visitor function may call |traversal.stop()| if it doesn't want
//      to visit any more nodes at all.
//
//      The visitor function may consult |traversal.visited| for information
//      about other nodes, but it should not add or remove entries.
//
//      The visitor function should return true on success, or false if an
//      error occurs. A false return value terminates the traversal
//      immediately, and causes BreadthFirst<Handler>::traverse to return
//      false.
template<typename Handler>
struct BreadthFirst {

    // Construct a breadth-first traversal object that reports the nodes it
    // reaches to |handler|. The traversal asserts that no GC happens in its
    // runtime during its lifetime.
    //
    // We do nothing with noGC, other than require it to exist, with a lifetime
    // that encloses our own.
    BreadthFirst(JSContext* cx, Handler& handler, const JS::AutoRequireNoGC& noGC)
      : wantNames(true), cx(cx), visited(), handler(handler), pending(),
        traversalBegun(false), stopRequested(false), abandonRequested(false)
    { }

    // Add |node| as a starting point for the traversal. You may add
    // as many starting points as you like. Return false on OOM.
    bool addStart(Node node) { return pending.append(node); }

    // Add |node| as a starting point for the traversal (see addStart) and also
    // add it to the |visited| set. Return false on OOM.
    bool addStartVisited(Node node) {
        typename NodeMap::AddPtr ptr = visited.lookupForAdd(node);
        if (!ptr && !visited.add(ptr, node, typename Handler::NodeData())) {
            return false;
        }
        return addStart(node);
    }

    // True if the handler wants us to compute edge names; doing so can be
    // expensive in time and memory. True by default.
    bool wantNames;

    // Traverse the graph in breadth-first order, starting at the given
    // start nodes, applying |handler::operator()| for each edge traversed
    // as described above.
    //
    // This should be called only once per instance of this class.
    //
    // Return false on OOM or error return from |handler::operator()|.
    bool traverse()
    {
        MOZ_ASSERT(!traversalBegun);
        traversalBegun = true;

        // While there are pending nodes, visit them.
        while (!pending.empty()) {
            Node origin = pending.front();
            pending.popFront();

            // Get a range containing all origin's outgoing edges.
            auto range = origin.edges(cx, wantNames);
            if (!range) {
                return false;
            }

            // Traverse each edge.
            for (; !range->empty(); range->popFront()) {
                MOZ_ASSERT(!stopRequested);

                Edge& edge = range->front();
                typename NodeMap::AddPtr a = visited.lookupForAdd(edge.referent);
                bool first = !a;

                if (first) {
                    // This is the first time we've reached |edge.referent|.
                    // Mark it as visited.
                    if (!visited.add(a, edge.referent, typename Handler::NodeData())) {
                        return false;
                    }
                }

                MOZ_ASSERT(a);

                // Report this edge to the visitor function.
                if (!handler(*this, origin, edge, &a->value(), first)) {
                    return false;
                }

                if (stopRequested) {
                    return true;
                }

                // Arrange to traverse this edge's referent's outgoing edges
                // later --- unless |handler| asked us not to.
                if (abandonRequested) {
                    // Skip the enqueue; reset flag for future iterations.
                    abandonRequested = false;
                } else if (first) {
                    if (!pending.append(edge.referent)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }

    // Stop traversal, and return true from |traverse| without visiting any
    // more nodes. Only |handler::operator()| should call this function; it
    // may do so to stop the traversal early, without returning false and
    // then making |traverse|'s caller disambiguate that result from a real
    // error.
    void stop() { stopRequested = true; }

    // Request that the current edge's referent's outgoing edges not be
    // traversed. This must be called the first time that referent is reached.
    // Other edges *to* that referent will still be traversed.
    void abandonReferent() { abandonRequested = true; }

    // The context with which we were constructed.
    JSContext* cx;

    // A map associating each node N that we have reached with a
    // Handler::NodeData, for |handler|'s use. This is public, so that
    // |handler| can access it to see the traversal thus far.
    using NodeMap = js::HashMap<Node, typename Handler::NodeData, js::DefaultHasher<Node>,
                                js::SystemAllocPolicy>;
    NodeMap visited;

  private:
    // Our handler object.
    Handler& handler;

    // A queue template. Appending and popping the front are constant time.
    // Wasted space is never more than some recent actual population plus the
    // current population.
    template <typename T>
    class Queue {
        js::Vector<T, 0, js::SystemAllocPolicy> head, tail;
        size_t frontIndex;
      public:
        Queue() : head(), tail(), frontIndex(0) { }
        bool empty() { return frontIndex >= head.length(); }
        T& front() {
            MOZ_ASSERT(!empty());
            return head[frontIndex];
        }
        void popFront() {
            MOZ_ASSERT(!empty());
            frontIndex++;
            if (frontIndex >= head.length()) {
                head.clearAndFree();
                head.swap(tail);
                frontIndex = 0;
            }
        }
        bool append(const T& elt) {
            return frontIndex == 0 ? head.append(elt) : tail.append(elt);
        }
    };

    // A queue of nodes that we have reached, but whose outgoing edges we
    // have not yet traversed. Nodes reachable in fewer edges are enqueued
    // earlier.
    Queue<Node> pending;

    // True if our traverse function has been called.
    bool traversalBegun;

    // True if we've been asked to stop the traversal.
    bool stopRequested;

    // True if we've been asked to abandon the current edge's referent.
    bool abandonRequested;
};

} // namespace ubi
} // namespace JS

#endif // js_UbiNodeBreadthFirst_h

Coverage Report

Created: 2018-09-25 14:53

Line	Count	Source (jump to first uncovered line)
1		/* -- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 --
2		* vim: set ts=8 sts=4 et sw=4 tw=99:
3		* This Source Code Form is subject to the terms of the Mozilla Public
4		* License, v. 2.0. If a copy of the MPL was not distributed with this
5		* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7		#ifndef js_UbiNodeBreadthFirst_h
8		#define js_UbiNodeBreadthFirst_h
9
10		#include "js/UbiNode.h"
11		#include "js/Utility.h"
12		#include "js/Vector.h"
13
14		namespace JS {
15		namespace ubi {
16
17		// A breadth-first traversal template for graphs of ubi::Nodes.
18		//
19		// No GC may occur while an instance of this template is live.
20		//
21		// The provided Handler type should have two members:
22		//
23		// typename NodeData;
24		//
25		// The value type of \|BreadthFirst<Handler>::visited\|, the HashMap of
26		// ubi::Nodes that have been visited so far. Since the algorithm needs a
27		// hash table like this for its own use anyway, it is simple to let
28		// Handler store its own metadata about each node in the same table.
29		//
30		// For example, if you want to find a shortest path to each node from any
31		// traversal starting point, your \|NodeData\| type could record the first
32		// edge to reach each node, and the node from which it originates. Then,
33		// when the traversal is complete, you can walk backwards from any node
34		// to some starting point, and the path recorded will be a shortest path.
35		//
36		// This type must have a default constructor. If this type owns any other
37		// resources, move constructors and assignment operators are probably a
38		// good idea, too.
39		//
40		// bool operator() (BreadthFirst& traversal,
41		// Node origin, const Edge& edge,
42		// Handler::NodeData* referentData, bool first);
43		//
44		// The visitor function, called to report that we have traversed
45		// \|edge\| from \|origin\|. This is called once for each edge we traverse.
46		// As this is a breadth-first search, any prior calls to the visitor function
47		// were for origin nodes not further from the start nodes than \|origin\|.
48		//
49		// \|traversal\| is this traversal object, passed along for convenience.
50		//
51		// \|referentData\| is a pointer to the value of the entry in
52		// \|traversal.visited\| for \|edge.referent\|; the visitor function can
53		// store whatever metadata it likes about \|edge.referent\| there.
54		//
55		// \|first\| is true if this is the first time we have visited an edge
56		// leading to \|edge.referent\|. This could be stored in NodeData, but
57		// the algorithm knows whether it has just created the entry in
58		// \|traversal.visited\|, so it passes it along for convenience.
59		//
60		// The visitor function may call \|traversal.abandonReferent()\| if it
61		// doesn't want to traverse the outgoing edges of \|edge.referent\|. You can
62		// use this to limit the traversal to a given portion of the graph: it will
63		// never visit nodes reachable only through nodes that you have abandoned.
64		// Note that \|abandonReferent\| must be called the first time the given node
65		// is reached; that is, \|first\| must be true.
66		//
67		// The visitor function may call \|traversal.stop()\| if it doesn't want
68		// to visit any more nodes at all.
69		//
70		// The visitor function may consult \|traversal.visited\| for information
71		// about other nodes, but it should not add or remove entries.
72		//
73		// The visitor function should return true on success, or false if an
74		// error occurs. A false return value terminates the traversal
75		// immediately, and causes BreadthFirst<Handler>::traverse to return
76		// false.
77		template<typename Handler>
78		struct BreadthFirst {
79
80		// Construct a breadth-first traversal object that reports the nodes it
81		// reaches to \|handler\|. The traversal asserts that no GC happens in its
82		// runtime during its lifetime.
83		//
84		// We do nothing with noGC, other than require it to exist, with a lifetime
85		// that encloses our own.
86		BreadthFirst(JSContext* cx, Handler& handler, const JS::AutoRequireNoGC& noGC)
87		: wantNames(true), cx(cx), visited(), handler(handler), pending(),
88		traversalBegun(false), stopRequested(false), abandonRequested(false)
89	0	{ } Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::BreadthFirst(JSContext, JS::ubi::ShortestPaths::Handler&, JS::AutoRequireNoGC const&) Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::BreadthFirst(JSContext, JS::ubi::CensusHandler&, JS::AutoRequireNoGC const&) Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::BreadthFirst(JSContext, mozilla::devtools::HeapSnapshotHandler&, JS::AutoRequireNoGC const&) Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::BreadthFirst(JSContext, heaptools::FindPathHandler&, JS::AutoRequireNoGC const&) Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::BreadthFirst(JSContext*, js::Debugger::ObjectQuery&, JS::AutoRequireNoGC const&)
90
91		// Add \|node\| as a starting point for the traversal. You may add
92		// as many starting points as you like. Return false on OOM.
93	0	bool addStart(Node node) { return pending.append(node); } Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::addStart(JS::ubi::Node) Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::addStart(JS::ubi::Node) Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::addStart(JS::ubi::Node) Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::addStart(JS::ubi::Node) Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::addStart(JS::ubi::Node)
94
95		// Add \|node\| as a starting point for the traversal (see addStart) and also
96		// add it to the \|visited\| set. Return false on OOM.
97	0	bool addStartVisited(Node node) {
98	0	typename NodeMap::AddPtr ptr = visited.lookupForAdd(node);
99	0	if (!ptr && !visited.add(ptr, node, typename Handler::NodeData())) {
100	0	return false;
101	0	}
102	0	return addStart(node);
103	0	}
104
105		// True if the handler wants us to compute edge names; doing so can be
106		// expensive in time and memory. True by default.
107		bool wantNames;
108
109		// Traverse the graph in breadth-first order, starting at the given
110		// start nodes, applying \|handler::operator()\| for each edge traversed
111		// as described above.
112		//
113		// This should be called only once per instance of this class.
114		//
115		// Return false on OOM or error return from \|handler::operator()\|.
116		bool traverse()
117	0	{
118	0	MOZ_ASSERT(!traversalBegun);
119	0	traversalBegun = true;
120	0
121	0	// While there are pending nodes, visit them.
122	0	while (!pending.empty()) {
123	0	Node origin = pending.front();
124	0	pending.popFront();
125	0
126	0	// Get a range containing all origin's outgoing edges.
127	0	auto range = origin.edges(cx, wantNames);
128	0	if (!range) {
129	0	return false;
130	0	}
131	0
132	0	// Traverse each edge.
133	0	for (; !range->empty(); range->popFront()) {
134	0	MOZ_ASSERT(!stopRequested);
135	0
136	0	Edge& edge = range->front();
137	0	typename NodeMap::AddPtr a = visited.lookupForAdd(edge.referent);
138	0	bool first = !a;
139	0
140	0	if (first) {
141	0	// This is the first time we've reached \|edge.referent\|.
142	0	// Mark it as visited.
143	0	if (!visited.add(a, edge.referent, typename Handler::NodeData())) {
144	0	return false;
145	0	}
146	0	}
147	0
148	0	MOZ_ASSERT(a);
149	0
150	0	// Report this edge to the visitor function.
151	0	if (!handler(*this, origin, edge, &a->value(), first)) {
152	0	return false;
153	0	}
154	0
155	0	if (stopRequested) {
156	0	return true;
157	0	}
158	0
159	0	// Arrange to traverse this edge's referent's outgoing edges
160	0	// later --- unless \|handler\| asked us not to.
161	0	if (abandonRequested) {
162	0	// Skip the enqueue; reset flag for future iterations.
163	0	abandonRequested = false;
164	0	} else if (first) {
165	0	if (!pending.append(edge.referent)) {
166	0	return false;
167	0	}
168	0	}
169	0	}
170	0	}
171	0
172	0	return true;
173	0	} Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::traverse() Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::traverse() Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::traverse() Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::traverse() Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::traverse()
174
175		// Stop traversal, and return true from \|traverse\| without visiting any
176		// more nodes. Only \|handler::operator()\| should call this function; it
177		// may do so to stop the traversal early, without returning false and
178		// then making \|traverse\|'s caller disambiguate that result from a real
179		// error.
180	0	void stop() { stopRequested = true; } Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::stop() Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::stop()
181
182		// Request that the current edge's referent's outgoing edges not be
183		// traversed. This must be called the first time that referent is reached.
184		// Other edges to that referent will still be traversed.
185	0	void abandonReferent() { abandonRequested = true; } Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::abandonReferent() Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::abandonReferent() Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::abandonReferent()
186
187		// The context with which we were constructed.
188		JSContext* cx;
189
190		// A map associating each node N that we have reached with a
191		// Handler::NodeData, for \|handler\|'s use. This is public, so that
192		// \|handler\| can access it to see the traversal thus far.
193		using NodeMap = js::HashMap<Node, typename Handler::NodeData, js::DefaultHasher<Node>,
194		js::SystemAllocPolicy>;
195		NodeMap visited;
196
197		private:
198		// Our handler object.
199		Handler& handler;
200
201		// A queue template. Appending and popping the front are constant time.
202		// Wasted space is never more than some recent actual population plus the
203		// current population.
204		template <typename T>
205		class Queue {
206		js::Vector<T, 0, js::SystemAllocPolicy> head, tail;
207		size_t frontIndex;
208		public:
209	0	Queue() : head(), tail(), frontIndex(0) { } Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::Queue<JS::ubi::Node>::Queue() Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::Queue<JS::ubi::Node>::Queue() Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::Queue<JS::ubi::Node>::Queue() Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::Queue<JS::ubi::Node>::Queue() Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::Queue<JS::ubi::Node>::Queue()
210	0	bool empty() { return frontIndex >= head.length(); } Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::Queue<JS::ubi::Node>::empty() Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::Queue<JS::ubi::Node>::empty() Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::Queue<JS::ubi::Node>::empty() Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::Queue<JS::ubi::Node>::empty() Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::Queue<JS::ubi::Node>::empty()
211	0	T& front() {
212	0	MOZ_ASSERT(!empty());
213	0	return head[frontIndex];
214	0	} Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::Queue<JS::ubi::Node>::front() Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::Queue<JS::ubi::Node>::front() Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::Queue<JS::ubi::Node>::front() Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::Queue<JS::ubi::Node>::front() Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::Queue<JS::ubi::Node>::front()
215	0	void popFront() {
216	0	MOZ_ASSERT(!empty());
217	0	frontIndex++;
218	0	if (frontIndex >= head.length()) {
219	0	head.clearAndFree();
220	0	head.swap(tail);
221	0	frontIndex = 0;
222	0	}
223	0	} Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::Queue<JS::ubi::Node>::popFront() Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::Queue<JS::ubi::Node>::popFront() Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::Queue<JS::ubi::Node>::popFront() Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::Queue<JS::ubi::Node>::popFront() Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::Queue<JS::ubi::Node>::popFront()
224	0	bool append(const T& elt) {
225	0	return frontIndex == 0 ? head.append(elt) : tail.append(elt);
226	0	} Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::ShortestPaths::Handler>::Queue<JS::ubi::Node>::append(JS::ubi::Node const&) Unexecuted instantiation: JS::ubi::BreadthFirst<JS::ubi::CensusHandler>::Queue<JS::ubi::Node>::append(JS::ubi::Node const&) Unexecuted instantiation: JS::ubi::BreadthFirst<mozilla::devtools::HeapSnapshotHandler>::Queue<JS::ubi::Node>::append(JS::ubi::Node const&) Unexecuted instantiation: JS::ubi::BreadthFirst<heaptools::FindPathHandler>::Queue<JS::ubi::Node>::append(JS::ubi::Node const&) Unexecuted instantiation: JS::ubi::BreadthFirst<js::Debugger::ObjectQuery>::Queue<JS::ubi::Node>::append(JS::ubi::Node const&)
227		};
228
229		// A queue of nodes that we have reached, but whose outgoing edges we
230		// have not yet traversed. Nodes reachable in fewer edges are enqueued
231		// earlier.
232		Queue<Node> pending;
233
234		// True if our traverse function has been called.
235		bool traversalBegun;
236
237		// True if we've been asked to stop the traversal.
238		bool stopRequested;
239
240		// True if we've been asked to abandon the current edge's referent.
241		bool abandonRequested;
242		};
243
244		} // namespace ubi
245		} // namespace JS
246
247		#endif // js_UbiNodeBreadthFirst_h