purge_Exp_1()

/**
 * Find the list head of the given element.
 * (Max. 2 iterations, as this is the max. E_list chain length).
 */
static int find_context(E_list *s[], int i)
{
	/* topmost element is at (i-1) */
	while (i-- >= 0)
	{
		if (s[i]->e->mark) break;
	}

	//assert(i >= 0, "find_context: Internal error\n");
	return i;
}

/**
 * Must be called with a non-null expression.
 * Return NULL iff the expression has no disjuncts.
 */
static Exp* purge_Exp(Exp *e)
{
	E_list exp_head = { NULL, e }; /* make the expression look like E_list */
	bool discard = false; /* discard next element */
	int context;
	int si;
	E_list *s[EXP_STACKSIZE];

	s[0] = &exp_head;
	si = 1;
	e->mark = false; /* see comment at start of loop */

	while (si > 0)
	{
		/* State variables:
		 *
		 * 1. Expression mark field:
		 * If TRUE, it is for operator (AND or OR) context only. An element
		 * so marked is ignored when popped up (unless "discard", see (2)
		 * below). For next expression tree elements - set their mark to
		 * FALSE when pushed (so they will not be ignored).
		 *
		 * 2. Local variable "discard":
		 * If TRUE, the popped up element should be discarded from the
		 * expression tree (along with all of its decedents).
		 *
		 * 3. Local variable "check_nonterminal":
		 * TRUE iff the operands of AND or OR may need further processing
		 * in order to find out if we can discard them.
		 *
		 * 4. Local variable "next_level":
		 * TRUE if there is a need to examine the next level elements.
		 *
		 * Note: Zeroary OR check is not done in order to save CPU,
		 * so it would be discarded if encountered. However, this kind of
		 * construct is not used.
		 */
		E_list *p = pop_elist(s, &si);     /* current E_list */
		Exp *t = p->e;                     /* current expression */

		bool next_level;                   /* push the next level elements */
		if (t->type == CONNECTOR_type)
		{
			if (NULL == t->u.condesc)
			{
				discard = true;
				next_level = false;
			}
		}
		else if (!discard)
		{
			if (t->mark) continue;
			bool check_nonterminal = false;

			if (AND_type == t->type)
			{
				if (NULL == t->u.l)
				{
					next_level = false; /* Zeroary AND */
				}
				else
				{
					for (E_list *l = t->u.l; l != NULL; l = l->next)
					{
						if (CONNECTOR_type == l->e->type)
						{
							if (NULL == l->e->u.condesc)
							{
								discard = true; /* discarded connector */
								break;
							}
						}
						else
						{
							check_nonterminal = true;
						}
					}
					next_level = !discard && check_nonterminal;
				}
			}
			else /* OR_type */
			{
				discard = true;
				for (E_list *l = t->u.l; l != NULL; l = l->next)
				{
					if (CONNECTOR_type == l->e->type)
					{
						if (NULL != l->e->u.condesc)
						{
							discard = false; /* not a discarded connector */
						}
					}
					else
					{
						check_nonterminal = true;
						discard = false; /* not a discarded connector */
					}
				}
				next_level = !discard || check_nonterminal;
			}

			if (next_level)
			{
				context = si;
				/* Retain the nonterminal in the stack for operator context. */
				t->mark = true;
				push_elist(s, &si, p);
				/* Push its E_list elements. */
				for (E_list *l = t->u.l; l != NULL; l = l->next)
				{
					l->e->mark = false;
					push_elist(s, &si, l);
				}
			}
		}

		if (discard)
		{
			/* Discard the E_List element "p" ("t" is its expression). */
			if (0 == si)
			{
				/* The topmost element has been discarded. */
				free_Exp(t);
				e = NULL;
				break;
			}

			/* Find the root of this E_list. */
			if (context >= si)
				context = find_context(s, si); /* recompute a stale context */
			E_list *root = pick_elist(s, context);

			if (OR_type == root->e->type)
			{
				/* Discard the element; first skip it, then free it. */
				E_list *el = pick_elist(s, si-1); /* previous element */
				E_list **n = (si-1 == context) ? &el->e->u.l : &el->next;
				*n = p->next;       /* skip the current element */
				if (CONNECTOR_type == t->type)
				{
					/* free_E_list() is too heavy for freeing just one element .*/
					free(t);
					free(p);
				}
				else
				{
					free_E_list(p);
				}

				if (NULL != root->e->u.l) /* an OR operand exists ... */
					discard = false; /* hence do not discard the OR root */
			}
			/* Else it is AND, and discard==true is propagated. */
		}
	}

	return e;
}