include/swift/AST/ArchetypeBuilder.h

//===--- ArchetypeBuilder.h - Generic Archetype Builder ---------*- C++ -*-===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See http://swift.org/LICENSE.txt for license information
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
//
// Support for collecting a set of generic requirements, both explicitly stated
// and inferred, and computing the archetypes and required witness tables from
// those requirements.
//
//===----------------------------------------------------------------------===//

#ifndef SWIFT_ARCHETYPEBUILDER_H
#define SWIFT_ARCHETYPEBUILDER_H

#include "swift/AST/Identifier.h"
#include "swift/AST/Types.h"
#include "swift/AST/TypeLoc.h"
#include "swift/Basic/LLVM.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/PointerUnion.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/TinyPtrVector.h"
#include <functional>
#include <memory>

namespace swift {

class AbstractTypeParamDecl;
class ArchetypeType;
class AssociatedTypeDecl;
class DeclContext;
class DependentMemberType;
class GenericParamList;
class GenericSignature;
class GenericTypeParamDecl;
class GenericTypeParamType;
class LazyResolver;
class ModuleDecl;
class Pattern;
class ProtocolConformance;
class ProtocolDecl;
class Requirement;
class RequirementRepr;
class SILModule;
class SourceLoc;
class Type;
class TypeRepr;
class ASTContext;
class DiagnosticEngine;

/// Describes how a requirement was determined.
class RequirementSource {
public:
  enum Kind : unsigned char {
    /// The requirement was explicitly stated in the generic parameter
    /// clause.
    Explicit,
    /// The requirement was inferred from the function's parameter or
    /// result types.
    Inferred,

    /// The requirement was part of a protocol requirement on an
    /// associated type.
    ///
    /// These are dropped when building the GenericSignature.
    Protocol,

    /// The requirement is redundant with some other requirement.
    ///
    /// These are dropped when building the GenericSignature.
    Redundant,

    /// The requirement came from an outer scope.
    /// FIXME: eliminate this in favor of keeping requirement sources in 
    /// GenericSignatures, at least non-canonical ones?
    OuterScope,
  };

  RequirementSource(Kind kind, SourceLoc loc) : StoredKind(kind), Loc(loc) { }

  /// Retrieve the kind of requirement source.
  Kind getKind() const { return StoredKind; }

  /// Set the kind of the requirement source.
  void setKind(Kind kind) { StoredKind = kind; }

  /// Retrieve the source location at which the requirement originated.
  SourceLoc getLoc() const { return Loc; }

  LLVM_ATTRIBUTE_DEPRECATED(
      void dump(SourceManager *srcMgr) const,
      "only for use within the debugger");

  /// Dump the requirement source.
  void dump(llvm::raw_ostream &out, SourceManager *srcMgr) const;

private:
  Kind StoredKind;
  SourceLoc Loc;
};

/// \brief Collects a set of requirements of generic parameters, both explicitly
/// stated and inferred, and determines the set of archetypes for each of
/// the generic parameters.
class ArchetypeBuilder {
public:
  /// Describes a potential archetype, which stands in for a generic parameter
  /// type or some type derived from it.
  class PotentialArchetype;

private:
  class InferRequirementsWalker;
  friend class InferRequirementsWalker;

  ModuleDecl &Mod;
  ASTContext &Context;
  DiagnosticEngine &Diags;
  struct Implementation;
  std::unique_ptr<Implementation> Impl;

  ArchetypeBuilder(const ArchetypeBuilder &) = delete;
  ArchetypeBuilder &operator=(const ArchetypeBuilder &) = delete;

  /// \brief Add a new conformance requirement specifying that the given
  /// potential archetype conforms to the given protocol.
  bool addConformanceRequirement(PotentialArchetype *T,
                                 ProtocolDecl *Proto,
                                 RequirementSource Source);

  bool addConformanceRequirement(PotentialArchetype *T,
                                 ProtocolDecl *Proto,
                                 RequirementSource Source,
                                llvm::SmallPtrSetImpl<ProtocolDecl *> &Visited);

public:
  /// \brief Add a new conformance requirement specifying that the given
  /// potential archetypes are equivalent.
  bool addSameTypeRequirementBetweenArchetypes(PotentialArchetype *T1,
                                               PotentialArchetype *T2,
                                               RequirementSource Source);
  
