path: root/src/format.c

/*
 * Copyright 2008 Red Hat, Inc.
 *
 * This Program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2 of the License.
 *
 * This Program 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
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this Program; if not, write to the
 *
 *   Free Software Foundation, Inc.
 *   59 Temple Place, Suite 330
 *   Boston, MA 02111-1307 USA
 *
 */

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <sys/types.h>
#include <ctype.h>
#include <errno.h>
#include <fnmatch.h>
#include <regex.h>
#include <stdlib.h>
#include <string.h>

#ifdef HAVE_DIRSRV_SLAPI_PLUGIN_H
#include <nspr.h>
#include <nss.h>
#include <dirsrv/slapi-plugin.h>
#else
#include <slapi-plugin.h>
#endif

#include <rpcsvc/yp.h>

#include "backend.h"
#include "back-shr.h"
#include "format.h"
#include "plugin.h"

#define DEFAULT_BUFFER_SIZE 0x1000
#define MAX_BUFFER_SIZE     0x100000
struct format_choice {
	char *offset;
	int n_values;
	struct berval **values;
	struct format_choice *next;
};

static int format_expand(struct plugin_state *state,
			 Slapi_PBlock *pb, Slapi_Entry *e,
			 const char *group, const char *set,
			 const char *fmt, const char *disallowed,
			 char *outbuf, int outbuf_len,
			 struct format_choice **outbuf_choices,
			 char ***ref_attrs,
			 struct format_inref_attr ***inref_attrs,
			 struct format_ref_attr_list ***ref_attr_list,
			 struct format_ref_attr_list ***inref_attr_list);

static char *
xstrndup(const char *start, size_t length)
{
	char *ret, *end;
	end = memchr(start, '\0', length);
	if (end != NULL) {
		length = end - start;
	}
	ret = malloc(length + 1);
	if (ret != NULL) {
		memcpy(ret, start, length);
		ret[length] = '\0';
	}
	return ret;
}

static char *
xstrndupp(const char *start, const char *end)
{
	return xstrndup(start, end - start);
}

static void *
xmemdup(char *region, int size)
{
	char *ret;
	ret = malloc(size + 1);
	if (ret != NULL) {
		if (size > 0) {
			memcpy(ret, region, size);
		}
		ret[size] = '\0';
	}
	return ret;
}

/* Maintain a DN list, which is list of distinguished names. */
void
format_free_sdn_list(struct slapi_dn **list)
{
	unsigned int i;
	if (list != NULL) {
		for (i = 0; list[i] != NULL; i++) {
			slapi_sdn_free(&(list[i]));
		}
		free(list);
	}
}

struct slapi_dn **
format_dup_sdn_list(struct slapi_dn **list)
{
	struct slapi_dn **ret;
	unsigned int i;
	for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
		continue;
	}
	ret = malloc((i + 1) * sizeof(struct slapi_dn*));
	if (ret != NULL) {
		for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
			ret[i] = slapi_sdn_dup(list[i]);
		}
		ret[i] = NULL;
	}
	return ret;
}

struct slapi_dn **
format_make_sdn_list(char **list)
{
	struct slapi_dn **ret;
	unsigned int i;
	for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
		continue;
	}
	ret = malloc((i + 1) * sizeof(struct slapi_dn*));
	if (ret != NULL) {
		for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
			ret[i] = slapi_sdn_new_dn_byval(list[i]);
		}
		ret[i] = NULL;
	}
	return ret;
}

struct slapi_dn **
format_add_sdn_list(struct slapi_dn ***list, const char *dn)
{
	struct slapi_dn **ret, *sdn;
	unsigned int i;
	sdn = slapi_sdn_new_dn_byval(dn);
	for (i = 0;
	     (list != NULL) && (*list != NULL) && ((*list)[i] != NULL);
	     i++) {
		if (slapi_sdn_compare(sdn, (*list)[i]) == 0) {
			slapi_sdn_free(&sdn);
			return *list;
		}
		continue;
	}
	ret = malloc((i + 2) * sizeof(struct slapi_dn*));
	if (ret != NULL) {
		for (i = 0;
		     (list != NULL) && (*list != NULL) && ((*list)[i] != NULL);
		     i++) {
			ret[i] = slapi_sdn_dup((*list)[i]);
		}
		ret[i++] = sdn;
		ret[i] = NULL;
		format_free_sdn_list(*list);
		*list = ret;
	}
	return *list;
}

/* Maintain a reference attribute list, which is group of lists of attribute
 * names and search bases. */
void
format_free_ref_attr_list(struct format_ref_attr_list **list)
{
	Slapi_DN **sdn_list;
	unsigned int i;
	int j;
	if (list != NULL) {
		for (i = 0; list[i] != NULL; i++) {
			for (j = 0; j < list[i]->n_links; j++) {
				free(list[i]->links[j].attribute);
				sdn_list = list[i]->links[j].base_sdn_list;
				format_free_sdn_list(sdn_list);
			}
			free(list[i]->links);
			free(list[i]->set);
			free(list[i]->group);
			free(list[i]);
		}
		free(list);
	}
}

struct format_ref_attr_list **
format_dup_ref_attr_list(struct format_ref_attr_list **list)
{
	struct format_ref_attr_list **ret;
	struct slapi_dn **sdn_list;
	unsigned int i;
	int j;
	for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
		continue;
	}
	ret = malloc((i + 1) * sizeof(struct format_ref_attr_list*));
	if (ret != NULL) {
		memset(ret, 0, (i + 1) * sizeof(struct format_ref_attr_list*));
		for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
			ret[i] = malloc(sizeof(*(list[i])));
			if (ret[i] == NULL) {
				format_free_ref_attr_list(ret);
				return NULL;
			}
			memset(ret[i], 0, sizeof(*(ret[i])));
			ret[i]->links = malloc(sizeof(*(ret[i]->links)) *
					       list[i]->n_links);
			if (ret[i]->links == NULL) {
				format_free_ref_attr_list(ret);
				return NULL;
			}
			for (j = 0; j < list[i]->n_links; j++) {
				ret[i]->links[j].attribute =
					strdup(list[i]->links[j].attribute);
				if (ret[i]->links[j].attribute == NULL) {
					format_free_ref_attr_list(ret);
					return NULL;
				}
				sdn_list = list[i]->links[j].base_sdn_list;
				ret[i]->links[j].base_sdn_list =
					format_dup_sdn_list(sdn_list);
				ret[i]->n_links++;
			}
			ret[i]->group = strdup(list[i]->group);
			ret[i]->set = strdup(list[i]->set);
		}
		ret[i] = NULL;
	}
	return ret;
}

static struct format_ref_attr_list *
format_find_ref_attr_list(struct format_ref_attr_list **list,
			  const char *group, const char *set,
			  const char **names)
{
	unsigned int i;
	int j;
	const char *attribute;
	for (i = 0; (list != NULL) && (list[i] != NULL); i++) {
		for (j = 0; names[j] != NULL; j++) {
			if (j < list[i]->n_links) {
				attribute = list[i]->links[j].attribute;
				if (strcmp(names[j], attribute) != 0) {
					break;
				}
			}
		}
		if ((j == list[i]->n_links) && (names[j] == NULL)) {
			return list[i];
		}
	}
	return NULL;
}

static struct format_ref_attr_list **
format_add_ref_attr_list(struct format_ref_attr_list ***list,
			 const char *group, const char *set,
			 const char **names)
{
	struct format_ref_attr_list **ret;
	unsigned int i;
	int j;
	if (format_find_ref_attr_list(*list, group, set, names) != NULL) {
		return *list;
	}
	for (i = 0;
	     (list != NULL) && (*list != NULL) && ((*list)[i] != NULL);
	     i++) {
		continue;
	}
	ret = malloc((i + 2) * sizeof(struct format_ref_attr_list*));
	if (ret != NULL) {
		memcpy(ret, *list, i * sizeof(struct format_ref_attr_list*));
		free(*list);
		*list = NULL;
		ret[i] = malloc(sizeof(*(ret[i])));
		if (ret[i] == NULL) {
			format_free_ref_attr_list(ret);
			return NULL;
		}
		memset(ret[i], 0, sizeof(*(ret[i])));
		for (j = 0; names[j] != NULL; j++) {
			continue;
		}
		ret[i]->links = malloc(sizeof(*(ret[i]->links)) * j);
		if (ret[i]->links == NULL) {
			format_free_ref_attr_list(ret);
			return NULL;
		}
		memset(ret[i]->links, 0, sizeof(*(ret[i]->links)) * j);
		ret[i]->n_links = j;
		for (j = 0; j < ret[i]->n_links; j++) {
			ret[i]->links[j].attribute = strdup(names[j]);
			if (ret[i]->links[j].attribute == NULL) {
				format_free_ref_attr_list(ret);
				return NULL;
			}
			ret[i]->links[j].base_sdn_list = NULL;
		}
		ret[i]->group = strdup(group);
		ret[i]->set = strdup(set);
		i++;
		ret[i] = NULL;
		*list = ret;
	}
	return ret;
}

/* Maintain an entry list.  The list takes ownership of entries which are
 * added to it. */
struct entry_list {
	Slapi_Entry *entry;
	struct entry_list *next;
};
static struct entry_list *
format_entry_list_remove_one(struct entry_list *list)
{
	struct entry_list *next;
	if (list == NULL) {
		next = NULL;
	} else {
		next = list->next;
		slapi_entry_free(list->entry);
		free(list);
	}
	return next;
}
static struct entry_list *
format_add_entry_list(struct entry_list *list, Slapi_Entry *entry)
{
	struct entry_list *next, *tail;
	next = malloc(sizeof(*next));
	if (next == NULL) {
		return list;
	} else {
		next->entry = entry;
		next->next = NULL;
		if (list == NULL) {
			return next;
		} else {
			for (tail = list;
			     tail->next != NULL;
			     tail = tail->next) {
				continue;
			}
			tail->next = next;
			return list;
		}
	}
}
static struct entry_list *
format_add_entry_list_dn(struct entry_list *list,
			 const char *dn, char **attributes,
			 void *plugin_identity)
{
	Slapi_Entry *entry;
	Slapi_DN *sdn;
	sdn = slapi_sdn_new_dn_byval(dn);
	if (sdn != NULL) {
		entry = NULL;
		wrap_search_internal_get_entry(sdn, attributes, &entry,
					       plugin_identity);
		slapi_sdn_free(&sdn);
		if (entry != NULL) {
			return format_add_entry_list(list, entry);
		} else {
			return list;
		}
	} else {
		return NULL;
	}
}

/* Maintain an attribute list, which is really just a string list.  Entries
 * named by an attribute in the list carry "interesting" information. */
char **
format_dup_attr_list(char **attr_list)
{
	return backend_shr_dup_strlist(attr_list);
}

void
format_free_attr_list(char **attr_list)
{
	return backend_shr_free_strlist(attr_list);
}

void
format_add_attrlist(char ***attrlist, const char *attribute)
{
	backend_shr_add_strlist(attrlist, attribute);
}

/* Maintain an inref attribute list, which tracks a group and set name and an
 * attribute.  If an entry in the group and set contains this entry's name in
 * the named attribute, then it's "interesting". */
struct format_inref_attr **
format_dup_inref_attrs(struct format_inref_attr **attrs)
{
	int i, j, elements;
	struct format_inref_attr **ret;

	elements = 0;
	ret = NULL;
	if (attrs != NULL) {
		for (i = 0; attrs[i] != NULL; i++) {
			continue;
		}
		elements = i;
		ret = malloc(sizeof(*ret) * (elements + 1));
		if (ret != NULL) {
			for (i = 0, j = 0; i < elements; i++) {
				ret[j] = malloc(sizeof(**attrs));
				if (ret[j] != NULL) {
					ret[j]->group =
						strdup(attrs[i]->group);
					ret[j]->set = strdup(attrs[i]->set);
					ret[j]->attribute =
						strdup(attrs[i]->attribute);
					if ((ret[j]->group != NULL) &&
					    (ret[j]->set != NULL) &&
					    (ret[j]->attribute != NULL)) {
						j++;
					}
				}
			}
			ret[j] = NULL;
		}
	}
	return ret;
}

