Building an Item Store for the itemized environment

My work is supported by members. If you find my work valuable and have the means, consider supporting it with a membership or sponsorship! This members-only article has been made publicly available. You can see more of my work at alexanderobenauer.com.

In this lab report, we look at the Item Store, a database of chronological facts that serves as the itemized environment’s persistent storage.

This year, I’ve been hard at work building a user environment that reifies personal computing of the kind I’ve explored for the last several years — something I can fully live in.

Over the next several lab reports, we’re going to take a deep dive into this environment and its implementation, as well as a bit of the project’s philosophy. This first report is on the environment’s storage mechanism. The next one will cover the environment’s programming language. After that, we’ll move toward the environment’s interface.

First, we will look at the kinds of ideas the Item Store was built to support. Then we will look at how the Item Store works, highlighting some key implementation details.

Itemized interface ideas

My experiments with the user environment for an “OS of the future” over the years initially suggested, and were later supported by, a particular form of persistent storage. Here are some of those early experiments with “itemized” interfaces and environments If you’re already familiar with these demos, feel free to skip ahead.:

Here we’re moving a podcast episode into the top of the note in which we’re recording some ideas from it, as it plays. We can pause and play from the widget in the note, since it isn’t a link to it, but it “is” the episode itself, rendered by our preferred item view.

Here we’re moving a line item from a bank statement into a reminder, so that when the reminder pops up, we can quickly get back to the information we’ll need.

References among items allow you to add anything to anything else; you can add notes or reminders to any other kind of item. You could introduce spaced reminders, which can be used with any other item in your system. The relationship between two items is itself an item, and can have its own attributes and references (such as to the item view chosen to render an item in the context of the referencing item). Attributes are user-defined, so you can create organizations that way too, by setting up queries for specific sets of things, or views that organize things the way you need, much like BeOS’ BFS or Newton OS’ Soup.

It is with references that items can be made up of other items: a to-do list is made of todos, an essay of paragraphs, etc. This allows you to make additional references to any level of granularity: you might reference one to-do from a project’s to-do list in another place, such as an email thread which originally spawned the to-do. In this way, arrangements are fluid, and things can be organized bottom-up or top-down, supporting the eternally evolving associative thinking that we tend to do in our heads. You can view your things in different organizations: by day or by project; by status or by topic; etc., and your system can evolve with your thinking.

Here we open many items in one path, which itself is an item. Since these items are now related by having a common reference (the parent, containing item), the system can prioritize them in a list of items to open when any one of them is open.

We can change views on items. Items are just data, and cannot force one interface with which we interact with them. We can swap out item views on any item at any time.

These basic ideas gestured at the data model demanded by such a system (you can see these and more in the early lab notes, roughly from the second one and on).

And then there were the bigger experiments, which helped home in on the data model.

This is an environment that lets you construct needed views extemporaneously through gestures (source).

This is an interface that automatically organizes your items based on the common references among your item graph (source).

This is OLLOS, an environment that organizes your items on one long timeline (source).

OLLOS was a particularly delightful implementation atop the Item Store, as its interface was largely a visualization of the chronological log of the appended facts.

We can build new item views, for new and existing item types, which can be provided to other, larger (app-like) views, such as the timeline in OLLOS. This is a simple way to extend interfaces, adding new functionality to existing items and views. By providing a default item view for a new kind of item, you can essentially inject that new interface into many existing views where items of your new type may appear.

Implementation

The Item Store is essentially a log of facts. Facts describe things about items. They can be created by user actions, or brought in by providers (more on this later). Queries are used to fetch lists of facts. These facts have an item ID, an attribute name, and a value (among a few other fields, like a timestamp).

Here you can see the facts created by the user dragging an item to a new location on a containing canvas:

The item store is built on a little core written in C. It drives a SQLite database that it uses to store and query our facts. These are the functions it makes available:

void csl_insertFact(CSLDatabase *db,
                    const char *factId,
                    const char *itemId,
                    const char *attribute,
                    const char *value,
                    double numericalValue,
                    const char *type,
                    int flags,
                    const char *timestamp);

CFactsCollection* csl_fetchFacts(CSLDatabase* db,
                                 const char* itemId,
                                 const char* attribute,
                                 const char* value);

CFactsCollection* csl_fetchFactsByValueRange(CSLDatabase* db,
                                             const char* itemId,
                                             const char* attribute,
                                             double valueAtOrAbove,
                                             double valueAtOrBelow);

CFactsCollection* csl_fetchFactsByDate(CSLDatabase* db,
                                       const char* createdAtOrAfter,
                                       const char* createdAtOrBefore);

It is with these four core functions — one for storing new facts, and three for querying them — that we build all of the higher-level ideas that we’ll see in the Item Store next. Everything eventually funnels down to these functions.

I’ve written a few higher-level libraries in a few different languages. They encode conventions — specific ways of using the lower-level facts database for the environment’s purposes, enforcing shared expectations with the facts they store.

We’ll look at some of the higher-level functions in the Swift library. You can insert one or more facts like this:

ItemStore.shared.insert(facts: [
    Fact(
        itemId: "1",
        attribute: "type",
        value: .string("note")
    ),
    Fact(
        itemId: "1",
        attribute: "title",
        value: .string("Hello, world!")
    )
])

Inserting more than one at a time is more efficient because views only receive one update notification, and it is more correct because these facts are given the same timestamp, which is considered by some views when grouping facts to describe changes over time.

We have many helper functions that manage creating facts. For example, to create an item, we simply call:

ItemStore.shared.createItem(
    type: "note",
    attributes: [
        "title": .string("Hello, world!")
    ]
)

