<commit_before>package com.redhat.ceylon.compiler.typechecker.model;

import static com.redhat.ceylon.compiler.typechecker.model.Util.addToIntersection;
import static com.redhat.ceylon.compiler.typechecker.model.Util.addToSupertypes;
import static com.redhat.ceylon.compiler.typechecker.model.Util.addToUnion;
import static com.redhat.ceylon.compiler.typechecker.model.Util.arguments;
import static com.redhat.ceylon.compiler.typechecker.model.Util.principalInstantiation;
import static java.util.Collections.emptyList;
import static java.util.Collections.singletonList;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

import com.redhat.ceylon.compiler.typechecker.context.ProducedTypeCache;
import com.redhat.ceylon.compiler.typechecker.util.ProducedTypeNamePrinter;


/**
 * A produced type with actual type arguments.
 * This represents something that is actually
 * considered a "type" in the language
 * specification.
 *
 * @author <NAME>
 */
public class ProducedType extends ProducedReference {
    
    private String underlyingType;
    private boolean isRaw;
    private ProducedType resolvedAliases;
//    private Map<TypeDeclaration, ProducedType> superTypesCache = 
//            new HashMap<TypeDeclaration, ProducedType>(5);

    private int hashCode;

    public int getHashCode(){
        if(hashCode == 0){
            int ret = 17;
            ProducedType qualifyingType = getQualifyingType();
            ret = (37 * ret) + (qualifyingType != null ? qualifyingType.hashCode() : 0);
            TypeDeclaration declaration = getDeclaration();
            ret = (37 * ret) + declaration.hashCodeForCache();
            
            Map<TypeParameter, ProducedType> typeArguments = getTypeArguments();

            if(!typeArguments.isEmpty()){
                List<TypeParameter> typeParameters = declaration.getTypeParameters();
                for(int i=0,l=typeParameters.size();i<l;i++){
                    TypeParameter typeParameter = typeParameters.get(i);
                    ProducedType typeArgument = typeArguments.get(typeParameter);
                    ret = (37 * ret) + (typeArgument != null ? typeArgument.hashCode() : 0);
                }
            }
            hashCode = ret;
        }
        return hashCode;
    }

    ProducedType() {}

    @Override
    public TypeDeclaration getDeclaration() {
        return (TypeDeclaration) super.getDeclaration();
    }
    
    /**
     * Is this type exactly the same type as the
     * given type? 
     */
    public boolean isExactly(ProducedType type) {
        return resolveAliases().isExactlyInternal(type.resolveAliases());
    }
    
    public boolean isExactlyInternal(ProducedType type) {
        if (getDeclaration() instanceof NothingType) {
            return type.isNothing();
        }
        else if (getDeclaration() instanceof UnionType) {
            List<ProducedType> cases = getCaseTypes();
            if (type.getDeclaration() instanceof UnionType) {
                List<ProducedType> otherCases = type.getCaseTypes();
                if (cases.size()!=otherCases.size()) {
                    return false;
                }
                else {
                    for (ProducedType c: cases) {
                        boolean found = false;
                        for (ProducedType oc: otherCases) {
                            if (c.isExactlyInternal(oc)) {
                                found = true;
                                break;
                            }
                        }
                        if (!found) {
                            return false;
                        }
                    }
                    return true;
                }
            }
            else if (cases.size()==1) {
                ProducedType st = cases.get(0);
                return st.isExactlyInternal(type);
            }
            else {
                return false;
            }
        }
        else if (getDeclaration() instanceof IntersectionType) {
            List<ProducedType> types = getSatisfiedTypes();
            if (type.getDeclaration() instanceof IntersectionType) {
                List<ProducedType> otherTypes = type.getSatisfiedTypes();
                if (types.size()!=otherTypes.size()) {
                    return false;
                }
                else {
                    for (ProducedType c: types) {
                        boolean found = false;
                        for (ProducedType oc: otherTypes) {
                            if (c.getDeclaration().equals(oc.getDeclaration())) {
                                if (c.isExactlyInternal(oc)) {
                                    found = true;
                                    break;
                                }
                                //given a covariant type Co, and interfaces
                                //A satisfies Co<B&Co<A>> and 
                                //B satisfies Co<A&Co<B>>, then
                                //A&Co<B> is equivalent A&Co<B&Co<A>> as a 
                                //consequence of principal instantiation 
                                //inheritance
                                ProducedType cst = getSupertypeInternal(c.getDeclaration());
                                ProducedType ocst = type.getSupertypeInternal(oc.getDeclaration());
                                if (cst.isExactlyInternal(ocst)) {
                                    found = true;
                                    break;
                                }
                            }
                        }
                        if (!found) {
                            return false;
                        }
                    }
                    return true;
                }
            }
            else if (types.size()==1) {
                ProducedType st = types.get(0);
                return st.isExactlyInternal(type);
            }
            else {
                return false;
            }
        }
        else if (type.getDeclaration() instanceof UnionType) {
            List<ProducedType> otherCases = type.getCaseTypes();
            if (otherCases.size()==1) {
                ProducedType st = otherCases.get(0);
                return this.isExactlyInternal(st);
            }
            else {
                return false;
            }
        }
        else if (type.getDeclaration() instanceof IntersectionType) {
            List<ProducedType> otherTypes = type.getSatisfiedTypes();
            if (otherTypes.size()==1) {
                ProducedType st = otherTypes.get(0);
                return this.isExactlyInternal(st);
            }
            else {
                return false;
            }
        }
        else {
            if (!type.getDeclaration().equals(getDeclaration())) {
                return false;
            }
            else {
                ProducedType qt = getDeclaration().isStaticallyImportable() ?
                        null : getQualifyingType();
                ProducedType tqt = type.getDeclaration().isStaticallyImportable() ? 
                        null : type.getQualifyingType();
                if (qt==null) {
                    if (tqt!=null) {
                        return false;
                    }
                }
                else {
                    if (tqt==null) {
                        return false;
                    }
                    else {
                        TypeDeclaration totd = (TypeDeclaration) type.getDeclaration().getContainer();
                        ProducedType tqts = tqt.getSupertypeInternal(totd);
                        TypeDeclaration otd = (TypeDeclaration) getDeclaration().getContainer();
                        ProducedType qts = qt.getSupertypeInternal(otd);
                        if ( !qts.isExactlyInternal(tqts) ) {
                            return false;
                        }
                    }
                }
                for (TypeParameter p: getDeclaration().getTypeParameters()) {
                    ProducedType arg = getTypeArguments().get(p);
                    ProducedType otherArg = type.getTypeArguments().get(p);
                    if (arg==null || otherArg==null) {
                        return false;
                        /*throw new RuntimeException(
                                "Missing type argument for: " +
                                        p.getName() + " of " +
                                        getDeclaration().getName());*/
                    }
                    else if (!arg.isExactlyInternal(otherArg)) {
                        return false;
                    }
                }
                return true;
            }
        }
    }

    /**
     * Is this type a supertype of the given type? 
     */
    public boolean isSupertypeOf(ProducedType type) {
        return type.isSubtypeOf(this);
    }

    /**
     * Is this type a subtype of the given type? 
     */
    public boolean isSubtypeOf(ProducedType type) {
        return type!=null && resolveAliases()
                .isSubtypeOfInternal(type.resolveAliases());
    }

    /**
     * Is this type a subtype of the given type? Ignore
     * a certain self type constraint.
     */
    public boolean isSubtypeOfInternal(ProducedType type) {
        if (depth.get()>30) {
            throw new RuntimeException("undecidable subtyping");
        }
        depth.set(depth.get()+1);
        try {
        if (isNothing()) {
            return true;
        }
        else if (type.isNothing()) {
            return false;
        }
        else if (getDeclaration() instanceof UnionType) {
            for (ProducedType ct: getInternalCaseTypes()) {
                if (ct==null || !ct.isSubtypeOfInternal(type)) {
                    return false;
                }
            }
            return true;
        }
        else if (type.getDeclaration() instanceof UnionType) {
            for (ProducedType ct: type.getInternalCaseTypes()) {
                if (ct!=null && isSubtypeOfInternal(ct)) {
                    return true;
                }
            }
            return false;
        }
        else if (type.getDeclaration() instanceof IntersectionType) {
            for (ProducedType ct: type.getInternalSatisfiedTypes()) {
                if (ct!=null && !isSubtypeOfInternal(ct)) {
                    return false;
                }
            }
            return true;
        }
        else if (getDeclaration() instanceof IntersectionType) {
        	if (type.getDeclaration() instanceof ClassOrInterface) {
        		ProducedType pst = getSupertypeInternal(type.getDeclaration());
        		if (pst!=null && pst.isSubtypeOfInternal(type)) {
        			return true;
        		}
        	}
            for (ProducedType ct: getInternalSatisfiedTypes()) {
                if (ct==null || ct.isSubtypeOfInternal(type)) {
                    return true;
                }
            }
            return false;
        }
        else {
            ProducedType st = getSupertypeInternal(type.getDeclaration());
            if (st==null) {
                return false;
            }
            else {
                st = st.resolveAliases();
                ProducedType stqt = st.getDeclaration().isStaticallyImportable() ?
                        null : st.getQualifyingType();
                ProducedType tqt = type.getDeclaration().isStaticallyImportable() ? 
                        null : type.getQualifyingType();
                if (stqt==null) {
                    if (tqt!=null) {
                        //probably extraneous!
                        return false;
                    }
                }
                else {
                    if (tqt==null) {
                        //probably extraneous!
                        return false;
                    }
                    else {
                        //note that the qualifying type of the
                        //given type may be an invariant subtype
                        //of the type that declares the member
                        //type, as long as it doesn't refine the
                        //member type
                        TypeDeclaration totd = (TypeDeclaration) type.getDeclaration().getContainer();
                        ProducedType tqts = tqt.getSupertypeInternal(totd);
                        if (!stqt.isSubtypeOf(tqts)) {
                            return false;
                        }
                    }
                }
                for (TypeParameter p: type.getDeclaration().getTypeParameters()) {
                    ProducedType arg = st.getTypeArguments().get(p);
                    ProducedType otherArg = type.getTypeArguments().get(p);
                    if (arg==null || otherArg==null) {
                        /*throw new RuntimeException("Missing type argument for type parameter: " +
                                      p.getName() + " of " +
                                      type.getDeclaration().getName());*/
                        return false;
                    }
                    else if (p.isCovariant()) {
                        if (!arg.isSubtypeOfInternal(otherArg)) {
                            return false;
                        }
                    }
                    else if (p.isContravariant()) {
                        if (!otherArg.isSubtypeOfInternal(arg)) {
                            return false;
                        }
                    }
                    else {
                        if (!arg.isExactlyInternal(otherArg)) {
                            return false;
                        }
                    }
                }
                return true;
            }
        }
        }
        finally { depth.set(depth.get()-1); }
    }

