Repository: kubernetes-sigs/node-feature-discovery
Pull request #639 (2021-11-02 13:45:41)

source/custom: expression based label rules
Implement a framework for more flexible rule configuration and matching,
mimicking the MatchExpressions pattern from K8s nodeselector.

The basic building block is MatchExpression which contains an operator
and a list of values. The operator specifies that "function" that is
applied when evaluating a given input agains the list of values.
Available operators are:

- MatchIn
- MatchNotIn
- MatchInRegexp
- MatchExists
- MatchDoesNotExist
- MatchGt
- MatchLt
- MatchIsTrue
- MatchIsFalse

Another building block of the framework is MatchExpressionSet which is a
map of string-MatchExpression pairs. It is a helper for specifying
multiple expressions that can be matched against a set of set of
features.

This patch converts all existing custom rules to utilize the new
expression-based framework.

The PR also contains a separate patch that implement `GtLt`, an operator for checking that an input (integer) is between two values. The purpose of keeping this patch separate is to demonstrate the addition of new operators

marquiz: Depends on #604
/hold
k8s-ci-robot: [APPROVALNOTIFIER] This PR is **APPROVED**

This pull-request has been approved by: *<a href="https://github.com/kubernetes-sigs/node-feature-discovery/pull/639#" title="Author self-approved">marquiz</a>*

