changelog

正则表达式库

        * regex.c (re_match_2): in on_failure_jump, if the * applied to
          a group, save the information for that group and all inner
          groups (by making it active), even though we're not inside it
          yet.

Sat Dec 14 09:50:59 1991  Karl Berry  (karl at hayley)

        * regex.c (PUSH_FAILURE_ITEM, POP_FAILURE_ITEM): new macros.
          Use them instead of copying the stack manipulating a zillion
          times.

        * regex.c (PUSH_FAILURE_POINT, pop_failure_point) [DEBUG]: save
          and restore a unique identification value for each failure point.

        * regexinc.c (partial_compiled_pattern_printer): don't print an
          extra / after duplicate commands.

        * regex.c (regex_compile): in back-reference case, allow a back
          reference to register `regnum'.  Otherwise, even `\(\)\1'
          fails, since regnum is 1 at the back-reference.

        * regex.c (re_match_2): in fail, don't examine the pattern if we
          restored to pend.

        * test_private.h: rename to private_tst.h.  Change includes.

        * regex.c (extend_bits_list): compute existing size for realloc
          in bytes, not blocks.

        * regex.c (re_match_2): in jump_past_next_alt, the for loop was
          missing its (empty) statement.  Even so, some register tests
          still fail, although in a different way than in the previous change.

Fri Dec 13 15:55:08 1991  Karl Berry  (karl at hayley)

        * regex.c (re_match_2): in jump_past_next_alt, unconditionally
          goto no_pop, since we weren't properly detecting if the
          alternative matched something anyway.  No, we need to not jump
          to keep the register values correct; just change to not look at
          register zero and not test RE_NO_EMPTY_ALTS (which is a
          compile-time thing).

        * regex.c (SET_REGS_MATCHED): start the loop at 1, since we never
          care about register zero until the very end.  (I think.)

        * regex.c (PUSH_FAILURE_POINT, pop_failure_point): go back to
          pushing and popping the active registers, instead of only doing
          the registers before a group: (fooq|fo|o)*qbar against fooqbar
          fails, since we restore back into the middle of group 1, yet it
          isn't active, because the previous restore clobbered the active flag.

Thu Dec 12 17:25:36 1991  Karl Berry  (karl at hayley)

        * regex.c (PUSH_FAILURE_POINT): do not call
          `equivalent_failure_points' after all; it causes the registers
          to be ``wrong'' (according to POSIX), and an infinite loop on
          `((a*)*)*' against `ab'.

        * regex.c (re_compile_fastmap): don't push `pend' on the failure
          stack.

Tue Dec 10 10:30:03 1991  Karl Berry  (karl at hayley)

        * regex.c (PUSH_FAILURE_POINT): if pushing same failure point that
          is on the top of the stack, fail.
        (equivalent_failure_points): new routine.

        * regex.c (re_match_2): add debug statements for every opcode we
          execute.

        * regex.c (regex_compile/handle_close): restore
          `fixup_inner_group_count' and `regnum' from the stack.

Mon Dec  9 13:51:15 1991  Karl Berry  (karl at hayley)

        * regex.c (PUSH_FAILURE_POINT): declare `this_reg' as int, so
          unsigned arithmetic doesn't happen when we don't want to save 
          the registers.

Tue Dec  3 08:11:10 1991  Karl Berry  (karl at hayley)

        * regex.c (extend_bits_list): divide size by bits/block.

        * regex.c (init_bits_list): remove redundant assignmen to
          `bits_list_ptr'.

        * regexinc.c (partial_compiled_pattern_printer): don't do *p++
          twice in the same expr.

        * regex.c (re_match_2): at on_failure_jump, use the correct
          pattern positions for getting the stuff following the start_memory.

        * regex.c (struct register_info): remove the bits_list for the
          inner groups; make that a separate variable.

