Concepts

Before diving into code, it helps to know what the main pieces of Ixion are and how they relate to each other. This page gives you that picture. The pages that follow then walk through the same ideas with working examples.

Cells and sheets

All cell values live in a model_context. A model context holds one or more sheets of a fixed size, each being a two-dimensional grid of cells. A cell can be empty, or it can hold a numeric, boolean, string or formula value.

To point at a cell you use an abs_address_t, which is just a sheet index, a row index and a column index, all 0-based. A rectangular block of cells is an abs_range_t. You append sheets by name, and the index of a sheet is simply its position in the model.

A model_context holding three sheets, with one cell and one range on the first sheet picked out with their addresses.

A model context with three sheets. C2 on the first sheet is the address {0, 1, 2}, and B3:D5 is the range from {0, 2, 1} to {0, 4, 3}.

The model context is deliberately kept small. It holds only what the formula engine needs in order to run a full calculation: the cell values, the formula cells, and the named expressions and tables that formulas refer to. Anything beyond that, such as keeping track of which cells you have edited since the last calculation, is left to whoever uses the model context, be it the document class or your own program.

In the same spirit, the model context doesn’t calculate anything by itself. Something outside of it has to drive the calculation, and that something is either your own code calling the functions described below, or the document class we’ll get to at the end of this page.

Formulas are tokens

Ixion doesn’t keep formulas around as strings. When you hand it a formula string like SUM(A1:A10), it gets parsed once into a sequence of tokens of type formula_tokens_t, and those tokens are what the formula cell stores and what the interpreter runs at calculation time.

A formula string parsed into tokens held by a formula cell, then printed back out as a string in another syntax.

The round trip of a formula. The string is parsed with one resolver into tokens, and the tokens can be printed back with the same or another resolver.

To parse a formula you need a formula_name_resolver. When the parser splits a formula string apart, some pieces are easy to classify on their own: operators, numbers and quoted strings. Everything else, like A1, Sheet1!B2:C5, SUM or Total, is a name, and what a name stands for depends on the syntax the formula is written in.

The resolver’s main job is to make sense of those names, that is, to decide whether each one is a cell reference, a range reference, a table reference, a named expression or a function. Along the way it also handles the finer points of the syntax, such as how a sheet name is attached to a reference, how absolute rows and columns are marked, and how a range is written. Ixion comes with resolvers for the following syntaxes, and you pick one with a formula_name_resolver_t value:

  • Excel A1

  • Excel R1C1

  • LibreOffice Calc A1

  • OpenFormula

  • ODF cell-range-address

The Formula syntax and name resolvers page goes through these in detail.

The resolver also works in the other direction, turning tokens back into a string through print_formula_tokens(). Since the tokens themselves don’t depend on any particular syntax, you can parse a formula with one resolver and print it with another.

One more thing to keep in mind: a reference can be relative or absolute. An absolute reference such as $A$1 always points at the same cell, whereas a relative reference such as A1 stores its target as an offset from the cell the formula is in, so the same tokens point at different cells depending on where the formula lives. That’s why both parse_formula_string() and print_formula_tokens() ask for the position of the formula cell.

Dependency tracking

Every model context comes with a dirty_cell_tracker. Its job is to remember which cells each formula cell references, so that when a cell changes, we can find the formula cells that depend on it, either directly or indirectly.

A grid where A11 sums A1:A10 and B1 references A11; a change in A5 makes A11 dirty, and A11 in turn makes B1 dirty.

A11 references A1:A10 and B1 references A11. When A5 changes, the tracker reports A11 as dirty, and through it B1.

The model keeps the tracker up to date on its own. When you set a formula cell, it walks through the reference tokens of the formula and records each one; when you overwrite or empty a formula cell, it drops the old references.

A formula cell whose result needs to be re-calculated is said to be dirty. That happens when one of the cells it references has changed, either directly or through some other formula cell in between, or when the formula cell itself is new or has been modified. A formula cell that uses a volatile function such as NOW() is treated as dirty on every calculation. See Errors and volatile functions.

