Repository: cayleygraph/cayley (go)

Issue:
graphql ko @opt
using the latest docker image, with query:

```
{
  nodes {
    id,
    status @opt
  }
}
```

I get:
```json
{
	"data": {
		"nodes": null
	}
}
```
while without @opt it is ok
```json
{
	"data": {
		"nodes": [
			{
				"id": "bob",
				"status": "cool_person"
			},
			{
				"id": "dani",
				"status": "cool_person"
			},
			{
				"id": "greg",
				"status": "cool_person"
			},
			{
				"id": "emily",
				"status": "smart_person"
			},
			{
				"id": "greg",
				"status": "smart_person"
			}
		]
	}
}
```

Pull request:
Fix optimization of optional intersections
This change removes `shape.Optional` and merges it into `shape.IntersectOpt`. This allows to properly optimize queries that contain only optional branches.

Fixes #740

<!-- 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/776)
<!-- Reviewable:end -->


Patch:
diff --git a/graph/shape/path.go b/graph/shape/path.go
index 25dc586..c3676bb 100644
--- a/graph/shape/path.go
+++ b/graph/shape/path.go
@@ -21,6 +21,31 @@ func IntersectShapes(s1, s2 Shape) Shape {
 	return Intersect{s1, s2}
 }
 
+func IntersectOptional(s, opt Shape) Shape {
+	var optional []Shape
+	switch opt := opt.(type) {
+	case Intersect:
+		optional = []Shape(opt)
+	case IntersectOpt:
+		optional = make([]Shape, 0, len(opt.Sub)+len(opt.Opt))
+		optional = append(optional, opt.Sub...)
+		optional = append(optional, opt.Opt...)
+	default:
+		optional = []Shape{opt}
+	}
+	if len(optional) == 0 {
+		return s
+	}
+	switch s := s.(type) {
+	case Intersect:
+		return IntersectOpt{Sub: s, Opt: optional}
+	case IntersectOpt:
+		s.Opt = append(s.Opt, optional...)
+		return s
+	}
+	return IntersectOpt{Sub: Intersect{s}, Opt: optional}
+}
+
 func UnionShapes(s1, s2 Shape) Union {
 	if s1, ok := s1.(Union); ok {
 		if s2, ok := s2.(Union); ok {
@@ -148,7 +173,7 @@ func SaveViaLabels(from, via, labels Shape, tag string, rev, opt bool) Shape {
 		Dir:   start,
 	}
 	if opt {
-		save = Optional{save}
+		return IntersectOptional(from, save)
 	}
 	return IntersectShapes(from, save)
 }
diff --git a/graph/shape/shape.go b/graph/shape/shape.go
index 9e1e052..b2a44dc 100644
--- a/graph/shape/shape.go
+++ b/graph/shape/shape.go
@@ -945,10 +945,12 @@ func (s Intersect) Optimize(r Optimizer) (sout Shape, opt bool) {
 		return ns, true
 	}
 	var (
-		onlyAll = true   // contains only AllNodes shapes
-		fixed   []Fixed  // we will collect all Fixed, and will place it as a first iterator
-		tags    []string // if we find a Save inside, we will push it outside of Intersect
-		quads   Quads    // also, collect all quad filters into a single set
+		onlyAll  = true // contains only AllNodes shapes
+		hasAll   = false
+		fixed    []Fixed  // we will collect all Fixed, and will place it as a first iterator
+		tags     []string // if we find a Save inside, we will push it outside of Intersect
+		quads    Quads    // also, collect all quad filters into a single set
+		optional []Shape
 	)
 	remove := func(i *int, optimized bool) {
 		realloc()
@@ -964,16 +966,10 @@ func (s Intersect) Optimize(r Optimizer) (sout Shape, opt bool) {
 	for i := 0; i < len(s); i++ {
 		c := s[i]
 		switch c := c.(type) {
-		case AllNodes: // remove AllNodes - it's useless
+		case AllNodes: // remove AllNodes - it's useless in the intersection
 			remove(&i, true)
-			// prevent resetting of onlyAll
-			continue
-		case Optional:
-			if IsNull(c.From) {
-				remove(&i, true)
-				// prevent resetting of onlyAll
-				continue
-			}
+			hasAll = true
+			continue // prevent resetting of onlyAll
 		case Quads: // merge all quad filters
 			remove(&i, false)
 			if quads == nil {
@@ -988,6 +984,10 @@ func (s Intersect) Optimize(r Optimizer) (sout Shape, opt bool) {
 		case Intersect: // merge with other Intersects
 			remove(&i, true)
 			s = append(s, c...)
+		case IntersectOpt: // merge with IntersectOpt
+			remove(&i, true)
+			s = append(s, c.Sub...)
+			optional = append(optional, c.Opt...)
 		case Save: // push Save outside of Intersect
 			realloc()
 			opt = true
@@ -1012,6 +1012,23 @@ func (s Intersect) Optimize(r Optimizer) (sout Shape, opt bool) {
 			opt = opt || topt
 		}()
 	}
+	if len(optional) != 0 {
+		// don't forget to add optional paths
+		defer func() {
+			if IsNull(sout) {
+				return
+			}
+			out := IntersectOpt{Opt: optional}
+			if so, ok := sout.(Intersect); ok {
+				out.Sub = so
+			} else {
+				out.Sub = Intersect{sout}
+			}
+			var topt bool
+			sout, topt = out.Optimize(r)
+			opt = opt || topt
+		}()
+	}
 	if quads != nil {
 		nq, qopt := quads.Optimize(r)
 		if IsNull(nq) {
@@ -1087,6 +1104,9 @@ func (s Intersect) Optimize(r Optimizer) (sout Shape, opt bool) {
 		s = ns
 	}
 	if len(s) == 0 {
+		if hasAll {
+			return AllNodes{}, true
+		}
 		return nil, true
 	} else if len(s) == 1 {
 		return s[0], true
@@ -1095,6 +1115,100 @@ func (s Intersect) Optimize(r Optimizer) (sout Shape, opt bool) {
 	return s, opt
 }
 
+// IntersectOpt is like Intersect but it also joins optional query shapes to the main query.
+type IntersectOpt struct {
+	Sub Intersect
+	Opt []Shape
+}
+
+func (s IntersectOpt) BuildIterator(qs graph.QuadStore) graph.Iterator {
+	if len(s.Sub) == 0 && len(s.Opt) == 0 {
+		return iterator.NewNull()
+	}
+	if len(s.Sub) == 0 {
+		if len(s.Opt) == 0 {
+			return iterator.NewNull()
+		}
+		s.Sub = Intersect{AllNodes{}}
+	}
+	sub := make([]graph.Iterator, 0, len(s.Sub)+len(s.Opt))
+	for _, c := range s.Sub {
+		sub = append(sub, c.BuildIterator(qs))
+	}
+	for _, c := range s.Opt {
+		sub = append(sub, iterator.NewOptional(c.BuildIterator(qs)))
+	}
+	if len(sub) == 1 {
+		return sub[0]
+	}
+	return iterator.NewAnd(qs, sub...)
+}
+
+func (s IntersectOpt) Optimize(r Optimizer) (_ Shape, opt bool) {
+	// optimize optional shapes first, reallocate if necessary
+	newSlice := false
+	realloc := func() {
+		opt = true
+		if newSlice {
+			return
+		}
+		newSlice = true
+		s.Opt = append([]Shape{}, s.Opt...)
+	}
+	for i := 0; i < len(s.Opt); i++ {
+		o := s.Opt[i]
+		if IsNull(o) {
+			realloc()
+			s.Opt = append(s.Opt[:i], s.Opt[i+1:]...)
+			i--
+			continue
+		}
+		o, opt2 := o.Optimize(r)
+		if !opt2 {
+			continue
+		}
+		realloc()
+		if IsNull(o) {
+			s.Opt = append(s.Opt[:i], s.Opt[i+1:]...)
+			i--
+		} else {
+			s.Opt[i] = o
+		}
+	}
+	if len(s.Opt) == 0 {
+		// no optional - replace with a regular intersection
+		si, _ := s.Sub.Optimize(r)
+		return si, true
+	}
+	if len(s.Sub) == 0 {
+		// force at least All to be in the intersection
+		s.Sub = Intersect{AllNodes{}}
+		opt = true
+	} else {
+		sub, opt2 := s.Sub.Optimize(r)
+		if IsNull(sub) {
+			return nil, true
+		}
+		opt = opt || opt2
+		switch sub := sub.(type) {
+		case Intersect:
+			s.Sub = sub
+		case IntersectOpt:
+			sub.Opt = append(sub.Opt)
+			s = sub
+			opt = true
+		default:
+			s.Sub = Intersect{sub}
+			opt = true
+		}
+	}
+	if r != nil {
+		ns, nopt := r.OptimizeShape(s)
+		return ns, opt || nopt
+	}
+	return s, opt
+}
+
 // Union joins results of multiple queries together. It does not make results unique.
 type Union []Shape
 
@@ -1272,34 +1386,8 @@ func (s Save) Optimize(r Optimizer) (Shape, bool) {
 	s.From, opt = s.From.Optimize(r)
 	if len(s.Tags) == 0 {
 		return s.From, true
-	}
-	if r != nil {
-		ns, nopt := r.OptimizeShape(s)
-		return ns, opt || nopt
-	}
-	return s, opt
-}
-
-// Optional makes a query execution optional. The query can only produce tagged results,
-// since it's value is not used to compute intersection.
-type Optional struct {
-	From Shape
-}
-
-func (s Optional) BuildIterator(qs graph.QuadStore) graph.Iterator {
-	if IsNull(s.From) {
-		return iterator.NewOptional(iterator.NewNull())
-	}
-	return iterator.NewOptional(s.From.BuildIterator(qs))
-}
-func (s Optional) Optimize(r Optimizer) (Shape, bool) {
-	if IsNull(s.From) {
-		return s, false
-	}
-	var opt bool
-	s.From, opt = s.From.Optimize(r)
-	if IsNull(s.From) {
-		return s, opt
+	} else if IsNull(s.From) {
+		return nil, true
 	}
 	if r != nil {
 		ns, nopt := r.OptimizeShape(s)


Test patch:
diff --git a/graph/shape/shape_test.go b/graph/shape/shape_test.go
index 463bbf8..f25a7be 100644
--- a/graph/shape/shape_test.go
+++ b/graph/shape/shape_test.go
@@ -129,6 +129,12 @@ var optimizeCases = []struct {
 			From: AllNodes{},
 		},
 	},
+	{
+		name:   "intersect tagged all",
+		from:   Intersect{Save{Tags: []string{"id"}, From: AllNodes{}}},
+		opt:    true,
+		expect: Save{Tags: []string{"id"}, From: AllNodes{}},
+	},
 	{
 		name: "intersect quads and lookup resolution",
 		from: Intersect{
@@ -256,14 +262,16 @@ var optimizeCases = []struct {
 	},
 	{ // remove optional empty set from intersect
 		name: "remove optional empty set",
-		from: Intersect{
-			AllNodes{},
-			Save{From: AllNodes{}, Tags: []string{"all"}},
-			Fixed{intVal(2)},
-			Optional{Save{
-				From: emptySet(),
-				Tags: []string{"name"}},
+		from: IntersectOpt{
+			Sub: Intersect{
+				AllNodes{},
+				Save{From: AllNodes{}, Tags: []string{"all"}},
+				Fixed{intVal(2)},
 			},
+			Opt: []Shape{Save{
+				From: emptySet(),
+				Tags: []string{"name"},
+			}},
 		},
 		opt: true,
 		expect: Save{
@@ -309,6 +317,33 @@ var optimizeCases = []struct {
 			},
 		},
 	},
+	{
+		name: "all optional",
+		from: Intersect{IntersectOpt{
+			Sub: Intersect{
+				Save{Tags: []string{"id"}, From: AllNodes{}},
+			},
+			Opt: []Shape{
+				NodesFrom{Dir: quad.Subject, Quads: Quads{
+					QuadFilter{Dir: quad.Object, Values: Save{Tags: []string{"status"}, From: AllNodes{}}},
+					QuadFilter{Dir: quad.Predicate, Values: Fixed{intVal(1)}},
+				}},
+			},
+		}},
+		opt: true,
+		expect: Save{
+			Tags: []string{"id"},
+			From: IntersectOpt{
+				Sub: Intersect{AllNodes{}},
+				Opt: []Shape{
+					QuadsAction{Result: quad.Subject,
+						Save:   map[quad.Direction][]string{quad.Object: {"status"}},
+						Filter: map[quad.Direction]graph.Value{quad.Predicate: intVal(1)},
+					},
+				},
+			},
+		},
+	},
 }
 
 func TestOptimize(t *testing.T) {
diff --git a/query/graphql/graphql_test.go b/query/graphql/graphql_test.go
index 54656f7..93462a2 100644
--- a/query/graphql/graphql_test.go
+++ b/query/graphql/graphql_test.go
@@ -95,10 +95,12 @@ func TestParse(t *testing.T) {
 	}
 }
 
+type M = map[string]interface{}
+
 var casesExecute = []struct {
 	name   string
 	query  string
-	result map[string]interface{}
+	result M
 }{
 	{
 		"cool people and friends",
@@ -114,12 +116,12 @@ var casesExecute = []struct {
     }
   }
 }`,
-		map[string]interface{}{
-			"me": []map[string]interface{}{
+		M{
+			"me": []M{
 				{
 					"id":      quad.IRI("bob"),
 					"follows": nil,
-					"followed": []map[string]interface{}{
+					"followed": []M{
 						{ValueKey: quad.IRI("alice")},
 						{ValueKey: quad.IRI("charlie")},
 						{ValueKey: quad.IRI("dani")},
@@ -127,7 +129,7 @@ var casesExecute = []struct {
 				},
 				{
 					"id": quad.IRI("dani"),
-					"follows": []map[string]interface{}{
+					"follows": []M{
 						{
 							ValueKey: quad.IRI("bob"),
 							"status": quad.String("cool_person"),
@@ -140,14 +142,14 @@ var casesExecute = []struct {
 							},
 						},
 					},
-					"followed": map[string]interface{}{
+					"followed": M{
 						ValueKey: quad.IRI("charlie"),
 					},
 				},
 				{
 					"id":      quad.IRI("greg"),
 					"follows": nil,
-					"followed": []map[string]interface{}{
+					"followed": []M{
 						{ValueKey: quad.IRI("dani")},
 						{ValueKey: quad.IRI("fred")},
 					},
@@ -165,10 +167,10 @@ var casesExecute = []struct {
     }
   }
 }`,
-		map[string]interface{}{
-			"me": map[string]interface{}{
+		M{
+			"me": M{
 				"id": quad.IRI("dani"),
-				"follows": map[string]interface{}{
+				"follows": M{
 					ValueKey: quad.IRI("bob"),
 				},
 			},
@@ -182,8 +184,8 @@ var casesExecute = []struct {
     status @label(v: <smart_graph>)
   }
 }`,
-		map[string]interface{}{
-			"me": []map[string]interface{}{
+		M{
+			"me": []M{
 				{
 					"id":     quad.IRI("emily"),
 					"status": quad.String("smart_person"),
@@ -204,12 +206,12 @@ var casesExecute = []struct {
     follows {*}
   }
 }`,
-		map[string]interface{}{
-			"me": []map[string]interface{}{
+		M{
+			"me": []M{
 				{
 					"id":     quad.IRI("emily"),
 					"status": quad.String("smart_person"),
-					"follows": map[string]interface{}{
+					"follows": M{
 						"id":      quad.IRI("fred"),
 						"follows": quad.IRI("greg"),
 					},
@@ -236,8 +238,8 @@ var casesExecute = []struct {
     }
   }
 }`,
-		map[string]interface{}{
-			"me": map[string]interface{}{
+		M{
+			"me": M{
 				"id":     quad.IRI("fred"),
 				"fof":    quad.IRI("dani"),
 				"friend": quad.IRI("greg"),
@@ -248,6 +250,36 @@ var casesExecute = []struct {
 			},
 		},
 	},
+	{
+		"all optional",
+		`{
+  nodes {
+    id,
+    status @opt
+  }
+}`,
+		M{
+			"nodes": []M{
+				{"id": quad.IRI("alice")},
+				{"id": quad.IRI("follows")},
+				{"id": quad.IRI("bob"), "status": quad.String("cool_person")},
+				{"id": quad.IRI("fred")},
+				{"id": quad.IRI("status")},
+				{"id": quad.String("cool_person")},
+				{"id": quad.IRI("charlie")},
+				{"id": quad.IRI("dani"), "status": quad.String("cool_person")},
+				{"id": quad.IRI("greg"), "status": []quad.Value{
+					quad.String("cool_person"),
+					quad.String("smart_person"),
+				}},
+				{"id": quad.IRI("emily"), "status": quad.String("smart_person")},
+				{"id": quad.IRI("predicates")},
+				{"id": quad.IRI("are")},
+				{"id": quad.String("smart_person")},
+				{"id": quad.IRI("smart_graph")},
+			},
+		},
+	},
 }
 
 func toJson(o interface{}) string {