Patchwork D6140: revset: add new contiguous(x) function for "x::x"

login
register
mail settings
Submitter phabricator
Date March 15, 2019, 5:27 a.m.
Message ID <differential-rev-PHID-DREV-iccfhw2okalrs24wl5st-req@phab.mercurial-scm.org>
Download mbox | patch
Permalink /patch/39257/
State New
Headers show

Comments

phabricator - March 15, 2019, 5:27 a.m.
martinvonz created this revision.
Herald added a subscriber: mercurial-devel.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  "x::x" is a useful trick for making a range contiguous, but it gets
  annoying if "x" is a long expression. Let's provide a simple function
  that helps with that. It also makes it the trick more discoverable.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

AFFECTED FILES
  mercurial/revset.py
  tests/test-revset.t

CHANGE DETAILS




To: martinvonz, #hg-reviewers
Cc: mercurial-devel
Pierre-Yves David - March 15, 2019, 10:48 a.m.
I am a fan of this function, I need this on a regular basis. Having an 
explicit function for this also open the way to various optimization. 
For example we know that a set already has this property we could skip 
all computation.

I am ambivalent about the naming however. It feels a bit odd. There are 
case where it could be misleading.

Lets look at the following case:

   c e
   | |
   b d
   |/
   a

the revset `(b+c+d+e)::(b+c+d+e)` returns the same `b+c+d+e`, however 
the set is not "contiguous" as `b+c` and `d+e` as not connected.

This feels a bit more like a "closure" operation to me.

Cheers,

