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 "fmt" 19 "strconv" 20 "strings" 21 22 "github.com/cayleygraph/cayley/graph" 23 "github.com/cayleygraph/cayley/graph/iterator" 24 "github.com/cayleygraph/cayley/quad" 25) 26 27const QuadStoreType = "memstore" 28 29func init() { 30 graph.RegisterQuadStore(QuadStoreType, graph.QuadStoreRegistration{ 31 NewFunc: func(string, graph.Options) (graph.QuadStore, error) { 32 return newQuadStore(), nil 33 }, 34 UpgradeFunc: nil, 35 InitFunc: nil, 36 IsPersistent: false, 37 }) 38} 39 40type bnode int64 41 42func (n bnode) Key() interface{} { return n } 43 44type qprim struct { 45 p *primitive 46} 47 48func (n qprim) Key() interface{} { return n.p.ID } 49 50var _ quad.Writer = (*QuadStore)(nil) 51 52func cmp(a, b int64) int { 53 return int(a - b) 54} 55 56type QuadDirectionIndex struct { 57 index [4]map[int64]*Tree 58} 59 60func NewQuadDirectionIndex() QuadDirectionIndex { 61 return QuadDirectionIndex{[...]map[int64]*Tree{ 62 quad.Subject - 1: make(map[int64]*Tree), 63 quad.Predicate - 1: make(map[int64]*Tree), 64 quad.Object - 1: make(map[int64]*Tree), 65 quad.Label - 1: make(map[int64]*Tree), 66 }} 67} 68 69func (qdi QuadDirectionIndex) Tree(d quad.Direction, id int64) *Tree { 70 if d < quad.Subject || d > quad.Label { 71 panic("illegal direction") 72 } 73 tree, ok := qdi.index[d-1][id] 74 if !ok { 75 tree = TreeNew(cmp) 76 qdi.index[d-1][id] = tree 77 } 78 return tree 79} 80 81func (qdi QuadDirectionIndex) Get(d quad.Direction, id int64) (*Tree, bool) { 82 if d < quad.Subject || d > quad.Label { 83 panic("illegal direction") 84 } 85 tree, ok := qdi.index[d-1][id] 86 return tree, ok 87} 88 89type primitive struct { 90 ID int64 91 Quad internalQuad 92 Value quad.Value 93 refs int 94} 95 96type internalQuad struct { 97 S, P, O, L int64 98} 99 100func (q internalQuad) Zero() bool { 101 return q == (internalQuad{}) 102} 103 104func (q *internalQuad) SetDir(d quad.Direction, n int64) { 105 switch d { 106 case quad.Subject: 107 q.S = n 108 case quad.Predicate: 109 q.P = n 110 case quad.Object: 111 q.O = n 112 case quad.Label: 113 q.L = n 114 default: 115 panic(fmt.Errorf("unknown dir: %v", d)) 116 } 117} 118func (q internalQuad) Dir(d quad.Direction) int64 { 119 var n int64 120 switch d { 121 case quad.Subject: 122 n = q.S 123 case quad.Predicate: 124 n = q.P 125 case quad.Object: 126 n = q.O 127 case quad.Label: 128 n = q.L 129 } 130 return n 131} 132 133type QuadStore struct { 134 last int64 135 // TODO: string -> quad.Value once Raw -> typed resolution is unnecessary 136 vals map[string]int64 137 quads map[internalQuad]int64 138 prim map[int64]*primitive 139 all []*primitive // might not be sorted by id 140 reading bool // someone else might be reading "all" slice - next insert/delete should clone it 141 index QuadDirectionIndex 142 horizon int64 // used only to assign ids to tx 143 // vip_index map[string]map[int64]map[string]map[int64]*b.Tree 144} 145 146// New creates a new in-memory quad store and loads provided quads. 147func New(quads ...quad.Quad) *QuadStore { 148 qs := newQuadStore() 149 for _, q := range quads { 150 qs.AddQuad(q) 151 } 152 return qs 153} 154 155func newQuadStore() *QuadStore { 156 return &QuadStore{ 157 vals: make(map[string]int64), 158 quads: make(map[internalQuad]int64), 159 prim: make(map[int64]*primitive), 160 index: NewQuadDirectionIndex(), 161 } 162} 163 164func (qs *QuadStore) cloneAll() []*primitive { 165 qs.reading = true 166 return qs.all 167} 168 169func (qs *QuadStore) addPrimitive(p *primitive) int64 { 170 qs.last++ 171 id := qs.last 172 p.ID = id 173 p.refs = 1 174 qs.appendPrimitive(p) 175 return id 176} 177 178func (qs *QuadStore) appendPrimitive(p *primitive) { 179 qs.prim[p.ID] = p 180 if !qs.reading { 181 qs.all = append(qs.all, p) 182 } else { 183 n := len(qs.all) 184 qs.all = append(qs.all[:n:n], p) // reallocate slice 185 qs.reading = false // this is a new slice 186 } 187} 188 189const internalBNodePrefix = "memnode" 190 191func (qs *QuadStore) resolveVal(v quad.Value, add bool) (int64, bool) { 192 if v == nil { 193 return 0, false 194 } 195 if n, ok := v.(quad.BNode); ok && strings.HasPrefix(string(n), internalBNodePrefix) { 196 n = n[len(internalBNodePrefix):] 197 id, err := strconv.ParseInt(string(n), 10, 64) 198 if err == nil && id != 0 { 199 if p, ok := qs.prim[id]; ok || !add { 200 if add { 201 p.refs++ 202 } 203 return id, ok 204 } 205 qs.appendPrimitive(&primitive{ID: id, refs: 1}) 206 return id, true 207 } 208 } 209 vs := v.String() 210 if id, exists := qs.vals[vs]; exists || !add { 211 if exists && add { 212 qs.prim[id].refs++ 213 } 214 return id, exists 215 } 216 id := qs.addPrimitive(&primitive{Value: v}) 217 qs.vals[vs] = id 218 return id, true 219} 220 221func (qs *QuadStore) resolveQuad(q quad.Quad, add bool) (internalQuad, bool) { 222 var p internalQuad 223 for dir := quad.Subject; dir <= quad.Label; dir++ { 224 v := q.Get(dir) 225 if v == nil { 226 continue 227 } 228 if vid, _ := qs.resolveVal(v, add); vid != 0 { 229 p.SetDir(dir, vid) 230 } else if !add { 231 return internalQuad{}, false 232 } 233 } 234 return p, true 235} 236 237func (qs *QuadStore) lookupVal(id int64) quad.Value { 238 pv := qs.prim[id] 239 if pv == nil || pv.Value == nil { 240 return quad.BNode(internalBNodePrefix + strconv.FormatInt(id, 10)) 241 } 242 return pv.Value 243} 244 245func (qs *QuadStore) lookupQuadDirs(p internalQuad) quad.Quad { 246 var q quad.Quad 247 for dir := quad.Subject; dir <= quad.Label; dir++ { 248 vid := p.Dir(dir) 249 if vid == 0 { 250 continue 251 } 252 v := qs.lookupVal(vid) 253 q.Set(dir, v) 254 } 255 return q 256} 257 258// AddNode adds a blank node (with no value) to quad store. It returns an id of the node. 259func (qs *QuadStore) AddBNode() int64 { 260 return qs.addPrimitive(&primitive{}) 261} 262 263// AddNode adds a value to quad store. It returns an id of the value. 264// False is returned as a second parameter if value exists already. 265func (qs *QuadStore) AddValue(v quad.Value) (int64, bool) { 266 id, exists := qs.resolveVal(v, true) 267 return id, !exists 268} 269 270func (qs *QuadStore) indexesForQuad(q internalQuad) []*Tree { 271 trees := make([]*Tree, 0, 4) 272 for dir := quad.Subject; dir <= quad.Label; dir++ { 273 v := q.Dir(dir) 274 if v == 0 { 275 continue 276 } 277 trees = append(trees, qs.index.Tree(dir, v)) 278 } 279 return trees 280} 281 282// AddQuad adds a quad to quad store. It returns an id of the quad. 283// False is returned as a second parameter if quad exists already. 284func (qs *QuadStore) AddQuad(q quad.Quad) (int64, bool) { 285 p, _ := qs.resolveQuad(q, true) 286 if id := qs.quads[p]; id != 0 { 287 return id, false 288 } 289 pr := &primitive{Quad: p} 290 id := qs.addPrimitive(pr) 291 qs.quads[p] = id 292 for _, t := range qs.indexesForQuad(p) { 293 t.Set(id, pr) 294 } 295 // TODO(barakmich): Add VIP indexing 296 return id, true 297} 298 299// WriteQuad adds a quad to quad store. 300// 301// Deprecated: use AddQuad instead. 302func (qs *QuadStore) WriteQuad(q quad.Quad) error { 303 qs.AddQuad(q) 304 return nil 305} 306 307func (qs *QuadStore) deleteQuadNodes(q internalQuad) { 308 for dir := quad.Subject; dir <= quad.Label; dir++ { 309 id := q.Dir(dir) 310 if id == 0 { 311 continue 312 } 313 if p := qs.prim[id]; p != nil { 314 p.refs-- 315 if p.refs < 0 { 316 panic("remove of deleted node") 317 } else if p.refs == 0 { 318 qs.Delete(id) 319 } 320 } 321 } 322} 323func (qs *QuadStore) Delete(id int64) bool { 324 p := qs.prim[id] 325 if p == nil { 326 return false 327 } 328 // remove from value index 329 if p.Value != nil { 330 delete(qs.vals, p.Value.String()) 331 } 332 // remove from quad indexes 333 for _, t := range qs.indexesForQuad(p.Quad) { 334 t.Delete(id) 335 } 336 delete(qs.quads, p.Quad) 337 // remove primitive 338 delete(qs.prim, id) 339 di := -1 340 for i, p2 := range qs.all { 341 if p == p2 { 342 di = i 343 break 344 } 345 } 346 if di >= 0 { 347 if !qs.reading { 348 qs.all = append(qs.all[:di], qs.all[di+1:]...) 349 } else { 350 all := make([]*primitive, 0, len(qs.all)-1) 351 all = append(all, qs.all[:di]...) 352 all = append(all, qs.all[di+1:]...) 353 qs.all = all 354 qs.reading = false // this is a new slice 355 } 356 } 357 qs.deleteQuadNodes(p.Quad) 358 return true 359} 360 361func (qs *QuadStore) findQuad(q quad.Quad) (int64, internalQuad, bool) { 362 p, ok := qs.resolveQuad(q, false) 363 if !ok { 364 return 0, p, false 365 } 366 id := qs.quads[p] 367 return id, p, id != 0 368} 369 370func (qs *QuadStore) ApplyDeltas(deltas []graph.Delta, ignoreOpts graph.IgnoreOpts) error { 371 // Precheck the whole transaction (if required) 372 if !ignoreOpts.IgnoreDup || !ignoreOpts.IgnoreMissing { 373 for _, d := range deltas { 374 switch d.Action { 375 case graph.Add: 376 if !ignoreOpts.IgnoreDup { 377 if _, _, ok := qs.findQuad(d.Quad); ok { 378 return &graph.DeltaError{Delta: d, Err: graph.ErrQuadExists} 379 } 380 } 381 case graph.Delete: 382 if !ignoreOpts.IgnoreMissing { 383 if _, _, ok := qs.findQuad(d.Quad); !ok { 384 return &graph.DeltaError{Delta: d, Err: graph.ErrQuadNotExist} 385 } 386 } 387 default: 388 return &graph.DeltaError{Delta: d, Err: graph.ErrInvalidAction} 389 } 390 } 391 } 392 393 for _, d := range deltas { 394 switch d.Action { 395 case graph.Add: 396 qs.AddQuad(d.Quad) 397 case graph.Delete: 398 if id, _, ok := qs.findQuad(d.Quad); ok { 399 qs.Delete(id) 400 } 401 default: 402 // TODO: ideally we should rollback it 403 return &graph.DeltaError{Delta: d, Err: graph.ErrInvalidAction} 404 } 405 } 406 qs.horizon++ 407 return nil 408} 409 410func asID(v graph.Value) (int64, bool) { 411 switch v := v.(type) { 412 case bnode: 413 return int64(v), true 414 case qprim: 415 return v.p.ID, true 416 default: 417 return 0, false 418 } 419} 420 421func (qs *QuadStore) quad(v graph.Value) (q internalQuad, ok bool) { 422 switch v := v.(type) { 423 case bnode: 424 p := qs.prim[int64(v)] 425 if p == nil { 426 return 427 } 428 q = p.Quad 429 case qprim: 430 q = v.p.Quad 431 default: 432 return internalQuad{}, false 433 } 434 return q, !q.Zero() 435} 436 437func (qs *QuadStore) Quad(index graph.Value) quad.Quad { 438 q, ok := qs.quad(index) 439 if !ok { 440 return quad.Quad{} 441 } 442 return qs.lookupQuadDirs(q) 443} 444 445func (qs *QuadStore) QuadIterator(d quad.Direction, value graph.Value) graph.Iterator { 446 id, ok := asID(value) 447 if !ok { 448 return iterator.NewNull() 449 } 450 index, ok := qs.index.Get(d, id) 451 if ok && index.Len() != 0 { 452 return NewIterator(index, qs, d, id) 453 } 454 return iterator.NewNull() 455} 456 457func (qs *QuadStore) Size() int64 { 458 return int64(len(qs.prim)) 459} 460 461func (qs *QuadStore) ValueOf(name quad.Value) graph.Value { 462 if name == nil { 463 return nil 464 } 465 id := qs.vals[name.String()] 466 if id == 0 { 467 return nil 468 } 469 return bnode(id) 470} 471 472func (qs *QuadStore) NameOf(v graph.Value) quad.Value { 473 if v == nil { 474 return nil 475 } else if v, ok := v.(graph.PreFetchedValue); ok { 476 return v.NameOf() 477 } 478 n, ok := asID(v) 479 if !ok { 480 return nil 481 } 482 if _, ok = qs.prim[n]; !ok { 483 return nil 484 } 485 return qs.lookupVal(n) 486} 487 488func (qs *QuadStore) QuadsAllIterator() graph.Iterator { 489 return newAllIterator(qs, false, qs.last) 490} 491 492func (qs *QuadStore) QuadDirection(val graph.Value, d quad.Direction) graph.Value { 493 q, ok := qs.quad(val) 494 if !ok { 495 return nil 496 } 497 id := q.Dir(d) 498 if id == 0 { 499 return nil 500 } 501 return bnode(id) 502} 503 504func (qs *QuadStore) NodesAllIterator() graph.Iterator { 505 return newAllIterator(qs, true, qs.last) 506} 507 508func (qs *QuadStore) Close() error { return nil } 509