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

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

/* 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;
		backend_shr_free_strlist(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, char **values)
{
	struct format_choice *choice;
	int i;
	if (values != NULL) {
		choice = malloc(sizeof(*choice));
		if (choice != NULL) {
			choice->offset = offset;
			choice->values = backend_shr_dup_strlist(values);
			choice->next = NULL;
			if (choice->values != NULL) {
				for (i = 0; choice->values[i] != NULL; i++) {
					continue;
				}
				choice->n_values = i;
				format_append_choice(choices, choice);
			} else {
				free(choice);
			}
		}
	}
}

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

/* Echo the parameter text. */
static int
format_echo(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, len;
	char **argv;
	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"echo: error parsing arguments\n");
		return -EINVAL;
	}
	if (argc < 1) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"echo: requires at least one argument\n");
		format_free_parsed_args(argv);
		return -EINVAL;
	}
	for (i = 0, ret = 0; i < argc; i++) {
		/* Get the length of this argument. */
		len = strlen(argv[i]);
		/* Check that we've got space for this argument. */
		if (ret + len > outbuf_len) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"echo: out of space\n");
			return -ENOBUFS;
		}
		/* Append the text of the argument. */
		memcpy(outbuf + ret, argv[i], len);
		ret += len;
	}
	format_free_parsed_args(argv);
	return ret;
}

/* 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, len, argc;
	Slapi_ValueSet *values;
	Slapi_Value *value;
	char **argv, *actual_attr;
	const char *cvalue;
	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. */
			cvalue = slapi_value_get_string(value);
			len = strlen(cvalue);
			/* Check if we have space for the value. */
			if (ret + len > 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, cvalue, len);
				ret += 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;
}

/* Create a list of the values of the attributes which are passed as arguments,
 * joined by a separator given as the first argument. */
static int
format_list(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, len, slen, count, argc;
	Slapi_ValueSet *values;
	Slapi_Value *value;
	char **argv, *actual_attr;
	const char *cvalue;
	int disposition, buffer_flags;
	ret = format_parse_args(state, args, &argc, &argv);
	if (ret != 0) {
		slapi_log_error(SLAPI_LOG_PLUGIN, state->plugin_desc->spd_id,
				"list: error parsing arguments\n");
		return -EINVAL;
	}
	for (i = 1, ret = 0, count = 0; i < argc; i++) {
		/* Get the list of values for this attribute. */
		if (slapi_vattr_values_get(e, argv[i], &values, &disposition,
					   &actual_attr, 0,
					   &buffer_flags) != 0) {
			continue;
		}
		for (j = slapi_valueset_first_value(values, &value);
		     j != -1;
		     j = slapi_valueset_next_value(values, j, &value)) {
			/* Get the length of the value. */
			cvalue = slapi_value_get_string(value);
			len = strlen(cvalue);
			/* Check if we have space for the value. */
			if (ret + len > outbuf_len) {
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"list: out of space\n");
				slapi_vattr_values_free(&values, &actual_attr,
							buffer_flags);
				format_free_parsed_args(argv);
				return -ENOBUFS;
			}
			/* If the value is empty, skip it. */
			if (len == 0) {
				continue;
			}
			/* If we've already added values, add the separator. */
			if (count > 0) {
				/* Get the length of the separator. */
				slen = strlen(argv[0]);
				/* Check if we have space for the separator. */
				if (ret + len + slen > outbuf_len) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
						     state->plugin_desc->spd_id,
						     "list: out of space\n");
					slapi_vattr_values_free(&values,
								&actual_attr,
								buffer_flags);
					format_free_parsed_args(argv);
					return -ENOBUFS;
				}
				/* Copy in the separator. */
				memcpy(outbuf + ret, argv[0], slen);
				ret += slen;
			}
			/* Copy in the value. */
			memcpy(outbuf + ret, cvalue, len);
			ret += len;
			count++;
		}
		/* 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 entry matching a DN stored in the attribute named by the second
 * argument, pull out the values for the attribute named by the third
 * argument, and create a list separated by the first argument. */
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, len, slen, ret, count, 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 *sep, *cvalue, *cref;
	char *ref_attr, *target_attr, **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 (outbuf_choices == NULL) {
		if (argc != 3) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"deref: requires 3 arguments\n");
			format_free_parsed_args(argv);
			return -EINVAL;
		}
		sep = argv[0];
		ref_attr = argv[1];
		target_attr = argv[2];
	} else {
		if (argc != 2) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"deref: requires 2 arguments\n");
			format_free_parsed_args(argv);
			return -EINVAL;
		}
		sep = NULL;
		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 names of the reference attribute. */
	if (slapi_vattr_values_get(e, ref_attr, &ref_values,
				   &ref_disposition, &actual_ref_attr,
				   0, &ref_buffer_flags) != 0) {
		/* No references. */
		format_free_parsed_args(argv);
		if (outbuf_choices == NULL) {
			return 0;
		} else {
			return -ENOENT;
		}
	}
	/* 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. */
	ret = 0;
	count = 0;
	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 reading "
					"\"%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 length of the value. */
			cvalue = slapi_value_get_string(value);
			len = strlen(cvalue);
			/* Check if there's space for the value. */
			if (ret + len > outbuf_len) {
				slapi_log_error(SLAPI_LOG_PLUGIN,
						state->plugin_desc->spd_id,
						"deref: out of space\n");
				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 -ENOBUFS;
			}
			/* If the value is empty, skip it. */
			if (len == 0) {
				continue;
			}
			/* If we're keeping a list of choices, just add it to
			 * the list of values we've retrieved and keep going. */
			if (outbuf_choices != NULL) {
				backend_shr_add_strlist(&choices, cvalue);
				continue;
			}
			/* If we need to, add the separator. */
			if (count > 0) {
				/* Get the length of the separator. */
				slen = strlen(sep);
				/* Check if there's space for the separator. */
				if (ret + len + slen > outbuf_len) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
						     state->plugin_desc->spd_id,
						     "deref: out of space\n");
					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 -ENOBUFS;
				}
				/* Append the separator. */
				memcpy(outbuf + ret, sep, slen);
				ret += slen;
			}
			/* Append the value. */
			memcpy(outbuf + ret, cvalue, len);
			ret += len;
			count++;
		}
		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);
	if (outbuf_choices != NULL) {
		if (choices != NULL) {
			/* Return the values we found. */
			format_add_choice(outbuf_choices, outbuf, choices);
			backend_shr_free_strlist(choices);
		} else {
			/* Return a no-result error. */
			ret = -ENOENT;
		}
	}
	return ret;
}

