[Haskell-cafe] Wrong Answer Computing Graph Dominators

[Bertram Felgenhauer]

Denis Bueno wrote:
> I'm using the Data.Graph.Inductive.Query.Dominators library
> (http://haskell.org/ghc/docs/latest/html/libraries/fgl/Data-Graph-Inductive-Query-Dominators.html)
> with GHC 6.8.2.
>  The library is a bit spare on comments, so I may or may not be using
> it correctly.
> 
[snip]
> But what I am getting is:
>    --> uips = [-9,20]
>    --> domConfl = [2,-9,20]
>    --> domAssigned = [-2,-9,-12,20]
>    --> lastd = 20
> 
> But -9 is not a dominator for 2, since 20,-7,8,6,2 is a path from 20
> to 2 that does not touch 9.  -9 is also not a dominator for -2, since
> 20,-7,8,6,-2 is a path from 20 to -2 not touching 9.
> 
> Am I missing something?

No. Data.Graph.Inductive.Query.Dominators is just buggy.

1) domr is meant to find a fixed point of builddoms by iteratively
   applying builddoms, but in fact it calls builddoms at most twice.
2) the code doesn't handle nodes with no predecessors correctly.

Here's a quick fix:

diff -rN -u old-fgl/Data/Graph/Inductive/Query/Dominators.hs new-fgl/Data/Graph/Inductive/Query/Dominators.hs
--- old-fgl/Data/Graph/Inductive/Query/Dominators.hs    2008-04-16 20:13:35.000000000 +0200
+++ new-fgl/Data/Graph/Inductive/Query/Dominators.hs    2008-04-16 20:13:35.000000000 +0200
@@ -18,13 +18,13 @@
 builddoms :: DomSets -> [Node] -> DomSets
 builddoms ds []     = ds
 builddoms ds (v:vs) = builddoms ((fs++[(n,p,sort(n:idv))])++(tail rs)) vs
-                      where idv     = intersection (getdomv p ds)
-                            (n,p,_) = head rs
+                      where idv     = intersection ((q \\ [n]):getdomv p ds)
+                            (n,p,q) = head rs
                             (fs,rs) = span (\(x,_,_)->x/=v) ds
 
 domr :: DomSets -> [Node] -> DomSets
 domr ds vs|xs == ds  = ds
-          |otherwise = builddoms xs vs
+          |otherwise = domr xs vs
            where xs = (builddoms ds vs)
 
 {-|

Bertram