Utility.hpp

Go to the documentation of this file.

//===- Utility.hpp ----------------------------------------------*- C++ -*-===//
//
//  Copyright (C) 2021 GrammaTech, Inc.
//
//  This code is licensed under the MIT license. See the LICENSE file in the
//  project root for license terms.
//
//  This project is sponsored by the Office of Naval Research, One Liberty
//  Center, 875 N. Randolph Street, Arlington, VA 22203 under contract #
//  N68335-17-C-0700.  The content of the information does not necessarily
//  reflect the position or policy of the Government and no official
//  endorsement should be inferred.
//
//===----------------------------------------------------------------------===//
#ifndef GTIRB_UTILITY_H
#define GTIRB_UTILITY_H
 
#include <gtirb/Addr.hpp>
#include <gtirb/Export.hpp>
#include <gtirb/Node.hpp>
#include <algorithm>
#include <boost/iterator/iterator_categories.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/iterator/iterator_traits.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/range/iterator_range.hpp>
#include <functional>
#include <iterator>
#include <optional>
#include <type_traits>
#include <vector>
 
namespace gtirb {
 
 
template <typename ForwardIterator,
          typename Compare = std::less<
              typename std::iterator_traits<ForwardIterator>::value_type>>
class MergeSortedIterator
    : public boost::iterator_facade<
          MergeSortedIterator<ForwardIterator, Compare>,
          typename std::iterator_traits<ForwardIterator>::value_type,
          boost::forward_traversal_tag,
          typename std::iterator_traits<ForwardIterator>::reference,
          typename std::iterator_traits<ForwardIterator>::difference_type> {
public:
  MergeSortedIterator() = default;
 
  template <typename OtherForwardIterator>
  MergeSortedIterator(
      const MergeSortedIterator<OtherForwardIterator, Compare>& MSI,
      std::enable_if_t<
          std::is_convertible_v<OtherForwardIterator, ForwardIterator>, void*> =
          0)
      : Ranges(MSI.Ranges.begin(), MSI.Ranges.end()) {}
 
  template <typename RangeIteratorRange>
  explicit MergeSortedIterator(RangeIteratorRange RangeRange) {
    for (const auto& Range : RangeRange) {
      if (auto RBegin = Range.begin(), REnd = Range.end(); RBegin != REnd) {
        Ranges.emplace_back(RBegin, REnd);
      }
    }
    // Establish the heap invariant for Ranges.
    std::make_heap(Ranges.begin(), Ranges.end(), rangeGreaterThan);
  }
 
  template <typename RangeIterator>
  MergeSortedIterator(RangeIterator Begin, RangeIterator End)
      : MergeSortedIterator(boost::make_iterator_range(Begin, End)) {}
 
  // Beginning of functions for iterator facade compatibility.
  typename std::iterator_traits<ForwardIterator>::reference
  dereference() const {
    assert(!Ranges.empty() && "Attempt to dereference end of iterator!");
    return *Ranges.front().first;
  }
 
  bool equal(const MergeSortedIterator<ForwardIterator, Compare>& Other) const {
    return Ranges == Other.Ranges;
  }
 
  void increment() {
    assert(!Ranges.empty() && "Attempt to increment end of iterator!");
    // After incrementing the first range, it may no longer have the lowest
    // first element. Removing the range, then re-inserting it ensures that the
    // heap invariant is maintained.
    std::pop_heap(Ranges.begin(), Ranges.end(), rangeGreaterThan);
    ++Ranges.back().first;
    if (Ranges.back().first == Ranges.back().second) {
      Ranges.pop_back();
    } else {
      std::push_heap(Ranges.begin(), Ranges.end(), rangeGreaterThan);
    }
  }
  // End of functions for iterator facade compatibility.
private:
  template <typename OtherForwardIterator, typename OtherCompare>
  friend class MergeSortedIterator;
 
  using RangeType = std::pair<ForwardIterator, ForwardIterator>;
 
  // Compares two ranges according to the relationship of their first elements
  // given by \c Compare. Empty ranges are treated as being greater than any
  // non-empty range.
  static bool rangeGreaterThan(const RangeType& R1, const RangeType& R2) {
    if (R1.first == R1.second)
      // An empty R1 is greater than every R2.
      return true;
    if (R2.first == R2.second)
      // Any R1 is less than an empty R2.
      return false;
    // Flip the comparison to implement "greater-than".
    return Compare()(*R2.first, *R1.first);
  }
 
  // Ranges is a heap ordered by \c rangeGreaterThan. This ensures that the
  // range with the lowest first element (according to \c Compare) is always at
  // the front.
  std::vector<RangeType> Ranges;
};
 
struct GTIRB_EXPORT_API AddressLess {
  template <typename NodeType> auto key(const NodeType* N) const {
    return std::make_tuple(N->getAddress(), N->getSize(), N->getUUID());
  }
 
