Python parser for attributes in a HAML template

Question

I'm working on a feature for the HamlPy (Haml for Django) project:

About Haml

For those who don't know, Haml is an indentation-based markup language which compiles to HTML:

%ul#atheletes
    - for athelete in athelete_list
        %li.athelete{'id': 'athelete_{{ athelete.pk }}'}= athelete.name

compiles to

<ul id='atheletes'>
    {% for athelete in athelete_list %}
        <li class='athelete' id='athelete_{{ athelete.pk }}'>{{ athelete.name }}</li>
    {% endfor %}
</ul>

The code

{'id': 'athelete_{{ athelete.pk }}'} is referred to as the 'attribute dictionary'. It is an (almost) valid Python dictionary and is currently parsed with some very ugly regular expressions and an eval(). However, I would like to add some features to it that would no longer make it a valid Python dictionary, e.g. using Haml within the attributes:

%a.link{
    'class':
        - if forloop.first
            link-first
        - else
            - if forloop.last
                link-last
    'href':
        - url some_view
    }

among other things.

I began by writing a class which I could swap out for the eval and would pass all of the current tests:

import re

# Valid characters for dictionary key
re_key = re.compile(r'[a-zA-Z0-9-_]+')
re_nums = re.compile(r'[0-9\.]+')

class AttributeParser:
    """Parses comma-separated HamlPy attribute values"""

    def __init__(self, data, terminator):
        self.terminator=terminator
        self.s = data.lstrip()
        # Index of current character being read
        self.ptr=1

    def consume_whitespace(self, include_newlines=False):
        """Moves the pointer to the next non-whitespace character"""
        whitespace = (' ', '\t', '\r', '\n') if include_newlines else (' ', '\t')

        while self.ptr<len(self.s) and self.s[self.ptr] in whitespace:
            self.ptr+=1
        return self.ptr

    def consume_end_of_value(self):
        # End of value comma or end of string
        self.ptr=self.consume_whitespace()
        if self.s[self.ptr] != self.terminator:
            if self.s[self.ptr] == ',':
                self.ptr+=1
            else:
                raise Exception("Expected comma for end of value (after ...%s), but got '%s' instead" % (self.s[max(self.ptr-10,0):self.ptr], self.s[self.ptr]))


    def read_until_unescaped_character(self, closing, pos=0):
        """
        Moves the dictionary string starting from position *pos*
        until a *closing* character not preceded by a backslash is found.
        Returns a tuple containing the string which was read (without any preceding backslashes)
        and the number of characters which were read.
        """
        initial_pos=pos

        while pos<len(self.s):
            if self.s[pos]==closing and (pos==initial_pos or self.s[pos-1]!='\\'):
                break
            pos+=1
        return (self.s[initial_pos:pos].replace('\\'+closing,closing), pos-initial_pos+1)

    def parse_value(self):
        self.ptr=self.consume_whitespace()

        # Invalid initial value
        val=False
        if self.s[self.ptr]==self.terminator:
            return val

        # String
        if self.s[self.ptr] in ("'",'"'):
            quote=self.s[self.ptr]
            self.ptr += 1
            val,characters_read = self.read_until_unescaped_character(quote, pos=self.ptr)
            self.ptr += characters_read
        # Django variable
        elif self.s[self.ptr:self.ptr+2] == '={':
            self.ptr+=2
            val,characters_read = self.read_until_unescaped_character('}', pos=self.ptr)
            self.ptr += characters_read
            val="{{ %s }}" % val
        # Django tag
        elif self.s[self.ptr:self.ptr+2] in ['-{', '#{']:
            self.ptr+=2
            val,characters_read = self.read_until_unescaped_character('}', pos=self.ptr)
            self.ptr += characters_read
            val=r"{%% %s %%}" % val
        # Boolean Attributes
        elif self.s[self.ptr:self.ptr+4] in ['none','None']:
            val = None
            self.ptr+=4
        # Integers and floats
        else:
            match=re_nums.match(self.s[self.ptr:])
            if match:
                val = match.group(0)
                self.ptr += len(val)

        if val is False:
            raise Exception("Failed to parse dictionary value beginning at: %s" % self.s[self.ptr:])

        self.consume_end_of_value()

        return val



