One of C-minor's primary goals is to provide a nice language for scripting and automation and as such it should be possible to write code with a minimum amount of boilerplate and plumbing code.

In C# this feature is called "top-level statements" (see here) and it removes the need for a Program class and a main method. Internally this is implemented by wrapping the top-level statements in a method of a class.

A similar approach is used with C-minor, but there's a small catch-22.

The Catch

Eventually I'd like C-minor to support that same kind of top-level statements as C# in which all the top-level statements are simply wrapped in a function. However, this requires support for closures and nested functions - which C-minor doesn't yet have.

So, for the time being there's a restriction on C-minor's top-level support: only functions and variables can be used at the top level - not control flow or expression statements - and they're wrapped in a class, not a method in a class.

Later, after I've implemented closures, this restriction will be relaxed and full support for top-level statements will be enabled.

It's Just Syntactic Sugar

In C-minor, top-level statements are just syntactic sugar in which the compiler automatically wraps any such statements in class.

In other words, all code in a C-minor program must reside inside a class - but for top-level statements, the compiler automatically generates this class and puts the code in it.

The mechanism for do this is by manipulating the AST.

The TopLevelStatements Visitor

As explained in previous posts, the way to work with the AST is with the visitor pattern and that's exactly what we do here.

The TopLevelStatements class implements the IAstStatementVisitor interface and its job is to locate any top-level statements and move them into an enclosing wrapper class called $global.

public class TopLevelStatements : IAstStatementVisitor<bool>
{
   ...

   AstClassOrStructDeclarationStatement _globalClass;
}

Firstly, we need a helper function to create the global class. Creating the global class is delayed until needed in case there are no top-level statements.

// Create (or return) the global class that encloses
// all top-level statements
AstClassOrStructDeclarationStatement GetGlobalClass()
{
    // First time? If so create the class
    if (_globalClass == null)
    {
        _globalClass = new AstClassOrStructDeclarationStatement(_unit.Position)
        {
            Name = "$global",
            IsClass = true,
            Modifiers = Modifiers.Partial | Modifiers.Public | Modifiers.Static,
            Statements = new(),
        };
    }
    return _globalClass;
}

Next, since we're only looking for top-level statements there's no need to recurse through the entire AST. Instead each statement in the root compilation unit is visited and if it returns false that means it was a top-level statement and should be removed from the root compilation unit.

After processing all the statements, if any top-level statements were found, the global class will have been created and we add it to the root compilation unit.

bool IAstStatementVisitor<bool>.Visit(AstCompilationUnit stmt)
{
    // Process all statements
    for (int i = 0; i < stmt.Statements.Count; i++)
    {
        if (!stmt.Statements[i].Visit(this))
        {
            stmt.Statements.RemoveAt(i);
            i--;
        }
    }

    // Add the global class declaration to the unit
    if (_globalClass != null)
        stmt.Statements.Add(_globalClass);

    return true;
}

Here's the visitor for the function declaration statement - it just adds the statement to the global class and returns false - so it's removed from the root compilation unit.

bool IAstStatementVisitor<bool>.Visit(AstFunctionDeclarationStatement stmt)
{
    // Move it to the global class
    GetGlobalClass().Statements.Add(stmt);
    stmt.Modifiers |= Modifiers.Public | Modifiers.Static;
    return false;
}

Note the statement is also updated to implicitly mark it as public and static.

Variable declarations are handled in exactly the same way and all other statements throw an error - since they're not supported a the top-level (at least not yet).

Before and After

To see the effect of the top-level statement visitor we can create a test case that shows the raw and the post-processed AST.

void main()
{
	Console.WriteLine("Hello World");
}

## Raw-AST

void main()
{
    Console.WriteLine("Hello World");
}

## AST

public static partial class $global
{
    public static void main()
    {
        Console.WriteLine("Hello World");
    }
}

Notice how the original void main() function is now public static void main() on the $global class.

Wrapping Up

That's it for top-level statements.

Top-level Statements remove the need for much of the plumbing and boilerplate code that would otherwise be necessary when all code must reside in a class and/or function.

The TopLevelStatements visitor is the first step after parsing and it just provides syntactic sugar that wraps any such statements in a class.

This approach means that code is always in a class and it removes the need for any further special handling by the later stages of the compiler.

On other language-based projects that I've worked on I've found that coded unit tests are cumbersome and a better approach is end-to-end testing with a dedicated test runner.

This post describes the approach I've taken with C-minor.

Starting with Sandboxing

For this project I didn’t want to waste time writing a comprehensive set of unit-tests for the tokenizer and parser as I knew those tests would soon be superceded by end-to-end testing.

Instead, I used a throw away sandbox program to exercise these parts to confirm they were basically working. Along with an AST formatter, I then had all the pieces required to build a custom test runner.

Requirements for a Testing Framework

The main thing I wanted to avoid with testing is the need to embed C-minor programs as strings in C# test case code because:

• it would require escaping C-minor code as C# strings.
• it's hard to correlate line numbers in error messages from the C-minor compiler to line numbers in an embedded string.

In other words, the source C-minor code had to come straight from a file.

Besides the C-minor program I knew the test cases would also be working with other blocks of text including reformatted AST listings, error messages from the compiler, generated code, perhaps assembly listings and the output from running a C-minor program.

Here’s the final requirements I decided on for the test cases:

• a test case file that included an input C-minor program
• line number error messages should match directly with the input program source code file
• ability to work with other blocks of text - including output from the compiler for diagnostic purposes and other blocks of text to be tested for correct output
• ability to list the input program’s AST and compare to an expected AST
• ability to check the output of a C-minor program to confirm correct behaviour
• ability to check for expected compiler error messages
• ability to show actual results when they don’t match expected results
• ability to produce diagnostic listings including generated code and post-processed AST listings
• the test runner should be able to run individual test cases or a whole recursive directory of test cases
• the test runner should be a console mode app so it can be run on any platform and from within a coding editor such as VS Code
• the output of the test runner itself should be minimal just listing failed tests

C-minor Test Case File Format

The file format I decided on for the test case files is extremely simple:

• at the top of the file is a C-minor program
• this is followed by sections of text delimited by section headings each starting with ##.

A TestCaseFile utility class (see here) provides support for loading a file, splitting it into sections, methods to add/remove and replace sections and then write it out again.

Testing the Tokenizer and Parser

To test the tokenizer and parser the test cases support a section named ## Expected-Raw-AST. When a test contains this section the test runner parses the code section to an AST before reformatting it back into code and comparing it to the expected AST.

// C-minor program at the top
void main()
{
    // Print a message
    Console.WriteLine("Hello World");

    /* Notice comments have been stripped below */
}

## Expected-Raw-AST
void main()
{
    Console.WriteLine();
}

If the AST matches, the test passes and there's nothing else to do. If the test fails (as the above example would), the test runner adds a## Actual-Raw-AST to the test case file:

// C-minor program at the top
void main()
{
    // Print a message
    Console.WriteLine("Hello World");

    /* Notice comments have been stripped below */
}

## Expected-Raw-AST
void main()
{
    Console.WriteLine();
}

## Actual-Raw-AST
void main()
{
    Console.WriteLine("Hello World");
}

From here, there's two possibilities:

• There's a bug in the tokenizer/parser. Once fixed the test can be re-run, the expected AST will match and the## Actual-Raw-AST section will be automatically deleted by the test runner.
• Or, there's a mistake in the test case and to fix it I can just copy the Actual AST to the Expected AST section and the test will now pass.

By having the actual AST added right there to the file, everything about the test is contained to one file. It also makes for an easy way to setup these tests:

1. Create the input program
2. Add an empty ## Expected-Raw-Ast section
3. Run the test, it will fail and the test runner will add the ## Actual-Raw-Ast section
4. Review the actual AST to ensure it's correct
5. Copy the actual to expected AST

