//===--- DiagnoseStaticExclusivity.cpp - Find violations of exclusivity ---===//
//
// 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 implements a diagnostic pass that finds violations of the
// "Law of Exclusivity" at compile time. The Law of Exclusivity requires
// that the access duration of any access to an address not overlap
// with an access to the same address unless both accesses are reads.
//
// This pass relies on 'begin_access' and 'end_access' SIL instruction
// markers inserted during SILGen to determine when an access to an address
// begins and ends. It models the in-progress accesses with a map from
// storage locations to the counts of read and write-like accesses in progress
// for that location.
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "static-exclusivity"
#include "swift/AST/ASTWalker.h"
#include "swift/AST/Decl.h"
#include "swift/AST/DiagnosticsSIL.h"
#include "swift/AST/Expr.h"
#include "swift/AST/Stmt.h"
#include "swift/Basic/SourceLoc.h"
#include "swift/Parse/Lexer.h"
#include "swift/SIL/CFG.h"
#include "swift/SIL/InstructionUtils.h"
#include "swift/SIL/MemAccessUtils.h"
#include "swift/SIL/Projection.h"
#include "swift/SIL/SILArgument.h"
#include "swift/SIL/SILInstruction.h"
#include "swift/SILOptimizer/Analysis/AccessSummaryAnalysis.h"
#include "swift/SILOptimizer/Analysis/PostOrderAnalysis.h"
#include "swift/SILOptimizer/PassManager/Passes.h"
#include "swift/SILOptimizer/PassManager/Transforms.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"

using namespace swift;

template <typename... T, typename... U>
static InFlightDiagnostic diagnose(ASTContext &Context, SourceLoc loc,
                                   Diag<T...> diag, U &&... args) {
  return Context.Diags.diagnose(loc, diag, std::forward<U>(args)...);
}

namespace {

enum class RecordedAccessKind {
  /// The access was for a 'begin_access' instruction in the current function
  /// being checked.
  BeginInstruction,

  /// The access was inside noescape closure that we either
  /// passed to function or called directly. It results from applying the
  /// the summary of the closure to the closure's captures.
  NoescapeClosureCapture
};

/// Records an access to an address and the single subpath of projections
/// that was performed on the address, if such a single subpath exists.
class RecordedAccess {
private:
  RecordedAccessKind RecordKind;

  union {
   BeginAccessInst *Inst;
    struct {
      SILAccessKind ClosureAccessKind;
      SILLocation ClosureAccessLoc;
    };
  };

  const IndexTrieNode *SubPath;
public:
  RecordedAccess(BeginAccessInst *BAI, const IndexTrieNode *SubPath) :
      RecordKind(RecordedAccessKind::BeginInstruction), Inst(BAI),
      SubPath(SubPath) { }

  RecordedAccess(SILAccessKind ClosureAccessKind,
                 SILLocation ClosureAccessLoc, const IndexTrieNode *SubPath) :
      RecordKind(RecordedAccessKind::NoescapeClosureCapture),
      ClosureAccessKind(ClosureAccessKind), ClosureAccessLoc(ClosureAccessLoc),
      SubPath(SubPath) { }

  RecordedAccessKind getRecordKind() const {
    return RecordKind;
  }

  BeginAccessInst *getInstruction() const {
    assert(RecordKind == RecordedAccessKind::BeginInstruction);
    return Inst;
  }

  SILAccessKind getAccessKind() const {
    switch (RecordKind) {
      case RecordedAccessKind::BeginInstruction:
        return Inst->getAccessKind();
      case RecordedAccessKind::NoescapeClosureCapture:
        return ClosureAccessKind;
    };
    llvm_unreachable("unhandled kind");
  }

  SILLocation getAccessLoc() const {
    switch (RecordKind) {
      case RecordedAccessKind::BeginInstruction:
        return Inst->getLoc();
      case RecordedAccessKind::NoescapeClosureCapture:
        return ClosureAccessLoc;
    };
    llvm_unreachable("unhandled kind");
  }

  const IndexTrieNode *getSubPath() const {
    return SubPath;
  }
};


/// Records the in-progress accesses to a given sub path.
class SubAccessInfo {
public:
  SubAccessInfo(const IndexTrieNode *P) : Path(P) {}

  const IndexTrieNode *Path;

  /// The number of in-progress 'read' accesses (that is 'begin_access [read]'
  /// instructions that have not yet had the corresponding 'end_access').
  unsigned Reads = 0;

  /// The number of in-progress write-like accesses.
  unsigned NonReads = 0;

  /// The instruction that began the first in-progress access to the storage
  /// location. Used for diagnostic purposes.
  Optional<RecordedAccess> FirstAccess = None;

public:
  /// Increment the count for given access.
  void beginAccess(BeginAccessInst *BAI, const IndexTrieNode *SubPath) {
    if (!FirstAccess) {
      assert(Reads == 0 && NonReads == 0);
      FirstAccess = RecordedAccess(BAI, SubPath);
    }

    if (BAI->getAccessKind() == SILAccessKind::Read)
      Reads++;
    else
      NonReads++;
  }

  /// Decrement the count for given access.
  void endAccess(EndAccessInst *EAI) {
    if (EAI->getBeginAccess()->getAccessKind() == SILAccessKind::Read)
      Reads--;
    else
      NonReads--;

    // If all open accesses are now ended, forget the location of the
    // first access.
    if (Reads == 0 && NonReads == 0)
      FirstAccess = None;
  }

  /// Returns true when there are any accesses to this location in progress.
  bool hasAccessesInProgress() const { return Reads > 0 || NonReads > 0; }

  /// Returns true when there must have already been a conflict diagnosed
  /// for an in-progress access. Used to suppress multiple diagnostics for
  /// the same underlying access violation.
  bool alreadyHadConflict() const {
    return (NonReads > 0 && Reads > 0) || (NonReads > 1);
  }

