path: root/trie/iterator_test.go

// Copyright 2014 The go-ethereum Authors
// This file is part of the go-ethereum library.
//
// The go-ethereum library is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// The go-ethereum library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.

package trie

import (
    "bytes"
    "fmt"
    "testing"

    "github.com/ethereum/go-ethereum/common"
    "github.com/ethereum/go-ethereum/ethdb"
)

func TestIterator(t *testing.T) {
    trie := newEmpty()
    vals := []struct{ k, v string }{
        {"do", "verb"},
        {"ether", "wookiedoo"},
        {"horse", "stallion"},
        {"shaman", "horse"},
        {"doge", "coin"},
        {"dog", "puppy"},
        {"somethingveryoddindeedthis is", "myothernodedata"},
    }
    all := make(map[string]string)
    for _, val := range vals {
        all[val.k] = val.v
        trie.Update([]byte(val.k), []byte(val.v))
    }
    trie.Commit()

    found := make(map[string]string)
    it := NewIterator(trie.NodeIterator(nil))
    for it.Next() {
        found[string(it.Key)] = string(it.Value)
    }

    for k, v := range all {
        if found[k] != v {
            t.Errorf("iterator value mismatch for %s: got %q want %q", k, found[k], v)
        }
    }
}

type kv struct {
    k, v []byte
    t    bool
}

func TestIteratorLargeData(t *testing.T) {
    trie := newEmpty()
    vals := make(map[string]*kv)

    for i := byte(0); i < 255; i++ {
        value := &kv{common.LeftPadBytes([]byte{i}, 32), []byte{i}, false}
        value2 := &kv{common.LeftPadBytes([]byte{10, i}, 32), []byte{i}, false}
        trie.Update(value.k, value.v)
        trie.Update(value2.k, value2.v)
        vals[string(value.k)] = value
        vals[string(value2.k)] = value2
    }

    it := NewIterator(trie.NodeIterator(nil))
    for it.Next() {
        vals[string(it.Key)].t = true
    }

    var untouched []*kv
    for _, value := range vals {
        if !value.t {
            untouched = append(untouched, value)
        }
    }

    if len(untouched) > 0 {
        t.Errorf("Missed %d nodes", len(untouched))
        for _, value := range untouched {
            t.Error(value)
        }
    }
}

// Tests that the node iterator indeed walks over the entire database contents.
func TestNodeIteratorCoverage(t *testing.T) {
    // Create some arbitrary test trie to iterate
    db, trie, _ := makeTestTrie()

    // Gather all the node hashes found by the iterator
    hashes := make(map[common.Hash]struct{})
    for it := trie.NodeIterator(nil); it.Next(true); {
        if it.Hash() != (common.Hash{}) {
            hashes[it.Hash()] = struct{}{}
        }
    }
    // Cross check the hashes and the database itself
    for hash := range hashes {
        if _, err := db.Get(hash.Bytes()); err != nil {
            t.Errorf("failed to retrieve reported node %x: %v", hash, err)
        }
    }
    for _, key := range db.(*ethdb.MemDatabase).Keys() {
        if _, ok := hashes[common.BytesToHash(key)]; !ok {
            t.Errorf("state entry not reported %x", key)
        }
    }
}

type kvs struct{ k, v string }

var testdata1 = []kvs{
    {"barb", "ba"},
    {"bard", "bc"},
    {"bars", "bb"},
    {"bar", "b"},
    {"fab", "z"},
    {"food", "ab"},
    {"foos", "aa"},
    {"foo", "a"},
}

var testdata2 = []kvs{
    {"aardvark", "c"},
    {"bar", "b"},
    {"barb", "bd"},
    {"bars", "be"},
    {"fab", "z"},
    {"foo", "a"},
    {"foos", "aa"},
    {"food", "ab"},
    {"jars", "d"},
}

func TestIteratorSeek(t *testing.T) {
    trie := newEmpty()
    for _, val := range testdata1 {
        trie.Update([]byte(val.k), []byte(val.v))
    }

    // Seek to the middle.
    it := NewIterator(trie.NodeIterator([]byte("fab")))
    if err := checkIteratorOrder(testdata1[4:], it); err != nil {
        t.Fatal(err)
    }

    // Seek to a non-existent key.
    it = NewIterator(trie.NodeIterator([]byte("barc")))
    if err := checkIteratorOrder(testdata1[1:], it); err != nil {
        t.Fatal(err)
    }

    // Seek beyond the end.
    it = NewIterator(trie.NodeIterator([]byte("z")))
    if err := checkIteratorOrder(nil, it); err != nil {
        t.Fatal(err)
    }
}

func checkIteratorOrder(want []kvs, it *Iterator) error {
    for it.Next() {
        if len(want) == 0 {
            return fmt.Errorf("didn't expect any more values, got key %q", it.Key)
        }
        if !bytes.Equal(it.Key, []byte(want[0].k)) {
            return fmt.Errorf("wrong key: got %q, want %q", it.Key, want[0].k)
        }
        want = want[1:]
    }
    if len(want) > 0 {
        return fmt.Errorf("iterator ended early, want key %q", want[0])
    }
    return nil
}

func TestDifferenceIterator(t *testing.T) {
    triea := newEmpty()
    for _, val := range testdata1 {
        triea.Update([]byte(val.k), []byte(val.v))
    }
    triea.Commit()

    trieb := newEmpty()
    for _, val := range testdata2 {
        trieb.Update([]byte(val.k), []byte(val.v))
    }
    trieb.Commit()

    found := make(map[string]string)
    di, _ := NewDifferenceIterator(triea.NodeIterator(nil), trieb.NodeIterator(nil))
    it := NewIterator(di)
    for it.Next() {
        found[string(it.Key)] = string(it.Value)
    }

    all := []struct{ k, v string }{
        {"aardvark", "c"},
        {"barb", "bd"},
        {"bars", "be"},
        {"jars", "d"},
    }
    for _, item := range all {
        if found[item.k] != item.v {
            t.Errorf("iterator value mismatch for %s: got %v want %v", item.k, found[item.k], item.v)
        }
    }
    if len(found) != len(all) {
        t.Errorf("iterator count mismatch: got %d values, want %d", len(found), len(all))
    }
}

func TestUnionIterator(t *testing.T) {
    triea := newEmpty()
    for _, val := range testdata1 {
        triea.Update([]byte(val.k), []byte(val.v))
    }
    triea.Commit()

    trieb := newEmpty()
    for _, val := range testdata2 {
        trieb.Update([]byte(val.k), []byte(val.v))
    }
    trieb.Commit()

    di, _ := NewUnionIterator([]NodeIterator{triea.NodeIterator(nil), trieb.NodeIterator(nil)})
    it := NewIterator(di)

    all := []struct{ k, v string }{
        {"aardvark", "c"},
        {"barb", "bd"},
        {"barb", "ba"},
        {"bard", "bc"},
        {"bars", "bb"},
        {"bars", "be"},
        {"bar", "b"},
        {"fab", "z"},
        {"food", "ab"},
        {"foos", "aa"},
        {"foo", "a"},
        {"jars", "d"},
    }

    for i, kv := range all {
        if !it.Next() {
            t.Errorf("Iterator ends prematurely at element %d", i)
        }
        if kv.k != string(it.Key) {
            t.Errorf("iterator value mismatch for element %d: got key %s want %s", i, it.Key, kv.k)
        }
        if kv.v != string(it.Value) {
            t.Errorf("iterator value mismatch for element %d: got value %s want %s", i, it.Value, kv.v)
        }
    }
    if it.Next() {
        t.Errorf("Iterator returned extra values.")
    }
}