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

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 >

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

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

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 >

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

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

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

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

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.

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

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