void
format_add_inref_attrs(struct format_inref_attr ***attrs,
		       const char *group, const char *set,
		       const char *attribute)
{
	struct format_inref_attr **ret;
	int i, elements;
	elements = 0;
	ret = NULL;
	if (*attrs != NULL) {
		for (i = 0; (*attrs)[i] != NULL; i++) {
			if ((strcmp((*attrs)[i]->group, group) == 0) &&
			    (strcmp((*attrs)[i]->set, set) == 0) &&
			    (strcmp((*attrs)[i]->attribute, attribute) == 0)) {
				return;
			}
		}
		elements = i;
	}
	ret = malloc(sizeof(*ret) * (elements + 2));
	if (ret != NULL) {
		memcpy(ret, *attrs, elements * sizeof(**attrs));
		ret[elements] = malloc(sizeof(**ret));
		if (ret[elements] != NULL) {
			ret[elements]->group = strdup(group);
			ret[elements]->set = strdup(set);
			ret[elements]->attribute = strdup(attribute);
			ret[elements + 1] = NULL;
		}
		free(*attrs);
		*attrs = ret;
	}
}

void
format_free_inref_attrs(struct format_inref_attr **attrs)
{
	int i;
	if (attrs != NULL) {
		for (i = 0; attrs[i] != NULL; i++) {
			free(attrs[i]->group);
			free(attrs[i]->set);
			free(attrs[i]->attribute);
			free(attrs[i]);
		}
		free(attrs);
	}
}

/* Maintain berval lists. */
static int
format_count_bv_list(struct berval **bvlist)
{
	int i;
	if (bvlist != NULL) {
		for (i = 0; bvlist[i] != NULL; i++) {
			continue;
		}
		return i;
	}
	return 0;
}
static void
format_free_bv_list(struct berval **bvlist)
{
	int i;
	if (bvlist != NULL) {
		for (i = 0; bvlist[i] != NULL; i++) {
			free(bvlist[i]->bv_val);
			free(bvlist[i]);
		}
		free(bvlist);
	}
}
static struct berval **
format_dup_bv_list(struct berval **bvlist)
{
	struct berval **ret, *bv;
	int i;
	ret = NULL;
	if (bvlist != NULL) {
		for (i = 0; bvlist[i] != NULL; i++) {
			continue;
		}
		if (i == 0) {
			return NULL;
		}
		ret = malloc((i + 1) * sizeof(struct berval *));
		if (ret != NULL) {
			for (i = 0; bvlist[i] != NULL; i++) {
				ret[i] = malloc(sizeof(struct berval));
				if (ret[i] != NULL) {
					bv = bvlist[i];
					ret[i]->bv_val = xmemdup(bv->bv_val,
								 bv->bv_len);
					ret[i]->bv_len = bv->bv_len;
				}
			}
			ret[i] = NULL;
		}
	}
	return ret;
}
static void
format_add_bv_list(struct berval ***bvlist, const struct berval *bv)
{
	struct berval **list;
	int i;
	if (bvlist == NULL) {
		return;
	}
	if (*bvlist != NULL) {
		for (i = 0; (*bvlist)[i] != NULL; i++) {
			continue;
		}
	} else {
		i = 0;
	}
	list = malloc((i + 2) * sizeof(struct berval *));
	if (list != NULL) {
		if (i > 0) {
			memcpy(list, *bvlist, i * sizeof(struct berval *));
		}
		list[i] = malloc(sizeof(struct berval));
		if (list[i] != NULL) {
			list[i]->bv_val = xmemdup(bv->bv_val, bv->bv_len);
			if (list[i]->bv_val != NULL) {
				list[i]->bv_len = bv->bv_len;
				list[i + 1] = NULL;
				free(*bvlist);
				*bvlist = list;
			} else {
				free(list[i]);
				free(list);
				format_free_bv_list(*bvlist);
				*bvlist = NULL;
			}
		} else {
			format_free_bv_list(*bvlist);
			*bvlist = NULL;
		}
	} else {
		format_free_bv_list(*bvlist);
		*bvlist = NULL;
	}
}

/* Maintain "choices" lists. */
static void
format_retarget_choicesp(struct format_choice **choices, char *oldt, char *newt)
{
	struct format_choice *this_choice;
	int offset;
	if (choices != NULL) {
		for (this_choice = *choices;
		     this_choice != NULL;
		     this_choice = this_choice->next) {
			offset = this_choice->offset - oldt;
			this_choice->offset = newt + offset;
		}
	}
}
static void
format_free_choices(struct format_choice *choices)
{
	struct format_choice *next;
	while (choices != NULL) {
		next = choices->next;
		format_free_bv_list(choices->values);
		free(choices);
		choices = next;
	}
}
static void
format_free_choicesp(struct format_choice **choices)
{
	if (choices) {
		format_free_choices(*choices);
		*choices = NULL;
	}
}
static void
format_append_choice(struct format_choice **choices,
		     struct format_choice *choice)
{
	struct format_choice *here;
	if (choices == NULL) {
		return;
	}
	if (*choices == NULL) {
		*choices = choice;
	} else {
		here = *choices;
		while (here->next != NULL) {
			here = here->next;
		}
		choice->next = here->next;
		here->next = choice;
	}
}
static void
format_add_choice(struct format_choice **choices, char *offset,
		  struct berval **values)
{
	struct format_choice *choice;
	int i;
	if (values != NULL) {
		choice = malloc(sizeof(*choice));
		if (choice != NULL) {
			choice->offset = offset;
			choice->next = NULL;
			for (i = 0; values[i] != NULL; i++) {
				continue;
			}
			choice->n_values = i;
			choice->values = format_dup_bv_list(values);
			if (choice->values != NULL) {
				format_append_choice(choices, choice);
			} else {
				free(choice);
			}
		}
	}
}

/* Convert a strlist to a berval list. */
static struct berval **
format_strlist_to_bv_list(char **values)
{
	struct berval **val;
	int i;
	char *p;
	if (values != NULL) {
		for (i = 0; values[i] != NULL; i++) {
			continue;
		}
		val = malloc(sizeof(struct berval *) * (i + 1));
		if (val != NULL) {
			for (i = 0; values[i] != NULL; i++) {
				val[i] = malloc(sizeof(struct berval));
				if (val[i] != NULL) {
					p = values[i];
					val[i]->bv_val = xmemdup(p, strlen(p));
					if (val[i] != NULL) {
						val[i]->bv_len = strlen(p);
					}
				}
			}
			val[i] = NULL;
			return val;
		}
	}
	return NULL;
}
static void
format_add_choice_str(struct format_choice **choices, char *offset,
		      char **values)
{
	struct berval **vals;
	vals = format_strlist_to_bv_list(values);
	format_add_choice(choices, offset, vals);
	format_free_bv_list(vals);
}

/* Parse an argument string into an array of arguments. */
static void
format_free_parsed_args(char **argv)
{
	free(argv);
}
static int
format_parse_args(struct plugin_state *state, const char *args,
		  int *pargc, char ***pargv)
{
	int i, dq, argc;
	char *out, **argv;
	*pargc = 0;
	*pargv = NULL;
	argv = malloc((sizeof(char *) + 1) * (strlen(args) + 1));
	if (argv == NULL) {
		return -1;
	}
	memset(argv, 0, (sizeof(char *) + 1) * (strlen(args) + 1));
	out = (char *) argv;
	out += sizeof(char *) * (strlen(args) + 1);
	argc = 0;
	i = 0;
	dq = 0;
	while (args[i] != '\0') {
		switch (args[i]) {
		case '"':
			dq = !dq;
			if (dq) {
				argv[argc++] = out;
			} else {
				*out++ = '\0';
			}
			i++;
			break;
		case '\\':
			i++;
			/* fall through */
		default:
			*out++ = args[i++];
			break;
		}
	}
	argv[argc] = NULL;
	*out = '\0';
	out = malloc((argc * 3) + strlen(args));
	if (out != NULL) {
		*out = '\0';
		for (i = 0; i < argc; i++) {
			if (i > 0) {
				strcat(out, ",");
			}
			strcat(out, "'");
			strcat(out, argv[i]);
			strcat(out, "'");
		}
		free(out);
	}
	*pargc = argc;
	*pargv = argv;
	return 0;
}

/* Choose the first value of the set of results for the first argument, and if
 * we get no results, return the second argument. */
static int
format_first(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	     const char *group, const char *set,
	     const char *args, const char *disallowed,
	     char *outbuf, int outbuf_len,
	     struct format_choice **outbuf_choices,
	     char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	     struct format_ref_attr_list ***ref_attr_list,
	     struct format_ref_attr_list ***inref_attr_list)
{
	int ret, i, argc, first, common_length;
	char **argv, **values;
	const char *value_format, *default_value;
	unsigned int *lengths;
	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"first: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc < 1) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"first: error parsing arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	if (argc < 2) {
		value_format = argv[0];
		default_value = NULL;
	} else {
		value_format = argv[0];
		default_value = argv[1];
	}
	ret = -ENOENT;
	values = format_get_data_set(state, e, group, set,
				     value_format, disallowed,
				     ref_attrs, inref_attrs,
				     ref_attr_list, inref_attr_list,
				     &lengths);
	if (values == NULL) {
		if (default_value == NULL) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"first: no values for ->%s<-, "
					"and no default value provided\n",
					value_format);
			ret = -ENOENT;
		} else {
			i = format_expand(state, pb, e,
					  group, set,
					  default_value, NULL,
					  outbuf, outbuf_len,
					  outbuf_choices,
					  ref_attrs, inref_attrs,
					  ref_attr_list, inref_attr_list);
			ret = i;
		}
	} else {
		first = 0;
		for (i = 1; values[i] != NULL; i++) {
			/* Check if this entry sorts "earlier" than the current
			 * "first" entry.  If it does, note its position as the
			 * "first". */
			common_length = lengths[first] < lengths[i] ?
					lengths[first] : lengths[i];
			ret = memcmp(values[i], values[first], common_length);
			if ((ret < 0) ||
			    ((ret == 0) && (lengths[i] < lengths[first]))) {
				first = i;
			}
		}
		if ((int) lengths[first] > outbuf_len) {
			ret = -ENOBUFS;
		} else {
			memcpy(outbuf, values[first], lengths[first]);
			ret = lengths[first];
		}
		format_free_data_set(values, lengths);
	}
	format_free_parsed_args(argv);
	return ret;
}

/* Look up the entries matching DNs stored in the attribute named by the first
 * argument, pull out the values for the attribute named by the second
 * argument, and return a list of those values. */
