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