1 files changed, 490 insertions, 0 deletions
diff --git a/src/parser/xml_namespace.cpp b/src/parser/xml_namespace.cpp
new file mode 100644
index 0000000..2aafea3
--- /dev/null
+++ b/src/parser/xml_namespace.cpp
@@ -0,0 +1,490 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ */
+
+#include <orcus/xml_namespace.hpp>
+#include <orcus/exception.hpp>
+#include <orcus/string_pool.hpp>
+
+#include <unordered_map>
+#include <vector>
+#include <limits>
+#include <sstream>
+#include <algorithm>
+#include <cassert>
+
+#define ORCUS_DEBUG_XML_NAMESPACE 0
+
+using namespace std;
+
+#if ORCUS_DEBUG_XML_NAMESPACE
+#include <cstdio>
+#include <iostream>
+#endif
+
+namespace orcus {
+
+namespace {
+
+#if ORCUS_DEBUG_XML_NAMESPACE
+template<typename _MapType>
+void print_map_keys(const _MapType& map_store)
+{
+    cout << "keys: (";
+    bool first = true;
+    typename _MapType::const_iterator it = map_store.begin(), it_end = map_store.end();
+    for (; it != it_end; ++it)
+    {
+        if (first)
+            first = false;
+        else
+            cout << " ";
+        cout << "'" << it->first << "'";
+    }
+    cout << ")";
+};
+#endif
+
+}
+
+typedef std::unordered_map<std::string_view, std::size_t> strid_map_type;
+
+struct xmlns_repository::impl
+{
+    size_t m_predefined_ns_size;
+    string_pool m_pool; /// storage of live string instances.
+    std::vector<std::string_view> m_identifiers; /// map strings to numerical identifiers.
+    strid_map_type m_strid_map; /// string-to-numerical identifiers map for quick lookup.
+
+    impl() : m_predefined_ns_size(0) {}
+};
+
+xmlns_repository::xmlns_repository() : mp_impl(std::make_unique<impl>()) {}
+xmlns_repository::xmlns_repository(xmlns_repository&& other) : mp_impl(std::move(other.mp_impl)) {}
+xmlns_repository::~xmlns_repository() = default;
+
+xmlns_repository& xmlns_repository::operator= (xmlns_repository&& other)
+{
+    mp_impl = std::move(other.mp_impl);
+    return *this;
+}
+
+xmlns_id_t xmlns_repository::intern(std::string_view uri)
+{
+    // See if the uri is already registered.
+    strid_map_type::iterator it = mp_impl->m_strid_map.find(uri);
+    if (it != mp_impl->m_strid_map.end())
+        return it->first.data();
+
+    try
+    {
+        auto r = mp_impl->m_pool.intern(uri);
+        std::string_view uri_interned = r.first;
+
+        if (!uri_interned.empty())
+        {
+            // Intern successful.
+            if (r.second)
+            {
+                // This is a new instance. Assign a numerical identifier.
+                mp_impl->m_strid_map.insert(
+                    strid_map_type::value_type(r.first, mp_impl->m_identifiers.size()));
+#if ORCUS_DEBUG_XML_NAMESPACE
+                cout << "xmlns_repository::intern: uri='" << uri_interned << "' (" << mp_impl->m_identifiers.size() << ")" << endl;
+#endif
+                mp_impl->m_identifiers.push_back(r.first);
+
+#if ORCUS_DEBUG_XML_NAMESPACE
+                cout << "pool size=" << mp_impl->m_pool.size() << ", predefined ns size=" << mp_impl->m_predefined_ns_size <<
+                    ", identifiers size=" << mp_impl->m_identifiers.size() << ", map size=" << mp_impl->m_strid_map.size() << endl;
+#endif
+                assert(mp_impl->m_pool.size()+mp_impl->m_predefined_ns_size == mp_impl->m_identifiers.size());
+                assert(mp_impl->m_pool.size()+mp_impl->m_predefined_ns_size == mp_impl->m_strid_map.size());
+            }
+            return uri_interned.data();
+        }
+    }
+    catch (const general_error&)
+    {
+    }
+
+    return XMLNS_UNKNOWN_ID;
+}
+
+void xmlns_repository::add_predefined_values(const xmlns_id_t* predefined_ns)
+{
+    if (!predefined_ns)
+        return;
+
+    const xmlns_id_t* val = &predefined_ns[0];
+    for (; *val; ++val)
+    {
+        std::string_view s(*val);
+        mp_impl->m_strid_map.insert(
+            strid_map_type::value_type(s, mp_impl->m_identifiers.size()));
+        mp_impl->m_identifiers.push_back(s);
+
+        ++mp_impl->m_predefined_ns_size;
+
+#if ORCUS_DEBUG_XML_NAMESPACE
+        cout << "xlmns_repository: predefined ns='" << s << "'" << endl;
+#endif
+    }
+}
+
+xmlns_context xmlns_repository::create_context()
+{
+    return xmlns_context(*this);
+}
+
+xmlns_id_t xmlns_repository::get_identifier(size_t index) const
+{
+    if (index >= mp_impl->m_identifiers.size())
+        return XMLNS_UNKNOWN_ID;
+
+    // All identifier strings are interned which means they are all null-terminated.
+    return mp_impl->m_identifiers[index].data();
+}
+
+string xmlns_repository::get_short_name(xmlns_id_t ns_id) const
+{
+    size_t index = get_index(ns_id);
+
+    if (index == INDEX_NOT_FOUND)
+        return string("???");
+
+    std::ostringstream os;
+    os << "ns" << index;
+    return os.str();
+}
+
+size_t xmlns_repository::get_index(xmlns_id_t ns_id) const
+{
+    if (!ns_id)
+        return INDEX_NOT_FOUND;
+
+    auto it = mp_impl->m_strid_map.find(std::string_view(ns_id));
+    if (it == mp_impl->m_strid_map.end())
+        return INDEX_NOT_FOUND;
+
+    return it->second;
+}
+
+typedef std::vector<xmlns_id_t> xmlns_list_type;
+typedef std::unordered_map<std::string_view, xmlns_list_type> alias_map_type;
+
+struct xmlns_context::impl
+{
+    xmlns_repository* repo = nullptr;
+    xmlns_list_type m_all_ns; /// all namespaces ever used in this context.
+    xmlns_list_type m_default;
+    alias_map_type m_map;
+
+    bool m_trim_all_ns = true;
+
+    impl() {}
+    impl(xmlns_repository& _repo) : repo(&_repo) {}
+    impl(const impl& r) :
+        repo(r.repo), m_all_ns(r.m_all_ns), m_default(r.m_default), m_map(r.m_map), m_trim_all_ns(r.m_trim_all_ns) {}
+};
+
+xmlns_context::xmlns_context() : mp_impl(std::make_unique<impl>()) {}
+xmlns_context::xmlns_context(xmlns_repository& repo) : mp_impl(std::make_unique<impl>(repo)) {}
+xmlns_context::xmlns_context(const xmlns_context& r) : mp_impl(std::make_unique<impl>(*r.mp_impl)) {}
+xmlns_context::xmlns_context(xmlns_context&& r) : mp_impl(std::move(r.mp_impl))
+{
+    r.mp_impl = std::make_unique<impl>();
+}
+
+xmlns_context::~xmlns_context() = default;
+
+xmlns_context& xmlns_context::operator= (const xmlns_context& r)
+{
+    xmlns_context tmp(r);
+    tmp.swap(*this);
+    return *this;
+}
+
+xmlns_context& xmlns_context::operator= (xmlns_context&& r)
+{
+    xmlns_context tmp(std::move(r));
+    tmp.swap(*this);
+    return *this;
+}
+
+xmlns_id_t xmlns_context::push(std::string_view alias, std::string_view uri)
+{
+    if (!mp_impl->repo)
+        throw general_error("this context is not associated with any repo.");
+
+#if ORCUS_DEBUG_XML_NAMESPACE
+    cout << "xmlns_context::push: key='" << alias << "', uri='" << uri << "'" << endl;
+#endif
+    mp_impl->m_trim_all_ns = true;
+
+    xmlns_id_t id = mp_impl->repo->intern(uri);
+    std::string_view uri_interned = id ? std::string_view(id) : std::string_view();
+
+    if (alias.empty())
+    {
+        // empty alias value is associated with default namespace.
+        mp_impl->m_default.push_back(uri_interned.data());
+        mp_impl->m_all_ns.push_back(uri_interned.data());
+        return mp_impl->m_default.back();
+    }
+
+    // See if this alias already exists.
+    alias_map_type::iterator it = mp_impl->m_map.find(alias);
+    if (it == mp_impl->m_map.end())
+    {
+        // This is the first time this alias is used.
+        xmlns_list_type nslist;
+        nslist.push_back(uri_interned.data());
+        mp_impl->m_all_ns.push_back(uri_interned.data());
+        std::pair<alias_map_type::iterator,bool> r =
+            mp_impl->m_map.insert(alias_map_type::value_type(alias, nslist));
+
+        if (!r.second)
+            // insertion failed.
+            throw general_error("Failed to insert new namespace.");
+
+        return nslist.back();
+    }
+
+    // The alias already exists.
+    xmlns_list_type& nslist = it->second;
+    nslist.push_back(uri_interned.data());
+    mp_impl->m_all_ns.push_back(uri_interned.data());
+    return nslist.back();
+}
+
+void xmlns_context::pop(std::string_view alias)
+{
+#if ORCUS_DEBUG_XML_NAMESPACE
+    cout << "xmlns_context::pop: alias='" << alias << "'" << endl;
+#endif
+    if (alias.empty())
+    {
+        // empty alias value is associated with default namespace.
+        if (mp_impl->m_default.empty())
+            throw general_error("default namespace stack is empty.");
+
+        mp_impl->m_default.pop_back();
+        return;
+    }
+
+    // See if this alias really exists.
+    alias_map_type::iterator it = mp_impl->m_map.find(alias);
+    if (it == mp_impl->m_map.end())
+    {
+        std::ostringstream os;
+        os << "alias named '" << alias << "' was attempted to be popped, but was not found in the stack";
+        throw general_error(os.str());
+    }
+
+    xmlns_list_type& nslist = it->second;
+    if (nslist.empty())
+        throw general_error("namespace stack for this key is empty.");
+
+    nslist.pop_back();
+}
+
+xmlns_id_t xmlns_context::get(std::string_view alias) const
+{
+#if ORCUS_DEBUG_XML_NAMESPACE
+    cout << "xmlns_context::get: alias='" << alias << "', default ns stack size="
+        << mp_impl->m_default.size() << ", non-default alias count=" << mp_impl->m_map.size();
+    cout << ", ";
+    print_map_keys(mp_impl->m_map);
+    cout << endl;
+#endif
+    if (alias.empty())
+        return mp_impl->m_default.empty() ? XMLNS_UNKNOWN_ID : mp_impl->m_default.back();
+
+    alias_map_type::const_iterator it = mp_impl->m_map.find(alias);
+    if (it == mp_impl->m_map.end())
+    {
+#if ORCUS_DEBUG_XML_NAMESPACE
+        cout << "xmlns_context::get: alias not in this context" << endl;
+#endif
+        return XMLNS_UNKNOWN_ID;
+    }
+
+#if ORCUS_DEBUG_XML_NAMESPACE
+    cout << "xmlns_context::get: alias stack size=" << it->second.size() << endl;
+#endif
+    return it->second.empty() ? XMLNS_UNKNOWN_ID : it->second.back();
+}
+
+size_t xmlns_context::get_index(xmlns_id_t ns_id) const
+{
+    if (!mp_impl->repo)
+        throw general_error("this context is not associated with any repo.");
+
+    return mp_impl->repo->get_index(ns_id);
+}
+
+string xmlns_context::get_short_name(xmlns_id_t ns_id) const
+{
+    if (!mp_impl->repo)
+        throw general_error("this context is not associated with any repo.");
+
+    return mp_impl->repo->get_short_name(ns_id);
+}
+
+std::string_view xmlns_context::get_alias(xmlns_id_t ns_id) const
+{
+    alias_map_type::const_iterator it = mp_impl->m_map.begin(), it_end = mp_impl->m_map.end();
+    for (; it != it_end; ++it)
+    {
+        const xmlns_list_type& lst = it->second;
+        if (lst.empty())
+            continue;
+
+        if (lst.back() == ns_id)
+            return it->first;
+    }
+
+    return std::string_view{};
+}
+
+namespace {
+
+#if ORCUS_DEBUG_XML_NAMESPACE
+struct print_ns
+{
+    void operator() (xmlns_id_t ns_id) const
+    {
+        const char* p = ns_id;
+        printf("%p: %s\n", p, p);
+    }
+};
+#endif
+
+struct ns_item
+{
+    size_t index;
+    xmlns_id_t ns;
+
+    ns_item(size_t _index, xmlns_id_t _ns) : index(_index), ns(_ns) {}
+};
+
+struct less_ns_by_index
+{
+    bool operator() (const ns_item& left, const ns_item& right) const
+    {
+        return left.index < right.index;
+    }
+};
+
+class push_back_ns_to_item
+{
+    vector<ns_item>& m_store;
+    const xmlns_context& m_cxt;
+public:
+    push_back_ns_to_item(vector<ns_item>& store, const xmlns_context& cxt) : m_store(store), m_cxt(cxt) {}
+    void operator() (xmlns_id_t ns)
+    {
+        size_t num_id = m_cxt.get_index(ns);
+        if (num_id != INDEX_NOT_FOUND)
+            m_store.push_back(ns_item(num_id, ns));
+    }
+};
+
+class push_back_item_to_ns
+{
+    std::vector<xmlns_id_t>& m_store;
+public:
+    push_back_item_to_ns(std::vector<xmlns_id_t>& store) : m_store(store) {}
+    void operator() (const ns_item& item)
+    {
+        m_store.push_back(item.ns);
+    }
+};
+
+}
+
+std::vector<xmlns_id_t> xmlns_context::get_all_namespaces() const
+{
+#if ORCUS_DEBUG_XML_NAMESPACE
+    cout << "xmlns_context::get_all_namespaces: count=" << mp_impl->m_all_ns.size() << endl;
+    std::for_each(mp_impl->m_all_ns.begin(), mp_impl->m_all_ns.end(), print_ns());
+#endif
+
+    std::vector<xmlns_id_t> nslist;
+
+    if (mp_impl->m_trim_all_ns)
+    {
+        xmlns_list_type& all_ns = mp_impl->m_all_ns;
+
+        nslist.assign(mp_impl->m_all_ns.begin(), mp_impl->m_all_ns.end());
+
+        // Sort it and remove duplicate.
+        std::sort(all_ns.begin(), all_ns.end());
+        xmlns_list_type::iterator it_unique_end =
+            std::unique(all_ns.begin(), all_ns.end());
+        all_ns.erase(it_unique_end, all_ns.end());
+
+        // Now, sort by indices.
+        vector<ns_item> items;
+        std::for_each(all_ns.begin(), all_ns.end(), push_back_ns_to_item(items, *this));
+        std::sort(items.begin(), items.end(), less_ns_by_index());
+
+        all_ns.clear();
+        std::for_each(items.begin(), items.end(), push_back_item_to_ns(all_ns));
+
+        mp_impl->m_trim_all_ns = false;
+    }
+
+    nslist.assign(mp_impl->m_all_ns.begin(), mp_impl->m_all_ns.end());
+    return nslist;
+}
+
+void xmlns_context::dump(std::ostream& os) const
+{
+    vector<xmlns_id_t> nslist = get_all_namespaces();
+    vector<xmlns_id_t>::const_iterator it = nslist.begin(), it_end = nslist.end();
+    for (; it != it_end; ++it)
+    {
+        xmlns_id_t ns_id = *it;
+        size_t num_id = get_index(ns_id);
+        if (num_id == INDEX_NOT_FOUND)
+            continue;
+
+        os << "ns" << num_id << "=\"" << ns_id << '"' << endl;
+    }
+}
+
+void xmlns_context::dump_state(std::ostream& os) const
+{
+    os << "namespaces:" << std::endl;
+    for (xmlns_id_t ns_id : get_all_namespaces())
+    {
+        size_t num_id = get_index(ns_id);
+        if (num_id == INDEX_NOT_FOUND)
+            continue;
+
+        os << "  ns" << num_id << ": \"" << ns_id << '"' << std::endl;
+    }
+
+    os << "aliases:" << std::endl;
+    for (const auto& [alias, ns_list] : mp_impl->m_map)
+    {
+        os << "  " << alias << ":" << std::endl;
+
+        for (const xmlns_id_t ns : ns_list)
+            os << "    - " << ns << std::endl;
+    }
+}
+
+void xmlns_context::swap(xmlns_context& other) noexcept
+{
+    mp_impl.swap(other.mp_impl);
+}
+
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */