Michael.W基于Foundry精读Openzeppelin第13期——Checkpoints.sol

0. 版本

[openzeppelin]：v4.8.3，[forge-std]：v1.5.6

0.1 Checkpoints.sol

Github: https://github.com/OpenZeppelin/openzeppelin-contracts/blob/v4.8.3/contracts/utils/Checkpoints.sol

Checkpoints库定义了History、Trace224和Trace160结构体。这些结构体中包含了在各个不同的区块高度或自定义key上记录的数值并可以查询出对应区块高度或key上的记录值。Checkpoints库提供了标准的添加记录、查询记录的库方法。

1. 目标合约

封装Checkpoints library成为一个可调用合约：

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/src/utils/MockCheckpoints.sol

// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;

import "openzeppelin-contracts/contracts/utils/Checkpoints.sol";

contract MockCheckpointsHistory {
    using Checkpoints for Checkpoints.History;

    Checkpoints.History _history;

    function getAtBlock(uint blockNumber) external view returns (uint) {
        return _history.getAtBlock(blockNumber);
    }

    function getAtProbablyRecentBlock(uint blockNumber) external view returns (uint){
        return _history.getAtProbablyRecentBlock(blockNumber);
    }

    function push(uint value) external returns (uint, uint) {
        return _history.push(value);
    }

    // a customized function for update latest value of _history
    function op(uint latestValue, uint delta) internal pure returns (uint){
        return latestValue + delta;
    }

    function pushWithOp(uint delta) external returns (uint, uint) {
        return _history.push(op, delta);
    }

    function latest() external view returns (uint224){
        return _history.latest();
    }

    function latestCheckpoint() external view returns (
        bool exists,
        uint32 _blockNumber,
        uint224 _value
    ){
        return _history.latestCheckpoint();
    }

    function length() external view returns (uint){
        return _history.length();
    }
}

contract MockCheckpointsTrace224 {
    using Checkpoints for Checkpoints.Trace224;

    Checkpoints.Trace224 _trace224;

    function push(
        uint32 key,
        uint224 value
    ) external returns (uint224, uint224){
        return _trace224.push(key, value);
    }

    function lowerLookup(uint32 key) external view returns (uint224){
        return _trace224.lowerLookup(key);
    }

    function upperLookup(uint32 key) external view returns (uint224){
        return _trace224.upperLookup(key);
    }

    function latest() external view returns (uint224) {
        return _trace224.latest();
    }

    function latestCheckpoint() external view returns (
        bool exists,
        uint32 _key,
        uint224 _value
    ){
        return _trace224.latestCheckpoint();
    }

    function length() external view returns (uint) {
        return _trace224.length();
    }
}

contract MockCheckpointsTrace160 {
    using Checkpoints for Checkpoints.Trace160;

    Checkpoints.Trace160 _trace160;

    function push(
        uint96 key,
        uint160 value
    ) external returns (uint160, uint160){
        return _trace160.push(key, value);
    }

    function lowerLookup(uint96 key) external view returns (uint160){
        return _trace160.lowerLookup(key);
    }

    function upperLookup(uint96 key) external view returns (uint160) {
        return _trace160.upperLookup(key);
    }

    function latest() external view returns (uint160) {
        return _trace160.latest();
    }

    function latestCheckpoint() external view returns (
        bool exists,
        uint96 _key,
        uint160 _value
    ){
        return _trace160.latestCheckpoint();
    }

    function length() external view returns (uint) {
        return _trace160.length();
    }
}

全部foundry测试合约：

Github: https://github.com/RevelationOfTuring/foundry-openzeppelin-contracts/blob/master/test/utils/Checkpoints.t.sol

2. 代码精读

Checkpoints库中提供了History、Trace224和Trace160三种存储记录的结构体。各个结构体自成体系并提供每种体系下的读修改写的库方法。

2.1 History体系

    // 定义History结构体，里面包含了不同时间点（区块高度）上的记录值
    struct History {
        Checkpoint[] _checkpoints;
    }

    struct Checkpoint {
        // uint32+uint224=uint256，合起来占1个slot
        // 区块号
        uint32 _blockNumber;
        // 记录值
        uint224 _value;
    }

2.1.1 push(History storage self, uint256 value) && push(History storage self, function(uint256, uint256) view returns (uint256) op, uint256 delta)

