/*
 *   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 St, Fifth Floor, Boston, MA 02110-1301, USA
 */

/**
 * $Id: 64d211a250036ca5102ed65474d431be3773b387 $
 *
 * @file src/lib/util/edit.c
 * @brief Functions to edit pair lists, and track undo operations
 *
 *  This file implements an "edit list" for changing values of
 *  #fr_pair_t.  After some investigation, it turns out that it's much
 *  easier to have an "undo list" than to track partially applied
 *  transactions.  Tracking partial transactions means that none of
 *  the fr_pair_foo() functions will work, as some pairs are in the
 *  "old" list and some in the "new" list.  Also, a transaction may
 *  still fail when we finalize it by moving the pairs around.
 *
 *  In contrast, an "undo" list means that all of the fr_pair_foo()
 *  functions will work, as any list contains only "active" pairs.
 *  And we never need to "finalize" a transaction, as the lists are
 *  already in their final form.  The only thing needed for
 *  finalization is to free the undo list.  Which can never fail.
 *
 *  Note that the functions here require the input VPs to already have
 *  the correct talloc parent!  The only thing the edit list does is
 *  to record "undo" actions.
 *
 *  The only exception to this is fr_edit_list_apply_list_assignment().
 *  Which does call talloc_steal, and then also frees any pairs which
 *  weren't applied to the LHS.
 *
 * @copyright 2021 Network RADIUS SAS (legal@networkradius.com)
 */

RCSID("$Id: 64d211a250036ca5102ed65474d431be3773b387 $")

#include <freeradius-devel/util/value.h>
#include <freeradius-devel/util/talloc.h>
#include "edit.h"
#include "calc.h"

typedef enum {
	FR_EDIT_INVALID = 0,
	FR_EDIT_DELETE,			//!< delete a VP
	FR_EDIT_VALUE,			//!< edit a VP in place
	FR_EDIT_CLEAR,			//!< clear the children of a structural entry.
	FR_EDIT_INSERT,			//!< insert a VP into a list, after another one.
	FR_EDIT_CHILD,			//!< child edit list
} fr_edit_op_t;

#if 0
/*
 *	For debugging.
 */
static const char *edit_names[4] = {
	"invalid",
	"delete",
	"value",
	"clear",
	"insert",
};
#endif

/** Track one particular edit.
 */
typedef struct {
	fr_edit_op_t	op;		//!< edit operation to perform
	fr_dlist_t	entry;		//!< linked list of edits

	fr_pair_t	*vp;		//!< pair edited, deleted, or inserted

	union {
		union {
			fr_value_box_t	data;	//!< original data
			fr_pair_list_t	children;  //!< original child list, for "clear"
			fr_edit_list_t	*child_edit;
		};

		struct {
			fr_pair_list_t	*list; //!< parent list
			fr_pair_t	*ref;	//!< reference pair for delete, insert before/after
		};
	};
} fr_edit_t;

/** Track a series of edits.
 *
 */
struct fr_edit_list_s {
	/*
	 *	List of undo changes to be made, in order.
	 */
	fr_dlist_head_t	undo;

	fr_dlist_head_t	ignore;		//!< lists to ignore

	/*
	 *	VPs which were inserted, and then over-written by a
	 *	later edit.
	 */
	fr_pair_list_t	deleted_pairs;

	fr_edit_list_t	*parent;	//!< for nested transactions
	fr_edit_t	*e;		//!< so we don't have to loop over parent edits on abort
};

typedef struct {
	fr_dlist_t	entry;
	fr_pair_list_t	*list;		//!< list to ignore (never dereferenced)
} fr_edit_ignore_t;


static bool fr_edit_list_empty(fr_edit_list_t *el)
{
	return fr_dlist_empty(&el->undo) && fr_dlist_empty(&el->ignore) && fr_pair_list_empty(&el->deleted_pairs);
}

/** Undo one particular edit.
 */
static int edit_undo(fr_edit_t *e)
{
	fr_pair_t *vp = e->vp;
#ifndef NDEBUG
	int rcode;
#endif

	fr_assert(vp != NULL);
	PAIR_VERIFY(vp);

	switch (e->op) {
	case FR_EDIT_INVALID:
		return -1;

	case FR_EDIT_VALUE:
		fr_assert(fr_type_is_leaf(vp->vp_type));
		if (!fr_type_is_fixed_size(vp->vp_type)) fr_value_box_clear(&vp->data);
		fr_value_box_copy(vp, &vp->data, &e->data);
		break;

	case FR_EDIT_CLEAR:
		fr_assert(fr_type_is_structural(vp->vp_type));

		fr_pair_list_free(&vp->vp_group);
		fr_pair_list_append(&vp->vp_group, &e->children);
		break;

	case FR_EDIT_DELETE:
		fr_assert(e->list != NULL);
#ifndef NDEBUG
		rcode =
#endif
		fr_pair_insert_after(e->list, e->ref, vp);
		fr_assert(rcode == 0);
		break;

	case FR_EDIT_INSERT:
		/*
		 *	We can free the VP here, as any edits to its'
		 *	children MUST come after the creation of the
		 *	VP.  And any deletion of VPs after this one
		 *	must come after this VP was created.
		 */
		fr_pair_delete(e->list, vp);
		break;

	case FR_EDIT_CHILD:
		fr_edit_list_abort(e->child_edit);
		break;
	}

	return 0;
}