static int
format_deref(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	     const char *group, const char *set,
	     const char *args, const char *disallowed,
	     char *outbuf, int outbuf_len,
	     struct format_choice **outbuf_choices,
	     char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	     struct format_ref_attr_list ***ref_attr_list,
	     struct format_ref_attr_list ***inref_attr_list)
{
	int i, j, ret, argc;
	Slapi_Entry *ref;
	Slapi_DN *refdn;
	Slapi_ValueSet *ref_values, *values;
	Slapi_Value *ref_value, *value;
	int disposition, ref_disposition, buffer_flags, ref_buffer_flags;
	char **argv, *attrs[3], *actual_attr, *actual_ref_attr;
	const char *cref;
	const struct berval *val;
	char *ref_attr, *target_attr;
	struct berval **choices;
	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"deref: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc != 2) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"deref: requires two arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	if (outbuf_choices == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"deref: returns a list, but a list "
				"would not be appropriate\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	ref_attr = argv[0];
	target_attr = argv[1];
	/* Note that the attribute in this entry refers to other entries. */
	if (ref_attrs != NULL) {
		format_add_attrlist(ref_attrs, ref_attr);
	}
	/* Get the values of the reference attribute from this entry. */
	if (slapi_vattr_values_get(e, ref_attr, &ref_values,
				   &ref_disposition, &actual_ref_attr,
				   0, &ref_buffer_flags) != 0) {
		/* No references means we're done. */
		format_free_parsed_args(argv);
		return 0;
	}
	/* Retrieve these attributes from the referred-to entries. */
	attrs[0] = ref_attr;
	attrs[1] = target_attr;
	attrs[2] = NULL;
	/* Iterate through the names of the referred-to entries. */
	choices = NULL;
	for (i = slapi_valueset_first_value(ref_values, &ref_value);
	     i != -1;
	     i = slapi_valueset_next_value(ref_values, i, &ref_value)) {
		/* Pull up the referred-to entry. */
		cref = slapi_value_get_string(ref_value);
		if (cref == NULL) {
			continue;
		}
		refdn = slapi_sdn_new_dn_byval(cref);
		if (refdn == NULL) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"deref: internal error parsing name "
					"\"%s\"\n", cref);
			continue;
		}
		ref = NULL;
		wrap_search_internal_get_entry(refdn, attrs, &ref,
					       state->plugin_identity);
		if (ref == NULL) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"deref: failure reading entry \"%s\"\n",
					slapi_sdn_get_ndn(refdn));
			slapi_sdn_free(&refdn);
			continue;
		}
		slapi_log_error(SLAPI_LOG_PLUGIN,
				state->plugin_desc->spd_id,
				"deref: reading \"%s\" from \"%s\"\n",
				target_attr, slapi_sdn_get_ndn(refdn));
		slapi_sdn_free(&refdn);
		/* Pull out the attribute from the referred-to entry. */
		if (slapi_vattr_values_get(ref, target_attr, &values,
					   &disposition, &actual_attr,
					   0, &buffer_flags) != 0) {
			slapi_entry_free(ref);
			continue;
		}
		for (j = slapi_valueset_first_value(values, &value);
		     j != -1;
		     j = slapi_valueset_next_value(values, j, &value)) {
			/* Get the value. */
			val = slapi_value_get_berval(value);
			/* If the value is empty, skip it. */
			if (val->bv_len == 0) {
				continue;
			}
			format_add_bv_list(&choices, val);
		}
		slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
		slapi_entry_free(ref);
	}
	slapi_vattr_values_free(&ref_values,
				&actual_ref_attr,
				ref_buffer_flags);
	format_free_parsed_args(argv);
	/* Return any values we found. */
	if (choices != NULL) {
		format_add_choice(outbuf_choices, outbuf, choices);
		format_free_bv_list(choices);
		return 0;
	} else {
		return -ENOENT;
	}
}

/* For the first N-1 arguments, look up the entries matching DNs stored in the
 * attribute named by the argument, following the chain of named entries, and
 * at last, pull out the values for the attribute named by the last argument,
 * and return a list of those values. */
static int
format_deref_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	       const char *group, const char *set,
	       const char *args, const char *disallowed,
	       char *outbuf, int outbuf_len,
	       struct format_choice **outbuf_choices,
	       char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	       struct format_ref_attr_list ***ref_attr_list,
	       struct format_ref_attr_list ***inref_attr_list)
{
	int i, j, k, ret, argc;
	Slapi_Entry *entry;
	Slapi_DN **these, **next;
	Slapi_ValueSet *values;
	Slapi_Value *value;
	int disposition, buffer_flags;
	char **argv, *attrs[2], *actual_attr;
	const char *dn, *cvalue;
	const struct berval *bval;
	struct berval **choices;
	struct format_ref_attr_list *list;

	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"deref_r: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc < 2) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"deref_r: requires at least two arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	if (outbuf_choices == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"deref_r: returns a list, but a list "
				"would not be appropriate\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}

	/* Note that this list of attributes is used for pulling up data. */
	format_add_ref_attr_list(ref_attr_list, group, set,
				 (const char **) argv);
	list = format_find_ref_attr_list(*ref_attr_list, group, set,
					 (const char **) argv);

	/* Follow the chain: set up the first link. */
	these = NULL;
	choices = NULL;
	dn = slapi_entry_get_dn(e);
	format_add_sdn_list(&these, dn);

	/* For the first N-1 links, read the contents of the named attribute
	 * from each entry we're examining at this point, and use the values
	 * to build a list of entries to visit the next time.  For the last
	 * link, pull the values out and prep them to be returned to our
	 * caller. */
	for (i = 0; (these != NULL) && (i < list->n_links); i++) {
		next = NULL;
		attrs[0] = list->links[i].attribute;
		attrs[1] = NULL;
		/* Walk the set of entries for this iteration. */
		for (j = 0; these[j] != NULL; j++) {
			/* For heuristic use later, note the parent of the
			 * entry from which we're reading this attribute. */
			dn = slapi_sdn_get_ndn(these[j]);
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"deref_r: noting parent "
					"\"%s\" for \"%s\"\n",
					slapi_dn_parent(dn), attrs[0]);
			format_add_sdn_list(&list->links[i].base_sdn_list,
					    slapi_dn_parent(dn));
			/* Pull up the named entry. */
			entry = NULL;
			wrap_search_internal_get_entry(these[j], attrs, &entry,
						       state->plugin_identity);
			if (entry == NULL) {
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"deref_r: error reading entry "
						"\"%s\"\n",
						slapi_sdn_get_dn(these[j]));
				continue;
			} else {
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"deref_r: reading entry "
						"\"%s\" (%d)\n",
						slapi_sdn_get_dn(these[j]), i);
			}
			/* Pull up the value set. */
			if (slapi_vattr_values_get(entry, attrs[0], &values,
						   &disposition,
						   &actual_attr,
						   0, &buffer_flags) != 0) {
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"deref_r: entry \"%s\" has no "
						"values for \"%s\"\n",
						slapi_sdn_get_dn(these[j]),
						attrs[0]);
				slapi_entry_free(entry);
				continue;
			}
			for (k = slapi_valueset_first_value(values, &value);
			     k != -1;
			     k = slapi_valueset_next_value(values, k, &value)){
				if (i < list->n_links - 1) {
					/* Get the text. */
					cvalue = slapi_value_get_string(value);
					/* If the value is empty, skip it. */
					if (cvalue == NULL) {
						continue;
					}
					/* Let's visit the named entry this
					 * time, in case we're nesting. */
					format_add_sdn_list(&these, cvalue);
					/* We need to visit the named entry
					 * next time. */
					format_add_sdn_list(&next, cvalue);
				} else {
					/* Get the value. */
					bval = slapi_value_get_berval(value);
					/* If the value is empty, skip it. */
					if (bval->bv_len == 0) {
						continue;
					}
					format_add_bv_list(&choices, bval);
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"deref_r: found value "
							"\"%.*s\" in \"%s\"\n",
							bval->bv_len,
							bval->bv_val, dn);
				}
			}
			slapi_vattr_values_free(&values, &actual_attr,
						buffer_flags);
			slapi_entry_free(entry);
		}
		/* Replace the list of entries we're examining now with the
		 * list of entries we need to examine next. */
		format_free_sdn_list(these);
		these = next;
		next = NULL;
	}

	/* Clean up and return any values we found. */
	format_free_sdn_list(these);
	format_free_parsed_args(argv);
	if (choices != NULL) {
		format_add_choice(outbuf_choices, outbuf, choices);
		format_free_bv_list(choices);
		return 0;
	} else {
		return -ENOENT;
	}
}

/* Look up entries in the set named by the first argument, which have this
 * entry's DN stored in the attribute named by the second argument, pull out
 * the values for the attribute named by the third argument, and return a list
 * of those values. */
struct format_referred_cbdata {
	struct plugin_state *state;
	char *attr;
	struct berval **choices;
};
static int
format_referred_entry_cb(Slapi_Entry *e, void *callback_data)
{
	Slapi_ValueSet *values;
	Slapi_Value *value;
	int i, disposition, buffer_flags;
	char *actual_attr;
	const struct berval *val;
	struct format_referred_cbdata *cbdata;

	cbdata = callback_data;

	slapi_log_error(SLAPI_LOG_PLUGIN,
			cbdata->state->plugin_desc->spd_id,
			"referred: examining \"%s\" in \%s\"\n",
			cbdata->attr, slapi_entry_get_ndn(e));

	/* Iterate through the values for the specified attribute. */
	if (slapi_vattr_values_get(e, cbdata->attr, &values,
				   &disposition, &actual_attr,
				   0, &buffer_flags) != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN,
				cbdata->state->plugin_desc->spd_id,
				"referred: no values for \"%s\" in \"%s\"\n",
				cbdata->attr, slapi_entry_get_ndn(e));
		return 0;
	}
	for (i = slapi_valueset_first_value(values, &value);
	     i != -1;
	     i = slapi_valueset_next_value(values, i, &value)) {
		/* Pull up the value. */
		val = slapi_value_get_berval(value);
		if (val->bv_len == 0) {
			continue;
		}
		slapi_log_error(SLAPI_LOG_PLUGIN,
				cbdata->state->plugin_desc->spd_id,
				"referred: got %d-byte value for \"%s\"\n",
				val->bv_len, actual_attr);
		/* Add it to the list of values we've retrieved. */
		format_add_bv_list(&cbdata->choices, val);
	}
	slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
	return 0;
}
static int
format_referred(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	        const char *group, const char *set,
		const char *args, const char *disallowed,
		char *outbuf, int outbuf_len,
		struct format_choice **outbuf_choices,
	        char ***ref_attrs, struct format_inref_attr ***inref_attrs,
		struct format_ref_attr_list ***ref_attr_list,
		struct format_ref_attr_list ***inref_attr_list)
{
	int i, ret, argc;
	Slapi_PBlock *local_pb;
	char **argv, *attrs[2], *filter, *tndn, *attr, *other_attr;
	char *other_set, *set_filter, **set_bases, *use_filter;
	struct format_referred_cbdata cbdata;

	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc != 3) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred: requires 3 arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	if (outbuf_choices == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred: returns a list, but a list would "
				"not be appropriate here\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	other_set = argv[0];
	other_attr = argv[1];
	attr = argv[2];

	/* Set up to search for matches. */
	local_pb = slapi_pblock_new();
	if (local_pb == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred: out of memory\n");
		format_free_parsed_args(argv);
		return -ENOMEM;
	}
	cbdata.state = state;
	cbdata.attr = attr;
	cbdata.choices = NULL;

	/* Retrieve the set-specific paramaters to determine which entries to
	 * examine. */
	set_filter = NULL;
	set_bases = NULL;
	backend_get_set_config(state, group, other_set,
			       &set_bases, &set_filter);
	if (set_bases == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN,
				state->plugin_desc->spd_id,
				"no search bases defined for \"%s\"/\"%s\"?\n",
				group, other_set);
		backend_free_set_config(set_bases, set_filter);
		slapi_pblock_destroy(local_pb);
		format_free_parsed_args(argv);
		return 0;
	}

	/* Note that the attribute in this map refers to this entry. */
	if (inref_attrs != NULL) {
		format_add_inref_attrs(inref_attrs, group,
				       other_set, other_attr);
	}

	/* Escape the current entry's DN in case it's necessary, and build a
	 * search filter. */
	tndn = format_escape_for_filter(slapi_entry_get_ndn(e));
	if (tndn == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN,
				state->plugin_desc->spd_id,
				"referred: out of memory\n");
		backend_free_set_config(set_bases, set_filter);
		slapi_pblock_destroy(local_pb);
		format_free_parsed_args(argv);
		return -ENOMEM;
	}
	use_filter = set_filter ? set_filter : "(objectClass=*)";
	filter = malloc(strlen(use_filter) + strlen(other_attr) +
			strlen(tndn) + 7);
	if (filter == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred: out of memory\n");
		backend_free_set_config(set_bases, set_filter);
		slapi_pblock_destroy(local_pb);
		format_free_parsed_args(argv);
		return -ENOMEM;
	}
	sprintf(filter, "(&(%s=%s)%s)", other_attr, tndn, use_filter);
	free(tndn);

	/* Search through the entries used for the set. */
	attrs[0] = attr;
	attrs[1] = NULL;
	for (i = 0; (set_bases != NULL) && (set_bases[i] != NULL); i++) {
		/* Set up the search. */
		slapi_search_internal_set_pb(local_pb,
					     set_bases[i], LDAP_SCOPE_SUBTREE,
					     filter, attrs, FALSE,
					     NULL, NULL,
					     state->plugin_identity, 0);
		/* Let the callback do the work of saving a value. */
		slapi_log_error(SLAPI_LOG_PLUGIN,
				state->plugin_desc->spd_id,
				"searching under \"%s\" for \"%s\"\n",
				set_bases[i], filter);
		slapi_search_internal_callback_pb(local_pb, &cbdata,
						  NULL,
						  format_referred_entry_cb,
						  NULL);
	}
	free(filter);

	/* Return any values we found. */
	if (cbdata.choices != NULL) {
		format_add_choice(outbuf_choices, outbuf, cbdata.choices);
		format_free_bv_list(cbdata.choices);
	}

	backend_free_set_config(set_bases, set_filter);
	slapi_pblock_destroy(local_pb);
	format_free_parsed_args(argv);
	return 0;
}

/* Add the name of this entry to the DN list in the cbdata. */
struct format_referred_r_entry_cbdata {
	struct plugin_state *state;
	char *attribute;
	struct berval ***choices;
	Slapi_DN ***sdn_list;
};

static int
format_referred_r_entry_cb(Slapi_Entry *e, void *cbdata_ptr)
{
	struct format_referred_r_entry_cbdata *cbdata = cbdata_ptr;
	const struct berval *bval;
	Slapi_DN *sdn;
	Slapi_ValueSet *values;
	Slapi_Value *value;
	int i, disposition, buffer_flags;
	char *actual_attr;

	/* Note that we visited this entry. */
	slapi_log_error(SLAPI_LOG_PLUGIN, cbdata->state->plugin_desc->spd_id,
			"search matched entry \"%s\"\n", slapi_entry_get_dn(e));
	format_add_sdn_list(cbdata->sdn_list, slapi_entry_get_dn(e));
	sdn = slapi_entry_get_sdn(e);

	/* If we're also being asked to pull values out of the entry... */
	if ((cbdata->attribute != NULL) && (cbdata->choices != NULL)) {
		/* Pull up the value set. */
		if (slapi_vattr_values_get(e, cbdata->attribute, &values,
					   &disposition,
					   &actual_attr,
					   0, &buffer_flags) != 0) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					cbdata->state->plugin_desc->spd_id,
					"referred_r: entry \"%s\" has no "
					"values for \"%s\"\n",
					slapi_sdn_get_dn(sdn),
					cbdata->attribute);
		} else {
			/* Walk the value set. */
			for (i = slapi_valueset_first_value(values, &value);
			     i != -1;
			     i = slapi_valueset_next_value(values, i, &value)){
				/* Get the value. */
				bval = slapi_value_get_berval(value);
				/* If the value is empty, skip it. */
				if (bval->bv_len == 0) {
					continue;
				}
				format_add_bv_list(cbdata->choices, bval);
				slapi_log_error(SLAPI_LOG_PLUGIN,
						cbdata->state->plugin_desc->spd_id,
						"referred_r: found value "
						"\"%.*s\" in \"%s\"\n",
						bval->bv_len,
						bval->bv_val,
						slapi_sdn_get_dn(sdn));
			}
			slapi_vattr_values_free(&values, &actual_attr,
						buffer_flags);
		}
	}
	return 0;
}

/* For the first N-1 arguments, treat them as pairs, looking entries in the
 * map named by the first part of the pair which refer to this entry using the
 * attribute named by the second part in the pair, following links until we
 * get to the last argument, at which point we return the value of the
 * attribute named by the final argument. */
static int
format_referred_r(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
		  const char *group, const char *set,
		  const char *args, const char *disallowed,
		  char *outbuf, int outbuf_len,
		  struct format_choice **outbuf_choices,
		  char ***ref_attrs, struct format_inref_attr ***inref_attrs,
		  struct format_ref_attr_list ***ref_attr_list,
		  struct format_ref_attr_list ***inref_attr_list)
{
	int i, j, k, ret, argc, attrs_list_length;
	Slapi_PBlock *local_pb;
	Slapi_DN **these_bases, **next_bases, **these_entries, **next_entries;
	struct berval **choices;
	struct format_referred_r_entry_cbdata entry_cbdata;
	struct format_ref_attr_list *list;
	char **argv, *attrs[2], *filter, *tndn, *attr;
	char *set_filter, **set_bases;
	const char **attr_links, *ndn;

	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred_r: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc < 3) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred_r: requires at least 3 arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	if ((argc % 2) != 1) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred_r: requires an odd number of "
				"arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	if (outbuf_choices == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred_r: returns a list, but a list would "
				"not be appropriate here\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	attr = argv[argc - 1];

	/* Build the list of attributes which we can use to select the list of
	 * references. */
	attrs_list_length = (argc + 1) / 2;
	attr_links = malloc((attrs_list_length + 1) * sizeof(char *));
	if (attr_links == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred_r: out of memory\n");
		format_free_parsed_args(argv);
		return -ENOMEM;
	}
	for (i = 0; i < attrs_list_length; i++) {
		if (i < (attrs_list_length - 1)) {
			attr_links[i] = argv[i * 2 + 1];
		} else {
			attr_links[i] = argv[i * 2];
		}
	}
	attr_links[i] = NULL;

	/* Note this list of attributes. */
	format_add_ref_attr_list(inref_attr_list, group, set, attr_links);
	list = format_find_ref_attr_list(*inref_attr_list, group, set,
					 attr_links);
	free(attr_links);

	/* Set up to search for referrers. */
	local_pb = slapi_pblock_new();
	if (local_pb == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"referred_r: out of memory\n");
		format_free_parsed_args(argv);
		return -ENOMEM;
	}

	/* Get the searching parameters for the set which contains the entry,
	 * and all of the referred-to sets, and save them for use at the last
	 * link in the chain. */
	backend_get_set_config(state, group, set,
			       &set_bases, &set_filter);
	for (i = 0; (set_bases != NULL) && (set_bases[i] != NULL); i++) {
		format_add_sdn_list(&(list->links[0].base_sdn_list),
				    set_bases[i]);
	}
	backend_free_set_config(set_bases, set_filter);
	for (i = 0; i < list->n_links - 1; i++) {
		backend_get_set_config(state, group, argv[i * 2],
				       &set_bases, &set_filter);
		for (j = 0;
		     (set_bases != NULL) && (set_bases[j] != NULL);
		     j++) {
			format_add_sdn_list(&(list->links[i + 1].base_sdn_list),
					    set_bases[j]);
		}
		backend_free_set_config(set_bases, set_filter);
	}

	/* Walk the chain, searching for entries which refer to entries at
	 * this point in the chain. */
	these_entries = NULL;
	format_add_sdn_list(&these_entries, slapi_entry_get_dn(e));
	choices = NULL;
	next_entries = NULL;
	attrs[0] = attr;
	attrs[1] = NULL;
	for (i = 0; i < list->n_links - 1; i++) {
		these_bases = list->links[i].base_sdn_list;
		if (i < list->n_links - 1) {
			next_bases = list->links[i + 1].base_sdn_list;
		} else {
			next_bases = NULL;
		}
		/* Perform the search for entries which refer to each entry we
		 * see here. */
		for (j = 0;
		     (these_entries != NULL) && (these_entries[j] != NULL);
		     j++) {
			ndn = slapi_sdn_get_ndn(these_entries[j]);
			tndn = format_escape_for_filter(ndn);
			if (tndn == NULL) {
				continue;
			}
			/* Walk the set of search bases for this link. */
			filter = malloc(strlen(list->links[i].attribute) +
					strlen(tndn) + 4);
			if (filter == NULL) {
				free(tndn);
				continue;
			}
			sprintf(filter, "(%s=%s)",
				list->links[i].attribute, tndn);
			for (k = 0;
			     (these_bases != NULL) && (these_bases[k] != NULL);
			     k++) {
				ndn = slapi_sdn_get_dn(these_bases[k]);
				/* Search for referrers under this tree. */
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"referred_r: searching under %s"
						" for \"%s\" (link=1.%d)\n",
						ndn, filter, i);
				slapi_search_internal_set_pb(local_pb,
							     ndn,
							     LDAP_SCOPE_SUBTREE,
							     filter, attrs,
							     FALSE,
							     NULL, NULL,
							     state->plugin_identity,
							     0);
				entry_cbdata.state = state;
				entry_cbdata.attribute = attr;
				entry_cbdata.choices = &choices;
				entry_cbdata.sdn_list = &these_entries;
				slapi_search_internal_callback_pb(local_pb,
								  &entry_cbdata,
								  NULL,
								  format_referred_r_entry_cb,
								  NULL);
			}
			free(filter);
			/* Walk the set of search bases for the next link. */
			filter = malloc(strlen(list->links[i].attribute) +
					strlen(tndn) + 4);
			if (filter == NULL) {
				free(tndn);
				continue;
			}
			sprintf(filter, "(%s=%s)",
				list->links[i].attribute, tndn);
			for (k = 0;
			     (next_bases != NULL) && (next_bases[k] != NULL);
			     k++) {
				ndn = slapi_sdn_get_dn(next_bases[k]);
				/* Search for referrers under that tree. */
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"referred_r: searching under %s"
						" for \"%s\" (link=2.%d)\n",
						ndn, filter, i);
				slapi_search_internal_set_pb(local_pb,
							     ndn,
							     LDAP_SCOPE_SUBTREE,
							     filter, attrs,
							     FALSE,
							     NULL, NULL,
							     state->plugin_identity,
							     0);
				entry_cbdata.state = state;
				entry_cbdata.attribute = attr;
				entry_cbdata.choices = &choices;
				entry_cbdata.sdn_list = &next_entries;
				slapi_search_internal_callback_pb(local_pb,
								  &entry_cbdata,
								  NULL,
								  format_referred_r_entry_cb,
								  NULL);
			}
			free(filter);
			free(tndn);
		}
		/* Set up for the next iteration. */
		format_free_sdn_list(these_entries);
		these_entries = next_entries;
		next_entries = NULL;
	}
	format_free_sdn_list(these_entries);

	slapi_pblock_destroy(local_pb);
	format_free_parsed_args(argv);

	/* Return any values we found. */
	if (choices != NULL) {
		format_add_choice(outbuf_choices, outbuf, choices);
		format_free_bv_list(choices);
		return 0;
	} else {
		return -ENOENT;
	}
}

/* Evaluate each argument's list of results, after the first, in turn, and
 * merge them, using the first argument as a separator. */
static int
format_merge(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	     const char *group, const char *set,
	     const char *args, const char *disallowed,
	     char *outbuf, int outbuf_len,
	     struct format_choice **outbuf_choices,
	     char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	     struct format_ref_attr_list ***ref_attr_list,
	     struct format_ref_attr_list ***inref_attr_list)
{
	int ret, i, j, argc, slen, count;
	unsigned int *lengths;
	char **argv, **values;
	const char *sep;
	struct format_choice *these_choices;

	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"merge: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc < 1) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"merge: requires at least one argument\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	sep = argv[0];
	slen = strlen(sep);
	for (i = 1, ret = 0, count = 0; i < argc; i++) {
		/* Expand this argument. */
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"merge: expanding ->%s<-\n", argv[i]);
		these_choices = NULL;
		values = format_get_data_set(state, e, group, set,
					     argv[i], disallowed,
					     ref_attrs, inref_attrs,
					     ref_attr_list, inref_attr_list,
					     &lengths);
		if (values == NULL) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"merge: no values for ->%s<-\n",
					argv[i]);
			continue;
		}
		for (j = 0; values[j] != NULL; j++) {
			/* Check if there's space for this value. */
			if (ret + lengths[j] + (count ? slen : 0) >
			    (unsigned int) outbuf_len) {
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"merge: out of space\n");
				format_free_data_set(values, lengths);
				format_free_parsed_args(argv);
				return -ENOBUFS;
			}
			/* Log this value. */
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"merge: got %d-byte value for ->%s<\n",
					lengths[j], argv[i]);
			/* If this isn't the first result, fill in the
			 * separator.  Then fill in the value. */
			if (count > 0) {
				memcpy(outbuf + ret, sep, slen);
				ret += slen;
			}
			memcpy(outbuf + ret, values[j], lengths[j]);
			ret += lengths[j];
			count++;
		}
		format_free_data_set(values, lengths);
	}
	format_free_parsed_args(argv);
	return ret;
}

