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