Existential Structs for Checked C

[abeln]

Design doc: https://github.com/microsoft/checkedc/wiki/%5BProposal%5D-Add-Existential-Structs-to-CheckedC

[abeln]

TODOs from the PR: #683
Alternatively can grep the code for TODOs mentioning "checkedc issue #661"

• Add support for pack expressions in StmtProfile.cpp
• Better printing of pack expressions (maybe) in StmtPrinter.cpp
• Handle existential types in ASTReader/Writer.cpp
• Fix the caching of existentials so it uses FoldingSet (Type.h 4479)

David's comment on this:

I believe you could 'profile' existential types by using:

ID.AddPointer(TypeVar)
ID.AddPointer(InnerType.getAsOpaquePtr()).

This would let you remove the caching code that you've added in ASTContext.cpp, and use FoldingSets as used for other types. You'd have to move the explanatory comment about the unique type objects not necessarily being canonical elsewhere.

• Expand existential types (and pack and unpack expressions) to bind multiple variables at once.
  See proposed syntax in the design doc: https://github.com/microsoft/checkedc/wiki/%5BProposal%5D-Add-Existential-Structs-to-CheckedC#extension-multi-argument-existentials

• Implement serialization and deserialization of generic structs.

[abeln]

Another TODO is to force declarations with an '_Unpack' specifier to be initialized.

e.g. the following code should produce an error

void TestUnpackRequiresExistentialInit() {
  struct Foo _For_any(T) {};
  struct Foo<int> fooInt;
  _Exists(B, struct Foo<B>) fooExist = _Pack(fooInt, _Exists(C, struct Foo<C>), int);
  _Unpack (A) struct Foo<A> fooA; // should raise error here, because fooA is uninitialized
}

Currently, no error is shown and the compiler accepts the code.

[abeln]

Another TODO: #683 (comment)
We need to add a test where we define an ExistentialType in a compilation unit (file), and use it from another one.

[abeln]

TODO: https://github.com/microsoft/checkedc-clang/pull/683/files/766f0683d800b7f89825f2fd0d2e377dadbc6a2e#diff-b29d742a082abe2707cec2d4b6caee64

We need to make sure that we can debug existential types (ditto for type applications).

[abeln]

Assigning back to David for future work.

[abeln]

Here are two additional bugs I found today:

1. The following incorrectly triggers an assertion error

struct Foo _For_any(A) {

};

_For_any(T) _Exists(T, struct Foo<T>) bar(int x) {
}

