/* BSD 2-Clause License - see OPAL/LICENSE for details. */
package org.opalj
package graphs

import org.opalj.collection.immutable.IntArraySet
import org.opalj.collection.immutable.IntTrieSet
import org.opalj.collection.immutable.IntRefPair
import org.opalj.collection.mutable.FixedSizeBitSet
import org.opalj.collection.mutable.IntArrayStack

import scala.collection.immutable.ArraySeq

/**
 * Representation of the dominance frontiers.
 *
 * @author Michael Eichberg
 */
final class DominanceFrontiers private (
        private val dfs: Array[IntArraySet] // IMPROVE Consider using an IntTrieSet (if it doesn't work, document it!)
) extends ControlDependencies {

    def apply(n: Int): IntArraySet = df(n)

    def maxNode: Int = dfs.length - 1

    /**
     * Returns the nodes in the dominance frontier of the given node.
     */
    def df(n: Int): IntArraySet = {
        val df = dfs(n)
        if (df eq null)
            IntArraySet.empty
        else
            df
    }

    def transitiveDF(n: Int): IntTrieSet = {
        var transitiveDF = IntTrieSet.empty ++ this.df(n).iterator
        var nodesToVisit = transitiveDF - n
        while (nodesToVisit.nonEmpty) {
            val IntRefPair(nextN, newNodesToVisit) = nodesToVisit.headAndTail
            nodesToVisit = newNodesToVisit
            val nextDF = this.df(nextN)
            transitiveDF ++= nextDF.iterator
            nodesToVisit ++= nextDF.iterator.filter(_ != nextN)
        }
        transitiveDF
    }

    def dominanceFrontiers: IndexedSeq[IntArraySet] = ArraySeq.unsafeWrapArray(dfs)

    def xIsDirectlyControlDependentOn(x: Int): IntArraySet = df(x)

    def xIsControlDependentOn(x: Int)(f: Int => Unit): Unit = {
        val maxNodeId = maxNode

        // IMPROVE Evaluate if a typed chain or an Int(Array|Trie)Set is more efficient...
        val seen = FixedSizeBitSet.create(maxNodeId)
        val worklist = new IntArrayStack(Math.min(10, maxNodeId / 3))
        worklist.push(x)

        do {
            val x = worklist.pop()

            df(x) foreach { y =>
                if (!seen.contains(y)) {
                    seen += y
                    worklist.push(y)
                    f(y)
                }
            }
        } while (worklist.nonEmpty)
    }

    //
    //
    // DEBUGGING RELATED FUNCTIONALITY
    //
    //

    /**
     * Creates a dot graph which depicts the dominance frontiers.
     *
     * @param   isNodeValid A function that returns `true` if the given int value
     *          identifies a valid node. If the underlying graph is not a sparse
     *          graph; i.e., if every index in the range [0...maxNode] identifies
     *          a valid node, then the default function, which always returns `true`,
     *          can be used.
     */
    def toDot(isNodeValid: Int => Boolean = _ => true): String = {
        val g = Graph.empty[Int]
        dfs.zipWithIndex.foreach { e =>
            val (df, s /*index*/ ) = e
            if (isNodeValid(s)) {
                if (df == null) {
                    g addVertice s
                } else {
                    df.foreach { t => g.addEdge(s, t) }
                }
            }
        }
        g.toDot(rankdir = "BT", ranksep = "0.3")
    }
}

/**
 * Factory to compute [[DominanceFrontiers]].
 *
 * @author Michael Eichberg
 */
object DominanceFrontiers {

