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