// Copyright 2014 Google Inc. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package parser

import (
 "errors"
 "fmt"
 "io"
 "sort"
 "strconv"
 "strings"
 "text/scanner"
)

var errTooManyErrors = errors.New("too many errors")

const maxErrors = 1

const default_select_branch_name = "__soong_conditions_default__"
const any_select_branch_name = "__soong_conditions_any__"

type ParseError struct {
 Err error
 Pos scanner.Position
}

func (e *ParseError) Error() string {
 return fmt.Sprintf("%s: %s", e.Pos, e.Err)
}

type File struct {
 Name     string
 Defs     []Definition
 Comments []*CommentGroup
}

func parse(p *parser) (file *File, errs []error) {
 defer func() {
  if r := recover(); r != nil {
   if r == errTooManyErrors {
    errs = p.errors
    return
   }
   panic(r)
  }
 }()

 p.next()
 defs := p.parseDefinitions()
 p.accept(scanner.EOF)
 errs = p.errors
 comments := p.comments

 return &File{
  Name:     p.scanner.Filename,
  Defs:     defs,
  Comments: comments,
 }, errs

}

func ParseAndEval(filename string, r io.Reader, scope *Scope) (file *File, errs []error) {
 file, errs = Parse(filename, r)
 if len(errs) > 0 {
  return nil, errs
 }

 // evaluate all module properties
 var newDefs []Definition
 for _, def := range file.Defs {
  switch d := def.(type) {
  case *Module:
   for _, prop := range d.Map.Properties {
    newval, err := prop.Value.Eval(scope)
    if err != nil {
     return nil, []error{err}
    }
    switch newval.(type) {
    case *String, *Bool, *Int64, *Select, *Map, *List:
     // ok
    default:
     panic(fmt.Sprintf("Evaled but got %#v\n", newval))
    }
    prop.Value = newval
   }
   newDefs = append(newDefs, d)
  case *Assignment:
   if err := scope.HandleAssignment(d); err != nil {
    return nil, []error{err}
   }
  }
 }

 // This is not strictly necessary, but removing the assignments from
 // the result makes it clearer that this is an evaluated file.
 // We could also consider adding a "EvaluatedFile" type to return.
 file.Defs = newDefs

 return file, nil
}

func Parse(filename string, r io.Reader) (file *File, errs []error) {
 p := newParser(r)
 p.scanner.Filename = filename

 return parse(p)
}

func ParseExpression(r io.Reader) (value Expression, errs []error) {
 p := newParser(r)
 p.next()
 value = p.parseExpression()
 p.accept(scanner.EOF)
 errs = p.errors
 return
}

type parser struct {
 scanner  scanner.Scanner
 tok      rune
 errors   []error
 comments []*CommentGroup
}

func newParser(r io.Reader) *parser {
 p := &parser{}
 p.scanner.Init(r)
 p.scanner.Error = func(sc *scanner.Scanner, msg string) {
  p.errorf(msg)
 }
 p.scanner.Mode = scanner.ScanIdents | scanner.ScanInts | scanner.ScanStrings |
  scanner.ScanRawStrings | scanner.ScanComments
 return p
}

func (p *parser) error(err error) {
 pos := p.scanner.Position
 if !pos.IsValid() {
  pos = p.scanner.Pos()
 }
 err = &ParseError{
  Err: err,
  Pos: pos,
 }
 p.errors = append(p.errors, err)
 if len(p.errors) >= maxErrors {
  panic(errTooManyErrors)
 }
}

func (p *parser) errorf(format string, args ...interface{}) {
 p.error(fmt.Errorf(format, args...))
}

func (p *parser) accept(toks ...rune) bool {
 for _, tok := range toks {
  if p.tok != tok {
   p.errorf("expected %s, found %s", scanner.TokenString(tok),
    scanner.TokenString(p.tok))
   return false
  }
  p.next()
 }
 return true
}

func (p *parser) next() {
 if p.tok != scanner.EOF {
  p.tok = p.scanner.Scan()
  if p.tok == scanner.Comment {
   var comments []*Comment
   for p.tok == scanner.Comment {
    lines := strings.Split(p.scanner.TokenText(), "\n")
    if len(comments) > 0 && p.scanner.Position.Line > comments[len(comments)-1].End().Line+1 {
     p.comments = append(p.comments, &CommentGroup{Comments: comments})
     comments = nil
    }
    comments = append(comments, &Comment{lines, p.scanner.Position})
    p.tok = p.scanner.Scan()
   }
   p.comments = append(p.comments, &CommentGroup{Comments: comments})
  }
 }
}

