Make RecursivelyEnumeratedSet_forest a subclass of RecursivelyEnumeratedSet_generic

[seblabbe]

As a follow up of #16351, we integrate the class RecursivelyEnumeratedSet_forest as a subclass of RecursivelyEnumeratedSet_generic implementing the following change:

-class RecursivelyEnumeratedSet_forest(Parent):
+class RecursivelyEnumeratedSet_forest(RecursivelyEnumeratedSet_generic):

and consequential changes.

I was hoping this to be enough to activate few methods like to_digraph from the generic class that I like to use but are currently not available for the forest type. But unfortunately, the implementation of breadth first search for forest type does not yet take into account the max_depth argument. That will be dealt in another ticket.

CC: @tscrim

Component: combinatorics

Author: Sébastien Labbé

Branch/Commit: u/slabbe/30238 @ 7b65a95

Issue created by migration from https://trac.sagemath.org/ticket/30238

[seblabbe]

Commit: d180dc5

[seblabbe]

Branch: u/slabbe/30238

[seblabbe]

New commits:

2b310e8	first change
d180dc5	30238:Make RecursivelyEnumeratedSet_forest a subclass of RecursivelyEnumeratedSet_generic

[seblabbe]

comment:2

Note: I am changing the ordering of the input of the init method of RecursivelyEnumeratedSet_forest to match the one of RecursivelyEnumeratedSet_generic. This might break code using RecursivelyEnumeratedSet_forest if such code exists. One option is to make this ticket less intrusive by preserving the previous ordering for the init of RecursivelyEnumeratedSet_forest.

This is transparent for the code based on the function RecursivelyEnumeratedSet. The problem was only if people were using directly RecursivelyEnumeratedSet_forest.

[mkoeppe]

comment:3

patchbot indicates doctest failures

[seblabbe]

comment:4

ok, I will work on that.

[sagetrac-git]

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

41aaa0a	30238: fix pycodestyle in map_reduce.py
cc0b7ae	30238: adapt sage library code with the algorithm->enumeration change

[sagetrac-git]

Changed commit from d180dc5 to cc0b7ae

[seblabbe]

comment:6

I am changing the status to needs review just to see what the patchbot says. Locally, I still have at least the following issues, but I did not tested the whole library.

----------------------------------------------------------------------
sage -t --random-seed=0 combinat/subsets_pairwise.py  # 1 doctest failed
sage -t --random-seed=0 combinat/posets/hasse_diagram.py  # 2 doctests failed
----------------------------------------------------------------------   

[seblabbe]

comment:7

I will need help to fix the above issue. Here is how to reproduce the error:

sage: from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets
sage: def predicate(x,y): return gcd(x,y) == 1
sage: P = PairwiseCompatibleSubsets( [4,5,6,8,9], predicate); P
An enumerated set with a forest structure
sage: import __main__; __main__.predicate = predicate
sage: TestSuite(P).run()
Failure in _test_pickling:
...
Traceback (most recent call last):
...
TypeError: classname(=PairwiseCompatibleSubsets_with_category) does not start 
with RecursivelyEnumeratedSet but 
isinstance(self, RecursivelyEnumeratedSet_generic) returns True
------------------------------------------------------------
The following tests failed: _test_pickling

This is due to the fact that a __reduce__ method exists in the class RecursivelyEnumeratedSet_generic which is now used by RecursivelyEnumeratedSet_forest. But the current __reduce__ method is not able to detect properly that self is an instance of RecursivelyEnumeratedSet_forest when the class is a class derivated from RecursivelyEnumeratedSet_forest. Testing classname.startswith('RecursivelyEnumeratedSet_forest') just does not work if the class name is PairwiseCompatibleSubsets_with_category for instance.

Replacing the code based on the name of the class by hasattr(self, 'map_reduce') or more naturally by isinstance(self, RecursivelyEnumeratedSet_forest) does not work because it gives a maximum recursion depth exceeded error:

diff --git a/src/sage/sets/recursively_enumerated_set.pyx b/src/sage/sets/recursively_enumerated_set.pyx
index 2ca2dde..b2f5455 100644
--- a/src/sage/sets/recursively_enumerated_set.pyx
+++ b/src/sage/sets/recursively_enumerated_set.pyx
@@ -539,6 +539,14 @@ cdef class RecursivelyEnumeratedSet_generic(Parent):
             struct = 'forest'
         elif classname.startswith('RecursivelyEnumeratedSet_generic'):
             struct = None
+        # this creates the following error
+        # RecursionError: maximum recursion depth exceeded while calling a Python object
+        #elif hasattr(self, 'map_reduce'):
+        #    struct = 'forest'
+        # this creates the following error
+        # RecursionError: maximum recursion depth exceeded while calling a Python object
+        #elif isinstance(self, RecursivelyEnumeratedSet_forest):
+        #    struct = 'forest'
         else:
             A = isinstance(self, RecursivelyEnumeratedSet_generic)
             raise TypeError("classname(={}) does not start with"

I guess that code is based on classname to avoid that RecursionError. But I don't understand where the RecursionError comes from. Travis do you know?

[sagetrac-git]

Changed commit from cc0b7ae to df88874

[sagetrac-git]

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

df88874

30238:using isinstance in __reduce__

[seblabbe]

comment:9

I updated __reduce__ to use isinstance instead which is more robust.

The next step is to fix the following Recursion error which I still do not understand:

sage: from sage.combinat.subsets_pairwise import PairwiseCompatibleSubsets
sage: def predicate(x,y): return gcd(x,y) == 1
sage: P = PairwiseCompatibleSubsets( [4,5,6,8,9], predicate); P
An enumerated set with a forest structure
sage: dumps(P)
Traceback (most recent call last):
...
RecursionError: maximum recursion depth exceeded while calling a Python object

[videlec]

comment:10

It appears that the error comes from the reduction of the .post_process. When the latter is a method then there is a recursive call. A minimal example is

sage: class A: 
....:     def a(self): pass 
....:     def __reduce__(self): 
....:         return (A, (self.a,))                                                                                                                                                                                 
sage: import pickle                                                                                                                                                                                                 
sage: pickle.dumps(A())                                                                                                                                                                                             
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-4-c96af998f575> in <module>
----> 1 pickle.dumps(A())

RecursionError: maximum recursion depth exceeded

[sagetrac-git]

Changed commit from df88874 to 3192a9e

[sagetrac-git]

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

3192a9e

30238:fixing the RecursionError

[seblabbe]

comment:12

Thank you Vincent. So, I managed to fix the Recursion error. Now, the same doctests fail for a different reason. I will work on that later.

One feature of RecursivelyEnumeratedSet_forest is that you can inherit from this class, define your own children and post_process method and it will work (even if you don't provide them in the init). The fact that RecursivelyEnumeratedSet_generic provides a __reduce__ method, I think it forces the classes inheriting from RecursivelyEnumeratedSet_forest to also overwrite the __reduce__ method. Why does RecursivelyEnumeratedSet_generic need a __reduce__ method in the first place?

[sagetrac-git]

Changed commit from 3192a9e to 7b65a95

[sagetrac-git]

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

7b65a95

30238:fixing one doctest

[tscrim]

comment:15

Replying to @seblabbe:

One feature of RecursivelyEnumeratedSet_forest is that you can inherit from this class, define your own children and post_process method and it will work (even if you don't provide them in the init). The fact that RecursivelyEnumeratedSet_generic provides a __reduce__ method, I think it forces the classes inheriting from RecursivelyEnumeratedSet_forest to also overwrite the __reduce__ method. Why does RecursivelyEnumeratedSet_generic need a __reduce__ method in the first place?

My guess is so that it pickles well when used to build other objects; e.g., as the basis for a CombinatorialFreeModule.

[mkoeppe]

comment:17

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

comment:18

Setting a new milestone for this ticket based on a cursory review.