/** Abort the entries in an edit list.
 *
 *  After this call, the input list(s) are unchanged from before any
 *  edits were made.
 *
 *  the caller does not have to call talloc_free(el);
 */
void fr_edit_list_abort(fr_edit_list_t *el)
{
	fr_edit_t *e;

	if (!el) return;

	/*
	 *      All of these pairs are already in the edit list.  They
	 *      have the correct parent, and will be placed back into
	 *      their correct location by edit_undo()
	 */
	fr_pair_list_init(&el->deleted_pairs);

	/*
	 *	Undo edits in reverse order, as later edits depend on
	 *	earlier ones.  We don't have multiple edits of the
	 *	same VP, but we can create a VP, and then later edit
	 *	its children.
	 */
	while ((e = fr_dlist_pop_tail(&el->undo)) != NULL) {
		edit_undo(e);
		/*
		 *	Don't free "e", it will be cleaned up when we
		 *	talloc_free(el).  That should be somewhat
		 *	faster than doing it incrementally.
		 */
	}

	/*
	 *	There's a parent, we remove ourselves from the parent undo list.
	 */
	if (el->parent) {
		fr_dlist_remove(&el->parent->undo, el->e);
		talloc_free(el->e);
	}

	talloc_free(el);
}

/** Record one particular edit
 *
 *  For INSERT / DELETE, this function will also insert / delete the
 *  VP.
 *
 *  For VALUE changes, this function must be called BEFORE the value
 *  is changed.  Once this function has been called, it is then safe
 *  to edit the value in place.
 *
 *  Note that VALUE changes for structural types are allowed ONLY when
 *  using T_OP_SET, which over-writes previous values.  For every
 *  other modification to structural types, we MUST instead call
 *  insert / delete on the vp_group.
 */
