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 Build code for vacuous graphs.
31 */
32#include "ng_vacuous.h"
33
34#include "grey.h"
35#include "ng.h"
36#include "ng_util.h"
37#include "compiler/compiler.h"
38
39using namespace std;
40
41namespace ue2 {
42
43static
44ReportID getInternalId(ReportManager &rm, const ExpressionInfo &expr) {
45 Report ir = rm.getBasicInternalReport(expr);
46
47 // Apply any extended params.
48 if (expr.min_offset || expr.max_offset != MAX_OFFSET) {
49 ir.minOffset = expr.min_offset;
50 ir.maxOffset = expr.max_offset;
51 }
52
53 assert(!expr.min_length); // should be handled elsewhere.
54
55 return rm.getInternalId(ir);
56}
57
58static
59void makeFirehose(BoundaryReports &boundary, ReportManager &rm, NGHolder &g,
60 const ExpressionInfo &expr) {
61 const ReportID r = getInternalId(rm, expr);
62
63 boundary.report_at_0_eod.insert(r);
64 boundary.report_at_0.insert(r);
65
66 // Replace the graph with a '.+'.
67
68 clear_graph(g);
69 clearReports(g);
70 remove_edge(g.start, g.accept, g);
71 remove_edge(g.start, g.acceptEod, g);
72 remove_edge(g.startDs, g.accept, g);
73 remove_edge(g.startDs, g.acceptEod, g);
74
75 NFAVertex v = add_vertex(g);
76 g[v].char_reach.setall();
77 g[v].reports.insert(r);
78 add_edge(v, v, g);
79 add_edge(g.start, v, g);
80 add_edge(g.startDs, v, g);
81 add_edge(v, g.accept, g);
82}
83
84static
85void makeAnchoredAcceptor(BoundaryReports &boundary, ReportManager &rm,
86 NGHolder &g, const ExpressionInfo &expr) {
87 boundary.report_at_0.insert(getInternalId(rm, expr));
88 remove_edge(g.start, g.accept, g);
89 remove_edge(g.start, g.acceptEod, g);
90 g[g.start].reports.clear();
91}
92
93static
94void makeEndAnchoredAcceptor(BoundaryReports &boundary, ReportManager &rm,
95 NGHolder &g, const ExpressionInfo &expr) {
96 boundary.report_at_eod.insert(getInternalId(rm, expr));
97 remove_edge(g.startDs, g.acceptEod, g);
98 remove_edge(g.start, g.acceptEod, g);
99 g[g.start].reports.clear();
100 g[g.startDs].reports.clear();
101}
102
103static
104void makeNothingAcceptor(BoundaryReports &boundary, ReportManager &rm,
105 NGHolder &g, const ExpressionInfo &expr) {
106 boundary.report_at_0_eod.insert(getInternalId(rm, expr));
107 remove_edge(g.start, g.acceptEod, g);
108 g[g.start].reports.clear();
109}
110
111bool splitOffVacuous(BoundaryReports &boundary, ReportManager &rm,
112 NGHolder &g, const ExpressionInfo &expr) {
113 if (edge(g.startDs, g.accept, g).second) {
114 // e.g. '.*'; match "between" every byte
115 DEBUG_PRINTF("graph is firehose\n");
116 makeFirehose(boundary, rm, g, expr);
117 return true;
118 }
119
120 bool work_done = false;
121
122 if (edge(g.start, g.accept, g).second) {
123 DEBUG_PRINTF("creating anchored acceptor\n");
124 makeAnchoredAcceptor(boundary, rm, g, expr);
125 work_done = true;
126 }
127
128 if (edge(g.startDs, g.acceptEod, g).second) {
129 DEBUG_PRINTF("creating end-anchored acceptor\n");
130 makeEndAnchoredAcceptor(boundary, rm, g, expr);
131 work_done = true;
132 }
133
134 if (edge(g.start, g.acceptEod, g).second) {
135 DEBUG_PRINTF("creating nothing acceptor\n");
136 makeNothingAcceptor(boundary, rm, g, expr);
137 work_done = true;
138 }
139
140 return work_done;
141}
142
143} // namespace ue2
144