  // Returns true when beginning an access of the given Kind can
  // result in a conflict with a previous access.
  bool canConflictWithAccessOfKind(SILAccessKind Kind) const {
    if (Kind == SILAccessKind::Read) {
      // A read conflicts with any non-read accesses.
      return NonReads > 0;
    }

    // A non-read access conflicts with any other access.
    return NonReads > 0 || Reads > 0;
  }

  bool conflictsWithAccess(SILAccessKind Kind,
                           const IndexTrieNode *SubPath) const {
    if (!canConflictWithAccessOfKind(Kind))
      return false;

    return pathsConflict(Path, SubPath);
  }

  /// Returns true when the two subpaths access overlapping memory.
  bool pathsConflict(const IndexTrieNode *Path1,
                     const IndexTrieNode *Path2) const {
    return Path1->isPrefixOf(Path2) || Path2->isPrefixOf(Path1);
  }
};

/// Models the in-progress accesses for an address on which access has begun
/// with a begin_access instruction. For a given address, tracks the
/// count and kinds of accesses as well as the subpaths (i.e., projections) that
/// were accessed.
class AccessInfo {
  using SubAccessVector = SmallVector<SubAccessInfo, 4>;

  SubAccessVector SubAccesses;

  /// Returns the SubAccess info for accessing at the given SubPath.
  SubAccessInfo &findOrCreateSubAccessInfo(const IndexTrieNode *SubPath) {
    for (auto &Info : SubAccesses) {
      if (Info.Path == SubPath)
        return Info;
    }

    SubAccesses.emplace_back(SubPath);
    return SubAccesses.back();
  }

  SubAccessVector::const_iterator
  findFirstSubPathWithConflict(SILAccessKind OtherKind,
                               const IndexTrieNode *OtherSubPath) const {
    // Note this iteration requires deterministic ordering for repeatable
    // diagnostics.
    for (auto I = SubAccesses.begin(), E = SubAccesses.end(); I != E; ++I) {
      const SubAccessInfo &Access = *I;
      if (Access.conflictsWithAccess(OtherKind, OtherSubPath))
        return I;
    }

    return SubAccesses.end();
  }

public:
  // Returns the previous access when beginning an access of the given Kind will
  // result in a conflict with a previous access.
  Optional<RecordedAccess>
  conflictsWithAccess(SILAccessKind Kind, const IndexTrieNode *SubPath) const {
    auto I = findFirstSubPathWithConflict(Kind, SubPath);
    if (I == SubAccesses.end())
      return None;

    return I->FirstAccess;
  }

  /// Returns true if any subpath of has already had a conflict.
  bool alreadyHadConflict() const {
    for (const auto &SubAccess : SubAccesses) {
      if (SubAccess.alreadyHadConflict())
        return true;
    }
    return false;
  }

  /// Returns true when there are any accesses to this location in progress.
  bool hasAccessesInProgress() const {
    for (const auto &SubAccess : SubAccesses) {
      if (SubAccess.hasAccessesInProgress())
        return true;
    }
    return false;
  }

  /// Increment the count for given access.
  void beginAccess(BeginAccessInst *BAI, const IndexTrieNode *SubPath) {
    SubAccessInfo &SubAccess = findOrCreateSubAccessInfo(SubPath);
    SubAccess.beginAccess(BAI, SubPath);
  }

  /// Decrement the count for given access.
  void endAccess(EndAccessInst *EAI, const IndexTrieNode *SubPath) {
    SubAccessInfo &SubAccess = findOrCreateSubAccessInfo(SubPath);
    SubAccess.endAccess(EAI);
  }
};

/// Indicates whether a 'begin_access' requires exclusive access
/// or allows shared access. This needs to be kept in sync with
/// diag::exclusivity_access_required, exclusivity_access_required_swift3,
/// and diag::exclusivity_conflicting_access.
enum class ExclusiveOrShared_t : unsigned {
  ExclusiveAccess = 0,
  SharedAccess = 1
};


/// Tracks the in-progress accesses on per-storage-location basis.
using StorageMap = llvm::SmallDenseMap<AccessedStorage, AccessInfo, 4>;

/// Represents two accesses that conflict and their underlying storage.
struct ConflictingAccess {
  /// Create a conflict for two begin_access instructions in the same function.
  ConflictingAccess(const AccessedStorage &Storage, const RecordedAccess &First,
                    const RecordedAccess &Second)
      : Storage(Storage), FirstAccess(First), SecondAccess(Second) {}

  const AccessedStorage Storage;
  const RecordedAccess FirstAccess;
  const RecordedAccess SecondAccess;
};

} // end anonymous namespace

/// Returns whether an access of the given kind requires exclusive or shared
/// access to its storage.
static ExclusiveOrShared_t getRequiredAccess(SILAccessKind Kind) {
  if (Kind == SILAccessKind::Read)
    return ExclusiveOrShared_t::SharedAccess;

  return ExclusiveOrShared_t::ExclusiveAccess;
}

/// Extract the text for the given expression.
static StringRef extractExprText(const Expr *E, SourceManager &SM) {
  const auto CSR = Lexer::getCharSourceRangeFromSourceRange(SM,
      E->getSourceRange());
  return SM.extractText(CSR);
}

/// Returns true when the call expression is a call to swap() in the Standard
/// Library.
/// This is a helper function that is only used in an assertion, which is why
/// it is in the ifndef.
#ifndef NDEBUG
static bool isCallToStandardLibrarySwap(CallExpr *CE, ASTContext &Ctx) {
  if (CE->getCalledValue() == Ctx.getSwap())
    return true;

  // Is the call module qualified, i.e. Swift.swap(&a[i], &[j)?
  if (auto *DSBIE = dyn_cast<DotSyntaxBaseIgnoredExpr>(CE->getFn())) {
    if (auto *DRE = dyn_cast<DeclRefExpr>(DSBIE->getRHS())) {
      return DRE->getDecl() == Ctx.getSwap();
    }
  }

  return false;
}
#endif

