// Copyright (C) 2017 xaizek <xaizek@posteo.net>
//
// This file is part of zograscope.
//
// zograscope is free software: you can redistribute it and/or modify
// it under the terms of version 3 of the GNU Affero General Public License as
// published by the Free Software Foundation.
//
// zograscope is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with zograscope.  If not, see <http://www.gnu.org/licenses/>.

#ifndef ZOGRASCOPE_TREE_HPP_
#define ZOGRASCOPE_TREE_HPP_

#include <boost/utility/string_ref.hpp>

#include <cstdint>

#include <memory>
#include <string>
#include <vector>

#include "pmr/pmr_deque.hpp"
#include "pmr/pmr_vector.hpp"

#include "utils/Pool.hpp"
#include "Language.hpp"
#include "types.hpp"

enum class State : std::uint8_t
{
    Unchanged,
    Deleted,
    Inserted,
    Updated
};

class PNode;
class SNode;

enum class SType : std::uint8_t;

struct Node
{
    using allocator_type = cpp17::pmr::polymorphic_allocator<cpp17::byte>;

    boost::string_ref label;
    // Leafs whose label is modified for the purpose of processing have
    // non-empty spelling that matches unmodified label.
    boost::string_ref spelling;
    cpp17::pmr::vector<Node *> children;
    Node *relative = nullptr;
    Node *parent = nullptr;
    Node *next = nullptr;
    int valueChild = -1;
    int poID = -1; // Post-order ID.
    int line = 0;
    int col = 0;
    Type type : 8;
    SType stype : 8;
    State state : 8;
    bool satellite : 1; // Decorative element or node whose match was finalized.
    bool moved : 1;
    bool last : 1; // This is root of a tree from the last layer.
    bool leaf : 1; // This node corresponds to something in the source.

    Node(allocator_type al = {})
        : children(al),
          type(Type::Virtual),
          stype(),
          state(State::Unchanged),
          satellite(false), moved(false), last(false), leaf(false)
    {
    }
    Node(const Node &rhs) = delete;
    Node(Node &&rhs) = default;
    Node(Node &&rhs, allocator_type al = {})
        : label(std::move(rhs.label)),
          spelling(std::move(rhs.spelling)),
          children(std::move(rhs.children), al),
          relative(rhs.relative),
          parent(rhs.parent),
          next(rhs.next),
          valueChild(rhs.valueChild),
          poID(rhs.poID),
          line(rhs.line),
          col(rhs.col),
          type(rhs.type),
          stype(rhs.stype),
          state(rhs.state),
          satellite(rhs.satellite),
          moved(rhs.moved),
          last(rhs.last),
          leaf(rhs.leaf)
    {
    }
    Node & operator=(const Node &rhs) = delete;
    Node & operator=(Node &&rhs) = default;

    bool hasValue() const
    {
        return (valueChild >= 0);
    }

    Node * getValue()
    {
        return (valueChild >= 0 ? children[valueChild] : nullptr);
    }

    const Node * getValue() const
    {
        return (valueChild >= 0 ? children[valueChild] : nullptr);
    }
};

class Tree
{
    using allocator_type = cpp17::pmr::polymorphic_allocator<cpp17::byte>;

public:
    Tree(allocator_type al = {})
        : nodes(al), stringified(al), internPool(al), tabWidth(0)
    { }
    Tree(const Tree &rhs) = delete;
    Tree(Tree &&rhs) = default;
    Tree(std::unique_ptr<Language> lang, int tabWidth,
         const std::string &contents, const PNode *node,
         allocator_type al = {});
    Tree(std::unique_ptr<Language> lang, int tabWidth,
         const std::string &contents, const SNode *node,
         allocator_type al = {});

    Tree & operator=(const Tree &rhs) = delete;
    Tree & operator=(Tree &&rhs) = default;

public:
    // Checks whether the tree is empty and thus shouldn't be used.
    bool isEmpty() const
    {
        return (root == nullptr);
    }

    Node * getRoot()
    {
        return root;
    }

    const Node * getRoot() const
    {
        return root;
    }

    // Retrieves language associated with this tree.
    Language * getLanguage()
    {
        return lang.get();
    }

    // Retrieves language associated with this tree as constant object.
    const Language * getLanguage() const
    {
        return lang.get();
    }

    // Marks nodes of the subtree as moved if that makes sense for them.
    void markTreeAsMoved(Node *node);

    // Marks all nodes with their positions on pre-order traversal.
    void markInPreOrder();

    // Dumps tree on standard output for debugging purposes.
    void dump() const;

    // Propagates states (both added/deleted and moved flags) across layers of
    // the tree.
    void propagateStates();

private:
    // Turns SNode-subtree into a corresponding Node-subtree.
    Node * materializeSNode(const std::string &contents,
                            const SNode *node, const SNode *parent);
    // Turns PNode-subtree into a corresponding Node-subtree.
    Node * materializePNode(const std::string &contents, const PNode *node);

    // Interns a string.
    boost::string_ref intern(std::string &&str);

private:
    std::unique_ptr<Language> lang;
    // Storage of all nodes managed by this unit.
    Pool<Node> nodes;
    Node *root = nullptr;
    // Storage of most labels and spelling.
    cpp17::pmr::vector<char> stringified;
    // Storage for interned strings.
    cpp17::pmr::deque<std::string> internPool;
    // Width of a single tabulation character.
    int tabWidth;
};

std::vector<Node *> postOrder(Node &root);

void reduceTreesCoarse(Node *T1, Node *T2);

// Turns tree defined by the node into a string.
std::string printSubTree(const Node &root, bool withComments,
                         int size_hint = -1);

bool canForceLeafMatch(const Node *x, const Node *y);

// Dumps tree defined by the node into specified stream for debugging purposes.
void dumpTree(std::ostream &os, const Node *node, const Language *lang);

#endif // ZOGRASCOPE_TREE_HPP_