// Copyright 2017 Daniel Parker
// Distributed under the Boost license, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

// See https://github.com/danielaparker/jsoncons for latest version

#ifndef JSONCONS_JSONPATCH_JSONPATCH_HPP
#define JSONCONS_JSONPATCH_JSONPATCH_HPP

#include <string>
#include <vector> 
#include <memory>
#include <algorithm> // std::min
#include <utility> // std::move
#include <jsoncons/json.hpp>
#include <jsoncons_ext/jsonpointer/jsonpointer.hpp>
#include <jsoncons_ext/jsonpatch/jsonpatch_error.hpp>

namespace jsoncons { namespace jsonpatch {

namespace detail {

    template <class CharT>
    struct jsonpatch_names
    {
        static std::basic_string<CharT> test_name()
        {
            static std::basic_string<CharT> name{'t','e','s','t'};
            return name;
        }
        static std::basic_string<CharT> add_name()
        {
            static std::basic_string<CharT> name{'a','d','d'};
            return name;
        }
        static std::basic_string<CharT> remove_name()
        {
            static std::basic_string<CharT> name{'r','e','m','o','v','e'};
            return name;
        }
        static std::basic_string<CharT> replace_name()
        {
            static std::basic_string<CharT> name{'r','e','p','l','a','c','e'};
            return name;
        }
        static std::basic_string<CharT> move_name()
        {
            static std::basic_string<CharT> name{'m','o','v','e'};
            return name;
        }
        static std::basic_string<CharT> copy_name()
        {
            static std::basic_string<CharT> name{'c','o','p','y'};
            return name;
        }
        static std::basic_string<CharT> op_name()
        {
            static std::basic_string<CharT> name{'o','p'};
            return name;
        }
        static std::basic_string<CharT> path_name()
        {
            static std::basic_string<CharT> name{'p','a','t','h'};
            return name;
        }
        static std::basic_string<CharT> from_name()
        {
            static std::basic_string<CharT> name{'f','r','o','m'};
            return name;
        }
        static std::basic_string<CharT> value_name()
        {
            static std::basic_string<CharT> name{'v','a','l','u','e'};
            return name;
        }
        static std::basic_string<CharT> dash_name()
        {
            static std::basic_string<CharT> name{'-'};
            return name;
        }
    };

    template<class Json>
    jsonpointer::basic_json_pointer<typename Json::char_type> definite_path(const Json& root, jsonpointer::basic_json_pointer<typename Json::char_type>& location)
    {
        using char_type = typename Json::char_type;
        using string_type = std::basic_string<char_type>;

        auto rit = location.rbegin();
        if (rit == location.rend())
        {
            return location;
        }

        if (*rit != jsonpatch_names<char_type>::dash_name())
        {
            return location;
        }

        std::vector<string_type> tokens;
        for (auto it = location.begin(); it != location.rbegin().base()-1; ++it)
        {
            tokens.push_back(*it);
        }
        jsonpointer::basic_json_pointer<char_type> pointer(tokens);

        std::error_code ec;

        Json val = jsonpointer::get(root, pointer, ec);
        if (ec || !val.is_array())
        {
            return location;
        }
        string_type last_token;
        jsoncons::detail::from_integer(val.size(), last_token);
        tokens.emplace_back(std::move(last_token));

        return jsonpointer::basic_json_pointer<char_type>(std::move(tokens));
    }

    enum class op_type {add,remove,replace};
    enum class state_type {begin,abort,commit};

    template <class Json>
    struct operation_unwinder
    {
        using char_type = typename Json::char_type;
        using string_type = std::basic_string<char_type>;
        using json_pointer_type = jsonpointer::basic_json_pointer<char_type>;

        struct entry
        {
            op_type op;
            json_pointer_type path;
            Json value;

            entry(op_type op, const json_pointer_type& path, const Json& value)
                : op(op), path(path), value(value)
            {
            }

            entry(const entry&) = default;

            entry(entry&&) = default;

            entry& operator=(const entry&) = default;

            entry& operator=(entry&&) = default;
        };

        Json& target;
        state_type state;
        std::vector<entry> stack;

