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 #include "config.h"
30 
31 #include <limits.h>
32 #include <vector>
33 
34 #include "gtest/gtest.h"
35 #include "hs.h"
36 #include "test_util.h"
37 
38 using namespace std;
39 using namespace testing;
40 
41 namespace /* anonymous */ {
42 
43 struct expected_info {
44     const char *pattern;
45     hs_expr_ext ext;
46 
47     unsigned min;
48     unsigned max;
49     char unordered_matches;
50     char matches_at_eod;
51     char matches_only_at_eod;
52 };
53 
operator <<(ostream & os,const hs_expr_ext & ext)54 ostream& operator<<(ostream &os, const hs_expr_ext &ext) {
55     if (!ext.flags) {
56         return os;
57     }
58     bool first = true;
59     if (ext.flags & HS_EXT_FLAG_MIN_OFFSET) {
60         if (!first) {
61             os << ", ";
62         }
63         os << "min_offset=" << ext.min_offset;
64         first = false;
65     }
66     if (ext.flags & HS_EXT_FLAG_MAX_OFFSET) {
67         if (!first) {
68             os << ", ";
69         }
70         os << "max_offset=" << ext.max_offset;
71         first = false;
72     }
73     if (ext.flags & HS_EXT_FLAG_MIN_LENGTH) {
74         if (!first) {
75             os << ", ";
76         }
77         os << "min_length=" << ext.min_length;
78         first = false;
79     }
80     if (ext.flags & HS_EXT_FLAG_EDIT_DISTANCE) {
81         if (!first) {
82             os << ", ";
83         }
84         os << "edit_distance=" << ext.edit_distance;
85         first = false;
86     }
87     if (ext.flags & HS_EXT_FLAG_HAMMING_DISTANCE) {
88         if (!first) {
89             os << ", ";
90         }
91         os << "hamming_distance=" << ext.hamming_distance;
92         first = false;
93     }
94     return os;
95 }
96 
97 // For Google Test.
PrintTo(const expected_info & ei,ostream * os)98 void PrintTo(const expected_info &ei, ostream *os) {
99     *os << "expected_info: "
100         << "pattern=\"" << ei.pattern << "\""
101         << ", ext={" << ei.ext << "}"
102         << ", min=" << ei.min << ", max=" << ei.max
103         << ", unordered_matches=" << (ei.unordered_matches ? 1 : 0)
104         << ", matches_at_eod=" << (ei.matches_at_eod ? 1 : 0)
105         << ", matches_only_at_eod=" << (ei.matches_only_at_eod ? 1 : 0);
106 }
107 
108 class ExprInfop : public TestWithParam<expected_info> {
109 };
110 
111 static
check_info(const expected_info & ei,const hs_expr_info_t * info)112 void check_info(const expected_info &ei, const hs_expr_info_t *info) {
113     EXPECT_EQ(ei.min, info->min_width);
114     EXPECT_EQ(ei.max, info->max_width);
115     EXPECT_EQ(ei.unordered_matches, info->unordered_matches);
116     EXPECT_EQ(ei.matches_at_eod, info->matches_at_eod);
117     EXPECT_EQ(ei.matches_only_at_eod, info->matches_only_at_eod);
118 }
119 
120 // Check with hs_expression_info function.
TEST_P(ExprInfop,check_no_ext)121 TEST_P(ExprInfop, check_no_ext) {
122     const expected_info &ei = GetParam();
123     SCOPED_TRACE(ei.pattern);
124 
125     if (ei.ext.flags) {
126         // This is an extparam test, skip it.
127         return;
128     }
129 
130     hs_expr_info_t *info = nullptr;
131     hs_compile_error_t *c_err = nullptr;
132     hs_error_t err = hs_expression_info(ei.pattern, 0, &info, &c_err);
133     ASSERT_EQ(HS_SUCCESS, err);
134     ASSERT_TRUE(info != nullptr);
135     ASSERT_TRUE(c_err == nullptr);
136 
137     check_info(ei, info);
138     free(info);
139 }
140 
141 // Check with hs_expression_ext_info function.
TEST_P(ExprInfop,check_ext)142 TEST_P(ExprInfop, check_ext) {
143     const expected_info &ei = GetParam();
144     SCOPED_TRACE(ei.pattern);
145 
146     hs_expr_info_t *info = nullptr;
147     hs_compile_error_t *c_err = nullptr;
148     hs_error_t err =
149         hs_expression_ext_info(ei.pattern, 0, &ei.ext, &info, &c_err);
150     ASSERT_EQ(HS_SUCCESS, err);
151     ASSERT_TRUE(info != nullptr);
152     ASSERT_TRUE(c_err == nullptr);
153 
154     check_info(ei, info);
155     free(info);
156 }
157 
158 // Check with hs_expression_ext_info function and a nullptr ext param, for
159 // cases where ext.flags == 0. Functionally identical to check_no_ext above.
TEST_P(ExprInfop,check_ext_null)160 TEST_P(ExprInfop, check_ext_null) {
161     const expected_info &ei = GetParam();
162     SCOPED_TRACE(ei.pattern);
163 
164     if (ei.ext.flags) {
165         // This is an extparam test, skip it.
166         return;
167     }
168 
169     hs_expr_info_t *info = nullptr;
170     hs_compile_error_t *c_err = nullptr;
171     hs_error_t err =
172         hs_expression_ext_info(ei.pattern, 0, nullptr, &info, &c_err);
173     ASSERT_EQ(HS_SUCCESS, err);
174     ASSERT_TRUE(info != nullptr);
175     ASSERT_TRUE(c_err == nullptr);
176 
177     check_info(ei, info);
178     free(info);
179 }
180 
181 static const hs_expr_ext NO_EXT_PARAM = { 0, 0, 0, 0, 0, 0 };
182 
183 static const expected_info ei_test[] = {
184     {"abc", NO_EXT_PARAM, 3, 3, 0, 0, 0},
185     {"abc.*def", NO_EXT_PARAM, 6, UINT_MAX, 0, 0, 0},
186     {"abc|defghi", NO_EXT_PARAM, 3, 6, 0, 0, 0},
187     {"abc(def)?", NO_EXT_PARAM, 3, 6, 0, 0, 0},
188     {"abc(def){0,3}", NO_EXT_PARAM, 3, 12, 0, 0, 0},
189     {"abc(def){1,4}", NO_EXT_PARAM, 6, 15, 0, 0, 0},
190     {"", NO_EXT_PARAM, 0, 0, 0, 0, 0},
191     {"^", NO_EXT_PARAM, 0, 0, 0, 0, 0},
192     {"^\\b", NO_EXT_PARAM, 0, 0, 1, 0, 0},
193     {"\\b$", NO_EXT_PARAM, 0, 0, 1, 1, 1},
194     {"(?m)\\b$", NO_EXT_PARAM, 0, 0, 1, 1, 0},
195     {"\\A", NO_EXT_PARAM, 0, 0, 0, 0, 0},
196     {"\\z", NO_EXT_PARAM, 0, 0, 0, 1, 1},
197     {"\\Z", NO_EXT_PARAM, 0, 0, 1, 1, 1},
198     {"$", NO_EXT_PARAM, 0, 0, 1, 1, 1},
199     {"(?m)$", NO_EXT_PARAM, 0, 0, 1, 1, 0},
200     {"^foo", NO_EXT_PARAM, 3, 3, 0, 0, 0},
201     {"^foo.*bar", NO_EXT_PARAM, 6, UINT_MAX, 0, 0, 0},
202     {"^foo.*bar?", NO_EXT_PARAM, 5, UINT_MAX, 0, 0, 0},
203     {"^foo.*bar$", NO_EXT_PARAM, 6, UINT_MAX, 1, 1, 1},
204     {"^foobar$", NO_EXT_PARAM, 6, 6, 1, 1, 1},
205     {"foobar$", NO_EXT_PARAM, 6, 6, 1, 1, 1},
206     {"^.*foo", NO_EXT_PARAM, 3, UINT_MAX, 0, 0, 0},
207     {"foo\\b", NO_EXT_PARAM, 3, 3, 1, 1, 0},
208     {"foo.{1,13}bar", NO_EXT_PARAM, 7, 19, 0, 0, 0},
209     {"foo.{10,}bar", NO_EXT_PARAM, 16, UINT_MAX, 0, 0, 0},
210     {"foo.{0,10}bar", NO_EXT_PARAM, 6, 16, 0, 0, 0},
211     {"foo.{,10}bar", NO_EXT_PARAM, 12, 12, 0, 0, 0},
212     {"foo.{10}bar", NO_EXT_PARAM, 16, 16, 0, 0, 0},
213     {"(^|\n)foo", NO_EXT_PARAM, 3, 4, 0, 0, 0},
214     {"(^\n|)foo", NO_EXT_PARAM, 3, 4, 0, 0, 0},
215     {"(?m)^foo", NO_EXT_PARAM, 3, 3, 0, 0, 0},
216     {"\\bfoo", NO_EXT_PARAM, 3, 3, 0, 0, 0},
217     {"^\\bfoo", NO_EXT_PARAM, 3, 3, 0, 0, 0},
218     {"(?m)^\\bfoo", NO_EXT_PARAM, 3, 3, 0, 0, 0},
219     {"\\Bfoo", NO_EXT_PARAM, 3, 3, 0, 0, 0},
220     {"(foo|bar\\z)", NO_EXT_PARAM, 3, 3, 0, 1, 0},
221     {"(foo|bar)\\z", NO_EXT_PARAM, 3, 3, 0, 1, 1},
222 
223     // Some cases with extended parameters.
224     {"^abc.*def", {HS_EXT_FLAG_MAX_OFFSET, 0, 10, 0, 0, 0}, 6, 10, 0, 0, 0},
225     {"^abc.*def", {HS_EXT_FLAG_MIN_LENGTH, 0, 0, 100, 0, 0}, 100, UINT_MAX, 0, 0, 0},
226     {"abc.*def", {HS_EXT_FLAG_MAX_OFFSET, 0, 10, 0, 0, 0}, 6, 10, 0, 0, 0},
227     {"abc.*def", {HS_EXT_FLAG_MIN_LENGTH, 0, 0, 100, 0, 0}, 100, UINT_MAX, 0, 0, 0},
228     {"abc.*def", {HS_EXT_FLAG_MIN_LENGTH, 0, 0, 5, 0, 0}, 6, UINT_MAX, 0, 0, 0},
229 
230     {"abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE, 0, 0, 0, 1, 0}, 5, UINT_MAX, 0, 0, 0},
231     {"abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE, 0, 0, 0, 2, 0}, 4, UINT_MAX, 0, 0, 0},
232     {"abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MIN_LENGTH, 0, 0, 10, 2, 0},
233                 10, UINT_MAX, 0, 0, 0},
234     {"abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MIN_OFFSET, 6, 0, 0, 2, 0},
235                 4, UINT_MAX, 0, 0, 0},
236     {"abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MAX_OFFSET, 0, 6, 0, 2, 0},
237                 4, 6, 0, 0, 0},
238 
239     {"^abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE, 0, 0, 0, 1, 0}, 5, UINT_MAX, 0, 0, 0},
240     {"^abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE, 0, 0, 0, 2, 0}, 4, UINT_MAX, 0, 0, 0},
241     {"^abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MIN_LENGTH, 0, 0, 10, 2, 0},
242                 10, UINT_MAX, 0, 0, 0},
243     {"^abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MIN_OFFSET, 6, 0, 0, 2, 0},
244                 4, UINT_MAX, 0, 0, 0},
245     {"^abc.*def", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MAX_OFFSET, 0, 6, 0, 2, 0},
246                 4, 6, 0, 0, 0},
247 
248     {"^abcdef", {HS_EXT_FLAG_EDIT_DISTANCE, 0, 0, 0, 1, 0}, 5, 7, 0, 0, 0},
249     {"^abcdef", {HS_EXT_FLAG_EDIT_DISTANCE, 0, 0, 0, 2, 0}, 4, 8, 0, 0, 0},
250     {"^abcdef", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MIN_LENGTH, 0, 0, 8, 2, 0},
251                 8, 8, 0, 0, 0},
252     {"^abcdef", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MIN_OFFSET, 6, 0, 0, 2, 0},
253                 4, 8, 0, 0, 0},
254     {"^abcdef", {HS_EXT_FLAG_EDIT_DISTANCE | HS_EXT_FLAG_MAX_OFFSET, 0, 6, 0, 2, 0},
255                 4, 6, 0, 0, 0},
256 
257     {"abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 1}, 6, UINT_MAX, 0, 0, 0},
258     {"abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 2}, 6, UINT_MAX, 0, 0, 0},
259     {"abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 5}, 6, UINT_MAX, 0, 0, 0},
260     {"abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MIN_LENGTH, 0, 0, 10, 0, 2},
261                 10, UINT_MAX, 0, 0, 0},
262     {"abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MIN_OFFSET, 6, 0, 0, 0, 2},
263                 6, UINT_MAX, 0, 0, 0},
264     {"abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MAX_OFFSET, 0, 6, 0, 0, 2},
265                 6, 6, 0, 0, 0},
266 
267     {"^abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 1}, 6, UINT_MAX, 0, 0, 0},
268     {"^abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 2}, 6, UINT_MAX, 0, 0, 0},
269     {"^abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 5}, 6, UINT_MAX, 0, 0, 0},
270     {"^abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MIN_LENGTH, 0, 0, 10, 0, 2},
271                 10, UINT_MAX, 0, 0, 0},
272     {"^abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MIN_OFFSET, 6, 0, 0, 0, 2},
273                 6, UINT_MAX, 0, 0, 0},
274     {"^abc.*def", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MAX_OFFSET, 0, 6, 0, 0, 2},
275                 6, 6, 0, 0, 0},
276 
277     {"^abcdef", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 1}, 6, 6, 0, 0, 0},
278     {"^abcdef", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 2}, 6, 6, 0, 0, 0},
279     {"^abcdef", {HS_EXT_FLAG_HAMMING_DISTANCE, 0, 0, 0, 0, 5}, 6, 6, 0, 0, 0},
280     {"^abcdef", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MIN_LENGTH, 0, 0, 6, 0, 2},
281                 6, 6, 0, 0, 0},
282     {"^abcdef", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MIN_OFFSET, 6, 0, 0, 0, 2},
283                 6, 6, 0, 0, 0},
284     {"^abcdef", {HS_EXT_FLAG_HAMMING_DISTANCE | HS_EXT_FLAG_MAX_OFFSET, 0, 6, 0, 0, 2},
285                 6, 6, 0, 0, 0},
286 };
287 
288 INSTANTIATE_TEST_CASE_P(ExprInfo, ExprInfop, ValuesIn(ei_test));
289 
290 }
291