Subject: bug#25122: 24.5; function describe-variable hangs on large variables

From: [email-masked]
Date: Mon, 17 Apr 2017 23:53:30 -0400

[email-masked] writes:

>>> [email-masked] writes:
>>>
>>> Okay, I think I found the real fix now:
>
> Same issue with indent-region.  The gains are not so dramatic for
> typical lisp code that has normal size sexps, but C-x h C-M-\ on
> subr.el's text runs twice as fast for me with the new lisp-indent-region
> function.

Had some test failures due to some corner cases, should all be fixed
now.  I think this is the final patch set.  This also fixes
lisp-indent-region and lisp-indent-line to not indent string literal
contents.

I intend to close this bug as fixed after merging these, as this does
fix the performance bug.  I will probably pursue the alternate pretty
printer separately; it doesn't help performance (after the indent-sexp
performance is fixed), but gives prettier results in some cases.  The
threading idea may also be worth looking at, but can also be considered
separately, as this bug report is already long enough.

>From 9ae3809189d08c15d64363c963eeeae62efae242 Mon Sep 17 00:00:00 2001
From: Noam Postavsky <[email-masked]>
Date: Sun, 12 Mar 2017 23:59:19 -0400
Subject: [PATCH v3 1/4] Don't reparse the sexp in indent-sexp (Bug#25122)

* lisp/emacs-lisp/lisp-mode.el (calculate-lisp-indent): Let
PARSE-START be a parse state that can be reused.
(indent-sexp): Pass the running parse state to calculate-lisp-indent
instead of the sexp beginning position.  Saving the
CONTAINING-SEXP-START returned by `calculate-lisp-indent' is no longer
needed.  Don't bother stopping if we don't descend below init-depth,
since we now alway scan the whole buffer (via syntax-ppss) anyway.
* test/lisp/emacs-lisp/lisp-mode-tests.el (indent-sexp): Add blank
line to test case.
---
 lisp/emacs-lisp/lisp-mode.el            | 76 +++++++++++++++++----------------
 test/lisp/emacs-lisp/lisp-mode-tests.el |  5 ++-
 2 files changed, 43 insertions(+), 38 deletions(-)

diff --git a/lisp/emacs-lisp/lisp-mode.el b/lisp/emacs-lisp/lisp-mode.el
index 2e6e13f1dd..607a4c3d11 100644
--- a/lisp/emacs-lisp/lisp-mode.el
+++ b/lisp/emacs-lisp/lisp-mode.el
@@ -785,6 +785,10 @@ calculate-lisp-indent
 If the value is nil, that means don't change the indentation
 because the line starts inside a string.
 
+PARSE-START may be a buffer position to start parsing from, or a
+parse state as returned by calling `parse-partial-sexp' up to the
+beginning of the current line.
+
 The value can also be a list of the form (COLUMN CONTAINING-SEXP-START).
 This means that following lines at the same level of indentation
 should not necessarily be indented the same as this line.
@@ -798,12 +802,14 @@ calculate-lisp-indent
           (desired-indent nil)
           (retry t)
           calculate-lisp-indent-last-sexp containing-sexp)
