lsup_rdf/src/graph.c

#include "lsup/graph.h"

/*
 * Data types.
 */

struct graph_t {
    LSUP_Term               *uri;           ///< Graph "name" (URI).
    LSUP_Store *            store;          ///< Store handle.
    LSUP_NSMap *            nsm;            /**< Namespace map.
                                              *
                                              * NOTE: This is
                                              * NULL for permanent stores.
                                              */
};

struct graph_iter_t {
    const LSUP_Graph *      graph;          ///< Parent graph.
    void *                  data;           ///< Iterator state.
    size_t                  ct;             ///< Total lookup matches.
    LSUP_BufferTriple *     sspo;           ///< Buffer triple for temp values.
};


/*
 * Static prototypes.
 */

inline static LSUP_rc
graph_iter_next_buffer (LSUP_GraphIterator *it);


#define ENTRY(a, b) (be) == (LSUP_STORE_##a) ||
static inline bool
check_backend (LSUP_StoreType be)
{ return (BACKEND_TBL false); }
#undef ENTRY


/*
 * Graph API.
 */

LSUP_Graph *
LSUP_graph_new (LSUP_Store *store, const char *uri_str, LSUP_NSMap *nsm)
{
    // Create a HTable graph by default.
    LSUP_Graph *gr;
    MALLOC_GUARD (gr, NULL);

    gr->store = (store) ? store : LSUP_store_new (LSUP_STORE_HTABLE, NULL, 0);

    if (gr->store->sif->nsm_get_fn)
        gr->nsm = gr->store->sif->nsm_get_fn (gr->store->data);
    else gr->nsm = nsm ? nsm : LSUP_default_nsm;

    gr->uri =
        uri_str? LSUP_iriref_new (uri_str, gr->nsm) :
        LSUP_iriref_new (NULL, NULL);

    LOG_DEBUG("Graph created.");
    return gr;
}


LSUP_Graph *
LSUP_graph_get_txn (
        void *txn, LSUP_Store *store, const LSUP_Term *uri, size_t *ct)
{
    LSUP_Buffer *sc = LSUP_term_serialize (uri);
    void *it = store->sif->lookup_fn (
            store->data, NULL, NULL, NULL, sc, NULL, NULL);

    LSUP_Graph *gr = LSUP_graph_new (NULL, uri->data, NULL);
    LSUP_BufferTriple *sspo = BTRP_DUMMY;
    void *add_it = LSUP_graph_add_init_txn (txn, gr);

    size_t _ct = 0;
    while (store->sif->lu_next_fn (it, sspo, NULL) == LSUP_OK) {
        // This is deserializing a buffer triple that will be re-serialized by
        // LSUP_graph_add_iter. But it's necessary to relativize URIs.
        LSUP_Triple *spo = LSUP_triple_new_from_btriple (sspo);
        LSUP_graph_add_iter (add_it, spo);
        LSUP_triple_free (spo);
        _ct++;
    }
    LSUP_graph_add_done (add_it);
    store->sif->lu_free_fn(it);
    LSUP_buffer_free (sc);
    LSUP_btriple_free (sspo);

    // Do not create a new graph if no results were found.
    if (_ct == 0) {
        LSUP_graph_free (gr);
        gr = NULL;
    }
    if (ct) *ct = _ct;

    return gr;
}


