bool dehydrator::has_elements(const intermediate_model& im) const {
    return
        !im.objects().empty() ||
        !im.primitives().empty() ||
        !im.enumerations().empty() ||
        !im.modules().empty();
}

void dehydrator::
dehydrate_enumerations(const intermediate_model& im, std::ostream& s) const {
    using boost::algorithm::join;
    formatters::utility_formatter uf(s);
    bool output_comma(!im.objects().empty() || !im.concepts().empty() ||
        im.modules().empty());
    const auto enumerations(to_map(im.enumerations()));
    for (const auto& pair : enumerations) {
        if (output_comma)
            s << comma_space;

        const auto& o(pair.second);
        s << " { ";
        dehydrate_element(im, o, "enumeration", s);
        s << comma_space;

        /*
         * Remove invalid from enumerators.
         */
        std::vector<enumerator> enumerators;
        enumerators.reserve(o.enumerators().size());
        for (const auto& en : o.enumerators()) {
            if (en.name() != "invalid")
                enumerators.push_back(en);
        }

        uf.insert_quoted("enumerators");
        s << ": [";

        bool is_first(true);
        for(const auto& en : enumerators) {
            if (!is_first)
                s << comma_space;

            s << " { ";
            uf.insert_quoted("simple_name");
            s << " : ";
            uf.insert_quoted(en.name());

            if (!en.documentation().empty()) {
                s << comma_space;
                uf.insert_quoted("documentation");
                s << " : ";
                uf.insert_quoted(tidy_up_string(en.documentation()));
            }

            s << " }";
            is_first = false;
        }
        s << " ]";

        s << " }";
        output_comma = true;
    }
}

void generalization_expander::populate_properties_up_the_generalization_tree(
    const type_group& tg, const yarn::name& leaf,
    intermediate_model& im, yarn::object& o) const {

    /*
     * Add the leaf to all nodes of the tree except for the leaf node
     * itself.
     */
    if (!o.is_leaf())
        o.leaves().push_back(leaf);

    /*
     * If we do not have a parent we have reached the top of the
     * generalisation tree.
     */
    if (!o.parent()) {
        /*
         * If the leaf name belongs to the target model, add it to
         * the model's list of leaves. Ignore non-target leaves.
         */
        const auto& ll(leaf.location());
        const auto& ml(im.name().location());
        if (ll.model_modules() == ml.model_modules())
            im.leaves().insert(leaf);

        return;
    }

    const auto pid(o.parent()->id());
    auto j(im.objects().find(pid));
    if (j == im.objects().end()) {
        BOOST_LOG_SEV(lg, error) << parent_not_found << pid;
        BOOST_THROW_EXCEPTION(expansion_error(parent_not_found + pid));
    }

    auto& parent(j->second);
    populate_properties_up_the_generalization_tree(tg, leaf, im, parent);

    if (!parent.parent()) {
        /*
         * If our parent does not have a parent then it is our root
         * parent.
         */
        o.root_parent(parent.name());
    } else {
        /*
         * On all other cases, inherit the root parent properties for
         * our direct parent; these would have been populated from the
         * root parent as per above.
         */
        o.root_parent(parent.root_parent());
    }
}

void dehydrator::dehydrate_annotations(const intermediate_model& im,
    const std::string& id, std::ostream& s) const {

    formatters::utility_formatter uf(s);
    bool has_annotations(false);
    const auto& scribble_groups(im.indices().scribble_groups());
    const auto i(scribble_groups.find(id));
    if (i == scribble_groups.end())
        return;

    bool is_first(true);
    const auto scribble(i->second.parent());
    has_annotations = !scribble.entries().empty();
    if (!has_annotations)
        return;

    s << comma_space;
    uf.insert_quoted("annotation");
    s << " : {";

    for (const auto& entry : scribble.entries()) {
        if (!is_first)
            s << ", ";
        uf.insert_quoted(entry.first);
        s << " : ";
        uf.insert_quoted(entry.second);
        is_first = false;
    }
    s << " }";
}

