//===--- iwyu.cc - main logic and driver for include-what-you-use ---------===//

//

// The LLVM Compiler Infrastructure

//

// This file is distributed under the University of Illinois Open Source

// License. See LICENSE.TXT for details.

//

//===----------------------------------------------------------------------===//

// A Clang-based tool that catches Include-What-You-Use violations:

//

// The analysis enforces the following rule:

//

// - For every symbol (variable, function, constant, type, and macro)

// X in C++ file CU.cc, X must be declared in CU.cc or in a header

// file directly included by itself, CU.h, or CU-inl.h. Likewise

// for CU.h and CU-inl.h.

//

// The rule has a few slight wrinkles:

// 1) CU_test.cc can also 'inherit' #includes from CU.h and CU-inl.h.

// Likewise for CU_unittest.cc, CU_regtest.cc, etc.

// 2) CU.cc can inherit #includes from ../public/CU.h in addition to

// ./CU.h (likewise for -inl.h).

// 3) For system #includes, and a few google #includes, we hard-code

// in knowledge of which #include files are public and which are not.

// (For instance, <vector> is public, <bits/stl_vector.h> is not.)

// We force CU.cc, CU.h, and CU-inl.h to #include the public version.

//

// iwyu.cc checks if a symbol can be forward-declared instead of fully

// declared. If so, it will enforce the rule that the symbol is

// forward-declared in the file that references it. We only forward-

// declare classes and structs (possibly templatized). We will not

// try to forward-declare variables or functions.

//

// Checking iwyu violations for variables, functions, constants, and

// macros is easy. Types can be trickier. Obviously, if you declare

// a variable of type Foo in cu.cc, it's straightforward to check

// whether it's an iwyu violation. But what if you call a function

// that returns a type, e.g. 'if (FnReturningSomeSTLType()->empty())'?

// Is it an iwyu violation if you don't #include the header for that

// STL type? We say no: whatever file provided the function

// FnReturningSomeSTLType is also responsible for providing whatever

// the STL type is, so we don't have to. Otherwise, we get into an

// un-fun propagation problem if we change the signature of

// FnReturningSomeSTLType to return a different type of STL type. So

// in general, types are only iwyu-checked if they appear explicitly

// in the source code.

//

// It can likewise be difficult to say whether a template arg is

// forward-declable: set<Foo*> x does not require the full type info

// for Foo, but remove_pointer<Foo*>::type does. And f<Foo>() doesn't

// require full type info for Foo if f doesn't actually use Foo in it.

// For now we do the simple heuristic that if the template arg is a

// pointer, it's ok if it's forward-declared, and if not, it's not.

//

// We use the following terminology:

//

// - A *symbol* is the name of a function, variable, constant, type,

// macro, etc.

//

// - A *quoted include path* is an include path with the surrounding <>

// or "", e.g. <stdio.h> or "ads/util.h".

//

// - Any #include falls into exactly one of three (non-overlapping)

// categories:

//

// * it's said to be *necessary* if it's a compiler or IWYU error to

// omit the #include;

//

// * it's said to be *optional* if the #include is unnecessary but

// having it is not an IWYU error either (e.g. if bar.h is a

// necessary #include of foo.h, and foo.cc uses symbols from

// bar.h, it's optional for foo.cc to #include bar.h.);

//

// * it's said to be *undesired* if it's an IWYU error to have the

// #include.

//

// Therefore, when we say a #include is *desired*, we mean that it's

// either necessary or optional.

//

// - We also say that a #include is *recommended* if the IWYU tool

// recommends to have it in the C++ source file. Obviously, any

// necessary #include must be recommended, and no undesired

// #include can be recommended. An optional #include can be

// either recommended or not -- the IWYU tool can decide which

// case it is. For example, if foo.cc desires bar.h, but can

// already get it via foo.h, IWYU won't recommend foo.cc to

// #include bar.h, unless it already does so.

#include <cstdio>

#include <cstdlib> // for atoi, exit

#include <functional>

#include <map> // for map, swap, etc

#include <memory> // for unique_ptr

#include <set> // for set, set<>::iterator, swap

#include <string> // for string, operator+, etc

#include <utility> // for pair

#include <vector> // for vector, swap

#include "clang/AST/ASTConsumer.h"

#include "clang/AST/ASTContext.h"

#include "clang/AST/Attr.h"

#include "clang/AST/Decl.h"

#include "clang/AST/DeclBase.h"

#include "clang/AST/DeclCXX.h"

