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