/**

 * @file ptree.c

 * @brief Implementation of the parse tree object.

 * @class ln_ptree ptree.h

 *//*

 * Copyright 2010 by Rainer Gerhards and Adiscon GmbH.

 *

 * Modified by Pavel Levshin (pavel@levshin.spb.ru) in 2013

 *

 * This file is part of liblognorm.

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * This library is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with this library; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA

 *

 * A copy of the LGPL v2.1 can be found in the file "COPYING" in this distribution.

 */

#include "config.h"

#include <stdlib.h>

#include <stdio.h>

#include <stdarg.h>

#include <string.h>

#include <assert.h>

#include <ctype.h>

#include <libestr.h>

#define LOGNORM_V1_SUBSYSTEM /* indicate we are old cruft */

#include "v1_liblognorm.h"

#include "annot.h"

#include "internal.h"

#include "lognorm.h"

#include "v1_ptree.h"

#include "v1_samp.h"

#include "v1_parser.h"

/**

 * Get base addr of common prefix. Takes length of prefix in account

 * and selects the right buffer.

 */

static inline unsigned char*

prefixBase(struct ln_ptree *tree)

{

	return (tree->lenPrefix <= sizeof(tree->prefix))

	       ? tree->prefix.data : tree->prefix.ptr;

}

struct ln_ptree*

ln_newPTree(ln_ctx ctx, struct ln_ptree **parentptr)

{

	struct ln_ptree *tree;

	if((tree = calloc(1, sizeof(struct ln_ptree))) == NULL)

		goto done;

	tree->parentptr = parentptr;

	tree->ctx = ctx;

	ctx->nNodes++;

done:	return tree;

}

void

ln_deletePTreeNode(ln_fieldList_t *node)

{

	ln_deletePTree(node->subtree);

	es_deleteStr(node->name);

	if(node->data != NULL)

		es_deleteStr(node->data);

	if(node->raw_data != NULL)

		es_deleteStr(node->raw_data);

	if(node->parser_data != NULL && node->parser_data_destructor != NULL)

		node->parser_data_destructor(&(node->parser_data));

	free(node);

}

void

ln_deletePTree(struct ln_ptree *tree)

{

	ln_fieldList_t *node, *nextnode;

	size_t i;

	if(tree == NULL)

		goto done;

	if(tree->tags != NULL)

		json_object_put(tree->tags);

	for(node = tree->froot; node != NULL; node = nextnode) {

		nextnode = node->next;

		ln_deletePTreeNode(node);

	}

	/* need to free a large prefix buffer? */

	if(tree->lenPrefix > sizeof(tree->prefix))

		free(tree->prefix.ptr);

	for(i = 0 ; i < 256 ; ++i)

		if(tree->subtree[i] != NULL)

			ln_deletePTree(tree->subtree[i]);

	free(tree);

done:	return;

}

/**

 * Set the common prefix inside a note, taking into account the subtle

 * issues associated with it.

 * @return 0 on success, something else otherwise

 */

static int

setPrefix(struct ln_ptree *tree, unsigned char *buf, size_t lenBuf, size_t offs)

{

	int r;

LN_DBGPRINTF(tree->ctx, "setPrefix lenBuf %zu, offs %zu", lenBuf, offs);

	tree->lenPrefix = lenBuf - offs;

	if(tree->lenPrefix > sizeof(tree->prefix)) {

		/* too-large for standard buffer, need to alloc one */

		if((tree->prefix.ptr = malloc(tree->lenPrefix * sizeof(unsigned char))) == NULL) {

			r = LN_NOMEM;

			goto done; /* fail! */

		}

		memcpy(tree->prefix.ptr, buf, tree->lenPrefix);

	} else {

		/* note: r->lenPrefix may be 0, but that is OK */

		memcpy(tree->prefix.data, buf, tree->lenPrefix);

	}

	r = 0;

done:	return r;

}

/**

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

 * does not contain any subtrees.

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

 */

static int

isLeaf(struct ln_ptree *tree)

{

	int r = 0;

	int i;

	if(tree->froot != NULL)

		goto done;

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

		if(tree->subtree[i] != NULL)

			goto done;

	}

	r = 1;

done:	return r;

}

/**

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

 * does not contain any subtrees of any kind and no prefix,

 * and it is not terminal leaf.

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

 */

