types: Coins.Add chokes if a denomination is repeated and does not coalesce coins with same denomination {{2A}, {3A}, {1A}}.Add({2A}. {3A}) gives back {{5A}, {5A}, {1A}} but it should return {{10A}}

[odeke-em]

Summary of Bug

The code for Coins.Add unfortunately can't coalesce coins if there is a repeated denomination for example

func TestCoinsAdd(t *testing.T) {
        A := sdk.Coins{
                {"den", sdk.NewInt(2)},
                {"den", sdk.NewInt(3)},
        }
        B := sdk.Coins{
                {"den", sdk.NewInt(3)},
                {"den", sdk.NewInt(2)},
                {"den", sdk.NewInt(1)},
        }

        A = A.Sort()
        B = B.Sort()
        got := A.Add(B...)


        want := sdk.Coins{
                {"den", sdk.NewInt(11)},
        }

        if !got.IsEqual(want) {
                t.Fatalf("Wrong result\n\tGot:   %s\n\tWant: %s", got, want)
        }
}

fails with

--- FAIL: TestCoinsAdd (0.00s)
    coin_test.go:1230: Wrong result
        	Got:    5den,5den,1den
        	Want: 11den
FAIL
exit status 1
FAIL	github.com/cosmos/cosmos-sdk/types	0.300s

This bug was discovered in Quicksilver's code

Cause

The reasoning is that the code in Coins.Add tries to be clever with matching indices yet the code chokes for just a repeated denomination but really it should firstly coalesce coins, bucket them by denominations then add them up and sort the amount

Fix

This can simply be fixed by simplifying the code and coalescing like this:

diff --git a/types/coin.go b/types/coin.go
index 52155a6ed..8f2c5bebb 100644
--- a/types/coin.go
+++ b/types/coin.go
@@ -319,7 +319,7 @@ func (coins Coins) Add(coinsB ...Coin) Coins {
 // denomination and addition only occurs when the denominations match, otherwise
 // the coin is simply added to the sum assuming it's not zero.
 // The function panics if `coins` or  `coinsB` are not sorted (ascending).
-func (coins Coins) safeAdd(coinsB Coins) Coins {
+func (coins Coins) safeAdd(coinsB Coins) (coalesced Coins) {
 	// probably the best way will be to make Coins and interface and hide the structure
 	// definition (type alias)
 	if !coins.isSorted() {
@@ -329,51 +329,27 @@ func (coins Coins) safeAdd(coinsB Coins) Coins {
 		panic("Wrong argument: coins must be sorted")
 	}
 
-	sum := ([]Coin)(nil)
-	indexA, indexB := 0, 0
-	lenA, lenB := len(coins), len(coinsB)
-
-	for {
-		if indexA == lenA {
-			if indexB == lenB {
-				// return nil coins if both sets are empty
-				return sum
-			}
-
-			// return set B (excluding zero coins) if set A is empty
-			return append(sum, removeZeroCoins(coinsB[indexB:])...)
-		} else if indexB == lenB {
-			// return set A (excluding zero coins) if set B is empty
-			return append(sum, removeZeroCoins(coins[indexA:])...)
+	allCoins := append(coins, coinsB...)
+	uniqCoins := make(map[string]Coins)
+	anyDups := false
+	for _, c := range allCoins {
+		uniqCoins[c.Denom] = append(uniqCoins[c.Denom], c)
+		if len(uniqCoins[c.Denom]) > 1 {
+			anyDups = true
 		}
+	}
+	if !anyDups {
+		return allCoins.Sort()
+	}
 
-		coinA, coinB := coins[indexA], coinsB[indexB]
-
-		switch strings.Compare(coinA.Denom, coinB.Denom) {
-		case -1: // coin A denom < coin B denom
-			if !coinA.IsZero() {
-				sum = append(sum, coinA)
-			}
-
-			indexA++
-
-		case 0: // coin A denom == coin B denom
-			res := coinA.Add(coinB)
-			if !res.IsZero() {
-				sum = append(sum, res)
-			}
-
-			indexA++
-			indexB++
-
-		case 1: // coin A denom > coin B denom
-			if !coinB.IsZero() {
-				sum = append(sum, coinB)
-			}
-
-			indexB++
+	for denom, cL := range uniqCoins {
+		unitCoin := Coin{Denom: denom, Amount: NewInt(0)}
+		for _, c := range cL {
+			unitCoin = unitCoin.Add(c)
 		}
+		coalesced = append(coalesced, unitCoin)
 	}
+	return coalesced.Sort()
 }
 
 // DenomsSubsetOf returns true if receiver's denom set

or as pure Go

func (coins Coins) safeAdd(coinsB Coins) (coalesced Coins) {
        // probably the best way will be to make Coins and interface and hide the structure
        // definition (type alias)
        if !coins.isSorted() {
                panic("Coins (self) must be sorted")
        }
        if !coinsB.isSorted() {
                panic("Wrong argument: coins must be sorted")
        }

        allCoins := append(coins, coinsB...)
        uniqCoins := make(map[string]Coins)
        anyDups := false
        for _, c := range allCoins {
                uniqCoins[c.Denom] = append(uniqCoins[c.Denom], c)
                if len(uniqCoins[c.Denom]) > 1 {
                        anyDups = true
                }
        }
        if !anyDups {
                return allCoins.Sort()
        }

        for denom, cL := range uniqCoins {
                unitCoin := Coin{Denom: denom, Amount: NewInt(0)}
                for _, c := range cL {
                        unitCoin = unitCoin.Add(c)
                }
                coalesced = append(coalesced, unitCoin)
        }
        return coalesced.Sort()
}

Version

The latest at e5e9d81

A kind FYI for @elias-orijtech @kirbyquerby @willpoint @marbar3778. I am sending over a PR shortly, if this is the desired behavior but open to discussion.

[alexanderbez]

For the record, repeating denominations in Coins should never happen and breaks the invariant. This is why NewCoins exists -- use the constructor.

[tac0turtle]

@odeke-em would you like to submit a pr?

[odeke-em]

I mailed #13265 @marbar3778
@alexanderbez thanks for the input! The problem is that we provide general libraries that can be abused and we don't know what purposes and ways people might be using this code so it is only right that it correctly implements what it says it'll do.

[alexanderbez]

Yeah it doesn't hurt to provide this protection, just wanted to note the invariants.

[odeke-em]

Acknowledged, and thank you @alexanderbez!

[alexanderbez]

Thanks for the PR! :)