func TestCalcInclusionProofNodeAddresses(t *testing.T) {
	node := func(level uint, index uint64) NodeFetch {
		return newNodeFetch(level, index, false)
	}
	rehash := func(level uint, index uint64) NodeFetch {
		return newNodeFetch(level, index, true)
	}
	for _, tc := range []struct {
		size    int64  
		index   int64  
		want    []NodeFetch
		wantErr bool
	}{
		{size: 0, index: 0, wantErr: true},
		{size: 0, index: 1, wantErr: true},
		{size: 1, index: 2, wantErr: true},
		{size: 0, index: 3, wantErr: true},
		{size: -1, index: 3, wantErr: true},
		{size: 7, index: -1, wantErr: true},
		{size: 7, index: 8, wantErr: true},
		{size: 1, index: 0, want: []NodeFetch{}},
		{size: 2, index: 0, want: []NodeFetch{node(0, 1)}},              
		{size: 2, index: 1, want: []NodeFetch{node(0, 0)}},              
		{size: 3, index: 1, want: []NodeFetch{node(0, 0), node(0, 2)}},  
		{size: 7, index: 0, want: []NodeFetch{
			node(0, 1), node(1, 1), rehash(0, 6), rehash(1, 2),
		}},  
		{size: 7, index: 1, want: []NodeFetch{
			node(0, 0), node(1, 1), rehash(0, 6), rehash(1, 2),
		}},  
		{size: 7, index: 2, want: []NodeFetch{
			node(0, 3), node(1, 0), rehash(0, 6), rehash(1, 2),
		}},  
		{size: 7, index: 3, want: []NodeFetch{
			node(0, 2), node(1, 0), rehash(0, 6), rehash(1, 2),
		}},  
		{size: 7, index: 4, want: []NodeFetch{
			node(0, 5), node(0, 6), node(2, 0),
		}},  
		{size: 7, index: 5, want: []NodeFetch{
			node(0, 4), node(0, 6), node(2, 0),
		}},  
		{size: 7, index: 6, want: []NodeFetch{
			node(1, 2), node(2, 0),
		}},  
		{size: 4, index: 2, want: []NodeFetch{
			node(0, 3), node(1, 0),
		}},  
		{size: 5, index: 3, want: []NodeFetch{
			node(0, 2), node(1, 0), node(0, 4),
		}},  
		{size: 6, index: 3, want: []NodeFetch{
			node(0, 2), node(1, 0), node(1, 2),
		}},  
		{size: 6, index: 4, want: []NodeFetch{
			node(0, 5), node(2, 0),
		}},  
		{size: 7, index: 1, want: []NodeFetch{
			node(0, 0), node(1, 1), rehash(0, 6), rehash(1, 2),
		}},  
		{size: 7, index: 3, want: []NodeFetch{
			node(0, 2), node(1, 0), rehash(0, 6), rehash(1, 2),
		}},  
		{size: 15, index: 10, want: []NodeFetch{
			node(0, 11), node(1, 4), rehash(0, 14), rehash(1, 6), node(3, 0),
		}},
		{size: 31, index: 24, want: []NodeFetch{
			node(0, 25), node(1, 13),
			rehash(0, 30), rehash(1, 14),
			node(3, 2), node(4, 0),
		}},
		{size: 95, index: 81, want: []NodeFetch{
			node(0, 80), node(1, 41), node(2, 21),
			rehash(0, 94), rehash(1, 46), rehash(2, 22),
			node(4, 4), node(6, 0),
		}},
	} {
		t.Run(fmt.Sprintf("%d:%d", tc.size, tc.index), func(t *testing.T) {
			proof, err := CalcInclusionProofNodeAddresses(tc.size, tc.index)
			if tc.wantErr {
				if err == nil {
					t.Fatal("accepted bad params")
				}
				return
			} else if err != nil {
				t.Fatalf("CalcInclusionProofNodeAddresses: %v", err)
			}
			if diff := cmp.Diff(tc.want, proof); diff != "" {
				t.Errorf("paths mismatch:\n%v", diff)
			}
		})
	}
}
TestCalcInclusionProofNodeAddresses contains inclusion proof tests. For
reference, consider the following example of a tree from RFC 6962:

hash              <== Level 3
/    \
/      \
/        \
/          \
/            \
k              l        <== Level 2
/ \            / \
/   \          /   \
/     \        /     \
g       h      i      [ ]   <== Level 1
/ \     / \    / \    /
a b     c d    e f    j      <== Level 0
| |     | |    | |    |
d0 d1   d2 d3  d4 d5  d6

Our storage node layers are always populated from the bottom up, hence the
gap at level 1, index 3 in the above picture.
package merkle
import (
	"fmt"
	"testing"
	_ "github.com/golang/glog"  
	"github.com/google/go-cmp/cmp"
	"github.com/google/trillian/merkle/compact"
	"github.com/google/trillian/merkle/rfc6962"
)