regexec.c 126 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040404140424043404440454046404740484049405040514052405340544055405640574058405940604061406240634064406540664067406840694070407140724073407440754076407740784079408040814082408340844085408640874088408940904091409240934094409540964097409840994100410141024103410441054106410741084109411041114112411341144115411641174118411941204121412241234124412541264127412841294130413141324133413441354136413741384139414041414142414341444145414641474148414941504151415241534154415541564157415841594160416141624163416441654166416741684169417041714172417341744175417641774178417941804181418241834184418541864187418841894190419141924193419441954196419741984199420042014202420342044205420642074208420942104211421242134214421542164217421842194220422142224223422442254226422742284229423042314232423342344235423642374238423942404241424242434244424542464247424842494250425142524253425442554256425742584259426042614262426342644265426642674268426942704271427242734274427542764277427842794280428142824283428442854286428742884289429042914292429342944295429642974298429943004301430243034304430543064307430843094310431143124313431443154316431743184319432043214322432343244325432643274328432943304331433243334334433543364337
  1. /* Extended regular expression matching and search library.
  2. Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
  3. This file is part of the GNU C Library.
  4. Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
  5. The GNU C Library is free software; you can redistribute it and/or
  6. modify it under the terms of the GNU Lesser General Public
  7. License as published by the Free Software Foundation; either
  8. version 2.1 of the License, or (at your option) any later version.
  9. The GNU C Library is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  12. Lesser General Public License for more details.
  13. You should have received a copy of the GNU Lesser General Public
  14. License along with the GNU C Library; if not, write to the Free
  15. Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  16. 02111-1307 USA. */
  17. static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
  18. int n) internal_function;
  19. static void match_ctx_clean (re_match_context_t *mctx) internal_function;
  20. static void match_ctx_free (re_match_context_t *cache) internal_function;
  21. static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
  22. int str_idx, int from, int to)
  23. internal_function;
  24. static int search_cur_bkref_entry (const re_match_context_t *mctx, int str_idx)
  25. internal_function;
  26. static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, int node,
  27. int str_idx) internal_function;
  28. static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
  29. int node, int str_idx)
  30. internal_function;
  31. static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
  32. re_dfastate_t **limited_sts, int last_node,
  33. int last_str_idx)
  34. internal_function;
  35. static reg_errcode_t re_search_internal (const regex_t *preg,
  36. const char *string, int length,
  37. int start, int range, int stop,
  38. size_t nmatch, regmatch_t pmatch[],
  39. int eflags) internal_function;
  40. static int re_search_2_stub (struct re_pattern_buffer *bufp,
  41. const char *string1, int length1,
  42. const char *string2, int length2,
  43. int start, int range, struct re_registers *regs,
  44. int stop, int ret_len) internal_function;
  45. static int re_search_stub (struct re_pattern_buffer *bufp,
  46. const char *string, int length, int start,
  47. int range, int stop, struct re_registers *regs,
  48. int ret_len) internal_function;
  49. static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
  50. int nregs, int regs_allocated) internal_function;
  51. static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
  52. internal_function;
  53. static int check_matching (re_match_context_t *mctx, int fl_longest_match,
  54. int *p_match_first) internal_function;
  55. static int check_halt_state_context (const re_match_context_t *mctx,
  56. const re_dfastate_t *state, int idx)
  57. internal_function;
  58. static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
  59. regmatch_t *prev_idx_match, int cur_node,
  60. int cur_idx, int nmatch) internal_function;
  61. static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
  62. int str_idx, int dest_node, int nregs,
  63. regmatch_t *regs,
  64. re_node_set *eps_via_nodes)
  65. internal_function;
  66. static reg_errcode_t set_regs (const regex_t *preg,
  67. const re_match_context_t *mctx,
  68. size_t nmatch, regmatch_t *pmatch,
  69. int fl_backtrack) internal_function;
  70. static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
  71. internal_function;
  72. #ifdef RE_ENABLE_I18N
  73. static int sift_states_iter_mb (const re_match_context_t *mctx,
  74. re_sift_context_t *sctx,
  75. int node_idx, int str_idx, int max_str_idx)
  76. internal_function;
  77. #endif /* RE_ENABLE_I18N */
  78. static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
  79. re_sift_context_t *sctx)
  80. internal_function;
  81. static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
  82. re_sift_context_t *sctx, int str_idx,
  83. re_node_set *cur_dest)
  84. internal_function;
  85. static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
  86. re_sift_context_t *sctx,
  87. int str_idx,
  88. re_node_set *dest_nodes)
  89. internal_function;
  90. static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
  91. re_node_set *dest_nodes,
  92. const re_node_set *candidates)
  93. internal_function;
  94. static int check_dst_limits (const re_match_context_t *mctx,
  95. re_node_set *limits,
  96. int dst_node, int dst_idx, int src_node,
  97. int src_idx) internal_function;
  98. static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
  99. int boundaries, int subexp_idx,
  100. int from_node, int bkref_idx)
  101. internal_function;
  102. static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
  103. int limit, int subexp_idx,
  104. int node, int str_idx,
  105. int bkref_idx) internal_function;
  106. static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
  107. re_node_set *dest_nodes,
  108. const re_node_set *candidates,
  109. re_node_set *limits,
  110. struct re_backref_cache_entry *bkref_ents,
  111. int str_idx) internal_function;
  112. static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
  113. re_sift_context_t *sctx,
  114. int str_idx, const re_node_set *candidates)
  115. internal_function;
  116. static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
  117. re_dfastate_t **dst,
  118. re_dfastate_t **src, int num)
  119. internal_function;
  120. static re_dfastate_t *find_recover_state (reg_errcode_t *err,
  121. re_match_context_t *mctx) internal_function;
  122. static re_dfastate_t *transit_state (reg_errcode_t *err,
  123. re_match_context_t *mctx,
  124. re_dfastate_t *state) internal_function;
  125. static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
  126. re_match_context_t *mctx,
  127. re_dfastate_t *next_state)
  128. internal_function;
  129. static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
  130. re_node_set *cur_nodes,
  131. int str_idx) internal_function;
  132. #if 0
  133. static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
  134. re_match_context_t *mctx,
  135. re_dfastate_t *pstate)
  136. internal_function;
  137. #endif
  138. #ifdef RE_ENABLE_I18N
  139. static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
  140. re_dfastate_t *pstate)
  141. internal_function;
  142. #endif /* RE_ENABLE_I18N */
  143. static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
  144. const re_node_set *nodes)
  145. internal_function;
  146. static reg_errcode_t get_subexp (re_match_context_t *mctx,
  147. int bkref_node, int bkref_str_idx)
  148. internal_function;
  149. static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
  150. const re_sub_match_top_t *sub_top,
  151. re_sub_match_last_t *sub_last,
  152. int bkref_node, int bkref_str)
  153. internal_function;
  154. static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
  155. int subexp_idx, int type) internal_function;
  156. static reg_errcode_t check_arrival (re_match_context_t *mctx,
  157. state_array_t *path, int top_node,
  158. int top_str, int last_node, int last_str,
  159. int type) internal_function;
  160. static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
  161. int str_idx,
  162. re_node_set *cur_nodes,
  163. re_node_set *next_nodes)
  164. internal_function;
  165. static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
  166. re_node_set *cur_nodes,
  167. int ex_subexp, int type)
  168. internal_function;
  169. static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
  170. re_node_set *dst_nodes,
  171. int target, int ex_subexp,
  172. int type) internal_function;
  173. static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
  174. re_node_set *cur_nodes, int cur_str,
  175. int subexp_num, int type)
  176. internal_function;
  177. static int build_trtable (const re_dfa_t *dfa,
  178. re_dfastate_t *state) internal_function;
  179. #ifdef RE_ENABLE_I18N
  180. static int check_node_accept_bytes (const re_dfa_t *dfa, int node_idx,
  181. const re_string_t *input, int idx)
  182. internal_function;
  183. # ifdef _LIBC
  184. static unsigned int find_collation_sequence_value (const unsigned char *mbs,
  185. size_t name_len)
  186. internal_function;
  187. # endif /* _LIBC */
  188. #endif /* RE_ENABLE_I18N */
  189. static int group_nodes_into_DFAstates (const re_dfa_t *dfa,
  190. const re_dfastate_t *state,
  191. re_node_set *states_node,
  192. bitset_t *states_ch) internal_function;
  193. static int check_node_accept (const re_match_context_t *mctx,
  194. const re_token_t *node, int idx)
  195. internal_function;
  196. static reg_errcode_t extend_buffers (re_match_context_t *mctx)
  197. internal_function;
  198. /* Entry point for POSIX code. */
  199. /* regexec searches for a given pattern, specified by PREG, in the
  200. string STRING.
  201. If NMATCH is zero or REG_NOSUB was set in the cflags argument to
  202. `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
  203. least NMATCH elements, and we set them to the offsets of the
  204. corresponding matched substrings.
  205. EFLAGS specifies `execution flags' which affect matching: if
  206. REG_NOTBOL is set, then ^ does not match at the beginning of the
  207. string; if REG_NOTEOL is set, then $ does not match at the end.
  208. We return 0 if we find a match and REG_NOMATCH if not. */
  209. int
  210. regexec (preg, string, nmatch, pmatch, eflags)
  211. const regex_t *__restrict preg;
  212. const char *__restrict string;
  213. size_t nmatch;
  214. regmatch_t pmatch[];
  215. int eflags;
  216. {
  217. reg_errcode_t err;
  218. int start, length;
  219. #ifndef __UCLIBC__ /* libc_lock_lock does not exist */
  220. re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
  221. #endif
  222. if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
  223. return REG_BADPAT;
  224. if (eflags & REG_STARTEND)
  225. {
  226. start = pmatch[0].rm_so;
  227. length = pmatch[0].rm_eo;
  228. }
  229. else
  230. {
  231. start = 0;
  232. length = strlen (string);
  233. }
  234. __libc_lock_lock (dfa->lock);
  235. if (preg->no_sub)
  236. err = re_search_internal (preg, string, length, start, length - start,
  237. length, 0, NULL, eflags);
  238. else
  239. err = re_search_internal (preg, string, length, start, length - start,
  240. length, nmatch, pmatch, eflags);
  241. __libc_lock_unlock (dfa->lock);
  242. return err != REG_NOERROR;
  243. }
  244. #ifdef _LIBC
  245. # include <shlib-compat.h>
  246. versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
  247. # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
  248. __typeof__ (__regexec) __compat_regexec;
  249. int
  250. attribute_compat_text_section
  251. __compat_regexec (const regex_t *__restrict preg,
  252. const char *__restrict string, size_t nmatch,
  253. regmatch_t pmatch[], int eflags)
  254. {
  255. return regexec (preg, string, nmatch, pmatch,
  256. eflags & (REG_NOTBOL | REG_NOTEOL));
  257. }
  258. compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
  259. # endif
  260. #elif defined __UCLIBC__
  261. strong_alias(__regexec,regexec)
  262. #endif
  263. /* Entry points for GNU code. */
  264. /* re_match, re_search, re_match_2, re_search_2
  265. The former two functions operate on STRING with length LENGTH,
  266. while the later two operate on concatenation of STRING1 and STRING2
  267. with lengths LENGTH1 and LENGTH2, respectively.
  268. re_match() matches the compiled pattern in BUFP against the string,
  269. starting at index START.
  270. re_search() first tries matching at index START, then it tries to match
  271. starting from index START + 1, and so on. The last start position tried
  272. is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
  273. way as re_match().)
  274. The parameter STOP of re_{match,search}_2 specifies that no match exceeding
  275. the first STOP characters of the concatenation of the strings should be
  276. concerned.
  277. If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
  278. and all groups is stroed in REGS. (For the "_2" variants, the offsets are
  279. computed relative to the concatenation, not relative to the individual
  280. strings.)
  281. On success, re_match* functions return the length of the match, re_search*
  282. return the position of the start of the match. Return value -1 means no
  283. match was found and -2 indicates an internal error. */
  284. int
  285. re_match (bufp, string, length, start, regs)
  286. struct re_pattern_buffer *bufp;
  287. const char *string;
  288. int length, start;
  289. struct re_registers *regs;
  290. {
  291. return re_search_stub (bufp, string, length, start, 0, length, regs, 1);
  292. }
  293. #if defined _LIBC || defined __UCLIBC__
  294. strong_alias(__re_match, re_match)
  295. #endif
  296. int
  297. re_search (bufp, string, length, start, range, regs)
  298. struct re_pattern_buffer *bufp;
  299. const char *string;
  300. int length, start, range;
  301. struct re_registers *regs;
  302. {
  303. return re_search_stub (bufp, string, length, start, range, length, regs, 0);
  304. }
  305. #if defined _LIBC || defined __UCLIBC__
  306. strong_alias(__re_search, re_search)
  307. #endif
  308. int
  309. re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
  310. struct re_pattern_buffer *bufp;
  311. const char *string1, *string2;
  312. int length1, length2, start, stop;
  313. struct re_registers *regs;
  314. {
  315. return re_search_2_stub (bufp, string1, length1, string2, length2,
  316. start, 0, regs, stop, 1);
  317. }
  318. #if defined _LIBC || defined __UCLIBC__
  319. strong_alias(__re_match_2, re_match_2)
  320. #endif
  321. int
  322. re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
  323. struct re_pattern_buffer *bufp;
  324. const char *string1, *string2;
  325. int length1, length2, start, range, stop;
  326. struct re_registers *regs;
  327. {
  328. return re_search_2_stub (bufp, string1, length1, string2, length2,
  329. start, range, regs, stop, 0);
  330. }
  331. #if defined _LIBC || defined __UCLIBC__
  332. strong_alias(__re_search_2, re_search_2)
  333. #endif
  334. static int
  335. re_search_2_stub (bufp, string1, length1, string2, length2, start, range, regs,
  336. stop, ret_len)
  337. struct re_pattern_buffer *bufp;
  338. const char *string1, *string2;
  339. int length1, length2, start, range, stop, ret_len;
  340. struct re_registers *regs;
  341. {
  342. const char *str;
  343. int rval;
  344. int len = length1 + length2;
  345. int free_str = 0;
  346. if (BE (length1 < 0 || length2 < 0 || stop < 0, 0))
  347. return -2;
  348. /* Concatenate the strings. */
  349. if (length2 > 0)
  350. if (length1 > 0)
  351. {
  352. char *s = re_malloc (char, len);
  353. if (BE (s == NULL, 0))
  354. return -2;
  355. #if (defined _LIBC || defined __UCLIBC__) && defined __USE_GNU
  356. memcpy (__mempcpy (s, string1, length1), string2, length2);
  357. #else
  358. memcpy (s, string1, length1);
  359. memcpy (s + length1, string2, length2);
  360. #endif
  361. str = s;
  362. free_str = 1;
  363. }
  364. else
  365. str = string2;
  366. else
  367. str = string1;
  368. rval = re_search_stub (bufp, str, len, start, range, stop, regs,
  369. ret_len);
  370. if (free_str)
  371. re_free ((char *) str);
  372. return rval;
  373. }
  374. /* The parameters have the same meaning as those of re_search.
  375. Additional parameters:
  376. If RET_LEN is nonzero the length of the match is returned (re_match style);
  377. otherwise the position of the match is returned. */
  378. static int
  379. re_search_stub (bufp, string, length, start, range, stop, regs, ret_len)
  380. struct re_pattern_buffer *bufp;
  381. const char *string;
  382. int length, start, range, stop, ret_len;
  383. struct re_registers *regs;
  384. {
  385. reg_errcode_t result;
  386. regmatch_t *pmatch;
  387. int nregs, rval;
  388. int eflags = 0;
  389. #ifndef __UCLIBC__ /* libc_lock_lock does not exist */
  390. re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
  391. #endif
  392. /* Check for out-of-range. */
  393. if (BE (start < 0 || start > length, 0))
  394. return -1;
  395. if (BE (start + range > length, 0))
  396. range = length - start;
  397. else if (BE (start + range < 0, 0))
  398. range = -start;
  399. __libc_lock_lock (dfa->lock);
  400. eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
  401. eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
  402. /* Compile fastmap if we haven't yet. */
  403. if (range > 0 && bufp->fastmap != NULL && !bufp->fastmap_accurate)
  404. re_compile_fastmap (bufp);
  405. if (BE (bufp->no_sub, 0))
  406. regs = NULL;
  407. /* We need at least 1 register. */
  408. if (regs == NULL)
  409. nregs = 1;
  410. else if (BE (bufp->regs_allocated == REGS_FIXED &&
  411. regs->num_regs < bufp->re_nsub + 1, 0))
  412. {
  413. nregs = regs->num_regs;
  414. if (BE (nregs < 1, 0))
  415. {
  416. /* Nothing can be copied to regs. */
  417. regs = NULL;
  418. nregs = 1;
  419. }
  420. }
  421. else
  422. nregs = bufp->re_nsub + 1;
  423. pmatch = re_malloc (regmatch_t, nregs);
  424. if (BE (pmatch == NULL, 0))
  425. {
  426. rval = -2;
  427. goto out;
  428. }
  429. result = re_search_internal (bufp, string, length, start, range, stop,
  430. nregs, pmatch, eflags);
  431. rval = 0;
  432. /* I hope we needn't fill ther regs with -1's when no match was found. */
  433. if (result != REG_NOERROR)
  434. rval = -1;
  435. else if (regs != NULL)
  436. {
  437. /* If caller wants register contents data back, copy them. */
  438. bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
  439. bufp->regs_allocated);
  440. if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
  441. rval = -2;
  442. }
  443. if (BE (rval == 0, 1))
  444. {
  445. if (ret_len)
  446. {
  447. assert (pmatch[0].rm_so == start);
  448. rval = pmatch[0].rm_eo - start;
  449. }
  450. else
  451. rval = pmatch[0].rm_so;
  452. }
  453. re_free (pmatch);
  454. out:
  455. __libc_lock_unlock (dfa->lock);
  456. return rval;
  457. }
  458. static unsigned
  459. re_copy_regs (regs, pmatch, nregs, regs_allocated)
  460. struct re_registers *regs;
  461. regmatch_t *pmatch;
  462. int nregs, regs_allocated;
  463. {
  464. int rval = REGS_REALLOCATE;
  465. int i;
  466. int need_regs = nregs + 1;
  467. /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
  468. uses. */
  469. /* Have the register data arrays been allocated? */
  470. if (regs_allocated == REGS_UNALLOCATED)
  471. { /* No. So allocate them with malloc. */
  472. regs->start = re_malloc (regoff_t, need_regs);
  473. regs->end = re_malloc (regoff_t, need_regs);
  474. if (BE (regs->start == NULL, 0) || BE (regs->end == NULL, 0))
  475. return REGS_UNALLOCATED;
  476. regs->num_regs = need_regs;
  477. }
  478. else if (regs_allocated == REGS_REALLOCATE)
  479. { /* Yes. If we need more elements than were already
  480. allocated, reallocate them. If we need fewer, just
  481. leave it alone. */
  482. if (BE (need_regs > regs->num_regs, 0))
  483. {
  484. regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
  485. regoff_t *new_end = re_realloc (regs->end, regoff_t, need_regs);
  486. if (BE (new_start == NULL, 0) || BE (new_end == NULL, 0))
  487. return REGS_UNALLOCATED;
  488. regs->start = new_start;
  489. regs->end = new_end;
  490. regs->num_regs = need_regs;
  491. }
  492. }
  493. else
  494. {
  495. assert (regs_allocated == REGS_FIXED);
  496. /* This function may not be called with REGS_FIXED and nregs too big. */
  497. assert (regs->num_regs >= nregs);
  498. rval = REGS_FIXED;
  499. }
  500. /* Copy the regs. */
  501. for (i = 0; i < nregs; ++i)
  502. {
  503. regs->start[i] = pmatch[i].rm_so;
  504. regs->end[i] = pmatch[i].rm_eo;
  505. }
  506. for ( ; i < regs->num_regs; ++i)
  507. regs->start[i] = regs->end[i] = -1;
  508. return rval;
  509. }
  510. /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
  511. ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
  512. this memory for recording register information. STARTS and ENDS
  513. must be allocated using the malloc library routine, and must each
  514. be at least NUM_REGS * sizeof (regoff_t) bytes long.
  515. If NUM_REGS == 0, then subsequent matches should allocate their own
  516. register data.
  517. Unless this function is called, the first search or match using
  518. PATTERN_BUFFER will allocate its own register data, without
  519. freeing the old data. */
  520. void
  521. re_set_registers (bufp, regs, num_regs, starts, ends)
  522. struct re_pattern_buffer *bufp;
  523. struct re_registers *regs;
  524. unsigned num_regs;
  525. regoff_t *starts, *ends;
  526. {
  527. if (num_regs)
  528. {
  529. bufp->regs_allocated = REGS_REALLOCATE;
  530. regs->num_regs = num_regs;
  531. regs->start = starts;
  532. regs->end = ends;
  533. }
  534. else
  535. {
  536. bufp->regs_allocated = REGS_UNALLOCATED;
  537. regs->num_regs = 0;
  538. regs->start = regs->end = (regoff_t *) 0;
  539. }
  540. }
  541. #if defined _LIBC || defined __UCLIBC__
  542. strong_alias(__re_set_registers, re_set_registers)
  543. #endif
  544. /* Entry points compatible with 4.2 BSD regex library. We don't define
  545. them unless specifically requested. */
  546. #if defined _REGEX_RE_COMP || defined _LIBC || defined __UCLIBC__
  547. int
  548. # if defined _LIBC || defined __UCLIBC__
  549. weak_function
  550. # endif
  551. re_exec (s)
  552. const char *s;
  553. {
  554. return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
  555. }
  556. #endif /* _REGEX_RE_COMP */
  557. /* Internal entry point. */
  558. /* Searches for a compiled pattern PREG in the string STRING, whose
  559. length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
  560. mingings with regexec. START, and RANGE have the same meanings
  561. with re_search.
  562. Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
  563. otherwise return the error code.
  564. Note: We assume front end functions already check ranges.
  565. (START + RANGE >= 0 && START + RANGE <= LENGTH) */
  566. static reg_errcode_t
  567. re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
  568. eflags)
  569. const regex_t *preg;
  570. const char *string;
  571. int length, start, range, stop, eflags;
  572. size_t nmatch;
  573. regmatch_t pmatch[];
  574. {
  575. reg_errcode_t err;
  576. const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
  577. int left_lim, right_lim, incr;
  578. int fl_longest_match, match_first, match_kind, match_last = -1;
  579. int extra_nmatch;
  580. int sb, ch;
  581. #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
  582. re_match_context_t mctx = { .dfa = dfa };
  583. #else
  584. re_match_context_t mctx;
  585. #endif
  586. char *fastmap = (preg->fastmap != NULL && preg->fastmap_accurate
  587. && range && !preg->can_be_null) ? preg->fastmap : NULL;
  588. RE_TRANSLATE_TYPE t = preg->translate;
  589. #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
  590. memset (&mctx, '\0', sizeof (re_match_context_t));
  591. mctx.dfa = dfa;
  592. #endif
  593. extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
  594. nmatch -= extra_nmatch;
  595. /* Check if the DFA haven't been compiled. */
  596. if (BE (preg->used == 0 || dfa->init_state == NULL
  597. || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
  598. || dfa->init_state_begbuf == NULL, 0))
  599. return REG_NOMATCH;
  600. #ifdef DEBUG
  601. /* We assume front-end functions already check them. */
  602. assert (start + range >= 0 && start + range <= length);
  603. #endif
  604. /* If initial states with non-begbuf contexts have no elements,
  605. the regex must be anchored. If preg->newline_anchor is set,
  606. we'll never use init_state_nl, so do not check it. */
  607. if (dfa->init_state->nodes.nelem == 0
  608. && dfa->init_state_word->nodes.nelem == 0
  609. && (dfa->init_state_nl->nodes.nelem == 0
  610. || !preg->newline_anchor))
  611. {
  612. if (start != 0 && start + range != 0)
  613. return REG_NOMATCH;
  614. start = range = 0;
  615. }
  616. /* We must check the longest matching, if nmatch > 0. */
  617. fl_longest_match = (nmatch != 0 || dfa->nbackref);
  618. err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
  619. preg->translate, preg->syntax & RE_ICASE, dfa);
  620. if (BE (err != REG_NOERROR, 0))
  621. goto free_return;
  622. mctx.input.stop = stop;
  623. mctx.input.raw_stop = stop;
  624. mctx.input.newline_anchor = preg->newline_anchor;
  625. err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
  626. if (BE (err != REG_NOERROR, 0))
  627. goto free_return;
  628. /* We will log all the DFA states through which the dfa pass,
  629. if nmatch > 1, or this dfa has "multibyte node", which is a
  630. back-reference or a node which can accept multibyte character or
  631. multi character collating element. */
  632. if (nmatch > 1 || dfa->has_mb_node)
  633. {
  634. mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
  635. if (BE (mctx.state_log == NULL, 0))
  636. {
  637. err = REG_ESPACE;
  638. goto free_return;
  639. }
  640. }
  641. else
  642. mctx.state_log = NULL;
  643. match_first = start;
  644. mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
  645. : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
  646. /* Check incrementally whether of not the input string match. */
  647. incr = (range < 0) ? -1 : 1;
  648. left_lim = (range < 0) ? start + range : start;
  649. right_lim = (range < 0) ? start : start + range;
  650. sb = dfa->mb_cur_max == 1;
  651. match_kind =
  652. (fastmap
  653. ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
  654. | (range >= 0 ? 2 : 0)
  655. | (t != NULL ? 1 : 0))
  656. : 8);
  657. for (;; match_first += incr)
  658. {
  659. err = REG_NOMATCH;
  660. if (match_first < left_lim || right_lim < match_first)
  661. goto free_return;
  662. /* Advance as rapidly as possible through the string, until we
  663. find a plausible place to start matching. This may be done
  664. with varying efficiency, so there are various possibilities:
  665. only the most common of them are specialized, in order to
  666. save on code size. We use a switch statement for speed. */
  667. switch (match_kind)
  668. {
  669. case 8:
  670. /* No fastmap. */
  671. break;
  672. case 7:
  673. /* Fastmap with single-byte translation, match forward. */
  674. while (BE (match_first < right_lim, 1)
  675. && !fastmap[t[(unsigned char) string[match_first]]])
  676. ++match_first;
  677. goto forward_match_found_start_or_reached_end;
  678. case 6:
  679. /* Fastmap without translation, match forward. */
  680. while (BE (match_first < right_lim, 1)
  681. && !fastmap[(unsigned char) string[match_first]])
  682. ++match_first;
  683. forward_match_found_start_or_reached_end:
  684. if (BE (match_first == right_lim, 0))
  685. {
  686. ch = match_first >= length
  687. ? 0 : (unsigned char) string[match_first];
  688. if (!fastmap[t ? t[ch] : ch])
  689. goto free_return;
  690. }
  691. break;
  692. case 4:
  693. case 5:
  694. /* Fastmap without multi-byte translation, match backwards. */
  695. while (match_first >= left_lim)
  696. {
  697. ch = match_first >= length
  698. ? 0 : (unsigned char) string[match_first];
  699. if (fastmap[t ? t[ch] : ch])
  700. break;
  701. --match_first;
  702. }
  703. if (match_first < left_lim)
  704. goto free_return;
  705. break;
  706. default:
  707. /* In this case, we can't determine easily the current byte,
  708. since it might be a component byte of a multibyte
  709. character. Then we use the constructed buffer instead. */
  710. for (;;)
  711. {
  712. /* If MATCH_FIRST is out of the valid range, reconstruct the
  713. buffers. */
  714. unsigned int offset = match_first - mctx.input.raw_mbs_idx;
  715. if (BE (offset >= (unsigned int) mctx.input.valid_raw_len, 0))
  716. {
  717. err = re_string_reconstruct (&mctx.input, match_first,
  718. eflags);
  719. if (BE (err != REG_NOERROR, 0))
  720. goto free_return;
  721. offset = match_first - mctx.input.raw_mbs_idx;
  722. }
  723. /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
  724. Note that MATCH_FIRST must not be smaller than 0. */
  725. ch = (match_first >= length
  726. ? 0 : re_string_byte_at (&mctx.input, offset));
  727. if (fastmap[ch])
  728. break;
  729. match_first += incr;
  730. if (match_first < left_lim || match_first > right_lim)
  731. {
  732. err = REG_NOMATCH;
  733. goto free_return;
  734. }
  735. }
  736. break;
  737. }
  738. /* Reconstruct the buffers so that the matcher can assume that
  739. the matching starts from the beginning of the buffer. */
  740. err = re_string_reconstruct (&mctx.input, match_first, eflags);
  741. if (BE (err != REG_NOERROR, 0))
  742. goto free_return;
  743. #ifdef RE_ENABLE_I18N
  744. /* Don't consider this char as a possible match start if it part,
  745. yet isn't the head, of a multibyte character. */
  746. if (!sb && !re_string_first_byte (&mctx.input, 0))
  747. continue;
  748. #endif
  749. /* It seems to be appropriate one, then use the matcher. */
  750. /* We assume that the matching starts from 0. */
  751. mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
  752. match_last = check_matching (&mctx, fl_longest_match,
  753. range >= 0 ? &match_first : NULL);
  754. if (match_last != -1)
  755. {
  756. if (BE (match_last == -2, 0))
  757. {
  758. err = REG_ESPACE;
  759. goto free_return;
  760. }
  761. else
  762. {
  763. mctx.match_last = match_last;
  764. if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
  765. {
  766. re_dfastate_t *pstate = mctx.state_log[match_last];
  767. mctx.last_node = check_halt_state_context (&mctx, pstate,
  768. match_last);
  769. }
  770. if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
  771. || dfa->nbackref)
  772. {
  773. err = prune_impossible_nodes (&mctx);
  774. if (err == REG_NOERROR)
  775. break;
  776. if (BE (err != REG_NOMATCH, 0))
  777. goto free_return;
  778. match_last = -1;
  779. }
  780. else
  781. break; /* We found a match. */
  782. }
  783. }
  784. match_ctx_clean (&mctx);
  785. }
  786. #ifdef DEBUG
  787. assert (match_last != -1);
  788. assert (err == REG_NOERROR);
  789. #endif
  790. /* Set pmatch[] if we need. */
  791. if (nmatch > 0)
  792. {
  793. int reg_idx;
  794. /* Initialize registers. */
  795. for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
  796. pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
  797. /* Set the points where matching start/end. */
  798. pmatch[0].rm_so = 0;
  799. pmatch[0].rm_eo = mctx.match_last;
  800. if (!preg->no_sub && nmatch > 1)
  801. {
  802. err = set_regs (preg, &mctx, nmatch, pmatch,
  803. dfa->has_plural_match && dfa->nbackref > 0);
  804. if (BE (err != REG_NOERROR, 0))
  805. goto free_return;
  806. }
  807. /* At last, add the offset to the each registers, since we slided
  808. the buffers so that we could assume that the matching starts
  809. from 0. */
  810. for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
  811. if (pmatch[reg_idx].rm_so != -1)
  812. {
  813. #ifdef RE_ENABLE_I18N
  814. if (BE (mctx.input.offsets_needed != 0, 0))
  815. {
  816. pmatch[reg_idx].rm_so =
  817. (pmatch[reg_idx].rm_so == mctx.input.valid_len
  818. ? mctx.input.valid_raw_len
  819. : mctx.input.offsets[pmatch[reg_idx].rm_so]);
  820. pmatch[reg_idx].rm_eo =
  821. (pmatch[reg_idx].rm_eo == mctx.input.valid_len
  822. ? mctx.input.valid_raw_len
  823. : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
  824. }
  825. #else
  826. assert (mctx.input.offsets_needed == 0);
  827. #endif
  828. pmatch[reg_idx].rm_so += match_first;
  829. pmatch[reg_idx].rm_eo += match_first;
  830. }
  831. for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
  832. {
  833. pmatch[nmatch + reg_idx].rm_so = -1;
  834. pmatch[nmatch + reg_idx].rm_eo = -1;
  835. }
  836. if (dfa->subexp_map)
  837. for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
  838. if (dfa->subexp_map[reg_idx] != reg_idx)
  839. {
  840. pmatch[reg_idx + 1].rm_so
  841. = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
  842. pmatch[reg_idx + 1].rm_eo
  843. = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
  844. }
  845. }
  846. free_return:
  847. re_free (mctx.state_log);
  848. if (dfa->nbackref)
  849. match_ctx_free (&mctx);
  850. re_string_destruct (&mctx.input);
  851. return err;
  852. }
  853. static reg_errcode_t
  854. prune_impossible_nodes (mctx)
  855. re_match_context_t *mctx;
  856. {
  857. const re_dfa_t *const dfa = mctx->dfa;
  858. int halt_node, match_last;
  859. reg_errcode_t ret;
  860. re_dfastate_t **sifted_states;
  861. re_dfastate_t **lim_states = NULL;
  862. re_sift_context_t sctx;
  863. #ifdef DEBUG
  864. assert (mctx->state_log != NULL);
  865. #endif
  866. match_last = mctx->match_last;
  867. halt_node = mctx->last_node;
  868. sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
  869. if (BE (sifted_states == NULL, 0))
  870. {
  871. ret = REG_ESPACE;
  872. goto free_return;
  873. }
  874. if (dfa->nbackref)
  875. {
  876. lim_states = re_malloc (re_dfastate_t *, match_last + 1);
  877. if (BE (lim_states == NULL, 0))
  878. {
  879. ret = REG_ESPACE;
  880. goto free_return;
  881. }
  882. while (1)
  883. {
  884. memset (lim_states, '\0',
  885. sizeof (re_dfastate_t *) * (match_last + 1));
  886. sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
  887. match_last);
  888. ret = sift_states_backward (mctx, &sctx);
  889. re_node_set_free (&sctx.limits);
  890. if (BE (ret != REG_NOERROR, 0))
  891. goto free_return;
  892. if (sifted_states[0] != NULL || lim_states[0] != NULL)
  893. break;
  894. do
  895. {
  896. --match_last;
  897. if (match_last < 0)
  898. {
  899. ret = REG_NOMATCH;
  900. goto free_return;
  901. }
  902. } while (mctx->state_log[match_last] == NULL
  903. || !mctx->state_log[match_last]->halt);
  904. halt_node = check_halt_state_context (mctx,
  905. mctx->state_log[match_last],
  906. match_last);
  907. }
  908. ret = merge_state_array (dfa, sifted_states, lim_states,
  909. match_last + 1);
  910. re_free (lim_states);
  911. lim_states = NULL;
  912. if (BE (ret != REG_NOERROR, 0))
  913. goto free_return;
  914. }
  915. else
  916. {
  917. sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
  918. ret = sift_states_backward (mctx, &sctx);
  919. re_node_set_free (&sctx.limits);
  920. if (BE (ret != REG_NOERROR, 0))
  921. goto free_return;
  922. }
  923. re_free (mctx->state_log);
  924. mctx->state_log = sifted_states;
  925. sifted_states = NULL;
  926. mctx->last_node = halt_node;
  927. mctx->match_last = match_last;
  928. ret = REG_NOERROR;
  929. free_return:
  930. re_free (sifted_states);
  931. re_free (lim_states);
  932. return ret;
  933. }
  934. /* Acquire an initial state and return it.
  935. We must select appropriate initial state depending on the context,
  936. since initial states may have constraints like "\<", "^", etc.. */
  937. static inline re_dfastate_t *
  938. __attribute ((always_inline)) internal_function
  939. acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
  940. int idx)
  941. {
  942. const re_dfa_t *const dfa = mctx->dfa;
  943. if (dfa->init_state->has_constraint)
  944. {
  945. unsigned int context;
  946. context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
  947. if (IS_WORD_CONTEXT (context))
  948. return dfa->init_state_word;
  949. else if (IS_ORDINARY_CONTEXT (context))
  950. return dfa->init_state;
  951. else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
  952. return dfa->init_state_begbuf;
  953. else if (IS_NEWLINE_CONTEXT (context))
  954. return dfa->init_state_nl;
  955. else if (IS_BEGBUF_CONTEXT (context))
  956. {
  957. /* It is relatively rare case, then calculate on demand. */
  958. return re_acquire_state_context (err, dfa,
  959. dfa->init_state->entrance_nodes,
  960. context);
  961. }
  962. else
  963. /* Must not happen? */
  964. return dfa->init_state;
  965. }
  966. else
  967. return dfa->init_state;
  968. }
  969. /* Check whether the regular expression match input string INPUT or not,
  970. and return the index where the matching end, return -1 if not match,
  971. or return -2 in case of an error.
  972. FL_LONGEST_MATCH means we want the POSIX longest matching.
  973. If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
  974. next place where we may want to try matching.
  975. Note that the matcher assume that the maching starts from the current
  976. index of the buffer. */
  977. static int
  978. internal_function
  979. check_matching (re_match_context_t *mctx, int fl_longest_match,
  980. int *p_match_first)
  981. {
  982. const re_dfa_t *const dfa = mctx->dfa;
  983. reg_errcode_t err;
  984. int match = 0;
  985. int match_last = -1;
  986. int cur_str_idx = re_string_cur_idx (&mctx->input);
  987. re_dfastate_t *cur_state;
  988. int at_init_state = p_match_first != NULL;
  989. int next_start_idx = cur_str_idx;
  990. err = REG_NOERROR;
  991. cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
  992. /* An initial state must not be NULL (invalid). */
  993. if (BE (cur_state == NULL, 0))
  994. {
  995. assert (err == REG_ESPACE);
  996. return -2;
  997. }
  998. if (mctx->state_log != NULL)
  999. {
  1000. mctx->state_log[cur_str_idx] = cur_state;
  1001. /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
  1002. later. E.g. Processing back references. */
  1003. if (BE (dfa->nbackref, 0))
  1004. {
  1005. at_init_state = 0;
  1006. err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
  1007. if (BE (err != REG_NOERROR, 0))
  1008. return err;
  1009. if (cur_state->has_backref)
  1010. {
  1011. err = transit_state_bkref (mctx, &cur_state->nodes);
  1012. if (BE (err != REG_NOERROR, 0))
  1013. return err;
  1014. }
  1015. }
  1016. }
  1017. /* If the RE accepts NULL string. */
  1018. if (BE (cur_state->halt, 0))
  1019. {
  1020. if (!cur_state->has_constraint
  1021. || check_halt_state_context (mctx, cur_state, cur_str_idx))
  1022. {
  1023. if (!fl_longest_match)
  1024. return cur_str_idx;
  1025. else
  1026. {
  1027. match_last = cur_str_idx;
  1028. match = 1;
  1029. }
  1030. }
  1031. }
  1032. while (!re_string_eoi (&mctx->input))
  1033. {
  1034. re_dfastate_t *old_state = cur_state;
  1035. int next_char_idx = re_string_cur_idx (&mctx->input) + 1;
  1036. if (BE (next_char_idx >= mctx->input.bufs_len, 0)
  1037. || (BE (next_char_idx >= mctx->input.valid_len, 0)
  1038. && mctx->input.valid_len < mctx->input.len))
  1039. {
  1040. err = extend_buffers (mctx);
  1041. if (BE (err != REG_NOERROR, 0))
  1042. {
  1043. assert (err == REG_ESPACE);
  1044. return -2;
  1045. }
  1046. }
  1047. cur_state = transit_state (&err, mctx, cur_state);
  1048. if (mctx->state_log != NULL)
  1049. cur_state = merge_state_with_log (&err, mctx, cur_state);
  1050. if (cur_state == NULL)
  1051. {
  1052. /* Reached the invalid state or an error. Try to recover a valid
  1053. state using the state log, if available and if we have not
  1054. already found a valid (even if not the longest) match. */
  1055. if (BE (err != REG_NOERROR, 0))
  1056. return -2;
  1057. if (mctx->state_log == NULL
  1058. || (match && !fl_longest_match)
  1059. || (cur_state = find_recover_state (&err, mctx)) == NULL)
  1060. break;
  1061. }
  1062. if (BE (at_init_state, 0))
  1063. {
  1064. if (old_state == cur_state)
  1065. next_start_idx = next_char_idx;
  1066. else
  1067. at_init_state = 0;
  1068. }
  1069. if (cur_state->halt)
  1070. {
  1071. /* Reached a halt state.
  1072. Check the halt state can satisfy the current context. */
  1073. if (!cur_state->has_constraint
  1074. || check_halt_state_context (mctx, cur_state,
  1075. re_string_cur_idx (&mctx->input)))
  1076. {
  1077. /* We found an appropriate halt state. */
  1078. match_last = re_string_cur_idx (&mctx->input);
  1079. match = 1;
  1080. /* We found a match, do not modify match_first below. */
  1081. p_match_first = NULL;
  1082. if (!fl_longest_match)
  1083. break;
  1084. }
  1085. }
  1086. }
  1087. if (p_match_first)
  1088. *p_match_first += next_start_idx;
  1089. return match_last;
  1090. }
  1091. /* Check NODE match the current context. */
  1092. static int
  1093. internal_function
  1094. check_halt_node_context (const re_dfa_t *dfa, int node, unsigned int context)
  1095. {
  1096. re_token_type_t type = dfa->nodes[node].type;
  1097. unsigned int constraint = dfa->nodes[node].constraint;
  1098. if (type != END_OF_RE)
  1099. return 0;
  1100. if (!constraint)
  1101. return 1;
  1102. if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
  1103. return 0;
  1104. return 1;
  1105. }
  1106. /* Check the halt state STATE match the current context.
  1107. Return 0 if not match, if the node, STATE has, is a halt node and
  1108. match the context, return the node. */
  1109. static int
  1110. internal_function
  1111. check_halt_state_context (const re_match_context_t *mctx,
  1112. const re_dfastate_t *state, int idx)
  1113. {
  1114. int i;
  1115. unsigned int context;
  1116. #ifdef DEBUG
  1117. assert (state->halt);
  1118. #endif
  1119. context = re_string_context_at (&mctx->input, idx, mctx->eflags);
  1120. for (i = 0; i < state->nodes.nelem; ++i)
  1121. if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
  1122. return state->nodes.elems[i];
  1123. return 0;
  1124. }
  1125. /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
  1126. corresponding to the DFA).
  1127. Return the destination node, and update EPS_VIA_NODES, return -1 in case
  1128. of errors. */
  1129. static int
  1130. internal_function
  1131. proceed_next_node (const re_match_context_t *mctx, int nregs, regmatch_t *regs,
  1132. int *pidx, int node, re_node_set *eps_via_nodes,
  1133. struct re_fail_stack_t *fs)
  1134. {
  1135. const re_dfa_t *const dfa = mctx->dfa;
  1136. int i, err;
  1137. if (IS_EPSILON_NODE (dfa->nodes[node].type))
  1138. {
  1139. re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
  1140. re_node_set *edests = &dfa->edests[node];
  1141. int dest_node;
  1142. err = re_node_set_insert (eps_via_nodes, node);
  1143. if (BE (err < 0, 0))
  1144. return -2;
  1145. /* Pick up a valid destination, or return -1 if none is found. */
  1146. for (dest_node = -1, i = 0; i < edests->nelem; ++i)
  1147. {
  1148. int candidate = edests->elems[i];
  1149. if (!re_node_set_contains (cur_nodes, candidate))
  1150. continue;
  1151. if (dest_node == -1)
  1152. dest_node = candidate;
  1153. else
  1154. {
  1155. /* In order to avoid infinite loop like "(a*)*", return the second
  1156. epsilon-transition if the first was already considered. */
  1157. if (re_node_set_contains (eps_via_nodes, dest_node))
  1158. return candidate;
  1159. /* Otherwise, push the second epsilon-transition on the fail stack. */
  1160. else if (fs != NULL
  1161. && push_fail_stack (fs, *pidx, candidate, nregs, regs,
  1162. eps_via_nodes))
  1163. return -2;
  1164. /* We know we are going to exit. */
  1165. break;
  1166. }
  1167. }
  1168. return dest_node;
  1169. }
  1170. else
  1171. {
  1172. int naccepted = 0;
  1173. re_token_type_t type = dfa->nodes[node].type;
  1174. #ifdef RE_ENABLE_I18N
  1175. if (dfa->nodes[node].accept_mb)
  1176. naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
  1177. else
  1178. #endif /* RE_ENABLE_I18N */
  1179. if (type == OP_BACK_REF)
  1180. {
  1181. int subexp_idx = dfa->nodes[node].opr.idx + 1;
  1182. naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
  1183. if (fs != NULL)
  1184. {
  1185. if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
  1186. return -1;
  1187. else if (naccepted)
  1188. {
  1189. char *buf = (char *) re_string_get_buffer (&mctx->input);
  1190. if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
  1191. naccepted) != 0)
  1192. return -1;
  1193. }
  1194. }
  1195. if (naccepted == 0)
  1196. {
  1197. int dest_node;
  1198. err = re_node_set_insert (eps_via_nodes, node);
  1199. if (BE (err < 0, 0))
  1200. return -2;
  1201. dest_node = dfa->edests[node].elems[0];
  1202. if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
  1203. dest_node))
  1204. return dest_node;
  1205. }
  1206. }
  1207. if (naccepted != 0
  1208. || check_node_accept (mctx, dfa->nodes + node, *pidx))
  1209. {
  1210. int dest_node = dfa->nexts[node];
  1211. *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
  1212. if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
  1213. || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
  1214. dest_node)))
  1215. return -1;
  1216. re_node_set_empty (eps_via_nodes);
  1217. return dest_node;
  1218. }
  1219. }
  1220. return -1;
  1221. }
  1222. static reg_errcode_t
  1223. internal_function
  1224. push_fail_stack (struct re_fail_stack_t *fs, int str_idx, int dest_node,
  1225. int nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
  1226. {
  1227. reg_errcode_t err;
  1228. int num = fs->num++;
  1229. if (fs->num == fs->alloc)
  1230. {
  1231. struct re_fail_stack_ent_t *new_array;
  1232. new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
  1233. * fs->alloc * 2));
  1234. if (new_array == NULL)
  1235. return REG_ESPACE;
  1236. fs->alloc *= 2;
  1237. fs->stack = new_array;
  1238. }
  1239. fs->stack[num].idx = str_idx;
  1240. fs->stack[num].node = dest_node;
  1241. fs->stack[num].regs = re_malloc (regmatch_t, nregs);
  1242. if (fs->stack[num].regs == NULL)
  1243. return REG_ESPACE;
  1244. memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
  1245. err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
  1246. return err;
  1247. }
  1248. static int
  1249. internal_function
  1250. pop_fail_stack (struct re_fail_stack_t *fs, int *pidx, int nregs,
  1251. regmatch_t *regs, re_node_set *eps_via_nodes)
  1252. {
  1253. int num = --fs->num;
  1254. assert (num >= 0);
  1255. *pidx = fs->stack[num].idx;
  1256. memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
  1257. re_node_set_free (eps_via_nodes);
  1258. re_free (fs->stack[num].regs);
  1259. *eps_via_nodes = fs->stack[num].eps_via_nodes;
  1260. return fs->stack[num].node;
  1261. }
  1262. /* Set the positions where the subexpressions are starts/ends to registers
  1263. PMATCH.
  1264. Note: We assume that pmatch[0] is already set, and
  1265. pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
  1266. static reg_errcode_t
  1267. internal_function
  1268. set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
  1269. regmatch_t *pmatch, int fl_backtrack)
  1270. {
  1271. const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
  1272. int idx, cur_node;
  1273. re_node_set eps_via_nodes;
  1274. struct re_fail_stack_t *fs;
  1275. struct re_fail_stack_t fs_body = { 0, 2, NULL };
  1276. regmatch_t *prev_idx_match;
  1277. int prev_idx_match_malloced = 0;
  1278. #ifdef DEBUG
  1279. assert (nmatch > 1);
  1280. assert (mctx->state_log != NULL);
  1281. #endif
  1282. if (fl_backtrack)
  1283. {
  1284. fs = &fs_body;
  1285. fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
  1286. if (fs->stack == NULL)
  1287. return REG_ESPACE;
  1288. }
  1289. else
  1290. fs = NULL;
  1291. cur_node = dfa->init_node;
  1292. re_node_set_init_empty (&eps_via_nodes);
  1293. if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
  1294. prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
  1295. else
  1296. {
  1297. prev_idx_match = re_malloc (regmatch_t, nmatch);
  1298. if (prev_idx_match == NULL)
  1299. {
  1300. free_fail_stack_return (fs);
  1301. return REG_ESPACE;
  1302. }
  1303. prev_idx_match_malloced = 1;
  1304. }
  1305. memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
  1306. for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
  1307. {
  1308. update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
  1309. if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
  1310. {
  1311. int reg_idx;
  1312. if (fs)
  1313. {
  1314. for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
  1315. if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
  1316. break;
  1317. if (reg_idx == nmatch)
  1318. {
  1319. re_node_set_free (&eps_via_nodes);
  1320. if (prev_idx_match_malloced)
  1321. re_free (prev_idx_match);
  1322. return free_fail_stack_return (fs);
  1323. }
  1324. cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
  1325. &eps_via_nodes);
  1326. }
  1327. else
  1328. {
  1329. re_node_set_free (&eps_via_nodes);
  1330. if (prev_idx_match_malloced)
  1331. re_free (prev_idx_match);
  1332. return REG_NOERROR;
  1333. }
  1334. }
  1335. /* Proceed to next node. */
  1336. cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
  1337. &eps_via_nodes, fs);
  1338. if (BE (cur_node < 0, 0))
  1339. {
  1340. if (BE (cur_node == -2, 0))
  1341. {
  1342. re_node_set_free (&eps_via_nodes);
  1343. if (prev_idx_match_malloced)
  1344. re_free (prev_idx_match);
  1345. free_fail_stack_return (fs);
  1346. return REG_ESPACE;
  1347. }
  1348. if (fs)
  1349. cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
  1350. &eps_via_nodes);
  1351. else
  1352. {
  1353. re_node_set_free (&eps_via_nodes);
  1354. if (prev_idx_match_malloced)
  1355. re_free (prev_idx_match);
  1356. return REG_NOMATCH;
  1357. }
  1358. }
  1359. }
  1360. re_node_set_free (&eps_via_nodes);
  1361. if (prev_idx_match_malloced)
  1362. re_free (prev_idx_match);
  1363. return free_fail_stack_return (fs);
  1364. }
  1365. static reg_errcode_t
  1366. internal_function
  1367. free_fail_stack_return (struct re_fail_stack_t *fs)
  1368. {
  1369. if (fs)
  1370. {
  1371. int fs_idx;
  1372. for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
  1373. {
  1374. re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
  1375. re_free (fs->stack[fs_idx].regs);
  1376. }
  1377. re_free (fs->stack);
  1378. }
  1379. return REG_NOERROR;
  1380. }
  1381. static void
  1382. internal_function
  1383. update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
  1384. regmatch_t *prev_idx_match, int cur_node, int cur_idx, int nmatch)
  1385. {
  1386. int type = dfa->nodes[cur_node].type;
  1387. if (type == OP_OPEN_SUBEXP)
  1388. {
  1389. int reg_num = dfa->nodes[cur_node].opr.idx + 1;
  1390. /* We are at the first node of this sub expression. */
  1391. if (reg_num < nmatch)
  1392. {
  1393. pmatch[reg_num].rm_so = cur_idx;
  1394. pmatch[reg_num].rm_eo = -1;
  1395. }
  1396. }
  1397. else if (type == OP_CLOSE_SUBEXP)
  1398. {
  1399. int reg_num = dfa->nodes[cur_node].opr.idx + 1;
  1400. if (reg_num < nmatch)
  1401. {
  1402. /* We are at the last node of this sub expression. */
  1403. if (pmatch[reg_num].rm_so < cur_idx)
  1404. {
  1405. pmatch[reg_num].rm_eo = cur_idx;
  1406. /* This is a non-empty match or we are not inside an optional
  1407. subexpression. Accept this right away. */
  1408. memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
  1409. }
  1410. else
  1411. {
  1412. if (dfa->nodes[cur_node].opt_subexp
  1413. && prev_idx_match[reg_num].rm_so != -1)
  1414. /* We transited through an empty match for an optional
  1415. subexpression, like (a?)*, and this is not the subexp's
  1416. first match. Copy back the old content of the registers
  1417. so that matches of an inner subexpression are undone as
  1418. well, like in ((a?))*. */
  1419. memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
  1420. else
  1421. /* We completed a subexpression, but it may be part of
  1422. an optional one, so do not update PREV_IDX_MATCH. */
  1423. pmatch[reg_num].rm_eo = cur_idx;
  1424. }
  1425. }
  1426. }
  1427. }
  1428. /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
  1429. and sift the nodes in each states according to the following rules.
  1430. Updated state_log will be wrote to STATE_LOG.
  1431. Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
  1432. 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
  1433. If `a' isn't the LAST_NODE and `a' can't epsilon transit to
  1434. the LAST_NODE, we throw away the node `a'.
  1435. 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
  1436. string `s' and transit to `b':
  1437. i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
  1438. away the node `a'.
  1439. ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
  1440. thrown away, we throw away the node `a'.
  1441. 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
  1442. i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
  1443. node `a'.
  1444. ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
  1445. we throw away the node `a'. */
  1446. #define STATE_NODE_CONTAINS(state,node) \
  1447. ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
  1448. static reg_errcode_t
  1449. internal_function
  1450. sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
  1451. {
  1452. reg_errcode_t err;
  1453. int null_cnt = 0;
  1454. int str_idx = sctx->last_str_idx;
  1455. re_node_set cur_dest;
  1456. #ifdef DEBUG
  1457. assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
  1458. #endif
  1459. /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
  1460. transit to the last_node and the last_node itself. */
  1461. err = re_node_set_init_1 (&cur_dest, sctx->last_node);
  1462. if (BE (err != REG_NOERROR, 0))
  1463. return err;
  1464. err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
  1465. if (BE (err != REG_NOERROR, 0))
  1466. goto free_return;
  1467. /* Then check each states in the state_log. */
  1468. while (str_idx > 0)
  1469. {
  1470. /* Update counters. */
  1471. null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
  1472. if (null_cnt > mctx->max_mb_elem_len)
  1473. {
  1474. memset (sctx->sifted_states, '\0',
  1475. sizeof (re_dfastate_t *) * str_idx);
  1476. re_node_set_free (&cur_dest);
  1477. return REG_NOERROR;
  1478. }
  1479. re_node_set_empty (&cur_dest);
  1480. --str_idx;
  1481. if (mctx->state_log[str_idx])
  1482. {
  1483. err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
  1484. if (BE (err != REG_NOERROR, 0))
  1485. goto free_return;
  1486. }
  1487. /* Add all the nodes which satisfy the following conditions:
  1488. - It can epsilon transit to a node in CUR_DEST.
  1489. - It is in CUR_SRC.
  1490. And update state_log. */
  1491. err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
  1492. if (BE (err != REG_NOERROR, 0))
  1493. goto free_return;
  1494. }
  1495. err = REG_NOERROR;
  1496. free_return:
  1497. re_node_set_free (&cur_dest);
  1498. return err;
  1499. }
  1500. static reg_errcode_t
  1501. internal_function
  1502. build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
  1503. int str_idx, re_node_set *cur_dest)
  1504. {
  1505. const re_dfa_t *const dfa = mctx->dfa;
  1506. const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
  1507. int i;
  1508. /* Then build the next sifted state.
  1509. We build the next sifted state on `cur_dest', and update
  1510. `sifted_states[str_idx]' with `cur_dest'.
  1511. Note:
  1512. `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
  1513. `cur_src' points the node_set of the old `state_log[str_idx]'
  1514. (with the epsilon nodes pre-filtered out). */
  1515. for (i = 0; i < cur_src->nelem; i++)
  1516. {
  1517. int prev_node = cur_src->elems[i];
  1518. int naccepted = 0;
  1519. int ret;
  1520. #ifdef DEBUG
  1521. re_token_type_t type = dfa->nodes[prev_node].type;
  1522. assert (!IS_EPSILON_NODE (type));
  1523. #endif
  1524. #ifdef RE_ENABLE_I18N
  1525. /* If the node may accept `multi byte'. */
  1526. if (dfa->nodes[prev_node].accept_mb)
  1527. naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
  1528. str_idx, sctx->last_str_idx);
  1529. #endif /* RE_ENABLE_I18N */
  1530. /* We don't check backreferences here.
  1531. See update_cur_sifted_state(). */
  1532. if (!naccepted
  1533. && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
  1534. && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
  1535. dfa->nexts[prev_node]))
  1536. naccepted = 1;
  1537. if (naccepted == 0)
  1538. continue;
  1539. if (sctx->limits.nelem)
  1540. {
  1541. int to_idx = str_idx + naccepted;
  1542. if (check_dst_limits (mctx, &sctx->limits,
  1543. dfa->nexts[prev_node], to_idx,
  1544. prev_node, str_idx))
  1545. continue;
  1546. }
  1547. ret = re_node_set_insert (cur_dest, prev_node);
  1548. if (BE (ret == -1, 0))
  1549. return REG_ESPACE;
  1550. }
  1551. return REG_NOERROR;
  1552. }
  1553. /* Helper functions. */
  1554. static reg_errcode_t
  1555. internal_function
  1556. clean_state_log_if_needed (re_match_context_t *mctx, int next_state_log_idx)
  1557. {
  1558. int top = mctx->state_log_top;
  1559. if (next_state_log_idx >= mctx->input.bufs_len
  1560. || (next_state_log_idx >= mctx->input.valid_len
  1561. && mctx->input.valid_len < mctx->input.len))
  1562. {
  1563. reg_errcode_t err;
  1564. err = extend_buffers (mctx);
  1565. if (BE (err != REG_NOERROR, 0))
  1566. return err;
  1567. }
  1568. if (top < next_state_log_idx)
  1569. {
  1570. memset (mctx->state_log + top + 1, '\0',
  1571. sizeof (re_dfastate_t *) * (next_state_log_idx - top));
  1572. mctx->state_log_top = next_state_log_idx;
  1573. }
  1574. return REG_NOERROR;
  1575. }
  1576. static reg_errcode_t
  1577. internal_function
  1578. merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
  1579. re_dfastate_t **src, int num)
  1580. {
  1581. int st_idx;
  1582. reg_errcode_t err;
  1583. for (st_idx = 0; st_idx < num; ++st_idx)
  1584. {
  1585. if (dst[st_idx] == NULL)
  1586. dst[st_idx] = src[st_idx];
  1587. else if (src[st_idx] != NULL)
  1588. {
  1589. re_node_set merged_set;
  1590. err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
  1591. &src[st_idx]->nodes);
  1592. if (BE (err != REG_NOERROR, 0))
  1593. return err;
  1594. dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
  1595. re_node_set_free (&merged_set);
  1596. if (BE (err != REG_NOERROR, 0))
  1597. return err;
  1598. }
  1599. }
  1600. return REG_NOERROR;
  1601. }
  1602. static reg_errcode_t
  1603. internal_function
  1604. update_cur_sifted_state (const re_match_context_t *mctx,
  1605. re_sift_context_t *sctx, int str_idx,
  1606. re_node_set *dest_nodes)
  1607. {
  1608. const re_dfa_t *const dfa = mctx->dfa;
  1609. reg_errcode_t err = REG_NOERROR;
  1610. const re_node_set *candidates;
  1611. candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
  1612. : &mctx->state_log[str_idx]->nodes);
  1613. if (dest_nodes->nelem == 0)
  1614. sctx->sifted_states[str_idx] = NULL;
  1615. else
  1616. {
  1617. if (candidates)
  1618. {
  1619. /* At first, add the nodes which can epsilon transit to a node in
  1620. DEST_NODE. */
  1621. err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
  1622. if (BE (err != REG_NOERROR, 0))
  1623. return err;
  1624. /* Then, check the limitations in the current sift_context. */
  1625. if (sctx->limits.nelem)
  1626. {
  1627. err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
  1628. mctx->bkref_ents, str_idx);
  1629. if (BE (err != REG_NOERROR, 0))
  1630. return err;
  1631. }
  1632. }
  1633. sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
  1634. if (BE (err != REG_NOERROR, 0))
  1635. return err;
  1636. }
  1637. if (candidates && mctx->state_log[str_idx]->has_backref)
  1638. {
  1639. err = sift_states_bkref (mctx, sctx, str_idx, candidates);
  1640. if (BE (err != REG_NOERROR, 0))
  1641. return err;
  1642. }
  1643. return REG_NOERROR;
  1644. }
  1645. static reg_errcode_t
  1646. internal_function
  1647. add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
  1648. const re_node_set *candidates)
  1649. {
  1650. reg_errcode_t err = REG_NOERROR;
  1651. int i;
  1652. re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
  1653. if (BE (err != REG_NOERROR, 0))
  1654. return err;
  1655. if (!state->inveclosure.alloc)
  1656. {
  1657. err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
  1658. if (BE (err != REG_NOERROR, 0))
  1659. return REG_ESPACE;
  1660. for (i = 0; i < dest_nodes->nelem; i++)
  1661. re_node_set_merge (&state->inveclosure,
  1662. dfa->inveclosures + dest_nodes->elems[i]);
  1663. }
  1664. return re_node_set_add_intersect (dest_nodes, candidates,
  1665. &state->inveclosure);
  1666. }
  1667. static reg_errcode_t
  1668. internal_function
  1669. sub_epsilon_src_nodes (const re_dfa_t *dfa, int node, re_node_set *dest_nodes,
  1670. const re_node_set *candidates)
  1671. {
  1672. int ecl_idx;
  1673. reg_errcode_t err;
  1674. re_node_set *inv_eclosure = dfa->inveclosures + node;
  1675. re_node_set except_nodes;
  1676. re_node_set_init_empty (&except_nodes);
  1677. for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
  1678. {
  1679. int cur_node = inv_eclosure->elems[ecl_idx];
  1680. if (cur_node == node)
  1681. continue;
  1682. if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
  1683. {
  1684. int edst1 = dfa->edests[cur_node].elems[0];
  1685. int edst2 = ((dfa->edests[cur_node].nelem > 1)
  1686. ? dfa->edests[cur_node].elems[1] : -1);
  1687. if ((!re_node_set_contains (inv_eclosure, edst1)
  1688. && re_node_set_contains (dest_nodes, edst1))
  1689. || (edst2 > 0
  1690. && !re_node_set_contains (inv_eclosure, edst2)
  1691. && re_node_set_contains (dest_nodes, edst2)))
  1692. {
  1693. err = re_node_set_add_intersect (&except_nodes, candidates,
  1694. dfa->inveclosures + cur_node);
  1695. if (BE (err != REG_NOERROR, 0))
  1696. {
  1697. re_node_set_free (&except_nodes);
  1698. return err;
  1699. }
  1700. }
  1701. }
  1702. }
  1703. for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
  1704. {
  1705. int cur_node = inv_eclosure->elems[ecl_idx];
  1706. if (!re_node_set_contains (&except_nodes, cur_node))
  1707. {
  1708. int idx = re_node_set_contains (dest_nodes, cur_node) - 1;
  1709. re_node_set_remove_at (dest_nodes, idx);
  1710. }
  1711. }
  1712. re_node_set_free (&except_nodes);
  1713. return REG_NOERROR;
  1714. }
  1715. static int
  1716. internal_function
  1717. check_dst_limits (const re_match_context_t *mctx, re_node_set *limits,
  1718. int dst_node, int dst_idx, int src_node, int src_idx)
  1719. {
  1720. const re_dfa_t *const dfa = mctx->dfa;
  1721. int lim_idx, src_pos, dst_pos;
  1722. int dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
  1723. int src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
  1724. for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
  1725. {
  1726. int subexp_idx;
  1727. struct re_backref_cache_entry *ent;
  1728. ent = mctx->bkref_ents + limits->elems[lim_idx];
  1729. subexp_idx = dfa->nodes[ent->node].opr.idx;
  1730. dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
  1731. subexp_idx, dst_node, dst_idx,
  1732. dst_bkref_idx);
  1733. src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
  1734. subexp_idx, src_node, src_idx,
  1735. src_bkref_idx);
  1736. /* In case of:
  1737. <src> <dst> ( <subexp> )
  1738. ( <subexp> ) <src> <dst>
  1739. ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
  1740. if (src_pos == dst_pos)
  1741. continue; /* This is unrelated limitation. */
  1742. else
  1743. return 1;
  1744. }
  1745. return 0;
  1746. }
  1747. static int
  1748. internal_function
  1749. check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
  1750. int subexp_idx, int from_node, int bkref_idx)
  1751. {
  1752. const re_dfa_t *const dfa = mctx->dfa;
  1753. const re_node_set *eclosures = dfa->eclosures + from_node;
  1754. int node_idx;
  1755. /* Else, we are on the boundary: examine the nodes on the epsilon
  1756. closure. */
  1757. for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
  1758. {
  1759. int node = eclosures->elems[node_idx];
  1760. switch (dfa->nodes[node].type)
  1761. {
  1762. case OP_BACK_REF:
  1763. if (bkref_idx != -1)
  1764. {
  1765. struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
  1766. do
  1767. {
  1768. int dst, cpos;
  1769. if (ent->node != node)
  1770. continue;
  1771. if (subexp_idx < BITSET_WORD_BITS
  1772. && !(ent->eps_reachable_subexps_map
  1773. & ((bitset_word_t) 1 << subexp_idx)))
  1774. continue;
  1775. /* Recurse trying to reach the OP_OPEN_SUBEXP and
  1776. OP_CLOSE_SUBEXP cases below. But, if the
  1777. destination node is the same node as the source
  1778. node, don't recurse because it would cause an
  1779. infinite loop: a regex that exhibits this behavior
  1780. is ()\1*\1* */
  1781. dst = dfa->edests[node].elems[0];
  1782. if (dst == from_node)
  1783. {
  1784. if (boundaries & 1)
  1785. return -1;
  1786. else /* if (boundaries & 2) */
  1787. return 0;
  1788. }
  1789. cpos =
  1790. check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
  1791. dst, bkref_idx);
  1792. if (cpos == -1 /* && (boundaries & 1) */)
  1793. return -1;
  1794. if (cpos == 0 && (boundaries & 2))
  1795. return 0;
  1796. if (subexp_idx < BITSET_WORD_BITS)
  1797. ent->eps_reachable_subexps_map
  1798. &= ~((bitset_word_t) 1 << subexp_idx);
  1799. }
  1800. while (ent++->more);
  1801. }
  1802. break;
  1803. case OP_OPEN_SUBEXP:
  1804. if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
  1805. return -1;
  1806. break;
  1807. case OP_CLOSE_SUBEXP:
  1808. if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
  1809. return 0;
  1810. break;
  1811. default:
  1812. break;
  1813. }
  1814. }
  1815. return (boundaries & 2) ? 1 : 0;
  1816. }
  1817. static int
  1818. internal_function
  1819. check_dst_limits_calc_pos (const re_match_context_t *mctx, int limit,
  1820. int subexp_idx, int from_node, int str_idx,
  1821. int bkref_idx)
  1822. {
  1823. struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
  1824. int boundaries;
  1825. /* If we are outside the range of the subexpression, return -1 or 1. */
  1826. if (str_idx < lim->subexp_from)
  1827. return -1;
  1828. if (lim->subexp_to < str_idx)
  1829. return 1;
  1830. /* If we are within the subexpression, return 0. */
  1831. boundaries = (str_idx == lim->subexp_from);
  1832. boundaries |= (str_idx == lim->subexp_to) << 1;
  1833. if (boundaries == 0)
  1834. return 0;
  1835. /* Else, examine epsilon closure. */
  1836. return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
  1837. from_node, bkref_idx);
  1838. }
  1839. /* Check the limitations of sub expressions LIMITS, and remove the nodes
  1840. which are against limitations from DEST_NODES. */
  1841. static reg_errcode_t
  1842. internal_function
  1843. check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
  1844. const re_node_set *candidates, re_node_set *limits,
  1845. struct re_backref_cache_entry *bkref_ents, int str_idx)
  1846. {
  1847. reg_errcode_t err;
  1848. int node_idx, lim_idx;
  1849. for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
  1850. {
  1851. int subexp_idx;
  1852. struct re_backref_cache_entry *ent;
  1853. ent = bkref_ents + limits->elems[lim_idx];
  1854. if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
  1855. continue; /* This is unrelated limitation. */
  1856. subexp_idx = dfa->nodes[ent->node].opr.idx;
  1857. if (ent->subexp_to == str_idx)
  1858. {
  1859. int ops_node = -1;
  1860. int cls_node = -1;
  1861. for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
  1862. {
  1863. int node = dest_nodes->elems[node_idx];
  1864. re_token_type_t type = dfa->nodes[node].type;
  1865. if (type == OP_OPEN_SUBEXP
  1866. && subexp_idx == dfa->nodes[node].opr.idx)
  1867. ops_node = node;
  1868. else if (type == OP_CLOSE_SUBEXP
  1869. && subexp_idx == dfa->nodes[node].opr.idx)
  1870. cls_node = node;
  1871. }
  1872. /* Check the limitation of the open subexpression. */
  1873. /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
  1874. if (ops_node >= 0)
  1875. {
  1876. err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
  1877. candidates);
  1878. if (BE (err != REG_NOERROR, 0))
  1879. return err;
  1880. }
  1881. /* Check the limitation of the close subexpression. */
  1882. if (cls_node >= 0)
  1883. for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
  1884. {
  1885. int node = dest_nodes->elems[node_idx];
  1886. if (!re_node_set_contains (dfa->inveclosures + node,
  1887. cls_node)
  1888. && !re_node_set_contains (dfa->eclosures + node,
  1889. cls_node))
  1890. {
  1891. /* It is against this limitation.
  1892. Remove it form the current sifted state. */
  1893. err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
  1894. candidates);
  1895. if (BE (err != REG_NOERROR, 0))
  1896. return err;
  1897. --node_idx;
  1898. }
  1899. }
  1900. }
  1901. else /* (ent->subexp_to != str_idx) */
  1902. {
  1903. for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
  1904. {
  1905. int node = dest_nodes->elems[node_idx];
  1906. re_token_type_t type = dfa->nodes[node].type;
  1907. if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
  1908. {
  1909. if (subexp_idx != dfa->nodes[node].opr.idx)
  1910. continue;
  1911. /* It is against this limitation.
  1912. Remove it form the current sifted state. */
  1913. err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
  1914. candidates);
  1915. if (BE (err != REG_NOERROR, 0))
  1916. return err;
  1917. }
  1918. }
  1919. }
  1920. }
  1921. return REG_NOERROR;
  1922. }
  1923. static reg_errcode_t
  1924. internal_function
  1925. sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
  1926. int str_idx, const re_node_set *candidates)
  1927. {
  1928. const re_dfa_t *const dfa = mctx->dfa;
  1929. reg_errcode_t err;
  1930. int node_idx, node;
  1931. re_sift_context_t local_sctx;
  1932. int first_idx = search_cur_bkref_entry (mctx, str_idx);
  1933. if (first_idx == -1)
  1934. return REG_NOERROR;
  1935. local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
  1936. for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
  1937. {
  1938. int enabled_idx;
  1939. re_token_type_t type;
  1940. struct re_backref_cache_entry *entry;
  1941. node = candidates->elems[node_idx];
  1942. type = dfa->nodes[node].type;
  1943. /* Avoid infinite loop for the REs like "()\1+". */
  1944. if (node == sctx->last_node && str_idx == sctx->last_str_idx)
  1945. continue;
  1946. if (type != OP_BACK_REF)
  1947. continue;
  1948. entry = mctx->bkref_ents + first_idx;
  1949. enabled_idx = first_idx;
  1950. do
  1951. {
  1952. int subexp_len;
  1953. int to_idx;
  1954. int dst_node;
  1955. int ret;
  1956. re_dfastate_t *cur_state;
  1957. if (entry->node != node)
  1958. continue;
  1959. subexp_len = entry->subexp_to - entry->subexp_from;
  1960. to_idx = str_idx + subexp_len;
  1961. dst_node = (subexp_len ? dfa->nexts[node]
  1962. : dfa->edests[node].elems[0]);
  1963. if (to_idx > sctx->last_str_idx
  1964. || sctx->sifted_states[to_idx] == NULL
  1965. || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
  1966. || check_dst_limits (mctx, &sctx->limits, node,
  1967. str_idx, dst_node, to_idx))
  1968. continue;
  1969. if (local_sctx.sifted_states == NULL)
  1970. {
  1971. local_sctx = *sctx;
  1972. err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
  1973. if (BE (err != REG_NOERROR, 0))
  1974. goto free_return;
  1975. }
  1976. local_sctx.last_node = node;
  1977. local_sctx.last_str_idx = str_idx;
  1978. ret = re_node_set_insert (&local_sctx.limits, enabled_idx);
  1979. if (BE (ret < 0, 0))
  1980. {
  1981. err = REG_ESPACE;
  1982. goto free_return;
  1983. }
  1984. cur_state = local_sctx.sifted_states[str_idx];
  1985. err = sift_states_backward (mctx, &local_sctx);
  1986. if (BE (err != REG_NOERROR, 0))
  1987. goto free_return;
  1988. if (sctx->limited_states != NULL)
  1989. {
  1990. err = merge_state_array (dfa, sctx->limited_states,
  1991. local_sctx.sifted_states,
  1992. str_idx + 1);
  1993. if (BE (err != REG_NOERROR, 0))
  1994. goto free_return;
  1995. }
  1996. local_sctx.sifted_states[str_idx] = cur_state;
  1997. re_node_set_remove (&local_sctx.limits, enabled_idx);
  1998. /* mctx->bkref_ents may have changed, reload the pointer. */
  1999. entry = mctx->bkref_ents + enabled_idx;
  2000. }
  2001. while (enabled_idx++, entry++->more);
  2002. }
  2003. err = REG_NOERROR;
  2004. free_return:
  2005. if (local_sctx.sifted_states != NULL)
  2006. {
  2007. re_node_set_free (&local_sctx.limits);
  2008. }
  2009. return err;
  2010. }
  2011. #ifdef RE_ENABLE_I18N
  2012. static int
  2013. internal_function
  2014. sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
  2015. int node_idx, int str_idx, int max_str_idx)
  2016. {
  2017. const re_dfa_t *const dfa = mctx->dfa;
  2018. int naccepted;
  2019. /* Check the node can accept `multi byte'. */
  2020. naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
  2021. if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
  2022. !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
  2023. dfa->nexts[node_idx]))
  2024. /* The node can't accept the `multi byte', or the
  2025. destination was already thrown away, then the node
  2026. could't accept the current input `multi byte'. */
  2027. naccepted = 0;
  2028. /* Otherwise, it is sure that the node could accept
  2029. `naccepted' bytes input. */
  2030. return naccepted;
  2031. }
  2032. #endif /* RE_ENABLE_I18N */
  2033. /* Functions for state transition. */
  2034. /* Return the next state to which the current state STATE will transit by
  2035. accepting the current input byte, and update STATE_LOG if necessary.
  2036. If STATE can accept a multibyte char/collating element/back reference
  2037. update the destination of STATE_LOG. */
  2038. static re_dfastate_t *
  2039. internal_function
  2040. transit_state (reg_errcode_t *err, re_match_context_t *mctx,
  2041. re_dfastate_t *state)
  2042. {
  2043. re_dfastate_t **trtable;
  2044. unsigned char ch;
  2045. #ifdef RE_ENABLE_I18N
  2046. /* If the current state can accept multibyte. */
  2047. if (BE (state->accept_mb, 0))
  2048. {
  2049. *err = transit_state_mb (mctx, state);
  2050. if (BE (*err != REG_NOERROR, 0))
  2051. return NULL;
  2052. }
  2053. #endif /* RE_ENABLE_I18N */
  2054. /* Then decide the next state with the single byte. */
  2055. #if 0
  2056. if (0)
  2057. /* don't use transition table */
  2058. return transit_state_sb (err, mctx, state);
  2059. #endif
  2060. /* Use transition table */
  2061. ch = re_string_fetch_byte (&mctx->input);
  2062. for (;;)
  2063. {
  2064. trtable = state->trtable;
  2065. if (BE (trtable != NULL, 1))
  2066. return trtable[ch];
  2067. trtable = state->word_trtable;
  2068. if (BE (trtable != NULL, 1))
  2069. {
  2070. unsigned int context;
  2071. context
  2072. = re_string_context_at (&mctx->input,
  2073. re_string_cur_idx (&mctx->input) - 1,
  2074. mctx->eflags);
  2075. if (IS_WORD_CONTEXT (context))
  2076. return trtable[ch + SBC_MAX];
  2077. else
  2078. return trtable[ch];
  2079. }
  2080. if (!build_trtable (mctx->dfa, state))
  2081. {
  2082. *err = REG_ESPACE;
  2083. return NULL;
  2084. }
  2085. /* Retry, we now have a transition table. */
  2086. }
  2087. }
  2088. /* Update the state_log if we need */
  2089. re_dfastate_t *
  2090. internal_function
  2091. merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
  2092. re_dfastate_t *next_state)
  2093. {
  2094. const re_dfa_t *const dfa = mctx->dfa;
  2095. int cur_idx = re_string_cur_idx (&mctx->input);
  2096. if (cur_idx > mctx->state_log_top)
  2097. {
  2098. mctx->state_log[cur_idx] = next_state;
  2099. mctx->state_log_top = cur_idx;
  2100. }
  2101. else if (mctx->state_log[cur_idx] == 0)
  2102. {
  2103. mctx->state_log[cur_idx] = next_state;
  2104. }
  2105. else
  2106. {
  2107. re_dfastate_t *pstate;
  2108. unsigned int context;
  2109. re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
  2110. /* If (state_log[cur_idx] != 0), it implies that cur_idx is
  2111. the destination of a multibyte char/collating element/
  2112. back reference. Then the next state is the union set of
  2113. these destinations and the results of the transition table. */
  2114. pstate = mctx->state_log[cur_idx];
  2115. log_nodes = pstate->entrance_nodes;
  2116. if (next_state != NULL)
  2117. {
  2118. table_nodes = next_state->entrance_nodes;
  2119. *err = re_node_set_init_union (&next_nodes, table_nodes,
  2120. log_nodes);
  2121. if (BE (*err != REG_NOERROR, 0))
  2122. return NULL;
  2123. }
  2124. else
  2125. next_nodes = *log_nodes;
  2126. /* Note: We already add the nodes of the initial state,
  2127. then we don't need to add them here. */
  2128. context = re_string_context_at (&mctx->input,
  2129. re_string_cur_idx (&mctx->input) - 1,
  2130. mctx->eflags);
  2131. next_state = mctx->state_log[cur_idx]
  2132. = re_acquire_state_context (err, dfa, &next_nodes, context);
  2133. /* We don't need to check errors here, since the return value of
  2134. this function is next_state and ERR is already set. */
  2135. if (table_nodes != NULL)
  2136. re_node_set_free (&next_nodes);
  2137. }
  2138. if (BE (dfa->nbackref, 0) && next_state != NULL)
  2139. {
  2140. /* Check OP_OPEN_SUBEXP in the current state in case that we use them
  2141. later. We must check them here, since the back references in the
  2142. next state might use them. */
  2143. *err = check_subexp_matching_top (mctx, &next_state->nodes,
  2144. cur_idx);
  2145. if (BE (*err != REG_NOERROR, 0))
  2146. return NULL;
  2147. /* If the next state has back references. */
  2148. if (next_state->has_backref)
  2149. {
  2150. *err = transit_state_bkref (mctx, &next_state->nodes);
  2151. if (BE (*err != REG_NOERROR, 0))
  2152. return NULL;
  2153. next_state = mctx->state_log[cur_idx];
  2154. }
  2155. }
  2156. return next_state;
  2157. }
  2158. /* Skip bytes in the input that correspond to part of a
  2159. multi-byte match, then look in the log for a state
  2160. from which to restart matching. */
  2161. re_dfastate_t *
  2162. internal_function
  2163. find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
  2164. {
  2165. re_dfastate_t *cur_state;
  2166. do
  2167. {
  2168. int max = mctx->state_log_top;
  2169. int cur_str_idx = re_string_cur_idx (&mctx->input);
  2170. do
  2171. {
  2172. if (++cur_str_idx > max)
  2173. return NULL;
  2174. re_string_skip_bytes (&mctx->input, 1);
  2175. }
  2176. while (mctx->state_log[cur_str_idx] == NULL);
  2177. cur_state = merge_state_with_log (err, mctx, NULL);
  2178. }
  2179. while (*err == REG_NOERROR && cur_state == NULL);
  2180. return cur_state;
  2181. }
  2182. /* Helper functions for transit_state. */
  2183. /* From the node set CUR_NODES, pick up the nodes whose types are
  2184. OP_OPEN_SUBEXP and which have corresponding back references in the regular
  2185. expression. And register them to use them later for evaluating the
  2186. correspoding back references. */
  2187. static reg_errcode_t
  2188. internal_function
  2189. check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
  2190. int str_idx)
  2191. {
  2192. const re_dfa_t *const dfa = mctx->dfa;
  2193. int node_idx;
  2194. reg_errcode_t err;
  2195. /* TODO: This isn't efficient.
  2196. Because there might be more than one nodes whose types are
  2197. OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
  2198. nodes.
  2199. E.g. RE: (a){2} */
  2200. for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
  2201. {
  2202. int node = cur_nodes->elems[node_idx];
  2203. if (dfa->nodes[node].type == OP_OPEN_SUBEXP
  2204. && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
  2205. && (dfa->used_bkref_map
  2206. & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
  2207. {
  2208. err = match_ctx_add_subtop (mctx, node, str_idx);
  2209. if (BE (err != REG_NOERROR, 0))
  2210. return err;
  2211. }
  2212. }
  2213. return REG_NOERROR;
  2214. }
  2215. #if 0
  2216. /* Return the next state to which the current state STATE will transit by
  2217. accepting the current input byte. */
  2218. static re_dfastate_t *
  2219. transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
  2220. re_dfastate_t *state)
  2221. {
  2222. const re_dfa_t *const dfa = mctx->dfa;
  2223. re_node_set next_nodes;
  2224. re_dfastate_t *next_state;
  2225. int node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
  2226. unsigned int context;
  2227. *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
  2228. if (BE (*err != REG_NOERROR, 0))
  2229. return NULL;
  2230. for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
  2231. {
  2232. int cur_node = state->nodes.elems[node_cnt];
  2233. if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
  2234. {
  2235. *err = re_node_set_merge (&next_nodes,
  2236. dfa->eclosures + dfa->nexts[cur_node]);
  2237. if (BE (*err != REG_NOERROR, 0))
  2238. {
  2239. re_node_set_free (&next_nodes);
  2240. return NULL;
  2241. }
  2242. }
  2243. }
  2244. context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
  2245. next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
  2246. /* We don't need to check errors here, since the return value of
  2247. this function is next_state and ERR is already set. */
  2248. re_node_set_free (&next_nodes);
  2249. re_string_skip_bytes (&mctx->input, 1);
  2250. return next_state;
  2251. }
  2252. #endif
  2253. #ifdef RE_ENABLE_I18N
  2254. static reg_errcode_t
  2255. internal_function
  2256. transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
  2257. {
  2258. const re_dfa_t *const dfa = mctx->dfa;
  2259. reg_errcode_t err;
  2260. int i;
  2261. for (i = 0; i < pstate->nodes.nelem; ++i)
  2262. {
  2263. re_node_set dest_nodes, *new_nodes;
  2264. int cur_node_idx = pstate->nodes.elems[i];
  2265. int naccepted, dest_idx;
  2266. unsigned int context;
  2267. re_dfastate_t *dest_state;
  2268. if (!dfa->nodes[cur_node_idx].accept_mb)
  2269. continue;
  2270. if (dfa->nodes[cur_node_idx].constraint)
  2271. {
  2272. context = re_string_context_at (&mctx->input,
  2273. re_string_cur_idx (&mctx->input),
  2274. mctx->eflags);
  2275. if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
  2276. context))
  2277. continue;
  2278. }
  2279. /* How many bytes the node can accept? */
  2280. naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
  2281. re_string_cur_idx (&mctx->input));
  2282. if (naccepted == 0)
  2283. continue;
  2284. /* The node can accepts `naccepted' bytes. */
  2285. dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
  2286. mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
  2287. : mctx->max_mb_elem_len);
  2288. err = clean_state_log_if_needed (mctx, dest_idx);
  2289. if (BE (err != REG_NOERROR, 0))
  2290. return err;
  2291. #ifdef DEBUG
  2292. assert (dfa->nexts[cur_node_idx] != -1);
  2293. #endif
  2294. new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
  2295. dest_state = mctx->state_log[dest_idx];
  2296. if (dest_state == NULL)
  2297. dest_nodes = *new_nodes;
  2298. else
  2299. {
  2300. err = re_node_set_init_union (&dest_nodes,
  2301. dest_state->entrance_nodes, new_nodes);
  2302. if (BE (err != REG_NOERROR, 0))
  2303. return err;
  2304. }
  2305. context = re_string_context_at (&mctx->input, dest_idx - 1,
  2306. mctx->eflags);
  2307. mctx->state_log[dest_idx]
  2308. = re_acquire_state_context (&err, dfa, &dest_nodes, context);
  2309. if (dest_state != NULL)
  2310. re_node_set_free (&dest_nodes);
  2311. if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
  2312. return err;
  2313. }
  2314. return REG_NOERROR;
  2315. }
  2316. #endif /* RE_ENABLE_I18N */
  2317. static reg_errcode_t
  2318. internal_function
  2319. transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
  2320. {
  2321. const re_dfa_t *const dfa = mctx->dfa;
  2322. reg_errcode_t err;
  2323. int i;
  2324. int cur_str_idx = re_string_cur_idx (&mctx->input);
  2325. for (i = 0; i < nodes->nelem; ++i)
  2326. {
  2327. int dest_str_idx, prev_nelem, bkc_idx;
  2328. int node_idx = nodes->elems[i];
  2329. unsigned int context;
  2330. const re_token_t *node = dfa->nodes + node_idx;
  2331. re_node_set *new_dest_nodes;
  2332. /* Check whether `node' is a backreference or not. */
  2333. if (node->type != OP_BACK_REF)
  2334. continue;
  2335. if (node->constraint)
  2336. {
  2337. context = re_string_context_at (&mctx->input, cur_str_idx,
  2338. mctx->eflags);
  2339. if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
  2340. continue;
  2341. }
  2342. /* `node' is a backreference.
  2343. Check the substring which the substring matched. */
  2344. bkc_idx = mctx->nbkref_ents;
  2345. err = get_subexp (mctx, node_idx, cur_str_idx);
  2346. if (BE (err != REG_NOERROR, 0))
  2347. goto free_return;
  2348. /* And add the epsilon closures (which is `new_dest_nodes') of
  2349. the backreference to appropriate state_log. */
  2350. #ifdef DEBUG
  2351. assert (dfa->nexts[node_idx] != -1);
  2352. #endif
  2353. for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
  2354. {
  2355. int subexp_len;
  2356. re_dfastate_t *dest_state;
  2357. struct re_backref_cache_entry *bkref_ent;
  2358. bkref_ent = mctx->bkref_ents + bkc_idx;
  2359. if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
  2360. continue;
  2361. subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
  2362. new_dest_nodes = (subexp_len == 0
  2363. ? dfa->eclosures + dfa->edests[node_idx].elems[0]
  2364. : dfa->eclosures + dfa->nexts[node_idx]);
  2365. dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
  2366. - bkref_ent->subexp_from);
  2367. context = re_string_context_at (&mctx->input, dest_str_idx - 1,
  2368. mctx->eflags);
  2369. dest_state = mctx->state_log[dest_str_idx];
  2370. prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
  2371. : mctx->state_log[cur_str_idx]->nodes.nelem);
  2372. /* Add `new_dest_node' to state_log. */
  2373. if (dest_state == NULL)
  2374. {
  2375. mctx->state_log[dest_str_idx]
  2376. = re_acquire_state_context (&err, dfa, new_dest_nodes,
  2377. context);
  2378. if (BE (mctx->state_log[dest_str_idx] == NULL
  2379. && err != REG_NOERROR, 0))
  2380. goto free_return;
  2381. }
  2382. else
  2383. {
  2384. re_node_set dest_nodes;
  2385. err = re_node_set_init_union (&dest_nodes,
  2386. dest_state->entrance_nodes,
  2387. new_dest_nodes);
  2388. if (BE (err != REG_NOERROR, 0))
  2389. {
  2390. re_node_set_free (&dest_nodes);
  2391. goto free_return;
  2392. }
  2393. mctx->state_log[dest_str_idx]
  2394. = re_acquire_state_context (&err, dfa, &dest_nodes, context);
  2395. re_node_set_free (&dest_nodes);
  2396. if (BE (mctx->state_log[dest_str_idx] == NULL
  2397. && err != REG_NOERROR, 0))
  2398. goto free_return;
  2399. }
  2400. /* We need to check recursively if the backreference can epsilon
  2401. transit. */
  2402. if (subexp_len == 0
  2403. && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
  2404. {
  2405. err = check_subexp_matching_top (mctx, new_dest_nodes,
  2406. cur_str_idx);
  2407. if (BE (err != REG_NOERROR, 0))
  2408. goto free_return;
  2409. err = transit_state_bkref (mctx, new_dest_nodes);
  2410. if (BE (err != REG_NOERROR, 0))
  2411. goto free_return;
  2412. }
  2413. }
  2414. }
  2415. err = REG_NOERROR;
  2416. free_return:
  2417. return err;
  2418. }
  2419. /* Enumerate all the candidates which the backreference BKREF_NODE can match
  2420. at BKREF_STR_IDX, and register them by match_ctx_add_entry().
  2421. Note that we might collect inappropriate candidates here.
  2422. However, the cost of checking them strictly here is too high, then we
  2423. delay these checking for prune_impossible_nodes(). */
  2424. static reg_errcode_t
  2425. internal_function
  2426. get_subexp (re_match_context_t *mctx, int bkref_node, int bkref_str_idx)
  2427. {
  2428. const re_dfa_t *const dfa = mctx->dfa;
  2429. int subexp_num, sub_top_idx;
  2430. const char *buf = (const char *) re_string_get_buffer (&mctx->input);
  2431. /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
  2432. int cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
  2433. if (cache_idx != -1)
  2434. {
  2435. const struct re_backref_cache_entry *entry
  2436. = mctx->bkref_ents + cache_idx;
  2437. do
  2438. if (entry->node == bkref_node)
  2439. return REG_NOERROR; /* We already checked it. */
  2440. while (entry++->more);
  2441. }
  2442. subexp_num = dfa->nodes[bkref_node].opr.idx;
  2443. /* For each sub expression */
  2444. for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
  2445. {
  2446. reg_errcode_t err;
  2447. re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
  2448. re_sub_match_last_t *sub_last;
  2449. int sub_last_idx, sl_str, bkref_str_off;
  2450. if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
  2451. continue; /* It isn't related. */
  2452. sl_str = sub_top->str_idx;
  2453. bkref_str_off = bkref_str_idx;
  2454. /* At first, check the last node of sub expressions we already
  2455. evaluated. */
  2456. for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
  2457. {
  2458. int sl_str_diff;
  2459. sub_last = sub_top->lasts[sub_last_idx];
  2460. sl_str_diff = sub_last->str_idx - sl_str;
  2461. /* The matched string by the sub expression match with the substring
  2462. at the back reference? */
  2463. if (sl_str_diff > 0)
  2464. {
  2465. if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
  2466. {
  2467. /* Not enough chars for a successful match. */
  2468. if (bkref_str_off + sl_str_diff > mctx->input.len)
  2469. break;
  2470. err = clean_state_log_if_needed (mctx,
  2471. bkref_str_off
  2472. + sl_str_diff);
  2473. if (BE (err != REG_NOERROR, 0))
  2474. return err;
  2475. buf = (const char *) re_string_get_buffer (&mctx->input);
  2476. }
  2477. if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
  2478. /* We don't need to search this sub expression any more. */
  2479. break;
  2480. }
  2481. bkref_str_off += sl_str_diff;
  2482. sl_str += sl_str_diff;
  2483. err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
  2484. bkref_str_idx);
  2485. /* Reload buf, since the preceding call might have reallocated
  2486. the buffer. */
  2487. buf = (const char *) re_string_get_buffer (&mctx->input);
  2488. if (err == REG_NOMATCH)
  2489. continue;
  2490. if (BE (err != REG_NOERROR, 0))
  2491. return err;
  2492. }
  2493. if (sub_last_idx < sub_top->nlasts)
  2494. continue;
  2495. if (sub_last_idx > 0)
  2496. ++sl_str;
  2497. /* Then, search for the other last nodes of the sub expression. */
  2498. for (; sl_str <= bkref_str_idx; ++sl_str)
  2499. {
  2500. int cls_node, sl_str_off;
  2501. const re_node_set *nodes;
  2502. sl_str_off = sl_str - sub_top->str_idx;
  2503. /* The matched string by the sub expression match with the substring
  2504. at the back reference? */
  2505. if (sl_str_off > 0)
  2506. {
  2507. if (BE (bkref_str_off >= mctx->input.valid_len, 0))
  2508. {
  2509. /* If we are at the end of the input, we cannot match. */
  2510. if (bkref_str_off >= mctx->input.len)
  2511. break;
  2512. err = extend_buffers (mctx);
  2513. if (BE (err != REG_NOERROR, 0))
  2514. return err;
  2515. buf = (const char *) re_string_get_buffer (&mctx->input);
  2516. }
  2517. if (buf [bkref_str_off++] != buf[sl_str - 1])
  2518. break; /* We don't need to search this sub expression
  2519. any more. */
  2520. }
  2521. if (mctx->state_log[sl_str] == NULL)
  2522. continue;
  2523. /* Does this state have a ')' of the sub expression? */
  2524. nodes = &mctx->state_log[sl_str]->nodes;
  2525. cls_node = find_subexp_node (dfa, nodes, subexp_num,
  2526. OP_CLOSE_SUBEXP);
  2527. if (cls_node == -1)
  2528. continue; /* No. */
  2529. if (sub_top->path == NULL)
  2530. {
  2531. sub_top->path = calloc (sizeof (state_array_t),
  2532. sl_str - sub_top->str_idx + 1);
  2533. if (sub_top->path == NULL)
  2534. return REG_ESPACE;
  2535. }
  2536. /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
  2537. in the current context? */
  2538. err = check_arrival (mctx, sub_top->path, sub_top->node,
  2539. sub_top->str_idx, cls_node, sl_str,
  2540. OP_CLOSE_SUBEXP);
  2541. if (err == REG_NOMATCH)
  2542. continue;
  2543. if (BE (err != REG_NOERROR, 0))
  2544. return err;
  2545. sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
  2546. if (BE (sub_last == NULL, 0))
  2547. return REG_ESPACE;
  2548. err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
  2549. bkref_str_idx);
  2550. if (err == REG_NOMATCH)
  2551. continue;
  2552. }
  2553. }
  2554. return REG_NOERROR;
  2555. }
  2556. /* Helper functions for get_subexp(). */
  2557. /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
  2558. If it can arrive, register the sub expression expressed with SUB_TOP
  2559. and SUB_LAST. */
  2560. static reg_errcode_t
  2561. internal_function
  2562. get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
  2563. re_sub_match_last_t *sub_last, int bkref_node, int bkref_str)
  2564. {
  2565. reg_errcode_t err;
  2566. int to_idx;
  2567. /* Can the subexpression arrive the back reference? */
  2568. err = check_arrival (mctx, &sub_last->path, sub_last->node,
  2569. sub_last->str_idx, bkref_node, bkref_str,
  2570. OP_OPEN_SUBEXP);
  2571. if (err != REG_NOERROR)
  2572. return err;
  2573. err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
  2574. sub_last->str_idx);
  2575. if (BE (err != REG_NOERROR, 0))
  2576. return err;
  2577. to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
  2578. return clean_state_log_if_needed (mctx, to_idx);
  2579. }
  2580. /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
  2581. Search '(' if FL_OPEN, or search ')' otherwise.
  2582. TODO: This function isn't efficient...
  2583. Because there might be more than one nodes whose types are
  2584. OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
  2585. nodes.
  2586. E.g. RE: (a){2} */
  2587. static int
  2588. internal_function
  2589. find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
  2590. int subexp_idx, int type)
  2591. {
  2592. int cls_idx;
  2593. for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
  2594. {
  2595. int cls_node = nodes->elems[cls_idx];
  2596. const re_token_t *node = dfa->nodes + cls_node;
  2597. if (node->type == type
  2598. && node->opr.idx == subexp_idx)
  2599. return cls_node;
  2600. }
  2601. return -1;
  2602. }
  2603. /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
  2604. LAST_NODE at LAST_STR. We record the path onto PATH since it will be
  2605. heavily reused.
  2606. Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
  2607. static reg_errcode_t
  2608. internal_function
  2609. check_arrival (re_match_context_t *mctx, state_array_t *path, int top_node,
  2610. int top_str, int last_node, int last_str, int type)
  2611. {
  2612. const re_dfa_t *const dfa = mctx->dfa;
  2613. reg_errcode_t err = REG_NOERROR;
  2614. int subexp_num, backup_cur_idx, str_idx, null_cnt;
  2615. re_dfastate_t *cur_state = NULL;
  2616. re_node_set *cur_nodes, next_nodes;
  2617. re_dfastate_t **backup_state_log;
  2618. unsigned int context;
  2619. subexp_num = dfa->nodes[top_node].opr.idx;
  2620. /* Extend the buffer if we need. */
  2621. if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
  2622. {
  2623. re_dfastate_t **new_array;
  2624. int old_alloc = path->alloc;
  2625. path->alloc += last_str + mctx->max_mb_elem_len + 1;
  2626. new_array = re_realloc (path->array, re_dfastate_t *, path->alloc);
  2627. if (BE (new_array == NULL, 0))
  2628. {
  2629. path->alloc = old_alloc;
  2630. return REG_ESPACE;
  2631. }
  2632. path->array = new_array;
  2633. memset (new_array + old_alloc, '\0',
  2634. sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
  2635. }
  2636. str_idx = path->next_idx ?: top_str;
  2637. /* Temporary modify MCTX. */
  2638. backup_state_log = mctx->state_log;
  2639. backup_cur_idx = mctx->input.cur_idx;
  2640. mctx->state_log = path->array;
  2641. mctx->input.cur_idx = str_idx;
  2642. /* Setup initial node set. */
  2643. context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
  2644. if (str_idx == top_str)
  2645. {
  2646. err = re_node_set_init_1 (&next_nodes, top_node);
  2647. if (BE (err != REG_NOERROR, 0))
  2648. return err;
  2649. err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
  2650. if (BE (err != REG_NOERROR, 0))
  2651. {
  2652. re_node_set_free (&next_nodes);
  2653. return err;
  2654. }
  2655. }
  2656. else
  2657. {
  2658. cur_state = mctx->state_log[str_idx];
  2659. if (cur_state && cur_state->has_backref)
  2660. {
  2661. err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
  2662. if (BE (err != REG_NOERROR, 0))
  2663. return err;
  2664. }
  2665. else
  2666. re_node_set_init_empty (&next_nodes);
  2667. }
  2668. if (str_idx == top_str || (cur_state && cur_state->has_backref))
  2669. {
  2670. if (next_nodes.nelem)
  2671. {
  2672. err = expand_bkref_cache (mctx, &next_nodes, str_idx,
  2673. subexp_num, type);
  2674. if (BE (err != REG_NOERROR, 0))
  2675. {
  2676. re_node_set_free (&next_nodes);
  2677. return err;
  2678. }
  2679. }
  2680. cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
  2681. if (BE (cur_state == NULL && err != REG_NOERROR, 0))
  2682. {
  2683. re_node_set_free (&next_nodes);
  2684. return err;
  2685. }
  2686. mctx->state_log[str_idx] = cur_state;
  2687. }
  2688. for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
  2689. {
  2690. re_node_set_empty (&next_nodes);
  2691. if (mctx->state_log[str_idx + 1])
  2692. {
  2693. err = re_node_set_merge (&next_nodes,
  2694. &mctx->state_log[str_idx + 1]->nodes);
  2695. if (BE (err != REG_NOERROR, 0))
  2696. {
  2697. re_node_set_free (&next_nodes);
  2698. return err;
  2699. }
  2700. }
  2701. if (cur_state)
  2702. {
  2703. err = check_arrival_add_next_nodes (mctx, str_idx,
  2704. &cur_state->non_eps_nodes,
  2705. &next_nodes);
  2706. if (BE (err != REG_NOERROR, 0))
  2707. {
  2708. re_node_set_free (&next_nodes);
  2709. return err;
  2710. }
  2711. }
  2712. ++str_idx;
  2713. if (next_nodes.nelem)
  2714. {
  2715. err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
  2716. if (BE (err != REG_NOERROR, 0))
  2717. {
  2718. re_node_set_free (&next_nodes);
  2719. return err;
  2720. }
  2721. err = expand_bkref_cache (mctx, &next_nodes, str_idx,
  2722. subexp_num, type);
  2723. if (BE (err != REG_NOERROR, 0))
  2724. {
  2725. re_node_set_free (&next_nodes);
  2726. return err;
  2727. }
  2728. }
  2729. context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
  2730. cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
  2731. if (BE (cur_state == NULL && err != REG_NOERROR, 0))
  2732. {
  2733. re_node_set_free (&next_nodes);
  2734. return err;
  2735. }
  2736. mctx->state_log[str_idx] = cur_state;
  2737. null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
  2738. }
  2739. re_node_set_free (&next_nodes);
  2740. cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
  2741. : &mctx->state_log[last_str]->nodes);
  2742. path->next_idx = str_idx;
  2743. /* Fix MCTX. */
  2744. mctx->state_log = backup_state_log;
  2745. mctx->input.cur_idx = backup_cur_idx;
  2746. /* Then check the current node set has the node LAST_NODE. */
  2747. if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
  2748. return REG_NOERROR;
  2749. return REG_NOMATCH;
  2750. }
  2751. /* Helper functions for check_arrival. */
  2752. /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
  2753. to NEXT_NODES.
  2754. TODO: This function is similar to the functions transit_state*(),
  2755. however this function has many additional works.
  2756. Can't we unify them? */
  2757. static reg_errcode_t
  2758. internal_function
  2759. check_arrival_add_next_nodes (re_match_context_t *mctx, int str_idx,
  2760. re_node_set *cur_nodes, re_node_set *next_nodes)
  2761. {
  2762. const re_dfa_t *const dfa = mctx->dfa;
  2763. int result;
  2764. int cur_idx;
  2765. #ifdef RE_ENABLE_I18N
  2766. reg_errcode_t err = REG_NOERROR;
  2767. #endif
  2768. re_node_set union_set;
  2769. re_node_set_init_empty (&union_set);
  2770. for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
  2771. {
  2772. int naccepted = 0;
  2773. int cur_node = cur_nodes->elems[cur_idx];
  2774. #ifdef DEBUG
  2775. re_token_type_t type = dfa->nodes[cur_node].type;
  2776. assert (!IS_EPSILON_NODE (type));
  2777. #endif
  2778. #ifdef RE_ENABLE_I18N
  2779. /* If the node may accept `multi byte'. */
  2780. if (dfa->nodes[cur_node].accept_mb)
  2781. {
  2782. naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
  2783. str_idx);
  2784. if (naccepted > 1)
  2785. {
  2786. re_dfastate_t *dest_state;
  2787. int next_node = dfa->nexts[cur_node];
  2788. int next_idx = str_idx + naccepted;
  2789. dest_state = mctx->state_log[next_idx];
  2790. re_node_set_empty (&union_set);
  2791. if (dest_state)
  2792. {
  2793. err = re_node_set_merge (&union_set, &dest_state->nodes);
  2794. if (BE (err != REG_NOERROR, 0))
  2795. {
  2796. re_node_set_free (&union_set);
  2797. return err;
  2798. }
  2799. }
  2800. result = re_node_set_insert (&union_set, next_node);
  2801. if (BE (result < 0, 0))
  2802. {
  2803. re_node_set_free (&union_set);
  2804. return REG_ESPACE;
  2805. }
  2806. mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
  2807. &union_set);
  2808. if (BE (mctx->state_log[next_idx] == NULL
  2809. && err != REG_NOERROR, 0))
  2810. {
  2811. re_node_set_free (&union_set);
  2812. return err;
  2813. }
  2814. }
  2815. }
  2816. #endif /* RE_ENABLE_I18N */
  2817. if (naccepted
  2818. || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
  2819. {
  2820. result = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
  2821. if (BE (result < 0, 0))
  2822. {
  2823. re_node_set_free (&union_set);
  2824. return REG_ESPACE;
  2825. }
  2826. }
  2827. }
  2828. re_node_set_free (&union_set);
  2829. return REG_NOERROR;
  2830. }
  2831. /* For all the nodes in CUR_NODES, add the epsilon closures of them to
  2832. CUR_NODES, however exclude the nodes which are:
  2833. - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
  2834. - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
  2835. */
  2836. static reg_errcode_t
  2837. internal_function
  2838. check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
  2839. int ex_subexp, int type)
  2840. {
  2841. reg_errcode_t err;
  2842. int idx, outside_node;
  2843. re_node_set new_nodes;
  2844. #ifdef DEBUG
  2845. assert (cur_nodes->nelem);
  2846. #endif
  2847. err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
  2848. if (BE (err != REG_NOERROR, 0))
  2849. return err;
  2850. /* Create a new node set NEW_NODES with the nodes which are epsilon
  2851. closures of the node in CUR_NODES. */
  2852. for (idx = 0; idx < cur_nodes->nelem; ++idx)
  2853. {
  2854. int cur_node = cur_nodes->elems[idx];
  2855. const re_node_set *eclosure = dfa->eclosures + cur_node;
  2856. outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
  2857. if (outside_node == -1)
  2858. {
  2859. /* There are no problematic nodes, just merge them. */
  2860. err = re_node_set_merge (&new_nodes, eclosure);
  2861. if (BE (err != REG_NOERROR, 0))
  2862. {
  2863. re_node_set_free (&new_nodes);
  2864. return err;
  2865. }
  2866. }
  2867. else
  2868. {
  2869. /* There are problematic nodes, re-calculate incrementally. */
  2870. err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
  2871. ex_subexp, type);
  2872. if (BE (err != REG_NOERROR, 0))
  2873. {
  2874. re_node_set_free (&new_nodes);
  2875. return err;
  2876. }
  2877. }
  2878. }
  2879. re_node_set_free (cur_nodes);
  2880. *cur_nodes = new_nodes;
  2881. return REG_NOERROR;
  2882. }
  2883. /* Helper function for check_arrival_expand_ecl.
  2884. Check incrementally the epsilon closure of TARGET, and if it isn't
  2885. problematic append it to DST_NODES. */
  2886. static reg_errcode_t
  2887. internal_function
  2888. check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
  2889. int target, int ex_subexp, int type)
  2890. {
  2891. int cur_node;
  2892. for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
  2893. {
  2894. int err;
  2895. if (dfa->nodes[cur_node].type == type
  2896. && dfa->nodes[cur_node].opr.idx == ex_subexp)
  2897. {
  2898. if (type == OP_CLOSE_SUBEXP)
  2899. {
  2900. err = re_node_set_insert (dst_nodes, cur_node);
  2901. if (BE (err == -1, 0))
  2902. return REG_ESPACE;
  2903. }
  2904. break;
  2905. }
  2906. err = re_node_set_insert (dst_nodes, cur_node);
  2907. if (BE (err == -1, 0))
  2908. return REG_ESPACE;
  2909. if (dfa->edests[cur_node].nelem == 0)
  2910. break;
  2911. if (dfa->edests[cur_node].nelem == 2)
  2912. {
  2913. err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
  2914. dfa->edests[cur_node].elems[1],
  2915. ex_subexp, type);
  2916. if (BE (err != REG_NOERROR, 0))
  2917. return err;
  2918. }
  2919. cur_node = dfa->edests[cur_node].elems[0];
  2920. }
  2921. return REG_NOERROR;
  2922. }
  2923. /* For all the back references in the current state, calculate the
  2924. destination of the back references by the appropriate entry
  2925. in MCTX->BKREF_ENTS. */
  2926. static reg_errcode_t
  2927. internal_function
  2928. expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
  2929. int cur_str, int subexp_num, int type)
  2930. {
  2931. const re_dfa_t *const dfa = mctx->dfa;
  2932. reg_errcode_t err;
  2933. int cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
  2934. struct re_backref_cache_entry *ent;
  2935. if (cache_idx_start == -1)
  2936. return REG_NOERROR;
  2937. restart:
  2938. ent = mctx->bkref_ents + cache_idx_start;
  2939. do
  2940. {
  2941. int to_idx, next_node;
  2942. /* Is this entry ENT is appropriate? */
  2943. if (!re_node_set_contains (cur_nodes, ent->node))
  2944. continue; /* No. */
  2945. to_idx = cur_str + ent->subexp_to - ent->subexp_from;
  2946. /* Calculate the destination of the back reference, and append it
  2947. to MCTX->STATE_LOG. */
  2948. if (to_idx == cur_str)
  2949. {
  2950. /* The backreference did epsilon transit, we must re-check all the
  2951. node in the current state. */
  2952. re_node_set new_dests;
  2953. reg_errcode_t err2, err3;
  2954. next_node = dfa->edests[ent->node].elems[0];
  2955. if (re_node_set_contains (cur_nodes, next_node))
  2956. continue;
  2957. err = re_node_set_init_1 (&new_dests, next_node);
  2958. err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
  2959. err3 = re_node_set_merge (cur_nodes, &new_dests);
  2960. re_node_set_free (&new_dests);
  2961. if (BE (err != REG_NOERROR || err2 != REG_NOERROR
  2962. || err3 != REG_NOERROR, 0))
  2963. {
  2964. err = (err != REG_NOERROR ? err
  2965. : (err2 != REG_NOERROR ? err2 : err3));
  2966. return err;
  2967. }
  2968. /* TODO: It is still inefficient... */
  2969. goto restart;
  2970. }
  2971. else
  2972. {
  2973. re_node_set union_set;
  2974. next_node = dfa->nexts[ent->node];
  2975. if (mctx->state_log[to_idx])
  2976. {
  2977. int ret;
  2978. if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
  2979. next_node))
  2980. continue;
  2981. err = re_node_set_init_copy (&union_set,
  2982. &mctx->state_log[to_idx]->nodes);
  2983. ret = re_node_set_insert (&union_set, next_node);
  2984. if (BE (err != REG_NOERROR || ret < 0, 0))
  2985. {
  2986. re_node_set_free (&union_set);
  2987. err = err != REG_NOERROR ? err : REG_ESPACE;
  2988. return err;
  2989. }
  2990. }
  2991. else
  2992. {
  2993. err = re_node_set_init_1 (&union_set, next_node);
  2994. if (BE (err != REG_NOERROR, 0))
  2995. return err;
  2996. }
  2997. mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
  2998. re_node_set_free (&union_set);
  2999. if (BE (mctx->state_log[to_idx] == NULL
  3000. && err != REG_NOERROR, 0))
  3001. return err;
  3002. }
  3003. }
  3004. while (ent++->more);
  3005. return REG_NOERROR;
  3006. }
  3007. /* Build transition table for the state.
  3008. Return 1 if succeeded, otherwise return NULL. */
  3009. static int
  3010. internal_function
  3011. build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
  3012. {
  3013. reg_errcode_t err;
  3014. int i, j, ch, need_word_trtable = 0;
  3015. bitset_word_t elem, mask;
  3016. bool dests_node_malloced = false;
  3017. bool dest_states_malloced = false;
  3018. int ndests; /* Number of the destination states from `state'. */
  3019. re_dfastate_t **trtable;
  3020. re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
  3021. re_node_set follows, *dests_node;
  3022. bitset_t *dests_ch;
  3023. bitset_t acceptable;
  3024. struct dests_alloc
  3025. {
  3026. re_node_set dests_node[SBC_MAX];
  3027. bitset_t dests_ch[SBC_MAX];
  3028. } *dests_alloc;
  3029. /* We build DFA states which corresponds to the destination nodes
  3030. from `state'. `dests_node[i]' represents the nodes which i-th
  3031. destination state contains, and `dests_ch[i]' represents the
  3032. characters which i-th destination state accepts. */
  3033. if (__libc_use_alloca (sizeof (struct dests_alloc)))
  3034. dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
  3035. else
  3036. {
  3037. dests_alloc = re_malloc (struct dests_alloc, 1);
  3038. if (BE (dests_alloc == NULL, 0))
  3039. return 0;
  3040. dests_node_malloced = true;
  3041. }
  3042. dests_node = dests_alloc->dests_node;
  3043. dests_ch = dests_alloc->dests_ch;
  3044. /* Initialize transiton table. */
  3045. state->word_trtable = state->trtable = NULL;
  3046. /* At first, group all nodes belonging to `state' into several
  3047. destinations. */
  3048. ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
  3049. if (BE (ndests <= 0, 0))
  3050. {
  3051. if (dests_node_malloced)
  3052. free (dests_alloc);
  3053. /* Return 0 in case of an error, 1 otherwise. */
  3054. if (ndests == 0)
  3055. {
  3056. state->trtable = (re_dfastate_t **)
  3057. calloc (sizeof (re_dfastate_t *), SBC_MAX);
  3058. return 1;
  3059. }
  3060. return 0;
  3061. }
  3062. err = re_node_set_alloc (&follows, ndests + 1);
  3063. if (BE (err != REG_NOERROR, 0))
  3064. goto out_free;
  3065. if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
  3066. + ndests * 3 * sizeof (re_dfastate_t *)))
  3067. dest_states = (re_dfastate_t **)
  3068. alloca (ndests * 3 * sizeof (re_dfastate_t *));
  3069. else
  3070. {
  3071. dest_states = (re_dfastate_t **)
  3072. malloc (ndests * 3 * sizeof (re_dfastate_t *));
  3073. if (BE (dest_states == NULL, 0))
  3074. {
  3075. out_free:
  3076. if (dest_states_malloced)
  3077. free (dest_states);
  3078. re_node_set_free (&follows);
  3079. for (i = 0; i < ndests; ++i)
  3080. re_node_set_free (dests_node + i);
  3081. if (dests_node_malloced)
  3082. free (dests_alloc);
  3083. return 0;
  3084. }
  3085. dest_states_malloced = true;
  3086. }
  3087. dest_states_word = dest_states + ndests;
  3088. dest_states_nl = dest_states_word + ndests;
  3089. bitset_empty (acceptable);
  3090. /* Then build the states for all destinations. */
  3091. for (i = 0; i < ndests; ++i)
  3092. {
  3093. int next_node;
  3094. re_node_set_empty (&follows);
  3095. /* Merge the follows of this destination states. */
  3096. for (j = 0; j < dests_node[i].nelem; ++j)
  3097. {
  3098. next_node = dfa->nexts[dests_node[i].elems[j]];
  3099. if (next_node != -1)
  3100. {
  3101. err = re_node_set_merge (&follows, dfa->eclosures + next_node);
  3102. if (BE (err != REG_NOERROR, 0))
  3103. goto out_free;
  3104. }
  3105. }
  3106. dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
  3107. if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
  3108. goto out_free;
  3109. /* If the new state has context constraint,
  3110. build appropriate states for these contexts. */
  3111. if (dest_states[i]->has_constraint)
  3112. {
  3113. dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
  3114. CONTEXT_WORD);
  3115. if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
  3116. goto out_free;
  3117. if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
  3118. need_word_trtable = 1;
  3119. dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
  3120. CONTEXT_NEWLINE);
  3121. if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
  3122. goto out_free;
  3123. }
  3124. else
  3125. {
  3126. dest_states_word[i] = dest_states[i];
  3127. dest_states_nl[i] = dest_states[i];
  3128. }
  3129. bitset_merge (acceptable, dests_ch[i]);
  3130. }
  3131. if (!BE (need_word_trtable, 0))
  3132. {
  3133. /* We don't care about whether the following character is a word
  3134. character, or we are in a single-byte character set so we can
  3135. discern by looking at the character code: allocate a
  3136. 256-entry transition table. */
  3137. trtable = state->trtable =
  3138. (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
  3139. if (BE (trtable == NULL, 0))
  3140. goto out_free;
  3141. /* For all characters ch...: */
  3142. for (i = 0; i < BITSET_WORDS; ++i)
  3143. for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
  3144. elem;
  3145. mask <<= 1, elem >>= 1, ++ch)
  3146. if (BE (elem & 1, 0))
  3147. {
  3148. /* There must be exactly one destination which accepts
  3149. character ch. See group_nodes_into_DFAstates. */
  3150. for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
  3151. ;
  3152. /* j-th destination accepts the word character ch. */
  3153. if (dfa->word_char[i] & mask)
  3154. trtable[ch] = dest_states_word[j];
  3155. else
  3156. trtable[ch] = dest_states[j];
  3157. }
  3158. }
  3159. else
  3160. {
  3161. /* We care about whether the following character is a word
  3162. character, and we are in a multi-byte character set: discern
  3163. by looking at the character code: build two 256-entry
  3164. transition tables, one starting at trtable[0] and one
  3165. starting at trtable[SBC_MAX]. */
  3166. trtable = state->word_trtable =
  3167. (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
  3168. if (BE (trtable == NULL, 0))
  3169. goto out_free;
  3170. /* For all characters ch...: */
  3171. for (i = 0; i < BITSET_WORDS; ++i)
  3172. for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
  3173. elem;
  3174. mask <<= 1, elem >>= 1, ++ch)
  3175. if (BE (elem & 1, 0))
  3176. {
  3177. /* There must be exactly one destination which accepts
  3178. character ch. See group_nodes_into_DFAstates. */
  3179. for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
  3180. ;
  3181. /* j-th destination accepts the word character ch. */
  3182. trtable[ch] = dest_states[j];
  3183. trtable[ch + SBC_MAX] = dest_states_word[j];
  3184. }
  3185. }
  3186. /* new line */
  3187. if (bitset_contain (acceptable, NEWLINE_CHAR))
  3188. {
  3189. /* The current state accepts newline character. */
  3190. for (j = 0; j < ndests; ++j)
  3191. if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
  3192. {
  3193. /* k-th destination accepts newline character. */
  3194. trtable[NEWLINE_CHAR] = dest_states_nl[j];
  3195. if (need_word_trtable)
  3196. trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
  3197. /* There must be only one destination which accepts
  3198. newline. See group_nodes_into_DFAstates. */
  3199. break;
  3200. }
  3201. }
  3202. if (dest_states_malloced)
  3203. free (dest_states);
  3204. re_node_set_free (&follows);
  3205. for (i = 0; i < ndests; ++i)
  3206. re_node_set_free (dests_node + i);
  3207. if (dests_node_malloced)
  3208. free (dests_alloc);
  3209. return 1;
  3210. }
  3211. /* Group all nodes belonging to STATE into several destinations.
  3212. Then for all destinations, set the nodes belonging to the destination
  3213. to DESTS_NODE[i] and set the characters accepted by the destination
  3214. to DEST_CH[i]. This function return the number of destinations. */
  3215. static int
  3216. internal_function
  3217. group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
  3218. re_node_set *dests_node, bitset_t *dests_ch)
  3219. {
  3220. reg_errcode_t err;
  3221. int result;
  3222. int i, j, k;
  3223. int ndests; /* Number of the destinations from `state'. */
  3224. bitset_t accepts; /* Characters a node can accept. */
  3225. const re_node_set *cur_nodes = &state->nodes;
  3226. bitset_empty (accepts);
  3227. ndests = 0;
  3228. /* For all the nodes belonging to `state', */
  3229. for (i = 0; i < cur_nodes->nelem; ++i)
  3230. {
  3231. re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
  3232. re_token_type_t type = node->type;
  3233. unsigned int constraint = node->constraint;
  3234. /* Enumerate all single byte character this node can accept. */
  3235. if (type == CHARACTER)
  3236. bitset_set (accepts, node->opr.c);
  3237. else if (type == SIMPLE_BRACKET)
  3238. {
  3239. bitset_merge (accepts, node->opr.sbcset);
  3240. }
  3241. else if (type == OP_PERIOD)
  3242. {
  3243. #ifdef RE_ENABLE_I18N
  3244. if (dfa->mb_cur_max > 1)
  3245. bitset_merge (accepts, dfa->sb_char);
  3246. else
  3247. #endif
  3248. bitset_set_all (accepts);
  3249. if (!(dfa->syntax & RE_DOT_NEWLINE))
  3250. bitset_clear (accepts, '\n');
  3251. if (dfa->syntax & RE_DOT_NOT_NULL)
  3252. bitset_clear (accepts, '\0');
  3253. }
  3254. #ifdef RE_ENABLE_I18N
  3255. else if (type == OP_UTF8_PERIOD)
  3256. {
  3257. memset (accepts, '\xff', sizeof (bitset_t) / 2);
  3258. if (!(dfa->syntax & RE_DOT_NEWLINE))
  3259. bitset_clear (accepts, '\n');
  3260. if (dfa->syntax & RE_DOT_NOT_NULL)
  3261. bitset_clear (accepts, '\0');
  3262. }
  3263. #endif
  3264. else
  3265. continue;
  3266. /* Check the `accepts' and sift the characters which are not
  3267. match it the context. */
  3268. if (constraint)
  3269. {
  3270. if (constraint & NEXT_NEWLINE_CONSTRAINT)
  3271. {
  3272. bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
  3273. bitset_empty (accepts);
  3274. if (accepts_newline)
  3275. bitset_set (accepts, NEWLINE_CHAR);
  3276. else
  3277. continue;
  3278. }
  3279. if (constraint & NEXT_ENDBUF_CONSTRAINT)
  3280. {
  3281. bitset_empty (accepts);
  3282. continue;
  3283. }
  3284. if (constraint & NEXT_WORD_CONSTRAINT)
  3285. {
  3286. bitset_word_t any_set = 0;
  3287. if (type == CHARACTER && !node->word_char)
  3288. {
  3289. bitset_empty (accepts);
  3290. continue;
  3291. }
  3292. #ifdef RE_ENABLE_I18N
  3293. if (dfa->mb_cur_max > 1)
  3294. for (j = 0; j < BITSET_WORDS; ++j)
  3295. any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
  3296. else
  3297. #endif
  3298. for (j = 0; j < BITSET_WORDS; ++j)
  3299. any_set |= (accepts[j] &= dfa->word_char[j]);
  3300. if (!any_set)
  3301. continue;
  3302. }
  3303. if (constraint & NEXT_NOTWORD_CONSTRAINT)
  3304. {
  3305. bitset_word_t any_set = 0;
  3306. if (type == CHARACTER && node->word_char)
  3307. {
  3308. bitset_empty (accepts);
  3309. continue;
  3310. }
  3311. #ifdef RE_ENABLE_I18N
  3312. if (dfa->mb_cur_max > 1)
  3313. for (j = 0; j < BITSET_WORDS; ++j)
  3314. any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
  3315. else
  3316. #endif
  3317. for (j = 0; j < BITSET_WORDS; ++j)
  3318. any_set |= (accepts[j] &= ~dfa->word_char[j]);
  3319. if (!any_set)
  3320. continue;
  3321. }
  3322. }
  3323. /* Then divide `accepts' into DFA states, or create a new
  3324. state. Above, we make sure that accepts is not empty. */
  3325. for (j = 0; j < ndests; ++j)
  3326. {
  3327. bitset_t intersec; /* Intersection sets, see below. */
  3328. bitset_t remains;
  3329. /* Flags, see below. */
  3330. bitset_word_t has_intersec, not_subset, not_consumed;
  3331. /* Optimization, skip if this state doesn't accept the character. */
  3332. if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
  3333. continue;
  3334. /* Enumerate the intersection set of this state and `accepts'. */
  3335. has_intersec = 0;
  3336. for (k = 0; k < BITSET_WORDS; ++k)
  3337. has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
  3338. /* And skip if the intersection set is empty. */
  3339. if (!has_intersec)
  3340. continue;
  3341. /* Then check if this state is a subset of `accepts'. */
  3342. not_subset = not_consumed = 0;
  3343. for (k = 0; k < BITSET_WORDS; ++k)
  3344. {
  3345. not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
  3346. not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
  3347. }
  3348. /* If this state isn't a subset of `accepts', create a
  3349. new group state, which has the `remains'. */
  3350. if (not_subset)
  3351. {
  3352. bitset_copy (dests_ch[ndests], remains);
  3353. bitset_copy (dests_ch[j], intersec);
  3354. err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
  3355. if (BE (err != REG_NOERROR, 0))
  3356. goto error_return;
  3357. ++ndests;
  3358. }
  3359. /* Put the position in the current group. */
  3360. result = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
  3361. if (BE (result < 0, 0))
  3362. goto error_return;
  3363. /* If all characters are consumed, go to next node. */
  3364. if (!not_consumed)
  3365. break;
  3366. }
  3367. /* Some characters remain, create a new group. */
  3368. if (j == ndests)
  3369. {
  3370. bitset_copy (dests_ch[ndests], accepts);
  3371. err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
  3372. if (BE (err != REG_NOERROR, 0))
  3373. goto error_return;
  3374. ++ndests;
  3375. bitset_empty (accepts);
  3376. }
  3377. }
  3378. return ndests;
  3379. error_return:
  3380. for (j = 0; j < ndests; ++j)
  3381. re_node_set_free (dests_node + j);
  3382. return -1;
  3383. }
  3384. #ifdef RE_ENABLE_I18N
  3385. /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
  3386. Return the number of the bytes the node accepts.
  3387. STR_IDX is the current index of the input string.
  3388. This function handles the nodes which can accept one character, or
  3389. one collating element like '.', '[a-z]', opposite to the other nodes
  3390. can only accept one byte. */
  3391. static int
  3392. internal_function
  3393. check_node_accept_bytes (const re_dfa_t *dfa, int node_idx,
  3394. const re_string_t *input, int str_idx)
  3395. {
  3396. const re_token_t *node = dfa->nodes + node_idx;
  3397. int char_len, elem_len;
  3398. int i;
  3399. if (BE (node->type == OP_UTF8_PERIOD, 0))
  3400. {
  3401. unsigned char c = re_string_byte_at (input, str_idx), d;
  3402. if (BE (c < 0xc2, 1))
  3403. return 0;
  3404. if (str_idx + 2 > input->len)
  3405. return 0;
  3406. d = re_string_byte_at (input, str_idx + 1);
  3407. if (c < 0xe0)
  3408. return (d < 0x80 || d > 0xbf) ? 0 : 2;
  3409. else if (c < 0xf0)
  3410. {
  3411. char_len = 3;
  3412. if (c == 0xe0 && d < 0xa0)
  3413. return 0;
  3414. }
  3415. else if (c < 0xf8)
  3416. {
  3417. char_len = 4;
  3418. if (c == 0xf0 && d < 0x90)
  3419. return 0;
  3420. }
  3421. else if (c < 0xfc)
  3422. {
  3423. char_len = 5;
  3424. if (c == 0xf8 && d < 0x88)
  3425. return 0;
  3426. }
  3427. else if (c < 0xfe)
  3428. {
  3429. char_len = 6;
  3430. if (c == 0xfc && d < 0x84)
  3431. return 0;
  3432. }
  3433. else
  3434. return 0;
  3435. if (str_idx + char_len > input->len)
  3436. return 0;
  3437. for (i = 1; i < char_len; ++i)
  3438. {
  3439. d = re_string_byte_at (input, str_idx + i);
  3440. if (d < 0x80 || d > 0xbf)
  3441. return 0;
  3442. }
  3443. return char_len;
  3444. }
  3445. char_len = re_string_char_size_at (input, str_idx);
  3446. if (node->type == OP_PERIOD)
  3447. {
  3448. if (char_len <= 1)
  3449. return 0;
  3450. /* FIXME: I don't think this if is needed, as both '\n'
  3451. and '\0' are char_len == 1. */
  3452. /* '.' accepts any one character except the following two cases. */
  3453. if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
  3454. re_string_byte_at (input, str_idx) == '\n') ||
  3455. ((dfa->syntax & RE_DOT_NOT_NULL) &&
  3456. re_string_byte_at (input, str_idx) == '\0'))
  3457. return 0;
  3458. return char_len;
  3459. }
  3460. elem_len = re_string_elem_size_at (input, str_idx);
  3461. if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
  3462. return 0;
  3463. if (node->type == COMPLEX_BRACKET)
  3464. {
  3465. const re_charset_t *cset = node->opr.mbcset;
  3466. # ifdef _LIBC
  3467. const unsigned char *pin
  3468. = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
  3469. int j;
  3470. uint32_t nrules;
  3471. # endif /* _LIBC */
  3472. int match_len = 0;
  3473. wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
  3474. ? re_string_wchar_at (input, str_idx) : 0);
  3475. /* match with multibyte character? */
  3476. for (i = 0; i < cset->nmbchars; ++i)
  3477. if (wc == cset->mbchars[i])
  3478. {
  3479. match_len = char_len;
  3480. goto check_node_accept_bytes_match;
  3481. }
  3482. /* match with character_class? */
  3483. for (i = 0; i < cset->nchar_classes; ++i)
  3484. {
  3485. wctype_t wt = cset->char_classes[i];
  3486. if (__iswctype (wc, wt))
  3487. {
  3488. match_len = char_len;
  3489. goto check_node_accept_bytes_match;
  3490. }
  3491. }
  3492. # ifdef _LIBC
  3493. nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
  3494. if (nrules != 0)
  3495. {
  3496. unsigned int in_collseq = 0;
  3497. const int32_t *table, *indirect;
  3498. const unsigned char *weights, *extra;
  3499. const char *collseqwc;
  3500. int32_t idx;
  3501. /* This #include defines a local function! */
  3502. # include <locale/weight.h>
  3503. /* match with collating_symbol? */
  3504. if (cset->ncoll_syms)
  3505. extra = (const unsigned char *)
  3506. _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
  3507. for (i = 0; i < cset->ncoll_syms; ++i)
  3508. {
  3509. const unsigned char *coll_sym = extra + cset->coll_syms[i];
  3510. /* Compare the length of input collating element and
  3511. the length of current collating element. */
  3512. if (*coll_sym != elem_len)
  3513. continue;
  3514. /* Compare each bytes. */
  3515. for (j = 0; j < *coll_sym; j++)
  3516. if (pin[j] != coll_sym[1 + j])
  3517. break;
  3518. if (j == *coll_sym)
  3519. {
  3520. /* Match if every bytes is equal. */
  3521. match_len = j;
  3522. goto check_node_accept_bytes_match;
  3523. }
  3524. }
  3525. if (cset->nranges)
  3526. {
  3527. if (elem_len <= char_len)
  3528. {
  3529. collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
  3530. in_collseq = __collseq_table_lookup (collseqwc, wc);
  3531. }
  3532. else
  3533. in_collseq = find_collation_sequence_value (pin, elem_len);
  3534. }
  3535. /* match with range expression? */
  3536. for (i = 0; i < cset->nranges; ++i)
  3537. if (cset->range_starts[i] <= in_collseq
  3538. && in_collseq <= cset->range_ends[i])
  3539. {
  3540. match_len = elem_len;
  3541. goto check_node_accept_bytes_match;
  3542. }
  3543. /* match with equivalence_class? */
  3544. if (cset->nequiv_classes)
  3545. {
  3546. const unsigned char *cp = pin;
  3547. table = (const int32_t *)
  3548. _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
  3549. weights = (const unsigned char *)
  3550. _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
  3551. extra = (const unsigned char *)
  3552. _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
  3553. indirect = (const int32_t *)
  3554. _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
  3555. idx = findidx (&cp);
  3556. if (idx > 0)
  3557. for (i = 0; i < cset->nequiv_classes; ++i)
  3558. {
  3559. int32_t equiv_class_idx = cset->equiv_classes[i];
  3560. size_t weight_len = weights[idx];
  3561. if (weight_len == weights[equiv_class_idx])
  3562. {
  3563. int cnt = 0;
  3564. while (cnt <= weight_len
  3565. && (weights[equiv_class_idx + 1 + cnt]
  3566. == weights[idx + 1 + cnt]))
  3567. ++cnt;
  3568. if (cnt > weight_len)
  3569. {
  3570. match_len = elem_len;
  3571. goto check_node_accept_bytes_match;
  3572. }
  3573. }
  3574. }
  3575. }
  3576. }
  3577. else
  3578. # endif /* _LIBC */
  3579. {
  3580. /* match with range expression? */
  3581. #if __GNUC__ >= 2
  3582. wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
  3583. #else
  3584. wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
  3585. cmp_buf[2] = wc;
  3586. #endif
  3587. for (i = 0; i < cset->nranges; ++i)
  3588. {
  3589. cmp_buf[0] = cset->range_starts[i];
  3590. cmp_buf[4] = cset->range_ends[i];
  3591. if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
  3592. && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
  3593. {
  3594. match_len = char_len;
  3595. goto check_node_accept_bytes_match;
  3596. }
  3597. }
  3598. }
  3599. check_node_accept_bytes_match:
  3600. if (!cset->non_match)
  3601. return match_len;
  3602. else
  3603. {
  3604. if (match_len > 0)
  3605. return 0;
  3606. else
  3607. return (elem_len > char_len) ? elem_len : char_len;
  3608. }
  3609. }
  3610. return 0;
  3611. }
  3612. # ifdef _LIBC
  3613. static unsigned int
  3614. internal_function
  3615. find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
  3616. {
  3617. uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
  3618. if (nrules == 0)
  3619. {
  3620. if (mbs_len == 1)
  3621. {
  3622. /* No valid character. Match it as a single byte character. */
  3623. const unsigned char *collseq = (const unsigned char *)
  3624. _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
  3625. return collseq[mbs[0]];
  3626. }
  3627. return UINT_MAX;
  3628. }
  3629. else
  3630. {
  3631. int32_t idx;
  3632. const unsigned char *extra = (const unsigned char *)
  3633. _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
  3634. int32_t extrasize = (const unsigned char *)
  3635. _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
  3636. for (idx = 0; idx < extrasize;)
  3637. {
  3638. int mbs_cnt, found = 0;
  3639. int32_t elem_mbs_len;
  3640. /* Skip the name of collating element name. */
  3641. idx = idx + extra[idx] + 1;
  3642. elem_mbs_len = extra[idx++];
  3643. if (mbs_len == elem_mbs_len)
  3644. {
  3645. for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
  3646. if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
  3647. break;
  3648. if (mbs_cnt == elem_mbs_len)
  3649. /* Found the entry. */
  3650. found = 1;
  3651. }
  3652. /* Skip the byte sequence of the collating element. */
  3653. idx += elem_mbs_len;
  3654. /* Adjust for the alignment. */
  3655. idx = (idx + 3) & ~3;
  3656. /* Skip the collation sequence value. */
  3657. idx += sizeof (uint32_t);
  3658. /* Skip the wide char sequence of the collating element. */
  3659. idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
  3660. /* If we found the entry, return the sequence value. */
  3661. if (found)
  3662. return *(uint32_t *) (extra + idx);
  3663. /* Skip the collation sequence value. */
  3664. idx += sizeof (uint32_t);
  3665. }
  3666. return UINT_MAX;
  3667. }
  3668. }
  3669. # endif /* _LIBC */
  3670. #endif /* RE_ENABLE_I18N */
  3671. /* Check whether the node accepts the byte which is IDX-th
  3672. byte of the INPUT. */
  3673. static int
  3674. internal_function
  3675. check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
  3676. int idx)
  3677. {
  3678. unsigned char ch;
  3679. ch = re_string_byte_at (&mctx->input, idx);
  3680. switch (node->type)
  3681. {
  3682. case CHARACTER:
  3683. if (node->opr.c != ch)
  3684. return 0;
  3685. break;
  3686. case SIMPLE_BRACKET:
  3687. if (!bitset_contain (node->opr.sbcset, ch))
  3688. return 0;
  3689. break;
  3690. #ifdef RE_ENABLE_I18N
  3691. case OP_UTF8_PERIOD:
  3692. if (ch >= 0x80)
  3693. return 0;
  3694. /* FALLTHROUGH */
  3695. #endif
  3696. case OP_PERIOD:
  3697. if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
  3698. || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
  3699. return 0;
  3700. break;
  3701. default:
  3702. return 0;
  3703. }
  3704. if (node->constraint)
  3705. {
  3706. /* The node has constraints. Check whether the current context
  3707. satisfies the constraints. */
  3708. unsigned int context = re_string_context_at (&mctx->input, idx,
  3709. mctx->eflags);
  3710. if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
  3711. return 0;
  3712. }
  3713. return 1;
  3714. }
  3715. /* Extend the buffers, if the buffers have run out. */
  3716. static reg_errcode_t
  3717. internal_function
  3718. extend_buffers (re_match_context_t *mctx)
  3719. {
  3720. reg_errcode_t ret;
  3721. re_string_t *pstr = &mctx->input;
  3722. /* Double the lengthes of the buffers. */
  3723. ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
  3724. if (BE (ret != REG_NOERROR, 0))
  3725. return ret;
  3726. if (mctx->state_log != NULL)
  3727. {
  3728. /* And double the length of state_log. */
  3729. /* XXX We have no indication of the size of this buffer. If this
  3730. allocation fail we have no indication that the state_log array
  3731. does not have the right size. */
  3732. re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
  3733. pstr->bufs_len + 1);
  3734. if (BE (new_array == NULL, 0))
  3735. return REG_ESPACE;
  3736. mctx->state_log = new_array;
  3737. }
  3738. /* Then reconstruct the buffers. */
  3739. if (pstr->icase)
  3740. {
  3741. #ifdef RE_ENABLE_I18N
  3742. if (pstr->mb_cur_max > 1)
  3743. {
  3744. ret = build_wcs_upper_buffer (pstr);
  3745. if (BE (ret != REG_NOERROR, 0))
  3746. return ret;
  3747. }
  3748. else
  3749. #endif /* RE_ENABLE_I18N */
  3750. build_upper_buffer (pstr);
  3751. }
  3752. else
  3753. {
  3754. #ifdef RE_ENABLE_I18N
  3755. if (pstr->mb_cur_max > 1)
  3756. build_wcs_buffer (pstr);
  3757. else
  3758. #endif /* RE_ENABLE_I18N */
  3759. {
  3760. if (pstr->trans != NULL)
  3761. re_string_translate_buffer (pstr);
  3762. }
  3763. }
  3764. return REG_NOERROR;
  3765. }
  3766. /* Functions for matching context. */
  3767. /* Initialize MCTX. */
  3768. static reg_errcode_t
  3769. internal_function
  3770. match_ctx_init (re_match_context_t *mctx, int eflags, int n)
  3771. {
  3772. mctx->eflags = eflags;
  3773. mctx->match_last = -1;
  3774. if (n > 0)
  3775. {
  3776. mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
  3777. mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
  3778. if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
  3779. return REG_ESPACE;
  3780. }
  3781. /* Already zero-ed by the caller.
  3782. else
  3783. mctx->bkref_ents = NULL;
  3784. mctx->nbkref_ents = 0;
  3785. mctx->nsub_tops = 0; */
  3786. mctx->abkref_ents = n;
  3787. mctx->max_mb_elem_len = 1;
  3788. mctx->asub_tops = n;
  3789. return REG_NOERROR;
  3790. }
  3791. /* Clean the entries which depend on the current input in MCTX.
  3792. This function must be invoked when the matcher changes the start index
  3793. of the input, or changes the input string. */
  3794. static void
  3795. internal_function
  3796. match_ctx_clean (re_match_context_t *mctx)
  3797. {
  3798. int st_idx;
  3799. for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
  3800. {
  3801. int sl_idx;
  3802. re_sub_match_top_t *top = mctx->sub_tops[st_idx];
  3803. for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
  3804. {
  3805. re_sub_match_last_t *last = top->lasts[sl_idx];
  3806. re_free (last->path.array);
  3807. re_free (last);
  3808. }
  3809. re_free (top->lasts);
  3810. if (top->path)
  3811. {
  3812. re_free (top->path->array);
  3813. re_free (top->path);
  3814. }
  3815. free (top);
  3816. }
  3817. mctx->nsub_tops = 0;
  3818. mctx->nbkref_ents = 0;
  3819. }
  3820. /* Free all the memory associated with MCTX. */
  3821. static void
  3822. internal_function
  3823. match_ctx_free (re_match_context_t *mctx)
  3824. {
  3825. /* First, free all the memory associated with MCTX->SUB_TOPS. */
  3826. match_ctx_clean (mctx);
  3827. re_free (mctx->sub_tops);
  3828. re_free (mctx->bkref_ents);
  3829. }
  3830. /* Add a new backreference entry to MCTX.
  3831. Note that we assume that caller never call this function with duplicate
  3832. entry, and call with STR_IDX which isn't smaller than any existing entry.
  3833. */
  3834. static reg_errcode_t
  3835. internal_function
  3836. match_ctx_add_entry (re_match_context_t *mctx, int node, int str_idx, int from,
  3837. int to)
  3838. {
  3839. if (mctx->nbkref_ents >= mctx->abkref_ents)
  3840. {
  3841. struct re_backref_cache_entry* new_entry;
  3842. new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
  3843. mctx->abkref_ents * 2);
  3844. if (BE (new_entry == NULL, 0))
  3845. {
  3846. re_free (mctx->bkref_ents);
  3847. return REG_ESPACE;
  3848. }
  3849. mctx->bkref_ents = new_entry;
  3850. memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
  3851. sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
  3852. mctx->abkref_ents *= 2;
  3853. }
  3854. if (mctx->nbkref_ents > 0
  3855. && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
  3856. mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
  3857. mctx->bkref_ents[mctx->nbkref_ents].node = node;
  3858. mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
  3859. mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
  3860. mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
  3861. /* This is a cache that saves negative results of check_dst_limits_calc_pos.
  3862. If bit N is clear, means that this entry won't epsilon-transition to
  3863. an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
  3864. it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
  3865. such node.
  3866. A backreference does not epsilon-transition unless it is empty, so set
  3867. to all zeros if FROM != TO. */
  3868. mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
  3869. = (from == to ? ~0 : 0);
  3870. mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
  3871. if (mctx->max_mb_elem_len < to - from)
  3872. mctx->max_mb_elem_len = to - from;
  3873. return REG_NOERROR;
  3874. }
  3875. /* Search for the first entry which has the same str_idx, or -1 if none is
  3876. found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
  3877. static int
  3878. internal_function
  3879. search_cur_bkref_entry (const re_match_context_t *mctx, int str_idx)
  3880. {
  3881. int left, right, mid, last;
  3882. last = right = mctx->nbkref_ents;
  3883. for (left = 0; left < right;)
  3884. {
  3885. mid = (left + right) / 2;
  3886. if (mctx->bkref_ents[mid].str_idx < str_idx)
  3887. left = mid + 1;
  3888. else
  3889. right = mid;
  3890. }
  3891. if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
  3892. return left;
  3893. else
  3894. return -1;
  3895. }
  3896. /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
  3897. at STR_IDX. */
  3898. static reg_errcode_t
  3899. internal_function
  3900. match_ctx_add_subtop (re_match_context_t *mctx, int node, int str_idx)
  3901. {
  3902. #ifdef DEBUG
  3903. assert (mctx->sub_tops != NULL);
  3904. assert (mctx->asub_tops > 0);
  3905. #endif
  3906. if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
  3907. {
  3908. int new_asub_tops = mctx->asub_tops * 2;
  3909. re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
  3910. re_sub_match_top_t *,
  3911. new_asub_tops);
  3912. if (BE (new_array == NULL, 0))
  3913. return REG_ESPACE;
  3914. mctx->sub_tops = new_array;
  3915. mctx->asub_tops = new_asub_tops;
  3916. }
  3917. mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
  3918. if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
  3919. return REG_ESPACE;
  3920. mctx->sub_tops[mctx->nsub_tops]->node = node;
  3921. mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
  3922. return REG_NOERROR;
  3923. }
  3924. /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
  3925. at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
  3926. static re_sub_match_last_t *
  3927. internal_function
  3928. match_ctx_add_sublast (re_sub_match_top_t *subtop, int node, int str_idx)
  3929. {
  3930. re_sub_match_last_t *new_entry;
  3931. if (BE (subtop->nlasts == subtop->alasts, 0))
  3932. {
  3933. int new_alasts = 2 * subtop->alasts + 1;
  3934. re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
  3935. re_sub_match_last_t *,
  3936. new_alasts);
  3937. if (BE (new_array == NULL, 0))
  3938. return NULL;
  3939. subtop->lasts = new_array;
  3940. subtop->alasts = new_alasts;
  3941. }
  3942. new_entry = calloc (1, sizeof (re_sub_match_last_t));
  3943. if (BE (new_entry != NULL, 1))
  3944. {
  3945. subtop->lasts[subtop->nlasts] = new_entry;
  3946. new_entry->node = node;
  3947. new_entry->str_idx = str_idx;
  3948. ++subtop->nlasts;
  3949. }
  3950. return new_entry;
  3951. }
  3952. static void
  3953. internal_function
  3954. sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
  3955. re_dfastate_t **limited_sts, int last_node, int last_str_idx)
  3956. {
  3957. sctx->sifted_states = sifted_sts;
  3958. sctx->limited_states = limited_sts;
  3959. sctx->last_node = last_node;
  3960. sctx->last_str_idx = last_str_idx;
  3961. re_node_set_init_empty (&sctx->limits);
  3962. }