1 ///////////////////////////////////////////////////////////////////////////////
2 // Copyright (c) 2000-2014 Ericsson Telecom AB
3 // All rights reserved. This program and the accompanying materials
4 // are made available under the terms of the Eclipse Public License v1.0
5 // which accompanies this distribution, and is available at
6 // http://www.eclipse.org/legal/epl-v10.html
7 ///////////////////////////////////////////////////////////////////////////////
8 #ifndef _Subtypestuff_HH
9 #define _Subtypestuff_HH
11 #include "ttcn3/compiler.h"
18 #include "../common/ttcn3float.hh"
21 class LengthRestriction;
34 enum tribool // http://en.wikipedia.org/wiki/Ternary_logic
36 TFALSE = 0, // values are indexes into truth tables
41 extern tribool operator||(tribool a, tribool b);
42 extern tribool operator&&(tribool a, tribool b);
43 extern tribool operator!(tribool tb);
44 extern tribool TRIBOOL(bool b);
45 extern string to_string(const tribool& tb);
47 ////////////////////////////////////////////////////////////////////////////////
49 // integer interval limit type, can be +/- infinity, in case of infinity value has no meaning
53 enum int_limit_type_t {
58 static const int_limit_t minimum;
59 static const int_limit_t maximum;
61 int_limit_type_t type;
64 int_limit_t(): type(NUMBER), value() {}
65 int_limit_t(int_limit_type_t p_type);
66 int_limit_t(const int_val_t& p_value): type(NUMBER), value(p_value) {}
67 bool operator<(const int_limit_t& right) const;
68 bool operator==(const int_limit_t& right) const;
69 bool is_adjacent(const int_limit_t& other) const;
70 int_val_t get_value() const;
71 int_limit_type_t get_type() const { return type; }
72 int_limit_t next() const; // upper neighbour
73 int_limit_t previous() const; // lower neighbour
74 void check_single_value() const;
75 void check_interval_start() const;
76 void check_interval_end() const;
77 string to_string() const;
80 ////////////////////////////////////////////////////////////////////////////////
82 // limit value for length/size restriction
86 enum size_limit_type_t {
93 static const size_limit_t minimum;
94 static const size_limit_t maximum;
95 size_limit_t() : infinity(false), size() {}
96 size_limit_t(size_limit_type_t): infinity(true), size() {}
97 size_limit_t(size_t p_size): infinity(false), size(p_size) {}
98 bool operator<(const size_limit_t& right) const;
99 bool operator==(const size_limit_t& right) const;
100 bool is_adjacent(const size_limit_t& other) const;
101 size_t get_size() const;
102 bool get_infinity() const { return infinity; }
103 size_limit_t next() const;
104 size_limit_t previous() const;
105 void check_single_value() const;
106 void check_interval_start() const;
107 void check_interval_end() const {}
108 string to_string() const;
109 int_limit_t to_int_limit() const;
112 ////////////////////////////////////////////////////////////////////////////////
114 // limit value for string range/alphabet restriction
119 static const short int max_char;
121 static bool is_valid_value(short int p_chr);
122 static const char_limit_t minimum;
123 static const char_limit_t maximum;
124 char_limit_t(): chr(0) {}
125 char_limit_t(short int p_chr);
126 bool operator<(const char_limit_t& right) const { return chr<right.chr; }
127 bool operator==(const char_limit_t& right) const { return chr==right.chr; }
128 bool is_adjacent(const char_limit_t& other) const { return (chr+1==other.chr); }
129 char get_char() const { return (char)chr; }
130 char_limit_t next() const;
131 char_limit_t previous() const;
132 void check_single_value() const {}
133 void check_interval_start() const {}
134 void check_interval_end() const {}
135 string to_string() const;
138 ////////////////////////////////////////////////////////////////////////////////
140 class universal_char_limit_t
143 unsigned int code_point; // UCS-4 values [0..0x7FFFFFFF], for easy calculations
144 static const unsigned int max_code_point;
145 void check_value() const;
147 static bool is_valid_value(const ustring::universal_char& p_uchr);
148 static unsigned int uchar2codepoint(const ustring::universal_char& uchr);
149 static ustring::universal_char codepoint2uchar(unsigned int cp);
150 static const universal_char_limit_t minimum;
151 static const universal_char_limit_t maximum;
152 universal_char_limit_t(): code_point(0) {}
153 universal_char_limit_t(unsigned int p_code_point): code_point(p_code_point) { check_value(); }
154 universal_char_limit_t(const ustring::universal_char& p_chr) : code_point(uchar2codepoint(p_chr)) { check_value(); }
155 bool operator<(const universal_char_limit_t& right) const { return code_point<right.code_point; }
156 bool operator==(const universal_char_limit_t& right) const { return code_point==right.code_point; }
157 bool is_adjacent(const universal_char_limit_t& other) const { return (code_point+1==other.code_point); }
158 ustring::universal_char get_universal_char() const { return codepoint2uchar(code_point); }
159 unsigned int get_code_point() const { return code_point; }
160 universal_char_limit_t next() const;
161 universal_char_limit_t previous() const;
162 void check_single_value() const {}
163 void check_interval_start() const {}
164 void check_interval_end() const {}
165 string to_string() const;
168 ////////////////////////////////////////////////////////////////////////////////
173 enum real_limit_type_t {
174 LOWER, // the highest value that is less than the value, for open interval's upper limit
175 EXACT, // the value itself, for closed interval limits and single values
176 UPPER // the lowest value that is more than the value, for open interval's lower limit
178 static const real_limit_t minimum;
179 static const real_limit_t maximum;
181 real_limit_type_t type;
183 void check_value() const; // check for illegal values: NaN, -inf.lower and inf.upper
185 real_limit_t(): type(EXACT), value() { value = 0.0; } // avoid random illegal values
186 real_limit_t(const ttcn3float& p_value): type(EXACT), value(p_value) { check_value(); }
187 real_limit_t(const ttcn3float& p_value, real_limit_type_t p_type): type(p_type), value(p_value) { check_value(); }
189 bool operator<(const real_limit_t& right) const;
190 bool operator==(const real_limit_t& right) const;
191 bool is_adjacent(const real_limit_t& other) const; // two different values cannot be adjacent in a general floating point value
192 ttcn3float get_value() const { return value; }
193 real_limit_type_t get_type() const { return type; }
194 real_limit_t next() const; // upper neighbour, has same value
195 real_limit_t previous() const; // lower neighbour, has same value
196 void check_single_value() const;
197 void check_interval_start() const;
198 void check_interval_end() const;
199 string to_string() const;
202 ////////////////////////////////////////////////////////////////////////////////
204 // forward declaration
205 template <typename LIMITTYPE>
206 class RangeListConstraint;
208 bool convert_int_to_size(const RangeListConstraint<int_limit_t>& int_range, RangeListConstraint<size_limit_t>& size_range);
211 all-in-one constraint class template for xxx_limit_t types
212 the xxx_limit_t classes must have the same interface for use by this class
214 - values must be v1 < v2 < v3 < ... < vN (xxx_limit_t::operator<() and xxx_limit_t::operator==() used)
215 - there cannot be two adjacent intervals that are part of the set (determined by xxx_limit_t::is_adjacent())
216 - two adjacent values must make an interval (if values[i] is adjacent to values[i+1] then intervals[i] is true)
217 - empty values[] means empty set
218 - full set is [minimum-maximum] interval (xxx_limit_t::minimum and xxx_limit_t::maximum are used)
220 template <typename LIMITTYPE>
221 class RangeListConstraint
224 // used in calculating the union and intersection of two sets, _idx are indexes into the values[] vector of the operand sets
227 int a_idx; // index into the operand's values/intervals vectors or -1
229 bool union_interval; // is this interval in the set
230 bool intersection_interval; // is this interval in the set
231 bool intersection_point; // is this point in the set
232 sweep_point_t(): a_idx(-1), b_idx(-1), union_interval(false), intersection_interval(false), intersection_point(false) {}
233 sweep_point_t(int a, int b): a_idx(a), b_idx(b), union_interval(false), intersection_interval(false), intersection_point(false) {}
236 dynamic_array<LIMITTYPE> values;
237 dynamic_array<bool> intervals;
241 RangeListConstraint(): values(), intervals() {} // empty set
242 RangeListConstraint(const LIMITTYPE& l); // single value set
243 RangeListConstraint(const LIMITTYPE& l_begin, const LIMITTYPE& l_end); // value range set
245 tribool is_empty() const;
246 tribool is_full() const;
247 tribool is_equal(const RangeListConstraint& other) const;
248 bool is_element(const LIMITTYPE& l) const;
250 RangeListConstraint set_operation(const RangeListConstraint& other, bool is_union) const; // A union/intersection B -> C
251 RangeListConstraint operator+(const RangeListConstraint& other) const { return set_operation(other, true); } // union
252 RangeListConstraint operator*(const RangeListConstraint& other) const { return set_operation(other, false); } // intersection
253 RangeListConstraint operator~() const; // complement
255 tribool is_subset(const RangeListConstraint& other) const { return (*this*~other).is_empty(); }
256 RangeListConstraint operator-(const RangeListConstraint& other) const { return ( *this * ~other ); } // except
258 // will return the minimal value that is part of the interval,
259 // if the interval is empty the returned value is undefined
260 LIMITTYPE get_minimal() const;
261 LIMITTYPE get_maximal() const;
263 string to_string(bool add_brackets=true) const;
265 /** conversion from integer range to size range,
266 returns true on success, false if the integers do not fit into the size values,
267 when returning false the size_range will be set to the full set */
268 friend bool convert_int_to_size(const RangeListConstraint<int_limit_t>& int_range, RangeListConstraint<size_limit_t>& size_range);
271 template <typename LIMITTYPE>
272 RangeListConstraint<LIMITTYPE>::RangeListConstraint(const LIMITTYPE& l)
273 : values(), intervals()
275 l.check_single_value();
277 intervals.add(false);
280 template <typename LIMITTYPE>
281 RangeListConstraint<LIMITTYPE>::RangeListConstraint(const LIMITTYPE& l_begin, const LIMITTYPE& l_end)
282 : values(), intervals()
284 if (l_end<l_begin) FATAL_ERROR("RangeListConstraint::RangeListConstraint(): invalid range");
285 if (l_begin==l_end) {
286 l_begin.check_single_value();
288 intervals.add(false);
290 l_begin.check_interval_start();
291 l_end.check_interval_end();
295 intervals.add(false);
299 template <typename LIMITTYPE>
300 tribool RangeListConstraint<LIMITTYPE>::is_empty() const
302 return TRIBOOL(values.size()==0);
305 template <typename LIMITTYPE>
306 tribool RangeListConstraint<LIMITTYPE>::is_full() const
308 return TRIBOOL( (values.size()==2) && (values[0]==LIMITTYPE::minimum) && (values[1]==LIMITTYPE::maximum) && (intervals[0]) );
311 template <typename LIMITTYPE>
312 tribool RangeListConstraint<LIMITTYPE>::is_equal(const RangeListConstraint<LIMITTYPE>& other) const
314 return TRIBOOL( (values==other.values) && (intervals==other.intervals) );
317 template <typename LIMITTYPE>
318 bool RangeListConstraint<LIMITTYPE>::is_element(const LIMITTYPE& l) const
320 if (values.size()==0) return false;
321 // binary search in values[]
322 size_t lower_idx = 0;
323 size_t upper_idx = values.size()-1;
324 while (upper_idx>lower_idx+1) {
325 size_t middle_idx = lower_idx + (upper_idx-lower_idx) / 2;
326 if (values[middle_idx]<l) lower_idx = middle_idx;
327 else upper_idx = middle_idx;
329 if (lower_idx==upper_idx) {
330 if (values[lower_idx]==l) return true; // every value is in the set
331 else if (values[lower_idx]<l) return intervals[lower_idx];
332 else return ( (lower_idx>0) ? intervals[lower_idx-1] : false );
334 if (l<values[lower_idx]) return ( (lower_idx>0) ? intervals[lower_idx-1] : false );
335 else if (l==values[lower_idx]) return true;
336 else if (l<values[upper_idx]) return intervals[upper_idx-1];
337 else if (l==values[upper_idx]) return true;
338 else return intervals[upper_idx];
342 template <typename LIMITTYPE>
343 RangeListConstraint<LIMITTYPE> RangeListConstraint<LIMITTYPE>::operator~() const
345 if (values.size()==0) { // if we have an empty set
346 return RangeListConstraint<LIMITTYPE>(LIMITTYPE::minimum, LIMITTYPE::maximum);
348 RangeListConstraint<LIMITTYPE> ret_val;
350 if (!(values[0]==LIMITTYPE::minimum)) {
351 if (LIMITTYPE::minimum.is_adjacent(values[0])) {
352 ret_val.values.add(LIMITTYPE::minimum);
353 ret_val.intervals.add(false);
355 ret_val.values.add(LIMITTYPE::minimum);
356 ret_val.intervals.add(true);
357 ret_val.values.add(values[0].previous());
358 ret_val.intervals.add(false);
361 int last = values.size()-1;
362 for (int i=0; i<last; i++)
365 if (values[i].next()==values[i+1].previous()) {
366 // add one value between intervals
367 ret_val.values.add(values[i].next());
368 ret_val.intervals.add(false);
370 // add interval between intervals
371 ret_val.values.add(values[i].next());
372 ret_val.intervals.add(true);
373 ret_val.values.add(values[i+1].previous());
374 ret_val.intervals.add(false);
378 if (!(values[last]==LIMITTYPE::maximum)) {
379 if (values[last].is_adjacent(LIMITTYPE::maximum)) {
380 ret_val.values.add(LIMITTYPE::maximum);
381 ret_val.intervals.add(false);
383 ret_val.values.add(values[last].next());
384 ret_val.intervals.add(true);
385 ret_val.values.add(LIMITTYPE::maximum);
386 ret_val.intervals.add(false);
392 template <typename LIMITTYPE>
393 RangeListConstraint<LIMITTYPE> RangeListConstraint<LIMITTYPE>::set_operation(const RangeListConstraint<LIMITTYPE>& other, bool is_union) const
395 // special case: one or both are empty sets
396 if (values.size()==0) return is_union ? other : *this;
397 if (other.values.size()==0) return is_union ? *this : other;
399 // calculate the sweep points
400 dynamic_array<sweep_point_t> sweep_points;
401 sweep_point_t spi(0,0);
402 while ( (spi.a_idx<(int)values.size()) || (spi.b_idx<(int)other.values.size()) )
404 if (spi.a_idx>=(int)values.size()) {
405 sweep_points.add(sweep_point_t(-1,spi.b_idx));
407 } else if (spi.b_idx>=(int)other.values.size()) {
408 sweep_points.add(sweep_point_t(spi.a_idx, -1));
410 } else { // both are within the vector, get smaller or get both if equal
411 if (values[spi.a_idx]<other.values[spi.b_idx]) {
412 sweep_points.add(sweep_point_t(spi.a_idx, -1));
414 } else if (values[spi.a_idx]==other.values[spi.b_idx]) {
415 sweep_points.add(spi);
419 sweep_points.add(sweep_point_t(-1,spi.b_idx));
425 // sweep (iterate) through both vectors
426 bool in_a = false; // we are already in an interval of A
428 for (int i=0; i<(int)sweep_points.size(); i++)
430 // set bools for A interval
431 bool a_interval = in_a;
432 bool a_point = false;
433 if (sweep_points[i].a_idx!=-1) { // we are at a value in A
435 if (intervals[sweep_points[i].a_idx]) { // this is a starting point of an interval in A
437 if (in_a) FATAL_ERROR("RangeListConstraint::set_operation(): invalid double interval");
439 } else { // this point ends an interval of A
444 // set bools for B interval
445 bool b_interval = in_b;
446 bool b_point = false;
447 if (sweep_points[i].b_idx!=-1) { // we are at a value in B
449 if (other.intervals[sweep_points[i].b_idx]) { // this is a starting point of an interval in B
451 if (in_b) FATAL_ERROR("RangeListConstraint::set_operation(): invalid double interval");
453 } else { // this point ends an interval of B
458 // set the booleans of the union and intersection sets
459 sweep_points[i].union_interval = a_interval || b_interval;
460 sweep_points[i].intersection_point = (a_point || in_a) && (b_point || in_b);
461 sweep_points[i].intersection_interval = a_interval && b_interval;
464 // canonicalization of ret_val
466 // connect adjacent limit points with interval: [i,i+1] becomes interval
467 for (int i=1; i<(int)sweep_points.size(); i++)
469 LIMITTYPE first, second;
470 if (sweep_points[i-1].a_idx!=-1) {
471 first = values[sweep_points[i-1].a_idx];
473 if (sweep_points[i-1].b_idx!=-1) first = other.values[sweep_points[i-1].b_idx];
474 else FATAL_ERROR("RangeListConstraint::set_operation()");
476 if (sweep_points[i].a_idx!=-1) {
477 second = values[sweep_points[i].a_idx];
479 if (sweep_points[i].b_idx!=-1) second = other.values[sweep_points[i].b_idx];
480 else FATAL_ERROR("RangeListConstraint::set_operation()");
482 if (first.is_adjacent(second)) {
483 sweep_points[i-1].union_interval = true;
484 sweep_points[i-1].intersection_interval = sweep_points[i-1].intersection_point && sweep_points[i].intersection_point;
488 // two adjacent intervals shall be united into one
489 RangeListConstraint<LIMITTYPE> ret_val;
490 for (int i=0; i<(int)sweep_points.size(); i++)
493 if ( (i>0) && sweep_points[i-1].union_interval && sweep_points[i].union_interval) {
494 // drop this point, it's in a double interval
497 if (sweep_points[i].a_idx!=-1) {
498 l = values[sweep_points[i].a_idx];
500 if (sweep_points[i].b_idx!=-1) l = other.values[sweep_points[i].b_idx];
501 else FATAL_ERROR("RangeListConstraint::set_operation()");
503 ret_val.values.add(l);
504 ret_val.intervals.add(sweep_points[i].union_interval);
507 if (sweep_points[i].intersection_point) {
508 if ( (i>0) && sweep_points[i-1].intersection_interval && sweep_points[i].intersection_interval) {
509 // drop this point, it's in a double interval
512 if (sweep_points[i].a_idx!=-1) {
513 l = values[sweep_points[i].a_idx];
515 if (sweep_points[i].b_idx!=-1) l = other.values[sweep_points[i].b_idx];
516 else FATAL_ERROR("RangeListConstraint::set_operation()");
518 ret_val.values.add(l);
519 ret_val.intervals.add(sweep_points[i].intersection_interval);
527 template <typename LIMITTYPE>
528 LIMITTYPE RangeListConstraint<LIMITTYPE>::get_minimal() const
530 if (values.size()<1) return LIMITTYPE();
534 template <typename LIMITTYPE>
535 LIMITTYPE RangeListConstraint<LIMITTYPE>::get_maximal() const
537 if (values.size()<1) return LIMITTYPE();
538 return values[values.size()-1];
541 template <typename LIMITTYPE>
542 string RangeListConstraint<LIMITTYPE>::to_string(bool add_brackets) const
545 if (add_brackets) ret_val += '(';
546 int last = values.size()-1;
547 for (int i=0; i<=last; i++)
549 ret_val += values[i].to_string();
550 if (intervals[i]) ret_val += "..";
551 else if (i<last) ret_val += ',';
553 if (add_brackets) ret_val += ')';
557 ////////////////////////////////////////////////////////////////////////////////
559 typedef RangeListConstraint<int_limit_t> IntegerRangeListConstraint; // for integer type
560 typedef RangeListConstraint<size_limit_t> SizeRangeListConstraint; // for length constraints
561 typedef RangeListConstraint<char_limit_t> CharRangeListConstraint; // for char/bit/hex/octet strings
562 typedef RangeListConstraint<universal_char_limit_t> UniversalCharRangeListConstraint; // for universal charstring
564 ////////////////////////////////////////////////////////////////////////////////
566 // RangeListConstraint with added NaN value (NaN is unordered so it cannot be a limit value)
567 // this is canonical only if two different Real values are never considered to be adjacent
568 // which means that in theory for two different Real values there are always infinite number of Real values that are between them
569 class RealRangeListConstraint
573 RangeListConstraint<real_limit_t> rlc;
576 RealRangeListConstraint(bool p_has_nan = false): has_nan(p_has_nan), rlc() {} // empty set or NaN
577 RealRangeListConstraint(const real_limit_t& rl): has_nan(false), rlc(rl) {} // single value set (cannot be lower or upper, must be exact value)
578 RealRangeListConstraint(const real_limit_t& rl_begin, const real_limit_t& rl_end): has_nan(false), rlc(rl_begin,rl_end) {} // range set
580 tribool is_empty() const { return ( rlc.is_empty() && TRIBOOL(!has_nan) ); }
581 tribool is_full() const { return ( rlc.is_full() && TRIBOOL(has_nan) ); }
582 tribool is_equal(const RealRangeListConstraint& other) const { return ( rlc.is_equal(other.rlc) && TRIBOOL(has_nan==other.has_nan) ); }
583 bool is_element(const ttcn3float& r) const;
585 // A union/intersection B -> C
586 RealRangeListConstraint set_operation(const RealRangeListConstraint& other, bool is_union) const;
588 RealRangeListConstraint operator+(const RealRangeListConstraint& other) const { return set_operation(other, true); } // union
589 RealRangeListConstraint operator*(const RealRangeListConstraint& other) const { return set_operation(other, false); } // intersection
590 RealRangeListConstraint operator~() const; // complement
592 tribool is_subset(const RealRangeListConstraint& other) const { return (*this*~other).is_empty(); }
593 RealRangeListConstraint operator-(const RealRangeListConstraint& other) const { return ( *this * ~other ); } // except
595 tribool is_range_empty() const { return rlc.is_empty(); }
596 real_limit_t get_minimal() const { return rlc.get_minimal(); }
597 real_limit_t get_maximal() const { return rlc.get_maximal(); }
599 string to_string() const;
602 ////////////////////////////////////////////////////////////////////////////////
604 class BooleanListConstraint
607 // every value selects a different bit, if the bit is set to 1 then the associated value is element of the set
608 enum boolean_constraint_t {
612 BC_ALL = 0x03 // all values, full set
614 unsigned char values;
618 BooleanListConstraint(): values(0) {} // empty set
619 BooleanListConstraint(bool b): values(b ? BC_TRUE:BC_FALSE) {} // single value set
621 tribool is_empty() const { return TRIBOOL(values==0); }
622 tribool is_full() const { return TRIBOOL(values==BC_ALL); }
623 tribool is_equal(const BooleanListConstraint& other) const { return TRIBOOL(values==other.values); }
624 bool is_element(bool b) const { return b ? (values&BC_TRUE) : (values&BC_FALSE); }
626 BooleanListConstraint operator+(const BooleanListConstraint& other) const { BooleanListConstraint rv; rv.values = values | other.values; return rv; }
627 BooleanListConstraint operator*(const BooleanListConstraint& other) const { BooleanListConstraint rv; rv.values = values & other.values; return rv; }
628 BooleanListConstraint operator~() const { BooleanListConstraint rv; rv.values = values ^ BC_ALL; return rv; }
630 tribool is_subset(const BooleanListConstraint& other) const { return (*this*~other).is_empty(); }
632 BooleanListConstraint operator-(const BooleanListConstraint& other) const { return ( *this * ~other ); }
634 string to_string() const;
637 ////////////////////////////////////////////////////////////////////////////////
639 class VerdicttypeListConstraint
642 enum verdicttype_constraint_t { // every value selects a different bit, if the bit is set to 1 then the associated value is element of the set
649 VC_ALL = 0x1F // all values, full set
653 unsigned char values;
657 VerdicttypeListConstraint(): values(0) {} // empty set
658 VerdicttypeListConstraint(verdicttype_constraint_t vtc): values(vtc) {} // single value set
660 tribool is_empty() const { return TRIBOOL(values==0); }
661 tribool is_full() const { return TRIBOOL(values==VC_ALL); }
662 tribool is_equal(const VerdicttypeListConstraint& other) const { return TRIBOOL(values==other.values); }
663 bool is_element(verdicttype_constraint_t vtc) const { return vtc&values; }
665 VerdicttypeListConstraint operator+(const VerdicttypeListConstraint& other) const { VerdicttypeListConstraint rv; rv.values = values | other.values; return rv; }
666 VerdicttypeListConstraint operator*(const VerdicttypeListConstraint& other) const { VerdicttypeListConstraint rv; rv.values = values & other.values; return rv; }
667 VerdicttypeListConstraint operator~() const { VerdicttypeListConstraint rv; rv.values = values ^ VC_ALL; return rv; }
669 tribool is_subset(const VerdicttypeListConstraint& other) const { return (*this*~other).is_empty(); }
671 VerdicttypeListConstraint operator-(const VerdicttypeListConstraint& other) const { return ( *this * ~other ); }
673 string to_string() const;
676 ////////////////////////////////////////////////////////////////////////////////
678 // size and value list constraint for bitstring, hexstring and octetstring
679 // in the compiler octetstring is a special hexstring where 1 octet = 2 hex.chars
680 // not_values is needed because the operation complement/except
681 // not_values must always be inside size_constraint set, has_values must be outside of size_constraint set
682 // canonical form can be obtained by simplifying value list constraints into size constraints
683 // and by converting not_values information into the other two sets if number of not values is >= [number of all values for L] / 2
684 // for length(L) there must be exactly N^L number of values that have length=L, where an element can have N different values
685 // where N = 2^BITCNT, BITCNT is the number of bits needed to store one element, works for BITCNT=1,4,8
686 // for octetstrings one octet element is 2 chars long, for others one element is one char, real size of string = elem.size()/ELEMSIZE
687 template<unsigned char BITCNT, unsigned short ELEMSIZE>
688 class StringSizeAndValueListConstraint
691 SizeRangeListConstraint size_constraint;
692 map<string,void> has_values, not_values;
694 void copy_content(const StringSizeAndValueListConstraint& other);
695 void canonicalize(map<string,void>& values, map<string,void>& other_values, bool if_values);
699 StringSizeAndValueListConstraint() {} // empty set
700 StringSizeAndValueListConstraint(const string& s); // single value set
701 StringSizeAndValueListConstraint(const size_limit_t& sl): size_constraint(sl) {} // single size value set
702 StringSizeAndValueListConstraint(const size_limit_t& rl_begin, const size_limit_t& rl_end): size_constraint(rl_begin,rl_end) {} // size range set
703 StringSizeAndValueListConstraint(const SizeRangeListConstraint& p_size_constraint): size_constraint(p_size_constraint) {}
704 StringSizeAndValueListConstraint(const StringSizeAndValueListConstraint& other) { copy_content(other); }
705 StringSizeAndValueListConstraint& operator=(const StringSizeAndValueListConstraint& other) { clean_up(); copy_content(other); return *this; }
706 ~StringSizeAndValueListConstraint() { clean_up(); }
708 tribool is_empty() const { return ( size_constraint.is_empty() && TRIBOOL(has_values.size()==0) ); }
709 tribool is_full() const { return ( size_constraint.is_full() && TRIBOOL(not_values.size()==0) ); }
710 tribool is_equal(const StringSizeAndValueListConstraint& other) const;
711 bool is_element(const string& s) const;
713 StringSizeAndValueListConstraint set_operation(const StringSizeAndValueListConstraint& other, bool is_union) const;
715 StringSizeAndValueListConstraint operator+(const StringSizeAndValueListConstraint& other) const { return set_operation(other, true); } // union
716 StringSizeAndValueListConstraint operator*(const StringSizeAndValueListConstraint& other) const { return set_operation(other, false); } // intersection
717 StringSizeAndValueListConstraint operator~() const; // complement
719 tribool is_subset(const StringSizeAndValueListConstraint& other) const { return (*this*~other).is_empty(); }
720 StringSizeAndValueListConstraint operator-(const StringSizeAndValueListConstraint& other) const { return ( *this * ~other ); } // except
722 tribool get_size_limit(bool is_upper, size_limit_t& limit) const;
724 string to_string() const;
727 template<unsigned char BITCNT, unsigned short ELEMSIZE>
728 tribool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::get_size_limit(bool is_upper, size_limit_t& limit) const
730 if (size_constraint.is_empty()==TTRUE) return TFALSE;
731 limit = is_upper ? size_constraint.get_maximal() : size_constraint.get_minimal();
735 template<unsigned char BITCNT, unsigned short ELEMSIZE>
736 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::clean_up()
738 size_constraint = SizeRangeListConstraint();
743 template<unsigned char BITCNT, unsigned short ELEMSIZE>
744 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::copy_content(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other)
746 size_constraint = other.size_constraint;
747 for (size_t i=0; i<other.has_values.size(); i++) has_values.add(other.has_values.get_nth_key(i),NULL);
748 for (size_t i=0; i<other.not_values.size(); i++) not_values.add(other.not_values.get_nth_key(i),NULL);
751 template<unsigned char BITCNT, unsigned short ELEMSIZE>
752 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::StringSizeAndValueListConstraint(const string& s)
754 if (s.size() % ELEMSIZE != 0) FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
756 for (size_t i=0; i<s.size(); i++)
757 if ( (s[i]!='0') && (s[i]!='1') ) FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
758 } else if ( (BITCNT==4) || (BITCNT==8) ) {
759 for (size_t i=0; i<s.size(); i++)
760 if ( !((s[i]>='0')&&(s[i]<='9')) && !((s[i]>='A')&&(s[i]<='F')) )
761 FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
763 FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
765 has_values.add(s,NULL);
768 template<unsigned char BITCNT, unsigned short ELEMSIZE>
769 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize(map<string,void>& values, map<string,void>& other_values, bool if_values)
771 map<size_t,size_t> values_lengths; // length -> number of values
772 for (size_t i=0; i<values.size(); i++) {
773 size_t value_size = values.get_nth_key(i).size()/ELEMSIZE;
774 if (values_lengths.has_key(value_size)) (*values_lengths[value_size])++;
775 else values_lengths.add(value_size,new size_t(1));
778 for (size_t i=0; i<values_lengths.size(); i++) {
779 // calculate the number of all possible values
780 size_t size = values_lengths.get_nth_key(i); // length of string
781 size_t count = *(values_lengths.get_nth_elem(i)); // number of strings with this length
782 size_t all_values_count = ~((size_t)0); // fake infinity
783 if (BITCNT*size<sizeof(size_t)*8) all_values_count = ( ((size_t)1) << (BITCNT*size) );
784 if (count==all_values_count) {
785 // delete all values which have this size
786 for (size_t hv_idx=0; hv_idx<values.size(); hv_idx++) {
787 if ((values.get_nth_key(hv_idx).size()/ELEMSIZE)==size) {
788 values.erase(values.get_nth_key(hv_idx));
792 // add/remove a single value size constraint with this size
793 if (if_values) size_constraint = size_constraint + SizeRangeListConstraint(size_limit_t(size));
794 else size_constraint = size_constraint - SizeRangeListConstraint(size_limit_t(size));
796 if ( (!if_values && (count>=all_values_count/2)) || (if_values && (count>all_values_count/2)) ) {
797 // add to other_values the complement of these values on the set with this size
798 for (size_t act_value=0; act_value<all_values_count; act_value++) {
799 string str; // for each value of act_value there is corresponding string value str
800 for (size_t elem_idx=0; elem_idx<size; elem_idx++) { // for every element
801 size_t ei = ( ( act_value >> (elem_idx*BITCNT) ) & ( (1<<BITCNT) - 1 ) );
803 str += '0' + (char)ei;
804 } else if (BITCNT==4) {
805 str += (ei<10) ? ('0' + (char)ei) : ('A' + ((char)ei-10));
806 } else if (BITCNT==8) {
808 str += (c<10) ? ('0' + c) : ('A' + (c-10));
809 c = (ei >> (BITCNT/ELEMSIZE)) & 0x0F;
810 str += (c<10) ? ('0' + c) : ('A' + (c-10));
812 FATAL_ERROR("StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize()");
815 // if str is not element of values then add to other_values
816 if (!values.has_key(str)) other_values.add(str,NULL);
818 // delete all values which have this size
819 for (size_t hv_idx=0; hv_idx<values.size(); hv_idx++) {
820 if ((values.get_nth_key(hv_idx).size()/ELEMSIZE)==size) {
821 values.erase(values.get_nth_key(hv_idx));
825 // add/remove a single value size constraint with this size
826 if (if_values) size_constraint = size_constraint + SizeRangeListConstraint(size_limit_t(size));
827 else size_constraint = size_constraint - SizeRangeListConstraint(size_limit_t(size));
831 for (size_t i=0; i<values_lengths.size(); i++) delete (values_lengths.get_nth_elem(i));
832 values_lengths.clear();
835 template<unsigned char BITCNT, unsigned short ELEMSIZE>
836 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize()
838 canonicalize(has_values, not_values, true);
839 canonicalize(not_values, has_values, false);
842 template<unsigned char BITCNT, unsigned short ELEMSIZE>
843 tribool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::is_equal(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other) const
845 if (size_constraint.is_equal(other.size_constraint)==TFALSE) return TFALSE;
846 if (has_values.size()!=other.has_values.size()) return TFALSE;
847 if (not_values.size()!=other.not_values.size()) return TFALSE;
848 for (size_t i=0; i<has_values.size(); i++) if (has_values.get_nth_key(i)!=other.has_values.get_nth_key(i)) return TFALSE;
849 for (size_t i=0; i<not_values.size(); i++) if (not_values.get_nth_key(i)!=other.not_values.get_nth_key(i)) return TFALSE;
853 template<unsigned char BITCNT, unsigned short ELEMSIZE>
854 bool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::is_element(const string& s) const
856 return ( ( size_constraint.is_element(s.size()/ELEMSIZE) && !not_values.has_key(s) ) || has_values.has_key(s) );
859 // representation of two sets: [Si+Vi-Ni] where Si=size_constraint, Vi=has_values, Ni=not_values
860 // UNION: [S1+V1-N1] + [S2+V2-N2] = ... = [(S1+S2)+(V1+V2)-((~S1*N2)+(N1*~S2)+(N1*N2))]
861 // INTERSECTION: [S1+V1-N1] * [S2+V2-N2] = ... = [(S1*S2)+((S1*V2-N1)+(S2*V1-N2)+(V1*V2))-(N1+N2)]
862 template<unsigned char BITCNT, unsigned short ELEMSIZE>
863 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>
864 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::
865 set_operation(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other, bool is_union) const
867 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> ret_val;
868 ret_val.size_constraint = size_constraint.set_operation(other.size_constraint, is_union);
870 // V1+V2 (union of has_values)
871 for (size_t i=0; i<has_values.size(); i++) ret_val.has_values.add(has_values.get_nth_key(i),NULL);
872 for (size_t i=0; i<other.has_values.size(); i++) {
873 const string& str = other.has_values.get_nth_key(i);
874 if (!ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL);
876 // N1*N2 (intersection of not_values)
877 for (size_t i=0; i<not_values.size(); i++) {
878 const string& str = not_values.get_nth_key(i);
879 if (other.not_values.has_key(str)) ret_val.not_values.add(str,NULL);
882 for (size_t i=0; i<other.not_values.size(); i++) {
883 const string& str = other.not_values.get_nth_key(i);
884 if (!size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) &&
885 !ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL);
888 for (size_t i=0; i<not_values.size(); i++) {
889 const string& str = not_values.get_nth_key(i);
890 if (!other.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) &&
891 !ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL);
893 } else { // intersection
894 // V1*V2 (intersection of has_values)
895 for (size_t i=0; i<has_values.size(); i++) {
896 const string& str = has_values.get_nth_key(i);
897 if (other.has_values.has_key(str)) ret_val.has_values.add(str,NULL);
900 for (size_t i=0; i<has_values.size(); i++) {
901 const string& str = has_values.get_nth_key(i);
902 if (other.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) &&
903 !other.not_values.has_key(str) &&
904 !ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL);
907 for (size_t i=0; i<other.has_values.size(); i++) {
908 const string& str = other.has_values.get_nth_key(i);
909 if (size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) &&
910 !not_values.has_key(str) &&
911 !ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL);
913 // N1+N2 (union of not_values)
914 for (size_t i=0; i<not_values.size(); i++) ret_val.not_values.add(not_values.get_nth_key(i),NULL);
915 for (size_t i=0; i<other.not_values.size(); i++) {
916 const string& str = other.not_values.get_nth_key(i);
917 if (!ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL);
921 // drop ret_val.has_values that are elements of ret_val.not_values too, drop from ret_val.not_values too
922 for (size_t i=0; i<ret_val.not_values.size(); i++) {
923 string str = ret_val.not_values.get_nth_key(i);
924 if (ret_val.has_values.has_key(str)) {
925 ret_val.has_values.erase(str);
926 ret_val.not_values.erase(str);
930 // drop ret_val.has_values elements that are elements of the ret_val.size_constraint set
931 for (size_t i=0; i<ret_val.has_values.size(); i++) {
932 string str = ret_val.has_values.get_nth_key(i);
933 if (ret_val.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE))) {
934 ret_val.has_values.erase(str);
938 // drop ret_val.not_values elements that are not elements of the ret_val.size_constraint set
939 for (size_t i=0; i<ret_val.not_values.size(); i++) {
940 string str = ret_val.not_values.get_nth_key(i);
941 if (!ret_val.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE))) {
942 ret_val.not_values.erase(str);
947 ret_val.canonicalize();
951 template<unsigned char BITCNT, unsigned short ELEMSIZE>
952 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::operator~() const
954 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> ret_val;
955 ret_val.size_constraint = ~size_constraint;
956 for (size_t i=0; i<has_values.size(); i++) ret_val.not_values.add(has_values.get_nth_key(i),NULL);
957 for (size_t i=0; i<not_values.size(); i++) ret_val.has_values.add(not_values.get_nth_key(i),NULL);
958 ret_val.canonicalize();
962 template<unsigned char BITCNT, unsigned short ELEMSIZE>
963 string StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::to_string() const
966 if (has_values.size()>0) {
968 for (size_t i=0; i<has_values.size(); i++) {
969 if (i>0) ret_val += ',';
971 ret_val += has_values.get_nth_key(i);
973 if (BITCNT==1) ret_val += 'B';
974 else if (BITCNT==4) ret_val += 'H';
975 else if (BITCNT==8) ret_val += 'O';
980 if (size_constraint.is_empty()!=TTRUE) {
981 if (has_values.size()>0) ret_val += " union ";
983 ret_val += size_constraint.to_string();
986 if (not_values.size()>0) {
987 ret_val += " except (";
988 for (size_t i=0; i<not_values.size(); i++) {
989 if (i>0) ret_val += ',';
991 ret_val += not_values.get_nth_key(i);
993 if (BITCNT==1) ret_val += 'B';
994 else if (BITCNT==4) ret_val += 'H';
995 else if (BITCNT==8) ret_val += 'O';
1002 typedef StringSizeAndValueListConstraint<1,1> BitstringConstraint;
1003 typedef StringSizeAndValueListConstraint<4,1> HexstringConstraint;
1004 typedef StringSizeAndValueListConstraint<8,2> OctetstringConstraint; // one char is half octet
1006 ////////////////////////////////////////////////////////////////////////////////
1008 class StringPatternConstraint
1011 Ttcn::PatternString* pattern; // not owned
1014 StringPatternConstraint() : pattern(0) {} // empty set
1015 StringPatternConstraint(Ttcn::PatternString* p): pattern(p) {}
1017 tribool is_empty() const { return TUNKNOWN; }
1018 tribool is_full() const { return TUNKNOWN; }
1019 tribool is_equal(const StringPatternConstraint&) const { return TUNKNOWN; }
1021 tribool match(const string& str) const;
1022 tribool match(const ustring&) const { return TUNKNOWN; } // TODO
1024 StringPatternConstraint set_operation(const StringPatternConstraint&, bool) const { FATAL_ERROR("StringPatternConstraint::set_operation(): not implemented"); }
1026 StringPatternConstraint operator+(const StringPatternConstraint& other) const { return set_operation(other, true); } // union
1027 StringPatternConstraint operator*(const StringPatternConstraint& other) const { return set_operation(other, false); } // intersection
1028 StringPatternConstraint operator~() const { FATAL_ERROR("StringPatternConstraint::operator~(): not implemented"); }
1030 tribool is_subset(const StringPatternConstraint&) const { return TUNKNOWN; }
1031 StringPatternConstraint operator-(const StringPatternConstraint& other) const { return ( *this * ~other ); } // except
1033 string to_string() const;
1036 ////////////////////////////////////////////////////////////////////////////////
1038 template <class STRINGTYPE>
1039 class StringValueConstraint
1042 map<STRINGTYPE,void> values;
1044 void copy_content(const StringValueConstraint& other);
1047 StringValueConstraint() {} // empty set
1048 StringValueConstraint(const STRINGTYPE& s) { values.add(s,NULL); } // single value set
1050 StringValueConstraint(const StringValueConstraint& other) { copy_content(other); }
1051 StringValueConstraint& operator=(const StringValueConstraint& other) { clean_up(); copy_content(other); return *this; }
1052 ~StringValueConstraint() { clean_up(); }
1054 tribool is_empty() const { return TRIBOOL(values.size()==0); }
1055 tribool is_full() const { return TFALSE; }
1056 tribool is_equal(const StringValueConstraint& other) const;
1057 bool is_element(const STRINGTYPE& s) const { return values.has_key(s); }
1059 StringValueConstraint set_operation(const StringValueConstraint& other, bool is_union) const;
1061 StringValueConstraint operator+(const StringValueConstraint& other) const { return set_operation(other, true); } // union
1062 StringValueConstraint operator*(const StringValueConstraint& other) const { return set_operation(other, false); } // intersection
1064 tribool is_subset(const StringValueConstraint& other) const { return (*this-other).is_empty(); }
1065 StringValueConstraint operator-(const StringValueConstraint& other) const; // except
1067 // remove strings that are or are not elements of the set defined by the XXX_constraint object,
1068 // using the XXX_constraint.is_element() member function
1069 void remove(const SizeRangeListConstraint& size_constraint, bool if_element);
1070 template <class CHARLIMITTYPE> void remove(const RangeListConstraint<CHARLIMITTYPE>& alphabet_constraint, bool if_element);
1071 void remove(const StringPatternConstraint& pattern_constraint, bool if_element);
1073 string to_string() const;
1076 template <class STRINGTYPE>
1077 void StringValueConstraint<STRINGTYPE>::clean_up()
1082 template <class STRINGTYPE>
1083 void StringValueConstraint<STRINGTYPE>::copy_content(const StringValueConstraint<STRINGTYPE>& other)
1085 for (size_t i=0; i<other.values.size(); i++) values.add(other.values.get_nth_key(i),NULL);
1088 template <class STRINGTYPE>
1089 tribool StringValueConstraint<STRINGTYPE>::is_equal(const StringValueConstraint<STRINGTYPE>& other) const
1091 if (values.size()!=other.values.size()) return TFALSE;
1092 for (size_t i=0; i<values.size(); i++) {
1093 if (values.get_nth_key(i)!=other.values.get_nth_key(i)) return TFALSE;
1098 template <class STRINGTYPE>
1099 StringValueConstraint<STRINGTYPE> StringValueConstraint<STRINGTYPE>::set_operation
1100 (const StringValueConstraint<STRINGTYPE>& other, bool is_union) const
1102 StringValueConstraint<STRINGTYPE> ret_val;
1104 for (size_t i=0; i<values.size(); i++) ret_val.values.add(values.get_nth_key(i), NULL);
1105 for (size_t i=0; i<other.values.size(); i++) {
1106 const STRINGTYPE& str = other.values.get_nth_key(i);
1107 if (!ret_val.values.has_key(str)) ret_val.values.add(str, NULL);
1110 for (size_t i=0; i<values.size(); i++) {
1111 const STRINGTYPE& str = values.get_nth_key(i);
1112 if (other.values.has_key(str)) ret_val.values.add(str, NULL);
1118 template <class STRINGTYPE>
1119 StringValueConstraint<STRINGTYPE> StringValueConstraint<STRINGTYPE>::operator-(const StringValueConstraint<STRINGTYPE>& other) const
1121 StringValueConstraint<STRINGTYPE> ret_val;
1122 for (size_t i=0; i<values.size(); i++) {
1123 const STRINGTYPE& str = values.get_nth_key(i);
1124 if (!other.values.has_key(str)) ret_val.values.add(str, NULL);
1129 template <class STRINGTYPE>
1130 void StringValueConstraint<STRINGTYPE>::remove(const SizeRangeListConstraint& size_constraint, bool if_element)
1132 for (size_t i=0; i<values.size(); i++) {
1133 STRINGTYPE str = values.get_nth_key(i);
1134 if (size_constraint.is_element(size_limit_t(str.size()))==if_element) {
1141 template <class STRINGTYPE>
1142 template <class CHARLIMITTYPE>
1143 void StringValueConstraint<STRINGTYPE>::remove(const RangeListConstraint<CHARLIMITTYPE>& alphabet_constraint, bool if_element)
1145 for (size_t i=0; i<values.size(); i++) {
1146 STRINGTYPE str = values.get_nth_key(i);
1147 bool all_chars_are_elements = true;
1148 for (size_t chr_idx=0; chr_idx<str.size(); chr_idx++)
1150 if (!alphabet_constraint.is_element(CHARLIMITTYPE(str[chr_idx]))) {
1151 all_chars_are_elements = false;
1155 if (all_chars_are_elements==if_element) {
1162 template <class STRINGTYPE>
1163 void StringValueConstraint<STRINGTYPE>::remove(const StringPatternConstraint& pattern_constraint, bool if_element)
1165 for (size_t i=0; i<values.size(); i++) {
1166 STRINGTYPE str = values.get_nth_key(i);
1167 switch (pattern_constraint.match(str)) {
1169 if (!if_element) { values.erase(str); i--; }
1174 if (if_element) { values.erase(str); i--; }
1177 FATAL_ERROR("StringValueConstraint::remove(StringPatternConstraint)");
1182 template <class STRINGTYPE>
1183 string StringValueConstraint<STRINGTYPE>::to_string() const
1187 for (size_t i=0; i<values.size(); i++) {
1188 if (i>0) ret_val += ',';
1189 STRINGTYPE str = values.get_nth_key(i);
1190 ret_val += str.get_stringRepr();
1196 ////////////////////////////////////////////////////////////////////////////////
1198 // contains a tree of subtype constraints
1199 template <class STRINGTYPE, class CHARLIMITTYPE>
1200 class StringSubtypeTreeElement
1203 enum elementtype_t {
1204 ET_NONE, // empty set
1205 ET_ALL, // all values of the root type, no subtype constraint was given, other data members have no meaning
1206 ET_CONSTRAINT, // constraint value
1207 ET_INTERSECTION, // A intersection B
1208 ET_UNION, // A union B
1209 ET_EXCEPT // A except B
1211 enum constrainttype_t {
1218 elementtype_t elementtype;
1220 struct { // operation (ET_INTERSECTION, ET_UNION, ET_EXCEPT)
1221 StringSubtypeTreeElement* a; // owned
1222 StringSubtypeTreeElement* b; // owned
1224 struct { // constraint
1225 constrainttype_t constrainttype;
1226 union { // constraint objects are owned
1227 SizeRangeListConstraint* s; // size/length constraint type
1229 RangeListConstraint<CHARLIMITTYPE>* c; // range/alphabet constraint type
1230 bool char_context; // this constraint can be either in char or string context
1231 // char context is constraining a single char,
1232 // string context is constraining a string
1233 // this bool value affects evaluation
1234 // in char context only range,all,none and operation
1235 // constructors can be called, operations must always evaluate
1236 // to range, all or none
1238 StringValueConstraint<STRINGTYPE>* v; // value set constraint
1239 StringPatternConstraint* p; // pattern constraint
1244 void copy_content(const StringSubtypeTreeElement& other); // *this must be empty
1245 void set_to_operand(bool operand_a);
1246 void simplify(); // convert to ET_NONE or ET_ALL if possible
1247 void evaluate(); // tries to evaluate a tree to a single constraint, works recursively for the whole tree
1249 StringSubtypeTreeElement(): elementtype(ET_NONE) {}
1250 StringSubtypeTreeElement(elementtype_t p_elementtype, StringSubtypeTreeElement* p_a, StringSubtypeTreeElement* p_b);
1251 StringSubtypeTreeElement(const SizeRangeListConstraint& p_s);
1252 StringSubtypeTreeElement(const RangeListConstraint<CHARLIMITTYPE>& p_a, bool p_char_context);
1253 StringSubtypeTreeElement(const StringValueConstraint<STRINGTYPE>& p_v);
1254 StringSubtypeTreeElement(const StringPatternConstraint& p_p);
1256 StringSubtypeTreeElement(const StringSubtypeTreeElement& p) { copy_content(p); }
1257 StringSubtypeTreeElement& operator=(const StringSubtypeTreeElement& other) { clean_up(); copy_content(other); return *this; }
1258 ~StringSubtypeTreeElement() { clean_up(); }
1260 tribool is_empty() const;
1261 tribool is_full() const;
1262 tribool is_equal(const StringSubtypeTreeElement* other) const;
1263 bool is_element(const STRINGTYPE& s) const;
1264 tribool is_subset(const StringSubtypeTreeElement* other) const;
1266 bool is_single_constraint() const { return ( (elementtype==ET_CONSTRAINT) || (elementtype==ET_NONE) || (elementtype==ET_ALL) ); }
1267 void set_none() { clean_up(); elementtype = ET_NONE; }
1268 void set_all() { clean_up(); elementtype = ET_ALL; }
1271 TFALSE: limit does not exist (empty set or values, ...)
1272 TUNKNOWN: limit cannot be determined
1273 TTRUE: limit was set to the proper value */
1274 tribool get_alphabet_limit(bool is_upper, CHARLIMITTYPE& limit) const;
1275 tribool get_size_limit(bool is_upper, size_limit_t& limit) const;
1277 bool is_valid_range() const;
1278 void set_char_context(bool p_char_context);
1280 string to_string() const;
1283 template <class STRINGTYPE, class CHARLIMITTYPE>
1284 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement(elementtype_t p_elementtype, StringSubtypeTreeElement* p_a, StringSubtypeTreeElement* p_b)
1285 : elementtype(p_elementtype)
1287 switch (elementtype) {
1288 case ET_INTERSECTION:
1293 FATAL_ERROR("StringSubtypeTreeElement::StringSubtypeTreeElement()");
1301 template <class STRINGTYPE, class CHARLIMITTYPE>
1302 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::
1303 get_alphabet_limit(bool is_upper, CHARLIMITTYPE& limit) const
1305 switch (elementtype) {
1309 limit = is_upper ? CHARLIMITTYPE::maximum : CHARLIMITTYPE::minimum;
1312 switch (u.cs.constrainttype) {
1314 limit = is_upper ? CHARLIMITTYPE::maximum : CHARLIMITTYPE::minimum;
1317 if (u.cs.a.c->is_empty()==TTRUE) return TFALSE;
1318 limit = is_upper ? u.cs.a.c->get_maximal() : u.cs.a.c->get_minimal();
1325 FATAL_ERROR("StringSubtypeTreeElement::get_alphabet_limit()");
1327 case ET_INTERSECTION: {
1328 CHARLIMITTYPE la, lb;
1329 tribool tb = u.op.a->get_alphabet_limit(is_upper, la) && u.op.b->get_alphabet_limit(is_upper, lb);
1331 limit = ((lb<la) ^ !is_upper) ? lb : la;
1339 FATAL_ERROR("StringSubtypeTreeElement::get_alphabet_limit()");
1344 template <class STRINGTYPE, class CHARLIMITTYPE>
1345 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::
1346 get_size_limit(bool is_upper, size_limit_t& limit) const
1348 switch (elementtype) {
1352 limit = is_upper ? size_limit_t::maximum : size_limit_t::minimum;
1355 switch (u.cs.constrainttype) {
1357 if (u.cs.s->is_empty()==TTRUE) return TFALSE;
1358 limit = is_upper ? u.cs.s->get_maximal() : u.cs.s->get_minimal();
1361 limit = is_upper ? size_limit_t::maximum : size_limit_t::minimum;
1368 FATAL_ERROR("StringSubtypeTreeElement::get_size_limit()");
1370 case ET_INTERSECTION: {
1371 size_limit_t la, lb;
1372 tribool tb = u.op.a->get_size_limit(is_upper, la) && u.op.b->get_size_limit(is_upper, lb);
1374 limit = ((lb<la) ^ !is_upper) ? lb : la;
1382 FATAL_ERROR("StringSubtypeTreeElement::get_size_limit()");
1387 template <class STRINGTYPE, class CHARLIMITTYPE>
1388 bool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_valid_range() const
1390 switch (elementtype) {
1395 switch (u.cs.constrainttype) {
1398 return (u.cs.s->is_equal(SizeRangeListConstraint(size_limit_t(1)))==TTRUE);
1405 FATAL_ERROR("StringSubtypeTreeElement::is_valid_range()");
1407 case ET_INTERSECTION:
1410 return ( u.op.a->is_valid_range() && u.op.b->is_valid_range() );
1412 FATAL_ERROR("StringSubtypeTreeElement::is_valid_range()");
1417 template <class STRINGTYPE, class CHARLIMITTYPE>
1418 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::set_char_context(bool p_char_context)
1420 switch (elementtype) {
1425 u.cs.a.char_context = p_char_context;
1426 switch (u.cs.constrainttype) {
1428 if (p_char_context) set_all(); // false -> true
1429 else FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1433 FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1436 case ET_INTERSECTION:
1439 u.op.a->set_char_context(p_char_context);
1440 u.op.b->set_char_context(p_char_context);
1443 FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1447 template <class STRINGTYPE, class CHARLIMITTYPE>
1448 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1449 (const SizeRangeListConstraint& p_s):
1450 elementtype(ET_CONSTRAINT)
1452 u.cs.constrainttype = CT_SIZE;
1453 u.cs.s = new SizeRangeListConstraint(p_s);
1457 template <class STRINGTYPE, class CHARLIMITTYPE>
1458 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1459 (const RangeListConstraint<CHARLIMITTYPE>& p_a, bool p_char_context):
1460 elementtype(ET_CONSTRAINT)
1462 u.cs.constrainttype = CT_ALPHABET;
1463 u.cs.a.c = new RangeListConstraint<CHARLIMITTYPE>(p_a);
1464 u.cs.a.char_context = p_char_context;
1468 template <class STRINGTYPE, class CHARLIMITTYPE>
1469 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1470 (const StringValueConstraint<STRINGTYPE>& p_v):
1471 elementtype(ET_CONSTRAINT)
1473 u.cs.constrainttype = CT_VALUES;
1474 u.cs.v = new StringValueConstraint<STRINGTYPE>(p_v);
1478 template <class STRINGTYPE, class CHARLIMITTYPE>
1479 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1480 (const StringPatternConstraint& p_p):
1481 elementtype(ET_CONSTRAINT)
1483 u.cs.constrainttype = CT_PATTERN;
1484 u.cs.p = new StringPatternConstraint(p_p);
1488 template <class STRINGTYPE, class CHARLIMITTYPE>
1489 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::clean_up()
1491 switch (elementtype) {
1496 switch (u.cs.constrainttype) {
1497 case CT_SIZE: delete u.cs.s; break;
1498 case CT_ALPHABET: delete u.cs.a.c; break;
1499 case CT_VALUES: delete u.cs.v; break;
1500 case CT_PATTERN: delete u.cs.p; break;
1501 default: FATAL_ERROR("StringSubtypeTreeElement::clean_up()");
1504 case ET_INTERSECTION:
1511 FATAL_ERROR("StringSubtypeTreeElement::clean_up()");
1515 template <class STRINGTYPE, class CHARLIMITTYPE>
1516 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::copy_content(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>& other)
1518 elementtype = other.elementtype;
1519 switch (elementtype) {
1524 u.cs.constrainttype = other.u.cs.constrainttype;
1525 switch (u.cs.constrainttype) {
1526 case CT_SIZE: u.cs.s = new SizeRangeListConstraint(*(other.u.cs.s)); break;
1528 u.cs.a.c = new RangeListConstraint<CHARLIMITTYPE>(*(other.u.cs.a.c));
1529 u.cs.a.char_context = other.u.cs.a.char_context;
1531 case CT_VALUES: u.cs.v = new StringValueConstraint<STRINGTYPE>(*(other.u.cs.v)); break;
1532 case CT_PATTERN: u.cs.p = new StringPatternConstraint(*(other.u.cs.p)); break;
1533 default: FATAL_ERROR("StringSubtypeTreeElement::copy_content()");
1536 case ET_INTERSECTION:
1539 u.op.a = new StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>(*(other.u.op.a));
1540 u.op.b = new StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>(*(other.u.op.b));
1543 FATAL_ERROR("StringSubtypeTreeElement::copy_content()");
1547 template <class STRINGTYPE, class CHARLIMITTYPE>
1548 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::set_to_operand(bool operand_a)
1550 switch (elementtype) {
1551 case ET_INTERSECTION:
1556 FATAL_ERROR("StringSubtypeTreeElement::copy_operand()");
1558 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* op;
1566 // steal the content of op into myself
1567 elementtype = op->elementtype;
1568 switch (elementtype) {
1573 u.cs.constrainttype = op->u.cs.constrainttype;
1574 switch (u.cs.constrainttype) {
1575 case CT_SIZE: u.cs.s = op->u.cs.s; break;
1577 u.cs.a.c = op->u.cs.a.c;
1578 u.cs.a.char_context = op->u.cs.a.char_context;
1580 case CT_VALUES: u.cs.v = op->u.cs.v; break;
1581 case CT_PATTERN: u.cs.p = op->u.cs.p; break;
1582 default: FATAL_ERROR("StringSubtypeTreeElement::copy_operand()");
1585 case ET_INTERSECTION:
1588 u.op.a = op->u.op.a;
1589 u.op.b = op->u.op.b;
1592 FATAL_ERROR("StringSubtypeTreeElement::copy_operand()");
1594 // delete the empty op
1595 op->elementtype = ET_NONE;
1599 template <class STRINGTYPE, class CHARLIMITTYPE>
1600 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::simplify()
1602 switch (elementtype) {
1607 switch (u.cs.constrainttype) {
1609 if (u.cs.s->is_empty()==TTRUE) { set_none(); return; }
1610 if (u.cs.s->is_full()==TTRUE) { set_all(); return; }
1613 if (u.cs.a.c->is_empty()==TTRUE) { set_none(); return; }
1614 if (u.cs.a.c->is_full()==TTRUE) { set_all(); return; }
1617 if (u.cs.v->is_empty()==TTRUE) { set_none(); return; }
1618 if (u.cs.v->is_full()==TTRUE) { set_all(); return; }
1621 if (u.cs.p->is_empty()==TTRUE) { set_none(); return; }
1622 if (u.cs.p->is_full()==TTRUE) { set_all(); return; }
1624 default: FATAL_ERROR("StringSubtypeTreeElement::simplify()");
1627 case ET_INTERSECTION:
1632 FATAL_ERROR("StringSubtypeTreeElement::simplify()");
1636 template <class STRINGTYPE, class CHARLIMITTYPE>
1637 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_empty() const
1639 switch (elementtype) {
1645 switch (u.cs.constrainttype) {
1646 case CT_SIZE: return u.cs.s->is_empty();
1647 case CT_ALPHABET: return ( u.cs.a.char_context ? u.cs.a.c->is_empty() : TFALSE );
1648 case CT_VALUES: return u.cs.v->is_empty();
1649 case CT_PATTERN: return u.cs.p->is_empty();
1650 default: FATAL_ERROR("StringSubtypeTreeElement::is_empty()");
1652 case ET_INTERSECTION:
1653 return ( u.op.a->is_empty() || u.op.b->is_empty() );
1655 return ( u.op.a->is_empty() && u.op.b->is_empty() );
1657 tribool a_empty = u.op.a->is_empty();
1658 return ( (a_empty!=TFALSE) ? a_empty :
1659 ( (u.op.b->is_empty()==TTRUE) ? TFALSE : TUNKNOWN ) );
1662 FATAL_ERROR("StringSubtypeTreeElement::is_empty()");
1667 template <class STRINGTYPE, class CHARLIMITTYPE>
1668 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_full() const
1670 switch (elementtype) {
1676 switch (u.cs.constrainttype) {
1677 case CT_SIZE: return u.cs.s->is_full();
1678 case CT_ALPHABET: return u.cs.a.c->is_full();
1679 case CT_VALUES: return u.cs.v->is_full();
1680 case CT_PATTERN: return u.cs.p->is_full();
1681 default: FATAL_ERROR("StringSubtypeTreeElement::is_full()");
1683 case ET_INTERSECTION:
1684 return ( u.op.a->is_full() && u.op.b->is_full() );
1686 return ( u.op.a->is_full() || u.op.b->is_full() );
1688 return ( u.op.a->is_full() && u.op.b->is_empty() );
1690 FATAL_ERROR("StringSubtypeTreeElement::is_full()");
1695 template <class STRINGTYPE, class CHARLIMITTYPE>
1696 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_equal(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* other) const
1698 if (elementtype!=other->elementtype) return TUNKNOWN;
1699 switch (elementtype) {
1704 if (u.cs.constrainttype!=other->u.cs.constrainttype) return TUNKNOWN;
1705 switch (u.cs.constrainttype) {
1706 case CT_SIZE: return u.cs.s->is_equal(*(other->u.cs.s));
1707 case CT_ALPHABET: return u.cs.a->is_equal(*(other->u.cs.a));
1708 case CT_VALUES: return u.cs.v->is_equal(*(other->u.cs.v));
1709 case CT_PATTERN: return u.cs.p->is_equal(*(other->u.cs.p));
1710 default: FATAL_ERROR("StringSubtypeTreeElement::is_equal()");
1712 case ET_INTERSECTION:
1717 FATAL_ERROR("StringSubtypeTreeElement::is_equal()");
1722 template <class STRINGTYPE, class CHARLIMITTYPE>
1723 bool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_element(const STRINGTYPE& s) const
1725 switch (elementtype) {
1731 switch (u.cs.constrainttype) {
1732 case CT_SIZE: return u.cs.s->is_element(size_limit_t(s.size()));
1734 for (size_t i=0; i<s.size(); i++) {
1735 CHARLIMITTYPE cl(s[i]);
1736 if (!u.cs.a.c->is_element(cl)) return false;
1740 case CT_VALUES: return u.cs.v->is_element(s);
1742 switch (u.cs.p->match(s)) {
1743 case TFALSE: return false;
1744 case TUNKNOWN: return true; // don't know if it matches
1745 case TTRUE: return true;
1746 default: FATAL_ERROR("StringSubtypeTreeElement::is_element()");
1749 default: FATAL_ERROR("StringSubtypeTreeElement::is_element()");
1751 case ET_INTERSECTION:
1752 return ( u.op.a->is_element(s) && u.op.b->is_element(s) );
1754 return ( u.op.a->is_element(s) || u.op.b->is_element(s) );
1756 return ( u.op.a->is_element(s) && !u.op.b->is_element(s) );
1758 FATAL_ERROR("StringSubtypeTreeElement::is_element()");
1763 // if the constraints are ortogonal (e.g. size and alphabet) or just different then return TUNKNOWN
1764 // in case of ortogonal constraints we should return TFALSE (if other is not full set)
1765 // but it seems that the standard wants to ignore such trivial cases, example:
1766 // length(1..4) is_subset ('a'..'z') shall not report an error
1767 template <class STRINGTYPE, class CHARLIMITTYPE>
1768 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_subset(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* other) const
1770 switch (elementtype) {
1774 if (other->elementtype==ET_ALL) return TTRUE;
1775 else return TUNKNOWN;
1777 if (elementtype!=other->elementtype) return TUNKNOWN;
1778 if (u.cs.constrainttype!=other->u.cs.constrainttype) return TUNKNOWN;
1779 switch (u.cs.constrainttype) {
1780 case CT_SIZE: return u.cs.s->is_subset(*(other->u.cs.s));
1781 case CT_ALPHABET: return u.cs.a.c->is_subset(*(other->u.cs.a.c));
1782 case CT_VALUES: return u.cs.v->is_subset(*(other->u.cs.v));
1783 case CT_PATTERN: return u.cs.p->is_subset(*(other->u.cs.p));
1784 default: FATAL_ERROR("StringSubtypeTreeElement::is_subset()");
1786 case ET_INTERSECTION:
1791 FATAL_ERROR("StringSubtypeTreeElement::is_subset()");
1796 template <class STRINGTYPE, class CHARLIMITTYPE>
1797 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::evaluate()
1799 switch (elementtype) {
1803 // these are the simplest forms, others are reduced to these in ideal case
1805 case ET_INTERSECTION:
1810 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
1813 // recursive evaluation
1817 // special case where the construct looks like this:
1821 // can be union or intersection, try to exchange constraint to have same type of constraints as operands,
1822 // constraint types: tree, ....
1823 // if succeeded then evaluate the new construct
1826 // special simple cases when one side is ET_ALL or ET_NONE but the other can be a tree
1827 if ( (u.op.a->elementtype==ET_NONE) || (u.op.b->elementtype==ET_NONE) ) {
1828 if (elementtype==ET_INTERSECTION) { set_none(); return; }
1829 if (elementtype==ET_UNION) {
1830 // the result is the other set
1831 set_to_operand(u.op.b->elementtype==ET_NONE);
1835 if ( (u.op.b->elementtype==ET_NONE) && (elementtype==ET_EXCEPT) ) {
1836 set_to_operand(true);
1839 if ( (u.op.a->elementtype==ET_ALL) || (u.op.b->elementtype==ET_ALL) ) {
1840 if (elementtype==ET_INTERSECTION) {
1841 // the result is the other set
1842 set_to_operand(u.op.b->elementtype==ET_ALL);
1845 if (elementtype==ET_UNION) { set_all(); return; }
1847 if ( (u.op.b->elementtype==ET_ALL) && (elementtype==ET_EXCEPT) ) { set_none(); return; }
1849 // both operands must be single constraints (ALL,NONE,CONSTRAINT),
1850 // after this point trees will not be further simplified
1851 if (!u.op.a->is_single_constraint() || !u.op.b->is_single_constraint()) return;
1853 // special case: ALL - some constraint type that can be complemented
1854 if ( (u.op.a->elementtype==ET_ALL) && (elementtype==ET_EXCEPT) && (u.op.b->elementtype==ET_CONSTRAINT) ) {
1855 switch (u.op.b->u.cs.constrainttype) {
1857 SizeRangeListConstraint* rvs = new SizeRangeListConstraint(~*(u.op.b->u.cs.s));
1859 elementtype = ET_CONSTRAINT;
1860 u.cs.constrainttype = CT_SIZE;
1865 if (u.cs.a.char_context) {
1866 RangeListConstraint<CHARLIMITTYPE>* rva = new RangeListConstraint<CHARLIMITTYPE>(~*(u.op.b->u.cs.a.c));
1868 elementtype = ET_CONSTRAINT;
1869 u.cs.constrainttype = CT_ALPHABET;
1871 u.cs.a.char_context = true;
1880 // special case: when one operand is CT_VALUES then is_element() can be called for the values
1881 // and drop values or drop the other operand set or both depending on the operation
1882 StringValueConstraint<STRINGTYPE>* svc = NULL;
1883 bool first_is_svc = false;
1884 if ( (u.op.a->elementtype==ET_CONSTRAINT) && (u.op.a->u.cs.constrainttype==CT_VALUES) ) {
1885 svc = u.op.a->u.cs.v;
1886 first_is_svc = true;
1887 } else if ( (u.op.b->elementtype==ET_CONSTRAINT) && (u.op.b->u.cs.constrainttype==CT_VALUES) ) {
1888 svc = u.op.b->u.cs.v;
1889 first_is_svc = false; // it's the second
1891 if (svc!=NULL) { // if one or both operands are CT_VALUES
1892 switch (elementtype) {
1893 case ET_INTERSECTION: {
1894 switch (first_is_svc ? u.op.b->u.cs.constrainttype : u.op.a->u.cs.constrainttype) {
1896 svc->remove(*(first_is_svc ? u.op.b->u.cs.s : u.op.a->u.cs.s), false);
1899 svc->remove(*(first_is_svc ? u.op.b->u.cs.a.c : u.op.a->u.cs.a.c), false);
1902 svc->remove(*(first_is_svc ? u.op.b->u.cs.p : u.op.a->u.cs.p), false);
1907 // drop the other operand, keep the values as constraint of this object
1908 StringValueConstraint<STRINGTYPE>* keep_svc = new StringValueConstraint<STRINGTYPE>(*svc);
1910 elementtype = ET_CONSTRAINT;
1911 u.cs.constrainttype = CT_VALUES;
1917 switch (first_is_svc ? u.op.b->u.cs.constrainttype : u.op.a->u.cs.constrainttype) {
1919 svc->remove(*(first_is_svc ? u.op.b->u.cs.s : u.op.a->u.cs.s), true);
1922 svc->remove(*(first_is_svc ? u.op.b->u.cs.a.c : u.op.a->u.cs.a.c), true);
1925 svc->remove(*(first_is_svc ? u.op.b->u.cs.p : u.op.a->u.cs.p), true);
1930 // if all values were dropped then drop the empty values operand
1931 if (svc->is_empty()==TTRUE) {
1932 set_to_operand(!first_is_svc);
1937 if (first_is_svc) { // the second operand is u.op.b->u.cs.X where X can be length/alphabet/pattern constraint
1938 switch (u.op.b->u.cs.constrainttype) {
1940 svc->remove(*(u.op.b->u.cs.s), true);
1943 svc->remove(*(u.op.b->u.cs.a.c), true);
1946 svc->remove(*(u.op.b->u.cs.p), true);
1951 // drop the other operand, keep the values as constraint of this object
1952 StringValueConstraint<STRINGTYPE>* keep_svc = new StringValueConstraint<STRINGTYPE>(*svc);
1954 elementtype = ET_CONSTRAINT;
1955 u.cs.constrainttype = CT_VALUES;
1962 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
1966 // operands of same types can be evaluated to one constraint using their
1967 // set arithmetic member functions
1968 // alphabet constraint in string context:
1969 // FROM(A) UNION FROM(B) =/= FROM(A UNION B)
1970 // ALL - FROM(A) =/= FROM(ALL - A)
1971 // FROM(A) INTERSECTION FROM(B) == FROM (A INTERSECTION B)
1972 if (u.op.a->elementtype==u.op.b->elementtype) {
1973 switch (u.op.a->elementtype) {
1975 if (elementtype==ET_EXCEPT) set_none();
1982 if (u.op.a->u.cs.constrainttype==u.op.b->u.cs.constrainttype) {
1983 switch (u.op.a->u.cs.constrainttype) {
1985 SizeRangeListConstraint* rvs = new SizeRangeListConstraint;
1986 switch (elementtype) {
1987 case ET_INTERSECTION:
1988 *rvs = *(u.op.a->u.cs.s) * *(u.op.b->u.cs.s);
1991 *rvs = *(u.op.a->u.cs.s) + *(u.op.b->u.cs.s);
1994 *rvs = *(u.op.a->u.cs.s) - *(u.op.b->u.cs.s);
1997 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2000 elementtype = ET_CONSTRAINT;
2001 u.cs.constrainttype = CT_SIZE;
2005 bool char_ctx = u.op.a->u.cs.a.char_context;
2006 if (u.op.b->u.cs.a.char_context!=char_ctx) FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2007 if (char_ctx || (elementtype==ET_INTERSECTION)) {
2008 RangeListConstraint<CHARLIMITTYPE>* rva = new RangeListConstraint<CHARLIMITTYPE>;
2009 switch (elementtype) {
2010 case ET_INTERSECTION:
2011 *rva = *(u.op.a->u.cs.a.c) * *(u.op.b->u.cs.a.c);
2014 *rva = *(u.op.a->u.cs.a.c) + *(u.op.b->u.cs.a.c);
2017 *rva = *(u.op.a->u.cs.a.c) - *(u.op.b->u.cs.a.c);
2020 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2023 elementtype = ET_CONSTRAINT;
2024 u.cs.constrainttype = CT_ALPHABET;
2026 u.cs.a.char_context = char_ctx;
2030 StringValueConstraint<STRINGTYPE>* rvv = new StringValueConstraint<STRINGTYPE>;
2031 switch (elementtype) {
2032 case ET_INTERSECTION:
2033 *rvv = *(u.op.a->u.cs.v) * *(u.op.b->u.cs.v);
2036 *rvv = *(u.op.a->u.cs.v) + *(u.op.b->u.cs.v);
2039 *rvv = *(u.op.a->u.cs.v) - *(u.op.b->u.cs.v);
2042 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2045 elementtype = ET_CONSTRAINT;
2046 u.cs.constrainttype = CT_VALUES;
2052 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2057 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2063 template <class STRINGTYPE, class CHARLIMITTYPE>
2064 string StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::to_string() const
2067 bool print_operation = false;
2069 switch (elementtype) {
2076 switch (u.cs.constrainttype) {
2078 ret_val += "length";
2079 ret_val += u.cs.s->to_string();
2082 ret_val += u.cs.a.char_context ? "range" : "from";
2083 ret_val += u.cs.a.c->to_string();
2086 ret_val += u.cs.v->to_string();
2089 ret_val += u.cs.p->to_string();
2092 FATAL_ERROR("StringSubtypeTreeElement::to_string()");
2095 case ET_INTERSECTION:
2096 op_str = "intersection";
2097 print_operation = true;
2101 print_operation = true;
2105 print_operation = true;
2108 FATAL_ERROR("StringSubtypeTreeElement::to_string()");
2110 if (print_operation) {
2112 ret_val += u.op.a->to_string();
2116 ret_val += u.op.b->to_string();
2122 typedef StringSubtypeTreeElement<string,char_limit_t> CharstringSubtypeTreeElement;
2123 typedef StringSubtypeTreeElement<ustring,universal_char_limit_t> UniversalCharstringSubtypeTreeElement;
2125 ////////////////////////////////////////////////////////////////////////////////
2126 // constraint classes for structured types
2128 // used by ValueListConstraint and RecofConstraint classes
2129 // only operator==() is used, since most value types do not have operator<()
2130 // when used in RecofConstraint it will use Value::get_nof_comps()
2134 vector<Value> values; // values are not owned
2136 void copy_content(const ValueList& other);
2138 ValueList() : values() {} // empty set
2139 ValueList(Value* v) : values() { values.add(v); }
2141 ValueList(const ValueList& other) : values() { copy_content(other); }
2142 ValueList& operator=(const ValueList& other) { clean_up(); copy_content(other); return *this; }
2143 ~ValueList() { clean_up(); }
2145 tribool is_empty() const { return TRIBOOL(values.size()==0); }
2146 tribool is_full() const { return TUNKNOWN; } // it's unknown how many possible values we have
2147 tribool is_equal(const ValueList& other) const;
2148 bool is_element(Value* v) const;
2150 // remove all elements whose size is (not) element of the given length set
2151 // works only if the type of values is correct (the get_nof_comps() doesn't end in FATAL_ERROR)
2152 void remove(const SizeRangeListConstraint& size_constraint, bool if_element);
2154 ValueList set_operation(const ValueList& other, bool is_union) const;
2156 ValueList operator+(const ValueList& other) const { return set_operation(other, true); } // union
2157 ValueList operator*(const ValueList& other) const { return set_operation(other, false); } // intersection
2158 ValueList operator-(const ValueList& other) const; // except
2160 tribool is_subset(const ValueList& other) const { return (*this-other).is_empty(); }
2162 string to_string() const;
2165 // can be a ValueList or (ALL-ValueList), used for subtypes of structured types, enumerated and objid
2166 class ValueListConstraint
2172 ValueListConstraint(): complemented(false), values() {} // empty set
2173 ValueListConstraint(Value* v): complemented(false), values(v) {} // single element set
2174 ValueListConstraint(bool p_complemented): complemented(p_complemented), values() {} // empty of full set
2176 tribool is_empty() const;
2177 tribool is_full() const;
2178 tribool is_equal(const ValueListConstraint& other) const;
2179 bool is_element(Value* v) const;
2181 ValueListConstraint operator+(const ValueListConstraint& other) const; // union
2182 ValueListConstraint operator*(const ValueListConstraint& other) const; // intersection
2183 ValueListConstraint operator~() const; // complement
2185 inline tribool is_subset(const ValueListConstraint& other) const
2186 { return (*this*~other).is_empty(); }
2187 inline ValueListConstraint operator-(const ValueListConstraint& other) const
2188 { return ( *this * ~other ); } // except
2190 string to_string() const;
2193 // length and value list constraints for record/set of types
2194 class RecofConstraint
2197 SizeRangeListConstraint size_constraint;
2198 ValueList has_values, not_values;
2201 RecofConstraint(): size_constraint(), has_values(), not_values() {} // empty set
2202 RecofConstraint(Value* v): size_constraint(), has_values(v), not_values() {} // single value set
2203 RecofConstraint(const size_limit_t& sl): size_constraint(sl), has_values(), not_values() {} // single size value set
2204 RecofConstraint(const size_limit_t& rl_begin, const size_limit_t& rl_end)
2205 : size_constraint(rl_begin,rl_end), has_values(), not_values() {} // size range set
2206 RecofConstraint(const SizeRangeListConstraint& p_size_constraint)
2207 : size_constraint(p_size_constraint), has_values(), not_values() {}
2209 tribool is_empty() const;
2210 tribool is_full() const;
2211 tribool is_equal(const RecofConstraint& other) const;
2212 bool is_element(Value* v) const;
2214 RecofConstraint set_operation(const RecofConstraint& other, bool is_union) const;
2216 inline RecofConstraint operator+(const RecofConstraint& other) const { return set_operation(other, true); } // union
2217 inline RecofConstraint operator*(const RecofConstraint& other) const { return set_operation(other, false); } // intersection
2218 RecofConstraint operator~() const; // complement
2220 inline tribool is_subset(const RecofConstraint& other) const { return (*this*~other).is_empty(); }
2221 inline RecofConstraint operator-(const RecofConstraint& other) const { return ( *this * ~other ); } // except
2223 tribool get_size_limit(bool is_upper, size_limit_t& limit) const;
2225 string to_string() const;
2229 }// namespace Common
2231 #endif // #ifndef _Subtypestuff_HH