/*
 * ???():
 *   If you belong to the group where do you belong only in the case you belong
 *   in that group, do you in fact belong to that group or don't?
 *   I've decided it is safer to decide that you DON'T belong to such group.
 *
 * expr_eval_notify_expr_remove():
 *   If someone was interested in what am I like but she is no longer
 *   interested in what am I like, because she already knows what is she like,
 *   then she should tell it me, as although I still may not know what am I
 *   like then in the case she was the last who wanted to know what am I like,
 *   I should tell everyone who I didn't know what they are like and I wanted
 *   to know what they are like that I no longer want to know what they are
 *   like, because it is no longer needed to know what am I like about myself.
 *
 * membership_eval_immediate():
 *   It is important to not only know, what do you want to know, but it is also
 *   important to know what do you now know but you still didn't utilize it.
 */


#include "tac_plus.h"

#include <stdlib.h>

#include "cfgeval.h"
#include "cfgfile.h"
#include "main.h"
#include "parse.h"
#include "report.h"
#include "hash.h"


/* Configurable:
 */

/* Whether to do sanity checks */
#define SCAN_PARANOIA 1

/* report even no-op scan up-to-date checks */
#define REPORT_CHECK_SCAN_VERBOSE 0


static void check_request_scan_membership TAC_ARGS((struct membership *membership, int flush));
static void check_eval_scan_membership TAC_ARGS((struct membership *membership, int flush));
static void check_eval_scan_entity TAC_ARGS((ENTITY *entity, int flush));
static void check_request_scan_expr TAC_ARGS((struct expr *expr, int flush));
static void check_eval_scan_expr TAC_ARGS((struct expr *expr, int flush));


static unsigned request_scan_seq = 0;
static unsigned value_scan_seq = 0;
static unsigned eval_scan_seq = 0;
int request_scan_user_known;
static struct tac_list eval_kicked_entity_list;
static struct tac_list eval_destroy_entity_list;
static struct tac_list eval_notified_expr_list;
static struct tac_list request_virtual_membership_list;


/* 'P[FA]_*' object printing section:
 */

static const char *eval_result_to_string TAC_ARGS((int valid, enum eval_result er));

const char *
eval_result_to_string(valid, er)
int valid;
enum eval_result er;
{
    if (!valid)
	return ("!UPDATED");

    switch (er) {
    case ER_TRUE:    return ("ER_TRUE"        );
    case ER_FALSE:   return ("ER_FALSE"       );
    case ER_UNKNOWN: return ("ER_UNKNOWN"     );
    default:         return ("*** INVALID ***");
    }
    /* NOTREACHED */
}

static const char *value_scan_func_result_to_string TAC_ARGS((enum value_scan_func_result vsfr));

const char *
value_scan_func_result_to_string(vsfr)
enum value_scan_func_result vsfr;
{
    switch (vsfr) {
    case VSFR_CONTINUE: return ("VSFR_CONTINUE");
    case VSFR_FOUND:    return ("VSFR_FOUND"   );
    case VSFR_STOP:     return ("VSFR_STOP"    );
    default:            return ("*** INVALID ***");
    }
    /* NOTREACHED */
}

/* These macros are VERY big overhead but it's primary negative effect
 * is the size of executable. I've considered it as not much interesting,
 * CPU overhead is hit only when DEBUG_CFGEVAL_FLAG (also not interesting).
 */

#define PF_VSFR       "%s"
#define PA_VSFR(vsfr) (value_scan_func_result_to_string((vsfr)))

#define PF_RESULT         "%s"
#define PA_RESULT(result) (eval_result_to_string(1 /* valid */, (result)))

#define PF_ERESULT_struct         PF_RESULT
#define PA_ERESULT_struct(entity, field) \
	(!(entity) ? "*NULL*(=ER_TRUE)" : \
		(eval_result_to_string((entity)->request_scan.seq == request_scan_seq, (entity)->request_scan.field)))
#define PA_ERESULT_struct_NULL    "*NULL*"

#define PF_ERESULT_EXPR       PF_ERESULT_struct
#define PA_ERESULT_EXPR(expr) PA_ERESULT_struct((expr), result)
#define PF_ERESULT_ENTITY         PF_ERESULT_struct
#define PA_ERESULT_ENTITY(entity) PA_ERESULT_struct((entity), belongs)
#define PF_ERESULT_MEMBERSHIP             PF_ERESULT_struct
#define PA_ERESULT_MEMBERSHIP(membership) (!(membership) ? PA_ERESULT_struct_NULL : PA_ERESULT_EXPR((membership)->when))

#define PF_EXPR_       "expr@%d{%s " PF_MEMBERSHIP "}"
#define PA_EXPR_(expr) (!(expr) ? 0        : (expr)->line), \
                       (!(expr) ? "*NULL*" : "of"), \
                       PA_MEMBERSHIP((!(expr) ? NULL : (expr)->membership))

#define PF_MEMBERSHIP_             "membership{child=" PF_ENTITY ",parent=" PF_ENTITY "}"
#define PA_MEMBERSHIP_(membership) PA_ENTITY((!(membership) ? NULL : MEMBERSHIP_TO_CHILD_ENTITY( (membership)))), \
                                   PA_ENTITY((!(membership) ? NULL : MEMBERSHIP_TO_PARENT_ENTITY((membership))))

#define PF_ENTITY_         "{%s@%d \"%s\"}"
#define PA_ENTITY_(entity) (!(entity) ? "*NULL* entity" : entity_type_to_string((entity)->type)), \
                           (!(entity) ? 0               : (entity)->line), \
                           (!(entity) ? "*NULL*"        : (entity)->name)

#define PF_EXPR       PF_EXPR_ "=" PF_ERESULT_EXPR
#define PA_EXPR(expr) PA_EXPR_(expr), PA_ERESULT_EXPR(expr)
#define PF_MEMBERSHIP             PF_MEMBERSHIP_ "=" PF_ERESULT_MEMBERSHIP
#define PA_MEMBERSHIP(membership) PA_MEMBERSHIP_(membership), PA_ERESULT_MEMBERSHIP(membership)
#define PF_ENTITY         PF_ENTITY_ "=" PF_ERESULT_ENTITY
#define PA_ENTITY(entity) PA_ENTITY_(entity), PA_ERESULT_ENTITY(entity)


/* '{unlink,free}_*()' section:
 */

void unlink_expr TAC_ARGS((struct expr *expr));

/* never depend on "->parent" as it may not yet been filled! */
void
unlink_expr(expr)
struct expr *expr;
{
    if (!expr)
	return;		/* prevent possible DEBUG_CLEAN_FLAG report */

    if (debug & DEBUG_CLEAN_FLAG) {
	if (expr->membership)
	    report(LOG_DEBUG, "unlink_expr: (of membership): " PF_EXPR,
		    PA_EXPR(expr));
	else
	    report(LOG_DEBUG, "unlink_expr: (standalone)");
    }

    while (expr) {

	/* We need to at least unlink "eval_scan->u.entity.notify_expr_node": */
	check_request_scan_expr(expr, 1);	/* invalidate */
	check_eval_scan_expr(expr, 1);		/* invalidate */

	switch (expr->type) {

	case S_not:
	    unlink_expr(expr->u.not.child);
	    break;

	case S_and:
	case S_or:
	    unlink_expr(expr->u.and_or.child_first);
	    break;

	case S_user:
	case S_host:
	case S_group:
	    break;

	default:
	    report(LOG_ERR, "Illegal node type %d for unlink_expr", expr->type);
	    return;
	}

	expr = expr->next;
    }
}

void free_expr TAC_ARGS((struct expr *expr));

/* given 'expr' memory WILL be freed! */
/* never depend on "->parent" as it may not yet been filled! */
void
free_expr(expr)
struct expr *expr;
{
struct expr *expr_next;

    if (!expr)
	return;		/* prevent possible DEBUG_CLEAN_FLAG report */

    if (debug & DEBUG_CLEAN_FLAG)
	report(LOG_DEBUG, "free_expr: (may be unlinked)");