On 3/15/19 6:27 AM, martinvonz (Martin von Zweigbergk) wrote:
> martinvonz created this revision.
> Herald added a subscriber: mercurial-devel.
> Herald added a reviewer: hg-reviewers.
> 
> REVISION SUMMARY
>    "x::x" is a useful trick for making a range contiguous, but it gets
>    annoying if "x" is a long expression. Let's provide a simple function
>    that helps with that. It also makes it the trick more discoverable.
> 
> REPOSITORY
>    rHG Mercurial
> 
> REVISION DETAIL
>    https://phab.mercurial-scm.org/D6140
> 
> AFFECTED FILES
>    mercurial/revset.py
>    tests/test-revset.t
> 
> CHANGE DETAILS
> 
> diff --git a/tests/test-revset.t b/tests/test-revset.t
> --- a/tests/test-revset.t
> +++ b/tests/test-revset.t
> @@ -1314,6 +1314,47 @@
>     2
>     3
>   
> +test contiguous
> +
> +  $ hg log -G -T '{rev}\n' --config experimental.graphshorten=True
> +  @  9
> +  o  8
> +  | o  7
> +  | o  6
> +  |/|
> +  | o  5
> +  o |  4
> +  | o  3
> +  o |  2
> +  |/
> +  o  1
> +  o  0
> +
> +  $ log 'contiguous(0+2)'
> +  0
> +  1
> +  2
> +  $ log 'contiguous(2+0)'
> +  0
> +  1
> +  2
> +  $ log 'contiguous(2+3)'
> +  2
> +  3
> +  $ log 'contiguous(3+2)'
> +  2
> +  3
> +  $ log 'contiguous(3+7)'
> +  3
> +  5
> +  6
> +  7
> +  $ log 'contiguous(9+3+4)'
> +  3
> +  4
> +  8
> +  9
> +
>   test author
>   
>     $ log 'author(bob)'
> diff --git a/mercurial/revset.py b/mercurial/revset.py
> --- a/mercurial/revset.py
> +++ b/mercurial/revset.py
> @@ -714,6 +714,16 @@
>   
>       return subset.filter(matches, condrepr=('<contains %r>', pat))
>   
> +@predicate('contiguous(set)', safe=True, takeorder=True)
> +def contiguous(repo, subset, x, order):
> +    """Changesets that have both ancestors and descendants in the set. This
> +    effectively fills in gaps in the set to make it contiguous, without adding
> +    new common ancestors or common descendants.
> +
> +     "contiguous(x)" is identical to "x::x".
> +    """
> +    return dagrange(repo, subset, x, x, order)
> +
>   @predicate('converted([id])', safe=True)
>   def converted(repo, subset, x):
>       """Changesets converted from the given identifier in the old repository if
> 
> 
> 
> To: martinvonz, #hg-reviewers
> Cc: mercurial-devel
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>
Pierre-Yves David - March 15, 2019, 10:51 a.m.
I am a fan of this function, I need this on a regular basis. Having an 
explicit function for this also open the way to various optimization. 
For example we know that a set already has this property we could skip 
all computation.

I am ambivalent about the naming however. It feels a bit odd. There are 
case where it could be misleading.

Lets look at the following case:

   c e
   | |
   b d
   |/
   a

the revset `(b+c+d+e)::(b+c+d+e)` returns the same `b+c+d+e`, however 
the set is not "contiguous" as `b+c` and `d+e` as not connected.

This feels a bit more like a "closure" operation to me.

Cheers,

On 3/15/19 6:27 AM, martinvonz (Martin von Zweigbergk) wrote:
> martinvonz created this revision.
> Herald added a subscriber: mercurial-devel.
> Herald added a reviewer: hg-reviewers.
> 
> REVISION SUMMARY
>    "x::x" is a useful trick for making a range contiguous, but it gets
>    annoying if "x" is a long expression. Let's provide a simple function
>    that helps with that. It also makes it the trick more discoverable.
> 
> REPOSITORY
>    rHG Mercurial
> 
> REVISION DETAIL
>    https://phab.mercurial-scm.org/D6140
> 
> AFFECTED FILES
>    mercurial/revset.py
>    tests/test-revset.t
> 
> CHANGE DETAILS
> 
> diff --git a/tests/test-revset.t b/tests/test-revset.t
> --- a/tests/test-revset.t
> +++ b/tests/test-revset.t
> @@ -1314,6 +1314,47 @@
>     2
>     3
>   
> +test contiguous
> +
> +  $ hg log -G -T '{rev}\n' --config experimental.graphshorten=True
> +  @  9
> +  o  8
> +  | o  7
> +  | o  6
> +  |/|
> +  | o  5
> +  o |  4
> +  | o  3
> +  o |  2
> +  |/
> +  o  1
> +  o  0
> +
> +  $ log 'contiguous(0+2)'
> +  0
> +  1
> +  2
> +  $ log 'contiguous(2+0)'
> +  0
> +  1
> +  2
> +  $ log 'contiguous(2+3)'
> +  2
> +  3
> +  $ log 'contiguous(3+2)'
> +  2
> +  3
> +  $ log 'contiguous(3+7)'
> +  3
> +  5
> +  6
> +  7
> +  $ log 'contiguous(9+3+4)'
> +  3
> +  4
> +  8
> +  9
> +
>   test author
>   
>     $ log 'author(bob)'
> diff --git a/mercurial/revset.py b/mercurial/revset.py
> --- a/mercurial/revset.py
> +++ b/mercurial/revset.py
> @@ -714,6 +714,16 @@
>   
>       return subset.filter(matches, condrepr=('<contains %r>', pat))
>   
> +@predicate('contiguous(set)', safe=True, takeorder=True)
> +def contiguous(repo, subset, x, order):
> +    """Changesets that have both ancestors and descendants in the set. This
> +    effectively fills in gaps in the set to make it contiguous, without adding
> +    new common ancestors or common descendants.
> +
> +     "contiguous(x)" is identical to "x::x".
> +    """
> +    return dagrange(repo, subset, x, x, order)
> +
>   @predicate('converted([id])', safe=True)
>   def converted(repo, subset, x):
>       """Changesets converted from the given identifier in the old repository if
> 
> 
> 
> To: martinvonz, #hg-reviewers
> Cc: mercurial-devel
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>
phabricator - March 15, 2019, 10:52 a.m.
marmoute added a comment.


  I am a fan of this function, I need this on a regular basis. Having an 
  explicit function for this also open the way to various optimization. 
  For example we know that a set already has this property we could skip 
  all computation.
  
  I am ambivalent about the naming however. It feels a bit odd. There are 
  case where it could be misleading.
  
  Lets look at the following case:
  
    c e
    | |
    b d
    |/
    a
  
  the revset `(b+c+d+e)::(b+c+d+e)` returns the same `b+c+d+e`, however 
  the set is not "contiguous" as `b+c` and `d+e` as not connected.
  
  This feels a bit more like a "closure" operation to me.
  
  Cheers,

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

To: martinvonz, #hg-reviewers
Cc: marmoute, mercurial-devel
phabricator - March 15, 2019, 3:28 p.m.
martinvonz added a comment.


  In https://phab.mercurial-scm.org/D6140#89400, @marmoute wrote:
  
  > I am a fan of this function, I need this on a regular basis. Having an 
  >  explicit function for this also open the way to various optimization. 
  >  For example we know that a set already has this property we could skip 
  >  all computation.
  >
  > I am ambivalent about the naming however. It feels a bit odd. There are 
  >  case where it could be misleading.
  >
  > Lets look at the following case:
  >
  >   c e
  >   | |
  >   b d
  >   |/
  >   a
  >   
  >
  > the revset `(b+c+d+e)::(b+c+d+e)` returns the same `b+c+d+e`, however 
  >  the set is not "contiguous" as `b+c` and `d+e` as not connected.
  
  
  Right, that's what I tried to express with "without adding new common ancestors or common descendants" in the documentation.
  
  > This feels a bit more like a "closure" operation to me.
  
  That's what I suggested on IRC because the operation somehow made me think of a closure, but when I looked up what a closure is, it seems like `ancestors()` is the actual closure function (if we consider the direction to point from child to parents as we normally do).

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