    /**
     * Computes the dominance frontiers for each node of a graph G using the (post) dominator tree.
     *
     * @example
     * {{{
     * // A graph taken from the paper:
     * // Efficiently Computing Static Single Assignment Form and the Control Dependence Graph
     * val g = org.opalj.graphs.Graph.empty[Int] += (0 -> 1) += (1 -> 2) += (2 -> 3) += (2 -> 7) += (3 -> 4) += (3->5) += (5->6) += (4->6) += (6->8) += (7->8)  += (8->9) += (9->10) += (9->11) += (10->11) += (11->9) += (11 -> 12) += (12 -> 13) += (12 ->2) += (0 -> 13)
     * val foreachSuccessor = (n: Int) => g.successors.getOrElse(n, List.empty).foreach _
     * val foreachPredecessor = (n: Int) => g.predecessors.getOrElse(n, List.empty).foreach _
     * val dt = org.opalj.graphs.DominatorTree(0, false, foreachSuccessor, foreachPredecessor, 13)
     * val isValidNode = (n : Int) => n>= 0 && n <= 13
     * org.opalj.io.writeAndOpen(dt.toDot(),"g",".dt.gv")
     * val df = org.opalj.graphs.DominanceFrontiers(dt,isValidNode)
     * org.opalj.io.writeAndOpen(df.toDot(),"g",".df.gv")
     *
     *
     * // A degenerated graph which consists of a single node that has a self-reference.
     * val g = org.opalj.graphs.Graph.empty[Int] += (0 -> 0)
     * val foreachSuccessor = (n: Int) => g.successors.getOrElse(n, List.empty).foreach _
     * val foreachPredecessor = (n: Int) => g.predecessors.getOrElse(n, List.empty).foreach _
     * val dtf = org.opalj.graphs.DominatorTreeFactory(0, true, foreachSuccessor, foreachPredecessor, 0)
     * val isValidNode = (n : Int) => n == 0
     * org.opalj.io.writeAndOpen(dtf.dt.toDot(),"g",".dt.gv")
     * val df = org.opalj.graphs.DominanceFrontiers(dtf,isValidNode)
     * org.opalj.io.writeAndOpen(df.toDot(),"g",".df.gv")
     * }}}
     *
     * @param   dt The dominator tree of the specified (flow) graph. We provide basic support
     *          for augmented post dominator trees: [[PostDominatorTree]]; we in particular
     *          handle common cases related to additional exit nodes as created by the implented(!)
     *          post dominator tree computation algorithm.
     *          However, the following case:
     *          {{{
     *          while (true) {
     *               if (i < 0) {
     *                   i += 1000;
     *                   // Exit Piont 1
     *               } else {
     *                   i -= 100;
     *                   // Exit Point 2
     *               }
     *          }
     *          }}}
     *          is not yet supported; it would require a significant transformation of the
     *          computed PDT, which we currently do not perform.
     *          Basically, in the PDT we would need to make both bodies dependent on the
     *          artifical exit node of the loop to ensure that both bodies are control-dependent
     *          on the "if" node.
     *
     * @param   isValidNode A function that returns `true` if the given id represents a node of the
     *          underlying graph. If the underlying graph contains a single, new artificial start
     *          node then this node may or may not be reported as a valid node; this is not relevant
     *          for this algorithm.
     */
    def apply(dt: AbstractDominatorTree, isValidNode: Int => Boolean): DominanceFrontiers = {
        val startNode: Int = dt.startNode
        val foreachSuccessorOf = dt.foreachSuccessorOf
        val max = dt.maxNode + 1

        val potentialChildrenCount = 3
        val children = new Array[IntArrayStack](max)
        var i = 0
        while (i < max) {
            if (isValidNode(i) && i != startNode) {
                val d = dt.idom(i)
                val dChildren = children(d)
                if (dChildren eq null) {
                    val child = new IntArrayStack(potentialChildrenCount)
                    child.push(i)
                    children(d) = child
                } else {
                    dChildren.push(i)
                }
            }
            i += 1
        }

        var dfs /* dominanceFrontiers */ = new Array[IntArraySet](max)

        @inline def dfLocal(n: Int): IntArraySet = {
            var s = IntArraySet.empty
            try {
                foreachSuccessorOf(n) { y => if (dt.dom(y) != n) s = s + y }
            } catch {
                case t: Throwable =>
                    throw new Throwable(s"failed iterating over successors of node $n", t)
            }
            s
        }

        val inDFSOrder = new IntArrayStack(Math.max(max - 2, 2))
        var nodes: List[Int] = List(startNode)
        while (nodes.nonEmpty) {
            val n = nodes.head
            nodes = nodes.tail
            val nChildren = children(n)
            if (nChildren ne null) {
                inDFSOrder.push(n)
                nChildren.foreach { nodes ::= _ }
            } else {
                // we immediately compute the dfs_local information
                dfs(n) = dfLocal(n)
            }
        }

        inDFSOrder foreach { n =>
            val s = children(n).foldLeft(dfLocal(n)) { (s, c) =>
                dfs(c).foldLeft(s) { (s, w) =>
                    if (!dt.strictlyDominates(n, w)) {
                        s + w
                    } else
                        s
                }
            }
            dfs(n) = s
        }

        if (dt.isAugmented) {
            dt match {
                case pdt: PostDominatorTree =>
                    // let's filter the extra exit points; recall that we are
                    // non-termination _in_sensitive
                    dfs = dfs.map { e =>
                        if (e ne null)
                            e -- pdt.additionalExitNodes
                        else
                            e
                    }

                case _: DominatorTree =>
                //nothing special to do

                case dt =>
                    org.opalj.log.OPALLogger.warn(
                        "computing dominance frontier",
                        s"the augmentation of $dt is not understood and ignored"
                    )(org.opalj.log.GlobalLogContext)
            }
        }
        new DominanceFrontiers(dfs)
    }

}