Michael.W基于Foundry精读Openzeppelin第18期——DoubleEndedQueue.sol

0. 版本

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

0.1 DoubleEndedQueue.sol

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

DoubleEndedQueue库提供了双向队列的数据结构及对应操作库函数，提供了队头或队尾插入及弹出元素值等逻辑功能。

本库采用优化过的storage存储且所有操作的时间复杂度都是O(1)。特别要注意的是库中的clear操作仅仅将队头和队尾指针清零，而之前队列中的元素值依然留存在storage中。

1. 目标合约

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

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

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

import "openzeppelin-contracts/contracts/utils/structs/DoubleEndedQueue.sol";

contract MockDoubleEndedQueue {
    using DoubleEndedQueue for DoubleEndedQueue.Bytes32Deque;

    DoubleEndedQueue.Bytes32Deque _deque;

    function pushBack(bytes32 value) external {
        _deque.pushBack(value);
    }

    function popBack() external returns (bytes32){
        return _deque.popBack();
    }

    function pushFront(bytes32 value) external {
        _deque.pushFront(value);
    }

    function popFront() external returns (bytes32) {
        return _deque.popFront();
    }

    function front() external view returns (bytes32){
        return _deque.front();
    }

    function back() external view returns (bytes32){
        return _deque.back();
    }

    function at(uint index) external view returns (bytes32){
        return _deque.at(index);
    }

    function clear() external {
        _deque.clear();
    }

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

    function empty() external view returns (bool){
        return _deque.empty();
    }
}

全部foundry测试合约：

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

2. 代码精读

2.1 结构体Bytes32Deque

双向队列的内部结构由两个指针和一个存储元素内容的mapping(int128 => bytes32)构成：

    struct Bytes32Deque {
        // 指向队头元素的index
        int128 _begin;
        // 指向队尾下一个元素的index
        int128 _end;
        // 用于存储队列中元素值的mapping
        mapping(int128 => bytes32) _data;
    }

指向队头和队尾的指针值被定义成int128使得队列可以进行安全的头尾双向延展——在队列头部和尾部增添元素时不会出现指针运算溢出的情况。同时，两个int128正好占用一个slot，节约存储。

需要注意的是，队列中的有效元素位于[Bytes32Deque._begin, Bytes32Deque._end)的范围中，也就是说队列第一个元素值为Bytes32Deque._data[Bytes32Deque._begin]，队列最后一个元素值为Bytes32Deque._data[Bytes32Deque._end-1]。

2.2 length(Bytes32Deque storage deque) && empty(Bytes32Deque storage deque)

• length(Bytes32Deque storage deque)：返回处于队列中的元素个数；
• empty(Bytes32Deque storage deque)：判断队列中是否有元素。如果队列中无元素返回true，队列中有元素返回false。

    function length(Bytes32Deque storage deque) internal view returns (uint256) {
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 将队尾指针和队头指针都提升到int256的维度作差，并将结果转成uint256返回
            // 由于前面的各种操作方法都可以严格保证deque._end不会小于deque._begin，此处减法不会发生溢出。并且这里有个前提假设：在该双端队列中最多的元素个数为type(int256).max
            return uint256(int256(deque._end) - int256(deque._begin));
        }
    }

    function empty(Bytes32Deque storage deque) internal view returns (bool) {
        // 如果队尾指针deque._end > 对头指针deque._begin，说明队列中有元素；否则，队列中无元素
        return deque._end <= deque._begin;
    }

2.3 at(Bytes32Deque storage deque, uint256 index)

返回队列中第index+1个元素的值（即索引为index的元素值，队头元素的index为0）。

    function at(Bytes32Deque storage deque, uint256 index) internal view returns (bytes32 value) {
        // idx为队头指针指向的位置索引+相对索引index。由于index为uint256，队头指针为int128，所以通过SafeCast库将二者统一到int256的维度进行加法运算。最后再将结果从int256转换成int128给idx变量，如果这个类型转换的过程产生溢出，SafeCast.toInt128()内部会revert
        int128 idx = SafeCast.toInt128(int256(deque._begin) + SafeCast.toInt256(index));
        // 如果idx的值>=队尾指针，说明输入的index已经越界。抛出OutOfBounds错误
        if (idx >= deque._end) revert OutOfBounds();
        // 如果idx的值<队尾指针，从deque._data中获取对应位置的元素值并返回
        return deque._data[idx];
    }

2.4 clear(Bytes32Deque storage deque)

清空队列。

