/**

 * @file pdag.c

 * @brief Implementation of the parse dag object.

 * @class ln_pdag pdag.h

 *//*

 * Copyright 2015 by Rainer Gerhards and Adiscon GmbH.

 *

 * Released under ASL 2.0.

 */

#include "config.h"

#include <stdlib.h>

#include <stdio.h>

#include <stdarg.h>

#include <string.h>

#include <assert.h>

#include <ctype.h>

#include <libestr.h>

#include "liblognorm.h"

#include "v1_liblognorm.h"

#include "v1_ptree.h"

#include "lognorm.h"

#include "samp.h"

#include "pdag.h"

#include "annot.h"

#include "internal.h"

#include "parser.h"

#include "helpers.h"

void ln_displayPDAGComponentAlternative(struct ln_pdag *dag, int level);

void ln_displayPDAGComponent(struct ln_pdag *dag, int level);

#ifdef	ADVANCED_STATS

uint64_t advstats_parsers_called = 0;

uint64_t advstats_parsers_success = 0;

int advstats_max_pathlen = 0;

int advstats_pathlens[ADVSTATS_MAX_ENTITIES];

int advstats_max_backtracked = 0;

int advstats_backtracks[ADVSTATS_MAX_ENTITIES];

int advstats_max_parser_calls = 0;

int advstats_parser_calls[ADVSTATS_MAX_ENTITIES];

int advstats_max_lit_parser_calls = 0;

int advstats_lit_parser_calls[ADVSTATS_MAX_ENTITIES];

#endif

/* parser lookup table

 * This is a memory- and cache-optimized way of calling parsers.

 * VERY IMPORTANT: the initialization must be done EXACTLY in the

 * order of parser IDs (also see comment in pdag.h).

 *

 * Rough guideline for assigning priorites:

 * 0 is highest, 255 lowest. 255 should be reserved for things that

 * *really* should only be run as last resort --> rest. Also keep in

 * mind that the user-assigned priority is put in the upper 24 bits, so

 * parser-specific priorities only count when the user has assigned

 * no priorities (which is expected to be common) or user-assigned

 * priorities are equal for some parsers.

 */

#ifdef ADVANCED_STATS

#define PARSER_ENTRY_NO_DATA(identifier, parser, prio) \

