34

I would like to fully understand type hierarchy of the C11 language and present it graphically (a tree diagram would be perfect). The standard does not provide any figure for this issue – there are 30 points describing individual types and relations between them. I'd like to draw it.

My attempt started from obtaining the ISO/IEC 9899:201x Committee Draft N1570 and extracting all the essential statements from section 6.2.5 of the document. Then, I started to rearrange the knowledge in a form of a tree. Let me present my work in two steps.

Step 1: points 1–15

The extracted knowledge (point within section 6.2.5 + specified production):

  • 1 types = object types + function types;
  • 4 standard signed integer types = signed char, short int, int, long int, long long int;
  • 4 signed integer types = standard signed integer types + extended signed integer types;
  • 6 standard unsigned integer types = _Bool, unsigned char, unsigned short int, unsigned int, unsigned long int, unsigned long long int;
  • 6 unsigned integer types = standard unsigned integer types + extended unsigned integer types;
  • 7 standard integer types = standard signed integer types + standard unsigned integer types;
  • 7 extended integer types = extended signed integer types + extended unsigned integer types;
  • 10 real floating types = float, double, long double;
  • 11 complex types = float _Complex, double _Complex, long double _Complex;
  • 12 floating types = real floating types + complex types;
  • 14 basic types = char + signed integer types + unsigned integer types + floating types;
  • 15 character types = char, signed char, unsigned char.

And the resulting structure:

types
    object types
    function types
basic types
    char
    sίgned integer types
        standard sίgned integer types
            signed char, short int, int, long int, long long int
        extended sίgned integer types
    unsίgned integer types
        standard unsίgned integer types
            _Bool, unsigned char, unsigned short int, unsigned int,
            unsigned long int, unsigned long long int
        extended unsίgned integer types
    floating types
        real floating types
            float, double, long double
        complex types
            float _Complex, double _Complex, long double _Complex
standard integer types
    standard sίgned integer types
    standard unsίgned integer types
extended integer types
    extended sίgned integer types
    extended unsίgned integer types
character types
    char, signed char, unsigned char

Step 2: points 16–24

The remaining statements:

  • 16 enumerated types;
  • 17 integer types = char + signed integer types + unsigned integer types + enumerated types;
  • 17 real types = integer types + real floating types;
  • 18 arithmetic types = integer types + floating types;
  • 20 derived types = array types, structure types, union types, function types, pointer types, atomic types;
  • 21 scalar types = arithmetic types + pointer types;
  • 21 aggregate types = array types + structure types;
  • 24 derived declarator types = array types + function types + pointer types.

And the final C11 type system structure:

types
    object types
    function types
basic types
    char
    sίgned integer types
        standard sίgned integer types
            signed char, short int, int, long int, long long int
        extended sίgned integer types
    unsίgned integer types
        standard unsίgned integer types
            _Bool, unsigned char, unsigned short int, unsigned int,
            unsigned long int, unsigned long long int
        extended unsίgned integer types
    floating types
        real floating types
            float, double, long double
        complex types
            float _Complex, double _Complex, long double _Complex
standard integer types
    standard sίgned integer types
    standard unsίgned integer types
extended integer types
    extended sίgned integer types
    extended unsίgned integer types
character types
    char, signed char, unsigned char
real types
    integer types
        char
        sίgned integer types
            standard sίgned integer types
                signed char, short int, int, long int, long long int
            extended sίgned integer types
        unsίgned integer types
            standard unsίgned integer types
                _Bool, unsigned char, unsigned short int, unsigned int,
                unsigned long int, unsigned long long int
            extended unsίgned integer types
        enumeration  types
    real floating types
        float, double, long double
scalar types
    arithmetic types
        integer types
            char
            sίgned integer types
                standard sίgned integer types
                    signed char, short int, int, long int, long long int
                extended sίgned integer types
            unsίgned integer types
                standard unsίgned integer types
                    _Bool, unsigned char, unsigned short int, unsigned int,
                    unsigned long int, unsigned long long int
                extended unsίgned integer types
            enumeration  types
        floating types
            real floating types
                float, double, long double
            complex types
                float _Complex, double _Complex, long double _Complex
    pointer types
derived types
    array types
    structure types
    unίon types
    function types
    pointer types
    atomic types
aggregate types
    array type
    structure type
derived declarator types
    array type
    structure type
    pointer type

Now I need to reduce the structure (ideally to a single tree) or find a more tricky way to represent the relations. I would like to came out with a nice cheet-sheet for the C11 typing system. Any ideas?