注：该方法仅仅是将队头和队尾指针清零，原来的deque._data中的元素值并未delete。这种操作不会影响该双端队列的功能，只是无法获得删除已有slot的值而返还的gas。

    function clear(Bytes32Deque storage deque) internal {
        // 队头指针清零
        deque._begin = 0;
        // 队尾指针清零
        deque._end = 0;
    }

foundry代码验证

contract DoubleEndedQueueTest is Test {
    MockDoubleEndedQueue mdeq = new MockDoubleEndedQueue();

    function test_Clear() external {
        for (uint16 i; i < type(uint16).max; ++i) {
            bytes32 content = bytes32(uint(i));
            mdeq.pushFront(content);
            mdeq.pushBack(content);
        }

        assertEq(mdeq.length(), uint(type(uint16).max) * 2);
        assertFalse(mdeq.empty());
        // clear
        mdeq.clear();

        // check
        assertEq(mdeq.length(), 0);
        assertTrue(mdeq.empty());
    }
}

2.5 pushBack(Bytes32Deque storage deque, bytes32 value) && popBack(Bytes32Deque storage deque) && back(Bytes32Deque storage deque)

• pushBack(Bytes32Deque storage deque, bytes32 value)：在队尾添加元素；
• popBack(Bytes32Deque storage deque)：弹出队尾元素。如果队列中无元素，则抛出Empty错误；
• back(Bytes32Deque storage deque)：返回队尾元素值（非弹出）。如果队列中无元素，则抛出Empty错误。

    function pushBack(Bytes32Deque storage deque, bytes32 value) internal {
        // 将deque._end的值复制给内存中的backIndex变量
        int128 backIndex = deque._end;
        // 将以backIndex为key，将元素value添加到内置mapping中（_data）
        deque._data[backIndex] = value;
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 队尾指针deque._end自增1
            deque._end = backIndex + 1;
        }
    }

    function popBack(Bytes32Deque storage deque) internal returns (bytes32 value) {
        // 如果此时队列中无元素，以Empty错误revert
        if (empty(deque)) revert Empty();
        // 声明变量backIndex
        int128 backIndex;
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 将队尾指针前移一个位置（此时指向队尾的最后一个元素），并将位移后的位置存到变量backIndex中
            backIndex = deque._end - 1;
        }
        // 获取此时队列中最后一个元素的值
        value = deque._data[backIndex];
        // 删除队列中最后一个元素的值
        delete deque._data[backIndex];
        // 更新队尾指针，即照比之前前移一个位置
        deque._end = backIndex;
    }

    function back(Bytes32Deque storage deque) internal view returns (bytes32 value) {
        // 如果此时队列中无元素，以Empty错误revert
        if (empty(deque)) revert Empty();
        // 声明变量backIndex
        int128 backIndex;
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // backIndex设置为队尾指针deque._end-1，即指向队列中最后一个元素
            backIndex = deque._end - 1;
        }
        // 返回队列中最后一个元素的值
        return deque._data[backIndex];
    }

foundry代码验证

contract DoubleEndedQueueTest is Test {
    MockDoubleEndedQueue mdeq = new MockDoubleEndedQueue();

    function test_PushBackAndPopBackAndBack() external {
        // empty deque
        assertTrue(mdeq.empty());
        assertEq(mdeq.length(), 0);
        // revert if back()/popBack() from an empty deque
        vm.expectRevert(DoubleEndedQueue.Empty.selector);
        mdeq.back();
        vm.expectRevert(DoubleEndedQueue.Empty.selector);
        mdeq.popBack();

        // push back a,b,c
        mdeq.pushBack('a');
        assertEq(mdeq.length(), 1);
        assertEq(mdeq.back(), 'a');
        mdeq.pushBack('b');
        assertEq(mdeq.length(), 2);
        assertEq(mdeq.back(), 'b');
        mdeq.pushBack('c');
        assertEq(mdeq.length(), 3);
        assertEq(mdeq.back(), 'c');
        assertFalse(mdeq.empty());

        // pop back
        assertEq(mdeq.popBack(), 'c');
        assertEq(mdeq.length(), 2);
        assertEq(mdeq.popBack(), 'b');
        assertEq(mdeq.length(), 1);
        assertEq(mdeq.popBack(), 'a');
        assertEq(mdeq.length(), 0);
        assertTrue(mdeq.empty());
    }
}

2.6 pushFront(Bytes32Deque storage deque, bytes32 value) && popFront(Bytes32Deque storage deque) && front(Bytes32Deque storage deque)

