/**                                                                           */
/* file: re.c                                                                 */
/* date: 22-Jul-26                                                            */
/* auth: bagel                                                                */
/* desc: This is an implementation of regular expressions (regex) based on    */
/*       tiny-regex-c [1]; which was inspired by an implementation found in   */
/*       the book 'Beautiful Code' [2]. Unlike tiny-regex-c, dynamic memory   */
/*       allocation is used to support compiling multiple regular expressions */
/*       at once.                                                             */
/*                                                                           **/

/*----------------------------------------------------------------------------*/
/* Function and Type Declarations                                             */
/*----------------------------------------------------------------------------*/
typedef enum {
	re_Unused=0,
	re_Char,
	re_Class,
	re_InvClass,
	re_Group,
	re_Begin,
	re_End,
	re_Dot,
	re_Star,
	re_Plus,
	re_QuestionMark,
} re_type_t;

typedef struct re_t {
	re_type_t       type   ; /* CHAR, STAR, etc.                    */
	union {
		unsigned char ch     ; /* the character itsself                */
		unsigned char *class ; /* or a pointer to characters in class  */
		re_t          *group ;
	};
} re_t;

/*----------------------------------------------------------------------------*/
/* Compilation                                                                */
/*----------------------------------------------------------------------------*/
/* Since the same regular expressions are often used repeatedly in a single   */
/* run of a program, precompling the regular expression patterns can save on  */
/* overall execution time.                                                    */
/*                                                                            */
/*                                                                            */
bool _re_comp_class(re_t *re, const char *pater, int *i, int *j);
bool _re_comp_group(re_t *re, const char *pater, int *i, int *j);

re_t *re_comp( const char *pattern, bool group ) 
{
	static re_t _re[1024];

	int i, j;
	re_t *re;

Compile: /* use the static _re to compile the pattern */
	i = 0; j = 0;

	while ( pattern[i] ) {
		switch ( pattern[i] ) {
		case '\\': { i += 1; j -= 1;                                ; } break;
		case '^' : { _re[j].type = re_Begin                         ; } break;
		case '$' : { _re[j].type = re_End                           ; } break;
		case '.' : { _re[j].type = re_Dot                           ; } break;
		case '*' : { _re[j].type = re_Star                          ; } break;
		case '+' : { _re[j].type = re_Plus                          ; } break;
		case '?' : { _re[j].type = re_QuestionMark                  ; } break;
		case '[' : { if ( _re_comp_class(_re, pattern, &i, &j) ) {
		             	goto Cancel                                   ;                          
						 		 }                                              ; } break;
		case '(' : { if ( _re_comp_group(_re, pattern, &i, &j) ) {
		             	goto Cancel                                   ;                          
						 		 }                                              ; } break;
		case '|' :
		case ')' : { if ( group ) { goto Complete; }                ; } break;
		default  : { _re[j].type = re_Character                     ;
		             _re[j].ch   = pattern[i]                       ; } break;
		}

		i += 1; j += 1;
	}

Complete: /* allocate heap memory and copy compiled re into it*/
	re = malloc(sizeof( re_t ) * j);
	if ( nullptr == re ) return nullptr;

	for ( i = 0; i < j; i++ ) re[i] = _re[i];
	re[j].type = Unused;

	return re;

Cancel: /* free any possible heap allocations on error */
	return nullptr;
}

bool _re_comp_class(re_t *_re, const char *pattern, int *i, int *j) 
{
	static char _class[1024];
	
	int  k      ;
	char *class ;

Compile:
	/* determine whether the character class is inverted (e.g. [^abc]) */
	if ( '^' == pattern[(*i) + 1] ) { _re[(*j)].type = re_InvClass; (*i) += 1 ; } 
	else                            {	_re[(*j)].type = re_Class               ; }

	(*i) += 1; k = 0;
	while ( pattern[(*i)] ) {
		switch ( pattern[(*i)] ) {
		case '\\': { (*i) += 1; k -= 1;        ; } break ;
		case ']' : { goto Complete             ; } break ;
		default  : { _class[k] = pattern[(*i)] ; } break ;
		}

		(*i) += 1; k += 1;
	}

	if ( ! pattern[(*i)] ) goto Cancel; 
	
Complete: /* allocate class and copy */
	class = malloc(sizeof(char) * k);
	if ( nullptr == re ) return false;

	memcpy(class, _class, k - 1);
	class[k] = '\0';

	_re[(*j)].class = class;

	return true;

Cancel:
	return false;
}

bool _re_comp_group(re_t *re, const char *pattern, int *i, int *j)
{
	static re_t *_group[1024];
	static char *_pattern[1024];

	int k, l;

	k = 0; l = 0;
	while ( pattern[(*i)] && ']' != pattern[(*i)] ) {
		switch ( pattern[(*i)] ) {
		case '\\': { (*i) += 1; k -= 1                     ; } break ;
		case ')' :
		case '|' : { pattern[k] = '\0'                     ; 
		             re[(*j)].group[l] = re_comp(_pattern) ; 
								 (*j) += 1; l += 1                     ; } break ;
		default  : { _pattern[k] = pattern[(*i)]           ; } break ;
		}

		(*i) += 1; k += 1;
	}

Finish:
	return true

Error:
	return false
}

void re_free(re_t *re)
{
	int i;

	i = 0;
	while ( re[i] ) {
		if ( re_Class == re[i].type ) free(re[i].class);
		i += 1;
	}

	free(re);
};

/* Executing */
int re_exec(re_t *pattern, const char *text, int *mlen)
{
	int i;

	if ( nullptr == pattern    ) return -1;
	if ( Begin == pattern.type ) return re_exec(&pattern[1], text, mlen) ? 0 : -1;

	*mlen = 0;

	i = -1; 
	do {
		i += 1;

		if ( _match_pattern(pattern, text, mlen) ) {
			if ( '\0' != text[0] ) return -1 ;
			else                   return i  ;
		}
	} while ( '\0' != *text++ )

	return -1;
}