static int edit_record(fr_edit_list_t *el, fr_edit_op_t op, fr_pair_t *vp, fr_pair_list_t *list, fr_pair_t *ref)
{
	fr_edit_t *e;

	fr_assert(el != NULL);
	fr_assert(vp != NULL);

	fr_assert(op != FR_EDIT_CHILD); /* only used by fr_edit_alloc() */

	/*
	 *	When we insert a structural type, we also want to
	 *	not track edits to it's children.  The "ignore list"
	 *	allows us to see which lists don't have edits recorded.
	 *
	 *	Perform the operation.  We're not recording
	 *	it, but we still need to do the work.
	 */
	fr_dlist_foreach(&el->ignore, fr_edit_ignore_t, i) {
		if (i->list != list) continue;

		switch (op) {
			/*
			 *	No need to save the value.
			 */
		case FR_EDIT_VALUE:
			return 0;

			/*
			 *	No need to save the value.
			 */
		case FR_EDIT_DELETE:
			fr_pair_remove(list, vp);
			return 0;

			/*
			 *	Delete all of the children.
			 */
		case FR_EDIT_CLEAR:
			if (!fr_type_is_structural(vp->vp_type)) return 0;

			/*
			 *	The VP is a child of an attribute which was previously inserted as part of
			 *	this edit.  We therefore allow the "clear" to clear it, even if it contains
			 *	immutable children.  Because this operation is equivalent to just never
			 *	creating the children.
			 */

			fr_pair_list_free(&vp->vp_group);
			return 0;

			/*
			 *	Insert it, and perhaps save the list
			 *	for a structural VP saying "don't
			 *	record edits to this, either".
			 */
		case FR_EDIT_INSERT:
			if (fr_pair_insert_after(list, ref, vp) < 0) return -1;

			/*
			 *	Non-structural types don't have any other work to do.
			 */
			if (!fr_type_is_structural(vp->vp_type)) return 0;

			/*
			 *	Otherwise we're inserting a VP which has a
			 *	child list.  Remember that we need to ignore
			 *	edits to the children of this VP, too.
			 */
			goto insert_ignore;

		default:
			return -1;
		}
	}

	/*
	 *	Catch NOOPs
	 */
	if (op == FR_EDIT_CLEAR) {
		fr_assert(fr_type_is_structural(vp->vp_type));

		if (fr_pair_list_empty(&vp->vp_group)) return 0;
	}

	/*
	 *	Search for previous edits.
	 *
	 *	@todo - if we're modifying values of a child VP, and
	 *	it's parent is marked as INSERT, then we don't need to
	 *	record FR_EDIT_VALUE changes to the children.  It's
	 *	not yet clear how best to track this.
	 */
	for (e = fr_dlist_head(&el->undo);
	     e != NULL;
	     e = fr_dlist_next(&el->undo, e)) {
		fr_assert(e->vp != NULL);

		if (e->vp != vp) continue;

		switch (op) {
		case FR_EDIT_INVALID:
			return -1;

			/*
			 *	We're editing a previous edit.
			 *	There's no need to record anything
			 *	new, as we've already recorded the
			 *	original value.
			 *
			 *	Note that we can insert a pair and
			 *	then edit it.  The undo list only
			 *	saves the insert, as the later edit is
			 *	irrelevant.  If we're undoing, we
			 *	simply delete the new attribute which
			 *	was inserted.
			 */
		case FR_EDIT_VALUE:
			/*
			 *	If we delete a pair, we can't later
			 *	edit it.  That indicates serious
			 *	issues with the code.
			 *
			 *      However, if we previously inserted
			 *      this VP, then we don't need to record
			 *      changes to its value.  Similarly, if
			 *      we had previously changed its value,
			 *      we don't need to record that
			 *      information again.
                         */
			fr_assert(e->op != FR_EDIT_DELETE);
			fr_assert(fr_type_is_leaf(vp->vp_type));
			return 0;

			/*
			 *	We're inserting a new pair.
			 *
			 *	We can't have previously edited this
			 *	pair (inserted, deleted, or updated
			 *	the value), as the pair is new!
			 */
		case FR_EDIT_INSERT:
			fr_assert(0);
			return -1;

		case FR_EDIT_CLEAR:
			/*
			 *	If we're clearing it, we MUST have
			 *	previously inserted it.  So just nuke
			 *	it's children, as merging the
			 *	operations of "insert with stuff" and
			 *	then "clear" is just "insert empty
			 *	pair".
			 *
			 *	However, we don't yet delete the
			 *	children, as there may be other edit
			 *	operations which are referring to
			 *	them.
			 */
			fr_assert(e->op == FR_EDIT_INSERT);
			fr_assert(fr_type_is_structural(vp->vp_type));

			fr_pair_list_append(&el->deleted_pairs, &vp->vp_group);
			break;

			/*
			 *	We're being asked to delete something
			 *	we previously inserted, or previously
			 *	edited.
			 */
		case FR_EDIT_DELETE:
			/*
			 *	We can't delete something which was
			 *	already deleted.
			 */
			fr_assert(e->op != FR_EDIT_DELETE);

			/*
			 *	We had previously inserted it.  So
			 *	just delete the insert operation, and
			 *	delete the VP from the list.
			 *
			 *	Other edits may refer to children of
			 *	this pair.  So we don't free the VP
			 *	immediately, but instead reparent it
			 *	to the edit list.  So that when the
			 *	edit list is freed, the VP will be
			 *	freed.
			 */
			if (e->op == FR_EDIT_INSERT) {
				fr_assert(e->list == list);

				fr_pair_remove(list, vp);
				fr_pair_append(&el->deleted_pairs, vp);

				fr_dlist_remove(&el->undo, e);
				talloc_free(e);
				return 0;
			}

			/*
			 *	We had previously changed the value,
			 *	but now we're going to delete it.
			 *
			 *	Since it had previously existed, we
			 *	have to reset its value to the
			 *	original one, and then track the
			 *	deletion.
			 */
			edit_undo(e);

			/*
			 *	Rewrite the edit to be delete.
			 *
			 *	And move the deletion to the tail of
			 *	the edit list, because edits between
			 *	"here" and the tail of the list may
			 *	refer to "vp".  If we leave the
			 *	deletion in place, then subsequent
			 *	edit list entries will refer to a VP
			 *	which has been deleted!
			 */
			e->op = FR_EDIT_DELETE;
			fr_dlist_remove(&el->undo, e);
			goto delete;

		case FR_EDIT_CHILD: /* e->vp==NULL, so this should never happen */
			fr_assert(0);
			return -1;
		}
	} /* loop over existing edits */

	/*
	 *	No edit for this pair exists.  Create a new edit entry.
	 */
	e = talloc_zero(el, fr_edit_t);
	if (!e) return -1;

	e->op = op;
	e->vp = vp;
	fr_value_box_init_null(&e->data);

	switch (op) {
	case FR_EDIT_INVALID:
	case FR_EDIT_CHILD:
	fail:
		talloc_free(e);
		return -1;

	case FR_EDIT_VALUE:
		fr_assert(list == NULL);
		fr_assert(ref == NULL);

		fr_assert(fr_type_is_leaf(vp->vp_type));
		fr_value_box_copy(e, &e->data, &vp->data);
		break;

	case FR_EDIT_CLEAR:
		fr_assert(list == NULL);
		fr_assert(ref == NULL);

		fr_assert(fr_type_is_structural(vp->vp_type));
		fr_pair_list_init(&e->children);
		fr_pair_list_append(&e->children, &vp->vp_group);
		break;

	case FR_EDIT_INSERT:
		fr_assert(list != NULL);

		/*
		 *	There's no need to record "prev".  On undo, we
		 *	just delete this pair from the list.
		 */
		e->list = list;
		if (fr_pair_insert_after(list, ref, vp) < 0) goto fail;
		break;

	case FR_EDIT_DELETE:
	delete:
		fr_assert(list != NULL);
		fr_assert(ref == NULL);

		e->list = list;
		e->ref = fr_pair_list_prev(list, vp);

		fr_pair_remove(list, vp);
		break;
	}

	fr_dlist_insert_tail(&el->undo, e);

	/*
	 *	Insert an "ignore" entry.
	 */
	if ((op == FR_EDIT_INSERT) && fr_type_is_structural(vp->vp_type)) {
		fr_edit_ignore_t *i;

	insert_ignore:
		i = talloc_zero(el, fr_edit_ignore_t);
		if (!i) return 0;

		i->list = &vp->vp_group;
		fr_dlist_insert_tail(&el->ignore, i);
	}

	return 0;
}


/** Insert a new VP after an existing one.
 *
 *  This function mirrors fr_pair_insert_after().
 *
 *  After this function returns, the new VP has been inserted into the
 *  list.
 */
int fr_edit_list_insert_pair_after(fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_t *pos, fr_pair_t *vp)
{
	if (!el) return fr_pair_insert_after(list, pos, vp);

	return edit_record(el, FR_EDIT_INSERT, vp, list, pos);
}

/** Delete a VP
 *
 *  This function mirrors fr_pair_delete()
 *
 *  After this function returns, the VP has been removed from the list.
 */
