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
Review URL: https://codereview.chromium.org/1915413002 .
diff --git a/mojom/mojom_tool/integration_tests/illfounded_types_test.go b/mojom/mojom_tool/integration_tests/illfounded_types_test.go
new file mode 100644
index 0000000..859bc55
--- /dev/null
+++ b/mojom/mojom_tool/integration_tests/illfounded_types_test.go
@@ -0,0 +1,474 @@
+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+package parser
+
+import (
+ "fmt"
+ "mojom/mojom_tool/mojom"
+ "mojom/mojom_tool/parser"
+ "strings"
+ "testing"
+)
+
+// TestIllegalPatterns tests cases where DetectIllFoundedTypes() should return an error.
+func TestIllegalPatterns(t *testing.T) {
+ test := singleFileTest{}
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is non-nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ Foo x;
+ };`
+ test.addTestCase(contents, []string{
+ "The type Foo is unserializable: Every instance of this type would include a cycle.",
+ "Example cycle: Foo.x -> Foo",
+ "One way to break this cycle is to make the field \"x\" nullable.",
+ })
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is non-nullable, fixed-length array of non-nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ array<Foo, 1> x;
+ };`
+ test.addTestCase(contents, []string{
+ "The type Foo is unserializable: Every instance of this type would include a cycle.",
+ "Example cycle: Foo.x -> Foo",
+ "One way to break this cycle is to make the field \"x\" nullable.",
+ })
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is non-nullable, fixed-length array of
+ // non-nullable fixed-length array of non-nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ array<array<Foo, 1>, 1> x;
+ };`
+ test.addTestCase(contents, []string{
+ "The type Foo is unserializable: Every instance of this type would include a cycle.",
+ "Example cycle: Foo.x -> Foo",
+ "One way to break this cycle is to make the field \"x\" nullable.",
+ })
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Union field is non-nullable pointer to union itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ union Foo{
+ Foo x;
+ };`
+ test.addTestCase(contents, []string{
+ "The type Foo is unserializable: Every instance of this type would include a cycle.",
+ "Example cycle: Foo.x -> Foo",
+ "One way to break this cycle is to make the field \"x\" nullable.",
+ })
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Union field is non-nullable, fixed-length array of non-nullable pointer to union itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ union Foo{
+ array<Foo, 1> x;
+ };`
+ test.addTestCase(contents, []string{
+ "The type Foo is unserializable: Every instance of this type would include a cycle.",
+ "Example cycle: Foo.x -> Foo",
+ "One way to break this cycle is to make the field \"x\" nullable.",
+ })
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: A cycle of length 3.
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct MyStruct1 {
+ MyStruct2 x;
+ };
+
+ struct MyStruct2 {
+ MyStruct3 x;
+ };
+
+ struct MyStruct3 {
+ MyStruct1 x;
+ };`
+ test.addTestCase(contents, []string{
+ "The type MyStruct1 is unserializable: Every instance of this type would include a cycle.",
+ "Example cycle: MyStruct1.x -> MyStruct2.x -> MyStruct3.x -> MyStruct1",
+ "One way to break this cycle is to make the field \"x\" nullable.",
+ })
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Two structs and a union
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct MyStruct1 {
+ MyStruct2 x;
+ int32 y;
+ };
+
+ struct MyStruct2 {
+ MyUnion x;
+ int32 y;
+ };
+
+ union MyUnion {
+ MyStruct1 x;
+ MyStruct2 y;
+ };`
+ test.addTestCase(contents, []string{
+ "The type MyStruct1 is unserializable: Every instance of this type would include a cycle.",
+ "Example cycle: MyStruct1.x -> MyStruct2.x -> MyUnion.x -> MyStruct1",
+ "One way to break this cycle is to make the field \"x\" nullable.",
+ })
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Ill-foundedness not found until second pass of algorithm.
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct AEmptyStruct {
+ };
+
+ struct BMyUnion {
+ AEmptyStruct x;
+ CBadStruct y;
+ };
+
+ struct CBadStruct {
+ CBadStruct x;
+ };`
+
+ test.addTestCase(contents, []string{
+ "The type CBadStruct is unserializable: Every instance of this type would include a cycle.",
+ "Example cycle: CBadStruct.x -> CBadStruct",
+ "One way to break this cycle is to make the field \"x\" nullable.",
+ })
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Execute all of the test cases.
+ ////////////////////////////////////////////////////////////
+ for i, c := range test.cases {
+ // Parse anresolve the mojom input.
+ descriptor := mojom.NewMojomDescriptor()
+ specifiedName := ""
+ if c.importedFrom == nil {
+ specifiedName = c.fileName
+ }
+ parser := parser.MakeParser(c.fileName, specifiedName, c.mojomContents, descriptor, c.importedFrom)
+ parser.Parse()
+ if !parser.OK() {
+ t.Errorf("Parsing error for %s: %s", c.fileName, parser.GetError().Error())
+ continue
+ }
+ err := descriptor.Resolve()
+ if err != nil {
+ t.Errorf("Resolution error for %s: %s", c.fileName, err)
+ continue
+ }
+ if err = descriptor.ComputeFinalData(); err != nil {
+ t.Errorf("ComputeFinalData error for %s: %s", c.fileName, err)
+ continue
+ }
+
+ descriptor.SetTestingMode(true)
+ err = descriptor.DetectIllFoundedTypes()
+
+ if err == nil {
+ t.Errorf("No cycles were detected for test case %d.", i)
+ continue
+ }
+
+ got := err.Error()
+ for _, expected := range c.expectedErrors {
+ if !strings.Contains(got, expected) {
+ t.Errorf("%s:\n*****expected to contain:\n%s\n****actual\n%s", c.fileName, expected, got)
+ }
+ }
+
+ }
+}
+
+// TestLegalPatterns tests cases where DetectIllFoundedTypes() should not return an error.
+func TestLegalPatterns(t *testing.T) {
+ test := singleFileSuccessTest{}
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is nullable, pointer to struct itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ Foo? x;
+ };`
+
+ testFunc := func(descriptor *mojom.MojomDescriptor) error {
+ return nil
+ }
+ test.addTestCase("", contents, testFunc)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is non-nullable, variable-length array of non-nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+
+ {
+ contents := `
+ struct Foo{
+ array<Foo> x;
+ };`
+
+ testFunc := func(descriptor *mojom.MojomDescriptor) error {
+ return nil
+ }
+ test.addTestCase("", contents, testFunc)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is nullable, fixed-length array of non-nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+
+ {
+ contents := `
+ struct Foo{
+ array<Foo, 1>? x;
+ };`
+
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is non-nullable, fixed-length array of nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+
+ {
+ contents := `
+ struct Foo{
+ array<Foo?, 1> x;
+ };`
+
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is non-nullable, variable-length array of
+ // non-nullable fixed-length array of non-nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ array<array<Foo, 1>> x;
+ };`
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is non-nullable, fixed-length array of
+ // non-nullable variable-length array of non-nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ array<array<Foo>, 1> x;
+ };`
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is non-nullable, fixed-length array of
+ // non-nullable fixed-length array of nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ array<array<Foo?, 1>, 1> x;
+ };`
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Struct field is nullable, fixed-length array of
+ // non-nullable fixed-length array of non-nullable pointer to struct itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ array<array<Foo, 1>, 1>? x;
+ };`
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Field of struct Foo is a map from a string to a Foo
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct Foo{
+ map<string, Foo> x;
+ };`
+
+ testFunc := func(descriptor *mojom.MojomDescriptor) error {
+ return nil
+ }
+ test.addTestCase("", contents, testFunc)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: union field is nullable, pointer to union itself
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ union Foo{
+ Foo? x;
+ };`
+
+ testFunc := func(descriptor *mojom.MojomDescriptor) error {
+ return nil
+ }
+ test.addTestCase("", contents, testFunc)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: union field is non-nullable, variable-length array of non-nullable pointer to union itself
+ ////////////////////////////////////////////////////////////
+
+ {
+ contents := `
+ union Foo{
+ array<Foo> x;
+ };`
+
+ testFunc := func(descriptor *mojom.MojomDescriptor) error {
+ return nil
+ }
+ test.addTestCase("", contents, testFunc)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: union field is nullable, fixed-length array of non-nullable pointer to union itself
+ ////////////////////////////////////////////////////////////
+
+ {
+ contents := `
+ union Foo{
+ array<Foo, 1>? x;
+ };`
+
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: union field is non-nullable, fixed-length array of nullable pointer to union itself
+ ////////////////////////////////////////////////////////////
+
+ {
+ contents := `
+ union Foo{
+ array<Foo?, 1> x;
+ };`
+
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: A cycle of length 3 with 1 nullable.
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ struct MyStruct1 {
+ MyStruct2 x;
+ };
+
+ struct MyStruct2 {
+ MyStruct3? x;
+ };
+
+ struct MyStruct3 {
+ MyStruct1 x;
+ };`
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Test Case: Well-founded because of CStruct2
+ ////////////////////////////////////////////////////////////
+ {
+ contents := `
+ union AUnion0 {
+ BStruct1 x;
+ CStruct2 y;
+ };
+
+ struct BStruct1 {
+ int32 x;
+ DUnion3 y;
+ };
+
+ struct CStruct2 {
+ string x;
+ };
+
+ union DUnion3 {
+ AUnion0 x;
+ BStruct1 y;
+ };`
+ test.addTestCase("", contents, nil)
+ }
+
+ ////////////////////////////////////////////////////////////
+ // Execute all of the test cases.
+ ////////////////////////////////////////////////////////////
+ for i, c := range test.cases {
+ // Parse and resolve the mojom input.
+ descriptor := mojom.NewMojomDescriptor()
+ fileName := fmt.Sprintf("file%d", i)
+ parser := parser.MakeParser(fileName, fileName, c.mojomContents, descriptor, nil)
+ parser.Parse()
+ if !parser.OK() {
+ t.Errorf("Parsing error for %s: %s", fileName, parser.GetError().Error())
+ continue
+ }
+ err := descriptor.Resolve()
+ if err != nil {
+ t.Errorf("Resolution failed for test case %d: %s", i, err.Error())
+ continue
+ }
+
+ if err := descriptor.ComputeFinalData(); err != nil {
+ t.Errorf("ComputeFinalData error for test case %d: %s", i, err.Error())
+ continue
+ }
+
+ if err := descriptor.DetectIllFoundedTypes(); err != nil {
+ t.Errorf("DetectIllFoundedTypes error for test case %d: %s", i, err.Error())
+ continue
+ }
+
+ if c.testFunc != nil {
+ if err := c.testFunc(descriptor); err != nil {
+ t.Errorf("%s:\n%s", fileName, err.Error())
+ continue
+ }
+ }
+ }
+}
diff --git a/mojom/mojom_tool/mojom/mojom_descriptor.go b/mojom/mojom_tool/mojom/mojom_descriptor.go
index cedad88..923b98f 100644
--- a/mojom/mojom_tool/mojom/mojom_descriptor.go
+++ b/mojom/mojom_tool/mojom/mojom_descriptor.go
@@ -8,6 +8,7 @@
"bytes"
"fmt"
"mojom/mojom_tool/lexer"
+ "sort"
"strings"
)
@@ -306,6 +307,9 @@
// 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 @@
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 @@
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
////////////////////////////////////////
diff --git a/mojom/mojom_tool/mojom/types.go b/mojom/mojom_tool/mojom/types.go
index 3796978..d1bbc8c 100644
--- a/mojom/mojom_tool/mojom/types.go
+++ b/mojom/mojom_tool/mojom/types.go
@@ -131,6 +131,33 @@
// It returns the number of bytes on which an instance of the type to which this
// type reference resolves must be aligned during Mojo serialization.
SerializationAlignment() uint32
+
+ // NonAvoidableUserType is invoked after the resolution and validation phases.
+ // It returns a non-nil UserDefinedType just in case this type
+ // reference resolves to a type the serialization of which will
+ // include a non-nullable pointer to a struct or union. In that case a
+ // non-nil UserDefinedType representing that struct or union is returnd.
+ //
+ // This method is used during the analysis of ill-founded types. The goal of
+ // that analysis is to find user-defined types that are unserializable because
+ // every instance of the type would involve a cycle.
+ //
+ // For example, suppose there is a struct Foo that contains a field |x|
+ // and the type of x is Foo. An instance of Foo could not be serialized because
+ // the cycle would cause an infinite recursion.
+ //
+ // However a cycle in the type graph is allowed if it is avoidable.
+ // For example if the type of x were instead Foo? then an instance
+ // of Foo could be serialized by setting x to null at some level
+ // of the recursion.
+ //
+ // Similarly if the type of x were array<Foo, 1> then an instance of
+ // Foo would not be serializable. However it allowed for the type of
+ // x to be any of the following:
+ // - array<Foo>
+ // - array<Foo?, 1>
+ // - array<Foo, 1>?
+ NonAvoidableUserType() UserDefinedType
}
/////////////////////////////////////////////////////////////
@@ -361,6 +388,10 @@
return t.SerializationSize()
}
+func (SimpleType) NonAvoidableUserType() UserDefinedType {
+ return nil
+}
+
func (t SimpleType) String() string {
switch t {
case SimpleTypeBool:
@@ -421,6 +452,10 @@
return 8
}
+func (StringType) NonAvoidableUserType() UserDefinedType {
+ return nil
+}
+
// StringLiteralType is a global singleton representing the unique LiteralType string.
var StringLiteralType LiteralType = StringType{}
@@ -518,6 +553,10 @@
return 4
}
+func (HandleTypeRef) NonAvoidableUserType() UserDefinedType {
+ return nil
+}
+
func (h HandleTypeRef) HandleKind() HandleKind {
return h.kind
}
@@ -663,6 +702,13 @@
return a.elementType
}
+func (a ArrayTypeRef) NonAvoidableUserType() UserDefinedType {
+ if a.nullable || a.fixedLength <= 0 {
+ return nil
+ }
+ return a.elementType.NonAvoidableUserType()
+}
+
// An ArrayTypeRef is a TypeRef:
func (ArrayTypeRef) TypeRefKind() TypeKind {
@@ -747,6 +793,10 @@
return 8
}
+func (MapTypeRef) NonAvoidableUserType() UserDefinedType {
+ return nil
+}
+
func (m MapTypeRef) KeyType() TypeRef {
return m.keyType
}
@@ -885,6 +935,20 @@
return t.resolvedType.SerializationAlignment()
}
+func (t *UserTypeRef) NonAvoidableUserType() UserDefinedType {
+ if t.nullable || t.interfaceRequest {
+ return nil
+ }
+ if t.resolvedType == nil {
+ panic("This method should only be invoked after successful resolution.")
+ }
+ switch udt := t.resolvedType.(type) {
+ case *MojomStruct, *MojomUnion:
+ return udt
+ }
+ return nil
+}
+
func (t *UserTypeRef) IsInterfaceRequest() bool {
return t.interfaceRequest
}
diff --git a/mojom/mojom_tool/mojom/user_defined_types.go b/mojom/mojom_tool/mojom/user_defined_types.go
index 0234bfe..ac8c05c 100644
--- a/mojom/mojom_tool/mojom/user_defined_types.go
+++ b/mojom/mojom_tool/mojom/user_defined_types.go
@@ -5,6 +5,7 @@
package mojom
import (
+ "bytes"
"errors"
"fmt"
"math"
@@ -83,6 +84,30 @@
// See computed_data.go.
ComputeFinalData() error
+ // CheckWellFounded() is invoked on each user-defined type in a MojomDescriptor
+ // after the resolution and type validation phases have completed successfully.
+ // The method performs an analysis of the type graph below a given type 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.
+ //
+ // We model this using the notion of a well-founded two-sorted graph. See
+ // utils/well-founded_graphs.go. Using the terminology from that file, we
+ // model structs as circle nodes and unions as square nodes. In this context
+ // the type graph only includes edges for non-nullable fields and arrays of
+ // fixed positive length.
+ CheckWellFounded() error
+
// SerializationSize() returns the number of bytes necessary to serialize an
// instance of this type in Mojo serialization.
SerializationSize() uint32
@@ -92,12 +117,19 @@
SerializationAlignment() uint32
}
+/////////////////////////////////////////////////////////////
+// type UserDefinedTypeBase
+/////////////////////////////////////////////////////////////
+
// This struct is embedded in each of MojomStruct, MojomInterface
// MojomEnum and MojomUnion
type UserDefinedTypeBase struct {
DeclarationData
thisType UserDefinedType
typeKey string
+
+ // Cache the fact that |SetKnownWellFounded| has been invoked.
+ knownWellFounded bool
}
// This method is invoked from the constructors for the containing types:
@@ -154,6 +186,101 @@
return b.scope
}
+func (b *UserDefinedTypeBase) CheckWellFounded() error {
+ cycleDescription := utils.CheckWellFounded(b)
+ if cycleDescription != nil {
+ firstIllFoundedType := nodeToUserDefinedType(cycleDescription.First)
+ var buffer bytes.Buffer
+ fmt.Fprintf(&buffer, "The type %s is unserializable: Every instance of this type would include a cycle.",
+ firstIllFoundedType.FullyQualifiedName())
+ fmt.Fprintf(&buffer, "\nExample cycle: %s", firstIllFoundedType.SimpleName())
+ for _, edge := range cycleDescription.Path {
+ fmt.Fprintf(&buffer, ".%s -> %s", edge.Label.(lexer.Token).Text, nodeToUserDefinedType(edge.Target).SimpleName())
+ }
+ fmt.Fprintf(&buffer, "\n")
+ fmt.Fprintf(&buffer, "One way to break this cycle is to make the field %q nullable.", cycleDescription.Path[0].Label.(lexer.Token).Text)
+ return fmt.Errorf(UserErrorMessage(
+ firstIllFoundedType.Scope().file, cycleDescription.Path[0].Label.(lexer.Token), buffer.String()))
+ }
+ return nil
+}
+
+// *UserDefinedTypeBase implements utils.Node for the sake of |CheckWellFounded|.
+func (b *UserDefinedTypeBase) KnownWellFounded() bool {
+ return b.knownWellFounded
+}
+
+// *UserDefinedTypeBase implements utils.Node for the sake of |CheckWellFounded|.
+func (b *UserDefinedTypeBase) SetKnownWellFounded() {
+ b.knownWellFounded = true
+}
+
+// *UserDefinedTypeBase implements utils.Node for the sake of |CheckWellFounded|.
+func (b *UserDefinedTypeBase) Name() string {
+ return b.FullyQualifiedName()
+}
+
+// *UserDefinedTypeBase implements utils.Node for the sake of |CheckWellFounded|.
+func (b *UserDefinedTypeBase) IsSquare() bool {
+ // A node in the type graph is square if and only if the type is a union.
+ return b.thisType.Kind() == UserDefinedTypeKindUnion
+}
+
+// *UserDefinedTypeBase implements utils.Node for the sake of |CheckWellFounded|.
+func (b *UserDefinedTypeBase) OutEdges() []utils.OutEdge {
+ // The only types we need to model as nodes are structs and unions.
+ // We model some of their fields as children: fields whose type is a non-nullable
+ // pointer or a fixed-length array to another struct or union.
+ outEdges := make([]utils.OutEdge, 0)
+ switch udt := b.thisType.(type) {
+ case *MojomEnum, *MojomInterface:
+ return nil
+ case *MojomStruct:
+ for _, field := range udt.FieldsInLexicalOrder {
+ childType := field.FieldType.NonAvoidableUserType()
+ if childType != nil {
+ outEdges = append(outEdges, utils.OutEdge{field.nameToken, getTypeBase(childType)})
+ }
+ }
+ case *MojomUnion:
+ for _, field := range udt.FieldsInLexicalOrder {
+ childType := field.FieldType.NonAvoidableUserType()
+ if childType != nil {
+ outEdges = append(outEdges, utils.OutEdge{field.nameToken, getTypeBase(childType)})
+ }
+ }
+ default:
+ panic(fmt.Sprintf("unexpected kind %T", udt))
+ }
+ return outEdges
+}
+
+// getTypeBase returns the *UserDefinedTypeBase contained in the given UserDefinedType
+func getTypeBase(udt UserDefinedType) *UserDefinedTypeBase {
+ switch udt := udt.(type) {
+ case *MojomStruct:
+ return &udt.UserDefinedTypeBase
+ case *MojomUnion:
+ return &udt.UserDefinedTypeBase
+ case *MojomEnum:
+ return &udt.UserDefinedTypeBase
+ case *MojomInterface:
+ return &udt.UserDefinedTypeBase
+ default:
+ panic(fmt.Sprintf("Unrecognized user defined type %T", udt))
+ }
+}
+
+// nodeToUserDefinedType assumes that the type of |node| is *UserDefinedTypeBase
+// and returns the associated UserDefinedType
+func nodeToUserDefinedType(node utils.Node) UserDefinedType {
+ return node.(*UserDefinedTypeBase).thisType
+}
+
+/////////////////////////////////////////////////////////////
+// type DeclaredObjectsContainerBase
+/////////////////////////////////////////////////////////////
+
// DeclaredObjectsContainerBase holds a list of DeclaredObjects in order of
// occurrence in the source.
// It includes all declared objects (for example methods and fields) not just
@@ -181,6 +308,10 @@
GetDeclaredObjects() []DeclaredObject
}
+/////////////////////////////////////////////////////////////
+// type NestedDeclarations
+/////////////////////////////////////////////////////////////
+
// Some user-defined types, namely interfaces and structs, may act as
// namespaced scopes for declarations of constants and enums.
type NestedDeclarations struct {
diff --git a/mojom/mojom_tool/parser/parse_driver.go b/mojom/mojom_tool/parser/parse_driver.go
index d058a99..f7b71bb 100644
--- a/mojom/mojom_tool/parser/parse_driver.go
+++ b/mojom/mojom_tool/parser/parse_driver.go
@@ -170,7 +170,12 @@
}
// Compute data for generators.
- err = descriptor.ComputeFinalData()
+ if err = descriptor.ComputeFinalData(); err != nil {
+ return
+ }
+
+ // Check for ill-founded types.
+ err = descriptor.DetectIllFoundedTypes()
return
}
diff --git a/mojom/mojom_tool/serialization/serialization_test.go b/mojom/mojom_tool/serialization/serialization_test.go
index cce8a1d..545609c 100644
--- a/mojom/mojom_tool/serialization/serialization_test.go
+++ b/mojom/mojom_tool/serialization/serialization_test.go
@@ -1148,6 +1148,10 @@
t.Errorf("ComputeFinalData error for %s: %s", c.fileName, err.Error())
continue
}
+ if err := descriptor.DetectIllFoundedTypes(); err != nil {
+ t.Errorf("DetectIllFoundedTypes error for %s: %s", c.fileName, err.Error())
+ continue
+ }
// Simulate setting the canonical file name for the imported files. In real operation
// this step is done in parser_driver.go when each of the imported files are parsed.
@@ -2082,7 +2086,7 @@
struct MyStruct1 {
int8 x;
MyUnion1 my_union;
- MyStruct1 my_struct;
+ MyStruct1? my_struct;
MyInterface1& my_interface_request;
int32 y;
MyInterface1 my_interface;
@@ -2117,7 +2121,7 @@
{
DeclData: test.newShortDeclDataO(2, -1, "my_struct"),
Type: &mojom_types.TypeTypeReference{mojom_types.TypeReference{
- false, false, stringPointer("MyStruct1"), stringPointer("TYPE_KEY:MyStruct1")}},
+ true, false, stringPointer("MyStruct1"), stringPointer("TYPE_KEY:MyStruct1")}},
Offset: 24,
},
// field my_interface_request
@@ -2181,7 +2185,7 @@
struct MyStruct1 {
int8 x;
MyUnion1 my_union;
- MyStruct1 my_struct;
+ MyStruct1? my_struct;
[MinVersion=1]
MyInterface1&? my_interface_request;
@@ -2222,7 +2226,7 @@
{
DeclData: test.newShortDeclDataO(2, -1, "my_struct"),
Type: &mojom_types.TypeTypeReference{mojom_types.TypeReference{
- false, false, stringPointer("MyStruct1"), stringPointer("TYPE_KEY:MyStruct1")}},
+ true, false, stringPointer("MyStruct1"), stringPointer("TYPE_KEY:MyStruct1")}},
Offset: 24,
},
// field my_interface_request
@@ -2303,6 +2307,10 @@
t.Errorf("ComputeFinalData error for %s: %s", c.fileName, err.Error())
continue
}
+ if err := descriptor.DetectIllFoundedTypes(); err != nil {
+ t.Errorf("DetectIllFoundedTypes error for %s: %s", c.fileName, err.Error())
+ continue
+ }
// Simulate setting the canonical file name for the imported files. In real operation
// this step is done in parser_driver.go when each of the imported files are parsed.
@@ -2412,6 +2420,10 @@
t.Errorf("ComputeFinalData error for %s: %s", c.fileName, err.Error())
continue
}
+ if err := descriptor.DetectIllFoundedTypes(); err != nil {
+ t.Errorf("DetectIllFoundedTypes error for %s: %s", c.fileName, err.Error())
+ continue
+ }
// Serialize
bytes, _, err := serialize(descriptor, false, false, c.lineAndcolumnNumbers, false)
@@ -2687,6 +2699,10 @@
t.Errorf("ComputeFinalData error for case %d: %s", i, err.Error())
continue
}
+ if err := descriptor.DetectIllFoundedTypes(); err != nil {
+ t.Errorf("DetectIllFoundedTypes error for case %d: %s", i, err.Error())
+ continue
+ }
// Serialize
bytes, _, err := serialize(descriptor, false, false, c.lineAndcolumnNumbers, false)
@@ -3296,6 +3312,10 @@
t.Errorf("ComputeFinalData error for case %d: %s", i, err.Error())
continue
}
+ if err := descriptor.DetectIllFoundedTypes(); err != nil {
+ t.Errorf("DetectIllFoundedTypes error for case %d: %s", i, err.Error())
+ continue
+ }
// Serialize
bytes, _, err := serialize(descriptor, false, false, false, true)
diff --git a/mojom/mojom_tool/utils/wellfounded_graphs.go b/mojom/mojom_tool/utils/wellfounded_graphs.go
index 6603c0f..1266a96 100644
--- a/mojom/mojom_tool/utils/wellfounded_graphs.go
+++ b/mojom/mojom_tool/utils/wellfounded_graphs.go
@@ -28,12 +28,15 @@
///////////////////////////////////////////////////
// Node type
//
-// A |Node| is a node in a directed graph.
+// A |Node| is a node in a directed graph. A user of this library is responsible
+// for implementing this interface. This library will use the Go equality operator
+// to compare instances of |Node| and it is the responsibility of the user
+// to ensure that x == y iff x and y represent the same logical node.
///////////////////////////////////////////////////
type Node interface {
// Returns the list of children of this node.
- OutEdges() []Node
+ OutEdges() []OutEdge
// Returns whether or not this node is a square node.
IsSquare() bool
@@ -53,8 +56,18 @@
// this library.
KnownWellFounded() bool
- // Returns the name of this node, appropriate for debugging.
- DebugName() string
+ // Returns a human-readable name for this node. Not used by the algorithm
+ // but used for generating debugging and error messages.
+ Name() string
+}
+
+type OutEdge struct {
+ // The Label on an edge is opaque data that may be used by the client however it wishes.
+ // The algorithm never inspects this data.
+ Label interface{}
+
+ // The target node of the out edge.
+ Target Node
}
///////////////////////////////////////////////////
@@ -134,13 +147,14 @@
///////////////////////////////////////////////////
type cycleFinder struct {
- // Maps each node seen by the computation to its holder.
+ // Maps each node seen by the computation to its holder. Note that this assumes
+ // that the implementation of Node uses values that are comparable and
+ // obey identity semantics.
nodeToHolder map[Node]*nodeHolder
foundationSet, pendingSet NodeSet
visitationIndex int
- currentPath nodeStack
debugDataRequest *debugData
}
@@ -155,7 +169,6 @@
finder.nodeToHolder = make(map[Node]*nodeHolder)
finder.foundationSet = MakeNodeSet()
finder.pendingSet = MakeNodeSet()
- finder.currentPath = nodeStack{}
return finder
}
@@ -206,7 +219,7 @@
// build a canonical cycle.
freshCycleFinder := makeCycleFinder()
holder := freshCycleFinder.holderForNode(minIllfoundedNode)
- return freshCycleFinder.findKnownIllFoundedCycle(holder)
+ return freshCycleFinder.findKnownIllFoundedCycle(holder, nil)
}
// checkWellFoundedPhase1 is a recursive helper function that does a depth-first traversal
@@ -246,8 +259,8 @@
// Next we examine each of the children and recurse into the unvisited ones.
sawUnverifiedChild := false
- for _, child := range nodeHolder.node.OutEdges() {
- childHolder := finder.holderForNode(child)
+ for _, edge := range nodeHolder.node.OutEdges() {
+ childHolder := finder.holderForNode(edge.Target)
if childHolder.state == vsUnvisited {
// Recursively visit this child.
finder.checkWellFoundedPhase1(childHolder)
@@ -323,7 +336,8 @@
if finder.pendingSet.Contains(p) {
knownWellFounded := true
if !p.node.IsSquare() {
- for _, child := range p.node.OutEdges() {
+ for _, edge := range p.node.OutEdges() {
+ child := edge.Target
if child != p.node && !child.KnownWellFounded() {
knownWellFounded = false
break
@@ -340,6 +354,14 @@
}
}
+// A pathElement is a node and one of its out-edges.
+type pathElement struct {
+ node Node
+ edge OutEdge
+}
+
+type nodePath []pathElement
+
// findKnownIllFoundedCycle finds and returns a |CycleDescription| starting from a node that is known
// to be ill-founded. This proceeds by following edges from an ill-founded node to
// an ill-founded child node until a cycle is formed. We return a *canonical* cycle,
@@ -348,18 +370,28 @@
// We are not concerned with optimizing the performance of phase 3 because in the intended application
// phase 3 can occur at most once in the lifetime of a program: Once an ill-founded node is detected the
// program exits with a cycle description allowing the user to fix the ill-foundedness.
-func (finder *cycleFinder) findKnownIllFoundedCycle(nodeHolder *nodeHolder) *CycleDescription {
+//
+// This method is recursive. To initiate the recursion |nodeHolder| should be set to the starting node and
+// |path| should be nil. In subsequent recursive calls |nodeHolder| is the current node of the walk and
+// |path| is the path from the starting node to the current node.
+func (finder *cycleFinder) findKnownIllFoundedCycle(nodeHolder *nodeHolder, path nodePath) *CycleDescription {
+ // If this is the start of the recursion initialize the path.
+ if path == nil {
+ path = make(nodePath, 0)
+ }
+
// Mark the current node as started
nodeHolder.state = vsVisitStarted
- finder.currentPath.Push(nodeHolder)
- for _, child := range nodeHolder.node.OutEdges() {
- childHolder := finder.holderForNode(child)
+ for _, edge := range nodeHolder.node.OutEdges() {
+ childHolder := finder.holderForNode(edge.Target)
if childHolder.state == vsVisitStarted {
// If the child has been started but not finished then we have found a cycle
// from the child to the current node back to the child.
- return newCycleDescription(finder.currentPath.elements, childHolder, nodeHolder)
+ path = append(path, pathElement{nodeHolder.node, edge})
+ return newCycleDescription(path, childHolder.node, nodeHolder.node)
} else if !childHolder.node.KnownWellFounded() {
- return finder.findKnownIllFoundedCycle(childHolder)
+ path = append(path, pathElement{nodeHolder.node, edge})
+ return finder.findKnownIllFoundedCycle(childHolder, path)
}
}
panic("Program logic error: Could not find a known ill-founded cycle.")
@@ -413,49 +445,6 @@
return nodeHolder
}
-//////////////////////////////////////////////
-/// nodeStack type
-//////////////////////////////////////////////
-
-// A nodeStack is a stack of *nodeHolders
-type nodeStack struct {
- elements []*nodeHolder
-}
-
-func (stack *nodeStack) Push(n *nodeHolder) {
- stack.elements = append(stack.elements, n)
-}
-
-func (stack *nodeStack) Size() int {
- return len(stack.elements)
-}
-
-func (stack *nodeStack) Pop() (n *nodeHolder) {
- lastIndex := stack.Size() - 1
- n = stack.elements[lastIndex]
- stack.elements = stack.elements[:lastIndex]
- return
-}
-
-func (stack *nodeStack) Peek() (n *nodeHolder) {
- return stack.elements[stack.Size()-1]
-}
-
-func (stack *nodeStack) String() string {
- var buffer bytes.Buffer
- fmt.Fprintf(&buffer, "[")
- first := true
- for _, e := range stack.elements {
- if !first {
- fmt.Fprintf(&buffer, ", ")
- }
- fmt.Fprintf(&buffer, "%s", e.node.DebugName())
- first = false
- }
- fmt.Fprintln(&buffer, "]")
- return buffer.String()
-}
-
///////////////////////////////////////////////////
/// NodeSet type
///////////////////////////////////////////////////
@@ -542,12 +531,12 @@
func compareNodeSets(expected, actual *NodeSet) error {
for n, _ := range expected.elements {
if !actual.Contains(n) {
- return fmt.Errorf("%s is in expected but not actual", n.node.DebugName())
+ return fmt.Errorf("%s is in expected but not actual", n.node.Name())
}
}
for n, _ := range actual.elements {
if !expected.Contains(n) {
- return fmt.Errorf("%s is in actual but not expected", n.node.DebugName())
+ return fmt.Errorf("%s is in actual but not expected", n.node.Name())
}
}
return nil
@@ -562,7 +551,7 @@
if !first {
fmt.Fprintf(&buffer, ", ")
}
- fmt.Fprintf(&buffer, "%s", e.node.DebugName())
+ fmt.Fprintf(&buffer, "%s", e.node.Name())
first = false
}
fmt.Fprintln(&buffer, "}")
@@ -576,39 +565,57 @@
///////////////////////////////////////////////////
type CycleDescription struct {
- first, last Node
- path []Node
+ First, Last Node
+ Path []OutEdge
}
func (c *CycleDescription) String() string {
var buffer bytes.Buffer
- fmt.Fprintf(&buffer, "first:%s", c.first.DebugName())
- fmt.Fprintf(&buffer, ", last:%s", c.last.DebugName())
+ fmt.Fprintf(&buffer, "first:%s", c.First.Name())
+ fmt.Fprintf(&buffer, ", last:%s", c.Last.Name())
fmt.Fprintf(&buffer, ", path:{")
- first := true
- for _, n := range c.path {
- if !first {
+ fmt.Fprintf(&buffer, "%s", c.First.Name())
+ for _, edge := range c.Path {
+ if edge.Target != c.First {
fmt.Fprintf(&buffer, ", ")
+ fmt.Fprintf(&buffer, "%s", edge.Target.Name())
}
- fmt.Fprintf(&buffer, "%s", n.DebugName())
- first = false
}
fmt.Fprintln(&buffer, "}")
return buffer.String()
}
-func newCycleDescription(path []*nodeHolder, first, last *nodeHolder) *CycleDescription {
+// newCycleDescription builds a CycleDescription based on the given data.
+// |path| should be a nodePath that ends with a cycle. That is it should look like
+// {x1, ->x2}, {x2, ->x3}, {x3, ->x4}, {x4, ->x5}, {x5, ->x2}
+//
+// |cycleStart| should be the first node of |path| included in the cycle. In
+// the above example it would be x2.
+//
+// |end| should be the last node of the path. In the above example it would be x5.
+//
+// The return value using our example would be:
+// {First: x2, Last: x5, Path:[{x2, x2->x3}, {x3, x3->x4}, {x4, x4->x5}, {x5, x5->x2}]}
+func newCycleDescription(path nodePath, cycleStart, end Node) *CycleDescription {
+ lastNode := path[len(path)-1].node
+ if lastNode != end {
+ panic(fmt.Sprintf("%s != %s", lastNode.Name(), end.Name()))
+ }
+ lastTarget := path[len(path)-1].edge.Target
+ if lastTarget != cycleStart {
+ panic(fmt.Sprintf("(%T)%s != (%T)%s", lastTarget, lastTarget.Name(), cycleStart, cycleStart.Name()))
+ }
description := CycleDescription{}
- description.first = first.node
- description.last = last.node
- description.path = make([]Node, 0, len(path))
- for _, n := range path {
- if len(description.path) > 0 || n.node == first.node {
- description.path = append(description.path, n.node)
+ description.First = cycleStart
+ description.Last = end
+ description.Path = make([]OutEdge, 0, len(path))
+ for _, element := range path {
+ if len(description.Path) > 0 || element.node == cycleStart {
+ description.Path = append(description.Path, element.edge)
}
}
- if description.path[len(description.path)-1] != last.node {
- panic(fmt.Sprintf("%s != %s", description.path[len(description.path)-1], last.node))
+ if description.Path[len(description.Path)-1].Target != cycleStart {
+ panic(fmt.Sprintf("%s != %s", description.Path[len(description.Path)-1].Target.Name(), cycleStart.Name()))
}
return &description
}
diff --git a/mojom/mojom_tool/utils/wellfounded_graphs_test.go b/mojom/mojom_tool/utils/wellfounded_graphs_test.go
index 958fa9a..5eb0898 100644
--- a/mojom/mojom_tool/utils/wellfounded_graphs_test.go
+++ b/mojom/mojom_tool/utils/wellfounded_graphs_test.go
@@ -20,18 +20,18 @@
// Is this node a square node?
isSquare bool
- // The list of out-edges. The elements will be *SimpleNodes.
- edges []Node
+ // The list of out-edges.
+ edges []OutEdge
// Cache the fact that |SetKnownWellFounded| has been invoked.
knownWellFounded bool
}
-func (node *SimpleNode) DebugName() string {
+func (node *SimpleNode) Name() string {
return fmt.Sprintf("Node%d", node.value)
}
-func (node *SimpleNode) OutEdges() []Node {
+func (node *SimpleNode) OutEdges() []OutEdge {
return node.edges
}
@@ -45,7 +45,7 @@
func (node *SimpleNode) SetKnownWellFounded() {
if node.knownWellFounded {
- panic(fmt.Sprintf("SetKnownWellFounded invoked twice on %s", node.DebugName()))
+ panic(fmt.Sprintf("SetKnownWellFounded invoked twice on %s", node.Name()))
}
node.knownWellFounded = true
}
@@ -54,7 +54,7 @@
func NewNode(value, numEdges int, isSquare bool) *SimpleNode {
node := new(SimpleNode)
node.value = value
- node.edges = make([]Node, numEdges)
+ node.edges = make([]OutEdge, numEdges)
node.isSquare = isSquare
return node
}
@@ -89,7 +89,7 @@
}
for index, connectionList := range connectionMatrix {
for i, target := range connectionList {
- nodes[index].edges[i] = nodes[target]
+ nodes[index].edges[i] = OutEdge{"", nodes[target]}
}
}
return
@@ -120,7 +120,7 @@
expectedMap[n] = true
}
for _, n := range actual {
- actualMap[n.DebugName()] = true
+ actualMap[n.Name()] = true
}
for _, n := range expected {
if _, ok := actualMap[n]; !ok {
@@ -128,8 +128,8 @@
}
}
for _, n := range actual {
- if _, ok := expectedMap[n.DebugName()]; !ok {
- return fmt.Errorf("%s: unexpected: %s, expected: %v, actual: %s", name, n.DebugName(), expected, NodeSliceToString(actual))
+ if _, ok := expectedMap[n.Name()]; !ok {
+ return fmt.Errorf("%s: unexpected: %s, expected: %v, actual: %s", name, n.Name(), expected, NodeSliceToString(actual))
}
}
return nil
@@ -143,7 +143,7 @@
if !first {
fmt.Fprintf(&buffer, ", ")
}
- fmt.Fprintf(&buffer, "%s", n.DebugName())
+ fmt.Fprintf(&buffer, "%s", n.Name())
first = false
}
fmt.Fprintln(&buffer, "]")
@@ -458,13 +458,13 @@
t.Fatalf("Case %d: Expected a cycle.", i)
}
if !strings.Contains(cycleDescription.String(), fmt.Sprintf("first:%s", c.expectedFirstA)) {
- t.Fatalf("Case %d: got=%s expectedFirst=%q", i, cycleDescription.String(), c.expectedFirstA)
+ t.Fatalf("Case %d: got=%s expectedFirstA=%q", i, cycleDescription.String(), c.expectedFirstA)
}
if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastA)) {
- t.Fatalf("Case %d: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastA)
+ t.Fatalf("Case %d: got=%s expectedLastA=%q", i, cycleDescription.String(), c.expectedLastA)
}
if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathA)) {
- t.Fatalf("Case %d: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathA)
+ t.Fatalf("Case %d: got=%s expectedPathA=%q", i, cycleDescription.String(), c.expectedPathA)
}
}
@@ -484,13 +484,13 @@
t.Fatalf("Case %dB: Expected a cycle.", i)
}
if !strings.Contains(cycleDescription.String(), fmt.Sprintf("first:%s", c.expectedFirstB)) {
- t.Fatalf("Case %dB: got=%s expectedFirst=%q", i, cycleDescription.String(), c.expectedFirstB)
+ t.Fatalf("Case %dB: got=%s expectedFirstB=%q", i, cycleDescription.String(), c.expectedFirstB)
}
if !strings.Contains(cycleDescription.String(), fmt.Sprintf("last:%s", c.expectedLastB)) {
- t.Fatalf("Case %dB: got=%s expectedLast=%q", i, cycleDescription.String(), c.expectedLastB)
+ t.Fatalf("Case %dB: got=%s expectedLastB=%q", i, cycleDescription.String(), c.expectedLastB)
}
if !strings.Contains(cycleDescription.String(), fmt.Sprintf("{%s}", c.expectedPathB)) {
- t.Fatalf("Case %dB: got=%s expectedPath=%q", i, cycleDescription.String(), c.expectedPathB)
+ t.Fatalf("Case %dB: got=%s expectedPathB=%q", i, cycleDescription.String(), c.expectedPathB)
}
}
}
