Commit | Line | Data |
---|---|---|
970ed795 EL |
1 | /////////////////////////////////////////////////////////////////////////////// |
2 | // Copyright (c) 2000-2014 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 | #ifndef _Subtypestuff_HH | |
9 | #define _Subtypestuff_HH | |
10 | ||
11 | #include "ttcn3/compiler.h" | |
12 | #include "vector.hh" | |
13 | #include "map.hh" | |
14 | #include "Int.hh" | |
15 | #include "Real.hh" | |
16 | #include "ustring.hh" | |
17 | #include "Setting.hh" | |
18 | #include "../common/ttcn3float.hh" | |
19 | ||
20 | namespace Ttcn { | |
21 | class LengthRestriction; | |
22 | class Template; | |
23 | class ValueRange; | |
24 | class PatternString; | |
25 | } | |
26 | ||
27 | namespace Common { | |
28 | ||
29 | class Identifier; | |
30 | class Value; | |
31 | class Type; | |
32 | ||
33 | ||
34 | enum tribool // http://en.wikipedia.org/wiki/Ternary_logic | |
35 | { | |
36 | TFALSE = 0, // values are indexes into truth tables | |
37 | TUNKNOWN = 1, | |
38 | TTRUE = 2 | |
39 | }; | |
40 | ||
41 | extern tribool operator||(tribool a, tribool b); | |
42 | extern tribool operator&&(tribool a, tribool b); | |
43 | extern tribool operator!(tribool tb); | |
44 | extern tribool TRIBOOL(bool b); | |
45 | extern string to_string(const tribool& tb); | |
46 | ||
47 | //////////////////////////////////////////////////////////////////////////////// | |
48 | ||
49 | // integer interval limit type, can be +/- infinity, in case of infinity value has no meaning | |
50 | class int_limit_t | |
51 | { | |
52 | public: | |
53 | enum int_limit_type_t { | |
54 | MINUS_INFINITY, | |
55 | NUMBER, | |
56 | PLUS_INFINITY | |
57 | }; | |
58 | static const int_limit_t minimum; | |
59 | static const int_limit_t maximum; | |
60 | private: | |
61 | int_limit_type_t type; | |
62 | int_val_t value; | |
63 | public: | |
64 | int_limit_t(): type(NUMBER), value() {} | |
65 | int_limit_t(int_limit_type_t p_type); | |
66 | int_limit_t(const int_val_t& p_value): type(NUMBER), value(p_value) {} | |
67 | bool operator<(const int_limit_t& right) const; | |
68 | bool operator==(const int_limit_t& right) const; | |
69 | bool is_adjacent(const int_limit_t& other) const; | |
70 | int_val_t get_value() const; | |
71 | int_limit_type_t get_type() const { return type; } | |
72 | int_limit_t next() const; // upper neighbour | |
73 | int_limit_t previous() const; // lower neighbour | |
74 | void check_single_value() const; | |
75 | void check_interval_start() const; | |
76 | void check_interval_end() const; | |
77 | string to_string() const; | |
78 | }; | |
79 | ||
80 | //////////////////////////////////////////////////////////////////////////////// | |
81 | ||
82 | // limit value for length/size restriction | |
83 | class size_limit_t | |
84 | { | |
85 | public: | |
86 | enum size_limit_type_t { | |
87 | INFINITE_SIZE | |
88 | }; | |
89 | private: | |
90 | bool infinity; | |
91 | size_t size; | |
92 | public: | |
93 | static const size_limit_t minimum; | |
94 | static const size_limit_t maximum; | |
95 | size_limit_t() : infinity(false), size() {} | |
96 | size_limit_t(size_limit_type_t): infinity(true), size() {} | |
97 | size_limit_t(size_t p_size): infinity(false), size(p_size) {} | |
98 | bool operator<(const size_limit_t& right) const; | |
99 | bool operator==(const size_limit_t& right) const; | |
100 | bool is_adjacent(const size_limit_t& other) const; | |
101 | size_t get_size() const; | |
102 | bool get_infinity() const { return infinity; } | |
103 | size_limit_t next() const; | |
104 | size_limit_t previous() const; | |
105 | void check_single_value() const; | |
106 | void check_interval_start() const; | |
107 | void check_interval_end() const {} | |
108 | string to_string() const; | |
109 | int_limit_t to_int_limit() const; | |
110 | }; | |
111 | ||
112 | //////////////////////////////////////////////////////////////////////////////// | |
113 | ||
114 | // limit value for string range/alphabet restriction | |
115 | class char_limit_t | |
116 | { | |
117 | private: | |
118 | short int chr; | |
119 | static const short int max_char; | |
120 | public: | |
121 | static bool is_valid_value(short int p_chr); | |
122 | static const char_limit_t minimum; | |
123 | static const char_limit_t maximum; | |
124 | char_limit_t(): chr(0) {} | |
125 | char_limit_t(short int p_chr); | |
126 | bool operator<(const char_limit_t& right) const { return chr<right.chr; } | |
127 | bool operator==(const char_limit_t& right) const { return chr==right.chr; } | |
128 | bool is_adjacent(const char_limit_t& other) const { return (chr+1==other.chr); } | |
129 | char get_char() const { return (char)chr; } | |
130 | char_limit_t next() const; | |
131 | char_limit_t previous() const; | |
132 | void check_single_value() const {} | |
133 | void check_interval_start() const {} | |
134 | void check_interval_end() const {} | |
135 | string to_string() const; | |
136 | }; | |
137 | ||
138 | //////////////////////////////////////////////////////////////////////////////// | |
139 | ||
140 | class universal_char_limit_t | |
141 | { | |
142 | private: | |
143 | unsigned int code_point; // UCS-4 values [0..0x7FFFFFFF], for easy calculations | |
144 | static const unsigned int max_code_point; | |
145 | void check_value() const; | |
146 | public: | |
147 | static bool is_valid_value(const ustring::universal_char& p_uchr); | |
148 | static unsigned int uchar2codepoint(const ustring::universal_char& uchr); | |
149 | static ustring::universal_char codepoint2uchar(unsigned int cp); | |
150 | static const universal_char_limit_t minimum; | |
151 | static const universal_char_limit_t maximum; | |
152 | universal_char_limit_t(): code_point(0) {} | |
153 | universal_char_limit_t(unsigned int p_code_point): code_point(p_code_point) { check_value(); } | |
154 | universal_char_limit_t(const ustring::universal_char& p_chr) : code_point(uchar2codepoint(p_chr)) { check_value(); } | |
155 | bool operator<(const universal_char_limit_t& right) const { return code_point<right.code_point; } | |
156 | bool operator==(const universal_char_limit_t& right) const { return code_point==right.code_point; } | |
157 | bool is_adjacent(const universal_char_limit_t& other) const { return (code_point+1==other.code_point); } | |
158 | ustring::universal_char get_universal_char() const { return codepoint2uchar(code_point); } | |
159 | unsigned int get_code_point() const { return code_point; } | |
160 | universal_char_limit_t next() const; | |
161 | universal_char_limit_t previous() const; | |
162 | void check_single_value() const {} | |
163 | void check_interval_start() const {} | |
164 | void check_interval_end() const {} | |
165 | string to_string() const; | |
166 | }; | |
167 | ||
168 | //////////////////////////////////////////////////////////////////////////////// | |
169 | ||
170 | class real_limit_t | |
171 | { | |
172 | public: | |
173 | enum real_limit_type_t { | |
174 | LOWER, // the highest value that is less than the value, for open interval's upper limit | |
175 | EXACT, // the value itself, for closed interval limits and single values | |
176 | UPPER // the lowest value that is more than the value, for open interval's lower limit | |
177 | }; | |
178 | static const real_limit_t minimum; | |
179 | static const real_limit_t maximum; | |
180 | private: | |
181 | real_limit_type_t type; | |
182 | ttcn3float value; | |
183 | void check_value() const; // check for illegal values: NaN, -inf.lower and inf.upper | |
184 | public: | |
185 | real_limit_t(): type(EXACT), value() { value = 0.0; } // avoid random illegal values | |
186 | real_limit_t(const ttcn3float& p_value): type(EXACT), value(p_value) { check_value(); } | |
187 | real_limit_t(const ttcn3float& p_value, real_limit_type_t p_type): type(p_type), value(p_value) { check_value(); } | |
188 | ||
189 | bool operator<(const real_limit_t& right) const; | |
190 | bool operator==(const real_limit_t& right) const; | |
191 | bool is_adjacent(const real_limit_t& other) const; // two different values cannot be adjacent in a general floating point value | |
192 | ttcn3float get_value() const { return value; } | |
193 | real_limit_type_t get_type() const { return type; } | |
194 | real_limit_t next() const; // upper neighbour, has same value | |
195 | real_limit_t previous() const; // lower neighbour, has same value | |
196 | void check_single_value() const; | |
197 | void check_interval_start() const; | |
198 | void check_interval_end() const; | |
199 | string to_string() const; | |
200 | }; | |
201 | ||
202 | //////////////////////////////////////////////////////////////////////////////// | |
203 | ||
204 | // forward declaration | |
205 | template <typename LIMITTYPE> | |
206 | class RangeListConstraint; | |
207 | ||
208 | bool convert_int_to_size(const RangeListConstraint<int_limit_t>& int_range, RangeListConstraint<size_limit_t>& size_range); | |
209 | ||
210 | /* | |
211 | all-in-one constraint class template for xxx_limit_t types | |
212 | the xxx_limit_t classes must have the same interface for use by this class | |
213 | canonical form: | |
214 | - values must be v1 < v2 < v3 < ... < vN (xxx_limit_t::operator<() and xxx_limit_t::operator==() used) | |
215 | - there cannot be two adjacent intervals that are part of the set (determined by xxx_limit_t::is_adjacent()) | |
216 | - two adjacent values must make an interval (if values[i] is adjacent to values[i+1] then intervals[i] is true) | |
217 | - empty values[] means empty set | |
218 | - full set is [minimum-maximum] interval (xxx_limit_t::minimum and xxx_limit_t::maximum are used) | |
219 | */ | |
220 | template <typename LIMITTYPE> | |
221 | class RangeListConstraint | |
222 | { | |
223 | private: | |
224 | // used in calculating the union and intersection of two sets, _idx are indexes into the values[] vector of the operand sets | |
225 | struct sweep_point_t | |
226 | { | |
227 | int a_idx; // index into the operand's values/intervals vectors or -1 | |
228 | int b_idx; | |
229 | bool union_interval; // is this interval in the set | |
230 | bool intersection_interval; // is this interval in the set | |
231 | bool intersection_point; // is this point in the set | |
232 | sweep_point_t(): a_idx(-1), b_idx(-1), union_interval(false), intersection_interval(false), intersection_point(false) {} | |
233 | sweep_point_t(int a, int b): a_idx(a), b_idx(b), union_interval(false), intersection_interval(false), intersection_point(false) {} | |
234 | }; | |
235 | ||
236 | dynamic_array<LIMITTYPE> values; | |
237 | dynamic_array<bool> intervals; | |
238 | ||
239 | public: | |
240 | // constructors | |
241 | RangeListConstraint(): values(), intervals() {} // empty set | |
242 | RangeListConstraint(const LIMITTYPE& l); // single value set | |
243 | RangeListConstraint(const LIMITTYPE& l_begin, const LIMITTYPE& l_end); // value range set | |
244 | ||
245 | tribool is_empty() const; | |
246 | tribool is_full() const; | |
247 | tribool is_equal(const RangeListConstraint& other) const; | |
248 | bool is_element(const LIMITTYPE& l) const; | |
249 | ||
250 | RangeListConstraint set_operation(const RangeListConstraint& other, bool is_union) const; // A union/intersection B -> C | |
251 | RangeListConstraint operator+(const RangeListConstraint& other) const { return set_operation(other, true); } // union | |
252 | RangeListConstraint operator*(const RangeListConstraint& other) const { return set_operation(other, false); } // intersection | |
253 | RangeListConstraint operator~() const; // complement | |
254 | ||
255 | tribool is_subset(const RangeListConstraint& other) const { return (*this*~other).is_empty(); } | |
256 | RangeListConstraint operator-(const RangeListConstraint& other) const { return ( *this * ~other ); } // except | |
257 | ||
258 | // will return the minimal value that is part of the interval, | |
259 | // if the interval is empty the returned value is undefined | |
260 | LIMITTYPE get_minimal() const; | |
261 | LIMITTYPE get_maximal() const; | |
262 | ||
263 | string to_string(bool add_brackets=true) const; | |
264 | ||
265 | /** conversion from integer range to size range, | |
266 | returns true on success, false if the integers do not fit into the size values, | |
267 | when returning false the size_range will be set to the full set */ | |
268 | friend bool convert_int_to_size(const RangeListConstraint<int_limit_t>& int_range, RangeListConstraint<size_limit_t>& size_range); | |
269 | }; | |
270 | ||
271 | template <typename LIMITTYPE> | |
272 | RangeListConstraint<LIMITTYPE>::RangeListConstraint(const LIMITTYPE& l) | |
273 | : values(), intervals() | |
274 | { | |
275 | l.check_single_value(); | |
276 | values.add(l); | |
277 | intervals.add(false); | |
278 | } | |
279 | ||
280 | template <typename LIMITTYPE> | |
281 | RangeListConstraint<LIMITTYPE>::RangeListConstraint(const LIMITTYPE& l_begin, const LIMITTYPE& l_end) | |
282 | : values(), intervals() | |
283 | { | |
284 | if (l_end<l_begin) FATAL_ERROR("RangeListConstraint::RangeListConstraint(): invalid range"); | |
285 | if (l_begin==l_end) { | |
286 | l_begin.check_single_value(); | |
287 | values.add(l_begin); | |
288 | intervals.add(false); | |
289 | } else { | |
290 | l_begin.check_interval_start(); | |
291 | l_end.check_interval_end(); | |
292 | values.add(l_begin); | |
293 | intervals.add(true); | |
294 | values.add(l_end); | |
295 | intervals.add(false); | |
296 | } | |
297 | } | |
298 | ||
299 | template <typename LIMITTYPE> | |
300 | tribool RangeListConstraint<LIMITTYPE>::is_empty() const | |
301 | { | |
302 | return TRIBOOL(values.size()==0); | |
303 | } | |
304 | ||
305 | template <typename LIMITTYPE> | |
306 | tribool RangeListConstraint<LIMITTYPE>::is_full() const | |
307 | { | |
308 | return TRIBOOL( (values.size()==2) && (values[0]==LIMITTYPE::minimum) && (values[1]==LIMITTYPE::maximum) && (intervals[0]) ); | |
309 | } | |
310 | ||
311 | template <typename LIMITTYPE> | |
312 | tribool RangeListConstraint<LIMITTYPE>::is_equal(const RangeListConstraint<LIMITTYPE>& other) const | |
313 | { | |
314 | return TRIBOOL( (values==other.values) && (intervals==other.intervals) ); | |
315 | } | |
316 | ||
317 | template <typename LIMITTYPE> | |
318 | bool RangeListConstraint<LIMITTYPE>::is_element(const LIMITTYPE& l) const | |
319 | { | |
320 | if (values.size()==0) return false; | |
321 | // binary search in values[] | |
322 | size_t lower_idx = 0; | |
323 | size_t upper_idx = values.size()-1; | |
324 | while (upper_idx>lower_idx+1) { | |
325 | size_t middle_idx = lower_idx + (upper_idx-lower_idx) / 2; | |
326 | if (values[middle_idx]<l) lower_idx = middle_idx; | |
327 | else upper_idx = middle_idx; | |
328 | } | |
329 | if (lower_idx==upper_idx) { | |
330 | if (values[lower_idx]==l) return true; // every value is in the set | |
331 | else if (values[lower_idx]<l) return intervals[lower_idx]; | |
332 | else return ( (lower_idx>0) ? intervals[lower_idx-1] : false ); | |
333 | } else { | |
334 | if (l<values[lower_idx]) return ( (lower_idx>0) ? intervals[lower_idx-1] : false ); | |
335 | else if (l==values[lower_idx]) return true; | |
336 | else if (l<values[upper_idx]) return intervals[upper_idx-1]; | |
337 | else if (l==values[upper_idx]) return true; | |
338 | else return intervals[upper_idx]; | |
339 | } | |
340 | } | |
341 | ||
342 | template <typename LIMITTYPE> | |
343 | RangeListConstraint<LIMITTYPE> RangeListConstraint<LIMITTYPE>::operator~() const | |
344 | { | |
345 | if (values.size()==0) { // if we have an empty set | |
346 | return RangeListConstraint<LIMITTYPE>(LIMITTYPE::minimum, LIMITTYPE::maximum); | |
347 | } | |
348 | RangeListConstraint<LIMITTYPE> ret_val; | |
349 | // invert intervals | |
350 | if (!(values[0]==LIMITTYPE::minimum)) { | |
351 | if (LIMITTYPE::minimum.is_adjacent(values[0])) { | |
352 | ret_val.values.add(LIMITTYPE::minimum); | |
353 | ret_val.intervals.add(false); | |
354 | } else { | |
355 | ret_val.values.add(LIMITTYPE::minimum); | |
356 | ret_val.intervals.add(true); | |
357 | ret_val.values.add(values[0].previous()); | |
358 | ret_val.intervals.add(false); | |
359 | } | |
360 | } | |
361 | int last = values.size()-1; | |
362 | for (int i=0; i<last; i++) | |
363 | { | |
364 | if (!intervals[i]) { | |
365 | if (values[i].next()==values[i+1].previous()) { | |
366 | // add one value between intervals | |
367 | ret_val.values.add(values[i].next()); | |
368 | ret_val.intervals.add(false); | |
369 | } else { | |
370 | // add interval between intervals | |
371 | ret_val.values.add(values[i].next()); | |
372 | ret_val.intervals.add(true); | |
373 | ret_val.values.add(values[i+1].previous()); | |
374 | ret_val.intervals.add(false); | |
375 | } | |
376 | } | |
377 | } | |
378 | if (!(values[last]==LIMITTYPE::maximum)) { | |
379 | if (values[last].is_adjacent(LIMITTYPE::maximum)) { | |
380 | ret_val.values.add(LIMITTYPE::maximum); | |
381 | ret_val.intervals.add(false); | |
382 | } else { | |
383 | ret_val.values.add(values[last].next()); | |
384 | ret_val.intervals.add(true); | |
385 | ret_val.values.add(LIMITTYPE::maximum); | |
386 | ret_val.intervals.add(false); | |
387 | } | |
388 | } | |
389 | return ret_val; | |
390 | } | |
391 | ||
392 | template <typename LIMITTYPE> | |
393 | RangeListConstraint<LIMITTYPE> RangeListConstraint<LIMITTYPE>::set_operation(const RangeListConstraint<LIMITTYPE>& other, bool is_union) const | |
394 | { | |
395 | // special case: one or both are empty sets | |
396 | if (values.size()==0) return is_union ? other : *this; | |
397 | if (other.values.size()==0) return is_union ? *this : other; | |
398 | ||
399 | // calculate the sweep points | |
400 | dynamic_array<sweep_point_t> sweep_points; | |
401 | sweep_point_t spi(0,0); | |
402 | while ( (spi.a_idx<(int)values.size()) || (spi.b_idx<(int)other.values.size()) ) | |
403 | { | |
404 | if (spi.a_idx>=(int)values.size()) { | |
405 | sweep_points.add(sweep_point_t(-1,spi.b_idx)); | |
406 | spi.b_idx++; | |
407 | } else if (spi.b_idx>=(int)other.values.size()) { | |
408 | sweep_points.add(sweep_point_t(spi.a_idx, -1)); | |
409 | spi.a_idx++; | |
410 | } else { // both are within the vector, get smaller or get both if equal | |
411 | if (values[spi.a_idx]<other.values[spi.b_idx]) { | |
412 | sweep_points.add(sweep_point_t(spi.a_idx, -1)); | |
413 | spi.a_idx++; | |
414 | } else if (values[spi.a_idx]==other.values[spi.b_idx]) { | |
415 | sweep_points.add(spi); | |
416 | spi.a_idx++; | |
417 | spi.b_idx++; | |
418 | } else { | |
419 | sweep_points.add(sweep_point_t(-1,spi.b_idx)); | |
420 | spi.b_idx++; | |
421 | } | |
422 | } | |
423 | } | |
424 | ||
425 | // sweep (iterate) through both vectors | |
426 | bool in_a = false; // we are already in an interval of A | |
427 | bool in_b = false; | |
428 | for (int i=0; i<(int)sweep_points.size(); i++) | |
429 | { | |
430 | // set bools for A interval | |
431 | bool a_interval = in_a; | |
432 | bool a_point = false; | |
433 | if (sweep_points[i].a_idx!=-1) { // we are at a value in A | |
434 | a_point = true; | |
435 | if (intervals[sweep_points[i].a_idx]) { // this is a starting point of an interval in A | |
436 | a_interval = true; | |
437 | if (in_a) FATAL_ERROR("RangeListConstraint::set_operation(): invalid double interval"); | |
438 | in_a = true; | |
439 | } else { // this point ends an interval of A | |
440 | a_interval = false; | |
441 | in_a = false; | |
442 | } | |
443 | } | |
444 | // set bools for B interval | |
445 | bool b_interval = in_b; | |
446 | bool b_point = false; | |
447 | if (sweep_points[i].b_idx!=-1) { // we are at a value in B | |
448 | b_point = true; | |
449 | if (other.intervals[sweep_points[i].b_idx]) { // this is a starting point of an interval in B | |
450 | b_interval = true; | |
451 | if (in_b) FATAL_ERROR("RangeListConstraint::set_operation(): invalid double interval"); | |
452 | in_b = true; | |
453 | } else { // this point ends an interval of B | |
454 | b_interval = false; | |
455 | in_b = false; | |
456 | } | |
457 | } | |
458 | // set the booleans of the union and intersection sets | |
459 | sweep_points[i].union_interval = a_interval || b_interval; | |
460 | sweep_points[i].intersection_point = (a_point || in_a) && (b_point || in_b); | |
461 | sweep_points[i].intersection_interval = a_interval && b_interval; | |
462 | } | |
463 | ||
464 | // canonicalization of ret_val | |
465 | if (is_union) { | |
466 | // connect adjacent limit points with interval: [i,i+1] becomes interval | |
467 | for (int i=1; i<(int)sweep_points.size(); i++) | |
468 | { | |
469 | LIMITTYPE first, second; | |
470 | if (sweep_points[i-1].a_idx!=-1) { | |
471 | first = values[sweep_points[i-1].a_idx]; | |
472 | } else { | |
473 | if (sweep_points[i-1].b_idx!=-1) first = other.values[sweep_points[i-1].b_idx]; | |
474 | else FATAL_ERROR("RangeListConstraint::set_operation()"); | |
475 | } | |
476 | if (sweep_points[i].a_idx!=-1) { | |
477 | second = values[sweep_points[i].a_idx]; | |
478 | } else { | |
479 | if (sweep_points[i].b_idx!=-1) second = other.values[sweep_points[i].b_idx]; | |
480 | else FATAL_ERROR("RangeListConstraint::set_operation()"); | |
481 | } | |
482 | if (first.is_adjacent(second)) { | |
483 | sweep_points[i-1].union_interval = true; | |
484 | sweep_points[i-1].intersection_interval = sweep_points[i-1].intersection_point && sweep_points[i].intersection_point; | |
485 | } | |
486 | } | |
487 | } | |
488 | // two adjacent intervals shall be united into one | |
489 | RangeListConstraint<LIMITTYPE> ret_val; | |
490 | for (int i=0; i<(int)sweep_points.size(); i++) | |
491 | { | |
492 | if (is_union) { | |
493 | if ( (i>0) && sweep_points[i-1].union_interval && sweep_points[i].union_interval) { | |
494 | // drop this point, it's in a double interval | |
495 | } else { | |
496 | LIMITTYPE l; | |
497 | if (sweep_points[i].a_idx!=-1) { | |
498 | l = values[sweep_points[i].a_idx]; | |
499 | } else { | |
500 | if (sweep_points[i].b_idx!=-1) l = other.values[sweep_points[i].b_idx]; | |
501 | else FATAL_ERROR("RangeListConstraint::set_operation()"); | |
502 | } | |
503 | ret_val.values.add(l); | |
504 | ret_val.intervals.add(sweep_points[i].union_interval); | |
505 | } | |
506 | } else { | |
507 | if (sweep_points[i].intersection_point) { | |
508 | if ( (i>0) && sweep_points[i-1].intersection_interval && sweep_points[i].intersection_interval) { | |
509 | // drop this point, it's in a double interval | |
510 | } else { | |
511 | LIMITTYPE l; | |
512 | if (sweep_points[i].a_idx!=-1) { | |
513 | l = values[sweep_points[i].a_idx]; | |
514 | } else { | |
515 | if (sweep_points[i].b_idx!=-1) l = other.values[sweep_points[i].b_idx]; | |
516 | else FATAL_ERROR("RangeListConstraint::set_operation()"); | |
517 | } | |
518 | ret_val.values.add(l); | |
519 | ret_val.intervals.add(sweep_points[i].intersection_interval); | |
520 | } | |
521 | } | |
522 | } | |
523 | } | |
524 | return ret_val; | |
525 | } | |
526 | ||
527 | template <typename LIMITTYPE> | |
528 | LIMITTYPE RangeListConstraint<LIMITTYPE>::get_minimal() const | |
529 | { | |
530 | if (values.size()<1) return LIMITTYPE(); | |
531 | return values[0]; | |
532 | } | |
533 | ||
534 | template <typename LIMITTYPE> | |
535 | LIMITTYPE RangeListConstraint<LIMITTYPE>::get_maximal() const | |
536 | { | |
537 | if (values.size()<1) return LIMITTYPE(); | |
538 | return values[values.size()-1]; | |
539 | } | |
540 | ||
541 | template <typename LIMITTYPE> | |
542 | string RangeListConstraint<LIMITTYPE>::to_string(bool add_brackets) const | |
543 | { | |
544 | string ret_val; | |
545 | if (add_brackets) ret_val += '('; | |
546 | int last = values.size()-1; | |
547 | for (int i=0; i<=last; i++) | |
548 | { | |
549 | ret_val += values[i].to_string(); | |
550 | if (intervals[i]) ret_val += ".."; | |
551 | else if (i<last) ret_val += ','; | |
552 | } | |
553 | if (add_brackets) ret_val += ')'; | |
554 | return ret_val; | |
555 | } | |
556 | ||
557 | //////////////////////////////////////////////////////////////////////////////// | |
558 | ||
559 | typedef RangeListConstraint<int_limit_t> IntegerRangeListConstraint; // for integer type | |
560 | typedef RangeListConstraint<size_limit_t> SizeRangeListConstraint; // for length constraints | |
561 | typedef RangeListConstraint<char_limit_t> CharRangeListConstraint; // for char/bit/hex/octet strings | |
562 | typedef RangeListConstraint<universal_char_limit_t> UniversalCharRangeListConstraint; // for universal charstring | |
563 | ||
564 | //////////////////////////////////////////////////////////////////////////////// | |
565 | ||
566 | // RangeListConstraint with added NaN value (NaN is unordered so it cannot be a limit value) | |
567 | // this is canonical only if two different Real values are never considered to be adjacent | |
568 | // which means that in theory for two different Real values there are always infinite number of Real values that are between them | |
569 | class RealRangeListConstraint | |
570 | { | |
571 | private: | |
572 | bool has_nan; | |
573 | RangeListConstraint<real_limit_t> rlc; | |
574 | public: | |
575 | // constructors | |
576 | RealRangeListConstraint(bool p_has_nan = false): has_nan(p_has_nan), rlc() {} // empty set or NaN | |
577 | RealRangeListConstraint(const real_limit_t& rl): has_nan(false), rlc(rl) {} // single value set (cannot be lower or upper, must be exact value) | |
578 | RealRangeListConstraint(const real_limit_t& rl_begin, const real_limit_t& rl_end): has_nan(false), rlc(rl_begin,rl_end) {} // range set | |
579 | ||
580 | tribool is_empty() const { return ( rlc.is_empty() && TRIBOOL(!has_nan) ); } | |
581 | tribool is_full() const { return ( rlc.is_full() && TRIBOOL(has_nan) ); } | |
582 | tribool is_equal(const RealRangeListConstraint& other) const { return ( rlc.is_equal(other.rlc) && TRIBOOL(has_nan==other.has_nan) ); } | |
583 | bool is_element(const ttcn3float& r) const; | |
584 | ||
585 | // A union/intersection B -> C | |
586 | RealRangeListConstraint set_operation(const RealRangeListConstraint& other, bool is_union) const; | |
587 | ||
588 | RealRangeListConstraint operator+(const RealRangeListConstraint& other) const { return set_operation(other, true); } // union | |
589 | RealRangeListConstraint operator*(const RealRangeListConstraint& other) const { return set_operation(other, false); } // intersection | |
590 | RealRangeListConstraint operator~() const; // complement | |
591 | ||
592 | tribool is_subset(const RealRangeListConstraint& other) const { return (*this*~other).is_empty(); } | |
593 | RealRangeListConstraint operator-(const RealRangeListConstraint& other) const { return ( *this * ~other ); } // except | |
594 | ||
595 | tribool is_range_empty() const { return rlc.is_empty(); } | |
596 | real_limit_t get_minimal() const { return rlc.get_minimal(); } | |
597 | real_limit_t get_maximal() const { return rlc.get_maximal(); } | |
598 | ||
599 | string to_string() const; | |
600 | }; | |
601 | ||
602 | //////////////////////////////////////////////////////////////////////////////// | |
603 | ||
604 | class BooleanListConstraint | |
605 | { | |
606 | private: | |
607 | // every value selects a different bit, if the bit is set to 1 then the associated value is element of the set | |
608 | enum boolean_constraint_t { | |
609 | // 0x00 is empty set | |
610 | BC_FALSE = 0x01, | |
611 | BC_TRUE = 0x02, | |
612 | BC_ALL = 0x03 // all values, full set | |
613 | }; | |
614 | unsigned char values; | |
615 | ||
616 | public: | |
617 | // constructors | |
618 | BooleanListConstraint(): values(0) {} // empty set | |
619 | BooleanListConstraint(bool b): values(b ? BC_TRUE:BC_FALSE) {} // single value set | |
620 | ||
621 | tribool is_empty() const { return TRIBOOL(values==0); } | |
622 | tribool is_full() const { return TRIBOOL(values==BC_ALL); } | |
623 | tribool is_equal(const BooleanListConstraint& other) const { return TRIBOOL(values==other.values); } | |
624 | bool is_element(bool b) const { return b ? (values&BC_TRUE) : (values&BC_FALSE); } | |
625 | ||
626 | BooleanListConstraint operator+(const BooleanListConstraint& other) const { BooleanListConstraint rv; rv.values = values | other.values; return rv; } | |
627 | BooleanListConstraint operator*(const BooleanListConstraint& other) const { BooleanListConstraint rv; rv.values = values & other.values; return rv; } | |
628 | BooleanListConstraint operator~() const { BooleanListConstraint rv; rv.values = values ^ BC_ALL; return rv; } | |
629 | ||
630 | tribool is_subset(const BooleanListConstraint& other) const { return (*this*~other).is_empty(); } | |
631 | ||
632 | BooleanListConstraint operator-(const BooleanListConstraint& other) const { return ( *this * ~other ); } | |
633 | ||
634 | string to_string() const; | |
635 | }; | |
636 | ||
637 | //////////////////////////////////////////////////////////////////////////////// | |
638 | ||
639 | class VerdicttypeListConstraint | |
640 | { | |
641 | public: | |
642 | enum verdicttype_constraint_t { // every value selects a different bit, if the bit is set to 1 then the associated value is element of the set | |
643 | // 0x00 is empty set | |
644 | VC_NONE = 0x01, | |
645 | VC_PASS = 0x02, | |
646 | VC_INCONC = 0x04, | |
647 | VC_FAIL = 0x08, | |
648 | VC_ERROR = 0x10, | |
649 | VC_ALL = 0x1F // all values, full set | |
650 | }; | |
651 | ||
652 | private: | |
653 | unsigned char values; | |
654 | ||
655 | public: | |
656 | // constructors | |
657 | VerdicttypeListConstraint(): values(0) {} // empty set | |
658 | VerdicttypeListConstraint(verdicttype_constraint_t vtc): values(vtc) {} // single value set | |
659 | ||
660 | tribool is_empty() const { return TRIBOOL(values==0); } | |
661 | tribool is_full() const { return TRIBOOL(values==VC_ALL); } | |
662 | tribool is_equal(const VerdicttypeListConstraint& other) const { return TRIBOOL(values==other.values); } | |
663 | bool is_element(verdicttype_constraint_t vtc) const { return vtc&values; } | |
664 | ||
665 | VerdicttypeListConstraint operator+(const VerdicttypeListConstraint& other) const { VerdicttypeListConstraint rv; rv.values = values | other.values; return rv; } | |
666 | VerdicttypeListConstraint operator*(const VerdicttypeListConstraint& other) const { VerdicttypeListConstraint rv; rv.values = values & other.values; return rv; } | |
667 | VerdicttypeListConstraint operator~() const { VerdicttypeListConstraint rv; rv.values = values ^ VC_ALL; return rv; } | |
668 | ||
669 | tribool is_subset(const VerdicttypeListConstraint& other) const { return (*this*~other).is_empty(); } | |
670 | ||
671 | VerdicttypeListConstraint operator-(const VerdicttypeListConstraint& other) const { return ( *this * ~other ); } | |
672 | ||
673 | string to_string() const; | |
674 | }; | |
675 | ||
676 | //////////////////////////////////////////////////////////////////////////////// | |
677 | ||
678 | // size and value list constraint for bitstring, hexstring and octetstring | |
679 | // in the compiler octetstring is a special hexstring where 1 octet = 2 hex.chars | |
680 | // not_values is needed because the operation complement/except | |
681 | // not_values must always be inside size_constraint set, has_values must be outside of size_constraint set | |
682 | // canonical form can be obtained by simplifying value list constraints into size constraints | |
683 | // and by converting not_values information into the other two sets if number of not values is >= [number of all values for L] / 2 | |
684 | // for length(L) there must be exactly N^L number of values that have length=L, where an element can have N different values | |
685 | // where N = 2^BITCNT, BITCNT is the number of bits needed to store one element, works for BITCNT=1,4,8 | |
686 | // for octetstrings one octet element is 2 chars long, for others one element is one char, real size of string = elem.size()/ELEMSIZE | |
687 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
688 | class StringSizeAndValueListConstraint | |
689 | { | |
690 | private: | |
691 | SizeRangeListConstraint size_constraint; | |
692 | map<string,void> has_values, not_values; | |
693 | void clean_up(); | |
694 | void copy_content(const StringSizeAndValueListConstraint& other); | |
695 | void canonicalize(map<string,void>& values, map<string,void>& other_values, bool if_values); | |
696 | void canonicalize(); | |
697 | public: | |
698 | // constructors | |
699 | StringSizeAndValueListConstraint() {} // empty set | |
700 | StringSizeAndValueListConstraint(const string& s); // single value set | |
701 | StringSizeAndValueListConstraint(const size_limit_t& sl): size_constraint(sl) {} // single size value set | |
702 | StringSizeAndValueListConstraint(const size_limit_t& rl_begin, const size_limit_t& rl_end): size_constraint(rl_begin,rl_end) {} // size range set | |
703 | StringSizeAndValueListConstraint(const SizeRangeListConstraint& p_size_constraint): size_constraint(p_size_constraint) {} | |
704 | StringSizeAndValueListConstraint(const StringSizeAndValueListConstraint& other) { copy_content(other); } | |
705 | StringSizeAndValueListConstraint& operator=(const StringSizeAndValueListConstraint& other) { clean_up(); copy_content(other); return *this; } | |
706 | ~StringSizeAndValueListConstraint() { clean_up(); } | |
707 | ||
708 | tribool is_empty() const { return ( size_constraint.is_empty() && TRIBOOL(has_values.size()==0) ); } | |
709 | tribool is_full() const { return ( size_constraint.is_full() && TRIBOOL(not_values.size()==0) ); } | |
710 | tribool is_equal(const StringSizeAndValueListConstraint& other) const; | |
711 | bool is_element(const string& s) const; | |
712 | ||
713 | StringSizeAndValueListConstraint set_operation(const StringSizeAndValueListConstraint& other, bool is_union) const; | |
714 | ||
715 | StringSizeAndValueListConstraint operator+(const StringSizeAndValueListConstraint& other) const { return set_operation(other, true); } // union | |
716 | StringSizeAndValueListConstraint operator*(const StringSizeAndValueListConstraint& other) const { return set_operation(other, false); } // intersection | |
717 | StringSizeAndValueListConstraint operator~() const; // complement | |
718 | ||
719 | tribool is_subset(const StringSizeAndValueListConstraint& other) const { return (*this*~other).is_empty(); } | |
720 | StringSizeAndValueListConstraint operator-(const StringSizeAndValueListConstraint& other) const { return ( *this * ~other ); } // except | |
721 | ||
722 | tribool get_size_limit(bool is_upper, size_limit_t& limit) const; | |
723 | ||
724 | string to_string() const; | |
725 | }; | |
726 | ||
727 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
728 | tribool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::get_size_limit(bool is_upper, size_limit_t& limit) const | |
729 | { | |
730 | if (size_constraint.is_empty()==TTRUE) return TFALSE; | |
731 | limit = is_upper ? size_constraint.get_maximal() : size_constraint.get_minimal(); | |
732 | return TTRUE; | |
733 | } | |
734 | ||
735 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
736 | void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::clean_up() | |
737 | { | |
738 | size_constraint = SizeRangeListConstraint(); | |
739 | has_values.clear(); | |
740 | not_values.clear(); | |
741 | } | |
742 | ||
743 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
744 | void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::copy_content(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other) | |
745 | { | |
746 | size_constraint = other.size_constraint; | |
747 | for (size_t i=0; i<other.has_values.size(); i++) has_values.add(other.has_values.get_nth_key(i),NULL); | |
748 | for (size_t i=0; i<other.not_values.size(); i++) not_values.add(other.not_values.get_nth_key(i),NULL); | |
749 | } | |
750 | ||
751 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
752 | StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::StringSizeAndValueListConstraint(const string& s) | |
753 | { | |
754 | if (s.size() % ELEMSIZE != 0) FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()"); | |
755 | if (BITCNT==1) { | |
756 | for (size_t i=0; i<s.size(); i++) | |
757 | if ( (s[i]!='0') && (s[i]!='1') ) FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()"); | |
758 | } else if ( (BITCNT==4) || (BITCNT==8) ) { | |
759 | for (size_t i=0; i<s.size(); i++) | |
760 | if ( !((s[i]>='0')&&(s[i]<='9')) && !((s[i]>='A')&&(s[i]<='F')) ) | |
761 | FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()"); | |
762 | } else { | |
763 | FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()"); | |
764 | } | |
765 | has_values.add(s,NULL); | |
766 | } | |
767 | ||
768 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
769 | void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize(map<string,void>& values, map<string,void>& other_values, bool if_values) | |
770 | { | |
771 | map<size_t,size_t> values_lengths; // length -> number of values | |
772 | for (size_t i=0; i<values.size(); i++) { | |
773 | size_t value_size = values.get_nth_key(i).size()/ELEMSIZE; | |
774 | if (values_lengths.has_key(value_size)) (*values_lengths[value_size])++; | |
775 | else values_lengths.add(value_size,new size_t(1)); | |
776 | } | |
777 | ||
778 | for (size_t i=0; i<values_lengths.size(); i++) { | |
779 | // calculate the number of all possible values | |
780 | size_t size = values_lengths.get_nth_key(i); // length of string | |
781 | size_t count = *(values_lengths.get_nth_elem(i)); // number of strings with this length | |
782 | size_t all_values_count = ~((size_t)0); // fake infinity | |
783 | if (BITCNT*size<sizeof(size_t)*8) all_values_count = ( ((size_t)1) << (BITCNT*size) ); | |
784 | if (count==all_values_count) { | |
785 | // delete all values which have this size | |
786 | for (size_t hv_idx=0; hv_idx<values.size(); hv_idx++) { | |
787 | if ((values.get_nth_key(hv_idx).size()/ELEMSIZE)==size) { | |
788 | values.erase(values.get_nth_key(hv_idx)); | |
789 | hv_idx--; | |
790 | } | |
791 | } | |
792 | // add/remove a single value size constraint with this size | |
793 | if (if_values) size_constraint = size_constraint + SizeRangeListConstraint(size_limit_t(size)); | |
794 | else size_constraint = size_constraint - SizeRangeListConstraint(size_limit_t(size)); | |
795 | } else | |
796 | if ( (!if_values && (count>=all_values_count/2)) || (if_values && (count>all_values_count/2)) ) { | |
797 | // add to other_values the complement of these values on the set with this size | |
798 | for (size_t act_value=0; act_value<all_values_count; act_value++) { | |
799 | string str; // for each value of act_value there is corresponding string value str | |
800 | for (size_t elem_idx=0; elem_idx<size; elem_idx++) { // for every element | |
801 | size_t ei = ( ( act_value >> (elem_idx*BITCNT) ) & ( (1<<BITCNT) - 1 ) ); | |
802 | if (BITCNT==1) { | |
803 | str += '0' + (char)ei; | |
804 | } else if (BITCNT==4) { | |
805 | str += (ei<10) ? ('0' + (char)ei) : ('A' + ((char)ei-10)); | |
806 | } else if (BITCNT==8) { | |
807 | char c = ei & 0x0F; | |
808 | str += (c<10) ? ('0' + c) : ('A' + (c-10)); | |
809 | c = (ei >> (BITCNT/ELEMSIZE)) & 0x0F; | |
810 | str += (c<10) ? ('0' + c) : ('A' + (c-10)); | |
811 | } else { | |
812 | FATAL_ERROR("StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize()"); | |
813 | } | |
814 | } | |
815 | // if str is not element of values then add to other_values | |
816 | if (!values.has_key(str)) other_values.add(str,NULL); | |
817 | } | |
818 | // delete all values which have this size | |
819 | for (size_t hv_idx=0; hv_idx<values.size(); hv_idx++) { | |
820 | if ((values.get_nth_key(hv_idx).size()/ELEMSIZE)==size) { | |
821 | values.erase(values.get_nth_key(hv_idx)); | |
822 | hv_idx--; | |
823 | } | |
824 | } | |
825 | // add/remove a single value size constraint with this size | |
826 | if (if_values) size_constraint = size_constraint + SizeRangeListConstraint(size_limit_t(size)); | |
827 | else size_constraint = size_constraint - SizeRangeListConstraint(size_limit_t(size)); | |
828 | } | |
829 | } | |
830 | // clean up | |
831 | for (size_t i=0; i<values_lengths.size(); i++) delete (values_lengths.get_nth_elem(i)); | |
832 | values_lengths.clear(); | |
833 | } | |
834 | ||
835 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
836 | void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize() | |
837 | { | |
838 | canonicalize(has_values, not_values, true); | |
839 | canonicalize(not_values, has_values, false); | |
840 | } | |
841 | ||
842 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
843 | tribool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::is_equal(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other) const | |
844 | { | |
845 | if (size_constraint.is_equal(other.size_constraint)==TFALSE) return TFALSE; | |
846 | if (has_values.size()!=other.has_values.size()) return TFALSE; | |
847 | if (not_values.size()!=other.not_values.size()) return TFALSE; | |
848 | for (size_t i=0; i<has_values.size(); i++) if (has_values.get_nth_key(i)!=other.has_values.get_nth_key(i)) return TFALSE; | |
849 | for (size_t i=0; i<not_values.size(); i++) if (not_values.get_nth_key(i)!=other.not_values.get_nth_key(i)) return TFALSE; | |
850 | return TTRUE; | |
851 | } | |
852 | ||
853 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
854 | bool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::is_element(const string& s) const | |
855 | { | |
856 | return ( ( size_constraint.is_element(s.size()/ELEMSIZE) && !not_values.has_key(s) ) || has_values.has_key(s) ); | |
857 | } | |
858 | ||
859 | // representation of two sets: [Si+Vi-Ni] where Si=size_constraint, Vi=has_values, Ni=not_values | |
860 | // UNION: [S1+V1-N1] + [S2+V2-N2] = ... = [(S1+S2)+(V1+V2)-((~S1*N2)+(N1*~S2)+(N1*N2))] | |
861 | // INTERSECTION: [S1+V1-N1] * [S2+V2-N2] = ... = [(S1*S2)+((S1*V2-N1)+(S2*V1-N2)+(V1*V2))-(N1+N2)] | |
862 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
863 | StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> | |
864 | StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>:: | |
865 | set_operation(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other, bool is_union) const | |
866 | { | |
867 | StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> ret_val; | |
868 | ret_val.size_constraint = size_constraint.set_operation(other.size_constraint, is_union); | |
869 | if (is_union) { | |
870 | // V1+V2 (union of has_values) | |
871 | for (size_t i=0; i<has_values.size(); i++) ret_val.has_values.add(has_values.get_nth_key(i),NULL); | |
872 | for (size_t i=0; i<other.has_values.size(); i++) { | |
873 | const string& str = other.has_values.get_nth_key(i); | |
874 | if (!ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL); | |
875 | } | |
876 | // N1*N2 (intersection of not_values) | |
877 | for (size_t i=0; i<not_values.size(); i++) { | |
878 | const string& str = not_values.get_nth_key(i); | |
879 | if (other.not_values.has_key(str)) ret_val.not_values.add(str,NULL); | |
880 | } | |
881 | // ~S1*N2 | |
882 | for (size_t i=0; i<other.not_values.size(); i++) { | |
883 | const string& str = other.not_values.get_nth_key(i); | |
884 | if (!size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) && | |
885 | !ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL); | |
886 | } | |
887 | // N1*~S2 | |
888 | for (size_t i=0; i<not_values.size(); i++) { | |
889 | const string& str = not_values.get_nth_key(i); | |
890 | if (!other.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) && | |
891 | !ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL); | |
892 | } | |
893 | } else { // intersection | |
894 | // V1*V2 (intersection of has_values) | |
895 | for (size_t i=0; i<has_values.size(); i++) { | |
896 | const string& str = has_values.get_nth_key(i); | |
897 | if (other.has_values.has_key(str)) ret_val.has_values.add(str,NULL); | |
898 | } | |
899 | // S2*V1-N2 | |
900 | for (size_t i=0; i<has_values.size(); i++) { | |
901 | const string& str = has_values.get_nth_key(i); | |
902 | if (other.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) && | |
903 | !other.not_values.has_key(str) && | |
904 | !ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL); | |
905 | } | |
906 | // S1*V2-N1 | |
907 | for (size_t i=0; i<other.has_values.size(); i++) { | |
908 | const string& str = other.has_values.get_nth_key(i); | |
909 | if (size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) && | |
910 | !not_values.has_key(str) && | |
911 | !ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL); | |
912 | } | |
913 | // N1+N2 (union of not_values) | |
914 | for (size_t i=0; i<not_values.size(); i++) ret_val.not_values.add(not_values.get_nth_key(i),NULL); | |
915 | for (size_t i=0; i<other.not_values.size(); i++) { | |
916 | const string& str = other.not_values.get_nth_key(i); | |
917 | if (!ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL); | |
918 | } | |
919 | } | |
920 | { | |
921 | // drop ret_val.has_values that are elements of ret_val.not_values too, drop from ret_val.not_values too | |
922 | for (size_t i=0; i<ret_val.not_values.size(); i++) { | |
923 | string str = ret_val.not_values.get_nth_key(i); | |
924 | if (ret_val.has_values.has_key(str)) { | |
925 | ret_val.has_values.erase(str); | |
926 | ret_val.not_values.erase(str); | |
927 | i--; | |
928 | } | |
929 | } | |
930 | // drop ret_val.has_values elements that are elements of the ret_val.size_constraint set | |
931 | for (size_t i=0; i<ret_val.has_values.size(); i++) { | |
932 | string str = ret_val.has_values.get_nth_key(i); | |
933 | if (ret_val.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE))) { | |
934 | ret_val.has_values.erase(str); | |
935 | i--; | |
936 | } | |
937 | } | |
938 | // drop ret_val.not_values elements that are not elements of the ret_val.size_constraint set | |
939 | for (size_t i=0; i<ret_val.not_values.size(); i++) { | |
940 | string str = ret_val.not_values.get_nth_key(i); | |
941 | if (!ret_val.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE))) { | |
942 | ret_val.not_values.erase(str); | |
943 | i--; | |
944 | } | |
945 | } | |
946 | } | |
947 | ret_val.canonicalize(); | |
948 | return ret_val; | |
949 | } | |
950 | ||
951 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
952 | StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::operator~() const | |
953 | { | |
954 | StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> ret_val; | |
955 | ret_val.size_constraint = ~size_constraint; | |
956 | for (size_t i=0; i<has_values.size(); i++) ret_val.not_values.add(has_values.get_nth_key(i),NULL); | |
957 | for (size_t i=0; i<not_values.size(); i++) ret_val.has_values.add(not_values.get_nth_key(i),NULL); | |
958 | ret_val.canonicalize(); | |
959 | return ret_val; | |
960 | } | |
961 | ||
962 | template<unsigned char BITCNT, unsigned short ELEMSIZE> | |
963 | string StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::to_string() const | |
964 | { | |
965 | string ret_val; | |
966 | if (has_values.size()>0) { | |
967 | ret_val += '('; | |
968 | for (size_t i=0; i<has_values.size(); i++) { | |
969 | if (i>0) ret_val += ','; | |
970 | ret_val += '\''; | |
971 | ret_val += has_values.get_nth_key(i); | |
972 | ret_val += '\''; | |
973 | if (BITCNT==1) ret_val += 'B'; | |
974 | else if (BITCNT==4) ret_val += 'H'; | |
975 | else if (BITCNT==8) ret_val += 'O'; | |
976 | } | |
977 | ret_val += ')'; | |
978 | } | |
979 | // size constraint | |
980 | if (size_constraint.is_empty()!=TTRUE) { | |
981 | if (has_values.size()>0) ret_val += " union "; | |
982 | ret_val += "length"; | |
983 | ret_val += size_constraint.to_string(); | |
984 | } | |
985 | // except not_values | |
986 | if (not_values.size()>0) { | |
987 | ret_val += " except ("; | |
988 | for (size_t i=0; i<not_values.size(); i++) { | |
989 | if (i>0) ret_val += ','; | |
990 | ret_val += '\''; | |
991 | ret_val += not_values.get_nth_key(i); | |
992 | ret_val += '\''; | |
993 | if (BITCNT==1) ret_val += 'B'; | |
994 | else if (BITCNT==4) ret_val += 'H'; | |
995 | else if (BITCNT==8) ret_val += 'O'; | |
996 | } | |
997 | ret_val += ')'; | |
998 | } | |
999 | return ret_val; | |
1000 | } | |
1001 | ||
1002 | typedef StringSizeAndValueListConstraint<1,1> BitstringConstraint; | |
1003 | typedef StringSizeAndValueListConstraint<4,1> HexstringConstraint; | |
1004 | typedef StringSizeAndValueListConstraint<8,2> OctetstringConstraint; // one char is half octet | |
1005 | ||
1006 | //////////////////////////////////////////////////////////////////////////////// | |
1007 | ||
1008 | class StringPatternConstraint | |
1009 | { | |
1010 | private: | |
1011 | Ttcn::PatternString* pattern; // not owned | |
1012 | public: | |
1013 | // constructors | |
1014 | StringPatternConstraint() : pattern(0) {} // empty set | |
1015 | StringPatternConstraint(Ttcn::PatternString* p): pattern(p) {} | |
1016 | ||
1017 | tribool is_empty() const { return TUNKNOWN; } | |
1018 | tribool is_full() const { return TUNKNOWN; } | |
1019 | tribool is_equal(const StringPatternConstraint&) const { return TUNKNOWN; } | |
1020 | ||
1021 | tribool match(const string& str) const; | |
1022 | tribool match(const ustring&) const { return TUNKNOWN; } // TODO | |
1023 | ||
1024 | StringPatternConstraint set_operation(const StringPatternConstraint&, bool) const { FATAL_ERROR("StringPatternConstraint::set_operation(): not implemented"); } | |
1025 | ||
1026 | StringPatternConstraint operator+(const StringPatternConstraint& other) const { return set_operation(other, true); } // union | |
1027 | StringPatternConstraint operator*(const StringPatternConstraint& other) const { return set_operation(other, false); } // intersection | |
1028 | StringPatternConstraint operator~() const { FATAL_ERROR("StringPatternConstraint::operator~(): not implemented"); } | |
1029 | ||
1030 | tribool is_subset(const StringPatternConstraint&) const { return TUNKNOWN; } | |
1031 | StringPatternConstraint operator-(const StringPatternConstraint& other) const { return ( *this * ~other ); } // except | |
1032 | ||
1033 | string to_string() const; | |
1034 | }; | |
1035 | ||
1036 | //////////////////////////////////////////////////////////////////////////////// | |
1037 | ||
1038 | template <class STRINGTYPE> | |
1039 | class StringValueConstraint | |
1040 | { | |
1041 | private: | |
1042 | map<STRINGTYPE,void> values; | |
1043 | void clean_up(); | |
1044 | void copy_content(const StringValueConstraint& other); | |
1045 | public: | |
1046 | // constructors | |
1047 | StringValueConstraint() {} // empty set | |
1048 | StringValueConstraint(const STRINGTYPE& s) { values.add(s,NULL); } // single value set | |
1049 | ||
1050 | StringValueConstraint(const StringValueConstraint& other) { copy_content(other); } | |
1051 | StringValueConstraint& operator=(const StringValueConstraint& other) { clean_up(); copy_content(other); return *this; } | |
1052 | ~StringValueConstraint() { clean_up(); } | |
1053 | ||
1054 | tribool is_empty() const { return TRIBOOL(values.size()==0); } | |
1055 | tribool is_full() const { return TFALSE; } | |
1056 | tribool is_equal(const StringValueConstraint& other) const; | |
1057 | bool is_element(const STRINGTYPE& s) const { return values.has_key(s); } | |
1058 | ||
1059 | StringValueConstraint set_operation(const StringValueConstraint& other, bool is_union) const; | |
1060 | ||
1061 | StringValueConstraint operator+(const StringValueConstraint& other) const { return set_operation(other, true); } // union | |
1062 | StringValueConstraint operator*(const StringValueConstraint& other) const { return set_operation(other, false); } // intersection | |
1063 | ||
1064 | tribool is_subset(const StringValueConstraint& other) const { return (*this-other).is_empty(); } | |
1065 | StringValueConstraint operator-(const StringValueConstraint& other) const; // except | |
1066 | ||
1067 | // remove strings that are or are not elements of the set defined by the XXX_constraint object, | |
1068 | // using the XXX_constraint.is_element() member function | |
1069 | void remove(const SizeRangeListConstraint& size_constraint, bool if_element); | |
1070 | template <class CHARLIMITTYPE> void remove(const RangeListConstraint<CHARLIMITTYPE>& alphabet_constraint, bool if_element); | |
1071 | void remove(const StringPatternConstraint& pattern_constraint, bool if_element); | |
1072 | ||
1073 | string to_string() const; | |
1074 | }; | |
1075 | ||
1076 | template <class STRINGTYPE> | |
1077 | void StringValueConstraint<STRINGTYPE>::clean_up() | |
1078 | { | |
1079 | values.clear(); | |
1080 | } | |
1081 | ||
1082 | template <class STRINGTYPE> | |
1083 | void StringValueConstraint<STRINGTYPE>::copy_content(const StringValueConstraint<STRINGTYPE>& other) | |
1084 | { | |
1085 | for (size_t i=0; i<other.values.size(); i++) values.add(other.values.get_nth_key(i),NULL); | |
1086 | } | |
1087 | ||
1088 | template <class STRINGTYPE> | |
1089 | tribool StringValueConstraint<STRINGTYPE>::is_equal(const StringValueConstraint<STRINGTYPE>& other) const | |
1090 | { | |
1091 | if (values.size()!=other.values.size()) return TFALSE; | |
1092 | for (size_t i=0; i<values.size(); i++) { | |
1093 | if (values.get_nth_key(i)!=other.values.get_nth_key(i)) return TFALSE; | |
1094 | } | |
1095 | return TTRUE; | |
1096 | } | |
1097 | ||
1098 | template <class STRINGTYPE> | |
1099 | StringValueConstraint<STRINGTYPE> StringValueConstraint<STRINGTYPE>::set_operation | |
1100 | (const StringValueConstraint<STRINGTYPE>& other, bool is_union) const | |
1101 | { | |
1102 | StringValueConstraint<STRINGTYPE> ret_val; | |
1103 | if (is_union) { | |
1104 | for (size_t i=0; i<values.size(); i++) ret_val.values.add(values.get_nth_key(i), NULL); | |
1105 | for (size_t i=0; i<other.values.size(); i++) { | |
1106 | const STRINGTYPE& str = other.values.get_nth_key(i); | |
1107 | if (!ret_val.values.has_key(str)) ret_val.values.add(str, NULL); | |
1108 | } | |
1109 | } else { | |
1110 | for (size_t i=0; i<values.size(); i++) { | |
1111 | const STRINGTYPE& str = values.get_nth_key(i); | |
1112 | if (other.values.has_key(str)) ret_val.values.add(str, NULL); | |
1113 | } | |
1114 | } | |
1115 | return ret_val; | |
1116 | } | |
1117 | ||
1118 | template <class STRINGTYPE> | |
1119 | StringValueConstraint<STRINGTYPE> StringValueConstraint<STRINGTYPE>::operator-(const StringValueConstraint<STRINGTYPE>& other) const | |
1120 | { | |
1121 | StringValueConstraint<STRINGTYPE> ret_val; | |
1122 | for (size_t i=0; i<values.size(); i++) { | |
1123 | const STRINGTYPE& str = values.get_nth_key(i); | |
1124 | if (!other.values.has_key(str)) ret_val.values.add(str, NULL); | |
1125 | } | |
1126 | return ret_val; | |
1127 | } | |
1128 | ||
1129 | template <class STRINGTYPE> | |
1130 | void StringValueConstraint<STRINGTYPE>::remove(const SizeRangeListConstraint& size_constraint, bool if_element) | |
1131 | { | |
1132 | for (size_t i=0; i<values.size(); i++) { | |
1133 | STRINGTYPE str = values.get_nth_key(i); | |
1134 | if (size_constraint.is_element(size_limit_t(str.size()))==if_element) { | |
1135 | values.erase(str); | |
1136 | i--; | |
1137 | } | |
1138 | } | |
1139 | } | |
1140 | ||
1141 | template <class STRINGTYPE> | |
1142 | template <class CHARLIMITTYPE> | |
1143 | void StringValueConstraint<STRINGTYPE>::remove(const RangeListConstraint<CHARLIMITTYPE>& alphabet_constraint, bool if_element) | |
1144 | { | |
1145 | for (size_t i=0; i<values.size(); i++) { | |
1146 | STRINGTYPE str = values.get_nth_key(i); | |
1147 | bool all_chars_are_elements = true; | |
1148 | for (size_t chr_idx=0; chr_idx<str.size(); chr_idx++) | |
1149 | { | |
1150 | if (!alphabet_constraint.is_element(CHARLIMITTYPE(str[chr_idx]))) { | |
1151 | all_chars_are_elements = false; | |
1152 | break; | |
1153 | } | |
1154 | } | |
1155 | if (all_chars_are_elements==if_element) { | |
1156 | values.erase(str); | |
1157 | i--; | |
1158 | } | |
1159 | } | |
1160 | } | |
1161 | ||
1162 | template <class STRINGTYPE> | |
1163 | void StringValueConstraint<STRINGTYPE>::remove(const StringPatternConstraint& pattern_constraint, bool if_element) | |
1164 | { | |
1165 | for (size_t i=0; i<values.size(); i++) { | |
1166 | STRINGTYPE str = values.get_nth_key(i); | |
1167 | switch (pattern_constraint.match(str)) { | |
1168 | case TFALSE: | |
1169 | if (!if_element) { values.erase(str); i--; } | |
1170 | break; | |
1171 | case TUNKNOWN: | |
1172 | break; | |
1173 | case TTRUE: | |
1174 | if (if_element) { values.erase(str); i--; } | |
1175 | break; | |
1176 | default: | |
1177 | FATAL_ERROR("StringValueConstraint::remove(StringPatternConstraint)"); | |
1178 | } | |
1179 | } | |
1180 | } | |
1181 | ||
1182 | template <class STRINGTYPE> | |
1183 | string StringValueConstraint<STRINGTYPE>::to_string() const | |
1184 | { | |
1185 | string ret_val; | |
1186 | ret_val += '('; | |
1187 | for (size_t i=0; i<values.size(); i++) { | |
1188 | if (i>0) ret_val += ','; | |
1189 | STRINGTYPE str = values.get_nth_key(i); | |
1190 | ret_val += str.get_stringRepr(); | |
1191 | } | |
1192 | ret_val += ')'; | |
1193 | return ret_val; | |
1194 | } | |
1195 | ||
1196 | //////////////////////////////////////////////////////////////////////////////// | |
1197 | ||
1198 | // contains a tree of subtype constraints | |
1199 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1200 | class StringSubtypeTreeElement | |
1201 | { | |
1202 | public: | |
1203 | enum elementtype_t { | |
1204 | ET_NONE, // empty set | |
1205 | ET_ALL, // all values of the root type, no subtype constraint was given, other data members have no meaning | |
1206 | ET_CONSTRAINT, // constraint value | |
1207 | ET_INTERSECTION, // A intersection B | |
1208 | ET_UNION, // A union B | |
1209 | ET_EXCEPT // A except B | |
1210 | }; | |
1211 | enum constrainttype_t { | |
1212 | CT_SIZE, | |
1213 | CT_ALPHABET, | |
1214 | CT_VALUES, | |
1215 | CT_PATTERN | |
1216 | }; | |
1217 | private: | |
1218 | elementtype_t elementtype; | |
1219 | union { | |
1220 | struct { // operation (ET_INTERSECTION, ET_UNION, ET_EXCEPT) | |
1221 | StringSubtypeTreeElement* a; // owned | |
1222 | StringSubtypeTreeElement* b; // owned | |
1223 | } op; | |
1224 | struct { // constraint | |
1225 | constrainttype_t constrainttype; | |
1226 | union { // constraint objects are owned | |
1227 | SizeRangeListConstraint* s; // size/length constraint type | |
1228 | struct { | |
1229 | RangeListConstraint<CHARLIMITTYPE>* c; // range/alphabet constraint type | |
1230 | bool char_context; // this constraint can be either in char or string context | |
1231 | // char context is constraining a single char, | |
1232 | // string context is constraining a string | |
1233 | // this bool value affects evaluation | |
1234 | // in char context only range,all,none and operation | |
1235 | // constructors can be called, operations must always evaluate | |
1236 | // to range, all or none | |
1237 | } a; | |
1238 | StringValueConstraint<STRINGTYPE>* v; // value set constraint | |
1239 | StringPatternConstraint* p; // pattern constraint | |
1240 | }; | |
1241 | } cs; | |
1242 | } u; | |
1243 | void clean_up(); | |
1244 | void copy_content(const StringSubtypeTreeElement& other); // *this must be empty | |
1245 | void set_to_operand(bool operand_a); | |
1246 | void simplify(); // convert to ET_NONE or ET_ALL if possible | |
1247 | void evaluate(); // tries to evaluate a tree to a single constraint, works recursively for the whole tree | |
1248 | public: | |
1249 | StringSubtypeTreeElement(): elementtype(ET_NONE) {} | |
1250 | StringSubtypeTreeElement(elementtype_t p_elementtype, StringSubtypeTreeElement* p_a, StringSubtypeTreeElement* p_b); | |
1251 | StringSubtypeTreeElement(const SizeRangeListConstraint& p_s); | |
1252 | StringSubtypeTreeElement(const RangeListConstraint<CHARLIMITTYPE>& p_a, bool p_char_context); | |
1253 | StringSubtypeTreeElement(const StringValueConstraint<STRINGTYPE>& p_v); | |
1254 | StringSubtypeTreeElement(const StringPatternConstraint& p_p); | |
1255 | ||
1256 | StringSubtypeTreeElement(const StringSubtypeTreeElement& p) { copy_content(p); } | |
1257 | StringSubtypeTreeElement& operator=(const StringSubtypeTreeElement& other) { clean_up(); copy_content(other); return *this; } | |
1258 | ~StringSubtypeTreeElement() { clean_up(); } | |
1259 | ||
1260 | tribool is_empty() const; | |
1261 | tribool is_full() const; | |
1262 | tribool is_equal(const StringSubtypeTreeElement* other) const; | |
1263 | bool is_element(const STRINGTYPE& s) const; | |
1264 | tribool is_subset(const StringSubtypeTreeElement* other) const; | |
1265 | ||
1266 | bool is_single_constraint() const { return ( (elementtype==ET_CONSTRAINT) || (elementtype==ET_NONE) || (elementtype==ET_ALL) ); } | |
1267 | void set_none() { clean_up(); elementtype = ET_NONE; } | |
1268 | void set_all() { clean_up(); elementtype = ET_ALL; } | |
1269 | ||
1270 | /** return value: | |
1271 | TFALSE: limit does not exist (empty set or values, ...) | |
1272 | TUNKNOWN: limit cannot be determined | |
1273 | TTRUE: limit was set to the proper value */ | |
1274 | tribool get_alphabet_limit(bool is_upper, CHARLIMITTYPE& limit) const; | |
1275 | tribool get_size_limit(bool is_upper, size_limit_t& limit) const; | |
1276 | ||
1277 | bool is_valid_range() const; | |
1278 | void set_char_context(bool p_char_context); | |
1279 | ||
1280 | string to_string() const; | |
1281 | }; | |
1282 | ||
1283 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1284 | StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement(elementtype_t p_elementtype, StringSubtypeTreeElement* p_a, StringSubtypeTreeElement* p_b) | |
1285 | : elementtype(p_elementtype) | |
1286 | { | |
1287 | switch (elementtype) { | |
1288 | case ET_INTERSECTION: | |
1289 | case ET_UNION: | |
1290 | case ET_EXCEPT: | |
1291 | break; | |
1292 | default: | |
1293 | FATAL_ERROR("StringSubtypeTreeElement::StringSubtypeTreeElement()"); | |
1294 | } | |
1295 | u.op.a = p_a; | |
1296 | u.op.b = p_b; | |
1297 | evaluate(); | |
1298 | } | |
1299 | ||
1300 | ||
1301 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1302 | tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>:: | |
1303 | get_alphabet_limit(bool is_upper, CHARLIMITTYPE& limit) const | |
1304 | { | |
1305 | switch (elementtype) { | |
1306 | case ET_NONE: | |
1307 | return TFALSE; | |
1308 | case ET_ALL: | |
1309 | limit = is_upper ? CHARLIMITTYPE::maximum : CHARLIMITTYPE::minimum; | |
1310 | return TTRUE; | |
1311 | case ET_CONSTRAINT: | |
1312 | switch (u.cs.constrainttype) { | |
1313 | case CT_SIZE: | |
1314 | limit = is_upper ? CHARLIMITTYPE::maximum : CHARLIMITTYPE::minimum; | |
1315 | return TTRUE; | |
1316 | case CT_ALPHABET: | |
1317 | if (u.cs.a.c->is_empty()==TTRUE) return TFALSE; | |
1318 | limit = is_upper ? u.cs.a.c->get_maximal() : u.cs.a.c->get_minimal(); | |
1319 | return TTRUE; | |
1320 | case CT_VALUES: | |
1321 | return TFALSE; | |
1322 | case CT_PATTERN: | |
1323 | return TUNKNOWN; | |
1324 | default: | |
1325 | FATAL_ERROR("StringSubtypeTreeElement::get_alphabet_limit()"); | |
1326 | } | |
1327 | case ET_INTERSECTION: { | |
1328 | CHARLIMITTYPE la, lb; | |
1329 | tribool tb = u.op.a->get_alphabet_limit(is_upper, la) && u.op.b->get_alphabet_limit(is_upper, lb); | |
1330 | if (tb==TTRUE) { | |
1331 | limit = ((lb<la) ^ !is_upper) ? lb : la; | |
1332 | } | |
1333 | return tb; | |
1334 | } | |
1335 | case ET_UNION: | |
1336 | case ET_EXCEPT: | |
1337 | return TUNKNOWN; | |
1338 | default: | |
1339 | FATAL_ERROR("StringSubtypeTreeElement::get_alphabet_limit()"); | |
1340 | } | |
1341 | return TUNKNOWN; | |
1342 | } | |
1343 | ||
1344 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1345 | tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>:: | |
1346 | get_size_limit(bool is_upper, size_limit_t& limit) const | |
1347 | { | |
1348 | switch (elementtype) { | |
1349 | case ET_NONE: | |
1350 | return TFALSE; | |
1351 | case ET_ALL: | |
1352 | limit = is_upper ? size_limit_t::maximum : size_limit_t::minimum; | |
1353 | return TTRUE; | |
1354 | case ET_CONSTRAINT: | |
1355 | switch (u.cs.constrainttype) { | |
1356 | case CT_SIZE: | |
1357 | if (u.cs.s->is_empty()==TTRUE) return TFALSE; | |
1358 | limit = is_upper ? u.cs.s->get_maximal() : u.cs.s->get_minimal(); | |
1359 | return TTRUE; | |
1360 | case CT_ALPHABET: | |
1361 | limit = is_upper ? size_limit_t::maximum : size_limit_t::minimum; | |
1362 | return TTRUE; | |
1363 | case CT_VALUES: | |
1364 | return TFALSE; | |
1365 | case CT_PATTERN: | |
1366 | return TUNKNOWN; | |
1367 | default: | |
1368 | FATAL_ERROR("StringSubtypeTreeElement::get_size_limit()"); | |
1369 | } | |
1370 | case ET_INTERSECTION: { | |
1371 | size_limit_t la, lb; | |
1372 | tribool tb = u.op.a->get_size_limit(is_upper, la) && u.op.b->get_size_limit(is_upper, lb); | |
1373 | if (tb==TTRUE) { | |
1374 | limit = ((lb<la) ^ !is_upper) ? lb : la; | |
1375 | } | |
1376 | return tb; | |
1377 | } | |
1378 | case ET_UNION: | |
1379 | case ET_EXCEPT: | |
1380 | return TUNKNOWN; | |
1381 | default: | |
1382 | FATAL_ERROR("StringSubtypeTreeElement::get_size_limit()"); | |
1383 | } | |
1384 | return TUNKNOWN; | |
1385 | } | |
1386 | ||
1387 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1388 | bool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_valid_range() const | |
1389 | { | |
1390 | switch (elementtype) { | |
1391 | case ET_NONE: | |
1392 | case ET_ALL: | |
1393 | return true; | |
1394 | case ET_CONSTRAINT: | |
1395 | switch (u.cs.constrainttype) { | |
1396 | case CT_SIZE: | |
1397 | // must be SIZE(1) | |
1398 | return (u.cs.s->is_equal(SizeRangeListConstraint(size_limit_t(1)))==TTRUE); | |
1399 | case CT_ALPHABET: | |
1400 | return true; | |
1401 | case CT_VALUES: | |
1402 | case CT_PATTERN: | |
1403 | return false; | |
1404 | default: | |
1405 | FATAL_ERROR("StringSubtypeTreeElement::is_valid_range()"); | |
1406 | } | |
1407 | case ET_INTERSECTION: | |
1408 | case ET_UNION: | |
1409 | case ET_EXCEPT: | |
1410 | return ( u.op.a->is_valid_range() && u.op.b->is_valid_range() ); | |
1411 | default: | |
1412 | FATAL_ERROR("StringSubtypeTreeElement::is_valid_range()"); | |
1413 | } | |
1414 | return false; | |
1415 | } | |
1416 | ||
1417 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1418 | void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::set_char_context(bool p_char_context) | |
1419 | { | |
1420 | switch (elementtype) { | |
1421 | case ET_NONE: | |
1422 | case ET_ALL: | |
1423 | break; | |
1424 | case ET_CONSTRAINT: | |
1425 | u.cs.a.char_context = p_char_context; | |
1426 | switch (u.cs.constrainttype) { | |
1427 | case CT_SIZE: | |
1428 | if (p_char_context) set_all(); // false -> true | |
1429 | else FATAL_ERROR("StringSubtypeTreeElement::set_char_context()"); | |
1430 | case CT_ALPHABET: | |
1431 | break; | |
1432 | default: | |
1433 | FATAL_ERROR("StringSubtypeTreeElement::set_char_context()"); | |
1434 | } | |
1435 | break; | |
1436 | case ET_INTERSECTION: | |
1437 | case ET_UNION: | |
1438 | case ET_EXCEPT: | |
1439 | u.op.a->set_char_context(p_char_context); | |
1440 | u.op.b->set_char_context(p_char_context); | |
1441 | break; | |
1442 | default: | |
1443 | FATAL_ERROR("StringSubtypeTreeElement::set_char_context()"); | |
1444 | } | |
1445 | } | |
1446 | ||
1447 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1448 | StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement | |
1449 | (const SizeRangeListConstraint& p_s): | |
1450 | elementtype(ET_CONSTRAINT) | |
1451 | { | |
1452 | u.cs.constrainttype = CT_SIZE; | |
1453 | u.cs.s = new SizeRangeListConstraint(p_s); | |
1454 | simplify(); | |
1455 | } | |
1456 | ||
1457 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1458 | StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement | |
1459 | (const RangeListConstraint<CHARLIMITTYPE>& p_a, bool p_char_context): | |
1460 | elementtype(ET_CONSTRAINT) | |
1461 | { | |
1462 | u.cs.constrainttype = CT_ALPHABET; | |
1463 | u.cs.a.c = new RangeListConstraint<CHARLIMITTYPE>(p_a); | |
1464 | u.cs.a.char_context = p_char_context; | |
1465 | simplify(); | |
1466 | } | |
1467 | ||
1468 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1469 | StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement | |
1470 | (const StringValueConstraint<STRINGTYPE>& p_v): | |
1471 | elementtype(ET_CONSTRAINT) | |
1472 | { | |
1473 | u.cs.constrainttype = CT_VALUES; | |
1474 | u.cs.v = new StringValueConstraint<STRINGTYPE>(p_v); | |
1475 | simplify(); | |
1476 | } | |
1477 | ||
1478 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1479 | StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement | |
1480 | (const StringPatternConstraint& p_p): | |
1481 | elementtype(ET_CONSTRAINT) | |
1482 | { | |
1483 | u.cs.constrainttype = CT_PATTERN; | |
1484 | u.cs.p = new StringPatternConstraint(p_p); | |
1485 | simplify(); | |
1486 | } | |
1487 | ||
1488 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1489 | void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::clean_up() | |
1490 | { | |
1491 | switch (elementtype) { | |
1492 | case ET_NONE: | |
1493 | case ET_ALL: | |
1494 | break; | |
1495 | case ET_CONSTRAINT: | |
1496 | switch (u.cs.constrainttype) { | |
1497 | case CT_SIZE: delete u.cs.s; break; | |
1498 | case CT_ALPHABET: delete u.cs.a.c; break; | |
1499 | case CT_VALUES: delete u.cs.v; break; | |
1500 | case CT_PATTERN: delete u.cs.p; break; | |
1501 | default: FATAL_ERROR("StringSubtypeTreeElement::clean_up()"); | |
1502 | } | |
1503 | break; | |
1504 | case ET_INTERSECTION: | |
1505 | case ET_UNION: | |
1506 | case ET_EXCEPT: | |
1507 | delete u.op.a; | |
1508 | delete u.op.b; | |
1509 | break; | |
1510 | default: | |
1511 | FATAL_ERROR("StringSubtypeTreeElement::clean_up()"); | |
1512 | } | |
1513 | } | |
1514 | ||
1515 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1516 | void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::copy_content(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>& other) | |
1517 | { | |
1518 | elementtype = other.elementtype; | |
1519 | switch (elementtype) { | |
1520 | case ET_NONE: | |
1521 | case ET_ALL: | |
1522 | break; | |
1523 | case ET_CONSTRAINT: | |
1524 | u.cs.constrainttype = other.u.cs.constrainttype; | |
1525 | switch (u.cs.constrainttype) { | |
1526 | case CT_SIZE: u.cs.s = new SizeRangeListConstraint(*(other.u.cs.s)); break; | |
1527 | case CT_ALPHABET: | |
1528 | u.cs.a.c = new RangeListConstraint<CHARLIMITTYPE>(*(other.u.cs.a.c)); | |
1529 | u.cs.a.char_context = other.u.cs.a.char_context; | |
1530 | break; | |
1531 | case CT_VALUES: u.cs.v = new StringValueConstraint<STRINGTYPE>(*(other.u.cs.v)); break; | |
1532 | case CT_PATTERN: u.cs.p = new StringPatternConstraint(*(other.u.cs.p)); break; | |
1533 | default: FATAL_ERROR("StringSubtypeTreeElement::copy_content()"); | |
1534 | } | |
1535 | break; | |
1536 | case ET_INTERSECTION: | |
1537 | case ET_UNION: | |
1538 | case ET_EXCEPT: | |
1539 | u.op.a = new StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>(*(other.u.op.a)); | |
1540 | u.op.b = new StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>(*(other.u.op.b)); | |
1541 | break; | |
1542 | default: | |
1543 | FATAL_ERROR("StringSubtypeTreeElement::copy_content()"); | |
1544 | } | |
1545 | } | |
1546 | ||
1547 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1548 | void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::set_to_operand(bool operand_a) | |
1549 | { | |
1550 | switch (elementtype) { | |
1551 | case ET_INTERSECTION: | |
1552 | case ET_UNION: | |
1553 | case ET_EXCEPT: | |
1554 | break; | |
1555 | default: | |
1556 | FATAL_ERROR("StringSubtypeTreeElement::copy_operand()"); | |
1557 | } | |
1558 | StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* op; | |
1559 | if (operand_a) { | |
1560 | delete u.op.b; | |
1561 | op = u.op.a; | |
1562 | } else { | |
1563 | delete u.op.a; | |
1564 | op = u.op.b; | |
1565 | } | |
1566 | // steal the content of op into myself | |
1567 | elementtype = op->elementtype; | |
1568 | switch (elementtype) { | |
1569 | case ET_NONE: | |
1570 | case ET_ALL: | |
1571 | break; | |
1572 | case ET_CONSTRAINT: | |
1573 | u.cs.constrainttype = op->u.cs.constrainttype; | |
1574 | switch (u.cs.constrainttype) { | |
1575 | case CT_SIZE: u.cs.s = op->u.cs.s; break; | |
1576 | case CT_ALPHABET: | |
1577 | u.cs.a.c = op->u.cs.a.c; | |
1578 | u.cs.a.char_context = op->u.cs.a.char_context; | |
1579 | break; | |
1580 | case CT_VALUES: u.cs.v = op->u.cs.v; break; | |
1581 | case CT_PATTERN: u.cs.p = op->u.cs.p; break; | |
1582 | default: FATAL_ERROR("StringSubtypeTreeElement::copy_operand()"); | |
1583 | } | |
1584 | break; | |
1585 | case ET_INTERSECTION: | |
1586 | case ET_UNION: | |
1587 | case ET_EXCEPT: | |
1588 | u.op.a = op->u.op.a; | |
1589 | u.op.b = op->u.op.b; | |
1590 | break; | |
1591 | default: | |
1592 | FATAL_ERROR("StringSubtypeTreeElement::copy_operand()"); | |
1593 | } | |
1594 | // delete the empty op | |
1595 | op->elementtype = ET_NONE; | |
1596 | delete op; | |
1597 | } | |
1598 | ||
1599 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1600 | void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::simplify() | |
1601 | { | |
1602 | switch (elementtype) { | |
1603 | case ET_NONE: | |
1604 | case ET_ALL: | |
1605 | break; | |
1606 | case ET_CONSTRAINT: | |
1607 | switch (u.cs.constrainttype) { | |
1608 | case CT_SIZE: | |
1609 | if (u.cs.s->is_empty()==TTRUE) { set_none(); return; } | |
1610 | if (u.cs.s->is_full()==TTRUE) { set_all(); return; } | |
1611 | break; | |
1612 | case CT_ALPHABET: | |
1613 | if (u.cs.a.c->is_empty()==TTRUE) { set_none(); return; } | |
1614 | if (u.cs.a.c->is_full()==TTRUE) { set_all(); return; } | |
1615 | break; | |
1616 | case CT_VALUES: | |
1617 | if (u.cs.v->is_empty()==TTRUE) { set_none(); return; } | |
1618 | if (u.cs.v->is_full()==TTRUE) { set_all(); return; } | |
1619 | break; | |
1620 | case CT_PATTERN: | |
1621 | if (u.cs.p->is_empty()==TTRUE) { set_none(); return; } | |
1622 | if (u.cs.p->is_full()==TTRUE) { set_all(); return; } | |
1623 | break; | |
1624 | default: FATAL_ERROR("StringSubtypeTreeElement::simplify()"); | |
1625 | } | |
1626 | break; | |
1627 | case ET_INTERSECTION: | |
1628 | case ET_UNION: | |
1629 | case ET_EXCEPT: | |
1630 | break; | |
1631 | default: | |
1632 | FATAL_ERROR("StringSubtypeTreeElement::simplify()"); | |
1633 | } | |
1634 | } | |
1635 | ||
1636 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1637 | tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_empty() const | |
1638 | { | |
1639 | switch (elementtype) { | |
1640 | case ET_NONE: | |
1641 | return TTRUE; | |
1642 | case ET_ALL: | |
1643 | return TFALSE; | |
1644 | case ET_CONSTRAINT: | |
1645 | switch (u.cs.constrainttype) { | |
1646 | case CT_SIZE: return u.cs.s->is_empty(); | |
1647 | case CT_ALPHABET: return ( u.cs.a.char_context ? u.cs.a.c->is_empty() : TFALSE ); | |
1648 | case CT_VALUES: return u.cs.v->is_empty(); | |
1649 | case CT_PATTERN: return u.cs.p->is_empty(); | |
1650 | default: FATAL_ERROR("StringSubtypeTreeElement::is_empty()"); | |
1651 | } | |
1652 | case ET_INTERSECTION: | |
1653 | return ( u.op.a->is_empty() || u.op.b->is_empty() ); | |
1654 | case ET_UNION: | |
1655 | return ( u.op.a->is_empty() && u.op.b->is_empty() ); | |
1656 | case ET_EXCEPT: { | |
1657 | tribool a_empty = u.op.a->is_empty(); | |
1658 | return ( (a_empty!=TFALSE) ? a_empty : | |
1659 | ( (u.op.b->is_empty()==TTRUE) ? TFALSE : TUNKNOWN ) ); | |
1660 | } | |
1661 | default: | |
1662 | FATAL_ERROR("StringSubtypeTreeElement::is_empty()"); | |
1663 | } | |
1664 | return TUNKNOWN; | |
1665 | } | |
1666 | ||
1667 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1668 | tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_full() const | |
1669 | { | |
1670 | switch (elementtype) { | |
1671 | case ET_NONE: | |
1672 | return TFALSE; | |
1673 | case ET_ALL: | |
1674 | return TTRUE; | |
1675 | case ET_CONSTRAINT: | |
1676 | switch (u.cs.constrainttype) { | |
1677 | case CT_SIZE: return u.cs.s->is_full(); | |
1678 | case CT_ALPHABET: return u.cs.a.c->is_full(); | |
1679 | case CT_VALUES: return u.cs.v->is_full(); | |
1680 | case CT_PATTERN: return u.cs.p->is_full(); | |
1681 | default: FATAL_ERROR("StringSubtypeTreeElement::is_full()"); | |
1682 | } | |
1683 | case ET_INTERSECTION: | |
1684 | return ( u.op.a->is_full() && u.op.b->is_full() ); | |
1685 | case ET_UNION: | |
1686 | return ( u.op.a->is_full() || u.op.b->is_full() ); | |
1687 | case ET_EXCEPT: | |
1688 | return ( u.op.a->is_full() && u.op.b->is_empty() ); | |
1689 | default: | |
1690 | FATAL_ERROR("StringSubtypeTreeElement::is_full()"); | |
1691 | } | |
1692 | return TUNKNOWN; | |
1693 | } | |
1694 | ||
1695 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1696 | tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_equal(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* other) const | |
1697 | { | |
1698 | if (elementtype!=other->elementtype) return TUNKNOWN; | |
1699 | switch (elementtype) { | |
1700 | case ET_NONE: | |
1701 | case ET_ALL: | |
1702 | return TTRUE; | |
1703 | case ET_CONSTRAINT: | |
1704 | if (u.cs.constrainttype!=other->u.cs.constrainttype) return TUNKNOWN; | |
1705 | switch (u.cs.constrainttype) { | |
1706 | case CT_SIZE: return u.cs.s->is_equal(*(other->u.cs.s)); | |
1707 | case CT_ALPHABET: return u.cs.a->is_equal(*(other->u.cs.a)); | |
1708 | case CT_VALUES: return u.cs.v->is_equal(*(other->u.cs.v)); | |
1709 | case CT_PATTERN: return u.cs.p->is_equal(*(other->u.cs.p)); | |
1710 | default: FATAL_ERROR("StringSubtypeTreeElement::is_equal()"); | |
1711 | } | |
1712 | case ET_INTERSECTION: | |
1713 | case ET_UNION: | |
1714 | case ET_EXCEPT: | |
1715 | return TUNKNOWN; | |
1716 | default: | |
1717 | FATAL_ERROR("StringSubtypeTreeElement::is_equal()"); | |
1718 | } | |
1719 | return TUNKNOWN; | |
1720 | } | |
1721 | ||
1722 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1723 | bool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_element(const STRINGTYPE& s) const | |
1724 | { | |
1725 | switch (elementtype) { | |
1726 | case ET_NONE: | |
1727 | return false; | |
1728 | case ET_ALL: | |
1729 | return true; | |
1730 | case ET_CONSTRAINT: | |
1731 | switch (u.cs.constrainttype) { | |
1732 | case CT_SIZE: return u.cs.s->is_element(size_limit_t(s.size())); | |
1733 | case CT_ALPHABET: { | |
1734 | for (size_t i=0; i<s.size(); i++) { | |
1735 | CHARLIMITTYPE cl(s[i]); | |
1736 | if (!u.cs.a.c->is_element(cl)) return false; | |
1737 | } | |
1738 | return true; | |
1739 | } | |
1740 | case CT_VALUES: return u.cs.v->is_element(s); | |
1741 | case CT_PATTERN: { | |
1742 | switch (u.cs.p->match(s)) { | |
1743 | case TFALSE: return false; | |
1744 | case TUNKNOWN: return true; // don't know if it matches | |
1745 | case TTRUE: return true; | |
1746 | default: FATAL_ERROR("StringSubtypeTreeElement::is_element()"); | |
1747 | } | |
1748 | } | |
1749 | default: FATAL_ERROR("StringSubtypeTreeElement::is_element()"); | |
1750 | } | |
1751 | case ET_INTERSECTION: | |
1752 | return ( u.op.a->is_element(s) && u.op.b->is_element(s) ); | |
1753 | case ET_UNION: | |
1754 | return ( u.op.a->is_element(s) || u.op.b->is_element(s) ); | |
1755 | case ET_EXCEPT: | |
1756 | return ( u.op.a->is_element(s) && !u.op.b->is_element(s) ); | |
1757 | default: | |
1758 | FATAL_ERROR("StringSubtypeTreeElement::is_element()"); | |
1759 | } | |
1760 | return TUNKNOWN; | |
1761 | } | |
1762 | ||
1763 | // if the constraints are ortogonal (e.g. size and alphabet) or just different then return TUNKNOWN | |
1764 | // in case of ortogonal constraints we should return TFALSE (if other is not full set) | |
1765 | // but it seems that the standard wants to ignore such trivial cases, example: | |
1766 | // length(1..4) is_subset ('a'..'z') shall not report an error | |
1767 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1768 | tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_subset(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* other) const | |
1769 | { | |
1770 | switch (elementtype) { | |
1771 | case ET_NONE: | |
1772 | return TTRUE; | |
1773 | case ET_ALL: | |
1774 | if (other->elementtype==ET_ALL) return TTRUE; | |
1775 | else return TUNKNOWN; | |
1776 | case ET_CONSTRAINT: | |
1777 | if (elementtype!=other->elementtype) return TUNKNOWN; | |
1778 | if (u.cs.constrainttype!=other->u.cs.constrainttype) return TUNKNOWN; | |
1779 | switch (u.cs.constrainttype) { | |
1780 | case CT_SIZE: return u.cs.s->is_subset(*(other->u.cs.s)); | |
1781 | case CT_ALPHABET: return u.cs.a.c->is_subset(*(other->u.cs.a.c)); | |
1782 | case CT_VALUES: return u.cs.v->is_subset(*(other->u.cs.v)); | |
1783 | case CT_PATTERN: return u.cs.p->is_subset(*(other->u.cs.p)); | |
1784 | default: FATAL_ERROR("StringSubtypeTreeElement::is_subset()"); | |
1785 | } | |
1786 | case ET_INTERSECTION: | |
1787 | case ET_UNION: | |
1788 | case ET_EXCEPT: | |
1789 | return TUNKNOWN; | |
1790 | default: | |
1791 | FATAL_ERROR("StringSubtypeTreeElement::is_subset()"); | |
1792 | } | |
1793 | return TUNKNOWN; | |
1794 | } | |
1795 | ||
1796 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
1797 | void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::evaluate() | |
1798 | { | |
1799 | switch (elementtype) { | |
1800 | case ET_NONE: | |
1801 | case ET_ALL: | |
1802 | case ET_CONSTRAINT: | |
1803 | // these are the simplest forms, others are reduced to these in ideal case | |
1804 | return; | |
1805 | case ET_INTERSECTION: | |
1806 | case ET_UNION: | |
1807 | case ET_EXCEPT: | |
1808 | break; | |
1809 | default: | |
1810 | FATAL_ERROR("StringSubtypeTreeElement::evaluate()"); | |
1811 | } | |
1812 | ||
1813 | // recursive evaluation | |
1814 | u.op.a->evaluate(); | |
1815 | u.op.b->evaluate(); | |
1816 | ||
1817 | // special case where the construct looks like this: | |
1818 | // 1. ( A + B ) + C | |
1819 | // 2. A + ( B + C ) | |
1820 | // 3. (A+B) + (C+D) | |
1821 | // can be union or intersection, try to exchange constraint to have same type of constraints as operands, | |
1822 | // constraint types: tree, .... | |
1823 | // if succeeded then evaluate the new construct | |
1824 | // TODO... | |
1825 | ||
1826 | // special simple cases when one side is ET_ALL or ET_NONE but the other can be a tree | |
1827 | if ( (u.op.a->elementtype==ET_NONE) || (u.op.b->elementtype==ET_NONE) ) { | |
1828 | if (elementtype==ET_INTERSECTION) { set_none(); return; } | |
1829 | if (elementtype==ET_UNION) { | |
1830 | // the result is the other set | |
1831 | set_to_operand(u.op.b->elementtype==ET_NONE); | |
1832 | return; | |
1833 | } | |
1834 | } | |
1835 | if ( (u.op.b->elementtype==ET_NONE) && (elementtype==ET_EXCEPT) ) { | |
1836 | set_to_operand(true); | |
1837 | return; | |
1838 | } | |
1839 | if ( (u.op.a->elementtype==ET_ALL) || (u.op.b->elementtype==ET_ALL) ) { | |
1840 | if (elementtype==ET_INTERSECTION) { | |
1841 | // the result is the other set | |
1842 | set_to_operand(u.op.b->elementtype==ET_ALL); | |
1843 | return; | |
1844 | } | |
1845 | if (elementtype==ET_UNION) { set_all(); return; } | |
1846 | } | |
1847 | if ( (u.op.b->elementtype==ET_ALL) && (elementtype==ET_EXCEPT) ) { set_none(); return; } | |
1848 | ||
1849 | // both operands must be single constraints (ALL,NONE,CONSTRAINT), | |
1850 | // after this point trees will not be further simplified | |
1851 | if (!u.op.a->is_single_constraint() || !u.op.b->is_single_constraint()) return; | |
1852 | ||
1853 | // special case: ALL - some constraint type that can be complemented | |
1854 | if ( (u.op.a->elementtype==ET_ALL) && (elementtype==ET_EXCEPT) && (u.op.b->elementtype==ET_CONSTRAINT) ) { | |
1855 | switch (u.op.b->u.cs.constrainttype) { | |
1856 | case CT_SIZE: { | |
1857 | SizeRangeListConstraint* rvs = new SizeRangeListConstraint(~*(u.op.b->u.cs.s)); | |
1858 | clean_up(); | |
1859 | elementtype = ET_CONSTRAINT; | |
1860 | u.cs.constrainttype = CT_SIZE; | |
1861 | u.cs.s = rvs; | |
1862 | simplify(); | |
1863 | } return; | |
1864 | case CT_ALPHABET: { | |
1865 | if (u.cs.a.char_context) { | |
1866 | RangeListConstraint<CHARLIMITTYPE>* rva = new RangeListConstraint<CHARLIMITTYPE>(~*(u.op.b->u.cs.a.c)); | |
1867 | clean_up(); | |
1868 | elementtype = ET_CONSTRAINT; | |
1869 | u.cs.constrainttype = CT_ALPHABET; | |
1870 | u.cs.a.c = rva; | |
1871 | u.cs.a.char_context = true; | |
1872 | simplify(); | |
1873 | } | |
1874 | } return; | |
1875 | default: | |
1876 | break; | |
1877 | } | |
1878 | } | |
1879 | ||
1880 | // special case: when one operand is CT_VALUES then is_element() can be called for the values | |
1881 | // and drop values or drop the other operand set or both depending on the operation | |
1882 | StringValueConstraint<STRINGTYPE>* svc = NULL; | |
1883 | bool first_is_svc = false; | |
1884 | if ( (u.op.a->elementtype==ET_CONSTRAINT) && (u.op.a->u.cs.constrainttype==CT_VALUES) ) { | |
1885 | svc = u.op.a->u.cs.v; | |
1886 | first_is_svc = true; | |
1887 | } else if ( (u.op.b->elementtype==ET_CONSTRAINT) && (u.op.b->u.cs.constrainttype==CT_VALUES) ) { | |
1888 | svc = u.op.b->u.cs.v; | |
1889 | first_is_svc = false; // it's the second | |
1890 | } | |
1891 | if (svc!=NULL) { // if one or both operands are CT_VALUES | |
1892 | switch (elementtype) { | |
1893 | case ET_INTERSECTION: { | |
1894 | switch (first_is_svc ? u.op.b->u.cs.constrainttype : u.op.a->u.cs.constrainttype) { | |
1895 | case CT_SIZE: | |
1896 | svc->remove(*(first_is_svc ? u.op.b->u.cs.s : u.op.a->u.cs.s), false); | |
1897 | break; | |
1898 | case CT_ALPHABET: | |
1899 | svc->remove(*(first_is_svc ? u.op.b->u.cs.a.c : u.op.a->u.cs.a.c), false); | |
1900 | break; | |
1901 | case CT_PATTERN: | |
1902 | svc->remove(*(first_is_svc ? u.op.b->u.cs.p : u.op.a->u.cs.p), false); | |
1903 | break; | |
1904 | default: | |
1905 | break; | |
1906 | } | |
1907 | // drop the other operand, keep the values as constraint of this object | |
1908 | StringValueConstraint<STRINGTYPE>* keep_svc = new StringValueConstraint<STRINGTYPE>(*svc); | |
1909 | clean_up(); | |
1910 | elementtype = ET_CONSTRAINT; | |
1911 | u.cs.constrainttype = CT_VALUES; | |
1912 | u.cs.v = keep_svc; | |
1913 | simplify(); | |
1914 | return; | |
1915 | } | |
1916 | case ET_UNION: { | |
1917 | switch (first_is_svc ? u.op.b->u.cs.constrainttype : u.op.a->u.cs.constrainttype) { | |
1918 | case CT_SIZE: | |
1919 | svc->remove(*(first_is_svc ? u.op.b->u.cs.s : u.op.a->u.cs.s), true); | |
1920 | break; | |
1921 | case CT_ALPHABET: | |
1922 | svc->remove(*(first_is_svc ? u.op.b->u.cs.a.c : u.op.a->u.cs.a.c), true); | |
1923 | break; | |
1924 | case CT_PATTERN: | |
1925 | svc->remove(*(first_is_svc ? u.op.b->u.cs.p : u.op.a->u.cs.p), true); | |
1926 | break; | |
1927 | default: | |
1928 | break; | |
1929 | } | |
1930 | // if all values were dropped then drop the empty values operand | |
1931 | if (svc->is_empty()==TTRUE) { | |
1932 | set_to_operand(!first_is_svc); | |
1933 | return; | |
1934 | } | |
1935 | } break; | |
1936 | case ET_EXCEPT: { | |
1937 | if (first_is_svc) { // the second operand is u.op.b->u.cs.X where X can be length/alphabet/pattern constraint | |
1938 | switch (u.op.b->u.cs.constrainttype) { | |
1939 | case CT_SIZE: | |
1940 | svc->remove(*(u.op.b->u.cs.s), true); | |
1941 | break; | |
1942 | case CT_ALPHABET: | |
1943 | svc->remove(*(u.op.b->u.cs.a.c), true); | |
1944 | break; | |
1945 | case CT_PATTERN: | |
1946 | svc->remove(*(u.op.b->u.cs.p), true); | |
1947 | break; | |
1948 | default: | |
1949 | break; | |
1950 | } | |
1951 | // drop the other operand, keep the values as constraint of this object | |
1952 | StringValueConstraint<STRINGTYPE>* keep_svc = new StringValueConstraint<STRINGTYPE>(*svc); | |
1953 | clean_up(); | |
1954 | elementtype = ET_CONSTRAINT; | |
1955 | u.cs.constrainttype = CT_VALUES; | |
1956 | u.cs.v = keep_svc; | |
1957 | simplify(); | |
1958 | return; | |
1959 | } | |
1960 | } break; | |
1961 | default: | |
1962 | FATAL_ERROR("StringSubtypeTreeElement::evaluate()"); | |
1963 | } | |
1964 | } | |
1965 | ||
1966 | // operands of same types can be evaluated to one constraint using their | |
1967 | // set arithmetic member functions | |
1968 | // alphabet constraint in string context: | |
1969 | // FROM(A) UNION FROM(B) =/= FROM(A UNION B) | |
1970 | // ALL - FROM(A) =/= FROM(ALL - A) | |
1971 | // FROM(A) INTERSECTION FROM(B) == FROM (A INTERSECTION B) | |
1972 | if (u.op.a->elementtype==u.op.b->elementtype) { | |
1973 | switch (u.op.a->elementtype) { | |
1974 | case ET_ALL: | |
1975 | if (elementtype==ET_EXCEPT) set_none(); | |
1976 | else set_all(); | |
1977 | return; | |
1978 | case ET_NONE: | |
1979 | set_none(); | |
1980 | return; | |
1981 | case ET_CONSTRAINT: | |
1982 | if (u.op.a->u.cs.constrainttype==u.op.b->u.cs.constrainttype) { | |
1983 | switch (u.op.a->u.cs.constrainttype) { | |
1984 | case CT_SIZE: { | |
1985 | SizeRangeListConstraint* rvs = new SizeRangeListConstraint; | |
1986 | switch (elementtype) { | |
1987 | case ET_INTERSECTION: | |
1988 | *rvs = *(u.op.a->u.cs.s) * *(u.op.b->u.cs.s); | |
1989 | break; | |
1990 | case ET_UNION: | |
1991 | *rvs = *(u.op.a->u.cs.s) + *(u.op.b->u.cs.s); | |
1992 | break; | |
1993 | case ET_EXCEPT: | |
1994 | *rvs = *(u.op.a->u.cs.s) - *(u.op.b->u.cs.s); | |
1995 | break; | |
1996 | default: | |
1997 | FATAL_ERROR("StringSubtypeTreeElement::evaluate()"); | |
1998 | } | |
1999 | clean_up(); | |
2000 | elementtype = ET_CONSTRAINT; | |
2001 | u.cs.constrainttype = CT_SIZE; | |
2002 | u.cs.s = rvs; | |
2003 | } break; | |
2004 | case CT_ALPHABET: { | |
2005 | bool char_ctx = u.op.a->u.cs.a.char_context; | |
2006 | if (u.op.b->u.cs.a.char_context!=char_ctx) FATAL_ERROR("StringSubtypeTreeElement::evaluate()"); | |
2007 | if (char_ctx || (elementtype==ET_INTERSECTION)) { | |
2008 | RangeListConstraint<CHARLIMITTYPE>* rva = new RangeListConstraint<CHARLIMITTYPE>; | |
2009 | switch (elementtype) { | |
2010 | case ET_INTERSECTION: | |
2011 | *rva = *(u.op.a->u.cs.a.c) * *(u.op.b->u.cs.a.c); | |
2012 | break; | |
2013 | case ET_UNION: | |
2014 | *rva = *(u.op.a->u.cs.a.c) + *(u.op.b->u.cs.a.c); | |
2015 | break; | |
2016 | case ET_EXCEPT: | |
2017 | *rva = *(u.op.a->u.cs.a.c) - *(u.op.b->u.cs.a.c); | |
2018 | break; | |
2019 | default: | |
2020 | FATAL_ERROR("StringSubtypeTreeElement::evaluate()"); | |
2021 | } | |
2022 | clean_up(); | |
2023 | elementtype = ET_CONSTRAINT; | |
2024 | u.cs.constrainttype = CT_ALPHABET; | |
2025 | u.cs.a.c = rva; | |
2026 | u.cs.a.char_context = char_ctx; | |
2027 | } | |
2028 | } break; | |
2029 | case CT_VALUES: { | |
2030 | StringValueConstraint<STRINGTYPE>* rvv = new StringValueConstraint<STRINGTYPE>; | |
2031 | switch (elementtype) { | |
2032 | case ET_INTERSECTION: | |
2033 | *rvv = *(u.op.a->u.cs.v) * *(u.op.b->u.cs.v); | |
2034 | break; | |
2035 | case ET_UNION: | |
2036 | *rvv = *(u.op.a->u.cs.v) + *(u.op.b->u.cs.v); | |
2037 | break; | |
2038 | case ET_EXCEPT: | |
2039 | *rvv = *(u.op.a->u.cs.v) - *(u.op.b->u.cs.v); | |
2040 | break; | |
2041 | default: | |
2042 | FATAL_ERROR("StringSubtypeTreeElement::evaluate()"); | |
2043 | } | |
2044 | clean_up(); | |
2045 | elementtype = ET_CONSTRAINT; | |
2046 | u.cs.constrainttype = CT_VALUES; | |
2047 | u.cs.v = rvv; | |
2048 | } break; | |
2049 | case CT_PATTERN: | |
2050 | return; // OH SHI- | |
2051 | default: | |
2052 | FATAL_ERROR("StringSubtypeTreeElement::evaluate()"); | |
2053 | } | |
2054 | } | |
2055 | break; | |
2056 | default: | |
2057 | FATAL_ERROR("StringSubtypeTreeElement::evaluate()"); | |
2058 | } | |
2059 | } | |
2060 | simplify(); | |
2061 | } | |
2062 | ||
2063 | template <class STRINGTYPE, class CHARLIMITTYPE> | |
2064 | string StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::to_string() const | |
2065 | { | |
2066 | string ret_val; | |
2067 | bool print_operation = false; | |
2068 | string op_str; | |
2069 | switch (elementtype) { | |
2070 | case ET_NONE: | |
2071 | break; | |
2072 | case ET_ALL: | |
2073 | ret_val += "ALL"; | |
2074 | break; | |
2075 | case ET_CONSTRAINT: | |
2076 | switch (u.cs.constrainttype) { | |
2077 | case CT_SIZE: | |
2078 | ret_val += "length"; | |
2079 | ret_val += u.cs.s->to_string(); | |
2080 | break; | |
2081 | case CT_ALPHABET: | |
2082 | ret_val += u.cs.a.char_context ? "range" : "from"; | |
2083 | ret_val += u.cs.a.c->to_string(); | |
2084 | break; | |
2085 | case CT_VALUES: | |
2086 | ret_val += u.cs.v->to_string(); | |
2087 | break; | |
2088 | case CT_PATTERN: | |
2089 | ret_val += u.cs.p->to_string(); | |
2090 | break; | |
2091 | default: | |
2092 | FATAL_ERROR("StringSubtypeTreeElement::to_string()"); | |
2093 | } | |
2094 | break; | |
2095 | case ET_INTERSECTION: | |
2096 | op_str = "intersection"; | |
2097 | print_operation = true; | |
2098 | break; | |
2099 | case ET_UNION: | |
2100 | op_str = "union"; | |
2101 | print_operation = true; | |
2102 | break; | |
2103 | case ET_EXCEPT: | |
2104 | op_str = "except"; | |
2105 | print_operation = true; | |
2106 | break; | |
2107 | default: | |
2108 | FATAL_ERROR("StringSubtypeTreeElement::to_string()"); | |
2109 | } | |
2110 | if (print_operation) { | |
2111 | ret_val += '('; | |
2112 | ret_val += u.op.a->to_string(); | |
2113 | ret_val += ' '; | |
2114 | ret_val += op_str; | |
2115 | ret_val += ' '; | |
2116 | ret_val += u.op.b->to_string(); | |
2117 | ret_val += ')'; | |
2118 | } | |
2119 | return ret_val; | |
2120 | } | |
2121 | ||
2122 | typedef StringSubtypeTreeElement<string,char_limit_t> CharstringSubtypeTreeElement; | |
2123 | typedef StringSubtypeTreeElement<ustring,universal_char_limit_t> UniversalCharstringSubtypeTreeElement; | |
2124 | ||
2125 | //////////////////////////////////////////////////////////////////////////////// | |
2126 | // constraint classes for structured types | |
2127 | ||
2128 | // used by ValueListConstraint and RecofConstraint classes | |
2129 | // only operator==() is used, since most value types do not have operator<() | |
2130 | // when used in RecofConstraint it will use Value::get_nof_comps() | |
2131 | class ValueList | |
2132 | { | |
2133 | private: | |
2134 | vector<Value> values; // values are not owned | |
2135 | void clean_up(); | |
2136 | void copy_content(const ValueList& other); | |
2137 | public: | |
2138 | ValueList() : values() {} // empty set | |
2139 | ValueList(Value* v) : values() { values.add(v); } | |
2140 | ||
2141 | ValueList(const ValueList& other) : values() { copy_content(other); } | |
2142 | ValueList& operator=(const ValueList& other) { clean_up(); copy_content(other); return *this; } | |
2143 | ~ValueList() { clean_up(); } | |
2144 | ||
2145 | tribool is_empty() const { return TRIBOOL(values.size()==0); } | |
2146 | tribool is_full() const { return TUNKNOWN; } // it's unknown how many possible values we have | |
2147 | tribool is_equal(const ValueList& other) const; | |
2148 | bool is_element(Value* v) const; | |
2149 | ||
2150 | // remove all elements whose size is (not) element of the given length set | |
2151 | // works only if the type of values is correct (the get_nof_comps() doesn't end in FATAL_ERROR) | |
2152 | void remove(const SizeRangeListConstraint& size_constraint, bool if_element); | |
2153 | ||
2154 | ValueList set_operation(const ValueList& other, bool is_union) const; | |
2155 | ||
2156 | ValueList operator+(const ValueList& other) const { return set_operation(other, true); } // union | |
2157 | ValueList operator*(const ValueList& other) const { return set_operation(other, false); } // intersection | |
2158 | ValueList operator-(const ValueList& other) const; // except | |
2159 | ||
2160 | tribool is_subset(const ValueList& other) const { return (*this-other).is_empty(); } | |
2161 | ||
2162 | string to_string() const; | |
2163 | }; | |
2164 | ||
2165 | // can be a ValueList or (ALL-ValueList), used for subtypes of structured types, enumerated and objid | |
2166 | class ValueListConstraint | |
2167 | { | |
2168 | private: | |
2169 | bool complemented; | |
2170 | ValueList values; | |
2171 | public: | |
2172 | ValueListConstraint(): complemented(false), values() {} // empty set | |
2173 | ValueListConstraint(Value* v): complemented(false), values(v) {} // single element set | |
2174 | ValueListConstraint(bool p_complemented): complemented(p_complemented), values() {} // empty of full set | |
2175 | ||
2176 | tribool is_empty() const; | |
2177 | tribool is_full() const; | |
2178 | tribool is_equal(const ValueListConstraint& other) const; | |
2179 | bool is_element(Value* v) const; | |
2180 | ||
2181 | ValueListConstraint operator+(const ValueListConstraint& other) const; // union | |
2182 | ValueListConstraint operator*(const ValueListConstraint& other) const; // intersection | |
2183 | ValueListConstraint operator~() const; // complement | |
2184 | ||
2185 | inline tribool is_subset(const ValueListConstraint& other) const | |
2186 | { return (*this*~other).is_empty(); } | |
2187 | inline ValueListConstraint operator-(const ValueListConstraint& other) const | |
2188 | { return ( *this * ~other ); } // except | |
2189 | ||
2190 | string to_string() const; | |
2191 | }; | |
2192 | ||
2193 | // length and value list constraints for record/set of types | |
2194 | class RecofConstraint | |
2195 | { | |
2196 | private: | |
2197 | SizeRangeListConstraint size_constraint; | |
2198 | ValueList has_values, not_values; | |
2199 | public: | |
2200 | // constructors | |
2201 | RecofConstraint(): size_constraint(), has_values(), not_values() {} // empty set | |
2202 | RecofConstraint(Value* v): size_constraint(), has_values(v), not_values() {} // single value set | |
2203 | RecofConstraint(const size_limit_t& sl): size_constraint(sl), has_values(), not_values() {} // single size value set | |
2204 | RecofConstraint(const size_limit_t& rl_begin, const size_limit_t& rl_end) | |
2205 | : size_constraint(rl_begin,rl_end), has_values(), not_values() {} // size range set | |
2206 | RecofConstraint(const SizeRangeListConstraint& p_size_constraint) | |
2207 | : size_constraint(p_size_constraint), has_values(), not_values() {} | |
2208 | ||
2209 | tribool is_empty() const; | |
2210 | tribool is_full() const; | |
2211 | tribool is_equal(const RecofConstraint& other) const; | |
2212 | bool is_element(Value* v) const; | |
2213 | ||
2214 | RecofConstraint set_operation(const RecofConstraint& other, bool is_union) const; | |
2215 | ||
2216 | inline RecofConstraint operator+(const RecofConstraint& other) const { return set_operation(other, true); } // union | |
2217 | inline RecofConstraint operator*(const RecofConstraint& other) const { return set_operation(other, false); } // intersection | |
2218 | RecofConstraint operator~() const; // complement | |
2219 | ||
2220 | inline tribool is_subset(const RecofConstraint& other) const { return (*this*~other).is_empty(); } | |
2221 | inline RecofConstraint operator-(const RecofConstraint& other) const { return ( *this * ~other ); } // except | |
2222 | ||
2223 | tribool get_size_limit(bool is_upper, size_limit_t& limit) const; | |
2224 | ||
2225 | string to_string() const; | |
2226 | }; | |
2227 | ||
2228 | ||
2229 | }// namespace Common | |
2230 | ||
2231 | #endif // #ifndef _Subtypestuff_HH |