    while (expr) {
    	expr_next = expr->next;
	switch (expr->type) {

	case S_not:
	    free_expr(expr->u.not.child);
	    break;

	case S_and:
	case S_or:
	    free_expr(expr->u.and_or.child_first);
	    break;

	case S_user:
	case S_host:
	case S_group:
	    if (expr->u.entity.name)
	    	free((/* de-const */ char *)expr->u.entity.name);
	    /* "expr->u.entity.entity" will be freed from elsewhere */
	    break;

	default:
	    report(LOG_ERR, "Illegal node type %d for free_expr", expr->type);
	    return;
	}

	free(expr);
	expr=expr_next;
    }
}

static void unlink_membership TAC_ARGS((struct membership *membership));

static void
unlink_membership(membership)
struct membership *membership;
{
    ENTITY *parent_entity;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "unlink_membership: " PF_MEMBERSHIP,
		PA_MEMBERSHIP(membership));

    parent_entity = MEMBERSHIP_TO_PARENT_ENTITY(membership);

    /* 'unlink_expr()' may want a lot of existing (linked) resources */
    unlink_expr(membership->when);

    check_request_scan_membership(membership, 1);	/* invalidate */
    check_eval_scan_membership(membership, 1);		/* invalidate */

#ifdef SCAN_PARANOIA
    if (!parent_entity->to_child_membership_num) {
	report(LOG_ERR, "INTERNAL: to_child_membership_num-- == 0 in unlink_membership");
	parent_entity->to_child_membership_num++;
    }
#endif
    parent_entity->to_child_membership_num--;

    tac_list_node_remove(&membership->parent_node);
    tac_list_node_remove(&membership-> child_node);
}

/* given 'membership' memory WILL be freed! */

static void free_membership TAC_ARGS((struct membership *membership));

static void
free_membership(membership)
struct membership *membership;
{
    if (debug & DEBUG_CLEAN_FLAG)
	report(LOG_DEBUG, "free_membership: (may be unlinked)");

    free_expr(membership->when);
    free(membership);
}

/* we are not allowed to free memory here, we are only 'scan_' additional 'free' */

void scan_free_entity TAC_ARGS((ENTITY *entity));

void
scan_free_entity(entity)
ENTITY *entity;
{
    struct tac_list_node *parent_membership_node, *next_parent_membership_node;
    struct membership *parent_membership;
    struct tac_list_node *child_membership_node, *next_child_membership_node;
    struct membership *child_membership;

    if (debug & DEBUG_CLEAN_FLAG)
	report(LOG_DEBUG, "scan_free_entity: " PF_ENTITY,
		PA_ENTITY(entity));

    /* Be careful to keep '->next' ptr before we destroy the structure! */

    for (
	    parent_membership_node = tac_list_first_node(&entity->to_child_membership_list);
	    parent_membership_node;
	    parent_membership_node = next_parent_membership_node
	    ) {
	parent_membership = PARENT_NODE_TO_MEMBERSHIP(parent_membership_node);
	next_parent_membership_node = tac_list_node_next(parent_membership_node);
	unlink_membership(parent_membership);
	free_membership(parent_membership);
    }
    for (
	    child_membership_node = tac_list_first_node(&entity->to_parent_membership_list);
	    child_membership_node;
	    child_membership_node = next_child_membership_node
	    ) {
	child_membership = CHILD_NODE_TO_MEMBERSHIP(child_membership_node);
	next_child_membership_node = tac_list_node_next(child_membership_node);
	unlink_membership(child_membership);
	free_membership(child_membership);
    }
}

struct expr *new_expr TAC_ARGS((int type));

struct expr *
new_expr(type)
int type;
{
    struct expr *expr;

    expr = (struct expr *) tac_malloc(sizeof(struct expr));
    expr->next = NULL;
    expr->type = type;
    switch (expr->type) {

    case S_not:
	expr->u.not.child = NULL;
	break;

    case S_and:
    case S_or:
	expr->u.and_or.child_first = NULL;
	break;

    case S_user:
    case S_host:
    case S_group:
	expr->u.entity.entity = NULL;
	break;

    default:
	report(LOG_ERR, "Illegal node type %d for new_expr", expr->type);
	return (expr);	/* it would be probably lethal to return NULL */
    }
    return (expr);
}

static int expr_sink_internal TAC_ARGS((struct expr *expr, struct membership *membership, struct expr *parent));

static int
expr_sink_internal(expr, membership, parent)
struct expr *expr;
struct membership *membership;
struct expr *parent;
{
    for (;expr; expr=expr->next) {
	expr->membership = membership;
	expr->parent = parent;
	expr->request_scan.seq = request_scan_seq-1;
	expr->   eval_scan.seq =    eval_scan_seq-1;
	switch (expr->type) {

	case S_not:
	    if (expr_sink_internal(expr->u.not.child, membership, expr /* parent */))
		return (1);
	    break;

	case S_and:
	case S_or:
	    if (expr_sink_internal(expr->u.and_or.child_first, membership, expr /* parent */))
		return (1);
	    break;

	case S_user:
	case S_host:
	case S_group:
	    tac_list_node_init(&expr->eval_scan.u.entity.notify_expr_node);
	    expr->u.entity.entity = entity_lookup(expr->type, expr->u.entity.name);
	    if (!expr->u.entity.entity && expr->type == S_host) {
		expr->u.entity.entity = new_entity(expr->type, (char *)expr->u.entity.name, expr->line);
		if (!expr->u.entity.entity)
		    return (1);
		expr->u.entity.name = NULL;
	    }
	    if (!expr->u.entity.entity) {
		report(LOG_ERR, "referenced entity %s %s not found on line %d",
			entity_type_to_string(expr->type), expr->u.entity.name, expr->line);
		return (1);
	    }
	    /* already NULLed for not-yet-existing S_host */
	    free((char *) expr->u.entity.name);
	    expr->u.entity.name = NULL;
	    break;

	default:
	    report(LOG_ERR, "Illegal node type %d for expr_sink", expr->type);
	    return (1);
	}
    }
    return (0);
}

static int expr_sink TAC_ARGS((struct expr *expr, struct membership *membership));

static int
expr_sink(expr, membership)
struct expr *expr;
struct membership *membership;
{
    return (expr_sink_internal(expr, membership, NULL /* parent */));
}

static struct expr *expr_sink_register_head = NULL;

void expr_sink_register TAC_ARGS((struct expr *expr));

void
expr_sink_register(expr)
struct expr *expr;
{
    if (!expr)
	return;

    expr->parent = expr_sink_register_head;
    expr_sink_register_head = expr;
}

int expr_sink_commit TAC_ARGS((void));

int
expr_sink_commit()
{
    struct expr *expr;

    while ((expr = expr_sink_register_head)) {
	expr_sink_register_head = expr->parent;
	/* 'expr->parent' not defined for 'expr_sink()' */

	if (expr_sink(expr, NULL /* membership */))
	    return (1);		/* failure */
    }
    return (0);		/* success */
}

struct expr *dupl_expr TAC_ARGS((const struct expr *in));

struct expr *
dupl_expr(in)
const struct expr *in;
{
    struct expr *expr_root = NULL;
    struct expr **succ_exprp = &expr_root;
    struct expr *expr;

    for (;in; in=in->next) {
	expr = (struct expr *) tac_malloc(sizeof(struct expr));
	expr->line = in->line;
	expr->next = NULL;
	expr->type = in->type;
	switch (in->type) {

	case S_not:
	    if (in->u.not.child && in->u.not.child->type==S_not) {
		free(expr);
		expr = dupl_expr(in->u.not.child->u.not.child);
	    } else
		expr->u.not.child = dupl_expr(in->u.not.child);
	    break;

	case S_and:
	case S_or:
	    if (!in->u.and_or.child_first) {
		free(expr);
		continue;
	    } else if (!in->u.and_or.child_first->next) {
		free(expr);
		expr = dupl_expr(in->u.and_or.child_first);
	    } else
		expr->u.and_or.child_first = dupl_expr(in->u.and_or.child_first);
	    break;

	case S_user:
	case S_host:
	case S_group:
	    if (in->u.entity.name)
		expr->u.entity.name = tac_strdup(in->u.entity.name);
	    else
	    	expr->u.entity.name = NULL;
	    expr->u.entity.entity = in->u.entity.entity;
	    break;

	default:
	    report(LOG_ERR, "Illegal node type %d for dupl_expr", in->type);
	    free_expr(expr_root);
	    return (NULL);
	}

	*succ_exprp = expr;
	succ_exprp = &expr->next;
    }
    return (expr_root);
}