-      (if parse-start
-          (goto-char parse-start)
-          (beginning-of-defun))
-      ;; Find outermost containing sexp
-      (while (< (point) indent-point)
-        (setq state (parse-partial-sexp (point) indent-point 0)))
+      (cond ((or (markerp parse-start) (integerp parse-start))
+             (goto-char parse-start))
+            ((null parse-start) (beginning-of-defun))
+            (t (setq state parse-start)))
+      (unless state
+        ;; Find outermost containing sexp
+        (while (< (point) indent-point)
+          (setq state (parse-partial-sexp (point) indent-point 0))))
       ;; Find innermost containing sexp
       (while (and retry
 		  state
@@ -1074,11 +1080,6 @@ indent-sexp
 ENDPOS is encountered."
   (interactive)
   (let* ((indent-stack (list nil))
-         ;; If ENDPOS is non-nil, use beginning of defun as STARTING-POINT.
-         ;; If ENDPOS is nil, it is safe not to scan before point
-         ;; since every line we indent is more deeply nested than point is.
-         (starting-point (save-excursion (if endpos (beginning-of-defun))
-                                         (point)))
          ;; Use `syntax-ppss' to get initial state so we don't get
          ;; confused by starting inside a string.  We don't use
          ;; `syntax-ppss' in the loop, because this is measurably
@@ -1087,8 +1088,7 @@ indent-sexp
          (init-depth (car state))
          (next-depth init-depth)
          (last-depth init-depth)
-         (last-syntax-point (point))
-         (real-endpos endpos))
+         (last-syntax-point (point)))
     (unless endpos
       ;; Get error now if we don't have a complete sexp after point.
       (save-excursion (forward-sexp 1)
@@ -1098,16 +1098,21 @@ indent-sexp
     (save-excursion
       (while (< (point) endpos)
         ;; Parse this line so we can learn the state to indent the
-        ;; next line.
-        (while (progn
-                 (setq state (parse-partial-sexp
-                              last-syntax-point (progn (end-of-line) (point))
-                              nil nil state))
-                 ;; Skip over newlines within strings.
-                 (nth 3 state))
-          (setq state (parse-partial-sexp (point) (point-max)
-                                          nil nil state 'syntax-table))
-          (setq last-syntax-point (point)))
+        ;; next line.  Preserve element 2 of the state (last sexp) for
+        ;; `calculate-lisp-indent'.
+        (let ((last-sexp (nth 2 state)))
+          (while (progn
+                   (setq state (parse-partial-sexp
+                                last-syntax-point (progn (end-of-line) (point))
+                                nil nil state))
+                   (setq last-sexp (or (nth 2 state) last-sexp))
+                   ;; Skip over newlines within strings.
+                   (nth 3 state))
+            (setq state (parse-partial-sexp (point) (point-max)
+                                            nil nil state 'syntax-table))
+            (setq last-sexp (or (nth 2 state) last-sexp))
+            (setq last-syntax-point (point)))
+          (setf (nth 2 state) last-sexp))
         (setq next-depth (car state))
         ;; If the line contains a comment indent it now with
         ;; `indent-for-comment'.
@@ -1120,9 +1125,9 @@ indent-sexp
                                     (make-list (- init-depth next-depth) nil))
                 last-depth (- last-depth next-depth)
                 next-depth init-depth))
+        ;; Now indent the next line according to what we learned from
+        ;; parsing the previous one.
         (forward-line 1)
-        (when (and (not real-endpos) (<= next-depth init-depth))
-          (goto-char endpos))
         (when (< (point) endpos)
           (let ((depth-delta (- next-depth last-depth)))
             (cond ((< depth-delta 0)
@@ -1131,28 +1136,25 @@ indent-sexp
                    (setq indent-stack (nconc (make-list depth-delta nil)
                                              indent-stack))))
             (setq last-depth next-depth))
-          ;; Now indent the next line according
-          ;; to what we learned from parsing the previous one.
-          (skip-chars-forward " \t")
           ;; But not if the line is blank, or just a comment (we
           ;; already called `indent-for-comment' above).
+          (skip-chars-forward " \t")
           (unless (or (eolp) (eq (char-syntax (char-after)) ?<))
-            (let ((this-indent (car indent-stack)))
-              (when (listp this-indent)
-                (let ((val (calculate-lisp-indent
-                            (or (car this-indent) starting-point))))
-                  (setq
-                   this-indent
+            (indent-line-to
+             (or (car indent-stack)
+                 ;; The state here is actually to the end of the
+                 ;; previous line, but that's fine for our purposes.
+                 ;; And parsing over the newline would only destroy
+                 ;; element 2 (last sexp position).
+                 (let ((val (calculate-lisp-indent state)))
                    (cond ((integerp val)
                           (setf (car indent-stack) val))
                          ((consp val) ; (COLUMN CONTAINING-SEXP-START)
-                          (setf (car indent-stack) (cdr val))
                           (car val))
                          ;; `calculate-lisp-indent' only returns nil
                          ;; when we're in a string, but this won't
                          ;; happen because we skip strings above.
-                         (t (error "This shouldn't happen!"))))))
-              (indent-line-to this-indent))))))))
+                         (t (error "This shouldn't happen!"))))))))))))
 
 (defun indent-pp-sexp (&optional arg)
   "Indent each line of the list starting just after point, or prettyprint it.
diff --git a/test/lisp/emacs-lisp/lisp-mode-tests.el b/test/lisp/emacs-lisp/lisp-mode-tests.el
index 8e3f2e185c..27f0bb5ec1 100644
--- a/test/lisp/emacs-lisp/lisp-mode-tests.el
+++ b/test/lisp/emacs-lisp/lisp-mode-tests.el
@@ -31,6 +31,9 @@
          1
        2)
    2)
