emacs-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH v4] Bound index checks in cl-seq functions


From: Tino Calancha
Subject: Re: [PATCH v4] Bound index checks in cl-seq functions
Date: Mon, 06 Feb 2017 16:00:58 +0900
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/26.0.50 (gnu/linux)

Clément Pit-Claudel <address@hidden> writes:

> On 2017-02-05 02:11, Tino Calancha wrote:
>> II) `cl--check-bound-indices' returns on success the sequence[s]
>>     length[s], so that callers don't need to recompute them.
>
> This sounds like a good idea, performance wise.  But maybe it would be
> even better to disable these checks when (cl-declaim (optimize (safety
> 0))) is set?
Yes, that sounds right.
The new patch disables those checks in that case (safety = 0).
I got ~0.92 s without checks and ~ 1.10 with checks
when i ran the following toy:
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; start
;; -*- lexical-binding: t; -*-

(require 'cl-lib)

(cl-declaim (optimize (safety 0))) ; (test) ~ 0.92
;(cl-declaim (optimize (safety 1))) ; (test) ~ 1.10
       
(defun test ()
  (let ((lst (nreverse (cons 'a (number-sequence 1 1000000)))))
    (benchmark-run 10
      (cl-position 'a lst))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; end

Following is the updated patch:

:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
>From a57cc0105e315382715edba1baa9b814b947675d Mon Sep 17 00:00:00 2001
From: Tino Calancha <address@hidden>
Date: Mon, 6 Feb 2017 15:20:51 +0900
Subject: [PATCH 1/2] Check for out-of-range indices in cl-seq function

Throw and error if the user inputs out of range indices
or if :start value is higher than :end value.
Suppress these checks if 'cl--optimize-safety' 0.
* lisp/emacs-lisp/cl-seq.el (cl--parsing-keywords):
Check for negative indices.
(cl--check-bound-indices): New defun; check for indices > seq length,
or start index > end index.
(cl-reduce, cl-fill, cl-replace, cl-remove, cl-delete)
(cl--delete-duplicates, cl-substitute, cl-nsubstitute, cl-position)
(cl-count, cl-mismatch, cl-search): Use it.
* doc/misc/cl.texi (Sequence Basics): Update manual.
; * etc/NEWS: Announce the change.
* test/lisp/emacs-lisp/cl-seq-tests.el (cl-seq-check-bounds): New test.
---
 doc/misc/cl.texi                     |   4 +-
 etc/NEWS                             |   4 +
 lisp/emacs-lisp/cl-seq.el            | 379 +++++++++++++++++++++--------------
 test/lisp/emacs-lisp/cl-seq-tests.el |  95 +++++++++
 4 files changed, 335 insertions(+), 147 deletions(-)

diff --git a/doc/misc/cl.texi b/doc/misc/cl.texi
index 8baa0bd88c..6f387f5cbb 100644
--- a/doc/misc/cl.texi
+++ b/doc/misc/cl.texi
@@ -3247,7 +3247,9 @@ Sequence Basics
 (exclusive) are affected by the operation.  The @var{end} argument
 may be passed @code{nil} to signify the length of the sequence;
 otherwise, both @var{start} and @var{end} must be integers, with
address@hidden <= @var{start} <= @var{end} <= (length @var{seq})}.
address@hidden <= @var{start} <= @var{end} <= (length @var{seq})}.  Emacs
+signals an error when this condition is not true, except for
address@hidden which allows negative indices.
 If the function takes two sequence arguments, the limits are
 defined by keywords @code{:start1} and @code{:end1} for the first,
 and @code{:start2} and @code{:end2} for the second.
diff --git a/etc/NEWS b/etc/NEWS
index 4d8ae091a7..19dd5d9995 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -706,6 +706,10 @@ processes on exit.
 * Incompatible Lisp Changes in Emacs 26.1
 
 +++
+** CL sequence functions now throw errors when the input indices
+are out of range, or if :start index is higher than :end index.
+
++++
 ** Resizing a frame no longer runs 'window-configuration-change-hook'.
 Put your function on 'window-size-change-functions' instead.
 
diff --git a/lisp/emacs-lisp/cl-seq.el b/lisp/emacs-lisp/cl-seq.el
index 67ff1a00bd..4ea9ebb063 100644
--- a/lisp/emacs-lisp/cl-seq.el
+++ b/lisp/emacs-lisp/cl-seq.el
@@ -42,6 +42,9 @@
 ;;; Code:
 
 (require 'cl-lib)
+(eval-when-compile (require 'subr-x))
+
+(defvar cl--optimize-safety)
 
 ;; Keyword parsing.
 ;; This is special-cased here so that we can compile
@@ -59,7 +62,14 @@ cl--parsing-keywords
                    (setq mem `(and ,mem (setq cl-if ,mem) t)))
                (list (intern
                       (format "cl-%s" (substring (symbol-name var) 1)))
-                     (if (consp x) `(or ,mem ,(car (cdr x))) mem))))
+                     `(if (and (not (zerop cl--optimize-safety))
+                               (string-match ":\\(start\\|end\\)" (symbol-name 
,var))
+                               (integerp (or ,mem ,(car (cdr-safe x))))
+                               (not (natnump (or ,mem ,(car (cdr-safe x))))))
+                          (error "Wrong negative index '%s': natnump, %s"
+                                 (substring (symbol-name ,var) 1)
+                                 (or ,mem ,(car (cdr-safe x))))
+                        (or ,mem ,(car (cdr-safe x)))))))
            kwords)
      ,@(append
         (and (not (eq other-keys t))
@@ -112,6 +122,49 @@ cl-test
 (defvar cl-if) (defvar cl-if-not)
 (defvar cl-key)
 
+;; Throw an error when :start or :end are > sequence length,
+;; or if :start > :end.
+;; If CL-SEQ2 is nil, then return (length cl-seq1), otherwise
+;; return (cons (length cl-seq1) (length cl-seq2)).
+(defun cl--check-bound-indices (cl-seq1 cl-seq2 cl-keys)
+  (let ((len1 (length cl-seq1))
+        (len2 (and cl-seq2 (length cl-seq2)))
+        (kwds (list :start1 :start2 :start :end1 :end2 :end))
+        alist)
+    (while cl-keys
+      (when (and (memq (car cl-keys) kwds)
+                 (string-match ":\\(start\\|end\\)\\([1-2]?\\)\\'"
+                               (symbol-name (car cl-keys))))
+        (delq (car cl-keys) kwds) ; Ignore succesive equal keys.
+        (let* ((idx (match-string 2 (symbol-name (car cl-keys))))
+               (len (if (equal idx "2") len2 len1)))
+          (when (integerp (cadr cl-keys))
+            (push (cons (car cl-keys) (cadr cl-keys)) alist)
+            (when (> (cadr cl-keys) len)
+              (error "Wrong bounding indices '%s', %s > (length %s), %s"
+                     (substring (symbol-name (car cl-keys)) 1)
+                     (cadr cl-keys)
+                     (concat "cl-seq" idx)
+                     len)))))
+      (setq cl-keys (cddr cl-keys)))
+    ;; Check :start value > :end value.
+    (mapc (lambda (x)
+            (and-let* ((start (alist-get (car x) alist))
+                       (end (alist-get (cdr x) alist))
+                       (bad-indices (> start end)))
+              (error "Bad bounding indices '%s', '%s': %d, %d"
+                     (substring (symbol-name (car x)) 1)
+                     (substring (symbol-name (cdr x)) 1)
+                     start
+                     end)))
+          (list (cons :start :end)
+                (cons :start1 :end1)
+                (cons :start2 :end2)))
+    ;; Return sequence lengths.
+    (if len2
+        (cons len1 len2)
+      len1)))
+
 ;;;###autoload
 (defun cl-reduce (cl-func cl-seq &rest cl-keys)
   "Reduce two-argument FUNCTION across SEQ.
@@ -128,6 +181,7 @@ cl-reduce
 
 \n(fn FUNCTION SEQ [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:from-end (:start 0) :end :initial-value :key) ()
+    (or (zerop cl--optimize-safety) (cl--check-bound-indices cl-seq nil 
cl-keys))
     (or (listp cl-seq) (setq cl-seq (append cl-seq nil)))
     (setq cl-seq (cl-subseq cl-seq cl-start cl-end))
     (if cl-from-end (setq cl-seq (nreverse cl-seq)))
@@ -149,18 +203,21 @@ cl-fill
 \nKeywords supported:  :start :end
 \n(fn SEQ ITEM [KEYWORD VALUE]...)"
   (cl--parsing-keywords ((:start 0) :end) ()
-    (if (listp cl-seq)
-       (let ((p (nthcdr cl-start cl-seq))
-             (n (and cl-end (- cl-end cl-start))))
-         (while (and p (or (null n) (>= (cl-decf n) 0)))
-           (setcar p cl-item)
-           (setq p (cdr p))))
-      (or cl-end (setq cl-end (length cl-seq)))
-      (if (and (= cl-start 0) (= cl-end (length cl-seq)))
-         (fillarray cl-seq cl-item)
-       (while (< cl-start cl-end)
-         (aset cl-seq cl-start cl-item)
-         (setq cl-start (1+ cl-start)))))
+    (let ((len (if (zerop cl--optimize-safety)
+                   (or cl-end (length cl-seq))
+                 (cl--check-bound-indices cl-seq nil cl-keys))))
+      (if (listp cl-seq)
+          (let ((p (nthcdr cl-start cl-seq))
+                (n (and cl-end (- cl-end cl-start))))
+            (while (and p (or (null n) (>= (cl-decf n) 0)))
+              (setcar p cl-item)
+              (setq p (cdr p))))
+        (or cl-end (setq cl-end len))
+        (if (and (= cl-start 0) (= cl-end len))
+            (fillarray cl-seq cl-item)
+          (while (< cl-start cl-end)
+            (aset cl-seq cl-start cl-item)
+            (setq cl-start (1+ cl-start))))))
     cl-seq))
 
 ;;;###autoload
@@ -170,44 +227,48 @@ cl-replace
 \nKeywords supported:  :start1 :end1 :start2 :end2
 \n(fn SEQ1 SEQ2 [KEYWORD VALUE]...)"
   (cl--parsing-keywords ((:start1 0) :end1 (:start2 0) :end2) ()
-    (if (and (eq cl-seq1 cl-seq2) (<= cl-start2 cl-start1))
-       (or (= cl-start1 cl-start2)
-           (let* ((cl-len (length cl-seq1))
-                  (cl-n (min (- (or cl-end1 cl-len) cl-start1)
-                             (- (or cl-end2 cl-len) cl-start2))))
-             (while (>= (setq cl-n (1- cl-n)) 0)
-               (setf (elt cl-seq1 (+ cl-start1 cl-n))
-                           (elt cl-seq2 (+ cl-start2 cl-n))))))
-      (if (listp cl-seq1)
-         (let ((cl-p1 (nthcdr cl-start1 cl-seq1))
-               (cl-n1 (and cl-end1 (- cl-end1 cl-start1))))
-           (if (listp cl-seq2)
-               (let ((cl-p2 (nthcdr cl-start2 cl-seq2))
-                     (cl-n (cond ((and cl-n1 cl-end2)
-                                  (min cl-n1 (- cl-end2 cl-start2)))
-                                 ((and cl-n1 (null cl-end2)) cl-n1)
-                                 ((and (null cl-n1) cl-end2) (- cl-end2 
cl-start2)))))
-                 (while (and cl-p1 cl-p2 (or (null cl-n) (>= (cl-decf cl-n) 
0)))
-                   (setcar cl-p1 (car cl-p2))
-                   (setq cl-p1 (cdr cl-p1) cl-p2 (cdr cl-p2))))
-             (setq cl-end2 (if (null cl-n1)
-                               (or cl-end2 (length cl-seq2))
-                             (min (or cl-end2 (length cl-seq2))
-                                  (+ cl-start2 cl-n1))))
-             (while (and cl-p1 (< cl-start2 cl-end2))
-               (setcar cl-p1 (aref cl-seq2 cl-start2))
-               (setq cl-p1 (cdr cl-p1) cl-start2 (1+ cl-start2)))))
-       (setq cl-end1 (min (or cl-end1 (length cl-seq1))
-                          (+ cl-start1 (- (or cl-end2 (length cl-seq2))
-                                          cl-start2))))
-       (if (listp cl-seq2)
-           (let ((cl-p2 (nthcdr cl-start2 cl-seq2)))
-             (while (< cl-start1 cl-end1)
-               (aset cl-seq1 cl-start1 (car cl-p2))
-               (setq cl-p2 (cdr cl-p2) cl-start1 (1+ cl-start1))))
-         (while (< cl-start1 cl-end1)
-           (aset cl-seq1 cl-start1 (aref cl-seq2 cl-start2))
-           (setq cl-start2 (1+ cl-start2) cl-start1 (1+ cl-start1))))))
+    (let*  ((lens (and (not (zerop cl--optimize-safety))
+                       (cl--check-bound-indices cl-seq1 cl-seq2 cl-keys)))
+            (len1 (if lens (car lens) (or cl-end1 (length cl-seq1))))
+            (len2 (if lens (cdr lens) (or cl-end2 (length cl-seq2)))))
+      (if (and (eq cl-seq1 cl-seq2) (<= cl-start2 cl-start1))
+          (or (= cl-start1 cl-start2)
+              (let* ((cl-len len1)
+                     (cl-n (min (- (or cl-end1 cl-len) cl-start1)
+                                (- (or cl-end2 cl-len) cl-start2))))
+                (while (>= (setq cl-n (1- cl-n)) 0)
+                  (setf (elt cl-seq1 (+ cl-start1 cl-n))
+                        (elt cl-seq2 (+ cl-start2 cl-n))))))
+        (if (listp cl-seq1)
+            (let ((cl-p1 (nthcdr cl-start1 cl-seq1))
+                  (cl-n1 (and cl-end1 (- cl-end1 cl-start1))))
+              (if (listp cl-seq2)
+                  (let ((cl-p2 (nthcdr cl-start2 cl-seq2))
+                        (cl-n (cond ((and cl-n1 cl-end2)
+                                     (min cl-n1 (- cl-end2 cl-start2)))
+                                    ((and cl-n1 (null cl-end2)) cl-n1)
+                                    ((and (null cl-n1) cl-end2) (- cl-end2 
cl-start2)))))
+                    (while (and cl-p1 cl-p2 (or (null cl-n) (>= (cl-decf cl-n) 
0)))
+                      (setcar cl-p1 (car cl-p2))
+                      (setq cl-p1 (cdr cl-p1) cl-p2 (cdr cl-p2))))
+                (setq cl-end2 (if (null cl-n1)
+                                  (or cl-end2 len2)
+                                (min (or cl-end2 len2)
+                                     (+ cl-start2 cl-n1))))
+                (while (and cl-p1 (< cl-start2 cl-end2))
+                  (setcar cl-p1 (aref cl-seq2 cl-start2))
+                  (setq cl-p1 (cdr cl-p1) cl-start2 (1+ cl-start2)))))
+          (setq cl-end1 (min (or cl-end1 len1)
+                             (+ cl-start1 (- (or cl-end2 len2)
+                                             cl-start2))))
+          (if (listp cl-seq2)
+              (let ((cl-p2 (nthcdr cl-start2 cl-seq2)))
+                (while (< cl-start1 cl-end1)
+                  (aset cl-seq1 cl-start1 (car cl-p2))
+                  (setq cl-p2 (cdr cl-p2) cl-start1 (1+ cl-start1))))
+            (while (< cl-start1 cl-end1)
+              (aset cl-seq1 cl-start1 (aref cl-seq2 cl-start2))
+              (setq cl-start2 (1+ cl-start2) cl-start1 (1+ cl-start1)))))))
     cl-seq1))
 
 ;;;###autoload
@@ -219,7 +280,9 @@ cl-remove
 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:test :test-not :key :if :if-not :count :from-end
                        (:start 0) :end) ()
-    (let ((len (length cl-seq)))
+    (let ((len (if (zerop cl--optimize-safety)
+                   (length cl-seq)
+                 (cl--check-bound-indices cl-seq nil cl-keys))))
       (if (<= (or cl-count (setq cl-count len)) 0)
        cl-seq
         (if (or (nlistp cl-seq) (and cl-from-end (< cl-count (/ len 2))))
@@ -283,7 +346,9 @@ cl-delete
 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:test :test-not :key :if :if-not :count :from-end
                        (:start 0) :end) ()
-    (let ((len (length cl-seq)))
+    (let ((len (if (zerop cl--optimize-safety)
+                   (length cl-seq)
+                 (cl--check-bound-indices cl-seq nil cl-keys))))
       (if (<= (or cl-count (setq cl-count len)) 0)
        cl-seq
       (if (listp cl-seq)
@@ -356,39 +421,42 @@ cl--delete-duplicates
           ;; We need to parse :if, otherwise `cl-if' is unbound.
           (:test :test-not :key (:start 0) :end :from-end :if)
          ()
-       (if cl-from-end
-           (let ((cl-p (nthcdr cl-start cl-seq)) cl-i)
-             (setq cl-end (- (or cl-end (length cl-seq)) cl-start))
-             (while (> cl-end 1)
-               (setq cl-i 0)
-               (while (setq cl-i (cl--position (cl--check-key (car cl-p))
-                                                (cdr cl-p) cl-i (1- cl-end)))
-                 (if cl-copy (setq cl-seq (copy-sequence cl-seq)
-                                   cl-p (nthcdr cl-start cl-seq) cl-copy nil))
-                 (let ((cl-tail (nthcdr cl-i cl-p)))
-                   (setcdr cl-tail (cdr (cdr cl-tail))))
-                 (setq cl-end (1- cl-end)))
-               (setq cl-p (cdr cl-p) cl-end (1- cl-end)
-                     cl-start (1+ cl-start)))
-             cl-seq)
-         (setq cl-end (- (or cl-end (length cl-seq)) cl-start))
-         (while (and (cdr cl-seq) (= cl-start 0) (> cl-end 1)
-                     (cl--position (cl--check-key (car cl-seq))
-                                    (cdr cl-seq) 0 (1- cl-end)))
-           (setq cl-seq (cdr cl-seq) cl-end (1- cl-end)))
-         (let ((cl-p (if (> cl-start 0) (nthcdr (1- cl-start) cl-seq)
-                       (setq cl-end (1- cl-end) cl-start 1) cl-seq)))
-           (while (and (cdr (cdr cl-p)) (> cl-end 1))
-             (if (cl--position (cl--check-key (car (cdr cl-p)))
-                                (cdr (cdr cl-p)) 0 (1- cl-end))
-                 (progn
-                   (if cl-copy (setq cl-seq (copy-sequence cl-seq)
-                                     cl-p (nthcdr (1- cl-start) cl-seq)
-                                     cl-copy nil))
-                   (setcdr cl-p (cdr (cdr cl-p))))
-               (setq cl-p (cdr cl-p)))
-             (setq cl-end (1- cl-end) cl-start (1+ cl-start)))
-           cl-seq)))
+        (let ((len (if (zerop cl--optimize-safety)
+                   (or cl-end (length cl-seq))
+                 (cl--check-bound-indices cl-seq nil cl-keys))))
+          (if cl-from-end
+              (let ((cl-p (nthcdr cl-start cl-seq)) cl-i)
+                (setq cl-end (- (or cl-end len) cl-start))
+                (while (> cl-end 1)
+                  (setq cl-i 0)
+                  (while (setq cl-i (cl--position (cl--check-key (car cl-p))
+                                                  (cdr cl-p) cl-i (1- cl-end)))
+                    (if cl-copy (setq cl-seq (copy-sequence cl-seq)
+                                      cl-p (nthcdr cl-start cl-seq) cl-copy 
nil))
+                    (let ((cl-tail (nthcdr cl-i cl-p)))
+                      (setcdr cl-tail (cdr (cdr cl-tail))))
+                    (setq cl-end (1- cl-end)))
+                  (setq cl-p (cdr cl-p) cl-end (1- cl-end)
+                        cl-start (1+ cl-start)))
+                cl-seq)
+            (setq cl-end (- (or cl-end len) cl-start))
+            (while (and (cdr cl-seq) (= cl-start 0) (> cl-end 1)
+                        (cl--position (cl--check-key (car cl-seq))
+                                      (cdr cl-seq) 0 (1- cl-end)))
+              (setq cl-seq (cdr cl-seq) cl-end (1- cl-end)))
+            (let ((cl-p (if (> cl-start 0) (nthcdr (1- cl-start) cl-seq)
+                          (setq cl-end (1- cl-end) cl-start 1) cl-seq)))
+              (while (and (cdr (cdr cl-p)) (> cl-end 1))
+                (if (cl--position (cl--check-key (car (cdr cl-p)))
+                                  (cdr (cdr cl-p)) 0 (1- cl-end))
+                    (progn
+                      (if cl-copy (setq cl-seq (copy-sequence cl-seq)
+                                        cl-p (nthcdr (1- cl-start) cl-seq)
+                                        cl-copy nil))
+                      (setcdr cl-p (cdr (cdr cl-p))))
+                  (setq cl-p (cdr cl-p)))
+                (setq cl-end (1- cl-end) cl-start (1+ cl-start)))
+              cl-seq))))
     (let ((cl-res (cl--delete-duplicates (append cl-seq nil) cl-keys nil)))
       (if (stringp cl-seq) (concat cl-res) (vconcat cl-res)))))
 
@@ -400,21 +468,24 @@ cl-substitute
 \nKeywords supported:  :test :test-not :key :count :start :end :from-end
 \n(fn NEW OLD SEQ [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:test :test-not :key :if :if-not :count
-                       (:start 0) :end :from-end) ()
-    (if (or (eq cl-old cl-new)
-           (<= (or cl-count (setq cl-from-end nil
-                                  cl-count (length cl-seq))) 0))
-       cl-seq
-      (let ((cl-i (cl--position cl-old cl-seq cl-start cl-end)))
-       (if (not cl-i)
-           cl-seq
-         (setq cl-seq (copy-sequence cl-seq))
-         (unless cl-from-end
-           (setf (elt cl-seq cl-i) cl-new)
-           (cl-incf cl-i)
-           (cl-decf cl-count))
-         (apply 'cl-nsubstitute cl-new cl-old cl-seq :count cl-count
-                :start cl-i cl-keys))))))
+                               (:start 0) :end :from-end) ()
+    (let ((len (if (zerop cl--optimize-safety)
+                   (length cl-seq)
+                 (cl--check-bound-indices cl-seq nil cl-keys))))
+      (if (or (eq cl-old cl-new)
+              (<= (or cl-count (setq cl-from-end nil
+                                     cl-count len)) 0))
+          cl-seq
+        (let ((cl-i (cl--position cl-old cl-seq cl-start cl-end)))
+          (if (not cl-i)
+              cl-seq
+            (setq cl-seq (copy-sequence cl-seq))
+            (unless cl-from-end
+              (setf (elt cl-seq cl-i) cl-new)
+              (cl-incf cl-i)
+              (cl-decf cl-count))
+            (apply 'cl-nsubstitute cl-new cl-old cl-seq :count cl-count
+                   :start cl-i cl-keys)))))))
 
 ;;;###autoload
 (defun cl-substitute-if (cl-new cl-pred cl-list &rest cl-keys)
@@ -442,7 +513,9 @@ cl-nsubstitute
 \n(fn NEW OLD SEQ [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:test :test-not :key :if :if-not :count
                        (:start 0) :end :from-end) ()
-    (let ((len (length cl-seq)))
+    (let ((len (if (zerop cl--optimize-safety)
+                   (length cl-seq)
+                 (cl--check-bound-indices cl-seq nil cl-keys))))
       (or (eq cl-old cl-new) (<= (or cl-count (setq cl-count len)) 0)
          (if (and (listp cl-seq) (or (not cl-from-end) (> cl-count (/ len 2))))
            (let ((cl-p (nthcdr cl-start cl-seq)))
@@ -517,8 +590,11 @@ cl-position
 \nKeywords supported:  :test :test-not :key :start :end :from-end
 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:test :test-not :key :if :if-not
-                       (:start 0) :end :from-end) ()
-    (cl--position cl-item cl-seq cl-start cl-end cl-from-end)))
+                               (:start 0) :end :from-end) ()
+    (let ((end (if (not (zerop cl--optimize-safety))
+                   (cl--check-bound-indices cl-seq nil cl-keys)
+                 cl-end)))
+      (cl--position cl-item cl-seq cl-start end cl-from-end))))
 
 (defun cl--position (cl-item cl-seq cl-start &optional cl-end cl-from-end)
   (if (listp cl-seq)
@@ -562,8 +638,11 @@ cl-count
 \nKeywords supported:  :test :test-not :key :start :end
 \n(fn ITEM SEQ [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:test :test-not :key :if :if-not (:start 0) :end) ()
-    (let ((cl-count 0) cl-x)
-      (or cl-end (setq cl-end (length cl-seq)))
+    (let ((len (if (zerop cl--optimize-safety)
+                   (or cl-end (length cl-seq))
+                 (cl--check-bound-indices cl-seq nil cl-keys)))
+          (cl-count 0) cl-x)
+      (or cl-end (setq cl-end len))
       (if (consp cl-seq) (setq cl-seq (nthcdr cl-start cl-seq)))
       (while (< cl-start cl-end)
        (setq cl-x (if (consp cl-seq) (pop cl-seq) (aref cl-seq cl-start)))
@@ -593,28 +672,32 @@ cl-mismatch
 \nKeywords supported:  :test :test-not :key :start1 :end1 :start2 :end2 
:from-end
 \n(fn SEQ1 SEQ2 [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:test :test-not :key :from-end
-                       (:start1 0) :end1 (:start2 0) :end2) ()
-    (or cl-end1 (setq cl-end1 (length cl-seq1)))
-    (or cl-end2 (setq cl-end2 (length cl-seq2)))
-    (if cl-from-end
-       (progn
-         (while (and (< cl-start1 cl-end1) (< cl-start2 cl-end2)
-                     (cl--check-match (elt cl-seq1 (1- cl-end1))
-                                     (elt cl-seq2 (1- cl-end2))))
-           (setq cl-end1 (1- cl-end1) cl-end2 (1- cl-end2)))
-         (and (or (< cl-start1 cl-end1) (< cl-start2 cl-end2))
-              (1- cl-end1)))
-      (let ((cl-p1 (and (listp cl-seq1) (nthcdr cl-start1 cl-seq1)))
-           (cl-p2 (and (listp cl-seq2) (nthcdr cl-start2 cl-seq2))))
-       (while (and (< cl-start1 cl-end1) (< cl-start2 cl-end2)
-                   (cl--check-match (if cl-p1 (car cl-p1)
-                                     (aref cl-seq1 cl-start1))
-                                   (if cl-p2 (car cl-p2)
-                                     (aref cl-seq2 cl-start2))))
-         (setq cl-p1 (cdr cl-p1) cl-p2 (cdr cl-p2)
-               cl-start1 (1+ cl-start1) cl-start2 (1+ cl-start2)))
-       (and (or (< cl-start1 cl-end1) (< cl-start2 cl-end2))
-            cl-start1)))))
+                               (:start1 0) :end1 (:start2 0) :end2) ()
+    (let* ((lens (and (not (zerop cl--optimize-safety))
+                       (cl--check-bound-indices cl-seq1 cl-seq2 cl-keys)))
+            (len1 (if lens (car lens) (or cl-end1 (length cl-seq1))))
+            (len2 (if lens (cdr lens) (or cl-end2 (length cl-seq2)))))
+      (or cl-end1 (setq cl-end1 len1))
+      (or cl-end2 (setq cl-end2 len2))
+      (if cl-from-end
+          (progn
+            (while (and (< cl-start1 cl-end1) (< cl-start2 cl-end2)
+                        (cl--check-match (elt cl-seq1 (1- cl-end1))
+                                         (elt cl-seq2 (1- cl-end2))))
+              (setq cl-end1 (1- cl-end1) cl-end2 (1- cl-end2)))
+            (and (or (< cl-start1 cl-end1) (< cl-start2 cl-end2))
+                 (1- cl-end1)))
+        (let ((cl-p1 (and (listp cl-seq1) (nthcdr cl-start1 cl-seq1)))
+              (cl-p2 (and (listp cl-seq2) (nthcdr cl-start2 cl-seq2))))
+          (while (and (< cl-start1 cl-end1) (< cl-start2 cl-end2)
+                      (cl--check-match (if cl-p1 (car cl-p1)
+                                         (aref cl-seq1 cl-start1))
+                                       (if cl-p2 (car cl-p2)
+                                         (aref cl-seq2 cl-start2))))
+            (setq cl-p1 (cdr cl-p1) cl-p2 (cdr cl-p2)
+                  cl-start1 (1+ cl-start1) cl-start2 (1+ cl-start2)))
+          (and (or (< cl-start1 cl-end1) (< cl-start2 cl-end2))
+               cl-start1))))))
 
 ;;;###autoload
 (defun cl-search (cl-seq1 cl-seq2 &rest cl-keys)
@@ -624,24 +707,28 @@ cl-search
 \nKeywords supported:  :test :test-not :key :start1 :end1 :start2 :end2 
:from-end
 \n(fn SEQ1 SEQ2 [KEYWORD VALUE]...)"
   (cl--parsing-keywords (:test :test-not :key :from-end
-                       (:start1 0) :end1 (:start2 0) :end2) ()
-    (or cl-end1 (setq cl-end1 (length cl-seq1)))
-    (or cl-end2 (setq cl-end2 (length cl-seq2)))
-    (if (>= cl-start1 cl-end1)
-       (if cl-from-end cl-end2 cl-start2)
-      (let* ((cl-len (- cl-end1 cl-start1))
-            (cl-first (cl--check-key (elt cl-seq1 cl-start1)))
-            (cl-if nil) cl-pos)
-       (setq cl-end2 (- cl-end2 (1- cl-len)))
-       (while (and (< cl-start2 cl-end2)
-                   (setq cl-pos (cl--position cl-first cl-seq2
-                                               cl-start2 cl-end2 cl-from-end))
-                   (apply 'cl-mismatch cl-seq1 cl-seq2
-                          :start1 (1+ cl-start1) :end1 cl-end1
-                          :start2 (1+ cl-pos) :end2 (+ cl-pos cl-len)
-                          :from-end nil cl-keys))
-         (if cl-from-end (setq cl-end2 cl-pos) (setq cl-start2 (1+ cl-pos))))
-       (and (< cl-start2 cl-end2) cl-pos)))))
+                               (:start1 0) :end1 (:start2 0) :end2) ()
+    (let* ((lens (and (not (zerop cl--optimize-safety))
+                       (cl--check-bound-indices cl-seq1 cl-seq2 cl-keys)))
+            (len1 (if lens (car lens) (or cl-end1 (length cl-seq1))))
+            (len2 (if lens (cdr lens) (or cl-end2 (length cl-seq2)))))
+      (or cl-end1 (setq cl-end1 len1))
+      (or cl-end2 (setq cl-end2 len2))
+      (if (>= cl-start1 cl-end1)
+          (if cl-from-end cl-end2 cl-start2)
+        (let* ((cl-len (- cl-end1 cl-start1))
+               (cl-first (cl--check-key (elt cl-seq1 cl-start1)))
+               (cl-if nil) cl-pos)
+          (setq cl-end2 (- cl-end2 (1- cl-len)))
+          (while (and (< cl-start2 cl-end2)
+                      (setq cl-pos (cl--position cl-first cl-seq2
+                                                 cl-start2 cl-end2 
cl-from-end))
+                      (apply 'cl-mismatch cl-seq1 cl-seq2
+                             :start1 (1+ cl-start1) :end1 cl-end1
+                             :start2 (1+ cl-pos) :end2 (+ cl-pos cl-len)
+                             :from-end nil cl-keys))
+            (if cl-from-end (setq cl-end2 cl-pos) (setq cl-start2 (1+ 
cl-pos))))
+          (and (< cl-start2 cl-end2) cl-pos))))))
 
 ;;;###autoload
 (defun cl-sort (cl-seq cl-pred &rest cl-keys)
diff --git a/test/lisp/emacs-lisp/cl-seq-tests.el 
b/test/lisp/emacs-lisp/cl-seq-tests.el
index 61e3d72033..9c6738048a 100644
--- a/test/lisp/emacs-lisp/cl-seq-tests.el
+++ b/test/lisp/emacs-lisp/cl-seq-tests.el
@@ -302,6 +302,101 @@ cl-seq--with-side-effects
     (should (equal '(2 8) (last (cl-replace list list2) 2)))
     (should (equal '(1 1) (last (cl-fill list 1) 2)))))
 
+(ert-deftest cl-seq-check-bounds ()
+  (let ((lst (list 1 2 3))
+        (lst2 (list 'a 'b 'c))
+        ;; t means pass, nil means fails.
+        (tests '("((lambda (x y) (cl-reduce #'max x :start 1)) . t)"
+                 "((lambda (x y) (cl-reduce #'max x :start -1)))"
+                 "((lambda (x y) (cl-reduce #'max x :start 4)))"
+                 "((lambda (x y) (cl-reduce #'max x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-fill x 'b :start 3)) . t)"
+                 "((lambda (x y) (cl-fill x 'b :start 4)))"
+                 "((lambda (x y) (cl-fill x 'b :start -1)))"
+                 "((lambda (x y) (cl-fill x 'b :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-replace x y :start1 3)) . t)"
+                 "((lambda (x y) (cl-replace x y :start2 3)) . t)"
+                 "((lambda (x y) (cl-replace x y :start1 4)))"
+                 "((lambda (x y) (cl-replace x y :start2 4)))"
+                 "((lambda (x y) (cl-replace x y :start1 -1)))"
+                 "((lambda (x y) (cl-replace x y :start2 -1)))"
+                 "((lambda (x y) (cl-replace x y :start1 2 :end1 1)))"
+                 "((lambda (x y) (cl-replace x y :start2 2 :end2 1)))"
+                 ;;
+                 "((lambda (x y) (cl-remove nil x :start 3)) . t)"
+                 "((lambda (x y) (cl-remove nil x :start 4)))"
+                 "((lambda (x y) (cl-remove nil x :start -1)))"
+                 "((lambda (x y) (cl-remove nil x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-delete nil x :start 3)) . t)"
+                 "((lambda (x y) (cl-delete nil x :start 4)))"
+                 "((lambda (x y) (cl-delete nil x :start -1)))"
+                 "((lambda (x y) (cl-delete nil x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-delete-duplicates x :start 3)) . t)"
+                 "((lambda (x y) (cl-delete-duplicates x :start 4)))"
+                 "((lambda (x y) (cl-delete-duplicates x :start -1)))"
+                 "((lambda (x y) (cl-delete-duplicates x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-remove-duplicates x :start 3)) . t)"
+                 "((lambda (x y) (cl-remove-duplicates x :start 4)))"
+                 "((lambda (x y) (cl-remove-duplicates x :start -1)))"
+                 "((lambda (x y) (cl-remove-duplicates x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-substitute 'foo 2 x :start 3)) . t)"
+                 "((lambda (x y) (cl-substitute 'foo 2 x :start 4)))"
+                 "((lambda (x y) (cl-substitute 'foo 2 x :start -1)))"
+                 "((lambda (x y) (cl-substitute 'foo 2 x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-nsubstitute 'foo 2 x :start 3)) . t)"
+                 "((lambda (x y) (cl-nsubstitute 'foo 2 x :start 4)))"
+                 "((lambda (x y) (cl-nsubstitute 'foo 2 x :start -1)))"
+                 "((lambda (x y) (cl-nsubstitute 'foo 2 x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-position 2 x :start 4)))"
+                 "((lambda (x y) (cl-position 2 x :start -1)))"
+                 "((lambda (x y) (cl-position 2 x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-count 2 x :start 3)) . t)"
+                 "((lambda (x y) (cl-count 2 x :start 4)))"
+                 "((lambda (x y) (cl-count 2 x :start -1)))"
+                 "((lambda (x y) (cl-count 2 x :start 2 :end 1)))"
+                 ;;
+                 "((lambda (x y) (cl-mismatch x x :start1 1 :start2 3)) . t)"
+                 "((lambda (x y) (cl-mismatch x x :start1 1 :start2 4)))"
+                 "((lambda (x y) (cl-mismatch x x :start1 4 :start2 1)))"
+                 "((lambda (x y) (cl-mismatch x x :start1 -1 :start2 1)))"
+                 "((lambda (x y) (cl-mismatch x x :start1 1 :start2 -1)))"
+                 "((lambda (x y) (cl-mismatch x x :start1 2 :end1 1)))"
+                 "((lambda (x y) (cl-mismatch x x :start2 2 :end2 1)))"
+                 ;;
+                 "((lambda (x y) (cl-search x x :start1 3 :start2 3)) . t)"
+                 "((lambda (x y) (cl-search x x :start1 4 :start2 4)))"
+                 "((lambda (x y) (cl-search x x :start1 -1 :start2 3)))"
+                 "((lambda (x y) (cl-search x x :start1 1 :start2 -1)))"
+                 "((lambda (x y) (cl-search x x :start1 2 :end1 1)))"
+                 "((lambda (x y) (cl-search x x :start2 2 :end2 1)))"
+                 ;;
+                 "((lambda (x y) (cl-subseq x -1)) . t)"
+                 "((lambda (x y) (cl-subseq x -2 -1)) . t)"
+                 "((lambda (x y) (cl-subseq x -4)))"
+                 "((lambda (x y) (cl-subseq x 2 1)))")))
+    (dolist (limit '("start" "end"))
+      (dolist (x tests)
+        (let ((form
+               (car
+                (read-from-string
+                 (cond ((string-match ":start\\([1-2]?\\) \\([0-9-]+\\) 
:end\\([1-2]?\\)" x)
+                        x)
+                       ((string= limit "start") x)
+                       (t
+                        (replace-regexp-in-string "start" limit x)))))))
+          (if (cdr form)
+              (should (funcall (car form) lst lst2))
+            (should-error (funcall (car form) lst lst2))))))))
+
 
 (provide 'cl-seq-tests)
 ;;; cl-seq-tests.el ends here
-- 
2.11.0

>From be0427570b987e942c934ab8ee841dc326a1a0be Mon Sep 17 00:00:00 2001
From: Tino Calancha <address@hidden>
Date: Mon, 6 Feb 2017 15:21:03 +0900
Subject: [PATCH 2/2] * lisp/edmacro.el (edmacro-format-keys): Prevent :end
 index out-of-range.

---
 lisp/edmacro.el | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/lisp/edmacro.el b/lisp/edmacro.el
index 5fefc3102d..c3608829c0 100644
--- a/lisp/edmacro.el
+++ b/lisp/edmacro.el
@@ -560,10 +560,11 @@ edmacro-format-keys
        (if prefix
            (setq desc (concat (edmacro-sanitize-for-string prefix) desc)))
        (unless (string-match " " desc)
-         (let ((times 1) (pos bind-len))
+         (let ((times 1) (pos bind-len)
+               (rest-mac-len (length rest-mac)))
            (while (not (cl-mismatch rest-mac rest-mac
-                                    :start1 0 :end1 bind-len
-                                    :start2 pos :end2 (+ bind-len pos)))
+                                    :start1 0 :end1 (min bind-len rest-mac-len)
+                                    :start2 pos :end2 (min (+ bind-len pos) 
rest-mac-len)))
              (cl-incf times)
              (cl-incf pos bind-len))
            (when (> times 1)
-- 
2.11.0

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
In GNU Emacs 26.0.50.1 (x86_64-pc-linux-gnu, GTK+ Version 3.22.7)
 of 2017-02-06
Repository revision: d45dbccc5d2360818e70bbb0bc816c62c8cf6cbe



reply via email to

[Prev in Thread] Current Thread [Next in Thread]