/* 'check_*_scan_*()' section:
 */

static void check_request_scan_expr TAC_ARGS((struct expr *expr, int flush));

static void
check_request_scan_expr(expr, flush)
struct expr *expr;
int flush;
{
#if REPORT_CHECK_SCAN_VERBOSE
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_request_scan_expr: " PF_EXPR " (" PF_ERESULT_EXPR ")",
		PA_EXPR(expr), PA_ERESULT_EXPR(expr));
#endif

    if (!flush && expr->request_scan.seq == request_scan_seq)
	return;		/* up to date */

    expr->request_scan.result = ER_UNKNOWN;
    expr->request_scan.loop_reported = 0;
    expr->request_scan.seq = request_scan_seq;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_request_scan_expr: done: " PF_EXPR,
		PA_EXPR(expr));
}

static void check_eval_scan_expr TAC_ARGS((struct expr *expr, int flush));

static void
check_eval_scan_expr(expr, flush)
struct expr *expr;
int flush;
{
#if REPORT_CHECK_SCAN_VERBOSE
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_eval_scan_expr: " PF_EXPR,
		PA_EXPR(expr));
#endif

    if (!flush && expr->eval_scan.seq == eval_scan_seq)
	return;		/* up to date */
    check_request_scan_expr(expr, 0);

    switch (expr->type) {

    case S_user:
    case S_host:
    case S_group: {
#ifdef SCAN_PARANOIA
	       if (tac_list_node_get_list(&expr->eval_scan.u.entity.notify_expr_node) == &eval_notified_expr_list) {
	    report(LOG_ERR, "INTERNAL: expr still connected to eval_notified_expr_list in check_eval_scan_expr");
	} else if (tac_list_node_get_list(&expr->eval_scan.u.entity.notify_expr_node)) {
	    ENTITY *notifying_entity = EXPR_ENTITY_TO_NOTIFYING_ENTITY(expr);

	    if (notifying_entity != expr->u.entity.entity)
		report(LOG_ERR, "INTERNAL: expr->notify_expr_node->list != expr->entity");
	    if (notifying_entity->eval_scan.seq != expr->eval_scan.seq)
		report(LOG_ERR, "INTERNAL: entity seq != expr node seq");
	    tac_list_node_remove(&expr->eval_scan.u.entity.notify_expr_node);
	    }
#else /* SCAN_PARANOIA */
	tac_list_node_init(&expr->eval_scan.u.entity.notify_expr_node);
#endif /* SCAN_PARANOIA */
	} break;
    }

    expr->eval_scan.seq = eval_scan_seq;	/* used above, keep as LAST! */

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_eval_scan_expr: done: " PF_EXPR,
		PA_EXPR(expr));
}

static void check_request_scan_membership TAC_ARGS((struct membership *membership, int flush));

static void
check_request_scan_membership(membership, flush)
struct membership *membership;
int flush;
{
#if REPORT_CHECK_SCAN_VERBOSE
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_request_scan_membership: " PF_MEMBERSHIP " (" PF_ERESULT_MEMBERSHIP ")",
		PA_MEMBERSHIP(membership), PA_ERESULT_MEMBERSHIP(membership));
#endif

    if (!flush && membership->request_scan.seq == request_scan_seq)
	return;		/* up to date */

#ifdef SCAN_PARANOIA
    {
        struct tac_list *virtual_list = tac_list_node_get_list(&membership->request_scan.virtual_membership_node);

        if (virtual_list && virtual_list != &request_virtual_membership_list)
	    report(LOG_ERR, "Illegal list in membership->virtual_membership_node.list");
	if (virtual_list)
	    tac_list_node_remove(&membership->request_scan.virtual_membership_node);
    }
#else /* SCAN_PARANOIA */
    tac_list_node_init(&membership->request_scan.virtual_membership_node);
#endif /* SCAN_PARANOIA */

    membership->request_scan.seq = request_scan_seq;	/* used above, keep as LAST! */

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_request_scan_membership: done: " PF_MEMBERSHIP,
		PA_MEMBERSHIP(membership));
}

/* we are cross-checking (membership<->parent entity)! */

static void check_eval_scan_membership TAC_ARGS((struct membership *membership, int flush));

static void
check_eval_scan_membership(membership, flush)
struct membership *membership;
int flush;
{
#if REPORT_CHECK_SCAN_VERBOSE
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_eval_scan_membership: " PF_MEMBERSHIP,
		PA_MEMBERSHIP(membership));
#endif

    if (!flush && membership->eval_scan.seq == eval_scan_seq)
	return;		/* up to date */
    check_request_scan_membership(membership, 0);

    membership->eval_scan.unsolved = 1;
    membership->eval_scan.seq = eval_scan_seq;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_eval_scan_membership: done: " PF_MEMBERSHIP,
		PA_MEMBERSHIP(membership));
}

static void check_request_scan_entity TAC_ARGS((ENTITY *entity, int flush));

static void
check_request_scan_entity(entity, flush)
ENTITY *entity;
int flush;
{
#if REPORT_CHECK_SCAN_VERBOSE
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_request_scan_entity: " PF_ENTITY " (" PF_ERESULT_ENTITY ")",
		PA_ENTITY(entity), PA_ERESULT_ENTITY(entity));
#endif

    if (!flush && entity->request_scan.seq == request_scan_seq)
	return;

    entity->request_scan.belongs = ER_UNKNOWN;
    entity->request_scan.seq = request_scan_seq;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_request_scan_entity: done: " PF_ENTITY,
		PA_ENTITY(entity));
}

static void check_value_scan_entity TAC_ARGS((ENTITY *entity, int flush));

static void
check_value_scan_entity(entity, flush)
ENTITY *entity;
int flush;
{
#if REPORT_CHECK_SCAN_VERBOSE
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_value_scan_entity: " PF_ENTITY,
		PA_ENTITY(entity));
#endif

    if (!flush && entity->value_scan.seq == value_scan_seq)
	return;
    check_request_scan_entity(entity, 0);

    entity->value_scan.seen = 0;
    entity->value_scan.from = NULL;
    entity->value_scan.seq = value_scan_seq;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_value_scan_entity: done: " PF_ENTITY,
		PA_ENTITY(entity));
}

static void check_eval_scan_entity TAC_ARGS((ENTITY *entity, int flush));

static void
check_eval_scan_entity(entity, flush)
ENTITY *entity;
int flush;
{
    struct tac_list_node *child_membership_parent_node;

#if REPORT_CHECK_SCAN_VERBOSE
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_eval_scan_entity: " PF_ENTITY,
		PA_ENTITY(entity));
#endif

    if (!flush && entity->eval_scan.seq == eval_scan_seq)
	return;		/* up to date */
    check_value_scan_entity(entity, 0);

    entity->eval_scan.unsolved_to_child_membership_num = entity->to_child_membership_num;

    if ((child_membership_parent_node = tac_list_first_node(&entity->to_child_membership_list))) {
	struct membership *child_membership = PARENT_NODE_TO_MEMBERSHIP(child_membership_parent_node);

	entity->eval_scan.unsolved_to_child_membership_first = child_membership;
    } else
	entity->eval_scan.unsolved_to_child_membership_first = NULL;