func (p *parser) parseDefinitions() (defs []Definition) {
 for {
  switch p.tok {
  case scanner.Ident:
   ident := p.scanner.TokenText()
   pos := p.scanner.Position

   p.accept(scanner.Ident)

   switch p.tok {
   case '+':
    p.accept('+')
    defs = append(defs, p.parseAssignment(ident, pos, "+="))
   case '=':
    defs = append(defs, p.parseAssignment(ident, pos, "="))
   case '{', '(':
    defs = append(defs, p.parseModule(ident, pos))
   default:
    p.errorf("expected \"=\" or \"+=\" or \"{\" or \"(\", found %s",
     scanner.TokenString(p.tok))
   }
  case scanner.EOF:
   return
  default:
   p.errorf("expected assignment or module definition, found %s",
    scanner.TokenString(p.tok))
   return
  }
 }
}

func (p *parser) parseAssignment(name string, namePos scanner.Position,
 assigner string) (assignment *Assignment) {

 // These are used as keywords in select statements, prevent making variables
 // with the same name to avoid any confusion.
 switch name {
 case "default", "unset":
  p.errorf("'default' and 'unset' are reserved keywords, and cannot be used as variable names")
  return nil
 }

 assignment = new(Assignment)

 pos := p.scanner.Position
 if !p.accept('=') {
  return
 }
 value := p.parseExpression()

 assignment.Name = name
 assignment.NamePos = namePos
 assignment.Value = value
 assignment.EqualsPos = pos
 assignment.Assigner = assigner

 return
}

func (p *parser) parseModule(typ string, typPos scanner.Position) *Module {

 compat := false
 lbracePos := p.scanner.Position
 if p.tok == '{' {
  compat = true
 }

 if !p.accept(p.tok) {
  return nil
 }
 properties := p.parsePropertyList(true, compat)
 rbracePos := p.scanner.Position
 if !compat {
  p.accept(')')
 } else {
  p.accept('}')
 }

 return &Module{
  Type:    typ,
  TypePos: typPos,
  Map: Map{
   Properties: properties,
   LBracePos:  lbracePos,
   RBracePos:  rbracePos,
  },
 }
}

func (p *parser) parsePropertyList(isModule, compat bool) (properties []*Property) {
 for p.tok == scanner.Ident {
  properties = append(properties, p.parseProperty(isModule, compat))

  if p.tok != ',' {
   // There was no comma, so the list is done.
   break
  }

  p.accept(',')
 }

 return
}

func (p *parser) parseProperty(isModule, compat bool) (property *Property) {
 property = new(Property)

 name := p.scanner.TokenText()
 namePos := p.scanner.Position
 p.accept(scanner.Ident)
 pos := p.scanner.Position

 if isModule {
  if compat {
   if !p.accept(':') {
    return
   }
  } else {
   if !p.accept('=') {
    return
   }
  }
 } else {
  if !p.accept(':') {
   return
  }
 }

 value := p.parseExpression()

 property.Name = name
 property.NamePos = namePos
 property.Value = value
 property.ColonPos = pos

 return
}

func (p *parser) parseExpression() (value Expression) {
 value = p.parseValue()
 switch p.tok {
 case '+':
  return p.parseOperator(value)
 case '-':
  p.errorf("subtraction not supported: %s", p.scanner.String())
  return value
 default:
  return value
 }
}

func (p *parser) parseOperator(value1 Expression) Expression {
 operator := p.tok
 pos := p.scanner.Position
 p.accept(operator)

 value2 := p.parseExpression()

 return &Operator{
  Args:        [2]Expression{value1, value2},
  Operator:    operator,
  OperatorPos: pos,
 }
}

func (p *parser) parseValue() (value Expression) {
 switch p.tok {
 case scanner.Ident:
  switch text := p.scanner.TokenText(); text {
  case "true", "false":
   return p.parseBoolean()
  case "select":
   return p.parseSelect()
  default:
   return p.parseVariable()
  }
 case '-', scanner.Int: // Integer might have '-' sign ahead ('+' is only treated as operator now)
  return p.parseIntValue()
 case scanner.String, scanner.RawString:
  return p.parseStringValue()
 case '[':
  return p.parseListValue()
 case '{':
  return p.parseMapValue()
 default:
  p.errorf("expected bool, list, or string value; found %s",
   scanner.TokenString(p.tok))
  return
 }
}