  template <typename NodeType>
  bool operator()(const NodeType* N1, const NodeType* N2) const {
    return key(N1) < key(N2);
  }
 
  template <typename NodeType,
            typename = std::enable_if_t<!std::is_pointer_v<NodeType>>>
  bool operator()(const NodeType& N1, const NodeType& N2) const {
    return operator()(&N1, &N2);
  }
 
  template <typename NodeType>
  bool operator()(const NodeType* N1, const Addr& A2) const {
    return N1->getAddress() < A2;
  }
 
  template <typename NodeType>
  bool operator()(const Addr& A1, const NodeType* N2) const {
    return A1 < N2->getAddress();
  }
};
 
template <>
GTIRB_EXPORT_API bool
AddressLess::operator()<CodeBlock>(const CodeBlock* B1,
                                   const CodeBlock* B2) const;
 
template <>
GTIRB_EXPORT_API bool
AddressLess::operator()<DataBlock>(const DataBlock* B1,
                                   const DataBlock* B2) const;
 
struct GTIRB_EXPORT_API BlockAddressLess {
  bool operator()(const Node* N1, const Node* N2) const {
    return operator()(*N1, *N2);
  }
  bool operator()(const Node& N1, const Node& N2) const;
};
 
template <typename T> struct ArbitraryLess {
  bool operator()(const T& N1, const T& N2) const { return &N1 < &N2; }
};
 
template <typename T, typename Method, Method Begin, Method End>
struct NodeToChildRange {
  boost::iterator_range<decltype((std::declval<T>().*Begin)())>
  operator()(T& N) const {
    return boost::make_iterator_range((N.*Begin)(), (N.*End)());
  }
};
 
template <typename T>
using NodeToBlockRange = NodeToChildRange<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_block_iterator (T::*)() const,
                       typename T::block_iterator (T::*)()>,
    &T::blocks_begin, &T::blocks_end>;
 
template <typename T>
using NodeToCodeBlockRange = NodeToChildRange<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_code_block_iterator (T::*)() const,
                       typename T::code_block_iterator (T::*)()>,
    &T::code_blocks_begin, &T::code_blocks_end>;
 
template <typename T>
using NodeToDataBlockRange = NodeToChildRange<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_data_block_iterator (T::*)() const,
                       typename T::data_block_iterator (T::*)()>,
    &T::data_blocks_begin, &T::data_blocks_end>;
 
template <typename T>
using NodeToSymbolicExpressionRange = NodeToChildRange<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_symbolic_expression_iterator (T::*)()
                           const,
                       typename T::symbolic_expression_iterator (T::*)()>,
    &T::symbolic_expressions_begin, &T::symbolic_expressions_end>;
 
template <typename T>
using NodeToByteIntervalRange = NodeToChildRange<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_byte_interval_iterator (T::*)() const,
                       typename T::byte_interval_iterator (T::*)()>,
    &T::byte_intervals_begin, &T::byte_intervals_end>;
 
template <typename T>
using NodeToSymbolRange = NodeToChildRange<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_symbol_iterator (T::*)() const,
                       typename T::symbol_iterator (T::*)()>,
    &T::symbols_begin, &T::symbols_end>;
 
template <typename T>
using NodeToSectionRange = NodeToChildRange<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_section_iterator (T::*)() const,
                       typename T::section_iterator (T::*)()>,
    &T::sections_begin, &T::sections_end>;
 
template <typename T>
using NodeToProxyBlockRange = NodeToChildRange<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_proxy_block_iterator (T::*)() const,
                       typename T::proxy_block_iterator (T::*)()>,
    &T::proxy_blocks_begin, &T::proxy_blocks_end>;
 
template <typename T, typename MethodType, MethodType Method>
struct FindNodesAt {
  Addr A;
 
  FindNodesAt(Addr A_) : A{A_} {}
 
  decltype((std::declval<T>().*Method)(Addr())) operator()(T& N) const {
    return (N.*Method)(A);
  }
};
 
template <typename T, typename MethodType, MethodType Method> struct FindNodes {
  std::string X;
 
  FindNodes(std::string X_) : X{X_} {}
 
  decltype((std::declval<T>().*Method)(std::string())) operator()(T& N) const {
    return (N.*Method)((std::string&)X);
  }
};
 
template <typename T, typename MethodType, MethodType Method>
struct FindNodesBetween {
  Addr Low, High;
 
  FindNodesBetween(Addr Low_, Addr High_) : Low{Low_}, High{High_} {}
 