/// Do a syntactic pattern match to determine whether the call is a call
/// to swap(&base[index1], &base[index2]), which can
/// be replaced with a call to MutableCollection.swapAt(_:_:) on base.
///
/// Returns true if the call can be replaced. Returns the call expression,
/// the base expression, and the two indices as out expressions.
///
/// This method takes an array of all the ApplyInsts for calls to swap()
/// in the function to avoid needing to construct a parent map over the AST
/// to find the CallExpr for the inout accesses.
static bool
canReplaceWithCallToCollectionSwapAt(const BeginAccessInst *Access1,
                                     const BeginAccessInst *Access2,
                                     ArrayRef<ApplyInst *> CallsToSwap,
                                     ASTContext &Ctx,
                                     CallExpr *&FoundCall,
                                     Expr *&Base,
                                     Expr *&Index1,
                                     Expr *&Index2) {
  if (CallsToSwap.empty())
    return false;

  // Inout arguments must be modifications.
  if (Access1->getAccessKind() != SILAccessKind::Modify ||
      Access2->getAccessKind() != SILAccessKind::Modify) {
    return false;
  }

  SILLocation Loc1 = Access1->getLoc();
  SILLocation Loc2 = Access2->getLoc();
  if (Loc1.isNull() || Loc2.isNull())
    return false;

  auto *InOut1 = Loc1.getAsASTNode<InOutExpr>();
  auto *InOut2 = Loc2.getAsASTNode<InOutExpr>();
  if (!InOut1 || !InOut2)
    return false;

  FoundCall = nullptr;
  // Look through all the calls to swap() recorded in the function to find
  // which one we're diagnosing.
  for (ApplyInst *AI : CallsToSwap) {
    SILLocation CallLoc = AI->getLoc();
    if (CallLoc.isNull())
      continue;

    auto *CE = CallLoc.getAsASTNode<CallExpr>();
    if (!CE)
      continue;

    assert(isCallToStandardLibrarySwap(CE, Ctx));
    // swap() takes two arguments.
    auto *ArgTuple = cast<TupleExpr>(CE->getArg());
    const Expr *Arg1 = ArgTuple->getElement(0);
    const Expr *Arg2 = ArgTuple->getElement(1);
    if ((Arg1 == InOut1 && Arg2 == InOut2)) {
        FoundCall = CE;
      break;
    }
  }
  if (!FoundCall)
    return false;

  // We found a call to swap(&e1, &e2). Now check to see whether it
  // matches the form swap(&someCollection[index1], &someCollection[index2]).
  auto *SE1 = dyn_cast<SubscriptExpr>(InOut1->getSubExpr());
  if (!SE1)
    return false;
  auto *SE2 = dyn_cast<SubscriptExpr>(InOut2->getSubExpr());
  if (!SE2)
    return false;

  // Do the two subscripts refer to the same subscript declaration?
  auto *Decl1 = cast<SubscriptDecl>(SE1->getDecl().getDecl());
  auto *Decl2 = cast<SubscriptDecl>(SE2->getDecl().getDecl());
  if (Decl1 != Decl2)
    return false;

  ProtocolDecl *MutableCollectionDecl = Ctx.getMutableCollectionDecl();

  // Is the subcript either (1) on MutableCollection itself or (2) a
  // a witness for a subscript on MutableCollection?
  bool IsSubscriptOnMutableCollection = false;
  ProtocolDecl *ProtocolForDecl =
      Decl1->getDeclContext()->getSelfProtocolDecl();
  if (ProtocolForDecl) {
    IsSubscriptOnMutableCollection = (ProtocolForDecl == MutableCollectionDecl);
  } else {
    for (ValueDecl *Req : Decl1->getSatisfiedProtocolRequirements()) {
      DeclContext *ReqDC = Req->getDeclContext();
      ProtocolDecl *ReqProto = ReqDC->getSelfProtocolDecl();
      assert(ReqProto && "Protocol requirement not in a protocol?");

      if (ReqProto == MutableCollectionDecl) {
        IsSubscriptOnMutableCollection = true;
        break;
      }
    }
  }

  if (!IsSubscriptOnMutableCollection)
    return false;

  // We're swapping two subscripts on mutable collections -- but are they
  // the same collection? Approximate this by checking for textual
  // equality on the base expressions. This is just an approximation,
  // but is fine for a best-effort Fix-It.
  SourceManager &SM = Ctx.SourceMgr;
  StringRef Base1Text = extractExprText(SE1->getBase(), SM);
  StringRef Base2Text = extractExprText(SE2->getBase(), SM);

  if (Base1Text != Base2Text)
    return false;

  auto *Index1Paren = dyn_cast<ParenExpr>(SE1->getIndex());
  if (!Index1Paren)
    return false;

  auto *Index2Paren = dyn_cast<ParenExpr>(SE2->getIndex());
  if (!Index2Paren)
    return false;

  Base = SE1->getBase();
  Index1 = Index1Paren->getSubExpr();
  Index2 = Index2Paren->getSubExpr();
  return true;
}

/// Suggest replacing with call with a call to swapAt().
static void addSwapAtFixit(InFlightDiagnostic &Diag, CallExpr *&FoundCall,
                           Expr *Base, Expr *&Index1, Expr *&Index2,
                           SourceManager &SM) {
  StringRef BaseText = extractExprText(Base, SM);
  StringRef Index1Text = extractExprText(Index1, SM);
  StringRef Index2Text = extractExprText(Index2, SM);
  SmallString<64> FixItText;
  {
    llvm::raw_svector_ostream Out(FixItText);
    Out << BaseText << ".swapAt(" << Index1Text << ", " << Index2Text << ")";
  }

  Diag.fixItReplace(FoundCall->getSourceRange(), FixItText);
}

