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 []Comment
44}
45
46func parse(p *parser) (file *File, errs []error) {
47	defer func() {
48		if r := recover(); r != nil {
49			if r == errTooManyErrors {
50				errs = p.errors
51				return
52			}
53			panic(r)
54		}
55	}()
56
57	defs := p.parseDefinitions()
58	p.accept(scanner.EOF)
59	errs = p.errors
60	comments := p.comments
61
62	return &File{
63		Name:     p.scanner.Filename,
64		Defs:     defs,
65		Comments: comments,
66	}, errs
67
68}
69
70func ParseAndEval(filename string, r io.Reader, scope *Scope) (file *File, errs []error) {
71	p := newParser(r, scope)
72	p.eval = true
73	p.scanner.Filename = filename
74
75	return parse(p)
76}
77
78func Parse(filename string, r io.Reader, scope *Scope) (file *File, errs []error) {
79	p := newParser(r, scope)
80	p.scanner.Filename = filename
81
82	return parse(p)
83}
84
85type parser struct {
86	scanner  scanner.Scanner
87	tok      rune
88	errors   []error
89	scope    *Scope
90	comments []Comment
91	eval     bool
92}
93
94func newParser(r io.Reader, scope *Scope) *parser {
95	p := &parser{}
96	p.scope = scope
97	p.scanner.Init(r)
98	p.scanner.Error = func(sc *scanner.Scanner, msg string) {
99		p.errorf(msg)
100	}
101	p.scanner.Mode = scanner.ScanIdents | scanner.ScanStrings |
102		scanner.ScanRawStrings | scanner.ScanComments
103	p.next()
104	return p
105}
106
107func (p *parser) error(err error) {
108	pos := p.scanner.Position
109	if !pos.IsValid() {
110		pos = p.scanner.Pos()
111	}
112	err = &ParseError{
113		Err: err,
114		Pos: pos,
115	}
116	p.errors = append(p.errors, err)
117	if len(p.errors) >= maxErrors {
118		panic(errTooManyErrors)
119	}
120}
121
122func (p *parser) errorf(format string, args ...interface{}) {
123	p.error(fmt.Errorf(format, args...))
124}
125
126func (p *parser) accept(toks ...rune) bool {
127	for _, tok := range toks {
128		if p.tok != tok {
129			p.errorf("expected %s, found %s", scanner.TokenString(tok),
130				scanner.TokenString(p.tok))
131			return false
132		}
133		p.next()
134	}
135	return true
136}
137
138func (p *parser) next() {
139	if p.tok != scanner.EOF {
140		p.tok = p.scanner.Scan()
141		for p.tok == scanner.Comment {
142			lines := strings.Split(p.scanner.TokenText(), "\n")
143			p.comments = append(p.comments, Comment{lines, p.scanner.Position})
144			p.tok = p.scanner.Scan()
145		}
146	}
147	return
148}
149
150func (p *parser) parseDefinitions() (defs []Definition) {
151	for {
152		switch p.tok {
153		case scanner.Ident:
154			ident := p.scanner.TokenText()
155			pos := p.scanner.Position
156
157			p.accept(scanner.Ident)
158
159			switch p.tok {
160			case '+':
161				p.accept('+')
162				defs = append(defs, p.parseAssignment(ident, pos, "+="))
163			case '=':
164				defs = append(defs, p.parseAssignment(ident, pos, "="))
165			case '{', '(':
166				defs = append(defs, p.parseModule(ident, pos))
167			default:
168				p.errorf("expected \"=\" or \"+=\" or \"{\" or \"(\", found %s",
169					scanner.TokenString(p.tok))
170			}
171		case scanner.EOF:
172			return
173		default:
174			p.errorf("expected assignment or module definition, found %s",
175				scanner.TokenString(p.tok))
176			return
177		}
178	}
179}
180
181func (p *parser) parseAssignment(name string,
182	namePos scanner.Position, assigner string) (assignment *Assignment) {
183
184	assignment = new(Assignment)
185
186	pos := p.scanner.Position
187	if !p.accept('=') {
188		return
189	}
190	value := p.parseExpression()
191
192	assignment.Name = Ident{name, namePos}
193	assignment.Value = value
194	assignment.OrigValue = value
195	assignment.Pos = pos
196	assignment.Assigner = assigner
197
198	if p.scope != nil {
199		if assigner == "+=" {
200			if old, local := p.scope.Get(assignment.Name.Name); old == nil {
201				p.errorf("modified non-existent variable %q with +=", assignment.Name.Name)
202			} else if !local {
203				p.errorf("modified non-local variable %q with +=", assignment.Name.Name)
204			} else if old.Referenced {
205				p.errorf("modified variable %q with += after referencing",
206					assignment.Name.Name)
207			} else {
208				val, err := p.evaluateOperator(old.Value, assignment.Value, '+', assignment.Pos)
209				if err != nil {
210					p.error(err)
211				} else {
212					old.Value = val
213				}
214			}
215		} else {
216			err := p.scope.Add(assignment)
217			if err != nil {
218				p.error(err)
219			}
220		}
221	}
222
223	return
224}
225
226func (p *parser) parseModule(typ string,
227	typPos scanner.Position) (module *Module) {
228
229	module = new(Module)
230	compat := false
231	lbracePos := p.scanner.Position
232	if p.tok == '{' {
233		compat = true
234	}
235
236	if !p.accept(p.tok) {
237		return
238	}
239	properties := p.parsePropertyList(true, compat)
240	rbracePos := p.scanner.Position
241	if !compat {
242		p.accept(')')
243	} else {
244		p.accept('}')
245	}
246
247	module.Type = Ident{typ, typPos}
248	module.Properties = properties
249	module.LbracePos = lbracePos
250	module.RbracePos = rbracePos
251	return
252}
253
254func (p *parser) parsePropertyList(isModule, compat bool) (properties []*Property) {
255	for p.tok == scanner.Ident {
256		property := p.parseProperty(isModule, compat)
257		properties = append(properties, property)
258
259		if p.tok != ',' {
260			// There was no comma, so the list is done.
261			break
262		}
263
264		p.accept(',')
265	}
266
267	return
268}
269
270func (p *parser) parseProperty(isModule, compat bool) (property *Property) {
271	property = new(Property)
272
273	name := p.scanner.TokenText()
274	namePos := p.scanner.Position
275	p.accept(scanner.Ident)
276	pos := p.scanner.Position
277
278	if isModule {
279		if compat && p.tok == ':' {
280			p.accept(':')
281		} else {
282			if !p.accept('=') {
283				return
284			}
285		}
286	} else {
287		if !p.accept(':') {
288			return
289		}
290	}
291
292	value := p.parseExpression()
293
294	property.Name = Ident{name, namePos}
295	property.Value = value
296	property.Pos = pos
297
298	return
299}
300
301func (p *parser) parseExpression() (value Value) {
302	value = p.parseValue()
303	switch p.tok {
304	case '+':
305		return p.parseOperator(value)
306	default:
307		return value
308	}
309}
310
311func (p *parser) evaluateOperator(value1, value2 Value, operator rune,
312	pos scanner.Position) (Value, error) {
313
314	value := Value{}
315
316	if p.eval {
317		if value1.Type != value2.Type {
318			return Value{}, fmt.Errorf("mismatched type in operator %c: %s != %s", operator,
319				value1.Type, value2.Type)
320		}
321
322		value = value1
323		value.Variable = ""
324
325		switch operator {
326		case '+':
327			switch value1.Type {
328			case String:
329				value.StringValue = value1.StringValue + value2.StringValue
330			case List:
331				value.ListValue = append([]Value{}, value1.ListValue...)
332				value.ListValue = append(value.ListValue, value2.ListValue...)
333			case Map:
334				var err error
335				value.MapValue, err = p.addMaps(value.MapValue, value2.MapValue, pos)
336				if err != nil {
337					return Value{}, err
338				}
339			default:
340				return Value{}, fmt.Errorf("operator %c not supported on type %s", operator,
341					value1.Type)
342			}
343		default:
344			panic("unknown operator " + string(operator))
345		}
346	}
347
348	value.Expression = &Expression{
349		Args:     [2]Value{value1, value2},
350		Operator: operator,
351		Pos:      pos,
352	}
353
354	return value, nil
355}
356
357func (p *parser) addMaps(map1, map2 []*Property, pos scanner.Position) ([]*Property, error) {
358	ret := make([]*Property, 0, len(map1))
359
360	inMap1 := make(map[string]*Property)
361	inMap2 := make(map[string]*Property)
362	inBoth := make(map[string]*Property)
363
364	for _, prop1 := range map1 {
365		inMap1[prop1.Name.Name] = prop1
366	}
367
368	for _, prop2 := range map2 {
369		inMap2[prop2.Name.Name] = prop2
370		if _, ok := inMap1[prop2.Name.Name]; ok {
371			inBoth[prop2.Name.Name] = prop2
372		}
373	}
374
375	for _, prop1 := range map1 {
376		if prop2, ok := inBoth[prop1.Name.Name]; ok {
377			var err error
378			newProp := *prop1
379			newProp.Value, err = p.evaluateOperator(prop1.Value, prop2.Value, '+', pos)
380			if err != nil {
381				return nil, err
382			}
383			ret = append(ret, &newProp)
384		} else {
385			ret = append(ret, prop1)
386		}
387	}
388
389	for _, prop2 := range map2 {
390		if _, ok := inBoth[prop2.Name.Name]; !ok {
391			ret = append(ret, prop2)
392		}
393	}
394
395	return ret, nil
396}
397
398func (p *parser) parseOperator(value1 Value) Value {
399	operator := p.tok
400	pos := p.scanner.Position
401	p.accept(operator)
402
403	value2 := p.parseExpression()
404
405	value, err := p.evaluateOperator(value1, value2, operator, pos)
406	if err != nil {
407		p.error(err)
408		return Value{}
409	}
410
411	return value
412}
413
414func (p *parser) parseValue() (value Value) {
415	switch p.tok {
416	case scanner.Ident:
417		return p.parseVariable()
418	case scanner.String:
419		return p.parseStringValue()
420	case '[':
421		return p.parseListValue()
422	case '{':
423		return p.parseMapValue()
424	default:
425		p.errorf("expected bool, list, or string value; found %s",
426			scanner.TokenString(p.tok))
427		return
428	}
429}
430
431func (p *parser) parseVariable() (value Value) {
432	switch text := p.scanner.TokenText(); text {
433	case "true":
434		value.Type = Bool
435		value.BoolValue = true
436	case "false":
437		value.Type = Bool
438		value.BoolValue = false
439	default:
440		variable := p.scanner.TokenText()
441		if p.eval {
442			if assignment, local := p.scope.Get(variable); assignment == nil {
443				p.errorf("variable %q is not set", variable)
444			} else {
445				if local {
446					assignment.Referenced = true
447				}
448				value = assignment.Value
449			}
450		}
451		value.Variable = variable
452	}
453	value.Pos = p.scanner.Position
454
455	p.accept(scanner.Ident)
456	return
457}
458
459func (p *parser) parseStringValue() (value Value) {
460	value.Type = String
461	value.Pos = p.scanner.Position
462	str, err := strconv.Unquote(p.scanner.TokenText())
463	if err != nil {
464		p.errorf("couldn't parse string: %s", err)
465		return
466	}
467	value.StringValue = str
468	p.accept(scanner.String)
469	return
470}
471
472func (p *parser) parseListValue() (value Value) {
473	value.Type = List
474	value.Pos = p.scanner.Position
475	if !p.accept('[') {
476		return
477	}
478
479	var elements []Value
480	for p.tok != ']' {
481		element := p.parseExpression()
482		if p.eval && element.Type != String {
483			p.errorf("Expected string in list, found %s", element.String())
484			return
485		}
486		elements = append(elements, element)
487
488		if p.tok != ',' {
489			// There was no comma, so the list is done.
490			break
491		}
492
493		p.accept(',')
494	}
495
496	value.ListValue = elements
497	value.EndPos = p.scanner.Position
498
499	p.accept(']')
500	return
501}
502
503func (p *parser) parseMapValue() (value Value) {
504	value.Type = Map
505	value.Pos = p.scanner.Position
506	if !p.accept('{') {
507		return
508	}
509
510	properties := p.parsePropertyList(false, false)
511	value.MapValue = properties
512
513	value.EndPos = p.scanner.Position
514	p.accept('}')
515	return
516}
517
518type Expression struct {
519	Args     [2]Value
520	Operator rune
521	Pos      scanner.Position
522}
523
524func (e *Expression) Copy() *Expression {
525	ret := *e
526	ret.Args[0] = e.Args[0].Copy()
527	ret.Args[1] = e.Args[1].Copy()
528	return &ret
529}
530
531func (e *Expression) String() string {
532	return fmt.Sprintf("(%s %c %s)@%d:%s", e.Args[0].String(), e.Operator, e.Args[1].String(),
533		e.Pos.Offset, e.Pos)
534}
535
536type ValueType int
537
538const (
539	Bool ValueType = iota
540	String
541	List
542	Map
543)
544
545func (p ValueType) String() string {
546	switch p {
547	case Bool:
548		return "bool"
549	case String:
550		return "string"
551	case List:
552		return "list"
553	case Map:
554		return "map"
555	default:
556		panic(fmt.Errorf("unknown value type: %d", p))
557	}
558}
559
560type Definition interface {
561	String() string
562	definitionTag()
563}
564
565type Assignment struct {
566	Name       Ident
567	Value      Value
568	OrigValue  Value
569	Pos        scanner.Position
570	Assigner   string
571	Referenced bool
572}
573
574func (a *Assignment) String() string {
575	return fmt.Sprintf("%s@%d:%s %s %s", a.Name, a.Pos.Offset, a.Pos, a.Assigner, a.Value)
576}
577
578func (a *Assignment) definitionTag() {}
579
580type Module struct {
581	Type       Ident
582	Properties []*Property
583	LbracePos  scanner.Position
584	RbracePos  scanner.Position
585}
586
587func (m *Module) Copy() *Module {
588	ret := *m
589	ret.Properties = make([]*Property, len(m.Properties))
590	for i := range m.Properties {
591		ret.Properties[i] = m.Properties[i].Copy()
592	}
593	return &ret
594}
595
596func (m *Module) String() string {
597	propertyStrings := make([]string, len(m.Properties))
598	for i, property := range m.Properties {
599		propertyStrings[i] = property.String()
600	}
601	return fmt.Sprintf("%s@%d:%s-%d:%s{%s}", m.Type,
602		m.LbracePos.Offset, m.LbracePos,
603		m.RbracePos.Offset, m.RbracePos,
604		strings.Join(propertyStrings, ", "))
605}
606
607func (m *Module) definitionTag() {}
608
609type Property struct {
610	Name  Ident
611	Value Value
612	Pos   scanner.Position
613}
614
615func (p *Property) Copy() *Property {
616	ret := *p
617	ret.Value = p.Value.Copy()
618	return &ret
619}
620
621func (p *Property) String() string {
622	return fmt.Sprintf("%s@%d:%s: %s", p.Name, p.Pos.Offset, p.Pos, p.Value)
623}
624
625type Ident struct {
626	Name string
627	Pos  scanner.Position
628}
629
630func (i Ident) String() string {
631	return fmt.Sprintf("%s@%d:%s", i.Name, i.Pos.Offset, i.Pos)
632}
633
634type Value struct {
635	Type        ValueType
636	BoolValue   bool
637	StringValue string
638	ListValue   []Value
639	MapValue    []*Property
640	Expression  *Expression
641	Variable    string
642	Pos         scanner.Position
643	EndPos      scanner.Position
644}
645
646func (p Value) Copy() Value {
647	ret := p
648	if p.MapValue != nil {
649		ret.MapValue = make([]*Property, len(p.MapValue))
650		for i := range p.MapValue {
651			ret.MapValue[i] = p.MapValue[i].Copy()
652		}
653	}
654	if p.ListValue != nil {
655		ret.ListValue = make([]Value, len(p.ListValue))
656		for i := range p.ListValue {
657			ret.ListValue[i] = p.ListValue[i].Copy()
658		}
659	}
660	if p.Expression != nil {
661		ret.Expression = p.Expression.Copy()
662	}
663	return ret
664}
665
666func (p Value) String() string {
667	var s string
668	if p.Variable != "" {
669		s += p.Variable + " = "
670	}
671	if p.Expression != nil {
672		s += p.Expression.String()
673	}
674	switch p.Type {
675	case Bool:
676		s += fmt.Sprintf("%t@%d:%s", p.BoolValue, p.Pos.Offset, p.Pos)
677	case String:
678		s += fmt.Sprintf("%q@%d:%s", p.StringValue, p.Pos.Offset, p.Pos)
679	case List:
680		valueStrings := make([]string, len(p.ListValue))
681		for i, value := range p.ListValue {
682			valueStrings[i] = value.String()
683		}
684		s += fmt.Sprintf("@%d:%s-%d:%s[%s]", p.Pos.Offset, p.Pos, p.EndPos.Offset, p.EndPos,
685			strings.Join(valueStrings, ", "))
686	case Map:
687		propertyStrings := make([]string, len(p.MapValue))
688		for i, property := range p.MapValue {
689			propertyStrings[i] = property.String()
690		}
691		s += fmt.Sprintf("@%d:%s-%d:%s{%s}", p.Pos.Offset, p.Pos, p.EndPos.Offset, p.EndPos,
692			strings.Join(propertyStrings, ", "))
693	default:
694		panic(fmt.Errorf("bad property type: %d", p.Type))
695	}
696
697	return s
698}
699
700type Scope struct {
701	vars          map[string]*Assignment
702	inheritedVars map[string]*Assignment
703}
704
705func NewScope(s *Scope) *Scope {
706	newScope := &Scope{
707		vars:          make(map[string]*Assignment),
708		inheritedVars: make(map[string]*Assignment),
709	}
710
711	if s != nil {
712		for k, v := range s.vars {
713			newScope.inheritedVars[k] = v
714		}
715		for k, v := range s.inheritedVars {
716			newScope.inheritedVars[k] = v
717		}
718	}
719
720	return newScope
721}
722
723func (s *Scope) Add(assignment *Assignment) error {
724	if old, ok := s.vars[assignment.Name.Name]; ok {
725		return fmt.Errorf("variable already set, previous assignment: %s", old)
726	}
727
728	if old, ok := s.inheritedVars[assignment.Name.Name]; ok {
729		return fmt.Errorf("variable already set in inherited scope, previous assignment: %s", old)
730	}
731
732	s.vars[assignment.Name.Name] = assignment
733
734	return nil
735}
736
737func (s *Scope) Remove(name string) {
738	delete(s.vars, name)
739	delete(s.inheritedVars, name)
740}
741
742func (s *Scope) Get(name string) (*Assignment, bool) {
743	if a, ok := s.vars[name]; ok {
744		return a, true
745	}
746
747	if a, ok := s.inheritedVars[name]; ok {
748		return a, false
749	}
750
751	return nil, false
752}
753
754func (s *Scope) String() string {
755	vars := []string{}
756
757	for k := range s.vars {
758		vars = append(vars, k)
759	}
760	for k := range s.inheritedVars {
761		vars = append(vars, k)
762	}
763
764	sort.Strings(vars)
765
766	ret := []string{}
767	for _, v := range vars {
768		if assignment, ok := s.vars[v]; ok {
769			ret = append(ret, assignment.String())
770		} else {
771			ret = append(ret, s.inheritedVars[v].String())
772		}
773	}
774
775	return strings.Join(ret, "\n")
776}
777
778type Comment struct {
779	Comment []string
780	Pos     scanner.Position
781}
782
783func (c Comment) String() string {
784	l := 0
785	for _, comment := range c.Comment {
786		l += len(comment) + 1
787	}
788	buf := make([]byte, 0, l)
789	for _, comment := range c.Comment {
790		buf = append(buf, comment...)
791		buf = append(buf, '\n')
792	}
793
794	return string(buf)
795}
796
797// Return the text of the comment with // or /* and */ stripped
798func (c Comment) Text() string {
799	l := 0
800	for _, comment := range c.Comment {
801		l += len(comment) + 1
802	}
803	buf := make([]byte, 0, l)
804
805	blockComment := false
806	if strings.HasPrefix(c.Comment[0], "/*") {
807		blockComment = true
808	}
809
810	for i, comment := range c.Comment {
811		if blockComment {
812			if i == 0 {
813				comment = strings.TrimPrefix(comment, "/*")
814			}
815			if i == len(c.Comment)-1 {
816				comment = strings.TrimSuffix(comment, "*/")
817			}
818		} else {
819			comment = strings.TrimPrefix(comment, "//")
820		}
821		buf = append(buf, comment...)
822		buf = append(buf, '\n')
823	}
824
825	return string(buf)
826}
827
828// Return the line number that the comment ends on
829func (c Comment) EndLine() int {
830	return c.Pos.Line + len(c.Comment) - 1
831}
832