/* This is extracted from the OpenLDAP sources.
 *
 * Stuff that isn't used in e-book-backend-ldap.c was dropped, like
 * the LDAPSchemaExtensionItem stuff.
 *
 * This file basically has three parts:
 *
 * - some general macros from OpenLDAP that work as such on all
 *   implementations.
 *
 * - ldap_str2objectclass()
 *
 * - ldap_url_parse()
 */

/* This work is part of OpenLDAP Software <http://www.openldap.org/>.
 *
 * Copyright 1998-2005 The OpenLDAP Foundation.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted only as authorized by the OpenLDAP
 * Public License.
 *
 * A copy of this license is available in file COPYING.OPENLDAP in
 * the top-level directory of the distribution or, alternatively, at
 * <http://www.OpenLDAP.org/license.html>.
 */

#include <string.h>
#include <assert.h>

/* from various header files */

#define LDAP_CONST const

#define LDAP_PORT		389		/* ldap:///		default LDAP port */
#define LDAPS_PORT		636		/* ldaps:///	default LDAP over TLS port */

#define LDAP_ROOT_DSE				""

#define LDAP_SPACE(c)		((c) == ' ' || (c) == '\t' || (c) == '\n')
#define LDAP_DIGIT(c)		((c) >= '0' && (c) <= '9')

#define LDAP_EXOP_START_TLS		"1.3.6.1.4.1.1466.20037"	/* RFC 2830 */

#define LDAP_MALLOC(n) malloc((n))
#define LDAP_CALLOC(n,s) calloc((n),(s))
#define LDAP_REALLOC(p,s) realloc((p),(s))
#define LDAP_FREE(p) free((p))
#define LDAP_VFREE(p) vfree((gpointer *)(p))
#define LDAP_STRDUP(s) strdup((s))

#define LDAP_RANGE(n,x,y)	(((x) <= (n)) && ((n) <= (y)))
#define LDAP_NAME_ERROR(n)	LDAP_RANGE((n),0x20,0x24) /* 32-34,36 */

#define ldap_msgtype(lm) (lm)->lm_msgtype
#define ldap_msgid(lm) (lm)->lm_msgid
#ifndef LDAP_TYPE_OR_VALUE_EXISTS
#define LDAP_TYPE_OR_VALUE_EXISTS 0x14
#endif
#ifndef LDAP_SCOPE_DEFAULT
#define LDAP_SCOPE_DEFAULT -1
#endif
#ifndef LDAP_OPT_SUCCESS
#define LDAP_OPT_SUCCESS 0x00
#endif
#ifndef LDAP_INSUFFICIENT_ACCESS
#define LDAP_INSUFFICIENT_ACCESS 0x32
#endif

#define LDAP_SCHERR_OUTOFMEM		1
#define LDAP_SCHERR_UNEXPTOKEN		2
#define LDAP_SCHERR_NOLEFTPAREN		3
#define LDAP_SCHERR_NORIGHTPAREN	4
#define LDAP_SCHERR_NODIGIT		5
#define LDAP_SCHERR_BADNAME		6
#define LDAP_SCHERR_BADDESC		7
#define LDAP_SCHERR_BADSUP		8
#define LDAP_SCHERR_DUPOPT		9
#define LDAP_SCHERR_EMPTY		10
#define LDAP_SCHERR_MISSING		11
#define LDAP_SCHERR_OUT_OF_ORDER	12

#define LDAP_SCHEMA_YES				1

#define LDAP_SCHEMA_ABSTRACT			0
#define LDAP_SCHEMA_STRUCTURAL			1
#define LDAP_SCHEMA_AUXILIARY			2

#define LDAP_SCHEMA_ALLOW_NONE		0x00U /* Strict parsing               */
#define LDAP_SCHEMA_ALLOW_NO_OID	0x01U /* Allow missing oid            */
#define LDAP_SCHEMA_ALLOW_QUOTED	0x02U /* Allow bogus extra quotes     */
#define LDAP_SCHEMA_ALLOW_DESCR		0x04U /* Allow descr instead of OID   */
#define LDAP_SCHEMA_ALLOW_DESCR_PREFIX	0x08U /* Allow descr as OID prefix    */
#define LDAP_SCHEMA_ALLOW_OID_MACRO	0x10U /* Allow OID macros in slapd    */
#define LDAP_SCHEMA_ALLOW_OUT_OF_ORDER_FIELDS 0x20U /* Allow fields in most any order */
#define LDAP_SCHEMA_ALLOW_ALL		0x3fU /* Be very liberal in parsing   */
#define	LDAP_SCHEMA_SKIP			0x80U /* Don't malloc any result      */

typedef struct ldap_objectclass {
	gchar *oc_oid;		/* REQUIRED */
	gchar **oc_names;	/* OPTIONAL */
	gchar *oc_desc;		/* OPTIONAL */
	gint  oc_obsolete;	/* 0=no, 1=yes */
	gchar **oc_sup_oids;	/* OPTIONAL */
	gint  oc_kind;		/* 0=ABSTRACT, 1=STRUCTURAL, 2=AUXILIARY */
	gchar **oc_at_oids_must;	/* OPTIONAL */
	gchar **oc_at_oids_may;	/* OPTIONAL */
} LDAPObjectClass;

static void
vfree (gpointer *vec)
{
  gint i;

  for (i = 0; vec[i] != NULL; i++)
    free (vec[i]);
}

/* from schema.c */

