Variable-sized types vs. templates

Variable-sized types vs. templates

[Mark Mitchell]

PR 5661 is a crash that arises when using a VLA as a template parameter.

Of course, VLAs are an extension to ANSI/ISO C++, so we are outside the
scope of the standard.

Here is the test case from the PR:

  template <class T> struct A{ A() throw() {} };

  struct B {
    static const int s;
    A<int[s]> a;
  };

  B b;

We accept "int[s]" thanks to the extension.  When trying to instantiate
A, we crash.

A purer example is:

  template <typename T> struct A { T t; };

  void f (int i) { A<int[i]> a; }

We happen not to crash on this example -- but we certainly do not do
the right thing either.

(Once again, we see the problem with incorporating extensions without
thinking through how they interact with other language features.  This
is likely not the only problem with variably-sized types.  I'll bet that
`typeid' and `dynamic_cast' do not behave sensibly in conjunction with
these types either.  The argument that GNU C (and now ANSI C) have VLAs
is, in my opinion, totally irrelevant; the C folks thought about what
these things mean in C, but nobody has thought through what they mean
in C++.)

However, I assume that nobody is about to let me remove the extension.

Therefore, we need to define a rule that allows us to diagnose the above
cases.  That's not easy.  For example, if T is a VLA type, or a type
containing a VLA, is "A<T>" ok?  What about "A<T*>"?  (Note that the
template body might dereference something of the pointer type.)  What
about "A<void (*)(T**)>"?  What about "A<S*>" where S is a struct
containing a VLA?

I do not fancy having to recursively walk the type tree every time we
instantiate a template; that will make our already slow template
instantiation process even slower.  Neither do I fancy having to keep
a bit on each and every type as we build them; the compiler creates
types in too many places using too many methods to make this easy to
get right.

Brilliant solutions?

-- 
Mark Mitchell                mark@codesourcery.com
CodeSourcery, LLC            http://www.codesourcery.com

Re: Variable-sized types vs. templates

[Nathan Sidwell]

Mark Mitchell wrote:

> is likely not the only problem with variably-sized types.  I'll bet that
> `typeid' and `dynamic_cast' do not behave sensibly in conjunction with
there was a bug report about typeid. IIRC, it now produces a
compile time error - It's just typeid (vla),
and not typeid (contains_vla). I suspect typeid (void (*)(VLA *))
and typeid (VLA *) are not handled gracefully. 

I don't think dynamic_cast has a problem.

> Therefore, we need to define a rule that allows us to diagnose the above
> cases.  That's not easy.  For example, if T is a VLA type, or a type
A<VLA> - compile error
A<VLA*> - compile error
A<contains_VLA> - probably ok.
A<void (*)(VLA**)> error
A<S*> compile error

The problematical ones are those that require the mangling of the
VLA. We either ban that, (with the above implications), or
specify that all VLA's of the same element type are 'the same'

> I do not fancy having to recursively walk the type tree every time we
> instantiate a template; that will make our already slow template
> instantiation process even slower.  Neither do I fancy having to keep
> a bit on each and every type as we build them; the compiler creates
> types in too many places using too many methods to make this easy to
> get right.
Yup, I remember being rather stunned when I discovered that uses_template_parms
did such a walk. How about a set of lazy cache bits along with a valid
bit. If valid is false, we do the walk, filling everything in, and
then set the bit. This is a bigger solution than I'm sure you and I
are happy with.

nathan

-- 
Dr Nathan Sidwell :: Computer Science Department :: Bristol University
           The voices in my head told me to say this
nathan@acm.org  http://www.cs.bris.ac.uk/~nathan/  nathan@cs.bris.ac.uk

Re: Variable-sized types vs. templates

[Jason Merrill]

The restrictions on use of VLAs in C99 seem appropriate here: a pointer to
VLA (and more complex versions of same) is called a variably modified (VM)
type.  Only a parameter or local variable can have VM type.  A VLA cannot
have static storage duration.

Similarly, I think it's appropriate to say that neither VLA nor VM types
are valid template type arguments.  I'd also say that a VLA is not a valid
type for a struct member; I don't understand why C99 seems to allow that.
Perhaps it wants to allow it so that uses in different functions can have
different sizes, but that seems incompatible with the stronger C++ model of
struct types.

Jason

Re: Variable-sized types vs. templates

[Neil Booth]

Jason Merrill wrote:-

