@yuja Let me know if this can simplify matchtree, buildtree implementation.

I also wonder if it makes sense to move (part of, mostly weight related) _optimize to runtime (getset), since the revset functions could have more information. For example, if sort gets rev as sort key, it could use getset(order=any) instead of getset(order=define). Some functions like ancestors(revs) also do not care about the order of revs, and we are being conservative - using define for all function arguments now.

Clever. I haven't looked this carefully, but the general direction seems fine.

@yuja Let me know if this can simplify matchtree, buildtree implementation.

Actually matchtree can ignore extra elements in a node tuple, so the existence
of order flag is acceptable, though this will slightly simplify the match function.

I also wonder if it makes sense to move (part of, mostly weight related) _optimize to runtime (getset), since the revset functions could have more information. For example, if sort gets rev as sort key, it could use getset(order=any) instead of getset(order=define). Some functions like ancestors(revs) also do not care about the order of revs, and we are being conservative - using define for all function arguments now.

That could be, perhaps.

(just scanned the series; no careful review yet)

Perhaps the name defineorder was misleading. As of lazyset was introduced,
most revset predicates "follow"ed the order of the input subset, which was by
default rev-ascending. This is also true now. And there are a few exceptions
(e.g. rangeset), which MAY enforce their ordering scheme if the flag is defineorder.

So, anyorder for not x would be my mistake because x and not y could be
theoretically flipped.

We could change this policy so all predicates must "define" their own ordering
schemes (as you did, I think), but I guess that would lead to bugs that are hardly
noticed. So I'm against to bring more "any" ordering without noticeable
performance win. Can you measure it?

I think it's more correct if all core revsets support defineorder explicitly. The current code depends on revset.makematcher using ascending fullreposet as default to make defineorder implicitly functional. If the callsite passes an non-ascending (unordered, or descending) set to the returned matcher, the code would behave wrong (ex. _flipand(1:0, _flipand(1:0, 0::1)) would be wrong if a descending fullreposet is passed).

It seems to me that the reason why people can get ordering wrong is because of legacy APIs (repo, subset, x). I tried to address that by introducing intersect(subset, xs, order) and suggest repo, x API (D453). If people write code using the new API, it's much harder to have ordering issues.

D456 provides a good test coverage about core revset ordering issues. If we really want to address ordering issues of 3rd party code, maybe we can deprecate repo, subset, x API and force people to either take subset and order, or none of them. Or require an explicit supportorder flag to be defined to mark it as order-safe.

So I'm against to bring more "any" ordering without noticeable
performance win. Can you measure it?