LSUP_rc
LSUP_graph_bool_op_txn (
        void *txn, const LSUP_bool_op op,
        const LSUP_Graph *gr1, const LSUP_Graph *gr2, LSUP_Graph *res)
{
    LSUP_rc rc = LSUP_NOACTION;
    if (UNLIKELY (
            op != LSUP_BOOL_UNION
            && op != LSUP_BOOL_SUBTRACTION
            && op != LSUP_BOOL_INTERSECTION
            && op != LSUP_BOOL_XOR)) {
        log_error ("Invalid boolean operation: %d.", op);

        return LSUP_VALUE_ERR;
    }

    /* BEGIN union block. */

    if (op == LSUP_BOOL_UNION) {
        // No need to use a transaction here: the graph is freed on failure.
        rc = LSUP_graph_copy_contents (gr1, res, NULL, NULL, NULL);
        PCHECK (rc, fail);
        rc = LSUP_graph_copy_contents (gr2, res, NULL, NULL, NULL);
        PCHECK (rc, fail);

        return LSUP_OK;
    }

    /* END union block. */

    LSUP_Buffer
        *res_sc = LSUP_term_serialize (res->uri),
        *gr1_sc = LSUP_term_serialize (gr1->uri),
        *gr2_sc = LSUP_term_serialize (gr2->uri);
    void *lu1_it, *lu2_it, *add_it;
    LSUP_BufferTriple *sspo = BTRP_DUMMY;
    size_t ct;

    // Handle transactions for graphs possibly in different storage back ends.
    void
        *lu1_txn = NULL,
        *lu2_txn = NULL,
        *res_txn = NULL;
    // Whether gr1 or gr2 txn will be open independently from res txn.
    bool
        open_txn1 = false,
        open_txn2 = false;

    add_it = res->store->sif->add_init_fn (res->store->data, res_sc, txn);

    if (res->store->sif->features & LSUP_STORE_TXN)
        res_txn = res->store->sif->iter_txn_fn (add_it);

    /* If either source graph is in the same store as the destination and has
     * an open transaction, reuse that transaction. A new reader cannot be
     * opened in LMDB while a writer is open already.
     */
    // Handle gr1 transaction.
    if (gr1->store->sif->features & LSUP_STORE_TXN) {
        if (gr1->store == res->store) lu1_txn = res_txn;
        // FIXME: MDB_RDONLY is implementation-specific and doesn't belong here.
        else {
            CHECK (gr1->store->sif->txn_begin_fn (
                gr1->store->data, MDB_RDONLY, &lu1_txn), fail);
            open_txn1 = true;
        }
    }

    // Handle gr2 transaction.
    if (gr2->store->sif->features & LSUP_STORE_TXN) {
        if (gr2->store == res->store) lu2_txn = res_txn;
        else if (gr2->store == gr1->store) lu2_txn = lu1_txn;
        // FIXME: see above.
        else {
            CHECK (gr2->store->sif->txn_begin_fn (
                gr2->store->data, MDB_RDONLY, &lu2_txn), fail);
            open_txn2 = true;
        }
    }
    LOG_TRACE (
            "lu1_txn: %p ; lu2_txn: %p ; res_txn: %p",
            lu1_txn, lu2_txn, res_txn);

    /* BEGIN XOR block. */

    if (op == LSUP_BOOL_XOR) {
        // Add triples from gr2 if not found in gr1.
        lu2_it = gr2->store->sif->lookup_fn (
                gr2->store->data, NULL, NULL, NULL, gr2_sc, lu2_txn, NULL);
        while (gr2->store->sif->lu_next_fn (lu2_it, sspo, NULL) == LSUP_OK) {
            lu1_it = gr1->store->sif->lookup_fn (
                    gr1->store->data, sspo->s, sspo->p, sspo->o, gr1_sc,
                    lu1_txn, &ct);
            if (ct == 0) {
                res->store->sif->add_iter_fn (add_it, sspo);
                rc = LSUP_OK;
            }
            gr1->store->sif->lu_free_fn (lu1_it);
        }
        gr2->store->sif->lu_free_fn (lu2_it);
    }

    /* BEGIN subtraction and intersection block. */

    lu1_it = gr1->store->sif->lookup_fn (
            gr1->store->data, NULL, NULL, NULL, gr1_sc, lu1_txn, NULL);
    while (gr1->store->sif->lu_next_fn (lu1_it, sspo, NULL) == LSUP_OK) {
        lu2_it = gr2->store->sif->lookup_fn (
                gr2->store->data, sspo->s, sspo->p, sspo->o, gr2_sc,
                lu2_txn, &ct);
        if (UNLIKELY (!lu2_it)) {
            rc = LSUP_DB_ERR;
            gr1->store->sif->lu_free_fn (lu1_it);
            goto fail;
        }
        // For XOR and subtraction, add if not found.
        // For intersection, add if found.
        if ((ct == 0) ^ (op == LSUP_BOOL_INTERSECTION)) {
            res->store->sif->add_iter_fn (add_it, sspo);
            rc = LSUP_OK;
        }
        gr2->store->sif->lu_free_fn (lu2_it);
    }
    gr1->store->sif->lu_free_fn (lu1_it);

    if (open_txn1) gr1->store->sif->txn_commit_fn (lu1_txn);
    if (open_txn2) gr2->store->sif->txn_commit_fn (lu2_txn);

    res->store->sif->add_done_fn (add_it);
    LSUP_btriple_free (sspo);
    LSUP_buffer_free (res_sc);
    LSUP_buffer_free (gr1_sc);
    LSUP_buffer_free (gr2_sc);

    /* END subtraction, intersection, XOR block. */

    return rc;

fail:
    if (lu1_txn) gr1->store->sif->txn_abort_fn (lu1_txn);
    if (lu2_txn) gr2->store->sif->txn_abort_fn (lu2_txn);
    LSUP_graph_free (res);
    return rc;
}


