Line data Source code
1 : // Copyright 2021 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 : "context"
9 : "fmt"
10 :
11 : "github.com/cockroachdb/errors"
12 : "github.com/cockroachdb/pebble/internal/base"
13 : "github.com/cockroachdb/pebble/internal/invariants"
14 : "github.com/cockroachdb/pebble/internal/treeprinter"
15 : )
16 :
17 : // A SpanMask may be used to configure an interleaving iterator to skip point
18 : // keys that fall within the bounds of some spans.
19 : type SpanMask interface {
20 : // SpanChanged is invoked by an interleaving iterator whenever the current
21 : // span changes. As the iterator passes into or out of a Span, it invokes
22 : // SpanChanged, passing the new Span. When the iterator passes out of a
23 : // span's boundaries and is no longer covered by any span, SpanChanged is
24 : // invoked with a nil span.
25 : //
26 : // SpanChanged is invoked before SkipPoint, and callers may use SpanChanged
27 : // to recalculate state used by SkipPoint for masking.
28 : //
29 : // SpanChanged may be invoked consecutively with identical spans under some
30 : // circumstances, such as repeatedly absolutely positioning an iterator to
31 : // positions covered by the same span, or while changing directions.
32 : SpanChanged(*Span)
33 : // SkipPoint is invoked by the interleaving iterator whenever the iterator
34 : // encounters a point key covered by a Span. If SkipPoint returns true, the
35 : // interleaving iterator skips the point key and all larger keys with the
36 : // same prefix. This is used during range key iteration to skip over point
37 : // keys 'masked' by range keys.
38 : SkipPoint(userKey []byte) bool
39 : }
40 :
41 : // InterleavingIter combines an iterator over point keys with an iterator over
42 : // key spans.
43 : //
44 : // Throughout Pebble, some keys apply at single discrete points within the user
45 : // keyspace. Other keys apply over continuous spans of the user key space.
46 : // Internally, iterators over point keys adhere to the base.InternalIterator
47 : // interface, and iterators over spans adhere to the keyspan.FragmentIterator
48 : // interface. The InterleavingIterator wraps a point iterator and span iterator,
49 : // providing access to all the elements of both iterators.
50 : //
51 : // The InterleavingIterator implements the point base.InternalIterator
52 : // interface. After any of the iterator's methods return a key, a caller may
53 : // call Span to retrieve the span covering the returned key, if any. A span is
54 : // considered to 'cover' a returned key if the span's [start, end) bounds
55 : // include the key's user key.
56 : //
57 : // In addition to tracking the current covering span, InterleavingIter returns a
58 : // special InternalKey at span start boundaries. Start boundaries are surfaced
59 : // as a synthetic span marker: an InternalKey with the boundary as the user key,
60 : // the infinite sequence number and a key kind selected from an arbitrary key
61 : // the infinite sequence number and an arbitrary contained key's kind. Since
62 : // which of the Span's key's kind is surfaced is undefined, the caller should
63 : // not use the InternalKey's kind. The caller should only rely on the `Span`
64 : // method for retrieving information about spanning keys. The interleaved
65 : // synthetic keys have the infinite sequence number so that they're interleaved
66 : // before any point keys with the same user key when iterating forward and after
67 : // when iterating backward.
68 : //
69 : // Interleaving the synthetic start key boundaries at the maximum sequence
70 : // number provides an opportunity for the higher-level, public Iterator to
71 : // observe the Span, even if no live points keys exist within the boudns of the
72 : // Span.
73 : //
74 : // When returning a synthetic marker key for a start boundary, InterleavingIter
75 : // will truncate the span's start bound to the SeekGE or SeekPrefixGE search
76 : // key. For example, a SeekGE("d") that finds a span [a, z) may return a
77 : // synthetic span marker key `d#72057594037927935,21`.
78 : //
79 : // If bounds have been applied to the iterator through SetBounds,
80 : // InterleavingIter will truncate the bounds of spans returned through Span to
81 : // the set bounds. The bounds returned through Span are not truncated by a
82 : // SeekGE or SeekPrefixGE search key. Consider, for example SetBounds('c', 'e'),
83 : // with an iterator containing the Span [a,z):
84 : //
85 : // First() = `c#72057594037927935,21` Span() = [c,e)
86 : // SeekGE('d') = `d#72057594037927935,21` Span() = [c,e)
87 : //
88 : // InterleavedIter does not interleave synthetic markers for spans that do not
89 : // contain any keys.
90 : //
91 : // When InterleavingIterOpts.InterleaveEndKeys is set, in addition to
92 : // interleaving start keys, the interleaving iterator will interleave end
93 : // boundary keys (also at the maximumal sequence number). At these end boundary
94 : // positions, Span() will return the span to which the end boundary belongs.
95 : //
96 : // # SpanMask
97 : //
98 : // InterelavingIter takes a SpanMask parameter that may be used to configure the
99 : // behavior of the iterator. See the documentation on the SpanMask type.
100 : //
101 : // All spans containing keys are exposed during iteration.
102 : type InterleavingIter struct {
103 : cmp base.Compare
104 : comparer *base.Comparer
105 : pointIter base.InternalIterator
106 : keyspanIter FragmentIterator
107 : opts InterleavingIterOpts
108 : // keyBuf is used to copy SeekGE or SeekPrefixGE arguments when they're used
109 : // to truncate a span. The byte slices backing a SeekGE/SeekPrefixGE search
110 : // keys can come directly from the end user, so they're copied into keyBuf
111 : // to ensure key stability.
112 : keyBuf []byte
113 : // nextPrefixBuf is used during SeekPrefixGE calls to store the truncated
114 : // upper bound of the returned spans. SeekPrefixGE truncates the returned
115 : // spans to an upper bound of the seeked prefix's immediate successor.
116 : nextPrefixBuf []byte
117 : pointKV *base.InternalKV
118 : // err holds an iterator error from either pointIter or keyspanIter. It's
119 : // reset to nil on seeks. An overview of error-handling mechanics:
120 : //
121 : // Whenever either pointIter or keyspanIter is respositioned and a nil
122 : // key/span is returned, the code performing the positioning is responsible
123 : // for checking the iterator's Error() value. This happens in savePoint and
124 : // saveSpan[Forward,Backward].
125 : //
126 : // Once i.err is non-nil, the computation of i.pos must set i.pos =
127 : // posExhausted. This happens in compute[Smallest|Largest]Pos and
128 : // [next|prev]Pos. Setting i.pos to posExhausted ensures we'll yield nil to
129 : // the caller, which they'll interpret as a signal they must check Error().
130 : //
131 : // INVARIANTS:
132 : // i.err != nil => i.pos = posExhausted
133 : err error
134 : // prefix records the iterator's current prefix if the iterator is in prefix
135 : // mode. During prefix mode, Pebble will truncate spans to the next prefix.
136 : // If the iterator subsequently leaves prefix mode, the existing span cached
137 : // in i.span must be invalidated because its bounds do not reflect the
138 : // original span's true bounds.
139 : prefix []byte
140 : // span holds the span at the keyspanIter's current position. If the span is
141 : // wholly contained within the iterator bounds, this span is directly
142 : // returned to the iterator consumer through Span(). If either bound needed
143 : // to be truncated to the iterator bounds, then truncated is set to true and
144 : // Span() must return a pointer to truncatedSpan.
145 : span *Span
146 : // spanMarker holds the synthetic key that is returned when the iterator
147 : // passes over a key span's start bound.
148 : spanMarker base.InternalKV
149 : // truncated indicates whether or not the span at the current position
150 : // needed to be truncated. If it did, truncatedSpan holds the truncated
151 : // span that should be returned.
152 : truncatedSpan Span
153 : truncated bool
154 :
155 : // Keeping all of the bools/uint8s together reduces the sizeof the struct.
156 :
157 : // pos encodes the current position of the iterator: exhausted, on the point
158 : // key, on a keyspan start, or on a keyspan end.
159 : pos interleavePos
160 : // withinSpan indicates whether the iterator is currently positioned within
161 : // the bounds of the current span (i.span). withinSpan must be updated
162 : // whenever the interleaving iterator's position enters or exits the bounds
163 : // of a span.
164 : withinSpan bool
165 : // spanMarkerTruncated is set by SeekGE/SeekPrefixGE calls that truncate a
166 : // span's start bound marker to the search key. It's returned to false on
167 : // the next repositioning of the keyspan iterator.
168 : spanMarkerTruncated bool
169 : // maskSpanChangedCalled records whether or not the last call to
170 : // SpanMask.SpanChanged provided the current span (i.span) or not.
171 : maskSpanChangedCalled bool
172 : // dir indicates the direction of iteration: forward (+1) or backward (-1)
173 : dir int8
174 : }
175 :
176 : // interleavePos indicates the iterator's current position. Note that both
177 : // keyspanStart and keyspanEnd positions correspond to their user key boundaries
178 : // with maximal sequence numbers. This means in the forward direction
179 : // posKeyspanStart and posKeyspanEnd are always interleaved before a posPointKey
180 : // with the same user key.
181 : type interleavePos int8
182 :
183 : const (
184 : posUninitialized interleavePos = iota
185 : posExhausted
186 : posPointKey
187 : posKeyspanStart
188 : posKeyspanEnd
189 : )
190 :
191 : // Assert that *InterleavingIter implements the InternalIterator interface.
192 : var _ base.InternalIterator = &InterleavingIter{}
193 :
194 : // InterleavingIterOpts holds options configuring the behavior of a
195 : // InterleavingIter.
196 : type InterleavingIterOpts struct {
197 : Mask SpanMask
198 : LowerBound, UpperBound []byte
199 : // InterleaveEndKeys configures the interleaving iterator to interleave the
200 : // end keys of spans (in addition to the start keys, which are always
201 : // interleaved).
202 : InterleaveEndKeys bool
203 : }
204 :
205 : // Init initializes the InterleavingIter to interleave point keys from pointIter
206 : // with key spans from keyspanIter.
207 : //
208 : // The point iterator must already have the bounds provided on opts. Init does
209 : // not propagate the bounds down the iterator stack.
210 : func (i *InterleavingIter) Init(
211 : comparer *base.Comparer,
212 : pointIter base.InternalIterator,
213 : keyspanIter FragmentIterator,
214 : opts InterleavingIterOpts,
215 1 : ) {
216 1 : keyspanIter = MaybeAssert(keyspanIter, comparer.Compare)
217 1 : // To debug:
218 1 : // keyspanIter = InjectLogging(keyspanIter, base.DefaultLogger)
219 1 : *i = InterleavingIter{
220 1 : cmp: comparer.Compare,
221 1 : comparer: comparer,
222 1 : pointIter: pointIter,
223 1 : keyspanIter: keyspanIter,
224 1 : opts: opts,
225 1 : }
226 1 : }
227 :
228 : // InitSeekGE may be called after Init but before any positioning method.
229 : // InitSeekGE initializes the current position of the point iterator and then
230 : // performs a SeekGE on the keyspan iterator using the provided key. InitSeekGE
231 : // returns whichever point or keyspan key is smaller. After InitSeekGE, the
232 : // iterator is positioned and may be repositioned using relative positioning
233 : // methods.
234 : //
235 : // This method is used specifically for lazily constructing combined iterators.
236 : // It allows for seeding the iterator with the current position of the point
237 : // iterator.
238 : func (i *InterleavingIter) InitSeekGE(
239 : prefix, key []byte, pointKV *base.InternalKV,
240 1 : ) *base.InternalKV {
241 1 : i.dir = +1
242 1 : i.clearMask()
243 1 : i.prefix = prefix
244 1 : i.savePoint(pointKV)
245 1 : // NB: This keyspanSeekGE call will truncate the span to the seek key if
246 1 : // necessary. This truncation is important for cases where a switch to
247 1 : // combined iteration is made during a user-initiated SeekGE.
248 1 : i.keyspanSeekGE(key, prefix)
249 1 : i.computeSmallestPos()
250 1 : return i.yieldPosition(key, i.nextPos)
251 1 : }
252 :
253 : // InitSeekLT may be called after Init but before any positioning method.
254 : // InitSeekLT initializes the current position of the point iterator and then
255 : // performs a SeekLT on the keyspan iterator using the provided key. InitSeekLT
256 : // returns whichever point or keyspan key is larger. After InitSeekLT, the
257 : // iterator is positioned and may be repositioned using relative positioning
258 : // methods.
259 : //
260 : // This method is used specifically for lazily constructing combined iterators.
261 : // It allows for seeding the iterator with the current position of the point
262 : // iterator.
263 1 : func (i *InterleavingIter) InitSeekLT(key []byte, pointKV *base.InternalKV) *base.InternalKV {
264 1 : i.dir = -1
265 1 : i.clearMask()
266 1 : i.savePoint(pointKV)
267 1 : i.keyspanSeekLT(key)
268 1 : i.computeLargestPos()
269 1 : return i.yieldPosition(i.opts.LowerBound, i.prevPos)
270 1 : }
271 :
272 : // SeekGE implements (base.InternalIterator).SeekGE.
273 : //
274 : // If there exists a span with a start key ≤ the first matching point key,
275 : // SeekGE will return a synthetic span marker key for the span. If this span's
276 : // start key is less than key, the returned marker will be truncated to key.
277 : // Note that this search-key truncation of the marker's key is not applied to
278 : // the span returned by Span.
279 : //
280 : // NB: In accordance with the base.InternalIterator contract:
281 : //
282 : // i.lower ≤ key
283 1 : func (i *InterleavingIter) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKV {
284 1 : i.err = nil
285 1 : i.clearMask()
286 1 : i.disablePrefixMode()
287 1 : i.savePoint(i.pointIter.SeekGE(key, flags))
288 1 :
289 1 : // We need to seek the keyspan iterator too. If the keyspan iterator was
290 1 : // already positioned at a span, we might be able to avoid the seek if the
291 1 : // seek key falls within the existing span's bounds.
292 1 : if i.span != nil && i.cmp(key, i.span.End) < 0 && i.cmp(key, i.span.Start) >= 0 {
293 1 : // We're seeking within the existing span's bounds. We still might need
294 1 : // truncate the span to the iterator's bounds.
295 1 : i.saveSpanForward(i.span, nil)
296 1 : i.savedKeyspan()
297 1 : } else {
298 1 : i.keyspanSeekGE(key, nil /* prefix */)
299 1 : }
300 :
301 1 : i.dir = +1
302 1 : i.computeSmallestPos()
303 1 : return i.yieldPosition(key, i.nextPos)
304 : }
305 :
306 : // SeekPrefixGE implements (base.InternalIterator).SeekPrefixGE.
307 : //
308 : // If there exists a span with a start key ≤ the first matching point key,
309 : // SeekPrefixGE will return a synthetic span marker key for the span. If this
310 : // span's start key is less than key, the returned marker will be truncated to
311 : // key. Note that this search-key truncation of the marker's key is not applied
312 : // to the span returned by Span.
313 : //
314 : // NB: In accordance with the base.InternalIterator contract:
315 : //
316 : // i.lower ≤ key
317 : func (i *InterleavingIter) SeekPrefixGE(
318 : prefix, key []byte, flags base.SeekGEFlags,
319 1 : ) *base.InternalKV {
320 1 : i.err = nil
321 1 : i.clearMask()
322 1 : i.prefix = prefix
323 1 : i.savePoint(i.pointIter.SeekPrefixGE(prefix, key, flags))
324 1 :
325 1 : // We need to seek the keyspan iterator too. If the keyspan iterator was
326 1 : // already positioned at a span, we might be able to avoid the seek if the
327 1 : // entire seek prefix key falls within the existing span's bounds.
328 1 : //
329 1 : // During a SeekPrefixGE, Pebble defragments range keys within the bounds of
330 1 : // the prefix. For example, a SeekPrefixGE('c', 'c@8') must defragment the
331 1 : // any overlapping range keys within the bounds of [c,c\00).
332 1 : //
333 1 : // If range keys are fragmented within a prefix (eg, because a version
334 1 : // within a prefix was chosen as an sstable boundary), then it's possible
335 1 : // the seek key falls into the current i.span, but the current i.span does
336 1 : // not wholly cover the seek prefix.
337 1 : //
338 1 : // For example, a SeekPrefixGE('d@5') may only defragment a range key to
339 1 : // the bounds of [c@2,e). A subsequent SeekPrefixGE('c@0') must re-seek the
340 1 : // keyspan iterator, because although 'c@0' is contained within [c@2,e), the
341 1 : // full span of the prefix is not.
342 1 : //
343 1 : // Similarly, a SeekPrefixGE('a@3') may only defragment a range key to the
344 1 : // bounds [a,c@8). A subsequent SeekPrefixGE('c@10') must re-seek the
345 1 : // keyspan iterator, because although 'c@10' is contained within [a,c@8),
346 1 : // the full span of the prefix is not.
347 1 : seekKeyspanIter := true
348 1 : if i.span != nil && i.cmp(prefix, i.span.Start) >= 0 {
349 1 : if ei := i.comparer.Split(i.span.End); i.cmp(prefix, i.span.End[:ei]) < 0 {
350 1 : // We're seeking within the existing span's bounds. We still might need
351 1 : // truncate the span to the iterator's bounds.
352 1 : i.saveSpanForward(i.span, nil)
353 1 : i.savedKeyspan()
354 1 : seekKeyspanIter = false
355 1 : }
356 : }
357 1 : if seekKeyspanIter {
358 1 : i.keyspanSeekGE(key, prefix)
359 1 : }
360 :
361 1 : i.dir = +1
362 1 : i.computeSmallestPos()
363 1 : return i.yieldPosition(key, i.nextPos)
364 : }
365 :
366 : // SeekLT implements (base.InternalIterator).SeekLT.
367 1 : func (i *InterleavingIter) SeekLT(key []byte, flags base.SeekLTFlags) *base.InternalKV {
368 1 : i.err = nil
369 1 : i.clearMask()
370 1 : i.disablePrefixMode()
371 1 : i.savePoint(i.pointIter.SeekLT(key, flags))
372 1 :
373 1 : // We need to seek the keyspan iterator too. If the keyspan iterator was
374 1 : // already positioned at a span, we might be able to avoid the seek if the
375 1 : // seek key falls within the existing span's bounds.
376 1 : if i.span != nil && i.cmp(key, i.span.Start) > 0 && i.cmp(key, i.span.End) < 0 {
377 1 : // We're seeking within the existing span's bounds. We still might need
378 1 : // truncate the span to the iterator's bounds.
379 1 : i.saveSpanBackward(i.span, nil)
380 1 : // The span's start key is still not guaranteed to be less than key,
381 1 : // because of the bounds enforcement. Consider the following example:
382 1 : //
383 1 : // Bounds are set to [d,e). The user performs a SeekLT(d). The
384 1 : // FragmentIterator.SeekLT lands on a span [b,f). This span has a start
385 1 : // key less than d, as expected. Above, saveSpanBackward truncates the
386 1 : // span to match the iterator's current bounds, modifying the span to
387 1 : // [d,e), which does not overlap the search space of [-∞, d).
388 1 : //
389 1 : // This problem is a consequence of the SeekLT's exclusive search key
390 1 : // and the fact that we don't perform bounds truncation at every leaf
391 1 : // iterator.
392 1 : if i.span != nil && i.truncated && i.cmp(i.truncatedSpan.Start, key) >= 0 {
393 1 : i.span = nil
394 1 : }
395 1 : i.savedKeyspan()
396 1 : } else {
397 1 : i.keyspanSeekLT(key)
398 1 : }
399 :
400 1 : i.dir = -1
401 1 : i.computeLargestPos()
402 1 : return i.yieldPosition(i.opts.LowerBound, i.prevPos)
403 : }
404 :
405 : // First implements (base.InternalIterator).First.
406 1 : func (i *InterleavingIter) First() *base.InternalKV {
407 1 : i.err = nil
408 1 : i.clearMask()
409 1 : i.disablePrefixMode()
410 1 : i.savePoint(i.pointIter.First())
411 1 : i.saveSpanForward(i.keyspanIter.First())
412 1 : i.savedKeyspan()
413 1 : i.dir = +1
414 1 : i.computeSmallestPos()
415 1 : return i.yieldPosition(i.opts.LowerBound, i.nextPos)
416 1 : }
417 :
418 : // Last implements (base.InternalIterator).Last.
419 1 : func (i *InterleavingIter) Last() *base.InternalKV {
420 1 : i.err = nil
421 1 : i.clearMask()
422 1 : i.disablePrefixMode()
423 1 : i.savePoint(i.pointIter.Last())
424 1 : i.saveSpanBackward(i.keyspanIter.Last())
425 1 : i.savedKeyspan()
426 1 : i.dir = -1
427 1 : i.computeLargestPos()
428 1 : return i.yieldPosition(i.opts.LowerBound, i.prevPos)
429 1 : }
430 :
431 : // Next implements (base.InternalIterator).Next.
432 1 : func (i *InterleavingIter) Next() *base.InternalKV {
433 1 : if i.dir == -1 {
434 1 : // Switching directions.
435 1 : i.dir = +1
436 1 :
437 1 : if i.opts.Mask != nil {
438 1 : // Clear the mask while we reposition the point iterator. While
439 1 : // switching directions, we may move the point iterator outside of
440 1 : // i.span's bounds.
441 1 : i.clearMask()
442 1 : }
443 :
444 : // When switching directions, iterator state corresponding to the
445 : // current iterator position (as indicated by i.pos) is already correct.
446 : // However any state that has yet to be interleaved describes a position
447 : // behind the current iterator position and needs to be updated to
448 : // describe the position ahead of the current iterator position.
449 1 : switch i.pos {
450 0 : case posExhausted:
451 : // Nothing to do. The below nextPos call will move both the point
452 : // key and span to their next positions and return
453 : // MIN(point,s.Start).
454 1 : case posPointKey:
455 1 : // If we're currently on a point key, the below nextPos will
456 1 : // correctly Next the point key iterator to the next point key.
457 1 : // Do we need to move the span forwards? If the current span lies
458 1 : // entirely behind the current key (!i.withinSpan), then we
459 1 : // need to move it to the first span in the forward direction.
460 1 : if !i.withinSpan {
461 1 : i.saveSpanForward(i.keyspanIter.Next())
462 1 : i.savedKeyspan()
463 1 : }
464 1 : case posKeyspanStart:
465 1 : i.withinSpan = true
466 1 : // Since we're positioned on a Span, the pointIter is positioned
467 1 : // entirely behind the current iterator position. Reposition it
468 1 : // ahead of the current iterator position.
469 1 : i.switchPointIteratorIntoForward()
470 1 : case posKeyspanEnd:
471 1 : // Since we're positioned on a Span, the pointIter is positioned
472 1 : // entirely behind of the current iterator position. Reposition it
473 1 : // ahead the current iterator position.
474 1 : i.switchPointIteratorIntoForward()
475 : }
476 : // Fallthrough to calling i.nextPos.
477 : }
478 1 : i.nextPos()
479 1 : return i.yieldPosition(i.opts.LowerBound, i.nextPos)
480 : }
481 :
482 : // NextPrefix implements (base.InternalIterator).NextPrefix.
483 : //
484 : // Calling NextPrefix while positioned at a span boundary is prohibited.
485 1 : func (i *InterleavingIter) NextPrefix(succKey []byte) *base.InternalKV {
486 1 : if i.dir == -1 {
487 0 : panic("pebble: cannot switch directions with NextPrefix")
488 : }
489 :
490 1 : switch i.pos {
491 0 : case posExhausted:
492 0 : return nil
493 1 : case posPointKey:
494 1 : i.savePoint(i.pointIter.NextPrefix(succKey))
495 1 : if i.withinSpan {
496 1 : if i.pointKV == nil || i.cmp(i.span.End, i.pointKV.K.UserKey) <= 0 {
497 1 : i.pos = posKeyspanEnd
498 1 : } else {
499 1 : i.pos = posPointKey
500 1 : }
501 1 : } else {
502 1 : i.computeSmallestPos()
503 1 : }
504 0 : case posKeyspanStart, posKeyspanEnd:
505 0 : panic(errors.AssertionFailedf("NextPrefix called while positioned on a span boundary"))
506 : }
507 1 : return i.yieldPosition(i.opts.LowerBound, i.nextPos)
508 : }
509 :
510 : // Prev implements (base.InternalIterator).Prev.
511 1 : func (i *InterleavingIter) Prev() *base.InternalKV {
512 1 : if i.dir == +1 {
513 1 : // Switching directions.
514 1 : i.dir = -1
515 1 :
516 1 : if i.opts.Mask != nil {
517 1 : // Clear the mask while we reposition the point iterator. While
518 1 : // switching directions, we may move the point iterator outside of
519 1 : // i.span's bounds.
520 1 : i.clearMask()
521 1 : }
522 :
523 : // When switching directions, iterator state corresponding to the
524 : // current iterator position (as indicated by i.pos) is already correct.
525 : // However any state that has yet to be interleaved describes a position
526 : // ahead of the current iterator position and needs to be updated to
527 : // describe the position behind the current iterator position.
528 1 : switch i.pos {
529 0 : case posExhausted:
530 : // Nothing to do. The below prevPos call will move both the point
531 : // key and span to previous positions and return MAX(point, s.End).
532 1 : case posPointKey:
533 1 : // If we're currently on a point key, the point iterator is in the
534 1 : // right place and the call to prevPos will correctly Prev the point
535 1 : // key iterator to the previous point key. Do we need to move the
536 1 : // span backwards? If the current span lies entirely ahead of the
537 1 : // current key (!i.withinSpan), then we need to move it to the first
538 1 : // span in the reverse direction.
539 1 : if !i.withinSpan {
540 1 : i.saveSpanBackward(i.keyspanIter.Prev())
541 1 : i.savedKeyspan()
542 1 : }
543 1 : case posKeyspanStart:
544 1 : // Since we're positioned on a Span, the pointIter is positioned
545 1 : // entirely ahead of the current iterator position. Reposition it
546 1 : // behind the current iterator position.
547 1 : i.switchPointIteratorIntoReverse()
548 1 : // Without considering truncation of spans to seek keys, the keyspan
549 1 : // iterator is already in the right place. But consider span [a, z)
550 1 : // and this sequence of iterator calls:
551 1 : //
552 1 : // SeekGE('c') = c.RANGEKEYSET#72057594037927935
553 1 : // Prev() = a.RANGEKEYSET#72057594037927935
554 1 : //
555 1 : // If the current span's start key was last surfaced truncated due
556 1 : // to a SeekGE or SeekPrefixGE call, then it's still relevant in the
557 1 : // reverse direction with an untruncated start key.
558 1 : if i.spanMarkerTruncated {
559 1 : // When we fallthrough to calling prevPos, we want to move to
560 1 : // MAX(point, span.Start). We cheat here by claiming we're
561 1 : // currently on the end boundary, so that we'll move on to the
562 1 : // untruncated start key if necessary.
563 1 : i.pos = posKeyspanEnd
564 1 : }
565 1 : case posKeyspanEnd:
566 1 : // Since we're positioned on a Span, the pointIter is positioned
567 1 : // entirely ahead of the current iterator position. Reposition it
568 1 : // behind the current iterator position.
569 1 : i.switchPointIteratorIntoReverse()
570 : }
571 :
572 1 : if i.spanMarkerTruncated {
573 1 : // Save the keyspan again to clear truncation.
574 1 : i.savedKeyspan()
575 1 : }
576 : // Fallthrough to calling i.prevPos.
577 : }
578 1 : i.prevPos()
579 1 : return i.yieldPosition(i.opts.LowerBound, i.prevPos)
580 : }
581 :
582 : // computeSmallestPos sets i.{pos,withinSpan} to:
583 : //
584 : // MIN(i.pointKey, i.span.Start)
585 1 : func (i *InterleavingIter) computeSmallestPos() {
586 1 : if i.err == nil {
587 1 : if i.span != nil && (i.pointKV == nil || i.cmp(i.startKey(), i.pointKV.K.UserKey) <= 0) {
588 1 : i.withinSpan = true
589 1 : i.pos = posKeyspanStart
590 1 : return
591 1 : }
592 1 : i.withinSpan = false
593 1 : if i.pointKV != nil {
594 1 : i.pos = posPointKey
595 1 : return
596 1 : }
597 : }
598 1 : i.pos = posExhausted
599 : }
600 :
601 : // computeLargestPos sets i.{pos,withinSpan} to:
602 : //
603 : // MAX(i.pointKey, i.span.End)
604 1 : func (i *InterleavingIter) computeLargestPos() {
605 1 : if i.err == nil {
606 1 : if i.span != nil && (i.pointKV == nil || i.cmp(i.span.End, i.pointKV.K.UserKey) > 0) {
607 1 : i.withinSpan = true
608 1 : i.pos = posKeyspanEnd
609 1 : return
610 1 : }
611 1 : i.withinSpan = false
612 1 : if i.pointKV != nil {
613 1 : i.pos = posPointKey
614 1 : return
615 1 : }
616 : }
617 1 : i.pos = posExhausted
618 : }
619 :
620 : // nextPos advances the iterator one position in the forward direction.
621 1 : func (i *InterleavingIter) nextPos() {
622 1 : if invariants.Enabled {
623 1 : defer func() {
624 1 : if i.err != nil && i.pos != posExhausted {
625 0 : panic(errors.AssertionFailedf("iterator has accumulated error but i.pos = %d", i.pos))
626 : }
627 : }()
628 : }
629 : // NB: If i.err != nil or any of the positioning methods performed in this
630 : // function result in i.err != nil, we must set i.pos = posExhausted. We
631 : // perform this check explicitly here, but if any of the branches below
632 : // advance either iterator, they must also check i.err and set posExhausted
633 : // if necessary.
634 1 : if i.err != nil {
635 0 : i.pos = posExhausted
636 0 : return
637 0 : }
638 :
639 1 : switch i.pos {
640 0 : case posExhausted:
641 0 : i.switchPointIteratorIntoForward()
642 0 : i.saveSpanForward(i.keyspanIter.Next())
643 0 : i.savedKeyspan()
644 0 : i.computeSmallestPos()
645 1 : case posPointKey:
646 1 : i.savePoint(i.pointIter.Next())
647 1 : if i.err != nil {
648 0 : i.pos = posExhausted
649 0 : return
650 0 : }
651 : // If we're not currently within the span, we want to chose the
652 : // MIN(pointKey,span.Start), which is exactly the calculation performed
653 : // by computeSmallestPos.
654 1 : if !i.withinSpan {
655 1 : i.computeSmallestPos()
656 1 : return
657 1 : }
658 : // i.withinSpan=true
659 : // Since we previously were within the span, we want to choose the
660 : // MIN(pointKey,span.End).
661 1 : switch {
662 0 : case i.span == nil:
663 0 : panic("i.withinSpan=true and i.span=nil")
664 1 : case i.pointKV == nil:
665 1 : // Since i.withinSpan=true, we step onto the end boundary of the
666 1 : // keyspan.
667 1 : i.pos = posKeyspanEnd
668 1 : default:
669 1 : // i.withinSpan && i.pointKV != nil && i.span != nil
670 1 : if i.cmp(i.span.End, i.pointKV.K.UserKey) <= 0 {
671 1 : i.pos = posKeyspanEnd
672 1 : } else {
673 1 : i.pos = posPointKey
674 1 : }
675 : }
676 1 : case posKeyspanStart:
677 1 : // Either a point key or the span's end key comes next.
678 1 : if i.pointKV != nil && i.cmp(i.pointKV.K.UserKey, i.span.End) < 0 {
679 1 : i.pos = posPointKey
680 1 : } else {
681 1 : i.pos = posKeyspanEnd
682 1 : }
683 1 : case posKeyspanEnd:
684 1 : i.saveSpanForward(i.keyspanIter.Next())
685 1 : i.savedKeyspan()
686 1 : i.computeSmallestPos()
687 0 : default:
688 0 : panic(fmt.Sprintf("unexpected pos=%d", i.pos))
689 : }
690 : }
691 :
692 : // prevPos advances the iterator one position in the reverse direction.
693 1 : func (i *InterleavingIter) prevPos() {
694 1 : if invariants.Enabled {
695 1 : defer func() {
696 1 : if i.err != nil && i.pos != posExhausted {
697 0 : panic(errors.AssertionFailedf("iterator has accumulated error but i.pos = %d", i.pos))
698 : }
699 : }()
700 : }
701 : // NB: If i.err != nil or any of the positioning methods performed in this
702 : // function result in i.err != nil, we must set i.pos = posExhausted. We
703 : // perform this check explicitly here, but if any of the branches below
704 : // advance either iterator, they must also check i.err and set posExhausted
705 : // if necessary.
706 1 : if i.err != nil {
707 0 : i.pos = posExhausted
708 0 : return
709 0 : }
710 :
711 1 : switch i.pos {
712 0 : case posExhausted:
713 0 : i.switchPointIteratorIntoReverse()
714 0 : i.saveSpanBackward(i.keyspanIter.Prev())
715 0 : i.savedKeyspan()
716 0 : i.computeLargestPos()
717 1 : case posPointKey:
718 1 : i.savePoint(i.pointIter.Prev())
719 1 : if i.err != nil {
720 0 : i.pos = posExhausted
721 0 : return
722 0 : }
723 : // If we're not currently covered by the span, we want to chose the
724 : // MAX(pointKey,span.End), which is exactly the calculation performed
725 : // by computeLargestPos.
726 1 : if !i.withinSpan {
727 1 : i.computeLargestPos()
728 1 : return
729 1 : }
730 1 : switch {
731 0 : case i.span == nil:
732 0 : panic("withinSpan=true, but i.span == nil")
733 1 : case i.pointKV == nil:
734 1 : i.pos = posKeyspanStart
735 1 : default:
736 1 : // i.withinSpan && i.pointKey != nil && i.span != nil
737 1 : if i.cmp(i.span.Start, i.pointKV.K.UserKey) > 0 {
738 1 : i.pos = posKeyspanStart
739 1 : } else {
740 1 : i.pos = posPointKey
741 1 : }
742 : }
743 1 : case posKeyspanStart:
744 1 : i.saveSpanBackward(i.keyspanIter.Prev())
745 1 : i.savedKeyspan()
746 1 : i.computeLargestPos()
747 1 : case posKeyspanEnd:
748 1 : // Either a point key or the span's start key is previous.
749 1 : if i.pointKV != nil && i.cmp(i.pointKV.K.UserKey, i.span.Start) >= 0 {
750 1 : i.pos = posPointKey
751 1 : } else {
752 1 : i.pos = posKeyspanStart
753 1 : }
754 0 : default:
755 0 : panic(fmt.Sprintf("unexpected pos=%d", i.pos))
756 : }
757 : }
758 :
759 1 : func (i *InterleavingIter) yieldPosition(lowerBound []byte, advance func()) *base.InternalKV {
760 1 : // This loop returns the first visible position in the current iteration
761 1 : // direction. Some positions are not visible and skipped. For example, if
762 1 : // masking is enabled and the iterator is positioned over a masked point
763 1 : // key, this loop skips the position. If a span's start key should be
764 1 : // interleaved next, but the span is empty, the loop continues to the next
765 1 : // key. Currently, span end keys are also always skipped, and are used only
766 1 : // for maintaining internal state.
767 1 : for {
768 1 : switch i.pos {
769 1 : case posExhausted:
770 1 : return i.yieldNil()
771 1 : case posPointKey:
772 1 : if i.pointKV == nil {
773 0 : panic("i.pointKV is nil")
774 : }
775 :
776 1 : if i.opts.Mask != nil {
777 1 : i.maybeUpdateMask()
778 1 : if i.withinSpan && i.opts.Mask.SkipPoint(i.pointKV.K.UserKey) {
779 1 : // The span covers the point key. If a SkipPoint hook is
780 1 : // configured, ask it if we should skip this point key.
781 1 : if i.prefix != nil {
782 1 : // During prefix-iteration node, once a point is masked,
783 1 : // all subsequent keys with the same prefix must also be
784 1 : // masked according to the key ordering. We can stop and
785 1 : // return nil.
786 1 : //
787 1 : // NB: The above is not just an optimization. During
788 1 : // prefix-iteration mode, the internal iterator contract
789 1 : // prohibits us from Next-ing beyond the first key
790 1 : // beyond the iteration prefix. If we didn't already
791 1 : // stop early, we would need to check if this masked
792 1 : // point is already beyond the prefix.
793 1 : return i.yieldNil()
794 1 : }
795 : // TODO(jackson): If we thread a base.Comparer through to
796 : // InterleavingIter so that we have access to
797 : // ImmediateSuccessor, we could use NextPrefix. We'd need to
798 : // tweak the SpanMask interface slightly.
799 :
800 : // Advance beyond the masked point key.
801 1 : advance()
802 1 : continue
803 : }
804 : }
805 1 : return i.yieldPointKey()
806 1 : case posKeyspanEnd:
807 1 : if !i.opts.InterleaveEndKeys {
808 1 : // Don't interleave end keys; just advance.
809 1 : advance()
810 1 : continue
811 : }
812 1 : return i.yieldSyntheticSpanEndMarker()
813 1 : case posKeyspanStart:
814 1 : // Don't interleave an empty span.
815 1 : if i.span.Empty() {
816 1 : advance()
817 1 : continue
818 : }
819 1 : return i.yieldSyntheticSpanStartMarker(lowerBound)
820 0 : default:
821 0 : panic(fmt.Sprintf("unexpected interleavePos=%d", i.pos))
822 : }
823 : }
824 : }
825 :
826 : // keyspanSeekGE seeks the keyspan iterator to the first span covering a key ≥ k.
827 1 : func (i *InterleavingIter) keyspanSeekGE(k []byte, prefix []byte) {
828 1 : i.saveSpanForward(i.keyspanIter.SeekGE(k))
829 1 : i.savedKeyspan()
830 1 : }
831 :
832 : // keyspanSeekLT seeks the keyspan iterator to the last span covering a key < k.
833 1 : func (i *InterleavingIter) keyspanSeekLT(k []byte) {
834 1 : i.saveSpanBackward(i.keyspanIter.SeekLT(k))
835 1 : // The current span's start key is not guaranteed to be less than key,
836 1 : // because of the bounds enforcement. Consider the following example:
837 1 : //
838 1 : // Bounds are set to [d,e). The user performs a SeekLT(d). The
839 1 : // FragmentIterator.SeekLT lands on a span [b,f). This span has a start key
840 1 : // less than d, as expected. Above, saveSpanBackward truncates the span to
841 1 : // match the iterator's current bounds, modifying the span to [d,e), which
842 1 : // does not overlap the search space of [-∞, d).
843 1 : //
844 1 : // This problem is a consequence of the SeekLT's exclusive search key and
845 1 : // the fact that we don't perform bounds truncation at every leaf iterator.
846 1 : if i.span != nil && i.truncated && i.cmp(i.truncatedSpan.Start, k) >= 0 {
847 1 : i.span = nil
848 1 : }
849 1 : i.savedKeyspan()
850 : }
851 :
852 : // switchPointIteratorIntoReverse switches the direction of the point iterator
853 : // into reverse, stepping to the previous point key. If the point iterator is
854 : // exhausted in the forward direction and there's an upper bound present, it's
855 : // re-seeked to ensure the iterator obeys the upper bound.
856 1 : func (i *InterleavingIter) switchPointIteratorIntoReverse() {
857 1 : if i.pointKV == nil && i.opts.UpperBound != nil {
858 1 : i.savePoint(i.pointIter.SeekLT(i.opts.UpperBound, base.SeekLTFlagsNone))
859 1 : return
860 1 : }
861 1 : i.savePoint(i.pointIter.Prev())
862 : }
863 :
864 : // switchPointIteratorIntoForward switches the direction of the point iterator
865 : // into the forward direction, stepping to the next point key. If the point
866 : // iterator is exhausted in the reverse direction and there's a lower bound
867 : // present, it's re-seeked to ensure the iterator obeys the lower bound.
868 1 : func (i *InterleavingIter) switchPointIteratorIntoForward() {
869 1 : if i.pointKV == nil && i.opts.LowerBound != nil {
870 1 : i.savePoint(i.pointIter.SeekGE(i.opts.LowerBound, base.SeekGEFlagsNone))
871 1 : return
872 1 : }
873 1 : i.savePoint(i.pointIter.Next())
874 : }
875 :
876 1 : func (i *InterleavingIter) saveSpanForward(span *Span, err error) {
877 1 : i.span = span
878 1 : i.err = firstError(i.err, err)
879 1 : i.truncated = false
880 1 : i.truncatedSpan = Span{}
881 1 : if i.span == nil {
882 1 : return
883 1 : }
884 : // Check the upper bound if we have one.
885 1 : if i.opts.UpperBound != nil && i.cmp(i.span.Start, i.opts.UpperBound) >= 0 {
886 1 : i.span = nil
887 1 : return
888 1 : }
889 :
890 : // TODO(jackson): The key comparisons below truncate bounds whenever the
891 : // keyspan iterator is repositioned. We could perform this lazily, and do it
892 : // the first time the user actually asks for this span's bounds in
893 : // SpanBounds. This would reduce work in the case where there's no span
894 : // covering the point and the keyspan iterator is non-empty.
895 :
896 : // NB: These truncations don't require setting `keyspanMarkerTruncated`:
897 : // That flag only applies to truncated span marker keys.
898 1 : if i.opts.LowerBound != nil && i.cmp(i.span.Start, i.opts.LowerBound) < 0 {
899 1 : i.truncated = true
900 1 : i.truncatedSpan = *i.span
901 1 : i.truncatedSpan.Start = i.opts.LowerBound
902 1 : }
903 1 : if i.opts.UpperBound != nil && i.cmp(i.opts.UpperBound, i.span.End) < 0 {
904 1 : if !i.truncated {
905 1 : i.truncated = true
906 1 : i.truncatedSpan = *i.span
907 1 : }
908 1 : i.truncatedSpan.End = i.opts.UpperBound
909 : }
910 : // If this is a part of a SeekPrefixGE call, we may also need to truncate to
911 : // the prefix's bounds.
912 1 : if i.prefix != nil {
913 1 : if !i.truncated {
914 1 : i.truncated = true
915 1 : i.truncatedSpan = *i.span
916 1 : }
917 1 : if i.cmp(i.prefix, i.truncatedSpan.Start) > 0 {
918 1 : i.truncatedSpan.Start = i.prefix
919 1 : }
920 1 : i.nextPrefixBuf = i.comparer.ImmediateSuccessor(i.nextPrefixBuf[:0], i.prefix)
921 1 : if i.truncated && i.cmp(i.nextPrefixBuf, i.truncatedSpan.End) < 0 {
922 1 : i.truncatedSpan.End = i.nextPrefixBuf
923 1 : }
924 : }
925 :
926 1 : if i.truncated && i.comparer.Equal(i.truncatedSpan.Start, i.truncatedSpan.End) {
927 1 : i.span = nil
928 1 : }
929 : }
930 :
931 1 : func (i *InterleavingIter) saveSpanBackward(span *Span, err error) {
932 1 : i.span = span
933 1 : i.err = firstError(i.err, err)
934 1 : i.truncated = false
935 1 : i.truncatedSpan = Span{}
936 1 : if i.span == nil {
937 1 : return
938 1 : }
939 :
940 : // Check the lower bound if we have one.
941 1 : if i.opts.LowerBound != nil && i.cmp(i.span.End, i.opts.LowerBound) <= 0 {
942 1 : i.span = nil
943 1 : return
944 1 : }
945 :
946 : // TODO(jackson): The key comparisons below truncate bounds whenever the
947 : // keyspan iterator is repositioned. We could perform this lazily, and do it
948 : // the first time the user actually asks for this span's bounds in
949 : // SpanBounds. This would reduce work in the case where there's no span
950 : // covering the point and the keyspan iterator is non-empty.
951 :
952 : // NB: These truncations don't require setting `keyspanMarkerTruncated`:
953 : // That flag only applies to truncated span marker keys.
954 1 : if i.opts.LowerBound != nil && i.cmp(i.span.Start, i.opts.LowerBound) < 0 {
955 1 : i.truncated = true
956 1 : i.truncatedSpan = *i.span
957 1 : i.truncatedSpan.Start = i.opts.LowerBound
958 1 : }
959 1 : if i.opts.UpperBound != nil && i.cmp(i.opts.UpperBound, i.span.End) < 0 {
960 1 : if !i.truncated {
961 1 : i.truncated = true
962 1 : i.truncatedSpan = *i.span
963 1 : }
964 1 : i.truncatedSpan.End = i.opts.UpperBound
965 : }
966 1 : if i.truncated && i.comparer.Equal(i.truncatedSpan.Start, i.truncatedSpan.End) {
967 1 : i.span = nil
968 1 : }
969 : }
970 :
971 1 : func (i *InterleavingIter) yieldNil() *base.InternalKV {
972 1 : i.withinSpan = false
973 1 : i.clearMask()
974 1 : return i.verify(nil)
975 1 : }
976 :
977 1 : func (i *InterleavingIter) yieldPointKey() *base.InternalKV {
978 1 : return i.verify(i.pointKV)
979 1 : }
980 :
981 1 : func (i *InterleavingIter) yieldSyntheticSpanStartMarker(lowerBound []byte) *base.InternalKV {
982 1 : i.spanMarker.K.UserKey = i.startKey()
983 1 : i.spanMarker.K.Trailer = base.MakeTrailer(base.SeqNumMax, i.span.Keys[0].Kind())
984 1 :
985 1 : // Truncate the key we return to our lower bound if we have one. Note that
986 1 : // we use the lowerBound function parameter, not i.lower. The lowerBound
987 1 : // argument is guaranteed to be ≥ i.lower. It may be equal to the SetBounds
988 1 : // lower bound, or it could come from a SeekGE or SeekPrefixGE search key.
989 1 : if lowerBound != nil && i.cmp(lowerBound, i.startKey()) > 0 {
990 1 : // Truncating to the lower bound may violate the upper bound if
991 1 : // lowerBound == i.upper. For example, a SeekGE(k) uses k as a lower
992 1 : // bound for truncating a span. The span a-z will be truncated to [k,
993 1 : // z). If i.upper == k, we'd mistakenly try to return a span [k, k), an
994 1 : // invariant violation.
995 1 : if i.comparer.Equal(lowerBound, i.opts.UpperBound) {
996 1 : return i.yieldNil()
997 1 : }
998 :
999 : // If the lowerBound argument came from a SeekGE or SeekPrefixGE
1000 : // call, and it may be backed by a user-provided byte slice that is not
1001 : // guaranteed to be stable.
1002 : //
1003 : // If the lowerBound argument is the lower bound set by SetBounds,
1004 : // Pebble owns the slice's memory. However, consider two successive
1005 : // calls to SetBounds(). The second may overwrite the lower bound.
1006 : // Although the external contract requires a seek after a SetBounds,
1007 : // Pebble's tests don't always. For this reason and to simplify
1008 : // reasoning around lifetimes, always copy the bound into keyBuf when
1009 : // truncating.
1010 1 : i.keyBuf = append(i.keyBuf[:0], lowerBound...)
1011 1 : i.spanMarker.K.UserKey = i.keyBuf
1012 1 : i.spanMarkerTruncated = true
1013 : }
1014 1 : i.maybeUpdateMask()
1015 1 : return i.verify(&i.spanMarker)
1016 : }
1017 :
1018 1 : func (i *InterleavingIter) yieldSyntheticSpanEndMarker() *base.InternalKV {
1019 1 : i.spanMarker.K.UserKey = i.endKey()
1020 1 : i.spanMarker.K.Trailer = base.MakeTrailer(base.SeqNumMax, i.span.Keys[0].Kind())
1021 1 : return i.verify(&i.spanMarker)
1022 1 : }
1023 :
1024 1 : func (i *InterleavingIter) disablePrefixMode() {
1025 1 : if i.prefix != nil {
1026 1 : i.prefix = nil
1027 1 : // Clear the existing span. It may not hold the true end bound of the
1028 1 : // underlying span.
1029 1 : i.span = nil
1030 1 : }
1031 : }
1032 :
1033 1 : func (i *InterleavingIter) verify(kv *base.InternalKV) *base.InternalKV {
1034 1 : // Wrap the entire function body in the invariants build tag, so that
1035 1 : // production builds elide this entire function.
1036 1 : if invariants.Enabled {
1037 1 : switch {
1038 0 : case i.dir == -1 && i.spanMarkerTruncated:
1039 0 : panic("pebble: invariant violation: truncated span key in reverse iteration")
1040 : case kv != nil && i.opts.LowerBound != nil && !kv.K.IsExclusiveSentinel() &&
1041 0 : i.cmp(kv.K.UserKey, i.opts.LowerBound) < 0:
1042 0 : panic("pebble: invariant violation: key < lower bound")
1043 : case kv != nil && i.opts.UpperBound != nil && !kv.K.IsExclusiveSentinel() &&
1044 0 : !base.UserKeyExclusive(i.opts.UpperBound).IsUpperBoundForInternalKey(i.comparer.Compare, kv.K):
1045 0 : panic("pebble: invariant violation: key ≥ upper bound")
1046 0 : case i.err != nil && kv != nil:
1047 0 : panic("pebble: invariant violation: accumulated error swallowed")
1048 0 : case i.err == nil && i.pointIter.Error() != nil:
1049 0 : panic("pebble: invariant violation: pointIter swallowed")
1050 : }
1051 : }
1052 1 : return kv
1053 : }
1054 :
1055 1 : func (i *InterleavingIter) savedKeyspan() {
1056 1 : i.spanMarkerTruncated = false
1057 1 : i.maskSpanChangedCalled = false
1058 1 : }
1059 :
1060 : // updateMask updates the current mask, if a mask is configured and the mask
1061 : // hasn't been updated with the current keyspan yet.
1062 1 : func (i *InterleavingIter) maybeUpdateMask() {
1063 1 : switch {
1064 1 : case i.opts.Mask == nil, i.maskSpanChangedCalled:
1065 1 : return
1066 1 : case !i.withinSpan || i.span.Empty():
1067 1 : i.clearMask()
1068 1 : case i.truncated:
1069 1 : i.opts.Mask.SpanChanged(&i.truncatedSpan)
1070 1 : i.maskSpanChangedCalled = true
1071 1 : default:
1072 1 : i.opts.Mask.SpanChanged(i.span)
1073 1 : i.maskSpanChangedCalled = true
1074 : }
1075 : }
1076 :
1077 : // clearMask clears the current mask, if a mask is configured and no mask should
1078 : // be active.
1079 1 : func (i *InterleavingIter) clearMask() {
1080 1 : if i.opts.Mask != nil {
1081 1 : i.maskSpanChangedCalled = false
1082 1 : i.opts.Mask.SpanChanged(nil)
1083 1 : }
1084 : }
1085 :
1086 1 : func (i *InterleavingIter) startKey() []byte {
1087 1 : if i.truncated {
1088 1 : return i.truncatedSpan.Start
1089 1 : }
1090 1 : return i.span.Start
1091 : }
1092 :
1093 1 : func (i *InterleavingIter) endKey() []byte {
1094 1 : if i.truncated {
1095 1 : return i.truncatedSpan.End
1096 1 : }
1097 1 : return i.span.End
1098 : }
1099 :
1100 1 : func (i *InterleavingIter) savePoint(kv *base.InternalKV) {
1101 1 : i.pointKV = kv
1102 1 : if kv == nil {
1103 1 : i.err = firstError(i.err, i.pointIter.Error())
1104 1 : }
1105 1 : if invariants.Enabled {
1106 1 : if err := i.pointIter.Error(); kv != nil && err != nil {
1107 0 : panic(errors.WithSecondaryError(
1108 0 : base.AssertionFailedf("pebble: %T point iterator returned non-nil key %q while iter has error", i.pointIter, kv),
1109 0 : err))
1110 : }
1111 : }
1112 : }
1113 :
1114 : // Span returns the span covering the last key returned, if any. A span key is
1115 : // considered to 'cover' a key if the key falls within the span's user key
1116 : // bounds. The returned span is owned by the InterleavingIter. The caller is
1117 : // responsible for copying if stability is required.
1118 : //
1119 : // Span will never return an invalid or empty span.
1120 1 : func (i *InterleavingIter) Span() *Span {
1121 1 : if invariants.Enabled && i.pointIter == nil {
1122 0 : panic("Span() called after close")
1123 : }
1124 1 : if !i.withinSpan || len(i.span.Keys) == 0 {
1125 1 : return nil
1126 1 : }
1127 1 : if i.truncated {
1128 1 : return &i.truncatedSpan
1129 1 : }
1130 1 : return i.span
1131 : }
1132 :
1133 : // SetBounds implements (base.InternalIterator).SetBounds.
1134 1 : func (i *InterleavingIter) SetBounds(lower, upper []byte) {
1135 1 : i.opts.LowerBound, i.opts.UpperBound = lower, upper
1136 1 : i.pointIter.SetBounds(lower, upper)
1137 1 : i.Invalidate()
1138 1 : }
1139 :
1140 : // SetContext implements (base.InternalIterator).SetContext.
1141 0 : func (i *InterleavingIter) SetContext(ctx context.Context) {
1142 0 : i.pointIter.SetContext(ctx)
1143 0 : i.keyspanIter.SetContext(ctx)
1144 0 : }
1145 :
1146 : // DebugTree is part of the InternalIterator interface.
1147 0 : func (i *InterleavingIter) DebugTree(tp treeprinter.Node) {
1148 0 : n := tp.Childf("%T(%p)", i, i)
1149 0 : if i.pointIter != nil {
1150 0 : i.pointIter.DebugTree(n)
1151 0 : }
1152 0 : if i.keyspanIter != nil {
1153 0 : i.keyspanIter.DebugTree(n)
1154 0 : }
1155 : }
1156 :
1157 : // Invalidate invalidates the interleaving iterator's current position, clearing
1158 : // its state. This prevents optimizations such as reusing the current span on
1159 : // seek.
1160 1 : func (i *InterleavingIter) Invalidate() {
1161 1 : i.span = nil
1162 1 : i.pointKV = nil
1163 1 : }
1164 :
1165 : // Error implements (base.InternalIterator).Error.
1166 1 : func (i *InterleavingIter) Error() error {
1167 1 : return i.err
1168 1 : }
1169 :
1170 : // Close implements (base.InternalIterator).Close.
1171 1 : func (i *InterleavingIter) Close() error {
1172 1 : err := i.pointIter.Close()
1173 1 : i.pointIter = nil
1174 1 : i.keyspanIter.Close()
1175 1 : i.keyspanIter = nil
1176 1 : return err
1177 1 : }
1178 :
1179 : // String implements (base.InternalIterator).String.
1180 0 : func (i *InterleavingIter) String() string {
1181 0 : return fmt.Sprintf("keyspan-interleaving(%q)", i.pointIter.String())
1182 0 : }
1183 :
1184 1 : func firstError(err0, err1 error) error {
1185 1 : if err0 != nil {
1186 0 : return err0
1187 0 : }
1188 1 : return err1
1189 : }
|
