blob: 7043b1c6c4e99003a5f5afc1283a08f6713a7cf2 [file] [log] [blame] [edit]
// Copyright 2023 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
package cnf
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 == '_'
}