Mercurial > public > mercurial-scm > hg-stable

comparison mercurial/revset.py @ 11279:62ccf4cd6e7f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
revset: optimize the parse tree directly Rather than dynamically optimize in methods, we pre-optimize the parse tree directly. This also lets us do some substitution on some of the symbols like - and ::.
author Matt Mackall <mpm@selenic.com>
date Thu, 03 Jun 2010 17:39:34 -0500
parents 7df88cdf47fd
children a5eb0bf7e158
comparison
equal deleted inserted replaced
11278:7df88cdf47fd 11279:62ccf4cd6e7f
130 n = getset(repo, subset, y)[-1] 130 n = getset(repo, subset, y)[-1]
131 if m < n: 131 if m < n:
132 return range(m, n + 1) 132 return range(m, n + 1)
133 return range(m, n - 1, -1) 133 return range(m, n - 1, -1)
134 134
135 def rangepreset(repo, subset, x):
136 return range(0, getset(repo, subset, x)[-1] + 1)
137
138 def rangepostset(repo, subset, x):
139 return range(getset(repo, subset, x)[0], len(repo))
140
141 def dagrangeset(repo, subset, x, y):
142 return andset(repo, subset,
143 ('func', ('symbol', 'descendants'), x),
144 ('func', ('symbol', 'ancestors'), y))
145
146 def andset(repo, subset, x, y): 135 def andset(repo, subset, x, y):
147 if weight(x, True) > weight(y, True):
148 x, y = y, x
149 return getset(repo, getset(repo, subset, x), y) 136 return getset(repo, getset(repo, subset, x), y)
150 137
151 def orset(repo, subset, x, y): 138 def orset(repo, subset, x, y):
152 if weight(y, False) < weight(x, False):
153 x, y = y, x
154 s = set(getset(repo, subset, x)) 139 s = set(getset(repo, subset, x))
155 s |= set(getset(repo, [r for r in subset if r not in s], y)) 140 s |= set(getset(repo, [r for r in subset if r not in s], y))
156 return [r for r in subset if r in s] 141 return [r for r in subset if r in s]
157 142
158 def notset(repo, subset, x): 143 def notset(repo, subset, x):
159 s = set(getset(repo, subset, x)) 144 s = set(getset(repo, subset, x))
160 return [r for r in subset if r not in s] 145 return [r for r in subset if r not in s]
161
162 def minusset(repo, subset, x, y):
163 if weight(x, True) > weight(y, True):
164 return getset(repo, notset(repo, subset, y), x)
165 return notset(repo, getset(repo, subset, x), y)
166 146
167 def listset(repo, subset, a, b): 147 def listset(repo, subset, a, b):
168 raise "can't use a list in this context" 148 raise "can't use a list in this context"
169 149
170 def func(repo, subset, a, b): 150 def func(repo, subset, a, b):
477 "outgoing": outgoing, 457 "outgoing": outgoing,
478 } 458 }
479 459
480 methods = { 460 methods = {
481 "negate": negate, 461 "negate": negate,
482 "minus": minusset,
483 "range": rangeset, 462 "range": rangeset,
484 "rangepre": rangepreset,
485 "rangepost": rangepostset,
486 "dagrange": dagrangeset,
487 "dagrangepre": ancestors,
488 "dagrangepost": descendants,
489 "string": stringset, 463 "string": stringset,
490 "symbol": symbolset, 464 "symbol": symbolset,
491 "and": andset, 465 "and": andset,
492 "or": orset, 466 "or": orset,
493 "not": notset, 467 "not": notset,
494 "list": listset, 468 "list": listset,
495 "func": func, 469 "func": func,
496 "group": lambda r, s, x: getset(r, s, x),
497 } 470 }
498 471
499 def weight(x, small): 472 def optimize(x, small):
473 if x == None:
474 return 0, x
475
500 smallbonus = 1 476 smallbonus = 1
501 if small: 477 if small:
502 smallbonus = .5 478 smallbonus = .5
503 479
504 op = x[0] 480 op = x[0]
505 if op in 'string symbol negate': 481 if op == '-':
506 return smallbonus # single revisions are small 482 return optimize(('and', x[1], ('not', x[2])), small)
483 elif op == 'dagrange':
484 return optimize(('and', ('func', ('symbol', 'descendants'), x[1]),
485 ('func', ('symbol', 'ancestors'), x[2])), small)
486 elif op == 'dagrangepre':
487 return optimize(('func', ('symbol', 'ancestors'), x[1]), small)
488 elif op == 'dagrangepost':
489 return optimize(('func', ('symbol', 'descendants'), x[1]), small)
490 elif op == 'rangepre':
491 return optimize(('range', ('string', '0'), x[1]), small)
492 elif op == 'rangepost':
493 return optimize(('range', x[1], ('string', 'tip')), small)
494 elif op in 'string symbol negate':
495 return smallbonus, x # single revisions are small
507 elif op == 'and' or op == 'dagrange': 496 elif op == 'and' or op == 'dagrange':
508 return min(weight(x[1], True), weight(x[2], True)) 497 wa, ta = optimize(x[1], True)
509 elif op in 'or -': 498 wb, tb = optimize(x[2], True)
510 return max(weight(x[1], False), weight(x[2], False)) 499 w = min(wa, wb)
500 if wa > wb:
501 return w, (op, tb, ta)
502 return w, (op, ta, tb)
503 elif op == 'or':
504 wa, ta = optimize(x[1], False)
505 wb, tb = optimize(x[2], False)
506 if wb < wa:
507 wb, wa = wa, wb
508 return max(wa, wb), (op, ta, tb)
511 elif op == 'not': 509 elif op == 'not':
512 return weight(x[1], not small) 510 o = optimize(x[1], not small)
511 return o[0], (op, o[1])
513 elif op == 'group': 512 elif op == 'group':
514 return weight(x[1], small) 513 return optimize(x[1], small)
515 elif op == 'range': 514 elif op in 'rangepre rangepost dagrangepre dagrangepost':
516 return weight(x[1], small) + weight(x[2], small) 515 wa, ta = optimize(x[1], small)
516 return wa + 1, (op, ta)
517 elif op in 'range list':
518 wa, ta = optimize(x[1], small)
519 wb, tb = optimize(x[2], small)
520 return wa + wb, (op, ta, tb)
517 elif op == 'func': 521 elif op == 'func':
518 f = getstring(x[1], "not a symbol") 522 f = getstring(x[1], "not a symbol")
523 wa, ta = optimize(x[2], small)
519 if f in "grep date user author keyword branch file": 524 if f in "grep date user author keyword branch file":
520 return 10 # slow 525 w = 10 # slow
521 elif f in "modifies adds removes": 526 elif f in "modifies adds removes outgoing":
522 return 30 # slower 527 w = 30 # slower
523 elif f == "contains": 528 elif f == "contains":
524 return 100 # very slow 529 w = 100 # very slow
525 elif f == "ancestor": 530 elif f == "ancestor":
526 return (weight(x[1][1], small) + 531 w = 1 * smallbonus
527 weight(x[1][2], small)) * smallbonus
528 elif f == "reverse limit": 532 elif f == "reverse limit":
529 return weight(x[1], small) 533 w = 0
530 elif f in "sort": 534 elif f in "sort":
531 base = x[1] 535 w = 10 # assume most sorts look at changelog
532 spec = "rev"
533 if x[1][0] == 'list':
534 base = x[1][1]
535 spec = x[1][2]
536 return max(weight(base, small), 10)
537 else: 536 else:
538 return 1 537 w = 1
538 return w + wa, (op, x[1], ta)
539 return 1, x
539 540
540 parse = parser.parser(tokenize, elements).parse 541 parse = parser.parser(tokenize, elements).parse
541 542
542 def match(spec): 543 def match(spec):
543 tree = parse(spec) 544 tree = parse(spec)
545 weight, tree = optimize(tree, True)
544 def mfunc(repo, subset): 546 def mfunc(repo, subset):
545 return getset(repo, subset, tree) 547 return getset(repo, subset, tree)
546 return mfunc 548 return mfunc