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