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