Immutable dynamic arrays

[nventuro]

Abstract

Add native support for dynamic immutable arrays, with a length defined at construction time (up to a maximum) and automatic bounds checks.

Motivation

immutable is a fantastic feature, allowing for highly efficient configuration access without forcing developers to use hardcoded constants, making testing and deployment much easier and enjoyable. However, there is zero support for any kind of arrays.

What I describe can be manually implemented today in solc >0.7, but it leads to a very large amount of error-prone boilerplate. No alternative exists for gas-efficient access to these values. You can look at production code using this pattern here. Using the proposed features in such a contract would reduce sour code size to less than a third of the original length, while also increasing auditability and maintainability.

Specification

'Dynamic' may be a confusing term. What I mean is that the contents and length would be dynamically defined at construction time. Read access with bounds check using the [] operator and .length would both be supported. This feature set is essentially the same as that of memory arrays, except memory arrays can have their contents mutated.

Truly dynamic immutable arrays would be quite an undertaking as the length of the runtime code would be dependent on construction arguments, but I'd argue that going that far is unnecessary. In all applications I've seen, there is a compile-time known maximum array length.

The proposed feature could therefore work as follows:

• the user declares an immutable array with a maximum length N (e.g. uint256[] private immutable(50) foo)
• the compiler allocates runtime code equivalent to N+1 immutable values, for each element plus the total length
• during construction, both foo.length and foo[i] can be used to write (not read) to the array. For simplicity, we could allow for each value to be written multiple times and perform no bounds check (other than .length <= N and i < N).
• during runtime, foo.length returns the array's length and foo[i] performs bounds check with foo.length.

Backwards Compatibility

This is a new feature using brand new (as of today invalid) syntax, so there should be no backwards compatibility implications.

---

Extra

Code samples

As mentioned above, this can be implemented today using standard Solidity. See for example how one might declare and use an up to 10 tokens array:

uint256 private immutable _totalTokens;

IERC20 internal immutable _token0;
IERC20 internal immutable _token1;
IERC20 internal immutable _token2;
IERC20 internal immutable _token3;
IERC20 internal immutable _token4;
IERC20 internal immutable _token5;
IERC20 internal immutable _token6;
IERC20 internal immutable _token7;
IERC20 internal immutable _token8;
IERC20 internal immutable _token9;

constructor(IERC20[] memory tokens) {
    uint256 numTokens = tokens.length;
    require(numTokens < 10);
    _totalTokens = numTokens;

    _token0 = numTokens > 0 ? tokens[0] : IERC20(0);
    _token1 = numTokens > 1 ? tokens[1] : IERC20(0);
    _token2 = numTokens > 2 ? tokens[2] : IERC20(0);
    _token3 = numTokens > 3 ? tokens[3] : IERC20(0);
    _token4 = numTokens > 4 ? tokens[4] : IERC20(0);
    _token5 = numTokens > 5 ? tokens[5] : IERC20(0);
    _token6 = numTokens > 6 ? tokens[6] : IERC20(0);
    _token7 = numTokens > 7 ? tokens[7] : IERC20(0);
    _token8 = numTokens > 8 ? tokens[8] : IERC20(0);
    _token9 = numTokens > 9 ? tokens[9] : IERC20(0);
}

function getTokenIndex(IERC20 token) public view returns (uint256) {
    if (token == _token0) { return 0; }
    else if (token == _token1) { return 1; }
    else if (token == _token2) { return 2; }
    else if (token == _token3) { return 3; }
    else if (token == _token4) { return 4; }
    else if (token == _token5) { return 5; }
    else if (token == _token6) { return 6; }
    else if (token == _token7) { return 7; }
    else if (token == _token8) { return 8; }
    else if (token == _token9) { return 9; }
    else {
        revert("Invalid token");
    }
}

This is of course very error-prone and hard to maintain, but it is the best way to get the desired behavior. With the suggested feature, we get the exact same bytecode size and performance using the following code:

IERC20[] internal immutable(10) _tokens;

constructor(IERC20[] memory tokens) {
    _tokens.length = tokens.length;
    
    for (uint256 i = 0; i < tokens.length; ++i) {
      _tokens[i] = tokens[i];
    }
}

function getTokenIndex(IERC20 token) public view returns (uint256) {
  for (uint256 i = 0; i < _tokens.length; ++i) {
    if (_tokens[i] == token) {
      return i;
    }
  }

  revert("invalid token");
}

[ylv-io]

love the code sample

[jaglinux]

Since it's really not dynamic array, better syntax would be
IERC20[10] internal immutable _tokens;

