Patchwork revsetlang: enable optimization of 'x + y' expression

login
register
mail settings
Submitter Yuya Nishihara
Date April 2, 2017, 2:28 p.m.
Message ID <069d36366695ccc5e953.1491143325@mimosa>
Download mbox | patch
Permalink /patch/19905/
State Accepted
Headers show

Comments

Yuya Nishihara - April 2, 2017, 2:28 p.m.
# HG changeset patch
# User Yuya Nishihara <yuya@tcha.org>
# Date 1463226717 -32400
#      Sat May 14 20:51:57 2016 +0900
# Node ID 069d36366695ccc5e953b35f7068f158242c1a29
# Parent  04ec317b81280c189fcea33a05c8cbbac3c186b1
revsetlang: enable optimization of 'x + y' expression

It's been disabled since 4d1e56b29a91, but it can be enabled now as the
ordering requirement is resolved at analyze().
Augie Fackler - April 3, 2017, 8:13 p.m.
On Sun, Apr 02, 2017 at 11:28:45PM +0900, Yuya Nishihara wrote:
> # HG changeset patch
> # User Yuya Nishihara <yuya@tcha.org>
> # Date 1463226717 -32400
> #      Sat May 14 20:51:57 2016 +0900
> # Node ID 069d36366695ccc5e953b35f7068f158242c1a29
> # Parent  04ec317b81280c189fcea33a05c8cbbac3c186b1
> revsetlang: enable optimization of 'x + y' expression

Queued, thanks.

>
> It's been disabled since 4d1e56b29a91, but it can be enabled now as the
> ordering requirement is resolved at analyze().
>
> diff --git a/mercurial/revsetlang.py b/mercurial/revsetlang.py
> --- a/mercurial/revsetlang.py
> +++ b/mercurial/revsetlang.py
> @@ -434,9 +434,9 @@ def _optimize(x, small):
>          flushss()
>          if len(ts) == 1:
>              return ws[0], ts[0] # 'or' operation is fully optimized out
> -        # we can't reorder trees by weight because it would change the order.
> -        # ("sort(a + b)" == "sort(b + a)", but "a + b" != "b + a")
> -        #   ts = tuple(t for w, t in sorted(zip(ws, ts), key=lambda wt: wt[0]))
> +        if order != defineorder:
> +            # reorder by weight only when f(a + b) == f(b + a)
> +            ts = [wt[1] for wt in sorted(zip(ws, ts), key=lambda wt: wt[0])]
>          return max(ws), (op, ('list',) + tuple(ts), order)
>      elif op == 'not':
>          # Optimize not public() to _notpublic() because we have a fast version
> diff --git a/tests/test-revset.t b/tests/test-revset.t
> --- a/tests/test-revset.t
> +++ b/tests/test-revset.t
> @@ -1420,19 +1420,19 @@ ordering defined by it.
>        define)
>      (or
>        (list
> +        ('symbol', '2')
>          (range
>            ('symbol', '0')
>            ('symbol', '1')
> -          follow)
> -        ('symbol', '2'))
> +          follow))
>        follow)
>      define)
>    * set:
>    <filteredset
>      <spanset- 0:2>,
>      <addset
> -      <spanset+ 0:1>,
> -      <baseset [2]>>>
> +      <baseset [2]>,
> +      <spanset+ 0:1>>>
>    2
>    1
>    0
> @@ -1917,6 +1917,69 @@ ordering defined by it.
>    1
>    0
>
> + 'A + B' can be rewritten to 'B + A' by weight only when the order doesn't
> + matter (e.g. 'X & (A + B)' can be 'X & (B + A)', but '(A + B) & X' can't):
> +
> +  $ try -p optimized '0:2 & (reverse(contains("a")) + 2)'
> +  * optimized:
> +  (and
> +    (range
> +      ('symbol', '0')
> +      ('symbol', '2')
> +      define)
> +    (or
> +      (list
> +        ('symbol', '2')
> +        (func
> +          ('symbol', 'reverse')
> +          (func
> +            ('symbol', 'contains')
> +            ('string', 'a')
> +            define)
> +          follow))
> +      follow)
> +    define)
> +  * set:
> +  <filteredset
> +    <spanset+ 0:2>,
> +    <addset
> +      <baseset [2]>,
> +      <filteredset
> +        <fullreposet+ 0:9>,
> +        <contains 'a'>>>>
> +  0
> +  1
> +  2
> +
> +  $ try -p optimized '(reverse(contains("a")) + 2) & 0:2'
> +  * optimized:
> +  (and
> +    (range
> +      ('symbol', '0')
> +      ('symbol', '2')
> +      follow)
> +    (or
> +      (list
> +        (func
> +          ('symbol', 'reverse')
> +          (func
> +            ('symbol', 'contains')
> +            ('string', 'a')
> +            define)
> +          define)
> +        ('symbol', '2'))
> +      define)
> +    define)
> +  * set:
> +  <addset
> +    <filteredset
> +      <spanset- 0:2>,
> +      <contains 'a'>>,
> +    <baseset [2]>>
> +  1
> +  0
> +  2
> +
>  test sort revset
>  --------------------------------------------
>
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel

Patch

diff --git a/mercurial/revsetlang.py b/mercurial/revsetlang.py
--- a/mercurial/revsetlang.py
+++ b/mercurial/revsetlang.py
@@ -434,9 +434,9 @@  def _optimize(x, small):
         flushss()
         if len(ts) == 1:
             return ws[0], ts[0] # 'or' operation is fully optimized out
-        # we can't reorder trees by weight because it would change the order.
-        # ("sort(a + b)" == "sort(b + a)", but "a + b" != "b + a")
-        #   ts = tuple(t for w, t in sorted(zip(ws, ts), key=lambda wt: wt[0]))
+        if order != defineorder:
+            # reorder by weight only when f(a + b) == f(b + a)
+            ts = [wt[1] for wt in sorted(zip(ws, ts), key=lambda wt: wt[0])]
         return max(ws), (op, ('list',) + tuple(ts), order)
     elif op == 'not':
         # Optimize not public() to _notpublic() because we have a fast version
diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -1420,19 +1420,19 @@  ordering defined by it.
       define)
     (or
       (list
+        ('symbol', '2')
         (range
           ('symbol', '0')
           ('symbol', '1')
-          follow)
-        ('symbol', '2'))
+          follow))
       follow)
     define)
   * set:
   <filteredset
     <spanset- 0:2>,
     <addset
