Milestone 5. Fees and Price Oracle

Swap Fees

Besides knowing when a price range gets engaged/disengaged, we also want to keep track of how much fees each price range accumulated.

To make fee accounting simpler, Uniswap V3 tracks the global fees generated by 1 unit of liquidity. Price range fees are then calculated based on the global ones: fees accumulated outside of a price range are subtracted from the global fees. Fees accumulated outside of a price range are tracked when a tick is crossed (and ticks are crossed when swaps move the price; fees are collected during swaps). With this approach, we don’t need to update fees accumulated by each position on every swap–this allows us to save a lot of gas and make interaction with pools cheaper.

Let’s recap so we have a clear picture before moving on:

Fees are paid by users who swap tokens. A small amount is subtracted from the input token and accumulated on the pool’s balance.
Each pool has feeGrowthGlobal0X128 and feeGrowthGlobal1X128 state variables that track total accumulated fees per unit of liquidity (that is, fee amount divided by the pool’s liquidity).
Notice that at this point actual positions are not updated to optimize gas usage.
Ticks keep a record of fees accumulated outside of them. When adding a new position and activating a tick (adding liquidity to a previously empty tick), the tick records how much fees were accumulated outside of it (by convention, we assume all fees were accumulated below the tick).
Whenever a tick is activated, fees accumulated outside of the tick are updated as the difference between global fees accumulated outside of the tick and the fees accumulated outside of the tick since the last time it was crossed.
Having ticks that know how much fees were accumulated outside of them will allow us to calculate how much fees were accumulated inside of a position (position is a range between two ticks).
Knowing how much fees were accumulated inside a position will allow us to calculate the shares of fees liquidity providers are eligible for. If a position wasn’t involved in swapping, it’ll have zero fees accumulated inside of it and the liquidity providers who provided liquidity into this range will have no profits from it.

Calculating Position Accumulated Fees

To calculate total fees accumulated by a position, we need to consider two cases: when the current price is inside the position and when it’s outside of the position. In both cases, we subtract fees collected outside of the lower and the upper ticks of the position from fees collected globally. However, we calculate those fees differently depending on the current price.

When the current price is inside the position, we subtract the fees that have been collected outside of ticks by this moment.

When the current price is outside of the position, we need to update fees collected by either upper or lower ticks before subtracting them from fees collected globally. We update them only for the calculations and don’t overwrite them in ticks because the ticks don’t get crossed.

This is how we update fees collected outside of a tick:

$$ f_o(i) = f_g - f_o(i) $$

Fees collected outside of a tick (fo(i)) is the difference between fees collected globally (fg) and fees collected outside of the tick when it crossed last time. We kind of reset the counter when a tick is crossed.

To calculate fees collected inside a position:

$$ f_r = f_g - f_b(i_l) - f_a(i_u) $$

We subtract fees collected below its lower tick ($f_b(i_l)$) and above its upper tick ($f_a(i_u)$) from fees collected globally from all price ranges ($f_g$). This is what we saw in the illustration above.

Now, when the current price is above the lower tick (i.e. the position is engaged), we don’t need to update fees accumulated below the lower tick and can simply take them from the lower tick. The same is true for fees collected outside of the upper tick when the current price is below the upper tick.

In the two other cases, we need to consider updated fees:

when taking fees collected below the lower tick and the current price is also below the tick (the lower tick hasn’t been crossed recently).
when taking fees above the upper tick and the current price is also above the tick (the upper tick hasn’t been crossed recently).

Accruing Swap Fees

Adding Required State Variables

Collecting Fees

The function now also returns the fee amount collected during the step–it’s calculated differently depending on whether the upper limit of the range was reached or not:

bool max = sqrtPriceNextX96 == sqrtPriceTargetX96;
if (!max) {
    feeAmount = amountRemaining - amountIn;
} else {
    feeAmount = Math.mulDivRoundingUp(amountIn, fee, 1e6 - fee);
}

When it’s not reached, the current price range has enough liquidity to fulfill the swap, thus we simply return the difference between the amount we needed to fulfill and the actual amount fulfilled. Notice that amountRemainingLessFee is not involved here since the actual final amount was calculated in amountIn (it’s calculated based on available liquidity).

When the target price is reached, we cannot subtract fees from the entire amountRemaining because the current price range doesn’t have enough liquidity to fulfill the swap. Thus, the fee amount is subtracted from the amount the current price range has fulfilled (amountIn).

