/* NSC -- new Scala compiler
 * Copyright 2005-2012 LAMP/EPFL
 * @author  Martin Odersky
 */

package dotty.tools.dotc
package core

import Symbols._
import Types.{TermRef, NoPrefix}
import Flags.Implicit
import Names._
import Periods._
import Decorators._
import Contexts._
import Denotations._
import SymDenotations._
import printing.Texts._
import printing.Printer
import util.common._
import util.DotClass
import SymDenotations.NoDenotation
import collection.mutable

object Scopes {

  /** Maximal fill factor of hash table */
  private final val FillFactor = 2.0/3.0

  /** A hashtable is created once current size exceeds MinHash * FillFactor
   *  The initial hash table has twice that size (i.e 16).
   *  This value must be a power of two, so that the index of an element can
   *  be computed as element.hashCode & (hashTable.length - 1)
   */
  final val MinHashedScopeSize = 8

  /** The maximal permissible number of recursions when creating
   *  a hashtable
   */
  private final val MaxRecursions = 1000

  class ScopeEntry private[Scopes] (val name: Name, _sym: Symbol, val owner: Scope) {

    var sym: Symbol = _sym

    /** the next entry in the hash bucket
     */
    var tail: ScopeEntry = null

    /** the preceding entry in this scope
     */
    var prev: ScopeEntry = null

    override def toString: String = sym.toString
  }

  /** A scope contains a set of symbols. It can be an extension
   *  of some outer scope, from which it inherits all symbols.
   *  This class does not have any methods to add symbols to a scope
   *  or to delete them. These methods are provided by subclass
   *  MutableScope.
   */
  abstract class Scope extends DotClass with printing.Showable {

    /** The last scope-entry from which all others are reachable via `prev` */
    private[dotc] def lastEntry: ScopeEntry

    /** The number of symbols in this scope (including inherited ones
     *  from outer scopes).
     */
    def size: Int

    /** The number of outer scopes from which symbols are inherited */
    def nestingLevel: Int

    /** The symbols in this scope in the order they were entered;
     *  inherited from outer ones first.
     */
    def toList(implicit ctx: Context): List[Symbol]

    /** Return all symbols as an iterator in the order they were entered in this scope.
     */
    def iterator(implicit ctx: Context): Iterator[Symbol] = toList.iterator

    /** Is the scope empty? */
    def isEmpty: Boolean = lastEntry eq null

    def foreach[U](p: Symbol => U)(implicit ctx: Context): Unit = toList foreach p

    def filter(p: Symbol => Boolean)(implicit ctx: Context): List[Symbol] = {
      ensureComplete()
      var syms: List[Symbol] = Nil
      var e = lastEntry
      while ((e ne null) && e.owner == this) {
        val sym = e.sym
        if (p(sym)) syms = sym :: syms
        e = e.prev
      }
      syms
    }

    def find(p: Symbol => Boolean)(implicit ctx: Context): Symbol = filter(p) match {
      case sym :: _ => sym
      case _ => NoSymbol
    }

    /** Returns a new mutable scope with the same content as this one. */
    def cloneScope(implicit ctx: Context): MutableScope

    /** Lookup a symbol entry matching given name. */
    def lookupEntry(name: Name)(implicit ctx: Context): ScopeEntry

    /** Lookup next entry with same name as this one */
    def lookupNextEntry(entry: ScopeEntry)(implicit ctx: Context): ScopeEntry

    /** Lookup a symbol */
    final def lookup(name: Name)(implicit ctx: Context): Symbol = {
      val e = lookupEntry(name)
      if (e eq null) NoSymbol else e.sym
    }

    /** Returns an iterator yielding every symbol with given name in this scope.
     */
    final def lookupAll(name: Name)(implicit ctx: Context): Iterator[Symbol] = new Iterator[Symbol] {
      var e = lookupEntry(name)
      def hasNext: Boolean = e ne null
      def next(): Symbol = { val r = e.sym; e = lookupNextEntry(e); r }
    }

    /** The denotation set of all the symbols with given name in this scope
     *  Symbols occur in the result in reverse order relative to their occurrence
     *  in `this.toList`.
     */
    final def denotsNamed(name: Name, select: SymDenotation => Boolean = selectAll)(implicit ctx: Context): PreDenotation = {
      var syms: PreDenotation = NoDenotation
      var e = lookupEntry(name)
      while (e != null) {
        val d = e.sym.denot
        if (select(d)) syms = syms union d
        e = lookupNextEntry(e)
      }
      syms
    }

    /** The scope that keeps only those symbols from this scope that match the
     *  given predicates. If all symbols match, returns the scope itself, otherwise
     *  a copy with the matching symbols.
     */
    final def filteredScope(p: Symbol => Boolean)(implicit ctx: Context): Scope = {
      var result: MutableScope = null
      for (sym <- iterator)
        if (!p(sym)) {
          if (result == null) result = cloneScope
          result.unlink(sym)
        }
      if (result == null) this else result
    }

    def implicitDecls(implicit ctx: Context): List[TermRef] = Nil

    def openForMutations: MutableScope = unsupported("openForMutations")

