Mercurial > public > mercurial-scm > hg

comparison mercurial/revset.py @ 25309:b333ca94403d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
revset: reduce nesting of chained 'or' operations (issue4624) This reduces the stack depth of chained 'or' operations: - from O(n) to O(1) at the parsing, alias expansion and optimization phases - from O(n) to O(log(n)) at the evaluation phase simplifyinfixops() must be applied immediately after the parsing phase. Otherwise, alias expansion would crash by "maximum recursion depth exceeded" error. Test cases use 'x:y|y:z' instead of 'x|y' because I'm planning to optimize 'x|y' in a different way. Benchmarks: 0) 605b1d32c1c0 1) this patch revset #0: 0 + 1 + 2 + ... + 200 0) wall 0.026347 comb 0.030000 user 0.030000 sys 0.000000 (best of 101) 1) wall 0.023858 comb 0.030000 user 0.030000 sys 0.000000 (best of 112) revset #1: 0 + 1 + 2 + ... + 1000 0) maximum recursion depth exceeded 1) wall 0.483341 comb 0.480000 user 0.480000 sys 0.000000 (best of 20) revset #2: sort(0 + 1 + 2 + ... + 200) 0) wall 0.013404 comb 0.010000 user 0.010000 sys 0.000000 (best of 196) 1) wall 0.006814 comb 0.010000 user 0.010000 sys 0.000000 (best of 375) revset #3: sort(0 + 1 + 2 + ... + 1000) 0) maximum recursion depth exceeded 1) wall 0.035240 comb 0.040000 user 0.040000 sys 0.000000 (best of 100)
author Yuya Nishihara <yuya@tcha.org>
date Sun, 26 Apr 2015 18:13:48 +0900
parents 036c26b08b71
children 9d6cc87bd507
comparison
equal deleted inserted replaced
25308:036c26b08b71 25309:b333ca94403d
354 return xs & subset 354 return xs & subset
355 355
356 def andset(repo, subset, x, y): 356 def andset(repo, subset, x, y):
357 return getset(repo, getset(repo, subset, x), y) 357 return getset(repo, getset(repo, subset, x), y)
358 358
359 def orset(repo, subset, x, y): 359 def orset(repo, subset, *xs):
360 xl = getset(repo, subset, x) 360 rs = [getset(repo, subset, x) for x in xs]
361 yl = getset(repo, subset, y) 361 return _combinesets(rs)
362 return xl + yl
363 362
364 def notset(repo, subset, x): 363 def notset(repo, subset, x):
365 return subset - getset(repo, subset, x) 364 return subset - getset(repo, subset, x)
366 365
367 def listset(repo, subset, a, b): 366 def listset(repo, subset, a, b):
2158 2157
2159 if wa > wb: 2158 if wa > wb:
2160 return w, (op, tb, ta) 2159 return w, (op, tb, ta)
2161 return w, (op, ta, tb) 2160 return w, (op, ta, tb)
2162 elif op == 'or': 2161 elif op == 'or':
2163 wa, ta = optimize(x[1], False) 2162 ws, ts = zip(*[optimize(y, False) for y in x[1:]])
2164 wb, tb = optimize(x[2], False)
2165 # we can't reorder trees by weight because it would change the order. 2163 # we can't reorder trees by weight because it would change the order.
2166 # ("sort(a + b)" == "sort(b + a)", but "a + b" != "b + a") 2164 # ("sort(a + b)" == "sort(b + a)", but "a + b" != "b + a")
2167 # if wb < wa: 2165 # ts = tuple(t for w, t in sorted(zip(ws, ts), key=lambda wt: wt[0]))
2168 # tb, ta = ta, tb 2166 return max(ws), (op,) + ts
2169 return max(wa, wb), (op, ta, tb)
2170 elif op == 'not': 2167 elif op == 'not':
2171 # Optimize not public() to _notpublic() because we have a fast version 2168 # Optimize not public() to _notpublic() because we have a fast version
2172 if x[1] == ('func', ('symbol', 'public'), None): 2169 if x[1] == ('func', ('symbol', 'public'), None):
2173 newsym = ('func', ('symbol', '_notpublic'), None) 2170 newsym = ('func', ('symbol', '_notpublic'), None)
2174 o = optimize(newsym, not small) 2171 o = optimize(newsym, not small)
2382 2379
2383 p = parser.parser(tokenizedefn, elements) 2380 p = parser.parser(tokenizedefn, elements)
2384 tree, pos = p.parse(defn) 2381 tree, pos = p.parse(defn)
2385 if pos != len(defn): 2382 if pos != len(defn):
2386 raise error.ParseError(_('invalid token'), pos) 2383 raise error.ParseError(_('invalid token'), pos)
2387 return tree 2384 return parser.simplifyinfixops(tree, ('or',))
2388 2385
2389 class revsetalias(object): 2386 class revsetalias(object):
2390 # whether own `error` information is already shown or not. 2387 # whether own `error` information is already shown or not.
2391 # this avoids showing same warning multiple times at each `findaliases`. 2388 # this avoids showing same warning multiple times at each `findaliases`.
2392 warned = False 2389 warned = False
2513 def parse(spec, lookup=None): 2510 def parse(spec, lookup=None):
2514 p = parser.parser(tokenize, elements) 2511 p = parser.parser(tokenize, elements)
2515 tree, pos = p.parse(spec, lookup=lookup) 2512 tree, pos = p.parse(spec, lookup=lookup)
2516 if pos != len(spec): 2513 if pos != len(spec):
2517 raise error.ParseError(_("invalid token"), pos) 2514 raise error.ParseError(_("invalid token"), pos)
2518 return tree 2515 return parser.simplifyinfixops(tree, ('or',))
2519 2516
2520 def posttreebuilthook(tree, repo): 2517 def posttreebuilthook(tree, repo):
2521 # hook for extensions to execute code on the optimized tree 2518 # hook for extensions to execute code on the optimized tree
2522 pass 2519 pass
2523 2520