Michael.W基于Foundry精读Openzeppelin第20期——EnumerableMap.sol
- Michael.W
- 更新于 2023-08-06 01:07
- 阅读 1760
EnumerableMap库提供了Bytes32ToBytes32Map、UintToUintMap、UintToAddressMap、AddressToUintMap和Bytes32ToUintMap五种可迭代的map。每种map都提供了增添/更新键值及查询等操作且所有操作的时间复杂度为O(1)。
0. 版本
[openzeppelin]：v4.8.3，[forge-std]：v1.5.6
0.1 EnumerableMap.sol
EnumerableMap库提供了Bytes32ToBytes32Map、UintToUintMap、UintToAddressMap、AddressToUintMap和Bytes32ToUintMap五种可迭代元素的map，分别适用于(bytes32, bytes32)、(uint256, uint256)、(uint256, address)、(address, uint256)和(bytes32, uint256)类型的键值对。每种map都提供了增添/更新/删除键值对及由键查值等操作。所有操作的时间复杂度均为O(1)。
1. 目标合约
封装EnumerableMap library成为一个可调用合约：
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.0;
import "openzeppelin-contracts/contracts/utils/structs/EnumerableMap.sol";
contract MockBytes32ToBytes32Map {
using EnumerableMap for EnumerableMap.Bytes32ToBytes32Map;
EnumerableMap.Bytes32ToBytes32Map _bytes32ToBytes32Map;
function set(bytes32 key, bytes32 value) external returns (bool) {
return _bytes32ToBytes32Map.set(key, value);
}
function remove(bytes32 key) external returns (bool) {
return _bytes32ToBytes32Map.remove(key);
}
function contains(bytes32 key) external view returns (bool) {
return _bytes32ToBytes32Map.contains(key);
}
function length() external view returns (uint) {
return _bytes32ToBytes32Map.length();
}
function at(uint index) external view returns (bytes32, bytes32) {
return _bytes32ToBytes32Map.at(index);
}
function tryGet(bytes32 key) external view returns (bool, bytes32){
return _bytes32ToBytes32Map.tryGet(key);
}
function get(bytes32 key) external view returns (bytes32) {
return _bytes32ToBytes32Map.get(key);
}
function get(bytes32 key, string memory errorMessage) external view returns (bytes32) {
return _bytes32ToBytes32Map.get(key, errorMessage);
}
}
contract MockUintToUintMap {
using EnumerableMap for EnumerableMap.UintToUintMap;
EnumerableMap.UintToUintMap _uintToUintMap;
function set(uint key, uint value) external returns (bool) {
return _uintToUintMap.set(key, value);
}
function remove(uint key) external returns (bool) {
return _uintToUintMap.remove(key);
}
function contains(uint key) external view returns (bool) {
return _uintToUintMap.contains(key);
}
function length() external view returns (uint) {
return _uintToUintMap.length();
}
function at(uint index) external view returns (uint, uint) {
return _uintToUintMap.at(index);
}
function tryGet(uint key) external view returns (bool, uint){
return _uintToUintMap.tryGet(key);
}
function get(uint key) external view returns (uint) {
return _uintToUintMap.get(key);
}
function get(uint key, string memory errorMessage) external view returns (uint) {
return _uintToUintMap.get(key, errorMessage);
}
}
contract MockUintToAddressMap {
using EnumerableMap for EnumerableMap.UintToAddressMap;
EnumerableMap.UintToAddressMap _uintToAddressMap;
function set(uint key, address value) external returns (bool) {
return _uintToAddressMap.set(key, value);
}
function remove(uint key) external returns (bool) {
return _uintToAddressMap.remove(key);
}
function contains(uint key) external view returns (bool) {
return _uintToAddressMap.contains(key);
}
function length() external view returns (uint) {
return _uintToAddressMap.length();
}
function at(uint index) external view returns (uint, address) {
return _uintToAddressMap.at(index);
}
function tryGet(uint key) external view returns (bool, address){
return _uintToAddressMap.tryGet(key);
}
function get(uint key) external view returns (address) {
return _uintToAddressMap.get(key);
}
function get(uint key, string memory errorMessage) external view returns (address) {
return _uintToAddressMap.get(key, errorMessage);
}
}
contract MockAddressToUintMap {
using EnumerableMap for EnumerableMap.AddressToUintMap;
EnumerableMap.AddressToUintMap _addressToUintMap;
function set(address key, uint value) external returns (bool) {
return _addressToUintMap.set(key, value);
}
function remove(address key) external returns (bool) {
return _addressToUintMap.remove(key);
}
function contains(address key) external view returns (bool) {
return _addressToUintMap.contains(key);
}
function length() external view returns (uint) {
return _addressToUintMap.length();
}
function at(uint index) external view returns (address, uint) {
return _addressToUintMap.at(index);
}
function tryGet(address key) external view returns (bool, uint){
return _addressToUintMap.tryGet(key);
}
function get(address key) external view returns (uint) {
return _addressToUintMap.get(key);
}
function get(address key, string memory errorMessage) external view returns (uint) {
return _addressToUintMap.get(key, errorMessage);
}
}
contract MockBytes32ToUintMap {
using EnumerableMap for EnumerableMap.Bytes32ToUintMap;
EnumerableMap.Bytes32ToUintMap _bytes32ToUintMap;
function set(bytes32 key, uint value) external returns (bool) {
return _bytes32ToUintMap.set(key, value);
}
function remove(bytes32 key) external returns (bool) {
return _bytes32ToUintMap.remove(key);
}
function contains(bytes32 key) external view returns (bool) {
return _bytes32ToUintMap.contains(key);
}
function length() external view returns (uint) {
return _bytes32ToUintMap.length();
}
function at(uint index) external view returns (bytes32, uint) {
return _bytes32ToUintMap.at(index);
}
function tryGet(bytes32 key) external view returns (bool, uint){
return _bytes32ToUintMap.tryGet(key);
}
function get(bytes32 key) external view returns (uint) {
return _bytes32ToUintMap.get(key);
}
function get(bytes32 key, string memory errorMessage) external view returns (uint) {
return _bytes32ToUintMap.get(key, errorMessage);
}
}全部foundry测试合约：
2. 代码精读
2.1 Bytes32ToBytes32Map体系
结构体Bytes32ToBytes32Map是由一个存储key值的EnumerableSet.Bytes32Set和一个存储value值的mapping(bytes32 => bytes32)构成：
// key: bytes32类型 value：bytes32类型
struct Bytes32ToBytes32Map {
// 利用EnumerableSet.Bytes32Set来存储全部keys
// ps：EnumerableSet库详解见：https://learnblockchain.cn/article/6272
EnumerableSet.Bytes32Set _keys;
// 通过key来映射value的mapping
mapping(bytes32 => bytes32) _values;
}2.1.1 set(Bytes32ToBytes32Map storage map, bytes32 key, bytes32 value) && remove(Bytes32ToBytes32Map storage map, bytes32 key)
-
set(Bytes32ToBytes32Map storage map, bytes32 key, bytes32 value)：增添或更新键值对。如果输入key为已存在key（为更新键值对），返回false；如果输入key不存在（为新增键值对），返回true。时间复杂度为O(1)； -
remove(Bytes32ToBytes32Map storage map, bytes32 key)：删除键值对。如果输入key为已存在key（删除键值对），返回true；如果输入key不存在，返回false。时间复杂度为O(1)。
function set(
Bytes32ToBytes32Map storage map,
bytes32 key,
bytes32 value
) internal returns (bool) {
// Bytes32ToBytes32Map._values中更新key-value
map._values[key] = value;
//调用EnumerableSet库中对应的add()方法，在EnumerableSet.Bytes32Set中增添key。如果该key已存在于set中，返回false。否则返回true
return map._keys.add(key);
}
function remove(Bytes32ToBytes32Map storage map, bytes32 key) internal returns (bool) {
// Bytes32ToBytes32Map._values中删除key-value
delete map._values[key];
// 调用EnumerableSet库中对应的remove()方法，从EnumerableSet.Bytes32Set中删除key。如果该key已存在于set中，返回true。否则返回false
return map._keys.remove(key);
}2.1.2 contains(Bytes32ToBytes32Map storage map, bytes32 key) && length(Bytes32ToBytes32Map storage map) && at(Bytes32ToBytes32Map storage map, uint256 index)
contains(Bytes32ToBytes32Map storage map, bytes32 key)：查询输入key是否存在于Bytes32ToBytes32Map中。如果输入key为已存在key，返回true；如果输入key不存在，返回false。时间复杂度为O(1)；length(Bytes32ToBytes32Map storage map)：返回Bytes32ToBytes32Map中已存在的键值对数量。时间复杂度为O(1)；at(Bytes32ToBytes32Map storage map, uint256 index)：返回Bytes32ToBytes32Map中索引为index的key和对应的value。函数内部没有对index是否越界进行检查，所以在调用时请确保传入的index小于整个Bytes32ToBytes32Map的长度。时间复杂度为O(1)。注：index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时，set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bool) {
// 调用EnumerableSet库中对应的contains()方法，从EnumerableSet.Bytes32Set中查询输入key是否存在。如果该key已存在于set中，返回true。否则返回false
return map._keys.contains(key);
}
function length(Bytes32ToBytes32Map storage map) internal view returns (uint256) {
// 调用EnumerableSet库中对应的length()方法，返回已存在于map中的key的数量。key的数量其实就是map中键值对的数量
return map._keys.length();
}
function at(Bytes32ToBytes32Map storage map, uint256 index) internal view returns (bytes32, bytes32) {
// 调用EnumerableSet库中对应的at()方法，返回已存在于set中对应index位置的key
bytes32 key = map._keys.at(index);
// 返回key，并通过key找到对应的value一起返回
return (key, map._values[key]);
}2.1.3 tryGet(Bytes32ToBytes32Map storage map, bytes32 key) && get(Bytes32ToBytes32Map storage map, bytes32 key) && get(Bytes32ToBytes32Map storage map, bytes32 key, string memory errorMessage)
tryGet(Bytes32ToBytes32Map storage map, bytes32 key)：返回输入key是否存在于Bytes32ToBytes32Map中及输入key对应的value。时间复杂度为O(1)。注：如果key不存在于Bytes32ToBytes32Map中，不会revert，而是第一个参数返回false且对应值为bytes32(0)；get(Bytes32ToBytes32Map storage map, bytes32 key)：返回输入key对应的value。时间复杂度为O(1)。注：如果key不存在于Bytes32ToBytes32Map中，会revert；get(Bytes32ToBytes32Map storage map, bytes32 key, string memory errorMessage)：返回输入key对应的value（已弃用）。时间复杂度为O(1)。注：该方法与上面的get方法功能完全一致，只是本方法提供自定义revert msg的功能。但是不建议使用该方法，因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg，建议使用tryGet()进行组合。
function tryGet(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bool, bytes32) {
// 通过key找到value
bytes32 value = map._values[key];
// 如果value为0，可能存在两种情况：1. 已存在key对应的value就是0、2. key不存在
if (value == bytes32(0)) {
// 返回该key是否存在于map中和0值
return (contains(map, key), bytes32(0));
} else {
// 如果value不为0说明该key存在于map中，返回true和对应value值
return (true, value);
}
}
function get(Bytes32ToBytes32Map storage map, bytes32 key) internal view returns (bytes32) {
// 通过key找到value
bytes32 value = map._values[key];
// 如果value为0且map中不包含该key，直接revert
require(value != 0 || contains(map, key), "EnumerableMap: nonexistent key");
// 返回value值
return value;
}
function get(
Bytes32ToBytes32Map storage map,
bytes32 key,
string memory errorMessage
) internal view returns (bytes32) {
// 通过key找到value
bytes32 value = map._values[key];
// 如果value为0且map中不包含该key，直接以传入的errorMessage revert
require(value != 0 || contains(map, key), errorMessage);
// 返回value值
return value;
}2.1.4 foundry代码验证
contract EnumerableMapTest is Test {
MockBytes32ToBytes32Map mbtbm = new MockBytes32ToBytes32Map();
function test_Bytes32ToBytes32Map_Operations() external {
// empty
assertEq(mbtbm.length(), 0);
assertFalse(mbtbm.contains(0));
// set
assertTrue(mbtbm.set(0, 'v_0'));
assertEq(mbtbm.length(), 1);
assertTrue(mbtbm.set('a', 'v_a'));
assertEq(mbtbm.length(), 2);
// set key 'a' again
assertFalse(mbtbm.set('a', 'v_a_new'));
assertEq(mbtbm.length(), 2);
(bytes32 key, bytes32 value) = mbtbm.at(0);
assertEq(0, key);
assertEq('v_0', value);
(key, value) = mbtbm.at(1);
assertEq('a', key);
assertEq('v_a_new', value);
assertTrue(mbtbm.set('b', 'v_b'));
assertTrue(mbtbm.set('c', 'v_c'));
assertEq(mbtbm.length(), 4);
// remove
// key array: [0,'a','b','c']
assertTrue(mbtbm.contains('a'));
assertTrue(mbtbm.remove('a'));
assertFalse(mbtbm.contains('a'));
assertEq(mbtbm.length(), 3);
// remove key 'a' again
assertFalse(mbtbm.remove('a'));
assertEq(mbtbm.length(), 3);
// key array after remove: [0,'c','b']
(key, value) = mbtbm.at(0);
assertEq(0, key);
assertEq('v_0', value);
(key, value) = mbtbm.at(1);
assertEq('c', key);
assertEq('v_c', value);
(key, value) = mbtbm.at(2);
assertEq('b', key);
assertEq('v_b', value);
// check tryGet()/get()/get() with error msg
bytes32[3] memory keys = [bytes32(0), 'b', 'c'];
bytes32[3] memory values = [bytes32('v_0'), 'v_b', 'v_c'];
// case 1: key exists
bool exist;
for (uint i; i < 3; ++i) {
// tryGet()
(exist, value) = mbtbm.tryGet(keys[i]);
assertTrue(exist);
assertEq(value, values[i]);
// get()
assertEq(mbtbm.get(keys[i]), values[i]);
// get() with error msg
assertEq(mbtbm.get(keys[i], "revert msg: key not exist"), values[i]);
}
// case 2: key doesn't exist
bytes32 keyNotExist = 'key not exist';
(exist, value) = mbtbm.tryGet(keyNotExist);
assertFalse(exist);
assertEq(value, 0);
// get()
vm.expectRevert("EnumerableMap: nonexistent key");
mbtbm.get(keyNotExist);
// get() with error msg
vm.expectRevert("revert msg: key not exist");
mbtbm.get(keyNotExist, "revert msg: key not exist");
// revert if out of bounds
vm.expectRevert();
mbtbm.at(1024);
}
}2.2 UintToUintMap体系
结构体UintToUintMap的内部直接封装了一个Bytes32ToBytes32Map：
// key: uint256类型 value：uint256类型
struct UintToUintMap {
// 内部直接封装了一个Bytes32ToBytes32Map
Bytes32ToBytes32Map _inner;
}2.2.1 set(UintToUintMap storage map, uint256 key, uint256 value) && remove(UintToUintMap storage map, uint256 key)
-
set(UintToUintMap storage map, uint256 key, uint256 value)：增添或更新键值对。如果输入key为已存在key（为更新键值对），返回false；如果输入key不存在（为新增键值对），返回true。时间复杂度为O(1)； -
remove(UintToUintMap storage map, uint256 key)：删除键值对。如果输入key为已存在key（删除键值对），返回true；如果输入key不存在，返回false。时间复杂度为O(1)。
function set(
UintToUintMap storage map,
uint256 key,
uint256 value
) internal returns (bool) {
// 将传入的key和value都转成bytes32类型并调用底层的Bytes32ToBytes32Map的set()方法
return set(map._inner, bytes32(key), bytes32(value));
}
function remove(UintToUintMap storage map, uint256 key) internal returns (bool) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的remove()方法
return remove(map._inner, bytes32(key));
}2.2.2 contains(UintToUintMap storage map, uint256 key) && length(UintToUintMap storage map) && at(UintToUintMap storage map, uint256 index)
contains(UintToUintMap storage map, uint256 key)：查询输入key是否存在于UintToUintMap中。如果输入key为已存在key，返回true；如果输入key不存在，返回false。时间复杂度为O(1)；length(UintToUintMap storage map)： 返回UintToUintMap中已存在的键值对数量。时间复杂度为O(1)；at(UintToUintMap storage map, uint256 index)：返回UintToUintMap中索引为index的key和对应的value。函数内部没有对index是否越界进行检查，所以在调用时请确保传入的index小于整个UintToUintMap的长度。时间复杂度为O(1)。注：index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时，set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(UintToUintMap storage map, uint256 key) internal view returns (bool) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的contains()方法
return contains(map._inner, bytes32(key));
}
function length(UintToUintMap storage map) internal view returns (uint256) {
// 调用底层的Bytes32ToBytes32Map的length()方法
return length(map._inner);
}
function at(UintToUintMap storage map, uint256 index) internal view returns (uint256, uint256) {
// 调用底层的Bytes32ToBytes32Map的at()方法，得到底层返回的bytes32类型的key和value值
(bytes32 key, bytes32 value) = at(map._inner, index);
// 将bytes32类型的key和value转换成uint256类型并返回
return (uint256(key), uint256(value));
}2.2.3 tryGet(UintToUintMap storage map, uint256 key) && get(UintToUintMap storage map, uint256 key) && get(UintToUintMap storage map, uint256 key, string memory errorMessage)
tryGet(UintToUintMap storage map, uint256 key)：返回输入key是否存在于UintToUintMap中及输入key对应的value。时间复杂度为O(1)。注：如果key不存在于UintToUintMap中，不会revert，而是第一个参数返回false且对应值为uint256(0)；get(UintToUintMap storage map, uint256 key)：返回输入key对应的value。时间复杂度为O(1)。注：如果key不存在于UintToUintMap中，会revert；get(UintToUintMap storage map, uint256 key, string memory errorMessage)：返回输入key对应的value（已弃用）。时间复杂度为O(1)。注：该方法与上面的get方法功能完全一致，只是本方法提供自定义revert msg的功能。但是不建议使用该方法，因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg，建议使用tryGet()进行组合。
function tryGet(UintToUintMap storage map, uint256 key) internal view returns (bool, uint256) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的tryGet()方法
(bool success, bytes32 value) = tryGet(map._inner, bytes32(key));
// 将底层返回的传入key是否存在及bytes32类型的value转换成uint256类型返回
return (success, uint256(value));
}
function get(UintToUintMap storage map, uint256 key) internal view returns (uint256) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法，得到的bytes32类型结果转换成uint256类型返回
return uint256(get(map._inner, bytes32(key)));
}
function get(
UintToUintMap storage map,
uint256 key,
string memory errorMessage
) internal view returns (uint256) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法，得到的bytes32类型结果转换成uint256类型返回
return uint256(get(map._inner, bytes32(key), errorMessage));
}2.2.4 foundry代码验证
contract EnumerableMapTest is Test {
MockUintToUintMap mutum = new MockUintToUintMap();
function test_UintToUintMap_Operations() external {
// empty
assertEq(mutum.length(), 0);
assertFalse(mutum.contains(0));
// set
assertTrue(mutum.set(0, 1));
assertEq(mutum.length(), 1);
assertTrue(mutum.set(1, 2));
assertEq(mutum.length(), 2);
// set key 1 again
assertFalse(mutum.set(1, 2 + 1));
assertEq(mutum.length(), 2);
(uint key, uint value) = mutum.at(0);
assertEq(0, key);
assertEq(1, value);
(key, value) = mutum.at(1);
assertEq(1, key);
assertEq(3, value);
assertTrue(mutum.set(2, 4));
assertTrue(mutum.set(3, 8));
assertEq(mutum.length(), 4);
// remove
// key array: [0,1,2,3]
assertTrue(mutum.contains(1));
assertTrue(mutum.remove(1));
assertFalse(mutum.contains(1));
assertEq(mutum.length(), 3);
// remove key 1 again
assertFalse(mutum.remove(1));
assertEq(mutum.length(), 3);
// key array after remove: [0,3,2]
(key, value) = mutum.at(0);
assertEq(0, key);
assertEq(1, value);
(key, value) = mutum.at(1);
assertEq(3, key);
assertEq(8, value);
(key, value) = mutum.at(2);
assertEq(2, key);
assertEq(4, value);
// check tryGet()/get()/get() with error msg
uint[3] memory keys = [uint(0), 2, 3];
uint[3] memory values = [uint(1), 4, 8];
// case 1: key exists
bool exist;
for (uint i; i < 3; ++i) {
// tryGet()
(exist, value) = mutum.tryGet(keys[i]);
assertTrue(exist);
assertEq(value, values[i]);
// get()
assertEq(mutum.get(keys[i]), values[i]);
// get() with error msg
assertEq(mutum.get(keys[i], "revert msg: key not exist"), values[i]);
}
// case 2: key doesn't exist
uint keyNotExist = 1024;
(exist, value) = mutum.tryGet(keyNotExist);
assertFalse(exist);
assertEq(value, 0);
// get()
vm.expectRevert("EnumerableMap: nonexistent key");
mutum.get(keyNotExist);
// get() with error msg
vm.expectRevert("revert msg: key not exist");
mutum.get(keyNotExist, "revert msg: key not exist");
// revert if out of bounds
vm.expectRevert();
mutum.at(1024);
}
}2.3 UintToAddressMap体系
结构体UintToAddressMap的内部直接封装了一个Bytes32ToBytes32Map：
// key: uint256类型 value：address类型
struct UintToAddressMap {
// 内部直接封装了一个Bytes32ToBytes32Map
Bytes32ToBytes32Map _inner;
}2.3.1 set(UintToAddressMap storage map, uint256 key, address value) && remove(UintToAddressMap storage map, uint256 key)
-
set(UintToAddressMap storage map, uint256 key, address value)：增添或更新键值对。如果输入key为已存在key（为更新键值对），返回false；如果输入key不存在（为新增键值对），返回true。时间复杂度为O(1)； -
remove(UintToAddressMap storage map, uint256 key)：删除键值对。如果输入key为已存在key（删除键值对），返回true；如果输入key不存在，返回false。时间复杂度为O(1)。
function set(
UintToAddressMap storage map,
uint256 key,
address value
) internal returns (bool) {
// 将传入的key和value都转成bytes32类型并调用底层的Bytes32ToBytes32Map的set()方法
return set(map._inner, bytes32(key), bytes32(uint256(uint160(value))));
}
function remove(UintToAddressMap storage map, uint256 key) internal returns (bool) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的remove()方法
return remove(map._inner, bytes32(key));
}2.3.2 contains(UintToAddressMap storage map, uint256 key) && length(UintToAddressMap storage map) && at(UintToAddressMap storage map, uint256 index)
contains(UintToAddressMap storage map, uint256 key)：查询输入key是否存在于UintToAddressMap中。如果输入key为已存在key，返回true；如果输入key不存在，返回false。时间复杂度为O(1)；length(UintToAddressMap storage map)：返回UintToAddressMap中已存在的键值对数量。时间复杂度为O(1)；at(UintToAddressMap storage map, uint256 index)：返回UintToAddressMap中索引为index的key和对应的value。函数内部没有对index是否越界进行检查，所以在调用时请确保传入的index小于整个UintToAddressMap的长度。时间复杂度为O(1)。注：index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时，set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(UintToAddressMap storage map, uint256 key) internal view returns (bool) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的contains()方法
return contains(map._inner, bytes32(key));
}
function length(UintToAddressMap storage map) internal view returns (uint256) {
// 调用底层的Bytes32ToBytes32Map的length()方法
return length(map._inner);
}
function at(UintToAddressMap storage map, uint256 index) internal view returns (uint256, address) {
// 调用底层的Bytes32ToBytes32Map的at()方法，得到底层返回的bytes32类型的key和value值
(bytes32 key, bytes32 value) = at(map._inner, index);
// 将bytes32类型的key和value分别转换成uint256和address类型并返回
return (uint256(key), address(uint160(uint256(value))));
}2.3.3 tryGet(UintToAddressMap storage map, uint256 key) && get(UintToAddressMap storage map, uint256 key) && get(UintToAddressMap storage map, uint256 key, string memory errorMessage)
tryGet(UintToAddressMap storage map, uint256 key)：返回输入key是否存在于UintToAddressMap中及输入key对应的value。时间复杂度为O(1)。注：如果key不存在于UintToAddressMap中，不会revert，而是第一个参数返回false且对应值为address(0)；get(UintToAddressMap storage map, uint256 key)：返回输入key对应的value。时间复杂度为O(1)。注：如果key不存在于UintToAddressMap中，会revert；get(UintToAddressMap storage map, uint256 key, string memory errorMessage)：返回输入key对应的value（已弃用）。时间复杂度为O(1)。注：该方法与上面的get方法功能完全一致，只是本方法提供自定义revert msg的功能。但是不建议使用该方法，因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg，建议使用tryGet()进行组合。
function tryGet(UintToAddressMap storage map, uint256 key) internal view returns (bool, address) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的tryGet()方法
(bool success, bytes32 value) = tryGet(map._inner, bytes32(key));
// 将底层返回的传入key是否存在及bytes32类型的value转换成address类型返回
return (success, address(uint160(uint256(value))));
}
function get(UintToAddressMap storage map, uint256 key) internal view returns (address) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法，得到的bytes32类型结果转换成address类型返回
return address(uint160(uint256(get(map._inner, bytes32(key)))));
}
function get(
UintToAddressMap storage map,
uint256 key,
string memory errorMessage
) internal view returns (address) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法，得到的bytes32类型结果转换成address类型返回
return address(uint160(uint256(get(map._inner, bytes32(key), errorMessage))));
}2.3.4 foundry代码验证
contract EnumerableMapTest is Test {
MockUintToAddressMap mutam = new MockUintToAddressMap();
function test_UintToAddressMap_Operations() external {
// empty
assertEq(mutam.length(), 0);
assertFalse(mutam.contains(0));
// set
assertTrue(mutam.set(0, address(0)));
assertEq(mutam.length(), 1);
assertTrue(mutam.set(1, address(1)));
assertEq(mutam.length(), 2);
// set key 1 again
assertFalse(mutam.set(1, address(1 + 1)));
assertEq(mutam.length(), 2);
(uint key, address value) = mutam.at(0);
assertEq(0, key);
assertEq(address(0), value);
(key, value) = mutam.at(1);
assertEq(1, key);
assertEq(address(2), value);
assertTrue(mutam.set(2, address(2)));
assertTrue(mutam.set(3, address(3)));
assertEq(mutam.length(), 4);
// remove
// key array: [0,1,2,3]
assertTrue(mutam.contains(1));
assertTrue(mutam.remove(1));
assertFalse(mutam.contains(1));
assertEq(mutam.length(), 3);
// remove key 1 again
assertFalse(mutam.remove(1));
assertEq(mutam.length(), 3);
// key array after remove: [0,3,2]
(key, value) = mutam.at(0);
assertEq(0, key);
assertEq(address(0), value);
(key, value) = mutam.at(1);
assertEq(3, key);
assertEq(address(3), value);
(key, value) = mutam.at(2);
assertEq(2, key);
assertEq(address(2), value);
// check tryGet()/get()/get() with error msg
uint[3] memory keys = [uint(0), 2, 3];
address[3] memory values = [address(0), address(2), address(3)];
// case 1: key exists
bool exist;
for (uint i; i < 3; ++i) {
// tryGet()
(exist, value) = mutam.tryGet(keys[i]);
assertTrue(exist);
assertEq(value, values[i]);
// get()
assertEq(mutam.get(keys[i]), values[i]);
// get() with error msg
assertEq(mutam.get(keys[i], "revert msg: key not exist"), values[i]);
}
// case 2: key doesn't exist
uint keyNotExist = 1024;
(exist, value) = mutam.tryGet(keyNotExist);
assertFalse(exist);
assertEq(value, address(0));
// get()
vm.expectRevert("EnumerableMap: nonexistent key");
mutam.get(keyNotExist);
// get() with error msg
vm.expectRevert("revert msg: key not exist");
mutam.get(keyNotExist, "revert msg: key not exist");
// revert if out of bounds
vm.expectRevert();
mutam.at(1024);
}
}2.4 AddressToUintMap体系
结构体AddressToUintMap的内部直接封装了一个Bytes32ToBytes32Map：
// key: address类型 value：uint256类型
struct AddressToUintMap {
// 内部直接封装了一个Bytes32ToBytes32Map
Bytes32ToBytes32Map _inner;
}2.4.1 set(AddressToUintMap storage map, address key, uint256 value) && remove(AddressToUintMap storage map, address key)
-
set(AddressToUintMap storage map, address key, uint256 value)：增添或更新键值对。如果输入key为已存在key（为更新键值对），返回false；如果输入key不存在（为新增键值对），返回true。时间复杂度为O(1)； -
remove(AddressToUintMap storage map, address key)：删除键值对。如果输入key为已存在key（删除键值对），返回true；如果输入key不存在，返回false。时间复杂度为O(1)。
function set(
AddressToUintMap storage map,
address key,
uint256 value
) internal returns (bool) {
// 将传入的key和value都转成bytes32类型并调用底层的Bytes32ToBytes32Map的set()方法
return set(map._inner, bytes32(uint256(uint160(key))), bytes32(value));
}
function remove(AddressToUintMap storage map, address key) internal returns (bool) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的remove()方法
return remove(map._inner, bytes32(uint256(uint160(key))));
}2.4.2 contains(AddressToUintMap storage map, address key) && length(AddressToUintMap storage map) && at(AddressToUintMap storage map, uint256 index)
contains(AddressToUintMap storage map, address key)：查询输入key是否存在于AddressToUintMap中。如果输入key为已存在key，返回true；如果输入key不存在，返回false。时间复杂度为O(1)；length(AddressToUintMap storage map)：返回AddressToUintMap中已存在的键值对数量。时间复杂度为O(1)；at(AddressToUintMap storage map, uint256 index)：返回AddressToUintMap中索引为index的key和对应的value。函数内部没有对index是否越界进行检查，所以在调用时请确保传入的index小于整个UintToAddressMap的长度。时间复杂度为O(1)。注：index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时，set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(AddressToUintMap storage map, address key) internal view returns (bool) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的contains()方法
return contains(map._inner, bytes32(uint256(uint160(key))));
}
function length(AddressToUintMap storage map) internal view returns (uint256) {
// 调用底层的Bytes32ToBytes32Map的length()方法
return length(map._inner);
}
function at(AddressToUintMap storage map, uint256 index) internal view returns (address, uint256) {
// 调用底层的Bytes32ToBytes32Map的at()方法，得到底层返回的bytes32类型的key和value值
(bytes32 key, bytes32 value) = at(map._inner, index);
// 将bytes32类型的key和value分别转换成address和uint256类型并返回
return (address(uint160(uint256(key))), uint256(value));
}2.4.3 tryGet(AddressToUintMap storage map, address key) && get(AddressToUintMap storage map, address key) && get(AddressToUintMap storage map, address key, string memory errorMessage)
tryGet(AddressToUintMap storage map, address key)：返回输入key是否存在于AddressToUintMap中及输入key对应的value。时间复杂度为O(1)。注：如果key不存在于AddressToUintMap中，不会revert，而是第一个参数返回false且对应值为uint256(0)；get(AddressToUintMap storage map, address key)：返回输入key对应的value。时间复杂度为O(1)。注：如果key不存在于AddressToUintMap中，会revert；get(AddressToUintMap storage map, address key, string memory errorMessage)：返回输入key对应的value（已弃用）。时间复杂度为O(1)。注：该方法与上面的get方法功能完全一致，只是本方法提供自定义revert msg的功能。但是不建议使用该方法，因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg，建议使用tryGet()进行组合。
function tryGet(AddressToUintMap storage map, address key) internal view returns (bool, uint256) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的tryGet()方法
(bool success, bytes32 value) = tryGet(map._inner, bytes32(uint256(uint160(key))));
// 将底层返回的传入key是否存在及bytes32类型的value转换成uint256类型返回
return (success, uint256(value));
}
function get(AddressToUintMap storage map, address key) internal view returns (uint256) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法，得到的bytes32类型结果转换成uint256类型返回
return uint256(get(map._inner, bytes32(uint256(uint160(key)))));
}
function get(
AddressToUintMap storage map,
address key,
string memory errorMessage
) internal view returns (uint256) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的get()方法，得到的bytes32类型结果转换成uint256类型返回
return uint256(get(map._inner, bytes32(uint256(uint160(key))), errorMessage));
}2.4.4 foundry代码验证
contract EnumerableMapTest is Test {
MockAddressToUintMap matum = new MockAddressToUintMap();
function test_AddressToUintMap_Operations() external {
// empty
assertEq(matum.length(), 0);
assertFalse(matum.contains(address(0)));
// set
assertTrue(matum.set(address(0), 0));
assertEq(matum.length(), 1);
assertTrue(matum.set(address(1), 1));
assertEq(matum.length(), 2);
// set key address(1) again
assertFalse(matum.set(address(1), 1 + 1));
assertEq(matum.length(), 2);
(address key, uint value) = matum.at(0);
assertEq(address(0), key);
assertEq(0, value);
(key, value) = matum.at(1);
assertEq(address(1), key);
assertEq(2, value);
assertTrue(matum.set(address(2), 2));
assertTrue(matum.set(address(3), 3));
assertEq(matum.length(), 4);
// remove
// key array: [address(0),address(1),address(2),address(3)]
assertTrue(matum.contains(address(1)));
assertTrue(matum.remove(address(1)));
assertFalse(matum.contains(address(1)));
assertEq(matum.length(), 3);
// remove key address(1) again
assertFalse(matum.remove(address(1)));
assertEq(matum.length(), 3);
// key array after remove: [address(0),address(3),address(2)]
(key, value) = matum.at(0);
assertEq(address(0), key);
assertEq(0, value);
(key, value) = matum.at(1);
assertEq(address(3), key);
assertEq(3, value);
(key, value) = matum.at(2);
assertEq(address(2), key);
assertEq(2, value);
// check tryGet()/get()/get() with error msg
address[3] memory keys = [address(0), address(2), address(3)];
uint[3] memory values = [uint(0), 2, 3];
// case 1: key exists
bool exist;
for (uint i; i < 3; ++i) {
// tryGet()
(exist, value) = matum.tryGet(keys[i]);
assertTrue(exist);
assertEq(value, values[i]);
// get()
assertEq(matum.get(keys[i]), values[i]);
// get() with error msg
assertEq(matum.get(keys[i], "revert msg: key not exist"), values[i]);
}
// case 2: key doesn't exist
address keyNotExist = address(1024);
(exist, value) = matum.tryGet(keyNotExist);
assertFalse(exist);
assertEq(value, 0);
// get()
vm.expectRevert("EnumerableMap: nonexistent key");
matum.get(keyNotExist);
// get() with error msg
vm.expectRevert("revert msg: key not exist");
matum.get(keyNotExist, "revert msg: key not exist");
// revert if out of bounds
vm.expectRevert();
matum.at(1024);
}
}2.5 Bytes32ToUintMap体系
结构体Bytes32ToUintMap的内部直接封装了一个Bytes32ToBytes32Map：
// key: bytes32类型 value：uint256类型
struct Bytes32ToUintMap {
// 内部直接封装了一个Bytes32ToBytes32Map
Bytes32ToBytes32Map _inner;
}2.5.1 set(Bytes32ToUintMap storage map, bytes32 key, uint256 value) && remove(Bytes32ToUintMap storage map, bytes32 key)
-
set(Bytes32ToUintMap storage map, bytes32 key, uint256 value)：增添或更新键值对。如果输入key为已存在key（为更新键值对），返回false；如果输入key不存在（为新增键值对），返回true。时间复杂度为O(1)； -
remove(Bytes32ToUintMap storage map, bytes32 key)：删除键值对。如果输入key为已存在key（删除键值对），返回true；如果输入key不存在，返回false。时间复杂度为O(1)。
function set(
Bytes32ToUintMap storage map,
bytes32 key,
uint256 value
) internal returns (bool) {
// 将传入的key和value都转成bytes32类型并调用底层的Bytes32ToBytes32Map的set()方法
return set(map._inner, key, bytes32(value));
}
function remove(Bytes32ToUintMap storage map, bytes32 key) internal returns (bool) {
// 将传入的key转成bytes32类型并调用底层的Bytes32ToBytes32Map的remove()方法
return remove(map._inner, key);
}2.5.2 contains(Bytes32ToUintMap storage map, bytes32 key) && length(Bytes32ToUintMap storage map) && at(Bytes32ToUintMap storage map, uint256 index)
contains(Bytes32ToUintMap storage map, bytes32 key)：查询输入key是否存在于Bytes32ToUintMap中。如果输入key为已存在key，返回true；如果输入key不存在，返回false。时间复杂度为O(1)；length(Bytes32ToUintMap storage map)：返回Bytes32ToUintMap中已存在的键值对数量。时间复杂度为O(1)；at(Bytes32ToUintMap storage map, uint256 index)：返回Bytes32ToUintMap中索引为index的key和对应的value。函数内部没有对index是否越界进行检查，所以在调用时请确保传入的index小于整个Bytes32ToUintMap的长度。时间复杂度为O(1)。注：index其实是指Bytes32ToBytes32Map.Bytes32Set的key的index。当每次进行key的remove操作时，set中的key顺序都会发生变化。所以不要盲目地认为该index就是键值对的添加顺序的index。
function contains(Bytes32ToUintMap storage map, bytes32 key) internal view returns (bool) {
// 直接调用底层的Bytes32ToBytes32Map的contains()方法
return contains(map._inner, key);
}
function length(Bytes32ToUintMap storage map) internal view returns (uint256) {
// 调用底层的Bytes32ToBytes32Map的length()方法
return length(map._inner);
}
function at(Bytes32ToUintMap storage map, uint256 index) internal view returns (bytes32, uint256) {
// 调用底层的Bytes32ToBytes32Map的at()方法，得到底层返回的bytes32类型的key和value值
(bytes32 key, bytes32 value) = at(map._inner, index);
// 直接返回key，并将value转换成uint256类型返回
return (key, uint256(value));
}2.5.3 tryGet(Bytes32ToUintMap storage map, bytes32 key) && get(Bytes32ToUintMap storage map, bytes32 key) && get(Bytes32ToUintMap storage map, bytes32 key, string memory errorMessage)
tryGet(Bytes32ToUintMap storage map, bytes32 key)：返回输入key是否存在于Bytes32ToUintMap中及输入key对应的value。时间复杂度为O(1)。注：如果key不存在于Bytes32ToUintMap中，不会revert，而是第一个参数返回false且对应值为uint256(0)；get(Bytes32ToUintMap storage map, bytes32 key)：返回输入key对应的value。时间复杂度为O(1)。注：如果key不存在于Bytes32ToUintMap中，会revert；get(Bytes32ToUintMap storage map, bytes32 key, string memory errorMessage)：返回输入key对应的value（已弃用）。时间复杂度为O(1)。注：该方法与上面的get方法功能完全一致，只是本方法提供自定义revert msg的功能。但是不建议使用该方法，因为字符串参数会增加额外的memory的消耗。如果当key不存在时一定要使用自定义revert msg，建议使用tryGet()进行组合。
function tryGet(Bytes32ToUintMap storage map, bytes32 key) internal view returns (bool, uint256) {
// 直接调用底层的Bytes32ToBytes32Map的tryGet()方法
(bool success, bytes32 value) = tryGet(map._inner, key);
// 直接返回key是否存在，并将value转换成uint256类型返回
return (success, uint256(value));
}
function get(Bytes32ToUintMap storage map, bytes32 key) internal view returns (uint256) {
// 直接调用底层的Bytes32ToBytes32Map的get()方法，得到的bytes32类型结果转换成uint256类型返回
return uint256(get(map._inner, key));
}
function get(
Bytes32ToUintMap storage map,
bytes32 key,
string memory errorMessage
) internal view returns (uint256) {
// 直接调用底层的Bytes32ToBytes32Map的get()方法，得到的bytes32类型结果转换成uint256类型返回
return uint256(get(map._inner, key, errorMessage));
}2.5.4 foundry代码验证
contract EnumerableMapTest is Test {
MockBytes32ToUintMap mbtum = new MockBytes32ToUintMap();
function test_Bytes32ToUintMap_Operations() external {
// empty
assertEq(mbtum.length(), 0);
assertFalse(mbtum.contains(0));
// set
assertTrue(mbtum.set(0, 0));
assertEq(mbtum.length(), 1);
assertTrue(mbtum.set('a', 1));
assertEq(mbtum.length(), 2);
// set key 'a' again
assertFalse(mbtum.set('a', 97));
assertEq(mbtum.length(), 2);
(bytes32 key, uint value) = mbtum.at(0);
assertEq(0, key);
assertEq(0, value);
(key, value) = mbtum.at(1);
assertEq('a', key);
assertEq(97, value);
assertTrue(mbtum.set('b', 98));
assertTrue(mbtum.set('c', 99));
assertEq(mbtum.length(), 4);
// remove
// key array: [0,'a','b','c']
assertTrue(mbtum.contains('a'));
assertTrue(mbtum.remove('a'));
assertFalse(mbtum.contains('a'));
assertEq(mbtum.length(), 3);
// remove key 'a' again
assertFalse(mbtum.remove('a'));
assertEq(mbtum.length(), 3);
// key array after remove: [0,'c','b']
(key, value) = mbtum.at(0);
assertEq(0, key);
assertEq(0, value);
(key, value) = mbtum.at(1);
assertEq('c', key);
assertEq(99, value);
(key, value) = mbtum.at(2);
assertEq('b', key);
assertEq(98, value);
// check tryGet()/get()/get() with error msg
bytes32[3] memory keys = [bytes32(0), 'b', 'c'];
uint[3] memory values = [uint(0), 98, 99];
// case 1: key exists
bool exist;
for (uint i; i < 3; ++i) {
// tryGet()
(exist, value) = mbtum.tryGet(keys[i]);
assertTrue(exist);
assertEq(value, values[i]);
// get()
assertEq(mbtum.get(keys[i]), values[i]);
// get() with error msg
assertEq(mbtum.get(keys[i], "revert msg: key not exist"), values[i]);
}
// case 2: key doesn't exist
bytes32 keyNotExist = 'key not exist';
(exist, value) = mbtum.tryGet(keyNotExist);
assertFalse(exist);
assertEq(value, 0);
// get()
vm.expectRevert("EnumerableMap: nonexistent key");
mbtum.get(keyNotExist);
// get() with error msg
vm.expectRevert("revert msg: key not exist");
mbtum.get(keyNotExist, "revert msg: key not exist");
// revert if out of bounds
vm.expectRevert();
mbtum.at(1024);
}
}ps:\ 本人热爱图灵，热爱中本聪，热爱V神。 以下是我个人的公众号，如果有技术问题可以关注我的公众号来跟我交流。 同时我也会在这个公众号上每周更新我的原创文章，喜欢的小伙伴或者老伙计可以支持一下！ 如果需要转发，麻烦注明作者。十分感谢！
公众号名称：后现代泼痞浪漫主义奠基人
- 原创
- 学分: 1
- 分类: Solidity
- 标签: OpenZeppelin
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。