• pushFront(Bytes32Deque storage deque, bytes32 value)：在队头添加元素；
• popFront(Bytes32Deque storage deque)：弹出队头元素。如果队列中无元素，则抛出Empty错误；
• front(Bytes32Deque storage deque)：返回队头元素值（非弹出）。如果队列中无元素，则抛出Empty错误。

    function pushFront(Bytes32Deque storage deque, bytes32 value) internal {
        // 声明变量frontIndex
        int128 frontIndex;
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 将队头指针前移一个位置（此时指向队头第一个元素前面的一个位置），并将位移后的位置存到变量frontIndex中
            frontIndex = deque._begin - 1;
        }
        // 向队头前一个位置添加元素value
        deque._data[frontIndex] = value;
        // 更新队头指针，即照比之前前移一个位置
        deque._begin = frontIndex;
    }

    function popFront(Bytes32Deque storage deque) internal returns (bytes32 value) {
        // 如果此时队列中无元素，以Empty错误revert
        if (empty(deque)) revert Empty();
        // 将队头元素指针复制给变量frontIndex
        int128 frontIndex = deque._begin;
        // 获取队头的元素值
        value = deque._data[frontIndex];
        // 删除队列中第一个元素的值
        delete deque._data[frontIndex];
        // 关闭solidity 0.8的整数运算溢出检查
        unchecked {
            // 更新队头指针，即队头指针自增1
            deque._begin = frontIndex + 1;
        }
    }

    function front(Bytes32Deque storage deque) internal view returns (bytes32 value) {
        // 如果此时队列中无元素，以Empty错误revert
        if (empty(deque)) revert Empty();
        // 将队头元素指针复制给变量frontIndex 
        int128 frontIndex = deque._begin;
        // 返回队列中队头元素指针指向的值
        return deque._data[frontIndex];
    }

foundry代码验证

contract DoubleEndedQueueTest is Test {
    MockDoubleEndedQueue mdeq = new MockDoubleEndedQueue();

    function test_PushFrontAndPopFrontAndFront() external {
        // empty deque
        assertTrue(mdeq.empty());
        assertEq(mdeq.length(), 0);
        // revert if front()/popFront() from an empty deque
        vm.expectRevert(DoubleEndedQueue.Empty.selector);
        mdeq.front();
        vm.expectRevert(DoubleEndedQueue.Empty.selector);
        mdeq.popFront();

        // push front a,b,c
        mdeq.pushFront('a');
        assertEq(mdeq.length(), 1);
        assertEq(mdeq.front(), 'a');
        mdeq.pushFront('b');
        assertEq(mdeq.length(), 2);
        assertEq(mdeq.front(), 'b');
        mdeq.pushFront('c');
        assertEq(mdeq.length(), 3);
        assertEq(mdeq.front(), 'c');
        assertFalse(mdeq.empty());

        // pop back
        assertEq(mdeq.popFront(), 'c');
        assertEq(mdeq.length(), 2);
        assertEq(mdeq.popFront(), 'b');
        assertEq(mdeq.length(), 1);
        assertEq(mdeq.popFront(), 'a');
        assertEq(mdeq.length(), 0);
        assertTrue(mdeq.empty());
    }

    function test_DoubleDirectionsPushAndAt() external {
        mdeq.pushFront('a');
        mdeq.pushBack('b');
        mdeq.pushFront('c');
        mdeq.pushBack('e');
        mdeq.pushBack('f');
        mdeq.pushFront('g');

        // status in deque [g,c,a,b,e,f]
        assertEq(mdeq.length(), 6);
        assertEq(mdeq.at(0), 'g');
        assertEq(mdeq.at(1), 'c');
        assertEq(mdeq.at(2), 'a');
        assertEq(mdeq.at(3), 'b');
        assertEq(mdeq.at(4), 'e');
        assertEq(mdeq.at(5), 'f');
        vm.expectRevert(DoubleEndedQueue.OutOfBounds.selector);
        mdeq.at(5 + 1);

        // pop front and pop back in turn
        assertEq(mdeq.front(), 'g');
        assertEq(mdeq.popFront(), 'g');
        assertEq(mdeq.length(), 5);

        assertEq(mdeq.back(), 'f');
        assertEq(mdeq.popBack(), 'f');
        assertEq(mdeq.length(), 4);

        assertEq(mdeq.front(), 'c');
        assertEq(mdeq.popFront(), 'c');
        assertEq(mdeq.length(), 3);

        assertEq(mdeq.back(), 'e');
        assertEq(mdeq.popBack(), 'e');
        assertEq(mdeq.length(), 2);

        assertEq(mdeq.front(), 'a');
        assertEq(mdeq.popFront(), 'a');
        assertEq(mdeq.length(), 1);

        assertEq(mdeq.back(), 'b');
        assertEq(mdeq.popBack(), 'b');
        assertEq(mdeq.length(), 0);
    }
}

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

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