/* Look up the entry's values for the attribute named by the first argument,
 * and use the callback to check if they match the second argument.  If we find
 * exactly one match, store it in the output buffer, otherwise store the text
 * of the default_arg'th argument if given, or return an error if no
 * default_arg'th argument was given. */
static int
format_match_generic(struct plugin_state *state,
		     Slapi_PBlock *pb, Slapi_Entry *e,
		     const char *group, const char *set,
		     const char *args, int min_args, int default_arg,
		     const char *disallowed,
		     char *outbuf, int outbuf_len,
		     struct format_choice **outbuf_choices,
		     char ***ref_attrs,
		     struct format_inref_attr ***inref_attrs,
		     struct format_ref_attr_list ***ref_attr_list,
		     struct format_ref_attr_list ***inref_attr_list,
		     const char *fnname,
		     char * (*match_fn)(const char *pattern, const char *value,
		     			char **argv))
{
	char *cvalue, **argv, **matches, **values, *plugin_id, *default_value;
	struct berval *defaults[2], default_bv;
	int i, count, argc, ret, len;
	unsigned int *lengths, default_length;

	plugin_id = state->plugin_desc->spd_id;
	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
				"%s: error parsing arguments\n", fnname);
		return -EINVAL;
	}
	if (argc < min_args) {
		slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
				"%s: requires at least %d arguments\n",
				fnname, min_args);
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	/* Evaluate the expression as a list, then walk it. */
	matches = NULL;
	count = 0;
	lengths = NULL;
	values = format_get_data_set(state, e, group, set,
				     argv[0], disallowed,
				     ref_attrs, inref_attrs,
				     ref_attr_list, inref_attr_list,
				     &lengths);
	if (values != NULL) {
		for (i = 0; values[i] != NULL; i++) {
			continue;
		}
		matches = malloc(sizeof(char *) * (i + 1));
		if (matches != NULL) {
			for (i = 0; values[i] != NULL; i++) {
				cvalue = xstrndup(values[i], lengths[i]);
				matches[count] = match_fn(argv[1], cvalue,
							  argv + 2);
				free(cvalue);
				if (matches[count] != NULL) {
					count++;
				}
			}
			matches[count] = NULL;
		}
		format_free_data_set(values, lengths);
	}
	/* Make sure matched is either the single match, the default, or NULL
	 * if we had no default. */
	switch (count) {
	case 0:
		/* No matches.  Try to generate the default value. */
		default_value = NULL;
		if ((default_arg >= 0) && (argv[default_arg] != NULL)) {
			default_value = format_get_data(state, e, group, set,
							argv[default_arg],
							disallowed,
							ref_attrs, inref_attrs,
							ref_attr_list,
							inref_attr_list,
							&default_length);
		}
		if (default_value != NULL) {
			/* Try to store the default value. */
			slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
					"%s: no matching values for "
					"\"%s\", using default value \"%s\"\n",
					fnname, argv[1], default_value);
			if (outbuf_choices != NULL) {
				/* Return the default value as a list. */
				default_bv.bv_len = default_length;
				default_bv.bv_val = default_value;
				defaults[0] = &default_bv;
				defaults[1] = NULL;
				format_add_choice(outbuf_choices, outbuf,
						  defaults);
				len = 0;
			} else {
				/* Store the default directly in the buffer. */
				len = default_length;
				if (len > outbuf_len) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
							plugin_id,
							"%s: out of space\n",
							fnname);
					format_free_data(default_value);
					format_free_parsed_args(argv);
					free(matches);
					return -ENOBUFS;
				}
				memcpy(outbuf, default_value, default_length);
			}
			format_free_data(default_value);
		} else {
			slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
					"%s: no matching values for "
					"\"%s\", and no default value "
					"generated by \"%s\"\n",
					fnname, argv[1]);
			format_free_parsed_args(argv);
			free(matches);
			return -ENOENT;
		}
		break;
	case 1:
		/* Single result. */
		if (outbuf_choices != NULL) {
			/* Return the one match as a list. */
			format_add_choice_str(outbuf_choices, outbuf, matches);
			len = 0;
		} else {
			/* Store the one match directly in the buffer. */
			len = strlen(matches[0]);
			if (len > outbuf_len) {
				slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
						"%s: out of space\n", fnname);
				free(matches[0]);
				free(matches);
				format_free_parsed_args(argv);
				return -ENOBUFS;
			}
			memcpy(outbuf, matches[0], len);
		}
		break;
	default:
		if (outbuf_choices != NULL) {
			/* Record the set of matching values as choices at this
			 * location. */
			format_add_choice_str(outbuf_choices, outbuf, matches);
			len = 0;
		} else {
			/* Too many matches to store. */
			default_value = NULL;
			if ((default_arg >= 0) && (argv[default_arg] != NULL)) {
				default_value = format_get_data(state, e,
								group, set,
								argv[default_arg],
								disallowed,
								ref_attrs,
								inref_attrs,
								ref_attr_list,
								inref_attr_list,
								&default_length);
			}
			if (default_value != NULL) {
				slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
						"%s: too many matching values "
						"for \"%s\", using default "
						"value \"%s\"\n",
						fnname, argv[1], default_value);
				len = default_length;
				if (len > outbuf_len) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
							plugin_id,
							"%s: out of space\n",
							fnname);
					format_free_data(default_value);
					for (i = 0; i < count; i++) {
						free(matches[i]);
					}
					free(matches);
					format_free_parsed_args(argv);
					return -ENOBUFS;
				}
				memcpy(outbuf, default_value, default_length);
				format_free_data(default_value);
			} else {
				slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
						"%s: too many matching values "
						"for \"%s\", and no default "
						"value provided by \"%s\"\n",
						fnname, argv[1]);
				for (i = 0; i < count; i++) {
					free(matches[i]);
				}
				free(matches);
				format_free_parsed_args(argv);
				return -ENOENT;
			}
		}
		break;
	}
	if (matches != NULL) {
		for (i = 0; i < count; i++) {
			free(matches[i]);
		}
		free(matches);
	}
	format_free_parsed_args(argv);
	return len;
}

/* Check for glob-style matched values. */
static char *
format_match_cb(const char *pattern, const char *value, char **argv)
{
	return (fnmatch(pattern, value, 0) == 0) ? strdup(value) : NULL;
}
static int
format_match(struct plugin_state *state,
	     Slapi_PBlock *pb, Slapi_Entry *e,
	     const char *group, const char *set,
	     const char *args, const char *disallowed,
	     char *outbuf, int outbuf_len,
	     struct format_choice **outbuf_choices,
	     char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	     struct format_ref_attr_list ***ref_attr_list,
	     struct format_ref_attr_list ***inref_attr_list)
{
	return format_match_generic(state, pb, e, group, set, args, 2, 2,
				    disallowed,
				    outbuf, outbuf_len, outbuf_choices,
				    ref_attrs, inref_attrs,
				    ref_attr_list, inref_attr_list,
				    "format_match", format_match_cb);
}

/* Check for a regex match. */
static char *
format_regmatch_cb(const char *pattern, const char *value, char **argv)
{
	regex_t reg;
	regmatch_t matches;
	bool_t matched;
	memset(&reg, 0, sizeof(reg));
	if (regcomp(&reg, pattern, REG_EXTENDED | REG_NOSUB) != 0) {
		return NULL;
	}
	matched = (regexec(&reg, value, 1, &matches, 0) == 0);
	regfree(&reg);
	return matched ? strdup(value) : NULL;
}
static int
format_regmatch(struct plugin_state *state,
	        Slapi_PBlock *pb, Slapi_Entry *e,
		const char *group, const char *set,
	        const char *args, const char *disallowed,
		char *outbuf, int outbuf_len,
		struct format_choice **outbuf_choices,
		char ***ref_attrs, struct format_inref_attr ***inref_attrs,
		struct format_ref_attr_list ***ref_attr_list,
		struct format_ref_attr_list ***inref_attr_list)
{
	return format_match_generic(state, pb, e, group, set, args, 2, 2,
				    disallowed,
				    outbuf, outbuf_len, outbuf_choices,
				    ref_attrs, inref_attrs,
				    ref_attr_list, inref_attr_list,
				    "format_regmatch", format_regmatch_cb);
}

/* Check for a regex match and build a custom result from the matching value. */
static char *
format_regsub_cb(const char *pattern, const char *value, char **argv)
{
	regex_t reg;
	regmatch_t matches[10];
	bool_t matched;
	int i, j, m, len;
	char *template, *ret;
	memset(&reg, 0, sizeof(reg));
	if (regcomp(&reg, pattern, REG_EXTENDED) != 0) {
		return NULL;
	}
	memset(&matches, 0, sizeof(matches));
	i = regexec(&reg, value,
		    sizeof(matches) / sizeof(matches[0]), &matches[0],
		    0);
	matched = (i == 0);
	regfree(&reg);
	if (!matched) {
		return NULL;
	}
	template = argv[0];
	for (i = 0, len = 0; (template != NULL) && (template[i] != '\0'); i++) {
		switch (template[i]) {
		case '%':
			i++;
			switch (template[i]) {
			case '%':
				len++;
				continue;
				break;
			case '0':
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
				m = template[i] - '0';
				if (matches[m].rm_so != -1) {
					len += (matches[m].rm_eo -
					        matches[m].rm_so);
				}
				continue;
				break;
			default:
				len++;
				break;
			}
			break;
		default:
			len++;
			break;
		}
	}
	ret = malloc(len + 1);
	if (ret == NULL) {
		return NULL;
	}
	for (i = 0, j = 0;
	     (template != NULL) && (template[i] != '\0') && (j < len);
	     i++) {
		switch (template[i]) {
		case '%':
			i++;
			switch (template[i]) {
			case '%':
				ret[j++] = template[i];
				continue;
				break;
			case '0':
			case '1':
			case '2':
			case '3':
			case '4':
			case '5':
			case '6':
			case '7':
			case '8':
			case '9':
				m = template[i] - '0';
				if (matches[m].rm_so != -1) {
					memcpy(ret + j,
					       value + matches[m].rm_so,
					       matches[m].rm_eo -
					       matches[m].rm_so);
					j += (matches[m].rm_eo -
					      matches[m].rm_so);
				}
				continue;
				break;
			default:
				ret[j++] = template[i];
				break;
			}
			break;
		default:
			ret[j++] = template[i];
			break;
		}
	}
	ret[j] = '\0';
	return ret;
}
static int
format_regsub(struct plugin_state *state,
	      Slapi_PBlock *pb, Slapi_Entry *e,
	      const char *group, const char *set,
	      const char *args, const char *disallowed,
	      char *outbuf, int outbuf_len,
	      struct format_choice **outbuf_choices,
	      char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	      struct format_ref_attr_list ***ref_attr_list,
	      struct format_ref_attr_list ***inref_attr_list)
{
	return format_match_generic(state, pb, e, group, set, args, 3, 3,
				    disallowed,
				    outbuf, outbuf_len, outbuf_choices,
				    ref_attrs, inref_attrs,
				    ref_attr_list, inref_attr_list,
				    "format_regsub", format_regsub_cb);
}

/* If the attribute given by the first argument is equal to the value given in
 * the second, return the third, else return the fourth.  We used to allow an
 * expression instead of an attribute name, but then it was never clear how
 * exactly we needed to do the comparison check (specifically,
 * case-sensitivity). */