class AttributeDictParser(AttributeParser):
    """
    Parses a Haml element's attribute dictionary string and
    provides a Python dictionary of the element attributes
    """

    def __init__(self, s):
        AttributeParser.__init__(self, s, '}')
        self.dict={}

    def parse(self):
        while self.ptr<len(self.s)-1:
            key = self.__parse_key()

            # Tuple/List parsing
            self.ptr=self.consume_whitespace()
            if self.s[self.ptr] in ('(', '['):
                tl_parser = AttributeTupleAndListParser(self.s[self.ptr:])
                val = tl_parser.parse()
                self.ptr += tl_parser.ptr
                self.consume_end_of_value()
            else:
                val = self.parse_value()

            self.dict[key]=val
        return self.dict

    def __parse_key(self):
        '''Parse key variable and consume up to the colon'''

        self.ptr=self.consume_whitespace(include_newlines=True)

        # Consume opening quote
        quote=None
        if self.s[self.ptr] in ("'",'"'):
            quote = self.s[self.ptr]
            self.ptr += 1

        # Extract key
        if quote:
            key,characters_read = self.read_until_unescaped_character(quote, pos=self.ptr)
            self.ptr+=characters_read
        else:
            key_match = re_key.match(self.s[self.ptr:])
            if key_match is None:
                raise Exception("Invalid key beginning at: %s" % self.s[self.ptr:])
            key = key_match.group(0)
            self.ptr += len(key)

        # Consume colon
        ptr=self.consume_whitespace()
        if self.s[self.ptr]==':':
            self.ptr+=1
        else:
            raise Exception("Expected colon for end of key (after ...%s), but got '%s' instead" % (self.s[max(self.ptr-10,0):self.ptr], self.s[self.ptr]))

        return key

    def render_attributes(self):
        attributes=[]
        for k, v in self.dict.items():
            if k != 'id' and k != 'class':
                # Boolean attributes
                if v==None:
                    attributes.append( "%s" % (k,))
                else:
                    attributes.append( "%s='%s'" % (k,v))

        return ' '.join(attributes)


class AttributeTupleAndListParser(AttributeParser):
    def __init__(self, s):
        if s[0]=='(':
            terminator = ')'
        elif s[0]=='[':
            terminator = ']'
        AttributeParser.__init__(self, s, terminator)

    def parse(self):
        lst=[]

        # Todo: Must be easier way...
        val=True
        while val != False:
            val = self.parse_value()
            if val != False:
                lst.append(val)

        self.ptr +=1

        if self.terminator==')':
            return tuple(lst)
        else:
            return lst

The class can be used stand-alone as follows:

>>> from attribute_dict_parser import AttributeDictParser
>>> a=AttributeDictParser("{'id': 'a', 'class': 'b'}")
>>> d=a.parse()
>>> d
{'id': 'a', 'class': 'b'}
>>> type(d)
<type 'dict'>

AttributeDictParser iterates through characters in s (the attribute dictionary) and uses the variable ptr to track its location (to prevent unnecessary string splicing). The function parse_key parses the keys ('id': and 'class':), and the function parse_value parses the values ('a' and 'b'). parse_value works with data types other than strings. It returns False if it reaches the end of the attribute dictionary, because Null is a valid value to return.