This function encodes the given expectations; it takes care of creating all the facts we expect to rely on later.

There’s a few different ways to reference an item from another. In the simplest case, one could create a fact where the value is another item’s ID. But it is often the case that the relationship between two items needs to be an item itself, so this function helps create that item’s various facts:

ItemStore.shared.relateItems(
    fromItemId: "1",
    toItemId: "2",
    referenceType: "content",
    referenceAttributes: [
        "order": .number(0)
    ]
)

The basic query function lets us fetch facts by providing any combination of its parameters:

func fetchFacts(
    itemId: String? = nil,
    attribute: String? = nil,
    value: String? = nil,
    includeDeleted: Bool = false,
    resource: String? = nil
) -> [Fact]

Here’s how we use it:

var facts: [Fact];

// Get all facts for one item
facts = ItemStore.shared.fetchFacts(itemId: "1")

// Get an item's type
facts = ItemStore.shared.fetchFacts(itemId: "1", attribute: "type")

// Find items of a certain type
facts = ItemStore.shared.fetchFacts(attribute: "type", value: "note")

If I provide just an item ID, I get all of that item’s facts. Or if I provide an item ID and an attribute, I get the value for that attribute. And if I provide an attribute and a value, I get all of the IDs of items that have that value.

If we treat multiple facts for one attribute on an item as prior values, then what gets returned is also a historical log of all the prior matches as well.

“Deleting” in the item store is not the same as “erasing”. Here’s the implementation for a function that deletes a fact:

func deleteFact(_ fact: Fact) {
    insert(fact: Fact(
        factId: fact.factId,
        itemId: fact.itemId,
        attribute: fact.attribute,
        value: fact.value,
        numericalValue: fact.numericalValue,
        type: fact.type,
        flags: fact.flags ^ 1,
        timestamp: Date()
    ))
}

When we delete a fact, we are actually inserting a new fact describing the earlier one as deleted. This means that the item store can be a complete chronology of the items it describes.

We can also mark an entire item as deleted, and when we do so, we can name a successor item:

ItemStore.shared.deleteItem(itemId: "1", successorItemId: "2")

This creates a reference between the deleted item and the successor item, helping to describe your item graph’s connections more completely. For example, when you send an email, a “draft” email item is deleted, but can be referenced by the “sent” message that succeeds it. When you view that sent message later, it can be easy to jump into its draft, to view earlier variations, this way.

We can push subscriptions to new facts low in the UI subtree, and get very precise about what kinds of updates we want to consider when updating our UIs — down to one specific attribute, if we’d like. These two techniques — pushing subscriptions lower in the subtree, and using more precise queries — make our interface updates very efficient.

For example, we can do something like this:

struct VCText: View {
    let itemId: String
    let attribute: String
    var defaultText: String? = nil

    var body: some View {
        ItemStoreValue {
            ItemStore.shared.fetchFacts(
                itemId: itemId,
                attribute: attribute
            ).first?.typedValue?.stringValue ?? defaultText
        } content: { text in
            Text(text)
        }
    }
}

An update only occurs when this particular attribute about this particular item is updated with a new fact, and only the Text component will be updated. Instead of updating a large view with many subviews on any update to an entire item, this method of connecting queries for specific facts to view components keeps things efficient.

This is such a common method that when prototyping new views, I usually start with pre-made view components:

struct TodoItemView: View {
    let itemId: String

    var body: some View {
        HStack(alignment: .center, spacing: 4) {
            VCCheckbox(itemId: itemId, attribute: "complete")
            VCText(itemId: itemId, attribute: "title")
        }
    }
}

I provide only an item ID and attribute name, and these components will internally handle representing the most recent fact’s value, and submitting new facts when the user interacts with their controls.

Interfaces that act like today’s programs are often, in fact, just large item views. Just as an item view for a “todo” takes an item ID and renders the proper interface from there, an item view for a “canvas” of many elements also simply takes an item ID, and renders its content references accordingly.

Providers are modules that bring items into user systems, such as an IMAP or CalDAV provider. The Item Store runs on multiple SQLite databases internally; besides the user’s own for facts generated by local actions, each provider gets its own. Results for queries are a union set of the results from each database. This means users have the final say on what is in their environments: facts they save in their own database can shadow any fact vended by a provider. This includes being able to choose with what item view they prefer to render and interact with any item.

I’ve imeplemented syncing in two different ways in the past: We can connect devices to one another so that each synced device appears as its own provider on the others, with its own database. I also built a replacement for the core C library that uses Core Data to enable CloudKit’s sync engine. The lower-level storage mechanism is an “Item Drive” with which we can swap implementations, so long as they implement the four functions we looked at initially.

The Item Store has been designed and evolved to support my experiments with itemized environments. I do not yet know enough about the landscape in which its concepts reside, so I can make no certain claims about any novelty it presents. I can, however, present the existing projects from which its design grew inspiration:

Datomic has been a rich source of clear thinking around an implementation in this space. You can read about Datomic’s data model here, which helped inform some of the trickier pieces of the Item Store’s own implementation. The Item Store’s concepts and use have also taken inspiration from triplestores and tuple spaces, as well as the above mentioned filesystems BFS (found in BeOS) and Soup (found in Newton OS), and concepts from Google Wave and OpenDoc.

For many of these references and conversations over demos, I owe gratitude to John Underkoffler, Alex Warth, Chet Corcos, and Andy Milburn.

You can also see the docs for an earlier implementation of the item store in a readme on GitHub here.

My work is supported by members. If you find my work valuable and have the means, consider supporting it with a membership or sponsorship! This members-only article has been made publicly available. You can see more of my work at alexanderobenauer.com.