-
Notifications
You must be signed in to change notification settings - Fork 6
/
ExitQueue.sol
193 lines (174 loc) · 6.92 KB
/
ExitQueue.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
// SPDX-License-Identifier: BUSL-1.1
pragma solidity ^0.8.22;
import {Math} from '@openzeppelin/contracts/utils/math/Math.sol';
import {SafeCast} from '@openzeppelin/contracts/utils/math/SafeCast.sol';
import {Errors} from './Errors.sol';
/**
* @title ExitQueue
* @author StakeWise
* @notice ExitQueue represent checkpoints of burned shares and exited assets
*/
library ExitQueue {
/**
* @notice A struct containing checkpoint data
* @param totalTickets The cumulative number of tickets (shares) exited
* @param exitedAssets The number of assets that exited in this checkpoint
*/
struct Checkpoint {
uint160 totalTickets;
uint96 exitedAssets;
}
/**
* @notice A struct containing the history of checkpoints data
* @param checkpoints An array of checkpoints
*/
struct History {
Checkpoint[] checkpoints;
}
/**
* @notice Check whether the position is a V1 position
* @param self An array containing checkpoints
* @param queuedShares The number of shares that are queued for exiting
* @param positionTicket The position ticket to check
* @return true if the position is a V1 position, false otherwise
*/
function isV1Position(
History storage self,
uint256 queuedShares,
uint256 positionTicket
) internal view returns (bool) {
return positionTicket < getLatestTotalTickets(self) + queuedShares;
}
/**
* @notice Get the latest checkpoint total tickets
* @param self An array containing checkpoints
* @return The current total tickets or zero if there are no checkpoints
*/
function getLatestTotalTickets(History storage self) internal view returns (uint256) {
uint256 pos = self.checkpoints.length;
unchecked {
// cannot underflow as subtraction happens in case pos > 0
return pos == 0 ? 0 : _unsafeAccess(self.checkpoints, pos - 1).totalTickets;
}
}
/**
* @notice Get checkpoint index for the burned shares
* @param self An array containing checkpoints
* @param positionTicket The position ticket to search the closest checkpoint for
* @return The checkpoint index or the length of checkpoints array in case there is no such
*/
function getCheckpointIndex(
History storage self,
uint256 positionTicket
) internal view returns (uint256) {
uint256 high = self.checkpoints.length;
uint256 low;
while (low < high) {
uint256 mid = Math.average(low, high);
if (_unsafeAccess(self.checkpoints, mid).totalTickets > positionTicket) {
high = mid;
} else {
unchecked {
// cannot underflow as mid < high
low = mid + 1;
}
}
}
return high;
}
/**
* @notice Calculates burned shares and exited assets
* @param self An array containing checkpoints
* @param checkpointIdx The index of the checkpoint to start calculating from
* @param positionTicket The position ticket to start calculating exited assets from
* @param positionShares The number of shares to calculate assets for
* @return burnedShares The number of shares burned
* @return exitedAssets The number of assets exited
*/
function calculateExitedAssets(
History storage self,
uint256 checkpointIdx,
uint256 positionTicket,
uint256 positionShares
) internal view returns (uint256 burnedShares, uint256 exitedAssets) {
uint256 length = self.checkpoints.length;
// there are no exited assets for such checkpoint index or no shares to burn
if (checkpointIdx >= length || positionShares == 0) return (0, 0);
// previous total tickets for calculating how much shares were burned for the period
uint256 prevTotalTickets;
unchecked {
// cannot underflow as subtraction happens in case checkpointIdx > 0
prevTotalTickets = checkpointIdx == 0
? 0
: _unsafeAccess(self.checkpoints, checkpointIdx - 1).totalTickets;
}
// current total tickets for calculating assets per burned share
// can be used with _unsafeAccess as checkpointIdx < length
Checkpoint memory checkpoint = _unsafeAccess(self.checkpoints, checkpointIdx);
uint256 currTotalTickets = checkpoint.totalTickets;
uint256 checkpointAssets = checkpoint.exitedAssets;
// check whether position ticket is in [prevTotalTickets, currTotalTickets) range
if (positionTicket < prevTotalTickets || currTotalTickets <= positionTicket) {
revert Errors.InvalidCheckpointIndex();
}
// calculate amount of available shares that will be updated while iterating over checkpoints
uint256 availableShares;
unchecked {
// cannot underflow as positionTicket < currTotalTickets
availableShares = currTotalTickets - positionTicket;
}
// accumulate assets until the number of required shares is collected
uint256 checkpointShares;
uint256 sharesDelta;
while (true) {
unchecked {
// cannot underflow as prevTotalTickets <= positionTicket
checkpointShares = currTotalTickets - prevTotalTickets;
// cannot underflow as positionShares > burnedShares while in the loop
sharesDelta = Math.min(availableShares, positionShares - burnedShares);
// cannot overflow as it is capped with underlying asset total supply
burnedShares += sharesDelta;
exitedAssets += Math.mulDiv(sharesDelta, checkpointAssets, checkpointShares);
// cannot overflow as checkpoints are created max once per day
checkpointIdx++;
}
// stop when required shares collected or reached end of checkpoints list
if (positionShares <= burnedShares || checkpointIdx >= length) {
return (burnedShares, exitedAssets);
}
// take next checkpoint
prevTotalTickets = currTotalTickets;
// can use _unsafeAccess as checkpointIdx < length is checked above
checkpoint = _unsafeAccess(self.checkpoints, checkpointIdx);
currTotalTickets = checkpoint.totalTickets;
checkpointAssets = checkpoint.exitedAssets;
unchecked {
// cannot underflow as every next checkpoint total tickets is larger than previous
availableShares = currTotalTickets - prevTotalTickets;
}
}
}
/**
* @notice Pushes a new checkpoint onto a History
* @param self An array containing checkpoints
* @param shares The number of shares to add to the latest checkpoint
* @param assets The number of assets that were exited for this checkpoint
*/
function push(History storage self, uint256 shares, uint256 assets) internal {
if (shares == 0 || assets == 0) revert Errors.InvalidCheckpointValue();
Checkpoint memory checkpoint = Checkpoint({
totalTickets: SafeCast.toUint160(getLatestTotalTickets(self) + shares),
exitedAssets: SafeCast.toUint96(assets)
});
self.checkpoints.push(checkpoint);
}
function _unsafeAccess(
Checkpoint[] storage self,
uint256 pos
) private pure returns (Checkpoint storage result) {
assembly {
mstore(0, self.slot)
result.slot := add(keccak256(0, 0x20), pos)
}
}
}