nodes_test.go

Documentation: github.com/transparency-dev/merkle/compact

     1  // Copyright 2019 Google LLC. All Rights Reserved.
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package compact
    16  
    17  import (
    18  	"fmt"
    19  	"testing"
    20  
    21  	"github.com/google/go-cmp/cmp"
    22  )
    23  
    24  func TestRangeNodesAndSize(t *testing.T) {
    25  	n := func(level uint, index uint64) NodeID {
    26  		return NewNodeID(level, index)
    27  	}
    28  	for _, tc := range []struct {
    29  		begin uint64
    30  		end   uint64
    31  		want  []NodeID
    32  	}{
    33  		// Empty ranges.
    34  		{end: 0, want: nil},
    35  		{begin: 10, end: 10, want: nil},
    36  		{begin: 1024, end: 1024, want: nil},
    37  		// One entry.
    38  		{begin: 10, end: 11, want: []NodeID{n(0, 10)}},
    39  		{begin: 1024, end: 1025, want: []NodeID{n(0, 1024)}},
    40  		{begin: 1025, end: 1026, want: []NodeID{n(0, 1025)}},
    41  		// Two entries.
    42  		{begin: 10, end: 12, want: []NodeID{n(1, 5)}},
    43  		{begin: 1024, end: 1026, want: []NodeID{n(1, 512)}},
    44  		{begin: 1025, end: 1027, want: []NodeID{n(0, 1025), n(0, 1026)}},
    45  		// Only right border.
    46  		{end: 1, want: []NodeID{n(0, 0)}},
    47  		{end: 2, want: []NodeID{n(1, 0)}},
    48  		{end: 3, want: []NodeID{n(1, 0), n(0, 2)}},
    49  		{end: 4, want: []NodeID{n(2, 0)}},
    50  		{end: 5, want: []NodeID{n(2, 0), n(0, 4)}},
    51  		{end: 15, want: []NodeID{n(3, 0), n(2, 2), n(1, 6), n(0, 14)}},
    52  		{end: 100, want: []NodeID{n(6, 0), n(5, 2), n(2, 24)}},
    53  		{end: 513, want: []NodeID{n(9, 0), n(0, 512)}},
    54  		{end: uint64(1) << 63, want: []NodeID{n(63, 0)}},
    55  		{end: (uint64(1) << 63) + (uint64(1) << 57), want: []NodeID{n(63, 0), n(57, 64)}},
    56  		// Only left border.
    57  		{begin: 0, end: 16, want: []NodeID{n(4, 0)}},
    58  		{begin: 1, end: 16, want: []NodeID{n(0, 1), n(1, 1), n(2, 1), n(3, 1)}},
    59  		{begin: 2, end: 16, want: []NodeID{n(1, 1), n(2, 1), n(3, 1)}},
    60  		{begin: 3, end: 16, want: []NodeID{n(0, 3), n(2, 1), n(3, 1)}},
    61  		{begin: 4, end: 16, want: []NodeID{n(2, 1), n(3, 1)}},
    62  		{begin: 6, end: 16, want: []NodeID{n(1, 3), n(3, 1)}},
    63  		{begin: 8, end: 16, want: []NodeID{n(3, 1)}},
    64  		{begin: 11, end: 16, want: []NodeID{n(0, 11), n(2, 3)}},
    65  		// Two-sided.
    66  		{begin: 1, end: 31, want: []NodeID{n(0, 1), n(1, 1), n(2, 1), n(3, 1), n(3, 2), n(2, 6), n(1, 14), n(0, 30)}},
    67  		{begin: 1, end: 17, want: []NodeID{n(0, 1), n(1, 1), n(2, 1), n(3, 1), n(0, 16)}},
    68  	} {
    69  		t.Run(fmt.Sprintf("range:%d:%d", tc.begin, tc.end), func(t *testing.T) {
    70  			got := RangeNodes(tc.begin, tc.end, nil)
    71  			if diff := cmp.Diff(got, tc.want); diff != "" {
    72  				t.Fatalf("RangeNodes: diff(-want +got):\n%s", diff)
    73  			}
    74  			if got, want := RangeSize(tc.begin, tc.end), len(tc.want); got != want {
    75  				t.Errorf("RangeSize: got %d, want %d", got, want)
    76  			}
    77  		})
    78  	}
    79  }
    80  
    81  func TestRangeNodesAppend(t *testing.T) {
    82  	prefix := []NodeID{NewNodeID(0, 0), NewNodeID(10, 0), NewNodeID(11, 5)}
    83  	nodes := RangeNodes(123, 456, prefix)
    84  
    85  	if got, min := len(nodes), len(prefix); got < min {
    86  		t.Fatalf("RangeNodes returned %d IDs, want >= %d", got, min)
    87  	}
    88  	got := nodes[:len(prefix)]
    89  	if diff := cmp.Diff(got, prefix); diff != "" {
    90  		t.Fatalf("RangeNodes: diff(-prefix +got):\n%s", diff)
    91  	}
    92  }
    93  
    94  func TestGenRangeNodes(t *testing.T) {
    95  	const size = uint64(512)
    96  	for begin := uint64(0); begin <= size; begin++ {
    97  		for end := begin; end <= size; end++ {
    98  			got := RangeNodes(begin, end, nil)
    99  			want := refRangeNodes(NewNodeID(63, 0), begin, end)
   100  			if diff := cmp.Diff(got, want); diff != "" {
   101  				t.Fatalf("RangeNodes(%d, %d): diff(-want +got):\n%s", begin, end, diff)
   102  			}
   103  		}
   104  	}
   105  }
   106  
   107  // refRangeNodes returns node IDs that comprise the [begin, end) compact range.
   108  // This is a reference implementation for cross-checking.
   109  func refRangeNodes(root NodeID, begin, end uint64) []NodeID {
   110  	b, e := root.Coverage()
   111  	if end <= b || begin >= e {
   112  		return nil
   113  	}
   114  	if b >= begin && e <= end {
   115  		return []NodeID{root}
   116  	}
   117  	return append(
   118  		refRangeNodes(NewNodeID(root.Level-1, root.Index*2), begin, end),
   119  		refRangeNodes(NewNodeID(root.Level-1, root.Index*2+1), begin, end)...)
   120  }
   121
View as plain text