<commit_before>//===--- ASTScopeLookup.cpp - Swift Object-Oriented AST Scope -------------===//
//
// 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 the lookup functionality of the ASTScopeImpl ontology.
///
//===----------------------------------------------------------------------===//
#include "swift/AST/ASTScope.h"

#include "swift/AST/ASTContext.h"
#include "swift/AST/ASTWalker.h"
#include "swift/AST/Decl.h"
#include "swift/AST/Expr.h"
#include "swift/AST/Initializer.h"
#include "swift/AST/LazyResolver.h"
#include "swift/AST/Module.h"
#include "swift/AST/NameLookup.h"
#include "swift/AST/ParameterList.h"
#include "swift/AST/Pattern.h"
#include "swift/AST/SourceFile.h"
#include "swift/AST/Stmt.h"
#include "swift/AST/TypeRepr.h"
#include "swift/Basic/STLExtras.h"
#include "llvm/Support/Compiler.h"
#include <algorithm>

using namespace swift;
using namespace namelookup;
using namespace ast_scope;

static bool isLocWithinAnInactiveClause(const SourceLoc loc, SourceFile *SF);

llvm::SmallVector<const ASTScopeImpl *, 0> ASTScopeImpl::unqualifiedLookup(
    SourceFile *sourceFile, const DeclNameRef name, const SourceLoc loc,
    const DeclContext *const startingContext, DeclConsumer consumer) {
  SmallVector<const ASTScopeImpl *, 0> history;
  const auto *start =
      findStartingScopeForLookup(sourceFile, name, loc, startingContext);
  if (start)
    start->lookup(history, nullptr, nullptr, consumer);
  return history;
}

const ASTScopeImpl *ASTScopeImpl::findStartingScopeForLookup(
    SourceFile *sourceFile, const DeclNameRef name, const SourceLoc loc,
    const DeclContext *const startingContext) {
  // At present, use legacy code in unqualifiedLookup.cpp to handle module-level
  // lookups
  // TODO: implement module scope someday
  if (startingContext->getContextKind() == DeclContextKind::Module)
    return nullptr;

  auto *const fileScope = sourceFile->getScope().impl;
  // Parser may have added decls to source file, since previous lookup
  if (name.isOperator())
    return fileScope; // operators always at file scope

  const auto *innermost = fileScope->findInnermostEnclosingScope(loc, nullptr);
  ASTScopeAssert(innermost->getWasExpanded(),
                 "If looking in a scope, it must have been expanded.");

  // The legacy lookup code gets passed both a SourceLoc and a starting context.
  // However, our ultimate intent is for clients to not have to pass in a
  // DeclContext at all, since the SourceLoc should be enough. While we are
  // debugging the new ASTScope lookup code, we can catch bugs by comparing the
  // DeclContext of the ASTScope found from the desired SourceLoc to the
  // DeclContext passed in by the client.

  const auto *startingScope = innermost;
  for (; startingScope &&
         !startingScope->doesContextMatchStartingContext(startingContext);
       startingScope = startingScope->getParent().getPtrOrNull()) {
  }
  // Someday, just use the assertion below. For now, print out lots of info for
  // debugging.
  if (!startingScope) {

    // Be lenient in code completion mode. There are cases where the decl
    // context doesn't match with the ASTScope. e.g. dangling attributes.
    // FIXME: Create ASTScope tree even for invalid code.
    if (innermost &&
        startingContext->getASTContext().SourceMgr.hasCodeCompletionBuffer()) {
      return innermost;
    }

    llvm::errs() << "ASTScopeImpl: resorting to startingScope hack, file: "
                 << sourceFile->getFilename() << "\n";
    // The check is costly, and inactive lookups will end up here, so don't
    // do the check unless we can't find the startingScope.
    const bool isInInactiveClause =
        isLocWithinAnInactiveClause(loc, sourceFile);
    if (isInInactiveClause)
      llvm::errs() << "  because location is within an inactive clause\n";
    llvm::errs() << "'";
    name.print(llvm::errs());
    llvm::errs() << "' ";
    llvm::errs() << "loc: ";
    loc.print(llvm::errs(), sourceFile->getASTContext().SourceMgr);
    llvm::errs() << "\nstarting context:\n ";
    startingContext->printContext(llvm::errs());
    //    llvm::errs() << "\ninnermost: ";
    //    innermost->dump();
    //    llvm::errs() << "in: \n";
    //    fileScope->dump();
    llvm::errs() << "\n\n";

    // Might distort things
    //    if (fileScope->crossCheckWithAST())
    //      llvm::errs() << "Tree creation missed some DeclContexts.\n";

    // Crash compilation even if NDEBUG
    if (isInInactiveClause)
      llvm::report_fatal_error(
          "A lookup was attempted into an inactive clause");
  }

  ASTScopeAssert(startingScope, "ASTScopeImpl: could not find startingScope");
  return startingScope;
}

