<commit_before>// Copyright 2016 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Package compact provides compact Merkle tree data structures.
package compact

import (
	"bytes"
	"encoding/base64"
	"encoding/hex"
	"fmt"
	"math/bits"

	log "github.com/golang/glog"
	"github.com/google/trillian/merkle/hashers"
)

// RootHashMismatchError indicates an unexpected root hash value.
type RootHashMismatchError struct {
	ExpectedHash []byte
	ActualHash   []byte
}

// Error formats the error into a string.
func (r RootHashMismatchError) Error() string {
	return fmt.Sprintf("root hash mismatch: got %v, expected %v", r.ActualHash, r.ExpectedHash)
}

// Tree is a compact Merkle tree representation. It uses O(log(N)) nodes to
// represent the current on-disk tree.
//
// TODO(pavelkalinnikov): Remove it, use compact.Range instead.
type Tree struct {
	hasher hashers.LogHasher
	root   []byte
	// the list of "dangling" left-hand nodes, NOTE: index 0 is the leaf, not the root.
	nodes [][]byte
	size  int64
}

func isPerfectTree(x int64) bool {
	return x != 0 && (x&(x-1) == 0)
}

// GetNodeFunc is a function prototype which can look up particular nodes
// within a non-compact Merkle tree. Used by the compact Tree to populate
// itself with correct state when starting up with a non-empty tree.
type GetNodeFunc func(depth int, index int64) ([]byte, error)

// NewTreeWithState creates a new compact Tree for the passed in |size|.
//
// This can fail if the nodes required to recreate the tree state cannot be
// fetched or the calculated root hash after population does not match the
// value we expect.
//
// |f| will be called a number of times with the coordinates of internal Merkle
// tree nodes whose hash values are required to initialize the internal state
// of the compact Tree. |expectedRoot| is the known-good tree root of the tree
// at |size|, and is used to verify the initial state of the compact Tree.
//
// TODO(pavelkalinnikov): Make GetNodeFunc get all nodes at once.
func NewTreeWithState(hasher hashers.LogHasher, size int64, f GetNodeFunc, expectedRoot []byte) (*Tree, error) {
	sizeBits := bits.Len64(uint64(size))

	r := Tree{
		hasher: hasher,
		nodes:  make([][]byte, sizeBits),
		root:   hasher.EmptyRoot(),
		size:   size,
	}

	if isPerfectTree(size) {
		log.V(1).Info("Is perfect tree.")
		r.root = append(make([]byte, 0, len(expectedRoot)), expectedRoot...)
		r.nodes[sizeBits-1] = r.root
	} else {
		// Pull in the nodes we need to repopulate our compact tree and verify the root
		for depth := 0; depth < sizeBits; depth++ {
			if size&1 == 1 {
				index := size - 1
				log.V(1).Infof("fetching d: %d i: %d, leaving size %d", depth, index, size)
				h, err := f(depth, index)
				if err != nil {
					log.Warningf("Failed to fetch node depth %d index %d: %s", depth, index, err)
					return nil, err
				}
				r.nodes[depth] = h
			}
			size >>= 1
		}
		r.recalculateRoot(func(depth int, index int64, hash []byte) error {
			return nil
		})
	}
	if !bytes.Equal(r.root, expectedRoot) {
		log.Warningf("Corrupt state, expected root %s, got %s", hex.EncodeToString(expectedRoot[:]), hex.EncodeToString(r.root[:]))
		return nil, RootHashMismatchError{ActualHash: r.root, ExpectedHash: expectedRoot}
	}
	log.V(1).Infof("Resuming at size %d, with root: %s", r.size, base64.StdEncoding.EncodeToString(r.root[:]))
	return &r, nil
}