  /// \brief Add a new conformance requirement specifying that the given
  /// potential archetype is bound to a concrete type.
  bool addSameTypeRequirementToConcrete(PotentialArchetype *T,
                                        Type Concrete,
                                        RequirementSource Source);

private:
  /// \brief Add a new superclass requirement specifying that the given
  /// potential archetype has the given type as an ancestor.
  bool addSuperclassRequirement(PotentialArchetype *T, 
                                Type Superclass,
                                RequirementSource Source);

  /// \brief Add a new same-type requirement specifying that the given potential
  /// archetypes should map to the equivalent archetype.
  bool addSameTypeRequirement(Type T1, Type T2, RequirementSource Source);

  /// Add the requirements placed on the given abstract type parameter
  /// to the given potential archetype.
  bool addAbstractTypeParamRequirements(
         AbstractTypeParamDecl *decl,
         PotentialArchetype *pa,
         RequirementSource::Kind kind,
         llvm::SmallPtrSetImpl<ProtocolDecl *> &visited);

  /// Visit all of the types that show up in the list of inherited
  /// types.
  ///
  /// \returns true if any of the invocations of \c visitor returned true.
  bool visitInherited(ArrayRef<TypeLoc> inheritedTypes,
                      llvm::function_ref<bool(Type, SourceLoc)> visitor);

  /// Visit all of the potential archetypes.
  template<typename F>
  void visitPotentialArchetypes(F f);

public:
  /// Construct a new archetype builder.
  ///
  /// \param mod The module in which the builder will create archetypes.
  ///
  /// \param diags The diagnostics entity to use.
  ArchetypeBuilder(ModuleDecl &mod, DiagnosticEngine &diags);

  ArchetypeBuilder(ArchetypeBuilder &&);
  ~ArchetypeBuilder();

  /// Retrieve the AST context.
  ASTContext &getASTContext() const { return Context; }

  /// Retrieve the module.
  ModuleDecl &getModule() const { return Mod; }

  /// Retrieve the lazy resolver, if there is one.
  LazyResolver *getLazyResolver() const;

  /// Enumerate the requirements that describe the signature of this
  /// archetype builder.
  ///
  /// \param f A function object that will be passed each requirement
  /// and requirement source.
  void enumerateRequirements(llvm::function_ref<
                      void (RequirementKind kind,
                            PotentialArchetype *archetype,
                            llvm::PointerUnion<Type, PotentialArchetype *> type,
                            RequirementSource source)> f);
  

private:
  PotentialArchetype *addGenericParameter(GenericTypeParamType *GenericParam,
                                          ProtocolDecl *RootProtocol,
                                          Identifier ParamName);

public:
  /// \brief Add a new generic parameter for which there may be requirements.
  void addGenericParameter(GenericTypeParamDecl *GenericParam);

  /// Add the requirements placed on the given abstract type parameter
  /// to the given potential archetype.
  ///
  /// \returns true if an error occurred, false otherwise.
  bool addGenericParameterRequirements(GenericTypeParamDecl *GenericParam);

  /// \brief Add a new generic parameter for which there may be requirements.
  void addGenericParameter(GenericTypeParamType *GenericParam);
  
  /// \brief Add a new requirement.
  ///
  /// \returns true if this requirement makes the set of requirements
  /// inconsistent, in which case a diagnostic will have been issued.
  bool addRequirement(const RequirementRepr &Req);

  /// \brief Add an already-checked requirement.
  ///
  /// Adding an already-checked requirement cannot fail. This is used to
  /// re-inject requirements from outer contexts.
  void addRequirement(const Requirement &req, RequirementSource source);
  
  /// \brief Add all of a generic signature's parameters and requirements.
  ///
  /// FIXME: Requirements from the generic signature are treated as coming from
  /// an outer scope. Setting \c treatRequirementsAsExplicit to true disables
  /// this behavior.
  void addGenericSignature(GenericSignature *sig,
                           GenericEnvironment *genericEnv,
                           bool treatRequirementsAsExplicit = false);

  /// \brief Build the generic signature.
  GenericSignature *getGenericSignature();

  /// \brief Build the generic environment.
  GenericEnvironment *getGenericEnvironment();

  /// Infer requirements from the given type, recursively.
  ///
  /// This routine infers requirements from a type that occurs within the
  /// signature of a generic function. For example, given:
  ///
  /// \code
  /// func f<K, V>(dict : Dictionary<K, V>) { ... }
  /// \endcode
  ///
  /// where \c Dictionary requires that its key type be \c Hashable,
  /// the requirement \c K : Hashable is inferred from the parameter type,
  /// because the type \c Dictionary<K,V> cannot be formed without it.
  void inferRequirements(TypeLoc type, GenericParamList *genericParams);

