phi.md

Phi, briefly

Phi is a tiny self-describing binary tree format. A document is two binary blobs written directly next to each other:

[ encoded type ][ value encoded according to that type ]

The first blob describes the value's complete Phi type. The second blob holds the actual value, omitting anything the type already told us. There is no separator: type encodings are self-delimiting, so the decoder knows exactly where the type ends and the value begins. It reads the first blob into a type, then uses that type as the schema for decoding the adjacent value blob.

There is no magic, revision byte, outer length, checksum, object identity, or canonical sort order around the pair.

Data model

Phi has null, signed integers (8/16/32/64-bit), floats (32/64-bit), strings, lists, maps, objects, and choices (tagged objects).

Object fields and choice subtypes use either a non-negative integer key or a string key. Lists share one element type; maps share one key type and one value type. That shared type may be Any when things get weird.

How the type compresses the value

The type is not decorative metadata. It stays in scope while the value is decoded, so anything already stated by the type is omitted from the value.

• List(1000, Int) says the size and element type once. The value is just 1000 zigzag integers: no item count and no 1000 Int tags.
• Map(20, String, Long) likewise states its size, key type, and value type once.
• An object type declares its field keys and field types. An object value uses tiny field indexes, so it repeats neither names nor types.
• A choice type declares all subtype schemas. A choice value uses a subtype index, then field indexes from that subtype.
• Any is the escape hatch. At an Any position the value supplies another TYPE VALUE, trading a little space for heterogeneity.

So the wire decoder always has an active type. Nested values either inherit part of it or select a previously declared slot from it.

Basic encodings

The key trick keeps integer key 0 (00) distinct from string key "" (01).

Type tags

Scalars

Lists

E is the shared element type. A fixed size lives in the type; ? means the size will be carried by the value instead.

Maps

K and V are the shared key and value types. Again, ? means the value carries the size.

Objects and choices

An object schema is repeated key TYPE. A choice schema is repeated key OBJECT_TYPE. Declaration order assigns the zero-based indexes used by values.

Values

Scalar values are unsurprising:

For a list, write the runtime size if the type did not include one. If its element type is Any and it is non-empty, write the actual common type once; then write the elements under that type.

Maps do the same independently for keys and values, followed by alternating key/value pairs.

An object value is:

size(present fields)
repeated: uvar(field index), VALUE under that field's type

A choice adds its subtype index first:

uvar(subtype index), size(present fields)
repeated: uvar(field index), VALUE under that field's type

Duplicate or out-of-range field/subtype indexes are invalid.

Worked examples

A homogeneous list

[1, 2, 300] : List(3, Int)

0f 05  02 04 d8 04
-----  -----------
type      value

• 0f says “fixed list of 3, with a concrete element type.”
• 05 supplies that type: Int.
• The remaining bytes are zigzag integers 1, 2, and 300.

The list size and Int tag appear once. All three values are bare integers.

A list of objects

Consider two people:

[
  {name: "Ada", age: 37},
  {name: "Bob", age: 42}
]

Its type bytes are:

0d                              List(2, E)
22                              E = Object with 2 fields
09 6e 61 6d 65  09              key "name": String
07 61 67 65     05              key "age": Int

The leading 09 and 07 on the field lines are encoded string-key lengths, not type tags. The two object values then become:

02 00 03 41 64 61 01 4a        2 fields; #0="Ada"; #1=37
02 00 03 42 6f 62 01 54        2 fields; #0="Bob"; #1=42

name, age, String, and Int occur only in the shared type. Each object uses field indexes 00 and 01.

Choices reuse subtype schemas too

Suppose field and subtype names use compact @Phi.Id keys:

Shape = #1 Circle { #0 radius: Int }
      | #2 Rect   { #0 width: Int, #1 height: Int }
value = [Circle(3), Rect(4, 5), Circle(8)]

The shared type is:

0f                              List(3, E)
27                              E = Choice with 2 subtypes
02 21 00 05                    subtype #1: Object { #0: Int }
04 22 00 05 02 05              subtype #2: Object { #0: Int, #1: Int }

The values are:

00 01 00 06                    subtype slot 0; 1 field; field 0 = 3
01 02 00 08 01 0a              subtype slot 1; 2 fields; 0 = 4; 1 = 5
00 01 00 10                    subtype slot 0; 1 field; field 0 = 8

Notice the distinction: subtype keys #1 and #2 live in the type, while values refer to their zero-based schema slots 0 and 1.

When the common type is Any

[7, "ok", null]

0e 01  05 0e  09 02 6f 6b  02
-----  -----  -----------  --
list    int      string     null

• 0e is a fixed list of 3 whose declared element type is Any.
• 01 says the runtime common type is still Any.
• Each item therefore carries its own type tag: 05, 09, then 02.

Homogeneous data gets the compact path; heterogeneous data still works.

Kotlin mapping

• Boolean is Byte(0|1); Char is a one-character String.
• Classes become objects. Enums and sealed/open polymorphism become choices.
• Fields and subtypes use serial names, unless a non-negative @Phi.Id is set.
• Nullable, list, map, inline, and contextual values map as expected.

One final wart: the implementation calls this revision 0, but that revision is not written into the stream. If you need framing/versioning, add it outside Phi.