/****************************************************************************

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the tools applications of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

/*

  tree.cpp

*/

#include <QDomDocument>

#include "atom.h"

#include "doc.h"

#include "htmlgenerator.h"

#include "location.h"

#include "node.h"

#include "text.h"

#include "tree.h"

#include <limits.h>

#include <qdebug.h>

QT_BEGIN_NAMESPACE

struct InheritanceBound

{

    Node::Access access;

    QStringList basePath;

    QString dataTypeWithTemplateArgs;

    InnerNode *parent;

    InheritanceBound()

        : access(Node::Public) { }

    InheritanceBound(Node::Access access0,

                     const QStringList& basePath0,

                     const QString &dataTypeWithTemplateArgs0,

                     InnerNode *parent)

	: access(access0), basePath(basePath0),

	  dataTypeWithTemplateArgs(dataTypeWithTemplateArgs0),

          parent(parent) { }

};

struct Target

{

    Node *node;

    Atom *atom;

    int priority;

};

typedef QMap<PropertyNode::FunctionRole, QString> RoleMap;

typedef QMap<PropertyNode *, RoleMap> PropertyMap;

typedef QMultiMap<QString, Node *> GroupMap;

typedef QMultiHash<QString, FakeNode *> FakeNodeHash;

typedef QMultiHash<QString, Target> TargetHash;

class TreePrivate

{

public:

    QMap<ClassNode *, QList<InheritanceBound> > unresolvedInheritanceMap;

    PropertyMap unresolvedPropertyMap;

    GroupMap groupMap;

    QMultiMap<QString, QString> publicGroupMap;

    FakeNodeHash fakeNodesByTitle;

    TargetHash targetHash;

    QList<QPair<ClassNode*,QString> > basesList;

    QList<QPair<FunctionNode*,QString> > relatedList;

};

/*!

  \class Tree

 */

/*!

  The default constructor is the only constructor.

 */

Tree::Tree()

    : roo(0, "")

{

    priv = new TreePrivate;

}

/*!

  The destructor deletes the internal, private tree.

 */

Tree::~Tree()

{

    delete priv;

}

/*!

 */

