Opened 8 years ago
Last modified 6 years ago
#13374 needs_work defect
Improve identification of arguments to Ring.ideal
Reported by:  nbruin  Owned by:  robertwb 

Priority:  major  Milestone:  sage6.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 )
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)
Change History (20)
Changed 8 years ago by
comment:1 Changed 8 years ago by
 Status changed from new to needs_review
comment:2 Changed 8 years ago by
 Description modified (diff)
comment:3 Changed 8 years ago by
 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 8 years ago by
Could you see whether #12969 fixes it?
comment:5 followup: ↓ 6 Changed 8 years ago by
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/sage5.2.rc0/<ipython console> in <module>() /home/simon/SAGE/prerelease/sage5.2.rc0/local/lib/python2.7/sitepackages/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 ; followup: ↓ 7 Changed 8 years ago by
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 nonlocality 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 8 years ago by
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 tohas_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 argumentwhen 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 8 years ago by
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 followup: ↓ 10 Changed 8 years ago by
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 nonmember 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!).
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 8 years ago by
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 nonexistence of a coercion from first to self should not be cached (because the nonexistence 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 ducktype 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 ; followup: ↓ 12 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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 335 335 elif isinstance(first, (list, tuple, GeneratorType)): 336 336 gens = first 337 337 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] 347 344 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 348 350 if coerce: 349 351 gens = [self(g) for g in gens] 350 352 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 491 491 break 492 492 elif isinstance(first, (list, tuple)): 493 493 gens = first 494 elif self.has_coerce_map_from(first):495 gens = first.gens() # we have a ring as argument494 # elif self.has_coerce_map_from(first): 495 # gens = first.gens() # we have a ring as argument 496 496 else: 497 497 break
(Of course, that patch wouldn't be ready for review).
I get this doctest error:
sage t "devel/sagemain/sage/rings/padics/padic_base_leaves.py" ********************************************************************** File "/mnt/local/king/SAGE/prereleases/sage5.3.beta2/devel/sagemain/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 8 years ago by
 Cc jpflori added
comment:15 Changed 7 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:16 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:17 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:18 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:19 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
First try