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