/*
 * Now come the parsers.  There is one parser for each entity type:
 * objectclasses, attributetypes, etc.
 *
 * Each of them is written as a recursive-descent parser, except that
 * none of them is really recursive.  But the idea is kept: there
 * is one routine per non-terminal that eithers gobbles lexical tokens
 * or calls lower-level routines, etc.
 *
 * The scanner is implemented in the routine get_token.  Actually,
 * get_token is more than a scanner and will return tokens that are
 * in fact non-terminals in the grammar.  So you can see the whole
 * approach as the combination of a low-level bottom-up recognizer
 * combined with a scanner and a number of top-down parsers.  Or just
 * consider that the real grammars recognized by the parsers are not
 * those of the standards.  As a matter of fact, our parsers are more
 * liberal than the spec when there is no ambiguity.
 *
 * The difference is pretty academic (modulo bugs or incorrect
 * interpretation of the specs).
 */

#define TK_NOENDQUOTE	-2
#define TK_OUTOFMEM	-1
#define TK_EOS		0
#define TK_UNEXPCHAR	1
#define TK_BAREWORD	2
#define TK_QDSTRING	3
#define TK_LEFTPAREN	4
#define TK_RIGHTPAREN	5
#define TK_DOLLAR	6
#define TK_QDESCR	TK_QDSTRING

struct token {
	gint type;
	gchar *sval;
};

static gint
get_token (const gchar **sp,
           gchar **token_val)
{
	gint kind;
	const gchar *p;
	const gchar *q;
	gchar *res;

	*token_val = NULL;
	switch (**sp) {
	case '\0':
		kind = TK_EOS;
		(*sp)++;
		break;
	case '(':
		kind = TK_LEFTPAREN;
		(*sp)++;
		break;
	case ')':
		kind = TK_RIGHTPAREN;
		(*sp)++;
		break;
	case '$':
		kind = TK_DOLLAR;
		(*sp)++;
		break;
	case '\'':
		kind = TK_QDSTRING;
		(*sp)++;
		p = *sp;
		while (**sp != '\'' && **sp != '\0')
			(*sp)++;
		if (**sp == '\'') {
			q = *sp;
			res = LDAP_MALLOC (q-p+1);
			if (!res) {
				kind = TK_OUTOFMEM;
			} else {
				strncpy (res,p,q-p);
				res[q-p] = '\0';
				*token_val = res;
			}
			(*sp)++;
		} else {
			kind = TK_NOENDQUOTE;
		}
		break;
	default:
		kind = TK_BAREWORD;
		p = *sp;
		while (!LDAP_SPACE (**sp) &&
			**sp != '(' &&
			**sp != ')' &&
			**sp != '$' &&
			**sp != '\'' &&
			**sp != '\0')
			(*sp)++;
		q = *sp;
		res = LDAP_MALLOC (q-p+1);
		if (!res) {
			kind = TK_OUTOFMEM;
		} else {
			strncpy (res,p,q-p);
			res[q-p] = '\0';
			*token_val = res;
		}
		break;
/*		kind = TK_UNEXPCHAR; */
/*		break; */
	}

	return kind;
}

/* Gobble optional whitespace */
static void
parse_whsp (const gchar **sp)
{
	while (LDAP_SPACE (**sp))
		(*sp)++;
}

/* Parse a sequence of dot-separated decimal strings */
static gchar *
ldap_int_parse_numericoid (const gchar **sp, gint *code, const gint flags)
{
	gchar *res = NULL;
	const gchar *start = *sp;
	gint len;
	gint quoted = 0;

	/* Netscape puts the SYNTAX value in quotes (incorrectly) */
	if (flags & LDAP_SCHEMA_ALLOW_QUOTED && **sp == '\'') {
		quoted = 1;
		(*sp)++;
		start++;
	}
	/* Each iteration of this loop gets one decimal string */
	while (**sp) {
		if (!LDAP_DIGIT (**sp)) {
			/*
			 * Initial gchar is not a digit or gchar after dot is
			 * not a digit
			 */
			*code = LDAP_SCHERR_NODIGIT;
			return NULL;
		}
		(*sp)++;
		while (LDAP_DIGIT (**sp))
			(*sp)++;
		if (**sp != '.')
			break;
		/* Otherwise, gobble the dot and loop again */
		(*sp)++;
	}
	/* Now *sp points at the gchar past the numericoid. Perfect. */
	len = *sp - start;
	if (flags & LDAP_SCHEMA_ALLOW_QUOTED && quoted) {
		if (**sp == '\'') {
			(*sp)++;
		} else {
			*code = LDAP_SCHERR_UNEXPTOKEN;
			return NULL;
		}
	}
	if (flags & LDAP_SCHEMA_SKIP) {
		res = (gchar *) start;
	} else {
		res = LDAP_MALLOC (len+1);
		if (!res) {
			*code = LDAP_SCHERR_OUTOFMEM;
			return (NULL);
		}
		strncpy (res,start,len);
		res[len] = '\0';
	}
	return (res);
}

