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 graph 16 17// Define the general iterator interface. 18 19import ( 20 "context" 21 "strings" 22 23 "github.com/cayleygraph/cayley/clog" 24 "github.com/cayleygraph/cayley/quad" 25) 26 27type Tagger struct { 28 tags []string 29 fixedTags map[string]Value 30} 31 32// TODO(barakmich): Linkage is general enough that there are places we take 33//the combined arguments `quad.Direction, graph.Value` that it may be worth 34//converting these into Linkages. If nothing else, future indexed iterators may 35//benefit from the shared representation 36 37// Linkage is a union type representing a set of values established for a given 38// quad direction. 39type Linkage struct { 40 Dir quad.Direction 41 Value Value 42} 43 44// TODO(barakmich): Helper functions as needed, eg, ValuesForDirection(quad.Direction) []Value 45 46// Add a tag to the iterator. 47func (t *Tagger) Add(tag ...string) { 48 t.tags = append(t.tags, tag...) 49} 50 51func (t *Tagger) AddFixed(tag string, value Value) { 52 if t.fixedTags == nil { 53 t.fixedTags = make(map[string]Value) 54 } 55 t.fixedTags[tag] = value 56} 57 58// Tags returns the tags held in the tagger. The returned value must not be mutated. 59func (t *Tagger) Tags() []string { 60 return t.tags 61} 62 63// Fixed returns the fixed tags held in the tagger. The returned value must not be mutated. 64func (t *Tagger) Fixed() map[string]Value { 65 return t.fixedTags 66} 67 68func (t *Tagger) TagResult(dst map[string]Value, v Value) { 69 for _, tag := range t.Tags() { 70 dst[tag] = v 71 } 72 73 for tag, value := range t.Fixed() { 74 dst[tag] = value 75 } 76} 77 78func (t *Tagger) CopyFrom(src Iterator) { 79 t.CopyFromTagger(src.Tagger()) 80} 81 82func (t *Tagger) CopyFromTagger(st *Tagger) { 83 t.tags = append(t.tags, st.tags...) 84 85 if t.fixedTags == nil { 86 t.fixedTags = make(map[string]Value, len(st.fixedTags)) 87 } 88 for k, v := range st.fixedTags { 89 t.fixedTags[k] = v 90 } 91} 92 93type Iterator interface { 94 // String returns a short textual representation of an iterator. 95 String() string 96 97 Tagger() *Tagger 98 99 // Fills a tag-to-result-value map. 100 TagResults(map[string]Value) 101 102 // Returns the current result. 103 Result() Value 104 105 // Next advances the iterator to the next value, which will then be available through 106 // the Result method. It returns false if no further advancement is possible, or if an 107 // error was encountered during iteration. Err should be consulted to distinguish 108 // between the two cases. 109 Next(ctx context.Context) bool 110 111 // These methods are the heart and soul of the iterator, as they constitute 112 // the iteration interface. 113 // 114 // To get the full results of iteration, do the following: 115 // 116 // for graph.Next(it) { 117 // val := it.Result() 118 // ... do things with val. 119 // for it.NextPath() { 120 // ... find other paths to iterate 121 // } 122 // } 123 // 124 // All of them should set iterator.result to be the last returned value, to 125 // make results work. 126 // 127 // NextPath() advances iterators that may have more than one valid result, 128 // from the bottom up. 129 NextPath(ctx context.Context) bool 130 131 // Contains returns whether the value is within the set held by the iterator. 132 Contains(ctx context.Context, v Value) bool 133 134 // Err returns any error that was encountered by the Iterator. 135 Err() error 136 137 // Start iteration from the beginning 138 Reset() 139 140 // Create a new iterator just like this one 141 Clone() Iterator 142 143 // These methods relate to choosing the right iterator, or optimizing an 144 // iterator tree 145 // 146 // Stats() returns the relative costs of calling the iteration methods for 147 // this iterator, as well as the size. Roughly, it will take NextCost * Size 148 // "cost units" to get everything out of the iterator. This is a wibbly-wobbly 149 // thing, and not exact, but a useful heuristic. 150 Stats() IteratorStats 151 152 // Helpful accessor for the number of things in the iterator. The first return 153 // value is the size, and the second return value is whether that number is exact, 154 // or a conservative estimate. 155 Size() (int64, bool) 156 157 // Returns a string relating to what the function of the iterator is. By 158 // knowing the names of the iterators, we can devise optimization strategies. 159 Type() Type 160 161 // Optimizes an iterator. Can replace the iterator, or merely move things 162 // around internally. if it chooses to replace it with a better iterator, 163 // returns (the new iterator, true), if not, it returns (self, false). 164 Optimize() (Iterator, bool) 165 166 // Return a slice of the subiterators for this iterator. 167 SubIterators() []Iterator 168 169 // Close the iterator and do internal cleanup. 170 Close() error 171 172 // UID returns the unique identifier of the iterator. 173 UID() uint64 174} 175 176// DescribeIterator returns a description of the iterator tree. 177func DescribeIterator(it Iterator) Description { 178 sz, exact := it.Size() 179 d := Description{ 180 UID: it.UID(), 181 Name: it.String(), 182 Type: it.Type(), 183 Tags: it.Tagger().Tags(), 184 Size: sz, Exact: exact, 185 } 186 if sub := it.SubIterators(); len(sub) != 0 { 187 d.Iterators = make([]Description, 0, len(sub)) 188 for _, sit := range sub { 189 d.Iterators = append(d.Iterators, DescribeIterator(sit)) 190 } 191 } 192 return d 193} 194 195type Description struct { 196 UID uint64 `json:",omitempty"` 197 Name string `json:",omitempty"` 198 Type Type `json:",omitempty"` 199 Tags []string `json:",omitempty"` 200 Size int64 `json:",omitempty"` 201 Exact bool `json:",omitempty"` 202 Iterators []Description `json:",omitempty"` 203} 204 205// ApplyMorphism is a curried function that can generates a new iterator based on some prior iterator. 206type ApplyMorphism func(QuadStore, Iterator) Iterator 207 208// CanNext is a helper for checking if iterator can be Next()'ed. 209func CanNext(it Iterator) bool { 210 _, ok := it.(NoNext) 211 return !ok 212} 213 214// NoNext is an optional interface to signal that iterator should be Contain()'ed instead of Next()'ing if possible. 215type NoNext interface { 216 NoNext() 217} 218 219// Height is a convienence function to measure the height of an iterator tree. 220func Height(it Iterator, until Type) int { 221 if it.Type() == until { 222 return 1 223 } 224 subs := it.SubIterators() 225 maxDepth := 0 226 for _, sub := range subs { 227 h := Height(sub, until) 228 if h > maxDepth { 229 maxDepth = h 230 } 231 } 232 return maxDepth + 1 233} 234 235// FixedIterator wraps iterators that are modifiable by addition of fixed value sets. 236type FixedIterator interface { 237 Iterator 238 Add(Value) 239} 240 241type IteratorStats struct { 242 ContainsCost int64 243 NextCost int64 244 Size int64 245 ExactSize bool 246 Next int64 247 Contains int64 248 ContainsNext int64 249} 250 251// Type enumerates the set of Iterator types. 252type Type string 253 254// These are the iterator types, defined as constants 255const ( 256 Invalid = Type("") 257 All = Type("all") 258 And = Type("and") 259 Or = Type("or") 260 HasA = Type("hasa") 261 LinksTo = Type("linksto") 262 Comparison = Type("comparison") 263 Null = Type("null") 264 Err = Type("error") 265 Fixed = Type("fixed") 266 Not = Type("not") 267 Optional = Type("optional") 268 Materialize = Type("materialize") 269 Unique = Type("unique") 270 Limit = Type("limit") 271 Skip = Type("skip") 272 Regex = Type("regexp") 273 Count = Type("count") 274 Recursive = Type("recursive") 275 Resolver = Type("resolver") 276) 277 278// String returns a string representation of the Type. 279func (t Type) String() string { 280 if t == "" { 281 return "illegal-type" 282 } 283 return string(t) 284} 285 286type StatsContainer struct { 287 UID uint64 288 Type Type 289 IteratorStats 290 SubIts []StatsContainer 291} 292 293func DumpStats(it Iterator) StatsContainer { 294 var out StatsContainer 295 out.IteratorStats = it.Stats() 296 out.Type = it.Type() 297 out.UID = it.UID() 298 for _, sub := range it.SubIterators() { 299 out.SubIts = append(out.SubIts, DumpStats(sub)) 300 } 301 return out 302} 303 304// Utility logging functions for when an iterator gets called Next upon, or Contains upon, as 305// well as what they return. Highly useful for tracing the execution path of a query. 306 307func ContainsLogIn(it Iterator, val Value) { 308 if clog.V(4) { 309 clog.Infof("%s %d CHECK CONTAINS %v", strings.ToUpper(it.Type().String()), it.UID(), val) 310 } 311} 312 313func ContainsLogOut(it Iterator, val Value, good bool) bool { 314 if clog.V(4) { 315 if good { 316 clog.Infof("%s %d CHECK CONTAINS %v GOOD", strings.ToUpper(it.Type().String()), it.UID(), val) 317 } else { 318 clog.Infof("%s %d CHECK CONTAINS %v BAD", strings.ToUpper(it.Type().String()), it.UID(), val) 319 } 320 } 321 return good 322} 323 324func NextLogIn(it Iterator) { 325 if clog.V(4) { 326 clog.Infof("%s %d NEXT", strings.ToUpper(it.Type().String()), it.UID()) 327 } 328} 329 330func NextLogOut(it Iterator, ok bool) bool { 331 if clog.V(4) { 332 if ok { 333 val := it.Result() 334 clog.Infof("%s %d NEXT IS %v (%T)", strings.ToUpper(it.Type().String()), it.UID(), val, val) 335 } else { 336 clog.Infof("%s %d NEXT DONE", strings.ToUpper(it.Type().String()), it.UID()) 337 } 338 } 339 return ok 340} 341