.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/mod@v0.3.0/sumdb/tlog/tlog_test.go

   1 // Copyright 2019 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package tlog
   6
   7 import (
   8         "bytes"
   9         "fmt"
  10         "testing"
  11 )
  12
  13 type testHashStorage []Hash
  14
  15 func (t testHashStorage) ReadHash(level int, n int64) (Hash, error) {
  16         return t[StoredHashIndex(level, n)], nil
  17 }
  18
  19 func (t testHashStorage) ReadHashes(index []int64) ([]Hash, error) {
  20         // It's not required by HashReader that indexes be in increasing order,
  21         // but check that the functions we are testing only ever ask for
  22         // indexes in increasing order.
  23         for i := 1; i < len(index); i++ {
  24                 if index[i-1] >= index[i] {
  25                         panic("indexes out of order")
  26                 }
  27         }
  28
  29         out := make([]Hash, len(index))
  30         for i, x := range index {
  31                 out[i] = t[x]
  32         }
  33         return out, nil
  34 }
  35
  36 type testTilesStorage struct {
  37         unsaved int
  38         m       map[Tile][]byte
  39 }
  40
  41 func (t testTilesStorage) Height() int {
  42         return 2
  43 }
  44
  45 func (t *testTilesStorage) SaveTiles(tiles []Tile, data [][]byte) {
  46         t.unsaved -= len(tiles)
  47 }
  48
  49 func (t *testTilesStorage) ReadTiles(tiles []Tile) ([][]byte, error) {
  50         out := make([][]byte, len(tiles))
  51         for i, tile := range tiles {
  52                 out[i] = t.m[tile]
  53         }
  54         t.unsaved += len(tiles)
  55         return out, nil
  56 }
  57
  58 func TestTree(t *testing.T) {
  59         var trees []Hash
  60         var leafhashes []Hash
  61         var storage testHashStorage
  62         tiles := make(map[Tile][]byte)
  63         const testH = 2
  64         for i := int64(0); i < 100; i++ {
  65                 data := []byte(fmt.Sprintf("leaf %d", i))
  66                 hashes, err := StoredHashes(i, data, storage)
  67                 if err != nil {
  68                         t.Fatal(err)
  69                 }
  70                 leafhashes = append(leafhashes, RecordHash(data))
  71                 oldStorage := len(storage)
  72                 storage = append(storage, hashes...)
  73                 if count := StoredHashCount(i + 1); count != int64(len(storage)) {
  74                         t.Errorf("StoredHashCount(%d) = %d, have %d StoredHashes", i+1, count, len(storage))
  75                 }
  76                 th, err := TreeHash(i+1, storage)
  77                 if err != nil {
  78                         t.Fatal(err)
  79                 }
  80
  81                 for _, tile := range NewTiles(testH, i, i+1) {
  82                         data, err := ReadTileData(tile, storage)
  83                         if err != nil {
  84                                 t.Fatal(err)
  85                         }
  86                         old := Tile{H: tile.H, L: tile.L, N: tile.N, W: tile.W - 1}
  87                         oldData := tiles[old]
  88                         if len(oldData) != len(data)-HashSize || !bytes.Equal(oldData, data[:len(oldData)]) {
  89                                 t.Fatalf("tile %v not extending earlier tile %v", tile.Path(), old.Path())
  90                         }
  91                         tiles[tile] = data
  92                 }
  93                 for _, tile := range NewTiles(testH, 0, i+1) {
  94                         data, err := ReadTileData(tile, storage)
  95                         if err != nil {
  96                                 t.Fatal(err)
  97                         }
  98                         if !bytes.Equal(tiles[tile], data) {
  99                                 t.Fatalf("mismatch at %+v", tile)
 100                         }
 101                 }
 102                 for _, tile := range NewTiles(testH, i/2, i+1) {
 103                         data, err := ReadTileData(tile, storage)
 104                         if err != nil {
 105                                 t.Fatal(err)
 106                         }
 107                         if !bytes.Equal(tiles[tile], data) {
 108                                 t.Fatalf("mismatch at %+v", tile)
 109                         }
 110                 }
 111
 112                 // Check that all the new hashes are readable from their tiles.
 113                 for j := oldStorage; j < len(storage); j++ {
 114                         tile := TileForIndex(testH, int64(j))
 115                         data, ok := tiles[tile]
 116                         if !ok {
 117                                 t.Log(NewTiles(testH, 0, i+1))
 118                                 t.Fatalf("TileForIndex(%d, %d) = %v, not yet stored (i=%d, stored %d)", testH, j, tile.Path(), i, len(storage))
 119                                 continue
 120                         }
 121                         h, err := HashFromTile(tile, data, int64(j))
 122                         if err != nil {
 123                                 t.Fatal(err)
 124                         }
 125                         if h != storage[j] {
 126                                 t.Errorf("HashFromTile(%v, %d) = %v, want %v", tile.Path(), int64(j), h, storage[j])
 127                         }
 128                 }
 129
 130                 trees = append(trees, th)
 131
 132                 // Check that leaf proofs work, for all trees and leaves so far.
 133                 for j := int64(0); j <= i; j++ {
 134                         p, err := ProveRecord(i+1, j, storage)
 135                         if err != nil {
 136                                 t.Fatalf("ProveRecord(%d, %d): %v", i+1, j, err)
 137                         }
 138                         if err := CheckRecord(p, i+1, th, j, leafhashes[j]); err != nil {
 139                                 t.Fatalf("CheckRecord(%d, %d): %v", i+1, j, err)
 140                         }
 141                         for k := range p {
 142                                 p[k][0] ^= 1
 143                                 if err := CheckRecord(p, i+1, th, j, leafhashes[j]); err == nil {
 144                                         t.Fatalf("CheckRecord(%d, %d) succeeded with corrupt proof hash #%d!", i+1, j, k)
 145                                 }
 146                                 p[k][0] ^= 1
 147                         }
 148                 }
 149
 150                 // Check that leaf proofs work using TileReader.
 151                 // To prove a leaf that way, all you have to do is read and verify its hash.
 152                 storage := &testTilesStorage{m: tiles}
 153                 thr := TileHashReader(Tree{i + 1, th}, storage)
 154                 for j := int64(0); j <= i; j++ {
 155                         h, err := thr.ReadHashes([]int64{StoredHashIndex(0, j)})
 156                         if err != nil {
 157                                 t.Fatalf("TileHashReader(%d).ReadHashes(%d): %v", i+1, j, err)
 158                         }
 159                         if h[0] != leafhashes[j] {
 160                                 t.Fatalf("TileHashReader(%d).ReadHashes(%d) returned wrong hash", i+1, j)
 161                         }
 162
 163                         // Even though reading the hash suffices,
 164                         // check we can generate the proof too.
 165                         p, err := ProveRecord(i+1, j, thr)
 166                         if err != nil {
 167                                 t.Fatalf("ProveRecord(%d, %d, TileHashReader(%d)): %v", i+1, j, i+1, err)
 168                         }
 169                         if err := CheckRecord(p, i+1, th, j, leafhashes[j]); err != nil {
 170                                 t.Fatalf("CheckRecord(%d, %d, TileHashReader(%d)): %v", i+1, j, i+1, err)
 171                         }
 172                 }
 173                 if storage.unsaved != 0 {
 174                         t.Fatalf("TileHashReader(%d) did not save %d tiles", i+1, storage.unsaved)
 175                 }
 176
 177                 // Check that ReadHashes will give an error if the index is not in the tree.
 178                 if _, err := thr.ReadHashes([]int64{(i + 1) * 2}); err == nil {
 179                         t.Fatalf("TileHashReader(%d).ReadHashes(%d) for index not in tree <nil>, want err", i, i+1)
 180                 }
 181                 if storage.unsaved != 0 {
 182                         t.Fatalf("TileHashReader(%d) did not save %d tiles", i+1, storage.unsaved)
 183                 }
 184
 185                 // Check that tree proofs work, for all trees so far, using TileReader.
 186                 // To prove a tree that way, all you have to do is compute and verify its hash.
 187                 for j := int64(0); j <= i; j++ {
 188                         h, err := TreeHash(j+1, thr)
 189                         if err != nil {
 190                                 t.Fatalf("TreeHash(%d, TileHashReader(%d)): %v", j, i+1, err)
 191                         }
 192                         if h != trees[j] {
 193                                 t.Fatalf("TreeHash(%d, TileHashReader(%d)) = %x, want %x (%v)", j, i+1, h[:], trees[j][:], trees[j])
 194                         }
 195
 196                         // Even though computing the subtree hash suffices,
 197                         // check that we can generate the proof too.
 198                         p, err := ProveTree(i+1, j+1, thr)
 199                         if err != nil {
 200                                 t.Fatalf("ProveTree(%d, %d): %v", i+1, j+1, err)
 201                         }
 202                         if err := CheckTree(p, i+1, th, j+1, trees[j]); err != nil {
 203                                 t.Fatalf("CheckTree(%d, %d): %v [%v]", i+1, j+1, err, p)
 204                         }
 205                         for k := range p {
 206                                 p[k][0] ^= 1
 207                                 if err := CheckTree(p, i+1, th, j+1, trees[j]); err == nil {
 208                                         t.Fatalf("CheckTree(%d, %d) succeeded with corrupt proof hash #%d!", i+1, j+1, k)
 209                                 }
 210                                 p[k][0] ^= 1
 211                         }
 212                 }
 213                 if storage.unsaved != 0 {
 214                         t.Fatalf("TileHashReader(%d) did not save %d tiles", i+1, storage.unsaved)
 215                 }
 216         }
 217 }
 218
 219 func TestSplitStoredHashIndex(t *testing.T) {
 220         for l := 0; l < 10; l++ {
 221                 for n := int64(0); n < 100; n++ {
 222                         x := StoredHashIndex(l, n)
 223                         l1, n1 := SplitStoredHashIndex(x)
 224                         if l1 != l || n1 != n {
 225                                 t.Fatalf("StoredHashIndex(%d, %d) = %d, but SplitStoredHashIndex(%d) = %d, %d", l, n, x, x, l1, n1)
 226                         }
 227                 }
 228         }
 229 }
 230
 231 // TODO(rsc): Test invalid paths too, like "tile/3/5/123/456/078".
 232 var tilePaths = []struct {
 233         path string
 234         tile Tile
 235 }{
 236         {"tile/4/0/001", Tile{4, 0, 1, 16}},
 237         {"tile/4/0/001.p/5", Tile{4, 0, 1, 5}},
 238         {"tile/3/5/x123/x456/078", Tile{3, 5, 123456078, 8}},
 239         {"tile/3/5/x123/x456/078.p/2", Tile{3, 5, 123456078, 2}},
 240         {"tile/1/0/x003/x057/500", Tile{1, 0, 3057500, 2}},
 241         {"tile/3/5/123/456/078", Tile{}},
 242         {"tile/3/-1/123/456/078", Tile{}},
 243         {"tile/1/data/x003/x057/500", Tile{1, -1, 3057500, 2}},
 244 }
 245
 246 func TestTilePath(t *testing.T) {
 247         for _, tt := range tilePaths {
 248                 if tt.tile.H > 0 {
 249                         p := tt.tile.Path()
 250                         if p != tt.path {
 251                                 t.Errorf("%+v.Path() = %q, want %q", tt.tile, p, tt.path)
 252                         }
 253                 }
 254                 tile, err := ParseTilePath(tt.path)
 255                 if err != nil {
 256                         if tt.tile.H == 0 {
 257                                 // Expected error.
 258                                 continue
 259                         }
 260                         t.Errorf("ParseTilePath(%q): %v", tt.path, err)
 261                 } else if tile != tt.tile {
 262                         if tt.tile.H == 0 {
 263                                 t.Errorf("ParseTilePath(%q): expected error, got %+v", tt.path, tt.tile)
 264                                 continue
 265                         }
 266                         t.Errorf("ParseTilePath(%q) = %+v, want %+v", tt.path, tile, tt.tile)
 267                 }
 268         }
 269 }