  /// Infer requirements from the given pattern, recursively.
  ///
  /// This routine infers requirements from a type that occurs within the
  /// signature of a generic function. For example, given:
  ///
  /// \code
  /// func f<K, V>(dict : Dictionary<K, V>) { ... }
  /// \endcode
  ///
  /// where \c Dictionary requires that its key type be \c Hashable,
  /// the requirement \c K : Hashable is inferred from the parameter type,
  /// because the type \c Dictionary<K,V> cannot be formed without it.
  void inferRequirements(ParameterList *params,GenericParamList *genericParams);

  /// Finalize the set of requirements, performing any remaining checking
  /// required before generating archetypes.
  ///
  /// \param allowConcreteGenericParams If true, allow generic parameters to
  /// be made concrete.
  void finalize(SourceLoc loc, bool allowConcreteGenericParams=false);

  /// \brief Resolve the given type to the potential archetype it names.
  ///
  /// This routine will synthesize nested types as required to refer to a
  /// potential archetype, even in cases where no requirement specifies the
  /// requirement for such an archetype. FIXME: The failure to include such a
  /// requirement will be diagnosed at some point later (when the types in the
  /// signature are fully resolved).
  ///
  /// For any type that cannot refer to an archetype, this routine returns null.
  PotentialArchetype *resolveArchetype(Type type);

  /// \brief Resolve the given dependent type using our context archetypes.
  ///
  /// Given an arbitrary type, this will substitute dependent type parameters
  /// structurally with their corresponding archetypes and resolve dependent
  /// member types to the appropriate associated types.
  Type substDependentType(Type type);

  /// Map an interface type to a contextual type.
  static Type mapTypeIntoContext(const DeclContext *dc, Type type);

  /// Map an interface type to a contextual type.
  static Type mapTypeIntoContext(ModuleDecl *M,
                                 GenericEnvironment *genericEnv,
                                 Type type);

  /// Map a contextual type to an interface type.
  static Type mapTypeOutOfContext(const DeclContext *dc, Type type);

  /// Map a contextual type to an interface type.
  static Type mapTypeOutOfContext(ModuleDecl *M,
                                  GenericEnvironment *genericEnv,
                                  Type type);

  /// \brief Dump all of the requirements, both specified and inferred.
  LLVM_ATTRIBUTE_DEPRECATED(
      void dump(),
      "only for use within the debugger");

  /// Dump all of the requirements to the given output stream.
  void dump(llvm::raw_ostream &out);

  // In SILFunction.cpp:
  
  /// \brief Resolve the given dependent type using our context archetypes.
  ///
  /// Given an arbitrary type, this will substitute dependent type parameters
  /// structurally with their corresponding archetypes and resolve dependent
  /// member types to the appropriate associated types. It will reabstract
  /// dependent types according to the abstraction level of their associated
  /// type requirements.
  SILType substDependentType(SILModule &M,
                             SILType type);
};

class ArchetypeBuilder::PotentialArchetype {
  /// Either the parent of this potential archetype (for an associated
  /// type) or the generic type parameter type to which this potential
  /// archetype corresponds.
  llvm::PointerUnion<PotentialArchetype*, GenericTypeParamType*> ParentOrParam;

  /// The root protocol with which this potential archetype is associated.
  ProtocolDecl *RootProtocol = nullptr;

  /// \brief The name of this potential archetype or, for an
  /// associated type, the declaration of the associated type to which
  /// this potential archetype has been resolved. Or, for a type alias,
  /// the type alias decl.
  llvm::PointerUnion3<Identifier, AssociatedTypeDecl *,
                      TypeAliasDecl *> NameOrAssociatedType;

  /// \brief The representative of the equivalent class of potential archetypes
  /// to which this potential archetype belongs.
  PotentialArchetype *Representative;

  /// \brief The source of a same-type requirement.
  Optional<RequirementSource> SameTypeSource;

  /// \brief The superclass of this archetype, if specified.
  Type Superclass;

  /// The source of the superclass requirement.
  Optional<RequirementSource> SuperclassSource;

  /// \brief The list of protocols to which this archetype will conform.
  llvm::MapVector<ProtocolDecl *, RequirementSource> ConformsTo;

