1// Copyright 2014 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 memstore
16
17import (
18	"context"
19	"reflect"
20	"sort"
21	"testing"
22
23	"github.com/cayleygraph/cayley/graph"
24	"github.com/cayleygraph/cayley/graph/graphtest"
25	"github.com/cayleygraph/cayley/graph/iterator"
26	"github.com/cayleygraph/cayley/quad"
27	"github.com/cayleygraph/cayley/writer"
28	"github.com/stretchr/testify/require"
29)
30
31// This is a simple test graph.
32//
33//    +---+                        +---+
34//    | A |-------               ->| F |<--
35//    +---+       \------>+---+-/  +---+   \--+---+
36//                 ------>|#B#|      |        | E |
37//    +---+-------/      >+---+      |        +---+
38//    | C |             /            v
39//    +---+           -/           +---+
40//      ----    +---+/             |#G#|
41//          \-->|#D#|------------->+---+
42//              +---+
43//
44var simpleGraph = []quad.Quad{
45	quad.MakeRaw("A", "follows", "B", ""),
46	quad.MakeRaw("C", "follows", "B", ""),
47	quad.MakeRaw("C", "follows", "D", ""),
48	quad.MakeRaw("D", "follows", "B", ""),
49	quad.MakeRaw("B", "follows", "F", ""),
50	quad.MakeRaw("F", "follows", "G", ""),
51	quad.MakeRaw("D", "follows", "G", ""),
52	quad.MakeRaw("E", "follows", "F", ""),
53	quad.MakeRaw("B", "status", "cool", "status_graph"),
54	quad.MakeRaw("D", "status", "cool", "status_graph"),
55	quad.MakeRaw("G", "status", "cool", "status_graph"),
56}
57
58func makeTestStore(data []quad.Quad) (*QuadStore, graph.QuadWriter, []pair) {
59	seen := make(map[string]struct{})
60	qs := New()
61	var (
62		val int64
63		ind []pair
64	)
65	writer, _ := writer.NewSingleReplication(qs, nil)
66	for _, t := range data {
67		for _, dir := range quad.Directions {
68			qp := t.GetString(dir)
69			if _, ok := seen[qp]; !ok && qp != "" {
70				val++
71				ind = append(ind, pair{qp, val})
72				seen[qp] = struct{}{}
73			}
74		}
75
76		writer.AddQuad(t)
77		val++
78	}
79	return qs, writer, ind
80}
81
82func TestMemstore(t *testing.T) {
83	graphtest.TestAll(t, func(t testing.TB) (graph.QuadStore, graph.Options, func()) {
84		return New(), nil, func() {}
85	}, &graphtest.Config{
86		AlwaysRunIntegration: true,
87	})
88}
89
90type pair struct {
91	query string
92	value int64
93}
94
95func TestMemstoreValueOf(t *testing.T) {
96	qs, _, index := makeTestStore(simpleGraph)
97	require.Equal(t, int64(22), qs.Size())
98
99	for _, test := range index {
100		v := qs.ValueOf(quad.Raw(test.query))
101		switch v := v.(type) {
102		default:
103			t.Errorf("ValueOf(%q) returned unexpected type, got:%T expected int64", test.query, v)
104		case bnode:
105			require.Equal(t, test.value, int64(v))
106		}
107	}
108}
109
110func TestIteratorsAndNextResultOrderA(t *testing.T) {
111	ctx := context.TODO()
112	qs, _, _ := makeTestStore(simpleGraph)
113
114	fixed := iterator.NewFixed()
115	fixed.Add(qs.ValueOf(quad.Raw("C")))
116
117	fixed2 := iterator.NewFixed()
118	fixed2.Add(qs.ValueOf(quad.Raw("follows")))
119
120	all := qs.NodesAllIterator()
121
122	innerAnd := iterator.NewAnd(qs,
123		iterator.NewLinksTo(qs, fixed2, quad.Predicate),
124		iterator.NewLinksTo(qs, all, quad.Object),
125	)
126
127	hasa := iterator.NewHasA(qs, innerAnd, quad.Subject)
128	outerAnd := iterator.NewAnd(qs, fixed, hasa)
129
130	if !outerAnd.Next(ctx) {
131		t.Error("Expected one matching subtree")
132	}
133	val := outerAnd.Result()
134	if qs.NameOf(val) != quad.Raw("C") {
135		t.Errorf("Matching subtree should be %s, got %s", "barak", qs.NameOf(val))
136	}
137
138	var (
139		got    []string
140		expect = []string{"B", "D"}
141	)
142	for {
143		got = append(got, quad.ToString(qs.NameOf(all.Result())))
144		if !outerAnd.NextPath(ctx) {
145			break
146		}
147	}
148	sort.Strings(got)
149
150	if !reflect.DeepEqual(got, expect) {
151		t.Errorf("Unexpected result, got:%q expect:%q", got, expect)
152	}
153
154	if outerAnd.Next(ctx) {
155		t.Error("More than one possible top level output?")
156	}
157}
158
159func TestLinksToOptimization(t *testing.T) {
160	qs, _, _ := makeTestStore(simpleGraph)
161
162	fixed := iterator.NewFixed()
163	fixed.Add(qs.ValueOf(quad.Raw("cool")))
164
165	lto := iterator.NewLinksTo(qs, fixed, quad.Object)
166	lto.Tagger().Add("foo")
167
168	newIt, changed := lto.Optimize()
169	if !changed {
170		t.Error("Iterator didn't change")
171	}
172	if _, ok := newIt.(*Iterator); !ok {
173		t.Fatal("Didn't swap out to LLRB")
174	}
175
176	v := newIt.(*Iterator)
177	vClone := v.Clone()
178	origDesc := graph.DescribeIterator(v)
179	cloneDesc := graph.DescribeIterator(vClone)
180	origDesc.UID, cloneDesc.UID = 0, 0 // We are more strict now, so fake UID equality.
181	if !reflect.DeepEqual(cloneDesc, origDesc) {
182		t.Fatalf("Unexpected iterator description.\ngot: %#v\nexpect: %#v", cloneDesc, origDesc)
183	}
184	vt := vClone.Tagger()
185	if len(vt.Tags()) < 1 || vt.Tags()[0] != "foo" {
186		t.Fatal("Tag on LinksTo did not persist")
187	}
188}
189
190func TestRemoveQuad(t *testing.T) {
191	ctx := context.TODO()
192	qs, w, _ := makeTestStore(simpleGraph)
193
194	err := w.RemoveQuad(quad.Make(
195		"E",
196		"follows",
197		"F",
198		nil,
199	))
200
201	if err != nil {
202		t.Error("Couldn't remove quad", err)
203	}
204
205	fixed := iterator.NewFixed()
206	fixed.Add(qs.ValueOf(quad.Raw("E")))
207
208	fixed2 := iterator.NewFixed()
209	fixed2.Add(qs.ValueOf(quad.Raw("follows")))
210
211	innerAnd := iterator.NewAnd(qs,
212		iterator.NewLinksTo(qs, fixed, quad.Subject),
213		iterator.NewLinksTo(qs, fixed2, quad.Predicate),
214	)
215
216	hasa := iterator.NewHasA(qs, innerAnd, quad.Object)
217
218	newIt, _ := hasa.Optimize()
219	if newIt.Next(ctx) {
220		t.Error("E should not have any followers.")
221	}
222}
223
224func TestTransaction(t *testing.T) {
225	qs, w, _ := makeTestStore(simpleGraph)
226	size := qs.Size()
227
228	tx := graph.NewTransaction()
229	tx.AddQuad(quad.Make(
230		"E",
231		"follows",
232		"G",
233		nil))
234	tx.RemoveQuad(quad.Make(
235		"Non",
236		"existent",
237		"quad",
238		nil))
239
240	err := w.ApplyTransaction(tx)
241	if err == nil {
242		t.Error("Able to remove a non-existent quad")
243	}
244	if size != qs.Size() {
245		t.Error("Appended a new quad in a failed transaction")
246	}
247}
248