Subject: bug#77725: 31.0.50; Add support for types accepted by `cl-typep' to cl-generic?

From: David Ponce <[email-masked]>
Date: Fri, 18 Apr 2025 01:00:57 +0200

On 2025-04-17 17:27, Stefan Monnier wrote:
>>>>             (if (memq name parents)
>>>>                 (error "Type in parents: %S" parents))
>>> Not sure how useful is this test.
>>
>> I removed testing if parents is a list, this is always true.
>> The other test prevents to define a type whose parent is itself.
> 
> My comment was specifically about the last 2 lines testing if `name` is
> in `parents`.  How likely is this error?  Wouldn't it be caught by the
> DAG test later anyway?

In principle your are correct, the cycle should be caught at DAG test.
But it seems it's not the case.  I removed the test for `name' in `parents'
and tried these definitions:

(cl-deftype test ()
   'number)

(cl-deftype test ()
   (declare (parents test))
   'number)

Normally, the second definition should be caught by the DAG test, but is
not, and produced wrong definition, with `cl--type-list' equals to
(test test).

It seems the problem is that `merge-ordered-lists' doesn't caught this
case:

(merge-ordered-lists '((test test)))
=> (test test)

I tried the same test with the topologic sort, and it failed as expected:

(gtype--topologic-sort '((test test)))
=> "Invalid graph" error

> 
>>>>             ;; Clear cached value of specializers with NAME.
>>>>             (if class
>>>> 	      (cl--type-reset-specializers name)
>>>> 	    ;; Record new type.
>>>> 	    (push name cl--type-list))
>>> Shouldn't we test `reged` before `push`ing?
>> Not sure to understand this point.  name needs to be in cl--type-list
>> before to call merge-ordered-lists on the DAG.
> 
> IIRC if `reged` is non-nil, `name` is already included in
> `cl--type-list` so we shouldn't push it again there.

In fact, push is done only if `class' is nil, which is the equivalent
to `reged' non-nil.  For clarity, I changed to test with `reged'
(renamed `recorded' new versions).

>>>> (defmacro cl-type-undefine (name)
>>>>     "Remove the definitions of type with NAME.
>>>> NAME is an unquoted symbol representing a type.
>>>> Signal an error if other types inherit from NAME."
>>>>     `(progn
>>>>        (cl-check-type ',name (satisfies cl-type-p))
>>>>        (cl--type-undefine ',name)))
>>> We don't have that for other types.  I understand it's somewhat
>>> dangerous for the other types and not for this one, but I still wonder
>>> if we need it.
>> I thought it could be useful, for example to cleanup the environment
>> when you kind of uninstall a library which defined types.  Maybe it
>> could help during tests?
> 
> I'm not saying it can't be useful, just wondering if it will be.
> In either case it doesn't seem like there's a good reason it should be
> a `defmacro` rather than a `defun`.
> 
> BTW, part of this is handled by `define-symbol-prop` which makes sure
> that the `cl-deftype-handler` is automatically removed when you
> `unload-feature`.  Maybe we should use `define-symbol-prop` instead of
> `setf` for the `cl--class` property as well.

This is good to know.  For now, I only kept the function `cl--type-undefine',
in case we need it to cleanup things while testing.  We can remove it later
if not useful.

>>> That doesn't sound right: it works only if there are no types which are
>>> overlapping and "incomparable" (like `cons-car-foo` and `cons-cdr-foo`).
>>> We may be able to use the `subtype-of` info to skip some types (e.g. we
>>> don't need to test the parents, or if we traverse the list in the other
>>> direction, we don't need to test FOO if we already saw that the object
>>> failed the test for one of FOO's parents), but in general we'll have to
>>> check them all: we definitely can't stop at the first successful check.
>> Good point.  But you lost me regarding possible optimizations :-(
> 
> If BAR is declared as a parent of FOO and `cl-types-of` has already
> decided that the value *is* of type FOO, then we already know BAR will
> be in the output anyway and there's no point testing BAR.

This looks like what I did in my previous version.  When FOO matched,
I put FOO and its parents in the result.  My mistake was stopping there
instead of continuing to the end of the list!

> The converse is that if we have already decided that the value is *not*
> for type BAR, then it can't be of type FOO either, so there's no point
> testing FOO.

Wouldn't this involve calculating the parents of all the types traversed,
instead of just the matching ones? If so, wouldn't we risk losing on one
side what we gain on the other?

>>>> ;;; Some tests
>> [...]
>>> I suggest to define something like `multiples-of-2`, `multiples-of-3`,
>>> and `multiples-of-4`, so as to test more complex relationships between
>>> types (with overlap but not inclusion).
>>
>> Do you have any examples in mind?
> 
> Test that (c-types-of 4) is (multiples-of-4 multiples-of-2 ...)
> Test that (c-types-of 6) is (multiples-of-3 multiples-of-2 ...)
> Test that (c-types-of 12) is (multiples-of-4 multiples-of-3 multiples-of-2 ...)
> 
> This would have failed with your previous code which didn't check
> all types.

Thank you, I'll give it a try.