Re: Radio links work only in small numbers

[Ihor Radchenko <yantar92@posteo.net>]

[-- Attachment #1: Type: text/plain, Size: 500 bytes --]

Rudolf Adamkovič <salutis@me.com> writes:

> All [[link]]s in my notes perfectly match LEVEL-1 headings, so I figured
> that I may as well ask Org to make links for me.  So, I replaced all the
> ~4000 headings in my notes with radio <<<targets>>>.  However, Org now
> errors out with "Regular expression too big".
>
> Does anyone know how to overcome this limitation?  Or, perhaps someone
> has a patch in works that fixes it?  If so, please let me know!

May you try the attached patch?

[-- Attachment #2: 0001-Work-around-regexp-size-limitation-for-large-number-.patch --]
[-- Type: text/x-patch, Size: 10623 bytes --]

From e01f5a56fff7b3a4c9ad016802a4da6a01053e22 Mon Sep 17 00:00:00 2001
Message-ID: <e01f5a56fff7b3a4c9ad016802a4da6a01053e22.1708334729.git.yantar92@posteo.net>
From: Ihor Radchenko <yantar92@posteo.net>
Date: Mon, 19 Feb 2024 12:19:34 +0300
Subject: [PATCH] Work around regexp size limitation for large number of link
 targets
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* lisp/ol.el (org-target-link-regexp-limit): New constant defining
maximum regexp limit where `org-target-link-regexp' is still safe to
use without triggering "Regexp too long" error.
(org-target-link-regexps): New variable holding a series of shorter
regexps to be used instead of too long single
`org-target-link-regexp'.
(org--re-list-search-forward): New function like `re-search-forward',
but accepting a list of regexps.
(org--re-list-looking-at): New function like `looking-at', but
accepting a list of regexps.
(org-update-radio-target-regexp): When `org-target-link-regexp' is too
long, set `org-target-link-regexps', partitioning the link target list
into smaller regexps.
* lisp/org-element.el (org-element-link-parser):
(org-element--object-lex):
* lisp/org.el (org-activate-target-links): Use
`org--re-list-search-forward' and `org--re-list-looking-at' when
`org-target-link-regexps' is non-nil.
* testing/lisp/test-org-element.el (test-org-element/link-parser): Add
tests.

Reported-by: Rudolf Adamkovič <salutis@me.com>
Link: https://list.orgmode.org/orgmode/m2lenax5m6.fsf@me.com/
---
 lisp/ol.el                       | 68 ++++++++++++++++++++++++++++++--
 lisp/org-element.el              | 16 ++++++--
 lisp/org.el                      |  4 +-
 testing/lisp/test-org-element.el | 17 ++++++++
 4 files changed, 97 insertions(+), 8 deletions(-)

diff --git a/lisp/ol.el b/lisp/ol.el
index a680c43f3..6842fb8fe 100644
--- a/lisp/ol.el
+++ b/lisp/ol.el
@@ -52,6 +52,7 @@ (declare-function org-before-first-heading-p "org" ())
 (declare-function org-do-occur "org" (regexp &optional cleanup))
 (declare-function org-element-at-point "org-element" (&optional pom cached-only))
 (declare-function org-element-cache-refresh "org-element" (pos))
+(declare-function org-element-cache-reset "org-element" (&optional all no-persistence))
 (declare-function org-element-context "org-element" (&optional element))
 (declare-function org-element-lineage "org-element-ast" (datum &optional types with-self))
 (declare-function org-element-link-parser "org-element" ())
@@ -532,6 +533,13 @@ (defconst org-radio-target-regexp (format "<%s>" org-target-regexp)
 
 (defvar-local org-target-link-regexp nil
   "Regular expression matching radio targets in plain text.")
+(defconst org-target-link-regexp-limit (ash 2 15)
+  "Maximum allowed length of regexp.
+See MAX_BUF_SIZE in src/regex-emacs.c")
+(defvar-local org-target-link-regexps nil
+  "List of regular expressions matching radio targets in plain text.
+This list is non-nil, when a single regexp would be too long to match
+all the possible targets, exceeding Emacs' regexp length limit.")
 
 (defvar org-link-types-re nil
   "Matches a link that has a url-like prefix like \"http:\".")
@@ -2078,6 +2086,34 @@ (defun org-insert-link-global ()
   (org-load-modules-maybe)
   (org-run-like-in-org-mode 'org-insert-link))
 
+(defun org--re-list-search-forward (regexp-list &optional bound noerror count)
+  "Like `re-search-forward', but REGEXP-LIST is a list of regexps.
+BOUND, NOERROR, and COUNT are passed to `re-search-forward'."
+  (let (result (min-found most-positive-fixnum)
+               (pos-found nil)
+               (min-found-data nil)
+               (tail regexp-list))
+    (while tail
+      (setq result (save-excursion (re-search-forward (pop tail) bound t count)))
+      (when (and result (< result min-found))
+        (setq min-found result
+              pos-found (match-end 0)
+              min-found-data (match-data))))
+    (if (= most-positive-fixnum min-found)
+        (pcase noerror
+          (`t nil)
+          (_ (re-search-forward (car regexp-list) bound noerror count)))
+      (set-match-data min-found-data)
+      (goto-char pos-found))))
+
+(defun org--re-list-looking-at (regexp-list &optional inhibit-modify)
+  "Like `looking-at', but REGEXP-LIST is a list of regexps.
+INHIBIT-MODIFY is passed to `looking-at'."
+  (catch :found
+    (while regexp-list
+      (when (looking-at (pop regexp-list) inhibit-modify)
+        (throw :found t)))))
+
 ;;;###autoload
 (defun org-update-radio-target-regexp ()
   "Find all radio targets in this file and update the regular expression.
@@ -2115,6 +2151,30 @@ (defun org-update-radio-target-regexp ()
 			targets
 			"\\|")
 		       after-re)))
+    (setq org-target-link-regexps nil)
+    (let (current-length sub-targets)
+      (when (<= org-target-link-regexp-limit (length org-target-link-regexp))
+        (while (or targets sub-targets)
+          (when (and sub-targets
+                     (or (not targets)
+                         (>= (+ current-length (length (car targets)))
+                            org-target-link-regexp-limit)))
+            (push (concat before-re
+                          (mapconcat
+			   (lambda (x)
+			     (replace-regexp-in-string
+			      " +" "\\s-+" (regexp-quote x) t t))
+			   (nreverse sub-targets)
+			   "\\|")
+		          after-re)
+                  org-target-link-regexps)
+            (setq current-length nil
+                  sub-targets nil))
+          (unless current-length
+            (setq current-length (+ (length before-re) (length after-re))))
+          (when targets (push (pop targets) sub-targets))
+          (cl-incf current-length (length (car sub-targets))))
+        (setq org-target-link-regexps (nreverse org-target-link-regexps))))
     (unless (equal old-regexp org-target-link-regexp)
       ;; Clean-up cache.
       (let ((regexp (cond ((not old-regexp) org-target-link-regexp)
@@ -2130,9 +2190,11 @@ (defun org-update-radio-target-regexp ()
 				   after-re)))))
 	(when (and (featurep 'org-element)
                    (not (bound-and-true-p org-mode-loading)))
-	  (org-with-point-at 1
-	    (while (re-search-forward regexp nil t)
-	      (org-element-cache-refresh (match-beginning 1))))))
+          (if org-target-link-regexps
+              (org-element-cache-reset)
+	    (org-with-point-at 1
+	      (while (re-search-forward regexp nil t)
+	        (org-element-cache-refresh (match-beginning 1)))))))
       ;; Re fontify buffer.
       (when (memq 'radio org-highlight-links)
 	(org-restart-font-lock)))))
diff --git a/lisp/org-element.el b/lisp/org-element.el
index 091059c6c..4ad7fe8c3 100644
--- a/lisp/org-element.el
+++ b/lisp/org-element.el
@@ -3842,7 +3842,9 @@ (defun org-element-link-parser ()
        ;; Type 1: Text targeted from a radio target.
        ((and org-target-link-regexp
 	     (save-excursion (or (bolp) (backward-char))
-			     (looking-at org-target-link-regexp)))
+                             (if org-target-link-regexps
+                                 (org--re-list-looking-at org-target-link-regexps)
+                               (looking-at org-target-link-regexp))))
 	(setq type "radio")
 	(setq format 'plain)
 	(setq link-end (match-end 1))
@@ -5215,7 +5217,10 @@ (defun org-element--object-lex (restriction)
 		       ((not (memq 'link restriction)) nil)
 		       ((progn
 		          (unless (bolp) (forward-char -1))
-		          (not (re-search-forward org-target-link-regexp nil t)))
+		          (not
+                           (if org-target-link-regexps
+                               (org--re-list-search-forward org-target-link-regexps nil t)
+                             (re-search-forward org-target-link-regexp nil t))))
 		        nil)
 		       ;; Since we moved backward, we do not want to
 		       ;; match again an hypothetical 1-character long
@@ -5224,8 +5229,11 @@ (defun org-element--object-lex (restriction)
 		       ;; beginning of line, we prevent this here.
 		       ((and (= start (1+ (line-beginning-position)))
 			     (= start (match-end 1)))
-		        (and (re-search-forward org-target-link-regexp nil t)
-			     (1+ (match-beginning 1))))
+		        (and
+                         (if org-target-link-regexps
+                             (org--re-list-search-forward org-target-link-regexps nil t)
+                           (re-search-forward org-target-link-regexp nil t))
+			 (1+ (match-beginning 1))))
 		       (t (1+ (match-beginning 1))))))
 	      found)
          (save-excursion
diff --git a/lisp/org.el b/lisp/org.el
index ad2394ae3..0c0376a9e 100644
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -5705,7 +5705,9 @@ (defun org-activate-target-links (limit)
       ;; `org-target-link-regexp' matches one character before the
       ;; actual target.
       (unless (bolp) (forward-char -1))
-      (when (re-search-forward org-target-link-regexp limit t)
+      (when (if org-target-link-regexps
+                (org--re-list-search-forward org-target-link-regexps limit t)
+              (re-search-forward org-target-link-regexp limit t))
 	(org-remove-flyspell-overlays-in (match-beginning 1) (match-end 1))
 	(add-text-properties (match-beginning 1) (match-end 1)
 			     (list 'mouse-face 'highlight
diff --git a/testing/lisp/test-org-element.el b/testing/lisp/test-org-element.el
index 93754bae5..61cd70693 100644
--- a/testing/lisp/test-org-element.el
+++ b/testing/lisp/test-org-element.el
@@ -2378,6 +2378,23 @@ (ert-deftest test-org-element/link-parser ()
       (org-element-property
        :type
        (org-element-map (org-element-parse-buffer) 'link #'identity nil t)))))
+  (should
+   (equal
+    "radio"
+    (org-test-with-temp-text "<<<radio>>><<<radio2>>><<<foo>>>A radio link"
+      (org-update-radio-target-regexp)
+      (org-element-property
+       :type
+       (org-element-map (org-element-parse-buffer) 'link #'identity nil t)))))
+  (should
+   (equal
+    "radio"
+    (let ((org-target-link-regexp-limit 9))
+      (org-test-with-temp-text "<<<radio>>><<<radio2>>><<<foo>>>A radio link"
+        (org-update-radio-target-regexp)
+        (org-element-property
+         :type
+         (org-element-map (org-element-parse-buffer) 'link #'identity nil t))))))
   ;; Pathological case: radio target of length 1 at beginning of line
   ;; not followed by spaces.
   (should
-- 
2.43.0


[-- Attachment #3: Type: text/plain, Size: 224 bytes --]


-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>