# Dusk C compiler implementation details

## CType

CType is most the central structures around which C compiling take place. It
describes, drum roll... a C type.

A type is an abstract notion describing the shape of something in memory or
register. It has no concept of location (storage) because by itself, it doesn't
exist anywhere. A type is either one of the base types (char, int, uint, etc.),
a struct/union, or a function signature.

A basic type has only a size and a level. An array has an element count.
Structs have members. Function signatures have both members and rettype. Members
of structs and funcsigs have an offset.

The size is the base size of the type. For an int, it's 4, for a char, it's 1,
void is 0. A function signature is 0, as we're never supposed to generate direct
references to it, only pointers to it. For a structure, the size if the sum of
the size of all its members.

The level is the indirection level of the type, that is, the number of "*"
associated with it. For "int", it's 0, for "int**", it's 2. Of course, the size
of any type with a nonzero level is 4 because it's a pointer. However, the
"size" field of CType will always give the "base size" of the type. To have an
actual size for a type (size that depends on "level"), use the ":elemsize"
method.

"nbelem" is the number of elements in the array if the type is an array. When
it's not an array, its value is zero. When it's nonzero, the type represents an
array of size/lvl elements. That last point is crucial: size/lvl. If size=4,
level=1 and nbelem=42, we have an array of 42 pointers to int. A pointer to an
array cannot be represented in the CType structure.

An array implicitly have a level of indirection which will not be present in the
"level" field. To get a level of indirection that considers whether "nbelem" is
zero, use the ":level" method.

Members is a dictionary of CType structures that describe either the fields of a
struct/union or the arguments of a function.

"rettype" is only used by function signatures and is a link to a CType that
represents the return type of the function signature.

"offset" is used only in elements of the "members" dictionary and is the byte
offset of the element within its parent structure. It's also used further within
the Symbol struct.

### Parsing types and memory management

Parsing a type is done in two parts. First, "CType :parse ( -- ?type f )" will
try to parse the "base" part of the type, that is, its first word ("int",
"char", "SomeStructName", etc). This yields a regular CType struct, that is, a
struct that already has its own place in memory. You don't want to mutate those
structs, you have to copy them first.

When the "struct" or "union" word is encountered, a new type is created to
permanent memory and yielded.

The second part of the parsing is done through "CType :decl ( type -- type )"
and parses the complete declaration of the type, that is, the "*" indirections,
the identifier, the "[]" array specifier and the "()" function signature. That
part of the parsing is done by first copying the input type to a static buffer
and then applying all those modifiers. Then, more often than not, it's this
*static* buffer that is returned.

Therefore, the CType that is yielded by ":decl" either has to be used and
discarded immediately, or to be copied away because the next ":decl" call will
overwrite it.

The members of a parsed structs or funcsig, however, are parsed to permanent
memory. In the majority of the cases, such parsing will be permanently
referenced, so it's logical, but in some cases, such as static functions or
anonymous structures, such memory management results in a memory leak. We live
with it. The struct/funcsig itself still comes from the static buffer though!

### Type referencing and compatibility testing

The CType structure doesn't allow us to represent something like "a pointer to
struct foo", only something like "a pointer to a structure having this list of
members". It's a bit inconvenient, but it's a tradeoff that buys us structural
simplicity.

When we have a CType struct reference and we want a pointer to it, we copy all
its fields and then increase "level".

We're still able to test for compatibility between two struct pointers however,
because the "members" LL link will be the same. Therefore, to test equality,
we compare size, level, nbelem flags and members, all together. Only when all
those fields are equal can we consider two CType structures to be compatible.

## The Symbol structure

While the CType structure is abstract, the Symbol structure represent a CType
at a particular place in memory. It extends CType (in other words, it holds a
*copy* of the represented type, allowing us to mutate it at will) and adds the
concept of "storage", which comes in 5 types:

1. Global variables (absolute addresses)
2. Function arguments (PS-relative addresses)
3. Function local variables (RS-relative addresses)
4. Immediates (constants)
5. The W register

In the first 3 cases, interactions with those locations first require the C code
to declare those locations through declarators ("int x;", etc.). These
declarators, when parsed, are stored in a Symbol and added to the appropriate
symbol dictionary: symbols (global and permanent symbols), ssymbols (static)
or lsymbols (local symbols).

The two other cases are used during sexpr resolution and thus only for temporary
Symbol structures.

## Stack frames

In C-compiled code, local variables and arguments being passed during function
calls are placed on something called a stack frame.

In Dusk, we have two stack frames. The "arguments" frame lives in PS and the
"local" frame (for local variables) lives on RS.  The caller of a C function
has to allocate enough space to place the arguments it's passing to the
function. When you think about it, it's the same thing as with Forth words.

When the function begins, it allocates enough space for its local variables on
RS. It also pushes (with "dup,") the value of its W register to PS so that it
becomes free for computation (and that PSP+0 points to the last argument).

## A and S registers usage

The A and S registers are used in some places during code generation, but only
in contexts that resolve immediately. Results stored in there can't be, for
example, still stored when a function call is generated.

## How the code is generated

