Expose binary lookup functions in Checkpoint

[byeongsu-hong]

🧐 Motivation

While implementing WithdrawalQueue using Checkpoint, I discovered that the current Checkpoint implementation only allows retrieving values based on specific keys. Since I'm implementing a system that can process requests in ranges by adjusting the offset, it would be beneficial to have a way to retrieve Checkpoint indices or positions.

📝 Details

Target functions: _upperBinaryLookup, _lowerBinaryLookup

1. Add wrapper functions for those functions

[Amxx]

Hello @byeongsu-hong

One of the reason these function are not exposed is because inproper arguments would cause unsafe/unexpected behavior, and checking the arguments are correct would require additional sloads that we want to avoid.

Can you tell us more about your usecase. What do you mean by "process requests in ranges". Can you give use an example. Maybe what we should ahve is a function that exposes implement that high level feature.

[byeongsu-hong]

Hi @Amxx, I understand your intent.

For our case, We implemented simple withdrawal queue like this.

struct Queue {
    uint48 withdrawalPeriod;
    uint208 offset;
    Checkpoints.Trace208 requests;
}

function requestWithdraw() // push new Checkpoint with accumulated amount
function claimWithdraw() // calculates claimable amount using binary search + set new offset to ignore claimed requests

We need to know the pos of the latest request for specific time to apply new offset.

[Amxx]

Can you share the implementation of claimWithdraw() ?

[byeongsu-hong]

Sure, Here it is. We temporarily made an extension library that contains valueAt and upperBinaryLookup

function claimWithdraw(address receiver) external nonReentrant returns (uint256) {
  StorageV1 storage $ = _getStorageV1();

  Checkpoints.Trace208 storage requests = $.queue[receiver].requests;

  uint256 offset = $.queue[receiver].offset;
  uint256 reqLen = requests.length();
  require(reqLen > offset, NothingToClaim());

  uint256 found = requests.upperBinaryLookup(clock() - $.withdrawalPeriod, offset, reqLen);
  require(found > offset + 1, NothingToClaim());

  uint256 claimed = requests.valueAt((found - 1).toUint32()) - requests.valueAt(offset.toUint32());
  $.queue[receiver].offset = found - 1;

  receiver.safeTransferETH(claimed);

  emit WithdrawRequestClaimed(receiver, claimed, offset, found - 1);

  return claimed;
}

[Amxx]

I'm wondering if you can't already solve that with the function you have available. It feels to me like the values in your requests structure are sorted (that is what I understand from the claimed computation.

Would something like this not work just fine ?

function claimWithdraw(address receiver) external nonReentrant returns (uint256) {
  StorageV1 storage $ = _getStorageV1();

  Checkpoints.Trace208 storage requests = $.queue[receiver].requests;

  uint256 alreadyClaimed = $.queue[receiver].alreadyClaimed;
  uint256 totalClaimable = requests.upperLookup(clock() - $.withdrawalPeriod);
  uint256 release = Math.saturatingSub(totalClaimable, alreadyClaimed); 

  $.queue[receiver].alreadyClaimed += release;
  receiver.safeTransferETH(release);

  emit WithdrawRequestClaimed(receiver, release, ...);

  return release;
}