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