Re: [Chicken-hackers] Add scrutiny special case for "append" [was: Re: [PATCH] Fix list-ref type derivation for smashed lists [was: Re: [PATCH] A few small performance and scrutiny warning improvement
Both pushed. Evan signature.asc Description: Digital signature ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
[Chicken-hackers] Add scrutiny special case for "append" [was: Re: [PATCH] Fix list-ref type derivation for smashed lists [was: Re: [PATCH] A few small performance and scrutiny warning improvements to
On Sun, Jul 24, 2016 at 08:32:31PM +0200, Peter Bex wrote: > The attached patch fixes this by only allowing this specialisation > for lists that are known to be proper. This means anything that > ends with a smashed component, which is (or pair null), it will not > be considered to be a known proper list, so the optimisation is skipped. And here's another improvement, to track types of "append"'s arguments into its return type. It needs to be applied after the fix for the list-ref specialisation, because it adds test cases that would otherwise conflict (I think). I'm having good hopes that this is a useful improvement, particularly because quasiquoted forms will expand to "append" calls, so there will be quite a few cases where semi-constant lists will get their types known, which they didn't before. There's one limitation: It doesn't know what to do when you append an unknown (or smashed) list to something else. I tried to come up with something that's smart enough to merge a nested (pair ...) type with a subsequent list argument, but I failed. We can add this later, though. Cheers, Peter From c5691539d01b47625dfbb278bc4372dee03cc1b5 Mon Sep 17 00:00:00 2001 From: Peter Bex Date: Sun, 24 Jul 2016 20:04:20 +0200 Subject: [PATCH] Add special-case scrutiny handling for "append". Type derivation works perfectly for arguments known to be proper lists, but for (pair ...) structures it will punt. However, it can emit warnings when the arguments (except for the last one) are known to be non-lists or improper lists. --- scrutinizer.scm | 52 tests/scrutiny-tests.scm | 16 +++ tests/scrutiny.expected | 6 ++ types.db | 1 + 4 files changed, 75 insertions(+) diff --git a/scrutinizer.scm b/scrutinizer.scm index b143b0c..51bf9ad 100644 --- a/scrutinizer.scm +++ b/scrutinizer.scm @@ -2332,6 +2332,58 @@ `((list ,@(reverse (cdr arg1) rtypes))) +(let () + ;; See comment in vector (let) + (define (report loc msg . args) +(warning + (conc (location-name loc) + (sprintf "~?" msg (map type-name args) + + (define (append-special-case node args loc rtypes) +(define (potentially-proper-list? l) (match-types l 'list '())) + +(define (derive-result-type) + (let lp ((arg-types (cdr args)) + (index 1)) +(if (null? arg-types) +'null +(let ((arg1 (walked-result (car arg-types + (cond + ((and (pair? arg1) (eq? (car arg1) 'list)) +(and-let* ((rest-t (lp (cdr arg-types) (add1 index + ;; decanonicalize, then recanonicalize to make it + ;; easy to append a variety of types. + (canonicalize-list-type + (foldl (lambda (rest t) `(pair ,t ,rest)) + rest-t (reverse (cdr arg1)) + + ((and (pair? arg1) (eq? (car arg1) 'list-of)) +(and-let* ((rest-t (lp (cdr arg-types) (add1 index + ;; list-of's length unsurety is "contagious" + (simplify-type `(or ,arg1 ,rest-t + + ;; TODO: (append (pair x (pair y z)) lst) => + ;; (pair x (pair y (or z lst))) + ;; This is trickier than it sounds! + + (else +;; The final argument may be an atom or improper list +(unless (or (null? (cdr arg-types)) +(potentially-proper-list? arg1)) + (report + loc "~ain procedure call to `~s', argument #~a is \ +of type ~a but expected a proper list" + (node-source-prefix node) + (first (node-parameters + (first (node-subexpressions node + index arg1)) +#f)) +(cond ((derive-result-type) => list) + (else rtypes))) + + (define-special-case append append-special-case) + (define-special-case ##sys#append append-special-case)) + ;;; Special cases for make-list/make-vector with a known size ; ; e.g. (make-list 3 #\a) => (list char char char) diff --git a/tests/scrutiny-tests.scm b/tests/scrutiny-tests.scm index a9f1942..546c523 100644 --- a/tests/scrutiny-tests.scm +++ b/tests/scrutiny-tests.scm @@ -295,3 +295,19 @@ (define (list-ref-type-nowarn2) (add1 (list-ref l2 1 (let ((l3 (the (list-of fixnum) '(1 2 3 (define (list-ref-type-nowarn3) (add1 (list-ref l3 1 + +;; Test type preservation of append (TODO: decouple from list-ref) +(let ((l1 (append (list 'x 'y) (list 1 2 (eval '(list)) + (define (append-result-type-warn1) (add1 (list-ref l1 1 +;; This currently doesn't warn because pair types aren't joined yet +#;(let ((l2 (append (cons 'x (cons 'y (eval '(list (list 'x 'y + (define (append-result-type-warn2) (add1 (list-ref l2 1 +(let ((l3 (append (t
[Chicken-hackers] [PATCH] Fix list-ref type derivation for smashed lists [was: Re: [PATCH] A few small performance and scrutiny warning improvements to assignments]
On Thu, Jul 14, 2016 at 09:08:57PM +0200, Peter Bex wrote:
> Patch 0003 is a simple modification based on the preceding one: it
> gives a scrutiny warning when you try to set or ref a vector at an
> index that is known not to exist. For completeness, I also did this
> for list-ref, list-tail, take and drop.
There's a small problem with this: it doesn't deal well with lists
constructed from lists of smashed components:
$ cat list-ref-test.scm
(let ((l1 (list 'a 'b c)))
(define (something) (print l1))
(let ((l2 (cons 'd l1)))
(define (fourth) (list-ref l2 4))
(print (fourth
$ csc -O3 list-ref-test.scm
Warning: in toplevel procedure `fourth':
(list-ref-test.scm:4) in procedure call to `list-ref', index 4 out of range
for list of type (pair symbol (or pair null))
The attached patch fixes this by only allowing this specialisation
for lists that are known to be proper. This means anything that
ends with a smashed component, which is (or pair null), it will not
be considered to be a known proper list, so the optimisation is skipped.
I decided that it's still useful to warn on these unknown lists when
list-ref receives a negative index because that's never valid.
So, I split the check in two: first check for negative index, then
perform the already existing check, but only if the list is known to
be a proper list.
Cheers,
Peter
From 4437dec23c69b42de37f825d637f1cd61fb34b6c Mon Sep 17 00:00:00 2001
From: Peter Bex
Date: Sun, 24 Jul 2016 15:37:11 +0200
Subject: [PATCH] Do not warn for out of range indices into possibly smashed
list types.
When a list is smashed, usually ends up as (or pair null). If then we
cons something onto it, it's seen as a list of length 1 or possibly 2.
We should *not* give a warning on (list-ref 3 that-list), because it may
originally have been a list of a greater length. We don't know that, so
we should avoid warning for anything that's not absolutely sure to be a
proper list.
Luckily, if it's typed as a proper list, that's presumably safe. That's
because a list with smashed components should end in just "pair", due to
possible mutation by set-cdr!, which means its type is not that of a
proper list.
We still always warn when list-ref takes a negative index, because
that's never ever valid, regardless of the argument list type.
We still always preserve types when using list-ref, even on a list with
smashed components, as long as the list is known to contain the index.
Conflicts:
scrutinizer.scm
---
NEWS | 2 +-
scrutinizer.scm | 40 ++-
tests/scrutiny-tests.scm | 61
tests/scrutiny.expected | 32 +
4 files changed, 103 insertions(+), 32 deletions(-)
diff --git a/NEWS b/NEWS
index de54596..d4eb49d 100644
--- a/NEWS
+++ b/NEWS
@@ -57,7 +57,7 @@
- define-constant now correctly keeps symbol values quoted.
- Warnings are now emitted when using vector-{ref,set!} or one
of take, drop, list-ref or list-tail with an out of range index
-for vectors and lists of a definitely known length.
+for vectors and proper lists of a definitely known length.
- The scrutinizer will no longer drop knowledge of the length of a
vector. It still drops types of its contents (which may be mutated).
diff --git a/scrutinizer.scm b/scrutinizer.scm
index 9eb0052..b143b0c 100644
--- a/scrutinizer.scm
+++ b/scrutinizer.scm
@@ -2232,6 +2232,7 @@
;; Split a list or pair type form at index i, calling k with the two
;; sections of the type or returning #f if it doesn't match that far.
+ ;; Note that "list-of" is handled by "forall" entries in types.db
(define (split-list-type l i k)
(cond ((not (pair? l))
(and (fx= i 0) (eq? l 'null) (k l l)))
@@ -2252,6 +2253,13 @@
(else #f
(else #f)))
+ ;; canonicalize-list-type will have taken care of converting (pair
+ ;; (pair ...)) to (list ...) or (list-of ...) for proper lists.
+ (define (proper-list-type-length t)
+(cond ((eq? t 'null) 0)
+ ((and (pair? t) (eq? (car t) 'list)) (length (cdr t)))
+ (else #f)))
+
(define (list+index-call-result-type-special-case k)
(lambda (node args loc rtypes)
(or (and-let* ((subs (node-subexpressions node))
@@ -2261,17 +2269,27 @@
((eq? 'quote (node-class index)))
(val (first (node-parameters index)))
((fixnum? val))) ; Standard type warning otherwise
- (or (and (>= val 0) (split-list-type arg1 val k))
- (begin
- (report
- loc "~ain procedure call to `~a', index ~a out of \
-range for list of type ~a"
- (node-source-prefix node)
- ;; TODO: It might make more sense to use
- ;; "pname" here
- (first (node-parameters (first subs)))
- val arg1)
- #f)))
+ ;; TODO: It might make sense to use "pname" when reporting
+ (cond ((negative? val)
+ ;; Negative indices should always generate a warning
+ (repo
Re: [Chicken-hackers] [PATCH] A few small performance and scrutiny warning improvements to assignments
Peter Bex scripsit: > It seems silly to ask the length of a vector that's statically known. Not at all. If your program needs a vector of constants, thus: (define pi-digits #(3 1 4 1 5 9) then you might want to future-proof the rest of your program against extending this constant by writing (vector-length pi-digits) rather than the magic number 6. This more usually comes up with strings rather than vectors, but the principle is the same. -- John Cowan http://www.ccil.org/~cowanco...@ccil.org If I have not seen as far as others, it is because giants were standing on my shoulders. --Hal Abelson ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
Re: [Chicken-hackers] [PATCH] A few small performance and scrutiny warning improvements to assignments
On Sun, Jul 24, 2016 at 09:18:14PM +1200, Evan Hanson wrote: > Hi Peter, > > Good improvements all, pushed. > > Regarding your note about special-casing `vector-length`, I'm curious > why you think it wouldn't make sense? It seems worthwhile to me. It seems silly to ask the length of a vector that's statically known. Also, the operation is very cheap. But, we can apply it if you think it's worthwhile anyway. Cheers, Peter signature.asc Description: Digital signature ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
Re: [Chicken-hackers] [PATCH] A few small performance and scrutiny warning improvements to assignments
Hi Peter, Good improvements all, pushed. Regarding your note about special-casing `vector-length`, I'm curious why you think it wouldn't make sense? It seems worthwhile to me. Evan signature.asc Description: Digital signature ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
Re: [Chicken-hackers] Improved manpages [was: (no subject)]
Hi folks, Looks good, applied to chicken-5. It didn't apply cleanly to master; was it meant to? Personally, I'm fine making this a 5-only change. I also updated the mdocs for the "-module" and "-link" options, which are different and new in 5, respectively. There might be some others that need updating; I didn't check too carefully yet. Timo, thanks very much for your work on this, it's a great change. Cheers, Evan signature.asc Description: Digital signature ___ Chicken-hackers mailing list Chicken-hackers@nongnu.org https://lists.nongnu.org/mailman/listinfo/chicken-hackers