/// Returns a string representation of the BaseName and the SubPath
/// suitable for use in diagnostic text. Only supports the Projections
/// that stored-property relaxation supports: struct stored properties
/// and tuple elements.
static std::string getPathDescription(DeclName BaseName, SILType BaseType,
                                      const IndexTrieNode *SubPath,
                                      SILModule &M) {
  std::string sbuf;
  llvm::raw_string_ostream os(sbuf);

  os << "'" << BaseName;
  os << AccessSummaryAnalysis::getSubPathDescription(BaseType, SubPath, M);
  os << "'";

  return os.str();
}

/// Emits a diagnostic if beginning an access with the given in-progress
/// accesses violates the law of exclusivity. Returns true when a
/// diagnostic was emitted.
static void diagnoseExclusivityViolation(const ConflictingAccess &Violation,
                                         ArrayRef<ApplyInst *> CallsToSwap,
                                         ASTContext &Ctx) {

  const AccessedStorage &Storage = Violation.Storage;
  const RecordedAccess &FirstAccess = Violation.FirstAccess;
  const RecordedAccess &SecondAccess = Violation.SecondAccess;
  SILFunction *F = FirstAccess.getInstruction()->getFunction();

  LLVM_DEBUG(llvm::dbgs() << "Conflict on " << *FirstAccess.getInstruction()
                          << "\n  vs " << *SecondAccess.getInstruction()
                          << "\n  in function " << *F);

  // Can't have a conflict if both accesses are reads.
  assert(!(FirstAccess.getAccessKind() == SILAccessKind::Read &&
           SecondAccess.getAccessKind() == SILAccessKind::Read));

  ExclusiveOrShared_t FirstRequires =
      getRequiredAccess(FirstAccess.getAccessKind());

  // Diagnose on the first access that requires exclusivity.
  bool FirstIsMain = (FirstRequires == ExclusiveOrShared_t::ExclusiveAccess);
  const RecordedAccess &MainAccess = (FirstIsMain ? FirstAccess : SecondAccess);
  const RecordedAccess &NoteAccess = (FirstIsMain ? SecondAccess : FirstAccess);

  SourceRange RangeForMain = MainAccess.getAccessLoc().getSourceRange();
  unsigned AccessKindForMain =
      static_cast<unsigned>(MainAccess.getAccessKind());

  if (const ValueDecl *VD = Storage.getDecl(F)) {
    // We have a declaration, so mention the identifier in the diagnostic.
    SILType BaseType = FirstAccess.getInstruction()->getType().getAddressType();
    SILModule &M = FirstAccess.getInstruction()->getModule();
    std::string PathDescription = getPathDescription(
        VD->getBaseName(), BaseType, MainAccess.getSubPath(), M);

    // Determine whether we can safely suggest replacing the violation with
    // a call to MutableCollection.swapAt().
    bool SuggestSwapAt = false;
    CallExpr *CallToReplace = nullptr;
    Expr *Base = nullptr;
    Expr *SwapIndex1 = nullptr;
    Expr *SwapIndex2 = nullptr;
    if (SecondAccess.getRecordKind() == RecordedAccessKind::BeginInstruction) {
        SuggestSwapAt = canReplaceWithCallToCollectionSwapAt(
            FirstAccess.getInstruction(), SecondAccess.getInstruction(),
            CallsToSwap, Ctx, CallToReplace, Base, SwapIndex1, SwapIndex2);
    }

    auto D =
        diagnose(Ctx, MainAccess.getAccessLoc().getSourceLoc(),
                 diag::exclusivity_access_required,
                 PathDescription, AccessKindForMain, SuggestSwapAt);
    D.highlight(RangeForMain);
    if (SuggestSwapAt)
      addSwapAtFixit(D, CallToReplace, Base, SwapIndex1, SwapIndex2,
                     Ctx.SourceMgr);
  } else {
    diagnose(Ctx, MainAccess.getAccessLoc().getSourceLoc(),
             diag::exclusivity_access_required_unknown_decl, AccessKindForMain)
        .highlight(RangeForMain);
  }
  diagnose(Ctx, NoteAccess.getAccessLoc().getSourceLoc(),
           diag::exclusivity_conflicting_access)
      .highlight(NoteAccess.getAccessLoc().getSourceRange());
}

/// Look through a value to find the underlying storage accessed.
static AccessedStorage findValidAccessedStorage(SILValue Source) {
  const AccessedStorage &Storage = findAccessedStorage(Source);
  if (!Storage) {
    llvm::dbgs() << "Bad memory access source: " << Source;
    llvm_unreachable("Unexpected access source.");
  }
  return Storage;
}

/// Returns true when the apply calls the Standard Library swap().
/// Used for fix-its to suggest replacing with Collection.swapAt()
/// on exclusivity violations.
static bool isCallToStandardLibrarySwap(ApplyInst *AI, ASTContext &Ctx) {
  SILFunction *SF = AI->getReferencedFunction();
  if (!SF)
    return false;

  if (!SF->hasLocation())
    return false;

  auto *FD = SF->getLocation().getAsASTNode<FuncDecl>();
  if (!FD)
    return false;

  return FD == Ctx.getSwap();
}

static llvm::cl::opt<bool> ShouldAssertOnFailure(
    "sil-assert-on-exclusivity-failure",
    llvm::cl::desc("Should the compiler assert when it diagnoses conflicting "
                   "accesses rather than emitting a diagnostic? Intended for "
                   "use only with debugging."));