Note

The references get recorded at the moment you set the formula cell, so a named expression or table the formula refers to has to exist by then. When you bulk-load a model, model_context_loader records the references once everything is in, so the order the content comes in matters less. See Loading a model in bulk.

Calculation

Calculation is a two-step process. First you tell the model which cells have been modified since the last calculation and ask for the dirty formula cells via query_and_sort_dirty_cells(). What you get back is the positions of those formula cells, sorted in order of dependency so that each one comes after the cells it depends on. Then you hand that sorted sequence to calculate_sorted_cells(), which interprets the formula cells one by one in that order and stores each result in its cell.

The modified cells go into the dirty query, which consults the tracker and yields the dirty formula cells in dependency order; those go through the calculation and end up as cached results.

The two steps of a calculation. The modified cells and the modified formula cells go in, the dirty formula cells come out sorted, and the calculation stores a result in each of them.

Note

You may wonder why the sequence consists of cell ranges rather than individual cell positions. That’s because of formula groups, which we’ll come back to at the end of this page. The cells of a group are calculated as one unit, so a dirty group shows up in the sequence as a single range covering all of its cells, while an ordinary formula cell shows up as a range of just one cell.

For the very first calculation you can simply declare every cell modified, which makes every formula cell dirty. From then on you only pass in what actually changed, and only the formula cells affected by those changes get re-calculated.

calculate_sorted_cells() also takes a thread count. Pass zero and everything runs on the calling thread. Pass a positive number and that many calculation threads get spawned; a formula cell that needs a result still being computed on another thread simply waits for it.

The result of a formula cell is a formula_result, which can be a number, a boolean, a string, a matrix or an error. When you read a cell value through the model context, you get the cached result from the last calculation. If some cells reference each other in a cycle, they all end up with the #REF! error while the rest of the cells calculate as usual. See Errors and volatile functions for more on error values.

Two levels of API

The application on top, document in the middle, and model_context with its dirty cell tracker beside the free functions at the bottom; one route goes through document, the other straight down.

The two levels of the API. An application can go through document, or work with model_context and the free functions directly.

What we’ve covered so far is the low-level API: a model_context for storage, and the free functions in <ixion/formula.hpp> for parsing and calculation. At this level you keep track of which cells were modified and drive each step yourself. The First step - creating model_context page shows what that looks like in practice.

The document class sits on top of a model context and takes care of that bookkeeping for you. It parses formula strings with a resolver you choose at construction, remembers which cells you’ve touched, and runs both calculation steps when you call calculate(). As a convenience, you can also address cells with strings like "Sheet1!A1" instead of an abs_address_t. The Using document for builtin formula management page builds the same example on top of it.

Which level to use depends on your program. If it already has its own document model and just needs a formula engine, it already knows which cells changed and when to calculate, so working with model_context directly is the natural fit. If you’d rather not deal with any of that, document handles it for you.

Beyond single cells

So far we’ve talked about individual cells and the formulas in them. Ixion has a handful of features that build on top of those basics, and here is a quick run-down of what they are:

  • Named expressions are formula token sequences stored under a name, either globally or per sheet, which formulas can then refer to by that name. See Named expressions and tables.

  • Tables are named rectangular ranges with named columns. A formula can refer to a table by its name and column instead of by cell addresses, and such references take part in dependency tracking like any other. See Named expressions and tables.

  • Formula groups let a range of formula cells share one set of formula tokens, which saves memory. This is also how an array formula spanning several cells is represented: the formula gets evaluated once, and each cell of the group shows its own element of the resulting matrix as its value. From the outside, each member is still an ordinary formula cell with its own result. See Formula groups.

  • Sheet copies append a new sheet as a copy of an existing one. The two sheets share their cell storage until one of them gets modified. See Copying a sheet.

  • Sheet views are named snapshots of a sheet whose rows you can sort without touching the sheet itself. See Sorting a sheet through a sheet view.