Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
fixes #600: Double optional with no matching relationships returns to…
…o many rows
  • Loading branch information
systay committed Jun 13, 2012
1 parent c665994 commit 3d0efc8
Show file tree
Hide file tree
Showing 4 changed files with 62 additions and 18 deletions.
4 changes: 4 additions & 0 deletions cypher/CHANGES.txt
@@ -1,3 +1,7 @@
1.8 (2012-06-21)
--------------------
o Fixes #600: Double optional with no matching relationships returns too many rows

1.8.M04 (2012-06-07)
--------------------
o CREATE now accepts full paths and not only single nodes and relationships
Expand Down
Expand Up @@ -24,48 +24,69 @@ import collection.immutable.Set
import collection.Seq
import collection.Map

/*
Normally, when we encounter an optional relationship, we can try with null and see if that's enough. But for
double optional patterns ( a -[?]-> X <-[?]- b ), we have to try to get to X both from a and from b
to find all combinations.
This class takes care of double optional patterns
*/
class DoubleOptionalPatternMatcher(bindings: Map[String, MatchingPair],
predicates: Seq[Predicate],
includeOptionals: Boolean,
source: Map[String, Any],
doubleOptionalPaths: Seq[DoubleOptionalPath])
extends PatternMatcher(bindings, predicates, includeOptionals, source) {

private lazy val optionalRels: Seq[String] = doubleOptionalPaths.map(_.relationshipName)

override protected def traverseNextSpecificNode[U](remaining: Set[MatchingPair],
history: History,
yielder: (Map[String, Any]) => U,
current: MatchingPair,
leftToDoAfterThisOne: Set[MatchingPair],
alreadyInExtraWork: Boolean): Boolean = {
val result = super.traverseNextSpecificNode(remaining, history, yielder, current, leftToDoAfterThisOne, false)
val initialResult = super.traverseNextSpecificNode(remaining, history, yielder, current, leftToDoAfterThisOne, alreadyInExtraWork = false)

// To prevent going around for infinity, we check that we are not already checking for double optionals
if (includeOptionals && !alreadyInExtraWork) {
val work = shouldDoExtraWork(current, remaining)
work.foldLeft(result)((last, next) => {
val pathsToCheck = shouldDoExtraWork(current, remaining)

val extendedCheck = pathsToCheck.foldLeft(initialResult)((last, next) => {
val (newHead, newRemaining) = remaining.partition(p => p.patternNode.key == next.endNode)
val remainingPlusCurrent = newRemaining + current

val myYielder = (m: Map[String, Any]) => {
m.get(next.relationshipName) match {
case Some(null) => yielder(m)
case _ =>
}
}
val myYielder = createYielder(yielder, next.relationshipName) _

traverseNextSpecificNode(remaining, history, myYielder, newHead.head, remainingPlusCurrent, true) || last
traverseNextSpecificNode(remaining, history, myYielder, newHead.head, remainingPlusCurrent, alreadyInExtraWork = true) || last
})

extendedCheck
}
else
result
initialResult
}

def shouldDoExtraWork(current: MatchingPair, remaining: Set[MatchingPair]): Seq[DoubleOptionalPath] = doubleOptionalPaths.filter(
dop => {
val b = dop.startNode == current.patternNode.key
val sdf = remaining.exists(_.patternNode.key == dop.endNode)
b && sdf

private def shouldDoExtraWork(current: MatchingPair, remaining: Set[MatchingPair]): Seq[DoubleOptionalPath] = doubleOptionalPaths.filter(
optionalPath => {
val standingOnOptionalPath = optionalPath.startNode == current.patternNode.key
val endPointStillToDo = remaining.exists(_.patternNode.key == optionalPath.endNode)
standingOnOptionalPath && endPointStillToDo
})

private def createYielder[A](inner: Map[String, Any] => A, relName: String)(m: Map[String, Any]) {
m.get(relName) match {
case Some(null) if !allOptionalRelsAreNull(m) => inner(m) /*We should only yield if we have found a null for
this relationship, and not all optional relationships
are null*/
case _ =>
}
)
}

private def allOptionalRelsAreNull[A](m: Map[String, Any]): Boolean = {
optionalRels.flatMap(m.get(_)).forall(_ == null)
}
}

case class DoubleOptionalPath(startNode:String, endNode:String, relationshipName:String)
case class DoubleOptionalPath(startNode: String, endNode: String, relationshipName: String)
Expand Up @@ -2053,4 +2053,13 @@ RETURN x0.name?
val result = parseAndExecute("START a=node(1) foreach(n in extract(p in a-->() : last(p)) : set n.touched = true) return a-->()").dumpToString()
println(result)
}

@Test
def double_optional_with_no_matches() {
createNode()
createNode()

val result = parseAndExecute("START a=node(1),b=node(2) MATCH a-[?]->X<-[?]-b return X").toList
assert(result === List(Map("X"->null)))
}
}
Expand Up @@ -262,6 +262,16 @@ class MatchingContextTest extends GraphDatabaseTestBase with Assertions {
assertMatches(matchingContext.getMatches(Map("a" -> a)), 1, Map("a" -> a, "b" -> null, "r" -> null))
}

@Test def doubleOptional() {
val patterns: Seq[Pattern] = Seq(
RelatedTo("a", "x", "r1", Seq(), Direction.OUTGOING, optional = true, predicate = True()),
RelatedTo("b", "x", "r2", Seq(), Direction.OUTGOING, optional = true, predicate = True())
)
val matchingContext = new MatchingContext(patterns, bind("a", "b"))

assertMatches(matchingContext.getMatches(Map("a" -> a, "b" -> b)), 1, Map("a" -> a, "b" -> b, "r1" -> null, "r2" -> null))
}

@Test def optionalRelatedWithMatch() {
val r1 = relate(a, b, "t1")
relate(a, b, "t2")
Expand Down

0 comments on commit 3d0efc8

Please sign in to comment.