1// Copyright 2015 The Cayley Authors. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package iterator_test
16
17import (
18	"context"
19	"reflect"
20	"sort"
21	"testing"
22
23	"github.com/cayleygraph/cayley/graph"
24	"github.com/cayleygraph/cayley/graph/graphmock"
25	. "github.com/cayleygraph/cayley/graph/iterator"
26	"github.com/cayleygraph/cayley/quad"
27)
28
29func singleHop(pred string) graph.ApplyMorphism {
30	return func(qs graph.QuadStore, it graph.Iterator) graph.Iterator {
31		fixed := NewFixed()
32		fixed.Add(graph.PreFetched(quad.Raw(pred)))
33		predlto := NewLinksTo(qs, fixed, quad.Predicate)
34		lto := NewLinksTo(qs, it.Clone(), quad.Subject)
35		and := NewAnd(qs)
36		and.AddSubIterator(lto)
37		and.AddSubIterator(predlto)
38		return NewHasA(qs, and, quad.Object)
39	}
40}
41
42var rec_test_qs = &graphmock.Store{
43	Data: []quad.Quad{
44		quad.MakeRaw("alice", "parent", "bob", ""),
45		quad.MakeRaw("bob", "parent", "charlie", ""),
46		quad.MakeRaw("charlie", "parent", "dani", ""),
47		quad.MakeRaw("charlie", "parent", "bob", ""),
48		quad.MakeRaw("dani", "parent", "emily", ""),
49		quad.MakeRaw("fred", "follows", "alice", ""),
50		quad.MakeRaw("greg", "follows", "alice", ""),
51	},
52}
53
54func TestRecursiveNext(t *testing.T) {
55	ctx := context.TODO()
56	qs := rec_test_qs
57	start := NewFixed()
58	start.Add(graph.PreFetched(quad.Raw("alice")))
59	r := NewRecursive(qs, start, singleHop("parent"), 0)
60	expected := []string{"bob", "charlie", "dani", "emily"}
61
62	var got []string
63	for r.Next(ctx) {
64		got = append(got, quad.ToString(qs.NameOf(r.Result())))
65	}
66	sort.Strings(expected)
67	sort.Strings(got)
68	if !reflect.DeepEqual(got, expected) {
69		t.Errorf("Failed to %s, got: %v, expected: %v", "check basic recursive iterator", got, expected)
70	}
71}
72
73func TestRecursiveContains(t *testing.T) {
74	ctx := context.TODO()
75	qs := rec_test_qs
76	start := NewFixed()
77	start.Add(graph.PreFetched(quad.Raw("alice")))
78	r := NewRecursive(qs, start, singleHop("parent"), 0)
79	values := []string{"charlie", "bob", "not"}
80	expected := []bool{true, true, false}
81
82	for i, v := range values {
83		ok := r.Contains(ctx, qs.ValueOf(quad.Raw(v)))
84		if expected[i] != ok {
85			t.Errorf("Failed to %s, value: %s, got: %v, expected: %v", "check basic recursive contains", v, ok, expected[i])
86		}
87	}
88}
89
90func TestRecursiveNextPath(t *testing.T) {
91	ctx := context.TODO()
92	qs := rec_test_qs
93	start := qs.NodesAllIterator()
94	start.Tagger().Add("person")
95	it := singleHop("follows")(qs, start)
96	and := NewAnd(qs)
97	and.AddSubIterator(it)
98	fixed := NewFixed()
99	fixed.Add(graph.PreFetched(quad.Raw("alice")))
100	and.AddSubIterator(fixed)
101	r := NewRecursive(qs, and, singleHop("parent"), 0)
102
103	expected := []string{"fred", "fred", "fred", "fred", "greg", "greg", "greg", "greg"}
104	var got []string
105	for r.Next(ctx) {
106		res := make(map[string]graph.Value)
107		r.TagResults(res)
108		got = append(got, quad.ToString(qs.NameOf(res["person"])))
109		for r.NextPath(ctx) {
110			res := make(map[string]graph.Value)
111			r.TagResults(res)
112			got = append(got, quad.ToString(qs.NameOf(res["person"])))
113		}
114	}
115	sort.Strings(expected)
116	sort.Strings(got)
117	if !reflect.DeepEqual(got, expected) {
118		t.Errorf("Failed to check NextPath, got: %v, expected: %v", got, expected)
119	}
120}
121