Opened 18 months ago
Last modified 9 months ago
#1399 reopened defect
Scrutinizer produces incorrect procedure types after merge
Reported by: | LemonBoy | Owned by: | evhan |
---|---|---|---|
Priority: | major | Milestone: | 5.1 |
Component: | scrutinizer | Version: | 4.12.0 |
Keywords: | Cc: | ||
Estimated difficulty: | medium |
Description
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.
Change History (10)
comment:1 Changed 17 months ago by sjamaan
comment:2 Changed 17 months ago by 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..
comment:3 Changed 17 months ago by evhan
- Owner set to evhan
- Status changed from new to assigned
comment:4 Changed 16 months ago by 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?
comment:5 Changed 16 months ago by 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)
comment:6 Changed 15 months ago by sjamaan
- Resolution set to fixed
- Status changed from assigned to closed
Fixed with 5ea816d and 62d7991.
comment:7 Changed 9 months ago by megane
- Resolution fixed deleted
- Status changed from closed to reopened
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|) . *).
comment:8 Changed 9 months ago by sjamaan
- Milestone changed from 4.13.0 to 5.0
comment:9 Changed 9 months ago by 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 <--
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.