Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #152534

Re: What is the rank of size_t ?

Show key headers only | View raw

Spiros Bousbouras <spibou@gmail.com> writes:

> On Wed, 27 May 2020 12:49:41 GMT
> Spiros Bousbouras <spibou@gmail.com> wrote:
>
>> Specifically , if a has type int and b has type size_t , can a + b
>> overflow i.e. cause undefined behaviour ?
>
> Let me expand on the question.  First I will quote "6.3.1.8 Usual
> arithmetic conversions" :
>
>     Otherwise, the integer promotions are performed on both
>     operands.  Then the following rules are applied to the promoted
>     operands:
>
>       If both operands have the same type, then no further
>       conversion is needed.  Otherwise, if both operands have signed
>       integer types or both have unsigned integer types, the operand
>       with the type of lesser integer conversion rank is converted
>       to the type of the operand with greater rank.
>
>       Otherwise, if the operand that has unsigned integer type has
>       rank greater or equal to the rank of the type of the other
>       operand, then the operand with signed integer type is
>       converted to the type of the operand with unsigned integer
>       type.
>
>       Otherwise, if the type of the operand with signed integer type
>       can represent all of the values of the type of the operand
>       with unsigned integer type, then the operand with unsigned
>       integer type is converted to the type of the operand with
>       signed integer type.
>
>       Otherwise, both operands are converted to the unsigned integer
>       type corresponding to the type of the operand with signed
>       integer type.
>
> The first 2 paragraphs don't apply because the standard doesn't say
> anything about the rank of size_t .

(Note that the "first paragraph" is actually two paragraphs in
the Standard.  But I will use the text as written above.)

The first paragraph /may/ apply if size_t has a conversion rank
less than int.  If so, then size_t could have been promoted to
int, so both types are int, and the addition is done in type
int, which can overflow.

The second paragraph /may/ apply but we don't know if it does apply
because we don't know whether (a) size_t has a conversion rank
less than int but was promoted to unsigned int, or (b) size_t has
a conversion rank greater than or equal to int.  If the second
paragraph applies, then no overflow is possible.

Note that size_t does have an integer conversion rank even if we
don't know what it is.

> The 3rd paragraph may apply

When the type of 'a' is int the third paragraph /cannot/ apply
because one of the first two paragraphs must apply even though we
don't know which one does.  This conclusion follows from the
lead-in sentence that says "the integer promotions are performed
on both operands."

When the type of 'a' is long the third paragraph may apply, so
let's proceed on that basis.

> and you can check using the preprocessor
> as in
>
>     #if SIZE_MAX >= LONG_MAX  [changed from INT_MAX]
>     .......
>     #else
>     .......
>     #endif
>
> taking advantage of the stipulation "For the purposes of this token
> conversion and evaluation, all signed integer types and all unsigned
> integer types act as if they have the same representation as,
> respectively, the types intmax_t and uintmax_t defined in the header
> <stdint.h>." in "6.10.1 Conditional inclusion" .So in the above
> context the C interpretation of SIZE_MAX >= INT_MAX agrees with the
> mathematical interpretation.

First, we don't need the preprocessor rules.  Conversion rules
for integer types guarantee that non-negative values are
unchanged, so any relation such as SIZE_MAX >= LONG_MAX will
always give the same result as the mathematical result.

However, the test is wrong.  If SIZE_MAX > LONG_MAX, then the
conversion rank of size_t must be at least as large as the
conversion rank of long, so the long operand will be converted to
type size_t.  If SIZE_MAX < LONG_MAX, then the conversion rank of
size_t must be less than the conversion rank of long, so the
addition will be done in type long, which could overflow.  The
last case is the interesting one.  If SIZE_MAX == LONG_MAX, then
the conversion rank of size_t may be less than the conversion
rank of long, or it may be greater than or equal to long's
conversion rank.  There is a test that can be done to see which
of these cases hold -- that is, whether overflow is possible --
although the test cannot be done in the preprocessor.  That test
is this:

  (0 ? a+b : -1) < 0 ? "may overflow" : "overflow not possible"

This test works because -1 is converted either to a signed type
or an unsigned type.  If it is converted to a signed type, it
will still be -1, hence less than 0, hence "may overflow".  If it
is converted to an unsigned type, whatever the value is the value
will /not/ be less than 0, hence "overflow not possible".

> But if the 3rd paragraph doesn't apply then for example in a
> situation a+b where a is int with value 1 and b is size_t with value
> SIZE_MAX-2 then both will be converted to unsigned int and then the
> addition will be performed.  So it won't be undefined behaviour but
> the expression won't have the mathematically correct result.  Is my
> analysis correct ?

   1 + (SIZE_MAX-2) == SIZE_MAX-1

