/src/freeradius-server/src/lib/util/edit.c

Source
/*
 *   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: 587257da8817ce748e8400e69e4f0351752f73f9 $
 *
 * @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: 587257da8817ce748e8400e69e4f0351752f73f9 $")

#include <freeradius-devel/util/value.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[5] = {
  "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_EDIT_CHILD has vp == NULL, handle it
   *  before the vp assertions.
   */
  if (e->op == FR_EDIT_CHILD) {
    fr_edit_list_abort(e->child_edit);
    return 0;
  }

  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);
    if (unlikely(fr_value_box_copy(vp, &vp->data, &e->data) < 0)) return -1;
    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_assert(0);  /* handled above */
    return -1;
  }

  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:
      if (fr_pair_immutable(vp)) {
        fr_strerror_printf("Cannot modify immutable value for %s", vp->da->name);
        return -1;
      }
      return 0;

      /*
       *  No need to save the value.
       */
    case FR_EDIT_DELETE:
      /*
       *  We silently refuse to delete immutable attributes.
       */
      if (fr_pair_immutable(vp)) return 0;

      if (vp->vp_edit) return 0;

      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
       *  its 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_value_box_clear(&e->data);
      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));
    if (unlikely(fr_value_box_copy(e, &e->data, &vp->data) < 0)) goto fail;
    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:
    /*
     *  We silently refuse to delete immutable attributes.
     */
    if (fr_pair_immutable(e->vp)) {
      talloc_free(e);
      return 0;
    }

    if (e->vp->vp_edit) {
      talloc_free(e);
      return 0;
    }

    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 -1;

    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 (!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 (vp->da != da) continue;

    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 (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 (!el) {
    if (fr_pair_insert_after(list, to_replace, vp) < 0) return -1;
    fr_pair_delete(list, to_replace);
    return 0;
  }

  /*
   *  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_list_free(&vp->children).
 *
 *  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);

  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_VERIFY(dst);
  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);

    /*
     *  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_VERIFY(dst);
  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_VERIFY(dst);
  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;
}

Coverage Report

Created: 2026-08-14 07:17