Repository: cayleygraph/cayley
Pull request #886 (2019-11-07 22:50:22)

Implement Optional path
Currently `path` library provides a `SaveOptional` helper - this is the only way to use optional path right now. This PR adds a generic `Optional` helper that accepts any other path, allowing to query larger optional subtrees.

<!-- Reviewable:start -->
---
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/cayleygraph/cayley/886)
<!-- Reviewable:end -->



Patch:
diff --git a/query/path/morphism_apply_functions.go b/query/path/morphism_apply_functions.go
index ee88eb7..10adbec 100644
--- a/query/path/morphism_apply_functions.go
+++ b/query/path/morphism_apply_functions.go
@@ -36,6 +36,10 @@ func join(its ...shape.Shape) shape.Shape {
 	return shape.Intersect(its)
 }
 
+func joinOpt(main, opt shape.Shape) shape.Shape {
+	return shape.IntersectOptional(main, opt)
+}
+
 // isMorphism represents all nodes passed in-- if there are none, this function
 // acts as a passthrough for the previous iterator.
 func isMorphism(nodes ...quad.Value) morphism {
@@ -88,6 +92,16 @@ func filterMorphism(filt []shape.ValueFilter) morphism {
 	}
 }
 
+// hasPathMorphism is a generic form of Has morphism - it accepts a subtree that will be checked on the current path.
+func hasPathMorphism(p *Path) morphism {
+	return morphism{
+		Reversal: func(ctx *pathContext) (morphism, *pathContext) { return hasPathMorphism(p), ctx },
+		Apply: func(in shape.Shape, ctx *pathContext) (shape.Shape, *pathContext) {
+			return shape.IntersectShapes(in, p.Shape()), ctx
+		},
+	}
+}
+
 // hasMorphism is the set of nodes that is reachable via either a *Path, a
 // single node.(string) or a list of nodes.([]string).
 func hasMorphism(via interface{}, rev bool, nodes ...quad.Value) morphism {
@@ -265,6 +279,16 @@ func andMorphism(p *Path) morphism {
 	}
 }
 
+// andOptMorphism sticks a path onto the current iterator chain and makes it optional.
+func andOptMorphism(p *Path) morphism {
+	return morphism{
+		Reversal: func(ctx *pathContext) (morphism, *pathContext) { return andOptMorphism(p), ctx },
+		Apply: func(in shape.Shape, ctx *pathContext) (shape.Shape, *pathContext) {
+			return joinOpt(in, p.Shape()), ctx
+		},
+	}
+}
+
 // orMorphism is the union, vice intersection, of a path and the current iterator.
 func orMorphism(p *Path) morphism {
 	return morphism{
diff --git a/query/path/path.go b/query/path/path.go
index f10a577..3814224 100644
--- a/query/path/path.go
+++ b/query/path/path.go
@@ -316,6 +316,13 @@ func (p *Path) And(path *Path) *Path {
 	return np
 }
 
+// Optional adds an optional path to evaluate. This path will only contribute to tags and won't change iteration results.
+func (p *Path) Optional(path *Path) *Path {
+	np := p.clone()
+	np.stack = append(np.stack, andOptMorphism(path.Reverse()))
+	return np
+}
+
 // Or updates the current Path to represent the nodes that match either the
 // current Path so far, or the given Path.
 func (p *Path) Or(path *Path) *Path {
@@ -428,6 +435,13 @@ func (p *Path) SaveOptionalReverse(via interface{}, tag string) *Path {
 	return np
 }
 
+// HasPath limits the paths to be ones where the current nodes have a given subpath.
+func (p *Path) HasPath(p2 *Path) *Path {
+	np := p.clone()
+	np.stack = append(np.stack, hasPathMorphism(p2.Reverse()))
+	return np
+}
+
 // Has limits the paths to be ones where the current nodes have some linkage
 // to some known node.
 func (p *Path) Has(via interface{}, nodes ...quad.Value) *Path {


Test patch:
diff --git a/query/path/pathtest/pathtest.go b/query/path/pathtest/pathtest.go
index 03dcc3d..78d6120 100644
--- a/query/path/pathtest/pathtest.go
+++ b/query/path/pathtest/pathtest.go
@@ -72,7 +72,7 @@ func runTopLevel(qs graph.QuadStore, path *Path, opt bool) ([]quad.Value, error)
 	return pb.Paths(false).AllValues(qs)
 }
 
-func runTag(qs graph.QuadStore, path *Path, tag string, opt bool) ([]quad.Value, error) {
+func runTag(qs graph.QuadStore, path *Path, tag string, opt, keepEmpty bool) ([]quad.Value, error) {
 	var out []quad.Value
 	pb := path.Iterate(context.TODO())
 	if !opt {
@@ -81,6 +81,8 @@ func runTag(qs graph.QuadStore, path *Path, tag string, opt bool) ([]quad.Value,
 	err := pb.Paths(true).TagEach(func(tags map[string]graph.Ref) {
 		if t, ok := tags[tag]; ok {
 			out = append(out, qs.NameOf(t))
+		} else if keepEmpty {
+			out = append(out, vEmpty)
 		}
 	})
 	return out, err
@@ -106,11 +108,14 @@ type test struct {
 	expectAlt [][]quad.Value
 	tag       string
 	unsorted  bool
+	empty     bool // do not skip empty tags
 }
 
 // Define morphisms without a QuadStore
 
 const (
+	vEmpty = quad.String("")
+
 	vFollows   = quad.IRI("follows")
 	vAre       = quad.IRI("are")
 	vStatus    = quad.IRI("status")
@@ -274,6 +279,11 @@ func testSet(qs graph.QuadStore) []test {
 			}),
 			expect: []quad.Value{vBob, vDani, vEmily, vFred},
 		},
+		{
+			message: "has path",
+			path:    StartPath(qs).HasPath(StartMorphism().Out(vStatus).Is(vCool)),
+			expect:  []quad.Value{vGreg, vDani, vBob},
+		},
 		{
 			message: "string prefix",
 			path: StartPath(qs).Filters(shape.Wildcard{
@@ -501,6 +511,13 @@ func testSet(qs graph.QuadStore) []test {
 			unsorted: true,
 			skip:     true, // TODO(dennwc): optimize Order in And properly
 		},
+		{
+			message: "optional path",
+			path:    StartPath(qs, vBob, vDani, vFred).Optional(StartMorphism().Save(vStatus, "status")),
+			tag:     "status",
+			empty:   true,
+			expect:  []quad.Value{vEmpty, vCool, vCool},
+		},
 	}
 }
 
@@ -532,7 +549,7 @@ func RunTestMorphisms(t *testing.T, fnc testutil.DatabaseFunc) {
 				if test.tag == "" {
 					got, err = runTopLevel(qs, test.path, opt)
 				} else {
-					got, err = runTag(qs, test.path, test.tag, opt)
+					got, err = runTag(qs, test.path, test.tag, opt, test.empty)
 				}
 				dt := time.Since(start)
 				if err != nil {