tre-match-backtrack.c [plain text]
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif
#undef TRE_USE_ALLOCA
#ifdef TRE_USE_ALLOCA
#ifndef __GNUC__
# if HAVE_ALLOCA_H
# include <alloca.h>
# else
# ifdef _AIX
#pragma alloca
# else
# ifndef alloca
char *alloca ();
# endif
# endif
# endif
#endif
#endif
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#ifdef HAVE_WCHAR_H
#include <wchar.h>
#endif
#ifdef HAVE_WCTYPE_H
#include <wctype.h>
#endif
#ifndef TRE_WCHAR
#include <ctype.h>
#endif
#ifdef HAVE_MALLOC_H
#include <malloc.h>
#endif
#include "tre-internal.h"
#include "tre-mem.h"
#include "tre-match-utils.h"
#include "tre.h"
#include "xmalloc.h"
typedef struct {
int pos;
unsigned int pos_add_next;
const char *str_byte;
#ifdef TRE_WCHAR
const wchar_t *str_wide;
#endif
tre_tnfa_transition_t *state;
int state_id;
int next_c;
tre_tag_t *tags;
#ifdef TRE_MBSTATE
mbstate_t mbstate;
#endif
} 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_WCHAR
#define BT_STACK_WIDE_IN(_str_wide) stack->item.str_wide = (_str_wide)
#define BT_STACK_WIDE_OUT (str_wide) = stack->item.str_wide
#else
#define BT_STACK_WIDE_IN(_str_wide)
#define BT_STACK_WIDE_OUT
#endif
#ifdef TRE_MBSTATE
#define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate)
#define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate
#else
#define BT_STACK_MBSTATE_IN
#define BT_STACK_MBSTATE_OUT
#endif
#ifdef TRE_USE_ALLOCA
#define tre_bt_mem_new tre_mem_newa
#define tre_bt_mem_alloc tre_mem_alloca
#define tre_bt_mem_destroy(obj) do { } while (0)
#else
#define tre_bt_mem_new tre_mem_new
#define tre_bt_mem_alloc tre_mem_alloc
#define tre_bt_mem_destroy tre_mem_destroy
#endif
#define BT_STACK_PUSH(_pos, _pos_add_next, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \
do \
{ \
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, \
num_tags * sizeof(*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.pos_add_next = (_pos_add_next); \
stack->item.str_byte = (_str_byte); \
BT_STACK_WIDE_IN(_str_wide); \
stack->item.state = (_state); \
stack->item.state_id = (_state_id); \
stack->item.next_c = (_next_c); \
memcpy(stack->item.tags, (_tags), num_tags * sizeof(*(_tags))); \
BT_STACK_MBSTATE_IN; \
} \
while (0)
#ifdef TRE_STR_USER
#define BT_STACK_POP() \
do \
{ \
assert(stack->prev); \
pos = stack->item.pos; \
pos_add_next = stack->item.pos_add_next; \
if (type == STR_USER) \
str_source->rewind(pos + pos_add_next, str_source->context); \
str_byte = stack->item.str_byte; \
BT_STACK_WIDE_OUT; \
state = stack->item.state; \
next_c = stack->item.next_c; \
memcpy(tags, stack->item.tags, num_tags * sizeof(*tags)); \
BT_STACK_MBSTATE_OUT; \
stack = stack->prev; \
} \
while (0)
#else
#define BT_STACK_POP() \
do \
{ \
assert(stack->prev); \
pos = stack->item.pos; \
pos_add_next = stack->item.pos_add_next; \
str_byte = stack->item.str_byte; \
BT_STACK_WIDE_OUT; \
state = stack->item.state; \
next_c = stack->item.next_c; \
memcpy(tags, stack->item.tags, num_tags * sizeof(*tags)); \
BT_STACK_MBSTATE_OUT; \
stack = stack->prev; \
} \
while (0)
#endif
#undef MIN
#define MIN(a, b) ((a) <= (b) ? (a) : (b))
reg_errcode_t
tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string,
int len, tre_str_type_t type, tre_tag_t *match_tags,
int eflags, int *match_end_ofs)
{
tre_char_t prev_c = 0, next_c = 0;
const char *str_byte = string;
int pos = 0;
unsigned int pos_add_next = 1;
#ifdef TRE_WCHAR
const wchar_t *str_wide = string;
#ifdef TRE_MBSTATE
mbstate_t mbstate;
#endif
#endif
int reg_notbol = eflags & REG_NOTBOL;
int reg_noteol = eflags & REG_NOTEOL;
int reg_newline = tnfa->cflags & REG_NEWLINE;
#ifdef TRE_STR_USER
int str_user_end = 0;
#endif
int i;
int next_c_start;
const char *str_byte_start;
int pos_start = -1;
#ifdef TRE_WCHAR
const wchar_t *str_wide_start;
#endif
#ifdef TRE_MBSTATE
mbstate_t mbstate_start;
#endif
int match_eo = -1;
int *next_tags;
tre_tag_t *tags = NULL;
tre_tnfa_transition_t *state;
int *states_seen = NULL;
tre_mem_t mem = tre_bt_mem_new();
tre_backtrack_t stack;
tre_tnfa_transition_t *trans_i;
regmatch_t *pmatch = NULL;
reg_errcode_t ret;
int num_tags = tnfa->num_tags;
int touch = 1;
char *buf = NULL;
int tbytes;
#ifdef TRE_MBSTATE
memset(&mbstate, '\0', sizeof(mbstate));
#endif
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;
DPRINT(("tnfa_execute_backtrack, input type %d\n", type));
DPRINT(("len = %d\n", len));
{
int pbytes, sbytes, total_bytes;
char *tmp_buf;
tbytes = sizeof(*tags) * num_tags;
pbytes = sizeof(*pmatch) * tnfa->num_submatches;
sbytes = sizeof(*states_seen) * tnfa->num_states;
total_bytes =
(sizeof(long) - 1) * 2
+ tbytes + pbytes + sbytes;
DPRINT(("tre_tnfa_run_backtrack, allocate %d bytes\n", total_bytes));
#ifdef TRE_USE_ALLOCA
buf = alloca(total_bytes);
#else
buf = xmalloc((unsigned)total_bytes);
#endif
if (buf == NULL)
return REG_ESPACE;
tags = (void *)buf;
tmp_buf = buf + tbytes;
tmp_buf += ALIGN(tmp_buf, long);
pmatch = (void *)tmp_buf;
tmp_buf += pbytes;
tmp_buf += ALIGN(tmp_buf, long);
states_seen = (void *)tmp_buf;
}
retry:
{
memset(tags, 0, num_tags * sizeof(*tags));
if (match_tags)
memset(match_tags, 0, num_tags * sizeof(*match_tags));
for (i = 0; i < tnfa->num_states; i++)
states_seen[i] = 0;
}
state = NULL;
pos = pos_start;
#ifdef TRE_STR_USER
if (type == STR_USER)
str_source->rewind(pos + pos_add_next, str_source->context);
#endif
GET_NEXT_WCHAR();
pos_start = pos;
next_c_start = next_c;
str_byte_start = str_byte;
#ifdef TRE_WCHAR
str_wide_start = str_wide;
#endif
#ifdef TRE_MBSTATE
mbstate_start = mbstate;
#endif
next_tags = NULL;
for (trans_i = tnfa->initial; trans_i->state; trans_i++)
{
DPRINT(("> init %p, prev_c %lc\n", trans_i->state, (tre_cint_t)prev_c));
if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions))
{
DPRINT(("assert failed\n"));
continue;
}
if (state == NULL)
{
state = trans_i->state;
next_tags = trans_i->tags;
}
else
{
DPRINT(("saving state %d for backtracking\n", trans_i->state_id));
BT_STACK_PUSH(pos, pos_add_next, str_byte, str_wide, trans_i->state,
trans_i->state_id, next_c, tags, mbstate);
{
int *tmp = trans_i->tags;
if (tmp)
{
while (*tmp >= 0)
tre_tag_set(stack->item.tags, *tmp++, pos, touch);
touch++;
}
}
}
}
if (next_tags)
{
for (; *next_tags >= 0; next_tags++)
tre_tag_set(tags, *next_tags, pos, touch);
touch++;
}
DPRINT(("entering match loop, pos %d, str_byte %p\n", pos, str_byte));
DPRINT(("pos:chr/code | state and tags\n"));
DPRINT(("-------------+------------------------------------------------\n"));
if (state == NULL)
goto backtrack;
while (1)
{
tre_tnfa_transition_t *next_state;
int empty_br_match;
DPRINT(("start loop\n"));
if (match_eo >= 0 && tnfa->num_minimals)
{
int skip = 0;
#ifdef TRE_DEBUG
DPRINT(("Checking minimal conditions: match_eo=%d match_tags=",
match_eo));
tre_print_tags(match_tags, tnfa->num_tags);
DPRINT(("\n"));
#endif
for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2)
{
int end = tnfa->minimal_tags[i];
int start = tnfa->minimal_tags[i + 1];
DPRINT((" Minimal start %d, end %d\n", start, end));
if (tre_minimal_tag_order(start, end, match_tags, tags) > 0)
{
skip = 1;
break;
}
}
if (!skip)
{
#ifdef TRE_DEBUG
DPRINT((" Keeping tags="));
tre_print_tags(tags, tnfa->num_tags);
DPRINT(("\n"));
#endif
}
else
{
#ifdef TRE_DEBUG
DPRINT((" Throwing out tags="));
tre_print_tags(tags, tnfa->num_tags);
DPRINT(("\n"));
#endif
goto backtrack;
}
}
if (state == tnfa->final)
{
DPRINT((" match found, match_eo=%d pos=%d\n", match_eo, pos));
if (match_eo >= 0 && tnfa->num_minimals)
{
int compare = 0;
#ifdef TRE_DEBUG
DPRINT(("Checking minimal conditions: match_eo=%d "
"match_tags=", match_eo));
tre_print_tags(match_tags, tnfa->num_tags);
DPRINT(("\n"));
#endif
for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2)
{
int end = tnfa->minimal_tags[i];
int start = tnfa->minimal_tags[i + 1];
DPRINT((" Minimal start %d, end %d\n", start, end));
if ((compare = tre_minimal_tag_order(start, end,
match_tags, tags)) != 0)
break;
}
if (compare > 0)
{
#ifdef TRE_DEBUG
DPRINT((" Throwing out new match, tags="));
tre_print_tags(tags, tnfa->num_tags);
DPRINT(("\n"));
#endif
goto backtrack;
}
else if (compare < 0)
{
#ifdef TRE_DEBUG
DPRINT((" Throwing out old match, tags="));
tre_print_tags(match_tags, tnfa->num_tags);
DPRINT(("\n"));
#endif
match_eo = -1;
}
}
if (match_eo < pos
|| (match_eo == pos
&& match_tags
&& tre_tag_order(tnfa->num_tags, tnfa->tag_directions,
tags, match_tags)))
{
#ifdef TRE_DEBUG
DPRINT((" win previous tags="));
tre_print_tags(tags, tnfa->num_tags);
DPRINT(("\n"));
#endif
match_eo = pos;
if (match_tags)
memcpy(match_tags, tags, num_tags * sizeof(*tags));
}
goto backtrack;
}
#ifdef TRE_DEBUG
DPRINT(("%3d:%2lc/%05d | %p ", pos, (tre_cint_t)next_c, (int)next_c,
state));
tre_print_tags(tags, tnfa->num_tags);
DPRINT(("\n"));
#endif
empty_br_match = 0;
trans_i = state;
if (trans_i->state && trans_i->assertions & ASSERT_BACKREF)
{
int so, eo, bt = trans_i->u.backref;
int bt_len;
int result;
DPRINT((" should match back reference %d\n", bt));
ret = tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB,
tnfa, tags, pos);
if (ret != REG_OK) goto error_exit;
so = pmatch[bt].rm_so;
eo = pmatch[bt].rm_eo;
bt_len = eo - so;
#ifdef TRE_DEBUG
{
int slen;
if (len < 0)
slen = bt_len;
else
slen = MIN(bt_len, len - pos);
if (type == STR_BYTE)
{
DPRINT((" substring (len %d) is [%d, %d]: '%.*s'\n",
bt_len, so, eo, bt_len, (char*)string + so));
DPRINT((" current string is '%.*s'\n", slen, str_byte - 1));
}
#ifdef TRE_WCHAR
else if (type == STR_WIDE)
{
DPRINT((" substring (len %d) is [%d, %d]: '%.*" STRF "'\n",
bt_len, so, eo, bt_len, (wchar_t*)string + so));
DPRINT((" current string is '%.*" STRF "'\n",
slen, str_wide - 1));
}
#endif
}
#endif
if (so < 0)
{
result = 1;
}
else if (len < 0)
{
#ifdef TRE_STR_USER
if (type == STR_USER)
result = str_source->compare((unsigned)so, (unsigned)pos,
(unsigned)bt_len,
str_source->context);
else
#endif
#ifdef TRE_WCHAR
if (type == STR_WIDE)
result = wcsncmp((const wchar_t*)string + so, str_wide - 1,
(size_t)bt_len);
else
#endif
result = strncmp((const char*)string + so, str_byte - 1,
(size_t)bt_len);
}
else if (len - pos < bt_len)
result = 1;
#ifdef TRE_WCHAR
else if (type == STR_WIDE)
result = wmemcmp((const wchar_t*)string + so, str_wide - 1,
(size_t)bt_len);
#endif
else
result = memcmp((const char*)string + so, str_byte - 1,
(size_t)bt_len);
if (result == 0)
{
if (bt_len == 0)
empty_br_match = 1;
if (empty_br_match && states_seen[trans_i->state_id])
{
DPRINT((" avoid loop\n"));
goto backtrack;
}
states_seen[trans_i->state_id] = empty_br_match;
DPRINT((" back reference matched\n"));
str_byte += bt_len - 1;
#ifdef TRE_WCHAR
str_wide += bt_len - 1;
#endif
pos += bt_len - 1;
GET_NEXT_WCHAR();
DPRINT((" pos now %d\n", pos));
}
else
{
DPRINT((" back reference did not match\n"));
goto backtrack;
}
}
else
{
if (len < 0)
{
#ifdef TRE_STR_USER
if (type == STR_USER)
{
if (str_user_end)
goto backtrack;
}
else
#endif
if (next_c == L'\0')
goto backtrack;
}
else
{
if (pos >= len)
goto backtrack;
}
GET_NEXT_WCHAR();
}
next_state = NULL;
for (trans_i = state; trans_i->state; trans_i++)
{
DPRINT((" transition %d-%d (%c-%c) %d to %d\n",
trans_i->code_min, trans_i->code_max,
trans_i->code_min, trans_i->code_max,
trans_i->assertions, trans_i->state_id));
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)))
{
DPRINT((" assertion failed\n"));
continue;
}
if (next_state == NULL)
{
DPRINT((" Next state is %d\n", trans_i->state_id));
next_state = trans_i->state;
next_tags = trans_i->tags;
}
else
{
DPRINT((" saving state %d for backtracking\n",
trans_i->state_id));
BT_STACK_PUSH(pos, pos_add_next, str_byte, str_wide,
trans_i->state, trans_i->state_id, next_c,
tags, mbstate);
{
int *tmp;
for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++)
tre_tag_set(stack->item.tags, *tmp, pos, touch);
touch++;
}
#if 0
break;
#endif
}
}
}
if (next_state != NULL)
{
state = next_state;
if (next_tags)
{
while (*next_tags >= 0)
tre_tag_set(tags, *next_tags++, pos, touch);
touch++;
}
}
else
{
backtrack:
if (stack->prev)
{
DPRINT((" backtracking\n"));
if (stack->item.state->assertions & ASSERT_BACKREF)
{
DPRINT((" states_seen[%d] = 0\n",
stack->item.state_id));
states_seen[stack->item.state_id] = 0;
}
BT_STACK_POP();
}
else if (match_eo < 0)
{
if (pos == pos_start)
{
if (len < 0)
{
if (next_c == L'\0')
{
DPRINT(("end of string.\n"));
break;
}
}
else
{
if (pos >= len)
{
DPRINT(("end of string.\n"));
break;
}
}
}
DPRINT(("restarting from next start position\n"));
next_c = next_c_start;
#ifdef TRE_MBSTATE
mbstate = mbstate_start;
#endif
str_byte = str_byte_start;
#ifdef TRE_WCHAR
str_wide = str_wide_start;
#endif
goto retry;
}
else
{
DPRINT(("finished\n"));
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 (buf)
xfree(buf);
#endif
return ret;
}