Line data Source code
1 : // Copyright 2023 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 : // Assert wraps an iterator which asserts that operations return sane results.
18 1 : func Assert(iter FragmentIterator, cmp base.Compare) FragmentIterator {
19 1 : return &assertIter{
20 1 : iter: iter,
21 1 : cmp: cmp,
22 1 : }
23 1 : }
24 :
25 : // MaybeAssert potentially wraps an iterator with Assert and/or
26 : // NewInvalidatingIter if we are in testing mode.
27 1 : func MaybeAssert(iter FragmentIterator, cmp base.Compare) FragmentIterator {
28 1 : if invariants.Enabled {
29 1 : if invariants.Sometimes(60 /* percent */) {
30 1 : iter = NewInvalidatingIter(iter)
31 1 : }
32 1 : if invariants.Sometimes(60 /* percent */) {
33 1 : iter = Assert(iter, cmp)
34 1 : }
35 : }
36 1 : return iter
37 : }
38 :
39 : // AssertUserKeyBounds wraps an iterator and asserts that all spans are within
40 : // the given bounds [lower, upper).
41 : func AssertUserKeyBounds(
42 : iter FragmentIterator, lower, upper []byte, cmp base.Compare,
43 0 : ) FragmentIterator {
44 0 : return AssertBounds(iter, base.MakeSearchKey(lower), upper, cmp)
45 0 : }
46 :
47 : // AssertBounds wraps an iterator and asserts that all spans are within the
48 : // given bounds [lower.UserKey, upper), and that all keys in a span that starts
49 : // exactly at lower.UserKey are >= lower.
50 : //
51 : // The asymmetry here is due to fragment spans having exclusive end user keys.
52 : func AssertBounds(
53 : iter FragmentIterator, lower base.InternalKey, upper []byte, cmp base.Compare,
54 1 : ) FragmentIterator {
55 1 : i := &assertIter{
56 1 : iter: iter,
57 1 : cmp: cmp,
58 1 : }
59 1 : i.checkBounds.enabled = true
60 1 : i.checkBounds.lower = lower
61 1 : i.checkBounds.upper = upper
62 1 : return i
63 1 : }
64 :
65 : // assertIter is a pass-through FragmentIterator wrapper which performs checks
66 : // on what the wrapped iterator returns.
67 : //
68 : // It verifies that results for various operations are sane, and it optionally
69 : // verifies that spans are within given bounds.
70 : type assertIter struct {
71 : iter FragmentIterator
72 : cmp base.Compare
73 : checkBounds struct {
74 : enabled bool
75 : lower base.InternalKey
76 : upper []byte
77 : }
78 : lastSpanStart []byte
79 : lastSpanEnd []byte
80 : }
81 :
82 : var _ FragmentIterator = (*assertIter)(nil)
83 :
84 0 : func (i *assertIter) panicf(format string, args ...interface{}) {
85 0 : str := fmt.Sprintf(format, args...)
86 0 : panic(errors.AssertionFailedf("%s; wraps %T", str, i.iter))
87 : }
88 :
89 1 : func (i *assertIter) check(span *Span) {
90 1 : i.lastSpanStart = i.lastSpanStart[:0]
91 1 : i.lastSpanEnd = i.lastSpanEnd[:0]
92 1 : if span == nil {
93 1 : return
94 1 : }
95 1 : if i.checkBounds.enabled {
96 1 : lower := i.checkBounds.lower
97 1 : switch startCmp := i.cmp(span.Start, lower.UserKey); {
98 0 : case startCmp < 0:
99 0 : i.panicf("lower bound %q violated by span %s", lower.UserKey, span)
100 1 : case startCmp == 0:
101 1 : // Note: trailers are in descending order.
102 1 : if len(span.Keys) > 0 && span.SmallestKey().Trailer > lower.Trailer {
103 0 : i.panicf("lower bound %s violated by key %s", lower, span.SmallestKey())
104 0 : }
105 : }
106 1 : if i.cmp(span.End, i.checkBounds.upper) > 0 {
107 0 : i.panicf("upper bound %q violated by span %s", i.checkBounds.upper, span)
108 0 : }
109 : }
110 : // Save the span to check Next/Prev operations.
111 1 : i.lastSpanStart = append(i.lastSpanStart, span.Start...)
112 1 : i.lastSpanEnd = append(i.lastSpanEnd, span.End...)
113 : }
114 :
115 : // SeekGE implements FragmentIterator.
116 1 : func (i *assertIter) SeekGE(key []byte) (*Span, error) {
117 1 : span, err := i.iter.SeekGE(key)
118 1 : if span != nil && i.cmp(span.End, key) <= 0 {
119 0 : i.panicf("incorrect SeekGE(%q) span %s", key, span)
120 0 : }
121 1 : i.check(span)
122 1 : return span, err
123 : }
124 :
125 : // SeekLT implements FragmentIterator.
126 1 : func (i *assertIter) SeekLT(key []byte) (*Span, error) {
127 1 : span, err := i.iter.SeekLT(key)
128 1 : if span != nil && i.cmp(span.Start, key) >= 0 {
129 0 : i.panicf("incorrect SeekLT(%q) span %s", key, span)
130 0 : }
131 1 : i.check(span)
132 1 : return span, err
133 : }
134 :
135 : // First implements FragmentIterator.
136 1 : func (i *assertIter) First() (*Span, error) {
137 1 : span, err := i.iter.First()
138 1 : i.check(span)
139 1 : return span, err
140 1 : }
141 :
142 : // Last implements FragmentIterator.
143 1 : func (i *assertIter) Last() (*Span, error) {
144 1 : span, err := i.iter.Last()
145 1 : i.check(span)
146 1 : return span, err
147 1 : }
148 :
149 : // Next implements FragmentIterator.
150 1 : func (i *assertIter) Next() (*Span, error) {
151 1 : span, err := i.iter.Next()
152 1 : if span != nil && len(i.lastSpanEnd) > 0 && i.cmp(i.lastSpanEnd, span.Start) > 0 {
153 0 : i.panicf("Next span %s not after last span end %q", span, i.lastSpanEnd)
154 0 : }
155 1 : i.check(span)
156 1 : return span, err
157 : }
158 :
159 : // Prev implements FragmentIterator.
160 1 : func (i *assertIter) Prev() (*Span, error) {
161 1 : span, err := i.iter.Prev()
162 1 : if span != nil && len(i.lastSpanStart) > 0 && i.cmp(i.lastSpanStart, span.End) < 0 {
163 0 : i.panicf("Prev span %s not before last span start %q", span, i.lastSpanStart)
164 0 : }
165 1 : i.check(span)
166 1 : return span, err
167 : }
168 :
169 : // SetContext is part of the FragmentIterator interface.
170 0 : func (i *assertIter) SetContext(ctx context.Context) {
171 0 : i.iter.SetContext(ctx)
172 0 : }
173 :
174 : // Close implements FragmentIterator.
175 1 : func (i *assertIter) Close() {
176 1 : i.iter.Close()
177 1 : }
178 :
179 : // WrapChildren implements FragmentIterator.
180 0 : func (i *assertIter) WrapChildren(wrap WrapFn) {
181 0 : i.iter = wrap(i.iter)
182 0 : }
183 :
184 : // DebugTree is part of the FragmentIterator interface.
185 0 : func (i *assertIter) DebugTree(tp treeprinter.Node) {
186 0 : n := tp.Childf("%T(%p)", i, i)
187 0 : if i.iter != nil {
188 0 : i.iter.DebugTree(n)
189 0 : }
190 : }
|