> The restrictions on use of VLAs in C99 seem appropriate here: a pointer to
> VLA (and more complex versions of same) is called a variably modified (VM)
> type.  Only a parameter or local variable can have VM type.  A VLA cannot
> have static storage duration.
> 
> Similarly, I think it's appropriate to say that neither VLA nor VM types
> are valid template type arguments.  I'd also say that a VLA is not a valid
> type for a struct member; I don't understand why C99 seems to allow that.
> Perhaps it wants to allow it so that uses in different functions can have
> different sizes, but that seems incompatible with the stronger C++ model of
> struct types.

I think they wanted to formalize hacks like:

/* Chained list of answers to an assertion.  */
struct answer
{
  struct answer *next;
  unsigned int count;
  cpp_token first[1];
};

Where first is an array of size determined at run time.

Neil.

Re: Variable-sized types vs. templates

[Jason Merrill]

On Tue, 8 Oct 2002 13:35:41 +0100, Neil Booth <neil@daikokuya.co.uk> wrote:

> Jason Merrill wrote:-
>
>> Similarly, I think it's appropriate to say that neither VLA nor VM types
>> are valid template type arguments.  I'd also say that a VLA is not a valid
>> type for a struct member; I don't understand why C99 seems to allow that.
>> Perhaps it wants to allow it so that uses in different functions can have
>> different sizes, but that seems incompatible with the stronger C++ model of
>> struct types.

> I think they wanted to formalize hacks like:
>
> /* Chained list of answers to an assertion.  */
> struct answer
> {
>   struct answer *next;
>   unsigned int count;
>   cpp_token first[1];
> };
>
> Where first is an array of size determined at run time.

But first isn't a VLA.  To actually use a VLA in a struct would mean an
example like

  int foo_length;
  struct foo
  {
    int arr[foo_length];
  };

  void f ()
  {
    foo_length = 42;
    {
      foo bar;
      bar.arr[12] = 24;
    }
  }

which seems rather more ugly than the 'struct hack' you refer to.  And,
since it can only be used for local variables, rather useless.  Now that I
think of it, this is probably more what they had in mind:

  void f (int n)
  {
    struct foo { ...; int arr[n]; } bar;
  }

So, to refine my earlier suggestion, in C++ I'd prohibit VLAs in types with
linkage.  A local class such as this is already an invalid template type
parm.

Jason

Re: Variable-sized types vs. templates

[Richard Earnshaw]

> On Tue, 8 Oct 2002 13:35:41 +0100, Neil Booth <neil@daikokuya.co.uk> wrote:
> 
> > Jason Merrill wrote:-
> >
> >> Similarly, I think it's appropriate to say that neither VLA nor VM types
> >> are valid template type arguments.  I'd also say that a VLA is not a valid
> >> type for a struct member; I don't understand why C99 seems to allow that.
> >> Perhaps it wants to allow it so that uses in different functions can have
> >> different sizes, but that seems incompatible with the stronger C++ model of
> >> struct types.
> 
> > I think they wanted to formalize hacks like:
> >
> > /* Chained list of answers to an assertion.  */
> > struct answer
> > {
> >   struct answer *next;
> >   unsigned int count;
> >   cpp_token first[1];
> > };
> >
> > Where first is an array of size determined at run time.
> 
> But first isn't a VLA.  To actually use a VLA in a struct would mean an
> example like
> 
>   int foo_length;
>   struct foo
>   {
>     int arr[foo_length];
>   };
> 
>   void f ()
>   {
>     foo_length = 42;
>     {
>       foo bar;
>       bar.arr[12] = 24;
>     }
>   }

Except, of course, that c99 says that only an "ordinary indentifier" may 
be a VLA.  So you can't have a VLA inside a struct and be conforming.

R.

Re: Variable-sized types vs. templates

[Jason Merrill]

On Tue, 08 Oct 2002 14:03:36 +0100, Richard Earnshaw <rearnsha@arm.com> wrote:

> Except, of course, that c99 says that only an "ordinary indentifier" may 
> be a VLA.

I don't see that.  It says that only an ordinary identifier can have a VM
type, but seems to specifically avoid saying the same thing about VLAs.

Jason

Re: Variable-sized types vs. templates

[Andreas Schwab]

Neil Booth <neil@daikokuya.co.uk> writes:

|> I think they wanted to formalize hacks like:
|> 
|> /* Chained list of answers to an assertion.  */
|> struct answer
|> {
|>   struct answer *next;
|>   unsigned int count;
|>   cpp_token first[1];
|> };

For this you'd use a flexible array member, which is something different.

struct answer
{
  struct answer *next;
  unsigned int count;
  cpp_token first[];
};

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux AG, Deutschherrnstr. 15-19, D-90429 Nürnberg
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: Variable-sized types vs. templates

[Richard Earnshaw]