static int
format_ifeq(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	    const char *group, const char *set,
	    const char *args, const char *disallowed,
	    char *outbuf, int outbuf_len,
	    struct format_choice **outbuf_choices,
	    char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	    struct format_ref_attr_list ***ref_attr_list,
	    struct format_ref_attr_list ***inref_attr_list)
{
	int ret, argc, i;
	unsigned int *lengths;
	char **argv, **values;
	bool_t matched;
	struct berval bv, **choices;
	Slapi_Value *value;

	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"ifeq: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc < 1) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"ifeq: error parsing arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	if (argc != 4) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"ifeq: expected four arguments (got %d)\n",
				argc);
		format_free_parsed_args(argv);
		return -EINVAL;
	}

	/* Evaluate the value expression to get a list of candidate values. */
	values = format_get_data_set(state, e, group, set,
				     argv[1], disallowed,
				     ref_attrs, inref_attrs,
				     ref_attr_list, inref_attr_list,
				     &lengths);
	if (values == NULL) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"ifeq: error evaluating \"%s\"\n", argv[1]);
		format_free_parsed_args(argv);
		return -EINVAL;
	}

	/* Check if any of the value expression's values match the entry's
	 * value for the named attribute. */
	matched = FALSE;
	value = slapi_value_new();
	for (i = 0; values[i] != NULL; i++) {
		bv.bv_val = values[i];
		bv.bv_len = lengths[i];
		slapi_value_set_berval(value, &bv);
		if ((slapi_vattr_value_compare(e, argv[0], value,
					       &ret, 0) == 0) &&
		    (ret == 1)) {
			matched = TRUE;
			break;
		}
	}
	slapi_value_free(&value);
	slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
			"ifeq: \"%s\" %s \"%s\"\n",
			argv[0], matched ? "matches" : "doesn't match",
			argv[1]);
	format_free_data_set(values, lengths);

	/* Evaluate the argument which corresponds to the output expression and
	 * return its values. */
	ret = format_expand(state, pb, e, group, set,
			    argv[matched ? 2 : 3], disallowed,
			    outbuf, outbuf_len,
			    outbuf_choices,
			    ref_attrs, inref_attrs,
			    ref_attr_list, inref_attr_list);
	format_free_parsed_args(argv);
	return ret;
}

/* Evaluate all of the arguments, and concatentate all of the lists of results
 * to produce one long list. */
static int
format_collect(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	       const char *group, const char *set,
	       const char *args, const char *disallowed,
	       char *outbuf, int outbuf_len,
	       struct format_choice **outbuf_choices,
	       char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	       struct format_ref_attr_list ***ref_attr_list,
	       struct format_ref_attr_list ***inref_attr_list)
{
	int ret, argc, i, j;
	unsigned int *lengths;
	char **argv, **values;
	bool_t matched;
	struct berval bv, **choices;
	Slapi_Value *value;

	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"collect: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc < 1) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"collect: error parsing arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}

	/* Walk the list of the arguments. */
	choices = NULL;
	for (i = 0; i < argc; i++) {
		/* Evaluate this argument. */
		values = format_get_data_set(state, e, group, set,
					     argv[i], disallowed,
					     ref_attrs, inref_attrs,
					     ref_attr_list, inref_attr_list,
					     &lengths);
		if (values != NULL) {
			/* Walk the list of values. */
			for (j = 0; values[j] != NULL; j++) {
				/* Add it to the list. */
				bv.bv_val = values[j];
				bv.bv_len = lengths[j];
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"collect: \"%.*s\"\n",
						bv.bv_len, bv.bv_val);
				format_add_bv_list(&choices, &bv);
			}
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"collect: expanded \"%s\" to produce "
					"%d values for \"%s\"\n", argv[i], j,
					slapi_entry_get_dn(e));
			format_free_data_set(values, lengths);
		} else {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"collect: expanding \"%s\" produced "
					"no values for \"%s\"\n", argv[i],
					slapi_entry_get_dn(e));
		}
	}

	if (choices != NULL) {
		for (i = 0; choices[i] != NULL; i++) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"collect: returning \"%.*s\" for "
					"\"%s\"\n",
					choices[i]->bv_len,
					choices[i]->bv_val,
					slapi_entry_get_dn(e));
			continue;
		}
		slapi_log_error(SLAPI_LOG_PLUGIN,
				state->plugin_desc->spd_id,
				"collect: returning %d values for \"%s\"\n", i,
				slapi_entry_get_dn(e));
		format_add_choice(outbuf_choices, outbuf, choices);
		format_free_bv_list(choices);
		ret = 0;
	} else {
		ret = -ENOENT;
	}

	format_free_parsed_args(argv);

	return ret;
}

/* Evaluate all of the arguments, and concatentate sets of entries from each
 * list, separating them with an optional separator, padding the lists with a
 * specified value until all of the elements of all lists have been used. */
static int
format_link(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	    const char *group, const char *set,
	    const char *args, const char *disallowed,
	    char *outbuf, int outbuf_len,
	    struct format_choice **outbuf_choices,
	    char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	    struct format_ref_attr_list ***ref_attr_list,
	    struct format_ref_attr_list ***inref_attr_list)
{
	int ret, argc, i, *j, l, n_lists, n_done;
	unsigned int **lengths, length, max_length;
	char **argv, ***values, *buffer, *p;
	struct berval bv, **choices;

	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"link: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc < 1) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"link: error parsing arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	if (((argc + 1) % 3) != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"link: wrong number of arguments\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}

	/* Allocate space to store the information. */
	values = malloc(sizeof(char **) * ((argc + 1) / 3));
	lengths = malloc(sizeof(int *) * ((argc + 1) / 3));
	j = malloc(sizeof(int) * ((argc + 1) / 3));
	if ((values == NULL) || (lengths == NULL)) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"link: out of memory\n");
		format_free_parsed_args(argv);
		free(values);
		free(lengths);
		free(j);
		return -ENOMEM;
	}

	/* Walk the list of the arguments, building a list of lists. */
	choices = NULL;
	n_lists = 0;
	for (i = 0; i < argc; i += 3) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"link: evaluating \"%s\"\n", argv[i]);
		values[i / 3] = format_get_data_set(state, e, group, set,
						    argv[i], disallowed,
						    ref_attrs, inref_attrs,
						    ref_attr_list,
						    inref_attr_list,
						    &lengths[i / 3]);
		if (values[i / 3] != NULL) {
			n_lists++;
		}
	}

	/* If we got _no_ answers for anything, that's a NULL result. */
	if (n_lists == 0) {
		format_free_parsed_args(argv);
		free(values);
		free(lengths);
		free(j);
		return -ENOENT;
	}

	/* Walk the lists, building the output data items. */
	n_lists = (argc + 1) / 3;
	for (i = 0; i < n_lists; i++) {
		j[i] = 0;
	}
	n_done = 0;
	length = 0;
	max_length = 0;
	buffer = NULL;
	do {
		/* Calculate how much space we need. */
		length = 0;
		for (i = 0; i < n_lists; i++) {
			if ((values[i] != NULL) && (values[i][j[i]] != NULL)) {
				length += lengths[i][j[i]];
			} else {
				length += strlen(argv[i * 3 + 1]);
			}
			if (i < (n_lists - 1)) {
				length += strlen(argv[i * 3 + 2]);
			}
		}
		/* Make sure the buffer is large enough. */
		if (length > max_length) {
			free(buffer);
			buffer = malloc(length);
			if (buffer == NULL) {
				format_free_bv_list(choices);
				format_free_parsed_args(argv);
				for (i = 0; i < n_lists; i += 3) {
					format_free_data_set(values[i],
							     lengths[i]);
				}
				free(values);
				free(lengths);
				free(j);
				return -ENOMEM;
			}
			max_length = length;
		}
		/* Build the output value. */
		p = buffer;
		for (i = 0; i < n_lists; i++) {
			if ((values[i] != NULL) && (values[i][j[i]] != NULL)) {
				l = lengths[i][j[i]];
				memcpy(p, values[i][j[i]], l);
				p += l;
				(j[i])++;
			} else {
				l = strlen(argv[i * 3 + 1]);
				memcpy(p, argv[i * 3 + 1], l);
				p += l;
			}
			if (i < (n_lists - 1)) {
				l = strlen(argv[i * 3 + 2]);
				memcpy(p, argv[i * 3 + 2], l);
				p += l;
			}
		}
		/* Add it to the result list. */
		bv.bv_val = buffer;
		bv.bv_len = length;
		if ((p - buffer) != length) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"link: internal error\n");
			break;
		} else {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"link: \"%.*s\"\n",
					bv.bv_len, bv.bv_val);
			format_add_bv_list(&choices, &bv);
		}
		/* Figure out if we're done yet. */
		for (i = 0, n_done = 0; i < n_lists; i++) {
			if ((values[i] == NULL) || (values[i][j[i]] == NULL)) {
				n_done++;
			}
		}
	} while (n_done != n_lists);

	if (choices != NULL) {
		format_add_choice(outbuf_choices, outbuf, choices);
		format_free_bv_list(choices);
		ret = 0;
	} else {
		ret = -ENOENT;
	}

	format_free_parsed_args(argv);
	for (i = 0; i < argc; i += 3) {
		format_free_data_set(values[i / 3], lengths[i / 3]);
	}
	free(buffer);
	free(values);
	free(lengths);
	free(j);

	return ret;
}

/* Choose a formatting function by name. */
static void *
format_lookup_fn(const char *fnname)
{
	unsigned int i;
	struct {
		const char *name;
		int (*fct_ptr)(struct plugin_state *state,
			       Slapi_PBlock *pb, Slapi_Entry *e,
			       const char *group, const char *set,
			       const char *args, const char *disallowed,
			       char *outbuf, int outbuf_len,
			       struct format_choice **outbuf_choices,
			       char ***ref_attrs,
			       struct format_inref_attr ***inref_attrs,
			       struct format_ref_attr_list ***ref_attr_list,
			       struct format_ref_attr_list ***inref_attr_list);
	} fns[] = {
		{"first", format_first},
		{"deref", format_deref},
		{"deref_r", format_deref_r},
		{"referred", format_referred},
		{"referred_r", format_referred_r},
		{"merge", format_merge},
		{"match", format_match},
		{"regmatch", format_regmatch},
		{"regsub", format_regsub},
		{"ifeq", format_ifeq},
		{"collect", format_collect},
		{"link", format_link},
	};
	for (i = 0; i < sizeof(fns) / sizeof(fns[0]); i++) {
		if ((fns[i].name != NULL) &&
		    (strcmp(fns[i].name, fnname) == 0)) {
			return fns[i].fct_ptr;
		}
	}
	return NULL;
}

/* Check for the presence of any character in the disallowed list in the
 * passed-in value. */
static char *
format_check_disallowed(const struct berval *bv, const char *disallowed)
{
	int i;
	char *p;
	if (disallowed != NULL) {
		for (i = 0; disallowed[i] != '\0'; i++) {
			p = memchr(bv->bv_val, disallowed[i], bv->bv_len);
			if (p != NULL) {
				return p;
			}
		}
	}
	return NULL;
}
/* Retrieve a single value for an attribute.  If there are no values, or more
 * than one, return NULL.  If there's more than one, store the values in the
 * array argument. */
static struct berval
format_single(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	      const char *attr, const char *disallowed,
	      struct berval ***values)
{
	Slapi_ValueSet *value_set;
	Slapi_Value *value;
	char *ret, *actual_attr;
	const char *d;
	const struct berval *val;
	struct berval bv;
	int count, disposition, buffer_flags, i;
	memset(&bv, 0, sizeof(bv));
	if (slapi_vattr_values_get(e, (char *) attr, &value_set,
				   &disposition, &actual_attr,
				   0, &buffer_flags) != 0) {
		return bv;
	}
	count = slapi_valueset_count(value_set);
	ret = NULL;
	if (count == 1) {
		if (slapi_valueset_first_value(value_set, &value) != -1) {
			val = slapi_value_get_berval(value);
			d = format_check_disallowed(val, disallowed);
			if (d != NULL) {
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"value for \"%s\" "
						"contains disallowed "
						"character \"%c\", "
						"ignoring\n",
						attr, *d);
			} else {
				bv.bv_val = xmemdup(val->bv_val, val->bv_len);
				if (bv.bv_val != NULL) {
					bv.bv_len = val->bv_len;
				} else {
					bv.bv_len = 0;
				}
			}
		}
	} else {
		if ((count == 0) || (values == NULL)) {
			/* Either no results, or too many results with no place
			 * to put them. */
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"%d values for \"%s\"\n", count, attr);
		} else {
			/* Return the list of values. */
			if (values != NULL) {
				for (i = slapi_valueset_first_value(value_set,
								    &value);
				     i != -1;
				     i = slapi_valueset_next_value(value_set, i,
								   &value)) {
					val = slapi_value_get_berval(value);
					if (val->bv_len == 0) {
						continue;
					}
					d = format_check_disallowed(val,
								    disallowed);
					if (d == NULL) {
						format_add_bv_list(values, val);
					}
				}
			} else {
				bv.bv_len = -EINVAL;
			}
		}
	}
	slapi_vattr_values_free(&value_set, &actual_attr, buffer_flags);
	return bv;
}

