Mojom frontend: Detect Ill-founded Types

Mojom frontend: Detect Ill-founded Types

This patch adds the functionality to detect user-defined types that are unserializable because every instance of the type would contain a cycle.

We use the ill-founded node detection algorithm from https://codereview.chromium.org/1908273003/ by having UserDefinedTypeBase implement the |Node| interface.

- In mojom_descriptor.go we add the method DetectIllFoundedTypes()
- We Invoke DetectIllFoundedTypes()in parse_driver.go after ComputeFinalData()
- We add the method NonAvoidableUserDefinedType() to the TypeRef interface to capture the notion that a type reference unavoidably entails a non-null pointer to a struct or union.
-We fixed up some ill-founded types that appeared in serialization_test.go because now we would be detecting them and failing before serialization.
- We enhanced the ill-founded graph detection library (in wellfounded_graphs.go) by introducing the ability for the client to add labels to the edges. The labels are opaque to the algorithm but we use them to maintain enough information to generate a useful error message. For example we use them to capture the name of the struct or union field corresponding to a graph edge.
- See illfounded_types_test.go to see the format of the error messages we will emit when an ill-founded type is detected.

BUG= fixes #694
R=azani@chromium.org

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

[rudominer, 2016-04-27 22:12:24]

Patchset #1 (id:1) has been deleted

[rudominer, 2016-04-27 22:12:32]

Patchset #1 (id:20001) has been deleted

[rudominer, 2016-04-27 22:12:42]

Patchset #1 (id:40001) has been deleted

[rudominer, 2016-04-27 22:12:50]

Patchset #1 (id:60001) has been deleted

[rudominer, 2016-04-27 22:12:58]

Patchset #1 (id:80001) has been deleted

[rudominer, 2016-04-27 22:17:38]

Description was changed from

==========
Added DetectIllFoundedTypes method.

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

to

==========
Mojom frontend: Detect Ill-founded Types

This patch adds the functionality to detect user-defined types that are
unserializable because every instance of the type would contain a cycle.

We use the ill-founded node detection algorithm from
https://codereview.chromium.org/1908273003/ by having UserDefinedTypeBase
implement the |Node| interface

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

[rudominer, 2016-04-27 22:40:06]

Description was changed from

==========
Mojom frontend: Detect Ill-founded Types

This patch adds the functionality to detect user-defined types that are
unserializable because every instance of the type would contain a cycle.

We use the ill-founded node detection algorithm from
https://codereview.chromium.org/1908273003/ by having UserDefinedTypeBase
implement the |Node| interface

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

to

==========
Mojom frontend: Detect Ill-founded Types

This patch adds the functionality to detect user-defined types that are
unserializable because every instance of the type would contain a cycle.

We use the ill-founded node detection algorithm from
https://codereview.chromium.org/1908273003/ by having UserDefinedTypeBase
implement the |Node| interface.

- In mojom_descriptor.go we add the method DetectIllFoundedTypes()
- We Invoke DetectIllFoundedTypes()in parse_driver.go after ComputeFinalData()
- We add the method NonAvoidableUserDefinedType() to the TypeRef interface to
capture the notion that a type reference unavoidably entails a non-null pointer
to a struct or union.
-We fixed up some ill-founded types that appeared in serialization_test.go
because now we would be detecting them and failing before serialization.
- We enhanced the ill-founded graph detection library (in wellfounded_graphs.go)
by introducing the ability for the client to add labels to the edges. The labels
are opaque to the algorithm but we use them to maintain enough information to
generate a useful error message. For example we use them to capture the name of
the struct or union field corresponding to a graph edge.
- See illfounded_types_test.go to see the format of the error messages we will
emit when an ill-founded type is detected.

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

[rudominer, 2016-04-27 22:48:43]

Patchset #1 (id:100001) has been deleted

[rudominer, 2016-04-27 23:05:24]

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

[rudominer, 2016-04-27 23:05:25]

Hi Alex, ptal.

[azani, 2016-04-28 22:37:13]

just some minor comments.

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
File mojom/mojom_tool/mojom/mojom_descriptor.go (right):

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/mojom_descriptor.go:312: testingMode bool
Can we add an accessor for testingMode that prints out a message when
testingMode is true? That will make it more obvious if we accidentally turn it
on.

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/mojom_descriptor.go:331: // SetTestingMode is used to
enable or disable testing mdoe. It is disabled by
s/mdoe/mode/

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
File mojom/mojom_tool/mojom/types.go (right):

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/types.go:135: // NonAvoidableUserType returns a non-nil
UserDefinedType just in case this type
I think something with more bullet points and references to the concrete problem
of infinite recursion and infinite space being forced during serialization would
be a bit easier to understand for future readers. Also, I think that in this
context, illegal is easier than ill-founded. Maybe something like this:

Some cycles in the type graph are illegal because serializing them would require
an infinite amount of space:
- A struct Foo with a non-nullable Foo field cannot be serialized.
However, not all cycles are illegal. A cycle is legal if serializing it does not
require an infinite recursion:
- A struct Foo with a nullable field of type Foo is a legal cycle because the
field can be set to null.
- A struct Foo with a field that is a variable-length array with elements of
type Foo is a legal cycle because the array can be empty.

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
File mojom/mojom_tool/mojom/user_defined_types.go (right):

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/user_defined_types.go:194: fmt.Fprintf(&buffer, "The type
%s is unserializable: Every instance of this type would include a cycle.",
Maybe we should also print a snippet.

[rudominer, 2016-04-29 00:27:02]

ptal

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
File mojom/mojom_tool/mojom/mojom_descriptor.go (right):

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/mojom_descriptor.go:312: testingMode bool
On 2016/04/28 22:37:13, azani wrote:
> Can we add an accessor for testingMode that prints out a message when
> testingMode is true? That will make it more obvious if we accidentally turn it
> on.

I took you suggesting seriously and played around with it. But it doesn't seem
like a good idea. It makes the test output spammy and I'm not too worried about
accidentally invoking SetTestingMode(true) in non-testing code. So I would
prefer not to do this if that is ok with you.

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/mojom_descriptor.go:331: // SetTestingMode is used to
enable or disable testing mdoe. It is disabled by
On 2016/04/28 22:37:13, azani wrote:
> s/mdoe/mode/

Done.

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
File mojom/mojom_tool/mojom/types.go (right):

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/types.go:135: // NonAvoidableUserType returns a non-nil
UserDefinedType just in case this type
On 2016/04/28 22:37:13, azani wrote:
> I think something with more bullet points and references to the concrete
problem
> of infinite recursion and infinite space being forced during serialization
would
> be a bit easier to understand for future readers. Also, I think that in this
> context, illegal is easier than ill-founded. Maybe something like this:
> 
> Some cycles in the type graph are illegal because serializing them would
require
> an infinite amount of space:
> - A struct Foo with a non-nullable Foo field cannot be serialized.
> However, not all cycles are illegal. A cycle is legal if serializing it does
not
> require an infinite recursion:
> - A struct Foo with a nullable field of type Foo is a legal cycle because the
> field can be set to null.
> - A struct Foo with a field that is a variable-length array with elements of
> type Foo is a legal cycle because the array can be empty.

Thanks for the suggestion. I reworked the comments. I did not do exactly what
you suggested by I did:

- Break into multiple paragraphs to avoid a big wall of words.
- Added one bulleted list
- Give more detailed examples as you suggested
- Mentioned "infinte recursion"
- Avoided the word "ill-founded" except in one place where I mention the
analysis of ill-founded types. I think this mention of ill-founded is warrented
because that is the language used by the method being referred to.

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
File mojom/mojom_tool/mojom/user_defined_types.go (right):

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/user_defined_types.go:194: fmt.Fprintf(&buffer, "The type
%s is unserializable: Every instance of this type would include a cycle.",
On 2016/04/28 22:37:13, azani wrote:
> Maybe we should also print a snippet.

We do. That is done by the method UserErrorMessage() invoked below.

[azani, 2016-04-29 00:31:48]

lgtm

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
File mojom/mojom_tool/mojom/mojom_descriptor.go (right):

https://codereview.chromium.org/1915413002/diff/120001/mojom/mojom_tool/mojom...
mojom/mojom_tool/mojom/mojom_descriptor.go:312: testingMode bool
On 2016/04/29 00:27:02, rudominer wrote:
> On 2016/04/28 22:37:13, azani wrote:
> > Can we add an accessor for testingMode that prints out a message when
> > testingMode is true? That will make it more obvious if we accidentally turn
it
> > on.
> 
> I took you suggesting seriously and played around with it. But it doesn't seem
> like a good idea. It makes the test output spammy and I'm not too worried
about
> accidentally invoking SetTestingMode(true) in non-testing code. So I would
> prefer not to do this if that is ok with you.

I thought the testing framework would eat those messages. OK.

[rudominer, 2016-04-29 00:59:57]

Description was changed from

==========
Mojom frontend: Detect Ill-founded Types

This patch adds the functionality to detect user-defined types that are
unserializable because every instance of the type would contain a cycle.

We use the ill-founded node detection algorithm from
https://codereview.chromium.org/1908273003/ by having UserDefinedTypeBase
implement the |Node| interface.

- In mojom_descriptor.go we add the method DetectIllFoundedTypes()
- We Invoke DetectIllFoundedTypes()in parse_driver.go after ComputeFinalData()
- We add the method NonAvoidableUserDefinedType() to the TypeRef interface to
capture the notion that a type reference unavoidably entails a non-null pointer
to a struct or union.
-We fixed up some ill-founded types that appeared in serialization_test.go
because now we would be detecting them and failing before serialization.
- We enhanced the ill-founded graph detection library (in wellfounded_graphs.go)
by introducing the ability for the client to add labels to the edges. The labels
are opaque to the algorithm but we use them to maintain enough information to
generate a useful error message. For example we use them to capture the name of
the struct or union field corresponding to a graph edge.
- See illfounded_types_test.go to see the format of the error messages we will
emit when an ill-founded type is detected.

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

to

==========
Mojom frontend: Detect Ill-founded Types

This patch adds the functionality to detect user-defined types that are
unserializable because every instance of the type would contain a cycle.

We use the ill-founded node detection algorithm from
https://codereview.chromium.org/1908273003/ by having UserDefinedTypeBase
implement the |Node| interface.

- In mojom_descriptor.go we add the method DetectIllFoundedTypes()
- We Invoke DetectIllFoundedTypes()in parse_driver.go after ComputeFinalData()
- We add the method NonAvoidableUserDefinedType() to the TypeRef interface to
capture the notion that a type reference unavoidably entails a non-null pointer
to a struct or union.
-We fixed up some ill-founded types that appeared in serialization_test.go
because now we would be detecting them and failing before serialization.
- We enhanced the ill-founded graph detection library (in wellfounded_graphs.go)
by introducing the ability for the client to add labels to the edges. The labels
are opaque to the algorithm but we use them to maintain enough information to
generate a useful error message. For example we use them to capture the name of
the struct or union field corresponding to a graph edge.
- See illfounded_types_test.go to see the format of the error messages we will
emit when an ill-founded type is detected.

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

[rudominer, 2016-04-29 01:02:53]

Description was changed from

==========
Mojom frontend: Detect Ill-founded Types

This patch adds the functionality to detect user-defined types that are
unserializable because every instance of the type would contain a cycle.

We use the ill-founded node detection algorithm from
https://codereview.chromium.org/1908273003/ by having UserDefinedTypeBase
implement the |Node| interface.

- In mojom_descriptor.go we add the method DetectIllFoundedTypes()
- We Invoke DetectIllFoundedTypes()in parse_driver.go after ComputeFinalData()
- We add the method NonAvoidableUserDefinedType() to the TypeRef interface to
capture the notion that a type reference unavoidably entails a non-null pointer
to a struct or union.
-We fixed up some ill-founded types that appeared in serialization_test.go
because now we would be detecting them and failing before serialization.
- We enhanced the ill-founded graph detection library (in wellfounded_graphs.go)
by introducing the ability for the client to add labels to the edges. The labels
are opaque to the algorithm but we use them to maintain enough information to
generate a useful error message. For example we use them to capture the name of
the struct or union field corresponding to a graph edge.
- See illfounded_types_test.go to see the format of the error messages we will
emit when an ill-founded type is detected.

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

to

==========
Mojom frontend: Detect Ill-founded Types

This patch adds the functionality to detect user-defined types that are
unserializable because every instance of the type would contain a cycle.

We use the ill-founded node detection algorithm from
https://codereview.chromium.org/1908273003/ by having UserDefinedTypeBase
implement the |Node| interface.

- In mojom_descriptor.go we add the method DetectIllFoundedTypes()
- We Invoke DetectIllFoundedTypes()in parse_driver.go after ComputeFinalData()
- We add the method NonAvoidableUserDefinedType() to the TypeRef interface to
capture the notion that a type reference unavoidably entails a non-null pointer
to a struct or union.
-We fixed up some ill-founded types that appeared in serialization_test.go
because now we would be detecting them and failing before serialization.
- We enhanced the ill-founded graph detection library (in wellfounded_graphs.go)
by introducing the ability for the client to add labels to the edges. The labels
are opaque to the algorithm but we use them to maintain enough information to
generate a useful error message. For example we use them to capture the name of
the struct or union field corresponding to a graph edge.
- See illfounded_types_test.go to see the format of the error messages we will
emit when an ill-founded type is detected.

BUG= fixes #694
R=azani@chromium.org

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

[rudominer, 2016-04-29 01:02:55]

Committed patchset #2 (id:140001) manually as
4c234209f3b34950d174f76c22c4ca8d20a49b9f (presubmit successful).