re-search-forward hang in org-link-search

re-search-forward hang in org-link-search

[Matthew MacLean]

[-- Attachment #1.1: Type: text/plain, Size: 2059 bytes --]

So, I found a hang in org-link-search... (In what I think is an Emacs bug,
but posting this here certainly can't hurt.)

When you have a headline with a tag (For example "Mawile" with
":something:" as a tag), and another headline later in the buffer beginning
with the other headline's title within a word boundary (For example "Mawile
stuff", but not "Mawile's stuff"), if you try to create a link to the
second headline, Emacs hangs.

I've attached an Org file where, if you click the link, the buffer will
freeze.

I've narrowed down the problem to the "(re-search-forward re nil t)" form
of the "Regular text search" section of org-link-search in org.el.

The regular expression generated for me when I click that link is:

  ^\*+ \(?:\(BUG\|CANCELLED\|DONE\|FIXED\|KNOWNCAUSE\|REPORT\|TODO\)[
]+\)?\(?:\[#.\][ ]+\)?\(?:COMMENT[ ]+\)?\(?:[ ]+\|\(?:[
]*\[[0-9]*\(?:%\|/[0-9]*\)\][ ]*\)+\)*Mawile\(?:[ ]+\|\(?:[
]*\[[0-9]*\(?:%\|/[0-9]*\)\][ ]*\)+\)+stuff\(?:[ ]+\|\(?:[
]*\[[0-9]*\(?:%\|/[0-9]*\)\][ ]*\)+\)*\(?:[ ]+:[[:alnum:]_@#%%:]+:\)?[ ]*$

And indeed, in the buffer, if you have the point before the first headline
and M-x re-search-forward the above regex, Emacs hangs. (However, if you
have point after the headline, it finds the correct location fine.)

In the org-link-search function, point is set to (point-min) before
performing the re-search-forward, so the hang will occur regardless of
where the link or headline is, as long as the tagged headline comes first.

This happens with the latest Org mode code from the master branch on Emacs
24.5.1 (x86_64) on Linux Mint 17.2.

I think this is an Emacs bug with re-search-forward since that function is
a built-in C function and is hanging, though I figured I should give a
heads up here first. (To either verify my findings in case I missed
something and check it on other Emacs versions, or to find a defensive
workaround.)

This is just speculation, but I think it might be caused by how
re-search-forward is reacting to the tag of the first heading because it is
wrapped in ":" characters.

[-- Attachment #1.2: Type: text/html, Size: 2240 bytes --]

[-- Attachment #2: hang.org --]
[-- Type: application/octet-stream, Size: 110 bytes --]

[[Mawile stuff]]
* Mawile                                                          :something:
* Mawile stuff

Re: re-search-forward hang in org-link-search

[Matthew MacLean]

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

On Thu, Aug 13, 2015 at 12:26 PM, Pip Cet <pipcet@gmail.com> wrote:

> It's not an Emacs bug. Your regular expression whittles down to:
>
> (defvar hang-re "^\\*+ *Mawile\\(?:[ ]+\\)+stuff\\(?:[ ]+\\)*$")
>
> or even
>
> (defvar hang-re "\\(?:[ ]+\\)+s")
>
> That expression matches the string of spaces separating the first
> Mawhile headline from its tags in many many different ways, and is one
> of the type of regular expressions warned about in the (Emacs Lisp
> Reference) manual. We shouldn't be generating it, and it is a bug, but
> it is in Org, not Emacs.
>

Ah... Well, this is the reason I posted it here first.

In that case, the bug is present as late as
a97f2c1830910d7a239dcbb98e200a6e4038acaa.

[-- Attachment #2: Type: text/html, Size: 1133 bytes --]

Re: re-search-forward hang in org-link-search

[Pip Cet]

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

Can you try this patch? That appears to fix the issue here, at least
for this one file, at the cost of yet another shy group added to the
regular expression.

diff --git a/lisp/org.el b/lisp/org.el
index a908d9e..7f46687 100755
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -11128,18 +11128,18 @@ of matched result, with is either
`dedicated' or `fuzzy'."
                       "\\[[0-9]*\\(?:%\\|/[0-9]*\\)\\]"
                       wspaceopt
                       "\\)"))
-              (sep (concat "\\(?:" wspace "+\\|" cookie "+\\)"))
+              (sep (concat "\\(?:\\(?:" wspace "\\|" cookie "\\)+\\)"))
               (re (concat
                org-outline-regexp-bol
                "\\(?:" org-todo-regexp "[ \t]+\\)?"
                "\\(?:\\[#.\\][ \t]+\\)?"
                "\\(?:" org-comment-string "[ \t]+\\)?"
-               sep "*"
+               sep "?"
                (let ((title (mapconcat #'regexp-quote
                            words
-                           (concat sep "+"))))
+                           sep)))
                  (if starred (substring title 1) title))
-               sep "*"
+               sep "?"
                (org-re "\\(?:[ \t]+:[[:alnum:]_@#%%:]+:\\)?")
                "[ \t]*$")))
          (goto-char (point-min))

