[tools][gen] Validate includes to external libraries
Check that conditional external includes are correctly guarded.
Make the CNF logic smarter about expression reduction with assumed truths.
Change-Id: Icde6370be789037676a16625161b38704e96c48f
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/162401
Commit-Queue: Ben Clayton <bclayton@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
Reviewed-by: dan sinclair <dsinclair@chromium.org>
diff --git a/tools/src/cmd/gen/build/build.go b/tools/src/cmd/gen/build/build.go
index db2bbc0..a408148 100644
--- a/tools/src/cmd/gen/build/build.go
+++ b/tools/src/cmd/gen/build/build.go
@@ -443,6 +443,32 @@
return nil
}
+// checkInclude checks that the include statement is valid
+// file is the file that contains the include
+// include is the include statement
+// includeCondition holds the required conditions for the include
+func checkInclude(file *File, include Include, includeCondition Condition) error {
+ noneIfEmpty := func(cond Condition) string {
+ if len(cond) == 0 {
+ return "<none>"
+ }
+ return cond.String()
+ }
+ sourceConditions := cnf.And(cnf.And(include.Condition, file.Condition), file.Target.Condition)
+ targetConditions := includeCondition
+ if missing := targetConditions.AssumeTrue(sourceConditions); len(missing) > 0 {
+ return fmt.Errorf(`%v:%v #include "%v" requires guard: #if %v
+
+%v build conditions: %v
+%v build conditions: %v`,
+ file.Path(), include.Line, include.Path, strings.ToUpper(missing.String()),
+ file.Path(), noneIfEmpty(sourceConditions),
+ include.Path, targetConditions,
+ )
+ }
+ return nil
+}
+
// buildDependencies walks all the #includes in all files, building the dependency information for
// all targets and files in the project. Errors if any cyclic includes are found.
func buildDependencies(p *Project) error {
@@ -509,30 +535,19 @@
addExternalDependency(dependency)
}
- noneIfEmpty := func(cond Condition) string {
- if len(cond) == 0 {
- return "<none>"
- }
- return cond.String()
+ includeCondition := cnf.And(includeFile.Condition, includeFile.Target.Condition)
+ if err := checkInclude(file, include, includeCondition); err != nil {
+ return err
}
- sourceConditions := cnf.And(cnf.And(include.Condition, file.Condition), file.Target.Condition)
- targetConditions := cnf.And(includeFile.Condition, includeFile.Target.Condition)
- if missing := targetConditions.Remove(sourceConditions); len(missing) > 0 {
- return fmt.Errorf(`%v:%v #include "%v" requires guard: #if %v
-
-%v build conditions: %v
-%v build conditions: %v`,
- file.Path(), include.Line, include.Path, strings.ToUpper(missing.String()),
- file.Path(), noneIfEmpty(sourceConditions),
- include.Path, targetConditions,
- )
- }
-
} else {
// Check for external includes
for _, external := range p.externals.Values() {
if external.includePatternMatch(include.Path) {
addExternalDependency(external)
+
+ if err := checkInclude(file, include, external.Condition); err != nil {
+ return err
+ }
}
}
}
diff --git a/tools/src/cnf/expr.go b/tools/src/cnf/expr.go
index a3dec34..3b151a6 100644
--- a/tools/src/cnf/expr.go
+++ b/tools/src/cnf/expr.go
@@ -27,7 +27,9 @@
package cnf
-import "dawn.googlesource.com/dawn/tools/src/container"
+import (
+ "dawn.googlesource.com/dawn/tools/src/container"
+)
// Expr is a boolean expression, expressed in a Conjunctive Normal Form.
// Expr is an alias to Ands, which represent all the OR expressions that are
@@ -54,17 +56,25 @@
Var string
}
-// Remove returns a new expression with all the And expressions of o removed from e
-func (e Expr) Remove(o Expr) Expr {
- set := container.NewSet[Key]()
- for _, expr := range o {
- set.Add(expr.Key())
+// AssumeTrue returns a new simplified expression assuming o is true
+func (e Expr) AssumeTrue(o Expr) Expr {
+ isTrue := container.NewSet[Key]()
+ for _, ors := range o {
+ isTrue.Add(ors.Key())
}
+
out := Expr{}
- for _, expr := range e {
- if !set.Contains(expr.Key()) {
- out = append(out, expr)
+nextAnd:
+ for _, ors := range e {
+ for _, unary := range ors {
+ if isTrue.Contains(unary.Key()) {
+ continue nextAnd // At least one of the OR expressions is true
+ }
}
+ if isTrue.Contains(ors.Key()) {
+ continue // Whole OR expression is true
+ }
+ out = append(out, ors)
}
return out
}
diff --git a/tools/src/cnf/expr_test.go b/tools/src/cnf/expr_test.go
new file mode 100644
index 0000000..7636ee6
--- /dev/null
+++ b/tools/src/cnf/expr_test.go
@@ -0,0 +1,90 @@
+// Copyright 2023 The Dawn & Tint Authors
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are met:
+//
+// 1. Redistributions of source code must retain the above copyright notice, this
+// list of conditions and the following disclaimer.
+//
+// 2. Redistributions in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+//
+// 3. Neither the name of the copyright holder nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+package cnf_test
+
+import (
+ "testing"
+
+ "dawn.googlesource.com/dawn/tools/src/cnf"
+)
+
+func TestAssumeTrue(t *testing.T) {
+ for _, test := range []struct {
+ expr string
+ isTrue string
+ expect string
+ }{
+ {expr: ``, isTrue: ``, expect: ``},
+ {expr: `a`, isTrue: ``, expect: `a`},
+ {expr: `a`, isTrue: `!a`, expect: `a`},
+ {expr: `a`, isTrue: `!b`, expect: `a`},
+ {expr: `a`, isTrue: `c`, expect: `a`},
+ {expr: `a`, isTrue: `c`, expect: `a`},
+ {expr: `a || b`, isTrue: ``, expect: `a || b`},
+ {expr: `a || b`, isTrue: `!a`, expect: `a || b`},
+ {expr: `a || b`, isTrue: `!b`, expect: `a || b`},
+ {expr: `a || b`, isTrue: `c`, expect: `a || b`},
+ {expr: `a || b`, isTrue: `c`, expect: `a || b`},
+ {expr: `a && b`, isTrue: ``, expect: `a && b`},
+ {expr: `a && b`, isTrue: `!a`, expect: `a && b`},
+ {expr: `a && b`, isTrue: `!b`, expect: `a && b`},
+ {expr: `a && b`, isTrue: `c`, expect: `a && b`},
+ {expr: `a && b`, isTrue: `c`, expect: `a && b`},
+
+ {expr: `a`, isTrue: `a`, expect: ``},
+ {expr: `a || b`, isTrue: `a`, expect: ``},
+ {expr: `a || b`, isTrue: `b`, expect: ``},
+ {expr: `a && b`, isTrue: `a`, expect: `b`},
+ {expr: `a && b`, isTrue: `b`, expect: `a`},
+
+ {expr: `a`, isTrue: `a && b`, expect: ``},
+ {expr: `a || b`, isTrue: `a && b`, expect: ``},
+ {expr: `a || b`, isTrue: `b && b`, expect: ``},
+ {expr: `a && b`, isTrue: `a && b`, expect: ``},
+
+ {expr: `a && c`, isTrue: `a && b`, expect: `c`},
+ {expr: `(a || b) && c`, isTrue: `a && b`, expect: `c`},
+ {expr: `(a || b) && c`, isTrue: `b && c`, expect: ``},
+ {expr: `a && b && c`, isTrue: `a && b`, expect: `c`},
+ } {
+ expr, err := cnf.Parse(test.expr)
+ if err != nil {
+ t.Errorf(`unexpected error returned from Parse('%v'): %v`, test.expr, err)
+ continue
+ }
+ isTrue, err := cnf.Parse(test.isTrue)
+ if err != nil {
+ t.Errorf(`unexpected error returned from Parse('%v'): %v`, test.isTrue, err)
+ continue
+ }
+ got := expr.AssumeTrue(isTrue).String()
+ if test.expect != got {
+ t.Errorf("('%v').AssumeTrue('%v') returned '%v', expected '%v'", expr, isTrue, got, test.expect)
+ }
+ }
+}