void
LSUP_graph_free (LSUP_Graph *gr)
{
    if (UNLIKELY (!gr)) return;

    LSUP_term_free (gr->uri);
    free (gr->store->id);
    // If the store has the nsm_get_fn, it's been uniquely created for this
    // graph and it's safe to free.
    if (gr->store->sif->nsm_get_fn) LSUP_nsmap_free (gr->nsm);
    // If the store is a HTable, it means it has been created with the graph
    // and must go with it.
    if (gr->store->type == LSUP_STORE_HTABLE) {
        gr->store->sif->free_fn (gr->store->data);
        free (gr->store);
    }

    free (gr);
}


const LSUP_Term *
LSUP_graph_uri (const LSUP_Graph *gr) { return gr->uri; }


LSUP_Store *
LSUP_graph_store (const LSUP_Graph *gr)
{ return gr->store; }


LSUP_rc
LSUP_graph_set_uri (LSUP_Graph *gr, const char *uri_str)
{
    LSUP_rc rc = LSUP_OK;
    LSUP_Buffer *old_sc = NULL, *new_sc = NULL;

    LSUP_Term *uri = LSUP_iriref_new (uri_str, gr->nsm);
    if (UNLIKELY (!uri)) {
        rc = LSUP_MEM_ERR;
        goto finally;
    }

    // Update context for triples in the graph.
    if (gr->store->sif->features & LSUP_STORE_CTX) {
        old_sc = LSUP_term_serialize (gr->uri);
        new_sc = LSUP_term_serialize (uri);
        if (UNLIKELY (!old_sc || !new_sc)) {
            rc = LSUP_MEM_ERR;
            goto finally;
        }

        PCHECK (rc = gr->store->sif->update_ctx_fn (
                    gr->store->data, old_sc, new_sc, NULL), finally);

        // Overall success even if rc of underlying fn was LSUP_NOACTION.
        if (rc == LSUP_NOACTION) rc = LSUP_OK;
    }

    LSUP_term_free (gr->uri);
    gr->uri = uri;

finally:
    if (old_sc) LSUP_buffer_free (old_sc);
    if (new_sc) LSUP_buffer_free (new_sc);

    return rc;
}


LSUP_NSMap *
LSUP_graph_namespace (const LSUP_Graph *gr)
{
    // If nsm_get_fn is not defined, the store has no own NS map.
    if (!gr->store->sif->nsm_get_fn) return gr->nsm;

    return gr->store->sif->nsm_get_fn (gr->store->data);
}


