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