marko.parse has quadtratic time for some input

[plaflamme]

Some input causes the parser's runtime to grow exponentially. To replicate:

import time
from marko import parse
def t(i):
  start = time.time()
  parse("X" + " " * i)
  return time.time() - start

tokens=[100,1000,10000,100000]
runtimes=[t(i) for i in tokens]
for (i,t) in enumerate(tokens):
    increase=int(runtimes[i] / runtimes[i-1] if i > 0 else 0)
    print(f"{t},{runtimes[i]},x{increase}")

This prints the following on my machine:

100,0.00041794776916503906,x0
1000,0.007384061813354492,x17
10000,0.38972020149230957,x52
100000,37.4679319858551,x96

As you can see, as the number of tokens increases linearly (x10), the runtime increases exponentially...