js/public/UbiNodeBreadthFirst.h
author Gregory Szorc <gps@mozilla.com>
Wed, 14 Jun 2017 16:52:55 -0700
changeset 364238 398d9d49677547b1b9f106370858c925de8c1511
parent 306451 6a92c25165546ad34e2ffa1f5d63c1c13fcca2d3
child 371292 000f28217a30b8cf649573ad2f52a03a8b426ef7
permissions -rw-r--r--
Bug 1371465 - Move MSVS_VERSION to moz.configure and properly define for vs2017; r=glandium Before, MSVS was set in old-configure and could only be unset or "2015." We move the definition of the variable to moz.configure and support defining its value as "2017" when VS2017 is being used. As part of this, I discovered that GYP barfs with a "2017" value. This is likely a limitation of the legacy version of GYP we have vendored. Rather than go down the rabbit hole of upgrading GYP, I added code to convert the value to "2015." This preserves existing behavior and unblocks us from setting MSVS_VERSION properly. A warning is emitted to remind us to remove this hack once GYP is upgraded. After this commit, we now generate native VS2017 solutions and projects when building with VS2017. MozReview-Commit-ID: BvNJX3F8qCn

/* -*- 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::AutoCheckCannotGC& noGC)
      : wantNames(true), cx(cx), visited(), handler(handler), pending(),
        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.
        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