static inline int

isTrueLeaf(struct ln_ptree *tree)

{

	return((tree->lenPrefix == 0) && isLeaf(tree)) && !tree->flags.isTerminal;

}

struct ln_ptree *

ln_addPTree(struct ln_ptree *tree, es_str_t *str, size_t offs)

{

	struct ln_ptree *r;

	struct ln_ptree **parentptr;	 /**< pointer in parent that needs to be updated */

LN_DBGPRINTF(tree->ctx, "addPTree: offs %zu", offs);

	parentptr = &(tree->subtree[es_getBufAddr(str)[offs]]);

	/* First check if tree node is totaly empty. If so, we can simply add

	 * the prefix to this node. This case is important, because it happens

	 * every time with a new field.

	 */

	if(isTrueLeaf(tree)) {

		if(setPrefix(tree, es_getBufAddr(str), es_strlen(str), offs) != 0) {

			r = NULL;

		} else {

			r = tree;

		}

		goto done;

	}

	if(tree->ctx->debug) {

		char *cstr = es_str2cstr(str, NULL);

		LN_DBGPRINTF(tree->ctx, "addPTree: add '%s', offs %zu, tree %p",

			     cstr + offs, offs, tree);

		free(cstr);

	}

	if((r = ln_newPTree(tree->ctx, parentptr)) == NULL)

		goto done;

	if(setPrefix(r, es_getBufAddr(str) + offs + 1, es_strlen(str) - offs - 1, 0) != 0) {

		free(r);

		r = NULL;

		goto done;

	}

	*parentptr = r;

done:	return r;

}

/**

 * Split the provided tree (node) into two at the provided index into its

 * common prefix. This function exists to support splitting nodes when

 * a mismatch in the common prefix requires that. This function more or less

 * keeps the tree as it is, just changes the structure. No new node is added.

 * Usually, it is desired to add a new node. This must be made afterwards.

 * Note that we need to create a new tree *in front of* the current one, as

 * the current one contains field etc. subtree pointers.

 * @param[in] tree tree to split

 * @param[in] offs offset into common prefix (must be less than prefix length!)

 */

static struct ln_ptree*

splitTree(struct ln_ptree *tree, unsigned short offs)

{

	unsigned char *c;

	struct ln_ptree *r;

	unsigned short newlen;

	ln_ptree **newparentptr;	 /**< pointer in parent that needs to be updated */

	assert(offs < tree->lenPrefix);

	if((r = ln_newPTree(tree->ctx, tree->parentptr)) == NULL)

		goto done;

	LN_DBGPRINTF(tree->ctx, "splitTree %p at offs %u", tree, offs);

	/* note: the overall prefix is reduced by one char, which is now taken

	 * care of inside the "branch table".

	 */

	c = prefixBase(tree);

//LN_DBGPRINTF(tree->ctx, "splitTree new bb, *(c+offs): '%s'", c);

	if(setPrefix(r, c, offs, 0) != 0) {

		ln_deletePTree(r);

		r = NULL;

		goto done; /* fail! */

	}

LN_DBGPRINTF(tree->ctx, "splitTree new tree %p lenPrefix=%u, char '%c'", r, r->lenPrefix, r->prefix.data[0]);

	/* add the proper branch table entry for the new node. must be done

	 * here, because the next step will destroy the required index char!

	 */

	newparentptr = &(r->subtree[c[offs]]);

	r->subtree[c[offs]] = tree;

	/* finally fix existing common prefix */

	newlen = tree->lenPrefix - offs - 1;

	if(tree->lenPrefix > sizeof(tree->prefix) && (newlen <= sizeof(tree->prefix))) {

		/* note: c is a different pointer; the original

		 * pointer is overwritten by memcpy! */

LN_DBGPRINTF(tree->ctx, "splitTree new case one bb, offs %u, lenPrefix %u, newlen %u", offs, tree->lenPrefix, newlen);

//LN_DBGPRINTF(tree->ctx, "splitTree new case one bb, *(c+offs): '%s'", c);

		memcpy(tree->prefix.data, c+offs+1, newlen);

		free(c);

	} else {

LN_DBGPRINTF(tree->ctx, "splitTree new case two bb, offs=%u, newlen %u", offs, newlen);

		memmove(c, c+offs+1, newlen);

	}

	tree->lenPrefix = tree->lenPrefix - offs - 1;

	if(tree->parentptr == 0)

		tree->ctx->ptree = r;	/* root does not have a parent! */

	else

		*(tree->parentptr) = r;

	tree->parentptr = newparentptr;

done:	return r;

}

