Opened 9 years ago

Closed 3 years ago

Last modified 3 years ago

#1185 closed defect (fixed)

wrong sorting example for topological-sort

Reported by: Christian Kellermann Owned by:
Priority: major Milestone: 5.3
Component: core libraries Version: 4.9.x
Keywords: Cc:
Estimated difficulty: easy

Description

As found by "WJ" on comp.lang.scheme:

(topological-sort
 '((i am)
   (not trying)
   (confuse the)
   (am trying)
   (trying to)
   (am not)
   (trying the)
   (to confuse)
   (the issue))
  eq?)

 ===>
(not i am trying to confuse the issue)


The correct output is:

(i am not trying to confuse the issue)

Attachments (1)

0001-Fix-1185-Normalize-DAG-passed-to-topological-sort-so.patch (1.7 KB) - added by Moritz Heidkamp 9 years ago.
Here's the patch implementing option 3 as discussed on IRC.

Download all attachments as: .zip

Change History (6)

comment:1 Changed 9 years ago by Moritz Heidkamp

This happens because the dependencies of am are defined twice, one of them clobbering the others. I think we have three options:

  1. Throw an error in that case
  2. Document it as undefined behavior
  3. Concatenate the dependencies

What do you think would be the most reasonable thing?

Changed 9 years ago by Moritz Heidkamp

Here's the patch implementing option 3 as discussed on IRC.

comment:2 Changed 8 years ago by sjamaan

Estimated difficulty: easy

comment:3 Changed 3 years ago by felix winkelmann

Resolution: fixed
Status: newclosed

Pushed in b175ce65fe17c0887ed89f070dc4c16ef95d51f9. Note that I had to change one test result which may be a user-visible change, which I consider acceptable as the new order seems more natural.

comment:4 Changed 3 years ago by sjamaan

Milestone: someday5.3

comment:5 Changed 3 years ago by Mario Domenech Goulart

This fix exposed issues in some eggs:

  • callable-data-structures (fixed)
  • generics (patch submitted)
  • pigeon-hole (patch submitted)
  • r7rs (fixed)
  • xml-rpc (patch submitted)

I'm documenting the status of eggs here so that we don't duplicate work.

Note: See TracTickets for help on using tickets.