• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.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 && p.tok == ':' {
306			p.accept(':')
307		} else {
308			if !p.accept('=') {
309				return
310			}
311		}
312	} else {
313		if !p.accept(':') {
314			return
315		}
316	}
317
318	value := p.parseExpression()
319
320	property.Name = name
321	property.NamePos = namePos
322	property.Value = value
323	property.ColonPos = pos
324
325	return
326}
327
328func (p *parser) parseExpression() (value Expression) {
329	value = p.parseValue()
330	switch p.tok {
331	case '+':
332		return p.parseOperator(value)
333	default:
334		return value
335	}
336}
337
338func (p *parser) evaluateOperator(value1, value2 Expression, operator rune,
339	pos scanner.Position) (*Operator, error) {
340
341	value := value1
342
343	if p.eval {
344		e1 := value1.Eval()
345		e2 := value2.Eval()
346		if e1.Type() != e2.Type() {
347			return nil, fmt.Errorf("mismatched type in operator %c: %s != %s", operator,
348				e1.Type(), e2.Type())
349		}
350
351		value = e1.Copy()
352
353		switch operator {
354		case '+':
355			switch v := value.(type) {
356			case *String:
357				v.Value += e2.(*String).Value
358			case *List:
359				v.Values = append(v.Values, e2.(*List).Values...)
360			case *Map:
361				var err error
362				v.Properties, err = p.addMaps(v.Properties, e2.(*Map).Properties, pos)
363				if err != nil {
364					return nil, err
365				}
366			default:
367				return nil, fmt.Errorf("operator %c not supported on type %s", operator, v.Type())
368			}
369		default:
370			panic("unknown operator " + string(operator))
371		}
372	}
373
374	return &Operator{
375		Args:        [2]Expression{value1, value2},
376		Operator:    operator,
377		OperatorPos: pos,
378		Value:       value,
379	}, nil
380}
381
382func (p *parser) addMaps(map1, map2 []*Property, pos scanner.Position) ([]*Property, error) {
383	ret := make([]*Property, 0, len(map1))
384
385	inMap1 := make(map[string]*Property)
386	inMap2 := make(map[string]*Property)
387	inBoth := make(map[string]*Property)
388
389	for _, prop1 := range map1 {
390		inMap1[prop1.Name] = prop1
391	}
392
393	for _, prop2 := range map2 {
394		inMap2[prop2.Name] = prop2
395		if _, ok := inMap1[prop2.Name]; ok {
396			inBoth[prop2.Name] = prop2
397		}
398	}
399
400	for _, prop1 := range map1 {
401		if prop2, ok := inBoth[prop1.Name]; ok {
402			var err error
403			newProp := *prop1
404			newProp.Value, err = p.evaluateOperator(prop1.Value, prop2.Value, '+', pos)
405			if err != nil {
406				return nil, err
407			}
408			ret = append(ret, &newProp)
409		} else {
410			ret = append(ret, prop1)
411		}
412	}
413
414	for _, prop2 := range map2 {
415		if _, ok := inBoth[prop2.Name]; !ok {
416			ret = append(ret, prop2)
417		}
418	}
419
420	return ret, nil
421}
422
423func (p *parser) parseOperator(value1 Expression) *Operator {
424	operator := p.tok
425	pos := p.scanner.Position
426	p.accept(operator)
427
428	value2 := p.parseExpression()
429
430	value, err := p.evaluateOperator(value1, value2, operator, pos)
431	if err != nil {
432		p.error(err)
433		return nil
434	}
435
436	return value
437
438}
439
440func (p *parser) parseValue() (value Expression) {
441	switch p.tok {
442	case scanner.Ident:
443		return p.parseVariable()
444	case scanner.String:
445		return p.parseStringValue()
446	case '[':
447		return p.parseListValue()
448	case '{':
449		return p.parseMapValue()
450	default:
451		p.errorf("expected bool, list, or string value; found %s",
452			scanner.TokenString(p.tok))
453		return
454	}
455}
456
457func (p *parser) parseVariable() Expression {
458	var value Expression
459
460	switch text := p.scanner.TokenText(); text {
461	case "true", "false":
462		value = &Bool{
463			LiteralPos: p.scanner.Position,
464			Value:      text == "true",
465		}
466	default:
467		if p.eval {
468			if assignment, local := p.scope.Get(text); assignment == nil {
469				p.errorf("variable %q is not set", text)
470			} else {
471				if local {
472					assignment.Referenced = true
473				}
474				value = assignment.Value
475			}
476		}
477		value = &Variable{
478			Name:    text,
479			NamePos: p.scanner.Position,
480			Value:   value,
481		}
482	}
483
484	p.accept(scanner.Ident)
485	return value
486}
487
488func (p *parser) parseStringValue() *String {
489	str, err := strconv.Unquote(p.scanner.TokenText())
490	if err != nil {
491		p.errorf("couldn't parse string: %s", err)
492		return nil
493	}
494
495	value := &String{
496		LiteralPos: p.scanner.Position,
497		Value:      str,
498	}
499	p.accept(scanner.String)
500	return value
501}
502
503func (p *parser) parseListValue() *List {
504	lBracePos := p.scanner.Position
505	if !p.accept('[') {
506		return nil
507	}
508
509	var elements []Expression
510	for p.tok != ']' {
511		element := p.parseExpression()
512		if p.eval && element.Type() != StringType {
513			p.errorf("Expected string in list, found %s", element.Type().String())
514			return nil
515		}
516		elements = append(elements, element)
517
518		if p.tok != ',' {
519			// There was no comma, so the list is done.
520			break
521		}
522
523		p.accept(',')
524	}
525
526	rBracePos := p.scanner.Position
527	p.accept(']')
528
529	return &List{
530		LBracePos: lBracePos,
531		RBracePos: rBracePos,
532		Values:    elements,
533	}
534}
535
536func (p *parser) parseMapValue() *Map {
537	lBracePos := p.scanner.Position
538	if !p.accept('{') {
539		return nil
540	}
541
542	properties := p.parsePropertyList(false, false)
543
544	rBracePos := p.scanner.Position
545	p.accept('}')
546
547	return &Map{
548		LBracePos:  lBracePos,
549		RBracePos:  rBracePos,
550		Properties: properties,
551	}
552}
553
554type Scope struct {
555	vars          map[string]*Assignment
556	inheritedVars map[string]*Assignment
557}
558
559func NewScope(s *Scope) *Scope {
560	newScope := &Scope{
561		vars:          make(map[string]*Assignment),
562		inheritedVars: make(map[string]*Assignment),
563	}
564
565	if s != nil {
566		for k, v := range s.vars {
567			newScope.inheritedVars[k] = v
568		}
569		for k, v := range s.inheritedVars {
570			newScope.inheritedVars[k] = v
571		}
572	}
573
574	return newScope
575}
576
577func (s *Scope) Add(assignment *Assignment) error {
578	if old, ok := s.vars[assignment.Name]; ok {
579		return fmt.Errorf("variable already set, previous assignment: %s", old)
580	}
581
582	if old, ok := s.inheritedVars[assignment.Name]; ok {
583		return fmt.Errorf("variable already set in inherited scope, previous assignment: %s", old)
584	}
585
586	s.vars[assignment.Name] = assignment
587
588	return nil
589}
590
591func (s *Scope) Remove(name string) {
592	delete(s.vars, name)
593	delete(s.inheritedVars, name)
594}
595
596func (s *Scope) Get(name string) (*Assignment, bool) {
597	if a, ok := s.vars[name]; ok {
598		return a, true
599	}
600
601	if a, ok := s.inheritedVars[name]; ok {
602		return a, false
603	}
604
605	return nil, false
606}
607
608func (s *Scope) String() string {
609	vars := []string{}
610
611	for k := range s.vars {
612		vars = append(vars, k)
613	}
614	for k := range s.inheritedVars {
615		vars = append(vars, k)
616	}
617
618	sort.Strings(vars)
619
620	ret := []string{}
621	for _, v := range vars {
622		if assignment, ok := s.vars[v]; ok {
623			ret = append(ret, assignment.String())
624		} else {
625			ret = append(ret, s.inheritedVars[v].String())
626		}
627	}
628
629	return strings.Join(ret, "\n")
630}
631