struct ln_ptree *

ln_buildPTree(struct ln_ptree *tree, es_str_t *str, size_t offs)

{

	struct ln_ptree *r;

	unsigned char *c;

	unsigned char *cpfix;

	size_t i;

	unsigned short ipfix;

	assert(tree != NULL);

	LN_DBGPRINTF(tree->ctx, "buildPTree: begin at %p, offs %zu", tree, offs);

	c = es_getBufAddr(str);

	/* check if the prefix matches and, if not, at what offset it is different */

	ipfix = 0;

	cpfix = prefixBase(tree);

	for(  i = offs

	    ; (i < es_strlen(str)) && (ipfix < tree->lenPrefix) && (c[i] == cpfix[ipfix])

	    ; ++i, ++ipfix) {

	    	; /*DO NOTHING - just find end of match */

		LN_DBGPRINTF(tree->ctx, "buildPTree: tree %p, i %zu, char '%c'", tree, i, c[i]);

	}

	/* if we reach this point, we have processed as much of the common prefix

	 * as we could. The following code now does the proper actions based on

	 * the possible cases.

	 */

	if(i == es_strlen(str)) {

		/* all of our input is consumed, no more recursion */

		if(ipfix == tree->lenPrefix) {

			LN_DBGPRINTF(tree->ctx, "case 1.1");

			/* exact match, we are done! */

			r = tree;

		} else {

			LN_DBGPRINTF(tree->ctx, "case 1.2");

			/* we need to split the node at the current position */

			r = splitTree(tree, ipfix);

		}

	} else if(ipfix < tree->lenPrefix) {

			LN_DBGPRINTF(tree->ctx, "case 2, i=%zu, ipfix=%u", i, ipfix);

			/* we need to split the node at the current position */

			if((r = splitTree(tree, ipfix)) == NULL)

				goto done; /* fail */

LN_DBGPRINTF(tree->ctx, "pre addPTree: i %zu", i);

			if((r = ln_addPTree(r, str, i)) == NULL)

				goto done;

			//r = ln_buildPTree(r, str, i + 1);

	} else {

		/* we could consume the current common prefix, but now need

		 * to traverse the rest of the tree based on the next char.

		 */

		if(tree->subtree[c[i]] == NULL) {

			LN_DBGPRINTF(tree->ctx, "case 3.1");

			/* non-match, need new subtree */

			r = ln_addPTree(tree, str, i);

		} else {

			LN_DBGPRINTF(tree->ctx, "case 3.2");

			/* match, follow subtree */

			r = ln_buildPTree(tree->subtree[c[i]], str, i + 1);

		}

	}

//LN_DBGPRINTF(tree->ctx, "---------------------------------------");

//ln_displayPTree(tree, 0);

//LN_DBGPRINTF(tree->ctx, "=======================================");

done:	return r;

}

int

ln_addFDescrToPTree(struct ln_ptree **tree, ln_fieldList_t *node)

{

	int r;

	ln_fieldList_t *curr;

	assert(tree != NULL);assert(*tree != NULL);

	assert(node != NULL);

	if((node->subtree = ln_newPTree((*tree)->ctx, &node->subtree)) == NULL) {

		r = -1;

		goto done;

	}

	LN_DBGPRINTF((*tree)->ctx, "got new subtree %p", node->subtree);

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

	 * TODO: optimized, check logic

	 */

	for(curr = (*tree)->froot ; curr != NULL ; curr = curr->next) {

		if(!es_strcmp(curr->name, node->name)

				&& curr->parser == node->parser

				&& ((curr->raw_data == NULL && node->raw_data == NULL)

					|| (curr->raw_data != NULL && node->raw_data != NULL

						&& !es_strcmp(curr->raw_data, node->raw_data)))) {

			*tree = curr->subtree;

			ln_deletePTreeNode(node);

			r = 0;

			LN_DBGPRINTF((*tree)->ctx, "merging with tree %p\n", *tree);

			goto done;

		}

	}

	if((*tree)->froot == NULL) {

		(*tree)->froot = (*tree)->ftail = node;

	} else {

		(*tree)->ftail->next = node;

		(*tree)->ftail = node;

	}

	r = 0;

	LN_DBGPRINTF((*tree)->ctx, "prev subtree %p", *tree);

	*tree = node->subtree;

	LN_DBGPRINTF((*tree)->ctx, "new subtree %p", *tree);

done:	return r;

}

