Something went wrong. Try again.
Reactos
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040404140424043404440454046404740484049405040514052405340544055405640574058405940604061406240634064406540664067406840694070407140724073407440754076407740784079408040814082408340844085408640874088408940904091409240934094409540964097409840994100410141024103410441054106410741084109411041114112411341144115411641174118411941204121412241234124412541264127412841294130413141324133413441354136413741384139414041414142414341444145414641474148414941504151415241534154415541564157415841594160416141624163416441654166416741684169417041714172417341744175417641774178417941804181418241834184418541864187418841894190419141924193419441954196419741984199420042014202420342044205420642074208420942104211421242134214421542164217421842194220422142224223422442254226422742284229423042314232423342344235423642374238423942404241424242434244424542464247424842494250425142524253425442554256425742584259426042614262426342644265426642674268426942704271427242734274427542764277427842794280428142824283428442854286428742884289429042914292429342944295429642974298429943004301430243034304430543064307430843094310431143124313431443154316431743184319432043214322432343244325432643274328432943304331433243334334433543364337433843394340434143424343434443454346434743484349435043514352435343544355435643574358435943604361436243634364436543664367436843694370437143724373437443754376437743784379438043814382438343844385438643874388438943904391439243934394439543964397439843994400440144024403440444054406440744084409441044114412441344144415441644174418441944204421442244234424442544264427442844294430443144324433443444354436443744384439444044414442444344444445444644474448444944504451445244534454445544564457445844594460446144624463446444654466446744684469447044714472447344744475447644774478447944804481448244834484448544864487448844894490449144924493449444954496449744984499450045014502450345044505450645074508450945104511451245134514451545164517451845194520452145224523452445254526452745284529453045314532453345344535453645374538453945404541454245434544454545464547454845494550455145524553455445554556455745584559456045614562456345644565456645674568456945704571457245734574457545764577457845794580458145824583458445854586458745884589459045914592459345944595459645974598459946004601460246034604460546064607460846094610461146124613461446154616461746184619462046214622462346244625462646274628462946304631463246334634463546364637463846394640464146424643464446454646464746484649465046514652465346544655465646574658465946604661466246634664466546664667466846694670467146724673467446754676467746784679468046814682468346844685468646874688468946904691469246934694469546964697469846994700470147024703470447054706470747084709471047114712471347144715471647174718471947204721472247234724472547264727472847294730473147324733473447354736473747384739474047414742474347444745474647474748474947504751475247534754475547564757475847594760476147624763476447654766476747684769477047714772477347744775477647774778477947804781478247834784478547864787478847894790479147924793479447954796479747984799480048014802480348044805480648074808480948104811481248134814481548164817481848194820482148224823482448254826482748284829483048314832483348344835483648374838483948404841484248434844484548464847484848494850485148524853485448554856485748584859486048614862486348644865486648674868486948704871487248734874487548764877487848794880488148824883488448854886488748884889489048914892489348944895489648974898489949004901490249034904490549064907490849094910491149124913491449154916491749184919492049214922492349244925492649274928492949304931493249334934493549364937493849394940494149424943494449454946494749484949495049514952495349544955495649574958495949604961496249634964496549664967496849694970497149724973497449754976497749784979498049814982498349844985498649874988498949904991499249934994499549964997499849995000500150025003500450055006500750085009501050115012501350145015501650175018501950205021502250235024502550265027502850295030503150325033503450355036503750385039504050415042504350445045504650475048504950505051505250535054505550565057505850595060506150625063506450655066506750685069507050715072507350745075507650775078507950805081508250835084508550865087508850895090509150925093509450955096509750985099510051015102510351045105510651075108510951105111511251135114511551165117511851195120512151225123512451255126512751285129513051315132513351345135513651375138513951405141514251435144514551465147514851495150515151525153515451555156515751585159516051615162516351645165516651675168516951705171517251735174517551765177517851795180518151825183518451855186518751885189519051915192519351945195519651975198519952005201520252035204520552065207520852095210521152125213521452155216521752185219522052215222522352245225522652275228522952305231523252335234523552365237523852395240524152425243524452455246524752485249525052515252525352545255525652575258525952605261526252635264526552665267526852695270527152725273527452755276527752785279528052815282528352845285528652875288528952905291529252935294529552965297529852995300530153025303530453055306530753085309531053115312531353145315531653175318531953205321532253235324532553265327532853295330533153325333533453355336533753385339534053415342534353445345534653475348534953505351535253535354535553565357535853595360536153625363536453655366536753685369537053715372537353745375537653775378537953805381538253835384538553865387538853895390539153925393539453955396539753985399540054015402540354045405540654075408540954105411541254135414541554165417541854195420542154225423542454255426542754285429543054315432543354345435543654375438543954405441544254435444544554465447544854495450545154525453545454555456545754585459546054615462546354645465546654675468546954705471547254735474547554765477547854795480548154825483548454855486548754885489549054915492549354945495549654975498549955005501550255035504550555065507550855095510551155125513551455155516551755185519552055215522552355245525552655275528552955305531553255335534553555365537553855395540554155425543554455455546554755485549555055515552555355545555555655575558555955605561556255635564556555665567556855695570557155725573557455755576557755785579558055815582558355845585558655875588558955905591559255935594559555965597559855995600560156025603560456055606560756085609561056115612561356145615561656175618561956205621562256235624562556265627562856295630563156325633563456355636563756385639564056415642564356445645564656475648564956505651565256535654565556565657565856595660566156625663566456655666566756685669567056715672567356745675567656775678567956805681568256835684568556865687568856895690569156925693569456955696569756985699570057015702570357045705570657075708570957105711571257135714571557165717571857195720572157225723572457255726572757285729573057315732573357345735573657375738573957405741574257435744574557465747574857495750575157525753575457555756575757585759576057615762576357645765576657675768576957705771577257735774577557765777577857795780578157825783578457855786578757885789579057915792579357945795579657975798579958005801580258035804580558065807580858095810581158125813581458155816581758185819582058215822582358245825582658275828582958305831583258335834583558365837583858395840584158425843584458455846584758485849585058515852585358545855585658575858585958605861586258635864586558665867586858695870587158725873587458755876587758785879588058815882588358845885588658875888588958905891589258935894589558965897589858995900590159025903590459055906590759085909591059115912591359145915591659175918591959205921592259235924592559265927592859295930593159325933593459355936593759385939594059415942594359445945594659475948594959505951595259535954595559565957595859595960596159625963596459655966596759685969597059715972597359745975597659775978597959805981598259835984598559865987598859895990599159925993599459955996599759985999600060016002600360046005600660076008600960106011601260136014601560166017601860196020602160226023602460256026602760286029603060316032603360346035603660376038603960406041604260436044604560466047604860496050605160526053605460556056605760586059606060616062606360646065606660676068606960706071607260736074607560766077607860796080608160826083608460856086608760886089609060916092609360946095609660976098609961006101610261036104610561066107610861096110611161126113611461156116611761186119612061216122612361246125612661276128612961306131613261336134613561366137613861396140614161426143614461456146614761486149615061516152615361546155615661576158615961606161616261636164616561666167616861696170617161726173617461756176617761786179618061816182618361846185618661876188618961906191619261936194619561966197619861996200620162026203620462056206620762086209621062116212621362146215621662176218621962206221622262236224622562266227622862296230623162326233623462356236623762386239624062416242624362446245624662476248624962506251625262536254625562566257625862596260626162626263626462656266626762686269627062716272627362746275627662776278627962806281628262836284628562866287628862896290629162926293629462956296629762986299630063016302630363046305630663076308630963106311631263136314631563166317631863196320632163226323632463256326632763286329633063316332633363346335633663376338633963406341634263436344634563466347634863496350635163526353635463556356635763586359636063616362636363646365636663676368636963706371637263736374637563766377637863796380638163826383638463856386638763886389639063916392639363946395639663976398639964006401640264036404640564066407640864096410641164126413641464156416641764186419642064216422642364246425642664276428642964306431643264336434643564366437643864396440644164426443644464456446644764486449645064516452645364546455645664576458645964606461646264636464646564666467646864696470647164726473647464756476647764786479648064816482648364846485648664876488648964906491649264936494649564966497649864996500650165026503650465056506650765086509651065116512651365146515651665176518651965206521652265236524652565266527652865296530653165326533653465356536653765386539654065416542654365446545654665476548654965506551655265536554655565566557655865596560656165626563656465656566656765686569657065716572657365746575657665776578657965806581658265836584658565866587658865896590659165926593659465956596659765986599660066016602660366046605660666076608660966106611661266136614661566166617661866196620662166226623662466256626662766286629663066316632663366346635663666376638663966406641664266436644664566466647664866496650665166526653665466556656665766586659666066616662666366646665666666676668666966706671667266736674667566766677667866796680668166826683668466856686668766886689669066916692669366946695669666976698669967006701670267036704670567066707670867096710671167126713671467156716671767186719672067216722672367246725672667276728672967306731673267336734673567366737673867396740674167426743674467456746674767486749675067516752675367546755675667576758675967606761676267636764676567666767676867696770677167726773677467756776677767786779678067816782678367846785678667876788678967906791679267936794679567966797679867996800680168026803680468056806680768086809681068116812681368146815681668176818681968206821682268236824682568266827682868296830683168326833683468356836683768386839684068416842684368446845684668476848684968506851685268536854685568566857685868596860686168626863686468656866686768686869687068716872687368746875687668776878687968806881688268836884688568866887688868896890689168926893689468956896689768986899690069016902690369046905690669076908690969106911691269136914691569166917691869196920692169226923692469256926692769286929693069316932693369346935693669376938693969406941694269436944694569466947694869496950695169526953695469556956695769586959696069616962696369646965696669676968696969706971697269736974697569766977697869796980698169826983698469856986698769886989699069916992699369946995699669976998699970007001700270037004700570067007700870097010701170127013701470157016701770187019702070217022702370247025702670277028702970307031703270337034703570367037703870397040704170427043704470457046704770487049705070517052705370547055705670577058705970607061706270637064706570667067706870697070707170727073707470757076707770787079708070817082708370847085708670877088708970907091709270937094709570967097709870997100710171027103710471057106710771087109711071117112711371147115711671177118711971207121712271237124712571267127712871297130713171327133713471357136713771387139714071417142714371447145714671477148714971507151715271537154715571567157715871597160716171627163716471657166716771687169717071717172717371747175717671777178717971807181718271837184718571867187718871897190719171927193719471957196719771987199720072017202720372047205720672077208720972107211721272137214721572167217721872197220722172227223722472257226722772287229723072317232723372347235723672377238723972407241724272437244724572467247724872497250725172527253725472557256725772587259726072617262726372647265726672677268726972707271727272737274727572767277727872797280728172827283728472857286728772887289729072917292729372947295729672977298729973007301730273037304730573067307730873097310731173127313731473157316731773187319732073217322732373247325732673277328732973307331733273337334733573367337733873397340734173427343734473457346734773487349735073517352735373547355735673577358735973607361736273637364736573667367736873697370737173727373737473757376737773787379738073817382738373847385738673877388738973907391739273937394739573967397739873997400740174027403740474057406740774087409741074117412741374147415741674177418741974207421742274237424742574267427742874297430743174327433743474357436743774387439744074417442744374447445744674477448744974507451745274537454745574567457745874597460746174627463746474657466746774687469747074717472747374747475747674777478747974807481748274837484748574867487748874897490749174927493749474957496749774987499750075017502750375047505750675077508750975107511751275137514751575167517751875197520752175227523752475257526752775287529753075317532753375347535753675377538753975407541754275437544754575467547754875497550755175527553755475557556755775587559756075617562756375647565756675677568756975707571757275737574757575767577757875797580758175827583758475857586758775887589759075917592759375947595759675977598759976007601760276037604760576067607760876097610761176127613761476157616761776187619762076217622762376247625762676277628762976307631763276337634763576367637763876397640764176427643764476457646764776487649765076517652765376547655765676577658765976607661766276637664766576667667766876697670767176727673767476757676767776787679768076817682768376847685768676877688768976907691769276937694769576967697769876997700770177027703770477057706770777087709771077117712771377147715771677177718771977207721772277237724772577267727772877297730773177327733773477357736773777387739774077417742774377447745774677477748774977507751775277537754775577567757775877597760776177627763776477657766776777687769777077717772777377747775777677777778777977807781778277837784778577867787778877897790779177927793779477957796779777987799780078017802780378047805780678077808780978107811781278137814781578167817781878197820782178227823782478257826782778287829783078317832783378347835783678377838783978407841784278437844784578467847784878497850785178527853785478557856785778587859786078617862786378647865786678677868786978707871787278737874787578767877787878797880788178827883788478857886788778887889789078917892789378947895789678977898789979007901790279037904790579067907790879097910791179127913791479157916791779187919792079217922792379247925792679277928792979307931793279337934793579367937793879397940794179427943794479457946794779487949795079517952795379547955795679577958795979607961796279637964796579667967796879697970797179727973797479757976797779787979798079817982798379847985798679877988798979907991799279937994799579967997799879998000800180028003800480058006800780088009801080118012/* * regexp.c: generic and extensible Regular Expression engine * * Basically designed with the purpose of compiling regexps for * the variety of validation/schemas mechanisms now available in * XML related specifications these include: * - XML-1.0 DTD validation * - XML Schemas structure part 1 * - XML Schemas Datatypes part 2 especially Appendix F * - RELAX-NG/TREX i.e. the counter proposal * * See Copyright for the status of this software. * * Daniel Veillard <veillard@redhat.com> */
#define IN_LIBXML#include "libxml.h"
#ifdef LIBXML_REGEXP_ENABLED
#include <stdio.h>#include <string.h>#include <limits.h>
#include <libxml/tree.h>#include <libxml/parserInternals.h>#include <libxml/xmlregexp.h>#include <libxml/xmlautomata.h>#include <libxml/xmlunicode.h>
#include "private/error.h"#include "private/regexp.h"
#ifndef SIZE_MAX#define SIZE_MAX ((size_t) -1)#endif
#define MAX_PUSH 10000000
/* * -2 and -3 are used by xmlValidateElementType for other things. */#define XML_REGEXP_OK 0#define XML_REGEXP_NOT_FOUND (-1)#define XML_REGEXP_INTERNAL_ERROR (-4)#define XML_REGEXP_OUT_OF_MEMORY (-5)#define XML_REGEXP_INTERNAL_LIMIT (-6)#define XML_REGEXP_INVALID_UTF8 (-7)
#ifdef ERROR#undef ERROR#endif#define ERROR(str) \ ctxt->error = XML_REGEXP_COMPILE_ERROR; \ xmlRegexpErrCompile(ctxt, str);#define NEXT ctxt->cur++#define CUR (*(ctxt->cur))#define NXT(index) (ctxt->cur[index])
#define NEXTL(l) ctxt->cur += l;#define XML_REG_STRING_SEPARATOR '|'/* * Need PREV to check on a '-' within a Character Group. May only be used * when it's guaranteed that cur is not at the beginning of ctxt->string! */#define PREV (ctxt->cur[-1])
/** * TODO: * * macro to flag unimplemented blocks */#define TODO \ xmlGenericError(xmlGenericErrorContext, \ "Unimplemented block at %s:%d\n", \ __FILE__, __LINE__);
/************************************************************************ * * * Datatypes and structures * * * ************************************************************************/
/* * Note: the order of the enums below is significant, do not shuffle */typedef enum { XML_REGEXP_EPSILON = 1, XML_REGEXP_CHARVAL, XML_REGEXP_RANGES, XML_REGEXP_SUBREG, /* used for () sub regexps */ XML_REGEXP_STRING, XML_REGEXP_ANYCHAR, /* . */ XML_REGEXP_ANYSPACE, /* \s */ XML_REGEXP_NOTSPACE, /* \S */ XML_REGEXP_INITNAME, /* \l */ XML_REGEXP_NOTINITNAME, /* \L */ XML_REGEXP_NAMECHAR, /* \c */ XML_REGEXP_NOTNAMECHAR, /* \C */ XML_REGEXP_DECIMAL, /* \d */ XML_REGEXP_NOTDECIMAL, /* \D */ XML_REGEXP_REALCHAR, /* \w */ XML_REGEXP_NOTREALCHAR, /* \W */ XML_REGEXP_LETTER = 100, XML_REGEXP_LETTER_UPPERCASE, XML_REGEXP_LETTER_LOWERCASE, XML_REGEXP_LETTER_TITLECASE, XML_REGEXP_LETTER_MODIFIER, XML_REGEXP_LETTER_OTHERS, XML_REGEXP_MARK, XML_REGEXP_MARK_NONSPACING, XML_REGEXP_MARK_SPACECOMBINING, XML_REGEXP_MARK_ENCLOSING, XML_REGEXP_NUMBER, XML_REGEXP_NUMBER_DECIMAL, XML_REGEXP_NUMBER_LETTER, XML_REGEXP_NUMBER_OTHERS, XML_REGEXP_PUNCT, XML_REGEXP_PUNCT_CONNECTOR, XML_REGEXP_PUNCT_DASH, XML_REGEXP_PUNCT_OPEN, XML_REGEXP_PUNCT_CLOSE, XML_REGEXP_PUNCT_INITQUOTE, XML_REGEXP_PUNCT_FINQUOTE, XML_REGEXP_PUNCT_OTHERS, XML_REGEXP_SEPAR, XML_REGEXP_SEPAR_SPACE, XML_REGEXP_SEPAR_LINE, XML_REGEXP_SEPAR_PARA, XML_REGEXP_SYMBOL, XML_REGEXP_SYMBOL_MATH, XML_REGEXP_SYMBOL_CURRENCY, XML_REGEXP_SYMBOL_MODIFIER, XML_REGEXP_SYMBOL_OTHERS, XML_REGEXP_OTHER, XML_REGEXP_OTHER_CONTROL, XML_REGEXP_OTHER_FORMAT, XML_REGEXP_OTHER_PRIVATE, XML_REGEXP_OTHER_NA, XML_REGEXP_BLOCK_NAME} xmlRegAtomType;
typedef enum { XML_REGEXP_QUANT_EPSILON = 1, XML_REGEXP_QUANT_ONCE, XML_REGEXP_QUANT_OPT, XML_REGEXP_QUANT_MULT, XML_REGEXP_QUANT_PLUS, XML_REGEXP_QUANT_ONCEONLY, XML_REGEXP_QUANT_ALL, XML_REGEXP_QUANT_RANGE} xmlRegQuantType;
typedef enum { XML_REGEXP_START_STATE = 1, XML_REGEXP_FINAL_STATE, XML_REGEXP_TRANS_STATE, XML_REGEXP_SINK_STATE, XML_REGEXP_UNREACH_STATE} xmlRegStateType;
typedef enum { XML_REGEXP_MARK_NORMAL = 0, XML_REGEXP_MARK_START, XML_REGEXP_MARK_VISITED} xmlRegMarkedType;
typedef struct _xmlRegRange xmlRegRange;typedef xmlRegRange *xmlRegRangePtr;
struct _xmlRegRange { int neg; /* 0 normal, 1 not, 2 exclude */ xmlRegAtomType type; int start; int end; xmlChar *blockName;};
typedef struct _xmlRegAtom xmlRegAtom;typedef xmlRegAtom *xmlRegAtomPtr;
typedef struct _xmlAutomataState xmlRegState;typedef xmlRegState *xmlRegStatePtr;
struct _xmlRegAtom { int no; xmlRegAtomType type; xmlRegQuantType quant; int min; int max;
void *valuep; void *valuep2; int neg; int codepoint; xmlRegStatePtr start; xmlRegStatePtr start0; xmlRegStatePtr stop; int maxRanges; int nbRanges; xmlRegRangePtr *ranges; void *data;};
typedef struct _xmlRegCounter xmlRegCounter;typedef xmlRegCounter *xmlRegCounterPtr;
struct _xmlRegCounter { int min; int max;};
typedef struct _xmlRegTrans xmlRegTrans;typedef xmlRegTrans *xmlRegTransPtr;
struct _xmlRegTrans { xmlRegAtomPtr atom; int to; int counter; int count; int nd;};
struct _xmlAutomataState { xmlRegStateType type; xmlRegMarkedType mark; xmlRegMarkedType markd; xmlRegMarkedType reached; int no; int maxTrans; int nbTrans; xmlRegTrans *trans; /* knowing states pointing to us can speed things up */ int maxTransTo; int nbTransTo; int *transTo;};
typedef struct _xmlAutomata xmlRegParserCtxt;typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;
#define AM_AUTOMATA_RNG 1
struct _xmlAutomata { xmlChar *string; xmlChar *cur;
int error; int neg;
xmlRegStatePtr start; xmlRegStatePtr end; xmlRegStatePtr state;
xmlRegAtomPtr atom;
int maxAtoms; int nbAtoms; xmlRegAtomPtr *atoms;
int maxStates; int nbStates; xmlRegStatePtr *states;
int maxCounters; int nbCounters; xmlRegCounter *counters;
int determinist; int negs; int flags;
int depth;};
struct _xmlRegexp { xmlChar *string; int nbStates; xmlRegStatePtr *states; int nbAtoms; xmlRegAtomPtr *atoms; int nbCounters; xmlRegCounter *counters; int determinist; int flags; /* * That's the compact form for determinists automatas */ int nbstates; int *compact; void **transdata; int nbstrings; xmlChar **stringMap;};
typedef struct _xmlRegExecRollback xmlRegExecRollback;typedef xmlRegExecRollback *xmlRegExecRollbackPtr;
struct _xmlRegExecRollback { xmlRegStatePtr state;/* the current state */ int index; /* the index in the input stack */ int nextbranch; /* the next transition to explore in that state */ int *counts; /* save the automata state if it has some */};
typedef struct _xmlRegInputToken xmlRegInputToken;typedef xmlRegInputToken *xmlRegInputTokenPtr;
struct _xmlRegInputToken { xmlChar *value; void *data;};
struct _xmlRegExecCtxt { int status; /* execution status != 0 indicate an error */ int determinist; /* did we find an indeterministic behaviour */ xmlRegexpPtr comp; /* the compiled regexp */ xmlRegExecCallbacks callback; void *data;
xmlRegStatePtr state;/* the current state */ int transno; /* the current transition on that state */ int transcount; /* the number of chars in char counted transitions */
/* * A stack of rollback states */ int maxRollbacks; int nbRollbacks; xmlRegExecRollback *rollbacks;
/* * The state of the automata if any */ int *counts;
/* * The input stack */ int inputStackMax; int inputStackNr; int index; int *charStack; const xmlChar *inputString; /* when operating on characters */ xmlRegInputTokenPtr inputStack;/* when operating on strings */
/* * error handling */ int errStateNo; /* the error state number */ xmlRegStatePtr errState; /* the error state */ xmlChar *errString; /* the string raising the error */ int *errCounts; /* counters at the error state */ int nbPush;};
#define REGEXP_ALL_COUNTER 0x123456#define REGEXP_ALL_LAX_COUNTER 0x123457
static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top);static void xmlRegFreeState(xmlRegStatePtr state);static void xmlRegFreeAtom(xmlRegAtomPtr atom);static int xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr);static int xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint);static int xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg, int start, int end, const xmlChar *blockName);
/************************************************************************ * * * Regexp memory error handler * * * ************************************************************************//** * xmlRegexpErrMemory: * @extra: extra information * * Handle an out of memory condition */static voidxmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra){ const char *regexp = NULL; if (ctxt != NULL) { regexp = (const char *) ctxt->string; ctxt->error = XML_ERR_NO_MEMORY; } __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP, XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, extra, regexp, NULL, 0, 0, "Memory allocation failed : %s\n", extra);}
/** * xmlRegexpErrCompile: * @extra: extra information * * Handle a compilation failure */static voidxmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra){ const char *regexp = NULL; int idx = 0;
if (ctxt != NULL) { regexp = (const char *) ctxt->string; idx = ctxt->cur - ctxt->string; ctxt->error = XML_REGEXP_COMPILE_ERROR; } __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP, XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL, 0, extra, regexp, NULL, idx, 0, "failed to compile: %s\n", extra);}
/************************************************************************ * * * Allocation/Deallocation * * * ************************************************************************/
static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt);
/** * xmlRegCalloc2: * @dim1: size of first dimension * @dim2: size of second dimension * @elemSize: size of element * * Allocate a two-dimensional array and set all elements to zero. * * Returns the new array or NULL in case of error. */static void*xmlRegCalloc2(size_t dim1, size_t dim2, size_t elemSize) { size_t totalSize; void *ret;
/* Check for overflow */ if ((dim2 == 0) || (elemSize == 0) || (dim1 > SIZE_MAX / dim2 / elemSize)) return (NULL); totalSize = dim1 * dim2 * elemSize; ret = xmlMalloc(totalSize); if (ret != NULL) memset(ret, 0, totalSize); return (ret);}
/** * xmlRegEpxFromParse: * @ctxt: the parser context used to build it * * Allocate a new regexp and fill it with the result from the parser * * Returns the new regexp or NULL in case of error */static xmlRegexpPtrxmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) { xmlRegexpPtr ret;
ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp)); if (ret == NULL) { xmlRegexpErrMemory(ctxt, "compiling regexp"); return(NULL); } memset(ret, 0, sizeof(xmlRegexp)); ret->string = ctxt->string; ret->nbStates = ctxt->nbStates; ret->states = ctxt->states; ret->nbAtoms = ctxt->nbAtoms; ret->atoms = ctxt->atoms; ret->nbCounters = ctxt->nbCounters; ret->counters = ctxt->counters; ret->determinist = ctxt->determinist; ret->flags = ctxt->flags; if (ret->determinist == -1) { if (xmlRegexpIsDeterminist(ret) < 0) { xmlRegexpErrMemory(ctxt, "checking determinism"); xmlFree(ret); return(NULL); } }
if ((ret->determinist != 0) && (ret->nbCounters == 0) && (ctxt->negs == 0) && (ret->atoms != NULL) && (ret->atoms[0] != NULL) && (ret->atoms[0]->type == XML_REGEXP_STRING)) { int i, j, nbstates = 0, nbatoms = 0; int *stateRemap; int *stringRemap; int *transitions; void **transdata; xmlChar **stringMap; xmlChar *value;
/* * Switch to a compact representation * 1/ counting the effective number of states left * 2/ counting the unique number of atoms, and check that * they are all of the string type * 3/ build a table state x atom for the transitions */
stateRemap = xmlMalloc(ret->nbStates * sizeof(int)); if (stateRemap == NULL) { xmlRegexpErrMemory(ctxt, "compiling regexp"); xmlFree(ret); return(NULL); } for (i = 0;i < ret->nbStates;i++) { if (ret->states[i] != NULL) { stateRemap[i] = nbstates; nbstates++; } else { stateRemap[i] = -1; } } stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *)); if (stringMap == NULL) { xmlRegexpErrMemory(ctxt, "compiling regexp"); xmlFree(stateRemap); xmlFree(ret); return(NULL); } stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int)); if (stringRemap == NULL) { xmlRegexpErrMemory(ctxt, "compiling regexp"); xmlFree(stringMap); xmlFree(stateRemap); xmlFree(ret); return(NULL); } for (i = 0;i < ret->nbAtoms;i++) { if ((ret->atoms[i]->type == XML_REGEXP_STRING) && (ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) { value = ret->atoms[i]->valuep; for (j = 0;j < nbatoms;j++) { if (xmlStrEqual(stringMap[j], value)) { stringRemap[i] = j; break; } } if (j >= nbatoms) { stringRemap[i] = nbatoms; stringMap[nbatoms] = xmlStrdup(value); if (stringMap[nbatoms] == NULL) { for (i = 0;i < nbatoms;i++) xmlFree(stringMap[i]); xmlFree(stringRemap); xmlFree(stringMap); xmlFree(stateRemap); xmlFree(ret); return(NULL); } nbatoms++; } } else { xmlFree(stateRemap); xmlFree(stringRemap); for (i = 0;i < nbatoms;i++) xmlFree(stringMap[i]); xmlFree(stringMap); xmlFree(ret); return(NULL); } } transitions = (int *) xmlRegCalloc2(nbstates + 1, nbatoms + 1, sizeof(int)); if (transitions == NULL) { xmlFree(stateRemap); xmlFree(stringRemap); for (i = 0;i < nbatoms;i++) xmlFree(stringMap[i]); xmlFree(stringMap); xmlFree(ret); return(NULL); }
/* * Allocate the transition table. The first entry for each * state corresponds to the state type. */ transdata = NULL;
for (i = 0;i < ret->nbStates;i++) { int stateno, atomno, targetno, prev; xmlRegStatePtr state; xmlRegTransPtr trans;
stateno = stateRemap[i]; if (stateno == -1) continue; state = ret->states[i];
transitions[stateno * (nbatoms + 1)] = state->type;
for (j = 0;j < state->nbTrans;j++) { trans = &(state->trans[j]); if ((trans->to < 0) || (trans->atom == NULL)) continue; atomno = stringRemap[trans->atom->no]; if ((trans->atom->data != NULL) && (transdata == NULL)) { transdata = (void **) xmlRegCalloc2(nbstates, nbatoms, sizeof(void *)); if (transdata == NULL) { xmlRegexpErrMemory(ctxt, "compiling regexp"); break; } } targetno = stateRemap[trans->to]; /* * if the same atom can generate transitions to 2 different * states then it means the automata is not deterministic and * the compact form can't be used ! */ prev = transitions[stateno * (nbatoms + 1) + atomno + 1]; if (prev != 0) { if (prev != targetno + 1) { ret->determinist = 0; if (transdata != NULL) xmlFree(transdata); xmlFree(transitions); xmlFree(stateRemap); xmlFree(stringRemap); for (i = 0;i < nbatoms;i++) xmlFree(stringMap[i]); xmlFree(stringMap); goto not_determ; } } else {#if 0 printf("State %d trans %d: atom %d to %d : %d to %d\n", i, j, trans->atom->no, trans->to, atomno, targetno);#endif transitions[stateno * (nbatoms + 1) + atomno + 1] = targetno + 1; /* to avoid 0 */ if (transdata != NULL) transdata[stateno * nbatoms + atomno] = trans->atom->data; } } } ret->determinist = 1; /* * Cleanup of the old data */ if (ret->states != NULL) { for (i = 0;i < ret->nbStates;i++) xmlRegFreeState(ret->states[i]); xmlFree(ret->states); } ret->states = NULL; ret->nbStates = 0; if (ret->atoms != NULL) { for (i = 0;i < ret->nbAtoms;i++) xmlRegFreeAtom(ret->atoms[i]); xmlFree(ret->atoms); } ret->atoms = NULL; ret->nbAtoms = 0;
ret->compact = transitions; ret->transdata = transdata; ret->stringMap = stringMap; ret->nbstrings = nbatoms; ret->nbstates = nbstates; xmlFree(stateRemap); xmlFree(stringRemap); }not_determ: ctxt->string = NULL; ctxt->nbStates = 0; ctxt->states = NULL; ctxt->nbAtoms = 0; ctxt->atoms = NULL; ctxt->nbCounters = 0; ctxt->counters = NULL; return(ret);}
/** * xmlRegNewParserCtxt: * @string: the string to parse * * Allocate a new regexp parser context * * Returns the new context or NULL in case of error */static xmlRegParserCtxtPtrxmlRegNewParserCtxt(const xmlChar *string) { xmlRegParserCtxtPtr ret;
ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt)); if (ret == NULL) return(NULL); memset(ret, 0, sizeof(xmlRegParserCtxt)); if (string != NULL) ret->string = xmlStrdup(string); ret->cur = ret->string; ret->neg = 0; ret->negs = 0; ret->error = 0; ret->determinist = -1; return(ret);}
/** * xmlRegNewRange: * @ctxt: the regexp parser context * @neg: is that negative * @type: the type of range * @start: the start codepoint * @end: the end codepoint * * Allocate a new regexp range * * Returns the new range or NULL in case of error */static xmlRegRangePtrxmlRegNewRange(xmlRegParserCtxtPtr ctxt, int neg, xmlRegAtomType type, int start, int end) { xmlRegRangePtr ret;
ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange)); if (ret == NULL) { xmlRegexpErrMemory(ctxt, "allocating range"); return(NULL); } ret->neg = neg; ret->type = type; ret->start = start; ret->end = end; return(ret);}
/** * xmlRegFreeRange: * @range: the regexp range * * Free a regexp range */static voidxmlRegFreeRange(xmlRegRangePtr range) { if (range == NULL) return;
if (range->blockName != NULL) xmlFree(range->blockName); xmlFree(range);}
/** * xmlRegCopyRange: * @range: the regexp range * * Copy a regexp range * * Returns the new copy or NULL in case of error. */static xmlRegRangePtrxmlRegCopyRange(xmlRegParserCtxtPtr ctxt, xmlRegRangePtr range) { xmlRegRangePtr ret;
if (range == NULL) return(NULL);
ret = xmlRegNewRange(ctxt, range->neg, range->type, range->start, range->end); if (ret == NULL) return(NULL); if (range->blockName != NULL) { ret->blockName = xmlStrdup(range->blockName); if (ret->blockName == NULL) { xmlRegexpErrMemory(ctxt, "allocating range"); xmlRegFreeRange(ret); return(NULL); } } return(ret);}
/** * xmlRegNewAtom: * @ctxt: the regexp parser context * @type: the type of atom * * Allocate a new atom * * Returns the new atom or NULL in case of error */static xmlRegAtomPtrxmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) { xmlRegAtomPtr ret;
ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom)); if (ret == NULL) { xmlRegexpErrMemory(ctxt, "allocating atom"); return(NULL); } memset(ret, 0, sizeof(xmlRegAtom)); ret->type = type; ret->quant = XML_REGEXP_QUANT_ONCE; ret->min = 0; ret->max = 0; return(ret);}
/** * xmlRegFreeAtom: * @atom: the regexp atom * * Free a regexp atom */static voidxmlRegFreeAtom(xmlRegAtomPtr atom) { int i;
if (atom == NULL) return;
for (i = 0;i < atom->nbRanges;i++) xmlRegFreeRange(atom->ranges[i]); if (atom->ranges != NULL) xmlFree(atom->ranges); if ((atom->type == XML_REGEXP_STRING) && (atom->valuep != NULL)) xmlFree(atom->valuep); if ((atom->type == XML_REGEXP_STRING) && (atom->valuep2 != NULL)) xmlFree(atom->valuep2); if ((atom->type == XML_REGEXP_BLOCK_NAME) && (atom->valuep != NULL)) xmlFree(atom->valuep); xmlFree(atom);}
/** * xmlRegCopyAtom: * @ctxt: the regexp parser context * @atom: the original atom * * Allocate a new regexp range * * Returns the new atom or NULL in case of error */static xmlRegAtomPtrxmlRegCopyAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) { xmlRegAtomPtr ret;
ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom)); if (ret == NULL) { xmlRegexpErrMemory(ctxt, "copying atom"); return(NULL); } memset(ret, 0, sizeof(xmlRegAtom)); ret->type = atom->type; ret->quant = atom->quant; ret->min = atom->min; ret->max = atom->max; if (atom->nbRanges > 0) { int i;
ret->ranges = (xmlRegRangePtr *) xmlMalloc(sizeof(xmlRegRangePtr) * atom->nbRanges); if (ret->ranges == NULL) { xmlRegexpErrMemory(ctxt, "copying atom"); goto error; } for (i = 0;i < atom->nbRanges;i++) { ret->ranges[i] = xmlRegCopyRange(ctxt, atom->ranges[i]); if (ret->ranges[i] == NULL) goto error; ret->nbRanges = i + 1; } } return(ret);
error: xmlRegFreeAtom(ret); return(NULL);}
static xmlRegStatePtrxmlRegNewState(xmlRegParserCtxtPtr ctxt) { xmlRegStatePtr ret;
ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState)); if (ret == NULL) { xmlRegexpErrMemory(ctxt, "allocating state"); return(NULL); } memset(ret, 0, sizeof(xmlRegState)); ret->type = XML_REGEXP_TRANS_STATE; ret->mark = XML_REGEXP_MARK_NORMAL; return(ret);}
/** * xmlRegFreeState: * @state: the regexp state * * Free a regexp state */static voidxmlRegFreeState(xmlRegStatePtr state) { if (state == NULL) return;
if (state->trans != NULL) xmlFree(state->trans); if (state->transTo != NULL) xmlFree(state->transTo); xmlFree(state);}
/** * xmlRegFreeParserCtxt: * @ctxt: the regexp parser context * * Free a regexp parser context */static voidxmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) { int i; if (ctxt == NULL) return;
if (ctxt->string != NULL) xmlFree(ctxt->string); if (ctxt->states != NULL) { for (i = 0;i < ctxt->nbStates;i++) xmlRegFreeState(ctxt->states[i]); xmlFree(ctxt->states); } if (ctxt->atoms != NULL) { for (i = 0;i < ctxt->nbAtoms;i++) xmlRegFreeAtom(ctxt->atoms[i]); xmlFree(ctxt->atoms); } if (ctxt->counters != NULL) xmlFree(ctxt->counters); xmlFree(ctxt);}
/************************************************************************ * * * Display of Data structures * * * ************************************************************************/
static voidxmlRegPrintAtomType(FILE *output, xmlRegAtomType type) { switch (type) { case XML_REGEXP_EPSILON: fprintf(output, "epsilon "); break; case XML_REGEXP_CHARVAL: fprintf(output, "charval "); break; case XML_REGEXP_RANGES: fprintf(output, "ranges "); break; case XML_REGEXP_SUBREG: fprintf(output, "subexpr "); break; case XML_REGEXP_STRING: fprintf(output, "string "); break; case XML_REGEXP_ANYCHAR: fprintf(output, "anychar "); break; case XML_REGEXP_ANYSPACE: fprintf(output, "anyspace "); break; case XML_REGEXP_NOTSPACE: fprintf(output, "notspace "); break; case XML_REGEXP_INITNAME: fprintf(output, "initname "); break; case XML_REGEXP_NOTINITNAME: fprintf(output, "notinitname "); break; case XML_REGEXP_NAMECHAR: fprintf(output, "namechar "); break; case XML_REGEXP_NOTNAMECHAR: fprintf(output, "notnamechar "); break; case XML_REGEXP_DECIMAL: fprintf(output, "decimal "); break; case XML_REGEXP_NOTDECIMAL: fprintf(output, "notdecimal "); break; case XML_REGEXP_REALCHAR: fprintf(output, "realchar "); break; case XML_REGEXP_NOTREALCHAR: fprintf(output, "notrealchar "); break; case XML_REGEXP_LETTER: fprintf(output, "LETTER "); break; case XML_REGEXP_LETTER_UPPERCASE: fprintf(output, "LETTER_UPPERCASE "); break; case XML_REGEXP_LETTER_LOWERCASE: fprintf(output, "LETTER_LOWERCASE "); break; case XML_REGEXP_LETTER_TITLECASE: fprintf(output, "LETTER_TITLECASE "); break; case XML_REGEXP_LETTER_MODIFIER: fprintf(output, "LETTER_MODIFIER "); break; case XML_REGEXP_LETTER_OTHERS: fprintf(output, "LETTER_OTHERS "); break; case XML_REGEXP_MARK: fprintf(output, "MARK "); break; case XML_REGEXP_MARK_NONSPACING: fprintf(output, "MARK_NONSPACING "); break; case XML_REGEXP_MARK_SPACECOMBINING: fprintf(output, "MARK_SPACECOMBINING "); break; case XML_REGEXP_MARK_ENCLOSING: fprintf(output, "MARK_ENCLOSING "); break; case XML_REGEXP_NUMBER: fprintf(output, "NUMBER "); break; case XML_REGEXP_NUMBER_DECIMAL: fprintf(output, "NUMBER_DECIMAL "); break; case XML_REGEXP_NUMBER_LETTER: fprintf(output, "NUMBER_LETTER "); break; case XML_REGEXP_NUMBER_OTHERS: fprintf(output, "NUMBER_OTHERS "); break; case XML_REGEXP_PUNCT: fprintf(output, "PUNCT "); break; case XML_REGEXP_PUNCT_CONNECTOR: fprintf(output, "PUNCT_CONNECTOR "); break; case XML_REGEXP_PUNCT_DASH: fprintf(output, "PUNCT_DASH "); break; case XML_REGEXP_PUNCT_OPEN: fprintf(output, "PUNCT_OPEN "); break; case XML_REGEXP_PUNCT_CLOSE: fprintf(output, "PUNCT_CLOSE "); break; case XML_REGEXP_PUNCT_INITQUOTE: fprintf(output, "PUNCT_INITQUOTE "); break; case XML_REGEXP_PUNCT_FINQUOTE: fprintf(output, "PUNCT_FINQUOTE "); break; case XML_REGEXP_PUNCT_OTHERS: fprintf(output, "PUNCT_OTHERS "); break; case XML_REGEXP_SEPAR: fprintf(output, "SEPAR "); break; case XML_REGEXP_SEPAR_SPACE: fprintf(output, "SEPAR_SPACE "); break; case XML_REGEXP_SEPAR_LINE: fprintf(output, "SEPAR_LINE "); break; case XML_REGEXP_SEPAR_PARA: fprintf(output, "SEPAR_PARA "); break; case XML_REGEXP_SYMBOL: fprintf(output, "SYMBOL "); break; case XML_REGEXP_SYMBOL_MATH: fprintf(output, "SYMBOL_MATH "); break; case XML_REGEXP_SYMBOL_CURRENCY: fprintf(output, "SYMBOL_CURRENCY "); break; case XML_REGEXP_SYMBOL_MODIFIER: fprintf(output, "SYMBOL_MODIFIER "); break; case XML_REGEXP_SYMBOL_OTHERS: fprintf(output, "SYMBOL_OTHERS "); break; case XML_REGEXP_OTHER: fprintf(output, "OTHER "); break; case XML_REGEXP_OTHER_CONTROL: fprintf(output, "OTHER_CONTROL "); break; case XML_REGEXP_OTHER_FORMAT: fprintf(output, "OTHER_FORMAT "); break; case XML_REGEXP_OTHER_PRIVATE: fprintf(output, "OTHER_PRIVATE "); break; case XML_REGEXP_OTHER_NA: fprintf(output, "OTHER_NA "); break; case XML_REGEXP_BLOCK_NAME: fprintf(output, "BLOCK "); break; }}
static voidxmlRegPrintQuantType(FILE *output, xmlRegQuantType type) { switch (type) { case XML_REGEXP_QUANT_EPSILON: fprintf(output, "epsilon "); break; case XML_REGEXP_QUANT_ONCE: fprintf(output, "once "); break; case XML_REGEXP_QUANT_OPT: fprintf(output, "? "); break; case XML_REGEXP_QUANT_MULT: fprintf(output, "* "); break; case XML_REGEXP_QUANT_PLUS: fprintf(output, "+ "); break; case XML_REGEXP_QUANT_RANGE: fprintf(output, "range "); break; case XML_REGEXP_QUANT_ONCEONLY: fprintf(output, "onceonly "); break; case XML_REGEXP_QUANT_ALL: fprintf(output, "all "); break; }}static voidxmlRegPrintRange(FILE *output, xmlRegRangePtr range) { fprintf(output, " range: "); if (range->neg) fprintf(output, "negative "); xmlRegPrintAtomType(output, range->type); fprintf(output, "%c - %c\n", range->start, range->end);}
static voidxmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) { fprintf(output, " atom: "); if (atom == NULL) { fprintf(output, "NULL\n"); return; } if (atom->neg) fprintf(output, "not "); xmlRegPrintAtomType(output, atom->type); xmlRegPrintQuantType(output, atom->quant); if (atom->quant == XML_REGEXP_QUANT_RANGE) fprintf(output, "%d-%d ", atom->min, atom->max); if (atom->type == XML_REGEXP_STRING) fprintf(output, "'%s' ", (char *) atom->valuep); if (atom->type == XML_REGEXP_CHARVAL) fprintf(output, "char %c\n", atom->codepoint); else if (atom->type == XML_REGEXP_RANGES) { int i; fprintf(output, "%d entries\n", atom->nbRanges); for (i = 0; i < atom->nbRanges;i++) xmlRegPrintRange(output, atom->ranges[i]); } else if (atom->type == XML_REGEXP_SUBREG) { fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no); } else { fprintf(output, "\n"); }}
static voidxmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) { fprintf(output, " trans: "); if (trans == NULL) { fprintf(output, "NULL\n"); return; } if (trans->to < 0) { fprintf(output, "removed\n"); return; } if (trans->nd != 0) { if (trans->nd == 2) fprintf(output, "last not determinist, "); else fprintf(output, "not determinist, "); } if (trans->counter >= 0) { fprintf(output, "counted %d, ", trans->counter); } if (trans->count == REGEXP_ALL_COUNTER) { fprintf(output, "all transition, "); } else if (trans->count >= 0) { fprintf(output, "count based %d, ", trans->count); } if (trans->atom == NULL) { fprintf(output, "epsilon to %d\n", trans->to); return; } if (trans->atom->type == XML_REGEXP_CHARVAL) fprintf(output, "char %c ", trans->atom->codepoint); fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to);}
static voidxmlRegPrintState(FILE *output, xmlRegStatePtr state) { int i;
fprintf(output, " state: "); if (state == NULL) { fprintf(output, "NULL\n"); return; } if (state->type == XML_REGEXP_START_STATE) fprintf(output, "START "); if (state->type == XML_REGEXP_FINAL_STATE) fprintf(output, "FINAL ");
fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans); for (i = 0;i < state->nbTrans; i++) { xmlRegPrintTrans(output, &(state->trans[i])); }}
/************************************************************************ * * * Finite Automata structures manipulations * * * ************************************************************************/
static xmlRegRangePtrxmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom, int neg, xmlRegAtomType type, int start, int end, xmlChar *blockName) { xmlRegRangePtr range;
if (atom == NULL) { ERROR("add range: atom is NULL"); return(NULL); } if (atom->type != XML_REGEXP_RANGES) { ERROR("add range: atom is not ranges"); return(NULL); } if (atom->maxRanges == 0) { atom->maxRanges = 4; atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges * sizeof(xmlRegRangePtr)); if (atom->ranges == NULL) { xmlRegexpErrMemory(ctxt, "adding ranges"); atom->maxRanges = 0; return(NULL); } } else if (atom->nbRanges >= atom->maxRanges) { xmlRegRangePtr *tmp; atom->maxRanges *= 2; tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges * sizeof(xmlRegRangePtr)); if (tmp == NULL) { xmlRegexpErrMemory(ctxt, "adding ranges"); atom->maxRanges /= 2; return(NULL); } atom->ranges = tmp; } range = xmlRegNewRange(ctxt, neg, type, start, end); if (range == NULL) return(NULL); range->blockName = blockName; atom->ranges[atom->nbRanges++] = range;
return(range);}
static intxmlRegGetCounter(xmlRegParserCtxtPtr ctxt) { if (ctxt->maxCounters == 0) { ctxt->maxCounters = 4; ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters * sizeof(xmlRegCounter)); if (ctxt->counters == NULL) { xmlRegexpErrMemory(ctxt, "allocating counter"); ctxt->maxCounters = 0; return(-1); } } else if (ctxt->nbCounters >= ctxt->maxCounters) { xmlRegCounter *tmp; ctxt->maxCounters *= 2; tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters * sizeof(xmlRegCounter)); if (tmp == NULL) { xmlRegexpErrMemory(ctxt, "allocating counter"); ctxt->maxCounters /= 2; return(-1); } ctxt->counters = tmp; } ctxt->counters[ctxt->nbCounters].min = -1; ctxt->counters[ctxt->nbCounters].max = -1; return(ctxt->nbCounters++);}
static intxmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) { if (atom == NULL) { ERROR("atom push: atom is NULL"); return(-1); } if (ctxt->nbAtoms >= ctxt->maxAtoms) { size_t newSize = ctxt->maxAtoms ? ctxt->maxAtoms * 2 : 4; xmlRegAtomPtr *tmp;
tmp = xmlRealloc(ctxt->atoms, newSize * sizeof(xmlRegAtomPtr)); if (tmp == NULL) { xmlRegexpErrMemory(ctxt, "allocating counter"); return(-1); } ctxt->atoms = tmp; ctxt->maxAtoms = newSize; } atom->no = ctxt->nbAtoms; ctxt->atoms[ctxt->nbAtoms++] = atom; return(0);}
static voidxmlRegStateAddTransTo(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr target, int from) { if (target->maxTransTo == 0) { target->maxTransTo = 8; target->transTo = (int *) xmlMalloc(target->maxTransTo * sizeof(int)); if (target->transTo == NULL) { xmlRegexpErrMemory(ctxt, "adding transition"); target->maxTransTo = 0; return; } } else if (target->nbTransTo >= target->maxTransTo) { int *tmp; target->maxTransTo *= 2; tmp = (int *) xmlRealloc(target->transTo, target->maxTransTo * sizeof(int)); if (tmp == NULL) { xmlRegexpErrMemory(ctxt, "adding transition"); target->maxTransTo /= 2; return; } target->transTo = tmp; } target->transTo[target->nbTransTo] = from; target->nbTransTo++;}
static voidxmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state, xmlRegAtomPtr atom, xmlRegStatePtr target, int counter, int count) {
int nrtrans;
if (state == NULL) { ERROR("add state: state is NULL"); return; } if (target == NULL) { ERROR("add state: target is NULL"); return; } /* * Other routines follow the philosophy 'When in doubt, add a transition' * so we check here whether such a transition is already present and, if * so, silently ignore this request. */
for (nrtrans = state->nbTrans - 1; nrtrans >= 0; nrtrans--) { xmlRegTransPtr trans = &(state->trans[nrtrans]); if ((trans->atom == atom) && (trans->to == target->no) && (trans->counter == counter) && (trans->count == count)) { return; } }
if (state->maxTrans == 0) { state->maxTrans = 8; state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans * sizeof(xmlRegTrans)); if (state->trans == NULL) { xmlRegexpErrMemory(ctxt, "adding transition"); state->maxTrans = 0; return; } } else if (state->nbTrans >= state->maxTrans) { xmlRegTrans *tmp; state->maxTrans *= 2; tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans * sizeof(xmlRegTrans)); if (tmp == NULL) { xmlRegexpErrMemory(ctxt, "adding transition"); state->maxTrans /= 2; return; } state->trans = tmp; }
state->trans[state->nbTrans].atom = atom; state->trans[state->nbTrans].to = target->no; state->trans[state->nbTrans].counter = counter; state->trans[state->nbTrans].count = count; state->trans[state->nbTrans].nd = 0; state->nbTrans++; xmlRegStateAddTransTo(ctxt, target, state->no);}
static xmlRegStatePtrxmlRegStatePush(xmlRegParserCtxtPtr ctxt) { xmlRegStatePtr state;
if (ctxt->nbStates >= ctxt->maxStates) { size_t newSize = ctxt->maxStates ? ctxt->maxStates * 2 : 4; xmlRegStatePtr *tmp;
tmp = xmlRealloc(ctxt->states, newSize * sizeof(tmp[0])); if (tmp == NULL) { xmlRegexpErrMemory(ctxt, "adding state"); return(NULL); } ctxt->states = tmp; ctxt->maxStates = newSize; }
state = xmlRegNewState(ctxt); if (state == NULL) return(NULL);
state->no = ctxt->nbStates; ctxt->states[ctxt->nbStates++] = state;
return(state);}
/** * xmlFAGenerateAllTransition: * @ctxt: a regexp parser context * @from: the from state * @to: the target state or NULL for building a new one * @lax: * */static intxmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from, xmlRegStatePtr to, int lax) { if (to == NULL) { to = xmlRegStatePush(ctxt); if (to == NULL) return(-1); ctxt->state = to; } if (lax) xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_LAX_COUNTER); else xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_COUNTER); return(0);}
/** * xmlFAGenerateEpsilonTransition: * @ctxt: a regexp parser context * @from: the from state * @to: the target state or NULL for building a new one * */static intxmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from, xmlRegStatePtr to) { if (to == NULL) { to = xmlRegStatePush(ctxt); if (to == NULL) return(-1); ctxt->state = to; } xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1); return(0);}
/** * xmlFAGenerateCountedEpsilonTransition: * @ctxt: a regexp parser context * @from: the from state * @to: the target state or NULL for building a new one * counter: the counter for that transition * */static intxmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from, xmlRegStatePtr to, int counter) { if (to == NULL) { to = xmlRegStatePush(ctxt); if (to == NULL) return(-1); ctxt->state = to; } xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1); return(0);}
/** * xmlFAGenerateCountedTransition: * @ctxt: a regexp parser context * @from: the from state * @to: the target state or NULL for building a new one * counter: the counter for that transition * */static intxmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from, xmlRegStatePtr to, int counter) { if (to == NULL) { to = xmlRegStatePush(ctxt); if (to == NULL) return(-1); ctxt->state = to; } xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter); return(0);}
/** * xmlFAGenerateTransitions: * @ctxt: a regexp parser context * @from: the from state * @to: the target state or NULL for building a new one * @atom: the atom generating the transition * * Returns 0 if success and -1 in case of error. */static intxmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from, xmlRegStatePtr to, xmlRegAtomPtr atom) { xmlRegStatePtr end; int nullable = 0;
if (atom == NULL) { ERROR("generate transition: atom == NULL"); return(-1); } if (atom->type == XML_REGEXP_SUBREG) { /* * this is a subexpression handling one should not need to * create a new node except for XML_REGEXP_QUANT_RANGE. */ if ((to != NULL) && (atom->stop != to) && (atom->quant != XML_REGEXP_QUANT_RANGE)) { /* * Generate an epsilon transition to link to the target */ xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);#ifdef DV } else if ((to == NULL) && (atom->quant != XML_REGEXP_QUANT_RANGE) && (atom->quant != XML_REGEXP_QUANT_ONCE)) { to = xmlRegStatePush(ctxt, to); if (to == NULL) return(-1); ctxt->state = to; xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);#endif } switch (atom->quant) { case XML_REGEXP_QUANT_OPT: atom->quant = XML_REGEXP_QUANT_ONCE; /* * transition done to the state after end of atom. * 1. set transition from atom start to new state * 2. set transition from atom end to this state. */ if (to == NULL) { xmlFAGenerateEpsilonTransition(ctxt, atom->start, 0); xmlFAGenerateEpsilonTransition(ctxt, atom->stop, ctxt->state); } else { xmlFAGenerateEpsilonTransition(ctxt, atom->start, to); } break; case XML_REGEXP_QUANT_MULT: atom->quant = XML_REGEXP_QUANT_ONCE; xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop); xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start); break; case XML_REGEXP_QUANT_PLUS: atom->quant = XML_REGEXP_QUANT_ONCE; xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start); break; case XML_REGEXP_QUANT_RANGE: { int counter; xmlRegStatePtr inter, newstate;
/* * create the final state now if needed */ if (to != NULL) { newstate = to; } else { newstate = xmlRegStatePush(ctxt); if (newstate == NULL) return(-1); }
/* * The principle here is to use counted transition * to avoid explosion in the number of states in the * graph. This is clearly more complex but should not * be exploitable at runtime. */ if ((atom->min == 0) && (atom->start0 == NULL)) { xmlRegAtomPtr copy; /* * duplicate a transition based on atom to count next * occurrences after 1. We cannot loop to atom->start * directly because we need an epsilon transition to * newstate. */ /* ???? For some reason it seems we never reach that case, I suppose this got optimized out before when building the automata */ copy = xmlRegCopyAtom(ctxt, atom); if (copy == NULL) return(-1); copy->quant = XML_REGEXP_QUANT_ONCE; copy->min = 0; copy->max = 0;
if (xmlFAGenerateTransitions(ctxt, atom->start, NULL, copy) < 0) { xmlRegFreeAtom(copy); return(-1); } inter = ctxt->state; counter = xmlRegGetCounter(ctxt); if (counter < 0) return(-1); ctxt->counters[counter].min = atom->min - 1; ctxt->counters[counter].max = atom->max - 1; /* count the number of times we see it again */ xmlFAGenerateCountedEpsilonTransition(ctxt, inter, atom->stop, counter); /* allow a way out based on the count */ xmlFAGenerateCountedTransition(ctxt, inter, newstate, counter); /* and also allow a direct exit for 0 */ xmlFAGenerateEpsilonTransition(ctxt, atom->start, newstate); } else { /* * either we need the atom at least once or there * is an atom->start0 allowing to easily plug the * epsilon transition. */ counter = xmlRegGetCounter(ctxt); if (counter < 0) return(-1); ctxt->counters[counter].min = atom->min - 1; ctxt->counters[counter].max = atom->max - 1; /* allow a way out based on the count */ xmlFAGenerateCountedTransition(ctxt, atom->stop, newstate, counter); /* count the number of times we see it again */ xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop, atom->start, counter); /* and if needed allow a direct exit for 0 */ if (atom->min == 0) xmlFAGenerateEpsilonTransition(ctxt, atom->start0, newstate);
} atom->min = 0; atom->max = 0; atom->quant = XML_REGEXP_QUANT_ONCE; ctxt->state = newstate; } default: break; } if (xmlRegAtomPush(ctxt, atom) < 0) return(-1); return(0); } if ((atom->min == 0) && (atom->max == 0) && (atom->quant == XML_REGEXP_QUANT_RANGE)) { /* * we can discard the atom and generate an epsilon transition instead */ if (to == NULL) { to = xmlRegStatePush(ctxt); if (to == NULL) return(-1); } xmlFAGenerateEpsilonTransition(ctxt, from, to); ctxt->state = to; xmlRegFreeAtom(atom); return(0); } if (to == NULL) { to = xmlRegStatePush(ctxt); if (to == NULL) return(-1); } end = to; if ((atom->quant == XML_REGEXP_QUANT_MULT) || (atom->quant == XML_REGEXP_QUANT_PLUS)) { /* * Do not pollute the target state by adding transitions from * it as it is likely to be the shared target of multiple branches. * So isolate with an epsilon transition. */ xmlRegStatePtr tmp;
tmp = xmlRegStatePush(ctxt); if (tmp == NULL) return(-1); xmlFAGenerateEpsilonTransition(ctxt, tmp, to); to = tmp; } if ((atom->quant == XML_REGEXP_QUANT_RANGE) && (atom->min == 0) && (atom->max > 0)) { nullable = 1; atom->min = 1; if (atom->max == 1) atom->quant = XML_REGEXP_QUANT_OPT; } xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1); ctxt->state = end; switch (atom->quant) { case XML_REGEXP_QUANT_OPT: atom->quant = XML_REGEXP_QUANT_ONCE; xmlFAGenerateEpsilonTransition(ctxt, from, to); break; case XML_REGEXP_QUANT_MULT: atom->quant = XML_REGEXP_QUANT_ONCE; xmlFAGenerateEpsilonTransition(ctxt, from, to); xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1); break; case XML_REGEXP_QUANT_PLUS: atom->quant = XML_REGEXP_QUANT_ONCE; xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1); break; case XML_REGEXP_QUANT_RANGE: if (nullable) xmlFAGenerateEpsilonTransition(ctxt, from, to); break; default: break; } if (xmlRegAtomPush(ctxt, atom) < 0) return(-1); return(0);}
/** * xmlFAReduceEpsilonTransitions: * @ctxt: a regexp parser context * @fromnr: the from state * @tonr: the to state * @counter: should that transition be associated to a counted * */static voidxmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr, int tonr, int counter) { int transnr; xmlRegStatePtr from; xmlRegStatePtr to;
from = ctxt->states[fromnr]; if (from == NULL) return; to = ctxt->states[tonr]; if (to == NULL) return; if ((to->mark == XML_REGEXP_MARK_START) || (to->mark == XML_REGEXP_MARK_VISITED)) return;
to->mark = XML_REGEXP_MARK_VISITED; if (to->type == XML_REGEXP_FINAL_STATE) { from->type = XML_REGEXP_FINAL_STATE; } for (transnr = 0;transnr < to->nbTrans;transnr++) { xmlRegTransPtr t1 = &to->trans[transnr]; int tcounter;
if (t1->to < 0) continue; if (t1->counter >= 0) { /* assert(counter < 0); */ tcounter = t1->counter; } else { tcounter = counter; } if (t1->atom == NULL) { /* * Don't remove counted transitions * Don't loop either */ if (t1->to != fromnr) { if (t1->count >= 0) { xmlRegStateAddTrans(ctxt, from, NULL, ctxt->states[t1->to], -1, t1->count); } else { xmlFAReduceEpsilonTransitions(ctxt, fromnr, t1->to, tcounter); } } } else { xmlRegStateAddTrans(ctxt, from, t1->atom, ctxt->states[t1->to], tcounter, -1); } }}
/** * xmlFAFinishReduceEpsilonTransitions: * @ctxt: a regexp parser context * @fromnr: the from state * @tonr: the to state * @counter: should that transition be associated to a counted * */static voidxmlFAFinishReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int tonr) { int transnr; xmlRegStatePtr to;
to = ctxt->states[tonr]; if (to == NULL) return; if ((to->mark == XML_REGEXP_MARK_START) || (to->mark == XML_REGEXP_MARK_NORMAL)) return;
to->mark = XML_REGEXP_MARK_NORMAL; for (transnr = 0;transnr < to->nbTrans;transnr++) { xmlRegTransPtr t1 = &to->trans[transnr]; if ((t1->to >= 0) && (t1->atom == NULL)) xmlFAFinishReduceEpsilonTransitions(ctxt, t1->to); }}
/** * xmlFAEliminateSimpleEpsilonTransitions: * @ctxt: a regexp parser context * * Eliminating general epsilon transitions can get costly in the general * algorithm due to the large amount of generated new transitions and * associated comparisons. However for simple epsilon transition used just * to separate building blocks when generating the automata this can be * reduced to state elimination: * - if there exists an epsilon from X to Y * - if there is no other transition from X * then X and Y are semantically equivalent and X can be eliminated * If X is the start state then make Y the start state, else replace the * target of all transitions to X by transitions to Y. * * If X is a final state, skip it. * Otherwise it would be necessary to manipulate counters for this case when * eliminating state 2: * State 1 has a transition with an atom to state 2. * State 2 is final and has an epsilon transition to state 1. */static voidxmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { int statenr, i, j, newto; xmlRegStatePtr state, tmp;
for (statenr = 0;statenr < ctxt->nbStates;statenr++) { state = ctxt->states[statenr]; if (state == NULL) continue; if (state->nbTrans != 1) continue; if (state->type == XML_REGEXP_UNREACH_STATE || state->type == XML_REGEXP_FINAL_STATE) continue; /* is the only transition out a basic transition */ if ((state->trans[0].atom == NULL) && (state->trans[0].to >= 0) && (state->trans[0].to != statenr) && (state->trans[0].counter < 0) && (state->trans[0].count < 0)) { newto = state->trans[0].to;
if (state->type == XML_REGEXP_START_STATE) { } else { for (i = 0;i < state->nbTransTo;i++) { tmp = ctxt->states[state->transTo[i]]; for (j = 0;j < tmp->nbTrans;j++) { if (tmp->trans[j].to == statenr) { tmp->trans[j].to = -1; xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom, ctxt->states[newto], tmp->trans[j].counter, tmp->trans[j].count); } } } if (state->type == XML_REGEXP_FINAL_STATE) ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE; /* eliminate the transition completely */ state->nbTrans = 0;
state->type = XML_REGEXP_UNREACH_STATE;
}
} }}/** * xmlFAEliminateEpsilonTransitions: * @ctxt: a regexp parser context * */static voidxmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { int statenr, transnr; xmlRegStatePtr state; int has_epsilon;
if (ctxt->states == NULL) return;
/* * Eliminate simple epsilon transition and the associated unreachable * states. */ xmlFAEliminateSimpleEpsilonTransitions(ctxt); for (statenr = 0;statenr < ctxt->nbStates;statenr++) { state = ctxt->states[statenr]; if ((state != NULL) && (state->type == XML_REGEXP_UNREACH_STATE)) { xmlRegFreeState(state); ctxt->states[statenr] = NULL; } }
has_epsilon = 0;
/* * Build the completed transitions bypassing the epsilons * Use a marking algorithm to avoid loops * Mark sink states too. * Process from the latest states backward to the start when * there is long cascading epsilon chains this minimize the * recursions and transition compares when adding the new ones */ for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) { state = ctxt->states[statenr]; if (state == NULL) continue; if ((state->nbTrans == 0) && (state->type != XML_REGEXP_FINAL_STATE)) { state->type = XML_REGEXP_SINK_STATE; } for (transnr = 0;transnr < state->nbTrans;transnr++) { if ((state->trans[transnr].atom == NULL) && (state->trans[transnr].to >= 0)) { if (state->trans[transnr].to == statenr) { state->trans[transnr].to = -1; } else if (state->trans[transnr].count < 0) { int newto = state->trans[transnr].to;
has_epsilon = 1; state->trans[transnr].to = -2; state->mark = XML_REGEXP_MARK_START; xmlFAReduceEpsilonTransitions(ctxt, statenr, newto, state->trans[transnr].counter); xmlFAFinishReduceEpsilonTransitions(ctxt, newto); state->mark = XML_REGEXP_MARK_NORMAL; } } } } /* * Eliminate the epsilon transitions */ if (has_epsilon) { for (statenr = 0;statenr < ctxt->nbStates;statenr++) { state = ctxt->states[statenr]; if (state == NULL) continue; for (transnr = 0;transnr < state->nbTrans;transnr++) { xmlRegTransPtr trans = &(state->trans[transnr]); if ((trans->atom == NULL) && (trans->count < 0) && (trans->to >= 0)) { trans->to = -1; } } } }
/* * Use this pass to detect unreachable states too */ for (statenr = 0;statenr < ctxt->nbStates;statenr++) { state = ctxt->states[statenr]; if (state != NULL) state->reached = XML_REGEXP_MARK_NORMAL; } state = ctxt->states[0]; if (state != NULL) state->reached = XML_REGEXP_MARK_START; while (state != NULL) { xmlRegStatePtr target = NULL; state->reached = XML_REGEXP_MARK_VISITED; /* * Mark all states reachable from the current reachable state */ for (transnr = 0;transnr < state->nbTrans;transnr++) { if ((state->trans[transnr].to >= 0) && ((state->trans[transnr].atom != NULL) || (state->trans[transnr].count >= 0))) { int newto = state->trans[transnr].to;
if (ctxt->states[newto] == NULL) continue; if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) { ctxt->states[newto]->reached = XML_REGEXP_MARK_START; target = ctxt->states[newto]; } } }
/* * find the next accessible state not explored */ if (target == NULL) { for (statenr = 1;statenr < ctxt->nbStates;statenr++) { state = ctxt->states[statenr]; if ((state != NULL) && (state->reached == XML_REGEXP_MARK_START)) { target = state; break; } } } state = target; } for (statenr = 0;statenr < ctxt->nbStates;statenr++) { state = ctxt->states[statenr]; if ((state != NULL) && (state->reached == XML_REGEXP_MARK_NORMAL)) { xmlRegFreeState(state); ctxt->states[statenr] = NULL; } }
}
static intxmlFACompareRanges(xmlRegRangePtr range1, xmlRegRangePtr range2) { int ret = 0;
if ((range1->type == XML_REGEXP_RANGES) || (range2->type == XML_REGEXP_RANGES) || (range2->type == XML_REGEXP_SUBREG) || (range1->type == XML_REGEXP_SUBREG) || (range1->type == XML_REGEXP_STRING) || (range2->type == XML_REGEXP_STRING)) return(-1);
/* put them in order */ if (range1->type > range2->type) { xmlRegRangePtr tmp;
tmp = range1; range1 = range2; range2 = tmp; } if ((range1->type == XML_REGEXP_ANYCHAR) || (range2->type == XML_REGEXP_ANYCHAR)) { ret = 1; } else if ((range1->type == XML_REGEXP_EPSILON) || (range2->type == XML_REGEXP_EPSILON)) { return(0); } else if (range1->type == range2->type) { if (range1->type != XML_REGEXP_CHARVAL) ret = 1; else if ((range1->end < range2->start) || (range2->end < range1->start)) ret = 0; else ret = 1; } else if (range1->type == XML_REGEXP_CHARVAL) { int codepoint; int neg = 0;
/* * just check all codepoints in the range for acceptance, * this is usually way cheaper since done only once at * compilation than testing over and over at runtime or * pushing too many states when evaluating. */ if (((range1->neg == 0) && (range2->neg != 0)) || ((range1->neg != 0) && (range2->neg == 0))) neg = 1;
for (codepoint = range1->start;codepoint <= range1->end ;codepoint++) { ret = xmlRegCheckCharacterRange(range2->type, codepoint, 0, range2->start, range2->end, range2->blockName); if (ret < 0) return(-1); if (((neg == 1) && (ret == 0)) || ((neg == 0) && (ret == 1))) return(1); } return(0); } else if ((range1->type == XML_REGEXP_BLOCK_NAME) || (range2->type == XML_REGEXP_BLOCK_NAME)) { if (range1->type == range2->type) { ret = xmlStrEqual(range1->blockName, range2->blockName); } else { /* * comparing a block range with anything else is way * too costly, and maintaining the table is like too much * memory too, so let's force the automata to save state * here. */ return(1); } } else if ((range1->type < XML_REGEXP_LETTER) || (range2->type < XML_REGEXP_LETTER)) { if ((range1->type == XML_REGEXP_ANYSPACE) && (range2->type == XML_REGEXP_NOTSPACE)) ret = 0; else if ((range1->type == XML_REGEXP_INITNAME) && (range2->type == XML_REGEXP_NOTINITNAME)) ret = 0; else if ((range1->type == XML_REGEXP_NAMECHAR) && (range2->type == XML_REGEXP_NOTNAMECHAR)) ret = 0; else if ((range1->type == XML_REGEXP_DECIMAL) && (range2->type == XML_REGEXP_NOTDECIMAL)) ret = 0; else if ((range1->type == XML_REGEXP_REALCHAR) && (range2->type == XML_REGEXP_NOTREALCHAR)) ret = 0; else { /* same thing to limit complexity */ return(1); } } else { ret = 0; /* range1->type < range2->type here */ switch (range1->type) { case XML_REGEXP_LETTER: /* all disjoint except in the subgroups */ if ((range2->type == XML_REGEXP_LETTER_UPPERCASE) || (range2->type == XML_REGEXP_LETTER_LOWERCASE) || (range2->type == XML_REGEXP_LETTER_TITLECASE) || (range2->type == XML_REGEXP_LETTER_MODIFIER) || (range2->type == XML_REGEXP_LETTER_OTHERS)) ret = 1; break; case XML_REGEXP_MARK: if ((range2->type == XML_REGEXP_MARK_NONSPACING) || (range2->type == XML_REGEXP_MARK_SPACECOMBINING) || (range2->type == XML_REGEXP_MARK_ENCLOSING)) ret = 1; break; case XML_REGEXP_NUMBER: if ((range2->type == XML_REGEXP_NUMBER_DECIMAL) || (range2->type == XML_REGEXP_NUMBER_LETTER) || (range2->type == XML_REGEXP_NUMBER_OTHERS)) ret = 1; break; case XML_REGEXP_PUNCT: if ((range2->type == XML_REGEXP_PUNCT_CONNECTOR) || (range2->type == XML_REGEXP_PUNCT_DASH) || (range2->type == XML_REGEXP_PUNCT_OPEN) || (range2->type == XML_REGEXP_PUNCT_CLOSE) || (range2->type == XML_REGEXP_PUNCT_INITQUOTE) || (range2->type == XML_REGEXP_PUNCT_FINQUOTE) || (range2->type == XML_REGEXP_PUNCT_OTHERS)) ret = 1; break; case XML_REGEXP_SEPAR: if ((range2->type == XML_REGEXP_SEPAR_SPACE) || (range2->type == XML_REGEXP_SEPAR_LINE) || (range2->type == XML_REGEXP_SEPAR_PARA)) ret = 1; break; case XML_REGEXP_SYMBOL: if ((range2->type == XML_REGEXP_SYMBOL_MATH) || (range2->type == XML_REGEXP_SYMBOL_CURRENCY) || (range2->type == XML_REGEXP_SYMBOL_MODIFIER) || (range2->type == XML_REGEXP_SYMBOL_OTHERS)) ret = 1; break; case XML_REGEXP_OTHER: if ((range2->type == XML_REGEXP_OTHER_CONTROL) || (range2->type == XML_REGEXP_OTHER_FORMAT) || (range2->type == XML_REGEXP_OTHER_PRIVATE)) ret = 1; break; default: if ((range2->type >= XML_REGEXP_LETTER) && (range2->type < XML_REGEXP_BLOCK_NAME)) ret = 0; else { /* safety net ! */ return(1); } } } if (((range1->neg == 0) && (range2->neg != 0)) || ((range1->neg != 0) && (range2->neg == 0))) ret = !ret; return(ret);}
/** * xmlFACompareAtomTypes: * @type1: an atom type * @type2: an atom type * * Compares two atoms type to check whether they intersect in some ways, * this is used by xmlFACompareAtoms only * * Returns 1 if they may intersect and 0 otherwise */static intxmlFACompareAtomTypes(xmlRegAtomType type1, xmlRegAtomType type2) { if ((type1 == XML_REGEXP_EPSILON) || (type1 == XML_REGEXP_CHARVAL) || (type1 == XML_REGEXP_RANGES) || (type1 == XML_REGEXP_SUBREG) || (type1 == XML_REGEXP_STRING) || (type1 == XML_REGEXP_ANYCHAR)) return(1); if ((type2 == XML_REGEXP_EPSILON) || (type2 == XML_REGEXP_CHARVAL) || (type2 == XML_REGEXP_RANGES) || (type2 == XML_REGEXP_SUBREG) || (type2 == XML_REGEXP_STRING) || (type2 == XML_REGEXP_ANYCHAR)) return(1);
if (type1 == type2) return(1);
/* simplify subsequent compares by making sure type1 < type2 */ if (type1 > type2) { xmlRegAtomType tmp = type1; type1 = type2; type2 = tmp; } switch (type1) { case XML_REGEXP_ANYSPACE: /* \s */ /* can't be a letter, number, mark, punctuation, symbol */ if ((type2 == XML_REGEXP_NOTSPACE) || ((type2 >= XML_REGEXP_LETTER) && (type2 <= XML_REGEXP_LETTER_OTHERS)) || ((type2 >= XML_REGEXP_NUMBER) && (type2 <= XML_REGEXP_NUMBER_OTHERS)) || ((type2 >= XML_REGEXP_MARK) && (type2 <= XML_REGEXP_MARK_ENCLOSING)) || ((type2 >= XML_REGEXP_PUNCT) && (type2 <= XML_REGEXP_PUNCT_OTHERS)) || ((type2 >= XML_REGEXP_SYMBOL) && (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ) return(0); break; case XML_REGEXP_NOTSPACE: /* \S */ break; case XML_REGEXP_INITNAME: /* \l */ /* can't be a number, mark, separator, punctuation, symbol or other */ if ((type2 == XML_REGEXP_NOTINITNAME) || ((type2 >= XML_REGEXP_NUMBER) && (type2 <= XML_REGEXP_NUMBER_OTHERS)) || ((type2 >= XML_REGEXP_MARK) && (type2 <= XML_REGEXP_MARK_ENCLOSING)) || ((type2 >= XML_REGEXP_SEPAR) && (type2 <= XML_REGEXP_SEPAR_PARA)) || ((type2 >= XML_REGEXP_PUNCT) && (type2 <= XML_REGEXP_PUNCT_OTHERS)) || ((type2 >= XML_REGEXP_SYMBOL) && (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || ((type2 >= XML_REGEXP_OTHER) && (type2 <= XML_REGEXP_OTHER_NA)) ) return(0); break; case XML_REGEXP_NOTINITNAME: /* \L */ break; case XML_REGEXP_NAMECHAR: /* \c */ /* can't be a mark, separator, punctuation, symbol or other */ if ((type2 == XML_REGEXP_NOTNAMECHAR) || ((type2 >= XML_REGEXP_MARK) && (type2 <= XML_REGEXP_MARK_ENCLOSING)) || ((type2 >= XML_REGEXP_PUNCT) && (type2 <= XML_REGEXP_PUNCT_OTHERS)) || ((type2 >= XML_REGEXP_SEPAR) && (type2 <= XML_REGEXP_SEPAR_PARA)) || ((type2 >= XML_REGEXP_SYMBOL) && (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || ((type2 >= XML_REGEXP_OTHER) && (type2 <= XML_REGEXP_OTHER_NA)) ) return(0); break; case XML_REGEXP_NOTNAMECHAR: /* \C */ break; case XML_REGEXP_DECIMAL: /* \d */ /* can't be a letter, mark, separator, punctuation, symbol or other */ if ((type2 == XML_REGEXP_NOTDECIMAL) || (type2 == XML_REGEXP_REALCHAR) || ((type2 >= XML_REGEXP_LETTER) && (type2 <= XML_REGEXP_LETTER_OTHERS)) || ((type2 >= XML_REGEXP_MARK) && (type2 <= XML_REGEXP_MARK_ENCLOSING)) || ((type2 >= XML_REGEXP_PUNCT) && (type2 <= XML_REGEXP_PUNCT_OTHERS)) || ((type2 >= XML_REGEXP_SEPAR) && (type2 <= XML_REGEXP_SEPAR_PARA)) || ((type2 >= XML_REGEXP_SYMBOL) && (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || ((type2 >= XML_REGEXP_OTHER) && (type2 <= XML_REGEXP_OTHER_NA)) )return(0); break; case XML_REGEXP_NOTDECIMAL: /* \D */ break; case XML_REGEXP_REALCHAR: /* \w */ /* can't be a mark, separator, punctuation, symbol or other */ if ((type2 == XML_REGEXP_NOTDECIMAL) || ((type2 >= XML_REGEXP_MARK) && (type2 <= XML_REGEXP_MARK_ENCLOSING)) || ((type2 >= XML_REGEXP_PUNCT) && (type2 <= XML_REGEXP_PUNCT_OTHERS)) || ((type2 >= XML_REGEXP_SEPAR) && (type2 <= XML_REGEXP_SEPAR_PARA)) || ((type2 >= XML_REGEXP_SYMBOL) && (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || ((type2 >= XML_REGEXP_OTHER) && (type2 <= XML_REGEXP_OTHER_NA)) )return(0); break; case XML_REGEXP_NOTREALCHAR: /* \W */ break; /* * at that point we know both type 1 and type2 are from * character categories are ordered and are different, * it becomes simple because this is a partition */ case XML_REGEXP_LETTER: if (type2 <= XML_REGEXP_LETTER_OTHERS) return(1); return(0); case XML_REGEXP_LETTER_UPPERCASE: case XML_REGEXP_LETTER_LOWERCASE: case XML_REGEXP_LETTER_TITLECASE: case XML_REGEXP_LETTER_MODIFIER: case XML_REGEXP_LETTER_OTHERS: return(0); case XML_REGEXP_MARK: if (type2 <= XML_REGEXP_MARK_ENCLOSING) return(1); return(0); case XML_REGEXP_MARK_NONSPACING: case XML_REGEXP_MARK_SPACECOMBINING: case XML_REGEXP_MARK_ENCLOSING: return(0); case XML_REGEXP_NUMBER: if (type2 <= XML_REGEXP_NUMBER_OTHERS) return(1); return(0); case XML_REGEXP_NUMBER_DECIMAL: case XML_REGEXP_NUMBER_LETTER: case XML_REGEXP_NUMBER_OTHERS: return(0); case XML_REGEXP_PUNCT: if (type2 <= XML_REGEXP_PUNCT_OTHERS) return(1); return(0); case XML_REGEXP_PUNCT_CONNECTOR: case XML_REGEXP_PUNCT_DASH: case XML_REGEXP_PUNCT_OPEN: case XML_REGEXP_PUNCT_CLOSE: case XML_REGEXP_PUNCT_INITQUOTE: case XML_REGEXP_PUNCT_FINQUOTE: case XML_REGEXP_PUNCT_OTHERS: return(0); case XML_REGEXP_SEPAR: if (type2 <= XML_REGEXP_SEPAR_PARA) return(1); return(0); case XML_REGEXP_SEPAR_SPACE: case XML_REGEXP_SEPAR_LINE: case XML_REGEXP_SEPAR_PARA: return(0); case XML_REGEXP_SYMBOL: if (type2 <= XML_REGEXP_SYMBOL_OTHERS) return(1); return(0); case XML_REGEXP_SYMBOL_MATH: case XML_REGEXP_SYMBOL_CURRENCY: case XML_REGEXP_SYMBOL_MODIFIER: case XML_REGEXP_SYMBOL_OTHERS: return(0); case XML_REGEXP_OTHER: if (type2 <= XML_REGEXP_OTHER_NA) return(1); return(0); case XML_REGEXP_OTHER_CONTROL: case XML_REGEXP_OTHER_FORMAT: case XML_REGEXP_OTHER_PRIVATE: case XML_REGEXP_OTHER_NA: return(0); default: break; } return(1);}
/** * xmlFAEqualAtoms: * @atom1: an atom * @atom2: an atom * @deep: if not set only compare string pointers * * Compares two atoms to check whether they are the same exactly * this is used to remove equivalent transitions * * Returns 1 if same and 0 otherwise */static intxmlFAEqualAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) { int ret = 0;
if (atom1 == atom2) return(1); if ((atom1 == NULL) || (atom2 == NULL)) return(0);
if (atom1->type != atom2->type) return(0); switch (atom1->type) { case XML_REGEXP_EPSILON: ret = 0; break; case XML_REGEXP_STRING: if (!deep) ret = (atom1->valuep == atom2->valuep); else ret = xmlStrEqual((xmlChar *)atom1->valuep, (xmlChar *)atom2->valuep); break; case XML_REGEXP_CHARVAL: ret = (atom1->codepoint == atom2->codepoint); break; case XML_REGEXP_RANGES: /* too hard to do in the general case */ ret = 0; default: break; } return(ret);}
/** * xmlFACompareAtoms: * @atom1: an atom * @atom2: an atom * @deep: if not set only compare string pointers * * Compares two atoms to check whether they intersect in some ways, * this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only * * Returns 1 if yes and 0 otherwise */static intxmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) { int ret = 1;
if (atom1 == atom2) return(1); if ((atom1 == NULL) || (atom2 == NULL)) return(0);
if ((atom1->type == XML_REGEXP_ANYCHAR) || (atom2->type == XML_REGEXP_ANYCHAR)) return(1);
if (atom1->type > atom2->type) { xmlRegAtomPtr tmp; tmp = atom1; atom1 = atom2; atom2 = tmp; } if (atom1->type != atom2->type) { ret = xmlFACompareAtomTypes(atom1->type, atom2->type); /* if they can't intersect at the type level break now */ if (ret == 0) return(0); } switch (atom1->type) { case XML_REGEXP_STRING: if (!deep) ret = (atom1->valuep != atom2->valuep); else { xmlChar *val1 = (xmlChar *)atom1->valuep; xmlChar *val2 = (xmlChar *)atom2->valuep; int compound1 = (xmlStrchr(val1, '|') != NULL); int compound2 = (xmlStrchr(val2, '|') != NULL);
/* Ignore negative match flag for ##other namespaces */ if (compound1 != compound2) return(0);
ret = xmlRegStrEqualWildcard(val1, val2); } break; case XML_REGEXP_EPSILON: goto not_determinist; case XML_REGEXP_CHARVAL: if (atom2->type == XML_REGEXP_CHARVAL) { ret = (atom1->codepoint == atom2->codepoint); } else { ret = xmlRegCheckCharacter(atom2, atom1->codepoint); if (ret < 0) ret = 1; } break; case XML_REGEXP_RANGES: if (atom2->type == XML_REGEXP_RANGES) { int i, j, res; xmlRegRangePtr r1, r2;
/* * need to check that none of the ranges eventually matches */ for (i = 0;i < atom1->nbRanges;i++) { for (j = 0;j < atom2->nbRanges;j++) { r1 = atom1->ranges[i]; r2 = atom2->ranges[j]; res = xmlFACompareRanges(r1, r2); if (res == 1) { ret = 1; goto done; } } } ret = 0; } break; default: goto not_determinist; }done: if (atom1->neg != atom2->neg) { ret = !ret; } if (ret == 0) return(0);not_determinist: return(1);}
/** * xmlFARecurseDeterminism: * @ctxt: a regexp parser context * * Check whether the associated regexp is determinist, * should be called after xmlFAEliminateEpsilonTransitions() * */static intxmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state, int fromnr, int tonr, xmlRegAtomPtr atom) { int ret = 1; int res; int transnr, nbTrans; xmlRegTransPtr t1; int deep = 1;
if (state == NULL) return(ret); if (state->markd == XML_REGEXP_MARK_VISITED) return(ret);
if (ctxt->flags & AM_AUTOMATA_RNG) deep = 0;
/* * don't recurse on transitions potentially added in the course of * the elimination. */ nbTrans = state->nbTrans; for (transnr = 0;transnr < nbTrans;transnr++) { t1 = &(state->trans[transnr]); /* * check transitions conflicting with the one looked at */ if ((t1->to < 0) || (t1->to == fromnr)) continue; if (t1->atom == NULL) { state->markd = XML_REGEXP_MARK_VISITED; res = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to], fromnr, tonr, atom); if (res == 0) { ret = 0; /* t1->nd = 1; */ } continue; } if (xmlFACompareAtoms(t1->atom, atom, deep)) { /* Treat equal transitions as deterministic. */ if ((t1->to != tonr) || (!xmlFAEqualAtoms(t1->atom, atom, deep))) ret = 0; /* mark the transition as non-deterministic */ t1->nd = 1; } } return(ret);}
/** * xmlFAFinishRecurseDeterminism: * @ctxt: a regexp parser context * * Reset flags after checking determinism. */static voidxmlFAFinishRecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) { int transnr, nbTrans;
if (state == NULL) return; if (state->markd != XML_REGEXP_MARK_VISITED) return; state->markd = 0;
nbTrans = state->nbTrans; for (transnr = 0; transnr < nbTrans; transnr++) { xmlRegTransPtr t1 = &state->trans[transnr]; if ((t1->atom == NULL) && (t1->to >= 0)) xmlFAFinishRecurseDeterminism(ctxt, ctxt->states[t1->to]); }}
/** * xmlFAComputesDeterminism: * @ctxt: a regexp parser context * * Check whether the associated regexp is determinist, * should be called after xmlFAEliminateEpsilonTransitions() * */static intxmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) { int statenr, transnr; xmlRegStatePtr state; xmlRegTransPtr t1, t2, last; int i; int ret = 1; int deep = 1;
if (ctxt->determinist != -1) return(ctxt->determinist);
if (ctxt->flags & AM_AUTOMATA_RNG) deep = 0;
/* * First cleanup the automata removing cancelled transitions */ for (statenr = 0;statenr < ctxt->nbStates;statenr++) { state = ctxt->states[statenr]; if (state == NULL) continue; if (state->nbTrans < 2) continue; for (transnr = 0;transnr < state->nbTrans;transnr++) { t1 = &(state->trans[transnr]); /* * Determinism checks in case of counted or all transitions * will have to be handled separately */ if (t1->atom == NULL) { /* t1->nd = 1; */ continue; } if (t1->to < 0) /* eliminated */ continue; for (i = 0;i < transnr;i++) { t2 = &(state->trans[i]); if (t2->to < 0) /* eliminated */ continue; if (t2->atom != NULL) { if (t1->to == t2->to) { /* * Here we use deep because we want to keep the * transitions which indicate a conflict */ if (xmlFAEqualAtoms(t1->atom, t2->atom, deep) && (t1->counter == t2->counter) && (t1->count == t2->count)) t2->to = -1; /* eliminated */ } } } } }
/* * Check for all states that there aren't 2 transitions * with the same atom and a different target. */ for (statenr = 0;statenr < ctxt->nbStates;statenr++) { state = ctxt->states[statenr]; if (state == NULL) continue; if (state->nbTrans < 2) continue; last = NULL; for (transnr = 0;transnr < state->nbTrans;transnr++) { t1 = &(state->trans[transnr]); /* * Determinism checks in case of counted or all transitions * will have to be handled separately */ if (t1->atom == NULL) { continue; } if (t1->to < 0) /* eliminated */ continue; for (i = 0;i < transnr;i++) { t2 = &(state->trans[i]); if (t2->to < 0) /* eliminated */ continue; if (t2->atom != NULL) { /* * But here we don't use deep because we want to * find transitions which indicate a conflict */ if (xmlFACompareAtoms(t1->atom, t2->atom, 1)) { /* * Treat equal counter transitions that couldn't be * eliminated as deterministic. */ if ((t1->to != t2->to) || (t1->counter == t2->counter) || (!xmlFAEqualAtoms(t1->atom, t2->atom, deep))) ret = 0; /* mark the transitions as non-deterministic ones */ t1->nd = 1; t2->nd = 1; last = t1; } } else { int res;
/* * do the closure in case of remaining specific * epsilon transitions like choices or all */ res = xmlFARecurseDeterminism(ctxt, ctxt->states[t2->to], statenr, t1->to, t1->atom); xmlFAFinishRecurseDeterminism(ctxt, ctxt->states[t2->to]); /* don't shortcut the computation so all non deterministic transition get marked down if (ret == 0) return(0); */ if (res == 0) { t1->nd = 1; /* t2->nd = 1; */ last = t1; ret = 0; } } } /* don't shortcut the computation so all non deterministic transition get marked down if (ret == 0) break; */ }
/* * mark specifically the last non-deterministic transition * from a state since there is no need to set-up rollback * from it */ if (last != NULL) { last->nd = 2; }
/* don't shortcut the computation so all non deterministic transition get marked down if (ret == 0) break; */ }
ctxt->determinist = ret; return(ret);}
/************************************************************************ * * * Routines to check input against transition atoms * * * ************************************************************************/
static intxmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg, int start, int end, const xmlChar *blockName) { int ret = 0;
switch (type) { case XML_REGEXP_STRING: case XML_REGEXP_SUBREG: case XML_REGEXP_RANGES: case XML_REGEXP_EPSILON: return(-1); case XML_REGEXP_ANYCHAR: ret = ((codepoint != '\n') && (codepoint != '\r')); break; case XML_REGEXP_CHARVAL: ret = ((codepoint >= start) && (codepoint <= end)); break; case XML_REGEXP_NOTSPACE: neg = !neg; /* Falls through. */ case XML_REGEXP_ANYSPACE: ret = ((codepoint == '\n') || (codepoint == '\r') || (codepoint == '\t') || (codepoint == ' ')); break; case XML_REGEXP_NOTINITNAME: neg = !neg; /* Falls through. */ case XML_REGEXP_INITNAME: ret = (IS_LETTER(codepoint) || (codepoint == '_') || (codepoint == ':')); break; case XML_REGEXP_NOTNAMECHAR: neg = !neg; /* Falls through. */ case XML_REGEXP_NAMECHAR: ret = (IS_LETTER(codepoint) || IS_DIGIT(codepoint) || (codepoint == '.') || (codepoint == '-') || (codepoint == '_') || (codepoint == ':') || IS_COMBINING(codepoint) || IS_EXTENDER(codepoint)); break; case XML_REGEXP_NOTDECIMAL: neg = !neg; /* Falls through. */ case XML_REGEXP_DECIMAL: ret = xmlUCSIsCatNd(codepoint); break; case XML_REGEXP_REALCHAR: neg = !neg; /* Falls through. */ case XML_REGEXP_NOTREALCHAR: ret = xmlUCSIsCatP(codepoint); if (ret == 0) ret = xmlUCSIsCatZ(codepoint); if (ret == 0) ret = xmlUCSIsCatC(codepoint); break; case XML_REGEXP_LETTER: ret = xmlUCSIsCatL(codepoint); break; case XML_REGEXP_LETTER_UPPERCASE: ret = xmlUCSIsCatLu(codepoint); break; case XML_REGEXP_LETTER_LOWERCASE: ret = xmlUCSIsCatLl(codepoint); break; case XML_REGEXP_LETTER_TITLECASE: ret = xmlUCSIsCatLt(codepoint); break; case XML_REGEXP_LETTER_MODIFIER: ret = xmlUCSIsCatLm(codepoint); break; case XML_REGEXP_LETTER_OTHERS: ret = xmlUCSIsCatLo(codepoint); break; case XML_REGEXP_MARK: ret = xmlUCSIsCatM(codepoint); break; case XML_REGEXP_MARK_NONSPACING: ret = xmlUCSIsCatMn(codepoint); break; case XML_REGEXP_MARK_SPACECOMBINING: ret = xmlUCSIsCatMc(codepoint); break; case XML_REGEXP_MARK_ENCLOSING: ret = xmlUCSIsCatMe(codepoint); break; case XML_REGEXP_NUMBER: ret = xmlUCSIsCatN(codepoint); break; case XML_REGEXP_NUMBER_DECIMAL: ret = xmlUCSIsCatNd(codepoint); break; case XML_REGEXP_NUMBER_LETTER: ret = xmlUCSIsCatNl(codepoint); break; case XML_REGEXP_NUMBER_OTHERS: ret = xmlUCSIsCatNo(codepoint); break; case XML_REGEXP_PUNCT: ret = xmlUCSIsCatP(codepoint); break; case XML_REGEXP_PUNCT_CONNECTOR: ret = xmlUCSIsCatPc(codepoint); break; case XML_REGEXP_PUNCT_DASH: ret = xmlUCSIsCatPd(codepoint); break; case XML_REGEXP_PUNCT_OPEN: ret = xmlUCSIsCatPs(codepoint); break; case XML_REGEXP_PUNCT_CLOSE: ret = xmlUCSIsCatPe(codepoint); break; case XML_REGEXP_PUNCT_INITQUOTE: ret = xmlUCSIsCatPi(codepoint); break; case XML_REGEXP_PUNCT_FINQUOTE: ret = xmlUCSIsCatPf(codepoint); break; case XML_REGEXP_PUNCT_OTHERS: ret = xmlUCSIsCatPo(codepoint); break; case XML_REGEXP_SEPAR: ret = xmlUCSIsCatZ(codepoint); break; case XML_REGEXP_SEPAR_SPACE: ret = xmlUCSIsCatZs(codepoint); break; case XML_REGEXP_SEPAR_LINE: ret = xmlUCSIsCatZl(codepoint); break; case XML_REGEXP_SEPAR_PARA: ret = xmlUCSIsCatZp(codepoint); break; case XML_REGEXP_SYMBOL: ret = xmlUCSIsCatS(codepoint); break; case XML_REGEXP_SYMBOL_MATH: ret = xmlUCSIsCatSm(codepoint); break; case XML_REGEXP_SYMBOL_CURRENCY: ret = xmlUCSIsCatSc(codepoint); break; case XML_REGEXP_SYMBOL_MODIFIER: ret = xmlUCSIsCatSk(codepoint); break; case XML_REGEXP_SYMBOL_OTHERS: ret = xmlUCSIsCatSo(codepoint); break; case XML_REGEXP_OTHER: ret = xmlUCSIsCatC(codepoint); break; case XML_REGEXP_OTHER_CONTROL: ret = xmlUCSIsCatCc(codepoint); break; case XML_REGEXP_OTHER_FORMAT: ret = xmlUCSIsCatCf(codepoint); break; case XML_REGEXP_OTHER_PRIVATE: ret = xmlUCSIsCatCo(codepoint); break; case XML_REGEXP_OTHER_NA: /* ret = xmlUCSIsCatCn(codepoint); */ /* Seems it doesn't exist anymore in recent Unicode releases */ ret = 0; break; case XML_REGEXP_BLOCK_NAME: ret = xmlUCSIsBlock(codepoint, (const char *) blockName); break; } if (neg) return(!ret); return(ret);}
static intxmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) { int i, ret = 0; xmlRegRangePtr range;
if ((atom == NULL) || (!IS_CHAR(codepoint))) return(-1);
switch (atom->type) { case XML_REGEXP_SUBREG: case XML_REGEXP_EPSILON: return(-1); case XML_REGEXP_CHARVAL: return(codepoint == atom->codepoint); case XML_REGEXP_RANGES: { int accept = 0;
for (i = 0;i < atom->nbRanges;i++) { range = atom->ranges[i]; if (range->neg == 2) { ret = xmlRegCheckCharacterRange(range->type, codepoint, 0, range->start, range->end, range->blockName); if (ret != 0) return(0); /* excluded char */ } else if (range->neg) { ret = xmlRegCheckCharacterRange(range->type, codepoint, 0, range->start, range->end, range->blockName); if (ret == 0) accept = 1; else return(0); } else { ret = xmlRegCheckCharacterRange(range->type, codepoint, 0, range->start, range->end, range->blockName); if (ret != 0) accept = 1; /* might still be excluded */ } } return(accept); } case XML_REGEXP_STRING: printf("TODO: XML_REGEXP_STRING\n"); return(-1); case XML_REGEXP_ANYCHAR: case XML_REGEXP_ANYSPACE: case XML_REGEXP_NOTSPACE: case XML_REGEXP_INITNAME: case XML_REGEXP_NOTINITNAME: case XML_REGEXP_NAMECHAR: case XML_REGEXP_NOTNAMECHAR: case XML_REGEXP_DECIMAL: case XML_REGEXP_NOTDECIMAL: case XML_REGEXP_REALCHAR: case XML_REGEXP_NOTREALCHAR: case XML_REGEXP_LETTER: case XML_REGEXP_LETTER_UPPERCASE: case XML_REGEXP_LETTER_LOWERCASE: case XML_REGEXP_LETTER_TITLECASE: case XML_REGEXP_LETTER_MODIFIER: case XML_REGEXP_LETTER_OTHERS: case XML_REGEXP_MARK: case XML_REGEXP_MARK_NONSPACING: case XML_REGEXP_MARK_SPACECOMBINING: case XML_REGEXP_MARK_ENCLOSING: case XML_REGEXP_NUMBER: case XML_REGEXP_NUMBER_DECIMAL: case XML_REGEXP_NUMBER_LETTER: case XML_REGEXP_NUMBER_OTHERS: case XML_REGEXP_PUNCT: case XML_REGEXP_PUNCT_CONNECTOR: case XML_REGEXP_PUNCT_DASH: case XML_REGEXP_PUNCT_OPEN: case XML_REGEXP_PUNCT_CLOSE: case XML_REGEXP_PUNCT_INITQUOTE: case XML_REGEXP_PUNCT_FINQUOTE: case XML_REGEXP_PUNCT_OTHERS: case XML_REGEXP_SEPAR: case XML_REGEXP_SEPAR_SPACE: case XML_REGEXP_SEPAR_LINE: case XML_REGEXP_SEPAR_PARA: case XML_REGEXP_SYMBOL: case XML_REGEXP_SYMBOL_MATH: case XML_REGEXP_SYMBOL_CURRENCY: case XML_REGEXP_SYMBOL_MODIFIER: case XML_REGEXP_SYMBOL_OTHERS: case XML_REGEXP_OTHER: case XML_REGEXP_OTHER_CONTROL: case XML_REGEXP_OTHER_FORMAT: case XML_REGEXP_OTHER_PRIVATE: case XML_REGEXP_OTHER_NA: case XML_REGEXP_BLOCK_NAME: ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0, (const xmlChar *)atom->valuep); if (atom->neg) ret = !ret; break; } return(ret);}
/************************************************************************ * * * Saving and restoring state of an execution context * * * ************************************************************************/
static voidxmlFARegExecSave(xmlRegExecCtxtPtr exec) {#ifdef MAX_PUSH if (exec->nbPush > MAX_PUSH) { exec->status = XML_REGEXP_INTERNAL_LIMIT; return; } exec->nbPush++;#endif
if (exec->maxRollbacks == 0) { exec->maxRollbacks = 4; exec->rollbacks = (xmlRegExecRollback *) xmlMalloc(exec->maxRollbacks * sizeof(xmlRegExecRollback)); if (exec->rollbacks == NULL) { xmlRegexpErrMemory(NULL, "saving regexp"); exec->maxRollbacks = 0; exec->status = XML_REGEXP_OUT_OF_MEMORY; return; } memset(exec->rollbacks, 0, exec->maxRollbacks * sizeof(xmlRegExecRollback)); } else if (exec->nbRollbacks >= exec->maxRollbacks) { xmlRegExecRollback *tmp; int len = exec->maxRollbacks;
exec->maxRollbacks *= 2; tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks, exec->maxRollbacks * sizeof(xmlRegExecRollback)); if (tmp == NULL) { xmlRegexpErrMemory(NULL, "saving regexp"); exec->maxRollbacks /= 2; exec->status = XML_REGEXP_OUT_OF_MEMORY; return; } exec->rollbacks = tmp; tmp = &exec->rollbacks[len]; memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback)); } exec->rollbacks[exec->nbRollbacks].state = exec->state; exec->rollbacks[exec->nbRollbacks].index = exec->index; exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1; if (exec->comp->nbCounters > 0) { if (exec->rollbacks[exec->nbRollbacks].counts == NULL) { exec->rollbacks[exec->nbRollbacks].counts = (int *) xmlMalloc(exec->comp->nbCounters * sizeof(int)); if (exec->rollbacks[exec->nbRollbacks].counts == NULL) { xmlRegexpErrMemory(NULL, "saving regexp"); exec->status = XML_REGEXP_OUT_OF_MEMORY; return; } } memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts, exec->comp->nbCounters * sizeof(int)); } exec->nbRollbacks++;}
static voidxmlFARegExecRollBack(xmlRegExecCtxtPtr exec) { if (exec->status != XML_REGEXP_OK) return; if (exec->nbRollbacks <= 0) { exec->status = XML_REGEXP_NOT_FOUND; return; } exec->nbRollbacks--; exec->state = exec->rollbacks[exec->nbRollbacks].state; exec->index = exec->rollbacks[exec->nbRollbacks].index; exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch; if (exec->comp->nbCounters > 0) { if (exec->rollbacks[exec->nbRollbacks].counts == NULL) { fprintf(stderr, "exec save: allocation failed"); exec->status = XML_REGEXP_INTERNAL_ERROR; return; } if (exec->counts) { memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts, exec->comp->nbCounters * sizeof(int)); } }}
/************************************************************************ * * * Verifier, running an input against a compiled regexp * * * ************************************************************************/
static intxmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) { xmlRegExecCtxt execval; xmlRegExecCtxtPtr exec = &execval; int ret, codepoint = 0, len, deter;
exec->inputString = content; exec->index = 0; exec->nbPush = 0; exec->determinist = 1; exec->maxRollbacks = 0; exec->nbRollbacks = 0; exec->rollbacks = NULL; exec->status = XML_REGEXP_OK; exec->comp = comp; exec->state = comp->states[0]; exec->transno = 0; exec->transcount = 0; exec->inputStack = NULL; exec->inputStackMax = 0; if (comp->nbCounters > 0) { exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int)); if (exec->counts == NULL) { xmlRegexpErrMemory(NULL, "running regexp"); return(XML_REGEXP_OUT_OF_MEMORY); } memset(exec->counts, 0, comp->nbCounters * sizeof(int)); } else exec->counts = NULL; while ((exec->status == XML_REGEXP_OK) && (exec->state != NULL) && ((exec->inputString[exec->index] != 0) || ((exec->state != NULL) && (exec->state->type != XML_REGEXP_FINAL_STATE)))) { xmlRegTransPtr trans; xmlRegAtomPtr atom;
/* * If end of input on non-terminal state, rollback, however we may * still have epsilon like transition for counted transitions * on counters, in that case don't break too early. Additionally, * if we are working on a range like "AB{0,2}", where B is not present, * we don't want to break. */ len = 1; if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL)) { /* * if there is a transition, we must check if * atom allows minOccurs of 0 */ if (exec->transno < exec->state->nbTrans) { trans = &exec->state->trans[exec->transno]; if (trans->to >=0) { atom = trans->atom; if (!((atom->min == 0) && (atom->max > 0))) goto rollback; } } else goto rollback; }
exec->transcount = 0; for (;exec->transno < exec->state->nbTrans;exec->transno++) { trans = &exec->state->trans[exec->transno]; if (trans->to < 0) continue; atom = trans->atom; ret = 0; deter = 1; if (trans->count >= 0) { int count; xmlRegCounterPtr counter;
if (exec->counts == NULL) { exec->status = XML_REGEXP_INTERNAL_ERROR; goto error; } /* * A counted transition. */
count = exec->counts[trans->count]; counter = &exec->comp->counters[trans->count]; ret = ((count >= counter->min) && (count <= counter->max)); if ((ret) && (counter->min != counter->max)) deter = 0; } else if (atom == NULL) { fprintf(stderr, "epsilon transition left at runtime\n"); exec->status = XML_REGEXP_INTERNAL_ERROR; break; } else if (exec->inputString[exec->index] != 0) { len = 4; codepoint = xmlGetUTF8Char(&exec->inputString[exec->index], &len); if (codepoint < 0) { exec->status = XML_REGEXP_INVALID_UTF8; goto error; } ret = xmlRegCheckCharacter(atom, codepoint); if ((ret == 1) && (atom->min >= 0) && (atom->max > 0)) { xmlRegStatePtr to = comp->states[trans->to];
/* * this is a multiple input sequence * If there is a counter associated increment it now. * do not increment if the counter is already over the * maximum limit in which case get to next transition */ if (trans->counter >= 0) { xmlRegCounterPtr counter;
if ((exec->counts == NULL) || (exec->comp == NULL) || (exec->comp->counters == NULL)) { exec->status = XML_REGEXP_INTERNAL_ERROR; goto error; } counter = &exec->comp->counters[trans->counter]; if (exec->counts[trans->counter] >= counter->max) continue; /* for loop on transitions */ } /* Save before incrementing */ if (exec->state->nbTrans > exec->transno + 1) { xmlFARegExecSave(exec); if (exec->status != XML_REGEXP_OK) goto error; } if (trans->counter >= 0) { exec->counts[trans->counter]++; } exec->transcount = 1; do { /* * Try to progress as much as possible on the input */ if (exec->transcount == atom->max) { break; } exec->index += len; /* * End of input: stop here */ if (exec->inputString[exec->index] == 0) { exec->index -= len; break; } if (exec->transcount >= atom->min) { int transno = exec->transno; xmlRegStatePtr state = exec->state;
/* * The transition is acceptable save it */ exec->transno = -1; /* trick */ exec->state = to; xmlFARegExecSave(exec); if (exec->status != XML_REGEXP_OK) goto error; exec->transno = transno; exec->state = state; } len = 4; codepoint = xmlGetUTF8Char( &exec->inputString[exec->index], &len); if (codepoint < 0) { exec->status = XML_REGEXP_INVALID_UTF8; goto error; } ret = xmlRegCheckCharacter(atom, codepoint); exec->transcount++; } while (ret == 1); if (exec->transcount < atom->min) ret = 0;
/* * If the last check failed but one transition was found * possible, rollback */ if (ret < 0) ret = 0; if (ret == 0) { goto rollback; } if (trans->counter >= 0) { if (exec->counts == NULL) { exec->status = XML_REGEXP_INTERNAL_ERROR; goto error; } exec->counts[trans->counter]--; } } else if ((ret == 0) && (atom->min == 0) && (atom->max > 0)) { /* * we don't match on the codepoint, but minOccurs of 0 * says that's ok. Setting len to 0 inhibits stepping * over the codepoint. */ exec->transcount = 1; len = 0; ret = 1; } } else if ((atom->min == 0) && (atom->max > 0)) { /* another spot to match when minOccurs is 0 */ exec->transcount = 1; len = 0; ret = 1; } if (ret == 1) { if ((trans->nd == 1) || ((trans->count >= 0) && (deter == 0) && (exec->state->nbTrans > exec->transno + 1))) { xmlFARegExecSave(exec); if (exec->status != XML_REGEXP_OK) goto error; } if (trans->counter >= 0) { xmlRegCounterPtr counter;
/* make sure we don't go over the counter maximum value */ if ((exec->counts == NULL) || (exec->comp == NULL) || (exec->comp->counters == NULL)) { exec->status = XML_REGEXP_INTERNAL_ERROR; goto error; } counter = &exec->comp->counters[trans->counter]; if (exec->counts[trans->counter] >= counter->max) continue; /* for loop on transitions */ exec->counts[trans->counter]++; } if ((trans->count >= 0) && (trans->count < REGEXP_ALL_COUNTER)) { if (exec->counts == NULL) { exec->status = XML_REGEXP_INTERNAL_ERROR; goto error; } exec->counts[trans->count] = 0; } exec->state = comp->states[trans->to]; exec->transno = 0; if (trans->atom != NULL) { exec->index += len; } goto progress; } else if (ret < 0) { exec->status = XML_REGEXP_INTERNAL_ERROR; break; } } if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {rollback: /* * Failed to find a way out */ exec->determinist = 0; xmlFARegExecRollBack(exec); }progress: continue; }error: if (exec->rollbacks != NULL) { if (exec->counts != NULL) { int i;
for (i = 0;i < exec->maxRollbacks;i++) if (exec->rollbacks[i].counts != NULL) xmlFree(exec->rollbacks[i].counts); } xmlFree(exec->rollbacks); } if (exec->state == NULL) return(XML_REGEXP_INTERNAL_ERROR); if (exec->counts != NULL) xmlFree(exec->counts); if (exec->status == XML_REGEXP_OK) return(1); if (exec->status == XML_REGEXP_NOT_FOUND) return(0); return(exec->status);}
/************************************************************************ * * * Progressive interface to the verifier one atom at a time * * * ************************************************************************/
/** * xmlRegNewExecCtxt: * @comp: a precompiled regular expression * @callback: a callback function used for handling progresses in the * automata matching phase * @data: the context data associated to the callback in this context * * Build a context used for progressive evaluation of a regexp. * * Returns the new context */xmlRegExecCtxtPtrxmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) { xmlRegExecCtxtPtr exec;
if (comp == NULL) return(NULL); if ((comp->compact == NULL) && (comp->states == NULL)) return(NULL); exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt)); if (exec == NULL) { xmlRegexpErrMemory(NULL, "creating execution context"); return(NULL); } memset(exec, 0, sizeof(xmlRegExecCtxt)); exec->inputString = NULL; exec->index = 0; exec->determinist = 1; exec->maxRollbacks = 0; exec->nbRollbacks = 0; exec->rollbacks = NULL; exec->status = XML_REGEXP_OK; exec->comp = comp; if (comp->compact == NULL) exec->state = comp->states[0]; exec->transno = 0; exec->transcount = 0; exec->callback = callback; exec->data = data; if (comp->nbCounters > 0) { /* * For error handling, exec->counts is allocated twice the size * the second half is used to store the data in case of rollback */ exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int) * 2); if (exec->counts == NULL) { xmlRegexpErrMemory(NULL, "creating execution context"); xmlFree(exec); return(NULL); } memset(exec->counts, 0, comp->nbCounters * sizeof(int) * 2); exec->errCounts = &exec->counts[comp->nbCounters]; } else { exec->counts = NULL; exec->errCounts = NULL; } exec->inputStackMax = 0; exec->inputStackNr = 0; exec->inputStack = NULL; exec->errStateNo = -1; exec->errString = NULL; exec->nbPush = 0; return(exec);}
/** * xmlRegFreeExecCtxt: * @exec: a regular expression evaluation context * * Free the structures associated to a regular expression evaluation context. */voidxmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) { if (exec == NULL) return;
if (exec->rollbacks != NULL) { if (exec->counts != NULL) { int i;
for (i = 0;i < exec->maxRollbacks;i++) if (exec->rollbacks[i].counts != NULL) xmlFree(exec->rollbacks[i].counts); } xmlFree(exec->rollbacks); } if (exec->counts != NULL) xmlFree(exec->counts); if (exec->inputStack != NULL) { int i;
for (i = 0;i < exec->inputStackNr;i++) { if (exec->inputStack[i].value != NULL) xmlFree(exec->inputStack[i].value); } xmlFree(exec->inputStack); } if (exec->errString != NULL) xmlFree(exec->errString); xmlFree(exec);}
static voidxmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value, void *data) { if (exec->inputStackMax == 0) { exec->inputStackMax = 4; exec->inputStack = (xmlRegInputTokenPtr) xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken)); if (exec->inputStack == NULL) { xmlRegexpErrMemory(NULL, "pushing input string"); exec->inputStackMax = 0; return; } } else if (exec->inputStackNr + 1 >= exec->inputStackMax) { xmlRegInputTokenPtr tmp;
exec->inputStackMax *= 2; tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack, exec->inputStackMax * sizeof(xmlRegInputToken)); if (tmp == NULL) { xmlRegexpErrMemory(NULL, "pushing input string"); exec->inputStackMax /= 2; return; } exec->inputStack = tmp; } exec->inputStack[exec->inputStackNr].value = xmlStrdup(value); exec->inputStack[exec->inputStackNr].data = data; exec->inputStackNr++; exec->inputStack[exec->inputStackNr].value = NULL; exec->inputStack[exec->inputStackNr].data = NULL;}
/** * xmlRegStrEqualWildcard: * @expStr: the string to be evaluated * @valStr: the validation string * * Checks if both strings are equal or have the same content. "*" * can be used as a wildcard in @valStr; "|" is used as a separator of * substrings in both @expStr and @valStr. * * Returns 1 if the comparison is satisfied and the number of substrings * is equal, 0 otherwise. */
static intxmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr) { if (expStr == valStr) return(1); if (expStr == NULL) return(0); if (valStr == NULL) return(0); do { /* * Eval if we have a wildcard for the current item. */ if (*expStr != *valStr) { /* if one of them starts with a wildcard make valStr be it */ if (*valStr == '*') { const xmlChar *tmp;
tmp = valStr; valStr = expStr; expStr = tmp; } if ((*valStr != 0) && (*expStr != 0) && (*expStr++ == '*')) { do { if (*valStr == XML_REG_STRING_SEPARATOR) break; valStr++; } while (*valStr != 0); continue; } else return(0); } expStr++; valStr++; } while (*valStr != 0); if (*expStr != 0) return (0); else return (1);}
/** * xmlRegCompactPushString: * @exec: a regexp execution context * @comp: the precompiled exec with a compact table * @value: a string token input * @data: data associated to the token to reuse in callbacks * * Push one input token in the execution context * * Returns: 1 if the regexp reached a final state, 0 if non-final, and * a negative value in case of error. */static intxmlRegCompactPushString(xmlRegExecCtxtPtr exec, xmlRegexpPtr comp, const xmlChar *value, void *data) { int state = exec->index; int i, target;
if ((comp == NULL) || (comp->compact == NULL) || (comp->stringMap == NULL)) return(-1);
if (value == NULL) { /* * are we at a final state ? */ if (comp->compact[state * (comp->nbstrings + 1)] == XML_REGEXP_FINAL_STATE) return(1); return(0); }
/* * Examine all outside transitions from current state */ for (i = 0;i < comp->nbstrings;i++) { target = comp->compact[state * (comp->nbstrings + 1) + i + 1]; if ((target > 0) && (target <= comp->nbstates)) { target--; /* to avoid 0 */ if (xmlRegStrEqualWildcard(comp->stringMap[i], value)) { exec->index = target; if ((exec->callback != NULL) && (comp->transdata != NULL)) { exec->callback(exec->data, value, comp->transdata[state * comp->nbstrings + i], data); } if (comp->compact[target * (comp->nbstrings + 1)] == XML_REGEXP_SINK_STATE) goto error;
if (comp->compact[target * (comp->nbstrings + 1)] == XML_REGEXP_FINAL_STATE) return(1); return(0); } } } /* * Failed to find an exit transition out from current state for the * current token */error: if (exec->errString != NULL) xmlFree(exec->errString); exec->errString = xmlStrdup(value); exec->errStateNo = state; exec->status = XML_REGEXP_NOT_FOUND; return(XML_REGEXP_NOT_FOUND);}
/** * xmlRegExecPushStringInternal: * @exec: a regexp execution context or NULL to indicate the end * @value: a string token input * @data: data associated to the token to reuse in callbacks * @compound: value was assembled from 2 strings * * Push one input token in the execution context * * Returns: 1 if the regexp reached a final state, 0 if non-final, and * a negative value in case of error. */static intxmlRegExecPushStringInternal(xmlRegExecCtxtPtr exec, const xmlChar *value, void *data, int compound) { xmlRegTransPtr trans; xmlRegAtomPtr atom; int ret; int final = 0; int progress = 1;
if (exec == NULL) return(-1); if (exec->comp == NULL) return(-1); if (exec->status != XML_REGEXP_OK) return(exec->status);
if (exec->comp->compact != NULL) return(xmlRegCompactPushString(exec, exec->comp, value, data));
if (value == NULL) { if (exec->state->type == XML_REGEXP_FINAL_STATE) return(1); final = 1; }
/* * If we have an active rollback stack push the new value there * and get back to where we were left */ if ((value != NULL) && (exec->inputStackNr > 0)) { xmlFARegExecSaveInputString(exec, value, data); value = exec->inputStack[exec->index].value; data = exec->inputStack[exec->index].data; }
while ((exec->status == XML_REGEXP_OK) && ((value != NULL) || ((final == 1) && (exec->state->type != XML_REGEXP_FINAL_STATE)))) {
/* * End of input on non-terminal state, rollback, however we may * still have epsilon like transition for counted transitions * on counters, in that case don't break too early. */ if ((value == NULL) && (exec->counts == NULL)) goto rollback;
exec->transcount = 0; for (;exec->transno < exec->state->nbTrans;exec->transno++) { trans = &exec->state->trans[exec->transno]; if (trans->to < 0) continue; atom = trans->atom; ret = 0; if (trans->count == REGEXP_ALL_LAX_COUNTER) { int i; int count; xmlRegTransPtr t; xmlRegCounterPtr counter;
ret = 0;
/* * Check all counted transitions from the current state */ if ((value == NULL) && (final)) { ret = 1; } else if (value != NULL) { for (i = 0;i < exec->state->nbTrans;i++) { t = &exec->state->trans[i]; if ((t->counter < 0) || (t == trans)) continue; counter = &exec->comp->counters[t->counter]; count = exec->counts[t->counter]; if ((count < counter->max) && (t->atom != NULL) && (xmlStrEqual(value, t->atom->valuep))) { ret = 0; break; } if ((count >= counter->min) && (count < counter->max) && (t->atom != NULL) && (xmlStrEqual(value, t->atom->valuep))) { ret = 1; break; } } } } else if (trans->count == REGEXP_ALL_COUNTER) { int i; int count; xmlRegTransPtr t; xmlRegCounterPtr counter;
ret = 1;
/* * Check all counted transitions from the current state */ for (i = 0;i < exec->state->nbTrans;i++) { t = &exec->state->trans[i]; if ((t->counter < 0) || (t == trans)) continue; counter = &exec->comp->counters[t->counter]; count = exec->counts[t->counter]; if ((count < counter->min) || (count > counter->max)) { ret = 0; break; } } } else if (trans->count >= 0) { int count; xmlRegCounterPtr counter;
/* * A counted transition. */
count = exec->counts[trans->count]; counter = &exec->comp->counters[trans->count]; ret = ((count >= counter->min) && (count <= counter->max)); } else if (atom == NULL) { fprintf(stderr, "epsilon transition left at runtime\n"); exec->status = XML_REGEXP_INTERNAL_ERROR; break; } else if (value != NULL) { ret = xmlRegStrEqualWildcard(atom->valuep, value); if (atom->neg) { ret = !ret; if (!compound) ret = 0; } if ((ret == 1) && (trans->counter >= 0)) { xmlRegCounterPtr counter; int count;
count = exec->counts[trans->counter]; counter = &exec->comp->counters[trans->counter]; if (count >= counter->max) ret = 0; }
if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) { xmlRegStatePtr to = exec->comp->states[trans->to];
/* * this is a multiple input sequence */ if (exec->state->nbTrans > exec->transno + 1) { if (exec->inputStackNr <= 0) { xmlFARegExecSaveInputString(exec, value, data); } xmlFARegExecSave(exec); } exec->transcount = 1; do { /* * Try to progress as much as possible on the input */ if (exec->transcount == atom->max) { break; } exec->index++; value = exec->inputStack[exec->index].value; data = exec->inputStack[exec->index].data;
/* * End of input: stop here */ if (value == NULL) { exec->index --; break; } if (exec->transcount >= atom->min) { int transno = exec->transno; xmlRegStatePtr state = exec->state;
/* * The transition is acceptable save it */ exec->transno = -1; /* trick */ exec->state = to; if (exec->inputStackNr <= 0) { xmlFARegExecSaveInputString(exec, value, data); } xmlFARegExecSave(exec); exec->transno = transno; exec->state = state; } ret = xmlStrEqual(value, atom->valuep); exec->transcount++; } while (ret == 1); if (exec->transcount < atom->min) ret = 0;
/* * If the last check failed but one transition was found * possible, rollback */ if (ret < 0) ret = 0; if (ret == 0) { goto rollback; } } } if (ret == 1) { if ((exec->callback != NULL) && (atom != NULL) && (data != NULL)) { exec->callback(exec->data, atom->valuep, atom->data, data); } if (exec->state->nbTrans > exec->transno + 1) { if (exec->inputStackNr <= 0) { xmlFARegExecSaveInputString(exec, value, data); } xmlFARegExecSave(exec); } if (trans->counter >= 0) { exec->counts[trans->counter]++; } if ((trans->count >= 0) && (trans->count < REGEXP_ALL_COUNTER)) { exec->counts[trans->count] = 0; } if ((exec->comp->states[trans->to] != NULL) && (exec->comp->states[trans->to]->type == XML_REGEXP_SINK_STATE)) { /* * entering a sink state, save the current state as error * state. */ if (exec->errString != NULL) xmlFree(exec->errString); exec->errString = xmlStrdup(value); exec->errState = exec->state; memcpy(exec->errCounts, exec->counts, exec->comp->nbCounters * sizeof(int)); } exec->state = exec->comp->states[trans->to]; exec->transno = 0; if (trans->atom != NULL) { if (exec->inputStack != NULL) { exec->index++; if (exec->index < exec->inputStackNr) { value = exec->inputStack[exec->index].value; data = exec->inputStack[exec->index].data; } else { value = NULL; data = NULL; } } else { value = NULL; data = NULL; } } goto progress; } else if (ret < 0) { exec->status = XML_REGEXP_INTERNAL_ERROR; break; } } if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {rollback: /* * if we didn't yet rollback on the current input * store the current state as the error state. */ if ((progress) && (exec->state != NULL) && (exec->state->type != XML_REGEXP_SINK_STATE)) { progress = 0; if (exec->errString != NULL) xmlFree(exec->errString); exec->errString = xmlStrdup(value); exec->errState = exec->state; if (exec->comp->nbCounters) memcpy(exec->errCounts, exec->counts, exec->comp->nbCounters * sizeof(int)); }
/* * Failed to find a way out */ exec->determinist = 0; xmlFARegExecRollBack(exec); if ((exec->inputStack != NULL ) && (exec->status == XML_REGEXP_OK)) { value = exec->inputStack[exec->index].value; data = exec->inputStack[exec->index].data; } } continue;progress: progress = 1; continue; } if (exec->status == XML_REGEXP_OK) { return(exec->state->type == XML_REGEXP_FINAL_STATE); } return(exec->status);}
/** * xmlRegExecPushString: * @exec: a regexp execution context or NULL to indicate the end * @value: a string token input * @data: data associated to the token to reuse in callbacks * * Push one input token in the execution context * * Returns: 1 if the regexp reached a final state, 0 if non-final, and * a negative value in case of error. */intxmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value, void *data) { return(xmlRegExecPushStringInternal(exec, value, data, 0));}
/** * xmlRegExecPushString2: * @exec: a regexp execution context or NULL to indicate the end * @value: the first string token input * @value2: the second string token input * @data: data associated to the token to reuse in callbacks * * Push one input token in the execution context * * Returns: 1 if the regexp reached a final state, 0 if non-final, and * a negative value in case of error. */intxmlRegExecPushString2(xmlRegExecCtxtPtr exec, const xmlChar *value, const xmlChar *value2, void *data) { xmlChar buf[150]; int lenn, lenp, ret; xmlChar *str;
if (exec == NULL) return(-1); if (exec->comp == NULL) return(-1); if (exec->status != XML_REGEXP_OK) return(exec->status);
if (value2 == NULL) return(xmlRegExecPushString(exec, value, data));
lenn = strlen((char *) value2); lenp = strlen((char *) value);
if (150 < lenn + lenp + 2) { str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2); if (str == NULL) { exec->status = XML_REGEXP_OUT_OF_MEMORY; return(-1); } } else { str = buf; } memcpy(&str[0], value, lenp); str[lenp] = XML_REG_STRING_SEPARATOR; memcpy(&str[lenp + 1], value2, lenn); str[lenn + lenp + 1] = 0;
if (exec->comp->compact != NULL) ret = xmlRegCompactPushString(exec, exec->comp, str, data); else ret = xmlRegExecPushStringInternal(exec, str, data, 1);
if (str != buf) xmlFree(str); return(ret);}
/** * xmlRegExecGetValues: * @exec: a regexp execution context * @err: error extraction or normal one * @nbval: pointer to the number of accepted values IN/OUT * @nbneg: return number of negative transitions * @values: pointer to the array of acceptable values * @terminal: return value if this was a terminal state * * Extract information from the regexp execution, internal routine to * implement xmlRegExecNextValues() and xmlRegExecErrInfo() * * Returns: 0 in case of success or -1 in case of error. */static intxmlRegExecGetValues(xmlRegExecCtxtPtr exec, int err, int *nbval, int *nbneg, xmlChar **values, int *terminal) { int maxval; int nb = 0;
if ((exec == NULL) || (nbval == NULL) || (nbneg == NULL) || (values == NULL) || (*nbval <= 0)) return(-1);
maxval = *nbval; *nbval = 0; *nbneg = 0; if ((exec->comp != NULL) && (exec->comp->compact != NULL)) { xmlRegexpPtr comp; int target, i, state;
comp = exec->comp;
if (err) { if (exec->errStateNo == -1) return(-1); state = exec->errStateNo; } else { state = exec->index; } if (terminal != NULL) { if (comp->compact[state * (comp->nbstrings + 1)] == XML_REGEXP_FINAL_STATE) *terminal = 1; else *terminal = 0; } for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) { target = comp->compact[state * (comp->nbstrings + 1) + i + 1]; if ((target > 0) && (target <= comp->nbstates) && (comp->compact[(target - 1) * (comp->nbstrings + 1)] != XML_REGEXP_SINK_STATE)) { values[nb++] = comp->stringMap[i]; (*nbval)++; } } for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) { target = comp->compact[state * (comp->nbstrings + 1) + i + 1]; if ((target > 0) && (target <= comp->nbstates) && (comp->compact[(target - 1) * (comp->nbstrings + 1)] == XML_REGEXP_SINK_STATE)) { values[nb++] = comp->stringMap[i]; (*nbneg)++; } } } else { int transno; xmlRegTransPtr trans; xmlRegAtomPtr atom; xmlRegStatePtr state;
if (terminal != NULL) { if (exec->state->type == XML_REGEXP_FINAL_STATE) *terminal = 1; else *terminal = 0; }
if (err) { if (exec->errState == NULL) return(-1); state = exec->errState; } else { if (exec->state == NULL) return(-1); state = exec->state; } for (transno = 0; (transno < state->nbTrans) && (nb < maxval); transno++) { trans = &state->trans[transno]; if (trans->to < 0) continue; atom = trans->atom; if ((atom == NULL) || (atom->valuep == NULL)) continue; if (trans->count == REGEXP_ALL_LAX_COUNTER) { /* this should not be reached but ... */ TODO; } else if (trans->count == REGEXP_ALL_COUNTER) { /* this should not be reached but ... */ TODO; } else if (trans->counter >= 0) { xmlRegCounterPtr counter = NULL; int count;
if (err) count = exec->errCounts[trans->counter]; else count = exec->counts[trans->counter]; if (exec->comp != NULL) counter = &exec->comp->counters[trans->counter]; if ((counter == NULL) || (count < counter->max)) { if (atom->neg) values[nb++] = (xmlChar *) atom->valuep2; else values[nb++] = (xmlChar *) atom->valuep; (*nbval)++; } } else { if ((exec->comp != NULL) && (exec->comp->states[trans->to] != NULL) && (exec->comp->states[trans->to]->type != XML_REGEXP_SINK_STATE)) { if (atom->neg) values[nb++] = (xmlChar *) atom->valuep2; else values[nb++] = (xmlChar *) atom->valuep; (*nbval)++; } } } for (transno = 0; (transno < state->nbTrans) && (nb < maxval); transno++) { trans = &state->trans[transno]; if (trans->to < 0) continue; atom = trans->atom; if ((atom == NULL) || (atom->valuep == NULL)) continue; if (trans->count == REGEXP_ALL_LAX_COUNTER) { continue; } else if (trans->count == REGEXP_ALL_COUNTER) { continue; } else if (trans->counter >= 0) { continue; } else { if ((exec->comp->states[trans->to] != NULL) && (exec->comp->states[trans->to]->type == XML_REGEXP_SINK_STATE)) { if (atom->neg) values[nb++] = (xmlChar *) atom->valuep2; else values[nb++] = (xmlChar *) atom->valuep; (*nbneg)++; } } } } return(0);}
/** * xmlRegExecNextValues: * @exec: a regexp execution context * @nbval: pointer to the number of accepted values IN/OUT * @nbneg: return number of negative transitions * @values: pointer to the array of acceptable values * @terminal: return value if this was a terminal state * * Extract information from the regexp execution, * the parameter @values must point to an array of @nbval string pointers * on return nbval will contain the number of possible strings in that * state and the @values array will be updated with them. The string values * returned will be freed with the @exec context and don't need to be * deallocated. * * Returns: 0 in case of success or -1 in case of error. */intxmlRegExecNextValues(xmlRegExecCtxtPtr exec, int *nbval, int *nbneg, xmlChar **values, int *terminal) { return(xmlRegExecGetValues(exec, 0, nbval, nbneg, values, terminal));}
/** * xmlRegExecErrInfo: * @exec: a regexp execution context generating an error * @string: return value for the error string * @nbval: pointer to the number of accepted values IN/OUT * @nbneg: return number of negative transitions * @values: pointer to the array of acceptable values * @terminal: return value if this was a terminal state * * Extract error information from the regexp execution, the parameter * @string will be updated with the value pushed and not accepted, * the parameter @values must point to an array of @nbval string pointers * on return nbval will contain the number of possible strings in that * state and the @values array will be updated with them. The string values * returned will be freed with the @exec context and don't need to be * deallocated. * * Returns: 0 in case of success or -1 in case of error. */intxmlRegExecErrInfo(xmlRegExecCtxtPtr exec, const xmlChar **string, int *nbval, int *nbneg, xmlChar **values, int *terminal) { if (exec == NULL) return(-1); if (string != NULL) { if (exec->status != XML_REGEXP_OK) *string = exec->errString; else *string = NULL; } return(xmlRegExecGetValues(exec, 1, nbval, nbneg, values, terminal));}
#if 0static intxmlRegExecPushChar(xmlRegExecCtxtPtr exec, int UCS) { xmlRegTransPtr trans; xmlRegAtomPtr atom; int ret; int codepoint, len;
if (exec == NULL) return(-1); if (exec->status != XML_REGEXP_OK) return(exec->status);
while ((exec->status == XML_REGEXP_OK) && ((exec->inputString[exec->index] != 0) || (exec->state->type != XML_REGEXP_FINAL_STATE))) {
/* * End of input on non-terminal state, rollback, however we may * still have epsilon like transition for counted transitions * on counters, in that case don't break too early. */ if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL)) goto rollback;
exec->transcount = 0; for (;exec->transno < exec->state->nbTrans;exec->transno++) { trans = &exec->state->trans[exec->transno]; if (trans->to < 0) continue; atom = trans->atom; ret = 0; if (trans->count >= 0) { int count; xmlRegCounterPtr counter;
/* * A counted transition. */
count = exec->counts[trans->count]; counter = &exec->comp->counters[trans->count]; ret = ((count >= counter->min) && (count <= counter->max)); } else if (atom == NULL) { fprintf(stderr, "epsilon transition left at runtime\n"); exec->status = XML_REGEXP_INTERNAL_ERROR; break; } else if (exec->inputString[exec->index] != 0) { codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len); ret = xmlRegCheckCharacter(atom, codepoint); if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) { xmlRegStatePtr to = exec->comp->states[trans->to];
/* * this is a multiple input sequence */ if (exec->state->nbTrans > exec->transno + 1) { xmlFARegExecSave(exec); } exec->transcount = 1; do { /* * Try to progress as much as possible on the input */ if (exec->transcount == atom->max) { break; } exec->index += len; /* * End of input: stop here */ if (exec->inputString[exec->index] == 0) { exec->index -= len; break; } if (exec->transcount >= atom->min) { int transno = exec->transno; xmlRegStatePtr state = exec->state;
/* * The transition is acceptable save it */ exec->transno = -1; /* trick */ exec->state = to; xmlFARegExecSave(exec); exec->transno = transno; exec->state = state; } codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len); ret = xmlRegCheckCharacter(atom, codepoint); exec->transcount++; } while (ret == 1); if (exec->transcount < atom->min) ret = 0;
/* * If the last check failed but one transition was found * possible, rollback */ if (ret < 0) ret = 0; if (ret == 0) { goto rollback; } } } if (ret == 1) { if (exec->state->nbTrans > exec->transno + 1) { xmlFARegExecSave(exec); } /* * restart count for expressions like this ((abc){2})* */ if (trans->count >= 0) { exec->counts[trans->count] = 0; } if (trans->counter >= 0) { exec->counts[trans->counter]++; } exec->state = exec->comp->states[trans->to]; exec->transno = 0; if (trans->atom != NULL) { exec->index += len; } goto progress; } else if (ret < 0) { exec->status = XML_REGEXP_INTERNAL_ERROR; break; } } if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {rollback: /* * Failed to find a way out */ exec->determinist = 0; xmlFARegExecRollBack(exec); }progress: continue; }}#endif/************************************************************************ * * * Parser for the Schemas Datatype Regular Expressions * * http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs * * * ************************************************************************/
/** * xmlFAIsChar: * @ctxt: a regexp parser context * * [10] Char ::= [^.\?*+()|#x5B#x5D] */static intxmlFAIsChar(xmlRegParserCtxtPtr ctxt) { int cur; int len;
len = 4; cur = xmlGetUTF8Char(ctxt->cur, &len); if (cur < 0) { ERROR("Invalid UTF-8"); return(0); } if ((cur == '.') || (cur == '\\') || (cur == '?') || (cur == '*') || (cur == '+') || (cur == '(') || (cur == ')') || (cur == '|') || (cur == 0x5B) || (cur == 0x5D) || (cur == 0)) return(-1); return(cur);}
/** * xmlFAParseCharProp: * @ctxt: a regexp parser context * * [27] charProp ::= IsCategory | IsBlock * [28] IsCategory ::= Letters | Marks | Numbers | Punctuation | * Separators | Symbols | Others * [29] Letters ::= 'L' [ultmo]? * [30] Marks ::= 'M' [nce]? * [31] Numbers ::= 'N' [dlo]? * [32] Punctuation ::= 'P' [cdseifo]? * [33] Separators ::= 'Z' [slp]? * [34] Symbols ::= 'S' [mcko]? * [35] Others ::= 'C' [cfon]? * [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+ */static voidxmlFAParseCharProp(xmlRegParserCtxtPtr ctxt) { int cur; xmlRegAtomType type = (xmlRegAtomType) 0; xmlChar *blockName = NULL;
cur = CUR; if (cur == 'L') { NEXT; cur = CUR; if (cur == 'u') { NEXT; type = XML_REGEXP_LETTER_UPPERCASE; } else if (cur == 'l') { NEXT; type = XML_REGEXP_LETTER_LOWERCASE; } else if (cur == 't') { NEXT; type = XML_REGEXP_LETTER_TITLECASE; } else if (cur == 'm') { NEXT; type = XML_REGEXP_LETTER_MODIFIER; } else if (cur == 'o') { NEXT; type = XML_REGEXP_LETTER_OTHERS; } else { type = XML_REGEXP_LETTER; } } else if (cur == 'M') { NEXT; cur = CUR; if (cur == 'n') { NEXT; /* nonspacing */ type = XML_REGEXP_MARK_NONSPACING; } else if (cur == 'c') { NEXT; /* spacing combining */ type = XML_REGEXP_MARK_SPACECOMBINING; } else if (cur == 'e') { NEXT; /* enclosing */ type = XML_REGEXP_MARK_ENCLOSING; } else { /* all marks */ type = XML_REGEXP_MARK; } } else if (cur == 'N') { NEXT; cur = CUR; if (cur == 'd') { NEXT; /* digital */ type = XML_REGEXP_NUMBER_DECIMAL; } else if (cur == 'l') { NEXT; /* letter */ type = XML_REGEXP_NUMBER_LETTER; } else if (cur == 'o') { NEXT; /* other */ type = XML_REGEXP_NUMBER_OTHERS; } else { /* all numbers */ type = XML_REGEXP_NUMBER; } } else if (cur == 'P') { NEXT; cur = CUR; if (cur == 'c') { NEXT; /* connector */ type = XML_REGEXP_PUNCT_CONNECTOR; } else if (cur == 'd') { NEXT; /* dash */ type = XML_REGEXP_PUNCT_DASH; } else if (cur == 's') { NEXT; /* open */ type = XML_REGEXP_PUNCT_OPEN; } else if (cur == 'e') { NEXT; /* close */ type = XML_REGEXP_PUNCT_CLOSE; } else if (cur == 'i') { NEXT; /* initial quote */ type = XML_REGEXP_PUNCT_INITQUOTE; } else if (cur == 'f') { NEXT; /* final quote */ type = XML_REGEXP_PUNCT_FINQUOTE; } else if (cur == 'o') { NEXT; /* other */ type = XML_REGEXP_PUNCT_OTHERS; } else { /* all punctuation */ type = XML_REGEXP_PUNCT; } } else if (cur == 'Z') { NEXT; cur = CUR; if (cur == 's') { NEXT; /* space */ type = XML_REGEXP_SEPAR_SPACE; } else if (cur == 'l') { NEXT; /* line */ type = XML_REGEXP_SEPAR_LINE; } else if (cur == 'p') { NEXT; /* paragraph */ type = XML_REGEXP_SEPAR_PARA; } else { /* all separators */ type = XML_REGEXP_SEPAR; } } else if (cur == 'S') { NEXT; cur = CUR; if (cur == 'm') { NEXT; type = XML_REGEXP_SYMBOL_MATH; /* math */ } else if (cur == 'c') { NEXT; type = XML_REGEXP_SYMBOL_CURRENCY; /* currency */ } else if (cur == 'k') { NEXT; type = XML_REGEXP_SYMBOL_MODIFIER; /* modifiers */ } else if (cur == 'o') { NEXT; type = XML_REGEXP_SYMBOL_OTHERS; /* other */ } else { /* all symbols */ type = XML_REGEXP_SYMBOL; } } else if (cur == 'C') { NEXT; cur = CUR; if (cur == 'c') { NEXT; /* control */ type = XML_REGEXP_OTHER_CONTROL; } else if (cur == 'f') { NEXT; /* format */ type = XML_REGEXP_OTHER_FORMAT; } else if (cur == 'o') { NEXT; /* private use */ type = XML_REGEXP_OTHER_PRIVATE; } else if (cur == 'n') { NEXT; /* not assigned */ type = XML_REGEXP_OTHER_NA; } else { /* all others */ type = XML_REGEXP_OTHER; } } else if (cur == 'I') { const xmlChar *start; NEXT; cur = CUR; if (cur != 's') { ERROR("IsXXXX expected"); return; } NEXT; start = ctxt->cur; cur = CUR; if (((cur >= 'a') && (cur <= 'z')) || ((cur >= 'A') && (cur <= 'Z')) || ((cur >= '0') && (cur <= '9')) || (cur == 0x2D)) { NEXT; cur = CUR; while (((cur >= 'a') && (cur <= 'z')) || ((cur >= 'A') && (cur <= 'Z')) || ((cur >= '0') && (cur <= '9')) || (cur == 0x2D)) { NEXT; cur = CUR; } } type = XML_REGEXP_BLOCK_NAME; blockName = xmlStrndup(start, ctxt->cur - start); } else { ERROR("Unknown char property"); return; } if (ctxt->atom == NULL) { ctxt->atom = xmlRegNewAtom(ctxt, type); if (ctxt->atom == NULL) { xmlFree(blockName); return; } ctxt->atom->valuep = blockName; } else if (ctxt->atom->type == XML_REGEXP_RANGES) { if (xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg, type, 0, 0, blockName) == NULL) { xmlFree(blockName); } }}
static int parse_escaped_codeunit(xmlRegParserCtxtPtr ctxt){ int val = 0, i, cur; for (i = 0; i < 4; i++) { NEXT; val *= 16; cur = CUR; if (cur >= '0' && cur <= '9') { val += cur - '0'; } else if (cur >= 'A' && cur <= 'F') { val += cur - 'A' + 10; } else if (cur >= 'a' && cur <= 'f') { val += cur - 'a' + 10; } else { ERROR("Expecting hex digit"); return -1; } } return val;}
static int parse_escaped_codepoint(xmlRegParserCtxtPtr ctxt){ int val = parse_escaped_codeunit(ctxt); if (0xD800 <= val && val <= 0xDBFF) { NEXT; if (CUR == '\\') { NEXT; if (CUR == 'u') { int low = parse_escaped_codeunit(ctxt); if (0xDC00 <= low && low <= 0xDFFF) { return (val - 0xD800) * 0x400 + (low - 0xDC00) + 0x10000; } } } ERROR("Invalid low surrogate pair code unit"); val = -1; } return val;}
/** * xmlFAParseCharClassEsc: * @ctxt: a regexp parser context * * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc ) * [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E] * [25] catEsc ::= '\p{' charProp '}' * [26] complEsc ::= '\P{' charProp '}' * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW]) */static voidxmlFAParseCharClassEsc(xmlRegParserCtxtPtr ctxt) { int cur;
if (CUR == '.') { if (ctxt->atom == NULL) { ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_ANYCHAR); } else if (ctxt->atom->type == XML_REGEXP_RANGES) { xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg, XML_REGEXP_ANYCHAR, 0, 0, NULL); } NEXT; return; } if (CUR != '\\') { ERROR("Escaped sequence: expecting \\"); return; } NEXT; cur = CUR; if (cur == 'p') { NEXT; if (CUR != '{') { ERROR("Expecting '{'"); return; } NEXT; xmlFAParseCharProp(ctxt); if (CUR != '}') { ERROR("Expecting '}'"); return; } NEXT; } else if (cur == 'P') { NEXT; if (CUR != '{') { ERROR("Expecting '{'"); return; } NEXT; xmlFAParseCharProp(ctxt); if (ctxt->atom != NULL) ctxt->atom->neg = 1; if (CUR != '}') { ERROR("Expecting '}'"); return; } NEXT; } else if ((cur == 'n') || (cur == 'r') || (cur == 't') || (cur == '\\') || (cur == '|') || (cur == '.') || (cur == '?') || (cur == '*') || (cur == '+') || (cur == '(') || (cur == ')') || (cur == '{') || (cur == '}') || (cur == 0x2D) || (cur == 0x5B) || (cur == 0x5D) || (cur == 0x5E) ||
/* Non-standard escape sequences: * Java 1.8|.NET Core 3.1|MSXML 6 */ (cur == '!') || /* + | + | + */ (cur == '"') || /* + | + | + */ (cur == '#') || /* + | + | + */ (cur == '$') || /* + | + | + */ (cur == '%') || /* + | + | + */ (cur == ',') || /* + | + | + */ (cur == '/') || /* + | + | + */ (cur == ':') || /* + | + | + */ (cur == ';') || /* + | + | + */ (cur == '=') || /* + | + | + */ (cur == '>') || /* | + | + */ (cur == '@') || /* + | + | + */ (cur == '`') || /* + | + | + */ (cur == '~') || /* + | + | + */ (cur == 'u')) { /* | + | + */ if (ctxt->atom == NULL) { ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL); if (ctxt->atom != NULL) { switch (cur) { case 'n': ctxt->atom->codepoint = '\n'; break; case 'r': ctxt->atom->codepoint = '\r'; break; case 't': ctxt->atom->codepoint = '\t'; break; case 'u': cur = parse_escaped_codepoint(ctxt); if (cur < 0) { return; } ctxt->atom->codepoint = cur; break; default: ctxt->atom->codepoint = cur; } } } else if (ctxt->atom->type == XML_REGEXP_RANGES) { switch (cur) { case 'n': cur = '\n'; break; case 'r': cur = '\r'; break; case 't': cur = '\t'; break; } xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg, XML_REGEXP_CHARVAL, cur, cur, NULL); } NEXT; } else if ((cur == 's') || (cur == 'S') || (cur == 'i') || (cur == 'I') || (cur == 'c') || (cur == 'C') || (cur == 'd') || (cur == 'D') || (cur == 'w') || (cur == 'W')) { xmlRegAtomType type = XML_REGEXP_ANYSPACE;
switch (cur) { case 's': type = XML_REGEXP_ANYSPACE; break; case 'S': type = XML_REGEXP_NOTSPACE; break; case 'i': type = XML_REGEXP_INITNAME; break; case 'I': type = XML_REGEXP_NOTINITNAME; break; case 'c': type = XML_REGEXP_NAMECHAR; break; case 'C': type = XML_REGEXP_NOTNAMECHAR; break; case 'd': type = XML_REGEXP_DECIMAL; break; case 'D': type = XML_REGEXP_NOTDECIMAL; break; case 'w': type = XML_REGEXP_REALCHAR; break; case 'W': type = XML_REGEXP_NOTREALCHAR; break; } NEXT; if (ctxt->atom == NULL) { ctxt->atom = xmlRegNewAtom(ctxt, type); } else if (ctxt->atom->type == XML_REGEXP_RANGES) { xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg, type, 0, 0, NULL); } } else { ERROR("Wrong escape sequence, misuse of character '\\'"); }}
/** * xmlFAParseCharRange: * @ctxt: a regexp parser context * * [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash * [18] seRange ::= charOrEsc '-' charOrEsc * [20] charOrEsc ::= XmlChar | SingleCharEsc * [21] XmlChar ::= [^\#x2D#x5B#x5D] * [22] XmlCharIncDash ::= [^\#x5B#x5D] */static voidxmlFAParseCharRange(xmlRegParserCtxtPtr ctxt) { int cur, len; int start = -1; int end = -1;
if (CUR == '\0') { ERROR("Expecting ']'"); return; }
cur = CUR; if (cur == '\\') { NEXT; cur = CUR; switch (cur) { case 'n': start = 0xA; break; case 'r': start = 0xD; break; case 't': start = 0x9; break; case '\\': case '|': case '.': case '-': case '^': case '?': case '*': case '+': case '{': case '}': case '(': case ')': case '[': case ']': start = cur; break; default: ERROR("Invalid escape value"); return; } end = start; len = 1; } else if ((cur != 0x5B) && (cur != 0x5D)) { len = 4; end = start = xmlGetUTF8Char(ctxt->cur, &len); if (start < 0) { ERROR("Invalid UTF-8"); return; } } else { ERROR("Expecting a char range"); return; } /* * Since we are "inside" a range, we can assume ctxt->cur is past * the start of ctxt->string, and PREV should be safe */ if ((start == '-') && (NXT(1) != ']') && (PREV != '[') && (PREV != '^')) { NEXTL(len); return; } NEXTL(len); cur = CUR; if ((cur != '-') || (NXT(1) == '[') || (NXT(1) == ']')) { xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg, XML_REGEXP_CHARVAL, start, end, NULL); return; } NEXT; cur = CUR; if (cur == '\\') { NEXT; cur = CUR; switch (cur) { case 'n': end = 0xA; break; case 'r': end = 0xD; break; case 't': end = 0x9; break; case '\\': case '|': case '.': case '-': case '^': case '?': case '*': case '+': case '{': case '}': case '(': case ')': case '[': case ']': end = cur; break; default: ERROR("Invalid escape value"); return; } len = 1; } else if ((cur != '\0') && (cur != 0x5B) && (cur != 0x5D)) { len = 4; end = xmlGetUTF8Char(ctxt->cur, &len); if (end < 0) { ERROR("Invalid UTF-8"); return; } } else { ERROR("Expecting the end of a char range"); return; }
/* TODO check that the values are acceptable character ranges for XML */ if (end < start) { ERROR("End of range is before start of range"); } else { NEXTL(len); xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg, XML_REGEXP_CHARVAL, start, end, NULL); } return;}
/** * xmlFAParsePosCharGroup: * @ctxt: a regexp parser context * * [14] posCharGroup ::= ( charRange | charClassEsc )+ */static voidxmlFAParsePosCharGroup(xmlRegParserCtxtPtr ctxt) { do { if (CUR == '\\') { xmlFAParseCharClassEsc(ctxt); } else { xmlFAParseCharRange(ctxt); } } while ((CUR != ']') && (CUR != '-') && (CUR != 0) && (ctxt->error == 0));}
/** * xmlFAParseCharGroup: * @ctxt: a regexp parser context * * [13] charGroup ::= posCharGroup | negCharGroup | charClassSub * [15] negCharGroup ::= '^' posCharGroup * [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr * [12] charClassExpr ::= '[' charGroup ']' */static voidxmlFAParseCharGroup(xmlRegParserCtxtPtr ctxt) { int neg = ctxt->neg;
if (CUR == '^') { NEXT; ctxt->neg = !ctxt->neg; xmlFAParsePosCharGroup(ctxt); ctxt->neg = neg; } while ((CUR != ']') && (ctxt->error == 0)) { if ((CUR == '-') && (NXT(1) == '[')) { NEXT; /* eat the '-' */ NEXT; /* eat the '[' */ ctxt->neg = 2; xmlFAParseCharGroup(ctxt); ctxt->neg = neg; if (CUR == ']') { NEXT; } else { ERROR("charClassExpr: ']' expected"); } break; } else { xmlFAParsePosCharGroup(ctxt); } }}
/** * xmlFAParseCharClass: * @ctxt: a regexp parser context * * [11] charClass ::= charClassEsc | charClassExpr * [12] charClassExpr ::= '[' charGroup ']' */static voidxmlFAParseCharClass(xmlRegParserCtxtPtr ctxt) { if (CUR == '[') { NEXT; ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_RANGES); if (ctxt->atom == NULL) return; xmlFAParseCharGroup(ctxt); if (CUR == ']') { NEXT; } else { ERROR("xmlFAParseCharClass: ']' expected"); } } else { xmlFAParseCharClassEsc(ctxt); }}
/** * xmlFAParseQuantExact: * @ctxt: a regexp parser context * * [8] QuantExact ::= [0-9]+ * * Returns 0 if success or -1 in case of error */static intxmlFAParseQuantExact(xmlRegParserCtxtPtr ctxt) { int ret = 0; int ok = 0; int overflow = 0;
while ((CUR >= '0') && (CUR <= '9')) { if (ret > INT_MAX / 10) { overflow = 1; } else { int digit = CUR - '0';
ret *= 10; if (ret > INT_MAX - digit) overflow = 1; else ret += digit; } ok = 1; NEXT; } if ((ok != 1) || (overflow == 1)) { return(-1); } return(ret);}
/** * xmlFAParseQuantifier: * @ctxt: a regexp parser context * * [4] quantifier ::= [?*+] | ( '{' quantity '}' ) * [5] quantity ::= quantRange | quantMin | QuantExact * [6] quantRange ::= QuantExact ',' QuantExact * [7] quantMin ::= QuantExact ',' * [8] QuantExact ::= [0-9]+ */static intxmlFAParseQuantifier(xmlRegParserCtxtPtr ctxt) { int cur;
cur = CUR; if ((cur == '?') || (cur == '*') || (cur == '+')) { if (ctxt->atom != NULL) { if (cur == '?') ctxt->atom->quant = XML_REGEXP_QUANT_OPT; else if (cur == '*') ctxt->atom->quant = XML_REGEXP_QUANT_MULT; else if (cur == '+') ctxt->atom->quant = XML_REGEXP_QUANT_PLUS; } NEXT; return(1); } if (cur == '{') { int min = 0, max = 0;
NEXT; cur = xmlFAParseQuantExact(ctxt); if (cur >= 0) min = cur; else { ERROR("Improper quantifier"); } if (CUR == ',') { NEXT; if (CUR == '}') max = INT_MAX; else { cur = xmlFAParseQuantExact(ctxt); if (cur >= 0) max = cur; else { ERROR("Improper quantifier"); } } } if (CUR == '}') { NEXT; } else { ERROR("Unterminated quantifier"); } if (max == 0) max = min; if (ctxt->atom != NULL) { ctxt->atom->quant = XML_REGEXP_QUANT_RANGE; ctxt->atom->min = min; ctxt->atom->max = max; } return(1); } return(0);}
/** * xmlFAParseAtom: * @ctxt: a regexp parser context * * [9] atom ::= Char | charClass | ( '(' regExp ')' ) */static intxmlFAParseAtom(xmlRegParserCtxtPtr ctxt) { int codepoint, len;
codepoint = xmlFAIsChar(ctxt); if (codepoint > 0) { ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL); if (ctxt->atom == NULL) return(-1); len = 4; codepoint = xmlGetUTF8Char(ctxt->cur, &len); if (codepoint < 0) { ERROR("Invalid UTF-8"); return(-1); } ctxt->atom->codepoint = codepoint; NEXTL(len); return(1); } else if (CUR == '|') { return(0); } else if (CUR == 0) { return(0); } else if (CUR == ')') { return(0); } else if (CUR == '(') { xmlRegStatePtr start, oldend, start0;
NEXT; if (ctxt->depth >= 50) { ERROR("xmlFAParseAtom: maximum nesting depth exceeded"); return(-1); } /* * this extra Epsilon transition is needed if we count with 0 allowed * unfortunately this can't be known at that point */ xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL); start0 = ctxt->state; xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL); start = ctxt->state; oldend = ctxt->end; ctxt->end = NULL; ctxt->atom = NULL; ctxt->depth++; xmlFAParseRegExp(ctxt, 0); ctxt->depth--; if (CUR == ')') { NEXT; } else { ERROR("xmlFAParseAtom: expecting ')'"); } ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_SUBREG); if (ctxt->atom == NULL) return(-1); ctxt->atom->start = start; ctxt->atom->start0 = start0; ctxt->atom->stop = ctxt->state; ctxt->end = oldend; return(1); } else if ((CUR == '[') || (CUR == '\\') || (CUR == '.')) { xmlFAParseCharClass(ctxt); return(1); } return(0);}
/** * xmlFAParsePiece: * @ctxt: a regexp parser context * * [3] piece ::= atom quantifier? */static intxmlFAParsePiece(xmlRegParserCtxtPtr ctxt) { int ret;
ctxt->atom = NULL; ret = xmlFAParseAtom(ctxt); if (ret == 0) return(0); if (ctxt->atom == NULL) { ERROR("internal: no atom generated"); } xmlFAParseQuantifier(ctxt); return(1);}
/** * xmlFAParseBranch: * @ctxt: a regexp parser context * @to: optional target to the end of the branch * * @to is used to optimize by removing duplicate path in automata * in expressions like (a|b)(c|d) * * [2] branch ::= piece* */static intxmlFAParseBranch(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr to) { xmlRegStatePtr previous; int ret;
previous = ctxt->state; ret = xmlFAParsePiece(ctxt); if (ret == 0) { /* Empty branch */ xmlFAGenerateEpsilonTransition(ctxt, previous, to); } else { if (xmlFAGenerateTransitions(ctxt, previous, (CUR=='|' || CUR==')' || CUR==0) ? to : NULL, ctxt->atom) < 0) { xmlRegFreeAtom(ctxt->atom); ctxt->atom = NULL; return(-1); } previous = ctxt->state; ctxt->atom = NULL; } while ((ret != 0) && (ctxt->error == 0)) { ret = xmlFAParsePiece(ctxt); if (ret != 0) { if (xmlFAGenerateTransitions(ctxt, previous, (CUR=='|' || CUR==')' || CUR==0) ? to : NULL, ctxt->atom) < 0) { xmlRegFreeAtom(ctxt->atom); ctxt->atom = NULL; return(-1); } previous = ctxt->state; ctxt->atom = NULL; } } return(0);}
/** * xmlFAParseRegExp: * @ctxt: a regexp parser context * @top: is this the top-level expression ? * * [1] regExp ::= branch ( '|' branch )* */static voidxmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top) { xmlRegStatePtr start, end;
/* if not top start should have been generated by an epsilon trans */ start = ctxt->state; ctxt->end = NULL; xmlFAParseBranch(ctxt, NULL); if (top) { ctxt->state->type = XML_REGEXP_FINAL_STATE; } if (CUR != '|') { ctxt->end = ctxt->state; return; } end = ctxt->state; while ((CUR == '|') && (ctxt->error == 0)) { NEXT; ctxt->state = start; ctxt->end = NULL; xmlFAParseBranch(ctxt, end); } if (!top) { ctxt->state = end; ctxt->end = end; }}
/************************************************************************ * * * The basic API * * * ************************************************************************/
/** * xmlRegexpPrint: * @output: the file for the output debug * @regexp: the compiled regexp * * Print the content of the compiled regular expression */voidxmlRegexpPrint(FILE *output, xmlRegexpPtr regexp) { int i;
if (output == NULL) return; fprintf(output, " regexp: "); if (regexp == NULL) { fprintf(output, "NULL\n"); return; } fprintf(output, "'%s' ", regexp->string); fprintf(output, "\n"); fprintf(output, "%d atoms:\n", regexp->nbAtoms); for (i = 0;i < regexp->nbAtoms; i++) { fprintf(output, " %02d ", i); xmlRegPrintAtom(output, regexp->atoms[i]); } fprintf(output, "%d states:", regexp->nbStates); fprintf(output, "\n"); for (i = 0;i < regexp->nbStates; i++) { xmlRegPrintState(output, regexp->states[i]); } fprintf(output, "%d counters:\n", regexp->nbCounters); for (i = 0;i < regexp->nbCounters; i++) { fprintf(output, " %d: min %d max %d\n", i, regexp->counters[i].min, regexp->counters[i].max); }}
/** * xmlRegexpCompile: * @regexp: a regular expression string * * Parses a regular expression conforming to XML Schemas Part 2 Datatype * Appendix F and builds an automata suitable for testing strings against * that regular expression * * Returns the compiled expression or NULL in case of error */xmlRegexpPtrxmlRegexpCompile(const xmlChar *regexp) { xmlRegexpPtr ret = NULL; xmlRegParserCtxtPtr ctxt;
if (regexp == NULL) return(NULL);
ctxt = xmlRegNewParserCtxt(regexp); if (ctxt == NULL) return(NULL);
/* initialize the parser */ ctxt->state = xmlRegStatePush(ctxt); if (ctxt->state == NULL) goto error; ctxt->start = ctxt->state; ctxt->end = NULL;
/* parse the expression building an automata */ xmlFAParseRegExp(ctxt, 1); if (CUR != 0) { ERROR("xmlFAParseRegExp: extra characters"); } if (ctxt->error != 0) goto error; ctxt->end = ctxt->state; ctxt->start->type = XML_REGEXP_START_STATE; ctxt->end->type = XML_REGEXP_FINAL_STATE;
/* remove the Epsilon except for counted transitions */ xmlFAEliminateEpsilonTransitions(ctxt);
if (ctxt->error != 0) goto error; ret = xmlRegEpxFromParse(ctxt);
error: xmlRegFreeParserCtxt(ctxt); return(ret);}
/** * xmlRegexpExec: * @comp: the compiled regular expression * @content: the value to check against the regular expression * * Check if the regular expression generates the value * * Returns 1 if it matches, 0 if not and a negative value in case of error */intxmlRegexpExec(xmlRegexpPtr comp, const xmlChar *content) { if ((comp == NULL) || (content == NULL)) return(-1); return(xmlFARegExec(comp, content));}
/** * xmlRegexpIsDeterminist: * @comp: the compiled regular expression * * Check if the regular expression is determinist * * Returns 1 if it yes, 0 if not and a negative value in case of error */intxmlRegexpIsDeterminist(xmlRegexpPtr comp) { xmlAutomataPtr am; int ret;
if (comp == NULL) return(-1); if (comp->determinist != -1) return(comp->determinist);
am = xmlNewAutomata(); if (am == NULL) return(-1); if (am->states != NULL) { int i;
for (i = 0;i < am->nbStates;i++) xmlRegFreeState(am->states[i]); xmlFree(am->states); } am->nbAtoms = comp->nbAtoms; am->atoms = comp->atoms; am->nbStates = comp->nbStates; am->states = comp->states; am->determinist = -1; am->flags = comp->flags; ret = xmlFAComputesDeterminism(am); am->atoms = NULL; am->states = NULL; xmlFreeAutomata(am); comp->determinist = ret; return(ret);}
/** * xmlRegFreeRegexp: * @regexp: the regexp * * Free a regexp */voidxmlRegFreeRegexp(xmlRegexpPtr regexp) { int i; if (regexp == NULL) return;
if (regexp->string != NULL) xmlFree(regexp->string); if (regexp->states != NULL) { for (i = 0;i < regexp->nbStates;i++) xmlRegFreeState(regexp->states[i]); xmlFree(regexp->states); } if (regexp->atoms != NULL) { for (i = 0;i < regexp->nbAtoms;i++) xmlRegFreeAtom(regexp->atoms[i]); xmlFree(regexp->atoms); } if (regexp->counters != NULL) xmlFree(regexp->counters); if (regexp->compact != NULL) xmlFree(regexp->compact); if (regexp->transdata != NULL) xmlFree(regexp->transdata); if (regexp->stringMap != NULL) { for (i = 0; i < regexp->nbstrings;i++) xmlFree(regexp->stringMap[i]); xmlFree(regexp->stringMap); }
xmlFree(regexp);}
#ifdef LIBXML_AUTOMATA_ENABLED/************************************************************************ * * * The Automata interface * * * ************************************************************************/
/** * xmlNewAutomata: * * Create a new automata * * Returns the new object or NULL in case of failure */xmlAutomataPtrxmlNewAutomata(void) { xmlAutomataPtr ctxt;
ctxt = xmlRegNewParserCtxt(NULL); if (ctxt == NULL) return(NULL);
/* initialize the parser */ ctxt->state = xmlRegStatePush(ctxt); if (ctxt->state == NULL) { xmlFreeAutomata(ctxt); return(NULL); } ctxt->start = ctxt->state; ctxt->end = NULL;
ctxt->start->type = XML_REGEXP_START_STATE; ctxt->flags = 0;
return(ctxt);}
/** * xmlFreeAutomata: * @am: an automata * * Free an automata */voidxmlFreeAutomata(xmlAutomataPtr am) { if (am == NULL) return; xmlRegFreeParserCtxt(am);}
/** * xmlAutomataSetFlags: * @am: an automata * @flags: a set of internal flags * * Set some flags on the automata */voidxmlAutomataSetFlags(xmlAutomataPtr am, int flags) { if (am == NULL) return; am->flags |= flags;}
/** * xmlAutomataGetInitState: * @am: an automata * * Initial state lookup * * Returns the initial state of the automata */xmlAutomataStatePtrxmlAutomataGetInitState(xmlAutomataPtr am) { if (am == NULL) return(NULL); return(am->start);}
/** * xmlAutomataSetFinalState: * @am: an automata * @state: a state in this automata * * Makes that state a final state * * Returns 0 or -1 in case of error */intxmlAutomataSetFinalState(xmlAutomataPtr am, xmlAutomataStatePtr state) { if ((am == NULL) || (state == NULL)) return(-1); state->type = XML_REGEXP_FINAL_STATE; return(0);}
/** * xmlAutomataNewTransition: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @token: the input string associated to that transition * @data: data passed to the callback function if the transition is activated * * If @to is NULL, this creates first a new target state in the automata * and then adds a transition from the @from state to the target state * activated by the value of @token * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewTransition(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, const xmlChar *token, void *data) { xmlRegAtomPtr atom;
if ((am == NULL) || (from == NULL) || (token == NULL)) return(NULL); atom = xmlRegNewAtom(am, XML_REGEXP_STRING); if (atom == NULL) return(NULL); atom->data = data; atom->valuep = xmlStrdup(token);
if (xmlFAGenerateTransitions(am, from, to, atom) < 0) { xmlRegFreeAtom(atom); return(NULL); } if (to == NULL) return(am->state); return(to);}
/** * xmlAutomataNewTransition2: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @token: the first input string associated to that transition * @token2: the second input string associated to that transition * @data: data passed to the callback function if the transition is activated * * If @to is NULL, this creates first a new target state in the automata * and then adds a transition from the @from state to the target state * activated by the value of @token * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewTransition2(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, const xmlChar *token, const xmlChar *token2, void *data) { xmlRegAtomPtr atom;
if ((am == NULL) || (from == NULL) || (token == NULL)) return(NULL); atom = xmlRegNewAtom(am, XML_REGEXP_STRING); if (atom == NULL) return(NULL); atom->data = data; if ((token2 == NULL) || (*token2 == 0)) { atom->valuep = xmlStrdup(token); } else { int lenn, lenp; xmlChar *str;
lenn = strlen((char *) token2); lenp = strlen((char *) token);
str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2); if (str == NULL) { xmlRegFreeAtom(atom); return(NULL); } memcpy(&str[0], token, lenp); str[lenp] = '|'; memcpy(&str[lenp + 1], token2, lenn); str[lenn + lenp + 1] = 0;
atom->valuep = str; }
if (xmlFAGenerateTransitions(am, from, to, atom) < 0) { xmlRegFreeAtom(atom); return(NULL); } if (to == NULL) return(am->state); return(to);}
/** * xmlAutomataNewNegTrans: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @token: the first input string associated to that transition * @token2: the second input string associated to that transition * @data: data passed to the callback function if the transition is activated * * If @to is NULL, this creates first a new target state in the automata * and then adds a transition from the @from state to the target state * activated by any value except (@token,@token2) * Note that if @token2 is not NULL, then (X, NULL) won't match to follow # the semantic of XSD ##other * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewNegTrans(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, const xmlChar *token, const xmlChar *token2, void *data) { xmlRegAtomPtr atom; xmlChar err_msg[200];
if ((am == NULL) || (from == NULL) || (token == NULL)) return(NULL); atom = xmlRegNewAtom(am, XML_REGEXP_STRING); if (atom == NULL) return(NULL); atom->data = data; atom->neg = 1; if ((token2 == NULL) || (*token2 == 0)) { atom->valuep = xmlStrdup(token); } else { int lenn, lenp; xmlChar *str;
lenn = strlen((char *) token2); lenp = strlen((char *) token);
str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2); if (str == NULL) { xmlRegFreeAtom(atom); return(NULL); } memcpy(&str[0], token, lenp); str[lenp] = '|'; memcpy(&str[lenp + 1], token2, lenn); str[lenn + lenp + 1] = 0;
atom->valuep = str; } snprintf((char *) err_msg, 199, "not %s", (const char *) atom->valuep); err_msg[199] = 0; atom->valuep2 = xmlStrdup(err_msg);
if (xmlFAGenerateTransitions(am, from, to, atom) < 0) { xmlRegFreeAtom(atom); return(NULL); } am->negs++; if (to == NULL) return(am->state); return(to);}
/** * xmlAutomataNewCountTrans2: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @token: the input string associated to that transition * @token2: the second input string associated to that transition * @min: the minimum successive occurrences of token * @max: the maximum successive occurrences of token * @data: data associated to the transition * * If @to is NULL, this creates first a new target state in the automata * and then adds a transition from the @from state to the target state * activated by a succession of input of value @token and @token2 and * whose number is between @min and @max * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewCountTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, const xmlChar *token, const xmlChar *token2, int min, int max, void *data) { xmlRegAtomPtr atom; int counter;
if ((am == NULL) || (from == NULL) || (token == NULL)) return(NULL); if (min < 0) return(NULL); if ((max < min) || (max < 1)) return(NULL); atom = xmlRegNewAtom(am, XML_REGEXP_STRING); if (atom == NULL) return(NULL); if ((token2 == NULL) || (*token2 == 0)) { atom->valuep = xmlStrdup(token); if (atom->valuep == NULL) goto error; } else { int lenn, lenp; xmlChar *str;
lenn = strlen((char *) token2); lenp = strlen((char *) token);
str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2); if (str == NULL) goto error; memcpy(&str[0], token, lenp); str[lenp] = '|'; memcpy(&str[lenp + 1], token2, lenn); str[lenn + lenp + 1] = 0;
atom->valuep = str; } atom->data = data; if (min == 0) atom->min = 1; else atom->min = min; atom->max = max;
/* * associate a counter to the transition. */ counter = xmlRegGetCounter(am); if (counter < 0) goto error; am->counters[counter].min = min; am->counters[counter].max = max;
/* xmlFAGenerateTransitions(am, from, to, atom); */ if (to == NULL) { to = xmlRegStatePush(am); if (to == NULL) goto error; } xmlRegStateAddTrans(am, from, atom, to, counter, -1); if (xmlRegAtomPush(am, atom) < 0) goto error; am->state = to;
if (to == NULL) to = am->state; if (to == NULL) return(NULL); if (min == 0) xmlFAGenerateEpsilonTransition(am, from, to); return(to);
error: xmlRegFreeAtom(atom); return(NULL);}
/** * xmlAutomataNewCountTrans: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @token: the input string associated to that transition * @min: the minimum successive occurrences of token * @max: the maximum successive occurrences of token * @data: data associated to the transition * * If @to is NULL, this creates first a new target state in the automata * and then adds a transition from the @from state to the target state * activated by a succession of input of value @token and whose number * is between @min and @max * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewCountTrans(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, const xmlChar *token, int min, int max, void *data) { xmlRegAtomPtr atom; int counter;
if ((am == NULL) || (from == NULL) || (token == NULL)) return(NULL); if (min < 0) return(NULL); if ((max < min) || (max < 1)) return(NULL); atom = xmlRegNewAtom(am, XML_REGEXP_STRING); if (atom == NULL) return(NULL); atom->valuep = xmlStrdup(token); if (atom->valuep == NULL) goto error; atom->data = data; if (min == 0) atom->min = 1; else atom->min = min; atom->max = max;
/* * associate a counter to the transition. */ counter = xmlRegGetCounter(am); if (counter < 0) goto error; am->counters[counter].min = min; am->counters[counter].max = max;
/* xmlFAGenerateTransitions(am, from, to, atom); */ if (to == NULL) { to = xmlRegStatePush(am); if (to == NULL) goto error; } xmlRegStateAddTrans(am, from, atom, to, counter, -1); if (xmlRegAtomPush(am, atom) < 0) goto error; am->state = to;
if (to == NULL) to = am->state; if (to == NULL) return(NULL); if (min == 0) xmlFAGenerateEpsilonTransition(am, from, to); return(to);
error: xmlRegFreeAtom(atom); return(NULL);}
/** * xmlAutomataNewOnceTrans2: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @token: the input string associated to that transition * @token2: the second input string associated to that transition * @min: the minimum successive occurrences of token * @max: the maximum successive occurrences of token * @data: data associated to the transition * * If @to is NULL, this creates first a new target state in the automata * and then adds a transition from the @from state to the target state * activated by a succession of input of value @token and @token2 and whose * number is between @min and @max, moreover that transition can only be * crossed once. * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewOnceTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, const xmlChar *token, const xmlChar *token2, int min, int max, void *data) { xmlRegAtomPtr atom; int counter;
if ((am == NULL) || (from == NULL) || (token == NULL)) return(NULL); if (min < 1) return(NULL); if (max < min) return(NULL); atom = xmlRegNewAtom(am, XML_REGEXP_STRING); if (atom == NULL) return(NULL); if ((token2 == NULL) || (*token2 == 0)) { atom->valuep = xmlStrdup(token); if (atom->valuep == NULL) goto error; } else { int lenn, lenp; xmlChar *str;
lenn = strlen((char *) token2); lenp = strlen((char *) token);
str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2); if (str == NULL) goto error; memcpy(&str[0], token, lenp); str[lenp] = '|'; memcpy(&str[lenp + 1], token2, lenn); str[lenn + lenp + 1] = 0;
atom->valuep = str; } atom->data = data; atom->quant = XML_REGEXP_QUANT_ONCEONLY; atom->min = min; atom->max = max; /* * associate a counter to the transition. */ counter = xmlRegGetCounter(am); if (counter < 0) goto error; am->counters[counter].min = 1; am->counters[counter].max = 1;
/* xmlFAGenerateTransitions(am, from, to, atom); */ if (to == NULL) { to = xmlRegStatePush(am); if (to == NULL) goto error; } xmlRegStateAddTrans(am, from, atom, to, counter, -1); if (xmlRegAtomPush(am, atom) < 0) goto error; am->state = to; return(to);
error: xmlRegFreeAtom(atom); return(NULL);}
/** * xmlAutomataNewOnceTrans: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @token: the input string associated to that transition * @min: the minimum successive occurrences of token * @max: the maximum successive occurrences of token * @data: data associated to the transition * * If @to is NULL, this creates first a new target state in the automata * and then adds a transition from the @from state to the target state * activated by a succession of input of value @token and whose number * is between @min and @max, moreover that transition can only be crossed * once. * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewOnceTrans(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, const xmlChar *token, int min, int max, void *data) { xmlRegAtomPtr atom; int counter;
if ((am == NULL) || (from == NULL) || (token == NULL)) return(NULL); if (min < 1) return(NULL); if (max < min) return(NULL); atom = xmlRegNewAtom(am, XML_REGEXP_STRING); if (atom == NULL) return(NULL); atom->valuep = xmlStrdup(token); atom->data = data; atom->quant = XML_REGEXP_QUANT_ONCEONLY; atom->min = min; atom->max = max; /* * associate a counter to the transition. */ counter = xmlRegGetCounter(am); if (counter < 0) goto error; am->counters[counter].min = 1; am->counters[counter].max = 1;
/* xmlFAGenerateTransitions(am, from, to, atom); */ if (to == NULL) { to = xmlRegStatePush(am); if (to == NULL) goto error; } xmlRegStateAddTrans(am, from, atom, to, counter, -1); if (xmlRegAtomPush(am, atom) < 0) goto error; am->state = to; return(to);
error: xmlRegFreeAtom(atom); return(NULL);}
/** * xmlAutomataNewState: * @am: an automata * * Create a new disconnected state in the automata * * Returns the new state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewState(xmlAutomataPtr am) { if (am == NULL) return(NULL); return(xmlRegStatePush(am));}
/** * xmlAutomataNewEpsilon: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * * If @to is NULL, this creates first a new target state in the automata * and then adds an epsilon transition from the @from state to the * target state * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewEpsilon(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to) { if ((am == NULL) || (from == NULL)) return(NULL); xmlFAGenerateEpsilonTransition(am, from, to); if (to == NULL) return(am->state); return(to);}
/** * xmlAutomataNewAllTrans: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @lax: allow to transition if not all all transitions have been activated * * If @to is NULL, this creates first a new target state in the automata * and then adds a an ALL transition from the @from state to the * target state. That transition is an epsilon transition allowed only when * all transitions from the @from node have been activated. * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewAllTrans(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, int lax) { if ((am == NULL) || (from == NULL)) return(NULL); xmlFAGenerateAllTransition(am, from, to, lax); if (to == NULL) return(am->state); return(to);}
/** * xmlAutomataNewCounter: * @am: an automata * @min: the minimal value on the counter * @max: the maximal value on the counter * * Create a new counter * * Returns the counter number or -1 in case of error */intxmlAutomataNewCounter(xmlAutomataPtr am, int min, int max) { int ret;
if (am == NULL) return(-1);
ret = xmlRegGetCounter(am); if (ret < 0) return(-1); am->counters[ret].min = min; am->counters[ret].max = max; return(ret);}
/** * xmlAutomataNewCountedTrans: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @counter: the counter associated to that transition * * If @to is NULL, this creates first a new target state in the automata * and then adds an epsilon transition from the @from state to the target state * which will increment the counter provided * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewCountedTrans(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, int counter) { if ((am == NULL) || (from == NULL) || (counter < 0)) return(NULL); xmlFAGenerateCountedEpsilonTransition(am, from, to, counter); if (to == NULL) return(am->state); return(to);}
/** * xmlAutomataNewCounterTrans: * @am: an automata * @from: the starting point of the transition * @to: the target point of the transition or NULL * @counter: the counter associated to that transition * * If @to is NULL, this creates first a new target state in the automata * and then adds an epsilon transition from the @from state to the target state * which will be allowed only if the counter is within the right range. * * Returns the target state or NULL in case of error */xmlAutomataStatePtrxmlAutomataNewCounterTrans(xmlAutomataPtr am, xmlAutomataStatePtr from, xmlAutomataStatePtr to, int counter) { if ((am == NULL) || (from == NULL) || (counter < 0)) return(NULL); xmlFAGenerateCountedTransition(am, from, to, counter); if (to == NULL) return(am->state); return(to);}
/** * xmlAutomataCompile: * @am: an automata * * Compile the automata into a Reg Exp ready for being executed. * The automata should be free after this point. * * Returns the compiled regexp or NULL in case of error */xmlRegexpPtrxmlAutomataCompile(xmlAutomataPtr am) { xmlRegexpPtr ret;
if ((am == NULL) || (am->error != 0)) return(NULL); xmlFAEliminateEpsilonTransitions(am); /* xmlFAComputesDeterminism(am); */ ret = xmlRegEpxFromParse(am);
return(ret);}
/** * xmlAutomataIsDeterminist: * @am: an automata * * Checks if an automata is determinist. * * Returns 1 if true, 0 if not, and -1 in case of error */intxmlAutomataIsDeterminist(xmlAutomataPtr am) { int ret;
if (am == NULL) return(-1);
ret = xmlFAComputesDeterminism(am); return(ret);}#endif /* LIBXML_AUTOMATA_ENABLED */
#ifdef LIBXML_EXPR_ENABLED/************************************************************************ * * * Formal Expression handling code * * * ************************************************************************//************************************************************************ * * * Expression handling context * * * ************************************************************************/
struct _xmlExpCtxt { xmlDictPtr dict; xmlExpNodePtr *table; int size; int nbElems; int nb_nodes; int maxNodes; const char *expr; const char *cur; int nb_cons; int tabSize;};
/** * xmlExpNewCtxt: * @maxNodes: the maximum number of nodes * @dict: optional dictionary to use internally * * Creates a new context for manipulating expressions * * Returns the context or NULL in case of error */xmlExpCtxtPtrxmlExpNewCtxt(int maxNodes, xmlDictPtr dict) { xmlExpCtxtPtr ret; int size = 256;
if (maxNodes <= 4096) maxNodes = 4096;
ret = (xmlExpCtxtPtr) xmlMalloc(sizeof(xmlExpCtxt)); if (ret == NULL) return(NULL); memset(ret, 0, sizeof(xmlExpCtxt)); ret->size = size; ret->nbElems = 0; ret->maxNodes = maxNodes; ret->table = xmlMalloc(size * sizeof(xmlExpNodePtr)); if (ret->table == NULL) { xmlFree(ret); return(NULL); } memset(ret->table, 0, size * sizeof(xmlExpNodePtr)); if (dict == NULL) { ret->dict = xmlDictCreate(); if (ret->dict == NULL) { xmlFree(ret->table); xmlFree(ret); return(NULL); } } else { ret->dict = dict; xmlDictReference(ret->dict); } return(ret);}
/** * xmlExpFreeCtxt: * @ctxt: an expression context * * Free an expression context */voidxmlExpFreeCtxt(xmlExpCtxtPtr ctxt) { if (ctxt == NULL) return; xmlDictFree(ctxt->dict); if (ctxt->table != NULL) xmlFree(ctxt->table); xmlFree(ctxt);}
/************************************************************************ * * * Structure associated to an expression node * * * ************************************************************************/#define MAX_NODES 10000
/* * TODO: * - Wildcards * - public API for creation * * Started * - regression testing * * Done * - split into module and test tool * - memleaks */
typedef enum { XML_EXP_NILABLE = (1 << 0)} xmlExpNodeInfo;
#define IS_NILLABLE(node) ((node)->info & XML_EXP_NILABLE)
struct _xmlExpNode { unsigned char type;/* xmlExpNodeType */ unsigned char info;/* OR of xmlExpNodeInfo */ unsigned short key; /* the hash key */ unsigned int ref; /* The number of references */ int c_max; /* the maximum length it can consume */ xmlExpNodePtr exp_left; xmlExpNodePtr next;/* the next node in the hash table or free list */ union { struct { int f_min; int f_max; } count; struct { xmlExpNodePtr f_right; } children; const xmlChar *f_str; } field;};
#define exp_min field.count.f_min#define exp_max field.count.f_max/* #define exp_left field.children.f_left */#define exp_right field.children.f_right#define exp_str field.f_str
static xmlExpNodePtr xmlExpNewNode(xmlExpCtxtPtr ctxt, xmlExpNodeType type);static xmlExpNode forbiddenExpNode = { XML_EXP_FORBID, 0, 0, 0, 0, NULL, NULL, {{ 0, 0}}};xmlExpNodePtr forbiddenExp = &forbiddenExpNode;static xmlExpNode emptyExpNode = { XML_EXP_EMPTY, 1, 0, 0, 0, NULL, NULL, {{ 0, 0}}};xmlExpNodePtr emptyExp = &emptyExpNode;
/************************************************************************ * * * The custom hash table for unicity and canonicalization * * of sub-expressions pointers * * * ************************************************************************//* * xmlExpHashNameComputeKey: * Calculate the hash key for a token */static unsigned shortxmlExpHashNameComputeKey(const xmlChar *name) { unsigned short value = 0L; char ch;
if (name != NULL) { value += 30 * (*name); while ((ch = *name++) != 0) { value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch); } } return (value);}
/* * xmlExpHashComputeKey: * Calculate the hash key for a compound expression */static unsigned shortxmlExpHashComputeKey(xmlExpNodeType type, xmlExpNodePtr left, xmlExpNodePtr right) { unsigned long value; unsigned short ret;
switch (type) { case XML_EXP_SEQ: value = left->key; value += right->key; value *= 3; ret = (unsigned short) value; break; case XML_EXP_OR: value = left->key; value += right->key; value *= 7; ret = (unsigned short) value; break; case XML_EXP_COUNT: value = left->key; value += right->key; ret = (unsigned short) value; break; default: ret = 0; } return(ret);}
static xmlExpNodePtrxmlExpNewNode(xmlExpCtxtPtr ctxt, xmlExpNodeType type) { xmlExpNodePtr ret;
if (ctxt->nb_nodes >= MAX_NODES) return(NULL); ret = (xmlExpNodePtr) xmlMalloc(sizeof(xmlExpNode)); if (ret == NULL) return(NULL); memset(ret, 0, sizeof(xmlExpNode)); ret->type = type; ret->next = NULL; ctxt->nb_nodes++; ctxt->nb_cons++; return(ret);}
/** * xmlExpHashGetEntry: * @table: the hash table * * Get the unique entry from the hash table. The entry is created if * needed. @left and @right are consumed, i.e. their ref count will * be decremented by the operation. * * Returns the pointer or NULL in case of error */static xmlExpNodePtrxmlExpHashGetEntry(xmlExpCtxtPtr ctxt, xmlExpNodeType type, xmlExpNodePtr left, xmlExpNodePtr right, const xmlChar *name, int min, int max) { unsigned short kbase, key; xmlExpNodePtr entry; xmlExpNodePtr insert;
if (ctxt == NULL) return(NULL);
/* * Check for duplicate and insertion location. */ if (type == XML_EXP_ATOM) { kbase = xmlExpHashNameComputeKey(name); } else if (type == XML_EXP_COUNT) { /* COUNT reduction rule 1 */ /* a{1} -> a */ if (min == max) { if (min == 1) { return(left); } if (min == 0) { xmlExpFree(ctxt, left); return(emptyExp); } } if (min < 0) { xmlExpFree(ctxt, left); return(forbiddenExp); } if (max == -1) kbase = min + 79; else kbase = max - min; kbase += left->key; } else if (type == XML_EXP_OR) { /* Forbid reduction rules */ if (left->type == XML_EXP_FORBID) { xmlExpFree(ctxt, left); return(right); } if (right->type == XML_EXP_FORBID) { xmlExpFree(ctxt, right); return(left); }
/* OR reduction rule 1 */ /* a | a reduced to a */ if (left == right) { xmlExpFree(ctxt, right); return(left); } /* OR canonicalization rule 1 */ /* linearize (a | b) | c into a | (b | c) */ if ((left->type == XML_EXP_OR) && (right->type != XML_EXP_OR)) { xmlExpNodePtr tmp = left; left = right; right = tmp; } /* OR reduction rule 2 */ /* a | (a | b) and b | (a | b) are reduced to a | b */ if (right->type == XML_EXP_OR) { if ((left == right->exp_left) || (left == right->exp_right)) { xmlExpFree(ctxt, left); return(right); } } /* OR canonicalization rule 2 */ /* linearize (a | b) | c into a | (b | c) */ if (left->type == XML_EXP_OR) { xmlExpNodePtr tmp;
/* OR canonicalization rule 2 */ if ((left->exp_right->type != XML_EXP_OR) && (left->exp_right->key < left->exp_left->key)) { tmp = left->exp_right; left->exp_right = left->exp_left; left->exp_left = tmp; } left->exp_right->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left->exp_right, right, NULL, 0, 0); left->exp_left->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left->exp_left, tmp, NULL, 0, 0);
xmlExpFree(ctxt, left); return(tmp); } if (right->type == XML_EXP_OR) { /* Ordering in the tree */ /* C | (A | B) -> A | (B | C) */ if (left->key > right->exp_right->key) { xmlExpNodePtr tmp; right->exp_right->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_right, left, NULL, 0, 0); right->exp_left->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_left, tmp, NULL, 0, 0); xmlExpFree(ctxt, right); return(tmp); } /* Ordering in the tree */ /* B | (A | C) -> A | (B | C) */ if (left->key > right->exp_left->key) { xmlExpNodePtr tmp; right->exp_right->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left, right->exp_right, NULL, 0, 0); right->exp_left->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_left, tmp, NULL, 0, 0); xmlExpFree(ctxt, right); return(tmp); } } /* we know both types are != XML_EXP_OR here */ else if (left->key > right->key) { xmlExpNodePtr tmp = left; left = right; right = tmp; } kbase = xmlExpHashComputeKey(type, left, right); } else if (type == XML_EXP_SEQ) { /* Forbid reduction rules */ if (left->type == XML_EXP_FORBID) { xmlExpFree(ctxt, right); return(left); } if (right->type == XML_EXP_FORBID) { xmlExpFree(ctxt, left); return(right); } /* Empty reduction rules */ if (right->type == XML_EXP_EMPTY) { return(left); } if (left->type == XML_EXP_EMPTY) { return(right); } kbase = xmlExpHashComputeKey(type, left, right); } else return(NULL);
key = kbase % ctxt->size; if (ctxt->table[key] != NULL) { for (insert = ctxt->table[key]; insert != NULL; insert = insert->next) { if ((insert->key == kbase) && (insert->type == type)) { if (type == XML_EXP_ATOM) { if (name == insert->exp_str) { insert->ref++; return(insert); } } else if (type == XML_EXP_COUNT) { if ((insert->exp_min == min) && (insert->exp_max == max) && (insert->exp_left == left)) { insert->ref++; left->ref--; return(insert); } } else if ((insert->exp_left == left) && (insert->exp_right == right)) { insert->ref++; left->ref--; right->ref--; return(insert); } } } }
entry = xmlExpNewNode(ctxt, type); if (entry == NULL) return(NULL); entry->key = kbase; if (type == XML_EXP_ATOM) { entry->exp_str = name; entry->c_max = 1; } else if (type == XML_EXP_COUNT) { entry->exp_min = min; entry->exp_max = max; entry->exp_left = left; if ((min == 0) || (IS_NILLABLE(left))) entry->info |= XML_EXP_NILABLE; if (max < 0) entry->c_max = -1; else entry->c_max = max * entry->exp_left->c_max; } else { entry->exp_left = left; entry->exp_right = right; if (type == XML_EXP_OR) { if ((IS_NILLABLE(left)) || (IS_NILLABLE(right))) entry->info |= XML_EXP_NILABLE; if ((entry->exp_left->c_max == -1) || (entry->exp_right->c_max == -1)) entry->c_max = -1; else if (entry->exp_left->c_max > entry->exp_right->c_max) entry->c_max = entry->exp_left->c_max; else entry->c_max = entry->exp_right->c_max; } else { if ((IS_NILLABLE(left)) && (IS_NILLABLE(right))) entry->info |= XML_EXP_NILABLE; if ((entry->exp_left->c_max == -1) || (entry->exp_right->c_max == -1)) entry->c_max = -1; else entry->c_max = entry->exp_left->c_max + entry->exp_right->c_max; } } entry->ref = 1; if (ctxt->table[key] != NULL) entry->next = ctxt->table[key];
ctxt->table[key] = entry; ctxt->nbElems++;
return(entry);}
/** * xmlExpFree: * @ctxt: the expression context * @exp: the expression * * Dereference the expression */voidxmlExpFree(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp) { if ((exp == NULL) || (exp == forbiddenExp) || (exp == emptyExp)) return; exp->ref--; if (exp->ref == 0) { unsigned short key;
/* Unlink it first from the hash table */ key = exp->key % ctxt->size; if (ctxt->table[key] == exp) { ctxt->table[key] = exp->next; } else { xmlExpNodePtr tmp;
tmp = ctxt->table[key]; while (tmp != NULL) { if (tmp->next == exp) { tmp->next = exp->next; break; } tmp = tmp->next; } }
if ((exp->type == XML_EXP_SEQ) || (exp->type == XML_EXP_OR)) { xmlExpFree(ctxt, exp->exp_left); xmlExpFree(ctxt, exp->exp_right); } else if (exp->type == XML_EXP_COUNT) { xmlExpFree(ctxt, exp->exp_left); } xmlFree(exp); ctxt->nb_nodes--; }}
/** * xmlExpRef: * @exp: the expression * * Increase the reference count of the expression */voidxmlExpRef(xmlExpNodePtr exp) { if (exp != NULL) exp->ref++;}
/** * xmlExpNewAtom: * @ctxt: the expression context * @name: the atom name * @len: the atom name length in byte (or -1); * * Get the atom associated to this name from that context * * Returns the node or NULL in case of error */xmlExpNodePtrxmlExpNewAtom(xmlExpCtxtPtr ctxt, const xmlChar *name, int len) { if ((ctxt == NULL) || (name == NULL)) return(NULL); name = xmlDictLookup(ctxt->dict, name, len); if (name == NULL) return(NULL); return(xmlExpHashGetEntry(ctxt, XML_EXP_ATOM, NULL, NULL, name, 0, 0));}
/** * xmlExpNewOr: * @ctxt: the expression context * @left: left expression * @right: right expression * * Get the atom associated to the choice @left | @right * Note that @left and @right are consumed in the operation, to keep * an handle on them use xmlExpRef() and use xmlExpFree() to release them, * this is true even in case of failure (unless ctxt == NULL). * * Returns the node or NULL in case of error */xmlExpNodePtrxmlExpNewOr(xmlExpCtxtPtr ctxt, xmlExpNodePtr left, xmlExpNodePtr right) { if (ctxt == NULL) return(NULL); if ((left == NULL) || (right == NULL)) { xmlExpFree(ctxt, left); xmlExpFree(ctxt, right); return(NULL); } return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, left, right, NULL, 0, 0));}
/** * xmlExpNewSeq: * @ctxt: the expression context * @left: left expression * @right: right expression * * Get the atom associated to the sequence @left , @right * Note that @left and @right are consumed in the operation, to keep * an handle on them use xmlExpRef() and use xmlExpFree() to release them, * this is true even in case of failure (unless ctxt == NULL). * * Returns the node or NULL in case of error */xmlExpNodePtrxmlExpNewSeq(xmlExpCtxtPtr ctxt, xmlExpNodePtr left, xmlExpNodePtr right) { if (ctxt == NULL) return(NULL); if ((left == NULL) || (right == NULL)) { xmlExpFree(ctxt, left); xmlExpFree(ctxt, right); return(NULL); } return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, left, right, NULL, 0, 0));}
/** * xmlExpNewRange: * @ctxt: the expression context * @subset: the expression to be repeated * @min: the lower bound for the repetition * @max: the upper bound for the repetition, -1 means infinite * * Get the atom associated to the range (@subset){@min, @max} * Note that @subset is consumed in the operation, to keep * an handle on it use xmlExpRef() and use xmlExpFree() to release it, * this is true even in case of failure (unless ctxt == NULL). * * Returns the node or NULL in case of error */xmlExpNodePtrxmlExpNewRange(xmlExpCtxtPtr ctxt, xmlExpNodePtr subset, int min, int max) { if (ctxt == NULL) return(NULL); if ((subset == NULL) || (min < 0) || (max < -1) || ((max >= 0) && (min > max))) { xmlExpFree(ctxt, subset); return(NULL); } return(xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, subset, NULL, NULL, min, max));}
/************************************************************************ * * * Public API for operations on expressions * * * ************************************************************************/
static intxmlExpGetLanguageInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar**list, int len, int nb) { int tmp, tmp2;tail: switch (exp->type) { case XML_EXP_EMPTY: return(0); case XML_EXP_ATOM: for (tmp = 0;tmp < nb;tmp++) if (list[tmp] == exp->exp_str) return(0); if (nb >= len) return(-2); list[nb] = exp->exp_str; return(1); case XML_EXP_COUNT: exp = exp->exp_left; goto tail; case XML_EXP_SEQ: case XML_EXP_OR: tmp = xmlExpGetLanguageInt(ctxt, exp->exp_left, list, len, nb); if (tmp < 0) return(tmp); tmp2 = xmlExpGetLanguageInt(ctxt, exp->exp_right, list, len, nb + tmp); if (tmp2 < 0) return(tmp2); return(tmp + tmp2); } return(-1);}
/** * xmlExpGetLanguage: * @ctxt: the expression context * @exp: the expression * @langList: where to store the tokens * @len: the allocated length of @list * * Find all the strings used in @exp and store them in @list * * Returns the number of unique strings found, -1 in case of errors and * -2 if there is more than @len strings */intxmlExpGetLanguage(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar**langList, int len) { if ((ctxt == NULL) || (exp == NULL) || (langList == NULL) || (len <= 0)) return(-1); return(xmlExpGetLanguageInt(ctxt, exp, langList, len, 0));}
static intxmlExpGetStartInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar**list, int len, int nb) { int tmp, tmp2;tail: switch (exp->type) { case XML_EXP_FORBID: return(0); case XML_EXP_EMPTY: return(0); case XML_EXP_ATOM: for (tmp = 0;tmp < nb;tmp++) if (list[tmp] == exp->exp_str) return(0); if (nb >= len) return(-2); list[nb] = exp->exp_str; return(1); case XML_EXP_COUNT: exp = exp->exp_left; goto tail; case XML_EXP_SEQ: tmp = xmlExpGetStartInt(ctxt, exp->exp_left, list, len, nb); if (tmp < 0) return(tmp); if (IS_NILLABLE(exp->exp_left)) { tmp2 = xmlExpGetStartInt(ctxt, exp->exp_right, list, len, nb + tmp); if (tmp2 < 0) return(tmp2); tmp += tmp2; } return(tmp); case XML_EXP_OR: tmp = xmlExpGetStartInt(ctxt, exp->exp_left, list, len, nb); if (tmp < 0) return(tmp); tmp2 = xmlExpGetStartInt(ctxt, exp->exp_right, list, len, nb + tmp); if (tmp2 < 0) return(tmp2); return(tmp + tmp2); } return(-1);}
/** * xmlExpGetStart: * @ctxt: the expression context * @exp: the expression * @tokList: where to store the tokens * @len: the allocated length of @list * * Find all the strings that appears at the start of the languages * accepted by @exp and store them in @list. E.g. for (a, b) | c * it will return the list [a, c] * * Returns the number of unique strings found, -1 in case of errors and * -2 if there is more than @len strings */intxmlExpGetStart(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar**tokList, int len) { if ((ctxt == NULL) || (exp == NULL) || (tokList == NULL) || (len <= 0)) return(-1); return(xmlExpGetStartInt(ctxt, exp, tokList, len, 0));}
/** * xmlExpIsNillable: * @exp: the expression * * Finds if the expression is nillable, i.e. if it accepts the empty sequence * * Returns 1 if nillable, 0 if not and -1 in case of error */intxmlExpIsNillable(xmlExpNodePtr exp) { if (exp == NULL) return(-1); return(IS_NILLABLE(exp) != 0);}
static xmlExpNodePtrxmlExpStringDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar *str){ xmlExpNodePtr ret;
switch (exp->type) { case XML_EXP_EMPTY: return(forbiddenExp); case XML_EXP_FORBID: return(forbiddenExp); case XML_EXP_ATOM: if (exp->exp_str == str) { ret = emptyExp; } else { /* TODO wildcards here */ ret = forbiddenExp; } return(ret); case XML_EXP_OR: { xmlExpNodePtr tmp;
tmp = xmlExpStringDeriveInt(ctxt, exp->exp_left, str); if (tmp == NULL) { return(NULL); } ret = xmlExpStringDeriveInt(ctxt, exp->exp_right, str); if (ret == NULL) { xmlExpFree(ctxt, tmp); return(NULL); } ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, tmp, ret, NULL, 0, 0); return(ret); } case XML_EXP_SEQ: ret = xmlExpStringDeriveInt(ctxt, exp->exp_left, str); if (ret == NULL) { return(NULL); } else if (ret == forbiddenExp) { if (IS_NILLABLE(exp->exp_left)) { ret = xmlExpStringDeriveInt(ctxt, exp->exp_right, str); } } else { exp->exp_right->ref++; ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, exp->exp_right, NULL, 0, 0); } return(ret); case XML_EXP_COUNT: { int min, max; xmlExpNodePtr tmp;
if (exp->exp_max == 0) return(forbiddenExp); ret = xmlExpStringDeriveInt(ctxt, exp->exp_left, str); if (ret == NULL) return(NULL); if (ret == forbiddenExp) { return(ret); } if (exp->exp_max == 1) return(ret); if (exp->exp_max < 0) /* unbounded */ max = -1; else max = exp->exp_max - 1; if (exp->exp_min > 0) min = exp->exp_min - 1; else min = 0; exp->exp_left->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left, NULL, NULL, min, max); if (ret == emptyExp) { return(tmp); } return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, tmp, NULL, 0, 0)); } } return(NULL);}
/** * xmlExpStringDerive: * @ctxt: the expression context * @exp: the expression * @str: the string * @len: the string len in bytes if available * * Do one step of Brzozowski derivation of the expression @exp with * respect to the input string * * Returns the resulting expression or NULL in case of internal error */xmlExpNodePtrxmlExpStringDerive(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar *str, int len) { const xmlChar *input;
if ((exp == NULL) || (ctxt == NULL) || (str == NULL)) { return(NULL); } /* * check the string is in the dictionary, if yes use an interned * copy, otherwise we know it's not an acceptable input */ input = xmlDictExists(ctxt->dict, str, len); if (input == NULL) { return(forbiddenExp); } return(xmlExpStringDeriveInt(ctxt, exp, input));}
static intxmlExpCheckCard(xmlExpNodePtr exp, xmlExpNodePtr sub) { int ret = 1;
if (sub->c_max == -1) { if (exp->c_max != -1) ret = 0; } else if ((exp->c_max >= 0) && (exp->c_max < sub->c_max)) { ret = 0; }#if 0 if ((IS_NILLABLE(sub)) && (!IS_NILLABLE(exp))) ret = 0;#endif return(ret);}
static xmlExpNodePtr xmlExpExpDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub);/** * xmlExpDivide: * @ctxt: the expressions context * @exp: the englobing expression * @sub: the subexpression * @mult: the multiple expression * @remain: the remain from the derivation of the multiple * * Check if exp is a multiple of sub, i.e. if there is a finite number n * so that sub{n} subsume exp * * Returns the multiple value if successful, 0 if it is not a multiple * and -1 in case of internal error. */
static intxmlExpDivide(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub, xmlExpNodePtr *mult, xmlExpNodePtr *remain) { int i; xmlExpNodePtr tmp, tmp2;
if (mult != NULL) *mult = NULL; if (remain != NULL) *remain = NULL; if (exp->c_max == -1) return(0); if (IS_NILLABLE(exp) && (!IS_NILLABLE(sub))) return(0);
for (i = 1;i <= exp->c_max;i++) { sub->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, sub, NULL, NULL, i, i); if (tmp == NULL) { return(-1); } if (!xmlExpCheckCard(tmp, exp)) { xmlExpFree(ctxt, tmp); continue; } tmp2 = xmlExpExpDeriveInt(ctxt, tmp, exp); if (tmp2 == NULL) { xmlExpFree(ctxt, tmp); return(-1); } if ((tmp2 != forbiddenExp) && (IS_NILLABLE(tmp2))) { if (remain != NULL) *remain = tmp2; else xmlExpFree(ctxt, tmp2); if (mult != NULL) *mult = tmp; else xmlExpFree(ctxt, tmp); return(i); } xmlExpFree(ctxt, tmp); xmlExpFree(ctxt, tmp2); } return(0);}
/** * xmlExpExpDeriveInt: * @ctxt: the expressions context * @exp: the englobing expression * @sub: the subexpression * * Try to do a step of Brzozowski derivation but at a higher level * the input being a subexpression. * * Returns the resulting expression or NULL in case of internal error */static xmlExpNodePtrxmlExpExpDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) { xmlExpNodePtr ret, tmp, tmp2, tmp3; const xmlChar **tab; int len, i;
/* * In case of equality and if the expression can only consume a finite * amount, then the derivation is empty */ if ((exp == sub) && (exp->c_max >= 0)) { return(emptyExp); } /* * decompose sub sequence first */ if (sub->type == XML_EXP_EMPTY) { exp->ref++; return(exp); } if (sub->type == XML_EXP_SEQ) { tmp = xmlExpExpDeriveInt(ctxt, exp, sub->exp_left); if (tmp == NULL) return(NULL); if (tmp == forbiddenExp) return(tmp); ret = xmlExpExpDeriveInt(ctxt, tmp, sub->exp_right); xmlExpFree(ctxt, tmp); return(ret); } if (sub->type == XML_EXP_OR) { tmp = xmlExpExpDeriveInt(ctxt, exp, sub->exp_left); if (tmp == forbiddenExp) return(tmp); if (tmp == NULL) return(NULL); ret = xmlExpExpDeriveInt(ctxt, exp, sub->exp_right); if ((ret == NULL) || (ret == forbiddenExp)) { xmlExpFree(ctxt, tmp); return(ret); } return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, tmp, ret, NULL, 0, 0)); } if (!xmlExpCheckCard(exp, sub)) { return(forbiddenExp); } switch (exp->type) { case XML_EXP_EMPTY: if (sub == emptyExp) return(emptyExp); return(forbiddenExp); case XML_EXP_FORBID: return(forbiddenExp); case XML_EXP_ATOM: if (sub->type == XML_EXP_ATOM) { /* TODO: handle wildcards */ if (exp->exp_str == sub->exp_str) { return(emptyExp); } return(forbiddenExp); } if ((sub->type == XML_EXP_COUNT) && (sub->exp_max == 1) && (sub->exp_left->type == XML_EXP_ATOM)) { /* TODO: handle wildcards */ if (exp->exp_str == sub->exp_left->exp_str) { return(emptyExp); } return(forbiddenExp); } return(forbiddenExp); case XML_EXP_SEQ: /* try to get the sequence consumed only if possible */ if (xmlExpCheckCard(exp->exp_left, sub)) { /* See if the sequence can be consumed directly */ ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub); if ((ret != forbiddenExp) && (ret != NULL)) { /* * TODO: assumption here that we are determinist * i.e. we won't get to a nillable exp left * subset which could be matched by the right * part too. * e.g.: (a | b)+,(a | c) and 'a+,a' */ exp->exp_right->ref++; return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, exp->exp_right, NULL, 0, 0)); } } /* Try instead to decompose */ if (sub->type == XML_EXP_COUNT) { int min, max;
ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub->exp_left); if (ret == NULL) return(NULL); if (ret != forbiddenExp) { if (sub->exp_max < 0) max = -1; else max = sub->exp_max -1; if (sub->exp_min > 0) min = sub->exp_min -1; else min = 0; exp->exp_right->ref++; tmp = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, exp->exp_right, NULL, 0, 0); if (tmp == NULL) return(NULL);
sub->exp_left->ref++; tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, sub->exp_left, NULL, NULL, min, max); if (tmp2 == NULL) { xmlExpFree(ctxt, tmp); return(NULL); } ret = xmlExpExpDeriveInt(ctxt, tmp, tmp2); xmlExpFree(ctxt, tmp); xmlExpFree(ctxt, tmp2); return(ret); } } /* we made no progress on structured operations */ break; case XML_EXP_OR: ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub); if (ret == NULL) return(NULL); tmp = xmlExpExpDeriveInt(ctxt, exp->exp_right, sub); if (tmp == NULL) { xmlExpFree(ctxt, ret); return(NULL); } return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, tmp, NULL, 0, 0)); case XML_EXP_COUNT: { int min, max;
if (sub->type == XML_EXP_COUNT) { /* * Try to see if the loop is completely subsumed */ tmp = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub->exp_left); if (tmp == NULL) return(NULL); if (tmp == forbiddenExp) { int mult;
mult = xmlExpDivide(ctxt, sub->exp_left, exp->exp_left, NULL, &tmp); if (mult <= 0) { return(forbiddenExp); } if (sub->exp_max == -1) { max = -1; if (exp->exp_max == -1) { if (exp->exp_min <= sub->exp_min * mult) min = 0; else min = exp->exp_min - sub->exp_min * mult; } else { xmlExpFree(ctxt, tmp); return(forbiddenExp); } } else { if (exp->exp_max == -1) { if (exp->exp_min > sub->exp_min * mult) { max = -1; min = exp->exp_min - sub->exp_min * mult; } else { max = -1; min = 0; } } else { if (exp->exp_max < sub->exp_max * mult) { xmlExpFree(ctxt, tmp); return(forbiddenExp); } if (sub->exp_max * mult > exp->exp_min) min = 0; else min = exp->exp_min - sub->exp_max * mult; max = exp->exp_max - sub->exp_max * mult; } } } else if (!IS_NILLABLE(tmp)) { /* * TODO: loop here to try to grow if working on finite * blocks. */ xmlExpFree(ctxt, tmp); return(forbiddenExp); } else if (sub->exp_max == -1) { if (exp->exp_max == -1) { if (exp->exp_min <= sub->exp_min) { max = -1; min = 0; } else { max = -1; min = exp->exp_min - sub->exp_min; } } else if (exp->exp_min > sub->exp_min) { xmlExpFree(ctxt, tmp); return(forbiddenExp); } else { max = -1; min = 0; } } else { if (exp->exp_max == -1) { if (exp->exp_min > sub->exp_min) { max = -1; min = exp->exp_min - sub->exp_min; } else { max = -1; min = 0; } } else { if (exp->exp_max < sub->exp_max) { xmlExpFree(ctxt, tmp); return(forbiddenExp); } if (sub->exp_max > exp->exp_min) min = 0; else min = exp->exp_min - sub->exp_max; max = exp->exp_max - sub->exp_max; } } exp->exp_left->ref++; tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left, NULL, NULL, min, max); if (tmp2 == NULL) { return(NULL); } ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, tmp, tmp2, NULL, 0, 0); return(ret); } tmp = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub); if (tmp == NULL) return(NULL); if (tmp == forbiddenExp) { return(forbiddenExp); } if (exp->exp_min > 0) min = exp->exp_min - 1; else min = 0; if (exp->exp_max < 0) max = -1; else max = exp->exp_max - 1;
exp->exp_left->ref++; tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left, NULL, NULL, min, max); if (tmp2 == NULL) return(NULL); ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, tmp, tmp2, NULL, 0, 0); return(ret); } }
if (IS_NILLABLE(sub)) { if (!(IS_NILLABLE(exp))) return(forbiddenExp); else ret = emptyExp; } else ret = NULL; /* * here the structured derivation made no progress so * we use the default token based derivation to force one more step */ if (ctxt->tabSize == 0) ctxt->tabSize = 40;
tab = (const xmlChar **) xmlMalloc(ctxt->tabSize * sizeof(const xmlChar *)); if (tab == NULL) { return(NULL); }
/* * collect all the strings accepted by the subexpression on input */ len = xmlExpGetStartInt(ctxt, sub, tab, ctxt->tabSize, 0); while (len < 0) { const xmlChar **temp; temp = (const xmlChar **) xmlRealloc((xmlChar **) tab, ctxt->tabSize * 2 * sizeof(const xmlChar *)); if (temp == NULL) { xmlFree((xmlChar **) tab); return(NULL); } tab = temp; ctxt->tabSize *= 2; len = xmlExpGetStartInt(ctxt, sub, tab, ctxt->tabSize, 0); } for (i = 0;i < len;i++) { tmp = xmlExpStringDeriveInt(ctxt, exp, tab[i]); if ((tmp == NULL) || (tmp == forbiddenExp)) { xmlExpFree(ctxt, ret); xmlFree((xmlChar **) tab); return(tmp); } tmp2 = xmlExpStringDeriveInt(ctxt, sub, tab[i]); if ((tmp2 == NULL) || (tmp2 == forbiddenExp)) { xmlExpFree(ctxt, tmp); xmlExpFree(ctxt, ret); xmlFree((xmlChar **) tab); return(tmp); } tmp3 = xmlExpExpDeriveInt(ctxt, tmp, tmp2); xmlExpFree(ctxt, tmp); xmlExpFree(ctxt, tmp2);
if ((tmp3 == NULL) || (tmp3 == forbiddenExp)) { xmlExpFree(ctxt, ret); xmlFree((xmlChar **) tab); return(tmp3); }
if (ret == NULL) ret = tmp3; else { ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, tmp3, NULL, 0, 0); if (ret == NULL) { xmlFree((xmlChar **) tab); return(NULL); } } } xmlFree((xmlChar **) tab); return(ret);}
/** * xmlExpExpDerive: * @ctxt: the expressions context * @exp: the englobing expression * @sub: the subexpression * * Evaluates the expression resulting from @exp consuming a sub expression @sub * Based on algebraic derivation and sometimes direct Brzozowski derivation * it usually takes less than linear time and can handle expressions generating * infinite languages. * * Returns the resulting expression or NULL in case of internal error, the * result must be freed */xmlExpNodePtrxmlExpExpDerive(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) { if ((exp == NULL) || (ctxt == NULL) || (sub == NULL)) return(NULL);
/* * O(1) speedups */ if (IS_NILLABLE(sub) && (!IS_NILLABLE(exp))) { return(forbiddenExp); } if (xmlExpCheckCard(exp, sub) == 0) { return(forbiddenExp); } return(xmlExpExpDeriveInt(ctxt, exp, sub));}
/** * xmlExpSubsume: * @ctxt: the expressions context * @exp: the englobing expression * @sub: the subexpression * * Check whether @exp accepts all the languages accepted by @sub * the input being a subexpression. * * Returns 1 if true 0 if false and -1 in case of failure. */intxmlExpSubsume(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) { xmlExpNodePtr tmp;
if ((exp == NULL) || (ctxt == NULL) || (sub == NULL)) return(-1);
/* * TODO: speedup by checking the language of sub is a subset of the * language of exp */ /* * O(1) speedups */ if (IS_NILLABLE(sub) && (!IS_NILLABLE(exp))) { return(0); } if (xmlExpCheckCard(exp, sub) == 0) { return(0); } tmp = xmlExpExpDeriveInt(ctxt, exp, sub); if (tmp == NULL) return(-1); if (tmp == forbiddenExp) return(0); if (tmp == emptyExp) return(1); if ((tmp != NULL) && (IS_NILLABLE(tmp))) { xmlExpFree(ctxt, tmp); return(1); } xmlExpFree(ctxt, tmp); return(0);}
/************************************************************************ * * * Parsing expression * * * ************************************************************************/
static xmlExpNodePtr xmlExpParseExpr(xmlExpCtxtPtr ctxt);
#undef CUR#define CUR (*ctxt->cur)#undef NEXT#define NEXT ctxt->cur++;#undef IS_BLANK#define IS_BLANK(c) ((c == ' ') || (c == '\n') || (c == '\r') || (c == '\t'))#define SKIP_BLANKS while (IS_BLANK(*ctxt->cur)) ctxt->cur++;
static intxmlExpParseNumber(xmlExpCtxtPtr ctxt) { int ret = 0;
SKIP_BLANKS if (CUR == '*') { NEXT return(-1); } if ((CUR < '0') || (CUR > '9')) return(-1); while ((CUR >= '0') && (CUR <= '9')) { ret = ret * 10 + (CUR - '0'); NEXT } return(ret);}
static xmlExpNodePtrxmlExpParseOr(xmlExpCtxtPtr ctxt) { const char *base; xmlExpNodePtr ret; const xmlChar *val;
SKIP_BLANKS base = ctxt->cur; if (*ctxt->cur == '(') { NEXT ret = xmlExpParseExpr(ctxt); SKIP_BLANKS if (*ctxt->cur != ')') { fprintf(stderr, "unbalanced '(' : %s\n", base); xmlExpFree(ctxt, ret); return(NULL); } NEXT; SKIP_BLANKS goto parse_quantifier; } while ((CUR != 0) && (!(IS_BLANK(CUR))) && (CUR != '(') && (CUR != ')') && (CUR != '|') && (CUR != ',') && (CUR != '{') && (CUR != '*') && (CUR != '+') && (CUR != '?') && (CUR != '}')) NEXT; val = xmlDictLookup(ctxt->dict, BAD_CAST base, ctxt->cur - base); if (val == NULL) return(NULL); ret = xmlExpHashGetEntry(ctxt, XML_EXP_ATOM, NULL, NULL, val, 0, 0); if (ret == NULL) return(NULL); SKIP_BLANKSparse_quantifier: if (CUR == '{') { int min, max;
NEXT min = xmlExpParseNumber(ctxt); if (min < 0) { xmlExpFree(ctxt, ret); return(NULL); } SKIP_BLANKS if (CUR == ',') { NEXT max = xmlExpParseNumber(ctxt); SKIP_BLANKS } else max = min; if (CUR != '}') { xmlExpFree(ctxt, ret); return(NULL); } NEXT ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL, min, max); SKIP_BLANKS } else if (CUR == '?') { NEXT ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL, 0, 1); SKIP_BLANKS } else if (CUR == '+') { NEXT ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL, 1, -1); SKIP_BLANKS } else if (CUR == '*') { NEXT ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL, 0, -1); SKIP_BLANKS } return(ret);}
static xmlExpNodePtrxmlExpParseSeq(xmlExpCtxtPtr ctxt) { xmlExpNodePtr ret, right;
ret = xmlExpParseOr(ctxt); SKIP_BLANKS while (CUR == '|') { NEXT right = xmlExpParseOr(ctxt); if (right == NULL) { xmlExpFree(ctxt, ret); return(NULL); } ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, right, NULL, 0, 0); if (ret == NULL) return(NULL); } return(ret);}
static xmlExpNodePtrxmlExpParseExpr(xmlExpCtxtPtr ctxt) { xmlExpNodePtr ret, right;
ret = xmlExpParseSeq(ctxt); SKIP_BLANKS while (CUR == ',') { NEXT right = xmlExpParseSeq(ctxt); if (right == NULL) { xmlExpFree(ctxt, ret); return(NULL); } ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, right, NULL, 0, 0); if (ret == NULL) return(NULL); } return(ret);}
/** * xmlExpParse: * @ctxt: the expressions context * @expr: the 0 terminated string * * Minimal parser for regexps, it understand the following constructs * - string terminals * - choice operator | * - sequence operator , * - subexpressions (...) * - usual cardinality operators + * and ? * - finite sequences { min, max } * - infinite sequences { min, * } * There is minimal checkings made especially no checking on strings values * * Returns a new expression or NULL in case of failure */xmlExpNodePtrxmlExpParse(xmlExpCtxtPtr ctxt, const char *expr) { xmlExpNodePtr ret;
ctxt->expr = expr; ctxt->cur = expr;
ret = xmlExpParseExpr(ctxt); SKIP_BLANKS if (*ctxt->cur != 0) { xmlExpFree(ctxt, ret); return(NULL); } return(ret);}
static voidxmlExpDumpInt(xmlBufferPtr buf, xmlExpNodePtr expr, int glob) { xmlExpNodePtr c;
if (expr == NULL) return; if (glob) xmlBufferWriteChar(buf, "("); switch (expr->type) { case XML_EXP_EMPTY: xmlBufferWriteChar(buf, "empty"); break; case XML_EXP_FORBID: xmlBufferWriteChar(buf, "forbidden"); break; case XML_EXP_ATOM: xmlBufferWriteCHAR(buf, expr->exp_str); break; case XML_EXP_SEQ: c = expr->exp_left; if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR)) xmlExpDumpInt(buf, c, 1); else xmlExpDumpInt(buf, c, 0); xmlBufferWriteChar(buf, " , "); c = expr->exp_right; if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR)) xmlExpDumpInt(buf, c, 1); else xmlExpDumpInt(buf, c, 0); break; case XML_EXP_OR: c = expr->exp_left; if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR)) xmlExpDumpInt(buf, c, 1); else xmlExpDumpInt(buf, c, 0); xmlBufferWriteChar(buf, " | "); c = expr->exp_right; if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR)) xmlExpDumpInt(buf, c, 1); else xmlExpDumpInt(buf, c, 0); break; case XML_EXP_COUNT: { char rep[40];
c = expr->exp_left; if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR)) xmlExpDumpInt(buf, c, 1); else xmlExpDumpInt(buf, c, 0); if ((expr->exp_min == 0) && (expr->exp_max == 1)) { rep[0] = '?'; rep[1] = 0; } else if ((expr->exp_min == 0) && (expr->exp_max == -1)) { rep[0] = '*'; rep[1] = 0; } else if ((expr->exp_min == 1) && (expr->exp_max == -1)) { rep[0] = '+'; rep[1] = 0; } else if (expr->exp_max == expr->exp_min) { snprintf(rep, 39, "{%d}", expr->exp_min); } else if (expr->exp_max < 0) { snprintf(rep, 39, "{%d,inf}", expr->exp_min); } else { snprintf(rep, 39, "{%d,%d}", expr->exp_min, expr->exp_max); } rep[39] = 0; xmlBufferWriteChar(buf, rep); break; } default: fprintf(stderr, "Error in tree\n"); } if (glob) xmlBufferWriteChar(buf, ")");}/** * xmlExpDump: * @buf: a buffer to receive the output * @expr: the compiled expression * * Serialize the expression as compiled to the buffer */voidxmlExpDump(xmlBufferPtr buf, xmlExpNodePtr expr) { if ((buf == NULL) || (expr == NULL)) return; xmlExpDumpInt(buf, expr, 0);}
/** * xmlExpMaxToken: * @expr: a compiled expression * * Indicate the maximum number of input a expression can accept * * Returns the maximum length or -1 in case of error */intxmlExpMaxToken(xmlExpNodePtr expr) { if (expr == NULL) return(-1); return(expr->c_max);}
/** * xmlExpCtxtNbNodes: * @ctxt: an expression context * * Debugging facility provides the number of allocated nodes at a that point * * Returns the number of nodes in use or -1 in case of error */intxmlExpCtxtNbNodes(xmlExpCtxtPtr ctxt) { if (ctxt == NULL) return(-1); return(ctxt->nb_nodes);}
/** * xmlExpCtxtNbCons: * @ctxt: an expression context * * Debugging facility provides the number of allocated nodes over lifetime * * Returns the number of nodes ever allocated or -1 in case of error */intxmlExpCtxtNbCons(xmlExpCtxtPtr ctxt) { if (ctxt == NULL) return(-1); return(ctxt->nb_cons);}
#endif /* LIBXML_EXPR_ENABLED */
#endif /* LIBXML_REGEXP_ENABLED */