std::unordered_set<std::string> generalization_expander::
update_and_collect_parent_ids(intermediate_model& im) const {
    BOOST_LOG_SEV(lg, debug) << "Updating and collecting parent ids.";

    resolver rs;
    std::unordered_set<std::string> r;
    for (auto& pair : im.objects()) {
        const auto& id(pair.first);
        BOOST_LOG_SEV(lg, debug) << "Processing type: " << id;

        auto& o(pair.second);
        if (!o.parent())
            continue;

        /*
         * Resolve the name of the parent. This is required because it
         * may have been supplied via meta-data, and as such, it may
         * not be complete. We can't wait for the resolution step
         * because there is a circular dependency (resolution needs
         * injection and injection needs generalization, which needs
         * resolution).
         */
        o.parent(rs.resolve(im, o.name(), *o.parent()));
        r.insert(o.parent()->id());
    }
    BOOST_LOG_SEV(lg, debug) << "Finished updating and collecting parent ids: "
                             << r;
    return r;
}

void dehydrator::
dehydrate_objects(const intermediate_model& im, std::ostream& s) const {

    using boost::algorithm::join;
    formatters::utility_formatter uf(s);
    bool is_first(true);

    const auto objects(to_map(im.objects()));
    for (const auto& pair : objects) {
        if (!is_first)
            s << comma_space;

        const auto& o(pair.second);
        s << " { ";
        dehydrate_element(im, o, "object", s);

        if (o.parent()) {
            s << comma_space;
            uf.insert_quoted("parent");
            s << " : ";
            dehydrate_name(*o.parent(), s);
        }

        if (!o.local_attributes().empty()) {
            s << comma_space;
            dehydrate_attributes(o.local_attributes(), s);
        }
        s << " }";
        is_first = false;
    }
}

void injector::inject_visitable_by(object& root, const std::list<name>& leaves,
    const name& visitor, intermediate_model& m) const {

    root.visitable_by().push_back(visitor);

    for (const auto& l : leaves) {
        auto i(m.objects().find(l.qualified()));
        if (i == m.objects().end()) {
            const auto qn(l.qualified());
            BOOST_LOG_SEV(lg, error) << leaf_not_found << qn;
            BOOST_THROW_EXCEPTION(injection_error(leaf_not_found + qn));
        }

        auto& leaf(i->second);
        leaf.visitable_by().push_back(visitor);
    }
}

void generalization_expander::
populate_generalizable_properties(const type_group& tg,
    const std::unordered_set<std::string>& parent_ids,
    intermediate_model& im) const {

    for (auto& pair : im.objects()) {
        const auto& id(pair.first);
        BOOST_LOG_SEV(lg, debug) << "Processing type: " << id;

        auto& o(pair.second);

        /*
         * We are a child if we have a parent (double-bang by design).
         */
         o.is_child(!!o.parent());

         /*
          * We are a parent if someone else declared us as their parent.
          */
         const auto i(parent_ids.find(id));
         o.is_parent(i != parent_ids.end());

         /*
          * Handle the case where the user decided to override final.
          */
         const auto is_final(make_is_final(tg, o.annotation()));
         if (is_final) {
             if (*is_final && o.is_parent()) {
                 BOOST_LOG_SEV(lg, error) << incompatible_is_final << id;
                 BOOST_THROW_EXCEPTION(
                     expansion_error(incompatible_is_final + id));
             }
             o.is_final(*is_final);
         } else {
             /*
              * By default we setup all childless types and leaf types
              * as final, unless the user tells us otherwise.
              */
             o.is_final(!o.is_parent());
         }

         /*
          * We are in an inheritance (generalisation) relationship if
          * we are either a parent or a child (or both).
          */
         o.in_inheritance_relationship(o.is_parent() || o.is_child());

         /*
          * We are a leaf if we are not a parent but we are a child.
          */
         o.is_leaf(!o.is_parent() && o.is_child());

         if (!o.is_leaf())
             continue;

         populate_properties_up_the_generalization_tree(tg, o.name(), im, o);
    }
}