(Note: the reason it's called the "raw" AST is that later we'll be doing manipulations on the AST to produce a post-processed AST. Using the prefix "raw" keeps the two AST's separately testable by the test runner)

Testing for Errors

It’s also important to test the compiler generates correct error messages when it should. To support this, the test case can include an ## Expected-Error section.

If the compiler doesn't generate this text as an error output, the test runner adds an ## Actual-Error section with the errors that were actually generated (if any).

void main()
{
    Console.WriteLine("Hello World")
}

## Expected-Error
error: code(4,1,4,2): syntax error: expected ';', found '}'

Just like the AST sections the ## Actual-Error section makes it easy to initially setup these tests.

Project Structure Overview

We're now almost at the point where we can actually run some tests, but first let's have a look at the project structure and where everything lives.

For this project I've decided to split things into a few top-level projects:

• Topten.CMinor.Compiler - the compiler itself as an assembly (.dll)
• Topten.Cminor.FrontEnd - a command line program for launching the compiler (cmc.exe)
• Topten.Cminor.Runtime - the .NET API to the runtime
• cmrt.dll - the actual (runtime written in C)

(I haven't covered the runtime yet, but I've included it here for completeness)

The Topten.CMinor.Compiler project contains everything related to actually compiling code. It also includes a Compiler class that wraps all the compilation stages - see here.

Here's an example of using the compiler to parse a file (or string) and render it as an AST:

// Create an instance of the compiler
var c = new Compiler();

// Pass compiler messages to console
c.OnMessage = (m) => Console.Error.WriteLine(m.ToString());

// Add files to be compiled
c.AddFile("myfile.cm");

// Or, add code from a string
//c.AddCode("void main() {}", "mycode.cm");

// Parse it
c.Parse();

// Render AST
c.RenderAST(Console.Out);

The Test Runner

All the pieces are now in place for building and running tests:

1. the TestRunner class (see here) in the Topten.Cminor.Compiler project loads a test case file, and then drives the Compiler class to actually run the tests. It does this according to the Expected-XXX sections it finds in the test case file.
2. the front-end (cmc.exe) supports loading C-minor test case files (these have .cmt file extension). For .cmt files the front-end uses the TestRunner class to run the test instead of compiling or running the file directly (as it would for.cm files).
3. the front-end can run an entire recursive directory full of .cmt files to run a comprehensive set of tests with one command.

Using VS Code to Develop and Run Tests

To make running tests a little easier, I setup a couple of VS Code tasks:

{
    // See https://go.microsoft.com/fwlink/?LinkId=733558
    // for the documentation about the tasks.json format
    "version": "2.0.0",
    "tasks": [
        {
            "label": "Run Current Test",
            "type": "shell",
            "command": "cmc ${file}",
            "problemMatcher": [],
            "group": {
                "kind": "build",
                "isDefault": "**/*.cmt"
            }
        },
        {
            "label": "Run All Tests",
            "type": "shell",
            "command": "cmc .",
            "problemMatcher": [],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ]
}

By putting this in a .vscode directory in the base test case directory I can:

• Open a .cmt file and press Ctrl+Shift+B to run it with the test runner. Any changes made by the test runner (eg: adding an Actual-XXX section for a failed test) will automatically be reloaded by VS Code and appear immediately.

Close all files and press Ctrl+Shift+B to run all the tests in the directory. This produces a list of files that failed in the output window that I can Ctrl+click to open them and see what went wrong.

Testing in Action

Here's a video showing the test runner in action.

Time to Get Testing

The approach I've taken to testing with C-minor is a custom test case file that's updated with detailed information by the test runner when a test fails. The output of the test runner is just a list of failed tests and a couple of tasks makes it easy to run individual or the entire test set from within VS Code.

From here on, these test case files will be central to everything I do with the compiler. I might use sandboxing for testing and experimenting with one-off things for the runtime, but anything related to the compiler itself will be developed and tested using these tests case files.

If you've been doing software development for any length of time you've almost certainly heard of the visitor pattern - it's even got its own Wikipedia page.

But it's also quite possible that you've never actually used it. Rather than try to explain it in theoretical terms, let's look at it from a practical point of view.

(Normally I wouldn't devote a whole post to a design pattern, but it really is central to everything else the compiler does. It's also a rarely used pattern so I wanted to make sure we're on the same page on how it works).

Working with the AST

Now that our compiler has parsed the source code into an AST we need a way to work with the AST. We might want to go over it to check for errors, evaluate a constant expression node, or generate code. Or perhaps we just want to print it out.

Let's take that last one - "print it out" - and see how to implement it.

The Traditional OO Approach

In order to print out the AST we need to start at the top-level element and print the parts related to that element while also recursively calling its connected elements to print themselves.

The traditional OO way to do this would be to add an abstract method to the base AstElement class named Print().

class AstElement
{
    // omitted

    public abstract void Print(IndentedTextwriter target);
}

(Let's assume a helper class IndentedTextWriter that we can print to).

Next, we'd implement the Print method on every class. For example, we'd add a Print method to the if statement like this:

public override void Print(IndentedTextWriter target)
{
    target.Write("if (");
    Condition.Print(target);
    target.WriteLine(")");

    TrueBlock.Print(target);

    if (FalseBlock != null)
    {
        target.WriteLine("else");
        FalseBlock.Print(target);
    }
}

To print the entire AST all we have to do is call Print on the top level AstCompilationUnit and the entire program can be printed out. Nice!

Need to generate code? Repeat the above adding a GenerateCode() method.

Need something else? Repeat again adding another method.

Very quickly a problem emerges: the code for each of these operations is spread over many different classes and files. Also, any state or context information for the operations (such as the target writer in the above example) needs to be passed around as parameters.

Containing an Operation to One Class

What we'd like to do is contain each operation on the AST to its own class.

Continuing with our example of printing out the AST, let's make a class called AstFormatter:

class AstFormatter
{
    public AstFormatter(IndentedTextWriter target)
    {
        _target = target;
    }

    public void Print(AstElement element)
    {
        // TODO
    }
}

and let's move the print methods from all the AstElement classes into our new AstFormatter . The function to print if statements now looks like this:

void PrintIfStatemnt(AstIfStatement stmt)
{
    _target.Write("if (");
    Print(stmt.Condition);
    _target.WriteLine(")");

    Print(stmt.TrueBlock);

    if (stmt.FalseBlock != null)
    {
        _target.WriteLine("else");
        Print(FalseBlock);
    }
}

This is looking good:

1. We've moved all our printing code to one class
2. We don't need to pass the target text writer around anymore since we can just store it as a member variable on the AstFormatter class.

But we've also created a mess. The worst kind of mess. A slow mess.

See that TODO comment in the Print method? It needs to inspect every element's type to work out which print method to call for each element:

if (element is AstIfStatement stmt_if)
  PrintIfStatement(stmt_if);
else if (element is AstForStatement stmt_for)
  PrintForStatement(stmt_for);
else if (element is AstWhileStatement stmt_while)
  PrintWhileStatement(stmt_while);
else if 

// ... for every ... type ... of ... element. Ugh

We've solved the original problem, but:

• it's slow - we need to test every element for every type.
• it's messy - just look at it!
• it's unsafe - we won't get compiler errors if we forget to implement an element (or add a new element type).
• it's painful - we need to re-type (or cut/copy/replace) that code for every different operation.

What we need is a type-safe, fast way to dispatch those PrintXXX() methods.

Using a Dispatch Interface

Imagine we've implemented all our operations using the above approach: a separate class for each operation, with a function that dispatches to methods for each element type.

What you'll notice is that you end up with each class having a method to handleif statements, a method to handle for statements, a method to handle while statement etc...

Let's force each of those classes to implement those methods by defining an interface IStatementProcesor that has a method for each statement type.

interface IStatementProcessor
{
    void ProcessIfStatement(AstIfStatement stmt);
    void ProcessForStatement(AstForStatement stmt);
    void ProcessWhileStatement(AstForStatement stmt);
    // etc.. for all statement types
}

By implementing this interface on an operation class we can ensure that it implements the functionality for all element types:

class AstFormatter : IStatementProcessor
{
    // If we don't implement a particular element type...
    // the compiler will complain
}

That solves the "unsafe" problem with the previous approach, but we can also use it to solve the "slow" and "messy" problems by adding a Process method to the element classes:

abstract class AstElement
{
    public abstract void Process(IStatementProcessor processor)
}

class AstIfStatement : AstElement
{
    public override void Process(IStatementProcessor processor)
    {
        processor.ProcessIfStatment(this);
    }
}

In other words, if you call Process on an element, passing an instance of IStatementProcessor you'll be called back through that interface on the correct method for the element's type.

Now the big slow mess can be fixed:

// GET RID OF THIS
/*
if (element is AstIfStatement stmt_if)
  PrintIfStatement(stmt_if);
else if (element is AstForStatement stmt_for)
  PrintForStatement(stmt_for);
else if (element is AstWhileStatement stmt_while)
  PrintWhileStatement(stmt_while);
else if ...
*/

element.Process(this);

Oh, and by the way, we've also solved the "painful" problem. Right clicking on the interface in Visual Studio there's a command "Implement Interface Explicitly" and stubs for every method will be automatically generated and we can just fill in the blanks.

What I've just described is the Visitor Pattern... so let's call it that.

The Visitor Pattern

Now that we understand what the visitor pattern is, let's look at how it's actually implemented in C-minor for the AST.

As before, there are two categories of visitors - statements and expressions and since we might want to have return values when processing elements the interfaces are defined with a generic type parameter T for the return type:

public interface IAstStatementVisitor<T>
{
  T Visit(AstIfStatement stmt);
  T Visit(AstForStatement stmt);
  T Visit(AstWhileStatement stmt);
  // etc
}

public interface IAstExprNodeVisitor<T>
{
  T Visit(AstExprNodeLiteral node);
  T Visit(AstExprNodeUnaryOp node);
  T Visit(AstExprNodeBinaryOp node);
  // etc...
}

(Note: we can use method overloading to name every method Visit() instead of VisitIfStatement(), VisitForStatement() etc...)

The AstStatement and AstExprNode bases classes both get an abstract Visit method:

public class AstStatement
{
    public abstract T Visit<T>(IAstStatementVisitor<T> visitor);
}

public class AstExprNode
{
    public abstract T Visit<T>(IAstExprNodeVisitor<T> visitor);
}

and every statement and expression node implements the Visit method with a simple one liner:

public class AstIfStatement
{
    public override T Visit<T>(IAstStatementVisitor<T> visitor) => visitor.Visit(this);
}

Revisiting (ha-ha) the AstFormatter

Now that we've formalized our visitor pattern, let's take a look at how our original AstFormatter class now looks:

class AstFormatter : 
    IAstStatementVisitor<bool>,
    IAstExprNodeVisitor<bool>
{
    public AstFormatter(IndentedTextWriter target)
    {
        _target = target;
    }

    public void Print(AstStatment stmt)
    {
        stmt.Visit(this);
    }

    bool IAstStatementVisitor<bool>.Visit(AstIfStatement stmt)
    {
        _target.Write("if (");
        stmt.Condition.Visit(this);
        _target.WriteLine(")");

        stmt.TrueBlock.Visit(this);

        if (stmt.FalseBlock != null)
        {
            _target.WriteLine("else");
            stmt.FalseBlock.Visit(this);
        }
        return true;
    }

    bool IAstStatementVisitor<bool>.Visit(AstForStatement stmt)
    {
        // TODO
    }

    // etc...
}

Note:

• C# doesn't allow a void generic type parameter sobool is used and its return value is always ignored.
• The interfaces are implemented explicitly which keeps the public API to the AstFormatter nice and clean.

Who Are These Mysterious Visitors?

To put into perspective just how important the visitor pattern is, here's the full list of visitors currently used in C-minor's compiler:

• AstFormatter
• CodeGenerator (C code)
• ControlFlowAnalysis
• HydrateTypes
• NameResolver
• ScaffoldTypes
• StatementBinder
• TopLevelStatements
• ConstantExpressionEvaluator
• SideEffects

Some of these classes are quite complex and without the visitor pattern their code would be scattered across many classes and files and we'd need to pass some sort of context class around to store the state of the operation.

The Down Side of the Visitor Pattern

There's only one small downside I've found with the visitor pattern - we can't pass parameters to the visit methods.

For example, in the ControlFlowAnalysis visitor there's an "entry state" that needs to be passed to each element as it's visited.

My solution is to store that information as a member of the operation class with a helper function that sets it before visiting the element. The Visit callback then picks it up again once it's been called.

// Helper function to visit a statement, passing an entryState
CFSTate Visit(AstStatement stmt, CFState entryState)
{
    _entryState = entryState;
    return stmt.Visit(this);
}

CFState Visit(AstIfStatement stmt)
{
    // Would be nicer if this was a parameter, but oh well.
    var entryState = _entryState;
}

It's a bit of a hacky solution, and I could update the visitor interfaces with at least one generic parameter, but I don't think it's worth it.

Enough Already!

Ok, so I think I've gone on enough about the visitor pattern, but just to sum up why it's used:

• Code for each operation on the AST can be contained to a single class.
• The AST elements know nothing about the operations being performed on them (this is good).
• We can add operations without touching the AST classes.
• It's fast since the dispatch is through virtual methods, not slow type tests.
• The operations can implement the separate statement and/or expression node visitor patterns as required.
• If we add a new AST element type, we have to add the associated method to the visitor interface in order to implement its Visit method... and then we're forced to implement the method on all classes. ie: it's type safe.

From now on, pretty much everything the C-minor compiler does centers around the AST - and the visitor pattern is the mechanism for doing it.

The Parser

Now that we've got a Tokenizer and an Abstract Syntax Tree we've got everything we need to build the Parser.

The parser's job is to read the tokens from the tokenizer, check they conform to the syntax rules of the language and produce a fully populated abstract syntax tree.

Just like the AST, this falls into two main categories - statements and expressions.

Parsing Statements

Parsing statements is a relatively straight forward process:

1. If the current token is a flow control statement if, for, while etc... then call a dedicated function to parse the supported syntax of each statement type.
2. If the current token is an open brace { then the statement is a code block, and the parser just recursively parses its contents into an AstCodeBlock statement.
3. Otherwise, the statement must be an expression or declaration statement - call a dedicated function for this.

Here's the code from C-minor that does this:

AstStatement ParseStatement()
{
    // Flow control statements
    switch (_tokenizer.Token)
    {
        case Token.Keyword_break:
            return ParseBreakStatement();

        case Token.Keyword_continue:
            return ParseContinueStatement();

        case Token.Keyword_for:
            return ParseForStatement();

        case Token.Keyword_if:
            return ParseIfStatement();

        case Token.Keyword_return:
            return ParseReturnStatement();

        case Token.Keyword_switch:
            return ParseSwitchStatement();

        case Token.Keyword_do:
            return ParseDoWhileStatement();

        case Token.Keyword_while:
            return ParseWhileStatement();

        case Token.Keyword_throw:
            return ParseThrowStatement();

        case Token.Keyword_try:
            return ParseTryStatement();
    }

    // Braced statement block?
    if (_tokenizer.Token == Token.OpenBrace)
    {
        return ParseCodeBlock();
    }

    // Function declaration, variable declaration or expression statement
    return ParseExpressionOrDeclarationStatement(0);
}

Flow Control Statements

Flow control statements are parsed by following the required and optional parts of the statement and building the associated AST element.

Here's an example for the if statement:

AstIfStatement ParseIfStatement()
{
    // Create 'if' Statement
    var stmt = new AstIfStatement(_tokenizer.TokenPosition);

    // Skip "if"
    _tokenizer.Next();

    // Parse the condition expression
    // '(' <condition> ')'
    _tokenizer.SkipToken(Token.OpenRound);
    stmt.Condition = ParseExpression();
    _tokenizer.SkipToken(Token.CloseRound);

    // Parse the true block
    stmt.TrueBlock = ParseCodeBlock();

    // If there's an else block parse it too
    if (_tokenizer.TrySkipToken(Token.Keyword_else))
        stmt.FalseBlock = ParseCodeBlock();

    // Done
    return stmt;
}

That's the entire code for parsing an if statement. The other flow control statements are all very similar.

The parsing code makes extensive use of helper functions provided by the tokenizer:

• SkipToken - checks the current token matches a particular token and if so moves to the next token. Otherwise, it throws a CodeException reporting a syntax error.
• TrySkipToken - checks if the current token matches a particular token and if so moves to the next token and return true. Otherwise, it returns false.
• There are other similar functions for skipping identifiers and various unexpected token helpers.

Note that at this point we've enforced the syntax of the if statement but haven't checked the statement is correct. eg: we haven't checked the condition expression evaluates to a boolean value.

Similarly, we haven't checked for statements that are only supported in certain contexts. For example, a continue statement can only be used inside a loop but the parser doesn't care and will happily include it anywhere in the AST.

Code Blocks

A code block is a sequence of one or more statements, optionally enclosed in braces. Here's how they're parsed:

AstCodeBlock ParseCodeBlock()
{
    // Create a code block statement
    var block = new AstCodeBlock(_tokenizer.TokenPosition);

    // Is it a braced code block?
    if (_tokenizer.TrySkipToken(Token.OpenBrace))
    {
        // Yes, parse statements until the close brace
        block.WasBraced = true;
        while (!_tokenizer.TrySkipToken(Token.CloseBrace))
        {
            block.Statements.Add(ParseStatement());
        }
    }
    else
    {
        // Not braced, parse just a single statement
        block.Statements.Add(ParseStatement());
    }

    return block;
}

Notice how braces are handled to group a block of statements as a single statement. This allows the same parsing code to be used for cases where braces are required vs optional. Eg:

• The true/false blocks of an if statement can be either a single statement or a braced block of statements. ParseCodeBlock handles either case.
• The code blocks of a try/catch statement are always braced. To enforce this the code that parses try statements just checks for an open brace before calling ParseCodeBlock.

Although not strictly necessary for the abstract syntax tree, the code block remembers if the block was originally braced or not. This is only used for reformatting the AST to text for debugging purposes and isn't used otherwise.

Parsing Declarations

Declarations are probably the trickiest part of the parser because we can't always tell whether it's a declaration or an expression until we get some way into things.

Declarations include:

• variables eg: int x;
• functions eg: void fn() { }
• type declarations eg: class MyClass { }

The approach here is to:

1. Capture the current position in the tokenizer.
2. Try to parse a declaration - if it succeeds, then use it and continue on.
3. Otherwise, rewind the tokenizer to the saved position and try again as an expression.

AstStatement ParseExpressionOrDeclarationStatement(ParseFlags flags)
{
    // Function or variable declaration
    var decl = TryParseDeclaration(flags);
    if (decl != null)
        return decl;

    // Must be an expression statement
    var pos = _tokenizer.TokenPosition.Start;
    var expr = ParseExpression();
    if (!flags.HasFlag(ParseFlags.NoConsumeSemicolon))
        _tokenizer.SkipToken(Token.SemiColon);
    return new AstExpressionStatement(pos)
    {
        Expression = expr
    };
}

(the NoConsumeSemicolon flag is used when parsing the initializer of a for statement).

Parsing Expressions

Finally, we come to parsing expression nodes. The main thing to get right here is the order-of-operation which is established by having the parser functions for lower order of operations call parse functions for higher order operations.

Let's take a look at the function for parsing the add and subtract binary operator. Add and subtract have equal order of operation, are evaluated left to right and have lower order of operation than multiply and divide.

// Parse add/subtract expression nodes
AstExprNode ParseAddSub()
{
    // Parse the LHS
    var lhs = ParseMulDiv();

    // Parse RHS while it's a add or subtract
    while (true)
    {
        switch (_tokenizer.Token)
        {
            case Token.Plus:
            {
                // Create binary add operator
                var binOp = new AstExprNodeBinaryOp(_tokenizer.TokenPosition);
                _tokenizer.Next();
                binOp.LHS = lhs;
                binOp.RHS = ParseMulDiv();
                binOp.Operator = BinaryOperatorType.Add;

                // Binary op becomes the new LHS
                lhs = binOp;
                break;
            }

            case Token.Minus:
            {
                // Create binary subtract operator
                var binOp = new AstExprNodeBinaryOp(_tokenizer.TokenPosition);
                _tokenizer.Next();
                binOp.LHS = lhs;
                binOp.RHS = ParseMulDiv();
                binOp.Operator = BinaryOperatorType.Subtract;

                // Binary op becomes the new LHS
                lhs = binOp;
                break;
            }

            default:
                // Not an add or subtract, finish.
                return lhs;
        }
    }
}

Consider this expression:

a * b + c * d

and imagine the tokenizer is currently on the a identifier token and we've just entered the ParseAddSub method:

• The ParseMulDiv function is called. This will consume the a * b and return an binary expression node to multiply a and b
• The ParseAddSub function then sees the Token.Plus token and creates a new AstExprNodeBinaryOp for addition.
• It sets the left-hand side to the previously parsed result from ParseMulDiv.
• It then parses another mul/div expression and sets it as the right-hand side.
• The new expression node is then set as the left-hand side and the whole operation is repeated for as long as there's an add or subtract token.

What we end up with is an expression tree that looks like this:

flowchart TD

    add[+] --> mul
    add[+] --> mul2
    mul[*] --> a
    mul[*] --> b

    mul2[*] --> c
    mul2[*] --> d

You might be wondering how parentheses work? Let's look at this expression:

a * (b + c) * d

The ParseMulDiv function is basically an exact copy of the ParseAddSub function except it calls an even higher order of operation parser for its operands. At the very top of the order of operation the parser looks for round parentheses and recurses back into itself.

AstExprNode ParsePrimaryRoot()
{
    switch (_tokenizer.Token)
    {
        /* OTHER CASES OMITTED */

        // Grouped expression `(` <subexpression> `)`
        case Token.OpenRound:
        {
            // Skip '('
            _tokenizer.Next();

            // Parse the sub-expression
            node = ParseExpression();

            // Must end with a ')'
            _tokenizer.SkipToken(Token.CloseRound);

            return node;
        }

        // ...

    

So when ParseMulDiv parses its right-hand operand after parsing the a operand, it will get back a binary node adding b + c and the expression tree looks like this:

flowchart TD

    mul[*] --> a
    mul[*] --> add
    add[+] --> b
    add[+] --> c

    mul2[*] --> mul[*]
    mul2[*] --> d

It's the order that these expression parsing functions call each other that establishes order of operation.

Here's the full set of expression parsing functions from highest to lowest order of operation (ie: each function calls the one above it to parse its operands).

// literals, identifiers, '(' ')'
AstExprNode ParsePrimaryRoot()

// function call `()`, member accessor `.`, postfix `++` and `--`
AstExprNode ParsePrimarySuffix()

// (type cast)
AstExprNode ParsePrimary()

// prefix `++` and `--`, negate `-`, unary plus `+`, 
// logical not `!`, one's complement `~`
AstExprNode ParseUnary()

// `*`, `/` and  `%`
AstExprNode ParseMulDiv()

// `+` and `-`
AstExprNode ParseAddSub()

// `<<` and `>>`
AstExprNode ParseShift()

// `<`, `<=`, `>` and `>=`
AstExprNode ParseRelational()

// `==` and `!=`
AstExprNode ParseEquality()

// `&`
AstExprNode ParseBitwiseAnd()

// `^`
AstExprNode ParseBitwiseXor()

// `|`
AstExprNode ParseBitwiseOr()

// `&&`
AstExprNode ParseLogicalAnd()

// `||`
AstExprNode ParseLogicalOr()

// `? :` (conditional operator)
AstExprNode ParseTernary()

// Entry point to parsing an expression
AstExprNode ParseExpression()

Parser API

That's most of the internal workings of the Parser but you might be wondering where it all starts? What kicks it off?

The API to the Parser is essentially just one function ParseCompilationUnit - see here.

A compilation unit represents an entire source code file.

/// <summary>
/// Parses a "compilation unit" (aka a source code file)
/// </summary>
/// <param name="source">The <see cref="CodeFile"/> to parse</param>
/// <returns>The AST of the entire file</returns>
public AstCompilationUnit ParseCompilationUnit(CodeFile source)
{
    // Create tokenizer
    _tokenizer = new Tokenizer(source);

    // Create compilation unit ast
    var unit = new AstCompilationUnit(_tokenizer.TokenPosition);

    // Parse all statements
    unit.Statements = ParseStatements();

    // Check nothing unexpected at the end of the file
    _tokenizer.CheckToken(Token.EOF);

    return unit;
}

Here's everything needed to parse a file:

try
{
    // Load code
    var codefile = CodeFile.FromFile("my-cminor-program.cm");

    // Parse it
    var parser = new Parser();
    var ast = parser.ParseCompilationUnit(codefile);

    // Work with ast...
}
catch (CodeException x)
{
    // Syntax error
    Console.WriteLine(x.Message);
}

(Note the parser has no internal state so the one instance can be re-used to parse multiple files).

Syntax Checked!

The Tokenizer and Parser have now been brought together to produce an Abstract Syntax Tree. At this point we have the entire structure of the program loaded and we know it's syntactically correct.

We're now ready to start working with the AST. To do that we'll be making extensive use of the visitor design pattern and in the next post I'll be showing how it's implemented and used with C-minor's AST.

What is an Abstract Syntax Tree?

An Abstract Syntax Tree (aka AST) is a tree graph of elements that represent the entire input program.

The easiest way to understand it is with a simple example. Consider this if statement:

if (x < y)
{
  print("less");
}
else
{
  return 0;
}

The abstract syntax tree for this statement would look something like this:

flowchart TD
    if[if statement]
    cond[<]
    x[x]
    y[y]
    
    if --condition--> cond
    cond --> x
    cond --> y

    if --trueblock--> true
    true[codeblock] --statements--> meth1

    if --falseblock--> false
    false[codeblock] --statements--> retstmt

    meth1[method call]
    meth1--LHS-->id1
    meth1--parameters-->p1
    p1[expr literal 'less']
    id1[identifier 'print']
    
    retstmt[return] --value--> retval
    retval[expr literal 0]

This AST can be read as follows:

• Anif statement with three connected elements
  • a condition expression
  • a code block of statements to execute if the condition is true
  • a code block of statements to execute if the condition is false
• The condition is a less than comparison < operator with two operands x and y
• The true block is a method call, on the identifier print with a single parameter - a literal string "less"
• The false block is a return statement with the literal value 0

Statements vs Expression Nodes

Everything in the AST falls under one of two main categories:

• Statements - control flow statements and declaration (functions, variables, types etc...).
• Expression Nodes - anything that has a value (literals, function calls, operator results etc...)

In C-minor these two categories are represented by the base classes AstStatement and AstExprNode - both of which derived from a common base class AstElement.

classDiagram
    class AstElement{
        +CodePosition Position
    }
    AstElement <|-- AstStatement
    AstElement <|-- AstExprNode

    AstStatement <|-- all_statements
    AstExprNode <|-- all_exprnodes

    class all_statements["all statement types"]

    class all_exprnodes["all expression nodes types"]

From AstStatement and AstExprNode there are derived classes for all the different element types - you can see the full list here.

(note that even though these classes are in a Topten.Cminor.Ast ok namespace I've kept the "Ast" prefix because their names tend to become a bit generic without it).

Declarations are Statements

As far as C-minor is concerned declarations (functions, variables, classes etc...) are also statements even though not technically statements if you take that word to mean something that executes.

Expression Statements

Although statements and expressions are generally different things, there's a special statement for expressions that are statements.

Consider a statement like this:

print("Hello World");

This is an expression, but it's used as a statement. The AstExpressionStatement class is used to represent this.

Order of Operation

It's worth noting that order of operation is implicit in the AST and doesn't need to record grouping tokens like parentheses.

Consider these two expressions:

# expression A
x + y * z

# expression B
(x + y) * z

Expression A is represented as:

flowchart TD

    add --> x
    add --> multiply

    multiply --> y
    multiply --> z

Expression B is represented as:

flowchart TD

    add --> x
    add --> y

    multiply --> add
    multiply --> z

The grouping parentheses in the original expression B is used by the parser to construct the correct tree and then discarded.

Syntactic Structure, Little Meaning

The AST stores the syntactic structure of the input program but by itself ascribes very little meaning to its elements.

For example:

• identifiers are recorded as identifier nodes but say nothing about whether the identifier represents a local variable, parameter, method or function, a class name etc...
• the AST allows function and class declarations anywhere statements are allowed so there's nothing to stop the declaration of a class inside a function (even though this is not supported in C-minor)
• the AST will happily record operations on incompatible arguments (eg: string + integer) or passing an incorrect number of arguments to a function.

In other words, at this stage all we're doing is capturing the syntactic structure of the program and meaning will be applied and correctness checked later as part of "semantic analysis".

Position Information

Just like every token produced by the tokenizer has a CodePosition describing where it came from, every element in the AST also has a position. In later stages as we're performing checks on the AST and we find problems we've got the position readily available to report the original location of the error.

Time to Parse!

The AST is a tree of elements that describe a program's syntactic structure but not its meaning.

Each node is either a statement or an expression. Order of operation is implicit in the arrangement of nodes that make an expression. Every node in the AST has position information attached for error reporting.

The AST is central to everything else the compiler does - it'll be used for building the type system, semantic analysis, code generation and more.

Now that we have a way to represent the AST the next challenge is to build a correctly formed AST from a stream of tokens... and that's the job of the parser.

What is a Token?

A token represents a single indivisible piece of source code:

• Operators - +, -, >=, >> etc...
• Literals - numbers, strings, null, true, false etc...
• Identifiers - name of variables, functions, classes, etc...
• Keywords - identifiers with special meaning in the language if/else, while, class etc...

As an example, this piece of code...

// A comment
int myvar = myothervar << 4;

...would be tokenized into the following tokens (assuming an enumerated type Token):

1. Token.Keyword_int
2. Token.Identifier "myvar"
3. Token.Assignment
4. Token.Identifier "myothervar"
5. Token.ShiftLeft
6. Token.Literal 4
7. Token.Semicolon

Note that whitespace and comments aren't included in the token stream.

Tokenization Algorithm

The tokenization process is to skip whitespace and comments and then look at the next character to figure out the type of token and consume as many characters as necessary to produce the token.

1. Skip any whitespace
2. If the next character is a / , skip it and...
   1. If the next character is a * then this is a comment - skip to the end of the comment and start again from step 1.
   2. Else, if the next character is a / then this is a single line comment - skip to the next line and start again from step 1
   3. Else, if the next character is a =, then skip it and return Token.DivideAssign
   4. Else, return Token.Divide.
3. If the next few characters match an operator token (eg: +, -, <, <=, << etc...) skip those characters and return the associated token.
4. If the next character is double or single quote, parse and store a string or character (while handling escape sequences) and return Token.Literal
5. If the next character is a digit, skip and store all characters valid for a numeric literal, convert the number to a numeric value and return Token.Literal. Also consume suffix letters (U and L) for unsigned and long numbers and make sure the literal value reflects those.
6. If the next character is a valid first character for an identifier, read all characters that are valid identifier characters and store as a string.
   1. If the resulting string is a named literal (eg: true, false, null) return Token.Literal.
   2. If the resulting string matches a keyword, return the Token for that keyword.
   3. Otherwise, return Token.Identifier.
7. Throw a syntax error exception. (see CodeException below)

The Tokenizer Class

The Tokenizer class wraps the above algorithm. The main API to the tokenizer consists of:

• Next() method - reads the next token (ie: the above algorithm)
• Token property - the current token (see here for a list of tokens)
• TokenLiteral property - the value of the currentToken.Literal token
• TokenIdentifier property - the identifier name of the currentToken.Identifier token
• TokenPosition property - position information for the current token (see below)

The tokenizer also has utility methods that can check for particular expected token and either skip it or throw an error. These are listed here and we'll see how they're used when we talk about the parser.

Related Classes

Besides the tokenizer itself, there are a number of supporting classes - primarily for tracking the position of a tokens in the source file for later error reporting:

The CodeFile Class

The tokenizer reads from the source file via the CodeFile class which:

• stores the filename of the input file
• holds the entire input file as a string
• maintains a current position in the file as an offset from the start of the file (ie: the current character index)
• provides helper methods for skipping whitespace, extracting sub-strings etc...

See here for more about this class.

File Offsets vs Line Number Positions

A file position can be represented in one of two ways:

1. a character offset from the start of the file, or
2. a line number and a character offset from the start of the line.

Internally, only file offsets are used because they're cheaper to store and easier to work with. When a file position needs to be presented to the user as part of an error message, it's converted to line number/offset.

In order to convert from a file offset to a line number the CodeFile class has an internal instance of the LineNumbers class that uses a list of line offsets and a binary search to quickly convert file offsets to line numbers.

The LinePosition struct encapsulates a line number and a character offset as a single value.

The CodePosition Struct

Every token has an association position represented by a CodePosition struct. It's a struct to save on memory allocations and it stores:

• a reference to the CodeFile
• a file offset

Given a CodePosition we have everything needed to construct useful position information for error messages:

• The name of the file (available via the CodeFile reference)
• The line number and offset from the start of the line (by converting the file offset using the line number mapping stored in the CodeFile)

Error Handling

Any syntax errors encountered during tokenization and parsing cause the compilation to immediately abort by throwing a CodeException - an exception with an associated CodePosition (see here).

These exceptions are caught by the compiler and reported as errors using the message and position information stored in the CodeException.

(Some compilers will attempt error recovery from syntax errors. This is important if you need to work with the file's abstract syntax tree as the user is editing the file - eg: for code completion. We don't need that functionality so the complexity of error recovery is avoided - at least for now).

Rewinding

There are a couple of instances where the parser needs to look ahead in the token stream.

To support this the tokenizer has a Rewind method which simply resets the input position to a previously saved position and re-reads the next token.

Special Handling for Interpolated Strings

Normally the tokenizer is "context free" in that the next token can always be determined without regard to the previously supplied tokens.

The only time this isn’t true is with interpolated strings as these contain embedded expressions.

(interpolated strings are string literals with embedded expressions such as $"answer {x} + {y} = {x+y}" where x, y and x+y are expressions to be evaluated and substituted into the final string)

You'll notice the tokenizer has methods and tokens related to interpolated strings. I’ll cover these in a later article because it involves the tokenizer, the parser and the runtime.

Tokenized!

There's not much more can be said about the tokenizer - it reads a stream of input characters, strips whitespace and comments and produces tokens with position information.

The next step is parsing, but first we need a structure in which to store the results of the parsing - an Abstract Syntax Tree.

Like many developers I've often thought about writing a compiler for a programming language. Recently I had reason enough to look into making a proof-of-concept scripting language for my music software Cantabile.

Although just a proof-of-concept I've learned a lot and thought it might be worth sharing what I've learned about "How to Write a Compiler".

First up though, what is this language?

Introducing C-minor

C-minor is a strongly typed, garbage collected language that compiles to in-memory machine code for direct execution.

• The compiler is written in C#.
• The supporting runtime library and garbage collector are written in plain C.
• The language is heavily influenced by C#.
• It has a focus on speed - which is why it's strongly typed and compiled to machine code instead of interpreted.
• It's strictly single threaded - as a feature.
• The name "C-minor" was chosen to reflect its musical connection to Cantabile and its C-style syntax. The word "minor" suggests this is a language for scripting and automation and not for building fully-fledged applications.

(Although influenced by C# it obviously doesn't have most of C#'s features - but anything it does has been shamelessly stolen).

Just how "Proof-of-Concepty" is it?

Very! It's not useful for anything other than as a proof-of-concept.

That said the initial goal for this project was just to get something working and it is "working":

• Primitive data types - bool, char, sbyte, byte, short, ushort, int, uint, long, ulong, float, double and string.
• All the standard math, logical, relational and bitwise operators for the built in types.
• Explicit and implicit type casting of primitive data types.
• Functions with simple parameters and local variables.
• Function overloading and overload resolution.
• Flow control statements - if/else, while, do-while, for, switch .
• Support for exceptions (currently by throwing a string since no class support), along with try/catch/finally blocks.
• Interpolated strings and numeric formatting.
• An incremental "in-series" garbage collector.
• A few library functions - just enough to run the test cases (eg: string.Substring, Console.Write/WriteLine).

Other things of note:

• The compiler generates C code that is then compiled to in-memory machine code using Tiny-C. I might do a direct native code generator at a later date.
• There's a front-end command line program to run C-minor source files and test cases.
• The front-end can either run C-minor programs directly, produce C code or produce .exe files.

An Example Program

Here's an example program:

void main()
{
  for (int i = 0; i < 3; i++)
  {
    Console.WriteLine($"#{i+1}: Hello World from C-minor");
  }
}

and its output:

#1: Hello World from C-minor
#2: Hello World from C-minor
#3: Hello World from C-minor

(I'd like to get rid of that main and have true top-level statements - I'll explain why I haven't in a later post).

Here's a more interactive look at it in action:

What's Next?

I'm going to chip away at this as a side project to Cantabile - partly because I'm enjoying the challenge and partly because it might get to the point of being useful.

In the meantime, I'm going to write some articles that go pretty deep on how it works and hope to cover everything from tokenization, parsing and semantic and control flow analysis through to code generation, the runtime and the garbage collector.

I'll also be touching on some interesting design patterns (in particular the much under-rated visitor pattern), some Big-O analysis and an interesting approach to testing.

In other words, this won't be hand-waving about abstract concepts - this will be everything you need to know to write your own compiler - or at least have a better understanding of how one works.

If you've ever been curious about how a modern compiler works (and who hasn't) then I think you'll enjoy these upcoming posts.

It always starts with "Hello World" and who knows where it goes from there.

Recently I purchased a Microsoft Surface Laptop 4 to replace my aging MacBook Pro.  The Surface is a great machine: excellent keyboard and trackpad, beautiful display. It's slim, lightweight, powerful, just enough storage and has good battery life.

But what a pity that all of that is ruined by one stupid design decision - the behaviour of the Fn key is completely intolerable and drives me to distraction.

The Fn Key

The Surface Laptop 4's Fn key is both a toggle (like capslock) and a modifier (like shift):

• If you press and release the Fn key without pressing another key it toggles - the light toggles on/off and the behaviour of the F1-F12 keys inverts.  However...
• If you press and hold the Fn key while using the arrow keys, it makes them work as Page Up/Down and Home/End.

Now that seems like a clever design decision to get double use out of a single key but in real-world use it makes for a terrible experience.

Developers and Keyboards

I'm a software developer and make heavy use of the keyboard.  In particular I'm constantly using the Fn+arrow keys to navigate around in code. I also make heavy use of the F1-F12 keys for building, debugging, browsing etc...

And here's where the problem starts. If you're constantly using the Fn+arrows for navigation it's incredibly easy to press/release the Fn key without another key and all of a sudden the behaviour of all the function keys has flipped.

It seems like such a minor thing but it completely kills productivity. Instead of being able to focus on what you're working on you end up constantly distracted by the keyboard not behaving as you expect it to.

In other words, the behaviour of the F1-F12 keys becomes random coin flip.

• Press F3 and it might jump to the next search match or it might increase the volume.
• Press F7 to start a build, but no the screen gets brighter.
• Press F8 to step in the debugger, nope that takes a screen shot.
• Press F10 to step-over in the debugger, why didn't it step? And why did the cursor move to the end of the line?
• Press F12 to browse to a symbol definition - that doesn't look right.  Oh, that's because it did a page down instead. OMG!

But it gets worse. Once you've been tricked by the Fn key trap, you can't just toggle it and try again.  No, you also need to undo what you just did, re-adjust the volume or screen brightness or navigate back to where you were, then you can toggle the Fn key and then you can try again - by which time you've probably forgotten what you were trying to do in the first place (mostly due to the rising rising frustration levels).

Argh!  I hate you Fn key!

This is not a Muscle Memory Issue

At first I thought this might be just a muscle memory issue.  I mean I get it, moving between Mac and PC is always painful when it comes to Ctrl, Alt and Options/Windows keys.  But I've been through that multiple times and you learn and adapt reasonably quickly.

But this isn't like that.  Muscle memory isn't going to learn that if you press the Fn key you absolutely must press another key to avoid toggling the function keys.

And it's easy to do: you press the Fn key in anticipation of pressing an arrow and there's no going back - you have to press another key to avoid the toggle. It's nuts.

This is Worse than the Stupid Power Button

The Surface Laptop 4 has another annoying keyboard antic - accidentally bump the power button and the machine will go to sleep.  

Conveniently (not) the power button is exactly where the F12 key is on my MacBook so I've accidentally hit it multiple times already. But muscle memory will kick in eventually and this will become less of an issue over time.  Also the machine wakes quickly and face recognition for login means I can back pretty quickly.

(That said, why not make it a long press on the power button to put the machine to sleep? Who needs to be able to sleep their machine at the touch of button - especially when you can just close the lid?)

But think about that... accidentally putting the machine to sleep is less annoying and easier to deal with than randomly toggling the function keys.

One Possible Saving Grace

The only possible saving grace here is that at the moment, I might be accidentally hitting the Fn key more often than I will be once I adjust to its different position.  

The Fn and Ctrl keys on the Surface are swapped compared to the MacBook and I'm still adjusting to that.  Eventually, as I get used to it, this issue should become less frequent but it certainly won't go away completely.

There Is No Fix

Now you'd think there'd be some work around for this right?

Well if you search you'll find suggestions like pressing Fn+CapsLock or pressing and holding Fn for 10 seconds.  Oh how I wish these ideas worked - they might on some Surface models, but they absolutely do not work on a Surface Laptop 4.  

(Microsoft Support: stop suggesting these ideas - they don't work, you should know that)

There is no firmware setting for this.

What's worse, the Fn key appears to be completely implemented in firmware. Windows doesn't see the Fn key presses so this can't be worked around in software.  No amount of key intercepting or key remapping can fix this.

So until Microsoft decide to fix this (presumably with a firmware update, assuming they decide to and that it's even possible) this is a problem that anyone with a Surface Laptop 4 is stuck with.

Please, please, please Microsoft...

Microsoft you have an excellent machine here but:

I hate, hate, hate that stupid f***ing Fn key.

Please fix it.

(And while you're at it, long press for the power button and Fn+Backspace for delete would be the icing on the cake).

When you install multiple copies of Windows on machine, Windows updates it's boot manager configuration so that at boot time you can choose which version you want to run.  This works fine if you're only running Windows...

If you're using a third-party boot manager like Grub or rEFInd it's less than ideal because it becomes a two-step process - first you need to choose Windows Boot Manager and then from the Windows boot manager choose which version of Windows.

But wait, it's even worse than that.  If you choose the non-default Windows installation the Windows boot manager reboots the machine before launching the selected operating system... so you need to go through your first boot loader again.

On my machine, getting into Windows 10 went like this:

1. Machine boots, rEFInd menu appears with Windows and Ubuntu options
2. Choose Windows
3. Windows boot menu appears, with Windows 10 and Windows 11
4. Choose Windows 10
5. Machine reboots and goes back to the rEFInd menu again
6. Choose Windows again
7. Windows 10 boots.

What's needed is a way to split up the two Windows entries so other boot loaders can see them as separate operating systems.

A Little Background

On EFI systems there's a special partition called the EFI System Partition (aka the ESP). This FAT32 formatted partition stores the boot loaders for all the installed operating systems.

On a Windows machine you can get to the ESP with the following command from an Administrator command prompt.

> mountvol b: /s

If you inspect the folder b:\EFI you'll see folders for each of the installed operating systems and boot tools.  

The Windows boot loader is in the folder b:\EFI\Microsoft\Boot .  Inside that folder is a file BCD that stores the boot configurations for the installed versions of Windows.

The problem is that third party bootloaders typically create menu entries based on the folders found in the EFI directory.  Because there's only one folder for Windows only one menu item appears.  The trick is to create two separate folders for Windows - each booting a particular version.

Note that all this only applies if the second installation of Windows found the original ESP and updated it.  If you disconnect the original ESP drive when you install the second version of Windows it'll create a new ESP on the installation drive and your boot manager should find both when you reconnect the original drive.  In this case you'll automatically get two menu entries.

The Fix

The basic idea here is to create two copies of the Windows boot loader folder and edit the contained BCD file in each to only reference one installation of Windows instead of both.

The following assumes you're using rEFInd and I've only tested it with rEFInd. The same approach should work with other boot managers but might require additional configuration of the boot manager.

Assuming you have Windows 10 and Windows 11 installed, here's how you can split the Windows boot loader:

1. Make sure you know what you're doing.  If you mess up the ESP you can end up with an unbootable machine.  Be careful.
2. Mount the ESP as described above
3. Create two copies of the b:\Microsoft\Boot folder as b:\EFI\win10 and b:\EFI\win11. eg:
   xcopy /s b:\EFI\Microsoft\Boot b:\EFI\win10
xcopy /s b:\EFI\Microsoft\Boot b:\EFI\win11
   (Note these folders must be in the \EFI folder, and not in the \EFI\Microsoft folder otherwise rEFInd won't find them).
4. List out the contents of the BCD file with this command:
   bcdedit /store b:\EFI\win10\BCD /enum.  
   You should see three entries: one titled "Windows Boot Manager" and two titled "Windows Boot Loader" (one for each installed version of Windows). Note of the identifier value listed under each boot loader entry - you'll need these for the next two steps.
5. Remove the Windows 10 entry from the Windows 11 folder:
   bcdedit /store b:\EFI\win11\BCD /delete {ID_FOR_WIN10}.
6. Vice-versa for the other OS:
   bcdedit /store b:\EFI\win10\BCD /delete {ID_FOR_WIN11}.

You'll now have two new, but separate boot folders for each version of Windows. Since each folder is now only configured for just one operating system the Windows boot loader won't prompt to select a version.

Reboot your machine and check that rEFInd has two new entries for Windows 10 and Windows 11 and check they both boot directly into the appropriate OS.

Finishing Touches

The rEFInd menu will probably now have a total of three entries for Windows - the original one and the two you just created.  To hide the original Windows boot manager just select it and press Delete.  You can get it back through the hidden items menu.

Finally, if you're after a nice clean theme for rEFInd here's one I put together that includes an updated icon for Windows 11's new logo. (get it here).

nvpatch is a command line utility that patches Windows x86 and x64 .exe files to include the export symbols required for some machines to enable their discreet GPU.

Although called "nvpatch" it works for both NVidia and AMD GPUs with appropriate drivers installed. It was originally written to be used with Sector's Edge, a game on which my son Mitch is the lead developer.

This article explains how it works. If you just want to get it and use it, then see here for instructions.

Background

NVidia Optimus and AMD Enduro are technologies that switch GPU behaviour between low power and high performance modes. One of the ways the drivers determine which mode to run is to look for special symbols exported from the main .exe of the process.

Typically graphics intensive applications like games will have these symbols included in their .exe files to enabling switching to the high performance GPU mode.

The NVidia drivers look for an export symbol named NvOptimusEnablement while the AMD drivers look for AmdPowerXpressRequestHighPerformance. In both cases the exported symbol refers to a 32-bit integer where a value of 1 indicates high performance mode should be enabled.

While these symbols are trivial to add to C and C++ program, for other languages it's more difficult. In C# for example, it's not possible to export native symbols. One solution is described here by Lucas Magder where he decompiles the exe IL, patches the IL to make an export symbol, recompiles and then patches the exported data at runtime.

That approach works in previous versions of .NET but with .NET 5 the executable is actually a stub program that launches the .NET runtime and then loads your program from an associated assembly dll - and the export symbols need to be on the .exe and not the .dll. In other words the .exe is produced by the Microsoft toolchain and your program has no influence over its content.

There's a couple of options here:

1. Petition Microsoft (and perhaps other language vendors) to add support for this in their stub .exe files.
2. Petition NVidia and AMD to provide alternative mechanisms to enable these features
3. Work out how to build the .NET stub executable and add those symbols
4. Get creative and patch the exe to add these symbols

I'm not going to hold my breath for options 1 and 2. Option 3 is the most technically correct but seems fragile and probably complicated to setup a build environment for such a trivial change.

Option 4 sounds complicated but it's actually not that hard and a fun dive in the PE .exe file format.

PE File Format Overview

Windows .exe files are in the Portable Executable (aka "PE") file format. While the Microsoft documentation on the PE Format is a very long document, we only need to understand a few basic concepts and one section in detail in order to patch in these new symbols.

The basic format of a PE file is simply a bunch of headers followed by a bunch of sections. The headers provide important information for the Windows loader (as well as pointers to significant data in the sections), while the sections contain the actual data and code that's loaded into memory by the loader.

In order to add new symbols we're interested in the Export Table. While the documentation suggests that the export table lives in a special ".edata" section, in practice it can reside in any section and will often be found in the ".rdata" section along with other initialized read-only data. To find the export table, we can't just look for the ".edata" section. Instead, in among the headers is a data directory entry that points to the export table - in whatever section in happens to live.

How It Works

So this is how nvpatch does its tricks:

1. Loads the .exe and locates all the various headers and sections
2. Finds the export table (if it exists) and parses it into its own set of data structures so it can be manipulated
3. Adds the new symbols to the parsed export table
4. Re-writes the modified export table to a new section at the end of the file called ".nvpatch" along with the 0x00000001 data constants that the symbols point to
5. Inserts a new section header in the headers area that points to the new .nvpatch section
6. Updates the Export Table data directory entry (in the header area) to point to the new export table (in the .nvpatch section)
7. Updates various sizes and counts in the headers so everything checks out
8. Rewrites all the changes as new .exe file

Note that if the exe had an existing Export Table (many exe files don't) it's left in the file - but nothing points to it so it's ignored. The reason the existing table isn't updated is there's no guarantee there will be room to extend the existing table without overwriting other important data. It's simpler and safer to just rewrite the table to a new section.

Note too, that by good luck there is almost always room at the end of the existing section header table to insert a new section header. That's because the section headers are the last of the headers and the actual section data that follows is typically aligned to 512 byte boundaries meaning there's usually room there. If by bad luck there isn't room, nvpatch will fail.

About the Code

nvpatch is written in C#. It could have been written in any language really, but C# means it can be easily packaged up as a dotnet tool for publishing.

The code is not at all shy about using unsafe code and pointers. In fact much of the code looks more like C.

• PEFile - the main class the reads and writes the .exe files and provides helpers for adding new sections
• PEExportTable - the class responsible for reading and writing the Export Table
• PESectionBuilder - helper class for adding new sections
• PEStructs.cs - C# definitions of various structures used in the PE format
• Utils.cs - various utilities functions
• Program.cs - logic to actually patch the exe

Just to explain the PEFile class a little more, it works like this:

1. Reads the entire .exe into a byte array
2. Pins the array and gets a fixed pointer to its content
3. The various header addresses are calculated and available as direct pointers into the loaded byte array as PEFile properties. These pointers are used to directly read and manipulate data in the headers.
4. The AddSection method creates a new PESectionBuilder instance that has a MemoryStream into which the new section content can be written.
5. When the file is rewritten, the originally loaded byte array (which has now be modified) is written first, followed the contents the memory stream of the PESectionBuilder of any new sections.

Limitations

In the interest of expediency (aka laziness) I've taken a few shortcuts that introduce a couple of limitations:

• Only the PE32+ file format (as used by x64) is supported. The PE32 (without the plus) format typically used by x86 executables isn't supported and the tool will fail with an error message. It should be reasonably easy to add support for this, but I just haven't bothered. x86 support has now been added (12 Jan 2026), but has had minimal testing. Let me know if you find issues.
• If there's no room for a new section header it will fail with an error message.
• The export table reading doesn't handle forwarding exports. It doesn't even try to detect nor warn about them.

That's it!

Recently I've been working on a new theming engine for my music app Cantabile and ran across the need for an algorithm that I've not seen discussed in computer science circles before.

The theming engine is built around a custom language called GTL (GuiKit Theming Language) that has a feature where different visual representations for a UI element can be specified based on the current state of that element.

For example, you can specify different colors for a control based on the control's current state:

BackgroundColor:
{
    Checked|Pressed: Color.Blue,
    Checked: Color.LightBlue,
    Else: Color.Black,
}

Currently GTL expects these states to be specified as a bitmask and evaluates them to true when (ControlState & BitMask) == BitMask. This is fine for many cases but is limited in that you can only specify a set of bits that must be set. What if I want to test that one of two bits are set, or that a bit isn't set?

What's really needed here are boolean expressions, or more specifically "Bit Flag Boolean Expressions".  That is, expressions that use typical C style boolean operators ( && , || , and ! ), but work on the individual bits in an input word.

• Checked && Pressed
• Focused && !Disabled
• Focused || Selected

Besides being more flexible in the types of conditions that can be expressed, boolean expressions are also a more intuitive way to express these conditions. eg: Checked | Pressed reads as "checked or pressed", but the condition we're actually trying to describe is "checked and pressed".

While it's pretty easy to parse and evaluate a boolean expression walking and evaluating an expression tree is going to be slower than a simple bit mask and test where multiple boolean operations can often be reduced to a single operation.

But what if we could convert the expression tree to a series of bit mask and test operations automatically? So, the question is:

How do we convert an abstract syntax tree for a boolean expression into an optimal set of mask and test operations?

I posted the question to StackOverflow, but ended up finding a good solution myself and thought it was worth writing up.

Tokenizing and Parsing

I've written about tokenizing and parsing expressions into abstract syntax trees before so I won't cover it again here.  If this is new to you, see this article.

For this algorithm to work properly the AST needs to represent boolean AND and OR operators as multi-input nodes rather than a chain of binary nodes as is often seen in expression syntax trees.

Since these operations are commutative (ie: can be evaluated in any order) making them all inputs to a single node provides more opportunities to re-order and coalesce boolean operations into a wider bitmask operation.

For an existing AST/parser implementation this might involve:

1. Updating the AST nodes for boolean AND and OR to accept multiple inputs
2. Updating the parser to parse chains of AND and OR operations into a single node
3. Updating the parser to simplify the AST so that it promotes nodes of the same type into their parent node.  eg: most parsers would produce two binary AND nodes for this expression: A && (B && C) but ideally this should be flattened to one three input node: A && B && C.

The Algorithm

Now that we've got an AST tree in suitable format, lets think about the algorithm. Most of these boolean operations can be reduced to one of two forms of bitmask operations:

• (input & mask) == testValue
• (input & mask) != testValue

The first form which I call MaskEqual is used for boolean AND operations. eg: the boolean expression A && B && !C becomes (input & (A|B|C)) == (A|B)

The second form which I call MaskNotEqual is used for boolean OR operations. eg: the boolean expression A || B || C becomes (input & (A|B|C)) != 0.

Note: throughout this article and in the code base I use the single capital letter symbols such that A = 0x01, B = 0x02, C = 0x04 etc...  So A && B && !C can also be expressed in bitwise form as (input & 0x07) == 0x03.

Next we have expressions that always evaluate to true or false:

• A && !A is always false
• A || !A is always true

And finally, we have expressions that can't be reduced to a single bitwise operation.  eg:  the best we can do with this:

A && (B || C)

is this:

((input & 0x1) == 0x1) && ((input & 0x6) != 0x0)

For those cases we have EvalAnd, EvalOr and EvalNot.

Based on the above we need to calculate an execution plan for every node in the tree where each plan will be one of the following types:

enum ExecPlanKind
{
    True,
    False,
    MaskEqual,
    MaskNotEqual,
    EvalAnd,
    EvalOr,
    EvalNot,
}

Each execution plan node will also have additional data depending on its type:

• True / False - no other data
• MaskEqual / MaskNoteEqual - an associated mask and test value
• EvalAnd / EvalOr / EvalNot - a set of input execution plan nodes

The goal of the algorithm is walk the AST and build a tree of execution plan nodes that minimizes the number of EvalAnd, EvalOr and EvalNot operations - since these require extra steps to execute.

One thing to note about the MaskEqual and MaskNotEqual execution plans is that if the mask has only a single bit set then it's possible to switch the plan from one kind to another by flipping the unmasked bits in the test value and changing the plan kind.

eg: (value & 0x01) == 0x01 is the same as (value & 0x01) != 0x00.

If more that one mask bit is set then the plan can't be converted to the other kind.

Next, let's think about how to translate each node in the AST into an execution plan node.

The Identifier Node

The identifier node represents a name in the expression (eg: A, B, C etc...) and has an associated bit that it represents in the input value.  The execution plan for this kind of node is trivial:

• Kind:ExecPlanKind.MaskEqual
• Mask: the identifier bit value
• TestValue: the identifier bit value

In other words, the expression A which has an bitmask value of 0x01 can be evaluated as (input & 0x01) == 0x01.

The Not Operator

The Not operator has a single input node.  To generate an execution plan, first we calculate the execution plan for the input node and depending on its ExecPlanKind we create a new execution plan that inverts it.

• ExecPlanKind.True => ExecPlanKind.False
• ExecPlanKind.False => ExecPlanKind.True
• ExecPlanKind.MaskEqual => ExecPlanKind.MaskNotEqual (keeping the same mask and value)
• ExecPlanKind.MaskNotEqual => ExecPlanKind.MaskEqual (keeping the same mask and value)
• Otherwise ExecPlanKind.EvalNot, with the input plan of the input operand as the argument

The And and Or Operators

The And and Or operators are the most complex, but very similar to each other.

Here's the logic for the And operator:

1. Calculate the execution plan for each of the inputs and place them in a collection.
2. If any of the input plans are ExecPlanKind.False then regardless of the other inputs the result is also ExecPlanKind.False.
3. If all of the input plans are ExecPlanKind.True the the result is also ExecPlanKind.True.
4. Remove any nodes from the collection that are ExecPlanKind.True since they don't contribute anything to the result.
5. Where possible, convert input plans of type ExecPlanKind.MaskNotEqual to ExecPlanKind.MaskEqual. Without this conversion, expressions like A && B && !C can't be reduced because of the way the Not operator works. (see the note above about only converting these when a single bit is set).
6. Coalesce all ExecPlanKind.MaskEqual input plans into a single MaskEqual plan that Or's the input masks and test values together.  The only catch here is to detect cases where the there's a conflicting test value bit for any of the masked bits.  Such a case will always be false (eg: A && !A) and if detected the execution plan for this node becomes just ExecPlanKind.False.
7. After applying the above steps if there's only one input plan left in the collection then that plan becomes the plan for this node.
8. Otherwise, there are multiple input plans left in the collection and they need to be evaluated sequentially at runtime. The plan for this node becomes ExecPlanKind.EvalAnd with the current collection of input plans as its input.

As mentioned the Or operator is basically the same with some of the logic flipped - see the source code for details.

Executing the Execution Plan

The output of the above algorithm is an execution plan and to execute it we just need an input value to test against:

public bool Evaluate(ulong input)
{
    switch (Kind)
    {
        case ExecPlanKind.True: 
            return true;

        case ExecPlanKind.False: 
            return false;

        case ExecPlanKind.MaskEqual: 
            return (input & Mask) == TestValue;

        case ExecPlanKind.MaskNotEqual: 
            return (input & Mask) != TestValue;

        case ExecPlanKind.EvalAnd: 
            return InputPlans.All(x => x.Evaluate(input));

        case ExecPlanKind.EvalOr: 
            return InputPlans.Any(x => x.Evaluate(input));

        case ExecPlanKind.EvalNot: 
            return !InputPlans[0].Evaluate(input);
    }
}

Testing and Results

To verify the results of the optimized execution plan, an expression evaluator that works directly using the AST was also implemented and the results compared with the optimized plan over a range of inputs and against a representative set of expressions

To get an idea of the kinds of operations that are generated by this algorithm, the sample program displays the boolean expression and its equivalent bitmask expression:

A && !A  =>  false
A || !A  =>  true
A  =>  (input & 0x1) == 0x1
B  =>  (input & 0x2) == 0x2
C  =>  (input & 0x4) == 0x4
D  =>  (input & 0x8) == 0x8
A && B  =>  (input & 0x3) == 0x3
A || B  =>  (input & 0x3) != 0x0
A && (B || C)  =>  ((input & 0x1) == 0x1) && ((input & 0x6) != 0x0)
(A && B) || C  =>  ((input & 0x4) != 0x0) || ((input & 0x3) == 0x3)
(A && B) || (C && D)  =>  ((input & 0x3) == 0x3) || ((input & 0xC) == 0xC)
(A || B) && (C || D)  =>  ((input & 0x3) != 0x0) && ((input & 0xC) != 0x0)
(A || B) && (C || D) && (A || C) && (A || D)  =>  ((input & 0x3) != 0x0) && ((input & 0xC) != 0x0) && ((input & 0x5) != 0x0) && ((input & 0x9) != 0x0)

But what about performance?  On the above set of expressions the optimized execution plans ran on average more than 60% faster that the non-optimized version. (approx 2.9 down to 1.1 seconds)

More Performance with ILGenerator

I really wanted to squeeze as much performance as I could out of these expressions since the UI library calls them fairly regularly during rendering and control state updates.

One of the coolest features of .NET are dynamic methods - the ability to generate IL code at runtime that effectively gets compiled to machine code.

Given the optimized execution plans from above it's really quite simple to generate IL code to actually execute them.  Here's the entire function that generates the IL for an execution plan:

void Emit(ExecPlan plan)
{
    switch (plan.Kind)
    {
        case ExecPlanKind.True:
            _il.Emit(OpCodes.Ldc_I4_1);
            break;

        case ExecPlanKind.False:
            _il.Emit(OpCodes.Ldc_I4_0);
            break;

        case ExecPlanKind.MaskEqual:
            _il.Emit(OpCodes.Ldarg_0);
            _il.Emit(OpCodes.Ldc_I4, plan.Mask);
            _il.Emit(OpCodes.And);
            _il.Emit(OpCodes.Ldc_I4, plan.TestValue);
            _il.Emit(OpCodes.Ceq);
            break;

        case ExecPlanKind.MaskNotEqual:
            _il.Emit(OpCodes.Ldarg_0);
            _il.Emit(OpCodes.Ldc_I4, plan.Mask);
            _il.Emit(OpCodes.And);
            _il.Emit(OpCodes.Ldc_I4, plan.TestValue);
            _il.Emit(OpCodes.Ceq);
            _il.Emit(OpCodes.Ldc_I4_0);
            _il.Emit(OpCodes.Ceq);
            break;

        case ExecPlanKind.EvalAnd:
            {
                var lblFalse = _il.DefineLabel();
                var lblDone = _il.DefineLabel();
                for (int i = 0; i < plan.InputPlans.Count; i++)
                {
                    // Generate the input plan
                    Emit(plan.InputPlans[i]);
                    _il.Emit(OpCodes.Brfalse, lblFalse);
                }
                _il.Emit(OpCodes.Ldc_I4_1);
                _il.Emit(OpCodes.Br_S, lblDone);
                _il.MarkLabel(lblFalse);
                _il.Emit(OpCodes.Ldc_I4_0);
                _il.MarkLabel(lblDone);
                return;
            }

        case ExecPlanKind.EvalOr:
            {
                var lblTrue = _il.DefineLabel();
                var lblDone = _il.DefineLabel();
                for (int i = 0; i < plan.InputPlans.Count; i++)
                {
                    // Generate the input plan
                    Emit(plan.InputPlans[i]);
                    _il.Emit(OpCodes.Brtrue, lblTrue);
                }
                _il.Emit(OpCodes.Ldc_I4_0);
                _il.Emit(OpCodes.Br_S, lblDone);
                _il.MarkLabel(lblTrue);
                _il.Emit(OpCodes.Ldc_I4_1);
                _il.MarkLabel(lblDone);
                break;
            }

        case ExecPlanKind.EvalNot:
            {
                Emit(plan.InputPlans[0]);
                _il.Emit(OpCodes.Ldc_I4_0);
                _il.Emit(OpCodes.Ceq);
                break;
            }

        default:
            throw new NotImplementedException();
    }
}

Using the above approach, performance jumped to almost 90% faster than directly evaluating the unoptimized tree.  (approx 2.9 down to 0.4 seconds). Well worth the effort!

About the Code

The code for this is available here.  Some notes:

• A Visitor Pattern is used for walking the AST
• It should probably use the Visitor pattern for ExecPlan nodes too (but it doesn't)
• Most of the logic can be found where you'd expect - the Tokenizer is in Tokenizer.cs, the Parser in Parser.cs etc...
• The Evaluator class evaluates an unoptimized AST tree against an input value
• The Planner class produces an optimized ExecPlan from a supplied AST
• The Compiler class generates IL code for a suppliedExecPlan
• The Logger class is used log an expression AST to the console
• All the AST nodes are in AstNodes.cs
• The IBitNames interface allows plugging in a mapping from expression identifier to bit mask
• The BitFromLetter class provides a hardcoded implementation of IBitNames where A = 0x01, B = 0x02, C = 0x04 etc... and is used only for testing.
• The EnumNames class provides an implementation of IBitNames that retrieves bit values from a C# enum type.

Finally, the Compiler class also includes this method:

public static Func<T, bool> Compile<T>(string expression) where T: Enum

It can be used to create an IL optimized method for an expression based on a C# enum:

[Flags]
enum Fruit
{
    Apples = 0x01,
    Pears = 0x02,
    Bananas = 0x04,
}

var compiledExpression = Compiler.Compile<Fruit>("Apples && (Bananas || Pears)");
var result = compiledExpression(Fruit.Apples|Fruit.Bananas);

The compiler supports generating IL code for enum types with a 8, 16, 32 and 64-bit underlying types.

Now I just need to retrofit it into GTL.

PS: If you've seen this or a similar algorithm before, I'd be interested in reading about it - let me know.

One of my favourite PS3 games was Need for Speed: The Run. When I saw the PC version on sale I couldn't resist grabbing a copy to see if I could get it to work on my new Linux gaming machine (which I wrote about here).

The Run isn't listed on ProtonDB so there was a chance it wouldn't be playable but at just $5 there wasn't much to lose. Since this was the first time I'd tried a non-Steam game under Proton I knew there'd be some tinkering around but I got it working in the end.

Update 1

Since posting this article there's a been some discussion on Reddit about why this is necessary:

• "Why not just use Lutris?" No reason except that I just like using Steam as the launcher for this lounge-room based, controller-only gaming machine. I personally haven't looked into Lutris, but have only heard good things about it. For me, everything else I play is in Steam, it works fine and I just wanted to add this one non-Steam game.
• "Why do this when EA Games already install OriginThinSetup." This is specifically for games that aren't on Steam, in this case NFS The Run.

Update 2

Since posting, EA has shutdown the servers causing an infinite hang when starting the game showing "Connecting to Auto Log servers". On Windows this can be worked around by setting up a firewall rule to block the game .exe file.

Since Linux doesn't seem to support firewall blocking by process, certainly not by process name, and definitely not for Wine process I did some digging and figured out the actual ports to block. The following two ufw rules seems to let the game run again:

sudo ufw reject out 42127/tcp
sudo ufw reject out 1900/udp

Actually, only the first rule is required, but in trying to figure this out I noticed it was connecting to 1900/udp as well... might as well block it too.

Ugh, EA Origin

Unfortunately, the only way to download, install and run most EA games is via their launcher Origin. It's like EA's version of Steam but crappier - especially for lounge room gaming machines that don't have a mouse or keyboard since it doesn't support controllers.

Luckily there's a way to launch Origin and then get it to run a specific game - which I'll cover below. Unfortunately, there doesn't seem to be a way to have it automatically shutdown when you close the game so that needs to be done manually.

This post explains the best way I found to set it up. There might be other better ways, in which case please let me know.

Here's How...

1. On a Windows machine, download OriginThinSetup.exe from their site. You need to do this because viewing the site from a Linux machine doesn't give the Windows download option. (Alternatively, Redditor GGG_246 informs these are also available at winehq)
2. Transfer OriginThinSetup.exe to your Linux machine. It doesn't matter where you put it but your Downloads folder is a good option.
3. In Steam, choose the "Add non-Steam Game" command and select OriginThinSetup.exe from where ever you placed it. Also, choose to run it using Proton. I used Proton 5.0.
4. Start the newly added "game" ie: the Origin installer and install it.
5. Once Origin is installed you can launch it directly from its installer. Login to your account and choose to download and install the game.
6. You should now be able to run the game and with a little luck it should basically work.

Now that Origin and the game are installed, the trick is figuring out how to start it directly instead of running the Origin installer again. The method I ended up using was a bash script:

1. Close Origin if it's still running.
2. Go to the directory ~/.steam/steam/steamapps/compatdata/ and look for a sub-directory named with 10 digits. In my case it was called 3627082160. If you have multiple directories go into each one and work out which has the Origin.exe program. It should be in a sub-folder named pfx/drive_c/Program Files (x86)/Origin/Origin.exe.
3. Next you'll need to create a bash script with the code shown below.
4. In the script update the variable COMPATDIR from 3627082160 to whatever the folder is called on your machine.
5. Also update the variable GAMEID to the Origin Id of the game you installed. You can get this by logging into origin.com and clicking on the game in your library and the game ID will show up in the URL (see screen shot below). The Origin Game Id for NFS The Run is 231088400.
6. If you've got other versions of Proton installed you can experiment with the PROTONVER variable in the script to change which version will be used. I found for The Run, Proton-5.21-GE-1 worked best.
7. Save the script somewhere convenient (I just put it in my home directory) and use chmod to mark it executable. eg: ~$ chmod +x nfstherun
8. Back in Steam, delete the previously created "non-Steam" shortcut to OriginThinSetup.exe.
9. Use the Add non-Steam game command again to add a shortcut to the script (note this time don't choose to run under Proton as this will cause Steam to create a second compatdata prefix directory which we don't want as we've already got everything setup in the existing prefix).
10. Finally you can set and icon and grid artwork as you would for any other non-Steam game.

Here's the script:

#!/bin/bash

# Set this the folder where Steam created the Origin prefix
COMPATDIR=3627082160

# Set the to the Origin Game ID of the game to launch
GAMEID=231088400

# Pick a Proton Version
#PROTONVER=steam/steamapps/common/Proton\ 5.0
PROTONVER=root/compatibilitytools.d/Proton-5.21-GE-1

# Location of Origin.exe within the compatdata folder
ORIGIN_EXE="pfx/drive_c/Program Files (x86)/Origin/Origin.exe"

# Steam prefix directory
export STEAM_COMPAT_DATA_PATH=~/.steam/steam/steamapps/compatdata/$COMPATDIR/

# Proton settings
export PROTON_USE_WINED3D=0

# Run
~/.steam/$PROTONVER/proton waitforexitandrun \
    "${STEAM_COMPAT_DATA_PATH}${ORIGIN_EXE}" \
    origin://LaunchGame/DR:${GAMEID}

In Practice: Origin

That's everything I did to setup Origin on my lounge room gaming machine. There's a couple of caveats:

1. For some reason sometimes the game either takes a really long time to start, or never starts. I've found that moving the mouse cursor around using the track pad on the PS4 controller seems to hurry this along quite a bit.
2. Once the game is closed, Origin will rear it's ugly head. I haven't found a way to prevent this so I just use the controller track pad to shut it down. Unfortunately you can't just leave it running because if you launch the game again it doesn't seem to start. (For a possible work around for this, see this reddit post by lucasrizzini)

In Practice: NFS The Run

As for NFS The Run, it seems to run really well and mostly looks like any other game in Steam:

There are a couple of minor issues:

• Proton 5 seemed to give fairly frequent micro-stutters. Switching to Glorious Eggroll 5.1 seemed to really help this. There's still the occasional stutter but I seem to remember similar behaviour on the PS3 - it could just be the game.
• Some of the instruction popup screens appeared blank with no text and just a close button. This didn't bother me since I knew the game anyway.
• In the snow levels the kicked up spray from other cars appears like black diesel smoke instead of a white mist. I didn't notice this on PS3 or in online videos of the PC version so I'm guessing this might be a bug in Proton.
• If you disable V-Sync, the same kicked up spray renders really weirdly in front of your own car and rises vertically from other cars. This is a known bug in the PC version and nothing to do with running under Linux/Proton.
• There's some lip-sync issues in the cut scenes. Not sure if this is a problem with Linux/Proton or just a problem with PC edition of the game. This didn't happen in the PS3 version. No big deal.

On the positive side, I've played through the entire "Run" part of the game and it's very playable - better than the PS3. On my GTX-2070 I can set all graphics settings to ultra and run it at 1920 x 1080, the sound is great, PS4 controller works well (although requires mental mapping of Playstation buttons to ABXY style buttons), it looks better than PS3 and I feel like I can see further down the road.

I also have a suspicion things are slightly better balanced on the PC. Some levels on the PS3 version seemed unusually difficult compared to the levels before and after and I didn't notice it this time through.

TL;DR: Definitely playable and a ton of fun :)

This video finishes the implementation of Undo/Redo in the view as well as support for multiple views and plain text clipboard operations.

For source code, see this tagged branch of the RichTextKit repo.

Got questions or comments? Find me on Twitter - @toptensoftware

This video looks at the document side aspects of undo/redo support.

For source code, see this tagged branch of the RichTextKit repo.

Got questions or comments? Find me on Twitter - @toptensoftware

In this video we reach a bit of a milestone with basic edit operations now working!

Got questions or comments? Find me on Twitter - @toptensoftware