DuskCC compiles code as it reads it, as soon as it can. When you hit the last
"}" of a function body, DuskCC is done writing it and it's ready to use.

There are different kind of behavior for different context, but the most
important context is expression parsing. Almost everything is an expression. A
"naked" statement ("a = b + c;" for example) is nothing but an expression,
"return" is followed by an expression, "if" evaluates an expression, etc. Let's
talk about how expressions are compiled. It's done in three stages, all
pipelining into the next stage:

1. Tokenization
2. Expression sequencing
3. Code generation

### Tokenization

DuskCC uses [doc/comp/tok] and installs its C-specific tokenizer there. The
tokenizer lives at [comp/c/tok.fs] and yields tokens as you'd expect, using a
predefined list of symbols to correctly detect token bounds. For example, the
input stream "*a=b--+42" can be tokenized by repeatedly calling "tok<", which
will yield: * a = b -- + 42

### Expression sequencing

Infix expression notation, the notation used in C, is foreign to Forth and it
thus needs to work a little bit to understand it. It does do using
[doc/comp/infix], which introduces the notion of "expression sequencing", that
is, to transform an infix expression into a sequence of words in the correct
sequence, "correct" meaning "if I execute it in Forth, the expression is going
to resolve as expected". For example, "*a+--b[c]" becomes "a u* b c + u* u-- +".
The "u" prefixes are to differentiate unary operators from binary operators of
the same name. See [doc/comp/infix], then read on.

comp/infix only deals with binary operators and DuskCC needs to augment it
to add prefix and postfix unary operator behavior. It does so through the
[comp/c/term.fs] unit, which agglomerates tokens into what we call "terms"
before sending them to comp/infix for binary sequencing. In the "*a+--b[c]"
example, "*a" and "--b[c]" are terms.

The process is implemented in "cterm< ( -- term )" which feeds from the input
stream thus:

1. Read a token.
2. Is is a prefix operator?
3. Yes? Do special stuff if needed, then recurse into step 1.
4. No? then it's an identifier or constant. Concatenate all tokens read until
   now.
5. Read a token.
6. Is it a postfix operator?
7. Yes? Do special stuff if needed, then recurse into step 5.
8. No? Put that token back, we're done reading. Concatenate all postfix tokens.
   That's our term.

With this process fed into comp/infix, we have complete expression sequencing,
which can be invoked through "cexpr< ( -- sexpr )". "sexpr" is a string.

### Code generation

Generating code for a sequenced expression is done in [comp/c/sexpr.fs] and, of
course, uses the HAL [doc/hal]. The broad idea is that we run through the sexpr,
word by word and do this:

1. Is this word an operator?
2. Yes? Execute it.
3. No? Is this word a symbol, constant?
4. Yes? If it's a symbol, push its CDecl (see below) to PS. If it's a constant
   create a "constant" CDecl and push it.
5. No? It has to be a literal. If it isn't, error. Create a constant CDecl and
   push it.

This means that all the logic is delegated to individual operators, which can
do whatever they want. Because the main "feed source" (the process above)
exclusively yields CDecl, it follows that operators will generally deal with
CDecls as arguments. The broad idea is that unary operators have a
( arg -- res ) signature, binary ones have a ( left right -- res ) one.

Then, the devil's in the details. The general idea is that we transform those
CDecl in the appropriate HAL operands and call the appropriate HAL operator.
For example, if we have the sexpr "a b +" and that "a" is at PS+4 (an argument)
and "b" is at RS+0 (a local variable), we will end up doing something like
"PSP) 4 +) @," and "RSP) +,", which will put the result in W.

Oh yeah, W. Knowing its state is absolutely central to this process. Operators
will generally yield a result in the W register and thus yield "res" as a CDecl
with the "storage" field set to "W register". With an expression like
"a + b + c", the previous result can nicely be fed into the next operator, a
happy path full of butterflies and singing birds.

With expressions like "(a * b) + (c * d)" (emphasis mine), we need temporary
storage to store the result of "a * b" because we'll need W to compute "c * d"
before those two results can be added.

This temporary space is PS and we're in luck today: it just so happens that the
way we resolve expressions fits well with stacks and we'll need. What we've
pushed last is the next element we'll need to recall. Handy!

A small problem though: Arguments are on PS. If we access arguments through
their PS-relative address while we have temporary values on the stack, we'll get
the wrong value. To mitigate this, we maintain a global "psoff" (PS offset)
variable in comp/c/glob.fs that modifies PSP offsets and thus allow us to access
arguments correctly.

Many expressions don't use their return values and might leave a dangling
element on PS. No stress, leave it there for now, it doesn't hurt anybody. We
still have "psoff" to remember it's there. At function postlude, we can "nip"
it all in one swoop fell, which is what we do.

... But we haven't considered branching! What if code inside a "if" block grows
PS? How do we know how to tidy up PS at postlude? To be able to know
this, we adhere to a rule: branches have to be PS-neutral. This is why you see
"psoff" and "psrestore" patterns in [comp/c/fgen.fs].

And that pretty much covers all the mechanisms involved in the code generation
stage.