/* Parse a qdescr or a list of them enclosed in () */
static gchar **
parse_qdescrs (const gchar **sp, gint *code)
{
	gchar ** res;
	gchar ** res1;
	gint kind;
	gchar *sval;
	gint size;
	gint pos;

	parse_whsp (sp);
	kind = get_token (sp,&sval);
	if (kind == TK_LEFTPAREN) {
		/* Let's presume there will be at least 2 entries */
		size = 3;
		res = LDAP_CALLOC (3,sizeof (gchar *));
		if (!res) {
			*code = LDAP_SCHERR_OUTOFMEM;
			return NULL;
		}
		pos = 0;
		while (1) {
			parse_whsp (sp);
			kind = get_token (sp,&sval);
			if (kind == TK_RIGHTPAREN)
				break;
			if (kind == TK_QDESCR) {
				if (pos == size-2) {
					size++;
					res1 = LDAP_REALLOC (res,size*sizeof (gchar *));
					if (!res1) {
						LDAP_VFREE (res);
						LDAP_FREE (sval);
						*code = LDAP_SCHERR_OUTOFMEM;
						return (NULL);
					}
					res = res1;
				}
				res[pos++] = sval;
				res[pos] = NULL;
				parse_whsp (sp);
			} else {
				LDAP_VFREE (res);
				LDAP_FREE (sval);
				*code = LDAP_SCHERR_UNEXPTOKEN;
				return (NULL);
			}
		}
		parse_whsp (sp);
		return (res);
	} else if (kind == TK_QDESCR) {
		res = LDAP_CALLOC (2,sizeof (gchar *));
		if (!res) {
			*code = LDAP_SCHERR_OUTOFMEM;
			return NULL;
		}
		res[0] = sval;
		res[1] = NULL;
		parse_whsp (sp);
		return res;
	} else {
		LDAP_FREE (sval);
		*code = LDAP_SCHERR_BADNAME;
		return NULL;
	}
}

/* Parse a woid or a $-separated list of them enclosed in () */
static gchar **
parse_oids (const gchar **sp, gint *code, const gint allow_quoted)
{
	gchar ** res;
	gchar ** res1;
	gint kind;
	gchar *sval;
	gint size;
	gint pos;

	/*
	 * Strictly speaking, doing this here accepts whsp before the
	 * ( at the begining of an oidlist, but this is harmless.  Also,
	 * we are very liberal in what we accept as an OID.  Maybe
	 * refine later.
	 */
	parse_whsp (sp);
	kind = get_token (sp,&sval);
	if (kind == TK_LEFTPAREN) {
		/* Let's presume there will be at least 2 entries */
		size = 3;
		res = LDAP_CALLOC (3,sizeof (gchar *));
		if (!res) {
			*code = LDAP_SCHERR_OUTOFMEM;
			return NULL;
		}
		pos = 0;
		parse_whsp (sp);
		kind = get_token (sp,&sval);
		if (kind == TK_BAREWORD ||
		     (allow_quoted && kind == TK_QDSTRING)) {
			res[pos++] = sval;
			res[pos] = NULL;
		} else {
			*code = LDAP_SCHERR_UNEXPTOKEN;
			LDAP_FREE (sval);
			LDAP_VFREE (res);
			return NULL;
		}
		parse_whsp (sp);
		while (1) {
			kind = get_token (sp,&sval);
			if (kind == TK_RIGHTPAREN)
				break;
			if (kind == TK_DOLLAR) {
				parse_whsp (sp);
				kind = get_token (sp,&sval);
				if (kind == TK_BAREWORD ||
				     (allow_quoted &&
				       kind == TK_QDSTRING)) {
					if (pos == size-2) {
						size++;
						res1 = LDAP_REALLOC (res,size*sizeof (gchar *));
						if (!res1) {
							LDAP_FREE (sval);
							LDAP_VFREE (res);
							*code = LDAP_SCHERR_OUTOFMEM;
							return (NULL);
						}
						res = res1;
					}
					res[pos++] = sval;
					res[pos] = NULL;
				} else {
					*code = LDAP_SCHERR_UNEXPTOKEN;
					LDAP_FREE (sval);
					LDAP_VFREE (res);
					return NULL;
				}
				parse_whsp (sp);
			} else {
				*code = LDAP_SCHERR_UNEXPTOKEN;
				LDAP_FREE (sval);
				LDAP_VFREE (res);
				return NULL;
			}
		}
		parse_whsp (sp);
		return (res);
	} else if (kind == TK_BAREWORD ||
		    (allow_quoted && kind == TK_QDSTRING)) {
		res = LDAP_CALLOC (2,sizeof (gchar *));
		if (!res) {
			LDAP_FREE (sval);
			*code = LDAP_SCHERR_OUTOFMEM;
			return NULL;
		}
		res[0] = sval;
		res[1] = NULL;
		parse_whsp (sp);
		return res;
	} else {
		LDAP_FREE (sval);
		*code = LDAP_SCHERR_BADNAME;
		return NULL;
	}
}

static void
ldap_objectclass_free (LDAPObjectClass *oc)
{
	LDAP_FREE (oc->oc_oid);
	if (oc->oc_names) LDAP_VFREE (oc->oc_names);
	if (oc->oc_desc) LDAP_FREE (oc->oc_desc);
	if (oc->oc_sup_oids) LDAP_VFREE (oc->oc_sup_oids);
	if (oc->oc_at_oids_must) LDAP_VFREE (oc->oc_at_oids_must);
	if (oc->oc_at_oids_may) LDAP_VFREE (oc->oc_at_oids_may);
	LDAP_FREE (oc);
}