// NewTree creates a new compact Tree with size zero. This always succeeds.
func NewTree(hasher hashers.LogHasher) *Tree {
	r := Tree{
		hasher: hasher,
		root:   hasher.EmptyRoot(),
		nodes:  make([][]byte, 0),
		size:   0,
	}
	return &r<commit_msg>Use glog package name verbatim (#1519)<commit_after>// Copyright 2016 Google Inc. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Package compact provides compact Merkle tree data structures.
package compact

import (
	"bytes"
	"encoding/base64"
	"encoding/hex"
	"fmt"
	"math/bits"

	"github.com/golang/glog"
	"github.com/google/trillian/merkle/hashers"
)

// RootHashMismatchError indicates an unexpected root hash value.
type RootHashMismatchError struct {
	ExpectedHash []byte
	ActualHash   []byte
}

// Error formats the error into a string.
func (r RootHashMismatchError) Error() string {
	return fmt.Sprintf("root hash mismatch: got %v, expected %v", r.ActualHash, r.ExpectedHash)
}

// Tree is a compact Merkle tree representation. It uses O(log(N)) nodes to
// represent the current on-disk tree.
//
// TODO(pavelkalinnikov): Remove it, use compact.Range instead.
type Tree struct {
	hasher hashers.LogHasher
	root   []byte
	// the list of "dangling" left-hand nodes, NOTE: index 0 is the leaf, not the root.
	nodes [][]byte
	size  int64
}

func isPerfectTree(x int64) bool {
	return x != 0 && (x&(x-1) == 0)
}

// GetNodeFunc is a function prototype which can look up particular nodes
// within a non-compact Merkle tree. Used by the compact Tree to populate
// itself with correct state when starting up with a non-empty tree.
type GetNodeFunc func(depth int, index int64) ([]byte, error)

// NewTreeWithState creates a new compact Tree for the passed in |size|.
//
// This can fail if the nodes required to recreate the tree state cannot be
// fetched or the calculated root hash after population does not match the
// value we expect.
//
// |f| will be called a number of times with the coordinates of internal Merkle
// tree nodes whose hash values are required to initialize the internal state
// of the compact Tree. |expectedRoot| is the known-good tree root of the tree
// at |size|, and is used to verify the initial state of the compact Tree.
//
// TODO(pavelkalinnikov): Make GetNodeFunc get all nodes at once.
func NewTreeWithState(hasher hashers.LogHasher, size int64, f GetNodeFunc, expectedRoot []byte) (*Tree, error) {
	sizeBits := bits.Len64(uint64(size))

	r := Tree{
		hasher: hasher,
		nodes:  make([][]byte, sizeBits),
		root:   hasher.EmptyRoot(),
		size:   size,
	}

	if isPerfectTree(size) {
		glog.V(1).Info("Is perfect tree.")
		r.root = append(make([]byte, 0, len(expectedRoot)), expectedRoot...)
		r.nodes[sizeBits-1] = r.root
	} else {
		// Pull in the nodes we need to repopulate our compact tree and verify the root
		for depth := 0; depth < sizeBits; depth++ {
			if size&1 == 1 {
				index := size - 1
				glog.V(1).Infof("fetching d: %d i: %d, leaving size %d", depth, index, size)
				h, err := f(depth, index)
				if err != nil {
					glog.Warningf("Failed to fetch node depth %d index %d: %s", depth, index, err)
					return nil, err
				}
				r.nodes[depth] = h
			}
			size >>= 1
		}
		r.recalculateRoot(func(depth int, index int64, hash []byte) error {
			return nil
		})
	}
	if !bytes.Equal(r.root, expectedRoot) {
		glog.Warningf("Corrupt state, expected root %s, got %s", hex.EncodeToString(expectedRoot[:]), hex.EncodeToString(r.root[:]))
		return nil, RootHashMismatchError{ActualHash: r.root, ExpectedHash: expectedRoot}
	}
	glog.V(1).Infof("Resuming at size %d, with root: %s", r.size, base64.StdEncoding.EncodeToString(r.root[:]))
	return &r, nil
}

// NewTree creates a new compact Tree with size zero. This always succeeds.
func NewTree(hasher hashers.LogHasher) *Tree {
	r := Tree{
		hasher: hasher,
		root:   hasher.EmptyRoot(),
		nodes:  make([][]byte, 0),
		size:   0,
	}
	return &r
{'fraction_non_alphanumeric': 0.11651067914566834, 'fraction_numerical': 0.010559155267578594, 'mean_word_length': 3.633129516397999, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3911983', 'n_tokens_mistral': 2785, 'n_tokens_neox': 2607, 'n_words': 1027}