In depth overview

How does dart_eval work?

Note: Chinese users may want to refer to @maxiee's blog posts about dart_eval.

dart_eval has two fundamental components: the compiler and the runtime. The runtime can be further broken down into sub-components: the bytecode VM and the runtime bridge. Furthermore, there are several ‘supplemental’ components such as the eval() function, runtime overrides, and the Dart standard library bindings.

Let’s go over each of these in a bit more detail, starting with the compiler.

The compiler

The compiler’s entrypoint is compiler.dart. This file contains most of the steps needed to prepare for compilation. A user typically calls it using the compile() method, which is simply a shorthand for the compileSources() method that performs the real processing.

Before we actually compile the Dart code, a few things must be set up.

1. Parsing

First, the source code must be parsed, from text into an abstract syntax tree (AST). While parsing is a whole topic unto itself, dart_eval simply relegates this task to the Dart analyzer package using its parseString() method. This turns code similar to this:

import 'dart:math';
	
int main() {
   return min(1, 2 + 3);
}

Into a tree like this (simplified):

CompilationUnit (main.dart)
> ImportDirective ('dart:math')
> FunctionDeclaration ('main', returns: 'int')
   > BlockStatement
      > ReturnStatement
         > MethodInvocation ('min')
             > IntegerLiteral (1)
             > BinaryExpression (+)
                > IntegerLiteral (2)
                > IntegerLiteral (3)

2. Building libraries

Second, we must combine Dart files into logical “libraries”. For most code, each Dart file is a standalone library, but using the part/part of syntax multiple Dart files can be combined into a single library. This is a classic graph algorithm, and like the official Dart compiler, dart_eval uses the Djikstra path-based strongcomponent algorithm to find "strongly connected components", i.e. groups of files where there is both a reference from the root file to its parts (“part x.dart”) and from each part back to the root (“part of y.dart”). Also in this step, bridge libraries that share an identical URI have their declarations merged with parsed libraries.

3. Resolving imports and exports

Next, we must resolve each library’s imports and exports. To be exact, the goal of this step is to find all of the declarations that should be visible to each library when it is compiled - i.e. if ClassA is defined in a.dart and b.dart imports a.dart, a function in b.dart should be able to instantiate ClassA; however, a function in c.dart that does not import a.dart should throw a compile error if you attempt to instantiate ClassA.

This step uses a two-pass algorithm to resolve all declarations visible to each library. First, build an export graph from all of the libraries’ exports. Unlike the part/part of graph from earlier, this is a directed graph - essentially a tree, except permissive of cyclic references - linking together libraries based on their export directives. Second, for each library we're resolving, iterate through each of its imports and find all declarations exposed by the import, both directly and through the export graph, taking into account show and hide combinators. This step also groups prefixed imports into a second layer.

4. Populating lookup tables

During compilation, the compiler needs to be able to look up declarations quickly based on their names. In this step, several maps are formed to allow this, including a top-level declaration map and instance declarations map.

5. Creating type references

The compiler now creates and caches types for each class present in the source code and each bridge class. These types are unresolved for now, meaning they don't have information about what other types they extend/implement/mixin.

6. Resolving visible types

The compiler now uses the cached type refs and the resolved imports and exports to build a simple String mapping of all types visible to each library. When compiling the code, we can reference this map to figure out what, for example, ClassA means in the current context. Since earlier types are overwritten by later ones, it will only resolve to one type.

7. Assign static and global indices

For efficient access, all static functions and global values (top-level variables) are assigned a unique integer index, starting at 0 and incrementing.

8. Compile!

Finally, it's time to actually compile some code!

The dart_eval compiler starts by compiling static fields and top-level variables to infer their type, before moving on to compiling the rest of the code. Unsurprisingly, compilation can take many different paths depending on what is being compiled. In general, compilation starts at the declaration level (class, function, field, constructor). Many declarations contain statements, such as blocks, loops and returns, as well as expressions, such as assignments and method calls.

This document is incomplete. It will continue to be updated.