static LDAPObjectClass *
ldap_str2objectclass (LDAP_CONST gchar *s,
                      gint *code,
                      LDAP_CONST gchar **errp,
                      LDAP_CONST unsigned flags)
{
	gint kind;
	const gchar *ss = s;
	gchar *sval;
	gint seen_name = 0;
	gint seen_desc = 0;
	gint seen_obsolete = 0;
	gint seen_sup = 0;
	gint seen_kind = 0;
	gint seen_must = 0;
	gint seen_may = 0;
	LDAPObjectClass *oc;
	gchar ** ext_vals;
	const gchar *savepos;

	if (!s) {
		*code = LDAP_SCHERR_EMPTY;
		*errp = "";
		return NULL;
	}

	*errp = s;
	oc = LDAP_CALLOC (1,sizeof (LDAPObjectClass));

	if (!oc) {
		*code = LDAP_SCHERR_OUTOFMEM;
		return NULL;
	}
	oc->oc_kind = LDAP_SCHEMA_STRUCTURAL;

	kind = get_token (&ss,&sval);
	if (kind != TK_LEFTPAREN) {
		*code = LDAP_SCHERR_NOLEFTPAREN;
		LDAP_FREE (sval);
		ldap_objectclass_free (oc);
		return NULL;
	}

	/*
	 * Definitions MUST begin with an OID in the numericoid format.
	 * However, this routine is used by clients to parse the response
	 * from servers and very well known servers will provide an OID
	 * in the wrong format or even no OID at all.  We do our best to
	 * extract info from those servers.
	 */
	parse_whsp (&ss);
	savepos = ss;
	oc->oc_oid = ldap_int_parse_numericoid (&ss,code,0);
	if (!oc->oc_oid) {
		if ((flags & LDAP_SCHEMA_ALLOW_ALL) && (ss == savepos)) {
			/* Backtracking */
			ss = savepos;
			kind = get_token (&ss,&sval);
			if (kind == TK_BAREWORD) {
				if (!strcasecmp (sval, "NAME") ||
				    !strcasecmp (sval, "DESC") ||
				    !strcasecmp (sval, "OBSOLETE") ||
				    !strcasecmp (sval, "SUP") ||
				    !strcasecmp (sval, "ABSTRACT") ||
				    !strcasecmp (sval, "STRUCTURAL") ||
				    !strcasecmp (sval, "AUXILIARY") ||
				    !strcasecmp (sval, "MUST") ||
				    !strcasecmp (sval, "MAY") ||
				    !strncasecmp (sval, "X-", 2)) {
					/* Missing OID, backtrack */
					ss = savepos;
				} else if (flags &
					LDAP_SCHEMA_ALLOW_OID_MACRO) {
					/* Non-numerical OID, ignore */
					gint len = ss-savepos;
					oc->oc_oid = LDAP_MALLOC (len+1);
					strncpy (oc->oc_oid, savepos, len);
					oc->oc_oid[len] = 0;
				}
			}
			LDAP_FREE (sval);
		} else {
			*errp = ss;
			ldap_objectclass_free (oc);
			return NULL;
		}
	}
	parse_whsp (&ss);

	/*
	 * Beyond this point we will be liberal an accept the items
	 * in any order.
	 */
	while (1) {
		kind = get_token (&ss,&sval);
		switch (kind) {
		case TK_EOS:
			*code = LDAP_SCHERR_NORIGHTPAREN;
			*errp = ss;
			ldap_objectclass_free (oc);
			return NULL;
		case TK_RIGHTPAREN:
			return oc;
		case TK_BAREWORD:
			if (!strcasecmp (sval,"NAME")) {
				LDAP_FREE (sval);
				if (seen_name) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_name = 1;
				oc->oc_names = parse_qdescrs (&ss,code);
				if (!oc->oc_names) {
					if (*code != LDAP_SCHERR_OUTOFMEM)
						*code = LDAP_SCHERR_BADNAME;
					*errp = ss;
					ldap_objectclass_free (oc);
					return NULL;
				}
			} else if (!strcasecmp (sval,"DESC")) {
				LDAP_FREE (sval);
				if (seen_desc) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_desc = 1;
				parse_whsp (&ss);
				kind = get_token (&ss,&sval);
				if (kind != TK_QDSTRING) {
					*code = LDAP_SCHERR_UNEXPTOKEN;
					*errp = ss;
					LDAP_FREE (sval);
					ldap_objectclass_free (oc);
					return NULL;
				}
				oc->oc_desc = sval;
				parse_whsp (&ss);
			} else if (!strcasecmp (sval,"OBSOLETE")) {
				LDAP_FREE (sval);
				if (seen_obsolete) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_obsolete = 1;
				oc->oc_obsolete = LDAP_SCHEMA_YES;
				parse_whsp (&ss);
			} else if (!strcasecmp (sval,"SUP")) {
				LDAP_FREE (sval);
				if (seen_sup) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_sup = 1;
				oc->oc_sup_oids = parse_oids (&ss,
							     code,
							     flags);
				if (!oc->oc_sup_oids) {
					*errp = ss;
					ldap_objectclass_free (oc);
					return NULL;
				}
			} else if (!strcasecmp (sval,"ABSTRACT")) {
				LDAP_FREE (sval);
				if (seen_kind) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_kind = 1;
				oc->oc_kind = LDAP_SCHEMA_ABSTRACT;
				parse_whsp (&ss);
			} else if (!strcasecmp (sval,"STRUCTURAL")) {
				LDAP_FREE (sval);
				if (seen_kind) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_kind = 1;
				oc->oc_kind = LDAP_SCHEMA_STRUCTURAL;
				parse_whsp (&ss);
			} else if (!strcasecmp (sval,"AUXILIARY")) {
				LDAP_FREE (sval);
				if (seen_kind) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_kind = 1;
				oc->oc_kind = LDAP_SCHEMA_AUXILIARY;
				parse_whsp (&ss);
			} else if (!strcasecmp (sval,"MUST")) {
				LDAP_FREE (sval);
				if (seen_must) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_must = 1;
				oc->oc_at_oids_must = parse_oids (&ss,code,0);
				if (!oc->oc_at_oids_must) {
					*errp = ss;
					ldap_objectclass_free (oc);
					return NULL;
				}
				parse_whsp (&ss);
			} else if (!strcasecmp (sval,"MAY")) {
				LDAP_FREE (sval);
				if (seen_may) {
					*code = LDAP_SCHERR_DUPOPT;
					*errp = ss;
					ldap_objectclass_free (oc);
					return (NULL);
				}
				seen_may = 1;
				oc->oc_at_oids_may = parse_oids (&ss,code,0);
				if (!oc->oc_at_oids_may) {
					*errp = ss;
					ldap_objectclass_free (oc);
					return NULL;
				}
				parse_whsp (&ss);
			} else if (sval[0] == 'X' && sval[1] == '-') {
				/* Should be parse_qdstrings */
				ext_vals = parse_qdescrs (&ss, code);
				if (!ext_vals) {
					*errp = ss;
					ldap_objectclass_free (oc);
					return NULL;
				}
#if 0
				if (add_extension (&oc->oc_extensions,
						    sval, ext_vals)) {
					*code = LDAP_SCHERR_OUTOFMEM;
					*errp = ss;
					LDAP_FREE (sval);
					ldap_objectclass_free (oc);
					return NULL;
				}
#endif
			} else {
				*code = LDAP_SCHERR_UNEXPTOKEN;
				*errp = ss;
				LDAP_FREE (sval);
				ldap_objectclass_free (oc);
				return NULL;
			}
			break;
		default:
			*code = LDAP_SCHERR_UNEXPTOKEN;
			*errp = ss;
			LDAP_FREE (sval);
			ldap_objectclass_free (oc);
			return NULL;
		}
	}
}

