RPA Toolkit
Fixed REX_DFA_NEXT macro.
[rpatk.git] / rex / rexdfa.c
1 /*
2  *  Regular Pattern Analyzer Toolkit (RPA/Tk)
3  *  Copyright (c) 2009-2012 Martin Stoilov
4  *
5  *  This program is free software: you can redistribute it and/or modify
6  *  it under the terms of the GNU General Public License as published by
7  *  the Free Software Foundation, either version 3 of the License, or
8  *  (at your option) any later version.
9  *
10  *  This program is distributed in the hope that it will be useful,
11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  *  GNU General Public License for more details.
14  *
15  *  You should have received a copy of the GNU General Public License
16  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  *
18  *  Martin Stoilov <martin@rpasearch.com>
19  */
20
21 #include <stdlib.h>
22 #include <stdio.h>
23 #include <ctype.h>
24 #include "rlib/rmem.h"
25 #include "rlib/rstring.h"
26 #include "rex/rexdfa.h"
27
28
29 rexdfa_t *rex_dfa_create(rexuint_t nstates, rexuint_t ntrans, rexuint_t naccsubstates, rexuint_t nsubstates)
30 {
31         rexdfa_t *dfa = (rexdfa_t *)r_zmalloc(sizeof(*dfa));
32         dfa->states = r_zmalloc(sizeof(rexdfs_t) * nstates);
33         dfa->trans = r_zmalloc(sizeof(rexdft_t) * ntrans);
34         if (naccsubstates)
35                 dfa->accsubstates = r_zmalloc(sizeof(rexdfss_t) * naccsubstates);
36         if (nsubstates)
37                 dfa->substates = r_zmalloc(sizeof(rexdfss_t) * nsubstates);
38         dfa->nstates = nstates;
39         dfa->ntrans = ntrans;
40         dfa->nsubstates = nsubstates;
41         dfa->naccsubstates = naccsubstates;
42         return dfa;
43 }
44
45
46 void rex_dfa_destroy(rexdfa_t *dfa)
47 {
48         if (dfa) {
49                 r_free(dfa->substates);
50                 r_free(dfa->accsubstates);
51                 r_free(dfa->states);
52                 r_free(dfa->trans);
53                 r_free(dfa);
54         }
55 }
56
57
58 rexdfs_t *rex_dfa_state(rexdfa_t *dfa, rexuint_t nstate)
59 {
60         rexdfs_t *s;
61         if (nstate >= dfa->nstates)
62                 return NULL;
63         s = REX_DFA_STATE(dfa, nstate);
64         return s;
65 }
66
67
68 rexdft_t *rex_dfa_transition(rexdfa_t *dfa, rexuint_t nstate, rexuint_t ntrans)
69 {
70         rexdft_t *t;
71         rexdfs_t *s = rex_dfa_state(dfa, nstate);
72         if (!s)
73                 return NULL;
74         if (ntrans >= s->ntrans)
75                 return NULL;
76         t = REX_DFA_TRANSITION(dfa, nstate, ntrans);
77         return t;
78 }
79
80
81 rexdfss_t *rex_dfa_substate(rexdfa_t *dfa, rexuint_t nstate, rexuint_t nsubstate)
82 {
83         rexdfss_t *ss;
84         rexdfs_t *s = rex_dfa_state(dfa, nstate);
85         if (!s)
86                 return NULL;
87         if (nsubstate >= s->nsubstates)
88                 return NULL;
89         ss = REX_DFA_SUBSTATE(dfa, nstate, nsubstate);
90         return ss;
91 }
92
93
94 rexdfss_t *rex_dfa_accsubstate(rexdfa_t *dfa, rexuint_t nstate, rexuint_t naccsubstate)
95 {
96         rexdfss_t *ss;
97         rexdfs_t *s = rex_dfa_state(dfa, nstate);
98         if (!s)
99                 return NULL;
100         if (naccsubstate >= s->naccsubstates)
101                 return NULL;
102         ss = REX_DFA_ACCSUBSTATE(dfa, nstate, naccsubstate);
103         return ss;
104 }
105
106
107 rexuint_t rex_dfa_next(rexdfa_t *dfa, rexuint_t nstate, rexchar_t input)
108 {
109         rexuint_t newstate = 0;
110         REX_DFA_NEXT(dfa, nstate, input, &newstate);
111         return newstate;
112 }
113
114
115 void rex_dfa_dumpstate(rexdfa_t *dfa, rexuint_t nstate)
116 {
117         long index;
118         char buf[240];
119         int bufsize = sizeof(buf) - 1;
120         int n = 0;
121         rexdfs_t *s = rex_dfa_state(dfa, nstate);
122         rexdfss_t *ss = NULL;
123         rexdft_t *t = NULL;
124
125         if (!s)
126                 return;
127         fprintf(stdout, "State %ld", (unsigned long)nstate);
128         fprintf(stdout, " (");
129         for (index = 0; index < s->nsubstates; index++) {
130                 ss = REX_DFA_SUBSTATE(dfa, nstate, index);
131                 if (ss) {
132                         fprintf(stdout, "%ld", (unsigned long)ss->uid);
133                         if (ss->type == REX_STATETYPE_ACCEPT)
134                                 fprintf(stdout, "*");
135                         if (index + 1 < s->nsubstates)
136                                 fprintf(stdout, ",");
137                 }
138         }
139         fprintf(stdout, ")");
140
141
142         fprintf(stdout, ": ");
143         if (s->type == REX_STATETYPE_ACCEPT) {
144                 fprintf(stdout, " REX_STATETYPE_ACCEPT ");
145                 fprintf(stdout, " (");
146                 for (index = 0; index < s->naccsubstates; index++) {
147                         ss = REX_DFA_ACCSUBSTATE(dfa, nstate, index);
148                         if (ss) {
149                                 fprintf(stdout, "%ld*", (unsigned long)ss->uid);
150                                 if (index + 1 < s->naccsubstates)
151                                         fprintf(stdout, ",");
152                         }
153                 }
154                 fprintf(stdout, ")");
155         } else if (s->type == REX_STATETYPE_DEAD) {
156                 fprintf(stdout, " REX_STATETYPE_DEAD ");
157         } else if (s->type == REX_STATETYPE_START) {
158                 fprintf(stdout, " REX_STATETYPE_START ");
159         }
160         fprintf(stdout, "\n");
161         for (index = 0; index < s->ntrans; index++) {
162                 t = &dfa->trans[s->trans + index];
163                 n = 0;
164                 if (t->lowin != t->highin) {
165                         if (isprint(t->lowin) && !isspace(t->lowin) && isprint(t->highin) && !isspace(t->highin) && !r_strchr("[]-^", t->lowin) && !r_strchr("[]-^", t->highin))
166                                 n += r_snprintf(buf + n, n < bufsize ? bufsize - n : 0, "    [%c - %c] ", t->lowin, t->highin);
167                         else
168                                 n += r_snprintf(buf + n, n < bufsize ? bufsize - n : 0, "    [0x%X - 0x%X] ", t->lowin, t->highin);
169                 } else {
170                         if (isprint(t->lowin) && !isspace(t->lowin))
171                                 n += r_snprintf(buf + n, n < bufsize ? bufsize - n : 0, "    '%c' ", t->lowin);
172                         else
173                                 n += r_snprintf(buf + n, n < bufsize ? bufsize - n : 0, "    0x%X ", t->lowin);
174                 }
175                 r_memset(buf + n, ' ', bufsize - n);
176                 n = 40;
177                 n += r_snprintf(buf + n, n < bufsize ? bufsize - n : 0, "-> %ld", t->state);
178                 fprintf(stdout, "%s\n", buf);
179         }
180         if (!s->ntrans)
181                 fprintf(stdout, "        (none)\n");
182         fprintf(stdout, "\n");
183 }
184
185