/*
 * 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);

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);
}

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);
}

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);
	}
}

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

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);
			}
		}
	}
}
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 attribute in the entry. */
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)
{
	int ret, i, argc;
	Slapi_ValueSet *values;
	Slapi_Value *value;
	const struct berval *val;
	char **argv, *actual_attr;
	int disposition, buffer_flags;
	ret = format_parse_args(state, args, &argc, &argv);
	if (argc != 1) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"first: error parsing arguments\n");
		return -EINVAL;
	}
	ret = -ENOENT;
	/* Get the list of values for this attribute. */
	if (slapi_vattr_values_get(e, argv[0], &values, &disposition,
				   &actual_attr, 0,
				   &buffer_flags) == 0) {
		i = slapi_valueset_first_value(values, &value);
		if (i != -1) {
			/* Get the length of the value. */
			val = slapi_value_get_berval(value);
			/* Check if we have space for the value. */
			if (ret + val->bv_len > (unsigned int) outbuf_len) {
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"first: out of space\n");
				ret = -ENOBUFS;
			} else {
				/* Copy in the value. */
				memcpy(outbuf + ret, val->bv_val, val->bv_len);
				ret += val->bv_len;
			}
		} else {
			/* No such attribute. */
			ret = -ENOENT;
		}
		/* Free the value set for this attribute. */
		slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
	}
	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)
{
	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) {
		backend_shr_add_strlist(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;
		slapi_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;
}

/* 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)
{
	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;
}

/* 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)
{
	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,
					     &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 for a non-empty value. */
			if (lengths[j] == 0) {
				continue;
			}
			/* 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,
		     const char *fnname,
		     char * (*match_fn)(const char *pattern, const char *value,
		     			char **argv))
{
	Slapi_ValueSet *values;
	Slapi_Value *value;
	char *cvalue, *actual_attr, **argv, **matches, *plugin_id, *defaults[2];
	int i, count, argc, disposition, buffer_flags;
	int ret, len;

	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;
	}
	/* Walk the list of values for the attribute. */
	matches = NULL;
	count = 0;
	values = NULL;
	/* Find all of the matching values. */
	if (slapi_vattr_values_get(e, argv[0], &values,
				   &disposition, &actual_attr,
				   0, &buffer_flags) == 0) {
		matches = malloc(sizeof(char *) *
				 (slapi_valueset_count(values) + 1));
		if (matches != NULL) {
			for (i = slapi_valueset_first_value(values, &value);
			     i != -1;
			     i = slapi_valueset_next_value(values, i, &value)) {
				cvalue = xstrndup(slapi_value_get_string(value),
						  slapi_value_get_length(value));
				matches[count] = match_fn(argv[1], cvalue,
							  argv + 2);
				free(cvalue);
				if (matches[count] != NULL) {
					count++;
				}
			}
			matches[count] = NULL;
		}
		slapi_vattr_values_free(&values, &actual_attr, buffer_flags);
	}
	/* Make sure matched is either the single match, the default, or NULL
	 * if we had no default. */
	switch (count) {
	case 0:
		/* No matches. */
		free(matches);
		if ((default_arg >= 0) && (argv[default_arg] != NULL)) {
			/* Try to store the default. */
			slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
					"%s: no matching values for "
					"\"%s\", using default value \"%s\"\n",
					fnname, argv[1], argv[default_arg]);
			if (outbuf_choices != NULL) {
				/* Return the default value as a list. */
				defaults[0] = argv[default_arg];
				defaults[1] = NULL;
				format_add_choice_str(outbuf_choices, outbuf,
						      defaults);
				len = 0;
			} else {
				/* Store the default directly in the buffer. */
				len = strlen(argv[default_arg]);
				if (len > outbuf_len) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
							plugin_id,
							"%s: out of space\n",
							fnname);
					format_free_parsed_args(argv);
					return -ENOBUFS;
				}
				memcpy(outbuf, argv[default_arg], len);
			}
		} else {
			slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
					"%s: no matching values for "
					"\"%s\", and no default value\n",
					fnname, argv[1]);
			format_free_parsed_args(argv);
			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. */
			if ((default_arg >= 0) && (argv[default_arg] != NULL)) {
				slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
						"%s: too many matching values "
						"for \"%s\", using default "
						"value \"%s\"\n",
						fnname, argv[1],
						argv[default_arg]);
				len = strlen(argv[default_arg]);
				if (len > outbuf_len) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
							plugin_id,
							"%s: out of space\n",
							fnname);
					for (i = 0; i < count; i++) {
						free(matches[i]);
					}
					free(matches);
					format_free_parsed_args(argv);
					return -ENOBUFS;
				}
				memcpy(outbuf, argv[default_arg], len);
			} else {
				slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
						"%s: too many matching values "
						"for \"%s\", and no default "
						"value\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)
{
	return format_match_generic(state, pb, e, group, set, args, 2, 2,
				    disallowed,
				    outbuf, outbuf_len, outbuf_choices,
				    ref_attrs, inref_attrs,
				    "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)
{
	return format_match_generic(state, pb, e, group, set, args, 2, 2,
				    disallowed,
				    outbuf, outbuf_len, outbuf_choices,
				    ref_attrs, inref_attrs,
				    "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)
{
	return format_match_generic(state, pb, e, group, set, args, 3, 3,
				    disallowed,
				    outbuf, outbuf_len, outbuf_choices,
				    ref_attrs, inref_attrs,
				    "format_regsub", format_regsub_cb);
}

/* 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);
	} fns[] = {
		{"first", format_first},
		{"deref", format_deref},
		{"referred", format_referred},
		{"merge", format_merge},
		{"match", format_match},
		{"regmatch", format_regmatch},
		{"regsub", format_regsub},
	};
	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 += 2;
			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)
{
	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);
				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);
				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);
			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)
{
	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);

	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);
					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);
				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,
	      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);
		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,
		unsigned int *data_length)
{
	unsigned int ignored;
	return format_format(state, e, group, set, fmt, disallowed,
			     NULL, ref_attrs, inref_attrs,
			     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,
		    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,
				 &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;
}