Opened 7 years ago

Last modified 5 years ago

#13374 needs_work defect

Improve identification of arguments to Ring.ideal

Reported by: nbruin Owned by: robertwb
Priority: major Milestone: sage-6.4
Component: coercion Keywords:
Cc: SimonKing, jpflori Merged in:
Authors: Nils Bruin Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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.

Attachments (1)

trac_13374-test-before-checking-coercion.patch (799 bytes) - added by nbruin 7 years ago.
First try

Download all attachments as: .zip

Change History (20)

Changed 7 years ago by nbruin

First try

comment:1 Changed 7 years ago by nbruin

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by nbruin

  • Description modified (diff)

comment:3 Changed 7 years ago by nbruin

  • Cc SimonKing added

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.

comment:4 Changed 7 years ago by SimonKing

Could you see whether #12969 fixes it?

comment:5 follow-up: Changed 7 years ago by 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.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 7 years ago by 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...

comment:7 in reply to: ↑ 6 Changed 7 years ago by 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.

comment:8 Changed 7 years ago by 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.

comment:9 follow-up: Changed 7 years ago by 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!).

Last edited 7 years ago by nbruin (previous) (diff)

comment:10 in reply to: ↑ 9 ; follow-up: Changed 7 years ago by 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?

comment:11 in reply to: ↑ 10 ; follow-up: Changed 7 years ago by 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.

comment:12 in reply to: ↑ 11 Changed 7 years ago by 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?

comment:13 Changed 7 years ago by SimonKing

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

  • sage/categories/rings.py

    diff --git a/sage/categories/rings.py b/sage/categories/rings.py
    a b  
    335335                    elif isinstance(first, (list, tuple, GeneratorType)):
    336336                        gens = first
    337337                    else:
    338                         try:
    339                             if self.has_coerce_map_from(first):
    340                                 gens = first.gens() # we have a ring as argument
    341                             elif hasattr(first,'parent'):
    342                                 gens = [first]
    343                             else:
    344                                 raise ArithmeticError, "There is no coercion from %s to %s"%(first,self)
    345                         except TypeError: # first may be a ring element
    346                             pass
     338#                        try:
     339#                            if self.has_coerce_map_from(first):
     340#                                gens = first.gens() # we have a ring as argument
     341#                            el
     342                        if hasattr(first,'parent'):
     343                            gens = [first]
    347344                        break
     345#                        else:
     346#                            raise ArithmeticError, "There is no coercion from %s to %s"%(first,self)
     347#                        except TypeError: # first may be a ring element
     348#                            pass
     349#                        break
    348350            if coerce:
    349351                gens = [self(g) for g in gens]
    350352            from sage.categories.principal_ideal_domains import PrincipalIdealDomains
  • sage/rings/ring.pyx

    diff --git a/sage/rings/ring.pyx b/sage/rings/ring.pyx
    a b  
    491491                break
    492492            elif isinstance(first, (list, tuple)):
    493493                gens = first
    494             elif self.has_coerce_map_from(first):
    495                 gens = first.gens() # we have a ring as argument
     494#            elif self.has_coerce_map_from(first):
     495#                gens = first.gens() # we have a ring as argument
    496496            else:
    497497                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.

comment:14 Changed 7 years ago by jpflori

  • Cc jpflori added

comment:15 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:16 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:17 Changed 6 years ago by rws

  • Status changed from needs_review to needs_work

comment:18 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:19 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.