text: //===--- Expr.cpp - Swift Language Expression ASTs ------------------------===//
  //
  // 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
  //
  //===----------------------------------------------------------------------===//
  //
  //  This file implements the Expr class and subclasses.
  //
  //===----------------------------------------------------------------------===//
  
  #include "swift/AST/Expr.h"
  #include "swift/Basic/Unicode.h"
  #include "swift/AST/ASTVisitor.h"
  #include "swift/AST/Decl.h" // FIXME: Bad dependency
  #include "swift/AST/Stmt.h"
  #include "swift/AST/AST.h"
  #include "swift/AST/ASTWalker.h"
  #include "swift/AST/AvailabilitySpec.h"
  #include "swift/AST/PrettyStackTrace.h"
  #include "swift/AST/TypeLoc.h"
  #include "llvm/ADT/APFloat.h"
  #include "llvm/ADT/PointerUnion.h"
  #include "llvm/ADT/SetVector.h"
  #include "llvm/ADT/Twine.h"
  using namespace swift;
  
  //===----------------------------------------------------------------------===//
  // Expr methods.
  //===----------------------------------------------------------------------===//
  
  // Only allow allocation of Stmts using the allocator in ASTContext.
  void *Expr::operator new(size_t Bytes, ASTContext &C,
                           unsigned Alignment) {
    return C.Allocate(Bytes, Alignment);
  }
  
  StringRef Expr::getKindName(ExprKind K) {
    switch (K) {
  #define EXPR(Id, Parent) case ExprKind::Id: return #Id;
  #include "swift/AST/ExprNodes.def"
    }
    llvm_unreachable("bad ExprKind");
  }
  
  template <class T> static SourceLoc getStartLocImpl(const T *E);
  template <class T> static SourceLoc getEndLocImpl(const T *E);
  template <class T> static SourceLoc getLocImpl(const T *E);
  
  // Helper functions to check statically whether a method has been
  // overridden from its implementation in Expr.  The sort of thing you
  // need when you're avoiding v-tables.
  namespace {
    template <typename ReturnType, typename Class>
    constexpr bool isOverriddenFromExpr(ReturnType (Class::*)() const) {
      return true;
    }
    template <typename ReturnType>
    constexpr bool isOverriddenFromExpr(ReturnType (Expr::*)() const) {
      return false;
    }
  
    template <bool IsOverridden> struct Dispatch;
  
    /// Dispatch down to a concrete override.
    template <> struct Dispatch<true> {
      template <class T> static SourceLoc getStartLoc(const T *E) {
        return E->getStartLoc();
      }
      template <class T> static SourceLoc getEndLoc(const T *E) {
        return E->getEndLoc();
      }
      template <class T> static SourceLoc getLoc(const T *E) {
        return E->getLoc();
      }
      template <class T> static SourceRange getSourceRange(const T *E) {
        return E->getSourceRange();
      }
    };
  
    /// Default implementations for when a method isn't overridden.
    template <> struct Dispatch<false> {
      template <class T> static SourceLoc getStartLoc(const T *E) {
        return E->getSourceRange().Start;
      }
      template <class T> static SourceLoc getEndLoc(const T *E) {
        return E->getSourceRange().End;
      }
      template <class T> static SourceLoc getLoc(const T *E) {
        return getStartLocImpl(E);
      }
      template <class T> static SourceRange getSourceRange(const T *E) {
        return { E->getStartLoc(), E->getEndLoc() };
      }
    };
  }
  
  template <class T> static SourceRange getSourceRangeImpl(const T *E) {
    static_assert(isOverriddenFromExpr(&T::getSourceRange) ||
                  (isOverriddenFromExpr(&T::getStartLoc) &&
                   isOverriddenFromExpr(&T::getEndLoc)),
                  "Expr subclass must implement either getSourceRange() "
                  "or getStartLoc()/getEndLoc()");
    return Dispatch<isOverriddenFromExpr(&T::getSourceRange)>::getSourceRange(E);
  }
  
  SourceRange Expr::getSourceRange() const {
    switch (getKind()) {
  #define EXPR(ID, PARENT)                                           \
    case ExprKind::ID: return getSourceRangeImpl(cast<ID##Expr>(this));
  #include "swift/AST/ExprNodes.def"
    }
    
    llvm_unreachable("expression type not handled!");
  }
  
  template <class T> static SourceLoc getStartLocImpl(const T *E) {
    return Dispatch<isOverriddenFromExpr(&T::getStartLoc)>::getStartLoc(E);
  }
  SourceLoc Expr::getStartLoc() const {
    switch (getKind()) {
  #define EXPR(ID, PARENT)                                           \
    case ExprKind::ID: return getStartLocImpl(cast<ID##Expr>(this));
  #include "swift/AST/ExprNodes.def"
    }
  
    llvm_unreachable("expression type not handled!");
  }
  
  template <class T> static SourceLoc getEndLocImpl(const T *E) {
    return Dispatch<isOverriddenFromExpr(&T::getEndLoc)>::getEndLoc(E);
  }
  SourceLoc Expr::getEndLoc() const {
    switch (getKind()) {
  #define EXPR(ID, PARENT)                                           \
    case ExprKind::ID: return getEndLocImpl(cast<ID##Expr>(this));
  #include "swift/AST/ExprNodes.def"
    }
  
    llvm_unreachable("expression type not handled!");
  }
  
  template <class T> static SourceLoc getLocImpl(const T *E) {
    return Dispatch<isOverriddenFromExpr(&T::getLoc)>::getLoc(E);
  }
  SourceLoc Expr::getLoc() const {
    switch (getKind()) {
  #define EXPR(ID, PARENT)                                           \
    case ExprKind::ID: return getLocImpl(cast<ID##Expr>(this));
  #include "swift/AST/ExprNodes.def"
    }
  
    llvm_unreachable("expression type not handled!");
  }
  
  Expr *Expr::getSemanticsProvidingExpr() {
    if (IdentityExpr *IE = dyn_cast<IdentityExpr>(this))
      return IE->getSubExpr()->getSemanticsProvidingExpr();
  
    if (TryExpr *TE = dyn_cast<TryExpr>(this))
      return TE->getSubExpr()->getSemanticsProvidingExpr();
  
    if (DefaultValueExpr *DE = dyn_cast<DefaultValueExpr>(this))
      return DE->getSubExpr()->getSemanticsProvidingExpr();
    
    return this;
  }
  
  Expr *Expr::getValueProvidingExpr() {
    Expr *E = getSemanticsProvidingExpr();
  
    if (auto TE = dyn_cast<ForceTryExpr>(this))
      return TE->getSubExpr()->getValueProvidingExpr();
  
    // TODO:
    //   - tuple literal projection, which may become interestingly idiomatic
  
    return E;
  }
  
  /// Propagate l-value use information to children.
  void Expr::propagateLValueAccessKind(AccessKind accessKind,
                                       bool allowOverwrite) {
    /// A visitor class which walks an entire l-value expression.
    class PropagateAccessKind
         : public ExprVisitor<PropagateAccessKind, void, AccessKind> {
  #ifndef NDEBUG
      bool AllowOverwrite;
  #endif
    public:
      PropagateAccessKind(bool allowOverwrite)
  #ifndef NDEBUG
        : AllowOverwrite(allowOverwrite)
  #endif
      {}
  
      void visit(Expr *E, AccessKind kind) {
        assert((AllowOverwrite || !E->hasLValueAccessKind()) &&
               "l-value access kind has already been set");
  
        assert(E->getType()->isAssignableType() &&
               "setting access kind on non-l-value");
        E->setLValueAccessKind(kind);
  
        // Propagate this to sub-expressions.
        ASTVisitor::visit(E, kind);
      }
  
  #define NON_LVALUE_EXPR(KIND)                                           \
      void visit##KIND##Expr(KIND##Expr *, AccessKind accessKind) {       \
        llvm_unreachable("not an l-value");                               \
      }
  #define LEAF_LVALUE_EXPR(KIND)                                          \
      void visit##KIND##Expr(KIND##Expr *E, AccessKind accessKind) {}
  #define COMPLETE_PHYSICAL_LVALUE_EXPR(KIND, ACCESSOR)                   \
      void visit##KIND##Expr(KIND##Expr *E, AccessKind accessKind) {      \
        visit(E->ACCESSOR, accessKind);                                   \
      }
  #define PARTIAL_PHYSICAL_LVALUE_EXPR(KIND, ACCESSOR)                    \
      void visit##KIND##Expr(KIND##Expr *E, AccessKind accessKind) {      \
        visit(E->ACCESSOR, getPartialAccessKind(accessKind));             \
      }
  
      void visitMemberRefExpr(MemberRefExpr *E, AccessKind accessKind) {
        if (!E->getBase()->getType()->isLValueType()) return;
        visit(E->getBase(), getBaseAccessKind(E->getMember(), accessKind));
      }
      void visitSubscriptExpr(SubscriptExpr *E, AccessKind accessKind) {
        if (!E->getBase()->getType()->isLValueType()) return;
        visit(E->getBase(), getBaseAccessKind(E->getDecl(), accessKind));
      }
  
      static AccessKind getPartialAccessKind(AccessKind accessKind) {
        return (accessKind == AccessKind::Read
                  ? accessKind : AccessKind::ReadWrite);
      }
  
      static AccessKind getBaseAccessKind(ConcreteDeclRef member,
                                          AccessKind accessKind) {
        // We assume writes are partial writes, so the result is always
        // either Read or ReadWrite.
        auto memberDecl = cast<AbstractStorageDecl>(member.getDecl());
  
        // If we're reading and the getter is mutating, or we're writing
        // and the setter is mutating, this is readwrite.
        if ((accessKind != AccessKind::Write &&
             memberDecl->isGetterMutating()) ||
            (accessKind != AccessKind::Read &&
             !memberDecl->isSetterNonMutating())) {
          return AccessKind::ReadWrite;
        }
  
        return AccessKind::Read;
      }
  
      void visitTupleExpr(TupleExpr *E, AccessKind accessKind) {
        for (auto elt : E->getElements()) {
          visit(elt, accessKind);
        }
      }
  
      void visitOpenExistentialExpr(OpenExistentialExpr *E,
                                    AccessKind accessKind) {
        bool opaqueValueHadAK = E->getOpaqueValue()->hasLValueAccessKind();
        AccessKind oldOpaqueValueAK =
          (opaqueValueHadAK ? E->getOpaqueValue()->getLValueAccessKind()
                            : AccessKind::Read);
  
        visit(E->getSubExpr(), accessKind);
  
        // Propagate the new access kind from the OVE to the original existential
        // if we just set or changed it on the OVE.
        if (E->getOpaqueValue()->hasLValueAccessKind()) {
          auto newOpaqueValueAK = E->getOpaqueValue()->getLValueAccessKind();
          if (!opaqueValueHadAK || newOpaqueValueAK != oldOpaqueValueAK)
            visit(E->getExistentialValue(), newOpaqueValueAK);
        }
      }
  
      LEAF_LVALUE_EXPR(DeclRef)
      LEAF_LVALUE_EXPR(DiscardAssignment)
      LEAF_LVALUE_EXPR(DynamicLookup)
      LEAF_LVALUE_EXPR(OpaqueValue)
      LEAF_LVALUE_EXPR(EditorPlaceholder)
  
      COMPLETE_PHYSICAL_LVALUE_EXPR(AnyTry, getSubExpr())
      PARTIAL_PHYSICAL_LVALUE_EXPR(BindOptional, getSubExpr())
      COMPLETE_PHYSICAL_LVALUE_EXPR(DotSyntaxBaseIgnored, getRHS());
      PARTIAL_PHYSICAL_LVALUE_EXPR(ForceValue, getSubExpr())
      COMPLETE_PHYSICAL_LVALUE_EXPR(Identity, getSubExpr())
      PARTIAL_PHYSICAL_LVALUE_EXPR(TupleElement, getBase())
  
      NON_LVALUE_EXPR(Error)
      NON_LVALUE_EXPR(Literal)
      NON_LVALUE_EXPR(SuperRef)
      NON_LVALUE_EXPR(Type)
      NON_LVALUE_EXPR(OtherConstructorDeclRef)
      NON_LVALUE_EXPR(Collection)
      NON_LVALUE_EXPR(CaptureList)
      NON_LVALUE_EXPR(AbstractClosure)
      NON_LVALUE_EXPR(InOut)
      NON_LVALUE_EXPR(DynamicType)
      NON_LVALUE_EXPR(RebindSelfInConstructor)
      NON_LVALUE_EXPR(Apply)
      NON_LVALUE_EXPR(ImplicitConversion)
      NON_LVALUE_EXPR(ExplicitCast)
      NON_LVALUE_EXPR(OptionalEvaluation)
      NON_LVALUE_EXPR(If)
      NON_LVALUE_EXPR(Assign)
      NON_LVALUE_EXPR(DefaultValue)
      NON_LVALUE_EXPR(CodeCompletion)
  
  #define UNCHECKED_EXPR(KIND, BASE) \
      NON_LVALUE_EXPR(KIND)
  #include "swift/AST/ExprNodes.def"
  
  #undef PHYSICAL_LVALUE_EXPR
  #undef LEAF_LVALUE_EXPR
  #undef NON_LVALUE_EXPR
    };
  
    PropagateAccessKind(allowOverwrite).visit(this, accessKind);
  }
  
  /// Enumerate each immediate child expression of this node, invoking the
  /// specific functor on it.  This ignores statements and other non-expression
  /// children.
  void Expr::
  forEachImmediateChildExpr(const std::function<Expr*(Expr*)> &callback) {
    struct ChildWalker : ASTWalker {
      const std::function<Expr*(Expr*)> &callback;
      Expr *ThisNode;
      
      ChildWalker(const std::function<Expr*(Expr*)> &callback, Expr *ThisNode)
        : callback(callback), ThisNode(ThisNode) {}
      
      std::pair<bool, Expr *> walkToExprPre(Expr *E) override {
        // When looking at the current node, of course we want to enter it.  We
        // also don't want to enumerate it.
        if (E == ThisNode)
          return { true, E };
  
        // Otherwise we must be a child of our expression, enumerate it!
        return { false, callback(E) };
      }
      
      std::pair<bool, Stmt *> walkToStmtPre(Stmt *S) override {
        return { false, S };
      }
  
      std::pair<bool, Pattern*> walkToPatternPre(Pattern *P) override {
        return { false, P };
      }
      bool walkToDeclPre(Decl *D) override { return false; }
      bool walkToTypeReprPre(TypeRepr *T) override { return false; }
      bool walkToTypeLocPre(TypeLoc &TL) override { return false; }
    };
    
    this->walk(ChildWalker(callback, this));
  }
  
  /// Enumerate each immediate child expression of this node, invoking the
  /// specific functor on it.  This ignores statements and other non-expression
  /// children.
  void Expr::forEachChildExpr(const std::function<Expr*(Expr*)> &callback) {
    struct ChildWalker : ASTWalker {
      const std::function<Expr*(Expr*)> &callback;
  
      ChildWalker(const std::function<Expr*(Expr*)> &callback)
      : callback(callback) {}
  
      std::pair<bool, Expr *> walkToExprPre(Expr *E) override {
        // Enumerate the node!
        return { true, callback(E) };
      }
  
      std::pair<bool, Stmt *> walkToStmtPre(Stmt *S) override {
        return { false, S };
      }
  
      std::pair<bool, Pattern*> walkToPatternPre(Pattern *P) override {
        return { false, P };
      }
      bool walkToDeclPre(Decl *D) override { return false; }
      bool walkToTypeReprPre(TypeRepr *T) override { return false; }
      bool walkToTypeLocPre(TypeLoc &TL) override { return false; }
    };
  
    this->walk(ChildWalker(callback));
  }
  
  Initializer *Expr::findExistingInitializerContext() {
    struct FindExistingInitializer : ASTWalker {
      Initializer *TheInitializer = nullptr;
      std::pair<bool,Expr*> walkToExprPre(Expr *E) override {
        assert(!TheInitializer && "continuing to walk after finding context?");
        if (auto closure = dyn_cast<AbstractClosureExpr>(E)) {
          TheInitializer = cast<Initializer>(closure->getParent());
          return { false, nullptr };
        }
        return { true, E };
      }
    } finder;
    walk(finder);
    return finder.TheInitializer;
  }
  
  bool Expr::isTypeReference() const {
    // If the result isn't a metatype, there's nothing else to do.
    if (!getType()->is<AnyMetatypeType>())
      return false;
    
    const Expr *expr = this;
    do {
      // Skip syntax.
      expr = expr->getSemanticsProvidingExpr();
  
      // Direct reference to a type.
      if (auto declRef = dyn_cast<DeclRefExpr>(expr))
        if (isa<TypeDecl>(declRef->getDecl()))
          return true;
      if (isa<TypeExpr>(expr))
        return true;
  
      // A "." expression that refers to a member.
      if (auto memberRef = dyn_cast<MemberRefExpr>(expr))
        return isa<TypeDecl>(memberRef->getMember().getDecl());
  
      // When the base of a "." expression is ignored, look at the member.
      if (auto ignoredDot = dyn_cast<DotSyntaxBaseIgnoredExpr>(expr)) {
        expr = ignoredDot->getRHS();
        continue;
      }
  
      // Anything else is not statically derived.
      return false;
    } while (true);
  
  }
  
  bool Expr::isStaticallyDerivedMetatype() const {
    // The type must first be a type reference.
    if (!isTypeReference())
      return false;
  
    // Archetypes are never statically derived.
    return !getType()->getAs<AnyMetatypeType>()->getInstanceType()
      ->is<ArchetypeType>();
  }
  
  bool Expr::isSuperExpr() const {
    const Expr *expr = this;
    do {
      expr = expr->getSemanticsProvidingExpr();
  
      if (isa<SuperRefExpr>(expr))
        return true;
  
      if (auto derivedToBase = dyn_cast<DerivedToBaseExpr>(expr)) {
        expr = derivedToBase->getSubExpr();
        continue;
      }
      if (auto metatypeConversion = dyn_cast<MetatypeConversionExpr>(expr)) {
        expr = metatypeConversion->getSubExpr();
        continue;
      }
  
      return false;
    } while (true);
  }
  
  bool Expr::canAppendCallParentheses() const {
    switch (getKind()) {
    case ExprKind::Error:
    case ExprKind::CodeCompletion:
      return false;
  
    case ExprKind::NilLiteral:
    case ExprKind::IntegerLiteral:
    case ExprKind::FloatLiteral:
    case ExprKind::BooleanLiteral:
    case ExprKind::StringLiteral:
    case ExprKind::InterpolatedStringLiteral:
    case ExprKind::MagicIdentifierLiteral:
      return true;
  
    case ExprKind::ObjectLiteral:
      return true;
  
    case ExprKind::DiscardAssignment:
      // Legal but pointless.
      return true;
  
    case ExprKind::DeclRef:
      return !cast<DeclRefExpr>(this)->getDecl()->getName().isOperator();
  
    case ExprKind::SuperRef:
    case ExprKind::Type:
    case ExprKind::OtherConstructorDeclRef:
    case ExprKind::DotSyntaxBaseIgnored:
      return true;
  
    case ExprKind::OverloadedDeclRef: {
      auto *overloadedExpr = cast<OverloadedDeclRefExpr>(this);
      if (overloadedExpr->getDecls().empty())
        return false;
      return !overloadedExpr->getDecls().front()->getName().isOperator();
    }
  
    case ExprKind::OverloadedMemberRef:
      return true;
  
    case ExprKind::UnresolvedDeclRef:
      return cast<UnresolvedDeclRefExpr>(this)->getName().isOperator();
  
    case ExprKind::MemberRef:
    case ExprKind::DynamicMemberRef:
    case ExprKind::DynamicSubscript:
    case ExprKind::UnresolvedSpecialize:
    case ExprKind::UnresolvedMember:
    case ExprKind::UnresolvedDot:
      return true;
  
    case ExprKind::Sequence:
      return false;
  
    case ExprKind::Paren:
    case ExprKind::DotSelf:
    case ExprKind::Tuple:
    case ExprKind::Array:
    case ExprKind::Dictionary:
    case ExprKind::Subscript:
    case ExprKind::TupleElement:
      return true;
  
    case ExprKind::CaptureList:
    case ExprKind::Closure:
    case ExprKind::AutoClosure:
      return false;
  
    case ExprKind::DynamicType:
      return true;
  
    case ExprKind::Try:
    case ExprKind::ForceTry:
    case ExprKind::OptionalTry:
    case ExprKind::InOut:
      return false;
  
    case ExprKind::RebindSelfInConstructor:
    case ExprKind::OpaqueValue:
    case ExprKind::BindOptional:
    case ExprKind::OptionalEvaluation:
      return false;
  
    case ExprKind::ForceValue:
      return true;
  
    case ExprKind::OpenExistential:
      return false;
  
    case ExprKind::Call:
    case ExprKind::PostfixUnary:
    case ExprKind::DotSyntaxCall:
    case ExprKind::ConstructorRefCall:
      return true;
  
    case ExprKind::PrefixUnary:
    case ExprKind::Binary:
      return false;
  
    case ExprKind::Load:
    case ExprKind::TupleShuffle:
    case ExprKind::UnresolvedTypeConversion:
    case ExprKind::FunctionConversion:
    case ExprKind::CovariantFunctionConversion:
    case ExprKind::CovariantReturnConversion:
    case ExprKind::MetatypeConversion:
    case ExprKind::CollectionUpcastConversion:
    case ExprKind::Erasure:
    case ExprKind::DerivedToBase:
    case ExprKind::ArchetypeToSuper:
    case ExprKind::InjectIntoOptional:
    case ExprKind::ClassMetatypeToObject:
    case ExprKind::ExistentialMetatypeToObject:
    case ExprKind::ProtocolMetatypeToObject:
    case ExprKind::InOutToPointer:
    case ExprKind::ArrayToPointer:
    case ExprKind::StringToPointer:
    case ExprKind::PointerToPointer:
    case ExprKind::LValueToPointer:
    case ExprKind::ForeignObjectConversion:
      return false;
  
    case ExprKind::ForcedCheckedCast:
    case ExprKind::ConditionalCheckedCast:
    case ExprKind::Is:
    case ExprKind::Coerce:
      return false;
  
    case ExprKind::If:
    case ExprKind::Assign:
    case ExprKind::DefaultValue:
    case ExprKind::UnresolvedPattern:
    case ExprKind::EditorPlaceholder:
      return false;
    }
  }
  
  llvm::DenseMap<Expr *, Expr *> Expr::getParentMap() {
    class RecordingTraversal : public ASTWalker {
    public:
      llvm::DenseMap<Expr *, Expr *> &ParentMap;
  
      explicit RecordingTraversal(llvm::DenseMap<Expr *, Expr *> &parentMap)
        : ParentMap(parentMap) { }
  
      virtual std::pair<bool, Expr *> walkToExprPre(Expr *E) {
        if (auto parent = Parent.getAsExpr())
          ParentMap[E] = parent;
  
        return { true, E };
      }
    };
  
    llvm::DenseMap<Expr *, Expr *> parentMap;
    RecordingTraversal traversal(parentMap);
    walk(traversal);
    return parentMap;
  }
  
  llvm::DenseMap<Expr *, unsigned> Expr::getDepthMap() {
    class RecordingTraversal : public ASTWalker {
    public:
      llvm::DenseMap<Expr *, unsigned> &DepthMap;
      unsigned Depth = 0;
  
      explicit RecordingTraversal(llvm::DenseMap<Expr *, unsigned> &depthMap)
        : DepthMap(depthMap) { }
  
      virtual std::pair<bool, Expr *> walkToExprPre(Expr *E) {
        DepthMap[E] = Depth;
        Depth++;
        return { true, E };
      }
  
      virtual Expr *walkToExprPost(Expr *E) {
        Depth--;
        return E;
      }
    };
  
    llvm::DenseMap<Expr *, unsigned> depthMap;
    RecordingTraversal traversal(depthMap);
    walk(traversal);
    return depthMap;
  }
  
  llvm::DenseMap<Expr *, unsigned> Expr::getPreorderIndexMap() {
    class RecordingTraversal : public ASTWalker {
    public:
      llvm::DenseMap<Expr *, unsigned> &IndexMap;
      unsigned Index = 0;
  
      explicit RecordingTraversal(llvm::DenseMap<Expr *, unsigned> &indexMap)
        : IndexMap(indexMap) { }
  
      virtual std::pair<bool, Expr *> walkToExprPre(Expr *E) {
        IndexMap[E] = Index;
        Index++;
        return { true, E };
      }
    };
  
    llvm::DenseMap<Expr *, unsigned> indexMap;
    RecordingTraversal traversal(indexMap);
    walk(traversal);
    return indexMap;
  }
  
  //===----------------------------------------------------------------------===//
  // Support methods for Exprs.
  //===----------------------------------------------------------------------===//
  
  static LiteralExpr *shallowCloneImpl(const NilLiteralExpr *E, ASTContext &Ctx) {
    return new (Ctx) NilLiteralExpr(E->getLoc());
  }
  
  static LiteralExpr *
  shallowCloneImpl(const IntegerLiteralExpr *E, ASTContext &Ctx) {
    auto res = new (Ctx) IntegerLiteralExpr(E->getDigitsText(),
                                            E->getSourceRange().End);
    if (E->isNegative())
      res->setNegative(E->getSourceRange().Start);
    return res;
  }
  
  static LiteralExpr *shallowCloneImpl(const FloatLiteralExpr *E, ASTContext &Ctx) {
    auto res = new (Ctx) FloatLiteralExpr(E->getDigitsText(),
                                          E->getSourceRange().End);
    if (E->isNegative())
      res->setNegative(E->getSourceRange().Start);
    return res;
  }
  static LiteralExpr *
  shallowCloneImpl(const BooleanLiteralExpr *E, ASTContext &Ctx) {
    return new (Ctx) BooleanLiteralExpr(E->getValue(), E->getLoc());
  }
  static LiteralExpr *shallowCloneImpl(const StringLiteralExpr *E, ASTContext &Ctx) {
    auto res = new (Ctx) StringLiteralExpr(E->getValue(), E->getSourceRange());
    res->setEncoding(E->getEncoding());
    return res;
  }
  
  static LiteralExpr *
  shallowCloneImpl(const InterpolatedStringLiteralExpr *E, ASTContext &Ctx) {
    auto res = new (Ctx) InterpolatedStringLiteralExpr(E->getLoc(),
                  const_cast<InterpolatedStringLiteralExpr*>(E)->getSegments());
    res->setSemanticExpr(E->getSemanticExpr());
    return res;
  }
  
  
  static LiteralExpr *
  shallowCloneImpl(const MagicIdentifierLiteralExpr *E, ASTContext &Ctx) {
    auto res = new (Ctx) MagicIdentifierLiteralExpr(E->getKind(),
                                                    E->getSourceRange().End);
    if (res->isString())
      res->setStringEncoding(E->getStringEncoding());
    return res;
  }
  
  static LiteralExpr *
  shallowCloneImpl(const ObjectLiteralExpr *E, ASTContext &Ctx) {
    auto res = new (Ctx) ObjectLiteralExpr(E->getStartLoc(), E->getName(),
                                           E->getNameLoc(), E->getArg(),
                                           E->getEndLoc());
    res->setSemanticExpr(E->getSemanticExpr());
    return res;
  }
  
  // Make an exact copy of this AST node.
  LiteralExpr *LiteralExpr::shallowClone(ASTContext &Ctx) const {
    LiteralExpr *Result = nullptr;
    switch (getKind()) {
    default: llvm_unreachable("Unknown literal type!");
  #define DISPATCH_CLONE(KIND) \
    case ExprKind::KIND: \
      Result = shallowCloneImpl(cast<KIND##Expr>(this), Ctx); \
      break;
  
    DISPATCH_CLONE(NilLiteral)
    DISPATCH_CLONE(IntegerLiteral)
    DISPATCH_CLONE(FloatLiteral)
    DISPATCH_CLONE(BooleanLiteral)
    DISPATCH_CLONE(StringLiteral)
    DISPATCH_CLONE(InterpolatedStringLiteral)
    DISPATCH_CLONE(ObjectLiteral)
    DISPATCH_CLONE(MagicIdentifierLiteral)
  #undef DISPATCH_CLONE
    }
    
    Result->setType(getType());
    Result->setImplicit(isImplicit());
    return Result;
  }
  
  
  
  
  static APInt getIntegerLiteralValue(bool IsNegative, StringRef Text,
                                      unsigned BitWidth) {
    llvm::APInt Value(BitWidth, 0);
    // swift encodes octal differently from C
    bool IsCOctal = Text.size() > 1 && Text[0] == '0' && isdigit(Text[1]);
    bool Error = Text.getAsInteger(IsCOctal ? 10 : 0, Value);
    assert(!Error && "Invalid IntegerLiteral formed"); (void)Error;
    if (IsNegative)
      Value = -Value;
    if (Value.getBitWidth() != BitWidth)
      Value = Value.sextOrTrunc(BitWidth);
    return Value;
  }
  
  APInt IntegerLiteralExpr::getValue(StringRef Text, unsigned BitWidth) {
    return getIntegerLiteralValue(/*IsNegative=*/false, Text, BitWidth);
  }
  
  APInt IntegerLiteralExpr::getValue() const {
    assert(!getType().isNull() && "Semantic analysis has not completed");
    assert(!getType()->is<ErrorType>() && "Should have a valid type");
    return getIntegerLiteralValue(
        isNegative(), getDigitsText(),
        getType()->castTo<BuiltinIntegerType>()->getGreatestWidth());
  }
  
  static APFloat getFloatLiteralValue(bool IsNegative, StringRef Text,
                                      const llvm::fltSemantics &Semantics) {
    APFloat Val(Semantics);
    APFloat::opStatus Res =
      Val.convertFromString(Text, llvm::APFloat::rmNearestTiesToEven);
    assert(Res != APFloat::opInvalidOp && "Sema didn't reject invalid number");
    (void)Res;
    if (IsNegative) {
      auto NegVal = APFloat::getZero(Semantics, /*negative*/ true);
      Res = NegVal.subtract(Val, llvm::APFloat::rmNearestTiesToEven);
      assert(Res != APFloat::opInvalidOp && "Sema didn't reject invalid number");
      (void)Res;
      return NegVal;
    }
    return Val;
  }
  
  APFloat FloatLiteralExpr::getValue(StringRef Text,
                                     const llvm::fltSemantics &Semantics) {
    return getFloatLiteralValue(/*IsNegative*/false, Text, Semantics);
  }
  
  llvm::APFloat FloatLiteralExpr::getValue() const {
    assert(!getType().isNull() && "Semantic analysis has not completed");
    assert(!getType()->is<ErrorType>() && "Should have a valid type");
  
    return getFloatLiteralValue(isNegative(), getDigitsText(),
                    getType()->castTo<BuiltinFloatType>()->getAPFloatSemantics());
  }
  
  StringLiteralExpr::StringLiteralExpr(StringRef Val, SourceRange Range,
                                       bool Implicit)
      : LiteralExpr(ExprKind::StringLiteral, Implicit), Val(Val),
        Range(Range) {
    StringLiteralExprBits.Encoding = static_cast<unsigned>(UTF8);
    StringLiteralExprBits.IsSingleUnicodeScalar =
        unicode::isSingleUnicodeScalar(Val);
    StringLiteralExprBits.IsSingleExtendedGraphemeCluster =
        unicode::isSingleExtendedGraphemeCluster(Val);
  }
  
  void DeclRefExpr::setSpecialized() {
    if (isSpecialized())
      return;
  
    ConcreteDeclRef ref = getDeclRef();
    void *Mem = ref.getDecl()->getASTContext().Allocate(sizeof(SpecializeInfo),
                                                        alignof(SpecializeInfo));
    auto Spec = new (Mem) SpecializeInfo;
    Spec->D = ref;
    DOrSpecialized = Spec;
  }
  
  void DeclRefExpr::setGenericArgs(ArrayRef<TypeRepr*> GenericArgs) {
    ValueDecl *D = getDecl();
    assert(D);
    setSpecialized();
    getSpecInfo()->GenericArgs = D->getASTContext().AllocateCopy(GenericArgs);
  }
  
  ConstructorDecl *OtherConstructorDeclRefExpr::getDecl() const {
    return cast_or_null<ConstructorDecl>(Ctor.getDecl());
  }
  
  MemberRefExpr::MemberRefExpr(Expr *base, SourceLoc dotLoc,
                               ConcreteDeclRef member, DeclNameLoc nameLoc,
                               bool Implicit, AccessSemantics semantics)
    : Expr(ExprKind::MemberRef, Implicit), Base(base),
      Member(member), DotLoc(dotLoc), NameLoc(nameLoc) {
     
    MemberRefExprBits.Semantics = (unsigned) semantics;
    MemberRefExprBits.IsSuper = false;
  }
  
  Type OverloadSetRefExpr::getBaseType() const {
    if (isa<OverloadedDeclRefExpr>(this))
      return Type();
    if (auto *DRE = dyn_cast<OverloadedMemberRefExpr>(this)) {
      return DRE->getBase()->getType()->getRValueType();
    }
    
    llvm_unreachable("Unhandled overloaded set reference expression");
  }
  
  bool OverloadSetRefExpr::hasBaseObject() const {
    if (Type BaseTy = getBaseType())
      return !BaseTy->is<AnyMetatypeType>();
  
    return false;
  }
  
  SequenceExpr *SequenceExpr::create(ASTContext &ctx, ArrayRef<Expr*> elements) {
    assert(elements.size() & 1 && "even number of elements in sequence");
    void *Buffer = ctx.Allocate(sizeof(SequenceExpr) +
                                elements.size() * sizeof(Expr*),
                                alignof(SequenceExpr));
    return ::new(Buffer) SequenceExpr(elements);
  }
  
  SourceLoc TupleExpr::getStartLoc() const {
    if (LParenLoc.isValid()) return LParenLoc;
    if (getNumElements() == 0) return SourceLoc();
    return getElement(0)->getStartLoc();
  }
  
  SourceLoc TupleExpr::getEndLoc() const {
    if (hasTrailingClosure() || RParenLoc.isInvalid()) {
      if (getNumElements() == 0) return SourceLoc();
      return getElements().back()->getEndLoc();
    }
    return RParenLoc;
  }
  
  TupleExpr::TupleExpr(SourceLoc LParenLoc, ArrayRef<Expr *> SubExprs,
                       ArrayRef<Identifier> ElementNames, 
                       ArrayRef<SourceLoc> ElementNameLocs,
                       SourceLoc RParenLoc, bool HasTrailingClosure, 
                       bool Implicit, Type Ty)
    : Expr(ExprKind::Tuple, Implicit, Ty),
      LParenLoc(LParenLoc), RParenLoc(RParenLoc),
      NumElements(SubExprs.size())
  {
    TupleExprBits.HasTrailingClosure = HasTrailingClosure;
    TupleExprBits.HasElementNames = !ElementNames.empty();
    TupleExprBits.HasElementNameLocations = !ElementNameLocs.empty();
    
    assert(LParenLoc.isValid() == RParenLoc.isValid() &&
           "Mismatched parenthesis location information validity");
    assert(ElementNames.empty() || ElementNames.size() == SubExprs.size());
    assert(ElementNameLocs.empty() || 
           ElementNames.size() == ElementNameLocs.size());
  
    // Copy elements.
    memcpy(getElements().data(), SubExprs.data(), 
           SubExprs.size() * sizeof(Expr *));
  
    // Copy element names, if provided.
    if (hasElementNames()) {
      memcpy(getElementNamesBuffer().data(), ElementNames.data(),
             ElementNames.size() * sizeof(Identifier));
    }
  
    // Copy element name locations, if provided.
    if (hasElementNameLocs()) {
      memcpy(getElementNameLocsBuffer().data(), ElementNameLocs.data(),
             ElementNameLocs.size() * sizeof(SourceLoc));
    }
  }
  
  TupleExpr *TupleExpr::create(ASTContext &ctx,
                               SourceLoc LParenLoc, 
                               ArrayRef<Expr *> SubExprs,
                               ArrayRef<Identifier> ElementNames, 
                               ArrayRef<SourceLoc> ElementNameLocs,
                               SourceLoc RParenLoc, bool HasTrailingClosure, 
                               bool Implicit, Type Ty) {
    unsigned size = sizeof(TupleExpr);
    size += SubExprs.size() * sizeof(Expr*);
    size += ElementNames.size() * sizeof(Identifier);
    size += ElementNameLocs.size() * sizeof(SourceLoc);
    void *mem = ctx.Allocate(size, alignof(TupleExpr));
    return new (mem) TupleExpr(LParenLoc, SubExprs, ElementNames, ElementNameLocs,
                               RParenLoc, HasTrailingClosure, Implicit, Ty);
  }
  
  TupleExpr *TupleExpr::createEmpty(ASTContext &ctx, SourceLoc LParenLoc, 
                                    SourceLoc RParenLoc, bool Implicit) {
    return create(ctx, LParenLoc, { }, { }, { }, RParenLoc, 
                  /*HasTrailingClosure=*/false, Implicit, 
                  TupleType::getEmpty(ctx));
  }
  
  TupleExpr *TupleExpr::createImplicit(ASTContext &ctx, ArrayRef<Expr *> SubExprs,
                                       ArrayRef<Identifier> ElementNames) {
    return create(ctx, SourceLoc(), SubExprs, ElementNames, { }, SourceLoc(),
                  /*HasTrailingClosure=*/false, /*Implicit=*/true, Type());
  }
  
  
  ArrayExpr *ArrayExpr::create(ASTContext &C, SourceLoc LBracketLoc,
                               ArrayRef<Expr*> Elements,
                               ArrayRef<SourceLoc> CommaLocs,
                               SourceLoc RBracketLoc, Type Ty) {
    // Copy the element list into the ASTContext.
    auto NewElements = C.AllocateCopy(Elements);
    auto NewCommas = C.AllocateCopy(CommaLocs);
    return new (C) ArrayExpr(LBracketLoc, NewElements, NewCommas, RBracketLoc,Ty);
  }
  
  DictionaryExpr *DictionaryExpr::create(ASTContext &C, SourceLoc LBracketLoc,
                               ArrayRef<Expr*> Elements, SourceLoc RBracketLoc,
                               Type Ty) {
    // Copy the element list into the ASTContext.
    auto NewElements = C.AllocateCopy(Elements);
    return new (C) DictionaryExpr(LBracketLoc, NewElements, RBracketLoc, Ty);
  }
  
  static ValueDecl *getCalledValue(Expr *E) {
    if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
      return DRE->getDecl();
  
    Expr *E2 = E->getValueProvidingExpr();
    if (E != E2) return getCalledValue(E2);
    return nullptr;
  }
  
  ValueDecl *ApplyExpr::getCalledValue() const {
    return ::getCalledValue(Fn);
  }
  
  RebindSelfInConstructorExpr::RebindSelfInConstructorExpr(Expr *SubExpr,
                                                           VarDecl *Self)
    : Expr(ExprKind::RebindSelfInConstructor, /*Implicit=*/true,
           TupleType::getEmpty(Self->getASTContext())),
      SubExpr(SubExpr), Self(Self)
  {}
  
  OtherConstructorDeclRefExpr *
  RebindSelfInConstructorExpr::getCalledConstructor(bool &isChainToSuper) const {
    // Dig out the OtherConstructorRefExpr. Note that this is the reverse
    // of what we do in pre-checking.
    Expr *candidate = getSubExpr();
    while (true) {
      // Look through identity expressions.
      if (auto identity = dyn_cast<IdentityExpr>(candidate)) {
        candidate = identity->getSubExpr();
        continue;
      }
  
      // Look through force-value expressions.
      if (auto force = dyn_cast<ForceValueExpr>(candidate)) {
        candidate = force->getSubExpr();
        continue;
      }
  
      // Look through all try expressions.
      if (auto tryExpr = dyn_cast<AnyTryExpr>(candidate)) {
        candidate = tryExpr->getSubExpr();
        continue;
      }
  
      break;
    }
  
    // We hit an application, find the constructor reference.
    OtherConstructorDeclRefExpr *otherCtorRef;
    const ApplyExpr *apply;
    do {
      apply = cast<ApplyExpr>(candidate);
      candidate = apply->getFn();
      auto candidateUnwrapped = candidate->getSemanticsProvidingExpr();
      otherCtorRef = dyn_cast<OtherConstructorDeclRefExpr>(candidateUnwrapped);
    } while (!otherCtorRef);
  
    isChainToSuper = apply->getArg()->isSuperExpr();
    return otherCtorRef;
  }
  
  void AbstractClosureExpr::setParameterList(ParameterList *P) {
    parameterList = P;
    // Change the DeclContext of any parameters to be this closure.
    if (P)
      P->setDeclContextOfParamDecls(this);
  }
  
  
  Type AbstractClosureExpr::getResultType() const {
    if (getType()->is<ErrorType>())
      return getType();
  
    return getType()->castTo<FunctionType>()->getResult();
  }
  
  bool AbstractClosureExpr::isBodyThrowing() const {
    if (getType()->is<ErrorType>())
      return false;
  
    return getType()->castTo<FunctionType>()->getExtInfo().throws();
  }
  
  bool AbstractClosureExpr::hasSingleExpressionBody() const {
    if (auto closure = dyn_cast<ClosureExpr>(this))
      return closure->hasSingleExpressionBody();
  
    return true;
  }
  
  #define FORWARD_SOURCE_LOCS_TO(CLASS, NODE) \
    SourceRange CLASS::getSourceRange() const {     \
      return (NODE)->getSourceRange();              \
    }                                               \
    SourceLoc CLASS::getStartLoc() const {          \
      return (NODE)->getStartLoc();                 \
    }                                               \
    SourceLoc CLASS::getEndLoc() const {            \
      return (NODE)->getEndLoc();                   \
    }                                               \
    SourceLoc CLASS::getLoc() const {               \
      return (NODE)->getStartLoc();                 \
    }
  
  FORWARD_SOURCE_LOCS_TO(ClosureExpr, Body.getPointer())
  
  Expr *ClosureExpr::getSingleExpressionBody() const {
    assert(hasSingleExpressionBody() && "Not a single-expression body");
    if (!isVoidConversionClosure()) {
      return cast<ReturnStmt>(getBody()->getElement(0).get<Stmt *>())
               ->getResult();
    } else {
      return getBody()->getElement(0).get<Expr *>();
    }
  }
  
  void ClosureExpr::setSingleExpressionBody(Expr *NewBody) {
    assert(hasSingleExpressionBody() && "Not a single-expression body");
    if (!isVoidConversionClosure()) {
      cast<ReturnStmt>(getBody()->getElement(0).get<Stmt *>())
        ->setResult(NewBody);
    } else {
      return getBody()->setElement(0, NewBody);
    }
  }
  
  FORWARD_SOURCE_LOCS_TO(AutoClosureExpr, Body)
  
  void AutoClosureExpr::setBody(Expr *E) {
    auto &Context = getASTContext();
    auto *RS = new (Context) ReturnStmt(SourceLoc(), E);
    Body = BraceStmt::create(Context, E->getStartLoc(), { RS }, E->getEndLoc());
  }
  
  Expr *AutoClosureExpr::getSingleExpressionBody() const {
    return cast<ReturnStmt>(Body->getElement(0).get<Stmt *>())->getResult();
  }
  
  FORWARD_SOURCE_LOCS_TO(UnresolvedPatternExpr, subPattern)
  
  TypeExpr::TypeExpr(TypeLoc TyLoc)
    : Expr(ExprKind::Type, /*implicit*/false), Info(TyLoc) {
    Type Ty = TyLoc.getType();
    if (Ty && Ty->hasCanonicalTypeComputed())
      setType(MetatypeType::get(Ty, Ty->getASTContext()));
  }
  
  TypeExpr::TypeExpr(Type Ty)
    : Expr(ExprKind::Type, /*implicit*/true), Info(TypeLoc::withoutLoc(Ty)) {
    if (Ty->hasCanonicalTypeComputed())
      setType(MetatypeType::get(Ty, Ty->getASTContext()));
  }
  
  // The type of a TypeExpr is always a metatype type.  Return the instance
  // type or null if not set yet.
  Type TypeExpr::getInstanceType() const {
    if (!getType() || getType()->is<ErrorType>())
      return Type();
    
    return getType()->castTo<MetatypeType>()->getInstanceType();
  }
  
  
  /// Return a TypeExpr for a simple identifier and the specified location.
  TypeExpr *TypeExpr::createForDecl(SourceLoc Loc, TypeDecl *Decl,
                                    bool isImplicit) {
    ASTContext &C = Decl->getASTContext();
    assert(Loc.isValid());
    auto *Repr = new (C) SimpleIdentTypeRepr(Loc, Decl->getName());
    Repr->setValue(Decl);
    auto result = new (C) TypeExpr(TypeLoc(Repr, Type()));
    if (isImplicit)
      result->setImplicit();
    return result;
  }
  
  TypeExpr *TypeExpr::createForSpecializedDecl(SourceLoc Loc, TypeDecl *D,
                                               ArrayRef<TypeRepr*> args,
                                               SourceRange AngleLocs) {
    ASTContext &C = D->getASTContext();
    assert(Loc.isValid());
    auto *Repr = new (C) GenericIdentTypeRepr(Loc, D->getName(),
                                              args, AngleLocs);
    Repr->setValue(D);
    return new (C) TypeExpr(TypeLoc(Repr, Type()));
  }
  
  
  // Create an implicit TypeExpr, with location information even though it
  // shouldn't have one.  This is presently used to work around other location
  // processing bugs.  If you have an implicit location, use createImplicit.
  TypeExpr *TypeExpr::createImplicitHack(SourceLoc Loc, Type Ty, ASTContext &C) {
    // FIXME: This is horrible.
    if (Loc.isInvalid()) return createImplicit(Ty, C);
    auto *Repr = new (C) FixedTypeRepr(Ty, Loc);
    auto *Res = new (C) TypeExpr(TypeLoc(Repr, Ty));
    Res->setImplicit();
    Res->setType(MetatypeType::get(Ty, C));
    return Res;
  }
  
  
  ArchetypeType *OpenExistentialExpr::getOpenedArchetype() const {
    auto type = getOpaqueValue()->getType()->getRValueType();
    while (auto metaTy = type->getAs<MetatypeType>())
      type = metaTy->getInstanceType();
    return type->castTo<ArchetypeType>();
  }
  