Lists

lists

Working document – full specification to follow

principles

1. Internal representation of a @list does not need to use Collections or Containers. Instead it is driven by a sequence CRDT operating on the list items.
2. A List object is reified to a Subject (unlike in JSON-LD) and has an @id, which can be set by the user. This is because it's normal in JSON-LD to be able to create multiple lists for a subject-predicate, but it's necessary to identify the list (not just by its head) when making updates.
3. A List object behaves logically like a Set of slots (@id, pos, object), where pos has its coherence maintained across operations (mapping Kleppmann to an RDF-representable form).
4. Slot pos is represented as a positive integer in json-rql, but can be managed in any way by the list CRDT in play.
5. Slot @id is to identify slots across moves, with the constraint that a slot can only exist once in the list. It can be set by the user by fully specifying the slot (see below).
6. Slot object is not inferred to be in the object position for the predicate whose object is the list, whether for insert or query.
7. Translation to/from containers & collections is possible (e.g. recognising well-formed list nodes (WFLN)).
8. Translation to/from JSON-LD @list is as natural as possible.
9. JSON-LD Context is respected, and supports omission of the @list keyword.
10. List CRDT behaviour is a pluggable @type-driven extension to m-ld, but list representation using @list is built-in. The default list CRDT is rdflseq, which is packaged with m-ld.

syntax

// JSON-LD
{
  '@id': 's',
  'p': {
    // '@id': 'listId' – is allowed here
    // '@type': 'http://m-ld.org/rdflseq' – default, or other
    // Never revert to JSON-LD rdf:List interpretation
    '@list': [
      'foo', // Zeroth position literally means zero, i.e. insert at head
      'bar'
    ]
  }
}
// json-rql indexed slot syntax
{
  '@id': 's',
  'p': {
    '@id': 'listId',
    // @type 'http://m-ld.org/rdflseq' is added if not specified
    // @list key triggers indexed-object interpretation
    '@list': {
      // json-rql index uses a data URI or numeric string
      'data:,0': 'foo',
      // In Javascript index can be a plain number.
      // Anything else errors.
      1: 'bar',
      // Use of the @item keyword means this value is a slot, not a subject item
      2: { '@id': 'mySlot', '@item': 'baz' }
    }
  }
}
// Fully-expanded rdflseq
{
  '@id': 's',
  'p': {
    '@type': 'http://m-ld.org/rdflseq',
    // Slot positions generated or validated by the list type
    'http://m-ld.org/rdflseq/p/10/a': {
      'http://m-ld.org/rdflseq/#item': 'foo'
    },
    'http://m-ld.org/rdflseq/p/20/a': {
      'http://m-ld.org/rdflseq/#item': 'bar'
    }
  }
}
// < s p l >
// # CRDT-generated positions will be unique
// < l pos/10/a o >
// < l pos/20/b p >
// < o item 'foo' >
// < p item 'bar' >

// For reference, RDF Collection in JSON-LD
// This does not create a m-ld list
// Possibly this should WARN that convergence will discombobulate the list
{
  '@id': 's',
  'p': {
    // '@id': firstId – can't specify the list @id this way
    'rdf:first': 'foo',
    'rdf:rest': {
      // '@id': secondId
      'rdf:first': 'bar',
      'rdf:rest': { '@id': 'rdf:nil' }
    }
  }
}

@insert

Using @list. Adds to existing triples, like all inserts.

Create list with genid at < s p ?o >:

This creates a new list even if there is already one at < s p ? >

{
  '@insert': {
    '@id': 's',
    'p': {
      // '@id': '_:b1' – implicit
      '@list': ['foo', 'bar']
    }
    // if 'p': { '@container': '@list' } in context
    // 'p': ['foo', 'bar']
  }
}

Create identified list at < s p ?o > (json-rql):

{
  '@insert': {
    '@id': 's',
    'p': {
      '@id': 'myList',
      '@list': { // May not omit, even if 'p': { '@container': '@list' } in context
        'data:,0': 'foo',
        'data:,1': 'bar'
      }
    }
  }
}

