Subject: v24i021: GNU Diff, version 1.15, Part06/08 Newsgroups: comp.sources.unix Approved: rsalz@uunet.UU.NET X-Checksum-Snefru: 20d4cb87 53dcbca3 10725bbd b18999e6 Submitted-by: Paul Eggert Posting-number: Volume 24, Issue 21 Archive-name: gnudiff1.15/part06 #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh 'regex.c2' <<'END_OF_FILE' X X X X/* Like re_search_2, below, but only one string is specified, and X doesn't let you say where to stop matching. */ X Xint Xre_search (pbufp, string, size, startpos, range, regs) X struct re_pattern_buffer *pbufp; X char *string; X int size, startpos, range; X struct re_registers *regs; X{ X return re_search_2 (pbufp, (char *) 0, 0, string, size, startpos, range, X regs, size); X} X X X/* Using the compiled pattern in PBUFP->buffer, first tries to match the X virtual concatenation of STRING1 and STRING2, starting first at index X STARTPOS, then at STARTPOS + 1, and so on. RANGE is the number of X places to try before giving up. If RANGE is negative, it searches X backwards, i.e., the starting positions tried are STARTPOS, STARTPOS X - 1, etc. STRING1 and STRING2 are of SIZE1 and SIZE2, respectively. X In REGS, return the indices of the virtual concatenation of STRING1 X and STRING2 that matched the entire PBUFP->buffer and its contained X subexpressions. Do not consider matching one past the index MSTOP in X the virtual concatenation of STRING1 and STRING2. X X The value returned is the position in the strings at which the match X was found, or -1 if no match was found, or -2 if error (such as X failure stack overflow). */ X Xint Xre_search_2 (pbufp, string1, size1, string2, size2, startpos, range, X regs, mstop) X struct re_pattern_buffer *pbufp; X char *string1, *string2; X int size1, size2; X int startpos; X register int range; X struct re_registers *regs; X int mstop; X{ X register char *fastmap = pbufp->fastmap; X register unsigned char *translate = (unsigned char *) pbufp->translate; X int total_size = size1 + size2; X int endpos = startpos + range; X int val; X X /* Check for out-of-range starting position. */ X if (startpos < 0 || startpos > total_size) X return -1; X X /* Fix up range if it would eventually take startpos outside of the X virtual concatenation of string1 and string2. */ X if (endpos < -1) X range = -1 - startpos; X else if (endpos > total_size) X range = total_size - startpos; X X /* Update the fastmap now if not correct already. */ X if (fastmap && !pbufp->fastmap_accurate) X re_compile_fastmap (pbufp); X X /* If the search isn't to be a backwards one, don't waste time in a X long search for a pattern that says it is anchored. */ X if (pbufp->used > 0 && (enum regexpcode) pbufp->buffer[0] == begbuf X && range > 0) X { X if (startpos > 0) X return -1; X else X range = 1; X } X X while (1) X { X /* If a fastmap is supplied, skip quickly over characters that X cannot possibly be the start of a match. Note, however, that X if the pattern can possibly match the null string, we must X test it at each starting point so that we take the first null X string we get. */ X X if (fastmap && startpos < total_size && pbufp->can_be_null != 1) X { X if (range > 0) /* Searching forwards. */ X { X register int lim = 0; X register unsigned char *p; X int irange = range; X if (startpos < size1 && startpos + range >= size1) X lim = range - (size1 - startpos); X X p = ((unsigned char *) X &(startpos >= size1 ? string2 - size1 : string1)[startpos]); X X while (range > lim && !fastmap[translate X ? translate[*p++] X : *p++]) X range--; X startpos += irange - range; X } X else /* Searching backwards. */ X { X register unsigned char c; X X if (string1 == 0 || startpos >= size1) X c = string2[startpos - size1]; X else X c = string1[startpos]; X X c &= 0xff; X if (translate ? !fastmap[translate[c]] : !fastmap[c]) X goto advance; X } X } X X if (range >= 0 && startpos == total_size X && fastmap && pbufp->can_be_null == 0) X return -1; X X val = re_match_2 (pbufp, string1, size1, string2, size2, startpos, X regs, mstop); X if (val >= 0) X return startpos; X if (val == -2) X return -2; X X#ifdef C_ALLOCA X alloca (0); X#endif /* C_ALLOCA */ X X advance: X if (!range) X break; X else if (range > 0) X { X range--; X startpos++; X } X else X { X range++; X startpos--; X } X } X return -1; X} X X X X#ifndef emacs /* emacs never uses this. */ Xint Xre_match (pbufp, string, size, pos, regs) X struct re_pattern_buffer *pbufp; X char *string; X int size, pos; X struct re_registers *regs; X{ X return re_match_2 (pbufp, (char *) 0, 0, string, size, pos, regs, size); X} X#endif /* not emacs */ X X X/* The following are used for re_match_2, defined below: */ X X/* Roughly the maximum number of failure points on the stack. Would be X exactly that if always pushed MAX_NUM_FAILURE_ITEMS each time we failed. */ X Xint re_max_failures = 2000; X X/* Routine used by re_match_2. */ Xstatic int bcmp_translate (); X X X/* Structure and accessing macros used in re_match_2: */ X Xstruct register_info X{ X unsigned is_active : 1; X unsigned matched_something : 1; X}; X X#define IS_ACTIVE(R) ((R).is_active) X#define MATCHED_SOMETHING(R) ((R).matched_something) X X X/* Macros used by re_match_2: */ X X X/* I.e., regstart, regend, and reg_info. */ X X#define NUM_REG_ITEMS 3 X X/* We push at most this many things on the stack whenever we X fail. The `+ 2' refers to PATTERN_PLACE and STRING_PLACE, which are X arguments to the PUSH_FAILURE_POINT macro. */ X X#define MAX_NUM_FAILURE_ITEMS (RE_NREGS * NUM_REG_ITEMS + 2) X X X/* We push this many things on the stack whenever we fail. */ X X#define NUM_FAILURE_ITEMS (last_used_reg * NUM_REG_ITEMS + 2) X X X/* This pushes most of the information about the current state we will want X if we ever fail back to it. */ X X#define PUSH_FAILURE_POINT(pattern_place, string_place) \ X { \ X short last_used_reg, this_reg; \ X \ X /* Find out how many registers are active or have been matched. \ X (Aside from register zero, which is only set at the end.) */ \ X for (last_used_reg = RE_NREGS - 1; last_used_reg > 0; last_used_reg--)\ X if (regstart[last_used_reg] != (unsigned char *) -1) \ X break; \ X \ X if (stacke - stackp < NUM_FAILURE_ITEMS) \ X { \ X unsigned char **stackx; \ X if (stacke - stackb > re_max_failures * MAX_NUM_FAILURE_ITEMS) \ X return -2; \ X \ X /* Roughly double the size of the stack. */ \ X stackx = (unsigned char **) alloca (2 * MAX_NUM_FAILURE_ITEMS \ X * (stacke - stackb) \ X * sizeof (unsigned char *));\ X /* Only copy what is in use. */ \ X bcopy (stackb, stackx, (stackp - stackb) * sizeof (char *)); \ X stackp = stackx + (stackp - stackb); \ X stackb = stackx; \ X stacke = stackb + 2 * MAX_NUM_FAILURE_ITEMS * (stacke - stackb);\ X } \ X \ X /* Now push the info for each of those registers. */ \ X for (this_reg = 1; this_reg <= last_used_reg; this_reg++) \ X { \ X *stackp++ = regstart[this_reg]; \ X *stackp++ = regend[this_reg]; \ X *stackp++ = (unsigned char *) ®_info[this_reg]; \ X } \ X \ X /* Push how many registers we saved. */ \ X *stackp++ = (unsigned char *) last_used_reg; \ X \ X *stackp++ = pattern_place; \ X *stackp++ = string_place; \ X } X X X/* This pops what PUSH_FAILURE_POINT pushes. */ X X#define POP_FAILURE_POINT() \ X { \ X int temp; \ X stackp -= 2; /* Remove failure points. */ \ X temp = (int) *--stackp; /* How many regs pushed. */ \ X temp *= NUM_REG_ITEMS; /* How much to take off the stack. */ \ X stackp -= temp; /* Remove the register info. */ \ X } X X X#define MATCHING_IN_FIRST_STRING (dend == end_match_1) X X/* Is true if there is a first string and if PTR is pointing anywhere X inside it or just past the end. */ X X#define IS_IN_FIRST_STRING(ptr) \ X (size1 && string1 <= (ptr) && (ptr) <= string1 + size1) X X/* Call before fetching a character with *d. This switches over to X string2 if necessary. */ X X#define PREFETCH \ X while (d == dend) \ X { \ X /* end of string2 => fail. */ \ X if (dend == end_match_2) \ X goto fail; \ X /* end of string1 => advance to string2. */ \ X d = string2; \ X dend = end_match_2; \ X } X X X/* Call this when have matched something; it sets `matched' flags for the X registers corresponding to the subexpressions of which we currently X are inside. */ X#define SET_REGS_MATCHED \ X { unsigned this_reg; \ X for (this_reg = 0; this_reg < RE_NREGS; this_reg++) \ X { \ X if (IS_ACTIVE(reg_info[this_reg])) \ X MATCHED_SOMETHING(reg_info[this_reg]) = 1; \ X else \ X MATCHED_SOMETHING(reg_info[this_reg]) = 0; \ X } \ X } X X/* Test if at very beginning or at very end of the virtual concatenation X of string1 and string2. If there is only one string, we've put it in X string2. */ X X#define AT_STRINGS_BEG (d == (size1 ? string1 : string2) || !size2) X#define AT_STRINGS_END (d == end2) X X#define AT_WORD_BOUNDARY \ X (AT_STRINGS_BEG || AT_STRINGS_END || IS_A_LETTER (d - 1) != IS_A_LETTER (d)) X X/* We have two special cases to check for: X 1) if we're past the end of string1, we have to look at the first X character in string2; X 2) if we're before the beginning of string2, we have to look at the X last character in string1; we assume there is a string1, so use X this in conjunction with AT_STRINGS_BEG. */ X#define IS_A_LETTER(d) \ X (SYNTAX ((d) == end1 ? *string2 : (d) == string2 - 1 ? *(end1 - 1) : *(d))\ X == Sword) X X X/* Match the pattern described by PBUFP against the virtual X concatenation of STRING1 and STRING2, which are of SIZE1 and SIZE2, X respectively. Start the match at index POS in the virtual X concatenation of STRING1 and STRING2. In REGS, return the indices of X the virtual concatenation of STRING1 and STRING2 that matched the X entire PBUFP->buffer and its contained subexpressions. Do not X consider matching one past the index MSTOP in the virtual X concatenation of STRING1 and STRING2. X X If pbufp->fastmap is nonzero, then it had better be up to date. X X The reason that the data to match are specified as two components X which are to be regarded as concatenated is so this function can be X used directly on the contents of an Emacs buffer. X X -1 is returned if there is no match. -2 is returned if there is an X error (such as match stack overflow). Otherwise the value is the X length of the substring which was matched. */ X Xint Xre_match_2 (pbufp, string1_arg, size1, string2_arg, size2, pos, regs, mstop) X struct re_pattern_buffer *pbufp; X char *string1_arg, *string2_arg; X int size1, size2; X int pos; X struct re_registers *regs; X int mstop; X{ X register unsigned char *p = (unsigned char *) pbufp->buffer; X X /* Pointer to beyond end of buffer. */ X register unsigned char *pend = p + pbufp->used; X X unsigned char *string1 = (unsigned char *) string1_arg; X unsigned char *string2 = (unsigned char *) string2_arg; X unsigned char *end1; /* Just past end of first string. */ X unsigned char *end2; /* Just past end of second string. */ X X /* Pointers into string1 and string2, just past the last characters in X each to consider matching. */ X unsigned char *end_match_1, *end_match_2; X X register unsigned char *d, *dend; X register int mcnt; /* Multipurpose. */ X unsigned char *translate = (unsigned char *) pbufp->translate; X unsigned is_a_jump_n = 0; X X /* Failure point stack. Each place that can handle a failure further X down the line pushes a failure point on this stack. It consists of X restart, regend, and reg_info for all registers corresponding to the X subexpressions we're currently inside, plus the number of such X registers, and, finally, two char *'s. The first char * is where to X resume scanning the pattern; the second one is where to resume X scanning the strings. If the latter is zero, the failure point is a X ``dummy''; if a failure happens and the failure point is a dummy, it X gets discarded and the next next one is tried. */ X X unsigned char *initial_stack[MAX_NUM_FAILURE_ITEMS * NFAILURES]; X unsigned char **stackb = initial_stack; X unsigned char **stackp = stackb; X unsigned char **stacke = &stackb[MAX_NUM_FAILURE_ITEMS * NFAILURES]; X X X /* Information on the contents of registers. These are pointers into X the input strings; they record just what was matched (on this X attempt) by a subexpression part of the pattern, that is, the X regnum-th regstart pointer points to where in the pattern we began X matching and the regnum-th regend points to right after where we X stopped matching the regnum-th subexpression. (The zeroth register X keeps track of what the whole pattern matches.) */ X X unsigned char *regstart[RE_NREGS]; X unsigned char *regend[RE_NREGS]; X X /* The is_active field of reg_info helps us keep track of which (possibly X nested) subexpressions we are currently in. The matched_something X field of reg_info[reg_num] helps us tell whether or not we have X matched any of the pattern so far this time through the reg_num-th X subexpression. These two fields get reset each time through any X loop their register is in. */ X X struct register_info reg_info[RE_NREGS]; X X X /* The following record the register info as found in the above X variables when we find a match better than any we've seen before. X This happens as we backtrack through the failure points, which in X turn happens only if we have not yet matched the entire string. */ X X unsigned best_regs_set = 0; X unsigned char *best_regstart[RE_NREGS]; X unsigned char *best_regend[RE_NREGS]; X X X /* Initialize subexpression text positions to -1 to mark ones that no X \( or ( and \) or ) has been seen for. Also set all registers to X inactive and mark them as not having matched anything or ever X failed. */ X for (mcnt = 0; mcnt < RE_NREGS; mcnt++) X { X regstart[mcnt] = regend[mcnt] = (unsigned char *) -1; X IS_ACTIVE (reg_info[mcnt]) = 0; X MATCHED_SOMETHING (reg_info[mcnt]) = 0; X } X X if (regs) X for (mcnt = 0; mcnt < RE_NREGS; mcnt++) X regs->start[mcnt] = regs->end[mcnt] = -1; X X /* Set up pointers to ends of strings. X Don't allow the second string to be empty unless both are empty. */ X if (size2 == 0) X { X string2 = string1; X size2 = size1; X string1 = 0; X size1 = 0; X } X end1 = string1 + size1; X end2 = string2 + size2; X X /* Compute where to stop matching, within the two strings. */ X if (mstop <= size1) X { X end_match_1 = string1 + mstop; X end_match_2 = string2; X } X else X { X end_match_1 = end1; X end_match_2 = string2 + mstop - size1; X } X X /* `p' scans through the pattern as `d' scans through the data. `dend' X is the end of the input string that `d' points within. `d' is X advanced into the following input string whenever necessary, but X this happens before fetching; therefore, at the beginning of the X loop, `d' can be pointing at the end of a string, but it cannot X equal string2. */ X X if (size1 != 0 && pos <= size1) X d = string1 + pos, dend = end_match_1; X else X d = string2 + pos - size1, dend = end_match_2; X X X /* This loops over pattern commands. It exits by returning from the X function if match is complete, or it drops through if match fails X at this starting point in the input data. */ X X while (1) X { X is_a_jump_n = 0; X /* End of pattern means we might have succeeded. */ X if (p == pend) X { X /* If not end of string, try backtracking. Otherwise done. */ X if (d != end_match_2) X { X if (stackp != stackb) X { X /* More failure points to try. */ X X unsigned in_same_string = X IS_IN_FIRST_STRING (best_regend[0]) X == MATCHING_IN_FIRST_STRING; X X /* If exceeds best match so far, save it. */ X if (! best_regs_set X || (in_same_string && d > best_regend[0]) X || (! in_same_string && ! MATCHING_IN_FIRST_STRING)) X { X best_regs_set = 1; X best_regend[0] = d; /* Never use regstart[0]. */ X X for (mcnt = 1; mcnt < RE_NREGS; mcnt++) X { X best_regstart[mcnt] = regstart[mcnt]; X best_regend[mcnt] = regend[mcnt]; X } X } X goto fail; X } X /* If no failure points, don't restore garbage. */ X else if (best_regs_set) X { X restore_best_regs: X /* Restore best match. */ X d = best_regend[0]; X X for (mcnt = 0; mcnt < RE_NREGS; mcnt++) X { X regstart[mcnt] = best_regstart[mcnt]; X regend[mcnt] = best_regend[mcnt]; X } X } X } X X /* If caller wants register contents data back, convert it X to indices. */ X if (regs) X { X regs->start[0] = pos; X if (MATCHING_IN_FIRST_STRING) X regs->end[0] = d - string1; X else X regs->end[0] = d - string2 + size1; X for (mcnt = 1; mcnt < RE_NREGS; mcnt++) X { X if (regend[mcnt] == (unsigned char *) -1) X { X regs->start[mcnt] = -1; X regs->end[mcnt] = -1; X continue; X } X if (IS_IN_FIRST_STRING (regstart[mcnt])) X regs->start[mcnt] = regstart[mcnt] - string1; X else X regs->start[mcnt] = regstart[mcnt] - string2 + size1; X X if (IS_IN_FIRST_STRING (regend[mcnt])) X regs->end[mcnt] = regend[mcnt] - string1; X else X regs->end[mcnt] = regend[mcnt] - string2 + size1; X } X } X return d - pos - (MATCHING_IN_FIRST_STRING X ? string1 X : string2 - size1); X } X X /* Otherwise match next pattern command. */ X#ifdef SWITCH_ENUM_BUG X switch ((int) ((enum regexpcode) *p++)) X#else X switch ((enum regexpcode) *p++) X#endif X { X X /* \( [or `(', as appropriate] is represented by start_memory, X \) by stop_memory. Both of those commands are followed by X a register number in the next byte. The text matched X within the \( and \) is recorded under that number. */ X case start_memory: X regstart[*p] = d; X IS_ACTIVE (reg_info[*p]) = 1; X MATCHED_SOMETHING (reg_info[*p]) = 0; X p++; X break; X X case stop_memory: X regend[*p] = d; X IS_ACTIVE (reg_info[*p]) = 0; X X /* If just failed to match something this time around with a sub- X expression that's in a loop, try to force exit from the loop. */ X if ((! MATCHED_SOMETHING (reg_info[*p]) X || (enum regexpcode) p[-3] == start_memory) X && (p + 1) != pend) X { X register unsigned char *p2 = p + 1; X mcnt = 0; X switch (*p2++) X { X case jump_n: X is_a_jump_n = 1; X case finalize_jump: X case maybe_finalize_jump: X case jump: X case dummy_failure_jump: X EXTRACT_NUMBER_AND_INCR (mcnt, p2); X if (is_a_jump_n) X p2 += 2; X break; X } X p2 += mcnt; X X /* If the next operation is a jump backwards in the pattern X to an on_failure_jump, exit from the loop by forcing a X failure after pushing on the stack the on_failure_jump's X jump in the pattern, and d. */ X if (mcnt < 0 && (enum regexpcode) *p2++ == on_failure_jump) X { X EXTRACT_NUMBER_AND_INCR (mcnt, p2); X PUSH_FAILURE_POINT (p2 + mcnt, d); X goto fail; X } X } X p++; X break; X X /* \ has been turned into a `duplicate' command which is X followed by the numeric value of as the register number. */ X case duplicate: X { X int regno = *p++; /* Get which register to match against */ X register unsigned char *d2, *dend2; X X /* Where in input to try to start matching. */ X d2 = regstart[regno]; X X /* Where to stop matching; if both the place to start and X the place to stop matching are in the same string, then X set to the place to stop, otherwise, for now have to use X the end of the first string. */ X X dend2 = ((IS_IN_FIRST_STRING (regstart[regno]) X == IS_IN_FIRST_STRING (regend[regno])) X ? regend[regno] : end_match_1); X while (1) X { X /* If necessary, advance to next segment in register X contents. */ X while (d2 == dend2) X { X if (dend2 == end_match_2) break; X if (dend2 == regend[regno]) break; X d2 = string2, dend2 = regend[regno]; /* end of string1 => advance to string2. */ X } X /* At end of register contents => success */ X if (d2 == dend2) break; X X /* If necessary, advance to next segment in data. */ X PREFETCH; X X /* How many characters left in this segment to match. */ X mcnt = dend - d; X X /* Want how many consecutive characters we can match in X one shot, so, if necessary, adjust the count. */ X if (mcnt > dend2 - d2) X mcnt = dend2 - d2; X X /* Compare that many; failure if mismatch, else move X past them. */ X if (translate X ? bcmp_translate (d, d2, mcnt, translate) X : bcmp (d, d2, mcnt)) X goto fail; X d += mcnt, d2 += mcnt; X } X } X break; X X case anychar: X PREFETCH; /* Fetch a data character. */ X /* Match anything but a newline, maybe even a null. */ X if ((translate ? translate[*d] : *d) == '\n' X || ((obscure_syntax & RE_DOT_NOT_NULL) X && (translate ? translate[*d] : *d) == '\000')) X goto fail; X SET_REGS_MATCHED; X d++; X break; X X case charset: X case charset_not: X { X int not = 0; /* Nonzero for charset_not. */ X register int c; X if (*(p - 1) == (unsigned char) charset_not) X not = 1; X X PREFETCH; /* Fetch a data character. */ X X if (translate) X c = translate[*d]; X else X c = *d; X X if (c < *p * BYTEWIDTH X && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH))) X not = !not; X X p += 1 + *p; X X if (!not) goto fail; X SET_REGS_MATCHED; X d++; X break; X } X X case begline: X if ((size1 != 0 && d == string1) X || (size1 == 0 && size2 != 0 && d == string2) X || (d && d[-1] == '\n') X || (size1 == 0 && size2 == 0)) X break; X else X goto fail; X X case endline: X if (d == end2 X || (d == end1 ? (size2 == 0 || *string2 == '\n') : *d == '\n')) X break; X goto fail; X X /* `or' constructs are handled by starting each alternative with X an on_failure_jump that points to the start of the next X alternative. Each alternative except the last ends with a X jump to the joining point. (Actually, each jump except for X the last one really jumps to the following jump, because X tensioning the jumps is a hassle.) */ X X /* The start of a stupid repeat has an on_failure_jump that points X past the end of the repeat text. This makes a failure point so X that on failure to match a repetition, matching restarts past X as many repetitions have been found with no way to fail and X look for another one. */ X X /* A smart repeat is similar but loops back to the on_failure_jump X so that each repetition makes another failure point. */ X X case on_failure_jump: X on_failure: X EXTRACT_NUMBER_AND_INCR (mcnt, p); X PUSH_FAILURE_POINT (p + mcnt, d); X break; X X /* The end of a smart repeat has a maybe_finalize_jump back. X Change it either to a finalize_jump or an ordinary jump. */ X case maybe_finalize_jump: X EXTRACT_NUMBER_AND_INCR (mcnt, p); X { X register unsigned char *p2 = p; X /* Compare what follows with the beginning of the repeat. X If we can establish that there is nothing that they would X both match, we can change to finalize_jump. */ X while (p2 + 1 != pend X && (*p2 == (unsigned char) stop_memory X || *p2 == (unsigned char) start_memory)) X p2 += 2; /* Skip over reg number. */ X if (p2 == pend) X p[-3] = (unsigned char) finalize_jump; X else if (*p2 == (unsigned char) exactn X || *p2 == (unsigned char) endline) X { X register int c = *p2 == (unsigned char) endline ? '\n' : p2[2]; X register unsigned char *p1 = p + mcnt; X /* p1[0] ... p1[2] are an on_failure_jump. X Examine what follows that. */ X if (p1[3] == (unsigned char) exactn && p1[5] != c) X p[-3] = (unsigned char) finalize_jump; X else if (p1[3] == (unsigned char) charset X || p1[3] == (unsigned char) charset_not) X { X int not = p1[3] == (unsigned char) charset_not; X if (c < p1[4] * BYTEWIDTH X && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH))) X not = !not; X /* `not' is 1 if c would match. */ X /* That means it is not safe to finalize. */ X if (!not) X p[-3] = (unsigned char) finalize_jump; X } X } X } X p -= 2; /* Point at relative address again. */ X if (p[-1] != (unsigned char) finalize_jump) X { X p[-1] = (unsigned char) jump; X goto nofinalize; X } X /* Note fall through. */ X X /* The end of a stupid repeat has a finalize_jump back to the X start, where another failure point will be made which will X point to after all the repetitions found so far. */ X X /* Take off failure points put on by matching on_failure_jump X because didn't fail. Also remove the register information X put on by the on_failure_jump. */ X case finalize_jump: X POP_FAILURE_POINT (); X /* Note fall through. */ X X /* Jump without taking off any failure points. */ X case jump: X nofinalize: X EXTRACT_NUMBER_AND_INCR (mcnt, p); X p += mcnt; X break; X X case dummy_failure_jump: X /* Normally, the on_failure_jump pushes a failure point, which X then gets popped at finalize_jump. We will end up at X finalize_jump, also, and with a pattern of, say, `a+', we X are skipping over the on_failure_jump, so we have to push X something meaningless for finalize_jump to pop. */ X PUSH_FAILURE_POINT (0, 0); X goto nofinalize; X X X /* Have to succeed matching what follows at least n times. Then X just handle like an on_failure_jump. */ X case succeed_n: X EXTRACT_NUMBER (mcnt, p + 2); X /* Originally, this is how many times we HAVE to succeed. */ X if (mcnt) X { X mcnt--; X p += 2; X STORE_NUMBER_AND_INCR (p, mcnt); X } X else if (mcnt == 0) X { X p[2] = unused; X p[3] = unused; X goto on_failure; X } X else X { X fprintf (stderr, "regex: the succeed_n's n is not set.\n"); X exit (1); X } X break; X X case jump_n: X EXTRACT_NUMBER (mcnt, p + 2); X /* Originally, this is how many times we CAN jump. */ X if (mcnt) X { X mcnt--; X STORE_NUMBER(p + 2, mcnt); X goto nofinalize; /* Do the jump without taking off X any failure points. */ X } X /* If don't have to jump any more, skip over the rest of command. */ X else X p += 4; X break; X X case set_number_at: X { X register unsigned char *p1; X X EXTRACT_NUMBER_AND_INCR (mcnt, p); X p1 = p + mcnt; X EXTRACT_NUMBER_AND_INCR (mcnt, p); X STORE_NUMBER (p1, mcnt); X break; X } X X /* Ignore these. Used to ignore the n of succeed_n's which X currently have n == 0. */ X case unused: X break; X X case wordbound: X if (AT_WORD_BOUNDARY) X break; X goto fail; X X case notwordbound: X if (AT_WORD_BOUNDARY) X goto fail; X break; X X case wordbeg: X if (IS_A_LETTER (d) && (!IS_A_LETTER (d - 1) || AT_STRINGS_BEG)) X break; X goto fail; X X case wordend: X /* Have to check if AT_STRINGS_BEG before looking at d - 1. */ X if (!AT_STRINGS_BEG && IS_A_LETTER (d - 1) X && (!IS_A_LETTER (d) || AT_STRINGS_END)) X break; X goto fail; X X#ifdef emacs X case before_dot: X if (PTR_CHAR_POS (d) >= point) X goto fail; X break; X X case at_dot: X if (PTR_CHAR_POS (d) != point) X goto fail; X break; X X case after_dot: X if (PTR_CHAR_POS (d) <= point) X goto fail; X break; X X case wordchar: X mcnt = (int) Sword; X goto matchsyntax; X X case syntaxspec: X mcnt = *p++; X matchsyntax: X PREFETCH; X if (SYNTAX (*d++) != (enum syntaxcode) mcnt) goto fail; X SET_REGS_MATCHED; X break; X X case notwordchar: X mcnt = (int) Sword; X goto matchnotsyntax; X X case notsyntaxspec: X mcnt = *p++; X matchnotsyntax: X PREFETCH; X if (SYNTAX (*d++) == (enum syntaxcode) mcnt) goto fail; X SET_REGS_MATCHED; X break; X X#else /* not emacs */ X X case wordchar: X PREFETCH; X if (!IS_A_LETTER (d)) X goto fail; X SET_REGS_MATCHED; X break; X X case notwordchar: X PREFETCH; X if (IS_A_LETTER (d)) X goto fail; X SET_REGS_MATCHED; X break; X X#endif /* not emacs */ X X case begbuf: X if (AT_STRINGS_BEG) X break; X goto fail; X X case endbuf: X if (AT_STRINGS_END) X break; X goto fail; X X case exactn: X /* Match the next few pattern characters exactly. X mcnt is how many characters to match. */ X mcnt = *p++; X /* This is written out as an if-else so we don't waste time X testing `translate' inside the loop. */ X if (translate) X { X do X { X PREFETCH; X if (translate[*d++] != *p++) goto fail; X } X while (--mcnt); X } X else X { X do X { X PREFETCH; X if (*d++ != *p++) goto fail; X } X while (--mcnt); X } X SET_REGS_MATCHED; X break; X } X continue; /* Successfully executed one pattern command; keep going. */ X X /* Jump here if any matching operation fails. */ X fail: X if (stackp != stackb) X /* A restart point is known. Restart there and pop it. */ X { X short last_used_reg, this_reg; X X /* If this failure point is from a dummy_failure_point, just X skip it. */ X if (!stackp[-2]) X { X POP_FAILURE_POINT (); X goto fail; X } X X d = *--stackp; X p = *--stackp; X if (d >= string1 && d <= end1) X dend = end_match_1; X /* Restore register info. */ X last_used_reg = (short) *--stackp; X X /* Make the ones that weren't saved -1 or 0 again. */ X for (this_reg = RE_NREGS - 1; this_reg > last_used_reg; this_reg--) X { X regend[this_reg] = (unsigned char *) -1; X regstart[this_reg] = (unsigned char *) -1; X IS_ACTIVE (reg_info[this_reg]) = 0; X MATCHED_SOMETHING (reg_info[this_reg]) = 0; X } X X /* And restore the rest from the stack. */ X for ( ; this_reg > 0; this_reg--) X { X reg_info[this_reg] = *(struct register_info *) *--stackp; X regend[this_reg] = *--stackp; X regstart[this_reg] = *--stackp; X } X } X else X break; /* Matching at this starting point really fails. */ X } X X if (best_regs_set) X goto restore_best_regs; X return -1; /* Failure to match. */ X} X X Xstatic int Xbcmp_translate (s1, s2, len, translate) X unsigned char *s1, *s2; X register int len; X unsigned char *translate; X{ X register unsigned char *p1 = s1, *p2 = s2; X while (len) X { X if (translate [*p1++] != translate [*p2++]) return 1; X len--; X } X return 0; X} X X X X/* Entry points compatible with 4.2 BSD regex library. */ X X#ifndef emacs X Xstatic struct re_pattern_buffer re_comp_buf; X Xchar * Xre_comp (s) X char *s; X{ X if (!s) X { X if (!re_comp_buf.buffer) X return "No previous regular expression"; X return 0; X } X X if (!re_comp_buf.buffer) X { X if (!(re_comp_buf.buffer = (char *) malloc (200))) X return "Memory exhausted"; X re_comp_buf.allocated = 200; X if (!(re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH))) X return "Memory exhausted"; X } X return re_compile_pattern (s, strlen (s), &re_comp_buf); X} X Xint Xre_exec (s) X char *s; X{ X int len = strlen (s); X return 0 <= re_search (&re_comp_buf, s, len, 0, len, X (struct re_registers *) 0); X} X#endif /* not emacs */ X X X X#ifdef test X X#include X X/* Indexed by a character, gives the upper case equivalent of the X character. */ X Xchar upcase[0400] = X { 000, 001, 002, 003, 004, 005, 006, 007, X 010, 011, 012, 013, 014, 015, 016, 017, X 020, 021, 022, 023, 024, 025, 026, 027, X 030, 031, 032, 033, 034, 035, 036, 037, X 040, 041, 042, 043, 044, 045, 046, 047, X 050, 051, 052, 053, 054, 055, 056, 057, X 060, 061, 062, 063, 064, 065, 066, 067, X 070, 071, 072, 073, 074, 075, 076, 077, X 0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107, X 0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117, X 0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127, X 0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137, X 0140, 0101, 0102, 0103, 0104, 0105, 0106, 0107, X 0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117, X 0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127, X 0130, 0131, 0132, 0173, 0174, 0175, 0176, 0177, X 0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207, X 0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217, X 0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227, X 0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237, X 0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247, X 0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257, X 0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267, X 0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277, X 0300, 0301, 0302, 0303, 0304, 0305, 0306, 0307, X 0310, 0311, 0312, 0313, 0314, 0315, 0316, 0317, X 0320, 0321, 0322, 0323, 0324, 0325, 0326, 0327, X 0330, 0331, 0332, 0333, 0334, 0335, 0336, 0337, X 0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347, X 0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357, X 0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367, X 0370, 0371, 0372, 0373, 0374, 0375, 0376, 0377 X }; X X#ifdef canned X X#include "tests.h" X Xtypedef enum { extended_test, basic_test } test_type; X X/* Use this to run the tests we've thought of. */ X Xvoid Xmain () X{ X test_type t = extended_test; X X if (t == basic_test) X { X printf ("Running basic tests:\n\n"); X test_posix_basic (); X } X else if (t == extended_test) X { X printf ("Running extended tests:\n\n"); X test_posix_extended (); X } X} X X#else /* not canned */ X X/* Use this to run interactive tests. */ X Xvoid Xmain (argc, argv) X int argc; X char **argv; X{ X char pat[80]; X struct re_pattern_buffer buf; X int i; X char c; X char fastmap[(1 << BYTEWIDTH)]; X X /* Allow a command argument to specify the style of syntax. */ X if (argc > 1) X obscure_syntax = atoi (argv[1]); X X buf.allocated = 40; X buf.buffer = (char *) malloc (buf.allocated); X buf.fastmap = fastmap; X buf.translate = upcase; X X while (1) X { X gets (pat); X X if (*pat) X { X re_compile_pattern (pat, strlen(pat), &buf); X X for (i = 0; i < buf.used; i++) X printchar (buf.buffer[i]); X X putchar ('\n'); X X printf ("%d allocated, %d used.\n", buf.allocated, buf.used); X X re_compile_fastmap (&buf); X printf ("Allowed by fastmap: "); X for (i = 0; i < (1 << BYTEWIDTH); i++) X if (fastmap[i]) printchar (i); X putchar ('\n'); X } X X gets (pat); /* Now read the string to match against */ X X i = re_match (&buf, pat, strlen (pat), 0, 0); X printf ("Match value %d.\n", i); X } X} X X#endif X X X#ifdef NOTDEF Xprint_buf (bufp) X struct re_pattern_buffer *bufp; X{ X int i; X X printf ("buf is :\n----------------\n"); X for (i = 0; i < bufp->used; i++) X printchar (bufp->buffer[i]); X X printf ("\n%d allocated, %d used.\n", bufp->allocated, bufp->used); X X printf ("Allowed by fastmap: "); X for (i = 0; i < (1 << BYTEWIDTH); i++) X if (bufp->fastmap[i]) X printchar (i); X printf ("\nAllowed by translate: "); X if (bufp->translate) X for (i = 0; i < (1 << BYTEWIDTH); i++) X if (bufp->translate[i]) X printchar (i); X printf ("\nfastmap is%s accurate\n", bufp->fastmap_accurate ? "" : "n't"); X printf ("can %s be null\n----------", bufp->can_be_null ? "" : "not"); X} X#endif /* NOTDEF */ X Xprintchar (c) X char c; X{ X if (c < 040 || c >= 0177) X { X putchar ('\\'); X putchar (((c >> 6) & 3) + '0'); X putchar (((c >> 3) & 7) + '0'); X putchar ((c & 7) + '0'); X } X else X putchar (c); X} X Xerror (string) X char *string; X{ X puts (string); X exit (1); X} X#endif /* test */ END_OF_FILE if test 37881 -ne `wc -c <'regex.c2'`; then echo shar: \"'regex.c2'\" unpacked with wrong size! fi # end of 'regex.c2' fi if test -r regex.c1 -a -r regex.c2 then echo shar: concatenating \"regex.c1\" and \"regex.c2\" into \"regex.c\" cat regex.c1 regex.c2 >regex.c || echo shar: \"regex.c\" creation failed! fi echo shar: End of archive 6 \(of 8\). cp /dev/null ark6isdone MISSING="" for I in 1 2 3 4 5 6 7 8 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 8 archives. rm -f ark[1-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0 exit 0 # Just in case...