/* Find the matching closing marker -- assumes that the first character in
 * pattern is the opener. */
static const char *
format_find_closer(const char *pair, const char *pattern)
{
	int i, dq, level = 0;
	for (i = 0, dq = 0; pattern[i] != '\0'; i++) {
		if (pattern[i] == '\\') {
			i++;
			continue;
		}
		if (pattern[i] == '"') {
			dq = !dq;
			continue;
		}
		if (!dq) {
			if (pattern[i] == pair[0]) {
				level++;
			} else {
				if (pattern[i] == pair[1]) {
					level--;
				}
			}
			if (level == 0) {
				return &pattern[i];
			}
		}
	}
	return NULL;
}

/* Trim off prefixes or suffixes which match the given patterns, free the
 * original, and return the result. */
static struct berval
format_trim_value(struct plugin_state *state, struct berval input,
		  const char *shortstart, const char *longstart,
		  const char *shortend, const char *longend,
		  const char *replace, const char *replaceall,
		  const char *replaceval)
{
	struct berval ret;
	char *buf;
	unsigned int i, len;
	buf = xmemdup(input.bv_val, input.bv_len);
	len = input.bv_len;
	if (buf != NULL) {
		if (shortstart) {
			/* The shortest initial subsection which matches gets
			 * trimmed off. */
			for (i = 0; i <= input.bv_len; i++) {
				memcpy(buf, input.bv_val, i);
				buf[i] = '\0';
				if (fnmatch(shortstart, buf, 0) == 0) {
					memcpy(buf, input.bv_val + i,
					       input.bv_len - i);
					buf[input.bv_len - i] = '\0';
					ret.bv_val = buf;
					ret.bv_len = input.bv_len - i;
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"trim-ss: ->%.*s<- => "
							"->%.*s<-\n",
							input.bv_len,
							input.bv_val,
							ret.bv_len,
							ret.bv_val);
					free(input.bv_val);
					return ret;
				}
			}
		}
		if (shortend) {
			/* The shortest ending substring which matches gets
			 * snipped. */
			for (i = 0; i <= input.bv_len; i++) {
				memcpy(buf,
				       input.bv_val + input.bv_len - i,
				       i);
				buf[i] = '\0';
				if (fnmatch(shortend, buf, 0) == 0) {
					memcpy(buf, input.bv_val,
					       input.bv_len - i);
					buf[input.bv_len - i] = '\0';
					ret.bv_val = buf;
					ret.bv_len = input.bv_len - i;
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"trim-se: ->%.*s<- => "
							"->%.*s<-\n",
							input.bv_len,
							input.bv_val,
							ret.bv_len,
							ret.bv_val);
					free(input.bv_val);
					return ret;
				}
			}
		}
		if (longstart) {
			/* The longest initial substring which matches gets
			 * skipped. */
			for (i = 0; i <= len; i++) {
				memcpy(buf, input.bv_val, (input.bv_len - i));
				buf[input.bv_len - i] = '\0';
				if (fnmatch(longstart, buf, 0) == 0) {
					memcpy(buf, input.bv_val + i,
					       input.bv_len - i);
					buf[input.bv_len - i] = '\0';
					ret.bv_val = buf;
					ret.bv_len = input.bv_len - i;
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"trim-ls: ->%.*s<- => "
							"->%.*s<-\n",
							input.bv_len,
							input.bv_val,
							ret.bv_len,
							ret.bv_val);
					free(input.bv_val);
					return ret;
				}
			}
		}
		if (longend) {
			/* The longest ending substring which matches gets
			 * snipped. */
			for (i = 0; i <= len; i++) {
				memcpy(buf, input.bv_val + i, input.bv_len - i);
				buf[input.bv_len - i] = '\0';
				if (fnmatch(longend, buf, 0) == 0) {
					memcpy(buf, input.bv_val,
					       input.bv_len - i);
					buf[i] = '\0';
					ret.bv_val = buf;
					ret.bv_len = input.bv_len - i;
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"trim-le: ->%.*s<- => "
							"->%.*s<-\n",
							input.bv_len,
							input.bv_val,
							ret.bv_len,
							ret.bv_val);
					free(input.bv_val);
					return ret;
				}
			}
		}
		if (replaceval == NULL) {
			replaceval = "";
		}
		if (replace) {
			/* FIXME */
		}
		if (replaceall) {
			/* FIXME */
		}
		free(buf);
	}
	return input;
}

/* Expand the simple expression into the output buffer. This is limited to one
 * attribute value, perhaps with a default or alternate value, perhaps with a
 * prefix or suffix stripped, perhaps with internal replacements made. */
static int
format_expand_simple(struct plugin_state *state,
		     Slapi_PBlock *pb, Slapi_Entry *e,
		     const char *group, const char *set,
		     const char *fmt, const char *disallowed,
		     char *outbuf, int outbuf_len,
		     struct format_choice **outbuf_choices,
		     char ***ref_attrs,
		     struct format_inref_attr ***inref_attrs,
		     struct format_ref_attr_list ***ref_attr_list,
		     struct format_ref_attr_list ***inref_attr_list)
{
	char *shortstart, *longstart, *shortend, *longend;
	struct berval tmp, **values;
	char *replace, *replaceall, *replaceval, *expr, *p;
	const char *attribute, *default_value, *alternate_value;
	size_t spn;
	int i;
	shortstart = NULL;
	longstart = NULL;
	shortend = NULL;
	longend = NULL;
	replace = NULL;
	replaceall = NULL;
	replaceval = NULL;
	expr = strdup(fmt);
	/* It's a simple expression, so evaluate it.  Check for substitutions
	 * and text to be stripped if the magic character occurs before the
	 * default/alternate signals. */
	if (strcspn(expr, "#%/!") < strcspn(expr, ":")) {
		spn = strcspn(expr, "#%/!");
		p = expr + spn;
		if (strncmp(p, "##", 2) == 0) {
			longstart = p + 2;
		}
		else if (strncmp(p, "%%", 2) == 0) {
			longend = p + 2;
		}
		else if (strncmp(p, "//", 2) == 0) {
			replaceall = p + 2;
		}
		else if (strncmp(p, "#", 1) == 0) {
			shortstart = p + 1;
		}
		else if (strncmp(p, "%", 1) == 0) {
			shortend = p + 1;
		}
		else if (strncmp(p, "/", 1) == 0) {
			replace = p + 1;
		}
		expr[spn] = '\0';
		if ((replace != NULL) || (replaceall != NULL)) {
			replaceval = NULL;
			if (replace != NULL) {
				spn = strcspn(replace, "/");
				replaceval = replace + spn;
			}
			if (replaceall != NULL) {
				spn = strcspn(replaceall, "/");
				replaceval = replaceall + spn;
			}
			if ((replaceval != NULL) &&
			    (*replaceval != '\0')) {
				*replaceval = '\0';
				replaceval++;
			}
		}
		attribute = expr;
		alternate_value = NULL;
		default_value = NULL;
	} else {
		/* Check if it uses a default/alternate value. */
		spn = strcspn(expr, ":");
		if (spn == strlen(expr)) {
			/* Plain old variable, no alternate or default value.
			 * */
			attribute = expr;
			alternate_value = NULL;
			default_value = NULL;
		} else {
			/* Make a copy of the attribute name. */
			expr[spn] = '\0';
			attribute = expr;
			alternate_value = NULL;
			default_value = NULL;
			/* Figure out if there's an alternate or default value
			 * given. */
			switch (expr[spn + 1]) {
			case '+':
				alternate_value = expr + spn + 2;
				break;
			case '-':
				default_value = expr + spn + 2;
				break;
			default:
				default_value = expr + spn + 1;
				break;
			}
		}
	}
	/* Retrieve the value. */
	values = NULL;
	tmp = format_single(state, pb, e, attribute, disallowed,
			    outbuf_choices ? &values : NULL);
	if (tmp.bv_val == NULL) {
		/* The attribute is undefined, or we're treating it as if it
		 * is. */
		if (values == NULL) {
			if (default_value != NULL) {
				/* Supply the default value, expanding it if
				 * needed. */
				i = format_expand(state, pb, e,
						  group, set,
						  default_value, NULL,
						  outbuf, outbuf_len,
						  outbuf_choices,
						  ref_attrs, inref_attrs,
						  ref_attr_list,
						  inref_attr_list);
				free(expr);
				return i;
			} else {
				/* No value, and no default: FAIL. */
				free(expr);
				return -ENOENT;
			}
		} else {
			if (alternate_value != NULL) {
				/* Supply the alternate value. */
				i = format_expand(state, pb, e,
						  group, set,
						  alternate_value, NULL,
						  outbuf, outbuf_len,
						  outbuf_choices,
						  ref_attrs, inref_attrs,
						  ref_attr_list,
						  inref_attr_list);
				free(expr);
				format_free_bv_list(values);
				return i;
			} else {
				/* Store nothing in the immediate position, but
				 * return a note that any of these values would
				 * be fine at this point in the output string.
				 * */
				format_add_choice(outbuf_choices,
						  outbuf, values);
				free(expr);
				format_free_bv_list(values);
				return 0;
			}
		}
	} else {
		if (values != NULL) {
			format_free_bv_list(values);
		}
		/* There's a suitable single value available. */
		if (alternate_value != NULL) {
			/* Supply the alternate value. */
			i = format_expand(state, pb, e,
					  group, set, alternate_value, NULL,
					  outbuf, outbuf_len, outbuf_choices,
					  ref_attrs, inref_attrs,
					  ref_attr_list, inref_attr_list);
			free(tmp.bv_val);
			free(expr);
			return i;
		} else {
			/* Munge up the looked-up value. */
			tmp = format_trim_value(state, tmp,
						shortstart, longstart,
						shortend, longend,
						replace, replaceall,
						replaceval);
			/* Supply the looked-up value. */
			if (tmp.bv_val != NULL) {
				if (tmp.bv_len <= (unsigned int) outbuf_len) {
					memcpy(outbuf, tmp.bv_val, tmp.bv_len);
				}
				free(tmp.bv_val);
				free(expr);
				return tmp.bv_len;
			} else {
				/* No useful value: FAIL. */
				free(expr);
				return -ENOENT;
			}
		}
	}
	/* not reached */
}

/* Recursively expand the expression into the output buffer.  If the result
 * will also be an expression, treat the entire result as an attribute
 * specifier and evaluate it, otherwise return it. */
static int
format_expand(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	      const char *group, const char *set,
	      const char *fmt, const char *disallowed,
	      char *outbuf, int outbuf_len,
	      struct format_choice **outbuf_choices,
	      char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	      struct format_ref_attr_list ***ref_attr_list,
	      struct format_ref_attr_list ***inref_attr_list)
{
	int i, j, used;
	const char *fmtstart, *fmtend, *match, *pair;
	char *subexp, *fnname, *params, *spd_id;
	const char *paramstart, *paramend;
	int (*formatfn)(struct plugin_state *state,
		        Slapi_PBlock *pb, Slapi_Entry *e,
			const char *group, const char *set,
			const char *args, const char *disallowed,
		        char *outbuf, int outbuf_len,
			struct format_choice **outbuf_choices,
			char ***ref_attrs,
			struct format_inref_attr ***inref_attrs,
			struct format_ref_attr_list ***ref_attr_list,
			struct format_ref_attr_list ***inref_attr_list);

	spd_id = state->plugin_desc->spd_id;