> On Tue, 08 Oct 2002 14:03:36 +0100, Richard Earnshaw <rearnsha@arm.com> wrote:
> 
> > Except, of course, that c99 says that only an "ordinary indentifier" may 
> > be a VLA.
> 
> I don't see that.  It says that only an ordinary identifier can have a VM
> type, but seems to specifically avoid saying the same thing about VLAs.
> 
> Jason

But 6.7.5 para 3 says that a VLA has VM type.  And in example 4 in 6.7.5.2 
para 10 shows that z[n] is not valid as a struct member.

R.

Re: Variable-sized types vs. templates

[Jim Wilson]

You are confusing ISO C99 variable length arrays (VLA) with GNU C dynamic
arrays.  These are related but distincly different features.  GNU C dynamic
arrays predate ISO C99 VLAs by almost 10 years, and it is the dynamic array
support in the C++ front end that is causing problems.

A key difference between the two is that GNU C dynamic arrays can exist inside
a structure, and VLAs can not.  This means GNU C has variable sized types,
but ISO C99 does not.  Variable sized types complicates things like argument
passing, so it is understandable that ISO C99 left this out.  I can also see
that it complicates stuff like template instantiation, so it would make sense
to leave this out of the C++ language also.

Since dynamic arrays have been around for so long, and are used in so many
programs, the C front end needs to continue supporting dynamic arrays in
addition to VLAs.  There seems to be some confusion here though.  I just
tried writing a simple testcase using a dynamic array that wasn't a valid VLA
and gcc accepted it with -std=c99 -pedantic.  I'm sure this will eventually
be sorted out.

Meanwhile, there probably isn't a lot of need to have dynamic array support
in the C++ front end.  You should support VLAs if at all possible, but you
don't really need dynamic arrays support.  There may be old programs that rely
on dynamic arrays, so you probably should phase this stuff out slowly.  If
a dynamic array is used in a context where it can't possibly work, then give
an error.  if a dynamic array is used in a context where it can work, then
you should continue to support it, but it would be OK to give an "obsolete
feature" warning, and then delete the feature in a future release.

Actually, I just noticed that someone changed the documentation in the
extend.texi file to use the term VLA instead of dynamic array.  I think that
was a mistake, since VLA and dynamic array are not the same thing.

Also, note that Ada has variable sized types, so the GNU C dynamic array
feature has some use for testing features needed for Ada language support.

Jim

Re: Variable-sized types vs. templates

[Richard Earnshaw]

> Since dynamic arrays have been around for so long, and are used in so many
> programs, the C front end needs to continue supporting dynamic arrays in
> addition to VLAs.  There seems to be some confusion here though.  I just
> tried writing a simple testcase using a dynamic array that wasn't a valid VLA
> and gcc accepted it with -std=c99 -pedantic.  I'm sure this will eventually
> be sorted out.

PR 7948

R.

Re: Variable-sized types vs. templates

[Jim Wilson]

>A key difference between the two is that GNU C dynamic arrays can exist inside
>a structure, and VLAs can not.  This means GNU C has variable sized types,
>but ISO C99 does not.  Variable sized types complicates things like argument
>passing, so it is understandable that ISO C99 left this out.  I can also see
>that it complicates stuff like template instantiation, so it would make sense
>to leave this out of the C++ language also.

I was a little too hasty here.  ISO C99 has VLAs, and VLAs are obviously
variable sized types.  What I meant to say was that ISO C99 can never have
an argument with a variable sized type.  Arrays decay to pointers when used
as arguments, and VLAs aren't allowed inside structures, so there is no way
to get a variable sized argument in ISO C99.  There isn't any other place in C
where variable sized types are a problem.  There are other places in C++, but
the VLA rules may be enough to avoid all problems.

GNU C dynamic arrays can be used to create variable sized arguments.  The
Ada language can also have variable sized arguments, and the GNU C dynamic
arrays feature can be useful for testing support needed for Ada.

Jim

Re: Variable-sized types vs. templates

[Jason Merrill]

On Tue, 08 Oct 2002 15:29:19 +0100, Richard Earnshaw <rearnsha@arm.com> wrote:

>> On Tue, 08 Oct 2002 14:03:36 +0100, Richard Earnshaw <rearnsha@arm.com> wrote:
>> 
>> > Except, of course, that c99 says that only an "ordinary indentifier" may 
>> > be a VLA.
>> 
>> I don't see that.  It says that only an ordinary identifier can have a VM
>> type, but seems to specifically avoid saying the same thing about VLAs.

> But 6.7.5 para 3 says that a VLA has VM type.

Sure, OK.  I was assuming that only types which were not themselves VLA
types could be VM types, but the text doesn't support that.

Jason