Add ImmutableMap and ImmutableSet and use them in the SDK

[ncorai]

I'd suggest adding ImmutableMap, ImmutableSet, MapBuilder and SetBuilder to the ceylon.collection module.

Then update the following places to use them instead of the current mutable versions:

• WebSocketProtocolHandshakeHandler: HashSet (internally)
• Sql: HashMap (returned by rows and firstRow)
• createSystem: HashMap (passed to newFileSystem)
• FormDataBuilder: HashMap (returned as FormData's parameters and files)
• RequestImpl: HashMap (returned by readQueryParameters)

In HashMap itself, the tradeoff between inheriting the LazyMap implementation of inverse and mapItems from Map and implementing materialized versions could be debated. At the very least, those two methods should have performance warnings in their documentation. The same concerns would apply to ImmutableMap.

There are a few other places that build MutableList and MutableMap that, in my view, would be better served by returning immutable versions instead, but it could require more refactoring work beyond just using SequenceBuilder and MapBuilder.

[quintesse]

Isn't ImmutableMap and ImmutableSet what Map and Set are right now?

[gavinking]

Isn't ImmutableMap and ImmutableSet what Map and Set are right now?

Yes, exactly. I thought the point of this issue was MapBuilder and SetBuilder. The issue description makes that a bit confusing.

I guess the question is, how is it better to use a MapBuilder or SetBuilder to create a map or set than just instantiating a HashSet or HashMap and adding members to it. There's a very specific reason we have StringBuilder and SequenceBuilder. The thing is that String and Sequence are immutable. We don't currently have any immutable implementations of Map or Set.

[quintesse]

We don't currently have any immutable implementations of Map or Set.

But we should, right?. I have tabs open on articles about immutable implementations for the most common datastructures for many months now. I even bought a book on functional datastructures hoping to find time to make a stab at implementing some of them :)

[ncorai]

I meant those classes as immutable implementations of the Map and Set interfaces, of course, unless you guys intend to provide native Builders again but I'm assuming that native is mostly destined to ceylon.language.

@gavinking, it's definitely better to use immutable implementations wherever you don't need mutators I believe: obviously in APIs, if you pass a HashMap as Map, there's nothing preventing the user from casting it back and mutating it. Performance-wise, I'd assume a builder will be faster than inserting into an existing collection, but that could be balanced by other criteria. And finally, there could be tangible memory savings.

[gavinking]

But we should, right?

Well this is not quite the way I look at it. I think that if there are implementations of Map and Set that have interesting and useful properties (performance, or whatever) that happen to be immutable, then it would be great to have such datastructures in ceylon.collection. But they wouldn't be there for their immutability per se. And of course every such implementation would need its own builder. It wouldn't be a generic builder for building any kind of immutable map or set.

if you pass a HashMap as Map, there's nothing preventing the user from casting it back and mutating it.

Ok, so yes, this is a great point, and I think we should add ImmutableMap and ImmutableSet wrapper classes, a bit like what Java's collection framework has. Of course in Ceylon they won't be broken like Java's because they won't have mutator methods.

[ncorai]

If you go the wrapper route, I'll say I find Map<Key, Value> imap = HashMap<Key, Value>(key->value).freeze() more elegant than Map<Key, Value> imap = ImmutableMap(HashMap<Key, Value>(key->value)), freeze (or some name that is more understandable though less cool) being maybe part of the MutableMap interface.

[gavinking]

@ncorai Hrm, sure, that sounds OK to me.

[ncorai]

OK, I've put my finger on what I don't like about immutable wrappers.

Even if you returned a wrapped mutable collection, it only means the collection is immutable for whoever references the wrapper, but any reference to the underlying collection can still mutate it, whereas builder.build makes a copy so the resulting collection is truly immutable.

[quintesse]

Indeed, but then then the word freeze suggests you're actually making the collection itself immutable, not returning a copy.

But I agree that's better than a wrapper. You could for example do Copy-On-Write enhancements by returning a result that only copies the items when the underlying collection gets changed. Something a wrapper couldn't do.

[gavinking]

Even if you returned a wrapped mutable collection, it only means the collection is immutable for whoever references the wrapper, but any reference to the underlying collection can still mutate it

I mean, if you want a truly immutable map, just throw away the reference to the underlying HashMap, leaving it only accessible via its wrapper. This is, after all, what you would have to do anyway with a builder.

[gavinking]

I think perhaps if we had Map<Key,Item> immutableView() and Map<Key,Item> immutableClone(), we would be fine.

[ncorai]

Sounds good to me, although I would rather name the latter immutableCopy (shouldn't clone() return the same type?), which could for now be implemented as immutableCopy() => clone().immutableView(); until the time you guys have more time to provide a smarter implementation, such as Tako's CopyOnWrite suggestion.

Oh wait, why does HashMap.clone() return a Map and not a MutableMap at least (not to mention an actual HashMap)? While the definition of Cloneable does not imply that the cloned copy of a mutable object be mutable too, it seems that should be the case. As it is, we'd have both Map<Key, Item> clone() and Map<Key, Item> immutableClone(), where the type system seems to indicate one thing and the method names another.

[gavinking]

I have added wrapper ImmutableMap and ImmutableSet classes to ceylon.collection. I'm inclined to close this issue now.

[gavinking]

Closing.