comparison tests/test-revset.t @ 20499:2efd608473fb

revset: optimize missing ancestor expressions

A missing ancestor expression is any expression of the form (::x - ::y) or
equivalent. Such expressions are remarkably common, and so far have involved
multiple walks down the DAG, followed by a set difference operation.

With this patch, such expressions will be transformed into uses of the fast
algorithm at ancestor.missingancestor.

For a repository with over 600,000 revisions, perfrevset for '::tip - ::-10000'
returns:

Before: ! wall 3.999575 comb 4.000000 user 3.910000 sys 0.090000 (best of 3)
After:  ! wall 0.132423 comb 0.130000 user 0.130000 sys 0.000000 (best of 75)

20498:fb2df4506c87

  6
  $ log 'tag(1.0)'
  6
  $ log 'tag(tip)'
  9

we can use patterns when searching for tags

  $ log 'tag("1..*")'
  abort: tag '1..*' does not exist

20499:2efd608473fb

  6
  $ log 'tag(1.0)'
  6
  $ log 'tag(tip)'
  9

check that conversion to _missingancestors works
  $ try --optimize '::3 - ::1'
  (minus
    (dagrangepre
      ('symbol', '3'))
    (dagrangepre
      ('symbol', '1')))
  * optimized:
  (func
    ('symbol', '_missingancestors')
    (list
      ('symbol', '3')
      ('symbol', '1')))
  3
  $ try --optimize 'ancestors(1) - ancestors(3)'
  (minus
    (func
      ('symbol', 'ancestors')
      ('symbol', '1'))
    (func
      ('symbol', 'ancestors')
      ('symbol', '3')))
  * optimized:
  (func
    ('symbol', '_missingancestors')
    (list
      ('symbol', '1')
      ('symbol', '3')))
  $ try --optimize 'not ::2 and ::6'
  (and
    (not
      (dagrangepre
        ('symbol', '2')))
    (dagrangepre
      ('symbol', '6')))
  * optimized:
  (func
    ('symbol', '_missingancestors')
    (list
      ('symbol', '6')
      ('symbol', '2')))
  3
  4
  5
  6
  $ try --optimize 'ancestors(6) and not ancestors(4)'
  (and
    (func
      ('symbol', 'ancestors')
      ('symbol', '6'))
    (not
      (func
        ('symbol', 'ancestors')
        ('symbol', '4'))))
  * optimized:
  (func
    ('symbol', '_missingancestors')
    (list
      ('symbol', '6')
      ('symbol', '4')))
  3
  5
  6

we can use patterns when searching for tags

  $ log 'tag("1..*")'
  abort: tag '1..*' does not exist