ntsimulator/regxstring/regxstring_impl.cpp

   1 /*************************************************************************\r
   2 *\r
   3 * Licensed under the Apache License, Version 2.0 (the "License");\r
   4 * you may not use this file except in compliance with the License.\r
   5 * You may obtain a copy of the License at\r
   6 *\r
   7 *     http://www.apache.org/licenses/LICENSE-2.0\r
   8 *\r
   9 * Unless required by applicable law or agreed to in writing, software\r
  10 * distributed under the License is distributed on an "AS IS" BASIS,\r
  11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  12 * See the License for the specific language governing permissions and\r
  13 * limitations under the License.\r
  14 ***************************************************************************/\r
  15 \r
  16 #include <algorithm>\r
  17 #include <sstream>\r
  18 #include <ctime>\r
  19 #include <cassert>\r
  20 #include "regxstring.h"\r
  21 #include "regxstring_impl.h"\r
  22 \r
  23 #if _DZ_DEBUG\r
  24 #   include <iostream>\r
  25 \r
  26 static void printRefs(__DZ_OSTRINGSTREAM & oss,const REGXSTRING_NS::__Refs & refs)\r
  27 {\r
  28     for(REGXSTRING_NS::__Refs::const_iterator i = refs.begin();i != refs.end();++i)\r
  29         std::cout<<"\t"<<oss.str().substr(i->first,i->second);\r
  30 }\r
  31 \r
  32 #   define _OSS_OUT(msg) {  \\r
  33         std::cout<<msg<<" : "<<gdata.oss_.str(); \\r
  34         printRefs(gdata.oss_,gdata.refs_);    \\r
  35         std::cout<<std::endl;}\r
  36 #else\r
  37 #   define _OSS_OUT(str)\r
  38 #endif\r
  39 \r
  40 NAMESAPCE_BEGIN\r
  41 \r
  42 // Replacements for new and delete\r
  43 template<class T>\r
  44 T * New(){\r
  45     T * ret = __DZ_ALLOC<T>().allocate(1);\r
  46     return new (ret) T;\r
  47 }\r
  48 \r
  49 template<class T,class A>\r
  50 T * New(const A & a){\r
  51     T * ret = __DZ_ALLOC<T>().allocate(1);\r
  52     return new (ret) T(a);\r
  53 }\r
  54 \r
  55 template<class T,class A,class B>\r
  56 T * New(const A & a,const B & b){\r
  57     T * ret = __DZ_ALLOC<T>().allocate(1);\r
  58     return new (ret) T(a,b);\r
  59 }\r
  60 \r
  61 template<class T,class A,class B,class C>\r
  62 T * New(const A & a,const B & b,const C & c){\r
  63     T * ret = __DZ_ALLOC<T>().allocate(1);\r
  64     return new (ret) T(a,b,c);\r
  65 }\r
  66 template<class T>\r
  67 void Delete(T * p){\r
  68     typedef char __dummy[sizeof(T)];\r
  69     if(p){\r
  70         p->~T();\r
  71         __DZ_ALLOC<T>().deallocate(p,1);\r
  72     }\r
  73 }\r
  74 \r
  75 struct __IsNull\r
  76 {\r
  77     bool operator ()(__NodeBase * n) const{\r
  78         return !n;\r
  79     }\r
  80 };\r
  81 \r
  82 static const char * const SEP = "  ";\r
  83 \r
  84 static __DZ_STRING sep(int lvl)\r
  85 {\r
  86     __DZ_STRING ret;\r
  87     while(lvl-- > 0)\r
  88         ret += SEP;\r
  89     return ret;\r
  90 }\r
  91 \r
  92 static void appendNode(__NodeBase *& parent,__NodeBase * node)\r
  93 {\r
  94     if(!node)\r
  95         return;\r
  96     if(!parent)\r
  97         parent = New<__Seq>(node);\r
  98     else\r
  99         parent->AppendNode(node);\r
 100 }\r
 101 \r
 102 namespace Tools{\r
 103 \r
 104     inline bool IsRepeat(int ch){\r
 105         return ch == '?' || ch == '+' || ch == '*';\r
 106     }\r
 107 \r
 108     inline bool IsBegin(int ch){\r
 109         return ch == '^';\r
 110     }\r
 111 \r
 112     inline bool IsEnd(int ch){\r
 113         return ch == '$';\r
 114     }\r
 115 \r
 116     inline bool IsSlash(int ch){\r
 117         return ch == '\\';\r
 118     }\r
 119 \r
 120     inline bool IsSetBegin(int ch){\r
 121         return ch == '[';\r
 122     }\r
 123 \r
 124     inline bool IsSetEnd(int ch){\r
 125         return ch == ']';\r
 126     }\r
 127 \r
 128     inline bool IsGroupBegin(int ch){\r
 129         return ch == '(';\r
 130     }\r
 131 \r
 132     inline bool IsGroupEnd(int ch){\r
 133         return ch == ')';\r
 134     }\r
 135 \r
 136     inline bool IsSelect(int ch){\r
 137         return ch == '|';\r
 138     }\r
 139 \r
 140     inline bool IsRepeatBegin(int ch){\r
 141         return ch == '{';\r
 142     }\r
 143 \r
 144     inline bool IsRepeatEnd(int ch){\r
 145         return ch == '}';\r
 146     }\r
 147 \r
 148     inline bool NeedEnd(int ch){\r
 149         return IsGroupEnd(ch) || IsRepeatEnd(ch);\r
 150     }\r
 151 \r
 152     inline bool IsDigit(int ch){\r
 153         return '0' <= ch && ch <= '9';\r
 154     }\r
 155 \r
 156     inline int TransDigit(int ch){\r
 157         return ch - '0';\r
 158     }\r
 159 \r
 160     inline bool IsDash(int ch){\r
 161         return ch == '-';\r
 162     }\r
 163 \r
 164     inline bool IsAny(int ch){\r
 165         return ch == '.';\r
 166     }\r
 167 \r
 168     inline int IsSubexpMark(int ch){\r
 169         return (ch == ':' || ch == '=' || ch == '!' || ch == '>' ? ch : 0);\r
 170     }\r
 171 \r
 172     inline int IsSubexpMark(const char * s){\r
 173         return (*s == '?' ? IsSubexpMark(*(s + 1)) : 0);\r
 174     }\r
 175 \r
 176     inline char TransSlash(int ch){\r
 177         switch(ch){\r
 178             case 'f':return '\f';\r
 179             case 'n':return '\n';\r
 180             case 'r':return '\r';\r
 181             case 't':return '\t';\r
 182             case 'v':return '\v';\r
 183         }\r
 184         return ch;\r
 185     }\r
 186 }\r
 187 \r
 188 //struct __ParseData\r
 189 int __ParseData::inEnds(int ch) const\r
 190 {\r
 191     int ret = 1;\r
 192     for(__Ends::const_reverse_iterator i = ends_.rbegin();i != ends_.rend();++i,++ret){\r
 193         if(ch == *i)\r
 194             return ret;\r
 195         if(Tools::NeedEnd(*i))\r
 196             break;\r
 197     }\r
 198     return 0;\r
 199 }\r
 200 \r
 201 //struct __NodeBase\r
 202 __NodeBase * const __NodeBase::REP_NULL = (__NodeBase *)1;\r
 203 \r
 204 #if _MEM_LEAK\r
 205 int __NodeBase::ref = 0;\r
 206 #endif\r
 207 \r
 208 __NodeBase::~__NodeBase()\r
 209 {\r
 210 #if _MEM_LEAK\r
 211     --ref;\r
 212 #endif\r
 213 }\r
 214 \r
 215 int __NodeBase::Repeat(int ch)\r
 216 {\r
 217     return 1;\r
 218 }\r
 219 \r
 220 void __NodeBase::AppendNode(__NodeBase * node)\r
 221 {\r
 222     assert(0);\r
 223 }\r
 224 \r
 225 //struct __Edge\r
 226 __Edge::__Edge(int ch)\r
 227     : begin_(ch == '^')\r
 228 {}\r
 229 \r
 230 __NodeBase * __Edge::Optimize(__ParseData & pdata)\r
 231 {\r
 232     return REP_NULL;\r
 233 }\r
 234 \r
 235 void __Edge::RandString(__GenerateData & gdata) const\r
 236 {\r
 237     _OSS_OUT("__Edge");\r
 238 }\r
 239 \r
 240 void __Edge::Debug(std::ostream & out,int lvl) const\r
 241 {\r
 242     out<<sep(lvl)<<(begin_ ? "BEGIN" : "END")<<"\n";\r
 243 }\r
 244 \r
 245 //struct __Text\r
 246 __Text::__Text(int ch)\r
 247     : str_(1,ch)\r
 248 {}\r
 249 \r
 250 __NodeBase * __Text::Optimize(__ParseData & pdata)\r
 251 {\r
 252     return (str_.empty() ? REP_NULL : 0);\r
 253 }\r
 254 \r
 255 void __Text::RandString(__GenerateData & gdata) const\r
 256 {\r
 257     gdata.oss_<<str_;\r
 258     _OSS_OUT("__Text");\r
 259 }\r
 260 \r
 261 void __Text::Debug(std::ostream & out,int lvl) const\r
 262 {\r
 263     out<<sep(lvl)<<"Text("<<str_<<")\n";\r
 264 }\r
 265 \r
 266 //class __Charset\r
 267 __Charset::__Charset()\r
 268     : inc_(1)\r
 269 {}\r
 270 \r
 271 __Charset::__Charset(const __DZ_STRING & str,bool include)\r
 272     : str_(str)\r
 273     , inc_(include)\r
 274 {}\r
 275 \r
 276 __NodeBase * __Charset::Optimize(__ParseData & pdata)\r
 277 {\r
 278     if(!inc_)\r
 279         reverse();\r
 280     if(str_.empty())\r
 281         return REP_NULL;\r
 282     inc_ = str_.size();\r
 283     return 0;\r
 284 }\r
 285 \r
 286 void __Charset::RandString(__GenerateData & gdata) const\r
 287 {\r
 288     assert(inc_ == str_.size());\r
 289     gdata.oss_<<str_[rand() % inc_];\r
 290     _OSS_OUT("__Charset");\r
 291 }\r
 292 \r
 293 void __Charset::Debug(std::ostream & out,int lvl) const\r
 294 {\r
 295     out<<sep(lvl)<<"Charset(INCLUDE"\r
 296         <<", "<<str_<<")\n";\r
 297 }\r
 298 \r
 299 void __Charset::Exclude()\r
 300 {\r
 301     inc_ = 0;\r
 302 }\r
 303 \r
 304 void __Charset::AddChar(int ch)\r
 305 {\r
 306     str_.push_back(ch);\r
 307 }\r
 308 \r
 309 void __Charset::AddRange(int from,int to)\r
 310 {\r
 311     for(;from <= to;++from)\r
 312         str_.push_back(from);\r
 313 }\r
 314 \r
 315 void __Charset::AddRange(__Charset * node)\r
 316 {\r
 317     if(!node)\r
 318         return;\r
 319     unite(*node);\r
 320 }\r
 321 \r
 322 void __Charset::Unique()\r
 323 {\r
 324     inc_ ? unique() : reverse();\r
 325 }\r
 326 \r
 327 void __Charset::unite(__Charset & node)\r
 328 {\r
 329     if(!node.inc_)\r
 330         node.reverse();\r
 331     str_ += node.str_;\r
 332 }\r
 333 \r
 334 void __Charset::reverse()\r
 335 {\r
 336     const int _CHAR_MIN = 32;\r
 337     const int _CHAR_MAX = 126;\r
 338     unique();\r
 339     __DZ_STRING s;\r
 340     s.swap(str_);\r
 341     int c = _CHAR_MIN;\r
 342     size_t i = 0,e = s.size();\r
 343     for(;c <= _CHAR_MAX && i < e;++i){\r
 344         int ch = s[i];\r
 345         if(c < ch)\r
 346             AddRange(c,ch - 1);\r
 347         c = std::max(ch + 1,_CHAR_MIN);\r
 348     }\r
 349     if(c <= _CHAR_MAX)\r
 350         AddRange(c,_CHAR_MAX);\r
 351     inc_ = !inc_;\r
 352 }\r
 353 \r
 354 void __Charset::unique()\r
 355 {\r
 356     if(!str_.empty()){\r
 357         std::sort(str_.begin(),str_.end());\r
 358         str_.erase(std::unique(str_.begin(),str_.end()),str_.end());\r
 359     }\r
 360 }\r
 361 \r
 362 //class __Repeat\r
 363 __Repeat::__Repeat(__NodeBase * node,int ch)\r
 364     : node_(node)\r
 365     , min_(0)\r
 366     , max_(0)\r
 367 {\r
 368     switch(ch){\r
 369         case '?':min_ = 0;max_ = 1;break;\r
 370         case '+':min_ = 1;max_ = INFINITE;break;\r
 371         case '*':min_ = 0;max_ = INFINITE;break;\r
 372         default:;\r
 373     }\r
 374 }\r
 375 \r
 376 __Repeat::__Repeat(__NodeBase * node,int min,int max)\r
 377     : node_(node)\r
 378     , min_(min)\r
 379     , max_(max)\r
 380 {}\r
 381 \r
 382 __Repeat::~__Repeat(){\r
 383     Delete(node_);\r
 384 }\r
 385 \r
 386 __NodeBase * __Repeat::Optimize(__ParseData & pdata)\r
 387 {\r
 388     min_ &= _CLEAR_FLAGS;\r
 389     max_ &= _CLEAR_FLAGS;\r
 390     if(isInfinite()){\r
 391         max_ = min_ + pdata.config_.repeatInfinite;\r
 392         if( max_ > _REPEAT_MAX)\r
 393             max_ = _REPEAT_MAX;\r
 394     }\r
 395     if(!node_ || (min_ > max_) || (!min_ && !max_))\r
 396         return REP_NULL;\r
 397     __NodeBase * r = node_->Optimize(pdata);\r
 398     if(r == REP_NULL)\r
 399         return REP_NULL;\r
 400     else if(r){\r
 401         Delete(node_);\r
 402         node_ = r;\r
 403     }\r
 404     if(1 == max_ && 1 == min_){\r
 405         r = node_;\r
 406         node_ = 0;\r
 407         return r;\r
 408     }\r
 409     max_ -= min_ - 1;\r
 410     return 0;\r
 411 }\r
 412 \r
 413 void __Repeat::RandString(__GenerateData & gdata) const\r
 414 {\r
 415     for(int t = min_ + rand() % max_;t > 0;t--)\r
 416         node_->RandString(gdata);\r
 417     _OSS_OUT("__Repeat");\r
 418 }\r
 419 \r
 420 void __Repeat::Debug(std::ostream & out,int lvl) const\r
 421 {\r
 422     out<<sep(lvl)<<"Repeat["<<min_<<", "<<(min_ + max_ - 1)<<"]\n";\r
 423     ++lvl;\r
 424     if(node_)\r
 425         node_->Debug(out,lvl);\r
 426     else\r
 427         out<<sep(lvl)<<"NULL\n";\r
 428 }\r
 429 \r
 430 int __Repeat::Repeat(int ch)\r
 431 {\r
 432     if(canRepeat()){\r
 433         switch(ch){\r
 434             case '?':min_ |= _NON_GREEDY;return 2;break;\r
 435             case '+':min_ |= _PROSSESSIVE;return 2;break;\r
 436             default:;\r
 437         }\r
 438     }\r
 439     return 0;\r
 440 }\r
 441 \r
 442 //class __Seq\r
 443 __Seq::__Seq(__NodeBase * node)\r
 444     : seq_(1,node)\r
 445 {}\r
 446 \r
 447 __Seq::~__Seq(){\r
 448     for(__Con::const_iterator i = seq_.begin(),e = seq_.end();i != e;++i)\r
 449         Delete(*i);\r
 450 }\r
 451 \r
 452 __NodeBase * __Seq::Optimize(__ParseData & pdata)\r
 453 {\r
 454     if(seq_.empty())\r
 455         return REP_NULL;\r
 456     for(__Con::iterator i = seq_.begin(),e = seq_.end();i != e;++i)\r
 457         if(*i){\r
 458             __NodeBase * r = (*i)->Optimize(pdata);\r
 459             if(r){\r
 460                 Delete(*i);\r
 461                 *i = (r == REP_NULL ? 0 : r);\r
 462             }\r
 463         }\r
 464     seq_.erase(std::remove_if(seq_.begin(),seq_.end(),__IsNull()),seq_.end());\r
 465     if(seq_.empty())\r
 466         return REP_NULL;\r
 467     if(seq_.size() == 1){\r
 468         __NodeBase * r = seq_[0];\r
 469         seq_.clear();\r
 470         return r;\r
 471     }\r
 472     return 0;\r
 473 }\r
 474 \r
 475 void __Seq::RandString(__GenerateData & gdata) const\r
 476 {\r
 477     for(__Con::const_iterator i = seq_.begin(),e = seq_.end();i != e;++i)\r
 478         (*i)->RandString(gdata);\r
 479     _OSS_OUT("__Seq");\r
 480 }\r
 481 \r
 482 void __Seq::Debug(std::ostream & out,int lvl) const\r
 483 {\r
 484     out<<sep(lvl)<<"Seq("<<seq_.size()<<")\n";\r
 485     ++lvl;\r
 486     for(__Con::const_iterator i = seq_.begin(),e = seq_.end();i != e;++i){\r
 487         if(*i)\r
 488             (*i)->Debug(out,lvl);\r
 489         else\r
 490             out<<sep(lvl)<<"NULL\n";\r
 491     }\r
 492 }\r
 493 \r
 494 void __Seq::AppendNode(__NodeBase * node)\r
 495 {\r
 496     if(!seq_.empty())\r
 497         if(__Text * cur = dynamic_cast<__Text *>(node))\r
 498             if(__Text * prev = dynamic_cast<__Text *>(seq_.back())){\r
 499                 *prev += *cur;\r
 500                 Delete(node);\r
 501                 return;\r
 502             }\r
 503     seq_.push_back(node);\r
 504 }\r
 505 \r
 506 //class __Group\r
 507 __Group::__Group(__NodeBase * node,int mark)\r
 508     : node_(node)\r
 509     , mark_(mark)\r
 510 {\r
 511     if(!Tools::IsSubexpMark(mark_))\r
 512         mark_ |= INDEX;\r
 513 }\r
 514 \r
 515 __Group::~__Group()\r
 516 {\r
 517     Delete(node_);\r
 518 }\r
 519 \r
 520 __NodeBase * __Group::Optimize(__ParseData & pdata)\r
 521 {\r
 522     if(!node_ || mark_ == '!')\r
 523         return REP_NULL;\r
 524     __NodeBase * r = node_->Optimize(pdata);\r
 525     if(r == REP_NULL)\r
 526         return REP_NULL;\r
 527     else if(r){\r
 528         Delete(node_);\r
 529         node_ = r;\r
 530     }\r
 531     switch(mark_){\r
 532         case ':':\r
 533         case '=':\r
 534         case '>':{\r
 535             r = node_;\r
 536             node_ = 0;\r
 537             return r;}\r
 538         default:;\r
 539     }\r
 540     mark_ = (mark_ & (INDEX - 1)) - 1;\r
 541     return 0;\r
 542 }\r
 543 \r
 544 void __Group::RandString(__GenerateData & gdata) const\r
 545 {\r
 546     assert(node_);\r
 547     assert(0 <= mark_ && mark_ < MAX_GROUPS);\r
 548     if(mark_ >= gdata.refs_.size())\r
 549         gdata.refs_.resize(mark_ + 1);\r
 550     gdata.refs_.back() = __RefValue(gdata.oss_.str().size(),__DZ_STRING::npos);\r
 551     node_->RandString(gdata);\r
 552     assert(mark_ < gdata.refs_.size());\r
 553     gdata.refs_[mark_].second = gdata.oss_.str().size() - gdata.refs_[mark_].first;\r
 554     _OSS_OUT("__Group");\r
 555 }\r
 556 \r
 557 void __Group::Debug(std::ostream & out,int lvl) const\r
 558 {\r
 559     out<<sep(lvl)<<"Group(";\r
 560     switch(mark_){\r
 561         case ':':out<<"?:";break;\r
 562         case '=':out<<"?=";break;\r
 563         case '!':out<<"?!";break;\r
 564         case '>':out<<"?>";break;\r
 565         default:out<<(mark_ & (INDEX - 1));\r
 566     }\r
 567     out<<")\n";\r
 568     ++lvl;\r
 569     if(node_)\r
 570         node_->Debug(out,lvl);\r
 571     else\r
 572         out<<sep(lvl)<<"NULL\n";\r
 573 }\r
 574 \r
 575 //class __Select\r
 576 __Select::__Select(__NodeBase * node)\r
 577     : sel_(1,node)\r
 578     , sz_(0)\r
 579 {}\r
 580 \r
 581 __Select::~__Select()\r
 582 {\r
 583     for(__Con::const_iterator i = sel_.begin(),e = sel_.end();i != e;++i)\r
 584         Delete(*i);\r
 585 }\r
 586 \r
 587 __NodeBase * __Select::Optimize(__ParseData & pdata)\r
 588 {\r
 589     if(sel_.empty())\r
 590         return REP_NULL;\r
 591     for(__Con::iterator i = sel_.begin(),e = sel_.end();i != e;++i)\r
 592         if(*i){\r
 593             __NodeBase * r = (*i)->Optimize(pdata);\r
 594             if(r){\r
 595                 Delete(*i);\r
 596                 *i = (r == REP_NULL ? 0 : r);\r
 597             }\r
 598         }\r
 599     sel_.erase(std::remove_if(sel_.begin(),sel_.end(),__IsNull()),sel_.end());\r
 600     if(sel_.empty())\r
 601         return REP_NULL;\r
 602     if(sel_.size() == 1){\r
 603         __NodeBase * r = sel_[0];\r
 604         sel_.clear();\r
 605         return r;\r
 606     }\r
 607     sz_ = sel_.size();\r
 608     return 0;\r
 609 }\r
 610 \r
 611 void __Select::RandString(__GenerateData & gdata) const\r
 612 {\r
 613     if(sz_)\r
 614         sel_[rand() % sz_]->RandString(gdata);\r
 615     _OSS_OUT("__Select");\r
 616 }\r
 617 \r
 618 void __Select::Debug(std::ostream & out,int lvl) const\r
 619 {\r
 620     out<<sep(lvl)<<"Select("<<sel_.size()<<")\n";\r
 621     ++lvl;\r
 622     for(__Con::const_iterator i = sel_.begin(),e = sel_.end();i != e;++i)\r
 623         if(*i)\r
 624             (*i)->Debug(out,lvl);\r
 625         else\r
 626             out<<sep(lvl)<<"NULL\n";\r
 627 }\r
 628 \r
 629 void __Select::AppendNode(__NodeBase * node)\r
 630 {\r
 631     sel_.push_back(node);\r
 632 }\r
 633 \r
 634 //class __Ref\r
 635 __Ref::__Ref(int index)\r
 636     : index_(index)\r
 637 {}\r
 638 \r
 639 __NodeBase * __Ref::Optimize(__ParseData & pdata)\r
 640 {\r
 641     --index_;\r
 642     return 0;\r
 643 }\r
 644 \r
 645 void __Ref::RandString(__GenerateData & gdata) const\r
 646 {\r
 647     assert(index_ < gdata.refs_.size());\r
 648     const __RefValue & ref = gdata.refs_[index_];\r
 649     __DZ_STRING str = gdata.oss_.str();\r
 650     if(ref.first < str.size())\r
 651         gdata.oss_<<str.substr(ref.first,ref.second);\r
 652     _OSS_OUT("__Ref("<<index_<<")");\r
 653 }\r
 654 \r
 655 void __Ref::Debug(std::ostream & out,int lvl) const\r
 656 {\r
 657     out<<sep(lvl)<<"Ref("<<index_<<")\n";\r
 658 }\r
 659 \r
 660 //class __CRegxString\r
 661 __CRegxString::__CRegxString()\r
 662     : top_(0)\r
 663 {}\r
 664 \r
 665 void __CRegxString::ParseRegx(const __DZ_STRING & regx,const Config * config)\r
 666 {\r
 667     uninit();\r
 668     regx_ = regx;\r
 669     if(regx_.empty())\r
 670         return;\r
 671     Config def;\r
 672     __ParseData pdata(config ? *config : def);\r
 673     top_ = processSeq(pdata).first;\r
 674     if(!top_)\r
 675         return;\r
 676     __NodeBase * r = top_->Optimize(pdata);\r
 677     if(r){\r
 678         Delete(top_);\r
 679         top_ = (r == __NodeBase::REP_NULL ? 0 : r);\r
 680     }\r
 681     // if(top_)\r
 682     //     srand((unsigned int)time(0));\r
 683     // Changed by Adrian Lita\r
 684 }\r
 685 \r
 686 const __DZ_STRING & __CRegxString::RandString()\r
 687 {\r
 688     str_.clear();\r
 689     if(top_){\r
 690         __DZ_OSTRINGSTREAM oss;\r
 691         __GenerateData gdata(oss);\r
 692         top_->RandString(gdata);\r
 693         str_ = oss.str();\r
 694     }\r
 695     return str_;\r
 696 }\r
 697 \r
 698 void __CRegxString::Debug(std::ostream & out) const{\r
 699     out<<"regx_ : "<<regx_<<"\nstructure :\n";\r
 700     if(top_)\r
 701         top_->Debug(out,0);\r
 702     else\r
 703         out<<"NULL\n";\r
 704 }\r
 705 \r
 706 void __CRegxString::uninit()\r
 707 {\r
 708     if(top_){\r
 709         Delete(top_);\r
 710         top_ = 0;\r
 711     }\r
 712     str_.clear();\r
 713 }\r
 714 \r
 715 __CRegxString::__Ret __CRegxString::processSeq(__ParseData & pdata)\r
 716 {\r
 717     __Ret ret;\r
 718     __NodeBase * cur = 0;\r
 719     bool begin = true;\r
 720     for(const size_t e = regx_.length();pdata.i_ < e;++pdata.i_){\r
 721         int ch = regx_[pdata.i_];\r
 722         if(begin){\r
 723             if(Tools::IsBegin(ch)){\r
 724                 cur = New<__Edge>(ch);\r
 725                 continue;\r
 726             }\r
 727             begin = false;\r
 728         }\r
 729         if(Tools::IsRepeat(ch) && cur){\r
 730             int r = cur->Repeat(ch);\r
 731             if(r){\r
 732                 if(r == 1)\r
 733                     cur = New<__Repeat>(cur,ch);\r
 734                 continue;\r
 735             }\r
 736         }\r
 737         if(Tools::IsRepeatBegin(ch)){\r
 738             cur = processRepeat(cur,pdata);\r
 739             continue;\r
 740         }\r
 741         appendNode(ret.first,cur);\r
 742         ret.second = pdata.inEnds(ch);\r
 743         if(ret.second)\r
 744             return ret;\r
 745         if(Tools::IsSelect(ch))\r
 746             return processSelect(ret.first,pdata);\r
 747         if(Tools::IsEnd(ch))\r
 748             cur = New<__Edge>(ch);\r
 749         else if(Tools::IsAny(ch)){\r
 750              __Charset * set = New<__Charset>("\n",false);\r
 751              set->Unique();\r
 752              cur = set;\r
 753         }else if(Tools::IsSetBegin(ch))\r
 754             cur = processSet(pdata);\r
 755         else if(Tools::IsGroupBegin(ch))\r
 756             cur = processGroup(pdata);\r
 757         else if(Tools::IsSlash(ch))\r
 758             cur = processSlash(true,pdata).first;\r
 759         else\r
 760             cur = New<__Text>(ch);\r
 761     }\r
 762     appendNode(ret.first,cur);\r
 763     return ret;\r
 764 }\r
 765 \r
 766 __CRegxString::__Ret __CRegxString::processSlash(bool bNode,__ParseData & pdata)\r
 767 {\r
 768     ++pdata.i_;\r
 769     __Ret ret((__NodeBase *)0,pdata.i_ < regx_.length() ? Tools::TransSlash(regx_[pdata.i_]) : '\\');\r
 770     __Charset * set = 0;\r
 771     switch(ret.second){\r
 772         case 'd':set = New<__Charset>("0123456789",true);break;\r
 773         case 'D':set = New<__Charset>("0123456789",false);break;\r
 774         case 's':set = New<__Charset>(/*"\f\n\r\v"*/"\t ",true);break;\r
 775         case 'S':set = New<__Charset>(/*"\f\n\r\v"*/"\t ",false);break;\r
 776         case 'w':{   //A-Za-z0-9_\r
 777             set = New<__Charset>();\r
 778             set->AddRange('A','Z');\r
 779             set->AddRange('a','z');\r
 780             set->AddRange('0','9');\r
 781             set->AddChar('_');\r
 782             break;}\r
 783         case 'W':{   //^A-Za-z0-9_\r
 784             set =  New<__Charset>();\r
 785             set->AddRange('A','Z');\r
 786             set->AddRange('a','z');\r
 787             set->AddRange('0','9');\r
 788             set->AddChar('_');\r
 789             set->Exclude();\r
 790             break;}\r
 791         default:;\r
 792     }\r
 793     if(set){\r
 794         set->Unique();\r
 795         ret.first = set;\r
 796     }else if(bNode){\r
 797         if(Tools::IsDigit(ret.second)){\r
 798             int i = ret.second - '0';\r
 799             if(!i)\r
 800                 ret.second = 0;\r
 801             else if(i <= pdata.ref_)\r
 802                 ret.first = New<__Ref>(i);\r
 803         }\r
 804         if(!ret.first)\r
 805             ret.first = New<__Text>(ret.second);\r
 806     }\r
 807     return ret;\r
 808 }\r
 809 \r
 810 __NodeBase * __CRegxString::processSet(__ParseData & pdata)\r
 811 {\r
 812     size_t bak = pdata.i_++;\r
 813     __Charset * ret = New<__Charset>();\r
 814     bool begin = true;\r
 815     int prev = 0;\r
 816     for(const size_t e = regx_.length();pdata.i_ < e;++pdata.i_){\r
 817         int ch = regx_[pdata.i_];\r
 818         if(begin && Tools::IsBegin(ch)){\r
 819             ret->Exclude();\r
 820             begin = false;\r
 821             continue;\r
 822         }\r
 823         if(Tools::IsDash(ch) && prev){\r
 824             int to = 0;\r
 825             if(processRange(to,pdata)){\r
 826                 ret->AddRange(prev,to);\r
 827                 prev = 0;\r
 828                 continue;\r
 829             }\r
 830         }\r
 831         if(prev)\r
 832             ret->AddChar(prev);\r
 833         if(Tools::IsSetEnd(ch)){\r
 834             ret->Unique();\r
 835             return ret;\r
 836         }\r
 837         if(Tools::IsSlash(ch)){\r
 838             __Ret s = processSlash(false,pdata);\r
 839             if(s.first){    //charset\r
 840                 ret->AddRange(dynamic_cast<__Charset *>(s.first));\r
 841                 Delete(s.first);\r
 842                 prev = 0;\r
 843                 continue;\r
 844             }\r
 845             ch = s.second;\r
 846         }\r
 847         prev = ch;\r
 848     }\r
 849     Delete(ret);\r
 850     pdata.i_ = bak;\r
 851     return New<__Text>('[');\r
 852 }\r
 853 \r
 854 __NodeBase * __CRegxString::processGroup(__ParseData & pdata)\r
 855 {\r
 856     int bak = pdata.i_++;\r
 857     int mark = ignoreSubexpMarks(pdata);\r
 858     pdata.ends_.push_back(')');\r
 859     if(!mark)\r
 860         mark = ++pdata.ref_;\r
 861     __Ret ret = processSeq(pdata);\r
 862     pdata.ends_.pop_back();\r
 863     if(ret.second)\r
 864         return New<__Group>(ret.first,mark);\r
 865     Delete(ret.first);\r
 866     pdata.i_ = bak;\r
 867     return New<__Text>('(');\r
 868 }\r
 869 \r
 870 __CRegxString::__Ret __CRegxString::processSelect(__NodeBase * node,__ParseData & pdata)\r
 871 {\r
 872     __Ret ret(New<__Select>(node),0);\r
 873     pdata.ends_.push_back('|');\r
 874     for(const size_t e = regx_.length();pdata.i_ < e;){\r
 875         ++pdata.i_;\r
 876         __Ret r = processSeq(pdata);\r
 877         ret.first->AppendNode(r.first);\r
 878         if(r.second > 1){\r
 879             ret.second = r.second - 1;\r
 880             break;\r
 881         }\r
 882     }\r
 883     pdata.ends_.pop_back();\r
 884     return ret;\r
 885 }\r
 886 \r
 887 __NodeBase * __CRegxString::processRepeat(__NodeBase * node,__ParseData & pdata)\r
 888 {\r
 889     if(node && node->Repeat(0)){\r
 890         size_t bak = pdata.i_++;\r
 891         int min = 0,max = __Repeat::INFINITE;\r
 892         switch(processInt(min,pdata)){\r
 893             case ',':\r
 894                 ++pdata.i_;\r
 895                 if(processInt(max,pdata) == '}')\r
 896                     return New<__Repeat>(node,min,(min < max ? max : min));\r
 897                 break;\r
 898             case '}':\r
 899                 return New<__Repeat>(node,min,min);\r
 900             default:;\r
 901         }\r
 902         pdata.i_ = bak;\r
 903     }\r
 904     return New<__Text>('{');\r
 905 }\r
 906 \r
 907 int __CRegxString::processInt(int & result,__ParseData & pdata)\r
 908 {\r
 909     bool begin = true;\r
 910     for(const size_t e = regx_.length();pdata.i_ < e;++pdata.i_){\r
 911         int ch = regx_[pdata.i_];\r
 912         if(Tools::IsDigit(ch)){\r
 913             ch = Tools::TransDigit(ch);\r
 914             if(begin){\r
 915                 result = ch;\r
 916                 begin = false;\r
 917             }else{\r
 918                 result *= 10;\r
 919                 if(result < 0)\r
 920                     return 0;\r
 921                 result += ch;\r
 922             }\r
 923         }else\r
 924             return ch;\r
 925     }\r
 926     return 0;\r
 927 }\r
 928 \r
 929 bool __CRegxString::processRange(int & result,__ParseData & pdata)\r
 930 {\r
 931     if(++pdata.i_ < regx_.size() && regx_[pdata.i_] != ']'){\r
 932         result = regx_[pdata.i_];\r
 933         return true;\r
 934     }\r
 935     --pdata.i_;\r
 936     return false;\r
 937 }\r
 938 \r
 939 int __CRegxString::ignoreSubexpMarks(__ParseData & pdata)\r
 940 {\r
 941     int ret = 0;\r
 942     if(pdata.i_ + 1 < regx_.size()){\r
 943         ret = Tools::IsSubexpMark(&regx_[pdata.i_]);\r
 944         if(ret)\r
 945             pdata.i_ += 2;\r
 946     }\r
 947     return ret;\r
 948 }\r
 949 \r
 950 NAMESAPCE_END\r