// SPDX-License-Identifier: MIT // OpenZeppelin Contracts (last updated v4.8.0) (token/ERC721/extensions/ERC721Enumerable.sol) pragma solidity ^0.8.0; import "../ERC721.sol"; import "./IERC721Enumerable.sol"; /** * @dev This implements an optional extension of {ERC721} defined in the EIP that adds * enumerability of all the token ids in the contract as well as all token ids owned by each * account. */ abstract contract ERC721Enumerable is ERC721, IERC721Enumerable { // Mapping from owner to list of owned token IDs mapping(address => mapping(uint256 => uint256)) private _ownedTokens; // Mapping from token ID to index of the owner tokens list mapping(uint256 => uint256) private _ownedTokensIndex; // Array with all token ids, used for enumeration uint256[] private _allTokens; // Mapping from token id to position in the allTokens array mapping(uint256 => uint256) private _allTokensIndex; /** * @dev See {IERC165-supportsInterface}. */ function supportsInterface(bytes4 interfaceId) public view virtual override(IERC165, ERC721) returns (bool) { return interfaceId == type(IERC721Enumerable).interfaceId || super.supportsInterface(interfaceId); } /** * @dev See {IERC721Enumerable-tokenOfOwnerByIndex}. */ function tokenOfOwnerByIndex(address owner, uint256 index) public view virtual override returns (uint256) { require(index < ERC721.balanceOf(owner), "ERC721Enumerable: owner index out of bounds"); return _ownedTokens[owner][index]; } /** * @dev See {IERC721Enumerable-totalSupply}. */ function totalSupply() public view virtual override returns (uint256) { return _allTokens.length; } /** * @dev See {IERC721Enumerable-tokenByIndex}. */ function tokenByIndex(uint256 index) public view virtual override returns (uint256) { require(index < ERC721Enumerable.totalSupply(), "ERC721Enumerable: global index out of bounds"); return _allTokens[index]; } /** * @dev See {ERC721-_beforeTokenTransfer}. */ function _beforeTokenTransfer( address from, address to, uint256 firstTokenId, uint256 batchSize ) internal virtual override { super._beforeTokenTransfer(from, to, firstTokenId, batchSize); if (batchSize > 1) { // Will only trigger during construction. Batch transferring (minting) is not available afterwards. revert("ERC721Enumerable: consecutive transfers not supported"); } uint256 tokenId = firstTokenId; if (from == address(0)) { _addTokenToAllTokensEnumeration(tokenId); } else if (from != to) { _removeTokenFromOwnerEnumeration(from, tokenId); } if (to == address(0)) { _removeTokenFromAllTokensEnumeration(tokenId); } else if (to != from) { _addTokenToOwnerEnumeration(to, tokenId); } } /** * @dev Private function to add a token to this extension's ownership-tracking data structures. * @param to address representing the new owner of the given token ID * @param tokenId uint256 ID of the token to be added to the tokens list of the given address */ function _addTokenToOwnerEnumeration(address to, uint256 tokenId) private { uint256 length = ERC721.balanceOf(to); _ownedTokens[to][length] = tokenId; _ownedTokensIndex[tokenId] = length; } /** * @dev Private function to add a token to this extension's token tracking data structures. * @param tokenId uint256 ID of the token to be added to the tokens list */ function _addTokenToAllTokensEnumeration(uint256 tokenId) private { _allTokensIndex[tokenId] = _allTokens.length; _allTokens.push(tokenId); } /** * @dev Private function to remove a token from this extension's ownership-tracking data structures. Note that * while the token is not assigned a new owner, the `_ownedTokensIndex` mapping is _not_ updated: this allows for * gas optimizations e.g. when performing a transfer operation (avoiding double writes). * This has O(1) time complexity, but alters the order of the _ownedTokens array. * @param from address representing the previous owner of the given token ID * @param tokenId uint256 ID of the token to be removed from the tokens list of the given address */ function _removeTokenFromOwnerEnumeration(address from, uint256 tokenId) private { // To prevent a gap in from's tokens array, we store the last token in the index of the token to delete, and // then delete the last slot (swap and pop). uint256 lastTokenIndex = ERC721.balanceOf(from) - 1; uint256 tokenIndex = _ownedTokensIndex[tokenId]; // When the token to delete is the last token, the swap operation is unnecessary if (tokenIndex != lastTokenIndex) { uint256 lastTokenId = _ownedTokens[from][lastTokenIndex]; _ownedTokens[from][tokenIndex] = lastTokenId; // Move the last token to the slot of the to-delete token _ownedTokensIndex[lastTokenId] = tokenIndex; // Update the moved token's index } // This also deletes the contents at the last position of the array delete _ownedTokensIndex[tokenId]; delete _ownedTokens[from][lastTokenIndex]; } /** * @dev Private function to remove a token from this extension's token tracking data structures. * This has O(1) time complexity, but alters the order of the _allTokens array. * @param tokenId uint256 ID of the token to be removed from the tokens list */ function _removeTokenFromAllTokensEnumeration(uint256 tokenId) private { // To prevent a gap in the tokens array, we store the last token in the index of the token to delete, and // then delete the last slot (swap and pop). uint256 lastTokenIndex = _allTokens.length - 1; uint256 tokenIndex = _allTokensIndex[tokenId]; // When the token to delete is the last token, the swap operation is unnecessary. However, since this occurs so // rarely (when the last minted token is burnt) that we still do the swap here to avoid the gas cost of adding // an 'if' statement (like in _removeTokenFromOwnerEnumeration) uint256 lastTokenId = _allTokens[lastTokenIndex]; _allTokens[tokenIndex] = lastTokenId; // Move the last token to the slot of the to-delete token _allTokensIndex[lastTokenId] = tokenIndex; // Update the moved token's index // This also deletes the contents at the last position of the array delete _allTokensIndex[tokenId]; _allTokens.pop(); } }