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 bool is_upper_limit_infinity() const;
264 bool is_lower_limit_infinity() const;
266 string to_string(bool add_brackets=true) const;
268 /** conversion from integer range to size range,
269 returns true on success, false if the integers do not fit into the size values,
270 when returning false the size_range will be set to the full set */
271 friend bool convert_int_to_size(const RangeListConstraint<int_limit_t>& int_range, RangeListConstraint<size_limit_t>& size_range);
274 template <typename LIMITTYPE>
275 RangeListConstraint<LIMITTYPE>::RangeListConstraint(const LIMITTYPE& l)
276 : values(), intervals()
278 l.check_single_value();
280 intervals.add(false);
283 template <typename LIMITTYPE>
284 RangeListConstraint<LIMITTYPE>::RangeListConstraint(const LIMITTYPE& l_begin, const LIMITTYPE& l_end)
285 : values(), intervals()
287 if (l_end<l_begin) FATAL_ERROR("RangeListConstraint::RangeListConstraint(): invalid range");
288 if (l_begin==l_end) {
289 l_begin.check_single_value();
291 intervals.add(false);
293 l_begin.check_interval_start();
294 l_end.check_interval_end();
298 intervals.add(false);
302 template <typename LIMITTYPE>
303 tribool RangeListConstraint<LIMITTYPE>::is_empty() const
305 return TRIBOOL(values.size()==0);
308 template <typename LIMITTYPE>
309 tribool RangeListConstraint<LIMITTYPE>::is_full() const
311 return TRIBOOL( (values.size()==2) && (values[0]==LIMITTYPE::minimum) && (values[1]==LIMITTYPE::maximum) && (intervals[0]) );
314 template <typename LIMITTYPE>
315 tribool RangeListConstraint<LIMITTYPE>::is_equal(const RangeListConstraint<LIMITTYPE>& other) const
317 return TRIBOOL( (values==other.values) && (intervals==other.intervals) );
320 template <typename LIMITTYPE>
321 bool RangeListConstraint<LIMITTYPE>::is_element(const LIMITTYPE& l) const
323 if (values.size()==0) return false;
324 // binary search in values[]
325 size_t lower_idx = 0;
326 size_t upper_idx = values.size()-1;
327 while (upper_idx>lower_idx+1) {
328 size_t middle_idx = lower_idx + (upper_idx-lower_idx) / 2;
329 if (values[middle_idx]<l) lower_idx = middle_idx;
330 else upper_idx = middle_idx;
332 if (lower_idx==upper_idx) {
333 if (values[lower_idx]==l) return true; // every value is in the set
334 else if (values[lower_idx]<l) return intervals[lower_idx];
335 else return ( (lower_idx>0) ? intervals[lower_idx-1] : false );
337 if (l<values[lower_idx]) return ( (lower_idx>0) ? intervals[lower_idx-1] : false );
338 else if (l==values[lower_idx]) return true;
339 else if (l<values[upper_idx]) return intervals[upper_idx-1];
340 else if (l==values[upper_idx]) return true;
341 else return intervals[upper_idx];
345 template <typename LIMITTYPE>
346 RangeListConstraint<LIMITTYPE> RangeListConstraint<LIMITTYPE>::operator~() const
348 if (values.size()==0) { // if we have an empty set
349 return RangeListConstraint<LIMITTYPE>(LIMITTYPE::minimum, LIMITTYPE::maximum);
351 RangeListConstraint<LIMITTYPE> ret_val;
353 if (!(values[0]==LIMITTYPE::minimum)) {
354 if (LIMITTYPE::minimum.is_adjacent(values[0])) {
355 ret_val.values.add(LIMITTYPE::minimum);
356 ret_val.intervals.add(false);
358 ret_val.values.add(LIMITTYPE::minimum);
359 ret_val.intervals.add(true);
360 ret_val.values.add(values[0].previous());
361 ret_val.intervals.add(false);
364 int last = values.size()-1;
365 for (int i=0; i<last; i++)
368 if (values[i].next()==values[i+1].previous()) {
369 // add one value between intervals
370 ret_val.values.add(values[i].next());
371 ret_val.intervals.add(false);
373 // add interval between intervals
374 ret_val.values.add(values[i].next());
375 ret_val.intervals.add(true);
376 ret_val.values.add(values[i+1].previous());
377 ret_val.intervals.add(false);
381 if (!(values[last]==LIMITTYPE::maximum)) {
382 if (values[last].is_adjacent(LIMITTYPE::maximum)) {
383 ret_val.values.add(LIMITTYPE::maximum);
384 ret_val.intervals.add(false);
386 ret_val.values.add(values[last].next());
387 ret_val.intervals.add(true);
388 ret_val.values.add(LIMITTYPE::maximum);
389 ret_val.intervals.add(false);
395 template <typename LIMITTYPE>
396 RangeListConstraint<LIMITTYPE> RangeListConstraint<LIMITTYPE>::set_operation(const RangeListConstraint<LIMITTYPE>& other, bool is_union) const
398 // special case: one or both are empty sets
399 if (values.size()==0) return is_union ? other : *this;
400 if (other.values.size()==0) return is_union ? *this : other;
402 // calculate the sweep points
403 dynamic_array<sweep_point_t> sweep_points;
404 sweep_point_t spi(0,0);
405 while ( (spi.a_idx<(int)values.size()) || (spi.b_idx<(int)other.values.size()) )
407 if (spi.a_idx>=(int)values.size()) {
408 sweep_points.add(sweep_point_t(-1,spi.b_idx));
410 } else if (spi.b_idx>=(int)other.values.size()) {
411 sweep_points.add(sweep_point_t(spi.a_idx, -1));
413 } else { // both are within the vector, get smaller or get both if equal
414 if (values[spi.a_idx]<other.values[spi.b_idx]) {
415 sweep_points.add(sweep_point_t(spi.a_idx, -1));
417 } else if (values[spi.a_idx]==other.values[spi.b_idx]) {
418 sweep_points.add(spi);
422 sweep_points.add(sweep_point_t(-1,spi.b_idx));
428 // sweep (iterate) through both vectors
429 bool in_a = false; // we are already in an interval of A
431 for (int i=0; i<(int)sweep_points.size(); i++)
433 // set bools for A interval
434 bool a_interval = in_a;
435 bool a_point = false;
436 if (sweep_points[i].a_idx!=-1) { // we are at a value in A
438 if (intervals[sweep_points[i].a_idx]) { // this is a starting point of an interval in A
440 if (in_a) FATAL_ERROR("RangeListConstraint::set_operation(): invalid double interval");
442 } else { // this point ends an interval of A
447 // set bools for B interval
448 bool b_interval = in_b;
449 bool b_point = false;
450 if (sweep_points[i].b_idx!=-1) { // we are at a value in B
452 if (other.intervals[sweep_points[i].b_idx]) { // this is a starting point of an interval in B
454 if (in_b) FATAL_ERROR("RangeListConstraint::set_operation(): invalid double interval");
456 } else { // this point ends an interval of B
461 // set the booleans of the union and intersection sets
462 sweep_points[i].union_interval = a_interval || b_interval;
463 sweep_points[i].intersection_point = (a_point || in_a) && (b_point || in_b);
464 sweep_points[i].intersection_interval = a_interval && b_interval;
467 // canonicalization of ret_val
469 // connect adjacent limit points with interval: [i,i+1] becomes interval
470 for (int i=1; i<(int)sweep_points.size(); i++)
472 LIMITTYPE first, second;
473 if (sweep_points[i-1].a_idx!=-1) {
474 first = values[sweep_points[i-1].a_idx];
476 if (sweep_points[i-1].b_idx!=-1) first = other.values[sweep_points[i-1].b_idx];
477 else FATAL_ERROR("RangeListConstraint::set_operation()");
479 if (sweep_points[i].a_idx!=-1) {
480 second = values[sweep_points[i].a_idx];
482 if (sweep_points[i].b_idx!=-1) second = other.values[sweep_points[i].b_idx];
483 else FATAL_ERROR("RangeListConstraint::set_operation()");
485 if (first.is_adjacent(second)) {
486 sweep_points[i-1].union_interval = true;
487 sweep_points[i-1].intersection_interval = sweep_points[i-1].intersection_point && sweep_points[i].intersection_point;
491 // two adjacent intervals shall be united into one
492 RangeListConstraint<LIMITTYPE> ret_val;
493 for (int i=0; i<(int)sweep_points.size(); i++)
496 if ( (i>0) && sweep_points[i-1].union_interval && sweep_points[i].union_interval) {
497 // drop this point, it's in a double interval
500 if (sweep_points[i].a_idx!=-1) {
501 l = values[sweep_points[i].a_idx];
503 if (sweep_points[i].b_idx!=-1) l = other.values[sweep_points[i].b_idx];
504 else FATAL_ERROR("RangeListConstraint::set_operation()");
506 ret_val.values.add(l);
507 ret_val.intervals.add(sweep_points[i].union_interval);
510 if (sweep_points[i].intersection_point) {
511 if ( (i>0) && sweep_points[i-1].intersection_interval && sweep_points[i].intersection_interval) {
512 // drop this point, it's in a double interval
515 if (sweep_points[i].a_idx!=-1) {
516 l = values[sweep_points[i].a_idx];
518 if (sweep_points[i].b_idx!=-1) l = other.values[sweep_points[i].b_idx];
519 else FATAL_ERROR("RangeListConstraint::set_operation()");
521 ret_val.values.add(l);
522 ret_val.intervals.add(sweep_points[i].intersection_interval);
530 template <typename LIMITTYPE>
531 LIMITTYPE RangeListConstraint<LIMITTYPE>::get_minimal() const
533 if (values.size()<1) return LIMITTYPE();
537 template <typename LIMITTYPE>
538 LIMITTYPE RangeListConstraint<LIMITTYPE>::get_maximal() const
540 if (values.size()<1) return LIMITTYPE();
541 return values[values.size()-1];
544 template <typename LIMITTYPE>
545 bool RangeListConstraint<LIMITTYPE>::is_upper_limit_infinity () const
547 if (0 == values.size()) return false;
548 return LIMITTYPE::maximum == values[values.size()-1];
551 template <typename LIMITTYPE>
552 bool RangeListConstraint<LIMITTYPE>::is_lower_limit_infinity () const
554 if (0 == values.size()) return false;
555 return LIMITTYPE::minimum == values[0];
558 template <typename LIMITTYPE>
559 string RangeListConstraint<LIMITTYPE>::to_string(bool add_brackets) const
562 if (add_brackets) ret_val += '(';
563 int last = values.size()-1;
564 for (int i=0; i<=last; i++)
566 ret_val += values[i].to_string();
567 if (intervals[i]) ret_val += "..";
568 else if (i<last) ret_val += ',';
570 if (add_brackets) ret_val += ')';
574 ////////////////////////////////////////////////////////////////////////////////
576 typedef RangeListConstraint<int_limit_t> IntegerRangeListConstraint; // for integer type
577 typedef RangeListConstraint<size_limit_t> SizeRangeListConstraint; // for length constraints
578 typedef RangeListConstraint<char_limit_t> CharRangeListConstraint; // for char/bit/hex/octet strings
579 typedef RangeListConstraint<universal_char_limit_t> UniversalCharRangeListConstraint; // for universal charstring
581 ////////////////////////////////////////////////////////////////////////////////
583 // RangeListConstraint with added NaN value (NaN is unordered so it cannot be a limit value)
584 // this is canonical only if two different Real values are never considered to be adjacent
585 // which means that in theory for two different Real values there are always infinite number of Real values that are between them
586 class RealRangeListConstraint
590 RangeListConstraint<real_limit_t> rlc;
593 RealRangeListConstraint(bool p_has_nan = false): has_nan(p_has_nan), rlc() {} // empty set or NaN
594 RealRangeListConstraint(const real_limit_t& rl): has_nan(false), rlc(rl) {} // single value set (cannot be lower or upper, must be exact value)
595 RealRangeListConstraint(const real_limit_t& rl_begin, const real_limit_t& rl_end): has_nan(false), rlc(rl_begin,rl_end) {} // range set
597 tribool is_empty() const { return ( rlc.is_empty() && TRIBOOL(!has_nan) ); }
598 tribool is_full() const { return ( rlc.is_full() && TRIBOOL(has_nan) ); }
599 tribool is_equal(const RealRangeListConstraint& other) const { return ( rlc.is_equal(other.rlc) && TRIBOOL(has_nan==other.has_nan) ); }
600 bool is_element(const ttcn3float& r) const;
602 // A union/intersection B -> C
603 RealRangeListConstraint set_operation(const RealRangeListConstraint& other, bool is_union) const;
605 RealRangeListConstraint operator+(const RealRangeListConstraint& other) const { return set_operation(other, true); } // union
606 RealRangeListConstraint operator*(const RealRangeListConstraint& other) const { return set_operation(other, false); } // intersection
607 RealRangeListConstraint operator~() const; // complement
609 tribool is_subset(const RealRangeListConstraint& other) const { return (*this*~other).is_empty(); }
610 RealRangeListConstraint operator-(const RealRangeListConstraint& other) const { return ( *this * ~other ); } // except
612 tribool is_range_empty() const { return rlc.is_empty(); }
613 real_limit_t get_minimal() const { return rlc.get_minimal(); }
614 real_limit_t get_maximal() const { return rlc.get_maximal(); }
616 string to_string() const;
617 bool is_upper_limit_infinity() const;
618 bool is_lower_limit_infinity() const;
621 ////////////////////////////////////////////////////////////////////////////////
623 class BooleanListConstraint
626 // every value selects a different bit, if the bit is set to 1 then the associated value is element of the set
627 enum boolean_constraint_t {
631 BC_ALL = 0x03 // all values, full set
633 unsigned char values;
637 BooleanListConstraint(): values(0) {} // empty set
638 BooleanListConstraint(bool b): values(b ? BC_TRUE:BC_FALSE) {} // single value set
640 tribool is_empty() const { return TRIBOOL(values==0); }
641 tribool is_full() const { return TRIBOOL(values==BC_ALL); }
642 tribool is_equal(const BooleanListConstraint& other) const { return TRIBOOL(values==other.values); }
643 bool is_element(bool b) const { return b ? (values&BC_TRUE) : (values&BC_FALSE); }
645 BooleanListConstraint operator+(const BooleanListConstraint& other) const { BooleanListConstraint rv; rv.values = values | other.values; return rv; }
646 BooleanListConstraint operator*(const BooleanListConstraint& other) const { BooleanListConstraint rv; rv.values = values & other.values; return rv; }
647 BooleanListConstraint operator~() const { BooleanListConstraint rv; rv.values = values ^ BC_ALL; return rv; }
649 tribool is_subset(const BooleanListConstraint& other) const { return (*this*~other).is_empty(); }
651 BooleanListConstraint operator-(const BooleanListConstraint& other) const { return ( *this * ~other ); }
653 string to_string() const;
656 ////////////////////////////////////////////////////////////////////////////////
658 class VerdicttypeListConstraint
661 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
668 VC_ALL = 0x1F // all values, full set
672 unsigned char values;
676 VerdicttypeListConstraint(): values(0) {} // empty set
677 VerdicttypeListConstraint(verdicttype_constraint_t vtc): values(vtc) {} // single value set
679 tribool is_empty() const { return TRIBOOL(values==0); }
680 tribool is_full() const { return TRIBOOL(values==VC_ALL); }
681 tribool is_equal(const VerdicttypeListConstraint& other) const { return TRIBOOL(values==other.values); }
682 bool is_element(verdicttype_constraint_t vtc) const { return vtc&values; }
684 VerdicttypeListConstraint operator+(const VerdicttypeListConstraint& other) const { VerdicttypeListConstraint rv; rv.values = values | other.values; return rv; }
685 VerdicttypeListConstraint operator*(const VerdicttypeListConstraint& other) const { VerdicttypeListConstraint rv; rv.values = values & other.values; return rv; }
686 VerdicttypeListConstraint operator~() const { VerdicttypeListConstraint rv; rv.values = values ^ VC_ALL; return rv; }
688 tribool is_subset(const VerdicttypeListConstraint& other) const { return (*this*~other).is_empty(); }
690 VerdicttypeListConstraint operator-(const VerdicttypeListConstraint& other) const { return ( *this * ~other ); }
692 string to_string() const;
695 ////////////////////////////////////////////////////////////////////////////////
697 // size and value list constraint for bitstring, hexstring and octetstring
698 // in the compiler octetstring is a special hexstring where 1 octet = 2 hex.chars
699 // not_values is needed because the operation complement/except
700 // not_values must always be inside size_constraint set, has_values must be outside of size_constraint set
701 // canonical form can be obtained by simplifying value list constraints into size constraints
702 // and by converting not_values information into the other two sets if number of not values is >= [number of all values for L] / 2
703 // for length(L) there must be exactly N^L number of values that have length=L, where an element can have N different values
704 // where N = 2^BITCNT, BITCNT is the number of bits needed to store one element, works for BITCNT=1,4,8
705 // for octetstrings one octet element is 2 chars long, for others one element is one char, real size of string = elem.size()/ELEMSIZE
706 template<unsigned char BITCNT, unsigned short ELEMSIZE>
707 class StringSizeAndValueListConstraint
710 SizeRangeListConstraint size_constraint;
711 map<string,void> has_values, not_values;
713 void copy_content(const StringSizeAndValueListConstraint& other);
714 void canonicalize(map<string,void>& values, map<string,void>& other_values, bool if_values);
718 StringSizeAndValueListConstraint() {} // empty set
719 StringSizeAndValueListConstraint(const string& s); // single value set
720 StringSizeAndValueListConstraint(const size_limit_t& sl): size_constraint(sl) {} // single size value set
721 StringSizeAndValueListConstraint(const size_limit_t& rl_begin, const size_limit_t& rl_end): size_constraint(rl_begin,rl_end) {} // size range set
722 StringSizeAndValueListConstraint(const SizeRangeListConstraint& p_size_constraint): size_constraint(p_size_constraint) {}
723 StringSizeAndValueListConstraint(const StringSizeAndValueListConstraint& other) { copy_content(other); }
724 StringSizeAndValueListConstraint& operator=(const StringSizeAndValueListConstraint& other) { clean_up(); copy_content(other); return *this; }
725 ~StringSizeAndValueListConstraint() { clean_up(); }
727 tribool is_empty() const { return ( size_constraint.is_empty() && TRIBOOL(has_values.size()==0) ); }
728 tribool is_full() const { return ( size_constraint.is_full() && TRIBOOL(not_values.size()==0) ); }
729 tribool is_equal(const StringSizeAndValueListConstraint& other) const;
730 bool is_element(const string& s) const;
732 StringSizeAndValueListConstraint set_operation(const StringSizeAndValueListConstraint& other, bool is_union) const;
734 StringSizeAndValueListConstraint operator+(const StringSizeAndValueListConstraint& other) const { return set_operation(other, true); } // union
735 StringSizeAndValueListConstraint operator*(const StringSizeAndValueListConstraint& other) const { return set_operation(other, false); } // intersection
736 StringSizeAndValueListConstraint operator~() const; // complement
738 tribool is_subset(const StringSizeAndValueListConstraint& other) const { return (*this*~other).is_empty(); }
739 StringSizeAndValueListConstraint operator-(const StringSizeAndValueListConstraint& other) const { return ( *this * ~other ); } // except
741 tribool get_size_limit(bool is_upper, size_limit_t& limit) const;
743 string to_string() const;
746 template<unsigned char BITCNT, unsigned short ELEMSIZE>
747 tribool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::get_size_limit(bool is_upper, size_limit_t& limit) const
749 if (size_constraint.is_empty()==TTRUE) return TFALSE;
750 limit = is_upper ? size_constraint.get_maximal() : size_constraint.get_minimal();
754 template<unsigned char BITCNT, unsigned short ELEMSIZE>
755 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::clean_up()
757 size_constraint = SizeRangeListConstraint();
762 template<unsigned char BITCNT, unsigned short ELEMSIZE>
763 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::copy_content(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other)
765 size_constraint = other.size_constraint;
766 for (size_t i=0; i<other.has_values.size(); i++) has_values.add(other.has_values.get_nth_key(i),NULL);
767 for (size_t i=0; i<other.not_values.size(); i++) not_values.add(other.not_values.get_nth_key(i),NULL);
770 template<unsigned char BITCNT, unsigned short ELEMSIZE>
771 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::StringSizeAndValueListConstraint(const string& s)
773 if (s.size() % ELEMSIZE != 0) FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
775 for (size_t i=0; i<s.size(); i++)
776 if ( (s[i]!='0') && (s[i]!='1') ) FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
777 } else if ( (BITCNT==4) || (BITCNT==8) ) {
778 for (size_t i=0; i<s.size(); i++)
779 if ( !((s[i]>='0')&&(s[i]<='9')) && !((s[i]>='A')&&(s[i]<='F')) )
780 FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
782 FATAL_ERROR("StringSizeAndValueListConstraint::StringSizeAndValueListConstraint()");
784 has_values.add(s,NULL);
787 template<unsigned char BITCNT, unsigned short ELEMSIZE>
788 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize(map<string,void>& values, map<string,void>& other_values, bool if_values)
790 map<size_t,size_t> values_lengths; // length -> number of values
791 for (size_t i=0; i<values.size(); i++) {
792 size_t value_size = values.get_nth_key(i).size()/ELEMSIZE;
793 if (values_lengths.has_key(value_size)) (*values_lengths[value_size])++;
794 else values_lengths.add(value_size,new size_t(1));
797 for (size_t i=0; i<values_lengths.size(); i++) {
798 // calculate the number of all possible values
799 size_t size = values_lengths.get_nth_key(i); // length of string
800 size_t count = *(values_lengths.get_nth_elem(i)); // number of strings with this length
801 size_t all_values_count = ~((size_t)0); // fake infinity
802 if (BITCNT*size<sizeof(size_t)*8) all_values_count = ( ((size_t)1) << (BITCNT*size) );
803 if (count==all_values_count) {
804 // delete all values which have this size
805 for (size_t hv_idx=0; hv_idx<values.size(); hv_idx++) {
806 if ((values.get_nth_key(hv_idx).size()/ELEMSIZE)==size) {
807 values.erase(values.get_nth_key(hv_idx));
811 // add/remove a single value size constraint with this size
812 if (if_values) size_constraint = size_constraint + SizeRangeListConstraint(size_limit_t(size));
813 else size_constraint = size_constraint - SizeRangeListConstraint(size_limit_t(size));
815 if ( (!if_values && (count>=all_values_count/2)) || (if_values && (count>all_values_count/2)) ) {
816 // add to other_values the complement of these values on the set with this size
817 for (size_t act_value=0; act_value<all_values_count; act_value++) {
818 string str; // for each value of act_value there is corresponding string value str
819 for (size_t elem_idx=0; elem_idx<size; elem_idx++) { // for every element
820 size_t ei = ( ( act_value >> (elem_idx*BITCNT) ) & ( (1<<BITCNT) - 1 ) );
822 str += '0' + (char)ei;
823 } else if (BITCNT==4) {
824 str += (ei<10) ? ('0' + (char)ei) : ('A' + ((char)ei-10));
825 } else if (BITCNT==8) {
827 str += (c<10) ? ('0' + c) : ('A' + (c-10));
828 c = (ei >> (BITCNT/ELEMSIZE)) & 0x0F;
829 str += (c<10) ? ('0' + c) : ('A' + (c-10));
831 FATAL_ERROR("StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize()");
834 // if str is not element of values then add to other_values
835 if (!values.has_key(str)) other_values.add(str,NULL);
837 // delete all values which have this size
838 for (size_t hv_idx=0; hv_idx<values.size(); hv_idx++) {
839 if ((values.get_nth_key(hv_idx).size()/ELEMSIZE)==size) {
840 values.erase(values.get_nth_key(hv_idx));
844 // add/remove a single value size constraint with this size
845 if (if_values) size_constraint = size_constraint + SizeRangeListConstraint(size_limit_t(size));
846 else size_constraint = size_constraint - SizeRangeListConstraint(size_limit_t(size));
850 for (size_t i=0; i<values_lengths.size(); i++) delete (values_lengths.get_nth_elem(i));
851 values_lengths.clear();
854 template<unsigned char BITCNT, unsigned short ELEMSIZE>
855 void StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::canonicalize()
857 canonicalize(has_values, not_values, true);
858 canonicalize(not_values, has_values, false);
861 template<unsigned char BITCNT, unsigned short ELEMSIZE>
862 tribool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::is_equal(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other) const
864 if (size_constraint.is_equal(other.size_constraint)==TFALSE) return TFALSE;
865 if (has_values.size()!=other.has_values.size()) return TFALSE;
866 if (not_values.size()!=other.not_values.size()) return TFALSE;
867 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;
868 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;
872 template<unsigned char BITCNT, unsigned short ELEMSIZE>
873 bool StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::is_element(const string& s) const
875 return ( ( size_constraint.is_element(s.size()/ELEMSIZE) && !not_values.has_key(s) ) || has_values.has_key(s) );
878 // representation of two sets: [Si+Vi-Ni] where Si=size_constraint, Vi=has_values, Ni=not_values
879 // UNION: [S1+V1-N1] + [S2+V2-N2] = ... = [(S1+S2)+(V1+V2)-((~S1*N2)+(N1*~S2)+(N1*N2))]
880 // INTERSECTION: [S1+V1-N1] * [S2+V2-N2] = ... = [(S1*S2)+((S1*V2-N1)+(S2*V1-N2)+(V1*V2))-(N1+N2)]
881 template<unsigned char BITCNT, unsigned short ELEMSIZE>
882 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>
883 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::
884 set_operation(const StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>& other, bool is_union) const
886 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> ret_val;
887 ret_val.size_constraint = size_constraint.set_operation(other.size_constraint, is_union);
889 // V1+V2 (union of has_values)
890 for (size_t i=0; i<has_values.size(); i++) ret_val.has_values.add(has_values.get_nth_key(i),NULL);
891 for (size_t i=0; i<other.has_values.size(); i++) {
892 const string& str = other.has_values.get_nth_key(i);
893 if (!ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL);
895 // N1*N2 (intersection of not_values)
896 for (size_t i=0; i<not_values.size(); i++) {
897 const string& str = not_values.get_nth_key(i);
898 if (other.not_values.has_key(str)) ret_val.not_values.add(str,NULL);
901 for (size_t i=0; i<other.not_values.size(); i++) {
902 const string& str = other.not_values.get_nth_key(i);
903 if (!size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) &&
904 !ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL);
907 for (size_t i=0; i<not_values.size(); i++) {
908 const string& str = not_values.get_nth_key(i);
909 if (!other.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) &&
910 !ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL);
912 } else { // intersection
913 // V1*V2 (intersection of has_values)
914 for (size_t i=0; i<has_values.size(); i++) {
915 const string& str = has_values.get_nth_key(i);
916 if (other.has_values.has_key(str)) ret_val.has_values.add(str,NULL);
919 for (size_t i=0; i<has_values.size(); i++) {
920 const string& str = has_values.get_nth_key(i);
921 if (other.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) &&
922 !other.not_values.has_key(str) &&
923 !ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL);
926 for (size_t i=0; i<other.has_values.size(); i++) {
927 const string& str = other.has_values.get_nth_key(i);
928 if (size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE)) &&
929 !not_values.has_key(str) &&
930 !ret_val.has_values.has_key(str)) ret_val.has_values.add(str,NULL);
932 // N1+N2 (union of not_values)
933 for (size_t i=0; i<not_values.size(); i++) ret_val.not_values.add(not_values.get_nth_key(i),NULL);
934 for (size_t i=0; i<other.not_values.size(); i++) {
935 const string& str = other.not_values.get_nth_key(i);
936 if (!ret_val.not_values.has_key(str)) ret_val.not_values.add(str,NULL);
940 // drop ret_val.has_values that are elements of ret_val.not_values too, drop from ret_val.not_values too
941 for (size_t i=0; i<ret_val.not_values.size(); i++) {
942 string str = ret_val.not_values.get_nth_key(i);
943 if (ret_val.has_values.has_key(str)) {
944 ret_val.has_values.erase(str);
945 ret_val.not_values.erase(str);
949 // drop ret_val.has_values elements that are elements of the ret_val.size_constraint set
950 for (size_t i=0; i<ret_val.has_values.size(); i++) {
951 string str = ret_val.has_values.get_nth_key(i);
952 if (ret_val.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE))) {
953 ret_val.has_values.erase(str);
957 // drop ret_val.not_values elements that are not elements of the ret_val.size_constraint set
958 for (size_t i=0; i<ret_val.not_values.size(); i++) {
959 string str = ret_val.not_values.get_nth_key(i);
960 if (!ret_val.size_constraint.is_element(size_limit_t(str.size()/ELEMSIZE))) {
961 ret_val.not_values.erase(str);
966 ret_val.canonicalize();
970 template<unsigned char BITCNT, unsigned short ELEMSIZE>
971 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::operator~() const
973 StringSizeAndValueListConstraint<BITCNT,ELEMSIZE> ret_val;
974 ret_val.size_constraint = ~size_constraint;
975 for (size_t i=0; i<has_values.size(); i++) ret_val.not_values.add(has_values.get_nth_key(i),NULL);
976 for (size_t i=0; i<not_values.size(); i++) ret_val.has_values.add(not_values.get_nth_key(i),NULL);
977 ret_val.canonicalize();
981 template<unsigned char BITCNT, unsigned short ELEMSIZE>
982 string StringSizeAndValueListConstraint<BITCNT,ELEMSIZE>::to_string() const
985 if (has_values.size()>0) {
987 for (size_t i=0; i<has_values.size(); i++) {
988 if (i>0) ret_val += ',';
990 ret_val += has_values.get_nth_key(i);
992 if (BITCNT==1) ret_val += 'B';
993 else if (BITCNT==4) ret_val += 'H';
994 else if (BITCNT==8) ret_val += 'O';
999 if (size_constraint.is_empty()!=TTRUE) {
1000 if (has_values.size()>0) ret_val += " union ";
1001 ret_val += "length";
1002 ret_val += size_constraint.to_string();
1004 // except not_values
1005 if (not_values.size()>0) {
1006 ret_val += " except (";
1007 for (size_t i=0; i<not_values.size(); i++) {
1008 if (i>0) ret_val += ',';
1010 ret_val += not_values.get_nth_key(i);
1012 if (BITCNT==1) ret_val += 'B';
1013 else if (BITCNT==4) ret_val += 'H';
1014 else if (BITCNT==8) ret_val += 'O';
1021 typedef StringSizeAndValueListConstraint<1,1> BitstringConstraint;
1022 typedef StringSizeAndValueListConstraint<4,1> HexstringConstraint;
1023 typedef StringSizeAndValueListConstraint<8,2> OctetstringConstraint; // one char is half octet
1025 ////////////////////////////////////////////////////////////////////////////////
1027 class StringPatternConstraint
1030 Ttcn::PatternString* pattern; // not owned
1033 StringPatternConstraint() : pattern(0) {} // empty set
1034 StringPatternConstraint(Ttcn::PatternString* p): pattern(p) {}
1036 tribool is_empty() const { return TUNKNOWN; }
1037 tribool is_full() const { return TUNKNOWN; }
1038 tribool is_equal(const StringPatternConstraint&) const { return TUNKNOWN; }
1040 tribool match(const string& str) const;
1041 tribool match(const ustring&) const { return TUNKNOWN; } // TODO
1043 StringPatternConstraint set_operation(const StringPatternConstraint&, bool) const { FATAL_ERROR("StringPatternConstraint::set_operation(): not implemented"); }
1045 StringPatternConstraint operator+(const StringPatternConstraint& other) const { return set_operation(other, true); } // union
1046 StringPatternConstraint operator*(const StringPatternConstraint& other) const { return set_operation(other, false); } // intersection
1047 StringPatternConstraint operator~() const { FATAL_ERROR("StringPatternConstraint::operator~(): not implemented"); }
1049 tribool is_subset(const StringPatternConstraint&) const { return TUNKNOWN; }
1050 StringPatternConstraint operator-(const StringPatternConstraint& other) const { return ( *this * ~other ); } // except
1052 string to_string() const;
1055 ////////////////////////////////////////////////////////////////////////////////
1057 template <class STRINGTYPE>
1058 class StringValueConstraint
1061 map<STRINGTYPE,void> values;
1063 void copy_content(const StringValueConstraint& other);
1066 StringValueConstraint() {} // empty set
1067 StringValueConstraint(const STRINGTYPE& s) { values.add(s,NULL); } // single value set
1069 StringValueConstraint(const StringValueConstraint& other) { copy_content(other); }
1070 StringValueConstraint& operator=(const StringValueConstraint& other) { clean_up(); copy_content(other); return *this; }
1071 ~StringValueConstraint() { clean_up(); }
1073 tribool is_empty() const { return TRIBOOL(values.size()==0); }
1074 tribool is_full() const { return TFALSE; }
1075 tribool is_equal(const StringValueConstraint& other) const;
1076 bool is_element(const STRINGTYPE& s) const { return values.has_key(s); }
1078 StringValueConstraint set_operation(const StringValueConstraint& other, bool is_union) const;
1080 StringValueConstraint operator+(const StringValueConstraint& other) const { return set_operation(other, true); } // union
1081 StringValueConstraint operator*(const StringValueConstraint& other) const { return set_operation(other, false); } // intersection
1083 tribool is_subset(const StringValueConstraint& other) const { return (*this-other).is_empty(); }
1084 StringValueConstraint operator-(const StringValueConstraint& other) const; // except
1086 // remove strings that are or are not elements of the set defined by the XXX_constraint object,
1087 // using the XXX_constraint.is_element() member function
1088 void remove(const SizeRangeListConstraint& size_constraint, bool if_element);
1089 template <class CHARLIMITTYPE> void remove(const RangeListConstraint<CHARLIMITTYPE>& alphabet_constraint, bool if_element);
1090 void remove(const StringPatternConstraint& pattern_constraint, bool if_element);
1092 string to_string() const;
1095 template <class STRINGTYPE>
1096 void StringValueConstraint<STRINGTYPE>::clean_up()
1101 template <class STRINGTYPE>
1102 void StringValueConstraint<STRINGTYPE>::copy_content(const StringValueConstraint<STRINGTYPE>& other)
1104 for (size_t i=0; i<other.values.size(); i++) values.add(other.values.get_nth_key(i),NULL);
1107 template <class STRINGTYPE>
1108 tribool StringValueConstraint<STRINGTYPE>::is_equal(const StringValueConstraint<STRINGTYPE>& other) const
1110 if (values.size()!=other.values.size()) return TFALSE;
1111 for (size_t i=0; i<values.size(); i++) {
1112 if (values.get_nth_key(i)!=other.values.get_nth_key(i)) return TFALSE;
1117 template <class STRINGTYPE>
1118 StringValueConstraint<STRINGTYPE> StringValueConstraint<STRINGTYPE>::set_operation
1119 (const StringValueConstraint<STRINGTYPE>& other, bool is_union) const
1121 StringValueConstraint<STRINGTYPE> ret_val;
1123 for (size_t i=0; i<values.size(); i++) ret_val.values.add(values.get_nth_key(i), NULL);
1124 for (size_t i=0; i<other.values.size(); i++) {
1125 const STRINGTYPE& str = other.values.get_nth_key(i);
1126 if (!ret_val.values.has_key(str)) ret_val.values.add(str, NULL);
1129 for (size_t i=0; i<values.size(); i++) {
1130 const STRINGTYPE& str = values.get_nth_key(i);
1131 if (other.values.has_key(str)) ret_val.values.add(str, NULL);
1137 template <class STRINGTYPE>
1138 StringValueConstraint<STRINGTYPE> StringValueConstraint<STRINGTYPE>::operator-(const StringValueConstraint<STRINGTYPE>& other) const
1140 StringValueConstraint<STRINGTYPE> ret_val;
1141 for (size_t i=0; i<values.size(); i++) {
1142 const STRINGTYPE& str = values.get_nth_key(i);
1143 if (!other.values.has_key(str)) ret_val.values.add(str, NULL);
1148 template <class STRINGTYPE>
1149 void StringValueConstraint<STRINGTYPE>::remove(const SizeRangeListConstraint& size_constraint, bool if_element)
1151 for (size_t i=0; i<values.size(); i++) {
1152 STRINGTYPE str = values.get_nth_key(i);
1153 if (size_constraint.is_element(size_limit_t(str.size()))==if_element) {
1160 template <class STRINGTYPE>
1161 template <class CHARLIMITTYPE>
1162 void StringValueConstraint<STRINGTYPE>::remove(const RangeListConstraint<CHARLIMITTYPE>& alphabet_constraint, bool if_element)
1164 for (size_t i=0; i<values.size(); i++) {
1165 STRINGTYPE str = values.get_nth_key(i);
1166 bool all_chars_are_elements = true;
1167 for (size_t chr_idx=0; chr_idx<str.size(); chr_idx++)
1169 if (!alphabet_constraint.is_element(CHARLIMITTYPE(str[chr_idx]))) {
1170 all_chars_are_elements = false;
1174 if (all_chars_are_elements==if_element) {
1181 template <class STRINGTYPE>
1182 void StringValueConstraint<STRINGTYPE>::remove(const StringPatternConstraint& pattern_constraint, bool if_element)
1184 for (size_t i=0; i<values.size(); i++) {
1185 STRINGTYPE str = values.get_nth_key(i);
1186 switch (pattern_constraint.match(str)) {
1188 if (!if_element) { values.erase(str); i--; }
1193 if (if_element) { values.erase(str); i--; }
1196 FATAL_ERROR("StringValueConstraint::remove(StringPatternConstraint)");
1201 template <class STRINGTYPE>
1202 string StringValueConstraint<STRINGTYPE>::to_string() const
1206 for (size_t i=0; i<values.size(); i++) {
1207 if (i>0) ret_val += ',';
1208 STRINGTYPE str = values.get_nth_key(i);
1209 ret_val += str.get_stringRepr();
1215 ////////////////////////////////////////////////////////////////////////////////
1217 // contains a tree of subtype constraints
1218 template <class STRINGTYPE, class CHARLIMITTYPE>
1219 class StringSubtypeTreeElement
1222 enum elementtype_t {
1223 ET_NONE, // empty set
1224 ET_ALL, // all values of the root type, no subtype constraint was given, other data members have no meaning
1225 ET_CONSTRAINT, // constraint value
1226 ET_INTERSECTION, // A intersection B
1227 ET_UNION, // A union B
1228 ET_EXCEPT // A except B
1230 enum constrainttype_t {
1237 elementtype_t elementtype;
1239 struct { // operation (ET_INTERSECTION, ET_UNION, ET_EXCEPT)
1240 StringSubtypeTreeElement* a; // owned
1241 StringSubtypeTreeElement* b; // owned
1243 struct { // constraint
1244 constrainttype_t constrainttype;
1245 union { // constraint objects are owned
1246 SizeRangeListConstraint* s; // size/length constraint type
1248 RangeListConstraint<CHARLIMITTYPE>* c; // range/alphabet constraint type
1249 bool char_context; // this constraint can be either in char or string context
1250 // char context is constraining a single char,
1251 // string context is constraining a string
1252 // this bool value affects evaluation
1253 // in char context only range,all,none and operation
1254 // constructors can be called, operations must always evaluate
1255 // to range, all or none
1257 StringValueConstraint<STRINGTYPE>* v; // value set constraint
1258 StringPatternConstraint* p; // pattern constraint
1263 void copy_content(const StringSubtypeTreeElement& other); // *this must be empty
1264 void set_to_operand(bool operand_a);
1265 void simplify(); // convert to ET_NONE or ET_ALL if possible
1266 void evaluate(); // tries to evaluate a tree to a single constraint, works recursively for the whole tree
1268 StringSubtypeTreeElement(): elementtype(ET_NONE) {}
1269 StringSubtypeTreeElement(elementtype_t p_elementtype, StringSubtypeTreeElement* p_a, StringSubtypeTreeElement* p_b);
1270 StringSubtypeTreeElement(const SizeRangeListConstraint& p_s);
1271 StringSubtypeTreeElement(const RangeListConstraint<CHARLIMITTYPE>& p_a, bool p_char_context);
1272 StringSubtypeTreeElement(const StringValueConstraint<STRINGTYPE>& p_v);
1273 StringSubtypeTreeElement(const StringPatternConstraint& p_p);
1275 StringSubtypeTreeElement(const StringSubtypeTreeElement& p) { copy_content(p); }
1276 StringSubtypeTreeElement& operator=(const StringSubtypeTreeElement& other) { clean_up(); copy_content(other); return *this; }
1277 ~StringSubtypeTreeElement() { clean_up(); }
1279 tribool is_empty() const;
1280 tribool is_full() const;
1281 tribool is_equal(const StringSubtypeTreeElement* other) const;
1282 bool is_element(const STRINGTYPE& s) const;
1283 tribool is_subset(const StringSubtypeTreeElement* other) const;
1285 bool is_single_constraint() const { return ( (elementtype==ET_CONSTRAINT) || (elementtype==ET_NONE) || (elementtype==ET_ALL) ); }
1286 void set_none() { clean_up(); elementtype = ET_NONE; }
1287 void set_all() { clean_up(); elementtype = ET_ALL; }
1290 TFALSE: limit does not exist (empty set or values, ...)
1291 TUNKNOWN: limit cannot be determined
1292 TTRUE: limit was set to the proper value */
1293 tribool get_alphabet_limit(bool is_upper, CHARLIMITTYPE& limit) const;
1294 tribool get_size_limit(bool is_upper, size_limit_t& limit) const;
1296 bool is_valid_range() const;
1297 void set_char_context(bool p_char_context);
1299 string to_string() const;
1302 template <class STRINGTYPE, class CHARLIMITTYPE>
1303 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement(elementtype_t p_elementtype, StringSubtypeTreeElement* p_a, StringSubtypeTreeElement* p_b)
1304 : elementtype(p_elementtype)
1306 switch (elementtype) {
1307 case ET_INTERSECTION:
1312 FATAL_ERROR("StringSubtypeTreeElement::StringSubtypeTreeElement()");
1320 template <class STRINGTYPE, class CHARLIMITTYPE>
1321 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::
1322 get_alphabet_limit(bool is_upper, CHARLIMITTYPE& limit) const
1324 switch (elementtype) {
1328 limit = is_upper ? CHARLIMITTYPE::maximum : CHARLIMITTYPE::minimum;
1331 switch (u.cs.constrainttype) {
1333 limit = is_upper ? CHARLIMITTYPE::maximum : CHARLIMITTYPE::minimum;
1336 if (u.cs.a.c->is_empty()==TTRUE) return TFALSE;
1337 limit = is_upper ? u.cs.a.c->get_maximal() : u.cs.a.c->get_minimal();
1344 FATAL_ERROR("StringSubtypeTreeElement::get_alphabet_limit()");
1346 case ET_INTERSECTION: {
1347 CHARLIMITTYPE la, lb;
1348 tribool tb = u.op.a->get_alphabet_limit(is_upper, la) && u.op.b->get_alphabet_limit(is_upper, lb);
1350 limit = ((lb<la) ^ !is_upper) ? lb : la;
1358 FATAL_ERROR("StringSubtypeTreeElement::get_alphabet_limit()");
1363 template <class STRINGTYPE, class CHARLIMITTYPE>
1364 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::
1365 get_size_limit(bool is_upper, size_limit_t& limit) const
1367 switch (elementtype) {
1371 limit = is_upper ? size_limit_t::maximum : size_limit_t::minimum;
1374 switch (u.cs.constrainttype) {
1376 if (u.cs.s->is_empty()==TTRUE) return TFALSE;
1377 limit = is_upper ? u.cs.s->get_maximal() : u.cs.s->get_minimal();
1380 limit = is_upper ? size_limit_t::maximum : size_limit_t::minimum;
1387 FATAL_ERROR("StringSubtypeTreeElement::get_size_limit()");
1389 case ET_INTERSECTION: {
1390 size_limit_t la, lb;
1391 tribool tb = u.op.a->get_size_limit(is_upper, la) && u.op.b->get_size_limit(is_upper, lb);
1393 limit = ((lb<la) ^ !is_upper) ? lb : la;
1401 FATAL_ERROR("StringSubtypeTreeElement::get_size_limit()");
1406 template <class STRINGTYPE, class CHARLIMITTYPE>
1407 bool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_valid_range() const
1409 switch (elementtype) {
1414 switch (u.cs.constrainttype) {
1417 return (u.cs.s->is_equal(SizeRangeListConstraint(size_limit_t(1)))==TTRUE);
1424 FATAL_ERROR("StringSubtypeTreeElement::is_valid_range()");
1426 case ET_INTERSECTION:
1429 return ( u.op.a->is_valid_range() && u.op.b->is_valid_range() );
1431 FATAL_ERROR("StringSubtypeTreeElement::is_valid_range()");
1436 template <class STRINGTYPE, class CHARLIMITTYPE>
1437 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::set_char_context(bool p_char_context)
1439 switch (elementtype) {
1444 u.cs.a.char_context = p_char_context;
1445 switch (u.cs.constrainttype) {
1447 if (p_char_context) set_all(); // false -> true
1448 else FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1452 FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1455 case ET_INTERSECTION:
1458 u.op.a->set_char_context(p_char_context);
1459 u.op.b->set_char_context(p_char_context);
1462 FATAL_ERROR("StringSubtypeTreeElement::set_char_context()");
1466 template <class STRINGTYPE, class CHARLIMITTYPE>
1467 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1468 (const SizeRangeListConstraint& p_s):
1469 elementtype(ET_CONSTRAINT)
1471 u.cs.constrainttype = CT_SIZE;
1472 u.cs.s = new SizeRangeListConstraint(p_s);
1476 template <class STRINGTYPE, class CHARLIMITTYPE>
1477 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1478 (const RangeListConstraint<CHARLIMITTYPE>& p_a, bool p_char_context):
1479 elementtype(ET_CONSTRAINT)
1481 u.cs.constrainttype = CT_ALPHABET;
1482 u.cs.a.c = new RangeListConstraint<CHARLIMITTYPE>(p_a);
1483 u.cs.a.char_context = p_char_context;
1487 template <class STRINGTYPE, class CHARLIMITTYPE>
1488 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1489 (const StringValueConstraint<STRINGTYPE>& p_v):
1490 elementtype(ET_CONSTRAINT)
1492 u.cs.constrainttype = CT_VALUES;
1493 u.cs.v = new StringValueConstraint<STRINGTYPE>(p_v);
1497 template <class STRINGTYPE, class CHARLIMITTYPE>
1498 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::StringSubtypeTreeElement
1499 (const StringPatternConstraint& p_p):
1500 elementtype(ET_CONSTRAINT)
1502 u.cs.constrainttype = CT_PATTERN;
1503 u.cs.p = new StringPatternConstraint(p_p);
1507 template <class STRINGTYPE, class CHARLIMITTYPE>
1508 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::clean_up()
1510 switch (elementtype) {
1515 switch (u.cs.constrainttype) {
1516 case CT_SIZE: delete u.cs.s; break;
1517 case CT_ALPHABET: delete u.cs.a.c; break;
1518 case CT_VALUES: delete u.cs.v; break;
1519 case CT_PATTERN: delete u.cs.p; break;
1520 default: FATAL_ERROR("StringSubtypeTreeElement::clean_up()");
1523 case ET_INTERSECTION:
1530 FATAL_ERROR("StringSubtypeTreeElement::clean_up()");
1534 template <class STRINGTYPE, class CHARLIMITTYPE>
1535 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::copy_content(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>& other)
1537 elementtype = other.elementtype;
1538 switch (elementtype) {
1543 u.cs.constrainttype = other.u.cs.constrainttype;
1544 switch (u.cs.constrainttype) {
1545 case CT_SIZE: u.cs.s = new SizeRangeListConstraint(*(other.u.cs.s)); break;
1547 u.cs.a.c = new RangeListConstraint<CHARLIMITTYPE>(*(other.u.cs.a.c));
1548 u.cs.a.char_context = other.u.cs.a.char_context;
1550 case CT_VALUES: u.cs.v = new StringValueConstraint<STRINGTYPE>(*(other.u.cs.v)); break;
1551 case CT_PATTERN: u.cs.p = new StringPatternConstraint(*(other.u.cs.p)); break;
1552 default: FATAL_ERROR("StringSubtypeTreeElement::copy_content()");
1555 case ET_INTERSECTION:
1558 u.op.a = new StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>(*(other.u.op.a));
1559 u.op.b = new StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>(*(other.u.op.b));
1562 FATAL_ERROR("StringSubtypeTreeElement::copy_content()");
1566 template <class STRINGTYPE, class CHARLIMITTYPE>
1567 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::set_to_operand(bool operand_a)
1569 switch (elementtype) {
1570 case ET_INTERSECTION:
1575 FATAL_ERROR("StringSubtypeTreeElement::copy_operand()");
1577 StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* op;
1585 // steal the content of op into myself
1586 elementtype = op->elementtype;
1587 switch (elementtype) {
1592 u.cs.constrainttype = op->u.cs.constrainttype;
1593 switch (u.cs.constrainttype) {
1594 case CT_SIZE: u.cs.s = op->u.cs.s; break;
1596 u.cs.a.c = op->u.cs.a.c;
1597 u.cs.a.char_context = op->u.cs.a.char_context;
1599 case CT_VALUES: u.cs.v = op->u.cs.v; break;
1600 case CT_PATTERN: u.cs.p = op->u.cs.p; break;
1601 default: FATAL_ERROR("StringSubtypeTreeElement::copy_operand()");
1604 case ET_INTERSECTION:
1607 u.op.a = op->u.op.a;
1608 u.op.b = op->u.op.b;
1611 FATAL_ERROR("StringSubtypeTreeElement::copy_operand()");
1613 // delete the empty op
1614 op->elementtype = ET_NONE;
1618 template <class STRINGTYPE, class CHARLIMITTYPE>
1619 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::simplify()
1621 switch (elementtype) {
1626 switch (u.cs.constrainttype) {
1628 if (u.cs.s->is_empty()==TTRUE) { set_none(); return; }
1629 if (u.cs.s->is_full()==TTRUE) { set_all(); return; }
1632 if (u.cs.a.c->is_empty()==TTRUE) { set_none(); return; }
1633 if (u.cs.a.c->is_full()==TTRUE) { set_all(); return; }
1636 if (u.cs.v->is_empty()==TTRUE) { set_none(); return; }
1637 if (u.cs.v->is_full()==TTRUE) { set_all(); return; }
1640 if (u.cs.p->is_empty()==TTRUE) { set_none(); return; }
1641 if (u.cs.p->is_full()==TTRUE) { set_all(); return; }
1643 default: FATAL_ERROR("StringSubtypeTreeElement::simplify()");
1646 case ET_INTERSECTION:
1651 FATAL_ERROR("StringSubtypeTreeElement::simplify()");
1655 template <class STRINGTYPE, class CHARLIMITTYPE>
1656 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_empty() const
1658 switch (elementtype) {
1664 switch (u.cs.constrainttype) {
1665 case CT_SIZE: return u.cs.s->is_empty();
1666 case CT_ALPHABET: return ( u.cs.a.char_context ? u.cs.a.c->is_empty() : TFALSE );
1667 case CT_VALUES: return u.cs.v->is_empty();
1668 case CT_PATTERN: return u.cs.p->is_empty();
1669 default: FATAL_ERROR("StringSubtypeTreeElement::is_empty()");
1671 case ET_INTERSECTION:
1672 return ( u.op.a->is_empty() || u.op.b->is_empty() );
1674 return ( u.op.a->is_empty() && u.op.b->is_empty() );
1676 tribool a_empty = u.op.a->is_empty();
1677 return ( (a_empty!=TFALSE) ? a_empty :
1678 ( (u.op.b->is_empty()==TTRUE) ? TFALSE : TUNKNOWN ) );
1681 FATAL_ERROR("StringSubtypeTreeElement::is_empty()");
1686 template <class STRINGTYPE, class CHARLIMITTYPE>
1687 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_full() const
1689 switch (elementtype) {
1695 switch (u.cs.constrainttype) {
1696 case CT_SIZE: return u.cs.s->is_full();
1697 case CT_ALPHABET: return u.cs.a.c->is_full();
1698 case CT_VALUES: return u.cs.v->is_full();
1699 case CT_PATTERN: return u.cs.p->is_full();
1700 default: FATAL_ERROR("StringSubtypeTreeElement::is_full()");
1702 case ET_INTERSECTION:
1703 return ( u.op.a->is_full() && u.op.b->is_full() );
1705 return ( u.op.a->is_full() || u.op.b->is_full() );
1707 return ( u.op.a->is_full() && u.op.b->is_empty() );
1709 FATAL_ERROR("StringSubtypeTreeElement::is_full()");
1714 template <class STRINGTYPE, class CHARLIMITTYPE>
1715 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_equal(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* other) const
1717 if (elementtype!=other->elementtype) return TUNKNOWN;
1718 switch (elementtype) {
1723 if (u.cs.constrainttype!=other->u.cs.constrainttype) return TUNKNOWN;
1724 switch (u.cs.constrainttype) {
1725 case CT_SIZE: return u.cs.s->is_equal(*(other->u.cs.s));
1726 case CT_ALPHABET: return u.cs.a->is_equal(*(other->u.cs.a));
1727 case CT_VALUES: return u.cs.v->is_equal(*(other->u.cs.v));
1728 case CT_PATTERN: return u.cs.p->is_equal(*(other->u.cs.p));
1729 default: FATAL_ERROR("StringSubtypeTreeElement::is_equal()");
1731 case ET_INTERSECTION:
1736 FATAL_ERROR("StringSubtypeTreeElement::is_equal()");
1741 template <class STRINGTYPE, class CHARLIMITTYPE>
1742 bool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_element(const STRINGTYPE& s) const
1744 switch (elementtype) {
1750 switch (u.cs.constrainttype) {
1751 case CT_SIZE: return u.cs.s->is_element(size_limit_t(s.size()));
1753 for (size_t i=0; i<s.size(); i++) {
1754 CHARLIMITTYPE cl(s[i]);
1755 if (!u.cs.a.c->is_element(cl)) return false;
1759 case CT_VALUES: return u.cs.v->is_element(s);
1761 switch (u.cs.p->match(s)) {
1762 case TFALSE: return false;
1763 case TUNKNOWN: return true; // don't know if it matches
1764 case TTRUE: return true;
1765 default: FATAL_ERROR("StringSubtypeTreeElement::is_element()");
1768 default: FATAL_ERROR("StringSubtypeTreeElement::is_element()");
1770 case ET_INTERSECTION:
1771 return ( u.op.a->is_element(s) && u.op.b->is_element(s) );
1773 return ( u.op.a->is_element(s) || u.op.b->is_element(s) );
1775 return ( u.op.a->is_element(s) && !u.op.b->is_element(s) );
1777 FATAL_ERROR("StringSubtypeTreeElement::is_element()");
1782 // if the constraints are ortogonal (e.g. size and alphabet) or just different then return TUNKNOWN
1783 // in case of ortogonal constraints we should return TFALSE (if other is not full set)
1784 // but it seems that the standard wants to ignore such trivial cases, example:
1785 // length(1..4) is_subset ('a'..'z') shall not report an error
1786 template <class STRINGTYPE, class CHARLIMITTYPE>
1787 tribool StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::is_subset(const StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>* other) const
1789 switch (elementtype) {
1793 if (other->elementtype==ET_ALL) return TTRUE;
1794 else return TUNKNOWN;
1796 if (elementtype!=other->elementtype) return TUNKNOWN;
1797 if (u.cs.constrainttype!=other->u.cs.constrainttype) return TUNKNOWN;
1798 switch (u.cs.constrainttype) {
1799 case CT_SIZE: return u.cs.s->is_subset(*(other->u.cs.s));
1800 case CT_ALPHABET: return u.cs.a.c->is_subset(*(other->u.cs.a.c));
1801 case CT_VALUES: return u.cs.v->is_subset(*(other->u.cs.v));
1802 case CT_PATTERN: return u.cs.p->is_subset(*(other->u.cs.p));
1803 default: FATAL_ERROR("StringSubtypeTreeElement::is_subset()");
1805 case ET_INTERSECTION:
1810 FATAL_ERROR("StringSubtypeTreeElement::is_subset()");
1815 template <class STRINGTYPE, class CHARLIMITTYPE>
1816 void StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::evaluate()
1818 switch (elementtype) {
1822 // these are the simplest forms, others are reduced to these in ideal case
1824 case ET_INTERSECTION:
1829 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
1832 // recursive evaluation
1836 // special case where the construct looks like this:
1840 // can be union or intersection, try to exchange constraint to have same type of constraints as operands,
1841 // constraint types: tree, ....
1842 // if succeeded then evaluate the new construct
1845 // special simple cases when one side is ET_ALL or ET_NONE but the other can be a tree
1846 if ( (u.op.a->elementtype==ET_NONE) || (u.op.b->elementtype==ET_NONE) ) {
1847 if (elementtype==ET_INTERSECTION) { set_none(); return; }
1848 if (elementtype==ET_UNION) {
1849 // the result is the other set
1850 set_to_operand(u.op.b->elementtype==ET_NONE);
1854 if ( (u.op.b->elementtype==ET_NONE) && (elementtype==ET_EXCEPT) ) {
1855 set_to_operand(true);
1858 if ( (u.op.a->elementtype==ET_ALL) || (u.op.b->elementtype==ET_ALL) ) {
1859 if (elementtype==ET_INTERSECTION) {
1860 // the result is the other set
1861 set_to_operand(u.op.b->elementtype==ET_ALL);
1864 if (elementtype==ET_UNION) { set_all(); return; }
1866 if ( (u.op.b->elementtype==ET_ALL) && (elementtype==ET_EXCEPT) ) { set_none(); return; }
1868 // both operands must be single constraints (ALL,NONE,CONSTRAINT),
1869 // after this point trees will not be further simplified
1870 if (!u.op.a->is_single_constraint() || !u.op.b->is_single_constraint()) return;
1872 // special case: ALL - some constraint type that can be complemented
1873 if ( (u.op.a->elementtype==ET_ALL) && (elementtype==ET_EXCEPT) && (u.op.b->elementtype==ET_CONSTRAINT) ) {
1874 switch (u.op.b->u.cs.constrainttype) {
1876 SizeRangeListConstraint* rvs = new SizeRangeListConstraint(~*(u.op.b->u.cs.s));
1878 elementtype = ET_CONSTRAINT;
1879 u.cs.constrainttype = CT_SIZE;
1884 if (u.cs.a.char_context) {
1885 RangeListConstraint<CHARLIMITTYPE>* rva = new RangeListConstraint<CHARLIMITTYPE>(~*(u.op.b->u.cs.a.c));
1887 elementtype = ET_CONSTRAINT;
1888 u.cs.constrainttype = CT_ALPHABET;
1890 u.cs.a.char_context = true;
1899 // special case: when one operand is CT_VALUES then is_element() can be called for the values
1900 // and drop values or drop the other operand set or both depending on the operation
1901 StringValueConstraint<STRINGTYPE>* svc = NULL;
1902 bool first_is_svc = false;
1903 if ( (u.op.a->elementtype==ET_CONSTRAINT) && (u.op.a->u.cs.constrainttype==CT_VALUES) ) {
1904 svc = u.op.a->u.cs.v;
1905 first_is_svc = true;
1906 } else if ( (u.op.b->elementtype==ET_CONSTRAINT) && (u.op.b->u.cs.constrainttype==CT_VALUES) ) {
1907 svc = u.op.b->u.cs.v;
1908 first_is_svc = false; // it's the second
1910 if (svc!=NULL) { // if one or both operands are CT_VALUES
1911 switch (elementtype) {
1912 case ET_INTERSECTION: {
1913 switch (first_is_svc ? u.op.b->u.cs.constrainttype : u.op.a->u.cs.constrainttype) {
1915 svc->remove(*(first_is_svc ? u.op.b->u.cs.s : u.op.a->u.cs.s), false);
1918 svc->remove(*(first_is_svc ? u.op.b->u.cs.a.c : u.op.a->u.cs.a.c), false);
1921 svc->remove(*(first_is_svc ? u.op.b->u.cs.p : u.op.a->u.cs.p), false);
1926 // drop the other operand, keep the values as constraint of this object
1927 StringValueConstraint<STRINGTYPE>* keep_svc = new StringValueConstraint<STRINGTYPE>(*svc);
1929 elementtype = ET_CONSTRAINT;
1930 u.cs.constrainttype = CT_VALUES;
1936 switch (first_is_svc ? u.op.b->u.cs.constrainttype : u.op.a->u.cs.constrainttype) {
1938 svc->remove(*(first_is_svc ? u.op.b->u.cs.s : u.op.a->u.cs.s), true);
1941 svc->remove(*(first_is_svc ? u.op.b->u.cs.a.c : u.op.a->u.cs.a.c), true);
1944 svc->remove(*(first_is_svc ? u.op.b->u.cs.p : u.op.a->u.cs.p), true);
1949 // if all values were dropped then drop the empty values operand
1950 if (svc->is_empty()==TTRUE) {
1951 set_to_operand(!first_is_svc);
1956 if (first_is_svc) { // the second operand is u.op.b->u.cs.X where X can be length/alphabet/pattern constraint
1957 switch (u.op.b->u.cs.constrainttype) {
1959 svc->remove(*(u.op.b->u.cs.s), true);
1962 svc->remove(*(u.op.b->u.cs.a.c), true);
1965 svc->remove(*(u.op.b->u.cs.p), true);
1970 // drop the other operand, keep the values as constraint of this object
1971 StringValueConstraint<STRINGTYPE>* keep_svc = new StringValueConstraint<STRINGTYPE>(*svc);
1973 elementtype = ET_CONSTRAINT;
1974 u.cs.constrainttype = CT_VALUES;
1981 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
1985 // operands of same types can be evaluated to one constraint using their
1986 // set arithmetic member functions
1987 // alphabet constraint in string context:
1988 // FROM(A) UNION FROM(B) =/= FROM(A UNION B)
1989 // ALL - FROM(A) =/= FROM(ALL - A)
1990 // FROM(A) INTERSECTION FROM(B) == FROM (A INTERSECTION B)
1991 if (u.op.a->elementtype==u.op.b->elementtype) {
1992 switch (u.op.a->elementtype) {
1994 if (elementtype==ET_EXCEPT) set_none();
2001 if (u.op.a->u.cs.constrainttype==u.op.b->u.cs.constrainttype) {
2002 switch (u.op.a->u.cs.constrainttype) {
2004 SizeRangeListConstraint* rvs = new SizeRangeListConstraint;
2005 switch (elementtype) {
2006 case ET_INTERSECTION:
2007 *rvs = *(u.op.a->u.cs.s) * *(u.op.b->u.cs.s);
2010 *rvs = *(u.op.a->u.cs.s) + *(u.op.b->u.cs.s);
2013 *rvs = *(u.op.a->u.cs.s) - *(u.op.b->u.cs.s);
2016 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2019 elementtype = ET_CONSTRAINT;
2020 u.cs.constrainttype = CT_SIZE;
2024 bool char_ctx = u.op.a->u.cs.a.char_context;
2025 if (u.op.b->u.cs.a.char_context!=char_ctx) FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2026 if (char_ctx || (elementtype==ET_INTERSECTION)) {
2027 RangeListConstraint<CHARLIMITTYPE>* rva = new RangeListConstraint<CHARLIMITTYPE>;
2028 switch (elementtype) {
2029 case ET_INTERSECTION:
2030 *rva = *(u.op.a->u.cs.a.c) * *(u.op.b->u.cs.a.c);
2033 *rva = *(u.op.a->u.cs.a.c) + *(u.op.b->u.cs.a.c);
2036 *rva = *(u.op.a->u.cs.a.c) - *(u.op.b->u.cs.a.c);
2039 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2042 elementtype = ET_CONSTRAINT;
2043 u.cs.constrainttype = CT_ALPHABET;
2045 u.cs.a.char_context = char_ctx;
2049 StringValueConstraint<STRINGTYPE>* rvv = new StringValueConstraint<STRINGTYPE>;
2050 switch (elementtype) {
2051 case ET_INTERSECTION:
2052 *rvv = *(u.op.a->u.cs.v) * *(u.op.b->u.cs.v);
2055 *rvv = *(u.op.a->u.cs.v) + *(u.op.b->u.cs.v);
2058 *rvv = *(u.op.a->u.cs.v) - *(u.op.b->u.cs.v);
2061 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2064 elementtype = ET_CONSTRAINT;
2065 u.cs.constrainttype = CT_VALUES;
2071 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2076 FATAL_ERROR("StringSubtypeTreeElement::evaluate()");
2082 template <class STRINGTYPE, class CHARLIMITTYPE>
2083 string StringSubtypeTreeElement<STRINGTYPE,CHARLIMITTYPE>::to_string() const
2086 bool print_operation = false;
2088 switch (elementtype) {
2095 switch (u.cs.constrainttype) {
2097 ret_val += "length";
2098 ret_val += u.cs.s->to_string();
2101 ret_val += u.cs.a.char_context ? "range" : "from";
2102 ret_val += u.cs.a.c->to_string();
2105 ret_val += u.cs.v->to_string();
2108 ret_val += u.cs.p->to_string();
2111 FATAL_ERROR("StringSubtypeTreeElement::to_string()");
2114 case ET_INTERSECTION:
2115 op_str = "intersection";
2116 print_operation = true;
2120 print_operation = true;
2124 print_operation = true;
2127 FATAL_ERROR("StringSubtypeTreeElement::to_string()");
2129 if (print_operation) {
2131 ret_val += u.op.a->to_string();
2135 ret_val += u.op.b->to_string();
2141 typedef StringSubtypeTreeElement<string,char_limit_t> CharstringSubtypeTreeElement;
2142 typedef StringSubtypeTreeElement<ustring,universal_char_limit_t> UniversalCharstringSubtypeTreeElement;
2144 ////////////////////////////////////////////////////////////////////////////////
2145 // constraint classes for structured types
2147 // used by ValueListConstraint and RecofConstraint classes
2148 // only operator==() is used, since most value types do not have operator<()
2149 // when used in RecofConstraint it will use Value::get_nof_comps()
2153 vector<Value> values; // values are not owned
2155 void copy_content(const ValueList& other);
2157 ValueList() : values() {} // empty set
2158 ValueList(Value* v) : values() { values.add(v); }
2160 ValueList(const ValueList& other) : values() { copy_content(other); }
2161 ValueList& operator=(const ValueList& other) { clean_up(); copy_content(other); return *this; }
2162 ~ValueList() { clean_up(); }
2164 tribool is_empty() const { return TRIBOOL(values.size()==0); }
2165 tribool is_full() const { return TUNKNOWN; } // it's unknown how many possible values we have
2166 tribool is_equal(const ValueList& other) const;
2167 bool is_element(Value* v) const;
2169 // remove all elements whose size is (not) element of the given length set
2170 // works only if the type of values is correct (the get_nof_comps() doesn't end in FATAL_ERROR)
2171 void remove(const SizeRangeListConstraint& size_constraint, bool if_element);
2173 ValueList set_operation(const ValueList& other, bool is_union) const;
2175 ValueList operator+(const ValueList& other) const { return set_operation(other, true); } // union
2176 ValueList operator*(const ValueList& other) const { return set_operation(other, false); } // intersection
2177 ValueList operator-(const ValueList& other) const; // except
2179 tribool is_subset(const ValueList& other) const { return (*this-other).is_empty(); }
2181 string to_string() const;
2184 // can be a ValueList or (ALL-ValueList), used for subtypes of structured types, enumerated and objid
2185 class ValueListConstraint
2191 ValueListConstraint(): complemented(false), values() {} // empty set
2192 ValueListConstraint(Value* v): complemented(false), values(v) {} // single element set
2193 ValueListConstraint(bool p_complemented): complemented(p_complemented), values() {} // empty of full set
2195 tribool is_empty() const;
2196 tribool is_full() const;
2197 tribool is_equal(const ValueListConstraint& other) const;
2198 bool is_element(Value* v) const;
2200 ValueListConstraint operator+(const ValueListConstraint& other) const; // union
2201 ValueListConstraint operator*(const ValueListConstraint& other) const; // intersection
2202 ValueListConstraint operator~() const; // complement
2204 inline tribool is_subset(const ValueListConstraint& other) const
2205 { return (*this*~other).is_empty(); }
2206 inline ValueListConstraint operator-(const ValueListConstraint& other) const
2207 { return ( *this * ~other ); } // except
2209 string to_string() const;
2212 // length and value list constraints for record/set of types
2213 class RecofConstraint
2216 SizeRangeListConstraint size_constraint;
2217 ValueList has_values, not_values;
2220 RecofConstraint(): size_constraint(), has_values(), not_values() {} // empty set
2221 RecofConstraint(Value* v): size_constraint(), has_values(v), not_values() {} // single value set
2222 RecofConstraint(const size_limit_t& sl): size_constraint(sl), has_values(), not_values() {} // single size value set
2223 RecofConstraint(const size_limit_t& rl_begin, const size_limit_t& rl_end)
2224 : size_constraint(rl_begin,rl_end), has_values(), not_values() {} // size range set
2225 RecofConstraint(const SizeRangeListConstraint& p_size_constraint)
2226 : size_constraint(p_size_constraint), has_values(), not_values() {}
2228 tribool is_empty() const;
2229 tribool is_full() const;
2230 tribool is_equal(const RecofConstraint& other) const;
2231 bool is_element(Value* v) const;
2233 RecofConstraint set_operation(const RecofConstraint& other, bool is_union) const;
2235 inline RecofConstraint operator+(const RecofConstraint& other) const { return set_operation(other, true); } // union
2236 inline RecofConstraint operator*(const RecofConstraint& other) const { return set_operation(other, false); } // intersection
2237 RecofConstraint operator~() const; // complement
2239 inline tribool is_subset(const RecofConstraint& other) const { return (*this*~other).is_empty(); }
2240 inline RecofConstraint operator-(const RecofConstraint& other) const { return ( *this * ~other ); } // except
2242 tribool get_size_limit(bool is_upper, size_limit_t& limit) const;
2244 string to_string() const;
2248 }// namespace Common
2250 #endif // #ifndef _Subtypestuff_HH