oracle.gno
12.25 Kb · 445 lines
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 seconds per liquidity
119 liquidityForCalc := liquidity
120 if liquidity.IsZero() {
121 liquidityForCalc = u256.One()
122 }
123
124 // secondsPerLiquidity += timeDelta * 2^128 / max(1, liquidity)
125 secondsPerLiquidityDelta := u256.MulDiv(
126 u256.NewUintFromInt64(timeDelta),
127 consts.Q128(),
128 liquidityForCalc,
129 )
130
131 prevSecPerLiq := u256.MustFromDecimal(lastObservation.SecondsPerLiquidityCumulativeX128())
132 secondsPerLiquidityCumulativeX128 := u256.Zero().Add(
133 prevSecPerLiq,
134 secondsPerLiquidityDelta,
135 )
136
137 return pl.NewObservation(
138 currentTime,
139 tickCumulative,
140 secondsPerLiquidityCumulativeX128.ToString(),
141 true,
142 ), nil
143}
144
145func grow(os *pl.ObservationState, currentCardinality, nextCardinality uint16) (uint16, error) {
146 if currentCardinality <= 0 {
147 return currentCardinality, errors.New("currentCardinality must be greater than 0")
148 }
149
150 if nextCardinality <= currentCardinality {
151 return currentCardinality, nil
152 }
153
154 if nextCardinality > maxObservationCardinality {
155 return currentCardinality, errors.New("nextCardinality exceeds maximum")
156 }
157
158 // This is more efficient than checking all slots from 0
159 for i := currentCardinality; i < nextCardinality; i++ {
160 observation := pl.NewDefaultObservation()
161 observation.SetBlockTimestamp(1)
162 os.SetObservation(i, observation)
163 }
164
165 return nextCardinality, nil
166}
167
168func writeObservation(
169 os *pl.ObservationState,
170 currentTime int64,
171 tick int32,
172 liquidity *u256.Uint,
173) error {
174 lastObservation, err := lastObservation(os)
175 if err != nil {
176 return err
177 }
178
179 if lastObservation.BlockTimestamp() == currentTime {
180 return nil
181 }
182
183 // Check if we need to grow the cardinality
184 if os.CardinalityNext() > os.Cardinality() && os.Index() == os.Cardinality()-1 {
185 os.SetCardinality(os.CardinalityNext())
186 }
187
188 nextIndex := (os.Index() + 1) % os.Cardinality()
189
190 // Ensure the slot exists before writing
191 if _, ok := os.Observations()[nextIndex]; !ok {
192 os.SetObservation(nextIndex, pl.NewDefaultObservation())
193 }
194
195 observation, err := transform(lastObservation, currentTime, tick, liquidity)
196 if err != nil {
197 return err
198 }
199
200 os.SetObservation(nextIndex, observation)
201 os.SetIndex(nextIndex)
202
203 return nil
204}
205
206func lastObservation(os *pl.ObservationState) (*pl.Observation, error) {
207 observation, ok := os.Observations()[os.Index()]
208 if !ok || observation == nil {
209 return nil, errors.New(errNotInitializedObservation)
210 }
211
212 return observation, nil
213}
214
215// observationAt returns the observation at a specific index
216// Returns error if the observation doesn't exist
217func observationAt(os *pl.ObservationState, index uint16) (*pl.Observation, error) {
218 obs, ok := os.Observations()[index]
219 if !ok || obs == nil {
220 return nil, errors.New(errNotInitializedObservation)
221 }
222
223 return obs, nil
224}
225
226// observeSingle returns the data for a single observation at a specific time ago
227func observeSingle(
228 os *pl.ObservationState,
229 currentTime int64,
230 secondsAgo uint32,
231 tick int32,
232 index uint16,
233 liquidity *u256.Uint,
234 cardinality uint16,
235) (int64, string, error) {
236 if secondsAgo == 0 {
237 // if secondsAgo is 0, return current values
238 last, err := observationAt(os, index)
239 if err != nil {
240 return 0, "", err
241 }
242
243 if last.BlockTimestamp() != currentTime {
244 // need to create virtual observation for current time
245 transformed, err := transform(last, currentTime, tick, liquidity)
246 if err != nil {
247 return 0, "", err
248 }
249
250 return transformed.TickCumulative(), transformed.SecondsPerLiquidityCumulativeX128(), nil
251 }
252
253 return last.TickCumulative(), last.SecondsPerLiquidityCumulativeX128(), nil
254 }
255
256 // A lookback longer than the chain's own age would place the target before unix epoch.
257 if int64(secondsAgo) > currentTime {
258 return 0, "", errors.New(errObservationBeforeEpoch)
259 }
260
261 target := currentTime - int64(secondsAgo)
262
263 // find the observations before and after the target
264 beforeOrAt, atOrAfter, err := getSurroundingObservations(
265 os,
266 target,
267 tick,
268 index,
269 liquidity,
270 cardinality,
271 )
272 if err != nil {
273 return 0, "", err
274 }
275
276 if target == beforeOrAt.BlockTimestamp() {
277 return beforeOrAt.TickCumulative(), beforeOrAt.SecondsPerLiquidityCumulativeX128(), nil
278 }
279
280 if target == atOrAfter.BlockTimestamp() {
281 return atOrAfter.TickCumulative(), atOrAfter.SecondsPerLiquidityCumulativeX128(), nil
282 }
283
284 // interpolate between the two observations
285 observationTimeDelta := atOrAfter.BlockTimestamp() - beforeOrAt.BlockTimestamp()
286 targetDelta := target - beforeOrAt.BlockTimestamp()
287
288 // tickCumulative += (tickCumulativeAfter - tickCumulativeBefore) / observationTimeDelta * targetDelta
289 tickCumulative := beforeOrAt.TickCumulative() +
290 ((atOrAfter.TickCumulative()-beforeOrAt.TickCumulative())/observationTimeDelta)*targetDelta
291
292 beforeSecPerLiq := u256.MustFromDecimal(beforeOrAt.SecondsPerLiquidityCumulativeX128())
293 afterSecPerLiq := u256.MustFromDecimal(atOrAfter.SecondsPerLiquidityCumulativeX128())
294
295 // for secondsPerLiquidity, need to interpolate carefully
296 secondsPerLiquidityDelta := u256.Zero().Sub(afterSecPerLiq, beforeSecPerLiq)
297
298 secondsPerLiquidity := u256.Zero().Add(
299 beforeSecPerLiq,
300 u256.MulDiv(
301 secondsPerLiquidityDelta,
302 u256.NewUintFromInt64(targetDelta),
303 u256.NewUintFromInt64(observationTimeDelta),
304 ),
305 )
306
307 return tickCumulative, secondsPerLiquidity.ToString(), nil
308}
309
310// getSurroundingObservations finds the observations immediately before and after the target timestamp.
311// It uses binary search over the logical time-ordered view of the circular buffer.
312// Logical order starts at (index+1) % cardinality (oldest) and ends at index (latest).
313func getSurroundingObservations(
314 os *pl.ObservationState,
315 target int64,
316 tick int32,
317 index uint16,
318 liquidity *u256.Uint,
319 cardinality uint16,
320) (*pl.Observation, *pl.Observation, error) {
321 // Optimistically set before to the newest observation
322 beforeOrAt, err := observationAt(os, index)
323 if err != nil {
324 return nil, nil, err
325 }
326
327 // Timestamps are int64, so natural ordering applies. Uniswap V3 needs a
328 // wraparound-aware comparison here only because it stores them as uint32.
329 // If the target is chronologically at or after the newest observation, we can early return
330 if beforeOrAt.BlockTimestamp() <= target {
331 if beforeOrAt.BlockTimestamp() == target {
332 // If newest observation equals target, we're in the same block, so we can ignore atOrAfter
333 return beforeOrAt, nil, nil
334 }
335 // Otherwise, we need to transform
336 atOrAfter, err := transform(beforeOrAt, target, tick, liquidity)
337 if err != nil {
338 return nil, nil, err
339 }
340 return beforeOrAt, atOrAfter, nil
341 }
342
343 // Now, set before to the oldest observation
344 start := (index + 1) % cardinality
345 beforeOrAt, err = observationAt(os, start)
346 if err != nil || !beforeOrAt.Initialized() {
347 beforeOrAt, err = observationAt(os, 0)
348 if err != nil {
349 return nil, nil, err
350 }
351 }
352
353 // Ensure that the target is chronologically at or after the oldest observation
354 if beforeOrAt.BlockTimestamp() > target {
355 return nil, nil, errors.New(errObservationTooOld)
356 }
357
358 // If we've reached this point, we have to binary search
359 return binarySearch(os, target, index, cardinality)
360}
361
362func binarySearch(
363 os *pl.ObservationState,
364 target int64,
365 index uint16,
366 cardinality uint16,
367) (*pl.Observation, *pl.Observation, error) {
368 l := uint64((index + 1) % cardinality) // oldest observation
369 r := l + uint64(cardinality) - 1 // newest observation
370 var i uint64
371 var beforeOrAt, atOrAfter *pl.Observation
372 var err error
373
374 for {
375 i = (l + r) / 2
376
377 beforeIndex := uint16(i % uint64(cardinality))
378 beforeOrAt, err = observationAt(os, beforeIndex)
379 if err != nil || !beforeOrAt.Initialized() {
380 // we've landed on an uninitialized tick, keep searching higher (more recently)
381 l = i + 1
382 continue
383 }
384
385 afterIndex := uint16((i + 1) % uint64(cardinality))
386 atOrAfter, err = observationAt(os, afterIndex)
387 if err != nil {
388 return nil, nil, err
389 }
390
391 targetAtOrAfter := beforeOrAt.BlockTimestamp() <= target
392
393 // check if we've found the answer!
394 if targetAtOrAfter && target <= atOrAfter.BlockTimestamp() {
395 break
396 }
397
398 if !targetAtOrAfter {
399 r = i - 1
400 } else {
401 l = i + 1
402 }
403 }
404
405 return beforeOrAt, atOrAfter, nil
406}
407
408// observe returns the cumulative tick and liquidity as of each timestamp secondsAgo from the current time.
409func observe(
410 os *pl.ObservationState,
411 currentTime int64,
412 secondsAgos []uint32,
413 tick int32,
414 index uint16,
415 liquidity *u256.Uint,
416 cardinality uint16,
417) ([]int64, []string, error) {
418 if cardinality <= 0 {
419 return nil, nil, errors.New("observation cardinality must be greater than 0")
420 }
421
422 historyCount := len(secondsAgos)
423 tickCumulatives := make([]int64, historyCount)
424 secondsPerLiquidityCumulativeX128s := make([]string, historyCount)
425
426 for i, secondsAgo := range secondsAgos {
427 tickCumulative, secondsPerLiquidity, err := observeSingle(
428 os,
429 currentTime,
430 secondsAgo,
431 tick,
432 index,
433 liquidity,
434 cardinality,
435 )
436 if err != nil {
437 return nil, nil, err
438 }
439
440 tickCumulatives[i] = tickCumulative
441 secondsPerLiquidityCumulativeX128s[i] = secondsPerLiquidity
442 }
443
444 return tickCumulatives, secondsPerLiquidityCumulativeX128s, nil
445}
