1// Copyright 2014 Google Inc. All rights reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package parser
16
17import (
18	"errors"
19	"fmt"
20	"io"
21	"sort"
22	"strconv"
23	"strings"
24	"text/scanner"
25)
26
27var errTooManyErrors = errors.New("too many errors")
28
29const maxErrors = 1
30
31type ParseError struct {
32	Err error
33	Pos scanner.Position
34}
35
36func (e *ParseError) Error() string {
37	return fmt.Sprintf("%s: %s", e.Pos, e.Err)
38}
39
40type File struct {
41	Name     string
42	Defs     []Definition
43	Comments []*CommentGroup
44}
45
46func (f *File) Pos() scanner.Position {
47	return scanner.Position{
48		Filename: f.Name,
49		Line:     1,
50		Column:   1,
51		Offset:   0,
52	}
53}
54
55func (f *File) End() scanner.Position {
56	if len(f.Defs) > 0 {
57		return f.Defs[len(f.Defs)-1].End()
58	}
59	return noPos
60}
61
62func parse(p *parser) (file *File, errs []error) {
63	defer func() {
64		if r := recover(); r != nil {
65			if r == errTooManyErrors {
66				errs = p.errors
67				return
68			}
69			panic(r)
70		}
71	}()
72
73	defs := p.parseDefinitions()
74	p.accept(scanner.EOF)
75	errs = p.errors
76	comments := p.comments
77
78	return &File{
79		Name:     p.scanner.Filename,
80		Defs:     defs,
81		Comments: comments,
82	}, errs
83
84}
85
86func ParseAndEval(filename string, r io.Reader, scope *Scope) (file *File, errs []error) {
87	p := newParser(r, scope)
88	p.eval = true
89	p.scanner.Filename = filename
90
91	return parse(p)
92}
93
94func Parse(filename string, r io.Reader, scope *Scope) (file *File, errs []error) {
95	p := newParser(r, scope)
96	p.scanner.Filename = filename
97
98	return parse(p)
99}
100
101type parser struct {
102	scanner  scanner.Scanner
103	tok      rune
104	errors   []error
105	scope    *Scope
106	comments []*CommentGroup
107	eval     bool
108}
109
110func newParser(r io.Reader, scope *Scope) *parser {
111	p := &parser{}
112	p.scope = scope
113	p.scanner.Init(r)
114	p.scanner.Error = func(sc *scanner.Scanner, msg string) {
115		p.errorf(msg)
116	}
117	p.scanner.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanStrings |
118		scanner.ScanRawStrings | scanner.ScanComments
119	p.next()
120	return p
121}
122
123func (p *parser) error(err error) {
124	pos := p.scanner.Position
125	if !pos.IsValid() {
126		pos = p.scanner.Pos()
127	}
128	err = &ParseError{
129		Err: err,
130		Pos: pos,
131	}
132	p.errors = append(p.errors, err)
133	if len(p.errors) >= maxErrors {
134		panic(errTooManyErrors)
135	}
136}
137
138func (p *parser) errorf(format string, args ...interface{}) {
139	p.error(fmt.Errorf(format, args...))
140}
141
142func (p *parser) accept(toks ...rune) bool {
143	for _, tok := range toks {
144		if p.tok != tok {
145			p.errorf("expected %s, found %s", scanner.TokenString(tok),
146				scanner.TokenString(p.tok))
147			return false
148		}
149		p.next()
150	}
151	return true
152}
153
154func (p *parser) next() {
155	if p.tok != scanner.EOF {
156		p.tok = p.scanner.Scan()
157		if p.tok == scanner.Comment {
158			var comments []*Comment
159			for p.tok == scanner.Comment {
160				lines := strings.Split(p.scanner.TokenText(), "\n")
161				if len(comments) > 0 && p.scanner.Position.Line > comments[len(comments)-1].End().Line+1 {
162					p.comments = append(p.comments, &CommentGroup{Comments: comments})
163					comments = nil
164				}
165				comments = append(comments, &Comment{lines, p.scanner.Position})
166				p.tok = p.scanner.Scan()
167			}
168			p.comments = append(p.comments, &CommentGroup{Comments: comments})
169		}
170	}
171	return
172}
173
174func (p *parser) parseDefinitions() (defs []Definition) {
175	for {
176		switch p.tok {
177		case scanner.Ident:
178			ident := p.scanner.TokenText()
179			pos := p.scanner.Position
180
181			p.accept(scanner.Ident)
182
183			switch p.tok {
184			case '+':
185				p.accept('+')
186				defs = append(defs, p.parseAssignment(ident, pos, "+="))
187			case '=':
188				defs = append(defs, p.parseAssignment(ident, pos, "="))
189			case '{', '(':
190				defs = append(defs, p.parseModule(ident, pos))
191			default:
192				p.errorf("expected \"=\" or \"+=\" or \"{\" or \"(\", found %s",
193					scanner.TokenString(p.tok))
194			}
195		case scanner.EOF:
196			return
197		default:
198			p.errorf("expected assignment or module definition, found %s",
199				scanner.TokenString(p.tok))
200			return
201		}
202	}
203}
204
205func (p *parser) parseAssignment(name string, namePos scanner.Position,
206	assigner string) (assignment *Assignment) {
207
208	assignment = new(Assignment)
209
210	pos := p.scanner.Position
211	if !p.accept('=') {
212		return
213	}
214	value := p.parseExpression()
215
216	assignment.Name = name
217	assignment.NamePos = namePos
218	assignment.Value = value
219	assignment.OrigValue = value
220	assignment.EqualsPos = pos
221	assignment.Assigner = assigner
222
223	if p.scope != nil {
224		if assigner == "+=" {
225			if old, local := p.scope.Get(assignment.Name); old == nil {
226				p.errorf("modified non-existent variable %q with +=", assignment.Name)
227			} else if !local {
228				p.errorf("modified non-local variable %q with +=", assignment.Name)
229			} else if old.Referenced {
230				p.errorf("modified variable %q with += after referencing", assignment.Name)
231			} else {
232				val, err := p.evaluateOperator(old.Value, assignment.Value, '+', assignment.EqualsPos)
233				if err != nil {
234					p.error(err)
235				} else {
236					old.Value = val
237				}
238			}
239		} else {
240			err := p.scope.Add(assignment)
241			if err != nil {
242				p.error(err)
243			}
244		}
245	}
246
247	return
248}
249
250func (p *parser) parseModule(typ string, typPos scanner.Position) *Module {
251
252	compat := false
253	lbracePos := p.scanner.Position
254	if p.tok == '{' {
255		compat = true
256	}
257
258	if !p.accept(p.tok) {
259		return nil
260	}
261	properties := p.parsePropertyList(true, compat)
262	rbracePos := p.scanner.Position
263	if !compat {
264		p.accept(')')
265	} else {
266		p.accept('}')
267	}
268
269	return &Module{
270		Type:    typ,
271		TypePos: typPos,
272		Map: Map{
273			Properties: properties,
274			LBracePos:  lbracePos,
275			RBracePos:  rbracePos,
276		},
277	}
278}
279
280func (p *parser) parsePropertyList(isModule, compat bool) (properties []*Property) {
281	for p.tok == scanner.Ident {
282		property := p.parseProperty(isModule, compat)
283		properties = append(properties, property)
284
285		if p.tok != ',' {
286			// There was no comma, so the list is done.
287			break
288		}
289
290		p.accept(',')
291	}
292
293	return
294}
295
296func (p *parser) parseProperty(isModule, compat bool) (property *Property) {
297	property = new(Property)
298
299	name := p.scanner.TokenText()
300	namePos := p.scanner.Position
301	p.accept(scanner.Ident)
302	pos := p.scanner.Position
303
304	if isModule {
305		if compat {
306			if !p.accept(':') {
307				return
308			}
309		} else {
310			if !p.accept('=') {
311				return
312			}
313		}
314	} else {
315		if !p.accept(':') {
316			return
317		}
318	}
319
320	value := p.parseExpression()
321
322	property.Name = name
323	property.NamePos = namePos
324	property.Value = value
325	property.ColonPos = pos
326
327	return
328}
329
330func (p *parser) parseExpression() (value Expression) {
331	value = p.parseValue()
332	switch p.tok {
333	case '+':
334		return p.parseOperator(value)
335	case '-':
336		p.errorf("subtraction not supported: %s", p.scanner.String())
337		return value
338	default:
339		return value
340	}
341}
342
343func (p *parser) evaluateOperator(value1, value2 Expression, operator rune,
344	pos scanner.Position) (*Operator, error) {
345
346	value := value1
347
348	if p.eval {
349		e1 := value1.Eval()
350		e2 := value2.Eval()
351		if e1.Type() != e2.Type() {
352			return nil, fmt.Errorf("mismatched type in operator %c: %s != %s", operator,
353				e1.Type(), e2.Type())
354		}
355
356		value = e1.Copy()
357
358		switch operator {
359		case '+':
360			switch v := value.(type) {
361			case *String:
362				v.Value += e2.(*String).Value
363			case *Int64:
364				v.Value += e2.(*Int64).Value
365				v.Token = ""
366			case *List:
367				v.Values = append(v.Values, e2.(*List).Values...)
368			case *Map:
369				var err error
370				v.Properties, err = p.addMaps(v.Properties, e2.(*Map).Properties, pos)
371				if err != nil {
372					return nil, err
373				}
374			default:
375				return nil, fmt.Errorf("operator %c not supported on type %s", operator, v.Type())
376			}
377		default:
378			panic("unknown operator " + string(operator))
379		}
380	}
381
382	return &Operator{
383		Args:        [2]Expression{value1, value2},
384		Operator:    operator,
385		OperatorPos: pos,
386		Value:       value,
387	}, nil
388}
389
390func (p *parser) addMaps(map1, map2 []*Property, pos scanner.Position) ([]*Property, error) {
391	ret := make([]*Property, 0, len(map1))
392
393	inMap1 := make(map[string]*Property)
394	inMap2 := make(map[string]*Property)
395	inBoth := make(map[string]*Property)
396
397	for _, prop1 := range map1 {
398		inMap1[prop1.Name] = prop1
399	}
400
401	for _, prop2 := range map2 {
402		inMap2[prop2.Name] = prop2
403		if _, ok := inMap1[prop2.Name]; ok {
404			inBoth[prop2.Name] = prop2
405		}
406	}
407
408	for _, prop1 := range map1 {
409		if prop2, ok := inBoth[prop1.Name]; ok {
410			var err error
411			newProp := *prop1
412			newProp.Value, err = p.evaluateOperator(prop1.Value, prop2.Value, '+', pos)
413			if err != nil {
414				return nil, err
415			}
416			ret = append(ret, &newProp)
417		} else {
418			ret = append(ret, prop1)
419		}
420	}
421
422	for _, prop2 := range map2 {
423		if _, ok := inBoth[prop2.Name]; !ok {
424			ret = append(ret, prop2)
425		}
426	}
427
428	return ret, nil
429}
430
431func (p *parser) parseOperator(value1 Expression) *Operator {
432	operator := p.tok
433	pos := p.scanner.Position
434	p.accept(operator)
435
436	value2 := p.parseExpression()
437
438	value, err := p.evaluateOperator(value1, value2, operator, pos)
439	if err != nil {
440		p.error(err)
441		return nil
442	}
443
444	return value
445
446}
447
448func (p *parser) parseValue() (value Expression) {
449	switch p.tok {
450	case scanner.Ident:
451		return p.parseVariable()
452	case '-', scanner.Int: // Integer might have '-' sign ahead ('+' is only treated as operator now)
453		return p.parseIntValue()
454	case scanner.String:
455		return p.parseStringValue()
456	case '[':
457		return p.parseListValue()
458	case '{':
459		return p.parseMapValue()
460	default:
461		p.errorf("expected bool, list, or string value; found %s",
462			scanner.TokenString(p.tok))
463		return
464	}
465}
466
467func (p *parser) parseVariable() Expression {
468	var value Expression
469
470	switch text := p.scanner.TokenText(); text {
471	case "true", "false":
472		value = &Bool{
473			LiteralPos: p.scanner.Position,
474			Value:      text == "true",
475			Token:      text,
476		}
477	default:
478		if p.eval {
479			if assignment, local := p.scope.Get(text); assignment == nil {
480				p.errorf("variable %q is not set", text)
481			} else {
482				if local {
483					assignment.Referenced = true
484				}
485				value = assignment.Value
486			}
487		} else {
488			value = &NotEvaluated{}
489		}
490		value = &Variable{
491			Name:    text,
492			NamePos: p.scanner.Position,
493			Value:   value,
494		}
495	}
496
497	p.accept(scanner.Ident)
498	return value
499}
500
501func (p *parser) parseStringValue() *String {
502	str, err := strconv.Unquote(p.scanner.TokenText())
503	if err != nil {
504		p.errorf("couldn't parse string: %s", err)
505		return nil
506	}
507
508	value := &String{
509		LiteralPos: p.scanner.Position,
510		Value:      str,
511	}
512	p.accept(scanner.String)
513	return value
514}
515
516func (p *parser) parseIntValue() *Int64 {
517	var str string
518	literalPos := p.scanner.Position
519	if p.tok == '-' {
520		str += string(p.tok)
521		p.accept(p.tok)
522		if p.tok != scanner.Int {
523			p.errorf("expected int; found %s", scanner.TokenString(p.tok))
524			return nil
525		}
526	}
527	str += p.scanner.TokenText()
528	i, err := strconv.ParseInt(str, 10, 64)
529	if err != nil {
530		p.errorf("couldn't parse int: %s", err)
531		return nil
532	}
533
534	value := &Int64{
535		LiteralPos: literalPos,
536		Value:      i,
537		Token:      str,
538	}
539	p.accept(scanner.Int)
540	return value
541}
542
543func (p *parser) parseListValue() *List {
544	lBracePos := p.scanner.Position
545	if !p.accept('[') {
546		return nil
547	}
548
549	var elements []Expression
550	for p.tok != ']' {
551		element := p.parseExpression()
552		elements = append(elements, element)
553
554		if p.tok != ',' {
555			// There was no comma, so the list is done.
556			break
557		}
558
559		p.accept(',')
560	}
561
562	rBracePos := p.scanner.Position
563	p.accept(']')
564
565	return &List{
566		LBracePos: lBracePos,
567		RBracePos: rBracePos,
568		Values:    elements,
569	}
570}
571
572func (p *parser) parseMapValue() *Map {
573	lBracePos := p.scanner.Position
574	if !p.accept('{') {
575		return nil
576	}
577
578	properties := p.parsePropertyList(false, false)
579
580	rBracePos := p.scanner.Position
581	p.accept('}')
582
583	return &Map{
584		LBracePos:  lBracePos,
585		RBracePos:  rBracePos,
586		Properties: properties,
587	}
588}
589
590type Scope struct {
591	vars          map[string]*Assignment
592	inheritedVars map[string]*Assignment
593}
594
595func NewScope(s *Scope) *Scope {
596	newScope := &Scope{
597		vars:          make(map[string]*Assignment),
598		inheritedVars: make(map[string]*Assignment),
599	}
600
601	if s != nil {
602		for k, v := range s.vars {
603			newScope.inheritedVars[k] = v
604		}
605		for k, v := range s.inheritedVars {
606			newScope.inheritedVars[k] = v
607		}
608	}
609
610	return newScope
611}
612
613func (s *Scope) Add(assignment *Assignment) error {
614	if old, ok := s.vars[assignment.Name]; ok {
615		return fmt.Errorf("variable already set, previous assignment: %s", old)
616	}
617
618	if old, ok := s.inheritedVars[assignment.Name]; ok {
619		return fmt.Errorf("variable already set in inherited scope, previous assignment: %s", old)
620	}
621
622	s.vars[assignment.Name] = assignment
623
624	return nil
625}
626
627func (s *Scope) Remove(name string) {
628	delete(s.vars, name)
629	delete(s.inheritedVars, name)
630}
631
632func (s *Scope) Get(name string) (*Assignment, bool) {
633	if a, ok := s.vars[name]; ok {
634		return a, true
635	}
636
637	if a, ok := s.inheritedVars[name]; ok {
638		return a, false
639	}
640
641	return nil, false
642}
643
644func (s *Scope) String() string {
645	vars := []string{}
646
647	for k := range s.vars {
648		vars = append(vars, k)
649	}
650	for k := range s.inheritedVars {
651		vars = append(vars, k)
652	}
653
654	sort.Strings(vars)
655
656	ret := []string{}
657	for _, v := range vars {
658		if assignment, ok := s.vars[v]; ok {
659			ret = append(ret, assignment.String())
660		} else {
661			ret = append(ret, s.inheritedVars[v].String())
662		}
663	}
664
665	return strings.Join(ret, "\n")
666}
667