Insert into identified list (JSON-LD):

{
  '@insert': {
    '@id': 'listId',
    // This is not an append, which requires explicit index >= length
    // 🚧 @list at top-level is ignored by JSON-LD processor
    // This interleaves at the head of the list (array index is a strong identifier)
    '@list': ['foo', 'bar']
  }
}

Insert into identified list (json-rql):

Append to list requires list length

{
  '@insert': {
    '@id': 'listId',
    '@list': {
      0: 'foo',
      // Javascript numeric keys are translated to data URIs
      'data:,1': 'bar'
    }
  }
}

Insert multiple at one index in identified list:

{
  '@insert': {
    '@id': 'listId',
    // This inserts two items at the head of the list
    // Note indexed list hash does not nest
    '@list': { 0: ['foo', 'bar'] }
    // Specify slots with
    // '@list': { 0: [{ '@item': 'foo' }, { '@item': 'bar' }] }
    // 🚧 expands internally to '@list': {
    //   'data:,0,0': { '@id': '_:b1', '@item': 'foo', 'mld:#index': 0 }
    //   'data:,0,1': { '@id': '_:b2', '@item': 'bar', 'mld:#index': 0 }
    // }
    // Deeper nesting is nested lists
  }
}

Create nested lists:

List arrays nest by default, per JSON-LD

{
  '@insert': {
    '@id': 's',
    'coordinates': {
      '@id': 'sc',
      '@list': [[0, 0], [1, 1]]
    }
  }
}

Insert new nested list into list:

List hashes do not nest

{
  '@insert': {
    '@id': 's',
    'coordinates': {
      '@id': 'sc',
      '@list': { 0: { '@list': [-1, -1] } }
    }
  }
}

@delete

All < s p ?o > whether ?o is a list or not:

This leaves lists dangling unless 'p': { '@container': '@list' } in context

{
  '@delete': {
    '@id': 's',
    'p': '?'
  }
}

Every list and item at s p, including slots (but not subject items):

{
  '@delete': {
    '@id': 's',
    'p': {
      // '@id': '?' is implicit
      '@list': { '?index': '?item' }
      // 🚧 expands to '?index#listKey': { '@id': '?index#slot', '@item': '?item', 'mld:#index': '?index' }
    }
    // if 'p': { '@container': '@list' } in context
    // 'p': '?i'
  }
}

Specific value at s p and its slot:

{
  // Deletes < list index slot > and < slot item 'foo' >
  '@delete': {
    '@id': '?list',
    '@list': { '?i': 'foo' }
    // 🚧 expands to '?i#listKey': { '@id': '?i#slot', '@item': 'foo', 'mld:#index': '?i' }
    // If '?i' is referenced in a non-list-item position, it is just plain ?i
  },
  '@where': {
    '@id': 's',
    'p': {
      '@id': '?list',
      '@list': { '?i': 'foo' }
      // 🚧 expands to '?i#listKey': { '@id': '?i#slot', '@item': 'foo', 'mld:#index': '?i' }
    }
  }
}

Specific slot by index in a list at < s p ?list >:

{
  '@delete': {
    '@id': '?list',
    '@list': { 5: '?i' }
  },
  '@where': {
    '@id': 's',
    'p': {
      '@id': '?list',
      '@list': { 5: '?i' }
      // 🚧 expands to '?': { '@id': '?', '@item': '?i', 'mld:#index': 5 }
    }
  }
}

update

Move a slot by value (atomically):

