Opened 8 years ago

Closed 8 years ago

Last modified 8 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: 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 8 years ago.
proposed patch

Download all attachments as: .zip

Change History (5)

Changed 8 years ago by int-e

proposed patch

comment:1 Changed 8 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 8 years ago by int-e

  • Resolution set to fixed
  • Status changed from new to closed

Martin Erwig kindly applied the patch.

comment:3 Changed 8 years ago by simonmar

  • Architecture changed from Multiple to Unknown/Multiple

comment:4 Changed 8 years ago by simonmar

  • Operating System changed from Multiple to Unknown/Multiple
Note: See TracTickets for help on using tickets.