open format

dodo dna

a lineage format for data workflows. every variable and result, traced to raw data.

Dodo DNA records data provenance in research code. It traces each variable and each statistical result back through its ancestors to raw source data. This page is the complete, normative definition of the formats. Version 0.6.0.

This specification is CC0 — anyone may implement it. The format is called Dodo DNA. It is used in Dodo products like Dodo Review and, soon, Dodo Studio.

architecture

Dodo DNA is built in steps. Source code passes through five representations. Each arrow in the diagram is one translation step. Each representation has its own section below.

source text
   │  parse (one tree-sitter grammar per language)
   ▼
CST         native concrete syntax tree, per-language node names
   │  harmonize (per-language mapping table)
   ▼
hCST        one fixed vocabulary of kinds over the native tree
   │  lower — canonical names are assigned here, once
   ▼
Expr IR     Sym | Lit | Call, language-independent expression trees
   │  extract
   ▼
DNA         one flat document per repository: files, symbols, ops
   │  slice
   ▼
RNA         per-target backward slices of the DNA document

Two rules hold at every step of this pipeline. First: function names are translated to their canonical names in one place, the lowering step. No later step renames anything. Second: when the tools cannot determine a value from the code alone, they do not fail and they do not guess. They record the fact with a confidence marker and continue.

The five supported source languages are Stata, Python, R, Julia, and MATLAB. The Stata grammar is our own; it is open source (MIT) at codedthinking/tree-sitter-stata.

the hCST

Every language parses into its own tree, and every language names its tree nodes differently. A function call is a call node in Python, a call_expression node in Julia, and a funcall node in Stata. Code that reads five kinds of trees must know five sets of names.

The hCST (harmonized concrete syntax tree) removes this problem. It is a read-only view over the native tree. The view gives each node one kind from one fixed list. The two tables below are that list: eleven statement kinds and thirteen expression kinds.

Three properties of the view:

• A node with no mapping keeps its native type with a language tag, for example py:lambda. Its children are still mapped.
• The text and the position of every node come from the native node. Nothing is copied and nothing is invented.
• Function and variable names are never rewritten at this stage.

Language tags: py Python, r R, jl Julia, m MATLAB, st Stata.

statement kinds

expression kinds

mapping rules

