source4/lib/ldb/common/ldb_dn.c

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