1/*
2 * Copyright (c) 2015-2017, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** \file
30 * \brief DFA determinisation code.
31 */
32
33#ifndef DETERMINISE_H
34#define DETERMINISE_H
35
36#include "nfagraph/ng_holder.h"
37#include "charreach.h"
38#include "container.h"
39#include "ue2common.h"
40
41#include <algorithm>
42#include <array>
43#include <queue>
44#include <vector>
45
46namespace ue2 {
47
48/* Automaton details:
49 *
50 * const vector<StateSet> initial()
51 * returns initial states to start determinising from. StateSets in the
52 * initial() vector will given consecutive ids starting from 1, in the order
53 * that they appear.
54 *
55 * void reports(StateSet s, flat_set<ReportID> *out)
56 * fills out with any reports that need to be raised for stateset.
57 *
58 * void reportsEod(StateSet s, flat_set<ReportID> *out)
59 * fills out with any reports that need to be raised for stateset at EOD.
60 *
61 * void transition(const StateSet &in, StateSet *next)
62 * fills the next array such next[i] is the stateset that in transitions to
63 * on seeing symbol i (i is in the compressed alphabet of the automaton).
64 *
65 * u16 alphasize
66 * size of the compressed alphabet
67 */
68
69/** \brief determinises some sort of nfa
70 * \param n the automaton to determinise
71 * \param dstates_out output dfa states
72 * \param state_limit limit on the number of dfa states to construct
73 * \param statesets_out a mapping from DFA state to the set of NFA states in
74 * the automaton
75 * \return true on success, false if state limit exceeded
76 */
77template<class Auto, class ds>
78never_inline
79bool determinise(Auto &n, std::vector<ds> &dstates, size_t state_limit,
80 std::vector<typename Auto::StateSet> *statesets_out = nullptr) {
81 DEBUG_PRINTF("the determinator\n");
82 using StateSet = typename Auto::StateSet;
83 typename Auto::StateMap dstate_ids;
84
85 const size_t alphabet_size = n.alphasize;
86
87 dstates.clear();
88 dstates.reserve(state_limit);
89
90 dstate_ids.emplace(n.dead, DEAD_STATE);
91 dstates.push_back(ds(alphabet_size));
92 std::fill_n(dstates[0].next.begin(), alphabet_size, DEAD_STATE);
93
94 std::queue<std::pair<StateSet, dstate_id_t>> q;
95 q.emplace(n.dead, DEAD_STATE);
96
97 const std::vector<StateSet> &init = n.initial();
98 for (u32 i = 0; i < init.size(); i++) {
99 q.emplace(init[i], dstates.size());
100 assert(!contains(dstate_ids, init[i]));
101 dstate_ids.emplace(init[i], dstates.size());
102 dstates.push_back(ds(alphabet_size));
103 }
104
105 std::vector<StateSet> succs(alphabet_size, n.dead);
106
107 while (!q.empty()) {
108 auto m = std::move(q.front());
109 q.pop();
110 StateSet &curr = m.first;
111 dstate_id_t curr_id = m.second;
112
113 DEBUG_PRINTF("curr: %hu\n", curr_id);
114
115 /* fill in accepts */
116 n.reports(curr, dstates[curr_id].reports);
117 n.reportsEod(curr, dstates[curr_id].reports_eod);
118
119 if (!dstates[curr_id].reports.empty()) {
120 DEBUG_PRINTF("curr: %hu: is accept\n", curr_id);
121 }
122
123 if (!dstates[curr_id].reports.empty()) {
124 /* only external reports set ekeys */
125 if (n.canPrune(dstates[curr_id].reports)) {
126 /* we only transition to dead on characters, TOPs leave us
127 * alone */
128 std::fill_n(dstates[curr_id].next.begin(), alphabet_size,
129 DEAD_STATE);
130 dstates[curr_id].next[n.alpha[TOP]] = curr_id;
131 continue;
132 }
133 }
134
135 /* fill in successor states */
136 n.transition(curr, &succs[0]);
137 for (symbol_t s = 0; s < n.alphasize; s++) {
138 dstate_id_t succ_id;
139 if (s && succs[s] == succs[s - 1]) {
140 succ_id = dstates[curr_id].next[s - 1];
141 } else {
142 auto p = dstate_ids.find(succs[s]);
143 if (p != dstate_ids.end()) { // succ[s] is already present
144 succ_id = p->second;
145 if (succ_id > curr_id && !dstates[succ_id].daddy
146 && n.unalpha[s] < N_CHARS) {
147 dstates[succ_id].daddy = curr_id;
148 }
149 } else {
150 succ_id = dstate_ids.size();
151 dstate_ids.emplace(succs[s], succ_id);
152 dstates.push_back(ds(alphabet_size));
153 dstates.back().daddy = n.unalpha[s] < N_CHARS ? curr_id : 0;
154 q.emplace(succs[s], succ_id);
155 }
156
157 DEBUG_PRINTF("-->%hu on %02hx\n", succ_id, n.unalpha[s]);
158 }
159
160 if (succ_id >= state_limit) {
161 DEBUG_PRINTF("succ_id %hu >= state_limit %zu\n",
162 succ_id, state_limit);
163 dstates.clear();
164 return false;
165 }
166
167 dstates[curr_id].next[s] = succ_id;
168 }
169 }
170
171 // The dstates vector will persist in the raw_dfa.
172 dstates.shrink_to_fit();
173
174 if (statesets_out) {
175 auto &statesets = *statesets_out;
176 statesets.resize(dstate_ids.size());
177 for (auto &m : dstate_ids) {
178 statesets[m.second] = std::move(m.first);
179 }
180 }
181
182 DEBUG_PRINTF("ok\n");
183 return true;
184}
185
186static inline
187std::vector<CharReach> populateCR(const NGHolder &g,
188 const std::vector<NFAVertex> &v_by_index,
189 const std::array<u16, ALPHABET_SIZE> &alpha) {
190 std::vector<CharReach> cr_by_index(v_by_index.size());
191
192 for (size_t i = 0; i < v_by_index.size(); i++) {
193 const CharReach &cr = g[v_by_index[i]].char_reach;
194 CharReach &cr_out = cr_by_index[i];
195 for (size_t s = cr.find_first(); s != cr.npos; s = cr.find_next(s)) {
196 cr_out.set(alpha[s]);
197 }
198 }
199
200 return cr_by_index;
201}
202
203} // namespace ue2
204
205#endif
206