#ifdef SCAN_PARANOIA
    {
	struct tac_list_node *notify_expr_node;

	while ((notify_expr_node = tac_list_first_node(&entity->eval_scan.notify_expr_list))) {
	    struct expr *notify_expr = NOTIFY_EXPR_NODE_TO_EXPR(notify_expr_node);

	    if (notify_expr->u.entity.entity != entity)
		report(LOG_ERR, "INTERNAL: notify_expr->entity != entity");
	    if (notify_expr->eval_scan.seq != entity->eval_scan.seq)
		report(LOG_ERR, "INTERNAL: notify_expr seq != entity seq");
	    tac_list_node_remove(notify_expr_node);
	}

	if (tac_list_node_get_list(&entity->eval_scan.pending_entity_node))
	    tac_list_node_remove(&entity->eval_scan.pending_entity_node);
    }
#else /* SCAN_PARANOIA */
    tac_list_init(&entity->eval_scan.notify_expr_list);
    tac_list_node_init(&entity->eval_scan.pending_entity_node);
#endif /* SCAN_PARANOIA */

    entity->eval_scan.seq = eval_scan_seq;	/* used above, keep as LAST! */

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "check_eval_scan_entity: done: " PF_ENTITY,
		PA_ENTITY(entity));
}


/* invalidation managing section (for '*_scan_begin()'):
 */

/* this will happen once upon 'unsigned' overflow, ehm */

#define INVALIDATE_SEQ_PTR(object,ptr) \
    (G_STRUCT_MEMBER(unsigned, ptr, invalidate_scan_##object##_table[what]) = (unsigned) -1)
#define INVALIDATE_SEQ(object) \
    (INVALIDATE_SEQ_PTR(object,object))

static const long invalidate_scan_expr_table[IS_MAX]={
    G_STRUCT_OFFSET(struct expr, request_scan.seq),
    -1,
    G_STRUCT_OFFSET(struct expr,    eval_scan.seq)};

static void invalidate_scan_expr TAC_ARGS((struct expr *expr,enum invalidate_scan what));

static void
invalidate_scan_expr(expr_single, what)
struct expr *expr_single;
enum invalidate_scan what;
{
    struct expr *expr_parent, *expr_child;

    if (!expr_single) {
	report(LOG_ERR, "INTERNAL: NULL input expressions not support by invalidate_scan_expr");
	return;
    }
    if (expr_single->parent) {
	report(LOG_ERR, "INTERNAL: non-root expressions not supported by invalidate_scan_expr");
	return;
    }

    /* TOP->DOWN scanner: */
top_down:
    do {
	INVALIDATE_SEQ_PTR(expr,expr_single);
	expr_parent = expr_single;

	switch (expr_parent->type) {

	case S_not:
	    expr_child = expr_parent->u.not.child;
	    continue;

	case S_and:
	case S_or:
	    expr_child = expr_parent->u.and_or.child_first;
	    break;

	case S_user:
	case S_host:
	case S_group:
	    expr_child = NULL;	/* no child exists */
	    break;

	default:
	    report(LOG_ERR, "Illegal child node type %d for invalidate_scan_expr", expr_parent->type);
	    return;
	}
    } while ((expr_single = expr_child));
    /* expr_child==NULL, we have only expr_parent: */

    expr_child = expr_parent;

    /* we have only expr_child: */
    /* BOTTOM->UP scanner */
    do {
        if ((expr_single = expr_child->next))
	    goto top_down;
	expr_parent = expr_child->parent;
    } while ((expr_child = expr_parent));
}

static const long invalidate_scan_membership_table[IS_MAX]={
    G_STRUCT_OFFSET(struct membership, request_scan.seq),
    -1,
    G_STRUCT_OFFSET(struct membership,    eval_scan.seq)};

static void invalidate_scan_membership TAC_ARGS((struct membership *membership,enum invalidate_scan what));

static void
invalidate_scan_membership(membership, what)
struct membership *membership;
enum invalidate_scan what;
{
    INVALIDATE_SEQ(membership);

    if (membership->when)
	invalidate_scan_expr(membership->when, what);
}

static const long invalidate_scan_entity_table[IS_MAX]={
    G_STRUCT_OFFSET(ENTITY, request_scan.seq),
    G_STRUCT_OFFSET(ENTITY,   value_scan.seq),
    G_STRUCT_OFFSET(ENTITY,    eval_scan.seq)};

static void invalidate_scan_entity TAC_ARGS((ENTITY *entity,enum invalidate_scan what));

static void
invalidate_scan_entity(entity, what)
ENTITY *entity;
enum invalidate_scan what;
{
    struct tac_list_node *child_membership_node;
    struct membership *child_membership;

    INVALIDATE_SEQ(entity);

    if (what==IS_VALUE)		/* optimalization */
	return;

    for (
	    child_membership_node = tac_list_first_node(&entity->to_child_membership_list);
	    child_membership_node;
	    child_membership_node = tac_list_node_next(&child_membership->parent_node)
	    ) {
	child_membership = PARENT_NODE_TO_MEMBERSHIP(child_membership_node);
	invalidate_scan_membership(child_membership, what);
    }
}

void scan_invalidate_entities_hashtable TAC_ARGS((void **hashtable, enum invalidate_scan what));

void
scan_invalidate_entities_hashtable(hashtable, what)
void **hashtable;
enum invalidate_scan what;
{
    int i;
    ENTITY *entity;

    for (i = 0; i < HASH_TAB_SIZE; i++)
	for (entity = (ENTITY *) hashtable[i]; entity; entity = entity->hash)
	    invalidate_scan_entity(entity, what);
}

/* '*_scan_begin()' section:
 */

void request_scan_begin TAC_ARGS((void));

void
request_scan_begin()
{
#ifdef SCAN_PARANOIA
    static int inited = 0;
#endif /* SCAN_PARANOIA */

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "request_scan_begin:");

    request_scan_user_known = 0;

    if (!++request_scan_seq)
	scan_invalidate_entities(IS_REQUEST);

#ifdef SCAN_PARANOIA
    if (!inited) {
#endif /* SCAN_PARANOIA */
	tac_list_init(&request_virtual_membership_list);
#ifdef SCAN_PARANOIA
	inited = 1;
    } else {
	struct tac_list_node *virtual_membership_node;

	while ((virtual_membership_node = tac_list_first_node(&request_virtual_membership_list))) {
	    struct membership *virtual_membership = VIRTUAL_MEMBERSHIP_NODE_TO_MEMBERSHIP(virtual_membership_node);

	    if (virtual_membership->request_scan.seq == request_scan_seq)
		report(LOG_ERR, "INTERNAL: request_virtual_membership_list membership seq == ++request_scan_seq in request_scan_begin");
	    tac_list_node_remove(virtual_membership_node);
	    unlink_membership(virtual_membership);
	    free_membership(virtual_membership);
	    }
    }
#endif /* SCAN_PARANOIA */
}

static void value_scan_begin TAC_ARGS((ENTITY *entity));

static void
value_scan_begin(entity)
ENTITY *entity;
{
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "value_scan_begin:");

    if (!++value_scan_seq)
	scan_invalidate_entities(IS_VALUE);

    check_value_scan_entity(entity, 0);	/* sure as seq invalidated */
    /* assumed (entity->value_scan.from == NULL) */
}

#ifdef SCAN_PARANOIA

static void eval_scan_begin_pending_entity_node TAC_ARGS((struct tac_list_node *pending_entity_node));

static void
eval_scan_begin_pending_entity_node(pending_entity_node)
struct tac_list_node *pending_entity_node;
{
    ENTITY *pending_entity = PENDING_ENTITY_NODE_TO_ENTITY(pending_entity_node);

    if (pending_entity->eval_scan.seq == eval_scan_seq)
	report(LOG_ERR, "INTERNAL: eval_{pending}_entity_list entity seq == ++eval_scan_seq in eval_scan_begin");

    tac_list_node_remove(pending_entity_node);
}

#endif /* SCAN_PARANOIA */

static void eval_scan_begin TAC_ARGS((void));

static void
eval_scan_begin()
{
#ifdef SCAN_PARANOIA
    static int inited = 0;
#endif /* SCAN_PARANOIA */

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "eval_scan_begin:");

    if (!++eval_scan_seq)
	scan_invalidate_entities(IS_EVAL);

