tlog_test.go

Documentation: golang.org/x/mod/sumdb/tlog

     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  }
   270
View as plain text