• 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
31const default_select_branch_name = "__soong_conditions_default__"
32const any_select_branch_name = "__soong_conditions_any__"
33
34type ParseError struct {
35	Err error
36	Pos scanner.Position
37}
38
39func (e *ParseError) Error() string {
40	return fmt.Sprintf("%s: %s", e.Pos, e.Err)
41}
42
43type File struct {
44	Name     string
45	Defs     []Definition
46	Comments []*CommentGroup
47}
48
49func parse(p *parser) (file *File, errs []error) {
50	defer func() {
51		if r := recover(); r != nil {
52			if r == errTooManyErrors {
53				errs = p.errors
54				return
55			}
56			panic(r)
57		}
58	}()
59
60	p.next()
61	defs := p.parseDefinitions()
62	p.accept(scanner.EOF)
63	errs = p.errors
64	comments := p.comments
65
66	return &File{
67		Name:     p.scanner.Filename,
68		Defs:     defs,
69		Comments: comments,
70	}, errs
71
72}
73
74func ParseAndEval(filename string, r io.Reader, scope *Scope) (file *File, errs []error) {
75	file, errs = Parse(filename, r)
76	if len(errs) > 0 {
77		return nil, errs
78	}
79
80	// evaluate all module properties
81	var newDefs []Definition
82	for _, def := range file.Defs {
83		switch d := def.(type) {
84		case *Module:
85			for _, prop := range d.Map.Properties {
86				newval, err := prop.Value.Eval(scope)
87				if err != nil {
88					return nil, []error{err}
89				}
90				switch newval.(type) {
91				case *String, *Bool, *Int64, *Select, *Map, *List:
92					// ok
93				default:
94					panic(fmt.Sprintf("Evaled but got %#v\n", newval))
95				}
96				prop.Value = newval
97			}
98			newDefs = append(newDefs, d)
99		case *Assignment:
100			if err := scope.HandleAssignment(d); err != nil {
101				return nil, []error{err}
102			}
103		}
104	}
105
106	// This is not strictly necessary, but removing the assignments from
107	// the result makes it clearer that this is an evaluated file.
108	// We could also consider adding a "EvaluatedFile" type to return.
109	file.Defs = newDefs
110
111	return file, nil
112}
113
114func Parse(filename string, r io.Reader) (file *File, errs []error) {
115	p := newParser(r)
116	p.scanner.Filename = filename
117
118	return parse(p)
119}
120
121func ParseExpression(r io.Reader) (value Expression, errs []error) {
122	p := newParser(r)
123	p.next()
124	value = p.parseExpression()
125	p.accept(scanner.EOF)
126	errs = p.errors
127	return
128}
129
130type parser struct {
131	scanner  scanner.Scanner
132	tok      rune
133	errors   []error
134	comments []*CommentGroup
135}
136
137func newParser(r io.Reader) *parser {
138	p := &parser{}
139	p.scanner.Init(r)
140	p.scanner.Error = func(sc *scanner.Scanner, msg string) {
141		p.errorf(msg)
142	}
143	p.scanner.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanStrings |
144		scanner.ScanRawStrings | scanner.ScanComments
145	return p
146}
147
148func (p *parser) error(err error) {
149	pos := p.scanner.Position
150	if !pos.IsValid() {
151		pos = p.scanner.Pos()
152	}
153	err = &ParseError{
154		Err: err,
155		Pos: pos,
156	}
157	p.errors = append(p.errors, err)
158	if len(p.errors) >= maxErrors {
159		panic(errTooManyErrors)
160	}
161}
162
163func (p *parser) errorf(format string, args ...interface{}) {
164	p.error(fmt.Errorf(format, args...))
165}
166
167func (p *parser) accept(toks ...rune) bool {
168	for _, tok := range toks {
169		if p.tok != tok {
170			p.errorf("expected %s, found %s", scanner.TokenString(tok),
171				scanner.TokenString(p.tok))
172			return false
173		}
174		p.next()
175	}
176	return true
177}
178
179func (p *parser) next() {
180	if p.tok != scanner.EOF {
181		p.tok = p.scanner.Scan()
182		if p.tok == scanner.Comment {
183			var comments []*Comment
184			for p.tok == scanner.Comment {
185				lines := strings.Split(p.scanner.TokenText(), "\n")
186				if len(comments) > 0 && p.scanner.Position.Line > comments[len(comments)-1].End().Line+1 {
187					p.comments = append(p.comments, &CommentGroup{Comments: comments})
188					comments = nil
189				}
190				comments = append(comments, &Comment{lines, p.scanner.Position})
191				p.tok = p.scanner.Scan()
192			}
193			p.comments = append(p.comments, &CommentGroup{Comments: comments})
194		}
195	}
196}
197
198func (p *parser) parseDefinitions() (defs []Definition) {
199	for {
200		switch p.tok {
201		case scanner.Ident:
202			ident := p.scanner.TokenText()
203			pos := p.scanner.Position
204
205			p.accept(scanner.Ident)
206
207			switch p.tok {
208			case '+':
209				p.accept('+')
210				defs = append(defs, p.parseAssignment(ident, pos, "+="))
211			case '=':
212				defs = append(defs, p.parseAssignment(ident, pos, "="))
213			case '{', '(':
214				defs = append(defs, p.parseModule(ident, pos))
215			default:
216				p.errorf("expected \"=\" or \"+=\" or \"{\" or \"(\", found %s",
217					scanner.TokenString(p.tok))
218			}
219		case scanner.EOF:
220			return
221		default:
222			p.errorf("expected assignment or module definition, found %s",
223				scanner.TokenString(p.tok))
224			return
225		}
226	}
227}
228
229func (p *parser) parseAssignment(name string, namePos scanner.Position,
230	assigner string) (assignment *Assignment) {
231
232	// These are used as keywords in select statements, prevent making variables
233	// with the same name to avoid any confusion.
234	switch name {
235	case "default", "unset":
236		p.errorf("'default' and 'unset' are reserved keywords, and cannot be used as variable names")
237		return nil
238	}
239
240	assignment = new(Assignment)
241
242	pos := p.scanner.Position
243	if !p.accept('=') {
244		return
245	}
246	value := p.parseExpression()
247
248	assignment.Name = name
249	assignment.NamePos = namePos
250	assignment.Value = value
251	assignment.EqualsPos = pos
252	assignment.Assigner = assigner
253
254	return
255}
256
257func (p *parser) parseModule(typ string, typPos scanner.Position) *Module {
258
259	compat := false
260	lbracePos := p.scanner.Position
261	if p.tok == '{' {
262		compat = true
263	}
264
265	if !p.accept(p.tok) {
266		return nil
267	}
268	properties := p.parsePropertyList(true, compat)
269	rbracePos := p.scanner.Position
270	if !compat {
271		p.accept(')')
272	} else {
273		p.accept('}')
274	}
275
276	return &Module{
277		Type:    typ,
278		TypePos: typPos,
279		Map: Map{
280			Properties: properties,
281			LBracePos:  lbracePos,
282			RBracePos:  rbracePos,
283		},
284	}
285}
286
287func (p *parser) parsePropertyList(isModule, compat bool) (properties []*Property) {
288	for p.tok == scanner.Ident {
289		properties = append(properties, p.parseProperty(isModule, compat))
290
291		if p.tok != ',' {
292			// There was no comma, so the list is done.
293			break
294		}
295
296		p.accept(',')
297	}
298
299	return
300}
301
302func (p *parser) parseProperty(isModule, compat bool) (property *Property) {
303	property = new(Property)
304
305	name := p.scanner.TokenText()
306	namePos := p.scanner.Position
307	p.accept(scanner.Ident)
308	pos := p.scanner.Position
309
310	if isModule {
311		if compat {
312			if !p.accept(':') {
313				return
314			}
315		} else {
316			if !p.accept('=') {
317				return
318			}
319		}
320	} else {
321		if !p.accept(':') {
322			return
323		}
324	}
325
326	value := p.parseExpression()
327
328	property.Name = name
329	property.NamePos = namePos
330	property.Value = value
331	property.ColonPos = pos
332
333	return
334}
335
336func (p *parser) parseExpression() (value Expression) {
337	value = p.parseValue()
338	switch p.tok {
339	case '+':
340		return p.parseOperator(value)
341	case '-':
342		p.errorf("subtraction not supported: %s", p.scanner.String())
343		return value
344	default:
345		return value
346	}
347}
348
349func (p *parser) parseOperator(value1 Expression) Expression {
350	operator := p.tok
351	pos := p.scanner.Position
352	p.accept(operator)
353
354	value2 := p.parseExpression()
355
356	return &Operator{
357		Args:        [2]Expression{value1, value2},
358		Operator:    operator,
359		OperatorPos: pos,
360	}
361}
362
363func (p *parser) parseValue() (value Expression) {
364	switch p.tok {
365	case scanner.Ident:
366		switch text := p.scanner.TokenText(); text {
367		case "true", "false":
368			return p.parseBoolean()
369		case "select":
370			return p.parseSelect()
371		default:
372			return p.parseVariable()
373		}
374	case '-', scanner.Int: // Integer might have '-' sign ahead ('+' is only treated as operator now)
375		return p.parseIntValue()
376	case scanner.String, scanner.RawString:
377		return p.parseStringValue()
378	case '[':
379		return p.parseListValue()
380	case '{':
381		return p.parseMapValue()
382	default:
383		p.errorf("expected bool, list, or string value; found %s",
384			scanner.TokenString(p.tok))
385		return
386	}
387}
388
389func (p *parser) parseBoolean() Expression {
390	switch text := p.scanner.TokenText(); text {
391	case "true", "false":
392		result := &Bool{
393			LiteralPos: p.scanner.Position,
394			Value:      text == "true",
395			Token:      text,
396		}
397		p.accept(scanner.Ident)
398		return result
399	default:
400		p.errorf("Expected true/false, got %q", text)
401		return nil
402	}
403}
404
405func (p *parser) parseVariable() Expression {
406	var value Expression
407
408	text := p.scanner.TokenText()
409	value = &Variable{
410		Name:    text,
411		NamePos: p.scanner.Position,
412	}
413
414	p.accept(scanner.Ident)
415	return value
416}
417
418func (p *parser) parseSelect() Expression {
419	result := &Select{
420		KeywordPos: p.scanner.Position,
421	}
422	// Read the "select("
423	p.accept(scanner.Ident)
424	if !p.accept('(') {
425		return nil
426	}
427
428	// If we see another '(', there's probably multiple conditions and there must
429	// be a ')' after. Set the multipleConditions variable to remind us to check for
430	// the ')' after.
431	multipleConditions := false
432	if p.tok == '(' {
433		multipleConditions = true
434		p.accept('(')
435	}
436
437	// Read all individual conditions
438	conditions := []ConfigurableCondition{}
439	for first := true; first || multipleConditions; first = false {
440		condition := ConfigurableCondition{
441			position:     p.scanner.Position,
442			FunctionName: p.scanner.TokenText(),
443		}
444		if !p.accept(scanner.Ident) {
445			return nil
446		}
447		if !p.accept('(') {
448			return nil
449		}
450
451		for p.tok != ')' {
452			if s := p.parseStringValue(); s != nil {
453				condition.Args = append(condition.Args, *s)
454			} else {
455				return nil
456			}
457			if p.tok == ')' {
458				break
459			}
460			if !p.accept(',') {
461				return nil
462			}
463		}
464		p.accept(')')
465
466		for _, c := range conditions {
467			if c.Equals(condition) {
468				p.errorf("Duplicate select condition found: %s", c.String())
469			}
470		}
471
472		conditions = append(conditions, condition)
473
474		if multipleConditions {
475			if p.tok == ')' {
476				p.next()
477				break
478			}
479			if !p.accept(',') {
480				return nil
481			}
482			// Retry the closing parent to allow for a trailing comma
483			if p.tok == ')' {
484				p.next()
485				break
486			}
487		}
488	}
489
490	if multipleConditions && len(conditions) < 2 {
491		p.errorf("Expected multiple select conditions due to the extra parenthesis, but only found 1. Please remove the extra parenthesis.")
492		return nil
493	}
494
495	result.Conditions = conditions
496
497	if !p.accept(',') {
498		return nil
499	}
500
501	result.LBracePos = p.scanner.Position
502	if !p.accept('{') {
503		return nil
504	}
505
506	maybeParseBinding := func() (Variable, bool) {
507		if p.scanner.TokenText() != "@" {
508			return Variable{}, false
509		}
510		p.next()
511		value := Variable{
512			Name:    p.scanner.TokenText(),
513			NamePos: p.scanner.Position,
514		}
515		p.accept(scanner.Ident)
516		return value, true
517	}
518
519	parseOnePattern := func() SelectPattern {
520		var result SelectPattern
521		switch p.tok {
522		case scanner.Ident:
523			switch p.scanner.TokenText() {
524			case "any":
525				result.Value = &String{
526					LiteralPos: p.scanner.Position,
527					Value:      any_select_branch_name,
528				}
529				p.next()
530				if binding, exists := maybeParseBinding(); exists {
531					result.Binding = binding
532				}
533				return result
534			case "default":
535				result.Value = &String{
536					LiteralPos: p.scanner.Position,
537					Value:      default_select_branch_name,
538				}
539				p.next()
540				return result
541			case "true":
542				result.Value = &Bool{
543					LiteralPos: p.scanner.Position,
544					Value:      true,
545				}
546				p.next()
547				return result
548			case "false":
549				result.Value = &Bool{
550					LiteralPos: p.scanner.Position,
551					Value:      false,
552				}
553				p.next()
554				return result
555			default:
556				p.errorf("Expected a string, true, false, or default, got %s", p.scanner.TokenText())
557			}
558		case scanner.Int:
559			if i := p.parseIntValue(); i != nil {
560				result.Value = i
561				return result
562			}
563			p.errorf("Expected a string, int, true, false, or default, got %s", p.scanner.TokenText())
564		case scanner.String:
565			if s := p.parseStringValue(); s != nil {
566				if strings.HasPrefix(s.Value, "__soong") {
567					p.errorf("select branch patterns starting with __soong are reserved for internal use")
568					return result
569				}
570				result.Value = s
571				return result
572			}
573			fallthrough
574		default:
575			p.errorf("Expected a string, int, true, false, or default, got %s", p.scanner.TokenText())
576		}
577		return result
578	}
579
580	hasNonUnsetValue := false
581	for p.tok != '}' {
582		c := &SelectCase{}
583
584		if multipleConditions {
585			if !p.accept('(') {
586				return nil
587			}
588			for i := 0; i < len(conditions); i++ {
589				c.Patterns = append(c.Patterns, parseOnePattern())
590				if i < len(conditions)-1 {
591					if !p.accept(',') {
592						return nil
593					}
594				} else if p.tok == ',' {
595					// allow optional trailing comma
596					p.next()
597				}
598			}
599			if !p.accept(')') {
600				return nil
601			}
602		} else {
603			c.Patterns = append(c.Patterns, parseOnePattern())
604		}
605		c.ColonPos = p.scanner.Position
606		if !p.accept(':') {
607			return nil
608		}
609		if p.tok == scanner.Ident && p.scanner.TokenText() == "unset" {
610			c.Value = &UnsetProperty{Position: p.scanner.Position}
611			p.accept(scanner.Ident)
612		} else {
613			hasNonUnsetValue = true
614			c.Value = p.parseExpression()
615		}
616		// allow trailing comma, require it if not seeing a }
617		if p.tok != '}' {
618			if !p.accept(',') {
619				return nil
620			}
621		}
622		result.Cases = append(result.Cases, c)
623	}
624
625	// If all branches have the value "unset", then this is equivalent
626	// to an empty select.
627	if !hasNonUnsetValue {
628		p.errorf("This select statement is empty, remove it")
629		return nil
630	}
631
632	patternsEqual := func(a, b SelectPattern) bool {
633		// We can ignore the bindings, they don't affect which pattern is matched
634		switch a2 := a.Value.(type) {
635		case *String:
636			if b2, ok := b.Value.(*String); ok {
637				return a2.Value == b2.Value
638			} else {
639				return false
640			}
641		case *Bool:
642			if b2, ok := b.Value.(*Bool); ok {
643				return a2.Value == b2.Value
644			} else {
645				return false
646			}
647		case *Int64:
648			if b2, ok := b.Value.(*Int64); ok {
649				return a2.Value == b2.Value
650			} else {
651				return false
652			}
653		default:
654			// true so that we produce an error in this unexpected scenario
655			return true
656		}
657	}
658
659	patternListsEqual := func(a, b []SelectPattern) bool {
660		if len(a) != len(b) {
661			return false
662		}
663		for i := range a {
664			if !patternsEqual(a[i], b[i]) {
665				return false
666			}
667		}
668		return true
669	}
670
671	for i, c := range result.Cases {
672		// Check for duplicate patterns across different branches
673		for _, d := range result.Cases[i+1:] {
674			if patternListsEqual(c.Patterns, d.Patterns) {
675				p.errorf("Found duplicate select patterns: %v", c.Patterns)
676				return nil
677			}
678		}
679		// check for duplicate bindings within this branch
680		for i := range c.Patterns {
681			if c.Patterns[i].Binding.Name != "" {
682				for j := i + 1; j < len(c.Patterns); j++ {
683					if c.Patterns[i].Binding.Name == c.Patterns[j].Binding.Name {
684						p.errorf("Found duplicate select pattern binding: %s", c.Patterns[i].Binding.Name)
685						return nil
686					}
687				}
688			}
689		}
690		// Check that the only all-default cases is the last one
691		if i < len(result.Cases)-1 {
692			isAllDefault := true
693			for _, x := range c.Patterns {
694				if x2, ok := x.Value.(*String); !ok || x2.Value != default_select_branch_name {
695					isAllDefault = false
696					break
697				}
698			}
699			if isAllDefault {
700				p.errorf("Found a default select branch at index %d, expected it to be last (index %d)", i, len(result.Cases)-1)
701				return nil
702			}
703		}
704	}
705
706	result.RBracePos = p.scanner.Position
707	if !p.accept('}') {
708		return nil
709	}
710	if !p.accept(')') {
711		return nil
712	}
713	return result
714}
715
716func (p *parser) parseStringValue() *String {
717	str, err := strconv.Unquote(p.scanner.TokenText())
718	if err != nil {
719		p.errorf("couldn't parse string: %s", err)
720		return nil
721	}
722
723	value := &String{
724		LiteralPos: p.scanner.Position,
725		Value:      str,
726	}
727	p.accept(p.tok)
728	return value
729}
730
731func (p *parser) parseIntValue() *Int64 {
732	var str string
733	literalPos := p.scanner.Position
734	if p.tok == '-' {
735		str += string(p.tok)
736		p.accept(p.tok)
737		if p.tok != scanner.Int {
738			p.errorf("expected int; found %s", scanner.TokenString(p.tok))
739			return nil
740		}
741	}
742	str += p.scanner.TokenText()
743	i, err := strconv.ParseInt(str, 10, 64)
744	if err != nil {
745		p.errorf("couldn't parse int: %s", err)
746		return nil
747	}
748
749	value := &Int64{
750		LiteralPos: literalPos,
751		Value:      i,
752		Token:      str,
753	}
754	p.accept(scanner.Int)
755	return value
756}
757
758func (p *parser) parseListValue() *List {
759	lBracePos := p.scanner.Position
760	if !p.accept('[') {
761		return nil
762	}
763
764	var elements []Expression
765	for p.tok != ']' {
766		element := p.parseExpression()
767		elements = append(elements, element)
768
769		if p.tok != ',' {
770			// There was no comma, so the list is done.
771			break
772		}
773
774		p.accept(',')
775	}
776
777	rBracePos := p.scanner.Position
778	p.accept(']')
779
780	return &List{
781		LBracePos: lBracePos,
782		RBracePos: rBracePos,
783		Values:    elements,
784	}
785}
786
787func (p *parser) parseMapValue() *Map {
788	lBracePos := p.scanner.Position
789	if !p.accept('{') {
790		return nil
791	}
792
793	properties := p.parsePropertyList(false, false)
794
795	rBracePos := p.scanner.Position
796	p.accept('}')
797
798	return &Map{
799		LBracePos:  lBracePos,
800		RBracePos:  rBracePos,
801		Properties: properties,
802	}
803}
804
805type Scope struct {
806	vars              map[string]*Assignment
807	preventInheriting map[string]bool
808	parentScope       *Scope
809}
810
811func NewScope(s *Scope) *Scope {
812	return &Scope{
813		vars:              make(map[string]*Assignment),
814		preventInheriting: make(map[string]bool),
815		parentScope:       s,
816	}
817}
818
819func (s *Scope) HandleAssignment(assignment *Assignment) error {
820	switch assignment.Assigner {
821	case "+=":
822		if !s.preventInheriting[assignment.Name] && s.parentScope.Get(assignment.Name) != nil {
823			return fmt.Errorf("modified non-local variable %q with +=", assignment.Name)
824		}
825		if old, ok := s.vars[assignment.Name]; !ok {
826			return fmt.Errorf("modified non-existent variable %q with +=", assignment.Name)
827		} else if old.Referenced {
828			return fmt.Errorf("modified variable %q with += after referencing", assignment.Name)
829		} else {
830			newValue, err := evaluateOperator(s, '+', old.Value, assignment.Value)
831			if err != nil {
832				return err
833			}
834			old.Value = newValue
835		}
836	case "=":
837		if old, ok := s.vars[assignment.Name]; ok {
838			return fmt.Errorf("variable already set, previous assignment: %s", old)
839		}
840
841		if old := s.parentScope.Get(assignment.Name); old != nil && !s.preventInheriting[assignment.Name] {
842			return fmt.Errorf("variable already set in inherited scope, previous assignment: %s", old)
843		}
844
845		if newValue, err := assignment.Value.Eval(s); err != nil {
846			return err
847		} else {
848			assignment.Value = newValue
849		}
850		s.vars[assignment.Name] = assignment
851	default:
852		return fmt.Errorf("Unknown assigner '%s'", assignment.Assigner)
853	}
854	return nil
855}
856
857func (s *Scope) Get(name string) *Assignment {
858	if s == nil {
859		return nil
860	}
861	if a, ok := s.vars[name]; ok {
862		return a
863	}
864	if s.preventInheriting[name] {
865		return nil
866	}
867	return s.parentScope.Get(name)
868}
869
870func (s *Scope) GetLocal(name string) *Assignment {
871	if s == nil {
872		return nil
873	}
874	if a, ok := s.vars[name]; ok {
875		return a
876	}
877	return nil
878}
879
880// DontInherit prevents this scope from inheriting the given variable from its
881// parent scope.
882func (s *Scope) DontInherit(name string) {
883	s.preventInheriting[name] = true
884}
885
886func (s *Scope) String() string {
887	var sb strings.Builder
888	s.stringInner(&sb)
889	return sb.String()
890}
891
892func (s *Scope) stringInner(sb *strings.Builder) {
893	if s == nil {
894		return
895	}
896	vars := make([]string, 0, len(s.vars))
897	for k := range s.vars {
898		vars = append(vars, k)
899	}
900
901	sort.Strings(vars)
902
903	for _, v := range vars {
904		sb.WriteString(s.vars[v].String())
905		sb.WriteRune('\n')
906	}
907
908	s.parentScope.stringInner(sb)
909}
910