func (p *parser) parseBoolean() Expression {
 switch text := p.scanner.TokenText(); text {
 case "true", "false":
  result := &Bool{
   LiteralPos: p.scanner.Position,
   Value:      text == "true",
   Token:      text,
  }
  p.accept(scanner.Ident)
  return result
 default:
  p.errorf("Expected true/false, got %q", text)
  return nil
 }
}

func (p *parser) parseVariable() Expression {
 var value Expression

 text := p.scanner.TokenText()
 value = &Variable{
  Name:    text,
  NamePos: p.scanner.Position,
 }

 p.accept(scanner.Ident)
 return value
}

func (p *parser) parseSelect() Expression {
 result := &Select{
  KeywordPos: p.scanner.Position,
 }
 // Read the "select("
 p.accept(scanner.Ident)
 if !p.accept('(') {
  return nil
 }

 // If we see another '(', there's probably multiple conditions and there must
 // be a ')' after. Set the multipleConditions variable to remind us to check for
 // the ')' after.
 multipleConditions := false
 if p.tok == '(' {
  multipleConditions = true
  p.accept('(')
 }

 // Read all individual conditions
 conditions := []ConfigurableCondition{}
 for first := true; first || multipleConditions; first = false {
  condition := ConfigurableCondition{
   position:     p.scanner.Position,
   FunctionName: p.scanner.TokenText(),
  }
  if !p.accept(scanner.Ident) {
   return nil
  }
  if !p.accept('(') {
   return nil
  }

  for p.tok != ')' {
   if s := p.parseStringValue(); s != nil {
    condition.Args = append(condition.Args, *s)
   } else {
    return nil
   }
   if p.tok == ')' {
    break
   }
   if !p.accept(',') {
    return nil
   }
  }
  p.accept(')')

  for _, c := range conditions {
   if c.Equals(condition) {
    p.errorf("Duplicate select condition found: %s", c.String())
   }
  }

  conditions = append(conditions, condition)

  if multipleConditions {
   if p.tok == ')' {
    p.next()
    break
   }
   if !p.accept(',') {
    return nil
   }
   // Retry the closing parent to allow for a trailing comma
   if p.tok == ')' {
    p.next()
    break
   }
  }
 }

 if multipleConditions && len(conditions) < 2 {
  p.errorf("Expected multiple select conditions due to the extra parenthesis, but only found 1. Please remove the extra parenthesis.")
  return nil
 }

 result.Conditions = conditions

 if !p.accept(',') {
  return nil
 }

 result.LBracePos = p.scanner.Position
 if !p.accept('{') {
  return nil
 }

 maybeParseBinding := func() (Variable, bool) {
  if p.scanner.TokenText() != "@" {
   return Variable{}, false
  }
  p.next()
  value := Variable{
   Name:    p.scanner.TokenText(),
   NamePos: p.scanner.Position,
  }
  p.accept(scanner.Ident)
  return value, true
 }

 parseOnePattern := func() SelectPattern {
  var result SelectPattern
  switch p.tok {
  case scanner.Ident:
   switch p.scanner.TokenText() {
   case "any":
    result.Value = &String{
     LiteralPos: p.scanner.Position,
     Value:      any_select_branch_name,
    }
    p.next()
    if binding, exists := maybeParseBinding(); exists {
     result.Binding = binding
    }
    return result
   case "default":
    result.Value = &String{
     LiteralPos: p.scanner.Position,
     Value:      default_select_branch_name,
    }
    p.next()
    return result
   case "true":
    result.Value = &Bool{
     LiteralPos: p.scanner.Position,
     Value:      true,
    }
    p.next()
    return result
   case "false":
    result.Value = &Bool{
     LiteralPos: p.scanner.Position,
     Value:      false,
    }
    p.next()
    return result
   default:
    p.errorf("Expected a string, true, false, or default, got %s", p.scanner.TokenText())
   }
  case scanner.Int:
   if i := p.parseIntValue(); i != nil {
    result.Value = i
    return result
   }
   p.errorf("Expected a string, int, true, false, or default, got %s", p.scanner.TokenText())
  case scanner.String:
   if s := p.parseStringValue(); s != nil {
    if strings.HasPrefix(s.Value, "__soong") {
     p.errorf("select branch patterns starting with __soong are reserved for internal use")
     return result
    }
    result.Value = s
    return result
   }
   fallthrough
  default:
   p.errorf("Expected a string, int, true, false, or default, got %s", p.scanner.TokenText())
  }
  return result
 }

 hasNonUnsetValue := false
 for p.tok != '}' {
  c := &SelectCase{}

  if multipleConditions {
   if !p.accept('(') {
    return nil
   }
   for i := 0; i < len(conditions); i++ {
    c.Patterns = append(c.Patterns, parseOnePattern())
    if i < len(conditions)-1 {
     if !p.accept(',') {
      return nil
     }
    } else if p.tok == ',' {
     // allow optional trailing comma
     p.next()
    }
   }
   if !p.accept(')') {
    return nil
   }
  } else {
   c.Patterns = append(c.Patterns, parseOnePattern())
  }
  c.ColonPos = p.scanner.Position
  if !p.accept(':') {
   return nil
  }
  if p.tok == scanner.Ident && p.scanner.TokenText() == "unset" {
   c.Value = &UnsetProperty{Position: p.scanner.Position}
   p.accept(scanner.Ident)
  } else {
   hasNonUnsetValue = true
   c.Value = p.parseExpression()
  }
  // allow trailing comma, require it if not seeing a }
  if p.tok != '}' {
   if !p.accept(',') {
    return nil
   }
  }
  result.Cases = append(result.Cases, c)
 }

 // If all branches have the value "unset", then this is equivalent
 // to an empty select.
 if !hasNonUnsetValue {
  p.errorf("This select statement is empty, remove it")
  return nil
 }

 patternsEqual := func(a, b SelectPattern) bool {
  // We can ignore the bindings, they don't affect which pattern is matched
  switch a2 := a.Value.(type) {
  case *String:
   if b2, ok := b.Value.(*String); ok {
    return a2.Value == b2.Value
   } else {
    return false
   }
  case *Bool:
   if b2, ok := b.Value.(*Bool); ok {
    return a2.Value == b2.Value
   } else {
    return false
   }
  case *Int64:
   if b2, ok := b.Value.(*Int64); ok {
    return a2.Value == b2.Value
   } else {
    return false
   }
  default:
   // true so that we produce an error in this unexpected scenario
   return true
  }
 }

 patternListsEqual := func(a, b []SelectPattern) bool {
  if len(a) != len(b) {
   return false
  }
  for i := range a {
   if !patternsEqual(a[i], b[i]) {
    return false
   }
  }
  return true
 }

 for i, c := range result.Cases {
  // Check for duplicate patterns across different branches
  for _, d := range result.Cases[i+1:] {
   if patternListsEqual(c.Patterns, d.Patterns) {
    p.errorf("Found duplicate select patterns: %v", c.Patterns)
    return nil
   }
  }
  // check for duplicate bindings within this branch
  for i := range c.Patterns {
   if c.Patterns[i].Binding.Name != "" {
    for j := i + 1; j < len(c.Patterns); j++ {
     if c.Patterns[i].Binding.Name == c.Patterns[j].Binding.Name {
      p.errorf("Found duplicate select pattern binding: %s", c.Patterns[i].Binding.Name)
      return nil
     }
    }
   }
  }
  // Check that the only all-default cases is the last one
  if i < len(result.Cases)-1 {
   isAllDefault := true
   for _, x := range c.Patterns {
    if x2, ok := x.Value.(*String); !ok || x2.Value != default_select_branch_name {
     isAllDefault = false
     break
    }
   }
   if isAllDefault {
    p.errorf("Found a default select branch at index %d, expected it to be last (index %d)", i, len(result.Cases)-1)
    return nil
   }
  }
 }

 result.RBracePos = p.scanner.Position
 if !p.accept('}') {
  return nil
 }
 if !p.accept(')') {
  return nil
 }
 return result
}

