Skip to content

Commit 9d63f04

Browse files
committed
Use a regex-based tokenizer for paths to avoid quadratic compexity
1 parent a4d585e commit 9d63f04

1 file changed

Lines changed: 15 additions & 16 deletions

File tree

‎cairosvg/path.py‎

Lines changed: 15 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55

66
from collections import deque
77
from math import copysign, hypot, pi, radians
8+
from re import finditer
89

910
from .bounding_box import calculate_bounding_box
1011
from .helpers import (
@@ -139,17 +140,15 @@ def path(surface, node):
139140
surface.context.move_to(0, 0)
140141
current_point = 0, 0
141142

142-
while string:
143+
matches = deque(match.groups() for match in finditer(
144+
f'([{PATH_LETTERS}])([^{PATH_LETTERS}]*)', string.strip()))
145+
while matches:
146+
letter, string = matches.popleft()
143147
string = string.strip()
144-
if string.split(' ', 1)[0] in PATH_LETTERS:
145-
letter, string = (string + ' ').split(' ', 1)
146-
if last_letter in (None, 'z', 'Z') and letter not in 'mM':
147-
node.vertices.append(current_point)
148-
first_path_point = current_point
149-
elif letter == 'M':
150-
letter = 'L'
151-
elif letter == 'm':
152-
letter = 'l'
148+
149+
if last_letter in (None, 'z', 'Z') and letter not in 'mM':
150+
node.vertices.append(current_point)
151+
first_path_point = current_point
153152

154153
if last_letter in (None, 'm', 'M', 'z', 'Z'):
155154
first_path_point = None
@@ -187,14 +186,12 @@ def path(surface, node):
187186

188187
# rx=0 or ry=0 means straight line
189188
if not rx or not ry:
190-
if string and string[0] not in PATH_LETTERS:
189+
if string := string.strip():
191190
# As we replace the current operation by l, we must be sure
192191
# that the next letter is set to the real current letter (a
193192
# or A) in case it’s omitted
194-
next_letter = f'{letter} '
195-
else:
196-
next_letter = ''
197-
string = f'l {x3} {y3} {next_letter}{string}'
193+
matches.appendleft((letter, string))
194+
matches.appendleft(('l', f'{x3} {y3}'))
198195
continue
199196

200197
radii_ratio = ry / rx
@@ -449,5 +446,7 @@ def path(surface, node):
449446
if letter not in 'zZ':
450447
node.vertices.append(current_point)
451448

452-
string = string.strip()
449+
if string := string.strip():
450+
next_letter = {'m': 'l', 'M': 'L'}.get(letter, letter)
451+
matches.appendleft((next_letter, string))
453452
last_letter = letter

0 commit comments

Comments
 (0)