#ifdef SCAN_PARANOIA
    if (!inited) {
#endif /* SCAN_PARANOIA */
	tac_list_init(&eval_kicked_entity_list);
	tac_list_init(&eval_destroy_entity_list);
	tac_list_init(&eval_notified_expr_list);
#ifdef SCAN_PARANOIA
	inited = 1;
    } else {
	struct tac_list_node *pending_entity_node;
	struct tac_list_node *notify_expr_node;

	while ((pending_entity_node = tac_list_first_node(&eval_kicked_entity_list)))
	    eval_scan_begin_pending_entity_node(pending_entity_node);
	while ((pending_entity_node = tac_list_first_node(&eval_destroy_entity_list)))
	    eval_scan_begin_pending_entity_node(pending_entity_node);

	while ((notify_expr_node = tac_list_first_node(&eval_notified_expr_list))) {
	    struct expr *notify_expr = NOTIFY_EXPR_NODE_TO_EXPR(notify_expr_node);

	    if (notify_expr->eval_scan.seq == eval_scan_seq)
		report(LOG_ERR, "INTERNAL: eval_notified_expr_list expr seq == ++eval_scan_seq in eval_scan_begin");

	    tac_list_node_remove(notify_expr_node);
	}
    }
#endif /* SCAN_PARANOIA */
}

/* 'priority=0' => addtail - used for WANTED entities
 * 'priority=1' => addhead - used for SOLVED entities
 *                 It may be better to do insert it AFTER all currently solved
 *                 entities but may be not but who cares...
 */

static void register_kicked_entity TAC_ARGS((ENTITY *entity, int priority));

static void register_kicked_entity(entity, priority)
ENTITY *entity;
int priority;
{
    struct tac_list_node *pending_entity_node = &entity->eval_scan.pending_entity_node;

    check_eval_scan_entity(entity, 0);

    if (tac_list_node_get_list(pending_entity_node) == &eval_destroy_entity_list) {
	tac_list_node_remove (pending_entity_node);
	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "register_kicked_entity: REMOVED " PF_ENTITY " from eval_DESTROY_entity_list",
		    PA_ENTITY(entity));
    }
    if (tac_list_node_get_list(pending_entity_node) == NULL) {
	if (priority)
	    tac_list_addhead(&eval_kicked_entity_list, pending_entity_node);
	else
	    tac_list_addtail(&eval_kicked_entity_list, pending_entity_node);
	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "register_kicked_entity: REGISTERED " PF_ENTITY " to eval_KICKED_entity_list (priority=%s)",
		    PA_ENTITY(entity), (priority ? "YES" : "NO"));
    }
#ifdef SCAN_PARANOIA
    if ((tac_list_node_get_list(pending_entity_node) != &eval_kicked_entity_list)) {
	report(LOG_ERR, "Illegal list in entity->pending_entity_node.list");
	return;
    }
#endif
}

/* check_eval_scan_*() is assumed both for "expr" and for "entity" ! */

static void expr_eval_notify_expr TAC_ARGS((struct expr *expr));

static void
expr_eval_notify_expr(expr)
struct expr *expr;
{
    ENTITY *entity = expr->u.entity.entity;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "expr_eval_notify_expr: REGISTERED notify " PF_EXPR " when " PF_ENTITY " is known",
		PA_EXPR(expr), PA_ENTITY(entity));

    if (tac_list_node_get_list(&expr->eval_scan.u.entity.notify_expr_node)) {
#ifdef SCAN_PARANOIA
	if (&entity->eval_scan.notify_expr_list
	 != tac_list_node_get_list(&expr->eval_scan.u.entity.notify_expr_node))
	    report(LOG_ERR, "Another " PF_ENTITY " already registered in notify node of " PF_EXPR,
		PA_ENTITY(EXPR_ENTITY_TO_NOTIFYING_ENTITY(expr)), PA_EXPR(expr));
#endif
	return;
    }

    tac_list_addtail(&entity->eval_scan.notify_expr_list,
	    &expr->eval_scan.u.entity.notify_expr_node);

    register_kicked_entity(entity, 0 /* priority */);
}

/* check_eval_scan_*() is assumed for "expr" ! */

static void expr_eval_notify_expr_remove_internal TAC_ARGS((struct expr *expr));

static void
expr_eval_notify_expr_remove_internal(expr)
struct expr *expr;
{
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "expr_eval_notify_expr_remove_internal: no longer interested in " PF_EXPR,
		PA_EXPR(expr));

    if (!expr)
	return;
    if (expr->eval_scan.seq != eval_scan_seq)
	return;
    if (expr->request_scan.result != ER_UNKNOWN)
	return;

    switch (expr->type) {

    case S_not:
	expr_eval_notify_expr_remove_internal(expr->u.not.child);
	break;

    case S_and:
    case S_or: {
	struct expr *child;

	for (child=expr->u.and_or.child_first; child; child=child->next)
	    expr_eval_notify_expr_remove_internal(child);
	} break;

    case S_user:
    case S_host:
    case S_group: {
	ENTITY *entity = expr->u.entity.entity;
	struct tac_list_node *pending_entity_node = &entity->eval_scan.pending_entity_node;

	if (!tac_list_node_get_list(&expr->eval_scan.u.entity.notify_expr_node))
	    break;

	tac_list_node_remove(&expr->eval_scan.u.entity.notify_expr_node);
	if (tac_list_first_node(&entity->eval_scan.notify_expr_list))
	    break;
	/* no one is further interested in "entity" */

	if ((tac_list_node_get_list(pending_entity_node) == &eval_kicked_entity_list)) {
	    tac_list_node_remove (pending_entity_node);
	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "expr_eval_notify_expr: REMOVED " PF_ENTITY " from eval_KICKED_entity_list",
			PA_ENTITY(entity));
	}
	if (tac_list_node_get_list(pending_entity_node) == NULL) {
	    tac_list_addtail(&eval_destroy_entity_list, pending_entity_node);
	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "expr_eval_notify_expr: REGISTERED " PF_ENTITY " to eval_DESTROY_entity_list",
			PA_ENTITY(entity));
	}
#ifdef SCAN_PARANOIA
	if (tac_list_node_get_list(pending_entity_node) != &eval_destroy_entity_list) {
	    report(LOG_ERR, "Illegal list in entity->pending_entity_node.list");
	    return;
	}
#endif

	} break;

    default:
	report(LOG_ERR, "Illegal node type %d for expr_eval_notify_expr_remove", expr->type);
	return;
    }
}

static void expr_eval_notify_expr_flush_destroy_entity_list TAC_ARGS((void));

static void expr_eval_notify_expr_flush_destroy_entity_list()
{
struct tac_list_node *destroy_entity_node;

    while ((destroy_entity_node = tac_list_first_node(&eval_destroy_entity_list))) {
	ENTITY *destroy_entity = PENDING_ENTITY_NODE_TO_ENTITY(destroy_entity_node);
	struct tac_list_node *destroy_notify_expr_node;

	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "expr_eval_notify_expr_flush_destroy_entity_list: PROCESSING " PF_ENTITY " from eval_DESTROY_entity_list",
		    PA_ENTITY(destroy_entity));

	while ((destroy_notify_expr_node = tac_list_first_node(&destroy_entity->eval_scan.notify_expr_list))) {
	    struct expr *destroy_notify_expr = NOTIFY_EXPR_NODE_TO_EXPR(destroy_notify_expr_node);

	    expr_eval_notify_expr_remove_internal(destroy_notify_expr);
	}
    }
}

static void expr_eval_notify_expr_remove TAC_ARGS((struct expr *expr));

static void
expr_eval_notify_expr_remove(expr)
struct expr *expr;
{
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "expr_eval_notify_expr_remove: no longer interested in " PF_EXPR,
		PA_EXPR(expr));

    expr_eval_notify_expr_remove_internal(expr);
    expr_eval_notify_expr_flush_destroy_entity_list();
}