[ekpyron]

Thanks for the issue - this has been on our longer term agenda ever since we introduced immutables :-) (I'm actually surprised that it wasn't requested much earlier ;-)).
At least I hadn't considered a maximal length for such dynamic immutable arrays - that's an interesting idea that could make this easier (but I could also imagine that fully dynamic arrays would not be that much harder actually).

One thing to be aware of is that this will not be as cheap as value-type immutables, because we won't be able to inline the values directly - in most cases I'd expect the values to end up being codecopyd to memory before use, which has some overhead (although it will be significantly cheaper than storage of course).

In retrospect, I'd much rather have introduced what we now have as immutables as a new data location called code (besides memory, calldata and storage), which would convey more clearly what actually happens and would make it less of a concern to allow multiple assignments during construction (there's no technical reason for disallowing that - during construction the values just live in memory - it's just contrary to the meaning of "immutable"...)

[nventuro]

(but I could also imagine that fully dynamic arrays would not be that much harder actually).

I haven't given this much thought, so I can't quite comment on complexity of such an implementation. In all scenarios where I'd use this however, a maximum length (which also means there's some wasted bytecode on the unused slots) is good enough.

One thing to be aware of is that this will not be as cheap as value-type immutables, because we won't be able to inline the values directly - in most cases I'd expect the values to end up being codecopyd to memory before use, which has some overhead (although it will be significantly cheaper than storage of course).

Yes, while the bytecode size for immutable variables in my example would be the same, the actual code that accesses them would not (both size and gas would differ). I imagine instead of a push we'd just have codecopy + mload (with no need to expand allocated memory), which would use very little gas.

(except for .length, which would be a push)

[simontianx]

Just would like to bring up a particular use case of mapping to an immutable array like in mapping(uint256=>uint256[10] immutable) data. This may find applications in ordered NFT batch standards.

[nventuro]

Hm, I'm not quite sure how you'd do mappings as they are currently extremely storage based (since they key is just a 256 bit hash, there's no notion of the 'capacity' of the map). But you'd likely be able to implement such a thing yourself using multiple immutable arrays (a few with the actual data, and one that tells you which mapping to use), though it'd require some boilerplate similar to the one in my code sample, even if this feature was implemented.

I'd limit discussion here to the feature discussed in the opening post.

[simontianx]

Hm, I'm not quite sure how you'd do mappings as they are currently extremely storage based (since they key is just a 256 bit hash, there's no notion of the 'capacity' of the map).

I think it's similar to mapping(uint256=>uint256[10]) data;, except the values in a mapped array cannot be modified.

But you'd likely be able to implement such a thing yourself using multiple immutable arrays (a few with the actual data, and one that tells you which mapping to use),

Is this an immutable struct?

[nventuro]

Hi @ekpyron! I keep running into scenarios where such a feature would be extremely useful :) Is there an estimated timeline for this feature? Is there any work the community can do to push it forward (e.g. come up with a more detailed spec, begin implementation work, etc.)?

[ekpyron]

@nventuro Unfortunately, there hasn't been progress on this and we don't have an estimated timeline for it. For now I moved it up in our design backlog, which will hopefully lead to us discussing it in one of our calls next week.

The main problem is that the implementation of this won't be trivial and I guess probably either @chriseth or I would have to do it and I'm not sure when we'll find the time.

Conceptually, the main question I think is whether we want to enforce an "assign once and do not read" logic for dynamic immutable types like we do for immutables of value type.
It would probably in fact be easier to implement this, if we were to treat the reference-type immutable just like a memory variable during the constructor and in that sense allow reassignments and reads from it. However, it'd be counterintuitive for them to be called immutable while they can be reassigned, even if only during creation (@chriseth objected that to such plans in the past IIRC).

[ekpyron]

We just discussed this in our design call and decided to make it a goal for Q2 2022.

Current rough sketch of a plan is:

• start off with an implementation for bytes only and then extend
• the length is dynamic without syntactic maximum and stored as if it was an immutable of value type
• we don't call them immutables, but introduce a data location code for them that can be passed around by reference
• the above should make cheap slicing feasible
• code variables during construction will behave just like memory variables, i.e. they will be normally writable and readable in memory during contract creation.

However, we will probably have some iterations on this plan as we start implementing this.

[nventuro]

The code part sounds very interesting! Looking forward to how this turns out, it'll likely be the tipping point that makes me migrate to 0.8 😁

[frangio]

A code location would be an awesome addition. I was going to say before that "assign once and do not read" is not the crucial part that people care about. It's all about the efficiency of access.