oracle.gno
12.70 Kb ยท 471 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 secondsPerLiquidityCumulativeX128s[1],
47 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 liquidityCumulative := u256.Zero().Add(lastObservation.LiquidityCumulative(), 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 q128FromDecimal,
137 liquidityForCalc,
138 )
139
140 secondsPerLiquidityCumulativeX128 := lastObservation.SecondsPerLiquidityCumulativeX128().Clone()
141 secondsPerLiquidityCumulativeX128 = u256.Zero().Add(
142 secondsPerLiquidityCumulativeX128,
143 secondsPerLiquidityDelta,
144 )
145
146 return pl.NewObservation(
147 currentTime,
148 tickCumulative,
149 liquidityCumulative,
150 secondsPerLiquidityCumulativeX128,
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.Observations()[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.Observations()[nextIndex] = pl.NewDefaultObservation()
223 }
224
225 observation, err := transform(lastObservation, currentTime, tick, liquidity)
226 if err != nil {
227 return err
228 }
229
230 os.Observations()[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, 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, 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, *u256.Uint, 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, nil, 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, nil, 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, nil, 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 // for secondsPerLiquidity, need to interpolate carefully
319 secondsPerLiquidityDelta := u256.Zero().Sub(
320 atOrAfter.SecondsPerLiquidityCumulativeX128(),
321 beforeOrAt.SecondsPerLiquidityCumulativeX128(),
322 )
323
324 secondsPerLiquidity := u256.Zero().Add(
325 beforeOrAt.SecondsPerLiquidityCumulativeX128(),
326 u256.MulDiv(
327 secondsPerLiquidityDelta,
328 u256.NewUintFromInt64(targetDelta),
329 u256.NewUintFromInt64(observationTimeDelta),
330 ),
331 )
332
333 return tickCumulative, secondsPerLiquidity, 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, 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, []*u256.Uint, 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([]*u256.Uint, 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}
