recursive types work

[Andy Wingo]

Hi,

On Wed, 29 Dec 2004, Havoc Pennington wrote:

> On Wed, 2004-12-29 at 16:48 +0200, Andy Wingo wrote:
> >        recurse (ARRAY)
> >          recurse (ARRAY)
> >            write (BOOL)
> 
> The problem is that the second recurse() will create a value, and the
> array may be an empty array.

Right, which is why I was suggesting the end-of-array internal "nil"
value, so that calling unrecurse() will append this special value.
That's what would allow you to recurse into an empty list: you'd see the
nil value and know that's the end of the list, regardless of whether
there were 10 or 0 elements before that.

Not that nil should be exposed in the api as such. The user would see it
as a false return value from read().

Also, this nil value has nothing to do with the old DBUS_TYPE_NIL,
rather being more analogous to the NULL at the end of a GList, or a lisp
nil.

Let A and B be the typecodes for arrays and booleans. Let N be the
typecode for our new "nil", which requires no value. Let 1 be the true
value. In the message writing states below, you'd have:

 code              state                   message
 ----              -----                   -------
 recurse(ARRAY)    {}                      A
 recurse(ARRAY)    { {} }                  AA
 write(Bool, true) { { TRUE } }            AAB1
 unrecurse()       { { TRUE nil } }        AAB1N
 unrecurse()       { { TRUE nil} nil }     AAB1NN

After the last unrecurse, the array would be scanned for its type
signature, array of array of boolean. If two values in the same array
are of different types, it becomes an array of variant. No error
possible.

> 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.

So give them a value ;) I could be confused, but I think the nil solves
this problem.

> 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.

recurse (ARRAY)
do {
  recurse (ARRAY)
  while (read (BOOL, &val)) {
    .. do something with the val ...
    next ()
  }
  unrecurse (ARRAY)
while (next ())
unrecurse (ARRAY)


Am I missing something?

--
Andy Wingo
http://wingolog.org/