/* 

 * Motif

 *

 * Copyright (c) 1987-2012, The Open Group. All rights reserved.

 *

 * These libraries and programs are free software; you can

 * redistribute them and/or modify them under the terms of the GNU

 * Lesser General Public License as published by the Free Software

 * Foundation; either version 2 of the License, or (at your option)

 * any later version.

 *

 * These libraries and programs are distributed in the hope that

 * they will be useful, but WITHOUT ANY WARRANTY; without even the

 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR

 * PURPOSE. See the GNU Lesser General Public License for more

 * details.

 *

 * You should have received a copy of the GNU Lesser General Public

 * License along with these librararies and programs; if not, write

 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth

 * Floor, Boston, MA 02110-1301 USA

*/

#include <Xm/PictureP.h>

static XmPictureNode* _XiGetNewNode(XmPictureRec*);

static void _XmPictureParseNode(XmPictureRec*, char**, XmPictureNode**,

				XmPictureNode**, Boolean);

static XmPictureTransition* _XiGetNewTransition(XmTransType,

						XmPictureNode*,

						XmPictureNode*);

static void _XmPictureSetState(unsigned char*, int);

static char _XmPictureGetState(unsigned char*, int);

static void _XmPictureFollowTransitions(XmPictureStateRec*, char, XmPictureNode*);

static XmPictureNode *_XmPictureCopySubGraph(XmPictureRec*, int,

					     XmPictureNode*, XmPictureNode*);

static void _XmPictureTagNodes(XmPictureRec*, XmPictureNode**, int);

static void _XmPictureFillTraverse(XmPictureRec*, int, XmAutoFill*);

/*

 * Parses the given string into an XmPicture object.  Returns NULL on a

 * mal-formed picture

 */

XmPicture

XmParsePicture(char *input)

{

    XmPictureRec *picture;

    XmPictureNode *root_node;

    XmPictureNode *end_node;

    picture = XtNew(XmPictureRec);

    picture->source = XtNewString(input);

    picture->num_nodes = 0;

    picture->nodes_alloced = NODE_START_COUNT;

    picture->nodes = (XmPictureNode**)

	             XtMalloc(NODE_START_COUNT * sizeof(XmPictureNode*));

    _XmPictureParseNode(picture, &input, &root_node, &end_node, False);

    picture->start_node = root_node->index;

    picture->final_node = end_node->index;

    return picture;

}

/*

 * Creates a new XmPictureState.  The memory allocated must be freed by the

 * user with XtFree()

 */

XmPictureState

XmGetNewPictureState(XmPicture picture)

{

    int i;

    XmPictureStateRec *state;

    state = XtNew(XmPictureStateRec);

    state->statesize = 1 + (picture->num_nodes * sizeof(char) / 8);

    state->picture = picture;

    state->state = (unsigned char*) XtMalloc(state->statesize);

    state->newstate = (unsigned char*) XtMalloc(state->statesize);

    for(i=0; i<state->statesize; i++) {

	state->state[i] = 0;

	state->newstate[i] = 0;

    }

    _XmPictureSetState(state->state, picture->start_node);

    /*

     * BAD BAD BAD HACK

     * This just allocates a static 1024 character array.  While this will

     * be fine for the DataField, because only one state per widget will

     * be allocated and because the strings will never get that long,

     * this makes this library useless for generalized database stuff.

     * DON'T attempt to make lots of these or use them for very long

     * regexps until I get this fixed -- Andy

     * Sigh, additionally, this is a security problem.  Feeding this

     * thing very long RE's and strings will therefore make the

     * program crash, which is not something our customers want

     */

    state->current_string = XtMalloc(1024 * sizeof(char));

    state->current_string[0] = '\0';

    state->append = state->current_string;

    return state;

}

/*

 * Processes a single character.  Returns a pointer to the current

 * value of the string (which may have been auto-filled, if

 * do_auto_fill is specified).  If the current state vector contains

 * the final state, it places True in is_finished, otherwise False.

 */

char*

XmPictureProcessCharacter(XmPictureState state, char in, Boolean *is_finished)

