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 iterator 16 17// Defines one of the base iterators, the LinksTo iterator. A LinksTo takes a 18// subiterator of nodes, and contains an iteration of links which "link to" 19// those nodes in a given direction. 20// 21// Next()ing a LinksTo is straightforward -- iterate through all links to // 22// things in the subiterator, and then advance the subiterator, and do it again. 23// LinksTo is therefore sensitive to growing with a fanout. (A small-sized 24// subiterator could cause LinksTo to be large). 25// 26// Contains()ing a LinksTo means, given a link, take the direction we care about 27// and check if it's in our subiterator. Checking is therefore fairly cheap, and 28// similar to checking the subiterator alone. 29// 30// Can be seen as the dual of the HasA iterator. 31 32import ( 33 "context" 34 "fmt" 35 36 "github.com/cayleygraph/cayley/graph" 37 "github.com/cayleygraph/cayley/quad" 38) 39 40var _ graph.Iterator = &LinksTo{} 41 42// A LinksTo has a reference back to the graph.QuadStore (to create the iterators 43// for each node) the subiterator, and the direction the iterator comes from. 44// `next_it` is the tempoarary iterator held per result in `primary_it`. 45type LinksTo struct { 46 uid uint64 47 tags graph.Tagger 48 qs graph.QuadStore 49 primaryIt graph.Iterator 50 dir quad.Direction 51 nextIt graph.Iterator 52 result graph.Value 53 runstats graph.IteratorStats 54 err error 55} 56 57// Construct a new LinksTo iterator around a direction and a subiterator of 58// nodes. 59func NewLinksTo(qs graph.QuadStore, it graph.Iterator, d quad.Direction) *LinksTo { 60 return &LinksTo{ 61 uid: NextUID(), 62 qs: qs, 63 primaryIt: it, 64 dir: d, 65 nextIt: &Null{}, 66 } 67} 68 69func (it *LinksTo) UID() uint64 { 70 return it.uid 71} 72 73func (it *LinksTo) Reset() { 74 it.primaryIt.Reset() 75 if it.nextIt != nil { 76 it.nextIt.Close() 77 } 78 it.nextIt = &Null{} 79} 80 81func (it *LinksTo) Tagger() *graph.Tagger { 82 return &it.tags 83} 84 85func (it *LinksTo) Clone() graph.Iterator { 86 out := NewLinksTo(it.qs, it.primaryIt.Clone(), it.dir) 87 out.tags.CopyFrom(it) 88 out.runstats.Size, out.runstats.ExactSize = it.runstats.Size, it.runstats.ExactSize 89 return out 90} 91 92// Return the direction under consideration. 93func (it *LinksTo) Direction() quad.Direction { return it.dir } 94 95// Tag these results, and our subiterator's results. 96func (it *LinksTo) TagResults(dst map[string]graph.Value) { 97 it.tags.TagResult(dst, it.Result()) 98 99 it.primaryIt.TagResults(dst) 100} 101 102func (it *LinksTo) String() string { 103 return fmt.Sprintf("LinksTo(%v)", it.dir) 104} 105 106// If it checks in the right direction for the subiterator, it is a valid link 107// for the LinksTo. 108func (it *LinksTo) Contains(ctx context.Context, val graph.Value) bool { 109 graph.ContainsLogIn(it, val) 110 it.runstats.Contains += 1 111 node := it.qs.QuadDirection(val, it.dir) 112 if it.primaryIt.Contains(ctx, node) { 113 it.result = val 114 return graph.ContainsLogOut(it, val, true) 115 } 116 it.err = it.primaryIt.Err() 117 return graph.ContainsLogOut(it, val, false) 118} 119 120// Return a list containing only our subiterator. 121func (it *LinksTo) SubIterators() []graph.Iterator { 122 return []graph.Iterator{it.primaryIt} 123} 124 125// Optimize the LinksTo, by replacing it if it can be. 126func (it *LinksTo) Optimize() (graph.Iterator, bool) { 127 newPrimary, changed := it.primaryIt.Optimize() 128 if changed { 129 it.primaryIt = newPrimary 130 if it.primaryIt.Type() == graph.Null { 131 it.nextIt.Close() 132 return it.primaryIt, true 133 } 134 } 135 // Ask the graph.QuadStore if we can be replaced. Often times, this is a great 136 // optimization opportunity (there's a fixed iterator underneath us, for 137 // example). 138 newReplacement, hasOne := it.qs.OptimizeIterator(it) 139 if hasOne { 140 it.Close() 141 return newReplacement, true 142 } 143 return it, false 144} 145 146// Next()ing a LinksTo operates as described above. 147func (it *LinksTo) Next(ctx context.Context) bool { 148 for { 149 graph.NextLogIn(it) 150 it.runstats.Next += 1 151 if it.nextIt.Next(ctx) { 152 it.runstats.ContainsNext += 1 153 it.result = it.nextIt.Result() 154 return graph.NextLogOut(it, true) 155 } 156 157 // If there's an error in the 'next' iterator, we save it and we're done. 158 it.err = it.nextIt.Err() 159 if it.err != nil { 160 return false 161 } 162 163 // Subiterator is empty, get another one 164 if !it.primaryIt.Next(ctx) { 165 // Possibly save error 166 it.err = it.primaryIt.Err() 167 168 // We're out of nodes in our subiterator, so we're done as well. 169 return graph.NextLogOut(it, false) 170 } 171 it.nextIt.Close() 172 it.nextIt = it.qs.QuadIterator(it.dir, it.primaryIt.Result()) 173 174 // Continue -- return the first in the next set. 175 } 176} 177 178func (it *LinksTo) Err() error { 179 return it.err 180} 181 182func (it *LinksTo) Result() graph.Value { 183 return it.result 184} 185 186// Close closes the iterator. It closes all subiterators it can, but 187// returns the first error it encounters. 188func (it *LinksTo) Close() error { 189 err := it.nextIt.Close() 190 191 _err := it.primaryIt.Close() 192 if _err != nil && err == nil { 193 err = _err 194 } 195 196 return err 197} 198 199// We won't ever have a new result, but our subiterators might. 200func (it *LinksTo) NextPath(ctx context.Context) bool { 201 ok := it.primaryIt.NextPath(ctx) 202 if !ok { 203 it.err = it.primaryIt.Err() 204 } 205 return ok 206} 207 208// Register the LinksTo. 209func (it *LinksTo) Type() graph.Type { return graph.LinksTo } 210 211// Return a guess as to how big or costly it is to next the iterator. 212func (it *LinksTo) Stats() graph.IteratorStats { 213 subitStats := it.primaryIt.Stats() 214 // TODO(barakmich): These should really come from the quadstore itself 215 checkConstant := int64(1) 216 nextConstant := int64(2) 217 st := graph.IteratorStats{ 218 NextCost: nextConstant + subitStats.NextCost, 219 ContainsCost: checkConstant + subitStats.ContainsCost, 220 Next: it.runstats.Next, 221 Contains: it.runstats.Contains, 222 ContainsNext: it.runstats.ContainsNext, 223 } 224 st.Size, st.ExactSize = it.Size() 225 return st 226} 227 228func (it *LinksTo) Size() (int64, bool) { 229 if it.runstats.Size != 0 { 230 return it.runstats.Size, it.runstats.ExactSize 231 } 232 if fixed, ok := it.primaryIt.(*Fixed); ok { 233 // get real sizes from sub iterators 234 var ( 235 sz int64 236 exact = true 237 ) 238 for _, v := range fixed.Values() { 239 sit := it.qs.QuadIterator(it.dir, v) 240 n, ex := sit.Size() 241 sit.Close() 242 sz += n 243 exact = exact && ex 244 } 245 it.runstats.Size, it.runstats.ExactSize = sz, exact 246 return sz, exact 247 } 248 // TODO(barakmich): It should really come from the quadstore itself 249 const fanoutFactor = 20 250 sz, _ := it.primaryIt.Size() 251 sz *= fanoutFactor 252 it.runstats.Size, it.runstats.ExactSize = sz, false 253 return sz, false 254} 255