void

ln_displayPTree(struct ln_ptree *tree, int level)

{

	int i;

	int nChildLit;

	int nChildField;

	es_str_t *str;

	char *cstr;

	ln_fieldList_t *node;

	char indent[2048];

	if(level > 1023)

		level = 1023;

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

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

	nChildField = 0;

	for(node = tree->froot ; node != NULL ; node = node->next ) {

		++nChildField;

	}

	nChildLit = 0;

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

		if(tree->subtree[i] != NULL) {

			nChildLit++;

		}

	}

	str = es_newStr(sizeof(tree->prefix));

	es_addBuf(&str, (char*) prefixBase(tree), tree->lenPrefix);

	cstr = es_str2cstr(str, NULL);

	es_deleteStr(str);

	LN_DBGPRINTF(tree->ctx, "%ssubtree%s %p (prefix: '%s', children: %d literals, %d fields) [visited %u "

	"backtracked %u terminated %u]",

			indent, tree->flags.isTerminal ? " TERM" : "", tree, cstr, nChildLit, nChildField,

			tree->stats.visited, tree->stats.backtracked, tree->stats.terminated);

	free(cstr);

	/* display char subtrees */

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

		if(tree->subtree[i] != NULL) {

			LN_DBGPRINTF(tree->ctx, "%schar %2.2x(%c):", indent, i, i);

			ln_displayPTree(tree->subtree[i], level + 1);

		}

	}

	/* display field subtrees */

	for(node = tree->froot ; node != NULL ; node = node->next ) {

		cstr = es_str2cstr(node->name, NULL);

		LN_DBGPRINTF(tree->ctx, "%sfield %s:", indent, cstr);

		free(cstr);

		ln_displayPTree(node->subtree, level + 1);

	}

}

/* the following is a quick hack, which should be moved to the

 * string class.

 */

static inline void dotAddPtr(es_str_t **str, void *p)

{

	char buf[64];

	int i;

	i = snprintf(buf, sizeof(buf), "%p", p);

	es_addBuf(str, buf, i);

}

/**

 * recursive handler for DOT graph generator.

 */

static void

ln_genDotPTreeGraphRec(struct ln_ptree *tree, es_str_t **str)

{

	int i;

	ln_fieldList_t *node;

	dotAddPtr(str, tree);

	es_addBufConstcstr(str, " [label=\"");

	if(tree->lenPrefix > 0) {

		es_addChar(str, '\'');

		es_addBuf(str, (char*) prefixBase(tree), tree->lenPrefix);

		es_addChar(str, '\'');

	}

	es_addBufConstcstr(str, "\"");

	if(isLeaf(tree)) {

		es_addBufConstcstr(str, " style=\"bold\"");

	}

	es_addBufConstcstr(str, "]\n");

	/* display char subtrees */

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

		if(tree->subtree[i] != NULL) {

			dotAddPtr(str, tree);

			es_addBufConstcstr(str, " -> ");

			dotAddPtr(str, tree->subtree[i]);

			es_addBufConstcstr(str, " [label=\"");

			es_addChar(str, (char) i);

			es_addBufConstcstr(str, "\"]\n");

			ln_genDotPTreeGraphRec(tree->subtree[i], str);

		}

	}

	/* display field subtrees */

	for(node = tree->froot ; node != NULL ; node = node->next ) {

		dotAddPtr(str, tree);

		es_addBufConstcstr(str, " -> ");

		dotAddPtr(str, node->subtree);

		es_addBufConstcstr(str, " [label=\"");

		es_addStr(str, node->name);

		es_addBufConstcstr(str, "\" style=\"dotted\"]\n");

		ln_genDotPTreeGraphRec(node->subtree, str);

	}

}

void

ln_genDotPTreeGraph(struct ln_ptree *tree, es_str_t **str)

