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