/* from utf-8.c */

#define LDAP_UTF8_NEXT(p) g_utf8_next_char((p))
#define LDAP_UTF8_INCR(p) ((p)=LDAP_UTF8_NEXT((p)))
#define ldap_x_utf8_to_ucs4(str) g_utf8_get_char(str)

static gchar *
ldap_utf8_strchr (const gchar *str,
                  const gchar *chr)
{
	for (; *str != '\0'; LDAP_UTF8_INCR (str)) {
		if (ldap_x_utf8_to_ucs4 (str) == ldap_x_utf8_to_ucs4 (chr)) {
			return (gchar *) str;
		}
	}

	return NULL;
}

static gsize
ldap_utf8_strcspn (const gchar *str,
                   const gchar *set)
{
	const gchar *cstr;
	const gchar *cset;

	for (cstr = str; *cstr != '\0'; LDAP_UTF8_INCR (cstr)) {
		for (cset = set; *cset != '\0'; LDAP_UTF8_INCR (cset)) {
			if (ldap_x_utf8_to_ucs4 (cstr) == ldap_x_utf8_to_ucs4 (cset)) {
				return cstr - str;
			}
		}
	}

	return cstr - str;
}

static gsize
ldap_utf8_strspn (const gchar *str,
                  const gchar *set)
{
	const gchar *cstr;
	const gchar *cset;

	for (cstr = str; *cstr != '\0'; LDAP_UTF8_INCR (cstr)) {
		for (cset = set; ; LDAP_UTF8_INCR (cset)) {
			if (*cset == '\0') {
				return cstr - str;
			}

			if (ldap_x_utf8_to_ucs4 (cstr) == ldap_x_utf8_to_ucs4 (cset)) {
				break;
			}
		}
	}

	return cstr - str;
}

static gchar *ldap_utf8_strtok (gchar *str, const gchar *sep, gchar **last)
{
	gchar *begin;
	gchar *end;

	if (last == NULL) return NULL;

	begin = str ? str : *last;

	begin += ldap_utf8_strspn (begin, sep);

	if (*begin == '\0') {
		*last = NULL;
		return NULL;
	}

	end = &begin[ ldap_utf8_strcspn (begin, sep) ];

	if (*end != '\0') {
		gchar *next = LDAP_UTF8_NEXT (end);
		*end = '\0';
		end = next;
	}

	*last = end;
	return begin;
}

/* from ldap.h */

#define LDAP_URL_SUCCESS		0x00	/* Success */
#define LDAP_URL_ERR_MEM		0x01	/* can't allocate memory space */
#define LDAP_URL_ERR_PARAM		0x02	/* parameter is bad */

#define LDAP_URL_ERR_BADSCHEME	0x03	/* URL doesn't begin with "ldap[si]://" */
#define LDAP_URL_ERR_BADENCLOSURE 0x04	/* URL is missing trailing ">" */
#define LDAP_URL_ERR_BADURL		0x05	/* URL is bad */
#define LDAP_URL_ERR_BADHOST	0x06	/* host port is bad */
#define LDAP_URL_ERR_BADATTRS	0x07	/* bad (or missing) attributes */
#define LDAP_URL_ERR_BADSCOPE	0x08	/* scope string is invalid (or missing) */
#define LDAP_URL_ERR_BADFILTER	0x09	/* bad or missing filter */
#define LDAP_URL_ERR_BADEXTS	0x0a	/* bad or missing extensions */

#define LDAP_URL_PREFIX         "ldap://"
#define LDAP_URL_PREFIX_LEN     (sizeof(LDAP_URL_PREFIX)-1)
#define LDAPS_URL_PREFIX		"ldaps://"
#define LDAPS_URL_PREFIX_LEN	(sizeof(LDAPS_URL_PREFIX)-1)
#define LDAPI_URL_PREFIX	"ldapi://"
#define LDAPI_URL_PREFIX_LEN	(sizeof(LDAPI_URL_PREFIX)-1)

