Fixed bug with circular substitution definitions that put Docutils into an infinite loop. Circular substitution definitions are now detected & reported.

git-svn-id: http://svn.code.sf.net/p/docutils/code/trunk/docutils@4233 929543f6-e4f2-0310-98a6-ba3bd3dd1d04

5 files changed, 122 insertions, 8 deletions

diff --git a/BUGS.txt b/BUGS.txt
index f966daf55..8bb781508 100644
--- a/BUGS.txt
+++ b/BUGS.txt
@@ -146,10 +146,6 @@ Also see the `SourceForge Bug Tracker`_.
   Quite a few nodes are getting a "None" source attribute as well.  In
   particular, see the bodies of definition lists.
 
-* _`Circular substitutions` cause Docutils to hang::
-
-      .. |sub| replace:: |sub|
-
 * Footnote label "5" should be "4" when processing the following
   input::
 
diff --git a/HISTORY.txt b/HISTORY.txt
index 0dc2b06a8..b8d27752e 100644
--- a/HISTORY.txt
+++ b/HISTORY.txt
@@ -147,6 +147,8 @@ Changes Since 0.3.9
     universal.FinalChecks.
   - Fixed bug with doubly-indirect substitutions.
   - Added footnote_reference classes attribute to "TargetNotes".
+  - Fixed bug with circular substitution definitions that put Docutils
+    into an infinite loop.
 
 * docutils/transforms/universal.py:
 
diff --git a/docs/ref/rst/restructuredtext.txt b/docs/ref/rst/restructuredtext.txt
index e0cee6031..1445619b3 100644
--- a/docs/ref/rst/restructuredtext.txt
+++ b/docs/ref/rst/restructuredtext.txt
@@ -2027,7 +2027,7 @@ Substitution definitions are indicated by an explicit markup start
 vertical bar, whitespace, and the definition block.  Substitution text
 may not begin or end with whitespace.  A substitution definition block
 contains an embedded inline-compatible directive (without the leading
-".. "), such as an image_.  For example::
+".. "), such as "image_" or "replace_".  For example::
 
     The |biohazard| symbol must be used on containers used to
     dispose of medical waste.
diff --git a/docutils/transforms/references.py b/docutils/transforms/references.py
index c3de8e3f1..c7e17b50e 100644
--- a/docutils/transforms/references.py
+++ b/docutils/transforms/references.py
@@ -625,6 +625,9 @@ class Footnotes(Transform):
         note.resolved = 1
 
 
+class CircularSubstitutionDefinitionError(Exception): pass
+
+
 class Substitutions(Transform):
 
     """
@@ -661,6 +664,7 @@ class Substitutions(Transform):
         defs = self.document.substitution_defs
         normed = self.document.substitution_names
         subreflist = self.document.traverse(nodes.substitution_reference)
+        nested = {}
         for ref in subreflist:
             refname = ref['refname']
             key = None
@@ -697,9 +701,37 @@ class Substitutions(Transform):
                         parent.replace(parent[index + 1],
                                        parent[index + 1].lstrip())
                 subdef_copy = subdef.deepcopy()
-                # Take care of nested substitution references.
-                subreflist.extend(subdef_copy.traverse(nodes.substitution_reference))
-                ref.replace_self(subdef_copy.children)
+                try:
+                    # Take care of nested substitution references:
+                    for nested_ref in subdef_copy.traverse(
+                          nodes.substitution_reference):
+                        nested_name = normed[nested_ref['refname'].lower()]
+                        if nested_name in nested.setdefault(nested_name, []):
+                            raise CircularSubstitutionDefinitionError
+                        else:
+                            nested[nested_name].append(key)
+                            subreflist.append(nested_ref)
+                except CircularSubstitutionDefinitionError:
+                    parent = ref.parent
+                    if isinstance(parent, nodes.substitution_definition):
+                        msg = self.document.reporter.error(
+                            'Circular substitution definition detected:',
+                            nodes.literal_block(parent.rawsource,
+                                                parent.rawsource),
+                            line=parent.line, base_node=parent)
+                        parent.replace_self(msg)
+                    else:
+                        msg = self.document.reporter.error(
+                            'Circular substitution definition referenced: "%s".'
+                            % refname, base_node=ref)
+                        msgid = self.document.set_id(msg)
+                        prb = nodes.problematic(
+                            ref.rawsource, ref.rawsource, refid=msgid)
+                        prbid = self.document.set_id(prb)
+                        msg.add_backref(prbid)
+                        ref.replace_self(prb)
+                else:
+                    ref.replace_self(subdef_copy.children)
 
 
 class TargetNotes(Transform):
diff --git a/test/test_transforms/test_substitutions.py b/test/test_transforms/test_substitutions.py
index aa3a7c6f6..196bec9a1 100755
--- a/test/test_transforms/test_substitutions.py
+++ b/test/test_transforms/test_substitutions.py
@@ -144,6 +144,90 @@ u"""\
                 exactly
              one character
 """],
+["""\
+.. |sub| replace:: |sub|
+""",
+"""\
+<document source="test data">
+    <system_message level="3" line="1" names="sub" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition detected:
+        <literal_block xml:space="preserve">
+            .. |sub| replace:: |sub|
+"""],
+["""\
+.. |sub| replace:: |indirect1|
+.. |indirect1| replace:: |indirect2|
+.. |indirect2| replace:: |Sub|
+""",
+"""\
+<document source="test data">
+    <system_message level="3" line="1" names="sub" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition detected:
+        <literal_block xml:space="preserve">
+            .. |sub| replace:: |indirect1|
+    <system_message level="3" line="2" names="indirect1" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition detected:
+        <literal_block xml:space="preserve">
+            .. |indirect1| replace:: |indirect2|
+    <system_message level="3" line="3" names="indirect2" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition detected:
+        <literal_block xml:space="preserve">
+            .. |indirect2| replace:: |Sub|
+"""],
+["""\
+.. |indirect1| replace:: |indirect2|
+.. |indirect2| replace:: |Sub|
+.. |sub| replace:: |indirect1|
+
+Use |sub| and |indirect1| and |sub| again (and |sub| one more time).
+""",
+"""\
+<document source="test data">
+    <system_message level="3" line="1" names="indirect1" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition detected:
+        <literal_block xml:space="preserve">
+            .. |indirect1| replace:: |indirect2|
+    <system_message level="3" line="2" names="indirect2" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition detected:
+        <literal_block xml:space="preserve">
+            .. |indirect2| replace:: |Sub|
+    <system_message level="3" line="3" names="sub" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition detected:
+        <literal_block xml:space="preserve">
+            .. |sub| replace:: |indirect1|
+    <paragraph>
+        Use \n\
+        <problematic ids="id8" refid="id7">
+         and \n\
+        <problematic ids="id2" refid="id1">
+            |indirect1|
+         and \n\
+        <problematic ids="id4" refid="id3">
+            |sub|
+         again (and \n\
+        <problematic ids="id6" refid="id5">
+            |sub|
+         one more time).
+    <system_message backrefs="id2" ids="id1" level="3" line="5" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition referenced: "indirect1".
+    <system_message backrefs="id4" ids="id3" level="3" line="5" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition referenced: "sub".
+    <system_message backrefs="id6" ids="id5" level="3" line="5" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition referenced: "sub".
+    <system_message backrefs="id8" ids="id7" level="3" source="test data" type="ERROR">
+        <paragraph>
+            Circular substitution definition referenced: "Sub".
+"""],
 ])
 
 totest['unicode'] = ((Substitutions,), [