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