Mon Dec  2 10:42:07 1991  Karl Berry  (karl at hayley)

        * regex.c (PUSH_FAILURE_POINT): don't pass `failure_stack' as an
          arg; change callers.

        * regex.c (PUSH_FAILURE_POINT): print items in order they are
          pushed.
        (pop_failure_point): likewise.

        * regex.c (main): prompt for the pattern and string.

        * regex.c (FREE_VARIABLES) [!REGEX_MALLOC]: declare as nothing;
          remove #ifdefs from around calls.

        * regex.c (extract_number, extract_number_and_incr): declare static.

        * regex.c: remove the canned main program.
        * main.c: new file.
        * Makefile (COMMON): add main.o.

Tue Sep 24 06:26:51 1991  Kathy Hargreaves  (kathy at fosse)

        * regex.c (re_match_2): Made `pend' and `dend' not register variables.
          Only set string2 to string1 if string1 isn't null.
          Send address of p, d, regstart, regend, and reg_info to
          pop_failure_point.
          Put in more debug statements.

        * regex.c [debug]: Added global variable.
          (DEBUG_*PRINT*): Only print if `debug' is true.
          (DEBUG_DOUBLE_STRING_PRINTER): Changed DEBUG_STRING_PRINTER's
          name to this.
          Changed some comments.
          (PUSH_FAILURE_POINT): Moved and added some debugging statements.
          Was saving regstart on the stack twice instead of saving both
          regstart and regend; remedied this.
          [NUM_REGS_ITEMS]: Changed from 3 to 4, as now save lowest and
          highest active registers instead of highest used one.
          [NUM_NON_REG_ITEMS]: Changed name of NUM_OTHER_ITEMS to this.
          (NUM_FAILURE_ITEMS): Use active registers instead of number 0
          through highest used one.
          (re_match_2): Have pop_failure_point put things in the variables.
          (pop_failure_point): Have it do what the fail case in re_match_2 
          did with the failure stack, instead of throwing away the stuff
          popped off.  re_match_2 can ignore results when it doesn't
          need them.
          

Thu Sep  5 13:23:28 1991  Kathy Hargreaves  (kathy at fosse)

        * regex.c (banner): Changed copyright years to be separate.
        
        * regex.c [CHAR_UNSIGNED]: Put __ at both ends of this name.
          [DEBUG, debug_count, *debug_p, DEBUG_PRINT_1, DEBUG_PRINT_2,
           DEBUG_COMPILED_PATTERN_PRINTER ,DEBUG_STRING_PRINTER]:
           defined these for debugging.
          (extract_number): Added this (debuggable) routine version of
          the macro EXTRACT_NUMBER.  Ditto for EXTRACT_NUMBER_AND_INCR.
          (re_compile_pattern): Set return_default_num_regs if the
          syntax bit RE_ALLOCATE_REGISTERS is set.
          [REGEX_MALLOC]: Renamed USE_ALLOCA to this.
          (BUF_POP): Got rid of this, as don't ever use it.
          (regex_compile): Made the type of `pattern' not be register.
          If DEBUG, print the pattern to compile.
          (re_match_2): If had a `$' in the pattern before a `^' then
          don't record the `^' as an anchor.
          Put (enum regexpcode) before references to b, as suggested
          [RE_NO_BK_BRACES]: Changed RE_NO_BK_CURLY_BRACES to this.
          (remove_pattern_offset): Removed this unused routine.
          (PUSH_FAILURE_POINT): Changed to only save active registers.
          Put in debugging statements.
          (re_compile_fastmap): Made `pattern' not a register variable.
          Use routine for extracting numbers instead of macro.
          (re_match_2): Made `p', `mcnt' and `mcnt2' not register variables.
          Added `num_regs_pushed' for debugging.
          Only malloc registers if the syntax bit RE_ALLOCATE_REGISTERS is set.
          Put in debug statements.
          Put the macro NOTE_INNER_GROUP's code inline, as it was the
          only called in one place.
          For debugging, extract numbers using routines instead of macros.
          In case fail: only restore pushed active registers, and added
          debugging statements.
          (pop_failure_point): Test for underfull stack.
          (group_can_match_nothing, common_op_can_match_nothing): For
          debugging, extract numbers using routines instead of macros.
          (regexec): Changed formal parameters to not be prototypes.
          Don't initialize `regs' or `private_preg' in their declarations.
          
Tue Jul 23 18:38:36 1991  Kathy Hargreaves  (kathy at hayley)

        * regex.h [RE_CONTEX_INDEP_OPS]: Moved the anchor stuff out of
          this bit.
          [RE_UNMATCHED_RIGHT_PAREN_ORD]: Defined this bit.
          [RE_CONTEXT_INVALID_ANCHORS]: Defined this bit.
          [RE_CONTEXT_INDEP_ANCHORS]: Defined this bit.
          Added RE_CONTEXT_INDEP_ANCHORS to all syntaxes which had
          RE_CONTEXT_INDEP_OPS. 
          Took RE_ANCHORS_ONLY_AT_ENDS out of the POSIX basic syntax.
          Added RE_UNMATCHED_RIGHT_PAREN_ORD to the POSIX extended
          syntax.
          Took RE_REPEATED_ANCHORS_AWAY out of the POSIX extended syntax.
          Defined REG_NOERROR (which will probably have to go away again).
          Changed the type `off_t' to `regoff_t'.

        * regex.c: Changed some commments.
          (regex_compile): Added variable `had_an_endline' to keep track
          of if hit a `$' since the beginning of the pattern or the last
          alternative (if any).
          Changed RE_CONTEXT_INVALID_OPS and RE_CONTEXT_INDEP_OPS to
          RE_CONTEXT_INVALID_ANCHORS and RE_CONTEXT_INDEP_ANCHORS where
          appropriate. 
          Put a `no_op' in the pattern if a repeat is only zero or one
          times; in this case and if it is many times (whereupon a jump
          backwards is pushed instead), keep track of the operator for
          verify_and_adjust_endlines.
          If RE_UNMATCHED_RIGHT_PAREN is set, make an unmatched
          close-group operator match `)'.
          Changed all error exits to exit (1).
          (remove_pattern_offset): Added this routine, but don't use it.
          (verify_and_adjust_endlines): At top of routine, if initialize
          routines run out of memory, return true after setting
          enough_memory false.
          At end of endline, et al. case, don't set *p to no_op.
          Repetition operators also set the level and active groups'
          match statuses, unless RE_REPEATED_ANCHORS_AWAY is set.
          (get_group_match_status): Put a return in front of call to get_bit.
          (re_compile_fastmap): Changed is_a_succeed_n to a boolean.
          If at end of pattern, then if the failure stack isn't empty,
          go back to the failure point.
          In *jump* case, only pop the stack if what's on top of it is
          where we've just jumped to.
          (re_search_2): Return -2 instead of val if val is -2.
          (group_can_match_nothing, alternative_can_match_nothing,
          common_op_can-match_nothing): Now pass in reg_info for the
          `duplicate' case.
          (re_match_2): Don't skip over the next alternative also if
          empty alternatives aren't allowed.
          In fail case, if failed to a backwards jump that's part of a
          repetition loop, pop the current failure point and use the
          next one.
          (pop_failure_point): Check that there's as many register items
          on the failure stack as the stack says there are.
          (common_op_can_match_nothing): Added variables `ret' and
          `reg_no' so can set reg_info for the group encountered.
          Also break without doing anything if hit a no_op or the other
          kinds of `endline's.
          If not done already, set reg_info in start_memory case.
          Put in no_pop_jump for an optimized succeed_n of zero repetitions.
          In succeed_n case, if the number isn't zero, then return false.
          Added `duplicate' case.
          
Sat Jul 13 11:27:38 1991  Kathy Hargreaves  (kathy at hayley)

        * regex.h (REG_NOERROR): Added this error code definition.
        
        * regex.c: Took some redundant parens out of macros.
          (enum regexpcode): Added jump_past_next_alt.
          Wrapped some macros in `do..while (0)'.
          Changed some comments.
          (regex_compile): Use `fixup_alt_jump' instead of `fixup_jump'.
          Use `maybe_pop_jump' instead of `maybe_pop_failure_jump'.
          Use `jump_past_next_alt' instead of `no_pop_jump' when at the
          end of an alternative.
          (re_match_2): Used REGEX_ALLOCATE for the registers stuff.
          In stop_memory case: Add more boolean tests to see if the
          group is in a loop.
          Added jump_past_next_alt case, which doesn't jump over the
          next alternative if the last one didn't match anything.
          Unfortunately, to make this work with, e.g., `(a+?*|b)*'
          against `bb', I also had to pop the alternative's failure
          point, which in turn broke backtracking!
          In fail case: Detect a dummy failure point by looking at
          failure_stack.avail - 2, not stack[-2].
          (pop_failure_point): Only pop if the stack isn't empty; don't
          give an error if it is.  (Not sure yet this is correct.)
          (group_can_match_nothing): Make it return a boolean instead of int.
          Make it take an argument indicating the end of where it should look.
          If find a group that can match nothing, set the pointer
          argument to past the group in the pattern.  
          Took out cases which can share with alternative_can_match_nothing
          and call common_op_can_match_nothing.
          Took ++ out of switch, so could call common_op_can_match_nothing.
          Wrote lots more for on_failure_jump case to handle alternatives.
          Main loop now doesn't look for matching stop_memory, but
          rather the argument END; return true if hit the matching
          stop_memory; this way can call itself for inner groups.
          (alternative_can_match_nothing): Added for alternatives.
          (common_op_can_match_nothing):  Added for previous two routines' 
          common operators.
          (regerror): Returns a message saying there's no error if gets
          sent REG_NOERROR.
          
Wed Jul  3 10:43:15 1991  Kathy Hargreaves  (kathy at hayley)

        * regex.c: Removed unnecessary enclosing parens from several macros.
          Put `do..while (0)' around a few.
          Corrected some comments.
          (INIT_FAILURE_STACK_SIZE): Deleted in favor of using
          INIT_FAILURE_ALLOC.
          (INIT_FAILURE_STACK, DOUBLE_FAILURE_STACK, PUSH_PATTERN_OP,
          PUSH_FAILURE_POINT): Made routines of the same name (but with all
          lowercase letters) into these macros, so could use `alloca'
          when USE_ALLOCA is defined.  The reason is stated below for
          bits lists.  Deleted analogous routines.
          (re_compile_fastmap): Added variable void *destination for
          PUSH_PATTERN_OP.
          (re_match_2): Added variable void *destination for REGEX_REALLOCATE.
          Used the failure stack macros in place of the routines.
          Detected a dummy failure point by inspecting the failure stack's
          (avail - 2)th element, not failure_stack.stack[-2].  This bug
          arose when used the failure stack macros instead of the routines.

        * regex.c [USE_ALLOCA]: Put this conditional around previous
          alloca stuff and defined these to work differently depending
          on whether or not USE_ALLOCA is defined:
          (REGEX_ALLOCATE): Uses either `alloca' or `malloc'.
          (REGEX_REALLOCATE): Uses either `alloca' or `realloc'.
          (INIT_BITS_LIST, EXTEND_BITS_LIST, SET_BIT_TO_VALUE): Defined
          macro versions of routines with the same name (only with all
          lowercase letters) so could use `alloc' in re_match_2.  This
          is to prevent core leaks when C-g is used in Emacs and to make
          things faster and avoid storage fragmentation.  These things
          have to be macros because the results of `alloca' go away with
          the routine by which it's called.  
          (BITS_BLOCK_SIZE, BITS_BLOCK, BITS_MASK): Moved to above the
          above-mentioned macros instea