  decltype((std::declval<T>().*Method)(Addr(), Addr())) operator()(T& N) const {
    return (N.*Method)(Low, High);
  }
};
 
template <typename T>
using FindBlocksIn = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_block_subrange (T::*)(Addr) const,
                       typename T::block_subrange (T::*)(Addr)>,
    &T::findBlocksOn>;
 
template <typename T>
using FindBlocksAt = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_block_range (T::*)(Addr) const,
                       typename T::block_range (T::*)(Addr)>,
    &T::findBlocksAt>;
 
template <typename T>
using FindBlocksBetween = FindNodesBetween<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_block_range (T::*)(Addr, Addr) const,
                       typename T::block_range (T::*)(Addr, Addr)>,
    &T::findBlocksAt>;
 
template <typename T>
using FindCodeBlocksIn = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_code_block_subrange (T::*)(Addr) const,
                       typename T::code_block_subrange (T::*)(Addr)>,
    &T::findCodeBlocksOn>;
 
template <typename T>
using FindCodeBlocksAt = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_code_block_range (T::*)(Addr) const,
                       typename T::code_block_range (T::*)(Addr)>,
    &T::findCodeBlocksAt>;
 
template <typename T>
using FindCodeBlocksBetween = FindNodesBetween<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_code_block_range (T::*)(Addr, Addr)
                           const,
                       typename T::code_block_range (T::*)(Addr, Addr)>,
    &T::findCodeBlocksAt>;
 
template <typename T>
using FindDataBlocksIn = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_data_block_subrange (T::*)(Addr) const,
                       typename T::data_block_subrange (T::*)(Addr)>,
    &T::findDataBlocksOn>;
 
template <typename T>
using FindDataBlocksAt = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_data_block_range (T::*)(Addr) const,
                       typename T::data_block_range (T::*)(Addr)>,
    &T::findDataBlocksAt>;
 
template <typename T>
using FindDataBlocksBetween = FindNodesBetween<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_data_block_range (T::*)(Addr, Addr)
                           const,
                       typename T::data_block_range (T::*)(Addr, Addr)>,
    &T::findDataBlocksAt>;
 
template <typename T>
using FindSymExprsAt = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_symbolic_expression_range (T::*)(Addr)
                           const,
                       typename T::symbolic_expression_range (T::*)(Addr)>,
    &T::findSymbolicExpressionsAt>;
 
template <typename T>
using FindSymExprsBetween = FindNodesBetween<
    T,
    std::conditional_t<
        std::is_const_v<T>,
        typename T::const_symbolic_expression_range (T::*)(Addr, Addr) const,
        typename T::symbolic_expression_range (T::*)(Addr, Addr)>,
    &T::findSymbolicExpressionsAt>;
 
template <typename T>
using FindByteIntervalsIn =
    FindNodesAt<T,
                std::conditional_t<
                    std::is_const_v<T>,
                    typename T::const_byte_interval_subrange (T::*)(Addr) const,
                    typename T::byte_interval_subrange (T::*)(Addr)>,
                &T::findByteIntervalsOn>;
 
template <typename T>
using FindByteIntervalsAt = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_byte_interval_range (T::*)(Addr) const,
                       typename T::byte_interval_range (T::*)(Addr)>,
    &T::findByteIntervalsAt>;
 
template <typename T>
using FindByteIntervalsBetween = FindNodesBetween<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_byte_interval_range (T::*)(Addr, Addr)
                           const,
                       typename T::byte_interval_range (T::*)(Addr, Addr)>,
    &T::findByteIntervalsAt>;
 
template <typename T>
using FindSectionsIn = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_section_subrange (T::*)(Addr) const,
                       typename T::section_subrange (T::*)(Addr)>,
    &T::findSectionsOn>;
 
template <typename T>
using FindSectionsAt = FindNodesAt<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_section_range (T::*)(Addr) const,
                       typename T::section_range (T::*)(Addr)>,
    &T::findSectionsAt>;
 
template <typename T>
using FindSections = FindNodes<
    T,
    std::conditional_t<
        std::is_const_v<T>,
        typename T::const_section_name_range (T::*)(const std::string& X) const,
        typename T::section_name_range (T::*)(const std::string& X)>,
    &T::findSections>;
 
template <typename T>
using FindSectionsBetween = FindNodesBetween<
    T,
    std::conditional_t<std::is_const_v<T>,
                       typename T::const_section_range (T::*)(Addr, Addr) const,
                       typename T::section_range (T::*)(Addr, Addr)>,
    &T::findSectionsAt>;
 
 
} // namespace gtirb
 
#endif // GTIRB_UTILITY_H