    final def toText(printer: Printer): Text = printer.toText(this)

    def checkConsistent()(implicit ctx: Context) = ()

    /** Ensure that all elements of this scope have been entered.
     *  Overridden by SymbolLoaders.PackageLoader#PackageScope, where it
     *  makes sure that all names with `$`'s have been added.
     */
    protected def ensureComplete()(implicit ctx: Context): Unit = ()
  }

  /** A subclass of Scope that defines methods for entering and
   *  unlinking entries.
   *  Note: constructor is protected to force everyone to use the factory methods newScope or newNestedScope instead.
   *  This is necessary because when run from reflection every scope needs to have a
   *  SynchronizedScope as mixin.
   */
  class MutableScope protected[Scopes](initElems: ScopeEntry, initSize: Int, val nestingLevel: Int = 0)
      extends Scope {

    /** Scope shares elements with `base` */
    protected[Scopes] def this(base: Scope)(implicit ctx: Context) = {
      this(base.lastEntry, base.size, base.nestingLevel + 1)
      ensureCapacity(MinHashedScopeSize)(ctx) // WTH? it seems the implicit is not in scope for a secondary constructor call.
    }

    def this() = this(null, 0, 0)

    private[dotc] var lastEntry: ScopeEntry = initElems

    /** The size of the scope */
    private[this] var _size = initSize

    override final def size = _size
    private def size_= (x: Int) = _size = x

    /** the hash table
     */
    private var hashTable: Array[ScopeEntry] = null

    /** a cache for all elements, to be used by symbol iterator.
     */
    private var elemsCache: List[Symbol] = null

    protected def newScopeLikeThis() = new MutableScope()

    /** Clone scope, taking care not to force the denotations of any symbols in the scope.
     */
    def cloneScope(implicit ctx: Context): MutableScope = {
      val entries = new mutable.ArrayBuffer[ScopeEntry]
      var e = lastEntry
      while ((e ne null) && e.owner == this) {
        entries += e
        e = e.prev
      }
      val scope = newScopeLikeThis()
      for (i <- entries.length - 1 to 0 by -1) {
        val e = entries(i)
        scope.newScopeEntry(e.name, e.sym)
      }
      scope
    }

    /** create and enter a scope entry with given name and symbol */
    protected def newScopeEntry(name: Name, sym: Symbol)(implicit ctx: Context): ScopeEntry = {
      ensureCapacity(if (hashTable ne null) hashTable.length else MinHashedScopeSize)
      val e = new ScopeEntry(name, sym, this)
      e.prev = lastEntry
      lastEntry = e
      if (hashTable ne null) enterInHash(e)
      size += 1
      elemsCache = null
      e
    }

    /** create and enter a scope entry */
    protected def newScopeEntry(sym: Symbol)(implicit ctx: Context): ScopeEntry =
      newScopeEntry(sym.name, sym)

    private def enterInHash(e: ScopeEntry)(implicit ctx: Context): Unit = {
      val idx = e.name.hashCode & (hashTable.length - 1)
      e.tail = hashTable(idx)
      assert(e.tail != e)
      hashTable(idx) = e
    }

    /** enter a symbol in this scope. */
    final def enter[T <: Symbol](sym: T)(implicit ctx: Context): T = {
      if (sym.isType && ctx.phaseId <= ctx.typerPhase.id) {
        assert(lookup(sym.name) == NoSymbol,
          s"duplicate ${sym.debugString}; previous was ${lookup(sym.name).debugString}") // !!! DEBUG
      }
      newScopeEntry(sym)
      sym
    }

    /** enter a symbol, asserting that no symbol with same name exists in scope */
    final def enterUnique(sym: Symbol)(implicit ctx: Context): Unit = {
      assert(lookup(sym.name) == NoSymbol, (sym.showLocated, lookup(sym.name).showLocated))
      enter(sym)
    }

    private def ensureCapacity(tableSize: Int)(implicit ctx: Context): Unit =
      if (size >= tableSize * FillFactor) createHash(tableSize * 2)

    private def createHash(tableSize: Int)(implicit ctx: Context): Unit =
      if (size > tableSize * FillFactor) createHash(tableSize * 2)
      else {
        hashTable = new Array[ScopeEntry](tableSize)
        enterAllInHash(lastEntry)
        // checkConsistent() // DEBUG
      }

    private def enterAllInHash(e: ScopeEntry, n: Int = 0)(implicit ctx: Context): Unit = {
      if (e ne null) {
        if (n < MaxRecursions) {
          enterAllInHash(e.prev, n + 1)
          enterInHash(e)
        } else {
          var entries: List[ScopeEntry] = List()
          var ee = e
          while (ee ne null) {
            entries = ee :: entries
            ee = ee.prev
          }
          entries foreach enterInHash
        }
      }
    }

    /** Remove entry from this scope (which is required to be present) */
    final def unlink(e: ScopeEntry)(implicit ctx: Context): Unit = {
      if (lastEntry == e) {
        lastEntry = e.prev
      } else {
        var e1 = lastEntry
        while (e1.prev != e) e1 = e1.prev
        e1.prev = e.prev
      }
      if (hashTable ne null) {
        val index = e.name.hashCode & (hashTable.length - 1)
        var e1 = hashTable(index)
        if (e1 == e)
          hashTable(index) = e.tail
        else {
          while (e1.tail != e) e1 = e1.tail
          e1.tail = e.tail
        }
      }
      elemsCache = null
      size -= 1
    }

    /** remove symbol from this scope if it is present */
    final def unlink(sym: Symbol)(implicit ctx: Context): Unit = {
      var e = lookupEntry(sym.name)
      while (e ne null) {
        if (e.sym == sym) unlink(e)
        e = lookupNextEntry(e)
      }
    }

    /** Replace symbol `prev` (if it exists in current scope) by symbol `replacement`.
     *  @pre `prev` and `replacement` have the same name.
     */
    final def replace(prev: Symbol, replacement: Symbol)(implicit ctx: Context): Unit = {
      require(prev.name == replacement.name)
      var e = lookupEntry(prev.name)
      while (e ne null) {
        if (e.sym == prev) e.sym = replacement
        e = lookupNextEntry(e)
      }
      elemsCache = null
    }

    /** Lookup a symbol entry matching given name.
     */
    override def lookupEntry(name: Name)(implicit ctx: Context): ScopeEntry = {
      var e: ScopeEntry = null
      if (hashTable ne null) {
        e = hashTable(name.hashCode & (hashTable.length - 1))
        while ((e ne null) && e.name != name) {
          e = e.tail
        }
      } else {
        e = lastEntry
        while ((e ne null) && e.name != name) {
          e = e.prev
        }
      }
      e
    }

    /** lookup next entry with same name as this one */
    override final def lookupNextEntry(entry: ScopeEntry)(implicit ctx: Context): ScopeEntry = {
      var e = entry
      if (hashTable ne null)
        do { e = e.tail } while ((e ne null) && e.name != entry.name)
      else
        do { e = e.prev } while ((e ne null) && e.name != entry.name)
      e
    }

    /** Returns all symbols as a list in the order they were entered in this scope.
     *  Does _not_ include the elements of inherited scopes.
     */
    override final def toList(implicit ctx: Context): List[Symbol] = {
      if (elemsCache eq null) {
        ensureComplete()
        elemsCache = Nil
        var e = lastEntry
        while ((e ne null) && e.owner == this) {
          elemsCache = e.sym :: elemsCache
          e = e.prev
        }
      }
      elemsCache
    }

    override def implicitDecls(implicit ctx: Context): List[TermRef] = {
      ensureComplete()
      var irefs = new mutable.ListBuffer[TermRef]
      var e = lastEntry
      while (e ne null) {
        if (e.sym is Implicit) {
          val d = e.sym.denot
          irefs += TermRef.withSigAndDenot(NoPrefix, d.name.asTermName, d.signature, d)
        }
        e = e.prev
      }
      irefs.toList
    }

    /** Vanilla scope - symbols are stored in declaration order.
     */
    final def sorted(implicit ctx: Context): List[Symbol] = toList

    override def openForMutations: MutableScope = this

    /** Check that all symbols in this scope are in their correct hashtable buckets. */
    override def checkConsistent()(implicit ctx: Context) = {
      ensureComplete()
      var e = lastEntry
      while (e != null) {
        var e1 = lookupEntry(e.name)
        while (e1 != e && e1 != null) e1 = lookupNextEntry(e1)
        assert(e1 == e, s"PANIC: Entry ${e.name} is badly linked")
        e = e.prev
      }
    }
  }

