Converting a tag to a string can exceed maximum recursion depth

[tgwizard]

When I do this:

>>> from bs4 import BeautifulSoup
>>> BeautifulSoup(''.join(['<br>' for x in range(1000)]))

An exception is raised:

  .....
  File "/Users/adam/code/tictail/asdfasdf/lib/python2.7/site-packages/bs4/element.py", line 1122, in decode
    indent_contents, eventual_encoding, formatter)
  File "/Users/adam/code/tictail/asdfasdf/lib/python2.7/site-packages/bs4/element.py", line 1191, in decode_contents
    formatter))
  File "/Users/adam/code/tictail/asdfasdf/lib/python2.7/site-packages/bs4/element.py", line 1122, in decode
    indent_contents, eventual_encoding, formatter)
  File "/Users/adam/code/tictail/asdfasdf/lib/python2.7/site-packages/bs4/element.py", line 1191, in decode_contents
    formatter))
  File "/Users/adam/code/tictail/asdfasdf/lib/python2.7/site-packages/bs4/element.py", line 1122, in decode
    indent_contents, eventual_encoding, formatter)
  File "/Users/adam/code/tictail/asdfasdf/lib/python2.7/site-packages/bs4/element.py", line 1191, in decode_contents
    formatter))
  File "/Users/adam/code/tictail/asdfasdf/lib/python2.7/site-packages/bs4/element.py", line 1122, in decode
    indent_contents, eventual_encoding, formatter)
  File "/Users/adam/code/tictail/asdfasdf/lib/python2.7/site-packages/bs4/element.py", line 1185, in decode_contents
    for c in self:
RuntimeError: maximum recursion depth exceeded while calling a Python object

This seems to be because BeautifulSoup uses recursion to find child elements. Also, BeautifulSoup seems to treat `<br>` as a tag that should be closed or self-closed, but that is not necessarily true for HTML5. Same issue with `<img>` and unclosed `<a>` tags, as well as other tags I assume.

[tgwizard (tgwizard)]

Oh, also

> pip freeze
beautifulsoup4==4.4.0
wheel==0.24.0

[Daniel (rigid-launchpad)]

confirmed, this also happens with "real world" html.

on my system, sys.getrecursionlimit() is 1000 (python2.7) which is quite conservative (for a reason, I suppose).
Since python is not a functional language, recursion should be avoided for this kind of task and a stack should be used.

[Connor Cook (cojoco)]

This does not happen for me, using Python 2.7.6 and bs4 version 4.4.1.

sys.getrecursionlimit() was 1000 for me as well, but even when I joined 5000 '<br>' tags it ran with no problems. I got lots of '<br/>' tags, so it looks like they were all turned into self-closing tags.

It doesn't look like this was explicitly fixed in 4.4.1, so it's possible there's just something strange about my machine or that some other change fixed this.

[Emil Stenström (em-u)]

@cojoco: This still happens for me. It seems I have to print the result now to get the error, so maybe bs4 is lazy now. This reproduces the problem for me:

from bs4 import BeautifulSoup
html = ''.join(['<br>' for x in range(1000)])
print BeautifulSoup(html, "html.parser")

(I've also specified the parser to avoid differences in environments)

$ pip freeze
beautifulsoup4==4.4.1
six==1.10.0
wheel==0.24.0

$ python --version
Python 2.7.10

Running Mac OSX 10.11.5 (15F34).

[John Sinteur (sinteur)]

Same problem in de code I use, narrowed it down to this prettify call on the html fetched from porkbun.com

def strip_irrelevant_html(html):
 soup = BeautifulSoup(html, 'html.parser')
 for tag in soup.select(','.join([
   f'{t}[nonce]' for t in ('script', 'style')])):
  del tag['nonce']
 return soup.prettify()

[John Sinteur (sinteur)]

(and that's running on 4.9.3)

[Leonard Richardson (leonardr)]

After taking several stabs at addressing this problem over the years I have a solution I think will work. The only problem is in PageElement.decode_contents(). The issue happens when turning a very deeply nested data structure into a string (not when parsing or searching), and the recursive call is specifically in the formatting code.

I'm working on a solution based on a nonrecursive generator that yields SAX-like events that can be used to create the output string. (Just using .descendants isn't enough because .descendants doesn't announce when tags are closed, only when they're opened.)

In terms of the existing unit tests, the only difference is that pretty-printed strings will now end with a newline, which I think is an improvement over the old code. I've run into one mysterious bug around the code for deactivating pretty-printing for tags like <pre> and <textarea>. So hopefully I can get this ready for testing soon.

[Leonard Richardson (leonardr)]

While setting up a test suite for the new code (to verify that the new algorithm gives the same output on a wide variety of real-world data) I discovered that the nonrecursive string encoding algorithm is incredibly slow. So this needs some performance work before being released.

[Leonard Richardson (leonardr)]

I merged this branch as revision 8944fe70574914cabfc9e6fb6eb048d71be39fb1.

I tested this on a sample of about 1200 web pages. I parsed each document and wrote to disk the results of BeautifulSoup.encode() and BeautifulSoup,prettify(). I did this for both the current release of Beautiful Soup and my new code. I then automatically compared each "old" document to the corresponding "new" document.

The only difference is that the current release of Beautiful Soup doesn't generally end a prettified string with a newline, and my new implementation consistently does this. I think this is an improvement and that _not_ ending a prettified string with a newline represents an oversight that no one ever pointed out.

[Isaac Muse (facelessuser)]

How did performance end up in the end?

[Leonard Richardson (leonardr)]

I fixed the big performance problem. The new algorithm is very slightly slower than recursive function calls, but not enough to worry me. I can also use the same underlying method to fix the stack overflow problem for deepcopying one of these documents, and possibly pickling as well. So it's a net win.

[Leonard Richardson (leonardr)]

Fix released in 4.12.1