Swift AST written in Swift. Part 1 of ∞

I have to confess. I love types. I love power and constraints that type system brought to you. I don’t love typing, so I love when type inference allows me to not carry my types with me.

And in my possession with types, I want to create something significant, something that can show the power of strong typing. I want to build Swift AST in Swift type system.

AST (Abstract Syntax Tree) — machine readable representation of your code. This representation allows compilers to manipulate different parts of your program, infer types, perform optimizations.

In Swift, you can examine it syntax in a separated C++ library. This is some example of building tree nodes from code:

auto NewIdentifier = SyntaxFactory::makeIdentifier(
    "YourStruct",
    MyStruct.getIdentifier().getLeadingTrivia(),
    MyStruct.getIdentifier().getTrailingTrivia()
);

MyStruct.withIdentifier(NewIdentifier).print(llvm::outs());
// Result
struct YourStruct {}

Swift AST is a huge and complex data type, I want to build the small library which allows you to manipulate Swift code inside a Swift code. If you want to experience real Swift meta-programming check out Sourcery lib.

In this part, I will go from the top level of grammar. You can find full Swift grammar here.

So far so simple. Our AST will consist of an optional list of statements. In Swift, we have an optional concept, but we don’t have a List concept. What to do?

We can combine these two concepts and use Array. The empty array will present absent list, and the non-empty array will present regular list.

struct AST {
    let declarations: [Statement]
}

Ok, we need to go deeper and define Statement type. Let’s look into grammar:

So many options! Looks like Statement is a polymorphic type. And can represent a lot of different things, but only 1 at a time. This kind of types usually called type unions.

In Swift, you can model type unions in a several ways, each with its own pros and cons.

1. Class inheritance. This approach allows to inherit both: interface and implementation; requires careful design and explicit open/final declarations. Considered fragile in a modern rapidly changed software.
2. Protocol inheritance — modern and more functional approach to inheritance. Allow only single level of inheritance, composable and scalable. Allow to model “open” type union.
3. Enums — functional approach to type unions. Form “closed” type union. Cannot be extended after the declaration. Can be used as a standalone type.

In this case, I will prefer enums (I often prefer enums) because they can be modeled as standalone type.

enum Statement {
    case expression(Expression)
    case declaration(Declaration)
    case loop(LoopStatement)
    case branch(BranchStatement) 
    case labeled(LabeledStatement) 
    case controlTransfer(ControlTransferStatement)
    case `defer`(DeferStatement)
    case `do`(DoStatement)
    case compilerControl(CompilerControlStatement)
}

What we have now? We can build our AST as array of some statements. We still cannot provide details about our statements, but at least we can build them. Let’s try to count number of branch statements in our AST:

func numberOfIfs(in ast: AST) -> Int {
    let branches = ast.declarations.filter {
        guard case Statement.branch = $0 else { return false }  
        return true
    }
    return branches.count
}

This filter call looks awfull. Our statement need more interface, lets add some checkers to it.

extension Statement {
    ...
    var isBranchStatement: Bool {
        if case .branch = self { return true }
        else { return false }
    }
    ...
}

Now we can rewrite our counter as one liner:

func numberOfIfs(in ast: AST) -> Int {
    return ast.declarations.filter { $0.isBranchStatement }.count
}

In next article we will dive into Declaration type. You can look at source from this article at this gist: https://gist.github.com/AlexeyDemedetskiy/9a2089b9fed6266517687d73fd9e4d6b