  /** Create a new scope */
  def newScope: MutableScope = new MutableScope()

  /** Create a new scope nested in another one with which it shares its elements */
  def newNestedScope(outer: Scope)(implicit ctx: Context): MutableScope = new MutableScope(outer)

  /** Create a new scope with given initial elements */
  def newScopeWith(elems: Symbol*)(implicit ctx: Context): MutableScope = {
    val scope = newScope
    elems foreach scope.enter
    scope
  }

  /** Transform scope of members of `owner` using operation `op`
   *  This is overridden by the reflective compiler to avoid creating new scopes for packages
   */
  def scopeTransform(owner: Symbol)(op: => MutableScope): MutableScope = op

  val selectAll: SymDenotation => Boolean = alwaysTrue
  val selectPrivate: SymDenotation => Boolean    = d => (d.flagsUNSAFE is Flags.Private)
  val selectNonPrivate: SymDenotation => Boolean = d => !(d.flagsUNSAFE is Flags.Private)

  /** The empty scope (immutable).
   */
  object EmptyScope extends Scope {
    override private[dotc] def lastEntry = null
    override def size = 0
    override def nestingLevel = 0
    override def toList(implicit ctx: Context) = Nil
    override def cloneScope(implicit ctx: Context): MutableScope = unsupported("cloneScope")
    override def lookupEntry(name: Name)(implicit ctx: Context): ScopeEntry = null
    override def lookupNextEntry(entry: ScopeEntry)(implicit ctx: Context): ScopeEntry = null
  }

  /** A class for error scopes (mutable)
   */
  class ErrorScope(owner: Symbol) extends MutableScope
}