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