Initial checkin of SkSL lexical analyzer generator (not actually in use yet).

Bug: skia:
Change-Id: I283feb9ac1cef134588204107ea019ce657e37b3
Reviewed-on: https://skia-review.googlesource.com/42084
Commit-Queue: Ethan Nicholas <ethannicholas@google.com>
Reviewed-by: Brian Salomon <bsalomon@google.com>

1 files changed, 41 insertions, 0 deletions

diff --git a/src/sksl/lex/NFA.cpp b/src/sksl/lex/NFA.cpp
new file mode 100644
index 0000000000..d1eb7497b3
--- /dev/null
+++ b/src/sksl/lex/NFA.cpp
@@ -0,0 +1,41 @@
+/*
+ * Copyright 2017 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "NFA.h"
+
+int NFA::match(std::string s) const {
+    std::vector<int> states = fStartStates;
+    for (size_t i = 0; i < s.size(); ++i) {
+        std::vector<int> next;
+        for (int id : states) {
+            if (fStates[id].accept(s[i])) {
+                for (int nextId : fStates[id].fNext) {
+                    if (fStates[nextId].fKind != NFAState::kRemapped_Kind) {
+                        next.push_back(nextId);
+                    } else {
+                        next.insert(next.end(), fStates[nextId].fData.begin(),
+                                    fStates[nextId].fData.end());
+                    }
+                }
+            }
+        }
+        if (!next.size()) {
+            return -1;
+        }
+        states = next;
+    }
+    int accept = -1;
+    for (int id : states) {
+        if (fStates[id].fKind == NFAState::kAccept_Kind) {
+            int result = fStates[id].fData[0];
+            if (accept == -1 || result < accept) {
+                accept = result;
+            }
+        }
+    }
+    return accept;
+}