path: root/js/public/UbiNodeShortestPaths.h

/* -*- 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