ASTScopeImpl *
ASTScopeImpl::findInnermostEnclosingScope(SourceLoc loc,
                                          NullablePtr<raw_ostream> os) {
  return findInnermostEnclosingScopeImpl(loc, os, getSourceManager(),
                                         getScopeCreator());
}

ASTScopeImpl *ASTScopeImpl::findInnermostEnclosingScopeImpl(
    SourceLoc loc, NullablePtr<raw_ostream> os, SourceManager &sourceMgr,
    ScopeCreator &scopeCreator) {
  expandAndBeCurrentDetectingRecursion(scopeCreator);
  auto child = findChildContaining(loc, sourceMgr);
  if (!child)
    return this;
  return child.get()->findInnermostEnclosingScopeImpl(loc, os, sourceMgr,
                                                      scopeCreator);
}

bool ASTScopeImpl::checkSourceRangeOfThisASTNode() const {
  const auto r = getSourceRangeOfThisASTNode();
  (void)r;
  ASTScopeAssert(!getSourceManager().isBeforeInBuffer(r.End, r.Start),
                 "Range is backwards.");
  return true;
}

/// If the \p loc is in a new buffer but \p range is not, consider the location
/// is at the start of replaced range. Otherwise, returns \p loc as is.
static SourceLoc translateLocForReplacedRange(SourceManager &sourceMgr,
                                              SourceRange range,
                                              SourceLoc loc) {
  if (const auto &replacedRange = sourceMgr.getReplacedRange()) {
    if (sourceMgr.rangeContainsTokenLoc(replacedRange.New, loc) &&
        !sourceMgr.rangeContains(replacedRange.New, range)) {
      return replacedRange.Original.Start;
    }
  }
  return loc;
}

NullablePtr<ASTScopeImpl>
ASTScopeImpl::findChildContaining(SourceLoc loc,
                                  SourceManager &sourceMgr) const {
  // Use binary search to find the child that contains this location.
  struct CompareLocs {
    SourceManager &sourceMgr;

    bool operator()(const ASTScopeImpl *scope, SourceLoc loc) {
      ASTScopeAssert(scope->checkSourceRangeOfThisASTNode(), "Bad range.");
      auto rangeOfScope = scope->getSourceRangeOfScope();
      loc = translateLocForReplacedRange(sourceMgr, rangeOfScope, loc);
      return -1 == ASTScopeImpl::compare(rangeOfScope, loc, sourceMgr,
                                         /*ensureDisjoint=*/false);
    }
    bool operator()(SourceLoc loc, const ASTScopeImpl *scope) {
      return !(*this)(scope, loc);
    }
  };
  auto *const *child = std::lower_bound(
      getChildren().begin(), getChildren().end(), loc, CompareLocs{sourceMgr});

  if (child != getChildren().end()) {
    auto rangeOfScope = (*child)->getSourceRangeOfScope();
    loc = translateLocForReplacedRange(sourceMgr, rangeOfScope, loc);
    if (sourceMgr.rangeContainsTokenLoc(rangeOfScope, loc))
      return *child;
  }

  return nullptr;
}

