<commit_before>/*************************************************************************/
/* Copyright (c) 2004                                                    */
/* <NAME>, <NAME>, and <NAME>                    */
/* Copyright (c) 2009, 2013, 2014 <NAME>                          */
/* 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.   */
/*                                                                       */
/*************************************************************************/

#include "api-structures.h"
#include "count.h"
#include "dict-api.h"  /* for print_expression when debugging */
#include "disjunct-utils.h"
#include "externs.h"
#include "post-process.h"
#include "print.h"
#include "prune.h"
#include "resources.h"
#include "string-set.h"
#include "word-utils.h"

#define CONTABSZ 8192
typedef Connector * connector_table;

typedef struct disjunct_dup_table_s disjunct_dup_table;
struct disjunct_dup_table_s
{
	unsigned int dup_table_size;
	Disjunct ** dup_table;
};

/* Indicator that this connector cannot be used -- that its "obsolete".  */
#define BAD_WORD (MAX_SENTENCE+1)

typedef struct c_list_s C_list;
struct c_list_s
{
	C_list * next;
	Connector * c;
	bool shallow;
};

typedef struct power_table_s power_table;
struct power_table_s
{
	unsigned int power_table_size;
	unsigned int *l_table_size;  /* the sizes of the hash tables */
	unsigned int *r_table_size;
	C_list *** l_table;
	C_list *** r_table;
};

typedef struct cms_struct Cms;
struct cms_struct
{
	Cms * next;
	const char * name;
	int count;	  /* the number of times this is in the multiset */
};

#define CMS_SIZE (2<<10)
typedef struct multiset_table_s multiset_table;
struct multiset_table_s
{
	Cms * cms_table[CMS_SIZE];
};

typedef struct prune_context_s prune_context;
struct prune_context_s
{
	bool null_links;
	int power_cost;
	int N_changed;   /* counts the number of changes
						   of c->word fields in a pass */
	power_table *pt;
	Sentence sent;
};

/*

  The algorithms in this file prune disjuncts from the disjunct list
  of the sentence that can be elimininated by a simple checks.  The first
  check works as follows:

  A series of passes are made through the sentence, alternating
  left-to-right and right-to-left.  Consier the left-to-right pass (the
  other is symmetric).  A set S of connectors is maintained (initialized
  to be empty).  Now the disjuncts of the current word are processed.
  If a given disjunct's left pointing connectors have the property that
  at least one of them has no connector in S to which it can be matched,
  then that disjunct is deleted. Now the set S is augmented by the right
  connectors of the remaining disjuncts of that word.  This completes
  one word.  The process continues through the words from left to right.
  Alternate passes are made until no disjunct is deleted.

  It worries me a little that if there are some really huge disjuncts lists,
  then this process will probably do nothing.  (This fear turns out to be
  unfounded.)

  Notes:  Power pruning will not work if applied before generating the
  "and" disjuncts.  This is because certain of it's tricks don't work.
  Think about this, and finish this note later....
  Also, currently I use the standard connector match procedure instead
  of the pruning one, since I know power pruning will not be used before
  and generation.  Replace this to allow power pruning to work before
  generating and disjuncts.

  Currently it seems that normal pruning, power pruning, and generation,
  pruning, and power pruning (after "and" generation) and parsing take
  about the same amount of time.  This is why doing power pruning before
  "and" generation might be a very good idea.

  New idea:  Suppose all the disjuncts of a word have a connector of type
  c pointing to the right.  And further, suppose that there is exactly one
  word to its right containing that type of connector pointing to the left.
  Then all the other disjuncts on the latter word can be deleted.
  (This situation is created by the processing of "either...or", and by
  the extra disjuncts added to a "," neighboring a conjunction.)

*/

/**
 * This hash function only looks at the leading upper case letters of
 * the connector string, and the label fields.  This ensures that if two
 * strings match (formally), then they must hash to the same place.
 */
static inline unsigned int hash_S(Connector * c)
{
	unsigned int h = connector_hash(c);
	return (h & (CONTABSZ-1));
}

static void zero_connector_table(connector_table *ct)
{
	memset(ct, 0, sizeof(Connector *) * CONTABSZ);
}

/**
 * This function puts connector c into the connector table
 * if one like it isn't already there.
 */
static void insert_connector(connector_table *ct, Connector * c)
{
	unsigned int h;
	Connector * e;

	h = hash_S(c);

	for (e = ct[h]; e != NULL; e = e->tableNext)
	{
		if (string_set_cmp(c->string, e->string))
			return;
	}
	c->tableNext = ct[h];
	ct[h] = c;
}

/*
   The second algorithm eliminates disjuncts that are dominated by
   another.  It works by hashing them all, and checking for domination.
*/

#if 0
/* ============================================================x */

/*
  Consider the idea of deleting a disjunct if it is dominated (in terms of
  what it can match) by some other disjunct on the same word.  This has
  been implemented below.  There are three problems with it:

  (1) It is almost never the case that any disjuncts are eliminated.

  (2) connector_matches_alam may not be exactly correct.

  (3) The linkage that is eliminated by this, might just be the one that
      passes post-processing, as the following example shows.
      This is pretty silly, and should probably be changed.

> telling John how our program works would be stupid
Accepted (2 linkages, 1 with no P.P. violations)
  Linkage 1, cost vector = (0, 0, 7)

   +------------------G-----------------+
   +-----R-----+----CL----+             |
   +---O---+   |   +---D--+---S---+     +--I-+-AI-+
   |       |   |   |      |       |     |    |    |
telling.g John how our program.n works would be stupid

               /////         CLg    <---CLg--->  CL      telling.g
 (g)           telling.g     G      <---G----->  G       would
 (g) (d)       telling.g     R      <---R----->  R       how
 (g) (d)       telling.g     O      <---O----->  O       John
 (g) (d)       how           CLe    <---CLe--->  CL      program.n
 (g) (d) (e)   our           D      <---Ds---->  Ds      program.n
 (g) (d) (e)   program.n     Ss     <---Ss---->  Ss      works
 (g)           would         I      <---Ix---->  Ix      be
 (g)           be            AI     <---AIi--->  AIi     stupid

(press return for another)
>
  Linkage 2 (bad), cost vector = (0, 0, 7)

   +------------------G-----------------+
   +-----R-----+----CL----+             |
   +---O---+   |   +---D--+---S---+     +--I-+-AI-+
   |       |   |   |      |       |     |    |    |
telling.g John how our program.n works would be stupid

               /////         CLg    <---CLg--->  CL      telling.g
 (g)           telling.g     G      <---G----->  G       would
 (g) (d)       telling.g     R      <---R----->  R       how
 (g) (d)       telling.g     O      <---O----->  O       John
 (g) (d)       how           CLe    <---CLe--->  CL      program.n
 (g) (d) (e)   our           D      <---Ds---->  Ds      program.n
 (g) (d) (e)   program.n     Ss     <---Ss---->  Ss      works
 (g)           would         I      <---Ix---->  Ix      be
 (g)           be            AI     <---AI---->  AI      stupid

P.P. violations:
      Special subject rule violated
*/

/**
 * hash function that takes a string and a seed value i
 */
static int string_hash(disjunct_dup_table *dt, const char * s, int i)
{
	for(;*s != '\0';s++) i = i + (i<<1) + randtable[(*s + i) & (RTSIZE-1)];
	return (i & (dt->dup_table_size-1));
}

/**
 * This returns true if the connector a matches everything that b
 *  matches, and possibly more.  (alam=at least as much)
 *
 * TRUE for equal connectors.
 * remains TRUE if multi-match added to the first.
 * remains TRUE if subsrcripts deleted from the first.
 */
static bool connector_matches_alam(Connector * a, Connector * b)
{
	char * s, * t, *u;
	if (((!a->multi) && b->multi) ||
		(a->label != b->label))  return false;
	s = a->string;
	t = b->string;

	/* isupper -- connectors cannot be UTF8 at this time */
	while (isupper(*s) || isupper(*t))
	{
		if (*s == *t) {
			s++;
			t++;
		} else return false;
	}
	while ((*s != '\0') && (*t != '\0')) {
		if ((*s == *t) || (*s == '*')) {
			s++;
			t++;
		} else return false;
	}
	while ((*s != '\0') && (*s == '*')) s++;
	return (*s == '\0');
}


/**
 * This hash function that takes a connector and a seed value i.
 * It only looks at the leading upper case letters of
 * the string, and the label.  This ensures that if two connectors
 * match, then they must hash to the same place.
 */
static int conn_hash(Connector * c, int i)
{
	int nb;
	const char * s;
	s = c->string;

	i = i + (i<<1) + randtable[(c->label + i) & (RTSIZE-1)];
	nb = is_utf8_upper(s);
	while (nb)
	{
		i = i + (i<<1) + randtable[(*s + i) & (RTSIZE-1)];
		s += nb;
		nb = is_utf8_upper(s);
	}
	return i;
}

static inline int pconnector_hash(disjunct_dup_table *dt, Connector * c, int i)
{
	i = conn_hash(c, i);
	return (i & (ct->dup_table_size-1));
}

/**
 * This is a hash function for disjuncts
 */
static int hash_disjunct(disjunct_dup_table *dt, Disjunct * d)
{
	int i;
	Connector *e;
	i = 0;
	for (e = d->left ; e != NULL; e = e->next)
	{
		i = pconnector_hash(dt, e, i);
	}
	for (e = d->right ; e != NULL; e = e->next)
	{
		i = pconnector_hash(dt, e, i);
	}
	return string_hash(dt, d->string, i);
}

/**
 * Returns TRUE if disjunct d1 can match anything that d2 can
 * if this happens, it constitutes a proof that there is absolutely
 * no use for d2.
 */
static bool disjunct_matches_alam(Disjunct * d1, Disjunct * d2)
{
	Connector *e1, *e2;
	if (d1->cost > d2->cost) return false;
	e1 = d1->left;
	e2 = d2->left;
	while ((e1!=NULL) && (e2!=NULL))
	{
		if (!connector_matches_alam(e1,e2)) break;
		e1 = e1->next;
		e2 = e2->next;
	}
	if ((e1!=NULL) || (e2!=NULL)) return false;
	e1 = d1->right;
	e2 = d2->right;
	while ((e1!=NULL) && (e2!=NULL))
	{
		if (!connector_matches_alam(e1,e2)) break;
		e1 = e1->next;
		e2 = e2->next;
	}
	if ((e1!=NULL) || (e2!=NULL)) return false;
	return (strcmp(d1->string, d2->string) == 0);
}

/**
 * Takes the list of disjuncts pointed to by d, eliminates all
 * duplicates, and returns a pointer to a new list.
 * It frees the disjuncts that are eliminated.
 */
Disjunct * eliminate_duplicate_disjuncts(Disjunct * d)
{
	int i, h, count;
	Disjunct *dn, *dx, *dxn, *front;
	count = 0;
	disjunct_dup_table *dt;

	dt = disjunct_dup_table_new(next_power_of_two_up(2 * count_disjuncts(d)));

	for (;d!=NULL; d = dn)
	{
		dn = d->next;
		h = hash_disjunct(d);

		front = NULL;
		for (dx = dt->dup_table[h]; dx != NULL; dx = dxn)
		{
			dxn = dx->next;
			if (disjunct_matches_alam(dx,d))
			{
				/* we know that d should be killed */
				d->next = NULL;
				free_disjuncts(d);
				count++;
				front = catenate_disjuncts(front, dx);
				break;
			} else if (disjunct_matches_alam(d,dx)) {
				/* we know that dx should be killed off */
				dx->next = NULL;
				free_disjuncts(dx);
				count++;
			} else {
				/* neither should be killed off */
				dx->next = front;
				front = dx;
			}
		}
		if (dx == NULL) {
			/* we put d in the table */
			d->next = front;
			front = d;
		}
		dt->dup_table[h] = front;
	}

	/* d is now NULL */
	for (i = 0; i < dt->dup_table_size; i++)
	{
		for (dx = dt->dup_table[i]; dx != NULL; dx = dxn)
		{
			dxn = dx->next;
			dx->next = d;
			d = dx;
		}
	}

	if ((verbosity > 2) && (count != 0)) printf("killed %d duplicates\n", count);

	disjunct_dup_table_delete(dt);
	return d;
}

/* ============================================================x */
#endif

/* ================================================================= */
/**
 * Here is expression pruning.  This is done even before the expressions
 * are turned into lists of disjuncts.
 *
 * This uses many of the same data structures and functions that are used
 * by prune.
 *
 * The purge operations remove all irrelevant stuff from the expression,
 * and free the purged stuff.  A connector is deemed irrelevant if its
 * string pointer has been set to NULL.  The passes through the sentence
 * have the job of doing this.
 *
 * If an OR or AND type expression node has one child, we can replace it
 * by its child.  This, of course, is not really necessary, except for
 * performance(?)
 */

static Exp* purge_Exp(Exp *);

/**
 * Get rid of the elements with null expressions
 */
static E_list * or_purge_E_list(E_list * l)
{
	E_list * el;
	if (l == NULL) return NULL;
	if ((l->e = purge_Exp(l->e)) == NULL)
	{
		el = or_purge_E_list(l->next);
		xfree((char *)l, sizeof(E_list));
		return el;
	}
	l->next = or_purge_E_list(l->next);
	return l;
}

/**
 * Returns 0 iff the length of the disjunct list is 0.
 * If this is the case, it frees the structure rooted at l.
 */
static int and_purge_E_list(E_list * l)
{
	if (l == NULL) return 1;
	if ((l->e = purge_Exp(l->e)) == NULL)
	{
		free_E_list(l->next);
		xfree((char *)l, sizeof(E_list));
		return 0;
	}
	if (and_purge_E_list(l->next) == 0)
	{
		free_Exp(l->e);
		xfree((char *)l, sizeof(E_list));
		return 0;
	}
	return 1;
}

/**
 * Must be called with a non-null expression.
 * Return NULL iff the expression has no disjuncts.
 */
static Exp* purge_Exp(Exp *e)
{
	if (e->type == CONNECTOR_type)
	{
		if (e->u.string == NULL)
		{
			xfree((char *)e, sizeof(Exp));
			return NULL;
		}
		else
		{
			return e;
		}
	}
	if (e->type == AND_type)
	{
		if (and_purge_E_list(e->u.l) == 0)
		{
			xfree((char *)e, sizeof(Exp));
			return NULL;
		}
	}
	else /* if we are here, its OR_type */
	{
		e->u.l = or_purge_E_list(e->u.l);
		if (e->u.l == NULL)
		{
			xfree((char *)e, sizeof(Exp));
			return NULL;
		}
	}

/* This code makes it kill off nodes that have just one child
   (1) It's going to give an insignificant speed-up
   (2) Costs have not been handled correctly here.
   The code is excised for these reasons.
*/
/*
	if ((e->u.l != NULL) && (e->u.l->next == NULL))
	{
		ne = e->u.l->e;
		xfree((char *) e->u.l, sizeof(E_list));
		xfree((char *) e, sizeof(Exp));
		return ne;
	}
*/
	return e;
}

/**
 * Returns TRUE if c can match anything in the set S (err. the connector table ct).
 */
static inline bool matches_S(connector_table *ct, Connector * c)
{
	Connector * e;

	for (e = ct[hash_S(c)]; e != NULL; e = e->tableNext)
	{
		if (easy_match(e->string, c->string)) return true;
	}
	return false;
}

/**
 * Mark as dead all of the dir-pointing connectors
 * in e that are not matched by anything in the current set.
 * Returns the number of connectors so marked.
 */
static int mark_dead_connectors(connector_table *ct, Exp * e, char dir)
{
	int count;
	count = 0;
	if (e->type == CONNECTOR_type)
	{
		if (e->dir == dir)
		{
			Connector dummy;
			init_connector(&dummy);
			dummy.string = e->u.string;
			if (!matches_S(ct, &dummy))
			{
				e->u.string = NULL;
				count++;
			}
		}
	}
	else
	{
		E_list *l;
		for (l = e->u.l; l != NULL; l = l->next)
		{
			count += mark_dead_connectors(ct, l->e, dir);
		}
	}
	return count;
}

/**
 * Put into the set S all of the dir-pointing connectors still in e.
 * Return a list of allocated dummy connectors; these will need to be
 * freed.
 */
static Connector * insert_connectors(connector_table *ct, Exp * e,
                                     Connector *alloc_list, int dir)
{
	if (e->type == CONNECTOR_type)
	{
		if (e->dir == dir)
		{
			Connector *dummy = connector_new();
			dummy->string = e->u.string;
			insert_connector(ct, dummy);
			dummy->next = alloc_list;
			alloc_list = dummy;
		}
	}
	else
	{
		E_list *l;
		for (l=e->u.l; l!=NULL; l=l->next)
		{
			alloc_list = insert_connectors(ct, l->e, alloc_list, dir);
		}
	}
	return alloc_list;
}

/**
 * This removes the expressions that are empty from the list corresponding
 * to word w of the sentence.
 */
static void clean_up_expressions(Sentence sent, int w)
{
	X_node head_node, *d, *d1;
	d = &head_node;
	d->next = sent->word[w].x;
	while (d->next != NULL)
	{
		if (d->next->exp == NULL)
		{
			d1 = d->next;
			d->next = d1->next;
			xfree((char *)d1, sizeof(X_node));
		}
		else
		{
			d = d->next;
		}
	}
	sent->word[w].x = head_node.next;
}

/* #define DBG(X) X */
#define DBG(X)

void expression_prune(Sentence sent)
{
	int N_deleted;
	X_node * x;
	size_t w;
	Connector *ct[CONTABSZ];
	Connector *dummy_list = NULL;

	zero_connector_table(ct);

	N_deleted = 1;  /* a lie to make it always do at least 2 passes */

	while (1)
	{
		/* Left-to-right pass */
		/* For every word */
		for (w = 0; w < sent->length; w++)
		{
			/* For every expression in word */
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
DBG(printf("before marking: "); print_expression(x->exp); printf("\n"););
				N_deleted += mark_dead_connectors(ct, x->exp, '-');
DBG(printf(" after marking: "); print_expression(x->exp); printf("\n"););
			}
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
DBG(printf("before purging: "); print_expression(x->exp); printf("\n"););
				x->exp = purge_Exp(x->exp);
DBG(printf("after purging: "); print_expression(x->exp); printf("\n"););
			}

			/* gets rid of X_nodes with NULL exp */
			clean_up_expressions(sent, w);
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
				dummy_list = insert_connectors(ct, x->exp, dummy_list, '+');
			}
		}

		if (verbosity > 2)
		{
			printf("l->r pass removed %d\n", N_deleted);
			print_expression_sizes(sent);
		}

		/* Free the allocated dummy connectors */
		free_connectors(dummy_list);
		dummy_list = NULL;
		zero_connector_table(ct);

		if (N_deleted == 0) break;

		/* Right-to-left pass */
		N_deleted = 0;
		for (w = sent->length-1; w != (size_t) -1; w--)
		{
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
/*	 printf("before marking: "); print_expression(x->exp); printf("\n"); */
				N_deleted += mark_dead_connectors(ct, x->exp, '+');
/*	 printf("after marking: "); print_expression(x->exp); printf("\n"); */
			}
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
/*	 printf("before perging: "); print_expression(x->exp); printf("\n"); */
				x->exp = purge_Exp(x->exp);
/*	 printf("after perging: "); print_expression(x->exp); printf("\n"); */
			}
			clean_up_expressions(sent, w);  /* gets rid of X_nodes with NULL exp */
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
				dummy_list = insert_connectors(ct, x->exp, dummy_list, '-');
			}
		}

		if (verbosity > 2)
		{
			printf("r->l pass removed %d\n", N_deleted);
			print_expression_sizes(sent);
		}

		/* Free the allocated dummy connectors */
		free_connectors(dummy_list);
		dummy_list = NULL;
		zero_connector_table(ct);
		if (N_deleted == 0) break;
		N_deleted = 0;
	}
}



/*
  Here is what you've been waiting for: POWER-PRUNE

  The kinds of constraints it checks for are the following:

	1) successive connectors on the same disjunct have to go to
	   nearer and nearer words.

	2) two deep connectors cannot attach to each other
	   (A connectors is deep if it is not the first in its list; it
	   is shallow if it is the first in its list; it is deepest if it
	   is the last on its list.)

	3) on two adjacent words, a pair of connectors can be used
	   only if they're the deepest ones on their disjuncts

	4) on two non-adjacent words, a pair of connectors can be used only
	   if not [both of them are the deepest].

   The data structure consists of a pair of hash tables on every word.
   Each bucket of a hash table has a list of pointers to connectors.
   These nodes also store if the chosen connector is shallow.
*/
/*
   As with normal pruning, we make alternate left->right and right->left
   passes.  In the R->L pass, when we're on a word w, we make use of
   all the left-pointing hash tables on the words to the right of w.
   After the pruning on this word, we build the left-pointing hash table
   this word.  This guarantees idempotence of the pass -- after doing an
   L->R, doing another would change nothing.

   Each connector has an integer c_word field.  This refers to the closest
   word that it could be connected to.  These are initially determined by
   how deep the connector is.  For example, a deepest connector can connect
   to the neighboring word, so its c_word field is w+1 (w-1 if this is a left
   pointing connector).  It's neighboring shallow connector has a c_word
   value of w+2, etc.

   The pruning process adjusts these c_word values as it goes along,
   accumulating information about any way of linking this sentence.
   The pruning process stops only after no disjunct is deleted and no
   c_word values change.

   The difference between RUTHLESS and GENTLE power pruning is simply
   that GENTLE uses the deletable region array, and RUTHLESS does not.
   So we can get the effect of these two different methods simply by
   always unsuring that deletable[][] has been defined.  With nothing
   deletable, this is equivalent to RUTHLESS.   --DS, 7/97
*/

/**
 * returns the number of connectors in the left lists of the disjuncts.
 */
static int left_connector_count(Disjunct * d)
{
	Connector *c;
	int i=0;
	for (;d!=NULL; d=d->next) {
		for (c = d->left; c!=NULL; c = c->next) i++;
	}
	return i;
}

static int right_connector_count(Disjunct * d)
{
	Connector *c;
	int i=0;
	for (;d!=NULL; d=d->next) {
	  for (c = d->right; c!=NULL; c = c->next) i++;
	}
	return i;
}

static void free_C_list(C_list * t)
{
	C_list *xt;
	for (; t!=NULL; t=xt) {
		xt = t->next;
		xfree((char *)t, sizeof(C_list));
	}
}

/**
 * free all of the hash tables and C_lists
 */
static void power_table_delete(power_table *pt)
{
	unsigned int w;
	unsigned int i;

	for (w = 0; w < pt->power_table_size; w++)
	{
		for (i = 0; i < pt->l_table_size[w]; i++)
		{
			free_C_list(pt->l_table[w][i]);
		}
		xfree((char *)pt->l_table[w], pt->l_table_size[w] * sizeof (C_list *));

		for (i = 0; i < pt->r_table_size[w]; i++)
		{
			free_C_list(pt->r_table[w][i]);
		}
		xfree((char *)pt->r_table[w], pt->r_table_size[w] * sizeof (C_list *));
	}
	xfree(pt->l_table_size, 2 * pt->power_table_size * sizeof(unsigned int));
	xfree(pt->l_table, 2 * pt->power_table_size * sizeof(C_list **));
	xfree(pt, sizeof(power_table));
}

/**
 * The disjunct d (whose left or right pointer points to c) is put
 * into the appropriate hash table
 */
static void put_into_power_table(unsigned int size, C_list ** t, Connector * c, bool shal)
{
	unsigned int h;
	C_list * m;
	h = connector_hash(c) & (size-1);
	m = (C_list *) xalloc (sizeof(C_list));
	m->next = t[h];
	t[h] = m;
	m->c = c;
	m->shallow = shal;
}

static int set_dist_fields(Connector * c, size_t w, int delta)
{
	int i;
	if (c == NULL) return (int) w;
	i = set_dist_fields(c->next, w, delta) + delta;
	c->word = i;
	return i;
}

/**
 * Allocates and builds the initial power hash tables
 */
static power_table * power_table_new(Sentence sent)
{
	power_table *pt;
	size_t w, len;
	unsigned int i, size;
	C_list ** t;
	Disjunct * d, * xd, * head;
	Connector * c;

	pt = (power_table *) xalloc (sizeof(power_table));
	pt->power_table_size = sent->length;
	pt->l_table_size = xalloc (2 * sent->length * sizeof(unsigned int));
	pt->r_table_size = pt->l_table_size + sent->length;
	pt->l_table = xalloc (2 * sent->length * sizeof(C_list **));
	pt->r_table = pt->l_table + sent->length;

   /* First, we initialize the word fields of the connectors, and
	  eliminate those disjuncts with illegal connectors */
	for (w=0; w<sent->length; w++)
	{
	  head = NULL;
	  for (d=sent->word[w].d; d!=NULL; d=xd) {
		  xd = d->next;
		  if ((set_dist_fields(d->left, w, -1) < 0) ||
			  (set_dist_fields(d->right, w, 1) >= (int) sent->length)) {
			  d->next = NULL;
			  free_disjuncts(d);
		  } else {
			  d->next = head;
			  head = d;
		  }
	  }
	  sent->word[w].d = head;
	}

	for (w=0; w<sent->length; w++)
	{
		/* The below uses variable-sized hash tables. This seems to
		 * provide performance that is equal or better than the best
		 * fixed-size prformance.
		 * The best fixed-size performance seems to come at about
		 * a 1K table size, for both English and Russian. (Both have
		 * about 100 fixed link-types, and many thousands of auto-genned
		 * link types (IDxxx idioms for both, LLxxx suffix links for
		 * Russian).  Plusses and minuses:
		 * + small fixed tables are faster to initialize.
		 * - small fixed tables have more collisions
		 * - variable-size tables require counting connectors.
		 *   (and the more complex code to go with)
		 * CPU cache-size effects ...
		 * Strong depenence on the hashing algo!
		 */
		len = left_connector_count(sent->word[w].d);
		size = next_power_of_two_up(len);
#define TOPSZ 32768
		if (TOPSZ < size) size = TOPSZ;
		pt->l_table_size[w] = size;
		t = pt->l_table[w] = (C_list **) xalloc(size * sizeof(C_list *));
		for (i=0; i<size; i++) t[i] = NULL;

		for (d=sent->word[w].d; d!=NULL; d=d->next) {
			c = d->left;
			if (c != NULL) {
				put_into_power_table(size, t, c, true);
				for (c=c->next; c!=NULL; c=c->next){
					put_into_power_table(size, t, c, false);
				}
			}
		}

		len = right_connector_count(sent->word[w].d);
		size = next_power_of_two_up(len);
		if (TOPSZ < size) size = TOPSZ;
		pt->r_table_size[w] = size;
		t = pt->r_table[w] = (C_list **) xalloc(size * sizeof(C_list *));
		for (i=0; i<size; i++) t[i] = NULL;

		for (d=sent->word[w].d; d!=NULL; d=d->next) {
			c = d->right;
			if (c != NULL) {
				put_into_power_table(size, t, c, true);
				for (c=c->next; c!=NULL; c=c->next){
					put_into_power_table(size, t, c, false);
				}
			}
		}
	}

	return pt;
}

/**
 * This runs through all the connectors in this table, and eliminates those
 * who are obsolete.  The word fields of an obsolete one has been set to
 * BAD_WORD.
 */
static void clean_table(unsigned int size, C_list ** t)
{
	unsigned int i;
	C_list * m, * xm, * head;
	for (i = 0; i < size; i++) {
		head = NULL;
		for (m = t[i]; m != NULL; m = xm) {
			xm = m->next;
			if (m->c->word != BAD_WORD) {
				m->next = head;
				head = m;
			} else {
				xfree((char *) m, sizeof(C_list));
			}
		}
		t[i] = head;
	}
}

/**
 * This takes two connectors (and whether these are shallow or not)
 * (and the two words that these came from) and returns TRUE if it is
 * possible for these two to match based on local considerations.
 */
static bool possible_connection(prune_context *pc,
                               Connector *lc, Connector *rc,
                               bool lshallow, bool rshallow,
                               int lword, int rword)
{
	int dist;
	if ((!lshallow) && (!rshallow)) return false;

	/* Two deep connectors can't work */
	if ((lc->word > rword) || (rc->word < lword)) return false;

	dist = rword - lword;
	// assert(0 < dist, "Bad word order in possible connection.");

	/* Word range constraints */
	if (1 == dist)
	{
		if (!((lc->next == NULL) && (rc->next == NULL))) return false;
	}
	else
	if (dist > lc->length_limit || dist > rc->length_limit)
	{
		return false;
	}
	/* If the words are NOT next to each other, then there must be
	 * at least one intervening connector (i.e. cannot have both
	 * lc->next amnd rc->next being null).  But we only enforce this
	 * when we think its still possible to have a complete parse,
	 * i.e. before well allow null-linked words.
	 */
	else
	if ((!pc->null_links) &&
	    (lc->next == NULL) &&
	    (rc->next == NULL) &&
	    (!lc->multi) && (!rc->multi))
	{
		return false;
	}

	return easy_match(lc->string, rc->string);
}

/**
 * This returns TRUE if the right table of word w contains
 * a connector that can match to c.  shallow tells if c is shallow.
 */
static bool
right_table_search(prune_context *pc, int w, Connector *c,
                   bool shallow, int word_c)
{
	unsigned int size, h;
	C_list *cl;
	power_table *pt;

	if (word_c - w > c->length_limit) return false;

	pt = pc->pt;
	size = pt->r_table_size[w];
	h = connector_hash(c) & (size-1);
	for (cl = pt->r_table[w][h]; cl != NULL; cl = cl->next)
	{
		if (possible_connection(pc, cl->c, c, cl->shallow, shallow, w, word_c))
		{
			return true;
		}
	}
	return false;
}

/**
 * This returns TRUE if the right table of word w contains
 * a connector that can match to c.  shallows tells if c is shallow
 */
static bool
left_table_search(prune_context *pc, int w, Connector *c,
                  bool shallow, int word_c)
{
	unsigned int size, h;
	C_list *cl;
	power_table *pt;

	if (w - word_c > c->length_limit) return false;

	pt = pc->pt;
	size = pt->l_table_size[w];
	h = connector_hash(c) & (size-1);
	for (cl = pt->l_table[w][h]; cl != NULL; cl = cl->next)
	{
		if (possible_connection(pc, c, cl->c, shallow, cl->shallow, word_c, w))
			return true;
	}
	return false;
}

/**
 * Take this connector list, and try to match it with the words
 * w-1, w-2, w-3...  Returns the word to which the first connector of
 * the list could possibly be matched.  If c is NULL, returns w.  If
 * there is no way to match this list, it returns a negative number.
 * If it does find a way to match it, it updates the c->word fields
 * correctly.
 */
static int
left_connector_list_update(prune_context *pc, Connector *c,
                           int word_c, int w, bool shallow)
{
	int n;
	bool foundmatch;

	if (c == NULL) return w;
	n = left_connector_list_update(pc, c->next, word_c, w, false) - 1;
	if (((int) c->word) < n) n = c->word;

	/* n is now the rightmost word we need to check */
	foundmatch = false;
	for (; n >= 0 ; n--)
	{
		pc->power_cost++;
		if (right_table_search(pc, n, c, shallow, word_c))
		{
			foundmatch = true;
			break;
		}
	}
	if (n < ((int) c->word))
	{
		c->word = n;
		pc->N_changed++;
	}
	return (foundmatch ? n : -1);
}

/**
 * Take this connector list, and try to match it with the words
 * w+1, w+2, w+3...  Returns the word to which the first connector of
 * the list could possibly be matched.  If c is NULL, returns w.  If
 * there is no way to match this list, it returns a number greater than
 * N_words - 1.   If it does find a way to match it, it updates the
 * c->word fields correctly.
 */
static size_t
right_connector_list_update(prune_context *pc, Sentence sent, Connector *c,
                            size_t word_c, size_t w, bool shallow)
{
	size_t n;
	bool foundmatch;

	if (c == NULL) return w;
	n = right_connector_list_update(pc, sent, c->next, word_c, w, false) + 1;
	if (c->word > n) n = c->word;

	/* n is now the leftmost word we need to check */
	foundmatch = false;
	for (; n < sent->length ; n++)
	{
		pc->power_cost++;
		if (left_table_search(pc, n, c, shallow, word_c))
		{
			foundmatch = true;
			break;
		}
	}
	if (n > c->word) {
		c->word = n;
		pc->N_changed++;
	}<commit_msg>Move the check higher up<commit_after>/*************************************************************************/
/* Copyright (c) 2004                                                    */
/* <NAME>, <NAME>, and <NAME>                    */
/* Copyright (c) 2009, 2013, 2014 <NAME>                          */
/* 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.   */
/*                                                                       */
/*************************************************************************/

#include "api-structures.h"
#include "count.h"
#include "dict-api.h"  /* for print_expression when debugging */
#include "disjunct-utils.h"
#include "externs.h"
#include "post-process.h"
#include "print.h"
#include "prune.h"
#include "resources.h"
#include "string-set.h"
#include "word-utils.h"

#define CONTABSZ 8192
typedef Connector * connector_table;

typedef struct disjunct_dup_table_s disjunct_dup_table;
struct disjunct_dup_table_s
{
	unsigned int dup_table_size;
	Disjunct ** dup_table;
};

/* Indicator that this connector cannot be used -- that its "obsolete".  */
#define BAD_WORD (MAX_SENTENCE+1)

typedef struct c_list_s C_list;
struct c_list_s
{
	C_list * next;
	Connector * c;
	bool shallow;
};

typedef struct power_table_s power_table;
struct power_table_s
{
	unsigned int power_table_size;
	unsigned int *l_table_size;  /* the sizes of the hash tables */
	unsigned int *r_table_size;
	C_list *** l_table;
	C_list *** r_table;
};

typedef struct cms_struct Cms;
struct cms_struct
{
	Cms * next;
	const char * name;
	int count;	  /* the number of times this is in the multiset */
};

#define CMS_SIZE (2<<10)
typedef struct multiset_table_s multiset_table;
struct multiset_table_s
{
	Cms * cms_table[CMS_SIZE];
};

typedef struct prune_context_s prune_context;
struct prune_context_s
{
	bool null_links;
	int power_cost;
	int N_changed;   /* counts the number of changes
						   of c->word fields in a pass */
	power_table *pt;
	Sentence sent;
};

/*

  The algorithms in this file prune disjuncts from the disjunct list
  of the sentence that can be elimininated by a simple checks.  The first
  check works as follows:

  A series of passes are made through the sentence, alternating
  left-to-right and right-to-left.  Consier the left-to-right pass (the
  other is symmetric).  A set S of connectors is maintained (initialized
  to be empty).  Now the disjuncts of the current word are processed.
  If a given disjunct's left pointing connectors have the property that
  at least one of them has no connector in S to which it can be matched,
  then that disjunct is deleted. Now the set S is augmented by the right
  connectors of the remaining disjuncts of that word.  This completes
  one word.  The process continues through the words from left to right.
  Alternate passes are made until no disjunct is deleted.

  It worries me a little that if there are some really huge disjuncts lists,
  then this process will probably do nothing.  (This fear turns out to be
  unfounded.)

  Notes:  Power pruning will not work if applied before generating the
  "and" disjuncts.  This is because certain of it's tricks don't work.
  Think about this, and finish this note later....
  Also, currently I use the standard connector match procedure instead
  of the pruning one, since I know power pruning will not be used before
  and generation.  Replace this to allow power pruning to work before
  generating and disjuncts.

  Currently it seems that normal pruning, power pruning, and generation,
  pruning, and power pruning (after "and" generation) and parsing take
  about the same amount of time.  This is why doing power pruning before
  "and" generation might be a very good idea.

  New idea:  Suppose all the disjuncts of a word have a connector of type
  c pointing to the right.  And further, suppose that there is exactly one
  word to its right containing that type of connector pointing to the left.
  Then all the other disjuncts on the latter word can be deleted.
  (This situation is created by the processing of "either...or", and by
  the extra disjuncts added to a "," neighboring a conjunction.)

*/

/**
 * This hash function only looks at the leading upper case letters of
 * the connector string, and the label fields.  This ensures that if two
 * strings match (formally), then they must hash to the same place.
 */
static inline unsigned int hash_S(Connector * c)
{
	unsigned int h = connector_hash(c);
	return (h & (CONTABSZ-1));
}

static void zero_connector_table(connector_table *ct)
{
	memset(ct, 0, sizeof(Connector *) * CONTABSZ);
}

/**
 * This function puts connector c into the connector table
 * if one like it isn't already there.
 */
static void insert_connector(connector_table *ct, Connector * c)
{
	unsigned int h;
	Connector * e;

	h = hash_S(c);

	for (e = ct[h]; e != NULL; e = e->tableNext)
	{
		if (string_set_cmp(c->string, e->string))
			return;
	}
	c->tableNext = ct[h];
	ct[h] = c;
}

/*
   The second algorithm eliminates disjuncts that are dominated by
   another.  It works by hashing them all, and checking for domination.
*/

#if 0
/* ============================================================x */

/*
  Consider the idea of deleting a disjunct if it is dominated (in terms of
  what it can match) by some other disjunct on the same word.  This has
  been implemented below.  There are three problems with it:

  (1) It is almost never the case that any disjuncts are eliminated.

  (2) connector_matches_alam may not be exactly correct.

  (3) The linkage that is eliminated by this, might just be the one that
      passes post-processing, as the following example shows.
      This is pretty silly, and should probably be changed.

> telling John how our program works would be stupid
Accepted (2 linkages, 1 with no P.P. violations)
  Linkage 1, cost vector = (0, 0, 7)

   +------------------G-----------------+
   +-----R-----+----CL----+             |
   +---O---+   |   +---D--+---S---+     +--I-+-AI-+
   |       |   |   |      |       |     |    |    |
telling.g John how our program.n works would be stupid

               /////         CLg    <---CLg--->  CL      telling.g
 (g)           telling.g     G      <---G----->  G       would
 (g) (d)       telling.g     R      <---R----->  R       how
 (g) (d)       telling.g     O      <---O----->  O       John
 (g) (d)       how           CLe    <---CLe--->  CL      program.n
 (g) (d) (e)   our           D      <---Ds---->  Ds      program.n
 (g) (d) (e)   program.n     Ss     <---Ss---->  Ss      works
 (g)           would         I      <---Ix---->  Ix      be
 (g)           be            AI     <---AIi--->  AIi     stupid

(press return for another)
>
  Linkage 2 (bad), cost vector = (0, 0, 7)

   +------------------G-----------------+
   +-----R-----+----CL----+             |
   +---O---+   |   +---D--+---S---+     +--I-+-AI-+
   |       |   |   |      |       |     |    |    |
telling.g John how our program.n works would be stupid

               /////         CLg    <---CLg--->  CL      telling.g
 (g)           telling.g     G      <---G----->  G       would
 (g) (d)       telling.g     R      <---R----->  R       how
 (g) (d)       telling.g     O      <---O----->  O       John
 (g) (d)       how           CLe    <---CLe--->  CL      program.n
 (g) (d) (e)   our           D      <---Ds---->  Ds      program.n
 (g) (d) (e)   program.n     Ss     <---Ss---->  Ss      works
 (g)           would         I      <---Ix---->  Ix      be
 (g)           be            AI     <---AI---->  AI      stupid

P.P. violations:
      Special subject rule violated
*/

/**
 * hash function that takes a string and a seed value i
 */
static int string_hash(disjunct_dup_table *dt, const char * s, int i)
{
	for(;*s != '\0';s++) i = i + (i<<1) + randtable[(*s + i) & (RTSIZE-1)];
	return (i & (dt->dup_table_size-1));
}

/**
 * This returns true if the connector a matches everything that b
 *  matches, and possibly more.  (alam=at least as much)
 *
 * TRUE for equal connectors.
 * remains TRUE if multi-match added to the first.
 * remains TRUE if subsrcripts deleted from the first.
 */
static bool connector_matches_alam(Connector * a, Connector * b)
{
	char * s, * t, *u;
	if (((!a->multi) && b->multi) ||
		(a->label != b->label))  return false;
	s = a->string;
	t = b->string;

	/* isupper -- connectors cannot be UTF8 at this time */
	while (isupper(*s) || isupper(*t))
	{
		if (*s == *t) {
			s++;
			t++;
		} else return false;
	}
	while ((*s != '\0') && (*t != '\0')) {
		if ((*s == *t) || (*s == '*')) {
			s++;
			t++;
		} else return false;
	}
	while ((*s != '\0') && (*s == '*')) s++;
	return (*s == '\0');
}


/**
 * This hash function that takes a connector and a seed value i.
 * It only looks at the leading upper case letters of
 * the string, and the label.  This ensures that if two connectors
 * match, then they must hash to the same place.
 */
static int conn_hash(Connector * c, int i)
{
	int nb;
	const char * s;
	s = c->string;

	i = i + (i<<1) + randtable[(c->label + i) & (RTSIZE-1)];
	nb = is_utf8_upper(s);
	while (nb)
	{
		i = i + (i<<1) + randtable[(*s + i) & (RTSIZE-1)];
		s += nb;
		nb = is_utf8_upper(s);
	}
	return i;
}

static inline int pconnector_hash(disjunct_dup_table *dt, Connector * c, int i)
{
	i = conn_hash(c, i);
	return (i & (ct->dup_table_size-1));
}

/**
 * This is a hash function for disjuncts
 */
static int hash_disjunct(disjunct_dup_table *dt, Disjunct * d)
{
	int i;
	Connector *e;
	i = 0;
	for (e = d->left ; e != NULL; e = e->next)
	{
		i = pconnector_hash(dt, e, i);
	}
	for (e = d->right ; e != NULL; e = e->next)
	{
		i = pconnector_hash(dt, e, i);
	}
	return string_hash(dt, d->string, i);
}

/**
 * Returns TRUE if disjunct d1 can match anything that d2 can
 * if this happens, it constitutes a proof that there is absolutely
 * no use for d2.
 */
static bool disjunct_matches_alam(Disjunct * d1, Disjunct * d2)
{
	Connector *e1, *e2;
	if (d1->cost > d2->cost) return false;
	e1 = d1->left;
	e2 = d2->left;
	while ((e1!=NULL) && (e2!=NULL))
	{
		if (!connector_matches_alam(e1,e2)) break;
		e1 = e1->next;
		e2 = e2->next;
	}
	if ((e1!=NULL) || (e2!=NULL)) return false;
	e1 = d1->right;
	e2 = d2->right;
	while ((e1!=NULL) && (e2!=NULL))
	{
		if (!connector_matches_alam(e1,e2)) break;
		e1 = e1->next;
		e2 = e2->next;
	}
	if ((e1!=NULL) || (e2!=NULL)) return false;
	return (strcmp(d1->string, d2->string) == 0);
}

/**
 * Takes the list of disjuncts pointed to by d, eliminates all
 * duplicates, and returns a pointer to a new list.
 * It frees the disjuncts that are eliminated.
 */
Disjunct * eliminate_duplicate_disjuncts(Disjunct * d)
{
	int i, h, count;
	Disjunct *dn, *dx, *dxn, *front;
	count = 0;
	disjunct_dup_table *dt;

	dt = disjunct_dup_table_new(next_power_of_two_up(2 * count_disjuncts(d)));

	for (;d!=NULL; d = dn)
	{
		dn = d->next;
		h = hash_disjunct(d);

		front = NULL;
		for (dx = dt->dup_table[h]; dx != NULL; dx = dxn)
		{
			dxn = dx->next;
			if (disjunct_matches_alam(dx,d))
			{
				/* we know that d should be killed */
				d->next = NULL;
				free_disjuncts(d);
				count++;
				front = catenate_disjuncts(front, dx);
				break;
			} else if (disjunct_matches_alam(d,dx)) {
				/* we know that dx should be killed off */
				dx->next = NULL;
				free_disjuncts(dx);
				count++;
			} else {
				/* neither should be killed off */
				dx->next = front;
				front = dx;
			}
		}
		if (dx == NULL) {
			/* we put d in the table */
			d->next = front;
			front = d;
		}
		dt->dup_table[h] = front;
	}

	/* d is now NULL */
	for (i = 0; i < dt->dup_table_size; i++)
	{
		for (dx = dt->dup_table[i]; dx != NULL; dx = dxn)
		{
			dxn = dx->next;
			dx->next = d;
			d = dx;
		}
	}

	if ((verbosity > 2) && (count != 0)) printf("killed %d duplicates\n", count);

	disjunct_dup_table_delete(dt);
	return d;
}

/* ============================================================x */
#endif

/* ================================================================= */
/**
 * Here is expression pruning.  This is done even before the expressions
 * are turned into lists of disjuncts.
 *
 * This uses many of the same data structures and functions that are used
 * by prune.
 *
 * The purge operations remove all irrelevant stuff from the expression,
 * and free the purged stuff.  A connector is deemed irrelevant if its
 * string pointer has been set to NULL.  The passes through the sentence
 * have the job of doing this.
 *
 * If an OR or AND type expression node has one child, we can replace it
 * by its child.  This, of course, is not really necessary, except for
 * performance(?)
 */

static Exp* purge_Exp(Exp *);

/**
 * Get rid of the elements with null expressions
 */
static E_list * or_purge_E_list(E_list * l)
{
	E_list * el;
	if (l == NULL) return NULL;
	if ((l->e = purge_Exp(l->e)) == NULL)
	{
		el = or_purge_E_list(l->next);
		xfree((char *)l, sizeof(E_list));
		return el;
	}
	l->next = or_purge_E_list(l->next);
	return l;
}

/**
 * Returns 0 iff the length of the disjunct list is 0.
 * If this is the case, it frees the structure rooted at l.
 */
static int and_purge_E_list(E_list * l)
{
	if (l == NULL) return 1;
	if ((l->e = purge_Exp(l->e)) == NULL)
	{
		free_E_list(l->next);
		xfree((char *)l, sizeof(E_list));
		return 0;
	}
	if (and_purge_E_list(l->next) == 0)
	{
		free_Exp(l->e);
		xfree((char *)l, sizeof(E_list));
		return 0;
	}
	return 1;
}

/**
 * Must be called with a non-null expression.
 * Return NULL iff the expression has no disjuncts.
 */
static Exp* purge_Exp(Exp *e)
{
	if (e->type == CONNECTOR_type)
	{
		if (e->u.string == NULL)
		{
			xfree((char *)e, sizeof(Exp));
			return NULL;
		}
		else
		{
			return e;
		}
	}
	if (e->type == AND_type)
	{
		if (and_purge_E_list(e->u.l) == 0)
		{
			xfree((char *)e, sizeof(Exp));
			return NULL;
		}
	}
	else /* if we are here, its OR_type */
	{
		e->u.l = or_purge_E_list(e->u.l);
		if (e->u.l == NULL)
		{
			xfree((char *)e, sizeof(Exp));
			return NULL;
		}
	}

/* This code makes it kill off nodes that have just one child
   (1) It's going to give an insignificant speed-up
   (2) Costs have not been handled correctly here.
   The code is excised for these reasons.
*/
/*
	if ((e->u.l != NULL) && (e->u.l->next == NULL))
	{
		ne = e->u.l->e;
		xfree((char *) e->u.l, sizeof(E_list));
		xfree((char *) e, sizeof(Exp));
		return ne;
	}
*/
	return e;
}

/**
 * Returns TRUE if c can match anything in the set S (err. the connector table ct).
 */
static inline bool matches_S(connector_table *ct, Connector * c)
{
	Connector * e;

	for (e = ct[hash_S(c)]; e != NULL; e = e->tableNext)
	{
		if (easy_match(e->string, c->string)) return true;
	}
	return false;
}

/**
 * Mark as dead all of the dir-pointing connectors
 * in e that are not matched by anything in the current set.
 * Returns the number of connectors so marked.
 */
static int mark_dead_connectors(connector_table *ct, Exp * e, char dir)
{
	int count;
	count = 0;
	if (e->type == CONNECTOR_type)
	{
		if (e->dir == dir)
		{
			Connector dummy;
			init_connector(&dummy);
			dummy.string = e->u.string;
			if (!matches_S(ct, &dummy))
			{
				e->u.string = NULL;
				count++;
			}
		}
	}
	else
	{
		E_list *l;
		for (l = e->u.l; l != NULL; l = l->next)
		{
			count += mark_dead_connectors(ct, l->e, dir);
		}
	}
	return count;
}

/**
 * Put into the set S all of the dir-pointing connectors still in e.
 * Return a list of allocated dummy connectors; these will need to be
 * freed.
 */
static Connector * insert_connectors(connector_table *ct, Exp * e,
                                     Connector *alloc_list, int dir)
{
	if (e->type == CONNECTOR_type)
	{
		if (e->dir == dir)
		{
			Connector *dummy = connector_new();
			dummy->string = e->u.string;
			insert_connector(ct, dummy);
			dummy->next = alloc_list;
			alloc_list = dummy;
		}
	}
	else
	{
		E_list *l;
		for (l=e->u.l; l!=NULL; l=l->next)
		{
			alloc_list = insert_connectors(ct, l->e, alloc_list, dir);
		}
	}
	return alloc_list;
}

/**
 * This removes the expressions that are empty from the list corresponding
 * to word w of the sentence.
 */
static void clean_up_expressions(Sentence sent, int w)
{
	X_node head_node, *d, *d1;
	d = &head_node;
	d->next = sent->word[w].x;
	while (d->next != NULL)
	{
		if (d->next->exp == NULL)
		{
			d1 = d->next;
			d->next = d1->next;
			xfree((char *)d1, sizeof(X_node));
		}
		else
		{
			d = d->next;
		}
	}
	sent->word[w].x = head_node.next;
}

/* #define DBG(X) X */
#define DBG(X)

void expression_prune(Sentence sent)
{
	int N_deleted;
	X_node * x;
	size_t w;
	Connector *ct[CONTABSZ];
	Connector *dummy_list = NULL;

	zero_connector_table(ct);

	N_deleted = 1;  /* a lie to make it always do at least 2 passes */

	while (1)
	{
		/* Left-to-right pass */
		/* For every word */
		for (w = 0; w < sent->length; w++)
		{
			/* For every expression in word */
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
DBG(printf("before marking: "); print_expression(x->exp); printf("\n"););
				N_deleted += mark_dead_connectors(ct, x->exp, '-');
DBG(printf(" after marking: "); print_expression(x->exp); printf("\n"););
			}
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
DBG(printf("before purging: "); print_expression(x->exp); printf("\n"););
				x->exp = purge_Exp(x->exp);
DBG(printf("after purging: "); print_expression(x->exp); printf("\n"););
			}

			/* gets rid of X_nodes with NULL exp */
			clean_up_expressions(sent, w);
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
				dummy_list = insert_connectors(ct, x->exp, dummy_list, '+');
			}
		}

		if (verbosity > 2)
		{
			printf("l->r pass removed %d\n", N_deleted);
			print_expression_sizes(sent);
		}

		/* Free the allocated dummy connectors */
		free_connectors(dummy_list);
		dummy_list = NULL;
		zero_connector_table(ct);

		if (N_deleted == 0) break;

		/* Right-to-left pass */
		N_deleted = 0;
		for (w = sent->length-1; w != (size_t) -1; w--)
		{
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
/*	 printf("before marking: "); print_expression(x->exp); printf("\n"); */
				N_deleted += mark_dead_connectors(ct, x->exp, '+');
/*	 printf("after marking: "); print_expression(x->exp); printf("\n"); */
			}
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
/*	 printf("before perging: "); print_expression(x->exp); printf("\n"); */
				x->exp = purge_Exp(x->exp);
/*	 printf("after perging: "); print_expression(x->exp); printf("\n"); */
			}
			clean_up_expressions(sent, w);  /* gets rid of X_nodes with NULL exp */
			for (x = sent->word[w].x; x != NULL; x = x->next)
			{
				dummy_list = insert_connectors(ct, x->exp, dummy_list, '-');
			}
		}

		if (verbosity > 2)
		{
			printf("r->l pass removed %d\n", N_deleted);
			print_expression_sizes(sent);
		}

		/* Free the allocated dummy connectors */
		free_connectors(dummy_list);
		dummy_list = NULL;
		zero_connector_table(ct);
		if (N_deleted == 0) break;
		N_deleted = 0;
	}
}



/*
  Here is what you've been waiting for: POWER-PRUNE

  The kinds of constraints it checks for are the following:

	1) successive connectors on the same disjunct have to go to
	   nearer and nearer words.

	2) two deep connectors cannot attach to each other
	   (A connectors is deep if it is not the first in its list; it
	   is shallow if it is the first in its list; it is deepest if it
	   is the last on its list.)

	3) on two adjacent words, a pair of connectors can be used
	   only if they're the deepest ones on their disjuncts

	4) on two non-adjacent words, a pair of connectors can be used only
	   if not [both of them are the deepest].

   The data structure consists of a pair of hash tables on every word.
   Each bucket of a hash table has a list of pointers to connectors.
   These nodes also store if the chosen connector is shallow.
*/
/*
   As with normal pruning, we make alternate left->right and right->left
   passes.  In the R->L pass, when we're on a word w, we make use of
   all the left-pointing hash tables on the words to the right of w.
   After the pruning on this word, we build the left-pointing hash table
   this word.  This guarantees idempotence of the pass -- after doing an
   L->R, doing another would change nothing.

   Each connector has an integer c_word field.  This refers to the closest
   word that it could be connected to.  These are initially determined by
   how deep the connector is.  For example, a deepest connector can connect
   to the neighboring word, so its c_word field is w+1 (w-1 if this is a left
   pointing connector).  It's neighboring shallow connector has a c_word
   value of w+2, etc.

   The pruning process adjusts these c_word values as it goes along,
   accumulating information about any way of linking this sentence.
   The pruning process stops only after no disjunct is deleted and no
   c_word values change.

   The difference between RUTHLESS and GENTLE power pruning is simply
   that GENTLE uses the deletable region array, and RUTHLESS does not.
   So we can get the effect of these two different methods simply by
   always unsuring that deletable[][] has been defined.  With nothing
   deletable, this is equivalent to RUTHLESS.   --DS, 7/97
*/

/**
 * returns the number of connectors in the left lists of the disjuncts.
 */
static int left_connector_count(Disjunct * d)
{
	Connector *c;
	int i=0;
	for (;d!=NULL; d=d->next) {
		for (c = d->left; c!=NULL; c = c->next) i++;
	}
	return i;
}

static int right_connector_count(Disjunct * d)
{
	Connector *c;
	int i=0;
	for (;d!=NULL; d=d->next) {
	  for (c = d->right; c!=NULL; c = c->next) i++;
	}
	return i;
}

static void free_C_list(C_list * t)
{
	C_list *xt;
	for (; t!=NULL; t=xt) {
		xt = t->next;
		xfree((char *)t, sizeof(C_list));
	}
}

/**
 * free all of the hash tables and C_lists
 */
static void power_table_delete(power_table *pt)
{
	unsigned int w;
	unsigned int i;

	for (w = 0; w < pt->power_table_size; w++)
	{
		for (i = 0; i < pt->l_table_size[w]; i++)
		{
			free_C_list(pt->l_table[w][i]);
		}
		xfree((char *)pt->l_table[w], pt->l_table_size[w] * sizeof (C_list *));

		for (i = 0; i < pt->r_table_size[w]; i++)
		{
			free_C_list(pt->r_table[w][i]);
		}
		xfree((char *)pt->r_table[w], pt->r_table_size[w] * sizeof (C_list *));
	}
	xfree(pt->l_table_size, 2 * pt->power_table_size * sizeof(unsigned int));
	xfree(pt->l_table, 2 * pt->power_table_size * sizeof(C_list **));
	xfree(pt, sizeof(power_table));
}

/**
 * The disjunct d (whose left or right pointer points to c) is put
 * into the appropriate hash table
 */
static void put_into_power_table(unsigned int size, C_list ** t, Connector * c, bool shal)
{
	unsigned int h;
	C_list * m;
	h = connector_hash(c) & (size-1);
	m = (C_list *) xalloc (sizeof(C_list));
	m->next = t[h];
	t[h] = m;
	m->c = c;
	m->shallow = shal;
}

static int set_dist_fields(Connector * c, size_t w, int delta)
{
	int i;
	if (c == NULL) return (int) w;
	i = set_dist_fields(c->next, w, delta) + delta;
	c->word = i;
	return i;
}

/**
 * Allocates and builds the initial power hash tables
 */
