<commit_before>package eu.stratosphere.emma.macros.program.controlflow

import scala.collection.Set
import scala.collection.mutable.ListBuffer

private[emma] trait ControlFlowCompiler extends ControlFlowModel {
  import universe._

  def compileDriver[T: c.WeakTypeTag](cfGraph: CFGraph): ListBuffer[Tree] = {
    // build driver tree startin from the (per construction unique) head block

    cfGraph.nodes.find(_.inDegree == 0) match {
      case Some(head) =>
        buildDriverTree(head, cfGraph)
      case None =>
        c.error(c.enclosingPosition, "Cannot determine head of CF graph")
        ListBuffer.empty[Tree]
    }
  }

  def compileBlock(block: CFBlock) = {
    val defName = block.defName
    val defType = block.defType
    val defBody = if (block.stats.last.tpe != NoType) q"{ ..${block.stats.toList} }" else q"{ ..${block.stats.toList}; Unit }"

    q"def $defName: $defType = $defBody"
  }

  private def buildDriverTree(head: CFGraph#NodeT, graph: CFGraph): ListBuffer[Tree] = {
    // outer object for the head
    val headBlock = head.value.asInstanceOf[CFBlock]
    // initialize result buffer
    val stats = ListBuffer[Tree]()

    // recursive descent based on the block type
    headBlock.kind match {

      case Linear =>
        stats ++= headBlock.stats
        stats ++= (findByLabel(head, label = true) match {
          case Some(next) => buildDriverTree(next, graph - head)
          case _ => ListBuffer.empty[Tree]
        })

      case Cond =>
        // get the `then` and `else` branch head nodes
        val optThenHead = findByLabel(head, label = true)
        val optElseHead = findByLabel(head, label = false)

        // get the `then` and `else` branch descendants
        val thenBlocks = for (x <- optThenHead match {
          case Some(thenHead) => thenHead.innerNodeTraverser.toSet
          case _ => Set.empty[CFGraph#NodeT]
        }) yield x.value.asInstanceOf[CFBlock]
        val elseBlocks = for (x <- optElseHead match {
          case Some(elseHead) => elseHead.innerNodeTraverser.toSet
          case _ => Set.empty[CFGraph#NodeT]
        }) yield x.value.asInstanceOf[CFBlock]
        // compute the intersection between the two descendant sets
        val commonBlocks = thenBlocks intersect elseBlocks

        // restrict `then`, `else` and `next` subgraphs
        val thenGraph = graph.clone()
        for (x <- thenGraph.nodes; y <- Some(x.value.asInstanceOf[CFBlock]); if !thenBlocks.contains(y) || commonBlocks.contains(y)) thenGraph -= x
        val elseGraph = graph.clone()
        for (x <- elseGraph.nodes; y <- Some(x.value.asInstanceOf[CFBlock]); if !elseBlocks.contains(y) || commonBlocks.contains(y)) elseGraph -= x
        val nextGraph = graph.clone()
        for (x <- nextGraph.nodes; y <- Some(x.value.asInstanceOf[CFBlock]); if !commonBlocks.contains(y)) nextGraph -= x

        // build `then` and `else` driver subtrees
        val thenTree = optThenHead match {
          case Some(thenHead) => buildDriverTree(thenGraph.get(thenHead.value.asInstanceOf[CFBlock]), thenGraph)
          case _ => ListBuffer[Tree]()
        }
        val elseTree = optElseHead match {
          case Some(elseHead) => buildDriverTree(elseGraph.get(elseHead.value.asInstanceOf[CFBlock]), elseGraph)
          case _ => ListBuffer[Tree]()
        }

        // FIXME: handle conditionals without else branch
        // build if (cond) thenp else elsep driver dubtree
        stats += q"if ({ ..${headBlock.stats.toList} }) { ..${thenTree.toList} } else { ..${elseTree.toList} }"

        // build `next` driver subtrees
        for (head <- nextGraph.nodes if head.inDegree == 0)
          stats ++= buildDriverTree(head, nextGraph)

      case WhileBegin(i) =>
        // get the head and the tail of the `body` branch
        val optBodyHead = findByLabel(head, label = true)
        val optBodyTail = graph.nodes find (_.value.asInstanceOf[CFBlock].kind match {
          case WhileEnd(j) if i == j => true
          case _ => false
        })
        // get the head of the `next` branch
        val optNextHead = findByLabel(head, label = false)

        // get the blocks in the `body` branch
        val bodyBlocks = {
          // compute all inner nodes between the head and the tail of the body (inclusive)
          val nodes = for (h <- optBodyHead;
                           t <- optBodyTail;
                           x <- Some(h.asInstanceOf[CFGraph#NodeT].innerNodeTraverser.toSet);
                           y <- Some(t.asInstanceOf[CFGraph#NodeT].innerNodeTraverser.toSet)) yield (x diff y) union Set(t.asInstanceOf[CFGraph#NodeT])
          // transform to outer nodes
          for (n <- nodes.get) yield n.value.asInstanceOf[CFBlock]
        }
        // get the blocks in the `next` branch
        val nextBlocks = {
          // compute all inner for the `next` subgraph
          val nodes = for (n <- optNextHead; x <- Some(n.innerNodeTraverser.toSet)) yield x
          // transform to outer nodes
          for (n <- nodes.get) yield n.value.asInstanceOf[CFBlock]
        }

        // restrict `body` and `next` subgraphs
        val bodyGraph = graph.clone()
        for (n <- bodyGraph.nodes; y <- Some(n.value.asInstanceOf[CFBlock]); if !bodyBlocks.contains(y)) bodyGraph -= n
        val nextGraph = graph.clone()
        for (n <- nextGraph.nodes; y <- Some(n.value.asInstanceOf[CFBlock]); if !nextBlocks.contains(y)) nextGraph -= n

        // build `body` and `next` driver subtrees
        val bodyTree = optBodyHead match {
          case Some(bodyHead) => buildDriverTree(bodyGraph.get(bodyHead.value.asInstanceOf[CFBlock]), bodyGraph)
          case _ => ListBuffer[Tree]()
        }
        val nextTree = optNextHead match {
          case Some(nextHead) => buildDriverTree(nextGraph.get(nextHead.value.asInstanceOf[CFBlock]), nextGraph)
          case _ => ListBuffer[Tree]()
        }

        // FIXME: changes semantics if condition test was pulled to the end
        stats += q"while ({ ..${headBlock.stats.toList} }) { ..${bodyTree.toList} }"
        stats ++= nextTree

      case WhileEnd(i) =>
        stats ++= headBlock.stats

      case DoWhileBegin(i) =>
        c.error(c.enclosingPosition, "Unsupported CFBLock type: DoWhileBegin")

      case DoWhileEnd(i) =>
        stats ++= headBlock.stats

      case _ =>
        c.error(c.enclosingPosition, "Unknown CFBLock type")
    }

    // the compiled sequence of statements
    stats
  }
}<commit_msg>[MACROS] Refactored `ControlFlowCompiler`<commit_after>package eu.stratosphere.emma.macros.program.controlflow

import eu.stratosphere.emma.macros.BlackBoxUtil
import scala.collection.Set
import scala.collection.mutable.ListBuffer

private[emma] trait ControlFlowCompiler extends ControlFlowModel with BlackBoxUtil {
  import universe._

  def compileDriver[T: c.WeakTypeTag](cfGraph: CFGraph): ListBuffer[Tree] = {
    // Build driver tree starting from the (per construction unique) head block
    cfGraph.nodes find { _.inDegree == 0 } match {
      case Some(head) => buildDriverTree(head, cfGraph)
      case None       => c.abort(c.enclosingPosition, "Cannot determine head of CF graph")
    }
  }

  def compileBlock(block: CFBlock) = {
    val defName = block.defName
    val defType = block.defType
    val stats   = block.stats
    val defBody =
      if (stats.last.tpe != NoType) q"{ ..$stats }"
      else q"{ ..$stats; () }"

    q"def $defName: $defType = $defBody"
  }

  private def buildDriverTree(head: CFGraph#NodeT, graph: CFGraph): ListBuffer[Tree] = {
    // Outer object for the head
    val headBlock = head.value.as[CFBlock]
    // Initialize result buffer
    val stats = ListBuffer.empty[Tree]

    // Recursive descent based on the block type
    headBlock.kind match {

      case Linear =>
        stats ++= headBlock.stats
        stats ++= (findByLabel(head, label = true) match {
          case Some(next) => buildDriverTree(next, graph - head)
          case None       => ListBuffer.empty[Tree]
        })

      case Cond =>
        // Get the `then` and `else` branch head nodes
        val optThenHead = findByLabel(head, label = true)
        val optElseHead = findByLabel(head, label = false)

        // Get the `then` and `else` branch descendants

        val thenBlocks =
          for (node <- optThenHead map { _.innerNodeTraverser.toSet } getOrElse Set.empty)
            yield node.value.as[CFBlock]

        val elseBlocks =
          for (node <- optElseHead map { _.innerNodeTraverser.toSet } getOrElse Set.empty)
            yield node.value.as[CFBlock]

        // Compute the intersection between the two descendant sets
        val commonBlocks = thenBlocks & elseBlocks

        // Restrict `then`, `else` and `next` sub-graphs

        val thenGraph = graph.clone()

        for {
          node <- thenGraph.nodes
          block = node.value.as[CFBlock]
          if !thenBlocks.contains(block) || commonBlocks.contains(block)
        } thenGraph -= node

        val elseGraph = graph.clone()

        for {
          node <- elseGraph.nodes
          block = node.value.as[CFBlock]
          if !elseBlocks.contains(block) || commonBlocks.contains(block)
        } elseGraph -= node

        val nextGraph = graph.clone()

        for {
          node <- nextGraph.nodes
          block = node.value.as[CFBlock]
          if !commonBlocks.contains(block)
        } nextGraph -= node

        // Build `then` and `else` driver subtrees

        val thenTree = optThenHead map { head =>
          buildDriverTree(thenGraph get head.value.as[CFBlock], thenGraph)
        } getOrElse ListBuffer.empty

        val elseTree = optElseHead map { head =>
          buildDriverTree(elseGraph get head.value.as[CFBlock], elseGraph)
        } getOrElse ListBuffer.empty

        // FIXME: Handle conditionals without else branch
        // Build if (cond) thn else els driver subtree
        stats += q"if ({ ..${headBlock.stats} }) { ..$thenTree } else { ..$elseTree }"

        // Build `next` driver subtrees
        for (head <- nextGraph.nodes if head.inDegree == 0)
          stats ++= buildDriverTree(head, nextGraph)

      case WhileBegin(i) =>
        // Get the head and the tail of the `body` branch
        val optBodyHead = findByLabel(head, label = true)
        val optBodyTail = graph.nodes find {
          _.value.as[CFBlock].kind match {
            case WhileEnd(j) => i == j
            case _ => false
          }
        }

        // Get the head of the `next` branch
        val optNextHead = findByLabel(head, label = false)

        // Get the blocks in the `body` branch
        val bodyBlocks = (for {
          head <- optBodyHead.toSeq
          tail <- optBodyTail.toSeq
          xs = head.as[CFGraph#NodeT].innerNodeTraverser.toSet
          ys = tail.as[CFGraph#NodeT].innerNodeTraverser.toSet
          node <- (xs diff ys) + tail.as[CFGraph#NodeT]
        } yield node.value.as[CFBlock]).toSet

        // Get the blocks in the `next` branch
        val nextBlocks = {
          // Compute all inner for the `next` sub-graph
          val nodes = for (node <- optNextHead) yield node.innerNodeTraverser.toSet
          // Transform to outer nodes
          for (node <- nodes.get) yield node.value.as[CFBlock]
        }

        // Restrict `body` and `next` sub-graphs

        val bodyGraph = graph.clone()

        for {
          node <- bodyGraph.nodes
          block = node.value.as[CFBlock]
          if !bodyBlocks.contains(block)
        } bodyGraph -= node

        val nextGraph = graph.clone()

        for {
          node <- nextGraph.nodes
          block = node.value.as[CFBlock]
          if !nextBlocks.contains(block)
        } nextGraph -= node

        // Build `body` and `next` driver subtrees

        val bodyTree = optBodyHead map { head =>
          buildDriverTree(bodyGraph get head.value.as[CFBlock], bodyGraph)
        } getOrElse ListBuffer.empty

        val nextTree = optNextHead map { head =>
          buildDriverTree(nextGraph get head.value.as[CFBlock], nextGraph)
        } getOrElse ListBuffer.empty

        // FIXME: Changes semantics if condition test was pulled to the end
        stats += q"while ({ ..${headBlock.stats} }) { ..$bodyTree }"
        stats ++= nextTree

      case WhileEnd(_) =>
        stats ++= headBlock.stats

      case DoWhileBegin(_) =>
        c.abort(c.enclosingPosition, "Unsupported CFBLock type: DoWhileBegin")

      case DoWhileEnd(_) =>
        stats ++= headBlock.stats

      case _ =>
        c.abort(c.enclosingPosition, "Unknown CFBLock type")
    }

    // The compiled sequence of statements
    stats
  }
}
{'fraction_non_alphanumeric': 0.1107162599699913, 'fraction_numerical': 0.0003158809128958383, 'mean_word_length': 2.305664317410598, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 45, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6966612', 'n_tokens_mistral': 3777, 'n_tokens_neox': 3635, 'n_words': 1001}