• push(History storage self, uint256 value) ：向History中添加记录值value，时间戳为当前的区块高度。返回值为前一条记录值和本次添加的记录值；
• push(History storage self, function(uint256, uint256) view returns (uint256) op, uint256 delta)：向历史记录中添加新的记录值。新的记录值为op(latest(self), delta)的返回值，其中op的函数类型为function(uint256, uint256) view returns (uint256)。

    function push(History storage self, uint256 value) internal returns (uint256, uint256) {
        // 调用_insert()函数，添加的key和value都是被安全类型转换得到的（如果存在溢出会revert）
        return _insert(self._checkpoints, SafeCast.toUint32(block.number), SafeCast.toUint224(value));
    }

    function push(
        History storage self,
        function(uint256, uint256) view returns (uint256) op,
        uint256 delta
    ) internal returns (uint256, uint256) {
        // latest(self)为总记录中最近的记录值。
        return push(self, op(latest(self), delta));
    }

    // 将新的键值对（区块高度,记录值）添加进有序的记录数组中
    // 注：如果传入的key跟最近的记录Checkpoint中的时间高度一样，则更新最近的记录Checkpoint中的值。如果传入的key跟最近的记录Checkpoint中的时间高度不一样，则在全部记录中新增一个Checkpoint。
    function _insert(
        Checkpoint[] storage self,
        uint32 key,
        uint224 value
    ) private returns (uint224, uint224) {
        // pos为当前记录数组的长度
        uint256 pos = self.length;

        if (pos > 0) {
            // 如果当前记录数组中存在过去的记录值，直接在内存中复制记录数组中最后一个Checkpoint（即时间点离现在最近的）
            Checkpoint memory last = _unsafeAccess(self, pos - 1);

            // 要求本次添加的键值对的区块高度>=历史数组中最近一条记录的区块高度
            // 这样才能保证本记录数组的数据是按照时间升序排列
            require(last._blockNumber <= key, "Checkpoint: invalid key");

            if (last._blockNumber == key) {
                // 如果输入的区块高度与最后一个Checkpoint的区块高度一致，则更新最后一个Checkpoint里的记录值
                _unsafeAccess(self, pos - 1)._value = value;
            } else {
                // 如果输入的区块高度与最后一个Checkpoint的区块高度不一致，则在记录数组中新增一个Checkpoint
                self.push(Checkpoint({_blockNumber: key, _value: value}));
            }
            // 返回last中的记录值和本次新增（或更新）的记录值
            return (last._value, value);
        } else {
            // 如果数组中无任何历史记录，直接将键值对push到数组中
            self.push(Checkpoint({_blockNumber: key, _value: value}));
            // 返回0和本次添加的记录值
            return (0, value);
        }
    }

2.1.2 latest(History storage self) && latestCheckpoint(History storage self) && length(History storage self)

• latest(History storage self)：返回最近的Checkpoint中的记录值。如果没有记录则返回0；
• latestCheckpoint(History storage self)：返回全部历史记录中最近的一个Checkpoint的信息；
• length(History storage self)：返回History中全部记录的Checkpoint数。

    function latest(History storage self) internal view returns (uint224) {
        // 记录总长度
        uint256 pos = self._checkpoints.length;
        // 如果pos等于0，表示没有记录，直接返回0。如果pos存在非0值，直接取pos-1索引的记录值返回
        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
    }

    function latestCheckpoint(History storage self)
        internal
        view
        returns (
            // 如果没有记录返回false，否则返回true
            bool exists,
            // 最近记录的区块高度
            uint32 _blockNumber,
            // 最近记录的记录值
            uint224 _value
        )
    {
        // 记录总长度
        uint256 pos = self._checkpoints.length;
        if (pos == 0) {
            // 如果无记录，则返回false,0,0
            return (false, 0, 0);
        } else {
            // 如果有记录，则将记录中最后一个Checkpoint复制到内存中
            Checkpoint memory ckpt = _unsafeAccess(self._checkpoints, pos - 1);
            // 返回true以及最后一个Checkpoint的区块高度及记录值
            return (true, ckpt._blockNumber, ckpt._value);
        }
    }

    function length(History storage self) internal view returns (uint256) {
        // 返回History中Checkpoint[]的数组长度
        return self._checkpoints.length;
    }

    // 从一个数组中无边界检查地获取索引为pos的元素值。由于没有边界检查，pos的值要在传入时保证不会造成数组越界
    function _unsafeAccess(Checkpoint[] storage self, uint256 pos) private pure returns (Checkpoint storage result) {
        assembly {
            // 将当前Checkpoint[] storage的本位slot号写入偏移量为0的内存中
            // 为什么是偏移量为0的空间？因为solidity的内存模型中，前两个字（即前两个32字节）是专门用于哈希函数的临时空间
            mstore(0, self.slot)
            // keccak256(0, 0x20)计算出storage中的动态数组self的第一个元素的slot号，具体storage动态数组和定长数组的layout细节可参见我之前的博文：https://learnblockchain.cn/article/6111
            // add(keccak256(0, 0x20), pos)得到的是动态数组self中索引为pos的元素的slot号，即返回值result就是对应slot号中存储的值
            // 注：这里不会做数组越界的检查
            result.slot := add(keccak256(0, 0x20), pos)
        }
    }

2.1.3 getAtBlock(History storage self, uint256 blockNumber) && getAtProbablyRecentBlock(History storage self, uint256 blockNumber)

