parser.go

package interpolate

import (
	"fmt"
	"strconv"
	"strings"
	"unicode"
	"unicode/utf8"
)

// This is a recursive descent parser for our grammar. Because it can contain nested expressions like
// ${LLAMAS:-${ROCK:-true}} we can't use regular expressions. The simplest possible alternative is
// a recursive parser like this. It parses a chunk and then calls a function to parse that further
// and so on and so forth. It results in a tree of objects that represent the things we've parsed (an AST).
// This means that the logic for how expansions work lives in those objects, and the logic for how we go
// from plain text to parsed objects lives here.
//
// To keep things simple, we do our "lexing" or "scanning" just as a few functions at the end of the file
// rather than as a dedicated lexer that emits tokens. This matches the simplicity of the format we are parsing
// relatively well
//
// Below is an EBNF grammar for the language. The parser was built by basically turning this into functions
// and structs named the same reading the string bite by bite (peekRune and nextRune)

/*
EscapedBackslash   = "\\"
Identifier         = letter { letters | digit | "_" }
EscapedDollar      = ( "\$" | "$$" )
EscapedExpansion   = EscapedDollar ( Identifier | Brace )
UnescapedExpansion = "$" ( Identifier | Brace )
Expansion          = UnescapedExpansion | EscapedExpansion
Brace              = "{" Identifier [ Identifier BraceOperation ] "}"
Text               = { EscapedBackslash | EscapedDollar | all characters except "$" }
Expression         = { Text | Expansion }
EmptyValue         = ":-" { Expression }
UnsetValue         = "-" { Expression }
Substring          = ":" number [ ":" number ]
Required           = "?" { Expression }
Operation          = EmptyValue | UnsetValue | Substring | Required
*/

const (
	eof = -1
)

// Parser takes a string and parses out a tree of structs that represent text and Expansions
type Parser struct {
	input string // the string we are scanning
	pos   int    // the current position
}

// NewParser returns a new instance of a Parser
func NewParser(str string) *Parser {
	return &Parser{
		input: str,
		pos:   0,
	}
}

// Parse expansions out of the internal text and return them as a tree of Expressions
func (p *Parser) Parse() (Expression, error) {
	return p.parseExpression()
}

func (p *Parser) parseExpression(stop ...rune) (Expression, error) {
	var expr Expression
	var stopStr = string(stop)

	for {
		c := p.peekRune()
		if c == eof || strings.ContainsRune(stopStr, c) {
			break
		}

		// check for our escaped characters first, as we assume nothing subsequently is escaped
		if strings.HasPrefix(p.input[p.pos:], `\\`) {
			p.pos += 2
			expr = append(expr, ExpressionItem{Text: `\\`})
			continue
		}

		if strings.HasPrefix(p.input[p.pos:], `\$`) || strings.HasPrefix(p.input[p.pos:], `$$`) {
			p.pos += 2

			ee, err := p.parseEscapedExpansion()
			if err != nil {
				return nil, err
			}

			expr = append(expr, ExpressionItem{Expansion: ee})
			continue
		}

		// Ignore bash shell expansions
		if strings.HasPrefix(p.input[p.pos:], `$(`) {
			p.pos += 2
			expr = append(expr, ExpressionItem{Text: `$(`})
			continue
		}

		// If we run into a dollar sign and it's not the last char, it's an expansion
		if c == '$' && p.pos < (len(p.input)-1) {
			expressionItem, err := p.parseExpansion()
			if err != nil {
				return nil, err
			}

			expr = append(expr, expressionItem)
			continue
		}

		// nibble a character, otherwise if it's a \ or a $ we can loop
		c = p.nextRune()

		// Scan as much as we can into text
		text := p.scanUntil(func(r rune) bool {
			return (r == '$' || r == '\\' || strings.ContainsRune(stopStr, r))
		})

		expr = append(expr, ExpressionItem{Text: string(c) + text})
	}

	return expr, nil
}

// parseEscapedExpansion attempts to extract a *potential* identifier or brace
// expression from the text following the escaped dollarsign.
func (p *Parser) parseEscapedExpansion() (EscapedExpansion, error) {
	// Since it's not an expansion, we should treat the following text as text.
	start := p.pos
	defer func() { p.pos = start }()

	next := p.peekRune()
	switch {
	case next == '{':
		// it *could be* an escaped brace expansion
		if _, err := p.parseBraceExpansion(); err != nil {
			return EscapedExpansion{}, nil
		}
		// it was! instead of storing the expansion itself, store the string
		// that produced it.
		return EscapedExpansion{PotentialIdentifier: p.input[start:p.pos]}, nil

	case unicode.IsLetter(next):
		// it *could be* an escaped identifier (eg $$MY_COOL_VAR)
		id, err := p.scanIdentifier()
		if err != nil {
			// this should never happen, since scanIdentifier only errors if the
			// first rune is not a letter, and we just checked that.
			return EscapedExpansion{}, nil
		}

		return EscapedExpansion{PotentialIdentifier: id}, nil

	default:
		// there's no identifier or brace afterward, so it's probably a literal
		// escaped dollar sign
		return EscapedExpansion{}, nil
	}
}

