qdoc: Teach qdoc to use multiple trees (part 2)

qdoc now knows how to search the forrest of node
trees in an optimal order. But there remain some
problems with specific searches that cross module
boundaries. These include group membership and C++
and QML module membership, as well ass C++ base
class resolution. Part 3 will be concerned with
fixing these remaining bugs.

With this update, qdoc now takes less time to
generate the docs for Qt 5. Testing indicates
that qdoc run time has dropped from about 14
minutes to about 7.5 minutes on an iMac.

Task-number: QTBUG-35377
Change-Id: I6bded6ef54124b4f6e5914cad4548f0b600209b0
Reviewed-by: Martin Smith <martin.smith@digia.com>

1 files changed, 213 insertions, 52 deletions

diff --git a/src/tools/qdoc/qdocdatabase.h b/src/tools/qdoc/qdocdatabase.h
index 4e50396817..8541f03106 100644
--- a/src/tools/qdoc/qdocdatabase.h
+++ b/src/tools/qdoc/qdocdatabase.h
@@ -45,6 +45,8 @@
 #include <qstring.h>
 #include <qmap.h>
 #include "tree.h"
+#include "config.h"
+#include <qdebug.h>
 
 QT_BEGIN_NAMESPACE
 
@@ -54,10 +56,10 @@ typedef QMap<QString, NodeMap> NodeMapMap;
 typedef QMap<QString, NodeMultiMap> NodeMultiMapMap;
 typedef QMultiMap<QString, Node*> QDocMultiMap;
 typedef QMap<Text, const Node*> TextToNodeMap;
-typedef QMultiMap<QString, DocNode*> DocNodeMultiMap;
 
 class Atom;
 class Generator;
