GenericMap.h

Go to the documentation of this file.

// -*- LSST-C++ -*-
/*
 * This file is part of afw.
 *
 * Developed for the LSST Data Management System.
 * This product includes software developed by the LSST Project
 * (https://www.lsst.org).
 * See the COPYRIGHT file at the top-level directory of this distribution
 * for details of code ownership.
 *
 * 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 3 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; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

#ifndef LSST_AFW_TYPEHANDLING_GENERICMAP_H
#define LSST_AFW_TYPEHANDLING_GENERICMAP_H

#include <algorithm>
#include <cstdint>
#include <functional>
#include <ostream>
#include <memory>
#include <sstream>
#include <typeinfo>
#include <type_traits>
#include <unordered_set>
#include <vector>

#include "boost/core/demangle.hpp"
#include "boost/variant.hpp"

#include "lsst/pex/exceptions.h"
#include "lsst/afw/typehandling/Storable.h"
#include "lsst/afw/typehandling/PolymorphicValue.h"

namespace lsst {
namespace afw {
namespace typehandling {

template <typename K, typename V>
class Key final {
public:
    using KeyType = K;
    using ValueType = V;

    constexpr Key(K id) : id(id) {}

    Key(Key const&) = default;
    Key(Key&&) = default;
    Key& operator=(Key const&) = delete;
    Key& operator=(Key&&) = delete;

    constexpr K const& getId() const noexcept { return id; }

    constexpr bool operator==(Key<K, V> const& other) const noexcept { return this->id == other.id; }

    template <typename U>
    constexpr std::enable_if_t<!std::is_same<U, V>::value, bool> operator==(Key<K, U> const&) const noexcept {
        return false;
    }

    template <typename U>
    constexpr bool operator!=(Key<K, U> const& other) const noexcept {
        return !(*this == other);
    }

    template <typename U>
    constexpr bool operator<(Key<K, U> const& other) const noexcept {
        const std::less<K> comparator;
        return comparator(this->getId(), other.getId());
    }

    std::size_t hash_value() const noexcept { return std::hash<K>()(id); }

private:
    K const id;
};

// template parameters must be reversed for inference to work correctly
template <typename V, typename K>
constexpr Key<K, V> makeKey(K const& id) {
    return Key<K, V>(id);
}

template <typename K, typename V>
std::ostream& operator<<(std::ostream& os, Key<K, V> const& key) {
    static const std::string typeStr = boost::core::demangle(typeid(V).name());
    static const std::string constStr = std::is_const<V>::value ? " const" : "";
    static const std::string volatileStr = std::is_volatile<V>::value ? " volatile" : "";
    os << key.getId() << "<" << typeStr << constStr << volatileStr << ">";
    return os;
}

// Test for smart pointers as "any type with an element_type member"
// Second template parameter is a dummy to let us do some metaprogramming
template <typename, typename = void>
constexpr bool IS_SMART_PTR = false;
template <typename T>
constexpr bool IS_SMART_PTR<T, std::enable_if_t<std::is_object<typename T::element_type>::value>> = true;

// TODO: const keys should be possible in C++17 with std::variant
template <typename K>
class GenericMap {
public:
    using key_type = K;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;

    virtual ~GenericMap() noexcept = default;

    template <typename T, typename std::enable_if_t<!IS_SMART_PTR<T>, int> = 0>
    T& at(Key<K, T> const& key) {
        // Both casts are safe; see Effective C++, Item 3
        return const_cast<T&>(static_cast<const GenericMap&>(*this).at(key));
    }

    template <typename T, typename std::enable_if_t<!IS_SMART_PTR<T>, int> = 0>
    T const& at(Key<K, T> const& key) const {
        // Delegate to private methods to hide further special-casing of T
        return _at(key);
    }

    template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
    std::shared_ptr<T> at(Key<K, std::shared_ptr<T>> const& key) const {
        // Delegate to private methods to hide further special-casing of T
        return _at(key);
    }

    virtual size_type size() const noexcept = 0;

    virtual bool empty() const noexcept = 0;

    virtual size_type max_size() const noexcept = 0;

    template <typename T>
    size_type count(Key<K, T> const& key) const {
        return contains(key) ? 1 : 0;
    }

    virtual bool contains(K const& key) const = 0;

    template <typename T>
    bool contains(Key<K, T> const& key) const {
        // Delegate to private methods to hide special-casing of T
        return _contains(key);
    }

    virtual std::vector<K> const& keys() const noexcept = 0;

    virtual bool operator==(GenericMap const& other) const noexcept {
        auto keys1 = this->keys();
        auto keys2 = other.keys();
        if (!std::is_permutation(keys1.begin(), keys1.end(), keys2.begin(), keys2.end())) {
            return false;
        }
        for (K const& key : keys1) {
            if (this->unsafeLookup(key) != other.unsafeLookup(key)) {
                return false;
            }
        }
        return true;
    }

    bool operator!=(GenericMap const& other) const { return !(*this == other); }

    template <class Visitor>
    auto apply(Visitor&& visitor) const {
        // Delegate to private methods to hide special-casing of Visitor
        return _apply(visitor);
    }

    template <class Visitor>
    auto apply(Visitor&& visitor) {
        // Delegate to private methods to hide special-casing of Visitor
        return _apply(visitor);
    }

private:
    // Transformations between value/reference/ref-to-const versions of internal variant type, to let
    //     the set of value types supported by GenericMap be defined only once
    // Icky TMP, but I can't find another way to get at the template arguments for variant :(
    // Methods have no definition but can't be deleted without breaking type definitions below

    // may need to use std::reference_wrapper when migrating to std::variant, but it confuses Boost
    template <typename... Types>
    static boost::variant<std::add_lvalue_reference_t<Types>...> _typeToRef(
            boost::variant<Types...> const&) noexcept;
    template <typename... Types>
    static boost::variant<std::add_lvalue_reference_t<std::add_const_t<Types>>...> _typeToConstRef(
            boost::variant<Types...> const&) noexcept;

protected:
    using StorableType = boost::variant<bool, std::int32_t, std::int64_t, float, double, std::string,
                                        PolymorphicValue, std::shared_ptr<Storable>>;

    // this mouthful is shorter than the equivalent expression with result_of
    using ConstValueReference = decltype(_typeToConstRef(std::declval<StorableType>()));
    using ValueReference = decltype(_typeToRef(std::declval<StorableType>()));

    virtual ConstValueReference unsafeLookup(K key) const = 0;

    ValueReference unsafeLookup(K key) {
        ConstValueReference constRef = static_cast<const GenericMap&>(*this).unsafeLookup(key);
        auto removeConst = [](auto const& value) -> ValueReference {
            using NonConstRef = std::add_lvalue_reference_t<
                    std::remove_const_t<std::remove_reference_t<decltype(value)>>>;
            // This cast is safe; see Effective C++, Item 3
            return const_cast<NonConstRef>(value);
        };
        return boost::apply_visitor(removeConst, constRef);
    }

private:
    // Neither Storable nor shared_ptr<Storable>
    template <typename T,
              typename std::enable_if_t<
                      std::is_fundamental<T>::value || std::is_base_of<std::string, T>::value, int> = 0>
    T const& _at(Key<K, T> const& key) const {
        static_assert(!std::is_const<T>::value,
                      "Due to implementation constraints, const keys are not supported.");
        try {
            auto foo = unsafeLookup(key.getId());
            return boost::get<T const&>(foo);
        } catch (boost::bad_get const&) {
            std::stringstream message;
            message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
            throw LSST_EXCEPT(pex::exceptions::OutOfRangeError, message.str());
        }
    }

    // Storable and its subclasses
    template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
    T const& _at(Key<K, T> const& key) const {
        static_assert(!std::is_const<T>::value,
                      "Due to implementation constraints, const keys are not supported.");
        try {
            auto foo = unsafeLookup(key.getId());
            // Don't use pointer-based get, because it won't work after migrating to std::variant
            Storable const& value = boost::get<PolymorphicValue const&>(foo);
            T const* typedPointer = dynamic_cast<T const*>(&value);
            if (typedPointer != nullptr) {
                return *typedPointer;
            } else {
                std::stringstream message;
                message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
                throw LSST_EXCEPT(pex::exceptions::OutOfRangeError, message.str());
            }
        } catch (boost::bad_get const&) {
            std::stringstream message;
            message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
            throw LSST_EXCEPT(pex::exceptions::OutOfRangeError, message.str());
        }
    }

    // shared_ptr<Storable>
    template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
    std::shared_ptr<T> _at(Key<K, std::shared_ptr<T>> const& key) const {
        static_assert(!std::is_const<T>::value,
                      "Due to implementation constraints, const keys are not supported.");
        try {
            auto foo = unsafeLookup(key.getId());
            auto pointer = boost::get<std::shared_ptr<Storable> const&>(foo);
            std::shared_ptr<T> typedPointer = std::dynamic_pointer_cast<T>(pointer);
            // shared_ptr can be empty without being null. dynamic_pointer_cast
            // only promises result of failed cast is empty, so test for that
            if (typedPointer.use_count() > 0) {
                return typedPointer;
            } else {
                std::stringstream message;
                message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
                throw LSST_EXCEPT(pex::exceptions::OutOfRangeError, message.str());
            }
        } catch (boost::bad_get const&) {
            std::stringstream message;
            message << "Key " << key << " not found, but a key labeled " << key.getId() << " is present.";
            throw LSST_EXCEPT(pex::exceptions::OutOfRangeError, message.str());
        }
    }

    // Neither Storable nor shared_ptr<Storable>
    template <typename T,
              typename std::enable_if_t<
                      std::is_fundamental<T>::value || std::is_base_of<std::string, T>::value, int> = 0>
    bool _contains(Key<K, T> const& key) const {
        // Avoid actually getting and casting an object, if at all possible
        if (!contains(key.getId())) {
            return false;
        }

        auto foo = unsafeLookup(key.getId());
        // boost::variant has no equivalent to std::holds_alternative
        try {
            boost::get<T const&>(foo);
            return true;
        } catch (boost::bad_get const&) {
            return false;
        }
    }

    // Storable and its subclasses
    template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
    bool _contains(Key<K, T> const& key) const {
        // Avoid actually getting and casting an object, if at all possible
        if (!contains(key.getId())) {
            return false;
        }

        auto foo = unsafeLookup(key.getId());
        try {
            // Don't use pointer-based get, because it won't work after migrating to std::variant
            Storable const& value = boost::get<PolymorphicValue const&>(foo);
            auto asT = dynamic_cast<T const*>(&value);
            return asT != nullptr;
        } catch (boost::bad_get const&) {
            return false;
        }
    }

    // shared_ptr<Storable>
    template <typename T, typename std::enable_if_t<std::is_base_of<Storable, T>::value, int> = 0>
    bool _contains(Key<K, std::shared_ptr<T>> const& key) const {
        // Avoid actually getting and casting an object, if at all possible
        if (!contains(key.getId())) {
            return false;
        }

        auto foo = unsafeLookup(key.getId());
        try {
            auto pointer = boost::get<std::shared_ptr<Storable> const&>(foo);
            std::shared_ptr<T> typedPointer = std::dynamic_pointer_cast<T>(pointer);
            // shared_ptr can be empty without being null. dynamic_pointer_cast
            // only promises result of failed cast is empty, so test for that
            return typedPointer.use_count() > 0;
        } catch (boost::bad_get const&) {
            return false;
        }
    }

    // Type alias to properly handle Visitor output
    // Assume that each operator() has the same return type; variant will enforce it
    template <class Visitor>
    using _VisitorResult = std::result_of_t<Visitor && (K&&, bool&)>;

    // No return value, const GenericMap
    template <class Visitor, typename std::enable_if_t<std::is_void<_VisitorResult<Visitor>>::value, int> = 0>
    void _apply(Visitor&& visitor) const {
        for (K const& key : keys()) {
            boost::variant<K> varKey = key;
            boost::apply_visitor(visitor, varKey, unsafeLookup(key));
        }
    }

    // Return value, const GenericMap
    template <class Visitor,
              typename std::enable_if_t<!std::is_void<_VisitorResult<Visitor>>::value, int> = 0>
    auto _apply(Visitor&& visitor) const {
        std::vector<_VisitorResult<Visitor>> results;
        results.reserve(size());

        for (K const& key : keys()) {
            boost::variant<K> varKey = key;
            results.emplace_back(boost::apply_visitor(visitor, varKey, unsafeLookup(key)));
        }
        return results;
    }

    // No return value, non-const GenericMap
    template <class Visitor, typename std::enable_if_t<std::is_void<_VisitorResult<Visitor>>::value, int> = 0>
    void _apply(Visitor&& visitor) {
        for (K const& key : keys()) {
            boost::variant<K> varKey = key;
            // Boost gets confused if we pass it a temporary variant
            ValueReference ref = unsafeLookup(key);
            boost::apply_visitor(visitor, varKey, ref);
        }
    }

    // Return value, non-const GenericMap
    template <class Visitor,
              typename std::enable_if_t<!std::is_void<_VisitorResult<Visitor>>::value, int> = 0>
    auto _apply(Visitor&& visitor) {
        std::vector<_VisitorResult<Visitor>> results;
        results.reserve(size());

        for (K const& key : keys()) {
            boost::variant<K> varKey = key;
            // Boost gets confused if we pass it a temporary variant
            ValueReference ref = unsafeLookup(key);
            results.emplace_back(boost::apply_visitor(visitor, varKey, ref));
        }
        return results;
    }
};

template <typename K>
class MutableGenericMap : public GenericMap<K> {
protected:
    using typename GenericMap<K>::StorableType;

public:
    virtual ~MutableGenericMap() noexcept = default;

    virtual void clear() noexcept = 0;

    template <typename T>
    bool insert(Key<K, T> const& key, T const& value) {
        if (this->contains(key.getId())) {
            return false;
        }

        return unsafeInsert(key.getId(), StorableType(value));
    }

    template <typename T>
    std::pair<Key<K, T>, bool> insert(K const& key, T const& value) {
        auto strongKey = makeKey<T>(key);
        // Construct return value in advance, so that exception from copying/moving Key is atomic
        auto result = make_pair(strongKey, false);
        result.second = insert(strongKey, value);
        return result;
    }

    template <typename T>
    bool erase(Key<K, T> const& key) {
        if (this->contains(key)) {
            return unsafeErase(key.getId());
        } else {
            return false;
        }
    }

protected:
    virtual bool unsafeInsert(K key, StorableType&& value) = 0;

    virtual bool unsafeErase(K key) = 0;
};

}  // namespace typehandling
}  // namespace afw
}  // namespace lsst

namespace std {
template <typename K, typename V>
struct hash<typename lsst::afw::typehandling::Key<K, V>> {
    using argument_type = typename lsst::afw::typehandling::Key<K, V>;
    using result_type = size_t;
    size_t operator()(argument_type const& obj) const noexcept { return obj.hash_value(); }
};
}  // namespace std

#endif