Add model and serd-sort utility

With all the new functionality, the complexity of the serd-pipe command-line
interface is starting to push the limits of available flags. So, instead of
grafting on further options to control a model, this commit adds a new tool,
serd-sort, which acts somewhat like a stripped-down serd-pipe that stores
statements in a model in memory.

This keeps the complexity (including the user-facing complexity) of any one
tool down, since other more focused tools can be used for streaming tasks in a
pipeline.

In other words, abandon Swissarmyknifeism, take a page from the Unix
philosophy, and try to expose the model functionality to the command-line in a
dedicated focused tool.  The model implementation is tested by using this tool
to run a subset of the usual test suites, and a special suite to test statement
sorting.

10 files changed, 1793 insertions, 1 deletions

diff --git a/src/compare.c b/src/compare.c
new file mode 100644
index 00000000..2ce49cc2
--- /dev/null
+++ b/src/compare.c
@@ -0,0 +1,147 @@
+// Copyright 2011-2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "compare.h"
+
+#include "statement.h" // IWYU pragma: keep
+
+#include "serd/node.h"
+#include "serd/statement.h"
+#include "zix/attributes.h"
+
+#include <assert.h>
+
+/// Compare a mandatory node with a node pattern
+ZIX_PURE_FUNC static inline int
+serd_node_wildcard_compare(const SerdNode* ZIX_NONNULL  a,
+                           const SerdNode* ZIX_NULLABLE b)
+{
+  assert(a);
+  return b ? serd_node_compare(a, b) : 0;
+}
+
+/// Compare an optional graph node with a node pattern
+static inline int
+serd_node_graph_compare(const SerdNode* ZIX_NULLABLE a,
+                        const SerdNode* ZIX_NULLABLE b)
+{
+  if (a == b) {
+    return 0;
+  }
+
+  if (!a) {
+    return -1;
+  }
+
+  if (!b) {
+    return 1;
+  }
+
+  return serd_node_compare(a, b);
+}
+
+/// Compare statements lexicographically, ignoring graph
+int
+serd_triple_compare(const void* const x,
+                    const void* const y,
+                    const void* const user_data)
+{
+  const int* const           ordering = (const int*)user_data;
+  const SerdStatement* const s        = (const SerdStatement*)x;
+  const SerdStatement* const t        = (const SerdStatement*)y;
+
+  for (unsigned i = 0U; i < 3U; ++i) {
+    const int o = ordering[i];
+    assert(o < 3);
+
+    const int c = serd_node_compare(s->nodes[o], t->nodes[o]);
+    if (c) {
+      return c;
+    }
+  }
+
+  return 0;
+}
+
+/**
+   Compare statments with statement patterns lexicographically, ignoring graph.
+
+   Null nodes in the second argument are treated as wildcards, always less than
+   any node.
+*/
+int
+serd_triple_compare_pattern(const void* const x,
+                            const void* const y,
+                            const void* const user_data)
+{
+  const int* const           ordering = (const int*)user_data;
+  const SerdStatement* const s        = (const SerdStatement*)x;
+  const SerdStatement* const t        = (const SerdStatement*)y;
+
+  for (unsigned i = 0U; i < 3U; ++i) {
+    const int o = ordering[i];
+    assert(o < 3);
+
+    const int c = serd_node_wildcard_compare(s->nodes[o], t->nodes[o]);
+    if (c) {
+      return c;
+    }
+  }
+
+  return 0;
+}
+
+/// Compare statements lexicographically
+int
+serd_quad_compare(const void* const x,
+                  const void* const y,
+                  const void* const user_data)
+{
+  const int* const           ordering = (const int*)user_data;
+  const SerdStatement* const s        = (const SerdStatement*)x;
+  const SerdStatement* const t        = (const SerdStatement*)y;
+
+  for (unsigned i = 0U; i < 4U; ++i) {
+    const int o = ordering[i];
+    const int c =
+      (o == SERD_GRAPH)
+        ? serd_node_graph_compare(s->nodes[SERD_GRAPH], t->nodes[SERD_GRAPH])
+        : serd_node_compare(s->nodes[o], t->nodes[o]);
+
+    if (c) {
+      return c;
+    }
+  }
+
+  return 0;
+}
+
+/**
+   Compare statments with statement patterns lexicographically.
+
+   Null nodes in the second argument are treated as wildcards, always less than
+   any node.
+*/
+int
+serd_quad_compare_pattern(const void* const x,
+                          const void* const y,
+                          const void* const user_data)
+{
+  const int* const           ordering = (const int*)user_data;
+  const SerdStatement* const s        = (const SerdStatement*)x;
+  const SerdStatement* const t        = (const SerdStatement*)y;
+
+  for (unsigned i = 0U; i < 4U; ++i) {
+    const int o = ordering[i];
+    const int c =
+      (o == SERD_GRAPH)
+        ? serd_node_graph_compare(s->nodes[SERD_GRAPH], t->nodes[SERD_GRAPH])
+        : serd_node_wildcard_compare(s->nodes[o], t->nodes[o]);
+
+    if (c) {
+      return c;
+    }
+  }
+
+  return 0;
+}
diff --git a/src/compare.h b/src/compare.h
new file mode 100644
index 00000000..f4dbc046
--- /dev/null
+++ b/src/compare.h
@@ -0,0 +1,37 @@
+// Copyright 2011-2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef SERD_SRC_COMPARE_H
+#define SERD_SRC_COMPARE_H
+
+#include "zix/attributes.h"
+
+/// Compare statements lexicographically, ignoring graph
+ZIX_PURE_FUNC int
+serd_triple_compare(const void* x, const void* y, const void* user_data);
+
+/**
+   Compare statments with statement patterns lexicographically, ignoring graph.
+
+   Null nodes in the second argument are treated as wildcards, always less than
+   any node.
+*/
+ZIX_PURE_FUNC int
+serd_triple_compare_pattern(const void* x,
+                            const void* y,
+                            const void* user_data);
+
+/// Compare statements lexicographically
+ZIX_PURE_FUNC int
+serd_quad_compare(const void* x, const void* y, const void* user_data);
+
+/**
+   Compare statments with statement patterns lexicographically.
+
+   Null nodes in the second argument are treated as wildcards, always less than
+   any node.
+*/
+ZIX_PURE_FUNC int
+serd_quad_compare_pattern(const void* x, const void* y, const void* user_data);
+
+#endif // ZIX_SRC_COMPARE_H
diff --git a/src/cursor.c b/src/cursor.c
new file mode 100644
index 00000000..d6a86d19
--- /dev/null
+++ b/src/cursor.c
@@ -0,0 +1,224 @@
+// Copyright 2011-2020 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "cursor.h"
+
+#include "memory.h"
+#include "model.h"
+#include "node.h"
+#include "statement.h"
+
+#include "serd/log.h"
+#include "serd/memory.h"
+#include "serd/statement.h"
+#include "zix/attributes.h"
+#include "zix/btree.h"
+#include "zix/status.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <string.h>
+
+static inline bool
+statement_matches_quad(const SerdStatement* const statement,
+                       const SerdNode* const      quad[4])
+{
+  return serd_statement_matches(statement, quad[0], quad[1], quad[2], quad[3]);
+}
+
+ZIX_PURE_FUNC bool
+serd_iter_in_range(const ZixBTreeIter    iter,
+                   const SerdNode* const pattern[4],
+                   const ScanStrategy    strategy)
+{
+  const SerdStatement* const statement =
+    (const SerdStatement*)zix_btree_get(iter);
+
+  for (unsigned i = 0U; i < strategy.n_prefix; ++i) {
+    const unsigned field = orderings[strategy.order][i];
+    if (!serd_node_pattern_match(statement->nodes[field], pattern[field])) {
+      return false;
+    }
+  }
+
+  return true;
+}
+
+static bool
+serd_cursor_in_range(const SerdCursor* const cursor)
+{
+  return (cursor->strategy.mode == FILTER_EVERYTHING ||
+          serd_iter_in_range(cursor->iter, cursor->pattern, cursor->strategy));
+}
+
+/// Seek forward as necessary until the cursor points to a matching statement
+static SerdStatus
+serd_cursor_seek_match(SerdCursor* const cursor)
+{
+  assert(cursor->strategy.mode == FILTER_EVERYTHING ||
+         cursor->strategy.mode == FILTER_RANGE);
+
+  for (; !zix_btree_iter_is_end(cursor->iter);
+       zix_btree_iter_increment(&cursor->iter)) {
+    if (!serd_cursor_in_range(cursor)) {
+      // Went past the end of the matching range, reset to end
+      cursor->iter = zix_btree_end_iter;
+      return SERD_FAILURE;
+    }
+
+    const SerdStatement* s = (const SerdStatement*)zix_btree_get(cursor->iter);
+    if (statement_matches_quad(s, cursor->pattern)) {
+      break; // Found matching statement
+    }
+  }
+
+  return SERD_SUCCESS;
+}
+
+static bool
+check_version(const SerdCursor* const cursor)
+{
+  if (cursor->version != cursor->model->version) {
+    serd_logf(cursor->model->world,
+              SERD_LOG_LEVEL_ERROR,
+              "attempt to use invalidated cursor");
+    return false;
+  }
+
+  return true;
+}
+
+SerdCursor
+serd_cursor_make(const SerdModel* const model,
+                 const ZixBTreeIter     iter,
+                 const SerdNode* const  pattern[4],
+                 const ScanStrategy     strategy)
+{
+  SerdCursor cursor = {model,
+                       {pattern[0], pattern[1], pattern[2], pattern[3]},
+                       model->version,
+                       iter,
+                       strategy};
+
+  if (strategy.mode == FILTER_RANGE || strategy.mode == FILTER_EVERYTHING) {
+    serd_cursor_seek_match(&cursor);
+  }
+
+#ifndef NDEBUG
+  if (!zix_btree_iter_is_end(cursor.iter)) {
+    // Check that the cursor is at a matching statement
+    const SerdStatement* first =
+      (const SerdStatement*)zix_btree_get(cursor.iter);
+    assert(statement_matches_quad(first, pattern));
+
+    // Check that any nodes in the pattern are interned
+    for (unsigned i = 0U; i < 3; ++i) {
+      assert(!cursor.pattern[i] || cursor.pattern[i] == first->nodes[i]);
+    }
+  }
+#endif
+
+  return cursor;
+}
+
+SerdCursor*
+serd_cursor_copy(SerdAllocator* const allocator, const SerdCursor* const cursor)
+{
+  if (!cursor) {
+    return NULL;
+  }
+
+  SerdCursor* const copy =
+    (SerdCursor* const)serd_amalloc(allocator, sizeof(SerdCursor));
+
+  if (copy) {
+    memcpy(copy, cursor, sizeof(SerdCursor));
+  }
+
+  return copy;
+}
+
+const SerdStatement*
+serd_cursor_get(const SerdCursor* const cursor)
+{
+  return (
+    (cursor && !zix_btree_iter_is_end(cursor->iter) && check_version(cursor))
+      ? (const SerdStatement*)zix_btree_get(cursor->iter)
+      : NULL);
+}
+
+SerdStatus
+serd_cursor_scan_next(SerdCursor* const cursor)
+{
+  if (zix_btree_iter_is_end(cursor->iter) || !check_version(cursor)) {
+    return SERD_BAD_CURSOR;
+  }
+
+  switch (cursor->strategy.mode) {
+  case SCAN_EVERYTHING:
+    break;
+
+  case SCAN_RANGE:
+    if (!serd_cursor_in_range(cursor)) {
+      // Went past the end of the matching range
+      cursor->iter = zix_btree_end_iter;
+      return SERD_FAILURE;
+    }
+    break;
+
+  case FILTER_EVERYTHING:
+  case FILTER_RANGE:
+    // Seek forward to next match
+    return serd_cursor_seek_match(cursor);
+  }
+
+  return SERD_SUCCESS;
+}
+
+SerdStatus
+serd_cursor_advance(SerdCursor* const cursor)
+{
+  if (!cursor) {
+    return SERD_FAILURE;
+  }
+
+  if (zix_btree_iter_is_end(cursor->iter) || !check_version(cursor)) {
+    return SERD_BAD_CURSOR;
+  }
+
+  const ZixStatus zst = zix_btree_iter_increment(&cursor->iter);
+  if (zst) {
+    assert(zst == ZIX_STATUS_REACHED_END);
+    return SERD_FAILURE;
+  }
+
+  return serd_cursor_scan_next(cursor);
+}
+
+bool
+serd_cursor_is_end(const SerdCursor* const cursor)
+{
+  return !cursor || zix_btree_iter_is_end(cursor->iter);
+}
+
+bool
+serd_cursor_equals(const SerdCursor* const lhs, const SerdCursor* const rhs)
+{
+  if (serd_cursor_is_end(lhs) || serd_cursor_is_end(rhs)) {
+    return serd_cursor_is_end(lhs) && serd_cursor_is_end(rhs);
+  }
+
+  /* We don't bother checking if the patterns match each other here, or if both
+     cursors have the same ordering, since both of these must be true if the
+     BTree iterators are equal. */
+
+  return (zix_btree_iter_equals(lhs->iter, rhs->iter) &&
+          lhs->strategy.mode == rhs->strategy.mode &&
+          lhs->strategy.n_prefix == rhs->strategy.n_prefix);
+}
+
+void
+serd_cursor_free(SerdAllocator* const allocator, SerdCursor* const cursor)
+{
+  serd_afree(allocator, cursor);
+}
diff --git a/src/cursor.h b/src/cursor.h
new file mode 100644
index 00000000..d7de7471
--- /dev/null
+++ b/src/cursor.h
@@ -0,0 +1,71 @@
+// Copyright 2011-2020 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef SERD_SRC_CURSOR_H
+#define SERD_SRC_CURSOR_H
+
+#include "serd/cursor.h"
+#include "serd/model.h"
+#include "serd/node.h"
+#include "serd/status.h"
+#include "zix/btree.h"
+
+#include <stdbool.h>
+#include <stddef.h>
+
+#define N_STATEMENT_ORDERS 12u
+
+/// An iteration mode that determines what to skip and when to end
+typedef enum {
+  SCAN_EVERYTHING,   ///< Iterate over entire store
+  SCAN_RANGE,        ///< Iterate over range with equal prefix
+  FILTER_EVERYTHING, ///< Iterate to end of store, filtering
+  FILTER_RANGE,      ///< Iterate over range with equal prefix, filtering
+} ScanMode;
+
+/// A strategy for searching and iterating over a statement index
+typedef struct {
+  ScanMode           mode;     ///< Iteration mode
+  unsigned           n_prefix; ///< Number of prefix nodes that match the index
+  SerdStatementOrder order;    ///< Order of index to scan
+} ScanStrategy;
+
+struct SerdCursorImpl {
+  const SerdModel* model;      ///< Model being iterated over
+  const SerdNode*  pattern[4]; ///< Search pattern (nodes in model or null)
+  size_t           version;    ///< Model version when iterator was created
+  ZixBTreeIter     iter;       ///< Current position in index
+  ScanStrategy     strategy;   ///< Index scanning strategy
+};
+
+/// Lookup table of ordered indices for each SerdStatementOrder
+static const unsigned orderings[N_STATEMENT_ORDERS][4] = {
+  {0U, 1U, 2U, 3U}, // SPOG
+  {0U, 2U, 1U, 3U}, // SOPG
+  {2U, 1U, 0U, 3U}, // OPSG
+  {2U, 0U, 1U, 3U}, // OPSG
+  {1U, 0U, 2U, 3U}, // PSOG
+  {1U, 2U, 0U, 3U}, // PSOG
+  {3U, 0U, 1U, 2U}, // GSPO
+  {3U, 0U, 2U, 1U}, // GSPO
+  {3U, 2U, 1U, 0U}, // GOPS
+  {3U, 2U, 0U, 1U}, // GOPS
+  {3U, 1U, 0U, 2U}, // GPSO
+  {3U, 1U, 2U, 0U}  // GPSO
+};
+
+SerdCursor
+serd_cursor_make(const SerdModel*      model,
+                 ZixBTreeIter          iter,
+                 const SerdNode* const pattern[4],
+                 ScanStrategy          strategy);
+
+SerdStatus
+serd_cursor_scan_next(SerdCursor* cursor);
+
+bool
+serd_iter_in_range(ZixBTreeIter          iter,
+                   const SerdNode* const pattern[4],
+                   ScanStrategy          strategy);
+
+#endif // SERD_SRC_CURSOR_H
diff --git a/src/describe.c b/src/describe.c
new file mode 100644
index 00000000..a7012cf9
--- /dev/null
+++ b/src/describe.c
@@ -0,0 +1,314 @@
+// Copyright 2011-2023 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "cursor.h"
+#include "model.h"
+#include "world.h"
+
+// Define the types used in the hash interface for more type safety
+#define ZIX_HASH_KEY_TYPE const SerdNode
+#define ZIX_HASH_RECORD_TYPE const SerdNode
+
+#include "serd/cursor.h"
+#include "serd/describe.h"
+#include "serd/memory.h"
+#include "serd/model.h"
+#include "serd/node.h"
+#include "serd/sink.h"
+#include "serd/statement.h"
+#include "serd/status.h"
+#include "serd/world.h"
+#include "zix/allocator.h"
+#include "zix/attributes.h"
+#include "zix/digest.h"
+#include "zix/hash.h"
+#include "zix/status.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+typedef enum { NAMED, ANON_S, ANON_O, LIST_S, LIST_O } NodeStyle;
+
+typedef struct {
+  SerdAllocator*    allocator;     // Allocator for auxiliary structures
+  const SerdModel*  model;         // Model to read from
+  const SerdSink*   sink;          // Sink to write description to
+  ZixHash*          list_subjects; // Nodes written in the current list or null
+  SerdDescribeFlags flags;         // Flags to control description
+} DescribeContext;
+
+static SerdStatus
+write_range_statement(const DescribeContext* ctx,
+                      unsigned               depth,
+                      SerdStatementFlags     statement_flags,
+                      const SerdStatement*   statement,
+                      const SerdNode*        last_subject,
+                      bool                   write_types);
+
+static NodeStyle
+get_node_style(const SerdModel* const model, const SerdNode* const node)
+{
+  if (serd_node_type(node) != SERD_BLANK) {
+    return NAMED; // Non-blank node can't be anonymous
+  }
+
+  const size_t n_as_object = serd_model_count(model, NULL, NULL, node, NULL);
+  if (n_as_object > 1) {
+    return NAMED; // Blank node referred to several times
+  }
+
+  if (serd_model_count(model, node, model->world->rdf_first, NULL, NULL) == 1 &&
+      serd_model_count(model, node, model->world->rdf_rest, NULL, NULL) == 1 &&
+      !serd_model_ask(model, NULL, model->world->rdf_rest, node, NULL)) {
+    return n_as_object == 0 ? LIST_S : LIST_O;
+  }
+
+  return n_as_object == 0 ? ANON_S : ANON_O;
+}
+
+static const SerdNode*
+identity(const SerdNode* const record)
+{
+  return record;
+}
+
+static ZixHashCode
+ptr_hash(const SerdNode* const ptr)
+{
+  return zix_digest(0U, &ptr, sizeof(SerdNode*));
+}
+
+static bool
+ptr_equals(const SerdNode* const a, const SerdNode* const b)
+{
+  return *(const void* const*)a == *(const void* const*)b;
+}
+
+static SerdStatus
+write_pretty_range(const DescribeContext* const ctx,
+                   const unsigned               depth,
+                   SerdCursor* const            range,
+                   const SerdNode*              last_subject,
+                   bool                         write_types)
+{
+  SerdStatus           st        = SERD_SUCCESS;
+  const SerdStatement* statement = serd_cursor_get(range);
+
+  while (statement) {
+    // Write this statement (and possibly more to describe anonymous nodes)
+    if ((st = write_range_statement(
+           ctx, depth, 0U, statement, last_subject, write_types))) {
+      break;
+    }
+
+    // Update the last subject and advance the cursor
+    last_subject = serd_statement_subject(statement);
+    st           = serd_cursor_advance(range);
+    statement    = serd_cursor_get(range);
+  }
+
+  return st > SERD_FAILURE ? st : SERD_SUCCESS;
+}
+
+static SerdStatus
+write_list(const DescribeContext* const ctx,
+           const unsigned               depth,
+           SerdStatementFlags           flags,
+           const SerdNode*              node,
+           const SerdNode* const        graph)
+{
+  const SerdModel* const model     = ctx->model;
+  const SerdWorld* const world     = model->world;
+  const SerdSink* const  sink      = ctx->sink;
+  const SerdNode* const  rdf_first = world->rdf_first;
+  const SerdNode* const  rdf_rest  = world->rdf_rest;
+  const SerdNode* const  rdf_nil   = world->rdf_nil;
+  SerdStatus             st        = SERD_SUCCESS;
+
+  const SerdStatement* fs =
+    serd_model_get_statement(model, node, rdf_first, NULL, graph);
+
+  assert(fs); // Shouldn't get here if it doesn't at least have an rdf:first
+
+  while (!st && !serd_node_equals(node, rdf_nil)) {
+    // Write rdf:first statement for this node
+    if ((st = write_range_statement(ctx, depth, flags, fs, NULL, false))) {
+      return st;
+    }
+
+    // Get rdf:rest statement
+    const SerdStatement* const rs =
+      serd_model_get_statement(model, node, rdf_rest, NULL, graph);
+
+    if (!rs) {
+      // Terminate malformed list with missing rdf:rest
+      return serd_sink_write(sink, 0, node, rdf_rest, rdf_nil, graph);
+    }
+
+    // Terminate if the next node has no rdf:first
+    const SerdNode* const next = serd_statement_object(rs);
+    if (!(fs = serd_model_get_statement(model, next, rdf_first, NULL, graph))) {
+      return serd_sink_write(sink, 0, node, rdf_rest, rdf_nil, graph);
+    }
+
+    // Write rdf:next statement and move to the next node
+    st    = serd_sink_write_statement(sink, 0, rs);
+    node  = next;
+    flags = 0U;
+  }
+
+  return st;
+}
+
+static bool
+skip_range_statement(const SerdModel* const     model,
+                     const SerdStatement* const statement)
+{
+  const SerdNode* const subject       = serd_statement_subject(statement);
+  const NodeStyle       subject_style = get_node_style(model, subject);
+  const SerdNode* const predicate     = serd_statement_predicate(statement);
+
+  if (subject_style == ANON_O || subject_style == LIST_O) {
+    return true; // Skip subject that will be inlined elsewhere
+  }
+
+  if (subject_style == LIST_S &&
+      (serd_node_equals(predicate, model->world->rdf_first) ||
+       serd_node_equals(predicate, model->world->rdf_rest))) {
+    return true; // Skip list statement that write_list will handle
+  }
+
+  return false;
+}
+
+static SerdStatus
+write_subject_types(const DescribeContext* const ctx,
+                    const unsigned               depth,
+                    const SerdNode* const        subject,
+                    const SerdNode* const        graph)
+{
+  SerdCursor* const t = serd_model_find(ctx->allocator,
+                                        ctx->model,
+                                        subject,
+                                        ctx->model->world->rdf_type,
+                                        NULL,
+                                        graph);
+
+  const SerdStatus st =
+    t ? write_pretty_range(ctx, depth + 1, t, subject, true) : SERD_SUCCESS;
+
+  serd_cursor_free(ctx->allocator, t);
+  return st;
+}
+
+static bool
+types_first_for_subject(const DescribeContext* const ctx, const NodeStyle style)
+{
+  return style != LIST_S && !(ctx->flags & SERD_NO_TYPE_FIRST);
+}
+
+static SerdStatus
+write_range_statement(const DescribeContext* const     ctx,
+                      const unsigned                   depth,
+                      SerdStatementFlags               statement_flags,
+                      const SerdStatement* ZIX_NONNULL statement,
+                      const SerdNode* ZIX_NULLABLE     last_subject,
+                      const bool                       write_types)
+{
+  const SerdModel* const model         = ctx->model;
+  const SerdSink* const  sink          = ctx->sink;
+  const SerdNode* const  subject       = serd_statement_subject(statement);
+  const NodeStyle        subject_style = get_node_style(model, subject);
+  const SerdNode* const  predicate     = serd_statement_predicate(statement);
+  const SerdNode* const  object        = serd_statement_object(statement);
+  const NodeStyle        object_style  = get_node_style(model, object);
+  const SerdNode* const  graph         = serd_statement_graph(statement);
+  SerdStatus             st            = SERD_SUCCESS;
+
+  if (depth == 0U) {
+    if (skip_range_statement(model, statement)) {
+      return SERD_SUCCESS; // Skip subject that will be inlined elsewhere
+    }
+
+    if (subject_style == LIST_S) {
+      // First write inline list subject, which this statement will follow
+      if (zix_hash_insert(ctx->list_subjects, subject) != ZIX_STATUS_EXISTS) {
+        st = write_list(ctx, 2, statement_flags | SERD_LIST_S, subject, graph);
+      }
+    }
+  }
+
+  if (st) {
+    return st;
+  }
+
+  // If this is a new subject, write types first if necessary
+  const bool types_first = types_first_for_subject(ctx, subject_style);
+  if (subject != last_subject && types_first) {
+    st = write_subject_types(ctx, depth, subject, graph);
+  }
+
+  // Skip type statement if it would be written another time (just above)
+  if (subject_style != LIST_S && !write_types &&
+      serd_node_equals(predicate, model->world->rdf_type)) {
+    return st;
+  }
+
+  // Set up the flags for this statement
+  statement_flags |=
+    (((subject_style == ANON_S) * (SerdStatementFlags)SERD_EMPTY_S) |
+     ((object_style == ANON_O) * (SerdStatementFlags)SERD_ANON_O) |
+     ((object_style == LIST_O) * (SerdStatementFlags)SERD_LIST_O));
+
+  // Finally write this statement
+  if ((st = serd_sink_write_statement(sink, statement_flags, statement))) {
+    return st;
+  }
+
+  if (object_style == ANON_O) {
+    // Follow an anonymous object with its description like "[ ... ]"
+    SerdCursor* const iter =
+      serd_model_find(ctx->allocator, model, object, NULL, NULL, NULL);
+
+    if (!(st = write_pretty_range(ctx, depth + 1, iter, last_subject, false))) {
+      st = serd_sink_write_end(sink, object);
+    }
+
+    serd_cursor_free(ctx->allocator, iter);
+
+  } else if (object_style == LIST_O) {
+    // Follow a list object with its description like "( ... )"
+    st = write_list(ctx, depth + 1, 0U, object, graph);
+  }
+
+  return st;
+}
+
+SerdStatus
+serd_describe_range(SerdAllocator* const    allocator,
+                    const SerdCursor* const range,
+                    const SerdSink*         sink,
+                    const SerdDescribeFlags flags)
+{
+  if (serd_cursor_is_end(range)) {
+    return SERD_SUCCESS;
+  }
+
+  assert(sink);
+
+  SerdCursor copy = *range;
+
+  ZixHash* const list_subjects =
+    zix_hash_new((ZixAllocator*)allocator, identity, ptr_hash, ptr_equals);
+
+  SerdStatus st = SERD_BAD_ALLOC;
+  if (list_subjects) {
+    DescribeContext ctx = {allocator, range->model, sink, list_subjects, flags};
+
+    st = write_pretty_range(&ctx, 0, &copy, NULL, (flags & SERD_NO_TYPE_FIRST));
+  }
+
+  zix_hash_free(list_subjects);
+  return st;
+}
diff --git a/src/inserter.c b/src/inserter.c
new file mode 100644
index 00000000..f3b8631b
--- /dev/null
+++ b/src/inserter.c
@@ -0,0 +1,146 @@
+// Copyright 2011-2020 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "memory.h"
+#include "model.h"
+#include "statement.h"
+
+#include "serd/caret.h"
+#include "serd/event.h"
+#include "serd/inserter.h"
+#include "serd/log.h"
+#include "serd/model.h"
+#include "serd/node.h"
+#include "serd/nodes.h"
+#include "serd/sink.h"
+#include "serd/statement.h"
+#include "serd/status.h"
+#include "serd/uri.h"
+#include "serd/world.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+typedef struct {
+  SerdModel* model;
+  SerdNode*  default_graph;
+} SerdInserterData;
+
+static bool
+can_insert(SerdWorld* const world, const SerdNode* const node)
+{
+  if (node) {
+    switch (serd_node_type(node)) {
+    case SERD_LITERAL:
+      return can_insert(world, serd_node_datatype(node));
+
+    case SERD_URI:
+      if (!serd_uri_string_has_scheme(serd_node_string(node))) {
+        serd_logf(world,
+                  SERD_LOG_LEVEL_ERROR,
+                  "attempt to insert relative URI <%s> into model",
+                  serd_node_string(node));
+        return false;
+      }
+      break;
+
+    case SERD_BLANK:
+    case SERD_VARIABLE:
+      break;
+    }
+  }
+
+  return true;
+}
+
+static SerdStatus
+serd_inserter_on_statement(SerdInserterData* const    data,
+                           const SerdStatementFlags   flags,
+                           const SerdStatement* const statement)
+{
+  (void)flags;
+
+  SerdModel* const model = data->model;
+  SerdWorld* const world = model->world;
+
+  // Check that every node is expanded so it is context-free
+  for (unsigned i = 0; i < 4; ++i) {
+    if (!can_insert(world, serd_statement_node(statement, (SerdField)i))) {
+      return SERD_BAD_DATA;
+    }
+  }
+
+  const SerdNode* const s =
+    serd_nodes_intern(model->nodes, serd_statement_subject(statement));
+
+  const SerdNode* const p =
+    serd_nodes_intern(model->nodes, serd_statement_predicate(statement));
+
+  const SerdNode* const o =
+    serd_nodes_intern(model->nodes, serd_statement_object(statement));
+
+  const SerdNode* const g = serd_nodes_intern(
+    model->nodes,
+    serd_statement_graph(statement) ? serd_statement_graph(statement)
+                                    : data->default_graph);
+
+  const SerdCaret* const caret =
+    (data->model->flags & SERD_STORE_CARETS) ? statement->caret : NULL;
+
+  const SerdStatus st =
+    serd_model_add_with_caret(data->model, s, p, o, g, caret);
+
+  return st > SERD_FAILURE ? st : SERD_SUCCESS;
+}
+
+static SerdStatus
+serd_inserter_on_event(void* const handle, const SerdEvent* const event)
+{
+  SerdInserterData* const data = (SerdInserterData*)handle;
+
+  if (event->type == SERD_STATEMENT) {
+    return serd_inserter_on_statement(
+      data, event->statement.flags, event->statement.statement);
+  }
+
+  return SERD_SUCCESS;
+}
+
+static SerdInserterData*
+serd_inserter_data_new(SerdModel* const      model,
+                       const SerdNode* const default_graph)
+{
+  SerdInserterData* const data =
+    (SerdInserterData*)serd_wcalloc(model->world, 1, sizeof(SerdInserterData));
+
+  if (data) {
+    data->model         = model;
+    data->default_graph = serd_node_copy(model->allocator, default_graph);
+  }
+
+  return data;
+}
+
+static void
+serd_inserter_data_free(void* const ptr)
+{
+  SerdInserterData* const data = (SerdInserterData*)ptr;
+  serd_node_free(data->model->allocator, data->default_graph);
+  serd_wfree(data->model->world, data);
+}
+
+SerdSink*
+serd_inserter_new(SerdModel* const model, const SerdNode* const default_graph)
+{
+  assert(model);
+
+  SerdEventFunc           func = serd_inserter_on_event;
+  SerdInserterData* const data = serd_inserter_data_new(model, default_graph);
+
+  return data ? serd_sink_new(serd_world_allocator(model->world),
+                              data,
+                              func,
+                              (SerdFreeFunc)serd_inserter_data_free)
+              : NULL;
+}
diff --git a/src/model.c b/src/model.c
new file mode 100644
index 00000000..89b37d83
--- /dev/null
+++ b/src/model.c
@@ -0,0 +1,820 @@
+// Copyright 2011-2020 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "model.h"
+
+#include "caret.h"
+#include "compare.h"
+#include "cursor.h"
+#include "memory.h"
+#include "statement.h"
+
+#include "serd/caret.h"
+#include "serd/log.h"
+#include "serd/node.h"
+#include "serd/statement.h"
+#include "serd/status.h"
+#include "zix/allocator.h"
+#include "zix/btree.h"
+#include "zix/status.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+static const SerdNode* const everything_pattern[4] = {NULL, NULL, NULL, NULL};
+
+/// A 3-bit signature for a triple pattern used as a table index
+typedef enum {
+  SERD_SIGNATURE_XXX, // 000 (???)
+  SERD_SIGNATURE_XXO, // 001 (??O)
+  SERD_SIGNATURE_XPX, // 010 (?P?)
+  SERD_SIGNATURE_XPO, // 011 (?PO)
+  SERD_SIGNATURE_SXX, // 100 (S??)
+  SERD_SIGNATURE_SXO, // 101 (S?O)
+  SERD_SIGNATURE_SPX, // 110 (SP?)
+  SERD_SIGNATURE_SPO, // 111 (SPO)
+} SerdPatternSignature;
+
+static SerdPatternSignature
+serd_model_pattern_signature(const bool with_s,
+                             const bool with_p,
+                             const bool with_o)
+{
+  return (SerdPatternSignature)(((with_s ? 1U : 0U) << 2U) +
+                                ((with_p ? 1U : 0U) << 1U) +
+                                ((with_o ? 1U : 0U)));
+}
+
+static ZixBTreeCompareFunc
+serd_model_index_comparator(const SerdModel* const   model,
+                            const SerdStatementOrder order)
+{
+  return (order < SERD_ORDER_GSPO && !(model->flags & SERD_STORE_GRAPHS))
+           ? serd_triple_compare
+           : serd_quad_compare;
+}
+
+static ZixBTreeCompareFunc
+serd_model_pattern_comparator(const SerdModel* const   model,
+                              const SerdStatementOrder order)
+{
+  return (order < SERD_ORDER_GSPO && !(model->flags & SERD_STORE_GRAPHS))
+           ? serd_triple_compare_pattern
+           : serd_quad_compare_pattern;
+}
+
+SerdStatus
+serd_model_add_index(SerdModel* const model, const SerdStatementOrder order)
+{
+  assert(model);
+
+  if (model->indices[order]) {
+    return SERD_FAILURE;
+  }
+
+  const unsigned* const     ordering = orderings[order];
+  const ZixBTreeCompareFunc comparator =
+    serd_model_index_comparator(model, order);
+
+  model->indices[order] =
+    zix_btree_new((ZixAllocator*)model->allocator, comparator, ordering);
+
+  if (!model->indices[order]) {
+    return SERD_BAD_ALLOC;
+  }
+
+  // Insert statements from the default index
+  ZixStatus zst = ZIX_STATUS_SUCCESS;
+  if (order != model->default_order) {
+    ZixBTree* const default_index = model->indices[model->default_order];
+    for (ZixBTreeIter i = zix_btree_begin(default_index);
+         !zst && !zix_btree_iter_is_end(i);
+         zix_btree_iter_increment(&i)) {
+      zst = zix_btree_insert(model->indices[order], zix_btree_get(i));
+    }
+  }
+
+  return zst ? serd_model_drop_index(model, order) : SERD_SUCCESS;
+}
+
+SerdStatus
+serd_model_drop_index(SerdModel* const model, const SerdStatementOrder order)
+{
+  assert(model);
+
+  if (!model->indices[order]) {
+    return SERD_FAILURE;
+  }
+
+  if (order == model->default_order) {
+    return SERD_BAD_CALL;
+  }
+
+  zix_btree_free(model->indices[order], NULL, NULL);
+  model->indices[order] = NULL;
+  return SERD_SUCCESS;
+}
+
+static SerdModel*
+serd_model_new_with_allocator(SerdAllocator* const     allocator,
+                              SerdWorld* const         world,
+                              const SerdStatementOrder default_order,
+                              const SerdModelFlags     flags)
+{
+  assert(world);
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+  if (!nodes) {
+    return NULL;
+  }
+
+  SerdModel* model =
+    (SerdModel*)serd_acalloc(allocator, 1, sizeof(struct SerdModelImpl));
+
+  if (!model) {
+    serd_nodes_free(nodes);
+    return NULL;
+  }
+
+  model->allocator     = allocator;
+  model->world         = world;
+  model->nodes         = nodes;
+  model->default_order = default_order;
+  model->flags         = flags;
+
+  if (serd_model_add_index(model, default_order)) {
+    serd_nodes_free(nodes);
+    serd_wfree(world, model);
+    return NULL;
+  }
+
+  const ScanStrategy end_strategy = {SCAN_EVERYTHING, 0U, default_order};
+
+  model->end = serd_cursor_make(model,
+                                zix_btree_end(model->indices[default_order]),
+                                everything_pattern,
+                                end_strategy);
+
+  return model;
+}
+
+SerdModel*
+serd_model_new(SerdWorld* const         world,
+               const SerdStatementOrder default_order,
+               const SerdModelFlags     flags)
+{
+  return serd_model_new_with_allocator(
+    serd_world_allocator(world), world, default_order, flags);
+}
+
+static void
+log_bad_index(const SerdModel* const   model,
+              const char* const        description,
+              const SerdStatementOrder index_order,
+              const bool               s,
+              const bool               p,
+              const bool               o,
+              const bool               g)
+{
+  static const char* const order_strings[] = {
+    "S P O G",
+    "S O P G",
+    "O P S G",
+    "O S P G",
+    "P S O G",
+    "P O S G",
+    "G S P O",
+    "G S O P",
+    "G O P S",
+    "G O S P",
+    "G P S O",
+    "G P O S",
+  };
+
+  serd_logf(model->world,
+            SERD_LOG_LEVEL_WARNING,
+            "%s index (%s) for (%s %s %s%s) query",
+            description,
+            order_strings[index_order],
+            s ? "S" : "?",
+            p ? "P" : "?",
+            o ? "O" : "?",
+            (model->flags & SERD_STORE_GRAPHS) ? g ? " G" : " ?" : "");
+}
+
+static SerdCursor
+make_begin_cursor(const SerdModel* const model, const SerdStatementOrder order)
+{
+  if (!model->indices[order]) {
+    log_bad_index(model, "missing", order, false, false, false, false);
+    return model->end;
+  }
+
+  const ScanStrategy strategy = {SCAN_EVERYTHING, 0U, order};
+
+  return serd_cursor_make(model,
+                          zix_btree_begin(model->indices[order]),
+                          everything_pattern,
+                          strategy);
+}
+
+SerdModel*
+serd_model_copy(SerdAllocator* const allocator, const SerdModel* const model)
+{
+  assert(model);
+
+  SerdModel* copy = serd_model_new_with_allocator(
+    allocator, model->world, model->default_order, model->flags);
+
+  SerdCursor cursor = make_begin_cursor(model, model->default_order);
+  serd_model_insert_statements(copy, &cursor);
+
+  assert(serd_model_size(model) == serd_model_size(copy));
+  assert(serd_nodes_size(model->nodes) == serd_nodes_size(copy->nodes));
+  return copy;
+}
+
+bool
+serd_model_equals(const SerdModel* const a, const SerdModel* const b)
+{
+  if (!a && !b) {
+    return true;
+  }
+
+  if (!a || !b || serd_model_size(a) != serd_model_size(b)) {
+    return false;
+  }
+
+  SerdCursor ia = make_begin_cursor(a, a->default_order);
+  SerdCursor ib = make_begin_cursor(b, b->default_order);
+
+  while (!serd_cursor_is_end(&ia) && !serd_cursor_is_end(&ib)) {
+    if (!serd_statement_equals(serd_cursor_get(&ia), serd_cursor_get(&ib)) ||
+        serd_cursor_advance(&ia) > SERD_FAILURE ||
+        serd_cursor_advance(&ib) > SERD_FAILURE) {
+      return false;
+    }
+  }
+
+  return serd_cursor_is_end(&ia) && serd_cursor_is_end(&ib);
+}
+
+static void
+serd_model_drop_statement(SerdModel* const     model,
+                          SerdStatement* const statement)
+{
+  assert(statement);
+
+  for (unsigned i = 0U; i < 4; ++i) {
+    if (statement->nodes[i]) {
+      serd_nodes_deref(model->nodes, statement->nodes[i]);
+    }
+  }
+
+  if (statement->caret && serd_caret_document(statement->caret)) {
+    serd_nodes_deref(model->nodes, serd_caret_document(statement->caret));
+  }
+
+  serd_statement_free(model->allocator, statement);
+}
+
+typedef struct {
+  SerdAllocator* allocator;
+} DestroyContext;
+
+static void
+destroy_tree_statement(void* ptr, const void* user_data)
+{
+  const DestroyContext* const ctx = (const DestroyContext*)user_data;
+
+  serd_statement_free(ctx->allocator, (SerdStatement*)ptr);
+}
+
+void
+serd_model_free(SerdModel* const model)
+{
+  if (!model) {
+    return;
+  }
+
+  // Free all statements (which are owned by the default index)
+  ZixBTree* const      default_index = model->indices[model->default_order];
+  const DestroyContext ctx           = {model->allocator};
+  zix_btree_clear(default_index, destroy_tree_statement, &ctx);
+
+  // Free indices themselves
+  for (unsigned i = 0U; i < N_STATEMENT_ORDERS; ++i) {
+    zix_btree_free(model->indices[i], NULL, NULL);
+  }
+
+  serd_nodes_free(model->nodes);
+  serd_wfree(model->world, model);
+}
+
+SerdWorld*
+serd_model_world(SerdModel* const model)
+{
+  assert(model);
+  return model->world;
+}
+
+const SerdNodes*
+serd_model_nodes(const SerdModel* const model)
+{
+  assert(model);
+  return model->nodes;
+}
+
+SerdStatementOrder
+serd_model_default_order(const SerdModel* const model)
+{
+  assert(model);
+  return model->default_order;
+}
+
+SerdModelFlags
+serd_model_flags(const SerdModel* const model)
+{
+  assert(model);
+  return model->flags;
+}
+
+size_t
+serd_model_size(const SerdModel* const model)
+{
+  assert(model);
+  return zix_btree_size(model->indices[model->default_order]);
+}
+
+bool
+serd_model_empty(const SerdModel* const model)
+{
+  assert(model);
+  return serd_model_size(model) == 0;
+}
+
+SerdCursor*
+serd_model_begin_ordered(SerdAllocator* const     allocator,
+                         const SerdModel* const   model,
+                         const SerdStatementOrder order)
+{
+  assert(model);
+
+  const SerdCursor cursor = make_begin_cursor(model, order);
+
+  return serd_cursor_copy(allocator, &cursor);
+}
+
+SerdCursor*
+serd_model_begin(SerdAllocator* const allocator, const SerdModel* const model)
+{
+  assert(model);
+  return serd_model_begin_ordered(allocator, model, model->default_order);
+}
+
+const SerdCursor*
+serd_model_end(const SerdModel* const model)
+{
+  assert(model);
+  return &model->end;
+}
+
+static SerdStatementOrder
+simple_order(const SerdStatementOrder order)
+{
+  return order < SERD_ORDER_GSPO ? order : (SerdStatementOrder)(order - 6U);
+}
+
+/// Return the best index scanning strategy for a pattern with given nodes
+static ScanStrategy
+serd_model_strategy(const SerdModel* const model,
+                    const bool             with_s,
+                    const bool             with_p,
+                    const bool             with_o,
+                    const bool             with_g)
+{
+#define N_STRATEGY_TIERS 4U
+
+  const SerdStatementOrder default_order = simple_order(model->default_order);
+  const ScanStrategy       none          = {SCAN_EVERYTHING, 0U, default_order};
+
+  const ScanStrategy strategies[N_STRATEGY_TIERS][8] = {
+    // Preferred perfect strategies: SPO, SOP, OPS, PSO
+    {
+      none,
+      {SCAN_RANGE, 1U, SERD_ORDER_OPS}, // ??O
+      {SCAN_RANGE, 1U, SERD_ORDER_PSO}, // ?P?
+      {SCAN_RANGE, 2U, SERD_ORDER_OPS}, // ?PO
+      {SCAN_RANGE, 1U, SERD_ORDER_SPO}, // S??
+      {SCAN_RANGE, 2U, SERD_ORDER_SOP}, // S?O
+      {SCAN_RANGE, 2U, SERD_ORDER_SPO}, // SP?
+      {SCAN_RANGE, 3U, default_order}   // SPO
+    },
+
+    // Alternate perfect strategies: adds OSP and POS
+    {
+      none,                             // ???
+      {SCAN_RANGE, 1U, SERD_ORDER_OSP}, // ??O
+      {SCAN_RANGE, 1U, SERD_ORDER_POS}, // ?P?
+      {SCAN_RANGE, 2U, SERD_ORDER_POS}, // ?PO
+      {SCAN_RANGE, 1U, SERD_ORDER_SOP}, // S??
+      {SCAN_RANGE, 2U, SERD_ORDER_OSP}, // S?O
+      {SCAN_RANGE, 2U, SERD_ORDER_PSO}, // SP?
+      none                              // SPO
+    },
+
+    // Preferred partial prefix strategies
+    {
+      none,                               // ???
+      none,                               // ??O
+      none,                               // ?P?
+      {FILTER_RANGE, 1U, SERD_ORDER_PSO}, // ?PO
+      none,                               // S??
+      {FILTER_RANGE, 1U, SERD_ORDER_SPO}, // S?O
+      {FILTER_RANGE, 1U, SERD_ORDER_SOP}, // SP?
+      none                                // SPO
+    },
+
+    // Alternate partial prefix strategies
+    {
+      none,                               // ???
+      none,                               // ??O
+      none,                               // ?P?
+      {FILTER_RANGE, 1U, SERD_ORDER_OSP}, // ?PO
+      none,                               // S??
+      {FILTER_RANGE, 1U, SERD_ORDER_OPS}, // S?O
+      {FILTER_RANGE, 1U, SERD_ORDER_POS}, // SP?
+      none                                // SPO
+    },
+  };
+
+  // Construct a 3-bit signature for this triple pattern
+  const SerdPatternSignature sig =
+    serd_model_pattern_signature(with_s, with_p, with_o);
+  if (!sig && !with_g) {
+    return none;
+  }
+
+  // Try to find a strategy we can support, from most to least preferred
+  for (unsigned t = 0U; t < N_STRATEGY_TIERS; ++t) {
+    ScanStrategy             strategy     = strategies[t][sig];
+    const SerdStatementOrder triple_order = strategy.order;
+
+    assert(strategy.order < SERD_ORDER_GSPO);
+
+    if (strategy.n_prefix > 0) {
+      if (with_g) {
+        const SerdStatementOrder quad_order =
+          (SerdStatementOrder)(triple_order + 6U);
+
+        if (model->indices[quad_order]) {
+          strategy.order = quad_order;
+          ++strategy.n_prefix;
+          return strategy;
+        }
+      }
+
+      if (model->indices[triple_order]) {
+        return strategy;
+      }
+    }
+  }
+
+  // Indices don't help with the triple, try to at least stay in the graph
+  if (with_g) {
+    for (unsigned i = SERD_ORDER_GSPO; i <= SERD_ORDER_GPOS; ++i) {
+      if (model->indices[i]) {
+        const ScanMode     mode     = sig == 0x000 ? SCAN_RANGE : FILTER_RANGE;
+        const ScanStrategy strategy = {mode, 1U, (SerdStatementOrder)i};
+
+        return strategy;
+      }
+    }
+  }
+
+  // All is lost, regress to linear search
+  const ScanStrategy linear = {FILTER_EVERYTHING, 0U, model->default_order};
+  return linear;
+}
+
+static SerdCursor
+serd_model_search(const SerdModel* const model,
+                  const SerdNode* const  s,
+                  const SerdNode* const  p,
+                  const SerdNode* const  o,
+                  const SerdNode* const  g)
+{
+  // Build a pattern of interned nodes
+  const SerdNode* pattern[4] = {serd_nodes_existing(model->nodes, s),
+                                serd_nodes_existing(model->nodes, p),
+                                serd_nodes_existing(model->nodes, o),
+                                serd_nodes_existing(model->nodes, g)};
+
+  // If some node isn't in the model at all, no need to search for statements
+  const int n_given = !!s + !!p + !!o + !!g;
+  if (n_given != (!!pattern[0] + !!pattern[1] + !!pattern[2] + !!pattern[3])) {
+    return model->end;
+  }
+
+  // Determine the best available search strategy
+  const ScanStrategy       strategy = serd_model_strategy(model, s, p, o, g);
+  const SerdStatementOrder order    = strategy.order;
+  ZixBTree* const          index    = model->indices[order];
+
+  // Issue any performance warnings, and return early for degenerate cases
+  switch (strategy.mode) {
+  case SCAN_EVERYTHING:
+    return make_begin_cursor(model, order);
+  case SCAN_RANGE:
+    break;
+  case FILTER_EVERYTHING:
+    log_bad_index(model, "using effectively linear", order, s, p, o, g);
+    return serd_cursor_make(model, zix_btree_begin(index), pattern, strategy);
+  case FILTER_RANGE:
+    log_bad_index(model, "filtering partial", order, s, p, o, g);
+    break;
+  }
+
+  // Find the first statement matching the pattern in the index
+  ZixBTreeIter iter = zix_btree_end_iter;
+  zix_btree_lower_bound(index,
+                        serd_model_pattern_comparator(model, order),
+                        orderings[order],
+                        pattern,
+                        &iter);
+
+  return (!zix_btree_iter_is_end(iter) &&
+          serd_iter_in_range(iter, pattern, strategy))
+           ? serd_cursor_make(model, iter, pattern, strategy)
+           : model->end;
+}
+
+SerdCursor*
+serd_model_find(SerdAllocator* const   allocator,
+                const SerdModel* const model,
+                const SerdNode* const  s,
+                const SerdNode* const  p,
+                const SerdNode* const  o,
+                const SerdNode* const  g)
+{
+  assert(model);
+
+  const SerdCursor cursor = serd_model_search(model, s, p, o, g);
+
+  return zix_btree_iter_is_end(cursor.iter)
+           ? NULL
+           : serd_cursor_copy(allocator, &cursor);
+}
+
+const SerdNode*
+serd_model_get(const SerdModel* const model,
+               const SerdNode* const  s,
+               const SerdNode* const  p,
+               const SerdNode* const  o,
+               const SerdNode* const  g)
+{
+  assert(model);
+
+  const SerdStatement* const statement =
+    serd_model_get_statement(model, s, p, o, g);
+
+  return !statement ? NULL
+         : !s       ? serd_statement_subject(statement)
+         : !p       ? serd_statement_predicate(statement)
+         : !o       ? serd_statement_object(statement)
+         : !g       ? serd_statement_graph(statement)
+                    : NULL;
+}
+
+const SerdStatement*
+serd_model_get_statement(const SerdModel* const model,
+                         const SerdNode* const  s,
+                         const SerdNode* const  p,
+                         const SerdNode* const  o,
+                         const SerdNode* const  g)
+{
+  assert(model);
+
+  if ((bool)s + (bool)p + (bool)o != 2 &&
+      (bool)s + (bool)p + (bool)o + (bool)g != 3) {
+    return NULL;
+  }
+
+  const SerdCursor i = serd_model_search(model, s, p, o, g);
+
+  return serd_cursor_get(&i);
+}
+
+size_t
+serd_model_count(const SerdModel* const model,
+                 const SerdNode* const  s,
+                 const SerdNode* const  p,
+                 const SerdNode* const  o,
+                 const SerdNode* const  g)
+{
+  assert(model);
+
+  SerdCursor i     = serd_model_search(model, s, p, o, g);
+  size_t     count = 0;
+
+  for (; !serd_cursor_is_end(&i); serd_cursor_advance(&i)) {
+    ++count;
+  }
+
+  return count;
+}
+
+bool
+serd_model_ask(const SerdModel* const model,
+               const SerdNode* const  s,
+               const SerdNode* const  p,
+               const SerdNode* const  o,
+               const SerdNode* const  g)
+{
+  assert(model);
+
+  const SerdCursor c = serd_model_search(model, s, p, o, g);
+
+  return !serd_cursor_is_end(&c);
+}
+
+static SerdCaret*
+serd_model_intern_caret(SerdModel* const model, const SerdCaret* const caret)
+{
+  if (!caret) {
+    return NULL;
+  }
+
+  SerdCaret* const copy =
+    (SerdCaret*)serd_acalloc(model->allocator, 1, sizeof(SerdCaret));
+
+  if (copy) {
+    copy->document = serd_nodes_intern(model->nodes, caret->document);
+    copy->line     = caret->line;
+    copy->col      = caret->col;
+  }
+
+  return copy;
+}
+
+SerdStatus
+serd_model_add_with_caret(SerdModel* const       model,
+                          const SerdNode* const  s,
+                          const SerdNode* const  p,
+                          const SerdNode* const  o,
+                          const SerdNode* const  g,
+                          const SerdCaret* const caret)
+{
+  assert(model);
+
+  SerdStatement* const statement =
+    serd_statement_new(model->allocator, s, p, o, g, NULL);
+
+  if (!statement) {
+    return SERD_BAD_ALLOC;
+  }
+
+  statement->caret = serd_model_intern_caret(model, caret);
+
+  bool added = false;
+  for (unsigned i = 0U; i < N_STATEMENT_ORDERS; ++i) {
+    if (model->indices[i]) {
+      if (!zix_btree_insert(model->indices[i], statement)) {
+        added = true;
+      } else if ((SerdStatementOrder)i == model->default_order) {
+        break; // Statement already indexed
+      }
+    }
+  }
+
+  ++model->version;
+  if (added) {
+    return SERD_SUCCESS;
+  }
+
+  serd_model_drop_statement(model, statement);
+  return SERD_FAILURE;
+}
+
+SerdStatus
+serd_model_add(SerdModel* const      model,
+               const SerdNode* const s,
+               const SerdNode* const p,
+               const SerdNode* const o,
+               const SerdNode* const g)
+{
+  return serd_model_add_with_caret(model,
+                                   serd_nodes_intern(model->nodes, s),
+                                   serd_nodes_intern(model->nodes, p),
+                                   serd_nodes_intern(model->nodes, o),
+                                   serd_nodes_intern(model->nodes, g),
+                                   NULL);
+}
+
+SerdStatus
+serd_model_insert(SerdModel* const model, const SerdStatement* const statement)
+{
+  SerdNodes* const nodes = model->nodes;
+
+  return serd_model_add_with_caret(
+    model,
+    serd_nodes_intern(nodes, serd_statement_subject(statement)),
+    serd_nodes_intern(nodes, serd_statement_predicate(statement)),
+    serd_nodes_intern(nodes, serd_statement_object(statement)),
+    serd_nodes_intern(nodes, serd_statement_graph(statement)),
+    serd_statement_caret(statement));
+}
+
+SerdStatus
+serd_model_insert_statements(SerdModel* const model, SerdCursor* const range)
+{
+  const SerdStatement* statement = serd_cursor_get(range);
+  SerdStatus           st        = SERD_SUCCESS;
+
+  while (!st && statement) {
+    if (!(st = serd_model_insert(model, statement))) {
+      st = serd_cursor_advance(range);
+    }
+
+    statement = serd_cursor_get(range);
+  }
+
+  return st;
+}
+
+SerdStatus
+serd_model_erase(SerdModel* const model, SerdCursor* const cursor)
+{
+  assert(model);
+  assert(cursor);
+
+  const SerdStatement* statement = serd_cursor_get(cursor);
+  SerdStatement*       removed   = NULL;
+  ZixStatus            zst       = ZIX_STATUS_SUCCESS;
+
+  if (!statement) {
+    return SERD_FAILURE;
+  }
+
+  // Erase from the index associated with this cursor
+  zst = zix_btree_remove(model->indices[cursor->strategy.order],
+                         statement,
+                         (void**)&removed,
+                         &cursor->iter);
+
+  // No error should be possible with a valid cursor
+  assert(!zst);
+  assert(removed);
+  assert(removed == statement);
+
+  for (unsigned i = SERD_ORDER_SPO; i <= SERD_ORDER_GPOS; ++i) {
+    ZixBTree* index = model->indices[i];
+
+    if (index && i != (unsigned)cursor->strategy.order) {
+      SerdStatement* ignored = NULL;
+      ZixBTreeIter   next    = zix_btree_end_iter;
+      zst = zix_btree_remove(index, statement, (void**)&ignored, &next);
+
+      assert(zst == ZIX_STATUS_SUCCESS || zst == ZIX_STATUS_NOT_FOUND);
+      assert(!ignored || ignored == removed);
+    }
+  }
+  serd_cursor_scan_next(cursor);
+
+  serd_model_drop_statement(model, removed);
+  cursor->version = ++model->version;
+
+  (void)zst;
+  return SERD_SUCCESS;
+}
+
+SerdStatus
+serd_model_erase_statements(SerdModel* const model, SerdCursor* const range)
+{
+  assert(model);
+  assert(range);
+
+  SerdStatus st = SERD_SUCCESS;
+
+  while (!st && !serd_cursor_is_end(range)) {
+    st = serd_model_erase(model, range);
+  }
+
+  return st;
+}
+
+SerdStatus
+serd_model_clear(SerdModel* const model)
+{
+  assert(model);
+
+  SerdStatus st = SERD_SUCCESS;
+  SerdCursor i  = make_begin_cursor(model, model->default_order);
+
+  while (!st && !serd_cursor_is_end(&i)) {
+    st = serd_model_erase(model, &i);
+  }
+
+  return st;
+}
diff --git a/src/model.h b/src/model.h
new file mode 100644
index 00000000..a67ba087
--- /dev/null
+++ b/src/model.h
@@ -0,0 +1,29 @@
+// Copyright 2011-2020 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef SERD_SRC_MODEL_H
+#define SERD_SRC_MODEL_H
+
+#include "cursor.h"
+
+#include "serd/cursor.h"
+#include "serd/memory.h"
+#include "serd/model.h"
+#include "serd/nodes.h"
+#include "serd/world.h"
+#include "zix/btree.h"
+
+#include <stddef.h>
+
+struct SerdModelImpl {
+  SerdAllocator*     allocator;     ///< Allocator for everything in this model
+  SerdWorld*         world;         ///< World this model is a part of
+  SerdNodes*         nodes;         ///< Interned nodes in this model
+  ZixBTree*          indices[12];   ///< Trees of SerdStatement pointers
+  SerdCursor         end;           ///< End cursor (always the same)
+  size_t             version;       ///< Version incremented on every change
+  SerdStatementOrder default_order; ///< Order for main statement-owning index
+  SerdModelFlags     flags;         ///< Active indices and features
+};
+
+#endif // SERD_SRC_MODEL_H
diff --git a/src/reader.c b/src/reader.c
index b7a64ce4..5ce81962 100644
--- a/src/reader.c
+++ b/src/reader.c
@@ -89,7 +89,7 @@ tolerate_status(const SerdReader* const reader, const SerdStatus status)
 
   if (status == SERD_BAD_STREAM || status == SERD_BAD_STACK ||
       status == SERD_BAD_WRITE || status == SERD_NO_DATA ||
-      status == SERD_BAD_CALL) {
+      status == SERD_BAD_CALL || status == SERD_BAD_CURSOR) {
     return false;
   }
 
diff --git a/src/string.c b/src/string.c
index b8227100..ac964705 100644
--- a/src/string.c
+++ b/src/string.c
@@ -64,6 +64,10 @@ serd_strerror(const SerdStatus status)
     return "Invalid literal";
   case SERD_BAD_PATTERN:
     return "Invalid statement pattern";
+  case SERD_BAD_CURSOR:
+    return "Invalid cursor";
+  case SERD_BAD_INDEX:
+    return "No suitable model index available";
   }
 
   return "Unknown error";