compiler2/subtypestuff.hh

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