1 /* 2 SPDX-FileCopyrightText: 2008 Andreas Pakulat <apaku@gmx.de> 3 SPDX-FileCopyrightText: 2006 Roberto Raggi <roberto@kdevelop.org> 4 SPDX-FileCopyrightText: 2006-2008 Hamish Rodda <rodda@kde.org> 5 6 SPDX-License-Identifier: LGPL-2.0-or-later 7 */ 8 9 #ifndef KDEVPLATFORM_ABSTRACTABSTRACTCONTEXTBUILDER_H 10 #define KDEVPLATFORM_ABSTRACTABSTRACTCONTEXTBUILDER_H 11 12 #include <climits> 13 14 #include "../topducontext.h" 15 #include "../duchainpointer.h" 16 #include "../duchainlock.h" 17 #include "../duchain.h" 18 #include "../ducontext.h" 19 #include "../identifier.h" 20 #include "../parsingenvironment.h" 21 22 #include <serialization/indexedstring.h> 23 #include <util/stack.h> 24 25 namespace KDevelop { 26 /** 27 * \short Abstract definition-use chain context builder class 28 * 29 * The AbstractContextBuilder is a convenience class template for creating customized 30 * definition-use chain context builders from an AST. It simplifies: 31 * - creating or modifying an existing DUContext tree 32 * - following a DUContext tree for second and subsequent passes, if required 33 * - opening and closing DUContext instances 34 * - tracking which DUContext instances are still present when recompiling, and removing DUContexts which no longer exist in the source code. 35 * 36 * \author Hamish Rodda \<rodda@kde.org\> 37 */ 38 template <typename T, typename NameT> 39 class AbstractContextBuilder 40 { 41 public: 42 /// Constructor. AbstractContextBuilder()43 AbstractContextBuilder() : m_compilingContexts(false) 44 , m_recompiling(false) 45 , m_lastContext(nullptr) 46 { 47 } 48 ~AbstractContextBuilder()49 virtual ~AbstractContextBuilder() 50 { 51 } 52 53 /** 54 * Entry point for building a definition-use chain with this builder. 55 * 56 * This function determines whether we are updating a chain, or creating a new one. If we are 57 * creating a new chain, a new TopDUContext is created and registered with DUChain. 58 * 59 * \param url Url of the document being parsed. 60 * \param node AST node to start building from. 61 * \param updateContext TopDUContext to update if a duchain was previously created for this url, otherwise pass a null pointer. 62 * 63 * \returns the newly created or updated TopDUContext pointer. 64 */ 65 virtual ReferencedTopDUContext build(const IndexedString& url, T* node, 66 const ReferencedTopDUContext& updateContext 67 = ReferencedTopDUContext()) 68 { 69 m_compilingContexts = true; 70 m_url = url; 71 72 ReferencedTopDUContext top; 73 { 74 DUChainWriteLocker lock(DUChain::lock()); 75 top = updateContext.data(); 76 77 if (top) { 78 m_recompiling = true; 79 Q_ASSERT(top->type() == DUContext::Global); 80 Q_ASSERT(DUChain::self()->chainForIndex(top->ownIndex()) == top); 81 } else 82 { 83 top = newTopContext(RangeInRevision(CursorInRevision(0, 0), CursorInRevision(INT_MAX, INT_MAX))); 84 DUChain::self()->addDocumentChain(top); 85 top->setType(DUContext::Global); 86 } 87 88 setEncountered(top); 89 setContextOnNode(node, top); 90 } 91 92 supportBuild(node, top); 93 94 m_compilingContexts = false; 95 return top; 96 } 97 98 protected: 99 /** 100 * Support another builder by tracking the current context. 101 * @param node the given node. 102 * @param context the context to use. Must be set when the given node has no context. When it has one attached, this parameter is not needed. 103 */ 104 virtual void supportBuild(T* node, DUContext* context = nullptr) 105 { 106 if (!context) 107 context = contextFromNode(node); 108 109 Q_ASSERT(context); 110 111 openContext(context); 112 113 startVisiting(node); 114 115 closeContext(); 116 117 Q_ASSERT(m_contextStack.isEmpty()); 118 } 119 120 /** 121 * Entry point to your visitor. Reimplement and call the appropriate visit function. 122 * 123 * \param node AST node to visit. 124 */ 125 virtual void startVisiting(T* node) = 0; 126 127 /** 128 * Associate a \a context with a given AST \a node. Once called on a \a node, the 129 * contextFromNode() function should return this \a context when called. 130 * 131 * \param node AST node to associate 132 * \param context DUContext to associate 133 */ 134 virtual void setContextOnNode(T* node, DUContext* context) = 0; 135 136 /** 137 * Retrieve an associated DUContext from the given \a node. Used on second and 138 * subsequent passes of the context builder (for supporting other builds) 139 * 140 * \param node AST node which was previously associated 141 * \returns the DUContext which was previously associated 142 */ 143 virtual DUContext* contextFromNode(T* node) = 0; 144 145 /** 146 * Retrieves a text range from the given nodes. 147 * 148 * As editor integrators have to be extended to determine ranges from AST nodes, 149 * this function must be reimplemented to allow generic retrieving of rangs from nodes. 150 * 151 * \param fromNode the AST node to start from (on the start boundary) 152 * \param toNode the AST node to end at (on the end boundary) 153 * 154 * \returns the text range encompassing the given AST node(s) 155 */ 156 virtual RangeInRevision editorFindRange(T* fromNode, T* toNode) = 0; 157 158 /** 159 * Retrieve a text range for the given nodes. This is a special function required 160 * by c++ support as a different range may need to be retrieved depending on 161 * whether macros are involved. It is not usually required to implement this 162 * function separately to editorFindRange() for other languages. 163 * 164 * \param fromNode the AST node to start from (on the start boundary) 165 * \param toNode the AST node to end at (on the end boundary) 166 * 167 * \returns the text range encompassing the given AST node(s) 168 */ editorFindRangeForContext(T * fromNode,T * toNode)169 virtual RangeInRevision editorFindRangeForContext(T* fromNode, T* toNode) 170 { 171 return editorFindRange(fromNode, toNode); 172 } 173 174 /** 175 * Determine the QualifiedIdentifier which corresponds to the given ast \a node. 176 * 177 * \param node ast node which represents an identifier 178 * \return the qualified identifier determined from \a node 179 */ 180 virtual QualifiedIdentifier identifierForNode(NameT* node) = 0; 181 182 /** 183 * Create a new DUContext from the given \a range. 184 * 185 * This exists so that you can create custom DUContext subclasses for your 186 * language if you need to. 187 * 188 * \param range range for the new context to encompass 189 * \returns the newly created context 190 */ newContext(const RangeInRevision & range)191 virtual DUContext* newContext(const RangeInRevision& range) 192 { 193 return new DUContext(range, currentContext()); 194 } 195 196 /** 197 * Create a new TopDUContext from the given \a range. 198 * 199 * This exists so that you can create custom TopDUContext subclasses for your 200 * language if you need to. 201 * 202 * \returns the newly created context 203 */ 204 virtual TopDUContext* newTopContext(const RangeInRevision& range, ParsingEnvironmentFile* file = nullptr) 205 { 206 return new TopDUContext(m_url, range, file); 207 } 208 209 /// Determine the currently open context. \returns the current context. currentContext()210 inline DUContext* currentContext() const { return m_contextStack.top(); } 211 /// Determine the last closed context. \returns the last closed context. lastContext()212 inline DUContext* lastContext() const { return m_lastContext; } 213 /// Clears the last closed context. clearLastContext()214 inline void clearLastContext() { m_lastContext = nullptr; } 215 setLastContext(DUContext * context)216 inline void setLastContext(DUContext* context) { m_lastContext = context; } 217 topContext()218 TopDUContext* topContext() const 219 { 220 return currentContext()->topContext(); 221 } 222 223 /** 224 * Determine if we are recompiling an existing definition-use chain, or if 225 * a new chain is being created from scratch. 226 * 227 * \returns true if an existing duchain is being updated, otherwise false. 228 */ recompiling()229 inline bool recompiling() const { return m_recompiling; } 230 231 /** 232 * Tell the context builder whether we are recompiling an existing definition-use chain, or if 233 * a new chain is being created from scratch. 234 * 235 * \param recomp set to true if an existing duchain is being updated, otherwise false. 236 */ setRecompiling(bool recomp)237 inline void setRecompiling(bool recomp) { m_recompiling = recomp; } 238 239 /** 240 * Determine whether this pass will create DUContext instances. 241 * 242 * On the first pass of definition-use chain compiling, DUContext instances 243 * are created to represent contexts in the source code. These contexts are 244 * associated with their AST nodes at the time (see setContextOnNode()). 245 * 246 * On second and subsequent passes, the contexts already exist and thus can be 247 * retrieved through contextFromNode(). 248 * 249 * \returns true if compiling contexts (ie. 1st pass), otherwise false. 250 */ compilingContexts()251 inline bool compilingContexts() const { return m_compilingContexts; } 252 253 /** 254 * Sets whether we need to create ducontexts, ie. if this is the first pass. 255 * 256 * \sa compilingContexts() 257 */ setCompilingContexts(bool compilingContexts)258 inline void setCompilingContexts(bool compilingContexts) { m_compilingContexts = compilingContexts; } 259 260 /** 261 * Create child contexts for only a portion of the document. 262 * 263 * \param node The AST node which corresponds to the context to parse 264 * \param parent The DUContext which encompasses the \a node. 265 * \returns The DUContext which was reparsed, ie. \a parent. 266 */ buildSubContexts(T * node,DUContext * parent)267 DUContext* buildSubContexts(T* node, DUContext* parent) 268 { 269 // m_compilingContexts = true; 270 // m_recompiling = false; 271 setContextOnNode(node, parent); 272 { 273 openContext(contextFromNode(node)); 274 startVisiting(node); 275 closeContext(); 276 } 277 278 m_compilingContexts = false; 279 280 if (contextFromNode(node) == parent) { 281 qDebug() << 282 "Error in AbstractContextBuilder::buildSubContexts(...): du-context was not replaced with new one"; 283 DUChainWriteLocker lock(DUChain::lock()); 284 deleteContextOnNode(node); 285 } 286 287 return contextFromNode(node); 288 } 289 290 /** 291 * Delete the DUContext which is associated with the given \a node, 292 * and remove the association. 293 * 294 * \param node Node which is associated with the context to delete. 295 */ deleteContextOnNode(T * node)296 void deleteContextOnNode(T* node) 297 { 298 delete contextFromNode(node); 299 setContextOnNode(node, nullptr); 300 } 301 302 /** 303 * Open a context, and create / update it if necessary. 304 * 305 * \param rangeNode The range which encompasses the context. 306 * \param type The type of context to open. 307 * \param identifier The range which encompasses the name of this context, if one exists. 308 * \returns the opened context. 309 */ 310 DUContext* openContext(T* rangeNode, DUContext::ContextType type, NameT* identifier = nullptr) 311 { 312 if (m_compilingContexts) { 313 DUContext* ret = openContextInternal(editorFindRangeForContext(rangeNode, 314 rangeNode), type, 315 identifier ? identifierForNode(identifier) : QualifiedIdentifier()); 316 setContextOnNode(rangeNode, ret); 317 return ret; 318 } else 319 { 320 openContext(contextFromNode(rangeNode)); 321 return currentContext(); 322 } 323 } 324 325 /** 326 * Open a context, and create / update it if necessary. 327 * 328 * \param node The range to associate with the context. 329 * \param range A custom range which the context should encompass. 330 * \param type The type of context to open. 331 * \param identifier The range which encompasses the name of this context, if one exists. 332 * \returns the opened context. 333 */ 334 DUContext* openContext(T* node, const RangeInRevision& range, DUContext::ContextType type, 335 NameT* identifier = nullptr) 336 { 337 if (m_compilingContexts) { 338 DUContext* ret = openContextInternal(range, type, identifier ? identifierForNode( 339 identifier) : QualifiedIdentifier()); 340 setContextOnNode(node, ret); 341 return ret; 342 } else { 343 openContext(contextFromNode(node)); 344 return currentContext(); 345 } 346 } 347 348 /** 349 * Open a context, and create / update it if necessary. 350 * 351 * \param node The range to associate with the context. 352 * \param range A custom range which the context should encompass. 353 * \param type The type of context to open. 354 * \param id The identifier for this context 355 * \returns the opened context. 356 */ openContext(T * node,const RangeInRevision & range,DUContext::ContextType type,const QualifiedIdentifier & id)357 DUContext* openContext(T* node, const RangeInRevision& range, DUContext::ContextType type, 358 const QualifiedIdentifier& id) 359 { 360 if (m_compilingContexts) { 361 DUContext* ret = openContextInternal(range, type, id); 362 setContextOnNode(node, ret); 363 return ret; 364 } else { 365 openContext(contextFromNode(node)); 366 return currentContext(); 367 } 368 } 369 370 /** 371 * Open a context, and create / update it if necessary. 372 * 373 * \param rangeNode The range which encompasses the context. 374 * \param type The type of context to open. 375 * \param identifier The identifier which corresponds to the context. 376 * \returns the opened context. 377 */ openContext(T * rangeNode,DUContext::ContextType type,const QualifiedIdentifier & identifier)378 DUContext* openContext(T* rangeNode, DUContext::ContextType type, const QualifiedIdentifier& identifier) 379 { 380 if (m_compilingContexts) { 381 DUContext* ret = openContextInternal(editorFindRangeForContext(rangeNode, rangeNode), type, identifier); 382 setContextOnNode(rangeNode, ret); 383 return ret; 384 } else 385 { 386 openContext(contextFromNode(rangeNode)); 387 return currentContext(); 388 } 389 } 390 391 /** 392 * Open a context, and create / update it if necessary. 393 * 394 * \param fromRange The range which starts the context. 395 * \param toRange The range which ends the context. 396 * \param type The type of context to open. 397 * \param identifier The identifier which corresponds to the context. 398 * \returns the opened context. 399 */ 400 DUContext* openContext(T* fromRange, T* toRange, DUContext::ContextType type, 401 const QualifiedIdentifier& identifier = QualifiedIdentifier()) 402 { 403 if (m_compilingContexts) { 404 DUContext* ret = openContextInternal(editorFindRangeForContext(fromRange, toRange), type, identifier); 405 setContextOnNode(fromRange, ret); 406 return ret; 407 } else 408 { 409 openContext(contextFromNode(fromRange)); 410 return currentContext(); 411 } 412 } 413 414 /** 415 * Open a newly created or previously existing context. 416 * 417 * The open context is put on the context stack, and becomes the new 418 * currentContext(). 419 * 420 * \warning When you call this, you also have to open a range! If you want to re-use 421 * the range associated to the context, use injectContext 422 * 423 * \param newContext Context to open. 424 */ openContext(DUContext * newContext)425 virtual void openContext(DUContext* newContext) 426 { 427 m_contextStack.push(newContext); 428 m_nextContextStack.push(0); 429 } 430 431 /** 432 * This can be used to temporarily change the current context. 433 * \param ctx The context to be injected 434 * */ injectContext(DUContext * ctx)435 void injectContext(DUContext* ctx) 436 { 437 openContext(ctx); 438 } 439 440 /** 441 * Use this to close the context previously injected with injectContext. 442 * */ closeInjectedContext()443 void closeInjectedContext() 444 { 445 m_contextStack.pop(); 446 m_nextContextStack.pop(); 447 } 448 449 /** 450 * Close the current DUContext. When recompiling, this function will remove any 451 * contexts that were not encountered in this passing run. 452 * \note The DUChain write lock is already held here. 453 */ closeContext()454 virtual void closeContext() 455 { 456 { 457 DUChainWriteLocker lock(DUChain::lock()); 458 //Remove all slaves that were not encountered while parsing 459 if (m_compilingContexts) 460 currentContext()->cleanIfNotEncountered(m_encountered); 461 setEncountered(currentContext()); 462 463 m_lastContext = currentContext(); 464 } 465 466 m_contextStack.pop(); 467 m_nextContextStack.pop(); 468 } 469 470 /** 471 * Remember that a specific item has been encoutered while parsing. 472 * All items that are not encountered will be deleted at some stage. 473 * 474 * \param item duchain item that was encountered. 475 * */ setEncountered(DUChainBase * item)476 void setEncountered(DUChainBase* item) 477 { 478 m_encountered.insert(item); 479 } 480 481 /** 482 * Determine whether the given \a item is in the set of encountered items. 483 * 484 * @return true if the \a item has been encountered, otherwise false. 485 * */ wasEncountered(DUChainBase * item)486 bool wasEncountered(DUChainBase* item) 487 { 488 return m_encountered.contains(item); 489 } 490 491 /** 492 * Set the current identifier to \a id. 493 * 494 * \param id the new current identifier. 495 */ setIdentifier(const QString & id)496 void setIdentifier(const QString& id) 497 { 498 m_identifier = Identifier(id); 499 m_qIdentifier.push(m_identifier); 500 } 501 502 /** 503 * Determine the current identifier. 504 * \returns the current identifier. 505 */ qualifiedIdentifier()506 QualifiedIdentifier qualifiedIdentifier() const 507 { 508 return m_qIdentifier; 509 } 510 511 /** 512 * Clears the current identifier. 513 */ clearQualifiedIdentifier()514 void clearQualifiedIdentifier() 515 { 516 m_qIdentifier.clear(); 517 } 518 519 /** 520 * Retrieve the current context stack. This function is not expected 521 * to be used often and may be phased out. 522 * 523 * \todo Audit whether access to the context stack is still required, and provide 524 * replacement functionality if possible. 525 */ contextStack()526 const Stack<DUContext*>& contextStack() const 527 { 528 return m_contextStack; 529 } 530 531 /** 532 * Access the index of the child context which has been encountered. 533 * 534 * \todo further delineate the role of this function and rename / document better. 535 * \todo make private again? 536 */ nextContextIndex()537 int& nextContextIndex() 538 { 539 return m_nextContextStack.top(); 540 } 541 542 /** 543 * Open a context, either creating it if it does not exist, or referencing a previously existing 544 * context if already encountered in a previous duchain parse run (when recompiling()). 545 * 546 * \param range The range of the context. 547 * \param type The type of context to create. 548 * \param identifier The identifier which corresponds to the context. 549 * \returns the opened context. 550 */ 551 openContextInternal(const RangeInRevision & range,DUContext::ContextType type,const QualifiedIdentifier & identifier)552 virtual DUContext* openContextInternal(const RangeInRevision& range, DUContext::ContextType type, 553 const QualifiedIdentifier& identifier) 554 { 555 Q_ASSERT(m_compilingContexts); 556 DUContext* ret = nullptr; 557 558 { 559 if (recompiling()) { 560 DUChainReadLocker readLock(DUChain::lock()); 561 const QVector<DUContext*>& childContexts = currentContext()->childContexts(); 562 563 int currentIndex = nextContextIndex(); 564 const auto indexedIdentifier = IndexedQualifiedIdentifier(identifier); 565 566 for (; currentIndex < childContexts.count(); ++currentIndex) { 567 DUContext* child = childContexts.at(currentIndex); 568 RangeInRevision childRange = child->range(); 569 570 if (child->type() != type) { 571 continue; 572 } 573 // We cannot update a contexts local scope identifier, that will break many other parts, like e.g. 574 // the CodeModel of child contexts or declarations. 575 // For unnamed child-ranges, we still do range-comparison, because we cannot distinguish them in other ways 576 if ((!identifier.isEmpty() && child->indexedLocalScopeIdentifier() == indexedIdentifier) 577 || (identifier.isEmpty() && child->indexedLocalScopeIdentifier().isEmpty() && 578 !childRange.isEmpty() && childRange == range)) { 579 // Match 580 ret = child; 581 readLock.unlock(); 582 DUChainWriteLocker writeLock(DUChain::lock()); 583 584 ret->clearImportedParentContexts(); 585 ++currentIndex; 586 break; 587 } 588 } 589 590 if (ret) 591 nextContextIndex() = currentIndex; //If we had a match, jump forward to that position 592 ///@todo We should also somehow make sure we don't get quadratic worst-case effort while updating. 593 } 594 595 if (!ret) { 596 DUChainWriteLocker writeLock(DUChain::lock()); 597 598 ret = newContext(range); 599 ret->setType(type); 600 601 if (!identifier.isEmpty()) 602 ret->setLocalScopeIdentifier(identifier); 603 604 setInSymbolTable(ret); 605 } else { 606 DUChainWriteLocker writeLock(DUChain::lock()); 607 Q_ASSERT(ret->localScopeIdentifier() == identifier); 608 if (ret->parentContext()) 609 ret->setRange(range); 610 } 611 } 612 613 m_encountered.insert(ret); 614 openContext(ret); 615 return ret; 616 } 617 618 ///This function should call context->setInSymbolTable(..) with an appropriate decision. The duchain is write-locked when this is called. setInSymbolTable(DUContext * context)619 virtual void setInSymbolTable(DUContext* context) 620 { 621 if (!context->parentContext()->inSymbolTable()) { 622 context->setInSymbolTable(false); 623 return; 624 } 625 DUContext::ContextType type = context->type(); 626 context->setInSymbolTable( 627 type == DUContext::Class || type == DUContext::Namespace || type == DUContext::Global || type == DUContext::Helper || 628 type == DUContext::Enum); 629 } 630 631 /// @returns the current url/path ot the document we are parsing document()632 IndexedString document() const 633 { 634 return m_url; 635 } 636 637 private: 638 639 Identifier m_identifier; 640 IndexedString m_url; 641 QualifiedIdentifier m_qIdentifier; 642 bool m_compilingContexts : 1; 643 bool m_recompiling : 1; 644 Stack<int> m_nextContextStack; 645 DUContext* m_lastContext; 646 //Here all valid declarations/uses/... will be collected 647 QSet<DUChainBase*> m_encountered; 648 Stack<DUContext*> m_contextStack; 649 }; 650 } 651 652 #endif 653