Implement a well defined ordering among types

[krader1961]

Replace the current total ordering of types defined by the address at which each type is defined (which is effectively random) with an explicit ordering. This makes writing unit tests easier and provides predictable run time behavior for users regardless of which platform they run Elvish on.

Related #1495

[krader1961]

I'll point out that my pending change to improve the pprint formatting of maps to vertically align values depends on this change. Primarily due to a unit test that deliberately includes mixed types to verify the formatting of the output is correct when mixed types are present. I appreciate why @xiaq rejected my previous solution to this problem but there really does need to be a platform independent ordering of heterogenous types. This change does so and is cheap. It also fixes a problem with the current implementation which does not treat regular and struct maps as equivalent when ordered. Not to mention simply making the order of heterogenous types consistent across platforms; rather than indeterminate.

[xiaq]

Reflection is expensive, and the Name() is not unique; you need PkgPath() too.

A much cheaper option is to simply return small numbers:

func typeOf(x any) uintptr {
  switch x.(type) {
  case nil:
    return 0
  case bool:
    return 1
  // ...
  default:
    return *(*uintptr)(unsafe.Pointer(&x))
  }
}

I don't think Elvish supports any operating system that maps page 0 without an explicit mmap, but if there's a need to support such platforms, it's always possible to allocate a small byte array, and use its address instead:

var dummy [10]byte
var dummyBase = uintptr(unsafe.Pointer(&dummy))

func typeOf(x any) uintptr {
  switch x.(type) {
  case nil:
    return dummyBase
  // ...
}

However, I don't feel having predictable ordering for testing pprint is a strong enough reason for having the ordering of types fixed; it's not a real-world use case. I'll reconsider if there's a real-world use case.

For testing pprint: If there are two types, you can just list the two possible outputs. If there's really a need for many different types, you can build some test utility, like this (very rough sketch):

type reorderableLines struct{
  before string
  middle []string // can appear in any relative order
  after string
}

Test(t,
  That(`pprint $m`).Prints(reorderableLines{"[", []string{"&a=b\n&c=d", "&(num 1)=foo\n&(num 2)=bar"} "]"})

In any case, the logic of pprint should be agnostic about maps having mixed-typed keys, so I'm not sure that it's necessary to test in the first place. But maybe your implementation does care about that.

[xiaq]

4ceb91901e83f3eae9d7db44d7a3268771e6bba7 fixed the structmap bug.