static power_table * power_table_new(Sentence sent)
{
	power_table *pt;
	size_t w, len;
	unsigned int i, size;
	C_list ** t;
	Disjunct * d, * xd, * head;
	Connector * c;

	pt = (power_table *) xalloc (sizeof(power_table));
	pt->power_table_size = sent->length;
	pt->l_table_size = xalloc (2 * sent->length * sizeof(unsigned int));
	pt->r_table_size = pt->l_table_size + sent->length;
	pt->l_table = xalloc (2 * sent->length * sizeof(C_list **));
	pt->r_table = pt->l_table + sent->length;

   /* First, we initialize the word fields of the connectors, and
	  eliminate those disjuncts with illegal connectors */
	for (w=0; w<sent->length; w++)
	{
	  head = NULL;
	  for (d=sent->word[w].d; d!=NULL; d=xd) {
		  xd = d->next;
		  if ((set_dist_fields(d->left, w, -1) < 0) ||
			  (set_dist_fields(d->right, w, 1) >= (int) sent->length)) {
			  d->next = NULL;
			  free_disjuncts(d);
		  } else {
			  d->next = head;
			  head = d;
		  }
	  }
	  sent->word[w].d = head;
	}

	for (w=0; w<sent->length; w++)
	{
		/* The below uses variable-sized hash tables. This seems to
		 * provide performance that is equal or better than the best
		 * fixed-size prformance.
		 * The best fixed-size performance seems to come at about
		 * a 1K table size, for both English and Russian. (Both have
		 * about 100 fixed link-types, and many thousands of auto-genned
		 * link types (IDxxx idioms for both, LLxxx suffix links for
		 * Russian).  Plusses and minuses:
		 * + small fixed tables are faster to initialize.
		 * - small fixed tables have more collisions
		 * - variable-size tables require counting connectors.
		 *   (and the more complex code to go with)
		 * CPU cache-size effects ...
		 * Strong depenence on the hashing algo!
		 */
		len = left_connector_count(sent->word[w].d);
		size = next_power_of_two_up(len);
#define TOPSZ 32768
		if (TOPSZ < size) size = TOPSZ;
		pt->l_table_size[w] = size;
		t = pt->l_table[w] = (C_list **) xalloc(size * sizeof(C_list *));
		for (i=0; i<size; i++) t[i] = NULL;

		for (d=sent->word[w].d; d!=NULL; d=d->next) {
			c = d->left;
			if (c != NULL) {
				put_into_power_table(size, t, c, true);
				for (c=c->next; c!=NULL; c=c->next){
					put_into_power_table(size, t, c, false);
				}
			}
		}

		len = right_connector_count(sent->word[w].d);
		size = next_power_of_two_up(len);
		if (TOPSZ < size) size = TOPSZ;
		pt->r_table_size[w] = size;
		t = pt->r_table[w] = (C_list **) xalloc(size * sizeof(C_list *));
		for (i=0; i<size; i++) t[i] = NULL;

		for (d=sent->word[w].d; d!=NULL; d=d->next) {
			c = d->right;
			if (c != NULL) {
				put_into_power_table(size, t, c, true);
				for (c=c->next; c!=NULL; c=c->next){
					put_into_power_table(size, t, c, false);
				}
			}
		}
	}

	return pt;
}

/**
 * This runs through all the connectors in this table, and eliminates those
 * who are obsolete.  The word fields of an obsolete one has been set to
 * BAD_WORD.
 */
static void clean_table(unsigned int size, C_list ** t)
{
	unsigned int i;
	C_list * m, * xm, * head;
	for (i = 0; i < size; i++) {
		head = NULL;
		for (m = t[i]; m != NULL; m = xm) {
			xm = m->next;
			if (m->c->word != BAD_WORD) {
				m->next = head;
				head = m;
			} else {
				xfree((char *) m, sizeof(C_list));
			}
		}
		t[i] = head;
	}
}

/**
 * This takes two connectors (and whether these are shallow or not)
 * (and the two words that these came from) and returns TRUE if it is
 * possible for these two to match based on local considerations.
 */
static bool possible_connection(prune_context *pc,
                               Connector *lc, Connector *rc,
                               bool lshallow, bool rshallow,
                               int lword, int rword)
{
	int dist;
	if ((!lshallow) && (!rshallow)) return false;

	/* Two deep connectors can't work */
	if ((lc->word > rword) || (rc->word < lword)) return false;

	dist = rword - lword;
	// assert(0 < dist, "Bad word order in possible connection.");

	/* Word range constraints */
	if (1 == dist)
	{
		if (!((lc->next == NULL) && (rc->next == NULL))) return false;
	}
	else
	if (dist > lc->length_limit || dist > rc->length_limit)
	{
		return false;
	}
	/* If the words are NOT next to each other, then there must be
	 * at least one intervening connector (i.e. cannot have both
	 * lc->next amnd rc->next being null).  But we only enforce this
	 * when we think its still possible to have a complete parse,
	 * i.e. before well allow null-linked words.
	 */
	else
	if ((!pc->null_links) &&
	    (lc->next == NULL) &&
	    (rc->next == NULL) &&
	    (!lc->multi) && (!rc->multi))
	{
		return false;
	}

	return easy_match(lc->string, rc->string);
}

/**
 * This returns TRUE if the right table of word w contains
 * a connector that can match to c.  shallow tells if c is shallow.
 */
static bool
right_table_search(prune_context *pc, int w, Connector *c,
                   bool shallow, int word_c)
{
	unsigned int size, h;
	C_list *cl;
	power_table *pt;

	pt = pc->pt;
	size = pt->r_table_size[w];
	h = connector_hash(c) & (size-1);
	for (cl = pt->r_table[w][h]; cl != NULL; cl = cl->next)
	{
		if (possible_connection(pc, cl->c, c, cl->shallow, shallow, w, word_c))
		{
			return true;
		}
	}
	return false;
}

/**
 * This returns TRUE if the right table of word w contains
 * a connector that can match to c.  shallows tells if c is shallow
 */
static bool
left_table_search(prune_context *pc, int w, Connector *c,
                  bool shallow, int word_c)
{
	unsigned int size, h;
	C_list *cl;
	power_table *pt;

	pt = pc->pt;
	size = pt->l_table_size[w];
	h = connector_hash(c) & (size-1);
	for (cl = pt->l_table[w][h]; cl != NULL; cl = cl->next)
	{
		if (possible_connection(pc, c, cl->c, shallow, cl->shallow, word_c, w))
			return true;
	}
	return false;
}

/**
 * Take this connector list, and try to match it with the words
 * w-1, w-2, w-3...  Returns the word to which the first connector of
 * the list could possibly be matched.  If c is NULL, returns w.  If
 * there is no way to match this list, it returns a negative number.
 * If it does find a way to match it, it updates the c->word fields
 * correctly.
 */
static int
left_connector_list_update(prune_context *pc, Connector *c,
                           int word_c, int w, bool shallow)
{
	int n, lb;
	bool foundmatch;

	if (c == NULL) return w;
	n = left_connector_list_update(pc, c->next, word_c, w, false) - 1;
	if (((int) c->word) < n) n = c->word;

	/* lb is now the leftmost word we need to check */
	lb = word_c - c->length_limit;
	if (0 > lb) lb = 0;

	/* n is now the rightmost word we need to check */
	foundmatch = false;
	for (; n >= lb ; n--)
	{
		pc->power_cost++;
		if (right_table_search(pc, n, c, shallow, word_c))
		{
			foundmatch = true;
			break;
		}
	}
	if (n < ((int) c->word))
	{
		c->word = n;
		pc->N_changed++;
	}
	return (foundmatch ? n : -1);
}

/**
 * Take this connector list, and try to match it with the words
 * w+1, w+2, w+3...  Returns the word to which the first connector of
 * the list could possibly be matched.  If c is NULL, returns w.  If
 * there is no way to match this list, it returns a number greater than
 * N_words - 1.   If it does find a way to match it, it updates the
 * c->word fields correctly.
 */
static size_t
right_connector_list_update(prune_context *pc, Sentence sent, Connector *c,
                            size_t word_c, size_t w, bool shallow)
{
	size_t n, ub;
	bool foundmatch;

	if (c == NULL) return w;
	n = right_connector_list_update(pc, sent, c->next, word_c, w, false) + 1;
	if (c->word > n) n = c->word;

	/* ub is now the rightmost word we need to check */
	ub = word_c + c->length_limit;
	if (ub > sent->length) ub = sent->length;

	/* n is now the leftmost word we need to check */
	foundmatch = false;
	for (; n < ub ; n++)
	{
		pc->power_cost++;
		if (left_table_search(pc, n, c, shallow, word_c))
		{
			foundmatch = true;
			break;
		}
	}
	if (n > c->word) {
		c->word = n;
		pc->N_changed++;
	}
{'fraction_non_alphanumeric': 0.15140738378119767, 'fraction_numerical': 0.005789012040507136, 'mean_word_length': 2.7198789820252713, 'pattern_counts': {'":': 0, '<': 99, '<?xml version=': 0, '>': 566, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4399376', 'n_tokens_mistral': 23621, 'n_tokens_neox': 21953, 'n_words': 7532}