{ identifier, prio, NULL, ln_v2_parse##parser, NULL, 0, 0 }

#define PARSER_ENTRY(identifier, parser, prio) \

{ identifier, prio, ln_construct##parser, ln_v2_parse##parser, ln_destruct##parser, 0, 0 }

#else

#define PARSER_ENTRY_NO_DATA(identifier, parser, prio) \

{ identifier, prio, NULL, ln_v2_parse##parser, NULL }

#define PARSER_ENTRY(identifier, parser, prio) \

{ identifier, prio, ln_construct##parser, ln_v2_parse##parser, ln_destruct##parser }

#endif

static struct ln_parser_info parser_lookup_table[] = {

	PARSER_ENTRY("literal", Literal, 4),

	PARSER_ENTRY("repeat", Repeat, 4),

	PARSER_ENTRY("date-rfc3164", RFC3164Date, 8),

	PARSER_ENTRY("date-rfc5424", RFC5424Date, 8),

	PARSER_ENTRY("number", Number, 16),

	PARSER_ENTRY("float", Float, 16),

	PARSER_ENTRY("hexnumber", HexNumber, 16),

	PARSER_ENTRY_NO_DATA("kernel-timestamp", KernelTimestamp, 16),

	PARSER_ENTRY_NO_DATA("whitespace", Whitespace, 4),

	PARSER_ENTRY_NO_DATA("ipv4", IPv4, 4),

	PARSER_ENTRY_NO_DATA("ipv6", IPv6, 4),

	PARSER_ENTRY_NO_DATA("word", Word, 32),

	PARSER_ENTRY_NO_DATA("alpha", Alpha, 32),

	PARSER_ENTRY_NO_DATA("rest", Rest, 255),

	PARSER_ENTRY_NO_DATA("op-quoted-string", OpQuotedString, 64),

	PARSER_ENTRY_NO_DATA("quoted-string", QuotedString, 64),

	PARSER_ENTRY_NO_DATA("date-iso", ISODate, 8),

	PARSER_ENTRY_NO_DATA("time-24hr", Time24hr, 8),

	PARSER_ENTRY_NO_DATA("time-12hr", Time12hr, 8),

	PARSER_ENTRY_NO_DATA("duration", Duration, 16),

	PARSER_ENTRY_NO_DATA("cisco-interface-spec", CiscoInterfaceSpec, 4),

	PARSER_ENTRY_NO_DATA("name-value-list", NameValue, 8),

	PARSER_ENTRY_NO_DATA("json", JSON, 4),

	PARSER_ENTRY_NO_DATA("cee-syslog", CEESyslog, 4),

	PARSER_ENTRY_NO_DATA("mac48", MAC48, 16),

	PARSER_ENTRY_NO_DATA("cef", CEF, 4),

	PARSER_ENTRY_NO_DATA("checkpoint-lea", CheckpointLEA, 4),

	PARSER_ENTRY_NO_DATA("v2-iptables", v2IPTables, 4),

	PARSER_ENTRY("string-to", StringTo, 32),

	PARSER_ENTRY("char-to", CharTo, 32),

	PARSER_ENTRY("char-sep", CharSeparated, 32),

	PARSER_ENTRY("string", String, 32)

};

#define NPARSERS (sizeof(parser_lookup_table)/sizeof(struct ln_parser_info))

#define DFLT_USR_PARSER_PRIO 30000 /**< default priority if user has not specified it */

static inline const char *

parserName(const prsid_t id)

{

	const char *name;

	if(id == PRS_CUSTOM_TYPE)

		name = "USER-DEFINED";

	else

		name = parser_lookup_table[id].name;

	return name;

}

prsid_t

ln_parserName2ID(const char *const __restrict__ name)

{

	unsigned i;

	for(  i = 0

	    ; i < sizeof(parser_lookup_table) / sizeof(struct ln_parser_info)

	    ; ++i) {

	    	if(!strcmp(parser_lookup_table[i].name, name)) {

			return i;

		}

	    }

	return PRS_INVALID;

}

/* find type pdag in table. If "bAdd" is set, add it if not

 * already present, a new entry will be added.

 * Returns NULL on error, ptr to type pdag entry otherwise

 */

struct ln_type_pdag *

ln_pdagFindType(ln_ctx ctx, const char *const __restrict__ name, const int bAdd)

{

	struct ln_type_pdag *td = NULL;

	int i;

	LN_DBGPRINTF(ctx, "ln_pdagFindType, name '%s', bAdd: %d, nTypes %d",

		name, bAdd, ctx->nTypes);

	for(i = 0 ; i < ctx->nTypes ; ++i) {

		if(!strcmp(ctx->type_pdags[i].name, name)) {

			td = ctx->type_pdags + i;

			goto done;

		}

	}

	if(!bAdd) {

		LN_DBGPRINTF(ctx, "custom type '%s' not found", name);

		goto done;

	}

	/* type does not yet exist -- create entry */

	LN_DBGPRINTF(ctx, "custom type '%s' does not yet exist, adding...", name);

	struct ln_type_pdag *newarr;

	newarr = realloc(ctx->type_pdags, sizeof(struct ln_type_pdag) * (ctx->nTypes+1));

	if(newarr == NULL) {

		LN_DBGPRINTF(ctx, "ln_pdagFindTypeAG: alloc newarr failed");

		goto done;

	}

	ctx->type_pdags = newarr;

	td = ctx->type_pdags + ctx->nTypes;

	++ctx->nTypes;

	td->name = strdup(name);

	td->pdag = ln_newPDAG(ctx);

done:

	return td;

}

/* we clear some multiple times, but as long as we have no loops

 * (dag!) we have no real issue.

 */

static void

ln_pdagComponentClearVisited(struct ln_pdag *const dag)

{

	dag->flags.visited = 0;

	for(int i = 0 ; i < dag->nparsers ; ++i) {

		ln_parser_t *prs = dag->parsers+i;

		ln_pdagComponentClearVisited(prs->node);

	}

}

static void

ln_pdagClearVisited(ln_ctx ctx)

{

	for(int i = 0 ; i < ctx->nTypes ; ++i)

		ln_pdagComponentClearVisited(ctx->type_pdags[i].pdag);

	ln_pdagComponentClearVisited(ctx->pdag);

}

/**

 * Process a parser defintion. Note that a single defintion can potentially

 * contain many parser instances.

 * @return parser node ptr or NULL (on error)

 */

ln_parser_t*

ln_newParser(ln_ctx ctx,

	json_object *prscnf)

{

	ln_parser_t *node = NULL;

	json_object *json;

	const char *val;

	prsid_t prsid;

	struct ln_type_pdag *custType = NULL;

	const char *name = NULL;

	const char *textconf = json_object_to_json_string(prscnf);

	int assignedPrio = DFLT_USR_PARSER_PRIO;

	int parserPrio;

	json_object_object_get_ex(prscnf, "type", &json);

	if(json == NULL) {

		ln_errprintf(ctx, 0, "parser type missing in config: %s",

			json_object_to_json_string(prscnf));

		goto done;

	}

	val = json_object_get_string(json);

	if(*val == '@') {

		prsid = PRS_CUSTOM_TYPE;

		custType = ln_pdagFindType(ctx, val, 0);

		parserPrio = 16; /* hopefully relatively specific... */

		if(custType == NULL) {

			ln_errprintf(ctx, 0, "unknown user-defined type '%s'", val);

			goto done;

		}

	} else {

		prsid = ln_parserName2ID(val);

		if(prsid == PRS_INVALID) {

			ln_errprintf(ctx, 0, "invalid field type '%s'", val);

			goto done;

		}

		parserPrio = parser_lookup_table[prsid].prio;

	}

	json_object_object_get_ex(prscnf, "name", &json);

	if(json == NULL || !strcmp(json_object_get_string(json), "-")) {

		name = NULL;

	} else {

		name = strdup(json_object_get_string(json));

	}

	json_object_object_get_ex(prscnf, "priority", &json);

	if(json != NULL) {

		assignedPrio = json_object_get_int(json);

	}

	LN_DBGPRINTF(ctx, "assigned priority is %d", assignedPrio);

	/* we need to remove already processed items from the config, so

	 * that we can pass the remaining parameters to the parser.

	 */

	json_object_object_del(prscnf, "type");

	json_object_object_del(prscnf, "priority");

	if(name != NULL)

		json_object_object_del(prscnf, "name");

	/* got all data items */

	if((node = calloc(1, sizeof(ln_parser_t))) == NULL) {

		LN_DBGPRINTF(ctx, "lnNewParser: alloc node failed");

		free((void*)name);

		goto done;

	}

	node->node = NULL;

	node->prio = ((assignedPrio << 8) & 0xffffff00) | (parserPrio & 0xff);

	node->name = name;

	node->prsid = prsid;

	node->conf = strdup(textconf);

	if(prsid == PRS_CUSTOM_TYPE) {

		node->custType = custType;

	} else {

		if(parser_lookup_table[prsid].construct != NULL) {

			parser_lookup_table[prsid].construct(ctx, prscnf, &node->parser_data);

		}

	}

done:

	return node;

}

struct ln_pdag*

ln_newPDAG(ln_ctx ctx)

{

	struct ln_pdag *dag;

	if((dag = calloc(1, sizeof(struct ln_pdag))) == NULL)

		goto done;

	dag->refcnt = 1;

	dag->ctx = ctx;

	ctx->nNodes++;

done:	return dag;

}

/* note: we must NOT free the parser itself, because

 * it is stored inside a parser table (so no single

 * alloc for the parser!).

 */

static void

pdagDeletePrs(ln_ctx ctx, ln_parser_t *const __restrict__ prs)

{

	// TODO: be careful here: once we move to real DAG from tree, we

	// cannot simply delete the next node! (refcount? something else?)

	if(prs->node != NULL)

		ln_pdagDelete(prs->node);

	free((void*)prs->name);

	free((void*)prs->conf);

	if(prs->parser_data != NULL)

		parser_lookup_table[prs->prsid].destruct(ctx, prs->parser_data);

}

void

ln_pdagDelete(struct ln_pdag *const __restrict__ pdag)

{

	if(pdag == NULL)

		goto done;

	LN_DBGPRINTF(pdag->ctx, "delete %p[%d]: %s", pdag, pdag->refcnt, pdag->rb_id);

	--pdag->refcnt;

	if(pdag->refcnt > 0)

		goto done;

	if(pdag->tags != NULL)

		json_object_put(pdag->tags);

	for(int i = 0 ; i < pdag->nparsers ; ++i) {

		pdagDeletePrs(pdag->ctx, pdag->parsers+i);

	}

	free(pdag->parsers);

	free((void*)pdag->rb_id);

	free((void*)pdag->rb_file);

	free(pdag);

done:	return;

}

/**

 * pdag optimizer step: literal path compaction

 *

 * We compress as much as possible and evalute the path down to

 * the first non-compressable element. Note that we must NOT

 * compact those literals that are either terminal nodes OR

 * contain names so that the literal is to be parsed out.

 */

static inline int

optLitPathCompact(ln_ctx ctx, ln_parser_t *prs)

{

	int r = 0;

	while(prs != NULL) {

		/* note the NOT prefix in the condition below! */

		if(!(   prs->prsid == PRS_LITERAL

		     && prs->name == NULL

		     && prs->node->flags.isTerminal == 0

		     && prs->node->refcnt == 1

		     && prs->node->nparsers == 1

		     /* we need to do some checks on the child as well */

		     && prs->node->parsers[0].prsid == PRS_LITERAL

		     && prs->node->parsers[0].name == NULL

		     && prs->node->parsers[0].node->refcnt == 1)

		  )

			goto done;

		/* ok, we have two compactable literals in a row, let's compact the nodes */

		ln_parser_t *child_prs = prs->node->parsers;

		LN_DBGPRINTF(ctx, "opt path compact: add %p to %p", child_prs, prs);

		CHKR(ln_combineData_Literal(prs->parser_data, child_prs->parser_data));

		ln_pdag *const node_del = prs->node;

		prs->node = child_prs->node;

		child_prs->node = NULL; /* remove, else this would be destructed! */

		ln_pdagDelete(node_del);

	}

done:

	return r;

}

static int

qsort_parserCmp(const void *v1, const void *v2)

{

	const ln_parser_t *const p1 = (const ln_parser_t *const) v1;

	const ln_parser_t *const p2 = (const ln_parser_t *const) v2;

	return p1->prio - p2->prio;

}

static int

ln_pdagComponentOptimize(ln_ctx ctx, struct ln_pdag *const dag)

{

	int r = 0;

for(int i = 0 ; i < dag->nparsers ; ++i) { /* TODO: remove when confident enough */

	ln_parser_t *prs = dag->parsers+i;

	LN_DBGPRINTF(ctx, "pre sort, parser %d:%s[%d]", i, prs->name, prs->prio);

}

	/* first sort parsers in priority order */

	if(dag->nparsers > 1) {

		qsort(dag->parsers, dag->nparsers, sizeof(ln_parser_t), qsort_parserCmp);

	}

for(int i = 0 ; i < dag->nparsers ; ++i) { /* TODO: remove when confident enough */

	ln_parser_t *prs = dag->parsers+i;

	LN_DBGPRINTF(ctx, "post sort, parser %d:%s[%d]", i, prs->name, prs->prio);

}

	/* now on to rest of processing */

	for(int i = 0 ; i < dag->nparsers ; ++i) {

		ln_parser_t *prs = dag->parsers+i;

		LN_DBGPRINTF(dag->ctx, "optimizing %p: field %d type '%s', name '%s': '%s':",

			prs->node, i, parserName(prs->prsid), prs->name,

			(prs->prsid == PRS_LITERAL) ?  ln_DataForDisplayLiteral(dag->ctx, prs->parser_data)

				: "UNKNOWN");

		optLitPathCompact(ctx, prs);

		ln_pdagComponentOptimize(ctx, prs->node);

	}

	return r;

}

static void

deleteComponentID(struct ln_pdag *const __restrict__ dag)

{

	free((void*)dag->rb_id);

	dag->rb_id = NULL;

	for(int i = 0 ; i < dag->nparsers ; ++i) {

		ln_parser_t *prs = dag->parsers+i;

		deleteComponentID(prs->node);

	}

}

/* fixes rb_ids for this node as well as it predecessors.

 * This is required if the ALTERNATIVE parser type is used,

 * which will create component IDs for each of it's invocations.

 * As such, we do not only fix the string, but know that all

 * children also need fixning. We do this be simply deleting

 * all of their rb_ids, as we know they will be visited again.

 * Note: if we introduce the same situation by new functionality,

 * we may need to review this code here as well. Also note

 * that the component ID will not be 100% correct after our fix,

 * because that ID could acutally be created by two sets of rules.

 * But this is the best we can do.

 */

static void

fixComponentID(struct ln_pdag *const __restrict__ dag, const char *const new)

{

	char *updated;

	const char *const curr = dag->rb_id;

	int i;

	int len = (int) strlen(curr);

	for(i = 0 ; i < len ; ++i){

		if(curr[i] != new [i])

			break;

	}

	if(i >= 1 && curr[i-1] == '%')

		--i;

	if(asprintf(&updated, "%.*s[%s|%s]", i, curr, curr+i, new+i) == -1)

		goto done;

	deleteComponentID(dag);

	dag->rb_id = updated;

done:	return;

}

/**

 * Assign human-readable identifiers (names) to each node. These are

 * later used in stats, debug output and whereever else this may make

 * sense.

 */

static void

ln_pdagComponentSetIDs(ln_ctx ctx, struct ln_pdag *const dag, const char *prefix)

{

	char *id = NULL;

	if(prefix == NULL)

		goto done;

	if(dag->rb_id == NULL) {

		dag->rb_id = strdup(prefix);

	} else {

		LN_DBGPRINTF(ctx, "rb_id already exists - fixing as good as "

			"possible. This happens with ALTERNATIVE parser. "

			"old: '%s', new: '%s'",

			dag->rb_id, prefix);

		fixComponentID(dag, prefix);

		LN_DBGPRINTF(ctx, "\"fixed\" rb_id: %s", dag->rb_id);

		prefix = dag->rb_id;

	}

	/* now on to rest of processing */

	for(int i = 0 ; i < dag->nparsers ; ++i) {

		ln_parser_t *prs = dag->parsers+i;

		if(prs->prsid == PRS_LITERAL) {

			if(prs->name == NULL) {

				if(asprintf(&id, "%s%s", prefix,

					ln_DataForDisplayLiteral(dag->ctx, prs->parser_data)) == -1)

					goto done;

			} else {

				if(asprintf(&id, "%s%%%s:%s:%s%%", prefix,

					prs->name,

					parserName(prs->prsid),

					ln_DataForDisplayLiteral(dag->ctx, prs->parser_data)) == -1)

					goto done;

			}

		} else {

			if(asprintf(&id, "%s%%%s:%s%%", prefix,

				prs->name ? prs->name : "-",

				parserName(prs->prsid)) == -1)

					goto done;

		}

		ln_pdagComponentSetIDs(ctx, prs->node, id);

		free(id);

	}

done:	return;

}

/**

 * Optimize the pdag.

 * This includes all components.

 */

int

ln_pdagOptimize(ln_ctx ctx)

{

	int r = 0;

	for(int i = 0 ; i < ctx->nTypes ; ++i) {

		LN_DBGPRINTF(ctx, "optimizing component %s\n", ctx->type_pdags[i].name);

		ln_pdagComponentOptimize(ctx, ctx->type_pdags[i].pdag);

		ln_pdagComponentSetIDs(ctx, ctx->type_pdags[i].pdag, "");

	}

	LN_DBGPRINTF(ctx, "optimizing main pdag component");

	ln_pdagComponentOptimize(ctx, ctx->pdag);

	LN_DBGPRINTF(ctx, "finished optimizing main pdag component");

	ln_pdagComponentSetIDs(ctx, ctx->pdag, "");

LN_DBGPRINTF(ctx, "---AFTER OPTIMIZATION------------------");

ln_displayPDAG(ctx);

LN_DBGPRINTF(ctx, "=======================================");

	return r;

}

#define LN_INTERN_PDAG_STATS_NPARSERS 100

/* data structure for pdag statistics */

struct pdag_stats {

	int nodes;

	int term_nodes;

	int parsers;

	int max_nparsers;

	int nparsers_cnt[LN_INTERN_PDAG_STATS_NPARSERS];

	int nparsers_100plus;

	int *prs_cnt;

};

/**

 * Recursive step of statistics gatherer.

 */

static int

ln_pdagStatsRec(ln_ctx ctx, struct ln_pdag *const dag, struct pdag_stats *const stats)

{

	if(dag->flags.visited)

		return 0;

	dag->flags.visited = 1;

	stats->nodes++;

	if(dag->flags.isTerminal)

		stats->term_nodes++;

	if(dag->nparsers > stats->max_nparsers)

		stats->max_nparsers = dag->nparsers;

	if(dag->nparsers >= LN_INTERN_PDAG_STATS_NPARSERS)

		stats->nparsers_100plus++;

	else

		stats->nparsers_cnt[dag->nparsers]++;

	stats->parsers += dag->nparsers;

	int max_path = 0;

	for(int i = 0 ; i < dag->nparsers ; ++i) {

		ln_parser_t *prs = dag->parsers+i;

		if(prs->prsid != PRS_CUSTOM_TYPE)

			stats->prs_cnt[prs->prsid]++;

		const int path_len = ln_pdagStatsRec(ctx, prs->node, stats);

		if(path_len > max_path)

			max_path = path_len;

	}

	return max_path + 1;

}

static void

ln_pdagStatsExtended(ln_ctx ctx, struct ln_pdag *const dag, FILE *const fp, int level)

{

	char indent[2048];

	if(level > 1023)

		level = 1023;

	memset(indent, ' ', level * 2);

	indent[level * 2] = '\0';

	if(dag->stats.called > 0) {

		fprintf(fp, "%u, %u, %s\n",

			dag->stats.called,

			dag->stats.backtracked,

			dag->rb_id);

	}

	for(int i = 0 ; i < dag->nparsers ; ++i) {

		ln_parser_t *const prs = dag->parsers+i;

		if(prs->node->stats.called > 0) {

			ln_pdagStatsExtended(ctx, prs->node, fp, level+1);

		}

	}

}

/**

 * Gather pdag statistics for a *specific* pdag.

 *

 * Data is sent to given file ptr.

 */

static void

ln_pdagStats(ln_ctx ctx, struct ln_pdag *const dag, FILE *const fp, const int extendedStats)

{

	struct pdag_stats *const stats = calloc(1, sizeof(struct pdag_stats));

	stats->prs_cnt = calloc(NPARSERS, sizeof(int));

	//ln_pdagClearVisited(ctx);

	const int longest_path = ln_pdagStatsRec(ctx, dag, stats);

	fprintf(fp, "nodes.............: %4d\n", stats->nodes);

	fprintf(fp, "terminal nodes....: %4d\n", stats->term_nodes);

	fprintf(fp, "parsers entries...: %4d\n", stats->parsers);

	fprintf(fp, "longest path......: %4d\n", longest_path);

	fprintf(fp, "Parser Type Counts:\n");

	for(prsid_t i = 0 ; i < NPARSERS ; ++i) {

		if(stats->prs_cnt[i] != 0)

			fprintf(fp, "\t%20s: %d\n", parserName(i), stats->prs_cnt[i]);

	}

	int pp = 0;

	fprintf(fp, "Parsers per Node:\n");

	fprintf(fp, "\tmax:\t%4d\n", stats->max_nparsers);

	for(int i = 0 ; i < 100 ; ++i) {

		pp += stats->nparsers_cnt[i];

		if(stats->nparsers_cnt[i] != 0)

			fprintf(fp, "\t%d:\t%4d\n", i, stats->nparsers_cnt[i]);

	}

	free(stats->prs_cnt);

	free(stats);

	if(extendedStats) {

		fprintf(fp, "Usage Statistics:\n"

			    "-----------------\n");

		fprintf(fp, "called, backtracked, rule\n");

		ln_pdagComponentClearVisited(dag);

		ln_pdagStatsExtended(ctx, dag, fp, 0);

	}

}

/**

 * Gather and output pdag statistics for the full pdag (ctx)

 * including all disconnected components (type defs).

 *

 * Data is sent to given file ptr.

 */

void

ln_fullPdagStats(ln_ctx ctx, FILE *const fp, const int extendedStats)

{

	if(ctx->ptree != NULL) {

		/* we need to handle the old cruft */

		ln_fullPTreeStats(ctx, fp, extendedStats);

		return;

	}

	fprintf(fp, "User-Defined Types\n"

	            "==================\n");

	fprintf(fp, "number types: %d\n", ctx->nTypes);

	for(int i = 0 ; i < ctx->nTypes ; ++i)

		fprintf(fp, "type: %s\n", ctx->type_pdags[i].name);

	for(int i = 0 ; i < ctx->nTypes ; ++i) {

		fprintf(fp, "\n"

			    "type PDAG: %s\n"

		            "----------\n", ctx->type_pdags[i].name);

		ln_pdagStats(ctx, ctx->type_pdags[i].pdag, fp, extendedStats);

	}

	fprintf(fp, "\n"

		    "Main PDAG\n"

	            "=========\n");

	ln_pdagStats(ctx, ctx->pdag, fp, extendedStats);

#ifdef	ADVANCED_STATS

	const uint64_t parsers_failed = advstats_parsers_called - advstats_parsers_success;

	fprintf(fp, "\n"

		    "Advanced Runtime Stats\n"

	            "======================\n");

	fprintf(fp, "These are actual number from analyzing the control flow "

		    "at runtime.\n");

	fprintf(fp, "Note that literal matching is also done via parsers. As such, \n"

		    "it is expected that fail rates increase with the size of the \n"

		    "rule base.\n");

	fprintf(fp, "\n");

	fprintf(fp, "Parser Calls:\n");

	fprintf(fp, "total....: %10" PRIu64 "\n", advstats_parsers_called);

	fprintf(fp, "succesful: %10" PRIu64 "\n", advstats_parsers_success);

	fprintf(fp, "failed...: %10" PRIu64 " [%d%%]\n",

		parsers_failed,

		(int) ((parsers_failed * 100) / advstats_parsers_called) );

	fprintf(fp, "\nIndividual Parser Calls "

		    "(never called parsers are not shown):\n");

	for(  size_t i = 0

	    ; i < sizeof(parser_lookup_table) / sizeof(struct ln_parser_info)

	    ; ++i) {

		if(parser_lookup_table[i].called > 0) {

			const uint64_t failed = parser_lookup_table[i].called

				- parser_lookup_table[i].success;

			fprintf(fp, "%20s: %10" PRIu64 " [%5.2f%%] "

				    "success: %10" PRIu64 " [%5.1f%%] "

				    "fail: %10" PRIu64 " [%5.1f%%]"

			            "\n",

				parser_lookup_table[i].name,

				parser_lookup_table[i].called,

				(float)(parser_lookup_table[i].called * 100)

				        / advstats_parsers_called,

				parser_lookup_table[i].success,

				(float)(parser_lookup_table[i].success * 100)

				        / parser_lookup_table[i].called,

				failed,

				(float)(failed * 100)

				        / parser_lookup_table[i].called

			       );

		}

	}

	uint64_t total_len;

	uint64_t total_cnt;

	fprintf(fp, "\n");

	fprintf(fp, "\n"

	            "Path Length Statistics\n"

	            "----------------------\n"

	            "The regular path length is the number of nodes being visited,\n"

		    "where each node potentially evaluates several parsers. The\n"

		    "parser call statistic is the number of parsers called along\n"

		    "the path. That number is higher, as multiple parsers may be\n"

		    "called at each node. The number of literal parser calls is\n"

		    "given explicitely, as they use almost no time to process.\n"

		    "\n"

		);

	total_len = 0;

	total_cnt = 0;

	fprintf(fp, "Path Length\n");

	for(int i = 0 ; i < ADVSTATS_MAX_ENTITIES ; ++i) {

		if(advstats_pathlens[i] > 0 ) {

			fprintf(fp, "%3d: %d\n", i, advstats_pathlens[i]);

			total_len += i * advstats_pathlens[i];

			total_cnt += advstats_pathlens[i];

		}

	}

	fprintf(fp, "avg: %f\n", (double) total_len / (double) total_cnt);

	fprintf(fp, "max: %d\n", advstats_max_pathlen);

	fprintf(fp, "\n");

	total_len = 0;

	total_cnt = 0;

	fprintf(fp, "Nbr Backtracked\n");

	for(int i = 0 ; i < ADVSTATS_MAX_ENTITIES ; ++i) {

		if(advstats_backtracks[i] > 0 ) {

			fprintf(fp, "%3d: %d\n", i, advstats_backtracks[i]);

			total_len += i * advstats_backtracks[i];

			total_cnt += advstats_backtracks[i];

		}

	}

	fprintf(fp, "avg: %f\n", (double) total_len / (double) total_cnt);

	fprintf(fp, "max: %d\n", advstats_max_backtracked);

	fprintf(fp, "\n");

	/* we calc some stats while we output */

	total_len = 0;

	total_cnt = 0;

	fprintf(fp, "Parser Calls\n");

	for(int i = 0 ; i < ADVSTATS_MAX_ENTITIES ; ++i) {

		if(advstats_parser_calls[i] > 0 ) {

			fprintf(fp, "%3d: %d\n", i, advstats_parser_calls[i]);

			total_len += i * advstats_parser_calls[i];

			total_cnt += advstats_parser_calls[i];

		}

	}

	fprintf(fp, "avg: %f\n", (double) total_len / (double) total_cnt);

	fprintf(fp, "max: %d\n", advstats_max_parser_calls);

	fprintf(fp, "\n");

	total_len = 0;

	total_cnt = 0;

	fprintf(fp, "LITERAL Parser Calls\n");

	for(int i = 0 ; i < ADVSTATS_MAX_ENTITIES ; ++i) {

		if(advstats_lit_parser_calls[i] > 0 ) {

			fprintf(fp, "%3d: %d\n", i, advstats_lit_parser_calls[i]);

			total_len += i * advstats_lit_parser_calls[i];

			total_cnt += advstats_lit_parser_calls[i];

		}

	}

	fprintf(fp, "avg: %f\n", (double) total_len / (double) total_cnt);

	fprintf(fp, "max: %d\n", advstats_max_lit_parser_calls);

	fprintf(fp, "\n");

#endif

}

/**

 * Check if the provided dag is a leaf. This means that it

 * does not contain any subdags.

 * @return 1 if it is a leaf, 0 otherwise

 */

static inline int

isLeaf(struct ln_pdag *dag)

{

	return dag->nparsers == 0 ? 1 : 0;

}

/**

 * Add a parser instance to the pdag at the current position.

 *

 * @param[in] ctx

 * @param[in] prscnf json parser config *object* (no array!)

 * @param[in] pdag current pdag position (to which parser is to be added)

 * @param[in/out] nextnode contains point to the next node, either

 *            an existing one or one newly created.

 *

 * The nextnode parameter permits to use this function to create

 * multiple parsers alternative parsers with a single run. To do so,

 * set nextnode=NULL on first call. On successive calls, keep the

 * value. If a value is present, we will not accept non-identical

 * parsers which point to different nodes - this will result in an

 * error.

 *

 * IMPORTANT: the caller is responsible to update its pdag pointer

 *            to the nextnode value when he is done adding parsers.

 *

 * If a parser of the same type with identical data already exists,

 * it is "resued", which means the function is effectively used to

 * walk the path. This is used during parser construction to

 * navigate to new parts of the pdag.

 */

static int

ln_pdagAddParserInstance(ln_ctx ctx,

	json_object *const __restrict__ prscnf,

	struct ln_pdag *const __restrict__ pdag,

	struct ln_pdag **nextnode)

{

	int r;

	ln_parser_t *newtab;

	LN_DBGPRINTF(ctx, "ln_pdagAddParserInstance: %s, nextnode %p",

		json_object_to_json_string(prscnf), *nextnode);

	ln_parser_t *const parser = ln_newParser(ctx, prscnf);

	CHKN(parser);

	LN_DBGPRINTF(ctx, "pdag: %p, parser %p", pdag, parser);

	/* check if we already have this parser, if so, merge

	 */

	int i;

	for(i = 0 ; i < pdag->nparsers ; ++i) {

		LN_DBGPRINTF(ctx, "parser  comparison:\n%s\n%s",  pdag->parsers[i].conf, parser->conf);

		if(   pdag->parsers[i].prsid == parser->prsid

		   && !strcmp(pdag->parsers[i].conf, parser->conf)) {

		   	// FIXME: the current ->conf object is depending on

			//        the order of json elements. We should do a JSON

			//        comparison (a bit more complex). For now, it

			//        works like we do it now.

			// FIXME: if nextnode is set, check we can actually combine,

			//        else err out

			*nextnode = pdag->parsers[i].node;

			r = 0;

			LN_DBGPRINTF(ctx, "merging with pdag %p", pdag);

			pdagDeletePrs(ctx, parser); /* no need for data items */

			goto done;

		}

	}

	/* if we reach this point, we have a new parser type */

	if(*nextnode == NULL) {

		CHKN(*nextnode = ln_newPDAG(ctx)); /* we need a new node */

	} else {

		(*nextnode)->refcnt++;

	}

	parser->node = *nextnode;

	newtab = realloc(pdag->parsers, (pdag->nparsers+1) * sizeof(ln_parser_t));

	CHKN(newtab);

	pdag->parsers = newtab;

	memcpy(pdag->parsers+pdag->nparsers, parser, sizeof(ln_parser_t));

	pdag->nparsers++;