require:
   "./location" ->
      [<<:] as transferLocation, Source
   "./util" as util ->
      classify
      GenSym, gensym
      camelCase
      invCamelCase
   "./lex" ->
      tokenize
   "./parse" ->
      parse


a <<: b =
   transferLocation{a, b}
   match a:
      Error? -> a
      when b.name -> a &: {name = b.name}
      else -> a


provide:
   Env
   Scope
   Info
   track_location
   Expander
   GenSym, gensym
   topscope
   jsKeywords

jsKeywords = "abstract arguments boolean break byte
              case catch char class const
              continue debugger default delete do
              double else enum eval export
              extends false final finally float
              for function goto if implements
              import in instanceof int interface
              let long native new null
              package private protected public return
              short static super switch synchronized
              this throw throws transient true
              try typeof var void volatile
              while with yield".split{R"[ \n]+"}




class Scope:

   constructor{@parent = null
               @name = gensym{"scope"}
               @top = false} =
      @options = {=}

   fork{} =
      Scope{@}

   toString{} =
      "Scope{" + @name + "}"


class Env:

   constructor{} =
      @scopes = {=}
      @options = {=}

   list_bindings{origin} =
      values = {=}
      var scope = origin
      while scope:
         values &: @scopes[scope.name]
         scope = scope.parent
      values


   getopt{scope, name, level = 0} =
      if [scope === null]:
         return undefined
      scope_data = @options[scope.name]
      if [scope_data and Object.prototype.hasOwnProperty.call{scope_data, name}]:
         if level == 0:
            scope_data[name]
         else:
            @getopt{scope.parent, name, level - 1}
      else:
         @getopt{scope.parent, name, level}

   setopt{scope, name, value} =
      if [not @options[scope.name]]:
         @options[scope.name] = {=}
      s = @options[scope.name]
      s[name] and s[camelCase{name}] and s[invCamelCase{name}] = value


   resolve{scope, name, level = 0} =
      if [scope === null]:
         return undefined
      scope_data = @scopes[scope.name]
      if [scope_data and Object.prototype.hasOwnProperty.call{scope_data, name}]:
         if level == 0:
            scope_data[name]
         else:
            @resolve{scope.parent, name, level - 1}
      else:
         @resolve{scope.parent, name, level}

   bind{scope, name, value} =
      if [not @scopes[scope.name]]:
         @scopes[scope.name] = {=}
      if scope.top:
         value.top = true
      s = @scopes[scope.name]
      s[name] and s[camelCase{name}] and s[invCamelCase{name}] = value

   mark{expr} =
      match expr:
         {env => e} ->
            expr
         #symbol or #value or #variable or #macro or #void ->
            expr &: {env = [@]}
         {type, *args} ->
            args each arg -> @mark{arg}
            expr &: {env = [@]}
         other ->
            other

         ;; Scope? s ->
         ;;    s
         ;; other ->
         ;;    print expr
         ;;    throw E.syntax.illegal_node{"Illegal node", {node = expr}}
         ;; other ->
         ;;    print expr
         ;;    expr &: {env = [@]}

   fork{} =
      e = Env{}
      items{@scopes} each {scope, bindings} ->
         items{bindings} each {k, v} ->
            if [not e.scopes[scope]]:
               e.scopes[scope] = {=}
            e.scopes[scope][k] = v
      items{@options} each {scope, bindings} ->
         items{bindings} each {k, v} ->
            if [not e.options[scope]]:
               e.options[scope] = {=}
            e.options[scope][k] = v
      e

   toString{} =
      "Env{...}"


track_location{f} = 
   f2{context, scope, expr} =
      rval = f{context, scope, expr} !!
         e ->
            e <<: expr
            throw e
      match rval:
         #bounce{v} ->
            f2{context, scope, v <<: expr}
         other ->
            other <<: expr
   f2