func (p *Parser) parseExpansion() (ExpressionItem, error) {
	var empty ExpressionItem

	if c := p.nextRune(); c != '$' {
		return empty, fmt.Errorf("Expected expansion to start with $, got %c", c)
	}

	c := p.peekRune()

	// if we have an open brace, this is a brace expansion
	if c == '{' {
		expansion, err := p.parseBraceExpansion()
		if err != nil {
			return empty, err
		}
		return ExpressionItem{Expansion: expansion}, nil
	}

	// if not a letter, it's a literal dollar sign
	if !unicode.IsLetter(c) {
		return ExpressionItem{Text: "$"}, nil
	}

	// otherwise, it's a variable expansion
	identifier, err := p.scanIdentifier()
	if err != nil {
		return empty, err
	}

	return ExpressionItem{Expansion: VariableExpansion{
		Identifier: identifier,
	}}, nil
}

func (p *Parser) parseBraceExpansion() (Expansion, error) {
	if c := p.nextRune(); c != '{' {
		return nil, fmt.Errorf("Expected brace expansion to start with {, got %c", c)
	}

	identifier, err := p.scanIdentifier()
	if err != nil {
		return nil, err
	}

	if c := p.peekRune(); c == '}' {
		_ = p.nextRune()
		return VariableExpansion{
			Identifier: identifier,
		}, nil
	}

	var operator string
	var exp Expansion

	// Parse an operator, some trickery is needed to handle : vs :-
	if op1 := p.nextRune(); op1 == ':' {
		if op2 := p.peekRune(); op2 == '-' {
			_ = p.nextRune()
			operator = ":-"
		} else {
			operator = ":"
		}
	} else if op1 == '?' || op1 == '-' {
		operator = string(op1)
	} else {
		return nil, fmt.Errorf("Expected an operator, got %c", op1)
	}

	switch operator {
	case `:-`:
		exp, err = p.parseEmptyValueExpansion(identifier)
		if err != nil {
			return nil, err
		}
	case `-`:
		exp, err = p.parseUnsetValueExpansion(identifier)
		if err != nil {
			return nil, err
		}
	case `:`:
		exp, err = p.parseSubstringExpansion(identifier)
		if err != nil {
			return nil, err
		}
	case `?`:
		exp, err = p.parseRequiredExpansion(identifier)
		if err != nil {
			return nil, err
		}
	}

	if c := p.nextRune(); c != '}' {
		return nil, fmt.Errorf("Expected brace expansion to end with }, got %c", c)
	}

	return exp, nil
}

func (p *Parser) parseEmptyValueExpansion(identifier string) (Expansion, error) {
	// parse an expression (text and expansions) up until the end of the brace
	expr, err := p.parseExpression('}')
	if err != nil {
		return nil, err
	}

	return EmptyValueExpansion{Identifier: identifier, Content: expr}, nil
}

func (p *Parser) parseUnsetValueExpansion(identifier string) (Expansion, error) {
	expr, err := p.parseExpression('}')
	if err != nil {
		return nil, err
	}

	return UnsetValueExpansion{Identifier: identifier, Content: expr}, nil
}

func (p *Parser) parseSubstringExpansion(identifier string) (Expansion, error) {
	offset := p.scanUntil(func(r rune) bool {
		return r == ':' || r == '}'
	})

	offsetInt, err := strconv.Atoi(strings.TrimSpace(offset))
	if err != nil {
		return nil, fmt.Errorf("Unable to parse offset: %v", err)
	}

	if c := p.peekRune(); c == '}' {
		return SubstringExpansion{Identifier: identifier, Offset: offsetInt}, nil
	}

	_ = p.nextRune()
	length := p.scanUntil(func(r rune) bool {
		return r == '}'
	})

	lengthInt, err := strconv.Atoi(strings.TrimSpace(length))
	if err != nil {
		return nil, fmt.Errorf("Unable to parse length: %v", err)
	}

	return SubstringExpansion{Identifier: identifier, Offset: offsetInt, Length: lengthInt, HasLength: true}, nil
}

func (p *Parser) parseRequiredExpansion(identifier string) (Expansion, error) {
	expr, err := p.parseExpression('}')
	if err != nil {
		return nil, err
	}

	return RequiredExpansion{Identifier: identifier, Message: expr}, nil
}

func (p *Parser) scanUntil(f func(rune) bool) string {
	start := p.pos
	for int(p.pos) < len(p.input) {
		c, size := utf8.DecodeRuneInString(p.input[p.pos:])
		if c == utf8.RuneError || f(c) {
			break
		}
		p.pos += size
	}
	return p.input[start:p.pos]
}

func (p *Parser) scanIdentifier() (string, error) {
	if c := p.peekRune(); !unicode.IsLetter(c) {
		return "", fmt.Errorf("Expected identifier to start with a letter, got %c", c)
	}
	notIdentifierChar := func(r rune) bool {
		return !(unicode.IsLetter(r) || unicode.IsNumber(r) || r == '_')
	}
	return p.scanUntil(notIdentifierChar), nil
}

func (p *Parser) nextRune() rune {
	if int(p.pos) >= len(p.input) {
		return eof
	}
	c, size := utf8.DecodeRuneInString(p.input[p.pos:])
	p.pos += size
	return c
}

func (p *Parser) peekRune() rune {
	if int(p.pos) >= len(p.input) {
		return eof
	}
	c, _ := utf8.DecodeRuneInString(p.input[p.pos:])
	return c
}