[tools] Add cnf library (Conjunctive normal form)
This will be used to parse the conditional expressions in the build
generator.
Change-Id: I95bf651f0e4b3b2d63265fee357426d7de1f2909
Reviewed-on: https://dawn-review.googlesource.com/c/dawn/+/147740
Auto-Submit: Ben Clayton <bclayton@google.com>
Reviewed-by: James Price <jrprice@google.com>
Commit-Queue: James Price <jrprice@google.com>
Kokoro: Kokoro <noreply+kokoro@google.com>
diff --git a/tools/src/cnf/cnf.go b/tools/src/cnf/cnf.go
new file mode 100644
index 0000000..185b90d
--- /dev/null
+++ b/tools/src/cnf/cnf.go
@@ -0,0 +1,19 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+// Package cnf provides utilities for parsing and operating on boolean
+// expressions in a Conjunctive Normal Form
+//
+// See: https://en.wikipedia.org/wiki/Conjunctive_normal_form
+package cnf
diff --git a/tools/src/cnf/decompose.go b/tools/src/cnf/decompose.go
new file mode 100644
index 0000000..3b01ce8
--- /dev/null
+++ b/tools/src/cnf/decompose.go
@@ -0,0 +1,59 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf
+
+import (
+ "dawn.googlesource.com/dawn/tools/src/container"
+)
+
+// / Decomposed holds a decomposed expression
+// / See Decompose()
+type Decomposed struct {
+ Ands []Ands // The decomposed Ands
+ Ors []Ors // The decomposed Ors
+ Unarys []Unary // The decomposed Unarys
+}
+
+// Decompose returns the unique Ands, Ors and Unarys that make up the expression.
+// If e has two or more OR expressions AND'd together, then Decomposed.Ands will
+// hold the deduplicated AND expressions, otherwise Decomposed.Ands will be
+// empty.
+// If e has two or more Unary expressions OR'd together, then Decomposed.ORs
+// will hold the deduplicated OR expressions, otherwise Decomposed.Ands will be
+// empty.
+// Decomposed.Unarys will hold all the deduplicated Unary expressions.
+func Decompose(e Expr) Decomposed {
+ ors := container.NewMap[Key, Ors]()
+ unarys := container.NewMap[Key, Unary]()
+ for _, o := range e {
+ for _, u := range o {
+ unarys.Add(u.Key(), u)
+ }
+ if len(o) > 1 {
+ ors.Add(o.Key(), o)
+ }
+ }
+ d := Decomposed{}
+ if len(e) > 1 {
+ d.Ands = []Ands{e}
+ }
+ if len(ors) > 0 {
+ d.Ors = ors.Values()
+ }
+ if len(unarys) > 0 {
+ d.Unarys = unarys.Values()
+ }
+ return d
+}
diff --git a/tools/src/cnf/decompose_test.go b/tools/src/cnf/decompose_test.go
new file mode 100644
index 0000000..229c9ff
--- /dev/null
+++ b/tools/src/cnf/decompose_test.go
@@ -0,0 +1,95 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf_test
+
+import (
+ "testing"
+
+ "dawn.googlesource.com/dawn/tools/src/cnf"
+ "github.com/google/go-cmp/cmp"
+)
+
+func TestDecompose(t *testing.T) {
+
+ for _, test := range []struct {
+ in string
+ expect cnf.Decomposed
+ }{
+ {
+ in: ``,
+ expect: cnf.Decomposed{},
+ },
+ {
+ in: `X`,
+ expect: cnf.Decomposed{
+ Unarys: []cnf.Unary{T("X")},
+ },
+ },
+ {
+ in: `X || Y`,
+ expect: cnf.Decomposed{
+ Ors: []cnf.Ors{{T("X"), T("Y")}},
+ Unarys: []cnf.Unary{T("X"), T("Y")},
+ },
+ },
+ {
+ in: `!X || Y`,
+ expect: cnf.Decomposed{
+ Ors: []cnf.Ors{{F("X"), T("Y")}},
+ Unarys: []cnf.Unary{F("X"), T("Y")},
+ },
+ },
+ {
+ in: `X || !Y`,
+ expect: cnf.Decomposed{
+ Ors: []cnf.Ors{{T("X"), F("Y")}},
+ Unarys: []cnf.Unary{T("X"), F("Y")},
+ },
+ },
+ {
+ in: `X || Y || Z`,
+ expect: cnf.Decomposed{
+ Ors: []cnf.Ors{{T("X"), T("Y"), T("Z")}},
+ Unarys: []cnf.Unary{T("X"), T("Y"), T("Z")},
+ },
+ },
+ {
+ in: `(X || Y) && Z`,
+ expect: cnf.Decomposed{
+ Ands: []cnf.Ands{{{T("X"), T("Y")}, {T("Z")}}},
+ Ors: []cnf.Ors{{T("X"), T("Y")}},
+ Unarys: []cnf.Unary{T("X"), T("Y"), T("Z")},
+ },
+ },
+ {
+ in: `(X || Y) && (X || Y)`,
+ expect: cnf.Decomposed{
+ Ands: []cnf.Ands{{{T("X"), T("Y")}, {T("X"), T("Y")}}},
+ Ors: []cnf.Ors{{T("X"), T("Y")}},
+ Unarys: []cnf.Unary{T("X"), T("Y")},
+ },
+ },
+ } {
+ expr, err := cnf.Parse(test.in)
+ if err != nil {
+ t.Errorf(`unexpected error returned from Parse('%v'): %v`, test.in, err)
+ continue
+ }
+ got := cnf.Decompose(expr)
+ if diff := cmp.Diff(test.expect, got); diff != "" {
+ t.Errorf("Decompose('%v') returned '%v'. Diff:\n%v", test.in, got, diff)
+ }
+ }
+}
diff --git a/tools/src/cnf/expr.go b/tools/src/cnf/expr.go
new file mode 100644
index 0000000..2466901
--- /dev/null
+++ b/tools/src/cnf/expr.go
@@ -0,0 +1,40 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf
+
+// 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
+// AND'd together.
+type Expr = Ands
+
+// Ands is a slice of Ors
+// Ands holds a sequence of OR'd expressions that are AND'd together:
+//
+// Ors[0] && Ors[1] && ... && Ors[n-1]
+type Ands []Ors
+
+// Ors is a slice of Unary
+// Ors holds a sequence of unary expressions that are OR'd together:
+//
+// Unary[0] || Unary[1] || ... || Unary[n-1]
+type Ors []Unary
+
+// Unary is a negatable variable
+type Unary struct {
+ // If true, Var is negated
+ Negate bool
+ // The name of the variable
+ Var string
+}
diff --git a/tools/src/cnf/format.go b/tools/src/cnf/format.go
new file mode 100644
index 0000000..fa96f48
--- /dev/null
+++ b/tools/src/cnf/format.go
@@ -0,0 +1,63 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf
+
+import (
+ "strings"
+
+ "dawn.googlesource.com/dawn/tools/src/transform"
+)
+
+// String returns the expression in a C-like syntax
+func (e Expr) String() string {
+ return e.Format(" && ", " || ", "!")
+}
+
+// String returns the expression in a C-like syntax
+func (o Ors) String() string {
+ return o.Format(" || ", "!")
+}
+
+// String returns the expression in a C-like syntax
+func (u Unary) String() string {
+ return u.Format("!")
+}
+
+// Format returns the expression using the provided operators
+func (e Expr) Format(and, or, not string) string {
+ parts, _ := transform.Slice(e, func(ors Ors) (string, error) {
+ if len(e) > 1 && len(ors) > 1 {
+ return "(" + ors.Format(or, not) + ")", nil
+ }
+ return ors.Format(or, not), nil
+ })
+ return strings.Join(parts, and)
+}
+
+// Format returns the expression using the provided operators
+func (o Ors) Format(or, not string) string {
+ parts, _ := transform.Slice(o, func(u Unary) (string, error) {
+ return u.Format(not), nil
+ })
+ return strings.Join(parts, or)
+}
+
+// Format returns the expression using the provided operator
+func (u Unary) Format(not string) string {
+ if u.Negate {
+ return "(" + not + u.Var + ")"
+ }
+ return u.Var
+}
diff --git a/tools/src/cnf/helpers_test.go b/tools/src/cnf/helpers_test.go
new file mode 100644
index 0000000..31af84b
--- /dev/null
+++ b/tools/src/cnf/helpers_test.go
@@ -0,0 +1,29 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf_test
+
+import (
+ "dawn.googlesource.com/dawn/tools/src/cnf"
+)
+
+// T returns a Unary with no negation
+func T(s string) cnf.Unary {
+ return cnf.Unary{Var: s}
+}
+
+// F returns a Unary with negation
+func F(s string) cnf.Unary {
+ return cnf.Unary{Var: s, Negate: true}
+}
diff --git a/tools/src/cnf/key.go b/tools/src/cnf/key.go
new file mode 100644
index 0000000..a37db90
--- /dev/null
+++ b/tools/src/cnf/key.go
@@ -0,0 +1,48 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf
+
+import (
+ "strings"
+
+ "dawn.googlesource.com/dawn/tools/src/transform"
+)
+
+// Key is a map key type returned by Key() methods on Ands, Ors and Unary.
+type Key string
+
+// Key returns a Key that can be used to sort the Ands
+func (e Ands) Key() Key {
+ parts, _ := transform.Slice(e, func(o Ors) (string, error) {
+ return string(o.Key()), nil
+ })
+ return Key(strings.Join(parts, "&&"))
+}
+
+// Key returns a Key that can be used to sort the Ors
+func (o Ors) Key() Key {
+ parts, _ := transform.Slice(o, func(u Unary) (string, error) {
+ return string(u.Key()), nil
+ })
+ return Key(strings.Join(parts, "||"))
+}
+
+// Key returns a Key that can be used to sort the Unary
+func (u Unary) Key() Key {
+ if u.Negate {
+ return Key(u.Var + "!")
+ }
+ return Key(u.Var)
+}
diff --git a/tools/src/cnf/ops.go b/tools/src/cnf/ops.go
new file mode 100644
index 0000000..551cd2e
--- /dev/null
+++ b/tools/src/cnf/ops.go
@@ -0,0 +1,52 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf
+
+import "dawn.googlesource.com/dawn/tools/src/transform"
+
+// And returns a new expression that represents (lhs ∧ rhs)
+func And(lhs, rhs Expr) Expr {
+ return append(append(Expr{}, lhs...), rhs...)
+}
+
+// Or returns a new expression that represents (lhs ∨ rhs)
+func Or(lhs, rhs Expr) Expr {
+ if len(lhs) == 0 {
+ return rhs
+ }
+ if len(rhs) == 0 {
+ return lhs
+ }
+ out := Expr{}
+ for _, aOrs := range lhs {
+ for _, bOrs := range rhs {
+ out = append(out, append(append(Ors{}, aOrs...), bOrs...))
+ }
+ }
+ return out
+}
+
+// Not returns a new expression that represents (¬expr)
+func Not(expr Expr) Expr {
+ // Transform each of the OR expressions into AND expressions where each unary is negated.
+ out := Expr{}
+ for _, o := range expr {
+ ands, _ := transform.Slice(o, func(u Unary) (Ors, error) {
+ return Ors{Unary{Negate: !u.Negate, Var: u.Var}}, nil
+ })
+ out = Or(out, ands)
+ }
+ return out
+}
diff --git a/tools/src/cnf/ops_test.go b/tools/src/cnf/ops_test.go
new file mode 100644
index 0000000..bc61dfa
--- /dev/null
+++ b/tools/src/cnf/ops_test.go
@@ -0,0 +1,360 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf_test
+
+import (
+ "testing"
+
+ "dawn.googlesource.com/dawn/tools/src/cnf"
+ "github.com/google/go-cmp/cmp"
+)
+
+func TestAnd(t *testing.T) {
+ type E = cnf.Expr
+ for _, test := range []struct {
+ lhs, rhs cnf.Expr
+ expect cnf.Expr
+ }{
+ { // And('', '') => ''
+ lhs: E{}, rhs: E{},
+ expect: E{},
+ },
+ { // And('X', '') => 'X'
+ lhs: E{{T("X")}}, rhs: E{},
+ expect: E{{T("X")}},
+ },
+ { // And('!X', '') => '!X'
+ lhs: E{{F("X")}}, rhs: E{},
+ expect: E{{F("X")}},
+ },
+ { // And('', 'X') => 'X'
+ lhs: E{}, rhs: E{{T("X")}},
+ expect: E{{T("X")}},
+ },
+ { // And('', '!X') => '!X'
+ lhs: E{}, rhs: E{{F("X")}},
+ expect: E{{F("X")}},
+ },
+ { // And('X', 'Y') => 'X && Y'
+ lhs: E{{T("X")}}, rhs: E{{T("Y")}},
+ expect: E{{T("X")}, {T("Y")}},
+ },
+ { // And('X', '!Y') => 'X && !Y'
+ lhs: E{{T("X")}}, rhs: E{{F("Y")}},
+ expect: E{{T("X")}, {F("Y")}},
+ },
+ { // And('Y', 'X') => 'Y && X'
+ lhs: E{{T("Y")}}, rhs: E{{T("X")}},
+ expect: E{{T("Y")}, {T("X")}},
+ },
+ { // And('!Y', 'X') => '!Y && X'
+ lhs: E{{F("Y")}}, rhs: E{{T("X")}},
+ expect: E{{F("Y")}, {T("X")}},
+ },
+ { // And('X && Y', 'Z') => 'X && Y && Z'
+ lhs: E{{T("X")}, {T("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{T("X")}, {T("Y")}, {T("Z")}},
+ },
+ { // And('!X && Y', 'Z') => '!X && Y && Z'
+ lhs: E{{F("X")}, {T("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{F("X")}, {T("Y")}, {T("Z")}},
+ },
+ { // And('X && !Y', 'Z') => 'X && !Y && Z'
+ lhs: E{{T("X")}, {F("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{T("X")}, {F("Y")}, {T("Z")}},
+ },
+ { // And('X && Y', '!Z') => 'X && Y && !Z'
+ lhs: E{{T("X")}, {T("Y")}}, rhs: E{{F("Z")}},
+ expect: E{{T("X")}, {T("Y")}, {F("Z")}},
+ },
+ { // And('X', 'Y && Z') => 'X && Y && Z'
+ lhs: E{{T("X")}}, rhs: E{{T("Y")}, {T("Z")}},
+ expect: E{{T("X")}, {T("Y")}, {T("Z")}},
+ },
+ { // And('!X', 'Y && Z') => '!X && Y && Z'
+ lhs: E{{F("X")}}, rhs: E{{T("Y")}, {T("Z")}},
+ expect: E{{F("X")}, {T("Y")}, {T("Z")}},
+ },
+ { // And('X', '!Y && Z') => 'X && !Y && Z'
+ lhs: E{{T("X")}}, rhs: E{{F("Y")}, {T("Z")}},
+ expect: E{{T("X")}, {F("Y")}, {T("Z")}},
+ },
+ { // And('X', 'Y && !Z') => 'X && Y && !Z'
+ lhs: E{{T("X")}}, rhs: E{{T("Y")}, {F("Z")}},
+ expect: E{{T("X")}, {T("Y")}, {F("Z")}},
+ },
+ { // And('X && Y', 'Y && Z') => 'X && Y && Y && Z'
+ lhs: E{{T("X")}, {T("Y")}}, rhs: E{{T("Y")}, {T("Z")}},
+ expect: E{{T("X")}, {T("Y")}, {T("Y")}, {T("Z")}},
+ },
+ { // And('!X && Y', 'Y && !Z') => '!X && Y && Y && !Z'
+ lhs: E{{F("X")}, {T("Y")}}, rhs: E{{T("Y")}, {F("Z")}},
+ expect: E{{F("X")}, {T("Y")}, {T("Y")}, {F("Z")}},
+ },
+ { // And('X || Y', 'Z') => '(X || Y) && Z'
+ lhs: E{{T("X"), T("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{T("X"), T("Y")}, {T("Z")}},
+ },
+ { // And('!X || Y', 'Z') => '(!X || Y) && Z'
+ lhs: E{{F("X"), T("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{F("X"), T("Y")}, {T("Z")}},
+ },
+ { // And('X || !Y', 'Z') => '(X || !Y) && Z'
+ lhs: E{{T("X"), F("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{T("X"), F("Y")}, {T("Z")}},
+ },
+ { // And('X || Y', '!Z') => '(X || Y) && !Z'
+ lhs: E{{T("X"), T("Y")}}, rhs: E{{F("Z")}},
+ expect: E{{T("X"), T("Y")}, {F("Z")}},
+ },
+ { // And('X', 'Y || Z') => 'X && (Y || Z)'
+ lhs: E{{T("X")}}, rhs: E{{T("Y"), T("Z")}},
+ expect: E{{T("X")}, {T("Y"), T("Z")}},
+ },
+ { // And('!X', 'Y || Z') => '!X && (Y || Z)'
+ lhs: E{{F("X")}}, rhs: E{{T("Y"), T("Z")}},
+ expect: E{{F("X")}, {T("Y"), T("Z")}},
+ },
+ { // And('X', '!Y || Z') => 'X && (!Y || Z)'
+ lhs: E{{T("X")}}, rhs: E{{F("Y"), T("Z")}},
+ expect: E{{T("X")}, {F("Y"), T("Z")}},
+ },
+ { // And('X', 'Y || !Z') => 'X && (Y || !Z)'
+ lhs: E{{T("X")}}, rhs: E{{T("Y"), F("Z")}},
+ expect: E{{T("X")}, {T("Y"), F("Z")}},
+ },
+ { // And('X || Y', 'Y || Z') => '(X || Y) && (Y || Z)'
+ lhs: E{{T("X"), T("Y")}}, rhs: E{{T("Y"), T("Z")}},
+ expect: E{{T("X"), T("Y")}, {T("Y"), T("Z")}},
+ },
+ { // And('!X || Y', 'Y || !Z') => '(!X || Y) && (Y || !Z)'
+ lhs: E{{F("X"), T("Y")}}, rhs: E{{T("Y"), F("Z")}},
+ expect: E{{F("X"), T("Y")}, {T("Y"), F("Z")}},
+ },
+ { // And('X || Y', 'Y && Z') => '(X || Y) && Y && Z'
+ lhs: E{{T("X"), T("Y")}}, rhs: E{{T("Y")}, {T("Z")}},
+ expect: E{{T("X"), T("Y")}, {T("Y")}, {T("Z")}},
+ },
+ { // And('!X && Y', 'Y || !Z') => '!X && Y && (Y || !Z)'
+ lhs: E{{F("X")}, {T("Y")}}, rhs: E{{T("Y"), F("Z")}},
+ expect: E{{F("X")}, {T("Y")}, {T("Y"), F("Z")}},
+ },
+ } {
+ got := cnf.And(test.lhs, test.rhs)
+ if diff := cmp.Diff(test.expect, got); diff != "" {
+ t.Errorf("And('%v', '%v') returned '%v'. Diff:\n%v", test.lhs, test.rhs, got, diff)
+ }
+ }
+}
+
+func TestOr(t *testing.T) {
+ type E = cnf.Expr
+ for _, test := range []struct {
+ lhs, rhs cnf.Expr
+ expect cnf.Expr
+ }{
+ { // Or('', '') => ''
+ lhs: E{}, rhs: E{},
+ expect: E{},
+ },
+ { // Or('X', '') => 'X'
+ lhs: E{{T("X")}}, rhs: E{},
+ expect: E{{T("X")}},
+ },
+ { // Or('!X', '') => '!X'
+ lhs: E{{F("X")}}, rhs: E{},
+ expect: E{{F("X")}},
+ },
+ { // Or('', 'X') => 'X'
+ lhs: E{}, rhs: E{{T("X")}},
+ expect: E{{T("X")}},
+ },
+ { // Or('', '!X') => '!X'
+ lhs: E{}, rhs: E{{F("X")}},
+ expect: E{{F("X")}},
+ },
+ { // Or('X', 'Y') => 'X || Y'
+ lhs: E{{T("X")}}, rhs: E{{T("Y")}},
+ expect: E{{T("X"), T("Y")}},
+ },
+ { // Or('X', '!Y') => 'X || !Y'
+ lhs: E{{T("X")}}, rhs: E{{F("Y")}},
+ expect: E{{T("X"), F("Y")}},
+ },
+ { // Or('Y', 'X') => 'Y || X'
+ lhs: E{{T("Y")}}, rhs: E{{T("X")}},
+ expect: E{{T("Y"), T("X")}},
+ },
+ { // Or('!Y', 'X') => '!Y || X'
+ lhs: E{{F("Y")}}, rhs: E{{T("X")}},
+ expect: E{{F("Y"), T("X")}},
+ },
+ { // Or('X && Y', 'Z') => '(X || Z) && (Y || Z)'
+ lhs: E{{T("X")}, {T("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{T("X"), T("Z")}, {T("Y"), T("Z")}},
+ },
+ { // Or('!X && Y', 'Z') => '(!X || Z) && (Y || Z)'
+ lhs: E{{F("X")}, {T("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{F("X"), T("Z")}, {T("Y"), T("Z")}},
+ },
+ { // Or('X && !Y', 'Z') => '(X || Z) && (!Y || Z)'
+ lhs: E{{T("X")}, {F("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{T("X"), T("Z")}, {F("Y"), T("Z")}},
+ },
+ { // Or('X && Y', '!Z') => '(X || !Z) && (Y || !Z)'
+ lhs: E{{T("X")}, {T("Y")}}, rhs: E{{F("Z")}},
+ expect: E{{T("X"), F("Z")}, {T("Y"), F("Z")}},
+ },
+ { // Or('X', 'Y && Z') => '(X || Y) && (X || Z)'
+ lhs: E{{T("X")}}, rhs: E{{T("Y")}, {T("Z")}},
+ expect: E{{T("X"), T("Y")}, {T("X"), T("Z")}},
+ },
+ { // Or('!X', 'Y && Z') => '(!X || Y) && (!X || Z)'
+ lhs: E{{F("X")}}, rhs: E{{T("Y")}, {T("Z")}},
+ expect: E{{F("X"), T("Y")}, {F("X"), T("Z")}},
+ },
+ { // Or('X', '!Y && Z') => '(X || !Y) && (X || Z)'
+ lhs: E{{T("X")}}, rhs: E{{F("Y")}, {T("Z")}},
+ expect: E{{T("X"), F("Y")}, {T("X"), T("Z")}},
+ },
+ { // Or('X', 'Y && !Z') => '(X || Y) && (X || !Z)'
+ lhs: E{{T("X")}}, rhs: E{{T("Y")}, {F("Z")}},
+ expect: E{{T("X"), T("Y")}, {T("X"), F("Z")}},
+ },
+ { // Or('X && Y', 'Z && W') => '(X || Z) && (X || W) && (Y || Z) && (Y || W)'
+ lhs: E{{T("X")}, {T("Y")}}, rhs: E{{T("Z")}, {T("W")}},
+ expect: E{{T("X"), T("Z")}, {T("X"), T("W")}, {T("Y"), T("Z")}, {T("Y"), T("W")}},
+ },
+ { // Or('!X && Y', 'Z && !W') => '(!X || Z) && (!X || !W) && (Y || Z) && (Y || !W)'
+ lhs: E{{F("X")}, {T("Y")}}, rhs: E{{T("Z")}, {F("W")}},
+ expect: E{{F("X"), T("Z")}, {F("X"), F("W")}, {T("Y"), T("Z")}, {T("Y"), F("W")}},
+ },
+ { // Or('X || Y', 'Z') => 'X || Y || Z'
+ lhs: E{{T("X"), T("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{T("X"), T("Y"), T("Z")}},
+ },
+ { // Or('!X || Y', 'Z') => '!X || Y || Z'
+ lhs: E{{F("X"), T("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{F("X"), T("Y"), T("Z")}},
+ },
+ { // Or('X || !Y', 'Z') => 'X || !Y || Z'
+ lhs: E{{T("X"), F("Y")}}, rhs: E{{T("Z")}},
+ expect: E{{T("X"), F("Y"), T("Z")}},
+ },
+ { // Or('X || Y', '!Z') => 'X || Y || !Z'
+ lhs: E{{T("X"), T("Y")}}, rhs: E{{F("Z")}},
+ expect: E{{T("X"), T("Y"), F("Z")}},
+ },
+ { // Or('X', 'Y || Z') => 'X || Y || Z'
+ lhs: E{{T("X")}}, rhs: E{{T("Y"), T("Z")}},
+ expect: E{{T("X"), T("Y"), T("Z")}},
+ },
+ { // Or('!X', 'Y || Z') => '!X || Y || Z'
+ lhs: E{{F("X")}}, rhs: E{{T("Y"), T("Z")}},
+ expect: E{{F("X"), T("Y"), T("Z")}},
+ },
+ { // Or('X', '!Y || Z') => 'X || !Y || Z'
+ lhs: E{{T("X")}}, rhs: E{{F("Y"), T("Z")}},
+ expect: E{{T("X"), F("Y"), T("Z")}},
+ },
+ { // Or('X', 'Y || !Z') => 'X || Y || !Z'
+ lhs: E{{T("X")}}, rhs: E{{T("Y"), F("Z")}},
+ expect: E{{T("X"), T("Y"), F("Z")}},
+ },
+ { // Or('X || Y', 'Y || Z') => 'X || Y || Y || Z'
+ lhs: E{{T("X"), T("Y")}}, rhs: E{{T("Y"), T("Z")}},
+ expect: E{{T("X"), T("Y"), T("Y"), T("Z")}},
+ },
+ { // Or('!X || Y', 'Y || !Z') => '!X || Y || Y || !Z'
+ lhs: E{{F("X"), T("Y")}}, rhs: E{{T("Y"), F("Z")}},
+ expect: E{{F("X"), T("Y"), T("Y"), F("Z")}},
+ },
+ { // Or('X || Y', 'Y && Z') => '(X || Y || Y) && (X || Y || Z)'
+ lhs: E{{T("X"), T("Y")}}, rhs: E{{T("Y")}, {T("Z")}},
+ expect: E{{T("X"), T("Y"), T("Y")}, {T("X"), T("Y"), T("Z")}},
+ },
+ { // Or('!X && Y', 'Z || !W') => '(!X || Z || !W) && (Y || Z || !W)'
+ lhs: E{{F("X")}, {T("Y")}}, rhs: E{{T("Z"), F("W")}},
+ expect: E{{F("X"), T("Z"), F("W")}, {T("Y"), T("Z"), F("W")}},
+ },
+ } {
+ got := cnf.Or(test.lhs, test.rhs)
+ if diff := cmp.Diff(test.expect, got); diff != "" {
+ t.Errorf("Or('%v', '%v') returned '%v'. Diff:\n%v", test.lhs, test.rhs, got, diff)
+ }
+ }
+}
+
+func TestNot(t *testing.T) {
+ type E = cnf.Expr
+ for _, test := range []struct {
+ expr cnf.Expr
+ expect cnf.Expr
+ }{
+ { // Not('') => ''
+ expr: E{},
+ expect: E{},
+ },
+ { // Not('X') => '!X'
+ expr: E{{T("X")}},
+ expect: E{{F("X")}},
+ },
+ { // Not('!X') => 'X'
+ expr: E{{F("X")}},
+ expect: E{{T("X")}},
+ },
+ { // Not('X || Y') => '!X && !Y'
+ expr: E{{T("X"), T("Y")}},
+ expect: E{{F("X")}, {F("Y")}},
+ },
+ { // Not('X || !Y') => '!X && Y'
+ expr: E{{T("X"), F("Y")}},
+ expect: E{{F("X")}, {T("Y")}},
+ },
+ { // Not('X && Y') => '!X || !Y'
+ expr: E{{T("X")}, {T("Y")}},
+ expect: E{{F("X"), F("Y")}},
+ },
+ { // Not('!X && Y') => 'X || !Y'
+ expr: E{{F("X")}, {T("Y")}},
+ expect: E{{T("X"), F("Y")}},
+ },
+ { // Not('(X || Y) && Z') => '(!X || !Z) && (!Y || !Z)'
+ expr: E{{T("X"), T("Y")}, {T("Z")}},
+ expect: E{{F("X"), F("Z")}, {F("Y"), F("Z")}},
+ },
+ { // Not('X && (Y || Z)') => '(!X || !Y) && (!X || !Z)'
+ expr: E{{T("X")}, {T("Y"), T("Z")}},
+ expect: E{{F("X"), F("Y")}, {F("X"), F("Z")}},
+ },
+ { // Not('X && (!Y || Z)') => '(!X || Y) && (!X || !Z)'
+ expr: E{{T("X")}, {F("Y"), T("Z")}},
+ expect: E{{F("X"), T("Y")}, {F("X"), F("Z")}},
+ },
+ { // Not('(X || Y) && (Z || W)') => '(!X || !Z) && (!X || !W) && (!Y || !Z) && (!Y || !W)'
+ expr: E{{T("X"), T("Y")}, {T("Z"), T("W")}},
+ expect: E{{F("X"), F("Z")}, {F("X"), F("W")}, {F("Y"), F("Z")}, {F("Y"), F("W")}},
+ },
+ { // Not('(X || !Y) && (!Z || W)') => '(!X || Z) && (!X || !W) && (Y || Z) && (Y || !W)'
+ expr: E{{T("X"), F("Y")}, {F("Z"), T("W")}},
+ expect: E{{F("X"), T("Z")}, {F("X"), F("W")}, {T("Y"), T("Z")}, {T("Y"), F("W")}},
+ },
+ } {
+ got := cnf.Not(test.expr)
+ if diff := cmp.Diff(test.expect, got); diff != "" {
+ t.Errorf("Not('%v') returned '%v'. Diff:\n%v", test.expr, got, diff)
+ }
+ }
+}
diff --git a/tools/src/cnf/optimize.go b/tools/src/cnf/optimize.go
new file mode 100644
index 0000000..6f61d97
--- /dev/null
+++ b/tools/src/cnf/optimize.go
@@ -0,0 +1,40 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf
+
+import (
+ "dawn.googlesource.com/dawn/tools/src/container"
+)
+
+// Optimize returns the expression with all duplicate unary expressions in the
+// ORs removed. The returned expression is sorted.
+func Optimize(e Expr) Expr {
+ m := container.NewMap[Key, Ors]()
+ for _, o := range e {
+ b := unique(o)
+ m.Add(b.Key(), b)
+ }
+ return m.Values()
+}
+
+// unique returns the o with all duplicate unary expressions removed
+// The returned OR expression list is sorted.
+func unique(o Ors) Ors {
+ m := container.NewMap[Key, Unary]()
+ for _, u := range o {
+ m.Add(u.Key(), u)
+ }
+ return m.Values()
+}
diff --git a/tools/src/cnf/optimize_test.go b/tools/src/cnf/optimize_test.go
new file mode 100644
index 0000000..fbb2b66
--- /dev/null
+++ b/tools/src/cnf/optimize_test.go
@@ -0,0 +1,66 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf_test
+
+import (
+ "testing"
+
+ "dawn.googlesource.com/dawn/tools/src/cnf"
+ "github.com/google/go-cmp/cmp"
+)
+
+func TestOptimize(t *testing.T) {
+ for _, test := range []struct {
+ in string
+ out string
+ }{
+ // no-ops
+ {in: `X`, out: `X`},
+ {in: `X && Y`, out: `X && Y`},
+ {in: `X && Y && Z`, out: `X && Y && Z`},
+ {in: `X || Y || Z`, out: `X || Y || Z`},
+ {in: `(X || Y) && (X || Z)`, out: `(X || Y) && (X || Z)`},
+
+ // Sorting
+ {in: `Z || X || Y`, out: `X || Y || Z`},
+ {in: `!Z || X || Y`, out: `X || Y || (!Z)`},
+ {in: `X || !X || Y`, out: `X || (!X) || Y`},
+ {in: `Z && X && Y`, out: `X && Y && Z`},
+ {in: `Z && !X && Y`, out: `(!X) && Y && Z`},
+
+ // Combine common
+ {in: `X || Y || X`, out: `X || Y`},
+ {in: `X && Y && X`, out: `X && Y`},
+ {in: `X && Y && X`, out: `X && Y`},
+ {in: `(X || Y) && (X || Y)`, out: `X || Y`},
+
+ // Complex cases
+ {in: `(X || Y) || (Y || Z)`, out: `X || Y || Z`},
+ {in: `(X || Y) || (Y && Z)`, out: `(X || Y) && (X || Y || Z)`},
+ {in: `(X && Y) && (Y && Z)`, out: `X && Y && Z`},
+ {in: `!(X && !(Y || Z)) && Z`, out: `((!X) || Y || Z) && Z`},
+ {in: `Z || !(X && !(Y || Z))`, out: `(!X) || Y || Z`},
+ } {
+ expr, err := cnf.Parse(test.in)
+ if err != nil {
+ t.Errorf(`unexpected error returned from Parse('%v'): %v`, test.in, err)
+ continue
+ }
+ opt := cnf.Optimize(expr)
+ if diff := cmp.Diff(test.out, opt.String()); diff != "" {
+ t.Errorf("Optimize('%v') returned '%v'. Diff:\n%v", test.in, opt, diff)
+ }
+ }
+}
diff --git a/tools/src/cnf/parse.go b/tools/src/cnf/parse.go
new file mode 100644
index 0000000..7e40b88
--- /dev/null
+++ b/tools/src/cnf/parse.go
@@ -0,0 +1,266 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf
+
+import (
+ "fmt"
+ "strings"
+ "unicode"
+)
+
+// Parse parses the string, returning an expression
+func Parse(s string) (Expr, error) {
+ tokens, err := lex(s)
+ if err != nil {
+ return nil, err
+ }
+ if len(tokens) == 0 {
+ return nil, nil
+ }
+ p := parser{string: s, tokens: tokens}
+ return p.parse()
+}
+
+type tokenKind string
+
+const (
+ tokEOF = "<end of expression>"
+ tokLParen = "("
+ tokRParen = ")"
+ tokIdent = "ident"
+ tokAnd = "&&"
+ tokOr = "||"
+ tokNot = "!"
+)
+
+type token struct {
+ kind tokenKind
+ start, end int
+}
+
+type parser struct {
+ string string
+ tokens []token
+}
+
+func (p *parser) parse() (Expr, error) {
+ return p.binary()
+}
+
+func (p *parser) binary() (Expr, error) {
+ expr, err := p.unary()
+ if err != nil {
+ return nil, err
+ }
+
+ var delimiter tokenKind
+ var op func(Expr, Expr) Expr
+
+ switch p.peek().kind {
+ case tokAnd:
+ delimiter, op = tokAnd, And
+ case tokOr:
+ delimiter, op = tokOr, Or
+ default:
+ return expr, nil
+ }
+
+ for {
+ switch p.peek().kind {
+ case delimiter:
+ p.next()
+ rhs, err := p.unary()
+ if err != nil {
+ return nil, err
+ }
+ expr = op(expr, rhs)
+ case tokRParen, tokEOF:
+ return expr, nil
+ case tokAnd, tokOr:
+ t := p.next()
+ return nil, p.err(t, "cannot mix '&&' and '||' without parentheses")
+ default:
+ t := p.next()
+ return nil, p.err(t, "expected '%v'", delimiter)
+ }
+ }
+}
+
+func (p *parser) unary() (Expr, error) {
+ if p.match(tokNot) {
+ expr, err := p.unary()
+ if err != nil {
+ return nil, err
+ }
+ return Not(expr), nil
+ }
+
+ // '(' binary ')'
+ if p.match(tokLParen) {
+ expr, err := p.binary()
+ if err != nil {
+ return nil, err
+ }
+ if _, err := p.expect(tokRParen); err != nil {
+ return nil, err
+ }
+ return expr, nil
+ }
+
+ return p.ident()
+}
+
+func (p *parser) ident() (Expr, error) {
+ identTok, err := p.expect(tokIdent)
+ if err != nil {
+ return nil, err
+ }
+ ident := p.string[identTok.start:identTok.end]
+ return Expr{{{Var: ident}}}, nil
+}
+
+func (p *parser) expect(t tokenKind) (token, error) {
+ got := p.next()
+ if t != got.kind {
+ if got.kind == tokEOF {
+ return token{}, p.err(got, "expected '%v'", t)
+ }
+ return token{}, p.err(got, "expected '%v', got '%v'", t, p.string[got.start:got.end])
+ }
+ return got, nil
+}
+
+func (p *parser) peek() token {
+ if len(p.tokens) == 0 {
+ return token{kind: tokEOF, start: len(p.string), end: len(p.string)}
+ }
+ return p.tokens[0]
+}
+
+func (p *parser) match(t tokenKind) bool {
+ if p.peek().kind == t {
+ p.next()
+ return true
+ }
+ return false
+}
+
+func (p *parser) next() token {
+ t := p.peek()
+ if len(p.tokens) > 0 {
+ p.tokens = p.tokens[1:]
+ }
+ return t
+}
+
+func (p *parser) err(t token, msg string, args ...any) error {
+ if t.end < t.start {
+ panic("token end is before start")
+ }
+ return ParseErr{
+ Start: t.start,
+ End: t.end,
+ Expression: p.string,
+ Message: fmt.Sprintf(msg, args...),
+ }
+}
+
+type ParseErr struct {
+ Start, End int
+ Expression string
+ Message string
+}
+
+func (e ParseErr) Error() string {
+ n := e.End - e.Start
+ if n == 0 {
+ n = 1
+ }
+ return fmt.Sprintf("Parse error:\n\n%v\n%v%v\n\n%v",
+ e.Expression,
+ strings.Repeat(" ", e.Start), strings.Repeat("^", n),
+ e.Message)
+}
+
+func lex(in string) ([]token, error) {
+ runes := []rune(in)
+ offset := 0
+
+ peek := func(i int) rune {
+ if offset+i < len(runes) {
+ return runes[offset+i]
+ }
+ return 0
+ }
+
+ advance := func(predicate func(r rune) bool) (start, end int) {
+ start = offset
+ for i, r := range runes[offset:] {
+ if !predicate(r) {
+ offset += i
+ return start, offset
+ }
+ }
+ offset = len(runes)
+ return start, offset
+ }
+
+ err := func(msg string, args ...any) ParseErr {
+ return ParseErr{
+ Start: offset,
+ End: offset + 1,
+ Expression: in,
+ Message: fmt.Sprintf(msg, args...),
+ }
+ }
+
+ tokens := []token{}
+ for offset < len(runes) {
+ advance(unicode.IsSpace)
+
+ p0 := peek(0)
+ switch {
+ case isIdentifier(p0):
+ start, end := advance(isIdentifier)
+ tokens = append(tokens, token{kind: tokIdent, start: start, end: end})
+ case p0 == '!':
+ tokens = append(tokens, token{kind: tokNot, start: offset, end: offset + 1})
+ offset++
+ case p0 == '(':
+ tokens = append(tokens, token{kind: tokLParen, start: offset, end: offset + 1})
+ offset++
+ case p0 == ')':
+ tokens = append(tokens, token{kind: tokRParen, start: offset, end: offset + 1})
+ offset++
+ default:
+ p1 := peek(1)
+ switch {
+ case p0 == '&' && p1 == '&':
+ tokens = append(tokens, token{kind: tokAnd, start: offset, end: offset + 2})
+ offset += 2
+ case p0 == '|' && p1 == '|':
+ tokens = append(tokens, token{kind: tokOr, start: offset, end: offset + 2})
+ offset += 2
+ default:
+ return nil, err("unexpected character '%c'", p0)
+ }
+ }
+ }
+ return tokens, nil
+}
+
+func isIdentifier(r rune) bool {
+ return unicode.IsLetter(r) || r == '_'
+}
diff --git a/tools/src/cnf/parse_test.go b/tools/src/cnf/parse_test.go
new file mode 100644
index 0000000..dcb04e4
--- /dev/null
+++ b/tools/src/cnf/parse_test.go
@@ -0,0 +1,153 @@
+// Copyright 2023 The Tint Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package cnf_test
+
+import (
+ "testing"
+
+ "dawn.googlesource.com/dawn/tools/src/cnf"
+ "github.com/google/go-cmp/cmp"
+)
+
+func TestParse(t *testing.T) {
+ for _, test := range []struct {
+ in string
+ expect cnf.Expr
+ }{
+ {in: ``, expect: nil},
+ {in: `X`, expect: cnf.Expr{{T("X")}}},
+ {in: `(X)`, expect: cnf.Expr{{T("X")}}},
+ {in: `((X))`, expect: cnf.Expr{{T("X")}}},
+ {in: `!X`, expect: cnf.Expr{{F("X")}}},
+ {in: `!(X)`, expect: cnf.Expr{{F("X")}}},
+ {in: `!!(X)`, expect: cnf.Expr{{T("X")}}},
+ {in: `(!(X))`, expect: cnf.Expr{{F("X")}}},
+ {in: `!(!(X))`, expect: cnf.Expr{{T("X")}}},
+ {in: `X && Y`, expect: cnf.Expr{{T("X")}, {T("Y")}}},
+ {in: `X && Y && Z`, expect: cnf.Expr{{T("X")}, {T("Y")}, {T("Z")}}},
+ {in: `X && !Y && Z`, expect: cnf.Expr{{T("X")}, {F("Y")}, {T("Z")}}},
+ {in: `!X && Y && !Z`, expect: cnf.Expr{{F("X")}, {T("Y")}, {F("Z")}}},
+ {in: `X || Y`, expect: cnf.Expr{{T("X"), T("Y")}}},
+ {in: `X || Y || Z`, expect: cnf.Expr{{T("X"), T("Y"), T("Z")}}},
+ {in: `X || !Y || Z`, expect: cnf.Expr{{T("X"), F("Y"), T("Z")}}},
+ {in: `!X || Y || !Z`, expect: cnf.Expr{{F("X"), T("Y"), F("Z")}}},
+ {in: `(X || Y) && Z`, expect: cnf.Expr{{T("X"), T("Y")}, {T("Z")}}},
+ {in: `( X || Y ) && Z`, expect: cnf.Expr{{T("X"), T("Y")}, {T("Z")}}},
+ {in: `X || (Y && Z)`, expect: cnf.Expr{{T("X"), T("Y")}, {T("X"), T("Z")}}},
+ {in: `(X && Y) || Z`, expect: cnf.Expr{{T("X"), T("Z")}, {T("Y"), T("Z")}}},
+ {in: `X && (Y || Z)`, expect: cnf.Expr{{T("X")}, {T("Y"), T("Z")}}},
+ {in: `(!X && Y) || Z`, expect: cnf.Expr{{F("X"), T("Z")}, {T("Y"), T("Z")}}},
+ {in: `(X && !Y) || Z`, expect: cnf.Expr{{T("X"), T("Z")}, {F("Y"), T("Z")}}},
+ {in: `(X && Y) || !Z`, expect: cnf.Expr{{T("X"), F("Z")}, {T("Y"), F("Z")}}},
+ {in: `!X && (Y || Z)`, expect: cnf.Expr{{F("X")}, {T("Y"), T("Z")}}},
+ {in: `!(!X && (Y || Z))`, expect: cnf.Expr{{T("X"), F("Y")}, {T("X"), F("Z")}}},
+ {in: `X && (!Y || Z)`, expect: cnf.Expr{{T("X")}, {F("Y"), T("Z")}}},
+ {in: `!(X && (!Y || Z))`, expect: cnf.Expr{{F("X"), T("Y")}, {F("X"), F("Z")}}},
+ {in: `X && (Y || !Z)`, expect: cnf.Expr{{T("X")}, {T("Y"), F("Z")}}},
+ {in: `X && !(!Y || Z)`, expect: cnf.Expr{{T("X")}, {T("Y")}, {F("Z")}}},
+ {in: `!(X && (Y || !Z))`, expect: cnf.Expr{{F("X"), F("Y")}, {F("X"), T("Z")}}},
+ {in: `!(X && !(Y || !Z))`, expect: cnf.Expr{{F("X"), T("Y"), F("Z")}}},
+ } {
+ expr, err := cnf.Parse(test.in)
+ if err != nil {
+ t.Errorf(`unexpected error returned from Parse('%v'): %v`, test.in, err)
+ continue
+ }
+ if diff := cmp.Diff(test.expect, expr); diff != "" {
+ t.Errorf("Parse('%v') returned '%v'. Diff:\n%v", test.in, expr, diff)
+ }
+ }
+}
+
+func TestParseErr(t *testing.T) {
+ for _, test := range []struct {
+ in string
+ expect string
+ }{
+ {
+ in: `)`,
+ expect: `Parse error:
+
+)
+^
+
+expected 'ident', got ')'`,
+ },
+ {
+ in: ` )`,
+ expect: `Parse error:
+
+ )
+ ^
+
+expected 'ident', got ')'`,
+ },
+ {
+ in: `(`,
+ expect: `Parse error:
+
+(
+ ^
+
+expected 'ident'`,
+ },
+ {
+ in: ` (`,
+ expect: `Parse error:
+
+ (
+ ^
+
+expected 'ident'`,
+ },
+ {
+ in: `(x`,
+ expect: `Parse error:
+
+(x
+ ^
+
+expected ')'`,
+ },
+ {
+ in: `((x)`,
+ expect: `Parse error:
+
+((x)
+ ^
+
+expected ')'`,
+ },
+ {
+ in: `X || Y && Z`,
+ expect: `Parse error:
+
+X || Y && Z
+ ^^
+
+cannot mix '&&' and '||' without parentheses`,
+ },
+ } {
+ _, err := cnf.Parse(test.in)
+ errStr := ""
+ if err != nil {
+ errStr = err.Error()
+ }
+ if test.expect != errStr {
+ t.Errorf(`unexpected error returned from Parse('%v'): %v`, test.in, err)
+ continue
+ }
+ }
+}