  /// \brief The set of nested types of this archetype.
  ///
  /// For a given nested type name, there may be multiple potential archetypes
  /// corresponding to different associated types (from different protocols)
  /// that share a name.
  llvm::MapVector<Identifier, llvm::TinyPtrVector<PotentialArchetype *>>
    NestedTypes;

  /// \brief The actual archetype, once it has been assigned, or the concrete
  /// type that the parameter was same-type constrained to.
  ArchetypeType::NestedType ArchetypeOrConcreteType;

  /// \brief Recursively conforms to itself.
  unsigned IsRecursive : 1;

  /// Whether this potential archetype is invalid, e.g., because it could not
  /// be resolved.
  unsigned Invalid : 1;

  /// Whether we are currently substituting into the concrete type of
  /// this potential archetype.
  unsigned SubstitutingConcreteType : 1;

  /// Whether we have detected recursion during the substitution of
  /// the concrete type.
  unsigned RecursiveConcreteType : 1;

  /// Whether we have detected recursion during the substitution of
  /// the superclass type.
  unsigned RecursiveSuperclassType : 1;

  /// Whether we have renamed this (nested) type due to typo correction.
  unsigned Renamed : 1;

  /// The equivalence class of this potential archetype.
  llvm::TinyPtrVector<PotentialArchetype *> EquivalenceClass;

  /// \brief Construct a new potential archetype for an unresolved
  /// associated type.
  PotentialArchetype(PotentialArchetype *Parent, Identifier Name)
    : ParentOrParam(Parent), NameOrAssociatedType(Name), Representative(this),
      IsRecursive(false), Invalid(false), SubstitutingConcreteType(false),
      RecursiveConcreteType(false), RecursiveSuperclassType(false),
      Renamed(false)
  { 
    assert(Parent != nullptr && "Not an associated type?");
    EquivalenceClass.push_back(this);
  }

  /// \brief Construct a new potential archetype for an associated type.
  PotentialArchetype(PotentialArchetype *Parent, AssociatedTypeDecl *AssocType)
    : ParentOrParam(Parent), NameOrAssociatedType(AssocType), 
      Representative(this), IsRecursive(false), Invalid(false),
      SubstitutingConcreteType(false), RecursiveConcreteType(false),
      RecursiveSuperclassType(false), Renamed(false)
  { 
    assert(Parent != nullptr && "Not an associated type?");
    EquivalenceClass.push_back(this);
  }

  /// \brief Construct a new potential archetype for a type alias.
  PotentialArchetype(PotentialArchetype *Parent, TypeAliasDecl *TypeAlias)
    : ParentOrParam(Parent), NameOrAssociatedType(TypeAlias),
      Representative(this), IsRecursive(false), Invalid(false),
      SubstitutingConcreteType(false), RecursiveConcreteType(false),
      RecursiveSuperclassType(false), Renamed(false)
  {
    assert(Parent != nullptr && "Not an associated type?");
    EquivalenceClass.push_back(this);
  }

  /// \brief Construct a new potential archetype for a generic parameter.
  PotentialArchetype(GenericTypeParamType *GenericParam, 
                     ProtocolDecl *RootProtocol,
                     Identifier Name)
    : ParentOrParam(GenericParam), RootProtocol(RootProtocol), 
      NameOrAssociatedType(Name), Representative(this), IsRecursive(false),
      Invalid(false), SubstitutingConcreteType(false),
      RecursiveConcreteType(false), RecursiveSuperclassType(false),
      Renamed(false)
  {
    EquivalenceClass.push_back(this);
  }

  /// \brief Recursively build the full name.
  void buildFullName(bool forDebug, SmallVectorImpl<char> &result) const;

public:
  ~PotentialArchetype();

  /// \brief Retrieve the name of this potential archetype.
  Identifier getName() const;

  /// \brief Retrieve the full display name of this potential archetype.
  std::string getFullName() const;

  /// \brief Retrieve the debug name of this potential archetype.
  std::string getDebugName() const;

  /// Retrieve the parent of this potential archetype, which will be non-null
  /// when this potential archetype is an associated type.
  PotentialArchetype *getParent() const { 
    return ParentOrParam.dyn_cast<PotentialArchetype *>(); 
  }

  /// Retrieve the generic parameter at the root of this potential archetype.
  GenericTypeParamType *getRootParam() const {
    if (auto parent = getParent())
      return parent->getRootParam();

    return getGenericParam();
  }

