Layout tree addressing system

Description

This MR adds an addressing system to the layout tree. I am not satisfied with the result, so I will step back come back to it later. The key ideas are:

• An address object can be constructed from a node with address(node) or from numbers with address<vfat> { numbers... }.
• The node at an address can be retrieved with root % address (actual operator subject to change, maybe /).

This branch will probably be edited several times before merging.

Related Issue

Will close #44 (closed).

How Has This Been Tested?

Bundled tests and visual inspection of the documentation.

Types of changes

• Bug fix (non-breaking change which fixes an issue)
• New feature (non-breaking change which adds functionality)
• Breaking change (fix or feature that would cause existing functionality to change)

Checklist:

• My code follows the code style of this project.
• My change requires a change to the documentation.
• I have updated the documentation accordingly.
• I have read the CONTRIBUTING document.
• I have added tests to cover my changes.
• All new and existing tests passed.

gemcore/layout-tree/interface/addressing.h

+#ifndef GEM_CORE_LAYOUT_TREE_ADDRESSING_H
+#define GEM_CORE_LAYOUT_TREE_ADDRESSING_H
+
+/// @file
+/// @brief Defines the addressing subsystem
+
+#include <ostream>
+#include <sstream>
+#include <stdexcept>
+
+#include "gem/core/layout-tree/child_of.h"
+#include "gem/core/layout-tree/parent_mixin.h"
+
+namespace gem::core::layout_tree {
+
+/// @brief Address of a node in the hardware layout tree
+/// @headerfile addressing.h "gem/core/layout-tree/addressing.h"
+///
+/// Every node in the layout tree has a unique address defined by the types of
+/// its parent nodes and, in case they have
+/// @ref multiple_child_of "non-zero multiplicity", their
+/// @ref multiple_child_of.number "number". The address has nothing to do with
+/// pointers and can be used even if there is no corresponding node in the tree.
+/// The address of a node is obtained by constructing an object of this class:
+///
+/// ~~~{.cpp}
+/// some_node* node = ...;
+/// auto addr = address(node);
+/// ~~~
+///
+/// The address of a child contains the address of its parent, and can be
+/// converted using:
+///
+/// ~~~{.cpp}
+/// auto parent_addr = address<parent_node>(addr);
+/// ~~~
+///
+/// This conversion is implicit in places where the address of a parent node is
+/// required (eg function calls).
+///
+/// An address is made of several numerical components, one for each ancestor
+/// class with greater-than-one multiplicity. Every component corresponds to a
+/// level in the tree with a node number. They are retrieved using the
+/// component() function.
+/// For instance, with a simple `root›A›B›C` tree implemented using `a_node`,
+/// `b_node` and `c_node`, one can do:
+///
+/// ~~~{.cpp}
+/// c_node* c = ...;
+/// auto addr = address(c);
+/// auto a_number = addr.component<a_node>(); // c->parent()->parent()->number()
+/// auto b_number = addr.component<b_node>(); // c->parent()->number()
+/// auto c_number = addr.component<c_node>(); // c->number()
+/// ~~~
+///
+/// For convenience, the address component of a node class with zero
+/// multiplicity (ie that doesn't inherit from @ref multiple_child_of) is always
+/// zero. The root node doesn't have an address component.
+///
+/// Addresses can be created from scratch using initializer lists:
+///
+/// ~~~{.cpp}
+/// address<a_node> { 0 }
+/// address<b_node> { 0, 1 }
+/// address<c_node> { 0, 1, 2 }
+/// ~~~
+///
+/// This conversion is implicit in places where an address is required (eg
+/// function calls). It is also possible to use an `std::array` of the
+/// appropriate dimension.
+///
+/// Note that addresses created this way aren't guaranteed to point to a valid
+/// object, or even to make sense: no validation is performed.
+///
+/// A reference to the node pointed to by an address can be retrieved by
+/// combining it with the root node of a tree:
+///
+/// ~~~{.cpp}
+/// auto& node = root % address;
+/// ~~~
+///
+/// An exception is thrown if no matching node is found. Using a reference (`&`
+/// symbol) is often mandatory because most node classes cannot be copied. Note
+/// that lookup by address isn't optimized for speed; prefer
+/// @ref parent_mixin.children "iterators" when targeting more than a handful of
+/// nodes.
+///
+///
+/// @tparam T a node class
+#if IS_DOXYGEN
+template <class T>
+#else
+template <
+    class T,
+    class U = typename T::parent_type,
+    bool V = std::is_base_of_v<multiple_child_of<typename T::parent_type>, T>>
+#endif
+class address : public address<typename T::parent_type> {
+public:
+    /// @brief The type of the class pointed to by this address
+    using addressed_type = T;
+
+    /// @brief The type of the address of the parent node
+    using parent_address_type = address<typename T::parent_type>;
+
+    /// @brief The number of components of this address type
+    inline constexpr static std::size_t component_count = parent_address_type::component_count;
+
+    /// @brief Constructs an address from a sequence of integers
+    address(const std::array<std::size_t, component_count>& components) noexcept
+    {
+        init_from_array(components);
+    }
+
+    /// @brief Constructs an address from a sequence of integers
+    address(const std::initializer_list<std::size_t>& components)
+    {
+        if (components.size() < component_count) {
+            std::stringstream ss;
+            ss << "Not enough components for address to "
+               << addressed_type::node_name
+               << " (got "
+               << std::to_string(components.size())
+               << ", expected "
+               << component_count
+               << ")";
+            throw std::invalid_argument(ss.str());
+        } else if (components.size() > component_count) {
+            std::stringstream ss;
+            ss << "Too many components for address to "
+               << addressed_type::node_name
+               << " (got "
+               << std::to_string(components.size())
+               << ", expected "
+               << component_count
+               << ")";
+            throw std::invalid_argument(ss.str());
+        }
+
+        std::array<std::size_t, component_count> tmp {};
+        auto it = components.begin();
+        for (std::size_t i = 0; i < component_count; ++i) {
+            tmp[i] = *it++;
+        }
+        init_from_array(tmp);
+    }
+
+    /// @brief Retrieves the address of a node
+    explicit address(const addressed_type* node) noexcept
+        : parent_address_type(node->parent())
+    {
+    }
+
+    /// @brief Retrieves the address of a node
+    ///
+    /// This overload can be used to get the address of a parent without the
+    /// need for an explicit conversion:
+    ///
+    /// ~~~{.cpp}
+    /// address<parent_node>(child)
+    /// ~~~
+    template <class W>
+    explicit address(const W* node) noexcept
+        : address(address<W>(node))
+    {
+    }
+
+    /// @brief Retrieves an address component
+    template <class W>
+    std::size_t component() const noexcept
+    {
+        if constexpr (std::is_same_v<W, addressed_type>) {
+            return 0;
+        } else {
+            return parent_address_type::template component<W>();
+        }
+    }
+
+    /// @brief Compares for equality
+    bool operator==(const address<addressed_type>& other) const noexcept
+    {
+        return parent_address_type::operator==(other);
+    }
+
+    /// @brief Compares for difference
+    bool operator!=(const address<addressed_type>& other) const noexcept
+    {
+        return !(*this == other);
+    }
+
+protected:
+    /// @brief Default constructor used internally
+    address() noexcept = default;
+
+    /// @brief Initializes by picking the correct components from an array
+    template <std::size_t L>
+    void init_from_array(const std::array<std::size_t, L>& array) noexcept
+    {
+        static_assert(L >= component_count);
+        parent_address_type::init_from_array(array);
+    }
+};
+
+/// @brief Address of a node in the hardware layout tree
+/// @headerfile addressing.h "gem/core/layout-tree/addressing.h"
+///
+/// Specialization of @ref address for nodes that inherit
+/// @ref multiple_child_of.
+///
+/// @see address
+#if IS_DOXYGEN
+template <class T>
+        class address < T extends multiple_child_of <
+    ? >>
+#else
+template <class T>
+class address<T, typename T::parent_type, true>
+#endif
+    : public address<typename T::parent_type> {
+public:
+    /// @copydoc address::addressed_type
+    using addressed_type = T;
+
+    /// @copydoc address::parent_address_type
+    using parent_address_type = address<typename T::parent_type>;
+
+    /// @copydoc address::component_count
+    inline constexpr static std::size_t component_count = parent_address_type::component_count + 1;
+
+    /// @copydoc address::address(const std::array<std::size_t, component_count>&)
+    address(const std::array<std::size_t, component_count>& components) noexcept
+    {
+        init_from_array(components);
+    }
+
+    /// @copydoc address::address(const std::initializer_list<std::size_t>&)
+    address(const std::initializer_list<std::size_t>& components)
+    {
+        if (components.size() < component_count) {
+            std::stringstream ss;
+            ss << "Not enough components for address to "
+               << addressed_type::node_name
+               << " (got "
+               << std::to_string(components.size())
+               << ", expected "
+               << component_count
+               << ")";
+            throw std::invalid_argument(ss.str());
+        } else if (components.size() > component_count) {
+            std::stringstream ss;
+            ss << "Too many components for address to "
+               << addressed_type::node_name
+               << " (got "
+               << std::to_string(components.size())
+               << ", expected "
+               << component_count
+               << ")";
+            throw std::invalid_argument(ss.str());
+        }
+
+        std::array<std::size_t, component_count> tmp {};
+        auto it = components.begin();
+        for (std::size_t i = 0; i < component_count; ++i) {
+            tmp[i] = *it++;
+        }
+        init_from_array(tmp);
+    }
+
+    /// @copydoc address::address
+    explicit address(const addressed_type* node) noexcept
+        : parent_address_type(node->parent())
+        , m_component(node->number())
+    {
+    }
+
+    /// @copydoc address::address(const W*)
+    template <class W>
+    explicit address(const W* node) noexcept
+        : address(address<W>(node))
+    {
+    }
+
+    /// @copydoc address::component
+    template <class W>
+    std::size_t component() const noexcept
+    {
+        if constexpr (std::is_same_v<W, addressed_type>) {
+            return last_component();
+        } else {
+            return parent_address_type::template component<W>();
+        }
+    }
+
+    /// @brief Retrieves the last component of an address.
+    std::size_t last_component() const noexcept { return m_component; }
+
+    /// @copydoc address::operator==
+    bool operator==(const address<addressed_type>& other) const noexcept
+    {
+        return m_component == other.m_component
+            && parent_address_type::operator==(other);
+    }
+
+    /// @copydoc address::operator!=
+    bool operator!=(const address<addressed_type>& other) const noexcept
+    {
+        return !(*this == other);
+    }
+
+protected:
+    /// @copydoc address::address
+    address() noexcept = default;
+
+    /// @copydoc address::init_from_array
+    template <std::size_t L>
+    void init_from_array(const std::array<std::size_t, L>& array) noexcept
+    {
+        static_assert(L >= component_count);
+        m_component = array[component_count - 1];
+        parent_address_type::init_from_array(array);
+    }
+
+private:
+    std::size_t m_component;
+};
+
+/// @brief Address of a node in the hardware layout tree
+/// @headerfile addressing.h "gem/core/layout-tree/addressing.h"
+///
+/// Specialization of @ref address for @ref root_node "root nodes". The address
+/// of a root node has no components.
+///
+/// @see address
+#if IS_DOXYGEN
+template <class T>
+class address<T extends root_node>
+#else
+template <class T>
+class address<T, void, false>
+#endif
+{
+public:
+    /// @copydoc address::addressed_type
+    using addressed_type = T;
+
+    /// @copydoc address::parent_address_type
+    using parent_address_type = void;
+
+    /// @brief The root type of the node tree
+    using root_type = addressed_type;
+
+    /// @copydoc address::component_count
+    inline constexpr static std::size_t component_count = 0;
+
+    /// @brief Default constructor
+    address() noexcept = default;
+
+    /// @copydoc address::address(const std::array<std::size_t, component_count>&)
+    address(const std::array<std::size_t, component_count>&) noexcept
+    {
+    }
+
+    /// @copydoc address::address(const std::initializer_list<std::size_t>&)
+    address(const std::initializer_list<std::size_t>& components)
+    {
+        if (components.size() > 0) {
+            std::stringstream ss;
+            ss << "Too many components for address to "
+               << addressed_type::node_name
+               << " (got "
+               << std::to_string(components.size())
+               << ", expected 0)";
+            throw std::invalid_argument(ss.str());
+        }
+    }
+
+    /// @copydoc address::address(const addressed_type*)
+    explicit address(const addressed_type*) noexcept
+    {
+    }
+
+    /// @copydoc address::address(const W*)
+    template <class W>
+    explicit address(const W* node) noexcept
+        : address(address<W>(node))
+    {
+    }
+
+    /// @copydoc address::operator==
+    bool operator==(const address<addressed_type>& other) const noexcept
+    {
+        return true;
+    }
+
+    /// @copydoc address::operator!=
+    bool operator!=(const address<addressed_type>& other) const noexcept
+    {
+        return false;
+    }
+
+protected:
+    /// @copydoc address::init_from_array
+    template <std::size_t L>
+    void init_from_array(const std::array<std::size_t, L>&) noexcept
+    {
+    }
+};
+
+/// @brief Template deduction guide
+/// @relates address
+template <class T>
+address(const T*)->address<T>;
+
+#if IS_DOXYGEN
+/// @brief Writes an address to a stream
+/// @relates address
+///
+/// This function requires the presence of the @c node_name attribute.
+template <class T>
+std::ostream& operator<<(std::ostream& out, const address<T>& addr);
+#else
+
+template <class T>
+std::ostream& operator<<(std::ostream& out, const address<T, void>& addr)
+{
+    return out << T::node_name;
+}
+
+template <class T>
+std::ostream& operator<<(std::ostream& out, const address<T>& addr)
+{
+    return out << typename address<T>::parent_address_type(addr)
+               << "::"
+               << T::node_name;
+}
+
+template <class T>
+std::ostream& operator<<(std::ostream& out,
+    const address<T, typename T::parent_type, true>& addr)
+{
+    return out << typename address<T>::parent_address_type(addr)
+               << "::"
+               << T::node_name
+               << "["
+               << addr.last_component()
+               << "]";
+}
+#endif // IS_DOXYGEN
+
+/// @brief Retrieves the node at a given address in a tree, if any
+/// @relates address
+/// @throw std::invalid_argument if there is no node at the given address
+template <class T>
+auto& operator%(
+    const typename address<T>::root_type* root, const address<T>& addr)
+{
+    if constexpr (is_root_node<T>) {
+        return *root;
+    } else if constexpr (
+        std::is_base_of_v<multiple_child_of<typename T::parent_type>, T>) {
+        auto& parent = root % address<typename T::parent_type>(addr);
+        for (auto& child : parent.children() | filter_nodes<T>) {
+            if (child.number() == addr.last_component()) {
+                return child;
+            }
+        }
+    } else {
+        auto& parent = root % address<typename T::parent_type>(addr);
+        for (auto& child : parent.children() | filter_nodes<T>) {
+            return child;
+        }
+    }
+    std::stringstream ss;
+    ss << "No node at address " << addr;
+    throw std::invalid_argument(ss.str());
+}
+
+/// @copydoc operator%(const typename address<T>::root_type*, const address<T>&)
+template <class T>
+auto& operator%(
+    const std::unique_ptr<typename address<T>::root_type>& root,
+    const address<T>& addr)
+{
+    return root.get() % addr;
+}
+
+} // namespace gem::core::layout_tree
+
+#endif // GEM_CORE_LAYOUT_TREE_ADDRESSING_H