mercurial/parser.py
author Augie Fackler <durin42@gmail.com>
Sun, 10 Oct 2010 12:03:28 -0500
changeset 12713 bd37e7492478
parent 11449 05af334bac05
child 13176 895f54a79c6e
permissions -rw-r--r--
hgweb help: fix double help links
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     1
# parser.py - simple top-down operator precedence parser for mercurial
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     2
#
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     3
# Copyright 2010 Matt Mackall <mpm@selenic.com>
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     4
#
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     5
# This software may be used and distributed according to the terms of the
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     6
# GNU General Public License version 2 or any later version.
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     7
11449
05af334bac05 parser: fix URL to effbot
Julian Cowley <julian@lava.net>
parents: 11412
diff changeset
     8
# see http://effbot.org/zone/simple-top-down-parsing.htm and
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     9
# http://eli.thegreenplace.net/2010/01/02/top-down-operator-precedence-parsing/
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    10
# for background
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    11
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    12
# takes a tokenizer and elements
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    13
# tokenizer is an iterator that returns type, value pairs
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    14
# elements is a mapping of types to binding strength, prefix and infix actions
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    15
# an action is a tree node name, a tree label, and an optional match
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    16
# __call__(program) parses program into a labelled tree
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    17
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
    18
import error
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
    19
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    20
class parser(object):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    21
    def __init__(self, tokenizer, elements, methods=None):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    22
        self._tokenizer = tokenizer
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    23
        self._elements = elements
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    24
        self._methods = methods
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    25
    def _advance(self):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    26
        'advance the tokenizer'
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    27
        t = self.current
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    28
        try:
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    29
            self.current = self._iter.next()
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    30
        except StopIteration:
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    31
            pass
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    32
        return t
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
    33
    def _match(self, m, pos):
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    34
        'make sure the tokenizer matches an end condition'
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    35
        if self.current[0] != m:
11305
d4cafcb63f77 cleanups: undefined variables
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 11289
diff changeset
    36
            raise error.ParseError("unexpected token: %s" % self.current[0],
d4cafcb63f77 cleanups: undefined variables
Dirkjan Ochtman <dirkjan@ochtman.nl>
parents: 11289
diff changeset
    37
                                   self.current[2])
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    38
        self._advance()
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    39
    def _parse(self, bind=0):
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
    40
        token, value, pos = self._advance()
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    41
        # handle prefix rules on current token
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    42
        prefix = self._elements[token][1]
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    43
        if not prefix:
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
    44
            raise error.ParseError("not a prefix: %s" % token, pos)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    45
        if len(prefix) == 1:
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    46
            expr = (prefix[0], value)
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    47
        else:
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    48
            if len(prefix) > 2 and prefix[2] == self.current[0]:
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
    49
                self._match(prefix[2], pos)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    50
                expr = (prefix[0], None)
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    51
            else:
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    52
                expr = (prefix[0], self._parse(prefix[1]))
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    53
                if len(prefix) > 2:
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
    54
                    self._match(prefix[2], pos)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    55
        # gather tokens until we meet a lower binding strength
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    56
        while bind < self._elements[self.current[0]][0]:
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11278
diff changeset
    57
            token, value, pos = self._advance()
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    58
            e = self._elements[token]
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    59
            # check for suffix - next token isn't a valid prefix
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    60
            if len(e) == 4 and not self._elements[self.current[0]][1]:
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    61
                suffix = e[3]
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    62
                expr = (suffix[0], expr)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    63
            else:
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    64
                # handle infix rules
11412
51ceb1571805 parser: improve infix error checking
Matt Mackall <mpm@selenic.com>
parents: 11319
diff changeset
    65
                if len(e) < 3 or not e[2]:
51ceb1571805 parser: improve infix error checking
Matt Mackall <mpm@selenic.com>
parents: 11319
diff changeset
    66
                    raise error.ParseError("not an infix: %s" % token, pos)
51ceb1571805 parser: improve infix error checking
Matt Mackall <mpm@selenic.com>
parents: 11319
diff changeset
    67
                infix = e[2]
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    68
                if len(infix) == 3 and infix[2] == self.current[0]:
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
    69
                    self._match(infix[2], pos)
11278
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    70
                    expr = (infix[0], expr, (None))
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    71
                else:
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    72
                    expr = (infix[0], expr, self._parse(infix[1]))
7df88cdf47fd revset: add support for prefix and suffix versions of : and ::
Matt Mackall <mpm@selenic.com>
parents: 11274
diff changeset
    73
                    if len(infix) == 3:
11319
9d1cf337a78d parser: fix missing param in _match
Peter Arrenbrecht <peter.arrenbrecht@gmail.com>
parents: 11305
diff changeset
    74
                        self._match(infix[2], pos)
11274
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    75
        return expr
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    76
    def parse(self, message):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    77
        'generate a parse tree from a message'
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    78
        self._iter = self._tokenizer(message)
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    79
        self.current = self._iter.next()
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    80
        return self._parse()
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    81
    def eval(self, tree):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    82
        'recursively evaluate a parse tree using node methods'
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    83
        if not isinstance(tree, tuple):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    84
            return tree
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    85
        return self._methods[tree[0]](*[self.eval(t) for t in tree[1:]])
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    86
    def __call__(self, message):
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    87
        'parse a message into a parse tree and evaluate if methods given'
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    88
        t = self.parse(message)
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    89
        if self._methods:
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    90
            return self.eval(t)
77272d28b53f revset: introduce basic parser
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    91
        return t