mercurial/filesetlang.py
author Gregory Szorc <gregory.szorc@gmail.com>
Mon, 08 Oct 2018 18:17:12 -0700
changeset 40176 41263df08109
parent 38879 e79a69af1593
child 43076 2372284d9457
permissions -rw-r--r--
wireprotov2: change how revisions are specified to changesetdata Right now, we have a handful of arguments for specifying the revisions whose data should be returned. Defining how all these arguments interact when various combinations are present is difficult. This commit establishes a new, generic mechanism for specifying revisions. Instead of a hodgepodge of arguments defining things, we have a list of dicts that specify revision selectors. The final set of revisions is a union of all these selectors. We implement support for specifying revisions based on: * An explicit list of changeset revisions * An explicit list of changeset revisions plus ancestry depth * A DAG range between changeset roots and heads If you squint hard enough, this problem has already been solved by revsets. But I'm reluctant to expose revsets to the wire protocol because that would require servers to implement a revset parser. Plus there are security and performance implications: the set of revision selectors needs to be narrowly and specifically tailored for what is appropriate to be executing on a server. Perhaps there would be a way for us to express the "parse tree" of a revset query, for example. I'm not sure. We can explore this space another time. For now, the new mechanism should bring sufficient flexibility while remaining relatively simple. The selector "types" are prefixed with "changeset" because I plan to add manifest and file-flavored selectors as well. This will enable us to e.g. select file revisions based on a range of changeset revisions. Differential Revision: https://phab.mercurial-scm.org/D4979
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
38805
b9162ea1b815 fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 38804
diff changeset
     1
# filesetlang.py - parser, tokenizer and utility for file set language
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     2
#
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     3
# Copyright 2010 Matt Mackall <mpm@selenic.com>
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     4
#
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     5
# This software may be used and distributed according to the terms of the
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     6
# GNU General Public License version 2 or any later version.
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
     7
25938
e194ada8d45f fileset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25815
diff changeset
     8
from __future__ import absolute_import
e194ada8d45f fileset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25815
diff changeset
     9
e194ada8d45f fileset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25815
diff changeset
    10
from .i18n import _
e194ada8d45f fileset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25815
diff changeset
    11
from . import (
e194ada8d45f fileset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25815
diff changeset
    12
    error,
e194ada8d45f fileset: use absolute_import
Gregory Szorc <gregory.szorc@gmail.com>
parents: 25815
diff changeset
    13
    parser,
32523
1fb0a85fb20e py3: use pycompat.bytestr so that we don't get ascii values
Pulkit Goyal <7895pulkit@gmail.com>
parents: 32291
diff changeset
    14
    pycompat,
37084
f0b6fbea00cf stringutil: bulk-replace call sites to point to new module
Yuya Nishihara <yuya@tcha.org>
parents: 36505
diff changeset
    15
)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    16
38863
61ab546b71c3 fileset: introduce weight constants for readability
Yuya Nishihara <yuya@tcha.org>
parents: 38832
diff changeset
    17
# common weight constants for static optimization
61ab546b71c3 fileset: introduce weight constants for readability
Yuya Nishihara <yuya@tcha.org>
parents: 38832
diff changeset
    18
# (see registrar.filesetpredicate for details)
61ab546b71c3 fileset: introduce weight constants for readability
Yuya Nishihara <yuya@tcha.org>
parents: 38832
diff changeset
    19
WEIGHT_CHECK_FILENAME = 0.5
61ab546b71c3 fileset: introduce weight constants for readability
Yuya Nishihara <yuya@tcha.org>
parents: 38832
diff changeset
    20
WEIGHT_READ_CONTENTS = 30
61ab546b71c3 fileset: introduce weight constants for readability
Yuya Nishihara <yuya@tcha.org>
parents: 38832
diff changeset
    21
WEIGHT_STATUS = 10
61ab546b71c3 fileset: introduce weight constants for readability
Yuya Nishihara <yuya@tcha.org>
parents: 38832
diff changeset
    22
