Subject: Re: bug#66615: 30.0.50; Inconsistent 'number-or-marker' type definition in the cl- machinery

From: Stefan Monnier <[email-masked]>
Date: Fri, 20 Oct 2023 16:51:54 -0400

> (null boolean symbol list sequence atom) is not a linearization of the
> DAG,

AFAIK it is.  A linearization can be "depth first" or "breadth" first or
any mix of it.  It's basically any total order compatible with the
partial order imposed by the DAG.

> is just (TYPE . SUPERTYPES) where SUPERTYPES have no specific
> order.  Am I wrong?

The order is from most specific to least specific.  For types which are
"incomparable", the choice is a judgment call.  The above ordering seems
acceptable to me since `atom` is arguably a larger type than `sequence`,
but

    (null boolean symbol atom list sequence)

is acceptable as well.

This said, in general we'd like to avoid situations where type T1
appears before type T2 in one case and after it in another (it may not
always be avoidable, sadly).  And `atom` appears after `sequence` in
cases like `vector` and `string`, so I think we should prefer

    (null boolean symbol list sequence atom)

over

    (null boolean symbol atom list sequence)

> How can current code (say dispatch on builtin types) work if we can't
> infer if 'sequence' is higher or lower in the hierarchy respect
> to 'list'?

The linearization is specific to a given type, so we use the ordering
provided by `cl--typeof-types` and we never care to know the full DAG.

[ BTW, we should be able to infer that `list` is lower because every
  time it appears in `cl--typeof-types` it is always followed by
  `sequence`.  ]

> I think the original idea (as expressed by the doc) of having "the list
> of its supertypes from the most specific to least specific" works for
> reconstructing the DAG if we have one entry per path to the top, say:
>
> (null boolean symbol atom)
> (null list sequence)
> (cons list sequence)

Indeed.  But then it doesn't say how to make this into a total order
when `cl-defmethod` needs to decide which method should come first.

IOW, there is supposedly a DAG, but until now we've never actually
needed the DAG itself, instead we've needed only a linearization of the
ancestors of the leaves of that DAG, which is what
`cl--typeof-types` stores.

If you need the DAG, then maybe we need to store more info (tho I still
suspect we should be able to extract that info from `cl--typeof-types`).

        Stefan