More explanation :

Calculating the Fee Amount

When the swap reaches the target price (max is true), the amount swapped (amountIn) is known, but we need to compute the fee based on this amount. To find the fee amount, we reverse the earlier fee deduction calculation.

if we can fill the order

$$amountRemainingLessFee = amountRemaining * \frac{1e6−fee}{1e6}$$$$feeAmount = amountRemaining - amountIn (⇒ given by getNextSqrtPriceFromInput)$$

FROM my understanding, we can have the amountIn with these formulas (however we don’t have the next price):

$$amountIn == amountRemainingLessFee$$$$amountIn = amountRemaining * \frac{1e6−fee}{1e6}$$$$amountIn = amountRemaining - feeAmount$$

We can fill partially the order

We can get the feeAmount for amountIn with these formulas

$$amountIn = amountRemaining - feeAmount$$$$amountRemaining = amountIn * \frac{1e6}{1e6−fee}$$$$feeAmount = amountRemaining - amountIn$$

Derivation of `feeAmount`

Here is a step-by-step derivation of the equation for feeAmount based on the relationship between amountIn and amountRemaining.

Starting Equation:
Given the initial relationship for amountIn:
$$ amountIn = amountRemaining \times \frac{1e6 - fee}{1e6} $$
Isolating amountRemaining:
To isolate amountRemaining, we rearrange the equation:
$$ amountRemaining = amountIn \times \frac{1e6}{1e6 - fee} $$
Expressing feeAmount:
The fee amount can be expressed as the difference between amountRemaining and amountIn:
$$ feeAmount = amountRemaining - amountIn $$
Substituting amountRemaining:
Substitute the expression for amountRemaining from step 2 into the equation for feeAmount:
$$ feeAmount = \left( amountIn \times \frac{1e6}{1e6 - fee} \right) - amountIn $$
Simplifying the Expression:
Factor out amountIn from the terms on the right-hand side:
$$ feeAmount = amountIn \left( \frac{1e6}{1e6 - fee} - 1 \right) $$
Combining the Fractions:
Combine the fractions to simplify the expression inside the parentheses:
$$ \frac{1e6}{1e6 - fee} - 1 = \frac{1e6 - (1e6 - fee)}{1e6 - fee} = \frac{fee}{1e6 - fee} $$
Final Expression for feeAmount:
Substitute this back into the equation for feeAmount:
$$ feeAmount = amountIn \times \frac{fee}{1e6 - fee} $$

Updating Fee Trackers in Ticks

Updating Global Fee Trackers

Fee Tracking in Positions Management

Initialization of Fee Trackers in Ticks

In the Tick.update function, whenever a tick is initialized (adding liquidity to a previously empty tick), we initialize its fee trackers. However, we’re only doing so when the tick is below the current price, i.e. when it’s inside of the current price range:

// src/lib/Tick.sol
function update(
    mapping(int24 => Tick.Info) storage self,
    int24 tick,
    int24 currentTick,
    int128 liquidityDelta,
    uint256 feeGrowthGlobal0X128,
    uint256 feeGrowthGlobal1X128,
    bool upper
) internal returns (bool flipped) {
    ...
    if (liquidityBefore == 0) {
        // by convention, assume that all previous fees were collected below
        // the tick
        if (tick <= currentTick) {
            tickInfo.feeGrowthOutside0X128 = feeGrowthGlobal0X128;
            tickInfo.feeGrowthOutside1X128 = feeGrowthGlobal1X128;
        }

        tickInfo.initialized = true;
    }
    ...
}

If it’s not inside of the current price range, its fee trackers will be 0 and they’ll be updated when the tick is crossed next time (see the cross function we updated above).

Updating Position Fees and Token Amounts

