Line data    Source code

       1             : // Copyright 2024 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             :         "sort"
       9             : 
      10             :         "github.com/cockroachdb/pebble/internal/testkeys"
      11             : )
      12             : 
      13             : // TryToSimplifyKeys parses the operations data and tries to reassign keys to
      14             : // single lowercase characters. Note that the result is not necessarily
      15             : // semantically equivalent.
      16             : //
      17             : // On success it returns the new operations data.
      18             : //
      19             : // If there are too many distinct keys, returns nil (and no error).
      20           1 : func TryToSimplifyKeys(opsData []byte) ([]byte, error) {
      21           1 :         ops, err := parse(opsData, parserOpts{})
      22           1 :         if err != nil {
      23           0 :                 return nil, err
      24           0 :         }
      25           1 :         keys := make(map[string]struct{})
      26           1 :         for i := range ops {
      27           1 :                 for _, k := range ops[i].keys() {
      28           1 :                         keys[string(*k)] = struct{}{}
      29           1 :                 }
      30             :         }
      31           1 :         if len(keys) > ('z' - 'a' + 1) {
      32           0 :                 return nil, nil
      33           0 :         }
      34           1 :         sorted := sortedKeys(keys)
      35           1 :         ordinals := make(map[string]int, len(sorted))
      36           1 :         for i, k := range sorted {
      37           1 :                 ordinals[k] = i
      38           1 :         }
      39             :         // TODO(radu): We reassign the user keys, ignoring the prefix and suffix
      40             :         // composition. This is sufficient to reproduce a class of problems, but if it
      41             :         // fails, we should try to simplify just the prefix and retain the suffix.
      42           1 :         for i := range ops {
      43           1 :                 for _, k := range ops[i].keys() {
      44           1 :                         idx := ordinals[string(*k)]
      45           1 :                         *k = []byte{'a' + byte(idx)}
      46           1 :                 }
      47             :         }
      48           1 :         return []byte(formatOps(ops)), nil
      49             : }
      50             : 
      51           1 : func sortedKeys(in map[string]struct{}) []string {
      52           1 :         var sorted []string
      53           1 :         for k := range in {
      54           1 :                 sorted = append(sorted, k)
      55           1 :         }
      56           1 :         sort.Slice(sorted, func(i, j int) bool {
      57           1 :                 return testkeys.Comparer.Compare([]byte(sorted[i]), []byte(sorted[j])) < 0
      58           1 :         })
      59           1 :         return sorted
      60             : }