#include "clang/AST/DeclTemplate.h"

#include "clang/AST/Expr.h"

#include "clang/AST/ExprCXX.h"

#include "clang/AST/ExprConcepts.h"

#include "clang/AST/NestedNameSpecifier.h"

#include "clang/AST/OperationKinds.h"

#include "clang/AST/RecursiveASTVisitor.h"

#include "clang/AST/StmtCXX.h"

#include "clang/AST/TemplateBase.h"

#include "clang/AST/TemplateName.h"

#include "clang/AST/Type.h"

#include "clang/AST/TypeLoc.h"

#include "clang/Basic/Diagnostic.h"

#include "clang/Basic/FileEntry.h"

#include "clang/Basic/LangOptions.h"

#include "clang/Basic/SourceLocation.h"

#include "clang/Basic/SourceManager.h"

#include "clang/Basic/Specifiers.h"

#include "clang/Basic/TypeTraits.h"

#include "clang/Frontend/CompilerInstance.h"

#include "clang/Frontend/FrontendAction.h"

#include "clang/Lex/Preprocessor.h"

#include "clang/Sema/Sema.h"

#include "iwyu_ast_util.h"

#include "iwyu_cache.h"

#include "iwyu_driver.h"

#include "iwyu_globals.h"

#include "iwyu_location_util.h"

#include "iwyu_output.h"

#include "iwyu_port.h" // for CHECK_

#include "iwyu_preprocessor.h"

#include "iwyu_stl_util.h"

#include "iwyu_string_util.h"

#include "iwyu_use_flags.h"

#include "iwyu_verrs.h"

#include "llvm/ADT/ArrayRef.h"

#include "llvm/ADT/StringRef.h"

#include "llvm/ADT/iterator_range.h"

#include "llvm/Support/Casting.h"

#include "llvm/Support/ManagedStatic.h"

#include "llvm/Support/TargetSelect.h"

// TODO: Clean out pragmas as IWYU improves.

// IWYU pragma: no_include "clang/AST/Redeclarable.h"

// IWYU pragma: no_include "clang/AST/StmtIterator.h"

// IWYU pragma: no_include "clang/AST/UnresolvedSet.h"

// IWYU pragma: no_include "clang/Basic/CustomizableOptional.h"

// IWYU pragma: no_include "clang/Lex/PPCallbacks.h"

// IWYU pragma: no_include "llvm/ADT/iterator.h"

// IWYU pragma: begin_keep

namespace clang {

class PPCallbacks;

} // namespace clang

// IWYU pragma: end_keep

namespace clang {

class FriendDecl;

class Stmt;

namespace driver {

class ToolChain;

}

} // namespace clang

