/* skel-test.c --- tests for the skeleton functions
*
* ====================================================================
* Copyright (c) 2000-2004 CollabNet. All rights reserved.
*
* This software is licensed as described in the file COPYING, which
* you should have received as part of this distribution. The terms
* are also available at http://subversion.tigris.org/license-1.html.
* If newer versions of this license are posted there, you may use a
* newer version instead, at your option.
*
* This software consists of voluntary contributions made by many
* individuals. For exact contribution history, see the revision
* history and logs, available at http://subversion.tigris.org/.
* ====================================================================
*/
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <stdio.h>
#include <apr.h>
#include "svn_pools.h"
#include "svn_string.h"
#include "../svn_test.h"
#include "../svn_test_fs.h"
#include "../../libsvn_fs_base/fs.h"
#include "../../libsvn_fs_base/util/skel.h"
/* Some utility functions. */
/* A quick way to create error messages. */
static svn_error_t *
fail(apr_pool_t *pool, const char *fmt, ...)
{
va_list ap;
char *msg;
va_start(ap, fmt);
msg = apr_pvsprintf(pool, fmt, ap);
va_end(ap);
return svn_error_create(SVN_ERR_TEST_FAILED, 0, msg);
}
/* Free everything from pool, and return an empty Subversion string. */
static svn_stringbuf_t *
get_empty_string(apr_pool_t *pool)
{
svn_pool_clear(pool);
return svn_stringbuf_ncreate(0, 0, pool);
}
/* Parse a skeleton from a Subversion string. */
static skel_t *
parse_str(svn_stringbuf_t *str, apr_pool_t *pool)
{
return svn_fs_base__parse_skel(str->data, str->len, pool);
}
/* Parse a skeleton from a C string. */
static skel_t *
parse_cstr(const char *str, apr_pool_t *pool)
{
return svn_fs_base__parse_skel(str, strlen(str), pool);
}
enum char_type {
type_nothing = 0,
type_space = 1,
type_digit = 2,
type_paren = 3,
type_name = 4
};
static int skel_char_map_initialized;
static enum char_type skel_char_map[256];
static void
init_char_types(void)
{
int i;
const char *c;
if (skel_char_map_initialized)
return;
for (i = 0; i < 256; i++)
skel_char_map[i] = type_nothing;
for (i = '0'; i <= '9'; i++)
skel_char_map[i] = type_digit;
for (c = "\t\n\f\r "; *c; c++)
skel_char_map[(unsigned char) *c] = type_space;
for (c = "()[]"; *c; c++)
skel_char_map[(unsigned char) *c] = type_paren;
for (i = 'A'; i <= 'Z'; i++)
skel_char_map[i] = type_name;
for (i = 'a'; i <= 'z'; i++)
skel_char_map[i] = type_name;
skel_char_map_initialized = 1;
}
/* Return true iff BYTE is a whitespace byte. */
static int
skel_is_space(char byte)
{
init_char_types();
return skel_char_map[(unsigned char) byte] == type_space;
}
#if 0
/* Return true iff BYTE is a digit byte. */
static int
skel_is_digit(char byte)
{
init_char_types();
return skel_char_map[(unsigned char) byte] == type_digit;
}
#endif
/* Return true iff BYTE is a paren byte. */
static int
skel_is_paren(char byte)
{
init_char_types();
return skel_char_map[(unsigned char) byte] == type_paren;
}
/* Return true iff BYTE is a name byte. */
static int
skel_is_name(char byte)
{
init_char_types();
return skel_char_map[(unsigned char) byte] == type_name;
}
/* Check that SKEL is an atom, and its contents match LEN bytes of
DATA. */
static int
check_atom(skel_t *skel, const char *data, apr_size_t len)
{
return (skel
&& skel->is_atom
&& skel->len == len
&& ! memcmp(skel->data, data, len));
}
/* Functions that generate/check interesting implicit-length atoms. */
/* Append to STR an implicit-length atom consisting of the byte BYTE,
terminated by the character TERM. BYTE must be a name byte,
and TERM must be a valid skel separator, or NULL. */
static void
put_implicit_length_byte(svn_stringbuf_t *str, char byte, char term)
{
if (! skel_is_name(byte))
abort();
if (term != '\0'
&& ! skel_is_space(term)
&& ! skel_is_paren(term))
abort();
svn_stringbuf_appendbytes(str, &byte, 1);
if (term != '\0')
svn_stringbuf_appendbytes(str, &term, 1);
}
/* Return true iff SKEL is the parsed form of the atom produced by
calling put_implicit_length with BYTE. */
static int
check_implicit_length_byte(skel_t *skel, char byte)
{
if (! skel_is_name(byte))
abort();
return check_atom(skel, &byte, 1);
}
/* Subroutine for the *_implicit_length_all_chars functions. */
static char *
gen_implicit_length_all_chars(apr_size_t *len_p)
{
apr_size_t pos;
int i;
static char name[256];
/* Gotta start with a valid name character. */
pos = 0;
name[pos++] = 'x';
for (i = 0; i < 256; i++)
if (! skel_is_space( (apr_byte_t)i)
&& ! skel_is_paren( (apr_byte_t)i))
name[pos++] = i;
*len_p = pos;
return name;
}
/* Append to STR an implicit-length atom containing every character
that's legal in such atoms, terminated by the valid atom terminator
TERM. */
static void
put_implicit_length_all_chars(svn_stringbuf_t *str, char term)
{
apr_size_t len;
char *name = gen_implicit_length_all_chars(&len);
if (term != '\0'
&& ! skel_is_space(term)
&& ! skel_is_paren(term))
abort();
svn_stringbuf_appendbytes(str, name, len);
if (term != '\0')
svn_stringbuf_appendbytes(str, &term, 1);
}
/* Return true iff SKEL is the parsed form of the atom produced by
calling put_implicit_length_all_chars. */
static int
check_implicit_length_all_chars(skel_t *skel)
{
apr_size_t len;
char *name = gen_implicit_length_all_chars(&len);
return check_atom(skel, name, len);
}
/* Test parsing of implicit-length atoms. */
static svn_error_t *
parse_implicit_length(const char **msg,
svn_boolean_t msg_only,
svn_test_opts_t *opts,
apr_pool_t *pool)
{
svn_stringbuf_t *str = get_empty_string(pool);
skel_t *skel;
*msg = "parse implicit-length atoms";
if (msg_only)
return SVN_NO_ERROR;
/* Try all valid single-byte atoms. */
{
const char *c;
int i;
for (c = "\t\n\f\r ()[]"; *c; c++)
for (i = 0; i < 256; i++)
if (skel_is_name((apr_byte_t)i))
{
svn_stringbuf_setempty(str);
put_implicit_length_byte(str, (apr_byte_t)i, *c);
skel = parse_str(str, pool);
if (! check_implicit_length_byte(skel, (apr_byte_t)i))
return fail(pool, "single-byte implicit-length skel 0x%02x"
" with terminator 0x%02x",
i, c);
}
}
/* Try an atom that contains every character that's legal in an
implicit-length atom. */
svn_stringbuf_setempty(str);
put_implicit_length_all_chars(str, '\0');
skel = parse_str(str, pool);
if (! check_implicit_length_all_chars(skel))
return fail(pool, "implicit-length skel containing all legal chars");
return SVN_NO_ERROR;
}
/* Functions that generate/check interesting explicit-length atoms. */
/* Append to STR the representation of the atom containing the LEN
bytes at DATA, in explicit-length form, using SEP as the separator
between the length and the data. */
static void
put_explicit_length(svn_stringbuf_t *str, const char *data, apr_size_t len,
char sep)
{
char *buf = malloc(len + 100);
apr_size_t length_len;
if (! skel_is_space(sep))
abort();
/* Generate the length and separator character. */
sprintf(buf, "%"APR_SIZE_T_FMT"%c", len, sep);
length_len = strlen(buf);
/* Copy in the real data (which may contain nulls). */
memcpy(buf + length_len, data, len);
svn_stringbuf_appendbytes(str, buf, length_len + len);
free(buf);
}
/* Return true iff SKEL is the parsed form of an atom generated by
put_explicit_length. */
static int
check_explicit_length(skel_t *skel, const char *data, apr_size_t len)
{
return check_atom(skel, data, len);
}
/* Test parsing of explicit-length atoms. */
static svn_error_t *
try_explicit_length(const char *data, apr_size_t len, apr_size_t check_len,
apr_pool_t *pool)
{
int i;
svn_stringbuf_t *str = get_empty_string(pool);
skel_t *skel;
/* Try it with every possible separator character. */
for (i = 0; i < 256; i++)
if (skel_is_space( (apr_byte_t)i))
{
svn_stringbuf_setempty(str);
put_explicit_length(str, data, len, (apr_byte_t)i);
skel = parse_str(str, pool);
if (! check_explicit_length(skel, data, check_len))
return fail(pool, "failed to reparse explicit-length atom");
}
return SVN_NO_ERROR;
}
static svn_error_t *
parse_explicit_length(const char **msg,
svn_boolean_t msg_only,
svn_test_opts_t *opts,
apr_pool_t *pool)
{
*msg = "parse explicit-length atoms";
if (msg_only)
return SVN_NO_ERROR;
/* Try to parse the empty atom. */
SVN_ERR(try_explicit_length("", 0, 0, pool));
/* Try to parse every one-character atom. */
{
int i;
for (i = 0; i < 256; i++)
{
char buf[1];
buf[0] = i;
SVN_ERR(try_explicit_length(buf, 1, 1, pool));
}
}
/* Try to parse an atom containing every character. */
{
int i;
char data[256];
for (i = 0; i < 256; i++)
data[i] = i;
SVN_ERR(try_explicit_length(data, 256, 256, pool));
}
return SVN_NO_ERROR;
}
/* Test parsing of invalid atoms. */
static struct invalid_atoms
{
int type;
apr_size_t len;
const char *data;
} invalid_atoms[] = { { 1, 1, "(" },
{ 1, 1, ")" },
{ 1, 1, "[" },
{ 1, 1, "]" },
{ 1, 1, " " },
{ 1, 13, "Hello, World!" },
{ 1, 8, "1mplicit" },
{ 2, 2, "1" },
{ 2, 1, "12" },
{ 7, 0, NULL } };
static svn_error_t *
parse_invalid_atoms(const char **msg,
svn_boolean_t msg_only,
svn_test_opts_t *opts,
apr_pool_t *pool)
{
struct invalid_atoms *ia = invalid_atoms;
*msg = "parse invalid atoms";
if (msg_only)
return SVN_NO_ERROR;
while (ia->type != 7)
{
if (ia->type == 1)
{
skel_t *skel = parse_cstr(ia->data, pool);
if (check_atom(skel, ia->data, ia->len))
return fail(pool,
"failed to detect parsing error in '%s'", ia->data);
}
else
{
svn_error_t *err = try_explicit_length(ia->data, ia->len,
strlen(ia->data), pool);
if (err == SVN_NO_ERROR)
return fail(pool, "got wrong length in explicit-length atom");
svn_error_clear(err);
}
ia++;
}
return SVN_NO_ERROR;
}
/* Functions that generate/check interesting lists. */
/* Append the start of a list to STR, using LEN bytes of the
whitespace character SPACE. */
static void
put_list_start(svn_stringbuf_t *str, char space, int len)
{
int i;
if (len > 0 && ! skel_is_space(space))
abort();
svn_stringbuf_appendcstr(str, "(");
for (i = 0; i < len; i++)
svn_stringbuf_appendbytes(str, &space, 1);
}
/* Append the end of a list to STR, using LEN bytes of the
whitespace character SPACE. */
static void
put_list_end(svn_stringbuf_t *str, char space, int len)
{
int i;
if (len > 0 && ! skel_is_space(space))
abort();
for (i = 0; i < len; i++)
svn_stringbuf_appendbytes(str, &space, 1);
svn_stringbuf_appendcstr(str, ")");
}
/* Return true iff SKEL is a list of length DESIRED_LEN. */
static int
check_list(skel_t *skel, int desired_len)
{
int len;
skel_t *child;
if (! (skel
&& ! skel->is_atom))
return 0;
len = 0;
for (child = skel->children; child; child = child->next)
len++;
return len == desired_len;
}
/* Parse lists. */
static svn_error_t *
parse_list(const char **msg,
svn_boolean_t msg_only,
svn_test_opts_t *opts,
apr_pool_t *pool)
{
*msg = "parse lists";
if (msg_only)
return SVN_NO_ERROR;
{
/* Try lists of varying length. */
int list_len;
for (list_len = 0;
list_len < 30;
list_len < 4 ? list_len++ : (list_len *= 3))
{
/* Try lists with different separators. */
int sep;
for (sep = 0; sep < 256; sep++)
if (skel_is_space( (apr_byte_t)sep))
{
/* Try lists with different numbers of separator
characters between the elements. */
int sep_count;
for (sep_count = 0;
sep_count < 30;
sep_count < 4 ? sep_count++ : (sep_count *= 3))
{
/* Try various single-byte implicit-length atoms
for elements. */
int atom_byte;
for (atom_byte = 0; atom_byte < 256; atom_byte++)
if (skel_is_name( (apr_byte_t)atom_byte))
{
int i;
svn_stringbuf_t *str = get_empty_string(pool);
skel_t *skel;
skel_t *child;
put_list_start(str, (apr_byte_t)sep, sep_count);
for (i = 0; i < list_len; i++)
put_implicit_length_byte(str,
(apr_byte_t)atom_byte,
(apr_byte_t)sep);
put_list_end(str, (apr_byte_t)sep, sep_count);
skel = parse_str(str, pool);
if (! check_list(skel, list_len))
return fail(pool, "couldn't parse list");
for (child = skel->children;
child;
child = child->next)
if (! check_implicit_length_byte
(child, (apr_byte_t)atom_byte))
return fail(pool,
"list was reparsed incorrectly");
}
/* Try the atom containing every character that's
legal in an implicit-length atom as the element. */
{
int i;
svn_stringbuf_t *str = get_empty_string(pool);
skel_t *skel;
skel_t *child;
put_list_start(str, (apr_byte_t)sep, sep_count);
for (i = 0; i < list_len; i++)
put_implicit_length_all_chars(str, (apr_byte_t)sep);
put_list_end(str, (apr_byte_t)sep, sep_count);
skel = parse_str(str, pool);
if (! check_list(skel, list_len))
return fail(pool, "couldn't parse list");
for (child = skel->children;
child;
child = child->next)
if (! check_implicit_length_all_chars(child))
return fail(pool, "couldn't parse list");
}
/* Try using every one-byte explicit-length atom as
an element. */
for (atom_byte = 0; atom_byte < 256; atom_byte++)
{
int i;
svn_stringbuf_t *str = get_empty_string(pool);
skel_t *skel;
skel_t *child;
char buf[1];
buf[0] = atom_byte;
put_list_start(str, (apr_byte_t)sep, sep_count);
for (i = 0; i < list_len; i++)
put_explicit_length(str, buf, 1, (apr_byte_t)sep);
put_list_end(str, (apr_byte_t)sep, sep_count);
skel = parse_str(str, pool);
if (! check_list(skel, list_len))
return fail(pool, "couldn't parse list");
for (child = skel->children;
child;
child = child->next)
if (! check_explicit_length(child, buf, 1))
return fail(pool, "list was reparsed incorrectly");
}
/* Try using an atom containing every character as
an element. */
{
int i;
svn_stringbuf_t *str = get_empty_string(pool);
skel_t *skel;
skel_t *child;
char data[256];
for (i = 0; i < 256; i++)
data[i] = i;
put_list_start(str, (apr_byte_t)sep, sep_count);
for (i = 0; i < list_len; i++)
put_explicit_length(str, data, 256, (apr_byte_t)sep);
put_list_end(str, (apr_byte_t)sep, sep_count);
skel = parse_str(str, pool);
if (! check_list(skel, list_len))
return fail(pool, "couldn't parse list");
for (child = skel->children;
child;
child = child->next)
if (! check_explicit_length(child, data, 256))
return fail(pool, "list was re-parsed incorrectly");
}
}
}
}
}
/* Try to parse some invalid lists. */
{
int sep;
/* Try different separators. */
for (sep = 0; sep < 256; sep++)
if (skel_is_space( (apr_byte_t)sep))
{
/* Try lists with different numbers of separator
characters between the elements. */
int sep_count;
for (sep_count = 0;
sep_count < 100;
sep_count < 10 ? sep_count++ : (sep_count *= 3))
{
svn_stringbuf_t *str;
/* A list with only a separator. */
str = get_empty_string(pool);
put_list_start(str, (apr_byte_t)sep, sep_count);
if (parse_str(str, pool))
return fail(pool, "failed to detect syntax error");
/* A list with only a terminator. */
str = get_empty_string(pool);
put_list_end(str, (apr_byte_t)sep, sep_count);
if (parse_str(str, pool))
return fail(pool, "failed to detect syntax error");
/* A list containing an invalid element. */
str = get_empty_string(pool);
put_list_start(str, (apr_byte_t)sep, sep_count);
svn_stringbuf_appendcstr(str, "100 ");
put_list_end(str, (apr_byte_t)sep, sep_count);
if (parse_str(str, pool))
return fail(pool, "failed to detect invalid element");
}
}
}
return SVN_NO_ERROR;
}
/* Building interesting skels. */
/* Build an atom skel containing the LEN bytes at DATA. */
static skel_t *
build_atom(apr_size_t len, char *data, apr_pool_t *pool)
{
char *copy = apr_palloc(pool, len);
skel_t *skel = apr_palloc(pool, sizeof(*skel));
memcpy(copy, data, len);
skel->is_atom = 1;
skel->len = len;
skel->data = copy;
return skel;
}
/* Build an empty list skel. */
static skel_t *
empty(apr_pool_t *pool)
{
skel_t *skel = apr_palloc(pool, sizeof(*skel));
skel->is_atom = 0;
skel->children = 0;
return skel;
}
/* Stick ELEMENT at the beginning of the list skeleton LIST. */
static void
add(skel_t *element, skel_t *list)
{
element->next = list->children;
list->children = element;
}
/* Return true if the contents of skel A are identical to those of
skel B. */
static int
skel_equal(skel_t *a, skel_t *b)
{
if (a->is_atom != b->is_atom)
return 0;
if (a->is_atom)
return (a->len == b->len
&& ! memcmp(a->data, b->data, a->len));
else
{
skel_t *a_child, *b_child;
for (a_child = a->children, b_child = b->children;
a_child && b_child;
a_child = a_child->next, b_child = b_child->next)
if (! skel_equal(a_child, b_child))
return 0;
if (a_child || b_child)
return 0;
}
return 1;
}
/* Unparsing implicit-length atoms. */
static svn_error_t *
unparse_implicit_length(const char **msg,
svn_boolean_t msg_only,
svn_test_opts_t *opts,
apr_pool_t *pool)
{
*msg = "unparse implicit-length atoms";
if (msg_only)
return SVN_NO_ERROR;
/* Unparse and check every single-byte implicit-length atom. */
{
int byte;
for (byte = 0; byte < 256; byte++)
if (skel_is_name( (apr_byte_t)byte))
{
svn_stringbuf_t *str = get_empty_string(pool);
char buf = (char)byte;
skel_t *skel = build_atom(1, &buf, pool);
str = svn_fs_base__unparse_skel(skel, pool);
if (! (str
&& str->len == 1
&& str->data[0] == (char)byte))
return fail(pool, "incorrectly unparsed single-byte "
"implicit-length atom");
}
}
return SVN_NO_ERROR;
}
/* Unparse some lists. */
static svn_error_t *
unparse_list(const char **msg,
svn_boolean_t msg_only,
svn_test_opts_t *opts,
apr_pool_t *pool)
{
*msg = "unparse lists";
if (msg_only)
return SVN_NO_ERROR;
/* Make a list of all the single-byte implicit-length atoms. */
{
svn_stringbuf_t *str = get_empty_string(pool);
int byte;
skel_t *list = empty(pool);
skel_t *reparsed, *elt;
for (byte = 0; byte < 256; byte++)
if (skel_is_name( (apr_byte_t)byte))
{
char buf = byte;
add(build_atom(1, &buf, pool), list);
}
/* Unparse that, parse it again, and see if we got the same thing
back. */
str = svn_fs_base__unparse_skel(list, pool);
reparsed = svn_fs_base__parse_skel(str->data, str->len, pool);
if (! reparsed || reparsed->is_atom)
return fail(pool, "result is syntactically misformed, or not a list");
if (! skel_equal(list, reparsed))
return fail(pool, "unparsing and parsing didn't preserve contents");
elt = reparsed->children;
for (byte = 255; byte >= 0; byte--)
if (skel_is_name( (apr_byte_t)byte))
{
if (! (elt
&& elt->is_atom
&& elt->len == 1
&& elt->data[0] == byte))
return fail(pool, "bad element");
/* Verify that each element's data falls within the string. */
if (elt->data < str->data
|| elt->data + elt->len > str->data + str->len)
return fail(pool, "bad element");
elt = elt->next;
}
/* We should have reached the end of the list at this point. */
if (elt)
return fail(pool, "list too long");
}
/* Make a list of lists. */
{
svn_stringbuf_t *str = get_empty_string(pool);
skel_t *top = empty(pool);
skel_t *reparsed;
int i;
for (i = 0; i < 10; i++)
{
skel_t *middle = empty(pool);
int j;
for (j = 0; j < 10; j++)
{
char buf[10];
apr_size_t k;
int val;
/* Make some interesting atom, containing lots of binary
characters. */
val = i * 10 + j;
for (k = 0; k < sizeof(buf); k++)
{
buf[k] = val;
val += j;
}
add(build_atom(sizeof(buf), buf, pool), middle);
}
add(middle, top);
}
str = svn_fs_base__unparse_skel(top, pool);
reparsed = svn_fs_base__parse_skel(str->data, str->len, pool);
if (! skel_equal(top, reparsed))
return fail(pool, "failed to reparse list of lists");
}
return SVN_NO_ERROR;
}
/* The test table. */
struct svn_test_descriptor_t test_funcs[] =
{
SVN_TEST_NULL,
SVN_TEST_PASS(parse_implicit_length),
SVN_TEST_PASS(parse_explicit_length),
SVN_TEST_PASS(parse_invalid_atoms),
SVN_TEST_PASS(parse_list),
SVN_TEST_PASS(unparse_implicit_length),
SVN_TEST_PASS(unparse_list),
SVN_TEST_NULL
};
syntax highlighted by Code2HTML, v. 0.9.1