Permalink
Browse files

The TraversalMatcher now supports variable length paths

  • Loading branch information...
1 parent 0da687b commit c13774f1a7231838648bbdff531d6d9c102c0cc1 @systay committed Sep 30, 2012
Showing with 1,839 additions and 472 deletions.
  1. +2 −2 cypher/src/main/scala/org/neo4j/cypher/PathImpl.scala
  2. +2 −0 cypher/src/main/scala/org/neo4j/cypher/internal/executionplan/ExecutionPlanImpl.scala
  3. +0 −106 cypher/src/main/scala/org/neo4j/cypher/internal/executionplan/builders/Trail.scala
  4. +100 −50 cypher/src/main/scala/org/neo4j/cypher/internal/executionplan/builders/TrailBuilder.scala
  5. +5 −4 cypher/src/main/scala/org/neo4j/cypher/internal/executionplan/builders/TraversalMatcherBuilder.scala
  6. +12 −6 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/Pipe.scala
  7. +22 −20 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/TraversalMatchPipe.scala
  8. +42 −15 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/BidirectionalTraversalMatcher.scala
  9. +58 −0 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/EndPoint.scala
  10. +27 −65 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/ExpanderStep.scala
  11. +7 −10 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/MonodirectionalTraversalMatcher.scala
  12. +1 −0 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/PatternMatcher.scala
  13. +96 −0 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/SingleStep.scala
  14. +86 −0 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/SingleStepTrail.scala
  15. +56 −0 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/Trail.scala
  16. +2 −3 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/TraversalPathExpander.scala
  17. +156 −0 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/VarLengthStep.scala
  18. +145 −0 cypher/src/main/scala/org/neo4j/cypher/internal/pipes/matching/VariableLengthStepTrail.scala
  19. +6 −6 cypher/src/test/scala/org/neo4j/cypher/ExecutionEngineTest.scala
  20. +1 −1 cypher/src/test/scala/org/neo4j/cypher/GraphDatabaseTestBase.scala
  21. +1 −11 cypher/src/test/scala/org/neo4j/cypher/PathImplTest.scala
  22. +7 −1 cypher/src/test/scala/org/neo4j/cypher/docgen/ArticleTest.scala
  23. +1 −2 cypher/src/test/scala/org/neo4j/cypher/docgen/cookbook/LinkedListTest.scala
  24. +21 −24 cypher/src/test/scala/org/neo4j/cypher/docgen/cookbook/MealTestIgnored.scala
  25. +3 −3 cypher/src/test/scala/org/neo4j/cypher/docgen/cookbook/PathTreeTest.scala
  26. +196 −84 cypher/src/test/scala/org/neo4j/cypher/internal/executionplan/builders/TrailBuilderTest.scala
  27. +231 −0 cypher/src/test/scala/org/neo4j/cypher/internal/executionplan/builders/TrailDecomposeTest.scala
  28. +160 −0 cypher/src/test/scala/org/neo4j/cypher/internal/executionplan/builders/TrailToStepTest.scala
  29. +12 −19 ...src/test/scala/org/neo4j/cypher/internal/executionplan/builders/TraversalMatcherBuilderTest.scala
  30. +22 −38 ...rg/neo4j/cypher/internal/pipes/matching/{ExpanderStepTest.scala → ExpanderStepReversalTest.scala}
  31. +62 −0 cypher/src/test/scala/org/neo4j/cypher/internal/pipes/matching/StepSizeTest.scala
  32. +2 −2 cypher/src/test/scala/org/neo4j/cypher/internal/pipes/matching/TraversalMatcherTest.scala
  33. +214 −0 ...rc/test/scala/org/neo4j/cypher/internal/pipes/matching/VariableLengthExpanderStepExpandTest.scala
  34. +81 −0 .../test/scala/org/neo4j/cypher/internal/pipes/matching/VariableLengthExpanderStepReversalTest.scala