{

    int i;

    char status;

    unsigned char *temp;

    char *save_start;

    /*

     * Reset the current-processing info

     */

    state->current = '\0';

    state->upcase  = False;

    for(i=0; i<state->statesize; i++)

	state->newstate[i] = 0;

    /*

     * For each node in the state set, try to follow all transitions

     * (recursing on NullTransitions of course)

     */    

    for(i=0; i<state->picture->num_nodes; i++) {

	if(_XmPictureGetState(state->state, i)) {

	    _XmPictureFollowTransitions(state, in, state->picture->nodes[i]);

	}

    }

    /*

     * Swap the states

     */

    temp = state->state;

    state->state = state->newstate;

    state->newstate = temp;

    /*

     * Append whatever we accepted (which might have been upcased)

     */

    save_start = state->append;

    if(state->current) {

	*state->append = state->current;

	state->append++;

	*state->append = '\0';

    }

    /*

     * If we didn't find _any_ transitions, return NULL

     */

    for(i=0; i<state->statesize; i++)

	if(state->state[i] != 0)

	    break;

    if(i == state->statesize) {

	*is_finished = True;

	return NULL;

    }

    /*

     * If our set contains the final state, set is_finished to true

     */

    status = _XmPictureGetState(state->state, state->picture->final_node);

    if(status) *is_finished = True;

    else *is_finished = False;

    return save_start;

}

void

XmPictureDelete(XmPicture p)

{

    int i;

    XmPictureTransition *trans, *delete_me;

    /*

     * First walk all the nodes, deleting the transitions then the

     * nodes themselves

     */

    for(i=0; i<p->num_nodes; i++) {

	trans = p->nodes[i]->transitions;

	while(trans) {

	    delete_me = trans;

	    trans = trans->next;

	    XtFree((char*)delete_me);

	}

	XtFree((char*)p->nodes[i]);

    }

    /*

     * Now the node table and finally the picture itself

     */

    XtFree((char*)p->nodes);

    XtFree(p->source);

    XtFree((char*)p);

}

void

XmPictureDeleteState(XmPictureState s)

{

    XtFree(s->current_string);

    XtFree((char*)s->state);

    XtFree((char*)s->newstate);

    XtFree((char*)s);

}

char*

XmPictureGetCurrentString(XmPictureState s)

{

    return s->current_string;

}

char*

XmPictureDoAutoFill(XmPictureState state)