• getAtBlock(History storage self, uint256 blockNumber)：通过区块号查询对应时间点的记录值。如果输入的区块号上没有记录值，那么将返回该区块号之前最近时间点的记录值。如果输入区块号之前都没有记录值，将返回0；
• getAtProbablyRecentBlock(History storage self, uint256 blockNumber)：通过区块号查询对应时间点的记录值。如果输入的区块号上没有记录值，那么将返回该区块号之前最近时间点的记录值。如果输入区块号之前都没有记录值，将返回0。 具体里面的查找函数照比前面的二分查找_upperBinaryLookup()做了一些算法上的优化：即如果记录长度>5，则不是在[0,len)的范围内做二分法查找，而是在[0,len-sqrt(len))或[len-sqrt(len)+1,len)范围中做二分查找。

    function getAtBlock(History storage self, uint256 blockNumber) internal view returns (uint256) {
        // 要求输入的区块号小于当前区块链上的区块高度
        require(blockNumber < block.number, "Checkpoints: block not yet mined");
        // 待查询区块号从uint256转换成uint32，存在溢出检查
        uint32 key = SafeCast.toUint32(blockNumber);
    // 获取History中所有的记录值数
        uint256 len = self._checkpoints.length;
        // 在所有记录的全量范围里找到区块号大于传入区块号blockNumber的第一条记录的索引pos
        uint256 pos = _upperBinaryLookup(self._checkpoints, key, 0, len);
        // 如果pos等于0，表示所有记录中的区块号都大于输入的blockNumber，直接返回0。如果pos存在非0值，表示所有记录中存在区块号小于等于输入的blockNumber的记录，直接取pos-1索引的记录值返回
        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
    }

    function getAtProbablyRecentBlock(History storage self, uint256 blockNumber) internal view returns (uint256) {
        // 要求输入的区块号小于当前区块链上的区块高度
        require(blockNumber < block.number, "Checkpoints: block not yet mined");
        // 待查询区块号从uint256转换成uint32，存在溢出检查
        uint32 key = SafeCast.toUint32(blockNumber);
    // 获取History中所有的记录值数
        uint256 len = self._checkpoints.length;
    // 设置查找边界，low为0，high为所有的记录值数
        uint256 low = 0;
        uint256 high = len;
        if (len > 5) {
            // 如果History中所有的记录值数大于5，mid为len-len的平方根（向下取整）
            uint256 mid = len - Math.sqrt(len);
            if (key < _unsafeAccess(self._checkpoints, mid)._blockNumber) {
                // 如果索引为mid的Checkpoint的区块号>key，则更新high为mid
                high = mid;
            } else {
                // 如果索引为mid的Checkpoint的区块号<=key，则更新low为mid+1
                low = mid + 1;
            }
        }
    // 从当下被调整过的[low,high)范围内进行二分查找
        uint256 pos = _upperBinaryLookup(self._checkpoints, key, low, high);
    // 如果pos等于0，表示所有[low,high)的记录中的区块号都大于输入的blockNumber，直接返回0。如果pos存在非0值，表示所有[low,high)的记录中存在区块号小于等于输入的blockNumber的记录，直接取pos-1索引的记录值返回
        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
    }

    // Checkpoint[] storage self中，通过二分法查找出blockNumber在[low,high)的范围中记录的区块号大于目标区块号key的第一条记录的索引值。如果不存在这样的记录值，则返回值为high。
    // 注： 传入的high不可以大于数组self的长度
    function _upperBinaryLookup(
        Checkpoint[] storage self,
        uint32 key,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        // 跳出循环条件：low>=high
        while (low < high) {
            // mid为low和high的均值
            uint256 mid = Math.average(low, high);
            if (_unsafeAccess(self, mid)._blockNumber > key) {
                // 如果索引为mid的Checkpoint的区块号>key，则更新high为mid
                high = mid;
            } else {
                // 如果索引为mid的Checkpoint的区块号<=key，则更新low为mid+1
                low = mid + 1;
            }
        }
        // 跳出循环，返回high
        return high;
    }

    // Checkpoint[] storage self中，通过二分法查找出blockNumber在[low,high)的范围中记录的区块号大于等于目标区块号key的第一条记录的索引值。如果不存在这样的记录值，则返回值为high。
    // 注： 传入的high不可以大于数组self的长度
    function _lowerBinaryLookup(
        Checkpoint[] storage self,
        uint32 key,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        // 跳出循环条件：low>=high
        while (low < high) {
            // mid为low和high的均值
            uint256 mid = Math.average(low, high);
            if (_unsafeAccess(self, mid)._blockNumber < key) {
                // 如果索引为mid的Checkpoint的区块号<key，则更新low为mid+1
                low = mid + 1;
            } else {
                // 如果索引为mid的Checkpoint的区块号>=key，则更新high为mid
                high = mid;
            }
        }
        // 跳出循环，返回high
        return high;
    }

2.1.4 foundry代码验证

