Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#2227 closed proposal (fixed)

(fgl) reimplement Data.Graph.Inductive.Query.Dominators

Reported by: int-e Owned by:
Priority: normal Milestone:
Component: libraries (other) Version: 6.9
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


As pointed out at ff., Data.Graph.Inductive.Query.Dominators.dom is buggy. Furthermore, it's slow, so instead of submitting the quick fix from that thread, I've rewritten the module from scratch using a more efficient algorithm.

The algorithm works by calculating the immediate dominators of the graph nodes first, so the patch also adds a function that returns those. It should be handy for flow graph analysis.

Attachments (1)

dominators.patch (7.4 KB) - added by int-e 9 years ago.
proposed patch

Download all attachments as: .zip

Change History (5)

Changed 9 years ago by int-e

Attachment: dominators.patch added

proposed patch

comment:1 Changed 9 years ago by int-e

FGL is not a core package (but an extra package shipped with ghc), so the library submission guidelines don't apply.

As per Don Stewart's suggestion on libraries@… I've contacted Martin Erwig about this.

comment:2 Changed 9 years ago by int-e

Resolution: fixed
Status: newclosed

Martin Erwig kindly applied the patch.

comment:3 Changed 9 years ago by simonmar

Architecture: MultipleUnknown/Multiple

comment:4 Changed 9 years ago by simonmar

Operating System: MultipleUnknown/Multiple
Note: See TracTickets for help on using tickets.