/* It would be very nice to try to optimize the expression before evaluation.

   We are not interested in some CPU time complexity of the expression.
   But we would be very happy to discard any user/host/group membership
   dependencies (our 'variables'). Unfortunately such optimization is
   NP problem (classification by courtesy of Daniel Kral) so it is considered
   too expensive for us.

   TODO in future: Full NP optimization for small number of variables and/or
   heuristic optimizations for complex expressions.
*/

static enum eval_result expr_eval_immediate TAC_ARGS((struct expr *expr_single));

static enum eval_result
expr_eval_immediate(expr_single)
struct expr *expr_single;
{
    struct expr *expr_child, *expr_parent;
    enum eval_result result_child, result_parent = 0 /* GCC paranoia */;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "expr_eval_immediate: " PF_EXPR,
		PA_EXPR(expr_single));

    if (!expr_single)
	return (ER_TRUE);

    /* TOP->DOWN scanner: */
top_down:
    while (1) {
	enum eval_result result_single;

	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "expr_eval_immediate: top_down start: " PF_EXPR,
		    PA_EXPR(expr_single));

	check_eval_scan_expr(expr_single, 0);
	result_single = expr_single->request_scan.result;
	if (result_single != ER_UNKNOWN)
	    break;
	switch (expr_single->type) {

	case S_not:
	    expr_single = expr_single->u.not.child;
	    continue;

	case S_and:
	case S_or:
	    expr_single = expr_single->u.and_or.child_first;
	    continue;

	case S_user:
	case S_host:
	case S_group: {
	    ENTITY *entity = expr_single->u.entity.entity;

	    check_eval_scan_entity(entity, 0);

	    if (entity->request_scan.belongs == ER_UNKNOWN)
		expr_eval_notify_expr(expr_single);
	    else
		result_single = entity->request_scan.belongs;
	    } break;

	default:
	    report(LOG_ERR, "Illegal child node type %d for expr_eval", expr_single->type);
	    return (ER_UNKNOWN);
	}

	expr_single->request_scan.result = result_single;
	break;
    }

    /* BOTTOM->UP scanner: */
    do {
	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "expr_eval_immediate: bottom_up start: " PF_EXPR,
		    PA_EXPR(expr_single));

	expr_parent = expr_single->parent;
	if (!expr_parent)
	    break;
	if (expr_parent->eval_scan.seq != eval_scan_seq) {
	    report(LOG_ERR, "INTERNAL: Parent expr node eval_scan NOT up-to-date");
	    return (ER_UNKNOWN);
	}
	if (expr_parent->request_scan.seq != request_scan_seq) {
	    report(LOG_ERR, "INTERNAL: Parent expr node request_scan NOT up-to-date");
	    return (ER_UNKNOWN);
	}
	if (expr_parent->request_scan.result != ER_UNKNOWN) {
	    report(LOG_WARNING, "INTERNAL-WARNING: Parent expr node already known, wasteful eval occured");
	    return (ER_UNKNOWN);
	}

	expr_child = expr_single;
	result_child = expr_child->request_scan.result;

	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "expr_eval_immediate: bottom_up switch: child=" PF_EXPR ",parent=" PF_EXPR,
		    PA_EXPR(expr_child), PA_EXPR(expr_parent));

	switch (expr_parent->type) {

	case S_not:
	    switch (result_child) {
	    case ER_UNKNOWN: result_parent = ER_UNKNOWN; break;
	    case ER_FALSE:   result_parent = ER_TRUE;    break;
	    case ER_TRUE:    result_parent = ER_FALSE;   break;
	    }
	    break;

	case S_and:
	case S_or: {
	    enum eval_result veto    = (expr_parent->type==S_and ? ER_FALSE : ER_TRUE );
	    enum eval_result consent = (expr_parent->type==S_and ? ER_TRUE  : ER_FALSE);

		 if (result_child == veto)
	    	result_parent = veto;
	    else if (result_child == ER_UNKNOWN || result_child == consent) {
		if (expr_child->next) {
		    expr_single = expr_child->next;
		    if (debug & DEBUG_CFGEVAL_FLAG)
			report(LOG_DEBUG, "expr_eval_immediate: bottom_up and_or: traversed to and_or next: " PF_EXPR,
				PA_EXPR(expr_single));
		    goto top_down;
		}

		if (debug & DEBUG_CFGEVAL_FLAG)
		    report(LOG_DEBUG, "expr_eval_immediate: bottom_up and_or: full scan: " PF_EXPR,
			    PA_EXPR(expr_single));

		/* It would be nice to pretend that all 'veto' decisions already made in the child
		 * had to set our 'result' to the correct value. But 'consent' decisions don't set
		 * us and the behaviour of auto-set from the child in 'veto' case may get changed
		 * in the future versions.
		 * So we rather don't depend on it.
		 * This overhead doesn't change altgorithmic complexity anyway.
		 */
		result_parent = consent;
		for (expr_child = expr_parent->u.and_or.child_first; expr_child; expr_child = expr_child->next)
		{
		    check_eval_scan_expr(expr_child, 0);	/* shouldn't be needed */
		         if (expr_child->request_scan.result == ER_UNKNOWN)
			result_parent = ER_UNKNOWN;	/* assumed (result_parent != veto) */
		    else if (expr_child->request_scan.result == veto) {
			result_parent = veto;
			break;
		    }
		}
		break;
	    }
	    } break;

	default:
	    report(LOG_ERR, "Illegal parent node type %d for expr_eval", expr_parent->type);
	    return (ER_UNKNOWN);
	}

	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "expr_eval_immediate: bottom_up end: child=" PF_EXPR ",parent=" PF_EXPR,
		    PA_EXPR(expr_child), PA_EXPR(expr_parent));

	if (result_parent != ER_UNKNOWN) {
	    expr_parent->request_scan.result = result_parent;
	    /* we no longer need any notifications from entities to solve sub-expression */
	    expr_eval_notify_expr_remove(expr_parent);
	}

	expr_single = expr_parent;
    } while (0);
    /* The whole expression has been scanned to its root, we have "expr_single" */

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "expr_eval_immediate: done: " PF_EXPR,
		PA_EXPR(expr_single));

    return (expr_single->request_scan.result);
}

static void membership_solved TAC_ARGS((struct membership *membership));

static void
membership_solved(membership)
struct membership *membership;
{
    ENTITY *parent_entity = MEMBERSHIP_TO_PARENT_ENTITY(membership);

    check_request_scan_entity(parent_entity, 0);

#ifdef SCAN_PARANOIA
    if (!membership->eval_scan.unsolved) {
	report(LOG_ERR, "INTERNAL: membership already solved in membership_solved");
	return;
    }
#endif

    membership->eval_scan.unsolved = 0;

#ifdef SCAN_PARANOIA
    if (!parent_entity->eval_scan.unsolved_to_child_membership_num) {
	report(LOG_ERR, "INTERNAL: unsolved_to_child_membership_num-- == 0 in membership_solved");
	parent_entity->eval_scan.unsolved_to_child_membership_num++;
    }
#endif
    parent_entity->eval_scan.unsolved_to_child_membership_num--;

    if (!parent_entity->eval_scan.unsolved_to_child_membership_num
     && parent_entity->request_scan.belongs == ER_UNKNOWN) {
	parent_entity->request_scan.belongs = ER_FALSE;
	register_kicked_entity(parent_entity, 1 /* priority */);
    }
}

static void membership_parent_solve TAC_ARGS((struct membership *membership, enum eval_result how));

static void
membership_parent_solve(membership, how)
struct membership *membership;
enum eval_result how;
{
    enum eval_result negative = (how == ER_TRUE ? ER_FALSE : ER_TRUE);
    ENTITY *parent_entity = MEMBERSHIP_TO_PARENT_ENTITY(membership);

    check_request_scan_entity(parent_entity, 0);

    if (parent_entity->request_scan.belongs == negative)
	report(LOG_ERR, "INTERNAL: parent " PF_ENTITY "already negative to what says membership " PF_MEMBERSHIP "in membership_eval_immediate",
		PA_ENTITY(parent_entity), PA_MEMBERSHIP(membership));

    parent_entity->request_scan.belongs = how;
    register_kicked_entity(parent_entity, 1 /* priority */);