void
LSUP_graph_set_namespace (LSUP_Graph *gr, LSUP_NSMap *nsm)
{
    if (!gr->store->sif->nsm_get_fn) gr->nsm = nsm;
    else log_warn ("Graph back end has a stored NS map.");
}


size_t
LSUP_graph_size (const LSUP_Graph *gr)
{
    size_t ct = 0;
    LSUP_Buffer *sc = LSUP_term_serialize (gr->uri);
    void *it = gr->store->sif->lookup_fn (
        gr->store->data, NULL, NULL, NULL, sc, NULL, &ct);
    gr->store->sif->lu_free_fn (it);

    LSUP_buffer_free (sc);

    return ct;
}


bool
LSUP_graph_equals (const LSUP_Graph *gr1, const LSUP_Graph *gr2)
{
    LSUP_Graph *res = LSUP_graph_new (NULL, NULL, NULL);
    LSUP_graph_bool_op (LSUP_BOOL_XOR, gr1, gr2, res);
    bool ret = (LSUP_graph_size (res) == 0);

    LSUP_graph_free (res);

    return ret;
}


LSUP_GraphIterator *
LSUP_graph_add_init_txn (void *txn, LSUP_Graph *gr)
{
    LSUP_GraphIterator *it;
    CALLOC_GUARD (it, NULL);

    LSUP_Buffer *sc = LSUP_term_serialize (gr->uri);

    it->data = gr->store->sif->add_init_fn (gr->store->data, sc, txn);
    LSUP_buffer_free (sc);

    it->graph = gr;

    return it;
}


LSUP_rc
LSUP_graph_add_iter (LSUP_GraphIterator *it, const LSUP_Triple *spo)
{
    LOG_TRACE(
            "Adding triple {%s, %s, %s} to %s",
            spo->s->data, spo->p->data, spo->o->data,
            LSUP_graph_uri(it->graph)->data);

    // Make relative s and o.
    LSUP_Term *rel_s, *rel_o;
    if (LSUP_IS_IRI (spo->s))
        rel_s = LSUP_iriref_relative (it->graph->uri, spo->s);
    else rel_s = spo->s;
    if (LSUP_IS_IRI (spo->o))
        rel_o = LSUP_iriref_relative (it->graph->uri, spo->o);
    else rel_o = spo->o;

    LSUP_Triple *rel_spo = LSUP_triple_new (rel_s, spo->p, rel_o);
    LOG_TRACE (
            "Adding relative triple: {%s, %s, %s}",
            rel_s->data, spo->p->data, rel_o->data);

    // Serialize relative triple.
    LSUP_BufferTriple *sspo = LSUP_triple_serialize (rel_spo);
    if (UNLIKELY (!sspo)) return LSUP_MEM_ERR;

    // Selectively free triple members and structure.
    if (rel_s != spo->s) LSUP_term_free (rel_s);
    if (rel_o != spo->o) LSUP_term_free (rel_o);
    free (rel_spo);

    const LSUP_StoreInt *sif = it->graph->store->sif;

    LSUP_rc rc;

    PCHECK (rc = sif->add_iter_fn (it->data, sspo), finally);

    // Store datatype term permanently.
    if (rc == LSUP_OK && sif->add_term_fn) {
        for (int i = 0; i < 3; i++) {
            LSUP_Term *term = LSUP_triple_pos (spo, i);
            if (term->type == LSUP_TERM_LITERAL) {
                LSUP_Buffer *ser_dtype = LSUP_term_serialize (term->datatype);
                void *txn =
                        sif->features & LSUP_STORE_TXN ?
                        sif->iter_txn_fn (it->data) : NULL;
                LSUP_rc term_rc = sif->add_term_fn (
                        it->graph->store->data, ser_dtype, txn);
                PCHECK (term_rc, finally);
                LSUP_buffer_free (ser_dtype);
            }
        }
    }


finally:
    LSUP_btriple_free (sspo);

    return rc;
}


void
LSUP_graph_add_done (LSUP_GraphIterator *it)
{
    it->graph->store->sif->add_done_fn (it->data);
    free (it);
}