func (p *parser) parseStringValue() *String {
 str, err := strconv.Unquote(p.scanner.TokenText())
 if err != nil {
  p.errorf("couldn't parse string: %s", err)
  return nil
 }

 value := &String{
  LiteralPos: p.scanner.Position,
  Value:      str,
 }
 p.accept(p.tok)
 return value
}

func (p *parser) parseIntValue() *Int64 {
 var str string
 literalPos := p.scanner.Position
 if p.tok == '-' {
  str += string(p.tok)
  p.accept(p.tok)
  if p.tok != scanner.Int {
   p.errorf("expected int; found %s", scanner.TokenString(p.tok))
   return nil
  }
 }
 str += p.scanner.TokenText()
 i, err := strconv.ParseInt(str, 10, 64)
 if err != nil {
  p.errorf("couldn't parse int: %s", err)
  return nil
 }

 value := &Int64{
  LiteralPos: literalPos,
  Value:      i,
  Token:      str,
 }
 p.accept(scanner.Int)
 return value
}

func (p *parser) parseListValue() *List {
 lBracePos := p.scanner.Position
 if !p.accept('[') {
  return nil
 }

 var elements []Expression
 for p.tok != ']' {
  element := p.parseExpression()
  elements = append(elements, element)

  if p.tok != ',' {
   // There was no comma, so the list is done.
   break
  }

  p.accept(',')
 }

 rBracePos := p.scanner.Position
 p.accept(']')

 return &List{
  LBracePos: lBracePos,
  RBracePos: rBracePos,
  Values:    elements,
 }
}

