Rewrite Handle to be top-down instead of bottom-up tree

We also rewrite the query code to use list comprehensions and as
lazy of an evaulation as possible.  This may permit callers to
avoid evaluating result nodes they are yet not interested in taking.

Signed-off-by: Shawn O. Pearce <sop@google.com>

10 files changed, 148 insertions, 142 deletions

diff --git a/src/main/scala/com/google/gimd/DatabaseSpi.scala b/src/main/scala/com/google/gimd/DatabaseSpi.scala
index 6c4b9be..8523346 100644
--- a/src/main/scala/com/google/gimd/DatabaseSpi.scala
+++ b/src/main/scala/com/google/gimd/DatabaseSpi.scala
@@ -15,7 +15,7 @@
 package com.google.gimd
 
 import file.{File, FileType}
-import query.{Predicate, Handler}
+import query.{Predicate, Handle}
 
 /**
  * Trait that provides all functionality for Gimd to ask specific storage implementation
@@ -32,9 +32,11 @@ trait DatabaseSpi {
    * Query database for all user objects of type U stored in files of
    * type FileType[W] satisfying predicate p.
    */
-  def query[U,W](ft: FileType[W], p: Predicate[U]): List[(Handler,U)] = {
-    val files = all(ft).toList
-    files.flatMap(_.query(p))
+  def query[U,W](ft: FileType[W], p: Predicate[U]): Iterator[(Handle,U)] = {
+    for {
+      f <- all(ft)
+      r <- f.query(p)
+    } yield r
   }
 
 }
diff --git a/src/main/scala/com/google/gimd/Message.scala b/src/main/scala/com/google/gimd/Message.scala
index 0e88bf9..fb90734 100644
--- a/src/main/scala/com/google/gimd/Message.scala
+++ b/src/main/scala/com/google/gimd/Message.scala
@@ -22,12 +22,6 @@ object Message {
   val empty: Message = new Message(TreeSet.empty)
   def apply(fields: Iterable[Field]) = empty ++ fields
   def apply(fields: Field*) = new Message(TreeSet(fields: _*))
-
-  def filterMessageFields(xs: Iterable[Field]): List[Message] =
-    xs.flatMap(_ match {
-      case x: MessageField => List(x.value)
-      case _ => Nil
-    }).toList
 }
 
 final class Message(private val fields: Sorted[Field, Field])
diff --git a/src/main/scala/com/google/gimd/file/File.scala b/src/main/scala/com/google/gimd/file/File.scala
index 60c3c1a..7996e28 100644
--- a/src/main/scala/com/google/gimd/file/File.scala
+++ b/src/main/scala/com/google/gimd/file/File.scala
@@ -33,7 +33,8 @@ trait File[T] {
   val message: Message
   val userObject: T
 
-  def query[U](p: Predicate[U]): List[(MessageHandler, U)] =
-    MessageQuery.simpleQuery(fileType.userType, message, p, FileHandler(this))
-
+  def query[U](p: Predicate[U]): Iterator[(FileHandle[T], U)] =
+    for {
+      (handle, obj) <- MessageQuery.simpleQuery(fileType.userType, message, p)
+    } yield (FileHandle(this, handle), obj)
 }
