source/regex.cpp

   1 /* $Id$
   2
   3 This file is part of libmspstrings
   4 Copyright © 2007 Mikko Rasa
   5 Distributed under the LGPL
   6 */
   7 #include <stack>
   8 #include <msp/core/except.h>
   9 #include "formatter.h"
  10 #include "regex.h"
  11
  12 using namespace std;
  13
  14 namespace {
  15
  16 /**
  17 Writes an integer to a Regex code string, in little-endian order.
  18 */
  19 template<typename T>
  20 void write_int(T n, Msp::Regex::Code &code)
  21 {
  22         for(unsigned i=0; i<sizeof(T); ++i)
  23                 code+=(n>>i*8)&0xFF;
  24 }
  25
  26 /**
  27 Reads an integer from a Regex code stream, in little-endian order.
  28 */
  29 template<typename T>
  30 T read_int(Msp::Regex::Code::const_iterator &c)
  31 {
  32         T result=0;
  33         for(unsigned i=0; i<sizeof(T); ++i)
  34                 result+=static_cast<unsigned char>(*c++)<<i*8;
  35         return result;
  36 }
  37
  38 }
  39
  40 namespace Msp {
  41
  42 Regex::Regex(const string &expr)
  43 {
  44         n_groups=0;
  45         string::const_iterator iter=expr.begin();
  46         code=compile(expr, iter, n_groups, false);
  47         ++n_groups;
  48 }
  49
  50 RegMatch Regex::match(const string &str) const
  51 {
  52         RegMatch::GroupArray groups(n_groups);
  53
  54         for(string::const_iterator i=str.begin(); i!=str.end(); ++i)
  55                 if(run(str, i, groups))
  56                         return RegMatch(str, groups);
  57
  58         return RegMatch();
  59 }
  60
  61 string Regex::disassemble() const
  62 {
  63         ostringstream ss;
  64
  65         for(Code::const_iterator i=code.begin(); i!=code.end();)
  66         {
  67                 Code::const_iterator j=i;
  68                 Offset offset=i-code.begin();
  69                 string decompiled=disassemble_instruction(i);
  70                 string bytes;
  71                 for(; j!=i; ++j)
  72                         bytes+=format(" %02X", static_cast<int>(*j)&0xFF);
  73                 ss<<Fmt("%3d")<<offset<<':'<<Fmt("%-9s")<<bytes;
  74                 if(bytes.size()>9)
  75                         ss<<"\n"<<Fmt("%15s");
  76                 ss<<"  "<<decompiled<<'\n';
  77         }
  78
  79         return ss.str();
  80 }
  81
  82 Regex::Code Regex::compile(const string &expr, string::const_iterator &iter, unsigned &group, bool branch)
  83 {
  84         bool has_branches=false;
  85         unsigned level=0;
  86         bool escape=false;
  87         string::const_iterator end;
  88         for(end=iter; end!=expr.end(); ++end)
  89         {
  90                 if(escape)
  91                         escape=false;
  92                 else if(*end=='\\')
  93                         escape=true;
  94                 else if(*end=='(')
  95                         ++level;
  96                 else if(*end==')')
  97                 {
  98                         if(level==0)
  99                         {
 100                                 if(group==0)
 101                                         throw InvalidParameterValue("Unexpected )");
 102                                 else
 103                                         break;
 104                         }
 105                         --level;
 106                 }
 107                 else if(*end=='|')
 108                 {
 109                         if(branch)
 110                                 break;
 111                         else if(level==0)
 112                                 has_branches=true;
 113                 }
 114         }
 115
 116         if(level>0)
 117                 throw InvalidParameterValue("Unmatched (");
 118
 119         Code result;
 120
 121         unsigned this_group=group;
 122         if(!branch)
 123         {
 124                 result+=GROUP_BEGIN;
 125                 write_int<Index>(this_group, result);
 126         }
 127
 128         const unsigned jump_size=1+sizeof(Offset);
 129
 130         if(!has_branches)
 131         {
 132                 for(string::const_iterator i=iter; i!=end;)
 133                 {
 134                         Code atom=parse_atom(expr, i, group);
 135
 136                         Count repeat_min=1;
 137                         Count repeat_max=1;
 138                         parse_repeat(i, repeat_min, repeat_max);
 139
 140                         for(unsigned j=0; j<repeat_min; ++j)
 141                                 result+=atom;
 142                         if(repeat_max==numeric_limits<Count>::max())
 143                         {
 144                                 if(repeat_min==0)
 145                                 {
 146                                         result+=ND_JUMP;
 147                                         write_int<Offset>(atom.size()+jump_size, result);
 148                                         result+=atom;
 149                                 }
 150                                 result+=ND_JUMP;
 151                                 write_int<Offset>(-(atom.size()+jump_size), result);
 152                         }
 153                         else if(repeat_max>repeat_min)
 154                         {
 155                                 for(unsigned j=repeat_min; j<repeat_max; ++j)
 156                                 {
 157                                         result+=ND_JUMP;
 158                                         write_int<Offset>((repeat_max-j)*(atom.size()+jump_size)-jump_size, result);
 159                                         result+=atom;
 160                                 }
 161                         }
 162                 }
 163         }
 164         else
 165         {
 166                 list<Code> branches;
 167                 for(string::const_iterator i=iter;;)
 168                 {
 169                         branches.push_back(compile(expr, i, group, true));
 170                         if(i==end)
 171                                 break;
 172                         ++i;
 173                 }
 174
 175                 unsigned n_branches=branches.size();
 176
 177                 Offset offset=(n_branches-1)*jump_size+branches.front().size();
 178                 for(list<Code>::iterator i=++branches.begin(); i!=branches.end(); ++i)
 179                 {
 180                         result+=ND_JUMP;
 181                         write_int<Offset>(offset, result);
 182                         offset+=i->size();
 183                 }
 184
 185                 for(list<Code>::iterator i=branches.begin(); i!=branches.end();)
 186                 {
 187                         result+=*i;
 188                         offset-=i->size()+jump_size;
 189                         ++i;
 190                         if(i!=branches.end())
 191                         {
 192                                 result+=JUMP;
 193                                 write_int<Offset>(offset, result);
 194                         }
 195                 }
 196         }
 197
 198         if(!branch)
 199         {
 200                 result+=GROUP_END;
 201                 write_int<Index>(this_group, result);
 202         }
 203
 204         iter=end;
 205
 206         return result;
 207 }
 208
 209 Regex::Code Regex::parse_atom(const string &expr, string::const_iterator &i, unsigned &group)
 210 {
 211         Code result;
 212
 213         if(i==expr.end())
 214                 return result;
 215
 216         bool flag=false;
 217         if(*i=='\\')
 218         {
 219                 if(++i==expr.end())
 220                         throw InvalidParameterValue("Stray backslash");
 221                 flag=true;
 222         }
 223
 224         if(!flag)
 225         {
 226                 if(*i=='*' || *i=='{' || *i=='}' || *i=='+' || *i=='?' || *i=='|' || *i==')')
 227                         throw InvalidParameterValue("Invalid atom");
 228                 else if(*i=='[')
 229                         return parse_brackets(expr, i);
 230                 else if(*i=='.')
 231                         result+=MATCH_ANY;
 232                 else if(*i=='^')
 233                         result+=MATCH_BEGIN;
 234                 else if(*i=='$')
 235                         result+=MATCH_END;
 236                 else if(*i=='(')
 237                 {
 238                         ++group;
 239                         result=compile(expr, ++i, group, false);
 240                 }
 241                 else
 242                         flag=true;
 243         }
 244
 245         if(flag)
 246         {
 247                 result+=MATCH_CHAR;
 248                 result+=*i;
 249         }
 250
 251         ++i;
 252
 253         return result;
 254 }
 255
 256 bool Regex::parse_repeat(string::const_iterator &i, Count &rmin, Count &rmax)
 257 {
 258         if(*i!='*' && *i!='+' && *i!='?' && *i!='{')
 259                 return false;
 260
 261         if(*i=='*' || *i=='+')
 262                 rmax=numeric_limits<Count>::max();
 263         if(*i=='*' || *i=='?')
 264                 rmin=0;
 265         if(*i=='{')
 266         {
 267                 rmin=0;
 268                 for(++i; isdigit(*i); ++i)
 269                         rmin=rmin*10+(*i-'0');
 270
 271                 if(*i==',')
 272                 {
 273                         ++i;
 274                         if(*i!='}')
 275                         {
 276                                 rmax=0;
 277                                 for(; isdigit(*i); ++i)
 278                                         rmax=rmax*10+(*i-'0');
 279                                 if(rmax<rmin)
 280                                         throw InvalidParameterValue("Invalid bound");
 281                         }
 282                         else
 283                                 rmax=numeric_limits<Count>::max();
 284                 }
 285                 else
 286                         rmax=rmin;
 287                 if(*i!='}')
 288                         throw InvalidParameterValue("Invalid bound");
 289         }
 290
 291         ++i;
 292
 293         return true;
 294 }
 295
 296 Regex::Code Regex::parse_brackets(const string &str, string::const_iterator &iter)
 297 {
 298         Code result;
 299
 300         ++iter;
 301         bool neg=false;
 302         if(*iter=='^')
 303         {
 304                 neg=true;
 305                 ++iter;
 306         }
 307
 308         string::const_iterator end=iter;
 309         for(; (end!=str.end() && (end==iter || *end!=']')); ++end);
 310         if(end==str.end())
 311                 throw InvalidParameterValue("Unmatched '['");
 312
 313         uint8_t mask[32]={0};
 314         unsigned type=0;
 315         bool range=false;
 316         unsigned char first=0, last=0;
 317         for(string::const_iterator i=iter; i!=end; ++i)
 318         {
 319                 unsigned char c=*i;
 320                 if(range)
 321                 {
 322                         last=c;
 323                         for(unsigned j=first; j<=c; ++j)
 324                                 mask[j>>3]|=1<<(j&7);
 325                         range=false;
 326                         if(type<2)
 327                                 type=2;
 328                 }
 329                 else if(c=='-' && i!=iter && end-i>1)
 330                         range=true;
 331                 else
 332                 {
 333                         first=c;
 334                         mask[c>>3]|=1<<(c&7);
 335                         if(type==0)
 336                                 type=1;
 337                         else
 338                                 type=3;
 339                 }
 340         }
 341
 342         if(neg)
 343                 result+=NEGATE;
 344
 345         if(type==1)
 346         {
 347                 result+=MATCH_CHAR;
 348                 result+=first;
 349         }
 350         else if(type==2)
 351         {
 352                 result+=MATCH_RANGE;
 353                 result+=first;
 354                 result+=last;
 355         }
 356         else
 357         {
 358                 result+=MATCH_MASK;
 359                 result.append(reinterpret_cast<char *>(mask), 32);
 360         }
 361
 362         iter=end;
 363         ++iter;
 364
 365         return result;
 366 }
 367
 368 bool Regex::run(const string &str, const string::const_iterator &begin, RegMatch::GroupArray &groups) const
 369 {
 370         bool result=false;
 371         list<RunContext> ctx;
 372         ctx.push_back(RunContext());
 373         ctx.front().citer=code.begin();
 374         ctx.front().groups.resize(groups.size());
 375
 376         for(string::const_iterator i=begin;;)
 377         {
 378                 int c;
 379                 if(i!=str.end())
 380                         c=static_cast<unsigned char>(*i);
 381                 else
 382                         c=-1;
 383
 384                 for(list<RunContext>::iterator j=ctx.begin(); j!=ctx.end();)
 385                 {
 386                         bool terminate=false;
 387                         bool negate_match=false;
 388                         for(; j->citer!=code.end();)
 389                         {
 390                                 Instruction instr=static_cast<Instruction>(*j->citer++);
 391
 392                                 if(instr==NEGATE)
 393                                         negate_match=true;
 394                                 else if(instr==JUMP)
 395                                 {
 396                                         Offset offset=read_int<Offset>(j->citer);
 397                                         j->citer+=offset;
 398                                 }
 399                                 else if(instr==ND_JUMP)
 400                                 {
 401                                         Offset offset=read_int<Offset>(j->citer);
 402                                         ctx.push_back(*j);
 403                                         ctx.back().citer+=offset;
 404                                 }
 405                                 else if(instr==GROUP_BEGIN)
 406                                 {
 407                                         Index n=read_int<Index>(j->citer);
 408                                         if(!j->groups[n].match)
 409                                                 j->groups[n].begin=i-str.begin();
 410                                 }
 411                                 else if(instr==GROUP_END)
 412                                 {
 413                                         Index n=read_int<Index>(j->citer);
 414                                         if(!j->groups[n].match)
 415                                         {
 416                                                 j->groups[n].match=true;
 417                                                 j->groups[n].end=i-str.begin();
 418                                                 j->groups[n].length=j->groups[n].end-j->groups[n].begin;
 419                                         }
 420
 421                                         if(n==0)
 422                                         {
 423                                                 result=true;
 424                                                 bool better=false;
 425                                                 for(unsigned k=0; (k<groups.size() && !better); ++k)
 426                                                 {
 427                                                         better=group_compare(j->groups[k], groups[k]);
 428                                                         if(group_compare(groups[k], j->groups[k]))
 429                                                                 break;
 430                                                 }
 431                                                 if(better)
 432                                                         groups=j->groups;
 433                                         }
 434                                 }
 435                                 else
 436                                 {
 437                                         bool match_result=false;
 438                                         bool input_consumed=false;
 439                                         if(instr==MATCH_BEGIN)
 440                                                 match_result=(i==str.begin());
 441                                         else if(instr==MATCH_END)
 442                                                 match_result=(i==str.end());
 443                                         else if(instr==MATCH_CHAR)
 444                                         {
 445                                                 match_result=(c==*j->citer++);
 446                                                 input_consumed=true;
 447                                         }
 448                                         else if(instr==MATCH_RANGE)
 449                                         {
 450                                                 unsigned char first=*j->citer++;
 451                                                 unsigned char last=*j->citer++;
 452                                                 match_result=(c>=first && c<=last);
 453                                                 input_consumed=true;
 454                                         }
 455                                         else if(instr==MATCH_MASK)
 456                                         {
 457                                                 uint8_t mask[32];
 458                                                 for(unsigned k=0; k<32; ++k)
 459                                                         mask[k]=*j->citer++;
 460                                                 match_result=mask[c>>3]&(1<<(c&7));
 461                                                 input_consumed=true;
 462                                         }
 463                                         else if(instr==MATCH_ANY)
 464                                         {
 465                                                 match_result=true;
 466                                                 input_consumed=true;
 467                                         }
 468                                         else
 469                                                 throw Exception("Invalid instruction");
 470
 471                                         if(match_result==negate_match)
 472                                                 terminate=true;
 473                                         negate_match=false;
 474
 475                                         if(input_consumed || terminate)
 476                                                 break;
 477                                 }
 478                         }
 479
 480                         if(terminate || j->citer==code.end())
 481                                 j=ctx.erase(j);
 482                         else
 483                                 ++j;
 484                 }
 485
 486                 if(i==str.end() || ctx.empty())
 487                         break;
 488                 ++i;
 489         }
 490
 491         return result;
 492 }
 493
 494 bool Regex::group_compare(const RegMatch::Group &g1, const RegMatch::Group &g2) const
 495 {
 496         if(!g1.match)
 497                 return false;
 498
 499         // Any match is better than no match
 500         if(!g2.match)
 501                 return true;
 502
 503         // Earlier match is better
 504         if(g1.begin<g2.begin)
 505                 return true;
 506         if(g2.begin>g2.begin)
 507                 return false;
 508
 509         // Longer match at same position is better
 510         return g1.end>g2.end;
 511 }
 512
 513 string Regex::disassemble_instruction(Code::const_iterator &i) const
 514 {
 515         Instruction instr=static_cast<Instruction>(*i++);
 516
 517         ostringstream result;
 518         switch(instr)
 519         {
 520         case JUMP:
 521                 {
 522                         Offset offset=read_int<Offset>(i);
 523                         result<<"JUMP "<<Fmt("%+d")<<offset<<" ("<<Fmt("%d")<<i-code.begin()+offset<<')';
 524                 }
 525                 break;
 526         case ND_JUMP:
 527                 {
 528                         Offset offset=read_int<Offset>(i);
 529                         result<<"ND_JUMP "<<Fmt("%+d")<<offset<<" ("<<Fmt("%d")<<i-code.begin()+offset<<')';
 530                 }
 531                 break;
 532         case GROUP_BEGIN:
 533                 result<<"GROUP_BEGIN "<<read_int<Index>(i);
 534                 break;
 535         case GROUP_END:
 536                 result<<"GROUP_END "<<read_int<Index>(i);
 537                 break;
 538         case NEGATE:
 539                 result<<"NEGATE";
 540                 break;
 541         case MATCH_BEGIN:
 542                 result<<"MATCH_BEGIN";
 543                 break;
 544         case MATCH_END:
 545                 result<<"MATCH_END";
 546                 break;
 547         case MATCH_CHAR:
 548                 {
 549                         char c=*i++;
 550                         result<<"MATCH_CHAR ";
 551                         if(c>=0x20 && c<=0x7E)
 552                                 result<<'\''<<c<<'\'';
 553                         else
 554                                 result<<(static_cast<int>(c)&0xFF);
 555                 }
 556                 break;
 557         case MATCH_RANGE:
 558                 result<<"MATCH_RANGE "<<(static_cast<int>(*i++)&0xFF);
 559                 result<<'-'<<(static_cast<int>(*i++)&0xFF);
 560                 break;
 561         case MATCH_MASK:
 562                 result<<"MATCH_MASK";
 563                 for(unsigned j=0; j<32; ++j)
 564                         result<<' '<<Fmt("%02X")<<(static_cast<int>(*i++)&0xFF);
 565                 break;
 566         case MATCH_ANY:
 567                 result<<"MATCH_ANY";
 568                 break;
 569         default:
 570                 result<<"UNKNOWN "<<instr;
 571         }
 572
 573         return result.str();
 574 }
 575
 576 } // namespace Msp