AttributeTupleAndListParser parses list and tuple values, as these are valid values (e.g. {'id': ['a','b','c']}.

Both of these classes inherit from AttributeParser because they share the same way of parsing values.

Questions:

1. Is this a sensible approach? Am I insane to think that I can move from eval()ing the code as a Python dictionary to a custom parser without causing issues for users, just because it passes the tests?

2. I'm worried that the performance hit of writing a parser in an interpreted language will be too much compared to doing the eval(). I've written similar things before for parsing JSON expressions, and was dismayed that for all my optimisations, the two-line regular expression won on the benchmarks. I will do some profiling on it once I've tidied up a few things. Are there any notable ineffeciencies in my approach?

3. There are some things in the old parser that have not been ported to the new one (e.g. supporting the Ruby Haml => syntax). This feature has never been documented however and I doubt anybody knows it's there. What is a good rule of thumb for breaking an undocumented feature in open source projects?

4. I would welcome any feedback on my coding style, as I don't get to be around other developers much.

Answer 1

1. Answers to your questions

1. If the goal of the project is to be able to include Haml in attribute values, then you've got no choice but to switch to your own parser. I haven't looked at the set of test cases, but it does seem plausible that you are going to introduce incompatibilities because of the complexity of Python's own parser. You are going to find that you have users who used the oddities of Python's string syntax (r-strings, \u-escapes and all).

   The way to manage the transition from the old parser to the new is to start out by shipping both, with the old parser selected by default, but the new parser selectable with an option. This gives your users time to discover the incompatibilities and fix them (or submit bug reports). Then in a later release make the new parser the default, but with the old parser available but deprecated. Finally, remove the old parser.

2. Correctness and simplicity first, speed later. You can always port the parser to C if nothing else will do.

3. My answer to question 1 applies here too.

4. See below.

2. Designing a parser

Now, let's look at the code. I thought about making a series of comments on the various misfeatures, but that seems less than helpful, given that the whole design of the parser isn't quite right:

1. There's no separation between the lexer and the parser.

2. You have different classes for different productions in your syntax, so that each time you need to parse a tuple/list, you construct a new AttributeTupleAndListParser object, construct a string for it to parse (by copying the tail of the original string), and then throw away the parser object when done.

3. Some of your parsing methods don't seem well-matched to the syntax of the language, making it difficult to understand what they do. consume_end_of_value is a good example: it doesn't seem to correspond to anything natural in the syntax.

Computer science is by no means a discipline with all the answers, but one thing that we know how to do is write a parser! You don't have to have read the dragon book from cover to cover to know that it's conventional to develop a formal grammar for your language (often written down in a variation on Backus–Naur form), and then split your code into a lexical analyzer (which transforms source code into tokens using a finite state machine or something similar) and a parser which takes a stream of tokens and constructs a syntax tree or some other form of output based on the syntax of the input.

Sticking to this convention has a bunch of advantages: the existence of a formal grammar makes it easier to build compatible implementations; you can modify and test the lexical analyzer independently from the parser and vice versa; and other programmers will find it easier to understand and modify your code.

3. Rewriting your parser conventionally

Here's how I might start rewriting your parser to use the conventional approach. This implements a deliberately incomplete subset of the HamlPy attribute language, in order to keep the code short and to get it finished in a reasonable amount of time.

First, a class whose instances represent source tokens. The original string and position of each token is recorded in that token so that we can easily produce an error message related to that token. I've used the built-in exception SyntaxError here so that the error messages match those from other Python libraries. (You might later want to extend this so that the class can represent tokens from files as well as tokens from strings.)

class Token(object):
    """
    An object representing a token in a HamlPy document. Construct it
    using `Token(type, value, source, start, end)` where:

    `type` is the token type (`Token.DELIMITER`, `Token.STRING`, etc);
    `value` is the token value;
    `source` is the string from which the token was taken;
    `start` is the character position in `source` where the token starts;
    `ends` is the character position in `source` where the token finishes.
    """

    # Enumeration of token types.
    DELIMITER = 1
    STRING = 2
    END = 3
    ERROR = 4

    def __init__(self, type, value, source, start, end):
        self.type = type
        self.value = value
        self.source = source
        self.start = start
        self.end = end

    def __repr__(self):
        type_name = 'UNKNOWN'
        for attr in dir(self):
            if getattr(self, attr) == self.type:
                type_name = attr
                break
        return ('Token(Token.{0}, {1}, {2}, {3}, {4})'
                .format(type_name, repr(self.value), repr(self.source),
                        self.start, self.end))

    def matches(self, type, value):
        """
        Return True iff this token matches the given `type` and `value`.
        """
        return self.type == type and self.value == value

    def error(self, msg):
        """
        Return a `SyntaxError` object describing a problem with this
        token. The argument `msg` is the error message; the token's
        line number and position are also reported.
        """
        line_start = 1 + self.source.rfind('\n', 0, self.start)
        line_end = self.source.find('\n', self.end)
        if line_end == -1: line_end = len(self.source)
        e = SyntaxError(msg)
        e.lineno = 1 + self.source.count('\n', 0, self.start)
        e.text = self.source[line_start: line_end]
        e.offset = self.start - line_start + 1
        return e

Second, the lexical analyzer, using Python's iterator protocol.

class Tokenizer(object):
    """
    Tokenizer for a subset of HamlPy. Instances of this class support
    the iterator protocol, and yield tokens from the string `s` as
    Token object. When the string `s` runs out, yield an END token.

    >>> from pprint import pprint
    >>> pprint(list(Tokenizer('{"a":"b"}')))
    [Token(Token.DELIMITER, '{', '{"a":"b"}', 0, 1),
     Token(Token.STRING, 'a', '{"a":"b"}', 2, 3),
     Token(Token.DELIMITER, ':', '{"a":"b"}', 4, 5),
     Token(Token.STRING, 'b', '{"a":"b"}', 6, 7),
     Token(Token.DELIMITER, '}', '{"a":"b"}', 8, 9),
     Token(Token.END, '', '{"a":"b"}', 9, 9)]
    """
    def __init__(self, s):
        self.iter = self.tokenize(s)

    def __iter__(self):
        return self

    def next(self):
        return next(self.iter)

    # Regular expression matching a source token.
    token_re = re.compile(r'''
        \s*                                 # Ignore initial whitespace
        (?:([][{},:])                       # 1. Delimiter
          |'([^\\']*(?:\\.[^\\']*)*)'       # 2. Single-quoted string
          |"([^\\"]*(?:\\.[^\\"]*)*)"       # 3. Double-quoted string
          |(\S)                             # 4. Something else
        )''', re.X)

    # Regular expression matching a backslash and following character.
    backslash_re = re.compile(r'\\(.)')

    def tokenize(self, s):
        for m in self.token_re.finditer(s):
            if m.group(1):
                yield Token(Token.DELIMITER, m.group(1),
                            s, m.start(1), m.end(1))
            elif m.group(2):
                yield Token(Token.STRING,
                            self.backslash_re.sub(r'\1', m.group(2)),
                            s, m.start(2), m.end(2))
            elif m.group(3):
                yield Token(Token.STRING,
                            self.backslash_re.sub(r'\1', m.group(3)),
                            s, m.start(3), m.end(3))
            else:
                t = Token(Token.ERROR, m.group(4), s, m.start(4), m.end(4))
                raise t.error('Unexpected character')
        yield Token(Token.END, '', s, len(s), len(s))

And third, the recursive descent parser, with the formal grammar given in the docstring for the class. The parser needs one token of lookahead.

class Parser(object):
    """
    Parser for the subset of HamlPy with the following grammar:

    attribute-dict ::= '{' [attribute-list] '}'
    attribute-list ::= attribute (',' attribute)*
    attribute      ::= string ':' value
    value          ::= string | '[' [value-list] ']'
    value-list     ::= value (',' value)*
    """

    def __init__(self, s):
        self.tokenizer = Tokenizer(s)
        self.lookahead = None       # The lookahead token.
        self.next_token()           # Lookahead one token.

    def next_token(self):
        """
        Return the next token from the lexer and update the lookahead
        token.
        """
        t = self.lookahead
        self.lookahead = next(self.tokenizer)
        return t

    # Regular expression matching an allowable key.
    key_re = re.compile(r'[a-zA-Z_0-9-]+$')

    def parse_value(self):
        t = self.next_token()
        if t.type == Token.STRING:
            return t.value
        elif t.matches(Token.DELIMITER, '['):
            return list(self.parse_value_list())
        else:
            raise t.error('Expected a value')

    def parse_value_list(self):
        if self.lookahead.matches(Token.DELIMITER, ']'):
            self.next_token()
            return
        while True:
            yield self.parse_value()
            t = self.next_token()
            if t.matches(Token.DELIMITER, ']'):
                return
            elif not t.matches(Token.DELIMITER, ','):
                raise t.error('Expected "," or "]"')

    def parse_attribute(self):
        t = self.next_token()
        if t.type != Token.STRING:
            raise t.error('Expected a string')
        key = t.value
        if not self.key_re.match(key):
            raise t.error('Invalid key')
        t = self.next_token()
        if not t.matches(Token.DELIMITER, ':'):
            raise t.error('Expected ":"')
        value = self.parse_value()
        return key, value

    def parse_attribute_list(self):
        if self.lookahead.matches(Token.DELIMITER, '}'):
            self.next_token()
            return
        while True:
            yield self.parse_attribute()
            t = self.next_token()
            if t.matches(Token.DELIMITER, '}'):
                return
            elif not t.matches(Token.DELIMITER, ','):
                raise t.error('Expected "," or "}"')

    def parse_attribute_dict(self):
        t = self.next_token()
        if not t.matches(Token.DELIMITER, '{'):
            raise t.error('Expected "{"')
        return dict(self.parse_attribute_list())

You'll probably want to know how to handle Haml's significant whitespace. The way to do this is to modify the tokenizer to emit NEWLINE, INDENT and DEDENT tokens, and then modify next_token to take an include_newlines optional parameter, and discard or return these extra tokens as appropriate.