1 /*
2 * Motif
3 *
4 * Copyright (c) 1987-2012, The Open Group. All rights reserved.
5 *
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
10 * any later version.
11 *
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
16 * details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
22 */
23
24 #include <Xm/PictureP.h>
25
26 static XmPictureNode* _XiGetNewNode(XmPictureRec*);
27 static void _XmPictureParseNode(XmPictureRec*, char**, XmPictureNode**,
28 XmPictureNode**, Boolean);
29 static XmPictureTransition* _XiGetNewTransition(XmTransType,
30 XmPictureNode*,
31 XmPictureNode*);
32 static void _XmPictureSetState(unsigned char*, int);
33 static char _XmPictureGetState(unsigned char*, int);
34 static void _XmPictureFollowTransitions(XmPictureStateRec*, char, XmPictureNode*);
35 static XmPictureNode *_XmPictureCopySubGraph(XmPictureRec*, int,
36 XmPictureNode*, XmPictureNode*);
37 static void _XmPictureTagNodes(XmPictureRec*, XmPictureNode**, int);
38 static void _XmPictureFillTraverse(XmPictureRec*, int, XmAutoFill*);
39
40 /*
41 * Parses the given string into an XmPicture object. Returns NULL on a
42 * mal-formed picture
43 */
44 XmPicture
XmParsePicture(char * input)45 XmParsePicture(char *input)
46 {
47 XmPictureRec *picture;
48 XmPictureNode *root_node;
49 XmPictureNode *end_node;
50
51 picture = XtNew(XmPictureRec);
52
53 picture->source = XtNewString(input);
54 picture->num_nodes = 0;
55 picture->nodes_alloced = NODE_START_COUNT;
56 picture->nodes = (XmPictureNode**)
57 XtMalloc(NODE_START_COUNT * sizeof(XmPictureNode*));
58
59 _XmPictureParseNode(picture, &input, &root_node, &end_node, False);
60
61 picture->start_node = root_node->index;
62 picture->final_node = end_node->index;
63
64 return picture;
65 }
66
67 /*
68 * Creates a new XmPictureState. The memory allocated must be freed by the
69 * user with XtFree()
70 */
71 XmPictureState
XmGetNewPictureState(XmPicture picture)72 XmGetNewPictureState(XmPicture picture)
73 {
74 int i;
75 XmPictureStateRec *state;
76
77 state = XtNew(XmPictureStateRec);
78
79 state->statesize = 1 + (picture->num_nodes * sizeof(char) / 8);
80
81 state->picture = picture;
82
83 state->state = (unsigned char*) XtMalloc(state->statesize);
84 state->newstate = (unsigned char*) XtMalloc(state->statesize);
85 for(i=0; i<state->statesize; i++) {
86 state->state[i] = 0;
87 state->newstate[i] = 0;
88 }
89
90 _XmPictureSetState(state->state, picture->start_node);
91
92 /*
93 * BAD BAD BAD HACK
94 * This just allocates a static 1024 character array. While this will
95 * be fine for the DataField, because only one state per widget will
96 * be allocated and because the strings will never get that long,
97 * this makes this library useless for generalized database stuff.
98 * DON'T attempt to make lots of these or use them for very long
99 * regexps until I get this fixed -- Andy
100 * Sigh, additionally, this is a security problem. Feeding this
101 * thing very long RE's and strings will therefore make the
102 * program crash, which is not something our customers want
103 */
104 state->current_string = XtMalloc(1024 * sizeof(char));
105 state->current_string[0] = '\0';
106 state->append = state->current_string;
107
108 return state;
109 }
110
111 /*
112 * Processes a single character. Returns a pointer to the current
113 * value of the string (which may have been auto-filled, if
114 * do_auto_fill is specified). If the current state vector contains
115 * the final state, it places True in is_finished, otherwise False.
116 */
117 char*
XmPictureProcessCharacter(XmPictureState state,char in,Boolean * is_finished)118 XmPictureProcessCharacter(XmPictureState state, char in, Boolean *is_finished)
119 {
120 int i;
121 char status;
122 unsigned char *temp;
123 char *save_start;
124
125 /*
126 * Reset the current-processing info
127 */
128 state->current = '\0';
129 state->upcase = False;
130 for(i=0; i<state->statesize; i++)
131 state->newstate[i] = 0;
132
133 /*
134 * For each node in the state set, try to follow all transitions
135 * (recursing on NullTransitions of course)
136 */
137 for(i=0; i<state->picture->num_nodes; i++) {
138 if(_XmPictureGetState(state->state, i)) {
139 _XmPictureFollowTransitions(state, in, state->picture->nodes[i]);
140 }
141 }
142
143 /*
144 * Swap the states
145 */
146 temp = state->state;
147 state->state = state->newstate;
148 state->newstate = temp;
149
150 /*
151 * Append whatever we accepted (which might have been upcased)
152 */
153 save_start = state->append;
154 if(state->current) {
155 *state->append = state->current;
156 state->append++;
157 *state->append = '\0';
158 }
159
160 /*
161 * If we didn't find _any_ transitions, return NULL
162 */
163 for(i=0; i<state->statesize; i++)
164 if(state->state[i] != 0)
165 break;
166 if(i == state->statesize) {
167 *is_finished = True;
168 return NULL;
169 }
170
171 /*
172 * If our set contains the final state, set is_finished to true
173 */
174 status = _XmPictureGetState(state->state, state->picture->final_node);
175 if(status) *is_finished = True;
176 else *is_finished = False;
177
178 return save_start;
179 }
180
181 void
XmPictureDelete(XmPicture p)182 XmPictureDelete(XmPicture p)
183 {
184 int i;
185 XmPictureTransition *trans, *delete_me;
186
187 /*
188 * First walk all the nodes, deleting the transitions then the
189 * nodes themselves
190 */
191 for(i=0; i<p->num_nodes; i++) {
192 trans = p->nodes[i]->transitions;
193 while(trans) {
194 delete_me = trans;
195 trans = trans->next;
196 XtFree((char*)delete_me);
197 }
198 XtFree((char*)p->nodes[i]);
199 }
200
201 /*
202 * Now the node table and finally the picture itself
203 */
204 XtFree((char*)p->nodes);
205 XtFree(p->source);
206 XtFree((char*)p);
207 }
208
209 void
XmPictureDeleteState(XmPictureState s)210 XmPictureDeleteState(XmPictureState s)
211 {
212 XtFree(s->current_string);
213 XtFree((char*)s->state);
214 XtFree((char*)s->newstate);
215 XtFree((char*)s);
216 }
217
218
219 char*
XmPictureGetCurrentString(XmPictureState s)220 XmPictureGetCurrentString(XmPictureState s)
221 {
222 return s->current_string;
223 }
224
225 char*
XmPictureDoAutoFill(XmPictureState state)226 XmPictureDoAutoFill(XmPictureState state)
227 {
228 XmAutoFill fill;
229 int i;
230 Boolean finished = False;
231
232 while(1) {
233
234 fill.reject = False;
235 fill.c = '\0';
236 fill.digit = False;
237 fill.upcase = False;
238 fill.letter = False;
239 fill.hexdigit = False;
240 fill.octaldigit = False;
241
242 for(i=0; i<state->picture->num_nodes; i++)
243 if(_XmPictureGetState(state->state, i))
244 _XmPictureFillTraverse(state->picture, i, &fill);
245
246 if(fill.c == '\0')
247 fill.reject = True;
248 if(fill.digit && (isdigit(fill.c) == 0))
249 fill.reject = True;
250 if(fill.hexdigit && (isxdigit(fill.c) == 0))
251 fill.reject = True;
252 if(fill.octaldigit && (fill.c < '0' || fill.c > '7'))
253 fill.reject = True;
254 if(fill.letter && (isalpha(fill.c) == 0))
255 fill.reject = True;
256 if(fill.upcase && islower(fill.c))
257 fill.reject = True;
258
259 if(fill.reject) return state->current_string;
260
261 XmPictureProcessCharacter(state, fill.c, &finished);
262
263 if(finished) return state->current_string;
264 }
265
266 }
267
268 /*
269 * Parses a single "node" of the regular expression. If returnNOW is true,
270 * this means only the very first complete RE encountered (a hack, to allow
271 * for the weird closure precedence: *ab should parse like {*a}b and not
272 * *{ab}), otherwise it reads until the end of the RE, be it a close brace
273 * or EOS.
274 */
275 static void
_XmPictureParseNode(XmPictureRec * picture,char ** in_string,XmPictureNode ** start_return,XmPictureNode ** end_return,Boolean returnNOW)276 _XmPictureParseNode(XmPictureRec *picture, char **in_string,
277 XmPictureNode **start_return,
278 XmPictureNode **end_return,
279 Boolean returnNOW)
280 {
281 XmPictureNode *start_node;
282 XmPictureNode *current_node;
283 XmPictureNode *start_node_2;
284 XmPictureNode *current_node_2;
285 XmPictureNode *newnode;
286 int node_idx;
287 XmPictureTransition *newtrans;
288 char inc;
289 int count;
290 char *endcount;
291
292 start_node = _XiGetNewNode(picture);
293 node_idx = start_node->index;
294 current_node = start_node;
295
296 while((inc = *((*in_string)++))) {
297 switch(inc) {
298 /*
299 * These are the "normal" single-character tokens that
300 * behave (more or less) like literals in the state
301 * machine.
302 */
303 case NUMDIGIT:
304 newnode = _XiGetNewNode(picture);
305 newtrans = _XiGetNewTransition(NumericDigit,
306 current_node, newnode);
307 current_node = newnode;
308 break;
309
310 case HEXDIGIT:
311 newnode = _XiGetNewNode(picture);
312 newtrans = _XiGetNewTransition(HexDigit,
313 current_node, newnode);
314 current_node = newnode;
315 break;
316
317 case OCTALDIGIT:
318 newnode = _XiGetNewNode(picture);
319 newtrans = _XiGetNewTransition(OctalDigit,
320 current_node, newnode);
321 current_node = newnode;
322 break;
323
324 case NONCASELETTER:
325 newnode = _XiGetNewNode(picture);
326 newtrans = _XiGetNewTransition(AnyLetter,
327 current_node, newnode);
328 current_node = newnode;
329 break;
330
331 case UPCASELETTER:
332 newnode = _XiGetNewNode(picture);
333 newtrans = _XiGetNewTransition(UpCaseLetter,
334 current_node, newnode);
335 current_node = newnode;
336 break;
337
338 case NONCASECHAR:
339 newnode = _XiGetNewNode(picture);
340 newtrans = _XiGetNewTransition(AnyCharacter,
341 current_node, newnode);
342 current_node = newnode;
343 break;
344
345 case UPCASECHAR:
346 newnode = _XiGetNewNode(picture);
347 newtrans = _XiGetNewTransition(UpCaseCharacter,
348 current_node, newnode);
349 current_node = newnode;
350 break;
351
352 /*
353 * The weird stuff.
354 */
355
356 /*
357 * Read a numeric specifier, if it exists, then read the
358 * next _single_ R.E. (i.e., not a string of concatenated
359 * ones!); Add a transition from the current end state to the
360 * end (!) state of the new closure states, and a transition
361 * from that end to it's beginning.
362 */
363 case CLOSURE: /* CR03602 picture should formatted to *nx;
364 n is no. of time repeat; x is the specified
365 character going to be display */
366 count = strtol(*in_string, &endcount, 0);
367 if(count)
368 *in_string = endcount;
369 _XmPictureParseNode(picture, in_string,
370 &start_node_2, ¤t_node_2,
371 True);
372 if(count) {
373 newtrans = _XiGetNewTransition(NullTransition,
374 current_node, start_node_2);
375 current_node = _XmPictureCopySubGraph(picture, count-1,
376 start_node_2,
377 current_node_2);
378 } else {
379 newtrans = _XiGetNewTransition(NullTransition,
380 current_node_2, start_node_2);
381 newtrans = _XiGetNewTransition(NullTransition,
382 current_node, current_node_2);
383
384 current_node = current_node_2;
385 }
386 break;
387
388 /*
389 * Read the next (NOT singleton, this time) R.E.; create a _new_
390 * initial state which has null-transitions to both the
391 * current and new R.E.'s, and a new final state to which
392 * both trails lead.
393 */
394 case ALTERNATIVE: /* CR03656 CR03359 a major overhaul */
395 _XmPictureParseNode(picture, in_string,
396 &start_node_2, ¤t_node_2,
397 True);
398 newtrans = _XiGetNewTransition(NullTransition, current_node,
399 current_node_2);
400 if (current_node->index)
401 picture->nodes[current_node->index - 1]->transitions->next =
402 start_node_2->transitions;
403 current_node = current_node_2;
404 break;
405
406 /*
407 * This actually is a special case of ALTERNATIVE. The
408 * stuff inside the brackets becomes one chain, and a
409 * null-transition becomes the second. Just read the
410 * (NON-singleton) RE until the close-bracket.
411 */
412 case LBRACKET:
413 _XmPictureParseNode(picture, in_string,
414 &start_node_2, ¤t_node_2,
415 False);
416
417 newtrans = _XiGetNewTransition(NullTransition,
418 current_node, current_node_2);
419 newtrans = _XiGetNewTransition(NullTransition,
420 current_node, start_node_2);
421
422 current_node = current_node_2;
423
424 break;
425
426 /*
427 * The easiest special case to handle. Just read a
428 * non-singleton R.E. until the close-brace and stick it
429 * in as a "literal".
430 */
431 case LBRACE:
432 _XmPictureParseNode(picture, in_string,
433 &start_node_2, ¤t_node_2,
434 False);
435
436 newtrans = _XiGetNewTransition(NullTransition,
437 current_node, start_node_2);
438
439 current_node = current_node_2;
440
441 break;
442
443 /*
444 * Deal with both end-of-subexpression tokens in the same
445 * way. This will accept stuff like {...] and [...}, but that's
446 * probably OK, since it will only parse stuff incorrectly
447 * for things like: [...{...]...} which aren't legal
448 * anyway. I.E., we accept a superset of legal pictures,
449 * but parse all legal pictures correctly.
450 */
451 case RBRACE:
452 case RBRACKET:
453 returnNOW = True;
454 break;
455
456 /*
457 * Special case handling for the ';' escape character.
458 * Make sure dumb users haven't escaped the end of the string
459 * then advance the pointer and fall through to the (default)
460 * handling for a literal.
461 */
462 case ESCAPE:
463 inc = **in_string;
464 if(inc == '\0') break;
465 else (*in_string)++;
466 /*
467 * It's not a special character, so it must be a literal
468 */
469 default:
470 newnode = _XiGetNewNode(picture);
471 newtrans = _XiGetNewTransition(LiteralCharacter,
472 current_node, newnode);
473 newtrans->c = inc;
474 current_node = newnode;
475 break;
476 }
477
478 /*
479 * Break out if we have to
480 */
481 if(returnNOW == True) break;
482 }
483 *start_return = start_node;
484 *end_return = current_node;
485 }
486
487 static XmPictureTransition*
_XiGetNewTransition(XmTransType type,XmPictureNode * src,XmPictureNode * dest)488 _XiGetNewTransition(XmTransType type,
489 XmPictureNode *src, XmPictureNode *dest)
490 {
491 XmPictureTransition *t = XtNew(XmPictureTransition);
492 t->destination = dest->index;
493 t->type = type;
494 t->next = src->transitions;
495 src->transitions = t;
496 return t;
497 }
498
499 /*
500 * Allocates a new state machine node
501 */
502 static XmPictureNode*
_XiGetNewNode(XmPictureRec * picture)503 _XiGetNewNode(XmPictureRec *picture)
504 {
505 XmPictureNode *new_node;
506
507 new_node = XtNew(XmPictureNode);
508 new_node->transitions = NULL;
509 new_node->index = picture->num_nodes++;
510
511 /*
512 * Handle growing the picture past it's boundary
513 */
514 if(picture->num_nodes > picture->nodes_alloced) {
515 int newsize = picture->nodes_alloced * 2;
516
517 picture->nodes = (XmPictureNode**)
518 XtRealloc((char*)picture->nodes,
519 newsize * sizeof(XmPictureNode*));
520 picture->nodes_alloced = newsize;
521 }
522
523 picture->nodes[new_node->index] = new_node;
524
525 return new_node;
526 }
527
528 static void
_XmPictureSetState(unsigned char * v,int i)529 _XmPictureSetState(unsigned char *v, int i)
530 {
531 int base = i / 8;
532 int offset = i % 8;
533
534 v[base] |= 1 << offset;
535 }
536
537 /*
538 * Do I need this at all?
539 *
540 static void
541 _XmPictureClearState(char *v, int i)
542 {
543 int base = i / 8;
544 int offset = i % 8;
545
546 v[base] &= ~(1 << offset);
547 }
548 */
549
550 static char
_XmPictureGetState(unsigned char * v,int i)551 _XmPictureGetState(unsigned char *v, int i)
552 {
553 int base = i / 8;
554 int offset = i % 8;
555 int result = v[base] & (1 << offset);
556
557 if(result) return 1;
558 else return 0;
559 }
560
561 /*
562 * The inc parameter gets set to '\0' if we are following a null
563 * transition after already having read the character.
564 */
565 static void
_XmPictureFollowTransitions(XmPictureStateRec * state,char inc,XmPictureNode * node)566 _XmPictureFollowTransitions(XmPictureStateRec *state, char inc,
567 XmPictureNode *node)
568 {
569 XmPictureTransition *curr = node->transitions;
570 char follow_c, changed_c;
571 Boolean found = False;
572 Boolean accepted = True;
573
574 while(curr) {
575 follow_c = '\0';
576 changed_c = '\0';
577 switch(curr->type) {
578 case NullTransition:
579 follow_c = inc;
580 found = True;
581 if(inc != '\0')
582 accepted = False;
583 break;
584 case NumericDigit:
585 if(isdigit(inc)) {
586 found = True;
587 }
588 break;
589 case HexDigit:
590 if(isdigit(inc) ||
591 (inc >= 'a' && inc <= 'f') ||
592 (inc >= 'A' && inc <= 'F')) {
593 found = True;
594 }
595 break;
596 case OctalDigit:
597 if((inc >= '0') && (inc <= '7')) {
598 found = True;
599 }
600 break;
601 case AnyLetter:
602 if(isalpha(inc)) {
603 found = True;
604 }
605 break;
606 case UpCaseLetter:
607 if(isalpha(inc)) {
608 changed_c = toupper(inc);
609 found = True;
610 }
611 break;
612 case AnyCharacter:
613 if(isalnum(inc)) {
614 found = True;
615 }
616 break;
617 case UpCaseCharacter:
618 if(isalnum(inc)) {
619 changed_c = toupper(inc);
620 found = True;
621 }
622 break;
623 case LiteralCharacter:
624 if(inc == curr->c) {
625 found = True;
626 }
627 break;
628 }
629
630 if(found) {
631 if(changed_c) {
632 state->current = changed_c;
633 } else if(inc) {
634 state->current = inc;
635 }
636 if(accepted)
637 _XmPictureSetState(state->newstate, curr->destination);
638 _XmPictureFollowTransitions(state, follow_c,
639 state->picture
640 ->nodes[curr->destination]);
641 }
642 found = False;
643 curr = curr->next;
644 }
645 }
646
647
648 /*
649 * Recursively traverses a subgraph, tagging all indices in table with
650 * a non-null value.
651 */
652 static void
_XmPictureTagNodes(XmPictureRec * picture,XmPictureNode ** table,int start)653 _XmPictureTagNodes(XmPictureRec *picture, XmPictureNode **table, int start)
654 {
655 XmPictureTransition *trans = picture->nodes[start]->transitions;
656
657 table[start] = (XmPictureNode*)0x1;
658
659 while(trans) {
660 _XmPictureTagNodes(picture, table, trans->destination);
661 trans = trans->next;
662 }
663 }
664
665 /*
666 * Makes a string of n copies of the subgraph indicated, chaining them
667 * end-to-end. It returns the new end node for the multiplied
668 * subgraph (the start node is the unchanged, of course)
669 */
670 static XmPictureNode*
_XmPictureCopySubGraph(XmPictureRec * picture,int n,XmPictureNode * start,XmPictureNode * end)671 _XmPictureCopySubGraph(XmPictureRec *picture, int n,
672 XmPictureNode *start, XmPictureNode *end)
673 {
674 XmPictureNode **table;
675 XmPictureTransition *trans, *newtrans;
676 int i, j, tablesize, end_index;
677
678
679 /*
680 * Bail if the user did a repeat count of 1
681 */
682 if(n < 1) return end;
683
684 /*
685 * First allocate a pointer array of the same size as the current
686 * picture. This will hold NULL for nodes not in the subgraph and
687 * the XmPictureNode for the newest copy.
688 */
689 tablesize = picture->num_nodes;
690 table = (XmPictureNode**)
691 XtMalloc(tablesize * sizeof(XmPictureNode*));
692 for(i=0; i<picture->num_nodes; i++)
693 table[i] = NULL;
694
695 /*
696 * Now recursively tag the ones in our subgraph with non-NULL
697 * values
698 */
699 _XmPictureTagNodes(picture, table, start->index);
700
701 /*
702 * Now loop: for each non-NULL, allocate a new node in its
703 * place; then go through each transition from the _original_
704 * nodes, and put equivalent ones in the new table's nodes.
705 * Finally chain it to the end of the previous node.
706 */
707 end_index = end->index;
708 for(i=0; i<n; i++) {
709
710 /* Allocate the new nodes */
711 for(j=0; j<tablesize; j++)
712 if(table[j]) table[j] = _XiGetNewNode(picture);
713
714 /* Fill them in */
715 for(j=0; j<tablesize; j++) {
716 if(table[j]) {
717 trans = picture->nodes[j]->transitions;
718 while(trans) {
719 /*
720 * Hack to make sure we don't follow transitions
721 * into the newly created nodes
722 */
723 if(trans->destination >= tablesize) {
724 trans = trans->next;
725 continue;
726 }
727
728 newtrans = _XiGetNewTransition(trans->type,
729 table[j],
730 table[trans->destination]);
731 newtrans->c = trans->c;
732 trans = trans->next;
733 }
734 }
735 }
736
737 _XiGetNewTransition(NullTransition, end, table[start->index]);
738 end = table[end_index];
739 }
740
741 XtFree((void*)table);
742
743 return end;
744 }
745
746 static void
_XmPictureFillTraverse(XmPictureRec * picture,int start,XmAutoFill * fill)747 _XmPictureFillTraverse(XmPictureRec *picture, int start, XmAutoFill *fill)
748 {
749 XmPictureTransition *trans = picture->nodes[start]->transitions;
750
751 while(trans) {
752 switch(trans->type) {
753 case NullTransition:
754 _XmPictureFillTraverse(picture, trans->destination, fill);
755 break;
756 case NumericDigit:
757 fill->digit = True;
758 break;
759 case HexDigit:
760 fill->hexdigit = True;
761 break;
762 case OctalDigit:
763 fill->octaldigit = True;
764 break;
765 case AnyLetter:
766 fill->letter = True;
767 break;
768 case UpCaseLetter:
769 fill->letter = True;
770 fill->upcase = True;
771 break;
772 case UpCaseCharacter:
773 fill->upcase = True;
774 break;
775 case LiteralCharacter:
776 if(fill->c == '\0')
777 fill->c = trans->c;
778 else if(fill->c != trans->c)
779 fill->reject = True;
780 break;
781 /* gr... AnyCharacter isn't handled, and gcc issues a warning. */
782 default:
783 break;
784 }
785 trans = trans->next;
786 }
787 }
788
789 #ifdef DEBUG
790 static void
_XiPrintStateVector(XmPictureStateRec * state)791 _XiPrintStateVector(XmPictureStateRec *state)
792 {
793 int i;
794 char c;
795
796 for(i=0; i<state->picture->num_nodes; i++) {
797 if(_XmPictureGetState(state->state, i))
798 c = '1';
799 else
800 c = '0';
801 printf("%c", c);
802 }
803 printf("\n");
804 }
805 #endif
806