Home | History | Annotate | Download | only in lex 
      1 /*
      2  * Copyright 2017 Google Inc.
      3  *
      4  * Use of this source code is governed by a BSD-style license that can be
      5  * found in the LICENSE file.
      6  */
      7 
      8 #ifndef SKSL_NFASTATE
      9 #define SKSL_NFASTATE
     10 
     11 #include <string>
     12 #include <vector>
     13 
     14 #include "LexUtil.h"
     15 
     16 struct NFAState {
     17     enum Kind {
     18         // represents an accept state - if the NFA ends up in this state, we have successfully
     19         // matched the token indicated by fData[0]
     20         kAccept_Kind,
     21         // matches the single character fChar
     22         kChar_Kind,
     23         // the regex '.'; matches any char but '\n'
     24         kDot_Kind,
     25         // a state which serves as a placeholder for the states indicated in fData. When we
     26         // transition to this state, we instead transition to all of the fData states.
     27         kRemapped_Kind,
     28         // contains a list of true/false values in fData. fData[c] tells us whether we accept the
     29         // character c.
     30         kTable_Kind
     31     };
     32 
     33     NFAState(Kind kind, std::vector<int> next)
     34     : fKind(kind)
     35     , fNext(std::move(next)) {}
     36 
     37     NFAState(char c, std::vector<int> next)
     38     : fKind(kChar_Kind)
     39     , fChar(c)
     40     , fNext(std::move(next)) {}
     41 
     42     NFAState(std::vector<int> states)
     43     : fKind(kRemapped_Kind)
     44     , fData(std::move(states)) {}
     45 
     46     NFAState(bool inverse, std::vector<bool> accepts, std::vector<int> next)
     47     : fKind(kTable_Kind)
     48     , fInverse(inverse)
     49     , fNext(std::move(next)) {
     50         for (bool b : accepts) {
     51             fData.push_back(b);
     52         }
     53     }
     54 
     55     NFAState(int token)
     56     : fKind(kAccept_Kind) {
     57         fData.push_back(token);
     58     }
     59 
     60     bool accept(char c) const {
     61         switch (fKind) {
     62             case kAccept_Kind:
     63                 return false;
     64             case kChar_Kind:
     65                 return c == fChar;
     66             case kDot_Kind:
     67                 return c != '\n';
     68             case kTable_Kind: {
     69                 bool value;
     70                 if ((size_t) c < fData.size()) {
     71                     value = fData[c];
     72                 } else {
     73                     value = false;
     74                 }
     75                 return value != fInverse;
     76             }
     77             default:
     78                 ABORT("unreachable");
     79         }
     80     }
     81 
     82     std::string description() const {
     83         switch (fKind) {
     84             case kAccept_Kind:
     85                 return "Accept(" + std::to_string(fData[0]) + ")";
     86             case kChar_Kind: {
     87                 std::string result = "Char('" + std::string(1, fChar) + "'";
     88                 for (int v : fNext) {
     89                     result += ", ";
     90                     result += std::to_string(v);
     91                 }
     92                 result += ")";
     93                 return result;
     94             }
     95             case kDot_Kind: {
     96                 std::string result = "Dot(";
     97                 const char* separator = "";
     98                 for (int v : fNext) {
     99                     result += separator;
    100                     result += std::to_string(v);
    101                     separator = ", ";
    102                 }
    103                 result += ")";
    104                 return result;
    105             }
    106             case kRemapped_Kind: {
    107                 std::string result = "Remapped(";
    108                 const char* separator = "";
    109                 for (int v : fData) {
    110                     result += separator;
    111                     result += std::to_string(v);
    112                     separator = ", ";
    113                 }
    114                 result += ")";
    115                 return result;
    116             }
    117             case kTable_Kind: {
    118                 std::string result = std::string("Table(") + (fInverse ? "true" : "false") + ", [";
    119                 const char* separator = "";
    120                 for (int v : fData) {
    121                     result += separator;
    122                     result += v ? "true" : "false";
    123                     separator = ", ";
    124                 }
    125                 result += "]";
    126                 for (int n : fNext) {
    127                     result += ", ";
    128                     result += std::to_string(n);
    129                 }
    130                 result += ")";
    131                 return result;
    132             }
    133             default:
    134                 ABORT("unreachable");
    135         }
    136     }
    137 
    138     Kind fKind;
    139 
    140     char fChar = 0;
    141 
    142     bool fInverse = false;
    143 
    144     std::vector<int> fData;
    145 
    146     // states we transition to upon a succesful match from this state
    147     std::vector<int> fNext;
    148 };
    149 
    150 #endif
    151