#pragma mark doesContextMatchStartingContext
// Match existing UnqualifiedLookupBehavior
<commit_msg>[ASTScope] Simplify binary search code in findChildContaining()<commit_after>//===--- ASTScopeLookup.cpp - Swift Object-Oriented AST Scope -------------===//
//
// 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 the lookup functionality of the ASTScopeImpl ontology.
///
//===----------------------------------------------------------------------===//
#include "swift/AST/ASTScope.h"

#include "swift/AST/ASTContext.h"
#include "swift/AST/ASTWalker.h"
#include "swift/AST/Decl.h"
#include "swift/AST/Expr.h"
#include "swift/AST/Initializer.h"
#include "swift/AST/LazyResolver.h"
#include "swift/AST/Module.h"
#include "swift/AST/NameLookup.h"
#include "swift/AST/ParameterList.h"
#include "swift/AST/Pattern.h"
#include "swift/AST/SourceFile.h"
#include "swift/AST/Stmt.h"
#include "swift/AST/TypeRepr.h"
#include "swift/Basic/STLExtras.h"
#include "llvm/Support/Compiler.h"

using namespace swift;
using namespace namelookup;
using namespace ast_scope;

static bool isLocWithinAnInactiveClause(const SourceLoc loc, SourceFile *SF);

llvm::SmallVector<const ASTScopeImpl *, 0> ASTScopeImpl::unqualifiedLookup(
    SourceFile *sourceFile, const DeclNameRef name, const SourceLoc loc,
    const DeclContext *const startingContext, DeclConsumer consumer) {
  SmallVector<const ASTScopeImpl *, 0> history;
  const auto *start =
      findStartingScopeForLookup(sourceFile, name, loc, startingContext);
  if (start)
    start->lookup(history, nullptr, nullptr, consumer);
  return history;
}

const ASTScopeImpl *ASTScopeImpl::findStartingScopeForLookup(
    SourceFile *sourceFile, const DeclNameRef name, const SourceLoc loc,
    const DeclContext *const startingContext) {
  // At present, use legacy code in unqualifiedLookup.cpp to handle module-level
  // lookups
  // TODO: implement module scope someday
  if (startingContext->getContextKind() == DeclContextKind::Module)
    return nullptr;

  auto *const fileScope = sourceFile->getScope().impl;
  // Parser may have added decls to source file, since previous lookup
  if (name.isOperator())
    return fileScope; // operators always at file scope

  const auto *innermost = fileScope->findInnermostEnclosingScope(loc, nullptr);
  ASTScopeAssert(innermost->getWasExpanded(),
                 "If looking in a scope, it must have been expanded.");

  // The legacy lookup code gets passed both a SourceLoc and a starting context.
  // However, our ultimate intent is for clients to not have to pass in a
  // DeclContext at all, since the SourceLoc should be enough. While we are
  // debugging the new ASTScope lookup code, we can catch bugs by comparing the
  // DeclContext of the ASTScope found from the desired SourceLoc to the
  // DeclContext passed in by the client.

  const auto *startingScope = innermost;
  for (; startingScope &&
         !startingScope->doesContextMatchStartingContext(startingContext);
       startingScope = startingScope->getParent().getPtrOrNull()) {
  }
  // Someday, just use the assertion below. For now, print out lots of info for
  // debugging.
  if (!startingScope) {

    // Be lenient in code completion mode. There are cases where the decl
    // context doesn't match with the ASTScope. e.g. dangling attributes.
    // FIXME: Create ASTScope tree even for invalid code.
    if (innermost &&
        startingContext->getASTContext().SourceMgr.hasCodeCompletionBuffer()) {
      return innermost;
    }

    llvm::errs() << "ASTScopeImpl: resorting to startingScope hack, file: "
                 << sourceFile->getFilename() << "\n";
    // The check is costly, and inactive lookups will end up here, so don't
    // do the check unless we can't find the startingScope.
    const bool isInInactiveClause =
        isLocWithinAnInactiveClause(loc, sourceFile);
    if (isInInactiveClause)
      llvm::errs() << "  because location is within an inactive clause\n";
    llvm::errs() << "'";
    name.print(llvm::errs());
    llvm::errs() << "' ";
    llvm::errs() << "loc: ";
    loc.print(llvm::errs(), sourceFile->getASTContext().SourceMgr);
    llvm::errs() << "\nstarting context:\n ";
    startingContext->printContext(llvm::errs());
    //    llvm::errs() << "\ninnermost: ";
    //    innermost->dump();
    //    llvm::errs() << "in: \n";
    //    fileScope->dump();
    llvm::errs() << "\n\n";

    // Might distort things
    //    if (fileScope->crossCheckWithAST())
    //      llvm::errs() << "Tree creation missed some DeclContexts.\n";

    // Crash compilation even if NDEBUG
    if (isInInactiveClause)
      llvm::report_fatal_error(
          "A lookup was attempted into an inactive clause");
  }

  ASTScopeAssert(startingScope, "ASTScopeImpl: could not find startingScope");
  return startingScope;
}

