Infinite loop when beginning a paragraph with a HTML tag within a `markdown="1"` tag

[rwmpelstilzchen]

Hi,

Thanks for Python-Markdown; it is very useful to me ☺

When running markdown_py -x markdown.extensions.extra foo.md on this input:

This is *true* markdown text.

<div markdown="1">
This is *true* markdown text.

This is <em>true</em> HTML text.
</div>

I get this OK HTML output:

<p>This is <em>true</em> markdown text.</p>
<div>
<p>This is <em>true</em> markdown text.</p>
<p>This is <em>true</em> HTML text.</p>
</div>

But when I try to run the same command on this input:

This is *true* markdown text.

<div markdown="1">
This is *true* markdown text.

<em>True</em> HTML text.
</div>

I get no output and markdown_py is stuck in an infinite loop.

This happens with my up-to-date python-markdown installation on my Arch Linux (version 2.6.2-1 in pacman) as well as with a fresh clone of the git repository.

I’m quite sure this is a genuine bug, but maybe there is something wrong with my local system.

Thanks!
Júda

[ryneeverett]

Confirmed.

[waylan]

I just confirmed as well. Thanks for the report @rwmpelstilzchen.

[ryneeverett]

I just checked out a47899f -- the commit of PR #310 in which I fixed an infinite loop with markdown=1 -- and was not able to reproduce there.

[waylan]

@ryneeverett interesting observation. I just went through your changes in a47899f and none of those have been altered except for your change to lines 178 & 179 of preprocessors.py. That was changed in 5d91369 to address the issue raised in #368. Interestingly, the commit message indicates that it was filling a hole left by the fix for #308.

I just checked and the problem does in fact occur at 5d91369.

I also noticed that it only is reproducible in a very specific scenario:

>>> t='<div markdown=1><em>bar</em></div>'
>>> import markdown
>>> markdown.markdown(t, extensions=['extra'])
u'<div>\n<p><em>bar</em></p>\n</div>'
>>> t='<div markdown=1>\n<em>bar</em>\n</div>'
>>> markdown.markdown(t, extensions=['extra'])
u'<div>\n<p><em>bar</em></p>\n</div>'
>>> t='<div markdown=1>\n\n<em>bar</em>\n\n</div>'
>>> markdown.markdown(t, extensions=['extra'])
u'<div>\n<p><em>bar</em></p>\n</div>'
>>> t='<div markdown=1>\n<em>bar</em> foo\n</div>'
>>> markdown.markdown(t, extensions=['extra'])
u'<div>\n<p><em>bar</em> foo</p>\n</div>'
>>> t='<div markdown=1>\nfoo bar\n\n<em>bar</em>\n</div>'
>>> markdown.markdown(t, extensions=['extra'])
>>> # We get an infinite loop here...

The infinite loop seems to only occur when the fist line of the block is not raw HTML and a later line starts with raw HTML. That is an odd edge case and I'm not all that surprised our tests missed it.

[ryneeverett]

@waylan Perhaps you should just revert that commit since the issue it fixed wasn't technically a bug (and certainly not as unacceptable as an infinite loop). I'd still like to see that issue resolved but it seems like the implementation is going to have to be more complicated than that one.

[waylan]

@facelessuser any input? 5d91369 was your work.

@ryneeverett if In understand it correctly, an infinite loop could still exist in certain edge cases if we backed out 5d91369. If so, that is just as undesirable.

That said, I expect a different solution altogether may be used to parse Raw HTML in Version 3 (some experiments). However, this should still be fixed in 2.x.

[facelessuser]

Okay, reading back through everything, it looks like I was patching the things because processing of markdown could completely break due to how things were getting indexed with the original infinite loop fix. It appears I simply didn't step back far enough to see all possible ways this could break.

I personally don't think reverting 5d91369 is desirable at this point; that feels more like a knee jerk reaction. Simply reverting it will bring back parser breaking bugs. More than likely the problem is more complex than originally thought and we need a little more complexity to handle these edge cases. I say let's not be hasty to come up with a quick solution, and let's come up with the right solution. Reverting only mutates the problem. I imagine a little logic addition can fix the edge case, or maybe some refactoring, but reverting is like picking between two evils; neither outcome is desirable. It has taken quite a while for this issue to resurface, so I don't think we need to panic.

I have some big things I am taking care of right now, but I should have some time by the weekend to dig into this. If I can get to this sooner I will.

[facelessuser]

Okay, I took a quick look, and I see what the issue is. The code was faulty. There are apparently scenarios where the end index is less than the start index. I incorrectly assumed right_listindex would be returned greater than i, but in some cases it is not.

--- a/markdown/preprocessors.py
+++ b/markdown/preprocessors.py
@@ -179,9 +179,12 @@ class HtmlBlockPreprocessor(Preprocessor):
                     if len(items) - right_listindex <= 1:  # last element
                         right_listindex -= 1
                     offset = 1 if i == right_listindex else 0
+                    end_index = right_listindex + offset
+                    if end_index <= i:
+                        end_index = i + 1
                     placeholder = self.markdown.htmlStash.store('\n\n'.join(
-                        items[i:right_listindex + offset]))
-                    del items[i:right_listindex + offset]
+                        items[i:end_index]))
+                    del items[i:end_index]
                     items.insert(i, placeholder)
         return items

Infinite loop no longer occurs and all other tests seem fine. Of course I probably need to do more testing, but this helps catch the current corner case and preserves existing tests as well.

I don't have time to dig into this further, but maybe later in the week.

[ryneeverett]

Any reason to add a new variable for end_index rather than just right_listindex += offset? Even if a new variable is for some reason clearer here, it should be end_listindex because any names not called listindex are string indexes.

[facelessuser]

Any reason to add a new variable for end_index rather than just right_listindex += offset?

It was just a quick and dirty solution. I mainly just wanted to illustrate the problem; wasn't really giving a final solution. As I mentioned earlier, I would probably also want to exercise it more before requesting a pull, and of course clean up and unit tests etc.

If anyone has time and wants to jump on it before I get to it, that is good too 😉.

[inducer]

Here's another reproducer of what seems like a related issue:

INPUT = """
<div id="table" markdown="1">

<div>
</div>
</div>
"""

import markdown
markdown.markdown(INPUT, extensions=["markdown.extensions.extra"])

This will cause an infinite loop and eat up all memory, given enough time. (Encountered on 2.6.2.)

@lukeolson

[facelessuser]

@inducer when I get a chance I will be able to finalize the fix; it will handle your case as well (which is no different to what is listed in the OP).

[waylan]

Fixed in #432.