Opened 9 years ago
Closed 9 years ago
#7420 closed defect (fixed)
Fix uncaught infinite loop in coercion discovery
Reported by: | nthiery | Owned by: | mhansen |
---|---|---|---|
Priority: | blocker | Milestone: | sage-4.3 |
Component: | coercion | Keywords: | coercion |
Cc: | sage-combinat, robertwb | Merged in: | sage-4.3.alpha0 |
Authors: | Mike Hansen | Reviewers: | Nicolas M. Thiéry, Robert Bradshaw |
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
#5597 or #5598 introduced a potential infinite loop (and segfault) upon coercion discovery on a cyclic graph. The first occurence of such a graph was with the newly refactored symmetric functions.
The attached patch fixes this. By the way, it uses a dictionary rather than a list to hold the marks used (register_pair) to detect cycles.
The category patches #5981 depend on this!!!
Attachments (3)
Change History (13)
Changed 9 years ago by
comment:1 Changed 9 years ago by
- Cc robertwb added
- Status changed from new to needs_review
comment:2 Changed 9 years ago by
Another option is to wrap that coerce_map_from call in a _register_pair try/except block.
comment:3 follow-up: ↓ 4 Changed 9 years ago by
Yes, calling _register_pair would work here, even a helper is_registered function might be better than using _coerce_test_dict directly.
Also, instead of
connection = None if EltPair(mor._domain, S, "coerce") not in _coerce_test_dict: connecting = mor._domain.coerce_map_from(S) if connecting is not None:
it might be clearer to do
if EltPair(mor._domain, S, "coerce") not in _coerce_test_dict: connecting = mor._domain.coerce_map_from(S) if connecting is not None: ...
comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 9 years ago by
Replying to robertwb:
Yes, calling _register_pair would work here
I gave it a shot, and this works almost fine: all sage tests pass; except that for jack polynomials. Looking at it, it appears that the coercion model is picking a path which is *really* far from the shortest (see the attached log). The previous version was doing reasonably. This sounds like a pure piece of luck though, since in both cases, the strategy seems to be depth first search + limited selection among the first conversions found.
Robert, Mike: from here, I see two options:
- Either you spot something stupid I did in the second version of the patch, and then we go for it after fixing it.
- Or we go for the first version of the patch for the moment (after applying Robert's suggestion for better indentation)
In both cases, after the category patches are in, we should definitely rewrite the coercion lookup to use a breath first search.
comment:5 in reply to: ↑ 4 Changed 9 years ago by
I should mention: the error appearing in the log comes from the having the coercion go through jack polynomials at t=-1; apparently, the scalar product is then non positive, which causes the error. I have to check the literature. Maybe we should forbid t=-1, or at least not declare the corresponding broken coercions.
comment:6 Changed 9 years ago by
- Milestone changed from sage-4.3 to sage-4.2.1
comment:7 Changed 9 years ago by
- Milestone changed from sage-4.2.1 to sage-4.3
I'm going to move this to 4.3 where it's more relevant.
comment:8 Changed 9 years ago by
I'd say at this point go for the first version of the patch, but with an eye towards improving things in the multiple paths case. (A breath first search sounds like a good idea, but could be more expensive if paths "all the way down" have already been explored. Also, there's the notion of assigning a cost to a morphism which has not been exploited.)
comment:9 Changed 9 years ago by
- Status changed from needs_review to positive_review
I'll merge the first patch, and then look into a better solution.
comment:10 Changed 9 years ago by
- Merged in set to sage-4.3.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
I reviewed the change, and it looks good.
Robert: please double check; I don't guarantee that all the invariants are preserved.