LSUP_rc
LSUP_graph_add_txn (
        void *txn, LSUP_Graph *gr, LSUP_Triple *const *trp, size_t *ct)
{
    LSUP_rc rc = LSUP_NOACTION;

    // Initialize iterator.
    LSUP_GraphIterator *it = LSUP_graph_add_init_txn (txn, gr);

    if (ct) *ct = 0;
    // Serialize and insert RDF triples.
    for (size_t i = 0; trp[i] != NULL; i++) {
        LOG_TRACE("Inserting triple #%lu", i);

        LSUP_rc db_rc = LSUP_graph_add_iter (it, trp[i]);

        if (db_rc == LSUP_OK) {
            rc = LSUP_OK;
            if (ct) (*ct)++;
            // A duplicate will return LSUP_NOACTION and not increment ct.
        }
        if (UNLIKELY (db_rc < 0)) {
            rc = db_rc;
            goto finally;
        }
    }

finally:
    LSUP_graph_add_done (it);

    return rc;
}


LSUP_rc
LSUP_graph_remove_txn (
        void *txn, LSUP_Graph *gr,
        const LSUP_Term *s, const LSUP_Term *p, const LSUP_Term *o,
        size_t *ct)
{
    LSUP_Buffer
        *ss = LSUP_term_serialize (s),
        *sp = LSUP_term_serialize (p),
        *so = LSUP_term_serialize (o),
        *sc = LSUP_term_serialize (gr->uri);

    LSUP_rc rc = gr->store->sif->remove_fn (
            gr->store->data, ss, sp, so, sc, txn, ct);

    LSUP_buffer_free (ss);
    LSUP_buffer_free (sp);
    LSUP_buffer_free (so);
    LSUP_buffer_free (sc);

    return rc;
}


LSUP_rc
LSUP_graph_copy_contents_txn (
        void *txn, const LSUP_Graph *src, LSUP_Graph *dest,
        const LSUP_Term *s, const LSUP_Term *p, const LSUP_Term *o)
{
    LSUP_rc rc = LSUP_NOACTION;

    LSUP_GraphIterator *it = LSUP_graph_lookup_txn (txn, src, s, p, o, NULL);

    LSUP_Triple *spo = NULL;
    LSUP_GraphIterator *add_it = LSUP_graph_add_init_txn (txn, dest);
    while (LSUP_graph_iter_next (it, &spo) != LSUP_END) {
        LSUP_rc add_rc = LSUP_graph_add_iter (add_it, spo);
        LSUP_triple_free (spo);
        if (LIKELY (add_rc == LSUP_OK)) rc = LSUP_OK;
        else if (add_rc < 0) {
            rc = add_rc;
            break;
        }
    }

    LSUP_graph_add_done (add_it);
    LSUP_graph_iter_free (it);

    return rc;
}


