Part 1
While C itself is obviously a language of types, it lacks the reflection capabilities of many higher level languages. This means that when designing modular, extensible systems, especially those that may interface across language boundaries, facilities for things like marshaling are effectively an exercise left to the reader (at least, marshaling in a uniform, automated fashion).
Motivation
So why bother with making a more featureful type system at all? Unfortunately, relative to more modern languages, C has very few batteries included. While it does have a conventional type system, it is one that has many sharp edges: types are not always uniform in terms of size between platforms, and relative to other systems languages, C's type system is very loose.
Additionally, things like managing object lifecycle and allocation are very much both system specific (how to allocate memory varies by operating environment). This can be a benefit to a degree, as environments which need to support multiple allocation strategies (e.g., OS kernels) can make the segregation between APIs very explicit, but it also means that managing deallocation in those environments can be complex: you must know how to free whatever memory you have allocated, and what heap it is in. There are also subtle, unmanaged-language specific bugs that can manifest, and either cause undesired behavior, or can manifest as major security issues. For example, I have encountered marshaling frameworks that treat every value internally as a fixed-width, signed number, which causes bad behavior when going from, say C or C++, across the network, and into a language that has no inherent concept of unsigned values, such as Python or Javascript. This has obvious implications in the other direction, too - signed values that are around four bytes may become very, very, large unsigned values in unmanaged code, when demarshaled.
Finally, all of this becomes more complex when considering complex, modular systems that must run in a distributed fashion. This sort of paradigm is challenging to manage without adding some abstraction layers, as basic activities like sharing objects between disparate, dynamically-loaded modules in a process, or marshaling/demarshaling across process (and system) boundaries will require a great deal of boilerplate, and may be error prone. Creating a more nuanced type system helps to alleviate these issues, and provide a unified set of tools to operate across these systems in a homogeneous manner.
Design Considerations
As an older language, C is certainly less featureful than more modern systems languages like C++ or Rust. This means that facilities for managing things like copy versus move semantics, lifetime maintenance, and strong typing are really mostly left as implementation details.
From this perspective, we need several things up front:
- A way to annotate object lifecycle to users.
- A basic system of types, that will allow us to gain some insights dynamically.
- A basic set of collection systems that we can use to manage passing data from one place to another.
- Some ability to provide a common interface for managing complex, user-defined types.
Implementing Conventions
As a first step, we will start our journey with the establishment of a simple set of conventions, created through a header. From an implementation perspective, there are really two paths to create a system like this: Duplication, or erasure. Languages like C++ or Rust tend to do the former - C++ templates will generate copies of code to interface with specialized types, where languages with more robust reflection facilities often (though not always) prefer erasure - this can be seen with Java, for example, where types get boxed into an Object (or appropriate generic type) to be stored, referenced, and managed by a common set of code.
For our implementation, we will be doing something relatively similar to erasure - while there are some extensible type systems in C that perform copy operations, they tend to rely on C's macro system fairly heavily, and can be difficult to debug and reason about. From an implementation perspective, we will leverage a tagged union as the mechanism to accomplish this. As we begin defining our "Type System" (which we will annotate with Ts* for short), we will start by setting up some basic, unified types in our header file (which we will assume from here on out to be ts_defs.h):
#pragma once
#include <stdint.h>
// This will serve as a general error-handling
// type. We will start with five cases:
// Success, Allocation Failure, bad arguments, "empty", and Generic Failure.
typedef enum TsStatus_ {
TsSuccess,
TsOutOfMemory,
TsInvalid,
TsEmpty,
TsFailure,
} TsStatus;
typedef enum TsType_ {
Ts_null = -1, // No type assigned - a sentinel value
Ts_int, // Signed integer
Ts_uint, // Unsigned integer
Ts_float, // Floating point value
Ts_bool, // Boolean value
} TsType;
// The basic layout of our structure
// with the type annotation and
// union of primitive types.
typedef struct ts_var_ {
TsType type;
union {
int64_t ts_int;
uint64_t ts_uint;
double ts_float;
uint8_t ts_bool;
} u;
} ts_var;
// Since C has no concept of lifetime,
// we will add some "hints" we can use
// to decorate our API, so users will
// get a sense of semantics. If we want
// to get really clever, this will also
// let us write some compiler tooling
// around this.
#define __ts_move__
#define __ts_copy__
#define __ts_ref__
#define ts_init(v) do { (v)->type = Ts_null; (v)->u.ts_uint = 0; } while(0)
#define ts_init_primitive(v, tp, value) do {\
(v)->type = Ts_ ## tp; (v)->u.ts_ ## tp = value;\
} while(0)
Which means that we can start off our shiny new type system with use cases like the following:
#include <stdio.h>
#include "ts_defs.h"
int main(int argc, char** argv)
{
ts_var tmp = {Ts_null};
ts_init_primitive(&tmp, uint, 0x1000);
printf("Initialized to: %d -> %d\n", tmp.type, tmp.u.ts_uint);
return 0;
}
Which should print out: Initialized to: 1 -> 4096.
Starting on Complex Types
While what we have now is a great start, it isn't quite where we need to be: a more modern set of collections. We'll start this journey with a very simple, easy-to-reason about structure: a linked list. We will now update our type system definitions as follows:
typedef enum TsType_ {
Ts_null = -1, // No type assigned - a sentinel value
Ts_int, // Signed integer
Ts_uint, // Unsigned integer
Ts_float, // Floating point value
Ts_bool, // Boolean value
Ts_list, // A linked list of values
} TsType;
// The basic layout of our structure
// with the type annotation and
// union of primitive types.
typedef struct ts_var_ {
TsType type;
union {
int64_t ts_int;
uint64_t ts_uint;
double ts_float;
uint8_t ts_bool;
void* ts_p;
} u;
} ts_var;
// ...
TsStatus ts_init_list(ts_var* v);
TsStatus ts_free_list(ts_var* v);
Now we have some slightly more complex operations that need to happen, which we can't really inline in our header file anymore. At this point, we'll start work in ts_defs.c:
#include <stdlib.h>
#include "ts_defs.h"
#define allocate(x) malloc(x)
#define deallocate(x) free(x)
// The basic linked-list structure - it is forward
// defined (as it is a recursive structure)
typedef struct list_entry_ list_entry;
struct list_entry_ {
list_entry* next;
list_entry* prev;
};
// This is the fundamental unit of our list.
// It will be where our actual values are stored.
typedef struct list_bucket_ {
list_entry entry;
ts_var value;
} list_bucket;
// This will be the list of values we keep, along with a count.
typedef struct ts_list_ {
uint32_t count;
list_entry head;
} ts_list;
// Initialize the list structure
static void init_list(ts_list* l)
{
l->count = 0;
l->head.next = &l->head;
l->head.prev = &l->head;
}
TsStatus ts_init_list(ts_var* v)
{
TsStatus status = TsSuccess;
ts_list* l = NULL;
// Invalid argument presented
if(NULL == v)
return TsInvalid;
// Return an error - allocation failed
if(NULL == (l = (ts_list*)allocate(sizeof(*l)))) {
status = TsOutOfMemory;
goto cleanup;
}
// Initialize the values in the list
init_list(l);
v->u.ts_p = l;
v->type = Ts_list;
cleanup:
return status;
}
TsStatus ts_free_list(ts_var* v)
{
if(NULL == v || v->type != Ts_list || NULL == v->u.ts_p)
return TsInvalid;
// we will need to do more work here soon, but we will start with this!
deallocate(v->u.ts_p);
// Set the variable back to NULL
ts_init(v);
return TsSuccess;
}
Note that we #define aliases for our allocation/deallocation functions - this (naively) enables us to set some conditionals around them in the future for more exotic environments - if we were to (for example) add Linux kernel support, we would then be able to add in an #ifdef block with allocate aliased to kmalloc/kfree. Similarly, we could specialize in Windows to HeapAlloc/HeapFree in user land (to specify which heap we're using), and ExAllocatePoolWithTag/ExFreePoolWithTag or similar in the kernel. If desired, we could certainly build a whole abstraction layer around allocation to make the system more flexible and extensible (and perhaps, support multiple allocation paradigms), but it is kept simple for illustration purposes here.
Now this is a good start - we have an internal set of structures by which we can manage our list, and some tools to do setup/initialization. We're clearly missing some pieces here, however - we have no way to add or remove elements, and also no way to walk the list to perform operations. So now we'll add in some logic to do those things - back in our header file, we will add some new method definitions:
// What should we do? Keep the current list element
// we are looking at and continue, or remove it and continue?
// Stop and keep, or stop and remove?
typedef enum TsWalkAction_ {
TsContinueKeep,
TsContinueRemove,
TsStopKeep,
TsStopRemove,
} TsWalkAction;
typedef TsWalkAction (*ts_filter_callback)(void* ctx, ts_var* v);
// Push/pop operations - note that the target value will be
// _moved from_ in the first case, and _moved to_ in the second.
TsStatus ts_list_push(ts_var* list, __ts_move__ ts_var* value);
TsStatus ts_list_pop(ts_var* list, __ts_move__ ts_var* value);
// Walk
TsStatus ts_list_walk(ts_var* list, ts_filter_callback cb, void* ctx);
This gives us some basic tools to operate on lists - hopping back over to our implementations, we can begin to fill them out, but first we will start with some helper methods to add and remove elements:
// Helper method to remove a list element via unlinking
static void unlink_list_entry(list_entry* le)
{
// We take the blink (back link) from the next
// element, and point it to the current element's
// predecessor
le->next->prev = le->prev;
// Next, we take the previous element's flink (forward link)
// and point it to our successor
le->prev->next = le->next;
}
// Helper method to insert a new list element
static void add_list_entry(list_entry* head, list_entry* next)
{
// First, we need to set the new element such that:
// - "head"'s flink (forward link, or "next") points to "next"
// - the new element's blink (back link) points to "head"
next->next = head->next;
next->prev = head;
// Now we need to adjust the back link of the element that used to be
// directly after "head" - it needs to now point to the new element.
head->next->prev = next;
// And now, we are ready to set "head"'s flink to the new element.
head->next = next;
}
Now that we've got these helpers defined, we can actually stub out the user-facing code to create a list_bucket, initialize it, and add it into the list (and conversely, copy data out of one with ts_list_pop):
TsStatus ts_list_push(ts_var* list, __ts_move__ ts_var* value)
{
TsStatus status = TsSuccess;
list_bucket* tmp = NULL;
ts_list* l = NULL;
// Basic error checking
if(NULL == list || Ts_list != list->type || NULL == list->u.ts_p)
return TsInvalid;
// Since the value we store in the union is just an opaque
// pointer, we will now cast it to the correct type
l = (ts_list*)list->u.ts_p;
// Now we need to allocate the bucket we will actuall insert
// into the list.
if(NULL == (tmp = (list_bucket*)allocate(sizeof(*tmp)))) {
return TsNoMemory;
}
// Now, since we are inserting "value", we will copy it into the bucket.
memcpy(&tmp->value, value, sizeof(*value));
// As we are emulating move semantics here, we will clear the variable.
// This will help ensure that users can't accidentally use this later
// if we free the underlying list.
ts_init(value);
// Now we will push it onto the list, and increment the count.
add_list_entry(&l->head, &tmp->entry);
l->count++;
return status;
}
TsStatus ts_list_pop(ts_var* list, __ts_move__ ts_var* value)
{
TsStatus status = TsSuccess;
list_bucket* lb = NULL;
ts_list* tsl = NULL;
// Basic error checking
if(NULL == list || Ts_list != list->type || NULL == list->u.ts_p)
return TsInvalid;
// We have no place to put the result!
if(NULL == value)
return TsInvalid;
tsl = (ts_list*)list->u.ts_p;
// Check to see if our list is empty
if(0 == tsl->count)
return TsEmpty;
// We are re-casting
lb = (list_bucket*)tsl->head.next;
// This is a guard to ensure that our list hasn't gotten
// corrupted somehow - that is to say, it has become empty
// but the count is >0.
if(((uintptr_t)lb) == ((uintptr_t)&ts->head))
return TsFailure;
// Remove the entry from our list
unlink_list_entry(&lb->entry);
ts->count--;
// Now, copy the data back to the user and free
// the bucket.
memcpy(value, &lb->value, sizeof(*value));
deallocate(lb);
return status;
}
Now we have two of our three basic primitives: tools to add items to the list, and to remove them from it. Now all we need is to be able to walk the list - this will allow us to perform filter/map/etc. functions on lists. If you recall from above, we started with something resembling the following:
typedef enum TsWalkAction_ {
TsContinueKeep,
TsContinueRemove,
TsStopKeep,
TsStopRemove,
} TsWalkAction;
typedef TsWalkAction (*ts_filter_callback)(void* ctx, ts_var* v);
The basic pattern we will employ here will be to provide the user with an interface to pass in a callback function, as well as an opaque context pointer, and we will walk through each element in the list, calling the user's callback method on each list element. This will allow them to add in their state management for searching/filtering/etc.
Additionally, we've provided an "action" result that the user can return - this will allow them to specify whether we should continue walking through the list or stop, and whether we should remove the current element from the list or keep it. At this point, there is something else we now need to consider: What if our list contains an element with a list in it? This sort of complex behavior is certainly possible, and will only get worse as we add more complex types. At this point, we need to add in some special behavior to handle that sort of case - in our header file we will now define a generic method to clean up values:
TsStatus ts_free_value(ts_var* v);
with a corresponding implementation that looks something like the following:
TsStatus ts_free_value(ts_var* v)
{
TsStatus status = TsSuccess;
if(NULL == v)
return TsInvalid;
switch(v->type) {
case Ts_null:
case Ts_int:
case Ts_uint:
case Ts_float:
case Ts_bool:
ts_init(v);
break;
case Ts_list:
status = ts_free_list(v);
break;
default:
// We've hit an unexpected value!
status = TsFailure;
}
return status;
}
and now we need to update ts_free_list to properly handle embedded lists:
TsStatus ts_free_list(ts_var* v)
{
TsStatus status = TsSuccess;
ts_var tmp = {Ts_null};
if(NULL == v || v->type != Ts_list || NULL == v->u.ts_p)
return TsInvalid;
// We will pop all of the elements from the list, and
// attempt to free each of them. If we fail, we will bail out.
while(TsSuccess == (status = ts_list_pop(v, &tmp))) {
if(TsSuccess != (status = ts_free_value(&tmp)))
goto error;
}
// We expect that we will have gotten `TsEmpty` back
// with the last call to `ts_list_pop`.
if(TsEmpty != status)
goto error;
else
status = TsSuccess;
// Now, our list will be totally empty, and ready to simply
// free.
deallocate(v->u.ts_p);
// Set the variable back to NULL
ts_init(v);
error:
return status;
}
Now we can finally start work on our walk method:
TsStatus ts_list_walk(ts_var* list, ts_filter_callback cb, void* ctx)
{
TsStatus status = TsSuccess;
ts_list* tsl = NULL;
list_entry* current = NULL;
if(NULL == list ||
Ts_list != list->type ||
NULL == list->u.ts_p ||
NULL == cb)
return TsInvalid;
tsl = (ts_list*)list->u.ts_p;
// If the list is empty, there is nothing to do!
if(0 == tsl->count)
return status;
// Get the first entry in the list, after
// the list head.
current = tsl->head.next;
// Now this takes just a bit more explanation:
// We will continue iterating through the list until
// we get back to the list head.
while(((uintptr_t)current) != ((uintptr_t)&tsl->head)) {
TsWalkAction wa = TsContinueKeep;
list_bucket* tmp = (list_bucket*)current;
// For each entry, we will invoke the user-provided
// callback function with context, and store the result.
wa = cb(ctx, &tmp->value);
// Before we operate on the result, we will move to the next item
current = current->next;
// There are now 4 possible actions we could take:
// 1 - Continue, keeping the element in the list
// 2 - Continue, but remove the element from the list
// 3 - Stop walking the list, don't remove the last observed element
// 4 - Stop walking the list, remove the last observed element
switch(wa) {
case TsContinueKeep:
// Nothing to do - we keep iterating.
break;
case TsContinueRemove:
// Now we will remove the last observed element and continue
unlink_list_entry(&tmp->entry);
ts_free_value(&tmp->value);
tsl->count--;
deallocate(tmp);
break;
case TsStopKeep:
// Jump out of the loop and exit.
goto end;
case TsStopRemove:
// Remove the last observed element, and jump out of the loop.
unlink_list_entry(&tmp->entry);
ts_free_value(&tmp->value);
tsl->count--;
deallocate(tmp);
goto end;
}
}
end:
return status;
}
At this point we now have a very basic set of types, including a list! Next we will look at adding a few more necessary complex types (at the very least, some sort of hash table and contiguous buffer), and look at marshaling.