From c32e6f8d5f5dec98e69be02f4b1c1b176a14b773 Mon Sep 17 00:00:00 2001 From: Erik Kundt Date: Mon, 1 Oct 2018 19:54:58 +0200 Subject: Documents storage layout of mappings and dynamic arrays. --- docs/miscellaneous.rst | 29 +++++++++++++++++++++++------ 1 file changed, 23 insertions(+), 6 deletions(-) (limited to 'docs') diff --git a/docs/miscellaneous.rst b/docs/miscellaneous.rst index 12603f2e..8cc52c8f 100644 --- a/docs/miscellaneous.rst +++ b/docs/miscellaneous.rst @@ -34,18 +34,20 @@ Statically-sized variables (everything except mapping and dynamically-sized arra The elements of structs and arrays are stored after each other, just as if they were given explicitly. +Mappings and Dynamic Arrays +=========================== + Due to their unpredictable size, mapping and dynamically-sized array types use a Keccak-256 hash computation to find the starting position of the value or the array data. These starting positions are always full stack slots. -The mapping or the dynamic array itself -occupies an (unfilled) slot in storage at some position ``p`` according to the above rule (or by -recursively applying this rule for mappings to mappings or arrays of arrays). For a dynamic array, this slot stores the number of elements in the array (byte arrays and strings are an exception here, see below). For a mapping, the slot is unused (but it is needed so that two equal mappings after each other will use a different hash distribution). -Array data is located at ``keccak256(p)`` and the value corresponding to a mapping key +The mapping or the dynamic array itself occupies a slot in storage at some position ``p`` +according to the above rule (or by recursively applying this rule for mappings of mappings or arrays of arrays). For dynamic arrays, +this slot stores the number of elements in the array (byte arrays and strings are an exception, see :ref:`below `). +For mappings, the slot is unused (but it is needed so that two equal mappings after each other will use a different +hash distribution). Array data is located at ``keccak256(p)`` and the value corresponding to a mapping key ``k`` is located at ``keccak256(k . p)`` where ``.`` is concatenation. If the value is again a non-elementary type, the positions are found by adding an offset of ``keccak256(k . p)``. -``bytes`` and ``string`` store their data in the same slot where also the length is stored if they are short. In particular: If the data is at most ``31`` bytes long, it is stored in the higher-order bytes (left aligned) and the lowest-order byte stores ``length * 2``. If it is longer, the main slot stores ``length * 2 + 1`` and the data is stored as usual in ``keccak256(slot)``. - So for the following contract snippet:: pragma solidity >=0.4.0 <0.6.0; @@ -58,6 +60,21 @@ So for the following contract snippet:: The position of ``data[4][9].b`` is at ``keccak256(uint256(9) . keccak256(uint256(4) . uint256(1))) + 1``. +.. _bytes-and-string: + +``bytes`` and ``string`` +------------------------ + +``bytes`` and ``string`` are encoded identically. For short byte arrays, they store their data in the same +slot where the length is also stored. In particular: if the data is at most ``31`` bytes long, it is stored +in the higher-order bytes (left aligned) and the lowest-order byte stores ``length * 2``. +For byte arrays that store data which is ``32`` or more bytes long, the main slot stores ``length * 2 + 1`` and the data is +stored as usual in ``keccak256(slot)``. This means that you can distinguish a short array from a long array +by checking if the lowest bit is set: short (not set) and long (set). + +.. note:: + Handling invalidly encoded slots is currently not supported but may be added in the future. + .. index: memory layout **************** -- cgit v1.2.3