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// "Optional" is kind of odd. It's not an iterator in the strictest sense, but 18// it's easier to implement as an iterator. 19// 20// Consider what it means. It means that we have a subconstraint which we do 21// not want to constrain the query -- we just want it to return the matching 22// subgraph if one matches at all. By analogy to regular expressions, it is the 23// '?' operator. 24// 25// If it were a proper iterator of its own (and indeed, a reasonable refactor 26// of this iterator would be to make it such) it would contain an all iterator 27// -- all things in the graph. It matches everything (as does the regex "(a)?") 28 29import ( 30 "context" 31 32 "github.com/cayleygraph/cayley/clog" 33 "github.com/cayleygraph/cayley/graph" 34) 35 36var ( 37 _ graph.Iterator = &Optional{} 38 _ graph.NoNext = &Optional{} 39) 40 41// An optional iterator has the sub-constraint iterator we wish to be optional 42// and whether the last check we received was true or false. 43type Optional struct { 44 uid uint64 45 tags graph.Tagger 46 subIt graph.Iterator 47 lastCheck bool 48 result graph.Value 49 err error 50} 51 52// Creates a new optional iterator. 53func NewOptional(it graph.Iterator) *Optional { 54 return &Optional{ 55 uid: NextUID(), 56 subIt: it, 57 } 58} 59 60func (it *Optional) UID() uint64 { 61 return it.uid 62} 63 64func (it *Optional) Reset() { 65 it.subIt.Reset() 66 it.lastCheck = false 67} 68 69func (it *Optional) Close() error { 70 return it.subIt.Close() 71} 72 73func (it *Optional) Tagger() *graph.Tagger { 74 return &it.tags 75} 76 77func (it *Optional) Clone() graph.Iterator { 78 out := NewOptional(it.subIt.Clone()) 79 out.tags.CopyFrom(it) 80 return out 81} 82 83func (it *Optional) Err() error { 84 return it.err 85} 86 87func (it *Optional) Result() graph.Value { 88 return it.result 89} 90 91// Optional iterator cannot be Next()'ed. 92func (it *Optional) Next(ctx context.Context) bool { 93 clog.Errorf("Nexting an un-nextable iterator: %T", it) 94 return false 95} 96 97// Optional iterator cannot be Next()'ed. 98func (it *Optional) NoNext() {} 99 100// An optional iterator only has a next result if, (a) last time we checked 101// we had any results whatsoever, and (b) there was another subresult in our 102// optional subbranch. 103func (it *Optional) NextPath(ctx context.Context) bool { 104 if it.lastCheck { 105 ok := it.subIt.NextPath(ctx) 106 if !ok { 107 it.err = it.subIt.Err() 108 } 109 return ok 110 } 111 return false 112} 113 114func (it *Optional) SubIterators() []graph.Iterator { 115 return []graph.Iterator{it.subIt} 116} 117 118// Contains() is the real hack of this iterator. It always returns true, regardless 119// of whether the subiterator matched. But we keep track of whether the subiterator 120// matched for results purposes. 121func (it *Optional) Contains(ctx context.Context, val graph.Value) bool { 122 checked := it.subIt.Contains(ctx, val) 123 it.lastCheck = checked 124 it.err = it.subIt.Err() 125 it.result = val 126 return true 127} 128 129// If we failed the check, then the subiterator should not contribute to the result 130// set. Otherwise, go ahead and tag it. 131func (it *Optional) TagResults(dst map[string]graph.Value) { 132 it.tags.TagResult(dst, it.Result()) 133 134 if it.lastCheck == false { 135 return 136 } 137 it.subIt.TagResults(dst) 138} 139 140// Registers the optional iterator. 141func (it *Optional) Type() graph.Type { return graph.Optional } 142 143func (it *Optional) String() string { 144 return "Optional" 145} 146 147// There's nothing to optimize for an optional. Optimize the subiterator and 148// potentially replace it. 149func (it *Optional) Optimize() (graph.Iterator, bool) { 150 newSub, changed := it.subIt.Optimize() 151 if changed { 152 it.subIt.Close() 153 it.subIt = newSub 154 } 155 return it, false 156} 157 158// We're only as expensive as our subiterator. Except, we can't be nexted. 159func (it *Optional) Stats() graph.IteratorStats { 160 subStats := it.subIt.Stats() 161 return graph.IteratorStats{ 162 ContainsCost: subStats.ContainsCost, 163 NextCost: int64(1 << 62), 164 // If it's empty, pretend like it's not. 165 Size: subStats.Size + 1, 166 ExactSize: subStats.ExactSize, 167 } 168} 169 170func (it *Optional) Size() (int64, bool) { 171 return it.Stats().Size, false 172} 173