SVG path parsing

Question

I have a module in Python for dealing with SVG paths. One of the problems with this is that the SVG spec is obsessed with saving characters to a pointless extent. As such, this path is valid:

"M3.4E-34-2.2e56L23-34z"

And should be parsed as follows:

"M", "3.4E-34", "-2.2e56", "L", "23", "-34", "z"

As you see, anything non-ambiguous is allowed, including separating two numbers only by a minus sign, as long as that minus-sign is not preceded by an "E" or an "e", in which case it should be interpreted as an exponent of the first number. Letters are commands (except "E" and "e" of course), and both comma and any sort of whitespace is allowed as separators.

My module currently uses a rather ugly way of tokenizing the SVG path by multiple string replacements and then a split:

COMMANDS = set('MmZzLlHhVvCcSsQqTtAa')

def _tokenize_path_replace(pathdef):
    # First handle negative exponents:
    pathdef = pathdef.replace('e-', 'NEGEXP').replace('E-', 'NEGEXP')
    # Commas and minus-signs are separators, just like spaces.
    pathdef = pathdef.replace(',', ' ').replace('-', ' -')
    pathdef = pathdef.replace('NEGEXP', 'e-')
    # Commands are allowed without spaces around. Let's insert spaces so it's
    # easier to split later.
    for c in COMMANDS:
        pathdef = pathdef.replace(c, ' %s ' % c)

    # Split the path into elements
    return pathdef.split()

This in fact is doing a total of 23 string replacements on the path, and this is easy, but seems like it should be slow. I tried doing this other ways, but to my surprise they were all slower. I did a character by character tokenizer, which took around 30-40% more time. A user of the module also suggested a regex:

import re
TOKEN_RE = re.compile("[MmZzLlHhVvCcSsQqTtAa]|[-+]?[0-9]*\.?[0-9]+(?:[eE]
[-+]?[0-9]+)?")

def _tokenize_path_replace(pathdef):
    return TOKEN_RE.findall(pathdef)

To my surprise this was also slower than doing 23 string replacements, although just 20-30%.

One thing that could speed up this is if the two expressions in the regex could be merged to one, but I can't find a way of doing that. If some regex guru can, that would improve things.

Any other way of making a speedy parsing of SVG paths that I haven't though about would also be appreciated.

Answer 1

Actually, the problem at hand might not be ideally addressed by replacements or regular expressions. The way how SVG path data is designed, seems to make going through the path string character by character more efficient.

There are essentially five different cases one has to examine. This is a direct consequence of the BNF of SVG Paths (http://www.w3.org/TR/SVG/paths.html#PathDataBNF). When looping over the string, the next character could be

1. a digit or one of the letters 'e' and 'E',
2. a comma or a whitespace,
3. a command letter, i.e. one of the letters 'MmZzLlHhVvCcSsQqTtAa',
4. the dot '.',
5. a sign, i.e. '+' or '-'.

In these five cases the following things are done:

1. We are inside a number and can simply append the character to the current entity.
2. We have encountered a separator and if not already done in the last step, a new empty entity is started.
3. We found a command. This command is added as a separate entity and a new empty one is started.
4. In this case it could be that we were already inside a float (if the flag 'float' is True). Then the dot starts a new entity. Otherwise the dot indicates that we are now in a float. The flag 'float' is then set to True and we stay in the current entity.
5. In this case it could be that the sign is the one of an exponent. Then it is just appended to the current entity. Otherwise a new one is started.

A code example might look like this:

def parse_path(path_data):
    digit_exp = '0123456789eE'
    comma_wsp = ', \t\n\r\f\v'
    drawto_command = 'MmZzLlHhVvCcSsQqTtAa'
    sign = '+-'
    exponent = 'eE'
    float = False
    entity = ''
    for char in path_data:
        if char in digit_exp:
            entity += char
        elif char in comma_wsp and entity:
            yield entity
            float = False
            entity = ''
        elif char in drawto_command:
            if entity:
                yield entity
                float = False
                entity = ''
            yield char
        elif char == '.':
            if float:
                yield entity
                entity = '.'
            else:
                entity += '.'
                float = True
        elif char in sign:
            if entity and entity[-1] not in exponent:
                yield entity
                float = False
                entity = char
            else:
                entity += char
    if entity:
        yield entity

I've run some tests with the above code and it was mostly twice as fast as the regexp version.

In addition, due to the clear cases it is relativly easy to understand what's going on here. This is also helpful for finding and correcting errors.

The problem in the regexp version Peter Taylor pointed to is not severe in most cases. But it might actually lead to wrong parsing. If one considers for example the coordinate 2.e2, the regexp version leads to the two coordinates '2','2'.

Answer 2

With cred to @VedranŠego for kicking me in the right direction, my current solution is simply to split the two regex-parts into separate parsings, the first one a split (instead of a match) and the second one a findall on the floats (because doing a split is near impossible, as - both should and should not be a separator, depending on context).:

import re

COMMANDS = set('MmZzLlHhVvCcSsQqTtAa')
COMMAND_RE = re.compile("([MmZzLlHhVvCcSsQqTtAa])")
FLOAT_RE = re.compile("[-+]?[0-9]*\.?[0-9]+(?:[eE][-+]?[0-9]+)?")

def _tokenize_path(pathdef):
    for x in COMMAND_RE.split(pathdef):
        if x in COMMANDS:
            yield x
        for token in FLOAT_RE.findall(x):
            yield token

I times this with:

from timeit import timeit
num = 1000000

a = timeit("_tokenize_path('M-3.4e38 3.4E+38L-3.4E-38,3.4e-38')", 
             "from svg.path.parser import _tokenize_path", number=num)
b = timeit("_tokenize_path('M600,350 l 50,-25 a25,25 -30 0,1 50,-25 l 50,-25 a25,50 -30 0,1 50,-25 l 50,-25 a25,75 -30 0,1 50,-25 l 50,-25 a25,100 -30 0,1 50,-25 l 50,-25')",
           "from svg.path.parser import _tokenize_path", number=num)
c = timeit("_tokenize_path('M3.4E-34-2.2e56L23-34z')",
           "from svg.path.parser import _tokenize_path", number=num)

print a + b + c

And it runs an astonishing 23 times faster than the "replace" based tokenizer above, and 30 times faster then the regex based tokenizer, even though it essentially does the same thing. :-) I really did not think it would be faster to run this "dual" regex in two separate steps, and I have tried other "two-stage" variations before that was even slower, but this time I arrived at the right combination.