forked from cayleygraph/cayley
-
Notifications
You must be signed in to change notification settings - Fork 0
/
optional_iterator.go
156 lines (134 loc) · 4.17 KB
/
optional_iterator.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
// Copyright 2014 The Cayley Authors. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package iterator
// "Optional" is kind of odd. It's not an iterator in the strictest sense, but
// it's easier to implement as an iterator.
//
// Consider what it means. It means that we have a subconstraint which we do
// not want to constrain the query -- we just want it to return the matching
// subgraph if one matches at all. By analogy to regular expressions, it is the
// '?' operator.
//
// If it were a proper iterator of its own (and indeed, a reasonable refactor
// of this iterator would be to make it such) it would contain an all iterator
// -- all things in the graph. It matches everything (as does the regex "(a)?")
import (
"fmt"
"strings"
"github.com/google/cayley/graph"
)
// An optional iterator has the sub-constraint iterator we wish to be optional
// and whether the last check we received was true or false.
type Optional struct {
uid uint64
tags graph.Tagger
subIt graph.Iterator
lastCheck bool
result graph.Value
}
// Creates a new optional iterator.
func NewOptional(it graph.Iterator) *Optional {
return &Optional{
uid: NextUID(),
subIt: it,
}
}
func (it *Optional) UID() uint64 {
return it.uid
}
func (it *Optional) Reset() {
it.subIt.Reset()
it.lastCheck = false
}
func (it *Optional) Close() {
it.subIt.Close()
}
func (it *Optional) Tagger() *graph.Tagger {
return &it.tags
}
func (it *Optional) Clone() graph.Iterator {
out := NewOptional(it.subIt.Clone())
out.tags.CopyFrom(it)
return out
}
// DEPRECATED
func (it *Optional) ResultTree() *graph.ResultTree {
return graph.NewResultTree(it.Result())
}
func (it *Optional) Result() graph.Value {
return it.result
}
// An optional iterator only has a next result if, (a) last time we checked
// we had any results whatsoever, and (b) there was another subresult in our
// optional subbranch.
func (it *Optional) NextPath() bool {
if it.lastCheck {
return it.subIt.NextPath()
}
return false
}
// No subiterators.
func (it *Optional) SubIterators() []graph.Iterator {
return nil
}
// Contains() is the real hack of this iterator. It always returns true, regardless
// of whether the subiterator matched. But we keep track of whether the subiterator
// matched for results purposes.
func (it *Optional) Contains(val graph.Value) bool {
checked := it.subIt.Contains(val)
it.lastCheck = checked
it.result = val
return true
}
// If we failed the check, then the subiterator should not contribute to the result
// set. Otherwise, go ahead and tag it.
func (it *Optional) TagResults(dst map[string]graph.Value) {
if it.lastCheck == false {
return
}
it.subIt.TagResults(dst)
}
// Registers the optional iterator.
func (it *Optional) Type() graph.Type { return graph.Optional }
// Prints the optional and it's subiterator.
func (it *Optional) DebugString(indent int) string {
return fmt.Sprintf("%s(%s tags:%s\n%s)",
strings.Repeat(" ", indent),
it.Type(),
it.tags.Tags(),
it.subIt.DebugString(indent+4))
}
// There's nothing to optimize for an optional. Optimize the subiterator and
// potentially replace it.
func (it *Optional) Optimize() (graph.Iterator, bool) {
newSub, changed := it.subIt.Optimize()
if changed {
it.subIt.Close()
it.subIt = newSub
}
return it, false
}
// We're only as expensive as our subiterator. Except, we can't be nexted.
func (it *Optional) Stats() graph.IteratorStats {
subStats := it.subIt.Stats()
return graph.IteratorStats{
ContainsCost: subStats.ContainsCost,
NextCost: int64(1 << 62),
Size: subStats.Size,
}
}
// If you're empty and you know it, clap your hands.
func (it *Optional) Size() (int64, bool) {
return 0, true
}