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.
      20           1 : func TryToSimplifyKeys(opsData []byte, retainSuffixes bool) []byte {
      21           1 :         ops, err := parse(opsData, parserOpts{})
      22           1 :         if err != nil {
      23           0 :                 panic(err)
      24             :         }
      25           1 :         keys := make(map[string]struct{})
      26           1 :         for i := range ops {
      27           1 :                 for _, k := range ops[i].keys() {
      28           1 :                         key := *k
      29           1 :                         if retainSuffixes {
      30           1 :                                 key = key[:testkeys.Comparer.Split(key)]
      31           1 :                         }
      32           1 :                         keys[string(key)] = struct{}{}
      33             :                 }
      34             :         }
      35           1 :         if len(keys) > ('z' - 'a' + 1) {
      36           0 :                 return nil
      37           0 :         }
      38           1 :         sorted := sortedKeys(keys)
      39           1 :         ordinals := make(map[string]int, len(sorted))
      40           1 :         for i, k := range sorted {
      41           1 :                 ordinals[k] = i
      42           1 :         }
      43           1 :         for i := range ops {
      44           1 :                 for _, k := range ops[i].keys() {
      45           1 :                         key := *k
      46           1 :                         var suffix []byte
      47           1 :                         if retainSuffixes {
      48           1 :                                 n := testkeys.Comparer.Split(key)
      49           1 :                                 suffix = key[n:]
      50           1 :                                 key = key[:n]
      51           1 :                         }
      52           1 :                         idx := ordinals[string(key)]
      53           1 :                         newKey := []byte{'a' + byte(idx)}
      54           1 :                         newKey = append(newKey, suffix...)
      55           1 :                         *k = newKey
      56             :                 }
      57             :         }
      58           1 :         return []byte(formatOps(ops))
      59             : }
      60             : 
      61           1 : func sortedKeys(in map[string]struct{}) []string {
      62           1 :         var sorted []string
      63           1 :         for k := range in {
      64           1 :                 sorted = append(sorted, k)
      65           1 :         }
      66           1 :         sort.Slice(sorted, func(i, j int) bool {
      67           1 :                 return testkeys.Comparer.Compare([]byte(sorted[i]), []byte(sorted[j])) < 0
      68           1 :         })
      69           1 :         return sorted
      70             : }