(Sorry if this arrives in duplicate, I had neglected to configure
Gmail to default to reply-to-all behaviour).


On Thu, Aug 13, 2015 at 6:36 PM, Matthew MacLean <archenoth@gmail.com> wrote:
>
> On Thu, Aug 13, 2015 at 12:26 PM, Pip Cet <pipcet@gmail.com> wrote:
>>
>> It's not an Emacs bug. Your regular expression whittles down to:
>>
>> (defvar hang-re "^\\*+ *Mawile\\(?:[ ]+\\)+stuff\\(?:[ ]+\\)*$")
>>
>> or even
>>
>> (defvar hang-re "\\(?:[ ]+\\)+s")
>>
>> That expression matches the string of spaces separating the first
>> Mawhile headline from its tags in many many different ways, and is one
>> of the type of regular expressions warned about in the (Emacs Lisp
>> Reference) manual. We shouldn't be generating it, and it is a bug, but
>> it is in Org, not Emacs.
>
>
> Ah... Well, this is the reason I posted it here first.
>
> In that case, the bug is present as late as
> a97f2c1830910d7a239dcbb98e200a6e4038acaa.

[-- Attachment #2: org-mode-003.diff --]
[-- Type: text/plain, Size: 897 bytes --]

diff --git a/lisp/org.el b/lisp/org.el
index a908d9e..7f46687 100755
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -11128,18 +11128,18 @@ of matched result, with is either `dedicated' or `fuzzy'."
 				      "\\[[0-9]*\\(?:%\\|/[0-9]*\\)\\]"
 				      wspaceopt
 				      "\\)"))
-		      (sep (concat "\\(?:" wspace "+\\|" cookie "+\\)"))
+		      (sep (concat "\\(?:\\(?:" wspace "\\|" cookie "\\)+\\)"))
 		      (re (concat
 			   org-outline-regexp-bol
 			   "\\(?:" org-todo-regexp "[ \t]+\\)?"
 			   "\\(?:\\[#.\\][ \t]+\\)?"
 			   "\\(?:" org-comment-string "[ \t]+\\)?"
-			   sep "*"
+			   sep "?"
 			   (let ((title (mapconcat #'regexp-quote
 						   words
-						   (concat sep "+"))))
+						   sep)))
 			     (if starred (substring title 1) title))
-			   sep "*"
+			   sep "?"
 			   (org-re "\\(?:[ \t]+:[[:alnum:]_@#%%:]+:\\)?")
 			   "[ \t]*$")))
 		 (goto-char (point-min))

Re: re-search-forward hang in org-link-search

[Matthew MacLean]

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

Yep! This patch works on the original file I noticed the behaviour.

On Thu, Aug 13, 2015 at 12:50 PM, Pip Cet <pipcet@gmail.com> wrote:

> (Sorry if this arrives in duplicate, I had neglected to configure
> Gmail to default to reply-to-all behaviour).
>

I did that earlier as well, it's a curse!

