Data Flow

Task Model

The smallest unit of a build is a task identified by a key and, on successful build, resulting in a value.

The keys represent the parameters to Value Shell Commands.

The values are discussed in Values.

Tasks, the computations that produce a value from a key, are all built into the build system except for Custom Lua Rules.

A task may depend on zero or more keys. For example, the form task CommonsBase_Shell.Pwsh@7.5.4 defined by:

{
  "forms": [
    {
      "id": "CommonsBase_Shell.Pwsh@7.5.4",
      "function": {
        "commands": [
            "$(get-object CommonsBase_Dotnet.SDK@10.0.100-rc.2.25502.107 -s ${SLOTNAME.Release.execution_abi} -d :)/dotnet${.exe.execution}",
            "tool",
            "install",
            "PowerShell",
            //...
        ]
      }
    }
  ]
}

depends on the object key CommonsBase_Dotnet.SDK@10.0.100-rc.2.25502.107.

We say that the object key CommonsBase_Dotnet.SDK@10.0.100-rc.2.25502.107 is an immediate dependency of object key CommonsBase_Shell.Pwsh@7.5.4.

The tasks and their dependencies form a task graph.

The shape of the task graph is:

1. optional layer. the incoming nodes of the task graph are impure rules (UI rules). These nodes may depend on nodes in a lower layer.
2. optional layers. the interior nodes of the task graph are objects and pure rules (ie. function rules). These nodes may depend on nodes in the same layer or below.
3. the leaf nodes of the task graph are the immutable bundles and assets. These nodes have no dependencies.

That shape is enforced through the edges (the dependencies) allowed in the task graph (todo: incomplete, inaccurate):

Value Type From	Value Type To	Why
a	j	Rebuild bundle if contents of values.json changes
a	v	Rebuild bundle if parsed values.json changes
o	j	Rebuild form if contents of values.json changes
o	v	Rebuild form if parsed values.json changes
p	j	Rebuild asset if contents of values.json changes
p	v	Rebuild asset if parsed values.json changes

Trace Store

Each time a task is executed, the following items are captured into a single trace:

• the key of the task
• the successful value of the task
• the keys of the task's immediate dependencies
• a SHA256 digest of the values of the task's immediate dependencies

The key is one of two types:

• A module key is what you -- the user -- specify in a shell command as the MODULE_ID and SLOT or PATH in the Value Shell Language. The module key can be large for run-function since its parameters includes a JSON request.
• A checksum key is the SHA-256 of some content

The value is not directly stored in the trace. Instead, an identifier (the value id) is stored in the trace, and the potentially large value is stored in the value store (more on that next section).

Value Store

The value store is a key value table stored on disk.

The value type is a single letter that categorizes what the value is:

Value Type	What	Docs
o	object	Objects
b	bundle	Bundles
a	asset	Assets
i	index files	Objects or Assets
j	values.json file	JSON Files
l	values.lua file	Lua Scripts
v	(cache) parsed values AST	JSON Files
c	built-in constants	Objects
s	source file	FILLMEIN

All value types are lowercase for support on case-insensitive file systems.

Any value types with (cache) are stored in the local cache rather than the valuestore.

• A value file is a file whose content matches the value type
• A value sha256 is a SHA-256 hex-encoded string of the value file. That is, if you ran certutil (Windows), sha256sum (Linux) or shasum -a 256 (macOS) on the value file, the value sha256 is what you would see.

The build system requests data in the form of a build key, and a build task is responsible for resolving the build key into a value that will be persisted in the value store. The value will be of a type that depends on the build key:

Build Key	Value Type	Id Material	Value File
asset	a	ACI	contents of asset
	i	digest of the a id (prefix swap)	index
bundle	b	BCI	contents of zip archive file
object	o	FRM	output of form function
		::<SLOT>
	i	digest of the o id (prefix swap)	index file
V256	j	V256	dos2unix json {schema_version:,forms:,bundles:}
V256	l	V256	dos2unix lua script
VCI	v	VCK	parsed {schema_version:,forms:,bundles:}

The exact construction of each value id is given in Value Id Formulas.

To allow byte range optimized reading of zip files, special rules are in place when fetching assets and objects:

• When fetching an asset, the fetched build system value is a composite Optional (zip) and Always (asset).
• When fetching an object, the fetched build system value is a composite Optional (zip) and Always (object).
• If the object value is known¹ to be a zip file the build system implementation will produce both the i value type and the o value type.
• If the asset value is known¹ to be a zip file the build system implementation will produce both the i value type and the a value type.

A build system implementation may choose to lazily extract entries using the Optional (zip) value (if present) which serves as an index over the Always (*) value. The Optional (zip) value avoids the overhead of preemptively downloading and unzip all of the possibly huge Always (*) zip file. However, for the Optional (zip) value to provide a benefit, the value URL must support byte range lookups. For example, if assets are on a web server that does not support the HTTP Range header, the entire Always (asset) zip file will be downloaded.

¹: Currently only value store assets of distributed value stores are known to be zip files. Other asset files are 1-to-1 with their SHA256 identifiers, and so can't be deterministically known to be zip files.

The value id is used to lookup or persist into the value store.

Value Id Formulas

Every value id is an explicit function of its inputs. The helper functions, where || is byte concatenation:

SHA256_HEX(s)   = lowercase hex encoding of the SHA-256 digest of the bytes s
BLAKE2B_RAW(s)  = raw (unencoded) BLAKE2b-256 digest of the bytes s
BASE32L(hex)    = RFC 4648 base32 of the hex-decoded bytes, using the lowercase
                  alphabet "abcdefghijklmnopqrstuvwxyz234567", without "="
                  padding. A 32-byte digest encodes to 52 characters.
BASE32L_RAW(b)  = the same base32 encoding applied directly to raw bytes b
CANON_JSON(x)   = the canonical compact JSON serialization of x: object fields
                  in the field order given in the definitions below, no
                  insignificant whitespace
STRIP_CR(s)     = s with every carriage return (ASCII 13) byte removed

Common inputs:

VCI       = SHA256_HEX( canonical JSON of the parsed values file CST )
            (see "VCI - Values Canonical ID"; the values file is stripped of
             carriage returns before parsing)
MODVER    = MODULE "@" VERSION      -- no build metadata; see "BLD"
SLOT      = the value shell slot name, e.g. "Release.Windows_x86_64"

The formulas, per value type:

-- o : object (the output of one form, for one slot)
FRM  = SHA256_HEX( VCI || "|form|" || MODVER )
o_id = "o" || BASE32L( SHA256_HEX( FRM || "::" || SLOT ) )

-- a : asset (one file of a bundle)
ACI_JSON = CANON_JSON( { checksum = { blake2b256?, sha1?, sha256? },
                         indexes?  = [ per-index records ],
                         path      = FILE_PATH,
                         size      = FILE_SIZE } )
ACI  = SHA256_HEX( ACI_JSON )
a_id = "a" || BASE32L( SHA256_HEX( ACI ) )

-- b : bundle (the zip of all files of a bundle)
BCI_JSON = CANON_JSON( { assets = [ ACI_JSON of each file, sorted by path ],
                         id     = MODVER } )
BCI  = SHA256_HEX( BCI_JSON )
b_id = "b" || BASE32L( SHA256_HEX( BCI ) )

-- i : index file over a zip-shaped object or asset payload
i_id = "i" || suffix          where ("o" || suffix) = o_id
                              or    ("a" || suffix) = a_id

-- j : values.json file        l : values.lua file
V256 = SHA256_HEX( STRIP_CR( values file bytes ) )
j_id = "j" || BASE32L( V256 )
l_id = "l" || BASE32L( V256 )

-- v : parsed values AST (local cache only)
VCK  = BLAKE2B_RAW( VCI || EXEC_ABI || TARGET_ABI || AST_SCHEMA_ID || CT )
v_id = "v" || BASE32L_RAW( VCK )
       where EXEC_ABI/TARGET_ABI are the ABI names of the current process,
             AST_SCHEMA_ID is a generated fingerprint of the AST type
             definitions (changes whenever the AST types change), and
             CT is the "CT - Compatibility Tag"

-- c : built-in constant        x : execution streams
c_id = "c" || BASE32L( SHA256_HEX( constant bytes ) )
x_id = "x" || BASE32L( SHA256_HEX( encoded execution streams ) )

-- k : key with a lazy value    s : source file (debugging)
k_id = "k" || KEY_ID
s_id = "s" || BASE32L( SHA256_HEX( source file bytes ) )