{

	es_addBufConstcstr(str, "digraph ptree {\n");

	ln_genDotPTreeGraphRec(tree, str);

	es_addBufConstcstr(str, "}\n");

}

/**

 * add unparsed string to event.

 */

static int

addUnparsedField(const char *str, size_t strLen, int offs, struct json_object *json)

{

	int r = 1;

	struct json_object *value;

	char *s = NULL;

	CHKN(s = strndup(str, strLen));

	value = json_object_new_string(s);

	if (value == NULL) {

		goto done;

	}

	json_object_object_add(json, ORIGINAL_MSG_KEY, value);

	value = json_object_new_string(s + offs);

	if (value == NULL) {

		goto done;

	}

	json_object_object_add(json, UNPARSED_DATA_KEY, value);

	r = 0;

done:

	free(s);

	return r;

}

/**

 * Special parser for iptables-like name/value pairs.

 * The pull multiple fields. Note that once this parser has been selected,

 * it is very unlikely to be left, as it is *very* generic. This parser is

 * required because practice shows that already-structured data like iptables

 * can otherwise not be processed by liblognorm in a meaningful way.

 *

 * @param[in] tree current tree to process

 * @param[in] str string to be matched against (the to-be-normalized data)

 * @param[in] strLen length of str

 * @param[in/out] offs start position in input data, on exit first unparsed position

 * @param[in/out] event handle to event that is being created during normalization

 *

 * @return 0 if parser was successfully, something else on error

 */

static int

ln_iptablesParser(struct ln_ptree *tree, const char *str, size_t strLen, size_t *offs,

		  struct json_object *json)

{

	int r;

	size_t o = *offs;

	es_str_t *fname;

	es_str_t *fval;

	const char *pstr;

	const char *end;

	struct json_object *value;

LN_DBGPRINTF(tree->ctx, "%zu enter iptables parser, len %zu", *offs, strLen);

	if(o == strLen) {

		r = -1; /* can not be, we have no n/v pairs! */

		goto done;

	}

	end = str + strLen;

	pstr = str + o;

	while(pstr < end) {

		while(pstr < end && isspace(*pstr))

			++pstr;

		CHKN(fname = es_newStr(16));

		while(pstr < end && !isspace(*pstr) && *pstr != '=') {

			es_addChar(&fname, *pstr);

			++pstr;

		}

		if(pstr < end && *pstr == '=') {

			CHKN(fval = es_newStr(16));

			++pstr;

			/* error on space */

			while(pstr < end && !isspace(*pstr)) {

				es_addChar(&fval, *pstr);

				++pstr;

			}

		} else {

			CHKN(fval = es_newStrFromCStr("[*PRESENT*]",

					sizeof("[*PRESENT*]")-1));

		}

		char *cn, *cv;

		CHKN(cn = ln_es_str2cstr(&fname));

		CHKN(cv = ln_es_str2cstr(&fval));

		if (tree->ctx->debug) {

			LN_DBGPRINTF(tree->ctx, "iptables parser extracts %s=%s", cn, cv);

		}

		CHKN(value = json_object_new_string(cv));

		json_object_object_add(json, cn, value);

		es_deleteStr(fval);

		es_deleteStr(fname);

	}

	r = 0;

	*offs = strLen;

done:

	LN_DBGPRINTF(tree->ctx, "%zu iptables parser returns %d", *offs, r);

	return r;

}

/**

 * Recursive step of the normalizer. It walks the parse tree and calls itself

 * recursively when this is appropriate. It also implements backtracking in

 * those (hopefully rare) cases where it is required.

 *

 * @param[in] tree current tree to process

 * @param[in] string string to be matched against (the to-be-normalized data)

 * @param[in] strLen length of the to-be-matched string

 * @param[in] offs start position in input data

 * @param[in/out] json ... that is being created during normalization

 * @param[out] endNode if a match was found, this is the matching node (undefined otherwise)

 *

 * @return number of characters left unparsed by following the subtree, negative if

 *         the to-be-parsed message is shorter than the rule sample by this number of

 *         characters.

 */

static int

ln_v1_normalizeRec(struct ln_ptree *tree, const char *str, size_t strLen, size_t offs, struct json_object *json,

		struct ln_ptree **endNode)

{

	int r;

	int localR;

	size_t i;

	int left;

	ln_fieldList_t *node;

