1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487348834893490349134923493349434953496349734983499350035013502350335043505350635073508350935103511351235133514351535163517351835193520352135223523352435253526352735283529353035313532353335343535353635373538353935403541354235433544354535463547354835493550355135523553355435553556355735583559356035613562356335643565356635673568356935703571357235733574357535763577357835793580358135823583358435853586358735883589359035913592359335943595359635973598359936003601360236033604360536063607360836093610361136123613361436153616361736183619362036213622362336243625362636273628362936303631363236333634363536363637363836393640364136423643364436453646364736483649 |
- /*##############################################################################
- HPCC SYSTEMS software Copyright (C) 2012 HPCC Systems®.
- Licensed under the Apache License, Version 2.0 (the "License");
- you may not use this file except in compliance with the License.
- You may obtain a copy of the License at
- http://www.apache.org/licenses/LICENSE-2.0
- Unless required by applicable law or agreed to in writing, software
- distributed under the License is distributed on an "AS IS" BASIS,
- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- See the License for the specific language governing permissions and
- limitations under the License.
- ############################################################################## */
- #ifndef U_OVERRIDE_CXX_ALLOCATION
- #define U_OVERRIDE_CXX_ALLOCATION 0 // Enabling this forces all allocation of ICU objects to ICU's heap, but is incompatible with jmemleak
- #endif
- #include "jliball.hpp"
- #include "junicode.hpp"
- #include "thorrparse.ipp"
- #include "thorregex.hpp"
- #include "eclrtl.hpp"
- #include "thorcommon.ipp"
- #ifdef _USE_ICU
- #include "unicode/utf.h"
- #include "unicode/uchar.h"
- #include "unicode/schriter.h"
- #include "unicode/coll.h"
- #include "unicode/ustring.h"
- using icu::UnicodeString;
- #endif
- #ifdef TRACE_REGEX
- #define MATCH traceMatch
- #else
- #define MATCH match
- #endif
- #define TRANSFORM_BEFORE_CREATE_LIMIT 4096 // Over this size, transform into a temp
- #define REGEX_VERSION 4
- #define REGEXERR_IncompatibleVersion 1000
- #define REGEXERR_MatchFailure 1001
- #define REGEXERR_IncompatibleVersion_Text "Serialized regex library is not compatible, please rebuild workunit"
- #define REGEXERR_MatchFailure_Text "Failed to match pattern: pattern too complicated (offset %d)"
- static const char * getPatternText(ThorRegexKind kind)
- {
- switch (kind)
- {
- case ThorRegexNull: return "Null";
- case ThorRegexAnyChar: return "AnyChar";
- case ThorRegexAsciiDFA: return "AsciiDFA";
- case ThorRegexUnicodeDFA: return "UnicodeDFA";
- case ThorRegexAscii: return "Ascii";
- case ThorRegexAsciiI: return "AsciiI";
- case ThorRegexAsciiSet: return "AsciiSet";
- case ThorRegexAsciiISet: return "AsciiISet";
- case ThorRegexUnicode: return "Unicode";
- case ThorRegexUnicodeI: return "UnicodeI";
- case ThorRegexUnicodeSet: return "UnicodeSet";
- case ThorRegexUnicodeISet: return "UnicodeISet";
- case ThorRegexUtf8: return "Utf8";
- case ThorRegexUtf8I: return "Utf8I";
- case ThorRegexStart: return "Start";
- case ThorRegexFinish: return "Finish";
- case ThorRegexBeginToken: return "BeginToken";
- case ThorRegexEndToken: return "EndToken";
- case ThorRegexBeginSeparator: return "BeginSeparator";
- case ThorRegexEndSeparator: return "EndSeparator";
- case ThorRegexRepeat: return "Repeat";
- case ThorRegexBeginCheck: return "BeginCheck";
- case ThorRegexCheck: return "Check";
- case ThorRegexCheckLength: return "CheckLength";
- case ThorRegexAssertNext: return "AssertNext";
- case ThorRegexAssertPrev: return "AssertPrev";
- case ThorRegexNamed: return "Named";
- case ThorRegexEndNamed: return "EndNamed";
- case ThorRegexEndNested: return "EndNested";
- case ThorRegexDone: return "Done";
- case ThorRegexRepeatInstance: return "RepeatInstance";
- case ThorRegexValidateAscAsAsc: return "ValidateAscAsAsc";
- case ThorRegexValidateUniAsAsc: return "ValidateUniAsAsc" ;
- case ThorRegexValidateUtf8AsAsc: return "ValidateUtf8AsAsc" ;
- case ThorRegexValidateAscAsUni: return "ValidateAscAsUni" ;
- case ThorRegexValidateUniAsUni: return "ValidateUniAsUni";
- case ThorRegexValidateUtf8AsUni: return "ValidateUtf8AsUni" ;
- case ThorRegexRecursive: return "Recursive";
- case ThorRegexEndRecursive: return "EndRecursive";
- case ThorRegexPenalty: return "Penalty";
- case ThorRegexRepeatAny: return "RepeatAny";
- }
- UNIMPLEMENTED;
- }
- static const char * resultText[] = { "Done", "Backtrack", "TokenBack", "Continue" };
- #ifdef TRACE_REGEX
- static unsigned patternDepth;
- #endif
- bool isAsciiMatch(unsigned code, unsigned next)
- {
- switch (code)
- {
- case RCCalnum: return isalnum(next) != 0;
- case RCCcntrl: return iscntrl(next) != 0;
- case RCClower: return islower(next) != 0;
- case RCCupper: return isupper(next) != 0;
- case RCCspace: return isspace(next) != 0;
- case RCCalpha: return isalpha(next) != 0;
- case RCCdigit: return isdigit(next) != 0;
- case RCCprint: return isprint(next) != 0;
- case RCCblank: return (next == ' ' || next == '\t'); // return isblank(next);
- case RCCgraph: return isgraph(next) != 0;
- case RCCpunct: return ispunct(next) != 0;
- case RCCxdigit: return isxdigit(next) != 0;
- case RCCany: return true;
- default:
- UNIMPLEMENTED;
- }
- }
- bool isUnicodeMatch(unsigned code, unsigned next)
- {
- #ifdef _USE_ICU
- switch (code)
- {
- case RCCalnum: return u_isalnum(next) != 0;
- case RCCcntrl: return u_iscntrl(next) != 0;
- case RCClower: return u_islower(next) != 0;
- case RCCupper: return u_isupper(next) != 0;
- case RCCspace: return u_isWhitespace(next) != 0;
- case RCCalpha: return u_isalpha(next) != 0;
- case RCCdigit: return u_isdigit(next) != 0;
- case RCCprint: return u_isprint(next) != 0;
- case RCCblank: return u_isspace(next) != 0 || (next == '\t');
- case RCCgraph: return u_isprint(next) && !u_isspace(next);
- case RCCpunct: return u_isprint(next) && !(u_isspace(next) || u_isalnum(next));
- case RCCxdigit: return (next < 128) && isxdigit(next); // should be good enough.
- case RCCany: return true;
- default:
- UNIMPLEMENTED;
- }
- #else
- rtlThrowNoUnicode();
- #endif
- }
- //Anyone got some better code - this works, but isn't wonderfully efficient.
- //works by accessing esp[-4096] and seeing if it dies.
- inline void checkStackOverflow(unsigned offset)
- {
- try
- {
- doStackProbe();
- }
- catch (...)
- {
- throwError1(REGEXERR_MatchFailure, offset);
- }
- }
-
- //---------------------------------------------------------------------------
- void serializeLink(MemoryBuffer & out, RegexPattern * pattern, RegexSerializeState & state)
- {
- unsigned match = state.patterns.find(*pattern);
- assertex(match != NotFound);
- out.append(match);
- }
- RegexPattern * deserializeLink(MemoryBuffer & in, RegexSerializeState & state)
- {
- unsigned match;
- in.read(match);
- return LINK(&state.patterns.item(match));
- }
- void serializeName(MemoryBuffer & out, RegexNamed * pattern, RegexSerializeState & state)
- {
- unsigned match = state.named.find(*pattern);
- assertex(match != NotFound);
- out.append(match);
- }
- RegexNamed * deserializeName(MemoryBuffer & in, RegexSerializeState & state)
- {
- unsigned match;
- in.read(match);
- return LINK(&state.named.item(match));
- }
- MemoryBuffer & serializeKind(MemoryBuffer & out, ThorRegexKind kind)
- {
- return out.append((byte)kind);
- }
- void deserialize(MemoryBuffer & in, IAtom * & name)
- {
- StringAttr x;
- in.read(x);
- name = createAtom(x);
- }
- //---------------------------------------------------------------------------
- static MatchState * findTrailingSeparator(MatchState & matched)
- {
- MatchState * child = matched.firstChild;
- while (child)
- {
- //find the last child.
- MatchState * next = child->next;
- while (next)
- {
- child = next;
- next = child->next;
- }
- //If the last child is a separator that matches the last offset of the matched token, adjust the end
- if (child->queryName() == separatorTagAtom)
- return child;
- child = child->firstChild;
- }
- return NULL;
- }
- static void removeTrailingSeparator(MatchState & matched)
- {
- MatchState * child = findTrailingSeparator(matched);
- if (child && child->end == matched.end)
- matched.end = child->start;
- }
- MatchState * RegexMatchSearchInstance::find(MatchState * top, const NlpMatchPath & path, unsigned depth)
- {
- regexid_t id = path.getId(depth);
- do
- {
- if (top->queryID() == id)
- {
- bool matchAny = path.matchAny(depth);
- if (matchAny || (nextIndex == 1))
- {
- if (depth+1 == path.numItems())
- {
- lastExactMatchDepth = depth+1;
- return top;
- }
- if (!matchAny)
- {
- lastExactMatchDepth = depth+1;
- nextIndex = path.nextExactMatchIndex(depth+1);
- }
- MatchState * ret = NULL;
- unsigned prevExactMatchDepth = lastExactMatchDepth;
- if (top->firstChild)
- ret = find(top->firstChild, path, depth+1);
- //If must match a child, or one of children had a required match then we have a result
- if (!matchAny || (prevExactMatchDepth != lastExactMatchDepth))
- return ret;
- }
- else
- nextIndex--;
- }
- else
- {
- if (top->firstChild)
- {
- unsigned prevExactMatchDepth = lastExactMatchDepth;
- MatchState * ret = find(top->firstChild, path, depth);
- //return if matched another level - may have failed to match, or matched completely
- if (prevExactMatchDepth != lastExactMatchDepth)
- return ret;
- }
- }
- top = top->next;
- } while (top);
- return NULL;
- }
- IMatchedElement * RegexMatchPath::getMatch(MatchState * top, bool removeTrailingSep) const
- {
- RegexMatchSearchInstance search;
- search.lastExactMatchDepth = 0;
- search.nextIndex = nextExactMatchIndex(0);
- MatchState * state = search.find(top, *this, 0);
- if (!state)
- return NULL;
- if (removeTrailingSep)
- removeTrailingSeparator(*state);
- return new CMatchedElement(state);
- }
- //---------------------------------------------------------------------------
- void CRegexMatchedResults::extractResults(MatchState & top, const byte * _in, bool removeTrailingSeparator)
- {
- in = _in;
- notMatched.ptr = in;
- ForEachItemIn(idx, def->matchResults)
- {
- ::Release(matched[idx]);
- matched[idx] = ((RegexMatchPath&)def->matchResults.item(idx)).getMatch(&top, removeTrailingSeparator);
- if (!matched[idx]) matched[idx] = LINK(¬Matched);
- }
- }
- //---------------------------------------------------------------------------
- static const char * stateText[] = { "Init", "Follow", "Retry", "Finished", "Repeat", "FollowOnly", "RepeatOnly", "DoneRepeat" };
- #ifdef TRACE_REGEX
- ActiveStage & ActiveStage::setState(unsigned _state)
- {
- DBGLOG("%*s[%p]Change state to %s", patternDepth, "", pattern, stateText[_state]);
- state = _state;
- return *this;
- }
- #endif
- //---------------------------------------------------------------------------
- static void disposeLink(Owned<RegexPattern> & pattern)
- {
- if (pattern)
- {
- RegexPattern * cur = pattern.getClear();
- cur->dispose();
- cur->Release();
- }
- }
- static void disposeName(Owned<RegexNamed> & named)
- {
- if (named)
- {
- RegexNamed * cur = named.getClear();
- cur->dispose();
- cur->Release();
- }
- }
- RegexPattern::RegexPattern()
- {
- gathered = false;
- }
- void RegexPattern::dispose()
- {
- while (next.ordinality())
- {
- RegexPattern & cur = next.popGet();
- cur.dispose();
- cur.Release();
- }
- }
- bool RegexPattern::gather(RegexSerializeState & state)
- {
- if (gathered)
- return false;
- gathered = true;
- state.patterns.append(OLINK(*this));
- gatherNext(state);
- return true;
- }
- void RegexPattern::gatherNext(RegexSerializeState & state)
- {
- ForEachItemIn(idx, next)
- next.item(idx).gather(state);
- }
- void RegexPattern::serializePattern(MemoryBuffer & out)
- {
- serializeKind(out, getKind());
- }
- void RegexPattern::serializeLinks(MemoryBuffer & out, RegexSerializeState & state)
- {
- out.append((unsigned)next.ordinality());
- ForEachItemIn(idx, next)
- serializeLink(out, &next.item(idx), state);
- }
- void RegexPattern::deserializePattern(MemoryBuffer & in)
- {
- }
- void RegexPattern::deserializeLinks(MemoryBuffer & in, RegexSerializeState & state)
- {
- unsigned nextCount;
- in.read(nextCount);
- for (unsigned idx=0; idx < nextCount; idx++)
- next.append(*deserializeLink(in, state));
- }
- RegexMatchAction RegexPattern::matchNext(RegexState & state)
- {
- unsigned num = next.ordinality();
- assertex(num);
- if (num == 1)
- return next.item(0).MATCH(state);
- const byte * saved = state.cur;
- for (unsigned idx = 0; idx < num; idx++)
- {
- RegexMatchAction ret = next.item(idx).MATCH(state);
- if (ret != RegexMatchBacktrack)
- return ret;
- state.cur = saved;
- }
- return RegexMatchBacktrack;
- }
- inline RegexMatchAction RegexPattern::pushMatched(RegexState & state)
- {
- pushStage(state).setMatched();
- return RegexMatchContinue;
- }
- inline RegexMatchAction RegexPattern::markFinishContinueMatch(RegexState & state)
- {
- MatchSaveState saved;
- state.markFinish(saved);
- RegexMatchAction ret = matchNext(state);
- state.unmarkFinish(saved);
- return ret;
- }
- ActiveStage & RegexPattern::pushStageBeginMatch(RegexState & state, RegexMatchStateSave * matched)
- {
- ActiveStage & stage = pushStage(state);
- stage.setMatched();
- stage.extra.matched = matched;
- state.pushMatch(*matched, matched->save);
- #ifdef TRACE_REGEX
- DBGLOG("%*s[%p]Push Begin Match", patternDepth, "", stage.pattern);
- #endif
- return stage;
- }
- void RegexPattern::cleanupBeginMatch(ActiveStage & stage, RegexState & state)
- {
- #ifdef TRACE_REGEX
- DBGLOG("%*s[%p]Pop Begin Match", patternDepth, "", stage.pattern);
- #endif
- state.popMatch(stage.extra.matched->save);
- state.cache.destroyStateSave(stage.extra.matched);
- stage.extra.matched = NULL;
- }
- RegexMatchAction RegexPattern::pushStageEndMatch(RegexState & state)
- {
- ActiveStage & stage = pushStage(state);
- stage.setMatched();
- state.markFinish(stage.extra.saved);
- #ifdef TRACE_REGEX
- DBGLOG("%*s[%p]Push End Match", patternDepth, "", stage.pattern);
- #endif
- return RegexMatchContinue;
- }
- void RegexPattern::cleanupEndMatch(ActiveStage & stage, RegexState & state)
- {
- #ifdef TRACE_REGEX
- DBGLOG("%*s[%p]Pop End Match", patternDepth, "", stage.pattern);
- #endif
- state.unmarkFinish(stage.extra.saved);
- }
- RegexMatchAction RegexPattern::traceMatch(RegexState & state)
- {
- static unsigned i;
- StringBuffer s,t;
- unsigned len = (size32_t)(state.end-state.cur);
- if (len > 10) len = 10;
- getTraceText(t);
- s.appendN(i++, ' ').appendf("Begin %s [%p] >%.*s<", t.str(), this, len, state.cur);
- DBGLOG("%s", s.str());
- RegexMatchAction ret = match(state);
- s.clear().appendN(--i, ' ').appendf("End %s [%p] = %s", t.str(), this, resultText[ret]);
- DBGLOG("%s", s.str());
- return ret;
- }
- void RegexPattern::getTraceText(StringBuffer & s)
- {
- s.append(getPatternText(getKind()));
- }
- void RegexPattern::toXML(StringBuffer & out, RegexXmlState & state)
- {
- out.appendf("\t<expr id=\"%d\"", (unsigned)state.patterns.find(*this));
- toXMLattr(out,state);
- if (next.ordinality())
- {
- out.append(">").newline();
- ForEachItemIn(idx, next)
- {
- out.appendf("\t\t<next id=\"%d\"/>", (unsigned)state.patterns.find(next.item(idx))).newline();
- }
- out.append("\t</expr>").newline();
- ForEachItemInRev(idx2, next)
- state.addLink(next.item(idx2));
- }
- else
- out.append("/>").newline();
- }
- void RegexPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- out.appendf(" kind=\"%s\"", getPatternText(getKind()));
- }
- void RegexPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- }
- RegexMatchAction RegexPattern::nextChild(ActiveStage & stage, RegexState & state)
- {
- if (next.isItem(stage.nextFollow))
- {
- RegexPattern & child = next.item(stage.nextFollow);
- stage.nextFollow++;
- state.cur = stage.followPosition;
- return child.beginMatch(state);
- }
- stage.setState(RSretry);
- return RegexMatchContinue;
- }
- RegexMatchAction RegexPattern::nextAction(ActiveStage & stage, RegexState & state)
- {
- switch (stage.getState())
- {
- case RSinit:
- throwUnexpected();
- case RSnextfollow:
- return nextChild(stage, state);
- case RSfollowonly:
- {
- RegexMatchAction action = nextChild(stage, state);
- if (stage.getState() == RSretry)
- stage.setState(RSfinished);
- return action;
- }
- case RSretry:
- case RSfinished:
- state.popStage();
- return RegexMatchBacktrack;
- }
- UNIMPLEMENTED;
- }
- ActiveStage & RegexPattern::pushStage(RegexState & state)
- {
- #ifdef TRACE_REGEX
- StringBuffer t;
- unsigned len = state.end-state.cur;
- if (len > 10) len = 10;
- getTraceText(t);
- DBGLOG("%*s[%p]Push %s >%.*s<", patternDepth++, "", this, t.str(), len, state.cur);
- #endif
- ActiveStage & cur = state.pushStage();
- cur.pattern = this;
- cur.followPosition = state.cur;
- cur.state = RSinit;
- cur.flags = 0;
- return cur;
- }
- //---------------------------------------------------------------------------
- RegexMatchAction RegexNullPattern::match(RegexState & state)
- {
- return matchNext(state);
- }
- RegexMatchAction RegexNullPattern::beginMatch(RegexState & state)
- {
- return pushMatched(state);
- }
- RegexMatchAction RegexBeginTokenPattern::match(RegexState & state)
- {
- RegexMatchAction ret = matchNext(state);
- if (ret == RegexMatchBacktrackToken)
- return RegexMatchBacktrack;
- return ret;
- }
- RegexMatchAction RegexBeginTokenPattern::beginMatch(RegexState & state)
- {
- ActiveStage & stage = pushStage(state).setMatched();
- stage.flags |= RFbeginToken;
- return RegexMatchContinue;
- }
- RegexMatchAction RegexEndTokenPattern::match(RegexState & state)
- {
- RegexMatchAction ret = matchNext(state);
- if (ret == RegexMatchBacktrack)
- return RegexMatchBacktrackToken;
- return ret;
- }
- RegexMatchAction RegexEndTokenPattern::beginMatch(RegexState & state)
- {
- return pushMatched(state);
- }
- RegexMatchAction RegexEndTokenPattern::nextAction(ActiveStage & stage, RegexState & state)
- {
- switch (stage.getState())
- {
- case RSretry:
- case RSfinished:
- state.popStage();
- return RegexMatchBacktrackToken;
- default:
- return RegexPattern::nextAction(stage, state);
- }
- }
- RegexMatchAction RegexStartPattern::match(RegexState & state)
- {
- if (state.cur == state.start)
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexStartPattern::beginMatch(RegexState & state)
- {
- if (state.cur == state.start)
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexFinishPattern::match(RegexState & state)
- {
- if (state.cur == state.end)
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexFinishPattern::beginMatch(RegexState & state)
- {
- if (state.cur == state.end)
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexAnyCharPattern::match(RegexState & state)
- {
- if (state.cur != state.end)
- {
- state.cur += state.charSize;
- return matchNext(state);
- }
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexAnyCharPattern::beginMatch(RegexState & state)
- {
- if (state.cur != state.end)
- {
- state.cur += state.charSize;
- return pushMatched(state);
- }
- return RegexMatchBacktrack;
- }
- //---------------------------------------------------------------------------
- RegexMatchAction RegexPenaltyPattern::match(RegexState & state)
- {
- state.score -= penalty;
- RegexMatchAction ret = matchNext(state);
- state.score += penalty;
- return ret;
- }
- RegexMatchAction RegexPenaltyPattern::beginMatch(RegexState & state)
- {
- state.score -= penalty;
- return pushMatched(state);
- }
- void RegexPenaltyPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- state.score += penalty;
- }
- void RegexPenaltyPattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- out.append(penalty);
- }
- void RegexPenaltyPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- in.read(penalty);
- }
- void RegexPenaltyPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.append(" penalty=\"").append(penalty).append("\"");
- }
- //---------------------------------------------------------------------------
- void RegexAsciiBasePattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- out.append(text);
- }
- void RegexAsciiBasePattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- in.read(text);
- len = (size32_t)strlen(text);
- }
- void RegexAsciiBasePattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.append(" text=\"");
- encodeXML(text, out, ENCODE_WHITESPACE);
- out.append("\"");
- }
- inline bool RegexAsciiPattern::doMatch(RegexState & state)
- {
- const byte * cur = state.cur;
- const byte * end = state.end;
- if (cur + len <= end)
- {
- if (memcmp(cur, text.get(), len) == 0)
- {
- state.cur = cur + len;
- return true;
- }
- }
- return false;
- }
- RegexMatchAction RegexAsciiPattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexAsciiPattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- inline bool RegexAsciiIPattern::doMatch(RegexState & state)
- {
- const byte * cur = state.cur;
- const byte * end = state.end;
- if (cur + len <= end)
- {
- if (memicmp(cur, text.get(), len) == 0)
- {
- state.cur = cur + len;
- return true;
- }
- }
- return false;
- }
- RegexMatchAction RegexAsciiIPattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexAsciiIPattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- //---------------------------------------------------------------------------
- RegexMatchAction RegexRecursivePattern::match(RegexState & state)
- {
- if ((positionStack.ordinality() == 0) || (positionStack.tos() != state.cur))
- {
- positionStack.append(state.cur);
- state.stack.append(*this);
- RegexMatchAction ret = matchNext(state);
- state.stack.pop();
- positionStack.pop();
- return ret;
- }
- else
- throw MakeStringException(0, "Grammar is left recursive - cannot yet process!");
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexRecursivePattern::beginMatch(RegexState & state)
- {
- //MORE!
- return pushMatched(state);
- }
- RegexMatchAction RegexEndRecursivePattern::match(RegexState & state)
- {
- RegexRecursivePattern & top = (RegexRecursivePattern &)state.stack.popGet();
- const void * saved = top.positionStack.popGet();
- RegexMatchAction ret = matchNext(state);
- top.positionStack.append(saved);
- state.stack.append(top);
- return ret;
- }
- RegexMatchAction RegexEndRecursivePattern::beginMatch(RegexState & state)
- {
- //MORE!
- return pushMatched(state);
- }
- void encodeUnicode(StringBuffer & out, size32_t len, const UChar * text)
- {
- #ifdef _USE_ICU
- UnicodeString unicode(text, len);
- unsigned len8 = unicode.extract(0, unicode.length(), 0, 0, "UTF-8");
- char * text8 = (char *)malloc(len8);
- unicode.extract(0, unicode.length(), text8, len8, "UTF-8");
- encodeXML(text8, out, ENCODE_WHITESPACE, len8, true);
- free(text8);
- #else
- rtlThrowNoUnicode();
- #endif
- }
- //---------------------------------------------------------------------------
- #ifdef _USE_ICU
- void RegexUnicodePattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- ::serialize(out, text);
- }
- void RegexUnicodePattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- ::deserialize(in, text);
- }
- void RegexUnicodePattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.appendf(" text=\"");
- encodeUnicode(out, (size32_t)(text.length()/2), (const UChar *)text.get());
- out.append("\"");
- }
- inline bool RegexUnicodePattern::doMatch(RegexState & state)
- {
- const byte * cur = state.cur;
- const byte * end = state.end;
- size32_t len = (size32_t)text.length();
- if (cur + len <= end)
- {
- if (memcmp(cur, text.get(), len) == 0)
- {
- state.cur = cur + len;
- return true;
- }
- }
- return false;
- }
- RegexMatchAction RegexUnicodePattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexUnicodePattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- RegexUnicodeIPattern::RegexUnicodeIPattern(unsigned _len, const UChar * _text)
- {
- UChar * curLower = (UChar *)lower.allocate(_len*2);
- UChar * curUpper = (UChar *)upper.allocate(_len*2);
- for (unsigned i = 0; i< _len; i++)
- {
- curLower[i] = (UChar)u_tolower(_text[i]);
- curUpper[i] = (UChar)u_toupper(_text[i]);
- }
- }
- void RegexUnicodeIPattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- ::serialize(out, lower);
- ::serialize(out, upper);
- }
- void RegexUnicodeIPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- ::deserialize(in, lower);
- ::deserialize(in, upper);
- }
- void RegexUnicodeIPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.appendf(" text=\"");
- encodeUnicode(out, (size32_t)(lower.length()/2), (const UChar *)lower.get());
- out.append("\"");
- }
- inline bool RegexUnicodeIPattern::doMatch(RegexState & state)
- {
- const byte * start = state.cur;
- const byte * end = state.end;
- size32_t size = (size32_t)lower.length();
- if (start + size <= end)
- {
- unsigned i;
- unsigned len = size/sizeof(UChar);
- const UChar * cur = (const UChar *)state.cur;
- const UChar * curLower = (const UChar *)lower.get();
- const UChar * curUpper = (const UChar *)upper.get();
- for (i = 0; i < len; i++)
- {
- UChar next = cur[i];
- if ((next != curLower[i]) && (next != curUpper[i]))
- return false;
- }
- state.cur += size;
- return true;
- }
- return false;
- }
- RegexMatchAction RegexUnicodeIPattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexUnicodeIPattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- RegexUnicodeFIPattern::RegexUnicodeFIPattern(unsigned _len, const UChar * _text)
- {
- MemoryBuffer foldedBuffer;
- UChar temp[2];
- UErrorCode error = U_ZERO_ERROR;
- for (unsigned i = 0; i< _len; i++)
- {
- unsigned foldLen = u_strFoldCase(temp, _elements_in(temp), _text+i, 1, U_FOLD_CASE_DEFAULT, &error);
- foldedBuffer.append(foldLen, &temp);
- }
- folded.set(foldedBuffer.length(), foldedBuffer.toByteArray());
- }
- bool RegexUnicodeFIPattern::doMatch(RegexState & state)
- {
- const UChar * cur = (const UChar *)state.cur;
- const UChar * end = (const UChar *)state.end;
- UChar temp[2];
- UErrorCode error = U_ZERO_ERROR;
- const UChar * curMatchText = (const UChar *)folded.get();
- const UChar * endMatchText = (const UChar *)((const byte *)folded.get() + folded.length());
- while (cur != end)
- {
- unsigned foldLen = u_strFoldCase(temp, _elements_in(temp), cur, 1, U_FOLD_CASE_DEFAULT, &error);
- if (temp[0] != *curMatchText)
- return false;
- assertex(foldLen == 1 || foldLen == 2);
- if (foldLen == 2)
- {
- if (curMatchText + foldLen > endMatchText)
- return false;
- if (temp[1] != curMatchText[1])
- return false;
- }
- cur += 1;
- curMatchText += foldLen;
- if (curMatchText == endMatchText)
- {
- state.cur = (const byte *)cur;
- return true;
- }
- }
- return false;
- }
- RegexMatchAction RegexUnicodeFIPattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexUnicodeFIPattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- //---------------------------------------------------------------------------
- void RegexUtf8Pattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- ::serialize(out, text);
- }
- void RegexUtf8Pattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- ::deserialize(in, text);
- }
- void RegexUtf8Pattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.appendf(" text=\"");
- encodeXML((const char *)text.get(), out, ENCODE_WHITESPACE, (size32_t)text.length(), true);
- out.append("\"");
- }
- inline bool RegexUtf8Pattern::doMatch(RegexState & state)
- {
- const byte * cur = state.cur;
- const byte * end = state.end;
- size32_t size = (size32_t)text.length();
- if (cur + size <= end)
- {
- if (memcmp(cur, text.get(), size) == 0)
- {
- state.cur = cur + size;
- return true;
- }
- }
- return false;
- }
- RegexMatchAction RegexUtf8Pattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexUtf8Pattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- //---------------------------------------------------------------------------
- RegexUtf8IPattern::RegexUtf8IPattern(unsigned _len, const char * _text)
- {
- //Store unicode lowercase and uppercase versions, and compare the incoming utf a character at a time.
- UChar * curLower = (UChar *)lower.allocate(_len*sizeof(UChar));
- UChar * curUpper = (UChar *)upper.allocate(_len*sizeof(UChar));
- const byte * cur = (const byte *)_text;
- const byte * end = cur + rtlUtf8Size(_len, cur);
- for (unsigned i = 0; i< _len; i++)
- {
- UChar next = readUtf8Character((size32_t)(end-cur), cur);
- curLower[i] = (UChar)u_tolower(next);
- curUpper[i] = (UChar)u_toupper(next);
- }
- }
- void RegexUtf8IPattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- ::serialize(out, lower);
- ::serialize(out, upper);
- }
- void RegexUtf8IPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- ::deserialize(in, lower);
- ::deserialize(in, upper);
- }
- void RegexUtf8IPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.appendf(" text=\"");
- encodeUnicode(out, (size32_t)(lower.length()/2), (const UChar *)lower.get());
- out.append("\"");
- }
- inline bool RegexUtf8IPattern::doMatch(RegexState & state)
- {
- const byte * end = state.end;
- size32_t size = (size32_t)lower.length();
- size32_t len = size/(size32_t)sizeof(UChar);
- const byte * cur = state.cur;
- const UChar * curLower = (const UChar *)lower.get();
- const UChar * curUpper = (const UChar *)upper.get();
- for (unsigned i = 0; i < len; i++)
- {
- if (cur == end)
- return false;
- UChar next = readUtf8Character((size32_t)(end-cur), cur);
- if ((next != curLower[i]) && (next != curUpper[i]))
- return false;
- }
- state.cur = cur;
- return true;
- }
- RegexMatchAction RegexUtf8IPattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexUtf8IPattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- #endif
- //---------------------------------------------------------------------------
- RegexAsciiSetBasePattern::RegexAsciiSetBasePattern()
- {
- inverted = false;
- for (unsigned i = 0; i < 256; i++)
- include[i] = inverted;
- }
- void RegexAsciiSetBasePattern::setInvert(bool newValue)
- {
- //can call before or after processing the list.
- if (inverted != newValue)
- {
- for (unsigned i = 0; i < 256; i++)
- include[i] ^= true;
- inverted = newValue;
- }
- }
- void RegexAsciiSetBasePattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- serializeBoolArray(out, 256, include);
- out.append(inverted);
- }
- void RegexAsciiSetBasePattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- deserializeBoolArray(256, include, in);
- in.read(inverted);
- }
- inline bool RegexAsciiSetBasePattern::doMatch(RegexState & state)
- {
- const byte * cur = state.cur;
- const byte * end = state.end;
- if (cur < end)
- {
- if (include[*cur])
- {
- state.cur = cur + 1;
- return true;
- }
- }
- return false;
- }
- RegexMatchAction RegexAsciiSetBasePattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexAsciiSetBasePattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- void RegexAsciiSetBasePattern::addSpecialRange(unsigned value)
- {
- for (unsigned i = 0; i < 256; i++)
- {
- if (isAsciiMatch(value, i))
- include[i] = !inverted;
- }
- }
- void RegexAsciiSetBasePattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexSetBasePattern::toXMLattr(out, state);
- out.append(" set=\"");
- if (inverted)
- out.append("^");
- for (unsigned i = 0; i < 256; i++)
- {
- if (include[i] != inverted)
- {
- char c = i;
- encodeXML(&c, out, ENCODE_WHITESPACE, 1);
- }
- }
- out.append("\"");
- }
- void RegexAsciiSetPattern::addRange(unsigned low, unsigned high)
- {
- if (low & RegexSpecialMask)
- {
- assertex(low == high);
- addSpecialRange(low);
- }
- else
- {
- assertex(low < 256 && high < 256);
- for (unsigned i = low; i <= high; i++)
- include[i] = !inverted;
- }
- }
- void RegexAsciiISetPattern::addRange(unsigned low, unsigned high)
- {
- if (low & RegexSpecialMask)
- {
- assertex(low == high);
- addSpecialRange(low);
- }
- else
- {
- assertex(low < 256 && high < 256);
- for (unsigned i = low; i <= high; i++)
- {
- include[tolower(i)] = !inverted;
- include[toupper(i)] = !inverted;
- }
- }
- }
- //---------------------------------------------------------------------------
- #ifdef _USE_ICU
- RegexUnicodeSetPattern::RegexUnicodeSetPattern(bool _caseSensitive)
- {
- inverted = false;
- caseSensitive = _caseSensitive;
- }
- void RegexUnicodeSetPattern::addRange(unsigned low, unsigned high)
- {
- if (!caseSensitive)
- {
- //This isn't really good enough - probably need to use string for the high and low values to allow collation
- //comparison, and to allow SS to match correctly.
- if (low & RegexSpecialMask)
- {
- if ((low == RCClower) || (low == RCCupper))
- low = RCCalpha;
- }
- else
- {
- low = u_foldCase(low, U_FOLD_CASE_DEFAULT);
- high = u_foldCase(high, U_FOLD_CASE_DEFAULT);
- }
- }
- from.append(low);
- to.append(high);
- }
- void RegexUnicodeSetPattern::setInvert(bool value)
- {
- inverted = value;
- }
- bool RegexUnicodeSetPattern::doMatch(RegexState & state)
- {
- const byte * cur = (const byte *)state.cur;
- const byte * end = (const byte *)state.end;
- if (cur < end)
- {
- UChar next;
- if (state.inputFormat == NlpUnicode)
- {
- next = *(const UChar *)cur;
- cur += sizeof(UChar);
- }
- else
- {
- next = readUtf8Character((size32_t)(end-cur), cur);
- }
- if (!caseSensitive)
- next = (UChar)u_foldCase(next, U_FOLD_CASE_DEFAULT); // MORE: Doesn't cope with full folding of SS
- ForEachItemIn(idx, from)
- {
- unsigned low = from.item(idx);
- if (low & RegexSpecialMask)
- {
- if (isUnicodeMatch(low, next))
- {
- if (inverted)
- return false;
- state.cur = cur;
- return true;
- }
- }
- else if ((next >= low) && (next <= to.item(idx)))
- {
- if (inverted)
- return false;
- state.cur = cur;
- return true;
- }
- }
- if (inverted)
- {
- state.cur = cur;
- return true;
- }
- }
- return false;
- }
- RegexMatchAction RegexUnicodeSetPattern::match(RegexState & state)
- {
- if (doMatch(state))
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexUnicodeSetPattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- void RegexUnicodeSetPattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- out.append(caseSensitive);
- out.append(inverted);
- out.append(from.ordinality());
- ForEachItemIn(idx, from)
- {
- out.append(from.item(idx));
- out.append(to.item(idx));
- }
- }
- void RegexUnicodeSetPattern::deserializePattern(MemoryBuffer & in)
- {
- unsigned count;
- RegexPattern::deserializePattern(in);
- in.read(caseSensitive);
- in.read(inverted);
- in.read(count);
- for (unsigned idx=0; idx < count; idx++)
- {
- unsigned value;
- in.read(value);
- from.append(value);
- in.read(value);
- to.append(value);
- }
- }
- void RegexUnicodeSetPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexSetBasePattern::toXMLattr(out, state);
- if (state.detail >= 100)
- {
- if (inverted)
- out.append(" inverted");
- out.append(" set=\"");
- ForEachItemIn(idx, from)
- {
- if (idx)
- out.append(",");
- out.append(from.item(idx));
- if (from.item(idx) != to.item(idx))
- out.append("..").append(to.item(idx));
- }
- out.append("\"");
- }
- }
- #endif
- //---------------------------------------------------------------------------
- RegexMatchAction RegexDonePattern::match(RegexState & state)
- {
- state.top.end = state.cur;
- if (state.matchAction->onMatch(state))
- return RegexMatchDone;
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexDonePattern::beginMatch(RegexState & state)
- {
- state.top.end = state.cur;
- if (state.matchAction->onMatch(state))
- return RegexMatchDone;
- return RegexMatchBacktrack;
- }
- //---------------------------------------------------------------------------
- RegexMatchAction RegexEndNestedPattern::match(RegexState & state)
- {
- RegexPattern & top = state.stack.popGet();
- RegexMatchAction ret = top.MATCH(state);
- state.stack.append(top);
- return ret;
- }
- RegexMatchAction RegexEndNestedPattern::beginMatch(RegexState & state)
- {
- ActiveStage & stage = pushStage(state);
- stage.setState(RSfinished);
- stage.extra.nextPattern = &state.namedStack.popGet();
- return stage.extra.nextPattern->beginMatch(state);
- }
- void RegexEndNestedPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- state.namedStack.append(*stage.extra.nextPattern);
- }
- //---------------------------------------------------------------------------
- void RegexAssertionPattern::dispose()
- {
- RegexPattern::dispose();
- disposeLink(pattern);
- }
- bool RegexAssertionPattern::gather(RegexSerializeState & state)
- {
- bool ok = RegexPattern::gather(state);
- if (ok)
- pattern->gather(state);
- return ok;
- }
- void RegexAssertionPattern::serializeLinks(MemoryBuffer & out, RegexSerializeState & state)
- {
- RegexPattern::serializeLinks(out, state);
- serializeLink(out, pattern, state);
- }
- void RegexAssertionPattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- out.append(invert);
- }
- void RegexAssertionPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.appendf(" sub=\"%d\" invert=\"%d\"", (unsigned)state.patterns.find(*pattern), invert);
- state.addLink(*pattern);
- }
- void RegexAssertionPattern::deserializeLinks(MemoryBuffer & in, RegexSerializeState & state)
- {
- RegexPattern::deserializeLinks(in, state);
- pattern.setown(deserializeLink(in, state));
- }
- void RegexAssertionPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- in.read(invert);
- }
- bool RegexAssertNextPattern::nextMatches(RegexState & state)
- {
- //Sub function to reduce stack usage
- MatchedAssertionAction matchedFlag;
- RegexState localState(state, &matchedFlag, (size32_t)(state.end - state.cur), state.cur);
- localState.processPattern(pattern);
- return matchedFlag.isMatched();
- }
- RegexMatchAction RegexAssertNextPattern::match(RegexState & state)
- {
- if (nextMatches(state) != invert)
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexAssertNextPattern::beginMatch(RegexState & state)
- {
- if (nextMatches(state) != invert)
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- bool RegexAssertPrevPattern::prevMatches(RegexState & state)
- {
- //Sub function to reduce stack usage
- ExactMatchedAssertionAction matchedFlag;
- //This will work efficiently on fixed size patterns, but its painful for variable length
- //It would work much better if we reversed the pattern, reversed the string, and then matched.
- //I'll implement it when someone complains!
- unsigned sizeBefore = (size32_t)(state.cur - state.start);
- if (sizeBefore >= minSize)
- {
- unsigned maxToCheck = sizeBefore < maxSize ? sizeBefore : maxSize;
- for (unsigned sizeToCheck = minSize; sizeToCheck <= maxToCheck; sizeToCheck += state.charSize)
- {
- //MORE: A test of finish will incorrectly succeed
- RegexState localState(state, &matchedFlag, sizeBefore, state.start);
- localState.cur = state.cur - sizeToCheck;
- localState.processPattern(pattern);
- if (matchedFlag.isMatched())
- return true;
- }
- }
- return false;
- }
- RegexMatchAction RegexAssertPrevPattern::match(RegexState & state)
- {
- if (prevMatches(state) != invert)
- return matchNext(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexAssertPrevPattern::beginMatch(RegexState & state)
- {
- if (prevMatches(state) != invert)
- return pushMatched(state);
- return RegexMatchBacktrack;
- }
- void RegexAssertPrevPattern::serializePattern(MemoryBuffer & out)
- {
- RegexAssertionPattern::serializePattern(out);
- out.append(minSize);
- out.append(maxSize);
- }
- void RegexAssertPrevPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexAssertionPattern::deserializePattern(in);
- in.read(minSize);
- in.read(maxSize);
- }
- void RegexAssertPrevPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexAssertionPattern::toXMLattr(out, state);
- out.appendf(" min=\"%d\" max=\"%d\"", minSize, maxSize);
- }
- //---------------------------------------------------------------------------
- RegexMatchAction RegexBeginCheckPattern::match(RegexState & state)
- {
- MatchState matched;
- MatchSaveState saved;
- state.pushMatch(matched, saved);
- RegexMatchAction ret = matchNext(state);
- state.popMatch(saved);
- return ret;
- }
- RegexMatchAction RegexBeginCheckPattern::beginMatch(RegexState & state)
- {
- RegexMatchStateSave * matched = state.cache.createStateSave(NULL, 0);
- pushStageBeginMatch(state, matched);
- return RegexMatchContinue;
- }
- void RegexBeginCheckPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- cleanupBeginMatch(stage, state);
- }
- void RegexCheckPattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- out.append(invert);
- out.append(stripSeparator);
- }
- void RegexCheckPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- in.read(invert);
- in.read(stripSeparator);
- }
- inline const byte * RegexCheckPattern::getEndMatch(RegexState & state)
- {
- const byte * end = state.cur;
- if (stripSeparator)
- {
- MatchState * child = findTrailingSeparator(*state.curMatch);
- if (child && child->end == end)
- end = child->start;
- }
- return end;
- }
- RegexMatchAction RegexCheckInPattern::match(RegexState & state)
- {
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- MatchedCheckAction matchedFlag;
- RegexState localState(state, &matchedFlag, (size32_t)(end - start), start);
- pattern->MATCH(localState);
- if (matchedFlag.isMatched() ^ invert)
- return markFinishContinueMatch(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexCheckInPattern::beginMatch(RegexState & state)
- {
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- MatchedCheckAction matchedFlag;
- RegexState localState(state, &matchedFlag, (size32_t)(end - start), start);
- localState.helper = state.helper;
- localState.processPattern(pattern);
- if (matchedFlag.isMatched() ^ invert)
- return pushStageEndMatch(state);
- return RegexMatchBacktrack;
- }
- void RegexCheckInPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- cleanupEndMatch(stage, state);
- }
- void RegexCheckInPattern::dispose()
- {
- RegexCheckPattern::dispose();
- disposeLink(pattern);
- }
- bool RegexCheckInPattern::gather(RegexSerializeState & state)
- {
- bool ok = RegexCheckPattern::gather(state);
- if (ok)
- pattern->gather(state);
- return ok;
- }
- void RegexCheckInPattern::serializeLinks(MemoryBuffer & out, RegexSerializeState & state)
- {
- RegexCheckPattern::serializeLinks(out, state);
- serializeLink(out, pattern, state);
- }
- void RegexCheckInPattern::deserializeLinks(MemoryBuffer & in, RegexSerializeState & state)
- {
- RegexCheckPattern::deserializeLinks(in, state);
- pattern.setown(deserializeLink(in, state));
- }
- void RegexCheckInPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexCheckPattern::toXMLattr(out, state);
- out.appendf(" sub=\"%d\"", (unsigned)state.patterns.find(*pattern));
- state.addLink(*pattern);
- }
- inline bool RegexCheckLengthPattern::doMatch(RegexState & state)
- {
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- unsigned matchSize = (size32_t)(end - start);
- unsigned matchLength;
- if (state.inputFormat == NlpUtf8)
- matchLength = rtlUtf8Length(matchSize, start);
- else
- matchLength = matchSize;
- bool inRange = ((matchLength >= minExpectedBytes) && (matchLength <= maxExpectedBytes));
- return (inRange != invert);
- }
- RegexMatchAction RegexCheckLengthPattern::match(RegexState & state)
- {
- if (doMatch(state))
- return markFinishContinueMatch(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexCheckLengthPattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushStageEndMatch(state);
- return RegexMatchBacktrack;
- }
- void RegexCheckLengthPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- cleanupEndMatch(stage, state);
- }
- void RegexCheckLengthPattern::serializePattern(MemoryBuffer & out)
- {
- RegexCheckPattern::serializePattern(out);
- out.append(minExpectedBytes);
- out.append(maxExpectedBytes);
- }
- void RegexCheckLengthPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexCheckPattern::deserializePattern(in);
- in.read(minExpectedBytes);
- in.read(maxExpectedBytes);
- }
- void RegexCheckLengthPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexCheckPattern::toXMLattr(out, state);
- out.appendf(" expected=\"%d..%d\"", minExpectedBytes, maxExpectedBytes);
- }
- //---------------------------------------------------------------------------
- void RegexValidatePattern::serializePattern(MemoryBuffer & out)
- {
- RegexCheckPattern::serializePattern(out);
- out.append(validatorIndex);
- }
- void RegexValidatePattern::deserializePattern(MemoryBuffer & in)
- {
- RegexCheckPattern::deserializePattern(in);
- in.read(validatorIndex);
- }
- void RegexValidatePattern::deserializeLinks(MemoryBuffer & in, RegexSerializeState & state)
- {
- RegexCheckPattern::deserializeLinks(in, state);
- }
- void RegexValidatePattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexCheckPattern::toXMLattr(out, state);
- out.appendf(" validator=\"%d\"", validatorIndex);
- }
- RegexMatchAction RegexValidatePattern::match(RegexState & state)
- {
- if (doMatch(state))
- return markFinishContinueMatch(state);
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexValidatePattern::beginMatch(RegexState & state)
- {
- if (doMatch(state))
- return pushStageEndMatch(state);
- return RegexMatchBacktrack;
- }
- void RegexValidatePattern::killStage(ActiveStage & stage, RegexState & state)
- {
- cleanupEndMatch(stage, state);
- }
- bool RegexValidateAscAsAscPattern::doMatch(RegexState & state)
- {
- IStringValidator * validator = (IStringValidator *)state.helper->queryValidator(validatorIndex);
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- unsigned matchSize = (size32_t)(end - start);
- return validator->isValid(matchSize, (const char *)start);
- }
- bool RegexValidateUniAsAscPattern::doMatch(RegexState & state)
- {
- IStringValidator * validator = (IStringValidator *)state.helper->queryValidator(validatorIndex);
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- size32_t matchSize = (size32_t)(end - start);
- unsigned asciiLen;
- char * asciiText;
- rtlUnicodeToStrX(asciiLen, asciiText, matchSize/2, (const UChar *)start);
- bool ok = validator->isValid(asciiLen, asciiText);
- rtlFree(asciiText);
- return ok;
- }
- bool RegexValidateUtf8AsAscPattern::doMatch(RegexState & state)
- {
- IStringValidator * validator = (IStringValidator *)state.helper->queryValidator(validatorIndex);
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- unsigned matchSize = (size32_t)(end - start);
- unsigned asciiLen;
- char * asciiText;
- rtlUnicodeToStrX(asciiLen, asciiText, rtlUtf8Length(matchSize, start), (const UChar *)start);
- bool ok = validator->isValid(asciiLen, asciiText);
- rtlFree(asciiText);
- return ok;
- }
- bool RegexValidateAscAsUniPattern::doMatch(RegexState & state)
- {
- IUnicodeValidator * validator = (IUnicodeValidator *)state.helper->queryValidator(validatorIndex);
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- unsigned matchSize = (size32_t)(end - start);
- unsigned unicodeLen;
- UChar * unicodeText;
- rtlStrToUnicodeX(unicodeLen, unicodeText, matchSize, (const char *)start);
- bool ok = validator->isValid(unicodeLen, unicodeText);
- rtlFree(unicodeText);
- return ok;
- }
- bool RegexValidateUniAsUniPattern::doMatch(RegexState & state)
- {
- IUnicodeValidator * validator = (IUnicodeValidator *)state.helper->queryValidator(validatorIndex);
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- unsigned matchSize = (size32_t)(end - start);
- return (validator->isValid(matchSize/2, (const UChar *)start));
- }
- bool RegexValidateUtf8AsUniPattern::doMatch(RegexState & state)
- {
- IUnicodeValidator * validator = (IUnicodeValidator *)state.helper->queryValidator(validatorIndex);
- const byte * start = state.curMatch->start;
- const byte * end = getEndMatch(state);
- unsigned matchSize = (size32_t)(end - start);
- unsigned unicodeLen;
- UChar * unicodeText;
- rtlStrToUnicodeX(unicodeLen, unicodeText, rtlUtf8Length(matchSize, start), (const char *)start);
- bool ok = validator->isValid(unicodeLen, unicodeText);
- rtlFree(unicodeText);
- return ok;
- }
- //---------------------------------------------------------------------------
- void RegexNamedPattern::getTraceText(StringBuffer & s)
- {
- s.append(getPatternText(getKind()));
- if (def->queryName())
- s.append(" ").append(def->queryName());
- }
- RegexMatchAction RegexNamedPattern::match(RegexState & state)
- {
- #ifdef __64BIT__
- // 64-bit systems have more space for stack
- RegexMatchState matched(def);
- return def->match(state, &end, matched);
- #else
- //Allocate on the heap to make a stack fault less likely
- RegexMatchState * matched = state.cache.createState(def);
- RegexMatchAction ret = def->match(state, &end, *matched);
- state.cache.destroyState(matched);
- return ret;
- #endif
- }
- void RegexNamedPattern::dispose()
- {
- RegexPattern::dispose();
- disposeName(def);
- }
- bool RegexNamedPattern::gather(RegexSerializeState & state)
- {
- bool ok = RegexPattern::gather(state);
- if (ok)
- def->gather(state);
- return ok;
- }
- void RegexNamedPattern::serializeLinks(MemoryBuffer & out, RegexSerializeState & state)
- {
- RegexPattern::serializeLinks(out, state);
- serializeName(out, def, state);
- }
- void RegexNamedPattern::deserializeLinks(MemoryBuffer & in, RegexSerializeState & state)
- {
- RegexPattern::deserializeLinks(in, state);
- def.setown(deserializeName(in, state));
- }
- void RegexNamedPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- if (def->queryName())
- out.appendf(" name=\"%s\"", def->queryName()->queryStr());
- out.appendf(" body=\"%d\"", (unsigned)state.named.find(*def));
- }
- RegexMatchAction RegexNamedPattern::RegexEndNamedPattern::match(RegexState & state)
- {
- MatchSaveState saved;
- state.markFinish(saved);
- RegexMatchAction ret = named->matchNext(state);
- state.unmarkFinish(saved);
- return ret;
- }
- RegexMatchAction RegexNamedPattern::RegexEndNamedPattern::beginMatch(RegexState & state)
- {
- return pushStageEndMatch(state);
- }
- RegexMatchAction RegexNamedPattern::RegexEndNamedPattern::nextAction(ActiveStage & stage, RegexState & state)
- {
- switch (stage.getState())
- {
- case RSnextfollow:
- return named->nextChild(stage, state);
- default:
- return RegexPattern::nextAction(stage, state);
- }
- }
- void RegexNamedPattern::RegexEndNamedPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- cleanupEndMatch(stage, state);
- }
- RegexMatchAction RegexNamedPattern::beginMatch(RegexState & state)
- {
- RegexMatchStateSave * matched = state.cache.createStateSave(def);
- ActiveStage & stage = pushStageBeginMatch(state, matched);
- stage.setState(RSfinished); // so children don't get processed.
- state.namedStack.append(end);
- return def->beginMatch(state);
- }
- void RegexNamedPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- cleanupBeginMatch(stage, state);
- state.namedStack.pop();
- }
- //---------------------------------------------------------------------------
- RegexMatchAction RegexBeginSeparatorPattern::match(RegexState & state)
- {
- MatchState matched(separatorTagAtom, 0);
- MatchSaveState saved;
- state.pushMatch(matched, saved);
- RegexMatchAction ret = matchNext(state);
- state.popMatch(saved);
- return ret;
- }
- RegexMatchAction RegexBeginSeparatorPattern::beginMatch(RegexState & state)
- {
- RegexMatchStateSave * matched = state.cache.createStateSave(separatorTagAtom, 0);
- pushStageBeginMatch(state, matched);
- return RegexMatchContinue;
- }
- void RegexBeginSeparatorPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- cleanupBeginMatch(stage, state);
- }
- RegexMatchAction RegexEndSeparatorPattern::match(RegexState & state)
- {
- return mapAction(markFinishContinueMatch(state));
- }
- RegexMatchAction RegexEndSeparatorPattern::beginMatch(RegexState & state)
- {
- return mapAction(pushStageEndMatch(state));
- }
- RegexMatchAction RegexEndSeparatorPattern::nextAction(ActiveStage & stage, RegexState & state)
- {
- return mapAction(RegexPattern::nextAction(stage, state));
- }
- void RegexEndSeparatorPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- cleanupEndMatch(stage, state);
- }
- //---------------------------------------------------------------------------
- RegexMatchAction RegexRepeatPattern::match(RegexState & state)
- {
- return match(state, minLimit, maxLimit);
- }
- RegexMatchAction RegexRepeatPattern::matchNextInstance(RegexState & state, unsigned curMin, unsigned curMax)
- {
- Owned<RegexRepeatInstance> instance = new RegexRepeatInstance(this, curMin ? curMin-1 : 0, curMax-1);
- return def->match(state, instance);
- }
- RegexMatchAction RegexRepeatPattern::match(RegexState & state, unsigned curMin, unsigned curMax)
- {
- if (curMax == 0)
- return matchNext(state);
- checkStackOverflow((size32_t)(state.cur-state.start));
- Owned<RegexRepeatInstance> instance = new RegexRepeatInstance(this, curMin ? curMin-1 : 0, curMax-1);
- if (curMin != 0)
- return def->match(state, instance);
- const byte * saved = state.cur;
- if (greedy)
- {
- RegexMatchAction ret = def->match(state, instance);
- if (ret != RegexMatchBacktrack)
- return ret;
- state.cur = saved;
- return matchNext(state);
- }
- else
- {
- RegexMatchAction ret = matchNext(state);
- if (ret != RegexMatchBacktrack)
- return ret;
- state.cur = saved;
- return def->match(state, instance);
- }
- }
- void RegexRepeatPattern::dispose()
- {
- RegexPattern::dispose();
- disposeName(def);
- }
- bool RegexRepeatPattern::gather(RegexSerializeState & state)
- {
- bool ok = RegexPattern::gather(state);
- if (ok)
- def->gather(state);
- return ok;
- }
- void RegexRepeatPattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- out.append(minLimit);
- out.append(maxLimit);
- out.append(greedy);
- }
- void RegexRepeatPattern::serializeLinks(MemoryBuffer & out, RegexSerializeState & state)
- {
- RegexPattern::serializeLinks(out, state);
- serializeName(out, def, state);
- }
- void RegexRepeatPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- in.read(minLimit);
- in.read(maxLimit);
- in.read(greedy);
- }
- void RegexRepeatPattern::deserializeLinks(MemoryBuffer & in, RegexSerializeState & state)
- {
- RegexPattern::deserializeLinks(in, state);
- def.setown(deserializeName(in, state));
- }
- void RegexRepeatPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.appendf(" min=\"%d\" max=\"%d\" greedy=\"%d\" body=\"%d\"", minLimit, maxLimit, greedy, (unsigned)state.named.find(*def));
- }
- RegexMatchAction RegexRepeatInstance::match(RegexState & state)
- {
- return def->match(state, minLimit, maxLimit);
- }
- //--- stack friedly implementation
- RegexMatchAction RegexRepeatPattern::beginMatch(RegexState & state)
- {
- return beginMatch(state, minLimit, maxLimit);
- }
- RegexMatchAction RegexRepeatPattern::beginMatchNextInstance(RegexState & state, unsigned curMin, unsigned curMax)
- {
- Owned<RegexRepeatInstance> instance = new RegexRepeatInstance(this, curMin ? curMin-1 : 0, curMax-1);
- return def->match(state, instance);
- }
- RegexMatchAction RegexRepeatPattern::beginMatch(RegexState & state, unsigned curMin, unsigned curMax)
- {
- ActiveStage & stage = pushStage(state);
- stage.nextFollow = 0;
- if (curMax == 0)
- {
- stage.extra.repeatInstance = NULL;
- stage.setState(RSfollowonly);
- return RegexMatchContinue;
- }
- RegexRepeatInstance * instance = new RegexRepeatInstance(this, curMin ? curMin-1 : 0, curMax-1);
- stage.extra.repeatInstance = instance;
- if (curMin != 0)
- stage.setState(RSrepeatonly);
- else if (greedy)
- stage.setState(RSrepeat);
- else
- stage.setState(RSnextfollow);
- return RegexMatchContinue;
- }
- void RegexRepeatPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- if (state.namedStack.ordinality() && stage.extra.repeatInstance)
- {
- if (&state.namedStack.tos() == stage.extra.repeatInstance)
- state.namedStack.pop();
- }
- delete stage.extra.repeatInstance;
- }
- inline RegexMatchAction RegexRepeatPattern::nextRepeatMatch(ActiveStage & stage, RegexState & state)
- {
- state.namedStack.append(*stage.extra.repeatInstance);
- return def->beginMatch(state);
- }
- RegexMatchAction RegexRepeatPattern::nextAction(ActiveStage & stage, RegexState & state)
- {
- switch (stage.getState())
- {
- case RSretry:
- assertex(!greedy);
- state.cur = stage.followPosition;
- //fall through to repeat-only code.
- case RSrepeatonly:
- stage.setState(RSfinished);
- return nextRepeatMatch(stage, state);
- case RSrepeat:
- stage.setState(RSdonerepeat); // ensure namedStack is popped before processing children
- stage.nextFollow = 0;
- return nextRepeatMatch(stage, state);
- case RSdonerepeat:
- state.namedStack.pop();
- stage.setState(RSfollowonly);
- stage.nextFollow = 0;
- return RegexPattern::nextAction(stage, state);
- default:
- return RegexPattern::nextAction(stage, state);
- }
- }
- RegexMatchAction RegexRepeatInstance::beginMatch(RegexState & state)
- {
- return def->beginMatch(state, minLimit, maxLimit);
- }
- //---------------------------------------------------------------------------
- static const int MultiAcceptMask = 0x80000000;
- AsciiDfa::AsciiDfa()
- {
- numStates = 0;
- numTransitions = 0;
- numAccepts = 0;
- states = NULL;
- transitions = NULL;
- accepts = NULL;
- }
- AsciiDfa::~AsciiDfa()
- {
- delete [] states;
- free(transitions);
- free(accepts);
- }
- void AsciiDfa::init(unsigned _numStates)
- {
- numStates = _numStates;
- states = new AsciiDfaState[numStates];
- memset(states, 0, sizeof(*states)*numStates);
- }
- unsigned AsciiDfa::getAccepts(const AsciiDfaState & state, unsigned idx) const
- {
- unsigned acceptId = state.acceptID;
- if (acceptId == NotFound) return NotFound;
- if (acceptId & MultiAcceptMask)
- {
- unsigned * values = accepts + (acceptId & ~MultiAcceptMask);
- return values[idx];
- }
- else
- return (idx == 0) ? acceptId : NotFound;
- }
- void AsciiDfa::serialize(MemoryBuffer & out)
- {
- out.append(numStates).append(numTransitions).append(numAccepts);
- out.append(numStates * sizeof(*states), states);
- out.append(numTransitions * sizeof(*transitions), transitions);
- out.append(numAccepts * sizeof(*accepts), accepts);
- }
- void AsciiDfa::deserialize(MemoryBuffer & in)
- {
- in.read(numStates).read(numTransitions).read(numAccepts);
- states = new AsciiDfaState[numStates];
- transitions = (unsigned *)malloc(numTransitions * sizeof(*transitions));
- accepts = (unsigned *)malloc(numAccepts * sizeof(*accepts));
- in.read(numStates * sizeof(*states), states);
- in.read(numTransitions * sizeof(*transitions), transitions);
- in.read(numAccepts * sizeof(*accepts), accepts);
- }
- void AsciiDfa::setEmpty()
- {
- init(1);
- states[0].delta = 0;
- states[0].min = 255;
- states[0].max = 0;
- states[0].acceptID = NotFound;
- }
- void AsciiDfa::toXML(StringBuffer & out, unsigned detail)
- {
- out.appendf(" numStates=\"%d\" numTransitions=\"%d\"", numStates, numTransitions);
- if (detail > 100)
- {
- out.newline();
- for (unsigned i=0; i < numStates; i++)
- {
- unsigned min = states[i].min;
- unsigned max = states[i].max;
- out.append("\t\t").append(i).append(": ").append(min).append("..").append(max);
- if (states[i].accepts())
- {
- out.append(" Accepts:");
- for (unsigned k = 0;;k++)
- {
- unsigned id = getAccepts(states[i], k);
- if (id == NotFound) break;
- out.append(" ").append(id);
- }
- }
- for (unsigned j = min; j<= max; j++)
- {
- if (((j-min) & 15)==0)
- out.newline().append("\t\t\t");
- out.append(j).append("->").append(transitions[states[i].delta + j]).append(' ');
- }
- out.newline();
- }
- }
- }
- AsciiDfaBuilder::AsciiDfaBuilder(AsciiDfa & _dfa) : dfa(_dfa)
- {
- maxTransitions = 0;
- }
- void AsciiDfaBuilder::addTransition(unsigned next, unsigned nextState)
- {
- if (dfa.states[curState].min > next)
- dfa.states[curState].min = next;
- if (dfa.states[curState].max < next)
- dfa.states[curState].max = next;
- dfa.transitions[firstTransition+next] = nextState;
- }
- void AsciiDfaBuilder::init(unsigned _numStates)
- {
- dfa.init(_numStates);
- }
- void AsciiDfaBuilder::init(unsigned _numStates, unsigned approxTransitions)
- {
- dfa.init(_numStates);
- reallocTransitions(approxTransitions+256*2);
- }
- void AsciiDfaBuilder::reallocTransitions(unsigned required)
- {
- if (required > maxTransitions)
- {
- if (maxTransitions < 0x1000)
- maxTransitions = 0x1000;
- while (maxTransitions < required)
- maxTransitions += 0x1000;
- dfa.transitions = (unsigned *)realloc(dfa.transitions, maxTransitions * sizeof(*dfa.transitions));
- }
- }
- void AsciiDfaBuilder::beginState(unsigned id)
- {
- curState = id;
- dfa.states[curState].min = 255;
- dfa.states[curState].max = 0;
- dfa.states[curState].acceptID = NotFound;
- firstTransition = dfa.numTransitions;
- //ensure there are enough transitions...
- if (firstTransition + 256 > maxTransitions)
- {
- reallocTransitions(firstTransition + 256 );
- assertex(dfa.transitions);
- }
- for (unsigned i =0; i < 256; i++)
- dfa.transitions[firstTransition+i] = NotFound;
- }
- void AsciiDfaBuilder::setStateAccept(unsigned id)
- {
- AsciiDfaState & cur = dfa.states[curState];
- assertex((id & MultiAcceptMask) == 0);
- if (cur.acceptID != NotFound)
- {
- if (!(cur.acceptID & MultiAcceptMask))
- {
- accepts.append(cur.acceptID);
- cur.acceptID = (accepts.ordinality()-1)|MultiAcceptMask;
- }
- accepts.append(id);
- }
- else
- cur.acceptID = id;
- }
- void AsciiDfaBuilder::endState()
- {
- AsciiDfaState & cur = dfa.states[curState];
- if ((cur.acceptID != NotFound) && (cur.acceptID & MultiAcceptMask))
- accepts.append(NotFound);
- unsigned minEntry = cur.min;
- unsigned maxEntry = cur.max;
- if (minEntry <= maxEntry)
- {
- for (unsigned i = minEntry; i <= maxEntry; i++)
- dfa.transitions[firstTransition+i-minEntry] = dfa.transitions[firstTransition+i];
- cur.delta = firstTransition-minEntry;
- dfa.numTransitions += (maxEntry - minEntry + 1);
- }
- else
- cur.delta = 0; // no transitions from this state.
- }
- void AsciiDfaBuilder::finished()
- {
- unsigned numAccepts = accepts.ordinality();
- dfa.numAccepts = numAccepts;
- dfa.accepts = (unsigned *)malloc(sizeof(unsigned)*numAccepts);
- memcpy_iflen(dfa.accepts, accepts.getArray(), numAccepts*sizeof(unsigned));
- }
- //---------------------------------------------------------------------------
- RegexAsciiDfaPattern::RegexAsciiDfaPattern(bool _matchesToken)
- {
- matchesToken = _matchesToken;
- }
- RegexMatchAction RegexAsciiDfaPattern::match(RegexState & state)
- {
- const byte * cur = state.cur;
- const byte * end = state.end;
- unsigned activeState = 0;
- const AsciiDfaState * states = dfa.queryStates();
- unsigned * transitions = dfa.queryTransitions();
- if (matchesToken)
- {
- //MORE: Store only one because we know we could never be backtracked - e.g., because this is always a token.
- const byte * best = NULL;
- for (;;)
- {
- if (states[activeState].accepts())
- best = cur;
- if (cur == end)
- break;
- byte next = *cur++;
- if (next < states[activeState].min)
- break;
- if (next > states[activeState].max)
- break;
- activeState = transitions[states[activeState].delta + next];
- if (activeState == NotFound)
- break;
- }
- if (best)
- {
- state.cur = best;
- RegexMatchAction ret = matchNext(state);
- if (ret == RegexMatchBacktrackToken)
- ret = RegexMatchBacktrack;
- return ret;
- }
- return RegexMatchBacktrack;
- }
- else
- {
- ConstPointerArray & potentialMatches = state.cache.potentialMatches;
- unsigned prevPotentialMatches = potentialMatches.ordinality();
- for (;;)
- {
- if (states[activeState].accepts())
- potentialMatches.append(cur);
- if (cur == end)
- break;
- byte next = *cur++;
- if (next < states[activeState].min)
- break;
- if (next > states[activeState].max)
- break;
- activeState = transitions[states[activeState].delta + next];
- if (activeState == NotFound)
- break;
- }
- while (potentialMatches.ordinality() > prevPotentialMatches)
- {
- state.cur = (const byte *)potentialMatches.popGet();
- RegexMatchAction ret = matchNext(state);
- if (ret != RegexMatchBacktrack)
- {
- potentialMatches.trunc(prevPotentialMatches);
- return ret;
- }
- }
- return RegexMatchBacktrack;
- }
- }
- void RegexAsciiDfaPattern::serializePattern(MemoryBuffer & out)
- {
- RegexDfaPattern::serializePattern(out);
- dfa.serialize(out);
- out.append(matchesToken);
- }
- void RegexAsciiDfaPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexDfaPattern::deserializePattern(in);
- dfa.deserialize(in);
- in.read(matchesToken);
- }
- void RegexAsciiDfaPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexDfaPattern::toXMLattr(out, state);
- dfa.toXML(out, state.detail);
- if (matchesToken)
- out.append(" token");
- }
- void RegexAsciiDfaPattern::killStage(ActiveStage & stage, RegexState & state)
- {
- ConstPointerArray & potentialMatches = state.cache.potentialMatches;
- unsigned prevPotentialMatches = stage.extra.prevPotentialMatches;
- potentialMatches.trunc(prevPotentialMatches);
- }
- RegexMatchAction RegexAsciiDfaPattern::beginMatch(RegexState & state)
- {
- const byte * cur = state.cur;
- const byte * end = state.end;
- unsigned activeState = 0;
- const AsciiDfaState * states = dfa.queryStates();
- unsigned * transitions = dfa.queryTransitions();
- const byte * best = NULL;
- ConstPointerArray & potentialMatches = state.cache.potentialMatches;
- const unsigned prevPotentialMatches = potentialMatches.ordinality();
- for (;;)
- {
- if (states[activeState].accepts())
- {
- if (!best || matchesToken)
- best = cur;
- else
- {
- if (prevPotentialMatches == potentialMatches.ordinality())
- potentialMatches.append(best);
- potentialMatches.append(cur);
- }
- }
- if (cur == end)
- break;
- byte next = *cur++;
- if (next < states[activeState].min)
- break;
- if (next > states[activeState].max)
- break;
- activeState = transitions[states[activeState].delta + next];
- if (activeState == NotFound)
- break;
- }
- if (!best)
- return RegexMatchBacktrack;
- ActiveStage & stage = pushStage(state);
- stage.extra.prevPotentialMatches = prevPotentialMatches;
- if (matchesToken)
- stage.flags |= RFbeginToken;
- //Only a single match, therefore no need to backtrack.
- if (prevPotentialMatches == potentialMatches.ordinality())
- {
- stage.followPosition = best;
- stage.setMatched();
- }
- else
- {
- stage.setState(RSretry);
- }
- return RegexMatchContinue;
- }
- RegexMatchAction RegexAsciiDfaPattern::nextAction(ActiveStage & stage, RegexState & state)
- {
- ConstPointerArray & potentialMatches = state.cache.potentialMatches;
- unsigned prevPotentialMatches = stage.extra.prevPotentialMatches;
- assertex(prevPotentialMatches <= potentialMatches.ordinality());
- switch (stage.getState())
- {
- case RSretry:
- {
- if (prevPotentialMatches < potentialMatches.ordinality())
- {
- stage.followPosition = (const byte *)potentialMatches.popGet();
- stage.setMatched();
- return RegexMatchContinue;
- }
- return RegexPattern::nextAction(stage, state);
- }
- default:
- return RegexPattern::nextAction(stage, state);
- }
- }
- //---------------------------------------------------------------------------
- RegexUnicodeDfaPattern::RegexUnicodeDfaPattern()
- {
- }
- RegexUnicodeDfaPattern::~RegexUnicodeDfaPattern()
- {
- }
- RegexMatchAction RegexUnicodeDfaPattern::match(RegexState & state)
- {
- /*
- const byte * cur = state.cur;
- const byte * end = state.end;
- unsigned activeState = 0;
- ConstPointerArray matches;
- for (;;)
- {
- //MORE: It would be better to store only one if we knew we could never be backtracked - e.g., if this was always a token.
- if (states[activeState].accepts)
- matches.append(cur);
- if (cur == end)
- break;
- byte next = *cur++;
- if (next < states[activeState].min)
- break;
- if (next > states[activeState].max)
- break;
- activeState = transitions[states[activeState].delta + next];
- }
- while (matches.ordinality())
- {
- state.cur = (const byte *)matches.tos();
- matches.pop();
- RegexMatchAction ret = matchNext(state);
- if (ret != RegexMatchBacktrack)
- return ret;
- }
- */
- return RegexMatchBacktrack;
- }
- RegexMatchAction RegexUnicodeDfaPattern::beginMatch(RegexState & state)
- {
- UNIMPLEMENTED;
- return RegexMatchBacktrack;
- }
- void RegexUnicodeDfaPattern::serializePattern(MemoryBuffer & out)
- {
- }
- void RegexUnicodeDfaPattern::deserializePattern(MemoryBuffer & in)
- {
- }
- //---------------------------------------------------------------------------
- RegexRepeatAnyPattern::RegexRepeatAnyPattern(unsigned _low, unsigned _high, bool _minimal)
- {
- low = _low;
- high = _high;
- minimal = _minimal;
- }
- RegexMatchAction RegexRepeatAnyPattern::match(RegexState & state)
- {
- unsigned max = (size32_t)(state.end - state.cur);
- if (max > high)
- max = high;
- const byte * start = state.cur;
- if (low > max)
- return RegexMatchBacktrack;
- if (minimal)
- {
- for (unsigned i = low; i <= max; i++)
- {
- state.cur = start+i;
- RegexMatchAction ret = matchNext(state);
- if (ret != RegexMatchBacktrack)
- return ret;
- }
- return RegexMatchBacktrack;
- }
- else
- {
- unsigned i = max;
- for (;;)
- {
- state.cur = start+i;
- RegexMatchAction ret = matchNext(state);
- if (ret != RegexMatchBacktrack)
- return ret;
- if (i == low)
- return RegexMatchBacktrack;
- i--;
- }
- }
- }
- RegexMatchAction RegexRepeatAnyPattern::beginMatch(RegexState & state)
- {
- unsigned max = (size32_t)(state.end - state.cur);
- if (max > high)
- max = high;
- const byte * start = state.cur;
- if (low > max)
- return RegexMatchBacktrack;
- ActiveStage & stage = pushStage(state).setMatched();
- if (minimal)
- {
- stage.followPosition = start+low;
- stage.extra.limit = start+max;
- }
- else
- {
- stage.followPosition = start+max;
- stage.extra.limit = start+low;
- }
- return RegexMatchContinue;
- }
- RegexMatchAction RegexRepeatAnyPattern::nextAction(ActiveStage & stage, RegexState & state)
- {
- switch (stage.getState())
- {
- case RSretry:
- if (minimal)
- {
- if (stage.followPosition < stage.extra.limit)
- {
- stage.followPosition++;
- stage.setMatched();
- return RegexMatchContinue;
- }
- }
- else
- {
- if (stage.followPosition > stage.extra.limit)
- {
- stage.followPosition++;
- stage.setMatched();
- return RegexMatchContinue;
- }
- }
- return RegexPattern::nextAction(stage, state);
- default:
- return RegexPattern::nextAction(stage, state);
- }
- }
- void RegexRepeatAnyPattern::serializePattern(MemoryBuffer & out)
- {
- RegexPattern::serializePattern(out);
- out.append(low).append(high).append(minimal);
- }
- void RegexRepeatAnyPattern::deserializePattern(MemoryBuffer & in)
- {
- RegexPattern::deserializePattern(in);
- in.read(low).read(high).read(minimal);
- }
- void RegexRepeatAnyPattern::toXMLattr(StringBuffer & out, RegexXmlState & state)
- {
- RegexPattern::toXMLattr(out, state);
- out.appendf(" low=\"%u\" high=\"%u\" greedy=\"%d\"", low, high, !minimal);
- }
- //---------------------------------------------------------------------------
- RegexMatchAction RegexNamed::match(RegexState & state, RegexPattern * instance, MatchState & matched)
- {
- MatchSaveState saved;
- checkStackOverflow((size32_t)(state.cur-state.start));
- state.pushMatch(matched, saved);
- RegexMatchAction ret = match(state, instance);
- state.popMatch(saved);
- return ret;
- }
- RegexMatchAction RegexNamed::match(RegexState & state, RegexPattern * instance)
- {
- state.stack.append(*instance);
- RegexMatchAction ret = first->MATCH(state);
- state.stack.pop();
- return ret;
- }
- void RegexNamed::serializeLinks(MemoryBuffer & out, RegexSerializeState & state)
- {
- serializeLink(out, first, state);
- }
- void RegexNamed::dispose()
- {
- disposeLink(first);
- }
- void RegexNamed::gather(RegexSerializeState & state)
- {
- if (state.named.find(*this) == NotFound)
- {
- state.named.append(OLINK(*this));
- first->gather(state);
- }
- }
- void RegexNamed::deserializeLinks(MemoryBuffer & in, RegexSerializeState & state)
- {
- first.setown(deserializeLink(in, state));
- }
- void RegexNamed::serializePattern(MemoryBuffer & out)
- {
- if (name)
- {
- StringBuffer lowerName;
- lowerName.append(str(name)).toLowerCase();
- out.append(lowerName.str());
- }
- else
- out.append(str(name));
- out.append(id);
- }
- void RegexNamed::deserializePattern(MemoryBuffer & in)
- {
- ::deserialize(in, name);
- in.read(id);
- }
- void graphToXML(StringBuffer & out, RegexXmlState & state, RegexPattern * first)
- {
- state.reset();
- state.addLink(*first);
- while (state.toVisit.ordinality())
- {
- RegexPattern & next = state.toVisit.item(0);
- state.toVisit.remove(0, true);
- state.visited.append(next);
- next.toXML(out, state);
- }
- }
- void RegexNamed::toXML(StringBuffer & out, RegexXmlState & state)
- {
- StringBuffer lowerName;
- lowerName.append(str(name)).toLowerCase();
- out.appendf("<named id=\"%d\" name=\"%s\" matchid=\"%d\" first=\"%d\">", (unsigned)state.named.find(*this), lowerName.str(), id, (unsigned)state.patterns.find(*first)).newline();
- graphToXML(out, state, first);
- //first->toXML(out, state);
- out.append("</named>").newline();
- }
- RegexMatchAction RegexNamed::beginMatch(RegexState & state)
- {
- return first->beginMatch(state);
- }
- //-----------------------------------------------------------------------
- void regexToXml(StringBuffer & out, RegexPattern * root, unsigned detail)
- {
- RegexXmlState state;
- state.detail = detail;
- root->gather(state);
- out.appendf("<regex root=\"%d\">", (unsigned)state.patterns.find(*root)).newline();
- graphToXML(out, state, root);
- ForEachItemIn(in, state.named)
- state.named.item(in).toXML(out, state);
- out.append("</regex>").newline();
- }
- void serializeRegex(MemoryBuffer & out, RegexPattern * root)
- {
- RegexSerializeState state;
- root->gather(state);
- unsigned version = REGEX_VERSION;
- out.append(version);
- out.append((unsigned)state.patterns.ordinality());
- out.append((unsigned)state.named.ordinality());
- ForEachItemIn(ip, state.patterns)
- state.patterns.item(ip).serializePattern(out);
- ForEachItemIn(in, state.named)
- state.named.item(in).serializePattern(out);
- ForEachItemIn(ip2, state.patterns)
- state.patterns.item(ip2).serializeLinks(out, state);
- ForEachItemIn(in2, state.named)
- state.named.item(in2).serializeLinks(out, state);
- ForEachItemIn(i, state.patterns)
- state.patterns.item(i).clearGathered();
- }
- RegexPattern * deserializeRegex(MemoryBuffer & in)
- {
- RegexSerializeState state;
- unsigned idx;
- unsigned version;
- unsigned numPatterns, numNamed;
- in.read(version);
- if (version != REGEX_VERSION)
- throwError(REGEXERR_IncompatibleVersion);
- in.read(numPatterns);
- in.read(numNamed);
- for (idx=0; idx < numPatterns; idx++)
- {
- byte _kind;
- ThorRegexKind kind;
- in.read(_kind);
- kind = (ThorRegexKind)_kind;
- RegexPattern * next;
- switch (kind)
- {
- case ThorRegexNull: next = new RegexNullPattern(); break;
- case ThorRegexAnyChar: next = new RegexAnyCharPattern(); break;
- case ThorRegexAsciiDFA: next = new RegexAsciiDfaPattern(); break;
- // case ThorRegexIDFA: next = new RegexIDFAPattern(); break;
- case ThorRegexAscii: next = new RegexAsciiPattern(); break;
- case ThorRegexAsciiI: next = new RegexAsciiIPattern(); break;
- case ThorRegexAsciiSet: next = new RegexAsciiSetPattern(); break;
- case ThorRegexAsciiISet: next = new RegexAsciiISetPattern(); break;
- #ifdef _USE_ICU
- case ThorRegexUnicode: next = new RegexUnicodePattern(); break;
- case ThorRegexUnicodeI: next = new RegexUnicodeIPattern(); break;
- case ThorRegexUnicodeSet: next = new RegexUnicodeSetPattern(); break;
- case ThorRegexUtf8: next = new RegexUtf8Pattern(); break;
- case ThorRegexUtf8I: next = new RegexUtf8IPattern(); break;
- // case ThorRegexUnicodeISet: next = new RegexUnicodeISetPattern(); break;
- #else
- case ThorRegexUnicode:
- case ThorRegexUnicodeI:
- case ThorRegexUnicodeSet:
- case ThorRegexUtf8:
- case ThorRegexUtf8I:
- rtlThrowNoUnicode();
- #endif
- case ThorRegexStart: next = new RegexStartPattern(); break;
- case ThorRegexFinish: next = new RegexFinishPattern(); break;
- case ThorRegexBeginToken: next = new RegexBeginTokenPattern(); break;
- case ThorRegexEndToken: next = new RegexEndTokenPattern(); break;
- case ThorRegexBeginSeparator:next = new RegexBeginSeparatorPattern(); break;
- case ThorRegexEndSeparator: next = new RegexEndSeparatorPattern(); break;
- case ThorRegexRepeat: next = new RegexRepeatPattern(); break;
- case ThorRegexCheck: next = new RegexCheckInPattern(); break;
- case ThorRegexCheckLength: next = new RegexCheckLengthPattern(); break;
- case ThorRegexBeginCheck: next = new RegexBeginCheckPattern(); break;
- case ThorRegexAssertNext: next = new RegexAssertNextPattern(); break;
- case ThorRegexAssertPrev: next = new RegexAssertPrevPattern(); break;
- case ThorRegexNamed: next = new RegexNamedPattern(); break;
- case ThorRegexEndNested: next = new RegexEndNestedPattern(); break;
- case ThorRegexDone: next = new RegexDonePattern(); break;
- case ThorRegexValidateAscAsAsc: next = new RegexValidateAscAsAscPattern(); break;
- case ThorRegexValidateUniAsAsc: next = new RegexValidateUniAsAscPattern(); break;
- case ThorRegexValidateUtf8AsAsc: next = new RegexValidateUtf8AsAscPattern(); break;
- case ThorRegexValidateAscAsUni: next = new RegexValidateAscAsUniPattern(); break;
- case ThorRegexValidateUniAsUni: next = new RegexValidateUniAsUniPattern(); break;
- case ThorRegexValidateUtf8AsUni: next = new RegexValidateUtf8AsUniPattern(); break;
- case ThorRegexRecursive: next = new RegexRecursivePattern(); break;
- case ThorRegexEndRecursive: next = new RegexEndRecursivePattern(); break;
- case ThorRegexPenalty: next = new RegexPenaltyPattern(); break;
- case ThorRegexRepeatAny: next = new RegexRepeatAnyPattern(); break;
- default:
- UNIMPLEMENTED;
- }
- next->deserializePattern(in);
- state.patterns.append(*next);
- }
- for (idx=0; idx < numNamed; idx++)
- {
- RegexNamed * next = new RegexNamed();
- next->deserializePattern(in);
- state.named.append(*next);
- }
- for (idx=0; idx < numPatterns; idx++)
- state.patterns.item(idx).deserializeLinks(in, state);
- for (idx=0; idx < numNamed; idx++)
- state.named.item(idx).deserializeLinks(in, state);
- return LINK(&state.patterns.item(0));
- }
- //---------------------------------------------------------------------------
- RegexMatchState * RegexStateCache::createState(RegexNamed * def)
- {
- if (matchStates.ordinality())
- {
- RegexMatchState * ret = &matchStates.popGet();
- ret->reset(def);
- return ret;
- }
- return new RegexMatchState(def);
- }
- void RegexStateCache::destroyState(RegexMatchState * state)
- {
- matchStates.append(*state);
- }
- RegexMatchStateSave * RegexStateCache::createStateSave(RegexNamed * def)
- {
- if (matchStateSaves.ordinality())
- {
- RegexMatchStateSave * ret = &matchStateSaves.popGet();
- ret->reset(def);
- return ret;
- }
- return new RegexMatchStateSave(def);
- }
- RegexMatchStateSave * RegexStateCache::createStateSave(IAtom * _name, regexid_t _id)
- {
- if (matchStateSaves.ordinality())
- {
- RegexMatchStateSave * ret = &matchStateSaves.popGet();
- ret->reset(_name, _id);
- return ret;
- }
- return new RegexMatchStateSave(_name, _id);
- }
- void RegexStateCache::destroyStateSave(RegexMatchStateSave * state)
- {
- matchStateSaves.append(*state);
- }
- void RegexState::processPattern(RegexPattern * grammar)
- {
- if (implementation == NLPAregexStack)
- {
- grammar->MATCH(*this);
- return;
- }
- RegexMatchAction action = grammar->beginMatch(*this);
- switch (action)
- {
- case RegexMatchDone:
- while (hasActiveStage())
- popStage();
- return;
- case RegexMatchBacktrack:
- case RegexMatchContinue:
- break;
- case RegexMatchBacktrackToken:
- throwUnexpected();
- break;
- }
- while (hasActiveStage())
- {
- #ifdef TRACE_REGEX
- StringBuffer itemText;
- itemText.appendf("[%p]", topStage().pattern);
- #endif
- action = topStage().nextAction(*this);
- #ifdef TRACE_REGEX
- DBGLOG("%*s%snextAction returned %s", patternDepth, "", itemText.str(), resultText[action]);
- #endif
- switch (action)
- {
- case RegexMatchDone:
- {
- while (hasActiveStage())
- popStage();
- return;
- }
- case RegexMatchContinue:
- case RegexMatchBacktrack:
- break;
- case RegexMatchBacktrackToken:
- {
- bool finished = false;
- do
- {
- finished = topStage().isBeginToken();
- popStage();
- } while (!finished);
- break;
- }
- }
- }
- assertex(namedStack.ordinality() == 0);
- assertex(curMatch == &top);
- }
- ActiveStage & RegexState::pushStage()
- {
- curActiveStage++;
- if (!stages.isItem(curActiveStage))
- {
- ActiveStage temp;
- //initialise not needed, but it stops a warning from the compiler
- temp.pattern = NULL;
- temp.state = RSinit;
- stages.append(temp);
- }
- return stages.element(curActiveStage);
- }
- void RegexState::popStage()
- {
- #ifdef TRACE_REGEX
- ActiveStage & tos = topStage();
- StringBuffer t;
- tos.pattern->getTraceText(t);
- DBGLOG("%*s[%p]Pop %s", --patternDepth, "", tos.pattern, t.str());
- #endif
- stages.element(curActiveStage).cleanup(*this);
- curActiveStage--;
- }
- /*
- RegexMatchAction RegexDfa::beginMatch(RegexState & state)
- {
- //walk to find matches
- if (only one then save it).
- if (>1 create a list and add all items onto it)
- if (matched)
- {
- if (single)
- {
- }
- else
- {
- state.pushState(this).setStage(RSretry);
- newState->extra.matches = matches;
- }
-
- state.namedAction.append(*end);
- return firstElement->beginMatch(state);
- }
- RegexMatchAction RegexDfa::nextAction(ActiveStage & stage, RegexState & state)
- {
- if (stage.extra.matches->ordinality())
- {
- state.cur = stage.extra.matches.pop();
- stage.setMatched();
- return RegexMatchContinue;
- }
- return RegexMatchBacktrack;
- }
- */
-
- //---------------------------------------------------------------------------
- RegexMatchInfo * RegexMatches::createMatch()
- {
- RegexMatchInfo * row = new RegexMatchInfo(NULL);
- results.append(*row);
- return row;
- }
- void RegexMatches::reset()
- {
- results.kill();
- }
- //---------------------------------------------------------------------------
- RegexAlgorithm::RegexAlgorithm(IOutputMetaData * _outRecordSize, byte _kind) : NlpAlgorithm(new CRegexMatchedResultInfo)
- {
- outRecordSize.set(_outRecordSize);
- kind = _kind;
- }
- RegexAlgorithm::~RegexAlgorithm()
- {
- if (grammar)
- grammar->dispose();
- }
- INlpParser * RegexAlgorithm::createParser(ICodeContext * ctx, unsigned activityId, INlpHelper * helper, IHThorParseArg * arg)
- {
- return new RegexParser(ctx, this, helper, activityId);
- }
- void RegexAlgorithm::init(IHThorParseArg & arg)
- {
- }
- void RegexAlgorithm::serialize(MemoryBuffer & out)
- {
- out.append(kind);
- NlpAlgorithm::serialize(out);
- out.append(minPatternLength);
- serializeRegex(out, grammar);
- }
- void RegexAlgorithm::deserialize(MemoryBuffer & in)
- {
- NlpAlgorithm::deserialize(in);
- in.read(minPatternLength);
- grammar.setown(deserializeRegex(in));
- }
- INlpParseAlgorithm * createRegexParser(MemoryBuffer & buffer, IOutputMetaData * outRecordSize, byte kind)
- {
- RegexAlgorithm * ret = new RegexAlgorithm(outRecordSize, kind);
- ret->deserialize(buffer);
- return ret;
- }
- void RegexAlgorithm::match(RegexState & state)
- {
- state.processPattern(grammar);
- }
- //---------------------------------------------------------------------------
- RegexParser::RegexParser(ICodeContext * ctx, RegexAlgorithm * _algo, INlpHelper * _helper, unsigned _activityId) : matched(_algo->matchInfo)
- {
- algo = LINK(_algo);
- IOutputMetaData * outputMeta = algo->outRecordSize;
- outputAllocator.setown(ctx->getRowAllocator(outputMeta, _activityId));
- helper = _helper;
- results.first();
- charWidth = algo->charWidth;
- }
- RegexParser::~RegexParser()
- {
- matched.kill();
- algo->Release();
- }
- bool RegexParser::performMatch(IMatchedAction & action, const void * row, unsigned len, const void * data)
- {
- try
- {
- results.reset();
- len *= charWidth;
- size32_t maxSize = algo->maxLength*charWidth;
- const byte * start = (const byte *)data;
- RegexState state(cache, algo->kind, helper, this, algo->inputFormat, len, start);
- state.row = row;
- state.processor = &action;
- state.best = NULL;
- if (len >= algo->minPatternLength)
- {
- const byte * endData = start + len;
- const byte * end = endData - algo->minPatternLength;
- for (const byte * curScan = start; curScan <= end;)
- {
- state.cur = curScan;
- state.top.start = curScan;
- state.nextScanPosition = NULL;
- state.score = 0;
- if (!algo->singleChoicePerLine)
- state.best = NULL;
- if ((size32_t)(endData - curScan) > maxSize)
- {
- state.end = curScan + (maxSize + charWidth);
- state.lengthIsLimited = true;
- }
- else
- {
- state.end = endData;
- state.lengthIsLimited = false;
- }
- algo->match(state);
- if (state.numMatched >= algo->keepLimit)
- break;
- if (state.numMatched > algo->atMostLimit)
- {
- results.reset();
- return false;
- }
- if (algo->scanAction == INlpParseAlgorithm::NlpScanWhole)
- break;
- if (state.numMatched && (algo->scanAction == INlpParseAlgorithm::NlpScanNone))
- break;
- if (state.nextScanPosition && (algo->scanAction == INlpParseAlgorithm::NlpScanNext) && (curScan != state.nextScanPosition))
- curScan = state.nextScanPosition;
- else
- curScan += charWidth;
- }
- }
- if (state.numMatched == 0)
- {
- if (algo->notMatchedOnly || algo->notMatched)
- {
- //Create a row where nothing matches.
- MatchState & top = state.top;
- top.end = top.start;
- matched.extractResults(top, state.start, algo->addedSeparators);
- NlpMatchWalker walker(&top);
-
- const void * matchRow = createMatchRow(state, walker);
- if (matchRow)
- results.appendOwnResult(matchRow);
- }
- }
- else if (algo->notMatchedOnly)
- {
- results.reset();
- }
- //Now reduce the number of matches according to min/max/best
- return results.first();
- }
- catch (IException *)
- {
- throw;
- }
- catch (...)
- {
- throwError1(REGEXERR_MatchFailure, 0);
- return false;
- }
- }
- const void * RegexParser::createMatchRow(RegexState & state, NlpMatchWalker & walker)
- {
- RtlDynamicRowBuilder row(outputAllocator);
- unsigned rowSize = state.processor->onMatch(row, state.row, &matched, &walker);
- if (rowSize)
- return row.finalizeRowClear(rowSize);
- return NULL;
- }
-
- bool RegexParser::onMatch(NlpState & _state)
- {
- if ((algo->scanAction == INlpParseAlgorithm::NlpScanWhole) && (_state.cur != _state.end))
- return false;
- RegexState & state = (RegexState &)_state;
- if (state.lengthIsLimited && state.cur == state.end)
- return false;
- MatchState & top = state.top;
- const byte * end = top.end;
- unsigned length = (size32_t)(end - top.start);
- RegexMatchInfo * result = NULL;
- if (algo->chooseMin || algo->chooseMax || algo->chooseBest)
- {
- RegexMatchInfo * best = state.best;
- if (best)
- {
- int comp = 0;
- if (algo->chooseMin)
- comp = (int)(length - best->length);
- else if (algo->chooseMax)
- comp = (int)(best->length - length);
- if (algo->chooseBest && (comp == 0))
- comp = (int)(best->score - state.score);
- if (comp >= 0)
- return false;
- }
- else
- {
- state.best = results.createMatch();
- state.numMatched++;
- }
- result = state.best;
- state.nextScanPosition = end;
- }
- else
- {
- if (!state.nextScanPosition || state.nextScanPosition > end)
- state.nextScanPosition = end;
- }
- matched.extractResults(top, state.start, algo->addedSeparators);
- NlpMatchWalker walker(&top);
- const void * newRow = createMatchRow(state, walker);
- if (!newRow)
- return false;
- if (!result)
- {
- result = results.appendOwnResult(newRow);
- state.numMatched++;
- }
- else
- {
- result->setown(newRow);
- }
-
- result->score = state.score;
- result->length = length;
- if (algo->matchAction == INlpParseAlgorithm::NlpMatchAll)
- {
- if (state.numMatched >= algo->keepLimit)
- return true;
- if (state.numMatched > algo->atMostLimit)
- return true;
- return false;
- }
- return true;
- }
- /*
- #if 0
- RegexMatchAction RegexDFAPattern::match(MatchState & state)
- {
- const byte * savedCur = state.cur;
- while (!fail)
- {
- if (consume & in a match state), add it to a list else fail
- else
- }
- ForEachItemInrev(matches)
- {
- state.cur =matches.item(idx);
- if (matchNext(state) == RegexMatchDone)
- return RegexMatchDone;
- }
- state.cur = savedCur;
- return RegexMatchBacktrack;
- }
- Converting a NFA:
- States, transition(symbol)->*states
- to a DFA
- States, transition(symbol)->state
- Create a set of set-of-nstates Dstates that can be reached from the initial.
- ForEachUnmarkedDState(T)
- ForEachSymbol(x),
- U = possible states that could be reach after that
- if U not in DStates, add it.
- Save DTrans[T,a] = U
- End
- End
- All states that can be reached at all onto a stack
- regular expressions:
- *+? have highest
- then concat
- then
-
- r|(s|t) == (r|s)|t
- (rs)t == r(st)
- r(s|t) == rs|rt
- er == r == re
- r* = (r|e)*
- r** = r*
- Regular expression to NFA:
- Fairly simple - gives a list of Node(All transitions and actions)
- Running a NFA:
- Simple algorithmn maintains a sets of possible states. So all calculated at the same time.
- - Solves problem of repeatadly searching, but I don't think it could be used for matching text,
- because no positioning information is maintained.
- - Use an ordered list of next-states which
- Lazy
- }}}
- #endif
- */
|