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