Mercurial > public > mercurial-scm > hg-stable
annotate mercurial/filesetlang.py @ 38872:ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
'x - y' is first rewritten to 'x and not y' so that x and y are reordered
by weight.
| author | Yuya Nishihara <yuya@tcha.org> |
|---|---|
| date | Sat, 21 Jul 2018 16:49:01 +0900 |
| parents | b975c5801487 |
| children | 61ab546b71c3 |
| rev | line source |
|---|---|
|
38845
b9162ea1b815
fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
38844
diff
changeset
|
1 # filesetlang.py - parser, tokenizer and utility for file set language |
| 11275 | 2 # |
| 3 # Copyright 2010 Matt Mackall <mpm@selenic.com> | |
| 4 # | |
| 5 # This software may be used and distributed according to the terms of the | |
| 6 # GNU General Public License version 2 or any later version. | |
| 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, |
|
32556
1fb0a85fb20e
py3: use pycompat.bytestr so that we don't get ascii values
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32331
diff
changeset
|
14 pycompat, |
|
37087
f0b6fbea00cf
stringutil: bulk-replace call sites to point to new module
Yuya Nishihara <yuya@tcha.org>
parents:
36535
diff
changeset
|
15 ) |
| 11275 | 16 |
| 17 elements = { | |
|
25815
e71e5629e006
parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents:
25801
diff
changeset
|
18 # 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
|
19 "(": (20, None, ("group", 1, ")"), ("func", 1, ")"), None), |
|
35741
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
20 ":": (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
|
21 "-": (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
|
22 "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
|
23 "!": (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
|
24 "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
|
25 "&": (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
|
26 "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
|
27 "|": (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
|
28 "+": (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
|
29 ",": (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
|
30 ")": (0, None, None, None, None), |
|
e71e5629e006
parser: separate actions for primary expression and prefix operator
Yuya Nishihara <yuya@tcha.org>
parents:
25801
diff
changeset
|
31 "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
|
32 "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
|
33 "end": (0, None, None, None, None), |
| 11275 | 34 } |
| 35 | |
|
32331
bd872f64a8ba
cleanup: use set literals
Martin von Zweigbergk <martinvonz@google.com>
parents:
32187
diff
changeset
|
36 keywords = {'and', 'or', 'not'} |
| 11275 | 37 |
|
38845
b9162ea1b815
fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
38844
diff
changeset
|
38 symbols = {} |
|
b9162ea1b815
fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
38844
diff
changeset
|
39 |
|
19470
19ac0d8ee9a2
fileset: handle underbar in symbols
Matt Mackall <mpm@selenic.com>
parents:
19194
diff
changeset
|
40 globchars = ".*{}[]?/\\_" |
|
14551
68d814a3cefd
fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents:
14513
diff
changeset
|
41 |
| 11275 | 42 def tokenize(program): |
| 43 pos, l = 0, len(program) | |
|
32556
1fb0a85fb20e
py3: use pycompat.bytestr so that we don't get ascii values
Pulkit Goyal <7895pulkit@gmail.com>
parents:
32331
diff
changeset
|
44 program = pycompat.bytestr(program) |
| 11275 | 45 while pos < l: |
| 46 c = program[pos] | |
| 47 if c.isspace(): # skip inter-token whitespace | |
| 48 pass | |
|
35741
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
49 elif c in "(),-:|&+!": # handle simple operators |
|
11289
4215ce511134
revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents:
11284
diff
changeset
|
50 yield (c, None, pos) |
|
12408
78a97859b90d
revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents:
12401
diff
changeset
|
51 elif (c in '"\'' or c == 'r' and |
|
78a97859b90d
revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents:
12401
diff
changeset
|
52 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
|
53 if c == 'r': |
|
78a97859b90d
revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents:
12401
diff
changeset
|
54 pos += 1 |
|
78a97859b90d
revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents:
12401
diff
changeset
|
55 c = program[pos] |
|
78a97859b90d
revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents:
12401
diff
changeset
|
56 decode = lambda x: x |
|
78a97859b90d
revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents:
12401
diff
changeset
|
57 else: |
|
26233
d3dbb65c8dc6
fileset: handle error of string unescaping
Yuya Nishihara <yuya@tcha.org>
parents:
26195
diff
changeset
|
58 decode = parser.unescapestr |
| 11275 | 59 pos += 1 |
| 60 s = pos | |
| 61 while pos < l: # find closing quote | |
| 62 d = program[pos] | |
| 63 if d == '\\': # skip over escaped characters | |
| 64 pos += 2 | |
| 65 continue | |
| 66 if d == c: | |
|
12408
78a97859b90d
revset: support raw string literals
Brodie Rao <brodie@bitheap.org>
parents:
12401
diff
changeset
|
67 yield ('string', decode(program[s:pos]), s) |
| 11275 | 68 break |
| 69 pos += 1 | |
| 70 else: | |
|
11383
de544774ebea
revset: all your error messages are belong to _
Martin Geisler <mg@lazybytes.net>
parents:
11349
diff
changeset
|
71 raise error.ParseError(_("unterminated string"), s) |
|
14551
68d814a3cefd
fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents:
14513
diff
changeset
|
72 elif c.isalnum() or c in globchars or ord(c) > 127: |
| 14513 | 73 # gather up a symbol/keyword |
| 11275 | 74 s = pos |
| 75 pos += 1 | |
| 76 while pos < l: # find end of symbol | |
| 77 d = program[pos] | |
|
14551
68d814a3cefd
fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents:
14513
diff
changeset
|
78 if not (d.isalnum() or d in globchars or ord(d) > 127): |
| 11275 | 79 break |
| 80 pos += 1 | |
| 81 sym = program[s:pos] | |
| 82 if sym in keywords: # operator keywords | |
|
11289
4215ce511134
revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents:
11284
diff
changeset
|
83 yield (sym, None, s) |
| 11275 | 84 else: |
|
11289
4215ce511134
revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents:
11284
diff
changeset
|
85 yield ('symbol', sym, s) |
| 11275 | 86 pos -= 1 |
| 87 else: | |
|
11383
de544774ebea
revset: all your error messages are belong to _
Martin Geisler <mg@lazybytes.net>
parents:
11349
diff
changeset
|
88 raise error.ParseError(_("syntax error"), pos) |
| 11275 | 89 pos += 1 |
|
11289
4215ce511134
revset: raise ParseError exceptions
Matt Mackall <mpm@selenic.com>
parents:
11284
diff
changeset
|
90 yield ('end', None, pos) |
| 11275 | 91 |
|
20208
61a47fd64f30
fileset, revset: do not use global parser object for thread safety
Yuya Nishihara <yuya@tcha.org>
parents:
19470
diff
changeset
|
92 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
|
93 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
|
94 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
|
95 if pos != len(expr): |
|
ac381dd7a21f
fileset: move validation of incomplete parsing to parse() function
Yuya Nishihara <yuya@tcha.org>
parents:
24408
diff
changeset
|
96 raise error.ParseError(_("invalid token"), pos) |
|
38844
d82c4d42b615
fileset: flatten 'or' nodes to unnest unionmatchers
Yuya Nishihara <yuya@tcha.org>
parents:
38843
diff
changeset
|
97 return parser.simplifyinfixops(tree, {'list', 'or'}) |
| 11275 | 98 |
|
35691
735f47b41521
fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents:
35615
diff
changeset
|
99 def getsymbol(x): |
|
735f47b41521
fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents:
35615
diff
changeset
|
100 if x and x[0] == 'symbol': |
|
735f47b41521
fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents:
35615
diff
changeset
|
101 return x[1] |
|
735f47b41521
fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents:
35615
diff
changeset
|
102 raise error.ParseError(_('not a symbol')) |
|
735f47b41521
fileset: make it robust for bad function calls
Yuya Nishihara <yuya@tcha.org>
parents:
35615
diff
changeset
|
103 |
|
14551
68d814a3cefd
fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents:
14513
diff
changeset
|
104 def getstring(x, err): |
|
68d814a3cefd
fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents:
14513
diff
changeset
|
105 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
|
106 return x[1] |
|
68d814a3cefd
fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents:
14513
diff
changeset
|
107 raise error.ParseError(err) |
|
68d814a3cefd
fileset: basic pattern and boolean support
Matt Mackall <mpm@selenic.com>
parents:
14513
diff
changeset
|
108 |
|
38845
b9162ea1b815
fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
38844
diff
changeset
|
109 def getkindpat(x, y, allkinds, err): |
|
35741
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
110 kind = getsymbol(x) |
|
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
111 pat = getstring(y, err) |
|
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
112 if kind not in allkinds: |
|
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
113 raise error.ParseError(_("invalid pattern kind: %s") % kind) |
|
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
114 return '%s:%s' % (kind, pat) |
|
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
115 |
|
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
116 def getpattern(x, allkinds, err): |
|
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
117 if x and x[0] == 'kindpat': |
|
38845
b9162ea1b815
fileset: extract language processing part to new module (API)
Yuya Nishihara <yuya@tcha.org>
parents:
38844
diff
changeset
|
118 return getkindpat(x[1], x[2], allkinds, err) |
|
35741
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
119 return getstring(x, err) |
|
73432eee0ac4
fileset: add kind:pat operator
Yuya Nishihara <yuya@tcha.org>
parents:
35739
diff
changeset
|
120 |
|
38599
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
121 def getlist(x): |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
122 if not x: |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
123 return [] |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
124 if x[0] == 'list': |
|
38843
4dc498d61d86
fileset: flatten arguments list
Yuya Nishihara <yuya@tcha.org>
parents:
38813
diff
changeset
|
125 return list(x[1:]) |
|
38599
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
126 return [x] |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
127 |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
128 def getargs(x, min, max, err): |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
129 l = getlist(x) |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
130 if len(l) < min or len(l) > max: |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
131 raise error.ParseError(err) |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
132 return l |
|
d046bf37f1ba
fileset: move helper functions to top
Yuya Nishihara <yuya@tcha.org>
parents:
38420
diff
changeset
|
133 |
|
38866
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
134 def _analyze(x): |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
135 if x is None: |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
136 return x |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
137 |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
138 op = x[0] |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
139 if op in {'string', 'symbol'}: |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
140 return x |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
141 if op == 'kindpat': |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
142 getsymbol(x[1]) # kind must be a symbol |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
143 t = _analyze(x[2]) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
144 return (op, x[1], t) |
|
38867
48fc2a8af345
fileset: drop 'group' node from tree to be evaluated
Yuya Nishihara <yuya@tcha.org>
parents:
38866
diff
changeset
|
145 if op == 'group': |
|
48fc2a8af345
fileset: drop 'group' node from tree to be evaluated
Yuya Nishihara <yuya@tcha.org>
parents:
38866
diff
changeset
|
146 return _analyze(x[1]) |
|
38868
3ea6ce609747
fileset: reject 'negate' node early while transforming parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38867
diff
changeset
|
147 if op == 'negate': |
|
3ea6ce609747
fileset: reject 'negate' node early while transforming parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38867
diff
changeset
|
148 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:
38867
diff
changeset
|
149 if op == 'not': |
|
38866
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
150 t = _analyze(x[1]) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
151 return (op, t) |
|
38872
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
152 if op == 'and': |
|
38866
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
153 ta = _analyze(x[1]) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
154 tb = _analyze(x[2]) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
155 return (op, ta, tb) |
|
38872
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
156 if op == 'minus': |
|
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
157 return _analyze(('and', x[1], ('not', x[2]))) |
|
38866
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
158 if op in {'list', 'or'}: |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
159 ts = tuple(_analyze(y) for y in x[1:]) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
160 return (op,) + ts |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
161 if op == 'func': |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
162 getsymbol(x[1]) # function name must be a symbol |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
163 ta = _analyze(x[2]) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
164 return (op, x[1], ta) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
165 raise error.ProgrammingError('invalid operator %r' % op) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
166 |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
167 def analyze(x): |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
168 """Transform raw parsed tree to evaluatable tree which can be fed to |
|
38869
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
169 optimize() or getmatch() |
|
38866
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
170 |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
171 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:
38845
diff
changeset
|
172 defined in methods or symbols table respectively. |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
173 """ |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
174 return _analyze(x) |
|
6371ab78c3b3
fileset: add phase to transform parsed tree
Yuya Nishihara <yuya@tcha.org>
parents:
38845
diff
changeset
|
175 |
|
38872
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
176 def _optimizeandops(op, ta, tb): |
|
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
177 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:
38871
diff
changeset
|
178 return ('minus', ta, tb[1]) |
|
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
179 return (op, ta, tb) |
|
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
180 |
|
38869
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
181 def _optimize(x): |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
182 if x is None: |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
183 return 0, x |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
184 |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
185 op = x[0] |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
186 if op in {'string', 'symbol'}: |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
187 return 0.5, x |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
188 if op == 'kindpat': |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
189 w, t = _optimize(x[2]) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
190 return w, (op, x[1], t) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
191 if op == 'not': |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
192 w, t = _optimize(x[1]) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
193 return w, (op, t) |
|
38871
b975c5801487
fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents:
38869
diff
changeset
|
194 if op == 'and': |
|
b975c5801487
fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents:
38869
diff
changeset
|
195 wa, ta = _optimize(x[1]) |
|
b975c5801487
fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents:
38869
diff
changeset
|
196 wb, tb = _optimize(x[2]) |
|
b975c5801487
fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents:
38869
diff
changeset
|
197 if wa <= wb: |
|
38872
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
198 return wa, _optimizeandops(op, ta, tb) |
|
38871
b975c5801487
fileset: reorder 'and' expression to evaluate basic patterns first
Yuya Nishihara <yuya@tcha.org>
parents:
38869
diff
changeset
|
199 else: |
|
38872
ca4de8ba5b5f
fileset: optimize 'x and not y' to 'x - y'
Yuya Nishihara <yuya@tcha.org>
parents:
38871
diff
changeset
|
200 return wb, _optimizeandops(op, tb, ta) |
|
38869
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
201 if op == 'or': |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
202 ws, ts = zip(*(_optimize(y) for y in x[1:])) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
203 return max(ws), (op,) + ts |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
204 if op == 'list': |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
205 ws, ts = zip(*(_optimize(y) for y in x[1:])) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
206 return sum(ws), (op,) + ts |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
207 if op == 'func': |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
208 f = getsymbol(x[1]) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
209 w = getattr(symbols.get(f), '_weight', 1) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
210 wa, ta = _optimize(x[2]) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
211 return w + wa, (op, x[1], ta) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
212 raise error.ProgrammingError('invalid operator %r' % op) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
213 |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
214 def optimize(x): |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
215 """Reorder/rewrite evaluatable tree for optimization |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
216 |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
217 All pseudo operations should be transformed beforehand. |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
218 """ |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
219 _w, t = _optimize(x) |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
220 return t |
|
7e7e2b2ff284
fileset: add stub for weight-based optimization
Yuya Nishihara <yuya@tcha.org>
parents:
38868
diff
changeset
|
221 |
|
25255
ad1d2c952889
fileset: pretty print syntax tree in debug output
Yuya Nishihara <yuya@tcha.org>
parents:
25252
diff
changeset
|
222 def prettyformat(tree): |
|
ad1d2c952889
fileset: pretty print syntax tree in debug output
Yuya Nishihara <yuya@tcha.org>
parents:
25252
diff
changeset
|
223 return parser.prettyformat(tree, ('string', 'symbol')) |