int fr_edit_list_pair_delete(fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_t *vp)
{
	if (fr_pair_immutable(vp)) {
		fr_strerror_printf("Cannot modify immutable value for %s", vp->da->name);
		return -1;
	}

	if (!el) {
		fr_pair_delete(list, vp);
		return 0;
	}

	return edit_record(el, FR_EDIT_DELETE, vp, list, NULL);
}

/** Delete VPs with a matching da
 *
 *  This function mirrors fr_pair_delete_by_da()
 */
int fr_edit_list_pair_delete_by_da(fr_edit_list_t *el, fr_pair_list_t *list, fr_dict_attr_t const *da)
{
	if (!el) {
		fr_pair_delete_by_da(list, da);
		return 0;
	}

	/*
	 *	Delete all VPs with a matching da.
	 */
	fr_pair_list_foreach(list, vp) {
		if (fr_pair_immutable(vp)) continue;

		if (vp->da != da) continue;

		(void) fr_pair_remove(list, vp);

		if (edit_record(el, FR_EDIT_DELETE, vp, list, NULL) < 0) return -1;
	}

	return 0;
}


/** Record the value of a leaf #fr_value_box_t
 *
 *  After this function returns, it's safe to edit the pair.
 */
int fr_edit_list_save_pair_value(fr_edit_list_t *el, fr_pair_t *vp)
{
	if (!el) return 0;

	if (!fr_type_is_leaf(vp->vp_type)) return -1;

	return edit_record(el, FR_EDIT_VALUE, vp, NULL, NULL);
}

/** Write a new value to the #fr_value_box_t
 *
 *  After this function returns, the value has been updated.
 */
int fr_edit_list_replace_pair_value(fr_edit_list_t *el, fr_pair_t *vp, fr_value_box_t *box)
{
	if (!fr_type_is_leaf(vp->vp_type)) return -1;

	if (vp->vp_immutable) {
		fr_strerror_printf("Cannot modify immutable value for %s", vp->da->name);
		return -1;
	}

	if (el && (edit_record(el, FR_EDIT_VALUE, vp, NULL, NULL) < 0)) return -1;

	if (!fr_type_is_fixed_size(vp->vp_type)) fr_value_box_clear(&vp->data);
	fr_value_box_copy_shallow(NULL, &vp->data, box);
	return 0;
}

/** Replace a pair with another one.
 *
 *  This function mirrors fr_pair_replace().
 *
 *  After this function returns, the new VP has replaced the old one,
 *  and the new one can be edited.
 */
int fr_edit_list_replace_pair(fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_t *to_replace, fr_pair_t *vp)
{
	if (to_replace->da != vp->da) return -1;

	if (fr_pair_immutable(to_replace)) {
		fr_strerror_printf("Cannot modify immutable value for %s", vp->da->name);
		return -1;
	}

	if (!el) {
		if (fr_pair_insert_after(list, to_replace, vp) < 0) return -1;
		fr_pair_delete(list, to_replace);
		return -1;
	}

	/*
	 *	We call edit_record() twice, which involves two
	 *	complete passes over the edit list.  That's fine,
	 *	either the edit list is small, OR we will eventually
	 *	put the VPs to be edited into an RB tree.
	 */
	if (edit_record(el, FR_EDIT_INSERT, vp, list, to_replace) < 0) return -1;

	/*
	 *	If deleting the old entry fails, then the new entry
	 *	above MUST be the last member of the edit list.  If
	 *	it's not the last member, then it means that it
	 *	already existed in the list (either VP list of edit
	 *	list).  The edit_record() function checks for that,
	 *	and errors if so.
	 */
	if (edit_record(el, FR_EDIT_DELETE, to_replace, list, NULL) < 0) {
		fr_edit_t *e = fr_dlist_pop_tail(&el->undo);

		fr_assert(e != NULL);
		fr_assert(e->vp == vp);
		talloc_free(e);
		return -1;
	}

	return 0;
}


/** Free children of a structural pair.
 *
 *  This function mirrors fr_pair_replace().
 *
 *  After this function returns, the new VP has replaced the old one,
 *  and the new one can be edited.
 */
int fr_edit_list_free_pair_children(fr_edit_list_t *el, fr_pair_t *vp)
{
	if (!fr_type_is_structural(vp->vp_type)) return -1;

	if (!el) {
		fr_pair_list_free(&vp->children);
		return 0;
	}

	/*
	 *	No children == do nothing.
	 */
	if (fr_pair_list_empty(&vp->vp_group)) return 0;

	/*
	 *	Record the list, even if it's empty.  That way if we
	 *	later add children to it, the "undo" operation can
	 *	reset the children list to be empty.
	 */
	return edit_record(el, FR_EDIT_CLEAR, vp, NULL, NULL);
}

/** Finalize the edits when we destroy the edit list.
 *
 *  Which in large part means freeing the VPs which have been deleted,
 *  or saved, and then deleting the edit list.
 */
static int _edit_list_destructor(fr_edit_list_t *el)
{
	fr_edit_t *e;

	fr_assert(el != NULL);

	for (e = fr_dlist_head(&el->undo);
	     e != NULL;
	     e = fr_dlist_next(&el->undo, e)) {
		switch (e->op) {
		case FR_EDIT_INVALID:
			fr_assert(0);
			break;

		case FR_EDIT_INSERT:
			break;

		case FR_EDIT_DELETE:
			fr_assert(e->vp != NULL);
			talloc_free(e->vp);
			break;

		case FR_EDIT_CLEAR:
			fr_pair_list_free(&e->children);
			break;

		case FR_EDIT_VALUE:
			fr_assert(fr_type_is_leaf(e->vp->vp_type));
			fr_value_box_clear(&e->data);
			break;

		case FR_EDIT_CHILD:
			talloc_free(e->child_edit);
			break;
		}
	}

	fr_pair_list_free(&el->deleted_pairs);

	talloc_free(el);

	return 0;
}

