From mboxrd@z Thu Jan 1 00:00:00 1970 From: Lawrence Mitchell Subject: [PATCH v2] ox: Cache locations of fuzzy links Date: Thu, 02 May 2013 10:03:13 +0100 Message-ID: <874nelycry.fsf_-_@gmx.li> References: <877gjnojsq.fsf@Rainer.invalid> <5654CA29-5F6D-4E8B-8B8B-C3609D76D189@gmail.com> <8761z5gw6w.fsf@gmx.li> <87zjwhxjla.fsf@Rainer.invalid> <87bo8uyjtc.fsf_-_@gmx.li> <87vc72idau.fsf@gmail.com> Mime-Version: 1.0 Content-Type: text/plain Return-path: Received: from eggs.gnu.org ([208.118.235.92]:35631) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UXpQF-00034q-Mf for emacs-orgmode@gnu.org; Thu, 02 May 2013 05:03:32 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UXpQE-0007Fd-5V for emacs-orgmode@gnu.org; Thu, 02 May 2013 05:03:27 -0400 Received: from plane.gmane.org ([80.91.229.3]:57584) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UXpQD-0007FP-S5 for emacs-orgmode@gnu.org; Thu, 02 May 2013 05:03:26 -0400 Received: from list by plane.gmane.org with local (Exim 4.69) (envelope-from ) id 1UXpQB-0005lp-Mo for emacs-orgmode@gnu.org; Thu, 02 May 2013 11:03:23 +0200 Received: from e4300lm.epcc.ed.ac.uk ([129.215.63.156]) by main.gmane.org with esmtp (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 02 May 2013 11:03:23 +0200 Received: from wence by e4300lm.epcc.ed.ac.uk with local (Gmexim 0.1 (Debian)) id 1AlnuQ-0007hv-00 for ; Thu, 02 May 2013 11:03:23 +0200 List-Id: "General discussions about Org-mode." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-orgmode-bounces+geo-emacs-orgmode=m.gmane.org@gnu.org Sender: emacs-orgmode-bounces+geo-emacs-orgmode=m.gmane.org@gnu.org To: emacs-orgmode@gnu.org * 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 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 <> 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 "<>" 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