From: Matt Armstrong <matt+dated+1010799012.80728c@...>
Date: 2002-01-07T10:30:17+09:00
Subject: [ruby-talk:30391] Efficient "lexing" in Ruby (maybe an RCR?)

I notice that many of the Ruby packages that do hard core parsing make
use of the strscan library for extra speed.

This is mainly because the Regexp#match matches on the whole string,
so if you want to match starting at an arbitrary position, you must
create a substring.  Parsing a large string this way can create a lot
of intermediate copies of the same string, stressing memory use.

For example, today if you have something in a string and want to break
it into tokens, where the set of tokens is described by many different
regexps, the easiest thing to do is something like this:

    loop {
        case string
        when ""
            break
        when regexp1
            # do something
            string = $POSTMATCH
        when regexp2
            # do something
            string = $POSTMATCH
        ...
        end
    }

This is also similar to what rscan.rb in the strscan library does for
the Ruby-only version of the strscan API.

Since this is a fairly common thing to do (witness the number of users
of strscan) could we change Regexp#match to take an optional starting
offset?  Then the code could be:

    offset = 0
    loop {
        if offset == string.length
            break
        elsif m = regexp1.match(string, offset)
            # do something
            offset = m.begin(0)
        elsif m = regexp2.match(string, offset)
            # do something
            offset = m.begin(0)
        end
    }

Or Regexp#match could even take a range to specify a substring to
match.

Here is a patch that adds a match_offset method to Regexp.  It is just
like match except that it takes an offset.  This is just meant to
illustrate how easy such a feature would be to implement.  ;-)

===================================================================
RCS file: /src/ruby/re.c,v
retrieving revision 1.54
diff -u -r1.54 re.c
--- re.c	2002/01/04 14:14:35	1.54
+++ re.c	2002/01/07 01:25:56
@@ -1042,6 +1042,27 @@
 }
 
 static VALUE
+rb_reg_match_m_offset(re, str, offset)
+    VALUE re, str, offset;
+{
+    int start;
+    VALUE result;
+    
+    Check_Type(offset, T_FIXNUM);
+    if (NIL_P(str)) {
+	return Qnil;
+    }
+    StringValue(str);
+    start = rb_reg_search(re, str, FIX2INT(offset), 0);
+    if (start < 0) {
+	return Qnil;
+    }
+    result = rb_backref_get();
+    rb_match_busy(result);
+    return result;
+}
+
+static VALUE
 rb_reg_initialize_m(argc, argv, self)
     int argc;
     VALUE *argv;
@@ -1447,6 +1468,7 @@
     rb_define_method(rb_cRegexp, "===", rb_reg_match, 1);
     rb_define_method(rb_cRegexp, "~", rb_reg_match2, 0);
     rb_define_method(rb_cRegexp, "match", rb_reg_match_m, 1);
+    rb_define_method(rb_cRegexp, "match_offset", rb_reg_match_m_offset, 2);
     rb_define_method(rb_cRegexp, "to_s", rb_reg_inspect, 0);
     rb_define_method(rb_cRegexp, "inspect", rb_reg_inspect, 0);
     rb_define_method(rb_cRegexp, "source", rb_reg_source, 0);


-- 
matt