    /**
     * Eliminate the given type from the union type.
     * (Performs a set complement operation.) Note
     * that this operation is not robust and only 
     * works if this is a union of the given type
     * with some other types that don't involve the
     * given type.
     */
    public ProducedType minus(ProducedType pt) {
        //canonicalize and then remove the type
        //from the resulting union
        return resolveAliases().minusInternal(pt.resolveAliases());
    }
    
    /**
     * Eliminates unioned Null from a type in a
     * very special way that the backend prefers
     */
    public ProducedType eliminateNull() {
        TypeDeclaration dec = getDeclaration();
        Unit unit = dec.getUnit();
        Class nd = unit.getNullDeclaration();
        if (getSupertype(nd)!=null) {
            return unit.getNothingDeclaration().getType();
        }
        else if (dec instanceof UnionType) {
            List<ProducedType> caseTypes = getCaseTypes();
            List<ProducedType> types = new ArrayList<ProducedType>(caseTypes.size());
            for (ProducedType ct: caseTypes) {
//                if (ct.getSupertype(nd)==null) {
                    addToUnion(types, ct.eliminateNull());
//                }
            }
            UnionType ut = new UnionType(unit);
            ut.setCaseTypes(types);
            return ut.getType();
        }
        else {
            return this;
        }
    }
    
    private ProducedType minusInternal(ProducedType pt) {
        Unit unit = getDeclaration().getUnit();
        if (pt.coversInternal(this)) { //note: coversInternal() already calls getUnionOfCases()
            return unit.getNothingDeclaration().getType();
        }
        else {
            ProducedType ucts = getUnionOfCases();
            if (ucts.getDeclaration() instanceof UnionType) {
                List<ProducedType> cts = ucts.getCaseTypes();
                List<ProducedType> types = new ArrayList<ProducedType>(cts.size());
                for (ProducedType ct: cts) {
                    addToUnion(types, ct.minus(pt));
                }
                UnionType ut = new UnionType(unit);
                ut.setCaseTypes(types);
                return ut.getType();
            }
            else {
                return this;
            }
        }
    }

    /**
     * Substitute the given types for the corresponding
     * given type parameters wherever they appear in the
     * type. 
     */
    public ProducedType substitute(Map<TypeParameter, ProducedType> substitutions) {
        return new Substitution().substitute(this, substitutions).simple();
    }

    private ProducedType substituteInternal(Map<TypeParameter, ProducedType> substitutions) {
        return new InternalSubstitution().substitute(this, substitutions);
    }

    /**
     * A member or member type of the type with actual type 
     * arguments to the receiving type and invocation.
     */
    public ProducedReference getTypedReference(Declaration member, 
            List<ProducedType> typeArguments) {
        if (member instanceof TypeDeclaration) {
            return getTypeMember( (TypeDeclaration) member, typeArguments );
        }
        else {
            return getTypedMember( (TypedDeclaration) member, typeArguments);
        }
    }

    /**
     * A member of the type with actual type arguments
     * to the receiving type and invocation.
     * 
     * @param member the declaration of a member of
     *               this type
     * @param typeArguments the type arguments of the
     *                      invocation
     */
    public ProducedTypedReference getTypedMember(TypedDeclaration member, 
            List<ProducedType> typeArguments) {
        ProducedType declaringType = getSupertype((TypeDeclaration) member.getContainer());
        /*if (declaringType==null) {
            return null;
        }
        else {*/
        ProducedTypedReference ptr = new ProducedTypedReference();
        ptr.setDeclaration(member);
        ptr.setQualifyingType(declaringType);
        Map<TypeParameter, ProducedType> map = arguments(member, declaringType, typeArguments);
        //map.putAll(sub(map));
        ptr.setTypeArguments(map);
        return ptr;
        //}
    }

    /**
     * A member type of the type with actual type arguments
     * to the receiving type and invocation.
     * 
     * @param member the declaration of a member type of
     *               this type
     * @param typeArguments the type arguments of the
     *                      invocation
     */
    public ProducedType getTypeMember(TypeDeclaration member, 
            List<ProducedType> typeArguments) {
        ProducedType declaringType = getSupertype((TypeDeclaration) member.getContainer());
    	return member.getProducedType(declaringType, typeArguments);
        /*ProducedType pt = new ProducedType();
        pt.setDeclaration(member);
        pt.setQualifyingType(declaringType);
        Map<TypeParameter, ProducedType> map = arguments(member, declaringType, typeArguments);
        //map.putAll(sub(map));
        pt.setTypeArguments(map);
        return pt;*/
    }

