op public repos

Blob

Date:: Mon Dec 27 00:38:59 2004 UTC
Message:: change to use new thread library
Actions:: History | Blame | Raw File
1 #include <u.h>
2 #include <libc.h>
3 #include <draw.h>
4 #include <thread.h>
5 #include <cursor.h>
6 #include <mouse.h>
7 #include <keyboard.h>
8 #include <frame.h>
9 #include <fcall.h>
10 #include <plumb.h>
11 #include "dat.h"
12 #include "fns.h"
13 
14 Rangeset	sel;
15 Rune		*lastregexp;
16 
17 /*
18  * Machine Information
19  */
20 typedef struct Inst Inst;
21 struct Inst
22 {
23 	uint	type;	/* < 0x10000 ==> literal, otherwise action */
24 	union {
25 		int sid;
26 		int subid;
27 		int class;
28 		Inst *other;
29 		Inst *right;
30 	} u;
31 	union{
32 		Inst *left;
33 		Inst *next;
34 	} u1;
35 };
36 
37 #define	NPROG	1024
38 Inst	program[NPROG];
39 Inst	*progp;
40 Inst	*startinst;	/* First inst. of program; might not be program[0] */
41 Inst	*bstartinst;	/* same for backwards machine */
42 Channel	*rechan;	/* chan(Inst*) */
43 
44 typedef struct Ilist Ilist;
45 struct Ilist
46 {
47 	Inst	*inst;		/* Instruction of the thread */
48 	Rangeset se;
49 	uint	startp;		/* first char of match */
50 };
51 
52 #define	NLIST	128
53 
54 Ilist	*tl, *nl;	/* This list, next list */
55 Ilist	list[2][NLIST];
56 static	Rangeset sempty;
57 
58 /*
59  * Actions and Tokens
60  *
61  *	0x100xx are operators, value == precedence
62  *	0x200xx are tokens, i.e. operands for operators
63  */
64 #define	OPERATOR	0x10000	/* Bitmask of all operators */
65 #define	START		0x10000	/* Start, used for marker on stack */
66 #define	RBRA		0x10001	/* Right bracket, ) */
67 #define	LBRA		0x10002	/* Left bracket, ( */
68 #define	OR		0x10003	/* Alternation, | */
69 #define	CAT		0x10004	/* Concatentation, implicit operator */
70 #define	STAR		0x10005	/* Closure, * */
71 #define	PLUS		0x10006	/* a+ == aa* */
72 #define	QUEST		0x10007	/* a? == a|nothing, i.e. 0 or 1 a's */
73 #define	ANY		0x20000	/* Any character but newline, . */
74 #define	NOP		0x20001	/* No operation, internal use only */
75 #define	BOL		0x20002	/* Beginning of line, ^ */
76 #define	EOL		0x20003	/* End of line, $ */
77 #define	CCLASS		0x20004	/* Character class, [] */
78 #define	NCCLASS		0x20005	/* Negated character class, [^] */
79 #define	END		0x20077	/* Terminate: match found */
80 
81 #define	ISATOR		0x10000
82 #define	ISAND		0x20000
83 
84 /*
85  * Parser Information
86  */
87 typedef struct Node Node;
88 struct Node
89 {
90 	Inst	*first;
91 	Inst	*last;
92 };
93 
94 #define	NSTACK	20
95 Node	andstack[NSTACK];
96 Node	*andp;
97 int	atorstack[NSTACK];
98 int	*atorp;
99 int	lastwasand;	/* Last token was operand */
100 int	cursubid;
101 int	subidstack[NSTACK];
102 int	*subidp;
103 int	backwards;
104 int	nbra;
105 Rune	*exprp;		/* pointer to next character in source expression */
106 #define	DCLASS	10	/* allocation increment */
107 int	nclass;		/* number active */
108 int	Nclass;		/* high water mark */
109 Rune	**class;
110 int	negateclass;
111 
112 void	addinst(Ilist *l, Inst *inst, Rangeset *sep);
113 void	newmatch(Rangeset*);
114 void	bnewmatch(Rangeset*);
115 void	pushand(Inst*, Inst*);
116 void	pushator(int);
117 Node	*popand(int);
118 int	popator(void);
119 void	startlex(Rune*);
120 int	lex(void);
121 void	operator(int);
122 void	operand(int);
123 void	evaluntil(int);
124 void	optimize(Inst*);
125 void	bldcclass(void);
126 
127 void
128 rxinit(void)
129 {
130 	rechan = chancreate(sizeof(Inst*), 0);
131 	chansetname(rechan, "rechan");
132 	lastregexp = runemalloc(1);
133 }
134 
135 void
136 regerror(char *e)
137 {
138 	lastregexp[0] = 0;
139 	warning(nil, "regexp: %s\n", e);
140 	sendp(rechan, nil);
141 	threadexits(nil);
142 }
143 
144 Inst *
145 newinst(int t)
146 {
147 	if(progp >= &program[NPROG])
148 		regerror("expression too long");
149 	progp->type = t;
150 	progp->u1.left = nil;
151 	progp->u.right = nil;
152 	return progp++;
153 }
154 
155 void
156 realcompile(void *arg)
157 {
158 	int token;
159 	Rune *s;
160 
161 	threadsetname("regcomp");
162 	s = arg;
163 	startlex(s);
164 	atorp = atorstack;
165 	andp = andstack;
166 	subidp = subidstack;
167 	cursubid = 0;
168 	lastwasand = FALSE;
169 	/* Start with a low priority operator to prime parser */
170 	pushator(START-1);
171 	while((token=lex()) != END){
172 		if((token&ISATOR) == OPERATOR)
173 			operator(token);
174 		else
175 			operand(token);
176 	}
177 	/* Close with a low priority operator */
178 	evaluntil(START);
179 	/* Force END */
180 	operand(END);
181 	evaluntil(START);
182 	if(nbra)
183 		regerror("unmatched `('");
184 	--andp;	/* points to first and only operand */
185 	sendp(rechan, andp->first);
186 	threadexits(nil);
187 }
188 
189 /* r is null terminated */
190 int
191 rxcompile(Rune *r)
192 {
193 	int i, nr;
194 	Inst *oprogp;
195 
196 	nr = runestrlen(r)+1;
197 	if(runeeq(lastregexp, runestrlen(lastregexp)+1, r, nr)==TRUE)
198 		return TRUE;
199 	lastregexp[0] = 0;
200 	for(i=0; i<nclass; i++)
201 		free(class[i]);
202 	nclass = 0;
203 	progp = program;
204 	backwards = FALSE;
205 	bstartinst = nil;
206 	threadcreate(realcompile, r, STACK);
207 	startinst = recvp(rechan);
208 	if(startinst == nil)
209 		return FALSE;
210 	optimize(program);
211 	oprogp = progp;
212 	backwards = TRUE;
213 	threadcreate(realcompile, r, STACK);
214 	bstartinst = recvp(rechan);
215 	if(bstartinst == nil)
216 		return FALSE;
217 	optimize(oprogp);
218 	lastregexp = runerealloc(lastregexp, nr);
219 	runemove(lastregexp, r, nr);
220 	return TRUE;
221 }
222 
223 void
224 operand(int t)
225 {
226 	Inst *i;
227 	if(lastwasand)
228 		operator(CAT);	/* catenate is implicit */
229 	i = newinst(t);
230 	if(t == CCLASS){
231 		if(negateclass)
232 			i->type = NCCLASS;	/* UGH */
233 		i->u.class = nclass-1;		/* UGH */
234 	}
235 	pushand(i, i);
236 	lastwasand = TRUE;
237 }
238 
239 void
240 operator(int t)
241 {
242 	if(t==RBRA && --nbra<0)
243 		regerror("unmatched `)'");
244 	if(t==LBRA){
245 		cursubid++;	/* silently ignored */
246 		nbra++;
247 		if(lastwasand)
248 			operator(CAT);
249 	}else
250 		evaluntil(t);
251 	if(t!=RBRA)
252 		pushator(t);
253 	lastwasand = FALSE;
254 	if(t==STAR || t==QUEST || t==PLUS || t==RBRA)
255 		lastwasand = TRUE;	/* these look like operands */
256 }
257 
258 void
259 pushand(Inst *f, Inst *l)
260 {
261 	if(andp >= &andstack[NSTACK])
262 		error("operand stack overflow");
263 	andp->first = f;
264 	andp->last = l;
265 	andp++;
266 }
267 
268 void
269 pushator(int t)
270 {
271 	if(atorp >= &atorstack[NSTACK])
272 		error("operator stack overflow");
273 	*atorp++=t;
274 	if(cursubid >= NRange)
275 		*subidp++= -1;
276 	else
277 		*subidp++=cursubid;
278 }
279 
280 Node *
281 popand(int op)
282 {
283 	char buf[64];
284 
285 	if(andp <= &andstack[0])
286 		if(op){
287 			sprint(buf, "missing operand for %c", op);
288 			regerror(buf);
289 		}else
290 			regerror("malformed regexp");
291 	return --andp;
292 }
293 
294 int
295 popator()
296 {
297 	if(atorp <= &atorstack[0])
298 		error("operator stack underflow");
299 	--subidp;
300 	return *--atorp;
301 }
302 
303 void
304 evaluntil(int pri)
305 {
306 	Node *op1, *op2, *t;
307 	Inst *inst1, *inst2;
308 
309 	while(pri==RBRA || atorp[-1]>=pri){
310 		switch(popator()){
311 		case LBRA:
312 			op1 = popand('(');
313 			inst2 = newinst(RBRA);
314 			inst2->u.subid = *subidp;
315 			op1->last->u1.next = inst2;
316 			inst1 = newinst(LBRA);
317 			inst1->u.subid = *subidp;
318 			inst1->u1.next = op1->first;
319 			pushand(inst1, inst2);
320 			return;		/* must have been RBRA */
321 		default:
322 			error("unknown regexp operator");
323 			break;
324 		case OR:
325 			op2 = popand('|');
326 			op1 = popand('|');
327 			inst2 = newinst(NOP);
328 			op2->last->u1.next = inst2;
329 			op1->last->u1.next = inst2;
330 			inst1 = newinst(OR);
331 			inst1->u.right = op1->first;
332 			inst1->u1.left = op2->first;
333 			pushand(inst1, inst2);
334 			break;
335 		case CAT:
336 			op2 = popand(0);
337 			op1 = popand(0);
338 			if(backwards && op2->first->type!=END){
339 				t = op1;
340 				op1 = op2;
341 				op2 = t;
342 			}
343 			op1->last->u1.next = op2->first;
344 			pushand(op1->first, op2->last);
345 			break;
346 		case STAR:
347 			op2 = popand('*');
348 			inst1 = newinst(OR);
349 			op2->last->u1.next = inst1;
350 			inst1->u.right = op2->first;
351 			pushand(inst1, inst1);
352 			break;
353 		case PLUS:
354 			op2 = popand('+');
355 			inst1 = newinst(OR);
356 			op2->last->u1.next = inst1;
357 			inst1->u.right = op2->first;
358 			pushand(op2->first, inst1);
359 			break;
360 		case QUEST:
361 			op2 = popand('?');
362 			inst1 = newinst(OR);
363 			inst2 = newinst(NOP);
364 			inst1->u1.left = inst2;
365 			inst1->u.right = op2->first;
366 			op2->last->u1.next = inst2;
367 			pushand(inst1, inst2);
368 			break;
369 		}
370 	}
371 }
372 
373 
374 void
375 optimize(Inst *start)
376 {
377 	Inst *inst, *target;
378 
379 	for(inst=start; inst->type!=END; inst++){
380 		target = inst->u1.next;
381 		while(target->type == NOP)
382 			target = target->u1.next;
383 		inst->u1.next = target;
384 	}
385 }
386 
387 void
388 startlex(Rune *s)
389 {
390 	exprp = s;
391 	nbra = 0;
392 }
393 
394 
395 int
396 lex(void){
397 	int c;
398 
399 	c = *exprp++;
400 	switch(c){
401 	case '\\':
402 		if(*exprp)
403 			if((c= *exprp++)=='n')
404 				c='\n';
405 		break;
406 	case 0:
407 		c = END;
408 		--exprp;	/* In case we come here again */
409 		break;
410 	case '*':
411 		c = STAR;
412 		break;
413 	case '?':
414 		c = QUEST;
415 		break;
416 	case '+':
417 		c = PLUS;
418 		break;
419 	case '|':
420 		c = OR;
421 		break;
422 	case '.':
423 		c = ANY;
424 		break;
425 	case '(':
426 		c = LBRA;
427 		break;
428 	case ')':
429 		c = RBRA;
430 		break;
431 	case '^':
432 		c = BOL;
433 		break;
434 	case '$':
435 		c = EOL;
436 		break;
437 	case '[':
438 		c = CCLASS;
439 		bldcclass();
440 		break;
441 	}
442 	return c;
443 }
444 
445 int
446 nextrec(void)
447 {
448 	if(exprp[0]==0 || (exprp[0]=='\\' && exprp[1]==0))
449 		regerror("malformed `[]'");
450 	if(exprp[0] == '\\'){
451 		exprp++;
452 		if(*exprp=='n'){
453 			exprp++;
454 			return '\n';
455 		}
456 		return *exprp++|0x10000;
457 	}
458 	return *exprp++;
459 }
460 
461 void
462 bldcclass(void)
463 {
464 	int c1, c2, n, na;
465 	Rune *classp;
466 
467 	classp = runemalloc(DCLASS);
468 	n = 0;
469 	na = DCLASS;
470 	/* we have already seen the '[' */
471 	if(*exprp == '^'){
472 		classp[n++] = '\n';	/* don't match newline in negate case */
473 		negateclass = TRUE;
474 		exprp++;
475 	}else
476 		negateclass = FALSE;
477 	while((c1 = nextrec()) != ']'){
478 		if(c1 == '-'){
479     Error:
480 			free(classp);
481 			regerror("malformed `[]'");
482 		}
483 		if(n+4 >= na){		/* 3 runes plus NUL */
484 			na += DCLASS;
485 			classp = runerealloc(classp, na);
486 		}
487 		if(*exprp == '-'){
488 			exprp++;	/* eat '-' */
489 			if((c2 = nextrec()) == ']')
490 				goto Error;
491 			classp[n+0] = 0xFFFF;
492 			classp[n+1] = c1;
493 			classp[n+2] = c2;
494 			n += 3;
495 		}else
496 			classp[n++] = c1;
497 	}
498 	classp[n] = 0;
499 	if(nclass == Nclass){
500 		Nclass += DCLASS;
501 		class = realloc(class, Nclass*sizeof(Rune*));
502 	}
503 	class[nclass++] = classp;
504 }
505 
506 int
507 classmatch(int classno, int c, int negate)
508 {
509 	Rune *p;
510 
511 	p = class[classno];
512 	while(*p){
513 		if(*p == 0xFFFF){
514 			if(p[1]<=c && c<=p[2])
515 				return !negate;
516 			p += 3;
517 		}else if(*p++ == c)
518 			return !negate;
519 	}
520 	return negate;
521 }
522 
523 /*
524  * Note optimization in addinst:
525  * 	*l must be pending when addinst called; if *l has been looked
526  *		at already, the optimization is a bug.
527  */
528 void
529 addinst(Ilist *l, Inst *inst, Rangeset *sep)
530 {
531 	Ilist *p;
532 
533 	for(p = l; p->inst; p++){
534 		if(p->inst==inst){
535 			if((sep)->r[0].q0 < p->se.r[0].q0)
536 				p->se= *sep;	/* this would be bug */
537 			return;	/* It's already there */
538 		}
539 	}
540 	p->inst = inst;
541 	p->se= *sep;
542 	(p+1)->inst = nil;
543 }
544 
545 int
546 rxnull(void)
547 {
548 	return startinst==nil || bstartinst==nil;
549 }
550 
551 /* either t!=nil or r!=nil, and we match the string in the appropriate place */
552 int
553 rxexecute(Text *t, Rune *r, uint startp, uint eof, Rangeset *rp)
554 {
555 	int flag;
556 	Inst *inst;
557 	Ilist *tlp;
558 	uint p;
559 	int nnl, ntl;
560 	int nc, c;
561 	int wrapped;
562 	int startchar;
563 
564 	flag = 0;
565 	p = startp;
566 	startchar = 0;
567 	wrapped = 0;
568 	nnl = 0;
569 	if(startinst->type<OPERATOR)
570 		startchar = startinst->type;
571 	list[0][0].inst = list[1][0].inst = nil;
572 	sel.r[0].q0 = -1;
573 	if(t != nil)
574 		nc = t->file->b.nc;
575 	else
576 		nc = runestrlen(r);
577 	/* Execute machine once for each character */
578 	for(;;p++){
579 	doloop:
580 		if(p>=eof || p>=nc){
581 			switch(wrapped++){
582 			case 0:		/* let loop run one more click */
583 			case 2:
584 				break;
585 			case 1:		/* expired; wrap to beginning */
586 				if(sel.r[0].q0>=0 || eof!=Infinity)
587 					goto Return;
588 				list[0][0].inst = list[1][0].inst = nil;
589 				p = 0;
590 				goto doloop;
591 			default:
592 				goto Return;
593 			}
594 			c = 0;
595 		}else{
596 			if(((wrapped && p>=startp) || sel.r[0].q0>0) && nnl==0)
597 				break;
598 			if(t != nil)
599 				c = textreadc(t, p);
600 			else
601 				c = r[p];
602 		}
603 		/* fast check for first char */
604 		if(startchar && nnl==0 && c!=startchar)
605 			continue;
606 		tl = list[flag];
607 		nl = list[flag^=1];
608 		nl->inst = nil;
609 		ntl = nnl;
610 		nnl = 0;
611 		if(sel.r[0].q0<0 && (!wrapped || p<startp || startp==eof)){
612 			/* Add first instruction to this list */
613 			if(++ntl >= NLIST){
614 	Overflow:
615 				warning(nil, "regexp list overflow\n");
616 				sel.r[0].q0 = -1;
617 				goto Return;
618 			}
619 			sempty.r[0].q0 = p;
620 			addinst(tl, startinst, &sempty);
621 		}
622 		/* Execute machine until this list is empty */
623 		for(tlp = tl; inst = tlp->inst; tlp++){	/* assignment = */
624 	Switchstmt:
625 			switch(inst->type){
626 			default:	/* regular character */
627 				if(inst->type==c){
628 	Addinst:
629 					if(++nnl >= NLIST)
630 						goto Overflow;
631 					addinst(nl, inst->u1.next, &tlp->se);
632 				}
633 				break;
634 			case LBRA:
635 				if(inst->u.subid>=0)
636 					tlp->se.r[inst->u.subid].q0 = p;
637 				inst = inst->u1.next;
638 				goto Switchstmt;
639 			case RBRA:
640 				if(inst->u.subid>=0)
641 					tlp->se.r[inst->u.subid].q1 = p;
642 				inst = inst->u1.next;
643 				goto Switchstmt;
644 			case ANY:
645 				if(c!='\n')
646 					goto Addinst;
647 				break;
648 			case BOL:
649 				if(p==0 || (t!=nil && textreadc(t, p-1)=='\n') || (r!=nil && r[p-1]=='\n')){
650 	Step:
651 					inst = inst->u1.next;
652 					goto Switchstmt;
653 				}
654 				break;
655 			case EOL:
656 				if(c == '\n')
657 					goto Step;
658 				break;
659 			case CCLASS:
660 				if(c>=0 && classmatch(inst->u.class, c, 0))
661 					goto Addinst;
662 				break;
663 			case NCCLASS:
664 				if(c>=0 && classmatch(inst->u.class, c, 1))
665 					goto Addinst;
666 				break;
667 			case OR:
668 				/* evaluate right choice later */
669 				if(++ntl >= NLIST)
670 					goto Overflow;
671 				addinst(tlp, inst->u.right, &tlp->se);
672 				/* efficiency: advance and re-evaluate */
673 				inst = inst->u1.left;
674 				goto Switchstmt;
675 			case END:	/* Match! */
676 				tlp->se.r[0].q1 = p;
677 				newmatch(&tlp->se);
678 				break;
679 			}
680 		}
681 	}
682     Return:
683 	*rp = sel;
684 	return sel.r[0].q0 >= 0;
685 }
686 
687 void
688 newmatch(Rangeset *sp)
689 {
690 	if(sel.r[0].q0<0 || sp->r[0].q0<sel.r[0].q0 ||
691 	   (sp->r[0].q0==sel.r[0].q0 && sp->r[0].q1>sel.r[0].q1))
692 		sel = *sp;
693 }
694 
695 int
696 rxbexecute(Text *t, uint startp, Rangeset *rp)
697 {
698 	int flag;
699 	Inst *inst;
700 	Ilist *tlp;
701 	int p;
702 	int nnl, ntl;
703 	int c;
704 	int wrapped;
705 	int startchar;
706 
707 	flag = 0;
708 	nnl = 0;
709 	wrapped = 0;
710 	p = startp;
711 	startchar = 0;
712 	if(bstartinst->type<OPERATOR)
713 		startchar = bstartinst->type;
714 	list[0][0].inst = list[1][0].inst = nil;
715 	sel.r[0].q0= -1;
716 	/* Execute machine once for each character, including terminal NUL */
717 	for(;;--p){
718 	doloop:
719 		if(p <= 0){
720 			switch(wrapped++){
721 			case 0:		/* let loop run one more click */
722 			case 2:
723 				break;
724 			case 1:		/* expired; wrap to end */
725 				if(sel.r[0].q0>=0)
726 					goto Return;
727 				list[0][0].inst = list[1][0].inst = nil;
728 				p = t->file->b.nc;
729 				goto doloop;
730 			case 3:
731 			default:
732 				goto Return;
733 			}
734 			c = 0;
735 		}else{
736 			if(((wrapped && p<=startp) || sel.r[0].q0>0) && nnl==0)
737 				break;
738 			c = textreadc(t, p-1);
739 		}
740 		/* fast check for first char */
741 		if(startchar && nnl==0 && c!=startchar)
742 			continue;
743 		tl = list[flag];
744 		nl = list[flag^=1];
745 		nl->inst = nil;
746 		ntl = nnl;
747 		nnl = 0;
748 		if(sel.r[0].q0<0 && (!wrapped || p>startp)){
749 			/* Add first instruction to this list */
750 			if(++ntl >= NLIST){
751 	Overflow:
752 				warning(nil, "regexp list overflow\n");
753 				sel.r[0].q0 = -1;
754 				goto Return;
755 			}
756 			/* the minus is so the optimizations in addinst work */
757 			sempty.r[0].q0 = -p;
758 			addinst(tl, bstartinst, &sempty);
759 		}
760 		/* Execute machine until this list is empty */
761 		for(tlp = tl; inst = tlp->inst; tlp++){	/* assignment = */
762 	Switchstmt:
763 			switch(inst->type){
764 			default:	/* regular character */
765 				if(inst->type == c){
766 	Addinst:
767 					if(++nnl >= NLIST)
768 						goto Overflow;
769 					addinst(nl, inst->u1.next, &tlp->se);
770 				}
771 				break;
772 			case LBRA:
773 				if(inst->u.subid>=0)
774 					tlp->se.r[inst->u.subid].q0 = p;
775 				inst = inst->u1.next;
776 				goto Switchstmt;
777 			case RBRA:
778 				if(inst->u.subid >= 0)
779 					tlp->se.r[inst->u.subid].q1 = p;
780 				inst = inst->u1.next;
781 				goto Switchstmt;
782 			case ANY:
783 				if(c != '\n')
784 					goto Addinst;
785 				break;
786 			case BOL:
787 				if(c=='\n' || p==0){
788 	Step:
789 					inst = inst->u1.next;
790 					goto Switchstmt;
791 				}
792 				break;
793 			case EOL:
794 				if(p<t->file->b.nc && textreadc(t, p)=='\n')
795 					goto Step;
796 				break;
797 			case CCLASS:
798 				if(c>0 && classmatch(inst->u.class, c, 0))
799 					goto Addinst;
800 				break;
801 			case NCCLASS:
802 				if(c>0 && classmatch(inst->u.class, c, 1))
803 					goto Addinst;
804 				break;
805 			case OR:
806 				/* evaluate right choice later */
807 				if(++ntl >= NLIST)
808 					goto Overflow;
809 				addinst(tlp, inst->u.right, &tlp->se);
810 				/* efficiency: advance and re-evaluate */
811 				inst = inst->u1.left;
812 				goto Switchstmt;
813 			case END:	/* Match! */
814 				tlp->se.r[0].q0 = -tlp->se.r[0].q0; /* minus sign */
815 				tlp->se.r[0].q1 = p;
816 				bnewmatch(&tlp->se);
817 				break;
818 			}
819 		}
820 	}
821     Return:
822 	*rp = sel;
823 	return sel.r[0].q0 >= 0;
824 }
825 
826 void
827 bnewmatch(Rangeset *sp)
828 {
829         int  i;
830 
831         if(sel.r[0].q0<0 || sp->r[0].q0>sel.r[0].q1 || (sp->r[0].q0==sel.r[0].q1 && sp->r[0].q1<sel.r[0].q0))
832                 for(i = 0; i<NRange; i++){       /* note the reversal; q0<=q1 */
833                         sel.r[i].q0 = sp->r[i].q1;
834                         sel.r[i].q1 = sp->r[i].q0;
835                 }
836 }