# recursive types work

Havoc Pennington hp at redhat.com
Wed Dec 29 10:47:51 PST 2004

```Hi,

Thanks for the feedback.

On Wed, 2004-12-29 at 16:48 +0200, Andy Wingo wrote:
> Hm, this is a bit confusing to me on first read. To me, this reads
> better as:
>
>        recurse (ARRAY)
>          recurse (ARRAY)
>            write (BOOL)
>
> I think the only sane way to make this work would be to store the point
> of the first recursion, then for the final unrecurse(), scan the values
> to see what the type signature should be.

The problem is that the second recurse() will create a value, and the
array may be an empty array.

In other words when I do recurse (ARRAY of ARRAY of BOOL) then I now
have an array of array of bool with zero elements. If I then
recurse (ARRAY of BOOL) then I have an array of array of bool with 1
element, which is an empty array of bool. If I then write(BOOL) then I
have an array of array of bool with 1 element, which is an array of bool
with 1 element.

These are the three states as we recurse:
{}
{ {} }
{ { TRUE } }

This is the thing I mentioned about type iterator vs. value iterator,
though there I was talking about reading, the same sort of thing applies
to writing.

The reason arrays cause complexity is that they have a recursive type
signature, but need not have any values, and don't store the type
signature per-value. So they create a split between type and value
iteration that doesn't happen for structs.

Anyway, I think we could make writer_recurse() support what you
describe, but we'd still need the special writer_recurse_array() taking
the full array signature since otherwise you can't do empty arrays.
Hopefully that makes sense.

> How can you detect that the array is finished when you are reading? One
> would assume this condition can be unified with the case of the null
> array.

Right, the reason it can't is that to detect array finished you look at
the array length vs. your position in the array. But if there's no array
value at all there's no array length or position in the array.

Take the three cases with type ARRAY of ARRAY of BOOL:
{}
{ {} }
{ { TRUE } }

The issue is the first case; if you recurse, there's no value to recurse
into.

So we could have a type-only iterator that doesn't look at values, and
even autoconvert the iterator to a type-only iterator if you recurse
into an empty array. To do that we need to change current next() I
guess, since right now you would write:

recurse (ARRAY)
do {
recurse (ARRAY)
} while (next())
unrecurse ()

and that always reads at least one element. So it needs to be one of:

while (next())
{
}

while (!end())
{
next()
}

Those are probably better choices anyway, regardless of this issue.

> Do you want patches for either of these?

Probably too soon, the code is all in flux. Though you are welcome to
play with it. ;-)

Havoc

```