config.cpp

Go to the documentation of this file.

/*
    Copyright (C) 2003 - 2025
    by Guillaume Melquiond <guillaume.melquiond@gmail.com>
    Copyright (C) 2003 by David White <dave@whitevine.net>
    Part of the Battle for Wesnoth Project https://www.wesnoth.org/
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.
    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY.
 
    See the COPYING file for more details.
*/
 
/**
 * @file
 * Routines related to configuration-files / WML.
 */
 
#include "config.hpp"
 
#include "formatter.hpp"
#include "log.hpp"
#include "deprecation.hpp"
#include "game_version.hpp"
#include "serialization/parser.hpp"
#include "serialization/string_utils.hpp"
#include "utils/general.hpp"
 
#include <algorithm>
#include <cstring>
#include <iterator>
 
static lg::log_domain log_config("config");
#define ERR_CF LOG_STREAM(err, log_config)
#define DBG_CF LOG_STREAM(debug, log_config)
 
static lg::log_domain log_wml("wml");
#define ERR_WML LOG_STREAM(err, log_wml)
 
namespace
{
// std::map::operator[] does not support heterogeneous lookup so we need this to work around.
template<typename Map, typename Key>
typename Map::iterator map_get(Map& map, Key&& key)
{
    auto res = map.lower_bound(key);
 
    if(res == map.end() || key != res->first) {
        res = map.emplace_hint(res, std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>());
    }
 
    return res;
}
 
// std::map::erase does not support heterogeneous lookup so we need this to work around.
template<typename Map, typename Key>
int map_erase_key(Map& map, Key&& key)
{
    auto i = map.find(key);
    if(i != map.end()) {
        map.erase(i);
        return 1;
    }
    return 0;
}
 
}
 
/* ** config implementation ** */
 
const char* config::diff_track_attribute = "__diff_track";
 
config::config()
    : values_()
    , children_()
    , ordered_children_()
{
}
 
config::config(const config& cfg)
    : values_(cfg.values_)
    , children_()
    , ordered_children_()
{
    append_children(cfg);
}
 
config::config(std::string_view child)
    : values_()
    , children_()
    , ordered_children_()
{
    add_child(child);
}
 
config::~config()
{
    clear();
}
 
config& config::operator=(const config& cfg)
{
    if(this == &cfg) {
        return *this;
    }
 
    config tmp(cfg);
    swap(tmp);
    return *this;
}
 
config::config(config&& cfg) noexcept
    : values_(std::move(cfg.values_))
    , children_(std::move(cfg.children_))
    , ordered_children_(std::move(cfg.ordered_children_))
{
}
 
config& config::operator=(config&& cfg) noexcept
{
    clear();
    swap(cfg);
    return *this;
}
 