WEIGHT_STATUS_THOROUGH = 50
61ab546b71c3 fileset: introduce weight constants for readability
Yuya Nishihara <yuya@tcha.org>
parents: 38832
diff changeset
    23
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    24
elements = {
25815
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    25
    # token-type: binding-strength, primary, prefix, infix, suffix
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    26
    "(": (20, None, ("group", 1, ")"), ("func", 1, ")"), None),
35741
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
    27
    ":": (15, None, None, ("kindpat", 15), None),
25815
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    28
    "-": (5, None, ("negate", 19), ("minus", 5), None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    29
    "not": (10, None, ("not", 10), None, None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    30
    "!": (10, None, ("not", 10), None, None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    31
    "and": (5, None, None, ("and", 5), None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    32
    "&": (5, None, None, ("and", 5), None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    33
    "or": (4, None, None, ("or", 4), None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    34
    "|": (4, None, None, ("or", 4), None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    35
    "+": (4, None, None, ("or", 4), None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    36
    ",": (2, None, None, ("list", 2), None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    37
    ")": (0, None, None, None, None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    38
    "symbol": (0, "symbol", None, None, None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    39
    "string": (0, "string", None, None, None),
e71e5629e006 parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents: 25801
diff changeset
    40
    "end": (0, None, None, None, None),
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    41
}
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    42
32291
bd872f64a8ba cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents: 32134
diff changeset
    43
keywords = {'and', 'or', 'not'}
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    44
38805
b9162ea1b815 fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 38804
diff changeset
    45
symbols = {}
b9162ea1b815 fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 38804
diff changeset
    46
19470
19ac0d8ee9a2 fileset: handle underbar in symbols
Matt Mackall <mpm@selenic.com>
parents: 19194
diff changeset
    47
globchars = ".*{}[]?/\\_"
14551
68d814a3cefd fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents: 14513
diff changeset
    48
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    49
def tokenize(program):
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    50
    pos, l = 0, len(program)
32523
1fb0a85fb20e py3: use pycompat.bytestr so that we don't get ascii values
Pulkit Goyal <7895pulkit@gmail.com>
parents: 32291
diff changeset
    51
    program = pycompat.bytestr(program)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    52
    while pos < l:
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    53
        c = program[pos]
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    54
        if c.isspace(): # skip inter-token whitespace
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    55
            pass
35741
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
    56
        elif c in "(),-:|&+!": # handle simple operators
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11284
diff changeset
    57
            yield (c, None, pos)
12408
78a97859b90d revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents: 12401
diff changeset
    58
        elif (c in '"\'' or c == 'r' and
78a97859b90d revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents: 12401
diff changeset
    59
              program[pos:pos + 2] in ("r'", 'r"')): # handle quoted strings
78a97859b90d revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents: 12401
diff changeset
    60
            if c == 'r':
78a97859b90d revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents: 12401
diff changeset
    61
                pos += 1
78a97859b90d revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents: 12401
diff changeset
    62
                c = program[pos]
78a97859b90d revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents: 12401
diff changeset
    63
                decode = lambda x: x
78a97859b90d revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents: 12401
diff changeset
    64
            else:
26233
d3dbb65c8dc6 fileset: handle error of string unescaping
Yuya Nishihara <yuya@tcha.org>
parents: 26195
diff changeset
    65
                decode = parser.unescapestr
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    66
            pos += 1
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    67
            s = pos
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    68
            while pos < l: # find closing quote
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    69
                d = program[pos]
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    70
                if d == '\\': # skip over escaped characters
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    71
                    pos += 2
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    72
                    continue
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    73
                if d == c:
12408
78a97859b90d revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents: 12401
diff changeset
    74
                    yield ('string', decode(program[s:pos]), s)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    75
                    break
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    76
                pos += 1
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    77
            else:
11383
de544774ebea revset: all your error messages are belong to _
Martin Geisler <mg@lazybytes.net>
parents: 11349
diff changeset
    78
                raise error.ParseError(_("unterminated string"), s)
14551
68d814a3cefd fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents: 14513
diff changeset
    79
        elif c.isalnum() or c in globchars or ord(c) > 127:
14513
85fe676c27e9 fileset: fix long line
Matt Mackall <mpm@selenic.com>
parents: 14511
diff changeset
    80
            # gather up a symbol/keyword
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    81
            s = pos
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    82
            pos += 1
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    83
            while pos < l: # find end of symbol
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    84
                d = program[pos]
14551
68d814a3cefd fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents: 14513
diff changeset
    85
                if not (d.isalnum() or d in globchars or ord(d) > 127):
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    86
                    break
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    87
                pos += 1
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    88
            sym = program[s:pos]
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    89
            if sym in keywords: # operator keywords
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11284
diff changeset
    90
                yield (sym, None, s)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    91
            else:
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11284
diff changeset
    92
                yield ('symbol', sym, s)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    93
            pos -= 1
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    94
        else:
11383
de544774ebea revset: all your error messages are belong to _
Martin Geisler <mg@lazybytes.net>
parents: 11349
diff changeset
    95
            raise error.ParseError(_("syntax error"), pos)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    96
        pos += 1
11289
4215ce511134 revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents: 11284
diff changeset
    97
    yield ('end', None, pos)
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
    98
20208
61a47fd64f30 fileset, revset: do not use global parser object for thread safety
Yuya Nishihara <yuya@tcha.org>
parents: 19470
diff changeset
    99
def parse(expr):
25654
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25633
diff changeset
   100
    p = parser.parser(elements)
af329a84310c parser: accept iterator of tokens instead of tokenizer function and program
Yuya Nishihara <yuya@tcha.org>
parents: 25633
diff changeset
   101
    tree, pos = p.parse(tokenize(expr))
25252
ac381dd7a21f fileset: move validation of incomplete parsing to parse() function
Yuya Nishihara <yuya@tcha.org>
parents: 24408
diff changeset
   102
    if pos != len(expr):
ac381dd7a21f fileset: move validation of incomplete parsing to parse() function
Yuya Nishihara <yuya@tcha.org>
parents: 24408
diff changeset
   103
        raise error.ParseError(_("invalid token"), pos)
38804
d82c4d42b615 fileset: flatten 'or' nodes to unnest unionmatchers
Yuya Nishihara <yuya@tcha.org>
parents: 38803
diff changeset
   104
    return parser.simplifyinfixops(tree, {'list', 'or'})
11275
c9ce8ecd6ca1 revset: introduce revset core
Matt Mackall <mpm@selenic.com>
parents:
diff changeset
   105
35691
735f47b41521 fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents: 35615
diff changeset
   106
def getsymbol(x):
735f47b41521 fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents: 35615
diff changeset
   107
    if x and x[0] == 'symbol':
735f47b41521 fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents: 35615
diff changeset
   108
        return x[1]
735f47b41521 fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents: 35615
diff changeset
   109
    raise error.ParseError(_('not a symbol'))
735f47b41521 fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents: 35615
diff changeset
   110
14551
68d814a3cefd fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents: 14513
diff changeset
   111
def getstring(x, err):
68d814a3cefd fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents: 14513
diff changeset
   112
    if x and (x[0] == 'string' or x[0] == 'symbol'):
68d814a3cefd fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents: 14513
diff changeset
   113
        return x[1]
68d814a3cefd fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents: 14513
diff changeset
   114
    raise error.ParseError(err)
68d814a3cefd fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents: 14513
diff changeset
   115
38805
b9162ea1b815 fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 38804
diff changeset
   116
def getkindpat(x, y, allkinds, err):
35741
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   117
    kind = getsymbol(x)
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   118
    pat = getstring(y, err)
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   119
    if kind not in allkinds:
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   120
        raise error.ParseError(_("invalid pattern kind: %s") % kind)
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   121
    return '%s:%s' % (kind, pat)
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   122
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   123
def getpattern(x, allkinds, err):
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   124
    if x and x[0] == 'kindpat':
38805
b9162ea1b815 fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents: 38804
diff changeset
   125
        return getkindpat(x[1], x[2], allkinds, err)
35741
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   126
    return getstring(x, err)
73432eee0ac4 fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents: 35739
diff changeset
   127
38598
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   128
def getlist(x):
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   129
    if not x:
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   130
        return []
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   131
    if x[0] == 'list':
38803
4dc498d61d86 fileset: flatten arguments list
Yuya Nishihara <yuya@tcha.org>
parents: 38772
diff changeset
   132
        return list(x[1:])
38598
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   133
    return [x]
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   134
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   135
def getargs(x, min, max, err):
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   136
    l = getlist(x)
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   137
    if len(l) < min or len(l) > max:
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   138
        raise error.ParseError(err)
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   139
    return l
d046bf37f1ba fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents: 38414
diff changeset
   140
38826
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   141
def _analyze(x):
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   142
    if x is None:
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   143
        return x
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   144
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   145
    op = x[0]
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   146
    if op in {'string', 'symbol'}:
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   147
        return x
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   148
    if op == 'kindpat':
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   149
        getsymbol(x[1])  # kind must be a symbol
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   150
        t = _analyze(x[2])
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   151
        return (op, x[1], t)
38827
48fc2a8af345 fileset: drop 'group' node from tree to be evaluated
Yuya Nishihara <yuya@tcha.org>
parents: 38826
diff changeset
   152
    if op == 'group':
48fc2a8af345 fileset: drop 'group' node from tree to be evaluated
Yuya Nishihara <yuya@tcha.org>
parents: 38826
diff changeset
   153
        return _analyze(x[1])
38828
3ea6ce609747 fileset: reject 'negate' node early while transforming parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38827
diff changeset
   154
    if op == 'negate':
3ea6ce609747 fileset: reject 'negate' node early while transforming parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38827
diff changeset
   155
        raise error.ParseError(_("can't use negate operator in this context"))
3ea6ce609747 fileset: reject 'negate' node early while transforming parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38827
diff changeset
   156
    if op == 'not':
38826
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   157
        t = _analyze(x[1])
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   158
        return (op, t)
38832
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   159
    if op == 'and':
38826
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   160
        ta = _analyze(x[1])
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   161
        tb = _analyze(x[2])
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   162
        return (op, ta, tb)
38832
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   163
    if op == 'minus':
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   164
        return _analyze(('and', x[1], ('not', x[2])))
38826
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   165
    if op in {'list', 'or'}:
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   166
        ts = tuple(_analyze(y) for y in x[1:])
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   167
        return (op,) + ts
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   168
    if op == 'func':
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   169
        getsymbol(x[1])  # function name must be a symbol
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   170
        ta = _analyze(x[2])
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   171
        return (op, x[1], ta)
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   172
    raise error.ProgrammingError('invalid operator %r' % op)
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   173
38879
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   174
def _insertstatushints(x):
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   175
    """Insert hint nodes where status should be calculated (first path)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   176
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   177
    This works in bottom-up way, summing up status names and inserting hint
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   178
    nodes at 'and' and 'or' as needed. Thus redundant hint nodes may be left.
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   179
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   180
    Returns (status-names, new-tree) at the given subtree, where status-names
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   181
    is a sum of status names referenced in the given subtree.
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   182
    """
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   183
    if x is None:
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   184
        return (), x
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   185
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   186
    op = x[0]
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   187
    if op in {'string', 'symbol', 'kindpat'}:
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   188
        return (), x
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   189
    if op == 'not':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   190
        h, t = _insertstatushints(x[1])
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   191
        return h, (op, t)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   192
    if op == 'and':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   193
        ha, ta = _insertstatushints(x[1])
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   194
        hb, tb = _insertstatushints(x[2])
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   195
        hr = ha + hb
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   196
        if ha and hb:
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   197
            return hr, ('withstatus', (op, ta, tb), ('string', ' '.join(hr)))
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   198
        return hr, (op, ta, tb)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   199
    if op == 'or':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   200
        hs, ts = zip(*(_insertstatushints(y) for y in x[1:]))
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   201
        hr = sum(hs, ())
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   202
        if sum(bool(h) for h in hs) > 1:
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   203
            return hr, ('withstatus', (op,) + ts, ('string', ' '.join(hr)))
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   204
        return hr, (op,) + ts
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   205
    if op == 'list':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   206
        hs, ts = zip(*(_insertstatushints(y) for y in x[1:]))
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   207
        return sum(hs, ()), (op,) + ts
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   208
    if op == 'func':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   209
        f = getsymbol(x[1])
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   210
        # don't propagate 'ha' crossing a function boundary
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   211
        ha, ta = _insertstatushints(x[2])
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   212
        if getattr(symbols.get(f), '_callstatus', False):
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   213
            return (f,), ('withstatus', (op, x[1], ta), ('string', f))
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   214
        return (), (op, x[1], ta)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   215
    raise error.ProgrammingError('invalid operator %r' % op)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   216
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   217
def _mergestatushints(x, instatus):
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   218
    """Remove redundant status hint nodes (second path)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   219
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   220
    This is the top-down path to eliminate inner hint nodes.
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   221
    """
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   222
    if x is None:
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   223
        return x
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   224
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   225
    op = x[0]
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   226
    if op == 'withstatus':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   227
        if instatus:
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   228
            # drop redundant hint node
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   229
            return _mergestatushints(x[1], instatus)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   230
        t = _mergestatushints(x[1], instatus=True)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   231
        return (op, t, x[2])
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   232
    if op in {'string', 'symbol', 'kindpat'}:
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   233
        return x
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   234
    if op == 'not':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   235
        t = _mergestatushints(x[1], instatus)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   236
        return (op, t)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   237
    if op == 'and':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   238
        ta = _mergestatushints(x[1], instatus)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   239
        tb = _mergestatushints(x[2], instatus)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   240
        return (op, ta, tb)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   241
    if op in {'list', 'or'}:
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   242
        ts = tuple(_mergestatushints(y, instatus) for y in x[1:])
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   243
        return (op,) + ts
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   244
    if op == 'func':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   245
        # don't propagate 'instatus' crossing a function boundary
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   246
        ta = _mergestatushints(x[2], instatus=False)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   247
        return (op, x[1], ta)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   248
    raise error.ProgrammingError('invalid operator %r' % op)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   249
38826
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   250
def analyze(x):
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   251
    """Transform raw parsed tree to evaluatable tree which can be fed to
38829
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   252
    optimize() or getmatch()
38826
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   253
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   254
    All pseudo operations should be mapped to real operations or functions
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   255
    defined in methods or symbols table respectively.
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   256
    """
38879
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   257
    t = _analyze(x)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   258
    _h, t = _insertstatushints(t)
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   259
    return _mergestatushints(t, instatus=False)
38826
6371ab78c3b3 fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents: 38805
diff changeset
   260
38832
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   261
def _optimizeandops(op, ta, tb):
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   262
    if tb is not None and tb[0] == 'not':
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   263
        return ('minus', ta, tb[1])
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   264
    return (op, ta, tb)
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   265
38865
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   266
def _optimizeunion(xs):
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   267
    # collect string patterns so they can be compiled into a single regexp
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   268
    ws, ts, ss = [], [], []
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   269
    for x in xs:
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   270
        w, t = _optimize(x)
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   271
        if t is not None and t[0] in {'string', 'symbol', 'kindpat'}:
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   272
            ss.append(t)
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   273
            continue
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   274
        ws.append(w)
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   275
        ts.append(t)
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   276
    if ss:
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   277
        ws.append(WEIGHT_CHECK_FILENAME)
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   278
        ts.append(('patterns',) + tuple(ss))
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   279
    return ws, ts
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   280
38829
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   281
def _optimize(x):
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   282
    if x is None:
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   283
        return 0, x
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   284
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   285
    op = x[0]
38879
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   286
    if op == 'withstatus':
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   287
        w, t = _optimize(x[1])
e79a69af1593 fileset: insert hints where status should be computed
Yuya Nishihara <yuya@tcha.org>
parents: 38865
diff changeset
   288
        return w, (op, t, x[2])
38829
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   289
    if op in {'string', 'symbol'}:
38863
61ab546b71c3 fileset: introduce weight constants for readability
Yuya Nishihara <yuya@tcha.org>
parents: 38832
diff changeset
   290
        return WEIGHT_CHECK_FILENAME, x
38829
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   291
    if op == 'kindpat':
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   292
        w, t = _optimize(x[2])
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   293
        return w, (op, x[1], t)
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   294
    if op == 'not':
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   295
        w, t = _optimize(x[1])
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   296
        return w, (op, t)
38831
b975c5801487 fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents: 38829
diff changeset
   297
    if op == 'and':
b975c5801487 fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents: 38829
diff changeset
   298
        wa, ta = _optimize(x[1])
b975c5801487 fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents: 38829
diff changeset
   299
        wb, tb = _optimize(x[2])
b975c5801487 fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents: 38829
diff changeset
   300
        if wa <= wb:
38832
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   301
            return wa, _optimizeandops(op, ta, tb)
38831
b975c5801487 fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents: 38829
diff changeset
   302
        else:
38832
ca4de8ba5b5f fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents: 38831
diff changeset
   303
            return wb, _optimizeandops(op, tb, ta)
38829
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   304
    if op == 'or':
38865
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   305
        ws, ts = _optimizeunion(x[1:])
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   306
        if len(ts) == 1:
899b4c74209c fileset: combine union of basic patterns into single matcher
Yuya Nishihara <yuya@tcha.org>
parents: 38864
diff changeset
   307
            return ws[0], ts[0] # 'or' operation is fully optimized out
38864
73731fa8d1bd fileset: reorder 'or' expression by weight
Yuya Nishihara <yuya@tcha.org>
parents: 38863
diff changeset
   308
        ts = tuple(it[1] for it in sorted(enumerate(ts),
73731fa8d1bd fileset: reorder 'or' expression by weight
Yuya Nishihara <yuya@tcha.org>
parents: 38863
diff changeset
   309
                                          key=lambda it: ws[it[0]]))
38829
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   310
        return max(ws), (op,) + ts
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   311
    if op == 'list':
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   312
        ws, ts = zip(*(_optimize(y) for y in x[1:]))
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   313
        return sum(ws), (op,) + ts
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   314
    if op == 'func':
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   315
        f = getsymbol(x[1])
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   316
        w = getattr(symbols.get(f), '_weight', 1)
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   317
        wa, ta = _optimize(x[2])
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   318
        return w + wa, (op, x[1], ta)
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   319
    raise error.ProgrammingError('invalid operator %r' % op)
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   320
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   321
def optimize(x):
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   322
    """Reorder/rewrite evaluatable tree for optimization
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   323
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   324
    All pseudo operations should be transformed beforehand.
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   325
    """
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   326
    _w, t = _optimize(x)
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   327
    return t
7e7e2b2ff284 fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents: 38828
diff changeset
   328
25255
ad1d2c952889 fileset: pretty print syntax tree in debug output
Yuya Nishihara <yuya@tcha.org>
parents: 25252
diff changeset
   329
def prettyformat(tree):
ad1d2c952889 fileset: pretty print syntax tree in debug output
Yuya Nishihara <yuya@tcha.org>
parents: 25252
diff changeset
   330
    return parser.prettyformat(tree, ('string', 'symbol'))