-
Notifications
You must be signed in to change notification settings - Fork 9
/
TwabLib.sol
748 lines (682 loc) · 29.1 KB
/
TwabLib.sol
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;
import "ring-buffer-lib/RingBufferLib.sol";
import { ObservationLib, MAX_CARDINALITY } from "./ObservationLib.sol";
type PeriodOffsetRelativeTimestamp is uint32;
/// @notice Emitted when a balance is decreased by an amount that exceeds the amount available.
/// @param balance The current balance of the account
/// @param amount The amount being decreased from the account's balance
/// @param message An additional message describing the error
error BalanceLTAmount(uint96 balance, uint96 amount, string message);
/// @notice Emitted when a delegate balance is decreased by an amount that exceeds the amount available.
/// @param delegateBalance The current delegate balance of the account
/// @param delegateAmount The amount being decreased from the account's delegate balance
/// @param message An additional message describing the error
error DelegateBalanceLTAmount(uint96 delegateBalance, uint96 delegateAmount, string message);
/// @notice Emitted when a request is made for a twab that is not yet finalized.
/// @param timestamp The requested timestamp
/// @param currentOverwritePeriodStartedAt The current overwrite period start time
error TimestampNotFinalized(uint256 timestamp, uint256 currentOverwritePeriodStartedAt);
/// @notice Emitted when a TWAB time range start is after the end.
/// @param start The start time
/// @param end The end time
error InvalidTimeRange(uint256 start, uint256 end);
/// @notice Emitted when there is insufficient history to lookup a twab time range
/// @param requestedTimestamp The timestamp requested
/// @param oldestTimestamp The oldest timestamp that can be read
error InsufficientHistory(
PeriodOffsetRelativeTimestamp requestedTimestamp,
PeriodOffsetRelativeTimestamp oldestTimestamp
);
/**
* @title PoolTogether V5 TwabLib (Library)
* @author PoolTogether Inc. & G9 Software Inc.
* @dev Time-Weighted Average Balance Library for ERC20 tokens.
* @notice This TwabLib adds on-chain historical lookups to a user(s) time-weighted average balance.
* Each user is mapped to an Account struct containing the TWAB history (ring buffer) and
* ring buffer parameters. Every token.transfer() creates a new TWAB checkpoint. The new
* TWAB checkpoint is stored in the circular ring buffer, as either a new checkpoint or
* rewriting a previous checkpoint with new parameters. One checkpoint per day is stored.
* The TwabLib guarantees minimum 1 year of search history.
* @notice There are limitations to the Observation data structure used. Ensure your token is
* compatible before using this library. Ensure the date ranges you're relying on are
* within safe boundaries.
*/
library TwabLib {
/**
* @notice Struct ring buffer parameters for single user Account.
* @param balance Current token balance for an Account
* @param delegateBalance Current delegate balance for an Account (active balance for chance)
* @param nextObservationIndex Next uninitialized or updatable ring buffer checkpoint storage slot
* @param cardinality Current total "initialized" ring buffer checkpoints for single user Account.
* Used to set initial boundary conditions for an efficient binary search.
*/
struct AccountDetails {
uint96 balance;
uint96 delegateBalance;
uint16 nextObservationIndex;
uint16 cardinality;
}
/**
* @notice Account details and historical twabs.
* @dev The size of observations is MAX_CARDINALITY from the ObservationLib.
* @param details The account details
* @param observations The history of observations for this account
*/
struct Account {
AccountDetails details;
ObservationLib.Observation[17520] observations;
}
/**
* @notice Increase a user's balance and delegate balance by a given amount.
* @dev This function mutates the provided account.
* @param PERIOD_LENGTH The length of an overwrite period
* @param PERIOD_OFFSET The offset of the first period
* @param _account The account to update
* @param _amount The amount to increase the balance by
* @param _delegateAmount The amount to increase the delegate balance by
* @return observation The new/updated observation
* @return isNew Whether or not the observation is new or overwrote a previous one
* @return isObservationRecorded Whether or not an observation was recorded to storage
*/
function increaseBalances(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
Account storage _account,
uint96 _amount,
uint96 _delegateAmount
)
internal
returns (
ObservationLib.Observation memory observation,
bool isNew,
bool isObservationRecorded,
AccountDetails memory accountDetails
)
{
accountDetails = _account.details;
// record a new observation if the delegateAmount is non-zero and time has not overflowed.
isObservationRecorded =
_delegateAmount != uint96(0) &&
block.timestamp <= lastObservationAt(PERIOD_LENGTH, PERIOD_OFFSET);
accountDetails.balance += _amount;
accountDetails.delegateBalance += _delegateAmount;
// Only record a new Observation if the users delegateBalance has changed.
if (isObservationRecorded) {
(observation, isNew, accountDetails) = _recordObservation(
PERIOD_LENGTH,
PERIOD_OFFSET,
accountDetails,
_account
);
}
_account.details = accountDetails;
}
/**
* @notice Decrease a user's balance and delegate balance by a given amount.
* @dev This function mutates the provided account.
* @param PERIOD_LENGTH The length of an overwrite period
* @param PERIOD_OFFSET The offset of the first period
* @param _account The account to update
* @param _amount The amount to decrease the balance by
* @param _delegateAmount The amount to decrease the delegate balance by
* @param _revertMessage The revert message to use if the balance is insufficient
* @return observation The new/updated observation
* @return isNew Whether or not the observation is new or overwrote a previous one
* @return isObservationRecorded Whether or not the observation was recorded to storage
*/
function decreaseBalances(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
Account storage _account,
uint96 _amount,
uint96 _delegateAmount,
string memory _revertMessage
)
internal
returns (
ObservationLib.Observation memory observation,
bool isNew,
bool isObservationRecorded,
AccountDetails memory accountDetails
)
{
accountDetails = _account.details;
if (accountDetails.balance < _amount) {
revert BalanceLTAmount(accountDetails.balance, _amount, _revertMessage);
}
if (accountDetails.delegateBalance < _delegateAmount) {
revert DelegateBalanceLTAmount(
accountDetails.delegateBalance,
_delegateAmount,
_revertMessage
);
}
// record a new observation if the delegateAmount is non-zero and time has not overflowed.
isObservationRecorded =
_delegateAmount != uint96(0) &&
block.timestamp <= lastObservationAt(PERIOD_LENGTH, PERIOD_OFFSET);
unchecked {
accountDetails.balance -= _amount;
accountDetails.delegateBalance -= _delegateAmount;
}
// Only record a new Observation if the users delegateBalance has changed.
if (isObservationRecorded) {
(observation, isNew, accountDetails) = _recordObservation(
PERIOD_LENGTH,
PERIOD_OFFSET,
accountDetails,
_account
);
}
_account.details = accountDetails;
}
/**
* @notice Looks up the oldest observation in the circular buffer.
* @param _observations The circular buffer of observations
* @param _accountDetails The account details to query with
* @return index The index of the oldest observation
* @return observation The oldest observation in the circular buffer
*/
function getOldestObservation(
ObservationLib.Observation[MAX_CARDINALITY] storage _observations,
AccountDetails memory _accountDetails
) internal view returns (uint16 index, ObservationLib.Observation memory observation) {
// If the circular buffer has not been fully populated, we go to the beginning of the buffer at index 0.
if (_accountDetails.cardinality < MAX_CARDINALITY) {
index = 0;
observation = _observations[0];
} else {
index = _accountDetails.nextObservationIndex;
observation = _observations[index];
}
}
/**
* @notice Looks up the newest observation in the circular buffer.
* @param _observations The circular buffer of observations
* @param _accountDetails The account details to query with
* @return index The index of the newest observation
* @return observation The newest observation in the circular buffer
*/
function getNewestObservation(
ObservationLib.Observation[MAX_CARDINALITY] storage _observations,
AccountDetails memory _accountDetails
) internal view returns (uint16 index, ObservationLib.Observation memory observation) {
index = uint16(
RingBufferLib.newestIndex(_accountDetails.nextObservationIndex, MAX_CARDINALITY)
);
observation = _observations[index];
}
/**
* @notice Looks up a users balance at a specific time in the past. The time must be before the current overwrite period.
* @dev Ensure timestamps are safe using requireFinalized
* @param PERIOD_LENGTH The length of an overwrite period
* @param PERIOD_OFFSET The offset of the first period
* @param _observations The circular buffer of observations
* @param _accountDetails The account details to query with
* @param _targetTime The time to look up the balance at
* @return balance The balance at the target time
*/
function getBalanceAt(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
ObservationLib.Observation[MAX_CARDINALITY] storage _observations,
AccountDetails memory _accountDetails,
uint256 _targetTime
) internal view requireFinalized(PERIOD_LENGTH, PERIOD_OFFSET, _targetTime) returns (uint256) {
if (_targetTime < PERIOD_OFFSET) {
return 0;
}
// if this is for an overflowed time period, return 0
if (isShutdownAt(_targetTime, PERIOD_LENGTH, PERIOD_OFFSET)) {
return 0;
}
ObservationLib.Observation memory prevOrAtObservation = _getPreviousOrAtObservation(
_observations,
_accountDetails,
PeriodOffsetRelativeTimestamp.wrap(uint32(_targetTime - PERIOD_OFFSET))
);
return prevOrAtObservation.balance;
}
/**
* @notice Returns whether the TwabController has been shutdown at the given timestamp
* If the twab is queried at or after this time, whether an absolute timestamp or time range, it will return 0.
* @param timestamp The timestamp to check
* @param PERIOD_OFFSET The offset of the first period
* @return True if the TwabController is shutdown at the given timestamp, false otherwise.
*/
function isShutdownAt(
uint256 timestamp,
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET
) internal pure returns (bool) {
return timestamp > lastObservationAt(PERIOD_LENGTH, PERIOD_OFFSET);
}
/**
* @notice Computes the largest timestamp at which the TwabController can record a new observation.
* @param PERIOD_OFFSET The offset of the first period
* @return The largest timestamp at which the TwabController can record a new observation.
*/
function lastObservationAt(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET
) internal pure returns (uint256) {
return uint256(PERIOD_OFFSET) + (type(uint32).max / PERIOD_LENGTH) * PERIOD_LENGTH;
}
/**
* @notice Looks up a users TWAB for a time range. The time must be before the current overwrite period.
* @dev If the timestamps in the range are not exact matches of observations, the balance is extrapolated using the previous observation.
* @param PERIOD_LENGTH The length of an overwrite period
* @param PERIOD_OFFSET The offset of the first period
* @param _observations The circular buffer of observations
* @param _accountDetails The account details to query with
* @param _startTime The start of the time range
* @param _endTime The end of the time range
* @return twab The TWAB for the time range
*/
function getTwabBetween(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
ObservationLib.Observation[MAX_CARDINALITY] storage _observations,
AccountDetails memory _accountDetails,
uint256 _startTime,
uint256 _endTime
) internal view requireFinalized(PERIOD_LENGTH, PERIOD_OFFSET, _endTime) returns (uint256) {
if (_endTime < _startTime) {
revert InvalidTimeRange(_startTime, _endTime);
}
// if the range extends into the shutdown period, return 0
if (isShutdownAt(_endTime, PERIOD_LENGTH, PERIOD_OFFSET)) {
return 0;
}
uint256 offsetStartTime = _startTime - PERIOD_OFFSET;
uint256 offsetEndTime = _endTime - PERIOD_OFFSET;
ObservationLib.Observation memory endObservation = _getPreviousOrAtObservation(
_observations,
_accountDetails,
PeriodOffsetRelativeTimestamp.wrap(uint32(offsetEndTime))
);
if (offsetStartTime == offsetEndTime) {
return endObservation.balance;
}
ObservationLib.Observation memory startObservation = _getPreviousOrAtObservation(
_observations,
_accountDetails,
PeriodOffsetRelativeTimestamp.wrap(uint32(offsetStartTime))
);
if (startObservation.timestamp != offsetStartTime) {
startObservation = _calculateTemporaryObservation(
startObservation,
PeriodOffsetRelativeTimestamp.wrap(uint32(offsetStartTime))
);
}
if (endObservation.timestamp != offsetEndTime) {
endObservation = _calculateTemporaryObservation(
endObservation,
PeriodOffsetRelativeTimestamp.wrap(uint32(offsetEndTime))
);
}
// Difference in amount / time
return
(endObservation.cumulativeBalance - startObservation.cumulativeBalance) /
(offsetEndTime - offsetStartTime);
}
/**
* @notice Given an AccountDetails with updated balances, either updates the latest Observation or records a new one
* @param PERIOD_LENGTH The overwrite period length
* @param PERIOD_OFFSET The overwrite period offset
* @param _accountDetails The updated account details
* @param _account The account to update
* @return observation The new/updated observation
* @return isNew Whether or not the observation is new or overwrote a previous one
* @return newAccountDetails The new account details
*/
function _recordObservation(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
AccountDetails memory _accountDetails,
Account storage _account
)
internal
returns (
ObservationLib.Observation memory observation,
bool isNew,
AccountDetails memory newAccountDetails
)
{
PeriodOffsetRelativeTimestamp currentTime = PeriodOffsetRelativeTimestamp.wrap(
uint32(block.timestamp - PERIOD_OFFSET)
);
uint16 nextIndex;
ObservationLib.Observation memory newestObservation;
(nextIndex, newestObservation, isNew) = _getNextObservationIndex(
PERIOD_LENGTH,
PERIOD_OFFSET,
_account.observations,
_accountDetails
);
if (isNew) {
// If the index is new, then we increase the next index to use
_accountDetails.nextObservationIndex = uint16(
RingBufferLib.nextIndex(uint256(nextIndex), MAX_CARDINALITY)
);
// Prevent the Account specific cardinality from exceeding the MAX_CARDINALITY.
// The ring buffer length is limited by MAX_CARDINALITY. IF the account.cardinality
// exceeds the max cardinality, new observations would be incorrectly set or the
// observation would be out of "bounds" of the ring buffer. Once reached the
// Account.cardinality will continue to be equal to max cardinality.
_accountDetails.cardinality = _accountDetails.cardinality < MAX_CARDINALITY
? _accountDetails.cardinality + 1
: MAX_CARDINALITY;
}
observation = ObservationLib.Observation({
cumulativeBalance: _extrapolateFromBalance(newestObservation, currentTime),
balance: _accountDetails.delegateBalance,
timestamp: PeriodOffsetRelativeTimestamp.unwrap(currentTime)
});
// Write to storage
_account.observations[nextIndex] = observation;
newAccountDetails = _accountDetails;
}
/**
* @notice Calculates a temporary observation for a given time using the previous observation.
* @dev This is used to extrapolate a balance for any given time.
* @param _observation The previous observation
* @param _time The time to extrapolate to
*/
function _calculateTemporaryObservation(
ObservationLib.Observation memory _observation,
PeriodOffsetRelativeTimestamp _time
) private pure returns (ObservationLib.Observation memory) {
return
ObservationLib.Observation({
cumulativeBalance: _extrapolateFromBalance(_observation, _time),
balance: _observation.balance,
timestamp: PeriodOffsetRelativeTimestamp.unwrap(_time)
});
}
/**
* @notice Looks up the next observation index to write to in the circular buffer.
* @dev If the current time is in the same period as the newest observation, we overwrite it.
* @dev If the current time is in a new period, we increment the index and write a new observation.
* @param PERIOD_LENGTH The length of an overwrite period
* @param PERIOD_OFFSET The offset of the first period
* @param _observations The circular buffer of observations
* @param _accountDetails The account details to query with
* @return index The index of the next observation slot to overwrite
* @return newestObservation The newest observation in the circular buffer
* @return isNew True if the observation slot is new, false if we're overwriting
*/
function _getNextObservationIndex(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
ObservationLib.Observation[MAX_CARDINALITY] storage _observations,
AccountDetails memory _accountDetails
)
private
view
returns (uint16 index, ObservationLib.Observation memory newestObservation, bool isNew)
{
uint16 newestIndex;
(newestIndex, newestObservation) = getNewestObservation(_observations, _accountDetails);
uint256 currentPeriod = getTimestampPeriod(PERIOD_LENGTH, PERIOD_OFFSET, block.timestamp);
uint256 newestObservationPeriod = getTimestampPeriod(
PERIOD_LENGTH,
PERIOD_OFFSET,
PERIOD_OFFSET + uint256(newestObservation.timestamp)
);
// Create a new Observation if it's the first period or the current time falls within a new period
if (_accountDetails.cardinality == 0 || currentPeriod > newestObservationPeriod) {
return (_accountDetails.nextObservationIndex, newestObservation, true);
}
// Otherwise, we're overwriting the current newest Observation
return (newestIndex, newestObservation, false);
}
/**
* @notice Computes the start time of the current overwrite period
* @param PERIOD_LENGTH The length of an overwrite period
* @param PERIOD_OFFSET The offset of the first period
* @return The start time of the current overwrite period
*/
function _currentOverwritePeriodStartedAt(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET
) private view returns (uint256) {
uint256 period = getTimestampPeriod(PERIOD_LENGTH, PERIOD_OFFSET, block.timestamp);
return getPeriodStartTime(PERIOD_LENGTH, PERIOD_OFFSET, period);
}
/**
* @notice Calculates the next cumulative balance using a provided Observation and timestamp.
* @param _observation The observation to extrapolate from
* @param _offsetTimestamp The timestamp to extrapolate to
* @return cumulativeBalance The cumulative balance at the timestamp
*/
function _extrapolateFromBalance(
ObservationLib.Observation memory _observation,
PeriodOffsetRelativeTimestamp _offsetTimestamp
) private pure returns (uint128) {
// new cumulative balance = provided cumulative balance (or zero) + (current balance * elapsed seconds)
unchecked {
return
uint128(
uint256(_observation.cumulativeBalance) +
uint256(_observation.balance) *
(PeriodOffsetRelativeTimestamp.unwrap(_offsetTimestamp) - _observation.timestamp)
);
}
}
/**
* @notice Computes the overwrite period start time given the current time
* @param PERIOD_LENGTH The length of an overwrite period
* @param PERIOD_OFFSET The offset of the first period
* @return The start time for the current overwrite period.
*/
function currentOverwritePeriodStartedAt(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET
) internal view returns (uint256) {
return _currentOverwritePeriodStartedAt(PERIOD_LENGTH, PERIOD_OFFSET);
}
/**
* @notice Calculates the period a timestamp falls within.
* @dev Timestamp prior to the PERIOD_OFFSET are considered to be in period 0.
* @param PERIOD_LENGTH The length of an overwrite period
* @param PERIOD_OFFSET The offset of the first period
* @param _timestamp The timestamp to calculate the period for
* @return period The period
*/
function getTimestampPeriod(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
uint256 _timestamp
) internal pure returns (uint256) {
if (_timestamp <= PERIOD_OFFSET) {
return 0;
}
return (_timestamp - PERIOD_OFFSET) / uint256(PERIOD_LENGTH);
}
/**
* @notice Calculates the start timestamp for a period
* @param PERIOD_LENGTH The period length to use to calculate the period
* @param PERIOD_OFFSET The period offset to use to calculate the period
* @param _period The period to check
* @return _timestamp The timestamp at which the period starts
*/
function getPeriodStartTime(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
uint256 _period
) internal pure returns (uint256) {
return _period * PERIOD_LENGTH + PERIOD_OFFSET;
}
/**
* @notice Calculates the last timestamp for a period
* @param PERIOD_LENGTH The period length to use to calculate the period
* @param PERIOD_OFFSET The period offset to use to calculate the period
* @param _period The period to check
* @return _timestamp The timestamp at which the period ends
*/
function getPeriodEndTime(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
uint256 _period
) internal pure returns (uint256) {
return (_period + 1) * PERIOD_LENGTH + PERIOD_OFFSET;
}
/**
* @notice Looks up the newest observation before or at a given timestamp.
* @dev If an observation is available at the target time, it is returned. Otherwise, the newest observation before the target time is returned.
* @param PERIOD_OFFSET The period offset to use to calculate the period
* @param _observations The circular buffer of observations
* @param _accountDetails The account details to query with
* @param _targetTime The timestamp to look up
* @return prevOrAtObservation The observation
*/
function getPreviousOrAtObservation(
uint32 PERIOD_OFFSET,
ObservationLib.Observation[MAX_CARDINALITY] storage _observations,
AccountDetails memory _accountDetails,
uint256 _targetTime
) internal view returns (ObservationLib.Observation memory prevOrAtObservation) {
if (_targetTime < PERIOD_OFFSET) {
return ObservationLib.Observation({ cumulativeBalance: 0, balance: 0, timestamp: 0 });
}
uint256 offsetTargetTime = _targetTime - PERIOD_OFFSET;
// if this is for an overflowed time period, return 0
if (offsetTargetTime > type(uint32).max) {
return
ObservationLib.Observation({
cumulativeBalance: 0,
balance: 0,
timestamp: type(uint32).max
});
}
prevOrAtObservation = _getPreviousOrAtObservation(
_observations,
_accountDetails,
PeriodOffsetRelativeTimestamp.wrap(uint32(offsetTargetTime))
);
}
/**
* @notice Looks up the newest observation before or at a given timestamp.
* @dev If an observation is available at the target time, it is returned. Otherwise, the newest observation before the target time is returned.
* @param _observations The circular buffer of observations
* @param _accountDetails The account details to query with
* @param _offsetTargetTime The timestamp to look up (offset by the period offset)
* @return prevOrAtObservation The observation
*/
function _getPreviousOrAtObservation(
ObservationLib.Observation[MAX_CARDINALITY] storage _observations,
AccountDetails memory _accountDetails,
PeriodOffsetRelativeTimestamp _offsetTargetTime
) private view returns (ObservationLib.Observation memory prevOrAtObservation) {
// If there are no observations, return a zeroed observation
if (_accountDetails.cardinality == 0) {
return ObservationLib.Observation({ cumulativeBalance: 0, balance: 0, timestamp: 0 });
}
uint16 oldestTwabIndex;
(oldestTwabIndex, prevOrAtObservation) = getOldestObservation(_observations, _accountDetails);
// if the requested time is older than the oldest observation
if (PeriodOffsetRelativeTimestamp.unwrap(_offsetTargetTime) < prevOrAtObservation.timestamp) {
// if the user didn't have any activity prior to the oldest observation, then we know they had a zero balance
if (_accountDetails.cardinality < MAX_CARDINALITY) {
return
ObservationLib.Observation({
cumulativeBalance: 0,
balance: 0,
timestamp: PeriodOffsetRelativeTimestamp.unwrap(_offsetTargetTime)
});
} else {
// if we are missing their history, we must revert
revert InsufficientHistory(
_offsetTargetTime,
PeriodOffsetRelativeTimestamp.wrap(prevOrAtObservation.timestamp)
);
}
}
// We know targetTime >= oldestObservation.timestamp because of the above if statement, so we can return here.
if (_accountDetails.cardinality == 1) {
return prevOrAtObservation;
}
// Find the newest observation
(
uint16 newestTwabIndex,
ObservationLib.Observation memory afterOrAtObservation
) = getNewestObservation(_observations, _accountDetails);
// if the target time is at or after the newest, return it
if (PeriodOffsetRelativeTimestamp.unwrap(_offsetTargetTime) >= afterOrAtObservation.timestamp) {
return afterOrAtObservation;
}
// if we know there is only 1 observation older than the newest
if (_accountDetails.cardinality == 2) {
return prevOrAtObservation;
}
// Otherwise, we perform a binarySearch to find the observation before or at the timestamp
(prevOrAtObservation, oldestTwabIndex, afterOrAtObservation, newestTwabIndex) = ObservationLib
.binarySearch(
_observations,
newestTwabIndex,
oldestTwabIndex,
PeriodOffsetRelativeTimestamp.unwrap(_offsetTargetTime),
_accountDetails.cardinality
);
// If the afterOrAt is at, we can skip a temporary Observation computation by returning it here
if (afterOrAtObservation.timestamp == PeriodOffsetRelativeTimestamp.unwrap(_offsetTargetTime)) {
return afterOrAtObservation;
}
return prevOrAtObservation;
}
/**
* @notice Checks if the given timestamp is safe to perform a historic balance lookup on.
* @dev A timestamp is safe if it is before the current overwrite period
* @param PERIOD_LENGTH The period length to use to calculate the period
* @param PERIOD_OFFSET The period offset to use to calculate the period
* @param _time The timestamp to check
* @return isSafe Whether or not the timestamp is safe
*/
function hasFinalized(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
uint256 _time
) internal view returns (bool) {
return _hasFinalized(PERIOD_LENGTH, PERIOD_OFFSET, _time);
}
/**
* @notice Checks if the given timestamp is safe to perform a historic balance lookup on.
* @dev A timestamp is safe if it is on or before the current overwrite period start time
* @param PERIOD_LENGTH The period length to use to calculate the period
* @param PERIOD_OFFSET The period offset to use to calculate the period
* @param _time The timestamp to check
* @return isSafe Whether or not the timestamp is safe
*/
function _hasFinalized(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
uint256 _time
) private view returns (bool) {
// It's safe if equal to the overwrite period start time, because the cumulative balance won't be impacted
return _time <= _currentOverwritePeriodStartedAt(PERIOD_LENGTH, PERIOD_OFFSET);
}
/**
* @notice Checks if the given timestamp is safe to perform a historic balance lookup on.
* @param PERIOD_LENGTH The period length to use to calculate the period
* @param PERIOD_OFFSET The period offset to use to calculate the period
* @param _timestamp The timestamp to check
*/
modifier requireFinalized(
uint32 PERIOD_LENGTH,
uint32 PERIOD_OFFSET,
uint256 _timestamp
) {
// The current period can still be changed; so the start of the period marks the beginning of unsafe timestamps.
uint256 overwritePeriodStartTime = _currentOverwritePeriodStartedAt(
PERIOD_LENGTH,
PERIOD_OFFSET
);
// timestamp == overwritePeriodStartTime doesn't matter, because the cumulative balance won't be impacted
if (_timestamp > overwritePeriodStartTime) {
revert TimestampNotFinalized(_timestamp, overwritePeriodStartTime);
}
_;
}
}