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