/** Allocate an edit list.
 *
 *  Edit lists can be nested.  If the child list commits, then it does nothing
 *  until the parent list commits.  On the other hand, if the child list aborts,
 *  then the parent list might continue.
 *
 * @param ctx		talloc context.  Ignored if parent!=NULL
 * @param hint		how many edits we are likely to allocate
 * @param parent	a parent edit list
 */
fr_edit_list_t *fr_edit_list_alloc(TALLOC_CTX *ctx, int hint, fr_edit_list_t *parent)
{
	fr_edit_list_t *el;
	fr_edit_t *e;

	/*
	 *	If we have nested transactions, then allocate this
	 *	list in the context of the parent.  Otherwise it will
	 *	be freed too soon.
	 */
	if (parent) ctx = parent;

	el = talloc_zero_pooled_object(ctx, fr_edit_list_t, hint, hint * sizeof(fr_edit_t));
	if (!el) return NULL;

	fr_dlist_init(&el->undo, fr_edit_t, entry);
	fr_dlist_init(&el->ignore, fr_edit_ignore_t, entry);

	fr_pair_list_init(&el->deleted_pairs);

	talloc_set_destructor(el, _edit_list_destructor);

	el->parent = parent;

	if (!parent) return el;

	e = talloc_zero(parent, fr_edit_t);
	if (!e) {
		talloc_free(el);
		return NULL;
	}

	/*
	 *	Insert the child into the tail of the current edit list.
	 */
	e->op = FR_EDIT_CHILD;
	e->vp = NULL;
	e->child_edit = el;

	fr_dlist_insert_tail(&parent->undo, e);
	el->e = e;

	return el;
}

/** Commit an edit list.
 *
 *  If there are nested transactions, then this transaction is
 *  committed only when the parent transaction has been committed.
 *
 */
void fr_edit_list_commit(fr_edit_list_t *el)
{
	if (el->parent) return;

	talloc_free(el);
}

/** Notes
 *
 *  Unlike "update" sections, edits are _not_ hierarchical.  If we're
 *  editing values a list, then the list has to exist.  If we're
 *  inserting pairs in a list, then we find the lowest existing pair,
 *  and add pairs there.
 *
 *  The functions tmpl_extents_find() and tmpl_extents_build_to_leaf_parent()
 *  should help us figure out where the VPs exist or not.
 *
 *  The overall "update" algorithm is now:
 *
 *	alloc(edit list)
 *
 *	foreach entry in the things to do
 *		expand LHS if needed to local TMPL
 *		expand RHS if needed to local box / cursor / TMPL
 *
 *		use LHS/RHS cursors to find VPs
 *		edit VPs, recording edits
 *
 *	free temporary map
 *	commit(edit list)
 */

/**********************************************************************
 *
 *  Now we have helper functions which use the edit list to get things
 *  done.
 *
 **********************************************************************/

/** Insert a list after a particular point in another list.
 *
 *  This function mirrors fr_pair_list_append(), but with a bit more
 *  control over where the to_insert list ends up.
 *
 *  There's nothing magical about this function, it's just easier to
 *  have it here than in multiple places in the code.
 */
int fr_edit_list_insert_list_after(fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_t *pos, fr_pair_list_t *to_insert)
{
	fr_pair_t *prev, *vp;

	prev = pos;

	if (!el) {
		/*
		 *	@todo - this should really be an O(1) dlist
		 *	operation.
		 */
		while ((vp = fr_pair_list_head(to_insert)) != NULL) {
			(void) fr_pair_remove(to_insert, vp);
			(void) fr_pair_insert_after(list, prev, vp);
			prev = vp;
		}

		return 0;
	}

	/*
	 *	We have to record each individual insert as a separate
	 *	item.  Some later edit may insert pairs in the middle
	 *	of the ones we've added.
	 */
	while ((vp = fr_pair_list_head(to_insert)) != NULL) {
		(void) fr_pair_remove(to_insert, vp);

		if (edit_record(el, FR_EDIT_INSERT, vp, list, prev) < 0) {
			fr_pair_prepend(to_insert, vp); /* don't lose it! */
			return -1;
		}

		prev = vp;
	}

	return 0;
}

/** Removes elements matching a list
 *
 *  O(N^2) unfortunately.
 */
static int fr_edit_list_delete_list(fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_list_t *to_remove)
{
	/*
	 *	We have a list of VPs with operators and values.  Those contain the list of things we want to
	 *	be removed from the main "list".
	 */
	fr_pair_list_foreach(to_remove, vp) {
		fr_pair_t *found, *next;

		/*
		 *	@todo - do this recursively.
		 */
		if (fr_type_is_structural(vp->vp_type)) continue;

		/*
		 *	Search the list to edit for VPs which match the ones we're trying to delete.
		 */
		for (found = fr_pair_find_by_da(list, NULL, vp->da);
		     found != NULL;
		     found = next) {
			int rcode;

			next = fr_pair_find_by_da(list, found, vp->da);

			/*
			 *	It doesn't match, keep it.  If it matches, delete it.
			 */
			rcode = fr_value_box_cmp_op(vp->op, &found->data, &vp->data);
			if (rcode < 0) return -1;

			if (!rcode) continue;

			if (fr_edit_list_pair_delete(el, list, found) < 0) return -1;
		}
	}

	return 0;
}

