Repository: cayleygraph/cayley
Pull request #916 (2020-02-01 18:25:52)

LinkedQL: Fix recursive matching for Match step
 - Brake down code of Match step
 - Add documentation for logic applied
 - Support recursive matching of nested objects

<!-- 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/916)
<!-- Reviewable:end -->



Patch:
diff --git a/query/linkedql/steps/match.go b/query/linkedql/steps/match.go
index da2bedf..94eff58 100644
--- a/query/linkedql/steps/match.go
+++ b/query/linkedql/steps/match.go
@@ -57,12 +57,43 @@ func (s *Match) BuildPath(qs graph.QuadStore, ns *voc.Namespaces) (*path.Path, e
 		return nil, err
 	}
 
-	// Group quads to subtrees
-	entities := make(map[quad.Value]map[quad.Value][]quad.Value)
-	for _, q := range quads {
+	return p.Follow(buildPatternPath(quads, ns)), nil
+}
+
+type entityProperties = map[quad.Value]map[quad.Value][]quad.Value
+
+func entityPropertiesToPath(entity quad.Value, entities entityProperties) *path.Path {
+	p := path.StartMorphism()
+	if iri, ok := entity.(quad.IRI); ok {
+		p = p.Is(iri)
+	}
+	for property, values := range entities[entity] {
+		for _, value := range values {
+			if _, ok := value.(quad.BNode); ok {
+				p = p.Out(property).Follow(entityPropertiesToPath(value, entities)).Back("")
+			} else {
+				p = p.Has(property, value)
+			}
+		}
+	}
+	return p
+}
+
+func groupEntities(pattern []quad.Quad, ns *voc.Namespaces) (entityProperties, map[quad.Value]struct{}) {
+	// referenced holds entities used as values for properties of other entities
+	referenced := make(map[quad.Value]struct{})
+
+	entities := make(entityProperties)
+
+	for _, q := range pattern {
 		entity := linkedql.AbsoluteValue(q.Subject, ns)
 		property := linkedql.AbsoluteValue(q.Predicate, ns)
 		value := linkedql.AbsoluteValue(q.Object, ns)
+
+		if _, ok := value.(quad.BNode); ok {
+			referenced[value] = struct{}{}
+		}
+
 		properties, ok := entities[entity]
 		if !ok {
 			properties = make(map[quad.Value][]quad.Value)
@@ -74,20 +105,25 @@ func (s *Match) BuildPath(qs graph.QuadStore, ns *voc.Namespaces) (*path.Path, e
 		properties[property] = append(properties[property], value)
 	}
 
-	for entity, properties := range entities {
-		if iri, ok := entity.(quad.IRI); ok {
-			p = p.Is(iri)
-		}
-		// FIXME(iddan): this currently flattens all nested objects, which is totally incorrect; recurse or limit allowed json-ld
-		for property, values := range properties {
-			p = p.Has(property, values...)
+	return entities, referenced
+}
+
+// buildPath for given pattern constructs a Path object
+func buildPatternPath(pattern []quad.Quad, ns *voc.Namespaces) *path.Path {
+	entities, referenced := groupEntities(pattern, ns)
+	p := path.StartMorphism()
+
+	for entity := range entities {
+		// Apply only on entities which are not referenced as values
+		if _, ok := referenced[entity]; !ok {
+			p = p.Follow(entityPropertiesToPath(entity, entities))
 		}
 	}
 
-	return p, nil
+	return p
 }
 
-func parsePattern(pattern linkedql.GraphPattern, ns *voc.Namespaces) ([]quad.Quad, error) {
+func contextualizePattern(pattern linkedql.GraphPattern, ns *voc.Namespaces) linkedql.GraphPattern {
 	context := make(map[string]interface{})
 	for _, namespace := range ns.List() {
 		context[namespace.Prefix] = namespace.Full
@@ -98,24 +134,44 @@ func parsePattern(pattern linkedql.GraphPattern, ns *voc.Namespaces) ([]quad.Qua
 	for key, value := range pattern {
 		patternClone[key] = value
 	}
-	reader := jsonld.NewReaderFromMap(patternClone)
-	quads, err := quad.ReadAll(reader)
-	if err != nil {
-		return nil, err
-	}
-	if id, ok := patternClone["@id"]; ok && len(quads) == 0 {
+	return pattern
+}
+
+func quadsFromMap(o interface{}) ([]quad.Quad, error) {
+	reader := jsonld.NewReaderFromMap(o)
+	return quad.ReadAll(reader)
+}
+
+func normalizeQuads(quads []quad.Quad, pattern linkedql.GraphPattern) ([]quad.Quad, error) {
+	if id, ok := pattern["@id"]; ok && len(quads) == 0 {
 		idString, ok := id.(string)
 		if !ok {
 			return nil, fmt.Errorf("Unexpected type for @id %T", idString)
 		}
 		quads = append(quads, makeSingleEntityQuad(quad.IRI(idString)))
 	}
+	return quads, nil
+}
+
+func parsePattern(pattern linkedql.GraphPattern, ns *voc.Namespaces) ([]quad.Quad, error) {
+	contextualizedPattern := contextualizePattern(pattern, ns)
+	quads, err := quadsFromMap(contextualizedPattern)
+	if err != nil {
+		return nil, err
+	}
+	quads, err = normalizeQuads(quads, contextualizedPattern)
+	if err != nil {
+		return nil, err
+	}
 	if len(quads) == 0 && len(pattern) != 0 {
 		return nil, fmt.Errorf("Pattern does not parse to any quad. `{}` is the only pattern allowed to not parse to any quad")
 	}
 	return quads, nil
 }
 
+// makeSingleEntityQuad creates a quad representing a propertyless entity. The
+// quad declares the entity is of type Resource, the base type of all entities
+// in RDF.
 func makeSingleEntityQuad(id quad.IRI) quad.Quad {
 	return quad.Quad{Subject: id, Predicate: quad.IRI(rdf.Type), Object: quad.IRI(rdfs.Resource)}
 }


Test patch:
diff --git a/query/linkedql/steps/match_test.go b/query/linkedql/steps/match_test.go
new file mode 100644
index 0000000..16ba906
--- /dev/null
+++ b/query/linkedql/steps/match_test.go
@@ -0,0 +1,103 @@
+package steps
+
+import (
+	"testing"
+
+	"github.com/cayleygraph/cayley/query/path"
+	"github.com/cayleygraph/quad"
+	"github.com/cayleygraph/quad/voc"
+	"github.com/stretchr/testify/require"
+)
+
+var (
+	ns      = "http://example.com/"
+	alice   = quad.IRI(ns + "alice")
+	likes   = quad.IRI(ns + "likes")
+	name    = quad.IRI(ns + "name")
+	bob     = quad.IRI(ns + "bob")
+	address = quad.IRI(ns + "address")
+	city    = quad.IRI(ns + "city")
+	street  = quad.IRI(ns + "street")
+	country = quad.IRI(ns + "country")
+)
+
+var patternTestCases = []struct {
+	name     string
+	pattern  map[string]interface{}
+	expected *path.Path
+}{
+	{
+		name:     "Empty Pattern",
+		pattern:  map[string]interface{}{},
+		expected: path.StartMorphism(),
+	},
+	{
+		name: "Single Entity",
+		pattern: map[string]interface{}{
+			"@id": string(alice),
+		},
+		expected: path.StartMorphism().Is(alice),
+	},
+	{
+		name: "Single Property Value",
+		pattern: map[string]interface{}{
+			string(likes): map[string]interface{}{"@id": string(bob)},
+		},
+		expected: path.StartMorphism().Has(likes, bob),
+	},
+	{
+		name: "Nested Structure",
+		pattern: map[string]interface{}{
+			string(address): map[string]interface{}{
+				string(street): "Lafayette",
+			},
+		},
+		expected: path.
+			StartMorphism().
+			Out(address).
+			Follow(
+				path.StartMorphism().
+					Has(street, quad.String("Lafayette")),
+			).
+			Back(""),
+	},
+	{
+		name: "Two Level Nested Structure",
+		pattern: map[string]interface{}{
+			string(address): map[string]interface{}{
+				string(country): map[string]interface{}{
+					string(name): "The United States of America",
+				},
+			},
+		},
+		expected: path.
+			StartMorphism().
+			Out(address).
+			Follow(
+				path.StartMorphism().
+					Out(country).
+					Follow(
+						path.StartMorphism().
+							Has(name, quad.String("The United States of America")),
+					).
+					Back(""),
+			).
+			Back(""),
+	},
+}
+
+func TestBuildPath(t *testing.T) {
+	for _, c := range patternTestCases {
+		t.Run(c.name, func(t *testing.T) {
+			ns := voc.Namespaces{}
+			quads, err := parsePattern(c.pattern, &ns)
+			require.NoError(t, err)
+			p := buildPatternPath(quads, &ns)
+			expectedShape := c.expected.Shape()
+			shape := p.Shape()
+			// TODO(iddan): replace with stable comparison. Currently, it breaks
+			// because order of properties is not guaranteed
+			require.Equal(t, expectedShape, shape)
+		})
+	}
+}
diff --git a/query/linkedql/steps/test-cases/match-exact.json b/query/linkedql/steps/test-cases/match-exact.json
new file mode 100644
index 0000000..ae01a86
--- /dev/null
+++ b/query/linkedql/steps/test-cases/match-exact.json
@@ -0,0 +1,26 @@
+{
+  "data": [
+    {
+      "@id": "http://example.com/alice",
+      "http://example.com/likes": [
+        {
+          "@id": "http://example.com/bob"
+        }
+      ]
+    }
+  ],
+  "query": {
+    "@context": {
+      "linkedql": "http://cayley.io/linkedql"
+    },
+    "@type": "linkedql:Match",
+    "linkedql:pattern": {
+      "@id": "http://example.com/alice"
+    }
+  },
+  "results": [
+    {
+      "@id": "http://example.com/alice"
+    }
+  ]
+}