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