<commit_before>/* NSC -- new Scala compiler
 * Copyright 2005-2006 LAMP/EPFL
 * @author  <NAME>
 */
// $Id$

package scala.tools.nsc.symtab

import scala.collection.mutable.ListBuffer
import scala.tools.nsc.util.{HashSet, Position}
import Flags._

/* A standard type pattern match:
  case ErrorType =>
  case WildcardType =>
  case NoType =>
  case NoPrefix =>
  case ThisType(_) =>
  case SingleType(pre, sym) =>
  case ConstantType(value) =>
  case TypeRef(pre, sym, args) =>
  case TypeBounds(lo, hi) =>
  case RefinedType(parents, defs) =>
  case ClassInfoType(parents, defs, clazz) =>
  case MethodType(paramtypes, result) =>
  case PolyType(tparams, result) =>
  // the last three types are not used after phase `typer'.
  case OverloadedType(pre, tparams, alts) =>
  case AntiPolyType(pre: Type, targs) =>
  case TypeVar(_, _) =>
*/

trait Types requires SymbolTable {
  import definitions._

  //statistics
  var singletonClosureCount = 0
  var compoundClosureCount = 0
  var typerefClosureCount = 0
  var findMemberCount = 0
  var noMemberCount = 0
  var multMemberCount = 0
  var findMemberMillis = 0l
  var subtypeCount = 0
  var subtypeMillis = 0l

  private var explainSwitch = false
  private var checkMalformedSwitch = true

  val emptyTypeArray = new Array[Type](0)

  /** The base class for all types */
  abstract class Type {

    /** Types for which asSeenFrom always is the identity, no matter what
     *  prefix or owner.
     */
    def isTrivial: boolean = false

    /** The symbol associated with the type */
    def symbol: Symbol = NoSymbol

    /** The base type underlying a singleton type,
     *  identity on all other types */
    def singleDeref: Type = this

    /** Widen from singleton type to its underlying non-singleton base type
     *  by applying one or more singleDeref steps,
     *  identity for all other types */
    def widen: Type = this

    /** The type of <code>this</code> of a class type or reference type
     */
    def typeOfThis = symbol.typeOfThis

    /** Map to a this type which is a subtype of this type.
     */
    def narrow: Type =
      if (phase.erasedTypes) this
      else refinedType(List(this), commonOwner(this), EmptyScope).narrow

    /** Map a constant type to its underlying base type,
     *  identity for all other types */
    def deconst: Type = this

    /** For a TypeBounds type, itself;
     *  for a reference denoting an abstract type, its bounds,
     *  for all other types, a TypeBounds type all of whose bounds are this type.
     *  error for all other types */
    def bounds: TypeBounds = TypeBounds(this, this)

    /** For a class or intersection type, its parents.
     *  For a TypeBounds type, the parents of its hi bound.
     *  inherited by typerefs, singleton types, and refinement types,
     *  The empty list for all other types */
    def parents: List[Type] = List()

    /** For a typeref or single-type, its prefix. NoType for all other types. */
    def prefix: Type = NoType

    /** For a typeref, its arguments. The empty list for all other types */
    def typeArgs: List[Type] = List()

    /** For a method or poly type, its direct result type,
     *  the type itself for all other types */
    def resultType: Type = this

    /** For a curried method or poly type its non-method result type,
     *  the type itself for all other types */
    def finalResultType: Type = this

    /** For a method or poly type, the number of its value parameter sections,
     *  0 for all other types */
    def paramSectionCount: int = 0

    /** For a method or poly type, the types of its first value parameter section,
     *  the empty list for all other types */
    def paramTypes: List[Type] = List()

    /** For a poly type, its type parameters,
     *  the empty list for all other types */
    def typeParams: List[Symbol] = List()

    /** Is this type produced as a repair for an error? */
    def isError: boolean = symbol.isError

    /** Is this type produced as a repair for an error? */
    def isErroneous: boolean = {
      ErroneousTraverser.result = false
      ErroneousTraverser.traverse(this)
      ErroneousTraverser.result
    }

    /** Does this type denote a stable reference (i.e. singleton type)? */
    def isStable: boolean = false

    /** Does this type denote a reference type which can be null? */
    // def isNullable: boolean = false

    /** Is this type guaranteed to be non-null? */
    // def isNonNull: boolean = false

    /** For a classtype or refined type, its defined or declared members;
     *  inherited by subtypes and typerefs.
     *  The empty scope for all other types */
    def decls: Scope = EmptyScope

    /** The defined or declared members with name <code>name</code> in this type;
     *  an OverloadedSymbol if several exist, NoSymbol if none exist.
     *  Alternatives of overloaded symbol appear in the order they are declared.
     */
    def decl(name: Name): Symbol = findDecl(name, 0)

    /** The non-private defined or declared members with name `name' in this type;
     *  an OverloadedSymbol if several exist, NoSymbol if none exist.
     *  Alternatives of overloaded symbol appear in the order they are declared.
     */
    def nonPrivateDecl(name: Name): Symbol = findDecl(name, PRIVATE)

    /** A list of all members of this type (defined or inherited)
     *  Members appear in linearization order of their owners.
     *  Members with the same owner appear in reverse order of their declarations.
     */
    def members: List[Symbol] = findMember(nme.ANYNAME, 0, 0, false).alternatives

    /** A list of all non-private members of this type (defined or inherited) */
    def nonPrivateMembers: List[Symbol] =
      findMember(nme.ANYNAME, PRIVATE | BRIDGE, 0, false).alternatives

    /** A list of all implicit symbols of this type  (defined or inherited) */
    def implicitMembers: List[Symbol] =
      findMember(nme.ANYNAME, BRIDGE, IMPLICIT, false).alternatives

    /** The member with given name,
     *  an OverloadedSymbol if several exist, NoSymbol if none exist */
    def member(name: Name): Symbol = findMember(name, BRIDGE, 0, false)

    /** The non-private member with given name,
     *  an OverloadedSymbol if several exist, NoSymbol if none exist */
    def nonPrivateMember(name: Name): Symbol =
      findMember(name, PRIVATE | BRIDGE, 0, false)

    /** The non-local member with given name,
     *  an OverloadedSymbol if several exist, NoSymbol if none exist */
    def nonLocalMember(name: Name): Symbol =
      findMember(name, LOCAL | BRIDGE, 0, false)

    /** The least type instance of given class which is a supertype
     *  of this type */
    def baseType(clazz: Symbol): Type = NoType

    /** This type as seen from prefix <code>pre</code> and class
     *  <code>clazz</code>. This means:
     *  Replace all thistypes of <code>clazz</code> or one of its subclasses
     *  by <code>pre</code> and instantiate all parameters by arguments of
     *  <code>pre</code>.
     *  Proceed analogously for thistypes referring to outer classes.
     */
    def asSeenFrom(pre: Type, clazz: Symbol): Type =
      if (!isTrivial && (!phase.erasedTypes || pre.symbol == ArrayClass)) {
        new AsSeenFromMap(pre, clazz) apply this
      } else this

    /** The info of <code>sym</code>, seen as a member of this type.
     */
    def memberInfo(sym: Symbol): Type =
      sym.info.asSeenFrom(this, sym.owner)

    /** The type of `sym', seen as a member of this type. */
    def memberType(sym: Symbol): Type = {
      sym.tpe match {
        case ov @ OverloadedType(pre, alts) =>
          OverloadedType(this, alts)
/*
          val pre1 = pre match {
            case ClassInfoType(_, _, clazz) => clazz.tpe
            case _ => pre
          }
          if (this =:= pre1) ov
          else if (this =:= pre1.narrow) OverloadedType(this, alts)
          else {
            Console.println("bad memberType of overloaded symbol: "+this+"/"+pre1+"/"+pre1.narrow)
            assert(false)
            ov
          }
*/
        case _ =>
          //System.out.println("" + this + ".memberType(" + sym +":" + sym.tpe +")");//DEBUG
          sym.tpe.asSeenFrom(this, sym.owner)
      }
    }