/* Look up entries in the map named by the second argument, which have this
 * entry's DN stored in the attribute named by the third argument, pull out the
 * values for the attribute named by the fourth argument, and create a list
 * separated by the first argument. */
struct format_referred_cbdata {
	struct plugin_state *state;
	char *attr, *separator;
	char *outbuf;
	int outbuf_len;
	struct format_choice **outbuf_choices;
	char **choices;
	int count;
	int ret;
};
static int
format_referred_entry_cb(Slapi_Entry *e, void *callback_data)
{
	Slapi_ValueSet *values;
	Slapi_Value *value;
	int i, disposition, buffer_flags, len, slen;
	char *actual_attr;
	const char *cvalue;
	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. */
		cvalue = slapi_value_get_string(value);
		if (cvalue == NULL) {
			continue;
		}
		len = strlen(cvalue);
		if (len == 0) {
			continue;
		}
		slapi_log_error(SLAPI_LOG_PLUGIN,
				cbdata->state->plugin_desc->spd_id,
				"referred: got value \"%s\"\n", cvalue);
		/* If we're keeping a list of choices, just add it to the list
		 * of values we've retrieved and keep going. */
		if (cbdata->outbuf_choices != NULL) {
			backend_shr_add_strlist(&cbdata->choices, cvalue);
			continue;
		}
		/* Check if there's space for the value. */
		slen = strlen(cbdata->separator);
		if (len + (cbdata->count ? slen : 0) > cbdata->outbuf_len) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					cbdata->state->plugin_desc->spd_id,
					"referred: out of space\n");
			slapi_vattr_values_free(&values,
						&actual_attr,
						buffer_flags);
			cbdata->ret = -ENOBUFS;
			return -1;
		}
		/* Store the value. */
		if (cbdata->count > 0) {
			memcpy(cbdata->outbuf, cbdata->separator, slen);
		}
		memcpy(cbdata->outbuf + (cbdata->count ? slen : 0),
		       cvalue, len);
		cbdata->outbuf += (len + (cbdata->count ? slen : 0));
		cbdata->outbuf_len -= (len + (cbdata->count ? slen : 0));
		slapi_log_error(SLAPI_LOG_PLUGIN,
				cbdata->state->plugin_desc->spd_id,
				"referred: stored value \"%s\"\n", cvalue);
		cbdata->count++;
	}
	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, *sep, *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 (outbuf_choices == NULL) {
		if (argc != 4) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"referred: requires 4 arguments\n");
			format_free_parsed_args(argv);
			return -EINVAL;
		}
		sep = argv[0];
		other_set = argv[1];
		other_attr = argv[2];
		attr = argv[3];
	} else {
		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;
		}
		sep = NULL;
		other_set = argv[0];
		other_attr = argv[1];
		attr = argv[2];
	}

	/* Build the attribute list. */
	attrs[0] = attr;
	attrs[1] = NULL;

	/* 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.separator = sep;
	cbdata.outbuf = outbuf;
	cbdata.outbuf_len = outbuf_len;
	cbdata.outbuf_choices = outbuf_choices;
	cbdata.choices = NULL;
	cbdata.count = 0;
	cbdata.ret = 0;

	/* Retrieve the map-specific paramters. */
	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);
	}

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

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

	/* Now just search through the entries used for the map. */
	use_filter = set_filter ? set_filter : "(objectClass=*)";
	for (i = 0; (set_bases != NULL) && (set_bases[i] != NULL); i++) {
		/* Build the search filter. */
		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);
		/* Set up the search. */
		slapi_search_internal_set_pb(local_pb,
					     set_bases[i], LDAP_SCOPE_SUB,
					     filter, attrs, FALSE,
					     NULL, NULL,
					     state->plugin_identity, 0);
		/* Let the callback do the work. */
		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);
		/* If the callback left an error code for us, then stop. */
		if (cbdata.ret != 0) {
			break;
		}
	}
	free(tndn);

	if (outbuf_choices != NULL) {
		if (cbdata.choices != NULL) {
			/* Return the values we found. */
			format_add_choice(outbuf_choices, outbuf,
					  cbdata.choices);
			backend_shr_free_strlist(cbdata.choices);
		} else {
			/* Return a no-result error. */
			cbdata.ret = -ENOENT;
		}
	}

	backend_free_set_config(set_bases, set_filter);
	slapi_pblock_destroy(local_pb);
	format_free_parsed_args(argv);
	return cbdata.ret ? cbdata.ret : cbdata.outbuf - outbuf;
}

