Vyper: VIP: Dynamic Arrays w/ Sizing

[fubuloubu]

Motivation

For inter-operation with Solidity and other languages that do not take Vyper's conservative approach to arrays, it is important to have a syntax that retains our principle of protecting against gas exhaustion attacks (and gas estimation) while encoding as a dynamic array type via the ABI.

Specification

This looks like defining a new "meta" type called Array:

@public
def foo(a: Array[uint256, 1:5]):
    ...  # a must have between 1 and 5 elements

@public
def bar(a: Array[uint256, 4]):
    ...  # a must have between 0 and 4 elements

In general, using this syntax, one can describe the minimum and the maximum of what a method will accept for a dynamic array. Min and max size have to be specified via min_size:max_size after the type that a dynamic array takes. If only a number is specified, min_size is assumed to be 0. If both are specified, the restriction min_size < max_size is enforced. Both can be a named constant.

When the calldata is parsed by the method, it will do an array bounds check to ensure the array's len is within the maximum and/or minimum specified. It will then operate on that array as a dynamic array, for example using he for item in list syntax for iteration.

This type of list will have limited abilities versus a static array. For example, it might not be allowed to be passed as an argument to an inner private function or to be referenced by index directly (these are possibilities, whatever the compiler needs to do to ensure safe usage of these types is TBD). This type of list may also not be allowed to be a state variable declaration (out-of-gas lock bugs possible), and potentially be disallowed from memory declaration usage as well.

Also, the built-in function len(...) should be expanded to allow the ability to query the current length variable of an Array type (currently it only queries the size of bytes objects)

Backwards Compatibility

The current syntax for bytes[N]/string[N] uses this same behavior, so to make both syntax consistent we are changing to Bytes[N]/Bytes[M:N] and String[N]/String[M:N].

Dependencies

No dependencies

Copyright

Copyright and related rights waived via CC0

[jacqueswww]

Note from meeting: bytes[min:max] min & max will have to be forced syntax, for readability / clarity.

[fubuloubu]

Something like Array(type, max_size=5) might be more readable:

@public
def foo(a: Array(uint256, max_size=5)) -> uint256:
    # reverts if len(a) > 5
    sum: uint256 = 0
    for i in a:
        sum += i
    return sum

[rayrrr]

Array(type, min_size=1, max_size=5) could handle both the foo and bar cases from the spec in the description. Sounds good to me.

[rayrrr]

@fubuloubu et al., veteran Pythonista new to Vyper here. I'd happy to put up a PR with this implementation of Dynamic Arrays w/size boundaries if one of you can clue me in as to where exactly in the codebase it should go, and possibly point me to an existing type syntax example in the code for another datatype. Thanks!

[fubuloubu]

@rayrrr really appreciate that! We've been waiting on the type checker refactor as that will significantly change how we define new syntax (and hopefully make it easier and more scalable), which make this much easier to drop and go. We already have some dynamic types (bytes and strings), that I was hoping to refactor to this new paradigm (bytes[N] => Bytes(max_size=N) and string[N] => String(max_size=N)). It should also hopefully be possible to leave the kwarg in or out

[rayrrr]

Okay, sounds like a bit of yak shaving to do here...how can I and/or others help with the type checker refactor to help move this forward?

[fubuloubu]

@rayrrr Perhaps we can talk about this work in our next meeting? #1941
Also, would you be willing to help out with reviewing the type checker series of PRs for ergonomics and clarity? PR(s) incoming soon™

Note: Updated the syntax in the original proposal to reflect the latest thought process.

[fubuloubu]

Note: reverted Accepted because of significant changes to proposal

[rayrrr]

@rayrrr Perhaps we can talk about this work in our next meeting? #1941
Also, would you be willing to help out with reviewing the type checker series of PRs for ergonomics and clarity? PR(s) incoming soon™

Yes to both.

[fubuloubu]

Note: for v0.2.0, ensure that Bytes/String is implemented, but can differ on Array until next patch release

[fubuloubu]

Breaking updates made in #2080, removing from 0.2.0 milestone