Mojom frontend: An algorithm for detecting ill-founded nodes in a graph.

Mojom frontend: An algorithm for detecting ill-founded nodes in a graph.

We add a utility containing an algorithm for detecting ill-founded nodes in a two-sorted directed graph.

See the paper "Well-Founded Two-Sorted Directed Graphs" (https://goo.gl/ipxFKu)
for background and detailed definitions. The proofs still need to be added.

The intended use of this is to detect unavoidable cycles in the Mojom type graph for as described in
https://github.com/domokit/mojo/issues/694

BUG=#694
R=azani@chromium.org

Committed: https://chromium.googlesource.com/external/mojo/+/4b3447da56085b53e0c928da30268f5ad8d93262

[rudominer, 2016-04-22 16:03:58]

Description was changed from

==========
Mojom frontend: An algorithm for testing for ill-founded nodes in a graph.

BUG=
==========

to

==========
Mojom frontend: An algorithm for detecting ill-founded nodes in a graph.

We add a utility containing an algorithm for detecting ill-founded nodes in a
two-sorted directed graph.

See the paper "Well-Founded Two-Sorted Directed Graphs" (https://goo.gl/ipxFKu) 
for background and detailed definitions. The proofs still need to be added.

The intended use of this is to detect unavoidable cycles in the Mojom type graph
for as described in
https://github.com/domokit/mojo/issues/694

BUG=#694
==========

[rudominer, 2016-04-22 16:07:57]

rudominer@chromium.org changed reviewers:
+ azani@chromium.org

[rudominer, 2016-04-22 16:07:58]

Hi alex, ptal.

[azani, 2016-04-22 18:37:15]

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
File mojom/mojom_parser/utils/wellfounded_graphs.go (right):

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:322: nextFoundationSet :=
MakeNodeSet()
Alternatively, you could add a Pop() method on NodeSet that returns an arbitrary
member of the set and just Pop a node each iteration until foundationSet is
empty. I think that might be slightly more readable.

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:350: // meaning we start from the
least possible node and follow edges to the least possible
"least possible node" is ambiguous.

Also, I wonder if you might want to always return a circle first. Ultimately, we
want to tell the user: take this circle and make it a square. So maybe the
circle should be highlighted/made easy to access.

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:354: // program exits with a
cycle descritpion allowing the user to fix the ill-foundedness.
s/descritpion/description

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:355: func (finder *cycleFinder)
findKnownCycle(nodeHolder *nodeHolder) *CycleDescription {
Maybe rename findKnownIllFoundedCycle.

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:369: panic("Should not get
here.")
Maybe:

"Could not find a known ill-founded cycle. That should not happen."

[rudominer, 2016-04-23 01:22:30]

ptal

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
File mojom/mojom_parser/utils/wellfounded_graphs.go (right):

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:322: nextFoundationSet :=
MakeNodeSet()
On 2016/04/22 18:37:14, azani wrote:
> Alternatively, you could add a Pop() method on NodeSet that returns an
arbitrary
> member of the set and just Pop a node each iteration until foundationSet is
> empty. I think that might be slightly more readable.

Done.

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:350: // meaning we start from the
least possible node and follow edges to the least possible
On 2016/04/22 18:37:14, azani wrote:
> "least possible node" is ambiguous.
Done
> 
> Also, I wonder if you might want to always return a circle first. Ultimately,
we
> want to tell the user: take this circle and make it a square. So maybe the
> circle should be highlighted/made easy to access.
Why do you think we ultimately want to tell the user to turn his struct into a
union? There are multiple ways to avoid the ill-foundedness. Also (in the
abstract setting at least) it is possible for a graph containing only square
nodes to be ill-founded.

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:354: // program exits with a
cycle descritpion allowing the user to fix the ill-foundedness.
On 2016/04/22 18:37:14, azani wrote:
> s/descritpion/description

Done.

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:355: func (finder *cycleFinder)
findKnownCycle(nodeHolder *nodeHolder) *CycleDescription {
On 2016/04/22 18:37:14, azani wrote:
> Maybe rename findKnownIllFoundedCycle.

Done.

https://codereview.chromium.org/1908273003/diff/1/mojom/mojom_parser/utils/we...
mojom/mojom_parser/utils/wellfounded_graphs.go:369: panic("Should not get
here.")
On 2016/04/22 18:37:14, azani wrote:
> Maybe:
> 
> "Could not find a known ill-founded cycle. That should not happen."

Done.

[azani, 2016-04-25 16:40:29]

lgtm

[rudominer, 2016-04-25 17:06:47]

Description was changed from

==========
Mojom frontend: An algorithm for detecting ill-founded nodes in a graph.

We add a utility containing an algorithm for detecting ill-founded nodes in a
two-sorted directed graph.

See the paper "Well-Founded Two-Sorted Directed Graphs" (https://goo.gl/ipxFKu) 
for background and detailed definitions. The proofs still need to be added.

The intended use of this is to detect unavoidable cycles in the Mojom type graph
for as described in
https://github.com/domokit/mojo/issues/694

BUG=#694
==========

to

==========
Mojom frontend: An algorithm for detecting ill-founded nodes in a graph.

We add a utility containing an algorithm for detecting ill-founded nodes in a
two-sorted directed graph.

See the paper "Well-Founded Two-Sorted Directed Graphs" (https://goo.gl/ipxFKu)
for background and detailed definitions. The proofs still need to be added.

The intended use of this is to detect unavoidable cycles in the Mojom type graph
for as described in
https://github.com/domokit/mojo/issues/694

BUG=#694
R=azani@chromium.org

Committed:
https://chromium.googlesource.com/external/mojo/+/4b3447da56085b53e0c928da302...
==========

[rudominer, 2016-04-25 17:06:48]

Committed patchset #2 (id:20001) manually as
4b3447da56085b53e0c928da30268f5ad8d93262 (presubmit successful).