/// If making an access of the given kind at the given subpath would
/// would conflict, returns the first recorded access it would conflict
/// with. Otherwise, returns None.
static Optional<RecordedAccess>
shouldReportAccess(const AccessInfo &Info,swift::SILAccessKind Kind,
                   const IndexTrieNode *SubPath) {
  if (Info.alreadyHadConflict())
    return None;

  auto result = Info.conflictsWithAccess(Kind, SubPath);
  if (ShouldAssertOnFailure && result.hasValue())
    llvm_unreachable("Standard assertion routine.");
  return result;
}

/// For each projection that the summarized function accesses on its
/// capture, check whether the access conflicts with already-in-progress
/// access. Returns the most general summarized conflict -- so if there are
/// two conflicts in the called function and one is for an access to an
/// aggregate and another is for an access to a projection from the aggregate,
/// this will return the conflict for the aggregate. This approach guarantees
/// determinism and makes it more  likely that we'll diagnose the most helpful
/// conflict.
static Optional<ConflictingAccess>
findConflictingArgumentAccess(const AccessSummaryAnalysis::ArgumentSummary &AS,
                              const AccessedStorage &AccessedStorage,
                              const AccessInfo &InProgressInfo) {
  Optional<RecordedAccess> BestInProgressAccess;
  Optional<RecordedAccess> BestArgAccess;

  for (const auto &MapPair : AS.getSubAccesses()) {
    const IndexTrieNode *SubPath = MapPair.getFirst();
    const auto &SubAccess = MapPair.getSecond();
    SILAccessKind Kind = SubAccess.getAccessKind();
    auto InProgressAccess = shouldReportAccess(InProgressInfo, Kind, SubPath);
    if (!InProgressAccess)
      continue;

    if (!BestArgAccess ||
        AccessSummaryAnalysis::compareSubPaths(SubPath,
                                               BestArgAccess->getSubPath())) {
        SILLocation AccessLoc = SubAccess.getAccessLoc();

        BestArgAccess = RecordedAccess(Kind, AccessLoc, SubPath);
        BestInProgressAccess = InProgressAccess;
    }
  }

  if (!BestArgAccess)
    return None;

  return ConflictingAccess(AccessedStorage, *BestInProgressAccess,
                           *BestArgAccess);
}

// =============================================================================
// The data flow algorithm that drives diagnostics.

// Forward declare verification entry points.
#ifndef NDEBUG
static void checkNoEscapePartialApply(PartialApplyInst *PAI);
#endif
static void checkAccessedAddress(Operand *memOper, StorageMap &Accesses);

namespace {
/// Track the current state of formal accesses, including exclusivity
/// violations, and function summaries at a particular point in the program.
struct AccessState {
  AccessSummaryAnalysis *ASA;

  // Stores the accesses that have been found to conflict. Used to defer
  // emitting diagnostics until we can determine whether they should
  // be suppressed.
  llvm::SmallVector<ConflictingAccess, 4> ConflictingAccesses;

  // Collects calls the Standard Library swap() for Fix-Its.
  llvm::SmallVector<ApplyInst *, 8> CallsToSwap;

  StorageMap *Accesses = nullptr;

  AccessState(AccessSummaryAnalysis *ASA) : ASA(ASA) {}
};
} // namespace

/// For each argument in the range of the callee arguments being applied at the
/// given apply site, use the summary analysis to determine whether the
/// arguments will be accessed in a way that conflicts with any currently in
/// progress accesses. If so, diagnose.
static void checkCaptureAccess(ApplySite Apply, AccessState &State) {
  SILFunction *Callee = Apply.getCalleeFunction();
  if (!Callee || Callee->empty())
    return;

  const AccessSummaryAnalysis::FunctionSummary &FS =
      State.ASA->getOrCreateSummary(Callee);

  for (unsigned ArgumentIndex : range(Apply.getNumArguments())) {

    unsigned CalleeIndex =
        Apply.getCalleeArgIndexOfFirstAppliedArg() + ArgumentIndex;

    const AccessSummaryAnalysis::ArgumentSummary &AS =
        FS.getAccessForArgument(CalleeIndex);

    const auto &SubAccesses = AS.getSubAccesses();

    // Is the capture accessed in the callee?
    if (SubAccesses.empty())
      continue;

    SILValue Argument = Apply.getArgument(ArgumentIndex);
    assert(Argument->getType().isAddress());

    // A valid AccessedStorage should alway sbe found because Unsafe accesses
    // are not tracked by AccessSummaryAnalysis.
    const AccessedStorage &Storage = findValidAccessedStorage(Argument);
    auto AccessIt = State.Accesses->find(Storage);

    // Are there any accesses in progress at the time of the call?
    if (AccessIt == State.Accesses->end())
      continue;

    const AccessInfo &Info = AccessIt->getSecond();
    if (auto Conflict = findConflictingArgumentAccess(AS, Storage, Info))
      State.ConflictingAccesses.push_back(*Conflict);
  }
}

/// If the given values has a SILFunctionType or an Optional<SILFunctionType>,
/// return the SILFunctionType. Otherwise, return an invalid type.
static CanSILFunctionType getSILFunctionTypeForValue(SILValue arg) {
  SILType argTy = arg->getType();
  // Handle `Optional<@convention(block) @noescape (_)->(_)>`
  if (auto optionalObjTy = argTy.getOptionalObjectType())
    argTy = optionalObjTy;

  return argTy.getAs<SILFunctionType>();
}

