/*************************************************************************/
/* Copyright (c) 2004 */
/* Daniel Sleator, David Temperley, and John Lafferty */
/* Copyright (c) 2009, 2013 Linas Vepstas */
/* All rights reserved */
/* */
/* Use of the link grammar parsing system is subject to the terms of the */
/* license set forth in the LICENSE file included with this software. */
/* This license allows free redistribution and use in source and binary */
/* forms, with or without modification, subject to certain conditions. */
/* */
/*************************************************************************/
#ifndef _LINK_GRAMMAR_CONNECTORS_H_
#define _LINK_GRAMMAR_CONNECTORS_H_
#include <ctype.h> // islower()
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h> // uint8_t ...
#include "api-types.h"
#include "error.h"
#include "memory-pool.h"
#include "string-set.h"
/* MAX_SENTENCE cannot be more than 254, because word MAX_SENTENCE+1 is
* BAD_WORD -- it is used to indicate that nothing can connect to this
* connector, and this should fit in one byte (because the word field
* of a connector is an uint8_t, see below).
*/
#define MAX_SENTENCE 254 /* Maximum number of words in a sentence */
/* Length-limits for how far connectors can reach out. */
#define UNLIMITED_LEN 255
/* Since tracon IDs are unique per sentence, for convenience NULL
* connectors (zero-length tracons) have tracon IDs equal to the word
* number on which their disjunct resides. To that end an initial block
* of IDs is reserved. It is the maximum number of words in a sentence
* rounded up to a power of 2.
*/
#define NULL_TRACON_BLOCK 256
/* For faster comparisons, the connector lc part is encoded into a number
* and a mask. Each letter is encoded using LC_BITS bits. With 7 bits, it
* is possible to encode up to 9 letters in an uint64_t. */
#define LC_BITS 7
#define LC_MASK ((1<<LC_BITS)-1)
#define MAX_CONNECTOR_LC_LENGTH 9
#define MAX_LINK_NAME_LENGTH 12
typedef uint64_t lc_enc_t;
typedef uint32_t connector_uc_hash_t;
#define CD_HEAD_DEPENDENT (1<<0) /* Has a leading 'h' or 'd'. */
#define CD_HEAD (1<<1) /* 0: dependent; 1: head; */
#define CD_PERMANENT (1<<2) /* For SQL dict: Do not clear (future). */
/* Validate connector string characters.
* Note that only ASCII characters are allowed. */
static inline bool is_connector_name_char(unsigned char c)
{
if (isupper(c)) return true;
if (unlikely(c == '_')) return true;
return false;
}
static inline bool is_connector_subscript_char(unsigned char c)
{
if (islower(c)) return true;
if (unlikely(isdigit(c))) return true;
if (unlikely(c == '*')) return true;
return false;
}
/* End of connector string character validation. */
typedef struct condesc_struct condesc_t;
/* The connector descriptors (see below) are pointed from a hash table
* with these elements. */
typedef struct hdesc
{
condesc_t *desc;
} hdesc_t;
typedef struct
{
const char *string; /* The connector name w/o the direction mark, e.g. ABc */
connector_uc_hash_t str_hash;
uint8_t length_limit; /* If not 0, it gives the limit of the length of the
* link that can be used on this connector type. The
* value UNLIMITED_LEN specifies no limit.
* If 0, short_length (a Parse_Option) is used. If
* all_short==true (a Parse_Option), length_limit
* is clipped to short_length. */
uint8_t flags; /* CD_* */
/* For connector match speedup when sorting the connector table. */
uint8_t uc_length; /* uc part length */
uint8_t uc_start; /* uc start position */
// float *cost; // Array of cost by connector length (cost[0]: default)
} condesc_more_t;
/* Each connector type has a connector descriptor. The size of this
* struct is 32 byes, to facilitate CPU memory caching during parsing.
* The "more" field points to connector information that is needed in
* other steps. The con_num field is used a lot in steps that need
* connector hashing, and it is included here to avoid extra
* redirections.
* Multi connectors are considering the same type as their non-multi
* version, so the multi indication is kept in Connector_struct. */
struct condesc_struct
{
lc_enc_t lc_letters;
lc_enc_t lc_mask;
condesc_more_t *more;/* More information, for keeping small struct size. */
connector_uc_hash_t uc_num; /* uc part enumeration. */
uint32_t con_num; /* Connector ordinal number. */
};
typedef struct length_limit_def
{
const char *defword;
const Exp *defexp;
struct length_limit_def *next;
int length_limit;
} length_limit_def_t;
typedef struct
{
hdesc_t *hdesc; /* Hashed connector descriptors table */
condesc_t **sdesc; /* Alphabetically sorted descriptors */
size_t size; /* Allocated size */
size_t num_con; /* Number of connector types */
size_t num_uc; /* Number of connector types with different UC part */
size_t last_num; /* All condescs up to here have been done already. */
Pool_desc *desc_pool; /* For condesc_t elements. */
Pool_desc *more_pool; /* For condesc_t::more. */
length_limit_def_t *length_limit_def;
length_limit_def_t **length_limit_def_next;
} ConTable;
/* On a 64-bit machine, this struct should be exactly 4*8=32 bytes long.
* Lets try to keep it that way. */
struct Connector_struct
{
uint8_t farthest_word;/* The farthest word to my left (or right)
that this could ever connect to. Computed
by set_connector_farthest_word(). */
uint8_t nearest_word; /* The nearest word to my left (or right) that
this could ever connect to. Initialized by
setup_connectors(). Final value is found in
the power pruning. */
uint8_t prune_pass; /* Prune pass number (one bit could be enough) */
bool multi; /* TRUE if this is a multi-connector */
int32_t tracon_id; /* Tracon identifier (see disjunct-utils.c) */
const condesc_t *desc;
Connector *next;
union
{
const gword_set *originating_gword; /* Used while and after parsing. */
struct
{
int32_t refcount; /* Memory-sharing reference count - for pruning. */
uint16_t exp_pos; /* The position in the originating expression,
* currently used only for debugging dict macros. */
bool shallow; /* TRUE if this is a shallow connector.
* A connector is shallow if it is the first in
* its list on its disjunct. (It is deep if it is
* not the first in its list; it is deepest if it
* is the last on its list.) */
};
};
};
void condesc_init(Dictionary, size_t);
void condesc_reset(Dictionary);
void condesc_setup(Dictionary);
condesc_t *condesc_add(ConTable *ct, const char *);
void condesc_delete(Dictionary);
void condesc_reuse(Dictionary);
/* GET accessors for connector attributes.
* Can be used for experimenting with Connector_struct internals in
* non-trivial ways without the need to change most of the code that
* accesses connectors */
static inline const char * connector_string(const Connector *c)
{
return c->desc->more->string;
}
static inline unsigned int connector_uc_start(const Connector *c)
{
return c->desc->more->uc_start;
}
static inline unsigned int connector_uc_length(const Connector *c)
{
return c->desc->more->uc_length;
}
static inline const condesc_t *connector_desc(const Connector *c)
{
return c->desc;
}
static inline unsigned int connector_uc_hash(const Connector * c)
{
return c->desc->uc_num;
}
static inline unsigned int connector_uc_num(const Connector * c)
{
return c->desc->uc_num;
}
static inline unsigned int connector_num(const Connector * c)
{
return 2 * c->desc->con_num + c->multi;
}
/* Connector utilities ... */
Connector * connector_new(Pool_desc *, const condesc_t *);
void set_connector_farthest_word(Exp *, int, int, Parse_Options);
void free_connectors(Connector *);
void calculate_connector_info(condesc_t *);
int condesc_by_uc_constring(const void *, const void *);
/**
* Compare only the uppercase part of two connectors.
* Return true if they are the same, else false.
*/
static inline bool connector_uc_eq(const Connector *c1, const Connector *c2)
{
return (connector_uc_num(c1) == connector_uc_num(c2));
}
/*
* Return the deepest connector in the connector chain starting with \p c.
* @param c Any connector
* @return The deepest connector (can be modified if needed).
*/
static inline Connector *connector_deepest(const Connector *c)
{
for (; c->next != NULL; c = c->next)
;
return (Connector *)c; /* Note: Constness removed. */
}
/**
* Returns TRUE if s and t match according to the connector matching
* rules. The connector strings must be properly formed, starting with
* zero or one lower case letters, followed by one or more upper case
* letters, followed by some other letters.
*
* The algorithm is symmetric with respect to a and b.
*
* Connectors starting with lower-case letters match ONLY if the initial
* letters are DIFFERENT. Otherwise, connectors only match if the
* upper-case letters are the same, and the trailing lower case letters
* are the same (or have wildcards).
*
* The initial lower-case letters allow an initial 'h' (denoting 'head
* word') to match an initial 'd' (denoting 'dependent word'), while
* rejecting a match 'h' to 'h' or 'd' to 'd'. This allows the parser
* to work with catena, instead of just links.
*/
static inline bool easy_match(const char * s, const char * t)
{
char is = 0, it = 0;
if (islower((int) *s)) { is = *s; s++; }
if (islower((int) *t)) { it = *t; t++; }
if (is != 0 && it != 0 && is == it) return false;
while (isupper((int)*s) || isupper((int)*t))
{
if (*s != *t) return false;
s++;
t++;
}
while ((*s!='\0') && (*t!='\0'))
{
if ((*s == '*') || (*t == '*') || (*s == *t))
{
s++;
t++;
}
else
return false;
}
return true;
}
/**
* Compare the lower-case and head/dependent parts of two connector descriptors.
* When this function is called, it is assumed that the upper-case
* parts are equal, and thus do not need to be checked again.
*/
static inline bool lc_easy_match(const condesc_t *c1, const condesc_t *c2)
{
return (((c1->lc_letters ^ c2->lc_letters) & c1->lc_mask & c2->lc_mask) ==
(c1->lc_mask & c2->lc_mask & 1));
}
/**
* This function is like easy_match(), but with connector descriptors.
* It uses a shortcut comparison of the upper-case parts.
*/
static inline bool easy_match_desc(const condesc_t *c1, const condesc_t *c2)
{
if (c1->uc_num != c2->uc_num) return false;
return lc_easy_match(c1, c2);
}
static inline uint32_t string_hash(const char *s)
{
unsigned int i;
/* djb2 hash */
i = 5381;
while (*s)
{
i = ((i << 5) + i) + *s;
s++;
}
return i;
}
typedef uint32_t connector_hash_t;
static const connector_hash_t FIBONACCI_MULT = 0x9E3779B9;
static inline connector_hash_t connector_hash(const Connector *c)
{
// connector_num() is different for each connector string + its multi
// attribute, and it naturally depends also on its head-dependent
// attribute, if any. For the importance of considering the
// head-dependent attribute during hashing see pull req #1487;
return connector_num(c);
}
/**
* \p c is assumed to be non-NULL.
*/
// To check hash functions, enable the "N" printing in
// eliminate_duplicate_disjuncts().
#define FEEDBACK_HASH 1
static inline connector_hash_t connector_list_hash(const Connector *c)
{
connector_hash_t accum = connector_hash(c);
for (c = c->next; c != NULL; c = c->next)
#if FEEDBACK_HASH
accum = (accum<<7) + (accum<<14) + (accum >> 16) - connector_hash(c);
#else
// Bad.
accum = (19 * accum) + connector_hash(c);
#endif
return accum;
}
/**
* Hash function for the classic parser linkage memoization.
*/
static inline size_t pair_hash(int lw, int rw,
int l_id, const int r_id,
unsigned int null_count)
{
size_t i;
#if 0
/* hash function. Based on some tests, this seems to be
* an almost "perfect" hash, in that almost all hash buckets
* have the same size! */
i = 1 << cost;
i += 1 << (lw % (log2_table_size-1));
i += 1 << (rw % (log2_table_size-1));
i += ((unsigned int) le) >> 2;
i += ((unsigned int) le) >> log2_table_size;
i += ((unsigned int) re) >> 2;
i += ((unsigned int) re) >> log2_table_size;
i += i >> log2_table_size;
#else
/* sdbm-based hash */
i = null_count;
i = lw + (i << 6) + (i << 16) - i;
i = rw + (i << 6) + (i << 16) - i;
i = l_id + (i << 6) + (i << 16) - i;
i = r_id + (i << 6) + (i << 16) - i;
#endif
if (i == 0) i = 1; /* Allow for table hash field validation. */
return i;
}
/**
* Get the word number of the given tracon.
* It is extracted from the nearest_word of the deepest connector.
* @param c The leading tracon connector.
* @param dir Direction - 0: left; 1: right.
* @return Sentence word number.
*
* This function depends on setup_connectors() (which initializes
* nearest_word). It should not be called during or after power_prune()
* (which changes nearest_word).
*
* Note: An alternative for getting the word number of a tracon is to keep
* it in the tracon list table or in a separate array. Both ways add
* noticeable overhead, maybe due to the added CPU cache footprint.
* However, if the need arises for the word number of a tracon during/after
* power_prune(), there will be a need to keep it in an alternative way.
*/
static inline int get_tracon_word_number(Connector *c, int dir)
{
c = connector_deepest(c);
return c->nearest_word + ((dir == 0) ? 1 : -1);
}
#endif /* _LINK_GRAMMAR_CONNECTORS_H_ */