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 Rose mask construction from NGHolder.
31 */
32#include "ng_fixed_width.h"
33
34#include "grey.h"
35#include "ng_holder.h"
36#include "ng_util.h"
37#include "rose/rose_build.h"
38#include "util/container.h"
39#include "ue2common.h"
40
41#include <algorithm>
42#include <iterator>
43#include <set>
44
45using namespace std;
46
47namespace ue2 {
48
49static
50bool findMask(const NGHolder &g, vector<CharReach> *mask, bool *anchored,
51 flat_set<ReportID> *reports) {
52 DEBUG_PRINTF("looking for a mask pattern\n");
53 set<NFAVertex> s_succ;
54 insert(&s_succ, adjacent_vertices(g.start, g));
55
56 set<NFAVertex> sds_succ;
57 insert(&sds_succ, adjacent_vertices(g.startDs, g));
58
59 *anchored = sds_succ.size() == 1; /* sds itself */
60 bool floating = is_subset_of(s_succ, sds_succ);
61
62 DEBUG_PRINTF("sds %zu s %zu%s%s\n", sds_succ.size(), s_succ.size(),
63 *anchored ? " anchored" : "", floating ? " floating" : "");
64 if (!*anchored && !floating) {
65 DEBUG_PRINTF("semi-anchored\n");
66 return false;
67 }
68
69 set<NFAVertex> &succs = *anchored ? s_succ : sds_succ;
70 succs.erase(g.startDs);
71 if (succs.size() != 1) {
72 DEBUG_PRINTF("branchy root\n");
73 return false;
74 }
75
76 NFAVertex u = *anchored ? g.start : g.startDs;
77 NFAVertex v = *succs.begin();
78
79 while (true) {
80 DEBUG_PRINTF("validating vertex %zu\n", g[v].index);
81
82 assert(v != g.acceptEod);
83
84 // If we've reached an accept, we MAY have found a valid Rose pattern
85 if (v == g.accept) {
86 DEBUG_PRINTF("accept\n");
87 insert(reports, g[u].reports);
88 return true;
89 }
90
91 mask->push_back(g[v].char_reach);
92
93 if (out_degree(v, g) != 1) {
94 DEBUG_PRINTF("out_degree != 1\n");
95 return false; /* not a chain */
96 }
97
98 u = v;
99 v = *adjacent_vertices(v, g).first;
100
101 if (in_degree(v, g) != 1) {
102 DEBUG_PRINTF("blargh\n"); /* picks up cases where there is no path
103 * to case accept (large cycles),
104 * ensures term */
105 return false;
106 }
107 }
108}
109
110bool handleFixedWidth(RoseBuild &rose, const NGHolder &g, const Grey &grey) {
111 if (!grey.roseMasks) {
112 return false;
113 }
114
115 if (in_degree(g.acceptEod,g) != 1) {
116 DEBUG_PRINTF("EOD anchoring not supported\n");
117 return false;
118 }
119
120 flat_set<ReportID> reports;
121 bool anchored = false;
122 vector<CharReach> mask;
123
124 if (!findMask(g, &mask, &anchored, &reports)) {
125 return false;
126 }
127
128 DEBUG_PRINTF("%smasky masky\n", anchored ? "anchored " : "");
129
130 assert(!mask.empty());
131 assert(!reports.empty());
132
133 if (rose.add(anchored, mask, reports)) {
134 DEBUG_PRINTF("added as rose mask\n");
135 return true;
136 } else {
137 DEBUG_PRINTF("failed to add masky\n");
138 return false;
139 }
140}
141
142} // namespace ue2
143