Scrutinizer produces incorrect procedure types after merge

[LemonBoy]

Suppose we get this expression after scrutinizing some code:

(or (procedure (|#!rest|) noreturn)
    (procedure (* |#!rest|) . *))

At the moment the result of the union is (procedure (#!rest)) which is clearly wrong because it has arity N >= 0 while the second procedure in the or expression has arity N >= 1. Moreover the return type is lost, I'd expect the noreturn to be dropped and * to be used instead.

The result of the miscalculation of the resulting type may or may not be dangerous.

[sjamaan]

I'm not so sure that the arity is "clearly wrong", because it would be equally incorrect to give a warning when calling the procedure with zero arguments; the procedure might accept zero arguments (if the first alternative is used).

Perhaps the best we can do is not to simplify/merge the procedure, but just keep the or? I don't know what the impact of that would be though.

[megane]

My understanding is that it is always safe to go for more general type. In this case procedure or even just * would be ok too. And N >= 0 is more general than N >= 1.

Notice that (procedure (#!rest)) does not specify return type. This is different from *.

Indeed, it would be interesting to know if there was any downsides if in this case the union was left as it is. Maybe it would make the scrutinizer slower..

[evhan]

On what version are you seeing this? The current behaviour in both master and 4.12.0 is, as far as I can tell, to simplify (or (procedure a (#!rest *) noreturn) (procedure b (* #!rest *) . *)) into (procedure (#!rest) . *), which is correct.

Is there a specific way to trigger this bug, and if so can you share?

[LemonBoy]

Sure, I caught this error during the compilation of the sxpath egg, to be precise during the compilation of chicken/context-sxpath-lolevel.scm.
The warnings emitted are reported below:

  Warning: in toplevel procedure `context-sxpath-lolevel#draft:ast-step':
    expected a single result in `let' binding of `axis', but received zero results

  Warning: in toplevel procedure `context-sxpath-lolevel#draft:ast-step':
    expected a single result in `let' binding of `axis', but received zero results

You have to start from those warnings and work your way backwards to the source of the type for axis-lst. If I still remember correctly the nitty gritty details it's the analysis of draft:ast-axis-specifier that gets the type mentioned in the ticket.

Tested right now with CHICKEN Version 4.12.1 (rev 5746f0c1)

[sjamaan]

Fixed with 5ea816d and 62d7991.

[megane]

LemonBoy?'s original analysis seems to be correct; the merged type should be (procedure (* |#!rest|) . *). Here is a case that fails at runtime:

(: f1 (#!rest * -> noreturn))
(define (f1 #!rest _) (exit))

(: f2 (procedure (* #!rest *) . *))
(define (f2 a #!rest _) (begin))

(declare (not inline foo))
(: foo ((#!rest ->) -> *))
(define (foo f)
  (f))

(print "running")
(foo (if (the * #f) f1 f2))

;; The merged type is (procedure (#!rest) . *)
;; (compiler-typecase (if (the * #f) f1 f2) ((not *) 1))

;; Output:
;;
;; $ csc -O3 1399-case.scm && ./1399-case
;; running
;;
;; Error: too few arguments - received 0 but expected 1: #<procedure (f2 a . _)>
;;
;; 	Call history:
;;
;; 	1399-case.scm:12: chicken.base#print
;; 	1399-case.scm:13: foo
;; 	1399-case.scm:10: f	  	<--

I think the procedure merging could be implemented with a simple algorithm:

Input: (or P1 P2 ... Pk)
T1  <- (or P1)
T_n <- if P_n < T_n-1
         T_n-1
       else
         (or T_n-1 P_n)
Result is T_k

This would return correct, but not necessarily minimal types.

For (or (procedure (|#!rest|) noreturn) (procedure (* |#!rest|) . *)) it wouldn't change the type.
For (or (procedure (* |#!rest|) . *) (procedure (|#!rest|) noreturn) ) it would return (procedure (* |#!rest|) . *).

[megane]

The idea of merging procedure argument and return types piecemeal, as it's currently done, is fundamentally flawed. See below:

(: f1 (fixnum -> *))
(define (f1 a)
  (+ a 1))

(: f2 (string -> *))
(define (f2 a)
  (string-length a))

(: foo (((or fixnum string) -> *) -> *))
(define (foo f)
  (print (f 1))
  (print (f "hello")))

;; (compiler-typecase (if (the * #t) f1 f2) ((not *) 1))
;; Error: at toplevel:
;;   (procedure-merge-fail.scm:14) no clause applies in `compiler-typecase' for expression of type `(procedure ((or string fixnum)) *)':
;;     (not *)

(foo (lambda (a) (if (string? a) (f2 a) (f1 a))))
(foo (if (the * #t) f2 f1))

;; $ csc -O3 procedure-merge-fail.scm && ./procedure-merge-fail
;; 2
;; 5
;;
;; Error: (string-length) bad argument type: 1
;;
;; 	Call history:
;;
;; 	procedure-merge-fail.scm:19: foo
;; 	procedure-merge-fail.scm:11: f
;; 	procedure-merge-fail.scm:11: chicken.base#print
;; 	procedure-merge-fail.scm:12: f
;; 	procedure-merge-fail.scm:12: chicken.base#print
;; 	procedure-merge-fail.scm:20: foo
;; 	procedure-merge-fail.scm:11: f	  	<--

[sjamaan]

Not a blocker for 5.0