oracle.gno

  1package pool
  2
  3import (
  4	"errors"
  5	"time"
  6
  7	"gno.land/p/gnoswap/consts"
  8	u256 "gno.land/p/gnoswap/uint256"
  9	pl "gno.land/r/gnoswap/pool"
 10)
 11
 12// maxObservationCardinality defines the maximum number of observations to store
 13const maxObservationCardinality uint16 = 65535
 14
 15// GetTWAP calculates the time-weighted average price between two points in time
 16// Returns the arithmetic mean tick and harmonic mean liquidity over the time period
 17func getTWAP(p *pl.Pool, secondsAgo uint32) (int32, *u256.Uint, error) {
 18	if secondsAgo == 0 {
 19		return 0, nil, errors.New("secondsAgo must be greater than 0")
 20	}
 21
 22	if p.ObservationState() == nil {
 23		return 0, nil, errors.New("observation state not initialized")
 24	}
 25
 26	// Get observations for current time and secondsAgo
 27	secondsAgos := []uint32{secondsAgo, 0}
 28	currentTime := time.Now().Unix()
 29
 30	tickCumulatives, secondsPerLiquidityCumulativeX128s, err := observe(
 31		p.ObservationState(),
 32		currentTime,
 33		secondsAgos,
 34		p.Slot0Tick(),
 35		p.ObservationState().Index(),
 36		p.Liquidity(),
 37		p.ObservationState().Cardinality(),
 38	)
 39	if err != nil {
 40		return 0, nil, err
 41	}
 42
 43	tickCumulativesDelta := tickCumulatives[1] - tickCumulatives[0]
 44	secondsPerLiquidityDelta := u256.Zero().Sub(
 45		u256.MustFromDecimal(secondsPerLiquidityCumulativeX128s[1]),
 46		u256.MustFromDecimal(secondsPerLiquidityCumulativeX128s[0]),
 47	)
 48
 49	arithmeticMeanTick := int32(tickCumulativesDelta / int64(secondsAgo))
 50	if tickCumulativesDelta < 0 && (tickCumulativesDelta%int64(secondsAgo) != 0) {
 51		arithmeticMeanTick--
 52	}
 53
 54	if secondsPerLiquidityDelta.IsZero() {
 55		return arithmeticMeanTick, u256.Zero(), nil
 56	}
 57
 58	// Calculate harmonic mean liquidity
 59	secondsAgoX160 := u256.Zero().Mul(u256.NewUint(uint64(secondsAgo)), consts.Max160())
 60	denominator := u256.Zero().Lsh(secondsPerLiquidityDelta, 32)
 61	harmonicMeanLiquidity := u256.Zero().Div(secondsAgoX160, denominator)
 62
 63	return arithmeticMeanTick, harmonicMeanLiquidity, nil
 64}
 65
 66func writeObservationByPool(
 67	p *pl.Pool,
 68	currentTime int64,
 69	tick int32,
 70	liquidity *u256.Uint,
 71) error {
 72	if p.ObservationState() == nil {
 73		p.SetObservationState(pl.NewObservationState(currentTime))
 74	}
 75
 76	err := writeObservation(p.ObservationState(), currentTime, tick, liquidity)
 77	if err != nil {
 78		return err
 79	}
 80
 81	return nil
 82}
 83
 84func increaseObservationCardinalityNextByPool(p *pl.Pool, observationCardinalityNext uint16) error {
 85	observationState := p.ObservationState()
 86
 87	if observationState == nil {
 88		return errors.New("observation state not initialized")
 89	}
 90
 91	if observationCardinalityNext > maxObservationCardinality {
 92		return errors.New("observation cardinality next exceeds maximum")
 93	}
 94
 95	if observationCardinalityNext <= observationState.CardinalityNext() {
 96		return errors.New("observation cardinality next must be greater than current")
 97	}
 98
 99	observationCardinalityNextNew, err := grow(observationState, observationState.Cardinality(), observationCardinalityNext)
100	if err != nil {
101		return err
102	}
103
104	observationState.SetCardinalityNext(observationCardinalityNextNew)
105
106	return nil
107}
108
109func transform(lastObservation *pl.Observation, currentTime int64, tick int32, liquidity *u256.Uint) (*pl.Observation, error) {
110	timeDelta := currentTime - lastObservation.BlockTimestamp()
111	if timeDelta < 0 {
112		return nil, errors.New("time delta must be greater than 0")
113	}
114
115	// calculate cumulative values
116	tickCumulative := lastObservation.TickCumulative() + int64(tick)*timeDelta
117
118	// calculate liquidity cumulative
119	liquidityDelta, overflow := u256.Zero().MulOverflow(liquidity, u256.NewUintFromInt64(timeDelta))
120	if overflow {
121		panic(errors.New(errOverflow))
122	}
123
124	prevLiqCum := u256.MustFromDecimal(lastObservation.LiquidityCumulative())
125	liquidityCumulative := u256.Zero().Add(prevLiqCum, liquidityDelta)
126
127	// calculate seconds per liquidity
128	liquidityForCalc := liquidity
129	if liquidity.IsZero() {
130		liquidityForCalc = u256.One()
131	}
132
133	// secondsPerLiquidity += timeDelta * 2^128 / max(1, liquidity)
134	secondsPerLiquidityDelta := u256.MulDiv(
135		u256.NewUintFromInt64(timeDelta),
136		consts.Q128(),
137		liquidityForCalc,
138	)
139
140	prevSecPerLiq := u256.MustFromDecimal(lastObservation.SecondsPerLiquidityCumulativeX128())
141	secondsPerLiquidityCumulativeX128 := u256.Zero().Add(
142		prevSecPerLiq,
143		secondsPerLiquidityDelta,
144	)
145
146	return pl.NewObservation(
147		currentTime,
148		tickCumulative,
149		liquidityCumulative.ToString(),
150		secondsPerLiquidityCumulativeX128.ToString(),
151		true,
152	), nil
153}
154
155func grow(os *pl.ObservationState, currentCardinality, nextCardinality uint16) (uint16, error) {
156	if currentCardinality <= 0 {
157		return currentCardinality, errors.New("currentCardinality must be greater than 0")
158	}
159
160	if nextCardinality <= currentCardinality {
161		return currentCardinality, nil
162	}
163
164	if nextCardinality > maxObservationCardinality {
165		return currentCardinality, errors.New("nextCardinality exceeds maximum")
166	}
167
168	// This is more efficient than checking all slots from 0
169	for i := currentCardinality; i < nextCardinality; i++ {
170		observation := pl.NewDefaultObservation()
171		observation.SetBlockTimestamp(1)
172		os.SetObservation(i, observation)
173	}
174
175	return nextCardinality, nil
176}
177
178func lte(time, a, b int64) bool {
179	if (a <= time) && (time <= b) {
180		return a <= b
181	}
182
183	aAdjusted := u256.NewUintFromInt64(a)
184	bAdjusted := u256.NewUintFromInt64(b)
185	timeUint256 := u256.NewUintFromInt64(time)
186
187	if aAdjusted.Gt(timeUint256) {
188		aAdjusted = aAdjusted.Add(aAdjusted, u256.NewUintFromInt64(1<<32))
189	}
190
191	if bAdjusted.Gt(timeUint256) {
192		bAdjusted = bAdjusted.Add(bAdjusted, u256.NewUintFromInt64(1<<32))
193	}
194
195	return aAdjusted.Lte(bAdjusted)
196}
197
198func writeObservation(
199	os *pl.ObservationState,
200	currentTime int64,
201	tick int32,
202	liquidity *u256.Uint,
203) error {
204	lastObservation, err := lastObservation(os)
205	if err != nil {
206		return err
207	}
208
209	if lastObservation.BlockTimestamp() == currentTime {
210		return nil
211	}
212
213	// Check if we need to grow the cardinality
214	if os.CardinalityNext() > os.Cardinality() && os.Index() == os.Cardinality()-1 {
215		os.SetCardinality(os.CardinalityNext())
216	}
217
218	nextIndex := (os.Index() + 1) % os.Cardinality()
219
220	// Ensure the slot exists before writing
221	if _, ok := os.Observations()[nextIndex]; !ok {
222		os.SetObservation(nextIndex, pl.NewDefaultObservation())
223	}
224
225	observation, err := transform(lastObservation, currentTime, tick, liquidity)
226	if err != nil {
227		return err
228	}
229
230	os.SetObservation(nextIndex, observation)
231	os.SetIndex(nextIndex)
232
233	return nil
234}
235
236func lastObservation(os *pl.ObservationState) (*pl.Observation, error) {
237	observation, ok := os.Observations()[os.Index()]
238	if !ok || observation == nil {
239		return nil, errors.New(errNotInitializedObservation)
240	}
241
242	return observation, nil
243}
244
245// observationAt returns the observation at a specific index
246// Returns error if the observation doesn't exist
247func observationAt(os *pl.ObservationState, index uint16) (*pl.Observation, error) {
248	obs, ok := os.Observations()[index]
249	if !ok || obs == nil {
250		return nil, errors.New(errNotInitializedObservation)
251	}
252
253	return obs, nil
254}
255
256// observeSingle returns the data for a single observation at a specific time ago
257func observeSingle(
258	os *pl.ObservationState,
259	currentTime int64,
260	secondsAgo uint32,
261	tick int32,
262	index uint16,
263	liquidity *u256.Uint,
264	cardinality uint16,
265) (int64, string, error) {
266	if secondsAgo == 0 {
267		// if secondsAgo is 0, return current values
268		last, err := observationAt(os, index)
269		if err != nil {
270			return 0, "", err
271		}
272
273		if last.BlockTimestamp() != currentTime {
274			// need to create virtual observation for current time
275			transformed, err := transform(last, currentTime, tick, liquidity)
276			if err != nil {
277				return 0, "", err
278			}
279
280			return transformed.TickCumulative(), transformed.SecondsPerLiquidityCumulativeX128(), nil
281		}
282
283		return last.TickCumulative(), last.SecondsPerLiquidityCumulativeX128(), nil
284	}
285
286	target := currentTime - int64(secondsAgo)
287
288	// find the observations before and after the target
289	beforeOrAt, atOrAfter, err := getSurroundingObservations(
290		os,
291		target,
292		currentTime,
293		tick,
294		index,
295		liquidity,
296		cardinality,
297	)
298	if err != nil {
299		return 0, "", err
300	}
301
302	if target == beforeOrAt.BlockTimestamp() {
303		return beforeOrAt.TickCumulative(), beforeOrAt.SecondsPerLiquidityCumulativeX128(), nil
304	}
305
306	if target == atOrAfter.BlockTimestamp() {
307		return atOrAfter.TickCumulative(), atOrAfter.SecondsPerLiquidityCumulativeX128(), nil
308	}
309
310	// interpolate between the two observations
311	observationTimeDelta := atOrAfter.BlockTimestamp() - beforeOrAt.BlockTimestamp()
312	targetDelta := target - beforeOrAt.BlockTimestamp()
313
314	// tickCumulative += (tickCumulativeAfter - tickCumulativeBefore) / observationTimeDelta * targetDelta
315	tickCumulative := beforeOrAt.TickCumulative() +
316		((atOrAfter.TickCumulative()-beforeOrAt.TickCumulative())/observationTimeDelta)*targetDelta
317
318	beforeSecPerLiq := u256.MustFromDecimal(beforeOrAt.SecondsPerLiquidityCumulativeX128())
319	afterSecPerLiq := u256.MustFromDecimal(atOrAfter.SecondsPerLiquidityCumulativeX128())
320
321	// for secondsPerLiquidity, need to interpolate carefully
322	secondsPerLiquidityDelta := u256.Zero().Sub(afterSecPerLiq, beforeSecPerLiq)
323
324	secondsPerLiquidity := u256.Zero().Add(
325		beforeSecPerLiq,
326		u256.MulDiv(
327			secondsPerLiquidityDelta,
328			u256.NewUintFromInt64(targetDelta),
329			u256.NewUintFromInt64(observationTimeDelta),
330		),
331	)
332
333	return tickCumulative, secondsPerLiquidity.ToString(), nil
334}
335
336// getSurroundingObservations finds the observations immediately before and after the target timestamp.
337// It uses binary search over the logical time-ordered view of the circular buffer.
338// Logical order starts at (index+1) % cardinality (oldest) and ends at index (latest).
339func getSurroundingObservations(
340	os *pl.ObservationState,
341	target int64,
342	currentTime int64,
343	tick int32,
344	index uint16,
345	liquidity *u256.Uint,
346	cardinality uint16,
347) (*pl.Observation, *pl.Observation, error) {
348	// Optimistically set before to the newest observation
349	beforeOrAt, err := observationAt(os, index)
350	if err != nil {
351		return nil, nil, err
352	}
353
354	// If the target is chronologically at or after the newest observation, we can early return
355	if lte(currentTime, beforeOrAt.BlockTimestamp(), target) {
356		if beforeOrAt.BlockTimestamp() == target {
357			// If newest observation equals target, we're in the same block, so we can ignore atOrAfter
358			return beforeOrAt, nil, nil
359		}
360		// Otherwise, we need to transform
361		atOrAfter, err := transform(beforeOrAt, target, tick, liquidity)
362		if err != nil {
363			return nil, nil, err
364		}
365		return beforeOrAt, atOrAfter, nil
366	}
367
368	// Now, set before to the oldest observation
369	start := (index + 1) % cardinality
370	beforeOrAt, err = observationAt(os, start)
371	if err != nil || !beforeOrAt.Initialized() {
372		beforeOrAt, err = observationAt(os, 0)
373		if err != nil {
374			return nil, nil, err
375		}
376	}
377
378	// Ensure that the target is chronologically at or after the oldest observation
379	if !lte(currentTime, beforeOrAt.BlockTimestamp(), target) {
380		return nil, nil, errors.New(errObservationTooOld)
381	}
382
383	// If we've reached this point, we have to binary search
384	return binarySearch(os, currentTime, target, index, cardinality)
385}
386
387func binarySearch(
388	os *pl.ObservationState,
389	currentTime int64,
390	target int64,
391	index uint16,
392	cardinality uint16,
393) (*pl.Observation, *pl.Observation, error) {
394	l := uint64((index + 1) % cardinality) // oldest observation
395	r := l + uint64(cardinality) - 1       // newest observation
396	var i uint64
397	var beforeOrAt, atOrAfter *pl.Observation
398	var err error
399
400	for {
401		i = (l + r) / 2
402
403		beforeIndex := uint16(i % uint64(cardinality))
404		beforeOrAt, err = observationAt(os, beforeIndex)
405		if err != nil || !beforeOrAt.Initialized() {
406			// we've landed on an uninitialized tick, keep searching higher (more recently)
407			l = i + 1
408			continue
409		}
410
411		afterIndex := uint16((i + 1) % uint64(cardinality))
412		atOrAfter, err = observationAt(os, afterIndex)
413		if err != nil {
414			return nil, nil, err
415		}
416
417		targetAtOrAfter := lte(currentTime, beforeOrAt.BlockTimestamp(), target)
418
419		// check if we've found the answer!
420		if targetAtOrAfter && lte(currentTime, target, atOrAfter.BlockTimestamp()) {
421			break
422		}
423
424		if !targetAtOrAfter {
425			r = i - 1
426		} else {
427			l = i + 1
428		}
429	}
430
431	return beforeOrAt, atOrAfter, nil
432}
433
434// observe returns the cumulative tick and liquidity as of each timestamp secondsAgo from the current time.
435func observe(
436	os *pl.ObservationState,
437	currentTime int64,
438	secondsAgos []uint32,
439	tick int32,
440	index uint16,
441	liquidity *u256.Uint,
442	cardinality uint16,
443) ([]int64, []string, error) {
444	if cardinality <= 0 {
445		return nil, nil, errors.New("observation cardinality must be greater than 0")
446	}
447
448	historyCount := len(secondsAgos)
449	tickCumulatives := make([]int64, historyCount)
450	secondsPerLiquidityCumulativeX128s := make([]string, historyCount)
451
452	for i, secondsAgo := range secondsAgos {
453		tickCumulative, secondsPerLiquidity, err := observeSingle(
454			os,
455			currentTime,
456			secondsAgo,
457			tick,
458			index,
459			liquidity,
460			cardinality,
461		)
462		if err != nil {
463			return nil, nil, err
464		}
465
466		tickCumulatives[i] = tickCumulative
467		secondsPerLiquidityCumulativeX128s[i] = secondsPerLiquidity
468	}
469
470	return tickCumulatives, secondsPerLiquidityCumulativeX128s, nil
471}