    /** Substitute types <code>to</code> for occurrences of references to
     *  symbols <code>from</code> in this type.
     */
    def subst(from: List[Symbol], to: List[Type]): Type =
      new SubstTypeMap(from, to) apply this

    /** Substitute symbols <code>to</code> for occurrences of symbols
     *  <code>from</code> in this type.
     */
    def substSym(from: List[Symbol], to: List[Symbol]): Type =
      new SubstSymMap(from, to) apply this

    /** Substitute all occurrences of <code>ThisType(from)</code> in this type
     *  by <code>to</code>.
     */
    def substThis(from: Symbol, to: Type): Type =
      new SubstThisMap(from, to) apply this

    def substSuper(from: Type, to: Type): Type =
      new SubstSuperMap(from, to) apply this

    /** Does this type contain a reference to this symbol? */
    def contains(sym: Symbol): boolean =
      new ContainsTraverser(sym).traverse(this).result

    /** Is this type a subtype of that type? */
    def <:<(that: Type): boolean = {
      if (util.Statistics.enabled) subtypeCount = subtypeCount + 1
      val startTime = if (util.Statistics.enabled) System.currentTimeMillis() else 0l
      val result =
        ((this eq that) ||
         (if (explainSwitch) explain("<", isSubType, this, that)
          else isSubType(this, that)));
      if (util.Statistics.enabled)
        subtypeMillis = subtypeMillis + System.currentTimeMillis() - startTime
      result
    }

    /** Is this type equivalent to that type? */
    def =:=(that: Type): boolean = (
      (this eq that) ||
      (if (explainSwitch) explain("=", isSameType, this, that)
       else isSameType(this, that))
    );

    /** Does this type implement symbol <code>sym</code> with same or stronger type?
     */
    def specializes(sym: Symbol): boolean =
      if (explainSwitch) explain("specializes", specializesSym, this, sym)
      else specializesSym(this, sym)

    /** Is this type close enough to that type so that
     *  members with the two type would override each other?
     *  This means:
     *    - Either both types are polytypes with the same number of
     *      type parameters and their result types match after renaming
     *      corresponding type parameters
     *    - Or both types are method types with equivalent type parameter types
     *      and matching result types
     *    - Or both types are equivalent
     *    - Or phase.erasedTypes is false and both types are neither method nor
     *      poly types.
     */
    def matches(that: Type): boolean = matchesType(this, that)

    /** The shortest sorted upwards closed array of types that contains
     *  this type as first element.
     *
     *  A list or array of types ts is upwards closed if
     *
     *    for all t in ts:
     *      for all typerefs p.s[args] such that t &lt;: p.s[args]
     *      there exists a typeref p'.s[args'] in ts such that
     *      t &lt;: p'.s['args] &lt;: p.s[args],
     *      and
     *      for all singleton types p.s such that t &lt;: p.s
     *      there exists a singleton type p'.s in ts such that
     *      t &lt;: p'.s &lt;: p.s
     *
     *  Sorting is with respect to Symbol.isLess() on type symbols.
     */
    def closure: Array[Type] = Array(this)

    def baseClasses: List[Symbol] = List()

    /**
     *  @param sym the class symbol
     *  @return    the index of given class symbol in the closure of this type,
     *             or -1 if no base type with given class symbol exists.
     */
    def closurePos(sym: Symbol): int = {
      val cl = closure
      var lo = 0
      var hi = cl.length - 1
      while (lo <= hi) {
        val mid = (lo + hi) / 2
        val clsym = cl(mid).symbol
        if (sym == clsym) return mid
        else if (sym isLess clsym) hi = mid - 1
        else if (clsym isLess sym) lo = mid + 1
        else throw new Error()
      }
      -1
    }

    /** If this is a polytype, a copy with cloned type parameters owned
     *  by <code>owner</code>. Identity for all other types.
     */
    def cloneInfo(owner: Symbol) = this

    protected def objectPrefix = "object "
    protected def packagePrefix = "package "

    def trimPrefix(str: String) =
      if (str.startsWith(objectPrefix)) str.substring(objectPrefix.length)
      else if (str.startsWith(packagePrefix)) str.substring(packagePrefix.length)
      else str

    /** The string representation of this type used as a prefix */
    def prefixString = trimPrefix(toString()) + "#"

    /** The string representation of this type, with singletypes explained */
    def toLongString = {
      val str = toString()
      if (str endsWith ".type") str + " (with underlying type " + widen + ")"
      else str
    }

    /** Is this type completed (i.e. not a lazy type)?
     */
    def isComplete: boolean = true

    /** If this is a lazy type, assign a new type to <code>sym</code>. */
    def complete(sym: Symbol): unit = {
      if (sym == NoSymbol || sym.isPackageClass)
        sym.validTo = period(currentRunId, phaseId(sym.validTo))
      else {
        val this1 = adaptToNewRunMap(this)
        if (this1 eq this) sym.validTo = period(currentRunId, phaseId(sym.validTo))
        else {
          //System.out.println("new type of " + sym + "=" + this1 + ", used to be " + this);//DEBUG
          sym.setInfo(this1)
        }
      }
    }

    /** If this is a symbol loader type, load and assign a new type to
     *  <code>sym</code>.
     */
    def load(sym: Symbol): unit = {}

    private def findDecl(name: Name, excludedFlags: int): Symbol = {
      var alts: List[Symbol] = List()
      var sym: Symbol = NoSymbol
      var e: ScopeEntry = decls.lookupEntry(name)
      while (e != null) {
        if (!e.sym.hasFlag(excludedFlags)) {
          if (sym == NoSymbol) sym = e.sym
          else {
            if (alts.isEmpty) alts = List(sym)
            alts = e.sym :: alts
          }
        }
        e = decls.lookupNextEntry(e)
      }
      if (alts.isEmpty) sym
      else baseClasses.head.newOverloaded(this, alts)
    }

    /**
     *  @param name          ...
     *  @param excludedFlags ...
     *  @param requiredFlags ...
     *  @param stableOnly    ...
     *  @return              ...
     */
    //TODO: use narrow only for modules? (correct? efficiency gain?)
    def findMember(name: Name, excludedFlags: int, requiredFlags: long, stableOnly: boolean): Symbol = {
      if (util.Statistics.enabled) findMemberCount = findMemberCount + 1
      val startTime = if (util.Statistics.enabled) System.currentTimeMillis() else 0l

      //System.out.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG
      var members: Scope = null
      var member: Symbol = NoSymbol
      var excluded = excludedFlags | DEFERRED
      var self: Type = null
      var continue = true
      var savedCheckMalformedSwitch = checkMalformedSwitch
      checkMalformedSwitch = false
      while (continue) {
        continue = false
        var bcs = baseClasses
        while (!bcs.isEmpty) {
          val decls = bcs.head.info.decls
          bcs = if (name == nme.CONSTRUCTOR) Nil else bcs.tail
          var entry =
            if (name == nme.ANYNAME) decls.elems else decls lookupEntry name
          while (entry != null) {
            val sym = entry.sym
            if (sym.getFlag(requiredFlags) == requiredFlags) {
              val excl = sym.getFlag(excluded)
              if (excl == 0) {
                if (name.isTypeName || stableOnly) {
                  checkMalformedSwitch = savedCheckMalformedSwitch
                  if (util.Statistics.enabled)
                    findMemberMillis = findMemberMillis + System.currentTimeMillis() - startTime
                  return sym
                } else if (member == NoSymbol) {
                  member = sym
                } else if (members == null) {
                  if (member.name != sym.name ||
                      member != sym &&
                      (member.owner == sym.owner || {
                         if (self == null) self = this.narrow;
                         !self.memberType(member).matches(self.memberType(sym))}))
                    members = newScope(List(member, sym));
                } else {
                  var prevEntry = members lookupEntry sym.name
                  while (prevEntry != null &&
                         !(prevEntry.sym == sym
                           ||
                           prevEntry.sym.owner != sym.owner &&
                           !prevEntry.sym.hasFlag(PRIVATE) &&
                           !sym.hasFlag(PRIVATE) && {
                             if (self == null) self = this.narrow;
                             (self.memberType(prevEntry.sym) matches self.memberType(sym))}))
                    prevEntry = members lookupNextEntry prevEntry;
                  if (prevEntry == null) {
                    members enter sym
                  }
                }
              } else if (excl == DEFERRED) {
                continue = true
              }
            }
            entry = if (name == nme.ANYNAME) entry.next else decls lookupNextEntry entry
          } // while (entry != null)
          // excluded = excluded | LOCAL
        } // while (!bcs.isEmpty)
        excluded = excludedFlags
      } // while (continue)
      checkMalformedSwitch = savedCheckMalformedSwitch
      if (util.Statistics.enabled)
        findMemberMillis = findMemberMillis + System.currentTimeMillis() - startTime
      if (members == null) {
        if (util.Statistics.enabled) if (member == NoSymbol) noMemberCount = noMemberCount + 1;
        member
      } else {
        if (util.Statistics.enabled) multMemberCount = multMemberCount + 1;
        //val pre = if (this.symbol.isClass) this.symbol.thisType else this;
        baseClasses.head.newOverloaded(this, members.toList)
      }
    }
  }

// Subclasses ------------------------------------------------------------

