| //===--- ConstraintLocator.h - Constraint Locator ---------------*- C++ -*-===// |
| // |
| // This source file is part of the Swift.org open source project |
| // |
| // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors |
| // Licensed under Apache License v2.0 with Runtime Library Exception |
| // |
| // See https://swift.org/LICENSE.txt for license information |
| // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file provides the \c ConstraintLocator class and its related types, |
| // which is used by the constraint-based type checker to describe how |
| // a particular constraint was derived. |
| // |
| //===----------------------------------------------------------------------===// |
| #ifndef SWIFT_SEMA_CONSTRAINTLOCATOR_H |
| #define SWIFT_SEMA_CONSTRAINTLOCATOR_H |
| |
| #include "swift/Basic/LLVM.h" |
| #include "swift/AST/Type.h" |
| #include "swift/AST/Types.h" |
| #include "llvm/ADT/ArrayRef.h" |
| #include "llvm/ADT/FoldingSet.h" |
| #include "llvm/ADT/PointerIntPair.h" |
| #include "llvm/ADT/PointerUnion.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/Support/Allocator.h" |
| #include "llvm/Support/ErrorHandling.h" |
| #include <utility> |
| |
| namespace swift { |
| |
| class Expr; |
| class SourceManager; |
| |
| namespace constraints { |
| class ConstraintSystem; |
| |
| /// \brief Locates a given constraint within the expression being |
| /// type-checked, which may refer down into subexpressions and parts of |
| /// the types of those subexpressions. |
| /// |
| /// Each locator as anchored at some expression, e.g., (3, (x, 3.14)), |
| /// and contains a path that digs further into the type of that expression. |
| /// For example, the path "tuple element #1" -> "tuple element #0" with the |
| /// above expression would refer to 'x'. If 'x' had function type, the |
| /// path could be further extended with either "-> argument" or "-> result", |
| /// to indicate constraints on its argument or result type. |
| class ConstraintLocator : public llvm::FoldingSetNode { |
| public: |
| /// \brief Describes the kind of a particular path element, e.g., |
| /// "tuple element", "call result", "base of member lookup", etc. |
| enum PathElementKind : unsigned char { |
| /// \brief The argument of function application. |
| ApplyArgument, |
| /// \brief The function being applied. |
| ApplyFunction, |
| /// Matching an argument to a parameter. |
| ApplyArgToParam, |
| /// \brief An archetype being opened. |
| /// |
| /// Also contains the archetype itself. |
| Archetype, |
| /// An associated type reference. |
| /// |
| /// Contains the associated type itself. |
| AssociatedType, |
| /// \brief The argument type of a function. |
| FunctionArgument, |
| /// \brief The result type of a function. |
| FunctionResult, |
| /// \brief A tuple element referenced by position. |
| TupleElement, |
| /// \brief A tuple element referenced by name. |
| NamedTupleElement, |
| /// \brief An optional payload. |
| OptionalPayload, |
| /// \brief A generic argument. |
| /// FIXME: Add support for named generic arguments? |
| GenericArgument, |
| /// \brief A member. |
| /// FIXME: Do we need the actual member name here? |
| Member, |
| /// \brief An unresolved member. |
| UnresolvedMember, |
| /// \brief The base of a member expression. |
| MemberRefBase, |
| /// \brief The lookup for a subscript member. |
| SubscriptMember, |
| /// \brief The index of a subscript expression. |
| SubscriptIndex, |
| /// \brief The result of a subscript expression. |
| SubscriptResult, |
| /// \brief The lookup for a constructor member. |
| ConstructorMember, |
| /// \brief Rvalue adjustment. |
| RvalueAdjustment, |
| /// \brief The result of a closure. |
| ClosureResult, |
| /// \brief The parent of a nested type. |
| ParentType, |
| /// \brief The instance of a metatype type. |
| InstanceType, |
| /// \brief The generic type of a sequence. |
| SequenceIteratorProtocol, |
| /// \brief The element type of a generator. |
| GeneratorElementType, |
| /// \brief The element of an array type. |
| ArrayElementType, |
| /// \brief The scalar type of a tuple type. |
| ScalarToTuple, |
| /// \brief The load of an lvalue. |
| Load, |
| /// The requirement that we're matching during protocol conformance |
| /// checking. |
| Requirement, |
| /// The candidate witness during protocol conformance checking. |
| Witness, |
| /// This is referring to a type produced by opening a generic type at the |
| /// base of the locator. |
| OpenedGeneric, |
| /// A component of a key path. |
| KeyPathComponent, |
| }; |
| |
| /// \brief Determine the number of numeric values used for the given path |
| /// element kind. |
| static unsigned numNumericValuesInPathElement(PathElementKind kind) { |
| switch (kind) { |
| case ApplyArgument: |
| case ApplyFunction: |
| case Archetype: |
| case AssociatedType: |
| case FunctionArgument: |
| case FunctionResult: |
| case OptionalPayload: |
| case Member: |
| case MemberRefBase: |
| case UnresolvedMember: |
| case SubscriptIndex: |
| case SubscriptMember: |
| case SubscriptResult: |
| case ConstructorMember: |
| case RvalueAdjustment: |
| case ClosureResult: |
| case ParentType: |
| case InstanceType: |
| case SequenceIteratorProtocol: |
| case GeneratorElementType: |
| case ArrayElementType: |
| case ScalarToTuple: |
| case Load: |
| case Requirement: |
| case Witness: |
| case OpenedGeneric: |
| return 0; |
| |
| case GenericArgument: |
| case NamedTupleElement: |
| case TupleElement: |
| case KeyPathComponent: |
| return 1; |
| |
| case ApplyArgToParam: |
| return 2; |
| } |
| |
| llvm_unreachable("Unhandled PathElementKind in switch."); |
| } |
| |
| /// Flags for efficiently recording certain information about a path. |
| /// All of this information should be re-derivable from the path. |
| /// |
| /// Values are chosen so that an empty path has value 0 and the |
| /// flags for a concatenated paths is simply the bitwise-or of the |
| /// flags of the component paths. |
| enum Flag : unsigned { |
| /// Does this path involve a function conversion, i.e. a |
| /// FunctionArgument or FunctionResult node? |
| IsFunctionConversion = 0x1, |
| }; |
| |
| static unsigned getSummaryFlagsForPathElement(PathElementKind kind) { |
| switch (kind) { |
| case ApplyArgument: |
| case ApplyFunction: |
| case ApplyArgToParam: |
| case SequenceIteratorProtocol: |
| case GeneratorElementType: |
| case ArrayElementType: |
| case ClosureResult: |
| case ConstructorMember: |
| case InstanceType: |
| case Load: |
| case OptionalPayload: |
| case Member: |
| case MemberRefBase: |
| case UnresolvedMember: |
| case ParentType: |
| case RvalueAdjustment: |
| case ScalarToTuple: |
| case SubscriptIndex: |
| case SubscriptMember: |
| case SubscriptResult: |
| case OpenedGeneric: |
| case Archetype: |
| case AssociatedType: |
| case GenericArgument: |
| case NamedTupleElement: |
| case TupleElement: |
| case Requirement: |
| case Witness: |
| case KeyPathComponent: |
| return 0; |
| |
| case FunctionArgument: |
| case FunctionResult: |
| return IsFunctionConversion; |
| } |
| |
| llvm_unreachable("Unhandled PathElementKind in switch."); |
| } |
| |
| template<unsigned N> struct incomplete; |
| |
| /// \brief One element in the path of a locator, which can include both |
| /// a kind (PathElementKind) and a value used to describe specific |
| /// kinds further (e.g., the position of a tuple element). |
| class PathElement { |
| /// \brief Describes the kind of data stored here. |
| enum StoredKind : unsigned char { |
| StoredArchetype, |
| StoredRequirement, |
| StoredWitness, |
| StoredKindAndValue |
| }; |
| |
| /// \brief The actual storage for the path element, which involves both a |
| /// kind and (potentially) a value. |
| /// |
| /// The current storage involves a two-bit "storage kind", which selects |
| /// among the possible value stores. The value stores can either be an |
| /// archetype (for archetype path elements) or an unsigned value that |
| /// stores both the specific kind and the (optional) numeric value of that |
| /// kind. Use \c encodeStorage and \c decodeStorage to work with this value. |
| /// |
| /// \note The "storage kind" is stored in the \c storedKind field. |
| uint64_t storage : 62; |
| |
| /// \brief The kind of value stored in \c storage. Valid values are those |
| /// from the StoredKind enum. |
| uint64_t storedKind : 2; |
| |
| /// \brief Encode a path element kind and a value into the storage format. |
| static uint64_t encodeStorage(PathElementKind kind, unsigned value) { |
| return ((uint64_t)value << 8) | kind; |
| } |
| |
| /// \brief Decode a storage value into path element kind and value. |
| static std::pair<PathElementKind, unsigned> |
| decodeStorage(uint64_t storage) { |
| return { (PathElementKind)((unsigned)storage & 0xFF), storage >> 8 }; |
| } |
| |
| PathElement(PathElementKind kind, unsigned value) |
| : storage(encodeStorage(kind, value)), storedKind(StoredKindAndValue) |
| { |
| assert(numNumericValuesInPathElement(kind) == 1 && |
| "Path element kind does not require 1 value"); |
| } |
| |
| PathElement(PathElementKind kind, unsigned value1, unsigned value2) |
| : storage(encodeStorage(kind, value1 << 16 | value2)), |
| storedKind(StoredKindAndValue) |
| { |
| assert(numNumericValuesInPathElement(kind) == 2 && |
| "Path element kind does not require 2 values"); |
| } |
| |
| friend class ConstraintLocator; |
| |
| public: |
| PathElement(PathElementKind kind) |
| : storage(encodeStorage(kind, 0)), storedKind(StoredKindAndValue) |
| { |
| assert(numNumericValuesInPathElement(kind) == 0 && |
| "Path element requires value"); |
| } |
| |
| PathElement(ArchetypeType *archetype) |
| : storage((reinterpret_cast<uintptr_t>(archetype) >> 2)), |
| storedKind(StoredArchetype) |
| { |
| static_assert(alignof(ArchetypeType) >= 4, |
| "archetypes insufficiently aligned"); |
| assert(getArchetype() == archetype); |
| } |
| |
| PathElement(PathElementKind kind, ValueDecl *decl) |
| : storage((reinterpret_cast<uintptr_t>(decl) >> 2)), |
| storedKind(kind == Witness ? StoredWitness : StoredRequirement) |
| { |
| assert((kind == Witness || kind == Requirement) && |
| "Not a witness element"); |
| assert(((kind == Requirement && getRequirement() == decl) || |
| (kind == Witness && getWitness() == decl))); |
| } |
| |
| PathElement(AssociatedTypeDecl *decl) |
| : storage((reinterpret_cast<uintptr_t>(decl) >> 2)), |
| storedKind(StoredRequirement) |
| { |
| assert(getAssociatedType() == decl); |
| } |
| |
| /// \brief Retrieve a path element for a tuple element referred to by |
| /// its position. |
| static PathElement getTupleElement(unsigned position) { |
| return PathElement(TupleElement, position); |
| } |
| |
| /// \brief Retrieve a path element for a tuple element referred to by |
| /// its name. |
| static PathElement getNamedTupleElement(unsigned position) { |
| return PathElement(NamedTupleElement, position); |
| } |
| |
| /// Retrieve a patch element for an argument/parameter comparison in a |
| /// function application. |
| static PathElement getApplyArgToParam(unsigned argIdx, unsigned paramIdx) { |
| return PathElement(ApplyArgToParam, argIdx, paramIdx); |
| } |
| |
| /// \brief Retrieve a path element for a generic argument referred to by |
| /// its position. |
| static PathElement getGenericArgument(unsigned position) { |
| return PathElement(GenericArgument, position); |
| } |
| |
| /// Get a path element for a key path component. |
| static PathElement getKeyPathComponent(unsigned position) { |
| return PathElement(KeyPathComponent, position); |
| } |
| |
| /// \brief Retrieve the kind of path element. |
| PathElementKind getKind() const { |
| switch (static_cast<StoredKind>(storedKind)) { |
| case StoredArchetype: |
| return Archetype; |
| |
| case StoredRequirement: |
| return isa<AssociatedTypeDecl>(getRequirement()) ? AssociatedType |
| : Requirement; |
| |
| case StoredWitness: |
| return Witness; |
| |
| case StoredKindAndValue: |
| return decodeStorage(storage).first; |
| } |
| |
| llvm_unreachable("Unhandled StoredKind in switch."); |
| } |
| |
| /// \brief Retrieve the value associated with this path element, |
| /// if it has one. |
| unsigned getValue() const { |
| unsigned numValues = numNumericValuesInPathElement(getKind()); |
| assert(numValues > 0 && "No value in path element!"); |
| |
| auto value = decodeStorage(storage).second; |
| if (numValues == 1) { |
| return value; |
| } |
| |
| return value >> 16; |
| } |
| |
| /// \brief Retrieve the second value associated with this path element, |
| /// if it has one. |
| unsigned getValue2() const { |
| unsigned numValues = numNumericValuesInPathElement(getKind()); |
| (void)numValues; |
| assert(numValues == 2 && "No second value in path element!"); |
| |
| auto value = decodeStorage(storage).second; |
| return value & 0x00FFFF; |
| } |
| |
| /// Retrieve the declaration for a witness path element. |
| ValueDecl *getWitness() const { |
| assert(getKind() == Witness && "Is not a witness"); |
| return reinterpret_cast<ValueDecl *>(storage << 2); |
| } |
| |
| /// \brief Retrieve the actual archetype for an archetype path element. |
| ArchetypeType *getArchetype() const { |
| assert(getKind() == Archetype && "Not an archetype path element"); |
| return reinterpret_cast<ArchetypeType *>(storage << 2); |
| } |
| |
| /// Retrieve the declaration for a requirement path element. |
| ValueDecl *getRequirement() const { |
| assert((static_cast<StoredKind>(storedKind) == StoredRequirement) && |
| "Is not a requirement"); |
| return reinterpret_cast<ValueDecl *>(storage << 2); |
| } |
| |
| /// Retrieve the declaration for an associated type path element. |
| AssociatedTypeDecl *getAssociatedType() const { |
| assert(getKind() == AssociatedType && "Is not an associated type"); |
| return reinterpret_cast<AssociatedTypeDecl *>(storage << 2); |
| } |
| |
| /// \brief Return the summary flags for this particular element. |
| unsigned getNewSummaryFlags() const { |
| return getSummaryFlagsForPathElement(getKind()); |
| } |
| }; |
| |
| /// Return the summary flags for an entire path. |
| static unsigned getSummaryFlagsForPath(ArrayRef<PathElement> path) { |
| unsigned flags = 0; |
| for (auto &elt : path) flags |= elt.getNewSummaryFlags(); |
| return flags; |
| } |
| |
| /// \brief Retrieve the expression that anchors this locator. |
| Expr *getAnchor() const { return anchor; } |
| |
| /// \brief Retrieve the path that extends from the anchor to a specific |
| /// subcomponent. |
| ArrayRef<PathElement> getPath() const { |
| // FIXME: Alignment. |
| return llvm::makeArrayRef(reinterpret_cast<const PathElement *>(this + 1), |
| numPathElements); |
| } |
| |
| unsigned getSummaryFlags() const { return summaryFlags; } |
| |
| /// \brief Determines whether this locator is part of a function |
| /// conversion. |
| bool isFunctionConversion() const { |
| return (getSummaryFlags() & IsFunctionConversion); |
| } |
| |
| /// \brief Produce a profile of this locator, for use in a folding set. |
| static void Profile(llvm::FoldingSetNodeID &id, Expr *anchor, |
| ArrayRef<PathElement> path); |
| |
| /// \brief Produce a profile of this locator, for use in a folding set. |
| void Profile(llvm::FoldingSetNodeID &id) { |
| Profile(id, anchor, getPath()); |
| } |
| |
| /// \brief Produce a debugging dump of this locator. |
| LLVM_ATTRIBUTE_DEPRECATED( |
| void dump(SourceManager *SM) LLVM_ATTRIBUTE_USED, |
| "only for use within the debugger"); |
| LLVM_ATTRIBUTE_DEPRECATED( |
| void dump(ConstraintSystem *CS) LLVM_ATTRIBUTE_USED, |
| "only for use within the debugger"); |
| |
| void dump(SourceManager *SM, raw_ostream &OS) LLVM_ATTRIBUTE_USED; |
| |
| private: |
| /// \brief Initialize a constraint locator with an anchor and a path. |
| ConstraintLocator(Expr *anchor, ArrayRef<PathElement> path, |
| unsigned flags) |
| : anchor(anchor), numPathElements(path.size()), summaryFlags(flags) |
| { |
| // FIXME: Alignment. |
| std::copy(path.begin(), path.end(), |
| reinterpret_cast<PathElement *>(this + 1)); |
| } |
| |
| /// \brief Create a new locator from an anchor and an array of path |
| /// elements. |
| /// |
| /// Note that this routine only handles the allocation and initialization |
| /// of the locator. The ConstraintSystem object is responsible for |
| /// uniquing via the FoldingSet. |
| static ConstraintLocator *create(llvm::BumpPtrAllocator &allocator, |
| Expr *anchor, |
| ArrayRef<PathElement> path, |
| unsigned flags) { |
| // FIXME: Alignment. |
| unsigned size = sizeof(ConstraintLocator) |
| + path.size() * sizeof(PathElement); |
| void *mem = allocator.Allocate(size, alignof(ConstraintLocator)); |
| return new (mem) ConstraintLocator(anchor, path, flags); |
| } |
| |
| /// \brief The expression at which this locator is anchored. |
| Expr *anchor; |
| |
| /// \brief The number of path elements in this locator. |
| /// |
| /// The actual path elements are stored after the locator. |
| unsigned numPathElements : 24; |
| |
| /// \brief A set of flags summarizing interesting properties of the path. |
| unsigned summaryFlags : 7; |
| |
| friend class ConstraintSystem; |
| }; |
| |
| typedef ConstraintLocator::PathElement LocatorPathElt; |
| |
| /// \brief A simple stack-only builder object that constructs a |
| /// constraint locator without allocating memory. |
| /// |
| /// Use this object to build a path when passing components down the |
| /// stack, e.g., when recursively breaking apart types as in \c matchTypes(). |
| class ConstraintLocatorBuilder { |
| /// \brief The constraint locator that this builder extends or the |
| /// previous builder in the chain. |
| llvm::PointerUnion<ConstraintLocator *, ConstraintLocatorBuilder *> |
| previous; |
| |
| /// \brief The current path element, if there is one. |
| Optional<LocatorPathElt> element; |
| |
| /// \brief The current set of flags. |
| unsigned summaryFlags; |
| |
| ConstraintLocatorBuilder(llvm::PointerUnion<ConstraintLocator *, |
| ConstraintLocatorBuilder *> |
| previous, |
| LocatorPathElt element, |
| unsigned flags) |
| : previous(previous), element(element), summaryFlags(flags) { } |
| |
| public: |
| ConstraintLocatorBuilder(ConstraintLocator *locator) |
| : previous(locator), element(), |
| summaryFlags(locator ? locator->getSummaryFlags() : 0) { } |
| |
| /// \brief Retrieve a new path with the given path element added to it. |
| ConstraintLocatorBuilder withPathElement(LocatorPathElt newElt) { |
| unsigned newFlags = summaryFlags | newElt.getNewSummaryFlags(); |
| if (!element) |
| return ConstraintLocatorBuilder(previous, newElt, newFlags); |
| |
| return ConstraintLocatorBuilder(this, newElt, newFlags); |
| } |
| |
| /// \brief Determine whether this builder has an empty path. |
| bool hasEmptyPath() const { |
| return !element; |
| } |
| |
| /// \brief Return the set of flags that summarize this path. |
| unsigned getSummaryFlags() const { |
| return summaryFlags; |
| } |
| |
| bool isFunctionConversion() const { |
| return (getSummaryFlags() & ConstraintLocator::IsFunctionConversion); |
| } |
| |
| /// \brief Retrieve the base constraint locator, on which this builder's |
| /// path is based. |
| ConstraintLocator *getBaseLocator() const { |
| for (auto prev = this; |
| prev; |
| prev = prev->previous.dyn_cast<ConstraintLocatorBuilder *>()) { |
| if (auto locator = prev->previous.dyn_cast<ConstraintLocator *>()) |
| return locator; |
| } |
| |
| return nullptr; |
| } |
| |
| /// \brief Retrieve the components of the complete locator, which includes |
| /// the anchor expression and the path. |
| Expr *getLocatorParts(SmallVectorImpl<LocatorPathElt> &path) const { |
| for (auto prev = this; |
| prev; |
| prev = prev->previous.dyn_cast<ConstraintLocatorBuilder *>()) { |
| // If there is an element at this level, add it. |
| if (prev->element) |
| path.push_back(*prev->element); |
| |
| if (auto locator = prev->previous.dyn_cast<ConstraintLocator *>()) { |
| // We found the end of the chain. Reverse the path we've built up, |
| // then prepend the locator's path. |
| std::reverse(path.begin(), path.end()); |
| path.insert(path.begin(), |
| locator->getPath().begin(), |
| locator->getPath().end()); |
| return locator->getAnchor(); |
| } |
| } |
| |
| // There was no locator. Just reverse the path. |
| std::reverse(path.begin(), path.end()); |
| return nullptr; |
| } |
| |
| /// Attempt to simplify this locator to a single expression. |
| Expr *trySimplifyToExpr() const; |
| |
| /// Retrieve the last element in the path, if there is one. |
| Optional<LocatorPathElt> last() const { |
| // If we stored a path element here, grab it. |
| if (element) return *element; |
| |
| // Otherwise, look in the previous builder if there is one. |
| if (auto prevBuilder = previous.dyn_cast<ConstraintLocatorBuilder *>()) |
| return prevBuilder->last(); |
| |
| // Next, check the constraint locator itself. |
| if (auto locator = previous.dyn_cast<ConstraintLocator *>()) { |
| auto path = locator->getPath(); |
| if (path.empty()) return None; |
| return path.back(); |
| } |
| |
| return None; |
| } |
| }; |
| |
| } // end namespace constraints |
| } // end namespace swift |
| |
| #endif // LLVM_SWIFT_SEMA_CONSTRAINTLOCATOR_H |