namespace include_what_you_use {

// I occasionally clean up this list by running:

// $ grep "using clang":: iwyu.cc | cut -b14- | tr -d ";" | while read t; do grep -q "[^:]$t" iwyu.cc || echo $t; done

using clang::ASTConsumer;

using clang::ASTContext;

using clang::ASTFrontendAction;

using clang::ArraySubscriptExpr;

using clang::ArrayType;

using clang::Attr;

using clang::BinaryOperator;

using clang::CXXBaseSpecifier;

using clang::CXXBindTemporaryExpr;

using clang::CXXCatchStmt;

using clang::CXXConstructExpr;

using clang::CXXConstructorDecl;

using clang::CXXDefaultArgExpr;

using clang::CXXDeleteExpr;

using clang::CXXDestructorDecl;

using clang::CXXForRangeStmt;

using clang::CXXMemberCallExpr;

using clang::CXXMethodDecl;

using clang::CXXNewExpr;

using clang::CXXOperatorCallExpr;

using clang::CXXRecordDecl;

using clang::CXXTemporaryObjectExpr;

using clang::CXXTypeidExpr;

using clang::CallExpr;

using clang::CastExpr;

using clang::ClassTemplateSpecializationDecl;

using clang::CleanupAttr;

using clang::CompilerInstance;

using clang::ConceptSpecializationExpr;

using clang::Decl;

using clang::DeclContext;

using clang::DeclRefExpr;

using clang::DecltypeType;

using clang::DeducedTemplateSpecializationType;

using clang::ElaboratedType;

using clang::ElaboratedTypeKeyword;

using clang::ElaboratedTypeLoc;

using clang::EnumConstantDecl;

using clang::EnumDecl;

using clang::EnumType;

using clang::Expr;

using clang::FriendDecl;

using clang::FriendTemplateDecl;

using clang::FunctionDecl;

using clang::FunctionProtoType;

using clang::FunctionTemplateDecl;

using clang::FunctionType;

using clang::LateParsedTemplate;

using clang::LinkageSpecDecl;

using clang::MemberExpr;

using clang::MemberPointerType;

using clang::NamedDecl;

using clang::NamespaceAliasDecl;

using clang::NestedNameSpecifier;

using clang::NestedNameSpecifierLoc;

using clang::OptionalFileEntryRef;

using clang::PPCallbacks;

using clang::ParenType;

using clang::ParmVarDecl;

using clang::PointerType;

using clang::Preprocessor;

using clang::QualType;

using clang::QualifiedTypeLoc;

using clang::RecordDecl;

using clang::RecordType;

using clang::RecursiveASTVisitor;

using clang::ReferenceType;

using clang::Sema;

using clang::SourceLocation;

using clang::SourceManager;

using clang::Stmt;

using clang::SubstTemplateTypeParmType;

using clang::TagDecl;

using clang::TagType;

using clang::TemplateArgument;

using clang::TemplateArgumentList;

using clang::TemplateArgumentLoc;

using clang::TemplateDecl;

using clang::TemplateName;

using clang::TemplateSpecializationType;

using clang::TemplateSpecializationTypeLoc;

using clang::TemplateTypeParmDecl;

using clang::TranslationUnitDecl;

using clang::Type;

using clang::TypeAliasDecl;

using clang::TypeAliasTemplateDecl;

using clang::TypeLoc;

using clang::TypeSourceInfo;

using clang::TypeTrait;

using clang::TypeTraitExpr;

using clang::TypedefDecl;

using clang::TypedefNameDecl;

using clang::TypedefType;

using clang::UnaryExprOrTypeTraitExpr;

using clang::UnresolvedLookupExpr;

using clang::UsingDecl;

using clang::UsingDirectiveDecl;

using clang::UsingShadowDecl;

using clang::UsingType;

using clang::ValueDecl;

using clang::VarDecl;

using clang::driver::ToolChain;

using llvm::cast;

using llvm::dyn_cast;

using llvm::dyn_cast_or_null;

using llvm::errs;

using llvm::isa;

using std::map;

using std::set;

using std::string;

using std::swap;

using std::vector;

namespace {

bool CanIgnoreLocation(SourceLocation loc) {

}

} // anonymous namespace

enum class DerefKind { None, RemoveRefs, RemoveRefsAndPtr };

// ----------------------------------------------------------------------

// --- BaseAstVisitor

// ----------------------------------------------------------------------

//

// We have a hierarchy of AST visitor classes, to keep the logic

// as clear as possible. The top level, BaseAstVisitor, has some

// basic, not particularly iwyu-related, functionality:

//

// 1) Maintain current_ast_node_, the current chain in the AST tree.

// 2) Provide functions related to the current location.

// 3) Print each node we're visiting, depending on --verbose settings.

// 4) Add appropriate implicit text. iwyu acts as if all constructor

// initializers were explicitly written, all default constructors

// were explicitly written, etc, even if they're not. We traverse

// the implicit stuff as if it were explicit.

// 5) Add two callbacks that subclasses can override (just like any

// other AST callback): TraverseImplicitDestructorCall and

// HandleFunctionCall. TraverseImplicitDestructorCall is a

// callback for a "pseudo-AST" node that covers destruction not

// specified in source, such as a destructor destroying one of the

// fields in its class. HandleFunctionCall is a convenience

// callback that bundles callbacks from many different kinds of

// function-calling callbacks (CallExpr, CXXConstructExpr, etc)

// into one place.

//

// To maintain current_ast_node_ properly, this class also implements

// VisitNestedNameSpecifier, VisitTemplateName, VisitTemplateArg, and

// VisitTemplateArgLoc, which are parallel to the Visit*Decl()/etc

// visitors. Subclasses should override these Visit routines, and not

// the Traverse routine directly.

template <class Derived>

class BaseAstVisitor : public RecursiveASTVisitor<Derived> {

};

// ----------------------------------------------------------------------

// --- AstTreeFlattenerVisitor

// ----------------------------------------------------------------------

//

// This simple visitor just creates a set of all AST nodes (stored as

// void*'s) seen while traversing via BaseAstVisitor.

class AstFlattenerVisitor : public BaseAstVisitor<AstFlattenerVisitor> {