/****************************************************************************
**
** Copyright (C) 2020 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtQml module of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:LGPL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Lesser General Public License Usage
** Alternatively, this file may be used under the terms of the GNU Lesser
** General Public License version 3 as published by the Free Software
** Foundation and appearing in the file LICENSE.LGPL3 included in the
** packaging of this file. Please review the following information to
** ensure the GNU Lesser General Public License version 3 requirements
** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
**
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 2.0 or (at your option) the GNU General
** Public license version 3 or any later version approved by the KDE Free
** Qt Foundation. The licenses are as published by the Free Software
** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-2.0.html and
** https://www.gnu.org/licenses/gpl-3.0.html.
**
** $QT_END_LICENSE$
**
****************************************************************************/
#ifndef INLINECOMPONENTUTILS_P_H
#define INLINECOMPONENTUTILS_P_H

//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists purely as an
// implementation detail.  This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.
//

#include <private/qv4compileddata_p.h>
#include <private/qv4resolvedtypereference_p.h>

namespace icutils {
struct Node {
    Node() = default;
    Node(const Node &) = default;
    Node(Node &&) = default;
    Node& operator=(Node const &) = default;
    Node& operator=(Node &&) = default;
    bool operator==(Node const &other) const {return index == other.index;}

    Node(std::vector<QV4::CompiledData::InlineComponent>::size_type s) {
        index = quint32(s);
        temporaryMark = 0;
        permanentMark = 0;
    }

    union {
        quint32_le_bitfield<0, 30> index;
        quint32_le_bitfield<30, 1> temporaryMark;
        quint32_le_bitfield<31, 1> permanentMark;
    };
};

using AdjacencyList = std::vector<std::vector<Node*>>;

template<typename ObjectContainer, typename InlineComponent>
void fillAdjacencyListForInlineComponents(ObjectContainer *objectContainer, AdjacencyList &adjacencyList, std::vector<Node> &nodes, const std::vector<InlineComponent> &allICs) {
    using CompiledObject = typename ObjectContainer::CompiledObject;
    // add an edge from A to B if A and B are inline components with the same containing type
    // and A inherits from B (ignore indirect chains through external types for now)
    // or if A instantiates B
    for (typename std::vector<InlineComponent>::size_type i = 0; i < allICs.size(); ++i) {
        const auto& ic = allICs[i];
        const CompiledObject *obj = objectContainer->objectAt(ic.objectIndex);
        QV4::ResolvedTypeReference *currentICTypeRef = objectContainer->resolvedType(ic.nameIndex);
        auto createEdgeFromTypeRef = [&](QV4::ResolvedTypeReference *targetTypeRef) {
            if (targetTypeRef) {
                const auto targetType = targetTypeRef->type();
                if (targetType.isInlineComponentType()
                        && targetType.containingType() == currentICTypeRef->type().containingType()) {
                    auto icIt = std::find_if(allICs.cbegin(), allICs.cend(), [&](const QV4::CompiledData::InlineComponent &icSearched){
                        return int(icSearched.objectIndex) == targetType.inlineComponentObjectId();
                    });
                    Q_ASSERT(icIt != allICs.cend());
                    Node& target = nodes[i];
                    adjacencyList[std::distance(allICs.cbegin(), icIt)].push_back(&target);
                }
            }
        };
        if (obj->inheritedTypeNameIndex != 0) {
            QV4::ResolvedTypeReference *parentTypeRef = objectContainer->resolvedType(obj->inheritedTypeNameIndex);
            createEdgeFromTypeRef(parentTypeRef);

        }
        auto referencedInICObjectIndex = ic.objectIndex + 1;
        while (int(referencedInICObjectIndex) < objectContainer->objectCount()) {
            auto potentiallyReferencedInICObject = objectContainer->objectAt(referencedInICObjectIndex);
            bool stillInIC = !(potentiallyReferencedInICObject-> flags & QV4::CompiledData::Object::IsInlineComponentRoot)
                    && (potentiallyReferencedInICObject-> flags & QV4::CompiledData::Object::InPartOfInlineComponent);
            if (!stillInIC)
                break;
            createEdgeFromTypeRef(objectContainer->resolvedType(potentiallyReferencedInICObject->inheritedTypeNameIndex));
            ++referencedInICObjectIndex;
        }
    }
};

inline void topoVisit(Node *node, AdjacencyList &adjacencyList, bool &hasCycle, std::vector<Node> &nodesSorted) {
    if (node->permanentMark)
        return;
    if (node->temporaryMark) {
        hasCycle = true;
        return;
    }
    node->temporaryMark = 1;

    auto const &edges = adjacencyList[node->index];
    for (auto edgeTarget =edges.begin(); edgeTarget != edges.end(); ++edgeTarget) {
        topoVisit(*edgeTarget, adjacencyList, hasCycle, nodesSorted);
    }

    node->temporaryMark = 0;
    node->permanentMark = 1;
    nodesSorted.push_back(*node);
};

// Use DFS based topological sorting (https://en.wikipedia.org/wiki/Topological_sorting)
inline std::vector<Node> topoSort(std::vector<Node> &nodes, AdjacencyList &adjacencyList, bool &hasCycle) {
    std::vector<Node> nodesSorted;
    nodesSorted.reserve(nodes.size());

    hasCycle = false;
    auto currentNodeIt = std::find_if(nodes.begin(), nodes.end(), [](const Node& node) {
        return node.permanentMark == 0;
    });
    // Do a topological sort of all inline components
    // afterwards, nodesSorted contains the nodes for the inline components in reverse topological order
    while (currentNodeIt != nodes.end() && !hasCycle) {
        Node& currentNode = *currentNodeIt;
        topoVisit(&currentNode, adjacencyList, hasCycle, nodesSorted);
        currentNodeIt = std::find_if(nodes.begin(), nodes.end(), [](const Node& node) {
            return node.permanentMark == 0;
        });
    }
    return nodesSorted;
}
}

#endif // INLINECOMPONENTUTILS_P_H