Mojom frontend: Detect Ill-founded Types

mojom/mojom_tool/mojom/mojom_descriptor.go

Index: mojom/mojom_tool/mojom/mojom_descriptor.go
diff --git a/mojom/mojom_tool/mojom/mojom_descriptor.go b/mojom/mojom_tool/mojom/mojom_descriptor.go
index cedad88197f72d83d95dc3432376a206172f19d3..923b98f013914b9b9dd959c3e0d4aa9f68d7bc68 100644
--- a/mojom/mojom_tool/mojom/mojom_descriptor.go
+++ b/mojom/mojom_tool/mojom/mojom_descriptor.go
@@ -8,6 +8,7 @@ import (
 	"bytes"
 	"fmt"
 	"mojom/mojom_tool/lexer"
+	"sort"
 	"strings"
 )
 
@@ -306,6 +307,9 @@ type MojomDescriptor struct {
 	// there are unresolved references in the .mojom files.
 	unresolvedTypeReferences  []*UserTypeRef
 	unresolvedValueReferences []*UserValueRef
+
+	// In testing mode we iterate through some maps in deterministic order.
+	testingMode bool
 }
 
 func NewMojomDescriptor() *MojomDescriptor {
@@ -324,6 +328,13 @@ func NewMojomDescriptor() *MojomDescriptor {
 	return descriptor
 }
 
+// SetTestingMode is used to enable or disable testing mode. It is disabled by
+// default. In testing mode some operations will iterate through maps in a
+// deterministic order. This is less performant but enables deterministic testing.
+func (d *MojomDescriptor) SetTestingMode(testingMode bool) {
+	d.testingMode = testingMode
+}
+
 func (d *MojomDescriptor) getAbstractModuleScope(fullyQualifiedName string) *Scope {
 	if scope, ok := d.abstractScopesByName[fullyQualifiedName]; ok {
 		return scope
@@ -361,6 +372,41 @@ func (d *MojomDescriptor) ContainsFile(fileName string) bool {
 	return ok
 }
 
+// DetectIllFoundedTypes() should be invoked after Resolve() has completed
+// successfully. It performs an analysis of the type graph in order to detect
+// ill-founded types. An ill-founded type is one for which it is impossible
+// to create an instance that would be legally serializable using Mojo
+// serialization. This method returns a non-nil error just in case an
+// ill-founded type is detected. The contained error message is appropriate
+// for display to an end-user.
+//
+// An example of an ill-founded type is a struct |Foo| with a field whose type
+// is a non-nullable Foo. Thus ill-foundedness may be due to a cycle in the
+// type graph. But not all cycles cause ill-foundedness. Firstly nullable
+// fields do not lead to ill-foundedness as the potential cycle can be broken
+// by setting the field to null. Also the situation with unions is more complicated:
+// Type graphs involving unions are only ill-founded if every possible way of
+// chosing a value for all of the unions still leads to an unbreakable cycle.
+func (d *MojomDescriptor) DetectIllFoundedTypes() error {
+	// We capture the keys of the map TypesByKey in a list and iterate over that list
+	// rather than iterating over the map. This is so that in testing mode
+	// we can first sort the list so as to iterate in a deterministic order.
+	keyList := make([]string, 0, len(d.TypesByKey))
+	for key, _ := range d.TypesByKey {
+		keyList = append(keyList, key)
+	}
+	if d.testingMode {
+		sort.Strings(keyList)
+	}
+	for _, key := range keyList {
+		udt := d.TypesByKey[key]
+		if err := udt.CheckWellFounded(); err != nil {
+			return err
+		}
+	}
+	return nil
+}
+
 /////////////////////////////////////////
 /// Type and Value Resolution
 ////////////////////////////////////////