Hacktoberfest 2026: the issues maintainers tagged for October, open and beginner-friendly. Browse Hacktoberfest issues

Trailing whitespace strip in <pre> is quadratic on a long whitespace run

Open Beginner friendly
  • Is something wrong?
#286 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
2/5
Estimated time
1-3 hours
Newbie friendliness
78/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
python
Domain
tooling

Research direction

The slow step is re_pre_rstrip.sub in strip_pre in markdownify/init.py, around line 78; the issue proposes replacing it with a str.rstrip call. Read the re_pre_lstrip and re_pre_rstrip definitions, then reproduce with a 64 KB <pre> block of trailing spaces through markdownify(). Done means that case runs in well under a second, the existing 83-test suite still passes, and a new timing test covers the <pre> spellings listed in the issue.

Written by the indexing model from the issue text.

Description

strip_pre() takes quadratic time on a <pre> block whose trailing whitespace run is a run of spaces not ended by a newline. Measured through markdownify() on tag 1.2.3, both trees in one isolated run:

HTML before after
16,000 B 0.6881 s 0.0003 s
32,000 B 2.6570 s 0.0004 s
65,536 B 9.1117 s 0.0007 s
131,072 B 35.5100 s 0.0014 s
16,000 B of ordinary words 0.0011 s 0.0009 s

Each doubling of the block quadruples the time, so the cost belongs to the shape rather than the size - the last row is a document of the same size that converts in a millisecond. The input is an HTML document, so nothing bounds it, and this is the default path: strip_pre defaults to STRIP, while STRIP_ONE uses the separate re_pre_rstrip1 = r'\n *$' and is unaffected.

Cause. re_pre_rstrip = re.compile(r'[ \n]*$') applied with .sub() at __init__.py:78. .sub restarts at every position in the string, and at each one the unbounded [ \n]* run expands and then backtracks looking for the $ that the following character denies.

It is worth saying why the costly shape is spaces and not newlines, because it is not obvious from the pattern alone: re_pre_lstrip = r'^[ \n]*\n' runs on the line before, so a leading newline run is consumed there and re_pre_rstrip is handed a one-character string. With no newline in the block, lstrip does not fire and rstrip receives the whole thing. On the same 65,536-byte input a newline run costs 0.0001 s and a space run 9.3704 s.

Fix. The docstring already describes a strip, so use one:

-    text = re_pre_rstrip.sub('', text)
+    text = text.rstrip(' \n')

Verification.

  • Test suite on both trees at tag 1.2.3: 83 passed, unchanged, with each run asserting which markdownify/__init__.py was loaded and whether it still contains the regex call.
  • Differential: 0 differences from current behaviour across all 29,524 strings of length 0 to 9 over {space, newline, x} - the whole alphabet the two patterns act on.
  • A new test converts a 64 KB <pre> block in under 0.5 s and checks seven <pre> spellings (blank lines, leading and trailing spaces, indentation, empty, whitespace-only). On 1.2.3 the timing test fails and the behaviour test passes.
  • Shapes aimed at the fix rather than the original (pure space run with no terminator, a leading x then a run, many short runs split by x) are all flat: worst 0.0003 s at 65,536 B.

re_pre_rstrip is now unused. I have deliberately left the definition in place to keep the diff to one line, since it is a module-level name that something downstream may import; say the word and I will remove it.

I am happy to open a pull request with the patch if that is easier.

Found with AI assistance (Claude) and verified by hand.

Patch: full patch 
--- a/markdownify/__init__.py
+++ b/markdownify/__init__.py
@@ -75,7 +75,7 @@
 def strip_pre(text):
     """Strip all leading and trailing newlines from a <pre> string."""
     text = re_pre_lstrip.sub('', text)
-    text = re_pre_rstrip.sub('', text)
+    text = text.rstrip(' \n')
     return text
Dominant language
Python
Stars
2.3k
Forks
205
No merged PRs in 30d

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from matthewwithanm/python-markdownify

All issues in matthewwithanm/python-markdownify

Similar issues

More Python issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.