LSUP_GraphIterator *
LSUP_graph_lookup_txn (
        void *txn, const LSUP_Graph *gr,
        const LSUP_Term *s, const LSUP_Term *p, const LSUP_Term *o,
        size_t *ct)
{
    LSUP_GraphIterator *it;
    MALLOC_GUARD (it, NULL);

    // Make relative s and o.
    LSUP_Term *rel_s, *rel_o;
    if (s && LSUP_IS_IRI (s)) {
        rel_s = LSUP_iriref_relative (gr->uri, s);
        LOG_DEBUG ("Relative S lookup: %s", rel_s->data);
    } else rel_s = (LSUP_Term *)s;
    if (o && LSUP_IS_IRI (o)) {
        rel_o = LSUP_iriref_relative (gr->uri, o);
        LOG_DEBUG ("Relative O lookup: %s", rel_o->data);
    } else rel_o = (LSUP_Term *)o;

    LSUP_Buffer
        *ss = LSUP_term_serialize (rel_s),
        *sp = LSUP_term_serialize (p),
        *so = LSUP_term_serialize (rel_o),
        *sc = LSUP_term_serialize (gr->uri);

    // Selectively free triple members and structure.
    if (rel_s != s) LSUP_term_free (rel_s);
    if (rel_o != o) LSUP_term_free (rel_o);

    it->data = gr->store->sif->lookup_fn (
            gr->store->data, ss, sp, so, sc, txn, ct);

    LSUP_buffer_free (ss);
    LSUP_buffer_free (sp);
    LSUP_buffer_free (so);
    LSUP_buffer_free (sc);

    if (UNLIKELY (!it->data)) {
        free (it);
        return NULL;
    }

    it->graph = gr;

    if (it->graph->store->sif->features & LSUP_STORE_COW) {
        // Copy-on-write store.
        it->sspo = BTRP_DUMMY;
        if (UNLIKELY (it->sspo == NULL)) return NULL;
        it->sspo->s->flags |= LSUP_BUF_BORROWED;
        it->sspo->p->flags |= LSUP_BUF_BORROWED;
        it->sspo->o->flags |= LSUP_BUF_BORROWED;
    } else {
        // TODO copy-on-retrieval store. No implementations yet.
    }

    return it;
}


LSUP_rc
LSUP_graph_iter_next (LSUP_GraphIterator *it, LSUP_Triple **spo_p)
{
    LSUP_rc rc = graph_iter_next_buffer (it);
    PRCCK (rc);
    if (rc != LSUP_OK) return rc;

    LSUP_Triple *spo = LSUP_triple_new (
        LSUP_term_new_from_buffer (it->sspo->s),
        LSUP_term_new_from_buffer (it->sspo->p),
        LSUP_term_new_from_buffer (it->sspo->o)
    );
    if (UNLIKELY (!spo)) return LSUP_MEM_ERR;

    *spo_p = spo;

    return LSUP_OK;
}

const LSUP_Graph *
LSUP_graph_iter_graph (LSUP_GraphIterator *it)
{ return it->graph; }


void
LSUP_graph_iter_free (LSUP_GraphIterator *it)
{
    if (UNLIKELY (!it)) return;

    it->graph->store->sif->lu_free_fn (it->data);

    /*
     * This deallocates resources properly by preserving borrowed pointers from
     * the store in case of LSUP_STORE_COW stores.
     */
    if (it->graph->store->sif->features & LSUP_STORE_COW) {
        LSUP_btriple_free (it->sspo);
        LOG_DEBUG("Freeing dummy triple @ %p", it->sspo);
    } else {
        // TODO copy-on-retrieval stores. None yet.
    }

    free (it);
}


LSUP_TermSet *
LSUP_graph_list_txn (void *txn, LSUP_Store *store)
{
    LSUP_Buffer **tdata = store->sif->ctx_list_fn (store->data, txn);
    if (UNLIKELY (!tdata)) return NULL;

    LSUP_TermSet *ts = LSUP_term_set_new();

    size_t i = 0;
    while (tdata[i]) {
        LSUP_Term *t = LSUP_term_new_from_buffer (tdata[i]);
        LSUP_rc rc = LSUP_term_set_add (ts, t, NULL);
        LSUP_buffer_free (tdata[i]);
        if (UNLIKELY (rc != LSUP_OK)) {
            LSUP_term_free (t);
            LSUP_term_set_free (ts);

            return NULL;
        }
        i++;
    }
    free (tdata);

    return ts;
}


bool
LSUP_graph_contains (const LSUP_Graph *gr, const LSUP_Triple *spo)
{
    LSUP_GraphIterator *it = LSUP_graph_lookup (
            gr, spo->s, spo->p, spo->o, NULL);
    LSUP_Triple *tmp_spo = NULL;
    bool rc = LSUP_graph_iter_next (it, &tmp_spo) != LSUP_END;

    LSUP_triple_free (tmp_spo);
    LSUP_graph_iter_free (it);

    return rc;
}