contract CheckpointsTest is Test {
    MockCheckpointsHistory mch = new MockCheckpointsHistory();

    function test_CheckpointsHistory() external {
        assertEq(mch.length(), 0);
        (bool exists,uint32 blockNumber,uint224 value) = mch.latestCheckpoint();
        assertFalse(exists);
        assertEq(blockNumber, 0);
        assertEq(value, 0);
        assertEq(mch.latest(), 0);

        // push on block number 1
        vm.roll(1);
        (uint latestValue,uint newValue) = mch.push(11);
        assertEq(latestValue, 0);
        assertEq(newValue, 11);
        assertEq(mch.length(), 1);
        (exists, blockNumber, value) = mch.latestCheckpoint();
        assertTrue(exists);
        assertEq(blockNumber, 1);
        assertEq(value, 11);
        assertEq(mch.latest(), newValue);

        // push on block number 2
        vm.roll(2);
        (latestValue, newValue) = mch.push(22);
        assertEq(latestValue, 11);
        assertEq(newValue, 22);
        assertEq(mch.length(), 2);
        (exists, blockNumber, value) = mch.latestCheckpoint();
        assertTrue(exists);
        assertEq(blockNumber, 2);
        assertEq(value, 22);
        assertEq(mch.latest(), newValue);

        // update value when push on block number 2 again
        (latestValue, newValue) = mch.push(33);
        // value before update
        assertEq(latestValue, 22);
        // value after update
        assertEq(newValue, 33);
        // total length no change
        assertEq(mch.length(), 2);
        (exists, blockNumber, value) = mch.latestCheckpoint();
        assertTrue(exists);
        assertEq(blockNumber, 2);
        assertEq(value, 33);
        assertEq(mch.latest(), newValue);

        // push on block number 3
        vm.roll(3);
        (latestValue, newValue) = mch.push(44);
        assertEq(latestValue, 33);
        assertEq(newValue, 44);
        assertEq(mch.length(), 3);
        (exists, blockNumber, value) = mch.latestCheckpoint();
        assertTrue(exists);
        assertEq(blockNumber, 3);
        assertEq(value, 44);
        assertEq(mch.latest(), newValue);

        // push with customized op function on a new block number
        vm.roll(4);
        (latestValue, newValue) = mch.pushWithOp(55);
        assertEq(latestValue, 44);
        // 44(latest)+55(delta)
        assertEq(newValue, 99);
        assertEq(mch.length(), 4);
        (exists, blockNumber, value) = mch.latestCheckpoint();
        assertTrue(exists);
        assertEq(blockNumber, 4);
        assertEq(value, 99);
        assertEq(mch.latest(), newValue);

        // push with customized op function on an existed block number
        (latestValue, newValue) = mch.pushWithOp(11);
        assertEq(latestValue, 99);
        // 99(latest)+11(delta)
        assertEq(newValue, 110);
        assertEq(mch.length(), 4);
        (exists, blockNumber, value) = mch.latestCheckpoint();
        assertTrue(exists);
        assertEq(blockNumber, 4);
        assertEq(value, 110);
        assertEq(mch.latest(), newValue);

        // push more
        vm.roll(10);
        mch.push(100);
        vm.roll(20);
        mch.push(101);
        vm.roll(25);
        mch.push(102);
        assertEq(mch.length(), 7);

        // history now:
        // 11(1)、33(2)、44(3)、110(4)、100(10)、101(20)、102(25)
        uint[7] memory values = [uint(11), 33, 44, 110, 100, 101, 102];
        uint[7] memory blockNumbers = [uint(1), 2, 3, 4, 10, 20, 25];

        // test getAtBlock
        // revert if the target block number not < the current block number of chain
        vm.expectRevert("Checkpoints: block not yet mined");
        mch.getAtBlock(25);

        vm.roll(25 + 1);
        for (uint i = 0; i < 7; ++i) {
            assertEq(mch.getAtBlock(blockNumbers[i]), values[i]);
        }

        // test getAtProbablyRecentBlock
        // revert if the target block number not < the current block number of chain
        vm.expectRevert("Checkpoints: block not yet mined");
        mch.getAtProbablyRecentBlock(26);
        for (uint i = 0; i < 7; ++i) {
            assertEq(mch.getAtProbablyRecentBlock(blockNumbers[i]), values[i]);
        }
    }
}

2.2 Trace224体系

    // 总记录，里面包含记录的动态数组_checkpoints
    struct Trace224 {
        Checkpoint224[] _checkpoints;
    }

    // 记录的结构体，具有uint32的key和uint224的value
    struct Checkpoint224 {
        // uint32+uint224=uint256，合起来占1个slot
        uint32 _key;
        uint224 _value;
    }

2.2.1 push(Trace224 storage self, uint32 key, uint224 value)

向Trace224中添加新的记录键值对(key,value)。返回值为前一条记录值和本次添加的记录值。

    function push(
        Trace224 storage self,
        uint32 key,
        uint224 value
    ) internal returns (uint224, uint224) {
        // 调用_insert()函数，添加的key和value都是被安全类型转换得到的（如果存在溢出会revert）
        return _insert(self._checkpoints, key, value);
    }

    // 将新的键值对(key,记录值)添加进有序的记录数组中
    // 注：如果传入的key跟最近的记录Checkpoint224._key一样，则更新最近的记录Checkpoint224中的值。如果传入的key跟最近的记录Checkpoint224._key不一样，则在全部记录中新增一个Checkpoint224。
    function _insert(
        Checkpoint224[] storage self,
        uint32 key,
        uint224 value
    ) private returns (uint224, uint224) {
        // pos为当前记录数组的长度
        uint256 pos = self.length;

        if (pos > 0) {
            // 如果当前记录数组中存在过去的记录值，直接在内存中复制记录数组中最后一个Checkpoint224
            Checkpoint224 memory last = _unsafeAccess(self, pos - 1);

            // 要求本次添加的键值对的key>=历史数组中最近一条记录的key
            // 这样才能保证本记录数组的数据是按照key的升序排列
            require(last._key <= key, "Checkpoint: invalid key");

            if (last._key == key) {
                // 如果输入的key与最后一个Checkpoint224._key一致，则更新最后一个Checkpoint224里的记录值
                _unsafeAccess(self, pos - 1)._value = value;
            } else {
                // 如果输入的key与最后一个Checkpoint224._key不一致，则在记录数组中新增一个Checkpoint224
                self.push(Checkpoint224({_key: key, _value: value}));
            }
            // 返回last中的记录值和本次新增（或更新）的记录值
            return (last._value, value);
        } else {
            // 如果数组中无任何历史记录，直接将键值对push到数组中
            self.push(Checkpoint224({_key: key, _value: value}));
            // 返回0和本次添加的记录值
            return (0, value);
        }
    }

