source4/lib/ldb/common/ldb_dn.c

   1 /*
   2    ldb database library
   3
   4    Copyright (C) Simo Sorce 2005
   5
   6      ** NOTE! The following LGPL license applies to the ldb
   7      ** library. This does NOT imply that all of Samba is released
   8      ** under the LGPL
   9
  10    This library is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU Lesser General Public
  12    License as published by the Free Software Foundation; either
  13    version 3 of the License, or (at your option) any later version.
  14
  15    This library is distributed in the hope that it will be useful,
  16    but WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    Lesser General Public License for more details.
  19
  20    You should have received a copy of the GNU Lesser General Public
  21    License along with this library; if not, see <http://www.gnu.org/licenses/>.
  22 */
  23
  24 /*
  25  *  Name: ldb
  26  *
  27  *  Component: ldb dn creation and manipulation utility functions
  28  *
  29  *  Description: - explode a dn into it's own basic elements
  30  *                 and put them in a structure (only if necessary)
  31  *               - manipulate ldb_dn structures
  32  *
  33  *  Author: Simo Sorce
  34  */
  35
  36 #include "ldb_includes.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 {
  56
  57         struct ldb_context *ldb;
  58
  59         /* Special DNs are always linearized */
  60         bool special;
  61         bool invalid;
  62
  63         bool valid_case;
  64
  65         char *linearized;
  66         char *casefold;
  67
  68         unsigned int comp_num;
  69         struct ldb_dn_component *components;
  70
  71 };
  72
  73 /* strdn may be NULL */
  74 struct ldb_dn *ldb_dn_new(void *mem_ctx, struct ldb_context *ldb, const char *strdn)
  75 {
  76         struct ldb_dn *dn;
  77
  78         if ( (! mem_ctx) || (! ldb)) return NULL;
  79
  80         dn = talloc_zero(mem_ctx, struct ldb_dn);
  81         LDB_DN_NULL_FAILED(dn);
  82
  83         dn->ldb = ldb;
  84
  85         if (strdn) {
  86                 if (strdn[0] == '@') {
  87                         dn->special = true;
  88                 }
  89                 if (strncasecmp(strdn, "<GUID=", 6) == 0) {
  90                         /* this is special DN returned when the
  91                          * exploded_dn control is used */
  92                         dn->special = true;
  93                         /* FIXME: add a GUID string to ldb_dn structure */
  94                 } else if (strncasecmp(strdn, "<SID=", 8) == 0) {
  95                         /* this is special DN returned when the
  96                          * exploded_dn control is used */
  97                         dn->special = true;
  98                         /* FIXME: add a SID string to ldb_dn structure */
  99                 } else if (strncasecmp(strdn, "<WKGUID=", 8) == 0) {
 100                         /* this is special DN returned when the
 101                          * exploded_dn control is used */
 102                         dn->special = true;
 103                         /* FIXME: add a WKGUID string to ldb_dn structure */
 104                 }
 105                 dn->linearized = talloc_strdup(dn, strdn);
 106         } else {
 107                 dn->linearized = talloc_strdup(dn, "");
 108         }
 109         LDB_DN_NULL_FAILED(dn->linearized);
 110
 111         return dn;
 112
 113 failed:
 114         talloc_free(dn);
 115         return NULL;
 116 }
 117
 118 struct ldb_dn *ldb_dn_new_fmt(void *mem_ctx, struct ldb_context *ldb, const char *new_fmt, ...)
 119 {
 120         struct ldb_dn *dn;
 121         char *strdn;
 122         va_list ap;
 123
 124         if ( (! mem_ctx) || (! ldb)) return NULL;
 125
 126         dn = talloc_zero(mem_ctx, struct ldb_dn);
 127         LDB_DN_NULL_FAILED(dn);
 128
 129         dn->ldb = ldb;
 130
 131         va_start(ap, new_fmt);
 132         strdn = talloc_vasprintf(dn, new_fmt, ap);
 133         va_end(ap);
 134         LDB_DN_NULL_FAILED(strdn);
 135
 136         if (strdn[0] == '@') {
 137                 dn->special = true;
 138         }
 139         if (strncasecmp(strdn, "<GUID=", 6) == 0) {
 140                 /* this is special DN returned when the
 141                  * exploded_dn control is used */
 142                 dn->special = true;
 143                 /* FIXME: add a GUID string to ldb_dn structure */
 144         } else if (strncasecmp(strdn, "<SID=", 8) == 0) {
 145                 /* this is special DN returned when the
 146                  * exploded_dn control is used */
 147                 dn->special = true;
 148                 /* FIXME: add a SID string to ldb_dn structure */
 149         } else if (strncasecmp(strdn, "<WKGUID=", 8) == 0) {
 150                 /* this is special DN returned when the
 151                  * exploded_dn control is used */
 152                 dn->special = true;
 153                 /* FIXME: add a WKGUID string to ldb_dn structure */
 154         }
 155         dn->linearized = strdn;
 156
 157         return dn;
 158
 159 failed:
 160         talloc_free(dn);
 161         return NULL;
 162 }
 163
 164 static int ldb_dn_escape_internal(char *dst, const char *src, int len)
 165 {
 166         const char *p, *s;
 167         char *d;
 168         int l;
 169
 170         p = s = src;
 171         d = dst;
 172
 173         while (p - src < len) {
 174
 175                 p += strcspn(p, ",=\n+<>#;\\\"");
 176
 177                 if (p - src == len) /* found no escapable chars */
 178                         break;
 179
 180                 memcpy(d, s, p - s); /* copy the part of the string before the stop */
 181                 d += (p - s); /* move to current position */
 182
 183                 if (*p) { /* it is a normal escapable character */
 184                         *d++ = '\\';
 185                         *d++ = *p++;
 186                 } else { /* we have a zero byte in the string */
 187                         strncpy(d, "\00", 3); /* escape the zero */
 188                         d += 3;
 189                         p++; /* skip the zero */
 190                 }
 191                 s = p; /* move forward */
 192         }
 193
 194         /* copy the last part (with zero) and return */
 195         l = len - (s - src);
 196         memcpy(d, s, l + 1);
 197
 198         /* return the length of the resulting string */
 199         return (l + (d - dst));
 200 }
 201
 202 char *ldb_dn_escape_value(void *mem_ctx, struct ldb_val value)
 203 {
 204         char *dst;
 205
 206         if (!value.length)
 207                 return NULL;
 208
 209         /* allocate destination string, it will be at most 3 times the source */
 210         dst = talloc_array(mem_ctx, char, value.length * 3 + 1);
 211         if ( ! dst) {
 212                 talloc_free(dst);
 213                 return NULL;
 214         }
 215
 216         ldb_dn_escape_internal(dst, (const char *)value.data, value.length);
 217
 218         dst = talloc_realloc(mem_ctx, dst, char, strlen(dst) + 1);
 219
 220         return dst;
 221 }
 222
 223 /*
 224   explode a DN string into a ldb_dn structure
 225   based on RFC4514 except that we don't support multiple valued RDNs
 226 */
 227 static bool ldb_dn_explode(struct ldb_dn *dn)
 228 {
 229         char *p, *data, *d, *dt, *t;
 230         bool trim = false;
 231         bool in_attr = false;
 232         bool in_value = false;
 233         bool in_quote = false;
 234         bool is_oid = false;
 235         bool escape = false;
 236         unsigned x;
 237         int l;
 238
 239         if ( ! dn || dn->invalid) return false;
 240
 241         if (dn->components) {
 242                 return true;
 243         }
 244
 245         if ( ! dn->linearized) {
 246                 return false;
 247         }
 248
 249         /* Empty DNs */
 250         if (dn->linearized[0] == '\0') {
 251                 return true;
 252         }
 253
 254         /* Special DNs case */
 255         if (dn->special) {
 256                 return true;
 257         }
 258
 259         /* make sure we free this if alloced previously before replacing */
 260         talloc_free(dn->components);
 261
 262         /* in the common case we have 3 or more components */
 263         /* make sure all components are zeroed, other functions depend on this */
 264         dn->components = talloc_zero_array(dn, struct ldb_dn_component, 3);
 265         if ( ! dn->components) {
 266                 return false;
 267         }
 268         dn->comp_num = 0;
 269
 270         /* Components data space is allocated here once */
 271         data = talloc_array(dn->components, char, strlen(dn->linearized) + 1);
 272         if (!data) {
 273                 return false;
 274         }
 275
 276         p = dn->linearized;
 277         in_attr = true;
 278         trim = true;
 279         t = NULL;
 280         d = dt = data;
 281
 282         while (*p) {
 283
 284                 if (in_attr) {
 285                         if (trim) {
 286                                 if (*p == ' ') {
 287                                         p++;
 288                                         continue;
 289                                 }
 290
 291                                 /* first char */
 292                                 trim = false;
 293
 294                                 if (!isascii(*p)) {
 295                                         /* attr names must be ascii only */
 296                                         dn->invalid = true;
 297                                         goto failed;
 298                                 }
 299
 300                                 if (isdigit(*p)) {
 301                                         is_oid = true;
 302                                 } else
 303                                 if ( ! isalpha(*p)) {
 304                                         /* not a digit nor an alpha, invalid attribute name */
 305                                         dn->invalid = true;
 306                                         goto failed;
 307                                 }
 308
 309                                 *d++ = *p++;
 310                                 continue;
 311                         }
 312
 313                         if (*p == ' ') {
 314                                 p++;
 315                                 /* valid only if we are at the end */
 316                                 trim = true;
 317                                 continue;
 318                         }
 319
 320                         if (trim && (*p != '=')) {
 321                                 /* spaces/tabs are not allowed in attribute names */
 322                                 dn->invalid = true;
 323                                 goto failed;
 324                         }
 325
 326                         if (*p == '=') {
 327                                 /* attribute terminated */
 328                                 in_attr = false;
 329                                 in_value = true;
 330                                 trim = true;
 331                                 l = 0;
 332
 333                                 *d++ = '\0';
 334                                 dn->components[dn->comp_num].name = talloc_strdup(dn->components, dt);
 335                                 if ( ! dn->components[dn->comp_num].name) {
 336                                         /* ouch */
 337                                         goto failed;
 338                                 }
 339
 340                                 dt = d;
 341
 342                                 p++;
 343                                 continue;
 344                         }
 345
 346                         if (!isascii(*p)) {
 347                                 /* attr names must be ascii only */
 348                                 dn->invalid = true;
 349                                 goto failed;
 350                         }
 351
 352                         if (is_oid && ( ! (isdigit(*p) || (*p == '.')))) {
 353                                 /* not a digit nor a dot, invalid attribute oid */
 354                                 dn->invalid = true;
 355                                 goto failed;
 356                         } else
 357                         if ( ! (isalpha(*p) || isdigit(*p) || (*p == '-'))) {
 358                                 /* not ALPHA, DIGIT or HYPHEN */
 359                                 dn->invalid = true;
 360                                 goto failed;
 361                         }
 362
 363                         *d++ = *p++;
 364                         continue;
 365                 }
 366
 367                 if (in_value) {
 368                         if (in_quote) {
 369                                 if (*p == '\"') {
 370                                         if (p[-1] != '\\') {
 371                                                 p++;
 372                                                 in_quote = false;
 373                                                 continue;
 374                                         }
 375                                 }
 376                                 *d++ = *p++;
 377                                 l++;
 378                                 continue;
 379                         }
 380
 381                         if (trim) {
 382                                 if (*p == ' ') {
 383                                         p++;
 384                                         continue;
 385                                 }
 386
 387                                 /* first char */
 388                                 trim = false;
 389
 390                                 if (*p == '\"') {
 391                                         in_quote = true;
 392                                         p++;
 393                                         continue;
 394                                 }
 395                         }
 396
 397                         switch (*p) {
 398
 399                         /* TODO: support ber encoded values
 400                         case '#':
 401                         */
 402
 403                         case ',':
 404                                 if (escape) {
 405                                         *d++ = *p++;
 406                                         l++;
 407                                         escape = false;
 408                                         continue;
 409                                 }
 410                                 /* ok found value terminator */
 411
 412                                 if ( t ) {
 413                                         /* trim back */
 414                                         d -= (p - t);
 415                                         l -= (p - t);
 416                                 }
 417
 418                                 in_attr = true;
 419                                 in_value = false;
 420                                 trim = true;
 421
 422                                 p++;
 423                                 *d++ = '\0';
 424                                 dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 425                                 dn->components[dn->comp_num].value.length = l;
 426                                 if ( ! dn->components[dn->comp_num].value.data) {
 427                                         /* ouch ! */
 428                                         goto failed;
 429                                 }
 430
 431                                 dt = d;
 432
 433                                 dn->comp_num++;
 434                                 if (dn->comp_num > 2) {
 435                                         dn->components = talloc_realloc(dn,
 436                                                                         dn->components,
 437                                                                         struct ldb_dn_component,
 438                                                                         dn->comp_num + 1);
 439                                         if ( ! dn->components) {
 440                                                 /* ouch ! */
 441                                                 goto failed;
 442                                         }
 443                                         /* make sure all components are zeroed, other functions depend on this */
 444                                         memset(&dn->components[dn->comp_num], '\0', sizeof(struct ldb_dn_component));
 445                                 }
 446
 447                                 continue;
 448
 449                         case '=':
 450                         case '\n':
 451                         case '+':
 452                         case '<':
 453                         case '>':
 454                         case '#':
 455                         case ';':
 456                         case '\"':
 457                                 /* a string with not escaped specials is invalid (tested) */
 458                                 if ( ! escape) {
 459                                         dn->invalid = true;
 460                                         goto failed;
 461                                 }
 462                                 escape = false;
 463
 464                                 *d++ = *p++;
 465                                 l++;
 466
 467                                 if ( t ) t = NULL;
 468                                 break;
 469
 470                         case '\\':
 471                                 if ( ! escape) {
 472                                         escape = true;
 473                                         p++;
 474                                         continue;
 475                                 }
 476                                 escape = false;
 477
 478                                 *d++ = *p++;
 479                                 l++;
 480
 481                                 if ( t ) t = NULL;
 482                                 break;
 483
 484                         default:
 485                                 if (escape) {
 486                                         if (sscanf(p, "%02x", &x) != 1) {
 487                                                 /* invalid escaping sequence */
 488                                                 dn->invalid = true;
 489                                                 goto failed;
 490                                         }
 491                                         escape = false;
 492
 493                                         p += 2;
 494                                         *d++ = (unsigned char)x;
 495                                         l++;
 496
 497                                         if ( t ) t = NULL;
 498                                         break;
 499                                 }
 500
 501                                 if (*p == ' ') {
 502                                         if ( ! t) t = p;
 503                                 } else {
 504                                         if ( t ) t = NULL;
 505                                 }
 506
 507                                 *d++ = *p++;
 508                                 l++;
 509
 510                                 break;
 511                         }
 512
 513                 }
 514         }
 515
 516         if (in_attr || in_quote) {
 517                 /* invalid dn */
 518                 dn->invalid = true;
 519                 goto failed;
 520         }
 521
 522         /* save last element */
 523         if ( t ) {
 524                 /* trim back */
 525                 d -= (p - t);
 526                 l -= (p - t);
 527         }
 528
 529         *d++ = '\0';
 530         dn->components[dn->comp_num].value.data = (uint8_t *)talloc_strdup(dn->components, dt);
 531         dn->components[dn->comp_num].value.length = l;
 532
 533         if ( ! dn->components[dn->comp_num].value.data) {
 534                 /* ouch */
 535                 goto failed;
 536         }
 537
 538         dn->comp_num++;
 539
 540         talloc_free(data);
 541         return true;
 542
 543 failed:
 544         dn->comp_num = 0;
 545         talloc_free(dn->components);
 546         return false;
 547 }
 548
 549 bool ldb_dn_validate(struct ldb_dn *dn)
 550 {
 551         return ldb_dn_explode(dn);
 552 }
 553
 554 const char *ldb_dn_get_linearized(struct ldb_dn *dn)
 555 {
 556         int i, len;
 557         char *d, *n;
 558
 559         if ( ! dn || ( dn->invalid)) return NULL;
 560
 561         if (dn->linearized) return dn->linearized;
 562
 563         if ( ! dn->components) {
 564                 dn->invalid = true;
 565                 return NULL;
 566         }
 567
 568         if (dn->comp_num == 0) {
 569                 dn->linearized = talloc_strdup(dn, "");
 570                 if ( ! dn->linearized) return NULL;
 571                 return dn->linearized;
 572         }
 573
 574         /* calculate maximum possible length of DN */
 575         for (len = 0, i = 0; i < dn->comp_num; i++) {
 576                 len += strlen(dn->components[i].name); /* name len */
 577                 len += (dn->components[i].value.length * 3); /* max escaped data len */
 578                 len += 2; /* '=' and ',' */
 579         }
 580         dn->linearized = talloc_array(dn, char, len);
 581         if ( ! dn->linearized) return NULL;
 582
 583         d = dn->linearized;
 584
 585         for (i = 0; i < dn->comp_num; i++) {
 586
 587                 /* copy the name */
 588                 n = dn->components[i].name;
 589                 while (*n) *d++ = *n++;
 590
 591                 *d++ = '=';
 592
 593                 /* and the value */
 594                 d += ldb_dn_escape_internal( d,
 595                                 (char *)dn->components[i].value.data,
 596                                 dn->components[i].value.length);
 597                 *d++ = ',';
 598         }
 599
 600         *(--d) = '\0';
 601
 602         /* don't waste more memory than necessary */
 603         dn->linearized = talloc_realloc(dn, dn->linearized, char, (d - dn->linearized + 1));
 604
 605         return dn->linearized;
 606 }
 607
 608 char *ldb_dn_alloc_linearized(void *mem_ctx, struct ldb_dn *dn)
 609 {
 610         return talloc_strdup(mem_ctx, ldb_dn_get_linearized(dn));
 611 }
 612
 613 /*
 614   casefold a dn. We need to casefold the attribute names, and canonicalize
 615   attribute values of case insensitive attributes.
 616 */
 617
 618 static bool ldb_dn_casefold_internal(struct ldb_dn *dn)
 619 {
 620         int i, ret;
 621
 622         if ( ! dn || dn->invalid) return false;
 623
 624         if (dn->valid_case) return true;
 625
 626         if (( ! dn->components) && ( ! ldb_dn_explode(dn))) {
 627                 return false;
 628         }
 629
 630         for (i = 0; i < dn->comp_num; i++) {
 631                 const struct ldb_schema_attribute *a;
 632
 633                 dn->components[i].cf_name = ldb_attr_casefold(dn->components, dn->components[i].name);
 634                 if (!dn->components[i].cf_name) {
 635                         goto failed;
 636                 }
 637
 638                 a = ldb_schema_attribute_by_name(dn->ldb, dn->components[i].cf_name);
 639                 ret = a->syntax->canonicalise_fn(dn->ldb, dn->components,
 640                                                  &(dn->components[i].value),
 641                                                  &(dn->components[i].cf_value));
 642                 if (ret != 0) {
 643                         goto failed;
 644                 }
 645         }
 646
 647         dn->valid_case = true;
 648
 649         return true;
 650
 651 failed:
 652         for (i = 0; i < dn->comp_num; i++) {
 653                 LDB_FREE(dn->components[i].cf_name);
 654                 LDB_FREE(dn->components[i].cf_value.data);
 655         }
 656         return false;
 657 }
 658
 659 const char *ldb_dn_get_casefold(struct ldb_dn *dn)
 660 {
 661         int i, len;
 662         char *d, *n;
 663
 664         if (dn->casefold) return dn->casefold;
 665
 666         if (dn->special) {
 667                 dn->casefold = talloc_strdup(dn, dn->linearized);
 668                 if (!dn->casefold) return NULL;
 669                 dn->valid_case = true;
 670                 return dn->casefold;
 671         }
 672
 673         if ( ! ldb_dn_casefold_internal(dn)) {
 674                 return NULL;
 675         }
 676
 677         if (dn->comp_num == 0) {
 678                 if (dn->linearized && dn->linearized[0] == '\0') {
 679                         /* hmm a NULL dn, should we faild casefolding ? */
 680                         dn->casefold = talloc_strdup(dn, "");
 681                         return dn->casefold;
 682                 }
 683                 /* A DN must be NULL, special, or have components */
 684                 dn->invalid = true;
 685                 return NULL;
 686         }
 687
 688         /* calculate maximum possible length of DN */
 689         for (len = 0, i = 0; i < dn->comp_num; i++) {
 690                 len += strlen(dn->components[i].cf_name); /* name len */
 691                 len += (dn->components[i].cf_value.length * 3); /* max escaped data len */
 692                 len += 2; /* '=' and ',' */
 693         }
 694         dn->casefold = talloc_array(dn, char, len);
 695         if ( ! dn->casefold) return NULL;
 696
 697         d = dn->casefold;
 698
 699         for (i = 0; i < dn->comp_num; i++) {
 700
 701                 /* copy the name */
 702                 n = dn->components[i].cf_name;
 703                 while (*n) *d++ = *n++;
 704
 705                 *d++ = '=';
 706
 707                 /* and the value */
 708                 d += ldb_dn_escape_internal( d,
 709                                 (char *)dn->components[i].cf_value.data,
 710                                 dn->components[i].cf_value.length);
 711                 *d++ = ',';
 712         }
 713         *(--d) = '\0';
 714
 715         /* don't waste more memory than necessary */
 716         dn->casefold = talloc_realloc(dn, dn->casefold, char, strlen(dn->casefold) + 1);
 717
 718         return dn->casefold;
 719 }
 720
 721 char *ldb_dn_alloc_casefold(void *mem_ctx, struct ldb_dn *dn)
 722 {
 723         return talloc_strdup(mem_ctx, ldb_dn_get_casefold(dn));
 724 }
 725
 726 /* Determine if dn is below base, in the ldap tree.  Used for
 727  * evaluating a subtree search.
 728  * 0 if they match, otherwise non-zero
 729  */
 730
 731 int ldb_dn_compare_base(struct ldb_dn *base, struct ldb_dn *dn)
 732 {
 733         int ret;
 734         int n_base, n_dn;
 735
 736         if ( ! base || base->invalid) return 1;
 737         if ( ! dn || dn->invalid) return -1;
 738
 739         if (( ! base->valid_case) || ( ! dn->valid_case)) {
 740                 if (base->linearized && dn->linearized) {
 741                         /* try with a normal compare first, if we are lucky
 742                          * we will avoid exploding and casfolding */
 743                         int dif;
 744                         dif = strlen(dn->linearized) - strlen(base->linearized);
 745                         if (dif < 0) return dif;
 746                         if (strcmp(base->linearized, &dn->linearized[dif]) == 0) return 0;
 747                 }
 748
 749                 if ( ! ldb_dn_casefold_internal(base)) {
 750                         return 1;
 751                 }
 752
 753                 if ( ! ldb_dn_casefold_internal(dn)) {
 754                         return -1;
 755                 }
 756
 757         }
 758
 759         /* if base has more components,
 760          * they don't have the same base */
 761         if (base->comp_num > dn->comp_num) {
 762                 return (dn->comp_num - base->comp_num);
 763         }
 764
 765         if (dn->comp_num == 0) {
 766                 if (dn->special && base->special) {
 767                         return strcmp(base->linearized, dn->linearized);
 768                 } else if (dn->special) {
 769                         return -1;
 770                 } else if (base->special) {
 771                         return 1;
 772                 } else {
 773                         return 0;
 774                 }
 775         }
 776
 777         n_base = base->comp_num - 1;
 778         n_dn = dn->comp_num - 1;
 779
 780         while (n_base >= 0) {
 781                 /* compare attr names */
 782                 ret = strcmp(base->components[n_base].cf_name, dn->components[n_dn].cf_name);
 783                 if (ret != 0) return ret;
 784
 785                 /* compare attr.cf_value. */
 786                 if (base->components[n_base].cf_value.length != dn->components[n_dn].cf_value.length) {
 787                         return base->components[n_base].cf_value.length - dn->components[n_dn].cf_value.length;
 788                 }
 789                 ret = strcmp((char *)base->components[n_base].cf_value.data, (char *)dn->components[n_dn].cf_value.data);
 790                 if (ret != 0) return ret;
 791
 792                 n_base--;
 793                 n_dn--;
 794         }
 795
 796         return 0;
 797 }
 798
 799 /* compare DNs using casefolding compare functions.
 800
 801    If they match, then return 0
 802  */
 803
 804 int ldb_dn_compare(struct ldb_dn *dn0, struct ldb_dn *dn1)
 805 {
 806         int i, ret;
 807
 808         if (( ! dn0) || dn0->invalid || ! dn1 || dn1->invalid) return -1;
 809
 810         if (( ! dn0->valid_case) || ( ! dn1->valid_case)) {
 811                 if (dn0->linearized && dn1->linearized) {
 812                         /* try with a normal compare first, if we are lucky
 813                          * we will avoid exploding and casfolding */
 814                         if (strcmp(dn0->linearized, dn1->linearized) == 0) return 0;
 815                 }
 816
 817                 if ( ! ldb_dn_casefold_internal(dn0)) {
 818                         return 1;
 819                 }
 820
 821                 if ( ! ldb_dn_casefold_internal(dn1)) {
 822                         return -1;
 823                 }
 824
 825         }
 826
 827         if (dn0->comp_num != dn1->comp_num) {
 828                 return (dn1->comp_num - dn0->comp_num);
 829         }
 830
 831         if (dn0->comp_num == 0) {
 832                 if (dn0->special && dn1->special) {
 833                         return strcmp(dn0->linearized, dn1->linearized);
 834                 } else if (dn0->special) {
 835                         return 1;
 836                 } else if (dn1->special) {
 837                         return -1;
 838                 } else {
 839                         return 0;
 840                 }
 841         }
 842
 843         for (i = 0; i < dn0->comp_num; i++) {
 844                 /* compare attr names */
 845                 ret = strcmp(dn0->components[i].cf_name, dn1->components[i].cf_name);
 846                 if (ret != 0) return ret;
 847
 848                 /* compare attr.cf_value. */
 849                 if (dn0->components[i].cf_value.length != dn1->components[i].cf_value.length) {
 850                         return dn0->components[i].cf_value.length - dn1->components[i].cf_value.length;
 851                 }
 852                 ret = strcmp((char *)dn0->components[i].cf_value.data, (char *)dn1->components[i].cf_value.data);
 853                 if (ret != 0) return ret;
 854         }
 855
 856         return 0;
 857 }
 858
 859 static struct ldb_dn_component ldb_dn_copy_component(void *mem_ctx, struct ldb_dn_component *src)
 860 {
 861         struct ldb_dn_component dst;
 862
 863         memset(&dst, 0, sizeof(dst));
 864
 865         if (src == NULL) {
 866                 return dst;
 867         }
 868
 869         dst.value = ldb_val_dup(mem_ctx, &(src->value));
 870         if (dst.value.data == NULL) {
 871                 return dst;
 872         }
 873
 874         dst.name = talloc_strdup(mem_ctx, src->name);
 875         if (dst.name == NULL) {
 876                 LDB_FREE(dst.value.data);
 877                 return dst;
 878         }
 879
 880         if (src->cf_value.data) {
 881                 dst.cf_value = ldb_val_dup(mem_ctx, &(src->cf_value));
 882                 if (dst.cf_value.data == NULL) {
 883                         LDB_FREE(dst.value.data);
 884                         LDB_FREE(dst.name);
 885                         return dst;
 886                 }
 887
 888                 dst.cf_name = talloc_strdup(mem_ctx, src->cf_name);
 889                 if (dst.cf_name == NULL) {
 890                         LDB_FREE(dst.cf_name);
 891                         LDB_FREE(dst.value.data);
 892                         LDB_FREE(dst.name);
 893                         return dst;
 894                 }
 895         } else {
 896                 dst.cf_value.data = NULL;
 897                 dst.cf_name = NULL;
 898         }
 899
 900         return dst;
 901 }
 902
 903 struct ldb_dn *ldb_dn_copy(void *mem_ctx, struct ldb_dn *dn)
 904 {
 905         struct ldb_dn *new_dn;
 906
 907         if (!dn || dn->invalid) {
 908                 return NULL;
 909         }
 910
 911         new_dn = talloc_zero(mem_ctx, struct ldb_dn);
 912         if ( !new_dn) {
 913                 return NULL;
 914         }
 915
 916         *new_dn = *dn;
 917
 918         if (dn->components) {
 919                 int i;
 920
 921                 new_dn->components = talloc_zero_array(new_dn, struct ldb_dn_component, dn->comp_num);
 922                 if ( ! new_dn->components) {
 923                         talloc_free(new_dn);
 924                         return NULL;
 925                 }
 926
 927                 for (i = 0; i < dn->comp_num; i++) {
 928                         new_dn->components[i] = ldb_dn_copy_component(new_dn->components, &dn->components[i]);
 929                         if ( ! new_dn->components[i].value.data) {
 930                                 talloc_free(new_dn);
 931                                 return NULL;
 932                         }
 933                 }
 934         }
 935
 936         if (dn->casefold) {
 937                 new_dn->casefold = talloc_strdup(new_dn, dn->casefold);
 938                 if ( ! new_dn->casefold) {
 939                         talloc_free(new_dn);
 940                         return NULL;
 941                 }
 942         }
 943
 944         if (dn->linearized) {
 945                 new_dn->linearized = talloc_strdup(new_dn, dn->linearized);
 946                 if ( ! new_dn->linearized) {
 947                         talloc_free(new_dn);
 948                         return NULL;
 949                 }
 950         }
 951
 952         return new_dn;
 953 }
 954
 955 /* modify the given dn by adding a base.
 956  *
 957  * return true if successful and false if not
 958  * if false is returned the dn may be marked invalid
 959  */
 960 bool ldb_dn_add_base(struct ldb_dn *dn, struct ldb_dn *base)
 961 {
 962         const char *s;
 963         char *t;
 964
 965         if ( !base || base->invalid || !dn || dn->invalid) {
 966                 return false;
 967         }
 968
 969         if (dn->components) {
 970                 int i;
 971
 972                 if ( ! ldb_dn_validate(base)) {
 973                         return false;
 974                 }
 975
 976                 s = NULL;
 977                 if (dn->valid_case) {
 978                         if ( ! (s = ldb_dn_get_casefold(base))) {
 979                                 return false;
 980                         }
 981                 }
 982
 983                 dn->components = talloc_realloc(dn,
 984                                                 dn->components,
 985                                                 struct ldb_dn_component,
 986                                                 dn->comp_num + base->comp_num);
 987                 if ( ! dn->components) {
 988                         dn->invalid = true;
 989                         return false;
 990                 }
 991
 992                 for (i = 0; i < base->comp_num; dn->comp_num++, i++) {
 993                         dn->components[dn->comp_num] = ldb_dn_copy_component(dn->components, &base->components[i]);
 994                         if (dn->components[dn->comp_num].value.data == NULL) {
 995                                 dn->invalid = true;
 996                                 return false;
 997                         }
 998                 }
 999
1000                 if (dn->casefold && s) {
1001                         if (*dn->casefold) {
1002                                 t = talloc_asprintf(dn, "%s,%s", dn->casefold, s);
1003                         } else {
1004                                 t = talloc_strdup(dn, s);
1005                         }
1006                         LDB_FREE(dn->casefold);
1007                         dn->casefold = t;
1008                 }
1009         }
1010
1011         if (dn->linearized) {
1012
1013                 s = ldb_dn_get_linearized(base);
1014                 if ( ! s) {
1015                         return false;
1016                 }
1017
1018                 if (*dn->linearized) {
1019                         t = talloc_asprintf(dn, "%s,%s", dn->linearized, s);
1020                 } else {
1021                         t = talloc_strdup(dn, s);
1022                 }
1023                 if ( ! t) {
1024                         dn->invalid = true;
1025                         return false;
1026                 }
1027                 LDB_FREE(dn->linearized);
1028                 dn->linearized = t;
1029         }
1030
1031         return true;
1032 }
1033
1034 /* modify the given dn by adding a base.
1035  *
1036  * return true if successful and false if not
1037  * if false is returned the dn may be marked invalid
1038  */
1039 bool ldb_dn_add_base_fmt(struct ldb_dn *dn, const char *base_fmt, ...)
1040 {
1041         struct ldb_dn *base;
1042         char *base_str;
1043         va_list ap;
1044         bool ret;
1045
1046         if ( !dn || dn->invalid) {
1047                 return false;
1048         }
1049
1050         va_start(ap, base_fmt);
1051         base_str = talloc_vasprintf(dn, base_fmt, ap);
1052         va_end(ap);
1053
1054         if (base_str == NULL) {
1055                 return false;
1056         }
1057
1058         base = ldb_dn_new(base_str, dn->ldb, base_str);
1059
1060         ret = ldb_dn_add_base(dn, base);
1061
1062         talloc_free(base_str);
1063
1064         return ret;
1065 }
1066
1067 /* modify the given dn by adding children elements.
1068  *
1069  * return true if successful and false if not
1070  * if false is returned the dn may be marked invalid
1071  */
1072 bool ldb_dn_add_child(struct ldb_dn *dn, struct ldb_dn *child)
1073 {
1074         const char *s;
1075         char *t;
1076
1077         if ( !child || child->invalid || !dn || dn->invalid) {
1078                 return false;
1079         }
1080
1081         if (dn->components) {
1082                 int n, i, j;
1083
1084                 if ( ! ldb_dn_validate(child)) {
1085                         return false;
1086                 }
1087
1088                 s = NULL;
1089                 if (dn->valid_case) {
1090                         if ( ! (s = ldb_dn_get_casefold(child))) {
1091                                 return false;
1092                         }
1093                 }
1094
1095                 n = dn->comp_num + child->comp_num;
1096
1097                 dn->components = talloc_realloc(dn,
1098                                                 dn->components,
1099                                                 struct ldb_dn_component,
1100                                                 n);
1101                 if ( ! dn->components) {
1102                         dn->invalid = true;
1103                         return false;
1104                 }
1105
1106                 for (i = dn->comp_num - 1, j = n - 1; i >= 0; i--, j--) {
1107                         dn->components[j] = dn->components[i];
1108                 }
1109
1110                 for (i = 0; i < child->comp_num; i++) {
1111                         dn->components[i] = ldb_dn_copy_component(dn->components, &child->components[i]);
1112                         if (dn->components[i].value.data == NULL) {
1113                                 dn->invalid = true;
1114                                 return false;
1115                         }
1116                 }
1117
1118                 dn->comp_num = n;
1119
1120                 if (dn->casefold && s) {
1121                         t = talloc_asprintf(dn, "%s,%s", s, dn->casefold);
1122                         LDB_FREE(dn->casefold);
1123                         dn->casefold = t;
1124                 }
1125         }
1126
1127         if (dn->linearized) {
1128
1129                 s = ldb_dn_get_linearized(child);
1130                 if ( ! s) {
1131                         return false;
1132                 }
1133
1134                 t = talloc_asprintf(dn, "%s,%s", s, dn->linearized);
1135                 if ( ! t) {
1136                         dn->invalid = true;
1137                         return false;
1138                 }
1139                 LDB_FREE(dn->linearized);
1140                 dn->linearized = t;
1141         }
1142
1143         return true;
1144 }
1145
1146 /* modify the given dn by adding children elements.
1147  *
1148  * return true if successful and false if not
1149  * if false is returned the dn may be marked invalid
1150  */
1151 bool ldb_dn_add_child_fmt(struct ldb_dn *dn, const char *child_fmt, ...)
1152 {
1153         struct ldb_dn *child;
1154         char *child_str;
1155         va_list ap;
1156         bool ret;
1157
1158         if ( !dn || dn->invalid) {
1159                 return false;
1160         }
1161
1162         va_start(ap, child_fmt);
1163         child_str = talloc_vasprintf(dn, child_fmt, ap);
1164         va_end(ap);
1165
1166         if (child_str == NULL) {
1167                 return false;
1168         }
1169
1170         child = ldb_dn_new(child_str, dn->ldb, child_str);
1171
1172         ret = ldb_dn_add_child(dn, child);
1173
1174         talloc_free(child_str);
1175
1176         return ret;
1177 }
1178
1179 bool ldb_dn_remove_base_components(struct ldb_dn *dn, unsigned int num)
1180 {
1181         int i;
1182
1183         if ( ! ldb_dn_validate(dn)) {
1184                 return false;
1185         }
1186
1187         if (dn->comp_num < num) {
1188                 return false;
1189         }
1190
1191         /* free components */
1192         for (i = num; i > 0; i--) {
1193                 LDB_FREE(dn->components[dn->comp_num - i].name);
1194                 LDB_FREE(dn->components[dn->comp_num - i].value.data);
1195                 LDB_FREE(dn->components[dn->comp_num - i].cf_name);
1196                 LDB_FREE(dn->components[dn->comp_num - i].cf_value.data);
1197         }
1198
1199         dn->comp_num -= num;
1200
1201         if (dn->valid_case) {
1202                 for (i = 0; i < dn->comp_num; i++) {
1203                         LDB_FREE(dn->components[i].cf_name);
1204                         LDB_FREE(dn->components[i].cf_value.data);
1205                 }
1206                 dn->valid_case = false;
1207         }
1208
1209         LDB_FREE(dn->casefold);
1210         LDB_FREE(dn->linearized);
1211
1212         return true;
1213 }
1214
1215 bool ldb_dn_remove_child_components(struct ldb_dn *dn, unsigned int num)
1216 {
1217         int i, j;
1218
1219         if ( ! ldb_dn_validate(dn)) {
1220                 return false;
1221         }
1222
1223         if (dn->comp_num < num) {
1224                 return false;
1225         }
1226
1227         for (i = 0, j = num; j < dn->comp_num; i++, j++) {
1228                 if (i < num) {
1229                         LDB_FREE(dn->components[i].name);
1230                         LDB_FREE(dn->components[i].value.data);
1231                         LDB_FREE(dn->components[i].cf_name);
1232                         LDB_FREE(dn->components[i].cf_value.data);
1233                 }
1234                 dn->components[i] = dn->components[j];
1235         }
1236
1237         dn->comp_num -= num;
1238
1239         if (dn->valid_case) {
1240                 for (i = 0; i < dn->comp_num; i++) {
1241                         LDB_FREE(dn->components[i].cf_name);
1242                         LDB_FREE(dn->components[i].cf_value.data);
1243                 }
1244                 dn->valid_case = false;
1245         }
1246
1247         LDB_FREE(dn->casefold);
1248         LDB_FREE(dn->linearized);
1249
1250         return true;
1251 }
1252
1253 struct ldb_dn *ldb_dn_get_parent(void *mem_ctx, struct ldb_dn *dn)
1254 {
1255         struct ldb_dn *new_dn;
1256
1257         new_dn = ldb_dn_copy(mem_ctx, dn);
1258         if ( !new_dn ) {
1259                 return NULL;
1260         }
1261
1262         if ( ! ldb_dn_remove_child_components(new_dn, 1)) {
1263                 talloc_free(new_dn);
1264                 return NULL;
1265         }
1266
1267         return new_dn;
1268 }
1269
1270 /* Create a 'canonical name' string from a DN:
1271
1272    ie dc=samba,dc=org -> samba.org/
1273       uid=administrator,ou=users,dc=samba,dc=org = samba.org/users/administrator
1274
1275    There are two formats, the EX format has the last / replaced with a newline (\n).
1276
1277 */
1278 static char *ldb_dn_canonical(void *mem_ctx, struct ldb_dn *dn, int ex_format) {
1279         int i;
1280         TALLOC_CTX *tmpctx;
1281         char *cracked = NULL;
1282
1283         if ( ! ldb_dn_validate(dn)) {
1284                 return NULL;
1285         }
1286
1287         tmpctx = talloc_new(mem_ctx);
1288
1289         /* Walk backwards down the DN, grabbing 'dc' components at first */
1290         for (i = dn->comp_num - 1 ; i >= 0; i--) {
1291                 if (ldb_attr_cmp(dn->components[i].name, "dc") != 0) {
1292                         break;
1293                 }
1294                 if (cracked) {
1295                         cracked = talloc_asprintf(tmpctx, "%s.%s",
1296                                                   ldb_dn_escape_value(tmpctx, dn->components[i].value),
1297                                                   cracked);
1298                 } else {
1299                         cracked = ldb_dn_escape_value(tmpctx, dn->components[i].value);
1300                 }
1301                 if (!cracked) {
1302                         goto done;
1303                 }
1304         }
1305
1306         /* Only domain components?  Finish here */
1307         if (i < 0) {
1308                 if (ex_format) {
1309                         cracked = talloc_append_string(tmpctx, cracked, "\n");
1310                 } else {
1311                         cracked = talloc_append_string(tmpctx, cracked, "/");
1312                 }
1313                 talloc_steal(mem_ctx, cracked);
1314                 goto done;
1315         }
1316
1317         /* Now walk backwards appending remaining components */
1318         for (; i > 0; i--) {
1319                 cracked = talloc_asprintf_append(cracked, "/%s",
1320                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1321                 if (!cracked) {
1322                         goto done;
1323                 }
1324         }
1325
1326         /* Last one, possibly a newline for the 'ex' format */
1327         if (ex_format) {
1328                 cracked = talloc_asprintf_append(cracked, "\n%s",
1329                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1330         } else {
1331                 cracked = talloc_asprintf_append(cracked, "/%s",
1332                                           ldb_dn_escape_value(tmpctx, dn->components[i].value));
1333         }
1334
1335         talloc_steal(mem_ctx, cracked);
1336 done:
1337         talloc_free(tmpctx);
1338         return cracked;
1339 }
1340
1341 /* Wrapper functions for the above, for the two different string formats */
1342 char *ldb_dn_canonical_string(void *mem_ctx, struct ldb_dn *dn) {
1343         return ldb_dn_canonical(mem_ctx, dn, 0);
1344
1345 }
1346
1347 char *ldb_dn_canonical_ex_string(void *mem_ctx, struct ldb_dn *dn) {
1348         return ldb_dn_canonical(mem_ctx, dn, 1);
1349 }
1350
1351 int ldb_dn_get_comp_num(struct ldb_dn *dn)
1352 {
1353         if ( ! ldb_dn_validate(dn)) {
1354                 return -1;
1355         }
1356         return dn->comp_num;
1357 }
1358
1359 const char *ldb_dn_get_component_name(struct ldb_dn *dn, unsigned int num)
1360 {
1361         if ( ! ldb_dn_validate(dn)) {
1362                 return NULL;
1363         }
1364         if (num >= dn->comp_num) return NULL;
1365         return dn->components[num].name;
1366 }
1367
1368 const struct ldb_val *ldb_dn_get_component_val(struct ldb_dn *dn, unsigned int num)
1369 {
1370         if ( ! ldb_dn_validate(dn)) {
1371                 return NULL;
1372         }
1373         if (num >= dn->comp_num) return NULL;
1374         return &dn->components[num].value;
1375 }
1376
1377 const char *ldb_dn_get_rdn_name(struct ldb_dn *dn)
1378 {
1379         if ( ! ldb_dn_validate(dn)) {
1380                 return NULL;
1381         }
1382         if (dn->comp_num == 0) return NULL;
1383         return dn->components[0].name;
1384 }
1385
1386 const struct ldb_val *ldb_dn_get_rdn_val(struct ldb_dn *dn)
1387 {
1388         if ( ! ldb_dn_validate(dn)) {
1389                 return NULL;
1390         }
1391         if (dn->comp_num == 0) return NULL;
1392         return &dn->components[0].value;
1393 }
1394
1395 int ldb_dn_set_component(struct ldb_dn *dn, int num, const char *name, const struct ldb_val val)
1396 {
1397         char *n;
1398         struct ldb_val v;
1399
1400         if ( ! ldb_dn_validate(dn)) {
1401                 return LDB_ERR_OTHER;
1402         }
1403
1404         if (num >= dn->comp_num) {
1405                 return LDB_ERR_OTHER;
1406         }
1407
1408         n = talloc_strdup(dn, name);
1409         if ( ! n) {
1410                 return LDB_ERR_OTHER;
1411         }
1412
1413         v.length = val.length;
1414         v.data = (uint8_t *)talloc_memdup(dn, val.data, v.length+1);
1415         if ( ! v.data) {
1416                 talloc_free(n);
1417                 return LDB_ERR_OTHER;
1418         }
1419
1420         talloc_free(dn->components[num].name);
1421         talloc_free(dn->components[num].value.data);
1422         dn->components[num].name = n;
1423         dn->components[num].value = v;
1424
1425         if (dn->valid_case) {
1426                 int i;
1427                 for (i = 0; i < dn->comp_num; i++) {
1428                         LDB_FREE(dn->components[i].cf_name);
1429                         LDB_FREE(dn->components[i].cf_value.data);
1430                 }
1431                 dn->valid_case = false;
1432         }
1433         LDB_FREE(dn->casefold);
1434         LDB_FREE(dn->linearized);
1435
1436         return LDB_SUCCESS;
1437 }
1438
1439 bool ldb_dn_is_valid(struct ldb_dn *dn)
1440 {
1441         if ( ! dn) return false;
1442         return ! dn->invalid;
1443 }
1444
1445 bool ldb_dn_is_special(struct ldb_dn *dn)
1446 {
1447         if ( ! dn || dn->invalid) return false;
1448         return dn->special;
1449 }
1450
1451 bool ldb_dn_check_special(struct ldb_dn *dn, const char *check)
1452 {
1453         if ( ! dn || dn->invalid) return false;
1454         return ! strcmp(dn->linearized, check);
1455 }
1456
1457 bool ldb_dn_is_null(struct ldb_dn *dn)
1458 {
1459         if ( ! dn || dn->invalid) return false;
1460         if (dn->linearized && (dn->linearized[0] == '\0')) return true;
1461         return false;
1462 }