subversion/libsvn_fs_base/util/skel.c

   1 /* skel.c --- parsing and unparsing skeletons
   2  *
   3  * ====================================================================
   4  * Copyright (c) 2000-2004 CollabNet.  All rights reserved.
   5  *
   6  * This software is licensed as described in the file COPYING, which
   7  * you should have received as part of this distribution.  The terms
   8  * are also available at http://subversion.tigris.org/license-1.html.
   9  * If newer versions of this license are posted there, you may use a
  10  * newer version instead, at your option.
  11  *
  12  * This software consists of voluntary contributions made by many
  13  * individuals.  For exact contribution history, see the revision
  14  * history and logs, available at http://subversion.tigris.org/.
  15  * ====================================================================
  16  */
  17
  18 #include <string.h>
  19 #include "svn_string.h"
  20 #include "skel.h"
  21 #include "../key-gen.h"
  22
  23 \f
  24 /* Parsing skeletons.  */
  25
  26 enum char_type {
  27   type_nothing = 0,
  28   type_space = 1,
  29   type_digit = 2,
  30   type_paren = 3,
  31   type_name = 4
  32 };
  33
  34
  35 /* We can't use the <ctype.h> macros here, because they are locale-
  36    dependent.  The syntax of a skel is specified directly in terms of
  37    byte values, and is independent of locale.  */
  38
  39 static const enum char_type skel_char_type[256] = {
  40   0, 0, 0, 0, 0, 0, 0, 0,   0, 1, 1, 0, 1, 1, 0, 0,
  41   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  42   1, 0, 0, 0, 0, 0, 0, 0,   3, 3, 0, 0, 0, 0, 0, 0,
  43   2, 2, 2, 2, 2, 2, 2, 2,   2, 2, 0, 0, 0, 0, 0, 0,
  44
  45   /* 64 */
  46   0, 4, 4, 4, 4, 4, 4, 4,   4, 4, 4, 4, 4, 4, 4, 4,
  47   4, 4, 4, 4, 4, 4, 4, 4,   4, 4, 4, 3, 0, 3, 0, 0,
  48   0, 4, 4, 4, 4, 4, 4, 4,   4, 4, 4, 4, 4, 4, 4, 4,
  49   4, 4, 4, 4, 4, 4, 4, 4,   4, 4, 4, 0, 0, 0, 0, 0,
  50
  51   /* 128 */
  52   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  53   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  54   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  55   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  56
  57   /* 192 */
  58   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  59   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  60   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  61   0, 0, 0, 0, 0, 0, 0, 0,   0, 0, 0, 0, 0, 0, 0, 0,
  62 };
  63
  64
  65 static skel_t *parse(const char *data, apr_size_t len,
  66                      apr_pool_t *pool);
  67 static skel_t *list(const char *data, apr_size_t len,
  68                     apr_pool_t *pool);
  69 static skel_t *implicit_atom(const char *data, apr_size_t len,
  70                              apr_pool_t *pool);
  71 static skel_t *explicit_atom(const char *data, apr_size_t len,
  72                              apr_pool_t *pool);
  73
  74
  75 skel_t *
  76 svn_fs_base__parse_skel(const char *data,
  77                         apr_size_t len,
  78                         apr_pool_t *pool)
  79 {
  80   return parse(data, len, pool);
  81 }
  82
  83
  84 /* Parse any kind of skel object --- atom, or list.  */
  85 static skel_t *
  86 parse(const char *data,
  87       apr_size_t len,
  88       apr_pool_t *pool)
  89 {
  90   char c;
  91
  92   /* The empty string isn't a valid skel.  */
  93   if (len <= 0)
  94     return 0;
  95
  96   c = *data;
  97
  98   /* Is it a list, or an atom?  */
  99   if (c == '(')
 100     return list(data, len, pool);
 101
 102   /* Is it a string with an implicit length?  */
 103   if (skel_char_type[(unsigned char) c] == type_name)
 104     return implicit_atom(data, len, pool);
 105
 106   /* Otherwise, we assume it's a string with an explicit length;
 107      svn_fs_base__getsize will catch the error.  */
 108   else
 109     return explicit_atom(data, len, pool);
 110 }
 111
 112
 113 static skel_t *
 114 list(const char *data,
 115      apr_size_t len,
 116      apr_pool_t *pool)
 117 {
 118   const char *end = data + len;
 119   const char *list_start;
 120
 121   /* Verify that the list starts with an opening paren.  At the
 122      moment, all callers have checked this already, but it's more
 123      robust this way.  */
 124   if (data >= end || *data != '(')
 125     return 0;
 126
 127   /* Mark where the list starts.  */
 128   list_start = data;
 129
 130   /* Skip the opening paren.  */
 131   data++;
 132
 133   /* Parse the children.  */
 134   {
 135     skel_t *children = 0;
 136     skel_t **tail = &children;
 137
 138     for (;;)
 139       {
 140         skel_t *element;
 141
 142         /* Skip any whitespace.  */
 143         while (data < end
 144                && skel_char_type[(unsigned char) *data] == type_space)
 145           data++;
 146
 147         /* End of data, but no closing paren?  */
 148         if (data >= end)
 149           return 0;
 150
 151         /* End of list?  */
 152         if (*data == ')')
 153           {
 154             data++;
 155             break;
 156           }
 157
 158         /* Parse the next element in the list.  */
 159         element = parse(data, end - data, pool);
 160         if (! element)
 161           return 0;
 162
 163         /* Link that element into our list.  */
 164         element->next = 0;
 165         *tail = element;
 166         tail = &element->next;
 167
 168         /* Advance past that element.  */
 169         data = element->data + element->len;
 170       }
 171
 172     /* Construct the return value.  */
 173     {
 174       skel_t *s = apr_pcalloc(pool, sizeof(*s));
 175
 176       s->is_atom = FALSE;
 177       s->data = list_start;
 178       s->len = data - list_start;
 179       s->children = children;
 180
 181       return s;
 182     }
 183   }
 184 }
 185
 186
 187 /* Parse an atom with implicit length --- one that starts with a name
 188    character, terminated by whitespace, '(', ')', or end-of-data.  */
 189 static skel_t *
 190 implicit_atom(const char *data,
 191               apr_size_t len,
 192               apr_pool_t *pool)
 193 {
 194   const char *start = data;
 195   const char *end = data + len;
 196   skel_t *s;
 197
 198   /* Verify that the atom starts with a name character.  At the
 199      moment, all callers have checked this already, but it's more
 200      robust this way.  */
 201   if (data >= end || skel_char_type[(unsigned char) *data] != type_name)
 202     return 0;
 203
 204   /* Find the end of the string.  */
 205   while (++data < end
 206          && skel_char_type[(unsigned char) *data] != type_space
 207          && skel_char_type[(unsigned char) *data] != type_paren)
 208     ;
 209
 210   /* Allocate the skel representing this string.  */
 211   s = apr_pcalloc(pool, sizeof(*s));
 212   s->is_atom = TRUE;
 213   s->data = start;
 214   s->len = data - start;
 215
 216   return s;
 217 }
 218
 219
 220 /* Parse an atom with explicit length --- one that starts with a byte
 221    length, as a decimal ASCII number.  */
 222 static skel_t *
 223 explicit_atom(const char *data,
 224               apr_size_t len,
 225               apr_pool_t *pool)
 226 {
 227   const char *end = data + len;
 228   const char *next;
 229   apr_size_t size;
 230   skel_t *s;
 231
 232   /* Parse the length.  */
 233   size = svn_fs_base__getsize(data, end - data, &next, end - data);
 234   data = next;
 235
 236   /* Exit if we overflowed, or there wasn't a valid number there.  */
 237   if (! data)
 238     return 0;
 239
 240   /* Skip the whitespace character after the length.  */
 241   if (data >= end || skel_char_type[(unsigned char) *data] != type_space)
 242     return 0;
 243   data++;
 244
 245   /* Check the length.  */
 246   if (data + size > end)
 247     return 0;
 248
 249   /* Allocate the skel representing this string.  */
 250   s = apr_pcalloc(pool, sizeof(*s));
 251   s->is_atom = TRUE;
 252   s->data = data;
 253   s->len = size;
 254
 255   return s;
 256 }
 257
 258
 259 \f
 260 /* Unparsing skeletons.  */
 261
 262 static apr_size_t estimate_unparsed_size(skel_t *);
 263 static svn_stringbuf_t *unparse(skel_t *, svn_stringbuf_t *, apr_pool_t *);
 264
 265
 266 svn_stringbuf_t *
 267 svn_fs_base__unparse_skel(skel_t *skel, apr_pool_t *pool)
 268 {
 269   svn_stringbuf_t *str;
 270
 271   /* Allocate a string to hold the data.  */
 272   str = apr_palloc(pool, sizeof(*str));
 273   str->pool = pool;
 274   str->blocksize = estimate_unparsed_size(skel) + 200;
 275   str->data = apr_palloc(pool, str->blocksize);
 276   str->len = 0;
 277
 278   return unparse(skel, str, pool);
 279 }
 280
 281
 282 /* Return an estimate of the number of bytes that the external
 283    representation of SKEL will occupy.  Since reallocing is expensive
 284    in pools, it's worth trying to get the buffer size right the first
 285    time.  */
 286 static apr_size_t
 287 estimate_unparsed_size(skel_t *skel)
 288 {
 289   if (skel->is_atom)
 290     {
 291       if (skel->len < 100)
 292         /* If we have to use the explicit-length form, that'll be
 293            two bytes for the length, one byte for the space, and
 294            the contents.  */
 295         return skel->len + 3;
 296       else
 297         return skel->len + 30;
 298     }
 299   else
 300     {
 301       int total_len;
 302       skel_t *child;
 303
 304       /* Allow space for opening and closing parens, and a space
 305          between each pair of elements.  */
 306       total_len = 2;
 307       for (child = skel->children; child; child = child->next)
 308         total_len += estimate_unparsed_size(child) + 1;
 309
 310       return total_len;
 311     }
 312 }
 313
 314
 315 /* Return non-zero iff we should use the implicit-length form for SKEL.
 316    Assume that SKEL is an atom.  */
 317 static svn_boolean_t
 318 use_implicit(skel_t *skel)
 319 {
 320   /* If it's null, or long, we should use explicit-length form.  */
 321   if (skel->len == 0
 322       || skel->len >= 100)
 323     return FALSE;
 324
 325   /* If it doesn't start with a name character, we must use
 326      explicit-length form.  */
 327   if (skel_char_type[(unsigned char) skel->data[0]] != type_name)
 328     return FALSE;
 329
 330   /* If it contains any whitespace or parens, then we must use
 331      explicit-length form.  */
 332   {
 333     apr_size_t i;
 334
 335     for (i = 1; i < skel->len; i++)
 336       if (skel_char_type[(unsigned char) skel->data[i]] == type_space
 337           || skel_char_type[(unsigned char) skel->data[i]] == type_paren)
 338         return FALSE;
 339   }
 340
 341   /* If we can't reject it for any of the above reasons, then we can
 342      use implicit-length form.  */
 343   return TRUE;
 344 }
 345
 346
 347 /* Append the concrete representation of SKEL to the string STR.
 348    Grow S with new space from POOL as necessary.  */
 349 static svn_stringbuf_t *
 350 unparse(skel_t *skel, svn_stringbuf_t *str, apr_pool_t *pool)
 351 {
 352   if (skel->is_atom)
 353     {
 354       /* Append an atom to STR.  */
 355       if (use_implicit(skel))
 356         svn_stringbuf_appendbytes(str, skel->data, skel->len);
 357       else
 358         {
 359           /* Append the length to STR.  */
 360           char buf[200];
 361           int length_len;
 362
 363           length_len = svn_fs_base__putsize(buf, sizeof(buf), skel->len);
 364           if (! length_len)
 365             abort();
 366
 367           /* Make sure we have room for the length, the space, and the
 368              atom's contents.  */
 369           svn_stringbuf_ensure(str, str->len + length_len + 1 + skel->len);
 370           svn_stringbuf_appendbytes(str, buf, length_len);
 371           str->data[str->len++] = ' ';
 372           svn_stringbuf_appendbytes(str, skel->data, skel->len);
 373         }
 374     }
 375   else
 376     {
 377       /* Append a list to STR.  */
 378       skel_t *child;
 379
 380       /* Emit an opening parenthesis.  */
 381       svn_stringbuf_ensure(str, str->len + 1);
 382       str->data[str->len++] = '(';
 383
 384       /* Append each element.  Emit a space between each pair of elements.  */
 385       for (child = skel->children; child; child = child->next)
 386         {
 387           unparse(child, str, pool);
 388           if (child->next)
 389             {
 390               svn_stringbuf_ensure(str, str->len + 1);
 391               str->data[str->len++] = ' ';
 392             }
 393         }
 394
 395       /* Emit a closing parenthesis.  */
 396       svn_stringbuf_appendbytes(str, ")", 1);
 397     }
 398
 399   return str;
 400 }
 401
 402
 403 \f
 404 /* Building skels.  */
 405
 406
 407 skel_t *
 408 svn_fs_base__str_atom(const char *str, apr_pool_t *pool)
 409 {
 410   skel_t *skel = apr_pcalloc(pool, sizeof(*skel));
 411   skel->is_atom = TRUE;
 412   skel->data = str;
 413   skel->len = strlen(str);
 414
 415   return skel;
 416 }
 417
 418
 419 skel_t *
 420 svn_fs_base__mem_atom(const void *addr,
 421                       apr_size_t len,
 422                       apr_pool_t *pool)
 423 {
 424   skel_t *skel = apr_pcalloc(pool, sizeof(*skel));
 425   skel->is_atom = TRUE;
 426   skel->data = addr;
 427   skel->len = len;
 428
 429   return skel;
 430 }
 431
 432
 433 skel_t *
 434 svn_fs_base__make_empty_list(apr_pool_t *pool)
 435 {
 436   skel_t *skel = apr_pcalloc(pool, sizeof(*skel));
 437   return skel;
 438 }
 439
 440
 441 void
 442 svn_fs_base__prepend(skel_t *skel, skel_t *list_skel)
 443 {
 444   /* If list_skel isn't even a list, somebody's not using this
 445      function properly. */
 446   if (list_skel->is_atom)
 447     abort();
 448
 449   skel->next = list_skel->children;
 450   list_skel->children = skel;
 451 }
 452
 453
 454 void
 455 svn_fs_base__append(skel_t *skel, skel_t *list_skel)
 456 {
 457   /* If list_skel isn't even a list, somebody's not using this
 458      function properly. */
 459   if (list_skel->is_atom)
 460     abort();
 461
 462   /* No kids?  Let's make one. */
 463   if (! list_skel->children)
 464     {
 465       list_skel->children = skel;
 466     }
 467   else
 468     {
 469       skel_t *tmp = list_skel->children;
 470
 471       /* Find the last child... */
 472       while (tmp->next)
 473         {
 474           tmp = tmp->next;
 475         }
 476       /* ...and then give her a sister. */
 477       tmp->next = skel;
 478     }
 479 }
 480
 481
 482 \f
 483 /* Examining skels.  */
 484
 485
 486 svn_boolean_t
 487 svn_fs_base__matches_atom(skel_t *skel, const char *str)
 488 {
 489   if (skel && skel->is_atom)
 490     {
 491       apr_size_t len = strlen(str);
 492
 493       return ((skel->len == len
 494                && ! memcmp(skel->data, str, len)) ? TRUE : FALSE);
 495     }
 496   return FALSE;
 497 }
 498
 499
 500 int
 501 svn_fs_base__atom_matches_string(skel_t *skel, const svn_string_t *str)
 502 {
 503   if (skel && skel->is_atom)
 504     {
 505       return ((skel->len == str->len
 506                && ! memcmp(skel->data, str->data, skel->len)) ? TRUE : FALSE);
 507     }
 508   return FALSE;
 509 }
 510
 511
 512 int
 513 svn_fs_base__list_length(skel_t *skel)
 514 {
 515   int len = 0;
 516   skel_t *child;
 517
 518   if ((! skel) || skel->is_atom)
 519     return -1;
 520
 521   for (child = skel->children; child; child = child->next)
 522     len++;
 523
 524   return len;
 525 }
 526
 527
 528 \f
 529 /* Comparing skels. */
 530
 531 svn_boolean_t
 532 svn_fs_base__skels_are_equal(skel_t *skel1, skel_t *skel2)
 533 {
 534   if (skel1 == skel2)
 535     return TRUE;
 536
 537   /* Else not `eq', but might still be `equal'. */
 538
 539   if (skel1->is_atom && skel2->is_atom)
 540     {
 541       if ((skel1->len == skel2->len)
 542           && (! strncmp(skel1->data, skel2->data, skel1->len)))
 543         return TRUE;
 544       else
 545         return FALSE;
 546     }
 547   else if (((! skel1->is_atom) && (! skel2->is_atom))
 548            && ((svn_fs_base__list_length(skel1))
 549                == (svn_fs_base__list_length(skel2))))
 550     {
 551       int len = svn_fs_base__list_length(skel1);
 552       int i;
 553
 554       for (i = 0; i < len; i++)
 555         if (! svn_fs_base__skels_are_equal((skel1->children) + i,
 556                                            (skel2->children) + i))
 557           return FALSE;
 558
 559       return TRUE;
 560     }
 561   else
 562     return FALSE;
 563 }
 564
 565
 566 \f
 567 /* Copying skels.  */
 568
 569
 570 skel_t *
 571 svn_fs_base__copy_skel(skel_t *skel, apr_pool_t *pool)
 572 {
 573   skel_t *copy = apr_pcalloc(pool, sizeof(*copy));
 574
 575   if (skel->is_atom)
 576     {
 577       apr_size_t len = skel->len;
 578       char *s = apr_palloc(pool, len);
 579
 580       memcpy(s, skel->data, len);
 581       copy->is_atom = TRUE;
 582       copy->data = s;
 583       copy->len = len;
 584     }
 585   else
 586     {
 587       skel_t *skel_child, **copy_child_ptr;
 588
 589       copy->is_atom = FALSE;
 590       copy->data = 0;
 591       copy->len = 0;
 592
 593       copy_child_ptr = &copy->children;
 594       for (skel_child = skel->children;
 595            skel_child;
 596            skel_child = skel_child->next)
 597         {
 598           *copy_child_ptr = svn_fs_base__copy_skel(skel_child, pool);
 599           copy_child_ptr = &(*copy_child_ptr)->next;
 600         }
 601       *copy_child_ptr = 0;
 602     }
 603
 604   return copy;
 605 }