Line data Source code
1 : /* Copyright 2017 noseglasses <shinynoseglasses@gmail.com>
2 : *
3 : * This program is free software: you can redistribute it and/or modify
4 : * it under the terms of the GNU Lesser General Public License as published by
5 : * the Free Software Foundation, either version 3 of the License, or
6 : * (at your option) any later version.
7 : *
8 : * This program is distributed in the hope that it will be useful,
9 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 : * GNU Lesser General Public License for more details.
12 : *
13 : * You should have received a copy of the GNU Lesser General Public License
14 : * along with this program. If not, see <http://www.gnu.org/licenses/>.
15 : */
16 : #include "ppg_event.h"
17 : #include "detail/ppg_context_detail.h"
18 : #include "detail/ppg_global_detail.h"
19 : #include "detail/ppg_furcation_detail.h"
20 : #include "detail/ppg_event_buffer_detail.h"
21 : #include "detail/ppg_signal_detail.h"
22 : #include "ppg_debug.h"
23 : #include "ppg_bitfield.h"
24 :
25 : enum {
26 : PPG_Pattern_State_Undefined = 0,
27 : PPG_Pattern_Matches,
28 : PPG_Pattern_Invalid,
29 : PPG_Pattern_Orphaned_Deactivation,
30 : PPG_Pattern_In_Progress,
31 : PPG_Pattern_Branch_Reversion
32 : };
33 :
34 560 : static void ppg_branch_prepare(PPG_Token__ *branch_token)
35 : {
36 560 : PPG_LOG("Preparing branch token 0x%" PRIXPTR "\n",
37 : (uintptr_t)branch_token);
38 :
39 560 : PPG_CALL_VIRT_METHOD(branch_token, reset);
40 :
41 1224 : for(PPG_Count i = 0; i < branch_token->n_children; ++i) {
42 664 : ppg_token_reset_control_state(branch_token->children[i]);
43 : }
44 560 : }
45 :
46 0 : PPG_Token__ * ppg_branch_find_root(
47 : PPG_Token__ *cur_token,
48 : PPG_Token__ *end_token)
49 : {
50 0 : PPG_Token__ *branch_root = cur_token;
51 :
52 : // Unwind and cleanup back to the current furcation or to the
53 : // root node
54 : //
55 0 : while(cur_token != end_token) {
56 :
57 0 : branch_root = cur_token;
58 :
59 0 : cur_token = cur_token->parent;
60 : }
61 :
62 0 : return branch_root;
63 : }
64 :
65 150 : static PPG_Token__ *ppg_furcation_revert(void)
66 : {
67 : // If there is no current furcation, we at least clean up to
68 : // the root node. Otherwise we cleanup to the current furcation.
69 : //
70 150 : PPG_Token__ *furcation_token = NULL;
71 :
72 : while(1) {
73 :
74 : #if PPG_HAVE_STATISTICS
75 : ++ppg_context->statistics.n_reversions;
76 : #endif
77 :
78 : furcation_token
79 182 : = (PPG_FB.cur_furcation == -1) ? NULL : PPG_CUR_FUR.token;
80 :
81 182 : PPG_LOG("Reverting to furcation token 0x%" PRIXPTR "\n",
82 : (uintptr_t)furcation_token);
83 :
84 : // If there is no current furcation, we can't do anything else
85 : //
86 182 : if(!furcation_token) {
87 :
88 52 : PPG_LOG(" No furcation found\n");
89 :
90 : // By returning NULL we signal that there is no
91 : // reversion to another furcation possible.
92 : //
93 52 : return NULL;
94 : }
95 :
96 : // If we already tried all possible branches of the current furcation
97 : //
98 130 : if(PPG_CUR_FUR.n_branch_candidates <= 1) {
99 :
100 32 : PPG_LOG(" No branches left for token 0x%" PRIXPTR "\n",
101 : (uintptr_t)furcation_token);
102 :
103 : // ... we mark all children as initialized.
104 :
105 96 : for(PPG_Count i = 0; i < furcation_token->n_children; ++i) {
106 64 : ppg_token_reset_control_state(furcation_token->children[i]);
107 :
108 64 : PPG_PRINT_TOKEN(furcation_token->children[i])
109 : }
110 :
111 : // Replace the current furcation with the previous one (if possible)
112 : //
113 32 : --PPG_FB.cur_furcation;
114 : }
115 : else {
116 :
117 : // Mark the current branch (i.e. the branch's root node) as invalid
118 : //
119 98 : PPG_CUR_FUR.branch->misc.state = PPG_Token_Invalid;
120 :
121 98 : --PPG_CUR_FUR.n_branch_candidates;
122 :
123 98 : PPG_LOG(" %d candidates left from %d\n",
124 : PPG_CUR_FUR.n_branch_candidates,
125 : PPG_CUR_FUR.token->n_children
126 : );
127 :
128 98 : break;
129 : }
130 32 : }
131 :
132 : // Reset the current event that is used for further processing
133 : //
134 98 : PPG_EB.cur = PPG_CUR_FUR.event_id;
135 :
136 : #if PPG_HAVE_ASSERTIONS
137 98 : ppg_check_event_buffer_validity();
138 : #endif
139 :
140 98 : return PPG_CUR_FUR.token;
141 : }
142 :
143 246 : static PPG_Token__ *ppg_token_get_most_appropriate_branch(
144 : PPG_Token__ *parent_token,
145 : PPG_Count *n_branch_candidates)
146 : {
147 246 : PPG_LOG("Getting most appropriate branch for 0x%" PRIXPTR "\n",
148 : (uintptr_t)parent_token);
149 :
150 : // Determine the number of possible candidates
151 : //
152 246 : PPG_Layer highest_layer = -1;
153 246 : PPG_Token__ *branch_token = NULL;
154 246 : PPG_Count precedence = 0;
155 :
156 246 : *n_branch_candidates = 0;
157 :
158 : // PPG_LOG("Getting most appropriate child\n");
159 :
160 : /* Find the most suitable token with respect to the current ppg_context->layer.
161 : */
162 948 : for(PPG_Count i = 0; i < parent_token->n_children; ++i) {
163 :
164 702 : if(parent_token->children[i]->misc.state == PPG_Token_Invalid) {
165 :
166 134 : PPG_LOG(" Ignoring 0x%" PRIXPTR " as invalid\n",
167 : (uintptr_t)parent_token->children[i]);
168 :
169 : // #if PPG_HAVE_DEBUGGING
170 : // PPG_PRINT_TOKEN(parent_token->children[i])
171 : // #endif
172 134 : continue;
173 : }
174 :
175 : /* Accept only paths through the search tree whose
176 : * nodes' ppg_context->layer tags are lower or equal the current ppg_context->layer
177 : */
178 : /* Note: Positive layer values are interpreted as lower boundaries,
179 : * negative layer values are interpreted as upper boundaries by taking the
180 : * negative and subtracting one.
181 : */
182 568 : if(parent_token->children[i]->layer < 0) {
183 :
184 0 : if(ppg_context->layer > (-parent_token->children[i]->layer - 1)) {
185 0 : PPG_LOG(" Ignoring 0x%" PRIXPTR " due to insuitably low layer\n",
186 : (uintptr_t)parent_token->children[i]);
187 :
188 0 : parent_token->children[i]->misc.state = PPG_Token_Invalid;
189 0 : continue;
190 : }
191 : }
192 568 : else if(parent_token->children[i]->layer > ppg_context->layer) {
193 :
194 20 : PPG_LOG(" Ignoring 0x%" PRIXPTR " due to insuitably high layer\n",
195 : (uintptr_t)parent_token->children[i]);
196 :
197 20 : parent_token->children[i]->misc.state = PPG_Token_Invalid;
198 20 : continue;
199 : }
200 :
201 548 : ++(*n_branch_candidates);
202 :
203 : // PPG_LOG("Child %d\n", i);
204 :
205 : // PPG_PRINT_TOKEN(parent_token->children[i])
206 :
207 548 : PPG_Count cur_precedence
208 1096 : = parent_token->children[i]
209 548 : ->vtable->token_precedence(parent_token->children[i]);
210 :
211 : // PPG_LOG("Cur precedence %d\n", cur_precedence);
212 : // PPG_LOG("precedence %d\n", precedence);
213 :
214 548 : if(cur_precedence > precedence) {
215 262 : precedence = cur_precedence;
216 262 : highest_layer = parent_token->children[i]->layer;
217 :
218 262 : branch_token = parent_token->children[i];
219 : }
220 : else {
221 :
222 : // PPG_LOG("Equal precedence\n");
223 :
224 286 : if(parent_token->children[i]->layer > highest_layer) {
225 8 : highest_layer = parent_token->children[i]->layer;
226 8 : branch_token = parent_token->children[i];
227 : }
228 : }
229 : // PPG_LOG("match_id %d\n", match_id);
230 : }
231 :
232 : #if PPG_HAVE_LOGGING
233 246 : if(!branch_token) {
234 0 : PPG_LOG("No branch left\n");
235 : }
236 : #endif
237 :
238 246 : return branch_token;
239 : }
240 :
241 470 : static PPG_Token__ *ppg_token_get_next_possible_branch(
242 : PPG_Token__ *parent_token)
243 :
244 : {
245 : // First check if there is already a furcation for the
246 : // parent node.
247 : //
248 470 : bool furcation_already_present =
249 470 : (PPG_FB.cur_furcation > -1)
250 470 : && (PPG_CUR_FUR.token == parent_token);
251 :
252 470 : bool revert_to_previous_furcation = false;
253 :
254 470 : if(parent_token->misc.state == PPG_Token_Invalid) {
255 150 : revert_to_previous_furcation = true;
256 : }
257 320 : else if(parent_token->n_children == 1) {
258 :
259 172 : if(parent_token->children[0]->misc.state == PPG_Token_Invalid) {
260 0 : revert_to_previous_furcation = true;
261 : }
262 : else {
263 :
264 172 : ppg_branch_prepare(parent_token->children[0]);
265 172 : return parent_token->children[0];
266 : }
267 : }
268 :
269 298 : if(revert_to_previous_furcation) {
270 :
271 150 : PPG_LOG("Reverting to previous furcation\n");
272 :
273 150 : parent_token = ppg_furcation_revert();
274 :
275 150 : if(!parent_token) {
276 :
277 : // By returning NULL, we signal that there is no next
278 : // possible branch
279 : //
280 52 : return NULL;
281 : }
282 :
283 98 : furcation_already_present = true;
284 : }
285 :
286 246 : PPG_Count n_branch_candidates = 0;
287 :
288 246 : PPG_Token__ *branch
289 : = ppg_token_get_most_appropriate_branch(
290 : parent_token,
291 : &n_branch_candidates
292 : );
293 :
294 246 : if(branch) {
295 246 : ppg_branch_prepare(branch);
296 : }
297 :
298 246 : if(furcation_already_present) {
299 :
300 98 : PPG_LOG("Updating furcation for token 0x%" PRIXPTR "\n",
301 : (uintptr_t)PPG_CUR_FUR.token);
302 :
303 98 : PPG_CUR_FUR.branch = branch;
304 : }
305 : else {
306 :
307 : #if PPG_HAVE_STATISTICS
308 : ++ppg_context->statistics.n_furcations;
309 : #endif
310 :
311 : // Create a new furcation data set
312 : //
313 148 : PPG_LOG("Creating furcation for token 0x%" PRIXPTR "\n",
314 : (uintptr_t)parent_token);
315 :
316 : //PPG_ASSERT(PPG_FB.cur_furcation < PPG_FB.n_furcations - 1);
317 :
318 148 : ++PPG_FB.cur_furcation;
319 :
320 148 : PPG_CUR_FUR.event_id = PPG_EB.cur;
321 148 : PPG_CUR_FUR.token = parent_token;
322 148 : PPG_CUR_FUR.branch = branch;
323 : }
324 :
325 246 : PPG_CUR_FUR.n_branch_candidates
326 246 : = n_branch_candidates;
327 :
328 246 : PPG_LOG("Furcation 0x%" PRIXPTR ": candidates %u, next branch 0x%" PRIXPTR "\n",
329 : (uintptr_t)PPG_CUR_FUR.token,
330 : PPG_CUR_FUR.n_branch_candidates,
331 : (uintptr_t)PPG_CUR_FUR.branch);
332 :
333 246 : return branch;
334 : }
335 :
336 877 : static PPG_Count ppg_process_next_event(void)
337 : {
338 877 : PPG_LOG("Processing next event\n");
339 :
340 : // If the event is a deactivation event that was obviously
341 : // not matched and it is the first in the queue,
342 : // we flush.
343 : //
344 877 : if( (ppg_event_buffer_size() == 1)
345 176 : && !(PPG_EB.events[PPG_EB.cur].event.flags & PPG_Event_Active)
346 : ) {
347 :
348 16 : PPG_LOG("orpth deact\n");
349 :
350 16 : return PPG_Pattern_Orphaned_Deactivation;
351 : }
352 :
353 861 : if(!ppg_context->current_token) {
354 :
355 142 : ppg_context->current_token = ppg_context->pattern_root;
356 :
357 : // The root node must be reset explicitly
358 : //
359 142 : PPG_CALL_VIRT_METHOD(ppg_context->current_token, reset);
360 :
361 142 : ppg_branch_prepare(ppg_context->current_token);
362 : }
363 :
364 861 : PPG_LOG("Current token 0x%" PRIXPTR ", state %u\n",
365 : (uintptr_t)ppg_context->current_token,
366 : (PPG_Count)ppg_context->current_token->misc.state
367 : );
368 :
369 861 : PPG_Count state = ppg_context->current_token->misc.state;
370 :
371 : // Pretend a match for the root token
372 : //
373 861 : if(!ppg_context->current_token->parent) {
374 142 : state = PPG_Token_Matches;
375 : }
376 :
377 861 : if(! ((state == PPG_Token_Activation_In_Progress)
378 : || (state == PPG_Token_Initialized))) {
379 :
380 442 : PPG_Token__ *branch_token = NULL;
381 :
382 442 : switch (state) {
383 :
384 : case PPG_Token_Matches:
385 : case PPG_Token_Finalized:
386 : case PPG_Token_Invalid:
387 : {
388 442 : PPG_LOG("Determining branch\n");
389 :
390 : // Here, we can rely on the fact that after a match
391 : // during processing the previous event, we already checked
392 : // for the pattern being finished. So the current token
393 : // must have children if we ended here.
394 :
395 : // Find the most appropriate branch to continue with
396 : //
397 : branch_token
398 442 : = ppg_token_get_next_possible_branch(
399 442 : ppg_context->current_token);
400 :
401 : }
402 442 : break;
403 : }
404 :
405 : // There are no possible branches left, e.g.
406 : // if we already tried all options on this level ...
407 : //
408 442 : if(!branch_token) {
409 :
410 : // If no furcation can be found this means that
411 : // we already traversed all candidate branches of
412 : // the search tree. That no matching branch can
413 : // be found means that no match for the overall pattern
414 : // is possible.
415 : //
416 42 : return PPG_Pattern_Invalid;
417 : }
418 :
419 : #if PPG_HAVE_STATISTICS
420 : ++ppg_context->statistics.n_nodes_visited;
421 : #endif
422 :
423 : // We are lucky. There are further branches left.
424 :
425 : // Continue with the branch
426 : //
427 400 : ppg_context->current_token = branch_token;
428 : }
429 :
430 819 : PPG_Event *event = &PPG_EB.events[PPG_EB.cur].event;
431 :
432 819 : PPG_LOG("Branch token 0x%" PRIXPTR "\n",
433 : (uintptr_t)ppg_context->current_token);
434 :
435 :
436 819 : PPG_Count state_before = ppg_context->current_token->misc.state;
437 :
438 : // As the token to process the event.
439 : //
440 819 : bool event_consumed =
441 819 : ppg_context->current_token
442 819 : ->vtable->match_event(
443 819 : ppg_context->current_token,
444 : event,
445 : false /*allow modifications in any case*/
446 : );
447 :
448 1638 : PPG_EB.events[PPG_EB.cur].token_state.changed =
449 819 : state_before != ppg_context->current_token->misc.state;
450 1638 : PPG_EB.events[PPG_EB.cur].token_state.state =
451 819 : ppg_context->current_token->misc.state;
452 :
453 819 : if(event_consumed) {
454 1022 : PPG_EB.events[PPG_EB.cur].consumer =
455 511 : ppg_context->current_token;
456 : }
457 : else {
458 308 : PPG_EB.events[PPG_EB.cur].consumer = NULL;
459 : }
460 :
461 : #if PPG_HAVE_STATISTICS
462 : ++ppg_context->statistics.n_token_checks;
463 : #endif
464 :
465 : // PPG_LOG("Token state after match_event: %u\n", (PPG_Count)ppg_context->current_token->misc.state);
466 : // PPG_LOG("Event consumed: %u\n", event_consumed);
467 :
468 819 : switch(ppg_context->current_token->misc.state) {
469 :
470 : case PPG_Token_Matches:
471 : case PPG_Token_Finalized:
472 259 : if(ppg_context->current_token->n_children == 0){
473 :
474 81 : PPG_LOG("p match\n");
475 :
476 : // We found a matching pattern
477 : //
478 81 : return PPG_Pattern_Matches;
479 : }
480 178 : break;
481 : case PPG_Token_Invalid:
482 :
483 122 : return PPG_Pattern_Branch_Reversion;
484 : break;
485 : }
486 :
487 616 : PPG_LOG("p in prog\n");
488 :
489 616 : return PPG_Pattern_In_Progress;
490 : }
491 :
492 575 : bool ppg_pattern_matching_run(void)
493 : {
494 : //PPG_LOG("ppg_pattern_matching_run\n");
495 :
496 575 : bool pattern_matched = false;
497 :
498 2027 : while(ppg_event_buffer_events_left()) {
499 :
500 877 : PPG_Count process_event_result = ppg_process_next_event();
501 :
502 877 : switch(process_event_result) {
503 :
504 : case PPG_Pattern_Matches:
505 :
506 81 : ppg_recurse_and_process_actions(ppg_context->current_token);
507 :
508 81 : ppg_event_buffer_on_match_success();
509 :
510 81 : pattern_matched = true;
511 :
512 81 : break;
513 :
514 : case PPG_Pattern_Invalid:
515 : {
516 42 : bool action_processed
517 42 : = ppg_recurse_and_process_actions(ppg_context->current_token);
518 :
519 42 : if(action_processed) {
520 :
521 : // PPG_LOG("Fallback success\n");
522 :
523 : // Fallback was possible
524 :
525 : // If an action was processed, we consider the processing as a match
526 : //
527 0 : ppg_event_buffer_on_match_success();
528 :
529 : // Prevent the timeout signal handler from processig events
530 : //
531 0 : ppg_delete_stored_events();
532 : }
533 : else {
534 :
535 : // If no furcation was found, there is no chance
536 : // for a match. Thus we remove the first stored event
537 : // and rerun the overall pattern matching based on a
538 : // new first event.
539 : //
540 42 : ppg_signal(PPG_On_Match_Failed);
541 :
542 42 : PPG_LOG("Mtch fld\n");
543 42 : ppg_even_buffer_flush_and_remove_first_event(false /* no success */);
544 : }
545 : }
546 42 : break;
547 :
548 : case PPG_Pattern_Orphaned_Deactivation:
549 :
550 16 : PPG_LOG("Orph deact\n");
551 :
552 : // Prepare the event buffer for
553 : // user processing
554 : //
555 16 : ppg_event_buffer_on_match_success();
556 :
557 : // If no furcation was found, there is no chance
558 : // for a match. Thus we remove the first stored event
559 : // and rerun the overall pattern matching based on a
560 : // new first event.
561 : //
562 16 : ppg_signal(PPG_On_Flush_Events);
563 :
564 16 : ppg_delete_stored_events();
565 :
566 16 : break;
567 :
568 : case PPG_Pattern_In_Progress:
569 :
570 616 : ppg_event_buffer_advance();
571 :
572 616 : continue;
573 :
574 : case PPG_Pattern_Branch_Reversion:
575 :
576 : // Repeat with the same event. The current
577 : // event might be changed during branch reversion.
578 :
579 122 : continue;
580 : }
581 :
582 : // Prepare for restart of pattern matching
583 : //
584 139 : ppg_reset_pattern_matching_engine();
585 : }
586 :
587 575 : return pattern_matched;
588 : }
589 :
590 10 : bool ppg_pattern_matching_process_remaining_branch_options(void)
591 : {
592 10 : bool pattern_matched = false;
593 :
594 : // Continue processing until all possible branches for the
595 : // given event queue have been processed.
596 : //
597 48 : while(ppg_context->current_token) {
598 :
599 28 : ppg_context->current_token->misc.state = PPG_Token_Invalid;
600 :
601 28 : ppg_context->current_token
602 28 : = ppg_token_get_next_possible_branch(
603 28 : ppg_context->current_token);
604 :
605 28 : if(ppg_context->current_token) {
606 :
607 18 : pattern_matched |= ppg_pattern_matching_run();
608 : }
609 : }
610 :
611 10 : return pattern_matched;
612 : }
|
