/*
 * Copyright (c) 2003-2008 The University of Wroclaw.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *    1. Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *    2. Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *    3. The name of the University may not be used to endorse or promote
 *       products derived from this software without specific prior
 *       written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
 * NO EVENT SHALL THE UNIVERSITY BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

using System;
using System.Diagnostics;
using Nemerle.Collections;
using Nemerle.Utility;

using PT = Nemerle.Compiler.Parsetree;
using SCG = System.Collections.Generic;

namespace Nemerle.Compiler
{
  [ManagerAccess]
  public class NamespaceTree
  {
    public variant TypeInfoCache {
      | No
      | Cached { tycon : TypeInfo; }
      | CachedAmbiguous { elems : list [TypeInfo] }
      | NotLoaded { e : ExternalType; }
      | NotLoadedList { elems : list [ExternalType] }        
      | MacroCall { m : IMacro; }
      | NamespaceReference
    }
    
    [System.Runtime.InteropServices.ComVisible(false)]
    [DebuggerDisplay("NamespaceTree.Node: '{GetDisplayName()}'")]
    public class Node {
      public Parent : Node;
      
      [DebuggerBrowsable(DebuggerBrowsableState.Never)]
      [Accessor(PartName)] name : string; // the same as edge from parent to this
      
      public mutable Value : TypeInfoCache;
      
      [DebuggerBrowsable(DebuggerBrowsableState.Never)]
      internal mutable children : Hashtable [string, Node];
      
      [DebuggerBrowsable(DebuggerBrowsableState.Never)]
      public Children : Hashtable [string, Node] { get { children } }
      
      public this (parent : Node, n : string, v : TypeInfoCache) {
        Parent = parent;
        name = n;
        Value = v;
      }

      /// Ensure type information loaded from external assemblies.
      /// Note: Types inforamtion loading in lazy way. You must call EnsureCached() for use it.
      public EnsureCached () : void
      {
        match (Value)
        {
          | NotLoaded (extType) => extType.ConstructTypeInfo (this, true)
          | NotLoadedList (elems) =>
            Value = TypeInfoCache.CachedAmbiguous (elems.Map (
              fun (e) { e.ConstructTypeInfo (this, false); e.tycon }))
          | _ => () 
        }
      }
      
      /// Retrieve a top types defined in the compile project (parsed from source files).
      public GetTopLevelTypeBuilders () : array [TypeBuilder]
      {
        GetTypeBuilders (true)
      }

      /// Retrieve a types defined in the compile project (parsed from source files).
      public GetTypeBuilders () : array [TypeBuilder]
      {
        GetTypeBuilders (false)
      }

      /// Retrieve a types defined in the compile project (parsed from source files).
      public GetTypeBuilders (onlyTopDeclarations : bool) : array [TypeBuilder]
      {
        def scan (node : NamespaceTree.Node, result) : void
        {
          when (node.Children != null)
            foreach (elem in node.Children)
            {
              //def name = elem.Key;
              def node = elem.Value;

              match (node.Value)
              {
                | NamespaceReference            => scan (node, result);
                | Cached (tycon is TypeBuilder) => result.Add (tycon);
                | CachedAmbiguous (elems)       =>
                  foreach (elem is TypeBuilder in elems)
                    result.Add (elem);
                
                | _                             => ()
              }
            }
        }
        
        def result = SCG.List();
        scan (this, result);

        def getNestedTypes(sec : SCG.IEnumerable[TypeBuilder])
        {
          foreach (tb in sec)
          {
            def result2 = tb.DeclaredNestedTypes;
            result.AddRange (result2);
            getNestedTypes (result2);
          }
        }

        unless (onlyTopDeclarations)
          getNestedTypes (result.ToArray());

        result.ToArray ();
      }
      
      [Nemerle.OverrideObjectEquals]
      public Equals (other : Node) : bool {
        if (other == null) false
        else if (this : object == other) true
        else
          if (Parent == null) false
          else
            Parent.Equals (other.Parent) && name == other.name
      }

      /**
       * Check if current node is under namespace given by reverse of [ns]
       */
      public Equals (ns : list [string]) : bool
      {
        | [] => Parent == null
        | x :: xs => name == x && Parent != null && Parent.Equals (xs)
      }
      
      public override GetHashCode () : int {
        def nameHashCode = if (name == null) 0 else name.GetHashCode ();

        if (Parent == null) nameHashCode
        else unchecked ((Parent.GetHashCode ()  * 7) ^ nameHashCode)
      }

      public GetDisplayName () : string
      {
        FullName.ToString(".")
      }

      [DebuggerBrowsable(DebuggerBrowsableState.Never)]
      public FullName : list [string]
      {
        get {
          if (name == null) ["alias"]
          else
            GetNameWithSuffix ([])
        }
      }

      [Obsolete("please use FullName property")]
      public Name : list [string]
      {
        get { FullName }
      }
      
      public GetNameWithSuffix (mutable suffix : list [string]) : list [string]
      {
        mutable node = this;
        while (node.Parent != null) {
          suffix = node.name :: suffix;
          node = node.Parent;
        }
        suffix
      }

      // some namespace nodes are faked for the need of namespace aliases
      public IsFromAlias : bool { get { name == null } }
      
      public Clear () : void
      {
        unless (children == null) children.Clear ();
      }

      /// Walks down the tree begining at current node, spliting given
      /// name to `.' separated parts. The path is created if at some
      /// point it doesn't exist in tree.
      public Path (n : string) : Node {
        mutable cur_node = this;
        mutable last = 0;
        for (mutable i = 0; i < n.Length; ++i) {
          when (n[i] == '.') {
            cur_node = cur_node.Child (n.Substring (last, i - last));
            last = i + 1;
          }
        };
        when (n.Length > 0 && !n.EndsWith ("."))
          cur_node = cur_node.Child (n.Substring (last, n.Length - last));
        cur_node
      }

      public Path (n : list [string]) : Node {
        mutable cur_node = this;
        def loop (l) {
          | x :: xs =>
            cur_node = cur_node.Child (x);
            loop (xs)
          | _ => cur_node
        };
        loop (n)
      }
      
      public TryPath (n : list [string]) : TypeInfoCache {
        def loop (l, cur_node : Node) {
          match (l) {
            | [x] =>
              when (cur_node.children == null)
                cur_node.children = Hashtable (10);
                
              match (cur_node.children.Get (x)) {
                | Some (nd) => nd.Value
                | _ =>
                  match (x [x.Length - 1]) {
                    | '*' | '&' =>
                      def bare_name = x.TrimEnd (array ['*', '&']);
                      def (st, lib) =
                        match (cur_node.children.Get (bare_name)) {
                          | Some (nd) =>
                            match (nd.Value) {
                              | TypeInfoCache.Cached (tc) =>
                                (tc.SystemType, tc.GetLibraryReference ())
                                
                              | TypeInfoCache.NotLoaded (e) =>
                                (e.system_type, e.library)
                                
                              | _ => (null, null)
                            }
                          | _ => (null, null)
                        };
                      if (st != null) {
                        def correct_name = st.TypeFullName () + x.Substring (bare_name.Length);
                        def nst = st.Assembly.GetType (correct_name);
                        //def correct_name = correct_name.Replace ('+', '.');
                        assert (nst != null);

                        //def node = namespace_tree.Path (correct_name);
                        def node = cur_node.Child (x);
                        def res = TypeInfoCache.Cached (lib.ConstructTypeInfo (nst, node));
                        node.Value = res;
                        res
                      }
                      else
                        TypeInfoCache.No ()

                    | _ => TypeInfoCache.No ()
                  }
                }

            | x :: xs =>
              when (cur_node.children == null)
                cur_node.children = Hashtable (10);
                
              match (cur_node.children.Get (x)) {
                | Some (nd) => loop (xs, nd)
                | _ => TypeInfoCache.No ()
              }
            // we are at good namespace, so return our own Value
            | _ => Value
          }
        };
        loop (n, this)
      }

      /// Return Node corresponding with name or null.
      public PassTo (name : list [string]) : Node
      {
        if (Children == null)
          if (name is []) this else null
        else match (name)
        {
          | part :: tail => 
            match (Children.GetValueOrDefault(part, null))
            {
              | null | subNode when subNode.Value is TypeInfoCache.No =>  null
              | subNode => subNode.PassTo(tail)
            }

          | [] => this
        }
      }

      /// Return Node corresponding with name or null.
      public static PassTo (
        nss : list [Node],
        name : list [string]
      ) : Node
      {
        match (nss)
        {
          | ns :: tail =>
            if (ns.Children == null)
              PassTo (tail, name)
            else match (ns.PassTo (name))
            {
              | null   => PassTo (tail, name)
              | result => result
            }

          | [] => null
        }
      }

      internal LoadValue (val : TypeInfoCache.NotLoadedList) : list [TypeInfo]
      {
        def by_parms_amount = Hashtable ();
        def cached = val.elems.FoldLeft ([], fun (e, acc) {
          // eliminate ambiguous types, store only those differing
          // on amount of generic parameters
          def count = e.system_type.GetGenericArguments ().Length;
          if (by_parms_amount.Contains (count)) {
            def used = by_parms_amount [count] : System.Type;
            Message.Warning ($"using type `[$(used.Assembly)]$(used.TypeFullName ())' that"
                             " was defined in more than one assembly: "
                             " `[$(e.system_type.Assembly)]$(e.system_type.TypeFullName ())'"
                             " (the first version was used)");
            acc
          }
          else {
            by_parms_amount.Add (count, e.system_type);

            e.ConstructTypeInfo (this, false);
            e.tycon :: acc
          }
        });
        Value = TypeInfoCache.CachedAmbiguous (cached);
        cached
      }
      
      public LookupType (split : list [string], args_count : int) : option [TypeInfo]
      {
        def search (cached) {
          | (x : TypeInfo) :: xs =>
            if (args_count == -1 || args_count == x.TyparmsCount)
              Some (x)
            else
              search (xs)
            
          | [] => None ()
        }
        
        match (TryPath (split)) {
          | TypeInfoCache.Cached (tc) =>
            // incorrect number of args is reported later in a cleaner way
            Some (tc)
            
          | TypeInfoCache.NotLoaded (e) =>
            e.ConstructTypeInfo (Path (split), true);
           
            // incorrect number of args is reported later in a cleaner way
            Some (e.tycon)

          | TypeInfoCache.NotLoadedList as val =>
            def cached = Path (split).LoadValue (val);
            search (cached)
            
          | CachedAmbiguous (all) => search (all)

          | TypeInfoCache.MacroCall | TypeInfoCache.No
          | TypeInfoCache.NamespaceReference => None ()
        }
      }

      public LookupTypes (split : list [string], for_completion = false) : list [TypeInfo]
      {
        def make_list (val, path) {
          match (val) {
            | TypeInfoCache.Cached (tc) => [tc]
              
            | TypeInfoCache.NotLoaded (e) =>
              def path = if (path == null) Path (split) else path;
              e.ConstructTypeInfo (path, true);
              [e.tycon]

            | TypeInfoCache.NotLoadedList as val =>
              def path = if (path == null) Path (split) else path;
              path.LoadValue (val);
              
            | CachedAmbiguous (all) => all
            | TypeInfoCache.MacroCall | TypeInfoCache.No
            | TypeInfoCache.NamespaceReference => []
          }
        }

        if (for_completion) {
          def (pref, mem_name) = List.DivideLast (split);
          def node = PassTo (pref);
          if (node != null && node.children != null)
            node.children.Fold ([], fun (name, node, acc) {
              if (name.StartsWith (mem_name, System.StringComparison.InvariantCultureIgnoreCase))
                make_list (node.Value, node) + acc
              else acc
            })
          else []
        } else
          make_list (TryPath (split), null)
      }
      
      public LookupSystemType (split : list [string]) : option [System.Type]
      {
        match (TryPath (split)) {
          | TypeInfoCache.Cached (tc) => Some (tc.SystemType)
          | TypeInfoCache.NotLoaded (e) => Some (e.system_type)
          | NotLoadedList (ts) => Some (ts.Head.system_type)
          | CachedAmbiguous (ts) => Some (ts.Head.SystemType)            
          | TypeInfoCache.MacroCall | TypeInfoCache.No
          | TypeInfoCache.NamespaceReference            => None ()
        }
      }

      public LookupValue () : option [TypeInfo]
      {
        LookupType ([], -1)
      }


      public LookupMacro (split : list [string]) : option [IMacro]
      {
        match (TryPath (split)) {
          | TypeInfoCache.MacroCall (m) => Some (m)
          | _ => None ()
        }
      }

      internal AddChild (name : string, node : Node) : void {
        when (children == null) children = Hashtable (16);
        children.Add (name, node);
      }
      
      internal CleanUp () : void
      {
        when (this.FullName is ["alias"]) 
          this.Clear ();
        this.Value = TypeInfoCache.No ();
      }
      
      /// Performs one step down the tree through given edge (name).
      /// String in this edge isn't splited to `.' separated parts.
      /// In case there is no such child in current node, it is created.
      Child (name : string) : Node {
        when (children == null) children = Hashtable (16);
        match (children.Get (name)) {
          | None =>
            def result = Node (this, name, TypeInfoCache.No ());
            children.Add (name, result);
            result

          | Some (r) => r
        }
      }

      public override ToString () : string {
        def s = Text.StringBuilder ("( ");
        when (children != null)
          children.Iter (fun (x, y : Node) {
            ignore (s.Append (x + "-" + y.ToString () + ", "))
          });
        _ = s.Append (")\n");
        s.ToString ();
      }

      // Debuging support.
      #pragma warning disable 10003

      [System.Runtime.InteropServices.ComVisible(false)]
      [DebuggerDisplay("NamespaceTree.Node: '{FullName}'")]
      private class NodeDebugDisplayHelper
      {
        public this (node : NamespaceTree.Node) { _node = node; }

        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        _node : NamespaceTree.Node;

        public FullName : string { get { _node.GetDisplayName () } }

        public Children : array [NamespaceTree.Node]
        {
          get
          {
            if (_node.Children is null)
              array (0)
            else
              _node.Children.Values.ToArray().SortInplace(
                (x, y) => x.PartName.CompareTo(y.PartName)
              )
          }
        }
      }

      [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
      private NodeDebugDisplay : NodeDebugDisplayHelper
      {
        get { NodeDebugDisplayHelper (this) }
      }
      
      #pragma warning restore 10003
    }
    
    internal mutable macro_context : int;
    internal macro_contexts : Hashtable [string, int];
    mutable macro_context_class : TypeBuilder;
    [Accessor]
    internal namespace_tree : Node;
    
    // we store nodes, which were referenced from using / alias to check their existance
    internal referenced_namespace_nodes : SCG.List [list [Node] * Location];

    internal this (man : ManagerClass) {
      macro_contexts = Hashtable (100);
      namespace_tree = Node (null, "", TypeInfoCache.NamespaceReference ());
      referenced_namespace_nodes = SCG.List ();
      Manager = man;
    }

    public Init () : void
    {
      macro_contexts.Clear ();
      macro_context = 0;
      macro_context_class = null;
      referenced_namespace_nodes.Clear ();
    }

    /** Function for adding type to namespace tree.

        It checks if given
        class is already in namespace tree and if it is and has `partial' modifier
        it add members to existing type instead of creating new TypeBuilder.
     */
    [Nemerle.Assertions.Ensures (value != null)]
    internal AddType (par : TypeBuilder, parent_node : Node,
                      newdecl : PT.TopDeclaration) : TypeBuilder
    {
      def pname = newdecl.ParsedName;
      def ns_node = parent_node.Path ([pname.Id]);

      def new_gparms =
        if (newdecl.typarms != null) newdecl.typarms.tyvars.Length else 0;

      def existing =
        match (ns_node.Value) {
          | TypeInfoCache.Cached (existing) => [existing]
          | TypeInfoCache.CachedAmbiguous (many) => many

          | TypeInfoCache.NotLoaded (external) =>
            external.ConstructTypeInfo (ns_node, true);
            [external.tycon]

          | TypeInfoCache.NotLoadedList as val =>
            ns_node.LoadValue (val)

          | TypeInfoCache.MacroCall (m) =>
            Message.Error ($"type declaration `$(pname.Id)' hides macro $(m.GetName ())");
            []
            
          | _ => []
        }

      mutable builder = null;
      
      mutable all = existing.FoldLeft ([], fun (x : TypeInfo, acc) {
        if (x.TyparmsCount == new_gparms)
          match (x) {
            | tb is TypeBuilder =>
              tb.ExtendPartialClass (newdecl);
              builder = tb;
              x :: acc
              
            | _ =>
              Message.Error (newdecl.Location, "redefinition of external type `" +
                             x.FullName + "'");
              Message.Error (x.Location, "first defined here");
              builder = Manager.Hierarchy.CreateTypeBuilder (par, newdecl, ns_node);
              builder :: acc
          }
        else
          x :: acc
      });

      when (builder == null) {
        builder = Manager.Hierarchy.CreateTypeBuilder (par, newdecl, ns_node);
        all ::= builder;
      }

      ns_node.Value = 
        match (all) {
          | [_] => TypeInfoCache.Cached (builder);
          | _ => TypeInfoCache.CachedAmbiguous (all)
        }
      builder
    }

    public AddMacro (split : list[string], m : IMacro) : void {
      AddMacro (namespace_tree.Path (split), m)
    }

    public static AddMacro (ns : Node, m : IMacro) : void {
      match (ns.Value) {
        | TypeInfoCache.No => 
          ns.Value = TypeInfoCache.MacroCall (m)

        | TypeInfoCache.NamespaceReference =>
          Message.Error ("cannot define `" + ns.GetDisplayName () + 
                         "' because the same namespace exists ");
        | _ =>
          Message.Error ("redefinition of `" + ns.GetDisplayName () + "'");
      }
    }
    
    
    internal LookupInternalType (name : list[string]) : TypeInfo {
      match (LookupExactType (name)) {
        | Some (t) => t
        | None => Util.ice ("unbound internal type " + name.ToString("."))
      }
    }

    internal LookupInternalType (name : list[string], args_count : int) : TypeInfo {
      match (LookupExactType (name, args_count)) {
        | Some (t) => t
        | None => Util.ice ("unbound internal type " + name.ToString (".") + "`" + 
                            args_count.ToString ())
      }
    }
    
    public LookupExactType (name : string) : option [TypeInfo] {
      LookupExactType (name, -1)
    }

    public LookupExactType (name : string, args_count : int) : option [TypeInfo] {
      namespace_tree.LookupType (NString.Split (name, '.'), args_count)
    }
    
    public LookupExactType (name : list [string]) : option [TypeInfo] {
      namespace_tree.LookupType (name, -1)
    }

    public LookupExactType (name : list [string], args_count : int) : option [TypeInfo] {
      namespace_tree.LookupType (name, args_count)
    }
    
    public LookupSystemType (name : string) : option [System.Type]
    {
      namespace_tree.LookupSystemType (NString.Split (name, '.'))
    }

    public ExactPath (path : list [string]) : Node
    {
      namespace_tree.Path (path)
    }
    
    public LookupExactMacro (name : list [string]) : option [IMacro]
    {
      namespace_tree.LookupMacro (name)
    }
    
    internal CheckReferencedNamespaces () : void
    {
      foreach ((all_opened, loc) in referenced_namespace_nodes) {
        mutable scream = true;
        foreach (node in all_opened)
          match (node.Value) {
            | TypeInfoCache.No =>
              node.Value = TypeInfoCache.NamespaceReference ();
              
            // we could forbid referencing type-style namespaces here if we want
            | _ => scream = false
          }
        when (scream) {
          Message.Error (loc, "referenced namespace `" 
                         + all_opened.Last.GetDisplayName ()
                         + "' does not exist")
        }
      }
    }
                 
    private LiftMacroContexts () : Parsetree.PExpr
    {
      def ar = array (macro_context);
      macro_contexts.Iter (fun (k, v) {ar[v - 1] = k});
      def make_expr (s) {
        assert (s != null); 
        <[ $(s : string) ]>
      };
      <[ array [..$(List.MapFromArray (ar, make_expr))] ]>
    }

    // macro contexts class is unique for given assembly and encodes
    // GlobalEnvs used in qutations occuring in code
    internal prepare_macro_context_class () : void
    {
      when (macro_context_class == null) {
        macro_context_class = Manager.CoreEnv.Define (<[ decl:
          internal module _N_MacroContexts 
          {
            private serialized : array [string];
            private contexts : array [GlobalEnv];
            private mutable last_manager : ManagerClass;

            internal Get (no : int, from_manager : ManagerClass) : GlobalEnv
            {
              when (from_manager : object != last_manager) {
                Clear ();
                last_manager = from_manager;
              }
              when (contexts[no - 1] == null)
                contexts[no - 1] = GlobalEnv (serialized[no - 1], from_manager);
              contexts[no - 1]
            }

            private Clear () : void
            {
              for (mutable i = 0; i < contexts.Length; ++i)
                contexts [i] = null;
              last_manager = null;
            }
          }
        ]>);
        macro_context_class.MarkWithSpecialName ();      
        macro_context_class.Compile ();
        
        // a little hack to override unassigned field warning
        foreach (f in macro_context_class.GetFields ())
          Manager.MarkAsAssigned (f);
        
        macro_context_class.CannotFinalize = true;
      }
    }

    internal FinishMacroContextClass () : void
    {
      def ty = macro_context_class;
      when (ty != null) {
        Util.locate (ty.Location,
          ty.Define (<[ decl:
            this ()
            {
              _N_MacroContexts.serialized = $(LiftMacroContexts ());
              _N_MacroContexts.contexts = array ($(macro_context : int));
              ManagerClass.OnInit += Clear;
            } 
          ]>));
        ty.CannotFinalize = false;
      }
    }
  }
} // ns