class Info:

   constructor{@context, @scope, @form, @arg, @expander} =
      @env = @form.env

   gettext{match} =
      {=> location} -> location.text{}
      else -> null

   raw{x} = @gettext{x}

   with_scope{newscope} =
      Info{@context, newscope, @form, @arg, @expander}

   gensym{name} =
      @expander.gensym{name or ""}

   defer{} =
      #nostep{@form}

   mkenv{} =
      @expander.mkenv{}

   mark{*match} =
      {x} -> @env.mark{x}
      xs -> xs each x -> @env.mark{x}

   step{context, expr} =
      @expander.step{context, @scope, expr}

   step_all{context, exprs} =
      @expander.step_all{context, @scope, exprs}

   expand{context, expr} =
      @expander.expand{context, @scope, expr}

   go{x, start, end} =
      @expander.pipeline.go{x, start, end}

   getopt{name} =
      @env.getopt{@scope, name}

   setopt{name, value} =
      @env.setopt{@scope, name, value}



class Expander:

   constructor{@stdenv, @generic_nodes, @pipeline} =
      ;; @pipeline.expand = [@]
      ;; @gensym = gensym
      ;; @gensym = GenSym{"$"}

      @nameusage = [object with jsKeywords each kw -> {kw, 0}]

   gensym{match name} =
      undefined? or null? ->
         @gensym{""}
      when Object.prototype.hasOwnProperty.call{@nameusage, name} ->
         idx = [@nameusage[name] += 1]
         name + "$" + String{idx}
      else ->
         @nameusage[name] = 0
         name + "$0"

   mkenv{} =
      e = Env{}
      e.scopes[.top] = @stdenv.scopes[.top]
      e

   run_macro{m, context, scope, form, arg} =
      info = Info{context, scope, form, arg, @}
      rval = m{context, info, form, arg} !!
         E.match? {args => {{=> value}}} ->
            #send{#symbol{name}, _} or name is "<unknown>" = form
            e = match value:
               === context ->
                  E.syntax.context{msg, {context = context, form = form}} where
                     msg = 'The macro cannot be found in context \{{context}\}.'
               other ->
                  find{match arg} =
                     === value ->
                        E.syntax.argument{msg, {context = context
                                                argument = arg
                                                form = form}} where
                           msg = 'The macro `{name}` expected something different. You should bug the macro/language implementer to improve their error messages.'
                     {type, *xs} ->
                        xs each find! x ->
                           if x: return x
                        false
                     other ->
                        false
                  err = find{arg}
                  if err:
                     then: err
                     else: E.syntax.failure{msg, {form = form, value = value}} where
                        msg = 'An error occurred in the `{name}` macro. You should bug the macro/language implementer to fix this.'
            ;; e <<: form
            throw e
         e ->
            throw e

      try:
         @mkenv{}.mark{rval}
      catch e:
         print rval
         throw E.syntax.macro{"Macro returned a bad node", {form = form}}


   ;; Perform one step of expansion.
   
   ;; Essentially, if the given expression is a macro call, it will be
   ;; expanded. If it is a plain macro, it will also be expanded, with
   ;; #void{} as its argument. Nothing else is expanded, and step does
   ;; not keep going recursively.
   
   ;; step is appropriate for use in macros that process specific node
   ;; types. For instance, pattern matching recognizes the #check{...}
   ;; node. expand will refuse that node, because it doesn't recognize
   ;; it, but step will let macros produce #check nodes and will leave
   ;; them untouched, so that the pattern matching macro can do something
   ;; with it and produce legal nodes.
   
   ;; context: the context in which the expression is evaluated (#expr,
   ;; #pattern, #blocktest, etc.)
   
   ;; scope: the scope in which we are located
   
   ;; expr: the expression to expand (one step)

   step{context, scope, expr} =
      track_location! helper{context, scope, match expr} =
         #symbol{s} ->
            env = match expr:
               {=> env} -> expr.env
               other -> throw E.syntax.no_env with
                  "No environment was found to resolve '" + s + "'"
                  {symbol = expr}
            match env.resolve{scope, s, expr.level or 0}:
               #macro{m} ->
                  match context:
                     #expr{.head} ->
                        #macro{m}
                     other ->
                        #bounce with @run_macro{m, context, scope, expr, #void{} <<: expr}
               other ->
                  expr
   
         #macro{m} ->
            match context:
               #expr{.head} ->
                  expr
               other ->
                  #bounce with @run_macro{m, context, scope, expr, #void{} <<: expr}
   
         #send{f, arg} ->
            match helper{#expr{.head}, scope, f}:
               #macro{m} ->
                  #bounce with @run_macro{m, context, scope, expr, arg}
               other ->
                  expr

         #parse{code, url = null} ->
            t = tokenize{Source{code, url}}
            p = parse{t}
            #bounce with helper{context, scope, expr.env.mark{p}}

         #nostep{x} ->
            x
   
         other ->
            expr
      
      helper{context, scope, expr}

   
   ;; Equivalent of step for a list of expressions. It recognizes
   ;; additional instructions:
   
   ;; #splice{...} -> splice expressions into the stream, expand them
   
   ;; #float{expr} -> float the expression to the top. If multiple floats
   ;;    are found, the first occurrences will be higher
   
   ;; #sink{expr} -> sinks the expression to the bottom. If multiple sinks
   ;;    are found, the first occurrences will be higher up
   
   ;; #restmacro{m} -> m is a macro that should take the remaining
   ;;    expressions in the list (those that come after itself), and
   ;;    return a new list of expressions.
   
   step_all{context, scope, {*[var stmts]}} =
      var pre = {}
      var bulk = {}
      var post = {}
      while stmts.length:
         current = stmts.shift{}
         match @step{context, scope, current}:
            #splice{*prepend} ->
               set-var stmts = prepend ++ stmts
            #float{stmt} ->
               pre ++= @step_all{context, scope, {stmt}}
            #sink{stmt} ->
               post ++= @step_all{context, scope, {stmt}}
            #restmacro{m} ->
               ;; We have to mark each resulting statement in case
               ;; it contains generated code.
               e = @mkenv{}
               set-var stmts = m{stmts} each
                  stmt -> e.mark{stmt}
            x ->
               bulk.push with x
      [pre ++ bulk] ++ post


   ;; Compute the full expansion of the provided expression. expand
   ;; is, more or less, the handler for the #expr context.

   expand{context, scope, expr} =
      track_location! helper{context, scope, var expr} =
         set-var expr = @step{context, scope, expr}
   
         match expr:
   
            #symbol{s} ->
               {=> env} = expr
               match env.resolve{scope, s, expr.level or 0}:
                  undefined? ->
                     throw E.syntax.undeclared{"Undeclared variable: " + s, {node = expr}}
                     ;; #variable{"UNDECLARED__" + s}
                  resolved ->
                     #bounce{v} where
                        v = clone{resolved} &: {
                           location = expr.location
                           top = resolved.top
                           origin = resolved
                        }
   
            #value{_} ->
               expr
   
            #variable{_} ->
               expr
   
            #void{} ->
               expr
   
            #send{f, arg} ->
               #send with 
                  helper{#expr{.head}, scope, f}
                  helper{#expr{.tail}, scope, arg}
   
            #array{*args} ->
               newargs = @step_all{#expr{.array}, scope, args} each arg ->
                  helper{#expr{.expr}, scope, arg}
               #array{*newargs}

            #object{*args} ->
               newargs = @step_all{#expr{.object}, scope, args} each #array{k, v} ->
                  #array{helper{#expr{.expr}, scope, k}
                         helper{#expr{.expr}, scope, v}}
               #object{*newargs}

            #bind{variable and #symbol{s}, value, body} ->
               newscope = Scope{scope}
               {=> env} = variable
               env.bind{newscope, s, value}
               helper{context, newscope, body}
   
            #splice{*args} ->
               #bounce with
                  #multi{*args} &: {override_scope = true}
   
            #interactive{*args} ->
               #bounce with
                  #multi{*args} &: {override_scope = true, all_mutable = true}

            #multi{*args} ->
               newscope = if{expr.override_scope, scope, Scope{scope}}
               stepscope =
                  if{expr.nonrecursive, scope, newscope}
               var changes = false
               {=> newargs, => vars} = classify{.newargs, .vars} with
                  @step_all{#expr{.multi}, stepscope, args} each
                     #option{opt, value} ->
                        {=> env} = expr
                        env.setopt{newscope, opt, value}
                        set-var changes = true
                        #ignore
                     #declare_raw{variable and #symbol{s}, value} ->
                        {=> env} = variable
                        env.bind{newscope, s} with value
                        set-var changes = true
                        #ignore
                     #declare{variable and #symbol{s}, value = null} ->
                        {=> env} = variable
                        if variable.use_previous and
                           \ env.resolve{newscope, s, variable.level or 0}:
                           then:
                              #splice{}
                           else:
                              v = #variable{@gensym{s}} <<: variable
                              ;; v = #variable{s} <<: variable
                              v &: {mutable = expr.all_mutable or variable.mutable}
                              v &: {top = variable.top}
                              env.bind{newscope, s} with v
                              set-var changes = true
                              if value:
                                 then:
                                    #splice with
                                       #newargs{#assign{v, value}}
                                       #vars{v}
                                 else:
                                    #vars{v}
                     #declare{v and #variable{_}, value = null} ->
                        set-var changes = true
                        if value:
                           then:
                              #splice with
                                 #newargs{#assign{v, value}}
                                 #vars{v}
                           else:
                              #vars{v}
                     #undeclare{#symbol{s} and variable} ->
                        {=> env} = variable
                        env.bind{newscope, s} with undefined
                        set-var changes = true
                        #ignore
                     other ->
                        #newargs{other}
               exp{s} =
                  ;; enumerate{newargs} each {i, arg} ->
                  ;;    helper{#expr{...}, s, arg} with
                  ;;       if{i === newargs.length - 1, .expr, .ignore}
                  stepped = enumerate{newargs} each {i, arg} ->
                     @step{#expr{e}, s, arg} where e =
                        if{i === [newargs.length - 1], .expr, .ignore}
                  stepped each arg -> helper{#expr{.expr}, s, arg}
               if changes:
                  then: #scope{vars, #multi{*exp{newscope}}}
                  else: #multi{*exp{scope}}
   

            #data{*args} ->
               var obj = #object{}
               var arr = #array{}
               arr_parts = {}
               obj_parts = {}
               var index = 0
               var objindex = null

               new_arr_part{} =
                  match arr:
                     #array{} -> false
                     other ->
                        arr_parts.push{arr}
                        set-var arr = #array{}
   
               decl_obj{} =
                  match objindex:
                     when index == null ->
                        throw E.syntax.illegal_object{msg, {node = expr}} where
                           msg = "Object fields cannot be declared after *rest arguments."
                     == null ->
                        objindex = index
                     == index ->
                        pass
                     else ->
                        throw E.syntax.illegal_object{msg, {node = expr}} where
                           msg = "Cannot declare object fields at multiple indexes."

               new_obj_part{} =
                  match obj:
                     #object{} -> false
                     other ->
                        obj_parts.push{obj}
                        set-var obj = #object{}

               @step_all{#expr{.data}, scope, args} each
                  #assoc{} ->
                     decl_obj{}
                  #assoc{k, v} ->
                     decl_obj{}
                     obj.push with #array{k, v}
                  #dynsplice{expr} ->
                     index = null
                     new_arr_part{}
                     arr_parts.push{expr}
                  #objsplice{expr} ->
                     decl_obj{}
                     new_obj_part{}
                     obj_parts.push{expr}
                  other ->
                     if index != null: index += 1
                     arr.push{other}
   
               new_arr_part{}
               is_obj = objindex != null
               if is_obj and arr_parts != {}:
                  obj.push with #array{#value{"::objinsert"}, #value{objindex}}
               new_obj_part{}

               obj =
                  util.construct{obj_parts, f, #object{}} where
                     f{x, rest} = `[^x &: ^rest]`
               arr =
                  util.construct{arr_parts.reverse{}, f, #array{}} where
                     f{x, rest} = `[^rest].concat{^x}`

               r = match arr_parts:
                  {} when is_obj ->
                     obj
                  when is_obj ->
                     `[^arr &: ^obj]`
                  other ->
                     arr

               helper{context, scope, @mkenv{}.mark{r}}
   
            #assign{target, value} ->
               t = helper{#expr{.expr}, scope, target}
               orig = t.origin or {=}
               match t:
                  #variable when [not t.mutable
                                  \ and orig.assigned
                                  \ and orig.assigned.group_id !== target.group_id] ->
                     throw E.syntax{msg, {variable = target, loc = t.assigned}} where
                        msg = {"Variable was declared as read-only. Declare it as"
                               "mutable at the origin with `var` (if you have access"
                               "to the declaration) or declare a new variable with"
                               "`let` or `var` or remove the original binding with"
                               "`delete`"}.join{" "}
                  ;; #variable when [not t.mutable and t.assigned] ->
                  ;;    console.log with {target, t.assigned.group_id}
                  #macro{m} ->
                     #bounce with m{#assign{}, scope, expr, value}
                     ;; throw E.syntax{msg, {variable = target}} where
                     ;;    msg = {"This variable is a macro and cannot be assigned to."
                     ;;           "Use `let` to redeclare it or `delete` to undeclare it"}.join{" "}
                  otherwise ->
                     orig.assigned = target

               #assign{t} with
                  helper{#expr{.expr}, scope, value}
   
            #lambda{bindings, body, generator} ->
               newscope = Scope{scope}
               #lambda with
                  bindings each match binding ->
                     #symbol{b} and {=> env} ->
                        v = #variable{@gensym{b}} <<: binding
                        v &: {
                           mutable = binding.mutable
                           group_id = binding.group_id
                           assigned = v
                        }
                        env.bind{newscope, b, v}
                        v
                     #variable and v ->
                        v
                     other ->
                        throw E.syntax.lambda.binding{"Not a valid binding.", {node = other}}
                  helper{#expr{.expr}, newscope, body}
                  generator
   
            #use{match, x} ->
               String? name ->
                  var s = scope
                  while s:
                     if [s.name.slice{0, name.length + 1} === [name + "/"]]:
                        break
                     else:
                        set-var s = s.parent
                  if s:
                     helper{context, s, x}
                  else:
                     throw E.syntax.noscope{"Could not find a scope tagged: " + name}
               newscope ->
                  helper{context, newscope, x}

            #tagscope{String? tag, body} ->
               helper{context, Scope{scope, @gensym{tag + "/"}}, body}

            #final{x} -> x

            {type, *args} when [@generic_nodes.indexOf{type} !== -1] ->
               {type} ++
                  args each arg ->
                     helper{#expr{.expr}, scope, arg}

            #mismix{ops, *args} ->
               throw E.syntax.mismatch{msg, tokens} where
                  tokens = object with enumerate{ops} each {i, op} ->
                     {"token" + String{i + 1}, op}
                  msg = "These operators or brackets cannot be mixed together."

            #char{c} ->
               throw E.syntax.illegal_character with
                  "An illegal character was found: " + c
                  {node = expr}

            other ->
               throw E.syntax.illegal_node with
                  "An illegal node was found: " + other
                  {node = other, context = context}

      helper{context, scope, expr}



topscope = Scope{null, .top, true}