[elpa] master 70bd6ce 36/78: Search only in the visible region

[Oleh Krehel]

branch: master
commit 70bd6cec70f280b67f47f6f94e897f0ec8805873
Author: Yasushi SHOJI <address@hidden>
Commit: Oleh Krehel <address@hidden>

    Search only in the visible region
    
    The current version of `avy--regex-candidates` first searches for the
    given regex then skip the match if it's invisible.  This works fine with
    less than a few thousand lines of buffer, however, it takes quit time if
    your have tens of thousand lines hidden, say, in org file.
    
    This patch reverse the strategy. Find all visible regions in given the
    window first, then map the original search function to that list.  This
    change reduced candidates search time from 10 or more seconds to instant
    on my 100,000+ lines of org file.
    
    It might be possible to have hundreds of visibility-interleaved regions
    in a huge window on the 4K or 8K monitor in near the future, but this
    reversed strategy should be fast enough for those system.
    
    This fixes #108.
    Fixes #109
---
 avy.el |   51 +++++++++++++++++++++++++++++++++++++++++----------
 1 files changed, 41 insertions(+), 10 deletions(-)

diff --git a/avy.el b/avy.el
index a030468..e0e9359 100644
--- a/avy.el
+++ b/avy.el
@@ -546,6 +546,33 @@ Use OVERLAY-FN to visualize the decision overlay."
   (setq avy--overlays-back nil)
   (avy--remove-leading-chars))
 
+(defun avy--next-visible-point ()
+  "Return the next closest point without 'invisible property."
+  (let ((s (point)))
+    (while (and (not (= (point-max) (setq s (next-overlay-change s))))
+                (get-char-property s 'invisible)))
+    s))
+
+(defun avy--next-invisible-point ()
+  "Return the next closest point with 'invisible property."
+  (let ((s (point)))
+    (while (and (not (= (point-max) (setq s (next-overlay-change s))))
+                (not (get-char-property s 'invisible))))
+    s))
+
+(defun avy--find-visible-regions (rbeg rend)
+  "Return a list of all visible regions between RBEG and REND."
+  (let (visibles beg)
+    (save-excursion
+      (save-restriction
+        (narrow-to-region rbeg rend)
+        (setq beg (goto-char (point-min)))
+        (while (not (= (point) (point-max)))
+          (goto-char (avy--next-invisible-point))
+          (push (cons beg (point)) visibles)
+          (setq beg (goto-char (avy--next-visible-point))))
+        (nreverse visibles)))))
+
 (defun avy--regex-candidates (regex &optional beg end pred group)
   "Return all elements that match REGEX.
 Each element of the list is ((BEG . END) . WND)
@@ -556,16 +583,20 @@ When GROUP is non-nil, (BEG . END) should delimit that 
regex group."
                               (not (string= regex (upcase regex)))))
         candidates)
     (avy-dowindows nil
-      (let ((we (or end (window-end (selected-window) t))))
-        (save-excursion
-          (goto-char (or beg (window-start)))
-          (while (re-search-forward regex we t)
-            (unless (get-char-property (point) 'invisible)
-              (when (or (null pred)
-                        (funcall pred))
-                (push (cons (cons (match-beginning group)
-                                  (match-end group))
-                            wnd) candidates)))))))
+      (dolist (pair (avy--find-visible-regions
+                     (or beg (window-start))
+                     (or end (window-end (selected-window) t))))
+        (let ((beg (car pair))
+              (end (cdr pair)))
+          (save-excursion
+            (goto-char beg)
+            (while (re-search-forward regex end t)
+              (unless (get-char-property (point) 'invisible)
+                (when (or (null pred)
+                          (funcall pred))
+                  (push (cons (cons (match-beginning group)
+                                    (match-end group))
+                              wnd) candidates))))))))
     (nreverse candidates)))
 
 (defvar avy--overlay-offset 0