开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 游戏 > 模拟服务器 > 查看源码
Regexp.cpp
资源名称：SwordOnline.rar　[点击查看]
上传用户：dzyhzl
上传日期：2019-04-29
资源大小：56270k
文件大小：45k
源码类别：

模拟服务器

开发平台：

C/C++

Regexp.cpp：源码内容
  1. // Win32 porting notes.
  3. #if defined( _MBCS )
  4. //#pragma message( __FILEINFO__ "This code is broken under _MBCS, " 
  5. //  "see the comments at the top of this file." )
  6. #endif //_MBCS
  7. //
  8. //
  9. // In case this isn't obvious from the later comments this is an ALTERED
  10. // version of the software. If you like my changes then cool, but nearly
  11. // all of the functionality here is derived from Henry Spencer's original
  12. // work.
  13. //
  14. // This code should work correctly under both _SBCS and _UNICODE, I did
  15. // start working on making it work with _MBCS but gave up after a while
  16. // since I don't need this particular port and it's not going to be as
  17. // straight forward as the other two.
  18. //
  19. // The problem stems from the compiled program being stored as TCHARS,
  20. // the individual items need to be wide enough to hold whatever character
  21. // is thrown at them, but currently they are accessed as an array of
  22. // whatever size integral type is appropriate.  _MBCS would cause this
  23. // to be char, but at times it would need to be larger.  This would
  24. // require making the program be an array of short with the appropriate
  25. // conversions used everywhere.  Certainly it's doable, but it's a pain.
  26. // What's worse is that the current code will compile and run under _MBCS,
  27. // only breaking when it gets wide characters thrown against it.
  28. //
  29. // I've marked at least one bit of code with #pragma messages, I may not
  30. // get all of them, but they should be a start
  31. //
  32. // Guy Gascoigne - Piggford (ggp@bigfoot.com) Friday, February 27, 1998
  35. // regcomp and regexec -- regsub and regerror are elsewhere
  36. // @(#)regexp.c 1.3 of 18 April 87
  37. //
  38. // Copyright (c) 1986 by University of Toronto.
  39. // Written by Henry Spencer.  Not derived from licensed software.
  40. //
  41. // Permission is granted to anyone to use this software for any
  42. // purpose on any computer system, and to redistribute it freely,
  43. // subject to the following restrictions:
  44. //
  45. // 1. The author is not responsible for the consequences of use of
  46. // this software, no matter how awful, even if they arise
  47. // from defects in it.
  48. //
  49. // 2. The origin of this software must not be misrepresented, either
  50. // by explicit claim or by omission.
  51. //
  52. // 3. Altered versions must be plainly marked as such, and must not
  53. // be misrepresented as being the original software.
  54. // *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  55. // *** hoptoad!gnu, on 27 Dec 1986, to add < and > for word-matching
  56. // *** as in BSD grep and ex.
  57. // *** THIS IS AN ALTERED VERSION.  It was altered by John Gilmore,
  58. // *** hoptoad!gnu, on 28 Dec 1986, to optimize characters quoted with .
  59. // *** THIS IS AN ALTERED VERSION.  It was altered by James A. Woods,
  60. // *** ames!jaw, on 19 June 1987, to quash a regcomp() redundancy.
  61. // *** THIS IS AN ALTERED VERSION.  It was altered by Geoffrey Noer,
  62. // *** THIS IS AN ALTERED VERSION.  It was altered by Guy Gascoigne - Piggford
  63. // *** guy@wyrdrune.com, on 15 March 1998, porting it to C++ and converting
  64. // *** it to be the engine for the Regexp class
  65. //
  66. // Beware that some of this code is subtly aware of the way operator
  67. // precedence is structured in regular expressions.  Serious changes in
  68. // regular-expression syntax might require a total rethink.
  70. #include "stdafx.h"
  71. #include "regexp.h"
  72. #include "malloc.h"
  74. // The first byte of the regexp internal "program" is actually this magic
  75. // number; the start node begins in the second byte.
  77. const TCHAR MAGIC = ((TCHAR)'234');
  79. //#define new DEBUG_NEW
  81. #pragma warning( disable : 4711 ) // automatic inline selected
  83. // The "internal use only" fields in regexp.h are present to pass info from
  84. // compile to execute that permits the execute phase to run lots faster on
  85. // simple cases.  They are:
  86. //
  87. // regstart char that must begin a match; '' if none obvious
  88. // reganch is the match anchored (at beginning-of-line only)?
  89. // regmust string (pointer into program) that match must include, or NULL
  90. // regmlen length of regmust string
  91. //
  92. // Regstart and reganch permit very fast decisions on suitable starting
  93. // points for a match, cutting down the work a lot.  Regmust permits fast
  94. // rejection of lines that cannot possibly match.  The regmust tests are
  95. // costly enough that regcomp() supplies a regmust only if the
  96. // r.e. contains something potentially expensive (at present, the only
  97. // such thing detected is * or + at the start of the r.e., which can
  98. // involve a lot of backup).  Regmlen is supplied because the test in
  99. // regexec() needs it and regcomp() is computing it anyway.
  101. // Structure for regexp "program".  This is essentially a linear encoding
  102. // of a nondeterministic finite-state machine (aka syntax charts or
  103. // "railroad normal form" in parsing technology).  Each node is an opcode
  104. // plus a "next" pointer, possibly plus an operand.  "Next" pointers of
  105. // all nodes except BRANCH implement concatenation; a "next" pointer with
  106. // a BRANCH on both ends of it is connecting two alternatives.  (Here we
  107. // have one of the subtle syntax dependencies: an individual BRANCH (as
  108. // opposed to a collection of them) is never concatenated with anything
  109. // because of operator precedence.)  The operand of some types of node is
  110. // a literal string; for others, it is a node leading into a sub-FSM.  In
  111. // particular, the operand of a BRANCH node is the first node of the
  112. // branch.  (NB this is *not* a tree structure: the tail of the branch
  113. // connects to the thing following the set of BRANCHes.)  The opcodes
  114. // are:
  116. enum {
  117. //  definition number opnd? meaning
  118. END = 0, // no End of program.
  119. BOL = 1, // no Match beginning of line.
  120. EOL = 2, // no Match end of line.
  121. ANY = 3, // no Match any character.
  122. ANYOF = 4, // str Match any of these.
  123. ANYBUT = 5, // str Match any but one of these.
  124. BRANCH = 6, // node Match this, or the next..&.
  125. BACK = 7, // no "next" ptr points backward.
  126. EXACTLY = 8, // str Match this string.
  127. NOTHING = 9, // no Match empty string.
  128. STAR = 10, // node Match this 0 or more times.
  129. PLUS = 11, // node Match this 1 or more times.
  130. WORDA = 12, // no Match "" at wordchar, where prev is nonword
  131. WORDZ = 13, // no Match "" at nonwordchar, where prev is word
  132. OPEN = 20, // no Sub-RE starts here.
  133. // OPEN+1 is number 1, etc.
  134. CLOSE = 30 // no Analogous to OPEN.
  135. };
  137. // Opcode notes:
  138. //
  139. // BRANCH The set of branches constituting a single choice are hooked
  140. // together with their "next" pointers, since precedence prevents
  141. // anything being concatenated to any individual branch.  The
  142. // "next" pointer of the last BRANCH in a choice points to the
  143. // thing following the whole choice.  This is also where the
  144. // final "next" pointer of each individual branch points; each
  145. // branch starts with the operand node of a BRANCH node.
  146. //
  147. // BACK Normal "next" pointers all implicitly point forward; BACK
  148. // exists to make loop structures possible.
  149. //
  150. // STAR,PLUS '?', and complex '*' and '+', are implemented as circular
  151. // BRANCH structures using BACK.  Simple cases (one character
  152. // per match) are implemented with STAR and PLUS for speed
  153. // and to minimize recursive plunges.
  154. //
  155. // OPEN,CLOSE ...are numbered at compile time.
  157. // A node is one char of opcode followed by two chars of "next" pointer.
  158. // "Next" pointers are stored as two 8-bit pieces, high order first.  The
  159. // value is a positive offset from the opcode of the node containing it.
  160. // An operand, if any, simply follows the node.  (Note that much of the
  161. // code generation knows about this implicit relationship.)
  162. //
  163. // Using two bytes for the "next" pointer is vast overkill for most things,
  164. // but allows patterns to get big without disasters.
  167. enum
  168. {
  169. REGERR_SENTINEL_VALUE = 0,
  170. REGERR_NULLARG = 1, REGERR_CORRUPTED, REGERR_CORRUPTION, REGERR_CORRUPTED_POINTERS,
  171. REGERR_BAD_REGREPEAT, REGERR_CORRUPTED_OPCODE, REGERR_NULL_TO_REGSUB,
  172. REGERR_DAMAGED_REGEXP_REGSUB, REGERR_DAMAGED_MATCH_STRING, REGERR_NULL_TO_REGCOMP,
  173. REGERR_TO_BIG, REGERR_TO_MANY_PAREN, REGERR_UNTERMINATED_PAREN, REGERR_UNMATCHED_PAREN,
  174. REGERR_INTERNAL_ERROR_JUNK, REGERR_OP_COULD_BE_EMPTY, REGERR_NESTED_OP, REGERR_INVALID_RANGE,
  175. REGERR_UNMATCHED_BRACE, REGERR_INTERNAL_UNEXPECTED_CHAR, REGERR_OP_FOLLOWS_NOTHING,
  176. REGERR_TRAILING_ESC, REGERR_INTERNAL_STRSCSPN, REGERR_NO_REGEXP
  177. };
  179. struct regErr
  180. {
  181. int m_id;
  182. LPCTSTR m_err;
  183. } errors[] = {
  184. { REGERR_NULLARG, _T( "NULL argument to regexec" ) },
  185. { REGERR_CORRUPTED, _T( "corrupted regexp" ) },
  186. { REGERR_CORRUPTION, _T( "regexp corruption" ) },
  187. { REGERR_CORRUPTED_POINTERS, _T( "corrupted pointers" ) },
  188. { REGERR_BAD_REGREPEAT, _T( "internal error: bad call of regrepeat" ) },
  189. { REGERR_CORRUPTED_OPCODE, _T( "corrupted opcode" ) },
  190. { REGERR_NULL_TO_REGSUB, _T( "NULL parm to regsub" ) },
  191. { REGERR_DAMAGED_REGEXP_REGSUB, _T( "damaged regexp fed to regsub" ) },
  192. { REGERR_DAMAGED_MATCH_STRING, _T( "damaged match string" ) },
  193. { REGERR_NULL_TO_REGCOMP, _T( "NULL argument to regcomp" ) },
  194. { REGERR_TO_BIG, _T( "regexp too big" ) },
  195. { REGERR_TO_MANY_PAREN, _T( "too many ()" ) },
  196. { REGERR_UNTERMINATED_PAREN, _T( "unterminated ()" ) },
  197. { REGERR_UNMATCHED_PAREN, _T( "unmatched ()" ) },
  198. { REGERR_INTERNAL_ERROR_JUNK, _T( "internal error: junk on end" ) },
  199. { REGERR_OP_COULD_BE_EMPTY, _T( "*+ operand could be empty" ) },
  200. { REGERR_NESTED_OP, _T( "nested *?+" ) },
  201. { REGERR_INVALID_RANGE, _T( "invalid [] range" ) },
  202. { REGERR_UNMATCHED_BRACE, _T( "unmatched []" ) },
  203. { REGERR_INTERNAL_UNEXPECTED_CHAR, _T( "internal error: \0|) unexpected" ) },
  204. { REGERR_OP_FOLLOWS_NOTHING, _T( "?+* follows nothing" ) },
  205. { REGERR_TRAILING_ESC, _T( "trailing \" ) },
  206. { REGERR_INTERNAL_STRSCSPN, _T( "internal error: strcspn 0" ) },
  207. { REGERR_NO_REGEXP, _T( "NULL regexp" ) },
  208. { REGERR_SENTINEL_VALUE, _T( "Unknown error") } // must be last value
  209. };
  211. // Flags to be passed up and down.
  213. enum {
  214. HASWIDTH = 01, // Known never to match null string.
  215. SIMPLE = 02, // Simple enough to be STAR/PLUS operand.
  216. SPSTART = 04, // Starts with * or +.
  217. WORST = 0 // Worst case.
  218. };
  220. ///////////////////////////////////////////////////////////////////////////////
  222. class CRegErrorHandler
  223. {
  224. friend Regexp;
  225. mutable CString m_szError;
  226. static LPCTSTR FindErr( int id );
  227. protected:
  228. void ClearErrorString() const;
  229. void regerror( LPCTSTR s ) const;
  230. void regerror( int id ) const;
  231. public:
  232. CRegErrorHandler() { }
  233. CRegErrorHandler( const CRegErrorHandler & reh ) : m_szError( reh.m_szError ) {}
  235. const CString & GetErrorString() const;
  236. };
  238. void CRegErrorHandler::regerror( LPCTSTR s ) const
  239. {
  240. //TRACE1( "regerror: %sn", s );
  241. m_szError = s;
  242. }
  244. void CRegErrorHandler::regerror( int id ) const
  245. {
  246. regerror( FindErr( id ) );
  247. }
  249. const CString & CRegErrorHandler::GetErrorString() const
  250. {
  251. return m_szError;
  252. }
  254. void CRegErrorHandler::ClearErrorString() const
  255. {
  256. m_szError.resize(0);
  257. }
  259. LPCTSTR CRegErrorHandler::FindErr( int id )
  260. {
  261. for ( struct regErr * perr = errors; perr->m_id != REGERR_SENTINEL_VALUE; perr++ )
  262. if ( perr->m_id == id )
  263. return perr->m_err;
  265. return perr->m_err; // since we've fallen off the array, perr->m_id == 0
  266. }
  268. ///////////////////////////////////////////////////////////////////////////////
  270. // All of the functions required to directly access the 'program'
  271. class CRegProgramAccessor : public CRegErrorHandler
  272. {
  273. public:
  274. static inline TCHAR OP( LPTSTR p )
  275. {
  276. return (*(p));
  277. }
  278. static inline LPTSTR OPERAND( LPTSTR p )
  279. {
  280. return p + 3;
  281. }
  282. static inline LPTSTR regnext( LPTSTR p )
  283. {
  284. const short &offset = *((short*)(p+1));
  286. if (offset == 0)
  287. return(NULL);
  289. return((OP(p) == BACK) ? p-offset : p+offset);
  290. }
  291. #ifdef _RE_DEBUG
  292. LPTSTR CRegProgramAccessor::regprop( LPTSTR op );
  293. #endif
  294. };
  296. ///////////////////////////////////////////////////////////////////////////////
  298. // The internal interface to the regexp, wrapping the compilation as well as the
  299. // execution of the regexp (matching)
  301. class regexp : public CRegProgramAccessor
  302. {
  303. friend class CRegExecutor;
  304. friend class Regexp;
  306. int m_programSize;
  307. LPTSTR startp[Regexp::NSUBEXP];
  308. LPTSTR endp[Regexp::NSUBEXP];
  309. TCHAR regstart; // Internal use only.
  310. TCHAR reganch; // Internal use only.
  311. LPTSTR regmust; // Internal use only.
  312. int regmlen; // Internal use only.
  313. LPTSTR program;
  315. bool status;
  316. int count; // used by Regexp to manage the reference counting of regexps
  317. int numSubs;
  318. public:
  320. regexp( LPCTSTR exp, BOOL iCase );
  321. regexp( const regexp & r );
  322. ~regexp();
  324. void ignoreCase( const TCHAR * in, TCHAR * out );
  326. bool regcomp( LPCTSTR exp );
  327. bool regexec( LPCTSTR string );
  328. bool Status() const { return status; }
  330. CString GetReplaceString( const TCHAR* sReplaceExp ) const;
  332. regexp * getCopy();
  334. #ifdef _RE_DEBUG
  335. void  regdump();
  336. #endif
  338. #ifdef _DEBUG
  339. CString m_originalPattern;
  340. CString m_modifiedPattern;
  341. #endif
  342. };
  344. ///////////////////////////////////////////////////////////////////////////////
  345. // Compile / Validate the regular expression - ADT
  347. class CRegCompilerBase : public CRegProgramAccessor
  348. {
  349. public:
  350. CRegCompilerBase( LPCTSTR parse );
  352. LPTSTR reg(int paren, int *flagp);
  353. protected:
  354. LPTSTR regparse; // Input-scan pointer. 
  355. int regnpar; // () count. 
  357. LPTSTR regbranch(int *flagp);
  358. LPTSTR regpiece(int *flagp);
  359. LPTSTR regatom(int *flagp);
  360. inline bool ISREPN( TCHAR c ) { return ((c) == '*' || (c) == '+' || (c) == '?'); }
  362. virtual void regc(int c) = 0;
  363. virtual LPTSTR regnode(int op) = 0;
  364. virtual void reginsert(TCHAR op, LPTSTR opnd) = 0;
  365. virtual void regtail(LPTSTR p, LPTSTR val) = 0;
  366. virtual void regoptail(LPTSTR p, LPTSTR val) = 0;
  367. };
  369. ///////////////////////////////////////////////////////////////////////////////
  370. // First pass over the expression, testing for validity and returning the 
  371. // program size
  373. class CRegValidator : public CRegCompilerBase
  374. {
  375. public:
  376. CRegValidator( LPCTSTR parse );
  378. inline long Size() const { return regsize; }
  379. private:
  380. long regsize; // Code size. 
  381. TCHAR regdummy[3]; // NOTHING, 0 next ptr 
  382. protected:
  383. LPTSTR regnode(int) { regsize += 3; return regdummy; }
  384. void regc(int) { regsize++; }
  385. void reginsert(TCHAR, LPTSTR) { regsize += 3; }
  386. void regtail(LPTSTR, LPTSTR) { return; }
  387. void regoptail(LPTSTR, LPTSTR) { return; }
  388. };
  390. ///////////////////////////////////////////////////////////////////////////////
  391. // Second pass, actually generating the program
  393. class CRegCompiler : public CRegCompilerBase
  394. {
  395. public:
  396. CRegCompiler( LPCTSTR parse, LPTSTR prog );
  397. private:
  398. LPTSTR regcode;
  399. protected:
  400. // regc - emit (if appropriate) a byte of code
  401. void regc(int b)
  402. {
  403. *regcode++ = (TCHAR)b;
  404. }
  405. LPTSTR regnode(int op);
  406. void reginsert(TCHAR op, LPTSTR opnd);
  407. void regtail(LPTSTR p, LPTSTR val);
  408. void regoptail(LPTSTR p, LPTSTR val);
  409. };
  411. // regnode - emit a node
  412. LPTSTR CRegCompiler::regnode(int op)
  413. {
  414. LPTSTR const ret = regcode;
  416. LPTSTR ptr = ret;
  417. *ptr++ = (TCHAR)op;
  418. *ptr++ = ''; // Null next pointer. 
  419. *ptr++ = '';
  420. regcode = ptr;
  422. return(ret);
  423. }
  425. // reginsert - insert an operator in front of already-emitted operand
  426. //
  427. // Means relocating the operand.
  428. void CRegCompiler::reginsert(TCHAR op, LPTSTR opnd)
  429. {
  430. LPTSTR place;
  432. (void) memmove(opnd+3, opnd, (size_t)((regcode - opnd)*sizeof(TCHAR)));
  433. regcode += 3;
  435. place = opnd; // Op node, where operand used to be.
  436. *place++ = op;
  437. *place++ = '';
  438. *place++ = '';
  439. }
  441. // regtail - set the next-pointer at the end of a node chain
  442. void CRegCompiler::regtail(LPTSTR p, LPTSTR val)
  443. {
  444. LPTSTR scan;
  445. LPTSTR temp;
  447. // Find last node. 
  448. for (scan = p; (temp = regnext(scan)) != NULL; scan = temp)
  449. continue;
  451. *((short *)(scan+1)) = (short)((OP(scan) == BACK) ? scan - val : val - scan);
  452. }
  454. // regoptail - regtail on operand of first argument; nop if operandless
  455. void CRegCompiler::regoptail(LPTSTR p, LPTSTR val)
  456. {
  457. // "Operandless" and "op != BRANCH" are synonymous in practice. 
  458. if (OP(p) == BRANCH)
  459. regtail(OPERAND(p), val);
  460. }
  462. ///////////////////////////////////////////////////////////////////////////////
  464. CRegCompilerBase::CRegCompilerBase( LPCTSTR parse )
  465. : regparse( (LPTSTR)parse ),
  466. regnpar(1)
  467. {
  468. }
  470. CRegValidator::CRegValidator( LPCTSTR parse )
  471. : CRegCompilerBase( parse ),
  472. regsize(0)
  473. {
  474. regc(MAGIC);
  475. regdummy[0] = NOTHING;
  476. regdummy[1] = regdummy[2] = 0;
  477. }
  479. CRegCompiler::CRegCompiler( LPCTSTR parse, LPTSTR prog )
  480. : CRegCompilerBase( parse ),
  481. regcode(prog)
  482. {
  483. regc(MAGIC);
  484. }
  486. ///////////////////////////////////////////////////////////////////////////////
  488. regexp::regexp( LPCTSTR exp, BOOL iCase )
  489. : regstart(0),
  490. reganch(0),
  491. regmust(0),
  492. regmlen(0),
  493. program(0),
  494. m_programSize(0)
  495. {
  496. #if _DEBUG
  497. m_originalPattern = exp; // keep a version of the pattern for debugging
  498. #endif
  500. if ( iCase )
  501. {
  502. TCHAR * out = new TCHAR[(_tcslen( exp ) * 4) + 1];
  503. ignoreCase( exp, out );
  505. #if _DEBUG
  506. m_modifiedPattern = out; // and the modified version if there is one
  507. #endif
  508. status = regcomp( out );
  509. delete [] out;
  510. }
  511. else
  512. status = regcomp( exp );
  514. count = numSubs = 0;
  515. }
  517. regexp::regexp( const regexp & orig )
  518. : regstart(orig.regstart),
  519. reganch(orig.reganch),
  520. regmlen(orig.regmlen),
  521. m_programSize(orig.m_programSize),
  522. numSubs(orig.numSubs),
  523. regmust(0)
  524. {
  525. #if _DEBUG
  526. m_originalPattern = orig.m_originalPattern;
  527. m_modifiedPattern = orig.m_modifiedPattern;
  528. #endif
  529. status = orig.status;
  530. count = 0;
  531. program = new TCHAR[m_programSize];
  532. memcpy( program, orig.program, m_programSize * sizeof( TCHAR ) );
  533. if ( orig.regmust )
  534. regmust = program + ( orig.regmust - orig.program );
  536. for ( int i = Regexp::NSUBEXP; i > 0; i--)
  537. {
  538. startp[i] = orig.startp[i];
  539. endp[i] = orig.endp[i];
  540. }
  541. }
  543. regexp::~regexp()
  544. {
  545. delete [] program;
  546. }
  549. // regcomp - compile a regular expression into internal code
  550. //
  551. // We can't allocate space until we know how big the compiled form will
  552. // be, but we can't compile it (and thus know how big it is) until we've
  553. // got a place to put the code.  So we cheat: we compile it twice, once
  554. // with code generation turned off and size counting turned on, and once
  555. // "for real".  This also means that we don't allocate space until we are
  556. // sure that the thing really will compile successfully, and we never
  557. // have to move the code and thus invalidate pointers into it.  (Note
  558. // that it has to be in one piece because free() must be able to free it
  559. // all.)
  560. //
  561. // Beware that the optimization-preparation code in here knows about some
  562. // of the structure of the compiled regexp.
  564. bool regexp::regcomp(LPCTSTR exp)
  565. {
  566. LPTSTR scan;
  567. int flags;
  569. if (exp == NULL)
  570. {
  571. regerror( REGERR_NULL_TO_REGCOMP );
  572. return NULL;
  573. }
  575. // First pass: determine size, legality.
  576. CRegValidator tester( exp );
  578. if (tester.reg(0, &flags) == NULL)
  579. return false;
  581. // Small enough for pointer-storage convention? 
  582. if (tester.Size() >= 0x7fffL) // Probably could be 0xffffL. 
  583. {
  584. regerror(REGERR_TO_BIG);
  585. return NULL;
  586. }
  588. m_programSize = tester.Size();
  589. // Allocate space. 
  590. program = new TCHAR[m_programSize];
  592. CRegCompiler comp( exp, program );
  593. // Second pass: emit code. 
  594. if (comp.reg(0, &flags) == NULL)
  595. return false;
  597. scan = program + 1; // First BRANCH. 
  598. if (OP(regnext(scan)) == END)
  599. { // Only one top-level choice. 
  600. scan = OPERAND(scan);
  602. // Starting-point info. 
  603. if (OP(scan) == EXACTLY)
  604. regstart = *OPERAND(scan);
  605. else if (OP(scan) == BOL)
  606. reganch = 1;
  608. // If there's something expensive in the r.e., find the
  609. // longest literal string that must appear and make it the
  610. // regmust.  Resolve ties in favor of later strings, since
  611. // the regstart check works with the beginning of the r.e.
  612. // and avoiding duplication strengthens checking.  Not a
  613. // strong reason, but sufficient in the absence of others.
  614.  
  615. if (flags&SPSTART) 
  616. {
  617. LPTSTR longest = NULL;
  618. size_t len = 0;
  620. for (; scan != NULL; scan = regnext(scan))
  621. if (OP(scan) == EXACTLY && _tcslen(OPERAND(scan)) >= len)
  622. {
  623. longest = OPERAND(scan);
  624. len = _tcslen(OPERAND(scan));
  625. }
  626. regmust = longest;
  627. regmlen = (int)len;
  628. }
  629. }
  631. return true;
  632. }
  634. regexp * regexp::getCopy()
  635. {
  636. return new regexp( *this );
  637. }
  639. // reg - regular expression, i.e. main body or parenthesized thing
  640. //
  641. // Caller must absorb opening parenthesis.
  642. //
  643. // Combining parenthesis handling with the base level of regular expression
  644. // is a trifle forced, but the need to tie the tails of the branches to what
  645. // follows makes it hard to avoid.
  647. LPTSTR CRegCompilerBase::reg( int paren, int *flagp )
  648. {
  649. LPTSTR ret;
  650. LPTSTR br;
  651. LPTSTR ender;
  652. int parno = 0;
  653. int flags;
  655. *flagp = HASWIDTH; // Tentatively. 
  657. if (paren)
  658. {
  659. // Make an OPEN node. 
  660. if (regnpar >= Regexp::NSUBEXP)
  661. {
  662. regerror(REGERR_TO_MANY_PAREN);
  663. return NULL;
  664. }
  665. parno = regnpar;
  666. regnpar++;
  667. ret = regnode(OPEN+parno);
  668. }
  670. // Pick up the branches, linking them together. 
  671. br = regbranch(&flags);
  672. if (br == NULL)
  673. return(NULL);
  674. if (paren)
  675. regtail(ret, br); // OPEN -> first. 
  676. else
  677. ret = br;
  678. *flagp &= ~(~flags&HASWIDTH); // Clear bit if bit 0. 
  679. *flagp |= flags&SPSTART;
  680. while (*regparse == '|')
  681. {
  682. regparse++;
  683. br = regbranch(&flags);
  684. if (br == NULL)
  685. return(NULL);
  686. regtail(ret, br); // BRANCH -> BRANCH. 
  687. *flagp &= ~(~flags&HASWIDTH);
  688. *flagp |= flags&SPSTART;
  689. }
  691. // Make a closing node, and hook it on the end. 
  692. ender = regnode((paren) ? CLOSE+parno : END);
  693. regtail(ret, ender);
  695. // Hook the tails of the branches to the closing node. 
  696. for (br = ret; br != NULL; br = regnext(br))
  697. regoptail(br, ender);
  699. // Check for proper termination. 
  700. if (paren && *regparse++ != ')')
  701. {
  702. regerror( REGERR_UNTERMINATED_PAREN );
  703. return NULL;
  704. }
  705. else if (!paren && *regparse != '')
  706. {
  707. if (*regparse == ')')
  708. {
  709. regerror( REGERR_UNMATCHED_PAREN );
  710. return NULL;
  711. }
  712. else
  713. {
  714. regerror( REGERR_INTERNAL_ERROR_JUNK );
  715. return NULL;
  716. }
  717. // NOTREACHED 
  718. }
  720. return(ret);
  721. }
  723. // regbranch - one alternative of an | operator
  724. //
  725. // Implements the concatenation operator.
  727. LPTSTR CRegCompilerBase::regbranch(int *flagp)
  728. {
  729. LPTSTR ret;
  730. LPTSTR chain;
  731. LPTSTR latest;
  732. int flags;
  733. int c;
  735. *flagp = WORST; // Tentatively. 
  737. ret = regnode(BRANCH);
  738. chain = NULL;
  739. while ((c = *regparse) != '' && c != '|' && c != ')')
  740. {
  741. latest = regpiece(&flags);
  742. if (latest == NULL)
  743. return(NULL);
  744. *flagp |= flags&HASWIDTH;
  745. if (chain == NULL) // First piece. 
  746. *flagp |= flags&SPSTART;
  747. else
  748. regtail(chain, latest);
  749. chain = latest;
  750. }
  751. if (chain == NULL) // Loop ran zero times. 
  752. (void) regnode(NOTHING);
  754. return(ret);
  755. }
  757. // regpiece - something followed by possible [*+?]
  758. //
  759. // Note that the branching code sequences used for ? and the general cases
  760. // of * and + are somewhat optimized:  they use the same NOTHING node as
  761. // both the endmarker for their branch list and the body of the last branch.
  762. // It might seem that this node could be dispensed with entirely, but the
  763. // endmarker role is not redundant.
  765. LPTSTR CRegCompilerBase::regpiece(int *flagp)
  766. {
  767. LPTSTR ret;
  768. TCHAR op;
  769. LPTSTR next;
  770. int flags;
  772. ret = regatom(&flags);
  773. if (ret == NULL)
  774. return(NULL);
  776. op = *regparse;
  777. if (!ISREPN(op))
  778. {
  779. *flagp = flags;
  780. return(ret);
  781. }
  783. if (!(flags&HASWIDTH) && op != _T( '?' ))
  784. {
  785. regerror( REGERR_OP_COULD_BE_EMPTY );
  786. return NULL;
  787. }
  788. switch (op)
  789. {
  790. case _T( '*' ): *flagp = WORST|SPSTART; break;
  791. case _T( '+' ): *flagp = WORST|SPSTART|HASWIDTH; break;
  792. case _T( '?' ): *flagp = WORST; break;
  793. }
  795. if (op == _T( '*' ) && (flags&SIMPLE))
  796. reginsert(STAR, ret);
  797. else if (op == _T( '*' ))
  798. {
  799. // Emit x* as (x&|), where & means "self". 
  800. reginsert(BRANCH, ret); // Either x 
  801. regoptail(ret, regnode(BACK)); // and loop 
  802. regoptail(ret, ret); // back 
  803. regtail(ret, regnode(BRANCH)); // or 
  804. regtail(ret, regnode(NOTHING)); // null. 
  805. }
  806. else if (op == _T( '+' ) && (flags&SIMPLE))
  807. reginsert(PLUS, ret);
  808. else if (op == _T( '+' ))
  809. {
  810. // Emit x+ as x(&|), where & means "self". 
  811. next = regnode(BRANCH); // Either 
  812. regtail(ret, next);
  813. regtail(regnode(BACK), ret); // loop back 
  814. regtail(next, regnode(BRANCH)); // or 
  815. regtail(ret, regnode(NOTHING)); // null. 
  816. }
  817. else if (op == _T( '?' ))
  818. {
  819. // Emit x? as (x|) 
  820. reginsert(BRANCH, ret); // Either x 
  821. regtail(ret, regnode(BRANCH)); // or 
  822. next = regnode(NOTHING); // null. 
  823. regtail(ret, next);
  824. regoptail(ret, next);
  825. }
  826. regparse++;
  827. if (ISREPN(*regparse))
  828. {
  829. regerror( REGERR_NESTED_OP );
  830. return NULL;
  831. }
  833. return(ret);
  834. }
  836. // regatom - the lowest level
  837. //
  838. // Optimization:  gobbles an entire sequence of ordinary characters so that
  839. // it can turn them into a single node, which is smaller to store and
  840. // faster to run.  Backslashed characters are exceptions, each becoming a
  841. // separate node; the code is simpler that way and it's not worth fixing.
  843. LPTSTR CRegCompilerBase::regatom(int * flagp)
  844. {
  845. LPTSTR ret;
  846. int flags;
  848. *flagp = WORST; // Tentatively. 
  850. switch ( *regparse++ )
  851. {
  852. // FIXME: these chars only have meaning at beg/end of pat?
  853. case '^':
  854. ret = regnode(BOL);
  855. break;
  856. case '$':
  857. ret = regnode(EOL);
  858. break;
  859. case '.':
  860. ret = regnode(ANY);
  861. *flagp |= HASWIDTH|SIMPLE;
  862. break;
  863. case '[':
  864. {
  865. int range;
  866. int rangeend;
  867. int c;
  869. if (*regparse == '^')
  870. { // Complement of range. 
  871. ret = regnode(ANYBUT);
  872. regparse++;
  873. }
  874. else
  875. ret = regnode(ANYOF);
  876. if ((c = *regparse) == ']' || c == '-')
  877. {
  878. regc(c);
  879. regparse++;
  880. }
  881. while ((c = *regparse++ ) != '' && c != ']')
  882. {
  883. if (c != '-')
  884. regc(c);
  885. else if ((c = *regparse) == ']' || c == '')
  886. regc('-');
  887. else
  888. {
  889. range = (TCHAR)*(regparse-2);
  890. rangeend = (TCHAR)c;
  891. if (range > rangeend)
  892. {
  893. regerror( REGERR_INVALID_RANGE );
  894. return NULL;
  895. }
  896. for (range++; range <= rangeend; range++)
  897. regc(range);
  898. regparse++;
  899. }
  900. }
  901. regc('');
  902. if (c != ']')
  903. {
  904. regerror( REGERR_UNMATCHED_BRACE );
  905. return NULL;
  906. }
  907. *flagp |= HASWIDTH|SIMPLE;
  908. break;
  909. }
  910. case '(':
  911. ret = reg(1, &flags);
  912. if (ret == NULL)
  913. return(NULL);
  914. *flagp |= flags&(HASWIDTH|SPSTART);
  915. break;
  916. case '':
  917. case '|':
  918. case ')':
  919. // supposed to be caught earlier 
  920. regerror( REGERR_INTERNAL_UNEXPECTED_CHAR );
  921. return NULL;
  922. case '?':
  923. case '+':
  924. case '*':
  925. {
  926. regerror( REGERR_OP_FOLLOWS_NOTHING );
  927. return NULL;
  928. }
  929. case '\':
  930. switch (*regparse++)
  931. {
  932. case '':
  933. {
  934. regerror( REGERR_TRAILING_ESC );
  935. return NULL;
  936. }
  937. case '<':
  938. ret = regnode(WORDA);
  939. break;
  940. case '>':
  941. ret = regnode(WORDZ);
  942. break;
  943. /* FIXME: Someday handle 1, 2, ... */
  944. default:
  945. /* Handle general quoted chars in exact-match routine */
  946. goto de_fault;
  947. }
  948. break;
  949. de_fault:
  950. default:
  951. // Encode a string of characters to be matched exactly.
  952. //
  953. // This is a bit tricky due to quoted chars and due to
  954. // '*', '+', and '?' taking the SINGLE char previous
  955. // as their operand.
  956. //
  957. // On entry, the char at regparse[-1] is going to go
  958. // into the string, no matter what it is.  (It could be
  959. // following a  if we are entered from the '' case.)
  960. // 
  961. // Basic idea is to pick up a good char in  ch  and
  962. // examine the next char.  If it's *+? then we twiddle.
  963. // If it's  then we frozzle.  If it's other magic char
  964. // we push  ch  and terminate the string.  If none of the
  965. // above, we push  ch  on the string and go around again.
  966. //
  967. //  regprev  is used to remember where "the current char"
  968. // starts in the string, if due to a *+? we need to back
  969. // up and put the current char in a separate, 1-char, string.
  970. // When  regprev  is NULL,  ch  is the only char in the
  971. // string; this is used in *+? handling, and in setting
  972. // flags |= SIMPLE at the end.
  973. {
  974. TCHAR *regprev;
  975. register TCHAR ch;
  977. regparse--; /* Look at cur char */
  978. ret = regnode(EXACTLY);
  979. for ( regprev = 0 ; ; ) {
  980. ch = *regparse++; /* Get current char */
  981. switch (*regparse) { /* look at next one */
  983. default:
  984. regc(ch); /* Add cur to string */
  985. break;
  987. case '.': case '[': case '(':
  988. case ')': case '|': case 'n':
  989. case '$': case '^':
  990. case '':
  991. /* FIXME, $ and ^ should not always be magic */
  992. magic:
  993. regc(ch); /* dump cur char */
  994. goto done; /* and we are done */
  996. case '?': case '+': case '*':
  997. if (!regprev)  /* If just ch in str, */
  998. goto magic; /* use it */
  999. /* End mult-char string one early */
  1000. regparse = regprev; /* Back up parse */
  1001. goto done;
  1003. case '\':
  1004. regc(ch); /* Cur char OK */
  1005. switch (regparse[1]){ /* Look after  */
  1006. case '':
  1007. case '<':
  1008. case '>':
  1009. /* FIXME: Someday handle 1, 2, ... */
  1010. goto done; /* Not quoted */
  1011. default:
  1012. /* Backup point is , scan  * point is after it. */
  1013. regprev = regparse;
  1014. regparse++; 
  1015. continue; /* NOT break; */
  1016. }
  1017. }
  1018. regprev = regparse; /* Set backup point */
  1019. }
  1020. done:
  1021. regc('');
  1022. *flagp |= HASWIDTH;
  1023. if (!regprev) /* One char? */
  1024. *flagp |= SIMPLE;
  1025. }
  1026. break;
  1027. }
  1029. return(ret);
  1030. }
  1032. ////////////////////////////////////////////////////////////////////////////////
  1033. // regexec and friends
  1035. // Work-variable struct for regexec().
  1037. class CRegExecutor : public CRegProgramAccessor
  1038. {
  1039. friend bool regexp::regexec( LPCTSTR str );
  1041. LPTSTR reginput; // String-input pointer. 
  1042. LPTSTR regbol; // Beginning of input, for ^ check. 
  1043. LPTSTR * regstartp; // Pointer to startp array. 
  1044. LPTSTR * regendp; // Ditto for endp.
  1046. regexp * prog;
  1047. public:
  1048. CRegExecutor( regexp * prog, LPTSTR string );
  1049. protected:
  1050. bool regtry( LPTSTR string );
  1051. bool regmatch( LPTSTR prog );
  1052. size_t regrepeat( LPTSTR node );
  1053. };
  1055. CRegExecutor::CRegExecutor( regexp * p, LPTSTR string )
  1056. : regbol( string ),
  1057. regstartp( p->startp ),
  1058. regendp( p->endp ),
  1059. prog(p)
  1060. {
  1061. }
  1063. #ifdef _RE_DEBUG
  1064. int regnarrate = 0;
  1065. #endif
  1067. // regexec - match a regexp against a string
  1069. bool regexp::regexec( LPCTSTR str )
  1070. {
  1071. LPTSTR string = (LPTSTR)str; // avert const poisoning 
  1073. // Be paranoid. 
  1074. if ( string == NULL )
  1075. {
  1076. regerror( REGERR_NULLARG );
  1077. return false;
  1078. }
  1080. // Check validity of program. 
  1081. if (*program != MAGIC)
  1082. {
  1083. regerror( REGERR_CORRUPTED );
  1084. return false;
  1085. }
  1087. // If there is a "must appear" string, look for it. 
  1088. if ( regmust != NULL && _tcsstr( string, regmust ) == NULL )
  1089. return false;
  1091. CRegExecutor executor( this, string );
  1093. // Simplest case:  anchored match need be tried only once. 
  1094. if ( reganch )
  1095. return( executor.regtry( string ) );
  1097. // Messy cases:  unanchored match. 
  1098. if ( regstart != '' )
  1099. {
  1100. // We know what TCHAR it must start with. 
  1101. for ( LPTSTR s = string; s != NULL; s = _tcschr( s+1 , regstart ) )
  1102. if ( executor.regtry( s) )
  1103. return true;
  1104. return false;
  1105. }
  1106. else
  1107. {
  1108. // We don't -- general case. 
  1109. for ( LPTSTR s = string; ! executor.regtry( s ); s++ )
  1110. if (*s == '')
  1111. return false;
  1112. }
  1113. return true;
  1114. }
  1116. // regtry - try match at specific point
  1117. bool CRegExecutor::regtry( LPTSTR string )
  1118. {
  1119. int i;
  1120. LPTSTR * stp;
  1121. LPTSTR * enp;
  1123. reginput = string;
  1125. stp = prog->startp;
  1126. enp = prog->endp;
  1127. for (i = Regexp::NSUBEXP; i > 0; i--)
  1128. {
  1129. *stp++ = NULL;
  1130. *enp++ = NULL;
  1131. }
  1132. if ( regmatch( prog->program + 1 ) )
  1133. {
  1134. prog->startp[0] = string;
  1135. prog->endp[0] = reginput;
  1136. return true;
  1137. }
  1138. else
  1139. return false;
  1140. }
  1142. // regmatch - main matching routine
  1143. //
  1144. // Conceptually the strategy is simple:  check to see whether the current
  1145. // node matches, call self recursively to see whether the rest matches,
  1146. // and then act accordingly.  In practice we make some effort to avoid
  1147. // recursion, in particular by going through "ordinary" nodes (that don't
  1148. // need to know whether the rest of the match failed) by a loop instead of
  1149. // by recursion.
  1151. bool CRegExecutor::regmatch( LPTSTR prog )
  1152. {
  1153. LPTSTR scan; // Current node. 
  1154. LPTSTR next; // Next node. 
  1156. #ifdef _RE_DEBUG
  1157. if (prog != NULL && regnarrate)
  1158. _ftprintf(stderr, _T( "%s(n" ), regprop(prog));
  1159. #endif
  1160. for (scan = prog; scan != NULL; scan = next)
  1161. {
  1162. #ifdef _RE_DEBUG
  1163. if (regnarrate)
  1164. _ftprintf(stderr, _T( "%s...n" ), regprop(scan));
  1165. #endif
  1166. next = regnext(scan);
  1168. switch (OP(scan))
  1169. {
  1170. case BOL:
  1171. if (reginput != regbol)
  1172. return false;
  1173. break;
  1174. case EOL:
  1175. if (*reginput != '')
  1176. return false;
  1177. break;
  1178. case WORDA:
  1179. /* Must be looking at a letter, digit, or _ */
  1180. if ((!isalnum(*reginput)) && *reginput != '_')
  1181. return(0);
  1182. /* Prev must be BOL or nonword */
  1183. if (reginput > regbol &&
  1184. (isalnum(reginput[-1]) || reginput[-1] == '_'))
  1185. return(0);
  1186. break;
  1187. case WORDZ:
  1188. /* Must be looking at non letter, digit, or _ */
  1189. if (isalnum(*reginput) || *reginput == '_')
  1190. return(0);
  1191. /* We don't care what the previous char was */
  1192. break;
  1193. case ANY:
  1194. if (*reginput == '')
  1195. return false;
  1196. reginput++;
  1197. break;
  1198. case EXACTLY:
  1199. {
  1200. size_t len;
  1201. LPTSTR const opnd = OPERAND(scan);
  1203. // Inline the first character, for speed. 
  1204. if (*opnd != *reginput)
  1205. return false;
  1206. len = _tcslen(opnd);
  1207. if (len > 1 && _tcsncmp(opnd, reginput, len) != 0)
  1208. return false;
  1209. reginput += len;
  1211. break;
  1212. }
  1213. case ANYOF:
  1214. if (*reginput == '' ||
  1215. _tcschr(OPERAND(scan), *reginput) == NULL)
  1216. return false;
  1217. reginput++;
  1218. break;
  1219. case ANYBUT:
  1220. if (*reginput == '' ||
  1221. _tcschr(OPERAND(scan), *reginput) != NULL)
  1222. return false;
  1223. reginput++;
  1224. break;
  1225. case NOTHING:
  1226. break;
  1227. case BACK:
  1228. break;
  1229. case OPEN+1: case OPEN+2: case OPEN+3:
  1230. case OPEN+4: case OPEN+5: case OPEN+6:
  1231. case OPEN+7: case OPEN+8: case OPEN+9:
  1232. {
  1233. const int no = OP(scan) - OPEN;
  1234. LPTSTR const input = reginput;
  1236. if (regmatch(next))
  1237. {
  1238. // Don't set startp if some later
  1239. // invocation of the same parentheses
  1240. // already has.
  1241.  
  1242. if (regstartp[no] == NULL)
  1243. regstartp[no] = input;
  1244. return true;
  1245. }
  1246. else
  1247. return false;
  1248. break;
  1249. }
  1250. case CLOSE+1: case CLOSE+2: case CLOSE+3:
  1251. case CLOSE+4: case CLOSE+5: case CLOSE+6:
  1252. case CLOSE+7: case CLOSE+8: case CLOSE+9:
  1253. {
  1254. const int no = OP(scan) - CLOSE;
  1255. LPTSTR const input = reginput;
  1257. if (regmatch(next))
  1258. {
  1259. // Don't set endp if some later
  1260. // invocation of the same parentheses
  1261. // already has.
  1262.  
  1263. if (regendp[no] == NULL)
  1264. regendp[no] = input;
  1265. return true;
  1266. }
  1267. else
  1268. return false;
  1269. break;
  1270. }
  1271. case BRANCH:
  1272. {
  1273. LPTSTR const save = reginput;
  1275. if (OP(next) != BRANCH) // No choice. 
  1276. next = OPERAND(scan); // Avoid recursion. 
  1277. else
  1278. {
  1279. while (OP(scan) == BRANCH)
  1280. {
  1281. if (regmatch(OPERAND(scan)))
  1282. return true;
  1283. reginput = save;
  1284. scan = regnext(scan);
  1285. }
  1286. return false;
  1287. // NOTREACHED 
  1288. }
  1289. break;
  1290. }
  1291. case STAR: case PLUS:
  1292. {
  1293. const TCHAR nextch = (OP(next) == EXACTLY) ? *OPERAND(next) : '';
  1294. size_t no;
  1295. LPTSTR const save = reginput;
  1296. const size_t min = (OP(scan) == STAR) ? 0 : 1;
  1298. for (no = regrepeat(OPERAND(scan)) + 1; no > min; no--)
  1299. {
  1300. reginput = save + no - 1;
  1301. // If it could work, try it. 
  1302. if (nextch == '' || *reginput == nextch)
  1303. if (regmatch(next))
  1304. return true;
  1305. }
  1306. return false;
  1307. break;
  1308. }
  1309. case END:
  1310. return true; // Success! 
  1311. break;
  1312. default:
  1313. regerror( REGERR_CORRUPTION );
  1314. return false;
  1315. break;
  1316. }
  1317. }
  1319. // We get here only if there's trouble -- normally "case END" is
  1320. // the terminating point.
  1322. regerror( REGERR_CORRUPTED_POINTERS );
  1323. return false;
  1324. }
  1326. // regrepeat - report how many times something simple would match
  1328. size_t CRegExecutor::regrepeat( LPTSTR node )
  1329. {
  1330. size_t count;
  1331. LPTSTR scan;
  1332. TCHAR ch;
  1334. switch (OP(node))
  1335. {
  1336. case ANY:
  1337. return(_tcslen(reginput));
  1338. break;
  1339. case EXACTLY:
  1340. ch = *OPERAND(node);
  1341. count = 0;
  1342. for (scan = reginput; *scan == ch; scan++)
  1343. count++;
  1344. return(count);
  1345. break;
  1346. case ANYOF:
  1347. return(_tcsspn(reginput, OPERAND(node)));
  1348. break;
  1349. case ANYBUT:
  1350. return(_tcscspn(reginput, OPERAND(node)));
  1351. break;
  1352. default: // Oh dear.  Called inappropriately. 
  1353. regerror( REGERR_BAD_REGREPEAT );
  1354. return(0); // Best compromise. 
  1355. break;
  1356. }
  1357. // NOTREACHED 
  1358. }
  1360. #ifdef _RE_DEBUG
  1362. // regdump - dump a regexp onto stdout in vaguely comprehensible form
  1364. void regexp::regdump()
  1365. {
  1366. LPTSTR s;
  1367. TCHAR op = EXACTLY; // Arbitrary non-END op. 
  1368. LPTSTR next;
  1370. s = _tcsinc(program);
  1371. while (op != END)
  1372. { // While that wasn't END last time... 
  1373. op = OP(s);
  1374. _tprintf(_T( "%2d%s" ), s-program, regprop(s)); // Where, what. 
  1375. next = regnext(s);
  1376. if (next == NULL) // Next ptr. 
  1377. _tprintf(_T( "(0)" ));
  1378. else 
  1379. _tprintf(_T( "(%d)" ), (s-program)+(next-s));
  1380. s += 3;
  1381. if (op == ANYOF || op == ANYBUT || op == EXACTLY)
  1382. {
  1383. // Literal string, where present. 
  1384. while (*s != '')
  1385. {
  1386. _puttchar(*s);
  1387. s = _tcsinc(s);
  1388. }
  1389. s = _tcsinc(s);
  1390. }
  1391. _puttchar('n');
  1392. }
  1394. // Header fields of interest. 
  1395. if (regstart != '')
  1396. _tprintf(_T( "start `%c' " ), regstart);
  1397. if (reganch)
  1398. _tprintf(_T( "anchored " ));
  1399. if (regmust != NULL)
  1400. _tprintf(_T( "must have "%s"" ), regmust);
  1401. _tprintf(_T( "n" ));
  1402. }
  1404. // regprop - printable representation of opcode
  1406. #define OUTPUT(s) case s: p = _T( #s ); break
  1407. LPTSTR CRegProgramAccessor::regprop( LPTSTR op )
  1408. {
  1409. LPTSTR p;
  1410. static TCHAR buf[50];
  1412. (void) _tcscpy(buf, _T( ":" ));
  1414. switch (OP(op))
  1415. {
  1416. OUTPUT( BOL );
  1417. OUTPUT( EOL );
  1418. OUTPUT( ANY );
  1419. OUTPUT( ANYOF );
  1420. OUTPUT( ANYBUT );
  1421. OUTPUT( BRANCH );
  1422. OUTPUT( EXACTLY );
  1423. OUTPUT( NOTHING );
  1424. OUTPUT( BACK );
  1425. OUTPUT( END );
  1426. OUTPUT( STAR );
  1427. OUTPUT( PLUS );
  1428. OUTPUT( WORDA );
  1429. OUTPUT( WORDZ );
  1430. case OPEN+1: case OPEN+2: case OPEN+3:
  1431. case OPEN+4: case OPEN+5: case OPEN+6:
  1432. case OPEN+7: case OPEN+8: case OPEN+9:
  1433. _stprintf(buf+_tcslen(buf), _T( "OPEN%d" ), OP(op)-OPEN);
  1434. p = NULL;
  1435. break;
  1436. case CLOSE+1: case CLOSE+2: case CLOSE+3:
  1437. case CLOSE+4: case CLOSE+5: case CLOSE+6:
  1438. case CLOSE+7: case CLOSE+8: case CLOSE+9:
  1439. _stprintf(buf+_tcslen(buf), _T( "CLOSE%d" ), OP(op)-CLOSE);
  1440. p = NULL;
  1441. break;
  1442. default:
  1443. regerror( REGERR_CORRUPTED_OPCODE );
  1444. break;
  1445. }
  1446. if (p != NULL)
  1447. (void) _tcscat(buf, p);
  1448. return(buf);
  1449. }
  1450. #endif
  1452. ///////////////////////////////////////////////////////////////////////////////
  1454. Regexp::Regexp()
  1455. : rc(0),
  1456. string(0)
  1457. {
  1458. }
  1460. Regexp::Regexp( LPCTSTR exp, BOOL iCase )
  1461. : rc( new regexp( exp, iCase ) ),
  1462. string( 0 )
  1463. {
  1464. }
  1466. Regexp::Regexp( const Regexp &r )
  1467. : rc( r.rc ),
  1468. m_szError(r.m_szError),
  1469. string(r.string)
  1470. {
  1471. if ( rc )
  1472. rc->count++;
  1473. }
  1475. const Regexp & Regexp::operator=( const Regexp & r )
  1476. {
  1477. if ( this != &r )
  1478. {
  1479. if ( rc && rc->count-- == 0 )
  1480. delete rc;
  1482. rc = r.rc;
  1483. if ( rc )
  1484. rc->count++;
  1486. string = r.string;
  1487. m_szError = r.m_szError;
  1488. }
  1489. return *this;
  1490. }
  1492. Regexp::~Regexp()
  1493. {
  1494. if ( rc && rc->count-- == 0 )
  1495. delete rc;
  1496. }
  1498. bool Regexp::Match( const TCHAR * s )
  1499. {
  1500. ClearErrorString();
  1501. string = s;
  1502. bool ret = false;
  1503. if ( rc )
  1504. {
  1505. // copy on write !
  1507. if ( rc->count )
  1508. {
  1509. rc->count--;
  1510. rc = rc->getCopy();
  1511. }
  1513. ret = rc->regexec( s );
  1514. int i = 0;
  1515. if ( ret )
  1516. for ( i = 0; i < Regexp::NSUBEXP && rc->startp[i] ; i++ )
  1517. ;
  1518. rc->numSubs = i - 1;
  1519. }
  1520. else
  1521. m_szError = CRegErrorHandler::FindErr( REGERR_NO_REGEXP );
  1522. return ret;
  1523. }
  1525. CString Regexp::GetReplaceString( LPCTSTR source ) const
  1526. {
  1527. ClearErrorString();
  1528. if ( rc )
  1529. return rc->GetReplaceString( source );
  1530. else
  1531. m_szError = CRegErrorHandler::FindErr( REGERR_NO_REGEXP );
  1532. return _T( "" );
  1533. }
  1535. int Regexp::SubStrings() const
  1536. {
  1537. ClearErrorString();
  1538. int ret = -1;
  1539. if ( rc )
  1540. ret = rc->numSubs;
  1541. else
  1542. m_szError = CRegErrorHandler::FindErr( REGERR_NO_REGEXP );
  1543. return ret;
  1544. }
  1546. int Regexp::SubStart( unsigned int i ) const
  1547. {
  1548. ClearErrorString();
  1549. int ret = -1;
  1550. if ( rc )
  1551. ret = rc->startp[safeIndex(i)] - string;
  1552. else
  1553. m_szError = CRegErrorHandler::FindErr( REGERR_NO_REGEXP );
  1554. return ret;
  1555. }
  1557. int Regexp::SubLength( unsigned int i ) const
  1558. {
  1559. ClearErrorString();
  1560. int ret = -1;
  1561. if ( rc )
  1562. {
  1563. i = safeIndex(i);
  1564. ret = rc->endp[i] - rc->startp[i];
  1565. }
  1566. else
  1567. m_szError = CRegErrorHandler::FindErr( REGERR_NO_REGEXP );
  1568. return ret;
  1569. }
  1571. bool Regexp::CompiledOK() const
  1572. {
  1573. return rc ? rc->Status() : false;
  1574. }
  1576. #ifdef _RE_DEBUG
  1577. void Regexp::Dump()
  1578. {
  1579. if ( rc )
  1580. rc->regdump();
  1581. #if defined( _DEBUG )
  1582. else
  1583. TRACE0( "No regexp to dump outn" );
  1584. #endif
  1585. }
  1586. #endif
  1588. int Regexp::safeIndex( unsigned int i ) const
  1589. {
  1590. return i < Regexp::NSUBEXP ? i : Regexp::NSUBEXP;
  1591. }
  1593. const CString Regexp::operator[]( unsigned int i ) const
  1594. {
  1595. ClearErrorString();
  1596. ASSERT( rc );
  1597. if ( rc )
  1598. {
  1599. //CString buffer;
  1600. int len = SubLength(i);
  1601. //TCHAR * szbuf = buffer.GetBufferSetLength( len );
  1602. size_t buflen = (len + 1) * sizeof(TCHAR);
  1603. TCHAR* szbuf = (TCHAR*)_alloca(buflen);
  1604. memcpy( szbuf, rc->startp[i], len * sizeof(TCHAR) );
  1605. szbuf[len] = 0;
  1606. //buffer.ReleaseBuffer();
  1607. ///buffer.resize(_tcslen(szbuf));
  1608. //return buffer;
  1609. return CString(szbuf);
  1610. }
  1611. else
  1612. {
  1613. m_szError = CRegErrorHandler::FindErr( REGERR_NO_REGEXP );
  1614. return "";
  1615. }
  1616. }
  1618. void regexp::ignoreCase( const TCHAR * in, TCHAR * out )
  1619. {
  1620. // copy in to out making every top level character a [Aa] set
  1621. BOOL inRange = FALSE;
  1622. while( *in )
  1623. {
  1624. if ( *in == '[' )
  1625. inRange = TRUE;
  1626. if ( *in == ']' )
  1627. inRange = FALSE;
  1628. if ( ! inRange && isalpha( *in ) )
  1629. {
  1630. *out++ = '[';
  1631. *out++ = (TCHAR)toupper( *in );
  1632. *out++ = (TCHAR)tolower( *in );
  1633. *out++ = ']';
  1634. }
  1635. else
  1636. *out++ = *in;
  1637. in++;
  1638. }
  1639. *out = 0;
  1640. }
  1642. // GetReplaceString - Converts a replace expression to a string
  1643. // - perform substitutions after a regexp match
  1644. // Returns - The resultant string
  1645. CString regexp::GetReplaceString( const TCHAR* sReplaceExp ) const
  1646. {
  1647. CString szEmpty( _T( "" ) );
  1649. TCHAR *src = (TCHAR *)sReplaceExp;
  1650. TCHAR *buf;
  1651. TCHAR c;
  1652. int no;
  1653. size_t len;
  1655. if( sReplaceExp == NULL )
  1656. {
  1657. regerror( REGERR_NULL_TO_REGSUB  );
  1658. return szEmpty;
  1659. }
  1660. if ( *program != MAGIC)
  1661. {
  1662. regerror( REGERR_DAMAGED_REGEXP_REGSUB );
  1663. return szEmpty;
  1664. }
  1666. // First compute the length of the string
  1667. int replacelen = 0;
  1668. while ((c = *src++) != _T('')) 
  1669. {
  1670. if (c == _T('&'))
  1671. no = 0;
  1672. else if (c == _T('\') && isdigit(*src))
  1673. no = *src++ - _T('0');
  1674. else
  1675. no = -1;
  1677. if (no < 0) 
  1678. {
  1679. // Ordinary character. 
  1680. if (c == _T('\') && (*src == _T('\') || *src == _T('&')))
  1681. c = *src++;
  1682. replacelen++;
  1683. } 
  1684. else if (startp[no] != NULL && endp[no] != NULL &&
  1685. endp[no] > startp[no]) 
  1686. {
  1687. // Get tagged expression
  1688. len = endp[no] - startp[no];
  1689. replacelen += len;
  1690. }
  1691. }
  1693. CString szReplace;
  1695. //buf = szReplace.GetBufferSetLength( replacelen );
  1696. size_t buflen = (replacelen + 1) * sizeof(TCHAR);
  1697. buf = (TCHAR*)_alloca(buflen);
  1698. size_t repsize = szReplace.size();
  1699. size_t reservesize = min(repsize, replacelen);
  1700. size_t reservelen = reservesize * sizeof(TCHAR);
  1701. memcpy(buf, szReplace.data(), reservelen);
  1702. memset(buf + reservesize, 0, buflen - reservelen);
  1704. // Now we can create the string
  1705. src = (TCHAR *)sReplaceExp;
  1706. while ((c = *src++) != _T('')) 
  1707. {
  1708. if (c == _T('&'))
  1709. no = 0;
  1710. else if (c == _T('\') && isdigit(*src))
  1711. no = *src++ - _T('0');
  1712. else
  1713. no = -1;
  1715. if (no < 0) 
  1716. {
  1717. // Ordinary character. 
  1718. if (c == _T('\') && (*src == _T('\') || *src == _T('&')))
  1719. c = *src++;
  1720. *buf++ = c;
  1721. } 
  1722. else if (startp[no] != NULL && endp[no] != NULL &&
  1723. endp[no] > startp[no]) 
  1724. {
  1725. // Get tagged expression
  1726. len = endp[no] - startp[no];
  1727. _tcsncpy(buf, startp[no], len);
  1728. buf += len;
  1729. if (len != 0 && *(buf-1) == _T( '' ))
  1730. { /* strncpy hit NUL. */
  1731. regerror( REGERR_DAMAGED_MATCH_STRING );
  1732. return szEmpty;
  1733. }
  1734. }
  1735. }
  1737. //szReplace.ReleaseBuffer( replacelen );
  1738. //return szReplace;
  1739. return CString(buf, replacelen);
  1740. }
  1742. CString Regexp::GetErrorString() const
  1743. {
  1744. // make sure that if status == 0 that we have an error string
  1745. //ASSERT( ( ! CompiledOK() ) ? ( rc ? rc->GetErrorString() : m_szError).GetLength() != 0 : 1 );
  1746. ASSERT( ( ! CompiledOK() ) ? ( rc ? rc->GetErrorString() : m_szError).size() != 0 : 1 );
  1747. return rc ? rc->GetErrorString() : m_szError ;
  1748. }
  1750. void Regexp::ClearErrorString() const
  1751. {
  1752. if ( rc )
  1753. rc->ClearErrorString();
  1754. m_szError.resize(0);
  1755. }