    /**
     * Substitute invocation type arguments into an upper bound 
     * on a type parameter of the invocation, where this type 
     * represents an upper bound.
     * 
     * @param receiver the type that receives the invocation
     * @param member the invoked member
     * @param typeArguments the explicit or inferred type 
     *                      arguments of the invocation
     * 
     * @return the upper bound of a type parameter, after 
     *         performing all type argument substitution
     */
    public ProducedType getProducedType(ProducedType receiver, Declaration member, 
            List<ProducedType> typeArguments) {
        ProducedType rst = (receiver==null) ? null : 
                receiver.getSupertype((TypeDeclaration) member.getContainer());
        return new Substitution().substitute(this, arguments(member, rst, typeArguments));
    }

    public ProducedType getType() {
        return this;
    }
    
    /**
     * Get all supertypes of the type by traversing the whole
     * type hierarchy. Avoid using this!
     */
    public List<ProducedType> getSupertypes() {
        return getSupertypes(new ArrayList<ProducedType>());
    }
    
    private List<ProducedType> getSupertypes(List<ProducedType> list) {
        if ( isWellDefined() && (getDeclaration() instanceof UnionType || 
                                 getDeclaration() instanceof IntersectionType || 
                                 addToSupertypes(list, this)) ) {
            ProducedType extendedType = getExtendedType();
            if (extendedType!=null) {
                extendedType.getSupertypes(list);
            }
            for (ProducedType dst: getSatisfiedTypes()) {
                dst.getSupertypes(list);
            }
            if (getDeclaration() instanceof UnionType) {
                //trying to infer supertypes of algebraic
                //types from their cases was resulting in
                //stack overflows and is not currently 
                //required by the spec
                List<ProducedType> caseTypes = getCaseTypes();
                if (caseTypes!=null) {
                    for (ProducedType t: caseTypes) {
                    	if (!alreadyInList(list, t)) {
                    		List<ProducedType> candidates = t.getSupertypes();
                    		for (ProducedType st: candidates) {
                    			boolean include = true;
                    			for (ProducedType ct: getDeclaration().getCaseTypes()) {
                    				if (!ct.isSubtypeOf(st)) {
                    					include = false;
                    					break;
                    				}
                    			}
                    			if (include) {
                    				addToSupertypes(list, st);
                    			}
                    		}
                    	}
                    }
                }
            }
        }
        return list;
    }

	private boolean alreadyInList(List<ProducedType> list, ProducedType t) {
		for (ProducedType pt: list) {
			if (t.getDeclaration() instanceof UnionType ||
				t.getDeclaration() instanceof IntersectionType ||
				(t.getDeclaration().equals(pt.getDeclaration()) && 
					t.isExactlyInternal(pt))) {
				return true;
			}
		}
		return false;
	}
    
    /**
     * Given a type declaration, return a produced type of 
     * which this type is an invariant subtype.
     * 
     * @param dec a type declaration
     * 
     * @return a produced type of the given type declaration
     *         which is a supertype of this type, or null if
     *         there is no such supertype
     */
    public ProducedType getSupertype(TypeDeclaration dec) {
        //TODO: do I need to call resolveAliases() here?
        return /*resolveAliases().*/getSupertypeInternal(dec);
    }
    
    private ProducedType getSupertypeInternal(TypeDeclaration dec) {
        boolean complexType = dec instanceof UnionType 
        		|| dec instanceof IntersectionType;
        ProducedTypeCache cache = dec.getUnit().getCache();
        if (!complexType 
                && cache.containsKey(this, dec)
//                && superTypesCache.containsKey(dec)
                ) {
            /*SoftReference<ProducedType> ref = superTypesCache.get(dec);
            if (ref==null) return null;
            ProducedType pt = ref.get();
            if (pt!=null) return pt;*/
            return cache.get(this, dec);
//            return superTypesCache.get(dec);
        }
        SupertypeCheck check = checkSupertype(getDeclaration(), dec);
        ProducedType superType;
        if(check == SupertypeCheck.NO){
            superType = null;
        }else if(check == SupertypeCheck.YES 
                && dec instanceof ClassOrInterface
                && dec.getTypeParameters().isEmpty()){
            superType = dec.getType();
        }else{
            superType = getSupertype(new SupertypeCriteria(dec));
        }
        if (!complexType) {
            cache.put(this, dec, superType);
//            superTypesCache.put(dec, superType);
        }
        //if (!complexType) superTypesCache.put(dec, superType==null?null:new SoftReference<ProducedType>(superType));
        return superType;
    }
    