{
  // @delete of start index is NOT implicit - without it, list constraint rejects
  '@delete': {
    '@id': '?list',
    '@list': { '?i': { '@id': '?slot', '@item': 'foo' } }
  },
  '@insert': {
    '@id': '?list',
    '@list': { 0: { '@id': '?slot', '@item': 'foo' } }
     // 🚧 expands to 'data:,0': { '@id': '?slot', '@item': 'foo', 'mld:#index': 0 }
  },
  '@where': {
    '@id': 's',
    'p': {
      '@id': '?list',
      '@list': { '?i': { '@id': '?slot', '@item': 'foo' } }
    }
    // SAME AS
    // '@graph': {
    //   '@id': 's',
    //   'p': { '@id': '?list', '@list': '?i' }
    // },
    // '@filter': { '@eq': ['?i', 'foo'] }
  }
}

Move a slot by start index:

{
  '@delete': {
    '@id': '?list',
    '@list': { 5: { '@id': '?slot', '@item': '?i' } }
    // 🚧 expands to '?': { '@id': '?slot', '@item': '?i', 'mld:#index': 5 }
  },
  '@insert': {
    '@id': '?list',
    '@list': { 0: { '@id': '?slot', '@item': '?i' } }
     // 🚧 expands to 'data:,0': { '@id': '?slot', '@item': '?i', 'mld:#index': 0 }
  },
  '@where': {
    '@id': 's',
    'p': {
      '@id': '?list',
      // Same item could be in two slots, which slot moves? – must be explicit
      '@list': { 5: { '@id': '?slot', '@item': '?i' } }
      // 🚧 expands to '?': { '@id': '?slot', '@item': '?i', 'mld:#index': 5 }
      // listKey, slot & index belong to the index variable because item can appear more than once
    }
  }
}

Swap slots:

{
  '@insert': {
    '@id': '?list',
    '@list': { 0: '?i5', 5: '?i0' }
  },
  '@where': {
    '@id': 's',
    'p': {
      '@id': '?list',
      '@list': { 0: '?i0', 5: '?i5' }
    }
  }
}

Replace a slot item:

{
  '@delete': {
    '@id': '?list', '@list': { '?i': 'foo' }
  },
  '@insert': {
    '@id': '?list',
    '@list': { '?i': 'bar' }
     // 🚧 expands to '?i#listKey': { '@id': '?i#slot', '@item': 'bar', 'mld:#index': '?i' }
  },
  '@where': {
    '@id': 's',
    'p': {
      '@id': '?list',
      '@list': { '?i': 'foo' }
      // 🚧 expands to '?i#listKey': { '@id': '?i#slot', '@item': 'foo', 'mld:#index': '?i' }
    }
  }
}

@describe

Does not include list property items unless the list itself is described.

@construct

Infer < s p item > (but lose ordering)

{
  '@construct': { '@id': 's', 'p': '?o' },
  '@where': {
    '@id': 's',
    'p': { '@list': { '?': '?o' } }
  }
}

@select

Select list reference (and anything else at < s p ?o >):

{ '@select': '?list', '@where': { '@id': 's', 'p': '?list' } }

Select item(s) by index:

{
  '@select': '?o',
  '@where': {
    '@id': 's',
    'p': { '@list': { 5: '?o' } }
  }
}

app updates

Format is always fully indexed and identified, e.g.

{
  '@delete': [{ '@id': 's', 'p': { '@id': '.well-known/genid/list1', '@list': { 0: 'foo' } } }],
  '@insert': [{ '@id': 's', 'p': { '@id': '.well-known/genid/list1', '@list': { 0: 'bar' } } }]
}

implementation

1. '@list': {} translation to json-rql syntax
2. List 'constraint' check/apply
3. List index query rewrite

concurrency

Constraint: slot identity can only appear once, lowest wins

Setup

< s p l >
< l rdf:type lseq >
< l 10/a o >
< l 20/a p >
< l 21/a q >
< o item x >
< p item y >
< q item z >

concurrently move q to index 0

Clone a: DELETE { l 30/a q } INSERT { l 4/a q }

Clone b: DELETE { l 30/a q } INSERT { l 6/b q }

move p and q to index 0

Clone a: DELETE { l 30/a q } INSERT { l 4/a q }

Clone b: DELETE { l 20/a p } INSERT { l 6/b p }