/// Recursively check for conflicts with in-progress accesses at the given
/// apply.
///
/// Any captured variable accessed by a noescape closure is considered to be
/// accessed at the point that the closure is fully applied. This includes
/// variables captured by address by the noescape closure being applied or by
/// any other noescape closure that is itself passed as an argument to that
/// closure.
///
/// (1) Use AccessSummaryAnalysis to check each argument for statically
/// enforced accesses nested within the callee.
///
/// (2) If an applied argument is itself a function type, recursively check for
/// violations on the closure being passed as an argument.
///
/// (3) Walk up the chain of partial applies to recursively visit all arguments.
///
/// Note: This handles closures that are called immediately:
///  var i = 7
///  ({ (p: inout Int) in i = 8})(&i) // Overlapping access to 'i'
///
/// Note: This handles chains of partial applies:
///   pa1 = partial_apply f(c) : $(a, b, c)
///   pa2 = partial_apply pa1(b) : $(a, b)
///   apply pa2(a)
static void checkForViolationAtApply(ApplySite Apply, AccessState &State) {
  // First, check access to variables immediately captured at this apply site.
  checkCaptureAccess(Apply, State);

  // Next, recursively check any noescape closures passed as arguments at this
  // apply site.
  TinyPtrVector<PartialApplyInst *> partialApplies;
  for (SILValue Argument : Apply.getArguments()) {
    auto FnType = getSILFunctionTypeForValue(Argument);
    if (!FnType || !FnType->isNoEscape())
      continue;

    findClosuresForFunctionValue(Argument, partialApplies);
  }
  // Continue recursively walking up the chain of applies if necessary.
  findClosuresForFunctionValue(Apply.getCallee(), partialApplies);

  for (auto *PAI : partialApplies)
    checkForViolationAtApply(ApplySite(PAI), State);
}

// Apply transfer function to the AccessState. Beginning an access
// increments the read or write count for the storage location;
// Ending one decrements the count.
static void checkForViolationsAtInstruction(SILInstruction &I,
                                            AccessState &State) {
  if (auto *BAI = dyn_cast<BeginAccessInst>(&I)) {
    if (BAI->getEnforcement() == SILAccessEnforcement::Unsafe)
      return;

    SILAccessKind Kind = BAI->getAccessKind();
    const AccessedStorage &Storage =
      findValidAccessedStorage(BAI->getSource());
    // Storage may be associated with a nested access where the outer access is
    // "unsafe". That's ok because the outer access can itself be treated like a
    // valid source, as long as we don't ask for its source.
    AccessInfo &Info = (*State.Accesses)[Storage];
    const IndexTrieNode *SubPath = State.ASA->findSubPathAccessed(BAI);
    if (auto Conflict = shouldReportAccess(Info, Kind, SubPath)) {
      State.ConflictingAccesses.emplace_back(Storage, *Conflict,
                                             RecordedAccess(BAI, SubPath));
    }

    Info.beginAccess(BAI, SubPath);
    return;
  }

  if (auto *EAI = dyn_cast<EndAccessInst>(&I)) {
    if (EAI->getBeginAccess()->getEnforcement() == SILAccessEnforcement::Unsafe)
      return;

    auto It =
      State.Accesses->find(findValidAccessedStorage(EAI->getSource()));
    AccessInfo &Info = It->getSecond();

    BeginAccessInst *BAI = EAI->getBeginAccess();
    const IndexTrieNode *SubPath = State.ASA->findSubPathAccessed(BAI);
    Info.endAccess(EAI, SubPath);

    // If the storage location has no more in-progress accesses, remove
    // it to keep the StorageMap lean.
    if (!Info.hasAccessesInProgress())
      State.Accesses->erase(It);
    return;
  }

  if (I.getModule().getOptions().VerifyExclusivity && I.mayReadOrWriteMemory()) {
    visitAccessedAddress(&I, [&State](Operand *memOper) {
        checkAccessedAddress(memOper, *State.Accesses);
      });
  }

  if (auto *AI = dyn_cast<ApplyInst>(&I)) {
    // Record calls to swap() for potential Fix-Its.
    if (isCallToStandardLibrarySwap(AI, I.getFunction()->getASTContext()))
      State.CallsToSwap.push_back(AI);
    else
      checkForViolationAtApply(AI, State);
    return;
  }

  if (auto *TAI = dyn_cast<TryApplyInst>(&I)) {
    checkForViolationAtApply(TAI, State);
    return;
  }
#ifndef NDEBUG
  // FIXME: Once AllocBoxToStack is fixed to correctly set noescape
  // closure types, move this PartialApply verification into the
  // SILVerifier to better pinpoint the offending pass.
  if (auto *PAI = dyn_cast<PartialApplyInst>(&I)) {
    ApplySite apply(PAI);
    if (llvm::any_of(apply.getArgumentOperands(), [apply](Operand &oper) {
          return apply.getArgumentConvention(oper)
                 == SILArgumentConvention::Indirect_InoutAliasable;
        })) {
      checkNoEscapePartialApply(PAI);
    }
  }
#endif
  // Sanity check to make sure entries are properly removed.
  assert((!isa<ReturnInst>(&I) || State.Accesses->empty())
         && "Entries were not properly removed?!");
}

