s4:ldb_dn: reset dn->ext_comp_num in ldb_dn_explode()
[samba.git] / source4 / lib / ldb / common / ldb_dn.c
1 /*
2    ldb database library
3
4    Copyright (C) Simo Sorce 2005
5
6      ** NOTE! The following LGPL license applies to the ldb
7      ** library. This does NOT imply that all of Samba is released
8      ** under the LGPL
9
10    This library is free software; you can redistribute it and/or
11    modify it under the terms of the GNU Lesser General Public
12    License as published by the Free Software Foundation; either
13    version 3 of the License, or (at your option) any later version.
14
15    This library is distributed in the hope that it will be useful,
16    but WITHOUT ANY WARRANTY; without even the implied warranty of
17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18    Lesser General Public License for more details.
19
20    You should have received a copy of the GNU Lesser General Public
21    License along with this library; if not, see <http://www.gnu.org/licenses/>.
22 */
23
24 /*
25  *  Name: ldb
26  *
27  *  Component: ldb dn creation and manipulation utility functions
28  *
29  *  Description: - explode a dn into it's own basic elements
30  *                 and put them in a structure (only if necessary)
31  *               - manipulate ldb_dn structures
32  *
33  *  Author: Simo Sorce
34  */
35
36 #include "ldb_private.h"
37 #include <ctype.h>
38
39 #define LDB_DN_NULL_FAILED(x) if (!(x)) goto failed
40
41 #define LDB_FREE(x) do { talloc_free(x); x = NULL; } while(0)
42
43 /**
44    internal ldb exploded dn structures
45 */
46 struct ldb_dn_component {
47
48         char *name;
49         struct ldb_val value;
50
51         char *cf_name;
52         struct ldb_val cf_value;
53 };
54
55 struct ldb_dn_ext_component {
56
57         char *name;
58         struct ldb_val value;
59 };
60
61 struct ldb_dn {
62
63         struct ldb_context *ldb;
64
65         /* Special DNs are always linearized */
66         bool special;
67         bool invalid;
68
69         bool valid_case;
70
71         char *linearized;
72         char *ext_linearized;
73         char *casefold;
74
75         unsigned int comp_num;
76         struct ldb_dn_component *components;
77
78         unsigned int ext_comp_num;
79         struct ldb_dn_ext_component *ext_components;
80 };
81
82 /* it is helpful to be able to break on this in gdb */
83 static void ldb_dn_mark_invalid(struct ldb_dn *dn)
84 {
85         dn->invalid = true;
86 }
87
88 /* strdn may be NULL */
89 struct ldb_dn *ldb_dn_from_ldb_val(void *mem_ctx,
90                                    struct ldb_context *ldb,
91                                    const struct ldb_val *strdn)
92 {
93         struct ldb_dn *dn;
94
95         if (! ldb) return NULL;
96
97         if (strdn && strdn->data
98             && (strnlen((const char*)strdn->data, strdn->length) != strdn->length)) {
99                 /* The RDN must not contain a character with value 0x0 */
100                 return NULL;
101         }
102
103         dn = talloc_zero(mem_ctx, struct ldb_dn);
104         LDB_DN_NULL_FAILED(dn);
105
106         dn->ldb = talloc_get_type(ldb, struct ldb_context);
107         if (dn->ldb == NULL) {
108                 /* the caller probably got the arguments to
109                    ldb_dn_new() mixed up */
110                 talloc_free(dn);
111                 return NULL;
112         }
113
114         if (strdn->data && strdn->length) {
115                 const char *data = (const char *)strdn->data;
116                 size_t length = strdn->length;
117
118                 if (data[0] == '@') {
119                         dn->special = true;
120                 }
121                 dn->ext_linearized = talloc_strndup(dn, data, length);
122                 LDB_DN_NULL_FAILED(dn->ext_linearized);
123
124                 if (data[0] == '<') {
125                         const char *p_save, *p = dn->ext_linearized;
126                         do {
127                                 p_save = p;
128                                 p = strstr(p, ">;");
129                                 if (p) {
130                                         p = p + 2;
131                                 }
132                         } while (p);
133
134                         if (p_save == dn->ext_linearized) {
135                                 dn->linearized = talloc_strdup(dn, "");
136                         } else {
137                                 dn->linearized = talloc_strdup(dn, p_save);
138                         }
139                         LDB_DN_NULL_FAILED(dn->linearized);
140                 } else {
141                         dn->linearized = dn->ext_linearized;
142                         dn->ext_linearized = NULL;
143                 }
144         } else {
145                 dn->linearized = talloc_strdup(dn, "");
146                 LDB_DN_NULL_FAILED(dn->linearized);
147         }
148
149         return dn;
150
151 failed:
152         talloc_free(dn);
153         return NULL;
154 }
155
156 /* strdn may be NULL */
157 struct ldb_dn *ldb_dn_new(void *mem_ctx,
158                           struct ldb_context *ldb,
159                           const char *strdn)
160 {
161         struct ldb_val blob;
162         blob.data = discard_const_p(uint8_t, strdn);
163         blob.length = strdn ? strlen(strdn) : 0;
164         return ldb_dn_from_ldb_val(mem_ctx, ldb, &blob);
165 }
166
167 struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx,
168                               struct ldb_context *ldb,
169                               const char *new_fmt, ...)
170 {
171         char *strdn;
172         va_list ap;
173
174         if ( (! mem_ctx) || (! ldb)) return NULL;
175
176         va_start(ap, new_fmt);
177         strdn = talloc_vasprintf(mem_ctx, new_fmt, ap);
178         va_end(ap);
179
180         if (strdn) {
181                 struct ldb_dn *dn = ldb_dn_new(mem_ctx, ldb, strdn);
182                 talloc_free(strdn);
183                 return dn;
184         }
185
186         return NULL;
187 }
188
189 /* see RFC2253 section 2.4 */
190 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
191 {
192         const char *p, *s;
193         char *d;
194         int l;
195
196         p = s = src;
197         d = dst;
198
199         while (p - src < len) {
200                 p += strcspn(p, ",=\n\r+<>#;\\\" ");
201
202                 if (p - src == len) /* found no escapable chars */
203                         break;
204
205                 /* copy the part of the string before the stop */
206                 memcpy(d, s, p - s);
207                 d += (p - s); /* move to current position */
208                 
209                 switch (*p) {
210                 case ' ':
211                         if (p == src || (p-src)==(len-1)) {
212                                 /* if at the beginning or end
213                                  * of the string then escape */
214                                 *d++ = '\\';
215                                 *d++ = *p++;                                     
216                         } else {
217                                 /* otherwise don't escape */
218                                 *d++ = *p++;
219                         }
220                         break;
221
222                 case '#':
223                         /* despite the RFC, windows escapes a #
224                            anywhere in the string */
225                 case ',':
226                 case '+':
227                 case '"':
228                 case '\\':
229                 case '<':
230                 case '>':
231                 case '?':
232                         /* these must be escaped using \c form */
233                         *d++ = '\\';
234                         *d++ = *p++;
235                         break;
236
237                 default: {
238                         /* any others get \XX form */
239                         unsigned char v;
240                         const char *hexbytes = "0123456789ABCDEF";
241                         v = *(const unsigned char *)p;
242                         *d++ = '\\';
243                         *d++ = hexbytes[v>>4];
244                         *d++ = hexbytes[v&0xF];
245                         p++;
246                         break;
247                 }
248                 }
249                 s = p; /* move forward */
250         }
251
252         /* copy the last part (with zero) and return */
253         l = len - (s - src);
254         memcpy(d, s, l + 1);
255
256         /* return the length of the resulting string */
257         return (l + (d - dst));
258 }
259
260 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
261 {
262         char *dst;
263
264         if (!value.length)
265                 return NULL;
266
267         /* allocate destination string, it will be at most 3 times the source */
268         dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
269         if ( ! dst) {
270                 talloc_free(dst);
271                 return NULL;
272         }
273
274         ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
275
276         dst = talloc_realloc(mem_ctx, dst, char, strlen(dst) + 1);
277
278         return dst;
279 }
280
281 /*
282   explode a DN string into a ldb_dn structure
283   based on RFC4514 except that we don't support multiple valued RDNs
284
285   TODO: according to MS-ADTS:3.1.1.5.2 Naming Constraints
286   DN must be compliant with RFC2253
287 */
288 static bool ldb_dn_explode(struct ldb_dn *dn)
289 {
290         char *p, *ex_name, *ex_value, *data, *d, *dt, *t;
291         bool trim = false;
292         bool in_extended = false;
293         bool in_ex_name = false;
294         bool in_ex_value = false;
295         bool in_attr = false;
296         bool in_value = false;
297         bool in_quote = false;
298         bool is_oid = false;
299         bool escape = false;
300         unsigned x;
301         int l, ret;
302         char *parse_dn;
303         bool is_index;
304
305         if ( ! dn || dn->invalid) return false;
306
307         if (dn->components) {
308                 return true;
309         }
310
311         if (dn->ext_linearized) {
312                 parse_dn = dn->ext_linearized;
313         } else {
314                 parse_dn = dn->linearized;
315         }
316
317         if ( ! parse_dn ) {
318                 return false;
319         }
320
321         is_index = (strncmp(parse_dn, "DN=@INDEX:", 10) == 0);
322
323         /* Empty DNs */
324         if (parse_dn[0] == '\0') {
325                 return true;
326         }
327
328         /* Special DNs case */
329         if (dn->special) {
330                 return true;
331         }
332
333         /* make sure we free this if alloced previously before replacing */
334         talloc_free(dn->components);
335
336         LDB_FREE(dn->ext_components);
337         dn->ext_comp_num = 0;
338
339         /* in the common case we have 3 or more components */
340         /* make sure all components are zeroed, other functions depend on it */
341         dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
342         if ( ! dn->components) {
343                 return false;
344         }
345         dn->comp_num = 0;
346
347         /* Components data space is allocated here once */
348         data = talloc_array(dn->components, char, strlen(parse_dn) + 1);
349         if (!data) {
350                 return false;
351         }
352
353         p = parse_dn;
354         in_extended = true;
355         in_ex_name = false;
356         in_ex_value = false;
357         trim = true;
358         t = NULL;
359         d = dt = data;
360
361         while (*p) {
362                 if (in_extended) {
363
364                         if (!in_ex_name && !in_ex_value) {
365
366                                 if (p[0] == '<') {
367                                         p++;
368                                         ex_name = d;
369                                         in_ex_name = true;
370                                         continue;
371                                 } else if (p[0] == '\0') {
372                                         p++;
373                                         continue;
374                                 } else {
375                                         in_extended = false;
376                                         in_attr = true;
377                                         dt = d;
378
379                                         continue;
380                                 }
381                         }
382
383                         if (in_ex_name && *p == '=') {
384                                 *d++ = '\0';
385                                 p++;
386                                 ex_value = d;
387                                 in_ex_name = false;
388                                 in_ex_value = true;
389                                 continue;
390                         }
391
392                         if (in_ex_value && *p == '>') {
393                                 const struct ldb_dn_extended_syntax *ext_syntax;
394                                 struct ldb_val ex_val = {
395                                         .data = (uint8_t *)ex_value,
396                                         .length = d - ex_value
397                                 };
398
399                                 *d++ = '\0';
400                                 p++;
401                                 in_ex_value = false;
402
403                                 /* Process name and ex_value */
404
405                                 dn->ext_components = talloc_realloc(dn,
406                                                                     dn->ext_components,
407                                                                     struct ldb_dn_ext_component,
408                                                                     dn->ext_comp_num + 1);
409                                 if ( ! dn->ext_components) {
410                                         /* ouch ! */
411                                         goto failed;
412                                 }
413
414                                 ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, ex_name);
415                                 if (!ext_syntax) {
416                                         /* We don't know about this type of extended DN */
417                                         goto failed;
418                                 }
419
420                                 dn->ext_components[dn->ext_comp_num].name = talloc_strdup(dn->ext_components, ex_name);
421                                 if (!dn->ext_components[dn->ext_comp_num].name) {
422                                         /* ouch */
423                                         goto failed;
424                                 }
425                                 ret = ext_syntax->read_fn(dn->ldb, dn->ext_components,
426                                                           &ex_val, &dn->ext_components[dn->ext_comp_num].value);
427                                 if (ret != LDB_SUCCESS) {
428                                         ldb_dn_mark_invalid(dn);
429                                         goto failed;
430                                 }
431
432                                 dn->ext_comp_num++;
433
434                                 if (*p == '\0') {
435                                         /* We have reached the end (extended component only)! */
436                                         talloc_free(data);
437                                         return true;
438
439                                 } else if (*p == ';') {
440                                         p++;
441                                         continue;
442                                 } else {
443                                         ldb_dn_mark_invalid(dn);
444                                         goto failed;
445                                 }
446                         }
447
448                         *d++ = *p++;
449                         continue;
450                 }
451                 if (in_attr) {
452                         if (trim) {
453                                 if (*p == ' ') {
454                                         p++;
455                                         continue;
456                                 }
457
458                                 /* first char */
459                                 trim = false;
460
461                                 if (!isascii(*p)) {
462                                         /* attr names must be ascii only */
463                                         ldb_dn_mark_invalid(dn);
464                                         goto failed;
465                                 }
466
467                                 if (isdigit(*p)) {
468                                         is_oid = true;
469                                 } else
470                                 if ( ! isalpha(*p)) {
471                                         /* not a digit nor an alpha,
472                                          * invalid attribute name */
473                                         ldb_dn_mark_invalid(dn);
474                                         goto failed;
475                                 }
476
477                                 /* Copy this character across from parse_dn,
478                                  * now we have trimmed out spaces */
479                                 *d++ = *p++;
480                                 continue;
481                         }
482
483                         if (*p == ' ') {
484                                 p++;
485                                 /* valid only if we are at the end */
486                                 trim = true;
487                                 continue;
488                         }
489
490                         if (trim && (*p != '=')) {
491                                 /* spaces/tabs are not allowed */
492                                 ldb_dn_mark_invalid(dn);
493                                 goto failed;
494                         }
495
496                         if (*p == '=') {
497                                 /* attribute terminated */
498                                 in_attr = false;
499                                 in_value = true;
500                                 trim = true;
501                                 l = 0;
502
503                                 /* Terminate this string in d
504                                  * (which is a copy of parse_dn
505                                  *  with spaces trimmed) */
506                                 *d++ = '\0';
507                                 dn->components[dn->comp_num].name = talloc_strdup(dn->components, dt);
508                                 if ( ! dn->components[dn->comp_num].name) {
509                                         /* ouch */
510                                         goto failed;
511                                 }
512
513                                 dt = d;
514
515                                 p++;
516                                 continue;
517                         }
518
519                         if (!isascii(*p)) {
520                                 /* attr names must be ascii only */
521                                 ldb_dn_mark_invalid(dn);
522                                 goto failed;
523                         }
524
525                         if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
526                                 /* not a digit nor a dot,
527                                  * invalid attribute oid */
528                                 ldb_dn_mark_invalid(dn);
529                                 goto failed;
530                         } else
531                         if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
532                                 /* not ALPHA, DIGIT or HYPHEN */
533                                 ldb_dn_mark_invalid(dn);
534                                 goto failed;
535                         }
536
537                         *d++ = *p++;
538                         continue;
539                 }
540
541                 if (in_value) {
542                         if (in_quote) {
543                                 if (*p == '\"') {
544                                         if (p[-1] != '\\') {
545                                                 p++;
546                                                 in_quote = false;
547                                                 continue;
548                                         }
549                                 }
550                                 *d++ = *p++;
551                                 l++;
552                                 continue;
553                         }
554
555                         if (trim) {
556                                 if (*p == ' ') {
557                                         p++;
558                                         continue;
559                                 }
560
561                                 /* first char */
562                                 trim = false;
563
564                                 if (*p == '\"') {
565                                         in_quote = true;
566                                         p++;
567                                         continue;
568                                 }
569                         }
570
571                         switch (*p) {
572
573                         /* TODO: support ber encoded values
574                         case '#':
575                         */
576
577                         case ',':
578                                 if (escape) {
579                                         *d++ = *p++;
580                                         l++;
581                                         escape = false;
582                                         continue;
583                                 }
584                                 /* ok found value terminator */
585
586                                 if ( t ) {
587                                         /* trim back */
588                                         d -= (p - t);
589                                         l -= (p - t);
590                                 }
591
592                                 in_attr = true;
593                                 in_value = false;
594                                 trim = true;
595
596                                 p++;
597                                 *d++ = '\0';
598                                 dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
599                                 dn->components[dn->comp_num].value.length = l;
600                                 if ( ! dn->components[dn->comp_num].value.data) {
601                                         /* ouch ! */
602                                         goto failed;
603                                 }
604
605                                 dt = d;
606
607                                 dn->comp_num++;
608                                 if (dn->comp_num > 2) {
609                                         dn->components = talloc_realloc(dn,
610                                                                         dn->components,
611                                                                         struct ldb_dn_component,
612                                                                         dn->comp_num + 1);
613                                         if ( ! dn->components) {
614                                                 /* ouch ! */
615                                                 goto failed;
616                                         }
617                                         /* make sure all components are zeroed, other functions depend on this */
618                                         memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
619                                 }
620
621                                 continue;
622
623                         case '+':
624                         case '=':
625                                 /* to main compatibility with earlier
626                                 versions of ldb indexing, we have to
627                                 accept the base64 encoded binary index
628                                 values, which contain a '+' or '='
629                                 which should normally be escaped */
630                                 if (is_index) {
631                                         if ( t ) t = NULL;
632                                         *d++ = *p++;
633                                         l++;
634                                         break;
635                                 }
636                                 /* fall through */
637                         case '\"':
638                         case '<':
639                         case '>':
640                         case ';':
641                                 /* a string with not escaped specials is invalid (tested) */
642                                 if ( ! escape) {
643                                         ldb_dn_mark_invalid(dn);
644                                         goto failed;
645                                 }
646                                 escape = false;
647
648                                 *d++ = *p++;
649                                 l++;
650
651                                 if ( t ) t = NULL;
652                                 break;
653
654                         case '\\':
655                                 if ( ! escape) {
656                                         escape = true;
657                                         p++;
658                                         continue;
659                                 }
660                                 escape = false;
661
662                                 *d++ = *p++;
663                                 l++;
664
665                                 if ( t ) t = NULL;
666                                 break;
667
668                         default:
669                                 if (escape) {
670                                         if (isxdigit(p[0]) && isxdigit(p[1])) {
671                                                 if (sscanf(p, "%02x", &x) != 1) {
672                                                         /* invalid escaping sequence */
673                                                         ldb_dn_mark_invalid(dn);
674                                                         goto failed;
675                                                 }
676                                                 p += 2;
677                                                 *d++ = (unsigned char)x;
678                                         } else {
679                                                 *d++ = *p++;
680                                         }
681
682                                         escape = false;
683                                         l++;
684                                         if ( t ) t = NULL;
685                                         break;
686                                 }
687
688                                 if (*p == ' ') {
689                                         if ( ! t) t = p;
690                                 } else {
691                                         if ( t ) t = NULL;
692                                 }
693
694                                 *d++ = *p++;
695                                 l++;
696
697                                 break;
698                         }
699
700                 }
701         }
702
703         if (in_attr || in_quote) {
704                 /* invalid dn */
705                 ldb_dn_mark_invalid(dn);
706                 goto failed;
707         }
708
709         /* save last element */
710         if ( t ) {
711                 /* trim back */
712                 d -= (p - t);
713                 l -= (p - t);
714         }
715
716         *d++ = '\0';
717         dn->components[dn->comp_num].value.length = l;
718         dn->components[dn->comp_num].value.data =
719                                 (uint8_t *)talloc_strdup(dn->components, dt);
720         if ( ! dn->components[dn->comp_num].value.data) {
721                 /* ouch */
722                 goto failed;
723         }
724
725         dn->comp_num++;
726
727         talloc_free(data);
728         return true;
729
730 failed:
731         dn->comp_num = 0;
732         talloc_free(dn->components);
733         return false;
734 }
735
736 bool ldb_dn_validate(struct ldb_dn *dn)
737 {
738         return ldb_dn_explode(dn);
739 }
740
741 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
742 {
743         int i, len;
744         char *d, *n;
745
746         if ( ! dn || ( dn->invalid)) return NULL;
747
748         if (dn->linearized) return dn->linearized;
749
750         if ( ! dn->components) {
751                 ldb_dn_mark_invalid(dn);
752                 return NULL;
753         }
754
755         if (dn->comp_num == 0) {
756                 dn->linearized = talloc_strdup(dn, "");
757                 if ( ! dn->linearized) return NULL;
758                 return dn->linearized;
759         }
760
761         /* calculate maximum possible length of DN */
762         for (len = 0, i = 0; i < dn->comp_num; i++) {
763                 /* name len */
764                 len += strlen(dn->components[i].name);
765                 /* max escaped data len */
766                 len += (dn->components[i].value.length * 3);
767                 len += 2; /* '=' and ',' */
768         }
769         dn->linearized = talloc_array(dn, char, len);
770         if ( ! dn->linearized) return NULL;
771
772         d = dn->linearized;
773
774         for (i = 0; i < dn->comp_num; i++) {
775
776                 /* copy the name */
777                 n = dn->components[i].name;
778                 while (*n) *d++ = *n++;
779
780                 *d++ = '=';
781
782                 /* and the value */
783                 d += ldb_dn_escape_internal( d,
784                                 (char *)dn->components[i].value.data,
785                                 dn->components[i].value.length);
786                 *d++ = ',';
787         }
788
789         *(--d) = '\0';
790
791         /* don't waste more memory than necessary */
792         dn->linearized = talloc_realloc(dn, dn->linearized,
793                                         char, (d - dn->linearized + 1));
794
795         return dn->linearized;
796 }
797
798 static int ldb_dn_extended_component_compare(const void *p1, const void *p2)
799 {
800         const struct ldb_dn_ext_component *ec1 = (const struct ldb_dn_ext_component *)p1;
801         const struct ldb_dn_ext_component *ec2 = (const struct ldb_dn_ext_component *)p2;
802         return strcmp(ec1->name, ec2->name);
803 }
804
805 char *ldb_dn_get_extended_linearized(void *mem_ctx, struct ldb_dn *dn, int mode)
806 {
807         const char *linearized = ldb_dn_get_linearized(dn);
808         char *p;
809         int i;
810
811         if (!linearized) {
812                 return NULL;
813         }
814
815         if (!ldb_dn_has_extended(dn)) {
816                 return talloc_strdup(mem_ctx, linearized);
817         }
818
819         if (!ldb_dn_validate(dn)) {
820                 return NULL;
821         }
822
823         /* sort the extended components by name. The idea is to make
824          * the resulting DNs consistent, plus to ensure that we put
825          * 'DELETED' first, so it can be very quickly recognised
826          */
827         TYPESAFE_QSORT(dn->ext_components, dn->ext_comp_num,
828                        ldb_dn_extended_component_compare);
829
830         for (i = 0; i < dn->ext_comp_num; i++) {
831                 const struct ldb_dn_extended_syntax *ext_syntax;
832                 const char *name = dn->ext_components[i].name;
833                 struct ldb_val ec_val = dn->ext_components[i].value;
834                 struct ldb_val val;
835                 int ret;
836
837                 ext_syntax = ldb_dn_extended_syntax_by_name(dn->ldb, name);
838                 if (!ext_syntax) {
839                         return NULL;
840                 }
841
842                 if (mode == 1) {
843                         ret = ext_syntax->write_clear_fn(dn->ldb, mem_ctx,
844                                                         &ec_val, &val);
845                 } else if (mode == 0) {
846                         ret = ext_syntax->write_hex_fn(dn->ldb, mem_ctx,
847                                                         &ec_val, &val);
848                 } else {
849                         ret = -1;
850                 }
851
852                 if (ret != LDB_SUCCESS) {
853                         return NULL;
854                 }
855
856                 if (i == 0) {
857                         p = talloc_asprintf(mem_ctx, "<%s=%s>", 
858                                             name, val.data);
859                 } else {
860                         p = talloc_asprintf_append_buffer(p, ";<%s=%s>",
861                                                           name, val.data);
862                 }
863
864                 talloc_free(val.data);
865
866                 if (!p) {
867                         return NULL;
868                 }
869         }
870
871         if (dn->ext_comp_num && *linearized) {
872                 p = talloc_asprintf_append_buffer(p, ";%s", linearized);
873         }
874
875         if (!p) {
876                 return NULL;
877         }
878
879         return p;
880 }
881
882 /*
883   filter out all but an acceptable list of extended DN components
884  */
885 void ldb_dn_extended_filter(struct ldb_dn *dn, const char * const *accept)
886 {
887         int i;
888         for (i=0; i<dn->ext_comp_num; i++) {
889                 if (!ldb_attr_in_list(accept, dn->ext_components[i].name)) {
890                         memmove(&dn->ext_components[i],
891                                 &dn->ext_components[i+1],
892                                 (dn->ext_comp_num-(i+1))*sizeof(dn->ext_components[0]));
893                         dn->ext_comp_num--;
894                         i--;
895                 }
896         }
897 }
898
899
900 char *ldb_dn_alloc_linearized(void *mem_ctx, struct ldb_dn *dn)
901 {
902         return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
903 }
904
905 /*
906   casefold a dn. We need to casefold the attribute names, and canonicalize
907   attribute values of case insensitive attributes.
908 */
909
910 static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
911 {
912         int i, ret;
913
914         if ( ! dn || dn->invalid) return false;
915
916         if (dn->valid_case) return true;
917
918         if (( ! dn->components) && ( ! ldb_dn_explode(dn))) {
919                 return false;
920         }
921
922         for (i = 0; i < dn->comp_num; i++) {
923                 const struct ldb_schema_attribute *a;
924
925                 dn->components[i].cf_name =
926                         ldb_attr_casefold(dn->components,
927                                           dn->components[i].name);
928                 if (!dn->components[i].cf_name) {
929                         goto failed;
930                 }
931
932                 a = ldb_schema_attribute_by_name(dn->ldb,
933                                                  dn->components[i].cf_name);
934
935                 ret = a->syntax->canonicalise_fn(dn->ldb, dn->components,
936                                                  &(dn->components[i].value),
937                                                  &(dn->components[i].cf_value));
938                 if (ret != 0) {
939                         goto failed;
940                 }
941         }
942
943         dn->valid_case = true;
944
945         return true;
946
947 failed:
948         for (i = 0; i < dn->comp_num; i++) {
949                 LDB_FREE(dn->components[i].cf_name);
950                 LDB_FREE(dn->components[i].cf_value.data);
951         }
952         return false;
953 }
954
955 const char *ldb_dn_get_casefold(struct ldb_dn *dn)
956 {
957         int i, len;
958         char *d, *n;
959
960         if (dn->casefold) return dn->casefold;
961
962         if (dn->special) {
963                 dn->casefold = talloc_strdup(dn, dn->linearized);
964                 if (!dn->casefold) return NULL;
965                 dn->valid_case = true;
966                 return dn->casefold;
967         }
968
969         if ( ! ldb_dn_casefold_internal(dn)) {
970                 return NULL;
971         }
972
973         if (dn->comp_num == 0) {
974                 dn->casefold = talloc_strdup(dn, "");
975                 return dn->casefold;
976         }
977
978         /* calculate maximum possible length of DN */
979         for (len = 0, i = 0; i < dn->comp_num; i++) {
980                 /* name len */
981                 len += strlen(dn->components[i].cf_name);
982                 /* max escaped data len */
983                 len += (dn->components[i].cf_value.length * 3);
984                 len += 2; /* '=' and ',' */
985         }
986         dn->casefold = talloc_array(dn, char, len);
987         if ( ! dn->casefold) return NULL;
988
989         d = dn->casefold;
990
991         for (i = 0; i < dn->comp_num; i++) {
992
993                 /* copy the name */
994                 n = dn->components[i].cf_name;
995                 while (*n) *d++ = *n++;
996
997                 *d++ = '=';
998
999                 /* and the value */
1000                 d += ldb_dn_escape_internal( d,
1001                                 (char *)dn->components[i].cf_value.data,
1002                                 dn->components[i].cf_value.length);
1003                 *d++ = ',';
1004         }
1005         *(--d) = '\0';
1006
1007         /* don't waste more memory than necessary */
1008         dn->casefold = talloc_realloc(dn, dn->casefold,
1009                                       char, strlen(dn->casefold) + 1);
1010
1011         return dn->casefold;
1012 }
1013
1014 char *ldb_dn_alloc_casefold(void *mem_ctx, struct ldb_dn *dn)
1015 {
1016         return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
1017 }
1018
1019 /* Determine if dn is below base, in the ldap tree.  Used for
1020  * evaluating a subtree search.
1021  * 0 if they match, otherwise non-zero
1022  */
1023
1024 int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
1025 {
1026         int ret;
1027         int n_base, n_dn;
1028
1029         if ( ! base || base->invalid) return 1;
1030         if ( ! dn || dn->invalid) return -1;
1031
1032         if (( ! base->valid_case) || ( ! dn->valid_case)) {
1033                 if (base->linearized && dn->linearized) {
1034                         /* try with a normal compare first, if we are lucky
1035                          * we will avoid exploding and casfolding */
1036                         int dif;
1037                         dif = strlen(dn->linearized) - strlen(base->linearized);
1038                         if (dif < 0) {
1039                                 return dif;
1040                         }
1041                         if (strcmp(base->linearized,
1042                                    &dn->linearized[dif]) == 0) {
1043                                 return 0;
1044                         }
1045                 }
1046
1047                 if ( ! ldb_dn_casefold_internal(base)) {
1048                         return 1;
1049                 }
1050
1051                 if ( ! ldb_dn_casefold_internal(dn)) {
1052                         return -1;
1053                 }
1054
1055         }
1056
1057         /* if base has more components,
1058          * they don't have the same base */
1059         if (base->comp_num > dn->comp_num) {
1060                 return (dn->comp_num - base->comp_num);
1061         }
1062
1063         if (dn->comp_num == 0) {
1064                 if (dn->special && base->special) {
1065                         return strcmp(base->linearized, dn->linearized);
1066                 } else if (dn->special) {
1067                         return -1;
1068                 } else if (base->special) {
1069                         return 1;
1070                 } else {
1071                         return 0;
1072                 }
1073         }
1074
1075         n_base = base->comp_num - 1;
1076         n_dn = dn->comp_num - 1;
1077
1078         while (n_base >= 0) {
1079                 char *b_name = base->components[n_base].cf_name;
1080                 char *dn_name = dn->components[n_dn].cf_name;
1081
1082                 char *b_vdata = (char *)base->components[n_base].cf_value.data;
1083                 char *dn_vdata = (char *)dn->components[n_dn].cf_value.data;
1084
1085                 size_t b_vlen = base->components[n_base].cf_value.length;
1086                 size_t dn_vlen = dn->components[n_dn].cf_value.length;
1087
1088                 /* compare attr names */
1089                 ret = strcmp(b_name, dn_name);
1090                 if (ret != 0) return ret;
1091
1092                 /* compare attr.cf_value. */
1093                 if (b_vlen != dn_vlen) {
1094                         return b_vlen - dn_vlen;
1095                 }
1096                 ret = strcmp(b_vdata, dn_vdata);
1097                 if (ret != 0) return ret;
1098
1099                 n_base--;
1100                 n_dn--;
1101         }
1102
1103         return 0;
1104 }
1105
1106 /* compare DNs using casefolding compare functions.
1107
1108    If they match, then return 0
1109  */
1110
1111 int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
1112 {
1113         int i, ret;
1114
1115         if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) {
1116                 return -1;
1117         }
1118
1119         if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
1120                 if (dn0->linearized && dn1->linearized) {
1121                         /* try with a normal compare first, if we are lucky
1122                          * we will avoid exploding and casfolding */
1123                         if (strcmp(dn0->linearized, dn1->linearized) == 0) {
1124                                 return 0;
1125                         }
1126                 }
1127
1128                 if ( ! ldb_dn_casefold_internal(dn0)) {
1129                         return 1;
1130                 }
1131
1132                 if ( ! ldb_dn_casefold_internal(dn1)) {
1133                         return -1;
1134                 }
1135
1136         }
1137
1138         if (dn0->comp_num != dn1->comp_num) {
1139                 return (dn1->comp_num - dn0->comp_num);
1140         }
1141
1142         if (dn0->comp_num == 0) {
1143                 if (dn0->special && dn1->special) {
1144                         return strcmp(dn0->linearized, dn1->linearized);
1145                 } else if (dn0->special) {
1146                         return 1;
1147                 } else if (dn1->special) {
1148                         return -1;
1149                 } else {
1150                         return 0;
1151                 }
1152         }
1153
1154         for (i = 0; i < dn0->comp_num; i++) {
1155                 char *dn0_name = dn0->components[i].cf_name;
1156                 char *dn1_name = dn1->components[i].cf_name;
1157
1158                 char *dn0_vdata = (char *)dn0->components[i].cf_value.data;
1159                 char *dn1_vdata = (char *)dn1->components[i].cf_value.data;
1160
1161                 size_t dn0_vlen = dn0->components[i].cf_value.length;
1162                 size_t dn1_vlen = dn1->components[i].cf_value.length;
1163
1164                 /* compare attr names */
1165                 ret = strcmp(dn0_name, dn1_name);
1166                 if (ret != 0) {
1167                         return ret;
1168                 }
1169
1170                 /* compare attr.cf_value. */
1171                 if (dn0_vlen != dn1_vlen) {
1172                         return dn0_vlen - dn1_vlen;
1173                 }
1174                 ret = strcmp(dn0_vdata, dn1_vdata);
1175                 if (ret != 0) {
1176                         return ret;
1177                 }
1178         }
1179
1180         return 0;
1181 }
1182
1183 static struct ldb_dn_component ldb_dn_copy_component(
1184                                                 void *mem_ctx,
1185                                                 struct ldb_dn_component *src)
1186 {
1187         struct ldb_dn_component dst;
1188
1189         memset(&dst, 0, sizeof(dst));
1190
1191         if (src == NULL) {
1192                 return dst;
1193         }
1194
1195         dst.value = ldb_val_dup(mem_ctx, &(src->value));
1196         if (dst.value.data == NULL) {
1197                 return dst;
1198         }
1199
1200         dst.name = talloc_strdup(mem_ctx, src->name);
1201         if (dst.name == NULL) {
1202                 LDB_FREE(dst.value.data);
1203                 return dst;
1204         }
1205
1206         if (src->cf_value.data) {
1207                 dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
1208                 if (dst.cf_value.data == NULL) {
1209                         LDB_FREE(dst.value.data);
1210                         LDB_FREE(dst.name);
1211                         return dst;
1212                 }
1213
1214                 dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
1215                 if (dst.cf_name == NULL) {
1216                         LDB_FREE(dst.cf_name);
1217                         LDB_FREE(dst.value.data);
1218                         LDB_FREE(dst.name);
1219                         return dst;
1220                 }
1221         } else {
1222                 dst.cf_value.data = NULL;
1223                 dst.cf_name = NULL;
1224         }
1225
1226         return dst;
1227 }
1228
1229 static struct ldb_dn_ext_component ldb_dn_ext_copy_component(
1230                                                 void *mem_ctx,
1231                                                 struct ldb_dn_ext_component *src)
1232 {
1233         struct ldb_dn_ext_component dst;
1234
1235         memset(&dst, 0, sizeof(dst));
1236
1237         if (src == NULL) {
1238                 return dst;
1239         }
1240
1241         dst.value = ldb_val_dup(mem_ctx, &(src->value));
1242         if (dst.value.data == NULL) {
1243                 return dst;
1244         }
1245
1246         dst.name = talloc_strdup(mem_ctx, src->name);
1247         if (dst.name == NULL) {
1248                 LDB_FREE(dst.value.data);
1249                 return dst;
1250         }
1251
1252         return dst;
1253 }
1254
1255 struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn)
1256 {
1257         struct ldb_dn *new_dn;
1258
1259         if (!dn || dn->invalid) {
1260                 return NULL;
1261         }
1262
1263         new_dn = talloc_zero(mem_ctx, struct ldb_dn);
1264         if ( !new_dn) {
1265                 return NULL;
1266         }
1267
1268         *new_dn = *dn;
1269
1270         if (dn->components) {
1271                 int i;
1272
1273                 new_dn->components =
1274                         talloc_zero_array(new_dn,
1275                                           struct ldb_dn_component,
1276                                           dn->comp_num);
1277                 if ( ! new_dn->components) {
1278                         talloc_free(new_dn);
1279                         return NULL;
1280                 }
1281
1282                 for (i = 0; i < dn->comp_num; i++) {
1283                         new_dn->components[i] =
1284                                 ldb_dn_copy_component(new_dn->components,
1285                                                       &dn->components[i]);
1286                         if ( ! new_dn->components[i].value.data) {
1287                                 talloc_free(new_dn);
1288                                 return NULL;
1289                         }
1290                 }
1291         }
1292
1293         if (dn->ext_components) {
1294                 int i;
1295
1296                 new_dn->ext_components =
1297                         talloc_zero_array(new_dn,
1298                                           struct ldb_dn_ext_component,
1299                                           dn->ext_comp_num);
1300                 if ( ! new_dn->ext_components) {
1301                         talloc_free(new_dn);
1302                         return NULL;
1303                 }
1304
1305                 for (i = 0; i < dn->ext_comp_num; i++) {
1306                         new_dn->ext_components[i] =
1307                                  ldb_dn_ext_copy_component(
1308                                                 new_dn->ext_components,
1309                                                 &dn->ext_components[i]);
1310                         if ( ! new_dn->ext_components[i].value.data) {
1311                                 talloc_free(new_dn);
1312                                 return NULL;
1313                         }
1314                 }
1315         }
1316
1317         if (dn->casefold) {
1318                 new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
1319                 if ( ! new_dn->casefold) {
1320                         talloc_free(new_dn);
1321                         return NULL;
1322                 }
1323         }
1324
1325         if (dn->linearized) {
1326                 new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
1327                 if ( ! new_dn->linearized) {
1328                         talloc_free(new_dn);
1329                         return NULL;
1330                 }
1331         }
1332
1333         if (dn->ext_linearized) {
1334                 new_dn->ext_linearized = talloc_strdup(new_dn,
1335                                                         dn->ext_linearized);
1336                 if ( ! new_dn->ext_linearized) {
1337                         talloc_free(new_dn);
1338                         return NULL;
1339                 }
1340         }
1341
1342         return new_dn;
1343 }
1344
1345 /* modify the given dn by adding a base.
1346  *
1347  * return true if successful and false if not
1348  * if false is returned the dn may be marked invalid
1349  */
1350 bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
1351 {
1352         const char *s;
1353         char *t;
1354
1355         if ( !base || base->invalid || !dn || dn->invalid) {
1356                 return false;
1357         }
1358
1359         if (dn->components) {
1360                 int i;
1361
1362                 if ( ! ldb_dn_validate(base)) {
1363                         return false;
1364                 }
1365
1366                 s = NULL;
1367                 if (dn->valid_case) {
1368                         if ( ! (s = ldb_dn_get_casefold(base))) {
1369                                 return false;
1370                         }
1371                 }
1372
1373                 dn->components = talloc_realloc(dn,
1374                                                 dn->components,
1375                                                 struct ldb_dn_component,
1376                                                 dn->comp_num + base->comp_num);
1377                 if ( ! dn->components) {
1378                         ldb_dn_mark_invalid(dn);
1379                         return false;
1380                 }
1381
1382                 for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
1383                         dn->components[dn->comp_num] =
1384                                 ldb_dn_copy_component(dn->components,
1385                                                         &base->components[i]);
1386                         if (dn->components[dn->comp_num].value.data == NULL) {
1387                                 ldb_dn_mark_invalid(dn);
1388                                 return false;
1389                         }
1390                 }
1391
1392                 if (dn->casefold && s) {
1393                         if (*dn->casefold) {
1394                                 t = talloc_asprintf(dn, "%s,%s",
1395                                                     dn->casefold, s);
1396                         } else {
1397                                 t = talloc_strdup(dn, s);
1398                         }
1399                         LDB_FREE(dn->casefold);
1400                         dn->casefold = t;
1401                 }
1402         }
1403
1404         if (dn->linearized) {
1405
1406                 s = ldb_dn_get_linearized(base);
1407                 if ( ! s) {
1408                         return false;
1409                 }
1410
1411                 if (*dn->linearized) {
1412                         t = talloc_asprintf(dn, "%s,%s",
1413                                             dn->linearized, s);
1414                 } else {
1415                         t = talloc_strdup(dn, s);
1416                 }
1417                 if ( ! t) {
1418                         ldb_dn_mark_invalid(dn);
1419                         return false;
1420                 }
1421                 LDB_FREE(dn->linearized);
1422                 dn->linearized = t;
1423         }
1424
1425         /* Wipe the ext_linearized DN,
1426          * the GUID and SID are almost certainly no longer valid */
1427         if (dn->ext_linearized) {
1428                 LDB_FREE(dn->ext_linearized);
1429         }
1430
1431         LDB_FREE(dn->ext_components);
1432         dn->ext_comp_num = 0;
1433         return true;
1434 }
1435
1436 /* modify the given dn by adding a base.
1437  *
1438  * return true if successful and false if not
1439  * if false is returned the dn may be marked invalid
1440  */
1441 bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
1442 {
1443         struct ldb_dn *base;
1444         char *base_str;
1445         va_list ap;
1446         bool ret;
1447
1448         if ( !dn || dn->invalid) {
1449                 return false;
1450         }
1451
1452         va_start(ap, base_fmt);
1453         base_str = talloc_vasprintf(dn, base_fmt, ap);
1454         va_end(ap);
1455
1456         if (base_str == NULL) {
1457                 return false;
1458         }
1459
1460         base = ldb_dn_new(base_str, dn->ldb, base_str);
1461
1462         ret = ldb_dn_add_base(dn, base);
1463
1464         talloc_free(base_str);
1465
1466         return ret;
1467 }
1468
1469 /* modify the given dn by adding children elements.
1470  *
1471  * return true if successful and false if not
1472  * if false is returned the dn may be marked invalid
1473  */
1474 bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
1475 {
1476         const char *s;
1477         char *t;
1478
1479         if ( !child || child->invalid || !dn || dn->invalid) {
1480                 return false;
1481         }
1482
1483         if (dn->components) {
1484                 int n, i, j;
1485
1486                 if ( ! ldb_dn_validate(child)) {
1487                         return false;
1488                 }
1489
1490                 s = NULL;
1491                 if (dn->valid_case) {
1492                         if ( ! (s = ldb_dn_get_casefold(child))) {
1493                                 return false;
1494                         }
1495                 }
1496
1497                 n = dn->comp_num + child->comp_num;
1498
1499                 dn->components = talloc_realloc(dn,
1500                                                 dn->components,
1501                                                 struct ldb_dn_component,
1502                                                 n);
1503                 if ( ! dn->components) {
1504                         ldb_dn_mark_invalid(dn);
1505                         return false;
1506                 }
1507
1508                 for (i = dn->comp_num - 1, j = n - 1; i >= 0; i--, j--) {
1509                         dn->components[j] = dn->components[i];
1510                 }
1511
1512                 for (i = 0; i < child->comp_num; i++) {
1513                         dn->components[i] =
1514                                 ldb_dn_copy_component(dn->components,
1515                                                         &child->components[i]);
1516                         if (dn->components[i].value.data == NULL) {
1517                                 ldb_dn_mark_invalid(dn);
1518                                 return false;
1519                         }
1520                 }
1521
1522                 dn->comp_num = n;
1523
1524                 if (dn->casefold && s) {
1525                         t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
1526                         LDB_FREE(dn->casefold);
1527                         dn->casefold = t;
1528                 }
1529         }
1530
1531         if (dn->linearized) {
1532
1533                 s = ldb_dn_get_linearized(child);
1534                 if ( ! s) {
1535                         return false;
1536                 }
1537
1538                 t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
1539                 if ( ! t) {
1540                         ldb_dn_mark_invalid(dn);
1541                         return false;
1542                 }
1543                 LDB_FREE(dn->linearized);
1544                 dn->linearized = t;
1545         }
1546
1547         /* Wipe the ext_linearized DN,
1548          * the GUID and SID are almost certainly no longer valid */
1549         LDB_FREE(dn->ext_linearized);
1550
1551         LDB_FREE(dn->ext_components);
1552         dn->ext_comp_num = 0;
1553
1554         return true;
1555 }
1556
1557 /* modify the given dn by adding children elements.
1558  *
1559  * return true if successful and false if not
1560  * if false is returned the dn may be marked invalid
1561  */
1562 bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
1563 {
1564         struct ldb_dn *child;
1565         char *child_str;
1566         va_list ap;
1567         bool ret;
1568
1569         if ( !dn || dn->invalid) {
1570                 return false;
1571         }
1572
1573         va_start(ap, child_fmt);
1574         child_str = talloc_vasprintf(dn, child_fmt, ap);
1575         va_end(ap);
1576
1577         if (child_str == NULL) {
1578                 return false;
1579         }
1580
1581         child = ldb_dn_new(child_str, dn->ldb, child_str);
1582
1583         ret = ldb_dn_add_child(dn, child);
1584
1585         talloc_free(child_str);
1586
1587         return ret;
1588 }
1589
1590 bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
1591 {
1592         int i;
1593
1594         if ( ! ldb_dn_validate(dn)) {
1595                 return false;
1596         }
1597
1598         if (dn->comp_num < num) {
1599                 return false;
1600         }
1601
1602         /* free components */
1603         for (i = num; i > 0; i--) {
1604                 LDB_FREE(dn->components[dn->comp_num - i].name);
1605                 LDB_FREE(dn->components[dn->comp_num - i].value.data);
1606                 LDB_FREE(dn->components[dn->comp_num - i].cf_name);
1607                 LDB_FREE(dn->components[dn->comp_num - i].cf_value.data);
1608         }
1609
1610         dn->comp_num -= num;
1611
1612         if (dn->valid_case) {
1613                 for (i = 0; i < dn->comp_num; i++) {
1614                         LDB_FREE(dn->components[i].cf_name);
1615                         LDB_FREE(dn->components[i].cf_value.data);
1616                 }
1617                 dn->valid_case = false;
1618         }
1619
1620         LDB_FREE(dn->casefold);
1621         LDB_FREE(dn->linearized);
1622
1623         /* Wipe the ext_linearized DN,
1624          * the GUID and SID are almost certainly no longer valid */
1625         LDB_FREE(dn->ext_linearized);
1626
1627         LDB_FREE(dn->ext_components);
1628         dn->ext_comp_num = 0;
1629
1630         return true;
1631 }
1632
1633 bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
1634 {
1635         int i, j;
1636
1637         if ( ! ldb_dn_validate(dn)) {
1638                 return false;
1639         }
1640
1641         if (dn->comp_num < num) {
1642                 return false;
1643         }
1644
1645         for (i = 0, j = num; j < dn->comp_num; i++, j++) {
1646                 if (i < num) {
1647                         LDB_FREE(dn->components[i].name);
1648                         LDB_FREE(dn->components[i].value.data);
1649                         LDB_FREE(dn->components[i].cf_name);
1650                         LDB_FREE(dn->components[i].cf_value.data);
1651                 }
1652                 dn->components[i] = dn->components[j];
1653         }
1654
1655         dn->comp_num -= num;
1656
1657         if (dn->valid_case) {
1658                 for (i = 0; i < dn->comp_num; i++) {
1659                         LDB_FREE(dn->components[i].cf_name);
1660                         LDB_FREE(dn->components[i].cf_value.data);
1661                 }
1662                 dn->valid_case = false;
1663         }
1664
1665         LDB_FREE(dn->casefold);
1666         LDB_FREE(dn->linearized);
1667
1668         /* Wipe the ext_linearized DN,
1669          * the GUID and SID are almost certainly no longer valid */
1670         LDB_FREE(dn->ext_linearized);
1671
1672         LDB_FREE(dn->ext_components);
1673         dn->ext_comp_num = 0;
1674         return true;
1675 }
1676
1677 struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn)
1678 {
1679         struct ldb_dn *new_dn;
1680
1681         new_dn = ldb_dn_copy(mem_ctx, dn);
1682         if ( !new_dn ) {
1683                 return NULL;
1684         }
1685
1686         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1687                 talloc_free(new_dn);
1688                 return NULL;
1689         }
1690
1691         /* Wipe the ext_linearized DN,
1692          * the GUID and SID are almost certainly no longer valid */
1693         LDB_FREE(dn->ext_linearized);
1694
1695         LDB_FREE(dn->ext_components);
1696         dn->ext_comp_num = 0;
1697         return new_dn;
1698 }
1699
1700 /* Create a 'canonical name' string from a DN:
1701
1702    ie dc=samba,dc=org -> samba.org/
1703       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1704
1705    There are two formats,
1706    the EX format has the last '/' replaced with a newline (\n).
1707
1708 */
1709 static char *ldb_dn_canonical(void *mem_ctx, struct ldb_dn *dn, int ex_format) {
1710         int i;
1711         TALLOC_CTX *tmpctx;
1712         char *cracked = NULL;
1713         const char *format = (ex_format ? "\n" : "/" );
1714
1715         if ( ! ldb_dn_validate(dn)) {
1716                 return NULL;
1717         }
1718
1719         tmpctx = talloc_new(mem_ctx);
1720
1721         /* Walk backwards down the DN, grabbing 'dc' components at first */
1722         for (i = dn->comp_num - 1 ; i >= 0; i--) {
1723                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1724                         break;
1725                 }
1726                 if (cracked) {
1727                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1728                                                   ldb_dn_escape_value(tmpctx,
1729                                                         dn->components[i].value),
1730                                                   cracked);
1731                 } else {
1732                         cracked = ldb_dn_escape_value(tmpctx,
1733                                                         dn->components[i].value);
1734                 }
1735                 if (!cracked) {
1736                         goto done;
1737                 }
1738         }
1739
1740         /* Only domain components?  Finish here */
1741         if (i < 0) {
1742                 cracked = talloc_strdup_append_buffer(cracked, format);
1743                 talloc_steal(mem_ctx, cracked);
1744                 goto done;
1745         }
1746
1747         /* Now walk backwards appending remaining components */
1748         for (; i > 0; i--) {
1749                 cracked = talloc_asprintf_append_buffer(cracked, "/%s",
1750                                                         ldb_dn_escape_value(tmpctx,
1751                                                         dn->components[i].value));
1752                 if (!cracked) {
1753                         goto done;
1754                 }
1755         }
1756
1757         /* Last one, possibly a newline for the 'ex' format */
1758         cracked = talloc_asprintf_append_buffer(cracked, "%s%s", format,
1759                                                 ldb_dn_escape_value(tmpctx,
1760                                                         dn->components[i].value));
1761
1762         talloc_steal(mem_ctx, cracked);
1763 done:
1764         talloc_free(tmpctx);
1765         return cracked;
1766 }
1767
1768 /* Wrapper functions for the above, for the two different string formats */
1769 char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn) {
1770         return ldb_dn_canonical(mem_ctx, dn, 0);
1771
1772 }
1773
1774 char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn) {
1775         return ldb_dn_canonical(mem_ctx, dn, 1);
1776 }
1777
1778 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1779 {
1780         if ( ! ldb_dn_validate(dn)) {
1781                 return -1;
1782         }
1783         return dn->comp_num;
1784 }
1785
1786 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1787 {
1788         if ( ! ldb_dn_validate(dn)) {
1789                 return NULL;
1790         }
1791         if (num >= dn->comp_num) return NULL;
1792         return dn->components[num].name;
1793 }
1794
1795 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn,
1796                                                 unsigned int num)
1797 {
1798         if ( ! ldb_dn_validate(dn)) {
1799                 return NULL;
1800         }
1801         if (num >= dn->comp_num) return NULL;
1802         return &dn->components[num].value;
1803 }
1804
1805 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1806 {
1807         if ( ! ldb_dn_validate(dn)) {
1808                 return NULL;
1809         }
1810         if (dn->comp_num == 0) return NULL;
1811         return dn->components[0].name;
1812 }
1813
1814 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1815 {
1816         if ( ! ldb_dn_validate(dn)) {
1817                 return NULL;
1818         }
1819         if (dn->comp_num == 0) return NULL;
1820         return &dn->components[0].value;
1821 }
1822
1823 int ldb_dn_set_component(struct ldb_dn *dn, int num,
1824                          const char *name, const struct ldb_val val)
1825 {
1826         char *n;
1827         struct ldb_val v;
1828
1829         if ( ! ldb_dn_validate(dn)) {
1830                 return LDB_ERR_OTHER;
1831         }
1832
1833         if (num >= dn->comp_num) {
1834                 return LDB_ERR_OTHER;
1835         }
1836
1837         n = talloc_strdup(dn, name);
1838         if ( ! n) {
1839                 return LDB_ERR_OTHER;
1840         }
1841
1842         v.length = val.length;
1843         v.data = (uint8_t *)talloc_memdup(dn, val.data, v.length+1);
1844         if ( ! v.data) {
1845                 talloc_free(n);
1846                 return LDB_ERR_OTHER;
1847         }
1848
1849         talloc_free(dn->components[num].name);
1850         talloc_free(dn->components[num].value.data);
1851         dn->components[num].name = n;
1852         dn->components[num].value = v;
1853
1854         if (dn->valid_case) {
1855                 int i;
1856                 for (i = 0; i < dn->comp_num; i++) {
1857                         LDB_FREE(dn->components[i].cf_name);
1858                         LDB_FREE(dn->components[i].cf_value.data);
1859                 }
1860                 dn->valid_case = false;
1861         }
1862         LDB_FREE(dn->casefold);
1863         LDB_FREE(dn->linearized);
1864
1865         /* Wipe the ext_linearized DN,
1866          * the GUID and SID are almost certainly no longer valid */
1867         LDB_FREE(dn->ext_linearized);
1868
1869         dn->ext_comp_num = 0;
1870         LDB_FREE(dn->ext_components);
1871         return LDB_SUCCESS;
1872 }
1873
1874 const struct ldb_val *ldb_dn_get_extended_component(struct ldb_dn *dn,
1875                                                     const char *name)
1876 {
1877         int i;
1878         if ( ! ldb_dn_validate(dn)) {
1879                 return NULL;
1880         }
1881         for (i=0; i < dn->ext_comp_num; i++) {
1882                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
1883                         return &dn->ext_components[i].value;
1884                 }
1885         }
1886         return NULL;
1887 }
1888
1889 int ldb_dn_set_extended_component(struct ldb_dn *dn,
1890                                   const char *name, const struct ldb_val *val)
1891 {
1892         struct ldb_dn_ext_component *p;
1893         int i;
1894         struct ldb_val v2;
1895
1896         if ( ! ldb_dn_validate(dn)) {
1897                 return LDB_ERR_OTHER;
1898         }
1899
1900         if (!ldb_dn_extended_syntax_by_name(dn->ldb, name)) {
1901                 /* We don't know how to handle this type of thing */
1902                 return LDB_ERR_INVALID_DN_SYNTAX;
1903         }
1904
1905         for (i=0; i < dn->ext_comp_num; i++) {
1906                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
1907                         if (val) {
1908                                 dn->ext_components[i].value =
1909                                         ldb_val_dup(dn->ext_components, val);
1910
1911                                 dn->ext_components[i].name =
1912                                         talloc_strdup(dn->ext_components, name);
1913                                 if (!dn->ext_components[i].name ||
1914                                     !dn->ext_components[i].value.data) {
1915                                         ldb_dn_mark_invalid(dn);
1916                                         return LDB_ERR_OPERATIONS_ERROR;
1917                                 }
1918                                 return LDB_SUCCESS;
1919                         } else {
1920                                 if (i != (dn->ext_comp_num - 1)) {
1921                                         memmove(&dn->ext_components[i],
1922                                                 &dn->ext_components[i+1],
1923                                                 ((dn->ext_comp_num-1) - i) *
1924                                                   sizeof(*dn->ext_components));
1925                                 }
1926                                 dn->ext_comp_num--;
1927
1928                                 dn->ext_components = talloc_realloc(dn,
1929                                                    dn->ext_components,
1930                                                    struct ldb_dn_ext_component,
1931                                                    dn->ext_comp_num);
1932                                 if (!dn->ext_components) {
1933                                         ldb_dn_mark_invalid(dn);
1934                                         return LDB_ERR_OPERATIONS_ERROR;
1935                                 }
1936                                 return LDB_SUCCESS;
1937                         }
1938                 }
1939         }
1940
1941         if (val == NULL) {
1942                 /* removing a value that doesn't exist is not an error */
1943                 return LDB_SUCCESS;
1944         }
1945
1946         v2 = *val;
1947
1948         p = dn->ext_components
1949                 = talloc_realloc(dn,
1950                                  dn->ext_components,
1951                                  struct ldb_dn_ext_component,
1952                                  dn->ext_comp_num + 1);
1953         if (!dn->ext_components) {
1954                 ldb_dn_mark_invalid(dn);
1955                 return LDB_ERR_OPERATIONS_ERROR;
1956         }
1957
1958         p[dn->ext_comp_num].value = ldb_val_dup(dn->ext_components, &v2);
1959         p[dn->ext_comp_num].name = talloc_strdup(p, name);
1960
1961         if (!dn->ext_components[i].name || !dn->ext_components[i].value.data) {
1962                 ldb_dn_mark_invalid(dn);
1963                 return LDB_ERR_OPERATIONS_ERROR;
1964         }
1965         dn->ext_components = p;
1966         dn->ext_comp_num++;
1967
1968         return LDB_SUCCESS;
1969 }
1970
1971 void ldb_dn_remove_extended_components(struct ldb_dn *dn)
1972 {
1973         dn->ext_comp_num = 0;
1974         LDB_FREE(dn->ext_components);
1975 }
1976
1977 bool ldb_dn_is_valid(struct ldb_dn *dn)
1978 {
1979         if ( ! dn) return false;
1980         return ! dn->invalid;
1981 }
1982
1983 bool ldb_dn_is_special(struct ldb_dn *dn)
1984 {
1985         if ( ! dn || dn->invalid) return false;
1986         return dn->special;
1987 }
1988
1989 bool ldb_dn_has_extended(struct ldb_dn *dn)
1990 {
1991         if ( ! dn || dn->invalid) return false;
1992         if (dn->ext_linearized && (dn->ext_linearized[0] == '<')) return true;
1993         return dn->ext_comp_num != 0;
1994 }
1995
1996 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
1997 {
1998         if ( ! dn || dn->invalid) return false;
1999         return ! strcmp(dn->linearized, check);
2000 }
2001
2002 bool ldb_dn_is_null(struct ldb_dn *dn)
2003 {
2004         if ( ! dn || dn->invalid) return false;
2005         if (ldb_dn_has_extended(dn)) return false;
2006         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
2007         return false;
2008 }
2009
2010 /*
2011   this updates dn->components, taking the components from ref_dn.
2012   This is used by code that wants to update the DN path of a DN
2013   while not impacting on the extended DN components
2014  */
2015 int ldb_dn_update_components(struct ldb_dn *dn, const struct ldb_dn *ref_dn)
2016 {
2017         dn->components = talloc_realloc(dn, dn->components,
2018                                         struct ldb_dn_component, ref_dn->comp_num);
2019         if (!dn->components) {
2020                 return LDB_ERR_OPERATIONS_ERROR;
2021         }
2022         memcpy(dn->components, ref_dn->components,
2023                sizeof(struct ldb_dn_component)*ref_dn->comp_num);
2024         dn->comp_num = ref_dn->comp_num;
2025
2026         talloc_free(dn->linearized);
2027         talloc_free(dn->ext_linearized);
2028         dn->ext_linearized = NULL;
2029         dn->linearized = NULL;
2030
2031         return LDB_SUCCESS;
2032 }