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!

[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 OpenZeppelin/openzeppelin-contracts#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 - #869 (comment) - #869 (comment) ?

[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.

[axic]

Here are three very simple functions which can come handy in many applications:

function min<T>(T a, T b) pure internal returns (T ret) {
  ret = (a < b) ? a : b;
}

function max<T>(T a, T b) pure internal returns (T ret) {
  ret = (a > b) ? a : b;
}
 
function abs<T: T.isSigned>(T a) pure internal returns (T ret) {
  ret = (a < 0) ? -a : a;
}

While the abs case does not strictly require the capability to enforce it is on a signed type (the < 0 may be a compile time failure with an unsigned type), it certainly helps clarity. Similarly to T.isSigned we could have something like T.toUnsignedType (aka C++ has), if we wanted to do type conversion at the end of abs.

Should we have more type inspection capabilities, we could introduce further restrictions on what types are accepted, such as isIntegral, isFixedPoint, etc. However even the above version would be sufficient to be used with int/uint/fixed types, while others would just throw a compile time error for invalid comparison operator.

Another questions springs to mind: what about variadic functions? min could be nice with variadic number of arguments, though that is something we may not actually want.

[aathan]

I think generics are a bit moot until the environment also has a reasonably automated mechanism for code size mitigation or alternatively, must come with very good control regarding code placement, libraries, linking etc. Generics-style programming tends to instantiate lots of type specializations and therefore lots of code. Solidity contracts are still very highly hand-tuned when it comes to this stuff. If the EVM is unlikely to remove the existing arbitrarily small code size restrictions and proxies continue to be "the way" to release large feature-rich codebases, IMHO the language will need to include first class support for those patterns.

Already my experience with Solidity is that you can't treat libraries like OZ the same way you do libraries in other coding environments. If you are too generous with your imports or to "OO" / declarative in your mindset, your contract size goes boom and then you're spending lots of time optimizing things back down to the minimal implementation that works well in practice.

[MicahZoltu]

If the user needs two data structures for two different types, then making them manually type out both by hand or copy/paste the implementation isn't saving anyone gas over having the compiler generate the two implementations. Even in the worst case where the compiler doesn't reuse any code between the implementations, I think that is still no worse than what most users would come up with.

Gas optimizations are good, but I don't think that is a good reason for not implementing a feature that would provide better code reuse (and thus reduce chance of bugs).

[aathan]

No doubt or argument that templating is a powerful tool that reduces copy pasta and makes for a better user experience overall. My comment was not at all about gas, but rather, about contract code size and about the coding style that generics and other sophisticated language features promote. As currently constructed the realities of the EVM execution environment are so constrained that code frequently has to be hand-tuned not for gas savings but for code structure and size. I have found that in practice, for complex implementations, such as those likely to benefit from generics, I end up having to break encapsulation, do some hand-inlining, etc (and here I'm just theorizing...) perhaps because instructions to marshal function parameters, manage limited stack size, etc end up simply being more numerous (irrespective of the gas cost).

With that clarification: E.g., what I meant by very good control regarding code placement might include being able to specify that a specific generic instantiation should be implemented in a separate link unit; e.g., a contract expected to be called via delegatecall (as in a proxy), such that storage, memory etc is in common, but code space is not. This might further require the language to understand proxy patterns and incorporate that into its linkage model; or more generally appropriate features to easily specify where generic specializations are made available (including e.g. library contracts to be deployed alongside the "main" contract).

Further discussion on this might be better placed in a discussion forum other than the issue tracker.