[-- Attachment #2: Type: text/html, Size: 667 bytes --]

Re: re-search-forward hang in org-link-search

[Nicolas Goaziou]

Hello,

Pip Cet <pipcet@gmail.com> writes:

> Can you try this patch? That appears to fix the issue here, at least
> for this one file, at the cost of yet another shy group added to the
> regular expression.

Thanks for the patch.

Would you mind providing a proper commit message and send it again using
"git format-patch"?


Regards,

-- 
Nicolas Goaziou

Re: re-search-forward hang in org-link-search

[Pip Cet]

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

Hi Nicolas,

On Thu, Aug 13, 2015 at 11:37 PM, Nicolas Goaziou
<mail@nicolasgoaziou.fr> wrote:
> Hello,
>
> Pip Cet <pipcet@gmail.com> writes:
>
>> Can you try this patch? That appears to fix the issue here, at least
>> for this one file, at the cost of yet another shy group added to the
>> regular expression.
>
> Thanks for the patch.
>
> Would you mind providing a proper commit message and send it again using
> "git format-patch"?

Of course, here we go. Please let me know if there's anything wrong
with it still. (I don't think gmail copy-and-paste preserves tabs, so
this is sent as an attachment. Is that okay, for future reference?)

It would be great if README_contribute could be updated no longer to
refer to ChangeLog files, and instead refer to the Emacs CONTRIBUTE
file (it would also be great if the special git commit messages could
be generated as easily as C-x 4 a does for ChangeLog entries. What do
people use for that?); I've attached a patch to change that as well,
but I'm not sure whether it's still properly a TINYCHANGE. Again, it
would be great if you could let me know if there's anything wrong with
it so I can avoid making the same mistake for future contributions.

Thanks!
Pip

[-- Attachment #2: 0001-org.el-fix-recursive-regular-expression-backtracking.patch --]
[-- Type: text/x-patch, Size: 1379 bytes --]

From 4dac047849bdb44b631f0b8d7013eb0e15a0f512 Mon Sep 17 00:00:00 2001
From: Philip <pipcet@gmail.com>
Date: Thu, 13 Aug 2015 18:49:56 +0000
Subject: [PATCH 1/2] org.el: fix recursive regular expression backtracking

	* org.el (org-link-search): Avoid recursive regexp
	backtracking behaviour when following search links.

	<http://article.gmane.org/gmane.emacs.orgmode/100010>

	TINYCHANGE
---
 lisp/org.el | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/lisp/org.el b/lisp/org.el
index a908d9e..7f46687 100755
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -11128,18 +11128,18 @@ of matched result, with is either `dedicated' or `fuzzy'."
 				      "\\[[0-9]*\\(?:%\\|/[0-9]*\\)\\]"
 				      wspaceopt
 				      "\\)"))
-		      (sep (concat "\\(?:" wspace "+\\|" cookie "+\\)"))
+		      (sep (concat "\\(?:\\(?:" wspace "\\|" cookie "\\)+\\)"))
 		      (re (concat
 			   org-outline-regexp-bol
 			   "\\(?:" org-todo-regexp "[ \t]+\\)?"
 			   "\\(?:\\[#.\\][ \t]+\\)?"
 			   "\\(?:" org-comment-string "[ \t]+\\)?"
-			   sep "*"
+			   sep "?"
 			   (let ((title (mapconcat #'regexp-quote
 						   words
-						   (concat sep "+"))))
+						   sep)))
 			     (if starred (substring title 1) title))
-			   sep "*"
+			   sep "?"
 			   (org-re "\\(?:[ \t]+:[[:alnum:]_@#%%:]+:\\)?")
 			   "[ \t]*$")))
 		 (goto-char (point-min))
-- 
2.5.0


