Line data Source code
1 : // Copyright 2019 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 metamorphic
6 :
7 : import (
8 : "fmt"
9 : "go/scanner"
10 : "go/token"
11 : "reflect"
12 : "strconv"
13 : "strings"
14 :
15 : "github.com/cockroachdb/errors"
16 : "github.com/cockroachdb/pebble"
17 : )
18 :
19 : type methodInfo struct {
20 : constructor func() op
21 : validTags uint32
22 : }
23 :
24 2 : func makeMethod(i interface{}, tags ...objTag) *methodInfo {
25 2 : var validTags uint32
26 2 : for _, tag := range tags {
27 2 : validTags |= 1 << tag
28 2 : }
29 :
30 2 : t := reflect.TypeOf(i)
31 2 : return &methodInfo{
32 2 : constructor: func() op {
33 2 : return reflect.New(t).Interface().(op)
34 2 : },
35 : validTags: validTags,
36 : }
37 : }
38 :
39 : // args returns the receiverID, targetID and arguments for the op. The
40 : // receiverID is the ID of the object the op will be applied to. The targetID
41 : // is the ID of the object for assignment. If the method does not return a new
42 : // object, then targetID will be nil. The argument list is just what it sounds
43 : // like: the list of arguments for the operation.
44 2 : func opArgs(op op) (receiverID *objID, targetID *objID, args []interface{}) {
45 2 : switch t := op.(type) {
46 2 : case *applyOp:
47 2 : return &t.writerID, nil, []interface{}{&t.batchID}
48 2 : case *checkpointOp:
49 2 : return nil, nil, []interface{}{&t.spans}
50 2 : case *closeOp:
51 2 : return &t.objID, nil, nil
52 2 : case *compactOp:
53 2 : return nil, nil, []interface{}{&t.start, &t.end, &t.parallelize}
54 2 : case *batchCommitOp:
55 2 : return &t.batchID, nil, nil
56 2 : case *dbRatchetFormatMajorVersionOp:
57 2 : return nil, nil, []interface{}{&t.vers}
58 2 : case *dbRestartOp:
59 2 : return nil, nil, nil
60 2 : case *deleteOp:
61 2 : return &t.writerID, nil, []interface{}{&t.key}
62 2 : case *deleteRangeOp:
63 2 : return &t.writerID, nil, []interface{}{&t.start, &t.end}
64 2 : case *iterFirstOp:
65 2 : return &t.iterID, nil, nil
66 2 : case *flushOp:
67 2 : return nil, nil, nil
68 2 : case *getOp:
69 2 : return &t.readerID, nil, []interface{}{&t.key}
70 2 : case *ingestOp:
71 2 : return nil, nil, []interface{}{&t.batchIDs}
72 2 : case *initOp:
73 2 : return nil, nil, []interface{}{&t.batchSlots, &t.iterSlots, &t.snapshotSlots}
74 2 : case *iterLastOp:
75 2 : return &t.iterID, nil, nil
76 2 : case *mergeOp:
77 2 : return &t.writerID, nil, []interface{}{&t.key, &t.value}
78 2 : case *newBatchOp:
79 2 : return nil, &t.batchID, nil
80 2 : case *newIndexedBatchOp:
81 2 : return nil, &t.batchID, nil
82 2 : case *newIterOp:
83 2 : return &t.readerID, &t.iterID, []interface{}{&t.lower, &t.upper, &t.keyTypes, &t.filterMin, &t.filterMax, &t.useL6Filters, &t.maskSuffix}
84 2 : case *newIterUsingCloneOp:
85 2 : return &t.existingIterID, &t.iterID, []interface{}{&t.refreshBatch, &t.lower, &t.upper, &t.keyTypes, &t.filterMin, &t.filterMax, &t.useL6Filters, &t.maskSuffix}
86 2 : case *newSnapshotOp:
87 2 : return nil, &t.snapID, []interface{}{&t.bounds}
88 2 : case *iterNextOp:
89 2 : return &t.iterID, nil, []interface{}{&t.limit}
90 2 : case *iterNextPrefixOp:
91 2 : return &t.iterID, nil, nil
92 2 : case *iterPrevOp:
93 2 : return &t.iterID, nil, []interface{}{&t.limit}
94 2 : case *iterSeekLTOp:
95 2 : return &t.iterID, nil, []interface{}{&t.key, &t.limit}
96 2 : case *iterSeekGEOp:
97 2 : return &t.iterID, nil, []interface{}{&t.key, &t.limit}
98 2 : case *iterSeekPrefixGEOp:
99 2 : return &t.iterID, nil, []interface{}{&t.key}
100 2 : case *setOp:
101 2 : return &t.writerID, nil, []interface{}{&t.key, &t.value}
102 2 : case *iterSetBoundsOp:
103 2 : return &t.iterID, nil, []interface{}{&t.lower, &t.upper}
104 2 : case *iterSetOptionsOp:
105 2 : return &t.iterID, nil, []interface{}{&t.lower, &t.upper, &t.keyTypes, &t.filterMin, &t.filterMax, &t.useL6Filters, &t.maskSuffix}
106 2 : case *singleDeleteOp:
107 2 : return &t.writerID, nil, []interface{}{&t.key, &t.maybeReplaceDelete}
108 2 : case *rangeKeyDeleteOp:
109 2 : return &t.writerID, nil, []interface{}{&t.start, &t.end}
110 2 : case *rangeKeySetOp:
111 2 : return &t.writerID, nil, []interface{}{&t.start, &t.end, &t.suffix, &t.value}
112 2 : case *rangeKeyUnsetOp:
113 2 : return &t.writerID, nil, []interface{}{&t.start, &t.end, &t.suffix}
114 : }
115 0 : panic(fmt.Sprintf("unsupported op type: %T", op))
116 : }
117 :
118 : var methods = map[string]*methodInfo{
119 : "Apply": makeMethod(applyOp{}, dbTag, batchTag),
120 : "Checkpoint": makeMethod(checkpointOp{}, dbTag),
121 : "Clone": makeMethod(newIterUsingCloneOp{}, iterTag),
122 : "Close": makeMethod(closeOp{}, dbTag, batchTag, iterTag, snapTag),
123 : "Commit": makeMethod(batchCommitOp{}, batchTag),
124 : "Compact": makeMethod(compactOp{}, dbTag),
125 : "Delete": makeMethod(deleteOp{}, dbTag, batchTag),
126 : "DeleteRange": makeMethod(deleteRangeOp{}, dbTag, batchTag),
127 : "First": makeMethod(iterFirstOp{}, iterTag),
128 : "Flush": makeMethod(flushOp{}, dbTag),
129 : "Get": makeMethod(getOp{}, dbTag, batchTag, snapTag),
130 : "Ingest": makeMethod(ingestOp{}, dbTag),
131 : "Init": makeMethod(initOp{}, dbTag),
132 : "Last": makeMethod(iterLastOp{}, iterTag),
133 : "Merge": makeMethod(mergeOp{}, dbTag, batchTag),
134 : "NewBatch": makeMethod(newBatchOp{}, dbTag),
135 : "NewIndexedBatch": makeMethod(newIndexedBatchOp{}, dbTag),
136 : "NewIter": makeMethod(newIterOp{}, dbTag, batchTag, snapTag),
137 : "NewSnapshot": makeMethod(newSnapshotOp{}, dbTag),
138 : "Next": makeMethod(iterNextOp{}, iterTag),
139 : "NextPrefix": makeMethod(iterNextPrefixOp{}, iterTag),
140 : "Prev": makeMethod(iterPrevOp{}, iterTag),
141 : "RangeKeyDelete": makeMethod(rangeKeyDeleteOp{}, dbTag, batchTag),
142 : "RangeKeySet": makeMethod(rangeKeySetOp{}, dbTag, batchTag),
143 : "RangeKeyUnset": makeMethod(rangeKeyUnsetOp{}, dbTag, batchTag),
144 : "RatchetFormatMajorVersion": makeMethod(dbRatchetFormatMajorVersionOp{}, dbTag),
145 : "Restart": makeMethod(dbRestartOp{}, dbTag),
146 : "SeekGE": makeMethod(iterSeekGEOp{}, iterTag),
147 : "SeekLT": makeMethod(iterSeekLTOp{}, iterTag),
148 : "SeekPrefixGE": makeMethod(iterSeekPrefixGEOp{}, iterTag),
149 : "Set": makeMethod(setOp{}, dbTag, batchTag),
150 : "SetBounds": makeMethod(iterSetBoundsOp{}, iterTag),
151 : "SetOptions": makeMethod(iterSetOptionsOp{}, iterTag),
152 : "SingleDelete": makeMethod(singleDeleteOp{}, dbTag, batchTag),
153 : }
154 :
155 : type parser struct {
156 : fset *token.FileSet
157 : s scanner.Scanner
158 : objs map[objID]bool
159 : }
160 :
161 2 : func parse(src []byte) (_ []op, err error) {
162 2 : // Various bits of magic incantation to set up a scanner for Go compatible
163 2 : // syntax. We arranged for the textual format of ops (e.g. op.String()) to
164 2 : // look like Go which allows us to use the Go scanner for parsing.
165 2 : p := &parser{
166 2 : fset: token.NewFileSet(),
167 2 : objs: map[objID]bool{makeObjID(dbTag, 0): true},
168 2 : }
169 2 : file := p.fset.AddFile("", -1, len(src))
170 2 : p.s.Init(file, src, nil /* no error handler */, 0)
171 2 : return p.parse()
172 2 : }
173 :
174 2 : func (p *parser) parse() (_ []op, err error) {
175 2 : defer func() {
176 2 : if r := recover(); r != nil {
177 1 : var ok bool
178 1 : if err, ok = r.(error); ok {
179 1 : return
180 1 : }
181 0 : err = errors.Errorf("%v", r)
182 : }
183 : }()
184 :
185 2 : var ops []op
186 2 : for {
187 2 : op := p.parseOp()
188 2 : if op == nil {
189 2 : computeDerivedFields(ops)
190 2 : return ops, nil
191 2 : }
192 2 : ops = append(ops, op)
193 : }
194 : }
195 :
196 2 : func (p *parser) parseOp() op {
197 2 : destPos, destTok, destLit := p.s.Scan()
198 2 : if destTok == token.EOF {
199 2 : return nil
200 2 : }
201 2 : if destTok != token.IDENT {
202 1 : panic(p.errorf(destPos, "unexpected token: %s %q", destTok, destLit))
203 : }
204 2 : if destLit == "Init" {
205 2 : // <op>(<args>)
206 2 : return p.makeOp(destLit, makeObjID(dbTag, 0), 0, destPos)
207 2 : }
208 :
209 2 : destID := p.parseObjID(destPos, destLit)
210 2 :
211 2 : pos, tok, lit := p.s.Scan()
212 2 : switch tok {
213 2 : case token.PERIOD:
214 2 : // <obj>.<op>(<args>)
215 2 : if !p.objs[destID] {
216 0 : panic(p.errorf(destPos, "unknown object: %s", destID))
217 : }
218 2 : _, methodLit := p.scanToken(token.IDENT)
219 2 : return p.makeOp(methodLit, destID, 0, destPos)
220 :
221 2 : case token.ASSIGN:
222 2 : // <obj> = <obj>.<op>(<args>)
223 2 : srcPos, srcLit := p.scanToken(token.IDENT)
224 2 : srcID := p.parseObjID(srcPos, srcLit)
225 2 : if !p.objs[srcID] {
226 0 : panic(p.errorf(srcPos, "unknown object %q", srcLit))
227 : }
228 2 : p.scanToken(token.PERIOD)
229 2 : _, methodLit := p.scanToken(token.IDENT)
230 2 : p.objs[destID] = true
231 2 : return p.makeOp(methodLit, srcID, destID, srcPos)
232 : }
233 0 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
234 : }
235 :
236 2 : func (p *parser) parseObjID(pos token.Pos, str string) objID {
237 2 : var tag objTag
238 2 : switch {
239 2 : case str == "db":
240 2 : return makeObjID(dbTag, 0)
241 2 : case strings.HasPrefix(str, "batch"):
242 2 : tag, str = batchTag, str[5:]
243 2 : case strings.HasPrefix(str, "iter"):
244 2 : tag, str = iterTag, str[4:]
245 2 : case strings.HasPrefix(str, "snap"):
246 2 : tag, str = snapTag, str[4:]
247 1 : default:
248 1 : panic(p.errorf(pos, "unable to parse objectID: %q", str))
249 : }
250 2 : id, err := strconv.ParseInt(str, 10, 32)
251 2 : if err != nil {
252 0 : panic(p.errorf(pos, "%s", err))
253 : }
254 2 : return makeObjID(tag, uint32(id))
255 : }
256 :
257 2 : func unquoteBytes(lit string) []byte {
258 2 : s, err := strconv.Unquote(lit)
259 2 : if err != nil {
260 0 : panic(err)
261 : }
262 2 : if len(s) == 0 {
263 2 : return nil
264 2 : }
265 2 : return []byte(s)
266 : }
267 :
268 2 : func (p *parser) parseArgs(op op, methodName string, args []interface{}) {
269 2 : pos, _ := p.scanToken(token.LPAREN)
270 2 : for i := range args {
271 2 : if i > 0 {
272 2 : pos, _ = p.scanToken(token.COMMA)
273 2 : }
274 :
275 2 : switch t := args[i].(type) {
276 2 : case *uint32:
277 2 : _, lit := p.scanToken(token.INT)
278 2 : val, err := strconv.ParseUint(lit, 10, 32)
279 2 : if err != nil {
280 0 : panic(err)
281 : }
282 2 : *t = uint32(val)
283 :
284 2 : case *uint64:
285 2 : _, lit := p.scanToken(token.INT)
286 2 : val, err := strconv.ParseUint(lit, 10, 64)
287 2 : if err != nil {
288 0 : panic(err)
289 : }
290 2 : *t = uint64(val)
291 :
292 2 : case *[]byte:
293 2 : _, lit := p.scanToken(token.STRING)
294 2 : *t = unquoteBytes(lit)
295 :
296 2 : case *bool:
297 2 : _, lit := p.scanToken(token.IDENT)
298 2 : b, err := strconv.ParseBool(lit)
299 2 : if err != nil {
300 0 : panic(err)
301 : }
302 2 : *t = b
303 :
304 2 : case *objID:
305 2 : pos, lit := p.scanToken(token.IDENT)
306 2 : *t = p.parseObjID(pos, lit)
307 :
308 2 : case *[]pebble.KeyRange:
309 2 : var pending pebble.KeyRange
310 2 : for {
311 2 : pos, tok, lit := p.s.Scan()
312 2 : switch tok {
313 2 : case token.STRING:
314 2 : x := unquoteBytes(lit)
315 2 : if pending.Start == nil {
316 2 : pending.Start = x
317 2 : } else {
318 2 : pending.End = x
319 2 : *t = append(*t, pending)
320 2 : pending = pebble.KeyRange{}
321 2 : }
322 2 : pos, tok, lit := p.s.Scan()
323 2 : switch tok {
324 2 : case token.COMMA:
325 2 : continue
326 2 : case token.RPAREN:
327 2 : p.scanToken(token.SEMICOLON)
328 2 : return
329 0 : default:
330 0 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
331 : }
332 2 : case token.RPAREN:
333 2 : p.scanToken(token.SEMICOLON)
334 2 : return
335 0 : default:
336 0 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
337 : }
338 : }
339 :
340 2 : case *[]objID:
341 2 : for {
342 2 : pos, tok, lit := p.s.Scan()
343 2 : switch tok {
344 2 : case token.IDENT:
345 2 : *t = append(*t, p.parseObjID(pos, lit))
346 2 : pos, tok, lit := p.s.Scan()
347 2 : switch tok {
348 2 : case token.COMMA:
349 2 : continue
350 2 : case token.RPAREN:
351 2 : p.scanToken(token.SEMICOLON)
352 2 : return
353 0 : default:
354 0 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
355 : }
356 0 : case token.RPAREN:
357 0 : p.scanToken(token.SEMICOLON)
358 0 : return
359 0 : default:
360 0 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
361 : }
362 : }
363 :
364 2 : case *[]pebble.CheckpointSpan:
365 2 : pos, tok, lit := p.s.Scan()
366 2 : switch tok {
367 2 : case token.RPAREN:
368 2 : // No spans.
369 2 : *t = nil
370 2 : p.scanToken(token.SEMICOLON)
371 2 : return
372 :
373 2 : case token.STRING:
374 2 : var keys [][]byte
375 2 : for {
376 2 : s, err := strconv.Unquote(lit)
377 2 : if err != nil {
378 0 : panic(p.errorf(pos, "unquoting %q: %v", lit, err))
379 : }
380 2 : keys = append(keys, []byte(s))
381 2 :
382 2 : pos, tok, lit = p.s.Scan()
383 2 : switch tok {
384 2 : case token.COMMA:
385 2 : pos, tok, lit = p.s.Scan()
386 2 : if tok != token.STRING {
387 0 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
388 : }
389 2 : continue
390 :
391 2 : case token.RPAREN:
392 2 : p.scanToken(token.SEMICOLON)
393 2 : if len(keys)%2 == 1 {
394 0 : panic(p.errorf(pos, "expected even number of keys"))
395 : }
396 2 : *t = make([]pebble.CheckpointSpan, len(keys)/2)
397 2 : for i := range *t {
398 2 : (*t)[i] = pebble.CheckpointSpan{
399 2 : Start: keys[i*2],
400 2 : End: keys[i*2+1],
401 2 : }
402 2 : }
403 2 : return
404 :
405 0 : default:
406 0 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
407 : }
408 : }
409 :
410 0 : default:
411 0 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
412 : }
413 :
414 2 : case *pebble.FormatMajorVersion:
415 2 : _, lit := p.scanToken(token.INT)
416 2 : val, err := strconv.ParseUint(lit, 10, 64)
417 2 : if err != nil {
418 0 : panic(err)
419 : }
420 2 : *t = pebble.FormatMajorVersion(val)
421 :
422 0 : default:
423 0 : panic(p.errorf(pos, "%s: unsupported arg[%d] type: %T", methodName, i, args[i]))
424 : }
425 : }
426 2 : p.scanToken(token.RPAREN)
427 2 : p.scanToken(token.SEMICOLON)
428 : }
429 :
430 2 : func (p *parser) scanToken(expected token.Token) (pos token.Pos, lit string) {
431 2 : pos, tok, lit := p.s.Scan()
432 2 : if tok != expected {
433 1 : panic(p.errorf(pos, "unexpected token: %q", p.tokenf(tok, lit)))
434 : }
435 2 : return pos, lit
436 : }
437 :
438 2 : func (p *parser) makeOp(methodName string, receiverID, targetID objID, pos token.Pos) op {
439 2 : info := methods[methodName]
440 2 : if info == nil {
441 1 : panic(p.errorf(pos, "unknown op %s.%s", receiverID, methodName))
442 : }
443 2 : if info.validTags&(1<<receiverID.tag()) == 0 {
444 1 : panic(p.errorf(pos, "%s.%s: %s is not a method on %s",
445 1 : receiverID, methodName, methodName, receiverID))
446 : }
447 :
448 2 : op := info.constructor()
449 2 : receiver, target, args := opArgs(op)
450 2 :
451 2 : // The form of an operation is:
452 2 : // [target =] receiver.method(args)
453 2 : //
454 2 : // The receiver is the object the operation will be called on, which can be
455 2 : // any valid ID. Certain operations such as Ingest are only valid on the DB
456 2 : // object. That is indicated by opArgs returning a nil receiver.
457 2 : if receiver != nil {
458 2 : *receiver = receiverID
459 2 : } else if receiverID.tag() != dbTag {
460 0 : panic(p.errorf(pos, "unknown op %s.%s", receiverID, methodName))
461 : }
462 :
463 : // The target is the object that will be assigned the result of an object
464 : // creation operation such as newBatchOp or newIterOp.
465 2 : if target != nil {
466 2 : // It is invalid to not have a targetID for a method which generates a new
467 2 : // object.
468 2 : if targetID == 0 {
469 1 : panic(p.errorf(pos, "assignment expected for %s.%s", receiverID, methodName))
470 : }
471 : // It is invalid to try to assign to the DB object.
472 2 : if targetID.tag() == dbTag {
473 0 : panic(p.errorf(pos, "cannot use %s as target of assignment", targetID))
474 : }
475 2 : *target = targetID
476 2 : } else if targetID != 0 {
477 1 : panic(p.errorf(pos, "cannot use %s.%s in assignment", receiverID, methodName))
478 : }
479 :
480 2 : p.parseArgs(op, methodName, args)
481 2 : return op
482 : }
483 :
484 1 : func (p *parser) tokenf(tok token.Token, lit string) string {
485 1 : if tok.IsLiteral() {
486 0 : return lit
487 0 : }
488 1 : return tok.String()
489 : }
490 :
491 1 : func (p *parser) errorf(pos token.Pos, format string, args ...interface{}) error {
492 1 : return errors.New(p.fset.Position(pos).String() + ": " + fmt.Sprintf(format, args...))
493 1 : }
494 :
495 : // computeDerivedFields makes one pass through the provided operations, filling
496 : // any derived fields. This pass must happen before execution because concurrent
497 : // execution depends on these fields.
498 2 : func computeDerivedFields(ops []op) {
499 2 : iterToReader := make(map[objID]objID)
500 2 : for i := range ops {
501 2 : switch v := ops[i].(type) {
502 2 : case *newIterOp:
503 2 : iterToReader[v.iterID] = v.readerID
504 2 : case *newIterUsingCloneOp:
505 2 : v.derivedReaderID = iterToReader[v.existingIterID]
506 2 : iterToReader[v.iterID] = v.derivedReaderID
507 2 : case *iterSetOptionsOp:
508 2 : v.derivedReaderID = iterToReader[v.iterID]
509 2 : case *iterFirstOp:
510 2 : v.derivedReaderID = iterToReader[v.iterID]
511 2 : case *iterLastOp:
512 2 : v.derivedReaderID = iterToReader[v.iterID]
513 2 : case *iterSeekGEOp:
514 2 : v.derivedReaderID = iterToReader[v.iterID]
515 2 : case *iterSeekPrefixGEOp:
516 2 : v.derivedReaderID = iterToReader[v.iterID]
517 2 : case *iterSeekLTOp:
518 2 : v.derivedReaderID = iterToReader[v.iterID]
519 2 : case *iterNextOp:
520 2 : v.derivedReaderID = iterToReader[v.iterID]
521 2 : case *iterNextPrefixOp:
522 2 : v.derivedReaderID = iterToReader[v.iterID]
523 2 : case *iterPrevOp:
524 2 : v.derivedReaderID = iterToReader[v.iterID]
525 : }
526 : }
527 : }
|