	ln_fieldList_t *restMotifNode = NULL;

	char *cstr;

	const char *c;

	unsigned char *cpfix;

	unsigned ipfix;

	size_t parsed;

	char *namestr;

	struct json_object *value;

	++tree->stats.visited;

	if(offs >= strLen) {

		*endNode = tree;

		r = -tree->lenPrefix;

		goto done;

	}

LN_DBGPRINTF(tree->ctx, "%zu: enter parser, tree %p", offs, tree);

	c = str;

	cpfix = prefixBase(tree);

	node = tree->froot;

	r = strLen - offs;

	/* first we need to check if the common prefix matches (and consume input data while we do) */

	ipfix = 0;

	while(offs < strLen && ipfix < tree->lenPrefix) {

		LN_DBGPRINTF(tree->ctx, "%zu: prefix compare '%c', '%c'", offs, c[offs], cpfix[ipfix]);

		if(c[offs] != cpfix[ipfix]) {

			r -= ipfix;

			goto done;

		}

		++offs, ++ipfix;

	}

	if(ipfix != tree->lenPrefix) {

		/* incomplete prefix match --> to-be-normalized string too short */

		r = ipfix - tree->lenPrefix;

		goto done;

	}

	r -= ipfix;

	LN_DBGPRINTF(tree->ctx, "%zu: prefix compare succeeded, still valid", offs);

	/* now try the parsers */

	while(node != NULL) {

		if(tree->ctx->debug) {

			cstr = es_str2cstr(node->name, NULL);

			LN_DBGPRINTF(tree->ctx, "%zu:trying parser for field '%s': %p",

					offs, cstr, node->parser);

			free(cstr);

		}

		i = offs;

		if(node->isIPTables) {

			localR = ln_iptablesParser(tree, str, strLen, &i, json);

			LN_DBGPRINTF(tree->ctx, "%zu iptables parser return, i=%zu",

						offs, i);

			if(localR == 0) {

				/* potential hit, need to verify */

				LN_DBGPRINTF(tree->ctx, "potential hit, trying subtree");

				left = ln_v1_normalizeRec(node->subtree, str, strLen, i, json, endNode);

				if(left == 0 && (*endNode)->flags.isTerminal) {

					LN_DBGPRINTF(tree->ctx, "%zu: parser matches at %zu", offs, i);

					r = 0;

					goto done;

				}

				LN_DBGPRINTF(tree->ctx, "%zu nonmatch, backtracking required, left=%d",

						offs, left);

				++tree->stats.backtracked;

				if(left < r)

					r = left;

			}

		} else if(node->parser == ln_parseRest) {

			/* This is a quick and dirty adjustment to handle "rest" more intelligently.

			 * It's just a tactical fix: in the longer term, we'll handle the whole

			 * situation differently. However, it makes sense to fix this now, as this

			 * solves some real-world problems immediately. -- rgerhards, 2015-04-15

			 */

			restMotifNode = node;

		} else {

			value = NULL;

			localR = node->parser(str, strLen, &i, node, &parsed, &value);

			LN_DBGPRINTF(tree->ctx, "parser returns %d, parsed %zu", localR, parsed);

			if(localR == 0) {

				/* potential hit, need to verify */

				LN_DBGPRINTF(tree->ctx, "%zu: potential hit, trying subtree %p", offs, node->subtree);

				left = ln_v1_normalizeRec(node->subtree, str, strLen, i + parsed, json, endNode);

				LN_DBGPRINTF(tree->ctx, "%zu: subtree returns %d", offs, r);

				if(left == 0 && (*endNode)->flags.isTerminal) {

					LN_DBGPRINTF(tree->ctx, "%zu: parser matches at %zu", offs, i);

					if(es_strbufcmp(node->name, (unsigned char*)"-", 1)) {

						/* Store the value here; create json if not already created */

						if (value == NULL) {

							CHKN(cstr = strndup(str + i, parsed));

							value = json_object_new_string(cstr);

							free(cstr);

						}

						if (value == NULL) {

							LN_DBGPRINTF(tree->ctx, "unable to create json");

							goto done;

						}

						namestr = ln_es_str2cstr(&node->name);

						json_object_object_add(json, namestr, value);

					} else {

						if (value != NULL) {

							/* Free the unneeded value */

							json_object_put(value);

						}

					}

					r = 0;

					goto done;

				}

				LN_DBGPRINTF(tree->ctx, "%zu nonmatch, backtracking required, left=%d",

						offs, left);

				if (value != NULL) {

					/* Free the value if it was created */

					json_object_put(value);

				}

				if(left > 0 && left < r)

					r = left;

				LN_DBGPRINTF(tree->ctx, "%zu nonmatch, backtracking required, left=%d, r now %d",

						offs, left, r);

				++tree->stats.backtracked;

			}

		}

		node = node->next;

	}