std::string dehydrator::dehydrate(const intermediate_model& im) const {
    std::ostringstream s;
    formatters::utility_formatter uf(s);
    using boost::algorithm::join;

    const auto& l(im.name().location());
    s << "{ ";
    uf.insert_quoted("model_name");
    s << " : ";
    uf.insert_quoted(join(l.model_modules(), scope));
    s << comma_space;

    uf.insert_quoted("external_modules");
    s << " : ";
    uf.insert_quoted(join(l.external_modules(), scope));

    const auto i(im.modules().find(im.name().id()));
    if (i != im.modules().end()) {
        const auto& root_module(i->second);
        if (!root_module.documentation().empty()) {
            s << comma_space;
            uf.insert_quoted("documentation");
            s << " : ";
            uf.insert_quoted(tidy_up_string(root_module.documentation()));
        }
    }

    dehydrate_annotations(im, im.name().id(), s);

    if (has_elements(im)) {
        s << comma_space;
        uf.insert_quoted("elements");
        s << ": [";
        dehydrate_objects(im, s);
        dehydrate_concepts(im, s);
        dehydrate_modules(im, s);
        dehydrate_enumerations(im, s);
        dehydrate_exceptions(im, s);
        s << " ]";
    }

    s << " }";

    return s.str();
}

void generalization_indexer::
populate(const generalization_details& d, intermediate_model& m) const {
    for (const auto& pair : d.leaves) {
        const auto& n(pair.first);
        auto i(m.objects().find(n.qualified()));
        if (i == m.objects().end()) {
            const auto qn(n.qualified());
            BOOST_LOG_SEV(lg, error) << object_not_found << qn;
            BOOST_THROW_EXCEPTION(indexing_error(object_not_found + qn));
        }

        auto& o(i->second);
        o.leaves(pair.second);
        o.leaves().sort();

        for (const auto& leaf : pair.second) {
            if (leaf.location().model_modules() ==
                m.name().location().model_modules())
                m.leaves().insert(leaf);
        }
    }

    for (const auto& pair : d.root_parents) {
        const auto& n(pair.first);
        auto i(m.objects().find(n.qualified()));
        if (i == m.objects().end()) {
            const auto qn(n.qualified());
            BOOST_LOG_SEV(lg, error) << object_not_found << qn;
            BOOST_THROW_EXCEPTION(indexing_error(object_not_found + qn));
        }

        auto& o(i->second);
        if (!o.is_child()) {
            /* Top-level types have themselves as the original parent
             * of the container just to make our life easier, so we
             * have to ignore them here.
             */
            BOOST_LOG_SEV(lg, debug) << "Type has parents but is not a child: "
                                     << n.qualified();
            continue;
        }

        o.root_parents(pair.second);
        for (const auto& opn : pair.second) {
            const auto j(m.objects().find(opn.qualified()));
            if (j == m.objects().end()) {
                const auto qn(opn.qualified());
                BOOST_LOG_SEV(lg, error) << object_not_found << qn;
                BOOST_THROW_EXCEPTION(indexing_error(object_not_found + qn));
            }
            o.is_root_parent_visitable(j->second.is_visitable());
        }
    }
}

std::list<name> generalization_indexer::
recurse_generalization(const intermediate_model& m, const name& leaf,
    const object& o, generalization_details& d) const {

    if (!o.is_child())
        return std::list<name> { o.name() };

    if (o.parents().empty()) {
        const auto qn(o.name().qualified());
        BOOST_LOG_SEV(lg, error) << child_with_no_parents << qn;
        BOOST_THROW_EXCEPTION(indexing_error(child_with_no_parents + qn));
    }

    std::list<name> root_parents;
    for (const auto& parent : o.parents()) {
        auto j(m.objects().find(parent.qualified()));
        if (j == m.objects().end()) {
            const auto qn(parent.qualified());
            BOOST_LOG_SEV(lg, error) << parent_not_found << qn;
            BOOST_THROW_EXCEPTION(indexing_error(parent_not_found + qn));
        }

        const auto op(recurse_generalization(m, leaf, j->second, d));
        if (op.empty()) {
            const auto qn(parent.qualified());
            BOOST_LOG_SEV(lg, error) << child_with_no_root_parent << qn;
            BOOST_THROW_EXCEPTION(
                indexing_error(child_with_no_root_parent + qn));
        }

        for (const auto qn : op)
            root_parents.push_back(qn);

        d.root_parents[parent] = op;
        BOOST_LOG_SEV(lg, debug) << "Type: " << parent.qualified()
                                 << " has original parents: " << op;

        d.leaves[parent].push_back(leaf);
        BOOST_LOG_SEV(lg, debug) << "Type is a leaf of: " << parent.qualified();
    }
    d.root_parents[o.name()] = root_parents;
    return root_parents;
}