  /// Retrieve the associated type to which this potential archetype
  /// has been resolved.
  AssociatedTypeDecl *getResolvedAssociatedType() const {
    assert(getParent() && "Not an associated type");
    return NameOrAssociatedType.dyn_cast<AssociatedTypeDecl *>();
  }

  /// Resolve the potential archetype to the given associated type.
  void resolveAssociatedType(AssociatedTypeDecl *assocType,
                             ArchetypeBuilder &builder);

  /// Retrieve the generic type parameter for this potential
  /// archetype, if it corresponds to a generic parameter.
  GenericTypeParamType *getGenericParam() const {
    return ParentOrParam.dyn_cast<GenericTypeParamType *>(); 
  }
  
  /// Retrieve the type alias.
  TypeAliasDecl *getTypeAliasDecl() const {
    return NameOrAssociatedType.dyn_cast<TypeAliasDecl *>();
  }

  /// Retrieve the set of protocols to which this type conforms.
  const llvm::MapVector<ProtocolDecl *, RequirementSource> &
  getConformsTo() const {
    return ConformsTo;
  }

  /// Add a conformance to this potential archetype.
  ///
  /// \returns true if the conformance was new, false if it already existed.
  bool addConformance(ProtocolDecl *proto, bool updateExistingSource,
                      const RequirementSource &source,
                      ArchetypeBuilder &builder);

  /// Retrieve the superclass of this archetype.
  Type getSuperclass() const { return Superclass; }

  /// Retrieve the requirement source for the superclass requirement.
  const RequirementSource &getSuperclassSource() const {
    return *SuperclassSource;
  } 

  /// Retrieve the set of nested types.
  const llvm::MapVector<Identifier, llvm::TinyPtrVector<PotentialArchetype *>> &
  getNestedTypes() const{
    return NestedTypes;
  }

  /// \brief Determine the nesting depth of this potential archetype, e.g.,
  /// the number of associated type references.
  unsigned getNestingDepth() const;

  /// \brief Retrieve the representative for this archetype, performing
  /// path compression on the way.
  PotentialArchetype *getRepresentative();

  /// Retrieve the equivalence class containing this potential archetype.
  ArrayRef<PotentialArchetype *> getEquivalenceClass() {
    return getRepresentative()->EquivalenceClass;
  }

  /// \brief Retrieve the potential archetype to be used as the anchor for
  /// potential archetype computations.
  PotentialArchetype *getArchetypeAnchor();

  /// Retrieve the source of the same-type constraint that applies to this
  /// potential archetype.
  const RequirementSource &getSameTypeSource() const {
    return *SameTypeSource;
  }

  /// \brief Retrieve (or create) a nested type with the given name.
  PotentialArchetype *getNestedType(Identifier Name,
                                    ArchetypeBuilder &builder);

  /// \brief Retrieve (or build) the type corresponding to the potential
  /// archetype.
  ArchetypeType::NestedType getType(ArchetypeBuilder &builder);

  /// Retrieve the dependent type that describes this potential
  /// archetype.
  Type getDependentType(ArchetypeBuilder &builder, bool allowUnresolved);

  /// True if the potential archetype has been bound by a concrete type
  /// constraint.
  bool isConcreteType() const {
    if (Representative != this)
      return Representative->isConcreteType();

    return ArchetypeOrConcreteType.isConcreteType();
  }
  
  /// Get the concrete type this potential archetype is constrained to.
  Type getConcreteType() const {
    assert(isConcreteType());
    if (Representative != this)
      return Representative->getConcreteType();
    return ArchetypeOrConcreteType.getAsConcreteType();
  }

  void setIsRecursive() { IsRecursive = true; }
  bool isRecursive() const { return IsRecursive; }

  bool isInvalid() const { return Invalid; }

  void setInvalid() { Invalid = true; }

  /// Determine whether this archetype was renamed due to typo
  /// correction. If so, \c getName() retrieves the new name.
  bool wasRenamed() const { return Renamed; }

  /// Note that this potential archetype was renamed (due to typo
  /// correction), providing the new name.
  void setRenamed(Identifier newName) {
    NameOrAssociatedType = newName;
    Renamed = true;
  }

  /// Whether this potential archetype makes a better archetype anchor than
  /// the given archetype anchor.
  bool isBetterArchetypeAnchor(PotentialArchetype *other) const;

  void dump(llvm::raw_ostream &Out, SourceManager *SrcMgr,
            unsigned Indent);

  friend class ArchetypeBuilder;

private:
  bool hasConcreteTypeInPath() const;
};

} // end namespace swift

#endif