  trait UniqueType {
    private val hashcode = { val h = super.hashCode(); if (h < 0) -h else h }
    override def hashCode() = hashcode
  }

  /** A base class for types that defer some operations
   *  to their immediate supertype.
   */
  abstract class SubType extends Type {
    def supertype: Type
    override def parents: List[Type] = supertype.parents
    override def decls: Scope = supertype.decls
    override def baseType(clazz: Symbol): Type = supertype.baseType(clazz)
    override def closure: Array[Type] = supertype.closure
    override def baseClasses: List[Symbol] = supertype.baseClasses
    // override def isNonNull = supertype.isNonNull
  }

  /** A base class for types that represent a single value
   *  (single-types and this-types).
   */
  abstract class SingletonType extends SubType {
    override def singleDeref: Type
    def supertype: Type = singleDeref
    override def isStable: boolean = true
    override def widen: Type = singleDeref.widen
    override def closure: Array[Type] = {
      if (util.Statistics.enabled) singletonClosureCount = singletonClosureCount + 1
      addClosure(this, supertype.closure)
    }
    override def toString(): String = prefixString + "type"
  }

  /** An object representing an erroneous type */
  case object ErrorType extends Type {
    // todo see whether we can do without
    override def isError: boolean = true
    override def decls: Scope = new ErrorScope(NoSymbol)
    override def findMember(name: Name, excludedFlags: int,
                            requiredFlags: long, stableOnly: boolean): Symbol = {
      var sym = decls lookup name
      if (sym == NoSymbol) {
        sym = NoSymbol.newErrorSymbol(name)
        decls enter sym
      }
      sym
    }
    override def baseType(clazz: Symbol): Type = this
    override def toString(): String = "<error>"
    override def narrow: Type = this
    // override def isNullable: boolean = true
  }

  /** An object representing an unknown type */
  case object WildcardType extends Type {
    override def toString(): String = "?"
    // override def isNullable: boolean = true
  }

  case class BoundedWildcardType(override val bounds: TypeBounds) extends Type {
    override def toString(): String = "?" + bounds
  }

  /** An object representing a non-existing type */
  case object NoType extends Type {
    override def isTrivial: boolean = true
    override def toString(): String = "<notype>"
    // override def isNullable: boolean = true
  }

  /** An object representing a non-existing prefix */
  case object NoPrefix extends Type {
    override def isTrivial: boolean = true
    override def isStable: boolean = true
    override def prefixString = ""
    override def toString(): String = "<noprefix>"
    // override def isNullable: boolean = true
  }

  /** A class for this-types of the form <sym>.this.type
   */
  abstract case class ThisType(sym: Symbol) extends SingletonType {
    //assert(sym.isClass && !sym.isModuleClass || sym.isRoot, sym)
    override def isTrivial: boolean = sym.isPackageClass
    // override def isNonNull = true
    override def symbol = sym
    override def singleDeref: Type = sym.typeOfThis
    override def prefixString =
      if (settings.debug.value) sym.nameString + ".this."
      else if (sym.isRoot || sym.isEmptyPackageClass) ""
      else if (sym.isAnonymousClass || sym.isRefinementClass) "this."
      else if (sym.isPackageClass) sym.fullNameString + "."
      else sym.nameString + ".this."
    override def toString(): String =
      if (sym.isRoot) "<root>"
      else if (sym.isEmptyPackageClass) "<empty>"
      else super.toString()
    override def narrow: Type = this
  }

  /** A class for singleton types of the form &lt;prefix&gt;.&lt;sym.name&gt;.type.
   *  Cannot be created directly; one should always use
   *  <code>singleType</code> for creation.
   */
  abstract case class SingleType(pre: Type, sym: Symbol) extends SingletonType {
    override val isTrivial: boolean = pre.isTrivial
    // override def isNullable = supertype.isNullable
    // override def isNonNull = supertype.isNonNull
    private var singleDerefCache: Type = _
    private var singleDerefPeriod = NoPeriod
    override def singleDeref: Type = {
      val period = singleDerefPeriod
      if (period != currentPeriod) {
        singleDerefPeriod = currentPeriod
        if (!isValid(period)) {
          singleDerefCache = pre.memberType(sym).resultType;
        }
      }
      singleDerefCache
    }

    override def narrow: Type = {
      if (phase.erasedTypes) this
      else {
        val thissym = refinedType(List(this), sym.owner, EmptyScope).symbol
        if (sym.owner != NoSymbol) {
          //Console.println("narrowing module " + sym + thissym.owner);
          thissym.typeOfThis = this
        }
        thissym.thisType
      }
    }

    override def symbol = sym
    override def prefix: Type = pre
    override def prefixString: String =
      if (sym.isEmptyPackage && !settings.debug.value) ""
      else pre.prefixString + sym.nameString + "."
  }

  abstract case class SuperType(thistpe: Type, supertp: Type) extends SingletonType {
    override val isTrivial: boolean = thistpe.isTrivial && supertp.isTrivial
    // override def isNonNull = true;
    override def symbol = thistpe.symbol
    override def singleDeref = supertp
    override def prefix: Type = supertp.prefix
    override def prefixString =
      if (thistpe.prefixString.endsWith("this."))
        thistpe.prefixString.substring(0, thistpe.prefixString.length() - 5) + "super."
      else thistpe.prefixString;
    override def narrow: Type = thistpe.narrow
  }

  /** A class for the bounds of abstract types and type parameters
   */
  abstract case class TypeBounds(lo: Type, hi: Type) extends SubType {
    override val isTrivial: boolean = lo.isTrivial && hi.isTrivial
    def supertype: Type = hi
    override def bounds: TypeBounds = this
    def containsType(that: Type) = that <:< this || lo <:< that && that <:< hi;
    // override def isNullable: boolean = AllRefClass.tpe <:< lo;
    override def toString() = ">: " + lo + " <: " + hi
  }

  /** A common base class for intersection types and class types
   */
  abstract class CompoundType extends Type {

    private var closureCache: Array[Type] = _
    private var closurePeriod = NoPeriod
    private var baseClassesCache: List[Symbol] = _
    private var baseClassesPeriod = NoPeriod

