1 ///////////////////////////////////////////////////////////////////////////////
2 // Copyright (c) 2000-2015 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 #include "Struct_of.hh"
10 #include "../common/memory.h"
13 #include "Template.hh"
15 #include "../common/dbgnew.hh"
18 void **allocate_pointers(int n_elements
)
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
;
26 void **reallocate_pointers(void **old_pointer
, int old_n_elements
,
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
;
35 void free_pointers(void **old_pointer
)
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);
46 - Arguments left_ptr and right_ptr shall point to the operands of comparison.
47 They are handled transparently by the comparison function.
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.
52 - In case of invalid value pointers, index overflow or negative indices the
53 behaviour of the function is undefined.
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
)
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
)
65 if (left_size
< 0 || right_size
< 0 ||
66 left_ptr
== NULL
|| right_ptr
== NULL
)
68 TTCN_error("Internal error: compare_set_of: invalid argument.");
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
;
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
));
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;
87 for(left_index
= 0; left_index
< left_size
; left_index
++)
90 for(right_index
=first_on_right
;right_index
<=last_on_right
;right_index
++)
92 if(!covered
[right_index
]
93 && compare_function(left_ptr
, left_index
, right_ptr
, right_index
))
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
]){}
109 //if we can't find a pair to any of the elements, the sets can not
117 //if we found a pair to all the elements then they are the same
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);
129 - Arguments value_ptr and template_ptr shall point to the corresponding
130 value and template object. They are handled transparently by the matching
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.
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.
141 - Otherwise (in case of invalid pointers, index overflow or negative
142 template_index) the behaviour of the function is undefined.
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
150 boolean
match_array(const Base_Type
*value_ptr
, int value_size
,
151 const Restricted_Length_Template
*template_ptr
, int template_size
,
152 match_function_t match_function
, boolean legacy
)
154 if (value_ptr
== NULL
|| value_size
< 0 || template_ptr
== NULL
||
156 TTCN_error("Internal error: match_array: invalid argument.");
158 // the empty template matches the empty value only
159 if (template_size
== 0) return value_size
== 0;
161 int template_index
= 0;//the index of the template we are examining
163 if (value_size
== 0){
164 //We matched if the remaining templates are
166 while(template_index
< template_size
&&
167 match_function(value_ptr
, -1, template_ptr
, template_index
, legacy
))
170 return template_index
== template_size
;
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;
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
185 if(match_function(value_ptr
, -1, template_ptr
, template_index
, legacy
))
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
;
191 else if(match_function(value_ptr
, value_index
, template_ptr
, template_index
,
194 //if we found a matching pair we step in both
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
;
206 if(value_index
== value_size
&& template_index
== template_size
)
210 } else if(template_index
== template_size
)
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
215 if(match_function(value_ptr
, -1, template_ptr
, template_index
-1, legacy
)) {
216 //if the templates last element is an asterisk it eats up the values
218 } else if (last_asterisk
== -1){
219 //if there were no asterisk the match failed
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
;
226 } else if(value_index
== value_size
)
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
232 while(template_index
< template_size
&&
233 match_function(value_ptr
, -1, template_ptr
, template_index
, legacy
))
236 return template_index
== template_size
;
241 /* Ancillary classes for 'set of' matching */
245 enum edge_status
{ UNKNOWN
, NO_EDGE
, EDGE
, PAIRS
};
247 /* Class Matching_Table:
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).
259 class Matching_Table
{
260 match_function_t match_function
;
266 int *template_index_table
;
267 edge_status
**edge_matrix
;
268 boolean
*covered_vector
; //tells if a value is covered
271 //if the value is covered, then tells by whom it is covered
272 int *covered_index_vector
;
274 int *paired_templates
;
276 //the matching function requires these pointers
277 const Base_Type
*value_ptr
;
279 //they are allocated and freed outside
280 const Restricted_Length_Template
*template_ptr
;
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
,
288 match_function_t par_match_function
, boolean par_legacy
)
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
;
298 nof_covered
= 0;//to get rid of the linear summing
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
++)
306 if(match_function(value_ptr
, -1,template_ptr
, par_template_start
+i
, legacy
))
308 else template_index_table
[i
- n_asterisks
] = i
;
310 // don't count the asterisks
311 template_size
= par_template_size
- n_asterisks
;
314 covered_vector
= NULL
;
315 covered_index_vector
= NULL
;
316 paired_templates
= NULL
;
321 delete [] template_index_table
;
322 if (edge_matrix
!= NULL
)
324 for (int i
= 0; i
< template_size
; i
++) delete [] edge_matrix
[i
];
325 delete [] edge_matrix
;
327 delete [] covered_vector
;
328 delete [] covered_index_vector
;
329 delete [] paired_templates
;
332 int get_template_size() const { return template_size
; }
334 boolean
has_asterisk() const { return n_asterisks
> 0; }
338 edge_matrix
= new edge_status
*[template_size
];
339 for (int i
= 0; i
< template_size
; i
++)
341 edge_matrix
[i
] = new edge_status
[value_size
];
342 for (int j
= 0; j
< value_size
; j
++) edge_matrix
[i
][j
] = UNKNOWN
;
344 covered_vector
= new boolean
[value_size
];
345 for (int j
= 0; j
< value_size
; j
++) covered_vector
[j
] = FALSE
;
347 paired_templates
= new int[template_size
];
348 for(int j
= 0; j
< template_size
; j
++) paired_templates
[j
] = -1;
350 covered_index_vector
= new int[value_size
];
353 edge_status
get_edge(int template_index
, int value_index
)
355 if (edge_matrix
[template_index
][value_index
] == UNKNOWN
)
357 if (match_function(value_ptr
, value_start
+ value_index
,
359 template_start
+ template_index_table
[template_index
], legacy
))
361 edge_matrix
[template_index
][value_index
] = EDGE
;
363 edge_matrix
[template_index
][value_index
] = NO_EDGE
;
366 return edge_matrix
[template_index
][value_index
];
369 void set_edge(int template_index
, int value_index
, edge_status new_status
)
371 edge_matrix
[template_index
][value_index
] = new_status
;
374 boolean
is_covered(int value_index
) const
376 return covered_vector
[value_index
];
379 int covered_by(int value_index
) const
381 return covered_index_vector
[value_index
];
384 int get_nof_covered() const
389 void set_covered(int value_index
, int template_index
)
391 if(!covered_vector
[value_index
])
394 covered_vector
[value_index
] = TRUE
;
395 covered_index_vector
[value_index
] = template_index
;
398 boolean
is_paired(int j
)
400 return paired_templates
[j
] != -1;
403 void set_paired(int j
, int i
)
405 paired_templates
[j
] = i
;
408 int get_paired(int j
)
410 return paired_templates
[j
];
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.
428 /* Elements of the tree-list. */
431 List_elem
*next
, *parent
;
435 Tree_list(int head_data
)
437 head
.data
= head_data
;
445 for (List_elem
*ptr
= head
.next
; ptr
!= NULL
; )
447 List_elem
*next
= ptr
->next
;
453 void insert_data(int new_data
)
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
;
464 if (current
->parent
!= NULL
) current
= current
->parent
;
469 if (current
->next
!= NULL
) current
= current
->next
;
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
; }
477 boolean
do_exists(int find_data
) const
479 for (const List_elem
*ptr
= &head
; ptr
!= NULL
; ptr
= ptr
->next
)
480 if (ptr
->data
== find_data
) return TRUE
;
487 /* Generic matching function for 'set of' values. The interpretation
488 * of third argument is the same as for 'record of'.
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.
500 The algorithm. For all elements in A the following:
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:
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.
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.
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.
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.
541 match_set_of implements a set matching algorithm using graphs.
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.
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
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).
557 In the beginning it makes some checks to see if we can quickly deny matching.
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
562 If no new matching elements can be found than:
563 -if the matching requirements (subset) allows this, we step to the next
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
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).
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).
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.
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
,
596 unsigned int number_of_checked
, boolean legacy
)
598 Matching_Table
table(value_ptr
, value_start
, value_size
,
599 template_ptr
, template_start
, template_size
,
600 match_function
, legacy
);
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();
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
;
612 if(match_type
== SUBSET
&& real_template_size
< template_size
)
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
;
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
);
630 // let's start the real work
632 // allocate some memory
633 table
.create_matrix();
635 //if we need increamentality
637 if(pair_list
!= NULL
)
638 for(int i
= 0; i
< template_size
; i
++)
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)
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
);
650 for(int template_index
= 0;
651 template_index
< real_template_size
;
654 if(table
.is_paired(template_index
))
657 boolean found_route
= FALSE
;
658 Tree_list
tree(template_index
);
659 for (int i
= template_index
; ; )
662 if(table
.is_paired(i
))
663 j
= table
.get_paired(i
)+1;
665 j
= number_of_checked
;
667 for(; j
< value_size
; j
++)
669 //if it is not covered
670 if(!table
.is_covered(j
))
672 //if it is not covered then it might be good
673 if (table
.get_edge(i
, j
) == EDGE
)
675 //update the values in the tree
676 // and in the other structures
677 int new_value_index
= j
;
678 int temp_value_index
;
680 boolean at_end
= FALSE
;
683 at_end
= tree
.is_head();
684 actual_node
= tree
.actual_data();
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
);
690 table
.set_paired(actual_node
,new_value_index
);
692 if(pair_list
!= NULL
)
693 pair_list
[actual_node
] = new_value_index
;
695 table
.set_edge(actual_node
, new_value_index
, PAIRS
);
696 table
.set_covered(new_value_index
,actual_node
);
698 new_value_index
= temp_value_index
;
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
)
717 if (found_route
) break;
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
723 for(j
= 0 ; j
< value_size
; j
++)
725 if(table
.is_covered(j
) &&
726 table
.get_edge(i
,j
) == EDGE
&&
727 !tree
.do_exists(j
+ real_template_size
))
729 int temp_index
= table
.covered_by(j
);
730 if(!tree
.do_exists(temp_index
))
732 tree
.insert_data(temp_index
);
737 if (!tree
.end_of_list()) {
738 // continue with the next element
740 i
= tree
.actual_data();
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
)
748 //every template has to match in SUPERSET matching
749 if(match_type
== SUPERSET
)
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
)
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
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
770 int number_of_pairs
= table
.get_nof_covered();
772 if(match_type
== SUBSET
)
774 if(number_of_pairs
== value_size
)
780 //here EXACT can only be true or we would have return false earlier
781 if(match_type
== EXACT
) return TRUE
;
783 if(match_type
== SUPERSET
)
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
)
789 *number_of_uncovered
= real_template_size
- number_of_pairs
;
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
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
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.
812 The algorithm is recursive so we will give the general working for one
813 level, which is what all the levels do.
815 At each level the algorithm is called with some left over of both arrays
816 and tries to match them.
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.
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.
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.
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
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.
845 There are some speedups:
846 -in permutation matching:
847 -we estimate how small or large the matching set can be in
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.
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
,
870 unsigned int& shift_size
,
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.");
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.",
888 if(template_size
== 0)
890 //reached the end of templates
891 // if we reached the end of values => good
899 //are we at an asterisk or at the beginning of a permutation interval
901 boolean permutation_begins
= permutation_index
< nof_permutations
&&
902 template_start_index
==
903 template_ptr
->get_permutation_start(permutation_index
);
905 if (permutation_begins
||
906 match_function(value_ptr
, -1, template_ptr
, template_start_index
, legacy
))
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
;
914 //check how many values might be associated with this permutation
915 //if we are at a permutation start
916 if (permutation_begins
)
920 template_ptr
->get_permutation_size(permutation_index
);
921 smallest_possible_size
= 0;
922 has_asterisk
= FALSE
;
924 //count how many non asterisk elements are in the permutation
925 for(unsigned int i
= 0; i
< permutation_size
; i
++)
927 if(match_function(value_ptr
, -1, template_ptr
,
928 i
+ template_start_index
, legacy
))
932 smallest_possible_size
++;
936 //the real permutation size is bigger then the value size
937 if(smallest_possible_size
> value_size
)
940 //if the permutation has an asterisk then it can grow
943 largest_possible_size
= value_size
;
945 //if there are only asterisks in the permutation
946 if(smallest_possible_size
== 0)
947 already_superset
= TRUE
;
949 already_superset
= FALSE
;
951 //without asterisks its size is fixed
952 largest_possible_size
= smallest_possible_size
;
953 already_superset
= FALSE
;
958 already_superset
= TRUE
;
959 permutation_size
= 1;
960 smallest_possible_size
= 0;
961 largest_possible_size
= value_size
;
965 unsigned int temp_size
= smallest_possible_size
;
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;
976 if(!already_superset
)
978 pair_list
= new int[permutation_size
];
979 for(unsigned int i
= 0 ; i
< permutation_size
; i
++)
981 //in the beginning we haven't found a template to any values
986 while(!already_superset
)
988 //must be a permutation having other values than asterisks
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
997 boolean found
= match_set_of_internal(value_ptr
, value_start_index
,
998 temp_size
, template_ptr
,
999 template_start_index
, permutation_size
,
1000 match_function
, SUPERSET
, &x
, pair_list
,old_temp_size
, legacy
);
1004 already_superset
= TRUE
;
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.
1014 //if we can match with more values
1015 if(has_asterisk
&& temp_size
+ x
<= largest_possible_size
)
1017 old_temp_size
= temp_size
;
1021 return FAILURE
; //else we failed
1029 //we reach here only if we found a match
1031 //can only go on recursively if we haven't reached the end
1033 //reached the end of templates
1034 if(permutation_size
== template_size
)
1036 if(has_asterisk
|| value_size
== temp_size
)
1042 for(unsigned int i
= temp_size
; i
<= largest_possible_size
;)
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
+
1056 match_function
, shift_size
, legacy
);
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
+
1063 template_size
- permutation_size
,
1064 permutation_index
+ 1,
1065 match_function
, shift_size
, legacy
);
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
1074 //if there is no chance of matching
1077 i
+= shift_size
> 1 ? shift_size
: 1;
1079 if(i
> largest_possible_size
)
1080 shift_size
= i
- largest_possible_size
;
1086 //this level failed;
1089 //we are at the beginning of a non permutation, non asterisk interval
1091 //the distance to the next permutation or the end of templates
1092 // so the longest possible match
1093 unsigned int distance
;
1095 if (permutation_index
< nof_permutations
)
1097 distance
= template_ptr
->get_permutation_start(permutation_index
)
1098 - template_start_index
;
1100 distance
= template_size
;
1103 //if there are no more values, but we still have templates
1104 // and the template is not an asterisk or a permutation start
1108 //we try to match as many values as possible
1109 //an asterisk is handled like a 0 length permutation
1113 good
= match_function(value_ptr
, value_start_index
+ i
,
1114 template_ptr
, template_start_index
+ i
, legacy
);
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
,
1121 template_start_index
+ i
, legacy
));
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
,
1126 template_start_index
+ i
, legacy
)))
1128 //reached the end of the templates
1129 if(i
== template_size
)
1133 //the next level would return FAILURE so we don't step it
1136 //i == value_size, so we matched everything
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
,
1145 template_start_index
+ i
,
1148 match_function
, shift_size
, legacy
);
1151 //something bad happened, so we have to check how bad the situation is
1152 if( i
== value_size
)
1154 //the aren't values left, meaning that the match is not possible
1157 //we couldn't match, but there is still a chance of matching
1159 //try to find a matching value for the last checked (and failed)
1161 // smaller jumps would fail so we skip them
1165 good
= match_function(value_ptr
,
1166 value_start_index
+ i
+ shift_size
,
1167 template_ptr
, template_start_index
+ i
, legacy
);
1169 }while(!good
&& i
+ shift_size
< value_size
);
1176 // the template can not be matched later
1185 outer function calling the real recursive_permutation_match
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.
1192 boolean
match_record_of(const Base_Type
*value_ptr
, int value_size
,
1193 const Record_Of_Template
*template_ptr
,
1194 int template_size
, match_function_t match_function
, boolean legacy
)
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.");
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
,
1205 template_ptr
, template_size
, match_function
, legacy
);
1206 // use 'set of' matching if all template elements are grouped into one
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
,
1212 match_function
, legacy
);
1214 unsigned int shift_size
= 0;
1215 return recursive_permutation_match(value_ptr
, 0, value_size
, template_ptr
,
1216 0, template_size
, 0, match_function
, shift_size
, legacy
) == SUCCESS
;
1219 boolean
match_set_of(const Base_Type
*value_ptr
, int value_size
,
1220 const Restricted_Length_Template
*template_ptr
,
1221 int template_size
, match_function_t match_function
, boolean legacy
)
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
:
1231 case SUPERSET_MATCH
:
1232 match_type
= SUPERSET
;
1235 match_type
= SUBSET
;
1238 TTCN_error("Internal error: match_set_of: invalid matching type.");
1240 return match_set_of_internal(value_ptr
, 0, value_size
, template_ptr
, 0,
1241 template_size
, match_function
, match_type
, NULL
, NULL
, 0, legacy
);
1244 void log_match_heuristics(const Base_Type
*value_ptr
, int value_size
,
1245 const Restricted_Length_Template
*template_ptr
,
1247 match_function_t match_function
,
1248 log_function_t log_function
, boolean legacy
)
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.");
1255 if (value_size
== 0 && template_size
== 0) return;
1257 if (!template_ptr
->match_length(value_size
)) {
1258 TTCN_Logger::log_event("Length restriction cannot be satisfied. ");
1262 int asterisks_found
= 0;
1263 for (int i
= 0; i
< template_size
; i
++)
1265 // If j == -1, check whether the template element is an asterisk.
1266 // There is no problem if an asterisk has no matching pair.
1267 if (match_function(value_ptr
, -1, template_ptr
, i
, legacy
))
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
);
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
);
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
);
1287 if (value_size
== 0 || template_size
== 0) return;
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: ");
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
++)
1299 boolean pair_found
= FALSE
;
1300 for (int j
= 0; j
< template_size
; j
++)
1302 if (match_function(value_ptr
, i
, template_ptr
, j
, legacy
))
1309 unmatched_values
[i
] = !pair_found
;
1312 if(TTCN_Logger::VERBOSITY_COMPACT
!= TTCN_Logger::get_matching_verbosity()){
1314 TTCN_Logger::log_event_str(", ");
1318 log_function(value_ptr
, NULL
, i
, 0, legacy
);
1319 TTCN_Logger::log_event(" at index %d", i
);
1321 nof_unmatched_values
++;
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 "
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
++)
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
1340 for (int j
= -1; j
< value_size
; j
++)
1342 if (match_function(value_ptr
, j
, template_ptr
, i
, legacy
))
1348 unmatched_templates
[i
] = !pair_found
;
1351 if(TTCN_Logger::VERBOSITY_COMPACT
!= TTCN_Logger::get_matching_verbosity()){
1353 TTCN_Logger::log_event_str(", ");
1355 template_found
= TRUE
;
1357 log_function(NULL
, template_ptr
, 0, i
, legacy
);
1358 TTCN_Logger::log_event(" at index %d", i
);
1360 nof_unmatched_templates
++;
1364 if(TTCN_Logger::VERBOSITY_COMPACT
!= TTCN_Logger::get_matching_verbosity()){
1365 if (!template_found
) TTCN_Logger::log_event_str("none");
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
++)
1371 for (int j
= 0; j
< template_size
; j
++)
1373 if (match_function(value_ptr
, i
, template_ptr
, j
, legacy
))
1376 TTCN_Logger::log_char(',');
1378 TTCN_Logger::log_char('{');
1381 TTCN_Logger::log_event(" %d <-> %d", i
, j
);
1385 if (pair_found
) TTCN_Logger::log_event_str(" }");
1386 else TTCN_Logger::log_event_str("none");
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
++)
1394 if(unmatched_values
[i
]){
1395 for (int j
= 0; j
< template_size
; j
++)
1397 if(unmatched_templates
[j
]){
1398 TTCN_Logger::log_logmatch_info("[%d <-> %d]", i
, j
);
1399 log_function(value_ptr
, template_ptr
, i
, j
, legacy
);
1401 TTCN_Logger::set_logmatch_buffer_len(previous_size
);
1407 TTCN_Logger::log_event_str(", matching unmatched value <-> template index pairs: ");
1409 for (int i
= 0; i
< value_size
; i
++)
1411 if(unmatched_values
[i
]){
1412 for (int j
= 0; j
< template_size
; j
++)
1414 if(unmatched_templates
[j
]){
1415 TTCN_Logger::log_event("%c %d <-> %d:{ ", sep
, i
, j
);
1419 log_function(value_ptr
, template_ptr
, i
, j
, legacy
);
1420 TTCN_Logger::log_event_str(" }");
1426 TTCN_Logger::log_event_str(" }");
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(" }");