1 /* skel.c --- parsing and unparsing skeletons
3 * ====================================================================
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
12 * http://www.apache.org/licenses/LICENSE-2.0
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
20 * ====================================================================
24 #include "svn_string.h"
25 #include "svn_error.h"
26 #include "svn_props.h"
27 #include "svn_pools.h"
28 #include "private/svn_skel.h"
29 #include "private/svn_string_private.h"
32 /* Parsing skeletons. */
43 /* We can't use the <ctype.h> macros here, because they are locale-
44 dependent. The syntax of a skel is specified directly in terms of
45 byte values, and is independent of locale. */
47 static const enum char_type skel_char_type[256] = {
48 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0,
49 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
50 1, 0, 0, 0, 0, 0, 0, 0, 3, 3, 0, 0, 0, 0, 0, 0,
51 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0,
54 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
55 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 0, 3, 0, 0,
56 0, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
57 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 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 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
63 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
66 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
67 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
68 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
69 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
74 /* ### WTF? since when is number conversion LOCALE DEPENDENT? */
75 /* stsp: In C99, various numerical string properties such as decimal point,
76 * thousands separator, and the plus/minus sign are locale dependent. */
78 /* Converting text to numbers. */
80 /* Return the value of the string of digits at DATA as an ASCII
81 decimal number. The string is at most LEN bytes long. The value
82 of the number is at most MAX. Set *END to the address of the first
83 byte after the number, or zero if an error occurred while
84 converting the number (overflow, for example).
86 We would like to use strtoul, but that family of functions is
87 locale-dependent, whereas we're trying to parse data in a
88 locale-independent format. */
90 getsize(const char *data, apr_size_t len,
91 const char **endptr, apr_size_t max)
93 /* We can't detect overflow by simply comparing value against max,
94 since multiplying value by ten can overflow in strange ways if
95 max is close to the limits of apr_size_t. For example, suppose
96 that max is 54, and apr_size_t is six bits long; its range is
97 0..63. If we're parsing the number "502", then value will be 50
98 after parsing the first two digits. 50 * 10 = 500. But 500
99 doesn't fit in an apr_size_t, so it'll be truncated to 500 mod 64
100 = 52, which is less than max, so we'd fail to recognize the
101 overflow. Furthermore, it *is* greater than 50, so you can't
102 detect overflow by checking whether value actually increased
103 after each multiplication --- sometimes it does increase, but
106 So we do the check for overflow before we multiply value and add
108 apr_size_t max_prefix = max / 10;
109 apr_size_t max_digit = max % 10;
111 apr_size_t value = 0;
113 for (i = 0; i < len && '0' <= data[i] && data[i] <= '9'; i++)
115 apr_size_t digit = data[i] - '0';
117 /* Check for overflow. */
118 if (value > max_prefix
119 || (value == max_prefix && digit > max_digit))
125 value = (value * 10) + digit;
128 /* There must be at least one digit there. */
142 /* Checking validity of skels. */
144 skel_err(const char *skel_type)
146 return svn_error_createf(SVN_ERR_FS_MALFORMED_SKEL, NULL,
147 "Malformed%s%s skeleton",
148 skel_type ? " " : "",
149 skel_type ? skel_type : "");
154 is_valid_proplist_skel(const svn_skel_t *skel)
156 int len = svn_skel__list_length(skel);
158 if ((len >= 0) && (len & 1) == 0)
162 for (elt = skel->children; elt; elt = elt->next)
173 is_valid_iproplist_skel(const svn_skel_t *skel)
175 int len = svn_skel__list_length(skel);
177 if ((len >= 0) && (len & 1) == 0)
181 for (elt = skel->children; elt; elt = elt->next)
186 if (elt->next == NULL)
191 if (! is_valid_proplist_skel(elt))
202 static svn_skel_t *parse(const char *data, apr_size_t len,
204 static svn_skel_t *list(const char *data, apr_size_t len,
206 static svn_skel_t *implicit_atom(const char *data, apr_size_t len,
208 static svn_skel_t *explicit_atom(const char *data, apr_size_t len,
213 svn_skel__parse(const char *data,
217 return parse(data, len, pool);
221 /* Parse any kind of skel object --- atom, or list. */
223 parse(const char *data,
229 /* The empty string isn't a valid skel. */
235 /* Is it a list, or an atom? */
237 return list(data, len, pool);
239 /* Is it a string with an implicit length? */
240 if (skel_char_type[(unsigned char) c] == type_name)
241 return implicit_atom(data, len, pool);
243 /* Otherwise, we assume it's a string with an explicit length;
244 svn_skel__getsize will catch the error. */
246 return explicit_atom(data, len, pool);
251 list(const char *data,
255 const char *end = data + len;
256 const char *list_start;
258 /* Verify that the list starts with an opening paren. At the
259 moment, all callers have checked this already, but it's more
261 if (data >= end || *data != '(')
264 /* Mark where the list starts. */
267 /* Skip the opening paren. */
270 /* Parse the children. */
272 svn_skel_t *children = NULL;
273 svn_skel_t **tail = &children;
279 /* Skip any whitespace. */
281 && skel_char_type[(unsigned char) *data] == type_space)
284 /* End of data, but no closing paren? */
295 /* Parse the next element in the list. */
296 element = parse(data, end - data, pool);
300 /* Link that element into our list. */
301 element->next = NULL;
303 tail = &element->next;
305 /* Advance past that element. */
306 data = element->data + element->len;
309 /* Construct the return value. */
311 svn_skel_t *s = apr_pcalloc(pool, sizeof(*s));
314 s->data = list_start;
315 s->len = data - list_start;
316 s->children = children;
324 /* Parse an atom with implicit length --- one that starts with a name
325 character, terminated by whitespace, '(', ')', or end-of-data. */
327 implicit_atom(const char *data,
331 const char *start = data;
332 const char *end = data + len;
335 /* Verify that the atom starts with a name character. At the
336 moment, all callers have checked this already, but it's more
338 if (data >= end || skel_char_type[(unsigned char) *data] != type_name)
341 /* Find the end of the string. */
343 && skel_char_type[(unsigned char) *data] != type_space
344 && skel_char_type[(unsigned char) *data] != type_paren)
347 /* Allocate the skel representing this string. */
348 s = apr_pcalloc(pool, sizeof(*s));
351 s->len = data - start;
357 /* Parse an atom with explicit length --- one that starts with a byte
358 length, as a decimal ASCII number. */
360 explicit_atom(const char *data,
364 const char *end = data + len;
369 /* Parse the length. */
370 size = getsize(data, end - data, &next, end - data);
373 /* Exit if we overflowed, or there wasn't a valid number there. */
377 /* Skip the whitespace character after the length. */
378 if (data >= end || skel_char_type[(unsigned char) *data] != type_space)
382 /* Check the length. */
383 if (data + size > end)
386 /* Allocate the skel representing this string. */
387 s = apr_pcalloc(pool, sizeof(*s));
397 /* Unparsing skeletons. */
399 static apr_size_t estimate_unparsed_size(const svn_skel_t *skel);
400 static svn_stringbuf_t *unparse(const svn_skel_t *skel,
401 svn_stringbuf_t *str);
405 svn_skel__unparse(const svn_skel_t *skel, apr_pool_t *pool)
408 = svn_stringbuf_create_ensure(estimate_unparsed_size(skel) + 200, pool);
410 return unparse(skel, str);
414 /* Return an estimate of the number of bytes that the external
415 representation of SKEL will occupy. Since reallocing is expensive
416 in pools, it's worth trying to get the buffer size right the first
419 estimate_unparsed_size(const svn_skel_t *skel)
424 /* If we have to use the explicit-length form, that'll be
425 two bytes for the length, one byte for the space, and
427 return skel->len + 3;
429 return skel->len + 30;
433 apr_size_t total_len;
436 /* Allow space for opening and closing parens, and a space
437 between each pair of elements. */
439 for (child = skel->children; child; child = child->next)
440 total_len += estimate_unparsed_size(child) + 1;
447 /* Return non-zero iff we should use the implicit-length form for SKEL.
448 Assume that SKEL is an atom. */
450 use_implicit(const svn_skel_t *skel)
452 /* If it's null, or long, we should use explicit-length form. */
457 /* If it doesn't start with a name character, we must use
458 explicit-length form. */
459 if (skel_char_type[(unsigned char) skel->data[0]] != type_name)
462 /* If it contains any whitespace or parens, then we must use
463 explicit-length form. */
467 for (i = 1; i < skel->len; i++)
468 if (skel_char_type[(unsigned char) skel->data[i]] == type_space
469 || skel_char_type[(unsigned char) skel->data[i]] == type_paren)
473 /* If we can't reject it for any of the above reasons, then we can
474 use implicit-length form. */
479 /* Append the concrete representation of SKEL to the string STR. */
480 static svn_stringbuf_t *
481 unparse(const svn_skel_t *skel, svn_stringbuf_t *str)
485 /* Append an atom to STR. */
486 if (use_implicit(skel))
487 svn_stringbuf_appendbytes(str, skel->data, skel->len);
490 /* Append the length to STR. Ensure enough space for at least
492 char buf[200 + SVN_INT64_BUFFER_SIZE];
493 apr_size_t length_len;
495 length_len = svn__ui64toa(buf, skel->len);
497 SVN_ERR_ASSERT_NO_RETURN(length_len > 0);
499 /* Make sure we have room for the length, the space, and the
501 svn_stringbuf_ensure(str, str->len + length_len + 1 + skel->len);
502 svn_stringbuf_appendbytes(str, buf, length_len);
503 svn_stringbuf_appendbyte(str, ' ');
504 svn_stringbuf_appendbytes(str, skel->data, skel->len);
509 /* Append a list to STR: an opening parenthesis, the list elements
510 * separated by a space, and a closing parenthesis. */
513 svn_stringbuf_appendbyte(str, '(');
515 for (child = skel->children; child; child = child->next)
519 svn_stringbuf_appendbyte(str, ' ');
522 svn_stringbuf_appendbyte(str, ')');
530 /* Building skels. */
534 svn_skel__str_atom(const char *str, apr_pool_t *pool)
536 svn_skel_t *skel = apr_pcalloc(pool, sizeof(*skel));
537 skel->is_atom = TRUE;
539 skel->len = strlen(str);
546 svn_skel__mem_atom(const void *addr,
550 svn_skel_t *skel = apr_pcalloc(pool, sizeof(*skel));
551 skel->is_atom = TRUE;
560 svn_skel__make_empty_list(apr_pool_t *pool)
562 svn_skel_t *skel = apr_pcalloc(pool, sizeof(*skel));
566 svn_skel_t *svn_skel__dup(const svn_skel_t *src_skel, svn_boolean_t dup_data,
567 apr_pool_t *result_pool)
569 svn_skel_t *skel = apr_pmemdup(result_pool, src_skel, sizeof(svn_skel_t));
571 if (dup_data && skel->data)
574 skel->data = apr_pmemdup(result_pool, skel->data, skel->len);
577 /* When creating a skel this would be NULL, 0 for a list.
578 When parsing a string to a skel this might point to real data
579 delimiting the sublist. We don't copy that from here. */
586 skel->children = svn_skel__dup(skel->children, dup_data, result_pool);
589 skel->next = svn_skel__dup(skel->next, dup_data, result_pool);
595 svn_skel__prepend(svn_skel_t *skel, svn_skel_t *list_skel)
597 /* If list_skel isn't even a list, somebody's not using this
598 function properly. */
599 SVN_ERR_ASSERT_NO_RETURN(! list_skel->is_atom);
601 skel->next = list_skel->children;
602 list_skel->children = skel;
606 void svn_skel__prepend_int(apr_int64_t value,
608 apr_pool_t *result_pool)
610 char *val_string = apr_palloc(result_pool, SVN_INT64_BUFFER_SIZE);
611 svn__i64toa(val_string, value);
613 svn_skel__prepend_str(val_string, skel, result_pool);
617 void svn_skel__prepend_str(const char *value,
619 apr_pool_t *result_pool)
621 svn_skel_t *atom = svn_skel__str_atom(value, result_pool);
623 svn_skel__prepend(atom, skel);
627 void svn_skel__append(svn_skel_t *list_skel, svn_skel_t *skel)
629 SVN_ERR_ASSERT_NO_RETURN(list_skel != NULL && !list_skel->is_atom);
631 if (list_skel->children == NULL)
633 list_skel->children = skel;
637 list_skel = list_skel->children;
638 while (list_skel->next != NULL)
639 list_skel = list_skel->next;
640 list_skel->next = skel;
645 /* Examining skels. */
649 svn_skel__matches_atom(const svn_skel_t *skel, const char *str)
651 if (skel && skel->is_atom)
653 apr_size_t len = strlen(str);
655 return (skel->len == len
656 && ! memcmp(skel->data, str, len));
663 svn_skel__list_length(const svn_skel_t *skel)
666 const svn_skel_t *child;
668 if ((! skel) || skel->is_atom)
671 for (child = skel->children; child; child = child->next)
679 /* Parsing and unparsing into high-level types. */
682 svn_skel__parse_int(apr_int64_t *n, const svn_skel_t *skel,
683 apr_pool_t *scratch_pool)
687 /* We need to duplicate the SKEL contents in order to get a NUL-terminated
688 version of it. The SKEL may not have valid memory at DATA[LEN]. */
689 str = apr_pstrmemdup(scratch_pool, skel->data, skel->len);
690 return svn_error_trace(svn_cstring_atoi64(n, str));
695 svn_skel__parse_proplist(apr_hash_t **proplist_p,
696 const svn_skel_t *skel,
697 apr_pool_t *pool /* result_pool */)
699 apr_hash_t *proplist = NULL;
702 /* Validate the skel. */
703 if (! is_valid_proplist_skel(skel))
704 return skel_err("proplist");
706 /* Create the returned structure */
707 proplist = apr_hash_make(pool);
708 for (elt = skel->children; elt; elt = elt->next->next)
710 svn_string_t *value = svn_string_ncreate(elt->next->data,
711 elt->next->len, pool);
712 apr_hash_set(proplist,
713 apr_pstrmemdup(pool, elt->data, elt->len),
718 /* Return the structure. */
719 *proplist_p = proplist;
724 svn_skel__parse_iprops(apr_array_header_t **iprops,
725 const svn_skel_t *skel,
726 apr_pool_t *result_pool)
730 /* Validate the skel. */
731 if (! is_valid_iproplist_skel(skel))
732 return skel_err("iprops");
734 /* Create the returned structure */
735 *iprops = apr_array_make(result_pool, 1,
736 sizeof(svn_prop_inherited_item_t *));
738 for (elt = skel->children; elt; elt = elt->next->next)
740 svn_prop_inherited_item_t *new_iprop = apr_palloc(result_pool,
742 svn_string_t *repos_parent = svn_string_ncreate(elt->data, elt->len,
744 SVN_ERR(svn_skel__parse_proplist(&(new_iprop->prop_hash), elt->next,
746 new_iprop->path_or_url = repos_parent->data;
747 APR_ARRAY_PUSH(*iprops, svn_prop_inherited_item_t *) = new_iprop;
753 svn_skel__parse_prop(svn_string_t **propval,
754 const svn_skel_t *skel,
755 const char *propname,
756 apr_pool_t *pool /* result_pool */)
762 /* Validate the skel. */
763 if (! is_valid_proplist_skel(skel))
764 return skel_err("proplist");
766 /* Look for PROPNAME in SKEL. */
767 for (elt = skel->children; elt; elt = elt->next->next)
769 if (elt->len == strlen(propname)
770 && strncmp(propname, elt->data, elt->len) == 0)
772 *propval = svn_string_ncreate(elt->next->data, elt->next->len,
786 svn_skel__unparse_proplist(svn_skel_t **skel_p,
787 const apr_hash_t *proplist,
790 svn_skel_t *skel = svn_skel__make_empty_list(pool);
791 apr_hash_index_t *hi;
793 /* Create the skel. */
796 /* Loop over hash entries */
797 for (hi = apr_hash_first(pool, (apr_hash_t *)proplist); hi;
798 hi = apr_hash_next(hi))
805 apr_hash_this(hi, &key, &klen, &val);
809 svn_skel__prepend(svn_skel__mem_atom(value->data, value->len, pool),
813 svn_skel__prepend(svn_skel__mem_atom(key, klen, pool), skel);
817 /* Validate and return the skel. */
818 if (! is_valid_proplist_skel(skel))
819 return skel_err("proplist");
825 svn_skel__unparse_iproplist(svn_skel_t **skel_p,
826 const apr_array_header_t *inherited_props,
827 apr_pool_t *result_pool,
828 apr_pool_t *scratch_pool)
830 svn_skel_t *skel = svn_skel__make_empty_list(result_pool);
832 /* Create the skel. */
836 apr_hash_index_t *hi;
838 for (i = 0; i < inherited_props->nelts; i++)
840 svn_prop_inherited_item_t *iprop =
841 APR_ARRAY_IDX(inherited_props, i, svn_prop_inherited_item_t *);
843 svn_skel_t *skel_list = svn_skel__make_empty_list(result_pool);
844 svn_skel_t *skel_atom;
846 /* Loop over hash entries */
847 for (hi = apr_hash_first(scratch_pool, iprop->prop_hash);
849 hi = apr_hash_next(hi))
856 apr_hash_this(hi, &key, &klen, &val);
860 svn_skel__prepend(svn_skel__mem_atom(value->data, value->len,
861 result_pool), skel_list);
864 svn_skel__prepend(svn_skel__mem_atom(key, klen, result_pool),
868 skel_atom = svn_skel__str_atom(
869 apr_pstrdup(result_pool, iprop->path_or_url), result_pool);
870 svn_skel__append(skel, skel_atom);
871 svn_skel__append(skel, skel_list);
875 /* Validate and return the skel. */
876 if (! is_valid_iproplist_skel(skel))
877 return skel_err("iproplist");