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
15 ******************************************************************************/
16 #ifndef _Subtypestuff_HH
17 #define _Subtypestuff_HH
19 #include "ttcn3/compiler.h"
26 #include "../common/ttcn3float.hh"
29 class LengthRestriction;
42 enum tribool // http://en.wikipedia.org/wiki/Ternary_logic
44 TFALSE = 0, // values are indexes into truth tables
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);
55 ////////////////////////////////////////////////////////////////////////////////
57 // integer interval limit type, can be +/- infinity, in case of infinity value has no meaning
61 enum int_limit_type_t {
66 static const int_limit_t minimum;
67 static const int_limit_t maximum;
69 int_limit_type_t type;
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;
88 ////////////////////////////////////////////////////////////////////////////////
90 // limit value for length/size restriction
94 enum size_limit_type_t {
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;
120 ////////////////////////////////////////////////////////////////////////////////
122 // limit value for string range/alphabet restriction
127 static const short int max_char;
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;
146 ////////////////////////////////////////////////////////////////////////////////
148 class universal_char_limit_t
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;
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;
176 ////////////////////////////////////////////////////////////////////////////////
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
186 static const real_limit_t minimum;
187 static const real_limit_t maximum;
189 real_limit_type_t type;
191 void check_value() const; // check for illegal values: NaN, -inf.lower and inf.upper
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(); }
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;
210 ////////////////////////////////////////////////////////////////////////////////
212 // forward declaration
213 template <typename LIMITTYPE>
214 class RangeListConstraint;
216 bool convert_int_to_size(const RangeListConstraint<int_limit_t>& int_range, RangeListConstraint<size_limit_t>& size_range);
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
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)
228 template <typename LIMITTYPE>
229 class RangeListConstraint
232 // used in calculating the union and intersection of two sets, _idx are indexes into the values[] vector of the operand sets
235 int a_idx; // index into the operand's values/intervals vectors or -1
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) {}
244 dynamic_array<LIMITTYPE> values;
245 dynamic_array<bool> intervals;
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
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;
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
263 tribool is_subset(const RangeListConstraint& other) const { return (*this*~other).is_empty(); }
264 RangeListConstraint operator-(const RangeListConstraint& other) const { return ( *this * ~other ); } // except
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;
271 bool is_upper_limit_infinity() const;
272 bool is_lower_limit_infinity() const;
274 string to_string(bool add_brackets=true) const;
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);
282 template <typename LIMITTYPE>
283 RangeListConstraint<LIMITTYPE>::RangeListConstraint(const LIMITTYPE& l)
284 : values(), intervals()
286 l.check_single_value();
288 intervals.add(false);
291 template <typename LIMITTYPE>
292 RangeListConstraint<LIMITTYPE>::RangeListConstraint(const LIMITTYPE& l_begin, const LIMITTYPE& l_end)
293 : values(), intervals()
295 if (l_end<l_begin) FATAL_ERROR("RangeListConstraint::RangeListConstraint(): invalid range");
296 if (l_begin==l_end) {
297 l_begin.check_single_value();
299 intervals.add(false);
301 l_begin.check_interval_start();
302 l_end.check_interval_end();
306 intervals.add(false);
310 template <typename LIMITTYPE>
311 tribool RangeListConstraint<LIMITTYPE>::is_empty() const
313 return TRIBOOL(values.size()==0);
316 template <typename LIMITTYPE>
317 tribool RangeListConstraint<LIMITTYPE>::is_full() const
319 return TRIBOOL( (values.size()==2) && (values[0]==LIMITTYPE::minimum) && (values[1]==LIMITTYPE::maximum) && (intervals[0]) );
322 template <typename LIMITTYPE>
323 tribool RangeListConstraint<LIMITTYPE>::is_equal(const RangeListConstraint<LIMITTYPE>& other) const
325 return TRIBOOL( (values==other.values) && (intervals==other.intervals) );
328 template <typename LIMITTYPE>
329 bool RangeListConstraint<LIMITTYPE>::is_element(const LIMITTYPE& l) const
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;
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 );
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];
353 template <typename LIMITTYPE>
354 RangeListConstraint<LIMITTYPE> RangeListConstraint<LIMITTYPE>::operator~() const
356 if (values.size()==0) { // if we have an empty set
357 return RangeListConstraint<LIMITTYPE>(LIMITTYPE::minimum, LIMITTYPE::maximum);
359 RangeListConstraint<LIMITTYPE> ret_val;
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);
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);
372 int last = values.size()-1;
373 for (int i=0; i<last; 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);
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);
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);
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);
403 template <typename LIMITTYPE>
404 RangeListConstraint<LIMITTYPE> RangeListConstraint<LIMITTYPE>::set_operation(const RangeListConstraint<LIMITTYPE>& other, bool is_union) const
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;
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()) )
415 if (spi.a_idx>=(int)values.size()) {
416 sweep_points.add(sweep_point_t(-1,spi.b_idx));
418 } else if (spi.b_idx>=(int)other.values.size()) {
419 sweep_points.add(sweep_point_t(spi.a_idx, -1));
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));
425 } else if (values[spi.a_idx]==other.values[spi.b_idx]) {
426 sweep_points.add(spi);
430 sweep_points.add(sweep_point_t(-1,spi.b_idx));
436 // sweep (iterate) through both vectors
437 bool in_a = false; // we are already in an interval of A
439 for (int i=0; i<(int)sweep_points.size(); i++)
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
446 if (intervals[sweep_points[i].a_idx]) { // this is a starting point of an interval in A
448 if (in_a) FATAL_ERROR("RangeListConstraint::set_operation(): invalid double interval");
450 } else { // this point ends an interval of A
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
460 if (other.intervals[sweep_points[i].b_idx]) { // this is a starting point of an interval in B
462 if (in_b) FATAL_ERROR("RangeListConstraint::set_operation(): invalid double interval");
464 } else { // this point ends an interval of B
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;
475 // canonicalization of ret_val
477 // connect adjacent limit points with interval: [i,i+1] becomes interval
478 for (int i=1; i<(int)sweep_points.size(); i++)
480 LIMITTYPE first, second;
481 if (sweep_points[i-1].a_idx!=-1) {
482 first = values[sweep_points[i-1].a_idx];
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()");
487 if (sweep_points[i].a_idx!=-1) {
488 second = values[sweep_points[i].a_idx];
490 if (sweep_points[i].b_idx!=-1) second = other.values[sweep_points[i].b_idx];
491 else FATAL_ERROR("RangeListConstraint::set_operation()");
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;
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++)
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
508 if (sweep_points[i].a_idx!=-1) {
509 l = values[sweep_points[i].a_idx];
511 if (sweep_points[i].b_idx!=-1) l = other.values[sweep_points[i].b_idx];
512 else FATAL_ERROR("RangeListConstraint::set_operation()");
514 ret_val.values.add(l);
515 ret_val.intervals.add(sweep_points[i].union_interval);
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
523 if (sweep_points[i].a_idx!=-1) {
524 l = values[sweep_points[i].a_idx];
526 if (sweep_points[i].b_idx!=-1) l = other.values[sweep_points[i].b_idx];
527 else FATAL_ERROR("RangeListConstraint::set_operation()");
529 ret_val.values.add(l);
530 ret_val.intervals.add(sweep_points[i].intersection_interval);
538 template <typename LIMITTYPE>
539 LIMITTYPE RangeListConstraint<LIMITTYPE>::get_minimal() const
541 if (values.size()<1) return LIMITTYPE();
545 template <typename LIMITTYPE>
546 LIMITTYPE RangeListConstraint<LIMITTYPE>::get_maximal() const
548 if (values.size()<1) return LIMITTYPE();
549 return values[values.size()-1];
552 template <typename LIMITTYPE>
553 bool RangeListConstraint<LIMITTYPE>::is_upper_limit_infinity () const
555 if (0 == values.size()) return false;
556 return LIMITTYPE::maximum == values[values.size()-1];
559 template <typename LIMITTYPE>
560 bool RangeListConstraint<LIMITTYPE>::is_lower_limit_infinity () const
562 if (0 == values.size()) return false;
563 return LIMITTYPE::minimum == values[0];
566 template <typename LIMITTYPE>
567 string RangeListConstraint<LIMITTYPE>::to_string(bool add_brackets) const
570 if (add_brackets) ret_val += '(';
571 int last = values.size()-1;
572 for (int i=0; i<=last; i++)
574 ret_val += values[i].to_string();
575 if (intervals[i]) ret_val += "..";
576 else if (i<last) ret_val += ',';
578 if (add_brackets) ret_val += ')';
582 ////////////////////////////////////////////////////////////////////////////////
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
589 ////////////////////////////////////////////////////////////////////////////////
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
598 RangeListConstraint<real_limit_t> rlc;
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
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;
610 // A union/intersection B -> C
611 RealRangeListConstraint set_operation(const RealRangeListConstraint& other, bool is_union) const;
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
617 tribool is_subset(const RealRangeListConstraint& other) const { return (*this*~other).is_empty(); }
618 RealRangeListConstraint operator-(const RealRangeListConstraint& other) const { return ( *this * ~other ); } // except
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(); }
624 string to_string() const;
625 bool is_upper_limit_infinity() const;
626 bool is_lower_limit_infinity() const;
629 ////////////////////////////////////////////////////////////////////////////////
631 class BooleanListConstraint
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 {
639 BC_ALL = 0x03 // all values, full set
641 unsigned char values;
645 BooleanListConstraint(): values(0) {} // empty set
646 BooleanListConstraint(bool b): values(b ? BC_TRUE:BC_FALSE) {} // single value set
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); }
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; }
657 tribool is_subset(const BooleanListConstraint& other) const { return (*this*~other).is_empty(); }
659 BooleanListConstraint operator-(const BooleanListConstraint& other) const { return ( *this * ~other ); }
661 string to_string() const;
664 ////////////////////////////////////////////////////////////////////////////////
666 class VerdicttypeListConstraint
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
676 VC_ALL = 0x1F // all values, full set
680 unsigned char values;
684 VerdicttypeListConstraint(): values(0) {} // empty set
685 VerdicttypeListConstraint(verdicttype_constraint_t vtc): values(vtc) {} // single value set
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; }
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; }
696 tribool is_subset(const VerdicttypeListConstraint& other) const { return (*this*~other).is_empty(); }
698 VerdicttypeListConstraint operator-(const VerdicttypeListConstraint& other) const { return ( *this * ~other ); }
700 string to_string() const;
703 ////////////////////////////////////////////////////////////////////////////////
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
718 SizeRangeListConstraint size_constraint;
719 map<string,void> has_values, not_values;
721 void copy_content(const StringSizeAndValueListConstraint& other);
722 void canonicalize(map<string,void>& values, map<string,void>& other_values, bool if_values);
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(); }
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;
740 StringSizeAndValueListConstraint set_operation(const StringSizeAndValueListConstraint& other, bool is_union) const;
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
746 tribool is_subset(const StringSizeAndValueListConstraint& other) const { return (*this*~other).is_empty(); }
747 StringSizeAndValueListConstraint operator-(const StringSizeAndValueListConstraint& other) const { return ( *this * ~other ); } // except
749 tribool get_size_limit(bool is_upper, size_limit_t& limit) const;
751 string to_string() const;
754 template<unsigned char BITCNT, unsigned short ELEMSIZE>
755 tribool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::get_size_limit(bool is_upper, size_limit_t& limit) const
757 if (size_constraint.is_empty()==TTRUE) return TFALSE;
758 limit = is_upper ? size_constraint.get_maximal() : size_constraint.get_minimal();
762 template<unsigned char BITCNT, unsigned short ELEMSIZE>
763 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::clean_up()
765 size_constraint = SizeRangeListConstraint();
770 template<unsigned char BITCNT, unsigned short ELEMSIZE>
771 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::copy_content(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other)
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);
778 template<unsigned char BITCNT, unsigned short ELEMSIZE>
779 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::StringSizeAndValueListConstraint(const string& s)
781 if (s.size() % ELEMSIZE != 0) FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
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()");
790 FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
792 has_values.add(s,NULL);
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)
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));
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));
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));
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 ) );
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) {
835 str += (c<10) ? ('0' + c) : ('A' + (c-10));
836 c = (ei >> (BITCNT/ELEMSIZE)) & 0x0F;
837 str += (c<10) ? ('0' + c) : ('A' + (c-10));
839 FATAL_ERROR("StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize()");
842 // if str is not element of values then add to other_values
843 if (!values.has_key(str)) other_values.add(str,NULL);
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));
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));
858 for (size_t i=0; i<values_lengths.size(); i++) delete (values_lengths.get_nth_elem(i));
859 values_lengths.clear();
862 template<unsigned char BITCNT, unsigned short ELEMSIZE>
863 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize()
865 canonicalize(has_values, not_values, true);
866 canonicalize(not_values, has_values, false);
869 template<unsigned char BITCNT, unsigned short ELEMSIZE>
870 tribool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::is_equal(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other) const
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;
880 template<unsigned char BITCNT, unsigned short ELEMSIZE>
881 bool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::is_element(const string& s) const
883 return ( ( size_constraint.is_element(s.size()/ELEMSIZE) && !not_values.has_key(s) ) || has_values.has_key(s) );
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
894 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> ret_val;
895 ret_val.size_constraint = size_constraint.set_operation(other.size_constraint, 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);
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);
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);
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);
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);
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);
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);
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);
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);
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);
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);
974 ret_val.canonicalize();
978 template<unsigned char BITCNT, unsigned short ELEMSIZE>
979 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::operator~() const
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();
989 template<unsigned char BITCNT, unsigned short ELEMSIZE>
990 string StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::to_string() const
993 if (has_values.size()>0) {
995 for (size_t i=0; i<has_values.size(); i++) {
996 if (i>0) ret_val += ',';
998 ret_val += has_values.get_nth_key(i);
1000 if (BITCNT==1) ret_val += 'B';
1001 else if (BITCNT==4) ret_val += 'H';
1002 else if (BITCNT==8) ret_val += 'O';
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();
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 += ',';
1018 ret_val += not_values.get_nth_key(i);
1020 if (BITCNT==1) ret_val += 'B';
1021 else if (BITCNT==4) ret_val += 'H';
1022 else if (BITCNT==8) ret_val += 'O';
1029 typedef StringSizeAndValueListConstraint<1,1> BitstringConstraint;
1030 typedef StringSizeAndValueListConstraint<4,1> HexstringConstraint;
1031 typedef StringSizeAndValueListConstraint<8,2> OctetstringConstraint; // one char is half octet
1033 ////////////////////////////////////////////////////////////////////////////////
1035 class StringPatternConstraint
1038 Ttcn::PatternString* pattern; // not owned
1041 StringPatternConstraint() : pattern(0) {} // empty set
1042 StringPatternConstraint(Ttcn::PatternString* p): pattern(p) {}
1044 tribool is_empty() const { return TUNKNOWN; }
1045 tribool is_full() const { return TUNKNOWN; }
1046 tribool is_equal(const StringPatternConstraint&) const { return TUNKNOWN; }
1048 tribool match(const string& str) const;
1049 tribool match(const ustring&) const { return TUNKNOWN; } // TODO
1051 StringPatternConstraint set_operation(const StringPatternConstraint&, bool) const { FATAL_ERROR("StringPatternConstraint::set_operation(): not implemented"); }
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"); }
1057 tribool is_subset(const StringPatternConstraint&) const { return TUNKNOWN; }
1058 StringPatternConstraint operator-(const StringPatternConstraint& other) const { return ( *this * ~other ); } // except
1060 string to_string() const;
1063 ////////////////////////////////////////////////////////////////////////////////
1065 template <class STRINGTYPE>
1066 class StringValueConstraint
1069 map<STRINGTYPE,void> values;
1071 void copy_content(const StringValueConstraint& other);
1074 StringValueConstraint() {} // empty set
1075 StringValueConstraint(const STRINGTYPE& s) { values.add(s,NULL); } // single value set
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(); }
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); }
1086 StringValueConstraint set_operation(const StringValueConstraint& other, bool is_union) const;
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
1091 tribool is_subset(const StringValueConstraint& other) const { return (*this-other).is_empty(); }
1092 StringValueConstraint operator-(const StringValueConstraint& other) const; // except
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);
1100 string to_string() const;
1103 template <class STRINGTYPE>
1104 void StringValueConstraint<STRINGTYPE>::clean_up()
1109 template <class STRINGTYPE>
1110 void StringValueConstraint<STRINGTYPE>::copy_content(const StringValueConstraint<STRINGTYPE>& other)
1112 for (size_t i=0; i<other.values.size(); i++) values.add(other.values.get_nth_key(i),NULL);
1115 template <class STRINGTYPE>
1116 tribool StringValueConstraint<STRINGTYPE>::is_equal(const StringValueConstraint<STRINGTYPE>& other) const
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;
1125 template <class STRINGTYPE>
1126 StringValueConstraint<STRINGTYPE> StringValueConstraint<STRINGTYPE>::set_operation
1127 (const StringValueConstraint<STRINGTYPE>& other, bool is_union) const
1129 StringValueConstraint<STRINGTYPE> ret_val;
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);
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);
1145 template <class STRINGTYPE>
1146 StringValueConstraint<STRINGTYPE> StringValueConstraint<STRINGTYPE>::operator-(const StringValueConstraint<STRINGTYPE>& other) const
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);
1156 template <class STRINGTYPE>
1157 void StringValueConstraint<STRINGTYPE>::remove(const SizeRangeListConstraint& size_constraint, bool if_element)
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) {
1168 template <class STRINGTYPE>
1169 template <class CHARLIMITTYPE>
1170 void StringValueConstraint<STRINGTYPE>::remove(const RangeListConstraint<CHARLIMITTYPE>& alphabet_constraint, bool if_element)
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++)
1177 if (!alphabet_constraint.is_element(CHARLIMITTYPE(str[chr_idx]))) {
1178 all_chars_are_elements = false;
1182 if (all_chars_are_elements==if_element) {
1189 template <class STRINGTYPE>
1190 void StringValueConstraint<STRINGTYPE>::remove(const StringPatternConstraint& pattern_constraint, bool if_element)
1192 for (size_t i=0; i<values.size(); i++) {
1193 STRINGTYPE str = values.get_nth_key(i);
1194 switch (pattern_constraint.match(str)) {
1196 if (!if_element) { values.erase(str); i--; }
1201 if (if_element) { values.erase(str); i--; }
1204 FATAL_ERROR("StringValueConstraint::remove(StringPatternConstraint)");
1209 template <class STRINGTYPE>
1210 string StringValueConstraint<STRINGTYPE>::to_string() const
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();
1223 ////////////////////////////////////////////////////////////////////////////////
1225 // contains a tree of subtype constraints
1226 template <class STRINGTYPE, class CHARLIMITTYPE>
1227 class StringSubtypeTreeElement
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
1238 enum constrainttype_t {
1245 elementtype_t elementtype;
1247 struct { // operation (ET_INTERSECTION, ET_UNION, ET_EXCEPT)
1248 StringSubtypeTreeElement* a; // owned
1249 StringSubtypeTreeElement* b; // owned
1251 struct { // constraint
1252 constrainttype_t constrainttype;
1253 union { // constraint objects are owned
1254 SizeRangeListConstraint* s; // size/length constraint type
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
1265 StringValueConstraint<STRINGTYPE>* v; // value set constraint
1266 StringPatternConstraint* p; // pattern constraint
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
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);
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(); }
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;
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; }
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;
1304 bool is_valid_range() const;
1305 void set_char_context(bool p_char_context);
1307 string to_string() const;
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)
1314 switch (elementtype) {
1315 case ET_INTERSECTION:
1320 FATAL_ERROR("StringSubtypeTreeElement::StringSubtypeTreeElement()");
1328 template <class STRINGTYPE, class CHARLIMITTYPE>
1329 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::
1330 get_alphabet_limit(bool is_upper, CHARLIMITTYPE& limit) const
1332 switch (elementtype) {
1336 limit = is_upper ? CHARLIMITTYPE::maximum : CHARLIMITTYPE::minimum;
1339 switch (u.cs.constrainttype) {
1341 limit = is_upper ? CHARLIMITTYPE::maximum : CHARLIMITTYPE::minimum;
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();
1352 FATAL_ERROR("StringSubtypeTreeElement::get_alphabet_limit()");
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);
1358 limit = ((lb<la) ^ !is_upper) ? lb : la;
1366 FATAL_ERROR("StringSubtypeTreeElement::get_alphabet_limit()");
1371 template <class STRINGTYPE, class CHARLIMITTYPE>
1372 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::
1373 get_size_limit(bool is_upper, size_limit_t& limit) const
1375 switch (elementtype) {
1379 limit = is_upper ? size_limit_t::maximum : size_limit_t::minimum;
1382 switch (u.cs.constrainttype) {
1384 if (u.cs.s->is_empty()==TTRUE) return TFALSE;
1385 limit = is_upper ? u.cs.s->get_maximal() : u.cs.s->get_minimal();
1388 limit = is_upper ? size_limit_t::maximum : size_limit_t::minimum;
1395 FATAL_ERROR("StringSubtypeTreeElement::get_size_limit()");
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);
1401 limit = ((lb<la) ^ !is_upper) ? lb : la;
1409 FATAL_ERROR("StringSubtypeTreeElement::get_size_limit()");
1414 template <class STRINGTYPE, class CHARLIMITTYPE>
1415 bool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_valid_range() const
1417 switch (elementtype) {
1422 switch (u.cs.constrainttype) {
1425 return (u.cs.s->is_equal(SizeRangeListConstraint(size_limit_t(1)))==TTRUE);
1432 FATAL_ERROR("StringSubtypeTreeElement::is_valid_range()");
1434 case ET_INTERSECTION:
1437 return ( u.op.a->is_valid_range() && u.op.b->is_valid_range() );
1439 FATAL_ERROR("StringSubtypeTreeElement::is_valid_range()");
1444 template <class STRINGTYPE, class CHARLIMITTYPE>
1445 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::set_char_context(bool p_char_context)
1447 switch (elementtype) {
1452 u.cs.a.char_context = p_char_context;
1453 switch (u.cs.constrainttype) {
1455 if (p_char_context) set_all(); // false -> true
1456 else FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1460 FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1463 case ET_INTERSECTION:
1466 u.op.a->set_char_context(p_char_context);
1467 u.op.b->set_char_context(p_char_context);
1470 FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1474 template <class STRINGTYPE, class CHARLIMITTYPE>
1475 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1476 (const SizeRangeListConstraint& p_s):
1477 elementtype(ET_CONSTRAINT)
1479 u.cs.constrainttype = CT_SIZE;
1480 u.cs.s = new SizeRangeListConstraint(p_s);
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)
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;
1495 template <class STRINGTYPE, class CHARLIMITTYPE>
1496 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1497 (const StringValueConstraint<STRINGTYPE>& p_v):
1498 elementtype(ET_CONSTRAINT)
1500 u.cs.constrainttype = CT_VALUES;
1501 u.cs.v = new StringValueConstraint<STRINGTYPE>(p_v);
1505 template <class STRINGTYPE, class CHARLIMITTYPE>
1506 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1507 (const StringPatternConstraint& p_p):
1508 elementtype(ET_CONSTRAINT)
1510 u.cs.constrainttype = CT_PATTERN;
1511 u.cs.p = new StringPatternConstraint(p_p);
1515 template <class STRINGTYPE, class CHARLIMITTYPE>
1516 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::clean_up()
1518 switch (elementtype) {
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()");
1531 case ET_INTERSECTION:
1538 FATAL_ERROR("StringSubtypeTreeElement::clean_up()");
1542 template <class STRINGTYPE, class CHARLIMITTYPE>
1543 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::copy_content(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>& other)
1545 elementtype = other.elementtype;
1546 switch (elementtype) {
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;
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;
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()");
1563 case ET_INTERSECTION:
1566 u.op.a = new StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>(*(other.u.op.a));
1567 u.op.b = new StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>(*(other.u.op.b));
1570 FATAL_ERROR("StringSubtypeTreeElement::copy_content()");
1574 template <class STRINGTYPE, class CHARLIMITTYPE>
1575 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::set_to_operand(bool operand_a)
1577 switch (elementtype) {
1578 case ET_INTERSECTION:
1583 FATAL_ERROR("StringSubtypeTreeElement::copy_operand()");
1585 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* op;
1593 // steal the content of op into myself
1594 elementtype = op->elementtype;
1595 switch (elementtype) {
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;
1604 u.cs.a.c = op->u.cs.a.c;
1605 u.cs.a.char_context = op->u.cs.a.char_context;
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()");
1612 case ET_INTERSECTION:
1615 u.op.a = op->u.op.a;
1616 u.op.b = op->u.op.b;
1619 FATAL_ERROR("StringSubtypeTreeElement::copy_operand()");
1621 // delete the empty op
1622 op->elementtype = ET_NONE;
1626 template <class STRINGTYPE, class CHARLIMITTYPE>
1627 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::simplify()
1629 switch (elementtype) {
1634 switch (u.cs.constrainttype) {
1636 if (u.cs.s->is_empty()==TTRUE) { set_none(); return; }
1637 if (u.cs.s->is_full()==TTRUE) { set_all(); return; }
1640 if (u.cs.a.c->is_empty()==TTRUE) { set_none(); return; }
1641 if (u.cs.a.c->is_full()==TTRUE) { set_all(); return; }
1644 if (u.cs.v->is_empty()==TTRUE) { set_none(); return; }
1645 if (u.cs.v->is_full()==TTRUE) { set_all(); return; }
1648 if (u.cs.p->is_empty()==TTRUE) { set_none(); return; }
1649 if (u.cs.p->is_full()==TTRUE) { set_all(); return; }
1651 default: FATAL_ERROR("StringSubtypeTreeElement::simplify()");
1654 case ET_INTERSECTION:
1659 FATAL_ERROR("StringSubtypeTreeElement::simplify()");
1663 template <class STRINGTYPE, class CHARLIMITTYPE>
1664 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_empty() const
1666 switch (elementtype) {
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()");
1679 case ET_INTERSECTION:
1680 return ( u.op.a->is_empty() || u.op.b->is_empty() );
1682 return ( u.op.a->is_empty() && u.op.b->is_empty() );
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 ) );
1689 FATAL_ERROR("StringSubtypeTreeElement::is_empty()");
1694 template <class STRINGTYPE, class CHARLIMITTYPE>
1695 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_full() const
1697 switch (elementtype) {
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()");
1710 case ET_INTERSECTION:
1711 return ( u.op.a->is_full() && u.op.b->is_full() );
1713 return ( u.op.a->is_full() || u.op.b->is_full() );
1715 return ( u.op.a->is_full() && u.op.b->is_empty() );
1717 FATAL_ERROR("StringSubtypeTreeElement::is_full()");
1722 template <class STRINGTYPE, class CHARLIMITTYPE>
1723 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_equal(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* other) const
1725 if (elementtype!=other->elementtype) return TUNKNOWN;
1726 switch (elementtype) {
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()");
1739 case ET_INTERSECTION:
1744 FATAL_ERROR("StringSubtypeTreeElement::is_equal()");
1749 template <class STRINGTYPE, class CHARLIMITTYPE>
1750 bool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_element(const STRINGTYPE& s) const
1752 switch (elementtype) {
1758 switch (u.cs.constrainttype) {
1759 case CT_SIZE: return u.cs.s->is_element(size_limit_t(s.size()));
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;
1767 case CT_VALUES: return u.cs.v->is_element(s);
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()");
1776 default: FATAL_ERROR("StringSubtypeTreeElement::is_element()");
1778 case ET_INTERSECTION:
1779 return ( u.op.a->is_element(s) && u.op.b->is_element(s) );
1781 return ( u.op.a->is_element(s) || u.op.b->is_element(s) );
1783 return ( u.op.a->is_element(s) && !u.op.b->is_element(s) );
1785 FATAL_ERROR("StringSubtypeTreeElement::is_element()");
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
1797 switch (elementtype) {
1801 if (other->elementtype==ET_ALL) return TTRUE;
1802 else return TUNKNOWN;
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()");
1813 case ET_INTERSECTION:
1818 FATAL_ERROR("StringSubtypeTreeElement::is_subset()");
1823 template <class STRINGTYPE, class CHARLIMITTYPE>
1824 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::evaluate()
1826 switch (elementtype) {
1830 // these are the simplest forms, others are reduced to these in ideal case
1832 case ET_INTERSECTION:
1837 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
1840 // recursive evaluation
1844 // special case where the construct looks like this:
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
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);
1862 if ( (u.op.b->elementtype==ET_NONE) && (elementtype==ET_EXCEPT) ) {
1863 set_to_operand(true);
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);
1872 if (elementtype==ET_UNION) { set_all(); return; }
1874 if ( (u.op.b->elementtype==ET_ALL) && (elementtype==ET_EXCEPT) ) { set_none(); return; }
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;
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) {
1884 SizeRangeListConstraint* rvs = new SizeRangeListConstraint(~*(u.op.b->u.cs.s));
1886 elementtype = ET_CONSTRAINT;
1887 u.cs.constrainttype = CT_SIZE;
1892 if (u.cs.a.char_context) {
1893 RangeListConstraint<CHARLIMITTYPE>* rva = new RangeListConstraint<CHARLIMITTYPE>(~*(u.op.b->u.cs.a.c));
1895 elementtype = ET_CONSTRAINT;
1896 u.cs.constrainttype = CT_ALPHABET;
1898 u.cs.a.char_context = true;
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
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) {
1923 svc->remove(*(first_is_svc ? u.op.b->u.cs.s : u.op.a->u.cs.s), false);
1926 svc->remove(*(first_is_svc ? u.op.b->u.cs.a.c : u.op.a->u.cs.a.c), false);
1929 svc->remove(*(first_is_svc ? u.op.b->u.cs.p : u.op.a->u.cs.p), false);
1934 // drop the other operand, keep the values as constraint of this object
1935 StringValueConstraint<STRINGTYPE>* keep_svc = new StringValueConstraint<STRINGTYPE>(*svc);
1937 elementtype = ET_CONSTRAINT;
1938 u.cs.constrainttype = CT_VALUES;
1944 switch (first_is_svc ? u.op.b->u.cs.constrainttype : u.op.a->u.cs.constrainttype) {
1946 svc->remove(*(first_is_svc ? u.op.b->u.cs.s : u.op.a->u.cs.s), true);
1949 svc->remove(*(first_is_svc ? u.op.b->u.cs.a.c : u.op.a->u.cs.a.c), true);
1952 svc->remove(*(first_is_svc ? u.op.b->u.cs.p : u.op.a->u.cs.p), true);
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);
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) {
1967 svc->remove(*(u.op.b->u.cs.s), true);
1970 svc->remove(*(u.op.b->u.cs.a.c), true);
1973 svc->remove(*(u.op.b->u.cs.p), true);
1978 // drop the other operand, keep the values as constraint of this object
1979 StringValueConstraint<STRINGTYPE>* keep_svc = new StringValueConstraint<STRINGTYPE>(*svc);
1981 elementtype = ET_CONSTRAINT;
1982 u.cs.constrainttype = CT_VALUES;
1989 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
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) {
2002 if (elementtype==ET_EXCEPT) set_none();
2009 if (u.op.a->u.cs.constrainttype==u.op.b->u.cs.constrainttype) {
2010 switch (u.op.a->u.cs.constrainttype) {
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);
2018 *rvs = *(u.op.a->u.cs.s) + *(u.op.b->u.cs.s);
2021 *rvs = *(u.op.a->u.cs.s) - *(u.op.b->u.cs.s);
2024 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2027 elementtype = ET_CONSTRAINT;
2028 u.cs.constrainttype = CT_SIZE;
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);
2041 *rva = *(u.op.a->u.cs.a.c) + *(u.op.b->u.cs.a.c);
2044 *rva = *(u.op.a->u.cs.a.c) - *(u.op.b->u.cs.a.c);
2047 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2050 elementtype = ET_CONSTRAINT;
2051 u.cs.constrainttype = CT_ALPHABET;
2053 u.cs.a.char_context = char_ctx;
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);
2063 *rvv = *(u.op.a->u.cs.v) + *(u.op.b->u.cs.v);
2066 *rvv = *(u.op.a->u.cs.v) - *(u.op.b->u.cs.v);
2069 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2072 elementtype = ET_CONSTRAINT;
2073 u.cs.constrainttype = CT_VALUES;
2079 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2084 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2090 template <class STRINGTYPE, class CHARLIMITTYPE>
2091 string StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::to_string() const
2094 bool print_operation = false;
2096 switch (elementtype) {
2103 switch (u.cs.constrainttype) {
2105 ret_val += "length";
2106 ret_val += u.cs.s->to_string();
2109 ret_val += u.cs.a.char_context ? "range" : "from";
2110 ret_val += u.cs.a.c->to_string();
2113 ret_val += u.cs.v->to_string();
2116 ret_val += u.cs.p->to_string();
2119 FATAL_ERROR("StringSubtypeTreeElement::to_string()");
2122 case ET_INTERSECTION:
2123 op_str = "intersection";
2124 print_operation = true;
2128 print_operation = true;
2132 print_operation = true;
2135 FATAL_ERROR("StringSubtypeTreeElement::to_string()");
2137 if (print_operation) {
2139 ret_val += u.op.a->to_string();
2143 ret_val += u.op.b->to_string();
2149 typedef StringSubtypeTreeElement<string,char_limit_t> CharstringSubtypeTreeElement;
2150 typedef StringSubtypeTreeElement<ustring,universal_char_limit_t> UniversalCharstringSubtypeTreeElement;
2152 ////////////////////////////////////////////////////////////////////////////////
2153 // constraint classes for structured types
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()
2161 vector<Value> values; // values are not owned
2163 void copy_content(const ValueList& other);
2165 ValueList() : values() {} // empty set
2166 ValueList(Value* v) : values() { values.add(v); }
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(); }
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;
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);
2181 ValueList set_operation(const ValueList& other, bool is_union) const;
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
2187 tribool is_subset(const ValueList& other) const { return (*this-other).is_empty(); }
2189 string to_string() const;
2192 // can be a ValueList or (ALL-ValueList), used for subtypes of structured types, enumerated and objid
2193 class ValueListConstraint
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
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;
2208 ValueListConstraint operator+(const ValueListConstraint& other) const; // union
2209 ValueListConstraint operator*(const ValueListConstraint& other) const; // intersection
2210 ValueListConstraint operator~() const; // complement
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
2217 string to_string() const;
2220 // length and value list constraints for record/set of types
2221 class RecofConstraint
2224 SizeRangeListConstraint size_constraint;
2225 ValueList has_values, not_values;
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() {}
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;
2241 RecofConstraint set_operation(const RecofConstraint& other, bool is_union) const;
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
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
2250 tribool get_size_limit(bool is_upper, size_limit_t& limit) const;
2252 string to_string() const;
2256 }// namespace Common
2258 #endif // #ifndef _Subtypestuff_HH