Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commite26cb69

Browse files
committed
factor out recursion
1 parent8bee489 commite26cb69

File tree

2 files changed

+51
-47
lines changed

2 files changed

+51
-47
lines changed

‎pike.c‎

Lines changed: 48 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -83,13 +83,6 @@ enum
8383
RSPLIT,
8484
};
8585

86-
/* Return codes for re_sizecode() and re_comp() */
87-
enum {
88-
RE_SUCCESS=0,
89-
RE_SYNTAX_ERROR=-2,
90-
RE_UNSUPPORTED_SYNTAX=-3,
91-
};
92-
9386
typedefstructrsubrsub;
9487
structrsub
9588
{
@@ -184,25 +177,22 @@ void re_dumpcode(rcode *prog)
184177
prog->unilen,prog->len,prog->splits,i);
185178
}
186179

187-
/* next todo: crack and factor out this recursion,
188-
no recursion will allow to make a meta macro out
189-
of this, such that re_sizecode() becomes efficient
190-
difficulty: very high, probably not any time soon */
191-
staticint_compilecode(constchar**re_loc,rcode*prog,intsizecode)
180+
staticint_compilecode(constchar*re_loc,rcode*prog,intsizecode)
192181
{
193-
constchar*re=*re_loc;
182+
constchar*re=re_loc;
194183
int*code=sizecode ?NULL :prog->insts;
195184
intstart=PC,term=PC;
196185
intalt_label=0,c;
197-
intalt_stack[5000],altc=0;
186+
intalt_stack[4096],altc=0;
187+
intcap_stack[4096*5],capc=0;
198188

199-
for (;*re&&*re!=')';) {
189+
while (*re) {
200190
switch (*re) {
201191
case'\\':
202192
re++;
203-
if (!*re)gotosyntax_error;/* Trailing backslash */
193+
if (!*re)return-1;/* Trailing backslash */
204194
if (*re=='<'||*re=='>') {
205-
if (re-*re_loc>2&&re[-2]=='\\')
195+
if (re-re_loc>2&&re[-2]=='\\')
206196
break;
207197
EMIT(PC++,*re=='<' ?WBEG :WEND);
208198
term=PC;
@@ -230,7 +220,7 @@ static int _compilecode(const char **re_loc, rcode *prog, int sizecode)
230220
PC++;/* Skip "# of pairs" byte */
231221
for (cnt=0;*re!=']';cnt++) {
232222
if (*re=='\\')re++;
233-
if (!*re)gotosyntax_error;
223+
if (!*re)return-1;
234224
uc_code(c,re)EMIT(PC++,c);
235225
uc_len(c,re)
236226
if (re[c]=='-'&&re[c+1]!=']')
@@ -244,29 +234,42 @@ static int _compilecode(const char **re_loc, rcode *prog, int sizecode)
244234
term=PC;
245235
intsub;
246236
intcapture=1;
247-
re++;
248-
if (*re=='?') {
249-
re++;
250-
if (*re==':') {
237+
if (*(re+1)=='?') {
238+
re+=2;
239+
if (*re==':')
251240
capture=0;
252-
re++;
253-
}else {
254-
*re_loc=re;
255-
returnRE_UNSUPPORTED_SYNTAX;
256-
}
241+
else
242+
return-1;
257243
}
258244
if (capture) {
259245
sub=++prog->sub;
260246
EMIT(PC++,SAVE);
261247
EMIT(PC++,sub);
262248
}
263-
intres=_compilecode(&re,prog,sizecode);
264-
*re_loc=re;
265-
if (res<0)returnres;
266-
if (*re!=')')returnRE_SYNTAX_ERROR;
267-
if (capture) {
249+
cap_stack[capc++]=capture;
250+
cap_stack[capc++]=term;
251+
cap_stack[capc++]=alt_label;
252+
cap_stack[capc++]=start;
253+
cap_stack[capc++]=altc;
254+
alt_label=0;
255+
start=PC;
256+
break;
257+
case')':
258+
if (--capc-4<0)return-1;
259+
if (code&&alt_label) {
260+
EMIT(alt_label,REL(alt_label,PC)+1);
261+
int_altc=cap_stack[capc];
262+
for (intalts=altc;altc>_altc;altc--) {
263+
intat=alt_stack[_altc+alts-altc]+(altc-_altc)*2;
264+
EMIT(at,REL(at,PC)+1);
265+
}
266+
}
267+
start=cap_stack[--capc];
268+
alt_label=cap_stack[--capc];
269+
term=cap_stack[--capc];
270+
if (cap_stack[--capc]) {
268271
EMIT(PC++,SAVE);
269-
EMIT(PC++,sub+prog->presub+1);
272+
EMIT(PC++,code[term+1]+prog->presub+1);
270273
}
271274
break;
272275
case'{':;
@@ -300,7 +303,7 @@ static int _compilecode(const char **re_loc, rcode *prog, int sizecode)
300303
}
301304
break;
302305
case'?':
303-
if (PC==term)gotosyntax_error;
306+
if (PC==term)return-1;
304307
INSERT_CODE(term,2,PC);
305308
if (re[1]=='?') {
306309
EMIT(term,RSPLIT);
@@ -311,7 +314,7 @@ static int _compilecode(const char **re_loc, rcode *prog, int sizecode)
311314
term=PC;
312315
break;
313316
case'*':
314-
if (PC==term)gotosyntax_error;
317+
if (PC==term)return-1;
315318
INSERT_CODE(term,2,PC);
316319
EMIT(PC,JMP);
317320
EMIT(PC+1,REL(PC,term));
@@ -325,7 +328,7 @@ static int _compilecode(const char **re_loc, rcode *prog, int sizecode)
325328
term=PC;
326329
break;
327330
case'+':
328-
if (PC==term)gotosyntax_error;
331+
if (PC==term)return-1;
329332
if (re[1]=='?') {
330333
EMIT(PC,SPLIT);
331334
re++;
@@ -363,11 +366,7 @@ static int _compilecode(const char **re_loc, rcode *prog, int sizecode)
363366
EMIT(at,REL(at,PC)+1);
364367
}
365368
}
366-
*re_loc=re;
367-
returnRE_SUCCESS;
368-
syntax_error:
369-
*re_loc=re;
370-
returnRE_SYNTAX_ERROR;
369+
returncapc ?-1 :0;
371370
}
372371

373372
intre_sizecode(constchar*re,int*nsub)
@@ -376,9 +375,8 @@ int re_sizecode(const char *re, int *nsub)
376375
dummyprog.unilen=3;
377376
dummyprog.sub=0;
378377

379-
intres=_compilecode(&re,&dummyprog,1);
378+
intres=_compilecode(re,&dummyprog,1);
380379
if (res<0)returnres;
381-
if (*re)returnRE_SYNTAX_ERROR;
382380
*nsub=dummyprog.sub;
383381
returndummyprog.unilen;
384382
}
@@ -391,9 +389,8 @@ int re_comp(rcode *prog, const char *re, int nsubs)
391389
prog->presub=nsubs;
392390
prog->splits=0;
393391

394-
intres=_compilecode(&re,prog,0);
392+
intres=_compilecode(re,prog,0);
395393
if (res<0)returnres;
396-
if (*re)returnRE_SYNTAX_ERROR;
397394
inticnt=0,scnt=SPLIT;
398395
for (inti=0;i<prog->unilen;i++)
399396
switch (prog->insts[i]) {
@@ -424,7 +421,7 @@ int re_comp(rcode *prog, const char *re, int nsubs)
424421
prog->presub=sizeof(rsub)+(sizeof(char*)* (nsubs+1)*2);
425422
prog->sub=prog->presub* (prog->len-prog->splits+3);
426423
prog->sparsesz=scnt;
427-
returnRE_SUCCESS;
424+
return0;
428425
}
429426

430427
#definenewsub(init,copy) \
@@ -636,10 +633,14 @@ int main(int argc, char *argv[])
636633
intsub_els;
637634
intsz=re_sizecode(argv[1],&sub_els)*sizeof(int);
638635
printf("Precalculated size: %d\n",sz);
636+
if (sz<0) {
637+
printf("Error in re_sizecode\n");
638+
return1;
639+
}
639640
charcode[sizeof(rcode)+sz];
640641
rcode*_code= (rcode*)code;
641642
if (re_comp(_code,argv[1],sub_els)) {
642-
printf("Error in re_comp");
643+
printf("Error in re_comp\n");
643644
return1;
644645
}
645646
re_dumpcode(_code);

‎test.sh‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -171,6 +171,7 @@ aaaaa(aa)aa(aa(a)a)?aa
171171
[0-9]+.(.*)
172172
([0-9])+.(.*)
173173
(([0-9])+)(.)(.*)
174+
(abc|sjd|qwq(hs|qw|oo)|(ty|xx|pp)we)
174175
"
175176
input="\
176177
abcdef
@@ -343,6 +344,7 @@ h:98: :3234utt;strokeliin:miter;stroke-mirlimit:10;stroke-dasharray:none;strok
343344
650-253-000123434-45551221
344345
650-253-000123434-45551221
345346
650-253-000123434-455512213224hsaqer
347+
ppwe
346348
"
347349
expect="\
348350
(0,3)
@@ -515,6 +517,7 @@ expect="\
515517
(0,26)(4,26)
516518
(0,26)(2,3)(4,26)
517519
(0,36)(0,3)(2,3)(3,4)(4,36)
520+
(0,4)(0,4)(?,?)(0,2)
518521
(0,0)
519522
"
520523

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp