Implementing Generics

[charsleysa]

@tgiphil @kiootic

I have been studying how generics work and I think I have come up with a solution that works just like the CLR runtime.

Every time a generic is used we duplicate the entire tree and replace the generics with either a value type or a special reference pointer.

So when we encounter the instantiation of a generic we simply duplicate it's tree (if there already isn't a duplicate tree with that particular specific) and replace it by the type specified such as int, float, enum, and for reference types we just have a single version for all of them which just has special pointers to the objects.

I think we can manage this through a few simple modifications of the existing type system and adding in a generic-to-specified duplicator which swaps out generics and adds in specifics and marks the duplicated tree as such.

What do you guys think?

I'm looking at starting development on this in July during my semester break.

---

Want to back this issue? Place a bounty on it! We accept bounties via Bountysource.

[tgiphil]

@charsleysa Sounds good.

[charsleysa]

@tgiphil what exactly are we missing in terms of generics?
Most if not all of the functionality is already there.

[tgiphil]

@kiootic can answer that better than I could.

[charsleysa]

@tgiphil well until then I've made a few modifications that fixes the problems with Metadata not knowing about generics. All tests pass so I will merge into main repo.

[kiootic]

@charsleysa At the moment, generic type/method instantiation are handled by the type system when loading assemblies. It might be better to move that part to the compiler. Also there is code duplication due to copies of type are produced for each generic instantiation. It would be beneficial to implement your proposal.

[charsleysa]

@kiootic while my solution my be better I don't think I have the necessary skills to be able to implement it and so I'll be leaving it for now and focussing on finishing the Runtime side of the new Metadata System.

The current solution works which is the important part, optimization can be done afterwards.

[charsleysa]

I have looked into this some more and the method I proposed would only work when all the generic parameters are reference type.

If even one generic parameter is a value type then another duplicate would have to be made that can't share the same.

While we would benefit from smaller binaries I think the amount of work that it would currently take would outweigh the benefits received. (Currently binaries are less than 2MB).

[tgiphil]

In the short-term, the linker could maintain a hash of the binary code of the method. And upon a collision, each byte could be compared. If an exactly match is found, the methods are the same. The linker then only emits one of the methods and the other method(s) are re-directed to the address of the emitted method.

The upside of this short-term solution is that it's almost trivial to implement and immediately reduces code bloat due to generics (and possibly other simpler methods as well). The downside of this method is the compiler continue to do work that is later discarded that could have been avoided by an analysis of the generic type usages.