{

    XmAutoFill fill;

    int i;

    Boolean finished = False;

    while(1) {

	fill.reject = False;

	fill.c      = '\0';

	fill.digit  = False;

	fill.upcase = False;

	fill.letter = False;

	fill.hexdigit = False;

	fill.octaldigit = False;

	for(i=0; i<state->picture->num_nodes; i++)

	    if(_XmPictureGetState(state->state, i))

		_XmPictureFillTraverse(state->picture, i, &fill;;

	if(fill.c == '\0')

	    fill.reject = True;

	if(fill.digit && (isdigit(fill.c) == 0))

	    fill.reject = True;

	if(fill.hexdigit && (isxdigit(fill.c) == 0))

	    fill.reject = True;

	if(fill.octaldigit && (fill.c < '0' || fill.c > '7'))

	    fill.reject = True;

	if(fill.letter && (isalpha(fill.c) == 0))

	    fill.reject = True;

	if(fill.upcase && islower(fill.c))

	    fill.reject = True;

	if(fill.reject) return state->current_string;

	XmPictureProcessCharacter(state, fill.c, &finished);

	if(finished) return state->current_string;

    }

}

/*

 * Parses a single "node" of the regular expression.  If returnNOW is true,

 * this means only the very first complete RE encountered (a hack, to allow

 * for the weird closure precedence:  *ab should parse like {*a}b and not

 * *{ab}), otherwise it reads until the end of the RE, be it a close brace

 * or EOS.

 */

static void

_XmPictureParseNode(XmPictureRec *picture, char **in_string,

		    XmPictureNode **start_return,

		    XmPictureNode **end_return,

		    Boolean returnNOW)

{

    XmPictureNode *start_node;

    XmPictureNode *current_node;

    XmPictureNode *start_node_2;

    XmPictureNode *current_node_2;

    XmPictureNode *newnode;

    int node_idx;

    XmPictureTransition *newtrans;

    char inc;

    int count;

    char *endcount;

    start_node = _XiGetNewNode(picture);

    node_idx = start_node->index;

    current_node = start_node;

    while((inc = *((*in_string)++))) {

	switch(inc) {

	    /*

	     * These are the "normal" single-character tokens that

	     * behave (more or less) like literals in the state

	     * machine.

	     */

	case NUMDIGIT:

	    newnode = _XiGetNewNode(picture);

	    newtrans = _XiGetNewTransition(NumericDigit,

					   current_node, newnode);

	    current_node = newnode;

	    break;

	case HEXDIGIT:

	    newnode = _XiGetNewNode(picture);

	    newtrans = _XiGetNewTransition(HexDigit,

					   current_node, newnode);

	    current_node = newnode;

	    break;

	case OCTALDIGIT:

	    newnode = _XiGetNewNode(picture);

	    newtrans = _XiGetNewTransition(OctalDigit,

					   current_node, newnode);

	    current_node = newnode;

	    break;

	case NONCASELETTER:

	    newnode = _XiGetNewNode(picture);

	    newtrans = _XiGetNewTransition(AnyLetter,

					   current_node, newnode);

	    current_node = newnode;

	    break;

	case UPCASELETTER:

	    newnode = _XiGetNewNode(picture);

	    newtrans = _XiGetNewTransition(UpCaseLetter,

					   current_node, newnode);

	    current_node = newnode;

	    break;

	case NONCASECHAR:

	    newnode = _XiGetNewNode(picture);

	    newtrans = _XiGetNewTransition(AnyCharacter,

					   current_node, newnode);

	    current_node = newnode;

	    break;

	case UPCASECHAR:

	    newnode = _XiGetNewNode(picture);

	    newtrans = _XiGetNewTransition(UpCaseCharacter,

					   current_node, newnode);

	    current_node = newnode;

	    break;

	    /*

	     * The weird stuff.

	     */

	    /*

	     * Read a numeric specifier, if it exists, then read the

	     * next _single_ R.E. (i.e., not a string of concatenated

	     * ones!); Add a transition from the current end state to the

	     * end (!) state of the new closure states, and a transition

	     * from that end to it's beginning.

	     */

	case CLOSURE: /* CR03602 picture should formatted to *nx;

			n is no. of time repeat; x is the specified

			character going to be display */

	    count = strtol(*in_string, &endcount, 0);

	    if(count)

		*in_string = endcount;		

	    _XmPictureParseNode(picture, in_string,

				&start_node_2, &current_node_2,

				True);

	    if(count) {

		newtrans = _XiGetNewTransition(NullTransition,

					       current_node, start_node_2);

		current_node = _XmPictureCopySubGraph(picture, count-1,

						      start_node_2,

						      current_node_2);

	    } else {

		newtrans = _XiGetNewTransition(NullTransition,

					       current_node_2, start_node_2);

		newtrans = _XiGetNewTransition(NullTransition,

					       current_node, current_node_2);

		current_node = current_node_2;

	    }

	    break;

	    /*

	     * Read the next (NOT singleton, this time) R.E.; create a _new_

	     * initial state which has null-transitions to both the

	     * current and new R.E.'s, and a new final state to which

	     * both trails lead.

	     */

	case ALTERNATIVE: /* CR03656 CR03359 a major overhaul */

	    _XmPictureParseNode(picture, in_string,

				&start_node_2, &current_node_2,

				True);

            newtrans = _XiGetNewTransition(NullTransition, current_node,

					   current_node_2);

            if (current_node->index)

              picture->nodes[current_node->index - 1]->transitions->next =

		start_node_2->transitions;

            current_node = current_node_2;

	    break;

	    /*

	     * This actually is a special case of ALTERNATIVE.  The

	     * stuff inside the brackets becomes one chain, and a

	     * null-transition becomes the second.  Just read the

	     * (NON-singleton) RE until the close-bracket.

	     */

	case LBRACKET:

	    _XmPictureParseNode(picture, in_string,

				&start_node_2, &current_node_2,

				False);

	    newtrans = _XiGetNewTransition(NullTransition,

					   current_node, current_node_2);

	    newtrans = _XiGetNewTransition(NullTransition,

					   current_node, start_node_2);

	    current_node = current_node_2;

	    break;

	    /*

	     * The easiest special case to handle.  Just read a

	     * non-singleton R.E. until the close-brace and stick it

	     * in as a "literal".

	     */

	case LBRACE:

	    _XmPictureParseNode(picture, in_string,

				&start_node_2, &current_node_2,

				False);

	    newtrans = _XiGetNewTransition(NullTransition,

					   current_node, start_node_2);

	    current_node = current_node_2;

	    break;

	    /*

	     * Deal with both end-of-subexpression tokens in the same

	     * way.  This will accept stuff like {...] and [...}, but that's

	     * probably OK, since it will only parse stuff incorrectly

	     * for things like: [...{...]...} which aren't legal

	     * anyway.  I.E., we accept a superset of legal pictures,

	     * but parse all legal pictures correctly.

	     */

	case RBRACE:

	case RBRACKET:

	    returnNOW = True;

	    break;

	    /*

	     * Special case handling for the ';' escape character.

	     * Make sure dumb users haven't escaped the end of the string

	     * then advance the pointer and fall through to the (default)

	     * handling for a literal.

	     */

	case ESCAPE:

	    inc = **in_string;

	    if(inc == '\0') break;

	    else (*in_string)++;

	    /*

	     * It's not a special character, so it must be a literal

	     */

	default:

	    newnode = _XiGetNewNode(picture);

	    newtrans = _XiGetNewTransition(LiteralCharacter,

					   current_node, newnode);

	    newtrans->c = inc;

	    current_node = newnode;

	    break;

	}

	/*

	 * Break out if we have to

	 */

	if(returnNOW == True) break;

    }

    *start_return = start_node;

    *end_return = current_node;

}

static XmPictureTransition*

_XiGetNewTransition(XmTransType type,

		    XmPictureNode *src, XmPictureNode *dest)

{

    XmPictureTransition *t = XtNew(XmPictureTransition);

    t->destination = dest->index;

    t->type = type;

    t->next = src->transitions;

    src->transitions = t;

    return t;

}

/*

 * Allocates a new state machine node

 */

static XmPictureNode*

_XiGetNewNode(XmPictureRec *picture)

{

    XmPictureNode *new_node;

    new_node = XtNew(XmPictureNode);

    new_node->transitions = NULL;

    new_node->index = picture->num_nodes++;

    /*

     * Handle growing the picture past it's boundary

     */

    if(picture->num_nodes > picture->nodes_alloced) {

	int newsize = picture->nodes_alloced * 2;

	picture->nodes = (XmPictureNode**)

	                 XtRealloc((char*)picture->nodes,

				   newsize * sizeof(XmPictureNode*));

	picture->nodes_alloced = newsize;

    }

    picture->nodes[new_node->index] = new_node;

    return new_node;

}

static void

_XmPictureSetState(unsigned char *v, int i)

{

    int base = i / 8;

    int offset = i % 8;

    v[base] |= 1 << offset;

}

/*

 * Do I need this at all?

 *

static void

_XmPictureClearState(char *v, int i)

{

    int base = i / 8;

    int offset = i % 8;

    v[base] &= ~(1 << offset);

}

*/

static char

_XmPictureGetState(unsigned char *v, int i)

{

    int base = i / 8;

    int offset = i % 8;

    int result = v[base] & (1 << offset);

    if(result) return 1;

    else return 0;

}

/*

 * The inc parameter gets set to '\0' if we are following a null

 * transition after already having read the character.

 */

static void

_XmPictureFollowTransitions(XmPictureStateRec *state, char inc,

			    XmPictureNode *node)

{

    XmPictureTransition *curr = node->transitions;

    char follow_c, changed_c;

    Boolean found = False;

    Boolean accepted = True;

    while(curr) {

	follow_c = '\0';

	changed_c = '\0';

	switch(curr->type) {

	case NullTransition:

	    follow_c = inc;

	    found = True;

	    if(inc != '\0')

		accepted = False;

	    break;

	case NumericDigit:

	    if(isdigit(inc)) {

		found = True;

	    }

	    break;

	case HexDigit:

	    if(isdigit(inc) ||

		(inc >= 'a' && inc <= 'f') ||

		(inc >= 'A' && inc <= 'F')) {

		found = True;

	    }

	    break;

	case OctalDigit:

	    if((inc >= '0') && (inc <= '7')) {

		found = True;

	    }

	    break;

	case AnyLetter:

	    if(isalpha(inc)) {

		found = True;

	    }

	    break;

	case UpCaseLetter:

	    if(isalpha(inc)) {

		changed_c = toupper(inc);

		found = True;

	    }

	    break;

	case AnyCharacter:

	    if(isalnum(inc)) {

		found = True;

	    }

	    break;

	case UpCaseCharacter:

	    if(isalnum(inc)) {

		changed_c = toupper(inc);

		found = True;

	    }

	    break;

	case LiteralCharacter:

	    if(inc == curr->c) {

		found = True;

	    }

	    break;

	}

	if(found) {

	    if(changed_c) {

		state->current = changed_c;

	    } else if(inc) {

		state->current = inc;

	    }

	    if(accepted)

		_XmPictureSetState(state->newstate, curr->destination);

	    _XmPictureFollowTransitions(state, follow_c,

					state->picture

					  ->nodes[curr->destination]);

	}

	found = False;

	curr = curr->next;

    }

}

/*

 * Recursively traverses a subgraph, tagging all indices in table with

 * a non-null value.

 */

static void

_XmPictureTagNodes(XmPictureRec *picture, XmPictureNode **table, int start)

{

    XmPictureTransition *trans = picture->nodes[start]->transitions;

    table[start] = (XmPictureNode*)0x1;

    while(trans) {

	_XmPictureTagNodes(picture, table, trans->destination);

	trans = trans->next;

    }

}

/*

 * Makes a string of n copies of the subgraph indicated, chaining them

 * end-to-end.  It returns the new end node for the multiplied

 * subgraph (the start node is the unchanged, of course)

 */

static XmPictureNode*

_XmPictureCopySubGraph(XmPictureRec *picture, int n,

		       XmPictureNode *start, XmPictureNode *end)

{

    XmPictureNode **table;

    XmPictureTransition *trans, *newtrans;

    int i, j, tablesize, end_index;

    /*

     * Bail if the user did a repeat count of 1

     */

    if(n < 1) return end;

    /*

     * First allocate a pointer array of the same size as the current

     * picture.  This will hold NULL for nodes not in the subgraph and

     * the XmPictureNode for the newest copy.

     */

    tablesize = picture->num_nodes;

    table = (XmPictureNode**)

	    XtMalloc(tablesize * sizeof(XmPictureNode*));

    for(i=0; i<picture->num_nodes; i++)

	table[i] = NULL;

    /*

     * Now recursively tag the ones in our subgraph with non-NULL

     * values

     */

    _XmPictureTagNodes(picture, table, start->index);

    /*

     * Now loop:  for each non-NULL, allocate a new node in its

     * place; then go through each transition from the _original_

     * nodes, and put equivalent ones in the new table's nodes.

     * Finally chain it to the end of the previous node.

     */

    end_index = end->index;

    for(i=0; i

	/* Allocate the new nodes */

	for(j=0; j

	    if(table[j]) table[j] = _XiGetNewNode(picture);

	/* Fill them in */

	for(j=0; j

	    if(table[j]) {

		trans = picture->nodes[j]->transitions;

		while(trans) {

		    /*

		     * Hack to make sure we don't follow transitions

                     * into the newly created nodes

		     */

		    if(trans->destination >= tablesize) {

			trans = trans->next;

			continue;

		    }

		    newtrans = _XiGetNewTransition(trans->type,

						   table[j],

						   table[trans->destination]);

		    newtrans->c = trans->c;

		    trans = trans->next;

		}

	    }

	}

	_XiGetNewTransition(NullTransition, end, table[start->index]);

	end = table[end_index];

    }

    XtFree((void*)table);

    return end;

}

static void

_XmPictureFillTraverse(XmPictureRec *picture, int start, XmAutoFill *fill)

{

    XmPictureTransition *trans = picture->nodes[start]->transitions;

    while(trans) {

	switch(trans->type) {

	case NullTransition:

	    _XmPictureFillTraverse(picture, trans->destination, fill);

	    break;

	case NumericDigit:

	    fill->digit = True;

	    break;

	case HexDigit:

	    fill->hexdigit = True;

	    break;

	case OctalDigit:

	    fill->octaldigit = True;

	    break;

	case AnyLetter:

	    fill->letter = True;

	    break;

	case UpCaseLetter:

	    fill->letter = True;

	    fill->upcase = True;

	    break;

	case UpCaseCharacter:

	    fill->upcase = True;

	    break;

	case LiteralCharacter:

	    if(fill->c == '\0')

		fill->c = trans->c;

	    else if(fill->c != trans->c)

		fill->reject = True;

	    break;

	    /* gr... AnyCharacter isn't handled, and gcc issues a warning. */

	default:

	    break;

	}

	trans = trans->next;

    }

}

#ifdef DEBUG

static void

_XiPrintStateVector(XmPictureStateRec *state)

{

    int i;

    char c;

    for(i=0; i<state->picture->num_nodes; i++) {

	if(_XmPictureGetState(state->state, i))

	    c = '1';

	else

	    c = '0';

	printf("%c", c);

    }

    printf("\n");

}

#endif