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