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
16struct 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