{

    return const_cast<Node*>(const_cast<const Tree*>(this)->findNode(path,

                                                                     relative,

}

/*!

 */

{

    do {

        int i;

        for (i = 0; i < path.size(); ++i) {

            if (node == 0 || !node->isInnerNode())

                break;

            const Node *next =

                static_cast<const InnerNode*>(node)->findNode(path.at(i));

            if (!next && (findFlags & SearchEnumValues) && i == path.size()-1)

                next = static_cast<const InnerNode*>(node)->findEnumNodeForValue(path.at(i));

            if (!next && node->type() == Node::Class && (findFlags & SearchBaseClasses)) {

                NodeList baseClasses = allBaseClasses(static_cast<const ClassNode *>(node));

                foreach (const Node *baseClass, baseClasses) {

                    next = static_cast<const InnerNode *>(baseClass)->findNode(path.at(i));

                    if (!next && (findFlags & SearchEnumValues) && i == path.size() - 1)

                        next = static_cast<const InnerNode *>(baseClass)

                                        ->findEnumNodeForValue(path.at(i));

                    if (next)

                        break;

                }

            }

            node = next;

        }

        if (node && i == path.size()

                && (!(findFlags & NonFunction) || node->type() != Node::Function

    return 0;

}

/*!

  Find the node with the specified \a path name of the

  specified \a type.

 */

Node *Tree::findNode(const QStringList &path,

                     Node::Type type,

                     Node *relative,

                     int findFlags)

{

    return const_cast<Node*>(const_cast<const Tree*>(this)->findNode(path,

                                                                     type,

                                                                     relative,

                                                                     findFlags));

}

/*!

  Find the node with the specified \a path name of the

  specified \a type.

 */

const Node *Tree::findNode(const QStringList &path,

                           Node::Type type,

                           const Node *relative,

                           int findFlags) const

{

    const Node *node = findNode(path, relative, findFlags);

    if (node != 0 && node->type() == type)

        return node;

    return 0;

}

/*!

 */

FunctionNode *Tree::findFunctionNode(const QStringList& path,

                                     Node *relative,

                                     int findFlags)

{

    return const_cast<FunctionNode *>(

                const_cast<const Tree *>(this)->findFunctionNode(path,

                                                                 relative,

                                                                 findFlags));

}

/*!

 */

const FunctionNode *Tree::findFunctionNode(const QStringList &path,

                                           const Node *relative,

                                           int findFlags) const

{

    if (!relative)

        relative = root();

    do {

        const Node *node = relative;

        int i;

        for (i = 0; i < path.size(); ++i) {

            if (node == 0 || !node->isInnerNode())

                break;

            const Node *next;

            if (i == path.size() - 1)

                next = ((InnerNode *) node)->findFunctionNode(path.at(i));

            else

                next = ((InnerNode *) node)->findNode(path.at(i));

            if (!next && node->type() == Node::Class &&

                (findFlags & SearchBaseClasses)) {

                NodeList baseClasses = allBaseClasses(static_cast<const ClassNode *>(node));

                foreach (const Node *baseClass, baseClasses) {

                    if (i == path.size() - 1)

                        next = static_cast<const InnerNode *>(baseClass)->findFunctionNode(path.at(i));

                    else

                        next = static_cast<const InnerNode *>(baseClass)->findNode(path.at(i));

                    if (next)

                        break;

                }

            }

            node = next;

        }

        if (node && i == path.size() && node->isFunction()) {

            // CppCodeParser::processOtherMetaCommand ensures that reimplemented

            // functions are private.

            const FunctionNode *func = static_cast<const FunctionNode*>(node);

            while (func->access() == Node::Private) {

                const FunctionNode *from = func->reimplementedFrom();

                if (from != 0) {

                    if (from->access() != Node::Private)

                        return from;

                    else

                        func = from;

                }

                else

                    break;

            }

            return func;

        }

        relative = relative->parent();

    } while (relative);

    return 0;

}

/*!

 */

FunctionNode *Tree::findFunctionNode(const QStringList &parentPath,

                                     const FunctionNode *clone,

                                     Node *relative,

                                     int findFlags)

{

    return const_cast<FunctionNode *>(

		const_cast<const Tree *>(this)->findFunctionNode(parentPath,

                                                                 clone,

                                      				 relative,

                                                                 findFlags));

}

/*!

 */

const FunctionNode *Tree::findFunctionNode(const QStringList &parentPath,

                                           const FunctionNode *clone,

                                           const Node *relative,

                                           int findFlags) const

{

    const Node *parent = findNode(parentPath, relative, findFlags);

    if (parent == 0 || !parent->isInnerNode()) {

        return 0;

    }

    else {

        return ((InnerNode *)parent)->findFunctionNode(clone);

    }

}

static const int NumSuffixes = 3;

static const char * const suffixes[NumSuffixes] = { "", "s", "es" };

/*!

 */

const FakeNode *Tree::findFakeNodeByTitle(const QString &title) const

{

    for (int pass = 0; pass < NumSuffixes; ++pass) {

        FakeNodeHash::const_iterator i =

                priv->fakeNodesByTitle.find(Doc::canonicalTitle(title + suffixes[pass]));

        if (i != priv->fakeNodesByTitle.constEnd()) {

            FakeNodeHash::const_iterator j = i;

            ++j;

            if (j != priv->fakeNodesByTitle.constEnd() && j.key() == i.key()) {

                QList<Location> internalLocations;

                while (j != priv->fakeNodesByTitle.constEnd()) {

                    if (j.key() == i.key() && j.value()->url().isEmpty())

                        internalLocations.append(j.value()->doc().location());

                    ++j;

                }

                if (internalLocations.size() > 0) {

                    i.value()->doc().location().warning(

                        tr("Page '%1' defined in more than one location:").arg(title));

                    foreach (const Location &location, internalLocations)

                        location.warning(tr("(defined here)"));

                }

            }

            return i.value();

        }

    }

    return 0;

}

/*!

 */

const Node*

Tree::findUnambiguousTarget(const QString &target, Atom *&atom) const

{

    Target bestTarget = {0, 0, INT_MAX};

    int numBestTargets = 0;

    for (int pass = 0; pass < NumSuffixes; ++pass) {

        TargetHash::const_iterator i =

                priv->targetHash.find(Doc::canonicalTitle(target + suffixes[pass]));

        if (i != priv->targetHash.constEnd()) {

            TargetHash::const_iterator j = i;

            do {

                const Target &candidate = j.value();

                if (candidate.priority < bestTarget.priority) {

                    bestTarget = candidate;

                    numBestTargets = 1;

                } else if (candidate.priority == bestTarget.priority) {

                    ++numBestTargets;

                }

                ++j;

            } while (j != priv->targetHash.constEnd() && j.key() == i.key());

            if (numBestTargets == 1) {

                atom = bestTarget.atom;

                return bestTarget.node;

            }

        }

    }

    return 0;

}

/*!

 */

Atom *Tree::findTarget(const QString &target, const Node *node) const

{

    for (int pass = 0; pass < NumSuffixes; ++pass) {

        QString key = Doc::canonicalTitle(target + suffixes[pass]);

        TargetHash::const_iterator i = priv->targetHash.find(key);

        if (i != priv->targetHash.constEnd()) {

            do {

                if (i.value().node == node)

                    return i.value().atom;

                ++i;

            } while (i != priv->targetHash.constEnd() && i.key() == key);

        }

    }

    return 0;

}

/*!

 */

void Tree::addBaseClass(ClassNode *subclass, Node::Access access,

                        const QStringList &basePath,

                        const QString &dataTypeWithTemplateArgs,

                        InnerNode *parent)

{

    priv->unresolvedInheritanceMap[subclass].append(

	    InheritanceBound(access,

                             basePath,

                             dataTypeWithTemplateArgs,

                             parent)

                                                   );

}

/*!

 */

void Tree::addPropertyFunction(PropertyNode *property,

                               const QString &funcName,

                               PropertyNode::FunctionRole funcRole)

{

    priv->unresolvedPropertyMap[property].insert(funcRole, funcName);

}

/*!

  This function adds the \a node to the \a group. The group

  can be listed anywhere using the \e{annotated list} command.

 */

void Tree::addToGroup(Node *node, const QString &group)

{

    priv->groupMap.insert(group, node);

}

/*!

 */

QMultiMap<QString, Node *> Tree::groups() const

{

    return priv->groupMap;

}

/*!

 */

void Tree::addToPublicGroup(Node *node, const QString &group)

{

    priv->publicGroupMap.insert(node->name(), group);

    addToGroup(node, group);

}

/*!

 */

QMultiMap<QString, QString> Tree::publicGroups() const

{

    return priv->publicGroupMap;

}

/*!

 */

void Tree::resolveInheritance(NamespaceNode *rootNode)

{

    if (!rootNode)

        rootNode = root();

    for (int pass = 0; pass < 2; pass++) {

        NodeList::ConstIterator c = rootNode->childNodes().begin();

        while (c != rootNode->childNodes().end()) {

                resolveInheritance(pass, (ClassNode *) *c);

            else if ((*c)->type() == Node::Namespace) {

                NamespaceNode *ns = static_cast<NamespaceNode*>(*c);

                resolveInheritance(ns);

            }

            ++c;

        }

        if (rootNode == root())

            priv->unresolvedInheritanceMap.clear();

    }

}

/*!

 */

void Tree::resolveProperties()

{

    PropertyMap::ConstIterator propEntry;

    propEntry = priv->unresolvedPropertyMap.begin();

    while (propEntry != priv->unresolvedPropertyMap.end()) {

        PropertyNode *property = propEntry.key();

        InnerNode *parent = property->parent();

        QString getterName = (*propEntry)[PropertyNode::Getter];

        QString setterName = (*propEntry)[PropertyNode::Setter];

        QString resetterName = (*propEntry)[PropertyNode::Resetter];

        QString notifierName = (*propEntry)[PropertyNode::Notifier];

        NodeList::ConstIterator c = parent->childNodes().begin();

        while (c != parent->childNodes().end()) {

            if ((*c)->type() == Node::Function) {

                FunctionNode *function = static_cast<FunctionNode *>(*c);

                if (function->access() == property->access() &&

                    (function->status() == property->status() ||

                     function->doc().isEmpty())) {

                    if (function->name() == getterName) {

                        property->addFunction(function, PropertyNode::Getter);

                    } else if (function->name() == setterName) {

                        property->addFunction(function, PropertyNode::Setter);

                    } else if (function->name() == resetterName) {

                        property->addFunction(function, PropertyNode::Resetter);

                    } else if (function->name() == notifierName) {

                        property->addSignal(function, PropertyNode::Notifier);

                    }

                }

            }

            ++c;

        }

        ++propEntry;

    }

    propEntry = priv->unresolvedPropertyMap.begin();