1 //===- ASTImporter.h - Importing ASTs from other Contexts -------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines the ASTImporter class which imports AST nodes from one 10 // context into another context. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_AST_ASTIMPORTER_H 15 #define LLVM_CLANG_AST_ASTIMPORTER_H 16 17 #include "clang/AST/DeclBase.h" 18 #include "clang/AST/DeclarationName.h" 19 #include "clang/AST/NestedNameSpecifier.h" 20 #include "clang/AST/TemplateName.h" 21 #include "clang/AST/Type.h" 22 #include "clang/Basic/Diagnostic.h" 23 #include "clang/Basic/IdentifierTable.h" 24 #include "clang/Basic/LLVM.h" 25 #include "clang/Basic/SourceLocation.h" 26 #include "llvm/ADT/DenseMap.h" 27 #include "llvm/ADT/DenseSet.h" 28 #include "llvm/ADT/Optional.h" 29 #include "llvm/ADT/SmallVector.h" 30 #include "llvm/Support/Error.h" 31 #include <utility> 32 33 namespace clang { 34 35 class ASTContext; 36 class ASTImporterSharedState; 37 class Attr; 38 class CXXBaseSpecifier; 39 class CXXCtorInitializer; 40 class Decl; 41 class DeclContext; 42 class Expr; 43 class FileManager; 44 class NamedDecl; 45 class Stmt; 46 class TagDecl; 47 class TranslationUnitDecl; 48 class TypeSourceInfo; 49 50 class ImportError : public llvm::ErrorInfo<ImportError> { 51 public: 52 /// \brief Kind of error when importing an AST component. 53 enum ErrorKind { 54 NameConflict, /// Naming ambiguity (likely ODR violation). 55 UnsupportedConstruct, /// Not supported node or case. 56 Unknown /// Other error. 57 }; 58 59 ErrorKind Error; 60 61 static char ID; 62 ImportError()63 ImportError() : Error(Unknown) { } ImportError(const ImportError & Other)64 ImportError(const ImportError &Other) : Error(Other.Error) { } ImportError(ErrorKind Error)65 ImportError(ErrorKind Error) : Error(Error) { } 66 67 std::string toString() const; 68 69 void log(raw_ostream &OS) const override; 70 std::error_code convertToErrorCode() const override; 71 }; 72 73 // \brief Returns with a list of declarations started from the canonical decl 74 // then followed by subsequent decls in the translation unit. 75 // This gives a canonical list for each entry in the redecl chain. 76 // `Decl::redecls()` gives a list of decls which always start from the 77 // previous decl and the next item is actually the previous item in the order 78 // of source locations. Thus, `Decl::redecls()` gives different lists for 79 // the different entries in a given redecl chain. 80 llvm::SmallVector<Decl*, 2> getCanonicalForwardRedeclChain(Decl* D); 81 82 /// Imports selected nodes from one AST context into another context, 83 /// merging AST nodes where appropriate. 84 class ASTImporter { 85 friend class ASTNodeImporter; 86 public: 87 using NonEquivalentDeclSet = llvm::DenseSet<std::pair<Decl *, Decl *>>; 88 using ImportedCXXBaseSpecifierMap = 89 llvm::DenseMap<const CXXBaseSpecifier *, CXXBaseSpecifier *>; 90 91 // An ImportPath is the list of the AST nodes which we visit during an 92 // Import call. 93 // If node `A` depends on node `B` then the path contains an `A`->`B` edge. 94 // From the call stack of the import functions we can read the very same 95 // path. 96 // 97 // Now imagine the following AST, where the `->` represents dependency in 98 // therms of the import. 99 // ``` 100 // A->B->C->D 101 // `->E 102 // ``` 103 // We would like to import A. 104 // The import behaves like a DFS, so we will visit the nodes in this order: 105 // ABCDE. 106 // During the visitation we will have the following ImportPaths: 107 // ``` 108 // A 109 // AB 110 // ABC 111 // ABCD 112 // ABC 113 // AB 114 // ABE 115 // AB 116 // A 117 // ``` 118 // If during the visit of E there is an error then we set an error for E, 119 // then as the call stack shrinks for B, then for A: 120 // ``` 121 // A 122 // AB 123 // ABC 124 // ABCD 125 // ABC 126 // AB 127 // ABE // Error! Set an error to E 128 // AB // Set an error to B 129 // A // Set an error to A 130 // ``` 131 // However, during the import we could import C and D without any error and 132 // they are independent from A,B and E. 133 // We must not set up an error for C and D. 134 // So, at the end of the import we have an entry in `ImportDeclErrors` for 135 // A,B,E but not for C,D. 136 // 137 // Now what happens if there is a cycle in the import path? 138 // Let's consider this AST: 139 // ``` 140 // A->B->C->A 141 // `->E 142 // ``` 143 // During the visitation we will have the below ImportPaths and if during 144 // the visit of E there is an error then we will set up an error for E,B,A. 145 // But what's up with C? 146 // ``` 147 // A 148 // AB 149 // ABC 150 // ABCA 151 // ABC 152 // AB 153 // ABE // Error! Set an error to E 154 // AB // Set an error to B 155 // A // Set an error to A 156 // ``` 157 // This time we know that both B and C are dependent on A. 158 // This means we must set up an error for C too. 159 // As the call stack reverses back we get to A and we must set up an error 160 // to all nodes which depend on A (this includes C). 161 // But C is no longer on the import path, it just had been previously. 162 // Such situation can happen only if during the visitation we had a cycle. 163 // If we didn't have any cycle, then the normal way of passing an Error 164 // object through the call stack could handle the situation. 165 // This is why we must track cycles during the import process for each 166 // visited declaration. 167 class ImportPathTy { 168 public: 169 using VecTy = llvm::SmallVector<Decl *, 32>; 170 push(Decl * D)171 void push(Decl *D) { 172 Nodes.push_back(D); 173 ++Aux[D]; 174 } 175 pop()176 void pop() { 177 if (Nodes.empty()) 178 return; 179 --Aux[Nodes.back()]; 180 Nodes.pop_back(); 181 } 182 183 /// Returns true if the last element can be found earlier in the path. hasCycleAtBack()184 bool hasCycleAtBack() const { 185 auto Pos = Aux.find(Nodes.back()); 186 return Pos != Aux.end() && Pos->second > 1; 187 } 188 189 using Cycle = llvm::iterator_range<VecTy::const_reverse_iterator>; getCycleAtBack()190 Cycle getCycleAtBack() const { 191 assert(Nodes.size() >= 2); 192 return Cycle(Nodes.rbegin(), 193 std::find(Nodes.rbegin() + 1, Nodes.rend(), Nodes.back()) + 194 1); 195 } 196 197 /// Returns the copy of the cycle. copyCycleAtBack()198 VecTy copyCycleAtBack() const { 199 auto R = getCycleAtBack(); 200 return VecTy(R.begin(), R.end()); 201 } 202 203 private: 204 // All nodes of the path. 205 VecTy Nodes; 206 // Auxiliary container to be able to answer "Do we have a cycle ending 207 // at last element?" as fast as possible. 208 // We count each Decl's occurrence over the path. 209 llvm::SmallDenseMap<Decl *, int, 32> Aux; 210 }; 211 212 private: 213 std::shared_ptr<ASTImporterSharedState> SharedState = nullptr; 214 215 /// The path which we go through during the import of a given AST node. 216 ImportPathTy ImportPath; 217 /// Sometimes we have to save some part of an import path, so later we can 218 /// set up properties to the saved nodes. 219 /// We may have several of these import paths associated to one Decl. 220 using SavedImportPathsForOneDecl = 221 llvm::SmallVector<ImportPathTy::VecTy, 32>; 222 using SavedImportPathsTy = 223 llvm::SmallDenseMap<Decl *, SavedImportPathsForOneDecl, 32>; 224 SavedImportPathsTy SavedImportPaths; 225 226 /// The contexts we're importing to and from. 227 ASTContext &ToContext, &FromContext; 228 229 /// The file managers we're importing to and from. 230 FileManager &ToFileManager, &FromFileManager; 231 232 /// Whether to perform a minimal import. 233 bool Minimal; 234 235 /// Whether the last diagnostic came from the "from" context. 236 bool LastDiagFromFrom = false; 237 238 /// Mapping from the already-imported types in the "from" context 239 /// to the corresponding types in the "to" context. 240 llvm::DenseMap<const Type *, const Type *> ImportedTypes; 241 242 /// Mapping from the already-imported declarations in the "from" 243 /// context to the corresponding declarations in the "to" context. 244 llvm::DenseMap<Decl *, Decl *> ImportedDecls; 245 246 /// Mapping from the already-imported declarations in the "from" 247 /// context to the error status of the import of that declaration. 248 /// This map contains only the declarations that were not correctly 249 /// imported. The same declaration may or may not be included in 250 /// ImportedDecls. This map is updated continuously during imports and never 251 /// cleared (like ImportedDecls). 252 llvm::DenseMap<Decl *, ImportError> ImportDeclErrors; 253 254 /// Mapping from the already-imported declarations in the "to" 255 /// context to the corresponding declarations in the "from" context. 256 llvm::DenseMap<Decl *, Decl *> ImportedFromDecls; 257 258 /// Mapping from the already-imported statements in the "from" 259 /// context to the corresponding statements in the "to" context. 260 llvm::DenseMap<Stmt *, Stmt *> ImportedStmts; 261 262 /// Mapping from the already-imported FileIDs in the "from" source 263 /// manager to the corresponding FileIDs in the "to" source manager. 264 llvm::DenseMap<FileID, FileID> ImportedFileIDs; 265 266 /// Mapping from the already-imported CXXBasesSpecifier in 267 /// the "from" source manager to the corresponding CXXBasesSpecifier 268 /// in the "to" source manager. 269 ImportedCXXBaseSpecifierMap ImportedCXXBaseSpecifiers; 270 271 /// Declaration (from, to) pairs that are known not to be equivalent 272 /// (which we have already complained about). 273 NonEquivalentDeclSet NonEquivalentDecls; 274 275 using FoundDeclsTy = SmallVector<NamedDecl *, 2>; 276 FoundDeclsTy findDeclsInToCtx(DeclContext *DC, DeclarationName Name); 277 278 void AddToLookupTable(Decl *ToD); 279 280 protected: 281 /// Can be overwritten by subclasses to implement their own import logic. 282 /// The overwritten method should call this method if it didn't import the 283 /// decl on its own. 284 virtual Expected<Decl *> ImportImpl(Decl *From); 285 286 /// Used only in unittests to verify the behaviour of the error handling. returnWithErrorInTest()287 virtual bool returnWithErrorInTest() { return false; }; 288 289 public: 290 291 /// \param ToContext The context we'll be importing into. 292 /// 293 /// \param ToFileManager The file manager we'll be importing into. 294 /// 295 /// \param FromContext The context we'll be importing from. 296 /// 297 /// \param FromFileManager The file manager we'll be importing into. 298 /// 299 /// \param MinimalImport If true, the importer will attempt to import 300 /// as little as it can, e.g., by importing declarations as forward 301 /// declarations that can be completed at a later point. 302 /// 303 /// \param SharedState The importer specific lookup table which may be 304 /// shared amongst several ASTImporter objects. 305 /// If not set then the original C/C++ lookup is used. 306 ASTImporter(ASTContext &ToContext, FileManager &ToFileManager, 307 ASTContext &FromContext, FileManager &FromFileManager, 308 bool MinimalImport, 309 std::shared_ptr<ASTImporterSharedState> SharedState = nullptr); 310 311 virtual ~ASTImporter(); 312 313 /// Whether the importer will perform a minimal import, creating 314 /// to-be-completed forward declarations when possible. isMinimalImport()315 bool isMinimalImport() const { return Minimal; } 316 317 /// \brief Import the given object, returns the result. 318 /// 319 /// \param To Import the object into this variable. 320 /// \param From Object to import. 321 /// \return Error information (success or error). 322 template <typename ImportT> importInto(ImportT & To,const ImportT & From)323 LLVM_NODISCARD llvm::Error importInto(ImportT &To, const ImportT &From) { 324 auto ToOrErr = Import(From); 325 if (ToOrErr) 326 To = *ToOrErr; 327 return ToOrErr.takeError(); 328 } 329 330 /// Import the given type from the "from" context into the "to" 331 /// context. A null type is imported as a null type (no error). 332 /// 333 /// \returns The equivalent type in the "to" context, or the import error. 334 llvm::Expected<QualType> Import(QualType FromT); 335 336 /// Import the given type source information from the 337 /// "from" context into the "to" context. 338 /// 339 /// \returns The equivalent type source information in the "to" 340 /// context, or the import error. 341 llvm::Expected<TypeSourceInfo *> Import(TypeSourceInfo *FromTSI); 342 343 /// Import the given attribute from the "from" context into the 344 /// "to" context. 345 /// 346 /// \returns The equivalent attribute in the "to" context, or the import 347 /// error. 348 llvm::Expected<Attr *> Import(const Attr *FromAttr); 349 350 /// Import the given declaration from the "from" context into the 351 /// "to" context. 352 /// 353 /// \returns The equivalent declaration in the "to" context, or the import 354 /// error. 355 llvm::Expected<Decl *> Import(Decl *FromD); Import(const Decl * FromD)356 llvm::Expected<const Decl *> Import(const Decl *FromD) { 357 return Import(const_cast<Decl *>(FromD)); 358 } 359 360 /// Return the copy of the given declaration in the "to" context if 361 /// it has already been imported from the "from" context. Otherwise return 362 /// nullptr. 363 Decl *GetAlreadyImportedOrNull(const Decl *FromD) const; 364 365 /// Return the translation unit from where the declaration was 366 /// imported. If it does not exist nullptr is returned. 367 TranslationUnitDecl *GetFromTU(Decl *ToD); 368 369 /// Import the given declaration context from the "from" 370 /// AST context into the "to" AST context. 371 /// 372 /// \returns the equivalent declaration context in the "to" 373 /// context, or error value. 374 llvm::Expected<DeclContext *> ImportContext(DeclContext *FromDC); 375 376 /// Import the given expression from the "from" context into the 377 /// "to" context. 378 /// 379 /// \returns The equivalent expression in the "to" context, or the import 380 /// error. 381 llvm::Expected<Expr *> Import(Expr *FromE); 382 383 /// Import the given statement from the "from" context into the 384 /// "to" context. 385 /// 386 /// \returns The equivalent statement in the "to" context, or the import 387 /// error. 388 llvm::Expected<Stmt *> Import(Stmt *FromS); 389 390 /// Import the given nested-name-specifier from the "from" 391 /// context into the "to" context. 392 /// 393 /// \returns The equivalent nested-name-specifier in the "to" 394 /// context, or the import error. 395 llvm::Expected<NestedNameSpecifier *> Import(NestedNameSpecifier *FromNNS); 396 397 /// Import the given nested-name-specifier-loc from the "from" 398 /// context into the "to" context. 399 /// 400 /// \returns The equivalent nested-name-specifier-loc in the "to" 401 /// context, or the import error. 402 llvm::Expected<NestedNameSpecifierLoc> 403 Import(NestedNameSpecifierLoc FromNNS); 404 405 /// Import the given template name from the "from" context into the 406 /// "to" context, or the import error. 407 llvm::Expected<TemplateName> Import(TemplateName From); 408 409 /// Import the given source location from the "from" context into 410 /// the "to" context. 411 /// 412 /// \returns The equivalent source location in the "to" context, or the 413 /// import error. 414 llvm::Expected<SourceLocation> Import(SourceLocation FromLoc); 415 416 /// Import the given source range from the "from" context into 417 /// the "to" context. 418 /// 419 /// \returns The equivalent source range in the "to" context, or the import 420 /// error. 421 llvm::Expected<SourceRange> Import(SourceRange FromRange); 422 423 /// Import the given declaration name from the "from" 424 /// context into the "to" context. 425 /// 426 /// \returns The equivalent declaration name in the "to" context, or the 427 /// import error. 428 llvm::Expected<DeclarationName> Import(DeclarationName FromName); 429 430 /// Import the given identifier from the "from" context 431 /// into the "to" context. 432 /// 433 /// \returns The equivalent identifier in the "to" context. Note: It 434 /// returns nullptr only if the FromId was nullptr. 435 IdentifierInfo *Import(const IdentifierInfo *FromId); 436 437 /// Import the given Objective-C selector from the "from" 438 /// context into the "to" context. 439 /// 440 /// \returns The equivalent selector in the "to" context, or the import 441 /// error. 442 llvm::Expected<Selector> Import(Selector FromSel); 443 444 /// Import the given file ID from the "from" context into the 445 /// "to" context. 446 /// 447 /// \returns The equivalent file ID in the source manager of the "to" 448 /// context, or the import error. 449 llvm::Expected<FileID> Import(FileID, bool IsBuiltin = false); 450 451 /// Import the given C++ constructor initializer from the "from" 452 /// context into the "to" context. 453 /// 454 /// \returns The equivalent initializer in the "to" context, or the import 455 /// error. 456 llvm::Expected<CXXCtorInitializer *> Import(CXXCtorInitializer *FromInit); 457 458 /// Import the given CXXBaseSpecifier from the "from" context into 459 /// the "to" context. 460 /// 461 /// \returns The equivalent CXXBaseSpecifier in the source manager of the 462 /// "to" context, or the import error. 463 llvm::Expected<CXXBaseSpecifier *> Import(const CXXBaseSpecifier *FromSpec); 464 465 /// Import the definition of the given declaration, including all of 466 /// the declarations it contains. 467 LLVM_NODISCARD llvm::Error ImportDefinition(Decl *From); 468 469 /// Cope with a name conflict when importing a declaration into the 470 /// given context. 471 /// 472 /// This routine is invoked whenever there is a name conflict while 473 /// importing a declaration. The returned name will become the name of the 474 /// imported declaration. By default, the returned name is the same as the 475 /// original name, leaving the conflict unresolve such that name lookup 476 /// for this name is likely to find an ambiguity later. 477 /// 478 /// Subclasses may override this routine to resolve the conflict, e.g., by 479 /// renaming the declaration being imported. 480 /// 481 /// \param Name the name of the declaration being imported, which conflicts 482 /// with other declarations. 483 /// 484 /// \param DC the declaration context (in the "to" AST context) in which 485 /// the name is being imported. 486 /// 487 /// \param IDNS the identifier namespace in which the name will be found. 488 /// 489 /// \param Decls the set of declarations with the same name as the 490 /// declaration being imported. 491 /// 492 /// \param NumDecls the number of conflicting declarations in \p Decls. 493 /// 494 /// \returns the name that the newly-imported declaration should have. 495 virtual DeclarationName HandleNameConflict(DeclarationName Name, 496 DeclContext *DC, 497 unsigned IDNS, 498 NamedDecl **Decls, 499 unsigned NumDecls); 500 501 /// Retrieve the context that AST nodes are being imported into. getToContext()502 ASTContext &getToContext() const { return ToContext; } 503 504 /// Retrieve the context that AST nodes are being imported from. getFromContext()505 ASTContext &getFromContext() const { return FromContext; } 506 507 /// Retrieve the file manager that AST nodes are being imported into. getToFileManager()508 FileManager &getToFileManager() const { return ToFileManager; } 509 510 /// Retrieve the file manager that AST nodes are being imported from. getFromFileManager()511 FileManager &getFromFileManager() const { return FromFileManager; } 512 513 /// Report a diagnostic in the "to" context. 514 DiagnosticBuilder ToDiag(SourceLocation Loc, unsigned DiagID); 515 516 /// Report a diagnostic in the "from" context. 517 DiagnosticBuilder FromDiag(SourceLocation Loc, unsigned DiagID); 518 519 /// Return the set of declarations that we know are not equivalent. getNonEquivalentDecls()520 NonEquivalentDeclSet &getNonEquivalentDecls() { return NonEquivalentDecls; } 521 522 /// Called for ObjCInterfaceDecl, ObjCProtocolDecl, and TagDecl. 523 /// Mark the Decl as complete, filling it in as much as possible. 524 /// 525 /// \param D A declaration in the "to" context. 526 virtual void CompleteDecl(Decl* D); 527 528 /// Subclasses can override this function to observe all of the \c From -> 529 /// \c To declaration mappings as they are imported. Imported(Decl * From,Decl * To)530 virtual void Imported(Decl *From, Decl *To) {} 531 532 void RegisterImportedDecl(Decl *FromD, Decl *ToD); 533 534 /// Store and assign the imported declaration to its counterpart. 535 /// It may happen that several decls from the 'from' context are mapped to 536 /// the same decl in the 'to' context. 537 Decl *MapImported(Decl *From, Decl *To); 538 539 /// Called by StructuralEquivalenceContext. If a RecordDecl is 540 /// being compared to another RecordDecl as part of import, completing the 541 /// other RecordDecl may trigger importation of the first RecordDecl. This 542 /// happens especially for anonymous structs. If the original of the second 543 /// RecordDecl can be found, we can complete it without the need for 544 /// importation, eliminating this loop. GetOriginalDecl(Decl * To)545 virtual Decl *GetOriginalDecl(Decl *To) { return nullptr; } 546 547 /// Return if import of the given declaration has failed and if yes 548 /// the kind of the problem. This gives the first error encountered with 549 /// the node. 550 llvm::Optional<ImportError> getImportDeclErrorIfAny(Decl *FromD) const; 551 552 /// Mark (newly) imported declaration with error. 553 void setImportDeclError(Decl *From, ImportError Error); 554 555 /// Determine whether the given types are structurally 556 /// equivalent. 557 bool IsStructurallyEquivalent(QualType From, QualType To, 558 bool Complain = true); 559 560 /// Determine the index of a field in its parent record. 561 /// F should be a field (or indirect field) declaration. 562 /// \returns The index of the field in its parent context (starting from 0). 563 /// On error `None` is returned (parent context is non-record). 564 static llvm::Optional<unsigned> getFieldIndex(Decl *F); 565 }; 566 567 } // namespace clang 568 569 #endif // LLVM_CLANG_AST_ASTIMPORTER_H 570