// src/lib/Tick.sol
function getFeeGrowthInside(
    mapping(int24 => Tick.Info) storage self,
    int24 lowerTick_,
    int24 upperTick_,
    int24 currentTick,
    uint256 feeGrowthGlobal0X128,
    uint256 feeGrowthGlobal1X128
)
    internal
    view
    returns (uint256 feeGrowthInside0X128, uint256 feeGrowthInside1X128)
{
    Tick.Info storage lowerTick = self[lowerTick_];
    Tick.Info storage upperTick = self[upperTick_];

    uint256 feeGrowthBelow0X128;
    uint256 feeGrowthBelow1X128;
    if (currentTick >= lowerTick_) {
        feeGrowthBelow0X128 = lowerTick.feeGrowthOutside0X128;
        feeGrowthBelow1X128 = lowerTick.feeGrowthOutside1X128;
    } else {
        feeGrowthBelow0X128 =
            feeGrowthGlobal0X128 -
            lowerTick.feeGrowthOutside0X128;
        feeGrowthBelow1X128 =
            feeGrowthGlobal1X128 -
            lowerTick.feeGrowthOutside1X128;
    }

    uint256 feeGrowthAbove0X128;
    uint256 feeGrowthAbove1X128;
    if (currentTick < upperTick_) {
        feeGrowthAbove0X128 = upperTick.feeGrowthOutside0X128;
        feeGrowthAbove1X128 = upperTick.feeGrowthOutside1X128;
    } else {
        feeGrowthAbove0X128 =
            feeGrowthGlobal0X128 -
            upperTick.feeGrowthOutside0X128;
        feeGrowthAbove1X128 =
            feeGrowthGlobal1X128 -
            upperTick.feeGrowthOutside1X128;
    }

    feeGrowthInside0X128 =
        feeGrowthGlobal0X128 -
        feeGrowthBelow0X128 -
        feeGrowthAbove0X128;
    feeGrowthInside1X128 =
        feeGrowthGlobal1X128 -
        feeGrowthBelow1X128 -
        feeGrowthAbove1X128;
}

Examples:

Explanation from LLM

Function Purpose

The getFeeGrowthInside function calculates the fee growth inside a specified range of ticks (lowerTick_ to upperTick_). This is important for determining how much fees have been accumulated within a particular liquidity position.

Parameters

self: The storage reference to the mapping of ticks.
lowerTick_: The lower tick boundary of the position.
upperTick_: The upper tick boundary of the position.
currentTick: The current tick (price) of the pool.
feeGrowthGlobal0X128: The global fee growth for token0.
feeGrowthGlobal1X128: The global fee growth for token1.

Steps in the Function

Retrieve Tick Information:

Tick_Info storage lowerTick = self[lowerTick_];
Tick_Info storage upperTick = self[upperTick_];

Calculate Fee Growth Below the Lower Tick:

uint256 feeGrowthBelow0X128;
uint256 feeGrowthBelow1X128;
if (currentTick >= lowerTick_) {
    feeGrowthBelow0X128 = lowerTick.feeGrowthOutside0X128;
    feeGrowthBelow1X128 = lowerTick.feeGrowthOutside1X128;
} else {
    feeGrowthBelow0X128 =
        feeGrowthGlobal0X128 -
        lowerTick.feeGrowthOutside0X128;
    feeGrowthBelow1X128 =
        feeGrowthGlobal1X128 -
        lowerTick.feeGrowthOutside1X128;
}

Condition Explanation:
- If currentTick >= lowerTick_, it means the current price is within or above the lower tick boundary. So, the fees collected below the lower tick are already accounted for in lowerTick.feeGrowthOutside.
- If currentTick < lowerTick_, it means the current price is below the lower tick boundary. Therefore, the fees collected below the lower tick must be subtracted from the global fee growth to get the fees outside the lower tick.

Calculate Fee Growth Above the Upper Tick:

uint256 feeGrowthAbove0X128;
uint256 feeGrowthAbove1X128;
if (currentTick < upperTick_) {
    feeGrowthAbove0X128 = upperTick.feeGrowthOutside0X128;
    feeGrowthAbove1X128 = upperTick.feeGrowthOutside1X128;
} else {
    feeGrowthAbove0X128 =
        feeGrowthGlobal0X128 -
        upperTick.feeGrowthOutside0X128;
    feeGrowthAbove1X128 =
        feeGrowthGlobal1X128 -
        upperTick.feeGrowthOutside1X128;
}

Condition Explanation:
- If currentTick < upperTick_, it means the current price is within or below the upper tick boundary. So, the fees collected above the upper tick are already accounted for in upperTick.feeGrowthOutside.
- If currentTick >= upperTick_, it means the current price is above the upper tick boundary. Therefore, the fees collected above the upper tick must be subtracted from the global fee growth to get the fees outside the upper tick.

