APC data model: Wire encoding example

This document presents an example of a complex but ordinary APC object and its encoding on the wire, which is also used to compute its hash address.

We describe the structure in a kind of wire assembly, which has a simple mapping to a binary representation, but we will discuss binary representatiosn in a later document. There may end up being more than one binary target, since the current IPLD format, dag-cbor, is nice to have, but hardly ideal.

The example object is a declaration/id/contract of a mutable (flippable) boolean with a description ("please leave turned off"). The boolean can be flipped by mako or imhotep, and can be observed by mako, imhotep and also steve. The boolean was initially set to false. The permissioning structure allows the writers mako or imhotep to add and remove additional writers and readers, and it allows steve to add more readers. Mako, imhotep and steve are all able to read the current state of both permissioning sets. All of this is declared immutably, though it concerns a mutable state.

First note that the above paragraph explaining the behavior of the data is almost as long as the code representation. This is a very concise representation of the data. There isn't a better way of expressing the data, so please forgive the following:

Notice that permission sets often have a cyclic structure. The writer set of the writer set is itself. The reader set of the reader set is itself. The two refer to each other. There are then, many languages in which they couldn't easily be worked, and we have to do some clever stuff to fit them into a content-addressed format, but it seems like we'll be able to keep the intricacies of that abstracted away.

wr := PermissionedSet(
  writers: wr
  readers: union(wr, rd)
  adders: wr
  Set(mako, imhotep)
)
rd := PermissionedSet(
  writers: wr
  readers: union(wr, rd)
  adders: union(wr, rd)
  Set(steve)
)
#Described(
  "please leave turned off"
  PermissionedSlot(
    writers: wr
    readers: rd
    v: false
  )
)

And the next code snippet describes the structure of the wire representation of the above structure. (I don't think we'll actually be sending s-expressions around, think of it as a kind of assembly format.)

Notice the impls of Contains. These wouldn't be here in reality because Contains would be implemented by Set and Union and so on in the standard library, so it wouldn't need to be explained to the recipient how these types provide Contains functionality, they would already know, but if it had not been so, for instance, if someone had just invented Contains and not provided impls for Sets or T or Union or Intersection, we demonstrate here that it would still be possible to send implementations of Contains over the wire in this way, even without sending any executable code (ie webassembly), simply by referring to extension tactics (ie, impls) like ContainsForSet or ContainsForUnion that the server may already have on their end.

impl components work by starting from the root type, then applying extension rules to the indicated parts of the component types until the required type (in this case, Contains<User>) is produced. If the chain holds, then the entity can be said to implement the provided type via these impl tactics.

(def std (std_glossary 0))
(import (std User String PermissionedSet Set Union Burl))
(def mako (entity
  (data User (entity (data String "mako")))))
  (impl (Contains User) ((ContainsForSelf User) 0))
(def imhotep (entity
  (data User (entity (data String "imhotep")))))
  (impl (Contains User) ((ContainsForSelf User) 0))
(def steve (entity
  (data User (entity (data String "steve")))))
  (impl (Contains User) ((ContainsForSelf User) 0))
(import (#Contains_apt Contains ContainsForSet ContainsForUnion))
(def k1 (entity (data Burl
  (entity
    (data (PermissionedSet User)
      (ref .. 0)
      (entity
        (data (Union (Contains User)) mako imhotep)
        (impl (Contains User) ((ContainsForUnion User) 0)))
      (ref .. 0)
      (entity (data Set mako imhotep)))
    (impl (Contains User) (via ((ContainsForSet User) 0))))
  (entity
    ((PermissionedSet User)
      (ref .. 0)
      (entity
        (data (Union (Contains User)) (ref .. 0) (ref .. 1))
        (impl (Contains User) ((ContainsForUnion User) 0)))
      (entity
        (data (Union (Contains User)) (ref .. 0) (ref .. 1))
        (impl (Contains User) ((ContainsForUnion User) 0)))
      (entity (data Set steve)))
    (impl (Contains User) ((ContainsForSet User) 0))))))

(entity
  (data (#Described (PermissionedSlot bool))
    (entity (data String "please leave turned off"))
    (entity (data (PermissionedSlot bool)
      (ref k1 0)
      (ref k1 1)
      (entity (data bool false))))))

definitions:

• (def a b): defines a shorthand for b, which we refer to as a in the text representation, but in the wire encoding it'll be a varint path, or if it is only used once, it may be placed there inline tagged with a "sprue" joint, as will any entity specified inline.

• (std_glossary v): refers to version v of the glossary. A glossary is a list of shorthands for types, a mapping of shorthands to full type IDs. compresses the wire encoding.

• (import (x ...)): does nothing to the wire encoding, just lets us refer to things in the assembly language without doing the full path, ie, lets us say Contains instead of #Contains_apt.Contains.

• #Link: denotes a hash address to the type that has the shortname Link. Your object cache should save you from having to see full hashes anywhere. All objects have shortnames. When the shortnames you're familiar with clash, then the editor will denote the newer/less important object with a longname. If longnames clash, there might be an even longer name. If all names clash, only then will you see the full hash, but this may also be indicative of a moderation issue.

• (ref ...): a reference to an object. For the programmer, is no different from specifying the object inline. ... can either be the hash address, or a shorthand (eg, std.introduction), and it can have more than one item, specifying a path inside an object. Paths are usually used to point to objects within burls, and within burls, relative paths are often used to refer to other objects within the burl. In the text format, a path is a list. The first item is always either the CID of the parent object or a series of parent backlinks ... After those, all path segments will be positive integers indicating the index of each item being navigated into. In the binary format, it's an enum, 0: cid, 1: backlink. 2: index

• (entity ...): a link to an object, defined in ..., which will either be data or impl.

• (data Type ...): a component in an entity of type Type.

• (impl Type (via ...)): a component in an entity of type Type that is defined in terms of tactics. In rust these are called 'impls'. Each one translates one type into another type, until the impl component produces a way of interpreting this entity as Type.

not mentioned here but will be used later:

• (raw ...): an alternative to entity where the type information isn't included and the data is just right there with no decoration. Never the default. Raw members can't be extended with additional impls or entity components. However, they're far more compact on the wire, and quicker to parse.