    membership_solved(membership);

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "membership_parent_solve: " PF_MEMBERSHIP " marked parent " PF_ENTITY,
		PA_MEMBERSHIP(membership), PA_ENTITY(parent_entity));
}

static void membership_eval_immediate TAC_ARGS((struct membership *membership));

static void
membership_eval_immediate(membership)
struct membership *membership;
{
    enum eval_result membership_valid;
    ENTITY *child_entity, *parent_entity;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "membership_eval_immediate: " PF_MEMBERSHIP,
		PA_MEMBERSHIP(membership));

    check_eval_scan_membership(membership, 0);

    if (!membership->eval_scan.unsolved)
	return;
    parent_entity = MEMBERSHIP_TO_PARENT_ENTITY(membership);
    check_request_scan_entity(parent_entity, 0);
    if (parent_entity->request_scan.belongs != ER_UNKNOWN)	/* why to solve this membership? */
	return;

    membership_valid = expr_eval_immediate(membership->when);

    child_entity = MEMBERSHIP_TO_CHILD_ENTITY( membership);
    check_request_scan_entity( child_entity, 0);

#if 0 /* non-valid membership doesn't YET solve the parent! */
    if (child_entity->request_scan.belongs == ER_FALSE || membership_valid == ER_FALSE) {
	membership_parent_solve(membership, ER_FALSE);
	return;
    }
#endif

    if (child_entity->request_scan.belongs == ER_TRUE  && membership_valid == ER_TRUE ) {
	membership_parent_solve(membership, ER_TRUE );
	return;
    }

    if ( child_entity->request_scan.belongs == ER_UNKNOWN)
	register_kicked_entity( child_entity, 0 /* priority */);
    if (parent_entity->request_scan.belongs == ER_UNKNOWN)
	register_kicked_entity(parent_entity, 0 /* priority */);

    if (parent_entity->request_scan.belongs != ER_UNKNOWN
     || (child_entity->request_scan.belongs == ER_FALSE || membership_valid == ER_FALSE))
	membership_solved(membership);

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "membership_eval_immediate: done: " PF_MEMBERSHIP,
		PA_MEMBERSHIP(membership));
}

static void entity_eval_immediate TAC_ARGS((ENTITY *entity));

static void
entity_eval_immediate(entity)
ENTITY *entity;
{
    struct tac_list_node *notified_expr_node;
    struct tac_list_node *child_membership_node;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "entity_eval_immediate: " PF_ENTITY,
		PA_ENTITY(entity));

    check_eval_scan_entity(entity, 0);

    if (!request_scan_user_known) {
#ifdef SCAN_PARANOIA
	if (entity->request_scan.belongs != ER_UNKNOWN)
	    report(LOG_ERR, "INTERNAL: belonging known while still !request_scan_user_known for " PF_ENTITY " in entity_eval_immediate",
		    PA_ENTITY(entity));
#endif
	return;
    }

    if (entity->request_scan.belongs == ER_UNKNOWN) {
	if (entity->eval_scan.unsolved_to_child_membership_first) {
	    struct membership *order_membership = entity->eval_scan.unsolved_to_child_membership_first;
	    struct tac_list_node *next_membership_parent_node = tac_list_node_next(&order_membership->parent_node);

	    membership_eval_immediate(order_membership);
	    if (next_membership_parent_node)
		entity->eval_scan.unsolved_to_child_membership_first = PARENT_NODE_TO_MEMBERSHIP(next_membership_parent_node);
	    else
		entity->eval_scan.unsolved_to_child_membership_first = NULL;

	    register_kicked_entity(entity, 0 /* priority */);

	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "entity_eval_immediate: finishing as we ordered child membership: " PF_MEMBERSHIP,
			PA_MEMBERSHIP(order_membership));
	    return;
	}

	if (!entity->eval_scan.unsolved_to_child_membership_num)
	    entity->request_scan.belongs = ER_FALSE;
	else {
	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "entity_eval_immediate: finishing as unsolved child memberships still available and I'm still clueless");
	    return;
	}
    }
    /* belonging is known here */

    /* recheck all memberships we may decide */
    for (
	    child_membership_node = tac_list_first_node(&entity->to_parent_membership_list);
	    child_membership_node;
	    child_membership_node = tac_list_node_next(child_membership_node)
	    ) {
	struct membership *child_membership = CHILD_NODE_TO_MEMBERSHIP(child_membership_node);

	membership_eval_immediate(child_membership);
    }

    /* notify all exprs which are interested in us */
    while ((notified_expr_node = tac_list_first_node(&entity->eval_scan.notify_expr_list))) {
	tac_list_node_remove(notified_expr_node);
	tac_list_addtail(&eval_notified_expr_list, notified_expr_node);
    }

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "entity_eval_immediate: done: " PF_ENTITY,
		PA_ENTITY(entity));
}


enum eval_result expr_eval TAC_ARGS((struct expr *expr));

enum eval_result
expr_eval(expr)
struct expr *expr;
{
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "expr_eval: top level order for " PF_EXPR,
		PA_EXPR(expr));

    if (!expr)
	return (ER_TRUE);

    eval_scan_begin();
    if (expr_eval_immediate(expr) != ER_UNKNOWN)
	return (expr->request_scan.result);

    /* all 'solved' nodes MUST be removed BEFORE '*_immediate()' has been called,
     * otherwise we may have no longer valid node!
     */
    for (;;) {
	struct tac_list_node *notified_expr_node, *kicked_entity_node;

	/* check it rather always, checking just on notifications looks too complex.
	*/
	if (expr->request_scan.result != ER_UNKNOWN) {
	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "expr_eval: finishing as ordered " PF_EXPR " got known",
			PA_EXPR(expr));
	    return (expr->request_scan.result);
	}

#if 0	/* not needed as it is now always called after any destroy */
	expr_eval_notify_expr_flush_destroy_entity_list();	/* eval_destroy_entity_list */
#endif	/* not needed */

	if ((notified_expr_node = tac_list_first_node(&eval_notified_expr_list))) {
	    struct expr *notified_expr = NOTIFY_EXPR_NODE_TO_EXPR(notified_expr_node);

	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "expr_eval: PROCESSING " PF_EXPR " from eval_NOTIFIED_expr_list",
			PA_EXPR(notified_expr));

	    tac_list_node_remove(notified_expr_node);
	    expr_eval_immediate(notified_expr);

	    if (notified_expr->membership)
		membership_eval_immediate(notified_expr->membership);

	    continue;		/* shortcut */
	}

	if ((kicked_entity_node = tac_list_first_node(&eval_kicked_entity_list))) {
	    ENTITY *kicked_entity = PENDING_ENTITY_NODE_TO_ENTITY(kicked_entity_node);

	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "expr_eval: PROCESSING " PF_ENTITY " from eval_KICKED_entity_list",
			PA_ENTITY(kicked_entity));

	    tac_list_node_remove(kicked_entity_node);
	    entity_eval_immediate(kicked_entity);
	    continue;		/* shortcut */
	}

	break;	/* nothing done yet, all lists are empty! */
    }

    if (!expr->request_scan.loop_reported) {
	report(LOG_WARNING, "Unable to resolve expression from line %d, some looping occured", expr->line);
	expr->request_scan.loop_reported = 1;
    }
    return (ER_UNKNOWN);
}


void eval_force_belong_entity TAC_ARGS((ENTITY *entity));

void eval_force_belong_entity(entity)
ENTITY *entity;
{
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "eval_force_belong_entity: " PF_ENTITY " (before check_scan " PF_ERESULT_ENTITY ")",
		PA_ENTITY(entity), PA_ERESULT_ENTITY(entity));

    check_request_scan_entity(entity, 0);

    if (entity->request_scan.belongs == ER_FALSE)
	report(LOG_ERR, "Dangerous force of TRUE to FALSE-determined entity in eval_force_belong_entity");

    entity->request_scan.belongs = ER_TRUE;
}

void scan_init_entity TAC_ARGS((ENTITY *entity));

