search

haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
184 stars 54 forks source link

Fix dom function calculation of dominators. #102

Closed kquick closed 1 year ago

kquick commented 2 years ago

Currently the dom function returns all nodes whether they are reachable or not. This change restricts the dominator search to only those nodes reachable from the provided root.

athas commented 1 year ago

This has broken ShellCheck (https://github.com/koalaman/shellcheck/issues/2677). I'm trying to work out whether ShellCheck was relying on buggy behaviour, or whether the old fgl behaviour was correct.

kquick commented 1 year ago

Is this now resolved via https://github.com/haskell/fgl/commit/99a37390ef492558dfe4b52ef0fad5bac6d18974 or is further work needed?

athas commented 1 year ago

It works, but I am unsure whether the new dom behaviour is a bugfix or a change to intended behaviour. The intention was not to change intentional behaviour.

kquick commented 1 year ago

FWIW, I initiated this change based on working with a different graph library (https://github.com/travitch/haggle) which runs property tests and used FGL as an oracle. With your latest change, I'm able to locally re-enable the dom tests in that library and confirm identical property-testing results from haggle and fgl, which lends additional support to the case that this is a bugfix and the behavior is now correct.

That said, it will be useful to know the effect on shellcheck as well.

athas commented 1 year ago

I also took a quick look at other graph libraries in various languages and they seem to have the same behaviour as fgl after this PR.

Shellcheck can (and has been) adapted to this behaviour fairly easily. Unless someone speaks up, I will keep this new behaviour and consider it a bugfix.

kquick commented 1 year ago

Sounds good. A 5.8.1.1 release would be nice to have for lower-bound dependencies as well when you are comfortable enough with this.