Jumping into Solidity — The ERC721 Standard (Part 7)

12 min readJun 28, 2018

By now our ERC721 implementation is really starting to take shape. We’ve written our basic implementation, the true codeslingers among you even tested it, and in the last article we learned about extensions and added Metadata to our contract. Today we’re going to round it off by implementing the Enumerable extension which will really give our contract some legs.

A quick note for the long time readers

In my last article, I went on a slight tangent where I urged you all to bookmark the EIPs page, and always use that as your main reference when writing a contract to an ERC standard (in this case the one for ERC721). The reason being that other resources can have mistakes, and up until a few days ago ERC721 wasn’t even finalised.

Well one of you was paying attention, because someone pointed out that the standard has slightly changed the ERC721TokenReceiver interface. Previously, its onERC721Received function only had 3 arguments, but now it takes 4. It now takes the form:

onERC721Received(address _operator, address _from, uint256 _tokenId, bytes _data)

The addition of the _operator argument just says who made the transfer, so msg.sender is always passed, but the point is that if you’ve been reading week-by-week you’ll need to go back and change your receivers as well as your safeTransferFrom function.

I’ve updated the old articles, so if you’re a new reader you should be okay, but if not we defined our receivers in Part 2 and we wrote our safeTransferFrom function in Part 4. There’s only one line changed in the latter so it shouldn’t be too much of a headache to fix.

The standard has now been made final, so there shouldn’t be any more surprises like this, but constant vigilance is the only weapon we have against bad code!

We now return to our feature presentation…

The Enumerable Extension

The Enumerable extension basically makes it easier for people to organise our NFTs. It bakes in some functions that let websites, apps, other contracts etc. sort them by index, which makes them easy to list without requiring any extra data.

Remember back in Part 3 we learned that tokenIds don’t need to follow any sort of pattern, and thus we can’t use them as an index. You may have a token with the tokenId of 19, but this doesn’t mean there exists a token with the tokenId of 20 or even 18.

But what if someone wants to make a website or wallet app that displays all your NFTs, or a marketplace that allows people to trade them? Or what if you want to build a front-end for your ERC721 implementation? These are just a couple of examples of times when it would be handy if we could organise tokens by an index, and that’s what the Enumerable extension gives us.

The extension gives us three functions, the latter two of which let us retrieve tokens by index,

function totalSupply() external view returns (uint256);function tokenByIndex(uint256 _index) external view returns (uint256);function tokenOfOwnerByIndex(address _owner, uint256 _index) external view returns (uint256);

What this means is that if there are 10 of your NFTs in existence, then someone can ask your contract “What is the tokenId of the 6th token?” and it will return some predictable result. Essentially your contract will keep ordered lists of tokens; one for all tokens, and one for each address that owns at least one token.

Before we go any further, let’s declare our contract as an extension of our original TokenERC721.sol contract, and an implementation of the ERC721Enumerable extension interface.

