Line data Source code
1 : // Copyright 2022 The LevelDB-Go and Pebble Authors. All rights reserved. Use
2 : // of this source code is governed by a BSD-style license that can be found in
3 : // the LICENSE file.
4 :
5 : package keyspan
6 :
7 : import (
8 : "github.com/cockroachdb/pebble/internal/base"
9 : "github.com/cockroachdb/pebble/internal/treeprinter"
10 : )
11 :
12 : // TODO(jackson): Consider removing this type and adding bounds enforcement
13 : // directly to the MergingIter. This type is probably too lightweight to warrant
14 : // its own type, but for now we implement it separately for expediency.
15 :
16 : // boundedIterPos records the position of the BoundedIter relative to the
17 : // underlying iterator's position. It's used to avoid Next/Prev-ing the iterator
18 : // if there can't possibly be another span within bounds, because the current
19 : // span overlaps the bound.
20 : //
21 : // Imagine bounds [a,c) and an iterator that seeks to a span [b,d). The span
22 : // [b,d) overlaps some portion of the iterator bounds, so the iterator must
23 : // return it. If the iterator is subsequently Nexted, Next can tell that the
24 : // iterator is exhausted without advancing the underlying iterator because the
25 : // current span's end bound of d is ≥ the upper bound of c. In this case, the
26 : // bounded iterator returns nil and records i.pos as posAtUpperLimit to remember
27 : // that the underlying iterator position does not match the current BoundedIter
28 : // position.
29 : type boundedIterPos int8
30 :
31 : const (
32 : posAtLowerLimit boundedIterPos = -1
33 : posAtIterSpan boundedIterPos = 0
34 : posAtUpperLimit boundedIterPos = +1
35 : )
36 :
37 : // BoundedIter implements FragmentIterator and enforces bounds.
38 : //
39 : // Like the point InternalIterator interface, the bounded iterator's forward
40 : // positioning routines (SeekGE, First, and Next) only check the upper bound.
41 : // The reverse positioning routines (SeekLT, Last, and Prev) only check the
42 : // lower bound. It is up to the caller to ensure that the forward positioning
43 : // routines respect the lower bound and the reverse positioning routines respect
44 : // the upper bound (i.e. calling SeekGE instead of First if there is a lower
45 : // bound, and SeekLT instead of Last if there is an upper bound).
46 : //
47 : // When the hasPrefix parameter indicates that the iterator is in prefix
48 : // iteration mode, BoundedIter elides any spans that do not overlap with the
49 : // prefix's keyspace. In prefix iteration mode, reverse iteration is disallowed,
50 : // except for an initial SeekLT with a seek key greater than or equal to the
51 : // prefix. In prefix iteration mode, the first seek must position the iterator
52 : // at or immediately before the first fragment covering a key greater than or
53 : // equal to the prefix.
54 : type BoundedIter struct {
55 : iter FragmentIterator
56 : iterSpan *Span
57 : cmp base.Compare
58 : split base.Split
59 : lower []byte
60 : upper []byte
61 : hasPrefix *bool
62 : prefix *[]byte
63 : pos boundedIterPos
64 : }
65 :
66 : // Init initializes the bounded iterator.
67 : //
68 : // In addition to the iterator bounds, Init takes pointers to a boolean
69 : // indicating whether the iterator is in prefix iteration mode and the prefix
70 : // key if it is. This is used to exclude spans that are outside the iteration
71 : // prefix.
72 : //
73 : // hasPrefix and prefix are allowed to be nil, however if hasPrefix != nil,
74 : // prefix must also not be nil.
75 : func (i *BoundedIter) Init(
76 : cmp base.Compare,
77 : split base.Split,
78 : iter FragmentIterator,
79 : lower, upper []byte,
80 : hasPrefix *bool,
81 : prefix *[]byte,
82 1 : ) {
83 1 : *i = BoundedIter{
84 1 : iter: iter,
85 1 : cmp: cmp,
86 1 : split: split,
87 1 : lower: lower,
88 1 : upper: upper,
89 1 : hasPrefix: hasPrefix,
90 1 : prefix: prefix,
91 1 : }
92 1 : }
93 :
94 : var _ FragmentIterator = (*BoundedIter)(nil)
95 :
96 : // Seek calls.
97 : //
98 : // Seek calls check iterator bounds in the direction of the seek. Additionally,
99 : // if the iterator is in prefix iteration mode, seek calls check both start and
100 : // end bounds against the prefix's bounds. We check both bounds for defense in
101 : // depth. This optimization has been a source of various bugs due to various
102 : // other prefix iteration optimizations that can result in seek keys that don't
103 : // respect the prefix bounds.
104 :
105 : // SeekGE implements FragmentIterator.
106 1 : func (i *BoundedIter) SeekGE(key []byte) (*Span, error) {
107 1 : s, err := i.iter.SeekGE(key)
108 1 : s, err = i.checkPrefixSpanStart(s, err)
109 1 : s, err = i.checkPrefixSpanEnd(s, err)
110 1 : return i.checkForwardBound(s, err)
111 1 : }
112 :
113 : // SeekLT implements FragmentIterator.
114 1 : func (i *BoundedIter) SeekLT(key []byte) (*Span, error) {
115 1 : s, err := i.iter.SeekLT(key)
116 1 : s, err = i.checkPrefixSpanStart(s, err)
117 1 : s, err = i.checkPrefixSpanEnd(s, err)
118 1 : return i.checkBackwardBound(s, err)
119 1 : }
120 :
121 : // First implements FragmentIterator.
122 1 : func (i *BoundedIter) First() (*Span, error) {
123 1 : s, err := i.iter.First()
124 1 : s, err = i.checkPrefixSpanStart(s, err)
125 1 : return i.checkForwardBound(s, err)
126 1 : }
127 :
128 : // Last implements FragmentIterator.
129 1 : func (i *BoundedIter) Last() (*Span, error) {
130 1 : s, err := i.iter.Last()
131 1 : s, err = i.checkPrefixSpanEnd(s, err)
132 1 : return i.checkBackwardBound(s, err)
133 1 : }
134 :
135 : // Next implements FragmentIterator.
136 1 : func (i *BoundedIter) Next() (*Span, error) {
137 1 : switch i.pos {
138 1 : case posAtLowerLimit:
139 1 : // The BoundedIter had previously returned nil, because it knew from
140 1 : // i.iterSpan's bounds that there was no previous span. To Next, we only
141 1 : // need to return the current iter span and reset i.pos to reflect that
142 1 : // we're no longer positioned at the limit.
143 1 : i.pos = posAtIterSpan
144 1 : return i.iterSpan, nil
145 1 : case posAtIterSpan:
146 1 : // If the span at the underlying iterator position extends to or beyond the
147 1 : // upper bound, we can avoid advancing because the next span is necessarily
148 1 : // out of bounds.
149 1 : if i.iterSpan != nil && i.upper != nil && i.cmp(i.iterSpan.End, i.upper) >= 0 {
150 1 : i.pos = posAtUpperLimit
151 1 : return nil, nil
152 1 : }
153 : // Similarly, if the span extends to the next prefix and we're in prefix
154 : // iteration mode, we can avoid advancing.
155 1 : if i.iterSpan != nil && i.hasPrefix != nil && *i.hasPrefix {
156 1 : ei := i.split(i.iterSpan.End)
157 1 : if i.cmp(i.iterSpan.End[:ei], *i.prefix) > 0 {
158 1 : i.pos = posAtUpperLimit
159 1 : return nil, nil
160 1 : }
161 : }
162 1 : return i.checkForwardBound(i.checkPrefixSpanStart(i.iter.Next()))
163 0 : case posAtUpperLimit:
164 0 : // Already exhausted.
165 0 : return nil, nil
166 0 : default:
167 0 : panic("unreachable")
168 : }
169 : }
170 :
171 : // Prev implements FragmentIterator.
172 1 : func (i *BoundedIter) Prev() (*Span, error) {
173 1 : switch i.pos {
174 0 : case posAtLowerLimit:
175 0 : // Already exhausted.
176 0 : return nil, nil
177 1 : case posAtIterSpan:
178 1 : // If the span at the underlying iterator position extends to or beyond
179 1 : // the lower bound, we can avoid advancing because the previous span is
180 1 : // necessarily out of bounds.
181 1 : if i.iterSpan != nil && i.lower != nil && i.cmp(i.iterSpan.Start, i.lower) <= 0 {
182 1 : i.pos = posAtLowerLimit
183 1 : return nil, nil
184 1 : }
185 : // Similarly, if the span extends to or beyond the current prefix and
186 : // we're in prefix iteration mode, we can avoid advancing.
187 1 : if i.iterSpan != nil && i.hasPrefix != nil && *i.hasPrefix {
188 1 : si := i.split(i.iterSpan.Start)
189 1 : if i.cmp(i.iterSpan.Start[:si], *i.prefix) < 0 {
190 1 : i.pos = posAtLowerLimit
191 1 : return nil, nil
192 1 : }
193 : }
194 1 : return i.checkBackwardBound(i.checkPrefixSpanEnd(i.iter.Prev()))
195 1 : case posAtUpperLimit:
196 1 : // The BoundedIter had previously returned nil, because it knew from
197 1 : // i.iterSpan's bounds that there was no next span. To Prev, we only
198 1 : // need to return the current iter span and reset i.pos to reflect that
199 1 : // we're no longer positioned at the limit.
200 1 : i.pos = posAtIterSpan
201 1 : return i.iterSpan, nil
202 0 : default:
203 0 : panic("unreachable")
204 : }
205 : }
206 :
207 : // Close implements FragmentIterator.
208 1 : func (i *BoundedIter) Close() {
209 1 : i.iter.Close()
210 1 : }
211 :
212 : // SetBounds modifies the FragmentIterator's bounds.
213 1 : func (i *BoundedIter) SetBounds(lower, upper []byte) {
214 1 : i.lower, i.upper = lower, upper
215 1 : }
216 :
217 1 : func (i *BoundedIter) checkPrefixSpanStart(span *Span, err error) (*Span, error) {
218 1 : // Compare to the prefix's bounds, if in prefix iteration mode.
219 1 : if span != nil && i.hasPrefix != nil && *i.hasPrefix {
220 1 : si := i.split(span.Start)
221 1 : if i.cmp(span.Start[:si], *i.prefix) > 0 {
222 1 : // This span starts at a prefix that sorts after our current prefix.
223 1 : span = nil
224 1 : }
225 : }
226 1 : return span, err
227 : }
228 :
229 : // checkForwardBound enforces the upper bound, returning nil if the provided
230 : // span is wholly outside the upper bound. It also updates i.pos and i.iterSpan
231 : // to reflect the new iterator position.
232 1 : func (i *BoundedIter) checkForwardBound(span *Span, err error) (*Span, error) {
233 1 : // Compare to the upper bound.
234 1 : if span != nil && i.upper != nil && i.cmp(span.Start, i.upper) >= 0 {
235 1 : span = nil
236 1 : }
237 1 : i.iterSpan = span
238 1 : if i.pos != posAtIterSpan {
239 1 : i.pos = posAtIterSpan
240 1 : }
241 1 : return span, err
242 : }
243 :
244 1 : func (i *BoundedIter) checkPrefixSpanEnd(span *Span, err error) (*Span, error) {
245 1 : // Compare to the prefix's bounds, if in prefix iteration mode.
246 1 : if span != nil && i.hasPrefix != nil && *i.hasPrefix && i.cmp(span.End, *i.prefix) <= 0 {
247 1 : // This span ends before the current prefix.
248 1 : span = nil
249 1 : }
250 1 : return span, err
251 : }
252 :
253 : // checkBackward enforces the lower bound, returning nil if the provided span is
254 : // wholly outside the lower bound. It also updates i.pos and i.iterSpan to
255 : // reflect the new iterator position.
256 1 : func (i *BoundedIter) checkBackwardBound(span *Span, err error) (*Span, error) {
257 1 : // Compare to the lower bound.
258 1 : if span != nil && i.lower != nil && i.cmp(span.End, i.lower) <= 0 {
259 1 : span = nil
260 1 : }
261 1 : i.iterSpan = span
262 1 : if i.pos != posAtIterSpan {
263 1 : i.pos = posAtIterSpan
264 1 : }
265 1 : return span, err
266 : }
267 :
268 : // WrapChildren implements FragmentIterator.
269 0 : func (i *BoundedIter) WrapChildren(wrap WrapFn) {
270 0 : i.iter = wrap(i.iter)
271 0 : }
272 :
273 : // DebugTree is part of the FragmentIterator interface.
274 0 : func (i *BoundedIter) DebugTree(tp treeprinter.Node) {
275 0 : n := tp.Childf("%T(%p)", i, i)
276 0 : if i.iter != nil {
277 0 : i.iter.DebugTree(n)
278 0 : }
279 : }
|
