Repository: joernio/joern
Pull request #700 (2021-11-09 13:46:28)

`reachableByDetailed` replaces `reachableByTable` (minus the race)
Introduces `reachableByDetailed` as a replacement for `reachableByTable`, which was introduced a few weeks back for experimental purposes, but unfortunately, contained a race condition. `reachableByDetailed` returns the sequence of `ReachableByResult`s, which now include the table.


Patch:
diff --git a/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/language/ExtendedCfgNode.scala b/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/language/ExtendedCfgNode.scala
index cc1472bb4..5b82b5929 100644
--- a/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/language/ExtendedCfgNode.scala
+++ b/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/language/ExtendedCfgNode.scala
@@ -28,12 +28,12 @@ class ExtendedCfgNode(val traversal: Traversal[CfgNode]) extends AnyVal {
 
   def reachableBy[NodeType <: CfgNode](sourceTravs: Traversal[NodeType]*)(
       implicit context: EngineContext): Traversal[NodeType] = {
-    val reachedSources = reachableByInternal(sourceTravs)._1.map(_.source)
+    val reachedSources = reachableByInternal(sourceTravs).map(_.source)
     Traversal.from(reachedSources).cast[NodeType]
   }
 
   def reachableByFlows[A <: CfgNode](sourceTravs: Traversal[A]*)(implicit context: EngineContext): Traversal[Path] = {
-    val paths = reachableByInternal(sourceTravs)._1
+    val paths = reachableByInternal(sourceTravs)
       .map { result =>
         // We can get back results that start in nodes that are invisible
         // according to the semantic, e.g., arguments that are only used
@@ -52,9 +52,9 @@ class ExtendedCfgNode(val traversal: Traversal[CfgNode]) extends AnyVal {
     paths.to(Traversal)
   }
 
-  def reachableByTable[NodeType <: CfgNode](sourceTravs: Traversal[NodeType]*)(
-      implicit context: EngineContext): ResultTable = {
-    reachableByInternal(sourceTravs)._2
+  def reachableByDetailed[NodeType <: CfgNode](sourceTravs: Traversal[NodeType]*)(
+      implicit context: EngineContext): List[ReachableByResult] = {
+    reachableByInternal(sourceTravs)
   }
 
   private def removeConsecutiveDuplicates[T](l: Vector[T]): List[T] = {
@@ -62,7 +62,7 @@ class ExtendedCfgNode(val traversal: Traversal[CfgNode]) extends AnyVal {
   }
 
   private def reachableByInternal[NodeType <: CfgNode](sourceTravs: Seq[Traversal[NodeType]])(
-      implicit context: EngineContext): (List[ReachableByResult], ResultTable) = {
+      implicit context: EngineContext): List[ReachableByResult] = {
     val sources: List[CfgNode] =
       sourceTravs
         .flatMap(_.toList)
diff --git a/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/queryengine/Engine.scala b/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/queryengine/Engine.scala
index 17451c6c9..da96db306 100644
--- a/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/queryengine/Engine.scala
+++ b/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/queryengine/Engine.scala
@@ -37,7 +37,7 @@ class Engine(context: EngineContext) {
     * Returns the list of results along with the ResultTable, a cache of known
     * paths created during the analysis.
     * */
-  def backwards(sinks: List[CfgNode], sources: List[CfgNode]): (List[ReachableByResult], ResultTable) = {
+  def backwards(sinks: List[CfgNode], sources: List[CfgNode]): List[ReachableByResult] = {
     if (sources.isEmpty) {
       logger.warn("Attempting to determine flows from empty list of sources.")
     }
@@ -46,10 +46,7 @@ class Engine(context: EngineContext) {
     }
     val sourcesSet = sources.toSet
     val tasks = sinks.map(sink => ReachableByTask(sink, sourcesSet, new ResultTable))
-    val results = solveTasks(tasks, sourcesSet)
-    // TODO: assemble result table from tables of all tasks
-    // and return it.
-    (results, new ResultTable)
+    solveTasks(tasks, sourcesSet)
   }
 
   private def solveTasks(tasks: List[ReachableByTask], sources: Set[CfgNode]): List[ReachableByResult] = {
@@ -327,9 +324,9 @@ private class ReachableByCallable(task: ReachableByTask, context: EngineContext)
 
     val resultsForCurNode = {
       val endStates = if (sources.contains(curNode.asInstanceOf[NodeType])) {
-        List(ReachableByResult(path))
+        List(ReachableByResult(path, table))
       } else if ((task.callDepth != context.config.maxCallDepth) && curNode.isInstanceOf[MethodParameterIn]) {
-        List(ReachableByResult(path, partial = true))
+        List(ReachableByResult(path, table, partial = true))
       } else {
         List()
       }
@@ -340,7 +337,7 @@ private class ReachableByCallable(task: ReachableByTask, context: EngineContext)
                 .to(Traversal)
                 .internal
                 .nonEmpty && semanticsForCall(call).isEmpty) {
-            List(ReachableByResult(PathElement(path.head.node, resolved = false) +: path.tail, partial = true))
+            List(ReachableByResult(PathElement(path.head.node, resolved = false) +: path.tail, table, partial = true))
           } else {
             List()
           }
diff --git a/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/queryengine/ResultTable.scala b/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/queryengine/ResultTable.scala
index 5b0121e49..9b2c04705 100644
--- a/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/queryengine/ResultTable.scala
+++ b/dataflowengineoss/src/main/scala/io/joern/dataflowengineoss/queryengine/ResultTable.scala
@@ -48,10 +48,14 @@ class ResultTable {
   * node in the graph.
   *
   * @param path this is the main result - a known path
+  * @param table the result table - kept to allow for detailed inspection of intermediate paths
   * @param partial indicate whether this result stands on its own or requires further analysis,
   *                e.g., by expanding output arguments backwards into method output parameters.
   * */
-case class ReachableByResult(path: Vector[PathElement], callDepth: Int = 0, partial: Boolean = false) {
+case class ReachableByResult(path: Vector[PathElement],
+                             table: ResultTable,
+                             callDepth: Int = 0,
+                             partial: Boolean = false) {
   def source: CfgNode = path.head.node
 
   def unresolvedArgs: Vector[CfgNode] =


Test patch:
diff --git a/dataflowengineoss/src/test/scala/io/joern/dataflowengineoss/queryengine/ResultTableTests.scala b/dataflowengineoss/src/test/scala/io/joern/dataflowengineoss/queryengine/ResultTableTests.scala
index ed1900bee..6e294e2bb 100644
--- a/dataflowengineoss/src/test/scala/io/joern/dataflowengineoss/queryengine/ResultTableTests.scala
+++ b/dataflowengineoss/src/test/scala/io/joern/dataflowengineoss/queryengine/ResultTableTests.scala
@@ -21,8 +21,8 @@ class ResultTableTests extends AnyWordSpec with Matchers {
       val node1 = cpg.literal.head
       val node2 = cpg.literal.last
       val table = new ResultTable
-      val res1 = Vector(ReachableByResult(Vector(PathElement(node1))))
-      val res2 = Vector(ReachableByResult(Vector(PathElement(node2))))
+      val res1 = Vector(ReachableByResult(Vector(PathElement(node1)), new ResultTable))
+      val res2 = Vector(ReachableByResult(Vector(PathElement(node2)), new ResultTable))
       table.add(node1, res1)
       table.add(node1, res2)
       table.get(node1) match {
@@ -52,9 +52,9 @@ class ResultTableTests extends AnyWordSpec with Matchers {
       val node4 = cpg.literal.code("moo").head
       val pathContainingPivot = Vector(PathElement(node4), PathElement(pivotNode), PathElement(node3))
       val table = new ResultTable
-      table.add(pivotNode, Vector(ReachableByResult(pathContainingPivot)))
+      table.add(pivotNode, Vector(ReachableByResult(pathContainingPivot, new ResultTable)))
       table.createFromTable(PathElement(pivotNode), Vector(PathElement(node1))) match {
-        case Some(Vector(ReachableByResult(path, _, _))) =>
+        case Some(Vector(ReachableByResult(path, _, _, _))) =>
           path.map(_.node.id) shouldBe List(node4.id, pivotNode.id, node1.id)
         case _ => fail()
       }