Opened 7 years ago

Closed 7 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)

trac_7420-fix-infinite-coercion-discovery-loop.patch (3.1 KB) - added by nthiery 7 years ago.
trac_7420-fix-infinite-coercion-discovery-loop-2.patch (3.8 KB) - added by nthiery 7 years ago.
This is a variant of the previous patch, using register_pair
log (34.8 KB) - added by nthiery 7 years ago.
Log showing a *long* conversion path

Download all attachments as: .zip

Change History (13)

comment:1 Changed 7 years ago by nthiery

  • Cc robertwb added
  • Status changed from new to needs_review

I reviewed the change, and it looks good.

Robert: please double check; I don't guarantee that all the invariants are preserved.

comment:2 Changed 7 years ago by mhansen

Another option is to wrap that coerce_map_from call in a _register_pair try/except block.

comment:3 follow-up: Changed 7 years ago by robertwb

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: 
                        ...

Changed 7 years ago by nthiery

This is a variant of the previous patch, using register_pair

comment:4 in reply to: ↑ 3 ; follow-up: Changed 7 years ago by nthiery

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.

Changed 7 years ago by nthiery

Log showing a *long* conversion path

comment:5 in reply to: ↑ 4 Changed 7 years ago by nthiery

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 7 years ago by was

  • Milestone changed from sage-4.3 to sage-4.2.1

comment:7 Changed 7 years ago by mhansen

  • 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 7 years ago by robertwb

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 7 years ago by mhansen

  • Status changed from needs_review to positive_review

I'll merge the first patch, and then look into a better solution.

comment:10 Changed 7 years ago by mhansen

  • Merged in set to sage-4.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.