File indexing completed on 2024-06-16 04:23:13

0001 /*
0002     SPDX-FileCopyrightText: 2008 Andreas Pakulat <apaku@gmx.de>
0003     SPDX-FileCopyrightText: 2006 Roberto Raggi <roberto@kdevelop.org>
0004     SPDX-FileCopyrightText: 2006-2008 Hamish Rodda <rodda@kde.org>
0005 
0006     SPDX-License-Identifier: LGPL-2.0-or-later
0007 */
0008 
0009 #ifndef KDEVPLATFORM_ABSTRACTABSTRACTCONTEXTBUILDER_H
0010 #define KDEVPLATFORM_ABSTRACTABSTRACTCONTEXTBUILDER_H
0011 
0012 #include <climits>
0013 
0014 #include "../topducontext.h"
0015 #include "../duchainpointer.h"
0016 #include "../duchainlock.h"
0017 #include "../duchain.h"
0018 #include "../ducontext.h"
0019 #include "../identifier.h"
0020 #include "../parsingenvironment.h"
0021 
0022 #include <serialization/indexedstring.h>
0023 #include <util/stack.h>
0024 
0025 namespace KDevelop {
0026 /**
0027  * \short Abstract definition-use chain context builder class
0028  *
0029  * The AbstractContextBuilder is a convenience class template for creating customized
0030  * definition-use chain context builders from an AST.  It simplifies:
0031  * - creating or modifying an existing DUContext tree
0032  * - following a DUContext tree for second and subsequent passes, if required
0033  * - opening and closing DUContext instances
0034  * - tracking which DUContext instances are still present when recompiling, and removing DUContexts which no longer exist in the source code.
0035  *
0036  * \author Hamish Rodda \<rodda@kde.org\>
0037  */
0038 template <typename T, typename NameT>
0039 class AbstractContextBuilder
0040 {
0041 public:
0042     /// Constructor.
0043     AbstractContextBuilder() : m_compilingContexts(false)
0044         , m_recompiling(false)
0045         , m_lastContext(nullptr)
0046     {
0047     }
0048 
0049     virtual ~AbstractContextBuilder()
0050     {
0051     }
0052 
0053     /**
0054      * Entry point for building a definition-use chain with this builder.
0055      *
0056      * This function determines whether we are updating a chain, or creating a new one.  If we are
0057      * creating a new chain, a new TopDUContext is created and registered with DUChain.
0058      *
0059      * \param url Url of the document being parsed.
0060      * \param node AST node to start building from.
0061      * \param updateContext TopDUContext to update if a duchain was previously created for this url, otherwise pass a null pointer.
0062      *
0063      * \returns the newly created or updated TopDUContext pointer.
0064      */
0065     virtual ReferencedTopDUContext build(const IndexedString& url, T* node,
0066                                          const ReferencedTopDUContext& updateContext
0067                                              = ReferencedTopDUContext())
0068     {
0069         m_compilingContexts = true;
0070         m_url = url;
0071 
0072         ReferencedTopDUContext top;
0073         {
0074             DUChainWriteLocker lock(DUChain::lock());
0075             top = updateContext.data();
0076 
0077             if (top) {
0078                 m_recompiling = true;
0079                 Q_ASSERT(top->type() == DUContext::Global);
0080                 Q_ASSERT(DUChain::self()->chainForIndex(top->ownIndex()) == top);
0081             } else
0082             {
0083                 top = newTopContext(RangeInRevision(CursorInRevision(0, 0), CursorInRevision(INT_MAX, INT_MAX)));
0084                 DUChain::self()->addDocumentChain(top);
0085                 top->setType(DUContext::Global);
0086             }
0087 
0088             setEncountered(top);
0089             setContextOnNode(node, top);
0090         }
0091 
0092         supportBuild(node, top);
0093 
0094         m_compilingContexts = false;
0095         return top;
0096     }
0097 
0098 protected:
0099     /**
0100      * Support another builder by tracking the current context.
0101      * @param node the given node.
0102      * @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.
0103      */
0104     virtual void supportBuild(T* node, DUContext* context = nullptr)
0105     {
0106         if (!context)
0107             context = contextFromNode(node);
0108 
0109         Q_ASSERT(context);
0110 
0111         openContext(context);
0112 
0113         startVisiting(node);
0114 
0115         closeContext();
0116 
0117         Q_ASSERT(m_contextStack.isEmpty());
0118     }
0119 
0120     /**
0121      * Entry point to your visitor.  Reimplement and call the appropriate visit function.
0122      *
0123      * \param node AST node to visit.
0124      */
0125     virtual void startVisiting(T* node) = 0;
0126 
0127     /**
0128      * Associate a \a context with a given AST \a node.  Once called on a \a node, the
0129      * contextFromNode() function should return this \a context when called.
0130      *
0131      * \param node AST node to associate
0132      * \param context DUContext to associate
0133      */
0134     virtual void setContextOnNode(T* node, DUContext* context) = 0;
0135 
0136     /**
0137      * Retrieve an associated DUContext from the given \a node.  Used on second and
0138      * subsequent passes of the context builder (for supporting other builds)
0139      *
0140      * \param node AST node which was previously associated
0141      * \returns the DUContext which was previously associated
0142      */
0143     virtual DUContext* contextFromNode(T* node) = 0;
0144 
0145     /**
0146      * Retrieves a text range from the given nodes.
0147      *
0148      * As editor integrators have to be extended to determine ranges from AST nodes,
0149      * this function must be reimplemented to allow generic retrieving of rangs from nodes.
0150      *
0151      * \param fromNode the AST node to start from (on the start boundary)
0152      * \param toNode the AST node to end at (on the end boundary)
0153      *
0154      * \returns the text range encompassing the given AST node(s)
0155      */
0156     virtual RangeInRevision editorFindRange(T* fromNode, T* toNode) = 0;
0157 
0158     /**
0159      * Retrieve a text range for the given nodes.  This is a special function required
0160      * by c++ support as a different range may need to be retrieved depending on
0161      * whether macros are involved.  It is not usually required to implement this
0162      * function separately to editorFindRange() for other languages.
0163      *
0164      * \param fromNode the AST node to start from (on the start boundary)
0165      * \param toNode the AST node to end at (on the end boundary)
0166      *
0167      * \returns the text range encompassing the given AST node(s)
0168      */
0169     virtual RangeInRevision editorFindRangeForContext(T* fromNode, T* toNode)
0170     {
0171         return editorFindRange(fromNode, toNode);
0172     }
0173 
0174     /**
0175      * Determine the QualifiedIdentifier which corresponds to the given ast \a node.
0176      *
0177      * \param node ast node which represents an identifier
0178      * \return the qualified identifier determined from \a node
0179      */
0180     virtual QualifiedIdentifier identifierForNode(NameT* node) = 0;
0181 
0182     /**
0183      * Create a new DUContext from the given \a range.
0184      *
0185      * This exists so that you can create custom DUContext subclasses for your
0186      * language if you need to.
0187      *
0188      * \param range range for the new context to encompass
0189      * \returns the newly created context
0190      */
0191     virtual DUContext* newContext(const RangeInRevision& range)
0192     {
0193         return new DUContext(range, currentContext());
0194     }
0195 
0196     /**
0197      * Create a new TopDUContext from the given \a range.
0198      *
0199      * This exists so that you can create custom TopDUContext subclasses for your
0200      * language if you need to.
0201      *
0202      * \returns the newly created context
0203      */
0204     virtual TopDUContext* newTopContext(const RangeInRevision& range, ParsingEnvironmentFile* file = nullptr)
0205     {
0206         return new TopDUContext(m_url, range, file);
0207     }
0208 
0209     /// Determine the currently open context. \returns the current context.
0210     inline DUContext* currentContext() const { return m_contextStack.top(); }
0211     /// Determine the last closed context. \returns the last closed context.
0212     inline DUContext* lastContext() const { return m_lastContext; }
0213     /// Clears the last closed context.
0214     inline void clearLastContext() { m_lastContext = nullptr; }
0215 
0216     inline void setLastContext(DUContext* context) { m_lastContext = context; }
0217 
0218     TopDUContext* topContext() const
0219     {
0220         return currentContext()->topContext();
0221     }
0222 
0223     /**
0224      * Determine if we are recompiling an existing definition-use chain, or if
0225      * a new chain is being created from scratch.
0226      *
0227      * \returns true if an existing duchain is being updated, otherwise false.
0228      */
0229     inline bool recompiling() const { return m_recompiling; }
0230 
0231     /**
0232      * Tell the context builder whether we are recompiling an existing definition-use chain, or if
0233      * a new chain is being created from scratch.
0234      *
0235      * \param recomp set to true if an existing duchain is being updated, otherwise false.
0236      */
0237     inline void setRecompiling(bool recomp) { m_recompiling = recomp; }
0238 
0239     /**
0240      * Determine whether this pass will create DUContext instances.
0241      *
0242      * On the first pass of definition-use chain compiling, DUContext instances
0243      * are created to represent contexts in the source code.  These contexts are
0244      * associated with their AST nodes at the time (see setContextOnNode()).
0245      *
0246      * On second and subsequent passes, the contexts already exist and thus can be
0247      * retrieved through contextFromNode().
0248      *
0249      * \returns true if compiling contexts (ie. 1st pass), otherwise false.
0250      */
0251     inline bool compilingContexts() const { return m_compilingContexts; }
0252 
0253     /**
0254      * Sets whether we need to create ducontexts, ie. if this is the first pass.
0255      *
0256      * \sa compilingContexts()
0257      */
0258     inline void setCompilingContexts(bool compilingContexts) { m_compilingContexts = compilingContexts; }
0259 
0260     /**
0261      * Create child contexts for only a portion of the document.
0262      *
0263      * \param node The AST node which corresponds to the context to parse
0264      * \param parent The DUContext which encompasses the \a node.
0265      * \returns The DUContext which was reparsed, ie. \a parent.
0266      */
0267     DUContext* buildSubContexts(T* node, DUContext* parent)
0268     {
0269         //     m_compilingContexts = true;
0270         //     m_recompiling = false;
0271         setContextOnNode(node, parent);
0272         {
0273             openContext(contextFromNode(node));
0274             startVisiting(node);
0275             closeContext();
0276         }
0277 
0278         m_compilingContexts = false;
0279 
0280         if (contextFromNode(node) == parent) {
0281             qDebug() <<
0282                 "Error in AbstractContextBuilder::buildSubContexts(...): du-context was not replaced with new one";
0283             DUChainWriteLocker lock(DUChain::lock());
0284             deleteContextOnNode(node);
0285         }
0286 
0287         return contextFromNode(node);
0288     }
0289 
0290     /**
0291      * Delete the DUContext which is associated with the given \a node,
0292      * and remove the association.
0293      *
0294      * \param node Node which is associated with the context to delete.
0295      */
0296     void deleteContextOnNode(T* node)
0297     {
0298         delete contextFromNode(node);
0299         setContextOnNode(node, nullptr);
0300     }
0301 
0302     /**
0303      * Open a context, and create / update it if necessary.
0304      *
0305      * \param rangeNode The range which encompasses the context.
0306      * \param type The type of context to open.
0307      * \param identifier The range which encompasses the name of this context, if one exists.
0308      * \returns the opened context.
0309      */
0310     DUContext* openContext(T* rangeNode, DUContext::ContextType type, NameT* identifier = nullptr)
0311     {
0312         if (m_compilingContexts) {
0313             DUContext* ret = openContextInternal(editorFindRangeForContext(rangeNode,
0314                                                                            rangeNode), type,
0315                                                  identifier ? identifierForNode(identifier) : QualifiedIdentifier());
0316             setContextOnNode(rangeNode, ret);
0317             return ret;
0318         } else
0319         {
0320             openContext(contextFromNode(rangeNode));
0321             return currentContext();
0322         }
0323     }
0324 
0325     /**
0326      * Open a context, and create / update it if necessary.
0327      *
0328      * \param node The range to associate with the context.
0329      * \param range A custom range which the context should encompass.
0330      * \param type The type of context to open.
0331      * \param identifier The range which encompasses the name of this context, if one exists.
0332      * \returns the opened context.
0333      */
0334     DUContext* openContext(T* node, const RangeInRevision& range, DUContext::ContextType type,
0335                            NameT* identifier = nullptr)
0336     {
0337         if (m_compilingContexts) {
0338             DUContext* ret = openContextInternal(range, type, identifier ? identifierForNode(
0339                                                      identifier) : QualifiedIdentifier());
0340             setContextOnNode(node, ret);
0341             return ret;
0342         } else {
0343             openContext(contextFromNode(node));
0344             return currentContext();
0345         }
0346     }
0347 
0348     /**
0349      * Open a context, and create / update it if necessary.
0350      *
0351      * \param node The range to associate with the context.
0352      * \param range A custom range which the context should encompass.
0353      * \param type The type of context to open.
0354      * \param id The identifier for this context
0355      * \returns the opened context.
0356      */
0357     DUContext* openContext(T* node, const RangeInRevision& range, DUContext::ContextType type,
0358                            const QualifiedIdentifier& id)
0359     {
0360         if (m_compilingContexts) {
0361             DUContext* ret = openContextInternal(range, type, id);
0362             setContextOnNode(node, ret);
0363             return ret;
0364         } else {
0365             openContext(contextFromNode(node));
0366             return currentContext();
0367         }
0368     }
0369 
0370     /**
0371      * Open a context, and create / update it if necessary.
0372      *
0373      * \param rangeNode The range which encompasses the context.
0374      * \param type The type of context to open.
0375      * \param identifier The identifier which corresponds to the context.
0376      * \returns the opened context.
0377      */
0378     DUContext* openContext(T* rangeNode, DUContext::ContextType type, const QualifiedIdentifier& identifier)
0379     {
0380         if (m_compilingContexts) {
0381             DUContext* ret = openContextInternal(editorFindRangeForContext(rangeNode, rangeNode), type, identifier);
0382             setContextOnNode(rangeNode, ret);
0383             return ret;
0384         } else
0385         {
0386             openContext(contextFromNode(rangeNode));
0387             return currentContext();
0388         }
0389     }
0390 
0391     /**
0392      * Open a context, and create / update it if necessary.
0393      *
0394      * \param fromRange The range which starts the context.
0395      * \param toRange The range which ends the context.
0396      * \param type The type of context to open.
0397      * \param identifier The identifier which corresponds to the context.
0398      * \returns the opened context.
0399      */
0400     DUContext* openContext(T* fromRange, T* toRange, DUContext::ContextType type,
0401                            const QualifiedIdentifier& identifier = QualifiedIdentifier())
0402     {
0403         if (m_compilingContexts) {
0404             DUContext* ret = openContextInternal(editorFindRangeForContext(fromRange, toRange), type, identifier);
0405             setContextOnNode(fromRange, ret);
0406             return ret;
0407         } else
0408         {
0409             openContext(contextFromNode(fromRange));
0410             return currentContext();
0411         }
0412     }
0413 
0414     /**
0415      * Open a newly created or previously existing context.
0416      *
0417      * The open context is put on the context stack, and becomes the new
0418      * currentContext().
0419      *
0420      * \warning When you call this, you also have to open a range! If you want to re-use
0421      * the range associated to the context, use injectContext
0422      *
0423      * \param newContext Context to open.
0424      */
0425     virtual void openContext(DUContext* newContext)
0426     {
0427         m_contextStack.push(newContext);
0428         m_nextContextStack.push(0);
0429     }
0430 
0431     /**
0432      * This can be used to temporarily change the current context.
0433      * \param ctx The context to be injected
0434      * */
0435     void injectContext(DUContext* ctx)
0436     {
0437         openContext(ctx);
0438     }
0439 
0440     /**
0441      * Use this to close the context previously injected with injectContext.
0442      * */
0443     void closeInjectedContext()
0444     {
0445         m_contextStack.pop();
0446         m_nextContextStack.pop();
0447     }
0448 
0449     /**
0450      * Close the current DUContext.  When recompiling, this function will remove any
0451      * contexts that were not encountered in this passing run.
0452      * \note The DUChain write lock is already held here.
0453      */
0454     virtual void closeContext()
0455     {
0456         {
0457             DUChainWriteLocker lock(DUChain::lock());
0458             //Remove all slaves that were not encountered while parsing
0459             if (m_compilingContexts)
0460                 currentContext()->cleanIfNotEncountered(m_encountered);
0461             setEncountered(currentContext());
0462 
0463             m_lastContext = currentContext();
0464         }
0465 
0466         m_contextStack.pop();
0467         m_nextContextStack.pop();
0468     }
0469 
0470     /**
0471      * Remember that a specific item has been encountered while parsing.
0472      * All items that are not encountered will be deleted at some stage.
0473      *
0474      * \param item duchain item that was encountered.
0475      * */
0476     void setEncountered(DUChainBase* item)
0477     {
0478         m_encountered.insert(item);
0479     }
0480 
0481     /**
0482      * Determine whether the given \a item is in the set of encountered items.
0483      *
0484      * @return true if the \a item has been encountered, otherwise false.
0485      * */
0486     bool wasEncountered(DUChainBase* item)
0487     {
0488         return m_encountered.contains(item);
0489     }
0490 
0491     /**
0492      * Set the current identifier to \a id.
0493      *
0494      * \param id the new current identifier.
0495      */
0496     void setIdentifier(const QString& id)
0497     {
0498         m_identifier = Identifier(id);
0499         m_qIdentifier.push(m_identifier);
0500     }
0501 
0502     /**
0503      * Determine the current identifier.
0504      * \returns the current identifier.
0505      */
0506     QualifiedIdentifier qualifiedIdentifier() const
0507     {
0508         return m_qIdentifier;
0509     }
0510 
0511     /**
0512      * Clears the current identifier.
0513      */
0514     void clearQualifiedIdentifier()
0515     {
0516         m_qIdentifier.clear();
0517     }
0518 
0519     /**
0520      * Retrieve the current context stack.  This function is not expected
0521      * to be used often and may be phased out.
0522      *
0523      * \todo Audit whether access to the context stack is still required, and provide
0524      *       replacement functionality if possible.
0525      */
0526     const Stack<DUContext*>& contextStack() const
0527     {
0528         return m_contextStack;
0529     }
0530 
0531     /**
0532      * Access the index of the child context which has been encountered.
0533      *
0534      * \todo further delineate the role of this function and rename / document better.
0535      * \todo make private again?
0536      */
0537     int& nextContextIndex()
0538     {
0539         return m_nextContextStack.top();
0540     }
0541 
0542     /**
0543      * Open a context, either creating it if it does not exist, or referencing a previously existing
0544      * context if already encountered in a previous duchain parse run (when recompiling()).
0545      *
0546      * \param range The range of the context.
0547      * \param type The type of context to create.
0548      * \param identifier The identifier which corresponds to the context.
0549      * \returns the opened context.
0550      */
0551 
0552     virtual DUContext* openContextInternal(const RangeInRevision& range, DUContext::ContextType type,
0553                                            const QualifiedIdentifier& identifier)
0554     {
0555         Q_ASSERT(m_compilingContexts);
0556         DUContext* ret = nullptr;
0557 
0558         {
0559             if (recompiling()) {
0560                 DUChainReadLocker readLock(DUChain::lock());
0561                 const QVector<DUContext*>& childContexts = currentContext()->childContexts();
0562 
0563                 int currentIndex = nextContextIndex();
0564                 const auto indexedIdentifier = IndexedQualifiedIdentifier(identifier);
0565 
0566                 for (; currentIndex < childContexts.count(); ++currentIndex) {
0567                     DUContext* child = childContexts.at(currentIndex);
0568                     RangeInRevision childRange = child->range();
0569 
0570                     if (child->type() != type) {
0571                         continue;
0572                     }
0573                     // We cannot update a contexts local scope identifier, that will break many other parts, like e.g.
0574                     // the CodeModel of child contexts or declarations.
0575                     // For unnamed child-ranges, we still do range-comparison, because we cannot distinguish them in other ways
0576                     if ((!identifier.isEmpty() && child->indexedLocalScopeIdentifier() == indexedIdentifier)
0577                         || (identifier.isEmpty() && child->indexedLocalScopeIdentifier().isEmpty() &&
0578                             !childRange.isEmpty() && childRange == range)) {
0579                         // Match
0580                         ret = child;
0581                         readLock.unlock();
0582                         DUChainWriteLocker writeLock(DUChain::lock());
0583 
0584                         ret->clearImportedParentContexts();
0585                         ++currentIndex;
0586                         break;
0587                     }
0588                 }
0589 
0590                 if (ret)
0591                     nextContextIndex() = currentIndex; //If we had a match, jump forward to that position
0592                 ///@todo We should also somehow make sure we don't get quadratic worst-case effort while updating.
0593             }
0594 
0595             if (!ret) {
0596                 DUChainWriteLocker writeLock(DUChain::lock());
0597 
0598                 ret = newContext(range);
0599                 ret->setType(type);
0600 
0601                 if (!identifier.isEmpty())
0602                     ret->setLocalScopeIdentifier(identifier);
0603 
0604                 setInSymbolTable(ret);
0605             } else {
0606                 DUChainWriteLocker writeLock(DUChain::lock());
0607                 Q_ASSERT(ret->localScopeIdentifier() == identifier);
0608                 if (ret->parentContext())
0609                     ret->setRange(range);
0610             }
0611         }
0612 
0613         m_encountered.insert(ret);
0614         openContext(ret);
0615         return ret;
0616     }
0617 
0618     ///This function should call context->setInSymbolTable(..) with an appropriate decision. The duchain is write-locked when this is called.
0619     virtual void setInSymbolTable(DUContext* context)
0620     {
0621         if (!context->parentContext()->inSymbolTable()) {
0622             context->setInSymbolTable(false);
0623             return;
0624         }
0625         DUContext::ContextType type = context->type();
0626         context->setInSymbolTable(
0627             type == DUContext::Class || type == DUContext::Namespace || type == DUContext::Global || type == DUContext::Helper ||
0628             type == DUContext::Enum);
0629     }
0630 
0631     /// @returns the current url/path ot the document we are parsing
0632     IndexedString document() const
0633     {
0634         return m_url;
0635     }
0636 
0637 private:
0638 
0639     Identifier m_identifier;
0640     IndexedString m_url;
0641     QualifiedIdentifier m_qIdentifier;
0642     bool m_compilingContexts : 1;
0643     bool m_recompiling : 1;
0644     Stack<int> m_nextContextStack;
0645     DUContext* m_lastContext;
0646     //Here all valid declarations/uses/... will be collected
0647     QSet<DUChainBase*> m_encountered;
0648     Stack<DUContext*> m_contextStack;
0649 };
0650 }
0651 
0652 #endif