Calculate Fee Growth Inside the Position:
```
feeGrowthInside0X128 =
    feeGrowthGlobal0X128 -
    feeGrowthBelow0X128 -
    feeGrowthAbove0X128;
feeGrowthInside1X128 =
    feeGrowthGlobal1X128 -
    feeGrowthBelow1X128 -
    feeGrowthAbove1X128;
```
- Final Calculation:
  - The fees inside the position are calculated by subtracting the fees outside the lower and upper ticks from the global fee growth. This gives the total fees accumulated within the tick range defined by lowerTick_ and upperTick_.

Question

can you develop :

the fees collected below the lower tick must be subtracted from the global fee growth to get the fees outside the lower tick.
the fees collected above the upper tick must be subtracted from the global fee growth to get the fees outside the upper tick

Sure, let’s dive deeper into the reasoning behind these two points.

Fees Collected Below the Lower Tick

Concept

The idea is to account for the fees accumulated in different segments of the tick range. Specifically, we need to isolate the fees that were collected below the lowerTick_ boundary from the rest of the global fee growth. This helps in accurately calculating the fee growth within the specified tick range.

Detailed Explanation

Global Fee Growth: This is the total fee growth across all ticks from the start of the pool until now.
Fee Growth Outside the Lower Tick: This is the fee growth that has occurred outside (below) the lowerTick_.

When the currentTick is below the lowerTick_, the pool has not yet reached the lowerTick_ position in its price movement. Thus, all fee growth attributed to positions below the lowerTick_ must be subtracted from the global fee growth to isolate the fees that are actually within the specified range.

Calculation

When currentTick < lowerTick_:
```
feeGrowthBelow0X128 = feeGrowthGlobal0X128 - lowerTick.feeGrowthOutside0X128;
feeGrowthBelow1X128 = feeGrowthGlobal1X128 - lowerTick.feeGrowthOutside1X128;
```
- feeGrowthGlobal0X128 and feeGrowthGlobal1X128 represent the total fee growth for token0 and token1, respectively.
- lowerTick.feeGrowthOutside0X128 and lowerTick.feeGrowthOutside1X128 are the fees that have been collected outside (below) the lowerTick_.

By subtracting lowerTick.feeGrowthOutside0X128 from feeGrowthGlobal0X128, we get the fee growth that is not below the lowerTick_, effectively isolating the fees outside the lower tick.

Fees Collected Above the Upper Tick

Concept

Similarly, we need to account for the fees accumulated above the upperTick_ boundary. This helps in isolating the fee growth within the specified tick range and excluding any fees that were collected above the upperTick_.

Detailed Explanation

Global Fee Growth: Again, this is the total fee growth across all ticks from the start of the pool until now.
Fee Growth Outside the Upper Tick: This is the fee growth that has occurred outside (above) the upperTick_.

When the currentTick is above the upperTick_, the pool has moved past the upperTick_ position. Therefore, all fee growth attributed to positions above the upperTick_ must be subtracted from the global fee growth to isolate the fees that are within the specified range.

Calculation

When currentTick >= upperTick_:
```
feeGrowthAbove0X128 = feeGrowthGlobal0X128 - upperTick.feeGrowthOutside0X128;
feeGrowthAbove1X128 = feeGrowthGlobal1X128 - upperTick.feeGrowthOutside1X128;
```
- feeGrowthGlobal0X128 and feeGrowthGlobal1X128 represent the total fee growth for token0 and token1, respectively.
- upperTick.feeGrowthOutside0X128 and upperTick.feeGrowthOutside1X128 are the fees that have been collected outside (above) the upperTick_.

By subtracting upperTick.feeGrowthOutside0X128 from feeGrowthGlobal0X128, we get the fee growth that is not above the upperTick_, effectively isolating the fees outside the upper tick.

Summary

The key idea is to isolate the fee growth within the specific range defined by lowerTick_ and upperTick_. This is done by:

Subtracting the fee growth outside (below) the lowerTick_ from the global fee growth when the currentTick is below the lowerTick_.
Subtracting the fee growth outside (above) the upperTick_ from the global fee growth when the currentTick is above the upperTick_.

This ensures that the fee growth inside the specified tick range is accurately calculated, reflecting only the fees accumulated within the boundaries of lowerTick_ and upperTick_.

Removing Liquidity

This function simply transfers tokens from a pool and ensures that only valid amounts can be transferred (one cannot transfer out more than they burned + fees they earned).