bool config::valid_tag(std::string_view name)
{
    if(name == "") {
        // Empty strings not allowed
        return false;
    } else if(name == "_") {
        // A lone underscore isn't a valid tag name
        return false;
    } else {
        return std::all_of(name.begin(), name.end(), [](const char& c)
        {
            /* Only alphanumeric ASCII characters and underscores are allowed.
 
            We're using a manual check mainly for performance. @gfgtdf measured
            that a manual check can be up to 30 times faster than std::isalnum().
 
            - Jyrki, 2019-01-19 */
            return (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') ||
                (c >= '0' && c <= '9') || (c == '_');
        });
    }
}
 
bool config::valid_attribute(std::string_view name)
{
    return valid_tag(name);
}
 
bool config::has_attribute(std::string_view key) const
{
    return values_.find(key) != values_.end();
}
 
void config::remove_attribute(std::string_view key)
{
    map_erase_key(values_, key);
}
 
void config::append_children(const config& cfg)
{
    for(const auto [key, cfg] : cfg.all_children_view()) {
        add_child(key, cfg);
    }
}
 
void config::append_attributes(const config& cfg)
{
    for(const auto& [key, value] : cfg.values_) {
        values_[key] = value;
    }
}
 
void config::append_children(const config& cfg, std::string_view key)
{
    for(const config& value : cfg.child_range(key)) {
        add_child(key, value);
    }
}
 
void config::append(const config& cfg)
{
    append_children(cfg);
    for(const auto& [key, value] : cfg.values_) {
        values_[key] = value;
    }
}
 
void config::append(config&& cfg)
{
    if(children_.empty()) {
        //optimisation
        children_ = std::move(cfg.children_);
        ordered_children_ = std::move(cfg.ordered_children_);
        cfg.clear_all_children();
    }
    else {
        for(const auto [child_key, child_value] : cfg.all_children_view()) {
            add_child(child_key, std::move(child_value));
        }
        cfg.clear_all_children();
    }
 
    if(values_.empty()) {
        //optimisation.
        values_ = std::move(cfg.values_);
    }
    else {
        for(const auto& [key, value] : cfg.values_) {
            //TODO: move the attributes as well?
            values_[key] = value;
        }
    }
    cfg.clear_attributes();
}
 
void config::append_children_by_move(config& cfg, std::string_view key)
{
    // DO note this leaves the tags empty in the source config. Not sure if
    // that should be changed.
    for(config& value : cfg.child_range(key)) {
        add_child(key, std::move(value));
    }
 
    cfg.clear_children_impl(key);
}
 
void config::merge_children(std::string_view key)
{
    if(child_count(key) < 2) {
        return;
    }
 
    config merged_children;
    for(config& cfg : child_range(key)) {
        merged_children.append(std::move(cfg));
    }
 
    clear_children_impl(key);
    add_child(key, std::move(merged_children));
}
 
void config::merge_children_by_attribute(std::string_view key, std::string_view attribute)
{
    if(child_count(key) < 2) {
        return;
    }
 
    typedef std::map<std::string, config> config_map;
    config_map merged_children_map;
    for(config& cfg : child_range(key)) {
        merged_children_map[cfg[attribute]].append(std::move(cfg));
    }
 
    clear_children_impl(key);
    for(const config_map::value_type& i : merged_children_map) {
        add_child(key, i.second); // TODO: can we use std::move?
    }
}
 
config::child_itors config::child_range(std::string_view key)
{
    child_map::iterator i = children_.find(key);
    static child_list dummy;
    child_list* p = &dummy;
    if(i != children_.end()) {
        p = &i->second;
    }
 
    return child_itors(child_iterator(p->begin()), child_iterator(p->end()));
}
 
config::const_child_itors config::child_range(std::string_view key) const
{
    child_map::const_iterator i = children_.find(key);
    static child_list dummy;
    const child_list* p = &dummy;
    if(i != children_.end()) {
        p = &i->second;
    }
 
    return const_child_itors(const_child_iterator(p->begin()), const_child_iterator(p->end()));
}
 
std::size_t config::child_count(std::string_view key) const
{
    child_map::const_iterator i = children_.find(key);
    if(i != children_.end()) {
        return i->second.size();
    }
 
    return 0;
}
 
std::size_t config::all_children_count() const
{
    return ordered_children_.size();
}
 
std::size_t config::attribute_count() const
{
    return std::count_if(values_.begin(), values_.end(), [](const attribute& v) { return !v.second.blank(); });
}
 
bool config::has_child(std::string_view key) const
{
    child_map::const_iterator i = children_.find(key);
    return i != children_.end() && !i->second.empty();
}
 
namespace {
template<class Tchildren>
auto get_child_impl(Tchildren& children, std::string_view key, int n) -> optional_config_impl<std::remove_reference_t<decltype(**(*children.begin()).second.begin())>>
{
 
    auto i = children.find(key);
    if(i == children.end()) {
        DBG_CF << "The config object has no child named ‘" << key << "’.";
        return utils::nullopt;
    }
 
    if(n < 0) {
        n = static_cast<int>(i->second.size()) + n;
    }
 
    try {
        return *i->second.at(n);
    } catch(const std::out_of_range&) {
        DBG_CF << "The config object has only ‘" << i->second.size() << "’ children named ‘" << key
               << "’; request for the index ‘" << n << "’ cannot be honored.";
        return utils::nullopt;
    }
}
 
}
 
config& config::mandatory_child(std::string_view key, const std::string& parent)
{
    if(auto res = get_child_impl(children_, key, 0)) {
        return *res;
    } else {
        throw error("Mandatory WML child ‘[" + std::string(key) + "]’ missing in ‘" + parent + "’. Please report this bug.");
    }
}
 
const config& config::mandatory_child(std::string_view key, const std::string& parent) const
{
    if(auto res = get_child_impl(children_, key, 0)) {
        return *res;
    } else {
        throw error("Mandatory WML child ‘[" + std::string(key) + "]’ missing in ‘" + parent + "’. Please report this bug.");
    }
}
 
config& config::mandatory_child(std::string_view key, int n)
{
    if(auto res = get_child_impl(children_, key, n)) {
        return *res;
    } else {
        throw error("Child [" + std::string(key) + "] at index " + std::to_string(n) + " not found");
    }
}
 
const config& config::mandatory_child(std::string_view key, int n) const
{
    if(auto res = get_child_impl(children_, key, n)) {
        return *res;
    } else {
        throw error("Child [" + std::string(key) + "] at index " + std::to_string(n) + " not found");
    }
}
 
optional_config config::optional_child(std::string_view key, int n)
{
    return get_child_impl(children_, key, n);
}
 
optional_const_config config::optional_child(std::string_view key, int n) const
{
    return get_child_impl(children_, key, n);
}
 
const config& config::child_or_empty(std::string_view key) const
{
    static const config empty_cfg;
    child_map::const_iterator i = children_.find(key);
    if(i != children_.end() && !i->second.empty()) {
        return *i->second.front();
    }
 
    return empty_cfg;
}
 
config& config::child_or_add(std::string_view key)
{
    child_map::const_iterator i = children_.find(key);
    if(i != children_.end() && !i->second.empty()) {
        return *i->second.front();
    }
 
    return add_child(key);
}
 
optional_config_impl<const config> config::get_deprecated_child(std::string_view old_key, const std::string& in_tag, DEP_LEVEL level, const std::string& message) const
{
    if(auto res = optional_child(old_key)) {
        const std::string what = formatter() << "[" << in_tag << "][" << old_key << "]";
        deprecated_message(what, level, "", message);
        return res;
    }
 
    return utils::nullopt;
}
 
config::const_child_itors config::get_deprecated_child_range(std::string_view old_key, const std::string& in_tag, DEP_LEVEL level, const std::string& message) const
{
    static child_list dummy;
    const child_list* p = &dummy;
 
    if(auto i = children_.find(old_key); i != children_.end() && !i->second.empty()) {
        const std::string what = formatter() << "[" << in_tag << "][" << old_key << "]";
        deprecated_message(what, level, "", message);
        p = &i->second;
    }
 
    return const_child_itors(const_child_iterator(p->begin()), const_child_iterator(p->end()));
}
 
config& config::add_child(std::string_view key)
{
    auto iter = map_get(children_, key);
    child_list& v = iter->second;
    v.emplace_back(new config());
    ordered_children_.emplace_back(iter, v.size() - 1);
    return *v.back();
}
 
config& config::add_child(std::string_view key, const config& val)
{
    auto iter = map_get(children_, key);
    child_list& v = iter->second;
    v.emplace_back(new config(val));
    ordered_children_.emplace_back(iter, v.size() - 1);
 
    return *v.back();
}
 
config& config::add_child(std::string_view key, config&& val)
{
    auto iter = map_get(children_, key);
    child_list& v = iter->second;
    v.emplace_back(new config(std::move(val)));
    ordered_children_.emplace_back(iter, v.size() - 1);
 
    return *v.back();
}
 
config& config::add_child_at(std::string_view key, const config& val, std::size_t index)
{
    auto iter = map_get(children_, key);
    child_list& v = iter->second;
    if(index > v.size()) {
        throw error("illegal index to add child at");
    }
 
    v.emplace(v.begin() + index, new config(val));
 
    bool inserted = false;
 
    const child_pos value(iter, index);
 
    std::vector<child_pos>::iterator ord = ordered_children_.begin();
    for(; ord != ordered_children_.end(); ++ord) {
        if(ord->pos != value.pos)
            continue;
        if(!inserted && ord->index == index) {
            ord = ordered_children_.insert(ord, value);
            inserted = true;
        } else if(ord->index >= index) {
            ord->index++;
        }
    }
 
    if(!inserted) {
        ordered_children_.push_back(value);
    }
 
    return *v[index];
}
 
std::size_t config::find_total_first_of(std::string_view key, std::size_t start)
{
    assert(start <= ordered_children_.size());
    const std::size_t npos = static_cast<std::size_t>(-1);
 
    auto pos = std::find_if(ordered_begin() + start, ordered_end(), [&](const config::any_child& can){ return can.key == key; });
 
    if(pos == ordered_end()) {
        return npos;
    }
 
    return static_cast<std::size_t>(pos - ordered_begin());
}
 
config& config::add_child_at_total(std::string_view key, const config &val, std::size_t pos)
{
    assert(pos <= ordered_children_.size());
    if(pos == ordered_children_.size()) {
        //optimisation
        return config::add_child(key, val);
    }
 
    auto end = ordered_children_.end();
    auto pos_it = ordered_children_.begin() + pos;
    auto next = std::find_if(pos_it, end,[&](const child_pos& p){ return p.pos->first == key; });
 
    if(next == end) {
        config& res = config::add_child(key, val);
        //rotate the just inserted element to position pos.
        std::rotate(ordered_children_.begin() + pos, ordered_children_.end() - 1, ordered_children_.end());
        return res;
    }
 
    auto pl = next->pos;
    child_list& l = pl->second;
    const auto index = next->index;
    config& res = **(l.emplace(l.begin() + index, new config(val)));
 
    for(auto ord = next; ord != end; ++ord) {
        //this changes next->index and all later refernces to that tag.
        if(ord->pos == pl) {
            ++ord->index;
        }
    }
 
    //finally insert our new child in ordered_children_.
    ordered_children_.insert(pos_it, { pl, index });
    return res;
}
 
void config::clear_children_impl(std::string_view key)
{
    child_map::iterator i = children_.find(key);
    if(i == children_.end())
        return;
 
    utils::erase_if(ordered_children_, [&i](const config::child_pos& pos) { return pos.pos == i; });
    children_.erase(i);
}
 
void config::splice_children(config& src, std::string_view key)
{
    child_map::iterator i_src = src.children_.find(key);
    if(i_src == src.children_.end()) {
        return;
    }
 
    utils::erase_if(src.ordered_children_, [&i_src](const config::child_pos& pos) { return pos.pos == i_src; });
 
    auto i_dst = map_get(children_, key);
    child_list& dst = i_dst->second;
 
    const auto before = dst.size();
    dst.insert(dst.end(),
        std::move_iterator{i_src->second.begin()},
        std::move_iterator{i_src->second.end()});
 
    src.children_.erase(i_src);
    // key might be a reference to i_src->first, so it is no longer usable.
 
    for(std::size_t j = before; j < dst.size(); ++j) {
        ordered_children_.emplace_back(i_dst, j);
    }
}
 
void config::recursive_clear_value(std::string_view key)
{
    map_erase_key(values_, key);
 
    for(std::pair<const std::string, child_list>& p : children_) {
        for(auto& cfg : p.second) {
            cfg->recursive_clear_value(key);
        }
    }
}
 
std::vector<config::child_pos>::iterator config::remove_child(const child_map::iterator& pos, std::size_t index)
{
    /* Find the position with the correct index and decrement all the
       indices in the ordering that are above this index. */
    std::size_t found = 0;
    for(child_pos& p : ordered_children_) {
        if(p.pos != pos) {
            continue;
        }
 
        if(p.index == index) {
            found = &p - &ordered_children_.front();
        } else if(p.index > index) {
            --p.index;
        }
    }
 
    // Remove from the child map.
    pos->second.erase(pos->second.begin() + index);
 
    // Erase from the ordering and return the next position.
    return ordered_children_.erase(ordered_children_.begin() + found);
}
 
config::all_children_iterator config::erase(const config::all_children_iterator& i)
{
    return all_children_iterator(remove_child(i.i_->pos, i.i_->index));
}
 
void config::remove_child(std::string_view key, std::size_t index)
{
    child_map::iterator i = children_.find(key);
    if(i == children_.end() || index >= i->second.size()) {
        ERR_CF << "Error: attempting to delete non-existing child: " << key << "[" << index << "]";
        return;
    }
 
    remove_child(i, index);
}
 
void config::remove_children(std::string_view key, const std::function<bool(const config&)>& p)
{
    child_map::iterator pos = children_.find(key);
    if(pos == children_.end()) {
        return;
    }
 
    const auto predicate = [p](const std::unique_ptr<config>& child)
    {
        return !p || p(*child);
    };
 
    auto child_it = std::find_if(pos->second.begin(), pos->second.end(), predicate);
    while(child_it != pos->second.end()) {
        const auto index = std::distance(pos->second.begin(), child_it);
        remove_child(pos, index);
        child_it = std::find_if(pos->second.begin() + index, pos->second.end(), predicate);
    }
}
 
const config::attribute_value& config::operator[](std::string_view key) const
{
    const attribute_map::const_iterator i = values_.find(key);
    if(i != values_.end()) {
        return i->second;
    }
 
    static const attribute_value empty_attribute;
    return empty_attribute;
}
 
const config::attribute_value* config::get(std::string_view key) const
{
    attribute_map::const_iterator i = values_.find(key);
    return i != values_.end() ? &i->second : nullptr;
}
 
const config::attribute_value& config::get_or(const std::string_view key, const std::string_view default_key) const
{
    const config::attribute_value & value = operator[](key);
    return !value.blank() ? value : operator[](default_key);
}
 
config::attribute_value& config::operator[](std::string_view key)
{
    auto res = values_.lower_bound(key);
 
    if(res == values_.end() || key != res->first) {
        res = values_.emplace_hint(res, std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>());
    }
 
    return res->second;
}
 
const config::attribute_value& config::get_old_attribute(std::string_view key, const std::string& old_key, const std::string& in_tag, const std::string& message) const
{
    if(has_attribute(old_key)) {
        const std::string what = formatter() << "[" << in_tag << "]" << old_key << "=";
        const std::string msg  = formatter() << "Use " << key << "= instead. " << message;
        deprecated_message(what, DEP_LEVEL::INDEFINITE, "", msg);
    }
 
    attribute_map::const_iterator i = values_.find(key);
    if(i != values_.end()) {
        return i->second;
    }
 
    i = values_.find(old_key);
    if(i != values_.end()) {
        return i->second;
    }
 
    static const attribute_value empty_attribute;
    return empty_attribute;
}
 
const config::attribute_value& config::get_deprecated_attribute(std::string_view old_key, const std::string& in_tag, DEP_LEVEL level, const std::string& message) const
{
    if(auto i = values_.find(old_key); i != values_.end()) {
        const std::string what = formatter() << "[" << in_tag << "]" << old_key << "=";
        deprecated_message(what, level, "", message);
        return i->second;
    }
 
    static const attribute_value empty_attribute;
    return empty_attribute;
}
 
void config::merge_attributes(const config& cfg)
{
    assert(this != &cfg);
    for(const auto& [key, value] : cfg.values_) {
        if(key.substr(0, 7) == "add_to_") {
            std::string add_to = key.substr(7);
            values_[add_to] = values_[add_to].to_double() + value.to_double();
        } else if(key.substr(0, 10) == "concat_to_") {
            std::string concat_to = key.substr(10);
            // TODO: Only use t_string if one or both are actually translatable?
            // That probably requires using a visitor though.
            values_[concat_to] = values_[concat_to].t_str() + value.t_str();
        } else {
            values_[key] = value;
        }
    }
}
 
config::const_attr_itors config::attribute_range() const
{
    const_attr_itors range(const_attribute_iterator(values_.begin()), const_attribute_iterator(values_.end()));
 
    // Ensure the first element is not blank, as a few places assume this
    while(range.begin() != range.end() && range.begin()->second.blank()) {
        range.pop_front();
    }
 
    return range;
}
 
config::attr_itors config::attribute_range()
{
    attr_itors range(attribute_iterator(values_.begin()), attribute_iterator(values_.end()));
 
    // Ensure the first element is not blank, as a few places assume this
    while(range.begin() != range.end() && range.begin()->second.blank()) {
        range.pop_front();
    }
 
    return range;
}
 
optional_config config::find_child(std::string_view key, const std::string& name, const std::string& value)
{
    const child_map::iterator i = children_.find(key);
    if(i == children_.end()) {
        DBG_CF << "Key ‘" << name << "’ value ‘" << value << "’ pair not found as child of key ‘" << key << "’.";
        return utils::nullopt;
    }
 
    const child_list::iterator j = utils::ranges::find(i->second, value,
        [&](const std::unique_ptr<config>& pcfg) -> const auto& { return (*pcfg)[name]; });
 
    if(j != i->second.end()) {
        return **j;
    }
 
    DBG_CF << "Key ‘" << name << "’ value ‘" << value << "’ pair not found as child of key ‘" << key << "’.";
 
    return utils::nullopt;
}
 
config& config::find_mandatory_child(std::string_view key, const std::string &name, const std::string &value)
{
    auto res = find_child(key, name, value);
    if(res) {
        return *res;
    }
    throw error("Cannot find child [" + std::string(key) + "] with " + name + "=" + value);
}
 
const config& config::find_mandatory_child(std::string_view key, const std::string &name, const std::string &value) const
{
    auto res = find_child(key, name, value);
    if(res) {
        return *res;
    }
    throw error("Cannot find child [" + std::string(key) + "] with " + name + "=" + value);
}
 
void config::clear()
{
    // No validity check for this function.
    children_.clear();
    values_.clear();
    ordered_children_.clear();
}
 
void config::clear_all_children()
{
    // No validity check for this function.
    children_.clear();
    ordered_children_.clear();
}
 
void config::clear_attributes()
{
    // No validity check for this function.
    values_.clear();
}
 
bool config::empty() const
{
    return children_.empty() && values_.empty();
}
 
config::all_children_iterator::reference config::all_children_iterator::operator*() const
{
    return any_child(&i_->pos->first, i_->pos->second[i_->index].get());
}
 
config::const_all_children_iterator::reference config::const_all_children_iterator::operator*() const
{
    return any_child(&i_->pos->first, i_->pos->second[i_->index].get());
}
 
config::const_all_children_iterator config::ordered_begin() const
{
    return const_all_children_iterator(ordered_children_.cbegin());
}
 
config::const_all_children_iterator config::ordered_cbegin() const
{
    return const_all_children_iterator(ordered_children_.cbegin());
}
 
config::const_all_children_iterator config::ordered_end() const
{
    return const_all_children_iterator(ordered_children_.cend());
}
 
config::const_all_children_iterator config::ordered_cend() const
{
    return const_all_children_iterator(ordered_children_.cend());
}
 
config::const_all_children_itors config::all_children_range() const
{
    return const_all_children_itors(
        const_all_children_iterator(ordered_children_.cbegin()),
        const_all_children_iterator(ordered_children_.cend())
    );
}
 
config::all_children_iterator config::ordered_begin()
{
    return all_children_iterator(ordered_children_.begin());
}
 
config::all_children_iterator config::ordered_end()
{
    return all_children_iterator(ordered_children_.end());
}
 
config::all_children_itors config::all_children_range()
{
    return all_children_itors(
        all_children_iterator(ordered_children_.begin()),
        all_children_iterator(ordered_children_.end())
    );
}
 
config config::get_diff(const config& c) const
{
    config res;
    get_diff(c, res);
    return res;
}
 
void config::get_diff(const config& c, config& res) const
{
    config* inserts = nullptr;
 
    for(const auto& [key, value] : values_) {
        if(value.blank()) {
            continue;
        }
 
        const attribute_map::const_iterator j = c.values_.find(key);
        if(j == c.values_.end() || (value != j->second && !value.blank())) {
            if(inserts == nullptr) {
                inserts = &res.add_child("insert");
            }
 
            (*inserts)[key] = value;
        }
    }
 
    config* deletes = nullptr;
 
    for(const auto& [key, value] : c.values_) {
        if(value.blank()) {
            continue;
        }
 
        const attribute_map::const_iterator itor = values_.find(key);
        if(itor == values_.end() || itor->second.blank()) {
            if(deletes == nullptr) {
                deletes = &res.add_child("delete");
            }
 
            (*deletes)[key] = "x";
        }
    }
 
    std::vector<std::string> entities;
 
    for(const auto& child : children_) {
        entities.push_back(child.first);
    }
 
    for(const auto& child : c.children_) {
        if(children_.count(child.first) == 0) {
            entities.push_back(child.first);
        }
    }
 
    for(const std::string& entity : entities) {
        const child_map::const_iterator itor_a = children_.find(entity);
        const child_map::const_iterator itor_b = c.children_.find(entity);
 
        static const child_list dummy;
 
        // Get the two child lists. 'b' has to be modified to look like 'a'.
        const child_list& a = itor_a != children_.end() ? itor_a->second : dummy;
        const child_list& b = itor_b != c.children_.end() ? itor_b->second : dummy;
 
        std::size_t ndeletes = 0;
        std::size_t ai = 0, bi = 0;
        while(ai != a.size() || bi != b.size()) {
            // If the two elements are the same, nothing needs to be done.
            if(ai < a.size() && bi < b.size() && *a[ai] == *b[bi]) {
                ++ai;
                ++bi;
            } else {
                // We have to work out what the most appropriate operation --
                // delete, insert, or change is the best to get b[bi] looking like a[ai].
                std::stringstream buf;
 
                // If b has more elements than a, then we assume this element
                // is an element that needs deleting.
                if(b.size() - bi > a.size() - ai) {
                    config& new_delete = res.add_child("delete_child");
                    buf << bi - ndeletes;
                    new_delete.values_["index"] = buf.str();
                    new_delete.add_child(entity);
 
                    ++ndeletes;
                    ++bi;
                }
 
                // If b has less elements than a, then we assume this element
                // is an element that needs inserting.
                else if(b.size() - bi < a.size() - ai) {
                    config& new_insert = res.add_child("insert_child");
                    buf << ai;
                    new_insert.values_["index"] = buf.str();
                    new_insert.add_child(entity, *a[ai]);
 
                    ++ai;
                }
 
                // Otherwise, they have the same number of elements,
                // so try just changing this element to match.
                else {
                    config& new_change = res.add_child("change_child");
                    buf << bi;
                    new_change.values_["index"] = buf.str();
                    new_change.add_child(entity, a[ai]->get_diff(*b[bi]));
 
                    ++ai;
                    ++bi;
                }
            }
        }
    }
}
 
void config::apply_diff(const config& diff, bool track /* = false */)
{
    if(track) {
        values_[diff_track_attribute] = "modified";
    }
 
    if(const auto inserts = diff.optional_child("insert")) {
        for(const auto& [key, value] : inserts->attribute_range()) {
            values_[key] = value;
        }
    }
 
    if(const auto deletes = diff.optional_child("delete")) {
        for(const attribute& v : deletes->attribute_range()) {
            values_.erase(v.first);
        }
    }
 
    for(const config& i : diff.child_range("change_child")) {
        const std::size_t index = i["index"].to_size_t();
        for(const auto [key, cfg] : i.all_children_view()) {
            if(key.empty()) {
                continue;
            }
 
            const child_map::iterator itor = children_.find(key);
            if(itor == children_.end() || index >= itor->second.size()) {
                throw error("error in diff: could not find element '" + key + "'");
            }
 
            itor->second[index]->apply_diff(cfg, track);
        }
    }
 
    for(const config& i : diff.child_range("insert_child")) {
        const std::size_t index = i["index"].to_size_t();
        for(const auto [key, cfg] : i.all_children_view()) {
            config& inserted = add_child_at(key, cfg, index);
            if(track) {
                inserted[diff_track_attribute] = "new";
            }
        }
    }
 
    for(const config& i : diff.child_range("delete_child")) {
        const std::size_t index = i["index"].to_size_t();
        for(const auto [key, cfg] : i.all_children_view()) {
            if(!track) {
                remove_child(key, index);
            } else {
                const child_map::iterator itor = children_.find(key);
                if(itor == children_.end() || index >= itor->second.size()) {
                    throw error("error in diff: could not find element '" + key + "'");
                }
 
                itor->second[index]->values_[diff_track_attribute] = "deleted";
            }
        }
    }
}
 
void config::clear_diff_track(const config& diff)
{
    remove_attribute(diff_track_attribute);
    for(const config& i : diff.child_range("delete_child")) {
        const std::size_t index = i["index"].to_size_t();
        for(const auto [key, cfg] : i.all_children_view()) {
            remove_child(key, index);
        }
    }
 
    for(const config& i : diff.child_range("change_child")) {
        const std::size_t index = i["index"].to_size_t();
        for(const auto [key, cfg] : i.all_children_view()) {
            if(key.empty()) {
                continue;
            }
 
            const child_map::iterator itor = children_.find(key);
            if(itor == children_.end() || index >= itor->second.size()) {
                throw error("error in diff: could not find element '" + key + "'");
            }
 
            itor->second[index]->clear_diff_track(cfg);
        }
    }
 
    for(std::pair<const std::string, child_list>& p : children_) {
        for(auto& cfg : p.second) {
            cfg->remove_attribute(diff_track_attribute);
        }
    }
}
 
/**
 * Merge config 'c' into this config, overwriting this config's values.
 */
void config::merge_with(const config& c)
{
    std::vector<child_pos> to_remove;
    std::map<std::string, unsigned> visitations;
 
    // Merge attributes first
    merge_attributes(c);
 
    // Now merge shared tags
    all_children_iterator::Itor i, i_end = ordered_children_.end();
    for(i = ordered_children_.begin(); i != i_end; ++i) {
        const std::string& tag = i->pos->first;
        const child_map::const_iterator j = c.children_.find(tag);
 
        if(j != c.children_.end()) {
            unsigned& visits = visitations[tag];
 
            if(visits < j->second.size()) {
                // Get a const config so we do not add attributes.
                const config& merge_child = *j->second[visits++];
 
                if(merge_child["__remove"].to_bool()) {
                    to_remove.push_back(*i);
                } else {
                    (i->pos->second[i->index])->merge_with(merge_child);
                }
            }
        }
    }
 
    // Now add any unvisited tags
    for(const auto& [tag, list] : c.children_) {
        unsigned& visits = visitations[tag];
        while(visits < list.size()) {
            add_child(tag, *list[visits++]);
        }
    }
 
    // Remove those marked so
    std::map<std::string, std::size_t> removals;
    for(const child_pos& pos : to_remove) {
        const std::string& tag = pos.pos->first;
        auto& removes = removals[tag];
        remove_child(tag, pos.index - removes++);
    }
}
 
/**
 * Merge config 'c' into this config, preserving this config's values.
 */
void config::inherit_from(const config& c)
{
    // Using a scratch config and merge_with() seems to execute about as fast
    // as direct coding of this merge.
    config scratch(c);
    scratch.merge_with(*this);
    swap(scratch);
}
 
/**
 * Merge the attributes of config 'c' into this config, preserving this config's values.
 */
void config::inherit_attributes(const config& cfg)
{
    for(const auto& [key, value] : cfg.values_) {
        attribute_value& v2 = values_[key];
        if(v2.blank()) {
            v2 = value;
        }
    }
}
bool config::matches(const config& filter) const
{
    bool result = true;
 
    for(const auto& [key, value] : filter.attribute_range()) {
        if(key.compare(0, 8, "glob_on_") == 0) {
            const attribute_value* v = get(key.substr(8));
            if(!v || !utils::wildcard_string_match(v->str(), value.str())) {
                result = false;
                break;
            }
        } else {
            const attribute_value* v = get(key);
            if(!v || *v != value) {
                result = false;
                break;
            }
        }
    }
 
    for(const auto [key, cfg] : filter.all_children_view()) {
        if(key == "not") {
            result = result && !matches(cfg);
            continue;
        } else if(key == "and") {
            result = result && matches(cfg);
            continue;
        } else if(key == "or") {
            result = result || matches(cfg);
            continue;
        }
 
        bool found = false;
        for(const config& j : child_range(key)) {
            if(j.matches(cfg)) {
                found = true;
                break;
            }
        }
 
        result = result && found;
    }
 
    return result;
}
 
std::string config::debug() const
{
    std::ostringstream outstream;
    outstream << *this;
    return outstream.str();
}
 
std::ostream& operator<<(std::ostream& outstream, const config& cfg)
{
    io::write(outstream, cfg);
    return outstream;
}
 
std::string config::hash() const
{
    static const unsigned int hash_length = 128;
    static const char hash_string[] = "+-,.<>0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    char hash_str[hash_length + 1];
 
    unsigned int i;
    for(i = 0; i != hash_length; ++i) {
        hash_str[i] = 'a';
    }
 
    hash_str[hash_length] = 0;
 
    i = 0;
    for(const auto& [key, value] : values_) {
        if(value.blank()) {
            continue;
        }
 
        for(char c : key) {
            hash_str[i] ^= c;
            if(++i == hash_length) {
                i = 0;
            }
        }
 
        std::string base_str = value.t_str().base_str();
        for(const char c : base_str) {
            hash_str[i] ^= c;
            if(++i == hash_length) {
                i = 0;
            }
        }
    }
 
    for(const auto [key, cfg] : all_children_view()) {
        std::string child_hash = cfg.hash();
        for(char c : child_hash) {
            hash_str[i] ^= c;
            ++i;
            if(i == hash_length) {
                i = 0;
            }
        }
    }
 
    for(i = 0; i != hash_length; ++i) {
        hash_str[i] = hash_string[static_cast<unsigned>(hash_str[i]) % strlen(hash_string)];
    }
 
    return std::string(hash_str);
}
 
void config::swap(config& cfg) noexcept
{
    values_.swap(cfg.values_);
    children_.swap(cfg.children_);
    ordered_children_.swap(cfg.ordered_children_);
}
 
void swap(config& lhs, config& rhs) noexcept
{
    lhs.swap(rhs);
}
 
bool config::validate_wml() const
{
    return std::all_of(children_.begin(), children_.end(), [](const auto& pair)
    {
        return valid_tag(pair.first) &&
            std::all_of(pair.second.begin(), pair.second.end(),
            [](const auto& c) { return c->validate_wml(); });
    }) &&
        std::all_of(values_.begin(), values_.end(), [](const auto& pair)
    {
        return valid_attribute(pair.first);
    });
}
 
bool operator==(const config& a, const config& b)
{
    if(a.values_ != b.values_) {
        return false;
    }
 
    config::const_all_children_itors x = a.all_children_range(), y = b.all_children_range();
    for(; !x.empty() && !y.empty(); x.pop_front(), y.pop_front()) {
        if(x.front().key != y.front().key || x.front().cfg != y.front().cfg) {
            return false;
        }
    }
 
    return x.empty() && y.empty();
}