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