elves / elvish

Powerful scripting language & versatile interactive shell
https://elv.sh/
BSD 2-Clause "Simplified" License
5.53k stars 297 forks source link

Implement a well defined ordering among types #1703

Closed krader1961 closed 1 year ago

krader1961 commented 1 year ago

This builds on the previous changes to implement a total ordering by replacing the dependency on the address at which various types are defined (which is effectively random) with an explicit ordering. For types without an explicit ordering it uses an ordering based on the order in which each unknown type is compared. This makes the ordering predictable based on the execution of Elvish code without regard to unpredictable factors such as the layout of data structures in the Elvish binary.

Note that the use of mechanisms like the peach command can introduce unpredictable ordering of unknown value types since this change handles unknown types at run time and thus, in theory, will produce different results when Elvish code that invokes compare &total or order &total is run concurrently. Whereas the prior logic is not affected by the parallelism of Elvish code. Nonetheless, I maintain that the predictability of ordering heterogenous values introduced by this change is a net positive since the new behavior will be predictable and reproducible (as a practical matter) while the prior logic (based on the random layout of data structures in the Elvish binary) is neither.

Related #1495

xiaq commented 1 year ago

Having a central place that enumerates all types makes it necessary to add every new type there, but there's no way to guarantee that this has happened when a new type is added. The approach in this PR requires Elvish's runtime type system to be closed when it is in fact an open system.

A predictable ordering between types is a good property, but the cost outweighs the benefit.

If there is a compelling use case for a well-defined ordering between types (which doesn't seem to be the case now), there is a simpler, less error-prone way to do this: compare the fully qualified names of the reflect.Type (using t.PkgPath() + "." + t.Name()) values.

xiaq commented 1 year ago

Also: I might decide in future to actually make the runtime type system closed, at which point imposing a well-defined total order among types will make more sense. That approach has some big advantages but also some big disadvantages, so I'm not committing to it happening any time soon, or indeed at all.