Krzysztof Abramowicz
  • 1,556
  • 1
  • 12
  • 30
  • 1
    The basic types etc are all object types. You don't seem to be treating them as a sub-type of the object types. You also have a number of the types appearing at multiple points in your diagram. – Jonathan Leffler Dec 08 '13 at 01:47
  • 1
    Is `wchar_t` applicable here? C11 3.7.3 – chux - Reinstate Monica Dec 08 '13 at 02:32
  • Your representation of the integer type hierarchy is not accurate. You can't omit the "prefix" *standard* because C11 distinguishes between *standard integer types* and *integer types*. The later puts together `char` the *standard integer types* (eventual extensions) and enumeration types. This category is an important one, those are the types used for indexing and that can lead to compile time constant expressions. – Jens Gustedt Dec 08 '13 at 08:24
  • @chux, no `wchar_t` is not a proper type but just an alias (`typedef`). – Jens Gustedt Dec 08 '13 at 08:25
  • @JonathanLeffler, I built the hierarchy exclusively on the basis of the knowledge from section 6.2.5 of the standard – there is no statement regarding further sub-typing of _object types_. This doesn't change the fact that you are right, of course. The same holds for the redundant definitions – it's a raw knowledge transformation which has to be optimised. I will consider adding a third step for that purpose. – Krzysztof Abramowicz Dec 08 '13 at 15:45
  • @JensGustedt, According to N1570 6.2.5: 4 _standard signed integer types_ + _extended signed integer types_ = _signed integer types_, 6 _standard unsigned integer types_ + _extended unsigned integer types_ = _unsigned integer types_, 7 _standard signed integer types_ + _standard unsigned integer types_ = _standard integer types_. **The word "standard" does not appear after point 7**. So, ignoring the extended types (I'm interested in the pure standard only), points 4 and 6 just discard the word "standard", while point 7 is not important. Does ISO/EIC 9899:2011 differ from this? – Krzysztof Abramowicz Dec 08 '13 at 16:32
  • 1
    @KrzysztofAbramowicz, you are missing my point. The term "integer type" occurs afterwards as such, and omitting "standard" from "standard integer types" thus clashes the names of the two terms. The term "integer type" by itself is a very important one in the standard, and its concept is not even represented here, yet. – Jens Gustedt Dec 08 '13 at 17:32
  • @JensGustedt, You are right. I wanted to simplify the _basic types_ sub-tree, but unwittingly, I caused the name clash which led to my misinterpretation of point 7. Optimisation should always be the last step... not only in programming :-) I've applied your remark to the question. Thanks! – Krzysztof Abramowicz Dec 09 '13 at 00:06
  • @JonathanLeffler, I've extended the question: the third step summarizes my effort to account for your remarks. Thank you! – Krzysztof Abramowicz Dec 11 '13 at 19:00
  • 1
    Dear Super Users and Moderators, The question has grown horribly long – too long for this format, but it is not too broad. I am almost ready to give it an answer – it will consist of a single diagram and one paragraph of text and will replace the "step 3" section of the question. As result: 1. the question will be much shorter, 2. it will be answered. So, please reopen my question and give me a chance to complete this thread – at least 10 people are waiting for it. – Krzysztof Abramowicz Dec 11 '13 at 22:31
  • It is reopened, pro tem. I'm hoping to find time to review it and the standard, but I'm not confident I can do it in a timely manner. – Jonathan Leffler Dec 11 '13 at 23:03
  • @JensGustedt, How should I actually represent the concept of _integer type_? Is it shown in my answer proposal? – Krzysztof Abramowicz Dec 16 '13 at 22:19
  • 1
    @KrzysztofAbramowicz, nice diagram. As off your remark about `_Atomic`, this is not completely correct. It can appear as two different meanings that in addition are very close to each other: as a qualifier, and therefore you should list it with the other qualifiers, and as a type *specifier*. The later is the one with the `()` and only with that one the corresponding atomic type is viewed as a derived type, as bizarre as that may sound. – Jens Gustedt Dec 16 '13 at 23:23
  • @JensGustedt, thanks!. A have applied your remark to the answer. Although reading the section in detail several times, I missed that subtle, yet significant detail. – Krzysztof Abramowicz Dec 17 '13 at 17:27

1 Answers1

16

The cluttered structure of C11 types resulting from the second step of the question can be simplified by removal/reduction of less important nodes and delegating some redundant/subsidiary information to be presented by other means.

I propose the following five-step algorithm for that:

  1. Removal of all extended integer types (strictly conforming implementation assumed);
  2. Reduction of the standard integer types (as they do not partition types any more);
  3. Grouping the structure:
    1. A scalar types vs aggregate types pair of sub-trees (represented as a tree),
    2. A basic types vs derived types pair of sub-trees (represented by coloured regions),
    3. real types and derived declarator types (represented as stroked sub-regions of these),
    4. character types (represented with different text colour);
  4. Application of an off-standard production: object types = scalar types + aggregate types;
  5. Supplementing the object types of missing union types and atomic types.

The resulting C11 type system summary looks as follows:

C11 type hierarchy

The grey stroke/areas are introduced to increase readability of the tree.

The type summary does not include the concept of "type declaration completeness" because it is a state, observed at a particular point within a translation unit. At run-time, all objects and functions are instances of a complete type. The void type is an exception but, as a no-type (or any-type in case of a pointer), it is intentionally excluded from the diagram.

The const, volatile, restrict and _Atomic are type qualifiers which, contrary to type specifiers for the derived types, cannot be applied recursively. Any combination of these may prepend any type definition (as long as it makes sense). Thus, including them in the diagram would complicate it, while not introducing any suitable information. The apparent exception makes the _Atomic (type) construct, which is taken into account as being a type specifier for the atomic type – one of the derived types listed in the C11 standard.

Krzysztof Abramowicz
  • 1,556
  • 1
  • 12
  • 30