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