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 #include "config.h"
30 #include <algorithm>
31 #include <string>
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 
matchesOrdered(const vector<MatchRecord> & matches)43 bool matchesOrdered(const vector<MatchRecord> &matches) {
44     unsigned long lastMatch = 0;
45     for (vector<MatchRecord>::const_iterator it = matches.begin();
46          it != matches.end(); ++it) {
47         if (lastMatch > it->to) {
48             return false;
49         }
50         lastMatch = it->to;
51     }
52     return true;
53 }
54 
countMatchesById(const vector<MatchRecord> & matches,int id)55 unsigned countMatchesById(const vector<MatchRecord> &matches, int id) {
56     unsigned count = 0;
57     for (vector<MatchRecord>::const_iterator it = matches.begin();
58          it != matches.end(); ++it) {
59         if (id == it->id) {
60             count++;
61         }
62     }
63     return count;
64 }
65 
TEST(order,ordering1)66 TEST(order, ordering1) {
67     vector<pattern> patterns;
68     patterns.push_back(pattern("aa", HS_FLAG_DOTALL, 1));
69     patterns.push_back(pattern("aa.", HS_FLAG_DOTALL, 2));
70     patterns.push_back(pattern("aa..", HS_FLAG_DOTALL, 3));
71     patterns.push_back(pattern("^.{0,4}aa..", HS_FLAG_DOTALL, 4));
72     patterns.push_back(pattern("^.{0,4}aa", HS_FLAG_DOTALL, 5));
73 
74     const char *data = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
75 
76     hs_database_t *db = buildDB(patterns, HS_MODE_NOSTREAM);
77     ASSERT_NE(nullptr, db);
78 
79     hs_scratch_t *scratch = nullptr;
80     hs_error_t err = hs_alloc_scratch(db, &scratch);
81     ASSERT_EQ(HS_SUCCESS, err);
82 
83     CallBackContext c;
84     err = hs_scan(db, data, strlen(data), 0, scratch, record_cb,
85                   (void *)&c);
86     ASSERT_EQ(HS_SUCCESS, err);
87 
88     EXPECT_EQ(31U, countMatchesById(c.matches, 1));
89     EXPECT_EQ(30U, countMatchesById(c.matches, 2));
90     EXPECT_EQ(29U, countMatchesById(c.matches, 3));
91     EXPECT_EQ(5U, countMatchesById(c.matches, 4));
92     EXPECT_EQ(5U, countMatchesById(c.matches, 5));
93     ASSERT_TRUE(matchesOrdered(c.matches));
94     err = hs_free_scratch(scratch);
95     ASSERT_EQ(HS_SUCCESS, err);
96     hs_free_database(db);
97 }
98 
TEST(order,ordering2)99 TEST(order, ordering2) {
100     vector<pattern> patterns;
101     patterns.push_back(pattern("aa.", HS_FLAG_DOTALL, 2));
102     patterns.push_back(pattern("aa..", HS_FLAG_DOTALL, 3));
103     patterns.push_back(pattern("^.{0,4}aa..", HS_FLAG_DOTALL, 4));
104     patterns.push_back(pattern("^.{0,4}aa", HS_FLAG_DOTALL, 5));
105 
106     const char *data = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
107 
108     hs_database_t *db = buildDB(patterns, HS_MODE_NOSTREAM);
109     ASSERT_NE(nullptr, db);
110 
111     hs_scratch_t *scratch = nullptr;
112     hs_error_t err = hs_alloc_scratch(db, &scratch);
113     ASSERT_EQ(HS_SUCCESS, err);
114 
115     CallBackContext c;
116     err = hs_scan(db, data, strlen(data), 0, scratch, record_cb,
117                   (void *)&c);
118     ASSERT_EQ(HS_SUCCESS, err);
119 
120     EXPECT_EQ(0U, countMatchesById(c.matches, 1));
121     EXPECT_EQ(30U, countMatchesById(c.matches, 2));
122     EXPECT_EQ(29U, countMatchesById(c.matches, 3));
123     EXPECT_EQ(5U, countMatchesById(c.matches, 4));
124     EXPECT_EQ(5U, countMatchesById(c.matches, 5));
125     ASSERT_TRUE(matchesOrdered(c.matches));
126     err = hs_free_scratch(scratch);
127     ASSERT_EQ(HS_SUCCESS, err);
128     hs_free_database(db);
129 }
130 
TEST(order,ordering3)131 TEST(order, ordering3) {
132     vector<pattern> patterns;
133     patterns.push_back(pattern("aa.", HS_FLAG_DOTALL, 2));
134     patterns.push_back(pattern("aa..", HS_FLAG_DOTALL, 3));
135     patterns.push_back(pattern("^.{0,4}aa..", HS_FLAG_DOTALL, 4));
136 
137     const char *data = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
138 
139     hs_database_t *db = buildDB(patterns, HS_MODE_NOSTREAM);
140     ASSERT_NE(nullptr, db);
141 
142     hs_scratch_t *scratch = nullptr;
143     hs_error_t err = hs_alloc_scratch(db, &scratch);
144     ASSERT_EQ(HS_SUCCESS, err);
145 
146     CallBackContext c;
147     err = hs_scan(db, data, strlen(data), 0, scratch, record_cb,
148                   (void *)&c);
149     ASSERT_EQ(HS_SUCCESS, err);
150 
151     EXPECT_EQ(0U, countMatchesById(c.matches, 1));
152     EXPECT_EQ(30U, countMatchesById(c.matches, 2));
153     EXPECT_EQ(29U, countMatchesById(c.matches, 3));
154     EXPECT_EQ(5U, countMatchesById(c.matches, 4));
155     EXPECT_EQ(0U, countMatchesById(c.matches, 5));
156     ASSERT_TRUE(matchesOrdered(c.matches));
157     err = hs_free_scratch(scratch);
158     ASSERT_EQ(HS_SUCCESS, err);
159     hs_free_database(db);
160 }
161 
TEST(order,ordering4)162 TEST(order, ordering4) {
163     vector<pattern> patterns;
164     patterns.push_back(pattern("aa", HS_FLAG_DOTALL, 1));
165     patterns.push_back(pattern("aa.", HS_FLAG_DOTALL, 2));
166     patterns.push_back(pattern("aa..", HS_FLAG_DOTALL, 3));
167 
168     const char *data = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
169 
170     hs_database_t *db = buildDB(patterns, HS_MODE_NOSTREAM);
171     ASSERT_NE(nullptr, db);
172 
173     hs_scratch_t *scratch = nullptr;
174     hs_error_t err = hs_alloc_scratch(db, &scratch);
175     ASSERT_EQ(HS_SUCCESS, err);
176 
177     CallBackContext c;
178     err = hs_scan(db, data, strlen(data), 0, scratch, record_cb,
179                   (void *)&c);
180     ASSERT_EQ(HS_SUCCESS, err);
181 
182     EXPECT_EQ(31U, countMatchesById(c.matches, 1));
183     EXPECT_EQ(30U, countMatchesById(c.matches, 2));
184     EXPECT_EQ(29U, countMatchesById(c.matches, 3));
185     EXPECT_EQ(0U, countMatchesById(c.matches, 4));
186     EXPECT_EQ(0U, countMatchesById(c.matches, 5));
187     ASSERT_TRUE(matchesOrdered(c.matches));
188     err = hs_free_scratch(scratch);
189     ASSERT_EQ(HS_SUCCESS, err);
190     hs_free_database(db);
191 }
192 
TEST(order,ordering5)193 TEST(order, ordering5) {
194     vector<pattern> patterns;
195     patterns.push_back(pattern("aa", HS_FLAG_DOTALL, 1));
196     patterns.push_back(pattern("aa.", HS_FLAG_DOTALL, 2));
197     patterns.push_back(pattern("aa..", HS_FLAG_DOTALL, 3));
198     patterns.push_back(pattern("^.{0,4}aa..", HS_FLAG_DOTALL, 4));
199     patterns.push_back(pattern("^.{0,4}aa", HS_FLAG_DOTALL, 5));
200 
201     const char *data = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
202 
203     hs_database_t *db = buildDB(patterns, HS_MODE_STREAM);
204     ASSERT_NE(nullptr, db);
205 
206     hs_scratch_t *scratch = nullptr;
207     hs_error_t err = hs_alloc_scratch(db, &scratch);
208     ASSERT_EQ(HS_SUCCESS, err);
209 
210     hs_stream_t *stream = nullptr;
211     CallBackContext c;
212 
213     for (size_t jump = 1; jump <= 8; jump++) {
214         err = hs_open_stream(db, 0, &stream);
215         ASSERT_EQ(HS_SUCCESS, err);
216         ASSERT_TRUE(stream != nullptr);
217 
218         for (unsigned i = 0; i < strlen(data); i += jump) {
219             err = hs_scan_stream(stream, data + i, min(jump, strlen(data) - i),
220                                  0, scratch, record_cb, (void *)&c);
221             ASSERT_EQ(HS_SUCCESS, err);
222         }
223         EXPECT_EQ(31U, countMatchesById(c.matches, 1));
224         EXPECT_EQ(30U, countMatchesById(c.matches, 2));
225         EXPECT_EQ(29U, countMatchesById(c.matches, 3));
226         EXPECT_EQ(5U, countMatchesById(c.matches, 4));
227         EXPECT_EQ(5U, countMatchesById(c.matches, 5));
228         ASSERT_TRUE(matchesOrdered(c.matches));
229         c.matches.clear();
230         hs_close_stream(stream, scratch, record_cb, (void *)&c);
231     }
232     err = hs_free_scratch(scratch);
233     ASSERT_EQ(HS_SUCCESS, err);
234     hs_free_database(db);
235 }
236 
TEST(order,ordering6)237 TEST(order, ordering6) {
238     vector<pattern> patterns;
239     patterns.push_back(pattern("aa.", HS_FLAG_DOTALL, 2));
240     patterns.push_back(pattern("aa..", HS_FLAG_DOTALL, 3));
241     patterns.push_back(pattern("^.{0,4}aa..", HS_FLAG_DOTALL, 4));
242     patterns.push_back(pattern("^.{0,4}aa", HS_FLAG_DOTALL, 5));
243 
244     const char *data = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
245 
246     hs_database_t *db = buildDB(patterns, HS_MODE_STREAM);
247     ASSERT_NE(nullptr, db);
248 
249     hs_scratch_t *scratch = nullptr;
250     hs_error_t err = hs_alloc_scratch(db, &scratch);
251     ASSERT_EQ(HS_SUCCESS, err);
252 
253     hs_stream_t *stream = nullptr;
254     CallBackContext c;
255 
256     for (size_t jump = 1; jump <= 8; jump++) {
257         err = hs_open_stream(db, 0, &stream);
258         ASSERT_EQ(HS_SUCCESS, err);
259         ASSERT_TRUE(stream != nullptr);
260 
261         for (unsigned i = 0; i < strlen(data); i += jump) {
262             err = hs_scan_stream(stream, data + i, min(jump, strlen(data) - i),
263                                  0, scratch, record_cb, (void *)&c);
264             ASSERT_EQ(HS_SUCCESS, err);
265         }
266         EXPECT_EQ(0U, countMatchesById(c.matches, 1));
267         EXPECT_EQ(30U, countMatchesById(c.matches, 2));
268         EXPECT_EQ(29U, countMatchesById(c.matches, 3));
269         EXPECT_EQ(5U, countMatchesById(c.matches, 4));
270         EXPECT_EQ(5U, countMatchesById(c.matches, 5));
271         ASSERT_TRUE(matchesOrdered(c.matches));
272         c.matches.clear();
273         hs_close_stream(stream, scratch, record_cb, (void *)&c);
274     }
275     err = hs_free_scratch(scratch);
276     ASSERT_EQ(HS_SUCCESS, err);
277     hs_free_database(db);
278 }
279 
TEST(order,ordering7)280 TEST(order, ordering7) {
281     vector<pattern> patterns;
282     patterns.push_back(pattern("aa.", HS_FLAG_DOTALL, 2));
283     patterns.push_back(pattern("aa..", HS_FLAG_DOTALL, 3));
284     patterns.push_back(pattern("^.{0,4}aa..", HS_FLAG_DOTALL, 4));
285 
286     const char *data = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
287 
288     hs_database_t *db = buildDB(patterns, HS_MODE_STREAM);
289     ASSERT_NE(nullptr, db);
290 
291     hs_scratch_t *scratch = nullptr;
292     hs_error_t err = hs_alloc_scratch(db, &scratch);
293     ASSERT_EQ(HS_SUCCESS, err);
294 
295     hs_stream_t *stream = nullptr;
296     CallBackContext c;
297 
298     for (size_t jump = 1; jump <= 8; jump++) {
299         err = hs_open_stream(db, 0, &stream);
300         ASSERT_EQ(HS_SUCCESS, err);
301         ASSERT_TRUE(stream != nullptr);
302 
303         for (unsigned i = 0; i < strlen(data); i += jump) {
304             err = hs_scan_stream(stream, data + i, min(jump, strlen(data) - i),
305                                  0, scratch, record_cb, (void *)&c);
306             ASSERT_EQ(HS_SUCCESS, err);
307         }
308         EXPECT_EQ(0U, countMatchesById(c.matches, 1));
309         EXPECT_EQ(30U, countMatchesById(c.matches, 2));
310         EXPECT_EQ(29U, countMatchesById(c.matches, 3));
311         EXPECT_EQ(5U, countMatchesById(c.matches, 4));
312         EXPECT_EQ(0U, countMatchesById(c.matches, 5));
313         ASSERT_TRUE(matchesOrdered(c.matches));
314         c.matches.clear();
315         hs_close_stream(stream, scratch, record_cb, (void *)&c);
316     }
317     err = hs_free_scratch(scratch);
318     ASSERT_EQ(HS_SUCCESS, err);
319     hs_free_database(db);
320 }
321 
TEST(order,ordering8)322 TEST(order, ordering8) {
323     vector<pattern> patterns;
324     patterns.push_back(pattern("aa", HS_FLAG_DOTALL, 1));
325     patterns.push_back(pattern("aa.", HS_FLAG_DOTALL, 2));
326     patterns.push_back(pattern("aa..", HS_FLAG_DOTALL, 3));
327 
328     const char *data = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
329 
330     hs_database_t *db = buildDB(patterns, HS_MODE_STREAM);
331     ASSERT_NE(nullptr, db);
332 
333     hs_scratch_t *scratch = nullptr;
334     hs_error_t err = hs_alloc_scratch(db, &scratch);
335     ASSERT_EQ(HS_SUCCESS, err);
336 
337     hs_stream_t *stream = nullptr;
338     CallBackContext c;
339 
340     for (size_t jump = 1; jump <= 8; jump++) {
341         err = hs_open_stream(db, 0, &stream);
342         ASSERT_EQ(HS_SUCCESS, err);
343         ASSERT_TRUE(stream != nullptr);
344 
345         for (unsigned i = 0; i < strlen(data); i += jump) {
346             err = hs_scan_stream(stream, data + i, min(jump, strlen(data) - i),
347                                  0, scratch, record_cb, (void *)&c);
348             ASSERT_EQ(HS_SUCCESS, err);
349         }
350         EXPECT_EQ(31U, countMatchesById(c.matches, 1));
351         EXPECT_EQ(30U, countMatchesById(c.matches, 2));
352         EXPECT_EQ(29U, countMatchesById(c.matches, 3));
353         EXPECT_EQ(0U, countMatchesById(c.matches, 4));
354         EXPECT_EQ(0U, countMatchesById(c.matches, 5));
355         ASSERT_TRUE(matchesOrdered(c.matches));
356         c.matches.clear();
357         hs_close_stream(stream, scratch, record_cb, (void *)&c);
358     }
359     err = hs_free_scratch(scratch);
360     ASSERT_EQ(HS_SUCCESS, err);
361     hs_free_database(db);
362 }
363 
364 }
365