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