1  /* A type for indices and sizes.
       2     Copyright (C) 2020-2023 Free Software Foundation, Inc.
       3     This file is part of the GNU C Library.
       4  
       5     The GNU C Library is free software; you can redistribute it and/or
       6     modify it under the terms of the GNU Lesser General Public
       7     License as published by the Free Software Foundation; either
       8     version 2.1 of the License, or (at your option) any later version.
       9  
      10     The GNU C Library is distributed in the hope that it will be useful,
      11     but WITHOUT ANY WARRANTY; without even the implied warranty of
      12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
      13     Lesser General Public License for more details.
      14  
      15     You should have received a copy of the GNU Lesser General Public
      16     License along with the GNU C Library; if not, see
      17     <https://www.gnu.org/licenses/>.  */
      18  
      19  #ifndef _IDX_H
      20  #define _IDX_H
      21  
      22  /* Get ptrdiff_t.  */
      23  #include <stddef.h>
      24  
      25  /* Get PTRDIFF_MAX.  */
      26  #include <stdint.h>
      27  
      28  /* The type 'idx_t' holds an (array) index or an (object) size.
      29     Its implementation promotes to a signed integer type,
      30     which can hold the values
      31       0..2^63-1 (on 64-bit platforms) or
      32       0..2^31-1 (on 32-bit platforms).
      33  
      34     Why a signed integer type?
      35  
      36       * Security: Signed types can be checked for overflow via
      37         '-fsanitize=undefined', but unsigned types cannot.
      38  
      39       * Comparisons without surprises: ISO C99 § 6.3.1.8 specifies a few
      40         surprising results for comparisons, such as
      41  
      42             (int) -3 < (unsigned long) 7  =>  false
      43             (int) -3 < (unsigned int) 7   =>  false
      44         and on 32-bit machines:
      45             (long) -3 < (unsigned int) 7  =>  false
      46  
      47         This is surprising because the natural comparison order is by
      48         value in the realm of infinite-precision signed integers (ℤ).
      49  
      50         The best way to get rid of such surprises is to use signed types
      51         for numerical integer values, and use unsigned types only for
      52         bit masks and enums.
      53  
      54     Why not use 'size_t' directly?
      55  
      56       * Because 'size_t' is an unsigned type, and a signed type is better.
      57         See above.
      58  
      59     Why not use 'ptrdiff_t' directly?
      60  
      61       * Maintainability: When reading and modifying code, it helps to know that
      62         a certain variable cannot have negative values.  For example, when you
      63         have a loop
      64  
      65           int n = ...;
      66           for (int i = 0; i < n; i++) ...
      67  
      68         or
      69  
      70           ptrdiff_t n = ...;
      71           for (ptrdiff_t i = 0; i < n; i++) ...
      72  
      73         you have to ask yourself "what if n < 0?".  Whereas in
      74  
      75           idx_t n = ...;
      76           for (idx_t i = 0; i < n; i++) ...
      77  
      78         you know that this case cannot happen.
      79  
      80         Similarly, when a programmer writes
      81  
      82           idx_t = ptr2 - ptr1;
      83  
      84         there is an implied assertion that ptr1 and ptr2 point into the same
      85         object and that ptr1 <= ptr2.
      86  
      87       * Being future-proof: In the future, range types (integers which are
      88         constrained to a certain range of values) may be added to C compilers
      89         or to the C standard.  Several programming languages (Ada, Haskell,
      90         Common Lisp, Pascal) already have range types.  Such range types may
      91         help producing good code and good warnings.  The type 'idx_t' could
      92         then be typedef'ed to a range type that is signed after promotion.  */
      93  
      94  /* In the future, idx_t could be typedef'ed to a signed range type.
      95     The clang "extended integer types", supported in Clang 11 or newer
      96     <https://clang.llvm.org/docs/LanguageExtensions.html#extended-integer-types>,
      97     are a special case of range types.  However, these types don't support binary
      98     operators with plain integer types (e.g. expressions such as x > 1).
      99     Therefore, they don't behave like signed types (and not like unsigned types
     100     either).  So, we cannot use them here.  */
     101  
     102  /* Use the signed type 'ptrdiff_t'.  */
     103  /* Note: ISO C does not mandate that 'size_t' and 'ptrdiff_t' have the same
     104     size, but it is so on all platforms we have seen since 1990.  */
     105  typedef ptrdiff_t idx_t;
     106  
     107  /* IDX_MAX is the maximum value of an idx_t.  */
     108  #define IDX_MAX PTRDIFF_MAX
     109  
     110  /* So far no need has been found for an IDX_WIDTH macro.
     111     Perhaps there should be another macro IDX_VALUE_BITS that does not
     112     count the sign bit and is therefore one less than PTRDIFF_WIDTH.  */
     113  
     114  #endif /* _IDX_H */