    override def closure: Array[Type] = {
      def computeClosure: Array[Type] =
        try {
          if (util.Statistics.enabled)
            compoundClosureCount = compoundClosureCount + 1
          //System.out.println("computing closure of " + symbol.tpe + " " + parents)//DEBUG
          val buf = new ListBuffer[Type]
          buf += symbol.tpe
          var clSize = 1
          val nparents = parents.length
          if (nparents != 0) {
            val pclosure = new Array[Array[Type]](nparents)
            val index = new Array[int](nparents)
            var i = 0
            for (val p <- parents) {
              pclosure(i) = if (p.closure == null) AnyClass.info.closure // cyclic reference
                            else p.closure
              index(i) = 0
              i = i + 1
            }
            def nextBaseType(i: int): Type = {
              val j = index(i)
              val pci = pclosure(i)
              if (j < pci.length) pci(j) else AnyClass.tpe
            }
            val limit = pclosure(0).length
            while (index(0) != limit) {
              var minSym: Symbol = nextBaseType(0).symbol
              i = 1
              while (i < nparents) {
                if (nextBaseType(i).symbol isLess minSym)
                  minSym = nextBaseType(i).symbol
                i = i + 1
              }
              var minTypes: List[Type] = List()
              i = 0
              while (i < nparents) {
                val tp = nextBaseType(i)
                if (tp.symbol == minSym) {
                  if (!(minTypes exists (tp =:=))) minTypes = tp :: minTypes;
                  index(i) = index(i) + 1
                }
                i = i + 1
              }
              buf += intersectionType(minTypes)
              clSize = clSize + 1
            }
          }
          closureCache = new Array[Type](clSize)
          buf.copyToArray(closureCache, 0)
          //System.out.println("closureCache of " + symbol.tpe + " = " + List.fromArray(closureCache))//DEBUG
          var j = 0
          while (j < clSize) {
            closureCache(j) match {
              case RefinedType(parents, decls) =>
                assert(decls.isEmpty)
                //Console.println("compute closure of "+this+" => glb("+parents+")")
                closureCache(j) = glbNoRefinement(parents)
              case _ =>
            }
            j = j + 1
          }
          //System.out.println("closure of " + symbol.tpe + " = " + List.fromArray(closureCache))//DEBUG
          closureCache
        } catch {
          case ex: MalformedClosure =>
            throw new MalformedType(
              "the type intersection " + this + " is malformed" +
              "\n --- because ---\n" + ex.getMessage())
        }
      val period = closurePeriod;
      if (period != currentPeriod) {
        closurePeriod = currentPeriod
        if (!isValidForBaseClasses(period)) {
          closureCache = null
          closureCache = computeClosure
        }
        //System.out.println("closure(" + symbol + ") = " + List.fromArray(closureCache));//DEBUG
      }
      if (closureCache == null)
        throw new TypeError("illegal cyclic reference involving " + symbol)
      closureCache
    }

    override def baseClasses: List[Symbol] = {
      def computeBaseClasses: List[Symbol] =
        if (parents.isEmpty) List(symbol)
        else {
          //System.out.println("computing base classes of " + symbol + " at phase " + phase);//DEBUG
          // optimized, since this seems to be performance critical
          val superclazz = parents.head
          var mixins = parents.tail
          val sbcs = superclazz.baseClasses
          var bcs = sbcs
          def isNew(clazz: Symbol): boolean = (
            superclazz.closurePos(clazz) < 0 &&
            { var p = bcs;
              while ((p ne sbcs) && (p.head != clazz)) p = p.tail;
              p eq sbcs
            }
          );
          while (!mixins.isEmpty) {
            def addMixinBaseClasses(mbcs: List[Symbol]): List[Symbol] =
              if (mbcs.isEmpty) bcs
              else if (isNew(mbcs.head)) mbcs.head :: addMixinBaseClasses(mbcs.tail)
              else addMixinBaseClasses(mbcs.tail);
            bcs = addMixinBaseClasses(mixins.head.baseClasses)
            mixins = mixins.tail
          }
          symbol :: bcs
        }
      val period = baseClassesPeriod
      if (period != currentPeriod) {
        baseClassesPeriod = currentPeriod
        if (!isValidForBaseClasses(period)) {
          baseClassesCache = null
          baseClassesCache = computeBaseClasses
        }
      }
      if (baseClassesCache == null)
        throw new TypeError("illegal cyclic reference involving " + symbol)
      baseClassesCache
    }

    override def baseType(sym: Symbol): Type = {
      val index = closurePos(sym)
      if (index >= 0) closure(index) else NoType
    }

    override def narrow: Type = symbol.thisType

    // override def isNonNull: boolean = parents forall (.isNonNull);

    // override def isNullable: boolean =
    // parents forall (p => p.isNullable && !p.symbol.isAbstractType);

    override def toString(): String = (
      parents.mkString("", " with ", "") +
      (if (settings.debug.value || parents.isEmpty || decls.elems != null)
        decls.mkString("{", "; ", "}") else "")
    );
  }

  /** A class representing intersection types with refinements of the form
   *    <code>&lt;parents_0&gt; with ... with &lt;parents_n&gt; { decls }</code>
   *  Cannot be created directly;
   *  one should always use <code>refinedType</code> for creation.
   */
  abstract case class RefinedType(override val parents: List[Type],
                                  override val decls: Scope) extends CompoundType

  /** A class representing a class info
   */
  case class ClassInfoType(
    override val parents: List[Type],
    override val decls: Scope,
    override val symbol: Symbol) extends CompoundType {

    // override def isNullable: boolean =
    // symbol == AnyClass ||
    // symbol != AllClass && (symbol isSubClass ObjectClass) && !(symbol isSubClass NonNullClass);

    // override def isNonNull: boolean = symbol == NonNullClass || super.isNonNull;
  }

  class PackageClassInfoType(decls: Scope, clazz: Symbol)
  extends ClassInfoType(List(), decls, clazz)

  /** A class representing a constant type.
   *
   *  @param value ...
   */
  abstract case class ConstantType(value: Constant) extends SingletonType {
    assert(value.tpe.symbol != UnitClass)
    override def isTrivial: boolean = true
    override def symbol: Symbol = value.tpe.symbol
    override def singleDeref: Type = value.tpe
    override def deconst: Type = value.tpe
    private def escape(text: String): String = {
      val buf = new StringBuffer
      for (val c <- Iterator.fromString(text))
        if (Character.isISOControl(c))
          buf.append("\\0" + Integer.toOctalString(c.asInstanceOf[Int]))
        else
          buf.append(c)
      buf.toString
    }
    override def toString(): String =
      value.tpe.toString() + "(\"" + escape(value.stringValue) + "\")"
    // override def isNullable: boolean = value.value == null
    // override def isNonNull: boolean = value.value != null
  }

