Element richcmp: never use id()

[Marc Mezzarobba]

As discussed in the sage-devel thread starting with <o21nte$6jp$1@blaine.gmane.org> (​https://groups.google.com/d/msg/sage-devel/YVFdxPH6avk/4OZUmzLHBgAJ), coercion_model.richcmp() should not fall back on comparing by type/id.

This branch implements comparisons for Element the same way as in Python 3: a TypeError is raised for uncomparable objects (instead of comparing by id).

Dependencies: #22297, #22344, #22346, #22369, #22370, #22371, #22372, #22373, #22376, #22382, #24968, #26917, #26931, #26933, #26934, #26935, #26936, #26937, #26938, #26947, #27003, #27009, #27010, #27026, #27027, #27029, #27123, #27241

[Jeroen Demeyer]

Do you plan to work on this? If yes, fill in your name as reviewer. If no, let me know.

[Marc Mezzarobba]

Replying to jdemeyer:

Do you plan to work on this? If yes, fill in your name as reviewer.

as author? owner?

If no, let me know.

I've started doing experiments, but I'll most likely need help from people who understand the parts of Sage that rely on the current behavior. At the very least I'll try to push a first draft in the next few days.

[Marc Mezzarobba]

My main concern right now is that sage.graphs heavily relies on sorting lists of vertices, while various other parts of Sage create graphs with vertices that mix Elements with other Python objects.

An option might be to try again with key=id when sort() fails, but (with no global understanding of the code, at least) there's a major risk of getting inconsistent orders with different subsets of vertices.

Another idea would be to do introduce utilities like

# universal_cmp.pyx
cpdef lt(x, y):
    try:
        return x < y
    except TypeError:
        if type(x) is type(y):
            return id(x) < id(y)
        else:
            return type(x) < type(y)
...

cdef class key(object):
    def __init__(self):
        self.value = value
    def __lt__(self, other):
        return lt(self.value, other.value)
    ...

and then use universal_cmp.lt() and sort(key=universal_cmp.key), but this won't work either when one of the types involved only has a partial order, since this order will not be consistent with id.

Yet another variant would be to pass a comparison function (or, equivalently but probably better in view of the transition to python3, a key as above) that wraps cmp() and catches TypeErrors. Not really ideal either, but at least it wouldn't introduce any regression(?), so perhaps that would be enough for this ticket...

Any advice?

[Jeroen Demeyer]

Replying to mmezzarobba:

Replying to jdemeyer:

Do you plan to work on this? If yes, fill in your name as reviewer.

as author? owner?

Sorry, I meant as author.

[Marc Mezzarobba]

By the way, why did you remove the reference to the sage-devel thread?

[Jeroen Demeyer]

Replying to mmezzarobba:

By the way, why did you remove the reference to the sage-devel thread?

Because I didn't understand how to interpret it. A hyperlink would be better.

[Jeroen Demeyer]

Replying to mmezzarobba:

My main concern right now is that sage.graphs heavily relies on sorting lists of vertices

Why does it rely on sorting vertices?

[Marc Mezzarobba]

Replying to jdemeyer:

Replying to mmezzarobba:

By the way, why did you remove the reference to the sage-devel thread?

Because I didn't understand how to interpret it. A hyperlink would be better.

I personally prefer Message-Ids, as they don't depend on a particular archive...

[Marc Mezzarobba]

Replying to jdemeyer:

Replying to mmezzarobba:

My main concern right now is that sage.graphs heavily relies on sorting lists of vertices

Why does it rely on sorting vertices?

In sparse_graph and generic_graph, mostly. Some of the occurrences look like they are there for algorithmic purposes, others to make the output more readable, some both at the same time... I didn't look closely enough to say more.

[Jeroen Demeyer]

Replying to mmezzarobba:

In sparse_graph and generic_graph, mostly. Some of the occurrences look like they are there for algorithmic purposes, others to make the output more readable, some both at the same time... I didn't look closely enough to say more.

It's also important to note the difference between old-style cmp() and new-style rich comparisons. Ideally, this branch would only affect the latter.

[Marc Mezzarobba]

Replying to jdemeyer:

It's also important to note the difference between old-style cmp() and new-style rich comparisons. Ideally, this branch would only affect the latter.

I'm not sure I follow you: cmp() can end up calling Element.__richcmp__(), and that's perhaps the main reason why getting rid of the comparison by id there is not trivial.

[Nils Bruin]

Replying to mmezzarobba:

My main concern right now is that sage.graphs heavily relies on sorting lists of vertices, while various other parts of Sage create graphs with vertices that mix Elements with other Python objects.

An option might be to try again with key=id when sort() fails, but (with no global understanding of the code, at least) there's a major risk of getting inconsistent orders with different subsets of vertices.

If you have no information on the objects you're sorting, I don't think there is anything that can save you. If your objects are guaranteed to be hashable you could try sorting on the hash, but that will leave your results undefined when hashes clash. In any case, if you rely on "first try what the object implements and then use a fallback if that fails", you're doomed.

In fact, if you allow your vertices to be labelled with arbitrary objects, you're already losing transitivity of equality in sage, via the standard

sage: a=GF(3)(1); b =31; c=GF(5)(1)
sage: a==b,b==c,a==c
(True, True, False)

It seems that labels get mangled anyway, though, so I think them not being sorted properly is only a minor concern by comparison (sorry):

sage: a=GF(3)(1); b =31; c=GF(5)(1)
sage: L=[[a,b,c],[a,c,b],[b,a,c],[b,c,a],[c,a,b],[c,b,a]]
sage: for l in L:
....:     G=Graph()
....:     for i in l:
....:         G.add_vertex(i)
....:     print [parent(j) for j in G.vertices()]
....:     
[<type 'int'>, Integer Ring]
[<type 'int'>, Integer Ring]
[<type 'int'>, Integer Ring]
[<type 'int'>, Integer Ring]
[<type 'int'>, Integer Ring]
[<type 'int'>, Integer Ring]

It seems to me the only sane approaches are to not rely on sorting (in python it seems being hashable is more ubiquitous than being sortable, so fast lookup is likely better accomplished via hash functions), or to declare that the labels are sortable (making failure a user error).

This stuff causes real problems: since the old python interface for __cmp__ methods required one to provide non-errors for "<" and ">" testing if one wants to implement "==", sage is riddled with apparent implementations of orderings that are in actuality inconsistent. This has cause problems in at least one case, where labels in published tables of elliptic curves were based on non-sensical but assumed-consistent ordering of number field elements:

​https://groups.google.com/forum/#!topic/sage-nt/aP5LP09sADY

This has convinced me that the only sane approach is to deprecate "cmp" style interfaces as quickly as possible and instead rely on "richcmp", with errors for ordering if not obviously correct.

[Marc Mezzarobba]

Here is a first attempt. All (standard, long) tests should pass unless I made a last-minute mistake. See the commit messages for some comments. I'm not 100% happy with the changes, but I don't think I can do much better in a reasonable amount of time, feel free to commit improvements to the existing branch!

---

Last 10 new commits:

​d45cd53	CGraphBackend: fix a segfault when given a non-existing vertex
​6e0e1b2	Fix use of comparison in simplicial_complex
​2925d0f	Bug in Poset.is_slender(?)
​2b0bcc9	Some benign doctest failures related to #22029
​5f36421	Ad-hoc comparison functions for graph vertices
​6d728fa	{c,sparse}_graph: systematically turn integer-like vertices into ints
​fcda2c2	graph_plot: sort by id
​127a11d	remove or fix some meaningless doctests for cmp()
​29fe1f8	misc fixes after changes to coercion_model.richcmp
​749dfbe	misc fixes after changes to coercion_model.richcmp

[Travis Scrimshaw]

I am a strong -1 on the removal of the != tests and the changes of foo != bar to (the fugly) not (foo == bar).

The failures you have in rigged_configurations.py is because you moved the definition of case_S. You have also made the cases in the code more difficult to follow. Please revert those changes.

[Jeroen Demeyer]

This is bad:

        # (Note that, when y is not a Sage Element, we may have ended up here
        # from a call to cmp(). In this case, and in this case only, it may be
        # better to emulate what Python does and compare by type/id. But we
        # have no way(?) to distinguish this situation from the "normal" case
        # of a comparison operator.)

[Marc Mezzarobba]

Replying to tscrim:

I am a strong -1 on the removal of the != tests and the changes of foo != bar to (the fugly) not (foo == bar).

Ugly, I agree, but safer in generic code (because of cases where equality is not decidable, like expressions, or where not enough information is available, like with intervals)... And code that might end up comparing objects of different type is generic code.

The failures you have in rigged_configurations.py is because you moved the definition of case_S. You have also made the cases in the code more difficult to follow. Please revert those changes.

I might do it, but I'd like first to understand in detail the alternative you are suggesting, and to see some evidence of a consensus that it is a better option.

In any case, please feel free to commit improvements yourself, and I'll do my best to review them.

[Marc Mezzarobba]

Replying to jdemeyer:

This is bad:

        # (Note that, when y is not a Sage Element, we may have ended up here
        # from a call to cmp(). In this case, and in this case only, it may be
        # better to emulate what Python does and compare by type/id. But we
        # have no way(?) to distinguish this situation from the "normal" case
        # of a comparison operator.)

What do you mean? If I understand right, this is an issue that will solve itself if sage ever switches to Python3...

[Jeroen Demeyer]

Replying to mmezzarobba:

If I understand right, this is an issue that will solve itself if sage ever switches to Python3...

Given that we currently still have Python 2, that's irrelevant.

[Marc Mezzarobba]

Replying to jdemeyer:

Replying to mmezzarobba:

If I understand right, this is an issue that will solve itself if sage ever switches to Python3...

Given that we currently still have Python 2, that's irrelevant.

Sorry, I fear I still don't understand your comment. The problem with cmp() was the main thing I asked about in the sage-devel post that led to this ticket, and you basically replied that it was okay from your point of view to remove the fallback code from richcmp. Now it looks to me like you are saying the contrary.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​fb9beb5

misc fixes after changes to coercion_model.richcmp

[Marc Mezzarobba]

Replying to tscrim:

The failures you have in rigged_configurations.py is because you moved the definition of case_S. You have also made the cases in the code more difficult to follow.

Fixed, sorry for the stupid mistake. That's all I did for now. It wouldn't be hard to revert the other changes related to !=, but I'm waiting for answers to the follow-up question I just asked on sage-devel.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​6e69645

Elt richcmp: return NotImplemented for non-Elements...

[Marc Mezzarobba]

Another take, now returning NotImplemented more often. Due to Jeroen's doubts, I left out the idea of treating SageObjects in a special way. I do however handle types such as int and float like Element, since this is what the coercion framework usually does.

This should make it possible to revert some of my other changes. I haven't done it yet.

[Jeroen Demeyer]

Replying to mmezzarobba:

I do however handle types such as int and float like Element since this is what the coercion framework usually does.

Yes, the coercion framework tries to coerce those types to a Sage Element. However, it doesn't do anything special in the case that such a coercion fails. So I don't see why you should treat the failed-coercion-with-int-or-float case differently. Just return NotImplemented in that case.

[Marc Mezzarobba]

Replying to jdemeyer:

Yes, the coercion framework tries to coerce those types to a Sage Element. However, it doesn't do anything special in the case that such a coercion fails.

But the net effect is that arithmetic that mixes Elements and objects of these types will succeed or fail (with an error coming from the coercion framework) depending whether there is a common parent or not.

So I don't see why you should treat the failed-coercion-with-int-or-float case differently. Just return NotImplemented in that case.

Do you really want things like

sage: GF(2)(1) > float(0.)
True
sage: RBF(0) < float(-1.)
True
sage: SymmetricGroup(2)(()) != int(1)
True

even though it takes exactly one LOC to prevent them and analogous code with Sage Elements raises an error (so that, in particular, the behavior will be different for preparsed and pure Python code)?

[Jeroen Demeyer]

Replying to mmezzarobba:

Do you really want things like

sage: GF(2)(1) > float(0.)
True
sage: RBF(0) < float(-1.)
True
sage: SymmetricGroup(2)(()) != int(1)
True

In Python 2? Yes, I want that.

In Python 3? No, I do not want that.

[Jeroen Demeyer]

In other words: just follow the common Python convention which specifies that a rich comparison (not __cmp__) should return NotImplemented when it cannot decide a comparison.

The fact that we directly raise a TypeError for Sage Elements is merely a shortcut to get the correct behaviour and to get a nicer error message referring to the parents.

[Marc Mezzarobba]

Replying to jdemeyer:

In other words: just follow the common Python convention which specifies that a rich comparison (not __cmp__) should return NotImplemented when it cannot decide a comparison.

I tend to see the situation we are talking about not as one where it can't decide, but as one where it can decide that the comparison doesn't make sense. And not to find “just follow the Python[2] convention” such a strong argument when Sage already breaks it in much worse ways...

[Jeroen Demeyer]

Replying to mmezzarobba:

And not to find “just follow the Python[2] convention” such a strong argument when Sage already breaks it in much worse ways...

How is it relevant whether or not Sage breaks certain Python conventions in much worse ways?

If Python specifies how to do arithmetic/comparisons, why not follow that?

[Marc Mezzarobba]

Replying to jdemeyer:

How is it relevant whether or not Sage breaks certain Python conventions in much worse ways?

When you start deviating from the general conventions, “your” objects already don't interact with the rest of the system as other developers will expect, and your job IMHO is to minimize the damage.

Now, there is no doubt that you have orders of magnitude more experience of Sage development than I'll likely ever do, so I guess I'll follow your advice even without understanding it if that's really the only way. But I'd really prefer (in general: I'm bringing this up because it is not the first time I have trouble understanding your comments) if you could explain why you think a certain technical choice is better instead of just stating that it is.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​af1a94a	Fix use of comparison in simplicial_complex
​744942c	Bug in Poset.is_slender(?)
​ea1910e	Some benign doctest failures related to #22029
​c87d7e3	Ad-hoc comparison functions for graph vertices
​107ad68	{c,sparse}_graph: systematically turn integer-like vertices into ints
​fd03cd8	graph_plot: sort by id
​69cc074	remove or fix some meaningless doctests for cmp()
​b33f2eb	Elt richcmp: return NotImplemented for non-Elements...
​87ca195	misc fixes after recent changes to coercion_model.richcmp()
​a5a1e2b	Jeroen doesn't like this

[Marc Mezzarobba]

New version of the complete patch series. Tested without the last commit, not fully with it.

I probably won't have much time to work on this in the coming 6-8 weeks, please feel free to take over if you have improvements to make.

[Marc Mezzarobba]

The “known bug” is now #22071.

[Marc Mezzarobba]

Replying to tscrim:

I am a strong -1 on the removal of the != tests and the changes of foo != bar to (the fugly) not (foo == bar).

Does the new version (that returns NotImplemented in more cases, so ill-typed comparisons by != will typically succeed when the other member is not an Element) address your concerns?

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

[Marc Mezzarobba]

Replying to mmezzarobba:

New version of the complete patch series. Tested without the last commit, not fully with it.

Turns out there where ​test failures with that commit. Since it is still not clear to me that it is really what we want, I undid it for now.

[Julian Rüth]

I also have trouble seeing why what jdemeyer proposes would be better. For me the proposed changes look fine.

[Marc Mezzarobba]

It is plausible that the ad-hoc comparison functions for graph vertices can be simplified (or even removed) thanks to the fact that the general comparison function now returns NotImplemented for non-Elements. I haven't had time to check yet.

Also, there are apparently test failures with sage-2.6...

I'll try to work on these issues in 1-2 weeks unless someone beats me to it.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​ea99124

Merge branch 'public/ticket/22029-richcmp_fallback' in 7.6.b2

[Frédéric Chapoton]

I just rebased on 7.6.b2 (easily fixed conflict with #22266)

[Jeroen Demeyer]

Let me try to "reboot" this ticket with a different approach: when coercion fails, assume that elements are different (so == and != would not give an error).

[Jeroen Demeyer]

The good pieces of the current branch should be split up into different tickets. It is doing way too much for one ticket.

[Jeroen Demeyer]

I might tackle Parent (#22344) first. It is a similar but hopefully easier ticket.

[Marc Mezzarobba]

I hope to have time tomorrow to clean up the branch a little. Then you can do whatever you want with it. But I still think that raising an error when coercion fails and both objects to be compared are Elements is a better tradeoff.

[Travis Scrimshaw]

Replying to mmezzarobba:

I hope to have time tomorrow to clean up the branch a little. Then you can do whatever you want with it. But I still think that raising an error when coercion fails and both objects to be compared are Elements is a better tradeoff.

I (also) think in that case we are safe to conclude that == and != should be False and True, respectively. The coercion framework does not allow us to create a new coercion path after that point IIRC. For < and >, raising an error is consistent with Python (specifically a TypeError).

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​e58fc96

Element richcmp: never use id()

[Jeroen Demeyer]

Replying to mmezzarobba:

I hope to have time tomorrow to clean up the branch a little.

It's not really about cleaning the branch, it's about identifying pieces which make sense to be a new ticket.

[Marc Mezzarobba]

Here is a version that does not require #22349 (nor other intrusive changes to graphs/) nor #22346 and passes all (short) tests but one even if we make a != b fail when there is no coercion. Which is what the branch currently does, but that shouldn't be hard to change. (Jeroen, I didn't update the dependency list because I don't really known what you have in mind with this ticket; the true dependencies with the current branch are the one that are obvious from the commits.)

Pretty much everything is improvable, especially the “main” commit, but I don't think I have left anything too dirty.

The one test that fails is:

File "src/sage/combinat/integer_vector_weighted.py", line 272, in sage.combinat.integer_vector_weighted.WeightedIntegerVectors_all.__init__
Failed example:
    TestSuite(C).run()
Expected nothing
Got:
    Failure in _test_elements_neq:
    Traceback (most recent call last):
      File "/home/marc/co/sage/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 293, in run
        test_method(tester = tester)
      File "/home/marc/co/sage/local/lib/python2.7/site-packages/sage/categories/sets_cat.py", line 1330, in _test_elements_neq
        tester.assertNotEqual(x == y, x != y,
      File "sage/structure/element.pyx", line 1125, in sage.structure.element.Element.__richcmp__ (/home/marc/co/sage/src/build/cythonized/sage/structure/element.c:10379)
        return coercion_model.richcmp(self, other, op)
      File "sage/structure/coerce.pyx", line 1907, in sage.structure.coerce.CoercionModel_cache_maps.richcmp (/home/marc/co/sage/src/build/cythonized/sage/structure/coerce.c:20514)
        raise bin_op_exception(_operator_to_string(op), x, y)
    TypeError: unsupported operand parent(s) for !=: 'Integer vectors of 0 weighted by [2, 1, 3]' and 'Integer vectors of 1 weighted by [2, 1, 3]'
    ------------------------------------------------------------
    The following tests failed: _test_elements_neq

Replying to jdemeyer:

It's not really about cleaning the branch, it's about identifying pieces which make sense to be a new ticket.

I'm not sure I understand the difference. Anyway, all commits except for the last two are intended to be independent. I didn't test them individually, though, and some probably shouldn't be merged separately without adding a test or two. Please feel free to move anything you want to separate tickets.

[Marc Mezzarobba]

Last 10 new commits:

​e779b2c	FGP_Element: cmp -> richcmp
​a5fe7fe	linear_expression: cmp -> richcmp
​bff3a10	CGraphBackend: fix a segfault when given a non-existing vertex
​3c6c86f	Fix use of comparison in simplicial_complex
​6662d83	Bug in Poset.is_slender(?)
​83af733	{c,sparse}_graph: systematically turn integer-like vertices into ints
​5225368	graph_plot: sort by id
​580e2fb	remove or fix some meaningless doctests for cmp()
​9136fa2	Don't rich-compare Elements by type/id
​3842d12	Additional changes to allow element != obj to raise an error

[Marc Mezzarobba]

Apparently the failure in integer_vector_weighted is due to the fact that DisjointUnionEnumeratedSets(facade=True) are parents that can construct elements whose parents differ from the parent that constructed them:

sage: V = WeightedIntegerVectors([2,1,3])
sage: V.an_element().parent() is V
False

I don't know what to do to fix the issue. Should there be a coercion from WeightedIntegerVectors(n, w) to WeightedIntegerVectors_all(w)? (It may not be easy to set up one, since as far as I understand it is currently not possible to create elements with elt.parent() == WeightedIntegerVectors_all(w) using normal mechanisms, one would have to construct them manually.) Should DisjointUnionEnumeratedSets override the test suite? Should WeightedIntegerVectors use facade=False?...

[Marc Mezzarobba]

For example, the following patch seems to solve the issue, but it is a bit too complicated and fragile to my taste. Do you think it is worth spending time adding docstrings?

src/sage/combinat/integer_vector_weighted.py

@@ -16 +16 @@
 #*****************************************************************************
 from __future__ import print_function, absolute_import
 
+from sage.structure.coerce_maps import CallableConvertMap
 from sage.structure.unique_representation import UniqueRepresentation
 from sage.structure.parent import Parent
+from sage.categories.pushout import ConstructionFunctor, IdentityConstructionFunctor
+from sage.categories.enumerated_sets import EnumeratedSets
 from sage.categories.finite_enumerated_sets import FiniteEnumeratedSets
 from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets
 from sage.categories.sets_with_grading import SetsWithGrading
@@ -28 +31 @@
 from sage.combinat.words.word import Word
 from sage.combinat.permutation import Permutation
 
+class WeightedIntegerVectorFunctor(ConstructionFunctor):
+    rank = 11
+    coercion_reversed = True
+    def __init__(self, n):
+        self.n = n
+        ConstructionFunctor.__init__(self, EnumeratedSets(), EnumeratedSets())
+    def _apply_functor(self, all_vectors):
+        return WeightedIntegerVectors(self.n, all_vectors._weights)
+    def __eq__(self, other):
+        return (isinstance(other, WeightedIntegerVectorFunctor)
+                and other.n == self.n)
+    def merge(self, other):
+        if isinstance(other, WeightedIntegerVectorFunctor):
+            return IdentityConstructionFunctor()
 
 class WeightedIntegerVectors(Parent, UniqueRepresentation):
     r"""
@@ -111 +128 @@
         self._n = n
         self._weights = weight
         Parent.__init__(self, category=FiniteEnumeratedSets())
+        all_vectors = WeightedIntegerVectors_all(self._weights)
+        emb = CallableConvertMap(self, all_vectors, IntegerVector)
+        self._populate_coercion_lists_(embedding=emb)
 
     Element = IntegerVector
 
+    def construction(self):
+        return (WeightedIntegerVectorFunctor(self._n),
+                WeightedIntegerVectors_all(self._weights))
+
     def _element_constructor_(self, lst):
         """
         Construct an element of ``self`` from ``lst``.

[Jeroen Demeyer]

Replying to mmezzarobba:

Please feel free to move anything you want to separate tickets.

OK, I just created #22367, #22368, #22369, #22370, #22371, #22372, #22373, #22374, #22375, #22376. Please set the tickets that you want reviewed to needs_review.

[Travis Scrimshaw]

I would say this is a bigger underlying problem with DisjointUnionEnumeratedSets. This comes from its doc:

sage: class MyUnion(DisjointUnionEnumeratedSets):
....:   def __init__(self):
....:       DisjointUnionEnumeratedSets.__init__(self,
....:            Family([1,2], Permutations))
sage: pp = MyUnion()
sage: pp.list()
[[1], [1, 2], [2, 1]]

We have

sage: pp.list()[0].parent()
Standard permutations of 1

I suspect the biggest problem comes from the fact it does pass the facade option to the category framework. I think your solution is too specific and somewhat over-engineered. While I think there should be an easy mechanism for allowing coercions when we have a non-facade parent, that seems to be tangent to the problem at hand.

The fact that this is causing a problem with a != test is worrisome to me too that there is something subtle not caught by your branch. In particular, you can have != that results in an error, which I strongly believe should never happen.

I also disagree with the change in != test; we should at least make the DummyParent compare by id so the test remains valid.

[Marc Mezzarobba]

Thanks for your commments.

Replying to tscrim:

I suspect the biggest problem comes from the fact it does pass the facade option to the category framework. I think your solution is too specific and somewhat over-engineered.

I agree :-). But I don't know what else to do.

The fact that this is causing a problem with a != test is worrisome to me too that there is something subtle not caught by your branch. In particular, you can have != that results in an error, which I strongly believe should never happen.

Yes, I know we disagree about that. I kept this behavior for now to see how much trouble it would cause, but I can live with a variant that never fails...

I also disagree with the change in != test; we should at least make the DummyParent compare by id so the test remains valid.

I don't see which change you are talking about, sorry.

[Marc Mezzarobba]

Replying to jdemeyer:

Please set the tickets that you want reviewed to needs_review.

Done, thanks.

[Marc Mezzarobba]

Replying to tscrim:

I suspect the biggest problem comes from the fact it does pass the facade option to the category framework. I think your solution is too specific and somewhat over-engineered. While I think there should be an easy mechanism for allowing coercions when we have a non-facade parent, that seems to be tangent to the problem at hand.

The fact that this is causing a problem with a != test is worrisome to me too that there is something subtle not caught by your branch. In particular, you can have != that results in an error, which I strongly believe should never happen.

I forgot to ask: are weighted integer vectors intended to be comparable by < etc.? If not, i.e. if the only issue is comparison by !=, and if we agree that != should never fail, then we can indeed ignore the problem for this ticket.

[Travis Scrimshaw]

Replying to mmezzarobba:

Thanks for your commments.

Replying to tscrim:

I suspect the biggest problem comes from the fact it does pass the facade option to the category framework. I think your solution is too specific and somewhat over-engineered.

I agree :-). But I don't know what else to do.

I have an idea. I should be able to fix it tomorrow (which I will do on a separate ticket).

The fact that this is causing a problem with a != test is worrisome to me too that there is something subtle not caught by your branch. In particular, you can have != that results in an error, which I strongly believe should never happen.

Yes, I know we disagree about that. I kept this behavior for now to see how much trouble it would cause, but I can live with a variant that never fails...

Okay, I wasn't sure about on a quick skim-over what behavior you were trying to support.

I also disagree with the change in != test; we should at least make the DummyParent compare by id so the test remains valid.

I don't see which change you are talking about, sorry.

src/sage/structure/element_wrapper.pyx

@@ -327 +327 @@
             sage: l11 != l12
             True
             sage: l11 != l21
-            True
+            Traceback (most recent call last):
+            ...
+            TypeError: unsupported operand parent(s) for !=: 'A parent' and
+            'Another parent'
 
         Testing less than::
 

I believe this fails because the DummyParent doesn't have comparisons.

Replying to mmezzarobba:

I forgot to ask: are weighted integer vectors intended to be comparable by < etc.? If not, i.e. if the only issue is comparison by !=, and if we agree that != should never fail, then we can indeed ignore the problem for this ticket.

It should be lex ordering, which should be inherited from ClonableArray.

[Jeroen Demeyer]

Replying to mmezzarobba:

Replying to jdemeyer:

Please set the tickets that you want reviewed to needs_review.

Done, thanks.

Could you also remove those commits from the branch on this ticket?

[Jeroen Demeyer]

The fundamental difference between my branch and your branch is that my branch does not fall back to __cmp__ if rich comparison fails. Given that __cmp__ will go away anyway in Python 3, I strongly disagree with relying on __cmp__ for rich comparisons. That will make it even harder to get rid of Python 2 __cmp__ comparisons.

[Jeroen Demeyer]

Not sure what are real dependencies and what not, so I'm just listing all potentially relevant tickets in the ticket description.

[Marc Mezzarobba]

Replying to jdemeyer:

The fundamental difference between my branch and your branch is that my branch does not fall back to __cmp__ if rich comparison fails. Given that __cmp__ will go away anyway in Python 3, I strongly disagree with relying on __cmp__ for rich comparisons. That will make it even harder to get rid of Python 2 __cmp__ comparisons.

I fear I don't understand what you mean. If you're talking about the fact that my version of richcmp can return NotImplemented in some cases, that's something I added following your suggestion on sage-devel...

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​9ac003d	Fix use of comparison in simplicial_complex
​4796945	Bug in Poset.is_slender(?)
​983e660	graph_plot: sort by id
​30d9fb0	remove or fix some meaningless doctests for cmp()
​6d2d496	#22376: additional change at Travis' request
​61feee1	{c,sparse}_graph: systematically turn integer-like vertices into ints
​918a0cb	linear_expression: cmp -> richcmp
​7a240cc	Merge dependencies
​8530b05	Don't rich-compare Elements by type/id
​33e88b0	Additional changes to allow element != obj to raise an error

[Jeroen Demeyer]

Replying to mmezzarobba:

If you're talking about the fact that my version of richcmp can return NotImplemented in some cases

Yes, I am talking about that. When Python sees NotImplemented, it will call __cmp__.

that's something I added following your suggestion on sage-devel...

Well, I don't remember what you refer to, but that was not such a good suggestion then...

[Travis Scrimshaw]

The DisjointUnionEnumeratedSets issue is now #22382.

[Marc Mezzarobba]

Replying to jdemeyer:

that's something I added following your suggestion on sage-devel...

Well, I don't remember what you refer to, but that was not such a good suggestion then...

<585262E2.3060709@cage.ugent.be> / ​https://groups.google.com/d/msg/sage-devel/YVFdxPH6avk/4OZUmzLHBgAJ

[Jeroen Demeyer]

Replying to mmezzarobba:

<585262E2.3060709@cage.ugent.be> / ​https://groups.google.com/d/msg/sage-devel/YVFdxPH6avk/4OZUmzLHBgAJ

Right. What I said there makes sense in principle in a world where only Python 2 exists.

I did not think of the Python 3 porting in that thread. Given that we are moving to Python 3, we might as well start implementing Python 3 semantics for comparisons, which means raising an error when a comparison makes no sense.

[Jeroen Demeyer]

To add to my last comment: we certainly should not make changes which will make the Python 3 porting even harder. I am afraid that your branch does that, since you rely more on the implementation of old-style Python 2 comparisons.

[Marc Mezzarobba]

Replying to jdemeyer:

I am afraid that your branch does that, since you rely more on the implementation of old-style Python 2 comparisons.

Perhaps indeed, I'm not sure. Note that my version only returns NotImplemented when comparing an Element with something else. This by itself is correct (and perhaps desirable) in Python3 too, isn't it? The only thing that will change if what Python will do as a result.

I have no clear opinion regarding whether it is better to return NotImplemented or to fail, and I trust you to know the details of Python3 comparison semantics better than me. The only thing I really care about is that nonsensical comparisons between Elements raise an exception.

However, I expect that raising an exception will break more existing code. Based on what I recall of the first version of my branch, the typical situation where falling back to the default Python2 comparison can help is with graphs or other combinatorial objects with labels that want to compare Elements with strings or with tuples. So, more than making Python3 porting harder, I think my version delays some of the issues with existing code to the actual porting.

I'm not going to try going back to a version that doesn't use NotImplemented in the next few days. But if you have one that works well, I could try to find time to review it some time next week.

[Jeroen Demeyer]

Replying to mmezzarobba:

Note that my version only returns NotImplemented when comparing an Element with something else. This by itself is correct (and perhaps desirable) in Python3 too, isn't it?

Yes, return NotImplemented is the right do to in Python 2. It is also the right thing to do in Python 3. So you would think that it's always right, but it's not.

The problem is that the implications of this return NotImplemented are very different in Python 2 and Python 3. Python 2 will happily compare the objects anyway while Python 3 will raise an exception.

Given that we are planning to port to Python 3, it makes sense to adopt the Python 3 conventions already using Python 2. That is: raise an error for undefined comparisons.

[Jeroen Demeyer]

Replying to mmezzarobba:

The only thing I really care about is that nonsensical comparisons between Elements raise an exception.

Then why don't you implement exactly that, without making changes to comparisons with non-Elements? That sounds like a good idea to me.

[Marc Mezzarobba]

Replying to jdemeyer:

Then why don't you implement exactly that, without making changes to comparisons with non-Elements? That sounds like a good idea to me.

Because I don't think that's the best option, even if I care less about the other cases.

[Jeroen Demeyer]

Please don't do that, it gives the totally wrong impression that this ticket needs work because there are merge conflicts.

[Julian Rüth]

It would be nice if you could just add to that list instead of just removing my items. Merge conflicts make it hard to see what the proposed changes are doing without being able to click on the branch link, so I think that's an issue that needs work.

So, what are the proposed changes about? Last time I had a look at them I was not unhappy about them but you seemed to disagree. It might not be perfect but don't the proposed changes improve the situation at least?

[Jeroen Demeyer]

It's too long ago. I don't remember.

Regardless, I feel that we should first focus on the "see also" tickets. In particular, #22349 looks like a major problem.

[Jeroen Demeyer]

I'm restoring my branch to see how much progress we made. Setting to needs_review only for patchbot testing, it's not actually ready.

---

New commits:

​e45cf27	Add libffi package
​8ef8033	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​414ca3a

Element richcmp: never use id()

[Jeroen Demeyer]

Oops, that libffi commit shouldn't be there.

[Jeroen Demeyer]

Not that many failed tests:

----------------------------------------------------------------------
sage -t --long --warn-long 54.8 src/sage/schemes/elliptic_curves/height.py  # 1 doctest failed
sage -t --long --warn-long 54.8 src/sage/graphs/generic_graph.py  # 9 doctests failed
sage -t --long --warn-long 54.8 src/sage/symbolic/expression.pyx  # 2 doctests failed
sage -t --long --warn-long 54.8 src/sage/homology/examples.py  # 1 doctest failed
sage -t --long --warn-long 54.8 src/sage/combinat/tutorial.py  # 4 doctests failed
sage -t --long --warn-long 54.8 src/sage/graphs/graph.py  # 2 doctests failed
sage -t --long --warn-long 54.8 src/sage/homology/simplicial_complex.py  # 12 doctests failed
sage -t --long --warn-long 54.8 src/sage/combinat/multiset_partition_into_sets_ordered.py  # 3 doctests failed
sage -t --long --warn-long 54.8 src/sage/rings/valuation/valuation.py  # 6 doctests failed
sage -t --long --warn-long 54.8 src/sage/combinat/finite_state_machine.py  # 4 doctests failed
sage -t --long --warn-long 54.8 src/sage/graphs/digraph_generators.py  # 4 doctests failed
sage -t --long --warn-long 54.8 src/sage/combinat/words/morphism.py  # 5 doctests failed
sage -t --long --warn-long 54.8 src/sage/combinat/words/finite_word.py  # 3 doctests failed
sage -t --long --warn-long 54.8 src/sage/combinat/words/word_generators.py  # 1 doctest failed
sage -t --long --warn-long 54.8 src/sage/categories/algebra_functor.py  # 1 doctest failed
sage -t --long --warn-long 54.8 src/sage/combinat/posets/lattices.py  # 5 doctests failed
sage -t --long --warn-long 54.8 src/sage/structure/formal_sum.py  # 3 doctests failed
sage -t --long --warn-long 54.8 src/sage/combinat/designs/incidence_structures.py  # 15 doctests failed
sage -t --long --warn-long 54.8 src/sage/combinat/set_partition.py  # 3 doctests failed
sage -t --long --warn-long 54.8 src/sage/misc/misc.py  # 3 doctests failed
sage -t --long --warn-long 54.8 src/sage/structure/coerce.pyx  # 1 doctest failed
sage -t --long --warn-long 54.8 src/sage/graphs/schnyder.py  # 4 doctests failed
----------------------------------------------------------------------

Perhaps we should look at those failures and triage them into various tickets.

[Jeroen Demeyer]

I identified quite a few additional issues. I'm not saying that I found all issues (I skimmed semi-quickly over the patchbot report) but surely the majority.

The most serious one is still the graph sorting, which counts for a substantial amount of doctest failures.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​9c92766	Add comparisons and hash for CuspFamily
​bcc0a23	Do not sort terms in FormalSum
​154b615	Sort key as sort_facets parameter of SimplicialComplex
​3930c20	Do not sort in Subsets_s
​d7ece06	Remove pointless comparison doctests in valuations
​d0ad378	AbstractLanguage should work with uncomparable alphabet
​7dda4ac	Use richcmp_item to compare Word_class
​a354dc1	Do not sort points in IncidenceStructure
​a9e0fe6	Merge commit 'bcc0a23bb4a32491f2145ff8412651a326b33a68'; commit '154b61536b55faca6f507c688881570fdc5812f8'; commit '3930c20b0d41c87f5b7ebc5c1ffd07bfcbb18832'; commit 'd7ece0605d390062cf625de4c54608cd05bfc8fa'; commit 'd0ad378c279b0628b84941ac1444c16b198cd7f4'; commit '7dda4ac6209a3b86ee0d042c2aa358d53f1d9f29'; commit 'a354dc129b0085acf88b4b1cbae1d5029218fa61' into t/22029/22029-richcmp
​f680404	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​5ba9405	Do not sort in Subsets_s
​0e9b0ab	Do not sort points in IncidenceStructure
​2466c5f	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​447fe92	Do not sort points in IncidenceStructure
​5ccd507	Do not sort in Subsets_s
​34a2af2	Element richcmp: never use id()

[Jeroen Demeyer]

I looked at the patchbot failures again and I have now identified all issues.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:

​30028e7	Element richcmp: never use id()
​ea22e20	26936: fixing doctests with sortable alphabets
​0cc0a61	26936: improved class documentation
​db81e7d	26936: add example with non sortable alphabet
​3efa9b1	_iterator_weight should not sort objects
​a0f038f	py3: some fix in set_partition (sortable elements only)
​94bc96a	make clear that equality needs a totally ordered set
​4c0cd90	reword as requested
​171f988	same for inequality
​f3aa735	Merge commit 'db81e7dd2f141be4eed6cfcb87fc718ccae9e68c'; commit '3efa9b1ad4154e5f4516d437bfbc56ae47fa9d80'; commit '171f9885ff150378e69de4cdfeea2fb1d6b107ea' into t/22029/22029-richcmp

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​f54c500

Merge commit 'db81e7dd2f141be4eed6cfcb87fc718ccae9e68c'; commit '3efa9b1ad4154e5f4516d437bfbc56ae47fa9d80'; commit '171f9885ff150378e69de4cdfeea2fb1d6b107ea' into t/22029/22029-richcmp

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b4f67ca	Deprecate uniq()
​6b000b9	Merge commit 'b4f67ca8620ffff6cf761abd44fe287a88c5bf13' into t/22029/22029-richcmp
​0240367	trac #27010: save some calls to .vertices()
​3a409b1	Minor doctest fixes for Trac #22029
​ab00c17	Avoid sorting vertices in relabel()
​66d2a8f	Merge commit '0240367bef781fc219655b3bacd60ffd291eb595'; commit '3a409b1929c9a049772cb725aa579a0344dae0b4'; commit 'ab00c175178632d7dd1835bc618fa08bf5253aa8' into t/22029/22029-richcmp

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f830eb9	trac #27009: avoid sorting in method treewidth
​31240a8	Merge commit 'f830eb94a953905c3b6e6540e46e2319fb8a3e41' into t/22029/22029-richcmp

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​70e123b	Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
​d5d7d70	Merge branch 't/27029/avoid_calling_vertices___in_graph_isom_equivalent_non_edge_labeled_graph__' into t/22029/22029-richcmp

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​a88dc2c	Make relabel() of DynkinDiagram more compatible with GenericGraph
​5ec5eb0	Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
​4c75779	Merge commit '5ec5eb0d4dc1a04dd51e216949841933256f7174' into t/22029/22029-richcmp

[Jeroen Demeyer]

I consider this ticket to be essentially finished. We need to wait a bit until all dependencies have been merged and a new Pynac release has been made.

[Marc Mezzarobba]

Replying to jdemeyer:

I consider this ticket to be essentially finished. We need to wait a bit until all dependencies have been merged and a new Pynac release has been made.

This is great! Thank you for working on it.

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​a7eaec9	Avoid sorting vertices in relabel()
​7ed35ed	Minor doctest fixes for Trac #22029
​e3e4a16	Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
​f3890d6	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​b5f1fd6

Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​d55170a	Minor doctest fixes for Trac #22029
​de55397	Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
​815ceab	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​4b3f8d3	Make relabel() of DynkinDiagram more compatible with GenericGraph
​69978b6	Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
​e09ddd2	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​103571f	Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
​2198757	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​02ecd8e	Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
​a0832c0	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​89e7ec2	Avoid calling vertices() in graph_isom_equivalent_non_edge_labeled_graph()
​20b6477	Element richcmp: never use id()

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​86bbcf5	Add Pynac unordered_map patch
​ef01c33	Element richcmp: never use id()

[Jeroen Demeyer]

Green bot!

[Marc Mezzarobba]

Replying to jdemeyer:

Green bot!

Great! Here is a version based on 8.7.beta3 with #27241.

[Marc Mezzarobba]

New commits:

​a6ceab9	pynac-0.7.24 pkg/chksum
​e311ab1	Element richcmp: never use id()

[Marc Mezzarobba]

As for the actual content: I'm happy with this version, and I'm ready to give it positive review once the patchbot comes back green with the new pynac release. I'm still not 100% convinced that the way you are handling non-Elements and coercion failures is optimal, but even if not, it shouldn't be too hard to change later if this turns out to be an issue.

[Marc Mezzarobba]

The tests pass on my box.

[Jeroen Demeyer]

Replying to mmezzarobba:

I'm still not 100% convinced that the way you are handling non-Elements and coercion failures is optimal

What do you mean exactly? I'm open to suggestions for improvement.

What I want is that comparisons involving the coercion model behave just like comparisons in Python 3 should behave. This means: if the objects cannot be compared, raise an error instead of returning some arbitrary value.

[Marc Mezzarobba]

Replying to jdemeyer:

Replying to mmezzarobba:

I'm still not 100% convinced that the way you are handling non-Elements and coercion failures is optimal

What do you mean exactly? I'm open to suggestions for improvement.

We had this discussion two years ago when I started this ticket, and frankly I don't remember all the details. But I think it revolved around the following points:

• Regarding coercion failures, it might be better to raise an error (however inconvenient that would be!)
  • instead of returning False when two Elements with no common parent are compared using ==,
  • and, perhaps more importantly, instead of returning True when they are compared with !=—the additional point to consider in this case being that returning True would be “wrong” if we haven't proved that the elements are different, while many boolean predicates in Sage return False when they can not decide.

• Regarding non-Elements:
  • The coercion framework treats some specific types essentially like Element. We need to be consistent with that, but still allow users to define new types that implement their own comparison logic with Sage elements.
  • richcmp() currently does that by calling tp_richcompare() on the non-Element, instead of returning NotImplemented. I'm not 100% comfortable with this choice. I assume that the goal to get the same behavior under Python 2 and 3, but I'm a bit confused here, because (unless I misunderstood you) you argued against that choice two years ago.

[Jeroen Demeyer]

Replying to mmezzarobba:

• Regarding coercion failures, it might be better to raise an error (however inconvenient that would be!)
  • instead of returning False when two Elements with no common parent are compared using ==

I would argue that, when there is no common parent, elements clearly cannot be equal. This is also consistent with Python 3 where uncomparable objects can still be compared by == and !=:

Python 3.6.3 (default, Mar 13 2018, 19:00:30) 
[GCC 6.4.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 1 == "x"
False

• and, perhaps more importantly, instead of returning True when they are compared with !=—the additional point to consider in this case being that returning True would be “wrong” if we haven't proved that the elements are different

Again, if those elements don't coerce to a common parent, they cannot be equal.

• Regarding non-Elements:
  • The coercion framework treats some specific types essentially like Element. We need to be consistent with that

As far as I know, we are consistent.

but still allow users to define new types that implement their own comparison logic with Sage elements.

• richcmp() currently does that by calling tp_richcompare() on the non-Element, instead of returning NotImplemented.

Exactly.

I'm not 100% comfortable with this choice. I assume that the goal to get the same behavior under Python 2 and 3

Exactly. Returning NotImplemented causes different behavior on Python 2 and Python 3.

I'm a bit confused here, because (unless I misunderstood you) you argued against that choice two years ago.

I don't remember precisely. Anyway, I changed my mind and I'm convinced now that raising an error is the right thing to do.