contrib/subversion/subversion/libsvn_delta/element.c

   1 /*
   2  * element.c :  editing trees of versioned resources
   3  *
   4  * ====================================================================
   5  *    Licensed to the Apache Software Foundation (ASF) under one
   6  *    or more contributor license agreements.  See the NOTICE file
   7  *    distributed with this work for additional information
   8  *    regarding copyright ownership.  The ASF licenses this file
   9  *    to you under the Apache License, Version 2.0 (the
  10  *    "License"); you may not use this file except in compliance
  11  *    with the License.  You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  *    Unless required by applicable law or agreed to in writing,
  16  *    software distributed under the License is distributed on an
  17  *    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  18  *    KIND, either express or implied.  See the License for the
  19  *    specific language governing permissions and limitations
  20  *    under the License.
  21  * ====================================================================
  22  */
  23
  24 #include <assert.h>
  25 #include <apr_pools.h>
  26
  27 #include "svn_types.h"
  28 #include "svn_error.h"
  29 #include "svn_string.h"
  30 #include "svn_props.h"
  31 #include "svn_dirent_uri.h"
  32 #include "svn_iter.h"
  33 #include "private/svn_sorts_private.h"
  34
  35 #include "private/svn_element.h"
  36 #include "svn_private_config.h"
  37
  38
  39 void *
  40 svn_eid__hash_get(apr_hash_t *ht,
  41                   int key)
  42 {
  43   return apr_hash_get(ht, &key, sizeof(key));
  44 }
  45
  46 void
  47 svn_eid__hash_set(apr_hash_t *ht,
  48                   int key,
  49                   const void *val)
  50 {
  51   int *id_p = apr_pmemdup(apr_hash_pool_get(ht), &key, sizeof(key));
  52
  53   apr_hash_set(ht, id_p, sizeof(key), val);
  54 }
  55
  56 int
  57 svn_eid__hash_this_key(apr_hash_index_t *hi)
  58 {
  59   return *(const int *)apr_hash_this_key(hi);
  60 }
  61
  62 svn_eid__hash_iter_t *
  63 svn_eid__hash_sorted_first(apr_pool_t *pool,
  64                            apr_hash_t *ht,
  65                            int (*comparison_func)(const svn_sort__item_t *,
  66                                                   const svn_sort__item_t *))
  67 {
  68   svn_eid__hash_iter_t *hi = apr_palloc(pool, sizeof(*hi));
  69
  70   if (apr_hash_count(ht) == 0)
  71     return NULL;
  72
  73   hi->array = svn_sort__hash(ht, comparison_func, pool);
  74   hi->i = 0;
  75   hi->eid = *(const int *)(APR_ARRAY_IDX(hi->array, hi->i,
  76                                          svn_sort__item_t).key);
  77   hi->val = APR_ARRAY_IDX(hi->array, hi->i, svn_sort__item_t).value;
  78   return hi;
  79 }
  80
  81 svn_eid__hash_iter_t *
  82 svn_eid__hash_sorted_next(svn_eid__hash_iter_t *hi)
  83 {
  84   hi->i++;
  85   if (hi->i >= hi->array->nelts)
  86     {
  87       return NULL;
  88     }
  89   hi->eid = *(const int *)(APR_ARRAY_IDX(hi->array, hi->i,
  90                                          svn_sort__item_t).key);
  91   hi->val = APR_ARRAY_IDX(hi->array, hi->i, svn_sort__item_t).value;
  92   return hi;
  93 }
  94
  95 int
  96 svn_eid__hash_sort_compare_items_by_eid(const svn_sort__item_t *a,
  97                                         const svn_sort__item_t *b)
  98 {
  99   int eid_a = *(const int *)a->key;
 100   int eid_b = *(const int *)b->key;
 101
 102   return eid_a - eid_b;
 103 }
 104
 105
 106 /*
 107  * ===================================================================
 108  * Element payload
 109  * ===================================================================
 110  */
 111
 112 svn_boolean_t
 113 svn_element__payload_invariants(const svn_element__payload_t *payload)
 114 {
 115   if (payload->is_subbranch_root)
 116     return TRUE;
 117
 118   /* If kind is unknown, it's a reference; otherwise it has content
 119      specified and may also have a reference. */
 120   if (payload->kind == svn_node_unknown)
 121     if (SVN_IS_VALID_REVNUM(payload->branch_ref.rev)
 122         && payload->branch_ref.branch_id
 123         && payload->branch_ref.eid != -1)
 124       return TRUE;
 125   if ((payload->kind == svn_node_dir
 126        || payload->kind == svn_node_file
 127        || payload->kind == svn_node_symlink)
 128       && (payload->props
 129           && ((payload->kind == svn_node_file) == !!payload->text)
 130           && ((payload->kind == svn_node_symlink) == !!payload->target)))
 131     return TRUE;
 132   return FALSE;
 133 }
 134
 135 svn_element__payload_t *
 136 svn_element__payload_dup(const svn_element__payload_t *old,
 137                          apr_pool_t *result_pool)
 138 {
 139   svn_element__payload_t *new_payload;
 140
 141   assert(! old || svn_element__payload_invariants(old));
 142
 143   if (old == NULL)
 144     return NULL;
 145
 146   new_payload = apr_pmemdup(result_pool, old, sizeof(*new_payload));
 147   if (old->branch_ref.branch_id)
 148     new_payload->branch_ref.branch_id
 149       = apr_pstrdup(result_pool, old->branch_ref.branch_id);
 150   if (old->props)
 151     new_payload->props = svn_prop_hash_dup(old->props, result_pool);
 152   if (old->kind == svn_node_file && old->text)
 153     new_payload->text = svn_stringbuf_dup(old->text, result_pool);
 154   if (old->kind == svn_node_symlink && old->target)
 155     new_payload->target = apr_pstrdup(result_pool, old->target);
 156   return new_payload;
 157 }
 158
 159 svn_boolean_t
 160 svn_element__payload_equal(const svn_element__payload_t *left,
 161                            const svn_element__payload_t *right,
 162                            apr_pool_t *scratch_pool)
 163 {
 164   apr_array_header_t *prop_diffs;
 165
 166   assert(svn_element__payload_invariants(left));
 167   assert(svn_element__payload_invariants(right));
 168
 169   /* any two subbranch-root elements compare equal */
 170   if (left->is_subbranch_root && right->is_subbranch_root)
 171     {
 172       return TRUE;
 173     }
 174   else if (left->is_subbranch_root || right->is_subbranch_root)
 175     {
 176       return FALSE;
 177     }
 178
 179   /* content defined only by reference is not supported */
 180   SVN_ERR_ASSERT_NO_RETURN(left->kind != svn_node_unknown
 181                            && right->kind != svn_node_unknown);
 182
 183   if (left->kind != right->kind)
 184     {
 185       return FALSE;
 186     }
 187
 188   svn_error_clear(svn_prop_diffs(&prop_diffs,
 189                                  left->props, right->props,
 190                                  scratch_pool));
 191
 192   if (prop_diffs->nelts != 0)
 193     {
 194       return FALSE;
 195     }
 196   switch (left->kind)
 197     {
 198     case svn_node_dir:
 199       break;
 200     case svn_node_file:
 201       if (! svn_stringbuf_compare(left->text, right->text))
 202         {
 203           return FALSE;
 204         }
 205       break;
 206     case svn_node_symlink:
 207       if (strcmp(left->target, right->target) != 0)
 208         {
 209           return FALSE;
 210         }
 211       break;
 212     default:
 213       break;
 214     }
 215
 216   return TRUE;
 217 }
 218
 219 svn_element__payload_t *
 220 svn_element__payload_create_subbranch(apr_pool_t *result_pool)
 221 {
 222   svn_element__payload_t *new_payload
 223     = apr_pcalloc(result_pool, sizeof(*new_payload));
 224
 225   new_payload->pool = result_pool;
 226   new_payload->is_subbranch_root = TRUE;
 227   assert(svn_element__payload_invariants(new_payload));
 228   return new_payload;
 229 }
 230
 231 svn_element__payload_t *
 232 svn_element__payload_create_ref(svn_revnum_t rev,
 233                                 const char *branch_id,
 234                                 int eid,
 235                                 apr_pool_t *result_pool)
 236 {
 237   svn_element__payload_t *new_payload
 238     = apr_pcalloc(result_pool, sizeof(*new_payload));
 239
 240   new_payload->pool = result_pool;
 241   new_payload->kind = svn_node_unknown;
 242   new_payload->branch_ref.rev = rev;
 243   new_payload->branch_ref.branch_id = apr_pstrdup(result_pool, branch_id);
 244   new_payload->branch_ref.eid = eid;
 245   assert(svn_element__payload_invariants(new_payload));
 246   return new_payload;
 247 }
 248
 249 svn_element__payload_t *
 250 svn_element__payload_create_dir(apr_hash_t *props,
 251                                 apr_pool_t *result_pool)
 252 {
 253   svn_element__payload_t *new_payload
 254     = apr_pcalloc(result_pool, sizeof(*new_payload));
 255
 256   new_payload->pool = result_pool;
 257   new_payload->kind = svn_node_dir;
 258   new_payload->props = props ? svn_prop_hash_dup(props, result_pool) : NULL;
 259   assert(svn_element__payload_invariants(new_payload));
 260   return new_payload;
 261 }
 262
 263 svn_element__payload_t *
 264 svn_element__payload_create_file(apr_hash_t *props,
 265                                  svn_stringbuf_t *text,
 266                                  apr_pool_t *result_pool)
 267 {
 268   svn_element__payload_t *new_payload
 269     = apr_pcalloc(result_pool, sizeof(*new_payload));
 270
 271   SVN_ERR_ASSERT_NO_RETURN(text);
 272
 273   new_payload->pool = result_pool;
 274   new_payload->kind = svn_node_file;
 275   new_payload->props = props ? svn_prop_hash_dup(props, result_pool) : NULL;
 276   new_payload->text = svn_stringbuf_dup(text, result_pool);
 277   assert(svn_element__payload_invariants(new_payload));
 278   return new_payload;
 279 }
 280
 281 svn_element__payload_t *
 282 svn_element__payload_create_symlink(apr_hash_t *props,
 283                                     const char *target,
 284                                     apr_pool_t *result_pool)
 285 {
 286   svn_element__payload_t *new_payload
 287     = apr_pcalloc(result_pool, sizeof(*new_payload));
 288
 289   SVN_ERR_ASSERT_NO_RETURN(target);
 290
 291   new_payload->pool = result_pool;
 292   new_payload->kind = svn_node_symlink;
 293   new_payload->props = props ? svn_prop_hash_dup(props, result_pool) : NULL;
 294   new_payload->target = apr_pstrdup(result_pool, target);
 295   assert(svn_element__payload_invariants(new_payload));
 296   return new_payload;
 297 }
 298
 299 svn_element__content_t *
 300 svn_element__content_create(int parent_eid,
 301                             const char *name,
 302                             const svn_element__payload_t *payload,
 303                             apr_pool_t *result_pool)
 304 {
 305   svn_element__content_t *content
 306      = apr_palloc(result_pool, sizeof(*content));
 307
 308   content->parent_eid = parent_eid;
 309   content->name = apr_pstrdup(result_pool, name);
 310   content->payload = svn_element__payload_dup(payload, result_pool);
 311   return content;
 312 }
 313
 314 svn_element__content_t *
 315 svn_element__content_dup(const svn_element__content_t *old,
 316                          apr_pool_t *result_pool)
 317 {
 318   svn_element__content_t *content
 319      = apr_pmemdup(result_pool, old, sizeof(*content));
 320
 321   content->name = apr_pstrdup(result_pool, old->name);
 322   content->payload = svn_element__payload_dup(old->payload, result_pool);
 323   return content;
 324 }
 325
 326 svn_boolean_t
 327 svn_element__content_equal(const svn_element__content_t *content_left,
 328                            const svn_element__content_t *content_right,
 329                            apr_pool_t *scratch_pool)
 330 {
 331   if (!content_left && !content_right)
 332     {
 333       return TRUE;
 334     }
 335   else if (!content_left || !content_right)
 336     {
 337       return FALSE;
 338     }
 339
 340   if (content_left->parent_eid != content_right->parent_eid)
 341     {
 342       return FALSE;
 343     }
 344   if (strcmp(content_left->name, content_right->name) != 0)
 345     {
 346       return FALSE;
 347     }
 348   if (! svn_element__payload_equal(content_left->payload, content_right->payload,
 349                                    scratch_pool))
 350     {
 351       return FALSE;
 352     }
 353
 354   return TRUE;
 355 }
 356
 357 svn_element__tree_t *
 358 svn_element__tree_create(apr_hash_t *e_map,
 359                          int root_eid,
 360                          apr_pool_t *result_pool)
 361 {
 362   svn_element__tree_t *element_tree
 363     = apr_pcalloc(result_pool, sizeof(*element_tree));
 364
 365   element_tree->e_map = e_map ? apr_hash_copy(result_pool, e_map)
 366                               : apr_hash_make(result_pool);
 367   element_tree->root_eid = root_eid;
 368   return element_tree;
 369 }
 370
 371 svn_element__content_t *
 372 svn_element__tree_get(const svn_element__tree_t *tree,
 373                       int eid)
 374 {
 375   return svn_eid__hash_get(tree->e_map, eid);
 376 }
 377
 378 svn_error_t *
 379 svn_element__tree_set(svn_element__tree_t *tree,
 380                       int eid,
 381                       const svn_element__content_t *element)
 382 {
 383   svn_eid__hash_set(tree->e_map, eid, element);
 384
 385   return SVN_NO_ERROR;
 386 }
 387
 388 void
 389 svn_element__tree_purge_orphans(apr_hash_t *e_map,
 390                                 int root_eid,
 391                                 apr_pool_t *scratch_pool)
 392 {
 393   apr_hash_index_t *hi;
 394   svn_boolean_t changed;
 395
 396   SVN_ERR_ASSERT_NO_RETURN(svn_eid__hash_get(e_map, root_eid));
 397
 398   do
 399     {
 400       changed = FALSE;
 401
 402       for (hi = apr_hash_first(scratch_pool, e_map);
 403            hi; hi = apr_hash_next(hi))
 404         {
 405           int this_eid = svn_eid__hash_this_key(hi);
 406           svn_element__content_t *this_element = apr_hash_this_val(hi);
 407
 408           if (this_eid != root_eid)
 409             {
 410               svn_element__content_t *parent_element
 411                 = svn_eid__hash_get(e_map, this_element->parent_eid);
 412
 413               /* Purge if parent is deleted */
 414               if (! parent_element)
 415                 {
 416                   svn_eid__hash_set(e_map, this_eid, NULL);
 417                   changed = TRUE;
 418                 }
 419               else
 420                 SVN_ERR_ASSERT_NO_RETURN(
 421                   ! parent_element->payload->is_subbranch_root);
 422             }
 423         }
 424     }
 425   while (changed);
 426 }
 427
 428 const char *
 429 svn_element__tree_get_path_by_eid(const svn_element__tree_t *tree,
 430                                   int eid,
 431                                   apr_pool_t *result_pool)
 432 {
 433   const char *path = "";
 434   svn_element__content_t *element;
 435
 436   for (; eid != tree->root_eid; eid = element->parent_eid)
 437     {
 438       element = svn_element__tree_get(tree, eid);
 439       if (! element)
 440         return NULL;
 441       path = svn_relpath_join(element->name, path, result_pool);
 442     }
 443   SVN_ERR_ASSERT_NO_RETURN(eid == tree->root_eid);
 444   return path;
 445 }
 446
 447 svn_element__tree_t *
 448 svn_element__tree_get_subtree_at_eid(svn_element__tree_t *element_tree,
 449                                      int eid,
 450                                      apr_pool_t *result_pool)
 451 {
 452   svn_element__tree_t *new_subtree;
 453   svn_element__content_t *subtree_root_element;
 454
 455   new_subtree = svn_element__tree_create(element_tree->e_map, eid,
 456                                          result_pool);
 457
 458   /* Purge orphans */
 459   svn_element__tree_purge_orphans(new_subtree->e_map,
 460                                   new_subtree->root_eid, result_pool);
 461
 462   /* Remove 'parent' and 'name' attributes from subtree root element */
 463   subtree_root_element
 464     = svn_element__tree_get(new_subtree, new_subtree->root_eid);
 465   svn_element__tree_set(new_subtree, new_subtree->root_eid,
 466                         svn_element__content_create(
 467                           -1, "", subtree_root_element->payload, result_pool));
 468
 469   return new_subtree;
 470 }
 471