	/* Expand any subexpressions and call any "functions". */
	i = 0;
	j = 0;
	while ((fmt[i] != '\0') && (j < outbuf_len)) {
		switch (fmt[i]) {
		case '%':
			/* This might be a subexpression, a "function" call, or
			 * an escaped character. */
			switch (fmt[i + 1]) {
			case '%':
				/* It's just an escaped "%". */
				outbuf[j++] = '%';
				i += 2;
				continue;
				break;
			case '{':
				/* Find the beginning of the simple expression.
				 */
				fmtstart = fmt + i;
				/* Find the end of the simple expression. */
				match = format_find_closer("{}", fmtstart + 1);
				if (match == NULL) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion failed: "
							"no closing brace\n");
					return -EINVAL;
				} else {
					/* Track the first character after the
					 * simple expression. */
					fmtend = match + 1;
					/* Make a copy of the simple
					 * expression. */
					subexp = xstrndupp(fmtstart + 2,
							   fmtend - 1);
					if (subexp == NULL) {
						slapi_log_error(SLAPI_LOG_PLUGIN,
								spd_id,
								"expansion "
								"failed: out "
								"of memory\n");
						return -ENOMEM;
					}
					/* Expand the simple expression. */
					used = format_expand_simple(state,
								    pb, e,
								    group,
								    set,
								    subexp,
								    disallowed,
								    outbuf + j,
								    outbuf_len - j,
								    outbuf_choices,
								    ref_attrs,
								    inref_attrs,
								    ref_attr_list,
								    inref_attr_list);
					if (used < 0) {
						/* Some failure, FAIL. */
						slapi_log_error(SLAPI_LOG_PLUGIN,
								spd_id,
								"error "
								"expanding "
								"expression "
								"->%s<-: %s\n",
								subexp,
								strerror(-used));
						free(subexp);
						return used;
					}
					free(subexp);
					subexp = NULL;
					if (used + j >= outbuf_len) {
						/* Out of space, or would be,
						 * so return a failure. */
						slapi_log_error(SLAPI_LOG_PLUGIN,
								spd_id,
								"expansion "
								"failed: result"
								" would be too "
								"big\n");
						return -ENOBUFS;
					} else {
						/* It fit, so keep going. */
						i = (match + 1) - fmt;
						j += used;
					}
				}
				continue;
				break;
			default:
				/* Assume it's a "function" call.  Pick out the
				 * name of the function. */
				paramstart = strpbrk(fmt + i + 1, "{(");
				if (paramstart == NULL) {
					/* No start? Bad format. */
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion failed: "
							"bad function "
							"invocation\n");
					return -EINVAL;
				}
				if (*paramstart == '{') {
					pair = "{}";
				} else {
					pair = "()";
				}
				paramend = format_find_closer(pair, paramstart);
				if (paramend == NULL) {
					/* No matching end? Bad format. */
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion failed: "
							"bad function "
							"invocation\n");
					return -EINVAL;
				}
				fnname = xstrndupp(fmt + i + 1, paramstart);
				if (fnname == NULL) {
					/* Out of memory, FAIL. */
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion failed: "
							"out of memory\n");
					return -ENOMEM;
				}
				/* Pick out the parameter list. */
				params = xstrndupp(paramstart + 1, paramend);
				if (params == NULL) {
					/* Out of memory, FAIL. */
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion failed: "
							"out of memory\n");
					free(fnname);
					return -ENOMEM;
				}
				/* Find the "function". */
				formatfn = format_lookup_fn(fnname);
				if (formatfn == NULL) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion "
							"failed: no function "
							"named \"%s\" is "
							"defined\n", fnname);
					free(fnname);
					free(params);
					return -ENOSYS;
				}
				/* Call the "function". */
				used = (*formatfn)(state, pb, e,
						   group, set,
						   params, disallowed,
						   outbuf + j, outbuf_len - j,
						   outbuf_choices,
						   ref_attrs, inref_attrs,
						   ref_attr_list,
						   inref_attr_list);
				free(params);
				params = NULL;
				if (used < 0) {
					/* Error in function, FAIL. */
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion "
							"failed: function "
							"'%s' failed: %s\n",
							fnname,
							strerror(-used));
					free(fnname);
					return used;
				}
				free(fnname);
				fnname = NULL;
				if (used + j >= outbuf_len) {
					/* We'd be out of space, fail. */
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion "
							"failed: result"
							" would be too "
							"big\n");
					return -ENOBUFS;
				}
				i = (paramend - fmt) + 1;
				j += used;
				continue;
				break;
			}
			break;
		default:
			/* Default is just a literal character. */
			outbuf[j++] = fmt[i++];
			break;
		}
	}
	outbuf[j] = '\0';

	if (j > outbuf_len) {
		return -ENOBUFS;
	} else {
		return j;
	}
}

static char *
format_format(struct plugin_state *state, Slapi_Entry *e,
	      const char *group, const char *set,
	      const char *fmt, const char *disallowed,
	      struct format_choice **choices,
	      char ***ref_attrs, struct format_inref_attr ***inref_attrs,
	      struct format_ref_attr_list ***ref_attr_list,
	      struct format_ref_attr_list ***inref_attr_list,
	      unsigned int *data_length)
{
	Slapi_PBlock *pb;
	char *buf, *ret, *spd_id;
	int i, buflen;

	spd_id = state->plugin_desc->spd_id;
	buflen = DEFAULT_BUFFER_SIZE;
	pb = slapi_pblock_new();
	do {
		buf = malloc(buflen);
		if (buf == NULL) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					spd_id,
					"expansion of \"%s\" "
					"for \"%s\" failing: out of memory\n",
					fmt,
					slapi_entry_get_ndn(e));
			slapi_pblock_destroy(pb);
			return NULL;
		}

		i = format_expand(state, pb, e, group, set,
				  fmt, disallowed,
				  buf, buflen, choices,
				  ref_attrs, inref_attrs,
				  ref_attr_list, inref_attr_list);
		if ((i >= 0) && (i < buflen)) {
			buf[i] = '\0';
			ret = xmemdup(buf, i);
			*data_length = i;
			format_retarget_choicesp(choices, buf, ret);
		} else {
			if (i == -ENOBUFS) {
				if (buflen < MAX_BUFFER_SIZE) {
					buflen *= 2;
#if 0
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion of \"%s\" "
							"for \"%s\" failed: %s "
							"(will try again)\n",
							fmt,
							slapi_entry_get_ndn(e),
							strerror(-i));
#endif
				} else {
					slapi_log_error(SLAPI_LOG_PLUGIN,
							spd_id,
							"expansion of \"%s\" "
							"for \"%s\" failed: %s "
							"(giving up)\n",
							fmt,
							slapi_entry_get_ndn(e),
							strerror(-i));
				}
			} else {
				slapi_log_error(SLAPI_LOG_PLUGIN, spd_id,
						"expansion of \"%s\" "
						"for \"%s\" failed: %s\n",
						fmt, slapi_entry_get_ndn(e),
						strerror(-i));
			}
			format_free_choicesp(choices);
			ret = NULL;
		}
		free(buf);
	} while (i == -ENOBUFS);

	slapi_pblock_destroy(pb);

	return ret;
}

void
format_free_data(char *data)
{
	if (data != NULL) {
		free(data);
	}
}
char *
format_get_data(struct plugin_state *state, Slapi_Entry *e,
		const char *group, const char *set,
		const char *fmt, const char *disallowed,
		char ***ref_attrs,
		struct format_inref_attr ***inref_attrs,
		struct format_ref_attr_list ***ref_attr_list,
		struct format_ref_attr_list ***inref_attr_list,
		unsigned int *data_length)
{
	unsigned int ignored;
	return format_format(state, e, group, set, fmt, disallowed,
			     NULL, ref_attrs, inref_attrs,
			     ref_attr_list, inref_attr_list,
			     data_length ? data_length : &ignored);
}

void
format_free_data_set(char **data, unsigned int *data_lengths)
{
	int i;
	if (data != NULL) {
		for (i = 0; data[i] != NULL; i++) {
			free(data[i]);
		}
		free(data);
	}
	free(data_lengths);
}
char **
format_get_data_set(struct plugin_state *state, Slapi_Entry *e,
		    const char *group, const char *set,
		    const char *fmt, const char *disallowed,
		    char ***ref_attrs,
		    struct format_inref_attr ***inref_attrs,
		    struct format_ref_attr_list ***ref_attr_list,
		    struct format_ref_attr_list ***inref_attr_list,
		    unsigned int **data_lengths)
{
	struct format_choice *choices, *this_choice;
	struct berval *val;
	char **ret, *template;
	int combinations, groupsize, i, j, k, offset, length;
	unsigned int template_len;
	choices = NULL;
	template = format_format(state, e, group, set, fmt, disallowed,
				 &choices,
				 ref_attrs, inref_attrs,
				 ref_attr_list, inref_attr_list,
				 &template_len);
	if (template == NULL) {
		format_free_choices(choices);
		return NULL;
	}
	/* Figure out how many results we're going to have. */
	combinations = 1;
	for (this_choice = choices;
	     this_choice != NULL;
	     this_choice = this_choice->next) {
		for (i = 0; i < this_choice->n_values; i++) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"choice: %d at %d\n",
					this_choice->values[i]->bv_len,
					this_choice->offset - template);
		}
		combinations *= this_choice->n_values;
	}
	if (combinations == 0) {
		format_free_choices(choices);
		return NULL;
	}
	ret = malloc((combinations + 1) * sizeof(char *));
	*data_lengths = malloc(sizeof(**data_lengths) * combinations);
	if ((ret != NULL) && (*data_lengths != NULL)) {
		/* Work out all of the results. */
		for (i = 0, j = 0; i < combinations; i++) {
			/* First figure out how long this result will be. */
			groupsize = combinations;
			length = template_len;
			for (this_choice = choices;
			     this_choice != NULL;
			     this_choice = this_choice->next) {
				/* Add the length of the value used here. */
				groupsize /= this_choice->n_values;
				val = this_choice->values[(i / groupsize) %
							  this_choice->n_values];
				length += val->bv_len;
			}
			/* Allocate memory for this result. */
			ret[j] = malloc(length + 1);
			if (ret[j] == NULL) {
				continue;
			}
			/* Build the result's value. */
			offset = 0;
			k = 0;
			groupsize = combinations;
			for (this_choice = choices;
			     this_choice != NULL;
			     this_choice = this_choice->next) {
				/* Copy any part of the template that should be
				 * in the result by now. */
				length = (this_choice->offset - template) -
					 offset;
				memcpy(ret[j] + k, template + offset, length);
				k += length;
				offset += length;
				groupsize /= this_choice->n_values;
				val = this_choice->values[(i / groupsize) %
							  this_choice->n_values];
				memcpy(ret[j] + k, val->bv_val, val->bv_len);
				k += val->bv_len;
			}
			/* Copy any part of the template which trails the
			 * choices. */
			length = template_len - offset;
			memcpy(ret[j] + k, template + offset, length);
			ret[j][k + length] = '\0';
			(*data_lengths)[j] = k + length;
			j++;
		}
		ret[j] = NULL;
	} else {
		free(ret);
		free(*data_lengths);
		ret = NULL;
		*data_lengths = NULL;
	}
	format_free_choices(choices);
	free(template);
	return ret;
}

char *
format_escape_for_filter(const char *unescaped)
{
	int i, j, count;
	char *ret;
	for (i = 0, count = 0; unescaped[i] != 0; i++) {
		switch (unescaped[i]) {
		case '*':
		case '(':
		case ')':
		case '\\':
			count++;
			break;
		default:
			break;
		}
	}
	ret = malloc(i + (2 * count) + 1);
	if (ret != NULL) {
		for (i = 0, j = 0; unescaped[i] != 0; i++) {
			switch (unescaped[i]) {
			case '*':
				ret[j++] = '\\';
				ret[j++] = '2';
				ret[j++] = 'a';
				break;
			case '(':
				ret[j++] = '\\';
				ret[j++] = '2';
				ret[j++] = '8';
				break;
			case ')':
				ret[j++] = '\\';
				ret[j++] = '2';
				ret[j++] = '9';
				break;
			case '\\':
				ret[j++] = '\\';
				ret[j++] = '5';
				ret[j++] = 'c';
				break;
			default:
				ret[j++] = unescaped[i];
				break;
			}
		}
		ret[j] = '\0';
	}
	return ret;
}