Rejigger LNode lists: add new LNodeList type

Users of Loyc trees must currently refer directly to VList<LNode> so they are dependent on which list implementation is used, which is unfortunate. It is nice to have the freedom of a struct for the node list so that implementations like VList<LNode> are possible, but to refer to VList<LNode> by name prevents me from easily changing list representations. Plus, when I write LNode implementations for other languages, I'm not going to write ports of VList.

Therefore I'm thinking of creating a wrapper struct that provides access to the list's features, but it could have any underlying implementation. This would also allow me to enforce the rule that null is not legal in LNode lists (though C# 8 will also help with this).

A significant disadvantage of this approach is that C# does not support user-defined conversions to interfaces. Therefore, conversion to IReadOnlyList<LNode> would box the wrapper instead of the underlying implementation. Ugh.

Meanwhile, I'd prefer that Loyc.Syntax not depend on Loyc.Collections (170 KB). I have reason to suspect that VLists don't have great performance... I haven't done any measurements, but my performance tests on ALists showed that they struggle to compete with List even in really simple cases like indexer access, as the virtual method call required by the indexer in both ALists and VLists is a significant cost at this low level.

So, what to do? Changing the return type of Args/Attrs to be IListSource<T> is not a good solution either, because it would mandate that clients access the lists through virtual calls, and would break existing code that relies on the simulated mutability of VList<LNode>. I think what's really needed here is a feature of C# where a DLL can create type name aliases, so that clients can refer to LNodeList and this is transformed to VList<LNode> by the C# compiler. I've been convinced for about 10 years now that a powerful type-aliasing feature is needed (in which you could also change the apparent public interface of a type) but I have no control over the Roslyn people.

Another option is to make a LNodeList wrapper struct that does not implement IReadOnlyList<T> (only IEnumerable<T> for Linq) but has an implicit conversion to the underlying list type so that if you pass a list where IReadOnlyList<T> is needed, the conversion succeeds. This isn't great either... conversion to IEnumerable<T> is still wrong-boxed and Linq-to-lists doesn't work. I just can't catch a break from C# sometimes...

But if my list implementation were not VList<T>, what would it be? Hmm. Perhaps a raw array, sized exactly, is the only thing more attractive than VList<T>, because it allows both fast read access and low memory usage. So I'd make a raw-array wrapper struct (using the existing InternalList class to help it implement itself), and whenever you add an item, it allocates a new array (as each array must be immutable to enable memory sharing).

This implementation implies your code should avoid calling LNode.PlusArg(a) many times in a row to build a list of statements. If your code currently builds a VList<LNode> or WList<LNode> to build up a long list of statements, that's okay - don't change the type to LNodeList, but you could change it to List<T> and convert to LNodeList at the end (is an implicit conversion warranted to make this easier for existing code?) This implementation also makes me want to not provide the simulated mutability that VList<T> provides... or to provide it, but mark it [Obsolete].

VList has special constructors for 1 or 2 items; LNodeList could do the same for 1, 2, 3, or N items. (I'm looking at the constructor VList(T[] array) and scratching my head wondering why I didn't mark it params!)

Any thoughts @jonathanvdc?

qwertie / ecsharp

Rejigger LNode lists: add new LNodeList type #100