static void checkStaticExclusivity(SILFunction &Fn, PostOrderFunctionInfo *PO,
                                   AccessSummaryAnalysis *ASA) {
  // The implementation relies on the following SIL invariants:
  //    - All incoming edges to a block must have the same in-progress
  //      accesses. This enables the analysis to not perform a data flow merge
  //      on incoming edges.
  //    - Further, for a given address each of the in-progress
  //      accesses must have begun in the same order on all edges. This ensures
  //      consistent diagnostics across changes to the exploration of the CFG.
  //    - On return from a function there are no in-progress accesses. This
  //      enables a sanity check for lean analysis state at function exit.
  //    - Each end_access instruction corresponds to exactly one begin access
  //      instruction. (This is encoded in the EndAccessInst itself)
  //    - begin_access arguments cannot be basic block arguments.
  //      This enables the analysis to look back to find the *single* storage
  //      storage location accessed.

  if (Fn.empty())
    return;

  AccessState State(ASA);

  // For each basic block, track the stack of current accesses on
  // exit from that block.
  llvm::SmallDenseMap<SILBasicBlock *, Optional<StorageMap>, 32>
      BlockOutAccesses;

  BlockOutAccesses[Fn.getEntryBlock()] = StorageMap();

  for (auto *BB : PO->getReversePostOrder()) {
    Optional<StorageMap> &BBState = BlockOutAccesses[BB];

    // Because we use a reverse post-order traversal, unless this is the entry
    // at least one of its predecessors must have been reached. Use the out
    // state for that predecessor as our in state. The SIL verifier guarantees
    // that all incoming edges must have the same current accesses.
    for (auto *Pred : BB->getPredecessorBlocks()) {
      auto it = BlockOutAccesses.find(Pred);
      if (it == BlockOutAccesses.end())
        continue;

      const Optional<StorageMap> &PredAccesses = it->getSecond();
      if (PredAccesses) {
        BBState = PredAccesses;
        break;
      }
    }

    // The in-progress accesses for the current program point, represented
    // as map from storage locations to the accesses in progress for the
    // location.
    State.Accesses = BBState.getPointer();
    for (auto &I : *BB)
      checkForViolationsAtInstruction(I, State);
  }

  // Now that we've collected violations and suppressed calls, emit
  // diagnostics.
  for (auto &Violation : State.ConflictingAccesses) {
    diagnoseExclusivityViolation(Violation, State.CallsToSwap,
                                 Fn.getASTContext());
  }
}

// =============================================================================
// Verification

#ifndef NDEBUG
// This must handle exactly the same SIL patterns as
// swift::funcClosureForAppliedArg but in forward order.
template <typename FollowUse>
static void checkNoEscapePartialApplyUse(Operand *oper, FollowUse followUses) {
  SILInstruction *user = oper->getUser();

  // Ignore uses that are totally uninteresting.
  if (isIncidentalUse(user) || onlyAffectsRefCount(user))
    return;

  // Before checking conversions in general below (getSingleValueCopyOrCast),
  // check for convert_function to [without_actually_escaping]. Assume such
  // conversion are not actually escaping without following their uses.
  if (auto *CFI = dyn_cast<ConvertFunctionInst>(user)) {
    if (CFI->withoutActuallyEscaping())
      return;
  }

  // Look through copies, borrows, and conversions.
  if (SingleValueInstruction *copy = getSingleValueCopyOrCast(user)) {
    // Only follow the copied operand. Other operands are incidental,
    // as in the second operand of mark_dependence.
    if (oper->getOperandNumber() == 0)
      followUses(copy);

    return;
  }

  switch (user->getKind()) {
  default:
    break;

  // Look through Optionals.
  case SILInstructionKind::EnumInst:
    // @noescape block storage can be passed as an Optional (Nullable).
    followUses(cast<EnumInst>(user));
    return;

  // Look through Phis.
  case SILInstructionKind::BranchInst: {
    const SILPhiArgument *arg = cast<BranchInst>(user)->getArgForOperand(oper);
    followUses(arg);
    return;
  }
  case SILInstructionKind::CondBranchInst: {
    const SILPhiArgument *arg =
        cast<CondBranchInst>(user)->getArgForOperand(oper);
    if (arg) // If the use isn't the branch condition, follow it.
      followUses(arg);
    return;
  }
  // Look through ObjC closures.
  case SILInstructionKind::StoreInst:
    if (oper->getOperandNumber() == StoreInst::Src) {
      if (auto *PBSI = dyn_cast<ProjectBlockStorageInst>(
            cast<StoreInst>(user)->getDest())) {
        SILValue storageAddr = PBSI->getOperand();
        // The closure is stored to block storage. Recursively visit all
        // uses of any initialized block storage values derived from this
        // storage address..
        for (Operand *oper : storageAddr->getUses()) {
          if (auto *IBS = dyn_cast<InitBlockStorageHeaderInst>(oper->getUser()))
            followUses(IBS);
        }
        return;
      }
    }
    break;

  case SILInstructionKind::IsEscapingClosureInst:
    // May be generated by withoutActuallyEscaping.
    return;

  case SILInstructionKind::PartialApplyInst: {
    // Recurse through partial_apply to handle special cases before handling
    // ApplySites in general below.
    PartialApplyInst *PAI = cast<PartialApplyInst>(user);
    // Use the same logic as checkForViolationAtApply applied to a def-use
    // traversal.
    //
    // checkForViolationAtApply recurses through partial_apply chains.
    if (oper->get() == PAI->getCallee()) {
      followUses(PAI);
      return;
    }
    // checkForViolationAtApply also uses findClosuresForAppliedArg which in
    // turn checks isPartialApplyOfReabstractionThunk.
    //
    // A closure with @inout_aliasable arguments may be applied to a
    // thunk as "escaping", but as long as the thunk is only used as a
    // '@noescape" type then it is safe.
    if (isPartialApplyOfReabstractionThunk(PAI)) {
      // Don't follow thunks that were generated by withoutActuallyEscaping.
      SILFunction *thunkDef = PAI->getReferencedFunction();
      if (!thunkDef->isWithoutActuallyEscapingThunk())
        followUses(PAI);
      return;
    }
    // Handle this use like a normal applied argument.
    break;
  }
  };

  // Handle ApplySites in general after checking PartialApply above.
  if (isa<ApplySite>(user)) {
    SILValue arg = oper->get();
    auto argumentFnType = getSILFunctionTypeForValue(arg);
    if (argumentFnType && argumentFnType->isNoEscape()) {
      // Verify that the inverse operation, finding a partial_apply from a
      // @noescape argument, is consistent.
      TinyPtrVector<PartialApplyInst *> partialApplies;
      findClosuresForFunctionValue(arg, partialApplies);
      assert(!partialApplies.empty()
             && "cannot find partial_apply from @noescape function argument");
      return;
    }
    llvm::dbgs() << "Applied argument must be @noescape function type: " << *arg;
  }
  else
    llvm::dbgs() << "Unexpected partial_apply use: " << *user;

  llvm_unreachable("A partial_apply with @inout_aliasable may only be "
                   "used as a @noescape function type argument.");
}