+class QDocDatabase;
 
 enum FindFlag {
     SearchBaseClasses = 0x1,
@@ -65,20 +67,159 @@ enum FindFlag {
     NonFunction = 0x4
 };
 
-struct TargetRec
+class QDocForest
 {
   public:
-    enum Type { Unknown, Target, Keyword, Contents, Class, Function, Page, Subtitle };
-    TargetRec() : node_(0), priority_(INT_MAX), type_(Unknown) { }
-    bool isEmpty() const { return ref_.isEmpty(); }
-    //void debug(int idx, const QString& key);
-    Node* node_;
-    QString ref_;
-    int priority_;
-    Type type_;
-};
-typedef QMultiMap<QString, TargetRec> TargetRecMultiMap;
+    friend class QDocDatabase;
+    QDocForest(QDocDatabase* qdb)
+        : qdb_(qdb), primaryTree_(0), currentIndex_(0) { }
+    ~QDocForest();
+
+    NamespaceNode* firstRoot();
+    NamespaceNode* nextRoot();
+    Tree* firstTree();
+    Tree* nextTree();
+    Tree* primaryTree() { return primaryTree_; }
+    NamespaceNode* primaryTreeRoot() { return (primaryTree_ ? primaryTree_->root() : 0); }
+    bool isEmpty() const { return searchOrder_.isEmpty(); }
+    bool done() const { return (currentIndex_ >= searchOrder_.size()); }
+    const QVector<Tree*>& searchOrder();
+    void setSearchOrder();
+
+    const Node* findNode(const QStringList& path, const Node* relative, int findFlags) {
+        foreach (Tree* t, searchOrder_) {
+            const Node* n = t->findNode(path, relative, findFlags);
+            if (n) {
+                return n;
+            }
+            relative = 0;
+        }
+        if (Config::debug_)
+            qDebug() << "FAILED SEARCH 1" << path;
+        return 0;
+    }
 
+    Node* findNodeByNameAndType(const QStringList& path,
+                                Node::Type type,
+                                Node::SubType subtype,
+                                bool acceptCollision = false) {
+        foreach (Tree* t, searchOrder_) {
+            Node* n = t->findNodeByNameAndType(path, type, subtype, acceptCollision);
+            if (n) {
+                return n;
+            }
+        }
+        if (Config::debug_)
+            qDebug() << "FAILED SEARCH 2" << path << type << subtype;
+        return 0;
+    }
+
+    ClassNode* findClassNode(const QStringList& path) {
+        foreach (Tree* t, searchOrder_) {
+            ClassNode* n = t->findClassNode(path);
+            if (n) {
+                return n;
+            }
+        }
+        if (Config::debug_)
+            qDebug() << "FAILED SEARCH 3" << path;
+        return 0;
+    }
+
+    InnerNode* findRelatesNode(const QStringList& path) {
+        foreach (Tree* t, searchOrder_) {
+            InnerNode* n = t->findRelatesNode(path);
+            if (n) {
+                return n;
+            }
+        }
+        if (Config::debug_)
+            qDebug() << "FAILED SEARCH 4" << path;
+        return 0;
+    }
+
+    const Node* resolveTarget(const QString& target, const Node* relative) {
+        const Node* r = relative;
+        foreach (Tree* t, searchOrder_) {
+            const Node* n = resolveTargetHelper(target, relative, t);
+            if (n) {
+                return n;
+            }
+            relative = 0;
+        }
+        if (Config::debug_) {
+            qDebug() << "FAILED SEARCH 6" << target << r;
+        }
+        return 0;
+    }
+
+    const Node* resolveType(const QStringList& path, const Node* relative)
+    {
+        foreach (Tree* t, searchOrder_) {
+            const Node* n = resolveTypeHelper(path, relative, t);
+            if (n) {
+                return n;
+            }
+            relative = 0;
+        }
+        if (Config::debug_)
+            qDebug() << "FAILED SEARCH 5" << path;
+        return 0;
+    }
+
+    QString findTarget(const QString& target, const Node* node) const
+    {
+        foreach (Tree* t, searchOrder_) {
+            QString ref = t->findTarget(target, node);
+            if (!ref.isEmpty()) {
+                return ref;
+            }
+        }
+        if (Config::debug_)
+            qDebug() << "FAILED SEARCH 7" << target;
+        return QString();
+    }
+
+    const Node* findUnambiguousTarget(const QString& target, QString& ref, const Node* relative)
+    {
+        foreach (Tree* t, searchOrder_) {
+            const Node* n = t->findUnambiguousTarget(target, ref, relative);
+            if (n) {
+                return n;
+            }
+        }
+        if (Config::debug_)
+            qDebug() << "FAILED SEARCH 8" << target;
+        return 0;
+    }
+
+    const DocNode* findDocNodeByTitle(const QString& title, const Node* relative) const
+    {
+        foreach (Tree* t, searchOrder_) {
+            const DocNode* n = t->findDocNodeByTitle(title, relative);
+            if (n) {
+                return n;
+            }
+        }
+        if (Config::debug_)
+            qDebug() << "FAILED SEARCH 9" << title;
+        return 0;
+    }
+
+  private:
+    void newPrimaryTree(const QString& module);
+    NamespaceNode* newIndexTree(const QString& module);
+    const Node* resolveTargetHelper(const QString& target, const Node* relative, Tree* t);
+    const Node* resolveTypeHelper(const QStringList& path, const Node* relative, Tree* t);
+
+  private:
+    QDocDatabase*          qdb_;
+    Tree*                  primaryTree_;
+    int                    currentIndex_;
+    QMap<QString, Tree*>   forest_;
+    QVector<Tree*>         searchOrder_;
+    QVector<QString>       moduleNames_;
+};
 
 class QDocDatabase
 {
@@ -90,8 +231,8 @@ class QDocDatabase
     ~QDocDatabase();
 
     const DocNodeMap& groups() const { return groups_; }
-    const DocNodeMap& modules() const { return modules_; }
-    const DocNodeMap& qmlModules() const { return qmlModules_; }
+    //const DocNodeMap& modules() const { return modules_; } // not used
+    //const DocNodeMap& qmlModules() const { return qmlModules_; } // not used
 
     DocNode* getGroup(const QString& name);
     DocNode* findGroup(const QString& name);
@@ -106,15 +247,15 @@ class QDocDatabase
     DocNode* addToModule(const QString& name, Node* node);
     void addToQmlModule(const QString& name, Node* node);
 
-    QmlClassNode* findQmlType(const QString& qmid, const QString& name) const;
+    QmlClassNode* findQmlType(const QString& qmid, const QString& name);
     QmlClassNode* findQmlType(const ImportRec& import, const QString& name) const;
 
-    void findAllClasses(const InnerNode *node);
-    void findAllFunctions(const InnerNode *node);
-    void findAllLegaleseTexts(const InnerNode *node);
-    void findAllNamespaces(const InnerNode *node);
-    void findAllObsoleteThings(const InnerNode* node);
-    void findAllSince(const InnerNode *node);
+    void findAllClasses(InnerNode *node);
+    void findAllFunctions(InnerNode *node);
+    void findAllLegaleseTexts(InnerNode *node);
+    void findAllNamespaces(InnerNode *node);
+    void findAllObsoleteThings(InnerNode* node);
+    void findAllSince(InnerNode *node);
     void buildCollections();
 
     // special collection access functions
@@ -137,57 +278,63 @@ class QDocDatabase
     /* convenience functions
        Many of these will be either eliminated or replaced.
     */
-    QString refForAtom(const Atom* atom);
-    Tree* tree() { return tree_; }
-    NamespaceNode* treeRoot() { return tree_->root(); }
-    void resolveInheritance() { tree_->resolveInheritance(); }
+    void resolveInheritance() { primaryTree()->resolveInheritance(); }
     void resolveQmlInheritance(InnerNode* root);
     void resolveIssues();
-    void fixInheritance() { tree_->fixInheritance(); }
-    void resolveProperties() { tree_->resolveProperties(); }
+    void fixInheritance() { primaryTree()->fixInheritance(); }
+    void resolveProperties() { primaryTree()->resolveProperties(); }
 
-    /*******************************************************************
-      The functions declared below don't search in the tree(s).
-    ********************************************************************/
-    QString findTarget(const QString &target, const Node *node) const;
-    void resolveTargets(InnerNode* root);
-    void insertTarget(const QString& name, TargetRec::Type type, Node* node, int priority);
-    /*******************************************************************/
+    void resolveTargets() {
+        primaryTree()->resolveTargets(primaryTreeRoot());
+    }
+    void insertTarget(const QString& name, TargetRec::Type type, Node* node, int priority) {
+        primaryTree()->insertTarget(name, type, node, priority);
+    }
 
     /*******************************************************************
       The functions declared below are called for the current tree only.
     ********************************************************************/
     FunctionNode* findFunctionNode(const QStringList& parentPath, const FunctionNode* clone) {
-        return tree_->findFunctionNode(parentPath, clone);
+        return primaryTree()->findFunctionNode(parentPath, clone);
     }
     FunctionNode* findNodeInOpenNamespace(const QStringList& parentPath, const FunctionNode* clone);
     Node* findNodeInOpenNamespace(QStringList& path, Node::Type type, Node::SubType subtype);
-    NameCollisionNode* findCollisionNode(const QString& name) const {
-        return tree_->findCollisionNode(name);
+    NameCollisionNode* findCollisionNode(const QString& name) {
+        return primaryTree()->findCollisionNode(name);
+    }
+    NameCollisionNode* checkForCollision(const QString& name) {
+        return primaryTree()->checkForCollision(name);
     }
     /*******************************************************************/
 
     /*******************************************************************
       The functions declared below are called for all trees.
     ********************************************************************/
-    ClassNode* findClassNode(const QStringList& path) { return tree_->findClassNode(path); }
-    InnerNode* findRelatesNode(const QStringList& path) { return tree_->findRelatesNode(path); }
-    const Node* resolveTarget(const QString& target, const Node* relative);
+    ClassNode* findClassNode(const QStringList& path) { return forest_.findClassNode(path); }
+    InnerNode* findRelatesNode(const QStringList& path) { return forest_.findRelatesNode(path); }
+    QString findTarget(const QString& target, const Node* node) const {
+        return forest_.findTarget(target, node);
+    }
+    const Node* resolveTarget(const QString& target, const Node* relative) {
+        return forest_.resolveTarget(target, relative);
+    }
+    const Node* resolveType(const QString& type, const Node* relative);
     const Node* findNodeForTarget(const QString& target, const Node* relative);
-    const DocNode* findDocNodeByTitle(const QString& title, const Node* relative = 0) const;
-    const Node* findUnambiguousTarget(const QString& target, QString& ref, const Node* relative);
-    Node* findNodeByNameAndType(const QStringList& path, Node::Type type, Node::SubType subtype){
-        return tree_->findNodeByNameAndType(path, type, subtype, 0);
+    const DocNode* findDocNodeByTitle(const QString& title, const Node* relative = 0) const {
+        return forest_.findDocNodeByTitle(title, relative);
+    }
+    const Node* findUnambiguousTarget(const QString& target, QString& ref, const Node* relative) {
+        return forest_.findUnambiguousTarget(target, ref, relative);
     }
-    NameCollisionNode* checkForCollision(const QString& name) const {
-        return tree_->checkForCollision(name);
+    Node* findNodeByNameAndType(const QStringList& path, Node::Type type, Node::SubType subtype){
+        return forest_.findNodeByNameAndType(path, type, subtype, false);
     }
     /*******************************************************************/
 
     void addPropertyFunction(PropertyNode* property,
                              const QString& funcName,
                              PropertyNode::FunctionRole funcRole) {
-        tree_->addPropertyFunction(property, funcName, funcRole);
+        primaryTree()->addPropertyFunction(property, funcName, funcRole);
     }
 
     void setVersion(const QString& v) { version_ = v; }
@@ -205,6 +352,14 @@ class QDocDatabase
     void insertOpenNamespace(const QString& path) { openNamespaces_.insert(path); }
     void setShowInternal(bool value) { showInternal_ = value; }
 
+    // Try to make this function private.
+    QDocForest& forest() { return forest_; }
+    NamespaceNode* primaryTreeRoot() { return forest_.primaryTreeRoot(); }
+    void newPrimaryTree(const QString& module) { forest_.newPrimaryTree(module); }
+    NamespaceNode* newIndexTree(const QString& module) { return forest_.newIndexTree(module); }
+    const QVector<Tree*>& searchOrder() { return forest_.searchOrder(); }
+    void setSearchOrder() { forest_.setSearchOrder(); }
+
     /* debugging functions */
     void printModules() const;
     void printQmlModules() const;
@@ -213,17 +368,25 @@ class QDocDatabase
     friend class QDocIndexFiles;
     friend class QDocTagFiles;
 
+    const Node* findNode(const QStringList& path, const Node* relative, int findFlags) {
+        return forest_.findNode(path, relative, findFlags);
+    }
+    void processForest(void (QDocDatabase::*) (InnerNode*));
+    static void initializeDB();
+
  private:
     QDocDatabase();
-    QDocDatabase(QDocDatabase const& ) { };         // copy constructor is private
-    QDocDatabase& operator=(QDocDatabase const& );  // assignment operator is private
+    QDocDatabase(QDocDatabase const& ) : showInternal_(false), forest_(this) { }
+    QDocDatabase& operator=(QDocDatabase const& );
+    Tree* primaryTree() { return forest_.primaryTree(); }
 
  private:
     static QDocDatabase*    qdocDB_;
+    static NodeMap          typeNodeMap_;
     bool                    showInternal_;
     QString                 version_;
     QDocMultiMap            masterMap_;
-    Tree*                   tree_;
+    QDocForest              forest_;
     DocNodeMap              groups_;
     DocNodeMap              modules_;
     DocNodeMap              qmlModules_;
@@ -244,8 +407,6 @@ class QDocDatabase
     NodeMultiMapMap         newSinceMaps_;
     NodeMapMap              funcIndex_;
     TextToNodeMap           legaleseTexts_;
-    DocNodeMultiMap         docNodesByTitle_;
-    TargetRecMultiMap       targetRecMultiMap_;
     QSet<QString>           openNamespaces_;
 };