2.2.2 latest(Trace224 storage self) && latestCheckpoint(Trace224 storage self) && length(Trace224 storage self)

• latest(Trace224 storage self)：返回最近的Checkpoint224中的记录值。如果没有记录则返回0；
• latestCheckpoint(Trace224 storage self)：返回Trace224全部历史记录中最近的一个Checkpoint的信息；
• length(Trace224 storage self)：返回Trace224中全部记录的Checkpoint224的数量。

    function latest(Trace224 storage self) internal view returns (uint224) {
        // 记录总长度
        uint256 pos = self._checkpoints.length;
        // 如果pos等于0，表示没有记录，直接返回0。如果pos存在非0值，直接取pos-1索引的记录值返回
        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
    }

    function latestCheckpoint(Trace224 storage self)
        internal
        view
        returns (
            // 如果没有记录返回false，否则返回true
            bool exists,
            // 最近记录的key
            uint32 _key,
            // 最近记录的记录值
            uint224 _value
        )
    {
        // 记录总长度
        uint256 pos = self._checkpoints.length;
        if (pos == 0) {
            // 如果无记录，则返回false,0,0
            return (false, 0, 0);
        } else {
            // 如果有记录，则将记录中最后一个Checkpoint224复制到内存中
            Checkpoint224 memory ckpt = _unsafeAccess(self._checkpoints, pos - 1);
            // 返回true以及最后一个Checkpoint224的key及记录值
            return (true, ckpt._key, ckpt._value);
        }
    }

    function length(Trace224 storage self) internal view returns (uint256) {
        // 返回Trace224中Checkpoint224[]的数组长度
        return self._checkpoints.length;
    }

    // 从Checkpoint224[]数组中无边界检查地获取索引为pos的元素值。由于没有边界检查，pos的值要在传入时保证不会造成数组越界
    function _unsafeAccess(Checkpoint224[] storage self, uint256 pos)
        private
        pure
        returns (Checkpoint224 storage result)
    {
        assembly {
            // 将当前Checkpoint224[] storage的本位slot号写入偏移量为0的内存中
            // 为什么是偏移量为0的空间？因为solidity的内存模型中，前两个字（即前两个32字节）是专门用于哈希函数的临时空间
            mstore(0, self.slot)
            // keccak256(0, 0x20)计算出storage中的动态数组self的第一个元素的slot号，具体storage动态数组和定长数组的layout细节可参见我之前的博文：https://learnblockchain.cn/article/6111
            // add(keccak256(0, 0x20), pos)得到的是动态数组self中索引为pos的元素的slot号，即返回值result就是对应slot号中存储的值
            // 注：这里不会做数组越界的检查
            result.slot := add(keccak256(0, 0x20), pos)
        }
    }

2.2.3 lowerLookup(Trace224 storage self, uint32 key) && upperLookup(Trace224 storage self, uint32 key)

• lowerLookup(Trace224 storage self, uint32 key)：返回Trace224所有记录中key>=目标key的最近的记录值。如果不存在这样的记录，返回0。注：传入的high不可以大于总记录的长度；
• upperLookup(Trace224 storage self, uint32 key)：返回Trace224所有记录中key<=目标key的最近的记录值。如果不存在这样的记录，返回0。注：传入的high不可以大于总记录的长度。

    function lowerLookup(Trace224 storage self, uint32 key) internal view returns (uint224) {
        // 记录总长度
        uint256 len = self._checkpoints.length;
        // 通过_lowerBinaryLookup方法在[0,len)的key的范围中找到key大于等于目标key的第一条记录的索引值
        uint256 pos = _lowerBinaryLookup(self._checkpoints, key, 0, len);
        // 如果pos为0表示不存在这样的记录，返回0。否则返回索引为pos的记录中的记录值
        return pos == len ? 0 : _unsafeAccess(self._checkpoints, pos)._value;
    }

    function upperLookup(Trace224 storage self, uint32 key) internal view returns (uint224) {
        // 记录总长度
        uint256 len = self._checkpoints.length;
        // 通过_upperBinaryLookup方法在[0,len)的key的范围中找到key大于目标key的第一条记录的索引值
        uint256 pos = _upperBinaryLookup(self._checkpoints, key, 0, len);
        // 如果pos为0表示不存在这样的记录，返回0。否则返回索引为pos-1的记录中的记录值
        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
    }

     // Checkpoint224[] storage self中，通过二分法查找出key在[low,high)的范围中，记录的key大于目标key的第一条记录的索引值。如果不存在这样的记录值，则返回值为high。
    // 注：传入的high不可以大于数组self的长度
    function _upperBinaryLookup(
        Checkpoint224[] storage self,
        uint32 key,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        // 跳出循环条件：low>=high
        while (low < high) {
            // mid为low和high的均值
            uint256 mid = Math.average(low, high);
            if (_unsafeAccess(self, mid)._key > key) {
                // 如果索引为mid的Checkpoint224._key>key，则更新high为mid
                high = mid;
            } else {
                // 如果索引为mid的Checkpoint224._key<=key，则更新low为mid+1
                low = mid + 1;
            }
        }
        // 跳出循环，返回high
        return high;
    }

     // Checkpoint224[] storage self中，通过二分法查找出key在[low,high)的范围中，记录的key大于或等于目标key的第一条记录的索引值。如果不存在这样的记录值，则返回值为high。
    // 注： 传入的high不可以大于数组self的长度
    function _lowerBinaryLookup(
        Checkpoint224[] storage self,
        uint32 key,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        // 跳出循环条件：low>=high
        while (low < high) {
            // mid为low和high的均值
            uint256 mid = Math.average(low, high);
            if (_unsafeAccess(self, mid)._key < key) {
                // 如果索引为mid的Checkpoint224._key<key，则更新low为mid+1
                low = mid + 1;
            } else {
                // 如果索引为mid的Checkpoint224._key>=key，则更新high为mid
                high = mid;
            }
        }
        // 跳出循环，返回high
        return high;
    }

