Repository: kaspanet/kaspad
Pull request #1153 (2020-11-25 15:28:42)

[NOD-1570] Fix the way UTXO iterators work


Patch:
diff --git a/domain/consensus/processes/consensusstatemanager/calculate_past_utxo.go b/domain/consensus/processes/consensusstatemanager/calculate_past_utxo.go
index 1b33df78..a988c94e 100644
--- a/domain/consensus/processes/consensusstatemanager/calculate_past_utxo.go
+++ b/domain/consensus/processes/consensusstatemanager/calculate_past_utxo.go
@@ -4,13 +4,14 @@ import (
 	"github.com/kaspanet/kaspad/domain/consensus/utils/consensusserialization"
 	"github.com/kaspanet/kaspad/domain/consensus/utils/constants"
 	"github.com/kaspanet/kaspad/domain/consensus/utils/multiset"
+	"github.com/kaspanet/kaspad/domain/consensus/utils/utxo"
 	"github.com/pkg/errors"
 
 	"github.com/kaspanet/kaspad/domain/consensus/model"
 	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
-	"github.com/kaspanet/kaspad/domain/consensus/processes/consensusstatemanager/utxoalgebra"
 	"github.com/kaspanet/kaspad/domain/consensus/ruleerrors"
 	"github.com/kaspanet/kaspad/domain/consensus/utils/transactionhelper"
+	"github.com/kaspanet/kaspad/domain/consensus/utils/utxo/utxoalgebra"
 )
 
 func (csm *consensusStateManager) CalculatePastUTXOAndAcceptanceData(blockHash *externalapi.DomainHash) (
@@ -249,14 +250,25 @@ func (csm *consensusStateManager) checkTransactionMass(
 	return true, accumulatedMassAfter
 }
 
+// RestorePastUTXOSetIterator restores the given block's UTXOSet iterator, and returns it as a model.ReadOnlyUTXOSetIterator
 func (csm *consensusStateManager) RestorePastUTXOSetIterator(blockHash *externalapi.DomainHash) (
 	model.ReadOnlyUTXOSetIterator, error) {
 
+	blockStatus, err := csm.resolveBlockStatus(blockHash)
+	if err != nil {
+		return nil, err
+	}
+	if blockStatus != externalapi.StatusValid {
+		return nil, errors.Errorf(
+			"block %s, has status '%s', and therefore can't restore it's UTXO set. Only blocks with status '%s' can be restored.",
+			blockHash, blockStatus, externalapi.StatusValid)
+	}
+
 	log.Tracef("RestorePastUTXOSetIterator start for block %s", blockHash)
 	defer log.Tracef("RestorePastUTXOSetIterator end for block %s", blockHash)
 
 	log.Tracef("Calculating UTXO diff for block %s", blockHash)
-	blockDiff, _, _, err := csm.CalculatePastUTXOAndAcceptanceData(blockHash)
+	blockDiff, err := csm.restorePastUTXO(blockHash)
 	if err != nil {
 		return nil, err
 	}
@@ -266,56 +278,5 @@ func (csm *consensusStateManager) RestorePastUTXOSetIterator(blockHash *external
 		return nil, err
 	}
 
-	virtualUTXO := model.NewUTXODiff()
-	for virtualUTXOSetIterator.Next() {
-		outpoint, utxoEntry, err := virtualUTXOSetIterator.Get()
-		if err != nil {
-			return nil, err
-		}
-		virtualUTXO.ToAdd[*outpoint] = utxoEntry
-	}
-
-	blockUTXO, err := utxoalgebra.WithDiff(virtualUTXO, blockDiff)
-	if err != nil {
-		return nil, err
-	}
-
-	if len(blockUTXO.ToRemove) > 0 {
-		return nil, errors.New("blockUTXO.ToRemove is expected to be empty")
-	}
-
-	return newUTXOSetIterator(blockUTXO.ToAdd), nil
-}
-
-type utxoOutpointEntryPair struct {
-	outpoint externalapi.DomainOutpoint
-	entry    *externalapi.UTXOEntry
-}
-
-type utxoSetIterator struct {
-	index int
-	pairs []utxoOutpointEntryPair
-}
-
-func newUTXOSetIterator(collection model.UTXOCollection) *utxoSetIterator {
-	pairs := make([]utxoOutpointEntryPair, len(collection))
-	i := 0
-	for outpoint, entry := range collection {
-		pairs[i] = utxoOutpointEntryPair{
-			outpoint: outpoint,
-			entry:    entry,
-		}
-		i++
-	}
-	return &utxoSetIterator{index: -1, pairs: pairs}
-}
-
-func (u *utxoSetIterator) Next() bool {
-	u.index++
-	return u.index < len(u.pairs)
-}
-
-func (u *utxoSetIterator) Get() (outpoint *externalapi.DomainOutpoint, utxoEntry *externalapi.UTXOEntry, err error) {
-	pair := u.pairs[u.index]
-	return &pair.outpoint, pair.entry, nil
+	return utxo.IteratorWithDiff(virtualUTXOSetIterator, blockDiff)
 }
diff --git a/domain/consensus/processes/consensusstatemanager/populate_tx_with_utxo_entries.go b/domain/consensus/processes/consensusstatemanager/populate_tx_with_utxo_entries.go
index 08147f00..9e9f4a00 100644
--- a/domain/consensus/processes/consensusstatemanager/populate_tx_with_utxo_entries.go
+++ b/domain/consensus/processes/consensusstatemanager/populate_tx_with_utxo_entries.go
@@ -3,9 +3,9 @@ package consensusstatemanager
 import (
 	"github.com/kaspanet/kaspad/domain/consensus/model"
 	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
-	"github.com/kaspanet/kaspad/domain/consensus/processes/consensusstatemanager/utxoalgebra"
 	"github.com/kaspanet/kaspad/domain/consensus/ruleerrors"
 	"github.com/kaspanet/kaspad/domain/consensus/utils/consensusserialization"
+	"github.com/kaspanet/kaspad/domain/consensus/utils/utxo/utxoalgebra"
 )
 
 // PopulateTransactionWithUTXOEntries populates the transaction UTXO entries with data from the virtual's UTXO set.
diff --git a/domain/consensus/processes/consensusstatemanager/resolve_block_status.go b/domain/consensus/processes/consensusstatemanager/resolve_block_status.go
index eb6998f2..bd54054c 100644
--- a/domain/consensus/processes/consensusstatemanager/resolve_block_status.go
+++ b/domain/consensus/processes/consensusstatemanager/resolve_block_status.go
@@ -3,8 +3,8 @@ package consensusstatemanager
 import (
 	"github.com/kaspanet/kaspad/domain/consensus/model"
 	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
-	"github.com/kaspanet/kaspad/domain/consensus/processes/consensusstatemanager/utxoalgebra"
 	"github.com/kaspanet/kaspad/domain/consensus/ruleerrors"
+	"github.com/kaspanet/kaspad/domain/consensus/utils/utxo/utxoalgebra"
 	"github.com/pkg/errors"
 )
 
diff --git a/domain/consensus/processes/consensusstatemanager/update_virtual.go b/domain/consensus/processes/consensusstatemanager/update_virtual.go
index 001b675c..f93bbe10 100644
--- a/domain/consensus/processes/consensusstatemanager/update_virtual.go
+++ b/domain/consensus/processes/consensusstatemanager/update_virtual.go
@@ -3,7 +3,7 @@ package consensusstatemanager
 import (
 	"github.com/kaspanet/kaspad/domain/consensus/model"
 	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
-	"github.com/kaspanet/kaspad/domain/consensus/processes/consensusstatemanager/utxoalgebra"
+	"github.com/kaspanet/kaspad/domain/consensus/utils/utxo/utxoalgebra"
 )
 
 func (csm *consensusStateManager) updateVirtual(newBlockHash *externalapi.DomainHash, tips []*externalapi.DomainHash) error {
diff --git a/domain/consensus/utils/utxo/utxo_iterator.go b/domain/consensus/utils/utxo/utxo_iterator.go
new file mode 100644
index 00000000..d75b33c5
--- /dev/null
+++ b/domain/consensus/utils/utxo/utxo_iterator.go
@@ -0,0 +1,40 @@
+package utxo
+
+import (
+	"github.com/kaspanet/kaspad/domain/consensus/model"
+	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
+)
+
+type utxoOutpointEntryPair struct {
+	outpoint externalapi.DomainOutpoint
+	entry    *externalapi.UTXOEntry
+}
+
+type utxoCollectionIterator struct {
+	index int
+	pairs []utxoOutpointEntryPair
+}
+
+// CollectionIterator creates a utxo iterator from give UTXO collection
+func CollectionIterator(collection model.UTXOCollection) model.ReadOnlyUTXOSetIterator {
+	pairs := make([]utxoOutpointEntryPair, len(collection))
+	i := 0
+	for outpoint, entry := range collection {
+		pairs[i] = utxoOutpointEntryPair{
+			outpoint: outpoint,
+			entry:    entry,
+		}
+		i++
+	}
+	return &utxoCollectionIterator{index: -1, pairs: pairs}
+}
+
+func (u *utxoCollectionIterator) Next() bool {
+	u.index++
+	return u.index < len(u.pairs)
+}
+
+func (u *utxoCollectionIterator) Get() (outpoint *externalapi.DomainOutpoint, utxoEntry *externalapi.UTXOEntry, err error) {
+	pair := u.pairs[u.index]
+	return &pair.outpoint, pair.entry, nil
+}
diff --git a/domain/consensus/utils/utxo/utxo_iterator_with_diff.go b/domain/consensus/utils/utxo/utxo_iterator_with_diff.go
new file mode 100644
index 00000000..f8b0da03
--- /dev/null
+++ b/domain/consensus/utils/utxo/utxo_iterator_with_diff.go
@@ -0,0 +1,56 @@
+package utxo
+
+import (
+	"github.com/kaspanet/kaspad/domain/consensus/model"
+	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
+	"github.com/kaspanet/kaspad/domain/consensus/utils/utxo/utxoalgebra"
+)
+
+type readOnlyUTXOIteratorWithDiff struct {
+	baseIterator model.ReadOnlyUTXOSetIterator
+	diff         *model.UTXODiff
+
+	currentOutpoint  *externalapi.DomainOutpoint
+	currentUTXOEntry *externalapi.UTXOEntry
+	currentErr       error
+
+	toAddIterator model.ReadOnlyUTXOSetIterator
+}
+
+// IteratorWithDiff applies a UTXODiff to given utxo iterator
+func IteratorWithDiff(iterator model.ReadOnlyUTXOSetIterator, diff *model.UTXODiff) (model.ReadOnlyUTXOSetIterator, error) {
+	if iteratorWithDiff, ok := iterator.(*readOnlyUTXOIteratorWithDiff); ok {
+		combinedDiff, err := utxoalgebra.WithDiff(iteratorWithDiff.diff, diff)
+		if err != nil {
+			return nil, err
+		}
+
+		return IteratorWithDiff(iteratorWithDiff.baseIterator, combinedDiff)
+	}
+
+	return &readOnlyUTXOIteratorWithDiff{
+		baseIterator:  iterator,
+		diff:          diff,
+		toAddIterator: CollectionIterator(diff.ToAdd),
+	}, nil
+}
+
+func (r *readOnlyUTXOIteratorWithDiff) Next() bool {
+	for r.baseIterator.Next() { // keep looping until we reach an outpoint/entry pair that is not in r.diff.ToRemove
+		r.currentOutpoint, r.currentUTXOEntry, r.currentErr = r.baseIterator.Get()
+		if !utxoalgebra.CollectionContainsWithBlueScore(r.diff.ToRemove, r.currentOutpoint, r.currentUTXOEntry.BlockBlueScore) {
+			return true
+		}
+	}
+
+	if r.toAddIterator.Next() {
+		r.currentOutpoint, r.currentUTXOEntry, r.currentErr = r.toAddIterator.Get()
+		return true
+	}
+
+	return false
+}
+
+func (r *readOnlyUTXOIteratorWithDiff) Get() (outpoint *externalapi.DomainOutpoint, utxoEntry *externalapi.UTXOEntry, err error) {
+	return r.currentOutpoint, r.currentUTXOEntry, r.currentErr
+}
diff --git a/domain/consensus/processes/consensusstatemanager/utxoalgebra/collection_helpers.go b/domain/consensus/utils/utxo/utxoalgebra/collection_helpers.go
similarity index 92%
rename from domain/consensus/processes/consensusstatemanager/utxoalgebra/collection_helpers.go
rename to domain/consensus/utils/utxo/utxoalgebra/collection_helpers.go
index 148ea926..f0e969cf 100644
--- a/domain/consensus/processes/consensusstatemanager/utxoalgebra/collection_helpers.go
+++ b/domain/consensus/utils/utxo/utxoalgebra/collection_helpers.go
@@ -42,9 +42,9 @@ func CollectionContains(collection model.UTXOCollection, outpoint *externalapi.D
 	return ok
 }
 
-// containsWithBlueScore returns a boolean value indicating whether a model.UTXOEntry
+// CollectionContainsWithBlueScore returns a boolean value indicating whether a model.UTXOEntry
 // is in the set and its blue score is equal to the given blue score.
-func collectionContainsWithBlueScore(collection model.UTXOCollection, outpoint *externalapi.DomainOutpoint, blueScore uint64) bool {
+func CollectionContainsWithBlueScore(collection model.UTXOCollection, outpoint *externalapi.DomainOutpoint, blueScore uint64) bool {
 	entry, ok := CollectionGet(collection, outpoint)
 	return ok && entry.BlockBlueScore == blueScore
 }
diff --git a/domain/consensus/processes/consensusstatemanager/utxoalgebra/diff_algebra.go b/domain/consensus/utils/utxo/utxoalgebra/diff_algebra.go
similarity index 95%
rename from domain/consensus/processes/consensusstatemanager/utxoalgebra/diff_algebra.go
rename to domain/consensus/utils/utxo/utxoalgebra/diff_algebra.go
index 9bcaf3f0..ad186c74 100644
--- a/domain/consensus/processes/consensusstatemanager/utxoalgebra/diff_algebra.go
+++ b/domain/consensus/utils/utxo/utxoalgebra/diff_algebra.go
@@ -56,7 +56,7 @@ func intersectionWithRemainderHavingBlueScore(collection1, collection2 model.UTX
 // having same blue score, puts it into result and into remainder from collection1
 func intersectionWithRemainderHavingBlueScoreInPlace(collection1, collection2, result, remainder model.UTXOCollection) {
 	for outpoint, utxoEntry := range collection1 {
-		if collectionContainsWithBlueScore(collection2, &outpoint, utxoEntry.BlockBlueScore) {
+		if CollectionContainsWithBlueScore(collection2, &outpoint, utxoEntry.BlockBlueScore) {
 			collectionAdd(result, &outpoint, utxoEntry)
 		} else {
 			collectionAdd(remainder, &outpoint, utxoEntry)
@@ -77,7 +77,7 @@ func subtractionHavingBlueScore(collection1, collection2 model.UTXOCollection) (
 // having same blue score, puts it into result
 func subtractionHavingBlueScoreInPlace(collection1, collection2, result model.UTXOCollection) {
 	for outpoint, utxoEntry := range collection1 {
-		if !collectionContainsWithBlueScore(collection2, &outpoint, utxoEntry.BlockBlueScore) {
+		if !CollectionContainsWithBlueScore(collection2, &outpoint, utxoEntry.BlockBlueScore) {
 			collectionAdd(result, &outpoint, utxoEntry)
 		}
 	}
@@ -97,7 +97,7 @@ func subtractionWithRemainderHavingBlueScore(collection1, collection2 model.UTXO
 // having same blue score, puts it into result and into remainder from collection1
 func subtractionWithRemainderHavingBlueScoreInPlace(collection1, collection2, result, remainder model.UTXOCollection) {
 	for outpoint, utxoEntry := range collection1 {
-		if !collectionContainsWithBlueScore(collection2, &outpoint, utxoEntry.BlockBlueScore) {
+		if !CollectionContainsWithBlueScore(collection2, &outpoint, utxoEntry.BlockBlueScore) {
 			collectionAdd(result, &outpoint, utxoEntry)
 		} else {
 			collectionAdd(remainder, &outpoint, utxoEntry)
@@ -142,8 +142,8 @@ func DiffFrom(this, other *model.UTXODiff) (*model.UTXODiff, error) {
 	// check that NOT (entries with unequal blue scores AND utxoEntry is in this.ToAdd and/or other.ToRemove) -> Error
 	isNotAddedOutputRemovedWithBlueScore := func(outpoint *externalapi.DomainOutpoint, utxoEntry, diffEntry *externalapi.UTXOEntry) bool {
 		return !(diffEntry.BlockBlueScore != utxoEntry.BlockBlueScore &&
-			(collectionContainsWithBlueScore(this.ToAdd, outpoint, diffEntry.BlockBlueScore) ||
-				collectionContainsWithBlueScore(other.ToRemove, outpoint, utxoEntry.BlockBlueScore)))
+			(CollectionContainsWithBlueScore(this.ToAdd, outpoint, diffEntry.BlockBlueScore) ||
+				CollectionContainsWithBlueScore(other.ToRemove, outpoint, utxoEntry.BlockBlueScore)))
 	}
 
 	if offendingOutpoint, ok :=
@@ -156,8 +156,8 @@ func DiffFrom(this, other *model.UTXODiff) (*model.UTXODiff, error) {
 		func(outpoint *externalapi.DomainOutpoint, utxoEntry, diffEntry *externalapi.UTXOEntry) bool {
 
 			return !(diffEntry.BlockBlueScore != utxoEntry.BlockBlueScore &&
-				(collectionContainsWithBlueScore(this.ToRemove, outpoint, diffEntry.BlockBlueScore) ||
-					collectionContainsWithBlueScore(other.ToAdd, outpoint, utxoEntry.BlockBlueScore)))
+				(CollectionContainsWithBlueScore(this.ToRemove, outpoint, diffEntry.BlockBlueScore) ||
+					CollectionContainsWithBlueScore(other.ToAdd, outpoint, utxoEntry.BlockBlueScore)))
 		}
 
 	if offendingOutpoint, ok :=
@@ -210,7 +210,7 @@ func DiffFrom(this, other *model.UTXODiff) (*model.UTXODiff, error) {
 func WithDiffInPlace(this *model.UTXODiff, diff *model.UTXODiff) error {
 	if offendingOutpoint, ok := checkIntersectionWithRule(diff.ToRemove, this.ToRemove,
 		func(outpoint *externalapi.DomainOutpoint, entryToAdd, existingEntry *externalapi.UTXOEntry) bool {
-			return !collectionContainsWithBlueScore(this.ToAdd, outpoint, entryToAdd.BlockBlueScore)
+			return !CollectionContainsWithBlueScore(this.ToAdd, outpoint, entryToAdd.BlockBlueScore)
 		}); ok {
 		return errors.Errorf(
 			"withDiffInPlace: outpoint %s both in this.ToRemove and in diff.ToRemove", offendingOutpoint)
@@ -218,7 +218,7 @@ func WithDiffInPlace(this *model.UTXODiff, diff *model.UTXODiff) error {
 
 	if offendingOutpoint, ok := checkIntersectionWithRule(diff.ToAdd, this.ToAdd,
 		func(outpoint *externalapi.DomainOutpoint, entryToAdd, existingEntry *externalapi.UTXOEntry) bool {
-			return !collectionContainsWithBlueScore(diff.ToRemove, outpoint, existingEntry.BlockBlueScore)
+			return !CollectionContainsWithBlueScore(diff.ToRemove, outpoint, existingEntry.BlockBlueScore)
 		}); ok {
 		return errors.Errorf(
 			"withDiffInPlace: outpoint %s both in this.ToAdd and in diff.ToAdd", offendingOutpoint)
diff --git a/domain/consensus/processes/consensusstatemanager/utxoalgebra/diff_algebra_test.go b/domain/consensus/utils/utxo/utxoalgebra/diff_algebra_test.go
similarity index 100%
rename from domain/consensus/processes/consensusstatemanager/utxoalgebra/diff_algebra_test.go
rename to domain/consensus/utils/utxo/utxoalgebra/diff_algebra_test.go
diff --git a/domain/consensus/processes/consensusstatemanager/utxoalgebra/diff_helpers.go b/domain/consensus/utils/utxo/utxoalgebra/diff_helpers.go
similarity index 94%
rename from domain/consensus/processes/consensusstatemanager/utxoalgebra/diff_helpers.go
rename to domain/consensus/utils/utxo/utxoalgebra/diff_helpers.go
index 2eb45829..98545f79 100644
--- a/domain/consensus/processes/consensusstatemanager/utxoalgebra/diff_helpers.go
+++ b/domain/consensus/utils/utxo/utxoalgebra/diff_helpers.go
@@ -45,7 +45,7 @@ func DiffAddTransaction(utxoDiff *model.UTXODiff, transaction *externalapi.Domai
 }
 
 func diffAddEntry(diff *model.UTXODiff, outpoint *externalapi.DomainOutpoint, entry *externalapi.UTXOEntry) error {
-	if collectionContainsWithBlueScore(diff.ToRemove, outpoint, entry.BlockBlueScore) {
+	if CollectionContainsWithBlueScore(diff.ToRemove, outpoint, entry.BlockBlueScore) {
 		collectionRemove(diff.ToRemove, outpoint)
 	} else if _, exists := diff.ToAdd[*outpoint]; exists {
 		return errors.Errorf("AddEntry: Cannot add outpoint %s twice", outpoint)
@@ -56,7 +56,7 @@ func diffAddEntry(diff *model.UTXODiff, outpoint *externalapi.DomainOutpoint, en
 }
 
 func diffRemoveEntry(diff *model.UTXODiff, outpoint *externalapi.DomainOutpoint, entry *externalapi.UTXOEntry) error {
-	if collectionContainsWithBlueScore(diff.ToAdd, outpoint, entry.BlockBlueScore) {
+	if CollectionContainsWithBlueScore(diff.ToAdd, outpoint, entry.BlockBlueScore) {
 		collectionRemove(diff.ToAdd, outpoint)
 	} else if _, exists := diff.ToRemove[*outpoint]; exists {
 		return errors.Errorf("removeEntry: Cannot remove outpoint %s twice", outpoint)


Test patch:
diff --git a/domain/consensus/datastructures/consensusstatestore/utxo.go b/domain/consensus/datastructures/consensusstatestore/utxo.go
index fe510a71..42ad6e02 100644
--- a/domain/consensus/datastructures/consensusstatestore/utxo.go
+++ b/domain/consensus/datastructures/consensusstatestore/utxo.go
@@ -4,6 +4,7 @@ import (
 	"github.com/kaspanet/kaspad/domain/consensus/model"
 	"github.com/kaspanet/kaspad/domain/consensus/model/externalapi"
 	"github.com/kaspanet/kaspad/domain/consensus/utils/dbkeys"
+	"github.com/kaspanet/kaspad/domain/consensus/utils/utxo"
 	"github.com/pkg/errors"
 )
 
@@ -172,14 +173,19 @@ func (css *consensusStateStore) VirtualUTXOSetIterator(dbContext model.DBReader)
 		return nil, err
 	}
 
-	return newUTXOSetIterator(cursor), nil
+	mainIterator := newCursorUTXOSetIterator(cursor)
+	if css.virtualUTXODiffStaging != nil {
+		return utxo.IteratorWithDiff(mainIterator, css.virtualUTXODiffStaging)
+	}
+
+	return mainIterator, nil
 }
 
 type utxoSetIterator struct {
 	cursor model.DBCursor
 }
 
-func newUTXOSetIterator(cursor model.DBCursor) model.ReadOnlyUTXOSetIterator {
+func newCursorUTXOSetIterator(cursor model.DBCursor) model.ReadOnlyUTXOSetIterator {
 	return &utxoSetIterator{cursor: cursor}
 }