[O] [PATCH v2] ox: Cache locations of fuzzy links

[Lawrence Mitchell]

* ox.el (org-export-resolve-fuzzy-link): Look for fuzzy link in a
  cache before trying to resolve it in the parse tree.

When a document contains a large number of identical fuzzy links, it
doesn't make sense to continually search for them.  Instead, cache the
locations in the position independent case.
---
 lisp/ox.el | 42 +++++++++++++++++++++++++++++-------------
 1 file changed, 29 insertions(+), 13 deletions(-)

Changes since v1:

- Pull initialisation of link-cache into let
- Don't use cons cells for keys, just use the path
  - lift found check to top-level let since it's now common

Nicolas Goaziou wrote:
> Hello,

> Lawrence Mitchell <address@hidden> writes:

>> * ox.el (org-export-resolve-fuzzy-link): Look for fuzzy link in a
>>   cache before trying to resolve it in the parse tree.

> Thanks for your patch. A few comments follow.

[...]

> Minor nitpick: I'd rather have this included in the (let ...), like:

>   (let (...
>         (link-cache
>          (or (plist-get info :fuzzy-link-cache)
>              (plist-get (setq info (plist-put info :fuzzy-link-cache
>                                               (make-hash-table :test 'eq)))
>                         :fuzzy-link-cache)))))

I've made this change.  Barring the eq test.

Remember, paths are strings and two strings are only eq or eql if
they are actually the same string (in memory).  In particular:

(let ((p "foo")) (eq (substring p 1) (substring p 1))) => nil
(let ((p "foo")) (eql (substring p 1) (substring p 1))) => nil
(let ((p "foo")) (equal (substring p 1) (substring p 1))) => t

Hence, we must use equal or string-equal as a test in the hash
table.  But string-equal isn't a predefined test, hence equal.

[...]

> I don't get why you need to use such a key. Simply use the link as key
> and `eq' as the test.

I was worried that I'd have the same key pointing to two
different places, but I see now that those worries were
unfounded, since if we didn't see it in the <<path>> case the
first time we never will.  I've simplified the key to just look
for the path.

diff --git a/lisp/ox.el b/lisp/ox.el
index 88b4122..6aa8617 100644
--- a/lisp/ox.el
+++ b/lisp/ox.el
@@ -3976,27 +3976,43 @@ significant."
         ;; Split PATH at white spaces so matches are space
         ;; insensitive.
         (path (org-split-string
-               (if match-title-p (substring raw-path 1) raw-path))))
+               (if match-title-p (substring raw-path 1) raw-path)))
+        ;; Cache for locations of fuzzy links that are not position dependent
+        (link-cache
+         (or (plist-get info :fuzzy-link-cache)
+             (plist-get (setq info (plist-put info :fuzzy-link-cache
+                                              (make-hash-table :test 'equal)))
+                        :fuzzy-link-cache)))
+        (found-in-cache (gethash path link-cache 'fuzzy-link-not-found)))
     (cond
      ;; First try to find a matching "<<path>>" unless user specified
      ;; he was looking for a headline (path starts with a "*"
      ;; character).
      ((and (not match-title-p)
-          (org-element-map (plist-get info :parse-tree) 'target
-            (lambda (blob)
-              (and (equal (org-split-string (org-element-property :value blob))
-                          path)
-                   blob))
-            info t)))
+          (or (not (eq found-in-cache 'fuzzy-link-not-found))
+              (puthash path
+                       (org-element-map (plist-get info :parse-tree) 'target
+                         (lambda (blob)
+                           (and (equal (org-split-string
+                                        (org-element-property :value blob))
+                                       path)
+                                blob))
+                         info t)
+                       link-cache))))
      ;; Then try to find an element with a matching "#+NAME: path"
      ;; affiliated keyword.
      ((and (not match-title-p)
-          (org-element-map (plist-get info :parse-tree)
-              org-element-all-elements
-            (lambda (el)
-              (let ((name (org-element-property :name el)))
-                (when (and name (equal (org-split-string name) path)) el)))
-            info 'first-match)))
+          (or (not (eq found-in-cache 'fuzzy-link-not-found))
+              (puthash path
+                       (org-element-map (plist-get info :parse-tree)
+                           org-element-all-elements
+                         (lambda (el)
+                           (let ((name (org-element-property :name el)))
+                             (when (and name
+                                        (equal (org-split-string name) path))
+                               el)))
+                         info 'first-match)
+                       link-cache))))
      ;; Last case: link either points to a headline or to nothingness.
      ;; Try to find the source, with priority given to headlines with
      ;; the closest common ancestor.  If such candidate is found,

-- 
1.8.2-rc3