@@ -30,11 +30,11 @@ case class PathImpl(pathEntities: PropertyContainer*)
with Traversable[PropertyContainer]
with CypherArray {
- assert(isProperPath)
+ require(isProperPath, "Tried to construct a path that is not built like a path")
def isProperPath: Boolean = {
var x = true
- val (nodes, rels) = pathEntities.partition(e => {
+ val (nodes, rels) = pathEntities.toList.partition(e => {
x = !x
!x
})
@@ -140,6 +140,8 @@ class ExecutionPlanImpl(inputQuery: Query, graph: GraphDatabaseService) extends
}
private def produceAndThrowException(plan: ExecutionPlanInProgress) {
+ val s = plan.pipe.symbols
+
val errors = builders.flatMap(builder => builder.missingDependencies(plan).map(builder -> _)).toList.
sortBy {
case (builder, _) => builder.priority
@@ -1,106 +0,0 @@
-/**
- * Copyright (c) 2002-2012 "Neo Technology,"
- * Network Engine for Objects in Lund AB [http://neotechnology.com]
- *
- * This file is part of Neo4j.
- *
- * Neo4j is free software: you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation, either version 3 of the License, or
- * (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
- */
-package org.neo4j.cypher.internal.executionplan.builders
-
-import org.neo4j.graphdb.{Direction, PropertyContainer}
-import org.neo4j.cypher.internal.symbols.{RelationshipType, NodeType, SymbolTable}
-import org.neo4j.cypher.internal.commands.{Pattern, True, Predicate}
-import org.neo4j.graphdb.DynamicRelationshipType._
-import org.neo4j.cypher.internal.pipes.matching.ExpanderStep
-import scala.Some
-
-
-sealed abstract class Trail {
- def pathDescription: Seq[String]
- def start: String
- def end: String
- def size: Int
- def toSteps(id: Int): Option[ExpanderStep]
- override def toString: String = pathDescription.toString()
- def decompose(p: Seq[PropertyContainer]): Map[String, Any] = decompose(p, Map.empty)._2
- protected[builders] def decompose(p: Seq[PropertyContainer], r: Map[String, Any]): (Seq[PropertyContainer], Map[String, Any])
- def symbols(table: SymbolTable): SymbolTable
- def contains(target: String): Boolean
- def predicates:Seq[Predicate]
- def patterns:Seq[Pattern]
-}
-
-final case class BoundPoint(name: String) extends Trail {
- def end = name
- def pathDescription = Seq(name)
- def start = name
- def size = 0
- def toSteps(id: Int) = None
- protected[builders] def decompose(p: Seq[PropertyContainer], r: Map[String, Any]) = {
- assert(p.size == 1, "Expected a path with a single node in it")
- (p.tail, r ++ Map(name -> p.head))
- }
- def symbols(table: SymbolTable): SymbolTable = table.add(name, NodeType())
- def contains(target: String): Boolean = target == name
- def predicates = Seq.empty
- def patterns = Seq.empty
-}
-
-final case class WrappingTrail(s: Trail,
- dir: Direction,
- rel: String,
- typ: Seq[String],
- end: String,
- candPredicates: Seq[Predicate],
- pattern: Pattern) extends Trail {
-
- val relPred = candPredicates.find(createFinder(rel))
- val nodePred = candPredicates.find(createFinder(end))
-
- private def containsSingle(set: Set[String], elem: String) = set.size == 1 && set.head == elem
-
- private def createFinder(elem: String): (Predicate => Boolean) =
- (pred: Predicate) => containsSingle(pred.symbolTableDependencies, elem)
-
- def start = s.start
-
- def pathDescription = s.pathDescription ++ Seq(rel, end)
-
- def toSteps(id: Int) = {
- val types = typ.map(withName(_))
- val steps = s.toSteps(id + 1)
- val relPredicate = relPred.getOrElse(True())
- val nodePredicate = nodePred.getOrElse(True())
-
- Some(ExpanderStep(id, types, dir, steps, relPredicate, nodePredicate))
- }
-
- def size = s.size + 1
-
- protected[builders] def decompose(p: Seq[PropertyContainer], m: Map[String, Any]) = {
- val r = p.tail.head
- val n = p.head
- val newMap = m + (rel -> r) + (end -> n)
- s.decompose(p.tail.tail, newMap)
- }
-
- def symbols(table: SymbolTable): SymbolTable = s.symbols(table).add(end, NodeType()).add(rel, RelationshipType())
-
- def contains(target: String): Boolean = s.contains(target) || target == end
-
- def predicates = nodePred.toSeq ++ relPred.toSeq ++ s.predicates
-
- def patterns = s.patterns :+ pattern
-}
@@ -19,54 +19,92 @@
*/
package org.neo4j.cypher.internal.executionplan.builders
-import org.neo4j.graphdb.{Direction, PropertyContainer}
-import org.neo4j.cypher.internal.symbols.{RelationshipType, NodeType, SymbolTable}
-import org.neo4j.cypher.internal.pipes.matching.ExpanderStep
-import org.neo4j.graphdb.DynamicRelationshipType.withName
-import org.neo4j.cypher.internal.commands.{Predicate, RelatedTo, True}
-
+import org.neo4j.cypher.internal.commands.{VarLengthRelatedTo, RelatedTo, Pattern, Predicate}
+import org.neo4j.graphdb.Direction
+import org.neo4j.cypher.internal.commands.expressions.{Identifier, Property}
+import org.neo4j.cypher.internal.pipes.matching.{EndPoint, VariableLengthStepTrail, SingleStepTrail, Trail}
+import org.neo4j.helpers.ThisShouldNotHappenError
+import annotation.tailrec
object TrailBuilder {
- def findLongestTrail(patterns: Seq[RelatedTo], boundPoints: Seq[String], predicates: Seq[Predicate] = Seq.empty) =
+ def findLongestTrail(patterns: Seq[Pattern], boundPoints: Seq[String], predicates: Seq[Predicate] = Seq.empty) =
new TrailBuilder(patterns, boundPoints, predicates).findLongestTrail()
}
final case class LongestTrail(start: String, end: Option[String], longestTrail: Trail) {
- lazy val step = longestTrail.toSteps(0).get.reverse()
+ lazy val step = longestTrail.toSteps(0).get
}
-final class TrailBuilder(patterns: Seq[RelatedTo], boundPoints: Seq[String], predicates: Seq[Predicate]) {
- private def internalFindLongestPath(doneSeq: Seq[(Trail, Seq[RelatedTo])]): Seq[(Trail, Seq[RelatedTo])] = {
- val result: Seq[(Trail, Seq[RelatedTo])] = doneSeq.flatMap {
- case (done: Trail, patterns: Seq[RelatedTo]) =>
- val relatedToes = patterns.filter {
- rel => done.end == rel.left || done.end == rel.right
- }
+final class TrailBuilder(patterns: Seq[Pattern], boundPoints: Seq[String], predicates: Seq[Predicate]) {
+ @tailrec
+ private def internalFindLongestPath(doneSeq: Seq[(Trail, Seq[Pattern])]): Seq[(Trail, Seq[Pattern])] = {
+
+ def createFinder(elem: String): (Predicate => Boolean) = {
+ def containsSingle(set: Set[String]) = set.size == 1 && set.head == elem
+ (pred: Predicate) => containsSingle(pred.symbolTableDependencies)
+ }
+
+ def transformToTrail(p: Pattern, done: Trail, patternsToDo: Seq[Pattern]): (Trail, Seq[Pattern]) = {
+ def predicateRewriter(from: String, to: String)(pred: Predicate) = pred.rewrite {
+ case Identifier(name) if name == from => Identifier(to)
+ case Property(name, prop) if name == from => Property(to, prop)
+ case e => e
+ }
+ def relPred(k: String) = predicates.find(createFinder(k)).map(predicateRewriter(k, "r"))
+ def nodePred(k: String) = predicates.find(createFinder(k)).map(predicateRewriter(k, "n"))
+ def singleStep(rel: RelatedTo, end: String, dir: Direction) = done.add(start => SingleStepTrail(EndPoint(end), dir, rel.relName, rel.relTypes, start, relPred(rel.relName), nodePred(start), rel))
+ def multiStep(rel: VarLengthRelatedTo, end: String, dir: Direction) = done.add(start => VariableLengthStepTrail(EndPoint(end), dir, rel.relTypes, rel.minHops.getOrElse(1), rel.maxHops, rel.pathName, rel.relIterator, start, rel))
+
+ val patternsLeft = patternsToDo.filterNot(_ == p)
+
+ val result: Trail = p match {
+ case rel: RelatedTo if rel.left == done.end => singleStep(rel, rel.right, rel.direction)
+ case rel: RelatedTo if rel.right == done.end => singleStep(rel, rel.left, rel.direction.reverse())
+ case rel: VarLengthRelatedTo if rel.end == done.end => multiStep(rel, rel.start, rel.direction.reverse())
+ case rel: VarLengthRelatedTo if rel.start == done.end => multiStep(rel, rel.end, rel.direction)
+ case _ => throw new ThisShouldNotHappenError("Andres", "This pattern is not expected")
+ }
- if (relatedToes.isEmpty)
- Seq((done, patterns))
- else {
- Seq((done, patterns)) ++
- relatedToes.map {
- case rel if rel.left == done.end => (WrappingTrail(done, rel.direction.reverse(), rel.relName, rel.relTypes, rel.right, predicates, rel), patterns.filterNot(_ == rel))
- case rel => (WrappingTrail(done, rel.direction, rel.relName, rel.relTypes, rel.left, predicates, rel), patterns.filterNot(_ == rel))
- }
+ (result, patternsLeft)
+ }
+
+ val result: Seq[(Trail, Seq[Pattern])] = doneSeq.flatMap {
+ case (done: Trail, patternsToDo: Seq[Pattern]) =>
+ val relatedToes: Seq[Pattern] = patternsToDo.filter {
+ case rel: RelatedTo => done.end == rel.left || done.end == rel.right
+ case rel: VarLengthRelatedTo => done.end == rel.end || done.end == rel.start
}
+
+ val newValues = relatedToes.map(transformToTrail(_, done, patternsToDo))
+ Seq((done, patternsToDo)) ++ newValues
}
- if (result.distinct == doneSeq.distinct)
+ val uniqueResults = result.distinct
+ val uniqueInput = doneSeq.distinct
+
+ if (uniqueResults == uniqueInput)
result
else
- internalFindLongestPath(result)
+ internalFindLongestPath(uniqueResults)
}
- private def findLongestTrail(): Option[LongestTrail] =
+ private def findLongestTrail(): Option[LongestTrail] = {
+ def findAllPaths(): Seq[(Trail, scala.Seq[Pattern])] = {
+ val startPoints = boundPoints.map(point => (EndPoint(point), patterns))
+ val foundPaths = internalFindLongestPath(startPoints)
+ val filteredPaths = foundPaths.filter {
+ case (trail, toes) => trail.size > 0 && trail.start != trail.end
+ }
+ filteredPaths
+ }
+
+
if (patterns.isEmpty) {
None
}
else {
- val foundPaths: Seq[(Trail, Seq[RelatedTo])] = findAllPaths()
- val pathsBetweenBoundPoints: Seq[(Trail, Seq[RelatedTo])] = findCompatiblePaths(foundPaths)
+ val foundPaths: Seq[(Trail, Seq[Pattern])] = findAllPaths()
+ val pathsBetweenBoundPoints: Seq[(Trail, Seq[Pattern])] = findCompatiblePaths(foundPaths)
if (pathsBetweenBoundPoints.isEmpty) {
None
@@ -76,48 +114,60 @@ final class TrailBuilder(patterns: Seq[RelatedTo], boundPoints: Seq[String], pre
Some(trail)
}
}
+ }
+ private def findLongestTrail(pathsBetweenBoundPoints: scala.Seq[(Trail, scala.Seq[Pattern])]): LongestTrail = {
+ val almost = pathsBetweenBoundPoints.sortWith {
+ case ((t1, _), (t2, _)) => t1.size < t2.size || t1.start > t2.start //Sort first by length, and then by start point
+ }
- private def findLongestTrail(pathsBetweenBoundPoints: scala.Seq[(Trail, scala.Seq[RelatedTo])]): LongestTrail = {
- val almost = pathsBetweenBoundPoints.sortBy(_._1.size)
val (longestPath, _) = almost.last
val start = longestPath.start
val end = if (boundPoints.contains(longestPath.end)) Some(longestPath.end) else None
- val trail = LongestTrail(start, end, longestPath)
- trail
+ LongestTrail(start, end, longestPath)
}
- private def findAllPaths(): Seq[(Trail, scala.Seq[RelatedTo])] = {
- val startPoints = boundPoints.map(point => (BoundPoint(point), patterns))
- val foundPaths = internalFindLongestPath(startPoints).
- filter {
- case (trail, toes) => trail.size > 0 && trail.start != trail.end
- }
- foundPaths
- }
- private def findCompatiblePaths(incomingPaths: Seq[(Trail, Seq[RelatedTo])]): Seq[(Trail, Seq[RelatedTo])] = {
- val foundPaths = incomingPaths.filterNot {
+ private def findCompatiblePaths(incomingPaths: Seq[(Trail, Seq[Pattern])]): Seq[(Trail, Seq[Pattern])] = {
+ val pathsWithoutBoundPointsInMiddle = incomingPaths.filterNot {
case (trail, _) => hasBoundPointsInMiddleOfPath(trail)
}
+ val boundInBothEnds = pathsWithoutBoundPointsInMiddle.filter {
+ case (p, _) =>
+ val startBound = boundPoints.contains(p.start)
+ val endBound = boundPoints.contains(p.end)
+ val numberOfVarlength = p.filter(_.isInstanceOf[VariableLengthStepTrail]).size
+ val numberOfTrails = p.asSeq.size
+ val validVarlength = (numberOfVarlength == 1 && numberOfTrails == 1)
+ val noVarlength = numberOfVarlength == 0
- val boundInTwoPoints = foundPaths.filter {
- case (p, left) => boundPoints.contains(p.start) && boundPoints.contains(p.end)
+ startBound && endBound && (validVarlength || noVarlength)
}
- val boundInAtLeastOnePoints = foundPaths.filter {
- case (p, left) => boundPoints.contains(p.start) || boundPoints.contains(p.end)
+ val boundInOneEnd = pathsWithoutBoundPointsInMiddle.filter {
+ case (p, _) =>
+ val startBound = boundPoints.contains(p.start)
+ val endBound = boundPoints.contains(p.end)
+ val numberOfVarlength = p.filter(_.isInstanceOf[VariableLengthStepTrail]).size
+ val seq = p.asSeq
+ val idxOfVar = seq.indexWhere(_.isInstanceOf[VariableLengthStepTrail])
+
+ val numberOfTrails = p.asSeq.size - 2
+ val result = startBound && !endBound && numberOfVarlength <= 1 && (numberOfVarlength == 0 || idxOfVar == numberOfTrails)
+ result
}
- if (boundInTwoPoints.nonEmpty)
- boundInTwoPoints
+ if (boundInBothEnds.nonEmpty)
+ boundInBothEnds
else
- boundInAtLeastOnePoints
+ boundInOneEnd
}
def hasBoundPointsInMiddleOfPath(trail: Trail): Boolean = {
- trail.pathDescription.slice(1, trail.pathDescription.size - 1).exists(boundPoints.contains)
+ val nodesInBetween = trail.nodeNames.toSet -- Set(trail.start, trail.end)
+
+ nodesInBetween exists (boundPoints.contains)
}
}
@@ -27,7 +27,6 @@ import graphdb.{Node, GraphDatabaseService}
import org.neo4j.cypher.internal.pipes.{ParameterPipe, TraversalMatchPipe, ExecutionContext}
import org.neo4j.cypher.internal.pipes.matching.{MonoDirectionalTraversalMatcher, BidirectionalTraversalMatcher}
import org.neo4j.cypher.internal.executionplan.ExecutionPlanInProgress
-import scala.Some
import org.neo4j.cypher.internal.commands.NodeByIndex
import org.neo4j.cypher.internal.commands.NodeByIndexQuery
@@ -46,7 +45,8 @@ class TraversalMatcherBuilder(graph: GraphDatabaseService) extends PlanBuilder {
(matcher, Seq(startToken))
} else {
val (endToken, endNodeFn) = identifier2nodeFn(graph, end.get, unsolvedItems)
- val matcher = new BidirectionalTraversalMatcher(longestPath.step, startNodeFn, endNodeFn)
+ val step = longestPath.step
+ val matcher = new BidirectionalTraversalMatcher(step, startNodeFn, endNodeFn)
(matcher, Seq(startToken, endToken))
}
@@ -82,8 +82,9 @@ class TraversalMatcherBuilder(graph: GraphDatabaseService) extends PlanBuilder {
}
val pattern = plan.query.patterns.flatMap {
- case Unsolved(r: RelatedTo) if !r.optional && r.left != r.right => Some(r)
- case _ => None
+ case Unsolved(r: RelatedTo) if !r.optional && r.left != r.right => Some(r)
+ case Unsolved(r: VarLengthRelatedTo) if !r.optional && r.start != r.end => Some(r)
+ case _ => None
}
val preds = plan.query.where.filter(_.unsolved).map(_.token)
Oops, something went wrong.

0 comments on commit c13774f

Please sign in to comment.