Assertion failed: !TypeVarInfo && "Already has type variable info!", file C:\cygwin64\home\t-abniet\src\llvm\tools\clang\lib\Sema\DeclSpec.cpp, line 466
0x00007FF6DA7CC1EC (0x0000001700000016 0x0000000000000000 0x00007FF6D6890EE8 0x0000000000000000), HandleAbort() + 0xC bytes(s), c:\cygwin64\home\t-abniet\src\llvm\lib\support\windows\signals.inc, line 409
0x00007FFF5158BBA1 (0x00007FFF00000016 0x00000017EFB8ABA0 0x0000000801000006 0xFFFFFF0100000132), raise() + 0x441 bytes(s)
0x00007FFF5158D7F9 (0x00000017EFB8ABA0 0x0000000000000240 0x00007FFF51688D10 0x00007FF6E428A990), abort() + 0x39 bytes(s)
0x00007FFF51593425 (0x00007FF6E428A990 0x00007FF6E428A900 0xCCCCCCCC000001D2 0xCCCCCCCCCCCCCCCC), _get_wide_winmain_command_line() + 0x2515 bytes(s)
0x00007FFF51592F97 (0x00007FF6E428A990 0x00007FF6E428A900 0xCCCCCCCC000001D2 0xCCCCCCCCCCCCCCCC), _get_wide_winmain_command_line() + 0x2087 bytes(s)
0x00007FFF51591001 (0x00007FF6E428A990 0x00007FF6E428A900 0x00000000000001D2 0x00007FF6DE714D3F), _get_wide_winmain_command_line() + 0xF1 bytes(s)
0x00007FFF5159398F (0x00007FF6E428A990 0x00007FF6E428A900 0xCCCCCCCC000001D2 0xCCCCCCCCCCCCCCCC), _wassert() + 0x2F bytes(s)
0x00007FF6DE714D3F (0x00000017EFB8BF20 0x00000185A86B3CD0 0x00000017EFB8B350 0x0000001700000001), clang::DeclSpec::setTypeVars() + 0x5F bytes(s), c:\cygwin64\home\t-abniet\src\llvm\tools\clang\lib\sema\declspec.cpp, line 466 + 0x32 byte(s)
0x00007FF6DE271F32 (0x00000185A8E068B0 0x00000017EFB8BF20 0xCCCCCCCCCCCCCCCC 0xCCCCCCCCCCCCCCCC), clang::Parser::ParseExistentialTypeSpecifierHelper() + 0x512 bytes(s), c:\cygwin64\home\t-abniet\src\llvm\tools\clang\lib\parse\parsedecl.cpp, line 7573
0x00007FF6DE271445 (0x00000185A8E068B0 0x00000017EFB8BF20 0x00000017EFB8B528 0x00000017EFB8B544), clang::Parser::ParseExistentialTypeSpecifier() + 0x85 bytes(s), c:\cygwin64\home\t-abniet\src\llvm\tools\clang\lib\parse\parsedecl.cpp, line 7424
0x00007FF6DE2636D4 (0x00000185A8E068B0 0x00000017EFB8BF20 0x00000017EFB8BE20 0xCCCCCCCC00000003), clang::Parser::ParseDeclarationSpecifiers() + 0x34F4 bytes(s), c:\cygwin64\home\t-abniet\src\llvm\tools\clang\lib\parse\parsedecl.cpp, line 3895
0x00007FF6DE216A72 (0x00000185A8E068B0 0x00000017EFB8C648 0x00000017EFB8C5D8 0x00000017EFB8BF20), clang::Parser::ParseDeclOrFunctionDefInternal()

The problem is that as we're parsing the specifier for the existential, we try to store the type variable name (T) in the DeclSpec. However, we've already stored a type variable in the same DeclSpec, because of the for_any. That triggers the assertion.

The solution is simple: we need to store the "existential" and "generic" type variables separately in the DeclSpec. The assertion will no longer trigger then.

[abeln]

2. This code is type-correct but produces a compilation error

struct Foo _For_any(A, B) {

};

_For_any(T) void bar(int x) {
	_Exists(A, struct Foo<A, T>) fooExists;
	_Unpack (B) struct Foo<B, T> fooUnpack = fooExists;
}

hello.c:54:31: error: initializing 'struct Foo<A, T>' with an expression of incompatible type 'struct Foo<(0, 0), B>'
        _Unpack (B) struct Foo<B, T> fooUnpack = fooExists;

The problem here is that if we look at the definition of SubstituteTypeArgs, we can see that we always substitute for the 0-depth variable:

QualType Sema::SubstituteTypeArgs(QualType QT, ArrayRef<TypeArgument> TypeArgs) {
   if (QT.isNull())
     return QT;

   // Transform the type and strip off the quantifier.
   TypeApplication TypeApp(*this, TypeArgs, 0 /* Depth */);

In this case, however, we want to substitute for the variable at level 1.
In general, whenever we see

_Unpack (A) struct Foo<...> = foo

for needs to have an existential type _Exists(T, ...), and we need to substitute A for T at whatever level T has.

[abeln]

Once the two bugs above are fixed, we should as a test the Closures example from the doc: https://github.com/microsoft/checkedc/wiki/%5BProposal%5D-Add-Existential-Structs-to-CheckedC#example-2-closures

[abeln]

Here are two other work items:

1. We should make sure that values with existential types are initialized (either via assignment to another existential or through _Pack).
2. Similarly, we must enforce that _Unpack declarations are initialized.

Otherwise we can end up re-introducing type confusion errors/null pointer de-references.