volksdata/include/term.h

#ifndef _LSUP_TERM_H
#define _LSUP_TERM_H

#include <assert.h>
#include <regex.h>

#include "buffer.h"
#include "namespace.h"

#define UUID4_URN_SIZE UUIDSTR_SIZE + 10

/** @brief Default data type for untyped literals (prefixed IRI).
 */
#define DEFAULT_DTYPE           "http://www.w3.org/2001/XMLSchema#string"

/** @brief URI parsing regular expression.
 *
 * Based on RFC3986 (see https://tools.ietf.org/html/rfc3986#appendix-B) and
 * modified for use in this application. Relevant matching groups are the
 * following, for a sample URI `http://example.org/123/456/?query=blah#frag`:
 *
 * #0:  Full parsed URI (http://example.org/123/456/?query=blah#frag)
 * #1:  Domain prefix (http://example.org)
 * #2:  Protocol (http:)
 * #4:  Authority (example.org)
 * #5:  Path relative to domain (/123/456/?query=blah#frag)
 * #6:  Path, excluding query and fragment (/123/456/)
 * #8:  Query (query=blah)
 * #10: Fragment (frag)
 *
 * For URN-like URIs, such as `urn:s:0`, the prefix part (#1) is `urn:` and
 * the path (#4) is `s:0`.
 */
#define LSUP_URI_REGEX_STR \
    "^(([^:/?#]+:)?(//([^/?#]*))?)?(([^?#]*)(\\?([^#]*))?(#(.*))?)"


/*
 * Data types.
 */

/// Language tag, currently restricted to 7 characters.
typedef char LSUP_LangTag[8];

/// Term type.
typedef enum {
    LSUP_TERM_UNDEFINED = 0,/**<
                              * Undefined placeholder or result of an error.
                              * Invalid for most operations.
                              */
    LSUP_TERM_IRIREF,       ///< IRI reference.
    LSUP_TERM_NS_IRIREF,    ///< Namespace-prefixed IRI reference.
    LSUP_TERM_LITERAL,      ///< Literal without language tag.
    LSUP_TERM_LT_LITERAL,   ///< Language-tagged string literal.
    LSUP_TERM_BNODE,        ///< Blank node.
} LSUP_TermType;

/** @brief IRI information.
 *
 * See regex matching group for #LSUP_URI_REGEX_STR for more information.
 */
typedef struct iri_info_t LSUP_IRIInfo;

/// RDF term.
typedef struct term_t {
    char *              data;       // URI, literal value, or BNode label.
    union {
        struct term_t * datatype;   // Data type IRI for LSUP_TERM_LITERAL.
        LSUP_LangTag    lang;       // Lang tag for LSUP_TERM_LT_LITERAL.
        LSUP_Key        bnode_id;   // BNode ID for comparison & skolemization.
        LSUP_IRIInfo *  iri_info;   // IRI information structure.
    };
    LSUP_TermType       type;       // Term type.
} LSUP_Term;


/** @brief Shorthand to test if a term is a IRI of any kind.
 */
#define LSUP_IS_IRI(term) \
    ((term)->type == LSUP_TERM_IRIREF || (term)->type == LSUP_TERM_NS_IRIREF)

/** @brief Shorthand to test if a term is a literal of any kind.
 */
#define LSUP_IS_LITERAL(term) \
    ((term)->type == LSUP_TERM_LITERAL || (term)->type == LSUP_TERM_LT_LITERAL)


typedef struct triple_t {
    LSUP_Term *s;
    LSUP_Term *p;
    LSUP_Term *o;
} LSUP_Triple;


/** @brief Key-term pair.
 */
typedef struct term_cache_entry_t {
    LSUP_Key            key;        // Key (hash) of the term.
    LSUP_Term *         term;       // Term handle.
} LSUP_KeyedTerm;


/// Connection type: inbound or outbound.
typedef enum {
    LSUP_CONN_INBOUND,              ///< Inbound connection.
    LSUP_CONN_OUTBOUND,             ///< Outbound connection.
} LSUP_ConnectionType;


/** @brief Connection list.
 *
 * A list of predicates and related lists of terms, that can be used to list
 * inbound or outbound connections to a node.
 *
 * Each term in the NUL-terminated `p` list represent a predicate which is
 * paired with a list of terms in the `tl` list. The index of each predicate
 * corresponds to the same index of a term list.
 *
 * If the type of the connection list is `LSUP_CONN_INBOUND`, the term list
 * represent subjects and a term that is associated with the connection list is
 * the related object; if `LSUP_CONN_OUTBOUND`, the term list represents
 * objects, and a term that is associated with the connection list represents
 * the subject.
 *
 */
typedef struct {
    LSUP_ConnectionType type;       ///< Inbound or outbound connection.
    LSUP_Term **    p;              ///< NUL-terminated array of term handles.
    LSUP_Term ***   tl;             /**<
                                      * NUL-terminated array of
                                      * NUL-terminated arrays of term handles.
                                      */
} LSUP_ConnectionList;


/*
 * Extern variables.
 */

/** @brief Global term cache.
 *
 * Stores frequently used terms, e.g. data type URIs.
 */
extern struct hashmap *LSUP_term_cache;

/** @brief Compiled hash of default literal data type.
 */
extern uint32_t LSUP_default_dtype_key;

/** @brief URI validation pattern, compiled in #LSUP_init().
 */
extern regex_t *LSUP_uri_ptn;

/** @brief Default literal data type URI.
 *
 * Literal terms created with undefined data type will have it set to this
 * URI implicitly.
 */
extern LSUP_Term *LSUP_default_datatype;


/*
 * API functions.
 */

/** @brief Create a new term.
 *
 * This is a generic function; it is recommended to use specialized functions
 * such as #LSUP_term_new(), #LSUP_literal_new(), etc. as they have strict type
 * checks for the metadata parameter.
 *
 * @param type[in] Term type. One of #LSUP_TermType.
 *
 * @param data[in] Term data: textual URI, literal value without data type
 *  or langtag, etc. It may be NULL for IRI refs and BNodes, in which case a
 *  random identifier is generated.
 *
 * @param metadata[in] Namespace map (LSUP_NSMap *) for IRI refs; language tag
 * (LSUP_LangTag *) for language-tagged literals; or data type (LSUP_Term *)
 * for other literals. It may be NULL.
 *
 * @return New term, which must be freed with #LSUP_term_free after use; or
 *  NULL on error.
 */
LSUP_Term *
LSUP_term_new (LSUP_TermType type, const char *data, void *metadata);


/** @brief Placeholder term to use with LSUP_term_reset.
 */
#define TERM_DUMMY LSUP_term_new (LSUP_TERM_UNDEFINED, NULL, NULL)


/** @brief Shortcut to create an IRI reference.
 *
 * Must be freed with #LSUP_term_free.
 *
 * @param data[in] The URI string. If NULL, a UUID4-based URN is generated.
 *  This cannot be NULL if the nsm parameter is not NULL.
 *
 * @param nsm[in] Namespace map. If not NULL, a namespace-prefixed
 *  (#LSUP_TERM_NS_IRIREF) is created, otherwise a regular one
 *  (#LSUP_TERM_IRIREF).
 *
 * @return same as #LSUP_term_new().
 */
inline LSUP_Term *
LSUP_iriref_new (const char *data, LSUP_NSMap *nsm)
{
    return (
            nsm ? LSUP_term_new (LSUP_TERM_NS_IRIREF, data, nsm) :
            LSUP_term_new (LSUP_TERM_IRIREF, data, NULL));
}


/** @brief Create a new absolute IRI from a path relative to a root IRI.
 *
 * The term is always of type LSUP_TERM_IRIREF (i.e. not namespace-prefixed).
 *
 * If the provided IRI is already a fully qualified IRI (i.e. it has a prefix)
 * the result is semantically identical to the input.
 *
 * If the relative IRI begins with a '/', the resulting IRI is relative to the
 * web root of the root IRI. I.e. if a root IRI has a path after the webroot,
 * it is ignored.
 *
 * Otherwise, the resulting IRI is relative to the full root string.
 *
 * @param[in] root Root IRI that the new IRI should be relative to.
 *
 * @param[in] iri Term with an IRI relative to the webroot.
 *
 * @return New absolute IRI, or NULL if either term is not an IRI.
 */
LSUP_Term *
LSUP_iriref_absolute (const LSUP_Term *root, const LSUP_Term *iri);


/** @brief Create a new relative IRI from an absolute IRI and a web root IRI.
 *
 * This works with namespace-prefixed IRIs and returns a term of the same type
 * as the input.
 *
 * @param[in] iri Full IRI.
 *
 * @param[in] root Root IRI that the new IRI should be relative to.
 *
 * @return New IRI, or NULL if either term is not an IRI. If the input IRI is
 * not a path under the root IRI, the result will be identical to the input.
 */
LSUP_Term *
LSUP_iriref_relative (const LSUP_Term *root, const LSUP_Term *iri);


/** @brief Shortcut to create a literal term.
 *
 * Must be freed with #LSUP_term_free.
 *
 * @param data[in] The literal string.
 *
 * @param datatype[in] Data type URI string. If NULL, the default data type
 * (xsd:string) is used. The new term takes ownership of the pointer.
 *
 * @return same as #LSUP_term_new().
 */
inline LSUP_Term *
LSUP_literal_new (const char *data, LSUP_Term *datatype)
{ return LSUP_term_new (LSUP_TERM_LITERAL, data, datatype); }


/** @brief Shortcut to create a language-tagged literal term.
 *
 * Must be freed with #LSUP_term_free.
 *
 * @param data[in] The literal string.
 *
 * @param lang[in] Language tag string.
 *
 * @return same as #LSUP_term_new().
 */
inline LSUP_Term *
LSUP_lt_literal_new (const char *data, char *lang)
{ return LSUP_term_new (LSUP_TERM_LT_LITERAL, data, lang); }


/** @brief Shortcut to create a blank node.
 *
 * Must be freed with #LSUP_term_free.
 *
 * @param data[in] The BNode identifier.
 *
 * @return same as #LSUP_term_new().
 */
inline LSUP_Term *
LSUP_bnode_new (const char *data)
{ return LSUP_term_new (LSUP_TERM_BNODE, data, NULL); }


/** @brief Copy a term.
 *
 * @param[in] src The term to copy.
 *
 * @return A new duplicate term handle.
 */
LSUP_Term *
LSUP_term_copy (const LSUP_Term *src);


/** @brief Deserialize a buffer into a term.
 *
 * @param[in] sterm Buffer to convert into a term. It must be a valid
 *  serialized term from store or obtained with #LSUP_term_serialize().
 *
 * @return New term handle. It must be freed with #LSUP_term_free().
 */
LSUP_Term *
LSUP_term_new_from_buffer (const LSUP_Buffer *sterm);


/** @brief Serialize a term into a buffer.
 *
 * @param[in] sterm Term to convert into a buffer.
 *
 * @return New buffer handle. It must be freed with #LSUP_buffer_free().
 */
LSUP_Buffer *
LSUP_term_serialize (const LSUP_Term *term);


/** @brief Hash a buffer.
 */
LSUP_Key
LSUP_term_hash (const LSUP_Term *term);


/** @brief Compare two terms.
 *
 * The terms evaluate as equal if their hashes are equal—i.e. if they are
 * semantically equivalent.
 */
inline bool LSUP_term_equals (const LSUP_Term *term1, const LSUP_Term *term2)
{ return LSUP_term_hash (term1) == LSUP_term_hash (term2); }


void
LSUP_term_free (LSUP_Term *term);


/** @brief Namespace map of a IRI ref.
 *
 * @param[in] iri IRI reference handle.
 *
 * @return A pointer to the namespace map associated with the IRI. It is
 *  freed at program shutdown.
 */
LSUP_NSMap *
LSUP_iriref_nsm (const LSUP_Term *iri);


/** @brief Get the prefix portion of a IRI ref.
 *
 * @param[in] iri IRI reference handle.
 *
 * @return String containing the protocol and domain name part of the IRI. It
 *  should be freed after use.
 */
char *
LSUP_iriref_prefix (const LSUP_Term *iri);


/** @brief Get the path portion of a IRI ref.
 *
 * @param[in] iri IRI reference handle.
 *
 * @return String containing the path of the IRI relative to the web root. For
 * a URN, such as `urn:myns:myid`, it would be `myns:myid`. This string should
 * be freed after use.
 */
char *
LSUP_iriref_path (const LSUP_Term *iri);


/** @brief Get the fragment portion of a IRI ref.
 *
 * @param[in] iri IRI reference handle.
 *
 * @return String containing the fragment part of the IRI, or NULL if the IRI
 * contains no fragment. It should be freed after use.
 */
char *
LSUP_iriref_frag (const LSUP_Term *iri);

/*
 * TRIPLES
 */

/** @brief Create a new triple from three terms.
 *
 * Terms are NOT copied. To free them with the triple, use #LSUP_triple_free().
 * To only free the triple, use free().
 *
 * TODO Term types are not validated at the moment.
 *
 * @param[in] s Triple subject. It must be an IRIRef or BNode.
 *
 * @param[in] p Triple predicate. It must be an IRIRef.
 *
 * @param[in] o Triple object.
 *
 */
LSUP_Triple *
LSUP_triple_new(LSUP_Term *s, LSUP_Term *p, LSUP_Term *o);


/** @brief Dummy triple with NULL slots. It is not a valid triple.
 */
#define TRP_DUMMY LSUP_triple_new (NULL, NULL, NULL)


LSUP_Triple *
LSUP_triple_new_from_btriple (const LSUP_BufferTriple *sspo);


LSUP_BufferTriple *
LSUP_triple_serialize (const LSUP_Triple *spo);


/** @brief Initialize internal term pointers in a heap-allocated triple.
 *
 * Terms are NOT copied. To free them with the triple, use #LSUP_triple_free().
 * To only free the triple, use free().
 *
 * @param spo[in] Triple pointer to initialize.
 */
LSUP_rc
LSUP_triple_init (LSUP_Triple *spo, LSUP_Term *s, LSUP_Term *p, LSUP_Term *o);


/** @brief Free the internal pointers of a triple.
 *
 * @param spo[in] Triple to be freed.
 */
void
LSUP_triple_done (LSUP_Triple *spo);


/** @brief Free a triple and all its internal pointers.
 *
 * NOTE: If the term pointers are not to be freed (e.g. they are owned by a
 * back end), use a simple free(spo) instead of this.
 *
 * @param spo[in] Triple to be freed.
 */
void
LSUP_triple_free (LSUP_Triple *spo);


/** @brief Get triple by term position.
 *
 * Useful for looping over all terms.
 *
 * @param trp[in] Triple pointer.
 *
 * @param n[in] A number between 0÷2.
 *
 * @return Corresponding triple term or NULL if n is out of range.
 */
inline LSUP_Term *
LSUP_triple_pos (const LSUP_Triple *trp, LSUP_TriplePos n)
{
    if (n == TRP_POS_S) return trp->s;
    if (n == TRP_POS_P) return trp->p;
    if (n == TRP_POS_O) return trp->o;
    return NULL;
}


/** @brief Hash a triple.
 *
 * TODO This doesn't handle blank nodes correctly.
 */
inline LSUP_Key
LSUP_triple_hash (const LSUP_Triple *trp)
{
    LSUP_BufferTriple *strp = LSUP_triple_serialize (trp);
    LSUP_Key hash = LSUP_btriple_hash (strp);
    LSUP_btriple_free (strp);

    return hash;
}


/** @brief Add an identifier to the term cache.
 *
 * @param[in] key Hash of the inserted term.
 *
 * @param[in] term Term to insert. A copy of the term is stored in the cache,
 *  which is freed on application teardown.
 */
LSUP_rc
LSUP_tcache_add (const LSUP_Key key, const LSUP_Term *term);

/** @brief Get an identifier from the cache.
 *
 * @param[in] key Key for the queried term.
 *
 * @return The retrieved term if found, or NULL. The string must not be
 *  modified or freed.
 */
const LSUP_Term *
LSUP_tcache_get (LSUP_Key key);


/** @brief Add term to a term list.
 *
 * @param[in] tl Array of term handles to be added to. The handle must be NUL-
 *  terminated. On success, this handle will be reallocated and the new address
 *  returned, so the passed handle should no longer be used. On failure, it
 *  remains unchanged and may be reused.
 *
 * @param[in] t Term to be added to the list. The object list will take
 *  ownership of the term.
 *
 * @return Reallocated list on success; NULL on failure.
 */
LSUP_Term **
LSUP_term_list_add (LSUP_Term **tl, LSUP_Term *t);


/** @brief New predicate-object list.
 *
 * The initial state of the returned list is: `{p: [NULL], tl: [NULL]}`
 *
 * Predicates and term lists can be added with #LSUP_conn_list_add, and terms
 * can be added to a term list with #LSUP_term_list_add.
 *
 * @return a new empty predicate-object list.
 */
LSUP_ConnectionList *
LSUP_conn_list_list_new (LSUP_ConnectionType type);


/** @brief Free a predicate-object list.
 *
 * All arrays and term handles are recursively freed.
 *
 * @param[in] pol Predicate-object list handle obtained with
 *  #LSUP_conn_list_list_new().
 */
void
LSUP_conn_list_list_free (LSUP_ConnectionList *pol);


/** @brief Add a predicate-object list pair to a PO list.
 *
 * @param[in] pol Predicate-object list handle obtained with
 *  #LSUP_conn_list_list_new().
 *
 *  @param[in] p Predicate to be associated with the given object list. The
 *   PO structure takes ownership of the term.
 *
 *  @param[in] o NULL-terminated array of object term handles to be associated
 *   with the given predicate. The PO structire takes ownership of the whole
 *   term array.
 *
 * @return LSUP_OK on success; LSUP_MEM_ERR on allocation error.
 */
LSUP_rc
LSUP_conn_list_list_add (LSUP_ConnectionList *pol, LSUP_Term *p, LSUP_Term **o);

#endif