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