	if(offs == strLen) {

		*endNode = tree;

		r = 0;

		goto done;

	}

if(offs < strLen) {

unsigned char cc = str[offs];

LN_DBGPRINTF(tree->ctx, "%zu no field, trying subtree char '%c': %p", offs, cc, tree->subtree[cc]);

} else {

LN_DBGPRINTF(tree->ctx, "%zu no field, offset already beyond end", offs);

}

	/* now let's see if we have a literal */

	if(tree->subtree[(unsigned char)str[offs]] != NULL) {

		left = ln_v1_normalizeRec(tree->subtree[(unsigned char)str[offs]],

				       str, strLen, offs + 1, json, endNode);

LN_DBGPRINTF(tree->ctx, "%zu got left %d, r %d", offs, left, r);

		if(left < r)

			r = left;

LN_DBGPRINTF(tree->ctx, "%zu got return %d", offs, r);

	}

	if(r == 0 && (*endNode)->flags.isTerminal)

		goto done;

	/* and finally give "rest" a try if it was present. Note that we MUST do this after

	 * literal evaluation, otherwise "rest" can never be overriden by other rules.

	 */

	if(restMotifNode != NULL) {

		LN_DBGPRINTF(tree->ctx, "rule has rest motif, forcing match via it");

		value = NULL;

		restMotifNode->parser(str, strLen, &i, restMotifNode, &parsed, &value);

#		ifndef NDEBUG

		left = /* we only need this for the assert below */

#		endif

		       ln_v1_normalizeRec(restMotifNode->subtree, str, strLen, i + parsed, json, endNode);

		assert(left == 0); /* with rest, we have this invariant */

		assert((*endNode)->flags.isTerminal); /* this one also */

		LN_DBGPRINTF(tree->ctx, "%zu: parser matches at %zu", offs, i);

		if(es_strbufcmp(restMotifNode->name, (unsigned char*)"-", 1)) {

			/* Store the value here; create json if not already created */

			if (value == NULL) {

				CHKN(cstr = strndup(str + i, parsed));

				value = json_object_new_string(cstr);

				free(cstr);

			}

			if (value == NULL) {

				LN_DBGPRINTF(tree->ctx, "unable to create json");

				goto done;

			}

			namestr = ln_es_str2cstr(&restMotifNode->name);

			json_object_object_add(json, namestr, value);

		} else {

			if (value != NULL) {

				/* Free the unneeded value */

				json_object_put(value);

			}

		}

		r = 0;

		goto done;

	}

done:

	LN_DBGPRINTF(tree->ctx, "%zu returns %d", offs, r);

	if(r == 0 && *endNode == tree)

		++tree->stats.terminated;

	return r;

}

int

ln_v1_normalize(ln_ctx ctx, const char *str, size_t strLen, struct json_object **json_p)

{

	int r;

	int left;

	struct ln_ptree *endNode = NULL;

	if(*json_p == NULL) {

		CHKN(*json_p = json_object_new_object());

	}

	left = ln_v1_normalizeRec(ctx->ptree, str, strLen, 0, *json_p, &endNode);

	if(ctx->debug) {

		if(left == 0) {

			LN_DBGPRINTF(ctx, "final result for normalizer: left %d, endNode %p, "

				     "isTerminal %d, tagbucket %p",

				     left, endNode, endNode->flags.isTerminal, endNode->tags);

		} else {

			LN_DBGPRINTF(ctx, "final result for normalizer: left %d, endNode %p",

				     left, endNode);

		}

	}

	if(left != 0 || !endNode->flags.isTerminal) {

		/* we could not successfully parse, some unparsed items left */

		if(left < 0) {

			addUnparsedField(str, strLen, strLen, *json_p);

		} else {