Line data Source code
1 : #include "passgen/parser/parser.h"
2 :
3 : #include <stdbool.h>
4 : #include <stddef.h>
5 : #include <stdint.h>
6 : #include <stdlib.h>
7 :
8 : #include "passgen/container/stack.h"
9 : #include "passgen/pattern/group.h"
10 : #include "passgen/pattern/literal.h"
11 : #include "passgen/pattern/pattern.h"
12 : #include "passgen/pattern/range.h"
13 : #include "passgen/pattern/repeat.h"
14 : #include "passgen/pattern/segment.h"
15 : #include "passgen/pattern/segment_item.h"
16 : #include "passgen/pattern/set.h"
17 :
18 : int passgen_parse_group(
19 : struct passgen_parser *parser,
20 : struct passgen_token *token,
21 : passgen_parser_state *state);
22 :
23 : int passgen_parse_multiplier(
24 : struct passgen_parser *parser,
25 : struct passgen_token *token,
26 : passgen_parser_state *state);
27 :
28 : int passgen_parse_set(
29 : struct passgen_parser *parser,
30 : struct passgen_token *token,
31 : passgen_parser_state *state);
32 :
33 : int passgen_parse_set_range(
34 : struct passgen_parser *parser,
35 : struct passgen_token *token,
36 : passgen_parser_state *state);
37 :
38 : int passgen_parse_repeat(
39 : struct passgen_parser *parser,
40 : struct passgen_token *token,
41 : passgen_parser_state *state);
42 :
43 : int passgen_parse_repeat_range(
44 : struct passgen_parser *parser,
45 : struct passgen_token *token,
46 : passgen_parser_state *state);
47 :
48 : int passgen_parse_special(
49 : struct passgen_parser *parser,
50 : struct passgen_token *token,
51 : passgen_parser_state *state);
52 :
53 : int passgen_parse_special_name(
54 : struct passgen_parser *parser,
55 : struct passgen_token *token,
56 : passgen_parser_state *state);
57 :
58 39712 : inline passgen_parser_state *passgen_parser_state_push(passgen_parser *parser) {
59 39712 : return passgen_stack_push(&parser->state, NULL);
60 : }
61 :
62 33333 : passgen_parser_state *passgen_parser_state_push_group(
63 : passgen_parser *parser,
64 : passgen_pattern_group *group,
65 : passgen_pattern_segment *segment) {
66 33333 : passgen_parser_state *state = passgen_parser_state_push(parser);
67 33333 : state->type = PASSGEN_PARSER_GROUP;
68 33333 : state->data.group.group = group;
69 33333 : state->data.group.segment = segment;
70 :
71 33333 : return state;
72 : }
73 :
74 3123 : passgen_parser_state *passgen_parser_state_push_set(
75 : passgen_parser *parser,
76 : passgen_pattern_set *set,
77 : passgen_pattern_range *range) {
78 3123 : passgen_parser_state *state = passgen_parser_state_push(parser);
79 3123 : state->type = PASSGEN_PARSER_SET;
80 3123 : state->data.set.set = set;
81 3123 : state->data.set.range = range;
82 :
83 3123 : return state;
84 : }
85 :
86 2621 : passgen_parser_state *passgen_parser_state_push_repeat(
87 : passgen_parser *parser,
88 : passgen_pattern_repeat *repeat) {
89 2621 : passgen_parser_state *state = passgen_parser_state_push(parser);
90 2621 : state->type = PASSGEN_PARSER_REPEAT;
91 2621 : repeat->min = 0;
92 2621 : repeat->max = 0;
93 2621 : state->data.repeat.repeat = repeat;
94 :
95 2621 : return state;
96 : }
97 :
98 518 : passgen_parser_state *passgen_parser_state_push_multiplier(
99 : passgen_parser *parser,
100 : size_t *multiplier,
101 : size_t *sum) {
102 518 : passgen_parser_state *state = passgen_parser_state_push(parser);
103 518 : state->type = PASSGEN_PARSER_MULTIPLIER;
104 518 : *multiplier = 0;
105 518 : state->data.multiplier.value = multiplier;
106 518 : state->data.multiplier.sum = sum;
107 518 : return state;
108 : }
109 :
110 117 : passgen_parser_state *passgen_parser_state_push_special(
111 : passgen_parser *parser,
112 : passgen_pattern_special *special) {
113 117 : passgen_parser_state *state = passgen_parser_state_push(parser);
114 117 : state->type = PASSGEN_PARSER_SPECIAL;
115 117 : state->data.special.special = special;
116 117 : return state;
117 : }
118 :
119 30154 : void passgen_parser_init(passgen_parser *parser, passgen_pattern *pattern) {
120 30154 : passgen_stack_init(&parser->state, sizeof(passgen_parser_state));
121 30154 : parser->limit = 0;
122 30154 : parser->pattern = pattern;
123 30154 : if(!pattern) {
124 0 : parser->pattern = malloc(sizeof(passgen_pattern));
125 : }
126 30154 : passgen_pattern_init(parser->pattern);
127 60308 : passgen_parser_state_push_group(
128 : parser,
129 30154 : &parser->pattern->group,
130 30154 : passgen_pattern_group_segment_append(&parser->pattern->group));
131 30154 : }
132 :
133 30154 : passgen_pattern *passgen_parser_free(passgen_parser *parser) {
134 30154 : passgen_stack_free(&parser->state);
135 30154 : passgen_pattern *pattern = parser->pattern;
136 30154 : parser->pattern = NULL;
137 30154 : return pattern;
138 : }
139 :
140 : passgen_parser_state *
141 0 : passgen_parser_state_get(passgen_parser *parser, size_t n) {
142 0 : return passgen_stack_get(&parser->state, n);
143 : }
144 :
145 351895 : passgen_parser_state *passgen_parser_state_last(passgen_parser *parser) {
146 351895 : return passgen_stack_top(&parser->state);
147 : }
148 :
149 : // get the last item, making sure that it's only a single character.
150 : // in case of characters, mark it as tainted.
151 : static inline passgen_pattern_item *
152 4997 : last_single_item_taint(passgen_pattern_segment *segment) {
153 4997 : passgen_pattern_item *item = passgen_stack_top(&segment->items);
154 :
155 4997 : if(!item) {
156 713 : return NULL;
157 : }
158 :
159 4284 : if(item->kind == PASSGEN_PATTERN_LITERAL) {
160 4259 : if(item->data.literal.count > 1) {
161 : // save last codepoint
162 3275 : int32_t codepoint =
163 3275 : item->data.literal.codepoints[item->data.literal.count - 1];
164 :
165 : // trim codepoints
166 3275 : item->data.literal.count -= 1;
167 :
168 : // create new item
169 3275 : item = passgen_pattern_segment_new_item(segment);
170 3275 : item->kind = PASSGEN_PATTERN_LITERAL;
171 3275 : passgen_pattern_literal_init(&item->data.literal);
172 3275 : passgen_pattern_literal_append(&item->data.literal, codepoint);
173 : }
174 :
175 : // characters are always marked as tainted.
176 4259 : passgen_pattern_literal_taint(&item->data.literal);
177 : }
178 :
179 4284 : return item;
180 : }
181 :
182 342362 : int passgen_parse_token(passgen_parser *parser, passgen_token *token) {
183 342362 : passgen_parser_state *state = passgen_parser_state_last(parser);
184 :
185 342362 : if(parser->limit && parser->state.len >= parser->limit) {
186 1 : return -1;
187 : }
188 :
189 342361 : switch(state->type) {
190 317941 : case PASSGEN_PARSER_GROUP:
191 317941 : return passgen_parse_group(parser, token, state);
192 688 : case PASSGEN_PARSER_MULTIPLIER:
193 688 : return passgen_parse_multiplier(parser, token, state);
194 20473 : case PASSGEN_PARSER_SET:
195 20473 : return passgen_parse_set(parser, token, state);
196 102 : case PASSGEN_PARSER_SET_RANGE:
197 102 : return passgen_parse_set_range(parser, token, state);
198 2781 : case PASSGEN_PARSER_REPEAT:
199 2781 : return passgen_parse_repeat(parser, token, state);
200 64 : case PASSGEN_PARSER_REPEAT_RANGE:
201 64 : return passgen_parse_repeat_range(parser, token, state);
202 110 : case PASSGEN_PARSER_SPECIAL:
203 110 : return passgen_parse_special(parser, token, state);
204 202 : case PASSGEN_PARSER_SPECIAL_NAME:
205 202 : return passgen_parse_special_name(parser, token, state);
206 0 : default:
207 0 : return -1;
208 : }
209 : }
210 :
211 327474 : static void passgen_pattern_segment_clean(passgen_pattern_segment *segment) {
212 327474 : if(segment->items.len > 0) {
213 : // get last item
214 291176 : passgen_pattern_item *last = passgen_stack_top(&segment->items);
215 :
216 291176 : if(last->kind == PASSGEN_PATTERN_GROUP &&
217 336 : last->data.group.multiplier_sum == 0) {
218 135 : passgen_pattern_group_free(&last->data.group);
219 135 : passgen_stack_pop(&segment->items, NULL);
220 : }
221 : }
222 327474 : }
223 :
224 317941 : int passgen_parse_group(
225 : passgen_parser *parser,
226 : passgen_token *token,
227 : passgen_parser_state *state) {
228 317941 : uint32_t codepoint = token->codepoint;
229 : passgen_pattern_group *group;
230 : passgen_pattern_special *special;
231 : passgen_pattern_item *item;
232 :
233 317941 : passgen_pattern_segment_clean(state->data.group.segment);
234 :
235 317941 : if(codepoint & PASSGEN_TOKEN_ESCAPED_BIT) {
236 1906 : codepoint &= ~PASSGEN_TOKEN_ESCAPED_BIT;
237 1906 : switch((char) codepoint) {
238 277 : case '|':
239 : case '(':
240 : case ')':
241 : case '{':
242 : case '}':
243 : case '[':
244 : case ']':
245 : // escaped token which would normally do something but
246 : // should be treated as text
247 277 : break;
248 117 : case 'm':
249 : case 'p':
250 : case 'w':
251 : // special token
252 117 : special = passgen_pattern_segment_new_special(
253 : state->data.group.segment);
254 117 : passgen_pattern_special_init(special, (char) codepoint);
255 117 : passgen_parser_state_push_special(parser, special);
256 117 : return 0;
257 1512 : default:
258 : // error
259 1512 : return -1;
260 : }
261 : } else {
262 316035 : switch((char) codepoint) {
263 3193 : case '|':
264 3193 : if(state->data.group.segment->multiplier > 0) {
265 : // create new segment and parser state
266 3093 : state->data.group.segment =
267 3093 : passgen_pattern_group_segment_append(
268 : state->data.group.group);
269 : } else {
270 : // if the previous segment had a zero multiplier, recycle it
271 100 : passgen_pattern_segment_free(state->data.group.segment);
272 100 : passgen_pattern_segment_init(state->data.group.segment);
273 : }
274 3193 : return 0;
275 3211 : case ')':
276 3211 : if(state->data.group.segment->multiplier == 0) {
277 2 : passgen_pattern_segment_free(state->data.group.segment);
278 2 : passgen_stack_pop(&state->data.group.group->segments, NULL);
279 : }
280 3211 : if(parser->state.len <= 1) {
281 2881 : return -1;
282 : }
283 330 : passgen_pattern_group_finish(state->data.group.group);
284 330 : passgen_stack_pop(&parser->state, NULL);
285 330 : return 0;
286 3179 : case '(':
287 : // we're supposed to read something in.
288 3179 : group = passgen_pattern_segment_new_group(
289 : state->data.group.segment);
290 3179 : passgen_parser_state_push_group(
291 : parser,
292 : group,
293 : passgen_pattern_group_segment_append(group));
294 3179 : return 0;
295 3123 : case '[':
296 3123 : passgen_parser_state_push_set(
297 : parser,
298 : passgen_pattern_segment_new_set(state->data.group.segment),
299 : NULL);
300 3123 : return 0;
301 3139 : case '{':
302 3139 : item = last_single_item_taint(state->data.group.segment);
303 : // error, there was no item
304 3139 : if(item) {
305 2621 : passgen_parser_state_push_repeat(parser, &item->repeat);
306 2621 : return 0;
307 : } else {
308 518 : state->data.group.segment->multiplier = 0;
309 518 : state->data.group.group->multiplier_sum -= 1;
310 518 : passgen_parser_state_push_multiplier(
311 : parser,
312 518 : &state->data.group.segment->multiplier,
313 518 : &state->data.group.group->multiplier_sum);
314 518 : return 0;
315 : }
316 1858 : case '?':
317 1858 : item = last_single_item_taint(state->data.group.segment);
318 1858 : if(item) {
319 1663 : item->maybe = true;
320 1663 : return 0;
321 : } else {
322 : // error: maybe without a previous item
323 195 : return -1;
324 : }
325 298332 : default:
326 298332 : break;
327 : }
328 : }
329 :
330 : // check if the last item was a character that we can add this one to
331 298609 : if(state->data.group.segment->items.len) {
332 : passgen_pattern_item *last =
333 266130 : passgen_stack_top(&state->data.group.segment->items);
334 :
335 266130 : if(last->kind == PASSGEN_PATTERN_LITERAL) {
336 265817 : if(0 ==
337 265817 : passgen_pattern_literal_append(&last->data.literal, codepoint)) {
338 236408 : return 0;
339 : }
340 : }
341 : }
342 :
343 : passgen_pattern_literal *literal =
344 62201 : passgen_pattern_segment_new_char(state->data.group.segment);
345 62201 : passgen_pattern_literal_append(literal, codepoint);
346 :
347 62201 : return 0;
348 : }
349 :
350 20473 : int passgen_parse_set(
351 : passgen_parser *parser,
352 : passgen_token *token,
353 : passgen_parser_state *state) {
354 20473 : passgen_pattern_set *set = state->data.set.set;
355 :
356 : // this set's over
357 20473 : if(token->codepoint == ']') {
358 : // compute sum of choices and choices list for binary search.
359 276 : size_t choices = 0;
360 276 : set->choices_list = malloc(sizeof(size_t) * set->items.len);
361 1280 : for(size_t i = 0; i < set->items.len; i++) {
362 1004 : passgen_pattern_range *range = passgen_stack_get(&set->items, i);
363 1004 : choices += 1 + range->end - range->start;
364 1004 : set->choices_list[i] = choices;
365 : }
366 :
367 276 : passgen_stack_pop(&parser->state, NULL);
368 276 : return 0;
369 : }
370 :
371 : // part of a range expression
372 20197 : if(state->data.set.range && token->codepoint == '-') {
373 116 : state->type = PASSGEN_PARSER_SET_RANGE;
374 116 : return 0;
375 : }
376 :
377 20081 : passgen_pattern_range *range = passgen_pattern_set_range_append(set);
378 :
379 20081 : range->start = token->codepoint & ~PASSGEN_TOKEN_ESCAPED_BIT;
380 20081 : range->end = token->codepoint & ~PASSGEN_TOKEN_ESCAPED_BIT;
381 :
382 20081 : state->data.set.range = range;
383 :
384 20081 : return 0;
385 : }
386 :
387 102 : int passgen_parse_set_range(
388 : passgen_parser *parser,
389 : passgen_token *token,
390 : passgen_parser_state *state) {
391 : (void) parser;
392 102 : if(token->codepoint == ']') {
393 2 : return -1;
394 : }
395 :
396 100 : if(token->codepoint < state->data.set.range->start) {
397 40 : return -1;
398 : }
399 :
400 60 : state->data.set.range->end = token->codepoint;
401 60 : state->type = PASSGEN_PARSER_SET;
402 :
403 60 : return 0;
404 : }
405 :
406 688 : int passgen_parse_multiplier(
407 : passgen_parser *parser,
408 : passgen_token *token,
409 : passgen_parser_state *state) {
410 688 : if(token->codepoint == '}') {
411 116 : *state->data.multiplier.sum += *state->data.multiplier.value;
412 116 : passgen_stack_pop(&parser->state, NULL);
413 116 : return 0;
414 : }
415 :
416 572 : if(token->codepoint >= '0' && token->codepoint <= '9') {
417 194 : uint8_t digit = token->codepoint - '0';
418 :
419 194 : *state->data.multiplier.value *= 10;
420 194 : *state->data.multiplier.value += digit;
421 :
422 194 : return 0;
423 : }
424 :
425 378 : return -1;
426 : }
427 :
428 2781 : int passgen_parse_repeat(
429 : passgen_parser *parser,
430 : passgen_token *token,
431 : passgen_parser_state *state) {
432 : // this set's over
433 2781 : if(token->codepoint == '}') {
434 59 : state->data.repeat.repeat->max = state->data.repeat.repeat->min;
435 59 : passgen_stack_pop(&parser->state, NULL);
436 59 : return 0;
437 : }
438 :
439 2722 : if(token->codepoint == ',') {
440 50 : state->data.repeat.repeat->max = 0;
441 50 : state->type = PASSGEN_PARSER_REPEAT_RANGE;
442 50 : return 0;
443 : }
444 :
445 2672 : if(token->codepoint >= '0' && token->codepoint <= '9') {
446 406 : uint8_t digit = token->codepoint - '0';
447 :
448 406 : state->data.repeat.repeat->min *= 10;
449 406 : state->data.repeat.repeat->min += digit;
450 :
451 406 : return 0;
452 : }
453 :
454 2266 : return -1;
455 : }
456 :
457 64 : int passgen_parse_repeat_range(
458 : passgen_parser *parser,
459 : passgen_token *token,
460 : passgen_parser_state *state) {
461 64 : if(token->codepoint == '}') {
462 9 : passgen_stack_pop(&parser->state, NULL);
463 9 : return 0;
464 : }
465 :
466 55 : if(token->codepoint >= '0' && token->codepoint <= '9') {
467 21 : uint8_t digit = token->codepoint - '0';
468 :
469 21 : state->data.repeat.repeat->max *= 10;
470 21 : state->data.repeat.repeat->max += digit;
471 :
472 21 : return 0;
473 : }
474 :
475 34 : return -1;
476 : }
477 :
478 110 : int passgen_parse_special(
479 : passgen_parser *parser,
480 : passgen_token *token,
481 : passgen_parser_state *state) {
482 : (void) parser;
483 :
484 110 : if(token->codepoint == '{') {
485 11 : state->type = PASSGEN_PARSER_SPECIAL_NAME;
486 11 : return 0;
487 : }
488 :
489 99 : return -1;
490 : }
491 :
492 202 : int passgen_parse_special_name(
493 : passgen_parser *parser,
494 : passgen_token *token,
495 : passgen_parser_state *state) {
496 : (void) parser;
497 :
498 202 : if(token->codepoint == '}') {
499 9 : passgen_stack_pop(&parser->state, NULL);
500 : } else {
501 193 : passgen_pattern_special_push(
502 : state->data.special.special,
503 193 : token->codepoint & ~PASSGEN_TOKEN_ESCAPED_BIT);
504 : }
505 :
506 202 : return 0;
507 : }
508 :
509 13563 : int passgen_parse_finish(passgen_parser *parser) {
510 : // make sure we just have one state on the stack, the initial one.
511 13563 : if(parser->state.len != 1) {
512 4030 : return -1;
513 : }
514 :
515 : // make sure last state is a group
516 9533 : passgen_parser_state *state = passgen_parser_state_last(parser);
517 9533 : if(state->type != PASSGEN_PARSER_GROUP) {
518 0 : return -1;
519 : }
520 :
521 : // clean last state
522 9533 : passgen_pattern_segment_clean(state->data.group.segment);
523 :
524 9533 : return 0;
525 : }
526 :
527 10000 : int passgen_parser_unicode(
528 : passgen_parser *parser,
529 : uint32_t *data,
530 : size_t length) {
531 10000 : passgen_token_parser token_parser = {0};
532 10000 : passgen_token token = {0};
533 : int ret;
534 :
535 160090 : for(size_t pos = 0; pos < length; pos++) {
536 151193 : ret = passgen_token_parse(&token_parser, &token, 1, data[pos]);
537 :
538 151193 : if(ret == PASSGEN_TOKEN_INIT) {
539 151193 : ret = passgen_parse_token(parser, &token);
540 :
541 151193 : if(ret != 0) {
542 1103 : return ret;
543 : }
544 : }
545 : }
546 :
547 8897 : return 0;
548 : }
|