/* Evaluate each argument, 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, argc, len, slen, count;
	char **argv;
	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;
	}
	slen = strlen(argv[0]);
	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;
		len = format_expand(state, pb, e, group, set,
				    argv[i], disallowed,
				    outbuf + ret + (count ? slen : 0),
				    outbuf_len - (ret + (count ? slen : 0)),
				    &these_choices,
				    ref_attrs, inref_attrs);
		if (len < 0) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"merge: error expanding ->%s<-: %s\n",
					argv[i], strerror(-len));
			format_free_parsed_args(argv);
			return len;
		}
		/* If it didn't expand to anything, just keep going. */
		if (len == 0) {
			if (these_choices == NULL) {
				/* No choices, ignore this expression. */
				continue;
			} else {
				/* Make note of the choices, and accept a
				 * zero-length value as a placeholder. */
				format_append_choice(outbuf_choices,
						     these_choices);
			}
		}
		/* Log this value. */
		slapi_log_error(SLAPI_LOG_PLUGIN,
				state->plugin_desc->spd_id,
				"merge: expanded ->%s<- to ->%.*s<-\n",
				argv[i], len,
				outbuf + ret + (count ? slen : 0));
		/* If we filled in a result, and we had more than one in there
		 * already, fill in the separator. */
		if (count > 0) {
			memcpy(outbuf + ret, argv[0], slen);
		}
		ret += (len + (count ? slen : 0));
		count++;
	}
	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;
	const char *cvalue;
	char *actual_attr, **argv, **matches, *plugin_id;
	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 = slapi_value_get_string(value);
				matches[count] = match_fn(argv[1], cvalue,
							  argv + 2);
				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. */
		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]);
			len = strlen(argv[default_arg]);
			if (len > outbuf_len) {
				slapi_log_error(SLAPI_LOG_PLUGIN, plugin_id,
						"%s: out of space\n", fnname);
				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: no matching values for "
					"\"%s\", and no default value\n",
					fnname, argv[1]);
			free(matches);
			format_free_parsed_args(argv);
			return -ENOENT;
		}
		break;
	case 1:
		/* Single result. */
		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) {
			/* Too many matches to store. */
			if (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]);
				if (values != NULL) {
					slapi_vattr_values_free(&values,
								&actual_attr,
								buffer_flags);
				}
				for (i = 0; i < count; i++) {
					free(matches[i]);
				}
				free(matches);
				format_free_parsed_args(argv);
				return -ENOENT;
			}
		} else {
			/* Record the set of matching values as choices at this
			 * location. */
			format_add_choice(outbuf_choices, outbuf, matches);
			len = 0;
		}
		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[] = {
		{"echo", format_echo},
		{"first", format_first},
		{"list", format_list},
		{"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;
}

/* 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 char *
format_single(struct plugin_state *state, Slapi_PBlock *pb, Slapi_Entry *e,
	      const char *attr, const char *disallowed, char ***values)
{
	Slapi_ValueSet *value_set;
	Slapi_Value *value;
	char *ret, *actual_attr, **tmp_values;
	const char *cret, *d;
	int count, disposition, buffer_flags, i, j;
	if (slapi_vattr_values_get(e, (char *) attr, &value_set,
				   &disposition, &actual_attr,
				   0, &buffer_flags) != 0) {
		return NULL;
	}
	count = slapi_valueset_count(value_set);
	ret = NULL;
	if (count == 1) {
		if (slapi_valueset_first_value(value_set, &value) != -1) {
			cret = slapi_value_get_string(value);
			if (cret != NULL) {
				if ((disallowed != NULL) &&
				    ((d = strpbrk(cret, disallowed)) != NULL)) {
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"value for \"%s\" "
							"contains disallowed "
							"character \"%c\", "
							"ignoring\n",
							attr, *d);
				} else {
					ret = strdup(cret);
				}
			}
		}
	} else {
		if ((count == 0) || (values == NULL)) {
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"%d values for \"%s\"\n", count, attr);
		} else {
			/* Return the list of values. */
			tmp_values = malloc(sizeof(char *) * (count + 1));
			if (tmp_values != NULL) {
				j = 0;
				for (i = slapi_valueset_first_value(value_set,
								    &value);
				     i != -1;
				     i = slapi_valueset_next_value(value_set, i,
				     				   &value)) {
					cret = slapi_value_get_string(value);
					if ((disallowed == NULL) ||
					    (strpbrk(cret,
						     disallowed) == NULL)) {
						tmp_values[j++] = strdup(cret);
					}
				}
				tmp_values[j] = NULL;
				*values = backend_shr_dup_strlist(tmp_values);
				for (i = 0; tmp_values[i] != NULL; i++) {
					free(tmp_values[i]);
				}
				free(tmp_values);
			}
		}
	}
	slapi_vattr_values_free(&value_set, &actual_attr, buffer_flags);
	return ret;
}

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

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