#define LDAP_URL_URLCOLON		"URL:"
#define LDAP_URL_URLCOLON_LEN	(sizeof(LDAP_URL_URLCOLON)-1)

typedef struct ldap_url_desc {
	struct ldap_url_desc *lud_next;
	gchar	*lud_scheme;
	gchar	*lud_host;
	gint		lud_port;
	gchar	*lud_dn;
	gchar	**lud_attrs;
	gint		lud_scope;
	gchar	*lud_filter;
	gchar	**lud_exts;
	gint		lud_crit_exts;
} LDAPURLDesc;

/* from url.c */

static const gchar *
skip_url_prefix (
	const gchar *url,
	gint *enclosedp,
	const gchar **scheme)
{
	/*
	 * return non-zero if this looks like a LDAP URL; zero if not
	 * if non-zero returned, *urlp will be moved past "ldap://" part of URL
	 */
	const gchar *p;

	if (url == NULL) {
		return (NULL);
	}

	p = url;

	/* skip leading '<' (if any) */
	if (*p == '<') {
		*enclosedp = 1;
		++p;
	} else {
		*enclosedp = 0;
	}

	/* skip leading "URL:" (if any) */
	if (strncasecmp (p, LDAP_URL_URLCOLON, LDAP_URL_URLCOLON_LEN) == 0) {
		p += LDAP_URL_URLCOLON_LEN;
	}

	/* check for "ldap://" prefix */
	if (strncasecmp (p, LDAP_URL_PREFIX, LDAP_URL_PREFIX_LEN) == 0) {
		/* skip over "ldap://" prefix and return success */
		p += LDAP_URL_PREFIX_LEN;
		*scheme = "ldap";
		return (p);
	}

	/* check for "ldaps://" prefix */
	if (strncasecmp (p, LDAPS_URL_PREFIX, LDAPS_URL_PREFIX_LEN) == 0) {
		/* skip over "ldaps://" prefix and return success */
		p += LDAPS_URL_PREFIX_LEN;
		*scheme = "ldaps";
		return (p);
	}

	/* check for "ldapi://" prefix */
	if (strncasecmp (p, LDAPI_URL_PREFIX, LDAPI_URL_PREFIX_LEN) == 0) {
		/* skip over "ldapi://" prefix and return success */
		p += LDAPI_URL_PREFIX_LEN;
		*scheme = "ldapi";
		return (p);
	}

#ifdef LDAP_CONNECTIONLESS
	/* check for "cldap://" prefix */
	if (strncasecmp (p, LDAPC_URL_PREFIX, LDAPC_URL_PREFIX_LEN) == 0) {
		/* skip over "cldap://" prefix and return success */
		p += LDAPC_URL_PREFIX_LEN;
		*scheme = "cldap";
		return (p);
	}
#endif

	return (NULL);
}

static gint
str2scope (const gchar *p)
{
	if (strcasecmp (p, "one") == 0) {
		return LDAP_SCOPE_ONELEVEL;

	} else if (strcasecmp (p, "onelevel") == 0) {
		return LDAP_SCOPE_ONELEVEL;

	} else if (strcasecmp (p, "base") == 0) {
		return LDAP_SCOPE_BASE;

	} else if (strcasecmp (p, "sub") == 0) {
		return LDAP_SCOPE_SUBTREE;

	} else if (strcasecmp (p, "subtree") == 0) {
		return LDAP_SCOPE_SUBTREE;
	}

	return (-1);
}

static void
ldap_free_urldesc (LDAPURLDesc *ludp)
{
	if (ludp == NULL) {
		return;
	}

	if (ludp->lud_scheme != NULL) {
		LDAP_FREE (ludp->lud_scheme);
	}

	if (ludp->lud_host != NULL) {
		LDAP_FREE (ludp->lud_host);
	}

	if (ludp->lud_dn != NULL) {
		LDAP_FREE (ludp->lud_dn);
	}

	if (ludp->lud_filter != NULL) {
		LDAP_FREE (ludp->lud_filter);
	}

	if (ludp->lud_attrs != NULL) {
		LDAP_VFREE (ludp->lud_attrs);
	}

	if (ludp->lud_exts != NULL) {
		LDAP_VFREE (ludp->lud_exts);
	}

	LDAP_FREE (ludp);
}

static gint
ldap_int_unhex (gint c)
{
	return (c >= '0' && c <= '9' ? c - '0'
	    : c >= 'A' && c <= 'F' ? c - 'A' + 10
	    : c - 'a' + 10);
}

static void
ldap_pvt_hex_unescape (gchar *s)
{
	/*
	 * Remove URL hex escapes from s... done in place.  The basic concept for
	 * this routine is borrowed from the WWW library HTUnEscape() routine.
	 */
	gchar	*p;

	for (p = s; *s != '\0'; ++s) {
		if (*s == '%') {
			if (*++s == '\0') {
				break;
			}
			*p = ldap_int_unhex(*s) << 4;
			if (*++s == '\0') {
				break;
			}
			*p++ += ldap_int_unhex(*s);
		} else {
			*p++ = *s;
		}
	}

	*p = '\0';
}

