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 | #ifndef RDFA_H |
30 | #define RDFA_H |
31 | |
32 | #include "nfa_kind.h" |
33 | #include "ue2common.h" |
34 | |
35 | #include "util/flat_containers.h" |
36 | |
37 | #include <array> |
38 | #include <vector> |
39 | |
40 | namespace ue2 { |
41 | |
42 | typedef u16 dstate_id_t; |
43 | typedef u16 symbol_t; |
44 | |
45 | static constexpr symbol_t TOP = 256; |
46 | static constexpr symbol_t ALPHABET_SIZE = 257; |
47 | static constexpr symbol_t N_SPECIAL_SYMBOL = 1; |
48 | static constexpr dstate_id_t DEAD_STATE = 0; |
49 | |
50 | /** Structure representing a dfa state during construction. */ |
51 | struct dstate { |
52 | /** Next state; indexed by remapped sym */ |
53 | std::vector<dstate_id_t> next; |
54 | |
55 | /** Set by ng_mcclellan, refined by mcclellancompile */ |
56 | dstate_id_t daddy = 0; |
57 | |
58 | /** Set by mcclellancompile, implementation state id, excludes edge |
59 | * decorations */ |
60 | dstate_id_t impl_id = 0; |
61 | |
62 | /** Reports to fire (at any location). */ |
63 | flat_set<ReportID> reports; |
64 | |
65 | /** Reports to fire (at EOD). */ |
66 | flat_set<ReportID> reports_eod; |
67 | |
68 | explicit dstate(size_t alphabet_size) : next(alphabet_size, 0) {} |
69 | }; |
70 | |
71 | struct raw_dfa { |
72 | nfa_kind kind; |
73 | std::vector<dstate> states; |
74 | dstate_id_t start_anchored = DEAD_STATE; |
75 | dstate_id_t start_floating = DEAD_STATE; |
76 | u16 alpha_size = 0; /* including special symbols */ |
77 | |
78 | /* mapping from input symbol --> equiv class id */ |
79 | std::array<u16, ALPHABET_SIZE> alpha_remap; |
80 | |
81 | explicit raw_dfa(nfa_kind k) : kind(k) {} |
82 | virtual ~raw_dfa(); |
83 | |
84 | u16 getImplAlphaSize() const { return alpha_size - N_SPECIAL_SYMBOL; } |
85 | virtual void (void); |
86 | bool hasEodReports(void) const; |
87 | }; |
88 | |
89 | } |
90 | |
91 | #endif |
92 | |