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#include "RegexNode.h"
9
10#include "NFA.h"
11
12std::vector<int> RegexNode::createStates(NFA* nfa, const std::vector<int>& accept) const {
13    std::vector<int> result;
14    switch (fKind) {
15        case kChar_Kind:
16            result.push_back(nfa->addState(NFAState(fPayload.fChar, accept)));
17            break;
18        case kCharset_Kind: {
19            std::vector<bool> chars;
20            for (const RegexNode& child : fChildren) {
21                if (child.fKind == kChar_Kind) {
22                    while (chars.size() <= (size_t) child.fPayload.fChar) {
23                        chars.push_back(false);
24                    }
25                    chars[child.fPayload.fChar] = true;
26                } else {
27                    ASSERT(child.fKind == kRange_Kind);
28                    while (chars.size() <= (size_t) child.fChildren[1].fPayload.fChar) {
29                        chars.push_back(false);
30                    }
31                    for (char c = child.fChildren[0].fPayload.fChar;
32                         c <= child.fChildren[1].fPayload.fChar;
33                         ++c) {
34                        chars[c] = true;
35                    }
36                }
37            }
38            result.push_back(nfa->addState(NFAState(fPayload.fBool, chars, accept)));
39            break;
40        }
41        case kConcat_Kind: {
42            std::vector<int> right = fChildren[1].createStates(nfa, accept);
43            result = fChildren[0].createStates(nfa, right);
44            break;
45        }
46        case kDot_Kind:
47            result.push_back(nfa->addState(NFAState(NFAState::kDot_Kind, accept)));
48            break;
49        case kOr_Kind: {
50            std::vector<int> states = fChildren[0].createStates(nfa, accept);
51            result.insert(result.end(), states.begin(), states.end());
52            states = fChildren[1].createStates(nfa, accept);
53            result.insert(result.end(), states.begin(), states.end());
54            break;
55        }
56        case kPlus_Kind: {
57            std::vector<int> next = accept;
58            std::vector<int> placeholder;
59            int id = nfa->addState(NFAState(placeholder));
60            next.push_back(id);
61            result = fChildren[0].createStates(nfa, next);
62            nfa->fStates[id] = NFAState(result);
63            break;
64        }
65        case kQuestion_Kind:
66            result = fChildren[0].createStates(nfa, accept);
67            result.insert(result.end(), accept.begin(), accept.end());
68            break;
69        case kRange_Kind:
70            ABORT("unreachable");
71        case kStar_Kind: {
72            std::vector<int> next = accept;
73            std::vector<int> placeholder;
74            int id = nfa->addState(NFAState(placeholder));
75            next.push_back(id);
76            result = fChildren[0].createStates(nfa, next);
77            result.insert(result.end(), accept.begin(), accept.end());
78            nfa->fStates[id] = NFAState(result);
79            break;
80        }
81    }
82    return result;
83}
84
85std::string RegexNode::description() const {
86    switch (fKind) {
87        case kChar_Kind:
88            return std::string(1, fPayload.fChar);
89        case kCharset_Kind: {
90            std::string result("[");
91            if (fPayload.fBool) {
92                result += "^";
93            }
94            for (const RegexNode& c : fChildren) {
95                result += c.description();
96            }
97            result += "]";
98            return result;
99        }
100        case kConcat_Kind:
101            return fChildren[0].description() + fChildren[1].description();
102        case kDot_Kind:
103            return ".";
104        case kOr_Kind:
105            return "(" + fChildren[0].description() + "|" + fChildren[1].description() + ")";
106        case kPlus_Kind:
107            return fChildren[0].description() + "+";
108        case kQuestion_Kind:
109            return fChildren[0].description() + "?";
110        case kRange_Kind:
111            return fChildren[0].description() + "-" + fChildren[1].description();
112        case kStar_Kind:
113            return fChildren[0].description() + "*";
114        default:
115            return "<" + std::to_string(fKind) + ">";
116    }
117}
118