  /** A class for named types of the form
   *  <code>&lt;prefix&gt;.&lt;sym.name&gt;[args]</code>
   *  Cannot be created directly; one should always use <code>typeRef</code>
   *  for creation.
   *
   *  @param pre  ...
   *  @param sym  ...
   *  @param args ...
   */
  abstract case class TypeRef(pre: Type, sym: Symbol, args: List[Type]) extends Type {
    assert(!checkMalformedSwitch || !sym.isAbstractType || pre.isStable || pre.isError)
    assert(!pre.isInstanceOf[ClassInfoType], this)
    assert(!sym.isTypeParameterOrSkolem || pre == NoPrefix, this)

    private var parentsCache: List[Type] = _
    private var parentsPeriod = NoPeriod
    private var closureCache: Array[Type] = _
    private var closurePeriod = NoPeriod

    override val isTrivial: boolean =
      pre.isTrivial && !sym.isTypeParameter && args.forall(.isTrivial)

    def transform(tp: Type): Type =
      tp.asSeenFrom(pre, sym.owner).subst(sym.typeParams, args)

    def transform(cl: Array[Type]): Array[Type] = {<commit_msg>fixed method toString for character constants<commit_after>/* NSC -- new Scala compiler
 * Copyright 2005-2006 LAMP/EPFL
 * @author  <NAME>
 */
// $Id$

package scala.tools.nsc.symtab

import scala.collection.mutable.ListBuffer
import scala.tools.nsc.util.{HashSet, Position}
import Flags._

/* A standard type pattern match:
  case ErrorType =>
  case WildcardType =>
  case NoType =>
  case NoPrefix =>
  case ThisType(_) =>
  case SingleType(pre, sym) =>
  case ConstantType(value) =>
  case TypeRef(pre, sym, args) =>
  case TypeBounds(lo, hi) =>
  case RefinedType(parents, defs) =>
  case ClassInfoType(parents, defs, clazz) =>
  case MethodType(paramtypes, result) =>
  case PolyType(tparams, result) =>
  // the last three types are not used after phase `typer'.
  case OverloadedType(pre, tparams, alts) =>
  case AntiPolyType(pre: Type, targs) =>
  case TypeVar(_, _) =>
*/

trait Types requires SymbolTable {
  import definitions._

  //statistics
  var singletonClosureCount = 0
  var compoundClosureCount = 0
  var typerefClosureCount = 0
  var findMemberCount = 0
  var noMemberCount = 0
  var multMemberCount = 0
  var findMemberMillis = 0l
  var subtypeCount = 0
  var subtypeMillis = 0l

  private var explainSwitch = false
  private var checkMalformedSwitch = true

  val emptyTypeArray = new Array[Type](0)

  /** The base class for all types */
  abstract class Type {

    /** Types for which asSeenFrom always is the identity, no matter what
     *  prefix or owner.
     */
    def isTrivial: boolean = false

    /** The symbol associated with the type */
    def symbol: Symbol = NoSymbol

    /** The base type underlying a singleton type,
     *  identity on all other types */
    def singleDeref: Type = this

    /** Widen from singleton type to its underlying non-singleton base type
     *  by applying one or more singleDeref steps,
     *  identity for all other types */
    def widen: Type = this

    /** The type of <code>this</code> of a class type or reference type
     */
    def typeOfThis = symbol.typeOfThis

    /** Map to a this type which is a subtype of this type.
     */
    def narrow: Type =
      if (phase.erasedTypes) this
      else refinedType(List(this), commonOwner(this), EmptyScope).narrow

    /** Map a constant type to its underlying base type,
     *  identity for all other types */
    def deconst: Type = this

    /** For a TypeBounds type, itself;
     *  for a reference denoting an abstract type, its bounds,
     *  for all other types, a TypeBounds type all of whose bounds are this type.
     *  error for all other types */
    def bounds: TypeBounds = TypeBounds(this, this)

    /** For a class or intersection type, its parents.
     *  For a TypeBounds type, the parents of its hi bound.
     *  inherited by typerefs, singleton types, and refinement types,
     *  The empty list for all other types */
    def parents: List[Type] = List()

    /** For a typeref or single-type, its prefix. NoType for all other types. */
    def prefix: Type = NoType

    /** For a typeref, its arguments. The empty list for all other types */
    def typeArgs: List[Type] = List()

    /** For a method or poly type, its direct result type,
     *  the type itself for all other types */
    def resultType: Type = this

    /** For a curried method or poly type its non-method result type,
     *  the type itself for all other types */
    def finalResultType: Type = this

    /** For a method or poly type, the number of its value parameter sections,
     *  0 for all other types */
    def paramSectionCount: int = 0

    /** For a method or poly type, the types of its first value parameter section,
     *  the empty list for all other types */
    def paramTypes: List[Type] = List()

    /** For a poly type, its type parameters,
     *  the empty list for all other types */
    def typeParams: List[Symbol] = List()

    /** Is this type produced as a repair for an error? */
    def isError: boolean = symbol.isError

    /** Is this type produced as a repair for an error? */
    def isErroneous: boolean = {
      ErroneousTraverser.result = false
      ErroneousTraverser.traverse(this)
      ErroneousTraverser.result
    }

    /** Does this type denote a stable reference (i.e. singleton type)? */
    def isStable: boolean = false

    /** Does this type denote a reference type which can be null? */
    // def isNullable: boolean = false

    /** Is this type guaranteed to be non-null? */
    // def isNonNull: boolean = false

    /** For a classtype or refined type, its defined or declared members;
     *  inherited by subtypes and typerefs.
     *  The empty scope for all other types */
    def decls: Scope = EmptyScope

    /** The defined or declared members with name <code>name</code> in this type;
     *  an OverloadedSymbol if several exist, NoSymbol if none exist.
     *  Alternatives of overloaded symbol appear in the order they are declared.
     */
    def decl(name: Name): Symbol = findDecl(name, 0)

    /** The non-private defined or declared members with name `name' in this type;
     *  an OverloadedSymbol if several exist, NoSymbol if none exist.
     *  Alternatives of overloaded symbol appear in the order they are declared.
     */
    def nonPrivateDecl(name: Name): Symbol = findDecl(name, PRIVATE)

    /** A list of all members of this type (defined or inherited)
     *  Members appear in linearization order of their owners.
     *  Members with the same owner appear in reverse order of their declarations.
     */
    def members: List[Symbol] = findMember(nme.ANYNAME, 0, 0, false).alternatives

    /** A list of all non-private members of this type (defined or inherited) */
    def nonPrivateMembers: List[Symbol] =
      findMember(nme.ANYNAME, PRIVATE | BRIDGE, 0, false).alternatives

    /** A list of all implicit symbols of this type  (defined or inherited) */
    def implicitMembers: List[Symbol] =
      findMember(nme.ANYNAME, BRIDGE, IMPLICIT, false).alternatives

    /** The member with given name,
     *  an OverloadedSymbol if several exist, NoSymbol if none exist */
    def member(name: Name): Symbol = findMember(name, BRIDGE, 0, false)

    /** The non-private member with given name,
     *  an OverloadedSymbol if several exist, NoSymbol if none exist */
    def nonPrivateMember(name: Name): Symbol =
      findMember(name, PRIVATE | BRIDGE, 0, false)

    /** The non-local member with given name,
     *  an OverloadedSymbol if several exist, NoSymbol if none exist */
    def nonLocalMember(name: Name): Symbol =
      findMember(name, LOCAL | BRIDGE, 0, false)

    /** The least type instance of given class which is a supertype
     *  of this type */
    def baseType(clazz: Symbol): Type = NoType

    /** This type as seen from prefix <code>pre</code> and class
     *  <code>clazz</code>. This means:
     *  Replace all thistypes of <code>clazz</code> or one of its subclasses
     *  by <code>pre</code> and instantiate all parameters by arguments of
     *  <code>pre</code>.
     *  Proceed analogously for thistypes referring to outer classes.
     */
    def asSeenFrom(pre: Type, clazz: Symbol): Type =
      if (!isTrivial && (!phase.erasedTypes || pre.symbol == ArrayClass)) {
        new AsSeenFromMap(pre, clazz) apply this
      } else this

    /** The info of <code>sym</code>, seen as a member of this type.
     */
    def memberInfo(sym: Symbol): Type =
      sym.info.asSeenFrom(this, sym.owner)

    /** The type of `sym', seen as a member of this type. */
    def memberType(sym: Symbol): Type = {
      sym.tpe match {
        case ov @ OverloadedType(pre, alts) =>
          OverloadedType(this, alts)
/*
          val pre1 = pre match {
            case ClassInfoType(_, _, clazz) => clazz.tpe
            case _ => pre
          }
          if (this =:= pre1) ov
          else if (this =:= pre1.narrow) OverloadedType(this, alts)
          else {
            Console.println("bad memberType of overloaded symbol: "+this+"/"+pre1+"/"+pre1.narrow)
            assert(false)
            ov
          }
*/
        case _ =>
          //System.out.println("" + this + ".memberType(" + sym +":" + sym.tpe +")");//DEBUG
          sym.tpe.asSeenFrom(this, sym.owner)
      }
    }

    /** Substitute types <code>to</code> for occurrences of references to
     *  symbols <code>from</code> in this type.
     */
    def subst(from: List[Symbol], to: List[Type]): Type =
      new SubstTypeMap(from, to) apply this

    /** Substitute symbols <code>to</code> for occurrences of symbols
     *  <code>from</code> in this type.
     */
    def substSym(from: List[Symbol], to: List[Symbol]): Type =
      new SubstSymMap(from, to) apply this

    /** Substitute all occurrences of <code>ThisType(from)</code> in this type
     *  by <code>to</code>.
     */
    def substThis(from: Symbol, to: Type): Type =
      new SubstThisMap(from, to) apply this

    def substSuper(from: Type, to: Type): Type =
      new SubstSuperMap(from, to) apply this

    /** Does this type contain a reference to this symbol? */
    def contains(sym: Symbol): boolean =
      new ContainsTraverser(sym).traverse(this).result

    /** Is this type a subtype of that type? */
    def <:<(that: Type): boolean = {
      if (util.Statistics.enabled) subtypeCount = subtypeCount + 1
      val startTime = if (util.Statistics.enabled) System.currentTimeMillis() else 0l
      val result =
        ((this eq that) ||
         (if (explainSwitch) explain("<", isSubType, this, that)
          else isSubType(this, that)));
      if (util.Statistics.enabled)
        subtypeMillis = subtypeMillis + System.currentTimeMillis() - startTime
      result
    }

    /** Is this type equivalent to that type? */
    def =:=(that: Type): boolean = (
      (this eq that) ||
      (if (explainSwitch) explain("=", isSameType, this, that)
       else isSameType(this, that))
    );

    /** Does this type implement symbol <code>sym</code> with same or stronger type?
     */
    def specializes(sym: Symbol): boolean =
      if (explainSwitch) explain("specializes", specializesSym, this, sym)
      else specializesSym(this, sym)

    /** Is this type close enough to that type so that
     *  members with the two type would override each other?
     *  This means:
     *    - Either both types are polytypes with the same number of
     *      type parameters and their result types match after renaming
     *      corresponding type parameters
     *    - Or both types are method types with equivalent type parameter types
     *      and matching result types
     *    - Or both types are equivalent
     *    - Or phase.erasedTypes is false and both types are neither method nor
     *      poly types.
     */
    def matches(that: Type): boolean = matchesType(this, that)

    /** The shortest sorted upwards closed array of types that contains
     *  this type as first element.
     *
     *  A list or array of types ts is upwards closed if
     *
     *    for all t in ts:
     *      for all typerefs p.s[args] such that t &lt;: p.s[args]
     *      there exists a typeref p'.s[args'] in ts such that
     *      t &lt;: p'.s['args] &lt;: p.s[args],
     *      and
     *      for all singleton types p.s such that t &lt;: p.s
     *      there exists a singleton type p'.s in ts such that
     *      t &lt;: p'.s &lt;: p.s
     *
     *  Sorting is with respect to Symbol.isLess() on type symbols.
     */
    def closure: Array[Type] = Array(this)

    def baseClasses: List[Symbol] = List()

    /**
     *  @param sym the class symbol
     *  @return    the index of given class symbol in the closure of this type,
     *             or -1 if no base type with given class symbol exists.
     */
    def closurePos(sym: Symbol): int = {
      val cl = closure
      var lo = 0
      var hi = cl.length - 1
      while (lo <= hi) {
        val mid = (lo + hi) / 2
        val clsym = cl(mid).symbol
        if (sym == clsym) return mid
        else if (sym isLess clsym) hi = mid - 1
        else if (clsym isLess sym) lo = mid + 1
        else throw new Error()
      }
      -1
    }

    /** If this is a polytype, a copy with cloned type parameters owned
     *  by <code>owner</code>. Identity for all other types.
     */
    def cloneInfo(owner: Symbol) = this

    protected def objectPrefix = "object "
    protected def packagePrefix = "package "

    def trimPrefix(str: String) =
      if (str.startsWith(objectPrefix)) str.substring(objectPrefix.length)
      else if (str.startsWith(packagePrefix)) str.substring(packagePrefix.length)
      else str

    /** The string representation of this type used as a prefix */
    def prefixString = trimPrefix(toString()) + "#"

    /** The string representation of this type, with singletypes explained */
    def toLongString = {
      val str = toString()
      if (str endsWith ".type") str + " (with underlying type " + widen + ")"
      else str
    }

    /** Is this type completed (i.e. not a lazy type)?
     */
    def isComplete: boolean = true

    /** If this is a lazy type, assign a new type to <code>sym</code>. */
    def complete(sym: Symbol): unit = {
      if (sym == NoSymbol || sym.isPackageClass)
        sym.validTo = period(currentRunId, phaseId(sym.validTo))
      else {
        val this1 = adaptToNewRunMap(this)
        if (this1 eq this) sym.validTo = period(currentRunId, phaseId(sym.validTo))
        else {
          //System.out.println("new type of " + sym + "=" + this1 + ", used to be " + this);//DEBUG
          sym.setInfo(this1)
        }
      }
    }

    /** If this is a symbol loader type, load and assign a new type to
     *  <code>sym</code>.
     */
    def load(sym: Symbol): unit = {}

    private def findDecl(name: Name, excludedFlags: int): Symbol = {
      var alts: List[Symbol] = List()
      var sym: Symbol = NoSymbol
      var e: ScopeEntry = decls.lookupEntry(name)
      while (e != null) {
        if (!e.sym.hasFlag(excludedFlags)) {
          if (sym == NoSymbol) sym = e.sym
          else {
            if (alts.isEmpty) alts = List(sym)
            alts = e.sym :: alts
          }
        }
        e = decls.lookupNextEntry(e)
      }
      if (alts.isEmpty) sym
      else baseClasses.head.newOverloaded(this, alts)
    }

    /**
     *  @param name          ...
     *  @param excludedFlags ...
     *  @param requiredFlags ...
     *  @param stableOnly    ...
     *  @return              ...
     */
    //TODO: use narrow only for modules? (correct? efficiency gain?)
    def findMember(name: Name, excludedFlags: int, requiredFlags: long, stableOnly: boolean): Symbol = {
      if (util.Statistics.enabled) findMemberCount = findMemberCount + 1
      val startTime = if (util.Statistics.enabled) System.currentTimeMillis() else 0l

      //System.out.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG
      var members: Scope = null
      var member: Symbol = NoSymbol
      var excluded = excludedFlags | DEFERRED
      var self: Type = null
      var continue = true
      var savedCheckMalformedSwitch = checkMalformedSwitch
      checkMalformedSwitch = false
      while (continue) {
        continue = false
        var bcs = baseClasses
        while (!bcs.isEmpty) {
          val decls = bcs.head.info.decls
          bcs = if (name == nme.CONSTRUCTOR) Nil else bcs.tail
          var entry =
            if (name == nme.ANYNAME) decls.elems else decls lookupEntry name
          while (entry != null) {
            val sym = entry.sym
            if (sym.getFlag(requiredFlags) == requiredFlags) {
              val excl = sym.getFlag(excluded)
              if (excl == 0) {
                if (name.isTypeName || stableOnly) {
                  checkMalformedSwitch = savedCheckMalformedSwitch
                  if (util.Statistics.enabled)
                    findMemberMillis = findMemberMillis + System.currentTimeMillis() - startTime
                  return sym
                } else if (member == NoSymbol) {
                  member = sym
                } else if (members == null) {
                  if (member.name != sym.name ||
                      member != sym &&
                      (member.owner == sym.owner || {
                         if (self == null) self = this.narrow;
                         !self.memberType(member).matches(self.memberType(sym))}))
                    members = newScope(List(member, sym));
                } else {
                  var prevEntry = members lookupEntry sym.name
                  while (prevEntry != null &&
                         !(prevEntry.sym == sym
                           ||
                           prevEntry.sym.owner != sym.owner &&
                           !prevEntry.sym.hasFlag(PRIVATE) &&
                           !sym.hasFlag(PRIVATE) && {
                             if (self == null) self = this.narrow;
                             (self.memberType(prevEntry.sym) matches self.memberType(sym))}))
                    prevEntry = members lookupNextEntry prevEntry;
                  if (prevEntry == null) {
                    members enter sym
                  }
                }
              } else if (excl == DEFERRED) {
                continue = true
              }
            }
            entry = if (name == nme.ANYNAME) entry.next else decls lookupNextEntry entry
          } // while (entry != null)
          // excluded = excluded | LOCAL
        } // while (!bcs.isEmpty)
        excluded = excludedFlags
      } // while (continue)
      checkMalformedSwitch = savedCheckMalformedSwitch
      if (util.Statistics.enabled)
        findMemberMillis = findMemberMillis + System.currentTimeMillis() - startTime
      if (members == null) {
        if (util.Statistics.enabled) if (member == NoSymbol) noMemberCount = noMemberCount + 1;
        member
      } else {
        if (util.Statistics.enabled) multMemberCount = multMemberCount + 1;
        //val pre = if (this.symbol.isClass) this.symbol.thisType else this;
        baseClasses.head.newOverloaded(this, members.toList)
      }
    }
  }

// Subclasses ------------------------------------------------------------

  trait UniqueType {
    private val hashcode = { val h = super.hashCode(); if (h < 0) -h else h }
    override def hashCode() = hashcode
  }

  /** A base class for types that defer some operations
   *  to their immediate supertype.
   */
  abstract class SubType extends Type {
    def supertype: Type
    override def parents: List[Type] = supertype.parents
    override def decls: Scope = supertype.decls
    override def baseType(clazz: Symbol): Type = supertype.baseType(clazz)
    override def closure: Array[Type] = supertype.closure
    override def baseClasses: List[Symbol] = supertype.baseClasses
    // override def isNonNull = supertype.isNonNull
  }

  /** A base class for types that represent a single value
   *  (single-types and this-types).
   */
  abstract class SingletonType extends SubType {
    override def singleDeref: Type
    def supertype: Type = singleDeref
    override def isStable: boolean = true
    override def widen: Type = singleDeref.widen
    override def closure: Array[Type] = {
      if (util.Statistics.enabled) singletonClosureCount = singletonClosureCount + 1
      addClosure(this, supertype.closure)
    }
    override def toString(): String = prefixString + "type"
  }

  /** An object representing an erroneous type */
  case object ErrorType extends Type {
    // todo see whether we can do without
    override def isError: boolean = true
    override def decls: Scope = new ErrorScope(NoSymbol)
    override def findMember(name: Name, excludedFlags: int,
                            requiredFlags: long, stableOnly: boolean): Symbol = {
      var sym = decls lookup name
      if (sym == NoSymbol) {
        sym = NoSymbol.newErrorSymbol(name)
        decls enter sym
      }
      sym
    }
    override def baseType(clazz: Symbol): Type = this
    override def toString(): String = "<error>"
    override def narrow: Type = this
    // override def isNullable: boolean = true
  }

  /** An object representing an unknown type */
  case object WildcardType extends Type {
    override def toString(): String = "?"
    // override def isNullable: boolean = true
  }

  case class BoundedWildcardType(override val bounds: TypeBounds) extends Type {
    override def toString(): String = "?" + bounds
  }

  /** An object representing a non-existing type */
  case object NoType extends Type {
    override def isTrivial: boolean = true
    override def toString(): String = "<notype>"
    // override def isNullable: boolean = true
  }

  /** An object representing a non-existing prefix */
  case object NoPrefix extends Type {
    override def isTrivial: boolean = true
    override def isStable: boolean = true
    override def prefixString = ""
    override def toString(): String = "<noprefix>"
    // override def isNullable: boolean = true
  }

  /** A class for this-types of the form <sym>.this.type
   */
  abstract case class ThisType(sym: Symbol) extends SingletonType {
    //assert(sym.isClass && !sym.isModuleClass || sym.isRoot, sym)
    override def isTrivial: boolean = sym.isPackageClass
    // override def isNonNull = true
    override def symbol = sym
    override def singleDeref: Type = sym.typeOfThis
    override def prefixString =
      if (settings.debug.value) sym.nameString + ".this."
      else if (sym.isRoot || sym.isEmptyPackageClass) ""
      else if (sym.isAnonymousClass || sym.isRefinementClass) "this."
      else if (sym.isPackageClass) sym.fullNameString + "."
      else sym.nameString + ".this."
    override def toString(): String =
      if (sym.isRoot) "<root>"
      else if (sym.isEmptyPackageClass) "<empty>"
      else super.toString()
    override def narrow: Type = this
  }

  /** A class for singleton types of the form &lt;prefix&gt;.&lt;sym.name&gt;.type.
   *  Cannot be created directly; one should always use
   *  <code>singleType</code> for creation.
   */
  abstract case class SingleType(pre: Type, sym: Symbol) extends SingletonType {
    override val isTrivial: boolean = pre.isTrivial
    // override def isNullable = supertype.isNullable
    // override def isNonNull = supertype.isNonNull
    private var singleDerefCache: Type = _
    private var singleDerefPeriod = NoPeriod
    override def singleDeref: Type = {
      val period = singleDerefPeriod
      if (period != currentPeriod) {
        singleDerefPeriod = currentPeriod
        if (!isValid(period)) {
          singleDerefCache = pre.memberType(sym).resultType;
        }
      }
      singleDerefCache
    }

    override def narrow: Type = {
      if (phase.erasedTypes) this
      else {
        val thissym = refinedType(List(this), sym.owner, EmptyScope).symbol
        if (sym.owner != NoSymbol) {
          //Console.println("narrowing module " + sym + thissym.owner);
          thissym.typeOfThis = this
        }
        thissym.thisType
      }
    }

    override def symbol = sym
    override def prefix: Type = pre
    override def prefixString: String =
      if (sym.isEmptyPackage && !settings.debug.value) ""
      else pre.prefixString + sym.nameString + "."
  }

  abstract case class SuperType(thistpe: Type, supertp: Type) extends SingletonType {
    override val isTrivial: boolean = thistpe.isTrivial && supertp.isTrivial
    // override def isNonNull = true;
    override def symbol = thistpe.symbol
    override def singleDeref = supertp
    override def prefix: Type = supertp.prefix
    override def prefixString =
      if (thistpe.prefixString.endsWith("this."))
        thistpe.prefixString.substring(0, thistpe.prefixString.length() - 5) + "super."
      else thistpe.prefixString;
    override def narrow: Type = thistpe.narrow
  }

  /** A class for the bounds of abstract types and type parameters
   */
  abstract case class TypeBounds(lo: Type, hi: Type) extends SubType {
    override val isTrivial: boolean = lo.isTrivial && hi.isTrivial
    def supertype: Type = hi
    override def bounds: TypeBounds = this
    def containsType(that: Type) = that <:< this || lo <:< that && that <:< hi;
    // override def isNullable: boolean = AllRefClass.tpe <:< lo;
    override def toString() = ">: " + lo + " <: " + hi
  }

  /** A common base class for intersection types and class types
   */
  abstract class CompoundType extends Type {

    private var closureCache: Array[Type] = _
    private var closurePeriod = NoPeriod
    private var baseClassesCache: List[Symbol] = _
    private var baseClassesPeriod = NoPeriod

    override def closure: Array[Type] = {
      def computeClosure: Array[Type] =
        try {
          if (util.Statistics.enabled)
            compoundClosureCount = compoundClosureCount + 1
          //System.out.println("computing closure of " + symbol.tpe + " " + parents)//DEBUG
          val buf = new ListBuffer[Type]
          buf += symbol.tpe
          var clSize = 1
          val nparents = parents.length
          if (nparents != 0) {
            val pclosure = new Array[Array[Type]](nparents)
            val index = new Array[int](nparents)
            var i = 0
            for (val p <- parents) {
              pclosure(i) = if (p.closure == null) AnyClass.info.closure // cyclic reference
                            else p.closure
              index(i) = 0
              i = i + 1
            }
            def nextBaseType(i: int): Type = {
              val j = index(i)
              val pci = pclosure(i)
              if (j < pci.length) pci(j) else AnyClass.tpe
            }
            val limit = pclosure(0).length
            while (index(0) != limit) {
              var minSym: Symbol = nextBaseType(0).symbol
              i = 1
              while (i < nparents) {
                if (nextBaseType(i).symbol isLess minSym)
                  minSym = nextBaseType(i).symbol
                i = i + 1
              }
              var minTypes: List[Type] = List()
              i = 0
              while (i < nparents) {
                val tp = nextBaseType(i)
                if (tp.symbol == minSym) {
                  if (!(minTypes exists (tp =:=))) minTypes = tp :: minTypes;
                  index(i) = index(i) + 1
                }
                i = i + 1
              }
              buf += intersectionType(minTypes)
              clSize = clSize + 1
            }
          }
          closureCache = new Array[Type](clSize)
          buf.copyToArray(closureCache, 0)
          //System.out.println("closureCache of " + symbol.tpe + " = " + List.fromArray(closureCache))//DEBUG
          var j = 0
          while (j < clSize) {
            closureCache(j) match {
              case RefinedType(parents, decls) =>
                assert(decls.isEmpty)
                //Console.println("compute closure of "+this+" => glb("+parents+")")
                closureCache(j) = glbNoRefinement(parents)
              case _ =>
            }
            j = j + 1
          }
          //System.out.println("closure of " + symbol.tpe + " = " + List.fromArray(closureCache))//DEBUG
          closureCache
        } catch {
          case ex: MalformedClosure =>
            throw new MalformedType(
              "the type intersection " + this + " is malformed" +
              "\n --- because ---\n" + ex.getMessage())
        }
      val period = closurePeriod;
      if (period != currentPeriod) {
        closurePeriod = currentPeriod
        if (!isValidForBaseClasses(period)) {
          closureCache = null
          closureCache = computeClosure
        }
        //System.out.println("closure(" + symbol + ") = " + List.fromArray(closureCache));//DEBUG
      }
      if (closureCache == null)
        throw new TypeError("illegal cyclic reference involving " + symbol)
      closureCache
    }

    override def baseClasses: List[Symbol] = {
      def computeBaseClasses: List[Symbol] =
        if (parents.isEmpty) List(symbol)
        else {
          //System.out.println("computing base classes of " + symbol + " at phase " + phase);//DEBUG
          // optimized, since this seems to be performance critical
          val superclazz = parents.head
          var mixins = parents.tail
          val sbcs = superclazz.baseClasses
          var bcs = sbcs
          def isNew(clazz: Symbol): boolean = (
            superclazz.closurePos(clazz) < 0 &&
            { var p = bcs;
              while ((p ne sbcs) && (p.head != clazz)) p = p.tail;
              p eq sbcs
            }
          );
          while (!mixins.isEmpty) {
            def addMixinBaseClasses(mbcs: List[Symbol]): List[Symbol] =
              if (mbcs.isEmpty) bcs
              else if (isNew(mbcs.head)) mbcs.head :: addMixinBaseClasses(mbcs.tail)
              else addMixinBaseClasses(mbcs.tail);
            bcs = addMixinBaseClasses(mixins.head.baseClasses)
            mixins = mixins.tail
          }
          symbol :: bcs
        }
      val period = baseClassesPeriod
      if (period != currentPeriod) {
        baseClassesPeriod = currentPeriod
        if (!isValidForBaseClasses(period)) {
          baseClassesCache = null
          baseClassesCache = computeBaseClasses
        }
      }
      if (baseClassesCache == null)
        throw new TypeError("illegal cyclic reference involving " + symbol)
      baseClassesCache
    }

    override def baseType(sym: Symbol): Type = {
      val index = closurePos(sym)
      if (index >= 0) closure(index) else NoType
    }

    override def narrow: Type = symbol.thisType

    // override def isNonNull: boolean = parents forall (.isNonNull);

    // override def isNullable: boolean =
    // parents forall (p => p.isNullable && !p.symbol.isAbstractType);

    override def toString(): String = (
      parents.mkString("", " with ", "") +
      (if (settings.debug.value || parents.isEmpty || decls.elems != null)
        decls.mkString("{", "; ", "}") else "")
    );
  }

  /** A class representing intersection types with refinements of the form
   *    <code>&lt;parents_0&gt; with ... with &lt;parents_n&gt; { decls }</code>
   *  Cannot be created directly;
   *  one should always use <code>refinedType</code> for creation.
   */
  abstract case class RefinedType(override val parents: List[Type],
                                  override val decls: Scope) extends CompoundType

  /** A class representing a class info
   */
  case class ClassInfoType(
    override val parents: List[Type],
    override val decls: Scope,
    override val symbol: Symbol) extends CompoundType {

    // override def isNullable: boolean =
    // symbol == AnyClass ||
    // symbol != AllClass && (symbol isSubClass ObjectClass) && !(symbol isSubClass NonNullClass);

    // override def isNonNull: boolean = symbol == NonNullClass || super.isNonNull;
  }

  class PackageClassInfoType(decls: Scope, clazz: Symbol)
  extends ClassInfoType(List(), decls, clazz)

  /** A class representing a constant type.
   *
   *  @param value ...
   */
  abstract case class ConstantType(value: Constant) extends SingletonType {
    assert(value.tpe.symbol != UnitClass)
    override def isTrivial: boolean = true
    override def symbol: Symbol = value.tpe.symbol
    override def singleDeref: Type = value.tpe
    override def deconst: Type = value.tpe
    override def toString(): String = {
      def escape(text: String): String = {
        val buf = new StringBuffer
        for (val c <- Iterator.fromString(text))
          if (Character.isISOControl(c))
            buf.append("\\0" + Integer.toOctalString(c.asInstanceOf[Int]))
          else
            buf.append(c)
        buf.toString
      }
      val svalue =
        if (value.tag == CharTag) "'" + escape(value.stringValue) + "'"
        else if (value.tag == StringTag) "\"" + escape(value.stringValue) + "\""
        else value.stringValue
      value.tpe.toString() + "(" + svalue + ")"
    }
    // override def isNullable: boolean = value.value == null
    // override def isNonNull: boolean = value.value != null
  }

  /** A class for named types of the form
   *  <code>&lt;prefix&gt;.&lt;sym.name&gt;[args]</code>
   *  Cannot be created directly; one should always use <code>typeRef</code>
   *  for creation.
   *
   *  @param pre  ...
   *  @param sym  ...
   *  @param args ...
   */
  abstract case class TypeRef(pre: Type, sym: Symbol, args: List[Type]) extends Type {
    assert(!checkMalformedSwitch || !sym.isAbstractType || pre.isStable || pre.isError)
    assert(!pre.isInstanceOf[ClassInfoType], this)
    assert(!sym.isTypeParameterOrSkolem || pre == NoPrefix, this)

    private var parentsCache: List[Type] = _
    private var parentsPeriod = NoPeriod
    private var closureCache: Array[Type] = _
    private var closurePeriod = NoPeriod

    override val isTrivial: boolean =
      pre.isTrivial && !sym.isTypeParameter && args.forall(.isTrivial)

    def transform(tp: Type): Type =
      tp.asSeenFrom(pre, sym.owner).subst(sym.typeParams, args)

    def transform(cl: Array[Type]): Array[Type] = {
{'fraction_non_alphanumeric': 0.1052448399007324, 'fraction_numerical': 0.002300102899340234, 'mean_word_length': 2.225704105042222, 'pattern_counts': {'":': 4, '<': 151, '<?xml version=': 0, '>': 163, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4222003', 'n_tokens_mistral': 18938, 'n_tokens_neox': 18474, 'n_words': 6175}