        operation_unwinder(Json& j)
            : target(j), state(state_type::begin)
        {
        }

        ~operation_unwinder() noexcept
        {
            std::error_code ec;
            if (state != state_type::commit)
            {
                for (auto it = stack.rbegin(); it != stack.rend(); ++it)
                {
                    if (it->op == op_type::add)
                    {
                        jsonpointer::add(target,it->path,it->value,ec);
                        if (ec)
                        {
                            //std::cout << "add: " << it->path << std::endl;
                            break;
                        }
                    }
                    else if (it->op == op_type::remove)
                    {
                        jsonpointer::remove(target,it->path,ec);
                        if (ec)
                        {
                            //std::cout << "remove: " << it->path << std::endl;
                            break;
                        }
                    }
                    else if (it->op == op_type::replace)
                    {
                        jsonpointer::replace(target,it->path,it->value,ec);
                        if (ec)
                        {
                            //std::cout << "replace: " << it->path << std::endl;
                            break;
                        }
                    }
                }
            }
        }
    };

    template <class Json>
    Json from_diff(const Json& source, const Json& target, const typename Json::string_view_type& path)
    {
        using char_type = typename Json::char_type;

        Json result = typename Json::array();

        if (source == target)
        {
            return result;
        }

        if (source.is_array() && target.is_array())
        {
            std::size_t common = (std::min)(source.size(),target.size());
            for (std::size_t i = 0; i < common; ++i)
            {
                std::basic_string<char_type> ss(path); 
                ss.push_back('/');
                jsoncons::detail::from_integer(i,ss);
                auto temp_diff = from_diff(source[i],target[i],ss);
                result.insert(result.array_range().end(),temp_diff.array_range().begin(),temp_diff.array_range().end());
            }
            // Element in source, not in target - remove
            for (std::size_t i = source.size(); i-- > target.size();)
            {
                std::basic_string<char_type> ss(path); 
                ss.push_back('/');
                jsoncons::detail::from_integer(i,ss);
                Json val(json_object_arg);
                val.insert_or_assign(jsonpatch_names<char_type>::op_name(), jsonpatch_names<char_type>::remove_name());
                val.insert_or_assign(jsonpatch_names<char_type>::path_name(), ss);
                result.push_back(std::move(val));
            }
            // Element in target, not in source - add, 
            // Fix contributed by Alexander rog13
            for (std::size_t i = source.size(); i < target.size(); ++i)
            {
                const auto& a = target[i];
                std::basic_string<char_type> ss(path); 
                ss.push_back('/');
                jsoncons::detail::from_integer(i,ss);
                Json val(json_object_arg);
                val.insert_or_assign(jsonpatch_names<char_type>::op_name(), jsonpatch_names<char_type>::add_name());
                val.insert_or_assign(jsonpatch_names<char_type>::path_name(), ss);
                val.insert_or_assign(jsonpatch_names<char_type>::value_name(), a);
                result.push_back(std::move(val));
            }
        }
        else if (source.is_object() && target.is_object())
        {
            for (const auto& a : source.object_range())
            {
                std::basic_string<char_type> ss(path);
                ss.push_back('/'); 
                jsonpointer::escape(a.key(),ss);
                auto it = target.find(a.key());
                if (it != target.object_range().end())
                {
                    auto temp_diff = from_diff(a.value(),it->value(),ss);
                    result.insert(result.array_range().end(),temp_diff.array_range().begin(),temp_diff.array_range().end());
                }
                else
                {
                    Json val(json_object_arg);
                    val.insert_or_assign(jsonpatch_names<char_type>::op_name(), jsonpatch_names<char_type>::remove_name());
                    val.insert_or_assign(jsonpatch_names<char_type>::path_name(), ss);
                    result.push_back(std::move(val));
                }
            }
            for (const auto& a : target.object_range())
            {
                auto it = source.find(a.key());
                if (it == source.object_range().end())
                {
                    std::basic_string<char_type> ss(path); 
                    ss.push_back('/');
                    jsonpointer::escape(a.key(),ss);
                    Json val(json_object_arg);
                    val.insert_or_assign(jsonpatch_names<char_type>::op_name(), jsonpatch_names<char_type>::add_name());
                    val.insert_or_assign(jsonpatch_names<char_type>::path_name(), ss);
                    val.insert_or_assign(jsonpatch_names<char_type>::value_name(), a.value());
                    result.push_back(std::move(val));
                }
            }
        }
        else
        {
            Json val(json_object_arg);
            val.insert_or_assign(jsonpatch_names<char_type>::op_name(), jsonpatch_names<char_type>::replace_name());
            val.insert_or_assign(jsonpatch_names<char_type>::path_name(), path);
            val.insert_or_assign(jsonpatch_names<char_type>::value_name(), target);
            result.push_back(std::move(val));
        }

        return result;
    }
}

template <class Json>
void apply_patch(Json& target, const Json& patch, std::error_code& ec)
{
    using char_type = typename Json::char_type;
    using string_type = std::basic_string<char_type>;
    using json_pointer_type = jsonpointer::basic_json_pointer<char_type>;

   jsoncons::jsonpatch::detail::operation_unwinder<Json> unwinder(target);
   std::error_code local_ec;

    // Validate
     
    for (const auto& operation : patch.array_range())
    {
        unwinder.state =jsoncons::jsonpatch::detail::state_type::begin;

        auto it_op = operation.find(detail::jsonpatch_names<char_type>::op_name());
        if (it_op == operation.object_range().end())
        {
            ec = jsonpatch_errc::invalid_patch;
            unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
            return;
        }
        string_type op = it_op->value().template as<string_type>();

        auto it_path = operation.find(detail::jsonpatch_names<char_type>::path_name());
        if (it_path == operation.object_range().end())
        {
            ec = jsonpatch_errc::invalid_patch;
            unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
            return;
        }
        string_type path = it_path->value().template as<string_type>();
        auto location = json_pointer_type::parse(path, local_ec);
        if (local_ec)
        {
            ec = jsonpatch_errc::invalid_patch;
            unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
            return;
        }

        if (op ==jsoncons::jsonpatch::detail::jsonpatch_names<char_type>::test_name())
        {
            Json val = jsonpointer::get(target,location,local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::test_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            auto it_value = operation.find(detail::jsonpatch_names<char_type>::value_name());
            if (it_value == operation.object_range().end())
            {
                ec = jsonpatch_errc::invalid_patch;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            if (val != it_value->value())
            {
                ec = jsonpatch_errc::test_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
        }
        else if (op ==jsoncons::jsonpatch::detail::jsonpatch_names<char_type>::add_name())
        {
            auto it_value = operation.find(detail::jsonpatch_names<char_type>::value_name());
            if (it_value == operation.object_range().end())
            {
                ec = jsonpatch_errc::invalid_patch;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            Json val = it_value->value();
            auto npath = jsonpatch::detail::definite_path(target,location);

            std::error_code insert_ec;
            jsonpointer::add_if_absent(target,npath,val,insert_ec); // try insert without replace
            if (insert_ec) // try a replace
            {
                std::error_code select_ec;
                Json orig_val = jsonpointer::get(target,npath,select_ec);
                if (select_ec) // shouldn't happen
                {
                    ec = jsonpatch_errc::add_failed;
                    unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                    return;
                }
                std::error_code replace_ec;
                jsonpointer::replace(target,npath,val,replace_ec);
                if (replace_ec)
                {
                    ec = jsonpatch_errc::add_failed;
                    unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                    return;
                }
                unwinder.stack.emplace_back(detail::op_type::replace,npath,orig_val);
            }
            else // insert without replace succeeded
            {
                unwinder.stack.emplace_back(detail::op_type::remove,npath,Json::null());
            }
        }
        else if (op ==jsoncons::jsonpatch::detail::jsonpatch_names<char_type>::remove_name())
        {
            Json val = jsonpointer::get(target,location,local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::remove_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            jsonpointer::remove(target,location,local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::remove_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            unwinder.stack.emplace_back(detail::op_type::add, location, val);
        }
        else if (op ==jsoncons::jsonpatch::detail::jsonpatch_names<char_type>::replace_name())
        {
            Json val = jsonpointer::get(target,location,local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::replace_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            auto it_value = operation.find(detail::jsonpatch_names<char_type>::value_name());
            if (it_value == operation.object_range().end())
            {
                ec = jsonpatch_errc::invalid_patch;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            jsonpointer::replace(target, location, it_value->value(), local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::replace_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            unwinder.stack.emplace_back(detail::op_type::replace,location,val);
        }
        else if (op ==jsoncons::jsonpatch::detail::jsonpatch_names<char_type>::move_name())
        {
            auto it_from = operation.find(detail::jsonpatch_names<char_type>::from_name());
            if (it_from == operation.object_range().end())
            {
                ec = jsonpatch_errc::invalid_patch;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            string_type from = it_from->value().as_string();
            auto from_pointer = json_pointer_type::parse(from, local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::move_failed;
                unwinder.state = jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }

            Json val = jsonpointer::get(target, from_pointer, local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::move_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            jsonpointer::remove(target, from_pointer, local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::move_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            unwinder.stack.emplace_back(detail::op_type::add, from_pointer, val);
            // add
            std::error_code insert_ec;
            auto npath = jsonpatch::detail::definite_path(target,location);
            jsonpointer::add_if_absent(target,npath,val,insert_ec); // try insert without replace
            if (insert_ec) // try a replace
            {
                std::error_code select_ec;
                Json orig_val = jsonpointer::get(target,npath,select_ec);
                if (select_ec) // shouldn't happen
                {
                    ec = jsonpatch_errc::copy_failed;
                    unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                    return;
                }
                std::error_code replace_ec;
                jsonpointer::replace(target, npath, val, replace_ec);
                if (replace_ec)
                {
                    ec = jsonpatch_errc::copy_failed;
                    unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                    return;
                }
                unwinder.stack.emplace_back(jsoncons::jsonpatch::detail::op_type::replace,npath,orig_val);
            }
            else
            {
                unwinder.stack.emplace_back(detail::op_type::remove,npath,Json::null());
            }
        }
        else if (op ==jsoncons::jsonpatch::detail::jsonpatch_names<char_type>::copy_name())
        {
            auto it_from = operation.find(detail::jsonpatch_names<char_type>::from_name());
            if (it_from == operation.object_range().end())
            {
                ec = jsonpatch_errc::invalid_patch;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            string_type from = it_from->value().as_string();
            Json val = jsonpointer::get(target,from,local_ec);
            if (local_ec)
            {
                ec = jsonpatch_errc::copy_failed;
                unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                return;
            }
            // add
            auto npath = jsonpatch::detail::definite_path(target,location);
            std::error_code insert_ec;
            jsonpointer::add_if_absent(target,npath,val,insert_ec); // try insert without replace
            if (insert_ec) // Failed, try a replace
            {
                std::error_code select_ec;
                Json orig_val = jsonpointer::get(target,npath, select_ec);
                if (select_ec) // shouldn't happen
                {
                    ec = jsonpatch_errc::copy_failed;
                    unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                    return;
                }
                std::error_code replace_ec;
                jsonpointer::replace(target, npath, val,replace_ec);
                if (replace_ec)
                {
                    ec = jsonpatch_errc::copy_failed;
                    unwinder.state =jsoncons::jsonpatch::detail::state_type::abort;
                    return;
                }
                unwinder.stack.emplace_back(jsoncons::jsonpatch::detail::op_type::replace,npath,orig_val);
            }
            else
            {
                unwinder.stack.emplace_back(detail::op_type::remove,npath,Json::null());
            }
        }
    }
    if (unwinder.state ==jsoncons::jsonpatch::detail::state_type::begin)
    {
        unwinder.state =jsoncons::jsonpatch::detail::state_type::commit;
    }
}

template <class Json>
Json from_diff(const Json& source, const Json& target)
{
    std::basic_string<typename Json::char_type> path;
    return jsoncons::jsonpatch::detail::from_diff(source, target, path);
}

template <class Json>
void apply_patch(Json& target, const Json& patch)
{
    std::error_code ec;
    apply_patch(target, patch, ec);
    if (ec)
    {
        JSONCONS_THROW(jsonpatch_error(ec));
    }
}

}}

#endif