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