void
LSUP_graph_print (const LSUP_Graph *gr)
{
    size_t ct;
    LSUP_GraphIterator *it = LSUP_graph_lookup (gr, NULL, NULL, NULL, &ct);
    if (UNLIKELY (!it)) {
        log_error ("Could not inspect graph for printing.");
        return;
    }

    printf ("*** Graph %s (%zu triples):\n\n", gr->uri->data, ct);

    LSUP_Triple *spo = NULL;
    ct = 0;
    LSUP_rc rc = LSUP_NORESULT;
    while ((rc = LSUP_graph_iter_next (it, &spo)) == LSUP_OK) {
        printf (
                "#%-6zu {%s  %s  %s}\n",
                ct, spo->s->data, spo->p->data, spo->o->data);
        ct++;
    }
    if (rc != LSUP_END)
        log_error (
                "Output truncated due to abnormal return: %s",
                LSUP_strerror (rc));
}


LSUP_LinkMap *
LSUP_graph_connections (
        const LSUP_Graph *gr, const LSUP_Term *t, const LSUP_LinkType type)
{
    const LSUP_Term
        *s = NULL,
        *p = NULL,
        *o = NULL;

    // Position of passed term and link terms, respectively.
    LSUP_TriplePos pos1, pos2;

    if (type == LSUP_LINK_INBOUND) {
        o = t;
        pos1 = TRP_POS_O;
        pos2 = TRP_POS_P;
    } else if (type == LSUP_LINK_OUTBOUND) {
        s = t;
        pos1 = TRP_POS_S;
        pos2 = TRP_POS_P;
    } else if (type == LSUP_LINK_EDGE) {
        p = t;
        pos1 = TRP_POS_P;
        pos2 = TRP_POS_S;
    } else {
        log_error ("Invalid connection type: %d", type);
        return NULL;
    }

    // Gather all linking terms in a set first.
    LSUP_GraphIterator *it = LSUP_graph_lookup (gr, s, p, o, NULL);
    if (!it) return NULL;

    LSUP_TermSet *lts = LSUP_term_set_new();
    while (graph_iter_next_buffer (it) != LSUP_END) {
        LSUP_Term
            *ex = NULL,
            *ins = LSUP_term_new_from_buffer (
                    LSUP_btriple_pos (it->sspo, pos2));
        LSUP_term_set_add (lts, ins, &ex);

        if (ex) LSUP_term_free (ins);
    }
    LSUP_graph_iter_free(it);

    LSUP_LinkMap *ret = LSUP_link_map_new (t, type);
    if (!ret) return NULL;
    size_t i = 0;
    LSUP_Term *lt;
    while (LSUP_term_set_next (lts, &i, &lt) != LSUP_END) {
        LSUP_link_map_add (
                ret, LSUP_term_copy (lt),
                LSUP_graph_term_set (gr, t, pos1, lt, pos2));
    }
    LSUP_term_set_free (lts);

    return ret;
}


LSUP_TermSet *
LSUP_graph_term_set (
        const LSUP_Graph *gr, const LSUP_Term *t1, const LSUP_TriplePos t1_pos,
        const LSUP_Term *t2, const LSUP_TriplePos t2_pos)
{
    if (t1_pos == t2_pos) {
        log_error ("Term 1 and 2 positions cannot be the same!");
        return NULL;
    }

    const LSUP_Term *spo_l[3] = {NULL};
    spo_l[t1_pos] = t1;
    spo_l[t2_pos] = t2;
    LSUP_TriplePos rpos = 0;  // Position of term to be added to results.
    for (unsigned i = 0; i < 3; i++)
        if (t1_pos != i && t2_pos != i) rpos = i;

    LSUP_GraphIterator *it = LSUP_graph_lookup (
            gr, spo_l[0], spo_l[1], spo_l[2], NULL);

    LSUP_TermSet *ts = LSUP_term_set_new();
    while (graph_iter_next_buffer (it) != LSUP_END) {
        // There cannot be duplicates in a 2-bound lookup.
        LSUP_term_set_add (
                ts,
                LSUP_term_new_from_buffer (LSUP_btriple_pos (it->sspo, rpos)),
                NULL);
    }
    LSUP_graph_iter_free (it);

    return ts;
}


