DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (4a108e94d3e2)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243
/* -*- 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_UbiNodeTraverse_h
#define js_UbiNodeTraverse_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 object reports OOM on |cx|, and
    // asserts that no GC happens in |cx|'s 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::AutoCheckCannotGC& noGC)
      : wantNames(true), cx(cx), visited(cx), handler(handler), pending(cx),
        traversalBegun(false), stopRequested(false), abandonRequested(false)
    { }

    // Initialize this traversal object. Return false on OOM.
    bool init() { return visited.init(); }

    // 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, until we've found a path to the target.
        while (!pending.empty()) {
            Node origin = pending.front();
            pending.popFront();

            // Get a range containing all origin's outgoing edges.
            js::ScopedJSDeletePtr<EdgeRange> range(origin.edges(cx, wantNames));
            if (!range)
                return false;

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

                const 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.
    typedef js::HashMap<Node, typename Handler::NodeData> NodeMap;
    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> head, tail;
        size_t frontIndex;
      public:
        explicit Queue(JSContext* cx) : head(cx), tail(cx), 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_UbiNodeTraverse.h