• R operators. R parses every infix operator into one node type, binary_operator. The view reads the operator text to choose the kind. The assignment arrows (<-, =, ->, <<-, :=) map to assign, and lhs is always the target — also for ->, which points the other way. The pipes (%>%, |>) map to call. The tilde (~) maps to formula. Every other operator maps to binop.
• Pipes. df %>% filter(x > 2) means: call filter with df as its input. The view records exactly that — a call whose receiver is df. There is no separate pipe kind.
• Receivers. A method call and a plain function call are both call. "x".lower() has callee lower and receiver "x". strlower("x") has callee strlower and no receiver.
• MATLAB parentheses. MATLAB writes indexing and function calls the same way: f(x). The parser cannot tell them apart, so the view maps both to call. The lowering step turns a call into an index when it knows the name refers to data, not to a function.
• Opaque payloads. Some regions have no useful inner structure, for example the payload of a Stata command option. The view keeps such a region as one node and exposes only its text.
• Macros. Stata macros (`x', $x) are not expanded before parsing. The parser records them as macro_ref nodes. Expansion happens later, at lowering, where the values are known.
• Positions. Every position is the position of the native node. Nothing is invented.

the Expr IR

The hCST still contains language-specific detail. The Expr IR (intermediate representation) removes it. Every expression lowers into a tree built from only three node types:

Expr = Sym | Lit | Call

• Sym — a reference to a column or to a named value. A Sym holds only the bare name, for example wage. It does not say which dataset the column belongs to; the operation that carries the expression says that.
• Lit — a constant, with a class: num, str, bool, or null.
• Call — a function application. When the vocabulary below has a name for the function, the Call uses that canonical name. When it does not, the surface name passes through with a language tag, for example r:mapvalues. Operators are calls too: a + b becomes Call(add, a, b).

Rules:

• Names are translated once, at lowering. The lookup key is (language, surface name, argument count). The argument count matters because the same name can mean different things with a different number of arguments. No later step renames anything.
• Indexes count from 1, and ranges include both ends. Languages with other conventions are translated at lowering: Python counts from 0, so a[0, 1:4] becomes a[1, 2:4]. When an index cannot be translated with certainty, it keeps its lowered form and gets confidence="runtime". A canonical Expr never contains an untranslated 0-based index.
• An open-ended slice uses the symbol end. In a[2:], the upper bound is "the last element". The IR writes that bound as the reserved symbol end, the word Julia and MATLAB use for it: a[2:end].
• Lowering never fails on valid source code. When something cannot be resolved, the Expr gets a confidence marker instead.
• Serialization. In the DNA document, an operation that carries an Expr has an ir child with the compact s-expression form, for example ir "(call log (sym wage))".
• Rendering. Every Expr also has a human-readable form: ordinary infix notation with the fewest parentheses that preserve meaning. (call sub (call log (sym a)) (call log (sym b))) renders as log(a) - log(b). An Expr with a confidence marker renders with a suffix, for example ?runtime.

canonical vocabulary

Canonical names are single words with no hyphens. When one language has the clearest word for a concept, that word wins. Julia separates minimum(x) (smallest element of a collection) from min(a, b) (smaller of two values), so the vocabulary does too.

Example. The same computation in five languages lowers to one Expr:

gen d = cond(missing(x), 0, x)        // Stata
np.where(df["x"].isna(), 0, df["x"])  #  Python
ifelse(is.na(x), 0, x)                #  R
ifelse.(ismissing.(df.x), 0, df.x)    #  Julia

  s-expression:  (call ifelse (call ismissing (sym x)) (lit 0) (sym x))
  rendered:      ifelse(ismissing(x), 0, x)

the DNA document

The DNA document is one flat file per repository, written in KDL — a small document language, similar to JSON but with named nodes. The document has three sections. The order of nodes is meaningful: it is the identity and the tiebreak rule for everything downstream.

dna "repo" spec="0.6" {
  files { ... }
  symbols { ... }
  ops { ... }
}

Every node has the same shape. The node name is a verb or a kind. The positional arguments are the operands. The properties (key=value) are metadata; their values are scalars. The children hold repeated or detailed content. Names stay clean: uncertainty is recorded in properties, never as marks on names.

files

Files, dependency edges, and execution-order results.

files {
  script "analysis.do"
  data "raw/firms.dta"
  link from="config.do" to="analysis.do" basis="..." confidence="evidenced" {
    evidence "analysis.do" 1
  }
  topo-order "config.do" "analysis.do"
  execution-chain "config.do" "analysis.do"
  entry-points "config.do"
  pipeline {
    scripts "config.do" "analysis.do"
    output key="tables/table3.tex" rule="research-output-extension"
  }
}

Node names carry the file kind: script, data, figure, config, doc, other. The path is the first positional argument. link edges are the ground truth for dependencies. Diagnostics (cycle, orphan-scripts, chain-ambiguity, unsupported-languages) are list or property nodes.

symbols

One node per symbol. The kind is the node name; the display name is the first positional argument. Kinds: variable, dataset, local, global, scalar, frame, tempfile.

symbols {
  variable "main.lnwage" inferred-type="numeric" description="natural log of wage" {
    def "analysis.do" 2
    use "analysis.do" 7
  }
  dataset "firms.dta" origin="external" {
    use "analysis.do" 1
  }
  global "controls" origin="runtime" confidence="unknown" {
    use "analysis.do" 7
  }
}

Three properties describe a symbol's status. origin says where the symbol comes from: external (a source file), runtime (exists only when the code runs), derived (computed from other symbols), or merged. confidence follows the table below. note is optional free text; it may add detail but never replaces the structured properties.

ops

One op per source statement, grouped per script in execution order, in source order within a script. Eleven verbs:

ops {
  script "analysis.do" {
    load "firms.dta" line=1
    assign "lnwage" "wage" expr="gen lnwage = log(wage)" line=2 {
      ir "(call log (sym wage))"
    }
    assign "lag_emp" "emp" by="firmid" expr="bysort firmid: gen lag_emp = L.emp" line=7 {
      ir "(call lag (sym emp) (lit 1))"   // renders: lag(emp, 1)
    }
    emit "lnwage" "lag_emp" estimator="ols" depvar="lnwage" line=10
  }
}

Six properties modify a verb. They are not verbs themselves:

• by= — the operation runs once per group.
• subset= — a row condition that applies to this one statement only.
• frame= — the dataframe the operation works on. The default frame is implicit.
• source= — the frame an operation reads when it binds a new name.
• per= / domain= — the loop the statement runs inside, and what the loop runs over.
• scope= — the namespace path of a value defined inside a program or a session.

Source names in an assign are bare column names. Detail such as lag depth lives in the ir child. The verbatim source line stays in expr= as the citation.

confidence

Four values, on ops, symbols, links, and Expr nodes alike:

The rule is uniform: mark, never guess, never fail.

RNA slices

The DNA document answers: what does this repository do? A reviewer usually asks a narrower question: where does this one number come from? An RNA slice answers that question. It contains every operation upstream of one target — and nothing else — nested, newest first. Slices are derived and disposable. The DNA document is the ground truth they are cut from.

Two slice shapes. A symbol slice roots at the latest definition of one variable. A result slice roots at one emit.

symbol "main.lag_emp" {
  description "lag_emp = previous-period emp; defined analysis.do:7; on rows of firms.dta"
  assign "lag_emp" by="firmid" expr="bysort firmid: gen lag_emp = L.emp" file="analysis.do" line=7 {
    from "emp" lag=1 {
      column "emp" of="firms.dta"
    }
    rows {
      load "firms.dta" file="analysis.do" line=1
    }
  }
  consumers {
    emit "lnwage" "lag_emp" estimator="ols" file="analysis.do" line=10
  }
}

• from children answer: where do the values come from? Each source of the root operation resolves to one of three things. A ref is another symbol, with its own nested slice. A column is a column of a source data file; saved-by names the script that wrote that file, when known. A nested operation is the definition itself, for named values. When a value is read through a lag, the branch carries lag=.
• rows children answer: which rows were present? They list the operations that changed the rowset before the root operation — filters, merges, collapses — newest first, ending at the nearest load.
• When a branch reaches a name that could not be resolved, the branch ends with confidence="unknown". The reader stops there. The slice never guesses past an unresolved name.
• description is one generated plain-language sentence: what the definition is, where it is, and which rows it stands on.

version history