Probably hard to measure. Since it's in theory useful for performance, I'm leaning towards keeping it. Test can random-shuffle anyorder sets and expect the result to still be correct (I didn't include that test change since D456 has better coverage with less code).

I'll wait for some comments before updating the series. The planned changes are:

• move micro optimizations like anyorder in sort to a single patch.
• move D456 to maybe the first patch in the series so we can track ordering correctness changes closely.

In D451#7281, @quark wrote:

I think it's more correct if all core revsets support defineorder explicitly. The current code depends on revset.makematcher using ascending fullreposet as default to make defineorder implicitly functional. If the callsite passes an non-ascending (unordered, or descending) set to the returned matcher, the code would behave wrong (ex. _flipand(1:0, _flipand(1:0, 0::1)) would be wrong if a descending fullreposet is passed).

Perhaps _flipand(1:0, _flipand(1:0, 0::1)) would return [1, 0] if the input set
were reversed. IMHO, that's correct under the original design.

It seems to me that the reason why people can get ordering wrong is because of legacy APIs (repo, subset, x). I tried to address that by introducing intersect(subset, xs, order) and suggest repo, x API (D453). If people write code using the new API, it's much harder to have ordering issues.
D456 provides a good test coverage about core revset ordering issues. If we really want to address ordering issues of 3rd party code, maybe we can deprecate repo, subset, x API and force people to either take subset and order, or none of them. Or require an explicit supportorder flag to be defined to mark it as order-safe.

I agree new decorator API would be slightly better for trivial cases, but the situation
for 3rd-party extensions would be worse. Before, subset was the canonical
source of ordering. Since most revset predicates should not have their own order,
they just needed to return a set in subset's order.

return subset.filter(...)

IIUC, this will be no longer be valid. All revset predicates will have to take care
of order flag if they need a subset argument, just because few predicates
want to enforce their order. This seems not a good balance.

In D451#7257, @yuja wrote:

So, anyorder for not x would be my mistake because x and not y could be
theoretically flipped.

FWIW, this should be okay since not x follows the order of the input subset.
The order of the x doesn't matter.

In D451#7456, @yuja wrote:

Perhaps _flipand(1:0, _flipand(1:0, 0::1)) would return [1, 0] if the input set
were reversed. IMHO, that's correct under the original design.

I see. The old code allows "weak define" that "define" becomes "follow". There is no way to tell if a revset is "strong define" or "weak define" from the help text. So it could be confusing sometimes.

list(revset.match(None, '_flipand(1:0, _flipand(1:0, 0::1))', order=ORDER)(repo, revset.baseset(INITSET)))

Since set.sort() is lazy and optimized to a no-op. Migrating everything to "strong define" does not seem to hurt performance in the default use-case. So I'd like to do that for core revsets.

but the situation for 3rd-party extensions would be worse

I think not all 3rd-party extensions need subset. subset is only required if they need filter the subset. There are many cases where just defining a small set is enough (ex. remotenames()). I'd like to show another "define a small set" example: d6708c20, where it's easier to make mistake using the old API (well, it's the reviewer of that change to blame).

All revset predicates will have to take care of order flag if they need a subset argument, just because few predicates want to enforce their order.

For the old code, all predicates must not change order if it's not supposed to define. I now see that's why anyorder is less useful in the old code - not seems to be the only valid case. The new code would allow anyorder to be used in wider cases.

Not directly related to this series, I think some revsets might want a non-ascending "define" order. For example, it seems more natural if p1(A+B) could be equivalent to p1(A)+p1(B). Same applies to p2, parents, children and maybe roots, heads.

Interestingly, I checked some well known 3rd-party extensions:

hgsubversion:

• svnrev() uses x for x in myset if x in subset therefore enforces "defineorder" and wrong.
• fromsvn() is also wrong similarly.

hg-git:

• fromgit(), gitnode(): happened to be "followorder" since it uses x for x in subset if ...

mutable-history:

• troubled(), suspended(), precursors(), ...: all of them use subset & ... , therefore enforces "followorder"

remotenames:

• remotenames(): uses subset & ... pattern
• upstream(): uses smartset.filteredset(subset, ...), which could be changed to subset.filter(...). But it's literally subset & tipancestors and does not have to use subset.filter.
• pushed(): same as upstream()

All of them could just remove subset argument without hurting performance. They may not be able to do that because they need to support older Mercurial. But I think that could be seen as an indication that new code probably does not need the subset argument.

I had also wanted to remove the need to pass subset, so I'd be happy so that change.

In D451#7499, @quark wrote:

hgsubversion:

• svnrev() uses x for x in myset if x in subset therefore enforces "defineorder" and wrong.
• fromsvn() is also wrong similarly.

Yes, they are wrong (and I've pointed out that before in hgsubversion thread.)
They could benefit from new subset-less API.

hg-git:

• fromgit(), gitnode(): happened to be "followorder" since it uses x for x in subset if ...

mutable-history:

• troubled(), suspended(), precursors(), ...: all of them use subset & ... , therefore enforces "followorder"

remotenames:

• remotenames(): uses subset & ... pattern
• upstream(): uses smartset.filteredset(subset, ...), which could be changed to subset.filter(...). But it's literally subset & tipancestors and does not have to use subset.filter.
• pushed(): same as upstream()

All of them could just remove subset argument without hurting performance. They may not be able to do that because they need to support older Mercurial. But I think that could be seen as an indication that new code probably does not need the subset argument.

The point is these implementations would become invalid if subset were
optimized to "any" order. That's breaking change, but which is likely to be
not covered by tests.

As I said, most revset predicates have no explicit order. I introduced the
order flag in order to work around a few exceptions, which are x:y,
x + y, sort() and reverse(), IIRC. A strong "define" is exceptional.

So, is it really make sense to revamp the revset ordering rules? I don't
think so. I generally like this series, but -1 for bringing "any" order
everywhere.

In D451#7698, @yuja wrote:

The point is these implementations would become invalid if subset were
optimized to "any" order. That's breaking change, but which is likely to be
not covered by tests.

How about making registrar.revsetpredicate conservative? If it sees any
predicate registered with the old API, Disable anyorder optimization and
change it to followorder in runtime?

That seems to address the concern about correctness of legacy code.

As I said, most revset predicates have no explicit order. I introduced the
order flag in order to work around a few exceptions, which are x:y,
x + y, sort() and reverse(), IIRC. A strong "define" is exceptional.

I feel it inconsistent if x:y has a strong order but x::y does not.
I also want to change p1, etc's define order as mentioned above.

So, is it really make sense to revamp the revset ordering rules? I don't
think so. I generally like this series, but -1 for bringing "any" order
everywhere.

I think in general, the new code is more explicit and better testable.
I'd like to move forward and not get blocked by legacy code.

I understand "anyorder" in the old code is almost a mistake. But with
the new code, and suppose no legacy code is used, "anyoder" is safe.
It seems to be simple (only used in a few places), less error-prone
(core hg has and encourages strong defineorder), and do have value
for optimization. I'd like to keep it. I can gate it by a config
option but I don't think that's necessary if we make registrar handle
it automatically.

How about making registrar.revsetpredicate conservative? If it sees any
predicate registered with the old API, Disable anyorder optimization and
change it to followorder in runtime?

Sounds unnecessarily complicated. How fast is the anyorder set in real-world
queries? Is that worth introducing more "if"s and corresponding tests?

We can apply anyorder optimization to inner queries even if we decided to not
optimize _flipand(). For example, think ancestors(complex_query), where
complex_query can be computed in anyorder constraint because we can be
sure the order of head revisions doesn't matter. OTOH, _flipand(x, y) is hard
because x is passed to arbitrary sub-expression y.

As I said, most revset predicates have no explicit order. I introduced the
order flag in order to work around a few exceptions, which are x:y,
x + y, sort() and reverse(), IIRC. A strong "define" is exceptional.

I feel it inconsistent if x:y has a strong order but x::y does not.

It would be surprising if x::parent suddenly starts listing parent's children
in reverse order.

I also want to change p1, etc's define order as mentioned above.

I don't like this idea because it would make things more inconsistent.
For instance, branch(a + b) could be branch(a) + branch(b), and ancestors(a:b)
could be ancestors(a) + ... + ancestors(b), but is that really what we want?

So, is it really make sense to revamp the revset ordering rules? I don't
think so. I generally like this series, but -1 for bringing "any" order
everywhere.

I think in general, the new code is more explicit and better testable.
I'd like to move forward and not get blocked by legacy code.
I understand "anyorder" in the old code is almost a mistake. But with
the new code, and suppose no legacy code is used, "anyoder" is safe.
It seems to be simple (only used in a few places), less error-prone
(core hg has and encourages strong defineorder), and do have value
for optimization. I'd like to keep it. I can gate it by a config
option but I don't think that's necessary if we make registrar handle
it automatically.

I doubt if it is really error-prone. We'll have to make sure that a revset
function returns a set in the right "defined" order (or an unordered set
which will be sorted implicitly by intersect().)

The current rule is IMHO, simpler. Almost all revsets are in the same
order unless they are explicitly sorted or concatenated.

In D451#8029, @yuja wrote:

How about making registrar.revsetpredicate conservative? If it sees any
predicate registered with the old API, Disable anyorder optimization and
change it to followorder in runtime?

Sounds unnecessarily complicated.

I just got a new idea: Wrap those 3-argument predicate in a function that
does an extra sort if it's defineorder [1]. That seems to solve things
cleanly.

How fast is the anyorder set in real-world
queries? Is that worth introducing more "if"s and corresponding tests?

mozilla-central % hg.old perfrevset 'sort(public() & 1:3)'
! wall 0.193297 comb 0.190000 user 0.190000 sys 0.000000 (best of 51)
mozilla-central % hg.new perfrevset 'sort(public() & 1:3)'
! wall 0.000188 comb 0.000000 user 0.000000 sys 0.000000 (best of 13504)

So I think anyorder definitely has value (not that much to a revset expert though).

We can apply anyorder optimization to inner queries even if we decided to not
optimize _flipand(). For example, think ancestors(complex_query), where
complex_query can be computed in anyorder constraint because we can be
sure the order of head revisions doesn't matter. OTOH, _flipand(x, y) is hard
because x is passed to arbitrary sub-expression y.

I hope the word "hard" here could suggest that the new code does make things simpler at least in this case.

It would be surprising if x::parent suddenly starts listing parent's children
in reverse order.
I don't like this idea because it would make things more inconsistent.
For instance, branch(a + b) could be branch(a) + branch(b), and ancestors(a:b)
could be ancestors(a) + ... + ancestors(b), but is that really what we want?

We can say revsets taking N revs returning O(N) revs would maintain
the order, and not for other revsets. That'd be clearly defined.
But I don't feel strong. We can keep the existing behavior here.

I doubt if it is really error-prone. We'll have to make sure that a revset
function returns a set in the right "defined" order (or an unordered set
which will be sorted implicitly by intersect().)

(The enforce-define [1] idea seems to address this well)

The current rule is IMHO, simpler. Almost all revsets are in the same
order unless they are explicitly sorted or concatenated.

Maybe. But if you insist defineorder does not always need to "define" order.
I hope I can rename it to maybedefineorder, which will make it less confusing
for developers. That said, I still prefer strong "define"s. It seems Martin
also likes it. I think it's simpler because both developers and end-users
won't need to worry about the "weak define" concept.

First, I'm tired of discussing this. Perhaps, you would be the same (guessing
from the initial reply.) I don't think this should be a blocker of your previous
series which optimizes draft() ... something.

If you want to move things forward, please split non-controversial parts,
which I think are:

• remove "order" from parsed tree, use _flipand() instead
• make subset argument optional

Alternatively, I could send my build/matchtree patch without respecting to
this series to unblock your original patch.

I just got a new idea: Wrap those 3-argument predicate in a function that
does an extra sort if it's defineorder [1]. That seems to solve things
cleanly.

I don't think it's clean, but yeah doable. If I had to take this series, that would
be the safest workaround for old code.

mozilla-central % hg.old perfrevset 'sort(public() & 1:3)'
! wall 0.193297 comb 0.190000 user 0.190000 sys 0.000000 (best of 51)
mozilla-central % hg.new perfrevset 'sort(public() & 1:3)'
! wall 0.000188 comb 0.000000 user 0.000000 sys 0.000000 (best of 13504)

So I think anyorder definitely has value (not that much to a revset expert though).

In this example, public() & 1:3 could be fully optimized to anyorder
without the help of _flipand(). It's obvious that the order of public() & 1:3
doesn't matter.

We can apply anyorder optimization to inner queries even if we decided to not
optimize _flipand(). For example, think ancestors(complex_query), where
complex_query can be computed in anyorder constraint because we can be
sure the order of head revisions doesn't matter. OTOH, _flipand(x, y) is hard
because x is passed to arbitrary sub-expression y.

I hope the word "hard" here could suggest that the new code does make things simpler at least in this case.

I think it's "simpler" at the cost of bringing the "order" concept everywhere.

We can say revsets taking N revs returning O(N) revs would maintain
the order, and not for other revsets. That'd be clearly defined.
But I don't feel strong. We can keep the existing behavior here.

Yep. I don't want to think about the complexity to determine if a revset
predicate may define its own order.

Maybe. But if you insist defineorder does not always need to "define" order.
I hope I can rename it to maybedefineorder, which will make it less confusing
for developers.

Seems good.

That said, I still prefer strong "define"s. It seems Martin
also likes it.

I guess he liked it since the new registrar would get rid of the subset
argument. So do I in that regard.

I think it's simpler because both developers and end-users
won't need to worry about the "weak define" concept.

Users and (most) developers don't have to think about it in either case.
Almost all revsets should be in revision order.

Don't worry about that optimization patch. I'll refactor this series and use maybedefine. Thanks!

It seems _optimize() has more bugs, so I decided to not queue this.
I have partially updated patch, but how can I collaborate with you?

FWIW, I think _optimize() could use defineorder/anyorder constants
in place of True/False for readablity.

It seems _optimize() has more bugs

Perhaps we can eliminate preserveorder flag from _optimize() at all.
flipand can always be inserted since and(x, y) is exactly the same as
flipand(x, y) if order != defineorder. For or, we could

• backout c63cb2d10d6d assuming the optimization wouldn't be that useful
• or add an internal method to select define/anyorder tree at runtime, e.g. (switch-by-order (or original-tree) (or sorted-tree))

One of the drawback of the current patch is we have to resolve the order
constraint twice, at parsing phase and evaluation phase. That's probably why
I decided to embed the flag to parsed tree, though I don't remember it. :-)

I have partially updated patch, but how can I collaborate with you?

You can phabsend . which will update this patch (assuming Differential Revision: .../D451 line exists), and I can fix the rest of things.

Perhaps we can eliminate preserveorder flag from _optimize() at all.

I like that simplicity. I don't think or optimization is that important (so there was no _flipor).

If we can attach extra hints (not affecting correctness if get lost) to tree nodes (ex. not tuple, but a TreeNode object with a estimated_weight property), the optimization about and and or could be moved to runtime and _flipand becomes unnecessary.

You can phabsend . which will update this patch

Done.

Perhaps we can eliminate preserveorder flag from _optimize() at all.

I like that simplicity. I don't think or optimization is that important (so there was no _flipor).

Let's revert c63cb2d10d6d then.