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