lib/Xm/Picture.c

/*
 * 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<n; i++) {

	/* Allocate the new nodes */
	for(j=0; j<tablesize; j++)
	    if(table[j]) table[j] = _XiGetNewNode(picture);

	/* Fill them in */
	for(j=0; j<tablesize; 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