Improve identification of arguments to Ring.ideal

[nbruin]

Currently, ZZ.ideal(3) will call ZZ.has_coerce_map_from(3) (and get back False of course) to see if the argument is a ring that might be able to generate an ideal in R. This is a problem, because has_coerce_map_from caches its result and 3 is not weakreffable. That means a strong reference to 3 is stored on ZZ, preventing it from ever being deleted. These things pile up and contaminate the cache. A classic example of DON'T DO THAT. The solution is to first test if the argument is appropriate to be fed into has_coerce_map_from.

An alternative is to delete the test completely! I'm no sure the relevant branch ever does something useful.

This issue came up in handling another ticket. See ​#715, comment 198.

[nbruin]

First try

[nbruin]

These lines were introduced in #11068. This ticket introduces the same test in a bunch of other places. Probably Simon King can comment on the wisdom of keeping/removing this use of has_coerce_map_from and/or workarounds for it. Preliminary tests suggest that removing the whole case at least from Ring.ideal doesn't break any doctests.

[SimonKing]

Could you see whether #12969 fixes it?

[SimonKing]

Even if #12969 fixes the resulting leak (I am not sure if it does, perhaps not), I believe that your patch has the potential to fix an independent problem:

sage: ZZ.ideal(int)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)

/home/simon/SAGE/prerelease/sage-5.2.rc0/<ipython console> in <module>()

/home/simon/SAGE/prerelease/sage-5.2.rc0/local/lib/python2.7/site-packages/sage/rings/ring.so in sage.rings.ring.Ring.ideal (sage/rings/ring.c:4769)()

AttributeError: type object 'int' has no attribute 'gens'

That is because

sage: ZZ.has_coerce_map_from(int)
True

but

sage: int in Rings()
False

With your patch, the error would be

TypeError: unable to coerce <type 'type'> to an integer

I think it would be a good idea to catch the type error internally and raise a type error with a more meaningful error message stating which arguments are accepted by ideal().

Since the patchbot gives a green light (or green blob), I tend to give it a positive review, but would like to add a referee patch.

[nbruin]

Replying to SimonKing:

Even if #12969 fixes the resulting leak (I am not sure if it does, perhaps not)

No, I tested it on >= 5.2.

Since the patchbot gives a green light (or green blob), I tend to give it a positive review, but would like to add a referee patch.

Absolutely, go ahead. And please address the other instances of this type of test in #11068 as well (just grep for has_coerce_map_from in the patch there). Perhaps we should add some documentation to has_coerce_map_from as well, warning against frivolous feeding of the cache. This is a general issue: People should be a bit more careful calling caching functions. Things like

# should be quick, because this should easily fit in the L2 CPU cache.
for i in srange(10^9):
   if is_square(caching_function(i)):
      print "Wow, I did not expect to find a square value for that thing; i=",i
      break

don't go so well. Memory leaks also hurt performance, due to OS overhead and non-locality of working set.

And what do you think about the alternative of simply deleting the lines:

    elif self.has_coerce_map_from(first): 
        gens = first.gens() # we have a ring as argument

when I tried it didn't break any doctests...

[SimonKing]

Replying to nbruin:

Absolutely, go ahead. And please address the other instances of this type of test in #11068 as well (just grep for has_coerce_map_from in the patch there). Perhaps we should add some documentation to has_coerce_map_from as well, warning against frivolous feeding of the cache.

I think there is a better (i.e., more conceptual) solution: R.coerce_map_from(S) should first test whether S is a parent or a type. If it is, then the current code should be used to detect and cache a coercion (we do want R.coerce_map_from(int) works and is cached). If it is not, then R.coerce_map_from(S) can simply return "None", without caching.

The same, by the way, should hold for convert_map_from.

And what do you think about the alternative of simply deleting the lines:

    elif self.has_coerce_map_from(first): 
        gens = first.gens() # we have a ring as argument

when I tried it didn't break any doctests...

That indicates we should add a doctest demonstrating the use of R.ideal(S) where S is a ring that coerces into R. Because that is what the lines you're citing implement.

What does that mean for the patch here? self.has_coerce_map_from(first) is meant as some kind of duck typing for rings. But it fails, as we can see with ZZ.ideal(int). Hence, your idea to test first in Rings() makes sense, independent of the memory leak problem.

So, I think we should keep this ticket, and I will create a patch for coerce_map_from on a different ticket.

[SimonKing]

I wonder if we really want the following:

sage: ZZ.convert_map_from(1)
Conversion map:
  From: Set of Python objects of 
  To:   Integer Ring

"Set of Python objects of". Of what? Why is there a map?

But I really think that this belongs to the "to be created" ticket I mentioned.

[nbruin]

I still doubt the validity of the test at all. Is the existence of a coercion map a good way of checking whether it's safe to call gens() on the object?

If I'm not mistaken, this test is part of a loop in Ring.ideal to flatten and convert its arguments into a finite list of elements that supposedly can be used to generate the ideal asked for. The coercion (or its failure) will happen once the ideal gets constructed. In this part, we only need to establish whether it's reasonable to expect that the ideal generated by S is the same as that generated by S.gens(). So shouldn't it be

    if first in AdditiveMagmasWithGens():
        gens= first.gens()

or something like that? Of course, this doesn't rule out that calling gens might be very expensive if it actually needs to compute generators:

R=Zmod(next_prime(10^100)*next_prime(10^102))
exp=exponentiationpairing(R.multiplicative_group(),ZZ)
K=exp.right_kernel() #place holder object with fast non-member detection
ZZ.ideal(K)

but hey, that code doesn't exist anyway and we can't protect the user against everything.

If our AdditiveMagma is actually VectorSpace(RR,17) we'll get an error because the elements of gens cannot be coerced into the ring to generate an ideal there (or they can!).

[SimonKing]

Replying to nbruin:

I still doubt the validity of the test at all. Is the existence of a coercion map a good way of checking whether it's safe to call gens() on the object?

No!

In fact, there is a coerce map from the type int to any ring, but the type int of course has no gens().

If I'm not mistaken, this test is part of a loop in Ring.ideal to flatten and convert its arguments into a finite list of elements that supposedly can be used to generate the ideal asked for.

Correct.

So shouldn't it be

    if first in AdditiveMagmasWithGens():
        gens= first.gens()

I am still not sure. Perhaps we should really ask ourselves what is really needed in the code.

We need that "first" has a gens() method, which returns a list of elements, and we need that the elements coerce (not just convert) into self. It is actually not needed that "first" is a ring or an additive magma, and being a ring does not necessary mean that "gens" exists.

So, what you think about the following approach:

• If "first" is an element, not a parent, then the non-existence of a coercion from first to self should not be cached (because the non-existence is clear). I think the fix should be in Parent.coerce_map_from(), not in Ring.ideal(). Hence, leave that to #13378.
• We need to duck-type the gens method of first. Of course, we can not ensure that it will give the answer quickly, and you are right that we can't protect the user from it.
• We need that "first" coerces into self.

Hence, the code should be like this:

if hasattr(first,"gens"):
    if self.has_coerce_map_from(first): # which should not cache too eagerly
        first = [self(x) for x in self.gens()]
if isinstance(first, (list,tuple,Sequence, <you name it>)):
    <some code that creates an ideal>

What do you think of that?

[nbruin]

Hence, the code should be like this:

if hasattr(first,"gens"):
    if self.has_coerce_map_from(first): # which should not cache too eagerly
        first = [self(x) for x in self.gens()]
if isinstance(first, (list,tuple,Sequence, <you name it>)):
    <some code that creates an ideal>

I think that, without a concrete use case where it's obvious people would actually be stuffing this kind of object into Ring.ideal (possibly indirectly), I would just not support it at all. Anybody sane would be extremely sceptical about letting a computer algebra system make deductions for them if that can be reasonably avoided. If I were to explicitly construct an ideal from S.gens(), I would do

ZZ.ideal( ZZ(g) for g in S.gens() )

rather than

R.ideal(S)

Funnily enough, the former currently fails with

TypeError: unable to coerce <type 'generator'> to an integer

I don't think this branch is hit by the quite believable

sage: ZZ['x']*ZZ.ideal(3)
Principal ideal (3) of Univariate Polynomial Ring in x over Integer Ring

In my experience, you can put a lot of work into being extremely liberal in accepting input in all kinds of forms, only to find that people only use the most basic case anyway.

[SimonKing]

Replying to nbruin:

I think that, without a concrete use case where it's obvious people would actually be stuffing this kind of object into Ring.ideal (possibly indirectly), I would just not support it at all.

Did you test whether stuff still works?

[SimonKing]

I tried to remove the support for "R.ideal(S)" with a ring S. The patch:

sage/categories/rings.py

@@ -335 +335 @@
                     elif isinstance(first, (list, tuple, GeneratorType)):
                         gens = first
                     else:
-                        try:
-                            if self.has_coerce_map_from(first):
-                                gens = first.gens() # we have a ring as argument
-                            elif hasattr(first,'parent'):
-                                gens = [first]
-                            else:
-                                raise ArithmeticError, "There is no coercion from %s to %s"%(first,self)
-                        except TypeError: # first may be a ring element
-                            pass
+#                        try:
+#                            if self.has_coerce_map_from(first):
+#                                gens = first.gens() # we have a ring as argument
+#                            el
+                        if hasattr(first,'parent'):
+                            gens = [first]
                         break
+#                        else:
+#                            raise ArithmeticError, "There is no coercion from %s to %s"%(first,self)
+#                        except TypeError: # first may be a ring element
+#                            pass
+#                        break
             if coerce:
                 gens = [self(g) for g in gens]
             from sage.categories.principal_ideal_domains import PrincipalIdealDomains

sage/rings/ring.pyx

@@ -491 +491 @@
                 break
             elif isinstance(first, (list, tuple)):
                 gens = first
-            elif self.has_coerce_map_from(first):
-                gens = first.gens() # we have a ring as argument
+#            elif self.has_coerce_map_from(first):
+#                gens = first.gens() # we have a ring as argument
             else:
                 break

(Of course, that patch wouldn't be ready for review).

I get this doctest error:

sage -t  "devel/sage-main/sage/rings/padics/padic_base_leaves.py"
**********************************************************************
File "/mnt/local/king/SAGE/prereleases/sage-5.3.beta2/devel/sage-main/sage/rings/padics/padic_base_leaves.py", line 482:
    sage: K.has_coerce_map_from(Zp(17,40))
Expected:
    True
Got:
    False

So, the question is whether we can get this coerce map without support for "R.ideal(S)", S a ring.