types: Coins.safeAdd is more complex than needed with separated 2 different counters for indices of the various slices being added, and hard to read nor check for correctness

[odeke-em]

Coming here from an audit, I noticed the logic in Coins.safeAdd is quite hard to follow and uses 2 different counters for index i.e.

cosmos-sdk/types/coin.go

Lines 237 to 288 in 6f928e1

	// safeAdd will perform addition of two coins sets. If both coin sets are
	// empty, then an empty set is returned. If only a single set is empty, the
	// other set is returned. Otherwise, the coins are compared in order of their
	// denomination and addition only occurs when the denominations match, otherwise
	// the coin is simply added to the sum assuming it's not zero.
	func (coins Coins) safeAdd(coinsB Coins) Coins {
	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:])...)
	}
	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++
	}
	}
	}

and there is one case that isn't tested, which is when higher lexicographic values of denomination are passed in, in the first Coin slice than the other.

If we asked a random person off the street to describe this algorithm and what it does, they'll likely take a while and stare at the code without figuring out what it does.

I believe we can totally simplify this logic by following the purpose and name of the algorithm and can thus simplify it

We want to add coins of the same denomination to each other

With that we don't need to special case conditions and this becomes just a grouping problem by a map, mapping denominations to their sums and that's it and here is the logic to simplify it

func (coins Coins) safeAdd(coinsB Coins) Coins {
        uniqSumByDenom := make(map[string]Coin)
        combo := append(coins, coinsB...)
        for _, coin := range combo {
                if coin.IsZero() {
                        continue
                }

                sum, ok := uniqSumByDenom[coin.Denom]
                if !ok {
                        sum = coin
                } else {
                        sum = sum.Add(coin)
                }
                uniqSumByDenom[sum.Denom] = sum
        }
        if len(uniqSumByDenom) == 0 {
                return nil
        }

        allCoins := make(Coins, 0, len(uniqSumByDenom))
        for _, sum := range uniqSumByDenom {
                allCoins = append(allCoins, sum)
        }
        return removeZeroCoins(allCoins).Sort()
}

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[odeke-em]

Aha I coincidentally fixed this issue by PR #13265 and commit 83f88a6 which massively simplified the code.