pkg/kconfig: add package

kconfig package is supposed to parse Kconfig/.config files
and provide some algorithms on top.
This commit includes only parser helper and expression parsing for starters.

Update #2171

4 files changed, 531 insertions, 0 deletions

diff --git a/pkg/kconfig/expr.go b/pkg/kconfig/expr.go
new file mode 100644
index 000000000..109ffd7b3
--- /dev/null
+++ b/pkg/kconfig/expr.go
@@ -0,0 +1,213 @@
+// Copyright 2020 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 kconfig
+
+import (
+	"fmt"
+)
+
+// expr represents an arbitrary kconfig expression used in "depends on", "visible if", "if", etc.
+// Currently we can only extract dependent symbols from expressions.
+type expr interface {
+	String() string
+	collectDeps(map[string]bool)
+}
+
+type exprShell struct {
+	cmd string
+}
+
+func (ex *exprShell) String() string {
+	return "$" + ex.cmd
+}
+
+func (ex *exprShell) collectDeps(deps map[string]bool) {
+}
+
+type exprNot struct {
+	ex expr
+}
+
+func (ex *exprNot) String() string {
+	return fmt.Sprintf("!(%v)", ex.ex)
+}
+
+func (ex *exprNot) collectDeps(deps map[string]bool) {
+}
+
+type exprIdent struct {
+	name string
+}
+
+func (ex *exprIdent) String() string {
+	return ex.name
+}
+
+func (ex *exprIdent) collectDeps(deps map[string]bool) {
+	deps[ex.name] = true
+}
+
+type exprString struct {
+	val string
+}
+
+func (ex *exprString) String() string {
+	return fmt.Sprintf("%q", ex.val)
+}
+
+func (ex *exprString) collectDeps(deps map[string]bool) {
+}
+
+type exprBin struct {
+	op  binOp
+	lex expr
+	rex expr
+}
+
+type binOp int
+
+const (
+	opNop binOp = iota
+	opAnd
+	opOr
+	opEq
+	opNe
+	opLt
+	opLe
+	opGt
+	opGe
+)
+
+func (op binOp) String() string {
+	switch op {
+	case opAnd:
+		return "&&"
+	case opOr:
+		return "||"
+	case opEq:
+		return "="
+	case opNe:
+		return "!="
+	case opLt:
+		return "<"
+	case opLe:
+		return "<="
+	case opGt:
+		return ">"
+	case opGe:
+		return ">="
+	default:
+		return fmt.Sprintf("???(%v)", int(op))
+	}
+}
+
+func (ex *exprBin) String() string {
+	return fmt.Sprintf("(%v %v %v)", ex.lex, ex.op, ex.rex)
+}
+
+func (ex *exprBin) collectDeps(deps map[string]bool) {
+	ex.lex.collectDeps(deps)
+	ex.rex.collectDeps(deps)
+}
+
+func exprAnd(lex, rex expr) expr {
+	if lex == nil {
+		return rex
+	}
+	if rex == nil {
+		return lex
+	}
+	return &exprBin{
+		op:  opAnd,
+		lex: lex,
+		rex: rex,
+	}
+}
+
+// Recursive-descent parsing with strict precedence levels.
+// See kconfig docs for reference:
+// https://www.kernel.org/doc/html/latest/kbuild/kconfig-language.html#menu-dependencies
+// The doc claims that all operators have different precedence levels,
+// e.g. '<' has higher precedence than '>' rather than being left-associative with the same precedence.
+// This is somewhat strange semantics and here it is implemented as simply being left-associative.
+// For now it does not matter since we do not evaluate expressions.
+func (p *parser) parseExpr() expr {
+	ex := p.parseExprAnd()
+	for p.TryConsume("||") {
+		ex = &exprBin{
+			op:  opOr,
+			lex: ex,
+			rex: p.parseExprAnd(),
+		}
+	}
+	return ex
+}
+
+func (p *parser) parseExprAnd() expr {
+	ex := p.parseExprCmp()
+	for p.TryConsume("&&") {
+		ex = &exprBin{
+			op:  opAnd,
+			lex: ex,
+			rex: p.parseExprCmp(),
+		}
+	}
+	return ex
+}
+
+func (p *parser) parseExprCmp() expr {
+	ex := p.parseExprTerm()
+	for {
+		op := opNop
+		switch {
+		case p.TryConsume("="):
+			op = opEq
+		case p.TryConsume("!="):
+			op = opNe
+		case p.TryConsume("<="):
+			op = opLe
+		case p.TryConsume(">="):
+			op = opGe
+		case p.TryConsume("<"):
+			op = opLt
+		case p.TryConsume(">"):
+			op = opGt
+		}
+		if op == opNop {
+			break
+		}
+		ex = &exprBin{
+			op:  op,
+			lex: ex,
+			rex: p.parseExprTerm(),
+		}
+	}
+	return ex
+}
+
+func (p *parser) parseExprTerm() expr {
+	if p.TryConsume("$") {
+		return &exprShell{
+			cmd: p.Shell(),
+		}
+	}
+	if str, ok := p.TryQuotedString(); ok {
+		return &exprString{
+			val: str,
+		}
+	}
+	if p.TryConsume("!") {
+		return &exprNot{
+			ex: p.parseExprTerm(),
+		}
+	}
+	if p.TryConsume("(") {
+		ex := p.parseExpr()
+		p.MustConsume(")")
+		return ex
+	}
+	return &exprIdent{
+		name: p.Ident(),
+	}
+}
diff --git a/pkg/kconfig/expr_test.go b/pkg/kconfig/expr_test.go
new file mode 100644
index 000000000..6ae270112
--- /dev/null
+++ b/pkg/kconfig/expr_test.go
@@ -0,0 +1,98 @@
+// Copyright 2020 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 kconfig
+
+import (
+	"fmt"
+	"reflect"
+	"testing"
+)
+
+func TestParseExpr(t *testing.T) {
+	type Test struct {
+		in   string
+		out  string
+		deps map[string]bool
+		err  bool
+	}
+	tests := []Test{
+		{
+			in:  ` `,
+			err: true,
+		},
+		{
+			in:   `A`,
+			out:  `A`,
+			deps: map[string]bool{"A": true},
+		},
+		{
+			in:   `A=B`,
+			out:  `(A = B)`,
+			deps: map[string]bool{"A": true, "B": true},
+		},
+		{
+			in:   `!A && B`,
+			out:  `(!(A) && B)`,
+			deps: map[string]bool{"B": true},
+		},
+		{
+			in:  `$(A "B")`,
+			out: `$(A "B")`,
+		},
+		{
+			in:  `"A"`,
+			out: `"A"`,
+		},
+		{
+			in:  `A||B&&C`,
+			out: `(A || (B && C))`,
+		},
+	}
+	for i, test := range tests {
+		t.Run(fmt.Sprint(i), func(t *testing.T) {
+			t.Logf("input: %v", test.in)
+			in := test.in
+			if !test.err {
+				in += " Z"
+			}
+			p := newParser([]byte(in), "file")
+			if !p.nextLine() {
+				t.Fatal("nextLine failed")
+			}
+			ex := p.parseExpr()
+			if test.err {
+				if p.err == nil {
+					t.Fatal("not failed")
+				}
+				return
+			}
+			if p.err != nil {
+				t.Fatalf("failed: %v", p.err)
+			}
+			if ex.String() != test.out {
+				t.Fatalf("\ngot:  %q\nwant: %q", ex, test.out)
+			}
+			deps := make(map[string]bool)
+			ex.collectDeps(deps)
+			if len(deps) != 0 && len(test.deps) != 0 && !reflect.DeepEqual(deps, test.deps) {
+				t.Fatalf("\ndeps: %v\nwant: %v", deps, test.deps)
+			}
+			if p.Ident() != "Z" {
+				t.Fatal("parsing consumed unrelated token")
+			}
+		})
+	}
+}
+
+func TestFuzzParseExpr(t *testing.T) {
+	for _, data := range []string{
+		``,
+		`A`,
+		`A = B`,
+		`A || B && C`,
+		`$(A"B")`,
+	} {
+		FuzzParseExpr([]byte(data)[:len(data):len(data)])
+	}
+}
diff --git a/pkg/kconfig/fuzz.go b/pkg/kconfig/fuzz.go
new file mode 100644
index 000000000..49f43efcb
--- /dev/null
+++ b/pkg/kconfig/fuzz.go
@@ -0,0 +1,13 @@
+// Copyright 2020 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 kconfig
+
+func FuzzParseExpr(data []byte) int {
+	p := newParser(data, "expr")
+	if !p.nextLine() {
+		return 0
+	}
+	p.parseExpr()
+	return 0
+}
diff --git a/pkg/kconfig/parser.go b/pkg/kconfig/parser.go
new file mode 100644
index 000000000..5fe9bed09
--- /dev/null
+++ b/pkg/kconfig/parser.go
@@ -0,0 +1,207 @@
+// Copyright 2020 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 kconfig
+
+import (
+	"bytes"
+	"fmt"
+	"strings"
+)
+
+// parser is a helper for parsing simple text protocols tailored for kconfig syntax.
+type parser struct {
+	data    []byte
+	file    string
+	current string
+	col     int
+	line    int
+	err     error
+}
+
+func newParser(data []byte, file string) *parser {
+	return &parser{
+		data: data,
+		file: file,
+	}
+}
+
+// nextLine resets the parser to the next line.
+// Automatically concatenates lines split with \ at the end.
+func (p *parser) nextLine() bool {
+	if !p.eol() {
+		p.failf("tailing data at the end of line")
+		return false
+	}
+	if p.err != nil || len(p.data) == 0 {
+		return false
+	}
+	p.col = 0
+	p.line++
+	p.current = p.readNextLine()
+	for p.current != "" && p.current[len(p.current)-1] == '\\' && len(p.data) != 0 {
+		p.current = p.current[:len(p.current)-1] + p.readNextLine()
+		p.line++
+	}
+	p.skipSpaces()
+	return true
+}
+
+func (p *parser) readNextLine() string {
+	line := ""
+	nextLine := bytes.IndexByte(p.data, '\n')
+	if nextLine != -1 {
+		line = string(p.data[:nextLine])
+		p.data = p.data[nextLine+1:]
+	} else {
+		line = string(p.data)
+		p.data = nil
+	}
+	return line
+}
+
+func (p *parser) skipSpaces() {
+	for p.col < len(p.current) && (p.current[p.col] == ' ' || p.current[p.col] == '\t') {
+		p.col++
+	}
+}
+
+func (p *parser) identLevel() int {
+	level := 0
+	for i := 0; i < p.col; i++ {
+		level++
+		if p.current[i] == '\t' {
+			level = (level + 7) & ^7
+		}
+	}
+	return level
+}
+
+func (p *parser) failf(msg string, args ...interface{}) {
+	if p.err == nil {
+		p.err = fmt.Errorf("%v:%v:%v: %v\n%v", p.file, p.line, p.col, fmt.Sprintf(msg, args...), p.current)
+	}
+}
+
+func (p *parser) eol() bool {
+	return p.col == len(p.current)
+}
+
+func (p *parser) char() byte {
+	if p.err != nil {
+		return 0
+	}
+	if p.eol() {
+		p.failf("unexpected end of line")
+		return 0
+	}
+	v := p.current[p.col]
+	p.col++
+	return v
+}
+
+func (p *parser) peek() byte {
+	if p.err != nil || p.eol() {
+		return 0
+	}
+	return p.current[p.col]
+}
+
+func (p *parser) ConsumeLine() string {
+	res := p.current[p.col:]
+	p.col = len(p.current)
+	return res
+}
+
+func (p *parser) TryConsume(what string) bool {
+	if !strings.HasPrefix(p.current[p.col:], what) {
+		return false
+	}
+	p.col += len(what)
+	p.skipSpaces()
+	return true
+}
+
+func (p *parser) MustConsume(what string) {
+	if !p.TryConsume(what) {
+		p.failf("expected %q", what)
+	}
+}
+
+func (p *parser) QuotedString() string {
+	var str []byte
+	quote := p.char()
+	if quote != '"' && quote != '\'' {
+		p.failf("expect quoted string")
+	}
+	for ch := p.char(); ch != quote; ch = p.char() {
+		if ch == 0 {
+			p.failf("unterminated quoted string")
+			break
+		}
+		if ch == '\\' {
+			ch = p.char()
+			switch ch {
+			case '\'', '"', '\\':
+				str = append(str, ch)
+			default:
+				p.failf("bad quoted character")
+			}
+			continue
+		}
+		str = append(str, ch)
+		if ch == '$' && p.peek() == '(' {
+			str = append(str, p.Shell()...)
+		}
+	}
+	p.skipSpaces()
+	return string(str)
+}
+
+func (p *parser) TryQuotedString() (string, bool) {
+	if ch := p.peek(); ch == '"' || ch == '\'' {
+		return p.QuotedString(), true
+	}
+	return "", false
+}
+
+func (p *parser) Ident() string {
+	var str []byte
+	for !p.eol() {
+		ch := p.peek()
+		if ch >= 'a' && ch <= 'z' ||
+			ch >= 'A' && ch <= 'Z' ||
+			ch >= '0' && ch <= '9' ||
+			ch == '_' || ch == '-' {
+			str = append(str, ch)
+			p.col++
+			continue
+		}
+		break
+	}
+	if len(str) == 0 {
+		p.failf("expected an identifier")
+	}
+	p.skipSpaces()
+	return string(str)
+}
+
+func (p *parser) Shell() string {
+	start := p.col
+	p.MustConsume("(")
+	for !p.eol() && p.peek() != ')' {
+		if p.peek() == '"' {
+			p.QuotedString()
+		} else if p.peek() == '(' {
+			p.Shell()
+		} else {
+			p.col++
+		}
+	}
+	if ch := p.char(); ch != ')' {
+		p.failf("shell expression is not terminated")
+	}
+	res := p.current[start:p.col]
+	p.skipSpaces()
+	return res
+}