To: martinvonz, #hg-reviewers
Cc: marmoute, mercurial-devel
Pierre-Yves David - March 15, 2019, 6:11 p.m.
I chatted a bit with Georges about this. He suggested something along 
the line of `fill` or `complete`.

On 3/15/19 4:28 PM, martinvonz (Martin von Zweigbergk) wrote:
> martinvonz added a comment.
> 
> 
>    In https://phab.mercurial-scm.org/D6140#89400, @marmoute wrote:
>    
>    > I am a fan of this function, I need this on a regular basis. Having an
>    >  explicit function for this also open the way to various optimization.
>    >  For example we know that a set already has this property we could skip
>    >  all computation.
>    >
>    > I am ambivalent about the naming however. It feels a bit odd. There are
>    >  case where it could be misleading.
>    >
>    > Lets look at the following case:
>    >
>    >   c e
>    >   | |
>    >   b d
>    >   |/
>    >   a
>    >
>    >
>    > the revset `(b+c+d+e)::(b+c+d+e)` returns the same `b+c+d+e`, however
>    >  the set is not "contiguous" as `b+c` and `d+e` as not connected.
>    
>    
>    Right, that's what I tried to express with "without adding new common ancestors or common descendants" in the documentation.
>    
>    > This feels a bit more like a "closure" operation to me.
>    
>    That's what I suggested on IRC because the operation somehow made me think of a closure, but when I looked up what a closure is, it seems like `ancestors()` is the actual closure function (if we consider the direction to point from child to parents as we normally do).
> 
> REPOSITORY
>    rHG Mercurial
> 
> REVISION DETAIL
>    https://phab.mercurial-scm.org/D6140
> 
> To: martinvonz, #hg-reviewers
> Cc: marmoute, mercurial-devel
> _______________________________________________
> Mercurial-devel mailing list
> Mercurial-devel@mercurial-scm.org
> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>
phabricator - March 15, 2019, 6:12 p.m.
marmoute added a subscriber: gracinet.
marmoute added a comment.


  I chatted a bit with Georges about this. He suggested something along 
  the line of `fill` or `complete`.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

To: martinvonz, #hg-reviewers
Cc: gracinet, marmoute, mercurial-devel
phabricator - March 15, 2019, 6:19 p.m.
martinvonz added a subscriber: spectral.
martinvonz added a comment.


  In https://phab.mercurial-scm.org/D6140#89440, @marmoute wrote:
  
  > I chatted a bit with Georges about this. He suggested something along 
  >  the line of `fill` or `complete`.
  
  
  `fill` also came up in IRC yesterday. @spectral found it slightly confusing that it there's a template function with the same name. I don't think we talked about `complete`. Other examples were `connect`, `fillgaps`, `gapfill`. Oh, and apparently nbjoerg also suggested `closure` (before I did) :) Funny how three of us came up with the same name. I still like `contiguous` the best, but let's see if we got other suggestions or votes for existing suggestions.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

To: martinvonz, #hg-reviewers
Cc: spectral, gracinet, marmoute, mercurial-devel
phabricator - March 15, 2019, 11:13 p.m.
gracinet added a comment.


  I thought of "closure" as well, but I fear it has too many possible meanings, "transitive closure" being one of them in that context (certainly related, but not the same thing), and of course the closures in functional programming.
  
  I think "hull" could be appropriate, if not too pedantic.
  
  I couldn't find out quickly if people dealing with partial ordered sets theory (another way to think of DAGs) actually use "hull", but here's the analogy:
  for the convex hull, you add [a, b] (line segment) to the set whenever a and b belong to it, for this "poset hull" you do the same with a::b (which in poset theory would be called the interval [a, b])
  
  This S::S operation seems to be a special case of Closure Operators in the sense of https://en.wikipedia.org/wiki/Closure_operator, which tells us that "hull" can indeed be used as alternative terminology in some cases where "closure" can be confusing (they quote topology). In that same article, there's inded yet another meaning in the context of partially ordered sets, as a generalisation of the very first definition (generalising the power set to any partially ordered set).
  
  /taking rusty mathematical hat off now

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

