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.
                                              */
    void *                  txn;            ///< Store transaction.
};

struct graph_iter_t {
    const LSUP_Graph *      graph;          ///< Parent graph.
    void *                  data;           ///< Iterator state.
    size_t                  ct;             ///< Total lookup matches.
};


/*
 * Static prototypes.
 */

inline static LSUP_rc
graph_iter_next_buffer (LSUP_GraphIterator *it, LSUP_BufferTriple *sspo);

#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_Term *uri, const LSUP_StoreType store_type, const char *store_id,
        LSUP_NSMap *nsm, size_t size)
{
    if (UNLIKELY (!LSUP_IS_INIT)) {
        log_error (
                "Environment is not initialized. Did you call LSUP_init()?");
        return NULL;
    }
    if (UNLIKELY (!check_backend (store_type))) return NULL;

    LSUP_Graph *gr;
    MALLOC_GUARD (gr, NULL);

    gr->uri = uri;
    MALLOC_GUARD (gr->store, NULL);

    gr->store->type = store_type;
    gr->store->id = store_id ? strdup (store_id) : NULL;

    switch (gr->store->type) {
#define ENTRY(a, b) \
        case LSUP_STORE_##a: gr->store->sif = &b; break;
BACKEND_TBL
#undef ENTRY
        default:
            log_error ("Not a valid store type: %d", store_type); return NULL;
    };

    // TODO implement custom default context.
    gr->store->data = gr->store->sif->new_fn (store_id, size);

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

    gr->txn = NULL;

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


LSUP_rc
LSUP_graph_bool_op(
        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;
    }

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

    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, gr1->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, gr1->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,
                    gr1->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, gr1->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,
                gr1->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_buffer_free (res_sc);
    LSUP_buffer_free (gr1_sc);
    LSUP_buffer_free (gr2_sc);

    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);
    gr->store->sif->free_fn (gr->store->data);
    free (gr->store);

    free (gr);
}


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


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)
{ return gr->store->sif->size_fn (gr->store->data); }


bool
LSUP_graph_equals (const LSUP_Graph *gr1, const LSUP_Graph *gr2)
{
    LSUP_Graph *res = LSUP_graph_new (NULL, LSUP_STORE_HTABLE, NULL, NULL, 0);
    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 (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, gr->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}",
            spo->s->data, spo->p->data, spo->o->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 = sif->add_iter_fn (it->data, sspo);
    PCHECK (rc, finally);

    // Store datatype term permanently if the store supports it.
    if (rc == LSUP_OK && sif->add_term_fn) {
        void *txn;
        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);
                // Run add_term in the iterator's txn.
                txn = sif->iter_txn_fn ? sif->iter_txn_fn (it->data) : NULL;
                sif->add_term_fn ( it->graph->store->data, ser_dtype, txn);
                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 (LSUP_Graph *gr, const LSUP_Triple trp[], size_t *ct)
{
    LSUP_rc rc = LSUP_NOACTION;

    // Initialize iterator.
    LSUP_GraphIterator *it = LSUP_graph_add_init (gr);

    if (ct) *ct = 0;
    // Serialize and insert RDF triples.
    for (size_t i = 0; trp[i].s != 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 the
            // counter.
        }
        if (UNLIKELY (db_rc < 0)) {
            rc = db_rc;
            goto finally;
        }
    }

finally:
    LSUP_graph_add_done (it);

    return rc;
}


