Scala future recursion returning early

Question

I'm trying to use recursive future calls to get a tree with a certain depth. The Futures.flatMap returns early, but the recursed futures do go on to complete after returning early.

We have a graph database with edges (parent-child relationships) and entities (nodes in tree). To retrieve the tree, we have two separate calls: getEdges and getEntitiesFromChildEdges. Both return futures.

The initial call, getEquipment, needs to return a Future. Since I, ultimately, need to return a future, I don't want to add an artificial wait.

Here's the code. getEquipment is called first.

getTree( rootEntities: Seq[Entity], parents: Seq[Entity], depth: Int): Future[Seq[Entity]] {

  getEdges( parents).flatMap{ edges =>
    getEntitiesFromChildEdges( edges).map{ children =>
      children.foreach{ child => findParent( child).addChild( child) }
      if( depth > 0) {
        getTree( rootEntities, children, depth - 1)
        logTheTree( "DEEPER", rootEntities)
        rootEntities
      } else {
        logTheTree( "!DEEPER", rootEntities)
        rootEntities
      }
    }
  }

}


getEquipment: Future[Json]{

  getRootEntities.flatMap{ rootEntities =>
    getTree( rootEntities, rootEntities, 3).flatMap { returnedRootEntities =>
      logTheTree( "FINAL", rootEntities)
      Json.toJson( rootEntities)
    }
  }

}

getEquipment is called first. Here are the log results. Note the logs with FINAL return before the tree is completely built.

DEEPER Root
DEEPER   One
FINAL Root
FINAL   One
---
DEEPER Root
DEEPER   One
DEEPER     Two
DEEPER     Three
!DEEPER Root
!DEEPER   One
!DEEPER     Two
!DEEPER     Three

The tree traversal is breadth-first instead of depth-first to minimize getEntities calls. Not relevant to the question, but does help to understand why the tree traversal is passed a sequence.

Lastly, I know I'm passing in the rootEntities unnecessarily, but the compiler complains when getTree.flatMap doesn't follow with returnedRootEntities =>. The actual getEquipment: Future is more complicated, but that's for a different question.

Answer 1

Someone pointed out that the reason the code was returning early was because the innermost getTree() returns a Future immediately (Doh!). It should have a map and enclose the two lines below it inside the map.

The else was changed to Future.successful and the getEntitiesFromChildEdges( edges).map was changed to flatMap.

Here's the updated code.

getTree( rootEntities: Seq[Entity], parents: Seq[Entity], depth: Int): Future[Seq[Entity]] {

  getEdges( parents).flatMap{ edges =>
    getEntitiesFromChildEdges( edges).flatMap{ children =>
      children.foreach{ child => findParent( child).addChild( child) }
      if( depth > 0) {
        // getTree needs to have a map and the results inside it.
        getTree( rootEntities, children, depth - 1).map{ r =>
          logTheTree( "DEEPER", rootEntities)
          rootEntities
        }
      } else {
        logTheTree( "!DEEPER", rootEntities)
        Future.successful( rootEntities)
      }
    }
  }

}

The answer from cmbaxter show promise :-) I'll look into using that technique in the future.

Answer 2

Here is a example based on my comment of using a Promise to handle this Future based recursion. I simplified your example so the code was cleaner, but it still has the same issue of needing to do Future based recursion. Take a look and hopefully you can bridge this into your code:

import concurrent.Future
import scala.concurrent.Promise
import concurrent.ExecutionContext.Implicits._
import scala.concurrent.Await
import concurrent.duration._

case class Person(id:Long, name:String, children:Option[List[Long]])
object RecurseTest extends App{
  val Everyone = Map(
    1L -> Person(1, "grandpa", Some(List(2,3))),
    2L -> Person(2, "dad", Some(List(4,5))),
    3L -> Person(3, "uncle joe", Some(List(6,7))),
    4L -> Person(4, "me", None),
    5L -> Person(5, "sis", None),
    6L -> Person(6, "cousin fred", None),
    7L -> Person(7, "cousin mary", None)
  )

  val f = getFamilMembers

  //Only using Await here to demonstrate the example.  Do not use in real code
  val result = Await.result(f, 5 seconds)
  println(result)

  def getFamilMembers():Future[List[String]] = {
    var names:List[String] = List.empty
    val prom = Promise[List[String]]
    def recurse(ids:List[Long]){
      ids.headOption match{

        //This is the recursion exit point
        case None => prom.success(names.reverse)
        case Some(id) =>
          getPerson(id) map{ p =>
            names = p.name :: names
            val childIds = p.children.getOrElse(List.empty)
            recurse(ids.tail ++ childIds)
          }                    
      }
    }

    recurse(List(1))  
    prom.future
  }

  def getPerson(id:Long):Future[Person] = {
    Future{         
      val p = Everyone.get(id).get
      println("loaded: " + p.name)
      p
    } 
  }
}