To: martinvonz, #hg-reviewers
Cc: spectral, gracinet, marmoute, mercurial-devel
phabricator - March 16, 2019, 2:02 a.m.
martinvonz added a subscriber: av6.
martinvonz added a comment.


  In https://phab.mercurial-scm.org/D6140#89469, @gracinet wrote:
  
  > I thought of "closure" as well, but I fear it has too many possible meanings, "transitive closure" being one of them in that context (certainly related, but not the same thing), and of course the closures in functional programming.
  >
  > I think "hull" could be appropriate, if not too pedantic.
  >
  > I couldn't find out quickly if people dealing with partial ordered sets theory (another way to think of DAGs) actually use "hull", but here's the analogy:
  >  for the convex hull, you add [a, b] (line segment) to the set whenever a and b belong to it, for this "poset hull" you do the same with a::b (which in poset theory would be called the interval [a, b])
  
  
  Wouldn't the hull pretty much be `heads(contiguous(x)) or roots(contiguous(x))`? Regardless, most users are not math nerds. I still think `contiguous()` is pretty clear. Sure, it won't join separate branches by adding ancestors or descendants, but I'm not sure there is a name that conveys that meaning too while not being too academic. @av6 also prefers `contiguous`, so we have two votes for that. I'm not sure how many votes for `closure` we have.
  
  If we still want to find a better name, maybe it helps to remember that the function returns nodes that are *both* ancestors and descendants of some nodes in the input. Maybe something family-related (like "ancestors" and "descendants" are)? But I can't think of any term like that.
  
  > This S::S operation seems to be a special case of Closure Operators in the sense of https://en.wikipedia.org/wiki/Closure_operator, which tells us that "hull" can indeed be used as alternative terminology in some cases where "closure" can be confusing (they quote topology). In that same article, there's inded yet another meaning in the context of partially ordered sets, as a generalisation of the very first definition (generalising the power set to any partially ordered set).
  > 
  > /taking rusty mathematical hat off now

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

To: martinvonz, #hg-reviewers
Cc: av6, spectral, gracinet, marmoute, mercurial-devel
Yuya Nishihara - March 16, 2019, 2:37 a.m.
I think "contiguous" is good as it stands for the main use case. "closure"
seems confusing unless we have stronger math background than computer science.
The other candidates would require more knowledge about the theory.
phabricator - March 16, 2019, 2:43 a.m.
yuja added a comment.


  I think "contiguous" is good as it stands for the main use case. "closure"
  seems confusing unless we have stronger math background than computer science.
  The other candidates would require more knowledge about the theory.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

To: martinvonz, #hg-reviewers
Cc: yuja, av6, spectral, gracinet, marmoute, mercurial-devel
phabricator - March 18, 2019, 10:54 p.m.
martinvonz added a comment.


  In https://phab.mercurial-scm.org/D6140#89474, @yuja wrote:
  
  > I think "contiguous" is good as it stands for the main use case. "closure"
  >  seems confusing unless we have stronger math background than computer science.
  >  The other candidates would require more knowledge about the theory.
  
  
  I'd say we've reached a decision then, but I'm obviously biased.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D6140

To: martinvonz, #hg-reviewers
Cc: yuja, av6, spectral, gracinet, marmoute, mercurial-devel

Patch

diff --git a/tests/test-revset.t b/tests/test-revset.t
--- a/tests/test-revset.t
+++ b/tests/test-revset.t
@@ -1314,6 +1314,47 @@ 
   2
   3
 
+test contiguous
+
+  $ hg log -G -T '{rev}\n' --config experimental.graphshorten=True
+  @  9
+  o  8
+  | o  7
+  | o  6
+  |/|
+  | o  5
+  o |  4
+  | o  3
+  o |  2
+  |/
+  o  1
+  o  0
+
+  $ log 'contiguous(0+2)'
+  0
+  1
+  2
+  $ log 'contiguous(2+0)'
+  0
+  1
+  2
+  $ log 'contiguous(2+3)'
+  2
+  3
+  $ log 'contiguous(3+2)'
+  2
+  3
+  $ log 'contiguous(3+7)'
+  3
+  5
+  6
+  7
+  $ log 'contiguous(9+3+4)'
+  3
+  4
+  8
+  9
+
 test author
 
   $ log 'author(bob)'
diff --git a/mercurial/revset.py b/mercurial/revset.py
--- a/mercurial/revset.py
+++ b/mercurial/revset.py
@@ -714,6 +714,16 @@ 
 
     return subset.filter(matches, condrepr=('<contains %r>', pat))
 
+@predicate('contiguous(set)', safe=True, takeorder=True)
+def contiguous(repo, subset, x, order):
+    """Changesets that have both ancestors and descendants in the set. This
+    effectively fills in gaps in the set to make it contiguous, without adding
+    new common ancestors or common descendants.
+
+     "contiguous(x)" is identical to "x::x".
+    """
+    return dagrange(repo, subset, x, x, order)
+
 @predicate('converted([id])', safe=True)
 def converted(repo, subset, x):
     """Changesets converted from the given identifier in the old repository if