diff --git a/src/main/scala/com/google/gimd/query/FileHandler.scala b/src/main/scala/com/google/gimd/query/FileHandler.scala
deleted file mode 100644
index 95d675b..0000000
--- a/src/main/scala/com/google/gimd/query/FileHandler.scala
+++ /dev/null
@@ -1,19 +0,0 @@
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.gimd.query
-
-import file.File
-
-final case class FileHandler[T](file: File[T]) extends Handler
diff --git a/src/main/scala/com/google/gimd/query/Handle.scala b/src/main/scala/com/google/gimd/query/Handle.scala
new file mode 100644
index 0000000..aeb35dc
--- /dev/null
+++ b/src/main/scala/com/google/gimd/query/Handle.scala
@@ -0,0 +1,47 @@
+// Copyright (C) 2009 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package com.google.gimd.query
+
+import com.google.gimd.file.File
+
+/** Any handle to a stored message. */
+abstract sealed class Handle
+
+/** Handle to a message contained within something else. */
+abstract case class InnerHandle() extends Handle
+
+/** Handle to a top-level message, that is not nested. */
+abstract case class RootHandle() extends Handle
+
+/** Handle to a message by itself. */
+final case class MessageHandle(
+  message: Message
+) extends InnerHandle
+
+/** Handle to a message stored within a field. */
+final case class FieldHandle(
+  // TODO We may be able to do a more efficient binding to the field
+  // in the parent by taking advantage of position of field in the
+  // parent, rather than using the object.
+  //
+  field: MessageField,
+  child: InnerHandle
+) extends InnerHandle
+
+/** Handle to a top level message. */
+final case class FileHandle[T](
+  file: File[T],
+  child: InnerHandle
+) extends RootHandle
diff --git a/src/main/scala/com/google/gimd/query/Handler.scala b/src/main/scala/com/google/gimd/query/Handler.scala
deleted file mode 100644
index c0840a4..0000000
--- a/src/main/scala/com/google/gimd/query/Handler.scala
+++ /dev/null
@@ -1,17 +0,0 @@
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.gimd.query
-
-abstract class Handler
diff --git a/src/main/scala/com/google/gimd/query/MessageHandler.scala b/src/main/scala/com/google/gimd/query/MessageHandler.scala
deleted file mode 100644
index d398dd8..0000000
--- a/src/main/scala/com/google/gimd/query/MessageHandler.scala
+++ /dev/null
@@ -1,17 +0,0 @@
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-
-package com.google.gimd.query
-
-final case class MessageHandler(parent: Handler, message: Message) extends Handler
diff --git a/src/main/scala/com/google/gimd/query/MessageQuery.scala b/src/main/scala/com/google/gimd/query/MessageQuery.scala
index 9bbb0cc..f88b0da 100644
--- a/src/main/scala/com/google/gimd/query/MessageQuery.scala
+++ b/src/main/scala/com/google/gimd/query/MessageQuery.scala
@@ -15,27 +15,35 @@
 package com.google.gimd.query
 
 object MessageQuery {
-
-  def simpleQuery[U, W](ut: UserType[W], m: Message, p: Predicate[U], parent: Handler):
-    List[(MessageHandler,U)] = {
-    val handler = MessageHandler(parent, m)
-
-    val matched = if (p.isType(ut.userTypeClass)) {
-      val value = ut.toUserObject(m).asInstanceOf[U]
-
-      if (p.isMatch(value))
-        List((handler, value))
-      else
-        Nil
-    } else Nil
-
-    val childMatches = (for {
-      nm <- ut.children
-      childMessageFields = Message.filterMessageFields(m.all(nm.name))
-      matches = childMessageFields.flatMap(simpleQuery(nm.userType, _, p, handler))
-    } yield matches).flatMap(identity[List[(MessageHandler,U)]])
-
-    matched ++ childMatches
+  def simpleQuery[U, W](ut: UserType[W], m: Message, p: Predicate[U]):
+   Iterator[(InnerHandle,U)] = {
+    val children = queryChildren(ut, m, p)
+    val self = querySelf(ut, m, p)
+    if (self.hasNext)
+      self ++ children
+    else
+      children
   }
 
+  private def querySelf[U, W](ut: UserType[W], m: Message, p: Predicate[U]) =
+    if (p.isType(ut.userTypeClass)) {
+      val obj = ut.toUserObject(m).asInstanceOf[U]
+      if (p.isMatch(obj))
+        Iterator.single( (MessageHandle(m), obj) )
+      else
+        Iterator.empty
+    } else
+      Iterator.empty
+
+  private def queryChildren[U, W](ut: UserType[W], m: Message, p: Predicate[U]) =
+    // TODO if ut.children was sorted we could merge against the sorted
+    // property of message and produce a faster join between the two.
+    //
+    for {
+      member <- ut.children.elements
+      field <- m.all(member.name).elements
+      if field.isInstanceOf[MessageField]
+      f = field.asInstanceOf[MessageField]
+      (handle, userObject) <- simpleQuery(member.userType, f.value, p)
+    } yield (FieldHandle(f, handle), userObject)
 }
diff --git a/src/test/resources/com/google/gimd/query/simpleMessage.gimd b/src/test/resources/com/google/gimd/query/simpleMessage.gimd
deleted file mode 100644
index c1415b3..0000000
--- a/src/test/resources/com/google/gimd/query/simpleMessage.gimd
+++ /dev/null
@@ -1,21 +0,0 @@
-name Some name
-child <
-  name Child1
-  property1 true
->
-child <
-  name Child2
-  property1 false
->
-child <
-  name Child3
-  property1 true
->
-child <
-  name Child4
-  property1 false
->
-child <
-  name Child5
-  property1 true
->
diff --git a/src/test/scala/com/google/gimd/query/MessageQueryTestCase.scala b/src/test/scala/com/google/gimd/query/MessageQueryTestCase.scala
index ded2592..3db5968 100644
--- a/src/test/scala/com/google/gimd/query/MessageQueryTestCase.scala
+++ b/src/test/scala/com/google/gimd/query/MessageQueryTestCase.scala
@@ -19,51 +19,79 @@ import org.junit.Test
 import org.junit.Assert._
 
 class MessageQueryTestCase {
+  case class TreeNode(id: Int, name: String)
+  object TreeNodeType extends UserType[TreeNode] {
+    def toMessageBuffer(n: TreeNode) =
+      new MessageBuffer().
+        add("id", n.id).
+        add("name", n.name)
+    def toUserObject(m: Message): TreeNode =
+      new TreeNode(
+        m.one("id").intField.value,
+        m.one("name").stringField.value
+      )
+    override def children = Seq(new NestedMember("node", TreeNodeType))
+  }
 
-  case class Child(name: String, property1: Boolean)
+  val root = new TreeNode(-1, "a")
+  val child_0 = new TreeNode(0, "a")
+  val child_1 = new TreeNode(1, "b")
+  val child_2 = new TreeNode(2, "a")
 
-  object ChildType extends UserType[Child] {
-    def toMessageBuffer(child: Child) = (new MessageBuffer()) ++
-            List(Field("name", child.name), Field("property1", child.property1.toString))
-    def toUserObject(m: Message): Child =
-      new Child(m.one("name").stringField.value,
-                m.one("property1").stringField.value.toBoolean)
-  }
+  val child_msg0 = TreeNodeType.toMessage(child_0)
+  val child_msg1 = TreeNodeType.toMessage(child_1)
+  val child_msg2 = TreeNodeType.toMessage(child_2)
 
-  case class SimpleMessage(name: String, children: List[Child])
+  val message = TreeNodeType.toMessageBuffer(root).
+    add("node", child_msg0).
+    add("node", child_msg1).
+    add("node", child_msg2).readOnly
 
-  object SimpleMessageType extends UserType[SimpleMessage] {
-    def toMessageBuffer(sm: SimpleMessage) = (new MessageBuffer()) ++
-      List(Field("name", sm.name))
-    def toUserObject(m: Message): SimpleMessage = {
-      val children = m.all("child").map(_.messageField.value).map(ChildType.toUserObject(_))
-      val name = m.one("name").stringField.value
-      new SimpleMessage(name, children.toList)
-    }
-    override def children = Seq(new NestedMember("child", ChildType))
-  }
+  @Test
+  def queryParentWithChildren = {
+    val queryResult = query((n: TreeNode) => n.name == "a")
 
-  object MockParentHandler extends Handler
+    val expectedResult = Set(
+      (handle(message), root),
+      (handle(("node", child_msg0)), child_0),
+      (handle(("node", child_msg2)), child_2)
+    )
+    assertEquals(expectedResult, Set(queryResult.toList: _*))
+  }
 
   @Test
-  def simpleQuery = {
-    import Predicate.functionLiteral2Predicate
-    val reader = new java.io.InputStreamReader(
-      this.getClass.getResourceAsStream("simpleMessage.gimd")
+  def queryChildren = {
+    val queryResult = query((n: TreeNode) => n.name == "a" && n.id >= 0)
+
+    val expectedResult = Set(
+      (handle(("node", child_msg0)), child_0),
+      (handle(("node", child_msg2)), child_2)
     )
-    val message = gimd.text.Parser.parse(reader)
-    val messageHandler = MessageHandler(MockParentHandler, message)
+    assertEquals(expectedResult, Set(queryResult.toList: _*))
+  }
 
-    val predicate = (child: Child) => child.property1 == true
-    val queryResult = MessageQuery.simpleQuery(SimpleMessageType, message, predicate,
-      MockParentHandler)
+  @Test
+  def queryParent = {
+    val queryResult = query((n: TreeNode) => n.name == "a" && n.id < 0)
 
-    val expectedChildren = List(Child("Child1", true), Child("Child3", true), Child("Child5", true))
-    val expectedMessages = expectedChildren.map(ChildType.toMessageBuffer(_).readOnly)
-    val handlers = expectedMessages.map(MessageHandler(messageHandler, _))
-    val expectedResult = handlers zip expectedChildren
+    val expectedResult = Set(
+      (handle(message), root)
+    )
+    assertEquals(expectedResult, Set(queryResult.toList: _*))
+  }
 
-    assertEquals(Set(expectedResult: _*), Set(queryResult: _*))
+  private def query(p: (TreeNode) => Boolean) = {
+    import Predicate.functionLiteral2Predicate
+    MessageQuery.simpleQuery(TreeNodeType, message, p)
   }
 
+  private def handle(message: Message): InnerHandle = MessageHandle(message)
+  private def handle(p: (String, Message)*): InnerHandle = {
+    val (name, message) = p(0)
+    val field = MessageField(name, message)
+    if (p.size == 1) {
+      FieldHandle(field, handle(message))
+    } else
+      FieldHandle(field, handle(p.drop(1): _*))
+  }
 }