I don't see why you think the expression won't have the same
result as the mathematically correct value.  It does.  Are you
talking about different values?

> If yes I find the outcome counterintuitive.  Note
> that if both had been converted to size_t then the expression would
> have the mathematically correct result.
>
> Given the above , I think it would be more useful if the standard
> said
>     The rank of size_t will be greater than the rank of any other
>     unsigned integer type whose greatest value is less or equal than
>     SIZE_MAX .

This rule isn't strong enough to give you the guarantees you
want.  Any should at least guarantee that size_t cannot
promote to int, which this rule does not.

> In the scenarios I can think of , such a stipulation would make it
> easier for programmers to reason about their code , would give more
> intuitive results (according to my intuition anyway) and would give
> no additional burden to implementations since likely they behave
> like this already.

If one is worried about such things, it better just not to use
size_t directly.  For example:

    #if SIZE_MAX > ULONG_MAX
       typedef size_t Size;
    #else
       typedef unsigned long Size;
    #endif

after which just use 'Size' rather than size_t.  As long as other
operands are 'long' or smaller, no overflow is possible.

> All the above inspired a related question : are 2 distinct ranks
> always comparable or is it possible to have ranks R1 and R2 where
> none of the following applies :
>     - R1 is smaller than R2
>     - R2 is smaller than R1
>     - R1 and R2 are equal
>
> ? I'm not sure if it's relevant to anything but it seems complicated
> to examine all combinations of ranks and conversion rules to see if
> it might be relevant so , unless there is a specific situation where
> it would be useful to have ranks which are incomparable , it would
> be better if the standard said that they are always comparable.

We know that integer conversion ranks are fully ordered because
of the provision in 6.2.5 p8:

    For any two integer types with the same signedness and
    different integer conversion rank (see 6.3.1.1), the range
    of values of the type with smaller integer conversion rank
    is a subrange of the values of the other type.

If two types have different integer conversion ranks, then one
conversion rank is smaller than the other.  Done.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

What is the rank of  size_t ? Spiros Bousbouras <spibou@gmail.com> - 2020-05-27 12:49 +0000
  Re: What is the rank of  size_t ? Spiros Bousbouras <spibou@gmail.com> - 2020-05-27 13:54 +0000
    Re: What is the rank of size_t ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-05-27 11:14 -0400
      Re: What is the rank of size_t ? Spiros Bousbouras <spibou@gmail.com> - 2020-05-27 19:03 +0000
        Re: What is the rank of size_t ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-05-27 18:09 -0400
    Re: What is the rank of  size_t ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-05-30 01:54 -0700
  Re: What is the rank of size_t ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-05-27 09:59 -0400
    Re: What is the rank of size_t ? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-05-27 07:37 -0700
      Re: What is the rank of size_t ? James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-05-27 11:02 -0400
    Re: What is the rank of size_t ? Vir Campestris <vir.campestris@invalid.invalid> - 2020-05-27 20:46 +0100
      Re: What is the rank of size_t ? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-05-27 14:30 -0700
  Re: What is the rank of size_t ? Real Troll <real.troll@trolls.com> - 2020-05-28 06:35 -1000
    Re: What is the rank of size_t ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-05-29 20:55 -0700
      Re: What is the rank of size_t ? Real Troll <Real.Troll@trolls.com> - 2020-05-30 08:05 -1000
        Re: What is the rank of size_t ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-05-31 17:33 -0700
          Re: What is the rank of size_t ? Real Troll <real.troll@trolls.com> - 2020-06-01 01:45 -1000
            Re: What is the rank of size_t ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-06-03 11:33 -0700
          Re: What is the rank of size_t ? Ike Naar <ike@otaku.sdf.org> - 2020-06-01 20:51 +0000
            Re: What is the rank of size_t ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-06-03 11:16 -0700
    Re: What is the rank of size_t ? raltbos@xs4all.nl (Richard Bos) - 2020-05-31 09:12 +0000
      Re: What is the rank of size_t ? Real Troll <reasl.troll@trolls.com> - 2020-05-31 01:30 -1000
        Re: What is the rank of size_t ? raltbos@xs4all.nl (Richard Bos) - 2020-06-04 20:40 +0000
          Re: What is the rank of size_t ? Real Troll <real.troll@trolls.com> - 2020-06-04 12:50 -1000
  Re: What is the rank of  size_t ? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-05-30 00:55 -0700
  Re: What is the rank of size_t ? Bonita Montero <Bonita.Montero@gmail.com> - 2020-06-02 10:06 +0200

csiph-web