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 = 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;
 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) {
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 = strcmp(b_vdata, dn_vdata);
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 = strcmp(dn0_vdata, dn1_vdata);
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 struct ldb_dn *ldb_dn_get_parent(TALLOC_CTX *mem_ctx, struct ldb_dn *dn)
1688 {
1689         struct ldb_dn *new_dn;
1690
1691         new_dn = ldb_dn_copy(mem_ctx, dn);
1692         if ( !new_dn ) {
1693                 return NULL;
1694         }
1695
1696         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1697                 talloc_free(new_dn);
1698                 return NULL;
1699         }
1700
1701         return new_dn;
1702 }
1703
1704 /* Create a 'canonical name' string from a DN:
1705
1706    ie dc=samba,dc=org -> samba.org/
1707       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1708
1709    There are two formats,
1710    the EX format has the last '/' replaced with a newline (\n).
1711
1712 */
1713 static char *ldb_dn_canonical(TALLOC_CTX *mem_ctx, struct ldb_dn *dn, int ex_format) {
1714         unsigned int i;
1715         TALLOC_CTX *tmpctx;
1716         char *cracked = NULL;
1717         const char *format = (ex_format ? "\n" : "/" );
1718
1719         if ( ! ldb_dn_validate(dn)) {
1720                 return NULL;
1721         }
1722
1723         tmpctx = talloc_new(mem_ctx);
1724
1725         /* Walk backwards down the DN, grabbing 'dc' components at first */
1726         for (i = dn->comp_num - 1; i != (unsigned int) -1; i--) {
1727                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1728                         break;
1729                 }
1730                 if (cracked) {
1731                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1732                                                   ldb_dn_escape_value(tmpctx,
1733                                                         dn->components[i].value),
1734                                                   cracked);
1735                 } else {
1736                         cracked = ldb_dn_escape_value(tmpctx,
1737                                                         dn->components[i].value);
1738                 }
1739                 if (!cracked) {
1740                         goto done;
1741                 }
1742         }
1743
1744         /* Only domain components?  Finish here */
1745         if (i == (unsigned int) -1) {
1746                 cracked = talloc_strdup_append_buffer(cracked, format);
1747                 talloc_steal(mem_ctx, cracked);
1748                 goto done;
1749         }
1750
1751         /* Now walk backwards appending remaining components */
1752         for (; i > 0; i--) {
1753                 cracked = talloc_asprintf_append_buffer(cracked, "/%s",
1754                                                         ldb_dn_escape_value(tmpctx,
1755                                                         dn->components[i].value));
1756                 if (!cracked) {
1757                         goto done;
1758                 }
1759         }
1760
1761         /* Last one, possibly a newline for the 'ex' format */
1762         cracked = talloc_asprintf_append_buffer(cracked, "%s%s", format,
1763                                                 ldb_dn_escape_value(tmpctx,
1764                                                         dn->components[i].value));
1765
1766         talloc_steal(mem_ctx, cracked);
1767 done:
1768         talloc_free(tmpctx);
1769         return cracked;
1770 }
1771
1772 /* Wrapper functions for the above, for the two different string formats */
1773 char *ldb_dn_canonical_string(TALLOC_CTX *mem_ctx, struct ldb_dn *dn) {
1774         return ldb_dn_canonical(mem_ctx, dn, 0);
1775
1776 }
1777
1778 char *ldb_dn_canonical_ex_string(TALLOC_CTX *mem_ctx, struct ldb_dn *dn) {
1779         return ldb_dn_canonical(mem_ctx, dn, 1);
1780 }
1781
1782 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1783 {
1784         if ( ! ldb_dn_validate(dn)) {
1785                 return -1;
1786         }
1787         return dn->comp_num;
1788 }
1789
1790 int ldb_dn_get_extended_comp_num(struct ldb_dn *dn)
1791 {
1792         if ( ! ldb_dn_validate(dn)) {
1793                 return -1;
1794         }
1795         return dn->ext_comp_num;
1796 }
1797
1798 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1799 {
1800         if ( ! ldb_dn_validate(dn)) {
1801                 return NULL;
1802         }
1803         if (num >= dn->comp_num) return NULL;
1804         return dn->components[num].name;
1805 }
1806
1807 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn,
1808                                                 unsigned int num)
1809 {
1810         if ( ! ldb_dn_validate(dn)) {
1811                 return NULL;
1812         }
1813         if (num >= dn->comp_num) return NULL;
1814         return &dn->components[num].value;
1815 }
1816
1817 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1818 {
1819         if ( ! ldb_dn_validate(dn)) {
1820                 return NULL;
1821         }
1822         if (dn->comp_num == 0) return NULL;
1823         return dn->components[0].name;
1824 }
1825
1826 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1827 {
1828         if ( ! ldb_dn_validate(dn)) {
1829                 return NULL;
1830         }
1831         if (dn->comp_num == 0) return NULL;
1832         return &dn->components[0].value;
1833 }
1834
1835 int ldb_dn_set_component(struct ldb_dn *dn, int num,
1836                          const char *name, const struct ldb_val val)
1837 {
1838         char *n;
1839         struct ldb_val v;
1840
1841         if ( ! ldb_dn_validate(dn)) {
1842                 return LDB_ERR_OTHER;
1843         }
1844
1845         if (num >= dn->comp_num) {
1846                 return LDB_ERR_OTHER;
1847         }
1848
1849         n = talloc_strdup(dn, name);
1850         if ( ! n) {
1851                 return LDB_ERR_OTHER;
1852         }
1853
1854         v.length = val.length;
1855         v.data = (uint8_t *)talloc_memdup(dn, val.data, v.length+1);
1856         if ( ! v.data) {
1857                 talloc_free(n);
1858                 return LDB_ERR_OTHER;
1859         }
1860
1861         talloc_free(dn->components[num].name);
1862         talloc_free(dn->components[num].value.data);
1863         dn->components[num].name = n;
1864         dn->components[num].value = v;
1865
1866         if (dn->valid_case) {
1867                 unsigned int i;
1868                 for (i = 0; i < dn->comp_num; i++) {
1869                         LDB_FREE(dn->components[i].cf_name);
1870                         LDB_FREE(dn->components[i].cf_value.data);
1871                 }
1872                 dn->valid_case = false;
1873         }
1874         LDB_FREE(dn->casefold);
1875         LDB_FREE(dn->linearized);
1876
1877         /* Wipe the ext_linearized DN,
1878          * the GUID and SID are almost certainly no longer valid */
1879         LDB_FREE(dn->ext_linearized);
1880         LDB_FREE(dn->ext_components);
1881         dn->ext_comp_num = 0;
1882
1883         return LDB_SUCCESS;
1884 }
1885
1886 const struct ldb_val *ldb_dn_get_extended_component(struct ldb_dn *dn,
1887                                                     const char *name)
1888 {
1889         unsigned int i;
1890         if ( ! ldb_dn_validate(dn)) {
1891                 return NULL;
1892         }
1893         for (i=0; i < dn->ext_comp_num; i++) {
1894                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
1895                         return &dn->ext_components[i].value;
1896                 }
1897         }
1898         return NULL;
1899 }
1900
1901 int ldb_dn_set_extended_component(struct ldb_dn *dn,
1902                                   const char *name, const struct ldb_val *val)
1903 {
1904         struct ldb_dn_ext_component *p;
1905         unsigned int i;
1906         struct ldb_val v2;
1907
1908         if ( ! ldb_dn_validate(dn)) {
1909                 return LDB_ERR_OTHER;
1910         }
1911
1912         if (!ldb_dn_extended_syntax_by_name(dn->ldb, name)) {
1913                 /* We don't know how to handle this type of thing */
1914                 return LDB_ERR_INVALID_DN_SYNTAX;
1915         }
1916
1917         for (i=0; i < dn->ext_comp_num; i++) {
1918                 if (ldb_attr_cmp(dn->ext_components[i].name, name) == 0) {
1919                         if (val) {
1920                                 dn->ext_components[i].value =
1921                                         ldb_val_dup(dn->ext_components, val);
1922
1923                                 dn->ext_components[i].name =
1924                                         talloc_strdup(dn->ext_components, name);
1925                                 if (!dn->ext_components[i].name ||
1926                                     !dn->ext_components[i].value.data) {
1927                                         ldb_dn_mark_invalid(dn);
1928                                         return LDB_ERR_OPERATIONS_ERROR;
1929                                 }
1930                         } else {
1931                                 if (i != (dn->ext_comp_num - 1)) {
1932                                         memmove(&dn->ext_components[i],
1933                                                 &dn->ext_components[i+1],
1934                                                 ((dn->ext_comp_num-1) - i) *
1935                                                   sizeof(*dn->ext_components));
1936                                 }
1937                                 dn->ext_comp_num--;
1938
1939                                 dn->ext_components = talloc_realloc(dn,
1940                                                    dn->ext_components,
1941                                                    struct ldb_dn_ext_component,
1942                                                    dn->ext_comp_num);
1943                                 if (!dn->ext_components) {
1944                                         ldb_dn_mark_invalid(dn);
1945                                         return LDB_ERR_OPERATIONS_ERROR;
1946                                 }
1947                         }
1948                         LDB_FREE(dn->ext_linearized);
1949
1950                         return LDB_SUCCESS;
1951                 }
1952         }
1953
1954         if (val == NULL) {
1955                 /* removing a value that doesn't exist is not an error */
1956                 return LDB_SUCCESS;
1957         }
1958
1959         v2 = *val;
1960
1961         p = dn->ext_components
1962                 = talloc_realloc(dn,
1963                                  dn->ext_components,
1964                                  struct ldb_dn_ext_component,
1965                                  dn->ext_comp_num + 1);
1966         if (!dn->ext_components) {
1967                 ldb_dn_mark_invalid(dn);
1968                 return LDB_ERR_OPERATIONS_ERROR;
1969         }
1970
1971         p[dn->ext_comp_num].value = ldb_val_dup(dn->ext_components, &v2);
1972         p[dn->ext_comp_num].name = talloc_strdup(p, name);
1973
1974         if (!dn->ext_components[i].name || !dn->ext_components[i].value.data) {
1975                 ldb_dn_mark_invalid(dn);
1976                 return LDB_ERR_OPERATIONS_ERROR;
1977         }
1978         dn->ext_components = p;
1979         dn->ext_comp_num++;
1980
1981         LDB_FREE(dn->ext_linearized);
1982
1983         return LDB_SUCCESS;
1984 }
1985
1986 void ldb_dn_remove_extended_components(struct ldb_dn *dn)
1987 {
1988         LDB_FREE(dn->ext_linearized);
1989         LDB_FREE(dn->ext_components);
1990         dn->ext_comp_num = 0;
1991 }
1992
1993 bool ldb_dn_is_valid(struct ldb_dn *dn)
1994 {
1995         if ( ! dn) return false;
1996         return ! dn->invalid;
1997 }
1998
1999 bool ldb_dn_is_special(struct ldb_dn *dn)
2000 {
2001         if ( ! dn || dn->invalid) return false;
2002         return dn->special;
2003 }
2004
2005 bool ldb_dn_has_extended(struct ldb_dn *dn)
2006 {
2007         if ( ! dn || dn->invalid) return false;
2008         if (dn->ext_linearized && (dn->ext_linearized[0] == '<')) return true;
2009         return dn->ext_comp_num != 0;
2010 }
2011
2012 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
2013 {
2014         if ( ! dn || dn->invalid) return false;
2015         return ! strcmp(dn->linearized, check);
2016 }
2017
2018 bool ldb_dn_is_null(struct ldb_dn *dn)
2019 {
2020         if ( ! dn || dn->invalid) return false;
2021         if (ldb_dn_has_extended(dn)) return false;
2022         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
2023         return false;
2024 }
2025
2026 /*
2027   this updates dn->components, taking the components from ref_dn.
2028   This is used by code that wants to update the DN path of a DN
2029   while not impacting on the extended DN components
2030  */
2031 int ldb_dn_update_components(struct ldb_dn *dn, const struct ldb_dn *ref_dn)
2032 {
2033         dn->components = talloc_realloc(dn, dn->components,
2034                                         struct ldb_dn_component, ref_dn->comp_num);
2035         if (!dn->components) {
2036                 return LDB_ERR_OPERATIONS_ERROR;
2037         }
2038         memcpy(dn->components, ref_dn->components,
2039                sizeof(struct ldb_dn_component)*ref_dn->comp_num);
2040         dn->comp_num = ref_dn->comp_num;
2041
2042         LDB_FREE(dn->casefold);
2043         LDB_FREE(dn->linearized);
2044         LDB_FREE(dn->ext_linearized);
2045
2046         return LDB_SUCCESS;
2047 }
2048
2049 /*
2050   minimise a DN. The caller must pass in a validated DN.
2051
2052   If the DN has an extended component then only the first extended
2053   component is kept, the DN string is stripped.
2054
2055   The existing dn is modified
2056  */
2057 bool ldb_dn_minimise(struct ldb_dn *dn)
2058 {
2059         unsigned int i;
2060
2061         if (!ldb_dn_validate(dn)) {
2062                 return false;
2063         }
2064         if (dn->ext_comp_num == 0) {
2065                 return true;
2066         }
2067
2068         /* free components */
2069         for (i = 0; i < dn->comp_num; i++) {
2070                 LDB_FREE(dn->components[i].name);
2071                 LDB_FREE(dn->components[i].value.data);
2072                 LDB_FREE(dn->components[i].cf_name);
2073                 LDB_FREE(dn->components[i].cf_value.data);
2074         }
2075         dn->comp_num = 0;
2076         dn->valid_case = false;
2077
2078         LDB_FREE(dn->casefold);
2079         LDB_FREE(dn->linearized);
2080
2081         /* note that we don't free dn->components as this there are
2082          * several places in ldb_dn.c that rely on it being non-NULL
2083          * for an exploded DN
2084          */
2085
2086         for (i = 1; i < dn->ext_comp_num; i++) {
2087                 LDB_FREE(dn->ext_components[i].name);
2088                 LDB_FREE(dn->ext_components[i].value.data);
2089         }
2090         dn->ext_comp_num = 1;
2091
2092         dn->ext_components = talloc_realloc(dn, dn->ext_components, struct ldb_dn_ext_component, 1);
2093         if (dn->ext_components == NULL) {
2094                 ldb_dn_mark_invalid(dn);
2095                 return false;
2096         }
2097
2098         LDB_FREE(dn->ext_linearized);
2099
2100         return true;
2101 }