/** Apply operators to pairs.
 *
 *  := is "if found vp, call fr_edit_list_pair_replace().  Otherwise call fr_edit_list_insert_pair_tail()
 *   = is "if found vp, do nothing.  Otherwise call fr_edit_list_insert_pair_tail()
 *
 */
int fr_edit_list_apply_pair_assignment(fr_edit_list_t *el, fr_pair_t *vp, fr_token_t op, fr_value_box_t const *in)
{
	fr_value_box_t box;

	switch (op) {
	case T_OP_LE:
	case T_OP_LT:
	case T_OP_GT:
	case T_OP_GE:
		if (fr_value_calc_binary_op(vp, &box, FR_TYPE_BOOL, &vp->data, op, in) < 0) return -1;

		if (box.vb_bool) return 0;

		if (el && (fr_edit_list_save_pair_value(el, vp) < 0)) return -1;

		fr_value_box_clear_value(&vp->data);

		/*
		 *	The input type may be different, so we can't just copy it.
		 */
		return fr_value_box_cast(vp, &vp->data, vp->vp_type, vp->data.enumv, in);

	default:
		break;

	}

	if (el && (fr_edit_list_save_pair_value(el, vp) < 0)) return -1;

	return fr_value_calc_assignment_op(vp, &vp->data, op, in);
}

#undef COPY
#define COPY(_x) do { if (copy) { \
		        c = fr_pair_copy(dst, _x); \
			if (!c) return -1; \
                      } else { \
			c = talloc_steal(dst, _x); \
			fr_pair_remove(src, c); \
		      } \
		 } while (0)

#define NEXT_A do { a = an; an = fr_pair_list_next(&dst->children, a); } while (0)
#define NEXT_B do { b = bn; bn = fr_pair_list_next(src, b); } while (0)


/** A UNION B
 *
 */
static int list_union(fr_edit_list_t *el, fr_pair_t *dst, fr_pair_list_t *src, bool copy)
{
	fr_pair_t *a, *an;
	fr_pair_t *b, *bn;
	fr_pair_t *c;

	/*
	 *	Prevent people from doing stupid things.
	 *	While it's technically possible to take a
	 *	UNION of structs, that would work ONLY when
	 *	the two structs had disjoint members.
	 *	e.g. {1, 3, 4} and {2, 5, 6}.  That's too
	 *	complex to check right now, so we punt on the
	 *	problem.
	 */
	if (dst->vp_type == FR_TYPE_STRUCT) {
		fr_strerror_printf("Cannot take union of STRUCT data types, it would break the structure");
		return -1;
	}

	fr_pair_list_sort(&dst->children, fr_pair_cmp_by_parent_num);
	fr_pair_list_sort(src, fr_pair_cmp_by_parent_num);

	PAIR_LIST_VERIFY(&dst->children);
	PAIR_LIST_VERIFY(src);

	a = fr_pair_list_head(&dst->children);
	an = fr_pair_list_next(&dst->children, a);
	b = fr_pair_list_head(src);
	bn = fr_pair_list_next(src, b);

	while (true) {
		int rcode;

		/*
		 *	B is done, so we stop processing.
		 */
		if (!b) break;

		/*
		 *	A is done, so we can add in B at the end of A.
		 */
		if (!a) {
			COPY(b);

			if (fr_edit_list_insert_pair_tail(el, &dst->children, c) < 0) {
				return -1;
			}

			NEXT_B;
			continue;
		}

		/*
		 *	Compare the da's
		 */
		rcode = fr_pair_cmp_by_parent_num(a, b);

		/*
		 *	We've seen things in A which aren't in B, so
		 *	we just increment A.
		 */
		if (rcode < 0) {
			NEXT_A;
			continue;
		}

		/*
		 *	a > b
		 *
		 *	This means that in the ordered set, the
		 *	equivalent to B does not exist.  So we copy B
		 *	to after A.
		 */
		if (rcode > 0) {
			COPY(b);

			if (fr_edit_list_insert_pair_after(el, &dst->children, a, c) < 0) {
				return -1;
			}

			NEXT_B;
			continue;
		}

		fr_assert(rcode == 0);

		/*
		 *	They're the same.
		 */
		fr_assert(a->da == b->da);

		/*
		 *	Union lists recursively.
		 *
		 *	Note that this doesn't mean copying both VPs!  We just merge their contents.
		 */
		if (fr_type_is_structural(a->vp_type)) {
			rcode = list_union(el, a, &b->children, copy);
			if (rcode < 0) return rcode;

			NEXT_A;
			NEXT_B;
			continue;
		}

		/*
		 *	Process all identical attributes, but by
		 *	value.  If the value is the same, we keep only
		 *	one.  If the values are different, we keep
		 *	both.
		 */
		while (a && b && (a->da == b->da)) {
			/*
			 *	Check if the values are the same.  This
			 *	returns 0 for "equal", and non-zero for
			 *	anything else.
			 */
			rcode = fr_value_box_cmp(&a->data, &b->data);
			if (rcode != 0) {
				COPY(b);

				if (fr_edit_list_insert_pair_after(el, &dst->children, a, c) < 0) {
					return -1;
				}
			}

			NEXT_A;
			NEXT_B;
		}
	}

	return 0;
}