2.2.4 foundry代码验证

contract CheckpointsTest is Test {
    MockCheckpointsTrace224 mct224 = new MockCheckpointsTrace224();

    function test_CheckpointsTrace224() external {
        assertEq(mct224.length(), 0);
        (bool exists,uint32 key,uint224 value) = mct224.latestCheckpoint();
        assertFalse(exists);
        assertEq(key, 0);
        assertEq(value, 0);
        assertEq(mct224.latest(), 0);

        // push on key 1
        (uint224 latestValue,uint224 newValue) = mct224.push(1, 10);
        assertEq(latestValue, 0);
        assertEq(newValue, 10);
        assertEq(mct224.length(), 1);
        (exists, key, value) = mct224.latestCheckpoint();
        assertTrue(exists);
        assertEq(key, 1);
        assertEq(value, 10);
        assertEq(mct224.latest(), newValue);

        // push on key 2
        (latestValue, newValue) = mct224.push(2, 20);
        assertEq(latestValue, 10);
        assertEq(newValue, 20);
        assertEq(mct224.length(), 2);
        (exists, key, value) = mct224.latestCheckpoint();
        assertTrue(exists);
        assertEq(key, 2);
        assertEq(value, 20);
        assertEq(mct224.latest(), newValue);

        // update value on key 2
        (latestValue, newValue) = mct224.push(2, 30);
        // value before update
        assertEq(latestValue, 20);
        // value after update
        assertEq(newValue, 30);
        // total length no change
        assertEq(mct224.length(), 2);
        (exists, key, value) = mct224.latestCheckpoint();
        assertTrue(exists);
        assertEq(key, 2);
        assertEq(value, 30);
        assertEq(mct224.latest(), newValue);

        // revert if the key to push is < latest key
        vm.expectRevert("Checkpoint: invalid key");
        mct224.push(2 - 1, 1);
        // push more
        mct224.push(3, 40);
        mct224.push(4, 50);
        mct224.push(5, 60);
        mct224.push(6, 70);
        assertEq(mct224.length(), 6);

        // Trace224 now:
        // 10(1)、30(2)、40(3)、50(4)、60(5)、70(6)
        // lowerLookup():
        // return the value in the oldest checkpoint with key greater or equal than the search key
        assertEq(mct224.lowerLookup(0), 10);
        assertEq(mct224.lowerLookup(1), 10);
        assertEq(mct224.lowerLookup(2), 30);
        assertEq(mct224.lowerLookup(3), 40);
        assertEq(mct224.lowerLookup(4), 50);
        assertEq(mct224.lowerLookup(5), 60);
        assertEq(mct224.lowerLookup(6), 70);
        assertEq(mct224.lowerLookup(7), 0);

        // upperLookup():
        // return the value in the most recent checkpoint with key lower or equal than the search key
        assertEq(mct224.upperLookup(0), 0);
        assertEq(mct224.upperLookup(1), 10);
        assertEq(mct224.upperLookup(2), 30);
        assertEq(mct224.upperLookup(3), 40);
        assertEq(mct224.upperLookup(4), 50);
        assertEq(mct224.upperLookup(5), 60);
        assertEq(mct224.upperLookup(6), 70);
        assertEq(mct224.upperLookup(7), 70);
    }
}

2.3 Trace160体系

    // 总记录，里面包含记录的动态数组_checkpoints
    struct Trace160 {
        Checkpoint160[] _checkpoints;
    }

    // 记录的结构体，具有uint96的key和uint160的value
    struct Checkpoint160 {
        // uint96+uint160=uint256，合起来占1个slot
        uint96 _key;
        uint160 _value;
    }

2.3.1 push(Trace160 storage self, uint96 key, uint160 value)

向Trace160中添加新的记录键值对(key,value)。返回值为前一条记录值和本次添加的记录值。

    function push(
        Trace160 storage self,
        uint96 key,
        uint160 value
    ) internal returns (uint160, uint160) {
        // 调用_insert()函数，添加的key和value都是被安全类型转换得到的（如果存在溢出会revert）
        return _insert(self._checkpoints, key, value);
    }

    // 将新的键值对(key,记录值)添加进有序的记录数组中
    // 注：如果传入的key跟最近的记录Checkpoint160._key一样，则更新最近的记录Checkpoint160中的值。如果传入的key跟最近的记录Checkpoint160._key不一样，则在全部记录中新增一个Checkpoint160。
    function _insert(
        Checkpoint160[] storage self,
        uint96 key,
        uint160 value
    ) private returns (uint160, uint160) {
        // pos为当前记录数组的长度
        uint256 pos = self.length;

        if (pos > 0) {
            // 如果当前记录数组中存在过去的记录值，直接在内存中复制记录数组中最后一个Checkpoint160
            Checkpoint160 memory last = _unsafeAccess(self, pos - 1);

            // 要求本次添加的键值对的key>=历史数组中最近一条记录的key
            // 这样才能保证本记录数组的数据是按照key的升序排列
            require(last._key <= key, "Checkpoint: invalid key");

            if (last._key == key) {
                // 如果输入的key与最后一个Checkpoint160._key一致，则更新最后一个Checkpoint160里的记录值
                _unsafeAccess(self, pos - 1)._value = value;
            } else {
                // 如果输入的key与最后一个Checkpoint160._key不一致，则在记录数组中新增一个Checkpoint160
                self.push(Checkpoint160({_key: key, _value: value}));
            }
            // 返回last中的记录值和本次新增（或更新）的记录值
            return (last._value, value);
        } else {
            // 如果数组中无任何历史记录，直接将键值对push到数组中
            self.push(Checkpoint160({_key: key, _value: value}));
            // 返回0和本次添加的记录值
            return (0, value);
        }
    }

