Subversion Repositories Games.Descent

Rev

Blame | Last modification | View Log | Download | RSS feed

  1. /*
  2.  * This file is part of the DXX-Rebirth project <https://www.dxx-rebirth.com/>.
  3.  * It is copyright by its individual contributors, as recorded in the
  4.  * project's Git history.  See COPYING.txt at the top level for license
  5.  * terms and a link to the Git history.
  6.  */
  7. #pragma once
  8. #include <array>
  9. #include <stdexcept>
  10. #include <iterator>
  11. #include <cstdio>
  12. #include <string>
  13. #include <type_traits>
  14. #include "fwd-partial_range.h"
  15. #include <memory>
  16. #include "dxxsconf.h"
  17.  
  18. /* If no value was specified for DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE,
  19.  * then define it to true for NDEBUG builds and false for debug builds.
  20.  *
  21.  * When DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE is true, the partial_range
  22.  * exception is a global scope structure.
  23.  *
  24.  * When DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE is false, the
  25.  * partial_range exception is nested in partial_range_t<I>, so that the
  26.  * exception type encodes the range type.
  27.  *
  28.  * Encoding the range type in the exception produces a more descriptive
  29.  * message when the program aborts for an uncaught exception, but
  30.  * produces larger debug information and many nearly-redundant
  31.  * instantiations of the report function.  Using the global scope
  32.  * structure avoids those redundant instances, but makes the exception
  33.  * description less descriptive.
  34.  *
  35.  * Choose false if you expect to debug partial_range exceptions or
  36.  * report them to someone who will debug them for you.  Choose true if
  37.  * you want a smaller program.
  38.  */
  39. #ifndef DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE
  40. #ifdef NDEBUG
  41. #define DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE   1
  42. #else
  43. #define DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE   0
  44. #endif
  45. #endif
  46.  
  47. namespace partial_range_detail
  48. {
  49.  
  50. namespace {
  51.  
  52. #define REPORT_FORMAT_STRING     "%s:%u: %s %lu past %p end %lu \"%s\""
  53. /* Round reporting into large buckets.  Code size is more
  54.  * important than stack space on a cold path.
  55.  */
  56. template <std::size_t NF, std::size_t NE>
  57. constexpr std::size_t required_buffer_size = ((sizeof(REPORT_FORMAT_STRING) + sizeof("65535") + (sizeof("18446744073709551615") * 2) + sizeof("0x0000000000000000") + (NF + NE + sizeof("begin"))) | 0xff) + 1;
  58.  
  59. template <std::size_t N>
  60. __attribute_cold
  61. void prepare_error_string(std::array<char, N> &buf, unsigned long d, const char *estr, const char *file, unsigned line, const char *desc, unsigned long expr, const void *t)
  62. {
  63.         std::snprintf(buf.data(), buf.size(), REPORT_FORMAT_STRING, file, line, desc, expr, t, d, estr);
  64. }
  65. #undef REPORT_FORMAT_STRING
  66.  
  67. /*
  68.  * These are placed out of line from the class and used as an
  69.  * indirection, so that the compiler can pick std::begin/std::end or ADL
  70.  * appropriate alternatives, if they exist.
  71.  */
  72. template <typename T>
  73. inline auto adl_begin(T &t)
  74. {
  75.         using std::begin;
  76.         return begin(t);
  77. }
  78.  
  79. template <typename T>
  80. inline auto adl_end(T &t)
  81. {
  82.         using std::end;
  83.         return end(t);
  84. }
  85.  
  86. }
  87.  
  88. }
  89.  
  90. #if DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE
  91. struct partial_range_error;
  92. #endif
  93.  
  94. template <typename I>
  95. class partial_range_t
  96. {
  97. public:
  98.         using range_owns_iterated_storage = std::false_type;
  99.         typedef I iterator;
  100.         /* When using the unminimized type, forward declare a structure.
  101.          *
  102.          * When using the minimized type, add a typedef here so that later
  103.          * code can unconditionally use the qualified type name.  Using a
  104.          * typedef here instead of a preprocessor macro at the usage sites
  105.          * causes the debug information to be very slightly bigger, but has
  106.          * no effect on the size of the generated code and is easier to
  107.          * maintain.
  108.          */
  109. #if DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE
  110.         using partial_range_error =
  111. #endif
  112.         struct partial_range_error;
  113.         iterator m_begin, m_end;
  114.         partial_range_t(iterator b, iterator e) :
  115.                 m_begin(b), m_end(e)
  116.         {
  117.         }
  118.         partial_range_t(const partial_range_t &) = default;
  119.         partial_range_t(partial_range_t &&) = default;
  120.         partial_range_t &operator=(const partial_range_t &) = default;
  121.         template <typename T>
  122.                 partial_range_t(T &t) :
  123.                         m_begin(partial_range_detail::adl_begin(t)), m_end(partial_range_detail::adl_end(t))
  124.         {
  125.         }
  126.         template <typename T>
  127.                 partial_range_t(partial_range_t<T> &&t) :
  128.                         m_begin(t.begin()), m_end(t.end())
  129.         {
  130.         }
  131.         __attribute_warn_unused_result
  132.         iterator begin() const { return m_begin; }
  133.         __attribute_warn_unused_result
  134.         iterator end() const { return m_end; }
  135.         bool empty() const __attribute_warn_unused_result
  136.         {
  137.                 return m_begin == m_end;
  138.         }
  139.         __attribute_warn_unused_result
  140.         std::size_t size() const { return std::distance(m_begin, m_end); }
  141.         std::reverse_iterator<iterator> rbegin() const __attribute_warn_unused_result { return std::reverse_iterator<iterator>{m_end}; }
  142.         std::reverse_iterator<iterator> rend() const __attribute_warn_unused_result { return std::reverse_iterator<iterator>{m_begin}; }
  143.         partial_range_t<std::reverse_iterator<iterator>> reversed() const __attribute_warn_unused_result
  144.         {
  145.                 return {rbegin(), rend()};
  146.         }
  147. };
  148.  
  149. #if DXX_PARTIAL_RANGE_MINIMIZE_ERROR_TYPE
  150. struct partial_range_error
  151. #else
  152. template <typename I>
  153. struct partial_range_t<I>::partial_range_error
  154. #endif
  155.         final : std::out_of_range
  156. {
  157.         DXX_INHERIT_CONSTRUCTORS(partial_range_error, out_of_range);
  158.         template <std::size_t N>
  159.                 __attribute_cold
  160.                 __attribute_noreturn
  161.         static void report(const char *file, unsigned line, const char *estr, const char *desc, unsigned long expr, const void *t, unsigned long d)
  162.         {
  163.                 std::array<char, N> buf;
  164.                 partial_range_detail::prepare_error_string(buf, d, estr, file, line, desc, expr, t);
  165.                 throw partial_range_error(buf.data());
  166.         }
  167. };
  168.  
  169. namespace partial_range_detail
  170. {
  171.  
  172. namespace {
  173.  
  174. template <typename I, std::size_t required_buffer_size>
  175. inline void check_range_bounds(const char *file, unsigned line, const char *estr, const void *t, const std::size_t o, const std::size_t l, const std::size_t d)
  176. {
  177. #ifdef DXX_CONSTANT_TRUE
  178.         /*
  179.          * If EXPR and d are compile-time constant, and the (EXPR > d)
  180.          * branch is optimized out, then the expansion of
  181.          * PARTIAL_RANGE_COMPILE_CHECK_BOUND is optimized out, preventing
  182.          * the compile error.
  183.          *
  184.          * If EXPR and d are compile-time constant, and the (EXPR > d)
  185.          * branch is not optimized out, then this function is guaranteed to
  186.          * throw if it is ever called.  In that case, the compile fails,
  187.          * since the program is guaranteed not to work as the programmer
  188.          * intends.
  189.          *
  190.          * If they are not compile-time constant, but the compiler can
  191.          * optimize based on constants, then it will optimize out the
  192.          * expansion of PARTIAL_RANGE_COMPILE_CHECK_BOUND, preventing the
  193.          * compile error.  The function might throw on invalid inputs,
  194.          * including constant inputs that the compiler failed to recognize
  195.          * as compile-time constant.
  196.          *
  197.          * If the compiler cannot optimize based on the result of
  198.          * __builtin_constant_p (such as at -O0), then configure tests do
  199.          * not define DXX_CONSTANT_TRUE and the macro expands to nothing.
  200.          */
  201. #define PARTIAL_RANGE_COMPILE_CHECK_BOUND(EXPR,S)       \
  202.         (DXX_CONSTANT_TRUE(EXPR > d) && (DXX_ALWAYS_ERROR_FUNCTION(partial_range_will_always_throw_##S, #S " will always throw"), 0))
  203. #else
  204. #define PARTIAL_RANGE_COMPILE_CHECK_BOUND(EXPR,S)       static_cast<void>(0)
  205. #endif
  206. #define PARTIAL_RANGE_CHECK_BOUND(EXPR,S)       \
  207.         PARTIAL_RANGE_COMPILE_CHECK_BOUND(EXPR,S),      \
  208.         ((EXPR > d) && (I::template report<required_buffer_size>(file, line, estr, #S, EXPR, t, d), 0))
  209.         PARTIAL_RANGE_CHECK_BOUND(o, begin);
  210.         PARTIAL_RANGE_CHECK_BOUND(l, end);
  211. #undef PARTIAL_RANGE_CHECK_BOUND
  212. #undef PARTIAL_RANGE_COMPILE_CHECK_BOUND
  213. }
  214.  
  215. template <typename I, std::size_t N, typename T>
  216. inline void check_partial_range(const char *file, unsigned line, const char *estr, const T &t, const std::size_t o, const std::size_t l)
  217. {
  218.         check_range_bounds<I, N>(file, line, estr, std::addressof(t), o, l, std::size(t));
  219. }
  220.  
  221. #ifdef DXX_HAVE_BUILTIN_OBJECT_SIZE
  222. template <typename I, std::size_t required_buffer_size, typename P>
  223. inline void check_range_object_size(const char *file, unsigned line, const char *estr, P &ref, const std::size_t o, const std::size_t l)
  224. {
  225.         const auto ptr = std::addressof(ref);
  226.         const std::size_t bos = __builtin_object_size(ptr, 1);
  227.         if (bos != static_cast<std::size_t>(-1))
  228.                 check_range_bounds<I, required_buffer_size>(file, line, estr, ptr, o, l, bos / sizeof(P));
  229. }
  230.  
  231. /* When P refers to a temporary, this overload is picked.  Temporaries
  232.  * have no useful address, so they cannot be checked.  A temporary would
  233.  * be present if iterator.operator*() returns a proxy object, rather
  234.  * than a reference to an element in the container.
  235.  */
  236. template <typename I, std::size_t required_buffer_size, typename P>
  237. void check_range_object_size(const char *, unsigned, const char *, const P &&, std::size_t, std::size_t) {}
  238. #endif
  239.  
  240. }
  241.  
  242. }
  243.  
  244. namespace {
  245.  
  246. template <typename I, std::size_t required_buffer_size>
  247. __attribute_warn_unused_result
  248. inline partial_range_t<I> (unchecked_partial_range)(const char *const file, const unsigned line, const char *const estr, I range_begin, const std::size_t o, const std::size_t l)
  249. {
  250. #ifdef DXX_CONSTANT_TRUE
  251.         /* Compile-time only check.  Runtime handles (o > l) correctly, and
  252.          * it can happen in a correct program.  If it is guaranteed to
  253.          * happen, then the range is always empty, which likely indicates a
  254.          * bug.
  255.          */
  256.         if (DXX_CONSTANT_TRUE(!(o < l)))
  257.                 DXX_ALWAYS_ERROR_FUNCTION(partial_range_is_always_empty, "offset never less than length");
  258. #endif
  259. #ifdef DXX_HAVE_BUILTIN_OBJECT_SIZE
  260.         /* Avoid iterator dereference if range is empty */
  261.         if (l)
  262.         {
  263.                 partial_range_detail::check_range_object_size<typename partial_range_t<I>::partial_range_error, required_buffer_size>(file, line, estr, *range_begin, o, l);
  264.         }
  265. #else
  266.         (void)file;
  267.         (void)line;
  268.         (void)estr;
  269. #endif
  270.         auto range_end = range_begin;
  271.         /* Use <= so that (o == 0) makes the expression always-true, so the
  272.          * compiler will optimize out the test.
  273.          */
  274.         if (o <= l)
  275.         {
  276.                 using std::advance;
  277.                 advance(range_begin, o);
  278.                 advance(range_end, l);
  279.         }
  280.         return {range_begin, range_end};
  281. }
  282.  
  283. template <typename I, typename UO, typename UL, std::size_t NF, std::size_t NE>
  284. __attribute_warn_unused_result
  285. inline partial_range_t<I> (unchecked_partial_range)(const char (&file)[NF], unsigned line, const char (&estr)[NE], I range_begin, const UO &o, const UL &l)
  286. {
  287.         /* Require unsigned length */
  288.         //static_assert(std::is_unsigned<UO>::value, "offset to partial_range must be unsigned");
  289.         static_assert(std::is_unsigned<UL>::value, "length to partial_range must be unsigned");
  290.         return unchecked_partial_range<I, partial_range_detail::required_buffer_size<NF, NE>>(
  291.                 file, line, estr, range_begin, o, l
  292.         );
  293. }
  294.  
  295. template <typename I, typename UL, std::size_t NF, std::size_t NE>
  296. __attribute_warn_unused_result
  297. inline partial_range_t<I> (unchecked_partial_range)(const char (&file)[NF], unsigned line, const char (&estr)[NE], I range_begin, const UL &l)
  298. {
  299.         return unchecked_partial_range<I, UL, UL>(file, line, estr, range_begin, 0, l);
  300. }
  301.  
  302. template <typename T, typename UO, typename UL, std::size_t NF, std::size_t NE, typename I = decltype(std::begin(std::declval<T &>()))>
  303. __attribute_warn_unused_result
  304. inline partial_range_t<I> (partial_range)(const char (&file)[NF], unsigned line, const char (&estr)[NE], T &t, const UO &o, const UL &l)
  305. {
  306.         partial_range_detail::check_partial_range<typename partial_range_t<I>::partial_range_error, partial_range_detail::required_buffer_size<NF, NE>, T>(file, line, estr, t, o, l);
  307.         return unchecked_partial_range<I, UO, UL>(file, line, estr, std::begin(t), o, l);
  308. }
  309.  
  310. template <typename T, typename UL, std::size_t NF, std::size_t NE>
  311. __attribute_warn_unused_result
  312. inline auto (partial_range)(const char (&file)[NF], const unsigned line, const char (&estr)[NE], T &t, const UL &l)
  313. {
  314.         return partial_range<T, UL, UL>(file, line, estr, t, 0, l);
  315. }
  316.  
  317. template <typename T, typename UO, typename UL, std::size_t NF, std::size_t NE>
  318. __attribute_warn_unused_result
  319. inline auto (partial_const_range)(const char (&file)[NF], unsigned line, const char (&estr)[NE], const T &t, const UO &o, const UL &l)
  320. {
  321.         return partial_range<const T, UO, UL>(file, line, estr, t, o, l);
  322. }
  323.  
  324. template <typename T, typename UL, std::size_t NF, std::size_t NE>
  325. __attribute_warn_unused_result
  326. inline auto (partial_const_range)(const char (&file)[NF], unsigned line, const char (&estr)[NE], const T &t, const UL &l)
  327. {
  328.         return partial_range<const T, UL>(file, line, estr, t, l);
  329. }
  330.  
  331. template <typename T, typename I = decltype(std::begin(std::declval<T &>()))>
  332. __attribute_warn_unused_result
  333. inline partial_range_t<I> (make_range)(T &t)
  334. {
  335.         return t;
  336. }
  337.  
  338. }
  339.  
  340. /* Explicitly block use on rvalue t because returned partial_range_t<I>
  341.  * will outlive the rvalue.
  342.  */
  343. template <typename T, typename UO, typename UL, std::size_t NF, std::size_t NE, typename I = decltype(begin(std::declval<T &&>()))>
  344. partial_range_t<I> (partial_const_range)(const char (&file)[NF], unsigned line, const char (&estr)[NE], const T &&t, const UO &o, const UL &l) = delete;
  345.  
  346. template <typename T, typename UL, std::size_t NF, std::size_t NE, typename I = decltype(begin(std::declval<T &&>()))>
  347. partial_range_t<I> (partial_const_range)(const char (&file)[NF], unsigned line, const char (&estr)[NE], const T &&t, const UL &l) = delete;
  348.  
  349. #define unchecked_partial_range(T,...)  unchecked_partial_range(__FILE__, __LINE__, #T, T, ##__VA_ARGS__)
  350. #define partial_range(T,...)    partial_range(__FILE__, __LINE__, #T, T, ##__VA_ARGS__)
  351. #define partial_const_range(T,...)      partial_const_range(__FILE__, __LINE__, #T, T, ##__VA_ARGS__)
  352.