Two structural properties follow directly from the formulas:

1. Asset and bundle ids pin exact bytes. ACI_JSON embeds the content checksum and byte size of the file, so two assets with different bytes can never share an a id, and BCI_JSON inherits that property for b ids.
2. Object ids do not hash the produced output. o_id is derived only from the recipe address: the values file (via VCI), the form's module version and the slot. The bytes that the form's function writes into the output directory appear nowhere in the formula. The consequences are described in the next section.

Object Ids Hide Build Non-Determinism

An object id is a recipe address (the values file (via VCI), the form's module version and the slot). Whichever build of the recipe completes first has its output bytes persisted into the value store under that id; every later build of the same recipe reuses (or republishes) bytes under the same id, even if a fresh build would have produced different bytes.

So object ids are designed to hide non-determinism present in the underlying build. For a distribution script that means the use of $ get-object ... will output a \dk.object(...) that contains a stable, build-agnostic value-id.

An early version of the CommonsLang_OCaml.DkML@4.14.3 -s Release.Windows_x86_64 OCaml compiler object, for example, had independent builds with the same value id. Even so, unique working directories were a primary source of non-determinism; 751 of the 2032 files inside any two newly built objects differed byte-for-byte:

• 671 OCaml typed-tree files (.cmt, .cmti) differed by a handful of bytes each: the OCaml compiler embeds the absolute source path, which contains the build system's ephemeral per-invocation working directory (for example t\p\476\7vpw\...\src-ocaml\ in one build and t\p\484\2vog\...\src-ocaml\ in the other).
• Linked binaries (.exe, .dll, .lib, .obj), which were generated by the MSVC compiler, differed because paths are recorded in debug information.
• Bytecode archives (.cma, .cmo) also differed.

Tip

Nothing prevents the object recipe from setting the compiler options and environment to be bit-for-bit reproducible. For example, the OCaml compiler accepts a BUILD_PATH_PREFIX_MAP environment variable to adjust build paths, and the MSVC compiler accepts /PDBALTPATH, /Brepro, and other deterministic flags. And that bit-for-bit reproducibility can be enforced with distribution scripts that run a checksum object with a subshell that gets the object (get-object):

$ run-object
>   CommonsBase_Std.Coreutils@0.8.0 -s Release.execution_abi
>   -m ./coreutils.exe -f coreutils.exe -e '*'
>   --
> sha256sum -b
> $(get-object OBJECT -s SLOT -m MEMBER -f YOUR_FILENAME)
\test(pass)
\dk.target(abi: "Windows_x86_64")[SHA256 (YOUR_FILENAME) = 66d5f22136245be5e5c0aa3aba4cdc795d0c7315c23a5ccef3322fd008ac007d
]

v - parsed values.json AST

A values.json is parsed into an AST, and the AST is persisted directly from OCaml memory blocks and signed with the local build key.

The build system will verify the signature of the AST before loading the AST into memory. If the signature does not match the local build key, or if the AST is incompatible with the memory layout of the current process (see compatibility tag), the j values.json file is fetched and re-parsed into a new AST.

i - index file

The value file is:

Offset (bytes)	Size (bytes)	What
0	n	Central Directory
n	4	Magic number. 44 4B 49 56 (DKIV)
n+4	4	Reserved. 00 00 00 00 for zipfile indexes
n+8	8	offset of first local header

The offset of the first local header is typically zero (0) except in special cases like:

• self-extracting zips have the executable stub before the first local header

All sizes are little-endian.

The Central Directory includes:

1. All the Central directory file headers (CDFH) including their ZIP64 extra fields.
2. Zip64 End of central directory record (EOCD64)
3. 20-byte End of Central Directory Locator
4. The classic end of central directory record (EOCD)

The following Central Directory fields are modified:

Record	Offset	Size	New Value
Zip64 End of central directory record (EOCD64)	16	4	1 (Number of this disk.)
Zip64 End of central directory record (EOCD64)	20	4	1 (Disk where central directory starts.)
Zip64 End of central directory record (EOCD64)	48	8	CD (Offset of start of central directory, relative to start of archive.)
Zip64 End of Central Directory Locator	4	4	1 (Disk where EOCD64 starts.)
Zip64 End of Central Directory Locator	8	8	CD + EOCD64 (Offset to start of EOCD64, relative to start of archive.)
Zip64 End of Central Directory Locator	16	4	2 (Total number of disks.)
Classic EOCD	4	2	1 (Number of this disk)
Classic EOCD	6	2	1 (Disk where central directory starts)
Classic EOCD	8	8	CD (Offset of start of central directory, relative to start of archive)

The modifications mean the i value files are valid ZIP files. In other words:

• the i file becomes the second disk containing only the directory entries
• the original asset file, if downloaded in its entirety, is the first disk

BLD - Build Metadata

The dot (.) separated build metadata from the semver version.

For example, OurZip_Demo.S7z2.Windows7zExe@25.1.0+bn-20250101000000+diff has build metadata bn-20250101000000.diff.

Build metadata is deliberately not part of any value id. The a, b and o value ids are content-addressed (from the asset/bundle/form canonical id and, for objects, the slot), so identical content gets the same value id regardless of the build number (the bn-* build metadata). This keeps distributions reproducible: changing the build number (for example via dk0's -n option or a git tag) does not change the object, bundle or asset ids.

Build metadata still participates in keys and versions (see ID with Build Metadata); it is only excluded from value ids.

V256 - SHA256 of Values File

The SHA-256 (raw, not hex-encoded) of the values.json file that contains the bundle (or form or asset).

P256 - SHA256 of Asset

The hex-encoded SHA-256 of the asset. It is the checksum.sha256 in the following asset:

{
  "origin": "github-release",
  "path": "SHA256.sig",
  "size": 151,
  "checksum": {
    "sha256": "0d281c9fe4a336b87a07e543be700e906e728becd7318fa17377d37c33be0f75"
  }
}

Z256 - SHA256 of Zip Archive File

The hex-encoded SHA-256 of the zip archive generated from either:

• the output directory of a form
• the bundle directory for one or more bundle files

Z256 is a checksum of the stored value file (the payload). In particular, the Z256 of an object payload is not stable across rebuilds of the same object id (see Object Ids Hide Build Non-Determinism).

CT - Compatibility Tag

A string with the format oc<OCAMLVERSION>_ws<OCAMLWORDSIZE>.

For example, oc414_wd64 is OCaml 4.14 with a 64-bit word size.

VCI - Values Canonical ID

The hex-encoded SHA256 of the values.json canonicalized JSON, stripped of all carriage returns (ASCII CR 13).

VCK - Values Checksum

The raw BLAKE2b-256 digest that keys the local cache of the parsed values AST:

VCK = BLAKE2B_RAW( VCI || EXEC_ABI || TARGET_ABI || AST_SCHEMA_ID || CT )

where EXEC_ABI and TARGET_ABI are the ABI names of the current process, AST_SCHEMA_ID is a generated fingerprint of the AST type definitions (it changes whenever the AST types change, protecting the marshalled AST from schema drift), and CT is the compatibility tag.

The stripping of carriage returns occurs before the CST and AST parsing, so that any serialized AST uses the byte positions of the Unix-encoded JSON.

FRM - Form

The hex-encoded SHA-256 of the concatenation of:

• VCI for the values.json defining the form
• |form|
• MODULE@VERSION (without build metadata)

That is, using the helpers of Value Id Formulas:

FRM = SHA256_HEX( VCI || "|form|" || MODULE "@" VERSION )

ACI - Asset Canonical Id

The hex-encoded SHA-256 of the canonical compact JSON of one bundle file's identity fields, in the field order:

ACI_JSON = { "checksum": { "blake2b256"?, "sha1"?, "sha256"? },
             "indexes"?: [ per-index records ],
             "path": FILE_PATH,
             "size": FILE_SIZE }
ACI      = SHA256_HEX( CANON_JSON( ACI_JSON ) )

The checksum object contains whichever of the three checksums the bundle declares. The P256 content checksum and the byte size are both inside ACI_JSON, so an asset id pins the exact bytes of the asset.

BCI - Bundle Canonical Id

The hex-encoded SHA-256 of the canonical compact JSON of the bundle definition:

BCI_JSON = { "assets": [ ACI_JSON of each file, sorted by path ],
             "id": MODULE "@" VERSION }
BCI      = SHA256_HEX( CANON_JSON( BCI_JSON ) )

The origins/mirrors listing is deliberately excluded so that re-mirroring a bundle does not change its identity.