2

I am trying to implement a recursive data structure. The following code does not compile in browser-solidity:

pragma solidity ^0.4.4;
contract TestContract {
    struct Item {
        uint someUint;
        Item[] internalItems;
    }
    Item[] items;
    function TestContract() {}
    function test() {
        Item memory item;
        items.push(item);
    }
}

I realize that recursion is discouraged in blockchain environments, but in this particular case the item is essentially empty, thus I did not expect any infinite recursion to occur. I am getting different errors in Chromium and Firefox (both in Ubuntu 16.04).

Chromium 53.0.2785.143 says:

Uncaught JavaScript exception:
RangeError: Maximum call stack size exceeded

(and sometimes it even loads a CPU core to 100% and freezes)

Firefox 49.0.2 says:

Uncaught JavaScript exception:
InternalError: too much recursion

A have two questions:

  1. Does browser-solidity fully implement the Solidity compiler spec? If so, how can the error message depend on which browser I am using? If not, what is the reference compiler implementation?

  2. Is there a way to implement recursive data structures in Solidity? Something like a tree, a linked list, etc.

0

This is an open bug in the Solidity compiler itself, unrelated to browser-solidity or the Javascript runtime: https://github.com/ethereum/solidity/issues/736

1

It appears to me that the compiler itself got into infinite recursion, and therefore crashed. The reason you get different errors is that Firefox and Chromium handle infinite recursion differently.

To quote the Solidity docs:

It is not possible for a struct to contain a member of its own type, although the struct itself can be the value type of a mapping member.

There's a simpler way to do recursive data structures. Give each Item some form of ID (either an incrementing number or a hash of the data.) Then you can store just references to said IDs. For example:

struct Item {
    uint ID;
    uint someInt;
    Item[] internalItems;
};
mapping (uint => Item) public Items;
uint public nextID;
// Some time later...
uint newID = nextID++;
Items[newID] = new Item(newID, _someInt);
oldItem.internalItems.push(newID);

This is a somewhat basic method. The more complicated Items are, the more it makes sense to actually have some function (say, createItem()) that does this all properly. I've also cached this "homemade pointer" on the struct itself in this example. If you give the struct as an argument to some function, you won't have the uint that identifies it otherwise. If you use a hash system, you can go without this as long as you can regenerate the hash.

Additionally, this will allow you to create circular data structures, such as a cyclic graph.

There is another important benefit to this method. Getters and recursive structs do not mix. If you call such a getter from the outside world, it will not return any field that is a struct-in-a-struct. This is also true of unbounded-length arrays and mappings inside of structs.

If you ever plan to have one of these Items be public, you won't be able to easily access the contents of any internal Items. However, Solidity will happily return a fixed-length array to the outside world. If you're willing to accept a maximum number of internal Items (for example, ten) then you can very easily have a dapp read an Item and iterate down the tree.

You might also be interested in Libraries, which would allow you to create very natural-looking data structures.

  • "actually cache this "homemade pointer" on the struct itself" - could you elaborate on that please? – Sergei Tikhomirov Nov 16 '16 at 14:03
  • You can conceivably enter a situation where you have access to the struct, but not the uint or hash that identifies it. This is especially possible with libraries, since you give the library functions "real" pointers. Since you can't "take the address" of the struct in this situation, caching the uint or hash that points to it before hand will help greatly. – Matthew Schmidt Nov 16 '16 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.