void dehydrator::
dehydrate_concepts(const intermediate_model& im, std::ostream& s) const {

    using boost::algorithm::join;
    formatters::utility_formatter uf(s);
    bool output_comma(!im.objects().empty());

    const auto concepts(to_map(im.concepts()));
    for (const auto& pair : concepts) {
        if (output_comma)
            s << comma_space;

        const auto& c(pair.second);
        s << " { ";
        dehydrate_element(im, c, "concept", s);

        if (!c.refines().empty()) {
            s << comma_space;
            uf.insert_quoted("refines");
            s << " : [ ";
            bool is_first(true);
            for (const auto& n : c.refines()) {
                if (!is_first)
                    s << comma_space;

                dehydrate_name(n, s);
                is_first = false;
            }
            s << " ] ";
        }

        if (!c.local_attributes().empty()) {
            s << comma_space;
            dehydrate_attributes(c.local_attributes(), s);
        }
        s << " }";
        output_comma = true;
    }
}

void injector::inject_visitors(intermediate_model& m) {
    BOOST_LOG_SEV(lg, debug) << "Injecting visitors.";

    std::list<visitor> visitors;
    for (auto& pair : m.objects()) {
        auto& o(pair.second);

        if (!o.is_visitable())
            continue;

        if (o.leaves().empty()) {
            const auto qn(o.name().qualified());
            BOOST_LOG_SEV(lg, error) << zero_leaves << qn;
            BOOST_THROW_EXCEPTION(injection_error(zero_leaves + qn));
        }

        const auto v(create_visitor(o, o.leaves()));
        inject_visitable_by(o, o.leaves(), v.name(), m);
        visitors.push_back(v);
    }

    for (const auto v : visitors) {
        BOOST_LOG_SEV(lg, debug) << "Adding visitor: "
                                 << v.name().qualified();

        const auto pair(std::make_pair(v.name().qualified(), v));
        const auto i(m.visitors().insert(pair));
        if (!i.second) {
            const auto qn(v.name().qualified());
            BOOST_LOG_SEV(lg, error) << duplicate_name << qn;
            BOOST_THROW_EXCEPTION(injection_error(duplicate_name + qn));
        }
    }

    BOOST_LOG_SEV(lg, debug) << "Done injecting visitors.";
}

void dehydrator::
dehydrate_modules(const intermediate_model& im, std::ostream& s) const {
    /*
     * Remove the root module.
     */
    auto modules(to_map(im.modules()));
    const auto i(modules.find(im.name().id()));
    if (i != modules.end())
        modules.erase(i);

    using boost::algorithm::join;
    formatters::utility_formatter uf(s);
    bool output_comma(!im.objects().empty() || !im.concepts().empty());
    for (const auto& pair : modules) {
        if (output_comma)
            s << comma_space;

        const auto& o(pair.second);
        s << " { ";
        dehydrate_element(im, o, "module", s);
        s << " }";
        output_comma = true;
    }
}

generalization_indexer::generalization_details generalization_indexer::
obtain_details(const intermediate_model& m) const {
    BOOST_LOG_SEV(lg, debug) << "Obtaining leaves.";
    generalization_details r;
    for (auto& pair : m.objects()) {
        auto& o(pair.second);
        BOOST_LOG_SEV(lg, debug) << "Processing type: "
                                 << o.name().qualified();

        if (!is_leaf(o))
            continue;

        recurse_generalization(m, o.name(), o, r);
    }

    BOOST_LOG_SEV(lg, debug) << "Leaves: " << r.leaves;
    BOOST_LOG_SEV(lg, debug) << "Original parents: " << r.root_parents;
    BOOST_LOG_SEV(lg, debug) << "Finished obtaining details.";
    return r;
}