/** A MERGE B
 *
 * with priority to A
 */
static int list_merge_lhs(fr_edit_list_t *el, fr_pair_t *dst, fr_pair_list_t *src, bool copy)
{
	fr_pair_t *a, *an;
	fr_pair_t *b, *bn;
	fr_pair_t *c;

	fr_pair_list_sort(&dst->children, fr_pair_cmp_by_parent_num);
	fr_pair_list_sort(src, fr_pair_cmp_by_parent_num);

	PAIR_LIST_VERIFY(&dst->children);
	PAIR_LIST_VERIFY(src);

	a = fr_pair_list_head(&dst->children);
	an = fr_pair_list_next(&dst->children, a);
	b = fr_pair_list_head(src);
	bn = fr_pair_list_next(src, b);

	while (true) {
		int rcode;

		/*
		 *	B is done, so we stop processing.
		 */
		if (!b) break;

		/*
		 *	A is done, so we can add in B at the end of A.
		 */
		if (!a) {
			COPY(b);

			if (fr_edit_list_insert_pair_tail(el, &dst->children, c) < 0) {
				return -1;
			}

			NEXT_B;
			continue;
		}

		/*
		 *	Compare the da's
		 */
		rcode = fr_pair_cmp_by_parent_num(a, b);

		/*
		 *	We've seen things in A which aren't in B, so
		 *	we just increment A.
		 */
		if (rcode < 0) {
			NEXT_A;
			continue;
		}

		/*
		 *	a > b
		 *
		 *	This means that in the ordered set, the
		 *	equivalent to B does not exist.  So we copy B
		 *	to before A.
		 */
		if (rcode > 0) {
			COPY(b);

			if (fr_edit_list_insert_pair_before(el, &dst->children, a, c) < 0) {
				return -1;
			}

			NEXT_B;
			continue;
		}

		fr_assert(rcode == 0);

		/*
		 *	They're the same.
		 */
		fr_assert(a->da == b->da);

		/*
		 *	Merge lists recursively.
		 */
		if (fr_type_is_structural(a->vp_type)) {
			rcode = list_merge_lhs(el, a, &b->children, copy);
			if (rcode < 0) return rcode;

			goto next_both;
		}

		/*
		 *	We have both A and B, so we prefer A, which means just skipping B.
		 */

	next_both:
		NEXT_A;
		NEXT_B;
	}

	return 0;
}

/** A MERGE B
 *
 * with priority to B.
 */
static int list_merge_rhs(fr_edit_list_t *el, fr_pair_t *dst, fr_pair_list_t *src, bool copy)
{
	fr_pair_t *a, *an;
	fr_pair_t *b, *bn;
	fr_pair_t *c;

	fr_pair_list_sort(&dst->children, fr_pair_cmp_by_parent_num);
	fr_pair_list_sort(src, fr_pair_cmp_by_parent_num);

	PAIR_LIST_VERIFY(&dst->children);
	PAIR_LIST_VERIFY(src);

	a = fr_pair_list_head(&dst->children);
	an = fr_pair_list_next(&dst->children, a);
	b = fr_pair_list_head(src);
	bn = fr_pair_list_next(src, b);

	while (true) {
		int rcode;

		/*
		 *	B is done, so we stop processing.
		 */
		if (!b) break;

		/*
		 *	A is done, so we can in B at the end of A.
		 */
		if (!a) {
			COPY(b);

			if (fr_edit_list_insert_pair_tail(el, &dst->children, c) < 0) {
				return -1;
			}

			NEXT_B;
			continue;
		}

		/*
		 *	Compare the da's
		 */
		rcode = fr_pair_cmp_by_parent_num(a, b);

		/*
		 *	We've seen things in A which aren't in B, so
		 *	we just increment A.
		 */
		if (rcode < 0) {
			NEXT_A;
			continue;
		}

		/*
		 *	a > b
		 *
		 *	This means that in the ordered set, the
		 *	equivalent to B does not exist.  So we copy B
		 *	to before A.
		 */
		if (rcode > 0) {
			COPY(b);

			if (fr_edit_list_insert_pair_before(el, &dst->children, a, c) < 0) {
				return -1;
			}

			NEXT_B;
			continue;
		}

		fr_assert(rcode == 0);

		/*
		 *	They're the same.
		 */
		fr_assert(a->da == b->da);

		/*
		 *	Merge lists recursively.
		 */
		if (fr_type_is_structural(a->vp_type)) {
			rcode = list_merge_rhs(el, a, &b->children, copy);
			if (rcode < 0) return rcode;

			goto next_both;
		}

		/*
		 *	We have both A and B, so we prefer B.
		 */
		COPY(b);
		if (fr_edit_list_replace_pair(el, &dst->children, a, c) < 0) {
			return -1;
		}

	next_both:
		NEXT_A;
		NEXT_B;
	}

	return 0;
}

/** A INTERSECTION B
 *
 */