    enum SupertypeCheck {
        YES, NO, MAYBE;
    }
    private static SupertypeCheck checkSupertype(TypeDeclaration declaration, TypeDeclaration supertype) {
        // fail-fast: there are only two classes that can be supertypes of an interface
        if(declaration instanceof Interface 
                && supertype instanceof Class){
            String supertypeName = supertype.getQualifiedNameString();
            if(supertypeName.equals("ceylon.language::Object")
               || supertypeName.equals("ceylon.language::Anything"))
                return SupertypeCheck.YES;
            return SupertypeCheck.NO;
        }<commit_msg>Optim: ProducedType.getSuperType: only do quick type for toplevels<commit_after>package com.redhat.ceylon.compiler.typechecker.model;

import static com.redhat.ceylon.compiler.typechecker.model.Util.addToIntersection;
import static com.redhat.ceylon.compiler.typechecker.model.Util.addToSupertypes;
import static com.redhat.ceylon.compiler.typechecker.model.Util.addToUnion;
import static com.redhat.ceylon.compiler.typechecker.model.Util.arguments;
import static com.redhat.ceylon.compiler.typechecker.model.Util.principalInstantiation;
import static java.util.Collections.emptyList;
import static java.util.Collections.singletonList;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

import com.redhat.ceylon.compiler.typechecker.context.ProducedTypeCache;
import com.redhat.ceylon.compiler.typechecker.util.ProducedTypeNamePrinter;


/**
 * A produced type with actual type arguments.
 * This represents something that is actually
 * considered a "type" in the language
 * specification.
 *
 * @author <NAME>
 */
public class ProducedType extends ProducedReference {
    
    private String underlyingType;
    private boolean isRaw;
    private ProducedType resolvedAliases;
//    private Map<TypeDeclaration, ProducedType> superTypesCache = 
//            new HashMap<TypeDeclaration, ProducedType>(5);

    private int hashCode;

    public int getHashCode(){
        if(hashCode == 0){
            int ret = 17;
            ProducedType qualifyingType = getQualifyingType();
            ret = (37 * ret) + (qualifyingType != null ? qualifyingType.hashCode() : 0);
            TypeDeclaration declaration = getDeclaration();
            ret = (37 * ret) + declaration.hashCodeForCache();
            
            Map<TypeParameter, ProducedType> typeArguments = getTypeArguments();

            if(!typeArguments.isEmpty()){
                List<TypeParameter> typeParameters = declaration.getTypeParameters();
                for(int i=0,l=typeParameters.size();i<l;i++){
                    TypeParameter typeParameter = typeParameters.get(i);
                    ProducedType typeArgument = typeArguments.get(typeParameter);
                    ret = (37 * ret) + (typeArgument != null ? typeArgument.hashCode() : 0);
                }
            }
            hashCode = ret;
        }
        return hashCode;
    }

    ProducedType() {}

    @Override
    public TypeDeclaration getDeclaration() {
        return (TypeDeclaration) super.getDeclaration();
    }
    
    /**
     * Is this type exactly the same type as the
     * given type? 
     */
    public boolean isExactly(ProducedType type) {
        return resolveAliases().isExactlyInternal(type.resolveAliases());
    }
    
    public boolean isExactlyInternal(ProducedType type) {
        if (getDeclaration() instanceof NothingType) {
            return type.isNothing();
        }
        else if (getDeclaration() instanceof UnionType) {
            List<ProducedType> cases = getCaseTypes();
            if (type.getDeclaration() instanceof UnionType) {
                List<ProducedType> otherCases = type.getCaseTypes();
                if (cases.size()!=otherCases.size()) {
                    return false;
                }
                else {
                    for (ProducedType c: cases) {
                        boolean found = false;
                        for (ProducedType oc: otherCases) {
                            if (c.isExactlyInternal(oc)) {
                                found = true;
                                break;
                            }
                        }
                        if (!found) {
                            return false;
                        }
                    }
                    return true;
                }
            }
            else if (cases.size()==1) {
                ProducedType st = cases.get(0);
                return st.isExactlyInternal(type);
            }
            else {
                return false;
            }
        }
        else if (getDeclaration() instanceof IntersectionType) {
            List<ProducedType> types = getSatisfiedTypes();
            if (type.getDeclaration() instanceof IntersectionType) {
                List<ProducedType> otherTypes = type.getSatisfiedTypes();
                if (types.size()!=otherTypes.size()) {
                    return false;
                }
                else {
                    for (ProducedType c: types) {
                        boolean found = false;
                        for (ProducedType oc: otherTypes) {
                            if (c.getDeclaration().equals(oc.getDeclaration())) {
                                if (c.isExactlyInternal(oc)) {
                                    found = true;
                                    break;
                                }
                                //given a covariant type Co, and interfaces
                                //A satisfies Co<B&Co<A>> and 
                                //B satisfies Co<A&Co<B>>, then
                                //A&Co<B> is equivalent A&Co<B&Co<A>> as a 
                                //consequence of principal instantiation 
                                //inheritance
                                ProducedType cst = getSupertypeInternal(c.getDeclaration());
                                ProducedType ocst = type.getSupertypeInternal(oc.getDeclaration());
                                if (cst.isExactlyInternal(ocst)) {
                                    found = true;
                                    break;
                                }
                            }
                        }
                        if (!found) {
                            return false;
                        }
                    }
                    return true;
                }
            }
            else if (types.size()==1) {
                ProducedType st = types.get(0);
                return st.isExactlyInternal(type);
            }
            else {
                return false;
            }
        }
        else if (type.getDeclaration() instanceof UnionType) {
            List<ProducedType> otherCases = type.getCaseTypes();
            if (otherCases.size()==1) {
                ProducedType st = otherCases.get(0);
                return this.isExactlyInternal(st);
            }
            else {
                return false;
            }
        }
        else if (type.getDeclaration() instanceof IntersectionType) {
            List<ProducedType> otherTypes = type.getSatisfiedTypes();
            if (otherTypes.size()==1) {
                ProducedType st = otherTypes.get(0);
                return this.isExactlyInternal(st);
            }
            else {
                return false;
            }
        }
        else {
            if (!type.getDeclaration().equals(getDeclaration())) {
                return false;
            }
            else {
                ProducedType qt = getDeclaration().isStaticallyImportable() ?
                        null : getQualifyingType();
                ProducedType tqt = type.getDeclaration().isStaticallyImportable() ? 
                        null : type.getQualifyingType();
                if (qt==null) {
                    if (tqt!=null) {
                        return false;
                    }
                }
                else {
                    if (tqt==null) {
                        return false;
                    }
                    else {
                        TypeDeclaration totd = (TypeDeclaration) type.getDeclaration().getContainer();
                        ProducedType tqts = tqt.getSupertypeInternal(totd);
                        TypeDeclaration otd = (TypeDeclaration) getDeclaration().getContainer();
                        ProducedType qts = qt.getSupertypeInternal(otd);
                        if ( !qts.isExactlyInternal(tqts) ) {
                            return false;
                        }
                    }
                }
                for (TypeParameter p: getDeclaration().getTypeParameters()) {
                    ProducedType arg = getTypeArguments().get(p);
                    ProducedType otherArg = type.getTypeArguments().get(p);
                    if (arg==null || otherArg==null) {
                        return false;
                        /*throw new RuntimeException(
                                "Missing type argument for: " +
                                        p.getName() + " of " +
                                        getDeclaration().getName());*/
                    }
                    else if (!arg.isExactlyInternal(otherArg)) {
                        return false;
                    }
                }
                return true;
            }
        }
    }

    /**
     * Is this type a supertype of the given type? 
     */
    public boolean isSupertypeOf(ProducedType type) {
        return type.isSubtypeOf(this);
    }

    /**
     * Is this type a subtype of the given type? 
     */
    public boolean isSubtypeOf(ProducedType type) {
        return type!=null && resolveAliases()
                .isSubtypeOfInternal(type.resolveAliases());
    }

    /**
     * Is this type a subtype of the given type? Ignore
     * a certain self type constraint.
     */
    public boolean isSubtypeOfInternal(ProducedType type) {
        if (depth.get()>30) {
            throw new RuntimeException("undecidable subtyping");
        }
        depth.set(depth.get()+1);
        try {
        if (isNothing()) {
            return true;
        }
        else if (type.isNothing()) {
            return false;
        }
        else if (getDeclaration() instanceof UnionType) {
            for (ProducedType ct: getInternalCaseTypes()) {
                if (ct==null || !ct.isSubtypeOfInternal(type)) {
                    return false;
                }
            }
            return true;
        }
        else if (type.getDeclaration() instanceof UnionType) {
            for (ProducedType ct: type.getInternalCaseTypes()) {
                if (ct!=null && isSubtypeOfInternal(ct)) {
                    return true;
                }
            }
            return false;
        }
        else if (type.getDeclaration() instanceof IntersectionType) {
            for (ProducedType ct: type.getInternalSatisfiedTypes()) {
                if (ct!=null && !isSubtypeOfInternal(ct)) {
                    return false;
                }
            }
            return true;
        }
        else if (getDeclaration() instanceof IntersectionType) {
        	if (type.getDeclaration() instanceof ClassOrInterface) {
        		ProducedType pst = getSupertypeInternal(type.getDeclaration());
        		if (pst!=null && pst.isSubtypeOfInternal(type)) {
        			return true;
        		}
        	}
            for (ProducedType ct: getInternalSatisfiedTypes()) {
                if (ct==null || ct.isSubtypeOfInternal(type)) {
                    return true;
                }
            }
            return false;
        }
        else {
            ProducedType st = getSupertypeInternal(type.getDeclaration());
            if (st==null) {
                return false;
            }
            else {
                st = st.resolveAliases();
                ProducedType stqt = st.getDeclaration().isStaticallyImportable() ?
                        null : st.getQualifyingType();
                ProducedType tqt = type.getDeclaration().isStaticallyImportable() ? 
                        null : type.getQualifyingType();
                if (stqt==null) {
                    if (tqt!=null) {
                        //probably extraneous!
                        return false;
                    }
                }
                else {
                    if (tqt==null) {
                        //probably extraneous!
                        return false;
                    }
                    else {
                        //note that the qualifying type of the
                        //given type may be an invariant subtype
                        //of the type that declares the member
                        //type, as long as it doesn't refine the
                        //member type
                        TypeDeclaration totd = (TypeDeclaration) type.getDeclaration().getContainer();
                        ProducedType tqts = tqt.getSupertypeInternal(totd);
                        if (!stqt.isSubtypeOf(tqts)) {
                            return false;
                        }
                    }
                }
                for (TypeParameter p: type.getDeclaration().getTypeParameters()) {
                    ProducedType arg = st.getTypeArguments().get(p);
                    ProducedType otherArg = type.getTypeArguments().get(p);
                    if (arg==null || otherArg==null) {
                        /*throw new RuntimeException("Missing type argument for type parameter: " +
                                      p.getName() + " of " +
                                      type.getDeclaration().getName());*/
                        return false;
                    }
                    else if (p.isCovariant()) {
                        if (!arg.isSubtypeOfInternal(otherArg)) {
                            return false;
                        }
                    }
                    else if (p.isContravariant()) {
                        if (!otherArg.isSubtypeOfInternal(arg)) {
                            return false;
                        }
                    }
                    else {
                        if (!arg.isExactlyInternal(otherArg)) {
                            return false;
                        }
                    }
                }
                return true;
            }
        }
        }
        finally { depth.set(depth.get()-1); }
    }

    /**
     * Eliminate the given type from the union type.
     * (Performs a set complement operation.) Note
     * that this operation is not robust and only 
     * works if this is a union of the given type
     * with some other types that don't involve the
     * given type.
     */
    public ProducedType minus(ProducedType pt) {
        //canonicalize and then remove the type
        //from the resulting union
        return resolveAliases().minusInternal(pt.resolveAliases());
    }
    
    /**
     * Eliminates unioned Null from a type in a
     * very special way that the backend prefers
     */
    public ProducedType eliminateNull() {
        TypeDeclaration dec = getDeclaration();
        Unit unit = dec.getUnit();
        Class nd = unit.getNullDeclaration();
        if (getSupertype(nd)!=null) {
            return unit.getNothingDeclaration().getType();
        }
        else if (dec instanceof UnionType) {
            List<ProducedType> caseTypes = getCaseTypes();
            List<ProducedType> types = new ArrayList<ProducedType>(caseTypes.size());
            for (ProducedType ct: caseTypes) {
//                if (ct.getSupertype(nd)==null) {
                    addToUnion(types, ct.eliminateNull());
//                }
            }
            UnionType ut = new UnionType(unit);
            ut.setCaseTypes(types);
            return ut.getType();
        }
        else {
            return this;
        }
    }
    
    private ProducedType minusInternal(ProducedType pt) {
        Unit unit = getDeclaration().getUnit();
        if (pt.coversInternal(this)) { //note: coversInternal() already calls getUnionOfCases()
            return unit.getNothingDeclaration().getType();
        }
        else {
            ProducedType ucts = getUnionOfCases();
            if (ucts.getDeclaration() instanceof UnionType) {
                List<ProducedType> cts = ucts.getCaseTypes();
                List<ProducedType> types = new ArrayList<ProducedType>(cts.size());
                for (ProducedType ct: cts) {
                    addToUnion(types, ct.minus(pt));
                }
                UnionType ut = new UnionType(unit);
                ut.setCaseTypes(types);
                return ut.getType();
            }
            else {
                return this;
            }
        }
    }

    /**
     * Substitute the given types for the corresponding
     * given type parameters wherever they appear in the
     * type. 
     */
    public ProducedType substitute(Map<TypeParameter, ProducedType> substitutions) {
        return new Substitution().substitute(this, substitutions).simple();
    }

    private ProducedType substituteInternal(Map<TypeParameter, ProducedType> substitutions) {
        return new InternalSubstitution().substitute(this, substitutions);
    }

    /**
     * A member or member type of the type with actual type 
     * arguments to the receiving type and invocation.
     */
    public ProducedReference getTypedReference(Declaration member, 
            List<ProducedType> typeArguments) {
        if (member instanceof TypeDeclaration) {
            return getTypeMember( (TypeDeclaration) member, typeArguments );
        }
        else {
            return getTypedMember( (TypedDeclaration) member, typeArguments);
        }
    }

    /**
     * A member of the type with actual type arguments
     * to the receiving type and invocation.
     * 
     * @param member the declaration of a member of
     *               this type
     * @param typeArguments the type arguments of the
     *                      invocation
     */
    public ProducedTypedReference getTypedMember(TypedDeclaration member, 
            List<ProducedType> typeArguments) {
        ProducedType declaringType = getSupertype((TypeDeclaration) member.getContainer());
        /*if (declaringType==null) {
            return null;
        }
        else {*/
        ProducedTypedReference ptr = new ProducedTypedReference();
        ptr.setDeclaration(member);
        ptr.setQualifyingType(declaringType);
        Map<TypeParameter, ProducedType> map = arguments(member, declaringType, typeArguments);
        //map.putAll(sub(map));
        ptr.setTypeArguments(map);
        return ptr;
        //}
    }

    /**
     * A member type of the type with actual type arguments
     * to the receiving type and invocation.
     * 
     * @param member the declaration of a member type of
     *               this type
     * @param typeArguments the type arguments of the
     *                      invocation
     */
    public ProducedType getTypeMember(TypeDeclaration member, 
            List<ProducedType> typeArguments) {
        ProducedType declaringType = getSupertype((TypeDeclaration) member.getContainer());
    	return member.getProducedType(declaringType, typeArguments);
        /*ProducedType pt = new ProducedType();
        pt.setDeclaration(member);
        pt.setQualifyingType(declaringType);
        Map<TypeParameter, ProducedType> map = arguments(member, declaringType, typeArguments);
        //map.putAll(sub(map));
        pt.setTypeArguments(map);
        return pt;*/
    }

    /**
     * Substitute invocation type arguments into an upper bound 
     * on a type parameter of the invocation, where this type 
     * represents an upper bound.
     * 
     * @param receiver the type that receives the invocation
     * @param member the invoked member
     * @param typeArguments the explicit or inferred type 
     *                      arguments of the invocation
     * 
     * @return the upper bound of a type parameter, after 
     *         performing all type argument substitution
     */
    public ProducedType getProducedType(ProducedType receiver, Declaration member, 
            List<ProducedType> typeArguments) {
        ProducedType rst = (receiver==null) ? null : 
                receiver.getSupertype((TypeDeclaration) member.getContainer());
        return new Substitution().substitute(this, arguments(member, rst, typeArguments));
    }

    public ProducedType getType() {
        return this;
    }
    
    /**
     * Get all supertypes of the type by traversing the whole
     * type hierarchy. Avoid using this!
     */
    public List<ProducedType> getSupertypes() {
        return getSupertypes(new ArrayList<ProducedType>());
    }
    
    private List<ProducedType> getSupertypes(List<ProducedType> list) {
        if ( isWellDefined() && (getDeclaration() instanceof UnionType || 
                                 getDeclaration() instanceof IntersectionType || 
                                 addToSupertypes(list, this)) ) {
            ProducedType extendedType = getExtendedType();
            if (extendedType!=null) {
                extendedType.getSupertypes(list);
            }
            for (ProducedType dst: getSatisfiedTypes()) {
                dst.getSupertypes(list);
            }
            if (getDeclaration() instanceof UnionType) {
                //trying to infer supertypes of algebraic
                //types from their cases was resulting in
                //stack overflows and is not currently 
                //required by the spec
                List<ProducedType> caseTypes = getCaseTypes();
                if (caseTypes!=null) {
                    for (ProducedType t: caseTypes) {
                    	if (!alreadyInList(list, t)) {
                    		List<ProducedType> candidates = t.getSupertypes();
                    		for (ProducedType st: candidates) {
                    			boolean include = true;
                    			for (ProducedType ct: getDeclaration().getCaseTypes()) {
                    				if (!ct.isSubtypeOf(st)) {
                    					include = false;
                    					break;
                    				}
                    			}
                    			if (include) {
                    				addToSupertypes(list, st);
                    			}
                    		}
                    	}
                    }
                }
            }
        }
        return list;
    }

	private boolean alreadyInList(List<ProducedType> list, ProducedType t) {
		for (ProducedType pt: list) {
			if (t.getDeclaration() instanceof UnionType ||
				t.getDeclaration() instanceof IntersectionType ||
				(t.getDeclaration().equals(pt.getDeclaration()) && 
					t.isExactlyInternal(pt))) {
				return true;
			}
		}
		return false;
	}
    
    /**
     * Given a type declaration, return a produced type of 
     * which this type is an invariant subtype.
     * 
     * @param dec a type declaration
     * 
     * @return a produced type of the given type declaration
     *         which is a supertype of this type, or null if
     *         there is no such supertype
     */
    public ProducedType getSupertype(TypeDeclaration dec) {
        //TODO: do I need to call resolveAliases() here?
        return /*resolveAliases().*/getSupertypeInternal(dec);
    }
    
    private ProducedType getSupertypeInternal(TypeDeclaration dec) {
        boolean complexType = dec instanceof UnionType 
        		|| dec instanceof IntersectionType;
        ProducedTypeCache cache = dec.getUnit().getCache();
        if (!complexType 
                && cache.containsKey(this, dec)
//                && superTypesCache.containsKey(dec)
                ) {
            /*SoftReference<ProducedType> ref = superTypesCache.get(dec);
            if (ref==null) return null;
            ProducedType pt = ref.get();
            if (pt!=null) return pt;*/
            return cache.get(this, dec);
//            return superTypesCache.get(dec);
        }
        SupertypeCheck check = checkSupertype(getDeclaration(), dec);
        ProducedType superType;
        if(check == SupertypeCheck.NO){
            superType = null;
        }else if(check == SupertypeCheck.YES 
                && dec instanceof ClassOrInterface
                && dec.isToplevel()
                && dec.getTypeParameters().isEmpty()){
            superType = dec.getType();
        }else{
            superType = getSupertype(new SupertypeCriteria(dec));
        }
        if (!complexType) {
            cache.put(this, dec, superType);
//            superTypesCache.put(dec, superType);
        }
        //if (!complexType) superTypesCache.put(dec, superType==null?null:new SoftReference<ProducedType>(superType));
        return superType;
    }
    
    enum SupertypeCheck {
        YES, NO, MAYBE;
    }
    private static SupertypeCheck checkSupertype(TypeDeclaration declaration, TypeDeclaration supertype) {
        // fail-fast: there are only two classes that can be supertypes of an interface
        if(declaration instanceof Interface 
                && supertype instanceof Class){
            String supertypeName = supertype.getQualifiedNameString();
            if(supertypeName.equals("ceylon.language::Object")
               || supertypeName.equals("ceylon.language::Anything"))
                return SupertypeCheck.YES;
            return SupertypeCheck.NO;
        }
{'fraction_non_alphanumeric': 0.08769662139320301, 'fraction_numerical': 0.0009942927595601248, 'mean_word_length': 1.4504434265666115, 'pattern_counts': {'":': 0, '<': 87, '<?xml version=': 0, '>': 87, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5527608', 'n_tokens_mistral': 12603, 'n_tokens_neox': 11820, 'n_words': 2942}