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 (409f3966645a)

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
/* -*- 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 gc_FindSCCs_h
#define gc_FindSCCs_h

#include "mozilla/Move.h"

#include "jsfriendapi.h"
#include "jsutil.h"

namespace js {
namespace gc {

template<class Node>
struct GraphNodeBase
{
    Node*          gcNextGraphNode;
    Node*          gcNextGraphComponent;
    unsigned       gcDiscoveryTime;
    unsigned       gcLowLink;

    GraphNodeBase()
      : gcNextGraphNode(nullptr),
        gcNextGraphComponent(nullptr),
        gcDiscoveryTime(0),
        gcLowLink(0) {}

    ~GraphNodeBase() {}

    Node* nextNodeInGroup() const {
        if (gcNextGraphNode && gcNextGraphNode->gcNextGraphComponent == gcNextGraphComponent)
            return gcNextGraphNode;
        return nullptr;
    }

    Node* nextGroup() const {
        return gcNextGraphComponent;
    }
};

/*
 * Find the strongly connected components of a graph using Tarjan's algorithm,
 * and return them in topological order.
 *
 * Nodes derive from GraphNodeBase and implement findGraphEdges, which calls
 * finder.addEdgeTo to describe the outgoing edges from that node:
 *
 * struct MyComponentFinder;
 *
 * struct MyGraphNode : public GraphNodeBase
 * {
 *     void findOutgoingEdges(MyComponentFinder& finder)
 *     {
 *         for edge in my_outgoing_edges:
 *             if is_relevant(edge):
 *                 finder.addEdgeTo(edge.destination)
 *     }
 * }
 *
 * struct MyComponentFinder : public ComponentFinder<MyGraphNode, MyComponentFinder>
 * {
 *     ...
 * };
 *
 * MyComponentFinder finder;
 * finder.addNode(v);
 */

template <typename Node, typename Derived>
class ComponentFinder
{
  public:
    explicit ComponentFinder(uintptr_t sl)
      : clock(1),
        stack(nullptr),
        firstComponent(nullptr),
        cur(nullptr),
        stackLimit(sl),
        stackFull(false)
    {}

    ~ComponentFinder() {
        MOZ_ASSERT(!stack);
        MOZ_ASSERT(!firstComponent);
    }

    /* Forces all nodes to be added to a single component. */
    void useOneComponent() { stackFull = true; }

    void addNode(Node* v) {
        if (v->gcDiscoveryTime == Undefined) {
            MOZ_ASSERT(v->gcLowLink == Undefined);
            processNode(v);
        }
    }

    Node* getResultsList() {
        if (stackFull) {
            /*
             * All nodes after the stack overflow are in |stack|. Put them all in
             * one big component of their own.
             */
            Node* firstGoodComponent = firstComponent;
            for (Node* v = stack; v; v = stack) {
                stack = v->gcNextGraphNode;
                v->gcNextGraphComponent = firstGoodComponent;
                v->gcNextGraphNode = firstComponent;
                firstComponent = v;
            }
            stackFull = false;
        }

        MOZ_ASSERT(!stack);

        Node* result = firstComponent;
        firstComponent = nullptr;

        for (Node* v = result; v; v = v->gcNextGraphNode) {
            v->gcDiscoveryTime = Undefined;
            v->gcLowLink = Undefined;
        }

        return result;
    }

    static void mergeGroups(Node* first) {
        for (Node* v = first; v; v = v->gcNextGraphNode)
            v->gcNextGraphComponent = nullptr;
    }

  public:
    /* Call from implementation of GraphNodeBase::findOutgoingEdges(). */
    void addEdgeTo(Node* w) {
        if (w->gcDiscoveryTime == Undefined) {
            processNode(w);
            cur->gcLowLink = Min(cur->gcLowLink, w->gcLowLink);
        } else if (w->gcDiscoveryTime != Finished) {
            cur->gcLowLink = Min(cur->gcLowLink, w->gcDiscoveryTime);
        }
    }

  private:
    /* Constant used to indicate an unprocessed vertex. */
    static const unsigned Undefined = 0;

    /* Constant used to indicate an processed vertex that is no longer on the stack. */
    static const unsigned Finished = (unsigned)-1;

    void processNode(Node* v) {
        v->gcDiscoveryTime = clock;
        v->gcLowLink = clock;
        ++clock;

        v->gcNextGraphNode = stack;
        stack = v;

        int stackDummy;
        if (stackFull || !JS_CHECK_STACK_SIZE(stackLimit, &stackDummy)) {
            stackFull = true;
            return;
        }

        Node* old = cur;
        cur = v;
        cur->findOutgoingEdges(*static_cast<Derived*>(this));
        cur = old;

        if (stackFull)
            return;

        if (v->gcLowLink == v->gcDiscoveryTime) {
            Node* nextComponent = firstComponent;
            Node* w;
            do {
                MOZ_ASSERT(stack);
                w = stack;
                stack = w->gcNextGraphNode;

                /*
                 * Record that the element is no longer on the stack by setting the
                 * discovery time to a special value that's not Undefined.
                 */
                w->gcDiscoveryTime = Finished;

                /* Figure out which group we're in. */
                w->gcNextGraphComponent = nextComponent;

                /*
                 * Prepend the component to the beginning of the output list to
                 * reverse the list and achieve the desired order.
                 */
                w->gcNextGraphNode = firstComponent;
                firstComponent = w;
            } while (w != v);
        }
    }

  private:
    unsigned       clock;
    Node*          stack;
    Node*          firstComponent;
    Node*          cur;
    uintptr_t      stackLimit;
    bool           stackFull;
};

} /* namespace gc */
} /* namespace js */

#endif /* gc_FindSCCs_h */