static int list_intersection(fr_edit_list_t *el, fr_pair_t *dst, fr_pair_list_t *src)
{
	fr_pair_t *a, *an;
	fr_pair_t *b, *bn;

	/*
	 *	Prevent people from doing stupid things.
	 */
	if (dst->vp_type == FR_TYPE_STRUCT) {
		fr_strerror_printf("Cannot take intersection of STRUCT data types, it would break the structure");
		return -1;
	}

	fr_pair_list_sort(&dst->children, fr_pair_cmp_by_parent_num);
	fr_pair_list_sort(src, fr_pair_cmp_by_parent_num);

	a = fr_pair_list_head(&dst->children);
	an = fr_pair_list_next(&dst->children, a);
	b = fr_pair_list_head(src);
	bn = fr_pair_list_next(src, b);

	while (true) {
		int rcode;

		/*
		 *	A is done, so we can return.  We don't need to
		 *	delete everything from B, as that will be
		 *	cleaned up by the caller when we exit.
		 */
		if (!a) break;

		/*
		 *	B is done, so we delete everything else in A.
		 */
		if (!b) {
		delete_a:
			if (fr_edit_list_pair_delete(el, &dst->children, a) < 0) return -1;
			NEXT_A;
			continue;
		}

		/*
		 *	Compare the da's
		 */
		rcode = fr_pair_cmp_by_parent_num(a, b);

		/*
		 *	a < b
		 *
		 *	A gets removed.
		 */
		if (rcode < 0) goto delete_a;

		/*
		 *	a > b
		 *
		 *      Skip forward in B until we have it better matching A.
		 */
		if (rcode > 0) {
			NEXT_B;
			continue;
		}

		fr_assert(rcode == 0);

		/*
		 *	INTERSECT the children, and then leave A
		 *	alone, unless it's empty, in which case A
		 *	INTERSECT B is empty, so we also delete A.
		 */
		if (fr_type_is_structural(a->vp_type)) {
			rcode = list_intersection(el, a, &b->children);
			if (rcode < 0) return rcode;

			NEXT_B;

			if (fr_pair_list_empty(&a->children)) goto delete_a;

			NEXT_A;
			continue;
		}

		/*
		 *	Process all identical attributes, but by
		 *	value.
		 */
		while (a && b && (a->da == b->da)) {
			/*
			 *	Check if the values are the same.  This
			 *	returns 0 for "equal", and non-zero for
			 *	anything else.
			 */
			rcode = fr_value_box_cmp(&a->data, &b->data);
			if (rcode != 0) {
				if (fr_edit_list_pair_delete(el, &dst->children, a) < 0) return -1;
			}

			NEXT_A;
			NEXT_B;
		}
	}

	return 0;
}


/** Apply operators to lists.
 *
 *   = is "if found vp, do nothing.  Otherwise call fr_edit_list_insert_pair_tail()
 *
 *  The src list is sorted, but is otherwise not modified.
 */
int fr_edit_list_apply_list_assignment(fr_edit_list_t *el, fr_pair_t *dst, fr_token_t op, fr_pair_list_t *src, bool copy)
{
	fr_pair_list_t list;

	if (!fr_type_is_structural(dst->vp_type)) {
		fr_strerror_printf("Cannot perform list assignment to non-structural type '%s'",
				   fr_type_to_str(dst->vp_type));
		return -1;
	}

#undef COPY
#define COPY do { if (copy) { \
		    fr_pair_list_init(&list); \
		    if (fr_pair_list_copy(dst, &list, src) < 0) return -1;\
                    src = &list; \
                  } else { \
		    fr_pair_list_steal(dst, src); \
	          } \
	} while (0)


	switch (op) {
		/*
		 *	Over-ride existing value (i.e. children) with
		 *	new list.
		 */
	case T_OP_SET:
		if (&dst->children == src) return 0; /* A := A == A */

		if (fr_edit_list_free_pair_children(el, dst) < 0) return -1;
		FALL_THROUGH;

	case T_OP_ADD_EQ:
		if (&dst->children == src) {
			fr_strerror_printf("Cannot append list to itself");
			return -1;
		}

		COPY;
		return fr_edit_list_insert_list_tail(el, &dst->children, src);

	case T_OP_SUB_EQ:
		/*
		 *	foo -= foo --> {}
		 */
		if (&dst->children == src) {
			fr_pair_t *vp;

			while ((vp = fr_pair_list_head(&dst->children)) != NULL) {
				if (fr_edit_list_pair_delete(el, &dst->children, vp) < 0) return -1;
			}

			return 0;
		}

		return fr_edit_list_delete_list(el, &dst->children, src);

	case T_OP_PREPEND:
		if (&dst->children == src) {
			fr_strerror_printf("Cannot prepend list to itself");
			return -1;
		}

		COPY;
		return fr_edit_list_insert_list_head(el, &dst->children, src);

	case T_OP_AND_EQ:
		if (&dst->children == src) return 0; /* A INTERSECTION A == A */

		if (!fr_edit_list_empty(el)) {
		not_empty:
			fr_strerror_printf("Failed to perform %s - undo list is not empty", fr_tokens[op]);
			return -1;
		}

		return list_intersection(el, dst, src);

	case T_OP_OR_EQ:
		if (&dst->children == src) return 0; /* A UNION A == A */

		if (!fr_edit_list_empty(el)) goto not_empty;

		return list_union(el, dst, src, copy);

	case T_OP_GE:
		if (&dst->children == src) return 0; /* A MERGE A == A */

		if (!fr_edit_list_empty(el)) goto not_empty;

		return list_merge_lhs(el, dst, src, copy);

	case T_OP_LE:
		if (&dst->children == src) return 0; /* A MERGE A == A */

		if (!fr_edit_list_empty(el)) goto not_empty;

		return list_merge_rhs(el, dst, src, copy);

	default:
		break;
	}

	fr_strerror_printf("Invalid assignment operator %s for destination type %s",
			   fr_tokens[op],
			   fr_type_to_str(dst->vp_type));
	return -1;
}