There’s also a way to collect fees only without burning liquidity: burn 0 amount of liquidity and then call collect. During burning, the position will be updated and the token amounts it owes will be updated as well.

Flash Loan Fees

Protocol Fees

For brevity, we’re not going to add protocol fees to our implementation, but let’s see how they’re implemented in Uniswap.

function setFeeProtocol(uint8 feeProtocol0, uint8 feeProtocol1) external override lock onlyFactoryOwner {
    require(
        (feeProtocol0 == 0 || (feeProtocol0 >= 4 && feeProtocol0 <= 10)) &&
            (feeProtocol1 == 0 || (feeProtocol1 >= 4 && feeProtocol1 <= 10))
    );
    uint8 feeProtocolOld = slot0.feeProtocol;
    slot0.feeProtocol = feeProtocol0 + (feeProtocol1 << 4);
    emit SetFeeProtocol(feeProtocolOld % 16, feeProtocolOld >> 4, feeProtocol0, feeProtocol1);
}

As you can see, it’s allowed to set protocol fees separately for each of the tokens. The values are two uint8 that are packed to be stored in one uint8: feeProtocol1 is shifted to the left by 4 bits (this is identical to multiplying it by 16) and added to feeProtocol0. To unpack feeProtocol0, a remainder of division slot0.feeProtocol by 16 is taken; feeProtocol1 is simply shifting slot0.feeProtocol to the right by 4 bits. Such packing works because neither feeProtocol0, nor feeProtocol1 can be greater than 10.

Price Oracle

Geometric mean

Price Oracle Implementation

Observations and Cardinality

However, since storing that many instances of Observation requires a lot of gas (someone would have to pay for writing each of them to the contract’s storage), a pool by default can store only 1 observation, which gets overwritten each time a new price is recorded. The number of activated observations, the cardinality of observations, can be increased at any time by anyone willing to pay for that.

Writing Observations

// src/UniswapV3Pool.sol
contract UniswapV3Pool is IUniswapV3Pool {
    function swap(...) public returns (...) {
        ...
        if (state.tick != slot0_.tick) {
            (
                uint16 observationIndex,
                uint16 observationCardinality
            ) = observations.write(
                    slot0_.observationIndex,
                    _blockTimestamp(),
                    slot0_.tick,
                    slot0_.observationCardinality,
                    slot0_.observationCardinalityNext
                );
            
            (
                slot0.sqrtPriceX96,
                slot0.tick,
                slot0.observationIndex,
                slot0.observationCardinality
            ) = (
                state.sqrtPriceX96,
                state.tick,
                observationIndex,
                observationCardinality
            );
        }
        ...
    }
}

Notice that the tick that’s observed here is slot0_.tick (not state.tick), i.e. the price before the swap! It’s updated with a new price in the next statement. This is the price manipulation mitigation we discussed earlier: Uniswap tracks prices before the first trade in the block and after the last trade in the previous block.

Also notice that each observation is identified by _blockTimestamp(), i.e. the current block timestamp. This means that if there’s already an observation for the current block, a price is not recorded. If there are no observations for the current block (i.e. this is the first swap in the block), a price is recorded. This is part of the price manipulation mitigation mechanism.

// src/lib/Oracle.sol
function write(
    Observation[65535] storage self,
    uint16 index,
    uint32 timestamp,
    int24 tick,
    uint16 cardinality,
    uint16 cardinalityNext
) internal returns (uint16 indexUpdated, uint16 cardinalityUpdated) {
    Observation memory last = self[index];

    if (last.timestamp == timestamp) return (index, cardinality);

    if (cardinalityNext > cardinality && index == (cardinality - 1)) {
        cardinalityUpdated = cardinalityNext;
    } else {
        cardinalityUpdated = cardinality;
    }

    indexUpdated = (index + 1) % cardinalityUpdated;
    self[indexUpdated] = transform(last, timestamp, tick);
}

function transform(
    Observation memory last,
    uint32 timestamp,
    int24 tick
) internal pure returns (Observation memory) {
    uint56 delta = timestamp - last.timestamp;

    return
        Observation({
            timestamp: timestamp,
            tickCumulative: last.tickCumulative +
                int56(tick) *
                int56(delta),
            initialized: true
        });
}