/* Trim off prefixes or suffixes which match the given patterns, free the
 * original, and return the result. */
static char *
format_trim_value(struct plugin_state *state, char *input,
		  const char *shortstart, const char *longstart,
		  const char *shortend, const char *longend,
		  const char *replace, const char *replaceall,
		  const char *replaceval)
{
	char *ret;
	int i, j, k, len;
	ret = strdup(input);
	len = strlen(input);
	if (ret != NULL) {
		if (shortstart) {
			/* The shortest initial substring which matches gets
			 * skipped. */
			for (i = 0; i <= len; i++) {
				memcpy(ret, input, i);
				ret[i] = '\0';
				if (fnmatch(shortstart, ret, 0) == 0) {
					strcpy(ret, input + i);
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"trim-ss: ->%s<- => "
							"->%s<-\n",
							input, ret);
					free(input);
					return ret;
				}
			}
		}
		if (shortend) {
			/* The shortest ending substring which matches gets
			 * snipped. */
			for (i = 0; i <= len; i++) {
				strcpy(ret, input + len - i);
				if (fnmatch(shortend, ret, 0) == 0) {
					strcpy(ret, input);
					ret[len - i] = '\0';
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"trim-se: ->%s<- => "
							"->%s<-\n",
							input, ret);
					free(input);
					return ret;
				}
			}
		}
		if (longstart) {
			/* The longest initial substring which matches gets
			 * skipped. */
			for (i = 0; i <= len; i++) {
				memcpy(ret, input, (len - i));
				ret[len - i] = '\0';
				if (fnmatch(longstart, ret, 0) == 0) {
					strcpy(ret, input + (len - i));
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"trim-ls: ->%s<- => "
							"->%s<-\n",
							input, ret);
					free(input);
					return ret;
				}
			}
		}
		if (longend) {
			/* The longest ending substring which matches gets
			 * snipped. */
			for (i = 0; i <= len; i++) {
				strcpy(ret, input + i);
				if (fnmatch(longend, ret, 0) == 0) {
					strcpy(ret, input);
					ret[i] = '\0';
					slapi_log_error(SLAPI_LOG_PLUGIN,
							state->plugin_desc->spd_id,
							"trim-le: ->%s<- => "
							"->%s<-\n",
							input, ret);
					free(input);
					return ret;
				}
			}
		}
		if (replaceval == NULL) {
			replaceval = "";
		}
		if (replace) {
			/* Every occurrence of the substring which matches gets
			 * replaced, maybe. */
			free(ret);
			ret = malloc(len + strlen(replaceval) + 1);
			if (ret == NULL) {
				return input;
			}
			for (i = 0, j = 0;
			     (i < len) && (replaceval != NULL);
			     i++, j++) {
				strcpy(ret + j, input + i);
				for (k = strlen(ret + j); k > 0; k--) {
					ret[j + k] = '\0';
					if (fnmatch(replace, ret + j, 0) == 0) {
						strcpy(ret + j, replaceval);
						strcat(ret + j, input + i + k);
						replaceval = NULL;
						break;
					}
				}
			}
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"trim-r: ->%s<- => ->%s<-\n",
					input, ret);
			free(input);
			return ret;
		}
		if (replaceall) {
			/* Every occurrence of the substring which matches gets
			 * replaced with the replaceval. */
			free(ret);
			ret = malloc(len * strlen(replaceval) + 1);
			if (ret == NULL) {
				return input;
			}
			for (i = 0, j = 0;
			     (i < len) && (replaceval != NULL);
			     i++, j++) {
				strcpy(ret + j, input + i);
				for (k = strlen(ret + j); k > 0; k--) {
					ret[j + k] = '\0';
					if (fnmatch(replaceall, ret + j,
						    0) == 0) {
						strcpy(ret + j, replaceval);
						j += (strlen(replaceval) - 1);
						i += (k - 1);
						break;
					}
				}
			}
			slapi_log_error(SLAPI_LOG_PLUGIN,
					state->plugin_desc->spd_id,
					"trim-r+: ->%s<- => ->%s<-\n",
					input, ret);
			free(input);
			return ret;
		}
		free(ret);
	}
	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, **value_list;
	char *replace, *replaceall, *replaceval, *tmp, *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. */
	value_list = NULL;
	tmp = format_single(state, pb, e, attribute, disallowed, &value_list);
	if (tmp == NULL) {
		/* The attribute is undefined, or we're treating it as if it
		 * is. */
		if (value_list == 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 {
			/* 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, value_list);
			backend_shr_free_strlist(value_list);
			return 0;
		}
	} else {
		/* There's a value defined. */
		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);
			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 != NULL) {
				i = strlen(tmp);
				if (i <= outbuf_len) {
					memcpy(outbuf, tmp, i);
				}
				free(tmp);
				free(expr);
				return i;
			} 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)
{
	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 = strdup(buf);
			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)
{
	return format_format(state, e, group, set, fmt, disallowed,
			     NULL, ref_attrs, inref_attrs);
}

