1/*
2 * Copyright (c) 2015, 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 Short Exhaustible Passthroughs.
31 *
32 * Analysis code for determining whether a graph should be treated specially
33 * because it is short and contains exhaustible reports; typically we turn
34 * these into outfixes rather than risk them becoming Rose literals.
35 *
36 * For example, the pattern:
37 *
38 * /[a-f]/H
39 *
40 * ... is far better suited to becoming a small outfix that generates one match
41 * and goes dead than being split into six one-byte Rose literals that end up
42 * in the literal matcher.
43 */
44#include "ng_sep.h"
45
46#include "grey.h"
47#include "ng_holder.h"
48#include "ng_reports.h"
49#include "ng_util.h"
50#include "ue2common.h"
51#include "util/graph_range.h"
52
53using namespace std;
54
55namespace ue2 {
56
57static
58bool checkFromVertex(const NGHolder &g, NFAVertex start) {
59 for (auto v : adjacent_vertices_range(start, g)) {
60 if (v == g.startDs) {
61 continue;
62 }
63
64 assert(!is_special(v, g)); /* should not be vacuous */
65
66 if (!edge(g.startDs, v, g).second) { /* only floating starts */
67 return false;
68 } else if (out_degree(v, g) == 1
69 && edge(v, g.accept, g).second) { /* only floating end */
70 ; /* possible sep */
71 } else {
72 return false;
73 }
74 }
75 return true;
76}
77
78bool isSEP(const NGHolder &g, const ReportManager &rm, const Grey &grey) {
79 if (!grey.mergeSEP || !can_exhaust(g, rm)) {
80 return false;
81 }
82
83 if (!checkFromVertex(g, g.start) || !checkFromVertex(g, g.startDs)) {
84 return false;
85 }
86
87 assert(out_degree(g.start, g) || proper_out_degree(g.startDs, g));
88
89 DEBUG_PRINTF("graph is an SEP\n");
90 return true;
91}
92
93} // namespace ue2
94