contract TokenERC721Enumerable is TokenERC721, ERC721Enumerable {

Next we’ll declare all our contract variables at the start because we like to keep things tidy, but first let’s talk about arrays in Solidity

Working with arrays in Solidity

Depending what programming languages you have experience with, you may be accustomed to being able to easily manipulate arrays without any stress at all.

For example, in Javascript we can insert or remove elements from the middle of an array with a single operation and it all glues itself back together automatically. Unfortunately Solidity doesn’t provide us with the same tools, so when working with arrays we sometimes need to get a little more creative.

If you have an array of uints,

uint[] a = [1,2,3,4];

And then use the delete operation on the second element,

delete a[1];

Then the result will be,

a = [1,0,3,4];

If this a array were our list of tokenIds then this wouldn’t be ideal, because now if somebody asks our contract “What is the tokenId of the 2nd token?”, the contract will say 0, which in our case isn’t even a valid tokenId.

There’s no simple trick that removes that gap and puts everything back in its place, but luckily preserving the order of our list isn’t a requirement. The tokenId of a token must never change, but its index may change whenever we want it to.

This may sound strange at first glance, but when you consider that some implementations allow tokens to be burnt, then of course the indices can change. The index isn’t supposed to be another unique identifier like the tokenId, it’s just a way of sorting your tokens given your contract’s current state.

So with that in mind, all we have to do is move the last element in our array to the newly empty slot and voila, we still have our list.

a = [1,4,3];

This, in a nutshell, is how all our lists are going to work. Whenever we add an element to a list, we’ll just chuck it on the end, and whenever we remove something from the middle, we’ll fill the empty space with the last element. For the tokenOfOwnerByIndex function we’ll need to make sure we keep track of which tokenId is in which slot, so there are a few other things we’ll be adding to deal with this, but the key takeaway is that the order of our lists changes.

The only way to preserve the order would be to iterate through our entire array moving one element at a time until we got to the end, which would be completely unscaleable.

Contract variables and constructor

As you may have figured out by now, we’re actually adding two types of list. The first is just a list of all the tokens that have been made, which is what the tokenByIndex function deals with. There will only be one of these, managed by the following array:

uint[] internal tokenIndexes;

If you have a burn function in your contract, you’ll also need to add a mapping which tracks which index belongs to which token (for working out which gap in the array needs to be filled). So if you do, make sure you also add this:

mapping(uint => uint) internal indexTokens;

However, if you don’t have a burn function, you can ignore any line you see today that mentions indexTokens.

The other type of list we have is a list of all the tokens that belong to a given address, and this is what the tokenOfOwnerByIndex function deals with. There will be one of these for each address that owns at least one token, managed by these two mappings:

mapping(address => uint[]) internal ownerTokenIndexes;
mapping(uint => uint) internal tokenTokenIndexes;

The first is just assigning an array of uints to each address, this is literally just a list of all the tokenIds that address owns. The second maps each tokenId to its position in the relevant ownerTokenIndexes array — we’ll need this when we have to move things around. If you’re still having trouble picturing it, they take this form:

ownerTokenIndexes[ownerAddress][tokenIndex] = tokenId;
tokenTokenIndexes[tokenId] = tokenIndex;

Next is the constructor, note as always that we need to add the interface to supportedInterfaces (see Part 2 if you’ve forgotten about that), and remember to pass _initialSupply to TokenERC721’s constructor if your implementation uses an initial supply.

constructor(uint _initialSupply) public TokenERC721(_initialSupply){
    for(uint i = 0; i < _initialSupply; i++){
        tokenTokenIndexes[i+1] = i;
        ownerTokenIndexes[creator].push(i+1);
        tokenIndexes.push(i+1);
        indexTokens[i + 1] = i;
    }

    //Add to ERC165 Interface Check
    supportedInterfaces[
        this.totalSupply.selector ^
        this.tokenByIndex.selector ^
        this.tokenOfOwnerByIndex.selector
    ] = true;
}

Again, this only applies if your implementation uses an initial supply, but what we’re doing here is adding our newly created tokens to their relevant arrays and mappings. Remember our tokenIds are just sequential integers starting at 1, which is what i+1 refers to, and since all initial tokens belong to the contract creator, i refers to the index in the creator’s ownerTokenIndexes array, as well as the main tokenIndexes array.

You may notice that this makes our contract slightly less scalable. The more tokens we create, the more gas it consumes, and the same will be true later when we modify our issueTokens function. Unfortunately there’s no way around this, it’s just the nature of the beast, but hopefully if you’re issuing a lot of tokens, it means your project has had enough success to justify the few extra cents you’ll have to spend on gas.

totalSupply

I’m not sure just how intuitive any of this has been so far so let’s knock out some easy stuff while all that soaks in. The totalSupply function is extremely simple, we just return the length of our tokenIndexes array. Since every token is in there, the length of the array will naturally be the number of tokens.

function totalSupply() external view returns (uint256){
    return tokenIndexes.length;
}

Easy!

tokenByIndex

The tokenByIndex function is equally simple. The index just refers to the position in this array, so we just return whatever value is at that position. The only other thing we have to do is make sure the index being checked is less than the total number of tokens.

function tokenByIndex(uint256 _index) external view returns(uint256){
    require(_index < tokenIndexes.length);
    return tokenIndexes[_index];
}

tokenOfOwnerByIndex

Even this function is simple. It’s basically the same as the last one, except instead we check if the index is less than the owner’s balance, and return a value from the relevant ownerTokenIndexes array.

function tokenOfOwnerByIndex(address _owner, uint256 _index) external view returns (uint256){
    require(_index < balances[_owner]);
    return ownerTokenIndexes[_owner][_index];
}

And now we’ve implemented all the new Enumerable functions, so we’re done right? I’m sorry to have to tell you, but that was the easy part! The real challenge is modifying our transferFrom function to deal with these new arrays.

Modifying transferFrom

I think the best way to explain this is with an example. Suppose we have two token owners, call them 0xAAA and 0xBBB.

0xAAA owns 4 tokens, with tokenIds of 1, 2, 3 and 4. 0xBBB also owns 4 tokens, with tokenIds of 5, 6, 7 and 8.

Let’s assume that their respective ownerTokenIndexes arrays are in the following state (although in theory they could be in any order):

ownerTokenIndexes[0xAAA] => [1, 2, 3, 4];
ownerTokenIndexes[0xBBB] => [5, 6, 7, 8];

This means that the relevant values in tokenTokenIndexes will be as follows:

tokenTokenIndexes[1] => 0;
tokenTokenIndexes[2] => 1;
tokenTokenIndexes[3] => 2;
tokenTokenIndexes[4] => 3;
tokenTokenIndexes[5] => 0;
tokenTokenIndexes[6] => 1;
tokenTokenIndexes[7] => 2;
tokenTokenIndexes[8] => 3;

Now if 0xAAA sends the token with the tokenId of 2 to 0xBBB, we need to make the following changes:

Remove 2 from ownerTokenIndexes[0xAAA]
Move 4 from the end of ownerTokenIndexes[0xAAA] to fill the newly empty slot.
Update tokenTokenIndexes[4] to reflect the new index of 4.
Add 2 to the end of ownerTokenIndexes[0xBBB]
Update tokenTokenIndexes[2] to reflect the new index of 2.

There’s also one last step which is:

6. Decrement ownerTokenIndexes[0xAAA].length by 1 because Solidity won’t automatically shorten an array even if you delete the last element. And really I lied about step 1, there’s no point in actually removing 2, we just go right ahead and overwrite it in step 2.

I’ll write this in code (with comments), making it a little bit generic, so when we implement it in a second it’s not too overwhelming. Steps 4 and 5 are swapped around, but you’ll see that’s just a way of saving a little gas.

//Temporarily store the old index because we need to reference it a few times
uint oldIndex = tokenTokenIndexes[2];
//Overwrite the value at oldIndex (2) with whatever is 
// at the end of the ownerTokenIndexes[0xAAA] array (4).ownerTokenIndexes[0xAAA][oldIndex] = 
 ownerTokenIndexes[0xAAA][ ownerTokenIndexes[0xAAA].length - 1 ];
//Update tokenTokenIndexes for whatever token is 
// now at ownerTokenIndexes[0xAAA][oldIndex] (4).tokenTokenIndexes[ownerTokenIndexes[0xAAA][oldIndex]] = oldIndex;
//Update tokentkenIndexes[2] to be the length of
// ownerTokenIndexes[0xBBB], since this will be its new position.tokenTokenIndexes[2] = ownerTokenIndexes[0xBBB].length;
//Add 2 to the end of ownerTokenIndexes[0xBBB].ownerTokenIndexes[0xBBB].push(2);
//Decrement ownerTokenIndexes[0xAAA].length by 1ownerTokenIndexes[0xAAA].length--;

If you’re okay with all that, then I have some good news for you: If instead of hard-coding the 2 we replace it with _tokenId, and we replace 0xAAA and 0xBBB with _from and _to respectively, that’s basically all the code we have to add to our transferFrom function.

The only other thing we need to do is check if the token being transferred was the last item in tokenTokenIndexes[_from], because then we don’t have to worry about shuffling stuff around.

So I’ll write out the whole transferFrom function, including the old stuff, but I’ll put the old stuff in italics so you can focus on the new (which is all at the end):

function transferFrom(address _from, address _to, uint256 _tokenId) public {
    address owner = ownerOf(_tokenId);    require ( owner == msg.sender             
        || allowance[_tokenId] == msg.sender      
        || authorised[owner][msg.sender]          
    );    require(owner == _from);
    require(_to != 0x0);

    emit Transfer(_from, _to, _tokenId);

    owners[_tokenId] = _to;
    balances[_from]--;
    balances[_to]++;    if(allowance[_tokenId] != 0x0){
        delete allowance[_tokenId];
    }

    //=== Enumerable Additions ===
    uint oldIndex = tokenTokenIndexes[_tokenId];    //If the token isn't the last one in the owner's index
    if(oldIndex != ownerTokenIndexes[_from].length - 1){    //Move the old one in the index list
        ownerTokenIndexes[_from][oldIndex] = ownerTokenIndexes[_from][ownerTokenIndexes[_from].length - 1];    //Update the token's reference to its place in the index list
        tokenTokenIndexes[ownerTokenIndexes[_from][oldIndex]] = oldIndex;
    }    ownerTokenIndexes[_from].length--;
    tokenTokenIndexes[_tokenId] = ownerTokenIndexes[_to].length;
    ownerTokenIndexes[_to].push(_tokenId);
}

Note that I decremented ownerTokenIndexes[_from].length before I added the token to the _to mappings. It may seem trivial, but the order is actually important for the case where a person sends a token to his or herself (meaning _to == _from). If we don’t decrement the length first, it would cause tokenTokenIndexes[_tokenId] to be assigned the incorrect value.

If you aren’t using mint or burn functions, then good news, you’re done! But for those of you who are, let’s quickly cover those:

burnToken

The change to burnToken is pretty much the same as the change to transferFrom, except we don’t have to worry about steps 5 and 6 where we added our token to ownerTokenIndexes[_to].

There is a little extra though, because we now have to remove it from tokenIndexes (and replace it with the final element if necessary). This second half follows the same pattern as the first half though, so I think it should be clear enough. Again, I’ll put the old stuff in italics so you can focus on the changes:

function burnToken(uint256 _tokenId) external{
    address owner = ownerOf(_tokenId);
    require ( owner == msg.sender
        || allowance[_tokenId] == msg.sender
        || authorised[owner][msg.sender]
    );
    burned[_tokenId] = true;
    balances[owner]--;    
    emit Transfer(owner, 0x0, _tokenId);    //=== Enumerable Additions ===
    uint oldIndex = tokenTokenIndexes[_tokenId];    if(oldIndex != ownerTokenIndexes[owner].length - 1){        //Move last token to old index
        ownerTokenIndexes[owner][oldIndex] = ownerTokenIndexes[owner][ownerTokenIndexes[owner].length - 1];        //update token self reference to new position
        tokenTokenIndexes[ownerTokenIndexes[owner][oldIndex]] = oldIndex;
    }    ownerTokenIndexes[owner].length--;
    delete tokenTokenIndexes[_tokenId];//This part deals with tokenIndexes
    oldIndex = indexTokens[_tokenId];
    if(oldIndex != tokenIndexes.length - 1){
        //Move last token to old index
        tokenIndexes[oldIndex] = tokenIndexes[tokenIndexes.length - 1];
    }
    tokenIndexes.length--;

}

issueTokens

Lastly we have our issueTokens function. As previously discussed, even if your contract allows issuing of new tokens, it may not do it in batches like mine. But no matter how you’re minting them, if you’ve been following this series to create your contract, your contract should do something like this whenever a new token is created:

uint newId = maxId.add(1); //Using SafeMath to prevent overflows.//Assign the new token its index in ownerTokenIndexes
tokenTokenIndexes[newId] = ownerTokenIndexes[msg.sender].length;//Add the tokenId to the end of ownerTokenIndexes
ownerTokenIndexes[creator].push(newId);//Add the token to the end of tokenIndexes and indexTokens
indexTokens[thisId] = tokenIndexes.length;
tokenIndexes.push(thisId);

Also note: since newId is maxId + 1, make sure you don’t increment maxId until after doing all this new stuff.

For my implementation, the modified issueTokens function is as follows, again with the old stuff in italics. There isn’t such a clean cut between old and new stuff, but I’ll try to make it obvious:

function issueTokens(uint256 _extraTokens) public{
    require(msg.sender == creator);
    balances[msg.sender] = balances[msg.sender].add(_extraTokens);

    uint thisId; //We'll reuse this for each iteration below.    for(uint i = 0; i < _extraTokens; i++){
        thisId = maxId.add(i).add(1); //SafeMath to be safe!        //Assign the new token its index in ownerTokenIndexes        
        tokenTokenIndexes[thisId] = ownerTokenIndexes[creator].length;//Add the tokenId to the end of ownerTokenIndexes
        ownerTokenIndexes[creator].push(thisId);

        //Add the token to the end of tokenIndexes
        indexTokens[thisId] = tokenIndexes.length;
        tokenIndexes.push(thisId);

       
        emit Transfer(0x0, creator, thisId);
    }    //Note: This used to be before the loop 
    // (loop was slightly different).
    maxId = maxId.add(_extraTokens); 

}

And that’s our issueTokens function done!

Wrapping up

So after all that, your token now has the Enumerable extension! We’ve implemented all the new functions, as well as modified our minting, burning and transfer functions. This should make it easier for other people to incorporate your token into their projects, which benefits everybody.

Next time we’ll be testing our Metadata and Enumerable extensions, to make sure everything is working the way it should be.

Next: Jumping into Solidity — The ERC721 Standard (Part 8)