volksdata/src/graph.c

#include "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, LSUP_Term *uri, LSUP_NSMap *nsm)
{
    // Create a HTable graph by default.
    if (!store) store = LSUP_store_new (LSUP_STORE_HTABLE, NULL, 0);

    LSUP_Graph *gr;
    MALLOC_GUARD (gr, NULL);

    gr->uri = uri? LSUP_term_copy (uri) : LSUP_iriref_new (NULL, NULL);
    gr->store = store;

    if (gr->store->sif->features & LSUP_STORE_PERM) gr->nsm = NULL;
    else gr->nsm = nsm ? nsm : LSUP_default_nsm;

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


LSUP_Graph *
LSUP_graph_get_txn (void *txn, LSUP_Store *store, 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, 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) {
        // TODO This is inefficient, it's deserializing a buffer triple that
        // will be re-serialized by LSUP_graph_add_iter.
        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) {
        rc = LSUP_graph_copy_contents (gr1, res);
        PCHECK (rc, fail);
        rc = LSUP_graph_copy_contents (gr2, res);
        PCHECK (rc, fail);

        return LSUP_OK;
    }

    /* END union block. */

    /* BEGIN subtraction, intersection, XOR 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;

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

    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, NULL, txn);
        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,
                    txn, &ct);
            if (ct == 0)
                res->store->sif->add_iter_fn (add_it, sspo);
            gr1->store->sif->lu_free_fn (lu1_it);
        }
        gr2->store->sif->lu_free_fn (lu2_it);
    }

    lu1_it = gr1->store->sif->lookup_fn (
            gr1->store->data, NULL, NULL, NULL, gr1_sc, 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,
                txn, &ct);
        // 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);
        gr2->store->sif->lu_free_fn (lu2_it);
    }
    gr1->store->sif->lu_free_fn (lu1_it);

    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:
    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 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, LSUP_Term *uri)
{
    if (!LSUP_IS_IRI (uri)) {
        log_error ("Term provided is not a IRI.");
        return LSUP_VALUE_ERR;
    }

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

    return LSUP_OK;
}


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);
    LSUP_BufferTriple *sspo = LSUP_triple_serialize (spo);
    if (UNLIKELY (!sspo)) return LSUP_MEM_ERR;
    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);
                LSUP_rc term_rc = sif->add_term_fn (
                        it->graph->store->data, ser_dtype, it->data);
                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;
}


/**
 * Copy triples from a source graph into a destination one.
 *
 * The destination graph is not initialized here, so the copy is cumulative.
 */
LSUP_rc
LSUP_graph_copy_contents_txn (
        void *txn, const LSUP_Graph *src, LSUP_Graph *dest)
{
    LSUP_rc rc = LSUP_NOACTION;

    LSUP_GraphIterator *it = LSUP_graph_lookup_txn (
            txn, src, NULL, NULL, NULL, 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);

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

    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-wite 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)
{
    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);
}


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;
}


LSUP_LinkMap *
LSUP_graph_connections (
        const LSUP_Graph *gr, LSUP_Term *t, LSUP_LinkType type)
{
    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 {
        // Very unlikely.
        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);
    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 (type);
    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, LSUP_Term *t1, LSUP_TriplePos t1_pos,
        LSUP_Term *t2, LSUP_TriplePos t2_pos)
{
    if (t1_pos == t2_pos) {
        log_error ("Term 1 and 2 positions cannot be the same!");
        return NULL;
    }

    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_Term *t, LSUP_LinkMap *lmap)
{
    LSUP_Triple *spo = TRP_DUMMY;
    size_t ct = 0;
    LSUP_LinkMapIterator *lmit = LSUP_link_map_iter_new (lmap, t);

    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);