-      <spanset+ 0:1>,
-      <baseset [2]>>>
+      <baseset [2]>,
+      <spanset+ 0:1>>>
   2
   1
   0
@@ -1917,6 +1917,69 @@  ordering defined by it.
   1
   0
 
+ 'A + B' can be rewritten to 'B + A' by weight only when the order doesn't
+ matter (e.g. 'X & (A + B)' can be 'X & (B + A)', but '(A + B) & X' can't):
+
+  $ try -p optimized '0:2 & (reverse(contains("a")) + 2)'
+  * optimized:
+  (and
+    (range
+      ('symbol', '0')
+      ('symbol', '2')
+      define)
+    (or
+      (list
+        ('symbol', '2')
+        (func
+          ('symbol', 'reverse')
+          (func
+            ('symbol', 'contains')
+            ('string', 'a')
+            define)
+          follow))
+      follow)
+    define)
+  * set:
+  <filteredset
+    <spanset+ 0:2>,
+    <addset
+      <baseset [2]>,
+      <filteredset
+        <fullreposet+ 0:9>,
+        <contains 'a'>>>>
+  0
+  1
+  2
+
+  $ try -p optimized '(reverse(contains("a")) + 2) & 0:2'
+  * optimized:
+  (and
+    (range
+      ('symbol', '0')
+      ('symbol', '2')
+      follow)
+    (or
+      (list
+        (func
+          ('symbol', 'reverse')
+          (func
+            ('symbol', 'contains')
+            ('string', 'a')
+            define)
+          define)
+        ('symbol', '2'))
+      define)
+    define)
+  * set:
+  <addset
+    <filteredset
+      <spanset- 0:2>,
+      <contains 'a'>>,
+    <baseset [2]>>
+  1
+  0
+  2
+
 test sort revset
 --------------------------------------------