2.3.2 latest(Trace160 storage self) && latestCheckpoint(Trace160 storage self) && length(Trace160 storage self)

• latest(Trace160 storage self)：返回最近的Checkpoint160中的记录值。如果没有记录则返回0；
• latestCheckpoint(Trace160 storage self)：返回Trace160全部历史记录中最近的一个Checkpoint的信息；
• length(Trace160 storage self)：返回Trace160中全部记录的Checkpoint160的数量。

    function latest(Trace160 storage self) internal view returns (uint160) {
        // 记录总长度
        uint256 pos = self._checkpoints.length;
        // 如果pos等于0，表示没有记录，直接返回0。如果pos存在非0值，直接取pos-1索引的记录值返回
        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
    }

    function latestCheckpoint(Trace160 storage self)
        internal
        view
        returns (
            // 如果没有记录返回false，否则返回true
            bool exists,
            // 最近记录的key
            uint96 _key,
            // 最近记录的记录值
            uint160 _value
        )
    {
        // 记录总长度
        uint256 pos = self._checkpoints.length;
        if (pos == 0) {
            // 如果无记录，则返回false,0,0
            return (false, 0, 0);
        } else {
            // 如果有记录，则将记录中最后一个Checkpoint160复制到内存中
            Checkpoint160 memory ckpt = _unsafeAccess(self._checkpoints, pos - 1);
            // 返回true以及最后一个Checkpoint160的key及记录值
            return (true, ckpt._key, ckpt._value);
        }
    }

    function length(Trace160 storage self) internal view returns (uint256) {
        // 返回Trace160中Checkpoint160[]的数组长度
        return self._checkpoints.length;
    }

    // 从Checkpoint160[]数组中无边界检查地获取索引为pos的元素值。由于没有边界检查，pos的值要在传入时保证不会造成数组越界
    function _unsafeAccess(Checkpoint160[] storage self, uint256 pos)
        private
        pure
        returns (Checkpoint160 storage result)
    {
        assembly {
            // 将Checkpoint160[] storage的本位slot号写入偏移量为0的内存中
            // 为什么是偏移量为0的空间？因为solidity的内存模型中，前两个字（即前两个32字节）是专门用于哈希函数的临时空间
            mstore(0, self.slot)
            // keccak256(0, 0x20)计算出storage中的动态数组self的第一个元素的slot号，具体storage动态数组和定长数组的layout细节可参见我之前的博文：https://learnblockchain.cn/article/6111
            // add(keccak256(0, 0x20), pos)得到的是动态数组self中索引为pos的元素的slot号，即返回值result就是对应slot号中存储的值
            // 注：这里不会做数组越界的检查
            result.slot := add(keccak256(0, 0x20), pos)
        }
    }

2.3.3 lowerLookup(Trace160 storage self, uint96 key) && upperLookup(Trace160 storage self, uint96 key)

