Solidity: templates / generics

[chriseth]

Solidity should support template types / generics for contracts, libraries, functions and structs.

The syntax should be as follows:

library listImpl[T] {
  struct List { T[] elements }
  function append(List storage self, T _e) {
    self.elements.push(_e);
  }
}

In general, at every point where a new library, contract, function or user-defined type is defined, you can suffix the name with [T1, T2, ...].

Inside the library, contract, function or user-defined type, the identifiers T1, T2, ... are bound to whatever they will be used with later. This means that type checking will not be done on those at the point where the template is defined.

At the point where a templated name is used, you have to prefix the name with [...], where inside the square brackets, an arbitrary expression is allowed. This will cause the template itself to be type-checked again, replacing the identifiers T1, T2, ... with the respective values.

On the implementation side, this means that the AST annotations now have to be context-sensitive. Every template variable will be assigned a compiler-global identifier. The annotation() function will receive an argument where these identifiers receive actual expressions. This argument will be transferred downwards in the AST during the second type checking phase.

[VoR0220]

any chance we can go full javascript on this and do this by using var as the generic type with a typeOf function to weed out unwanted types in the generics function?

[chriseth]

@VoR0220 I think what you are proposing is to basically do type checking at runtime, which is not a good idea in my opinion.

[VoR0220]

no it's more of a syntactic thing I think... could not [T] be substituted by var ?

[SCBuergel]

Any progress / timeline on this one? Seems to be a fantastic feature that is been around here for a while.

[axic]

A larger example from https://www.pivotaltracker.com/story/show/89907258:

Type-templated contracts, libraries, structs and functions, where type names are given after struct name in [] and concrete types in the same way at the point of instantiation.
Example:

struct Set[T] {
  uint m_lastIndex;
  mapping(T => uint) m_indices;
  mapping(uint => T) m_elements;
  uint constant notFound = 0;

  function insert(T _element) {
    if (find(_element) != notFound) return;
    uint index  = ++m_lastIndex;
    m_elements[index] = _element;
    m_indices[_element] = index;
  }
  function find(T _element) returns (uint index) {
    return m_indices[_element];
  }
  function remove(T _element) returns (bool removed) {
    uint index = m_indices[_element];
    if (index == notFound) return false;
    delete m_indices[_element];
    delete m_elements[index];
    return true;
  }
  function remove(uint _index) returns (bool removed) {
    if (_index == notFound) return false;
    delete m_indices[m_elements[_index]];
    delete m_elements[_index];
    return true;
  }
}

contract C {
  Set[address] m_owners;
}

Implementation details: Obviously, we cannot do type checking on the template struct, but only at the point of instantiation. This means that we need to create a kind of parellel AST node that contains the actual types. This might be the point where we separate the type checking from the AST and move it to its own visitor.

[chriseth]

@axic the implementation idea here was to use the annotation() function and provide as parameter to it the values for the template parameters. Whenever annotation(x) is not yet defined, run type checking over it again.

Having said that: I think the fastest way to achieve something like this outside the compiler is to use a simple preprocessor that only does string replacement, i.e. Set<address> -> Set_generic_address and then library Set<T> { ... } is copied to something library Set_generic_address { ... } where every T in {....} is replaced by address.

Perhaps that could be a feature request for truffle?

[nickbclifford]

Would this mean that things like uint[] would become Array<uint> and mapping (address => uint) would become Mapping<address, uint> or would generics be for user-defined types only?

[Skyge]

So which method should we take? outside the compiler or inside? Maybe we can implement two methods at the same time, and then we can find out which one is better?
OK, if I want to achieve this outside the compiler at first, what should I notice and what is the key point to be solved? I think I should learn some thing about the AST(Abstract Syntax Tree) at first, shouldn't I?

[Skyge]

@chriseth @axic @elopio OK, this issue really has existed for a long time, so now I will push it forward, please do me a favor, listing more details. BTW, my issue is related to this one, but I think it is much easier.

[chriseth]

The reason why this has been open for quite some time is because it is a really delicate matter whose pros and cons have to weighed carefully.

[Skyge]

Absolutely, we really should weighed carefully for all changes, but you know, there are not only many things to solve at now, but also more and more issues come out, besides that, we should go forward on schedule, in a word, all things are extremely urgent. I hope to contribute my humble efforts to you.

[chriseth]

We of course appreciate your help! I think all the details we have worked out so far are here. Do you have specific questions? One of the problems we might run into is function overloading, for example.

[mwaeckerlin]

@VoR0220 I think what you are proposing is to basically do type checking at runtime, which is not a good idea in my opinion.

Nope. In C++, template types are strictly checked at compile time. Templates do not require runtime type checking.

[Skyge]

I have got to say, it is hard for me rather than a little complex as I expected to achieve overloading, so it is more suitable for experienced people. I will move to help at other issues, but I will also keep my eye on this question.

[Amxx]

I've been working a bit on a solution for pre-compile template generation. It's very far from perfect, but here is a link to the repo in case anyone sees a point to it and want to use / improve it
https://github.com/Amxx/SolStruct

[chriseth]

Nice!

[chriseth]

Since public functions of libraries are not really used, we do not have the problem of linking to the correct templatized library. We could allow templates only for libraries that do not have public functions.

Another step would be to only allow templatized functions. This would remove the possibility to define templatized structs - which might also be a good simplification.

[frangio]

remove the possibility to define templatized structs

I don't think this would be useful. Templates are mostly used to build generic data structures.

[chriseth]

@frangio this is probably true. So I think restricting to libraries with only internal functions is a good first step.

Which template libraries come to mind that are really useful and efficient enough?

[chriseth]

Some implementation notes for the version of templatizing full libraries (including their structs):

We parse templatized libraries, but skip them at first for reference resolution. After reference resolution, we add a loop:

loop:

• search for all references to templatized libraries and store the types for the template parameters in a map
• break if no new template parameter values are discovered
• re-run reference resolution on the libraries for all values for the templatized parameters

For the rest of the compilation process, whenever a templatized library is encountered, we run all checks for all values of the parameters. AST annotations are stored relative to the values for the template parameters (by the AST id of the template parameter).

Some type constructors (that reference declarations inside templatized libraries, for example) will need the template parameter values.

[ekpyron]

What about this:

• For each templatized library we store a map from type to AST nodes containing versions of the library specialized for that type.
• Whenever we encounter a reference to a templatized library, we either resolve to the specialized AST node in the map or create a specialization and store it in the map.

The rest of the compilation process can continue without modification, as if there were no templatized libraries at all.

In any case, we need to take care about self-referential templates, e.g.
library L[T] { struct S { T x; } function f() internal { L[L[T].S].f(); } }

[ekpyron]

If we go for specialized copies of AST subtrees, we should probably still annotate such AST nodes with the "source template" and specialization type and support that in error messages (e.g. TypeError: blahblah in specialization of L for type int.)

[chriseth]

Similar idea, but without libraries: https://github.com/ethereum/solidity/issues/9063

[chriseth]

If we want to use the <-syntax for templates, we could borrow an idea from rust (I hope I understood it correctly):
At expression context, you move from the identifier to specifying its template arguments by using . (in rust it is ::):

function add<T>(T _a, T_b) pure returns (T _c) {
  return _a + _b;
}

function useTemplate() pure {
  add.<uint>(x, y);
}

For us, we also have to use this when we specify types at statement level - so maybe we could require the . everywhere except in the declaration of the template itself:

struct IterableMap<Key, Value> {
  mapping(Key => value) data;
  Key[] keys;
}
function f(IterableMap.<uint, bytes> storage _map) {
...
}

[leonardoalt]

Sounds good, although visually I think I prefer ::<>

[Marenz]

Example from D:

void templateFunction(TemplateType)(TemplateType _parameter)
{
..
}

calling:
templateFunction!uint(34);

void templateFunction2(TemplateType, TemplateType2)(TemplateType _parameter, TemplateType2 _parameter)
{
..
}

calling:
templateFunction!(uint, size_t)(34, 24);

[Marenz]

Also an even further shorthand for defining a function:

void templ(auto param) {..}

[chriseth]

Here is another example of how templates might be used: https://gist.github.com/chriseth/d8bf126817fa236c0406c130433a0a7e

I think we have to force people to specify the data location, so data location cannot be part of the template. In the worst case, two/three templates have to be written. If something turns out to be a value type, it does not matter if a data location is specified.

[chriseth]

Suggested by @cameel : there should be a way to write templates for data locations.

One way to do this would be to have a keyword that means "any data location". For function parameters, it would mean "generate one function for each combination of data locations that are used". For local variables, it would mean "infer the data location from the context".

[franzihei]

Heads-up for all people involved in this issue so far:

We are conducting a language design call to ideate around the topic of templates / generics for Solidity on Wednesday, 2nd of September at 5PM CEST. You can find all relevant information and a link to the meeting invite here.

[MicahZoltu]

I can't make the call, but my number one desire from generics is the ability to create some datastructure primitives like linked lists, skip lists, doubly linked lists, iterable maps, sets, etc. (yes, mostly collections). On a number of occasions I have tried to write a general purpose datastructure and ended up having to copy/paste and mutate it every time I wanted to reuse it because the datatypes of the datastructure differ between use cases.

See https://github.com/OpenZeppelin/openzeppelin-contracts/pull/2072 for some discussion around how the lack of generics resulted in no standard EnumercableMap being created in a very popular base contract library. 😢

[chriseth]

Too bad you cannot make the call, but your input is already very useful! Do you have an opinion about the problem of data locations - https://github.com/ethereum/solidity/issues/869#issuecomment-668767160 - https://github.com/ethereum/solidity/issues/869#issuecomment-676517663 ?

[MicahZoltu]

Generic constraints would be nice, and allow for better error messages. For example, I may want to constrain to "comparable" things so I can do a < b for one of my generic parameters but another one may be unconstrained so I can assign a tuple to it (which presumably isn't comparable). I have become quite happy with TypeScript's generics lately, they are type erased and pretty powerful. While they have a few soundness issues, most of them exist for legacy reasons not out of necessity.

I don't have an opinion on the data location question. Could this be solved with generic constraints mentioned above? <T is storage, comparable, U is calldata, V> or something? In this example, V could be any storage type while T and U are constrained as to what storage type they can be. The compiler would then be able to type check the generic without having to look at call sites, and the callsites could get nice clean fast-failures when they do the wrong thing.

[MicahZoltu]

It probably says above but I didn't see it when glancing through... will this be C++ style templates/macros, or C#/Java/TypeScript generics? That is, will the compiler essentially inline the template as a pre-compile step, or will the generics be statically analyzed as their own datastructure and then the callsite type checking merely verifies constraints?

[chriseth]

Since Solidity's type system is not structured enough, I fear we have to do one full analysis pass per instantiation.

[alejoamiras]

It's way out of my technical ability to comment on how to implement this, but as a fellow programmer, I was actually googling on how to use templated params in solidity. So it's needed, and it would be awesome.
TY for your work guys.

[franzihei]

Thanks to all that joined the language design discussion just now! Here's a link to the collaborative notes: https://hackmd.io/@franzihei/BkyqUzpmv.