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