diff options
Diffstat (limited to 'system/lib')
30 files changed, 5489 insertions, 332 deletions
diff --git a/system/lib/libc/musl/src/regex/regcomp.c b/system/lib/libc/musl/src/regex/regcomp.c new file mode 100644 index 00000000..5cedfd52 --- /dev/null +++ b/system/lib/libc/musl/src/regex/regcomp.c @@ -0,0 +1,3352 @@ +/* + regcomp.c - TRE POSIX compatible regex compilation functions. + + Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi> + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS + ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*/ + +#include <string.h> +#include <errno.h> +#include <stdlib.h> +#include <regex.h> +#include <limits.h> +#include <stdint.h> + +#include "tre.h" + +#include <assert.h> + +/*********************************************************************** + from tre-compile.h +***********************************************************************/ + +typedef struct { + int position; + int code_min; + int code_max; + int *tags; + int assertions; + tre_ctype_t class; + tre_ctype_t *neg_classes; + int backref; +} tre_pos_and_tags_t; + + +/*********************************************************************** + from tre-ast.c and tre-ast.h +***********************************************************************/ + +/* The different AST node types. */ +typedef enum { + LITERAL, + CATENATION, + ITERATION, + UNION +} tre_ast_type_t; + +/* Special subtypes of TRE_LITERAL. */ +#define EMPTY -1 /* Empty leaf (denotes empty string). */ +#define ASSERTION -2 /* Assertion leaf. */ +#define TAG -3 /* Tag leaf. */ +#define BACKREF -4 /* Back reference leaf. */ + +#define IS_SPECIAL(x) ((x)->code_min < 0) +#define IS_EMPTY(x) ((x)->code_min == EMPTY) +#define IS_ASSERTION(x) ((x)->code_min == ASSERTION) +#define IS_TAG(x) ((x)->code_min == TAG) +#define IS_BACKREF(x) ((x)->code_min == BACKREF) + + +/* A generic AST node. All AST nodes consist of this node on the top + level with `obj' pointing to the actual content. */ +typedef struct { + tre_ast_type_t type; /* Type of the node. */ + void *obj; /* Pointer to actual node. */ + int nullable; + int submatch_id; + int num_submatches; + int num_tags; + tre_pos_and_tags_t *firstpos; + tre_pos_and_tags_t *lastpos; +} tre_ast_node_t; + + +/* A "literal" node. These are created for assertions, back references, + tags, matching parameter settings, and all expressions that match one + character. */ +typedef struct { + long code_min; + long code_max; + int position; + tre_ctype_t class; + tre_ctype_t *neg_classes; +} tre_literal_t; + +/* A "catenation" node. These are created when two regexps are concatenated. + If there are more than one subexpressions in sequence, the `left' part + holds all but the last, and `right' part holds the last subexpression + (catenation is left associative). */ +typedef struct { + tre_ast_node_t *left; + tre_ast_node_t *right; +} tre_catenation_t; + +/* An "iteration" node. These are created for the "*", "+", "?", and "{m,n}" + operators. */ +typedef struct { + /* Subexpression to match. */ + tre_ast_node_t *arg; + /* Minimum number of consecutive matches. */ + int min; + /* Maximum number of consecutive matches. */ + int max; + /* If 0, match as many characters as possible, if 1 match as few as + possible. Note that this does not always mean the same thing as + matching as many/few repetitions as possible. */ + unsigned int minimal:1; +} tre_iteration_t; + +/* An "union" node. These are created for the "|" operator. */ +typedef struct { + tre_ast_node_t *left; + tre_ast_node_t *right; +} tre_union_t; + +static tre_ast_node_t * +tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size); + +static tre_ast_node_t * +tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position); + +static tre_ast_node_t * +tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max, + int minimal); + +static tre_ast_node_t * +tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right); + +static tre_ast_node_t * +tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left, + tre_ast_node_t *right); + + +static tre_ast_node_t * +tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size) +{ + tre_ast_node_t *node; + + node = tre_mem_calloc(mem, sizeof(*node)); + if (!node) + return NULL; + node->obj = tre_mem_calloc(mem, size); + if (!node->obj) + return NULL; + node->type = type; + node->nullable = -1; + node->submatch_id = -1; + + return node; +} + +static tre_ast_node_t * +tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position) +{ + tre_ast_node_t *node; + tre_literal_t *lit; + + node = tre_ast_new_node(mem, LITERAL, sizeof(tre_literal_t)); + if (!node) + return NULL; + lit = node->obj; + lit->code_min = code_min; + lit->code_max = code_max; + lit->position = position; + + return node; +} + +static tre_ast_node_t * +tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max, + int minimal) +{ + tre_ast_node_t *node; + tre_iteration_t *iter; + + node = tre_ast_new_node(mem, ITERATION, sizeof(tre_iteration_t)); + if (!node) + return NULL; + iter = node->obj; + iter->arg = arg; + iter->min = min; + iter->max = max; + iter->minimal = minimal; + node->num_submatches = arg->num_submatches; + + return node; +} + +static tre_ast_node_t * +tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right) +{ + tre_ast_node_t *node; + + node = tre_ast_new_node(mem, UNION, sizeof(tre_union_t)); + if (node == NULL) + return NULL; + ((tre_union_t *)node->obj)->left = left; + ((tre_union_t *)node->obj)->right = right; + node->num_submatches = left->num_submatches + right->num_submatches; + + return node; +} + +static tre_ast_node_t * +tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left, + tre_ast_node_t *right) +{ + tre_ast_node_t *node; + + node = tre_ast_new_node(mem, CATENATION, sizeof(tre_catenation_t)); + if (node == NULL) + return NULL; + ((tre_catenation_t *)node->obj)->left = left; + ((tre_catenation_t *)node->obj)->right = right; + node->num_submatches = left->num_submatches + right->num_submatches; + + return node; +} + + +/*********************************************************************** + from tre-stack.c and tre-stack.h +***********************************************************************/ + +typedef struct tre_stack_rec tre_stack_t; + +/* Creates a new stack object. `size' is initial size in bytes, `max_size' + is maximum size, and `increment' specifies how much more space will be + allocated with realloc() if all space gets used up. Returns the stack + object or NULL if out of memory. */ +static tre_stack_t * +tre_stack_new(int size, int max_size, int increment); + +/* Frees the stack object. */ +static void +tre_stack_destroy(tre_stack_t *s); + +/* Returns the current number of objects in the stack. */ +static int +tre_stack_num_objects(tre_stack_t *s); + +/* Each tre_stack_push_*(tre_stack_t *s, <type> value) function pushes + `value' on top of stack `s'. Returns REG_ESPACE if out of memory. + This tries to realloc() more space before failing if maximum size + has not yet been reached. Returns REG_OK if successful. */ +#define declare_pushf(typetag, type) \ + static reg_errcode_t tre_stack_push_ ## typetag(tre_stack_t *s, type value) + +declare_pushf(voidptr, void *); +declare_pushf(int, int); + +/* Each tre_stack_pop_*(tre_stack_t *s) function pops the topmost + element off of stack `s' and returns it. The stack must not be + empty. */ +#define declare_popf(typetag, type) \ + static type tre_stack_pop_ ## typetag(tre_stack_t *s) + +declare_popf(voidptr, void *); +declare_popf(int, int); + +/* Just to save some typing. */ +#define STACK_PUSH(s, typetag, value) \ + do \ + { \ + status = tre_stack_push_ ## typetag(s, value); \ + } \ + while (/*CONSTCOND*/0) + +#define STACK_PUSHX(s, typetag, value) \ + { \ + status = tre_stack_push_ ## typetag(s, value); \ + if (status != REG_OK) \ + break; \ + } + +#define STACK_PUSHR(s, typetag, value) \ + { \ + reg_errcode_t _status; \ + _status = tre_stack_push_ ## typetag(s, value); \ + if (_status != REG_OK) \ + return _status; \ + } + +union tre_stack_item { + void *voidptr_value; + int int_value; +}; + +struct tre_stack_rec { + int size; + int max_size; + int increment; + int ptr; + union tre_stack_item *stack; +}; + + +static tre_stack_t * +tre_stack_new(int size, int max_size, int increment) +{ + tre_stack_t *s; + + s = xmalloc(sizeof(*s)); + if (s != NULL) + { + s->stack = xmalloc(sizeof(*s->stack) * size); + if (s->stack == NULL) + { + xfree(s); + return NULL; + } + s->size = size; + s->max_size = max_size; + s->increment = increment; + s->ptr = 0; + } + return s; +} + +static void +tre_stack_destroy(tre_stack_t *s) +{ + xfree(s->stack); + xfree(s); +} + +static int +tre_stack_num_objects(tre_stack_t *s) +{ + return s->ptr; +} + +static reg_errcode_t +tre_stack_push(tre_stack_t *s, union tre_stack_item value) +{ + if (s->ptr < s->size) + { + s->stack[s->ptr] = value; + s->ptr++; + } + else + { + if (s->size >= s->max_size) + { + return REG_ESPACE; + } + else + { + union tre_stack_item *new_buffer; + int new_size; + new_size = s->size + s->increment; + if (new_size > s->max_size) + new_size = s->max_size; + new_buffer = xrealloc(s->stack, sizeof(*new_buffer) * new_size); + if (new_buffer == NULL) + { + return REG_ESPACE; + } + assert(new_size > s->size); + s->size = new_size; + s->stack = new_buffer; + tre_stack_push(s, value); + } + } + return REG_OK; +} + +#define define_pushf(typetag, type) \ + declare_pushf(typetag, type) { \ + union tre_stack_item item; \ + item.typetag ## _value = value; \ + return tre_stack_push(s, item); \ +} + +define_pushf(int, int) +define_pushf(voidptr, void *) + +#define define_popf(typetag, type) \ + declare_popf(typetag, type) { \ + return s->stack[--s->ptr].typetag ## _value; \ + } + +define_popf(int, int) +define_popf(voidptr, void *) + + +/*********************************************************************** + from tre-parse.c and tre-parse.h +***********************************************************************/ + +/* Parse context. */ +typedef struct { + /* Memory allocator. The AST is allocated using this. */ + tre_mem_t mem; + /* Stack used for keeping track of regexp syntax. */ + tre_stack_t *stack; + /* The parse result. */ + tre_ast_node_t *result; + /* The regexp to parse and its length. */ + const char *re; + /* The first character of the entire regexp. */ + const char *re_start; + /* Current submatch ID. */ + int submatch_id; + /* Current position (number of literal). */ + int position; + /* The highest back reference or -1 if none seen so far. */ + int max_backref; + /* This flag is set if the regexp uses approximate matching. */ + int have_approx; + /* Compilation flags. */ + int cflags; + /* If this flag is set the top-level submatch is not captured. */ + int nofirstsub; +} tre_parse_ctx_t; + +/* Parses a wide character regexp pattern into a syntax tree. This parser + handles both syntaxes (BRE and ERE), including the TRE extensions. */ +static reg_errcode_t +tre_parse(tre_parse_ctx_t *ctx); + + +/* + This parser is just a simple recursive descent parser for POSIX.2 + regexps. The parser supports both the obsolete default syntax and + the "extended" syntax, and some nonstandard extensions. +*/ + +/* Characters with special meanings in regexp syntax. */ +#define CHAR_PIPE '|' +#define CHAR_LPAREN '(' +#define CHAR_RPAREN ')' +#define CHAR_LBRACE '{' +#define CHAR_RBRACE '}' +#define CHAR_LBRACKET '[' +#define CHAR_RBRACKET ']' +#define CHAR_MINUS '-' +#define CHAR_STAR '*' +#define CHAR_QUESTIONMARK '?' +#define CHAR_PLUS '+' +#define CHAR_PERIOD '.' +#define CHAR_COLON ':' +#define CHAR_EQUAL '=' +#define CHAR_COMMA ',' +#define CHAR_CARET '^' +#define CHAR_DOLLAR '$' +#define CHAR_BACKSLASH '\\' +#define CHAR_HASH '#' +#define CHAR_TILDE '~' + + +/* Some macros for expanding \w, \s, etc. */ +static const struct tre_macro_struct { + const char c; + const char *expansion; +} tre_macros[] = + { {'t', "\t"}, {'n', "\n"}, {'r', "\r"}, + {'f', "\f"}, {'a', "\a"}, {'e', "\033"}, + {'w', "[[:alnum:]_]"}, {'W', "[^[:alnum:]_]"}, {'s', "[[:space:]]"}, + {'S', "[^[:space:]]"}, {'d', "[[:digit:]]"}, {'D', "[^[:digit:]]"}, + { 0, NULL } + }; + + +/* Expands a macro delimited by `regex' and `regex_end' to `buf', which + must have at least `len' items. Sets buf[0] to zero if the there + is no match in `tre_macros'. */ +static const char * +tre_expand_macro(const char *regex) +{ + int i; + + if (!*regex) + return 0; + + for (i = 0; tre_macros[i].expansion && tre_macros[i].c != *regex; i++); + return tre_macros[i].expansion; +} + +static reg_errcode_t +tre_new_item(tre_mem_t mem, int min, int max, int *i, int *max_i, + tre_ast_node_t ***items) +{ + reg_errcode_t status; + tre_ast_node_t **array = *items; + /* Allocate more space if necessary. */ + if (*i >= *max_i) + { + tre_ast_node_t **new_items; + /* If the array is already 1024 items large, give up -- there's + probably an error in the regexp (e.g. not a '\0' terminated + string and missing ']') */ + if (*max_i > 1024) + return REG_ESPACE; + *max_i *= 2; + new_items = xrealloc(array, sizeof(*items) * *max_i); + if (new_items == NULL) + return REG_ESPACE; + *items = array = new_items; + } + array[*i] = tre_ast_new_literal(mem, min, max, -1); + status = array[*i] == NULL ? REG_ESPACE : REG_OK; + (*i)++; + return status; +} + + +static int +tre_compare_items(const void *a, const void *b) +{ + const tre_ast_node_t *node_a = *(tre_ast_node_t * const *)a; + const tre_ast_node_t *node_b = *(tre_ast_node_t * const *)b; + tre_literal_t *l_a = node_a->obj, *l_b = node_b->obj; + int a_min = l_a->code_min, b_min = l_b->code_min; + + if (a_min < b_min) + return -1; + else if (a_min > b_min) + return 1; + else + return 0; +} + +/* Maximum number of character classes that can occur in a negated bracket + expression. */ +#define MAX_NEG_CLASSES 64 + +/* Maximum length of character class names. */ +#define MAX_CLASS_NAME + +static reg_errcode_t +tre_parse_bracket_items(tre_parse_ctx_t *ctx, int negate, + tre_ctype_t neg_classes[], int *num_neg_classes, + tre_ast_node_t ***items, int *num_items, + int *items_size) +{ + const char *re = ctx->re; + reg_errcode_t status = REG_OK; + tre_ctype_t class = (tre_ctype_t)0; + int i = *num_items; + int max_i = *items_size; + int skip; + + /* Build an array of the items in the bracket expression. */ + while (status == REG_OK) + { + skip = 0; + if (!*re) + { + status = REG_EBRACK; + } + else if (*re == CHAR_RBRACKET && re > ctx->re) + { + re++; + break; + } + else + { + tre_cint_t min = 0, max = 0; + wchar_t wc; + int clen = mbtowc(&wc, re, -1); + + if (clen<0) clen=1, wc=WEOF; + + class = (tre_ctype_t)0; + if (*(re + clen) == CHAR_MINUS && *(re + clen + 1) != CHAR_RBRACKET) + { + min = wc; + re += clen+1; + clen = mbtowc(&wc, re, -1); + if (clen<0) clen=1, wc=WEOF; + max = wc; + re += clen; + /* XXX - Should use collation order instead of encoding values + in character ranges. */ + if (min > max) + status = REG_ERANGE; + } + else if (*re == CHAR_LBRACKET && *(re + 1) == CHAR_PERIOD) + status = REG_ECOLLATE; + else if (*re == CHAR_LBRACKET && *(re + 1) == CHAR_EQUAL) + status = REG_ECOLLATE; + else if (*re == CHAR_LBRACKET && *(re + 1) == CHAR_COLON) + { + char tmp_str[64]; + const char *endptr = re + 2; + int len; + while (*endptr && *endptr != CHAR_COLON) + endptr++; + if (*endptr) + { + len = MIN(endptr - re - 2, 63); + strncpy(tmp_str, re + 2, len); + tmp_str[len] = '\0'; + class = tre_ctype(tmp_str); + if (!class) + status = REG_ECTYPE; + re = endptr + 2; + } + else + status = REG_ECTYPE; + min = 0; + max = TRE_CHAR_MAX; + } + else + { + if (*re == CHAR_MINUS && *(re + 1) != CHAR_RBRACKET + && ctx->re != re) + /* Two ranges are not allowed to share and endpoint. */ + status = REG_ERANGE; + min = max = wc; + re += clen; + } + + if (status != REG_OK) + break; + + if (class && negate) + if (*num_neg_classes >= MAX_NEG_CLASSES) + status = REG_ESPACE; + else + neg_classes[(*num_neg_classes)++] = class; + else if (!skip) + { + status = tre_new_item(ctx->mem, min, max, &i, &max_i, items); + if (status != REG_OK) + break; + ((tre_literal_t*)((*items)[i-1])->obj)->class = class; + } + + /* Add opposite-case counterpoints if REG_ICASE is present. + This is broken if there are more than two "same" characters. */ + if (ctx->cflags & REG_ICASE && !class && status == REG_OK && !skip) + { + tre_cint_t cmin, ccurr; + + while (min <= max) + { + if (tre_islower(min)) + { + cmin = ccurr = tre_toupper(min++); + while (tre_islower(min) && tre_toupper(min) == ccurr + 1 + && min <= max) + ccurr = tre_toupper(min++); + status = tre_new_item(ctx->mem, cmin, ccurr, + &i, &max_i, items); + } + else if (tre_isupper(min)) + { + cmin = ccurr = tre_tolower(min++); + while (tre_isupper(min) && tre_tolower(min) == ccurr + 1 + && min <= max) + ccurr = tre_tolower(min++); + status = tre_new_item(ctx->mem, cmin, ccurr, + &i, &max_i, items); + } + else min++; + if (status != REG_OK) + break; + } + if (status != REG_OK) + break; + } + } + } + *num_items = i; + *items_size = max_i; + ctx->re = re; + return status; +} + +static reg_errcode_t +tre_parse_bracket(tre_parse_ctx_t *ctx, tre_ast_node_t **result) +{ + tre_ast_node_t *node = NULL; + int negate = 0; + reg_errcode_t status = REG_OK; + tre_ast_node_t **items, *u, *n; + int i = 0, j, max_i = 32, curr_max, curr_min; + tre_ctype_t neg_classes[MAX_NEG_CLASSES]; + int num_neg_classes = 0; + + /* Start off with an array of `max_i' elements. */ + items = xmalloc(sizeof(*items) * max_i); + if (items == NULL) + return REG_ESPACE; + + if (*ctx->re == CHAR_CARET) + { + negate = 1; + ctx->re++; + } + + status = tre_parse_bracket_items(ctx, negate, neg_classes, &num_neg_classes, + &items, &i, &max_i); + + if (status != REG_OK) + goto parse_bracket_done; + + /* Sort the array if we need to negate it. */ + if (negate) + qsort(items, (unsigned)i, sizeof(*items), tre_compare_items); + + curr_max = curr_min = 0; + /* Build a union of the items in the array, negated if necessary. */ + for (j = 0; j < i && status == REG_OK; j++) + { + int min, max; + tre_literal_t *l = items[j]->obj; + min = l->code_min; + max = l->code_max; + + if (negate) + { + if (min < curr_max) + { + /* Overlap. */ + curr_max = MAX(max + 1, curr_max); + l = NULL; + } + else + { + /* No overlap. */ + curr_max = min - 1; + if (curr_max >= curr_min) + { + l->code_min = curr_min; + l->code_max = curr_max; + } + else + { + l = NULL; + } + curr_min = curr_max = max + 1; + } + } + + if (l != NULL) + { + int k; + l->position = ctx->position; + if (num_neg_classes > 0) + { + l->neg_classes = tre_mem_alloc(ctx->mem, + (sizeof(l->neg_classes) + * (num_neg_classes + 1))); + if (l->neg_classes == NULL) + { + status = REG_ESPACE; + break; + } + for (k = 0; k < num_neg_classes; k++) + l->neg_classes[k] = neg_classes[k]; + l->neg_classes[k] = (tre_ctype_t)0; + } + else + l->neg_classes = NULL; + if (node == NULL) + node = items[j]; + else + { + u = tre_ast_new_union(ctx->mem, node, items[j]); + if (u == NULL) + status = REG_ESPACE; + node = u; + } + } + } + + if (status != REG_OK) + goto parse_bracket_done; + + if (negate) + { + int k; + n = tre_ast_new_literal(ctx->mem, curr_min, TRE_CHAR_MAX, ctx->position); + if (n == NULL) + status = REG_ESPACE; + else + { + tre_literal_t *l = n->obj; + if (num_neg_classes > 0) + { + l->neg_classes = tre_mem_alloc(ctx->mem, + (sizeof(l->neg_classes) + * (num_neg_classes + 1))); + if (l->neg_classes == NULL) + { + status = REG_ESPACE; + goto parse_bracket_done; + } + for (k = 0; k < num_neg_classes; k++) + l->neg_classes[k] = neg_classes[k]; + l->neg_classes[k] = (tre_ctype_t)0; + } + else + l->neg_classes = NULL; + if (node == NULL) + node = n; + else + { + u = tre_ast_new_union(ctx->mem, node, n); + if (u == NULL) + status = REG_ESPACE; + node = u; + } + } + } + + if (status != REG_OK) + goto parse_bracket_done; + +#ifdef TRE_DEBUG + tre_ast_print(node); +#endif /* TRE_DEBUG */ + + parse_bracket_done: + xfree(items); + ctx->position++; + *result = node; + return status; +} + + +/* Parses a positive decimal integer. Returns -1 if the string does not + contain a valid number. */ +static int +tre_parse_int(const char **regex) +{ + int num = -1; + const char *r = *regex; + while (*r-'0'<10U) + { + if (num < 0) + num = 0; + num = num * 10 + *r - '0'; + r++; + } + *regex = r; + return num; +} + + +static reg_errcode_t +tre_parse_bound(tre_parse_ctx_t *ctx, tre_ast_node_t **result) +{ + int min, max; + const char *r = ctx->re; + int minimal = 0; + + /* Parse number (minimum repetition count). */ + min = -1; + if (*r >= '0' && *r <= '9') { + min = tre_parse_int(&r); + } + + /* Parse comma and second number (maximum repetition count). */ + max = min; + if (*r == CHAR_COMMA) + { + r++; + max = tre_parse_int(&r); + } + + /* Check that the repeat counts are sane. */ + if ((max >= 0 && min > max) || max > RE_DUP_MAX) + return REG_BADBR; + + /* Missing }. */ + if (!*r) + return REG_EBRACE; + + /* Empty contents of {}. */ + if (r == ctx->re) + return REG_BADBR; + + /* Parse the ending '}' or '\}'.*/ + if (ctx->cflags & REG_EXTENDED) + { + if (*r != CHAR_RBRACE) + return REG_BADBR; + r++; + } + else + { + if (*r != CHAR_BACKSLASH || *(r + 1) != CHAR_RBRACE) + return REG_BADBR; + r += 2; + } + + /* Create the AST node(s). */ + if (min == 0 && max == 0) + { + *result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1); + if (*result == NULL) + return REG_ESPACE; + } + else + { + if (min < 0 && max < 0) + /* Only approximate parameters set, no repetitions. */ + min = max = 1; + + *result = tre_ast_new_iter(ctx->mem, *result, min, max, minimal); + if (!*result) + return REG_ESPACE; + } + + ctx->re = r; + return REG_OK; +} + +typedef enum { + PARSE_RE = 0, + PARSE_ATOM, + PARSE_MARK_FOR_SUBMATCH, + PARSE_BRANCH, + PARSE_PIECE, + PARSE_CATENATION, + PARSE_POST_CATENATION, + PARSE_UNION, + PARSE_POST_UNION, + PARSE_POSTFIX, + PARSE_RESTORE_CFLAGS +} tre_parse_re_stack_symbol_t; + + +static reg_errcode_t +tre_parse(tre_parse_ctx_t *ctx) +{ + tre_ast_node_t *result = NULL; + tre_parse_re_stack_symbol_t symbol; + reg_errcode_t status = REG_OK; + tre_stack_t *stack = ctx->stack; + int bottom = tre_stack_num_objects(stack); + int depth = 0; + wchar_t wc; + int clen; + + if (!ctx->nofirstsub) + { + STACK_PUSH(stack, int, ctx->submatch_id); + STACK_PUSH(stack, int, PARSE_MARK_FOR_SUBMATCH); + ctx->submatch_id++; + } + STACK_PUSH(stack, int, PARSE_RE); + ctx->re_start = ctx->re; + + + /* The following is basically just a recursive descent parser. I use + an explicit stack instead of recursive functions mostly because of + two reasons: compatibility with systems which have an overflowable + call stack, and efficiency (both in lines of code and speed). */ + while (tre_stack_num_objects(stack) > bottom && status == REG_OK) + { + if (status != REG_OK) + break; + symbol = tre_stack_pop_int(stack); + switch (symbol) + { + case PARSE_RE: + /* Parse a full regexp. A regexp is one or more branches, + separated by the union operator `|'. */ + if (ctx->cflags & REG_EXTENDED) + STACK_PUSHX(stack, int, PARSE_UNION); + STACK_PUSHX(stack, int, PARSE_BRANCH); + break; + + case PARSE_BRANCH: + /* Parse a branch. A branch is one or more pieces, concatenated. + A piece is an atom possibly followed by a postfix operator. */ + STACK_PUSHX(stack, int, PARSE_CATENATION); + STACK_PUSHX(stack, int, PARSE_PIECE); + break; + + case PARSE_PIECE: + /* Parse a piece. A piece is an atom possibly followed by one + or more postfix operators. */ + STACK_PUSHX(stack, int, PARSE_POSTFIX); + STACK_PUSHX(stack, int, PARSE_ATOM); + break; + + case PARSE_CATENATION: + /* If the expression has not ended, parse another piece. */ + { + tre_char_t c; + if (!*ctx->re) + break; + c = *ctx->re; + if (ctx->cflags & REG_EXTENDED && c == CHAR_PIPE) + break; + if ((ctx->cflags & REG_EXTENDED + && c == CHAR_RPAREN && depth > 0) + || (!(ctx->cflags & REG_EXTENDED) + && (c == CHAR_BACKSLASH + && *(ctx->re + 1) == CHAR_RPAREN))) + { + if (!(ctx->cflags & REG_EXTENDED) && depth == 0) + status = REG_EPAREN; + depth--; + if (!(ctx->cflags & REG_EXTENDED)) + ctx->re += 2; + break; + } + + { + /* Default case, left associative concatenation. */ + STACK_PUSHX(stack, int, PARSE_CATENATION); + STACK_PUSHX(stack, voidptr, result); + STACK_PUSHX(stack, int, PARSE_POST_CATENATION); + STACK_PUSHX(stack, int, PARSE_PIECE); + } + break; + } + + case PARSE_POST_CATENATION: + { + tre_ast_node_t *tree = tre_stack_pop_voidptr(stack); + tre_ast_node_t *tmp_node; + tmp_node = tre_ast_new_catenation(ctx->mem, tree, result); + if (!tmp_node) + return REG_ESPACE; + result = tmp_node; + break; + } + + case PARSE_UNION: + switch (*ctx->re) + { + case CHAR_PIPE: + STACK_PUSHX(stack, int, PARSE_UNION); + STACK_PUSHX(stack, voidptr, result); + STACK_PUSHX(stack, int, PARSE_POST_UNION); + STACK_PUSHX(stack, int, PARSE_BRANCH); + ctx->re++; + break; + + case CHAR_RPAREN: + ctx->re++; + break; + + default: + break; + } + break; + + case PARSE_POST_UNION: + { + tre_ast_node_t *tmp_node; + tre_ast_node_t *tree = tre_stack_pop_voidptr(stack); + tmp_node = tre_ast_new_union(ctx->mem, tree, result); + if (!tmp_node) + return REG_ESPACE; + result = tmp_node; + break; + } + + case PARSE_POSTFIX: + /* Parse postfix operators. */ + switch (*ctx->re) + { + case CHAR_PLUS: + case CHAR_QUESTIONMARK: + if (!(ctx->cflags & REG_EXTENDED)) + break; + /*FALLTHROUGH*/ + case CHAR_STAR: + { + tre_ast_node_t *tmp_node; + int minimal = 0; + int rep_min = 0; + int rep_max = -1; + + if (*ctx->re == CHAR_PLUS) + rep_min = 1; + if (*ctx->re == CHAR_QUESTIONMARK) + rep_max = 1; + + ctx->re++; + tmp_node = tre_ast_new_iter(ctx->mem, result, rep_min, rep_max, + minimal); + if (tmp_node == NULL) + return REG_ESPACE; + result = tmp_node; + STACK_PUSHX(stack, int, PARSE_POSTFIX); + } + break; + + case CHAR_BACKSLASH: + /* "\{" is special without REG_EXTENDED */ + if (!(ctx->cflags & REG_EXTENDED) + && *(ctx->re + 1) == CHAR_LBRACE) + { + ctx->re++; + goto parse_brace; + } + else + break; + + case CHAR_LBRACE: + /* "{" is literal without REG_EXTENDED */ + if (!(ctx->cflags & REG_EXTENDED)) + break; + + parse_brace: + ctx->re++; + + status = tre_parse_bound(ctx, &result); + if (status != REG_OK) + return status; + STACK_PUSHX(stack, int, PARSE_POSTFIX); + break; + } + break; + + case PARSE_ATOM: + /* Parse an atom. An atom is a regular expression enclosed in `()', + an empty set of `()', a bracket expression, `.', `^', `$', + a `\' followed by a character, or a single character. */ + + switch (*ctx->re) + { + case CHAR_LPAREN: /* parenthesized subexpression */ + + if (ctx->cflags & REG_EXTENDED) + { + lparen: + depth++; + { + ctx->re++; + /* First parse a whole RE, then mark the resulting tree + for submatching. */ + STACK_PUSHX(stack, int, ctx->submatch_id); + STACK_PUSHX(stack, int, PARSE_MARK_FOR_SUBMATCH); + STACK_PUSHX(stack, int, PARSE_RE); + ctx->submatch_id++; + } + } + else + goto parse_literal; + break; + + case CHAR_LBRACKET: /* bracket expression */ + ctx->re++; + status = tre_parse_bracket(ctx, &result); + if (status != REG_OK) + return status; + break; + + case CHAR_BACKSLASH: + /* If this is "\(" or "\)" chew off the backslash and + try again. */ + if (!(ctx->cflags & REG_EXTENDED) && *(ctx->re + 1) == CHAR_LPAREN) + { + ctx->re++; + goto lparen; + } + if (!(ctx->cflags & REG_EXTENDED) && *(ctx->re + 1) == CHAR_RPAREN) + { + goto empty_atom; + } + + /* If a macro is used, parse the expanded macro recursively. */ + { + const char *buf = tre_expand_macro(ctx->re + 1); + if (buf) + { + tre_parse_ctx_t subctx; + memcpy(&subctx, ctx, sizeof(subctx)); + subctx.re = buf; + subctx.nofirstsub = 1; + status = tre_parse(&subctx); + if (status != REG_OK) + return status; + ctx->re += 2; + ctx->position = subctx.position; + result = subctx.result; + break; + } + } + + if (!ctx->re[1]) + /* Trailing backslash. */ + return REG_EESCAPE; + + ctx->re++; + switch (*ctx->re) + { + case 'b': + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_WB, -1); + ctx->re++; + break; + case 'B': + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_WB_NEG, -1); + ctx->re++; + break; + case '<': + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_BOW, -1); + ctx->re++; + break; + case '>': + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_EOW, -1); + ctx->re++; + break; + case 'x': + ctx->re++; + if (ctx->re[0] != CHAR_LBRACE) + { + /* 8 bit hex char. */ + char tmp[3] = {0, 0, 0}; + long val; + + if (tre_isxdigit(ctx->re[0])) + { + tmp[0] = (char)ctx->re[0]; + ctx->re++; + } + if (tre_isxdigit(ctx->re[0])) + { + tmp[1] = (char)ctx->re[0]; + ctx->re++; + } + val = strtol(tmp, NULL, 16); + result = tre_ast_new_literal(ctx->mem, (int)val, + (int)val, ctx->position); + ctx->position++; + break; + } + else if (*ctx->re) + { + /* Wide char. */ + char tmp[32]; + long val; + int i = 0; + ctx->re++; + while (*ctx->re && i < sizeof tmp) + { + if (ctx->re[0] == CHAR_RBRACE) + break; + if (tre_isxdigit(ctx->re[0])) + { + tmp[i] = (char)ctx->re[0]; + i++; + ctx->re++; + continue; + } + return REG_EBRACE; + } + ctx->re++; + tmp[i] = 0; + val = strtol(tmp, NULL, 16); + result = tre_ast_new_literal(ctx->mem, (int)val, (int)val, + ctx->position); + ctx->position++; + break; + } + /*FALLTHROUGH*/ + + default: + if (tre_isdigit(*ctx->re)) + { + /* Back reference. */ + int val = *ctx->re - '0'; + result = tre_ast_new_literal(ctx->mem, BACKREF, val, + ctx->position); + if (result == NULL) + return REG_ESPACE; + ctx->position++; + ctx->max_backref = MAX(val, ctx->max_backref); + ctx->re++; + } + else + { + /* Escaped character. */ + result = tre_ast_new_literal(ctx->mem, *ctx->re, *ctx->re, + ctx->position); + ctx->position++; + ctx->re++; + } + break; + } + if (result == NULL) + return REG_ESPACE; + break; + + case CHAR_PERIOD: /* the any-symbol */ + if (ctx->cflags & REG_NEWLINE) + { + tre_ast_node_t *tmp1; + tre_ast_node_t *tmp2; + tmp1 = tre_ast_new_literal(ctx->mem, 0, '\n' - 1, + ctx->position); + if (!tmp1) + return REG_ESPACE; + tmp2 = tre_ast_new_literal(ctx->mem, '\n' + 1, TRE_CHAR_MAX, + ctx->position + 1); + if (!tmp2) + return REG_ESPACE; + result = tre_ast_new_union(ctx->mem, tmp1, tmp2); + if (!result) + return REG_ESPACE; + ctx->position += 2; + } + else + { + result = tre_ast_new_literal(ctx->mem, 0, TRE_CHAR_MAX, + ctx->position); + if (!result) + return REG_ESPACE; + ctx->position++; + } + ctx->re++; + break; + + case CHAR_CARET: /* beginning of line assertion */ + /* '^' has a special meaning everywhere in EREs, and at + beginning of BRE. */ + if (ctx->cflags & REG_EXTENDED + || ctx->re == ctx->re_start) + { + if (!(ctx->cflags & REG_EXTENDED)) + STACK_PUSHX(stack, int, PARSE_CATENATION); + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_BOL, -1); + if (result == NULL) + return REG_ESPACE; + ctx->re++; + } + else + goto parse_literal; + break; + + case CHAR_DOLLAR: /* end of line assertion. */ + /* '$' is special everywhere in EREs, and in the end of the + string in BREs. */ + if (ctx->cflags & REG_EXTENDED + || !*(ctx->re + 1)) + { + result = tre_ast_new_literal(ctx->mem, ASSERTION, + ASSERT_AT_EOL, -1); + if (result == NULL) + return REG_ESPACE; + ctx->re++; + } + else + goto parse_literal; + break; + + case CHAR_RPAREN: + if (!depth) + goto parse_literal; + case CHAR_STAR: + case CHAR_PIPE: + case CHAR_LBRACE: + case CHAR_PLUS: + case CHAR_QUESTIONMARK: + if (!(ctx->cflags & REG_EXTENDED)) + goto parse_literal; + + case 0: + empty_atom: + result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1); + if (!result) + return REG_ESPACE; + break; + + default: + parse_literal: + + clen = mbtowc(&wc, ctx->re, -1); + if (clen<0) clen=1, wc=WEOF; + + /* Note that we can't use an tre_isalpha() test here, since there + may be characters which are alphabetic but neither upper or + lower case. */ + if (ctx->cflags & REG_ICASE + && (tre_isupper(wc) || tre_islower(wc))) + { + tre_ast_node_t *tmp1; + tre_ast_node_t *tmp2; + + /* XXX - Can there be more than one opposite-case + counterpoints for some character in some locale? Or + more than two characters which all should be regarded + the same character if case is ignored? If yes, there + does not seem to be a portable way to detect it. I guess + that at least for multi-character collating elements there + could be several opposite-case counterpoints, but they + cannot be supported portably anyway. */ + tmp1 = tre_ast_new_literal(ctx->mem, tre_toupper(wc), + tre_toupper(wc), + ctx->position); + if (!tmp1) + return REG_ESPACE; + tmp2 = tre_ast_new_literal(ctx->mem, tre_tolower(wc), + tre_tolower(wc), + ctx->position); + if (!tmp2) + return REG_ESPACE; + result = tre_ast_new_union(ctx->mem, tmp1, tmp2); + if (!result) + return REG_ESPACE; + } + else + { + result = tre_ast_new_literal(ctx->mem, wc, wc, + ctx->position); + if (!result) + return REG_ESPACE; + } + ctx->position++; + ctx->re += clen; + break; + } + break; + + case PARSE_MARK_FOR_SUBMATCH: + { + int submatch_id = tre_stack_pop_int(stack); + + if (result->submatch_id >= 0) + { + tre_ast_node_t *n, *tmp_node; + n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1); + if (n == NULL) + return REG_ESPACE; + tmp_node = tre_ast_new_catenation(ctx->mem, n, result); + if (tmp_node == NULL) + return REG_ESPACE; + tmp_node->num_submatches = result->num_submatches; + result = tmp_node; + } + result->submatch_id = submatch_id; + result->num_submatches++; + break; + } + + case PARSE_RESTORE_CFLAGS: + ctx->cflags = tre_stack_pop_int(stack); + break; + + default: + assert(0); + break; + } + } + + /* Check for missing closing parentheses. */ + if (depth > 0) + return REG_EPAREN; + + if (status == REG_OK) + ctx->result = result; + + return status; +} + + + +/*********************************************************************** + from tre-compile.c +***********************************************************************/ + + +/* + TODO: + - Fix tre_ast_to_tnfa() to recurse using a stack instead of recursive + function calls. +*/ + +/* + Algorithms to setup tags so that submatch addressing can be done. +*/ + + +/* Inserts a catenation node to the root of the tree given in `node'. + As the left child a new tag with number `tag_id' to `node' is added, + and the right child is the old root. */ +static reg_errcode_t +tre_add_tag_left(tre_mem_t mem, tre_ast_node_t *node, int tag_id) +{ + tre_catenation_t *c; + + c = tre_mem_alloc(mem, sizeof(*c)); + if (c == NULL) + return REG_ESPACE; + c->left = tre_ast_new_literal(mem, TAG, tag_id, -1); + if (c->left == NULL) + return REG_ESPACE; + c->right = tre_mem_alloc(mem, sizeof(tre_ast_node_t)); + if (c->right == NULL) + return REG_ESPACE; + + c->right->obj = node->obj; + c->right->type = node->type; + c->right->nullable = -1; + c->right->submatch_id = -1; + c->right->firstpos = NULL; + c->right->lastpos = NULL; + c->right->num_tags = 0; + node->obj = c; + node->type = CATENATION; + return REG_OK; +} + +/* Inserts a catenation node to the root of the tree given in `node'. + As the right child a new tag with number `tag_id' to `node' is added, + and the left child is the old root. */ +static reg_errcode_t +tre_add_tag_right(tre_mem_t mem, tre_ast_node_t *node, int tag_id) +{ + tre_catenation_t *c; + + c = tre_mem_alloc(mem, sizeof(*c)); + if (c == NULL) + return REG_ESPACE; + c->right = tre_ast_new_literal(mem, TAG, tag_id, -1); + if (c->right == NULL) + return REG_ESPACE; + c->left = tre_mem_alloc(mem, sizeof(tre_ast_node_t)); + if (c->left == NULL) + return REG_ESPACE; + + c->left->obj = node->obj; + c->left->type = node->type; + c->left->nullable = -1; + c->left->submatch_id = -1; + c->left->firstpos = NULL; + c->left->lastpos = NULL; + c->left->num_tags = 0; + node->obj = c; + node->type = CATENATION; + return REG_OK; +} + +typedef enum { + ADDTAGS_RECURSE, + ADDTAGS_AFTER_ITERATION, + ADDTAGS_AFTER_UNION_LEFT, + ADDTAGS_AFTER_UNION_RIGHT, + ADDTAGS_AFTER_CAT_LEFT, + ADDTAGS_AFTER_CAT_RIGHT, + ADDTAGS_SET_SUBMATCH_END +} tre_addtags_symbol_t; + + +typedef struct { + int tag; + int next_tag; +} tre_tag_states_t; + + +/* Go through `regset' and set submatch data for submatches that are + using this tag. */ +static void +tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag) +{ + int i; + + for (i = 0; regset[i] >= 0; i++) + { + int id = regset[i] / 2; + int start = !(regset[i] % 2); + if (start) + tnfa->submatch_data[id].so_tag = tag; + else + tnfa->submatch_data[id].eo_tag = tag; + } + regset[0] = -1; +} + + +/* Adds tags to appropriate locations in the parse tree in `tree', so that + subexpressions marked for submatch addressing can be traced. */ +static reg_errcode_t +tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree, + tre_tnfa_t *tnfa) +{ + reg_errcode_t status = REG_OK; + tre_addtags_symbol_t symbol; + tre_ast_node_t *node = tree; /* Tree node we are currently looking at. */ + int bottom = tre_stack_num_objects(stack); + /* True for first pass (counting number of needed tags) */ + int first_pass = (mem == NULL || tnfa == NULL); + int *regset, *orig_regset; + int num_tags = 0; /* Total number of tags. */ + int num_minimals = 0; /* Number of special minimal tags. */ + int tag = 0; /* The tag that is to be added next. */ + int next_tag = 1; /* Next tag to use after this one. */ + int *parents; /* Stack of submatches the current submatch is + contained in. */ + int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */ + tre_tag_states_t *saved_states; + + tre_tag_direction_t direction = TRE_TAG_MINIMIZE; + if (!first_pass) + { + tnfa->end_tag = 0; + tnfa->minimal_tags[0] = -1; + } + + regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2)); + if (regset == NULL) + return REG_ESPACE; + regset[0] = -1; + orig_regset = regset; + + parents = xmalloc(sizeof(*parents) * (tnfa->num_submatches + 1)); + if (parents == NULL) + { + xfree(regset); + return REG_ESPACE; + } + parents[0] = -1; + + saved_states = xmalloc(sizeof(*saved_states) * (tnfa->num_submatches + 1)); + if (saved_states == NULL) + { + xfree(regset); + xfree(parents); + return REG_ESPACE; + } + else + { + unsigned int i; + for (i = 0; i <= tnfa->num_submatches; i++) + saved_states[i].tag = -1; + } + + STACK_PUSH(stack, voidptr, node); + STACK_PUSH(stack, int, ADDTAGS_RECURSE); + + while (tre_stack_num_objects(stack) > bottom) + { + if (status != REG_OK) + break; + + symbol = (tre_addtags_symbol_t)tre_stack_pop_int(stack); + switch (symbol) + { + + case ADDTAGS_SET_SUBMATCH_END: + { + int id = tre_stack_pop_int(stack); + int i; + + /* Add end of this submatch to regset. */ + for (i = 0; regset[i] >= 0; i++); + regset[i] = id * 2 + 1; + regset[i + 1] = -1; + + /* Pop this submatch from the parents stack. */ + for (i = 0; parents[i] >= 0; i++); + parents[i - 1] = -1; + break; + } + + case ADDTAGS_RECURSE: + node = tre_stack_pop_voidptr(stack); + + if (node->submatch_id >= 0) + { + int id = node->submatch_id; + int i; + + + /* Add start of this submatch to regset. */ + for (i = 0; regset[i] >= 0; i++); + regset[i] = id * 2; + regset[i + 1] = -1; + + if (!first_pass) + { + for (i = 0; parents[i] >= 0; i++); + tnfa->submatch_data[id].parents = NULL; + if (i > 0) + { + int *p = xmalloc(sizeof(*p) * (i + 1)); + if (p == NULL) + { + status = REG_ESPACE; + break; + } + assert(tnfa->submatch_data[id].parents == NULL); + tnfa->submatch_data[id].parents = p; + for (i = 0; parents[i] >= 0; i++) + p[i] = parents[i]; + p[i] = -1; + } + } + + /* Add end of this submatch to regset after processing this + node. */ + STACK_PUSHX(stack, int, node->submatch_id); + STACK_PUSHX(stack, int, ADDTAGS_SET_SUBMATCH_END); + } + + switch (node->type) + { + case LITERAL: + { + tre_literal_t *lit = node->obj; + + if (!IS_SPECIAL(lit) || IS_BACKREF(lit)) + { + int i; + if (regset[0] >= 0) + { + /* Regset is not empty, so add a tag before the + literal or backref. */ + if (!first_pass) + { + status = tre_add_tag_left(mem, node, tag); + tnfa->tag_directions[tag] = direction; + if (minimal_tag >= 0) + { + for (i = 0; tnfa->minimal_tags[i] >= 0; i++); + tnfa->minimal_tags[i] = tag; + tnfa->minimal_tags[i + 1] = minimal_tag; + tnfa->minimal_tags[i + 2] = -1; + minimal_tag = -1; + num_minimals++; + } + tre_purge_regset(regset, tnfa, tag); + } + else + { + node->num_tags = 1; + } + + regset[0] = -1; + tag = next_tag; + num_tags++; + next_tag++; + } + } + else + { + assert(!IS_TAG(lit)); + } + break; + } + case CATENATION: + { + tre_catenation_t *cat = node->obj; + tre_ast_node_t *left = cat->left; + tre_ast_node_t *right = cat->right; + int reserved_tag = -1; + + + /* After processing right child. */ + STACK_PUSHX(stack, voidptr, node); + STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_RIGHT); + + /* Process right child. */ + STACK_PUSHX(stack, voidptr, right); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + /* After processing left child. */ + STACK_PUSHX(stack, int, next_tag + left->num_tags); + if (left->num_tags > 0 && right->num_tags > 0) + { + /* Reserve the next tag to the right child. */ + reserved_tag = next_tag; + next_tag++; + } + STACK_PUSHX(stack, int, reserved_tag); + STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_LEFT); + + /* Process left child. */ + STACK_PUSHX(stack, voidptr, left); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + } + break; + case ITERATION: + { + tre_iteration_t *iter = node->obj; + + if (first_pass) + { + STACK_PUSHX(stack, int, regset[0] >= 0 || iter->minimal); + } + else + { + STACK_PUSHX(stack, int, tag); + STACK_PUSHX(stack, int, iter->minimal); + } + STACK_PUSHX(stack, voidptr, node); + STACK_PUSHX(stack, int, ADDTAGS_AFTER_ITERATION); + + STACK_PUSHX(stack, voidptr, iter->arg); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + /* Regset is not empty, so add a tag here. */ + if (regset[0] >= 0 || iter->minimal) + { + if (!first_pass) + { + int i; + status = tre_add_tag_left(mem, node, tag); + if (iter->minimal) + tnfa->tag_directions[tag] = TRE_TAG_MAXIMIZE; + else + tnfa->tag_directions[tag] = direction; + if (minimal_tag >= 0) + { + for (i = 0; tnfa->minimal_tags[i] >= 0; i++); + tnfa->minimal_tags[i] = tag; + tnfa->minimal_tags[i + 1] = minimal_tag; + tnfa->minimal_tags[i + 2] = -1; + minimal_tag = -1; + num_minimals++; + } + tre_purge_regset(regset, tnfa, tag); + } + + regset[0] = -1; + tag = next_tag; + num_tags++; + next_tag++; + } + direction = TRE_TAG_MINIMIZE; + } + break; + case UNION: + { + tre_union_t *uni = node->obj; + tre_ast_node_t *left = uni->left; + tre_ast_node_t *right = uni->right; + int left_tag; + int right_tag; + + if (regset[0] >= 0) + { + left_tag = next_tag; + right_tag = next_tag + 1; + } + else + { + left_tag = tag; + right_tag = next_tag; + } + + /* After processing right child. */ + STACK_PUSHX(stack, int, right_tag); + STACK_PUSHX(stack, int, left_tag); + STACK_PUSHX(stack, voidptr, regset); + STACK_PUSHX(stack, int, regset[0] >= 0); + STACK_PUSHX(stack, voidptr, node); + STACK_PUSHX(stack, voidptr, right); + STACK_PUSHX(stack, voidptr, left); + STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT); + + /* Process right child. */ + STACK_PUSHX(stack, voidptr, right); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + /* After processing left child. */ + STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT); + + /* Process left child. */ + STACK_PUSHX(stack, voidptr, left); + STACK_PUSHX(stack, int, ADDTAGS_RECURSE); + + /* Regset is not empty, so add a tag here. */ + if (regset[0] >= 0) + { + if (!first_pass) + { + int i; + status = tre_add_tag_left(mem, node, tag); + tnfa->tag_directions[tag] = direction; + if (minimal_tag >= 0) + { + for (i = 0; tnfa->minimal_tags[i] >= 0; i++); + tnfa->minimal_tags[i] = tag; + tnfa->minimal_tags[i + 1] = minimal_tag; + tnfa->minimal_tags[i + 2] = -1; + minimal_tag = -1; + num_minimals++; + } + tre_purge_regset(regset, tnfa, tag); + } + + regset[0] = -1; + tag = next_tag; + num_tags++; + next_tag++; + } + + if (node->num_submatches > 0) + { + /* The next two tags are reserved for markers. */ + next_tag++; + tag = next_tag; + next_tag++; + } + + break; + } + } + + if (node->submatch_id >= 0) + { + int i; + /* Push this submatch on the parents stack. */ + for (i = 0; parents[i] >= 0; i++); + parents[i] = node->submatch_id; + parents[i + 1] = -1; + } + + break; /* end case: ADDTAGS_RECURSE */ + + case ADDTAGS_AFTER_ITERATION: + { + int minimal = 0; + int enter_tag; + node = tre_stack_pop_voidptr(stack); + if (first_pass) + { + node->num_tags = ((tre_iteration_t *)node->obj)->arg->num_tags + + tre_stack_pop_int(stack); + minimal_tag = -1; + } + else + { + minimal = tre_stack_pop_int(stack); + enter_tag = tre_stack_pop_int(stack); + if (minimal) + minimal_tag = enter_tag; + } + + if (!first_pass) + { + if (minimal) + direction = TRE_TAG_MINIMIZE; + else + direction = TRE_TAG_MAXIMIZE; + } + break; + } + + case ADDTAGS_AFTER_CAT_LEFT: + { + int new_tag = tre_stack_pop_int(stack); + next_tag = tre_stack_pop_int(stack); + if (new_tag >= 0) + { + tag = new_tag; + } + break; + } + + case ADDTAGS_AFTER_CAT_RIGHT: + node = tre_stack_pop_voidptr(stack); + if (first_pass) + node->num_tags = ((tre_catenation_t *)node->obj)->left->num_tags + + ((tre_catenation_t *)node->obj)->right->num_tags; + break; + + case ADDTAGS_AFTER_UNION_LEFT: + /* Lift the bottom of the `regset' array so that when processing + the right operand the items currently in the array are + invisible. The original bottom was saved at ADDTAGS_UNION and + will be restored at ADDTAGS_AFTER_UNION_RIGHT below. */ + while (*regset >= 0) + regset++; + break; + + case ADDTAGS_AFTER_UNION_RIGHT: + { + int added_tags, tag_left, tag_right; + tre_ast_node_t *left = tre_stack_pop_voidptr(stack); + tre_ast_node_t *right = tre_stack_pop_voidptr(stack); + node = tre_stack_pop_voidptr(stack); + added_tags = tre_stack_pop_int(stack); + if (first_pass) + { + node->num_tags = ((tre_union_t *)node->obj)->left->num_tags + + ((tre_union_t *)node->obj)->right->num_tags + added_tags + + ((node->num_submatches > 0) ? 2 : 0); + } + regset = tre_stack_pop_voidptr(stack); + tag_left = tre_stack_pop_int(stack); + tag_right = tre_stack_pop_int(stack); + + /* Add tags after both children, the left child gets a smaller + tag than the right child. This guarantees that we prefer + the left child over the right child. */ + /* XXX - This is not always necessary (if the children have + tags which must be seen for every match of that child). */ + /* XXX - Check if this is the only place where tre_add_tag_right + is used. If so, use tre_add_tag_left (putting the tag before + the child as opposed after the child) and throw away + tre_add_tag_right. */ + if (node->num_submatches > 0) + { + if (!first_pass) + { + status = tre_add_tag_right(mem, left, tag_left); + tnfa->tag_directions[tag_left] = TRE_TAG_MAXIMIZE; + status = tre_add_tag_right(mem, right, tag_right); + tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE; + } + num_tags += 2; + } + direction = TRE_TAG_MAXIMIZE; + break; + } + + default: + assert(0); + break; + + } /* end switch(symbol) */ + } /* end while(tre_stack_num_objects(stack) > bottom) */ + + if (!first_pass) + tre_purge_regset(regset, tnfa, tag); + + if (!first_pass && minimal_tag >= 0) + { + int i; + for (i = 0; tnfa->minimal_tags[i] >= 0; i++); + tnfa->minimal_tags[i] = tag; + tnfa->minimal_tags[i + 1] = minimal_tag; + tnfa->minimal_tags[i + 2] = -1; + minimal_tag = -1; + num_minimals++; + } + + assert(tree->num_tags == num_tags); + tnfa->end_tag = num_tags; + tnfa->num_tags = num_tags; + tnfa->num_minimals = num_minimals; + xfree(orig_regset); + xfree(parents); + xfree(saved_states); + return status; +} + + + +/* + AST to TNFA compilation routines. +*/ + +typedef enum { + COPY_RECURSE, + COPY_SET_RESULT_PTR +} tre_copyast_symbol_t; + +/* Flags for tre_copy_ast(). */ +#define COPY_REMOVE_TAGS 1 +#define COPY_MAXIMIZE_FIRST_TAG 2 + +static reg_errcode_t +tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast, + int flags, int *pos_add, tre_tag_direction_t *tag_directions, + tre_ast_node_t **copy, int *max_pos) +{ + reg_errcode_t status = REG_OK; + int bottom = tre_stack_num_objects(stack); + int num_copied = 0; + int first_tag = 1; + tre_ast_node_t **result = copy; + tre_copyast_symbol_t symbol; + + STACK_PUSH(stack, voidptr, ast); + STACK_PUSH(stack, int, COPY_RECURSE); + + while (status == REG_OK && tre_stack_num_objects(stack) > bottom) + { + tre_ast_node_t *node; + if (status != REG_OK) + break; + + symbol = (tre_copyast_symbol_t)tre_stack_pop_int(stack); + switch (symbol) + { + case COPY_SET_RESULT_PTR: + result = tre_stack_pop_voidptr(stack); + break; + case COPY_RECURSE: + node = tre_stack_pop_voidptr(stack); + switch (node->type) + { + case LITERAL: + { + tre_literal_t *lit = node->obj; + int pos = lit->position; + int min = lit->code_min; + int max = lit->code_max; + if (!IS_SPECIAL(lit) || IS_BACKREF(lit)) + { + /* XXX - e.g. [ab] has only one position but two + nodes, so we are creating holes in the state space + here. Not fatal, just wastes memory. */ + pos += *pos_add; + num_copied++; + } + else if (IS_TAG(lit) && (flags & COPY_REMOVE_TAGS)) + { + /* Change this tag to empty. */ + min = EMPTY; + max = pos = -1; + } + else if (IS_TAG(lit) && (flags & COPY_MAXIMIZE_FIRST_TAG) + && first_tag) + { + /* Maximize the first tag. */ + tag_directions[max] = TRE_TAG_MAXIMIZE; + first_tag = 0; + } + *result = tre_ast_new_literal(mem, min, max, pos); + if (*result == NULL) + status = REG_ESPACE; + + if (pos > *max_pos) + *max_pos = pos; + break; + } + case UNION: + { + tre_union_t *uni = node->obj; + tre_union_t *tmp; + *result = tre_ast_new_union(mem, uni->left, uni->right); + if (*result == NULL) + { + status = REG_ESPACE; + break; + } + tmp = (*result)->obj; + result = &tmp->left; + STACK_PUSHX(stack, voidptr, uni->right); + STACK_PUSHX(stack, int, COPY_RECURSE); + STACK_PUSHX(stack, voidptr, &tmp->right); + STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR); + STACK_PUSHX(stack, voidptr, uni->left); + STACK_PUSHX(stack, int, COPY_RECURSE); + break; + } + case CATENATION: + { + tre_catenation_t *cat = node->obj; + tre_catenation_t *tmp; + *result = tre_ast_new_catenation(mem, cat->left, cat->right); + if (*result == NULL) + { + status = REG_ESPACE; + break; + } + tmp = (*result)->obj; + tmp->left = NULL; + tmp->right = NULL; + result = &tmp->left; + + STACK_PUSHX(stack, voidptr, cat->right); + STACK_PUSHX(stack, int, COPY_RECURSE); + STACK_PUSHX(stack, voidptr, &tmp->right); + STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR); + STACK_PUSHX(stack, voidptr, cat->left); + STACK_PUSHX(stack, int, COPY_RECURSE); + break; + } + case ITERATION: + { + tre_iteration_t *iter = node->obj; + STACK_PUSHX(stack, voidptr, iter->arg); + STACK_PUSHX(stack, int, COPY_RECURSE); + *result = tre_ast_new_iter(mem, iter->arg, iter->min, + iter->max, iter->minimal); + if (*result == NULL) + { + status = REG_ESPACE; + break; + } + iter = (*result)->obj; + result = &iter->arg; + break; + } + default: + assert(0); + break; + } + break; + } + } + *pos_add += num_copied; + return status; +} + +typedef enum { + EXPAND_RECURSE, + EXPAND_AFTER_ITER +} tre_expand_ast_symbol_t; + +/* Expands each iteration node that has a finite nonzero minimum or maximum + iteration count to a catenated sequence of copies of the node. */ +static reg_errcode_t +tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast, + int *position, tre_tag_direction_t *tag_directions) +{ + reg_errcode_t status = REG_OK; + int bottom = tre_stack_num_objects(stack); + int pos_add = 0; + int pos_add_total = 0; + int max_pos = 0; + int iter_depth = 0; + + STACK_PUSHR(stack, voidptr, ast); + STACK_PUSHR(stack, int, EXPAND_RECURSE); + while (status == REG_OK && tre_stack_num_objects(stack) > bottom) + { + tre_ast_node_t *node; + tre_expand_ast_symbol_t symbol; + + if (status != REG_OK) + break; + + symbol = (tre_expand_ast_symbol_t)tre_stack_pop_int(stack); + node = tre_stack_pop_voidptr(stack); + switch (symbol) + { + case EXPAND_RECURSE: + switch (node->type) + { + case LITERAL: + { + tre_literal_t *lit= node->obj; + if (!IS_SPECIAL(lit) || IS_BACKREF(lit)) + { + lit->position += pos_add; + if (lit->position > max_pos) + max_pos = lit->position; + } + break; + } + case UNION: + { + tre_union_t *uni = node->obj; + STACK_PUSHX(stack, voidptr, uni->right); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + STACK_PUSHX(stack, voidptr, uni->left); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + break; + } + case CATENATION: + { + tre_catenation_t *cat = node->obj; + STACK_PUSHX(stack, voidptr, cat->right); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + STACK_PUSHX(stack, voidptr, cat->left); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + break; + } + case ITERATION: + { + tre_iteration_t *iter = node->obj; + STACK_PUSHX(stack, int, pos_add); + STACK_PUSHX(stack, voidptr, node); + STACK_PUSHX(stack, int, EXPAND_AFTER_ITER); + STACK_PUSHX(stack, voidptr, iter->arg); + STACK_PUSHX(stack, int, EXPAND_RECURSE); + /* If we are going to expand this node at EXPAND_AFTER_ITER + then don't increase the `pos' fields of the nodes now, it + will get done when expanding. */ + if (iter->min > 1 || iter->max > 1) + pos_add = 0; + iter_depth++; + break; + } + default: + assert(0); + break; + } + break; + case EXPAND_AFTER_ITER: + { + tre_iteration_t *iter = node->obj; + int pos_add_last; + pos_add = tre_stack_pop_int(stack); + pos_add_last = pos_add; + if (iter->min > 1 || iter->max > 1) + { + tre_ast_node_t *seq1 = NULL, *seq2 = NULL; + int j; + int pos_add_save = pos_add; + + /* Create a catenated sequence of copies of the node. */ + for (j = 0; j < iter->min; j++) + { + tre_ast_node_t *copy; + /* Remove tags from all but the last copy. */ + int flags = ((j + 1 < iter->min) + ? COPY_REMOVE_TAGS + : COPY_MAXIMIZE_FIRST_TAG); + pos_add_save = pos_add; + status = tre_copy_ast(mem, stack, iter->arg, flags, + &pos_add, tag_directions, ©, + &max_pos); + if (status != REG_OK) + return status; + if (seq1 != NULL) + seq1 = tre_ast_new_catenation(mem, seq1, copy); + else + seq1 = copy; + if (seq1 == NULL) + return REG_ESPACE; + } + + if (iter->max == -1) + { + /* No upper limit. */ + pos_add_save = pos_add; + status = tre_copy_ast(mem, stack, iter->arg, 0, + &pos_add, NULL, &seq2, &max_pos); + if (status != REG_OK) + return status; + seq2 = tre_ast_new_iter(mem, seq2, 0, -1, 0); + if (seq2 == NULL) + return REG_ESPACE; + } + else + { + for (j = iter->min; j < iter->max; j++) + { + tre_ast_node_t *tmp, *copy; + pos_add_save = pos_add; + status = tre_copy_ast(mem, stack, iter->arg, 0, + &pos_add, NULL, ©, &max_pos); + if (status != REG_OK) + return status; + if (seq2 != NULL) + seq2 = tre_ast_new_catenation(mem, copy, seq2); + else + seq2 = copy; + if (seq2 == NULL) + return REG_ESPACE; + tmp = tre_ast_new_literal(mem, EMPTY, -1, -1); + if (tmp == NULL) + return REG_ESPACE; + seq2 = tre_ast_new_union(mem, tmp, seq2); + if (seq2 == NULL) + return REG_ESPACE; + } + } + + pos_add = pos_add_save; + if (seq1 == NULL) + seq1 = seq2; + else if (seq2 != NULL) + seq1 = tre_ast_new_catenation(mem, seq1, seq2); + if (seq1 == NULL) + return REG_ESPACE; + node->obj = seq1->obj; + node->type = seq1->type; + } + + iter_depth--; + pos_add_total += pos_add - pos_add_last; + if (iter_depth == 0) + pos_add = pos_add_total; + + break; + } + default: + assert(0); + break; + } + } + + *position += pos_add_total; + + /* `max_pos' should never be larger than `*position' if the above + code works, but just an extra safeguard let's make sure + `*position' is set large enough so enough memory will be + allocated for the transition table. */ + if (max_pos > *position) + *position = max_pos; + + return status; +} + +static tre_pos_and_tags_t * +tre_set_empty(tre_mem_t mem) +{ + tre_pos_and_tags_t *new_set; + + new_set = tre_mem_calloc(mem, sizeof(*new_set)); + if (new_set == NULL) + return NULL; + + new_set[0].position = -1; + new_set[0].code_min = -1; + new_set[0].code_max = -1; + + return new_set; +} + +static tre_pos_and_tags_t * +tre_set_one(tre_mem_t mem, int position, int code_min, int code_max, + tre_ctype_t class, tre_ctype_t *neg_classes, int backref) +{ + tre_pos_and_tags_t *new_set; + + new_set = tre_mem_calloc(mem, sizeof(*new_set) * 2); + if (new_set == NULL) + return NULL; + + new_set[0].position = position; + new_set[0].code_min = code_min; + new_set[0].code_max = code_max; + new_set[0].class = class; + new_set[0].neg_classes = neg_classes; + new_set[0].backref = backref; + new_set[1].position = -1; + new_set[1].code_min = -1; + new_set[1].code_max = -1; + + return new_set; +} + +static tre_pos_and_tags_t * +tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2, + int *tags, int assertions) +{ + int s1, s2, i, j; + tre_pos_and_tags_t *new_set; + int *new_tags; + int num_tags; + + for (num_tags = 0; tags != NULL && tags[num_tags] >= 0; num_tags++); + for (s1 = 0; set1[s1].position >= 0; s1++); + for (s2 = 0; set2[s2].position >= 0; s2++); + new_set = tre_mem_calloc(mem, sizeof(*new_set) * (s1 + s2 + 1)); + if (!new_set ) + return NULL; + + for (s1 = 0; set1[s1].position >= 0; s1++) + { + new_set[s1].position = set1[s1].position; + new_set[s1].code_min = set1[s1].code_min; + new_set[s1].code_max = set1[s1].code_max; + new_set[s1].assertions = set1[s1].assertions | assertions; + new_set[s1].class = set1[s1].class; + new_set[s1].neg_classes = set1[s1].neg_classes; + new_set[s1].backref = set1[s1].backref; + if (set1[s1].tags == NULL && tags == NULL) + new_set[s1].tags = NULL; + else + { + for (i = 0; set1[s1].tags != NULL && set1[s1].tags[i] >= 0; i++); + new_tags = tre_mem_alloc(mem, (sizeof(*new_tags) + * (i + num_tags + 1))); + if (new_tags == NULL) + return NULL; + for (j = 0; j < i; j++) + new_tags[j] = set1[s1].tags[j]; + for (i = 0; i < num_tags; i++) + new_tags[j + i] = tags[i]; + new_tags[j + i] = -1; + new_set[s1].tags = new_tags; + } + } + + for (s2 = 0; set2[s2].position >= 0; s2++) + { + new_set[s1 + s2].position = set2[s2].position; + new_set[s1 + s2].code_min = set2[s2].code_min; + new_set[s1 + s2].code_max = set2[s2].code_max; + /* XXX - why not | assertions here as well? */ + new_set[s1 + s2].assertions = set2[s2].assertions; + new_set[s1 + s2].class = set2[s2].class; + new_set[s1 + s2].neg_classes = set2[s2].neg_classes; + new_set[s1 + s2].backref = set2[s2].backref; + if (set2[s2].tags == NULL) + new_set[s1 + s2].tags = NULL; + else + { + for (i = 0; set2[s2].tags[i] >= 0; i++); + new_tags = tre_mem_alloc(mem, sizeof(*new_tags) * (i + 1)); + if (new_tags == NULL) + return NULL; + for (j = 0; j < i; j++) + new_tags[j] = set2[s2].tags[j]; + new_tags[j] = -1; + new_set[s1 + s2].tags = new_tags; + } + } + new_set[s1 + s2].position = -1; + return new_set; +} + +/* Finds the empty path through `node' which is the one that should be + taken according to POSIX.2 rules, and adds the tags on that path to + `tags'. `tags' may be NULL. If `num_tags_seen' is not NULL, it is + set to the number of tags seen on the path. */ +static reg_errcode_t +tre_match_empty(tre_stack_t *stack, tre_ast_node_t *node, int *tags, + int *assertions, int *num_tags_seen) +{ + tre_literal_t *lit; + tre_union_t *uni; + tre_catenation_t *cat; + tre_iteration_t *iter; + int i; + int bottom = tre_stack_num_objects(stack); + reg_errcode_t status = REG_OK; + if (num_tags_seen) + *num_tags_seen = 0; + + status = tre_stack_push_voidptr(stack, node); + + /* Walk through the tree recursively. */ + while (status == REG_OK && tre_stack_num_objects(stack) > bottom) + { + node = tre_stack_pop_voidptr(stack); + + switch (node->type) + { + case LITERAL: + lit = (tre_literal_t *)node->obj; + switch (lit->code_min) + { + case TAG: + if (lit->code_max >= 0) + { + if (tags != NULL) + { + /* Add the tag to `tags'. */ + for (i = 0; tags[i] >= 0; i++) + if (tags[i] == lit->code_max) + break; + if (tags[i] < 0) + { + tags[i] = lit->code_max; + tags[i + 1] = -1; + } + } + if (num_tags_seen) + (*num_tags_seen)++; + } + break; + case ASSERTION: + assert(lit->code_max >= 1 + || lit->code_max <= ASSERT_LAST); + if (assertions != NULL) + *assertions |= lit->code_max; + break; + case EMPTY: + break; + default: + assert(0); + break; + } + break; + + case UNION: + /* Subexpressions starting earlier take priority over ones + starting later, so we prefer the left subexpression over the + right subexpression. */ + uni = (tre_union_t *)node->obj; + if (uni->left->nullable) + STACK_PUSHX(stack, voidptr, uni->left) + else if (uni->right->nullable) + STACK_PUSHX(stack, voidptr, uni->right) + else + assert(0); + break; + + case CATENATION: + /* The path must go through both children. */ + cat = (tre_catenation_t *)node->obj; + assert(cat->left->nullable); + assert(cat->right->nullable); + STACK_PUSHX(stack, voidptr, cat->left); + STACK_PUSHX(stack, voidptr, cat->right); + break; + + case ITERATION: + /* A match with an empty string is preferred over no match at + all, so we go through the argument if possible. */ + iter = (tre_iteration_t *)node->obj; + if (iter->arg->nullable) + STACK_PUSHX(stack, voidptr, iter->arg); + break; + + default: + assert(0); + break; + } + } + + return status; +} + + +typedef enum { + NFL_RECURSE, + NFL_POST_UNION, + NFL_POST_CATENATION, + NFL_POST_ITERATION +} tre_nfl_stack_symbol_t; + + +/* Computes and fills in the fields `nullable', `firstpos', and `lastpos' for + the nodes of the AST `tree'. */ +static reg_errcode_t +tre_compute_nfl(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree) +{ + int bottom = tre_stack_num_objects(stack); + + STACK_PUSHR(stack, voidptr, tree); + STACK_PUSHR(stack, int, NFL_RECURSE); + + while (tre_stack_num_objects(stack) > bottom) + { + tre_nfl_stack_symbol_t symbol; + tre_ast_node_t *node; + + symbol = (tre_nfl_stack_symbol_t)tre_stack_pop_int(stack); + node = tre_stack_pop_voidptr(stack); + switch (symbol) + { + case NFL_RECURSE: + switch (node->type) + { + case LITERAL: + { + tre_literal_t *lit = (tre_literal_t *)node->obj; + if (IS_BACKREF(lit)) + { + /* Back references: nullable = false, firstpos = {i}, + lastpos = {i}. */ + node->nullable = 0; + node->firstpos = tre_set_one(mem, lit->position, 0, + TRE_CHAR_MAX, 0, NULL, -1); + if (!node->firstpos) + return REG_ESPACE; + node->lastpos = tre_set_one(mem, lit->position, 0, + TRE_CHAR_MAX, 0, NULL, + (int)lit->code_max); + if (!node->lastpos) + return REG_ESPACE; + } + else if (lit->code_min < 0) + { + /* Tags, empty strings, params, and zero width assertions: + nullable = true, firstpos = {}, and lastpos = {}. */ + node->nullable = 1; + node->firstpos = tre_set_empty(mem); + if (!node->firstpos) + return REG_ESPACE; + node->lastpos = tre_set_empty(mem); + if (!node->lastpos) + return REG_ESPACE; + } + else + { + /* Literal at position i: nullable = false, firstpos = {i}, + lastpos = {i}. */ + node->nullable = 0; + node->firstpos = + tre_set_one(mem, lit->position, (int)lit->code_min, + (int)lit->code_max, 0, NULL, -1); + if (!node->firstpos) + return REG_ESPACE; + node->lastpos = tre_set_one(mem, lit->position, + (int)lit->code_min, + (int)lit->code_max, + lit->class, lit->neg_classes, + -1); + if (!node->lastpos) + return REG_ESPACE; + } + break; + } + + case UNION: + /* Compute the attributes for the two subtrees, and after that + for this node. */ + STACK_PUSHR(stack, voidptr, node); + STACK_PUSHR(stack, int, NFL_POST_UNION); + STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->right); + STACK_PUSHR(stack, int, NFL_RECURSE); + STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->left); + STACK_PUSHR(stack, int, NFL_RECURSE); + break; + + case CATENATION: + /* Compute the attributes for the two subtrees, and after that + for this node. */ + STACK_PUSHR(stack, voidptr, node); + STACK_PUSHR(stack, int, NFL_POST_CATENATION); + STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->right); + STACK_PUSHR(stack, int, NFL_RECURSE); + STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->left); + STACK_PUSHR(stack, int, NFL_RECURSE); + break; + + case ITERATION: + /* Compute the attributes for the subtree, and after that for + this node. */ + STACK_PUSHR(stack, voidptr, node); + STACK_PUSHR(stack, int, NFL_POST_ITERATION); + STACK_PUSHR(stack, voidptr, ((tre_iteration_t *)node->obj)->arg); + STACK_PUSHR(stack, int, NFL_RECURSE); + break; + } + break; /* end case: NFL_RECURSE */ + + case NFL_POST_UNION: + { + tre_union_t *uni = (tre_union_t *)node->obj; + node->nullable = uni->left->nullable || uni->right->nullable; + node->firstpos = tre_set_union(mem, uni->left->firstpos, + uni->right->firstpos, NULL, 0); + if (!node->firstpos) + return REG_ESPACE; + node->lastpos = tre_set_union(mem, uni->left->lastpos, + uni->right->lastpos, NULL, 0); + if (!node->lastpos) + return REG_ESPACE; + break; + } + + case NFL_POST_ITERATION: + { + tre_iteration_t *iter = (tre_iteration_t *)node->obj; + + if (iter->min == 0 || iter->arg->nullable) + node->nullable = 1; + else + node->nullable = 0; + node->firstpos = iter->arg->firstpos; + node->lastpos = iter->arg->lastpos; + break; + } + + case NFL_POST_CATENATION: + { + int num_tags, *tags, assertions; + reg_errcode_t status; + tre_catenation_t *cat = node->obj; + node->nullable = cat->left->nullable && cat->right->nullable; + + /* Compute firstpos. */ + if (cat->left->nullable) + { + /* The left side matches the empty string. Make a first pass + with tre_match_empty() to get the number of tags and + parameters. */ + status = tre_match_empty(stack, cat->left, + NULL, NULL, &num_tags); + if (status != REG_OK) + return status; + /* Allocate arrays for the tags and parameters. */ + tags = xmalloc(sizeof(*tags) * (num_tags + 1)); + if (!tags) + return REG_ESPACE; + tags[0] = -1; + assertions = 0; + /* Second pass with tre_mach_empty() to get the list of + tags and parameters. */ + status = tre_match_empty(stack, cat->left, tags, + &assertions, NULL); + if (status != REG_OK) + { + xfree(tags); + return status; + } + node->firstpos = + tre_set_union(mem, cat->right->firstpos, cat->left->firstpos, + tags, assertions); + xfree(tags); + if (!node->firstpos) + return REG_ESPACE; + } + else + { + node->firstpos = cat->left->firstpos; + } + + /* Compute lastpos. */ + if (cat->right->nullable) + { + /* The right side matches the empty string. Make a first pass + with tre_match_empty() to get the number of tags and + parameters. */ + status = tre_match_empty(stack, cat->right, + NULL, NULL, &num_tags); + if (status != REG_OK) + return status; + /* Allocate arrays for the tags and parameters. */ + tags = xmalloc(sizeof(int) * (num_tags + 1)); + if (!tags) + return REG_ESPACE; + tags[0] = -1; + assertions = 0; + /* Second pass with tre_mach_empty() to get the list of + tags and parameters. */ + status = tre_match_empty(stack, cat->right, tags, + &assertions, NULL); + if (status != REG_OK) + { + xfree(tags); + return status; + } + node->lastpos = + tre_set_union(mem, cat->left->lastpos, cat->right->lastpos, + tags, assertions); + xfree(tags); + if (!node->lastpos) + return REG_ESPACE; + } + else + { + node->lastpos = cat->right->lastpos; + } + break; + } + + default: + assert(0); + break; + } + } + + return REG_OK; +} + + +/* Adds a transition from each position in `p1' to each position in `p2'. */ +static reg_errcode_t +tre_make_trans(tre_pos_and_tags_t *p1, tre_pos_and_tags_t *p2, + tre_tnfa_transition_t *transitions, + int *counts, int *offs) +{ + tre_pos_and_tags_t *orig_p2 = p2; + tre_tnfa_transition_t *trans; + int i, j, k, l, dup, prev_p2_pos; + + if (transitions != NULL) + while (p1->position >= 0) + { + p2 = orig_p2; + prev_p2_pos = -1; + while (p2->position >= 0) + { + /* Optimization: if this position was already handled, skip it. */ + if (p2->position == prev_p2_pos) + { + p2++; + continue; + } + prev_p2_pos = p2->position; + /* Set `trans' to point to the next unused transition from + position `p1->position'. */ + trans = transitions + offs[p1->position]; + while (trans->state != NULL) + { +#if 0 + /* If we find a previous transition from `p1->position' to + `p2->position', it is overwritten. This can happen only + if there are nested loops in the regexp, like in "((a)*)*". + In POSIX.2 repetition using the outer loop is always + preferred over using the inner loop. Therefore the + transition for the inner loop is useless and can be thrown + away. */ + /* XXX - The same position is used for all nodes in a bracket + expression, so this optimization cannot be used (it will + break bracket expressions) unless I figure out a way to + detect it here. */ + if (trans->state_id == p2->position) + { + break; + } +#endif + trans++; + } + + if (trans->state == NULL) + (trans + 1)->state = NULL; + /* Use the character ranges, assertions, etc. from `p1' for + the transition from `p1' to `p2'. */ + trans->code_min = p1->code_min; + trans->code_max = p1->code_max; + trans->state = transitions + offs[p2->position]; + trans->state_id = p2->position; + trans->assertions = p1->assertions | p2->assertions + | (p1->class ? ASSERT_CHAR_CLASS : 0) + | (p1->neg_classes != NULL ? ASSERT_CHAR_CLASS_NEG : 0); + if (p1->backref >= 0) + { + assert((trans->assertions & ASSERT_CHAR_CLASS) == 0); + assert(p2->backref < 0); + trans->u.backref = p1->backref; + trans->assertions |= ASSERT_BACKREF; + } + else + trans->u.class = p1->class; + if (p1->neg_classes != NULL) + { + for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++); + trans->neg_classes = + xmalloc(sizeof(*trans->neg_classes) * (i + 1)); + if (trans->neg_classes == NULL) + return REG_ESPACE; + for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++) + trans->neg_classes[i] = p1->neg_classes[i]; + trans->neg_classes[i] = (tre_ctype_t)0; + } + else + trans->neg_classes = NULL; + + /* Find out how many tags this transition has. */ + i = 0; + if (p1->tags != NULL) + while(p1->tags[i] >= 0) + i++; + j = 0; + if (p2->tags != NULL) + while(p2->tags[j] >= 0) + j++; + + /* If we are overwriting a transition, free the old tag array. */ + if (trans->tags != NULL) + xfree(trans->tags); + trans->tags = NULL; + + /* If there were any tags, allocate an array and fill it. */ + if (i + j > 0) + { + trans->tags = xmalloc(sizeof(*trans->tags) * (i + j + 1)); + if (!trans->tags) + return REG_ESPACE; + i = 0; + if (p1->tags != NULL) + while(p1->tags[i] >= 0) + { + trans->tags[i] = p1->tags[i]; + i++; + } + l = i; + j = 0; + if (p2->tags != NULL) + while (p2->tags[j] >= 0) + { + /* Don't add duplicates. */ + dup = 0; + for (k = 0; k < i; k++) + if (trans->tags[k] == p2->tags[j]) + { + dup = 1; + break; + } + if (!dup) + trans->tags[l++] = p2->tags[j]; + j++; + } + trans->tags[l] = -1; + } + + p2++; + } + p1++; + } + else + /* Compute a maximum limit for the number of transitions leaving + from each state. */ + while (p1->position >= 0) + { + p2 = orig_p2; + while (p2->position >= 0) + { + counts[p1->position]++; + p2++; + } + p1++; + } + return REG_OK; +} + +/* Converts the syntax tree to a TNFA. All the transitions in the TNFA are + labelled with one character range (there are no transitions on empty + strings). The TNFA takes O(n^2) space in the worst case, `n' is size of + the regexp. */ +static reg_errcode_t +tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions, + int *counts, int *offs) +{ + tre_union_t *uni; + tre_catenation_t *cat; + tre_iteration_t *iter; + reg_errcode_t errcode = REG_OK; + + /* XXX - recurse using a stack!. */ + switch (node->type) + { + case LITERAL: + break; + case UNION: + uni = (tre_union_t *)node->obj; + errcode = tre_ast_to_tnfa(uni->left, transitions, counts, offs); + if (errcode != REG_OK) + return errcode; + errcode = tre_ast_to_tnfa(uni->right, transitions, counts, offs); + break; + + case CATENATION: + cat = (tre_catenation_t *)node->obj; + /* Add a transition from each position in cat->left->lastpos + to each position in cat->right->firstpos. */ + errcode = tre_make_trans(cat->left->lastpos, cat->right->firstpos, + transitions, counts, offs); + if (errcode != REG_OK) + return errcode; + errcode = tre_ast_to_tnfa(cat->left, transitions, counts, offs); + if (errcode != REG_OK) + return errcode; + errcode = tre_ast_to_tnfa(cat->right, transitions, counts, offs); + break; + + case ITERATION: + iter = (tre_iteration_t *)node->obj; + assert(iter->max == -1 || iter->max == 1); + + if (iter->max == -1) + { + assert(iter->min == 0 || iter->min == 1); + /* Add a transition from each last position in the iterated + expression to each first position. */ + errcode = tre_make_trans(iter->arg->lastpos, iter->arg->firstpos, + transitions, counts, offs); + if (errcode != REG_OK) + return errcode; + } + errcode = tre_ast_to_tnfa(iter->arg, transitions, counts, offs); + break; + } + return errcode; +} + + +#define ERROR_EXIT(err) \ + do \ + { \ + errcode = err; \ + if (/*CONSTCOND*/1) \ + goto error_exit; \ + } \ + while (/*CONSTCOND*/0) + + +int +regcomp(regex_t *restrict preg, const char *restrict regex, int cflags) +{ + tre_stack_t *stack; + tre_ast_node_t *tree, *tmp_ast_l, *tmp_ast_r; + tre_pos_and_tags_t *p; + int *counts = NULL, *offs = NULL; + int i, add = 0; + tre_tnfa_transition_t *transitions, *initial; + tre_tnfa_t *tnfa = NULL; + tre_submatch_data_t *submatch_data; + tre_tag_direction_t *tag_directions = NULL; + reg_errcode_t errcode; + tre_mem_t mem; + + /* Parse context. */ + tre_parse_ctx_t parse_ctx; + + /* Allocate a stack used throughout the compilation process for various + purposes. */ + stack = tre_stack_new(512, 10240, 128); + if (!stack) + return REG_ESPACE; + /* Allocate a fast memory allocator. */ + mem = tre_mem_new(); + if (!mem) + { + tre_stack_destroy(stack); + return REG_ESPACE; + } + + /* Parse the regexp. */ + memset(&parse_ctx, 0, sizeof(parse_ctx)); + parse_ctx.mem = mem; + parse_ctx.stack = stack; + parse_ctx.re = regex; + parse_ctx.cflags = cflags; + parse_ctx.max_backref = -1; + errcode = tre_parse(&parse_ctx); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + preg->re_nsub = parse_ctx.submatch_id - 1; + tree = parse_ctx.result; + + /* Back references and approximate matching cannot currently be used + in the same regexp. */ + if (parse_ctx.max_backref >= 0 && parse_ctx.have_approx) + ERROR_EXIT(REG_BADPAT); + +#ifdef TRE_DEBUG + tre_ast_print(tree); +#endif /* TRE_DEBUG */ + + /* Referring to nonexistent subexpressions is illegal. */ + if (parse_ctx.max_backref > (int)preg->re_nsub) + ERROR_EXIT(REG_ESUBREG); + + /* Allocate the TNFA struct. */ + tnfa = xcalloc(1, sizeof(tre_tnfa_t)); + if (tnfa == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->have_backrefs = parse_ctx.max_backref >= 0; + tnfa->have_approx = parse_ctx.have_approx; + tnfa->num_submatches = parse_ctx.submatch_id; + + /* Set up tags for submatch addressing. If REG_NOSUB is set and the + regexp does not have back references, this can be skipped. */ + if (tnfa->have_backrefs || !(cflags & REG_NOSUB)) + { + + /* Figure out how many tags we will need. */ + errcode = tre_add_tags(NULL, stack, tree, tnfa); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + + if (tnfa->num_tags > 0) + { + tag_directions = xmalloc(sizeof(*tag_directions) + * (tnfa->num_tags + 1)); + if (tag_directions == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->tag_directions = tag_directions; + memset(tag_directions, -1, + sizeof(*tag_directions) * (tnfa->num_tags + 1)); + } + tnfa->minimal_tags = xcalloc((unsigned)tnfa->num_tags * 2 + 1, + sizeof(tnfa->minimal_tags)); + if (tnfa->minimal_tags == NULL) + ERROR_EXIT(REG_ESPACE); + + submatch_data = xcalloc((unsigned)parse_ctx.submatch_id, + sizeof(*submatch_data)); + if (submatch_data == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->submatch_data = submatch_data; + + errcode = tre_add_tags(mem, stack, tree, tnfa); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + + } + + /* Expand iteration nodes. */ + errcode = tre_expand_ast(mem, stack, tree, &parse_ctx.position, + tag_directions); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + + /* Add a dummy node for the final state. + XXX - For certain patterns this dummy node can be optimized away, + for example "a*" or "ab*". Figure out a simple way to detect + this possibility. */ + tmp_ast_l = tree; + tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position++); + if (tmp_ast_r == NULL) + ERROR_EXIT(REG_ESPACE); + + tree = tre_ast_new_catenation(mem, tmp_ast_l, tmp_ast_r); + if (tree == NULL) + ERROR_EXIT(REG_ESPACE); + + errcode = tre_compute_nfl(mem, stack, tree); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + + counts = xmalloc(sizeof(int) * parse_ctx.position); + if (counts == NULL) + ERROR_EXIT(REG_ESPACE); + + offs = xmalloc(sizeof(int) * parse_ctx.position); + if (offs == NULL) + ERROR_EXIT(REG_ESPACE); + + for (i = 0; i < parse_ctx.position; i++) + counts[i] = 0; + tre_ast_to_tnfa(tree, NULL, counts, NULL); + + add = 0; + for (i = 0; i < parse_ctx.position; i++) + { + offs[i] = add; + add += counts[i] + 1; + counts[i] = 0; + } + transitions = xcalloc((unsigned)add + 1, sizeof(*transitions)); + if (transitions == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->transitions = transitions; + tnfa->num_transitions = add; + + errcode = tre_ast_to_tnfa(tree, transitions, counts, offs); + if (errcode != REG_OK) + ERROR_EXIT(errcode); + + tnfa->firstpos_chars = NULL; + + p = tree->firstpos; + i = 0; + while (p->position >= 0) + { + i++; + p++; + } + + initial = xcalloc((unsigned)i + 1, sizeof(tre_tnfa_transition_t)); + if (initial == NULL) + ERROR_EXIT(REG_ESPACE); + tnfa->initial = initial; + + i = 0; + for (p = tree->firstpos; p->position >= 0; p++) + { + initial[i].state = transitions + offs[p->position]; + initial[i].state_id = p->position; + initial[i].tags = NULL; + /* Copy the arrays p->tags, and p->params, they are allocated + from a tre_mem object. */ + if (p->tags) + { + int j; + for (j = 0; p->tags[j] >= 0; j++); + initial[i].tags = xmalloc(sizeof(*p->tags) * (j + 1)); + if (!initial[i].tags) + ERROR_EXIT(REG_ESPACE); + memcpy(initial[i].tags, p->tags, sizeof(*p->tags) * (j + 1)); + } + initial[i].assertions = p->assertions; + i++; + } + initial[i].state = NULL; + + tnfa->num_transitions = add; + tnfa->final = transitions + offs[tree->lastpos[0].position]; + tnfa->num_states = parse_ctx.position; + tnfa->cflags = cflags; + + tre_mem_destroy(mem); + tre_stack_destroy(stack); + xfree(counts); + xfree(offs); + + preg->TRE_REGEX_T_FIELD = (void *)tnfa; + return REG_OK; + + error_exit: + /* Free everything that was allocated and return the error code. */ + tre_mem_destroy(mem); + if (stack != NULL) + tre_stack_destroy(stack); + if (counts != NULL) + xfree(counts); + if (offs != NULL) + xfree(offs); + preg->TRE_REGEX_T_FIELD = (void *)tnfa; + regfree(preg); + return errcode; +} + + + + +void +regfree(regex_t *preg) +{ + tre_tnfa_t *tnfa; + unsigned int i; + tre_tnfa_transition_t *trans; + + tnfa = (void *)preg->TRE_REGEX_T_FIELD; + if (!tnfa) + return; + + for (i = 0; i < tnfa->num_transitions; i++) + if (tnfa->transitions[i].state) + { + if (tnfa->transitions[i].tags) + xfree(tnfa->transitions[i].tags); + if (tnfa->transitions[i].neg_classes) + xfree(tnfa->transitions[i].neg_classes); + } + if (tnfa->transitions) + xfree(tnfa->transitions); + + if (tnfa->initial) + { + for (trans = tnfa->initial; trans->state; trans++) + { + if (trans->tags) + xfree(trans->tags); + } + xfree(tnfa->initial); + } + + if (tnfa->submatch_data) + { + for (i = 0; i < tnfa->num_submatches; i++) + if (tnfa->submatch_data[i].parents) + xfree(tnfa->submatch_data[i].parents); + xfree(tnfa->submatch_data); + } + + if (tnfa->tag_directions) + xfree(tnfa->tag_directions); + if (tnfa->firstpos_chars) + xfree(tnfa->firstpos_chars); + if (tnfa->minimal_tags) + xfree(tnfa->minimal_tags); + xfree(tnfa); +} diff --git a/system/lib/libc/musl/src/regex/regerror.c b/system/lib/libc/musl/src/regex/regerror.c new file mode 100644 index 00000000..df4afa4f --- /dev/null +++ b/system/lib/libc/musl/src/regex/regerror.c @@ -0,0 +1,35 @@ +#include <string.h> +#include <regex.h> +#include <stdio.h> + +/* Error message strings for error codes listed in `regex.h'. This list + needs to be in sync with the codes listed there, naturally. */ + +/* Converted to single string by Rich Felker to remove the need for + * data relocations at runtime, 27 Feb 2006. */ + +static const char messages[] = { + "No error\0" + "No match\0" + "Invalid regexp\0" + "Unknown collating element\0" + "Unknown character class name\0" + "Trailing backslash\0" + "Invalid back reference\0" + "Missing ']'\0" + "Missing ')'\0" + "Missing '}'\0" + "Invalid contents of {}\0" + "Invalid character range\0" + "Out of memory\0" + "Repetition not preceded by valid expression\0" + "\0Unknown error" +}; + +size_t regerror(int e, const regex_t *restrict preg, char *restrict buf, size_t size) +{ + const char *s; + for (s=messages; e && *s; e--, s+=strlen(s)+1); + if (!*s) s++; + return 1+snprintf(buf, size, "%s", s); +} diff --git a/system/lib/libc/musl/src/regex/regexec.c b/system/lib/libc/musl/src/regex/regexec.c new file mode 100644 index 00000000..855cef57 --- /dev/null +++ b/system/lib/libc/musl/src/regex/regexec.c @@ -0,0 +1,1011 @@ +/* + regexec.c - TRE POSIX compatible matching functions (and more). + + Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi> + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS + ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*/ + +#include <stdlib.h> +#include <string.h> +#include <wchar.h> +#include <wctype.h> +#include <limits.h> + +#include <regex.h> + +#include "tre.h" + +#include <assert.h> + +static void +tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, + const tre_tnfa_t *tnfa, int *tags, int match_eo); + +/*********************************************************************** + from tre-match-utils.h +***********************************************************************/ + +#define GET_NEXT_WCHAR() do { \ + prev_c = next_c; pos += pos_add_next; \ + if ((pos_add_next = mbtowc(&next_c, str_byte, MB_LEN_MAX)) <= 0) { \ + if (pos_add_next < 0) return REG_NOMATCH; \ + else pos_add_next++; \ + } \ + str_byte += pos_add_next; \ + } while (0) + +#define IS_WORD_CHAR(c) ((c) == L'_' || tre_isalnum(c)) + +#define CHECK_ASSERTIONS(assertions) \ + (((assertions & ASSERT_AT_BOL) \ + && (pos > 0 || reg_notbol) \ + && (prev_c != L'\n' || !reg_newline)) \ + || ((assertions & ASSERT_AT_EOL) \ + && (next_c != L'\0' || reg_noteol) \ + && (next_c != L'\n' || !reg_newline)) \ + || ((assertions & ASSERT_AT_BOW) \ + && (IS_WORD_CHAR(prev_c) || !IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_EOW) \ + && (!IS_WORD_CHAR(prev_c) || IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_WB) \ + && (pos != 0 && next_c != L'\0' \ + && IS_WORD_CHAR(prev_c) == IS_WORD_CHAR(next_c))) \ + || ((assertions & ASSERT_AT_WB_NEG) \ + && (pos == 0 || next_c == L'\0' \ + || IS_WORD_CHAR(prev_c) != IS_WORD_CHAR(next_c)))) + +#define CHECK_CHAR_CLASSES(trans_i, tnfa, eflags) \ + (((trans_i->assertions & ASSERT_CHAR_CLASS) \ + && !(tnfa->cflags & REG_ICASE) \ + && !tre_isctype((tre_cint_t)prev_c, trans_i->u.class)) \ + || ((trans_i->assertions & ASSERT_CHAR_CLASS) \ + && (tnfa->cflags & REG_ICASE) \ + && !tre_isctype(tre_tolower((tre_cint_t)prev_c),trans_i->u.class) \ + && !tre_isctype(tre_toupper((tre_cint_t)prev_c),trans_i->u.class)) \ + || ((trans_i->assertions & ASSERT_CHAR_CLASS_NEG) \ + && tre_neg_char_classes_match(trans_i->neg_classes,(tre_cint_t)prev_c,\ + tnfa->cflags & REG_ICASE))) + + + + +/* Returns 1 if `t1' wins `t2', 0 otherwise. */ +static int +tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions, + int *t1, int *t2) +{ + int i; + for (i = 0; i < num_tags; i++) + { + if (tag_directions[i] == TRE_TAG_MINIMIZE) + { + if (t1[i] < t2[i]) + return 1; + if (t1[i] > t2[i]) + return 0; + } + else + { + if (t1[i] > t2[i]) + return 1; + if (t1[i] < t2[i]) + return 0; + } + } + /* assert(0);*/ + return 0; +} + +static int +tre_neg_char_classes_match(tre_ctype_t *classes, tre_cint_t wc, int icase) +{ + while (*classes != (tre_ctype_t)0) + if ((!icase && tre_isctype(wc, *classes)) + || (icase && (tre_isctype(tre_toupper(wc), *classes) + || tre_isctype(tre_tolower(wc), *classes)))) + return 1; /* Match. */ + else + classes++; + return 0; /* No match. */ +} + + +/*********************************************************************** + from tre-match-parallel.c +***********************************************************************/ + +/* + This algorithm searches for matches basically by reading characters + in the searched string one by one, starting at the beginning. All + matching paths in the TNFA are traversed in parallel. When two or + more paths reach the same state, exactly one is chosen according to + tag ordering rules; if returning submatches is not required it does + not matter which path is chosen. + + The worst case time required for finding the leftmost and longest + match, or determining that there is no match, is always linearly + dependent on the length of the text being searched. + + This algorithm cannot handle TNFAs with back referencing nodes. + See `tre-match-backtrack.c'. +*/ + +typedef struct { + tre_tnfa_transition_t *state; + int *tags; +} tre_tnfa_reach_t; + +typedef struct { + int pos; + int **tags; +} tre_reach_pos_t; + + +static reg_errcode_t +tre_tnfa_run_parallel(const tre_tnfa_t *tnfa, const void *string, + int *match_tags, int eflags, + int *match_end_ofs) +{ + /* State variables required by GET_NEXT_WCHAR. */ + tre_char_t prev_c = 0, next_c = 0; + const char *str_byte = string; + int pos = -1; + int pos_add_next = 1; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ + int reg_notbol = eflags & REG_NOTBOL; + int reg_noteol = eflags & REG_NOTEOL; + int reg_newline = tnfa->cflags & REG_NEWLINE; + + char *buf; + tre_tnfa_transition_t *trans_i; + tre_tnfa_reach_t *reach, *reach_next, *reach_i, *reach_next_i; + tre_reach_pos_t *reach_pos; + int *tag_i; + int num_tags, i; + + int match_eo = -1; /* end offset of match (-1 if no match found yet) */ + int new_match = 0; + int *tmp_tags = NULL; + int *tmp_iptr; + +#ifdef TRE_MBSTATE + memset(&mbstate, '\0', sizeof(mbstate)); +#endif /* TRE_MBSTATE */ + + if (!match_tags) + num_tags = 0; + else + num_tags = tnfa->num_tags; + + /* Allocate memory for temporary data required for matching. This needs to + be done for every matching operation to be thread safe. This allocates + everything in a single large block from the stack frame using alloca() + or with malloc() if alloca is unavailable. */ + { + int tbytes, rbytes, pbytes, xbytes, total_bytes; + char *tmp_buf; + /* Compute the length of the block we need. */ + tbytes = sizeof(*tmp_tags) * num_tags; + rbytes = sizeof(*reach_next) * (tnfa->num_states + 1); + pbytes = sizeof(*reach_pos) * tnfa->num_states; + xbytes = sizeof(int) * num_tags; + total_bytes = + (sizeof(long) - 1) * 4 /* for alignment paddings */ + + (rbytes + xbytes * tnfa->num_states) * 2 + tbytes + pbytes; + + /* Allocate the memory. */ + buf = xmalloc((unsigned)total_bytes); + if (buf == NULL) + return REG_ESPACE; + memset(buf, 0, (size_t)total_bytes); + + /* Get the various pointers within tmp_buf (properly aligned). */ + tmp_tags = (void *)buf; + tmp_buf = buf + tbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach_next = (void *)tmp_buf; + tmp_buf += rbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach = (void *)tmp_buf; + tmp_buf += rbytes; + tmp_buf += ALIGN(tmp_buf, long); + reach_pos = (void *)tmp_buf; + tmp_buf += pbytes; + tmp_buf += ALIGN(tmp_buf, long); + for (i = 0; i < tnfa->num_states; i++) + { + reach[i].tags = (void *)tmp_buf; + tmp_buf += xbytes; + reach_next[i].tags = (void *)tmp_buf; + tmp_buf += xbytes; + } + } + + for (i = 0; i < tnfa->num_states; i++) + reach_pos[i].pos = -1; + + GET_NEXT_WCHAR(); + pos = 0; + + reach_next_i = reach_next; + while (1) + { + /* If no match found yet, add the initial states to `reach_next'. */ + if (match_eo < 0) + { + trans_i = tnfa->initial; + while (trans_i->state != NULL) + { + if (reach_pos[trans_i->state_id].pos < pos) + { + if (trans_i->assertions + && CHECK_ASSERTIONS(trans_i->assertions)) + { + trans_i++; + continue; + } + + reach_next_i->state = trans_i->state; + for (i = 0; i < num_tags; i++) + reach_next_i->tags[i] = -1; + tag_i = trans_i->tags; + if (tag_i) + while (*tag_i >= 0) + { + if (*tag_i < num_tags) + reach_next_i->tags[*tag_i] = pos; + tag_i++; + } + if (reach_next_i->state == tnfa->final) + { + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = reach_next_i->tags[i]; + } + reach_pos[trans_i->state_id].pos = pos; + reach_pos[trans_i->state_id].tags = &reach_next_i->tags; + reach_next_i++; + } + trans_i++; + } + reach_next_i->state = NULL; + } + else + { + if (num_tags == 0 || reach_next_i == reach_next) + /* We have found a match. */ + break; + } + + /* Check for end of string. */ + if (!next_c) break; + + GET_NEXT_WCHAR(); + + /* Swap `reach' and `reach_next'. */ + reach_i = reach; + reach = reach_next; + reach_next = reach_i; + + /* For each state in `reach', weed out states that don't fulfill the + minimal matching conditions. */ + if (tnfa->num_minimals && new_match) + { + new_match = 0; + reach_next_i = reach_next; + for (reach_i = reach; reach_i->state; reach_i++) + { + int skip = 0; + for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2) + { + int end = tnfa->minimal_tags[i]; + int start = tnfa->minimal_tags[i + 1]; + if (end >= num_tags) + { + skip = 1; + break; + } + else if (reach_i->tags[start] == match_tags[start] + && reach_i->tags[end] < match_tags[end]) + { + skip = 1; + break; + } + } + if (!skip) + { + reach_next_i->state = reach_i->state; + tmp_iptr = reach_next_i->tags; + reach_next_i->tags = reach_i->tags; + reach_i->tags = tmp_iptr; + reach_next_i++; + } + } + reach_next_i->state = NULL; + + /* Swap `reach' and `reach_next'. */ + reach_i = reach; + reach = reach_next; + reach_next = reach_i; + } + + /* For each state in `reach' see if there is a transition leaving with + the current input symbol to a state not yet in `reach_next', and + add the destination states to `reach_next'. */ + reach_next_i = reach_next; + for (reach_i = reach; reach_i->state; reach_i++) + { + for (trans_i = reach_i->state; trans_i->state; trans_i++) + { + /* Does this transition match the input symbol? */ + if (trans_i->code_min <= (tre_cint_t)prev_c && + trans_i->code_max >= (tre_cint_t)prev_c) + { + if (trans_i->assertions + && (CHECK_ASSERTIONS(trans_i->assertions) + || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) + { + continue; + } + + /* Compute the tags after this transition. */ + for (i = 0; i < num_tags; i++) + tmp_tags[i] = reach_i->tags[i]; + tag_i = trans_i->tags; + if (tag_i != NULL) + while (*tag_i >= 0) + { + if (*tag_i < num_tags) + tmp_tags[*tag_i] = pos; + tag_i++; + } + + if (reach_pos[trans_i->state_id].pos < pos) + { + /* Found an unvisited node. */ + reach_next_i->state = trans_i->state; + tmp_iptr = reach_next_i->tags; + reach_next_i->tags = tmp_tags; + tmp_tags = tmp_iptr; + reach_pos[trans_i->state_id].pos = pos; + reach_pos[trans_i->state_id].tags = &reach_next_i->tags; + + if (reach_next_i->state == tnfa->final + && (match_eo == -1 + || (num_tags > 0 + && reach_next_i->tags[0] <= match_tags[0]))) + { + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = reach_next_i->tags[i]; + } + reach_next_i++; + + } + else + { + assert(reach_pos[trans_i->state_id].pos == pos); + /* Another path has also reached this state. We choose + the winner by examining the tag values for both + paths. */ + if (tre_tag_order(num_tags, tnfa->tag_directions, + tmp_tags, + *reach_pos[trans_i->state_id].tags)) + { + /* The new path wins. */ + tmp_iptr = *reach_pos[trans_i->state_id].tags; + *reach_pos[trans_i->state_id].tags = tmp_tags; + if (trans_i->state == tnfa->final) + { + match_eo = pos; + new_match = 1; + for (i = 0; i < num_tags; i++) + match_tags[i] = tmp_tags[i]; + } + tmp_tags = tmp_iptr; + } + } + } + } + } + reach_next_i->state = NULL; + } + + if (buf) + xfree(buf); + + *match_end_ofs = match_eo; + return match_eo >= 0 ? REG_OK : REG_NOMATCH; +} + + + +/*********************************************************************** + from tre-match-backtrack.c +***********************************************************************/ + +/* + This matcher is for regexps that use back referencing. Regexp matching + with back referencing is an NP-complete problem on the number of back + references. The easiest way to match them is to use a backtracking + routine which basically goes through all possible paths in the TNFA + and chooses the one which results in the best (leftmost and longest) + match. This can be spectacularly expensive and may run out of stack + space, but there really is no better known generic algorithm. Quoting + Henry Spencer from comp.compilers: + <URL: http://compilers.iecc.com/comparch/article/93-03-102> + + POSIX.2 REs require longest match, which is really exciting to + implement since the obsolete ("basic") variant also includes + \<digit>. I haven't found a better way of tackling this than doing + a preliminary match using a DFA (or simulation) on a modified RE + that just replicates subREs for \<digit>, and then doing a + backtracking match to determine whether the subRE matches were + right. This can be rather slow, but I console myself with the + thought that people who use \<digit> deserve very slow execution. + (Pun unintentional but very appropriate.) + +*/ + +typedef struct { + int pos; + const char *str_byte; + tre_tnfa_transition_t *state; + int state_id; + int next_c; + int *tags; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ +} tre_backtrack_item_t; + +typedef struct tre_backtrack_struct { + tre_backtrack_item_t item; + struct tre_backtrack_struct *prev; + struct tre_backtrack_struct *next; +} *tre_backtrack_t; + +#ifdef TRE_MBSTATE +#define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate) +#define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate +#else /* !TRE_MBSTATE */ +#define BT_STACK_MBSTATE_IN +#define BT_STACK_MBSTATE_OUT +#endif /* !TRE_MBSTATE */ + +#define tre_bt_mem_new tre_mem_new +#define tre_bt_mem_alloc tre_mem_alloc +#define tre_bt_mem_destroy tre_mem_destroy + + +#define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \ + do \ + { \ + int i; \ + if (!stack->next) \ + { \ + tre_backtrack_t s; \ + s = tre_bt_mem_alloc(mem, sizeof(*s)); \ + if (!s) \ + { \ + tre_bt_mem_destroy(mem); \ + if (tags) \ + xfree(tags); \ + if (pmatch) \ + xfree(pmatch); \ + if (states_seen) \ + xfree(states_seen); \ + return REG_ESPACE; \ + } \ + s->prev = stack; \ + s->next = NULL; \ + s->item.tags = tre_bt_mem_alloc(mem, \ + sizeof(*tags) * tnfa->num_tags); \ + if (!s->item.tags) \ + { \ + tre_bt_mem_destroy(mem); \ + if (tags) \ + xfree(tags); \ + if (pmatch) \ + xfree(pmatch); \ + if (states_seen) \ + xfree(states_seen); \ + return REG_ESPACE; \ + } \ + stack->next = s; \ + stack = s; \ + } \ + else \ + stack = stack->next; \ + stack->item.pos = (_pos); \ + stack->item.str_byte = (_str_byte); \ + stack->item.state = (_state); \ + stack->item.state_id = (_state_id); \ + stack->item.next_c = (_next_c); \ + for (i = 0; i < tnfa->num_tags; i++) \ + stack->item.tags[i] = (_tags)[i]; \ + BT_STACK_MBSTATE_IN; \ + } \ + while (0) + +#define BT_STACK_POP() \ + do \ + { \ + int i; \ + assert(stack->prev); \ + pos = stack->item.pos; \ + str_byte = stack->item.str_byte; \ + state = stack->item.state; \ + next_c = stack->item.next_c; \ + for (i = 0; i < tnfa->num_tags; i++) \ + tags[i] = stack->item.tags[i]; \ + BT_STACK_MBSTATE_OUT; \ + stack = stack->prev; \ + } \ + while (0) + +#undef MIN +#define MIN(a, b) ((a) <= (b) ? (a) : (b)) + +static reg_errcode_t +tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, + int *match_tags, int eflags, int *match_end_ofs) +{ + /* State variables required by GET_NEXT_WCHAR. */ + tre_char_t prev_c = 0, next_c = 0; + const char *str_byte = string; + int pos = 0; + int pos_add_next = 1; +#ifdef TRE_MBSTATE + mbstate_t mbstate; +#endif /* TRE_MBSTATE */ + int reg_notbol = eflags & REG_NOTBOL; + int reg_noteol = eflags & REG_NOTEOL; + int reg_newline = tnfa->cflags & REG_NEWLINE; + + /* These are used to remember the necessary values of the above + variables to return to the position where the current search + started from. */ + int next_c_start; + const char *str_byte_start; + int pos_start = -1; +#ifdef TRE_MBSTATE + mbstate_t mbstate_start; +#endif /* TRE_MBSTATE */ + + /* End offset of best match so far, or -1 if no match found yet. */ + int match_eo = -1; + /* Tag arrays. */ + int *next_tags, *tags = NULL; + /* Current TNFA state. */ + tre_tnfa_transition_t *state; + int *states_seen = NULL; + + /* Memory allocator to for allocating the backtracking stack. */ + tre_mem_t mem = tre_bt_mem_new(); + + /* The backtracking stack. */ + tre_backtrack_t stack; + + tre_tnfa_transition_t *trans_i; + regmatch_t *pmatch = NULL; + int ret; + +#ifdef TRE_MBSTATE + memset(&mbstate, '\0', sizeof(mbstate)); +#endif /* TRE_MBSTATE */ + + if (!mem) + return REG_ESPACE; + stack = tre_bt_mem_alloc(mem, sizeof(*stack)); + if (!stack) + { + ret = REG_ESPACE; + goto error_exit; + } + stack->prev = NULL; + stack->next = NULL; + + if (tnfa->num_tags) + { + tags = xmalloc(sizeof(*tags) * tnfa->num_tags); + if (!tags) + { + ret = REG_ESPACE; + goto error_exit; + } + } + if (tnfa->num_submatches) + { + pmatch = xmalloc(sizeof(*pmatch) * tnfa->num_submatches); + if (!pmatch) + { + ret = REG_ESPACE; + goto error_exit; + } + } + if (tnfa->num_states) + { + states_seen = xmalloc(sizeof(*states_seen) * tnfa->num_states); + if (!states_seen) + { + ret = REG_ESPACE; + goto error_exit; + } + } + + retry: + { + int i; + for (i = 0; i < tnfa->num_tags; i++) + { + tags[i] = -1; + if (match_tags) + match_tags[i] = -1; + } + for (i = 0; i < tnfa->num_states; i++) + states_seen[i] = 0; + } + + state = NULL; + pos = pos_start; + GET_NEXT_WCHAR(); + pos_start = pos; + next_c_start = next_c; + str_byte_start = str_byte; +#ifdef TRE_MBSTATE + mbstate_start = mbstate; +#endif /* TRE_MBSTATE */ + + /* Handle initial states. */ + next_tags = NULL; + for (trans_i = tnfa->initial; trans_i->state; trans_i++) + { + if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions)) + { + continue; + } + if (state == NULL) + { + /* Start from this state. */ + state = trans_i->state; + next_tags = trans_i->tags; + } + else + { + /* Backtrack to this state. */ + BT_STACK_PUSH(pos, str_byte, 0, trans_i->state, + trans_i->state_id, next_c, tags, mbstate); + { + int *tmp = trans_i->tags; + if (tmp) + while (*tmp >= 0) + stack->item.tags[*tmp++] = pos; + } + } + } + + if (next_tags) + for (; *next_tags >= 0; next_tags++) + tags[*next_tags] = pos; + + + if (state == NULL) + goto backtrack; + + while (1) + { + tre_tnfa_transition_t *next_state; + int empty_br_match; + + if (state == tnfa->final) + { + if (match_eo < pos + || (match_eo == pos + && match_tags + && tre_tag_order(tnfa->num_tags, tnfa->tag_directions, + tags, match_tags))) + { + int i; + /* This match wins the previous match. */ + match_eo = pos; + if (match_tags) + for (i = 0; i < tnfa->num_tags; i++) + match_tags[i] = tags[i]; + } + /* Our TNFAs never have transitions leaving from the final state, + so we jump right to backtracking. */ + goto backtrack; + } + + /* Go to the next character in the input string. */ + empty_br_match = 0; + trans_i = state; + if (trans_i->state && trans_i->assertions & ASSERT_BACKREF) + { + /* This is a back reference state. All transitions leaving from + this state have the same back reference "assertion". Instead + of reading the next character, we match the back reference. */ + int so, eo, bt = trans_i->u.backref; + int bt_len; + int result; + + /* Get the substring we need to match against. Remember to + turn off REG_NOSUB temporarily. */ + tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB, + tnfa, tags, pos); + so = pmatch[bt].rm_so; + eo = pmatch[bt].rm_eo; + bt_len = eo - so; + + result = strncmp((const char*)string + so, str_byte - 1, + (size_t)bt_len); + + if (result == 0) + { + /* Back reference matched. Check for infinite loop. */ + if (bt_len == 0) + empty_br_match = 1; + if (empty_br_match && states_seen[trans_i->state_id]) + { + goto backtrack; + } + + states_seen[trans_i->state_id] = empty_br_match; + + /* Advance in input string and resync `prev_c', `next_c' + and pos. */ + str_byte += bt_len - 1; + pos += bt_len - 1; + GET_NEXT_WCHAR(); + } + else + { + goto backtrack; + } + } + else + { + /* Check for end of string. */ + if (next_c == L'\0') + goto backtrack; + + /* Read the next character. */ + GET_NEXT_WCHAR(); + } + + next_state = NULL; + for (trans_i = state; trans_i->state; trans_i++) + { + if (trans_i->code_min <= (tre_cint_t)prev_c + && trans_i->code_max >= (tre_cint_t)prev_c) + { + if (trans_i->assertions + && (CHECK_ASSERTIONS(trans_i->assertions) + || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) + { + continue; + } + + if (next_state == NULL) + { + /* First matching transition. */ + next_state = trans_i->state; + next_tags = trans_i->tags; + } + else + { + /* Second matching transition. We may need to backtrack here + to take this transition instead of the first one, so we + push this transition in the backtracking stack so we can + jump back here if needed. */ + BT_STACK_PUSH(pos, str_byte, 0, trans_i->state, + trans_i->state_id, next_c, tags, mbstate); + { + int *tmp; + for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++) + stack->item.tags[*tmp] = pos; + } +#if 0 /* XXX - it's important not to look at all transitions here to keep + the stack small! */ + break; +#endif + } + } + } + + if (next_state != NULL) + { + /* Matching transitions were found. Take the first one. */ + state = next_state; + + /* Update the tag values. */ + if (next_tags) + while (*next_tags >= 0) + tags[*next_tags++] = pos; + } + else + { + backtrack: + /* A matching transition was not found. Try to backtrack. */ + if (stack->prev) + { + if (stack->item.state->assertions & ASSERT_BACKREF) + { + states_seen[stack->item.state_id] = 0; + } + + BT_STACK_POP(); + } + else if (match_eo < 0) + { + /* Try starting from a later position in the input string. */ + /* Check for end of string. */ + if (next_c == L'\0') + { + break; + } + next_c = next_c_start; +#ifdef TRE_MBSTATE + mbstate = mbstate_start; +#endif /* TRE_MBSTATE */ + str_byte = str_byte_start; + goto retry; + } + else + { + break; + } + } + } + + ret = match_eo >= 0 ? REG_OK : REG_NOMATCH; + *match_end_ofs = match_eo; + + error_exit: + tre_bt_mem_destroy(mem); +#ifndef TRE_USE_ALLOCA + if (tags) + xfree(tags); + if (pmatch) + xfree(pmatch); + if (states_seen) + xfree(states_seen); +#endif /* !TRE_USE_ALLOCA */ + + return ret; +} + +/*********************************************************************** + from regexec.c +***********************************************************************/ + +/* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match + endpoint values. */ +static void +tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags, + const tre_tnfa_t *tnfa, int *tags, int match_eo) +{ + tre_submatch_data_t *submatch_data; + unsigned int i, j; + int *parents; + + i = 0; + if (match_eo >= 0 && !(cflags & REG_NOSUB)) + { + /* Construct submatch offsets from the tags. */ + submatch_data = tnfa->submatch_data; + while (i < tnfa->num_submatches && i < nmatch) + { + if (submatch_data[i].so_tag == tnfa->end_tag) + pmatch[i].rm_so = match_eo; + else + pmatch[i].rm_so = tags[submatch_data[i].so_tag]; + + if (submatch_data[i].eo_tag == tnfa->end_tag) + pmatch[i].rm_eo = match_eo; + else + pmatch[i].rm_eo = tags[submatch_data[i].eo_tag]; + + /* If either of the endpoints were not used, this submatch + was not part of the match. */ + if (pmatch[i].rm_so == -1 || pmatch[i].rm_eo == -1) + pmatch[i].rm_so = pmatch[i].rm_eo = -1; + + i++; + } + /* Reset all submatches that are not within all of their parent + submatches. */ + i = 0; + while (i < tnfa->num_submatches && i < nmatch) + { + if (pmatch[i].rm_eo == -1) + assert(pmatch[i].rm_so == -1); + assert(pmatch[i].rm_so <= pmatch[i].rm_eo); + + parents = submatch_data[i].parents; + if (parents != NULL) + for (j = 0; parents[j] >= 0; j++) + { + if (pmatch[i].rm_so < pmatch[parents[j]].rm_so + || pmatch[i].rm_eo > pmatch[parents[j]].rm_eo) + pmatch[i].rm_so = pmatch[i].rm_eo = -1; + } + i++; + } + } + + while (i < nmatch) + { + pmatch[i].rm_so = -1; + pmatch[i].rm_eo = -1; + i++; + } +} + + +/* + Wrapper functions for POSIX compatible regexp matching. +*/ + +int +regexec(const regex_t *restrict preg, const char *restrict string, + size_t nmatch, regmatch_t pmatch[restrict], int eflags) +{ + tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD; + reg_errcode_t status; + int *tags = NULL, eo; + if (tnfa->num_tags > 0 && nmatch > 0) + { + tags = xmalloc(sizeof(*tags) * tnfa->num_tags); + if (tags == NULL) + return REG_ESPACE; + } + + /* Dispatch to the appropriate matcher. */ + if (tnfa->have_backrefs) + { + /* The regex has back references, use the backtracking matcher. */ + status = tre_tnfa_run_backtrack(tnfa, string, tags, eflags, &eo); + } + else + { + /* Exact matching, no back references, use the parallel matcher. */ + status = tre_tnfa_run_parallel(tnfa, string, tags, eflags, &eo); + } + + if (status == REG_OK) + /* A match was found, so fill the submatch registers. */ + tre_fill_pmatch(nmatch, pmatch, tnfa->cflags, tnfa, tags, eo); + if (tags) + xfree(tags); + return status; +} diff --git a/system/lib/libc/musl/src/regex/tre-mem.c b/system/lib/libc/musl/src/regex/tre-mem.c new file mode 100644 index 00000000..86f809d4 --- /dev/null +++ b/system/lib/libc/musl/src/regex/tre-mem.c @@ -0,0 +1,158 @@ +/* + tre-mem.c - TRE memory allocator + + Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi> + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS + ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*/ + +/* + This memory allocator is for allocating small memory blocks efficiently + in terms of memory overhead and execution speed. The allocated blocks + cannot be freed individually, only all at once. There can be multiple + allocators, though. +*/ + +#include <stdlib.h> +#include <string.h> + +#include "tre.h" + +/* + This memory allocator is for allocating small memory blocks efficiently + in terms of memory overhead and execution speed. The allocated blocks + cannot be freed individually, only all at once. There can be multiple + allocators, though. +*/ + +/* Returns a new memory allocator or NULL if out of memory. */ +tre_mem_t +tre_mem_new_impl(int provided, void *provided_block) +{ + tre_mem_t mem; + if (provided) + { + mem = provided_block; + memset(mem, 0, sizeof(*mem)); + } + else + mem = xcalloc(1, sizeof(*mem)); + if (mem == NULL) + return NULL; + return mem; +} + + +/* Frees the memory allocator and all memory allocated with it. */ +void +tre_mem_destroy(tre_mem_t mem) +{ + tre_list_t *tmp, *l = mem->blocks; + + while (l != NULL) + { + xfree(l->data); + tmp = l->next; + xfree(l); + l = tmp; + } + xfree(mem); +} + + +/* Allocates a block of `size' bytes from `mem'. Returns a pointer to the + allocated block or NULL if an underlying malloc() failed. */ +void * +tre_mem_alloc_impl(tre_mem_t mem, int provided, void *provided_block, + int zero, size_t size) +{ + void *ptr; + + if (mem->failed) + { + return NULL; + } + + if (mem->n < size) + { + /* We need more memory than is available in the current block. + Allocate a new block. */ + tre_list_t *l; + if (provided) + { + if (provided_block == NULL) + { + mem->failed = 1; + return NULL; + } + mem->ptr = provided_block; + mem->n = TRE_MEM_BLOCK_SIZE; + } + else + { + int block_size; + if (size * 8 > TRE_MEM_BLOCK_SIZE) + block_size = size * 8; + else + block_size = TRE_MEM_BLOCK_SIZE; + l = xmalloc(sizeof(*l)); + if (l == NULL) + { + mem->failed = 1; + return NULL; + } + l->data = xmalloc(block_size); + if (l->data == NULL) + { + xfree(l); + mem->failed = 1; + return NULL; + } + l->next = NULL; + if (mem->current != NULL) + mem->current->next = l; + if (mem->blocks == NULL) + mem->blocks = l; + mem->current = l; + mem->ptr = l->data; + mem->n = block_size; + } + } + + /* Make sure the next pointer will be aligned. */ + size += ALIGN(mem->ptr + size, long); + + /* Allocate from current block. */ + ptr = mem->ptr; + mem->ptr += size; + mem->n -= size; + + /* Set to zero if needed. */ + if (zero) + memset(ptr, 0, size); + + return ptr; +} diff --git a/system/lib/libc/musl/src/regex/tre.h b/system/lib/libc/musl/src/regex/tre.h new file mode 100644 index 00000000..67cb9a84 --- /dev/null +++ b/system/lib/libc/musl/src/regex/tre.h @@ -0,0 +1,231 @@ +/* + tre-internal.h - TRE internal definitions + + Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi> + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS + ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +*/ + +#include <regex.h> +#include <wchar.h> +#include <wctype.h> + +#undef TRE_MBSTATE + +#define NDEBUG + +#define TRE_REGEX_T_FIELD __opaque +typedef int reg_errcode_t; + +typedef wchar_t tre_char_t; + +#define DPRINT(msg) do { } while(0) + +#define elementsof(x) ( sizeof(x) / sizeof(x[0]) ) + +#define tre_mbrtowc(pwc, s, n, ps) (mbtowc((pwc), (s), (n))) + +/* Wide characters. */ +typedef wint_t tre_cint_t; +#define TRE_CHAR_MAX 0x10ffff + +#define tre_isalnum iswalnum +#define tre_isalpha iswalpha +#define tre_isblank iswblank +#define tre_iscntrl iswcntrl +#define tre_isdigit iswdigit +#define tre_isgraph iswgraph +#define tre_islower iswlower +#define tre_isprint iswprint +#define tre_ispunct iswpunct +#define tre_isspace iswspace +#define tre_isupper iswupper +#define tre_isxdigit iswxdigit + +#define tre_tolower towlower +#define tre_toupper towupper +#define tre_strlen wcslen + +/* Use system provided iswctype() and wctype(). */ +typedef wctype_t tre_ctype_t; +#define tre_isctype iswctype +#define tre_ctype wctype + +/* Returns number of bytes to add to (char *)ptr to make it + properly aligned for the type. */ +#define ALIGN(ptr, type) \ + ((((long)ptr) % sizeof(type)) \ + ? (sizeof(type) - (((long)ptr) % sizeof(type))) \ + : 0) + +#undef MAX +#undef MIN +#define MAX(a, b) (((a) >= (b)) ? (a) : (b)) +#define MIN(a, b) (((a) <= (b)) ? (a) : (b)) + +/* TNFA transition type. A TNFA state is an array of transitions, + the terminator is a transition with NULL `state'. */ +typedef struct tnfa_transition tre_tnfa_transition_t; + +struct tnfa_transition { + /* Range of accepted characters. */ + tre_cint_t code_min; + tre_cint_t code_max; + /* Pointer to the destination state. */ + tre_tnfa_transition_t *state; + /* ID number of the destination state. */ + int state_id; + /* -1 terminated array of tags (or NULL). */ + int *tags; + /* Assertion bitmap. */ + int assertions; + /* Assertion parameters. */ + union { + /* Character class assertion. */ + tre_ctype_t class; + /* Back reference assertion. */ + int backref; + } u; + /* Negative character class assertions. */ + tre_ctype_t *neg_classes; +}; + + +/* Assertions. */ +#define ASSERT_AT_BOL 1 /* Beginning of line. */ +#define ASSERT_AT_EOL 2 /* End of line. */ +#define ASSERT_CHAR_CLASS 4 /* Character class in `class'. */ +#define ASSERT_CHAR_CLASS_NEG 8 /* Character classes in `neg_classes'. */ +#define ASSERT_AT_BOW 16 /* Beginning of word. */ +#define ASSERT_AT_EOW 32 /* End of word. */ +#define ASSERT_AT_WB 64 /* Word boundary. */ +#define ASSERT_AT_WB_NEG 128 /* Not a word boundary. */ +#define ASSERT_BACKREF 256 /* A back reference in `backref'. */ +#define ASSERT_LAST 256 + +/* Tag directions. */ +typedef enum { + TRE_TAG_MINIMIZE = 0, + TRE_TAG_MAXIMIZE = 1 +} tre_tag_direction_t; + +/* Instructions to compute submatch register values from tag values + after a successful match. */ +struct tre_submatch_data { + /* Tag that gives the value for rm_so (submatch start offset). */ + int so_tag; + /* Tag that gives the value for rm_eo (submatch end offset). */ + int eo_tag; + /* List of submatches this submatch is contained in. */ + int *parents; +}; + +typedef struct tre_submatch_data tre_submatch_data_t; + + +/* TNFA definition. */ +typedef struct tnfa tre_tnfa_t; + +struct tnfa { + tre_tnfa_transition_t *transitions; + unsigned int num_transitions; + tre_tnfa_transition_t *initial; + tre_tnfa_transition_t *final; + tre_submatch_data_t *submatch_data; + char *firstpos_chars; + int first_char; + unsigned int num_submatches; + tre_tag_direction_t *tag_directions; + int *minimal_tags; + int num_tags; + int num_minimals; + int end_tag; + int num_states; + int cflags; + int have_backrefs; + int have_approx; +}; + +/* from tre-mem.h: */ + +#define TRE_MEM_BLOCK_SIZE 1024 + +typedef struct tre_list { + void *data; + struct tre_list *next; +} tre_list_t; + +typedef struct tre_mem_struct { + tre_list_t *blocks; + tre_list_t *current; + char *ptr; + size_t n; + int failed; + void **provided; +} *tre_mem_t; + +#define tre_mem_new_impl __tre_mem_new_impl +#define tre_mem_alloc_impl __tre_mem_alloc_impl +#define tre_mem_destroy __tre_mem_destroy + +tre_mem_t tre_mem_new_impl(int provided, void *provided_block); +void *tre_mem_alloc_impl(tre_mem_t mem, int provided, void *provided_block, + int zero, size_t size); + +/* Returns a new memory allocator or NULL if out of memory. */ +#define tre_mem_new() tre_mem_new_impl(0, NULL) + +/* Allocates a block of `size' bytes from `mem'. Returns a pointer to the + allocated block or NULL if an underlying malloc() failed. */ +#define tre_mem_alloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 0, size) + +/* Allocates a block of `size' bytes from `mem'. Returns a pointer to the + allocated block or NULL if an underlying malloc() failed. The memory + is set to zero. */ +#define tre_mem_calloc(mem, size) tre_mem_alloc_impl(mem, 0, NULL, 1, size) + +#ifdef TRE_USE_ALLOCA +/* alloca() versions. Like above, but memory is allocated with alloca() + instead of malloc(). */ + +#define tre_mem_newa() \ + tre_mem_new_impl(1, alloca(sizeof(struct tre_mem_struct))) + +#define tre_mem_alloca(mem, size) \ + ((mem)->n >= (size) \ + ? tre_mem_alloc_impl((mem), 1, NULL, 0, (size)) \ + : tre_mem_alloc_impl((mem), 1, alloca(TRE_MEM_BLOCK_SIZE), 0, (size))) +#endif /* TRE_USE_ALLOCA */ + + +/* Frees the memory allocator and all memory allocated with it. */ +void tre_mem_destroy(tre_mem_t mem); + +#define xmalloc malloc +#define xcalloc calloc +#define xfree free +#define xrealloc realloc + diff --git a/system/lib/libcextra.symbols b/system/lib/libcextra.symbols index 522137c6..d169ead6 100644 --- a/system/lib/libcextra.symbols +++ b/system/lib/libcextra.symbols @@ -2,6 +2,9 @@ T __strxfrm_l W __towlower_l W __towupper_l + T __tre_mem_alloc_impl + T __tre_mem_destroy + T __tre_mem_new_impl T __wcscoll_l T __wcsxfrm_l W __wctype_l @@ -47,6 +50,10 @@ T mbsrtowcs T mbstowcs T mbtowc + T regcomp + T regerror + T regexec + T regfree T strfmon T strfmon_l T strxfrm diff --git a/system/lib/libcxx/CREDITS.TXT b/system/lib/libcxx/CREDITS.TXT index 5e4d14ec..368b526f 100644 --- a/system/lib/libcxx/CREDITS.TXT +++ b/system/lib/libcxx/CREDITS.TXT @@ -31,7 +31,7 @@ D: FreeBSD and Solaris ports, libcxxrt support, some atomics work. N: Marshall Clow E: mclow.lists@gmail.com E: marshall@idio.com -D: Minor patches and bug fixes. +D: C++14 support, patches and bug fixes. N: Bill Fisher E: william.w.fisher@gmail.com @@ -76,6 +76,10 @@ N: Bjorn Reese E: breese@users.sourceforge.net D: Initial regex prototype +N: Nico Rieck +E: nico.rieck@gmail.com +D: Windows fixes + N: Jonathan Sauer D: Minor patches, mostly related to constexpr @@ -105,6 +109,10 @@ N: Zhang Xiongpang E: zhangxiongpang@gmail.com D: Minor patches and bug fixes. +N: Xing Xue +E: xingxue@ca.ibm.com +D: AIX port + N: Zhihao Yuan E: lichray@gmail.com D: Standard compatibility fixes. diff --git a/system/lib/libcxx/algorithm.cpp b/system/lib/libcxx/algorithm.cpp index 6d5cf7c0..10c4c331 100644 --- a/system/lib/libcxx/algorithm.cpp +++ b/system/lib/libcxx/algorithm.cpp @@ -7,6 +7,7 @@ // //===----------------------------------------------------------------------===// +#define _LIBCPP_EXTERN_TEMPLATE(...) extern template __VA_ARGS__; #include "algorithm" #include "random" #include "mutex" diff --git a/system/lib/libcxx/debug.cpp b/system/lib/libcxx/debug.cpp index c9b09b7a..d0e86795 100644 --- a/system/lib/libcxx/debug.cpp +++ b/system/lib/libcxx/debug.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// -#define _LIBCPP_DEBUG2 1 +#define _LIBCPP_DEBUG 1 #include "__config" #include "__debug" #include "functional" @@ -118,20 +118,19 @@ void __libcpp_db::__insert_ic(void* __i, const void* __c) { WLock _(mut()); - __i_node* i = __insert_iterator(__i); - const char* errmsg = - "Container constructed in a translation unit with debug mode disabled." - " But it is being used in a translation unit with debug mode enabled." - " Enable it in the other translation unit with #define _LIBCPP_DEBUG2 1"; - _LIBCPP_ASSERT(__cbeg_ != __cend_, errmsg); + if (__cbeg_ == __cend_) + return; size_t hc = hash<const void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); __c_node* c = __cbeg_[hc]; - _LIBCPP_ASSERT(c != nullptr, errmsg); + if (c == nullptr) + return; while (c->__c_ != __c) { c = c->__next_; - _LIBCPP_ASSERT(c != nullptr, errmsg); + if (c == nullptr) + return; } + __i_node* i = __insert_iterator(__i); c->__add(i); i->__c_ = c; } @@ -217,18 +216,23 @@ void __libcpp_db::__invalidate_all(void* __c) { WLock _(mut()); - size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); - __c_node* p = __cbeg_[hc]; - _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all A"); - while (p->__c_ != __c) - { - p = p->__next_; - _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __invalidate_all B"); - } - while (p->end_ != p->beg_) + if (__cend_ != __cbeg_) { - --p->end_; - (*p->end_)->__c_ = nullptr; + size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); + __c_node* p = __cbeg_[hc]; + if (p == nullptr) + return; + while (p->__c_ != __c) + { + p = p->__next_; + if (p == nullptr) + return; + } + while (p->end_ != p->beg_) + { + --p->end_; + (*p->end_)->__c_ = nullptr; + } } } @@ -236,13 +240,26 @@ __c_node* __libcpp_db::__find_c_and_lock(void* __c) const { mut().lock(); + if (__cend_ == __cbeg_) + { + mut().unlock(); + return nullptr; + } size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); __c_node* p = __cbeg_[hc]; - _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock A"); + if (p == nullptr) + { + mut().unlock(); + return nullptr; + } while (p->__c_ != __c) { p = p->__next_; - _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __find_c_and_lock B"); + if (p == nullptr) + { + mut().unlock(); + return nullptr; + } } return p; } @@ -271,28 +288,35 @@ void __libcpp_db::__erase_c(void* __c) { WLock _(mut()); - size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); - __c_node* p = __cbeg_[hc]; - __c_node* q = nullptr; - _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); - while (p->__c_ != __c) + if (__cend_ != __cbeg_) { - q = p; - p = p->__next_; - _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); - } - if (q == nullptr) - __cbeg_[hc] = p->__next_; - else - q->__next_ = p->__next_; - while (p->end_ != p->beg_) - { - --p->end_; - (*p->end_)->__c_ = nullptr; + size_t hc = hash<void*>()(__c) % static_cast<size_t>(__cend_ - __cbeg_); + __c_node* p = __cbeg_[hc]; + if (p == nullptr) + return; + __c_node* q = nullptr; + _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c A"); + while (p->__c_ != __c) + { + q = p; + p = p->__next_; + if (p == nullptr) + return; + _LIBCPP_ASSERT(p != nullptr, "debug mode internal logic error __erase_c B"); + } + if (q == nullptr) + __cbeg_[hc] = p->__next_; + else + q->__next_ = p->__next_; + while (p->end_ != p->beg_) + { + --p->end_; + (*p->end_)->__c_ = nullptr; + } + free(p->beg_); + free(p); + --__csz_; } - free(p->beg_); - free(p); - --__csz_; } void diff --git a/system/lib/libcxx/exception.cpp b/system/lib/libcxx/exception.cpp index 3487bd8b..83f6fd19 100644 --- a/system/lib/libcxx/exception.cpp +++ b/system/lib/libcxx/exception.cpp @@ -10,6 +10,7 @@ #include <stdio.h> #include "exception" +#include "new" #ifndef __has_include #define __has_include(inc) 0 @@ -90,14 +91,14 @@ terminate() _NOEXCEPT (*get_terminate())(); // handler should not return printf("terminate_handler unexpectedly returned\n"); - ::abort (); + ::abort(); #ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { // handler should not throw exception printf("terminate_handler unexpectedly threw an exception\n"); - ::abort (); + ::abort(); } #endif // _LIBCPP_NO_EXCEPTIONS } @@ -111,12 +112,17 @@ bool uncaught_exception() _NOEXCEPT // on Darwin, there is a helper function so __cxa_get_globals is private return __cxa_uncaught_exception(); #else // __APPLE__ - #warning uncaught_exception not yet implemented +# if defined(_MSC_VER) && ! defined(__clang__) + _LIBCPP_WARNING("uncaught_exception not yet implemented") +# else +# warning uncaught_exception not yet implemented +# endif printf("uncaught_exception not yet implemented\n"); ::abort(); #endif // __APPLE__ } + #ifndef _LIBCPPABI_VERSION exception::~exception() _NOEXCEPT @@ -143,16 +149,50 @@ const char* bad_exception::what() const _NOEXCEPT #endif +#if defined(__GLIBCXX__) + +// libsupc++ does not implement the dependent EH ABI and the functionality +// it uses to implement std::exception_ptr (which it declares as an alias of +// std::__exception_ptr::exception_ptr) is not directly exported to clients. So +// we have little choice but to hijack std::__exception_ptr::exception_ptr's +// (which fortunately has the same layout as our std::exception_ptr) copy +// constructor, assignment operator and destructor (which are part of its +// stable ABI), and its rethrow_exception(std::__exception_ptr::exception_ptr) +// function. + +namespace __exception_ptr +{ + +struct exception_ptr +{ + void* __ptr_; + + exception_ptr(const exception_ptr&) _NOEXCEPT; + exception_ptr& operator=(const exception_ptr&) _NOEXCEPT; + ~exception_ptr() _NOEXCEPT; +}; + +} + +_LIBCPP_NORETURN void rethrow_exception(__exception_ptr::exception_ptr); + +#endif exception_ptr::~exception_ptr() _NOEXCEPT { #if HAVE_DEPENDENT_EH_ABI __cxa_decrement_exception_refcount(__ptr_); +#elif defined(__GLIBCXX__) + reinterpret_cast<__exception_ptr::exception_ptr*>(this)->~exception_ptr(); #else - #warning exception_ptr not yet implemented +# if defined(_MSC_VER) && ! defined(__clang__) + _LIBCPP_WARNING("exception_ptr not yet implemented") +# else +# warning exception_ptr not yet implemented +# endif printf("exception_ptr not yet implemented\n"); ::abort(); -#endif // __APPLE__ +#endif } exception_ptr::exception_ptr(const exception_ptr& other) _NOEXCEPT @@ -160,11 +200,18 @@ exception_ptr::exception_ptr(const exception_ptr& other) _NOEXCEPT { #if HAVE_DEPENDENT_EH_ABI __cxa_increment_exception_refcount(__ptr_); +#elif defined(__GLIBCXX__) + new (reinterpret_cast<void*>(this)) __exception_ptr::exception_ptr( + reinterpret_cast<const __exception_ptr::exception_ptr&>(other)); #else - #warning exception_ptr not yet implemented +# if defined(_MSC_VER) && ! defined(__clang__) + _LIBCPP_WARNING("exception_ptr not yet implemented") +# else +# warning exception_ptr not yet implemented +# endif printf("exception_ptr not yet implemented\n"); ::abort(); -#endif // __APPLE__ +#endif } exception_ptr& exception_ptr::operator=(const exception_ptr& other) _NOEXCEPT @@ -177,11 +224,19 @@ exception_ptr& exception_ptr::operator=(const exception_ptr& other) _NOEXCEPT __ptr_ = other.__ptr_; } return *this; -#else // __APPLE__ - #warning exception_ptr not yet implemented +#elif defined(__GLIBCXX__) + *reinterpret_cast<__exception_ptr::exception_ptr*>(this) = + reinterpret_cast<const __exception_ptr::exception_ptr&>(other); + return *this; +#else +# if defined(_MSC_VER) && ! defined(__clang__) + _LIBCPP_WARNING("exception_ptr not yet implemented") +# else +# warning exception_ptr not yet implemented +# endif printf("exception_ptr not yet implemented\n"); ::abort(); -#endif // __APPLE__ +#endif } nested_exception::nested_exception() _NOEXCEPT @@ -189,10 +244,14 @@ nested_exception::nested_exception() _NOEXCEPT { } +#if !defined(__GLIBCXX__) + nested_exception::~nested_exception() _NOEXCEPT { } +#endif + _LIBCPP_NORETURN void nested_exception::rethrow_nested() const @@ -202,6 +261,7 @@ nested_exception::rethrow_nested() const rethrow_exception(__ptr_); } +#if !defined(__GLIBCXX__) exception_ptr current_exception() _NOEXCEPT { @@ -212,13 +272,19 @@ exception_ptr current_exception() _NOEXCEPT exception_ptr ptr; ptr.__ptr_ = __cxa_current_primary_exception(); return ptr; -#else // __APPLE__ - #warning exception_ptr not yet implemented +#else +# if defined(_MSC_VER) && ! defined(__clang__) + _LIBCPP_WARNING( "exception_ptr not yet implemented" ) +# else +# warning exception_ptr not yet implemented +# endif printf("exception_ptr not yet implemented\n"); ::abort(); -#endif // __APPLE__ +#endif } +#endif // !__GLIBCXX__ + _LIBCPP_NORETURN void rethrow_exception(exception_ptr p) { @@ -226,10 +292,16 @@ void rethrow_exception(exception_ptr p) __cxa_rethrow_primary_exception(p.__ptr_); // if p.__ptr_ is NULL, above returns so we terminate terminate(); -#else // __APPLE__ - #warning exception_ptr not yet implemented +#elif defined(__GLIBCXX__) + rethrow_exception(reinterpret_cast<__exception_ptr::exception_ptr&>(p)); +#else +# if defined(_MSC_VER) && ! defined(__clang__) + _LIBCPP_WARNING("exception_ptr not yet implemented") +# else +# warning exception_ptr not yet implemented +# endif printf("exception_ptr not yet implemented\n"); ::abort(); -#endif // __APPLE__ +#endif } } // std diff --git a/system/lib/libcxx/future.cpp b/system/lib/libcxx/future.cpp index 7d9a5b5d..70919ab7 100644 --- a/system/lib/libcxx/future.cpp +++ b/system/lib/libcxx/future.cpp @@ -26,11 +26,15 @@ __future_error_category::name() const _NOEXCEPT return "future"; } +#pragma clang diagnostic push +#pragma clang diagnostic ignored "-Wswitch" + string __future_error_category::message(int ev) const { switch (static_cast<future_errc>(ev)) { + case future_errc(0): // For backwards compatibility with C++11 (LWG 2056) case future_errc::broken_promise: return string("The associated promise has been destructed prior " "to the associated state becoming ready."); @@ -46,6 +50,8 @@ __future_error_category::message(int ev) const return string("unspecified future_errc value\n"); } +#pragma clang diagnostic pop + const error_category& future_category() _NOEXCEPT { diff --git a/system/lib/libcxx/ios.cpp b/system/lib/libcxx/ios.cpp index 732a61bb..004d3183 100644 --- a/system/lib/libcxx/ios.cpp +++ b/system/lib/libcxx/ios.cpp @@ -7,6 +7,8 @@ // //===----------------------------------------------------------------------===// +#define _LIBCPP_EXTERN_TEMPLATE(...) extern template __VA_ARGS__; + #include "ios" #include "streambuf" #include "istream" @@ -61,7 +63,7 @@ __iostream_category::message(int ev) const } const error_category& -iostream_category() +iostream_category() _NOEXCEPT { static __iostream_category s; return s; @@ -147,8 +149,11 @@ ios_base::getloc() const } // xalloc - +#if __has_feature(cxx_atomic) && !defined(__EMSCRIPTEN__) +atomic<int> ios_base::__xindex_ = ATOMIC_VAR_INIT(0); +#else int ios_base::__xindex_ = 0; +#endif int ios_base::xalloc() diff --git a/system/lib/libcxx/iostream.cpp b/system/lib/libcxx/iostream.cpp index f413681f..7102e438 100644 --- a/system/lib/libcxx/iostream.cpp +++ b/system/lib/libcxx/iostream.cpp @@ -22,14 +22,14 @@ _ALIGNAS_TYPE (__stdinbuf<wchar_t> ) static char __wcin [sizeof(__stdinbuf <wcha _ALIGNAS_TYPE (__stdoutbuf<wchar_t>) static char __wcout[sizeof(__stdoutbuf<wchar_t>)]; _ALIGNAS_TYPE (__stdoutbuf<wchar_t>) static char __wcerr[sizeof(__stdoutbuf<wchar_t>)]; -_ALIGNAS_TYPE (istream) char cin [sizeof(istream)]; -_ALIGNAS_TYPE (ostream) char cout[sizeof(ostream)]; -_ALIGNAS_TYPE (ostream) char cerr[sizeof(ostream)]; -_ALIGNAS_TYPE (ostream) char clog[sizeof(ostream)]; -_ALIGNAS_TYPE (wistream) char wcin [sizeof(wistream)]; -_ALIGNAS_TYPE (wostream) char wcout[sizeof(wostream)]; -_ALIGNAS_TYPE (wostream) char wcerr[sizeof(wostream)]; -_ALIGNAS_TYPE (wostream) char wclog[sizeof(wostream)]; +_ALIGNAS_TYPE (istream) _LIBCPP_FUNC_VIS char cin [sizeof(istream)]; +_ALIGNAS_TYPE (ostream) _LIBCPP_FUNC_VIS char cout[sizeof(ostream)]; +_ALIGNAS_TYPE (ostream) _LIBCPP_FUNC_VIS char cerr[sizeof(ostream)]; +_ALIGNAS_TYPE (ostream) _LIBCPP_FUNC_VIS char clog[sizeof(ostream)]; +_ALIGNAS_TYPE (wistream) _LIBCPP_FUNC_VIS char wcin [sizeof(wistream)]; +_ALIGNAS_TYPE (wostream) _LIBCPP_FUNC_VIS char wcout[sizeof(wostream)]; +_ALIGNAS_TYPE (wostream) _LIBCPP_FUNC_VIS char wcerr[sizeof(wostream)]; +_ALIGNAS_TYPE (wostream) _LIBCPP_FUNC_VIS char wclog[sizeof(wostream)]; ios_base::Init __start_std_streams; diff --git a/system/lib/libcxx/locale.cpp b/system/lib/libcxx/locale.cpp index ad64668f..a326323a 100644 --- a/system/lib/libcxx/locale.cpp +++ b/system/lib/libcxx/locale.cpp @@ -7,6 +7,8 @@ // //===----------------------------------------------------------------------===// +#define _LIBCPP_EXTERN_TEMPLATE(...) extern template __VA_ARGS__; + // On Solaris, we need to define something to make the C99 parts of localeconv // visible. #ifdef __sun__ @@ -26,7 +28,7 @@ #include "cstring" #include "cwctype" #include "__sso_allocator" -#ifdef _LIBCPP_MSVCRT +#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__) #include <support/win32/locale_win32.h> #else // _LIBCPP_MSVCRT #include <langinfo.h> @@ -36,7 +38,9 @@ // On Linux, wint_t and wchar_t have different signed-ness, and this causes // lots of noise in the build log, but no bugs that I know of. +#if defined(__clang__) #pragma clang diagnostic ignored "-Wsign-conversion" +#endif _LIBCPP_BEGIN_NAMESPACE_STD @@ -107,6 +111,11 @@ countof(const T * const begin, const T * const end) } +#if defined(_AIX) +// Set priority to INT_MIN + 256 + 150 +# pragma priority ( -2147483242 ) +#endif + const locale::category locale::none; const locale::category locale::collate; const locale::category locale::ctype; @@ -116,14 +125,23 @@ const locale::category locale::time; const locale::category locale::messages; const locale::category locale::all; +#if defined(__clang__) #pragma clang diagnostic push #pragma clang diagnostic ignored "-Wpadded" +#endif class _LIBCPP_HIDDEN locale::__imp : public facet { enum {N = 28}; +#if defined(_LIBCPP_MSVC) +// FIXME: MSVC doesn't support aligned parameters by value. +// I can't get the __sso_allocator to work here +// for MSVC I think for this reason. + vector<facet*> facets_; +#else vector<facet*, __sso_allocator<facet*, N> > facets_; +#endif string name_; public: explicit __imp(size_t refs = 0); @@ -147,7 +165,9 @@ private: template <class F> void install_from(const __imp& other); }; +#if defined(__clang__) #pragma clang diagnostic pop +#endif locale::__imp::__imp(size_t refs) : facet(refs), @@ -757,7 +777,7 @@ ctype<wchar_t>::~ctype() bool ctype<wchar_t>::do_is(mask m, char_type c) const { - return isascii(c) ? ctype<char>::classic_table()[c] & m : false; + return isascii(c) ? (ctype<char>::classic_table()[c] & m) != 0 : false; } const wchar_t* @@ -1009,12 +1029,14 @@ ctype<char>::classic_table() _NOEXCEPT return __cloc()->__ctype_b; #elif __sun__ return __ctype_mask; -#elif defined(_LIBCPP_MSVCRT) +#elif defined(_LIBCPP_MSVCRT) || defined(__MINGW32__) return _ctype+1; // internal ctype mask table defined in msvcrt.dll // This is assumed to be safe, which is a nonsense assumption because we're // going to end up dereferencing it later... #elif defined(__EMSCRIPTEN__) return *__ctype_b_loc(); +#elif defined(_AIX) + return (const unsigned long *)__lc_ctype_ptr->obj->mask; #else // Platform not supported: abort so the person doing the port knows what to // fix @@ -4350,7 +4372,7 @@ __num_put_base::__format_float(char* __fmtp, const char* __len, if (__flags & ios_base::showpoint) *__fmtp++ = '#'; ios_base::fmtflags floatfield = __flags & ios_base::floatfield; - bool uppercase = __flags & ios_base::uppercase; + bool uppercase = (__flags & ios_base::uppercase) != 0; if (floatfield == (ios_base::fixed | ios_base::scientific)) specify_precision = false; else @@ -4681,9 +4703,12 @@ __time_get::~__time_get() { freelocale(__loc_); } - +#if defined(__clang__) #pragma clang diagnostic ignored "-Wmissing-field-initializers" +#endif +#if defined(__GNUG__) #pragma GCC diagnostic ignored "-Wmissing-field-initializers" +#endif template <> string @@ -4829,7 +4854,9 @@ __time_get_storage<char>::__analyze(char fmt, const ctype<char>& ct) return result; } +#if defined(__clang__) #pragma clang diagnostic ignored "-Wmissing-braces" +#endif template <> wstring @@ -5848,7 +5875,7 @@ moneypunct_byname<char, true>::init(const char* nm) __frac_digits_ = lc->int_frac_digits; else __frac_digits_ = base::do_frac_digits(); -#ifdef _LIBCPP_MSVCRT +#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__) if (lc->p_sign_posn == 0) #else // _LIBCPP_MSVCRT if (lc->int_p_sign_posn == 0) @@ -5856,7 +5883,7 @@ moneypunct_byname<char, true>::init(const char* nm) __positive_sign_ = "()"; else __positive_sign_ = lc->positive_sign; -#ifdef _LIBCPP_MSVCRT +#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__) if(lc->n_sign_posn == 0) #else // _LIBCPP_MSVCRT if (lc->int_n_sign_posn == 0) @@ -5868,7 +5895,7 @@ moneypunct_byname<char, true>::init(const char* nm) // the same places in curr_symbol since there's no way to // represent anything else. string_type __dummy_curr_symbol = __curr_symbol_; -#ifdef _LIBCPP_MSVCRT +#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__) __init_pat(__pos_format_, __dummy_curr_symbol, true, lc->p_cs_precedes, lc->p_sep_by_space, lc->p_sign_posn, ' '); __init_pat(__neg_format_, __curr_symbol_, true, @@ -6007,7 +6034,7 @@ moneypunct_byname<wchar_t, true>::init(const char* nm) __frac_digits_ = lc->int_frac_digits; else __frac_digits_ = base::do_frac_digits(); -#ifdef _LIBCPP_MSVCRT +#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__) if (lc->p_sign_posn == 0) #else // _LIBCPP_MSVCRT if (lc->int_p_sign_posn == 0) @@ -6027,7 +6054,7 @@ moneypunct_byname<wchar_t, true>::init(const char* nm) wbe = wbuf + j; __positive_sign_.assign(wbuf, wbe); } -#ifdef _LIBCPP_MSVCRT +#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__) if (lc->n_sign_posn == 0) #else // _LIBCPP_MSVCRT if (lc->int_n_sign_posn == 0) @@ -6051,7 +6078,7 @@ moneypunct_byname<wchar_t, true>::init(const char* nm) // the same places in curr_symbol since there's no way to // represent anything else. string_type __dummy_curr_symbol = __curr_symbol_; -#ifdef _LIBCPP_MSVCRT +#if defined(_LIBCPP_MSVCRT) || defined(__MINGW32__) __init_pat(__pos_format_, __dummy_curr_symbol, true, lc->p_cs_precedes, lc->p_sep_by_space, lc->p_sign_posn, L' '); __init_pat(__neg_format_, __curr_symbol_, true, diff --git a/system/lib/libcxx/mutex.cpp b/system/lib/libcxx/mutex.cpp index 42195aa8..07678978 100644 --- a/system/lib/libcxx/mutex.cpp +++ b/system/lib/libcxx/mutex.cpp @@ -42,6 +42,7 @@ void mutex::unlock() _NOEXCEPT { int ec = pthread_mutex_unlock(&__m_); + (void)ec; assert(ec == 0); } @@ -79,6 +80,7 @@ fail: recursive_mutex::~recursive_mutex() { int e = pthread_mutex_destroy(&__m_); + (void)e; assert(e == 0); } @@ -94,6 +96,7 @@ void recursive_mutex::unlock() _NOEXCEPT { int e = pthread_mutex_unlock(&__m_); + (void)e; assert(e == 0); } diff --git a/system/lib/libcxx/new.cpp b/system/lib/libcxx/new.cpp index b23a516f..fa0331a8 100644 --- a/system/lib/libcxx/new.cpp +++ b/system/lib/libcxx/new.cpp @@ -7,6 +7,8 @@ // //===----------------------------------------------------------------------===// +#define _LIBCPP_BUILDING_NEW + #include <stdlib.h> #include "new" @@ -28,16 +30,18 @@ #if defined(LIBCXXRT) || __has_include(<cxxabi.h>) #include <cxxabi.h> #endif // __has_include(<cxxabi.h>) - #ifndef _LIBCPPABI_VERSION + #if !defined(_LIBCPPABI_VERSION) && !defined(__GLIBCXX__) static std::new_handler __new_handler; #endif // _LIBCPPABI_VERSION #endif +#ifndef __GLIBCXX__ + // Implement all new and delete operators as weak definitions // in this shared library, so that they can be overriden by programs // that define non-weak copies of the functions. -__attribute__((__weak__, __visibility__("default"))) +_LIBCPP_WEAK _LIBCPP_NEW_DELETE_VIS void * operator new(std::size_t size) #if !__has_feature(cxx_noexcept) @@ -64,7 +68,7 @@ operator new(std::size_t size) return p; } -__attribute__((__weak__, __visibility__("default"))) +_LIBCPP_WEAK _LIBCPP_NEW_DELETE_VIS void* operator new(size_t size, const std::nothrow_t&) _NOEXCEPT { @@ -83,7 +87,7 @@ operator new(size_t size, const std::nothrow_t&) _NOEXCEPT return p; } -__attribute__((__weak__, __visibility__("default"))) +_LIBCPP_WEAK _LIBCPP_NEW_DELETE_VIS void* operator new[](size_t size) #if !__has_feature(cxx_noexcept) @@ -93,7 +97,7 @@ operator new[](size_t size) return ::operator new(size); } -__attribute__((__weak__, __visibility__("default"))) +_LIBCPP_WEAK _LIBCPP_NEW_DELETE_VIS void* operator new[](size_t size, const std::nothrow_t&) _NOEXCEPT { @@ -112,7 +116,7 @@ operator new[](size_t size, const std::nothrow_t&) _NOEXCEPT return p; } -__attribute__((__weak__, __visibility__("default"))) +_LIBCPP_WEAK _LIBCPP_NEW_DELETE_VIS void operator delete(void* ptr) _NOEXCEPT { @@ -120,34 +124,40 @@ operator delete(void* ptr) _NOEXCEPT ::free(ptr); } -__attribute__((__weak__, __visibility__("default"))) +_LIBCPP_WEAK _LIBCPP_NEW_DELETE_VIS void operator delete(void* ptr, const std::nothrow_t&) _NOEXCEPT { ::operator delete(ptr); } -__attribute__((__weak__, __visibility__("default"))) +_LIBCPP_WEAK _LIBCPP_NEW_DELETE_VIS void operator delete[] (void* ptr) _NOEXCEPT { ::operator delete (ptr); } -__attribute__((__weak__, __visibility__("default"))) +_LIBCPP_WEAK _LIBCPP_NEW_DELETE_VIS void operator delete[] (void* ptr, const std::nothrow_t&) _NOEXCEPT { ::operator delete[](ptr); } +#endif // !__GLIBCXX__ + namespace std { +#ifndef __GLIBCXX__ const nothrow_t nothrow = {}; +#endif #ifndef _LIBCPPABI_VERSION +#ifndef __GLIBCXX__ + new_handler set_new_handler(new_handler handler) _NOEXCEPT { @@ -160,12 +170,16 @@ get_new_handler() _NOEXCEPT return __sync_fetch_and_add(&__new_handler, (new_handler)0); } +#endif // !__GLIBCXX__ + #ifndef LIBCXXRT bad_alloc::bad_alloc() _NOEXCEPT { } +#ifndef __GLIBCXX__ + bad_alloc::~bad_alloc() _NOEXCEPT { } @@ -176,6 +190,8 @@ bad_alloc::what() const _NOEXCEPT return "std::bad_alloc"; } +#endif // !__GLIBCXX__ + #endif //LIBCXXRT bad_array_new_length::bad_array_new_length() _NOEXCEPT @@ -187,12 +203,28 @@ bad_array_new_length::~bad_array_new_length() _NOEXCEPT } const char* +bad_array_length::what() const _NOEXCEPT +{ + return "bad_array_length"; +} + +bad_array_length::bad_array_length() _NOEXCEPT +{ +} + +bad_array_length::~bad_array_length() _NOEXCEPT +{ +} + +const char* bad_array_new_length::what() const _NOEXCEPT { return "bad_array_new_length"; } -#endif +#endif // _LIBCPPABI_VERSION + +#ifndef LIBSTDCXX void __throw_bad_alloc() @@ -202,4 +234,6 @@ __throw_bad_alloc() #endif } +#endif // !LIBSTDCXX + } // std diff --git a/system/lib/libcxx/optional.cpp b/system/lib/libcxx/optional.cpp new file mode 100644 index 00000000..fde071c9 --- /dev/null +++ b/system/lib/libcxx/optional.cpp @@ -0,0 +1,25 @@ +//===------------------------ optional.cpp --------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "optional" + +namespace std // purposefully not using versioning namespace +{ + +#ifdef _LIBCPP_HAS_NO_DEFAULTED_FUNCTIONS + +bad_optional_access::~bad_optional_access() _NOEXCEPT {} + +#else + +bad_optional_access::~bad_optional_access() _NOEXCEPT = default; + +#endif + +} // std diff --git a/system/lib/libcxx/random.cpp b/system/lib/libcxx/random.cpp index 97a40c50..47cdee40 100644 --- a/system/lib/libcxx/random.cpp +++ b/system/lib/libcxx/random.cpp @@ -7,6 +7,12 @@ // //===----------------------------------------------------------------------===// +#if defined(_WIN32) +// Must be defined before including stdlib.h to enable rand_s(). +#define _CRT_RAND_S +#include <stdio.h> +#endif + #include "random" #include "system_error" @@ -19,6 +25,25 @@ _LIBCPP_BEGIN_NAMESPACE_STD +#if defined(_WIN32) +random_device::random_device(const string&) +{ +} + +random_device::~random_device() +{ +} + +unsigned +random_device::operator()() +{ + unsigned r; + errno_t err = rand_s(&r); + if (err) + __throw_system_error(err, "random_device rand_s failed."); + return r; +} +#else random_device::random_device(const string& __token) : __f_(open(__token.c_str(), O_RDONLY)) { @@ -38,6 +63,7 @@ random_device::operator()() read(__f_, &r, sizeof(r)); return r; } +#endif // defined(_WIN32) double random_device::entropy() const _NOEXCEPT diff --git a/system/lib/libcxx/readme.txt b/system/lib/libcxx/readme.txt index 7687e5b2..ae8090fd 100644 --- a/system/lib/libcxx/readme.txt +++ b/system/lib/libcxx/readme.txt @@ -1 +1 @@ -These files are from libc++, svn revision 187959, 2013-08-08. +These files are from libc++, svn revision 194185, 2013-11-07. diff --git a/system/lib/libcxx/shared_mutex.cpp b/system/lib/libcxx/shared_mutex.cpp new file mode 100644 index 00000000..5fb22e44 --- /dev/null +++ b/system/lib/libcxx/shared_mutex.cpp @@ -0,0 +1,101 @@ +//===---------------------- shared_mutex.cpp ------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is dual licensed under the MIT and the University of Illinois Open +// Source Licenses. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#define _LIBCPP_BUILDING_SHARED_MUTEX +#include "shared_mutex" + +_LIBCPP_BEGIN_NAMESPACE_STD + +shared_mutex::shared_mutex() + : __state_(0) +{ +} + +// Exclusive ownership + +void +shared_mutex::lock() +{ + unique_lock<mutex> lk(__mut_); + while (__state_ & __write_entered_) + __gate1_.wait(lk); + __state_ |= __write_entered_; + while (__state_ & __n_readers_) + __gate2_.wait(lk); +} + +bool +shared_mutex::try_lock() +{ + unique_lock<mutex> lk(__mut_); + if (__state_ == 0) + { + __state_ = __write_entered_; + return true; + } + return false; +} + +void +shared_mutex::unlock() +{ + lock_guard<mutex> _(__mut_); + __state_ = 0; + __gate1_.notify_all(); +} + +// Shared ownership + +void +shared_mutex::lock_shared() +{ + unique_lock<mutex> lk(__mut_); + while ((__state_ & __write_entered_) || (__state_ & __n_readers_) == __n_readers_) + __gate1_.wait(lk); + unsigned num_readers = (__state_ & __n_readers_) + 1; + __state_ &= ~__n_readers_; + __state_ |= num_readers; +} + +bool +shared_mutex::try_lock_shared() +{ + unique_lock<mutex> lk(__mut_); + unsigned num_readers = __state_ & __n_readers_; + if (!(__state_ & __write_entered_) && num_readers != __n_readers_) + { + ++num_readers; + __state_ &= ~__n_readers_; + __state_ |= num_readers; + return true; + } + return false; +} + +void +shared_mutex::unlock_shared() +{ + lock_guard<mutex> _(__mut_); + unsigned num_readers = (__state_ & __n_readers_) - 1; + __state_ &= ~__n_readers_; + __state_ |= num_readers; + if (__state_ & __write_entered_) + { + if (num_readers == 0) + __gate2_.notify_one(); + } + else + { + if (num_readers == __n_readers_ - 1) + __gate1_.notify_one(); + } +} + + +_LIBCPP_END_NAMESPACE_STD diff --git a/system/lib/libcxx/stdexcept.cpp b/system/lib/libcxx/stdexcept.cpp index 8d25f3ee..a4207d60 100644 --- a/system/lib/libcxx/stdexcept.cpp +++ b/system/lib/libcxx/stdexcept.cpp @@ -28,7 +28,9 @@ // Note: optimize for size +#if ! defined(_LIBCPP_MSVC) #pragma GCC visibility push(hidden) +#endif namespace { @@ -47,9 +49,9 @@ private: count_t& count() const _NOEXCEPT {return (count_t&)(*(str_ - sizeof(count_t)));} public: explicit __libcpp_nmstr(const char* msg); - __libcpp_nmstr(const __libcpp_nmstr& s) _LIBCPP_CANTTHROW; - __libcpp_nmstr& operator=(const __libcpp_nmstr& s) _LIBCPP_CANTTHROW; - ~__libcpp_nmstr() _LIBCPP_CANTTHROW; + __libcpp_nmstr(const __libcpp_nmstr& s) _NOEXCEPT; + __libcpp_nmstr& operator=(const __libcpp_nmstr& s) _NOEXCEPT; + ~__libcpp_nmstr(); const char* c_str() const _NOEXCEPT {return str_;} }; @@ -65,14 +67,14 @@ __libcpp_nmstr::__libcpp_nmstr(const char* msg) } inline -__libcpp_nmstr::__libcpp_nmstr(const __libcpp_nmstr& s) +__libcpp_nmstr::__libcpp_nmstr(const __libcpp_nmstr& s) _NOEXCEPT : str_(s.str_) { __sync_add_and_fetch(&count(), 1); } __libcpp_nmstr& -__libcpp_nmstr::operator=(const __libcpp_nmstr& s) +__libcpp_nmstr::operator=(const __libcpp_nmstr& s) _NOEXCEPT { const char* p = str_; str_ = s.str_; @@ -91,7 +93,9 @@ __libcpp_nmstr::~__libcpp_nmstr() } +#if ! defined(_LIBCPP_MSVC) #pragma GCC visibility pop +#endif namespace std // purposefully not using versioning namespace { @@ -123,7 +127,7 @@ logic_error::operator=(const logic_error& le) _NOEXCEPT return *this; } -#ifndef _LIBCPPABI_VERSION +#if !defined(_LIBCPPABI_VERSION) && !defined(LIBSTDCXX) logic_error::~logic_error() _NOEXCEPT { @@ -167,7 +171,7 @@ runtime_error::operator=(const runtime_error& le) _NOEXCEPT return *this; } -#ifndef _LIBCPPABI_VERSION +#if !defined(_LIBCPPABI_VERSION) && !defined(LIBSTDCXX) runtime_error::~runtime_error() _NOEXCEPT { diff --git a/system/lib/libcxx/string.cpp b/system/lib/libcxx/string.cpp index 5a869116..fde52129 100644 --- a/system/lib/libcxx/string.cpp +++ b/system/lib/libcxx/string.cpp @@ -7,6 +7,8 @@ // //===----------------------------------------------------------------------===// +#define _LIBCPP_EXTERN_TEMPLATE(...) extern template __VA_ARGS__; + #include "string" #include "cstdlib" #include "cwchar" @@ -89,7 +91,7 @@ inline int as_integer(const string& func, const string& s, size_t* idx, int base ) { - // Use long as no Stantard string to integer exists. + // Use long as no Standard string to integer exists. long r = as_integer_helper<long>( func, s, idx, base, strtol ); if (r < numeric_limits<int>::min() || numeric_limits<int>::max() < r) throw_from_string_out_of_range(func); diff --git a/system/lib/libcxx/strstream.cpp b/system/lib/libcxx/strstream.cpp index 518422bd..c1965ea3 100644 --- a/system/lib/libcxx/strstream.cpp +++ b/system/lib/libcxx/strstream.cpp @@ -156,13 +156,13 @@ strstreambuf::overflow(int_type __c) { if ((__strmode_ & __dynamic) == 0 || (__strmode_ & __frozen) != 0) return int_type(EOF); - streamsize old_size = (epptr() ? epptr() : egptr()) - eback(); - streamsize new_size = max<streamsize>(__alsize_, 2*old_size); + size_t old_size = static_cast<size_t> ((epptr() ? epptr() : egptr()) - eback()); + size_t new_size = max<size_t>(static_cast<size_t>(__alsize_), 2*old_size); if (new_size == 0) new_size = __default_alsize; char* buf = nullptr; if (__palloc_) - buf = static_cast<char*>(__palloc_(static_cast<size_t>(new_size))); + buf = static_cast<char*>(__palloc_(new_size)); else buf = new char[new_size]; if (buf == nullptr) @@ -229,8 +229,8 @@ strstreambuf::pos_type strstreambuf::seekoff(off_type __off, ios_base::seekdir __way, ios_base::openmode __which) { off_type __p(-1); - bool pos_in = __which & ios::in; - bool pos_out = __which & ios::out; + bool pos_in = (__which & ios::in) != 0; + bool pos_out = (__which & ios::out) != 0; bool legal = false; switch (__way) { @@ -287,8 +287,8 @@ strstreambuf::pos_type strstreambuf::seekpos(pos_type __sp, ios_base::openmode __which) { off_type __p(-1); - bool pos_in = __which & ios::in; - bool pos_out = __which & ios::out; + bool pos_in = (__which & ios::in) != 0; + bool pos_out = (__which & ios::out) != 0; if (pos_in || pos_out) { if (!((pos_in && gptr() == nullptr) || (pos_out && pptr() == nullptr))) diff --git a/system/lib/libcxx/support/win32/locale_win32.cpp b/system/lib/libcxx/support/win32/locale_win32.cpp index a639ade4..1729d84a 100644 --- a/system/lib/libcxx/support/win32/locale_win32.cpp +++ b/system/lib/libcxx/support/win32/locale_win32.cpp @@ -8,9 +8,8 @@ // //===----------------------------------------------------------------------===// -#include "support/win32/locale_win32.h" +#include <locale> #include <cstdarg> // va_start, va_end -#include <cwchar> // mbstate_t // FIXME: base currently unused. Needs manual work to construct the new locale locale_t newlocale( int mask, const char * locale, locale_t /*base*/ ) @@ -34,38 +33,38 @@ lconv *localeconv_l( locale_t loc ) __locale_raii __current( uselocale(loc), uselocale ); return localeconv(); } -size_t mbrlen_l( const char *__restrict__ s, size_t n, - mbstate_t *__restrict__ ps, locale_t loc ) +size_t mbrlen_l( const char *__restrict s, size_t n, + mbstate_t *__restrict ps, locale_t loc ) { __locale_raii __current( uselocale(loc), uselocale ); return mbrlen( s, n, ps ); } -size_t mbsrtowcs_l( wchar_t *__restrict__ dst, const char **__restrict__ src, - size_t len, mbstate_t *__restrict__ ps, locale_t loc ) +size_t mbsrtowcs_l( wchar_t *__restrict dst, const char **__restrict src, + size_t len, mbstate_t *__restrict ps, locale_t loc ) { __locale_raii __current( uselocale(loc), uselocale ); return mbsrtowcs( dst, src, len, ps ); } -size_t wcrtomb_l( char *__restrict__ s, wchar_t wc, mbstate_t *__restrict__ ps, +size_t wcrtomb_l( char *__restrict s, wchar_t wc, mbstate_t *__restrict ps, locale_t loc ) { __locale_raii __current( uselocale(loc), uselocale ); return wcrtomb( s, wc, ps ); } -size_t mbrtowc_l( wchar_t *__restrict__ pwc, const char *__restrict__ s, - size_t n, mbstate_t *__restrict__ ps, locale_t loc ) +size_t mbrtowc_l( wchar_t *__restrict pwc, const char *__restrict s, + size_t n, mbstate_t *__restrict ps, locale_t loc ) { __locale_raii __current( uselocale(loc), uselocale ); return mbrtowc( pwc, s, n, ps ); } -size_t mbsnrtowcs_l( wchar_t *__restrict__ dst, const char **__restrict__ src, - size_t nms, size_t len, mbstate_t *__restrict__ ps, locale_t loc ) +size_t mbsnrtowcs_l( wchar_t *__restrict dst, const char **__restrict src, + size_t nms, size_t len, mbstate_t *__restrict ps, locale_t loc ) { __locale_raii __current( uselocale(loc), uselocale ); return mbsnrtowcs( dst, src, nms, len, ps ); } -size_t wcsnrtombs_l( char *__restrict__ dst, const wchar_t **__restrict__ src, - size_t nwc, size_t len, mbstate_t *__restrict__ ps, locale_t loc ) +size_t wcsnrtombs_l( char *__restrict dst, const wchar_t **__restrict src, + size_t nwc, size_t len, mbstate_t *__restrict ps, locale_t loc ) { __locale_raii __current( uselocale(loc), uselocale ); return wcsnrtombs( dst, src, nwc, len, ps ); diff --git a/system/lib/libcxx/support/win32/support.cpp b/system/lib/libcxx/support/win32/support.cpp index 4215a700..6ee31e0c 100644 --- a/system/lib/libcxx/support/win32/support.cpp +++ b/system/lib/libcxx/support/win32/support.cpp @@ -14,14 +14,7 @@ #include <cstdio> // vsprintf, vsnprintf #include <cstring> // strcpy, wcsncpy #include <cwchar> // mbstate_t -#include <memory> // unique_ptr -namespace { // Private - - struct free_deleter { - inline void operator()(char* p) { free(p); } - }; -} // Some of these functions aren't standard or if they conform, the name does not. int asprintf(char **sptr, const char *__restrict format, ...) @@ -29,44 +22,44 @@ int asprintf(char **sptr, const char *__restrict format, ...) va_list ap; va_start(ap, format); int result; -#ifndef _LIBCPP_NO_EXCEPTIONS - try { -#endif - result = vasprintf(sptr, format, ap); -#ifndef _LIBCPP_NO_EXCEPTIONS - } catch( ... ) { - va_end(ap); - throw; - } -#endif + result = vasprintf(sptr, format, ap); va_end(ap); return result; } -// Like sprintf, but when return value >= 0 it returns a pointer to a malloc'd string in *sptr. +// Like sprintf, but when return value >= 0 it returns +// a pointer to a malloc'd string in *sptr. // If return >= 0, use free to delete *sptr. int vasprintf( char **sptr, const char *__restrict format, va_list ap ) { *sptr = NULL; - int count = _vsnprintf( NULL, 0, format, ap ); // Query the buffer size required. - if( count >= 0 ) { - std::unique_ptr<char, free_deleter> p( static_cast<char*>(malloc(count+1)) ); - if ( ! p ) - return -1; - if ( vsnprintf( p.get(), count+1, format, ap ) == count ) // We should have used exactly what was required. - *sptr = p.release(); - else // Otherwise something is wrong, likely a bug in vsnprintf. If so free the memory and report the error. - return -1; // Pointer will get automaticlaly deleted. + // Query the count required. + int count = _vsnprintf( NULL, 0, format, ap ); + if (count < 0) + return count; + size_t buffer_size = static_cast<size_t>(count) + 1; + char* p = static_cast<char*>(malloc(buffer_size)); + if ( ! p ) + return -1; + // If we haven't used exactly what was required, something is wrong. + // Maybe bug in vsnprintf. Report the error and return. + if (_vsnprintf(p, buffer_size, format, ap) != count) { + free(p); + return -1; } - + // All good. This is returning memory to the caller not freeing it. + *sptr = p; return count; } -// Returns >= 0: the number of wide characters found in the multi byte sequence src (of src_size_bytes), -// that fit in the buffer dst (of max_dest_chars elements size). The count returned excludes the null terminator. -// When dst is NULL, no characters are copied and no "out" parameters are updated. +// Returns >= 0: the number of wide characters found in the +// multi byte sequence src (of src_size_bytes), that fit in the buffer dst +// (of max_dest_chars elements size). The count returned excludes the +// null terminator. When dst is NULL, no characters are copied +// and no "out" parameters are updated. // Returns (size_t) -1: an incomplete sequence encountered. -// Leaves *src pointing the next character to convert or NULL if a null character was converted from *src. +// Leaves *src pointing the next character to convert or NULL +// if a null character was converted from *src. size_t mbsnrtowcs( wchar_t *__restrict dst, const char **__restrict src, size_t src_size_bytes, size_t max_dest_chars, mbstate_t *__restrict ps ) { @@ -112,10 +105,13 @@ size_t mbsnrtowcs( wchar_t *__restrict dst, const char **__restrict src, } // Converts max_source_chars from the wide character buffer pointer to by *src, -// into the multi byte character sequence buffer stored at dst which must be dst_size_bytes bytes in size. -// Returns >= 0: the number of bytes in the sequence sequence converted frome *src, excluding the null terminator. +// into the multi byte character sequence buffer stored at dst which must be +// dst_size_bytes bytes in size. +// Returns >= 0: the number of bytes in the sequence sequence +// converted frome *src, excluding the null terminator. // Returns size_t(-1) if an error occurs, also sets errno. -// If dst is NULL dst_size_bytes is ignored and no bytes are copied to dst and no "out" parameters are updated. +// If dst is NULL dst_size_bytes is ignored and no bytes are copied to dst +// and no "out" parameters are updated. size_t wcsnrtombs( char *__restrict dst, const wchar_t **__restrict src, size_t max_source_chars, size_t dst_size_bytes, mbstate_t *__restrict ps ) { @@ -138,7 +134,8 @@ size_t wcsnrtombs( char *__restrict dst, const wchar_t **__restrict src, result = wcrtomb_s( &char_size, dst + dest_converted, dest_remaining, c, ps); else result = wcrtomb_s( &char_size, NULL, 0, c, ps); - // If result is zero there is no error and char_size contains the size of the multi-byte-sequence converted. + // If result is zero there is no error and char_size contains the + // size of the multi-byte-sequence converted. // Otherwise result indicates an errno type error. if ( result == no_error ) { if ( c == L'\0' ) { diff --git a/system/lib/libcxx/symbols b/system/lib/libcxx/symbols index 92a665d8..51368bce 100644 --- a/system/lib/libcxx/symbols +++ b/system/lib/libcxx/symbols @@ -235,27 +235,27 @@ W _ZNKSt3__113basic_ostreamIcNS_11char_traitsIcEEE6sentrycvbEv W _ZNKSt3__113basic_ostreamIwNS_11char_traitsIwEEE6sentrycvbEv T _ZNKSt3__113random_device7entropyEv - T _ZNKSt3__114__codecvt_utf8IDiE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__114__codecvt_utf8IDiE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__114__codecvt_utf8IDiE11do_encodingEv T _ZNKSt3__114__codecvt_utf8IDiE13do_max_lengthEv T _ZNKSt3__114__codecvt_utf8IDiE16do_always_noconvEv - T _ZNKSt3__114__codecvt_utf8IDiE5do_inER10_mbstate_tPKcS5_RS5_PDiS7_RS7_ - T _ZNKSt3__114__codecvt_utf8IDiE6do_outER10_mbstate_tPKDiS5_RS5_PcS7_RS7_ - T _ZNKSt3__114__codecvt_utf8IDiE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__114__codecvt_utf8IDsE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__114__codecvt_utf8IDiE5do_inER11__mbstate_tPKcS5_RS5_PDiS7_RS7_ + T _ZNKSt3__114__codecvt_utf8IDiE6do_outER11__mbstate_tPKDiS5_RS5_PcS7_RS7_ + T _ZNKSt3__114__codecvt_utf8IDiE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__114__codecvt_utf8IDsE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__114__codecvt_utf8IDsE11do_encodingEv T _ZNKSt3__114__codecvt_utf8IDsE13do_max_lengthEv T _ZNKSt3__114__codecvt_utf8IDsE16do_always_noconvEv - T _ZNKSt3__114__codecvt_utf8IDsE5do_inER10_mbstate_tPKcS5_RS5_PDsS7_RS7_ - T _ZNKSt3__114__codecvt_utf8IDsE6do_outER10_mbstate_tPKDsS5_RS5_PcS7_RS7_ - T _ZNKSt3__114__codecvt_utf8IDsE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__114__codecvt_utf8IwE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__114__codecvt_utf8IDsE5do_inER11__mbstate_tPKcS5_RS5_PDsS7_RS7_ + T _ZNKSt3__114__codecvt_utf8IDsE6do_outER11__mbstate_tPKDsS5_RS5_PcS7_RS7_ + T _ZNKSt3__114__codecvt_utf8IDsE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__114__codecvt_utf8IwE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__114__codecvt_utf8IwE11do_encodingEv T _ZNKSt3__114__codecvt_utf8IwE13do_max_lengthEv T _ZNKSt3__114__codecvt_utf8IwE16do_always_noconvEv - T _ZNKSt3__114__codecvt_utf8IwE5do_inER10_mbstate_tPKcS5_RS5_PwS7_RS7_ - T _ZNKSt3__114__codecvt_utf8IwE6do_outER10_mbstate_tPKwS5_RS5_PcS7_RS7_ - T _ZNKSt3__114__codecvt_utf8IwE9do_lengthER10_mbstate_tPKcS5_j + T _ZNKSt3__114__codecvt_utf8IwE5do_inER11__mbstate_tPKcS5_RS5_PwS7_RS7_ + T _ZNKSt3__114__codecvt_utf8IwE6do_outER11__mbstate_tPKwS5_RS5_PcS7_RS7_ + T _ZNKSt3__114__codecvt_utf8IwE9do_lengthER11__mbstate_tPKcS5_j T _ZNKSt3__114collate_bynameIcE10do_compareEPKcS3_S3_S3_ T _ZNKSt3__114collate_bynameIcE12do_transformEPKcS3_ T _ZNKSt3__114collate_bynameIwE10do_compareEPKwS3_S3_S3_ @@ -263,48 +263,48 @@ T _ZNKSt3__114error_category10equivalentERKNS_10error_codeEi T _ZNKSt3__114error_category10equivalentEiRKNS_15error_conditionE T _ZNKSt3__114error_category23default_error_conditionEi - T _ZNKSt3__115__codecvt_utf16IDiLb0EE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__115__codecvt_utf16IDiLb0EE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__115__codecvt_utf16IDiLb0EE11do_encodingEv T _ZNKSt3__115__codecvt_utf16IDiLb0EE13do_max_lengthEv T _ZNKSt3__115__codecvt_utf16IDiLb0EE16do_always_noconvEv - T _ZNKSt3__115__codecvt_utf16IDiLb0EE5do_inER10_mbstate_tPKcS5_RS5_PDiS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IDiLb0EE6do_outER10_mbstate_tPKDiS5_RS5_PcS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IDiLb0EE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__115__codecvt_utf16IDiLb1EE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__115__codecvt_utf16IDiLb0EE5do_inER11__mbstate_tPKcS5_RS5_PDiS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IDiLb0EE6do_outER11__mbstate_tPKDiS5_RS5_PcS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IDiLb0EE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__115__codecvt_utf16IDiLb1EE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__115__codecvt_utf16IDiLb1EE11do_encodingEv T _ZNKSt3__115__codecvt_utf16IDiLb1EE13do_max_lengthEv T _ZNKSt3__115__codecvt_utf16IDiLb1EE16do_always_noconvEv - T _ZNKSt3__115__codecvt_utf16IDiLb1EE5do_inER10_mbstate_tPKcS5_RS5_PDiS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IDiLb1EE6do_outER10_mbstate_tPKDiS5_RS5_PcS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IDiLb1EE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__115__codecvt_utf16IDsLb0EE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__115__codecvt_utf16IDiLb1EE5do_inER11__mbstate_tPKcS5_RS5_PDiS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IDiLb1EE6do_outER11__mbstate_tPKDiS5_RS5_PcS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IDiLb1EE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__115__codecvt_utf16IDsLb0EE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__115__codecvt_utf16IDsLb0EE11do_encodingEv T _ZNKSt3__115__codecvt_utf16IDsLb0EE13do_max_lengthEv T _ZNKSt3__115__codecvt_utf16IDsLb0EE16do_always_noconvEv - T _ZNKSt3__115__codecvt_utf16IDsLb0EE5do_inER10_mbstate_tPKcS5_RS5_PDsS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IDsLb0EE6do_outER10_mbstate_tPKDsS5_RS5_PcS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IDsLb0EE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__115__codecvt_utf16IDsLb1EE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__115__codecvt_utf16IDsLb0EE5do_inER11__mbstate_tPKcS5_RS5_PDsS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IDsLb0EE6do_outER11__mbstate_tPKDsS5_RS5_PcS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IDsLb0EE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__115__codecvt_utf16IDsLb1EE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__115__codecvt_utf16IDsLb1EE11do_encodingEv T _ZNKSt3__115__codecvt_utf16IDsLb1EE13do_max_lengthEv T _ZNKSt3__115__codecvt_utf16IDsLb1EE16do_always_noconvEv - T _ZNKSt3__115__codecvt_utf16IDsLb1EE5do_inER10_mbstate_tPKcS5_RS5_PDsS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IDsLb1EE6do_outER10_mbstate_tPKDsS5_RS5_PcS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IDsLb1EE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__115__codecvt_utf16IwLb0EE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__115__codecvt_utf16IDsLb1EE5do_inER11__mbstate_tPKcS5_RS5_PDsS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IDsLb1EE6do_outER11__mbstate_tPKDsS5_RS5_PcS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IDsLb1EE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__115__codecvt_utf16IwLb0EE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__115__codecvt_utf16IwLb0EE11do_encodingEv T _ZNKSt3__115__codecvt_utf16IwLb0EE13do_max_lengthEv T _ZNKSt3__115__codecvt_utf16IwLb0EE16do_always_noconvEv - T _ZNKSt3__115__codecvt_utf16IwLb0EE5do_inER10_mbstate_tPKcS5_RS5_PwS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IwLb0EE6do_outER10_mbstate_tPKwS5_RS5_PcS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IwLb0EE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__115__codecvt_utf16IwLb1EE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__115__codecvt_utf16IwLb0EE5do_inER11__mbstate_tPKcS5_RS5_PwS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IwLb0EE6do_outER11__mbstate_tPKwS5_RS5_PcS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IwLb0EE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__115__codecvt_utf16IwLb1EE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__115__codecvt_utf16IwLb1EE11do_encodingEv T _ZNKSt3__115__codecvt_utf16IwLb1EE13do_max_lengthEv T _ZNKSt3__115__codecvt_utf16IwLb1EE16do_always_noconvEv - T _ZNKSt3__115__codecvt_utf16IwLb1EE5do_inER10_mbstate_tPKcS5_RS5_PwS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IwLb1EE6do_outER10_mbstate_tPKwS5_RS5_PcS7_RS7_ - T _ZNKSt3__115__codecvt_utf16IwLb1EE9do_lengthER10_mbstate_tPKcS5_j + T _ZNKSt3__115__codecvt_utf16IwLb1EE5do_inER11__mbstate_tPKcS5_RS5_PwS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IwLb1EE6do_outER11__mbstate_tPKwS5_RS5_PcS7_RS7_ + T _ZNKSt3__115__codecvt_utf16IwLb1EE9do_lengthER11__mbstate_tPKcS5_j W _ZNKSt3__115basic_streambufIcNS_11char_traitsIcEEE4gptrEv W _ZNKSt3__115basic_streambufIcNS_11char_traitsIcEEE4pptrEv W _ZNKSt3__115basic_streambufIcNS_11char_traitsIcEEE5ebackEv @@ -377,27 +377,27 @@ T _ZNKSt3__119__iostream_category4nameEv T _ZNKSt3__119__iostream_category7messageEi T _ZNKSt3__119__shared_weak_count13__get_deleterERKSt9type_info - T _ZNKSt3__120__codecvt_utf8_utf16IDiE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__120__codecvt_utf8_utf16IDiE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__120__codecvt_utf8_utf16IDiE11do_encodingEv T _ZNKSt3__120__codecvt_utf8_utf16IDiE13do_max_lengthEv T _ZNKSt3__120__codecvt_utf8_utf16IDiE16do_always_noconvEv - T _ZNKSt3__120__codecvt_utf8_utf16IDiE5do_inER10_mbstate_tPKcS5_RS5_PDiS7_RS7_ - T _ZNKSt3__120__codecvt_utf8_utf16IDiE6do_outER10_mbstate_tPKDiS5_RS5_PcS7_RS7_ - T _ZNKSt3__120__codecvt_utf8_utf16IDiE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__120__codecvt_utf8_utf16IDsE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__120__codecvt_utf8_utf16IDiE5do_inER11__mbstate_tPKcS5_RS5_PDiS7_RS7_ + T _ZNKSt3__120__codecvt_utf8_utf16IDiE6do_outER11__mbstate_tPKDiS5_RS5_PcS7_RS7_ + T _ZNKSt3__120__codecvt_utf8_utf16IDiE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__120__codecvt_utf8_utf16IDsE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__120__codecvt_utf8_utf16IDsE11do_encodingEv T _ZNKSt3__120__codecvt_utf8_utf16IDsE13do_max_lengthEv T _ZNKSt3__120__codecvt_utf8_utf16IDsE16do_always_noconvEv - T _ZNKSt3__120__codecvt_utf8_utf16IDsE5do_inER10_mbstate_tPKcS5_RS5_PDsS7_RS7_ - T _ZNKSt3__120__codecvt_utf8_utf16IDsE6do_outER10_mbstate_tPKDsS5_RS5_PcS7_RS7_ - T _ZNKSt3__120__codecvt_utf8_utf16IDsE9do_lengthER10_mbstate_tPKcS5_j - T _ZNKSt3__120__codecvt_utf8_utf16IwE10do_unshiftER10_mbstate_tPcS4_RS4_ + T _ZNKSt3__120__codecvt_utf8_utf16IDsE5do_inER11__mbstate_tPKcS5_RS5_PDsS7_RS7_ + T _ZNKSt3__120__codecvt_utf8_utf16IDsE6do_outER11__mbstate_tPKDsS5_RS5_PcS7_RS7_ + T _ZNKSt3__120__codecvt_utf8_utf16IDsE9do_lengthER11__mbstate_tPKcS5_j + T _ZNKSt3__120__codecvt_utf8_utf16IwE10do_unshiftER11__mbstate_tPcS4_RS4_ T _ZNKSt3__120__codecvt_utf8_utf16IwE11do_encodingEv T _ZNKSt3__120__codecvt_utf8_utf16IwE13do_max_lengthEv T _ZNKSt3__120__codecvt_utf8_utf16IwE16do_always_noconvEv - T _ZNKSt3__120__codecvt_utf8_utf16IwE5do_inER10_mbstate_tPKcS5_RS5_PwS7_RS7_ - T _ZNKSt3__120__codecvt_utf8_utf16IwE6do_outER10_mbstate_tPKwS5_RS5_PcS7_RS7_ - T _ZNKSt3__120__codecvt_utf8_utf16IwE9do_lengthER10_mbstate_tPKcS5_j + T _ZNKSt3__120__codecvt_utf8_utf16IwE5do_inER11__mbstate_tPKcS5_RS5_PwS7_RS7_ + T _ZNKSt3__120__codecvt_utf8_utf16IwE6do_outER11__mbstate_tPKwS5_RS5_PcS7_RS7_ + T _ZNKSt3__120__codecvt_utf8_utf16IwE9do_lengthER11__mbstate_tPKcS5_j T _ZNKSt3__120__time_get_c_storageIcE3__XEv T _ZNKSt3__120__time_get_c_storageIcE3__cEv T _ZNKSt3__120__time_get_c_storageIcE3__rEv @@ -450,34 +450,34 @@ T _ZNKSt3__16locale9has_facetERNS0_2idE T _ZNKSt3__16locale9use_facetERNS0_2idE T _ZNKSt3__16localeeqERKS0_ - T _ZNKSt3__17codecvtIDic10_mbstate_tE10do_unshiftERS1_PcS4_RS4_ - T _ZNKSt3__17codecvtIDic10_mbstate_tE11do_encodingEv - T _ZNKSt3__17codecvtIDic10_mbstate_tE13do_max_lengthEv - T _ZNKSt3__17codecvtIDic10_mbstate_tE16do_always_noconvEv - T _ZNKSt3__17codecvtIDic10_mbstate_tE5do_inERS1_PKcS5_RS5_PDiS7_RS7_ - T _ZNKSt3__17codecvtIDic10_mbstate_tE6do_outERS1_PKDiS5_RS5_PcS7_RS7_ - T _ZNKSt3__17codecvtIDic10_mbstate_tE9do_lengthERS1_PKcS5_j - T _ZNKSt3__17codecvtIDsc10_mbstate_tE10do_unshiftERS1_PcS4_RS4_ - T _ZNKSt3__17codecvtIDsc10_mbstate_tE11do_encodingEv - T _ZNKSt3__17codecvtIDsc10_mbstate_tE13do_max_lengthEv - T _ZNKSt3__17codecvtIDsc10_mbstate_tE16do_always_noconvEv - T _ZNKSt3__17codecvtIDsc10_mbstate_tE5do_inERS1_PKcS5_RS5_PDsS7_RS7_ - T _ZNKSt3__17codecvtIDsc10_mbstate_tE6do_outERS1_PKDsS5_RS5_PcS7_RS7_ - T _ZNKSt3__17codecvtIDsc10_mbstate_tE9do_lengthERS1_PKcS5_j - T _ZNKSt3__17codecvtIcc10_mbstate_tE10do_unshiftERS1_PcS4_RS4_ - T _ZNKSt3__17codecvtIcc10_mbstate_tE11do_encodingEv - T _ZNKSt3__17codecvtIcc10_mbstate_tE13do_max_lengthEv - T _ZNKSt3__17codecvtIcc10_mbstate_tE16do_always_noconvEv - T _ZNKSt3__17codecvtIcc10_mbstate_tE5do_inERS1_PKcS5_RS5_PcS7_RS7_ - T _ZNKSt3__17codecvtIcc10_mbstate_tE6do_outERS1_PKcS5_RS5_PcS7_RS7_ - T _ZNKSt3__17codecvtIcc10_mbstate_tE9do_lengthERS1_PKcS5_j - T _ZNKSt3__17codecvtIwc10_mbstate_tE10do_unshiftERS1_PcS4_RS4_ - T _ZNKSt3__17codecvtIwc10_mbstate_tE11do_encodingEv - T _ZNKSt3__17codecvtIwc10_mbstate_tE13do_max_lengthEv - T _ZNKSt3__17codecvtIwc10_mbstate_tE16do_always_noconvEv - T _ZNKSt3__17codecvtIwc10_mbstate_tE5do_inERS1_PKcS5_RS5_PwS7_RS7_ - T _ZNKSt3__17codecvtIwc10_mbstate_tE6do_outERS1_PKwS5_RS5_PcS7_RS7_ - T _ZNKSt3__17codecvtIwc10_mbstate_tE9do_lengthERS1_PKcS5_j + T _ZNKSt3__17codecvtIDic11__mbstate_tE10do_unshiftERS1_PcS4_RS4_ + T _ZNKSt3__17codecvtIDic11__mbstate_tE11do_encodingEv + T _ZNKSt3__17codecvtIDic11__mbstate_tE13do_max_lengthEv + T _ZNKSt3__17codecvtIDic11__mbstate_tE16do_always_noconvEv + T _ZNKSt3__17codecvtIDic11__mbstate_tE5do_inERS1_PKcS5_RS5_PDiS7_RS7_ + T _ZNKSt3__17codecvtIDic11__mbstate_tE6do_outERS1_PKDiS5_RS5_PcS7_RS7_ + T _ZNKSt3__17codecvtIDic11__mbstate_tE9do_lengthERS1_PKcS5_j + T _ZNKSt3__17codecvtIDsc11__mbstate_tE10do_unshiftERS1_PcS4_RS4_ + T _ZNKSt3__17codecvtIDsc11__mbstate_tE11do_encodingEv + T _ZNKSt3__17codecvtIDsc11__mbstate_tE13do_max_lengthEv + T _ZNKSt3__17codecvtIDsc11__mbstate_tE16do_always_noconvEv + T _ZNKSt3__17codecvtIDsc11__mbstate_tE5do_inERS1_PKcS5_RS5_PDsS7_RS7_ + T _ZNKSt3__17codecvtIDsc11__mbstate_tE6do_outERS1_PKDsS5_RS5_PcS7_RS7_ + T _ZNKSt3__17codecvtIDsc11__mbstate_tE9do_lengthERS1_PKcS5_j + T _ZNKSt3__17codecvtIcc11__mbstate_tE10do_unshiftERS1_PcS4_RS4_ + T _ZNKSt3__17codecvtIcc11__mbstate_tE11do_encodingEv + T _ZNKSt3__17codecvtIcc11__mbstate_tE13do_max_lengthEv + T _ZNKSt3__17codecvtIcc11__mbstate_tE16do_always_noconvEv + T _ZNKSt3__17codecvtIcc11__mbstate_tE5do_inERS1_PKcS5_RS5_PcS7_RS7_ + T _ZNKSt3__17codecvtIcc11__mbstate_tE6do_outERS1_PKcS5_RS5_PcS7_RS7_ + T _ZNKSt3__17codecvtIcc11__mbstate_tE9do_lengthERS1_PKcS5_j + T _ZNKSt3__17codecvtIwc11__mbstate_tE10do_unshiftERS1_PcS4_RS4_ + T _ZNKSt3__17codecvtIwc11__mbstate_tE11do_encodingEv + T _ZNKSt3__17codecvtIwc11__mbstate_tE13do_max_lengthEv + T _ZNKSt3__17codecvtIwc11__mbstate_tE16do_always_noconvEv + T _ZNKSt3__17codecvtIwc11__mbstate_tE5do_inERS1_PKcS5_RS5_PwS7_RS7_ + T _ZNKSt3__17codecvtIwc11__mbstate_tE6do_outERS1_PKwS5_RS5_PcS7_RS7_ + T _ZNKSt3__17codecvtIwc11__mbstate_tE9do_lengthERS1_PKcS5_j W _ZNKSt3__17collateIcE10do_compareEPKcS3_S3_S3_ W _ZNKSt3__17collateIcE12do_transformEPKcS3_ W _ZNKSt3__17collateIcE4hashEPKcS3_ @@ -490,6 +490,15 @@ W _ZNKSt3__17collateIwE7compareEPKwS3_S3_S3_ W _ZNKSt3__17collateIwE7do_hashEPKwS3_ W _ZNKSt3__17collateIwE9transformEPKwS3_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE15__do_get_signedIlEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE15__do_get_signedIxEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE17__do_get_unsignedIjEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE17__do_get_unsignedImEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE17__do_get_unsignedItEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE17__do_get_unsignedIyEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE23__do_get_floating_pointIdEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE23__do_get_floating_pointIeEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE23__do_get_floating_pointIfEES4_S4_S4_RNS_8ios_baseERjRT_ W _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE3getES4_S4_RNS_8ios_baseERjRPv W _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE3getES4_S4_RNS_8ios_baseERjRb W _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE3getES4_S4_RNS_8ios_baseERjRd @@ -512,6 +521,15 @@ W _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE6do_getES4_S4_RNS_8ios_baseERjRx W _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE6do_getES4_S4_RNS_8ios_baseERjRy W _ZNKSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEE6do_getES4_S4_RNS_8ios_baseERjS8_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE15__do_get_signedIlEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE15__do_get_signedIxEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE17__do_get_unsignedIjEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE17__do_get_unsignedImEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE17__do_get_unsignedItEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE17__do_get_unsignedIyEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE23__do_get_floating_pointIdEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE23__do_get_floating_pointIeEES4_S4_S4_RNS_8ios_baseERjRT_ + C _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE23__do_get_floating_pointIfEES4_S4_S4_RNS_8ios_baseERjRT_ W _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE3getES4_S4_RNS_8ios_baseERjRPv W _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE3getES4_S4_RNS_8ios_baseERjRb W _ZNKSt3__17num_getIwNS_19istreambuf_iteratorIwNS_11char_traitsIwEEEEE3getES4_S4_RNS_8ios_baseERjRd @@ -751,21 +769,21 @@ T _ZNSt16nested_exceptionD0Ev T _ZNSt16nested_exceptionD1Ev T _ZNSt16nested_exceptionD2Ev - C _ZNSt3__110__sscanf_lEPKcPvS1_z + C _ZNSt3__110__sscanf_lEPKcP15__locale_structS1_z C _ZNSt3__110__stdinbufIcE5imbueERKNS_6localeE C _ZNSt3__110__stdinbufIcE5uflowEv C _ZNSt3__110__stdinbufIcE9__getcharEb C _ZNSt3__110__stdinbufIcE9pbackfailEi C _ZNSt3__110__stdinbufIcE9underflowEv - C _ZNSt3__110__stdinbufIcEC2EP7__sFILEP10_mbstate_t + C _ZNSt3__110__stdinbufIcEC2EP8_IO_FILEP11__mbstate_t C _ZNSt3__110__stdinbufIcED0Ev C _ZNSt3__110__stdinbufIcED1Ev C _ZNSt3__110__stdinbufIwE5imbueERKNS_6localeE C _ZNSt3__110__stdinbufIwE5uflowEv C _ZNSt3__110__stdinbufIwE9__getcharEb - C _ZNSt3__110__stdinbufIwE9pbackfailEi + C _ZNSt3__110__stdinbufIwE9pbackfailEj C _ZNSt3__110__stdinbufIwE9underflowEv - C _ZNSt3__110__stdinbufIwEC2EP7__sFILEP10_mbstate_t + C _ZNSt3__110__stdinbufIwEC2EP8_IO_FILEP11__mbstate_t C _ZNSt3__110__stdinbufIwED0Ev C _ZNSt3__110__stdinbufIwED1Ev T _ZNSt3__110__time_getC1EPKc @@ -867,12 +885,14 @@ W _ZNSt3__111__money_putIwEC2Ev C _ZNSt3__111__stdoutbufIcE4syncEv C _ZNSt3__111__stdoutbufIcE5imbueERKNS_6localeE + C _ZNSt3__111__stdoutbufIcE6xsputnEPKci C _ZNSt3__111__stdoutbufIcE8overflowEi C _ZNSt3__111__stdoutbufIcED0Ev C _ZNSt3__111__stdoutbufIcED1Ev C _ZNSt3__111__stdoutbufIwE4syncEv C _ZNSt3__111__stdoutbufIwE5imbueERKNS_6localeE - C _ZNSt3__111__stdoutbufIwE8overflowEi + C _ZNSt3__111__stdoutbufIwE6xsputnEPKwi + C _ZNSt3__111__stdoutbufIwE8overflowEj C _ZNSt3__111__stdoutbufIwED0Ev C _ZNSt3__111__stdoutbufIwED1Ev T _ZNSt3__111regex_errorC1ENS_15regex_constants10error_typeE @@ -889,7 +909,7 @@ T _ZNSt3__111timed_mutexD1Ev T _ZNSt3__111timed_mutexD2Ev D _ZNSt3__111try_to_lockE - C _ZNSt3__112__asprintf_lEPPcPvPKcz + C _ZNSt3__112__asprintf_lEPPcP15__locale_structPKcz C _ZNSt3__112__do_messageD0Ev C _ZNSt3__112__do_messageD1Ev T _ZNSt3__112__do_nothingEPv @@ -903,7 +923,7 @@ T _ZNSt3__112__rs_defaultD1Ev T _ZNSt3__112__rs_defaultD2Ev T _ZNSt3__112__rs_defaultclEv - C _ZNSt3__112__snprintf_lEPcjPvPKcz + C _ZNSt3__112__snprintf_lEPcjP15__locale_structPKcz T _ZNSt3__112bad_weak_ptrD0Ev T _ZNSt3__112bad_weak_ptrD1Ev T _ZNSt3__112bad_weak_ptrD2Ev @@ -1190,7 +1210,7 @@ T _ZNSt3__112strstreambuf6__initEPciS1_ T _ZNSt3__112strstreambuf6freezeEb T _ZNSt3__112strstreambuf7seekoffExNS_8ios_base7seekdirEj - T _ZNSt3__112strstreambuf7seekposENS_4fposI10_mbstate_tEEj + T _ZNSt3__112strstreambuf7seekposENS_4fposI11__mbstate_tEEj T _ZNSt3__112strstreambuf8overflowEi T _ZNSt3__112strstreambuf9pbackfailEi T _ZNSt3__112strstreambuf9underflowEv @@ -1240,7 +1260,7 @@ W _ZNSt3__113basic_istreamIcNS_11char_traitsIcEEE4readEPci W _ZNSt3__113basic_istreamIcNS_11char_traitsIcEEE4swapERS3_ W _ZNSt3__113basic_istreamIcNS_11char_traitsIcEEE4syncEv - W _ZNSt3__113basic_istreamIcNS_11char_traitsIcEEE5seekgENS_4fposI10_mbstate_tEE + W _ZNSt3__113basic_istreamIcNS_11char_traitsIcEEE5seekgENS_4fposI11__mbstate_tEE W _ZNSt3__113basic_istreamIcNS_11char_traitsIcEEE5seekgExNS_8ios_base7seekdirE W _ZNSt3__113basic_istreamIcNS_11char_traitsIcEEE5tellgEv W _ZNSt3__113basic_istreamIcNS_11char_traitsIcEEE5ungetEv @@ -1286,11 +1306,11 @@ W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE4readEPwi W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE4swapERS3_ W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE4syncEv - W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE5seekgENS_4fposI10_mbstate_tEE + W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE5seekgENS_4fposI11__mbstate_tEE W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE5seekgExNS_8ios_base7seekdirE W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE5tellgEv W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE5ungetEv - W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE6ignoreEii + W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE6ignoreEij W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE6sentryC1ERS3_b W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE6sentryC2ERS3_b W _ZNSt3__113basic_istreamIwNS_11char_traitsIwEEE7getlineEPwi @@ -1325,7 +1345,7 @@ W _ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE3putEc W _ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE4swapERS3_ W _ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5flushEv - W _ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5seekpENS_4fposI10_mbstate_tEE + W _ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5seekpENS_4fposI11__mbstate_tEE W _ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5seekpExNS_8ios_base7seekdirE W _ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5tellpEv W _ZNSt3__113basic_ostreamIcNS_11char_traitsIcEEE5writeEPKci @@ -1363,7 +1383,7 @@ W _ZNSt3__113basic_ostreamIwNS_11char_traitsIwEEE3putEw W _ZNSt3__113basic_ostreamIwNS_11char_traitsIwEEE4swapERS3_ W _ZNSt3__113basic_ostreamIwNS_11char_traitsIwEEE5flushEv - W _ZNSt3__113basic_ostreamIwNS_11char_traitsIwEEE5seekpENS_4fposI10_mbstate_tEE + W _ZNSt3__113basic_ostreamIwNS_11char_traitsIwEEE5seekpENS_4fposI11__mbstate_tEE W _ZNSt3__113basic_ostreamIwNS_11char_traitsIwEEE5seekpExNS_8ios_base7seekdirE W _ZNSt3__113basic_ostreamIwNS_11char_traitsIwEEE5tellpEv W _ZNSt3__113basic_ostreamIwNS_11char_traitsIwEEE5writeEPKwi @@ -1436,34 +1456,34 @@ W _ZNSt3__114basic_iostreamIcNS_11char_traitsIcEEED1Ev W _ZNSt3__114basic_iostreamIcNS_11char_traitsIcEEED2Ev W _ZNSt3__114basic_iostreamIcNS_11char_traitsIcEEEaSEOS3_ - W _ZNSt3__114codecvt_bynameIDic10_mbstate_tEC1EPKcj - W _ZNSt3__114codecvt_bynameIDic10_mbstate_tEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj - W _ZNSt3__114codecvt_bynameIDic10_mbstate_tEC2EPKcj - W _ZNSt3__114codecvt_bynameIDic10_mbstate_tEC2ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj - W _ZNSt3__114codecvt_bynameIDic10_mbstate_tED0Ev - W _ZNSt3__114codecvt_bynameIDic10_mbstate_tED1Ev - W _ZNSt3__114codecvt_bynameIDic10_mbstate_tED2Ev - W _ZNSt3__114codecvt_bynameIDsc10_mbstate_tEC1EPKcj - W _ZNSt3__114codecvt_bynameIDsc10_mbstate_tEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj - W _ZNSt3__114codecvt_bynameIDsc10_mbstate_tEC2EPKcj - W _ZNSt3__114codecvt_bynameIDsc10_mbstate_tEC2ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj - W _ZNSt3__114codecvt_bynameIDsc10_mbstate_tED0Ev - W _ZNSt3__114codecvt_bynameIDsc10_mbstate_tED1Ev - W _ZNSt3__114codecvt_bynameIDsc10_mbstate_tED2Ev - W _ZNSt3__114codecvt_bynameIcc10_mbstate_tEC1EPKcj - W _ZNSt3__114codecvt_bynameIcc10_mbstate_tEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj - W _ZNSt3__114codecvt_bynameIcc10_mbstate_tEC2EPKcj - W _ZNSt3__114codecvt_bynameIcc10_mbstate_tEC2ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj - W _ZNSt3__114codecvt_bynameIcc10_mbstate_tED0Ev - W _ZNSt3__114codecvt_bynameIcc10_mbstate_tED1Ev - W _ZNSt3__114codecvt_bynameIcc10_mbstate_tED2Ev - W _ZNSt3__114codecvt_bynameIwc10_mbstate_tEC1EPKcj - W _ZNSt3__114codecvt_bynameIwc10_mbstate_tEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj - W _ZNSt3__114codecvt_bynameIwc10_mbstate_tEC2EPKcj - W _ZNSt3__114codecvt_bynameIwc10_mbstate_tEC2ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj - W _ZNSt3__114codecvt_bynameIwc10_mbstate_tED0Ev - W _ZNSt3__114codecvt_bynameIwc10_mbstate_tED1Ev - W _ZNSt3__114codecvt_bynameIwc10_mbstate_tED2Ev + W _ZNSt3__114codecvt_bynameIDic11__mbstate_tEC1EPKcj + W _ZNSt3__114codecvt_bynameIDic11__mbstate_tEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj + W _ZNSt3__114codecvt_bynameIDic11__mbstate_tEC2EPKcj + W _ZNSt3__114codecvt_bynameIDic11__mbstate_tEC2ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj + W _ZNSt3__114codecvt_bynameIDic11__mbstate_tED0Ev + W _ZNSt3__114codecvt_bynameIDic11__mbstate_tED1Ev + W _ZNSt3__114codecvt_bynameIDic11__mbstate_tED2Ev + W _ZNSt3__114codecvt_bynameIDsc11__mbstate_tEC1EPKcj + W _ZNSt3__114codecvt_bynameIDsc11__mbstate_tEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj + W _ZNSt3__114codecvt_bynameIDsc11__mbstate_tEC2EPKcj + W _ZNSt3__114codecvt_bynameIDsc11__mbstate_tEC2ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj + W _ZNSt3__114codecvt_bynameIDsc11__mbstate_tED0Ev + W _ZNSt3__114codecvt_bynameIDsc11__mbstate_tED1Ev + W _ZNSt3__114codecvt_bynameIDsc11__mbstate_tED2Ev + W _ZNSt3__114codecvt_bynameIcc11__mbstate_tEC1EPKcj + W _ZNSt3__114codecvt_bynameIcc11__mbstate_tEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj + W _ZNSt3__114codecvt_bynameIcc11__mbstate_tEC2EPKcj + W _ZNSt3__114codecvt_bynameIcc11__mbstate_tEC2ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj + W _ZNSt3__114codecvt_bynameIcc11__mbstate_tED0Ev + W _ZNSt3__114codecvt_bynameIcc11__mbstate_tED1Ev + W _ZNSt3__114codecvt_bynameIcc11__mbstate_tED2Ev + W _ZNSt3__114codecvt_bynameIwc11__mbstate_tEC1EPKcj + W _ZNSt3__114codecvt_bynameIwc11__mbstate_tEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj + W _ZNSt3__114codecvt_bynameIwc11__mbstate_tEC2EPKcj + W _ZNSt3__114codecvt_bynameIwc11__mbstate_tEC2ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj + W _ZNSt3__114codecvt_bynameIwc11__mbstate_tED0Ev + W _ZNSt3__114codecvt_bynameIwc11__mbstate_tED1Ev + W _ZNSt3__114codecvt_bynameIwc11__mbstate_tED2Ev T _ZNSt3__114collate_bynameIcEC1EPKcj T _ZNSt3__114collate_bynameIcEC1ERKNS_12basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEEj T _ZNSt3__114collate_bynameIcEC2EPKcj @@ -1509,7 +1529,7 @@ C _ZNSt3__115__time_get_tempIwED0Ev C _ZNSt3__115__time_get_tempIwED1Ev W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE10pubseekoffExNS_8ios_base7seekdirEj - W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE10pubseekposENS_4fposI10_mbstate_tEEj + W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE10pubseekposENS_4fposI11__mbstate_tEEj W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE4setgEPcS4_S4_ W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE4setpEPcS4_ W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE4swapERS3_ @@ -1529,7 +1549,7 @@ W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE6xsputnEPKci W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE7pubsyncEv W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE7seekoffExNS_8ios_base7seekdirEj - W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE7seekposENS_4fposI10_mbstate_tEEj + W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE7seekposENS_4fposI11__mbstate_tEEj W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE7sungetcEv W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE8in_availEv W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEE8overflowEi @@ -1548,7 +1568,7 @@ W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEED2Ev W _ZNSt3__115basic_streambufIcNS_11char_traitsIcEEEaSERKS3_ W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE10pubseekoffExNS_8ios_base7seekdirEj - W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE10pubseekposENS_4fposI10_mbstate_tEEj + W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE10pubseekposENS_4fposI11__mbstate_tEEj W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE4setgEPwS4_S4_ W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE4setpEPwS4_ W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE4swapERS3_ @@ -1568,12 +1588,12 @@ W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE6xsputnEPKwi W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE7pubsyncEv W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE7seekoffExNS_8ios_base7seekdirEj - W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE7seekposENS_4fposI10_mbstate_tEEj + W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE7seekposENS_4fposI11__mbstate_tEEj W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE7sungetcEv W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE8in_availEv - W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE8overflowEi + W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE8overflowEj W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE8pubimbueERKNS_6localeE - W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE9pbackfailEi + W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE9pbackfailEj W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE9pubsetbufEPwi W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE9showmanycEv W _ZNSt3__115basic_streambufIwNS_11char_traitsIwEEE9sputbackcEw @@ -1956,26 +1976,26 @@ C _ZNSt3__17__sort5IRNS_6__lessIwwEEPwEEjT0_S5_S5_S5_S5_T_ C _ZNSt3__17__sort5IRNS_6__lessIxxEEPxEEjT0_S5_S5_S5_S5_T_ C _ZNSt3__17__sort5IRNS_6__lessIyyEEPyEEjT0_S5_S5_S5_S5_T_ - D _ZNSt3__17codecvtIDic10_mbstate_tE2idE - T _ZNSt3__17codecvtIDic10_mbstate_tED0Ev - T _ZNSt3__17codecvtIDic10_mbstate_tED1Ev - T _ZNSt3__17codecvtIDic10_mbstate_tED2Ev - D _ZNSt3__17codecvtIDsc10_mbstate_tE2idE - T _ZNSt3__17codecvtIDsc10_mbstate_tED0Ev - T _ZNSt3__17codecvtIDsc10_mbstate_tED1Ev - T _ZNSt3__17codecvtIDsc10_mbstate_tED2Ev - D _ZNSt3__17codecvtIcc10_mbstate_tE2idE - T _ZNSt3__17codecvtIcc10_mbstate_tED0Ev - T _ZNSt3__17codecvtIcc10_mbstate_tED1Ev - T _ZNSt3__17codecvtIcc10_mbstate_tED2Ev - D _ZNSt3__17codecvtIwc10_mbstate_tE2idE - T _ZNSt3__17codecvtIwc10_mbstate_tEC1EPKcj - T _ZNSt3__17codecvtIwc10_mbstate_tEC1Ej - T _ZNSt3__17codecvtIwc10_mbstate_tEC2EPKcj - T _ZNSt3__17codecvtIwc10_mbstate_tEC2Ej - T _ZNSt3__17codecvtIwc10_mbstate_tED0Ev - T _ZNSt3__17codecvtIwc10_mbstate_tED1Ev - T _ZNSt3__17codecvtIwc10_mbstate_tED2Ev + D _ZNSt3__17codecvtIDic11__mbstate_tE2idE + T _ZNSt3__17codecvtIDic11__mbstate_tED0Ev + T _ZNSt3__17codecvtIDic11__mbstate_tED1Ev + T _ZNSt3__17codecvtIDic11__mbstate_tED2Ev + D _ZNSt3__17codecvtIDsc11__mbstate_tE2idE + T _ZNSt3__17codecvtIDsc11__mbstate_tED0Ev + T _ZNSt3__17codecvtIDsc11__mbstate_tED1Ev + T _ZNSt3__17codecvtIDsc11__mbstate_tED2Ev + D _ZNSt3__17codecvtIcc11__mbstate_tE2idE + T _ZNSt3__17codecvtIcc11__mbstate_tED0Ev + T _ZNSt3__17codecvtIcc11__mbstate_tED1Ev + T _ZNSt3__17codecvtIcc11__mbstate_tED2Ev + D _ZNSt3__17codecvtIwc11__mbstate_tE2idE + T _ZNSt3__17codecvtIwc11__mbstate_tEC1EPKcj + T _ZNSt3__17codecvtIwc11__mbstate_tEC1Ej + T _ZNSt3__17codecvtIwc11__mbstate_tEC2EPKcj + T _ZNSt3__17codecvtIwc11__mbstate_tEC2Ej + T _ZNSt3__17codecvtIwc11__mbstate_tED0Ev + T _ZNSt3__17codecvtIwc11__mbstate_tED1Ev + T _ZNSt3__17codecvtIwc11__mbstate_tED2Ev W _ZNSt3__17collateIcE2idE W _ZNSt3__17collateIcEC1Ej W _ZNSt3__17collateIcEC2Ej @@ -2241,7 +2261,6 @@ T _ZNSt3__19to_stringEx T _ZNSt3__19to_stringEy W _ZNSt3__1plIcNS_11char_traitsIcEENS_9allocatorIcEEEENS_12basic_stringIT_T0_T1_EEPKS6_RKS9_ - C _ZNSt3__1plIcNS_11char_traitsIcEENS_9allocatorIcEEEENS_12basic_stringIT_T0_T1_EERKS9_PKS6_ T _ZSt10unexpectedv T _ZSt13get_terminatev T _ZSt13set_terminatePFvvE @@ -2295,10 +2314,10 @@ C _ZTINSt3__114__num_put_baseE D _ZTINSt3__114__shared_countE W _ZTINSt3__114basic_iostreamIcNS_11char_traitsIcEEEE - W _ZTINSt3__114codecvt_bynameIDic10_mbstate_tEE - W _ZTINSt3__114codecvt_bynameIDsc10_mbstate_tEE - W _ZTINSt3__114codecvt_bynameIcc10_mbstate_tEE - W _ZTINSt3__114codecvt_bynameIwc10_mbstate_tEE + W _ZTINSt3__114codecvt_bynameIDic11__mbstate_tEE + W _ZTINSt3__114codecvt_bynameIDsc11__mbstate_tEE + W _ZTINSt3__114codecvt_bynameIcc11__mbstate_tEE + W _ZTINSt3__114codecvt_bynameIwc11__mbstate_tEE D _ZTINSt3__114collate_bynameIcEE D _ZTINSt3__114collate_bynameIwEE D _ZTINSt3__114error_categoryE @@ -2345,10 +2364,10 @@ D _ZTINSt3__15ctypeIwEE D _ZTINSt3__16locale5__impE D _ZTINSt3__16locale5facetE - D _ZTINSt3__17codecvtIDic10_mbstate_tEE - D _ZTINSt3__17codecvtIDsc10_mbstate_tEE - D _ZTINSt3__17codecvtIcc10_mbstate_tEE - D _ZTINSt3__17codecvtIwc10_mbstate_tEE + D _ZTINSt3__17codecvtIDic11__mbstate_tEE + D _ZTINSt3__17codecvtIDsc11__mbstate_tEE + D _ZTINSt3__17codecvtIcc11__mbstate_tEE + D _ZTINSt3__17codecvtIwc11__mbstate_tEE W _ZTINSt3__17collateIcEE W _ZTINSt3__17collateIwEE W _ZTINSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEEE @@ -2429,10 +2448,10 @@ C _ZTSNSt3__114__num_put_baseE D _ZTSNSt3__114__shared_countE W _ZTSNSt3__114basic_iostreamIcNS_11char_traitsIcEEEE - W _ZTSNSt3__114codecvt_bynameIDic10_mbstate_tEE - W _ZTSNSt3__114codecvt_bynameIDsc10_mbstate_tEE - W _ZTSNSt3__114codecvt_bynameIcc10_mbstate_tEE - W _ZTSNSt3__114codecvt_bynameIwc10_mbstate_tEE + W _ZTSNSt3__114codecvt_bynameIDic11__mbstate_tEE + W _ZTSNSt3__114codecvt_bynameIDsc11__mbstate_tEE + W _ZTSNSt3__114codecvt_bynameIcc11__mbstate_tEE + W _ZTSNSt3__114codecvt_bynameIwc11__mbstate_tEE D _ZTSNSt3__114collate_bynameIcEE D _ZTSNSt3__114collate_bynameIwEE D _ZTSNSt3__114error_categoryE @@ -2479,10 +2498,10 @@ D _ZTSNSt3__15ctypeIwEE D _ZTSNSt3__16locale5__impE D _ZTSNSt3__16locale5facetE - D _ZTSNSt3__17codecvtIDic10_mbstate_tEE - D _ZTSNSt3__17codecvtIDsc10_mbstate_tEE - D _ZTSNSt3__17codecvtIcc10_mbstate_tEE - D _ZTSNSt3__17codecvtIwc10_mbstate_tEE + D _ZTSNSt3__17codecvtIDic11__mbstate_tEE + D _ZTSNSt3__17codecvtIDsc11__mbstate_tEE + D _ZTSNSt3__17codecvtIcc11__mbstate_tEE + D _ZTSNSt3__17codecvtIwc11__mbstate_tEE W _ZTSNSt3__17collateIcEE W _ZTSNSt3__17collateIwEE W _ZTSNSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEEE @@ -2559,10 +2578,10 @@ D _ZTVNSt3__114__codecvt_utf8IwEE D _ZTVNSt3__114__shared_countE W _ZTVNSt3__114basic_iostreamIcNS_11char_traitsIcEEEE - W _ZTVNSt3__114codecvt_bynameIDic10_mbstate_tEE - W _ZTVNSt3__114codecvt_bynameIDsc10_mbstate_tEE - W _ZTVNSt3__114codecvt_bynameIcc10_mbstate_tEE - W _ZTVNSt3__114codecvt_bynameIwc10_mbstate_tEE + W _ZTVNSt3__114codecvt_bynameIDic11__mbstate_tEE + W _ZTVNSt3__114codecvt_bynameIDsc11__mbstate_tEE + W _ZTVNSt3__114codecvt_bynameIcc11__mbstate_tEE + W _ZTVNSt3__114codecvt_bynameIwc11__mbstate_tEE D _ZTVNSt3__114collate_bynameIcEE D _ZTVNSt3__114collate_bynameIwEE D _ZTVNSt3__114error_categoryE @@ -2605,10 +2624,10 @@ D _ZTVNSt3__15ctypeIwEE D _ZTVNSt3__16locale5__impE D _ZTVNSt3__16locale5facetE - D _ZTVNSt3__17codecvtIDic10_mbstate_tEE - D _ZTVNSt3__17codecvtIDsc10_mbstate_tEE - D _ZTVNSt3__17codecvtIcc10_mbstate_tEE - D _ZTVNSt3__17codecvtIwc10_mbstate_tEE + D _ZTVNSt3__17codecvtIDic11__mbstate_tEE + D _ZTVNSt3__17codecvtIDsc11__mbstate_tEE + D _ZTVNSt3__17codecvtIcc11__mbstate_tEE + D _ZTVNSt3__17codecvtIwc11__mbstate_tEE W _ZTVNSt3__17collateIcEE W _ZTVNSt3__17collateIwEE W _ZTVNSt3__17num_getIcNS_19istreambuf_iteratorIcNS_11char_traitsIcEEEEEE diff --git a/system/lib/libcxx/system_error.cpp b/system/lib/libcxx/system_error.cpp index 7376b770..b40409f8 100644 --- a/system/lib/libcxx/system_error.cpp +++ b/system/lib/libcxx/system_error.cpp @@ -7,6 +7,7 @@ // //===----------------------------------------------------------------------===// +#define _LIBCPP_BUILDING_SYSTEM_ERROR #include "system_error" #include "string" #include "cstring" diff --git a/system/lib/libcxx/thread.cpp b/system/lib/libcxx/thread.cpp index 1fd8bb04..338a8a24 100644 --- a/system/lib/libcxx/thread.cpp +++ b/system/lib/libcxx/thread.cpp @@ -14,9 +14,9 @@ #include "limits" #include <sys/types.h> #if !defined(_WIN32) -#if !defined(__sun__) && !defined(__linux__) +#if !defined(__sun__) && !defined(__linux__) && !defined(_AIX) #include <sys/sysctl.h> -#endif // !__sun__ && !__linux__ +#endif // !__sun__ && !__linux__ && !_AIX #include <unistd.h> #endif // !_WIN32 @@ -89,7 +89,11 @@ thread::hardware_concurrency() _NOEXCEPT #else // defined(CTL_HW) && defined(HW_NCPU) // TODO: grovel through /proc or check cpuid on x86 and similar // instructions on other architectures. -#warning hardware_concurrency not yet implemented +# if defined(_MSC_VER) && ! defined(__clang__) + _LIBCPP_WARNING("hardware_concurrency not yet implemented") +# else +# warning hardware_concurrency not yet implemented +# endif return 0; // Means not computable [thread.thread.static] #endif // defined(CTL_HW) && defined(HW_NCPU) } diff --git a/system/lib/libcxx/typeinfo.cpp b/system/lib/libcxx/typeinfo.cpp index 60828944..b4281209 100644 --- a/system/lib/libcxx/typeinfo.cpp +++ b/system/lib/libcxx/typeinfo.cpp @@ -20,12 +20,18 @@ #include "typeinfo" -#if !(defined(_LIBCPPABI_VERSION) || defined(LIBCXXRT)) +#if !defined(LIBCXXRT) && !defined(_LIBCPPABI_VERSION) std::bad_cast::bad_cast() _NOEXCEPT { } +std::bad_typeid::bad_typeid() _NOEXCEPT +{ +} + +#ifndef __GLIBCXX__ + std::bad_cast::~bad_cast() _NOEXCEPT { } @@ -36,10 +42,6 @@ std::bad_cast::what() const _NOEXCEPT return "std::bad_cast"; } -std::bad_typeid::bad_typeid() _NOEXCEPT -{ -} - std::bad_typeid::~bad_typeid() _NOEXCEPT { } @@ -67,4 +69,5 @@ std::bad_typeid::what() const _NOEXCEPT } #endif -#endif // _LIBCPPABI_VERSION +#endif // !__GLIBCXX__ +#endif // !LIBCXXRT && !_LIBCPPABI_VERSION diff --git a/system/lib/libcxx/valarray.cpp b/system/lib/libcxx/valarray.cpp index 2d8db52a..e4c9ed02 100644 --- a/system/lib/libcxx/valarray.cpp +++ b/system/lib/libcxx/valarray.cpp @@ -7,6 +7,8 @@ // //===----------------------------------------------------------------------===// +#define _LIBCPP_EXTERN_TEMPLATE(...) extern template __VA_ARGS__; + #include "valarray" _LIBCPP_BEGIN_NAMESPACE_STD |