overview

A CAD program like Antimony has to keep track of many small pieces of data. For example, a 2D point has x and y coordinates:

2D point

One of the major design decisions in Antimony is that every datum is a piece of code. This means we can put arbitrary expressions into the point's coordinates.

Object properties are also free to refer to each other, with the graph acting as a local namespace. Given a point named p with properties x and y, a datum could refer to p.x or p.y:

2D point with equations

This brings us to the challenge: how do we build a system to represent this set of datums-as-code, tracking dependencies and re-evaluating data values as needed?

This writeup gives a high-level overview of the Antimony graph engine, which is a general-purpose library for building this kind of software infrastructure.

basics

evaluation

First, a basic level of functionality: how do we make an expression evaluate itself?

Example expression

Antimony's chosen scripting language is Python, which has a friendly C API that allows it to be embedded into C/C++ applications.

To evaluate an expression, we simply call PyRun_String. This gives us back a PyObject, which we can examine and show to the user.

lookups

PyRun_String takes in a pair of dictionaries (named globals and locals). These dictionaries are used to look up variables when evaluating an expression. We can pass in a custom dictionary that maps datum names to their values, making lookups work:

Example lookup

When we evaluate x + 3, Python looks for x in the locals dictionary, which returns its value of 2.

dependencies

This system should track dependencies: if y looks up x, then changes to x should cause y to re-evaluate.

Since Python 2.4, the locals argument doesn't strictly need to be a dictionary; it just needs to be an object that implements the mapping protocol. According to the release notes, "there's all sorts of new and shiny evil possible thanks to this little change."

One such evil possibility is recording when lookups happen. We pass a Proxy object as the locals argument, which stores both the name-to-value association and a lookup-to-datum table:

Lookup with tracking

When y asks locals for the value of x, that lookup is stored; the Proxy knows that y cares about the value of x.

When x changes, it informs the Proxy that anything which has looked up x should re-evaluate itself. Since the Proxy knows that y cares about x, it triggers a re-evaluation of y. Sneaky!

A cool emergent benefit is correct behavior in response to changing (and appearing) names. If y was created first, the Proxy still records that it attempted a lookup on x (even though the lookup failed). Then, when x is created, the Proxy knows to re-evaluate y; the lookup will then succeed.

advanced

recursion

As Antimony doesn't have a constraint solver, certain types of recursive connections create undefined situations:

Recursive

These kind of loops can be prevented by maintaining a set of upstream sources which contains any datum that is used in evaluating an expression.

Sources

Then, when a lookup is attempted, we check to see if the looked-up datum contains the downstream datum in its list of sources. If so, execution halts with an error flagging a recursive lookup.

connections

We also want to make persistent graphical connections in the UI. These connections, unlike the lookup-by-name described above, should persist even if datum names change.

Antimony connections

We'd like for connections to use the same lookup mechanism (and reap the benefits of dependency tracking). Making them persist through name changes requires adding a unique identifier (UID) to each Datum. Then, we mark connections with a special character that enables lookups by UID (instead of just by name).

Graph connections

sequencing

Consider the following structure:

Sequencing challenge

If x changes, re-evaluation should be sequenced in the order x, y, z; otherwise, z needs to be evaluated twice (i.e. the sequence x, z, y, z).

Instead of evaluating children immediately, we'll schedule them in a queue. The next object to evaluate is the one without any sources in the queue (other than itself).

The example above proceeds as follows:

beyond

The engine in Antimony goes beyond these idea in a few notable ways.

Datums are clustered into nodes to add a level of hierarchy. Keeping up the theme of "Python scripts everywhere!", nodes are defined by scripts:

Script

You'll notice a set of magic hooks that actually change the node's Datums; designing this feature is left as an exercise for the reader (or you can cheat by looking at how I did it).

Nodes can also define UI hooks, shown in demos on the project page. These UI hooks aren't built-into the graph engine; instead, they're injected by the parent application.

Finally, the actual graph engine includes a callback system to notify the UI of changes to nodes and datums.

To see these ideas in practice, check out lib/graph in Antimony.