+ (fun arg1
+
+      arg2)
  (1
   \"string
 noindent\" (\"string2
@@ -58,7 +61,7 @@
         (save-excursion
           (let ((n 0))
             (while (not (eobp))
-              (unless (looking-at "noindent")
+              (unless (looking-at "noindent\\|^[[:blank:]]*$")
                 (insert (make-string n ?\s)))
               (cl-incf n)
               (forward-line))))
-- 
2.11.1

>From b14e7d088ef23074841cb1384503dd60c1e939e9 Mon Sep 17 00:00:00 2001
From: Noam Postavsky <[email-masked]>
Date: Wed, 15 Mar 2017 22:35:47 -0400
Subject: [PATCH v3 2/4] * lisp/emacs-lisp/lisp-mode.el (indent-sexp): Clean up
 marker.

---
 lisp/emacs-lisp/lisp-mode.el | 16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)

diff --git a/lisp/emacs-lisp/lisp-mode.el b/lisp/emacs-lisp/lisp-mode.el
index 607a4c3d11..810fc95614 100644
--- a/lisp/emacs-lisp/lisp-mode.el
+++ b/lisp/emacs-lisp/lisp-mode.el
@@ -1089,12 +1089,13 @@ indent-sexp
          (next-depth init-depth)
          (last-depth init-depth)
          (last-syntax-point (point)))
