src/sksl/lex/NFA.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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 INVALID;
        }
        states = next;
    }
    int accept = INVALID;
    for (int id : states) {
        if (fStates[id].fKind == NFAState::kAccept_Kind) {
            int result = fStates[id].fData[0];
            if (accept == INVALID || result < accept) {
                accept = result;
            }
        }
    }
    return accept;
}