// If a partial apply has @inout_aliasable arguments, it may only be used as
// a @noescape function type in a way that is recognized by
// DiagnoseStaticExclusivity.
static void checkNoEscapePartialApply(PartialApplyInst *PAI) {
  SmallVector<Operand *, 8> uses;
  // Avoid exponential path exploration.
  llvm::SmallDenseSet<Operand *, 8> visited;
  auto uselistInsert = [&](Operand *operand) {
    if (visited.insert(operand).second)
      uses.push_back(operand);
  };

  for (Operand *use : PAI->getUses())
    uselistInsert(use);

  while (!uses.empty()) {
    Operand *oper = uses.pop_back_val();
    checkNoEscapePartialApplyUse(oper, [&](SILValue V) {
      for (Operand *use : V->getUses())
        uselistInsert(use);
    });
  }
}
#endif

// Check that the given address-type operand is guarded by begin/end access
// markers.
static void checkAccessedAddress(Operand *memOper, StorageMap &Accesses) {
  SILValue address = memOper->get();
  SILInstruction *memInst = memOper->getUser();

  auto error = [address, memInst]() {
    llvm::dbgs() << "Memory access not protected by begin_access:\n";
    memInst->printInContext(llvm::dbgs());
    llvm::dbgs() << "Accessing: " << address;
    llvm::dbgs() << "In function:\n";
    memInst->getFunction()->print(llvm::dbgs());
    abort();
  };

  // If the memory instruction is only used for initialization, it doesn't need
  // an access marker.
  if (memInstMustInitialize(memOper))
    return;

  if (auto apply = ApplySite::isa(memInst)) {
    SILArgumentConvention conv = apply.getArgumentConvention(*memOper);
    // Captured addresses currently use the @inout_aliasable convention. They
    // are considered an access at any call site that uses the closure. However,
    // those accesses are never explictly protected by access markers. Instead,
    // exclusivity uses AccessSummaryAnalysis to check for conflicts. Here, we
    // can simply ignore any @inout_aliasable arguments.
    if (conv == SILArgumentConvention::Indirect_InoutAliasable)
      return;

    assert(!isa<PartialApplyInst>(memInst)
           && "partial apply can only capture an address as inout_aliasable");
    // TODO: We currently assume @in/@in_guaranteed are only used for
    // pass-by-value arguments. i.e. the address points a local copy of the
    // argument, which is only passed by address for abstraction
    // reasons. However, in the future, @in_guaranteed may be used for
    // borrowed values, which should be recognized as a formal read.
    if (conv != SILArgumentConvention::Indirect_Inout)
      return;
  }

  // Strip off address projections, but not ref_element_addr.
  const AccessedStorage &storage = findAccessedStorage(address);
  // findAccessedStorage may return an invalid storage object if the address
  // producer is not recognized by its whitelist. For the purpose of
  // verification, we assume that this can only happen for local
  // initialization, not a formal memory access. The strength of
  // verification rests on the completeness of the opcode list inside
  // findAccessedStorage.
  //
  // For the purpose of verification, an unidentified access is
  // unenforced. These occur in cases like global addressors and local buffers
  // that make use of RawPointers.
  if (!storage || storage.getKind() == AccessedStorage::Unidentified)
    return;

  // Some identifiable addresses can also be recognized as local initialization
  // or other patterns that don't qualify as formal access.
  if (!isPossibleFormalAccessBase(storage, memInst->getFunction()))
    return;

  // A box or stack variable may represent lvalues, but they can only conflict
  // with call sites in the same scope. Some initialization patters (stores to
  // the local value) aren't protected by markers, so we need this check.
  if (!isa<ApplySite>(memInst)
      && (storage.getKind() == AccessedStorage::Box
          || storage.getKind() == AccessedStorage::Stack)) {
    return;
  }

  // Otherwise, the address base should be an in-scope begin_access.
  if (storage.getKind() == AccessedStorage::Nested) {
    auto *BAI = cast<BeginAccessInst>(storage.getValue());
    if (BAI->getEnforcement() == SILAccessEnforcement::Unsafe)
      return;

    const AccessedStorage &Storage = findValidAccessedStorage(BAI->getSource());
    AccessInfo &Info = Accesses[Storage];
    if (!Info.hasAccessesInProgress())
      error();
    return;
  }
  error();
}

// =============================================================================
// Function Pass Driver

namespace {

class DiagnoseStaticExclusivity : public SILFunctionTransform {
public:
  DiagnoseStaticExclusivity() {}

private:
  void run() override {
    // Don't rerun diagnostics on deserialized functions.
    if (getFunction()->wasDeserializedCanonical())
      return;

    SILFunction *Fn = getFunction();
    // This is a staging flag. Eventually the ability to turn off static
    // enforcement will be removed.
    if (!Fn->getModule().getOptions().EnforceExclusivityStatic)
      return;

    PostOrderFunctionInfo *PO = getAnalysis<PostOrderAnalysis>()->get(Fn);
    auto *ASA = getAnalysis<AccessSummaryAnalysis>();
    checkStaticExclusivity(*Fn, PO, ASA);
  }
};

} // end anonymous namespace

SILTransform *swift::createDiagnoseStaticExclusivity() {
  return new DiagnoseStaticExclusivity();
}