-    (unless endpos
-      ;; Get error now if we don't have a complete sexp after point.
-      (save-excursion (forward-sexp 1)
-                      ;; We need a marker because we modify the buffer
-                      ;; text preceding endpos.
-                      (setq endpos (point-marker))))
+    ;; We need a marker because we modify the buffer
+    ;; text preceding endpos.
+    (setq endpos (copy-marker
+                  (if endpos endpos
+                    ;; Get error now if we don't have a complete sexp
+                    ;; after point.
+                    (save-excursion (forward-sexp 1) (point)))))
     (save-excursion
       (while (< (point) endpos)
         ;; Parse this line so we can learn the state to indent the
@@ -1154,7 +1155,8 @@ indent-sexp
                          ;; `calculate-lisp-indent' only returns nil
                          ;; when we're in a string, but this won't
                          ;; happen because we skip strings above.
-                         (t (error "This shouldn't happen!"))))))))))))
+                         (t (error "This shouldn't happen!"))))))))))
+    (move-marker endpos nil)))
 
 (defun indent-pp-sexp (&optional arg)
   "Indent each line of the list starting just after point, or prettyprint it.
-- 
2.11.1

>From 6cbe2b3acbb22e75b373d39d716ab4dc1a0f276f Mon Sep 17 00:00:00 2001
From: Noam Postavsky <[email-masked]>
Date: Wed, 15 Mar 2017 21:59:13 -0400
Subject: [PATCH v3 3/4] Remove ignored argument from lisp-indent-line

* lisp/emacs-lisp/lisp-mode.el (lisp-indent-line): Remove WHOLE-EXP
argument, the behavior has long since been handled in
`indent-for-tab-command'.  Also remove redundant `beg' and `shift-amt'
variables and use `indent-line-to'.
---
 lisp/emacs-lisp/lisp-mode.el | 20 +++++++-------------
 1 file changed, 7 insertions(+), 13 deletions(-)

diff --git a/lisp/emacs-lisp/lisp-mode.el b/lisp/emacs-lisp/lisp-mode.el
index 810fc95614..89d5659f30 100644
--- a/lisp/emacs-lisp/lisp-mode.el
+++ b/lisp/emacs-lisp/lisp-mode.el
@@ -748,14 +748,12 @@ lisp-indent-function
   :type 'function
   :group 'lisp)
 
-(defun lisp-indent-line (&optional _whole-exp)
-  "Indent current line as Lisp code.
-With argument, indent any additional lines of the same expression
-rigidly along with this one."
-  (interactive "P")
-  (let ((indent (calculate-lisp-indent)) shift-amt
-	(pos (- (point-max) (point)))
-	(beg (progn (beginning-of-line) (point))))
+(defun lisp-indent-line ()
+  "Indent current line as Lisp code."
+  (interactive)
+  (let ((indent (calculate-lisp-indent))
+	(pos (- (point-max) (point))))
+    (beginning-of-line)
     (skip-chars-forward " \t")
     (if (or (null indent) (looking-at "\\s<\\s<\\s<"))
 	;; Don't alter indentation of a ;;; comment line
@@ -767,11 +765,7 @@ lisp-indent-line
 	  ;; as comment lines, not as code.
 	  (progn (indent-for-comment) (forward-char -1))
 	(if (listp indent) (setq indent (car indent)))
-	(setq shift-amt (- indent (current-column)))
-	(if (zerop shift-amt)
-	    nil
-	  (delete-region beg (point))
-	  (indent-to indent)))
+        (indent-line-to indent))
       ;; If initial point was within line's indentation,
       ;; position after the indentation.  Else stay at same point in text.
       (if (> (- (point-max) pos) (point))
-- 
2.11.1

>From d2f3101d88eb9601a52c06d1171c413fc23e3d8d Mon Sep 17 00:00:00 2001
From: Noam Postavsky <[email-masked]>
Date: Wed, 15 Mar 2017 22:27:27 -0400
Subject: [PATCH v3 4/4] Add new `lisp-indent-region' that doesn't reparse the
 code.

Both `lisp-indent-region' and `lisp-indent-line' now use `syntax-ppss'
to get initial state, so they will no longer indent string literal
contents.

* lisp/emacs-lisp/lisp-mode.el (lisp-ppss): New function, like
`syntax-ppss', but with a more dependable item 2.
(lisp-indent-region): New function, like `indent-region-line-by-line'
but additionally keep a running parse state to avoid reparsing the
code repeatedly.  Use `lisp-ppss' to get initial state.
(lisp-indent-line): Take optional PARSE-STATE argument, pass it to
`calculate-lisp-indent', use `lisp-ppss' if not given.
(lisp-mode-variables): Set `indent-region-function' to
`lisp-indent-region'.
---
 lisp/emacs-lisp/lisp-mode.el | 48 ++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 44 insertions(+), 4 deletions(-)

diff --git a/lisp/emacs-lisp/lisp-mode.el b/lisp/emacs-lisp/lisp-mode.el
index 89d5659f30..54d916887c 100644
--- a/lisp/emacs-lisp/lisp-mode.el
+++ b/lisp/emacs-lisp/lisp-mode.el
@@ -594,6 +594,7 @@ lisp-mode-variables
   ;;  I believe that newcomment's auto-fill code properly deals with it  -stef
   ;;(set (make-local-variable 'adaptive-fill-mode) nil)
   (setq-local indent-line-function 'lisp-indent-line)
+  (setq-local indent-region-function 'lisp-indent-region)
   (setq-local outline-regexp ";;;\\(;* [^ \t\n]\\|###autoload\\)\\|(")
   (setq-local outline-level 'lisp-outline-level)
   (setq-local add-log-current-defun-function #'lisp-current-defun-name)
@@ -748,12 +749,51 @@ lisp-indent-function
   :type 'function
   :group 'lisp)
 
-(defun lisp-indent-line ()
+(defun lisp-ppss (&optional pos)
+  "Return Parse-Partial-Sexp State at POS, defaulting to point.
+Like to `syntax-ppss' but includes the character address of the
+last complete sexp in the innermost containing list at position
+2 (counting from 0).  This is important for lisp indentation."
+  (unless pos (setq pos (point)))
+  (let ((pss (syntax-ppss pos)))
+    (if (nth 9 pss)
+        (parse-partial-sexp (car (last (nth 9 pss))) pos)
+      pss)))
+
+(defun lisp-indent-region (start end)
+  "Indent region as Lisp code, efficiently."
+  (save-excursion
+    (setq end (copy-marker end))
+    (goto-char start)
+    ;; The default `indent-region-line-by-line' doesn't hold a running
+    ;; parse state, which forces each indent call to reparse from the
+    ;; beginning.  That has O(n^2) complexity.
+    (let* ((parse-state (lisp-ppss start))
+           (last-syntax-point start)
+           (pr (unless (minibufferp)
+                 (make-progress-reporter "Indenting region..." (point) end))))
+      (while (< (point) end)
+        (unless (and (bolp) (eolp))
+          (lisp-indent-line parse-state))
+        (forward-line 1)
+        (let ((last-sexp (nth 2 parse-state)))
+          (setq parse-state (parse-partial-sexp last-syntax-point (point)
+                                                nil nil parse-state))
+          ;; It's important to preserve last sexp location for
+          ;; `calculate-lisp-indent'.
+          (unless (nth 2 parse-state)
+            (setf (nth 2 parse-state) last-sexp))
+          (setq last-syntax-point (point)))
+        (and pr (progress-reporter-update pr (point))))
+      (and pr (progress-reporter-done pr))
+      (move-marker end nil))))
+
+(defun lisp-indent-line (&optional parse-state)
   "Indent current line as Lisp code."
   (interactive)
-  (let ((indent (calculate-lisp-indent))
-	(pos (- (point-max) (point))))
-    (beginning-of-line)
+  (let ((pos (- (point-max) (point)))
+        (indent (progn (beginning-of-line)
+                       (calculate-lisp-indent (or parse-state (lisp-ppss))))))
     (skip-chars-forward " \t")
     (if (or (null indent) (looking-at "\\s<\\s<\\s<"))
 	;; Don't alter indentation of a ;;; comment line
-- 
2.11.1