ASTScopeImpl *
ASTScopeImpl::findInnermostEnclosingScope(SourceLoc loc,
                                          NullablePtr<raw_ostream> os) {
  return findInnermostEnclosingScopeImpl(loc, os, getSourceManager(),
                                         getScopeCreator());
}

ASTScopeImpl *ASTScopeImpl::findInnermostEnclosingScopeImpl(
    SourceLoc loc, NullablePtr<raw_ostream> os, SourceManager &sourceMgr,
    ScopeCreator &scopeCreator) {
  expandAndBeCurrentDetectingRecursion(scopeCreator);
  auto child = findChildContaining(loc, sourceMgr);
  if (!child)
    return this;
  return child.get()->findInnermostEnclosingScopeImpl(loc, os, sourceMgr,
                                                      scopeCreator);
}

bool ASTScopeImpl::checkSourceRangeOfThisASTNode() const {
  const auto r = getSourceRangeOfThisASTNode();
  (void)r;
  ASTScopeAssert(!getSourceManager().isBeforeInBuffer(r.End, r.Start),
                 "Range is backwards.");
  return true;
}

/// If the \p loc is in a new buffer but \p range is not, consider the location
/// is at the start of replaced range. Otherwise, returns \p loc as is.
static SourceLoc translateLocForReplacedRange(SourceManager &sourceMgr,
                                              SourceRange range,
                                              SourceLoc loc) {
  if (const auto &replacedRange = sourceMgr.getReplacedRange()) {
    if (sourceMgr.rangeContainsTokenLoc(replacedRange.New, loc) &&
        !sourceMgr.rangeContains(replacedRange.New, range)) {
      return replacedRange.Original.Start;
    }
  }
  return loc;
}

NullablePtr<ASTScopeImpl>
ASTScopeImpl::findChildContaining(SourceLoc loc,
                                  SourceManager &sourceMgr) const {
  // Use binary search to find the child that contains this location.
  auto *const *child = llvm::lower_bound(
      getChildren(), loc,
      [&sourceMgr](const ASTScopeImpl *scope, SourceLoc loc) {
        ASTScopeAssert(scope->checkSourceRangeOfThisASTNode(), "Bad range.");
        auto rangeOfScope = scope->getSourceRangeOfScope();
        loc = translateLocForReplacedRange(sourceMgr, rangeOfScope, loc);
        return -1 == ASTScopeImpl::compare(rangeOfScope, loc, sourceMgr,
                                           /*ensureDisjoint=*/false);
      });

  if (child != getChildren().end()) {
    auto rangeOfScope = (*child)->getSourceRangeOfScope();
    loc = translateLocForReplacedRange(sourceMgr, rangeOfScope, loc);
    if (sourceMgr.rangeContainsTokenLoc(rangeOfScope, loc))
      return *child;
  }

  return nullptr;
}

#pragma mark doesContextMatchStartingContext
// Match existing UnqualifiedLookupBehavior

{'fraction_non_alphanumeric': 0.12950643097003103, 'fraction_numerical': 0.0016473420769182031, 'mean_word_length': 3.045105074320861, 'pattern_counts': {'":': 0, '<': 62, '<?xml version=': 0, '>': 50, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 26, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5494224', 'n_tokens_mistral': 4515, 'n_tokens_neox': 4314, 'n_words': 1264}