void
scan_init_entity(entity)
ENTITY *entity;
{
    entity->request_scan.seq = request_scan_seq-1;	/* invalidate */
    entity->  value_scan.seq =   value_scan_seq-1;	/* invalidate */
    entity->   eval_scan.seq =    eval_scan_seq-1;	/* invalidate */
    tac_list_init(&entity->eval_scan.notify_expr_list);
    tac_list_node_init(&entity->eval_scan.pending_entity_node);
}

struct membership *enlist_entity_direct TAC_ARGS((ENTITY *parent, ENTITY *child, struct expr *when));

struct membership *
enlist_entity_direct(parent, child, when)
ENTITY *parent;
ENTITY *child;
struct expr *when;
{
    struct membership *membership = (struct membership *) tac_malloc(sizeof(struct membership));

    tac_list_node_init(&membership->parent_node);
    tac_list_node_init(&membership->child_node);
    membership->request_scan.seq = request_scan_seq-1;
    tac_list_node_init(&membership->request_scan.virtual_membership_node);
    membership->eval_scan.seq = eval_scan_seq-1;

    tac_list_addtail(&parent->to_child_membership_list , &membership->parent_node);
    parent->to_child_membership_num++;
    tac_list_addtail(& child->to_parent_membership_list, &membership-> child_node);
    membership->when = when;
    if (expr_sink(membership->when, membership)) {
	unlink_membership(membership);
	free_membership(membership);
	return (NULL);
    }

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "enlist_entity_direct: done: " PF_MEMBERSHIP,
		PA_MEMBERSHIP(membership));

    return (membership);
}

struct membership *virtual_enlist_entity_direct TAC_ARGS((ENTITY *parent, ENTITY *child));

struct membership *
virtual_enlist_entity_direct(parent, child)
ENTITY *parent;
ENTITY *child;
{
    struct membership *membership;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "virtual_enlist_entity_direct: the following enlist will be VIRTUAL...");

    membership = enlist_entity_direct(parent, child, NULL /* when */);
    if (!membership)
	return (NULL);

    check_request_scan_membership(membership, 0);
    tac_list_addtail(&request_virtual_membership_list, &membership->request_scan.virtual_membership_node);

    return (membership);
}

/* returns given 'entity' or NULL if already visited */

void (*value_scan_forward_seen_hook) TAC_ARGS((struct membership *membership));

static ENTITY *value_scan_forward TAC_ARGS((struct membership *membership));

static ENTITY *
value_scan_forward(membership)
struct membership *membership;
{
    ENTITY *parent_entity;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "value_scan_forward: from " PF_MEMBERSHIP " try forward...",
		PA_MEMBERSHIP(membership));

    parent_entity = MEMBERSHIP_TO_PARENT_ENTITY(membership);

    if (ER_TRUE != expr_eval(membership->when)) {
	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "value_scan_forward: forward NOT successful due to failed 'when' evaluation.");
	return (NULL);
    }
    check_value_scan_entity(parent_entity, 0);
    if (parent_entity->value_scan.seen) {
	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "value_scan_forward: forward NOT successful as the parent " PF_ENTITY " was already seen this value scan.",
		    PA_ENTITY(parent_entity));
	if (value_scan_forward_seen_hook)
	    (*value_scan_forward_seen_hook)(membership);
	return (NULL);
    }
    parent_entity->value_scan.seen = 1;
    parent_entity->value_scan.from = membership;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "value_scan_forward: forward SUCCESSFUL to parent " PF_ENTITY,
		PA_ENTITY(parent_entity));
    return (parent_entity);
}

struct membership *value_scan_backward TAC_ARGS((ENTITY *entity));

struct membership *
value_scan_backward(entity)
ENTITY *entity;
{
    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "value_scan_backward: from " PF_ENTITY " went back to " PF_MEMBERSHIP,
		PA_ENTITY(entity), PA_MEMBERSHIP(entity->value_scan.from));

#ifdef SCAN_PARANOIA
    if (entity->value_scan.seq != value_scan_seq) {
	report(LOG_ERR, "entity value_scan NOT up-to-date in value_scan_backward");
	return (NULL);
    }
#endif

    return (entity->value_scan.from);
}

/* Scan the entity graph and return each node found.
   'when' conditions for graph connections are respected,
   looping is correctly prevented.
*/

enum value_scan_func_result value_scan_entity TAC_ARGS((ENTITY *entity, int recurse, value_scan_func_t func, void *func_data));

enum value_scan_func_result
value_scan_entity(entity, recurse, func, func_data)
ENTITY *entity;
int recurse;
value_scan_func_t func;
void *func_data;
{
    enum value_scan_func_result vsfr;
    struct tac_list_node *membership_node;

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "value_scan_entity: " PF_ENTITY ", recurse=%d",
		PA_ENTITY(entity), recurse);

    vsfr=(*func)(entity,func_data);

    if (debug & DEBUG_CFGEVAL_FLAG)
	report(LOG_DEBUG, "value_scan_entity: root func-> " PF_VSFR,
		PA_VSFR(vsfr));

    if (vsfr != VSFR_CONTINUE) {
	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "value_scan_entity: finishing as root func didn't return VSFR_CONTINUE");
	return (vsfr);
    }
    if (!recurse ) {
	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "value_scan_entity: finishing as recurse not ordered");
	return (VSFR_STOP);
    }

    value_scan_begin(entity);
    membership_node = tac_list_first_node(&entity->to_parent_membership_list);
    if (!membership_node) {
	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "value_scan_entity: finishing as no parent entities of root");
	return (VSFR_CONTINUE);		/* no parent entities */
    }

    while (1) {
	struct membership *membership = CHILD_NODE_TO_MEMBERSHIP(membership_node);

	if (debug & DEBUG_CFGEVAL_FLAG)
	    report(LOG_DEBUG, "value_scan_entity: trace loop start: " PF_MEMBERSHIP,
		    PA_MEMBERSHIP(membership));

	entity = value_scan_forward(membership);
	if (entity) {
	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "value_scan_entity: successful recurse to " PF_ENTITY,
			PA_ENTITY(entity));

	    vsfr=(*func)(entity,func_data);

	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "value_scan_entity: func(" PF_ENTITY ")-> " PF_VSFR,
			PA_ENTITY(entity), PA_VSFR(vsfr));

	    if (vsfr == VSFR_FOUND) {
		if (debug & DEBUG_CFGEVAL_FLAG)
		    report(LOG_DEBUG, "value_scan_entity: finishing as func returned VSFR_FOUND");
		return (vsfr);
	    }
	    if (vsfr == VSFR_CONTINUE)
		membership_node = tac_list_first_node(&entity->to_parent_membership_list);
	}
	if (!entity || vsfr == VSFR_STOP) {
	    ENTITY *parent_entity = MEMBERSHIP_TO_PARENT_ENTITY(membership);

	    entity = MEMBERSHIP_TO_CHILD_ENTITY(membership);	/* for retreat from the LAST membership */

	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "value_scan_entity: unsuccessful recurse to " PF_ENTITY ", tracing back through child " PF_ENTITY,
			PA_ENTITY(parent_entity), PA_ENTITY(entity));

	    membership_node = tac_list_node_next(&membership->child_node);
	}

	while (!membership_node) {
	    membership = value_scan_backward(entity);
	    if (!membership) {
		if (debug & DEBUG_CFGEVAL_FLAG)
		    report(LOG_DEBUG, "value_scan_entity: finishing as all nodes were scanned");
		return (VSFR_CONTINUE);		/* FINISH */
	    }

	    entity = MEMBERSHIP_TO_CHILD_ENTITY(membership);	/* for retreat from the LAST membership */

	    if (debug & DEBUG_CFGEVAL_FLAG)
		report(LOG_DEBUG, "value_scan_entity: backward retreat ('next' chase) "
				"through " PF_MEMBERSHIP " to child " PF_ENTITY,
				PA_MEMBERSHIP(membership), PA_ENTITY(entity));

	    membership_node = tac_list_node_next(&membership->child_node);
	}
    }
    /* NOTREACHED */
}