[-- Attachment #3: 0002-Remove-references-to-ChangeLog.patch --]
[-- Type: text/x-patch, Size: 1297 bytes --]

From f52f2e428d5d981ad6db43cd8c73724c8d62b037 Mon Sep 17 00:00:00 2001
From: Philip <pipcet@gmail.com>
Date: Fri, 14 Aug 2015 16:42:02 +0000
Subject: [PATCH 2/2] 	Remove references to ChangeLog.

	* README_contribute: remove references to ChangeLog.  Instead,
	reference the Emacs `CONTRIBUTE' file which documents how to
	format git commit messages.

        TINYCHANGE
---
 README_contribute | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/README_contribute b/README_contribute
index 3e1ef6d..63ed0bd 100644
--- a/README_contribute
+++ b/README_contribute
@@ -58,10 +58,10 @@ development.
      new mechanism to make sure all changes end up in the right
      place.
 
-   - Creating and pushing a change to the Org-mode core requires
-     you also to provide ChangeLog entries.  Just press `C-x 4 a'
-     in each function or variable you have modified and describe
-     the change you made in the ChangeLog buffer/file.
+   - Org-mode no longer uses ChangeLog entries to document
+     changes. Instead, special commit messages are used, as
+     described in the `CONTRIBUTE' file in the main Emacs
+     repository.
 
    - Among other things, Org-mode is widely appreciated because
      of its simplicity, cleanness and consistency.  We should try
-- 
2.5.0

Re: re-search-forward hang in org-link-search

[Nicolas Goaziou]

Pip Cet <pipcet@gmail.com> writes:

> Of course, here we go. Please let me know if there's anything wrong
> with it still. (I don't think gmail copy-and-paste preserves tabs, so
> this is sent as an attachment. Is that okay, for future reference?)
>
> It would be great if README_contribute could be updated no longer to
> refer to ChangeLog files, and instead refer to the Emacs CONTRIBUTE
> file (it would also be great if the special git commit messages could
> be generated as easily as C-x 4 a does for ChangeLog entries. What do
> people use for that?); I've attached a patch to change that as well,
> but I'm not sure whether it's still properly a TINYCHANGE. Again, it
> would be great if you could let me know if there's anything wrong with
> it so I can avoid making the same mistake for future contributions.

Thanks for your patches. They look good. I applied them with very minor
tweaks, explained below.

> Subject: [PATCH 1/2] org.el: fix recursive regular expression backtracking

"Fix" needs to be capitalized.

>
> 	* org.el (org-link-search): Avoid recursive regexp
> 	backtracking behaviour when following search links.

Emacs uses American spelling: "behavior".

> Subject: [PATCH 2/2] 	Remove references to ChangeLog.

No full stop at the end of the commit summary.

> 	* README_contribute: remove references to ChangeLog.  Instead,

"Remove"

> +   - Org-mode no longer uses ChangeLog entries to document

We try to change "Org-mode" into "Org mode" whenever we can.

> +     changes. Instead, special commit messages are used, as

Sentences are separated with two spaces.


Regards,

Re: re-search-forward hang in org-link-search

[Bastien]

Hi Matthew,

I've no problem with the link in hang.org.

This is with Org 8.3.1 and Emacs 25.0.50.18.

-- 
 Bastien

Re: re-search-forward hang in org-link-search

[Matthew MacLean]

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

Fascinating.

Maybe the recursive-whitespace Regular Expressions that Pip Cet mentioned
are not Emacs freezers in Emacs 25?

On Tue, Aug 18, 2015 at 11:30 AM, Bastien <bzg@gnu.org> wrote:

> Hi Matthew,
>
> I've no problem with the link in hang.org.
>
> This is with Org 8.3.1 and Emacs 25.0.50.18.
>
> --
>  Bastien
>

[-- Attachment #2: Type: text/html, Size: 761 bytes --]

Re: re-search-forward hang in org-link-search

[Bastien]

Matthew MacLean <archenoth@gmail.com> writes:

> Maybe the recursive-whitespace Regular Expressions that Pip Cet
> mentioned are not Emacs freezers in Emacs 25?

No... this is just me using the patched version, sorry for the noise.

-- 
 Bastien

Re: re-search-forward hang in org-link-search

[Matthew MacLean]

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

No worries. If anything it makes be feel better about my own silliness
earlier.

On Tue, Aug 18, 2015 at 11:54 AM, Bastien <bzg@gnu.org> wrote:

> Matthew MacLean <archenoth@gmail.com> writes:
>
> > Maybe the recursive-whitespace Regular Expressions that Pip Cet
> > mentioned are not Emacs freezers in Emacs 25?
>
> No... this is just me using the patched version, sorry for the noise.
>
> --
>  Bastien
>

[-- Attachment #2: Type: text/html, Size: 858 bytes --]

Re: re-search-forward hang in org-link-search

[Bastien]

Matthew MacLean <archenoth@gmail.com> writes:

> No worries. If anything it makes be feel better about my own
> silliness earlier.

Well, I'm good at making people feeling better about their own
silliness, so you're most welcome.

-- 
 Bastien

Re: re-search-forward hang in org-link-search

[Pip Cet]

I'm using Emacs 25.0.50.26, for what it's worth, and they still freeze
Emacs here. I don't recall precisely when the problematic regular
expressions were introduced, though, that might have been after 8.3.1?

On 8/18/15, Matthew MacLean <archenoth@gmail.com> wrote:
> Fascinating.
>
> Maybe the recursive-whitespace Regular Expressions that Pip Cet mentioned
> are not Emacs freezers in Emacs 25?
>
> On Tue, Aug 18, 2015 at 11:30 AM, Bastien <bzg@gnu.org> wrote:
>
>> Hi Matthew,
>>
>> I've no problem with the link in hang.org.
>>
>> This is with Org 8.3.1 and Emacs 25.0.50.18.
>>
>> --
>>  Bastien
>>
>