1 /*
2  * Copyright (c) 2015-2016, 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 Miscellaneous optimisations.
31  */
32 
33 #ifndef NG_MISC_OPT_H
34 #define NG_MISC_OPT_H
35 
36 #include <map>
37 #include <vector>
38 
39 #include "ng_holder.h"
40 #include "som/som.h"
41 #include "util/depth.h"
42 
43 namespace ue2 {
44 
45 /** Small structure describing the bounds on a repeat. */
46 struct BoundedRepeatSummary {
BoundedRepeatSummaryBoundedRepeatSummary47     BoundedRepeatSummary(void) : repeatMin(0), repeatMax(depth::infinity()) {}
BoundedRepeatSummaryBoundedRepeatSummary48     BoundedRepeatSummary(const depth &min_in, const depth &max_in)
49         : repeatMin(min_in), repeatMax(max_in) {
50         assert(repeatMin <= repeatMax);
51         assert(repeatMax.is_reachable());
52     }
unboundedBoundedRepeatSummary53     bool unbounded(void) const { return repeatMax.is_infinite(); }
54 
55     depth repeatMin; //!< minimum repeat bound.
56     depth repeatMax; //!< maximum repeat bound.
57 };
58 
59 /* returns true if anything changed */
60 bool improveGraph(NGHolder &g, som_type som);
61 
62 /** Sometimes the reach of a vertex is greater than it needs to be to reduce
63  * stop chars for the benefit of the rest of our code base (accel, etc). In
64  * these circumstances, we can treat the reach as the smaller one as
65  * the graphs are equivalent. */
66 CharReach reduced_cr(NFAVertex v, const NGHolder &g,
67         const std::map<NFAVertex, BoundedRepeatSummary> &br_cyclic);
68 
69 std::vector<CharReach> reduced_cr(const NGHolder &g,
70            const std::map<NFAVertex, BoundedRepeatSummary> &br_cyclic);
71 
72 /** Remove cyclic stars connected to start */
73 bool mergeCyclicDotStars(NGHolder &g);
74 
75 /**
76  * Given a cyclic state 'c' with a broad reach and a later state 'v' that is
77  * only reachable if c is still on, then any edges to a successor of a direct
78  * successor of c with reach a superset of v are redundant.
79  */
80 bool prunePathsRedundantWithSuccessorOfCyclics(NGHolder &h, som_type som);
81 
82 } // namespace ue2
83 
84 #endif
85