Commit | Line | Data |
---|---|---|
d44e3c4f | 1 | /****************************************************************************** |
2 | * Copyright (c) 2000-2016 Ericsson Telecom AB | |
3 | * All rights reserved. This program and the accompanying materials | |
4 | * are made available under the terms of the Eclipse Public License v1.0 | |
5 | * which accompanies this distribution, and is available at | |
6 | * http://www.eclipse.org/legal/epl-v10.html | |
7 | * | |
8 | * Contributors: | |
9 | * Baji, Laszlo | |
10 | * Balasko, Jeno | |
11 | * Baranyi, Botond | |
12 | * Delic, Adam | |
13 | * Forstner, Matyas | |
14 | * Raduly, Csaba | |
15 | * Szabados, Kristof | |
16 | * Szabo, Janos Zoltan – initial implementation | |
17 | * Zalanyi, Balazs Andor | |
18 | * | |
19 | ******************************************************************************/ | |
970ed795 EL |
20 | #include "Struct_of.hh" |
21 | ||
22 | #include "../common/memory.h" | |
23 | #include "Error.hh" | |
24 | #include "Logger.hh" | |
25 | #include "Template.hh" | |
26 | ||
27 | #include "../common/dbgnew.hh" | |
28 | #include <string.h> | |
29 | ||
30 | void **allocate_pointers(int n_elements) | |
31 | { | |
32 | void **ret_val = (void**)Malloc(n_elements * sizeof(void*)); | |
33 | for (int elem_count = 0; elem_count < n_elements; elem_count++) | |
34 | ret_val[elem_count] = NULL; | |
35 | return ret_val; | |
36 | } | |
37 | ||
38 | void **reallocate_pointers(void **old_pointer, int old_n_elements, | |
39 | int n_elements) | |
40 | { | |
41 | void **ret_val = (void**)Realloc(old_pointer, n_elements * sizeof(void*)); | |
42 | for (int elem_count = old_n_elements; elem_count < n_elements; elem_count++) | |
43 | ret_val[elem_count] = NULL; | |
44 | return ret_val; | |
45 | } | |
46 | ||
47 | void free_pointers(void **old_pointer) | |
48 | { | |
49 | Free(old_pointer); | |
50 | } | |
51 | ||
52 | /* | |
53 | Generic comparison function for 'set of' values. The fifth argument | |
54 | is a pointer to a type-specific callback function: boolean | |
55 | compare_function(Base_Type *left_ptr, int left_index, | |
56 | Base_Type *right_ptr, int right_index); | |
57 | ||
58 | - Arguments left_ptr and right_ptr shall point to the operands of comparison. | |
59 | They are handled transparently by the comparison function. | |
60 | ||
61 | - The function returns whether the element of left operand at position | |
62 | left_index equals to the element of right operand at position right_index. | |
63 | ||
64 | - In case of invalid value pointers, index overflow or negative indices the | |
65 | behaviour of the function is undefined. | |
66 | */ | |
67 | #ifdef TITAN_RUNTIME_2 | |
68 | boolean compare_set_of(const Record_Of_Type *left_ptr, int left_size, | |
69 | const Record_Of_Type *right_ptr, int right_size, | |
70 | compare_function_t compare_function) | |
71 | #else | |
72 | boolean compare_set_of(const Base_Type *left_ptr, int left_size, | |
73 | const Base_Type *right_ptr, int right_size, | |
74 | compare_function_t compare_function) | |
75 | #endif | |
76 | { | |
77 | if (left_size < 0 || right_size < 0 || | |
78 | left_ptr == NULL || right_ptr == NULL) | |
79 | { | |
80 | TTCN_error("Internal error: compare_set_of: invalid argument."); | |
81 | } | |
82 | ||
83 | // if the sizes are different the values cannot be equal | |
84 | if (left_size != right_size) return FALSE; | |
85 | // if both values are empty they must be equal | |
86 | if (left_size == 0) return TRUE; | |
87 | ||
88 | //stores which have already been matched | |
89 | boolean *covered = (boolean*)Malloc(left_size * sizeof(boolean)); | |
90 | //initially none of them | |
91 | memset(covered, 0, left_size * sizeof(boolean)); | |
92 | ||
93 | boolean pair_found; | |
94 | int left_index, right_index;//the actual indices | |
95 | int first_on_right = 0;//index of the first element to check on the right side | |
96 | //index of the last element to check on the right side | |
97 | int last_on_right = left_size-1; | |
98 | ||
99 | for(left_index = 0; left_index < left_size; left_index++) | |
100 | { | |
101 | pair_found = FALSE; | |
102 | for(right_index=first_on_right;right_index<=last_on_right;right_index++) | |
103 | { | |
104 | if(!covered[right_index] | |
105 | && compare_function(left_ptr, left_index, right_ptr, right_index)) | |
106 | { | |
107 | //a new match was found | |
108 | covered[right_index] = TRUE; | |
109 | //if it is the first then check if we can increase the index more, | |
110 | // reducing the elements that need to be checked | |
111 | if(right_index == first_on_right) | |
112 | while(++first_on_right<last_on_right && covered[first_on_right]){} | |
113 | //if it is the last then check if we can decrease the index more, | |
114 | // reducing the elements that need to be checked | |
115 | if(right_index == last_on_right) | |
116 | while(--last_on_right>first_on_right && covered[last_on_right]){} | |
117 | pair_found = TRUE; | |
118 | break; | |
119 | } | |
120 | } | |
121 | //if we can't find a pair to any of the elements, the sets can not | |
122 | // match any longer | |
123 | if(!pair_found){ | |
124 | Free(covered); | |
125 | return FALSE; | |
126 | } | |
127 | } | |
128 | ||
129 | //if we found a pair to all the elements then they are the same | |
130 | Free(covered); | |
131 | return TRUE; | |
132 | } | |
133 | ||
134 | /* | |
135 | Simplified matching function for 'record of' types. It is used when the | |
136 | template does not contain permutation matching constructs. | |
137 | The fifth argument is a pointer to a type-specific callback function: | |
138 | boolean match_function(const Base_Type *value_ptr, int value_index, | |
139 | const Restricted_Length_Template *template_ptr, int template_index); | |
140 | ||
141 | - Arguments value_ptr and template_ptr shall point to the corresponding | |
142 | value and template object. They are handled transparently by the matching | |
143 | function. | |
144 | ||
145 | - If both index arguments are non-negative the function returns whether | |
146 | the value at position value_index matches the template_index-th | |
147 | element in the template. | |
148 | ||
149 | - If value_index is negative the function returns whether the | |
150 | element in the template at index template_index is a '*' | |
151 | (ANY_OR_NONE) wildcard. | |
152 | ||
153 | - Otherwise (in case of invalid pointers, index overflow or negative | |
154 | template_index) the behaviour of the function is undefined. | |
155 | ||
156 | The very same abstract algorithm is used in the matching of types of | |
157 | bitstring, octetstring, hexstring. The only differences are how we | |
158 | match 2 elements, how we find out if a template element is | |
159 | an ANY_OR_NONE / ANY element | |
160 | */ | |
161 | ||
162 | boolean match_array(const Base_Type *value_ptr, int value_size, | |
163 | const Restricted_Length_Template *template_ptr, int template_size, | |
3abe9331 | 164 | match_function_t match_function, boolean legacy) |
970ed795 EL |
165 | { |
166 | if (value_ptr == NULL || value_size < 0 || template_ptr == NULL || | |
167 | template_size < 0) | |
168 | TTCN_error("Internal error: match_array: invalid argument."); | |
169 | ||
170 | // the empty template matches the empty value only | |
171 | if (template_size == 0) return value_size == 0; | |
172 | ||
173 | int template_index = 0;//the index of the template we are examining | |
174 | ||
175 | if (value_size == 0){ | |
176 | //We matched if the remaining templates are | |
177 | // asterisks | |
178 | while(template_index < template_size && | |
3abe9331 | 179 | match_function(value_ptr, -1, template_ptr, template_index, legacy)) |
970ed795 EL |
180 | template_index++; |
181 | ||
182 | return template_index == template_size; | |
183 | } | |
184 | ||
185 | int value_index = 0;//the index of the value we are examining at the point | |
186 | //the index of the last asterisk found in the template at the moment | |
187 | // -1 if no asterisks were found yet | |
188 | int last_asterisk = -1; | |
189 | //this is the index of the last value that is matched by | |
190 | // the last asterisk in the template | |
191 | int last_value_to_asterisk = -1; | |
192 | ||
193 | //must finish as we always increase one of the 4 indices or we return | |
194 | // and there are limited number of templates and values | |
195 | for(;;) | |
196 | { | |
3abe9331 | 197 | if(match_function(value_ptr, -1, template_ptr, template_index, legacy)) |
970ed795 EL |
198 | { |
199 | //if we found an asterisk we administer it, and step in the template | |
200 | last_asterisk = template_index++; | |
201 | last_value_to_asterisk = value_index; | |
3abe9331 | 202 | } |
203 | else if(match_function(value_ptr, value_index, template_ptr, template_index, | |
204 | legacy)) | |
970ed795 EL |
205 | { |
206 | //if we found a matching pair we step in both | |
207 | value_index++; | |
208 | template_index++; | |
209 | } else { | |
210 | //if we didn't match and we found no asterisk the match failed | |
211 | if(last_asterisk == -1) return FALSE; | |
212 | //if we found an asterisk than fall back to it | |
213 | //and step the value index | |
214 | template_index = last_asterisk +1; | |
215 | value_index = ++last_value_to_asterisk; | |
216 | } | |
217 | ||
218 | if(value_index == value_size && template_index == template_size) | |
219 | { | |
220 | //we finished clean | |
221 | return TRUE; | |
222 | } else if(template_index == template_size) | |
223 | { | |
224 | //value_index != value_size at this point so it is pointless | |
225 | // to check it in the if statement | |
226 | //At the end of the template | |
3abe9331 | 227 | if(match_function(value_ptr, -1, template_ptr, template_index-1, legacy)) { |
970ed795 EL |
228 | //if the templates last element is an asterisk it eats up the values |
229 | return TRUE; | |
230 | } else if (last_asterisk == -1){ | |
231 | //if there were no asterisk the match failed | |
232 | return FALSE; | |
233 | } else{ | |
234 | //fall back to the asterisk, and step the value's indices | |
235 | template_index = last_asterisk+1; | |
236 | value_index = ++last_value_to_asterisk; | |
237 | } | |
238 | } else if(value_index == value_size) | |
239 | { | |
240 | //template_index != template_size at this point so it is pointless | |
241 | // to check it in the if statement | |
242 | //At the end of the value we matched if the remaining templates are | |
243 | // asterisks | |
244 | while(template_index < template_size && | |
3abe9331 | 245 | match_function(value_ptr, -1, template_ptr, template_index, legacy)) |
970ed795 EL |
246 | template_index++; |
247 | ||
248 | return template_index == template_size; | |
249 | } | |
250 | } | |
251 | } | |
252 | ||
253 | /* Ancillary classes for 'set of' matching */ | |
254 | ||
255 | namespace { | |
256 | ||
257 | enum edge_status { UNKNOWN, NO_EDGE, EDGE, PAIRS }; | |
258 | ||
259 | /* Class Matching_Table: | |
260 | * Responsibilities | |
261 | * - index transformation to skip asterisks in the template | |
262 | * the table is initialized in constructor | |
263 | * - maintain a matrix that stores the status of edges | |
264 | * (template <-> value relations) | |
265 | * table is initialized explicitly | |
266 | * - a flag for each value element to indicate whether it is covered | |
267 | * Note: All dynamically allocated memory is collected into this class | |
268 | * to avoid memory leaks in case of errors (exceptions). | |
269 | */ | |
270 | ||
271 | class Matching_Table { | |
272 | match_function_t match_function; | |
273 | int value_size; | |
274 | int value_start; | |
275 | int template_size; | |
276 | int template_start; | |
277 | int n_asterisks; | |
278 | int *template_index_table; | |
279 | edge_status **edge_matrix; | |
280 | boolean *covered_vector; //tells if a value is covered | |
3abe9331 | 281 | boolean legacy; |
970ed795 EL |
282 | |
283 | //if the value is covered, then tells by whom it is covered | |
284 | int *covered_index_vector; | |
285 | int nof_covered; | |
286 | int *paired_templates; | |
287 | ||
288 | //the matching function requires these pointers | |
289 | const Base_Type *value_ptr; | |
290 | ||
291 | //they are allocated and freed outside | |
292 | const Restricted_Length_Template *template_ptr; | |
293 | ||
294 | public: | |
295 | //the match_set_of will be called from the permutation matcher | |
296 | // where the beginning of the examined set might not be at 0 position | |
297 | Matching_Table(const Base_Type *par_value_ptr, int par_value_start, | |
298 | int par_value_size,const Restricted_Length_Template *par_template_ptr, | |
299 | int par_template_start, int par_template_size, | |
3abe9331 | 300 | match_function_t par_match_function, boolean par_legacy) |
970ed795 EL |
301 | { |
302 | match_function = par_match_function; | |
303 | value_size = par_value_size; | |
304 | value_start = par_value_start; | |
305 | template_start = par_template_start; | |
306 | value_ptr = par_value_ptr; | |
307 | template_ptr = par_template_ptr; | |
3abe9331 | 308 | legacy = par_legacy; |
970ed795 EL |
309 | n_asterisks = 0; |
310 | nof_covered = 0;//to get rid of the linear summing | |
311 | ||
312 | // we won't use all elements if there are asterisks in template | |
313 | // it is cheaper to allocate it once instead of realloc'ing | |
314 | template_index_table = new int[par_template_size]; | |
315 | // locating the asterisks in the template | |
316 | for (int i = 0; i < par_template_size; i++) | |
317 | { | |
3abe9331 | 318 | if(match_function(value_ptr, -1,template_ptr, par_template_start+i, legacy)) |
970ed795 EL |
319 | n_asterisks++; |
320 | else template_index_table[i - n_asterisks] = i; | |
321 | } | |
322 | // don't count the asterisks | |
323 | template_size = par_template_size - n_asterisks; | |
324 | ||
325 | edge_matrix = NULL; | |
326 | covered_vector = NULL; | |
327 | covered_index_vector = NULL; | |
328 | paired_templates = NULL; | |
329 | } | |
330 | ||
331 | ~Matching_Table() | |
332 | { | |
333 | delete [] template_index_table; | |
334 | if (edge_matrix != NULL) | |
335 | { | |
336 | for (int i = 0; i < template_size; i++) delete [] edge_matrix[i]; | |
337 | delete [] edge_matrix; | |
338 | } | |
339 | delete [] covered_vector; | |
340 | delete [] covered_index_vector; | |
341 | delete [] paired_templates; | |
342 | } | |
343 | ||
344 | int get_template_size() const { return template_size; } | |
345 | ||
346 | boolean has_asterisk() const { return n_asterisks > 0; } | |
347 | ||
348 | void create_matrix() | |
349 | { | |
350 | edge_matrix = new edge_status*[template_size]; | |
351 | for (int i = 0; i < template_size; i++) | |
352 | { | |
353 | edge_matrix[i] = new edge_status[value_size]; | |
354 | for (int j = 0; j < value_size; j++) edge_matrix[i][j] = UNKNOWN; | |
355 | } | |
356 | covered_vector = new boolean[value_size]; | |
357 | for (int j = 0; j < value_size; j++) covered_vector[j] = FALSE; | |
358 | ||
359 | paired_templates = new int[template_size]; | |
360 | for(int j = 0; j < template_size; j++) paired_templates[j] = -1; | |
361 | ||
362 | covered_index_vector = new int[value_size]; | |
363 | } | |
364 | ||
365 | edge_status get_edge(int template_index, int value_index) | |
366 | { | |
367 | if (edge_matrix[template_index][value_index] == UNKNOWN) | |
368 | { | |
369 | if (match_function(value_ptr, value_start + value_index, | |
370 | template_ptr, | |
3abe9331 | 371 | template_start + template_index_table[template_index], legacy)) |
970ed795 EL |
372 | { |
373 | edge_matrix[template_index][value_index] = EDGE; | |
374 | }else{ | |
375 | edge_matrix[template_index][value_index] = NO_EDGE; | |
376 | } | |
377 | } | |
378 | return edge_matrix[template_index][value_index]; | |
379 | } | |
380 | ||
381 | void set_edge(int template_index, int value_index, edge_status new_status) | |
382 | { | |
383 | edge_matrix[template_index][value_index] = new_status; | |
384 | } | |
385 | ||
386 | boolean is_covered(int value_index) const | |
387 | { | |
388 | return covered_vector[value_index]; | |
389 | } | |
390 | ||
391 | int covered_by(int value_index) const | |
392 | { | |
393 | return covered_index_vector[value_index]; | |
394 | } | |
395 | ||
396 | int get_nof_covered() const | |
397 | { | |
398 | return nof_covered; | |
399 | } | |
400 | ||
401 | void set_covered(int value_index, int template_index) | |
402 | { | |
403 | if(!covered_vector[value_index]) | |
404 | nof_covered++; | |
405 | ||
406 | covered_vector[value_index] = TRUE; | |
407 | covered_index_vector[value_index] = template_index; | |
408 | } | |
409 | ||
410 | boolean is_paired(int j) | |
411 | { | |
412 | return paired_templates[j] != -1; | |
413 | } | |
414 | ||
415 | void set_paired(int j, int i) | |
416 | { | |
417 | paired_templates[j] = i; | |
418 | } | |
419 | ||
420 | int get_paired(int j) | |
421 | { | |
422 | return paired_templates[j]; | |
423 | } | |
424 | }; | |
425 | ||
426 | } | |
427 | ||
428 | namespace { | |
429 | ||
430 | /* Tree-list. It is used for storing a tree in BFS order. That is: the | |
431 | * first element is the root of the tree, it is followed by its | |
432 | * neighbours then the neighbours of the neighbours follow, and so | |
433 | * on. The elements can be reached sequentially by the use of the next | |
434 | * pointer. Also the parent of an element can be reached via a pointer | |
435 | * also. Elements can be inserted in the tree, and with the help of | |
436 | * the functions one can move or search in the tree. | |
437 | */ | |
438 | ||
439 | class Tree_list { | |
440 | /* Elements of the tree-list. */ | |
441 | struct List_elem { | |
442 | int data; | |
443 | List_elem *next, *parent; | |
444 | } head, *current; | |
445 | ||
446 | public: | |
447 | Tree_list(int head_data) | |
448 | { | |
449 | head.data = head_data; | |
450 | head.next = NULL; | |
451 | head.parent = NULL; | |
452 | current = &head; | |
453 | } | |
454 | ||
455 | ~Tree_list() | |
456 | { | |
457 | for (List_elem *ptr = head.next; ptr != NULL; ) | |
458 | { | |
459 | List_elem *next = ptr->next; | |
460 | delete ptr; | |
461 | ptr = next; | |
462 | } | |
463 | } | |
464 | ||
465 | void insert_data(int new_data) | |
466 | { | |
467 | List_elem* newptr = new List_elem; | |
468 | newptr->data = new_data; | |
469 | newptr->next = current->next; | |
470 | newptr->parent = current; | |
471 | current->next = newptr; | |
472 | } | |
473 | ||
474 | void back_step() | |
475 | { | |
476 | if (current->parent != NULL) current = current->parent; | |
477 | } | |
478 | ||
479 | void step_forward() | |
480 | { | |
481 | if (current->next != NULL) current = current->next; | |
482 | } | |
483 | ||
484 | int head_value() const { return head.data; } | |
485 | int actual_data()const { return current->data; } | |
486 | boolean is_head() const { return current->parent == NULL; } | |
487 | boolean end_of_list() const { return current->next == NULL; } | |
488 | ||
489 | boolean do_exists(int find_data) const | |
490 | { | |
491 | for (const List_elem *ptr = &head; ptr != NULL; ptr = ptr->next) | |
492 | if (ptr->data == find_data) return TRUE; | |
493 | return FALSE; | |
494 | } | |
495 | }; | |
496 | ||
497 | } | |
498 | ||
499 | /* Generic matching function for 'set of' values. The interpretation | |
500 | * of third argument is the same as for 'record of'. | |
501 | */ | |
502 | ||
503 | /* | |
504 | find_pairs implements an algorithm of matching sets using a graph | |
505 | algorithm. The correctness of the algorithm is _not_ proven here just | |
506 | the steps of the algorithm are described. Let denote the two sets by A | |
507 | and B. The algorithm is for deciding whether for all elements of A | |
508 | there can be found a matching pair in B. This means that the function | |
509 | returns true when A matches a subset of B. If the two sets' sizes | |
510 | equal then the function returns true if the two sets match each other. | |
511 | ||
512 | The algorithm. For all elements in A the following: | |
513 | ||
514 | Initialize some variables. After that start a cycle. In the cycle we | |
515 | try to find a pair for the actual element (at the start actual element | |
516 | is the element from set A - later it may change). The result can be: | |
517 | ||
518 | case 1: If there is one pair the cycle is finished we administer the | |
519 | pairs (it may need a recursive modification in the | |
520 | other pairs) and after that the algorithm continues | |
521 | with the next element in A. | |
522 | ||
523 | case 2: If there is no pair the algorithm returns false because if | |
524 | there is no pair for one element, that means that the | |
525 | two sets cannot be equal/matching. case 3: If there | |
526 | is a "pair" but is already assigned as a pair to an | |
527 | other element of A then this "pair" element is put in | |
528 | the alternating tree list (if it's not in the list | |
529 | already). The alternating tree is built to modify and | |
530 | administer existing pairs in a way that the elements | |
531 | which already have pairs will have pairs (but maybe | |
532 | other ones) and we will be able to assign a pair for | |
533 | the actual element also. | |
534 | ||
535 | If we haven't found a pair which is not assigned already nor we have | |
536 | found only non-matching elements then (in other words in case 3) we | |
537 | built an alternating tree with some "pairs" and continue the cycle by | |
538 | going to the next element of the alternating tree list. If it is from | |
539 | set A, we do as described above, if not - the actual element is from | |
540 | set B - we do the following. As this element is a pair of another | |
541 | element it should have a pair, so if its pair is not already in the | |
542 | alternating tree, we add it to the alternating tree list and continue | |
543 | the cycle with the next element of the list. | |
544 | ||
545 | If the algorithm doesn't terminate within the cycles by finding no | |
546 | pairs (case 2) then it will find pairs (simply or with the help of | |
547 | alternating trees) for each element of set A, meaning the two sets are | |
548 | matching. If it terminates that means that the matching process | |
549 | already failed somewhere resulting in non-matching. | |
550 | */ | |
551 | ||
552 | /* | |
553 | match_set_of implements a set matching algorithm using graphs. | |
554 | ||
555 | The algorithm implements subset, exact and superset matching. | |
556 | The description will be general, to ease understanding, giving up on the | |
557 | specific details. Later, when the base algorithm is already understood | |
558 | I will mention a part that ain't really needed for this algorithm, but it | |
559 | is still in the code. | |
560 | ||
561 | The correctness of the algorithm is _not_ proven here just | |
562 | the steps of the algorithm are described. Let denote the two sets by A | |
563 | and B. | |
564 | The algorithm returns true if the relationship between A and B is right | |
565 | (A is subset of B and thats what we were checking for). | |
566 | ||
567 | The algorithm: | |
568 | ||
569 | In the beginning it makes some checks to see if we can quickly deny matching. | |
570 | ||
571 | Than it goes through the elements of set A and tries to find a matching element | |
572 | in set B which still has no pair. If it finds a matching element, then | |
573 | it is administered. | |
574 | If no new matching elements can be found than: | |
575 | -if the matching requirements (subset) allows this, we step to the next | |
576 | element of set A. | |
577 | -if the requirements (exact/superset) don't allow this, then we insert | |
578 | B's element in the tree, trying to find a new element of B | |
579 | for his pair in A. | |
580 | ||
581 | The tree is walked recursively searching a new pair for elements of set A | |
582 | (the elements of set B are only inserted so we have links between A's elements, | |
583 | when in case of success we try to administer the changes). | |
584 | ||
585 | The algorithm can end on two ways: | |
586 | -not even with the recursive search can we find a pair for an element | |
587 | and the matching requirement doesn't allow this, so we return false. | |
588 | -we went through all of A's elements, in this case we decide based | |
589 | on the matching requirement and the number of pairs found | |
590 | (for example in subset matching the number of A's elements and the | |
591 | number of found pairs must be the same). | |
592 | ||
593 | The strange piece of code is when we work with the pair_list. | |
594 | It stores which element of set A is paired with an element of set B | |
595 | (if there is no element than it stores -1). | |
596 | This is not needed in this algorithm, but if we would call this algorithm | |
597 | in a loop with increasing sets than it would make this algorithm incremental, | |
598 | by not making the same matching test ever and ever again. | |
599 | */ | |
600 | ||
601 | boolean match_set_of_internal(const Base_Type *value_ptr, | |
602 | int value_start, int value_size, | |
603 | const Restricted_Length_Template *template_ptr, | |
604 | int template_start, int template_size, | |
605 | match_function_t match_function, | |
606 | type_of_matching match_type, | |
607 | int* number_of_uncovered, int* pair_list, | |
3abe9331 | 608 | unsigned int number_of_checked, boolean legacy) |
970ed795 EL |
609 | { |
610 | Matching_Table table(value_ptr, value_start, value_size, | |
611 | template_ptr, template_start, template_size, | |
3abe9331 | 612 | match_function, legacy); |
970ed795 EL |
613 | |
614 | // we have to use the reduced length of the template | |
615 | // (not counting the asterisks) | |
616 | int real_template_size = table.get_template_size(); | |
617 | ||
618 | // handling trivial cases: | |
619 | //to be compatible with the previous version | |
620 | // is a mistake if the user can't enter an asterisk as a set member | |
621 | if(match_type == EXACT && real_template_size < template_size) | |
622 | match_type = SUPERSET; | |
623 | ||
624 | if(match_type == SUBSET && real_template_size < template_size) | |
625 | { | |
626 | return TRUE; | |
627 | } | |
628 | ||
629 | //if the element count does not match the matching mode then we are ready | |
630 | if(match_type == SUBSET && value_size > real_template_size) return FALSE; | |
631 | if(match_type == EXACT && value_size != real_template_size) return FALSE; | |
632 | if(match_type == SUPERSET && value_size < real_template_size) return FALSE; | |
633 | ||
634 | // if the template has no non-asterisk elements | |
635 | if (real_template_size == 0) { | |
636 | // if the template has only asterisks -> matches everything | |
637 | if (template_size > 0) return TRUE; | |
638 | // the empty template matches the empty value only | |
639 | else return (value_size == 0 || match_type == SUPERSET); | |
640 | } | |
641 | ||
642 | // let's start the real work | |
643 | ||
644 | // allocate some memory | |
645 | table.create_matrix(); | |
646 | ||
647 | //if we need increamentality | |
648 | ||
649 | if(pair_list != NULL) | |
650 | for(int i = 0; i < template_size; i++) | |
651 | { | |
652 | //if we have values from a previous matching than use them | |
653 | // instead of counting them out again | |
654 | if(pair_list[i] >= 0) | |
655 | { | |
656 | table.set_paired(i, pair_list[i]); | |
657 | table.set_covered(pair_list[i], i); | |
658 | table.set_edge(i, pair_list[i], PAIRS); | |
659 | } | |
660 | } | |
661 | ||
662 | for(int template_index = 0; | |
663 | template_index < real_template_size; | |
664 | template_index++) | |
665 | { | |
666 | if(table.is_paired(template_index)) | |
667 | continue; | |
668 | ||
669 | boolean found_route = FALSE; | |
670 | Tree_list tree(template_index); | |
671 | for (int i = template_index; ; ) | |
672 | { | |
673 | int j; | |
674 | if(table.is_paired(i)) | |
675 | j = table.get_paired(i)+1; | |
676 | else | |
677 | j = number_of_checked; | |
678 | ||
679 | for(; j < value_size; j++) | |
680 | { | |
681 | //if it is not covered | |
682 | if(!table.is_covered(j)) | |
683 | { | |
684 | //if it is not covered then it might be good | |
685 | if (table.get_edge(i, j) == EDGE) | |
686 | { | |
687 | //update the values in the tree | |
688 | // and in the other structures | |
689 | int new_value_index = j; | |
690 | int temp_value_index; | |
691 | int actual_node; | |
692 | boolean at_end = FALSE; | |
693 | for( ; !at_end; ) | |
694 | { | |
695 | at_end = tree.is_head(); | |
696 | actual_node = tree.actual_data(); | |
697 | ||
698 | temp_value_index = table.get_paired(actual_node); | |
699 | if(temp_value_index != -1) | |
700 | table.set_edge(temp_value_index,actual_node,EDGE); | |
701 | ||
702 | table.set_paired(actual_node,new_value_index); | |
703 | ||
704 | if(pair_list != NULL) | |
705 | pair_list[actual_node] = new_value_index; | |
706 | ||
707 | table.set_edge(actual_node, new_value_index, PAIRS); | |
708 | table.set_covered(new_value_index,actual_node); | |
709 | ||
710 | new_value_index = temp_value_index; | |
711 | if(!at_end) | |
712 | tree.back_step(); | |
713 | } | |
714 | ||
715 | //if we need subset matching | |
716 | // and we already matched every value | |
717 | // then we have finished | |
718 | if(match_type == SUBSET | |
719 | && table.get_nof_covered() == value_size) | |
720 | { | |
721 | return TRUE; | |
722 | } | |
723 | ||
724 | found_route = TRUE; | |
725 | break; | |
726 | } | |
727 | } | |
728 | } | |
729 | if (found_route) break; | |
730 | ||
731 | //we get here if we couldn't find a new value for the template | |
732 | // so we check if there is a covered value. | |
733 | // if we find one then we try to find a new value for his | |
734 | // pair template. | |
735 | for(j = 0 ; j < value_size; j++) | |
736 | { | |
737 | if(table.is_covered(j) && | |
738 | table.get_edge(i,j) == EDGE && | |
739 | !tree.do_exists(j + real_template_size)) | |
740 | { | |
741 | int temp_index = table.covered_by(j); | |
742 | if(!tree.do_exists(temp_index)) | |
743 | { | |
744 | tree.insert_data(temp_index); | |
745 | } | |
746 | } | |
747 | } | |
748 | ||
749 | if (!tree.end_of_list()) { | |
750 | // continue with the next element | |
751 | tree.step_forward(); | |
752 | i = tree.actual_data(); | |
753 | } else { | |
754 | //couldn't find a matching value for a template | |
755 | // this can only be allowed in SUBSET matching, | |
756 | // otherwise there is no match | |
757 | if(match_type == EXACT) | |
758 | return FALSE; | |
759 | ||
760 | //every template has to match in SUPERSET matching | |
761 | if(match_type == SUPERSET) | |
762 | { | |
763 | //if we are not in permutation matching or don't need to count | |
764 | // the number of unmatched templates than exit | |
765 | if(number_of_uncovered == NULL) | |
766 | return FALSE; | |
767 | } | |
768 | ||
769 | //if we are SUBSET matching | |
770 | // then we have either returned true when we found | |
771 | // a new value for the last template (so we can't get to here) | |
772 | // or we just have to simply ignore this template | |
773 | break; | |
774 | } | |
775 | } | |
776 | } | |
777 | //we only reach here if we have found pairs to every template or we | |
778 | // are making a SUBSET match | |
779 | // (or in SUPERSET we need the number of uncovered) | |
780 | //the result depends on the number of pairs found | |
781 | ||
782 | int number_of_pairs = table.get_nof_covered(); | |
783 | ||
784 | if(match_type == SUBSET) | |
785 | { | |
786 | if(number_of_pairs == value_size) | |
787 | return TRUE; | |
788 | else | |
789 | return FALSE; | |
790 | } | |
791 | ||
792 | //here EXACT can only be true or we would have return false earlier | |
793 | if(match_type == EXACT) return TRUE; | |
794 | ||
795 | if(match_type == SUPERSET) | |
796 | { | |
797 | //we only return FALSE if we need the number of uncovered templates and | |
798 | // there really were uncovered templates | |
799 | if(number_of_uncovered != NULL && number_of_pairs != real_template_size) | |
800 | { | |
801 | *number_of_uncovered = real_template_size - number_of_pairs; | |
802 | return FALSE; | |
803 | }else{ | |
804 | return TRUE; | |
805 | } | |
806 | } | |
807 | ||
808 | return FALSE; | |
809 | } | |
810 | ||
811 | ||
812 | //the real matching function, we don't wan't it to be seen from outside so | |
813 | // it is not declared in the header, but called by permutation_match | |
814 | ||
815 | /* | |
816 | recursive_permutation_match implements a recursive algorithm to match | |
817 | two arrays of values say A and B, where A can contain permutations and | |
818 | asterisks. | |
819 | A permutation is matched if there is a matching part of values in array B | |
820 | with any order of the values in the permutation. | |
821 | ||
822 | The algorithm: | |
823 | ||
824 | The algorithm is recursive so we will give the general working for one | |
825 | level, which is what all the levels do. | |
826 | ||
827 | At each level the algorithm is called with some left over of both arrays | |
828 | and tries to match them. | |
829 | ||
830 | There are three different ways to go on each level: | |
831 | -if A's leftover's first element is the beginning of a permutation | |
832 | then a set_of like matching will take place. It is not exactly a set_of | |
833 | matching because if there is a asterisk among the permutated elements | |
834 | than we can'tknow how long part of B's array will match it. | |
835 | ||
836 | So we try to find the smallest possible part of B's array which will be | |
837 | a superset of the permutated elements. This is achieved by making set_of | |
838 | matchings. When the superset is found, we call the algorithm for | |
839 | the leftovers of the two arrays. | |
840 | ||
841 | If the leftovers don't match, than we try matching a bigger part of B's | |
842 | array with the permutated elements, till we find a size where the | |
843 | leftovers match and we can return true, or we reach the maximal size | |
844 | the permutation allows as to match with elements of B, in this case | |
845 | we must return false. | |
846 | ||
847 | -if A's leftover start with an asterisk which does not belong to a | |
848 | permutation than it treated like a permutation, whose minimal size of | |
849 | matching is 0 elements, and maximal size of matching is the whole | |
850 | leftover array of B. | |
851 | ||
852 | -else we have to make element-by-element matches. | |
853 | if we match till the next asterisk or permutation start then we | |
854 | make a recursive call with the elements from there | |
855 | else we return false. | |
856 | ||
857 | There are some speedups: | |
858 | -in permutation matching: | |
859 | -we estimate how small or large the matching set can be in | |
860 | advance. | |
861 | -to find the first matching set of B's elements we use the incremental | |
862 | version of set matching. | |
863 | -after finding a matching set we don't make any more set matches as | |
864 | the increased set must still be a superset. | |
865 | -if we fail in the element-by-element matching part than we don't return | |
866 | with false, but try to find the first element of B which will match with | |
867 | the last "unmatched" element of A. We give back this shift size to the | |
868 | calling level so it can make a bigger jump forward (skipping the calls | |
869 | that have no chance to match). | |
870 | -if we in any part of the algorithm find that match can't possibly happen, | |
871 | than we return to the calling level with NO_CHANCE. This way we can | |
872 | end the algorithm without making those unnecessary checks. | |
873 | */ | |
874 | static answer recursive_permutation_match(const Base_Type *value_ptr, | |
875 | unsigned int value_start_index, | |
876 | unsigned int value_size, | |
877 | const Record_Of_Template *template_ptr, | |
878 | unsigned int template_start_index, | |
879 | unsigned int template_size, | |
880 | unsigned int permutation_index, | |
881 | match_function_t match_function, | |
3abe9331 | 882 | unsigned int& shift_size, |
883 | boolean legacy) | |
970ed795 EL |
884 | { |
885 | unsigned int nof_permutations = template_ptr->get_number_of_permutations(); | |
886 | if (permutation_index > nof_permutations) | |
887 | TTCN_error("Internal error: recursive_permutation_match: " | |
888 | "invalid argument."); | |
889 | ||
890 | if (permutation_index < nof_permutations && | |
891 | template_ptr->get_permutation_end(permutation_index) > | |
892 | template_start_index + template_size) | |
893 | TTCN_error("Internal error: recursive_permutation_match: wrong " | |
894 | "permutation interval settings for permutation %d.", | |
895 | permutation_index); | |
896 | ||
897 | shift_size = 0; | |
898 | ||
899 | //trivial cases | |
900 | if(template_size == 0) | |
901 | { | |
902 | //reached the end of templates | |
903 | // if we reached the end of values => good | |
904 | // else => bad | |
905 | if(value_size == 0) | |
906 | return SUCCESS; | |
907 | else | |
908 | return FAILURE; | |
909 | } | |
910 | ||
911 | //are we at an asterisk or at the beginning of a permutation interval | |
912 | boolean is_asterisk; | |
913 | boolean permutation_begins = permutation_index < nof_permutations && | |
914 | template_start_index == | |
915 | template_ptr->get_permutation_start(permutation_index); | |
916 | ||
917 | if (permutation_begins || | |
3abe9331 | 918 | match_function(value_ptr, -1, template_ptr, template_start_index, legacy)) |
970ed795 EL |
919 | { |
920 | unsigned int smallest_possible_size; | |
921 | unsigned int largest_possible_size; | |
922 | boolean has_asterisk; | |
923 | boolean already_superset; | |
924 | unsigned int permutation_size; | |
925 | ||
926 | //check how many values might be associated with this permutation | |
927 | //if we are at a permutation start | |
928 | if (permutation_begins) | |
929 | { | |
930 | is_asterisk = FALSE; | |
931 | permutation_size = | |
932 | template_ptr->get_permutation_size(permutation_index); | |
933 | smallest_possible_size = 0; | |
934 | has_asterisk = FALSE; | |
935 | ||
936 | //count how many non asterisk elements are in the permutation | |
937 | for(unsigned int i = 0; i < permutation_size; i++) | |
938 | { | |
939 | if(match_function(value_ptr, -1, template_ptr, | |
3abe9331 | 940 | i + template_start_index, legacy)) |
970ed795 EL |
941 | { |
942 | has_asterisk = TRUE; | |
943 | }else{ | |
944 | smallest_possible_size++; | |
945 | } | |
946 | } | |
947 | ||
948 | //the real permutation size is bigger then the value size | |
949 | if(smallest_possible_size > value_size) | |
950 | return NO_CHANCE; | |
951 | ||
952 | //if the permutation has an asterisk then it can grow | |
953 | if(has_asterisk) | |
954 | { | |
955 | largest_possible_size = value_size; | |
956 | ||
957 | //if there are only asterisks in the permutation | |
958 | if(smallest_possible_size == 0) | |
959 | already_superset = TRUE; | |
960 | else | |
961 | already_superset = FALSE; | |
962 | }else{ | |
963 | //without asterisks its size is fixed | |
964 | largest_possible_size = smallest_possible_size; | |
965 | already_superset = FALSE; | |
966 | } | |
967 | }else{ | |
968 | //or at an asterisk | |
969 | is_asterisk = TRUE; | |
970 | already_superset = TRUE; | |
971 | permutation_size = 1; | |
972 | smallest_possible_size = 0; | |
973 | largest_possible_size = value_size; | |
974 | has_asterisk = TRUE; | |
975 | } | |
976 | ||
977 | unsigned int temp_size = smallest_possible_size; | |
978 | ||
979 | { | |
980 | //this is to make match_set_of incremental, | |
981 | // we store the already found pairs in this vector | |
982 | // so we wouldn't try to find a pair for those templates again | |
983 | // and we can set the covered state of values too | |
984 | // to not waste memory it is only created if needed | |
985 | int* pair_list = NULL; | |
986 | unsigned int old_temp_size = 0; | |
987 | ||
988 | if(!already_superset) | |
989 | { | |
990 | pair_list = new int[permutation_size]; | |
991 | for(unsigned int i = 0 ; i < permutation_size; i++) | |
992 | { | |
993 | //in the beginning we haven't found a template to any values | |
994 | pair_list[i] = -1; | |
995 | } | |
996 | } | |
997 | ||
998 | while(!already_superset) | |
999 | { | |
1000 | //must be a permutation having other values than asterisks | |
1001 | ||
1002 | int x = 0; | |
1003 | ||
1004 | //our set matching is extended with 2 more parameters | |
1005 | // giving back how many templates | |
1006 | // (other than asterisk) couldn't be matched | |
1007 | // and setting / giving back the value-template pairs | |
1008 | ||
1009 | boolean found = match_set_of_internal(value_ptr, value_start_index, | |
1010 | temp_size, template_ptr, | |
1011 | template_start_index, permutation_size, | |
3abe9331 | 1012 | match_function, SUPERSET, &x, pair_list,old_temp_size, legacy); |
970ed795 EL |
1013 | |
1014 | if(found) | |
1015 | { | |
1016 | already_superset = TRUE; | |
1017 | }else{ | |
1018 | //as we didn't found a match we have to try | |
1019 | // a larger set of values | |
1020 | //x is the number of templates we couldn't find | |
1021 | // a matching pair for | |
1022 | // the next must be at least this big to fully cover | |
1023 | // on the other side if it would be bigger than it might miss | |
1024 | // the smallest possible match. | |
1025 | ||
1026 | //if we can match with more values | |
1027 | if(has_asterisk && temp_size + x <= largest_possible_size) | |
1028 | { | |
1029 | old_temp_size = temp_size; | |
1030 | temp_size += x; | |
1031 | }else{ | |
1032 | delete[] pair_list; | |
1033 | return FAILURE; //else we failed | |
1034 | } | |
1035 | } | |
1036 | } | |
1037 | ||
1038 | delete[] pair_list; | |
1039 | } | |
1040 | ||
1041 | //we reach here only if we found a match | |
1042 | ||
1043 | //can only go on recursively if we haven't reached the end | |
1044 | ||
1045 | //reached the end of templates | |
1046 | if(permutation_size == template_size) | |
1047 | { | |
1048 | if(has_asterisk || value_size == temp_size) | |
1049 | return SUCCESS; | |
1050 | else | |
1051 | return FAILURE; | |
1052 | } | |
1053 | ||
1054 | for(unsigned int i = temp_size; i <= largest_possible_size;) | |
1055 | { | |
1056 | answer result; | |
1057 | ||
1058 | if(is_asterisk) | |
1059 | { | |
1060 | //don't step the permutation index | |
1061 | result = recursive_permutation_match(value_ptr,value_start_index+i, | |
1062 | value_size - i, template_ptr, | |
1063 | template_start_index + | |
1064 | permutation_size, | |
1065 | template_size - | |
1066 | permutation_size, | |
1067 | permutation_index, | |
3abe9331 | 1068 | match_function, shift_size, legacy); |
970ed795 EL |
1069 | }else{ |
1070 | //try with the next permutation | |
1071 | result = recursive_permutation_match(value_ptr,value_start_index+i, | |
1072 | value_size - i, template_ptr, | |
1073 | template_start_index + | |
1074 | permutation_size, | |
1075 | template_size - permutation_size, | |
1076 | permutation_index + 1, | |
3abe9331 | 1077 | match_function, shift_size, legacy); |
970ed795 EL |
1078 | } |
1079 | ||
1080 | if(result == SUCCESS) | |
1081 | return SUCCESS; //we finished | |
1082 | else if(result == NO_CHANCE) | |
1083 | return NO_CHANCE; //matching is not possible | |
1084 | else if(i == value_size) //we failed | |
1085 | { | |
1086 | //if there is no chance of matching | |
1087 | return NO_CHANCE; | |
1088 | }else{ | |
1089 | i += shift_size > 1 ? shift_size : 1; | |
1090 | ||
1091 | if(i > largest_possible_size) | |
1092 | shift_size = i - largest_possible_size; | |
1093 | else | |
1094 | shift_size = 0; | |
1095 | } | |
1096 | } | |
1097 | ||
1098 | //this level failed; | |
1099 | return FAILURE; | |
1100 | }else{ | |
1101 | //we are at the beginning of a non permutation, non asterisk interval | |
1102 | ||
1103 | //the distance to the next permutation or the end of templates | |
1104 | // so the longest possible match | |
1105 | unsigned int distance; | |
1106 | ||
1107 | if (permutation_index < nof_permutations) | |
1108 | { | |
1109 | distance = template_ptr->get_permutation_start(permutation_index) | |
1110 | - template_start_index; | |
1111 | }else{ | |
1112 | distance = template_size; | |
1113 | } | |
1114 | ||
1115 | //if there are no more values, but we still have templates | |
1116 | // and the template is not an asterisk or a permutation start | |
1117 | if(value_size == 0) | |
1118 | return FAILURE; | |
1119 | ||
1120 | //we try to match as many values as possible | |
1121 | //an asterisk is handled like a 0 length permutation | |
1122 | boolean good; | |
1123 | unsigned int i = 0; | |
1124 | do{ | |
1125 | good = match_function(value_ptr, value_start_index + i, | |
3abe9331 | 1126 | template_ptr, template_start_index + i, legacy); |
970ed795 EL |
1127 | i++; |
1128 | //bad stop: something can't be matched | |
1129 | //half bad half good stop: the end of values is reached | |
1130 | //good stop: matching on the full distance or till an asterisk | |
1131 | }while(good && i < value_size && i < distance && | |
1132 | !match_function(value_ptr, -1, template_ptr, | |
3abe9331 | 1133 | template_start_index + i, legacy)); |
970ed795 EL |
1134 | |
1135 | //if we matched on the full distance or till an asterisk | |
1136 | if(good && (i == distance || | |
1137 | match_function(value_ptr, -1, template_ptr, | |
3abe9331 | 1138 | template_start_index + i, legacy))) |
970ed795 EL |
1139 | { |
1140 | //reached the end of the templates | |
1141 | if(i == template_size) | |
1142 | { | |
1143 | if(i < value_size) | |
1144 | { | |
1145 | //the next level would return FAILURE so we don't step it | |
1146 | return FAILURE; | |
1147 | }else{ | |
1148 | //i == value_size, so we matched everything | |
1149 | return SUCCESS; | |
1150 | } | |
1151 | }else{ | |
1152 | //we reached the next asterisk or permutation, | |
1153 | // so step to the next level | |
1154 | return recursive_permutation_match(value_ptr,value_start_index + i, | |
1155 | value_size - i, | |
1156 | template_ptr, | |
1157 | template_start_index + i, | |
1158 | template_size - i, | |
1159 | permutation_index, | |
3abe9331 | 1160 | match_function, shift_size, legacy); |
970ed795 EL |
1161 | } |
1162 | }else{ | |
1163 | //something bad happened, so we have to check how bad the situation is | |
1164 | if( i == value_size) | |
1165 | { | |
1166 | //the aren't values left, meaning that the match is not possible | |
1167 | return NO_CHANCE; | |
1168 | }else{ | |
1169 | //we couldn't match, but there is still a chance of matching | |
1170 | ||
1171 | //try to find a matching value for the last checked (and failed) | |
1172 | // template. | |
1173 | // smaller jumps would fail so we skip them | |
1174 | shift_size = 0; | |
1175 | i--; | |
1176 | do{ | |
1177 | good = match_function(value_ptr, | |
1178 | value_start_index + i + shift_size, | |
3abe9331 | 1179 | template_ptr, template_start_index + i, legacy); |
970ed795 EL |
1180 | shift_size++; |
1181 | }while(!good && i + shift_size < value_size); | |
1182 | ||
1183 | if(good) | |
1184 | { | |
1185 | shift_size--; | |
1186 | return FAILURE; | |
1187 | }else{ | |
1188 | // the template can not be matched later | |
1189 | return NO_CHANCE; | |
1190 | } | |
1191 | } | |
1192 | } | |
1193 | } | |
1194 | } | |
1195 | ||
1196 | /* | |
1197 | outer function calling the real recursive_permutation_match | |
1198 | ||
1199 | if we know that there is no need for the permutation matching | |
1200 | (because there are no permutations in the array, or the whole array | |
1201 | is just one permutation), than we call appropriate matching function | |
1202 | instead of slower recursive_permutation_match. | |
1203 | */ | |
1204 | boolean match_record_of(const Base_Type *value_ptr, int value_size, | |
1205 | const Record_Of_Template *template_ptr, | |
3abe9331 | 1206 | int template_size, match_function_t match_function, boolean legacy) |
970ed795 EL |
1207 | { |
1208 | if (value_ptr == NULL || value_size < 0 || | |
1209 | template_ptr == NULL || template_size < 0 || | |
1210 | template_ptr->get_selection() != SPECIFIC_VALUE) | |
1211 | TTCN_error("Internal error: match_record_of: invalid argument."); | |
1212 | ||
1213 | unsigned int nof_permutations = template_ptr->get_number_of_permutations(); | |
1214 | // use the simplified algorithm if the template does not contain permutation | |
1215 | if (nof_permutations == 0) | |
1216 | return match_array(value_ptr, value_size, | |
3abe9331 | 1217 | template_ptr, template_size, match_function, legacy); |
970ed795 EL |
1218 | // use 'set of' matching if all template elements are grouped into one |
1219 | // permutation | |
1220 | if (nof_permutations == 1 && template_ptr->get_permutation_start(0) == 0 && | |
1221 | template_ptr->get_permutation_end(0) == | |
1222 | (unsigned int)(template_size - 1)) | |
1223 | return match_set_of(value_ptr, value_size, template_ptr, template_size, | |
3abe9331 | 1224 | match_function, legacy); |
970ed795 EL |
1225 | |
1226 | unsigned int shift_size = 0; | |
1227 | return recursive_permutation_match(value_ptr, 0, value_size, template_ptr, | |
3abe9331 | 1228 | 0, template_size, 0, match_function, shift_size, legacy) == SUCCESS; |
970ed795 EL |
1229 | } |
1230 | ||
1231 | boolean match_set_of(const Base_Type *value_ptr, int value_size, | |
1232 | const Restricted_Length_Template *template_ptr, | |
3abe9331 | 1233 | int template_size, match_function_t match_function, boolean legacy) |
970ed795 EL |
1234 | { |
1235 | if (value_ptr == NULL || value_size < 0 || | |
1236 | template_ptr == NULL || template_size < 0) | |
1237 | TTCN_error("Internal error: match_set_of: invalid argument."); | |
1238 | type_of_matching match_type = EXACT; | |
1239 | switch (template_ptr->get_selection()) { | |
1240 | case SPECIFIC_VALUE: | |
1241 | match_type = EXACT; | |
1242 | break; | |
1243 | case SUPERSET_MATCH: | |
1244 | match_type = SUPERSET; | |
1245 | break; | |
1246 | case SUBSET_MATCH: | |
1247 | match_type = SUBSET; | |
1248 | break; | |
1249 | default: | |
1250 | TTCN_error("Internal error: match_set_of: invalid matching type."); | |
1251 | } | |
1252 | return match_set_of_internal(value_ptr, 0, value_size, template_ptr, 0, | |
3abe9331 | 1253 | template_size, match_function, match_type, NULL, NULL, 0, legacy); |
970ed795 EL |
1254 | } |
1255 | ||
1256 | void log_match_heuristics(const Base_Type *value_ptr, int value_size, | |
1257 | const Restricted_Length_Template *template_ptr, | |
1258 | int template_size, | |
1259 | match_function_t match_function, | |
3abe9331 | 1260 | log_function_t log_function, boolean legacy) |
970ed795 EL |
1261 | { |
1262 | if (value_ptr == NULL || value_size < 0 || | |
1263 | template_ptr == NULL || template_size < 0 || | |
1264 | template_ptr->get_selection() != SPECIFIC_VALUE) | |
1265 | TTCN_error("Internal error: log_match_heuristics: invalid argument."); | |
1266 | ||
1267 | if (value_size == 0 && template_size == 0) return; | |
1268 | ||
1269 | if (!template_ptr->match_length(value_size)) { | |
1270 | TTCN_Logger::log_event("Length restriction cannot be satisfied. "); | |
1271 | return; | |
1272 | } | |
1273 | ||
1274 | int asterisks_found = 0; | |
1275 | for (int i = 0; i < template_size; i++) | |
1276 | { | |
1277 | // If j == -1, check whether the template element is an asterisk. | |
1278 | // There is no problem if an asterisk has no matching pair. | |
3abe9331 | 1279 | if (match_function(value_ptr, -1, template_ptr, i, legacy)) |
970ed795 EL |
1280 | { |
1281 | asterisks_found++; | |
1282 | } | |
1283 | } | |
1284 | ||
1285 | if(value_size < template_size - asterisks_found){ | |
1286 | TTCN_Logger::print_logmatch_buffer(); | |
1287 | if(asterisks_found == 0){ | |
1288 | TTCN_Logger::log_event(" Too few elements in value are present: %d was expected instead of %d", template_size, value_size); | |
1289 | }else{ | |
1290 | TTCN_Logger::log_event(" Too few value elements are present in value: at least %d was expected instead of %d", template_size-asterisks_found, value_size); | |
1291 | } | |
1292 | return; | |
1293 | }else if(asterisks_found == 0 && value_size > template_size){ | |
1294 | TTCN_Logger::print_logmatch_buffer(); | |
1295 | TTCN_Logger::log_event(" Too many elements are present in value: %d was expected instead of %d", template_size, value_size); | |
1296 | return; | |
1297 | } | |
1298 | ||
1299 | if (value_size == 0 || template_size == 0) return; | |
1300 | ||
1301 | if(TTCN_Logger::VERBOSITY_COMPACT != TTCN_Logger::get_matching_verbosity()){ | |
1302 | TTCN_Logger::log_event_str(" Some hints to find the reason of mismatch: "); | |
1303 | TTCN_Logger::log_event_str("{ value elements that have no pairs in the template: "); | |
1304 | } | |
1305 | ||
1306 | boolean value_found = FALSE; | |
1307 | int nof_unmatched_values = 0; | |
1308 | bool *unmatched_values = new bool[value_size]; | |
1309 | for (int i = 0; i < value_size; i++) | |
1310 | { | |
1311 | boolean pair_found = FALSE; | |
1312 | for (int j = 0; j < template_size; j++) | |
1313 | { | |
3abe9331 | 1314 | if (match_function(value_ptr, i, template_ptr, j, legacy)) |
970ed795 EL |
1315 | { |
1316 | pair_found = TRUE; | |
1317 | break; | |
1318 | } | |
1319 | } | |
1320 | ||
1321 | unmatched_values[i] = !pair_found; | |
1322 | if (!pair_found) | |
1323 | { | |
1324 | if(TTCN_Logger::VERBOSITY_COMPACT != TTCN_Logger::get_matching_verbosity()){ | |
1325 | if (value_found) | |
1326 | TTCN_Logger::log_event_str(", "); | |
1327 | else | |
1328 | value_found = TRUE; | |
1329 | ||
3abe9331 | 1330 | log_function(value_ptr, NULL, i, 0, legacy); |
970ed795 EL |
1331 | TTCN_Logger::log_event(" at index %d", i); |
1332 | } | |
1333 | nof_unmatched_values++; | |
1334 | } | |
1335 | } | |
1336 | ||
1337 | if(TTCN_Logger::VERBOSITY_COMPACT != TTCN_Logger::get_matching_verbosity()){ | |
1338 | if (!value_found) TTCN_Logger::log_event_str("none"); | |
1339 | TTCN_Logger::log_event_str(", template elements that have no pairs in " | |
1340 | "the value: "); | |
1341 | } | |
1342 | ||
1343 | boolean template_found = FALSE; | |
1344 | int nof_unmatched_templates = 0; | |
1345 | bool *unmatched_templates = new bool[template_size]; | |
1346 | for (int i = 0; i < template_size; i++) | |
1347 | { | |
1348 | boolean pair_found = FALSE; | |
1349 | // if j == -1 it is checked whether the template element is an | |
1350 | // asterisk there is no problem if an asterisk has no matching | |
1351 | // pair | |
1352 | for (int j = -1; j < value_size; j++) | |
1353 | { | |
3abe9331 | 1354 | if (match_function(value_ptr, j, template_ptr, i, legacy)) |
970ed795 EL |
1355 | { |
1356 | pair_found = TRUE; | |
1357 | break; | |
1358 | } | |
1359 | } | |
1360 | unmatched_templates[i] = !pair_found; | |
1361 | if (!pair_found) | |
1362 | { | |
1363 | if(TTCN_Logger::VERBOSITY_COMPACT != TTCN_Logger::get_matching_verbosity()){ | |
1364 | if (template_found) | |
1365 | TTCN_Logger::log_event_str(", "); | |
1366 | else | |
1367 | template_found = TRUE; | |
1368 | ||
3abe9331 | 1369 | log_function(NULL, template_ptr, 0, i, legacy); |
970ed795 EL |
1370 | TTCN_Logger::log_event(" at index %d", i); |
1371 | } | |
1372 | nof_unmatched_templates++; | |
1373 | } | |
1374 | } | |
1375 | ||
1376 | if(TTCN_Logger::VERBOSITY_COMPACT != TTCN_Logger::get_matching_verbosity()){ | |
1377 | if (!template_found) TTCN_Logger::log_event_str("none"); | |
1378 | ||
1379 | TTCN_Logger::log_event_str(", matching value <-> template index pairs: "); | |
1380 | boolean pair_found = FALSE; | |
1381 | for (int i = 0; i < value_size; i++) | |
1382 | { | |
1383 | for (int j = 0; j < template_size; j++) | |
1384 | { | |
3abe9331 | 1385 | if (match_function(value_ptr, i, template_ptr, j, legacy)) |
970ed795 EL |
1386 | { |
1387 | if (pair_found) | |
1388 | TTCN_Logger::log_char(','); | |
1389 | else { | |
1390 | TTCN_Logger::log_char('{'); | |
1391 | pair_found = TRUE; | |
1392 | } | |
1393 | TTCN_Logger::log_event(" %d <-> %d", i, j); | |
1394 | } | |
1395 | } | |
1396 | } | |
1397 | if (pair_found) TTCN_Logger::log_event_str(" }"); | |
1398 | else TTCN_Logger::log_event_str("none"); | |
1399 | } | |
1400 | ||
1401 | if(nof_unmatched_templates > 0 && nof_unmatched_values > 0){ | |
1402 | if(TTCN_Logger::VERBOSITY_COMPACT == TTCN_Logger::get_matching_verbosity()){ | |
1403 | int previous_size = TTCN_Logger::get_logmatch_buffer_len(); | |
1404 | for (int i = 0; i < value_size; i++) | |
1405 | { | |
1406 | if(unmatched_values[i]){ | |
1407 | for (int j = 0; j < template_size; j++) | |
1408 | { | |
1409 | if(unmatched_templates[j]){ | |
1410 | TTCN_Logger::log_logmatch_info("[%d <-> %d]", i, j); | |
3abe9331 | 1411 | log_function(value_ptr, template_ptr, i, j, legacy); |
970ed795 EL |
1412 | |
1413 | TTCN_Logger::set_logmatch_buffer_len(previous_size); | |
1414 | } | |
1415 | } | |
1416 | } | |
1417 | } | |
1418 | }else{ | |
1419 | TTCN_Logger::log_event_str(", matching unmatched value <-> template index pairs: "); | |
1420 | char sep = '{'; | |
1421 | for (int i = 0; i < value_size; i++) | |
1422 | { | |
1423 | if(unmatched_values[i]){ | |
1424 | for (int j = 0; j < template_size; j++) | |
1425 | { | |
1426 | if(unmatched_templates[j]){ | |
1427 | TTCN_Logger::log_event("%c %d <-> %d:{ ", sep, i, j); | |
1428 | if('{' == sep){ | |
1429 | sep = ','; | |
1430 | } | |
3abe9331 | 1431 | log_function(value_ptr, template_ptr, i, j, legacy); |
970ed795 EL |
1432 | TTCN_Logger::log_event_str(" }"); |
1433 | } | |
1434 | } | |
1435 | } | |
1436 | } | |
1437 | ||
1438 | TTCN_Logger::log_event_str(" }"); | |
1439 | } | |
1440 | } | |
1441 | delete [] unmatched_values; | |
1442 | delete [] unmatched_templates; | |
1443 | if(TTCN_Logger::VERBOSITY_COMPACT != TTCN_Logger::get_matching_verbosity()) | |
1444 | TTCN_Logger::log_event_str(" }"); | |
1445 | } |