What we’re calculating here is the accumulated price: the current tick gets multiplied by the number of seconds since the last observation and gets added to the last accumulated price.

Accumulated price :

$$ a_i = \sum_{i=1}^tlog_{1.0001}P(i) $$

Increasing Cardinality

Reading Observations

So, reading observations means finding observations by timestamps and interpolating missing observations, taking into consideration that the observations array is allowed to overflow (e.g. the oldest observation can come after the most recent one in the array). Since we’re not indexing the observations by timestamps (to save gas), we’ll need to use the binary search algorithm for efficient search. But not always.

function observe(
    Observation[65535] storage self,
    uint32 time,
    uint32[] memory secondsAgos,
    int24 tick,
    uint16 index,
    uint16 cardinality
) internal view returns (int56[] memory tickCumulatives) {
    tickCumulatives = new int56[](secondsAgos.length);

    for (uint256 i = 0; i < secondsAgos.length; i++) {
        tickCumulatives[i] = observeSingle(
            self,
            time,
            secondsAgos[i],
            tick,
            index,
            cardinality
        );
    }
}

The function takes the current block timestamp, the list of time points we want to get prices at (secondsAgo), the current tick, the observations index, and the cardinality.

function observeSingle(
    Observation[65535] storage self,
    uint32 time,
    uint32 secondsAgo,
    int24 tick,
    uint16 index,
    uint16 cardinality
) internal view returns (int56 tickCumulative) {
    if (secondsAgo == 0) {
        Observation memory last = self[index];
        if (last.timestamp != time) last = transform(last, time, tick);
        return last.tickCumulative;
    }
    ...
}

When the most recent observation is requested (0 seconds passed), we can return it right away. If it wasn’t recorded in the current block, transform it to consider the current block and the current tick.

If an older time point is requested, we need to make several checks before switching to the binary search algorithm:

if the requested time point is the last observation, we can return the accumulated price at the latest observation;
if the requested time point is after the last observation, we can call transform to find the accumulated price at this point, knowing the last observed price and the current price;
if the requested time point is before the last observation, we have to use the binary search.

Let’s go straight to the third point:

function binarySearch(
    Observation[65535] storage self,
    uint32 time,
    uint32 target,
    uint16 index,
    uint16 cardinality
)
    private
    view
    returns (Observation memory beforeOrAt, Observation memory atOrAfter)
{
    ...

The function takes the current block timestamp (time), the timestamp of the price point requested (target), as well as the current observations index and cardinality. It returns the range between two observations in which the requested time point is located.

Examples from LLM

Example : `[10, 20, 30, 40, 50, 60, 70]`

Example 1: `[10, 20, 30, 40, 50, 60, 70]`

Cardinality: 7
Index: 6
Target: 35 (for example)

Assume the timestamps of the observations are as follows:

[-10, 20, 30, 40, 50, 60, 70] // These correspond to indices [0, 1, 2, 3, 4, 5, 6]

Initial Setup

Initial Boundaries:

uint256 l = (index + 1) % cardinality; // (6 + 1) % 7 = 0
uint256 r = l + cardinality - 1; // 0 + 7 - 1 = 6

So, l = 0 and r = 6.

First Iteration

Calculate Midpoint:
```
i = (l + r) / 2; // (0 + 6) / 2 = 3
```
- beforeOrAt = self[3]; // Timestamp = 40
- atOrAfter = self[(3 + 1) % 7]; // Timestamp = 50
Check Condition:
```
bool targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(40, 35) => false
```
Since targetAtOrAfter is false (40 > 35), the target is in the left half, so we update the right boundary::
```
r = i - 1; // r = 3 - 1 = 2
```

Second Iteration

Calculate New Midpoint:
```
i = (l + r) / 2; // (0 + 2) / 2 = 1
```
- beforeOrAt = self[1]; // Timestamp = 20
- atOrAfter = self[(1 + 1) % 7]; // Timestamp = 30
Check Condition:
```
bool targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(20, 35) => true
```
Since targetAtOrAfter is true (20 <= 35) and target (35) is not between 20 and 30, the target is in the right half, so we update the left boundary:
```
l = i + 1; // l = 1 + 1 = 2
```

Third Iteration

Calculate New Midpoint:
```
i = (l + r) / 2; // (2 + 2) / 2 = 2
```
- beforeOrAt = self[2]; // Timestamp = 30
- atOrAfter = self[(2 + 1) % 7]; // Timestamp = 40

Check Condition:

bool targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(30, 35) => true

Now targetAtOrAfter is true (30 <= 35) and target (35) is between 30 and 40:

if (targetAtOrAfter && lte(time, target, atOrAfter.timestamp))
    break;

The condition is met, and the loop breaks.

Example 2 : `[10, 20, 30, 40, 50, 0, 0]`

Initial Setup

Array: [10, 20, 30, 40, 50, 0, 0]
Cardinality: 7
Index: 4
Target: 35

Initial Boundaries

uint256 l = (index + 1) % cardinality; // l = (4 + 1) % 7 = 5
uint256 r = l + cardinality - 1; // r = 5 + 7 - 1 = 11

Since r should be within the array bounds, we will work with r as it is for now, but keep in mind that the actual array access will use modulo cardinality.

First Iteration

Calculate Midpoint:

uint256 i = (l + r) / 2; // i = (5 + 11) / 2 = 8

Access Observations:

Observation memory beforeOrAt = self[i % cardinality]; // self[8 % 7] = self[1] (20)
Observation memory atOrAfter = self[(i + 1) % cardinality]; // self[(8 + 1) % 7] = self[2] (30)

Check Initialization:
```
if (!beforeOrAt.initialized) { l = i + 1; continue; }
```
Since beforeOrAt (20) is initialized, we proceed.

Check Target Range:

bool targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(20, 35) = true
if (targetAtOrAfter && lte(time, target, atOrAfter.timestamp)) // lte(35, 30) = false
    break;

targetAtOrAfter is true because 20 <= 35.
lte(35, 30) is false, so the target is not between 20 and 30.

Adjust Boundaries:

if (!targetAtOrAfter) r = i - 1; // Not executed
else l = i + 1; // l = 8 + 1 = 9

Second Iteration

Calculate Midpoint:

i = (l + r) / 2; // i = (9 + 11) / 2 = 10

Access Observations:

beforeOrAt = self[i % cardinality]; // self[10 % 7] = self[3] (40)
atOrAfter = self[(i + 1) % cardinality]; // self[(10 + 1) % 7] = self[4] (50)

Check Initialization:
```
if (!beforeOrAt.initialized) { l = i + 1; continue; }
```
Since beforeOrAt (40) is initialized, we proceed.

Check Target Range:

targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(40, 35) = false
if (targetAtOrAfter && lte(time, target, atOrAfter.timestamp)) // Not executed
    break;

targetAtOrAfter is false because 40 > 35.

Adjust Boundaries:

if (!targetAtOrAfter) r = i - 1; // r = 10 - 1 = 9
else l = i + 1; // Not executed

Third Iteration

Calculate Midpoint:

i = (l + r) / 2; // i = (9 + 9) / 2 = 9

Access Observations:

beforeOrAt = self[i % cardinality]; // self[9 % 7] = self[2] (30)
atOrAfter = self[(i + 1) % cardinality]; // self[(9 + 1) % 7] = self[3] (40)

Check Initialization:
```
if (!beforeOrAt.initialized) { l = i + 1; continue; }
```
Since beforeOrAt (30) is initialized, we proceed.

Check Target Range:

bool targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(30, 35) = true
if (targetAtOrAfter && lte(time, target, atOrAfter.timestamp)) // lte(35, 40) = true
    break;

targetAtOrAfter is true because 30 <= 35.
lte(35, 40) is true, so the target is between 30 and 40.

Since the condition targetAtOrAfter && lte(time, target, atOrAfter.timestamp) is true, we break out of the loop.

Example 3 : `[70, 20, 30, 40, 50]`

Initial Setup

Array: [70, 20, 30, 40, 50]
Cardinality: 5
Index: 4
Target: 60

Initial Boundaries

uint256 l = (index + 1) % cardinality; // l = (4 + 1) % 5 = 0
uint256 r = l + cardinality - 1; // r = 0 + 5 - 1 = 4

First Iteration

Calculate Midpoint:

uint256 i = (l + r) / 2; // i = (0 + 4) / 2 = 2

Access Observations:

Observation memory beforeOrAt = self[i % cardinality]; // self[2 % 5] = self[2] (30)
Observation memory atOrAfter = self[(i + 1) % cardinality]; // self[(2 + 1) % 5] = self[3] (40)

Check Initialization:
```
if (!beforeOrAt.initialized) { l = i + 1; continue; }
```
Since beforeOrAt (30) is initialized, we proceed.

Check Target Range:

bool targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(30, 60) = true
if (targetAtOrAfter && lte(time, target, atOrAfter.timestamp)) // lte(60, 40) = false
    break;

targetAtOrAfter is true because 30 <= 60.
lte(60, 40) is false, so the target is not between 30 and 40.

Adjust Boundaries:

if (!targetAtOrAfter) r = i - 1; // Not executed
else l = i + 1; // l = 2 + 1 = 3

Second Iteration

Calculate Midpoint:

i = (l + r) / 2; // i = (3 + 4) / 2 = 3

Access Observations:

beforeOrAt = self[i % cardinality]; // self[3 % 5] = self[3] (40)
atOrAfter = self[(i + 1) % cardinality]; // self[(3 + 1) % 5] = self[4] (50)

Check Initialization:
```
if (!beforeOrAt.initialized) { l = i + 1; continue; }
```
Since beforeOrAt (40) is initialized, we proceed.

Check Target Range:

targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(40, 60) = true
if (targetAtOrAfter && lte(time, target, atOrAfter.timestamp)) // lte(60, 50) = false
    break;

targetAtOrAfter is true because 40 <= 60.
lte(60, 50) is false, so the target is not between 40 and 50.

Adjust Boundaries:

if (!targetAtOrAfter) r = i - 1; // Not executed
else l = i + 1; // l = 3 + 1 = 4

Third Iteration

Calculate Midpoint:

i = (l + r) / 2; // i = (4 + 4) / 2 = 4

Access Observations:

beforeOrAt = self[i % cardinality]; // self[4 % 5] = self[4] (50)
atOrAfter = self[(i + 1) % cardinality]; // self[(4 + 1) % 5] = self[0] (70)

Check Initialization:
```
if (!beforeOrAt.initialized) { l = i + 1; continue; }
```
Since beforeOrAt (50) is initialized, we proceed.

Check Target Range:

targetAtOrAfter = lte(time, beforeOrAt.timestamp, target); // lte(50, 60) = true
if (targetAtOrAfter && lte(time, target, atOrAfter.timestamp)) // lte(60, 70) = true
    break;

targetAtOrAfter is true because 50 <= 60.
lte(60, 70) is true, so the target is between 50 and 70.

Since the condition targetAtOrAfter && lte(time, target, atOrAfter.timestamp) is true, we break out of the loop.

// function observeSingle() {
    ...
    uint56 observationTimeDelta = atOrAfter.timestamp -
        beforeOrAt.timestamp;
    uint56 targetDelta = target - beforeOrAt.timestamp;
    return
        beforeOrAt.tickCumulative +
        ((atOrAfter.tickCumulative - beforeOrAt.tickCumulative) /
            int56(observationTimeDelta)) *
        int56(targetDelta);
    ...

Want to calculate the tickCumulative between beforeAt and target

Interpreting Observations

Code

Check repo

Calculating the Fee Amount#

Derivation of feeAmount#

Function Purpose#

Parameters#

Steps in the Function#

Fees Collected Below the Lower Tick#

Concept#

Detailed Explanation#

Calculation#

Fees Collected Above the Upper Tick#

Concept#

Detailed Explanation#

Calculation#

Summary#

Example 1: [10, 20, 30, 40, 50, 60, 70]#

Initial Setup#

First Iteration#

Second Iteration#

Third Iteration#

Initial Setup#

Initial Boundaries#

First Iteration#

Second Iteration#

Third Iteration#

Initial Setup#

Initial Boundaries#

First Iteration#

Second Iteration#

Third Iteration#

Code#

Calculating the Fee Amount

Derivation of `feeAmount`

Function Purpose

Parameters

Steps in the Function

Fees Collected Below the Lower Tick

Concept

Detailed Explanation

Calculation

Fees Collected Above the Upper Tick

Concept

Detailed Explanation

Calculation

Summary

Example 1: `[10, 20, 30, 40, 50, 60, 70]`

Initial Setup

First Iteration

Second Iteration

Third Iteration

Initial Setup

Initial Boundaries

First Iteration

Second Iteration

Third Iteration

Initial Setup

Initial Boundaries

First Iteration

Second Iteration

Third Iteration

Code