Switched to new trie

14 files changed, 105 insertions, 73 deletions

diff --git a/cmd/ethereum/main.go b/cmd/ethereum/main.go
index 2e0a5663a..e4070aa47 100644
--- a/cmd/ethereum/main.go
+++ b/cmd/ethereum/main.go
@@ -21,6 +21,7 @@ import (
 	"fmt"
 	"os"
 	"runtime"
+	"time"
 
 	"github.com/ethereum/go-ethereum/cmd/utils"
 	"github.com/ethereum/go-ethereum/core/types"
@@ -97,9 +98,6 @@ func main() {
 			os.Exit(1)
 		}
 
-		// block.GetRoot() does not exist
-		//fmt.Printf("RLP: %x\nstate: %x\nhash: %x\n", ethutil.Rlp(block), block.GetRoot(), block.Hash())
-
 		// Leave the Println. This needs clean output for piping
 		fmt.Printf("%s\n", block.State().Dump())
 
@@ -117,10 +115,12 @@ func main() {
 	}
 
 	if len(ImportChain) > 0 {
+		start := time.Now()
 		err := utils.ImportChain(ethereum, ImportChain)
 		if err != nil {
 			clilogger.Infoln(err)
 		}
+		clilogger.Infoln("export done in", time.Since(start))
 		return
 	}
 
diff --git a/cmd/utils/cmd.go b/cmd/utils/cmd.go
index c0a5d1c97..466c51383 100644
--- a/cmd/utils/cmd.go
+++ b/cmd/utils/cmd.go
@@ -339,7 +339,7 @@ func BlockDo(ethereum *eth.Ethereum, hash []byte) error {
 }
 
 func ImportChain(ethereum *eth.Ethereum, fn string) error {
-	clilogger.Infof("importing chain '%s'\n", ImportChain)
+	clilogger.Infof("importing chain '%s'\n", fn)
 	fh, err := os.OpenFile(fn, os.O_RDONLY, os.ModePerm)
 	if err != nil {
 		return err
diff --git a/core/block_manager.go b/core/block_manager.go
index ef2113bfb..1b9da1269 100644
--- a/core/block_manager.go
+++ b/core/block_manager.go
@@ -217,6 +217,7 @@ func (sm *BlockManager) ProcessWithParent(block, parent *types.Block) (td *big.I
 
 	receiptSha := types.DeriveSha(receipts)
 	if bytes.Compare(receiptSha, header.ReceiptHash) != 0 {
+		fmt.Println("receipts", receipts)
 		err = fmt.Errorf("validating receipt root. received=%x got=%x", header.ReceiptHash, receiptSha)
 		return
 	}
diff --git a/core/genesis.go b/core/genesis.go
index 51afa314e..10b40516f 100644
--- a/core/genesis.go
+++ b/core/genesis.go
@@ -20,7 +20,7 @@ var EmptyShaList = crypto.Sha3(ethutil.Encode([]interface{}{}))
 var EmptyListRoot = crypto.Sha3(ethutil.Encode(""))
 
 func GenesisBlock() *types.Block {
-	genesis := types.NewBlock(ZeroHash256, ZeroHash160, EmptyListRoot, big.NewInt(131072), crypto.Sha3(big.NewInt(42).Bytes()), "")
+	genesis := types.NewBlock(ZeroHash256, ZeroHash160, nil, big.NewInt(131072), crypto.Sha3(big.NewInt(42).Bytes()), "")
 	genesis.Header().Number = ethutil.Big0
 	genesis.Header().GasLimit = big.NewInt(1000000)
 	genesis.Header().GasUsed = ethutil.Big0
diff --git a/core/types/block.go b/core/types/block.go
index 940f2402e..054767d67 100644
--- a/core/types/block.go
+++ b/core/types/block.go
@@ -9,9 +9,9 @@ import (
 
 	"github.com/ethereum/go-ethereum/crypto"
 	"github.com/ethereum/go-ethereum/ethutil"
+	"github.com/ethereum/go-ethereum/ptrie"
 	"github.com/ethereum/go-ethereum/rlp"
 	"github.com/ethereum/go-ethereum/state"
-	"github.com/ethereum/go-ethereum/trie"
 )
 
 type Header struct {
@@ -196,7 +196,7 @@ func (self *Block) Time() int64               { return int64(self.header.Time) }
 func (self *Block) GasLimit() *big.Int        { return self.header.GasLimit }
 func (self *Block) GasUsed() *big.Int         { return self.header.GasUsed }
 func (self *Block) Hash() []byte              { return self.header.Hash() }
-func (self *Block) Trie() *trie.Trie          { return trie.New(ethutil.Config.Db, self.header.Root) }
+func (self *Block) Trie() *ptrie.Trie         { return ptrie.New(self.header.Root, ethutil.Config.Db) }
 func (self *Block) State() *state.StateDB     { return state.New(self.Trie()) }
 func (self *Block) Size() ethutil.StorageSize { return ethutil.StorageSize(len(ethutil.Encode(self))) }
 
diff --git a/core/types/derive_sha.go b/core/types/derive_sha.go
index 1897ff198..0beb19670 100644
--- a/core/types/derive_sha.go
+++ b/core/types/derive_sha.go
@@ -2,7 +2,7 @@ package types
 
 import (
 	"github.com/ethereum/go-ethereum/ethutil"
-	"github.com/ethereum/go-ethereum/trie"
+	"github.com/ethereum/go-ethereum/ptrie"
 )
 
 type DerivableList interface {
@@ -11,10 +11,10 @@ type DerivableList interface {
 }
 
 func DeriveSha(list DerivableList) []byte {
-	trie := trie.New(ethutil.Config.Db, "")
+	trie := ptrie.New(nil, ethutil.Config.Db)
 	for i := 0; i < list.Len(); i++ {
-		trie.Update(string(ethutil.NewValue(i).Encode()), string(list.GetRlp(i)))
+		trie.Update(ethutil.Encode(i), list.GetRlp(i))
 	}
 
-	return trie.GetRoot()
+	return trie.Root()
 }
diff --git a/javascript/types.go b/javascript/types.go
index cf5a6677b..ce1d9995a 100644
--- a/javascript/types.go
+++ b/javascript/types.go
@@ -18,11 +18,11 @@ type JSStateObject struct {
 
 func (self *JSStateObject) EachStorage(call otto.FunctionCall) otto.Value {
 	cb := call.Argument(0)
-	self.JSObject.EachStorage(func(key string, value *ethutil.Value) {
-		value.Decode()
 
-		cb.Call(self.eth.toVal(self), self.eth.toVal(key), self.eth.toVal(ethutil.Bytes2Hex(value.Bytes())))
-	})
+	it := self.JSObject.Trie().Iterator()
+	for it.Next() {
+		cb.Call(self.eth.toVal(self), self.eth.toVal(ethutil.Bytes2Hex(it.Key)), self.eth.toVal(ethutil.Bytes2Hex(it.Value)))
+	}
 
 	return otto.UndefinedValue()
 }
diff --git a/ptrie/fullnode.go b/ptrie/fullnode.go
index 7a7f7d22d..d6b0745ec 100644
--- a/ptrie/fullnode.go
+++ b/ptrie/fullnode.go
@@ -1,5 +1,7 @@
 package ptrie
 
+import "fmt"
+
 type FullNode struct {
 	trie  *Trie
 	nodes [17]Node
@@ -56,6 +58,11 @@ func (self *FullNode) RlpData() interface{} {
 }
 
 func (self *FullNode) set(k byte, value Node) {
+	if _, ok := value.(*ValueNode); ok && k != 16 {
+		fmt.Println(value, k)
+		panic(":(")
+	}
+
 	self.nodes[int(k)] = value
 }
 
diff --git a/ptrie/trie.go b/ptrie/trie.go
index 9fe9ea52a..d8135f36c 100644
--- a/ptrie/trie.go
+++ b/ptrie/trie.go
@@ -19,7 +19,7 @@ func ParanoiaCheck(t1 *Trie, backend Backend) (bool, *Trie) {
 		t2.Update(it.Key, it.Value)
 	}
 
-	return bytes.Compare(t2.Hash(), t1.Hash()) == 0, t2
+	return bytes.Equal(t2.Hash(), t1.Hash()), t2
 }
 
 type Trie struct {
@@ -49,14 +49,17 @@ func (self *Trie) Iterator() *Iterator {
 	return NewIterator(self)
 }
 
+func (self *Trie) Copy() *Trie {
+	return New(self.roothash, self.cache.backend)
+}
+
 // Legacy support
 func (self *Trie) Root() []byte { return self.Hash() }
 func (self *Trie) Hash() []byte {
 	var hash []byte
 	if self.root != nil {
-		//hash = self.root.Hash().([]byte)
 		t := self.root.Hash()
-		if byts, ok := t.([]byte); ok {
+		if byts, ok := t.([]byte); ok && len(byts) > 0 {
 			hash = byts
 		} else {
 			hash = crypto.Sha3(ethutil.Encode(self.root.RlpData()))
@@ -73,6 +76,9 @@ func (self *Trie) Hash() []byte {
 	return hash
 }
 func (self *Trie) Commit() {
+	self.mu.Lock()
+	defer self.mu.Unlock()
+
 	// Hash first
 	self.Hash()
 
@@ -81,10 +87,15 @@ func (self *Trie) Commit() {
 
 // Reset should only be called if the trie has been hashed
 func (self *Trie) Reset() {
+	self.mu.Lock()
+	defer self.mu.Unlock()
+
 	self.cache.Reset()
 
-	revision := self.revisions.Remove(self.revisions.Back()).([]byte)
-	self.roothash = revision
+	if self.revisions.Len() > 0 {
+		revision := self.revisions.Remove(self.revisions.Back()).([]byte)
+		self.roothash = revision
+	}
 	value := ethutil.NewValueFromBytes(self.cache.Get(self.roothash))
 	self.root = self.mknode(value)
 }
@@ -173,7 +184,7 @@ func (self *Trie) insert(node Node, key []byte, value Node) Node {
 		return cpy
 
 	default:
-		panic("Invalid node")
+		panic(fmt.Sprintf("%T: invalid node: %v", node, node))
 	}
 }
 
@@ -274,6 +285,8 @@ func (self *Trie) delete(node Node, key []byte) Node {
 func (self *Trie) mknode(value *ethutil.Value) Node {
 	l := value.Len()
 	switch l {
+	case 0:
+		return nil
 	case 2:
 		return NewShortNode(self, trie.CompactDecode(string(value.Get(0).Bytes())), self.mknode(value.Get(1)))
 	case 17:
diff --git a/ptrie/trie_test.go b/ptrie/trie_test.go
index 5b1c64140..63a8ed36e 100644
--- a/ptrie/trie_test.go
+++ b/ptrie/trie_test.go
@@ -141,7 +141,7 @@ func TestReplication(t *testing.T) {
 
 	trie2 := New(trie.roothash, trie.cache.backend)
 	if string(trie2.GetString("horse")) != "stallion" {
-		t.Error("expected to have harse => stallion")
+		t.Error("expected to have horse => stallion")
 	}
 
 	hash := trie2.Hash()
diff --git a/state/dump.go b/state/dump.go
index c1f5ecf3a..40ecff50c 100644
--- a/state/dump.go
+++ b/state/dump.go
@@ -22,22 +22,23 @@ type World struct {
 
 func (self *StateDB) Dump() []byte {
 	world := World{
-		Root:     ethutil.Bytes2Hex(self.Trie.GetRoot()),
+		Root:     ethutil.Bytes2Hex(self.trie.Root()),
 		Accounts: make(map[string]Account),
 	}
 
-	self.Trie.NewIterator().Each(func(key string, value *ethutil.Value) {
-		stateObject := NewStateObjectFromBytes([]byte(key), value.Bytes())
+	it := self.trie.Iterator()
+	for it.Next() {
+		stateObject := NewStateObjectFromBytes(it.Key, it.Value)
 
 		account := Account{Balance: stateObject.balance.String(), Nonce: stateObject.Nonce, Root: ethutil.Bytes2Hex(stateObject.Root()), CodeHash: ethutil.Bytes2Hex(stateObject.codeHash)}
 		account.Storage = make(map[string]string)
 
-		stateObject.EachStorage(func(key string, value *ethutil.Value) {
-			value.Decode()
-			account.Storage[ethutil.Bytes2Hex([]byte(key))] = ethutil.Bytes2Hex(value.Bytes())
-		})
-		world.Accounts[ethutil.Bytes2Hex([]byte(key))] = account
-	})
+		storageIt := stateObject.State.trie.Iterator()
+		for storageIt.Next() {
+			account.Storage[ethutil.Bytes2Hex(it.Key)] = ethutil.Bytes2Hex(it.Value)
+		}
+		world.Accounts[ethutil.Bytes2Hex(it.Key)] = account
+	}
 
 	json, err := json.MarshalIndent(world, "", "    ")
 	if err != nil {
@@ -50,7 +51,8 @@ func (self *StateDB) Dump() []byte {
 // Debug stuff
 func (self *StateObject) CreateOutputForDiff() {
 	fmt.Printf("%x %x %x %x\n", self.Address(), self.State.Root(), self.balance.Bytes(), self.Nonce)
-	self.EachStorage(func(addr string, value *ethutil.Value) {
-		fmt.Printf("%x %x\n", addr, value.Bytes())
-	})
+	it := self.State.trie.Iterator()
+	for it.Next() {
+		fmt.Printf("%x %x\n", it.Key, it.Value)
+	}
 }
diff --git a/state/state_object.go b/state/state_object.go
index b8af4e702..420ad9757 100644
--- a/state/state_object.go
+++ b/state/state_object.go
@@ -6,7 +6,7 @@ import (
 
 	"github.com/ethereum/go-ethereum/crypto"
 	"github.com/ethereum/go-ethereum/ethutil"
-	"github.com/ethereum/go-ethereum/trie"
+	"github.com/ethereum/go-ethereum/ptrie"
 )
 
 type Code []byte
@@ -62,7 +62,7 @@ func NewStateObject(addr []byte) *StateObject {
 	address := ethutil.Address(addr)
 
 	object := &StateObject{address: address, balance: new(big.Int), gasPool: new(big.Int)}
-	object.State = New(trie.New(ethutil.Config.Db, ""))
+	object.State = New(ptrie.New(nil, ethutil.Config.Db)) //New(trie.New(ethutil.Config.Db, ""))
 	object.storage = make(Storage)
 	object.gasPool = new(big.Int)
 
@@ -72,7 +72,7 @@ func NewStateObject(addr []byte) *StateObject {
 func NewContract(address []byte, balance *big.Int, root []byte) *StateObject {
 	contract := NewStateObject(address)
 	contract.balance = balance
-	contract.State = New(trie.New(ethutil.Config.Db, string(root)))
+	contract.State = New(ptrie.New(nil, ethutil.Config.Db)) //New(trie.New(ethutil.Config.Db, string(root)))
 
 	return contract
 }
@@ -89,12 +89,12 @@ func (self *StateObject) MarkForDeletion() {
 	statelogger.DebugDetailf("%x: #%d %v (deletion)\n", self.Address(), self.Nonce, self.balance)
 }
 
-func (c *StateObject) GetAddr(addr []byte) *ethutil.Value {
-	return ethutil.NewValueFromBytes([]byte(c.State.Trie.Get(string(addr))))
+func (c *StateObject) getAddr(addr []byte) *ethutil.Value {
+	return ethutil.NewValueFromBytes([]byte(c.State.trie.Get(addr)))
 }
 
-func (c *StateObject) SetAddr(addr []byte, value interface{}) {
-	c.State.Trie.Update(string(addr), string(ethutil.NewValue(value).Encode()))
+func (c *StateObject) setAddr(addr []byte, value interface{}) {
+	c.State.trie.Update(addr, ethutil.Encode(value))
 }
 
 func (self *StateObject) GetStorage(key *big.Int) *ethutil.Value {
@@ -113,7 +113,7 @@ func (self *StateObject) GetState(k []byte) *ethutil.Value {
 
 	value := self.storage[string(key)]
 	if value == nil {
-		value = self.GetAddr(key)
+		value = self.getAddr(key)
 
 		if !value.IsNil() {
 			self.storage[string(key)] = value
@@ -128,6 +128,7 @@ func (self *StateObject) SetState(k []byte, value *ethutil.Value) {
 	self.storage[string(key)] = value.Copy()
 }
 
+/*
 // Iterate over each storage address and yield callback
 func (self *StateObject) EachStorage(cb trie.EachCallback) {
 	// First loop over the uncommit/cached values in storage
@@ -145,23 +146,26 @@ func (self *StateObject) EachStorage(cb trie.EachCallback) {
 		}
 	})
 }
+*/
 
 func (self *StateObject) Sync() {
 	for key, value := range self.storage {
 		if value.Len() == 0 {
-			self.State.Trie.Delete(string(key))
+			self.State.trie.Delete([]byte(key))
 			continue
 		}
 
-		self.SetAddr([]byte(key), value)
+		self.setAddr([]byte(key), value)
 	}
 
-	valid, t2 := trie.ParanoiaCheck(self.State.Trie)
-	if !valid {
-		statelogger.Infof("Warn: PARANOIA: Different state storage root during copy %x vs %x\n", self.State.Root(), t2.GetRoot())
+	/*
+		valid, t2 := ptrie.ParanoiaCheck(self.State.trie, ethutil.Config.Db)
+		if !valid {
+			statelogger.Infof("Warn: PARANOIA: Different state storage root during copy %x vs %x\n", self.State.Root(), t2.Root())
 
-		self.State.Trie = t2
-	}
+			self.State.trie = t2
+		}
+	*/
 }
 
 func (c *StateObject) GetInstr(pc *big.Int) *ethutil.Value {
@@ -276,8 +280,12 @@ func (c *StateObject) Init() Code {
 	return c.InitCode
 }
 
+func (self *StateObject) Trie() *ptrie.Trie {
+	return self.State.trie
+}
+
 func (self *StateObject) Root() []byte {
-	return self.State.Trie.GetRoot()
+	return self.Trie().Root()
 }
 
 func (self *StateObject) SetCode(code []byte) {
@@ -302,7 +310,7 @@ func (c *StateObject) RlpDecode(data []byte) {
 
 	c.Nonce = decoder.Get(0).Uint()
 	c.balance = decoder.Get(1).BigInt()
-	c.State = New(trie.New(ethutil.Config.Db, decoder.Get(2).Interface()))
+	c.State = New(ptrie.New(decoder.Get(2).Bytes(), ethutil.Config.Db)) //New(trie.New(ethutil.Config.Db, decoder.Get(2).Interface()))
 	c.storage = make(map[string]*ethutil.Value)
 	c.gasPool = new(big.Int)
 
diff --git a/state/state.go b/state/statedb.go
index f77da72f0..6a11fc328 100644
--- a/state/state.go
+++ b/state/statedb.go
@@ -1,11 +1,12 @@
 package state
 
 import (
+	"bytes"
 	"math/big"
 
 	"github.com/ethereum/go-ethereum/ethutil"
 	"github.com/ethereum/go-ethereum/logger"
-	"github.com/ethereum/go-ethereum/trie"
+	"github.com/ethereum/go-ethereum/ptrie"
 )
 
 var statelogger = logger.NewLogger("STATE")
@@ -16,8 +17,8 @@ var statelogger = logger.NewLogger("STATE")
 // * Contracts
 // * Accounts
 type StateDB struct {
-	// The trie for this structure
-	Trie *trie.Trie
+	//Trie *trie.Trie
+	trie *ptrie.Trie
 
 	stateObjects map[string]*StateObject
 
@@ -29,8 +30,8 @@ type StateDB struct {
 }
 
 // Create a new state from a given trie
-func New(trie *trie.Trie) *StateDB {
-	return &StateDB{Trie: trie, stateObjects: make(map[string]*StateObject), manifest: NewManifest(), refund: make(map[string]*big.Int)}
+func New(trie *ptrie.Trie) *StateDB {
+	return &StateDB{trie: trie, stateObjects: make(map[string]*StateObject), manifest: NewManifest(), refund: make(map[string]*big.Int)}
 }
 
 func (self *StateDB) EmptyLogs() {
@@ -140,12 +141,12 @@ func (self *StateDB) UpdateStateObject(stateObject *StateObject) {
 		ethutil.Config.Db.Put(stateObject.CodeHash(), stateObject.Code)
 	}
 
-	self.Trie.Update(string(addr), string(stateObject.RlpEncode()))
+	self.trie.Update(addr, stateObject.RlpEncode())
 }
 
 // Delete the given state object and delete it from the state trie
 func (self *StateDB) DeleteStateObject(stateObject *StateObject) {
-	self.Trie.Delete(string(stateObject.Address()))
+	self.trie.Delete(stateObject.Address())
 
 	delete(self.stateObjects, string(stateObject.Address()))
 }
@@ -159,7 +160,7 @@ func (self *StateDB) GetStateObject(addr []byte) *StateObject {
 		return stateObject
 	}
 
-	data := self.Trie.Get(string(addr))
+	data := self.trie.Get(addr)
 	if len(data) == 0 {
 		return nil
 	}
@@ -206,12 +207,12 @@ func (self *StateDB) GetAccount(addr []byte) *StateObject {
 //
 
 func (s *StateDB) Cmp(other *StateDB) bool {
-	return s.Trie.Cmp(other.Trie)
+	return bytes.Equal(s.trie.Root(), other.trie.Root())
 }
 
 func (self *StateDB) Copy() *StateDB {
-	if self.Trie != nil {
-		state := New(self.Trie.Copy())
+	if self.trie != nil {
+		state := New(self.trie.Copy())
 		for k, stateObject := range self.stateObjects {
 			state.stateObjects[k] = stateObject.Copy()
 		}
@@ -235,19 +236,19 @@ func (self *StateDB) Set(state *StateDB) {
 		panic("Tried setting 'state' to nil through 'Set'")
 	}
 
-	self.Trie = state.Trie
+	self.trie = state.trie
 	self.stateObjects = state.stateObjects
 	self.refund = state.refund
 	self.logs = state.logs
 }
 
 func (s *StateDB) Root() []byte {
-	return s.Trie.GetRoot()
+	return s.trie.Root()
 }
 
 // Resets the trie and all siblings
 func (s *StateDB) Reset() {
-	s.Trie.Undo()
+	s.trie.Reset()
 
 	// Reset all nested states
 	for _, stateObject := range s.stateObjects {
@@ -272,7 +273,7 @@ func (s *StateDB) Sync() {
 		stateObject.State.Sync()
 	}
 
-	s.Trie.Sync()
+	s.trie.Commit()
 
 	s.Empty()
 }
@@ -304,11 +305,11 @@ func (self *StateDB) Update(gasUsed *big.Int) {
 
 	// FIXME trie delete is broken
 	if deleted {
-		valid, t2 := trie.ParanoiaCheck(self.Trie)
+		valid, t2 := ptrie.ParanoiaCheck(self.trie, ethutil.Config.Db)
 		if !valid {
-			statelogger.Infof("Warn: PARANOIA: Different state root during copy %x vs %x\n", self.Trie.GetRoot(), t2.GetRoot())
+			statelogger.Infof("Warn: PARANOIA: Different state root during copy %x vs %x\n", self.trie.Root(), t2.Root())
 
-			self.Trie = t2
+			self.trie = t2
 		}
 	}
 }
diff --git a/xeth/hexface.go b/xeth/hexface.go
index 6c084f947..c3d8cef86 100644
--- a/xeth/hexface.go
+++ b/xeth/hexface.go
@@ -138,10 +138,10 @@ type KeyVal struct {
 func (self *JSXEth) EachStorage(addr string) string {
 	var values []KeyVal
 	object := self.World().SafeGet(ethutil.Hex2Bytes(addr))
-	object.EachStorage(func(name string, value *ethutil.Value) {
-		value.Decode()
-		values = append(values, KeyVal{ethutil.Bytes2Hex([]byte(name)), ethutil.Bytes2Hex(value.Bytes())})
-	})
+	it := object.Trie().Iterator()
+	for it.Next() {
+		values = append(values, KeyVal{ethutil.Bytes2Hex(it.Key), ethutil.Bytes2Hex(it.Value)})
+	}
 
 	valuesJson, err := json.Marshal(values)
 	if err != nil {