blob: 79978b69d2b669b1d2db88ce5c14abf03cdfe000 [file] [log] [blame]
// Copyright 2015 Google Inc. All rights reserved
//
// 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 kati
import (
"bytes"
"errors"
"fmt"
"io"
"regexp"
"strconv"
"strings"
"github.com/golang/glog"
)
var (
errEndOfInput = errors.New("unexpected end of input")
errNotLiteral = errors.New("valueNum: not literal")
errUnterminatedVariableReference = errors.New("*** unterminated variable reference.")
)
type evalWriter interface {
io.Writer
writeWord([]byte)
writeWordString(string)
resetSep()
}
// Value is an interface for value.
type Value interface {
String() string
Eval(w evalWriter, ev *Evaluator) error
serialize() serializableVar
dump(d *dumpbuf)
}
// literal is literal value.
type literal string
func (s literal) String() string { return string(s) }
func (s literal) Eval(w evalWriter, ev *Evaluator) error {
io.WriteString(w, string(s))
return nil
}
func (s literal) serialize() serializableVar {
return serializableVar{Type: "literal", V: string(s)}
}
func (s literal) dump(d *dumpbuf) {
d.Byte(valueTypeLiteral)
d.Bytes([]byte(s))
}
// tmpval is temporary value.
type tmpval []byte
func (t tmpval) String() string { return string(t) }
func (t tmpval) Eval(w evalWriter, ev *Evaluator) error {
w.Write(t)
return nil
}
func (t tmpval) Value() []byte { return []byte(t) }
func (t tmpval) serialize() serializableVar {
return serializableVar{Type: "tmpval", V: string(t)}
}
func (t tmpval) dump(d *dumpbuf) {
d.Byte(valueTypeTmpval)
d.Bytes(t)
}
// expr is a list of values.
type expr []Value
func (e expr) String() string {
var s []string
for _, v := range e {
s = append(s, v.String())
}
return strings.Join(s, "")
}
func (e expr) Eval(w evalWriter, ev *Evaluator) error {
for _, v := range e {
w.resetSep()
err := v.Eval(w, ev)
if err != nil {
return err
}
}
return nil
}
func (e expr) serialize() serializableVar {
r := serializableVar{Type: "expr"}
for _, v := range e {
r.Children = append(r.Children, v.serialize())
}
return r
}
func (e expr) dump(d *dumpbuf) {
d.Byte(valueTypeExpr)
d.Int(len(e))
for _, v := range e {
v.dump(d)
}
}
func compactExpr(e expr) Value {
if len(e) == 1 {
return e[0]
}
// TODO(ukai): concat literal
return e
}
func toExpr(v Value) expr {
if v == nil {
return nil
}
if e, ok := v.(expr); ok {
return e
}
return expr{v}
}
// varref is variable reference. e.g. ${foo}.
type varref struct {
varname Value
paren byte
}
func (v *varref) String() string {
varname := v.varname.String()
if len(varname) == 1 && v.paren == 0 {
return fmt.Sprintf("$%s", varname)
}
paren := v.paren
if paren == 0 {
paren = '{'
}
return fmt.Sprintf("$%c%s%c", paren, varname, closeParen(paren))
}
func (v *varref) Eval(w evalWriter, ev *Evaluator) error {
te := traceEvent.begin("var", v, traceEventMain)
buf := newEbuf()
err := v.varname.Eval(buf, ev)
if err != nil {
return err
}
vv := ev.LookupVar(buf.String())
buf.release()
err = vv.Eval(w, ev)
if err != nil {
return err
}
traceEvent.end(te)
return nil
}
func (v *varref) serialize() serializableVar {
return serializableVar{
Type: "varref",
V: string(v.paren),
Children: []serializableVar{v.varname.serialize()},
}
}
func (v *varref) dump(d *dumpbuf) {
d.Byte(valueTypeVarref)
d.Byte(v.paren)
v.varname.dump(d)
}
// paramref is parameter reference e.g. $1.
type paramref int
func (p paramref) String() string {
return fmt.Sprintf("$%d", int(p))
}
func (p paramref) Eval(w evalWriter, ev *Evaluator) error {
te := traceEvent.begin("param", p, traceEventMain)
n := int(p)
if n < len(ev.paramVars) {
err := ev.paramVars[n].Eval(w, ev)
if err != nil {
return err
}
} else {
vv := ev.LookupVar(fmt.Sprintf("%d", n))
err := vv.Eval(w, ev)
if err != nil {
return err
}
}
traceEvent.end(te)
return nil
}
func (p paramref) serialize() serializableVar {
return serializableVar{Type: "paramref", V: strconv.Itoa(int(p))}
}
func (p paramref) dump(d *dumpbuf) {
d.Byte(valueTypeParamref)
d.Int(int(p))
}
// varsubst is variable substitutaion. e.g. ${var:pat=subst}.
type varsubst struct {
varname Value
pat Value
subst Value
paren byte
}
func (v varsubst) String() string {
paren := v.paren
if paren == 0 {
paren = '{'
}
return fmt.Sprintf("$%c%s:%s=%s%c", paren, v.varname, v.pat, v.subst, closeParen(paren))
}
func (v varsubst) Eval(w evalWriter, ev *Evaluator) error {
te := traceEvent.begin("varsubst", v, traceEventMain)
buf := newEbuf()
params, err := ev.args(buf, v.varname, v.pat, v.subst)
if err != nil {
return err
}
vname := string(params[0])
pat := string(params[1])
subst := string(params[2])
buf.Reset()
vv := ev.LookupVar(vname)
err = vv.Eval(buf, ev)
if err != nil {
return err
}
vals := splitSpaces(buf.String())
buf.release()
space := false
for _, val := range vals {
if space {
io.WriteString(w, " ")
}
io.WriteString(w, substRef(pat, subst, val))
space = true
}
traceEvent.end(te)
return nil
}
func (v varsubst) serialize() serializableVar {
return serializableVar{
Type: "varsubst",
V: string(v.paren),
Children: []serializableVar{
v.varname.serialize(),
v.pat.serialize(),
v.subst.serialize(),
},
}
}
func (v varsubst) dump(d *dumpbuf) {
d.Byte(valueTypeVarsubst)
d.Byte(v.paren)
v.varname.dump(d)
v.pat.dump(d)
v.subst.dump(d)
}
func str(buf []byte, alloc bool) Value {
if alloc {
return literal(string(buf))
}
return tmpval(buf)
}
func appendStr(exp expr, buf []byte, alloc bool) expr {
if len(buf) == 0 {
return exp
}
if len(exp) == 0 {
return append(exp, str(buf, alloc))
}
switch v := exp[len(exp)-1].(type) {
case literal:
v += literal(string(buf))
exp[len(exp)-1] = v
return exp
case tmpval:
v = append(v, buf...)
exp[len(exp)-1] = v
return exp
}
return append(exp, str(buf, alloc))
}
func valueNum(v Value) (int, error) {
switch v := v.(type) {
case literal, tmpval:
n, err := strconv.ParseInt(v.String(), 10, 64)
return int(n), err
}
return 0, errNotLiteral
}
type parseOp struct {
// alloc indicates text will be allocated as literal (string)
alloc bool
// matchParen matches parenthesis.
// note: required for func arg
matchParen bool
}
// parseExpr parses expression in `in` until it finds any byte in term.
// if term is nil, it will parse to end of input.
// if term is not nil, and it reaches to end of input, return error.
// it returns parsed value, and parsed length `n`, so in[n-1] is any byte of
// term, and in[n:] is next input.
func parseExpr(in, term []byte, op parseOp) (Value, int, error) {
var exp expr
b := 0
i := 0
var saveParen byte
parenDepth := 0
Loop:
for i < len(in) {
ch := in[i]
if term != nil && bytes.IndexByte(term, ch) >= 0 {
break Loop
}
switch ch {
case '$':
if i+1 >= len(in) {
break Loop
}
if in[i+1] == '$' {
exp = appendStr(exp, in[b:i+1], op.alloc)
i += 2
b = i
continue
}
if bytes.IndexByte(term, in[i+1]) >= 0 {
exp = appendStr(exp, in[b:i], op.alloc)
exp = append(exp, &varref{varname: literal("")})
i++
b = i
break Loop
}
exp = appendStr(exp, in[b:i], op.alloc)
v, n, err := parseDollar(in[i:], op.alloc)
if err != nil {
return nil, 0, err
}
i += n
b = i
exp = append(exp, v)
continue
case '(', '{':
if !op.matchParen {
break
}
cp := closeParen(ch)
if i := bytes.IndexByte(term, cp); i >= 0 {
parenDepth++
saveParen = cp
term[i] = 0
} else if cp == saveParen {
parenDepth++
}
case saveParen:
if !op.matchParen {
break
}
parenDepth--
if parenDepth == 0 {
i := bytes.IndexByte(term, 0)
term[i] = saveParen
saveParen = 0
}
}
i++
}
exp = appendStr(exp, in[b:i], op.alloc)
if i == len(in) && term != nil {
glog.Warningf("parse: unexpected end of input: %q %d [%q]", in, i, term)
return exp, i, errEndOfInput
}
return compactExpr(exp), i, nil
}
func closeParen(ch byte) byte {
switch ch {
case '(':
return ')'
case '{':
return '}'
}
return 0
}
// parseDollar parses
// $(func expr[, expr...]) # func = literal SP
// $(expr:expr=expr)
// $(expr)
// $x
// it returns parsed value and parsed length.
func parseDollar(in []byte, alloc bool) (Value, int, error) {
if len(in) <= 1 {
return nil, 0, errors.New("empty expr")
}
if in[0] != '$' {
return nil, 0, errors.New("should starts with $")
}
if in[1] == '$' {
return nil, 0, errors.New("should handle $$ as literal $")
}
oparen := in[1]
paren := closeParen(oparen)
if paren == 0 {
// $x case.
if in[1] >= '0' && in[1] <= '9' {
return paramref(in[1] - '0'), 2, nil
}
return &varref{varname: str(in[1:2], alloc)}, 2, nil
}
term := []byte{paren, ':', ' '}
var varname expr
i := 2
op := parseOp{alloc: alloc}
Again:
for {
e, n, err := parseExpr(in[i:], term, op)
if err != nil {
if err == errEndOfInput {
// unmatched_paren2.mk
varname = append(varname, toExpr(e)...)
if len(varname) > 0 {
for i, vn := range varname {
if vr, ok := vn.(*varref); ok {
if vr.paren == oparen {
varname = varname[:i+1]
varname[i] = expr{literal(fmt.Sprintf("$%c", oparen)), vr.varname}
return &varref{varname: varname, paren: oparen}, i + 1 + n + 1, nil
}
}
}
}
return nil, 0, errUnterminatedVariableReference
}
return nil, 0, err
}
varname = append(varname, toExpr(e)...)
i += n
switch in[i] {
case paren:
// ${expr}
vname := compactExpr(varname)
n, err := valueNum(vname)
if err == nil {
// ${n}
return paramref(n), i + 1, nil
}
return &varref{varname: vname, paren: oparen}, i + 1, nil
case ' ':
// ${e ...}
switch token := e.(type) {
case literal, tmpval:
funcName := intern(token.String())
if f, ok := funcMap[funcName]; ok {
return parseFunc(f(), in, i+1, term[:1], funcName, op.alloc)
}
}
term = term[:2] // drop ' '
continue Again
case ':':
// ${varname:...}
colon := in[i : i+1]
var vterm []byte
vterm = append(vterm, term[:2]...)
vterm[1] = '=' // term={paren, '='}.
e, n, err := parseExpr(in[i+1:], vterm, op)
if err != nil {
return nil, 0, err
}
i += 1 + n
if in[i] == paren {
varname = appendStr(varname, colon, op.alloc)
return &varref{varname: varname, paren: oparen}, i + 1, nil
}
// ${varname:xx=...}
pat := e
subst, n, err := parseExpr(in[i+1:], term[:1], op)
if err != nil {
return nil, 0, err
}
i += 1 + n
// ${first:pat=e}
return varsubst{
varname: compactExpr(varname),
pat: pat,
subst: subst,
paren: oparen,
}, i + 1, nil
default:
return nil, 0, fmt.Errorf("unexpected char %c at %d in %q", in[i], i, string(in))
}
}
}
// skipSpaces skips spaces at front of `in` before any bytes in term.
// in[n] will be the first non white space in in.
func skipSpaces(in, term []byte) int {
for i := 0; i < len(in); i++ {
if bytes.IndexByte(term, in[i]) >= 0 {
return i
}
switch in[i] {
case ' ', '\t':
default:
return i
}
}
return len(in)
}
// trimLiteralSpace trims literal space around v.
func trimLiteralSpace(v Value) Value {
switch v := v.(type) {
case literal:
return literal(strings.TrimSpace(string(v)))
case tmpval:
b := bytes.TrimSpace([]byte(v))
if len(b) == 0 {
return literal("")
}
return tmpval(b)
case expr:
if len(v) == 0 {
return v
}
switch s := v[0].(type) {
case literal, tmpval:
t := trimLiteralSpace(s)
if t == literal("") {
v = v[1:]
} else {
v[0] = t
}
}
switch s := v[len(v)-1].(type) {
case literal, tmpval:
t := trimLiteralSpace(s)
if t == literal("") {
v = v[:len(v)-1]
} else {
v[len(v)-1] = t
}
}
return compactExpr(v)
}
return v
}
// concatLine concatinates line with "\\\n" in function expression.
// TODO(ukai): less alloc?
func concatLine(v Value) Value {
switch v := v.(type) {
case literal:
for {
s := string(v)
i := strings.Index(s, "\\\n")
if i < 0 {
return v
}
v = literal(s[:i] + strings.TrimLeft(s[i+2:], " \t"))
}
case tmpval:
for {
b := []byte(v)
i := bytes.Index(b, []byte{'\\', '\n'})
if i < 0 {
return v
}
var buf bytes.Buffer
buf.Write(b[:i])
buf.Write(bytes.TrimLeft(b[i+2:], " \t"))
v = tmpval(buf.Bytes())
}
case expr:
for i := range v {
switch vv := v[i].(type) {
case literal, tmpval:
v[i] = concatLine(vv)
}
}
return v
}
return v
}
// parseFunc parses function arguments from in[s:] for f.
// in[0] is '$' and in[s] is space just after func name.
// in[:n] will be "${func args...}"
func parseFunc(f mkFunc, in []byte, s int, term []byte, funcName string, alloc bool) (Value, int, error) {
f.AddArg(str(in[1:s-1], alloc))
arity := f.Arity()
term = append(term, ',')
i := skipSpaces(in[s:], term)
i = s + i
if i == len(in) {
return f, i, nil
}
narg := 1
op := parseOp{alloc: alloc, matchParen: true}
for {
if arity != 0 && narg >= arity {
// final arguments.
term = term[:1] // drop ','
}
v, n, err := parseExpr(in[i:], term, op)
if err != nil {
if err == errEndOfInput {
return nil, 0, fmt.Errorf("*** unterminated call to function `%s': missing `)'.", funcName)
}
return nil, 0, err
}
v = concatLine(v)
// TODO(ukai): do this in funcIf, funcAnd, or funcOr's compactor?
if (narg == 1 && funcName == "if") || funcName == "and" || funcName == "or" {
v = trimLiteralSpace(v)
}
f.AddArg(v)
i += n
narg++
if in[i] == term[0] {
i++
break
}
i++ // should be ','
if i == len(in) {
break
}
}
var fv Value
fv = f
if compactor, ok := f.(compactor); ok {
fv = compactor.Compact()
}
if EvalStatsFlag || traceEvent.enabled() {
fv = funcstats{
Value: fv,
str: fv.String(),
}
}
return fv, i, nil
}
type compactor interface {
Compact() Value
}
type funcstats struct {
Value
str string
}
func (f funcstats) Eval(w evalWriter, ev *Evaluator) error {
te := traceEvent.begin("func", literal(f.str), traceEventMain)
err := f.Value.Eval(w, ev)
if err != nil {
return err
}
// TODO(ukai): per functype?
traceEvent.end(te)
return nil
}
type matcherValue struct{}
func (m matcherValue) Eval(w evalWriter, ev *Evaluator) error {
return fmt.Errorf("couldn't eval matcher")
}
func (m matcherValue) serialize() serializableVar {
return serializableVar{Type: ""}
}
func (m matcherValue) dump(d *dumpbuf) {
d.err = fmt.Errorf("couldn't dump matcher")
}
type matchVarref struct{ matcherValue }
func (m matchVarref) String() string { return "$(match-any)" }
type literalRE struct {
matcherValue
*regexp.Regexp
}
func mustLiteralRE(s string) literalRE {
return literalRE{
Regexp: regexp.MustCompile(s),
}
}
func (r literalRE) String() string { return r.Regexp.String() }
func matchValue(exp, pat Value) bool {
switch pat := pat.(type) {
case literal:
return literal(exp.String()) == pat
}
// TODO: other type match?
return false
}
func matchExpr(exp, pat expr) ([]Value, bool) {
if len(exp) != len(pat) {
return nil, false
}
var mv matchVarref
var matches []Value
for i := range exp {
if pat[i] == mv {
switch exp[i].(type) {
case paramref, *varref:
matches = append(matches, exp[i])
continue
}
return nil, false
}
if patre, ok := pat[i].(literalRE); ok {
re := patre.Regexp
m := re.FindStringSubmatch(exp[i].String())
if m == nil {
return nil, false
}
for _, sm := range m[1:] {
matches = append(matches, literal(sm))
}
continue
}
if !matchValue(exp[i], pat[i]) {
return nil, false
}
}
return matches, true
}