1/**
  2 *  @file
  3 *  @copyright defined in aergo/LICENSE.txt
  4 */
  5
  6package trie
  7
  8import (
  9	"bytes"
 10	"fmt"
 11)
 12
 13// Revert rewinds the state tree to a previous version
 14// All the nodes (subtree roots and values) reverted are deleted from the database.
 15func (s *Trie) Revert(toOldRoot []byte) error {
 16	s.lock.RLock()
 17	defer s.lock.RUnlock()
 18
 19	// safety precaution if reverting to a shortcut batch that might have been deleted
 20	s.atomicUpdate = false // so loadChildren doesnt return a copy
 21	batch, _, _, _, isShortcut, err := s.loadChildren(toOldRoot, s.TrieHeight, 0, nil)
 22	if err != nil {
 23		return err
 24	}
 25
 26	//check if toOldRoot is in s.pastTries
 27	canRevert := false
 28	toIndex := 0
 29	for i, r := range s.pastTries {
 30		if bytes.Equal(r, toOldRoot) {
 31			canRevert = true
 32			toIndex = i
 33			break
 34		}
 35	}
 36	if !canRevert || bytes.Equal(s.Root, toOldRoot) {
 37		return fmt.Errorf("The root cannot be reverted, because already latest of not in pastTries : current : %x, target : %x", s.Root, toOldRoot)
 38	}
 39
 40	// For every node of toOldRoot, compare it to the equivalent node in other pasttries between toOldRoot and current s.Root. If a node is different, delete the one from pasttries
 41	s.db.nodesToRevert = make([][]byte, 0)
 42	for i := toIndex + 1; i < len(s.pastTries); i++ {
 43		ch := make(chan error, 1)
 44		s.maybeDeleteSubTree(toOldRoot, s.pastTries[i], s.TrieHeight, 0, nil, nil, ch)
 45		err := <-ch
 46		if err != nil {
 47			return err
 48		}
 49	}
 50	// NOTE The tx interface doesnt handle ErrTxnTooBig
 51	txn := s.db.Store.NewTx()
 52	for _, key := range s.db.nodesToRevert {
 53		txn.Delete(key[:HashLength])
 54	}
 55	txn.Commit()
 56
 57	s.pastTries = s.pastTries[:toIndex+1]
 58	s.Root = toOldRoot
 59	s.db.liveCache = make(map[Hash][][]byte)
 60	s.db.updatedNodes = make(map[Hash][][]byte)
 61	if isShortcut {
 62		// If toOldRoot is a shortcut batch, it is possible that
 63		// revert has deleted it if the key was ever stored at height0
 64		// because in leafHash byte(0) = byte(256)
 65		s.db.Store.Set(toOldRoot, s.db.serializeBatch(batch))
 66	}
 67	return nil
 68}
 69
 70// maybeDeleteSubTree compares the subtree nodes of 2 tries and keeps only the older one
 71func (s *Trie) maybeDeleteSubTree(original, maybeDelete []byte, height, iBatch int, batch, batch2 [][]byte, ch chan<- (error)) {
 72	if height == 0 {
 73		if !bytes.Equal(original, maybeDelete) && len(maybeDelete) != 0 {
 74			s.maybeDeleteRevertedNode(maybeDelete, 0)
 75		}
 76		ch <- nil
 77		return
 78	}
 79	if bytes.Equal(original, maybeDelete) || len(maybeDelete) == 0 {
 80		ch <- nil
 81		return
 82	}
 83	// if this point os reached, then the root of the batch is same
 84	// so the batch is also same.
 85	batch, iBatch, lnode, rnode, isShortcut, lerr := s.loadChildren(original, height, iBatch, batch)
 86	if lerr != nil {
 87		ch <- lerr
 88		return
 89	}
 90	batch2, _, lnode2, rnode2, isShortcut2, rerr := s.loadChildren(maybeDelete, height, iBatch, batch2)
 91	if rerr != nil {
 92		ch <- rerr
 93		return
 94	}
 95
 96	if isShortcut != isShortcut2 {
 97		if isShortcut {
 98			ch1 := make(chan error, 1)
 99			s.deleteSubTree(maybeDelete, height, iBatch, batch2, ch1)
100			err := <-ch1
101			if err != nil {
102				ch <- err
103				return
104			}
105		} else {
106			s.maybeDeleteRevertedNode(maybeDelete, iBatch)
107		}
108	} else {
109		if isShortcut {
110			// Delete shortcut if not equal
111			if !bytes.Equal(lnode, lnode2) || !bytes.Equal(rnode, rnode2) {
112				s.maybeDeleteRevertedNode(maybeDelete, iBatch)
113			}
114		} else {
115			// Delete subtree if not equal
116			s.maybeDeleteRevertedNode(maybeDelete, iBatch)
117			ch1 := make(chan error, 1)
118			ch2 := make(chan error, 1)
119			go s.maybeDeleteSubTree(lnode, lnode2, height-1, 2*iBatch+1, batch, batch2, ch1)
120			go s.maybeDeleteSubTree(rnode, rnode2, height-1, 2*iBatch+2, batch, batch2, ch2)
121			err1, err2 := <-ch1, <-ch2
122			if err1 != nil {
123				ch <- err1
124				return
125			}
126			if err2 != nil {
127				ch <- err2
128				return
129			}
130		}
131	}
132	ch <- nil
133}
134
135// deleteSubTree deletes all the nodes contained in a tree
136func (s *Trie) deleteSubTree(root []byte, height, iBatch int, batch [][]byte, ch chan<- (error)) {
137	if len(root) == 0 || height == 0 {
138		if height == 0 {
139			s.maybeDeleteRevertedNode(root, 0)
140		}
141		ch <- nil
142		return
143	}
144	batch, iBatch, lnode, rnode, isShortcut, err := s.loadChildren(root, height, iBatch, batch)
145	if err != nil {
146		ch <- err
147		return
148	}
149	if !isShortcut {
150		ch1 := make(chan error, 1)
151		ch2 := make(chan error, 1)
152		go s.deleteSubTree(lnode, height-1, 2*iBatch+1, batch, ch1)
153		go s.deleteSubTree(rnode, height-1, 2*iBatch+2, batch, ch2)
154		lerr := <-ch1
155		rerr := <-ch2
156
157		if lerr != nil {
158			ch <- lerr
159			return
160		}
161		if rerr != nil {
162			ch <- rerr
163			return
164		}
165	}
166	s.maybeDeleteRevertedNode(root, iBatch)
167	ch <- nil
168}
169
170// maybeDeleteRevertedNode adds the node to updatedNodes to be reverted
171// if it is a batch node at height%4 == 0
172func (s *Trie) maybeDeleteRevertedNode(root []byte, iBatch int) {
173	if iBatch == 0 {
174		s.db.revertMux.Lock()
175		s.db.nodesToRevert = append(s.db.nodesToRevert, root)
176		s.db.revertMux.Unlock()
177	}
178}