How to represent recursive types

[phadej]

Consider

struct linked_list_s {
  int head;
  struct linked_list_s *tail;
};

our current data types we could represent that as:

Struct
    { structTag    = "linked_list_s"
    , structFields =
        [ StructField "head" offset_head (TypPrim (PrimInt Signed))
        , StructField "tail" offset_tail (TypPointer (TypStruct ???))
    }

with ??? tying back.

Infinite data is a bit tricky (e.g. tree-diff derived instances won't work out of a box), but they feel nice.

There are various alternatives:

• Stop at the first recursive occurence
• Stop immediately at the first named struct/typedef/etc. (this would require keeping symbol table)

[edsko]

I think a symbol table is the way to go; we anyway want to say "this is that named struct".

[edsko]

("Anyway" because, for example, if we see the same struct declared twice, we should export it only once, where "the same" means "has the same tag").

[phadej]

The symbol table approach is not unambiguous, what about anonymous records (see also #173)

struct foo {
   struct {
     int a;
     int b;
   } inner;
};

How to represent inner? Should we create a dummy data, like

data Foo_inner = Foo_inner { a :: CInt, b :: CInt }

(and put it into a symbol table with some unique name, as we'd probably rather traverse symbol table to generate data-types?)

or should we have some anonymous representation (say large-anon) for anonymous structs?

[edsko]

I think we probably don't want the complexity of true anonymous records (large-anon or otherwise)? So I guess yes, dummy name, but since it cannot be referred to elsewhere in the C header, it doesn't need to be added to the symbol table?

[phadej]

FWIW, apparently

struct foo {
   struct bar {
     int a;
     int b;
   } inner;
};

int main () {
  struct bar x = { 1, 2 };
  return x.a;
}

is valid C (at least gcc doesn't warn about anything.

[phadej]

it doesn't need to be added to the symbol table?

As I said, it makes sense to add all types to the symbol table. So one could traverse symbol table to translate types.

[edsko]

Fair enough.