void
format_free_data_set(char **data)
{
	int i;
	if (data != NULL) {
		for (i = 0; data[i] != NULL; i++) {
			free(data[i]);
		}
		free(data);
	}
}
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_choice *choices, *this_choice;
	char **ret, *template, *s;
	int combinations, groupsize, i, j, k, offset, length, template_len;
	choices = NULL;
	template = format_format(state, e, group, set, fmt, disallowed,
				 &choices, ref_attrs, inref_attrs);
	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: \"%s\" %d\n",
					this_choice->values[i],
					this_choice->offset - template);
		}
		combinations *= this_choice->n_values;
	}
	if (combinations == 0) {
		format_free_choices(choices);
		return NULL;
	}
	template_len = strlen(template);
	ret = malloc((combinations + 1) * sizeof(char *));
	if (ret != 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;
				s = this_choice->values[(i / groupsize) %
						        this_choice->n_values];
				length += strlen(s);
			}
			/* 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;
				s = this_choice->values[(i / groupsize) %
						        this_choice->n_values];
				length = strlen(s);
				memcpy(ret[j] + k, s, length);
				k += length;
			}
			/* Copy any part of the template which trails the
			 * choices. */
			strcpy(ret[j] + k, template + offset);
			j++;
		}
		ret[j] = NULL;
	}
	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;
}