LSUP_TermSet *
LSUP_graph_unique_terms (const LSUP_Graph *gr, LSUP_TriplePos pos)
{
    // TODO We should use spo indices for stores that have them...
    LSUP_GraphIterator *it = LSUP_graph_lookup (gr, NULL, NULL, NULL, NULL);

    LSUP_TermSet *ts = LSUP_term_set_new();
    while (graph_iter_next_buffer (it) != LSUP_END) {
        LSUP_Term
            *ex = NULL,
            *ins = LSUP_term_new_from_buffer (LSUP_btriple_pos (it->sspo, pos));
        LSUP_term_set_add (ts, ins, &ex);

        if (ex) LSUP_term_free (ins);
    }
    LSUP_graph_iter_free(it);

    return ts;
}


size_t
LSUP_graph_add_link_map (LSUP_GraphIterator *it, LSUP_LinkMap *lm)
{
    LSUP_Triple *spo = TRP_DUMMY;
    size_t ct = 0;
    LSUP_LinkMapIterator *lmit = LSUP_link_map_iter_new (lm);

    while (LSUP_link_map_triples (lmit, spo) != LSUP_END) {
        LSUP_rc rc = LSUP_graph_add_iter (it, spo);
        if (rc >= 0) ct++;
        PRCCK (rc);
    }
    LSUP_link_map_iter_free (lmit);
    free (spo);

    return ct;
}


LSUP_Term *
LSUP_bnode_add_collection (LSUP_GraphIterator *it, LSUP_TermSet *ts)
{
    LSUP_NSMap *nsm = LSUP_graph_namespace (LSUP_graph_iter_graph (it));
    LSUP_Term
        *s = LSUP_term_new (LSUP_TERM_BNODE, NULL, NULL),
        *rdf_first = LSUP_iriref_new ("rdf:first", nsm),
        *rdf_rest = LSUP_iriref_new ("rdf:rest", nsm),
        *rdf_nil = LSUP_iriref_new ("rdf:nil", nsm),
        *link;

    LSUP_Triple *spo = TRP_DUMMY;
    link = s;
    size_t i = 0;
    LSUP_Term *t;
    while (LSUP_term_set_next (ts, &i, &t) != LSUP_END) {
        spo->s = link;
        spo->p = rdf_first;
        spo->o = t;
        PRCNL (LSUP_graph_add_iter (it, spo));

        spo->p = rdf_rest;
        size_t save_i = i; // Save iterator position to restore it after peek.
        spo->o = (
                // Peek into the next result.
                LSUP_term_set_next (ts, &i, NULL) != LSUP_END ?
                LSUP_term_new (LSUP_TERM_BNODE, NULL, NULL)
                : rdf_nil);
        i = save_i; // Restore the iterator that advanced when peeking.

        PRCNL (LSUP_graph_add_iter (it, spo));

        if (link != s) LSUP_term_free (link);
        // Current object becomes next subject. Irrelevant for last item.
        link = spo->o;
    }

    LSUP_term_free (rdf_first);
    LSUP_term_free (rdf_rest);
    LSUP_term_free (rdf_nil);
    free (spo);

    return s;
}


/*
 * Static functions.
 */

/** @brief Advance an iterator and return a serialized triple.
 *
 * This is an internal function to pass raw buffers between higher-level
 * functions without serializing and deserializing triples.
 *
 * The results are stored in it->sspo.
 */
inline static LSUP_rc
graph_iter_next_buffer (LSUP_GraphIterator *it)
{ return it->graph->store->sif->lu_next_fn (it->data, it->sspo, NULL); }


/**
 * Extern inline definitions.
 */

size_t LSUP_graph_size (const LSUP_Graph *gr);