static gchar **
ldap_str2charray (const gchar *str_in,
                  const gchar *brkstr)
{
	gchar	**res;
	gchar	*str, *s;
	gchar	*lasts;
	gint	i;

	/* protect the input string from strtok */
	str = LDAP_STRDUP (str_in);
	if (str == NULL) {
		return NULL;
	}

	i = 1;
	for (s = str; *s; s++) {
		if (ldap_utf8_strchr (brkstr, s) != NULL) {
			i++;
		}
	}

	res = (gchar **) LDAP_MALLOC ((i + 1) * sizeof (gchar *));

	if (res == NULL) {
		LDAP_FREE (str);
		return NULL;
	}

	i = 0;

	for (s = ldap_utf8_strtok (str, brkstr, &lasts);
		s != NULL;
		s = ldap_utf8_strtok (NULL, brkstr, &lasts))
	{
		res[i] = LDAP_STRDUP (s);

		if (res[i] == NULL) {
			for (--i; i >= 0; i--) {
				LDAP_FREE (res[i]);
			}
			LDAP_FREE (res);
			LDAP_FREE (str);
			return NULL;
		}

		i++;
	}

	res[i] = NULL;

	LDAP_FREE (str);
	return (res);
}

static gint
ldap_url_parse_ext (LDAP_CONST gchar *url_in,
                    LDAPURLDesc **ludpp)
{
/*
 *  Pick apart the pieces of an LDAP URL.
 */

	LDAPURLDesc	*ludp;
	gchar	*p, *q, *r;
	gint		i, enclosed;
	const gchar *scheme = NULL;
	const gchar *url_tmp;
	gchar *url;

	if (url_in == NULL || ludpp == NULL) {
		return LDAP_URL_ERR_PARAM;
	}

	*ludpp = NULL;	/* pessimistic */

	url_tmp = skip_url_prefix (url_in, &enclosed, &scheme);

	if (url_tmp == NULL) {
		return LDAP_URL_ERR_BADSCHEME;
	}

	assert (scheme);

	/* make working copy of the remainder of the URL */
	url = LDAP_STRDUP (url_tmp);
	if (url == NULL) {
		return LDAP_URL_ERR_MEM;
	}

	if (enclosed) {
		p = &url[strlen (url)-1];

		if (*p != '>') {
			LDAP_FREE (url);
			return LDAP_URL_ERR_BADENCLOSURE;
		}

		*p = '\0';
	}

	/* allocate return struct */
	ludp = (LDAPURLDesc *) LDAP_CALLOC (1, sizeof (LDAPURLDesc));

	if (ludp == NULL) {
		LDAP_FREE (url);
		return LDAP_URL_ERR_MEM;
	}

	ludp->lud_next = NULL;
	ludp->lud_host = NULL;
	ludp->lud_port = 0;
	ludp->lud_dn = NULL;
	ludp->lud_attrs = NULL;
	ludp->lud_filter = NULL;
	ludp->lud_scope = LDAP_SCOPE_DEFAULT;
	ludp->lud_filter = NULL;
	ludp->lud_exts = NULL;

	ludp->lud_scheme = LDAP_STRDUP (scheme);

	if (ludp->lud_scheme == NULL) {
		LDAP_FREE (url);
		ldap_free_urldesc (ludp);
		return LDAP_URL_ERR_MEM;
	}

	/* scan forward for '/' that marks end of hostport and begin. of dn */
	p = strchr (url, '/');

	if (p != NULL) {
		/* terminate hostport; point to start of dn */
		*p++ = '\0';
	}

	/* IPv6 syntax with [ip address]:port */
	if (*url == '[') {
		r = strchr (url, ']');
		if (r == NULL) {
			LDAP_FREE (url);
			ldap_free_urldesc (ludp);
			return LDAP_URL_ERR_BADURL;
		}
		*r++ = '\0';
		q = strchr (r, ':');
	} else {
		q = strchr (url, ':');
	}

	if (q != NULL) {
		gchar	*next;

		*q++ = '\0';
		ldap_pvt_hex_unescape (q);

		if (*q == '\0') {
			LDAP_FREE (url);
			ldap_free_urldesc (ludp);
			return LDAP_URL_ERR_BADURL;
		}

		ludp->lud_port = strtol (q, &next, 10);
		if (next == NULL || next[0] != '\0') {
			LDAP_FREE (url);
			ldap_free_urldesc (ludp);
			return LDAP_URL_ERR_BADURL;
		}
	}

	ldap_pvt_hex_unescape (url);

	/* If [ip address]:port syntax, url is [ip and we skip the [ */
	ludp->lud_host = LDAP_STRDUP (url + (*url == '['));

	if (ludp->lud_host == NULL) {
		LDAP_FREE (url);
		ldap_free_urldesc (ludp);
		return LDAP_URL_ERR_MEM;
	}

	/*
	 * Kludge.  ldap://111.222.333.444:389??cn=abc,o=company
	 *
	 * On early Novell releases, search references/referrals were returned
	 * in this format, i.e., the dn was kind of in the scope position,
	 * but the required slash is missing. The whole thing is illegal syntax,
	 * but we need to account for it. Fortunately it can't be confused with
	 * anything real.
	 */
	if ((p == NULL) && (q != NULL) && ((q = strchr (q, '?')) != NULL)) {
		q++;
		/* ? immediately followed by question */
		if (*q == '?') {
			q++;
			if (*q != '\0') {
				/* parse dn part */
				ldap_pvt_hex_unescape (q);
				ludp->lud_dn = LDAP_STRDUP (q);
			} else {
				ludp->lud_dn = LDAP_STRDUP ("");
			}

			if (ludp->lud_dn == NULL) {
				LDAP_FREE (url);
				ldap_free_urldesc (ludp);
				return LDAP_URL_ERR_MEM;
			}
		}
	}

	if (p == NULL) {
		LDAP_FREE (url);
		*ludpp = ludp;
		return LDAP_URL_SUCCESS;
	}

	/* scan forward for '?' that may marks end of dn */
	q = strchr (p, '?');

	if (q != NULL) {
		/* terminate dn part */
		*q++ = '\0';
	}

	if (*p != '\0') {
		/* parse dn part */
		ldap_pvt_hex_unescape (p);
		ludp->lud_dn = LDAP_STRDUP (p);
	} else {
		ludp->lud_dn = LDAP_STRDUP ("");
	}

	if (ludp->lud_dn == NULL) {
		LDAP_FREE (url);
		ldap_free_urldesc (ludp);
		return LDAP_URL_ERR_MEM;
	}

	if (q == NULL) {
		/* no more */
		LDAP_FREE (url);
		*ludpp = ludp;
		return LDAP_URL_SUCCESS;
	}

	/* scan forward for '?' that may marks end of attributes */
	p = q;
	q = strchr (p, '?');

	if (q != NULL) {
		/* terminate attributes part */
		*q++ = '\0';
	}

	if (*p != '\0') {
		/* parse attributes */
		ldap_pvt_hex_unescape (p);
		ludp->lud_attrs = ldap_str2charray (p, ",");

		if (ludp->lud_attrs == NULL) {
			LDAP_FREE (url);
			ldap_free_urldesc (ludp);
			return LDAP_URL_ERR_BADATTRS;
		}
	}

	if (q == NULL) {
		/* no more */
		LDAP_FREE (url);
		*ludpp = ludp;
		return LDAP_URL_SUCCESS;
	}

	/* scan forward for '?' that may marks end of scope */
	p = q;
	q = strchr (p, '?');

	if (q != NULL) {
		/* terminate the scope part */
		*q++ = '\0';
	}

	if (*p != '\0') {
		/* parse the scope */
		ldap_pvt_hex_unescape (p);
		ludp->lud_scope = str2scope (p);

		if (ludp->lud_scope == -1) {
			LDAP_FREE (url);
			ldap_free_urldesc (ludp);
			return LDAP_URL_ERR_BADSCOPE;
		}
	}

	if (q == NULL) {
		/* no more */
		LDAP_FREE (url);
		*ludpp = ludp;
		return LDAP_URL_SUCCESS;
	}

	/* scan forward for '?' that may marks end of filter */
	p = q;
	q = strchr (p, '?');

	if (q != NULL) {
		/* terminate the filter part */
		*q++ = '\0';
	}

	if (*p != '\0') {
		/* parse the filter */
		ldap_pvt_hex_unescape (p);

		if (!*p) {
			/* missing filter */
			LDAP_FREE (url);
			ldap_free_urldesc (ludp);
			return LDAP_URL_ERR_BADFILTER;
		}

		LDAP_FREE (ludp->lud_filter);
		ludp->lud_filter = LDAP_STRDUP (p);

		if (ludp->lud_filter == NULL) {
			LDAP_FREE (url);
			ldap_free_urldesc (ludp);
			return LDAP_URL_ERR_MEM;
		}
	}

	if (q == NULL) {
		/* no more */
		LDAP_FREE (url);
		*ludpp = ludp;
		return LDAP_URL_SUCCESS;
	}

	/* scan forward for '?' that may marks end of extensions */
	p = q;
	q = strchr (p, '?');

	if (q != NULL) {
		/* extra '?' */
		LDAP_FREE (url);
		ldap_free_urldesc (ludp);
		return LDAP_URL_ERR_BADURL;
	}

	/* parse the extensions */
	ludp->lud_exts = ldap_str2charray (p, ",");

	if (ludp->lud_exts == NULL) {
		LDAP_FREE (url);
		ldap_free_urldesc (ludp);
		return LDAP_URL_ERR_BADEXTS;
	}

	for (i=0; ludp->lud_exts[i] != NULL; i++) {
		ldap_pvt_hex_unescape (ludp->lud_exts[i]);

		if (*ludp->lud_exts[i] == '!') {
			/* count the number of critical extensions */
			ludp->lud_crit_exts++;
		}
	}

	if (i == 0) {
		/* must have 1 or more */
		LDAP_FREE (url);
		ldap_free_urldesc (ludp);
		return LDAP_URL_ERR_BADEXTS;
	}

	/* no more */
	*ludpp = ludp;
	LDAP_FREE (url);
	return LDAP_URL_SUCCESS;
}

static gint
ldap_url_parse (LDAP_CONST gchar *url_in,
                LDAPURLDesc **ludpp)
{
	gint rc = ldap_url_parse_ext (url_in, ludpp);

	if (rc != LDAP_URL_SUCCESS) {
		return rc;
	}

	if ((*ludpp)->lud_scope == LDAP_SCOPE_DEFAULT) {
		(*ludpp)->lud_scope = LDAP_SCOPE_BASE;
	}

	if ((*ludpp)->lud_host != NULL && *(*ludpp)->lud_host == '\0') {
		LDAP_FREE ((*ludpp)->lud_host);
		(*ludpp)->lud_host = NULL;
	}

	if ((*ludpp)->lud_port == 0) {
		if (strcmp ((*ludpp)->lud_scheme, "ldap") == 0) {
			(*ludpp)->lud_port = LDAP_PORT;
#ifdef LDAP_CONNECTIONLESS
		} else if (strcmp ((*ludpp)->lud_scheme, "cldap") == 0) {
			(*ludpp)->lud_port = LDAP_PORT;
#endif
		} else if (strcmp ((*ludpp)->lud_scheme, "ldaps") == 0) {
			(*ludpp)->lud_port = LDAPS_PORT;
		}
	}

	return rc;
}