The full list of commands accepted by this bot can be found [here](https://go.k8s.io/bot-commands?repo=kubernetes-sigs%2Fnode-feature-discovery).

The pull request process is described [here](https://git.k8s.io/community/contributors/guide/owners.md#the-code-review-process)

<details >
Needs approval from an approver in each of these files:

- ~~[OWNERS](https://github.com/kubernetes-sigs/node-feature-discovery/blob/master/OWNERS)~~ [marquiz]

Approvers can indicate their approval by writing `/approve` in a comment
Approvers can cancel approval by writing `/approve cancel` in a comment
</details>
<!-- META={"approvers":[]} -->
marquiz: e2e-tests were failing but fixed, now
ArangoGutierrez: e2e-test
```bash
Ran 2 of 230 Specs in 26.560 seconds
SUCCESS! -- 2 Passed | 0 Failed | 0 Pending | 228 Skipped
--- PASS: TestE2E (26.58s)
PASS
ok      sigs.k8s.io/node-feature-discovery/test/e2e     26.615s
```

test
```bash
go test ./cmd/... ./pkg/... ./source/...                                                                               
?       sigs.k8s.io/node-feature-discovery/cmd/nfd-master       [no test files]                                        
ok      sigs.k8s.io/node-feature-discovery/cmd/nfd-topology-updater     (cached)                                       
ok      sigs.k8s.io/node-feature-discovery/cmd/nfd-worker       0.009s
?       sigs.k8s.io/node-feature-discovery/pkg/api/feature      [no test files]
?       sigs.k8s.io/node-feature-discovery/pkg/apihelper        [no test files]
?       sigs.k8s.io/node-feature-discovery/pkg/cpuid    [no test files]
ok      sigs.k8s.io/node-feature-discovery/pkg/kubeconf (cached)
?       sigs.k8s.io/node-feature-discovery/pkg/labeler  [no test files]
?       sigs.k8s.io/node-feature-discovery/pkg/nfd-client       [no test files]
ok      sigs.k8s.io/node-feature-discovery/pkg/nfd-client/topology-updater      (cached)
ok      sigs.k8s.io/node-feature-discovery/pkg/nfd-client/worker        3.088s
ok      sigs.k8s.io/node-feature-discovery/pkg/nfd-master       (cached)
?       sigs.k8s.io/node-feature-discovery/pkg/podres   [no test files]
ok      sigs.k8s.io/node-feature-discovery/pkg/resourcemonitor  (cached)
?       sigs.k8s.io/node-feature-discovery/pkg/topologypolicy   [no test files]
?       sigs.k8s.io/node-feature-discovery/pkg/topologyupdater  [no test files]
ok      sigs.k8s.io/node-feature-discovery/pkg/utils    (cached)
?       sigs.k8s.io/node-feature-discovery/pkg/version  [no test files]
ok      sigs.k8s.io/node-feature-discovery/source       0.004s
ok      sigs.k8s.io/node-feature-discovery/source/cpu   (cached)
?       sigs.k8s.io/node-feature-discovery/source/custom        [no test files]
ok      sigs.k8s.io/node-feature-discovery/source/custom/expression     0.078s
?       sigs.k8s.io/node-feature-discovery/source/custom/rules  [no test files]
?       sigs.k8s.io/node-feature-discovery/source/fake  [no test files]
?       sigs.k8s.io/node-feature-discovery/source/iommu [no test files]
ok      sigs.k8s.io/node-feature-discovery/source/kernel        (cached)
ok      sigs.k8s.io/node-feature-discovery/source/local (cached)
?       sigs.k8s.io/node-feature-discovery/source/memory        [no test files]
?       sigs.k8s.io/node-feature-discovery/source/network       [no test files]
ok      sigs.k8s.io/node-feature-discovery/source/pci   (cached)
?       sigs.k8s.io/node-feature-discovery/source/storage       [no test files]
ok      sigs.k8s.io/node-feature-discovery/source/system        (cached)
ok      sigs.k8s.io/node-feature-discovery/source/usb   (cached)
```
test image =`quay.io/eduardoarango/node-feature-discovery:639`
ArangoGutierrez: /assign
marquiz: /unhold

Patch:
diff --git a/source/custom/custom.go b/source/custom/custom.go
index 33abb7c7f..427f4a5cb 100644
--- a/source/custom/custom.go
+++ b/source/custom/custom.go
@@ -56,6 +56,10 @@ type customSource struct {
 	config *config
 }
 
+type legacyRule interface {
+	Match() (bool, error)
+}
+
 // Singleton source instance
 var (
 	src                           = customSource{config: newDefaultConfig()}
@@ -114,7 +118,7 @@ func (s *customSource) GetLabels() (source.FeatureLabels, error) {
 func (s *customSource) discoverFeature(feature FeatureSpec) (bool, error) {
 	for _, matchRules := range feature.MatchOn {
 
-		allRules := []rules.Rule{
+		allRules := []legacyRule{
 			matchRules.PciID,
 			matchRules.UsbID,
 			matchRules.LoadedKMod,
@@ -124,7 +128,7 @@ func (s *customSource) discoverFeature(feature FeatureSpec) (bool, error) {
 		}
 
 		// return true, nil if all rules match
-		matchRules := func(rules []rules.Rule) (bool, error) {
+		matchRules := func(rules []legacyRule) (bool, error) {
 			for _, rule := range rules {
 				if reflect.ValueOf(rule).IsNil() {
 					continue
diff --git a/source/custom/expression/expression.go b/source/custom/expression/expression.go
new file mode 100644
index 000000000..6ff961f03
--- /dev/null
+++ b/source/custom/expression/expression.go
@@ -0,0 +1,457 @@
+/*
+Copyright 2021 The Kubernetes 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 expression
+
+import (
+	"encoding/json"
+	"fmt"
+	"regexp"
+	"strconv"
+	"strings"
+
+	"k8s.io/klog/v2"
+
+	"sigs.k8s.io/node-feature-discovery/pkg/api/feature"
+)
+
+// MatchExpressionSet contains a set of MatchExpressions, each of which is
+// evaluated against a set of input values.
+type MatchExpressionSet map[string]*MatchExpression
+
+// MatchExpression specifies an expression to evaluate against a set of input
+// values. It contains an operator that is applied when matching the input and
+// an array of values that the operator evaluates the input against.
+// NB: CreateMatchExpression or MustCreateMatchExpression() should be used for
+//     creating new instances.
+// NB: Validate() must be called if Op or Value fields are modified or if a new
+//     instance is created from scratch without using the helper functions.
+type MatchExpression struct {
+	// Op is the operator to be applied.
+	Op MatchOp
+
+	// Value is the list of values that the operand evaluates the input
+	// against. Value should be empty if the operator is Exists, DoesNotExist,
+	// IsTrue or IsFalse. Value should contain exactly one element if the
+	// operator is Gt or Lt and exactly two elements if the operator is GtLt.
+	// In other cases Value should contain at least one element.
+	Value MatchValue `json:",omitempty"`
+
+	// valueRe caches compiled regexps for "InRegexp" operator
+	valueRe []*regexp.Regexp
+}
+
+// MatchOp is the match operator that is applied on values when evaluating a
+// MatchExpression.
+type MatchOp string
+
+// MatchValue is the list of values associated with a MatchExpression.
+type MatchValue []string
+
+const (
+	// MatchAny returns always true.
+	MatchAny MatchOp = ""
+	// MatchIn returns true if any of the values stored in the expression is
+	// equal to the input.
+	MatchIn MatchOp = "In"
+	// MatchIn returns true if none of the values in the expression are equal
+	// to the input.
+	MatchNotIn MatchOp = "NotIn"
+	// MatchInRegexp treats values of the expression as regular expressions and
+	// returns true if any of them matches the input.
+	MatchInRegexp MatchOp = "InRegexp"
+	// MatchExists returns true if the input is valid. The expression must not
+	// have any values.
+	MatchExists MatchOp = "Exists"
+	// MatchDoesNotExist returns true if the input is not valid. The expression
+	// must not have any values.
+	MatchDoesNotExist MatchOp = "DoesNotExist"
+	// MatchGt returns true if the input is greater than the value of the
+	// expression (number of values in the expression must be exactly one).
+	// Both the input and value must be integer numbers, otherwise an error is
+	// returned.
+	MatchGt MatchOp = "Gt"
+	// MatchLt returns true if the input is less  than the value of the
+	// expression (number of values in the expression must be exactly one).
+	// Both the input and value must be integer numbers, otherwise an error is
+	// returned.
+	MatchLt MatchOp = "Lt"
+	// MatchGtLt returns true if the input is between two values, i.e. greater
+	// than the first value and less than the second value of the expression
+	// (number of values in the expression must be exactly two). Both the input
+	// and values must be integer numbers, otherwise an error is returned.
+	MatchGtLt MatchOp = "GtLt"
+	// MatchIsTrue returns true if the input holds the value "true". The
+	// expression must not have any values.
+	MatchIsTrue MatchOp = "IsTrue"
+	// MatchIsTrue returns true if the input holds the value "false". The
+	// expression must not have any values.
+	MatchIsFalse MatchOp = "IsFalse"
+)
+
+var matchOps = map[MatchOp]struct{}{
+	MatchAny:          struct{}{},
+	MatchIn:           struct{}{},
+	MatchNotIn:        struct{}{},
+	MatchInRegexp:     struct{}{},
+	MatchExists:       struct{}{},
+	MatchDoesNotExist: struct{}{},
+	MatchGt:           struct{}{},
+	MatchLt:           struct{}{},
+	MatchGtLt:         struct{}{},
+	MatchIsTrue:       struct{}{},
+	MatchIsFalse:      struct{}{},
+}
+
+// CreateMatchExpression creates a new MatchExpression instance. Returns an
+// error if validation fails.
+func CreateMatchExpression(op MatchOp, values ...string) (*MatchExpression, error) {
+	m := newMatchExpression(op, values...)
+	return m, m.Validate()
+}
+
+// MustCreateMatchExpression creates a new MatchExpression instance. Panics if
+// validation fails.
+func MustCreateMatchExpression(op MatchOp, values ...string) *MatchExpression {
+	m, err := CreateMatchExpression(op, values...)
+	if err != nil {
+		panic(err)
+	}
+	return m
+}
+
+// newMatchExpression returns a new MatchExpression instance.
+func newMatchExpression(op MatchOp, values ...string) *MatchExpression {
+	return &MatchExpression{
+		Op:    op,
+		Value: values,
+	}
+}
+
+// Validate validates the expression.
+func (m *MatchExpression) Validate() error {
+	m.valueRe = nil
+
+	if _, ok := matchOps[m.Op]; !ok {
+		return fmt.Errorf("invalid Op %q", m.Op)
+	}
+	switch m.Op {
+	case MatchExists, MatchDoesNotExist, MatchIsTrue, MatchIsFalse, MatchAny:
+		if len(m.Value) != 0 {
+			return fmt.Errorf("Value must be empty for Op %q (have %v)", m.Op, m.Value)
+		}
+	case MatchGt, MatchLt:
+		if len(m.Value) != 1 {
+			return fmt.Errorf("Value must contain exactly one element for Op %q (have %v)", m.Op, m.Value)
+		}
+		if _, err := strconv.Atoi(m.Value[0]); err != nil {
+			return fmt.Errorf("Value must be an integer for Op %q (have %v)", m.Op, m.Value[0])
+		}
+	case MatchGtLt:
+		if len(m.Value) != 2 {
+			return fmt.Errorf("Value must contain exactly two elements for Op %q (have %v)", m.Op, m.Value)
+		}
+		var err error
+		v := make([]int, 2)
+		for i := 0; i < 2; i++ {
+			if v[i], err = strconv.Atoi(m.Value[i]); err != nil {
+				return fmt.Errorf("Value must contain integers for Op %q (have %v)", m.Op, m.Value)
+			}
+		}
+		if v[0] >= v[1] {
+			return fmt.Errorf("Value[0] must be less than Value[1] for Op %q (have %v)", m.Op, m.Value)
+		}
+	case MatchInRegexp:
+		if len(m.Value) == 0 {
+			return fmt.Errorf("Value must be non-empty for Op %q", m.Op)
+		}
+		m.valueRe = make([]*regexp.Regexp, len(m.Value))
+		for i, v := range m.Value {
+			re, err := regexp.Compile(v)
+			if err != nil {
+				return fmt.Errorf("Value must only contain valid regexps for Op %q (have %v)", m.Op, m.Value)
+			}
+			m.valueRe[i] = re
+		}
+	default:
+		if len(m.Value) == 0 {
+			return fmt.Errorf("Value must be non-empty for Op %q", m.Op)
+		}
+	}
+	return nil
+}
+
+// Match evaluates the MatchExpression against a single input value.
+func (m *MatchExpression) Match(valid bool, value interface{}) (bool, error) {
+	switch m.Op {
+	case MatchAny:
+		return true, nil
+	case MatchExists:
+		return valid, nil
+	case MatchDoesNotExist:
+		return !valid, nil
+	}
+
+	if valid {
+		value := fmt.Sprintf("%v", value)
+		switch m.Op {
+		case MatchIn:
+			for _, v := range m.Value {
+				if value == v {
+					return true, nil
+				}
+			}
+		case MatchNotIn:
+			for _, v := range m.Value {
+				if value == v {
+					return false, nil
+				}
+			}
+			return true, nil
+		case MatchInRegexp:
+			if m.valueRe == nil {
+				return false, fmt.Errorf("BUG: MatchExpression has not been initialized properly, regexps missing")
+			}
+			for _, re := range m.valueRe {
+				if re.MatchString(value) {
+					return true, nil
+				}
+			}
+		case MatchGt, MatchLt:
+			l, err := strconv.Atoi(value)
+			if err != nil {
+				return false, fmt.Errorf("not a number %q", value)
+			}
+			r, err := strconv.Atoi(m.Value[0])
+			if err != nil {
+				return false, fmt.Errorf("not a number %q in %v", m.Value[0], m)
+			}
+
+			if (l < r && m.Op == MatchLt) || (l > r && m.Op == MatchGt) {
+				return true, nil
+			}
+		case MatchGtLt:
+			v, err := strconv.Atoi(value)
+			if err != nil {
+				return false, fmt.Errorf("not a number %q", value)
+			}
+			lr := make([]int, 2)
+			for i := 0; i < 2; i++ {
+				lr[i], err = strconv.Atoi(m.Value[i])
+				if err != nil {
+					return false, fmt.Errorf("not a number %q in %v", m.Value[i], m)
+				}
+			}
+			return v > lr[0] && v < lr[1], nil
+		case MatchIsTrue:
+			return value == "true", nil
+		case MatchIsFalse:
+			return value == "false", nil
+		default:
+			return false, fmt.Errorf("unsupported Op %q", m.Op)
+		}
+	}
+	return false, nil
+}
+
+// MatchKeys evaluates the MatchExpression against a set of keys.
+func (m *MatchExpression) MatchKeys(name string, keys map[string]feature.Nil) (bool, error) {
+	klog.V(3).Infof("matching %q %q against %v", name, m.Op, keys)
+
+	_, ok := keys[name]
+	switch m.Op {
+	case MatchAny:
+		return true, nil
+	case MatchExists:
+		return ok, nil
+	case MatchDoesNotExist:
+		return !ok, nil
+	default:
+		return false, fmt.Errorf("invalid Op %q when matching keys", m.Op)
+	}
+}
+
+// MatchValues evaluates the MatchExpression against a set of key-value pairs.
+func (m *MatchExpression) MatchValues(name string, values map[string]string) (bool, error) {
+	klog.V(3).Infof("matching %q %q %v against %v", name, m.Op, m.Value, values)
+	v, ok := values[name]
+	return m.Match(ok, v)
+}
+
+// matchExpression is a helper type for unmarshalling MatchExpression
+type matchExpression MatchExpression
+
+// UnmarshalJSON implements the Unmarshaler interface of "encoding/json"
+func (m *MatchExpression) UnmarshalJSON(data []byte) error {
+	raw := new(interface{})
+
+	err := json.Unmarshal(data, raw)
+	if err != nil {
+		return err
+	}
+
+	switch v := (*raw).(type) {
+	case string:
+		*m = *newMatchExpression(MatchIn, v)
+	case bool:
+		*m = *newMatchExpression(MatchIn, strconv.FormatBool(v))
+	case float64:
+		*m = *newMatchExpression(MatchIn, strconv.FormatFloat(v, 'f', -1, 64))
+	case []interface{}:
+		values := make([]string, len(v))
+		for i, value := range v {
+			str, ok := value.(string)
+			if !ok {
+				return fmt.Errorf("invalid value %v in %v", value, v)
+			}
+			values[i] = str
+		}
+		*m = *newMatchExpression(MatchIn, values...)
+	case map[string]interface{}:
+		helper := &matchExpression{}
+		if err := json.Unmarshal(data, &helper); err != nil {
+			return err
+		}
+		*m = *newMatchExpression(helper.Op, helper.Value...)
+	default:
+		return fmt.Errorf("invalid rule '%v' (%T)", v, v)
+	}
+
+	return m.Validate()
+}
+
+// MatchKeys evaluates the MatchExpressionSet against a set of keys.
+func (m *MatchExpressionSet) MatchKeys(keys map[string]feature.Nil) (bool, error) {
+	for n, e := range *m {
+		match, err := e.MatchKeys(n, keys)
+		if err != nil {
+			return false, err
+		}
+		if !match {
+			return false, nil
+		}
+	}
+	return true, nil
+}
+
+// MatchValues evaluates the MatchExpressionSet against a set of key-value pairs.
+func (m *MatchExpressionSet) MatchValues(values map[string]string) (bool, error) {
+	for n, e := range *m {
+		match, err := e.MatchValues(n, values)
+		if err != nil {
+			return false, err
+		}
+		if !match {
+			return false, nil
+		}
+	}
+	return true, nil
+}
+
+// MatchInstances evaluates the MatchExpressionSet against a set of instance
+// features, each of which is an individual set of key-value pairs
+// (attributes).
+func (m *MatchExpressionSet) MatchInstances(instances []feature.InstanceFeature) (bool, error) {
+	for _, i := range instances {
+		if match, err := m.MatchValues(i.Attributes); err != nil {
+			return false, err
+		} else if match {
+			return true, nil
+		}
+	}
+	return false, nil
+}
+
+// UnmarshalJSON implements the Unmarshaler interface of "encoding/json".
+func (m *MatchExpressionSet) UnmarshalJSON(data []byte) error {
+	*m = make(MatchExpressionSet)
+
+	names := make([]string, 0)
+	if err := json.Unmarshal(data, &names); err == nil {
+		// Simplified slice form
+		for _, name := range names {
+			split := strings.SplitN(name, "=", 2)
+			if len(split) == 1 {
+				(*m)[split[0]] = newMatchExpression(MatchExists)
+			} else {
+				(*m)[split[0]] = newMatchExpression(MatchIn, split[1])
+			}
+		}
+	} else {
+		// Unmarshal the full map form
+		expressions := make(map[string]*MatchExpression)
+		if err := json.Unmarshal(data, &expressions); err != nil {
+			return err
+		} else {
+			for k, v := range expressions {
+				if v != nil {
+					(*m)[k] = v
+				} else {
+					(*m)[k] = newMatchExpression(MatchExists)
+				}
+			}
+		}
+	}
+
+	return nil
+}
+
+// UnmarshalJSON implements the Unmarshaler interface of "encoding/json".
+func (m *MatchOp) UnmarshalJSON(data []byte) error {
+	var raw string
+
+	if err := json.Unmarshal(data, &raw); err != nil {
+		return err
+	}
+
+	if _, ok := matchOps[MatchOp(raw)]; !ok {
+		return fmt.Errorf("invalid Op %q", raw)
+	}
+	*m = MatchOp(raw)
+	return nil
+}
+
+// UnmarshalJSON implements the Unmarshaler interface of "encoding/json".
+func (m *MatchValue) UnmarshalJSON(data []byte) error {
+	var raw interface{}
+
+	if err := json.Unmarshal(data, &raw); err != nil {
+		return err
+	}
+
+	switch v := raw.(type) {
+	case string:
+		*m = []string{v}
+	case bool:
+		*m = []string{strconv.FormatBool(v)}
+	case float64:
+		*m = []string{strconv.FormatFloat(v, 'f', -1, 64)}
+	case []interface{}:
+		values := make([]string, len(v))
+		for i, value := range v {
+			str, ok := value.(string)
+			if !ok {
+				return fmt.Errorf("invalid value %v in %v", value, v)
+			}
+			values[i] = str
+		}
+		*m = values
+	default:
+		return fmt.Errorf("invalid values '%v' (%T)", v, v)
+	}
+
+	return nil
+}
diff --git a/source/custom/rules/cpuid_rule.go b/source/custom/rules/cpuid_rule.go
index 40117e965..fda326aa1 100644
--- a/source/custom/rules/cpuid_rule.go
+++ b/source/custom/rules/cpuid_rule.go
@@ -21,21 +21,18 @@ import (
 
 	"sigs.k8s.io/node-feature-discovery/source"
 	"sigs.k8s.io/node-feature-discovery/source/cpu"
+	"sigs.k8s.io/node-feature-discovery/source/custom/expression"
 )
 
 // CpuIDRule implements Rule for the custom source
-type CpuIDRule []string
+type CpuIDRule struct {
+	expression.MatchExpressionSet
+}
 
-func (cpuids *CpuIDRule) Match() (bool, error) {
+func (r *CpuIDRule) Match() (bool, error) {
 	flags, ok := source.GetFeatureSource("cpu").GetFeatures().Keys[cpu.CpuidFeature]
 	if !ok {
 		return false, fmt.Errorf("cpuid information not available")
 	}
-
-	for _, f := range *cpuids {
-		if _, ok := flags.Elements[f]; !ok {
-			return false, nil
-		}
-	}
-	return true, nil
+	return r.MatchKeys(flags.Elements)
 }
diff --git a/source/custom/rules/kconfig_rule.go b/source/custom/rules/kconfig_rule.go
index d7cd3d9ce..a8c79a823 100644
--- a/source/custom/rules/kconfig_rule.go
+++ b/source/custom/rules/kconfig_rule.go
@@ -17,48 +17,22 @@ limitations under the License.
 package rules
 
 import (
-	"encoding/json"
 	"fmt"
-	"strings"
 
 	"sigs.k8s.io/node-feature-discovery/source"
+	"sigs.k8s.io/node-feature-discovery/source/custom/expression"
 	"sigs.k8s.io/node-feature-discovery/source/kernel"
 )
 
-// KconfigRule implements Rule
-type KconfigRule []kconfig
-
-type kconfig struct {
-	Name  string
-	Value string
+// KconfigRule implements Rule for the custom source
+type KconfigRule struct {
+	expression.MatchExpressionSet
 }
 
-func (kconfigs *KconfigRule) Match() (bool, error) {
+func (r *KconfigRule) Match() (bool, error) {
 	options, ok := source.GetFeatureSource("kernel").GetFeatures().Values[kernel.ConfigFeature]
 	if !ok {
 		return false, fmt.Errorf("kernel config options not available")
 	}
-
-	for _, f := range *kconfigs {
-		if v, ok := options.Elements[f.Name]; !ok || f.Value != v {
-			return false, nil
-		}
-	}
-	return true, nil
-}
-
-func (c *kconfig) UnmarshalJSON(data []byte) error {
-	var raw string
-	if err := json.Unmarshal(data, &raw); err != nil {
-		return err
-	}
-
-	split := strings.SplitN(raw, "=", 2)
-	c.Name = split[0]
-	if len(split) == 1 {
-		c.Value = "true"
-	} else {
-		c.Value = split[1]
-	}
-	return nil
+	return r.MatchValues(options.Elements)
 }
diff --git a/source/custom/rules/loaded_kmod_rule.go b/source/custom/rules/loaded_kmod_rule.go
index 1fdb546f8..38a3be060 100644
--- a/source/custom/rules/loaded_kmod_rule.go
+++ b/source/custom/rules/loaded_kmod_rule.go
@@ -20,24 +20,21 @@ import (
 	"fmt"
 
 	"sigs.k8s.io/node-feature-discovery/source"
+	"sigs.k8s.io/node-feature-discovery/source/custom/expression"
 	"sigs.k8s.io/node-feature-discovery/source/kernel"
 )
 
 // LoadedKModRule matches loaded kernel modules in the system
-type LoadedKModRule []string
+type LoadedKModRule struct {
+	expression.MatchExpressionSet
+}
 
 // Match loaded kernel modules on provided list of kernel modules
-func (kmods *LoadedKModRule) Match() (bool, error) {
+func (r *LoadedKModRule) Match() (bool, error) {
 	modules, ok := source.GetFeatureSource("kernel").GetFeatures().Keys[kernel.LoadedModuleFeature]
 	if !ok {
 		return false, fmt.Errorf("info about loaded modules not available")
 	}
 
-	for _, kmod := range *kmods {
-		if _, ok := modules.Elements[kmod]; !ok {
-			// kernel module not loaded
-			return false, nil
-		}
-	}
-	return true, nil
+	return r.MatchKeys(modules.Elements)
 }
diff --git a/source/custom/rules/nodename_rule.go b/source/custom/rules/nodename_rule.go
index f1a9af18a..7f5724f93 100644
--- a/source/custom/rules/nodename_rule.go
+++ b/source/custom/rules/nodename_rule.go
@@ -17,40 +17,35 @@ limitations under the License.
 package rules
 
 import (
+	"encoding/json"
 	"fmt"
-	"regexp"
-
-	"k8s.io/klog/v2"
 
 	"sigs.k8s.io/node-feature-discovery/source"
+	"sigs.k8s.io/node-feature-discovery/source/custom/expression"
 	"sigs.k8s.io/node-feature-discovery/source/system"
 )
 
 // NodenameRule matches on nodenames configured in a ConfigMap
-type NodenameRule []string
-
-// Force implementation of Rule
-var _ Rule = NodenameRule{}
+type NodenameRule struct {
+	expression.MatchExpression
+}
 
-func (n NodenameRule) Match() (bool, error) {
+func (r *NodenameRule) Match() (bool, error) {
 	nodeName, ok := source.GetFeatureSource("system").GetFeatures().Values[system.NameFeature].Elements["nodename"]
-	if !ok {
+	if !ok || nodeName == "" {
 		return false, fmt.Errorf("node name not available")
 	}
+	return r.MatchExpression.Match(true, nodeName)
+}
 
-	for _, nodenamePattern := range n {
-		klog.V(1).Infof("matchNodename %s", nodenamePattern)
-		match, err := regexp.MatchString(nodenamePattern, nodeName)
-		if err != nil {
-			klog.Errorf("nodename rule: invalid nodename regexp %q: %v", nodenamePattern, err)
-			continue
-		}
-		if !match {
-			klog.V(2).Infof("nodename rule: No match for pattern %q with node %q", nodenamePattern, nodeName)
-			continue
-		}
-		klog.V(2).Infof("nodename rule: Match for pattern %q with node %q", nodenamePattern, nodeName)
-		return true, nil
+func (r *NodenameRule) UnmarshalJSON(data []byte) error {
+	if err := json.Unmarshal(data, &r.MatchExpression); err != nil {
+		return err
+	}
+	// Force regexp matching
+	if r.Op == expression.MatchIn {
+		r.Op = expression.MatchInRegexp
 	}
-	return false, nil
+	// We need to run Validate() because operator forcing above
+	return r.Validate()
 }
diff --git a/source/custom/rules/pci_id_rule.go b/source/custom/rules/pci_id_rule.go
index 4ce7e97e4..28793e341 100644
--- a/source/custom/rules/pci_id_rule.go
+++ b/source/custom/rules/pci_id_rule.go
@@ -19,23 +19,13 @@ package rules
 import (
 	"fmt"
 
-	"sigs.k8s.io/node-feature-discovery/pkg/api/feature"
 	"sigs.k8s.io/node-feature-discovery/source"
+	"sigs.k8s.io/node-feature-discovery/source/custom/expression"
 	"sigs.k8s.io/node-feature-discovery/source/pci"
 )
 
-// Rule that matches on the following PCI device attributes: <class, vendor, device>
-// each device attribute will be a list elements(strings).
-// Match operation: OR will be performed per element and AND will be performed per attribute.
-// An empty attribute will not be included in the matching process.
-type PciIDRuleInput struct {
-	Class  []string `json:"class,omitempty"`
-	Vendor []string `json:"vendor,omitempty"`
-	Device []string `json:"device,omitempty"`
-}
-
 type PciIDRule struct {
-	PciIDRuleInput
+	expression.MatchExpressionSet
 }
 
 // Match PCI devices on provided PCI device attributes
@@ -45,46 +35,5 @@ func (r *PciIDRule) Match() (bool, error) {
 		return false, fmt.Errorf("cpuid information not available")
 	}
 
-	devAttr := map[string]bool{}
-	for _, attr := range []string{"class", "vendor", "device"} {
-		devAttr[attr] = true
-	}
-
-	for _, dev := range devs.Elements {
-		// match rule on a single device
-		if r.matchDevOnRule(dev) {
-			return true, nil
-		}
-	}
-	return false, nil
-}
-
-func (r *PciIDRule) matchDevOnRule(dev feature.InstanceFeature) bool {
-	if len(r.Class) == 0 && len(r.Vendor) == 0 && len(r.Device) == 0 {
-		return false
-	}
-
-	attrs := dev.Attributes
-	if len(r.Class) > 0 && !in(attrs["class"], r.Class) {
-		return false
-	}
-
-	if len(r.Vendor) > 0 && !in(attrs["vendor"], r.Vendor) {
-		return false
-	}
-
-	if len(r.Device) > 0 && !in(attrs["device"], r.Device) {
-		return false
-	}
-
-	return true
-}
-
-func in(item string, arr []string) bool {
-	for _, val := range arr {
-		if val == item {
-			return true
-		}
-	}
-	return false
+	return r.MatchInstances(devs.Elements)
 }
diff --git a/source/custom/rules/rule.go b/source/custom/rules/rule.go
deleted file mode 100644
index 5632fccd0..000000000
--- a/source/custom/rules/rule.go
+++ /dev/null
@@ -1,22 +0,0 @@
-/*
-Copyright 2020 The Kubernetes 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 rules
-
-type Rule interface {
-	// Match on rule
-	Match() (bool, error)
-}
diff --git a/source/custom/rules/usb_id_rule.go b/source/custom/rules/usb_id_rule.go
index 058ec357b..23f53e602 100644
--- a/source/custom/rules/usb_id_rule.go
+++ b/source/custom/rules/usb_id_rule.go
@@ -19,24 +19,13 @@ package rules
 import (
 	"fmt"
 
-	"sigs.k8s.io/node-feature-discovery/pkg/api/feature"
 	"sigs.k8s.io/node-feature-discovery/source"
+	"sigs.k8s.io/node-feature-discovery/source/custom/expression"
 	"sigs.k8s.io/node-feature-discovery/source/usb"
 )
 
-// Rule that matches on the following USB device attributes: <class, vendor, device>
-// each device attribute will be a list elements(strings).
-// Match operation: OR will be performed per element and AND will be performed per attribute.
-// An empty attribute will not be included in the matching process.
-type UsbIDRuleInput struct {
-	Class  []string `json:"class,omitempty"`
-	Vendor []string `json:"vendor,omitempty"`
-	Device []string `json:"device,omitempty"`
-	Serial []string `json:"serial,omitempty"`
-}
-
 type UsbIDRule struct {
-	UsbIDRuleInput
+	expression.MatchExpressionSet
 }
 
 // Match USB devices on provided USB device attributes
@@ -45,37 +34,5 @@ func (r *UsbIDRule) Match() (bool, error) {
 	if !ok {
 		return false, fmt.Errorf("usb device information not available")
 	}
-
-	for _, dev := range devs.Elements {
-		// match rule on a single device
-		if r.matchDevOnRule(dev) {
-			return true, nil
-		}
-	}
-	return false, nil
-}
-
-func (r *UsbIDRule) matchDevOnRule(dev feature.InstanceFeature) bool {
-	if len(r.Class) == 0 && len(r.Vendor) == 0 && len(r.Device) == 0 {
-		return false
-	}
-
-	attrs := dev.Attributes
-	if len(r.Class) > 0 && !in(attrs["class"], r.Class) {
-		return false
-	}
-
-	if len(r.Vendor) > 0 && !in(attrs["vendor"], r.Vendor) {
-		return false
-	}
-
-	if len(r.Device) > 0 && !in(attrs["device"], r.Device) {
-		return false
-	}
-
-	if len(r.Serial) > 0 && !in(attrs["serial"], r.Serial) {
-		return false
-	}
-
-	return true
+	return r.MatchInstances(devs.Elements)
 }
diff --git a/source/custom/static_features.go b/source/custom/static_features.go
index c3e48165b..3d632e479 100644
--- a/source/custom/static_features.go
+++ b/source/custom/static_features.go
@@ -17,6 +17,7 @@ limitations under the License.
 package custom
 
 import (
+	"sigs.k8s.io/node-feature-discovery/source/custom/expression"
 	"sigs.k8s.io/node-feature-discovery/source/custom/rules"
 )
 
@@ -29,7 +30,9 @@ func getStaticFeatureConfig() []FeatureSpec {
 			MatchOn: []MatchRule{
 				{
 					PciID: &rules.PciIDRule{
-						PciIDRuleInput: rules.PciIDRuleInput{Vendor: []string{"15b3"}},
+						MatchExpressionSet: expression.MatchExpressionSet{
+							"vendor": expression.MustCreateMatchExpression(expression.MatchIn, "15b3"),
+						},
 					},
 				},
 			},
@@ -38,7 +41,12 @@ func getStaticFeatureConfig() []FeatureSpec {
 			Name: "rdma.available",
 			MatchOn: []MatchRule{
 				{
-					LoadedKMod: &rules.LoadedKModRule{"ib_uverbs", "rdma_ucm"},
+					LoadedKMod: &rules.LoadedKModRule{
+						MatchExpressionSet: expression.MatchExpressionSet{
+							"ib_uverbs": expression.MustCreateMatchExpression(expression.MatchExists),
+							"rdma_ucm":  expression.MustCreateMatchExpression(expression.MatchExists),
+						},
+					},
 				},
 			},
 		},


Test patch:
diff --git a/source/custom/expression/expression_test.go b/source/custom/expression/expression_test.go
new file mode 100644
index 000000000..94b1681e3
--- /dev/null
+++ b/source/custom/expression/expression_test.go
@@ -0,0 +1,439 @@
+/*
+Copyright 2021 The Kubernetes 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 expression_test
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	"sigs.k8s.io/yaml"
+
+	"sigs.k8s.io/node-feature-discovery/pkg/api/feature"
+	e "sigs.k8s.io/node-feature-discovery/source/custom/expression"
+)
+
+type BoolAssertionFuncf func(assert.TestingT, bool, string, ...interface{}) bool
+
+type ValueAssertionFuncf func(assert.TestingT, interface{}, string, ...interface{}) bool
+
+func TestCreateMatchExpression(t *testing.T) {
+	type V = e.MatchValue
+	type TC struct {
+		op     e.MatchOp
+		values V
+		err    ValueAssertionFuncf
+	}
+
+	tcs := []TC{
+		{op: e.MatchAny, err: assert.Nilf}, // #0
+		{op: e.MatchAny, values: V{"1"}, err: assert.NotNilf},
+
+		{op: e.MatchIn, err: assert.NotNilf},
+		{op: e.MatchIn, values: V{"1"}, err: assert.Nilf},
+		{op: e.MatchIn, values: V{"1", "2", "3", "4"}, err: assert.Nilf},
+
+		{op: e.MatchNotIn, err: assert.NotNilf},
+		{op: e.MatchNotIn, values: V{"1"}, err: assert.Nilf},
+		{op: e.MatchNotIn, values: V{"1", "2"}, err: assert.Nilf},
+
+		{op: e.MatchInRegexp, err: assert.NotNilf},
+		{op: e.MatchInRegexp, values: V{"1"}, err: assert.Nilf},
+		{op: e.MatchInRegexp, values: V{"()", "2", "3"}, err: assert.Nilf},
+		{op: e.MatchInRegexp, values: V{"("}, err: assert.NotNilf},
+
+		{op: e.MatchExists, err: assert.Nilf},
+		{op: e.MatchExists, values: V{"1"}, err: assert.NotNilf},
+
+		{op: e.MatchDoesNotExist, err: assert.Nilf},
+		{op: e.MatchDoesNotExist, values: V{"1"}, err: assert.NotNilf},
+
+		{op: e.MatchGt, err: assert.NotNilf},
+		{op: e.MatchGt, values: V{"1"}, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"-10"}, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"1", "2"}, err: assert.NotNilf},
+		{op: e.MatchGt, values: V{""}, err: assert.NotNilf},
+
+		{op: e.MatchLt, err: assert.NotNilf},
+		{op: e.MatchLt, values: V{"1"}, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"-1"}, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"1", "2", "3"}, err: assert.NotNilf},
+		{op: e.MatchLt, values: V{"a"}, err: assert.NotNilf},
+
+		{op: e.MatchGtLt, err: assert.NotNilf},
+		{op: e.MatchGtLt, values: V{"1"}, err: assert.NotNilf},
+		{op: e.MatchGtLt, values: V{"1", "2"}, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"2", "1"}, err: assert.NotNilf},
+		{op: e.MatchGtLt, values: V{"1", "2", "3"}, err: assert.NotNilf},
+		{op: e.MatchGtLt, values: V{"a", "2"}, err: assert.NotNilf},
+
+		{op: e.MatchIsTrue, err: assert.Nilf},
+		{op: e.MatchIsTrue, values: V{"1"}, err: assert.NotNilf},
+
+		{op: e.MatchIsFalse, err: assert.Nilf},
+		{op: e.MatchIsFalse, values: V{"1", "2"}, err: assert.NotNilf},
+	}
+
+	for i, tc := range tcs {
+		_, err := e.CreateMatchExpression(tc.op, tc.values...)
+		tc.err(t, err, "test case #%d (%v) failed", i, tc)
+	}
+}
+
+func TestMatch(t *testing.T) {
+	type V = e.MatchValue
+	type TC struct {
+		op     e.MatchOp
+		values V
+		input  interface{}
+		valid  bool
+		result BoolAssertionFuncf
+		err    ValueAssertionFuncf
+	}
+
+	tcs := []TC{
+		{op: e.MatchAny, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchAny, input: "2", valid: false, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchIn, values: V{"1"}, input: "2", valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIn, values: V{"1"}, input: "2", valid: true, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIn, values: V{"1", "2", "3"}, input: "2", valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIn, values: V{"1", "2", "3"}, input: "2", valid: true, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchNotIn, values: V{"2"}, input: 2, valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchNotIn, values: V{"1"}, input: 2, valid: true, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchNotIn, values: V{"1", "2", "3"}, input: "2", valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchNotIn, values: V{"1", "2", "3"}, input: "2", valid: true, result: assert.Falsef, err: assert.Nilf},
+
+		{op: e.MatchInRegexp, values: V{"val-[0-9]$"}, input: "val-1", valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchInRegexp, values: V{"val-[0-9]$"}, input: "val-1", valid: true, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchInRegexp, values: V{"val-[0-9]$"}, input: "val-12", valid: true, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchInRegexp, values: V{"val-[0-9]$", "al-[1-9]"}, input: "val-12", valid: true, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchExists, input: nil, valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchExists, input: nil, valid: true, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchDoesNotExist, input: false, valid: false, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchDoesNotExist, input: false, valid: true, result: assert.Falsef, err: assert.Nilf},
+
+		{op: e.MatchGt, values: V{"2"}, input: 3, valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"2"}, input: 2, valid: true, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"2"}, input: 3, valid: true, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"-10"}, input: -3, valid: true, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"2"}, input: "3a", valid: true, result: assert.Falsef, err: assert.NotNilf},
+
+		{op: e.MatchLt, values: V{"2"}, input: "1", valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"2"}, input: "2", valid: true, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"-10"}, input: -3, valid: true, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"2"}, input: "1", valid: true, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"2"}, input: "1.0", valid: true, result: assert.Falsef, err: assert.NotNilf},
+
+		{op: e.MatchGtLt, values: V{"1", "10"}, input: "1", valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"1", "10"}, input: "1", valid: true, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"1", "10"}, input: "10", valid: true, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"1", "10"}, input: "2", valid: true, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"1", "10"}, input: "1.0", valid: true, result: assert.Falsef, err: assert.NotNilf},
+
+		{op: e.MatchIsTrue, input: true, valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIsTrue, input: true, valid: true, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchIsTrue, input: false, valid: true, result: assert.Falsef, err: assert.Nilf},
+
+		{op: e.MatchIsFalse, input: "false", valid: false, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIsFalse, input: "false", valid: true, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchIsFalse, input: "true", valid: true, result: assert.Falsef, err: assert.Nilf},
+	}
+
+	for i, tc := range tcs {
+		me := e.MustCreateMatchExpression(tc.op, tc.values...)
+		res, err := me.Match(tc.valid, tc.input)
+		tc.result(t, res, "test case #%d (%v) failed", i, tc)
+		tc.err(t, err, "test case #%d (%v) failed", i, tc)
+	}
+
+	// Check some special error cases separately because MustCreateMatch panics
+	tcs = []TC{
+
+		{op: e.MatchGt, values: V{"3.0"}, input: 1, valid: true},
+		{op: e.MatchLt, values: V{"0x2"}, input: 1, valid: true},
+		{op: e.MatchGtLt, values: V{"1", "str"}, input: 1, valid: true},
+		{op: "non-existent-op", values: V{"1"}, input: 1, valid: true},
+	}
+
+	for i, tc := range tcs {
+		me := e.MatchExpression{Op: tc.op, Value: tc.values}
+		res, err := me.Match(tc.valid, tc.input)
+		assert.Falsef(t, res, "err test case #%d (%v) failed", i, tc)
+		assert.NotNilf(t, err, "err test case #%d (%v) failed", i, tc)
+	}
+}
+
+func TestMatchKeys(t *testing.T) {
+	type V = e.MatchValue
+	type I = map[string]feature.Nil
+	type TC struct {
+		op     e.MatchOp
+		values V
+		name   string
+		input  I
+		result BoolAssertionFuncf
+		err    ValueAssertionFuncf
+	}
+
+	tcs := []TC{
+		{op: e.MatchAny, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchExists, name: "foo", input: nil, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchExists, name: "foo", input: I{"bar": {}}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchExists, name: "foo", input: I{"bar": {}, "foo": {}}, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchDoesNotExist, name: "foo", input: nil, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchDoesNotExist, name: "foo", input: I{}, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchDoesNotExist, name: "foo", input: I{"bar": {}}, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchDoesNotExist, name: "foo", input: I{"bar": {}, "foo": {}}, result: assert.Falsef, err: assert.Nilf},
+
+		// All other ops should return an error
+		{op: e.MatchIn, values: V{"foo"}, name: "foo", result: assert.Falsef, err: assert.NotNilf},
+		{op: e.MatchNotIn, values: V{"foo"}, name: "foo", result: assert.Falsef, err: assert.NotNilf},
+		{op: e.MatchInRegexp, values: V{"foo"}, name: "foo", result: assert.Falsef, err: assert.NotNilf},
+		{op: e.MatchGt, values: V{"1"}, name: "foo", result: assert.Falsef, err: assert.NotNilf},
+		{op: e.MatchLt, values: V{"1"}, name: "foo", result: assert.Falsef, err: assert.NotNilf},
+		{op: e.MatchGtLt, values: V{"1", "10"}, name: "foo", result: assert.Falsef, err: assert.NotNilf},
+		{op: e.MatchIsTrue, name: "foo", result: assert.Falsef, err: assert.NotNilf},
+		{op: e.MatchIsFalse, name: "foo", result: assert.Falsef, err: assert.NotNilf},
+	}
+
+	for i, tc := range tcs {
+		me := e.MustCreateMatchExpression(tc.op, tc.values...)
+		res, err := me.MatchKeys(tc.name, tc.input)
+		tc.result(t, res, "test case #%d (%v) failed", i, tc)
+		tc.err(t, err, "test case #%d (%v) failed", i, tc)
+	}
+}
+
+func TestMatchValues(t *testing.T) {
+	type V = []string
+	type I = map[string]string
+
+	type TC struct {
+		op     e.MatchOp
+		values V
+		name   string
+		input  I
+		result BoolAssertionFuncf
+		err    ValueAssertionFuncf
+	}
+
+	tcs := []TC{
+		{op: e.MatchAny, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchIn, values: V{"1", "2"}, name: "foo", input: I{"bar": "2"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIn, values: V{"1", "2"}, name: "foo", input: I{"foo": "3"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIn, values: V{"1", "2"}, name: "foo", input: I{"foo": "2"}, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchNotIn, values: V{"1", "2"}, name: "foo", input: I{"bar": "2"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchNotIn, values: V{"1", "2"}, name: "foo", input: I{"foo": "3"}, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchNotIn, values: V{"1", "2"}, name: "foo", input: I{"foo": "2"}, result: assert.Falsef, err: assert.Nilf},
+
+		{op: e.MatchInRegexp, values: V{"1", "2"}, name: "foo", input: I{"bar": "2"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchInRegexp, values: V{"1", "[0-8]"}, name: "foo", input: I{"foo": "9"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchInRegexp, values: V{"1", "[0-8]"}, name: "foo", input: I{"foo": "2"}, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchExists, name: "foo", input: I{"bar": "1"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchExists, name: "foo", input: I{"foo": "1"}, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchDoesNotExist, name: "foo", input: nil, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchDoesNotExist, name: "foo", input: I{"foo": "1"}, result: assert.Falsef, err: assert.Nilf},
+
+		{op: e.MatchGt, values: V{"2"}, name: "foo", input: I{"bar": "3"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"2"}, name: "foo", input: I{"bar": "3", "foo": "2"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"2"}, name: "foo", input: I{"bar": "3", "foo": "3"}, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchGt, values: V{"2"}, name: "foo", input: I{"bar": "str", "foo": "str"}, result: assert.Falsef, err: assert.NotNilf},
+
+		{op: e.MatchLt, values: V{"2"}, name: "foo", input: I{"bar": "1"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"2"}, name: "foo", input: I{"bar": "1", "foo": "2"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"2"}, name: "foo", input: I{"bar": "1", "foo": "1"}, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchLt, values: V{"2"}, name: "foo", input: I{"bar": "str", "foo": "str"}, result: assert.Falsef, err: assert.NotNilf},
+
+		{op: e.MatchGtLt, values: V{"-10", "10"}, name: "foo", input: I{"bar": "1"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"-10", "10"}, name: "foo", input: I{"bar": "1", "foo": "11"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"-10", "10"}, name: "foo", input: I{"bar": "1", "foo": "-11"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"-10", "10"}, name: "foo", input: I{"bar": "1", "foo": "1"}, result: assert.Truef, err: assert.Nilf},
+		{op: e.MatchGtLt, values: V{"-10", "10"}, name: "foo", input: I{"bar": "str", "foo": "str"}, result: assert.Falsef, err: assert.NotNilf},
+
+		{op: e.MatchIsTrue, name: "foo", result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIsTrue, name: "foo", input: I{"foo": "1"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIsTrue, name: "foo", input: I{"foo": "true"}, result: assert.Truef, err: assert.Nilf},
+
+		{op: e.MatchIsFalse, name: "foo", input: I{"foo": "true"}, result: assert.Falsef, err: assert.Nilf},
+		{op: e.MatchIsFalse, name: "foo", input: I{"foo": "false"}, result: assert.Truef, err: assert.Nilf},
+	}
+
+	for i, tc := range tcs {
+		me := e.MustCreateMatchExpression(tc.op, tc.values...)
+		res, err := me.MatchValues(tc.name, tc.input)
+		tc.result(t, res, "test case #%d (%v) failed", i, tc)
+		tc.err(t, err, "test case #%d (%v) failed", i, tc)
+	}
+}
+
+func TestMESMatchKeys(t *testing.T) {
+	type I = map[string]feature.Nil
+	type TC struct {
+		mes    string
+		input  I
+		result BoolAssertionFuncf
+		err    ValueAssertionFuncf
+	}
+
+	tcs := []TC{
+		{result: assert.Truef, err: assert.Nilf},
+
+		{input: I{"foo": {}}, result: assert.Truef, err: assert.Nilf},
+
+		{mes: `
+foo: { op: DoesNotExist }
+bar: { op: Exists }
+`,
+			input:  I{"bar": {}, "baz": {}},
+			result: assert.Truef, err: assert.Nilf},
+
+		{mes: `
+foo: { op: DoesNotExist }
+bar: { op: Exists }
+`,
+			input:  I{"foo": {}, "bar": {}, "baz": {}},
+			result: assert.Falsef, err: assert.Nilf},
+
+		{mes: `
+foo: { op: In, value: ["bar"] }
+bar: { op: Exists }
+`,
+			input:  I{"bar": {}, "baz": {}},
+			result: assert.Falsef, err: assert.NotNilf},
+	}
+
+	for i, tc := range tcs {
+		mes := &e.MatchExpressionSet{}
+		if err := yaml.Unmarshal([]byte(tc.mes), mes); err != nil {
+			t.Fatalf("failed to parse data of test case #%d (%v): %v", i, tc, err)
+		}
+
+		res, err := mes.MatchKeys(tc.input)
+		tc.result(t, res, "test case #%d (%v) failed", i, tc)
+		tc.err(t, err, "test case #%d (%v) failed", i, tc)
+	}
+}
+
+func TestMESMatchValues(t *testing.T) {
+	type I = map[string]string
+	type TC struct {
+		mes    string
+		input  I
+		result BoolAssertionFuncf
+		err    ValueAssertionFuncf
+	}
+
+	tcs := []TC{
+		{result: assert.Truef, err: assert.Nilf},
+
+		{input: I{"foo": "bar"}, result: assert.Truef, err: assert.Nilf},
+
+		{mes: `
+foo: { op: Exists }
+bar: { op: In, value: ["val", "wal"] }
+baz: { op: Gt, value: ["10"] }
+`,
+			input:  I{"bar": "val"},
+			result: assert.Falsef, err: assert.Nilf},
+
+		{mes: `
+foo: { op: Exists }
+bar: { op: In, value: ["val", "wal"] }
+baz: { op: Gt, value: ["10"] }
+`,
+			input:  I{"foo": "1", "bar": "val", "baz": "123"},
+			result: assert.Truef, err: assert.Nilf},
+
+		{mes: `
+foo: { op: Exists }
+bar: { op: In, value: ["val"] }
+baz: { op: Gt, value: ["10"] }
+`,
+			input:  I{"foo": "1", "bar": "val", "baz": "123.0"},
+			result: assert.Falsef, err: assert.NotNilf},
+	}
+
+	for i, tc := range tcs {
+		mes := &e.MatchExpressionSet{}
+		if err := yaml.Unmarshal([]byte(tc.mes), mes); err != nil {
+			t.Fatalf("failed to parse data of test case #%d (%v): %v", i, tc, err)
+		}
+
+		res, err := mes.MatchValues(tc.input)
+		tc.result(t, res, "test case #%d (%v) failed", i, tc)
+		tc.err(t, err, "test case #%d (%v) failed", i, tc)
+	}
+}
+
+func TestMESMatchInstances(t *testing.T) {
+	type I = feature.InstanceFeature
+	type A = map[string]string
+	type TC struct {
+		mes    string
+		input  []I
+		result BoolAssertionFuncf
+		err    ValueAssertionFuncf
+	}
+
+	tcs := []TC{
+		{result: assert.Falsef, err: assert.Nilf}, // nil instances -> false
+
+		{input: []I{}, result: assert.Falsef, err: assert.Nilf}, // zero instances -> false
+
+		{input: []I{I{Attributes: A{}}}, result: assert.Truef, err: assert.Nilf}, // one "empty" instance
+
+		{mes: `
+foo: { op: Exists }
+bar: { op: Lt, value: ["10"] }
+`,
+			input:  []I{I{Attributes: A{"foo": "1"}}, I{Attributes: A{"bar": "1"}}},
+			result: assert.Falsef, err: assert.Nilf},
+
+		{mes: `
+foo: { op: Exists }
+bar: { op: Lt, value: ["10"] }
+`,
+			input:  []I{I{Attributes: A{"foo": "1"}}, I{Attributes: A{"foo": "2", "bar": "1"}}},
+			result: assert.Truef, err: assert.Nilf},
+
+		{mes: `
+bar: { op: Lt, value: ["10"] }
+`,
+			input:  []I{I{Attributes: A{"foo": "1"}}, I{Attributes: A{"bar": "0x1"}}},
+			result: assert.Falsef, err: assert.NotNilf},
+	}
+
+	for i, tc := range tcs {
+		mes := &e.MatchExpressionSet{}
+		if err := yaml.Unmarshal([]byte(tc.mes), mes); err != nil {
+			t.Fatalf("failed to parse data of test case #%d (%v): %v", i, tc, err)
+		}
+
+		res, err := mes.MatchInstances(tc.input)
+		tc.result(t, res, "test case #%d (%v) failed", i, tc)
+		tc.err(t, err, "test case #%d (%v) failed", i, tc)
+	}
+}