/
shape.go
1303 lines (1228 loc) · 30.5 KB
/
shape.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
package shape
import (
"reflect"
"regexp"
"strings"
"github.com/cayleygraph/cayley/clog"
"github.com/cayleygraph/cayley/graph"
"github.com/cayleygraph/cayley/graph/iterator"
"github.com/cayleygraph/cayley/quad"
)
// Shape represent a query tree shape.
type Shape interface {
// BuildIterator constructs an iterator tree from a given shapes and binds it to QuadStore.
BuildIterator(qs graph.QuadStore) graph.Iterator
// Optimize runs an optimization pass over a query shape.
//
// It returns a bool that indicates if shape was replaced and should always return a copy of shape in this case.
// In case no optimizations were made, it returns the same unmodified shape.
//
// If Optimizer is specified, it will be used instead of default optimizations.
Optimize(r Optimizer) (Shape, bool)
}
type Optimizer interface {
OptimizeShape(s Shape) (Shape, bool)
}
// Composite shape can be simplified to a tree of more basic shapes.
type Composite interface {
Simplify() Shape
}
// WalkFunc is used to visit all shapes in the tree.
// If false is returned, branch will not be traversed further.
type WalkFunc func(Shape) bool
type resolveValues struct {
qs graph.QuadStore
}
func (r resolveValues) OptimizeShape(s Shape) (Shape, bool) {
if l, ok := s.(Lookup); ok {
return l.resolve(r.qs), true
}
return s, false
}
// Optimize applies generic optimizations for the tree.
// If quad store is specified it will also resolve Lookups and apply any specific optimizations.
// Should not be used with Simplify - it will fold query to a compact form again.
func Optimize(s Shape, qs graph.QuadStore) (Shape, bool) {
if s == nil {
return nil, false
}
qs = graph.Unwrap(qs)
var opt bool
if qs != nil {
// resolve all lookups earlier
s, opt = s.Optimize(resolveValues{qs: qs})
}
if s == nil {
return Null{}, true
}
// generic optimizations
var opt1 bool
s, opt1 = s.Optimize(nil)
if s == nil {
return Null{}, true
}
opt = opt || opt1
// apply quadstore-specific optimizations
if so, ok := qs.(Optimizer); ok && s != nil {
var opt2 bool
s, opt2 = s.Optimize(so)
opt = opt || opt2
}
if s == nil {
return Null{}, true
}
return s, opt
}
var rtShape = reflect.TypeOf((*Shape)(nil)).Elem()
// Walk calls provided function for each shape in the tree.
func Walk(s Shape, fnc WalkFunc) {
if s == nil {
return
}
if !fnc(s) {
return
}
walkReflect(reflect.ValueOf(s), fnc)
}
func walkReflect(rv reflect.Value, fnc WalkFunc) {
rt := rv.Type()
switch rv.Kind() {
case reflect.Slice:
if rt.Elem().ConvertibleTo(rtShape) {
// all element are shapes - call function on each of them
for i := 0; i < rv.Len(); i++ {
Walk(rv.Index(i).Interface().(Shape), fnc)
}
} else {
// elements are not shapes, but might contain them
for i := 0; i < rv.Len(); i++ {
walkReflect(rv.Index(i), fnc)
}
}
case reflect.Map:
keys := rv.MapKeys()
if rt.Elem().ConvertibleTo(rtShape) {
// all element are shapes - call function on each of them
for _, k := range keys {
Walk(rv.MapIndex(k).Interface().(Shape), fnc)
}
} else {
// elements are not shapes, but might contain them
for _, k := range keys {
walkReflect(rv.MapIndex(k), fnc)
}
}
case reflect.Struct:
// visit all fields
for i := 0; i < rt.NumField(); i++ {
f := rt.Field(i)
// if field is of shape type - call function on it
// we skip anonymous fields because they were already visited as part of the parent
if !f.Anonymous && f.Type.ConvertibleTo(rtShape) {
Walk(rv.Field(i).Interface().(Shape), fnc)
continue
}
// it might be a struct/map/slice field, so we need to go deeper
walkReflect(rv.Field(i), fnc)
}
}
}
// InternalQuad is an internal representation of quad index in QuadStore.
type InternalQuad struct {
Subject graph.Value
Predicate graph.Value
Object graph.Value
Label graph.Value
}
// Get returns a specified direction of the quad.
func (q InternalQuad) Get(d quad.Direction) graph.Value {
switch d {
case quad.Subject:
return q.Subject
case quad.Predicate:
return q.Predicate
case quad.Object:
return q.Object
case quad.Label:
return q.Label
default:
return nil
}
}
// Set assigns a specified direction of the quad to a given value.
func (q InternalQuad) Set(d quad.Direction, v graph.Value) {
switch d {
case quad.Subject:
q.Subject = v
case quad.Predicate:
q.Predicate = v
case quad.Object:
q.Object = v
case quad.Label:
q.Label = v
default:
panic(d)
}
}
// QuadIndexer is an optional interface for quad stores that keep an index of quad directions.
//
// It is used to optimize shapes based on stats from these indexes.
type QuadIndexer interface {
// SizeOfIndex returns a size of a quad index with given constraints.
SizeOfIndex(c map[quad.Direction]graph.Value) (int64, bool)
// LookupQuadIndex finds a quad that matches a given constraint.
// It returns false if quad was not found, or there are multiple quads matching constraint.
LookupQuadIndex(c map[quad.Direction]graph.Value) (InternalQuad, bool)
}
// IsNull safely checks if shape represents an empty set. It accounts for both Null and nil.
func IsNull(s Shape) bool {
_, ok := s.(Null)
return s == nil || ok
}
// BuildIterator optimizes the shape and builds a corresponding iterator tree.
func BuildIterator(qs graph.QuadStore, s Shape) graph.Iterator {
qs = graph.Unwrap(qs)
if s != nil {
if clog.V(2) {
clog.Infof("shape: %#v", s)
}
s, _ = Optimize(s, qs)
if clog.V(2) {
clog.Infof("optimized: %#v", s)
}
}
if IsNull(s) {
return iterator.NewNull()
}
return s.BuildIterator(qs)
}
// Null represent an empty set. Mostly used as a safe alias for nil shape.
type Null struct{}
func (Null) BuildIterator(qs graph.QuadStore) graph.Iterator {
return iterator.NewNull()
}
func (s Null) Optimize(r Optimizer) (Shape, bool) {
if r != nil {
return r.OptimizeShape(s)
}
return nil, true
}
// AllNodes represents all nodes in QuadStore.
type AllNodes struct{}
func (s AllNodes) BuildIterator(qs graph.QuadStore) graph.Iterator {
return qs.NodesAllIterator()
}
func (s AllNodes) Optimize(r Optimizer) (Shape, bool) {
if r != nil {
return r.OptimizeShape(s)
}
return s, false
}
// Except excludes a set on nodes from a source. If source is nil, AllNodes is assumed.
type Except struct {
Exclude Shape // nodes to exclude
From Shape // a set of all nodes to exclude from; nil means AllNodes
}
func (s Except) BuildIterator(qs graph.QuadStore) graph.Iterator {
var all graph.Iterator
if s.From != nil {
all = s.From.BuildIterator(qs)
} else {
all = qs.NodesAllIterator()
}
if IsNull(s.Exclude) {
return all
}
return iterator.NewNot(s.Exclude.BuildIterator(qs), all)
}
func (s Except) Optimize(r Optimizer) (Shape, bool) {
var opt bool
s.Exclude, opt = s.Exclude.Optimize(r)
if s.From != nil {
var opta bool
s.From, opta = s.From.Optimize(r)
opt = opt || opta
}
if r != nil {
ns, nopt := r.OptimizeShape(s)
return ns, opt || nopt
}
if IsNull(s.Exclude) {
return AllNodes{}, true
} else if _, ok := s.Exclude.(AllNodes); ok {
return nil, true
}
return s, opt
}
// ValueFilter is an interface for iterator wrappers that can filter node values.
type ValueFilter interface {
BuildIterator(qs graph.QuadStore, it graph.Iterator) graph.Iterator
}
// Filter filters all values from the source using a list of operations.
type Filter struct {
From Shape // source that will be filtered
Filters []ValueFilter // filters to apply
}
func (s Filter) BuildIterator(qs graph.QuadStore) graph.Iterator {
if IsNull(s.From) {
return iterator.NewNull()
}
it := s.From.BuildIterator(qs)
for _, f := range s.Filters {
it = f.BuildIterator(qs, it)
}
return it
}
func (s Filter) Optimize(r Optimizer) (Shape, bool) {
if IsNull(s.From) {
return nil, true
}
var opt bool
s.From, opt = s.From.Optimize(r)
if r != nil {
ns, nopt := r.OptimizeShape(s)
return ns, opt || nopt
}
if IsNull(s.From) {
return nil, true
} else if len(s.Filters) == 0 {
return s.From, true
}
return s, opt
}
var _ ValueFilter = Comparison{}
// Comparison is a value filter that evaluates binary operation in reference to a fixed value.
type Comparison struct {
Op iterator.Operator
Val quad.Value
}
func (f Comparison) BuildIterator(qs graph.QuadStore, it graph.Iterator) graph.Iterator {
return iterator.NewComparison(it, f.Op, f.Val, qs)
}
var _ ValueFilter = Regexp{}
// Regexp filters values using regular expression.
//
// Since regexp patterns can not be optimized in most cases, Wildcard should be used if possible.
type Regexp struct {
Re *regexp.Regexp
Refs bool // allow to match IRIs
}
func (f Regexp) BuildIterator(qs graph.QuadStore, it graph.Iterator) graph.Iterator {
rit := iterator.NewRegex(it, f.Re, qs)
rit.AllowRefs(f.Refs)
return rit
}
var _ ValueFilter = Wildcard{}
// Wildcard is a filter for string patterns.
//
// % - zero or more characters
// ? - exactly one character
type Wildcard struct {
Pattern string // allowed wildcards are: % and ?
}
// Regexp returns an analog regexp pattern in format accepted by Go stdlib (RE2).
func (f Wildcard) Regexp() string {
const any = `%`
// escape all meta-characters in pattern string
pattern := regexp.QuoteMeta(f.Pattern)
// if the pattern is anchored, add regexp analog for it
if !strings.HasPrefix(pattern, any) {
pattern = "^" + pattern
} else {
pattern = strings.TrimPrefix(pattern, any)
}
if !strings.HasSuffix(pattern, any) {
pattern = pattern + "$"
} else {
pattern = strings.TrimSuffix(pattern, any)
}
// replace wildcards
pattern = strings.NewReplacer(
any, `.*`,
`\?`, `.`,
).Replace(pattern)
return pattern
}
func (f Wildcard) BuildIterator(qs graph.QuadStore, it graph.Iterator) graph.Iterator {
if f.Pattern == "" {
return iterator.NewNull()
} else if strings.Trim(f.Pattern, "%") == "" {
return it
}
re, err := regexp.Compile(f.Regexp())
if err != nil {
return iterator.NewError(err)
}
rit := iterator.NewRegex(it, re, qs)
rit.AllowRefs(true)
return rit
}
// Count returns a count of objects in source as a single value. It always returns exactly one value.
type Count struct {
Values Shape
}
func (s Count) BuildIterator(qs graph.QuadStore) graph.Iterator {
var it graph.Iterator
if IsNull(s.Values) {
it = iterator.NewNull()
} else {
it = s.Values.BuildIterator(qs)
}
return iterator.NewCount(it, qs)
}
func (s Count) Optimize(r Optimizer) (Shape, bool) {
if IsNull(s.Values) {
return Fixed{graph.PreFetched(quad.Int(0))}, true
}
var opt bool
s.Values, opt = s.Values.Optimize(r)
if IsNull(s.Values) {
return Fixed{graph.PreFetched(quad.Int(0))}, true
}
if r != nil {
ns, nopt := r.OptimizeShape(s)
return ns, opt || nopt
}
// TODO: ask QS to estimate size - if it exact, then we can use it
return s, opt
}
// QuadFilter is a constraint used to filter quads that have a certain set of values on a given direction.
// Analog of LinksTo iterator.
type QuadFilter struct {
Dir quad.Direction
Values Shape
}
// buildIterator is not exposed to force to use Quads and group filters together.
func (s QuadFilter) buildIterator(qs graph.QuadStore) graph.Iterator {
if s.Values == nil {
return iterator.NewNull()
} else if v, ok := One(s.Values); ok {
return qs.QuadIterator(s.Dir, v)
}
if s.Dir == quad.Any {
panic("direction is not set")
}
sub := s.Values.BuildIterator(qs)
return iterator.NewLinksTo(qs, sub, s.Dir)
}
// Quads is a selector of quads with a given set of node constraints. Empty or nil Quads is equivalent to AllQuads.
// Equivalent to And(AllQuads,LinksTo*) iterator tree.
type Quads []QuadFilter
func (s *Quads) Intersect(q ...QuadFilter) {
*s = append(*s, q...)
}
func (s Quads) BuildIterator(qs graph.QuadStore) graph.Iterator {
if len(s) == 0 {
return qs.QuadsAllIterator()
}
its := make([]graph.Iterator, 0, len(s))
for _, f := range s {
its = append(its, f.buildIterator(qs))
}
if len(its) == 1 {
return its[0]
}
return iterator.NewAnd(qs, its...)
}
func (s Quads) Optimize(r Optimizer) (Shape, bool) {
var opt bool
sw := 0
realloc := func() {
if !opt {
opt = true
nq := make(Quads, len(s))
copy(nq, s)
s = nq
}
}
// TODO: multiple constraints on the same dir -> merge as Intersect on Values of this dir
for i := 0; i < len(s); i++ {
f := s[i]
if f.Values == nil {
return nil, true
}
v, ok := f.Values.Optimize(r)
if v == nil {
return nil, true
}
if ok {
realloc()
s[i].Values = v
}
switch s[i].Values.(type) {
case Fixed:
realloc()
s[sw], s[i] = s[i], s[sw]
sw++
}
}
if r != nil {
ns, nopt := r.OptimizeShape(s)
return ns, opt || nopt
}
return s, opt
}
// NodesFrom extracts nodes on a given direction from source quads. Similar to HasA iterator.
type NodesFrom struct {
Dir quad.Direction
Quads Shape
}
func (s NodesFrom) BuildIterator(qs graph.QuadStore) graph.Iterator {
if IsNull(s.Quads) {
return iterator.NewNull()
}
sub := s.Quads.BuildIterator(qs)
if s.Dir == quad.Any {
panic("direction is not set")
}
return iterator.NewHasA(qs, sub, s.Dir)
}
func (s NodesFrom) Optimize(r Optimizer) (Shape, bool) {
if IsNull(s.Quads) {
return nil, true
}
var opt bool
s.Quads, opt = s.Quads.Optimize(r)
if r != nil {
// ignore default optimizations
ns, nopt := r.OptimizeShape(s)
return ns, opt || nopt
}
q, ok := s.Quads.(Quads)
if !ok {
return s, opt
}
// HasA(x, LinksTo(x, y)) == y
if len(q) == 1 && q[0].Dir == s.Dir {
return q[0].Values, true
}
// collect all fixed tags and push them up the tree
var (
tags map[string]graph.Value
nquad Quads
)
for i, f := range q {
if ft, ok := f.Values.(FixedTags); ok {
if tags == nil {
// allocate map and clone quad filters
tags = make(map[string]graph.Value)
nquad = make([]QuadFilter, len(q))
copy(nquad, q)
q = nquad
}
q[i].Values = ft.On
for k, v := range ft.Tags {
tags[k] = v
}
}
}
if tags != nil {
// re-run optimization without fixed tags
ns, _ := NodesFrom{Dir: s.Dir, Quads: q}.Optimize(r)
return FixedTags{On: ns, Tags: tags}, true
}
var (
// if quad filter contains one fixed value, it will be added to the map
filt map[quad.Direction]graph.Value
// if we see a Save from AllNodes, we will write it here, since it's a Save on quad direction
save map[quad.Direction][]string
// how many filters are recognized
n int
)
for _, f := range q {
if v, ok := One(f.Values); ok {
if filt == nil {
filt = make(map[quad.Direction]graph.Value)
}
if _, ok := filt[f.Dir]; ok {
return s, opt // just to be safe
}
filt[f.Dir] = v
n++
} else if sv, ok := f.Values.(Save); ok {
if _, ok = sv.From.(AllNodes); ok {
if save == nil {
save = make(map[quad.Direction][]string)
}
save[f.Dir] = append(save[f.Dir], sv.Tags...)
n++
}
}
}
if n == len(q) {
// if all filters were recognized we can merge this tree as a single iterator with multiple
// constraints and multiple save commands over the same set of quads
ns, _ := QuadsAction{
Result: s.Dir, // this is still a HasA, remember?
Filter: filt,
Save: save,
}.Optimize(r)
return ns, true
}
// TODO
return s, opt
}
var _ Composite = QuadsAction{}
// QuadsAction represents a set of actions that can be done to a set of quads in a single scan pass.
// It filters quads according to Filter constraints (equivalent of LinksTo), tags directions using tags in Save field
// and returns a specified quad direction as result of the iterator (equivalent of HasA).
// Optionally, Size field may be set to indicate an approximate number of quads that will be returned by this query.
type QuadsAction struct {
Size int64 // approximate size; zero means undefined
Result quad.Direction
Save map[quad.Direction][]string
Filter map[quad.Direction]graph.Value
}
func (s *QuadsAction) SetFilter(d quad.Direction, v graph.Value) {
if s.Filter == nil {
s.Filter = make(map[quad.Direction]graph.Value)
}
s.Filter[d] = v
}
func (s QuadsAction) Clone() QuadsAction {
if n := len(s.Save); n != 0 {
s2 := make(map[quad.Direction][]string, n)
for k, v := range s.Save {
s2[k] = v
}
s.Save = s2
} else {
s.Save = nil
}
if n := len(s.Filter); n != 0 {
f2 := make(map[quad.Direction]graph.Value, n)
for k, v := range s.Filter {
f2[k] = v
}
s.Filter = f2
} else {
s.Filter = nil
}
return s
}
func (s QuadsAction) simplify() NodesFrom {
q := make(Quads, 0, len(s.Save)+len(s.Filter))
for dir, val := range s.Filter {
q = append(q, QuadFilter{Dir: dir, Values: Fixed{val}})
}
for dir, tags := range s.Save {
q = append(q, QuadFilter{Dir: dir, Values: Save{From: AllNodes{}, Tags: tags}})
}
return NodesFrom{Dir: s.Result, Quads: q}
}
func (s QuadsAction) Simplify() Shape {
return s.simplify()
}
func (s QuadsAction) BuildIterator(qs graph.QuadStore) graph.Iterator {
h := s.simplify()
return h.BuildIterator(qs)
}
func (s QuadsAction) Optimize(r Optimizer) (Shape, bool) {
if r != nil {
return r.OptimizeShape(s)
}
// if optimizer has stats for quad indexes we can use them to do more
ind, ok := r.(QuadIndexer)
if !ok {
return s, false
}
if s.Size > 0 { // already optimized; specific for QuadIndexer optimization
return s, false
}
sz, exact := ind.SizeOfIndex(s.Filter)
if !exact {
return s, false
}
s.Size = sz // computing size is already an optimization
if sz == 0 {
// nothing here, collapse the tree
return nil, true
} else if sz == 1 {
// only one quad matches this set of filters
// try to load it from quad store, do all operations and bake result as a fixed node/tags
if q, ok := ind.LookupQuadIndex(s.Filter); ok {
fx := Fixed{q.Get(s.Result)}
if len(s.Save) == 0 {
return fx, true
}
ft := FixedTags{On: fx, Tags: make(map[string]graph.Value)}
for d, tags := range s.Save {
for _, t := range tags {
ft.Tags[t] = q.Get(d)
}
}
return ft, true
}
}
if sz < int64(MaterializeThreshold) {
// if this set is small enough - materialize it
return Materialize{Values: s, Size: int(sz)}, true
}
return s, true
}
// One checks if Shape represents a single fixed value and returns it.
func One(s Shape) (graph.Value, bool) {
switch s := s.(type) {
case Fixed:
if len(s) == 1 {
return s[0], true
}
}
return nil, false
}
// Fixed is a static set of nodes. Defined only for a particular QuadStore.
type Fixed []graph.Value
func (s *Fixed) Add(v ...graph.Value) {
*s = append(*s, v...)
}
func (s Fixed) BuildIterator(qs graph.QuadStore) graph.Iterator {
it := iterator.NewFixed()
for _, v := range s {
if _, ok := v.(quad.Value); ok {
panic("quad value in fixed iterator")
}
it.Add(v)
}
return it
}
func (s Fixed) Optimize(r Optimizer) (Shape, bool) {
if len(s) == 0 {
return nil, true
}
if r != nil {
return r.OptimizeShape(s)
}
return s, false
}
// FixedTags adds a set of fixed tag values to query results. It does not affect query execution in any other way.
//
// Shape implementations should try to push these objects up the tree during optimization process.
type FixedTags struct {
Tags map[string]graph.Value
On Shape
}
func (s FixedTags) BuildIterator(qs graph.QuadStore) graph.Iterator {
if IsNull(s.On) {
return iterator.NewNull()
}
it := s.On.BuildIterator(qs)
tg := it.Tagger()
for k, v := range s.Tags {
tg.AddFixed(k, v)
}
return it
}
func (s FixedTags) Optimize(r Optimizer) (Shape, bool) {
if IsNull(s.On) {
return nil, true
}
var opt bool
s.On, opt = s.On.Optimize(r)
if len(s.Tags) == 0 {
return s.On, true
} else if s2, ok := s.On.(FixedTags); ok {
tags := make(map[string]graph.Value, len(s.Tags)+len(s2.Tags))
for k, v := range s.Tags {
tags[k] = v
}
for k, v := range s2.Tags {
tags[k] = v
}
s, opt = FixedTags{On: s2.On, Tags: tags}, true
}
if r != nil {
ns, nopt := r.OptimizeShape(s)
return ns, opt || nopt
}
return s, opt
}
// Lookup is a static set of values that must be resolved to nodes by QuadStore.
type Lookup []quad.Value
func (s *Lookup) Add(v ...quad.Value) {
*s = append(*s, v...)
}
var _ valueResolver = graph.QuadStore(nil)
type valueResolver interface {
ValueOf(v quad.Value) graph.Value
}
func (s Lookup) resolve(qs valueResolver) Shape {
// TODO: check if QS supports batch lookup
vals := make([]graph.Value, 0, len(s))
for _, v := range s {
if gv := qs.ValueOf(v); gv != nil {
vals = append(vals, gv)
}
}
if len(vals) == 0 {
return nil
}
return Fixed(vals)
}
func (s Lookup) BuildIterator(qs graph.QuadStore) graph.Iterator {
f := s.resolve(qs)
if IsNull(f) {
return iterator.NewNull()
}
return f.BuildIterator(qs)
}
func (s Lookup) Optimize(r Optimizer) (Shape, bool) {
if r == nil {
return s, false
}
ns, opt := r.OptimizeShape(s)
if opt {
return ns, true
}
if qs, ok := r.(valueResolver); ok {
ns, opt = s.resolve(qs), true
}
return ns, opt
}
var MaterializeThreshold = 100 // TODO: tune
// Materialize loads results of sub-query into memory during execution to speedup iteration.
type Materialize struct {
Size int // approximate size; zero means undefined
Values Shape
}
func (s Materialize) BuildIterator(qs graph.QuadStore) graph.Iterator {
if IsNull(s.Values) {
return iterator.NewNull()
}
it := s.Values.BuildIterator(qs)
return iterator.NewMaterializeWithSize(it, int64(s.Size))
}
func (s Materialize) Optimize(r Optimizer) (Shape, bool) {
if IsNull(s.Values) {
return nil, true
}
var opt bool
s.Values, opt = s.Values.Optimize(r)
if r != nil {
ns, nopt := r.OptimizeShape(s)
return ns, opt || nopt
}
return s, opt
}
func clearFixedTags(arr []Shape) ([]Shape, map[string]graph.Value) {
var tags map[string]graph.Value
for i := 0; i < len(arr); i++ {
if ft, ok := arr[i].(FixedTags); ok {
if tags == nil {
tags = make(map[string]graph.Value)
na := make([]Shape, len(arr))
copy(na, arr)
arr = na
}
arr[i] = ft.On
for k, v := range ft.Tags {
tags[k] = v
}
}
}
return arr, tags
}
// Intersect computes an intersection of nodes between multiple queries. Similar to And iterator.
type Intersect []Shape
func (s Intersect) BuildIterator(qs graph.QuadStore) graph.Iterator {
if len(s) == 0 {
return iterator.NewNull()
}
sub := make([]graph.Iterator, 0, len(s))
for _, c := range s {
sub = append(sub, c.BuildIterator(qs))
}
if len(sub) == 1 {
return sub[0]
}
return iterator.NewAnd(qs, sub...)
}
func (s Intersect) Optimize(r Optimizer) (sout Shape, opt bool) {
if len(s) == 0 {
return nil, true
}
// function to lazily reallocate a copy of Intersect slice
realloc := func() {
if !opt {
arr := make(Intersect, len(s))
copy(arr, s)
s = arr
}
}
// optimize sub-iterators, return empty set if Null is found
for i := 0; i < len(s); i++ {
c := s[i]
if IsNull(c) {
return nil, true
}
v, ok := c.Optimize(r)
if !ok {
continue
}
realloc()
opt = true
if IsNull(v) {
return nil, true
}
s[i] = v
}
if r != nil {
ns, nopt := r.OptimizeShape(s)
return ns, opt || nopt
}
if arr, ft := clearFixedTags([]Shape(s)); ft != nil {
ns, _ := FixedTags{On: Intersect(arr), Tags: ft}.Optimize(r)
return ns, true
}
var (
onlyAll = true // contains only AllNodes shapes
fixed []Fixed // we will collect all Fixed, and will place it as a first iterator
tags []string // if we find a Save inside, we will push it outside of Intersect
quads Quads // also, collect all quad filters into a single set
)
remove := func(i *int, optimized bool) {
realloc()
if optimized {
opt = true
}
v := *i
s = append(s[:v], s[v+1:]...)
v--
*i = v
}
// second pass - remove AllNodes, merge Quads, collect Fixed, collect Save, merge Intersects
for i := 0; i < len(s); i++ {
c := s[i]
switch c := c.(type) {
case AllNodes: // remove AllNodes - it's useless
remove(&i, true)
// prevent resetting of onlyAll
continue
case Optional:
if IsNull(c.From) {
remove(&i, true)
// prevent resetting of onlyAll
continue
}
case Quads: // merge all quad filters
remove(&i, false)
if quads == nil {
quads = c[:len(c):len(c)]
} else {
opt = true
quads = append(quads, c...)
}
case Fixed: // collect all Fixed sets
remove(&i, true)
fixed = append(fixed, c)
case Intersect: // merge with other Intersects
remove(&i, true)
s = append(s, c...)
case Save: // push Save outside of Intersect
realloc()
opt = true
tags = append(tags, c.Tags...)
s[i] = c.From
i--
}
onlyAll = false
}
if onlyAll {
return AllNodes{}, true
}
if len(tags) != 0 {
// don't forget to move Save outside of Intersect at the end
defer func() {
if IsNull(sout) {