pkg/subsystem: add the path matching code

Additionally, optimize the matching by joining the rules without
exclusion (that is, almost all MAINTAINER records).

3 files changed, 142 insertions, 0 deletions

diff --git a/pkg/subsystem/entity/entities.go b/pkg/subsystem/entity/entities.go
new file mode 100644
index 000000000..6d028e391
--- /dev/null
+++ b/pkg/subsystem/entity/entities.go
@@ -0,0 +1,15 @@
+// Copyright 2023 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package entity
+
+type Subsystem struct {
+	PathRules []PathRule
+}
+
+// PathRule describes the part of the directory tree belonging to a single subsystem.
+type PathRule struct {
+	IncludeRegexp string
+	// ExcludeRegexps are tested before IncludeRegexp.
+	ExcludeRegexp string
+}
diff --git a/pkg/subsystem/match/match.go b/pkg/subsystem/match/match.go
new file mode 100644
index 000000000..31874f978
--- /dev/null
+++ b/pkg/subsystem/match/match.go
@@ -0,0 +1,75 @@
+// Copyright 2023 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package match
+
+import (
+	"regexp"
+	"strings"
+
+	"github.com/google/syzkaller/pkg/subsystem/entity"
+)
+
+type PathMatcher struct {
+	matches []*match
+}
+
+type match struct {
+	include *regexp.Regexp
+	exclude *regexp.Regexp
+	object  *entity.Subsystem
+}
+
+func MakePathMatcher(list []*entity.Subsystem) *PathMatcher {
+	m := &PathMatcher{}
+	for _, item := range list {
+		m.register(item)
+	}
+	return m
+}
+
+func (p *PathMatcher) register(item *entity.Subsystem) {
+	onlyInclude := []string{}
+	list := []entity.PathRule{}
+	for _, r := range item.PathRules {
+		if r.ExcludeRegexp == "" {
+			// It's expected that almost everything will go to this branch.
+			onlyInclude = append(onlyInclude, r.IncludeRegexp)
+		} else {
+			list = append(list, r)
+		}
+	}
+	if len(onlyInclude) > 0 {
+		list = append(list, entity.PathRule{
+			IncludeRegexp: strings.Join(onlyInclude, "|"),
+		})
+	}
+	for _, rule := range list {
+		p.matches = append(p.matches, buildMatch(rule, item))
+	}
+}
+
+func (p *PathMatcher) Match(path string) []*entity.Subsystem {
+	ret := []*entity.Subsystem{}
+	for _, m := range p.matches {
+		if m.exclude != nil && m.exclude.MatchString(path) {
+			continue
+		}
+		if m.include != nil && !m.include.MatchString(path) {
+			continue
+		}
+		ret = append(ret, m.object)
+	}
+	return ret
+}
+
+func buildMatch(rule entity.PathRule, item *entity.Subsystem) *match {
+	m := &match{object: item}
+	if rule.IncludeRegexp != "" {
+		m.include = regexp.MustCompile(rule.IncludeRegexp)
+	}
+	if rule.ExcludeRegexp != "" {
+		m.exclude = regexp.MustCompile(rule.ExcludeRegexp)
+	}
+	return m
+}
diff --git a/pkg/subsystem/match/match_test.go b/pkg/subsystem/match/match_test.go
new file mode 100644
index 000000000..2f7440e19
--- /dev/null
+++ b/pkg/subsystem/match/match_test.go
@@ -0,0 +1,52 @@
+// Copyright 2023 syzkaller project authors. All rights reserved.
+// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
+
+package match
+
+import (
+	"testing"
+
+	"github.com/google/syzkaller/pkg/subsystem/entity"
+	"github.com/stretchr/testify/assert"
+)
+
+func TestPathMatcher(t *testing.T) {
+	arm := &entity.Subsystem{
+		PathRules: []entity.PathRule{
+			{
+				IncludeRegexp: `^arch/arm/.*$`,
+				ExcludeRegexp: `^arch/arm/boot/dts/.*$`,
+			},
+			{IncludeRegexp: `^drivers/spi/spi-pl022\.c$`},
+			{
+				// nolint:lll
+				IncludeRegexp: `^drivers/irqchip/irq-vic\.c$|^Documentation/devicetree/bindings/interrupt-controller/arm,vic\.yaml$`,
+			},
+		},
+	}
+	docs := &entity.Subsystem{
+		PathRules: []entity.PathRule{
+			{IncludeRegexp: `^Documentation/.*$`},
+		},
+	}
+	m := MakePathMatcher([]*entity.Subsystem{arm, docs})
+	assert.ElementsMatch(t, []*entity.Subsystem{arm, docs},
+		m.Match(`Documentation/devicetree/bindings/interrupt-controller/arm,vic.yaml`))
+	assert.ElementsMatch(t, []*entity.Subsystem{arm}, m.Match(`arch/arm/a.c`))
+	assert.ElementsMatch(t, []*entity.Subsystem{docs}, m.Match(`Documentation/a/b/c.md`))
+	assert.Empty(t, m.Match(`arch/boot/dts/a.c`))
+}
+
+func TestPathMatchOrder(t *testing.T) {
+	s := &entity.Subsystem{
+		PathRules: []entity.PathRule{
+			{
+				IncludeRegexp: `^a/b/.*$`,
+				ExcludeRegexp: `^a/.*$`,
+			},
+		},
+	}
+	m := MakePathMatcher([]*entity.Subsystem{s})
+	// If we first exclude a/, then a/b/c never matches.
+	assert.Empty(t, m.Match("a/b/c"))
+}