LSUP_rc
LSUP_graph_remove (
        LSUP_Graph *gr, const LSUP_Term *s, const LSUP_Term *p,
        const LSUP_Term *o, size_t *ct)
{
    LSUP_rc rc;

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

    rc = gr->store->sif->remove_fn (
            gr->store->data, ss, sp, so, sc, gr->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 (const LSUP_Graph *src, LSUP_Graph *dest)
{
    LSUP_rc rc = LSUP_NOACTION;

    LSUP_GraphIterator *it = LSUP_graph_lookup (src, NULL, NULL, NULL, NULL);

    LSUP_Triple spo;

    LSUP_GraphIterator *add_it = LSUP_graph_add_init (dest);
    while (LSUP_graph_iter_next (it, &spo) != LSUP_END) {
        LSUP_rc add_rc = LSUP_graph_add_iter (add_it, &spo);
        LSUP_triple_done (&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 (
        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, gr->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;

    return it;
}


LSUP_rc
LSUP_graph_iter_next (LSUP_GraphIterator *it, LSUP_Triple *spo)
{
    LSUP_Buffer *ss, *sp, *so;
    LSUP_BufferTriple *sspo;
    if (it->graph->store->sif->features & LSUP_STORE_COW) {
        CALLOC_GUARD (ss, LSUP_MEM_ERR);
        CALLOC_GUARD (sp, LSUP_MEM_ERR);
        CALLOC_GUARD (so, LSUP_MEM_ERR);
        sspo = LSUP_btriple_new (ss, sp, so);
    } else {
        // TODO copy-on-retrieval stores. None yet.
    }

    LSUP_rc rc = graph_iter_next_buffer (it, sspo);

    if (rc == LSUP_OK) {
        spo->s = LSUP_term_new_from_buffer (sspo->s);
        if (!spo->s) return LSUP_ERROR;
        spo->p = LSUP_term_new_from_buffer (sspo->p);
        if (!spo->p) return LSUP_ERROR;
        spo->o = LSUP_term_new_from_buffer (sspo->o);
        if (!spo->o) return LSUP_ERROR;
    }

    if (it->graph->store->sif->features & LSUP_STORE_COW) {
        LSUP_btriple_free_shallow (sspo);
    } else {
        // TODO copy-on-retrieval stores. None yet.
    }

    return rc;
}


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);
    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 = TRP_DUMMY;
    bool rc = LSUP_graph_iter_next (it, tmp_spo) != LSUP_END;

    LSUP_triple_free (tmp_spo);
    LSUP_graph_iter_free (it);

    return rc;
}


LSUP_rc
LSUP_graph_begin (LSUP_Graph *gr, int flags) {
    if (!(gr->store->sif->features & LSUP_STORE_TXN)) return LSUP_VALUE_ERR;

    return gr->store->sif->txn_begin_fn(gr->store->data, flags, &gr->txn);
}


LSUP_rc
LSUP_graph_commit (LSUP_Graph *gr)
{
    LSUP_rc rc = gr->store->sif->txn_commit_fn (gr->txn);

    if (rc == LSUP_OK) gr->txn = NULL;

    return rc;
}


void
LSUP_graph_abort (LSUP_Graph *gr)
{
    gr->store->sif->txn_abort_fn (gr->txn);
    gr->txn = NULL;
}


LSUP_LinkMap *
LSUP_graph_connections (
        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;
    }

    LSUP_GraphIterator *it = LSUP_graph_lookup (gr, s, p, o, NULL);

    LSUP_LinkMap *ret = LSUP_link_map_new (type);
    LSUP_BufferTriple *sspo = BTRP_DUMMY;
    // Gather all linking terms in a set first.
    LSUP_TermSet *lts = LSUP_term_set_new();
    while (graph_iter_next_buffer (it, sspo) != LSUP_END) {
        LSUP_Term
            *ex = NULL,
            *ins = LSUP_term_new_from_buffer (LSUP_btriple_pos (sspo, pos2));
        LSUP_term_set_add (lts, ins, &ex);

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

    size_t i = 0;
    LSUP_Term *lt;
    while (LSUP_term_set_next (lts, &i, &lt) != LSUP_END) {
        LSUP_link_map_add (
                ret, lt, LSUP_graph_term_set (gr, t, pos1, lt, pos2));
    }

    return ret;
}


LSUP_TermSet *
LSUP_graph_term_set (
        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;  // Position of term to be added to results.
    for (int 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();
    LSUP_BufferTriple *sspo = BTRP_DUMMY;
    while (graph_iter_next_buffer (it, sspo) != LSUP_END) {
        // There cannot be duplicates in a 2-bound lookup.
        LSUP_term_set_add (
                ts,
                LSUP_term_new_from_buffer (LSUP_btriple_pos (sspo, rpos)),
                NULL);
    }
    LSUP_graph_iter_free (it);

    return ts;
}


LSUP_TermSet *
LSUP_graph_unique_terms (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_BufferTriple *sspo = BTRP_DUMMY;
    LSUP_TermSet *ts = LSUP_term_set_new();
    while (graph_iter_next_buffer (it, sspo) != LSUP_END) {
        LSUP_Term
            *ex = NULL,
            *ins = LSUP_term_new_from_buffer (LSUP_btriple_pos (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);

    while (LSUP_link_map_triples (lmit, t, 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.
 */
inline static LSUP_rc
graph_iter_next_buffer (LSUP_GraphIterator *it, LSUP_BufferTriple *sspo)
{ return it->graph->store->sif->lu_next_fn (it->data, sspo, NULL); }


/**
 * Extern inline definitions.
 */

size_t LSUP_graph_size (const LSUP_Graph *gr);