Repository: osmosis-labs/osmosis
Pull request #3934 (2023-01-06 13:55:24)

test(x/twap): geometric twap edge case tests (backport #3922)
This is an automatic backport of pull request #3922 done by [Mergify](https://mergify.com).


---


<details>
<summary>Mergify commands and options</summary>

<br />

More conditions and actions can be found in the [documentation](https://docs.mergify.com/).

You can also trigger Mergify actions by commenting on this pull request:

- `@Mergifyio refresh` will re-evaluate the rules
- `@Mergifyio rebase` will rebase this PR on its base branch
- `@Mergifyio update` will merge the base branch into this PR
- `@Mergifyio backport <destination>` will backport this PR on `<destination>` branch

Additionally, on Mergify [dashboard](https://dashboard.mergify.com/) you can:

- look at your merge queues
- generate the Mergify configuration with the config editor.

Finally, you can contact us on https://mergify.com
</details>


Patch:
diff --git a/osmomath/binary_search.go b/osmomath/binary_search.go
index d43c9dd3b..bd24fb18c 100644
--- a/osmomath/binary_search.go
+++ b/osmomath/binary_search.go
@@ -107,7 +107,7 @@ func (e ErrTolerance) CompareBigDec(expected BigDec, actual BigDec) int {
 	comparisonSign := 0
 	if expected.GT(actual) {
 		comparisonSign = 1
-	} else {
+	} else if expected.LT(actual) {
 		comparisonSign = -1
 	}
 
diff --git a/x/gamm/types/constants.go b/x/gamm/types/constants.go
index e7f3694ef..6c1991e3c 100644
--- a/x/gamm/types/constants.go
+++ b/x/gamm/types/constants.go
@@ -37,6 +37,9 @@ var (
 	// Other tests depend on being equal to MaxSpotPrice,
 	// but don't directly import it due to import issues.
 	MaxSpotPrice = sdk.NewDec(2).Power(128).Sub(sdk.OneDec())
+	// MinSpotPrice is the minimum supported spot price. Anything less than this will error.
+	// It is limited by sdk.Dec's precision.
+	MinSpotPrice = sdk.SmallestDec()
 
 	// MultihopSwapFeeMultiplierForOsmoPools if a swap fees multiplier for trades consists of just two OSMO pools during a single transaction.
 	MultihopSwapFeeMultiplierForOsmoPools = sdk.NewDecWithPrec(5, 1) // 0.5
diff --git a/x/twap/strategy.go b/x/twap/strategy.go
index 7863ff93a..4e6460bc6 100644
--- a/x/twap/strategy.go
+++ b/x/twap/strategy.go
@@ -43,6 +43,10 @@ func (s *arithmetic) computeTwap(startRecord types.TwapRecord, endRecord types.T
 func (s *geometric) computeTwap(startRecord types.TwapRecord, endRecord types.TwapRecord, quoteAsset string) sdk.Dec {
 	accumDiff := endRecord.GeometricTwapAccumulator.Sub(startRecord.GeometricTwapAccumulator)
 
+	if accumDiff.IsZero() {
+		return sdk.ZeroDec()
+	}
+
 	timeDelta := endRecord.Time.Sub(startRecord.Time)
 	arithmeticMeanOfLogPrices := types.AccumDiffDivDuration(accumDiff, timeDelta)
 


Test patch:
diff --git a/x/twap/strategy_test.go b/x/twap/strategy_test.go
index f5208f4c9..9abdadd04 100644
--- a/x/twap/strategy_test.go
+++ b/x/twap/strategy_test.go
@@ -22,10 +22,6 @@ type computeTwapTestCase struct {
 	expPanic       bool
 }
 
-var (
-	oneHundredYears = OneSec.MulInt64(60 * 60 * 24 * 365 * 100)
-)
-
 // TestComputeArithmeticTwap tests computeTwap on various inputs.
 // The test vectors are structured by setting up different start and records,
 // based on time interval, and their accumulator values.
@@ -166,6 +162,34 @@ func (s *TestSuite) TestComputeArithmeticStrategyTwap() {
 // Contrary to computeTwap function (logic.go) that handles the cases with zero delta correctly,
 // this function should panic in case of zero delta.
 func (s *TestSuite) TestComputeGeometricStrategyTwap() {
+	var (
+		errTolerance = osmomath.ErrTolerance{
+			MultiplicativeTolerance: sdk.SmallestDec(),
+			RoundingDir:             osmomath.RoundDown,
+		}
+
+		// Compute accumulator difference for the underflow test case by
+		// taking log base 2 of the min spot price
+		minSpotPriceLogBase2 = twap.TwapLog(gammtypes.MinSpotPrice)
+
+		// Compute accumulator difference for the overflow test case by
+		// taking log base 2 of the max spot price
+		maxSpotPriceLogBase2 = twap.TwapLog(gammtypes.MaxSpotPrice)
+
+		oneHundredYearsInHours        int64 = 100 * 365 * 24
+		oneHundredYears                     = OneSec.MulInt64(60 * 60 * oneHundredYearsInHours)
+		oneHundredYearsMin1MsDuration       = time.Duration(oneHundredYearsInHours)*time.Hour - time.Millisecond
+
+		// Subtract 1ms from 100 years to assume that we interpolate.
+		oneHundredYearsMin1Ms = oneHundredYears.Sub(oneDec)
+
+		// Calculate the geometric accumulator difference for overflow test case.
+		overflowTestCaseAccumDiff = oneHundredYearsMin1Ms.Mul(maxSpotPriceLogBase2)
+
+		// Calculate the geometric accumulator difference for underflow test case.
+		underflowTestCaseAccumDiff = oneHundredYearsMin1Ms.Mul(minSpotPriceLogBase2)
+	)
+
 	tests := map[string]computeTwapTestCase{
 		// basic test for both denom with zero start accumulator
 		"basic denom0: spot price = 1 for one second, 0 init accumulator": {
@@ -211,28 +235,63 @@ func (s *TestSuite) TestComputeGeometricStrategyTwap() {
 		"accumulator = 10*OneSec, t=100s. .1*second base accum": geometricTestCaseFromDeltas0(
 			s, OneSec.MulInt64(10).Mul(logOneOverTen), geometricTenSecAccum, 100*time.Second, twap.TwapPow(geometricTenSecAccum.QuoInt64(100*1000))),
 
-		// TODO: this is the highest price we currently support with the given precision bounds.
-		// Need to choose better base and potentially improve math functions to mitigate.
 		"price of 1_000_000 for an hour": {
 			startRecord: newOneSidedGeometricRecord(baseTime, sdk.ZeroDec()),
 			endRecord:   newOneSidedGeometricRecord(baseTime.Add(time.Hour), OneSec.MulInt64(60*60).Mul(twap.TwapLog(sdk.NewDec(1_000_000)))),
 			quoteAsset:  denom0,
 			expTwap:     sdk.NewDec(1_000_000),
 		},
-		// TODO: overflow tests
-		// - max spot price
-		// - large time delta
-		// - both
 
-		// TODO: hand calculated tests
+		"no overflow test: at max spot price denom0 quote - get max spot price": {
+			startRecord: withSp0(baseRecord, gammtypes.MaxSpotPrice),
+			endRecord:   newOneSidedGeometricRecord(baseRecord.Time.Add(oneHundredYearsMin1MsDuration), overflowTestCaseAccumDiff),
+			quoteAsset:  denom0,
+			expTwap:     gammtypes.MaxSpotPrice,
+		},
+
+		"expected precision loss test: - at spot price denom1 quote - return zero": {
+			startRecord: withSp0(baseRecord, gammtypes.MaxSpotPrice),
+			endRecord:   newOneSidedGeometricRecord(baseRecord.Time.Add(oneHundredYearsMin1MsDuration), overflowTestCaseAccumDiff),
+			quoteAsset:  denom1,
+
+			expTwap: sdk.ZeroDec(),
+		},
+
+		"no underflow test: spot price is smallest possible denom0 quote": {
+			startRecord: newOneSidedGeometricRecord(baseTime, sdk.ZeroDec()),
+			endRecord:   newOneSidedGeometricRecord(baseRecord.Time.Add(oneHundredYearsMin1MsDuration), underflowTestCaseAccumDiff),
+			quoteAsset:  denom0,
+			expTwap:     gammtypes.MinSpotPrice,
+		},
+
+		"no underflow test: spot price is smallest possible denom1 quote": {
+			startRecord: newOneSidedGeometricRecord(baseTime, sdk.ZeroDec()),
+			endRecord:   newOneSidedGeometricRecord(baseRecord.Time.Add(oneHundredYearsMin1MsDuration), underflowTestCaseAccumDiff),
+			quoteAsset:  denom1,
+			expTwap:     sdk.OneDec().Quo(gammtypes.MinSpotPrice),
+		},
+
+		"zero accum difference - return zero": {
+			startRecord: newOneSidedGeometricRecord(baseTime, sdk.ZeroDec()),
+			endRecord:   newOneSidedGeometricRecord(baseRecord.Time.Add(time.Millisecond), sdk.ZeroDec()),
+			quoteAsset:  denom1,
+
+			expTwap: sdk.ZeroDec(),
+		},
 	}
 
 	for name, tc := range tests {
+		tc := tc
 		s.Run(name, func() {
 			osmoassert.ConditionalPanic(s.T(), tc.expPanic, func() {
+
 				geometricStrategy := &twap.GeometricTwapStrategy{TwapKeeper: *s.App.TwapKeeper}
 				actualTwap := geometricStrategy.ComputeTwap(tc.startRecord, tc.endRecord, tc.quoteAsset)
-				osmoassert.DecApproxEq(s.T(), tc.expTwap, actualTwap, osmomath.GetPowPrecision())
+
+				// Sig fig round the expected value.
+				tc.expTwap = osmomath.SigFigRound(tc.expTwap, gammtypes.SpotPriceSigFigs)
+
+				s.Require().Equal(0, errTolerance.CompareBigDec(osmomath.BigDecFromSDKDec(tc.expTwap), osmomath.BigDecFromSDKDec(actualTwap)), "expected %s, got %s", tc.expTwap, actualTwap)
 			})
 		})
 	}
@@ -305,19 +364,3 @@ func (s *TestSuite) TestComputeGeometricStrategyTwap_ThreeAsset() {
 		})
 	}
 }
-
-// TestTwapPow_MaxSpotPrice_NoOverflow tests that no overflow occurs at log_2{max spot price values}.
-// and that the epsilon is within the tolerated multiplicative error.
-func (s *TestSuite) TestTwapLogPow_MaxSpotPrice_NoOverflow() {
-	errTolerance := osmomath.ErrTolerance{
-		MultiplicativeTolerance: sdk.OneDec().Quo(sdk.NewDec(10).Power(18)),
-		RoundingDir:             osmomath.RoundDown,
-	}
-
-	oneHundredYearsTimesMaxSpotPrice := oneHundredYears.Mul(gammtypes.MaxSpotPrice)
-
-	exponentValue := twap.TwapLog(oneHundredYearsTimesMaxSpotPrice)
-	finalValue := twap.TwapPow(exponentValue)
-
-	s.Require().Equal(0, errTolerance.CompareBigDec(osmomath.BigDecFromSDKDec(oneHundredYearsTimesMaxSpotPrice), osmomath.BigDecFromSDKDec(finalValue)))
-}