1ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas/* 2ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas * Copyright 2017 Google Inc. 3ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas * 4ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas * Use of this source code is governed by a BSD-style license that can be 5ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas * found in the LICENSE file. 6ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas */ 7ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 8ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas#ifndef SKSL_REGEXNODE 9ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas#define SKSL_REGEXNODE 10ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 11ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas#include <string> 12ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas#include <vector> 13ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 14ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholasstruct NFA; 15ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 16ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas/** 17ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas * Represents a node in the parse tree of a regular expression. 18ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas */ 19ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholasstruct RegexNode { 20ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas enum Kind { 21ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kChar_Kind, 22ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kCharset_Kind, 23ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kConcat_Kind, 24ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kDot_Kind, 25ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kOr_Kind, 26ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kPlus_Kind, 27ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kRange_Kind, 28ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kQuestion_Kind, 29ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas kStar_Kind 30ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas }; 31ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 32ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas RegexNode(Kind kind) 33ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas : fKind(kind) {} 34ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 35ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas RegexNode(Kind kind, char payload) 36ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas : fKind(kind) { 37ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas fPayload.fChar = payload; 38ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas } 39ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 40ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas RegexNode(Kind kind, const char* children) 41ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas : fKind(kind) { 42ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas fPayload.fBool = false; 43ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas while (*children != '\0') { 44ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas fChildren.emplace_back(kChar_Kind, *children); 45ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas ++children; 46ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas } 47ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas } 48ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 49ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas RegexNode(Kind kind, RegexNode child) 50ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas : fKind(kind) { 51ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas fChildren.push_back(std::move(child)); 52ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas } 53ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 54ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas RegexNode(Kind kind, RegexNode child1, RegexNode child2) 55ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas : fKind(kind) { 56ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas fChildren.push_back(std::move(child1)); 57ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas fChildren.push_back(std::move(child2)); 58ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas } 59ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 60ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas /** 61ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas * Creates NFA states for this node, with a successful match against this node resulting in a 62ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas * transition to all of the states in the accept vector. 63ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas */ 64ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas std::vector<int> createStates(NFA* nfa, const std::vector<int>& accept) const; 65ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 66ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas std::string description() const; 67ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 68ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas Kind fKind; 69ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 70ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas union Payload { 71ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas char fChar; 72ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas bool fBool; 73ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas } fPayload; 74ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 75ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas std::vector<RegexNode> fChildren; 76ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas}; 77ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas 78ca82a922e3d081ae83c940f4fd3ccc8cc6f0916fEthan Nicholas#endif 79