func (p *parser) parseMapValue() *Map {
 lBracePos := p.scanner.Position
 if !p.accept('{') {
  return nil
 }

 properties := p.parsePropertyList(false, false)

 rBracePos := p.scanner.Position
 p.accept('}')

 return &Map{
  LBracePos:  lBracePos,
  RBracePos:  rBracePos,
  Properties: properties,
 }
}

type Scope struct {
 vars              map[string]*Assignment
 preventInheriting map[string]bool
 parentScope       *Scope
}

func NewScope(s *Scope) *Scope {
 return &Scope{
  vars:              make(map[string]*Assignment),
  preventInheriting: make(map[string]bool),
  parentScope:       s,
 }
}

func (s *Scope) HandleAssignment(assignment *Assignment) error {
 switch assignment.Assigner {
 case "+=":
  if !s.preventInheriting[assignment.Name] && s.parentScope.Get(assignment.Name) != nil {
   return fmt.Errorf("modified non-local variable %q with +=", assignment.Name)
  }
  if old, ok := s.vars[assignment.Name]; !ok {
   return fmt.Errorf("modified non-existent variable %q with +=", assignment.Name)
  } else if old.Referenced.Load() {
   return fmt.Errorf("modified variable %q with += after referencing", assignment.Name)
  } else {
   newValue, err := evaluateOperator(s, '+', old.Value, assignment.Value)
   if err != nil {
    return err
   }
   old.Value = newValue
  }
 case "=":
  if old, ok := s.vars[assignment.Name]; ok {
   return fmt.Errorf("variable already set, previous assignment: %s", old)
  }

  if old := s.parentScope.Get(assignment.Name); old != nil && !s.preventInheriting[assignment.Name] {
   return fmt.Errorf("variable already set in inherited scope, previous assignment: %s", old)
  }

  if newValue, err := assignment.Value.Eval(s); err != nil {
   return err
  } else {
   assignment.Value = newValue
  }
  s.vars[assignment.Name] = assignment
 default:
  return fmt.Errorf("Unknown assigner '%s'", assignment.Assigner)
 }
 return nil
}

func (s *Scope) Get(name string) *Assignment {
 if s == nil {
  return nil
 }
 if a, ok := s.vars[name]; ok {
  return a
 }
 if s.preventInheriting[name] {
  return nil
 }
 return s.parentScope.Get(name)
}

func (s *Scope) GetLocal(name string) *Assignment {
 if s == nil {
  return nil
 }
 if a, ok := s.vars[name]; ok {
  return a
 }
 return nil
}

// DontInherit prevents this scope from inheriting the given variable from its
// parent scope.
func (s *Scope) DontInherit(name string) {
 s.preventInheriting[name] = true
}

func (s *Scope) String() string {
 var sb strings.Builder
 s.stringInner(&sb)
 return sb.String()
}

func (s *Scope) stringInner(sb *strings.Builder) {
 if s == nil {
  return
 }
 vars := make([]string, 0, len(s.vars))
 for k := range s.vars {
  vars = append(vars, k)
 }

 sort.Strings(vars)

 for _, v := range vars {
  sb.WriteString(s.vars[v].String())
  sb.WriteRune('\n')
 }

 s.parentScope.stringInner(sb)
}