• lowerLookup(Trace160 storage self, uint96 key)：返回Trace160所有记录中key>=目标key的最近的记录值。如果不存在这样的记录，返回0。注：传入的high不可以大于总记录的长度；
• upperLookup(Trace160 storage self, uint96 key)：返回Trace160所有记录中key<=目标key的最近的记录值。如果不存在这样的记录，返回0。注：传入的high不可以大于总记录的长度。

    function lowerLookup(Trace160 storage self, uint96 key) internal view returns (uint160) {
        // 记录总长度
        uint256 len = self._checkpoints.length;
        // 通过_lowerBinaryLookup方法在[0,len)的key的范围中找到key大于等于目标key的第一条记录的索引值
        uint256 pos = _lowerBinaryLookup(self._checkpoints, key, 0, len);
        // 如果pos为0表示不存在这样的记录，返回0。否则返回索引为pos的记录中的记录值
        return pos == len ? 0 : _unsafeAccess(self._checkpoints, pos)._value;
    }

    function upperLookup(Trace160 storage self, uint96 key) internal view returns (uint160) {
        // 记录总长度
        uint256 len = self._checkpoints.length;
        // 通过_upperBinaryLookup方法在[0,len)的key的范围中找到key大于目标key的第一条记录的索引值
        uint256 pos = _upperBinaryLookup(self._checkpoints, key, 0, len);
        // 如果pos为0表示不存在这样的记录，返回0。否则返回索引为pos-1的记录中的记录值
        return pos == 0 ? 0 : _unsafeAccess(self._checkpoints, pos - 1)._value;
    }

    // Checkpoint160[] storage self中，通过二分法查找出key在[low,high)的范围中，记录的key大于目标key的第一条记录的索引值。如果不存在这样的记录值，则返回值为high。
    // 注：传入的high不可以大于数组self的长度
    function _upperBinaryLookup(
        Checkpoint160[] storage self,
        uint96 key,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        // 跳出循环条件：low>=high
        while (low < high) {
            // mid为low和high的均值
            uint256 mid = Math.average(low, high);
            if (_unsafeAccess(self, mid)._key > key) {
                // 如果索引为mid的Checkpoint160._key>key，则更新high为mid
                high = mid;
            } else {
                // 如果索引为mid的Checkpoint160._key<=key，则更新low为mid+1
                low = mid + 1;
            }
        }
        // 跳出循环，返回high
        return high;
    }

    // Checkpoint160[] storage self中，通过二分法查找出key在[low,high)的范围中，记录的key大于或等于目标key的第一条记录的索引值。如果不存在这样的记录值，则返回值为high。
    // 注： 传入的high不可以大于数组self的长度
    function _lowerBinaryLookup(
        Checkpoint160[] storage self,
        uint96 key,
        uint256 low,
        uint256 high
    ) private view returns (uint256) {
        // 跳出循环条件：low>=high
        while (low < high) {
            // mid为low和high的均值
            uint256 mid = Math.average(low, high);
            if (_unsafeAccess(self, mid)._key < key) {
                // 如果索引为mid的Checkpoint160._key<key，则更新low为mid+1
                low = mid + 1;
            } else {
                // 如果索引为mid的Checkpoint160._key>=key，则更新high为mid
                high = mid;
            }
        }
        return high;
    }

2.3.4 foundry代码验证

contract CheckpointsTest is Test {
    MockCheckpointsTrace160 mct160 = new MockCheckpointsTrace160();

    function test_CheckpointsTrace160() external {
        assertEq(mct160.length(), 0);
        (bool exists,uint96 key,uint160 value) = mct160.latestCheckpoint();
        assertFalse(exists);
        assertEq(key, 0);
        assertEq(value, 0);
        assertEq(mct160.latest(), 0);

        // push on key 1
        (uint160 latestValue,uint160 newValue) = mct160.push(1, 10);
        assertEq(latestValue, 0);
        assertEq(newValue, 10);
        assertEq(mct160.length(), 1);
        (exists, key, value) = mct160.latestCheckpoint();
        assertTrue(exists);
        assertEq(key, 1);
        assertEq(value, 10);
        assertEq(mct160.latest(), newValue);

        // push on key 2
        (latestValue, newValue) = mct160.push(2, 20);
        assertEq(latestValue, 10);
        assertEq(newValue, 20);
        assertEq(mct160.length(), 2);
        (exists, key, value) = mct160.latestCheckpoint();
        assertTrue(exists);
        assertEq(key, 2);
        assertEq(value, 20);
        assertEq(mct160.latest(), newValue);

        // update value on key 2
        (latestValue, newValue) = mct160.push(2, 30);
        // value before update
        assertEq(latestValue, 20);
        // value after update
        assertEq(newValue, 30);
        // total length no change
        assertEq(mct160.length(), 2);
        (exists, key, value) = mct160.latestCheckpoint();
        assertTrue(exists);
        assertEq(key, 2);
        assertEq(value, 30);
        assertEq(mct160.latest(), newValue);

        // revert if the key to push is < latest key
        vm.expectRevert("Checkpoint: invalid key");
        mct160.push(2 - 1, 1);
        // push more
        mct160.push(3, 40);
        mct160.push(4, 50);
        mct160.push(5, 60);
        mct160.push(6, 70);
        assertEq(mct160.length(), 6);

        // Trace160 now:
        // 10(1)、30(2)、40(3)、50(4)、60(5)、70(6)
        // lowerLookup():
        // return the value in the oldest checkpoint with key greater or equal than the search key
        assertEq(mct160.lowerLookup(0), 10);
        assertEq(mct160.lowerLookup(1), 10);
        assertEq(mct160.lowerLookup(2), 30);
        assertEq(mct160.lowerLookup(3), 40);
        assertEq(mct160.lowerLookup(4), 50);
        assertEq(mct160.lowerLookup(5), 60);
        assertEq(mct160.lowerLookup(6), 70);
        assertEq(mct160.lowerLookup(7), 0);

        // upperLookup():
        // return the value in the most recent checkpoint with key lower or equal than the search key
        assertEq(mct160.upperLookup(0), 0);
        assertEq(mct160.upperLookup(1), 10);
        assertEq(mct160.upperLookup(2), 30);
        assertEq(mct160.upperLookup(3), 40);
        assertEq(mct160.upperLookup(4), 50);
        assertEq(mct160.upperLookup(5), 60);
        assertEq(mct160.upperLookup(6), 70);
        assertEq(mct160.upperLookup(7), 70);
    }
}

ps:\ 本人热爱图灵，热爱中本聪，热爱V神。 以下是我个人的公众号，如果有技术问题可以关注我的公众号来跟我交流。 同时我也会在这个公众号上每周更新我的原创文章，喜欢的小伙伴或者老伙计可以支持一下！ 如果需要转发，麻烦注明作者。十分感谢！

公众号名称：后现代泼痞浪漫主义奠基人