inline void elements_traversal(intermediate_model& m, TraversalVisitor& v) {
    for (auto& pair : m.modules())
        v(pair.second);

    for (auto& pair : m.concepts())
        v(pair.second);

    for (auto& pair : m.primitives())
        v(pair.second);

    for (auto& pair : m.enumerations())
        v(pair.second);

    for (auto& pair : m.objects())
        v(pair.second);

    for (auto& pair : m.exceptions())
        v(pair.second);

    for (auto& pair : m.visitors())
        v(pair.second);
}

void dehydrator::
dehydrate_exceptions(const intermediate_model& im, std::ostream& s) const {
    using boost::algorithm::join;
    formatters::utility_formatter uf(s);

    bool output_comma(!im.objects().empty() || !im.concepts().empty() ||
        im.modules().empty() || im.modules().empty() ||
        im.enumerations().empty());
    const auto exceptions(to_map(im.exceptions()));
    for (const auto& pair : exceptions) {
        if (output_comma)
            s << comma_space;

        const auto& o(pair.second);
        s << " { ";
        dehydrate_element(im, o, "exception", s);
        s << " }";
        output_comma = true;
    }
}

std::size_t intermediate_model_hasher::hash(const intermediate_model& v) {
    std::size_t seed(0);

    combine(seed, v.name());
    combine(seed, v.origin_type());
    combine(seed, v.original_model_name());
    combine(seed, v.generation_type());
    combine(seed, hash_std_unordered_map_dogen_yarn_name_dogen_yarn_origin_types(v.references()));
    combine(seed, hash_std_unordered_set_dogen_yarn_name(v.leaves()));
    combine(seed, hash_std_unordered_map_std_string_dogen_yarn_module(v.modules()));
    combine(seed, hash_std_unordered_map_std_string_dogen_yarn_concept(v.concepts()));
    combine(seed, hash_std_unordered_map_std_string_dogen_yarn_primitive(v.primitives()));
    combine(seed, hash_std_unordered_map_std_string_dogen_yarn_enumeration(v.enumerations()));
    combine(seed, hash_std_unordered_map_std_string_dogen_yarn_object(v.objects()));
    combine(seed, hash_std_unordered_map_std_string_dogen_yarn_exception(v.exceptions()));
    combine(seed, hash_std_unordered_map_std_string_dogen_yarn_visitor(v.visitors()));
    combine(seed, v.is_target());
    combine(seed, v.has_generatable_types());

    return seed;
}

void injector::inject_global_module(intermediate_model& m) {
    const auto gm(create_global_module());

    const auto gmn(gm.name());
    const auto i(m.modules().find(gmn.qualified()));
    if (i != m.modules().end()) {
        const auto qn(m.name().qualified());
        BOOST_LOG_SEV(lg, error) << model_already_has_global_module << qn;
        BOOST_THROW_EXCEPTION(injection_error(
                model_already_has_global_module + qn));
    }
    m.modules().insert(std::make_pair(gmn.qualified(), gm));

    add_containing_module_to_non_contained_entities(gmn, m.modules());
    add_containing_module_to_non_contained_entities(gmn, m.concepts());
    add_containing_module_to_non_contained_entities(gmn, m.primitives());
    add_containing_module_to_non_contained_entities(gmn, m.enumerations());
    add_containing_module_to_non_contained_entities(gmn, m.objects());
    add_containing_module_to_non_contained_entities(gmn, m.exceptions());
    add_containing_module_to_non_contained_entities(gmn, m.visitors());
}

void generalization_expander::sort_leaves(intermediate_model& im) const {
    for (auto& pair : im.objects()) {
        auto& o(pair.second);
        o.leaves().sort();
    }
}