This commit was manufactured by cvs2svn to create tag 'v1_1'.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/tags/v1_1@13 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

12 files changed, 3875 insertions, 2099 deletions

diff --git a/ext/marshal/MANIFEST b/ext/marshal/MANIFEST
deleted file mode 100644
index 54870ec71f..0000000000
--- a/ext/marshal/MANIFEST
+++ /dev/null
@@ -1,5 +0,0 @@
-MANIFEST
-depend
-extconf.rb
-marshal.c
-marshal.doc
diff --git a/ext/marshal/depend b/ext/marshal/depend
deleted file mode 100644
index c955eb2d59..0000000000
--- a/ext/marshal/depend
+++ /dev/null
@@ -1,2 +0,0 @@
-marshal.o: marshal.c ../../ruby.h ../../config.h ../../defines.h ../../io.h \
-  ../../st.h
diff --git a/ext/marshal/extconf.rb b/ext/marshal/extconf.rb
deleted file mode 100644
index ab30bd117b..0000000000
--- a/ext/marshal/extconf.rb
+++ /dev/null
@@ -1 +0,0 @@
-create_makefile("marshal")
diff --git a/ext/marshal/marshal.c b/ext/marshal/marshal.c
deleted file mode 100644
index 99e87d0b5f..0000000000
--- a/ext/marshal/marshal.c
+++ /dev/null
@@ -1,850 +0,0 @@
-/************************************************
-
-  marshal.c -
-
-  $Author$
-  $Revision$
-  $Date$
-  created at: Thu Apr 27 16:30:01 JST 1995
-
-************************************************/
-
-#include "ruby.h"
-#include "io.h"
-#include "st.h"
-
-#define MARSHAL_MAJOR   4
-#define MARSHAL_MINOR   0
-
-#define TYPE_NIL	'0'
-#define TYPE_TRUE	'T'
-#define TYPE_FALSE	'F'
-#define TYPE_FIXNUM	'i'
-
-#define TYPE_UCLASS	'C'
-#define TYPE_OBJECT	'o'
-#define TYPE_USERDEF	'u'
-#define TYPE_FLOAT	'f'
-#define TYPE_BIGNUM	'l'
-#define TYPE_STRING	'"'
-#define TYPE_REGEXP	'/'
-#define TYPE_ARRAY	'['
-#define TYPE_HASH	'{'
-#define TYPE_STRUCT	'S'
-#define TYPE_MODULE	'M'
-
-#define TYPE_SYMBOL	':'
-#define TYPE_SYMLINK	';'
-
-#define TYPE_LINK	'@'
-
-extern VALUE cString;
-extern VALUE cRegexp;
-extern VALUE cArray;
-extern VALUE cHash;
-
-VALUE rb_path2class();
-
-static ID s_dump, s_load;
-
-struct dump_arg {
-    VALUE obj;
-    FILE *fp;
-    VALUE str;
-    st_table *symbol;
-    st_table *data;
-};
-
-struct dump_call_arg {
-    VALUE obj;
-    struct dump_arg *arg;
-    int limit;
-};
-
-static void w_long _((long, struct dump_arg*));
-
-static void
-w_byte(c, arg)
-    char c;
-    struct dump_arg *arg;
-{
-    if (arg->fp) putc(c, arg->fp);
-    else str_cat(arg->str, (UCHAR*)&c, 1);
-}
-
-static void
-w_bytes(s, n, arg)
-    char *s;
-    int n;
-    struct dump_arg *arg;
-{
-    w_long(n, arg);
-    if (arg->fp) {
-	fwrite(s, 1, n, arg->fp);
-    }
-    else {
-	str_cat(arg->str, s, n);
-    }
-}
-
-static void
-w_short(x, arg)
-    int x;
-    struct dump_arg *arg;
-{
-    int i;
-
-    for (i=0; i<sizeof(USHORT); i++) {
-	w_byte((x >> (i*8)) & 0xff, arg);
-    }
-}
-
-static void
-w_long(x, arg)
-    long x;
-    struct dump_arg *arg;
-{
-    char buf[sizeof(long)+1];
-    int i, len = 0;
-
-    if (x == 0) {
-	w_byte(0, arg);
-	return;
-    }
-    for (i=1;i<sizeof(long)+1;i++) {
-	buf[i] = x & 0xff;
-	x = RSHIFT(x,8);
-	if (x == 0) {
-	    buf[0] = i;
-	    break;
-	}
-	if (x == -1) {
-	    buf[0] = -i;
-	    break;
-	}
-    }
-    len = i;
-    for (i=0;i<=len;i++) {
-	w_byte(buf[i], arg);
-    }
-}
-
-static void
-w_float(d, arg)
-    double d;
-    struct dump_arg *arg;
-{
-    char buf[100];
-
-    sprintf(buf, "%.12g", d);
-    w_bytes(buf, strlen(buf), arg);
-}
-
-static void
-w_symbol(id, arg)
-    ID id;
-    struct dump_arg *arg;
-{
-    char *sym = rb_id2name(id);
-    int num;
-
-    if (st_lookup(arg->symbol, id, &num)) {
-	w_byte(TYPE_SYMLINK, arg);
-	w_long(num, arg);
-    }
-    else {
-	w_byte(TYPE_SYMBOL, arg);
-	w_bytes(sym, strlen(sym), arg);
-	st_insert(arg->symbol, id, arg->symbol->num_entries);
-    }
-}
-
-static void
-w_unique(s, arg)
-    char *s;
-    struct dump_arg *arg;
-{
-    w_symbol(rb_intern(s), arg);
-}
-
-static void w_object _((VALUE,struct dump_arg*,int));
-extern VALUE cIO, cBignum, cStruct;
-
-static int
-hash_each(key, value, arg)
-    VALUE key, value;
-    struct dump_call_arg *arg;
-{
-    w_object(key, arg->arg, arg->limit);
-    w_object(value, arg->arg, arg->limit);
-    return ST_CONTINUE;
-}
-
-static int
-obj_each(id, value, arg)
-    ID id;
-    VALUE value;
-    struct dump_call_arg *arg;
-{
-    w_symbol(id, arg->arg);
-    w_object(value, arg->arg, arg->limit);
-    return ST_CONTINUE;
-}
-
-static void
-w_uclass(obj, class, arg)
-    VALUE obj, class;
-    struct dump_arg *arg;
-{
-    if (CLASS_OF(obj) != class) {
-	w_byte(TYPE_UCLASS, arg);
-	w_unique(rb_class2name(CLASS_OF(obj)), arg);
-    }
-}
-
-static void
-w_object(obj, arg, limit)
-    VALUE obj;
-    struct dump_arg *arg;
-    int limit;
-{
-    int n;
-    struct dump_call_arg c_arg;
-
-    if (limit == 0) {
-	Fail("exceed depth limit");
-    }
-    limit--;
-    c_arg.limit = limit;
-    c_arg.arg = arg;
-
-    if (obj == Qnil) {
-	w_byte(TYPE_NIL, arg);
-    }
-    else if (obj == TRUE) {
-	w_byte(TYPE_TRUE, arg);
-    }
-    else if (obj == FALSE) {
-	w_byte(TYPE_FALSE, arg);
-    }
-    else if (FIXNUM_P(obj)) {
-#if SIZEOF_LONG <= 4
-	w_byte(TYPE_FIXNUM, arg);
-	w_long(FIX2INT(obj), arg);
-#else
-	if (RSHIFT(obj, 32) == 0 || RSHIFT(obj, 32) == -1) {
-	    w_byte(TYPE_FIXNUM, arg);
-	    w_long(FIX2INT(obj), arg);
-	}
-	else {
-	    obj = int2big(FIX2INT(obj));
-	    goto write_bignum;
-	}
-#endif
-    }
-    else {
-	int num;
-
-	if (st_lookup(arg->data, obj, &num)) {
-	    w_byte(TYPE_LINK, arg);
-	    w_long(num, arg);
-	    return;
-	}
-	st_insert(arg->data, obj, arg->data->num_entries);
-	if (rb_respond_to(obj, s_dump)) {
-	    VALUE v;
-
-	    w_byte(TYPE_USERDEF, arg);
-	    w_unique(rb_class2name(CLASS_OF(obj)), arg);
-	    v = rb_funcall(obj, s_dump, 1, limit);
-	    if (TYPE(v) != T_STRING) {
-		TypeError("_dump_to must return String");
-	    }
-	    w_bytes(RSTRING(v)->ptr, RSTRING(v)->len, arg);
-	    return;
-	}
-
-	switch (BUILTIN_TYPE(obj)) {
-	  case T_MODULE:
-	  case T_CLASS:
-	    w_byte(TYPE_MODULE, arg);
-	    {
-		VALUE path = rb_class_path(obj);
-		w_bytes(RSTRING(path)->ptr, RSTRING(path)->len, arg);
-	    }
-	    return;
-
-	  case T_FLOAT:
-	    w_byte(TYPE_FLOAT, arg);
-	    w_float(RFLOAT(obj)->value, arg);
-	    return;
-
-	  case T_BIGNUM:
-	  write_bignum:
-	    w_byte(TYPE_BIGNUM, arg);
-	    {
-		char sign = RBIGNUM(obj)->sign?'+':'-';
-		int len = RBIGNUM(obj)->len;
-		USHORT *d = RBIGNUM(obj)->digits;
-
-		w_byte(sign, arg);
-		w_long(len, arg);
-		while (len--) {
-		    w_short(*d, arg);
-		    d++;
-		}
-	    }
-	    return;
-
-	  case T_STRING:
-	    w_uclass(obj, cString, arg);
-	    w_byte(TYPE_STRING, arg);
-	    w_bytes(RSTRING(obj)->ptr, RSTRING(obj)->len, arg);
-	    return;
-
-	  case T_REGEXP:
-	    w_uclass(obj, cRegexp, arg);
-	    w_byte(TYPE_REGEXP, arg);
-	    w_bytes(RREGEXP(obj)->str, RREGEXP(obj)->len, arg);
-	    w_byte(FL_TEST(obj, FL_USER1), arg);
-	    return;
-
-	  case T_ARRAY:
-	    w_uclass(obj, cArray, arg);
-	    w_byte(TYPE_ARRAY, arg);
-	    {
-		int len = RARRAY(obj)->len;
-		VALUE *ptr = RARRAY(obj)->ptr;
-
-		w_long(len, arg);
-		while (len--) {
-		    w_object(*ptr, arg, limit);
-		    ptr++;
-		}
-	    }
-	    break;
-
-	  case T_HASH:
-	    w_uclass(obj, cHash, arg);
-	    w_byte(TYPE_HASH, arg);
-	    w_long(RHASH(obj)->tbl->num_entries, arg);
-	    st_foreach(RHASH(obj)->tbl, hash_each, &c_arg);
-	    break;
-
-	  case T_STRUCT:
-	    w_byte(TYPE_STRUCT, arg);
-	    {
-		int len = RSTRUCT(obj)->len;
-		char *path = rb_class2name(CLASS_OF(obj));
-		VALUE mem;
-		int i;
-
-		w_unique(path, arg);
-		w_long(len, arg);
-		mem = rb_ivar_get(CLASS_OF(obj), rb_intern("__member__"));
-		if (mem == Qnil) {
-		    Fatal("non-initialized struct");
-		}
-		for (i=0; i<len; i++) {
-		    w_symbol(FIX2INT(RARRAY(mem)->ptr[i]), arg);
-		    w_object(RSTRUCT(obj)->ptr[i], arg, limit);
-		}
-	    }
-	    break;
-
-	  case T_OBJECT:
-	    w_byte(TYPE_OBJECT, arg);
-	    {
-		VALUE class = CLASS_OF(obj);
-		char *path;
-
-		if (FL_TEST(class, FL_SINGLETON)) {
-		    TypeError("singleton can't be dumped");
-		}
-		path = rb_class2name(class);
-		w_unique(path, arg);
-		if (ROBJECT(obj)->iv_tbl) {
-		    w_long(ROBJECT(obj)->iv_tbl->num_entries, arg);
-		    st_foreach(ROBJECT(obj)->iv_tbl, obj_each, &c_arg);
-		}
-		else {
-		    w_long(0, arg);
-		}
-	    }
-	    break;
-
-	  default:
-	    TypeError("can't dump %s", rb_class2name(CLASS_OF(obj)));
-	    break;
-	}
-    }
-}
-
-static VALUE
-dump(arg)
-    struct dump_call_arg *arg;
-{
-    w_object(arg->obj, arg->arg, arg->limit);
-}
-
-static VALUE
-dump_ensure(arg)
-    struct dump_arg *arg;
-{
-    st_free_table(arg->symbol);
-    st_free_table(arg->data);
-}
-
-static VALUE
-marshal_dump(argc, argv)
-    int argc;
-    VALUE argv;
-{
-    VALUE obj, port, a1, a2;
-    int limit = -1;
-    extern VALUE cIO;
-    struct dump_arg arg;
-    struct dump_call_arg c_arg;
-
-    port = 0;
-    rb_scan_args(argc, argv, "12", &obj, &a1, &a2);
-    if (argc == 3) {
-	limit = NUM2INT(a2);
-	port = a1;
-    }
-    else if (argc == 2) {
-	if (FIXNUM_P(a1)) limit = FIX2INT(a1);
-	else port = a1;
-    }
-    if (port) {
-	if (obj_is_kind_of(port, cIO)) {
-	    OpenFile *fptr;
-
-	    io_binmode(port);
-	    GetOpenFile(port, fptr);
-	    io_writable(fptr);
-	    arg.fp = (fptr->f2) ? fptr->f2 : fptr->f;
-	}
-	else {
-	    TypeError("instance of IO needed");
-	}
-    }
-    else {
-	arg.fp = 0;
-	port = str_new(0, 0);
-	arg.str = port;
-    }
-
-    arg.symbol = st_init_numtable();
-    arg.data   = st_init_numtable();
-    c_arg.obj = obj;
-    c_arg.arg = &arg;
-    c_arg.limit = limit;
-
-    w_byte(MARSHAL_MAJOR, &arg);
-    w_byte(MARSHAL_MINOR, &arg);
-
-    rb_ensure(dump, &c_arg, dump_ensure, &arg);
-
-    return port;
-}
-
-struct load_arg {
-    FILE *fp;
-    UCHAR *ptr, *end;
-    st_table *symbol;
-    st_table *data;
-};
-
-static int
-r_byte(arg)
-    struct load_arg *arg;
-{
-    if (arg->fp) return getc(arg->fp);
-    if (arg->ptr < arg->end) return *arg->ptr++;
-    return EOF;
-}
-
-static USHORT
-r_short(arg)
-    struct load_arg *arg;
-{
-    USHORT x;
-    int i;
-
-    x = 0;
-    for (i=0; i<sizeof(USHORT); i++) {
-	x |= r_byte(arg)<<(i*8);
-    }
-
-    return x;
-}
-
-static void
-long_toobig(size)
-    int size;
-{
-    TypeError("long too big for this architecture (size %d, given %d)",
-	      sizeof(long), size);
-}
-
-static long
-r_long(arg)
-    struct load_arg *arg;
-{
-    int c = r_byte(arg), i;
-    register long x;
-
-    if (c == 0) return 0;
-    if (c > 0) {
-	if (c > sizeof(long)) long_toobig((int)c);
-	x = 0;
-	for (i=0;i<c;i++) {
-	    x |= (long)r_byte(arg) << (8*i);
-	}
-    }
-    else if (c < 0) {
-	c = -c;
-	if (c > sizeof(long)) long_toobig((int)c);
-	x = -1;
-	for (i=0;i<c;i++) {
-	    x &= ~(0xff << (8*i));
-	    x |= (long)r_byte(arg) << (8*i);
-	}
-    }
-    return x;
-}
-
-#define r_bytes(s, arg) \
-  (s = (char*)r_long(arg), r_bytes0(&s,ALLOCA_N(char,(long)s),(long)s,arg))
-
-static int
-r_bytes0(sp, s, len, arg)
-    char **sp, *s;
-    int len;
-    struct load_arg *arg;
-{
-    if (arg->fp) {
-	len = fread(s, 1, len, arg->fp);
-    }
-    else {
-	if (arg->ptr + len > arg->end) {
-	    len = arg->end - arg->ptr;
-	}
-	memcpy(s, arg->ptr, len);
-	arg->ptr += len;
-    }
-
-    (s)[len] = '\0';
-    *sp = s;
-
-    return len;
-}
-
-static ID
-r_symbol(arg)
-    struct load_arg *arg;
-{
-    char *buf;
-    ID id;
-    char type;
-
-    if (r_byte(arg) == TYPE_SYMLINK) {
-	int num = r_long(arg);
-
-	if (st_lookup(arg->symbol, num, &id)) {
-	    return id;
-	}
-	TypeError("bad symbol");
-    }
-    r_bytes(buf, arg);
-    id = rb_intern(buf);
-    st_insert(arg->symbol, arg->symbol->num_entries, id);
-
-    return id;
-}
-
-static char*
-r_unique(arg)
-    struct load_arg *arg;
-{
-    return rb_id2name(r_symbol(arg));
-}
-
-static VALUE
-r_string(arg)
-    struct load_arg *arg;
-{
-    char *buf;
-    int len = r_bytes(buf, arg);
-
-    return str_taint(str_new(buf, len));
-}
-
-static VALUE
-r_regist(v, arg)
-    VALUE v;
-    struct load_arg *arg;
-{
-    st_insert(arg->data, arg->data->num_entries, v);
-    return v;
-}
-
-static VALUE
-r_object(arg)
-    struct load_arg *arg;
-{
-    VALUE v;
-    int type = r_byte(arg);
-
-    switch (type) {
-      case EOF:
-	eof_error();
-	return Qnil;
-
-      case TYPE_LINK:
-	if (st_lookup(arg->data, r_long(arg), &v)) {
-	    return v;
-	}
-	ArgError("dump format error (unlinked)");
-	break;
-
-      case TYPE_UCLASS:
-	{
-	    VALUE c = rb_path2class(r_unique(arg));
-	    v = r_object(arg);
-	    if (rb_special_const_p(v)) {
-		ArgError("dump format error (user class)");
-	    }
-	    RBASIC(v)->class = c;
-	    return v;
-	}
-
-      case TYPE_NIL:
-	return Qnil;
-
-      case TYPE_TRUE:
-	return TRUE;
-
-      case TYPE_FALSE:
-	return FALSE;
-
-      case TYPE_FIXNUM:
-	{
-	    int i = r_long(arg);
-	    return INT2FIX(i);
-	}
-
-      case TYPE_FLOAT:
-	{
-#ifndef atof
-	    double atof();
-#endif
-	    char *buf;
-
-	    r_bytes(buf, arg);
-	    v = float_new(atof(buf));
-	    return r_regist(v, arg);
-	}
-
-      case TYPE_BIGNUM:
-	{
-	    int len;
-	    USHORT *digits;
-
-	    NEWOBJ(big, struct RBignum);
-	    OBJSETUP(big, cBignum, T_BIGNUM);
-	    big->sign = (r_byte(arg) == '+');
-	    big->len = len = r_long(arg);
-	    big->digits = digits = ALLOC_N(USHORT, len);
-	    while (len--) {
-		*digits++ = r_short(arg);
-	    }
-	    big = RBIGNUM(big_norm((VALUE)big));
-	    if (TYPE(big) == T_BIGNUM) {
-		r_regist(big, arg);
-	    }
-	    return (VALUE)big;
-	}
-
-      case TYPE_STRING:
-	return r_regist(r_string(arg), arg);
-
-      case TYPE_REGEXP:
-	{
-	    char *buf;
-	    int len = r_bytes(buf, arg);
-	    int ci = r_byte(arg);
-	    return r_regist(reg_new(buf, len, ci), arg);
-	}
-
-      case TYPE_ARRAY:
-	{
-	    volatile int len = r_long(arg);
-	    v = ary_new2(len);
-	    r_regist(v, arg);
-	    while (len--) {
-		ary_push(v, r_object(arg));
-	    }
-	    return v;
-	}
-
-      case TYPE_HASH:
-	{
-	    int len = r_long(arg);
-
-	    v = hash_new();
-	    r_regist(v, arg);
-	    while (len--) {
-		VALUE key = r_object(arg);
-		VALUE value = r_object(arg);
-		hash_aset(v, key, value);
-	    }
-	    return v;
-	}
-
-      case TYPE_STRUCT:
-	{
-	    VALUE class, mem, values;
-	    int i, len;
-	    int num = arg->data->num_entries;
-
-	    class = rb_path2class(r_unique(arg));
-	    mem = rb_ivar_get(class, rb_intern("__member__"));
-	    if (mem == Qnil) {
-		Fatal("non-initialized struct");
-	    }
-	    len = r_long(arg);
-
-	    values = ary_new2(len);
-	    for (i=0; i<len; i++) {
-		ary_push(values, Qnil);
-	    }
-	    v = struct_alloc(class, values);
-	    r_regist(v, arg);
-	    for (i=0; i<len; i++) {
-		ID slot = r_symbol(arg);
-		if (RARRAY(mem)->ptr[i] != INT2FIX(slot))
-		    TypeError("struct not compatible");
-		struct_aset(v, INT2FIX(i), r_object(arg));
-	    }
-	    return v;
-	}
-	break;
-
-      case TYPE_USERDEF:
-        {
-	    VALUE class;
-	    int len;
-
-	    class = rb_path2class(r_unique(arg));
-	    if (rb_respond_to(class, s_load)) {
-		v = rb_funcall(class, s_load, 1, r_string(arg));
-		return r_regist(v, arg);
-	    }
-	    TypeError("class %s needs to have method `_load_from'",
-		      rb_class2name(class));
-	}
-        break;
-
-      case TYPE_OBJECT:
-	{
-	    VALUE class;
-	    int len;
-
-	    class = rb_path2class(r_unique(arg));
-	    len = r_long(arg);
-	    v = obj_alloc(class);
-	    r_regist(v, arg);
-	    if (len > 0) {
-		while (len--) {
-		    ID id = r_symbol(arg);
-		    VALUE val = r_object(arg);
-		    rb_ivar_set(v, id, val);
-		}
-	    }
-	    return v;
-	}
-	break;
-
-      case TYPE_MODULE:
-        {
-	    char *buf;
-	    r_bytes(buf, arg);
-	    return rb_path2class(buf);
-	}
-
-      default:
-	ArgError("dump format error(0x%x)", type);
-	break;
-    }
-}
-
-static VALUE
-load(arg)
-    struct load_arg *arg;
-{
-    return r_object(arg);
-}
-
-static VALUE
-load_ensure(arg)
-    struct load_arg *arg;
-{
-    st_free_table(arg->symbol);
-    st_free_table(arg->data);
-}
-
-static VALUE
-marshal_load(self, port)
-    VALUE self, port;
-{
-    FILE *fp;
-    int major;
-    VALUE v;
-    OpenFile *fptr;
-    struct load_arg arg;
-
-    if (TYPE(port) == T_STRING) {
-	arg.fp = 0;
-	arg.ptr = RSTRING(port)->ptr;
-	arg.end = arg.ptr + RSTRING(port)->len;
-    }
-    else {
-	if (obj_is_kind_of(port, cIO)) {
-	    io_binmode(port);
-	    GetOpenFile(port, fptr);
-	    io_readable(fptr);
-	    arg.fp = fptr->f;
-	}
-	else {
-	    TypeError("instance of IO needed");
-	}
-    }
-
-    major = r_byte(&arg);
-    if (major == MARSHAL_MAJOR) {
-	if (r_byte(&arg) != MARSHAL_MINOR) {
-	    Warning("Old marshal file format (can be read)");
-	}
-	arg.symbol = st_init_numtable();
-	arg.data   = st_init_numtable();
-	v = rb_ensure(load, &arg, load_ensure, &arg);
-    }
-    else {
-	TypeError("Old marshal file format (can't read)");
-    }
-
-    return v;
-}
-
-Init_marshal()
-{
-    VALUE mMarshal = rb_define_module("Marshal");
-
-    s_dump = rb_intern("_dump_to");
-    s_load = rb_intern("_load_from");
-    rb_define_module_function(mMarshal, "dump", marshal_dump, -1);
-    rb_define_module_function(mMarshal, "load", marshal_load, 1);
-    rb_define_module_function(mMarshal, "restore", marshal_load, 1);
-}
diff --git a/ext/marshal/marshal.doc b/ext/marshal/marshal.doc
deleted file mode 100644
index 7529e7942f..0000000000
--- a/ext/marshal/marshal.doc
+++ /dev/null
@@ -1,48 +0,0 @@
-.\" marshal.doc -  -*- Indented-Text -*- created at: Tue May 16 12:18:08 JST 1995
-
-** Marshal(モジュール)
-
-rubyオブジェクトをファイルに書き出したり，読みも度したりする機能を提供
-するモジュール．大部分のクラスのインスタンスを書き出す事ができるが，ファ
-イルへの不可能なクラスも存在し(例:IO)，そのようなクラスを書き出そうと
-すると例外を発生させる．
-
-Methods:
-Single Methods:
-
-   dump(obj, port[, limit])
-
-    objを再帰的にファイルに書き出す．ファイルに書き出せないクラスのイ
-    ンスタンスをファイルに書き出そうとすると例外を発生させる．ファイル
-    に書き出せないクラスは以下の通り．
-
-	Class, Module, Data
-
-    また，これらのクラスを間接的に指すクラス(例えばIOのサブクラス)など
-    も書き出せない．portはIO(またはそのサブクラス)のインスタンスを指定
-    する．
-
-    出力するオブジェクトがメソッド`_dump_to'を定義している場合には，ファ
-    イル出力はそのメソッドを使って行われる．メソッド`_dump_to'は引数と
-    して出力先のファイルオブジェクトを受け取る．インスタンスがメソッド
-    `_dump_to'を持つクラスは必ず同じフォーマットを読み戻す特異メソッド
-    `_load_from'を定義する必要がある．
-
-    limitを指定した場合，limit段以上深くリンクしたオブジェクトをダンプ
-    できない(デフォルトは100レベル)。負のlimitを指定すると深さチェック
-    を行わない。
-
-   dumps(obj)
-
-    dump()がファイルに書き出すのと同じ内容を含む文字列を返す．
-
-   load(port)
-
-    portからオブジェクトを読み込んで来て，元のオブジェクトと同じ状態を
-    もつオブジェクトを生成する．portは文字列かIO(またはそのサブクラス)
-    のインスタンスである．
-
--------------------------------------------------------
-Local variables:
-fill-column: 70
-end:
diff --git a/lib/e2mmap1_0.rb b/lib/e2mmap1_0.rb
deleted file mode 100644
index d245dec975..0000000000
--- a/lib/e2mmap1_0.rb
+++ /dev/null
@@ -1,71 +0,0 @@
-#
-#   e2mmap.rb - 
-#   	$Release Version: 1.0$
-#   	$Revision$
-#   	$Date$
-#   	by Keiju ISHITSUKA
-#
-# --
-#
-#
-
-module Exception2MessageMapper
-  RCS_ID='-$Header$-'
-  E2MM = Exception2MessageMapper
-  
-  def E2MM.extend_to(b)
-    c = eval("self", b)
-    c.extend(self)
-    c.bind(b)
-  end
-  
-  def bind(b)
-    eval "
-  @binding = binding
-  E2MM_ErrorMSG = Hash.new
-  
-  # fail(err, *rest)
-  #	err:	例外
-  #	rest:	メッセージに渡すパラメータ
-  #
-  def fail!(*rest)
-    super
-  end
-  
-  def fail(err, *rest)
-    $! = err.new(sprintf(E2MM_ErrorMSG[err], *rest))
-    super()
-  end
-
-  public :fail
-  # def_exception(c, m)
-  #	    c:  exception
-  #	    m:  message_form
-  #	例外cのメッセージをmとする.
-  #
-  def def_e2message(c, m)
-    E2MM_ErrorMSG[c] = m
-  end
-  
-  # def_exception(c, m)
-  #	    c:  exception_name
-  #	    m:  message_form
-  #	    s:	例外スーパークラス(デフォルト: Exception)
-  #	例外名``c''をもつ例外を定義し, そのメッセージをmとする.
-  #
-  def def_exception(c, m)
-
-    c = c.id2name if c.kind_of?(Fixnum)
-    eval \"class \#{c} < Exception
-           end
-           E2MM_ErrorMSG[\#{c}] = '\#{m}'
-           \", @binding
-  end
-", b
-    
-  end
-  
-  E2MM.extend_to(binding)
-  def_exception("ErrNotClassOrModule", "Not Class or Module")
-end
-
diff --git a/lib/tkcore.rb b/lib/tkcore.rb
deleted file mode 100644
index c151b0af9e..0000000000
--- a/lib/tkcore.rb
+++ /dev/null
@@ -1,528 +0,0 @@
-#
-#		tkcore.rb - Tk interface modue without thread
-#			$Date$
-#			by Yukihiro Matsumoto <matz@caelum.co.jp>
-
-require "tkutil"
-if defined? Thread
-  require "thread"
-end
-
-module Tk
-  include TkUtil
-  extend Tk
-
-  wish_path = nil
-  ENV['PATH'].split(":").each {|path|
-    for wish in ['wish4.2', 'wish4.1', 'wish4.0', 'wish']
-      if File.exist? path+'/'+wish
-	wish_path = path+'/'+wish
-	break
-      end
-      break if wish_path
-    end
-  }
-  fail 'can\'t find wish' if not wish_path #'
-
-  def Tk.tk_exit
-    if not PORT.closed?
-      PORT.print "exit\n"
-      PORT.close
-    end
-  end
-
-#  PORT = open(format("|%s -n %s", wish_path, File.basename($0)), "w+");
-  PORT = open(format("|%s", wish_path), "w+");
-  trap "EXIT", proc{Tk.tk_exit}
-  trap "PIPE", ""
-
-  def tk_write(*args)
-    printf PORT, *args;
-    PORT.print "\n"
-    PORT.flush
-  end
-  tk_write '\
-wm withdraw .
-proc rb_out args {
-  puts [format %%s $args]
-  flush stdout
-}
-proc rb_ans arg {
-  if [catch $arg var] {puts "!$var"} {puts "=$var@@"}
-  flush stdout
-}
-proc tkerror args { exit }
-proc keepalive {} { rb_out alive; after 120000 keepalive}
-after 120000 keepalive'
-
-  READABLE = []
-  READ_CMD = {}
-
-  def file_readable(port, cmd)
-    if cmd == nil
-      READABLE.delete port
-    else
-      READABLE.push port
-    end
-    READ_CMD[port] = cmd
-  end
-
-  WRITABLE = []
-  WRITE_CMD = {}
-  def file_writable(port, cmd)
-    if cmd == nil
-      WRITABLE.delete port
-    else
-      WRITABLE.push port
-    end
-    WRITE_CMD[port] = cmd
-  end
-  module_function :file_readable, :file_writable
-
-  file_readable PORT, proc {
-    line = PORT.gets
-    exit if not line
-    Tk.dispatch(line.chop!)
-  }
-
-  def error_at
-    frames = caller(1)
-    frames.delete_if do |c|
-      c =~ %r!/tk(|core|thcore|canvas|text|entry|scrollbox)\.rb:\d+!
-    end
-    frames
-  end
-
-  def tk_tcl2ruby(val)
-    case val
-    when /^-?\d+$/
-      val.to_i
-    when /^\./
-      $tk_window_list[val]
-    when /^rb_out (c\d+)/
-      $tk_cmdtbl[$1]
-    when / /
-      val.split.collect{|elt|
-	tk_tcl2ruby(elt)
-      }
-    when /^-?\d+\.\d*$/
-      val.to_f
-    else
-      val
-    end
-  end
-
-  def tk_split_list(str)
-    idx = str.index('{')
-    return tk_tcl2ruby(str) if not idx
-
-    list = tk_tcl2ruby(str[0,idx])
-    str = str[idx+1..-1]
-    i = -1
-    brace = 1
-    str.each_byte {|c|
-      i += 1
-      brace += 1 if c == ?{
-      brace -= 1 if c == ?}
-      break if brace == 0
-    }
-    if str[0, i] == ' '
-      list.push ' '
-    else
-      list.push tk_split_list(str[0, i])
-    end
-    list += tk_split_list(str[i+1..-1])
-    list
-  end
-  private :tk_tcl2ruby, :tk_split_list
-
-  def bool(val)
-    case bool
-    when "1", 1, 'yes', 'true'
-      TRUE
-    else
-      FALSE
-    end
-  end
-  def number(val)
-    case val
-    when /^-?\d+$/
-      val.to_i
-    when /^-?\d+\.\d*$/
-      val.to_f
-    else
-      val
-    end
-  end
-  def string(val)
-    if val == "{}"
-      ''
-    elsif val[0] == ?{
-      val[1..-2]
-    else
-      val
-    end
-  end
-  def list(val)
-    tk_split_list(val)
-  end
-  def window(val)
-    $tk_window_list[val]
-  end
-  def procedure(val)
-    if val =~ /^rb_out (c\d+)/
-      $tk_cmdtbl[$1]
-    else
-      nil
-    end
-  end
-  private :bool, :number, :string, :list, :window, :procedure
-
-  # mark for non-given arguments
-  None = Object.new
-  def None.to_s
-    'None'
-  end
-
-  $tk_event_queue = []
-  def tk_call(str, *args)
-    args = args.collect{|s|
-      next if s == None
-      if s.kind_of?(Hash)
-	s = hash_kv(s).join(" ")
-      else
-	if not s
-	  s = "0"
-	elsif s == TRUE
-	  s = "1"
-	elsif s.kind_of?(TkObject)
-	  s = s.path
-	elsif s.kind_of?(TkVariable)
-	  s = s.id
-	else
-	  s = s.to_s
-	  s.gsub!(/["\\\$\[\]]/, '\\\\\0') #"
-	  s.gsub!(/\{/, '\\\\173')
-	  s.gsub!(/\}/, '\\\\175')
-	end
-	"\"#{s}\""
-      end
-    }
-    str += " "
-    str += args.join(" ")
-    print str, "\n" if $DEBUG
-    tk_write 'rb_ans {%s}', str
-    while PORT.gets
-      print $_ if $DEBUG
-      $_.chop!
-      if /^=(.*)@@$/
-	val = $1
-	break
-      elsif /^=/
-	val = $' + "\n"
-	while TRUE
-	  PORT.readline
-	  if ~/@@$/
-	    val += $'
-	    return val
-	  else
-	    val += $_
-	  end
-	end
-      elsif /^!/
-	$@ = error_at
-	msg = $'
-	if msg =~ /unknown option "-(.*)"/
-	  $! = NameError.new(format("undefined method `%s' for %s(%s)",
-				    $1, self, self.type)) #`'
-	else
-	  $! = RuntimeError.new(format("%s - %s", self.type, msg))
-	end
-	fail
-      end
-      $tk_event_queue.push $_
-    end
-
-    while ev = $tk_event_queue.shift
-      Tk.dispatch ev
-    end
-    fail 'wish closed' if PORT.closed?
-#    tk_split_list(val)
-    val
-  end
-
-  def hash_kv(keys)
-    conf = []
-    if keys
-      for k, v in keys
-	 conf.push("-#{k}")
-	 v = install_cmd(v) if v.kind_of? Proc
-	 conf.push(v)
-      end
-    end
-    conf
-  end
-  private :tk_call, :error_at, :hash_kv
-
-  $tk_cmdid = 0
-  def install_cmd(cmd)
-    return '' if cmd == ''	# uninstall cmd
-    id = format("c%.4d", $tk_cmdid)
-    $tk_cmdid += 1
-    $tk_cmdtbl[id] = cmd
-    @cmdtbl = [] if not @cmdtbl
-    @cmdtbl.push id
-    return format('rb_out %s', id)
-  end
-  def uninstall_cmd(id)
-    $tk_cmdtbl[id] = nil
-  end
-  private :install_cmd, :uninstall_cmd
-
-  $tk_window_list = {}
-  class Event
-    def initialize(seq,b,f,h,k,s,t,w,x,y,aa,ee,kk,nn,ww,tt,xx,yy)
-      @serial = seq
-      @num = b
-      @focus = (f == 1)
-      @height = h
-      @keycode = k
-      @state = s
-      @time = t
-      @width = w
-      @x = x
-      @y = y
-      @char = aa
-      @send_event = (ee == 1)
-      @keysym = kk
-      @keysym_num = nn
-      @type = tt
-      @widget = ww
-      @x_root = xx
-      @y_root = yy
-    end
-    attr :serial
-    attr :num
-    attr :focus
-    attr :height
-    attr :keycode
-    attr :state
-    attr :time
-    attr :width
-    attr :x
-    attr :y
-    attr :char
-    attr :send_event
-    attr :keysym
-    attr :keysym_num
-    attr :type
-    attr :widget
-    attr :x_root
-    attr :y_root
-  end
-
-  def install_bind(cmd, args=nil)
-    if args
-      id = install_cmd(proc{|arg|
-	TkUtil.eval_cmd cmd, *arg
-      })
-      id + " " + args
-    else
-      id = install_cmd(proc{|arg|
-	TkUtil.eval_cmd cmd, Event.new(*arg)
-      })
-      id + " %# %b %f %h %k %s %t %w %x %y %A %E %K %N %W %T %X %Y"
-    end
-  end
-
-  def _bind(path, context, cmd, args=nil)
-    begin
-      id = install_bind(cmd, args)
-      tk_call 'bind', path, "<#{context}>", id
-    rescue
-      $tk_cmdtbl[id] = nil
-      fail
-    end
-  end
-  private :install_bind, :_bind
-
-  def bind_all(context, cmd=Proc.new, args=nil)
-    _bind 'all', context, cmd, args
-  end
-
-  def pack(*args)
-    TkPack.configure *args
-  end
-
-  $tk_cmdtbl = {}
-
-  def after(ms, cmd=Proc.new)
-    myid = format("c%.4d", $tk_cmdid)
-    tk_call 'after', ms,
-      install_cmd(proc{
-		    TkUtil.eval_cmd cmd
-		    uninstall_cmd myid
-		  })
-  end
-
-  def update(idle=nil)
-    if idle
-      tk_call 'update', 'idletasks'
-    else
-      tk_call 'update'
-    end
-  end
-
-  def dispatch(line)
-    if line =~ /^c\d+/
-      cmd = $&
-      fail "no command `#{cmd}'" if not $tk_cmdtbl[cmd]
-      args = tk_split_list($')
-      TkUtil.eval_cmd $tk_cmdtbl[cmd], *args
-    elsif line =~ /^alive$/
-      # keep alive, do nothing
-    else
-      fail "malformed line <#{line}>"
-    end
-  end
-
-  def mainloop
-    begin
-      tk_write 'after idle {wm deiconify .}'
-      while TRUE
-	rf, wf = select(READABLE, WRITABLE)
-	for f in rf
-	  READ_CMD[f].call(f) if READ_CMD[f]
-	  if f.closed?
-	    READABLE.delete f
-	    READ_CMD[f] = nil
-	  end
-	end
-	for f in wf
-	  WRITE_CMD[f].call(f) if WRITE_CMD[f]
-	  if f.closed?
-	    WRITABLE.delete f
-	    WRITE_CMD[f] = nil
-	  end
-	end
-      end
-    ensure
-      Tk.tk_exit
-    end
-  end
-
-  def root
-    $tk_root
-  end
-
-  def bell
-    tk_call 'bell'
-  end
-  module_function :after, :update, :dispatch, :mainloop, :root, :bell
-
-  module Scrollable
-    def xscrollcommand(cmd=Proc.new)
-      configure_cmd 'xscrollcommand', cmd
-    end
-    def yscrollcommand(cmd=Proc.new)
-      configure_cmd 'yscrollcommand', cmd
-    end
-  end
-
-  module Wm
-    def aspect(*args)
-      w = window(tk_call('wm', 'grid', path, *args))
-      w.split.collect{|s|s.to_i} if args.length == 0
-    end
-    def client(name=None)
-      tk_call 'wm', 'client', path, name
-    end
-    def colormapwindows(*args)
-      list(tk_call('wm', 'colormapwindows', path, *args))
-    end
-    def wm_command(value=None)
-      string(tk_call('wm', 'command', path, value))
-    end
-    def deiconify
-      tk_call 'wm', 'deiconify', path
-    end
-    def focusmodel(*args)
-      tk_call 'wm', 'focusmodel', path, *args
-    end
-    def frame
-      tk_call 'wm', 'frame', path
-    end
-    def geometry(*args)
-      list(tk_call('wm', 'geometry', path, *args))
-    end
-    def grid(*args)
-      w = tk_call('wm', 'grid', path, *args)
-      list(w) if args.size == 0
-    end
-    def group(*args)
-      tk_call 'wm', 'path', path, *args
-    end
-    def iconbitmap(*args)
-      tk_call 'wm', 'bitmap', path, *args
-    end
-    def iconify
-      tk_call 'wm', 'iconify'
-    end
-    def iconmask(*args)
-      tk_call 'wm', 'iconmask', path, *args
-    end
-    def iconname(*args)
-      tk_call 'wm', 'iconname', path, *args
-    end
-    def iconposition(*args)
-      w = tk_call('wm', 'iconposition', path, *args)
-      list(w) if args.size == 0
-    end
-    def iconwindow(*args)
-      tk_call 'wm', 'iconwindow', path, *args
-    end
-    def maxsize(*args)
-      w = tk_call('wm', 'maxsize', path, *args)
-      list(w) if not args.size == 0
-    end
-    def minsize(*args)
-      w = tk_call('wm', 'minsize', path, *args)
-      list(w) if args.size == 0
-    end
-    def overrideredirect(bool=None)
-      if bool == None
-	bool(tk_call('wm', 'overrideredirect', path))
-      else
-	tk_call 'wm', 'overrideredirect', path, bool
-      end
-    end
-    def positionfrom(*args)
-      tk_call 'wm', 'positionfrom', path, *args
-    end
-    def protocol(name, func=None)
-      func = install_cmd(func) if not func == None
-      tk_call 'wm', 'command', path, name, func
-    end
-    def resizable(*args)
-      w = tk_call('wm', 'resizable', path, *args)
-      if args.length == 0
-	list(w).collect{|e| bool(e)}
-      end
-    end
-    def sizefrom(*args)
-      list(tk_call('wm', 'sizefrom', path, *args))
-    end
-    def state
-      tk_call 'wm', 'state', path
-    end
-    def title(*args)
-      tk_call 'wm', 'title', path, *args
-    end
-    def transient(*args)
-      tk_call 'wm', 'transient', path, *args
-    end
-    def withdraw
-      tk_call 'wm', 'withdraw', path
-    end
-  end
-end
diff --git a/lib/tkthcore.rb b/lib/tkthcore.rb
deleted file mode 100644
index a6648502bd..0000000000
--- a/lib/tkthcore.rb
+++ /dev/null
@@ -1,550 +0,0 @@
-#
-#		tkthcore.rb - Tk interface modue using thread
-#			$Date$
-#			by Yukihiro Matsumoto <matz@caelum.co.jp>
-
-require "tkutil"
-require "thread"
-
-module Tk
-  include TkUtil
-  extend Tk
-
-  def Tk.tk_exit
-    if not PORT.closed?
-      tk_write "exit"
-      PORT.close
-    end
-  end
-
-  trap "EXIT", proc{Tk.tk_exit}
-  trap "PIPE", ''
-
-  wish_path = nil
-  ENV['PATH'].split(":").each {|path|
-    for wish in ['wish4.2', 'wish4.1', 'wish4.0', 'wish']
-      if File.exist? path+'/'+wish
-	wish_path = path+'/'+wish
-	break
-      end
-      break if wish_path
-    end
-  }
-  fail 'can\'t find wish' if not wish_path #'
-
-  # mark for non-given arguments
-  None = Object.new
-  def None.to_s
-    'None'
-  end
-
-  Qin = Queue.new
-  Qout = Queue.new
-  Qwish = Queue.new
-  Qcmd = Queue.new
-  PORT = open(format("|%s -n %s", wish_path, File.basename($0)), "w+");
-
-  $tk_not_init = TRUE
-
-  def Tk.init
-    $tk_not_init = FALSE
-    Thread.start do
-      loop do
-	while line = PORT.gets
-	  line.chop!
-	  if line =~ /^[=!]/
-	    Qwish.push line
-	  else
-	    Qcmd.push line
-	  end
-	end
-	exit
-      end
-    end
-
-    Thread.start do
-      ary = [PORT]
-      loop do
-	str = Qin.pop
-	print "Qin: ", str, "\n" if $DEBUG
-	tk_write 'if [catch {%s} var] {puts "!$var"} {puts "=$var@@"};flush stdout', str
-	line = tk_recv
-	Qout.push(line)
-      end
-    end
-  end
-
-  $tk_event_queue = []
-  def tk_recv()
-    val = nil
-    $_ = Qwish.pop
-    loop do
-      if /^=(.*)@@$/
-	val = $1
-	break
-      elsif /^=/
-	val = $' + "\n"
-	while TRUE
-	  PORT.readline
-	  if ~/@@$/
-	    val += $'
-	    return val
-	  else
-	    val += $_
-	  end
-	end
-      elsif /^!/
-	$@ = error_at
-	msg = $'
-	if msg =~ /unknown option "-(.*)"/
-	  fail NameError, format("undefined method `%s' for %s(%s)", $1, self, self.type) #`'
-	else
-	  fail format("%s - %s", self.type, msg)
-	end
-      end
-    end
-
-    fail 'wish closed' if PORT.closed?
-#    tk_split_list(val)
-    val
-  end
-
-  def tk_call(str, *args)
-    Tk.init if $tk_not_init
-    args = args.collect{|s|
-      next if s == None
-      if s.kind_of?(Hash)
-	s = hash_kv(s).join(" ")
-      else
-	if not s
-	  s = "0"
-	elsif s == TRUE
-	  s = "1"
-	elsif s.kind_of?(TkObject)
-	  s = s.path
-	elsif s.kind_of?(TkVariable)
-	  s = s.id
-	else
-	  s = s.to_s
-	  s.gsub!(/["\\\$\[\]]/, '\\\\\0') #"
-	  s.gsub!(/\{/, '\\\\173')
-	  s.gsub!(/\}/, '\\\\175')
-	end
-	"\"#{s}\""
-      end
-    }
-    str += " "
-    str += args.join(" ")
-    Qin.push str
-    return Qout.pop
-  end
-
-  def tk_write(*args)
-    PORT.printf *args; PORT.print "\n"
-    PORT.flush
-  end
-  module_function :tk_write, :tk_recv
-  tk_write '\
-wm withdraw .
-proc rb_out args {
-  puts [format %%s $args]
-  flush stdout
-}
-proc tkerror args { exit }
-proc keepalive {} { rb_out alive; after 120000 keepalive}
-after 120000 keepalive'
-
-  READ_TH = {}
-  def file_readable(port, cmd)
-    if cmd == nil
-      if READ_TH[port].has_key?
-	READ_TH[port].exit
-	READ_TH[port] = nil
-      end
-    else
-      READ_TH[port] = Thread.start{
-	loop do
-	  TkUtil.eval_cmd cmd
-	end
-      }
-    end
-  end
-
-  WRITE_TH = {}
-  def file_writable(port, cmd)
-    if cmd == nil
-      if WRITE_TH[port].has_key?
-	WRITE_TH[port].exit
-      end
-    else
-      WRITE_TH[port] = Thread.start{
-	loop do
-	  TkUtil.eval_cmd cmd
-	end
-      }
-    end
-  end
-  module_function :file_readable, :file_writable
-
-  def tk_tcl2ruby(val)
-    case val
-    when /^-?\d+$/
-      val.to_i
-    when /^\./
-      $tk_window_list[val]
-    when /^rb_out (c\d+)/
-      $tk_cmdtbl[$1]
-    when / /
-      val.split.collect{|elt|
-	tk_tcl2ruby(elt)
-      }
-    when /^-?\d+\.\d*$/
-      val.to_f
-    else
-      val
-    end
-  end
-
-  def tk_split_list(str)
-    idx = str.index('{')
-    return tk_tcl2ruby(str) if not idx
-
-    list = tk_tcl2ruby(str[0,idx])
-    str = str[idx+1..-1]
-    i = -1
-    brace = 1
-    str.each_byte {|c|
-      i += 1
-      brace += 1 if c == ?{
-      brace -= 1 if c == ?}
-      break if brace == 0
-    }
-    if str[0, i] == ' '
-      list.push ' '
-    else
-      list.push tk_split_list(str[0, i])
-    end
-    list += tk_split_list(str[i+1..-1])
-    list
-  end
-  private :tk_tcl2ruby, :tk_split_list
-
-  def dispatch(line)
-    if line =~ /^c\d+/
-      cmd = $&
-      fail "no command `#{cmd}'" if not $tk_cmdtbl[cmd]
-      args = tk_split_list($')
-      TkUtil.eval_cmd $tk_cmdtbl[cmd], *args
-    elsif line =~ /^alive$/
-      # keep alive, do nothing
-    else
-      fail "malformed line <#{line}>"
-    end
-  end
-  module_function :dispatch
-
-  def error_at
-    frames = caller(1)
-    frames.delete_if do |c|
-      c =~ %r!/tk(|core|thcore|canvas|text|entry|scrollbox)\.rb:\d+!
-    end
-    frames
-  end
-
-  def bool(val)
-    case bool
-    when "1", 1, 'yes', 'true'
-      TRUE
-    else
-      FALSE
-    end
-  end
-  def number(val)
-    case val
-    when /^-?\d+$/
-      val.to_i
-    when /^-?\d+\.\d*$/
-      val.to_f
-    else
-      val
-    end
-  end
-  def string(val)
-    if val == "{}"
-      ''
-    elsif val[0] == ?{
-      val[1..-2]
-    else
-      val
-    end
-  end
-  def list(val)
-    tk_split_list(val)
-  end
-  def window(val)
-    $tk_window_list[val]
-  end
-  def procedure(val)
-    if val =~ /^rb_out (c\d+)/
-      $tk_cmdtbl[$1]
-    else
-      nil
-    end
-  end
-  private :bool, :number, :string, :list, :window, :procedure
-
-  def hash_kv(keys)
-    conf = []
-    if keys
-      for k, v in keys
-	 conf.push("-#{k}")
-	 v = install_cmd(v) if v.kind_of? Proc
-	 conf.push(v)
-      end
-    end
-    conf
-  end
-  private :tk_call, :error_at, :hash_kv
-
-  $tk_cmdid = 0
-  def install_cmd(cmd)
-    return '' if cmd == ''	# uninstall cmd
-    id = format("c%.4d", $tk_cmdid)
-    $tk_cmdid += 1
-    $tk_cmdtbl[id] = cmd
-    @cmdtbl = [] if not @cmdtbl
-    @cmdtbl.push id
-    return format('rb_out %s', id)
-  end
-  def uninstall_cmd(id)
-    $tk_cmdtbl[id] = nil
-  end
-  private :install_cmd, :uninstall_cmd
-
-  $tk_window_list = {}
-  class Event
-    def initialize(seq,b,f,h,k,s,t,w,x,y,aa,ee,kk,nn,ww,tt,xx,yy)
-      @serial = seq
-      @num = b
-      @focus = (f == 1)
-      @height = h
-      @keycode = k
-      @state = s
-      @time = t
-      @width = w
-      @x = x
-      @y = y
-      @char = aa
-      @send_event = (ee == 1)
-      @keysym = kk
-      @keysym_num = nn
-      @type = tt
-      @widget = ww
-      @x_root = xx
-      @y_root = yy
-    end
-    attr :serial
-    attr :num
-    attr :focus
-    attr :height
-    attr :keycode
-    attr :state
-    attr :time
-    attr :width
-    attr :x
-    attr :y
-    attr :char
-    attr :send_event
-    attr :keysym
-    attr :keysym_num
-    attr :type
-    attr :widget
-    attr :x_root
-    attr :y_root
-  end
-
-  def install_bind(cmd, args=nil)
-    if args
-      id = install_cmd(proc{|arg|
-	TkUtil.eval_cmd cmd, *arg
-      })
-      id + " " + args
-    else
-      id = install_cmd(proc{|arg|
-	TkUtil.eval_cmd cmd, Event.new(*arg)
-      })
-      id + " %# %b %f %h %k %s %t %w %x %y %A %E %K %N %W %T %X %Y"
-    end
-  end
-
-  def _bind(path, context, cmd, args=nil)
-    begin
-      id = install_bind(cmd, args)
-      tk_call 'bind', path, "<#{context}>", id
-    rescue
-      $tk_cmdtbl[id] = nil
-      fail
-    end
-  end
-  private :install_bind, :_bind
-
-  def bind_all(context, cmd=Proc.new, args=nil)
-    _bind 'all', context, cmd, args
-  end
-
-  def pack(*args)
-    TkPack.configure *args
-  end
-
-  $tk_cmdtbl = {}
-
-  Qafter = Queue.new
-  def after(ms, cmd=Proc.new)
-    unless $tk_after_thread
-      $tk_after_thread = Thread.start{
-	loop do
-	  cmd = Qafter.pop
-	  TkUtil.eval_cmd cmd
-	end
-      }
-    end
-    Thread.start do
-      sleep Float(ms)/1000
-      Qafter.push cmd
-    end
-  end
-
-  def update(idle=nil)
-    if idle
-      tk_call 'update', 'idletasks'
-    else
-      tk_call 'update'
-    end
-  end
-
-  def root
-    $tk_root
-  end
-
-  def bell
-    tk_call 'bell'
-  end
-
-  def mainloop
-    begin
-      tk_call 'after', 'idle', 'wm deiconify .'
-      loop do
-	dispatch Qcmd.pop
-      end
-    ensure
-      Tk.tk_exit
-    end
-  end
-  module_function :after, :update, :dispatch, :mainloop, :root, :bell
-
-  module Scrollable
-    def xscrollcommand(cmd=Proc.new)
-      configure_cmd 'xscrollcommand', cmd
-    end
-    def yscrollcommand(cmd=Proc.new)
-      configure_cmd 'yscrollcommand', cmd
-    end
-  end
-
-  module Wm
-    def aspect(*args)
-      w = window(tk_call('wm', 'grid', path, *args))
-      w.split.collect{|s|s.to_i} if args.length == 0
-    end
-    def client(name=None)
-      tk_call 'wm', 'client', path, name
-    end
-    def colormapwindows(*args)
-      list(tk_call('wm', 'colormapwindows', path, *args))
-    end
-    def wm_command(value=None)
-      string(tk_call('wm', 'command', path, value))
-    end
-    def deiconify
-      tk_call 'wm', 'deiconify', path
-    end
-    def focusmodel(*args)
-      tk_call 'wm', 'focusmodel', path, *args
-    end
-    def frame
-      tk_call 'wm', 'frame', path
-    end
-    def geometry(*args)
-      list(tk_call('wm', 'geometry', path, *args))
-    end
-    def grid(*args)
-      w = tk_call('wm', 'grid', path, *args)
-      list(w) if args.size == 0
-    end
-    def group(*args)
-      tk_call 'wm', 'path', path, *args
-    end
-    def iconbitmap(*args)
-      tk_call 'wm', 'bitmap', path, *args
-    end
-    def iconify
-      tk_call 'wm', 'iconify'
-    end
-    def iconmask(*args)
-      tk_call 'wm', 'iconmask', path, *args
-    end
-    def iconname(*args)
-      tk_call 'wm', 'iconname', path, *args
-    end
-    def iconposition(*args)
-      w = tk_call('wm', 'iconposition', path, *args)
-      list(w) if args.size == 0
-    end
-    def iconwindow(*args)
-      tk_call 'wm', 'iconwindow', path, *args
-    end
-    def maxsize(*args)
-      w = tk_call('wm', 'maxsize', path, *args)
-      list(w) if not args.size == 0
-    end
-    def minsize(*args)
-      w = tk_call('wm', 'minsize', path, *args)
-      list(w) if args.size == 0
-    end
-    def overrideredirect(bool=None)
-      if bool == None
-	bool(tk_call('wm', 'overrideredirect', path))
-      else
-	tk_call 'wm', 'overrideredirect', path, bool
-      end
-    end
-    def positionfrom(*args)
-      tk_call 'wm', 'positionfrom', path, *args
-    end
-    def protocol(name, func=None)
-      func = install_cmd(func) if not func == None
-      tk_call 'wm', 'command', path, name, func
-    end
-    def resizable(*args)
-      w = tk_call('wm', 'resizable', path, *args)
-      if args.length == 0
-	list(w).collect{|e| bool(e)}
-      end
-    end
-    def sizefrom(*args)
-      list(tk_call('wm', 'sizefrom', path, *args))
-    end
-    def state
-      tk_call 'wm', 'state', path
-    end
-    def title(*args)
-      tk_call 'wm', 'title', path, *args
-    end
-    def transient(*args)
-      tk_call 'wm', 'transient', path, *args
-    end
-    def withdraw
-      tk_call 'wm', 'withdraw', path
-    end
-  end
-end
diff --git a/regex.c b/regex.c
new file mode 100644
index 0000000000..0fdf2c06f9
--- /dev/null
+++ b/regex.c
@@ -0,0 +1,3388 @@
+/* Extended regular expression matching and search library.
+   Copyright (C) 1985, 1989-90 Free Software Foundation, Inc.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 1, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
+/* Multi-byte extension added May, 1993 by t^2 (Takahiro Tanimoto)
+   Last change: May 21, 1993 by t^2  */
+
+
+/* To test, compile with -Dtest.  This Dtestable feature turns this into
+   a self-contained program which reads a pattern, describes how it
+   compiles, then reads a string and searches for it.
+
+   On the other hand, if you compile with both -Dtest and -Dcanned you
+   can run some tests we've already thought of.  */
+
+/* We write fatal error messages on standard error.  */
+#include <stdio.h>
+
+/* isalpha(3) etc. are used for the character classes.  */
+#include <ctype.h>
+#include <sys/types.h>
+
+#include "config.h"
+#include "defines.h"
+
+#ifdef __STDC__
+#define P(s)    s
+#define MALLOC_ARG_T size_t
+#else
+#define P(s)    ()
+#define MALLOC_ARG_T unsigned
+#define volatile
+#define const
+#endif
+
+/* #define	NO_ALLOCA	/* try it out for now */
+#ifndef NO_ALLOCA
+/* Make alloca work the best possible way.  */
+#ifdef __GNUC__
+#ifndef atarist
+#ifndef alloca
+#define alloca __builtin_alloca
+#endif
+#endif /* atarist */
+#else
+#if defined(HAVE_ALLOCA_H) && !defined(__GNUC__)
+#include <alloca.h>
+#else
+char *alloca();
+#endif
+#endif /* __GNUC__ */
+
+#ifdef _AIX
+#pragma alloca
+#endif
+
+#ifdef HAVE_STRING_H
+# include <string.h>
+#else
+# include <strings.h>
+#endif
+
+#define RE_ALLOCATE alloca
+#define FREE_VARIABLES() alloca(0)
+
+#define FREE_AND_RETURN_VOID(stackb)	return
+#define FREE_AND_RETURN(stackb,val)	return(val)
+#define DOUBLE_STACK(stackx,stackb,len,type) \
+        (stackx = (type*) alloca(2 * len * sizeof(type)),		\
+	/* Only copy what is in use.  */				\
+        (type*) memcpy(stackx, stackb, len * sizeof (type)))
+#else  /* NO_ALLOCA defined */
+
+#define RE_ALLOCATE malloc
+
+#define FREE_VAR(var) if (var) free(var); var = NULL
+#define FREE_VARIABLES()						\
+  do {									\
+    FREE_VAR(regstart);							\
+    FREE_VAR(regend);							\
+    FREE_VAR(best_regstart);						\
+    FREE_VAR(best_regend);						\
+    FREE_VAR(reg_info);							\
+  } while (0)
+
+#define FREE_AND_RETURN_VOID(stackb)   free(stackb);return
+#define FREE_AND_RETURN(stackb,val)    free(stackb);return(val)
+#define DOUBLE_STACK(stackx,stackb,len,type) \
+        (type*)xrealloc(stackb, 2 * len * sizeof(type))
+#endif /* NO_ALLOCA */
+
+#define RE_TALLOC(n,t)  ((t*)RE_ALLOCATE((n)*sizeof(t)))
+#define TMALLOC(n,t)    ((t*)xmalloc((n)*sizeof(t)))
+#define TREALLOC(s,n,t) (s=((t*)xrealloc(s,(n)*sizeof(t))))
+
+#define EXPAND_FAIL_STACK(stackx,stackb,len) \
+    do {\
+        /* Roughly double the size of the stack.  */			\
+        stackx = DOUBLE_STACK(stackx,stackb,len,unsigned char*);	\
+	/* Rearrange the pointers. */					\
+	stackp = stackx + (stackp - stackb);				\
+	stackb = stackx;						\
+	stacke = stackb + 2 * len;					\
+    } while (0);									\
+
+/* Get the interface, including the syntax bits.  */
+#include "regex.h"
+
+/* Subroutines for re_compile_pattern.  */
+static void store_jump P((char *, int, char *));
+static void insert_jump P((int, char *, char *, char *));
+static void store_jump_n P((char *, int, char *, unsigned));
+static void insert_jump_n P((int, char *, char *, char *, unsigned));
+static void insert_op P((int, char *, char *));
+static void insert_op_2 P((int, char *, char *, int, int));
+static int memcmp_translate P((unsigned char *, unsigned char *,
+			       int, unsigned char *));
+
+/* Define the syntax stuff, so we can do the \<, \>, etc.  */
+
+/* This must be nonzero for the wordchar and notwordchar pattern
+   commands in re_match_2.  */
+#ifndef Sword 
+#define Sword 1
+#endif
+
+#define SYNTAX(c) re_syntax_table[c]
+
+static char re_syntax_table[256];
+static void init_syntax_once P((void));
+
+#undef P
+
+#include "util.h"
+
+static void
+init_syntax_once()
+{
+   register int c;
+   static int done = 0;
+
+   if (done)
+     return;
+
+   memset(re_syntax_table, 0, sizeof re_syntax_table);
+
+   for (c = 'a'; c <= 'z'; c++)
+     re_syntax_table[c] = Sword;
+
+   for (c = 'A'; c <= 'Z'; c++)
+     re_syntax_table[c] = Sword;
+
+   for (c = '0'; c <= '9'; c++)
+     re_syntax_table[c] = Sword;
+
+   re_syntax_table['_'] = Sword;
+
+   /* Add specific syntax for ISO Latin-1.  */
+   for (c = 0300; c <= 0377; c++)
+     re_syntax_table[c] = Sword;
+   re_syntax_table[0327] = 0;
+   re_syntax_table[0367] = 0;
+
+   done = 1;
+}
+
+/* Sequents are missing isgraph.  */
+#ifndef isgraph
+#define isgraph(c) (isprint((c)) && !isspace((c)))
+#endif
+
+/* These are the command codes that appear in compiled regular
+   expressions, one per byte.  Some command codes are followed by
+   argument bytes.  A command code can specify any interpretation
+   whatsoever for its arguments.  Zero-bytes may appear in the compiled
+   regular expression.
+
+   The value of `exactn' is needed in search.c (search_buffer) in emacs.
+   So regex.h defines a symbol `RE_EXACTN_VALUE' to be 1; the value of
+   `exactn' we use here must also be 1.  */
+
+enum regexpcode
+  {
+    unused=0,
+    exactn=1, /* Followed by one byte giving n, then by n literal bytes.  */
+    begline,  /* Fail unless at beginning of line.  */
+    endline,  /* Fail unless at end of line.  */
+    begbuf,   /* Succeeds if at beginning of buffer (if emacs) or at beginning
+                 of string to be matched (if not).  */
+    endbuf,   /* Analogously, for end of buffer/string.  */
+    jump,     /* Followed by two bytes giving relative address to jump to.  */
+    on_failure_jump,	 /* Followed by two bytes giving relative address of 
+			    place to resume at in case of failure.  */
+    finalize_jump,	 /* Throw away latest failure point and then jump to 
+			    address.  */
+    maybe_finalize_jump, /* Like jump but finalize if safe to do so.
+			    This is used to jump back to the beginning
+			    of a repeat.  If the command that follows
+			    this jump is clearly incompatible with the
+			    one at the beginning of the repeat, such that
+			    we can be sure that there is no use backtracking
+			    out of repetitions already completed,
+			    then we finalize.  */
+    dummy_failure_jump,  /* Jump, and push a dummy failure point. This 
+			    failure point will be thrown away if an attempt 
+                            is made to use it for a failure. A + construct 
+                            makes this before the first repeat.  Also
+                            use it as an intermediary kind of jump when
+                            compiling an or construct.  */
+    succeed_n,	 /* Used like on_failure_jump except has to succeed n times;
+		    then gets turned into an on_failure_jump. The relative
+                    address following it is useless until then.  The
+                    address is followed by two bytes containing n.  */
+    jump_n,	 /* Similar to jump, but jump n times only; also the relative
+		    address following is in turn followed by yet two more bytes
+                    containing n.  */
+    try_next,    /* Jump to next pattern for the first time,
+		    leaving this pattern on the failure stack. */
+    finalize_push,	/* Finalize stack and push the beginning of the pattern
+			   on the stack to retry (used for non-greedy match) */
+    finalize_push_n,	/* Similar to finalize_push, buf finalize n time only */
+    set_number_at,	/* Set the following relative location to the
+			   subsequent number.  */
+    anychar,	 /* Matches any (more or less) one character.  */
+    charset,     /* Matches any one char belonging to specified set.
+		    First following byte is number of bitmap bytes.
+		    Then come bytes for a bitmap saying which chars are in.
+		    Bits in each byte are ordered low-bit-first.
+		    A character is in the set if its bit is 1.
+		    A character too large to have a bit in the map
+		    is automatically not in the set.  */
+    charset_not, /* Same parameters as charset, but match any character
+                    that is not one of those specified.  */
+    start_memory, /* Start remembering the text that is matched, for
+		    storing in a memory register.  Followed by one
+                    byte containing the register number.  Register numbers
+                    must be in the range 0 through RE_NREGS.  */
+    stop_memory, /* Stop remembering the text that is matched
+		    and store it in a memory register.  Followed by
+                    one byte containing the register number. Register
+                    numbers must be in the range 0 through RE_NREGS.  */
+    start_nowidth, /* Save string point to the stack. */
+    stop_nowidth,  /* Restore string place at the point start_nowidth. */
+    pop_and_fail,  /* Fail after popping nowidth entry from stack. */
+    duplicate,   /* Match a duplicate of something remembered.
+		    Followed by one byte containing the index of the memory 
+                    register.  */
+    wordchar,    /* Matches any word-constituent character.  */
+    notwordchar, /* Matches any char that is not a word-constituent.  */
+    wordbeg,	 /* Succeeds if at word beginning.  */
+    wordend,	 /* Succeeds if at word end.  */
+    wordbound,   /* Succeeds if at a word boundary.  */
+    notwordbound,/* Succeeds if not at a word boundary.  */
+  };
+
+
+/* Number of failure points to allocate space for initially,
+   when matching.  If this number is exceeded, more space is allocated,
+   so it is not a hard limit.  */
+
+#ifndef NFAILURES
+#define NFAILURES 80
+#endif
+
+#if defined(CHAR_UNSIGNED) || defined(__CHAR_UNSIGNED__)
+#define SIGN_EXTEND_CHAR(c) ((c)>(char)127?(c)-256:(c)) /* for IBM RT */
+#endif
+#ifndef SIGN_EXTEND_CHAR
+#define SIGN_EXTEND_CHAR(x) (x)
+#endif
+
+
+/* Store NUMBER in two contiguous bytes starting at DESTINATION.  */
+#define STORE_NUMBER(destination, number)				\
+  { (destination)[0] = (number) & 0377;					\
+    (destination)[1] = (number) >> 8; }
+
+/* Same as STORE_NUMBER, except increment the destination pointer to
+   the byte after where the number is stored.  Watch out that values for
+   DESTINATION such as p + 1 won't work, whereas p will.  */
+#define STORE_NUMBER_AND_INCR(destination, number)			\
+  { STORE_NUMBER(destination, number);					\
+    (destination) += 2; }
+
+
+/* Put into DESTINATION a number stored in two contingous bytes starting
+   at SOURCE.  */
+#define EXTRACT_NUMBER(destination, source)				\
+  { (destination) = *(source) & 0377;					\
+    (destination) += SIGN_EXTEND_CHAR (*(char *)((source) + 1)) << 8; }
+
+/* Same as EXTRACT_NUMBER, except increment the pointer for source to
+   point to second byte of SOURCE.  Note that SOURCE has to be a value
+   such as p, not, e.g., p + 1. */
+#define EXTRACT_NUMBER_AND_INCR(destination, source)			\
+  { EXTRACT_NUMBER(destination, source);				\
+    (source) += 2; }
+
+
+/* Specify the precise syntax of regexps for compilation.  This provides
+   for compatibility for various utilities which historically have
+   different, incompatible syntaxes.
+
+   The argument SYNTAX is a bit-mask comprised of the various bits
+   defined in regex.h.  */
+
+long
+re_set_syntax(syntax)
+  long syntax;
+{
+  long ret;
+
+  ret = re_syntax_options;
+  re_syntax_options = syntax;
+  return ret;
+}
+
+/* Set by re_set_syntax to the current regexp syntax to recognize.  */
+long re_syntax_options = DEFAULT_MBCTYPE;
+
+
+/* Macros for re_compile_pattern, which is found below these definitions.  */
+
+/* Fetch the next character in the uncompiled pattern---translating it 
+   if necessary.  Also cast from a signed character in the constant
+   string passed to us by the user to an unsigned char that we can use
+   as an array index (in, e.g., `translate').  */
+#define PATFETCH(c)							\
+  do {if (p == pend) goto end_of_pattern;				\
+    c = (unsigned char) *p++; 						\
+    if (translate) c = (unsigned char)translate[c];			\
+  } while (0)
+
+/* Fetch the next character in the uncompiled pattern, with no
+   translation.  */
+#define PATFETCH_RAW(c)							\
+  do {if (p == pend) goto end_of_pattern;				\
+    c = (unsigned char) *p++; 						\
+  } while (0)
+
+/* Go backwards one character in the pattern.  */
+#define PATUNFETCH p--
+
+
+/* If the buffer isn't allocated when it comes in, use this.  */
+#define INIT_BUF_SIZE  28
+
+/* Make sure we have at least N more bytes of space in buffer.  */
+#define GET_BUFFER_SPACE(n)						\
+  {								        \
+    while (b - bufp->buffer + (n) >= bufp->allocated)			\
+      EXTEND_BUFFER;							\
+  }
+
+/* Make sure we have one more byte of buffer space and then add CH to it.  */
+#define BUFPUSH(ch)							\
+  {									\
+    GET_BUFFER_SPACE(1);						\
+    *b++ = (char)(ch);							\
+  }
+
+/* Extend the buffer by twice its current size via reallociation and
+   reset the pointers that pointed into the old allocation to point to
+   the correct places in the new allocation.  If extending the buffer
+   results in it being larger than 1 << 16, then flag memory exhausted.  */
+#define EXTEND_BUFFER							\
+  { char *old_buffer = bufp->buffer;					\
+    if (bufp->allocated == (1L<<16)) goto too_big;			\
+    bufp->allocated *= 2;						\
+    if (bufp->allocated > (1L<<16)) bufp->allocated = (1L<<16);		\
+    bufp->buffer = (char *) xrealloc (bufp->buffer, bufp->allocated);	\
+    if (bufp->buffer == 0)						\
+      goto memory_exhausted;						\
+    b = (b - old_buffer) + bufp->buffer;				\
+    if (fixup_jump)							\
+      fixup_jump = (fixup_jump - old_buffer) + bufp->buffer;		\
+    if (laststart)							\
+      laststart = (laststart - old_buffer) + bufp->buffer;		\
+    begalt = (begalt - old_buffer) + bufp->buffer;			\
+    if (pending_exact)							\
+      pending_exact = (pending_exact - old_buffer) + bufp->buffer;	\
+  }
+
+
+/* Set the bit for character C in a character set list.  */
+#define SET_LIST_BIT(c)							\
+  (b[(unsigned char)(c) / BYTEWIDTH]					\
+   |= 1 << ((unsigned char)(c) % BYTEWIDTH))
+
+/* Get the next unsigned number in the uncompiled pattern.  */
+#define GET_UNSIGNED_NUMBER(num) 					\
+  { if (p != pend) 							\
+      { 								\
+        PATFETCH(c); 							\
+	while (isdigit(c)) 						\
+	  { 								\
+	    if (num < 0) 						\
+	       num = 0; 						\
+            num = num * 10 + c - '0'; 					\
+	    if (p == pend) 						\
+	       break; 							\
+	    PATFETCH(c); 						\
+	  } 								\
+        } 								\
+  }
+
+
+#define STORE_MBC(p, c) \
+  ((p)[0] = (unsigned char)(c >> 8), (p)[1] = (unsigned char)(c))
+#define STORE_MBC_AND_INCR(p, c) \
+  (*(p)++ = (unsigned char)(c >> 8), *(p)++ = (unsigned char)(c))
+
+#define EXTRACT_MBC(p) \
+  ((unsigned short)((unsigned char)(p)[0] << 8 | (unsigned char)(p)[1]))
+#define EXTRACT_MBC_AND_INCR(p) \
+  ((unsigned short)((p) += 2, (unsigned char)(p)[-2] << 8 | (unsigned char)(p)[-1]))
+
+#define EXTRACT_UNSIGNED(p) \
+  ((unsigned char)(p)[0] | (unsigned char)(p)[1] << 8)
+#define EXTRACT_UNSIGNED_AND_INCR(p) \
+  ((p) += 2, (unsigned char)(p)[-2] | (unsigned char)(p)[-1] << 8)
+
+/* Handle (mb)?charset(_not)?.
+
+   Structure of mbcharset(_not)? in compiled pattern.
+
+     struct {
+       unsinged char id;		mbcharset(_not)?
+       unsigned char sbc_size;
+       unsigned char sbc_map[sbc_size];	same as charset(_not)? up to here.
+       unsigned short mbc_size;		number of intervals.
+       struct {
+	 unsigned short beg;		beginning of interval.
+	 unsigned short end;		end of interval.
+       } intervals[mbc_size];
+     }; */
+
+static void
+set_list_bits(c1, c2, b)
+    unsigned short c1, c2;
+    unsigned char *b;
+{
+  unsigned char sbc_size = b[-1];
+  unsigned short mbc_size = EXTRACT_UNSIGNED(&b[sbc_size]);
+  unsigned short beg, end, upb;
+
+  if (c1 > c2)
+    return;
+  if ((int)c1 < 1 << BYTEWIDTH) {
+    upb = c2;
+    if (1 << BYTEWIDTH <= (int)upb)
+      upb = (1 << BYTEWIDTH) - 1;	/* The last single-byte char */
+    if (sbc_size <= (unsigned short)(upb / BYTEWIDTH)) {
+      /* Allocate maximum size so it never happens again.  */
+      /* NOTE: memcpy() would not work here.  */
+      memmove(&b[(1 << BYTEWIDTH) / BYTEWIDTH], &b[sbc_size], 2 + mbc_size*4);
+      memset(&b[sbc_size], 0, (1 << BYTEWIDTH) / BYTEWIDTH - sbc_size);
+      b[-1] = sbc_size = (1 << BYTEWIDTH) / BYTEWIDTH;
+    }
+    for (; c1 <= upb; c1++)
+	if (!ismbchar(c1))
+	    SET_LIST_BIT(c1);
+    if ((int)c2 < 1 << BYTEWIDTH)
+      return;
+    c1 = 0x8000;			/* The first wide char */
+  }
+  b = &b[sbc_size + 2];
+
+  for (beg = 0, upb = mbc_size; beg < upb; ) {
+    unsigned short mid = (unsigned short)(beg + upb) >> 1;
+
+    if ((int)c1 - 1 > (int)EXTRACT_MBC(&b[mid*4 + 2]))
+      beg = mid + 1;
+    else
+      upb = mid;
+  }
+
+  for (end = beg, upb = mbc_size; end < upb; ) {
+    unsigned short mid = (unsigned short)(end + upb) >> 1;
+
+    if ((int)c2 >= (int)EXTRACT_MBC(&b[mid*4]) - 1)
+      end = mid + 1;
+    else
+      upb = mid;
+  }
+
+  if (beg != end) {
+    if (c1 > EXTRACT_MBC(&b[beg*4]))
+      c1 = EXTRACT_MBC(&b[beg*4]);
+    if (c2 < EXTRACT_MBC(&b[(end - 1)*4]))
+      c2 = EXTRACT_MBC(&b[(end - 1)*4]);
+  }
+  if (end < mbc_size && end != beg + 1)
+    /* NOTE: memcpy() would not work here.  */
+    memmove(&b[(beg + 1)*4], &b[end*4], (mbc_size - end)*4);
+  STORE_MBC(&b[beg*4 + 0], c1);
+  STORE_MBC(&b[beg*4 + 2], c2);
+  mbc_size += beg - end + 1;
+  STORE_NUMBER(&b[-2], mbc_size);
+}
+
+static int
+is_in_list(c, b)
+    unsigned short c;
+    const unsigned char *b;
+{
+    unsigned short size;
+    unsigned short i, j;
+    int result = 0;
+
+    size = *b++;
+    if ((int)c < 1<<BYTEWIDTH) {
+	if ((int)c / BYTEWIDTH < (int)size && b[c / BYTEWIDTH] & 1 << c % BYTEWIDTH) {
+	    return 1;
+	}
+    }
+    b += size + 2;
+    size = EXTRACT_UNSIGNED(&b[-2]);
+    if (size == 0) return 0;
+
+    if (b[(size-1)*4] == 0xff) {
+	i = c;
+	if ((int)c >= 1<<BYTEWIDTH) {
+	    i = i>>BYTEWIDTH;
+	}
+	while (size>0 && b[size*4-2] == 0xff) {
+	    size--;
+	    if (b[size*4+1] <= i && i <= b[size*4+3]) {
+		result = 2;
+		break;
+	    }
+	}
+    }
+    for (i = 0, j = size; i < j; ) {
+	unsigned short k = (unsigned short)(i + j) >> 1;
+
+	if (c > EXTRACT_MBC(&b[k*4+2]))
+	    i = k + 1;
+	else
+	    j = k;
+    }
+    if (i < size && EXTRACT_MBC(&b[i*4]) <= c
+	&& ((unsigned char)c != '\n' && (unsigned char)c != '\0'))
+	return 1;
+    return result;
+}
+
+static void
+print_partial_compiled_pattern(start, end)
+    unsigned char *start;
+    unsigned char *end;
+{
+  int mcnt, mcnt2;
+  unsigned char *p = start;
+  unsigned char *pend = end;
+
+  if (start == NULL)
+    {
+      printf ("(null)\n");
+      return;
+    }
+    
+  /* Loop over pattern commands.  */
+  while (p < pend)
+    {
+      switch ((enum regexpcode) *p++)
+	{
+	case unused:
+	  printf ("/unused");
+	  break;
+
+	case exactn:
+	  mcnt = *p++;
+          printf ("/exactn/%d", mcnt);
+          do
+	    {
+              putchar('/');
+	      printf("%c", *p++);
+            }
+          while (--mcnt);
+          break;
+
+	case start_memory:
+          mcnt = *p++;
+          printf ("/start_memory/%d", mcnt);
+          break;
+
+	case stop_memory:
+          mcnt = *p++;
+	  printf ("/stop_memory/%d", mcnt);
+          break;
+
+	case start_nowidth:
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+	  printf ("/start_nowidth//%d", mcnt);
+	  break;
+
+	case stop_nowidth:
+	  printf ("/stop_nowidth//");
+	  p += 2;
+	  break;
+
+	case pop_and_fail:
+	  printf ("/pop_and_fail");
+	  break;
+
+	case duplicate:
+	  printf ("/duplicate/%d", *p++);
+	  break;
+
+	case anychar:
+	  printf ("/anychar");
+	  break;
+
+	case charset:
+        case charset_not:
+          {
+            register int c;
+
+            printf ("/charset%s",
+	            (enum regexpcode) *(p - 1) == charset_not ? "_not" : "");
+
+            mcnt = *p;
+	    printf("/%d", mcnt);
+            for (c = 0; c < mcnt; c++)
+              {
+                unsigned bit;
+                unsigned char map_byte = p[1 + c];
+
+		putchar ('/');
+                
+		for (bit = 0; bit < BYTEWIDTH; bit++)
+                  if (map_byte & (1 << bit))
+		    printf("%c", c * BYTEWIDTH + bit);
+              }
+	    p += mcnt + 1;
+	    mcnt = EXTRACT_UNSIGNED(p);
+	    p += 2;
+	    while (mcnt--) {
+		int beg = *p++;
+		int end = *p++;
+		printf("/%c%c-%c%c", beg>>BYTEWIDTH, beg&0xff, end>>BYTEWIDTH, end&0xff);
+	    }
+	    break;
+	  }
+
+	case begline:
+	  printf ("/begline");
+          break;
+
+	case endline:
+          printf ("/endline");
+          break;
+
+	case on_failure_jump:
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+  	  printf ("/on_failure_jump//%d", mcnt);
+          break;
+
+	case dummy_failure_jump:
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+  	  printf ("/dummy_failure_jump//%d", mcnt);
+          break;
+
+        case finalize_jump:
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+  	  printf ("/finalize_jump//%d", mcnt);
+	  break;
+
+        case maybe_finalize_jump:
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+  	  printf ("/maybe_finalize_jump//%d", mcnt);
+	  break;
+
+        case jump:
+	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
+  	  printf ("/jump//%d", mcnt);
+	  break;
+
+        case succeed_n: 
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+          EXTRACT_NUMBER_AND_INCR (mcnt2, p);
+ 	  printf ("/succeed_n//%d//%d", mcnt, mcnt2);
+          break;
+        
+        case jump_n: 
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+          EXTRACT_NUMBER_AND_INCR (mcnt2, p);
+ 	  printf ("/jump_n//%d//%d", mcnt, mcnt2);
+          break;
+        
+        case set_number_at: 
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+          EXTRACT_NUMBER_AND_INCR (mcnt2, p);
+ 	  printf ("/set_number_at//%d//%d", mcnt, mcnt2);
+          break;
+        
+	case try_next:
+	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
+  	  printf ("/try_next//%d", mcnt);
+          break;
+
+	case finalize_push:
+	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
+  	  printf ("/finalize_push//%d", mcnt);
+          break;
+
+	case finalize_push_n:
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+          EXTRACT_NUMBER_AND_INCR (mcnt2, p);
+ 	  printf ("/finalize_push_n//%d//%d", mcnt, mcnt2);
+          break;
+
+        case wordbound:
+	  printf ("/wordbound");
+	  break;
+
+	case notwordbound:
+	  printf ("/notwordbound");
+          break;
+
+	case wordbeg:
+	  printf ("/wordbeg");
+	  break;
+          
+	case wordend:
+	  printf ("/wordend");
+          
+	case wordchar:
+	  printf ("/wordchar");
+          break;
+	  
+	case notwordchar:
+	  printf ("/notwordchar");
+          break;
+
+	case begbuf:
+	  printf ("/begbuf");
+          break;
+
+	case endbuf:
+	  printf ("/endbuf");
+          break;
+
+        default:
+          printf ("?%d", *(p-1));
+	}
+    }
+  printf ("/\n");
+}
+
+
+static void
+print_compiled_pattern(bufp)
+    struct re_pattern_buffer *bufp;
+{
+  unsigned char *buffer = bufp->buffer;
+
+  print_partial_compiled_pattern (buffer, buffer + bufp->used);
+}
+
+static char*
+calculate_must_string(start, end)
+    unsigned char *start;
+    unsigned char *end;
+{
+  int mcnt, mcnt2;
+  int max = 0;
+  unsigned char *p = start;
+  unsigned char *pend = end;
+  unsigned char *must = 0;
+
+  if (start == NULL) return 0;
+    
+  /* Loop over pattern commands.  */
+  while (p < pend)
+    {
+      switch ((enum regexpcode) *p++)
+	{
+	case unused:
+	  break;
+
+	case exactn:
+	  mcnt = *p;
+	  if (mcnt > max) {
+	    must = p;
+	  }
+	  p += mcnt+1;
+          break;
+
+	case start_memory:
+	case stop_memory:
+	case duplicate:
+          p++;
+          break;
+
+	case start_nowidth:
+	case stop_nowidth:
+	case pop_and_fail:
+	case anychar:
+	case begline:
+	case endline:
+        case wordbound:
+	case notwordbound:
+	case wordbeg:
+	case wordend:
+	case wordchar:
+	case notwordchar:
+	case begbuf:
+	case endbuf:
+	  break;
+
+	case charset:
+        case charset_not:
+	  mcnt = *p++;
+	  p += mcnt;
+	  EXTRACT_NUMBER_AND_INCR (mcnt, p);
+	  while (mcnt--) {
+	    EXTRACT_NUMBER_AND_INCR (mcnt2, p);
+	    EXTRACT_NUMBER_AND_INCR (mcnt2, p);
+	  }
+	  break;
+
+	case on_failure_jump:
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+	  if (mcnt > 0) p += mcnt;
+	  if ((enum regexpcode)p[-3] == jump) {
+	    p -= 3;
+	    EXTRACT_NUMBER_AND_INCR (mcnt, p);
+	    if (mcnt > 0) p += mcnt;
+	  }
+          break;
+
+	case dummy_failure_jump:
+        case succeed_n: 
+	case try_next:
+	case jump:
+          EXTRACT_NUMBER_AND_INCR (mcnt, p);
+	  if (mcnt > 0) p += mcnt;
+          break;
+
+        case finalize_jump:
+        case maybe_finalize_jump:
+	case finalize_push:
+	  p += 2;
+	  break;
+
+        case jump_n: 
+        case set_number_at: 
+	case finalize_push_n:
+	  p += 4;
+          break;
+
+        default:
+	  break;
+	}
+    }
+  return must;
+}
+
+
+/* re_compile_pattern takes a regular-expression string
+   and converts it into a buffer full of byte commands for matching.
+
+   PATTERN   is the address of the pattern string
+   SIZE      is the length of it.
+   BUFP	    is a  struct re_pattern_buffer *  which points to the info
+	     on where to store the byte commands.
+	     This structure contains a  char *  which points to the
+	     actual space, which should have been obtained with malloc.
+	     re_compile_pattern may use realloc to grow the buffer space.
+
+   The number of bytes of commands can be found out by looking in
+   the `struct re_pattern_buffer' that bufp pointed to, after
+   re_compile_pattern returns. */
+
+char *
+re_compile_pattern(pattern, size, bufp)
+     char *pattern;
+     size_t size;
+     struct re_pattern_buffer *bufp;
+{
+    register char *b = bufp->buffer;
+    register char *p = pattern;
+    char *pend = pattern + size;
+    register unsigned c, c1;
+    char *p0;
+    int numlen;
+
+    /* Address of the count-byte of the most recently inserted `exactn'
+       command.  This makes it possible to tell whether a new exact-match
+       character can be added to that command or requires a new `exactn'
+       command.  */
+
+    char *pending_exact = 0;
+
+    /* Address of the place where a forward-jump should go to the end of
+       the containing expression.  Each alternative of an `or', except the
+       last, ends with a forward-jump of this sort.  */
+
+    char *fixup_jump = 0;
+
+    /* Address of start of the most recently finished expression.
+       This tells postfix * where to find the start of its operand.  */
+
+    char *laststart = 0;
+
+    /* In processing a repeat, 1 means zero matches is allowed.  */
+
+    char zero_times_ok;
+
+    /* In processing a repeat, 1 means many matches is allowed.  */
+
+    char many_times_ok;
+
+    /* In processing a repeat, 1 means non-greedy matches.  */
+
+    char greedy;
+
+    /* Address of beginning of regexp, or inside of last \(.  */
+
+    char *begalt = b;
+
+    /* In processing an interval, at least this many matches must be made.  */
+    int lower_bound;
+
+    /* In processing an interval, at most this many matches can be made.  */
+    int upper_bound;
+
+    /* Stack of information saved by \( and restored by \).
+       Five stack elements are pushed by each \(:
+       First, the value of b.
+       Second, the value of fixup_jump.
+       Third, the value of begalt.
+       Fourth, the value of regnum.
+       Fifth, the type of the paren. */
+
+    int *stackb = RE_TALLOC(40, int);
+    int *stackp = stackb;
+    int *stacke = stackb + 40;
+    int *stackt;
+
+    /* Counts \('s as they are encountered.  Remembered for the matching \),
+       where it becomes the register number to put in the stop_memory
+       command.  */
+
+    int regnum = 1;
+    int range = 0;
+
+    /* How to translate the characters in the pattern.  */
+    char *translate = bufp->translate;
+
+    bufp->fastmap_accurate = 0;
+
+    /* Initialize the syntax table.  */
+    init_syntax_once();
+
+    if (bufp->allocated == 0)
+	{
+	    bufp->allocated = INIT_BUF_SIZE;
+	    if (bufp->buffer)
+		/* EXTEND_BUFFER loses when bufp->allocated is 0.  */
+		bufp->buffer = (char *) xrealloc (bufp->buffer, INIT_BUF_SIZE);
+	    else
+		/* Caller did not allocate a buffer.  Do it for them.  */
+	bufp->buffer = (char *) xmalloc(INIT_BUF_SIZE);
+      if (!bufp->buffer) goto memory_exhausted;
+      begalt = b = bufp->buffer;
+    }
+
+  while (p != pend)
+    {
+      PATFETCH(c);
+
+      switch (c)
+	{
+	case '$':
+	  {
+	    char *p1 = p;
+	    /* When testing what follows the $,
+	       look past the \-constructs that don't consume anything.  */
+	    if (! (re_syntax_options & RE_CONTEXT_INDEP_OPS))
+	      while (p1 != pend)
+		{
+		  if (*p1 == '\\' && p1 + 1 != pend
+		      && (p1[1] == 'b' || p1[1] == 'B'))
+		    p1 += 2;
+		  else
+		    break;
+		}
+            if (re_syntax_options & RE_TIGHT_VBAR)
+	      {
+		if (! (re_syntax_options & RE_CONTEXT_INDEP_OPS) && p1 != pend)
+		  goto normal_char;
+		/* Make operand of last vbar end before this `$'.  */
+		if (fixup_jump)
+		  store_jump(fixup_jump, jump, b);
+		fixup_jump = 0;
+		BUFPUSH(endline);
+		break;
+	      }
+	    /* $ means succeed if at end of line, but only in special contexts.
+	      If validly in the middle of a pattern, it is a normal character. */
+
+	    if (p1 == pend || *p1 == '\n'
+		|| (re_syntax_options & RE_CONTEXT_INDEP_OPS)
+		|| (re_syntax_options & RE_NO_BK_PARENS
+		    ? *p1 == ')'
+		    : *p1 == '\\' && p1[1] == ')')
+		|| (re_syntax_options & RE_NO_BK_VBAR
+		    ? *p1 == '|'
+		    : *p1 == '\\' && p1[1] == '|'))
+	      {
+		BUFPUSH(endline);
+		break;
+	      }
+	    goto normal_char;
+          }
+	case '^':
+	  /* ^ means succeed if at beg of line, but only if no preceding 
+             pattern.  */
+
+          if ((re_syntax_options & RE_CONTEXTUAL_INVALID_OPS) && laststart)
+            goto invalid_pattern;
+          if (laststart && p - 2 >= pattern && p[-2] != '\n'
+	       && !(re_syntax_options & RE_CONTEXT_INDEP_OPS))
+	    goto normal_char;
+	  if (re_syntax_options & RE_TIGHT_VBAR)
+	    {
+	      if (p != pattern + 1
+		  && ! (re_syntax_options & RE_CONTEXT_INDEP_OPS))
+		goto normal_char;
+	      BUFPUSH(begline);
+	      begalt = b;
+	    }
+	  else
+	    {
+	      BUFPUSH(begline);
+	    }
+	  break;
+
+	case '+':
+	case '?':
+	  if (re_syntax_options & RE_LIMITED_OPS)
+	    goto normal_char;
+	case '*':
+	  /* If there is no previous pattern, char not special. */
+	  if (!laststart) {
+	    if (re_syntax_options & RE_CONTEXTUAL_INVALID_OPS)
+	      goto invalid_pattern;
+	    else if (! (re_syntax_options & RE_CONTEXT_INDEP_OPS))
+	      goto normal_char;
+	  }
+	  /* If there is a sequence of repetition chars,
+	     collapse it down to just one.  */
+	  zero_times_ok = c != '+';
+	  many_times_ok = c != '?';
+	  greedy = 1;
+	  if (p != pend) {
+	    PATFETCH(c);
+	    switch (c) {
+	      case '?':
+		greedy = 0;
+		break;
+	      case '*':
+	      case '+':
+		goto nested_meta;
+	      default:
+		PATUNFETCH;
+		break;
+	    }
+	  }
+
+	repeat:
+	  /* Star, etc. applied to an empty pattern is equivalent
+	     to an empty pattern.  */
+	  if (!laststart)  
+	    break;
+
+	  /* Now we know whether or not zero matches is allowed
+	     and also whether or not two or more matches is allowed.  */
+	  if (many_times_ok) {
+	    /* If more than one repetition is allowed, put in at the
+	       end a backward relative jump from b to before the next
+	       jump we're going to put in below (which jumps from
+	       laststart to after this jump).  */
+	    GET_BUFFER_SPACE(3);
+	    store_jump(b,greedy?maybe_finalize_jump:finalize_push,laststart-3);
+	    b += 3;  	/* Because store_jump put stuff here.  */
+	  }
+
+	  /* On failure, jump from laststart to next pattern, which will be the
+	     end of the buffer after this jump is inserted.  */
+	  GET_BUFFER_SPACE(3);
+	  insert_jump(on_failure_jump, laststart, b + 3, b);
+	  b += 3;
+
+	  if (zero_times_ok) {
+	    if (greedy == 0) {
+	      GET_BUFFER_SPACE(3);
+	      insert_jump(try_next, laststart, b + 3, b);
+	      b += 3;
+	    }
+	  }
+	  else {
+	    /* At least one repetition is required, so insert a
+	       `dummy_failure_jump' before the initial
+	       `on_failure_jump' instruction of the loop. This
+	       effects a skip over that instruction the first time
+	       we hit that loop.  */
+	    GET_BUFFER_SPACE(3);
+	    insert_jump(dummy_failure_jump, laststart, laststart + 6, b);
+	    b += 3;
+	  }
+	  break;
+
+	case '.':
+	  laststart = b;
+	  BUFPUSH(anychar);
+	  break;
+
+        case '[':
+          if (p == pend)
+            goto invalid_pattern;
+	  while (b - bufp->buffer
+		 > bufp->allocated - 9 - (1 << BYTEWIDTH) / BYTEWIDTH)
+	    EXTEND_BUFFER;
+
+	  laststart = b;
+	  if (*p == '^')
+	    {
+              BUFPUSH(charset_not); 
+              p++;
+            }
+	  else
+	    BUFPUSH(charset);
+	  p0 = p;
+
+	  BUFPUSH((1 << BYTEWIDTH) / BYTEWIDTH);
+	  /* Clear the whole map */
+	  memset(b, 0, (1 << BYTEWIDTH) / BYTEWIDTH + 2);
+
+	  if ((re_syntax_options & RE_HAT_NOT_NEWLINE) && b[-2] == charset_not)
+            SET_LIST_BIT('\n');
+
+
+	  /* Read in characters and ranges, setting map bits.  */
+	  for (;;)
+	    {
+	      int size;
+	      unsigned last = (unsigned)-1;
+
+	      if ((size = EXTRACT_UNSIGNED(&b[(1 << BYTEWIDTH) / BYTEWIDTH]))) {
+		/* Ensure the space is enough to hold another interval
+		   of multi-byte chars in charset(_not)?.  */
+		size = (1 << BYTEWIDTH) / BYTEWIDTH + 2 + size*4 + 4;
+		while (b + size + 1 > bufp->buffer + bufp->allocated)
+		  EXTEND_BUFFER;
+	      }
+	    range_retry:
+	      PATFETCH(c);
+
+              if (c == ']') {
+                  if (p == p0 + 1) {
+		      /* If this is an empty bracket expression.  */
+                      if ((re_syntax_options & RE_NO_EMPTY_BRACKETS) 
+                          && p == pend)
+			  goto invalid_pattern;
+		  }
+                  else 
+		    /* Stop if this isn't merely a ] inside a bracket
+                       expression, but rather the end of a bracket
+                       expression.  */
+		      break;
+	      }
+	      if (ismbchar(c)) {
+		PATFETCH(c1);
+		c = c << BYTEWIDTH | c1;
+	      }
+
+	      /* \ escapes characters when inside [...].  */
+	      if (c == '\\') {
+	          PATFETCH(c);
+		  switch (c) {
+		    case 'w':
+		      for (c = 0; c < (1 << BYTEWIDTH); c++)
+		          if (SYNTAX(c) == Sword)
+			      SET_LIST_BIT(c);
+		      last = -1;
+		      continue;
+
+		    case 'W':
+		      for (c = 0; c < (1 << BYTEWIDTH); c++)
+		          if (SYNTAX(c) != Sword)
+			      SET_LIST_BIT(c);
+		      if (re_syntax_options & RE_MBCTYPE_MASK) {
+			  set_list_bits(0x8000, 0xffff, (unsigned char*)b);
+		      }
+		      last = -1;
+		      continue;
+
+		    case 's':
+		      for (c = 0; c < 256; c++)
+			  if (isspace(c))
+			      SET_LIST_BIT(c);
+		      last = -1;
+		      continue;
+
+		    case 'S':
+		      for (c = 0; c < 256; c++)
+			  if (!isspace(c))
+			      SET_LIST_BIT(c);
+		      if (re_syntax_options & RE_MBCTYPE_MASK) {
+			  set_list_bits(0x8000, 0xffff, (unsigned char*)b);
+		      }
+		      last = -1;
+		      continue;
+
+		    case 'd':
+		      for (c = '0'; c <= '9'; c++)
+			  SET_LIST_BIT(c);
+		      last = -1;
+		      continue;
+
+		    case 'D':
+		      for (c = 0; c < 256; c++)
+			  if (!isdigit(c))
+			      SET_LIST_BIT(c);
+		      if (re_syntax_options & RE_MBCTYPE_MASK) {
+			  set_list_bits(0x8000, 0xffff, (unsigned char*)b);
+		      }
+		      last = -1;
+		      continue;
+
+		    case 'x':
+		      c = scan_hex(p, 2, &numlen);
+		      if ((re_syntax_options & RE_MBCTYPE_MASK) && c > 0x7f)
+			  c = 0xff00 | c;
+		      p += numlen;
+		      break;
+
+		    case '0': case '1': case '2': case '3': case '4':
+		    case '5': case '6': case '7': case '8': case '9':
+		      PATUNFETCH;
+		      c = scan_oct(p, 3, &numlen);
+		      if ((re_syntax_options & RE_MBCTYPE_MASK) && ismbchar(c))
+			  c = 0xff00 | c;
+		      p += numlen;
+		      break;
+
+		    default:
+		      if (ismbchar(c)) {
+			  PATFETCH(c1);
+			  c = c << 8 | c1;
+		      }
+		      break;
+		  }
+	      }
+
+              /* Get a range.  */
+	      if (range) {
+		  if (last > c)
+                    goto invalid_pattern;
+
+		  if ((re_syntax_options & RE_NO_HYPHEN_RANGE_END) 
+                      && c == '-' && *p != ']')
+                    goto invalid_pattern;
+
+		  range = 0;
+		  if (last < 1 << BYTEWIDTH && c < 1 << BYTEWIDTH) {
+		      for (;last<=c;last++)
+			  SET_LIST_BIT(last);
+		  }
+		  else {
+		      set_list_bits(last, c, (unsigned char*)b);
+		  }
+	      }
+              else if (p[0] == '-' && p[1] != ']') {
+		  last = c;
+		  PATFETCH(c1);
+		  range = 1;
+		  goto range_retry;
+	      }
+              else if (c < 1 << BYTEWIDTH)
+		SET_LIST_BIT(c);
+	      else
+		set_list_bits(c, c, (unsigned char*)b);
+	    }
+
+          /* Discard any character set/class bitmap bytes that are all
+             0 at the end of the map. Decrement the map-length byte too.  */
+          while ((int) b[-1] > 0 && b[b[-1] - 1] == 0) 
+            b[-1]--; 
+	  if (b[-1] != (1 << BYTEWIDTH) / BYTEWIDTH)
+	    memmove(&b[b[-1]], &b[(1 << BYTEWIDTH) / BYTEWIDTH],
+		    2 + EXTRACT_UNSIGNED (&b[(1 << BYTEWIDTH) / BYTEWIDTH])*4);
+	  b += b[-1] + 2 + EXTRACT_UNSIGNED (&b[b[-1]])*4;
+          break;
+
+	case '(':
+	  PATFETCH(c);
+	  if (c == '?') {
+	      PATFETCH(c);
+	      switch (c) {
+		case '#':
+		case 'i':
+		case 'm':
+		case 's':
+		case 'x':
+		  for (;;) {
+		      PATFETCH(c);
+		      if (c == ')') break;
+		  }
+		  c = '#';
+		  break;
+
+		case ':':
+		case '=':
+		case '!':
+		  break;
+
+		default:
+		  FREE_AND_RETURN(stackb, "undefined (?...) sequence");
+	      }
+	  }
+	  else {
+	    PATUNFETCH;
+	    c = '(';
+	  }
+	  if (c == '#') break;
+	  if (stackp+6 >= stacke) {
+	    int *stackx;
+	    unsigned int len = stacke - stackb;
+
+	    stackx = DOUBLE_STACK(stackx,stackb,len,int);
+	    /* Rearrange the pointers. */
+	    stackp = stackx + (stackp - stackb);
+	    stackb = stackx;
+	    stacke = stackb + 2 * len;
+	  }
+
+	  /* Laststart should point to the start_memory that we are about
+	     to push (unless the pattern has RE_NREGS or more ('s).  */
+	  /* obsolete: now RE_NREGS is just a default register size. */
+	  *stackp++ = b - bufp->buffer;    
+	  *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0;
+	  *stackp++ = begalt - bufp->buffer;
+	  switch (c) {
+	    case '(':
+	      BUFPUSH(start_memory);
+	      BUFPUSH(regnum);
+	      *stackp++ = regnum++;
+	      /* too many ()'s to fit in a byte. (max 254) */
+	      if (regnum >= RE_REG_MAX) goto too_big;
+	      break;
+
+	    case '=':
+	    case '!':
+	      BUFPUSH(start_nowidth);
+	      *stackp++ = b - bufp->buffer;
+	      BUFPUSH(0);	/* temporary value */
+	      BUFPUSH(0);
+	      if (c == '=') break;
+
+	      BUFPUSH(on_failure_jump);
+	      *stackp++ = b - bufp->buffer;
+	      BUFPUSH(0);	/* temporary value */
+	      BUFPUSH(0);
+	      break;
+
+	    case ':':
+	    default:
+	      break;
+	  }
+	  *stackp++ = c;
+	  fixup_jump = 0;
+	  laststart = 0;
+	  begalt = b;
+	  break;
+
+	case ')':
+	  if (stackp == stackb) goto unmatched_close;
+	  switch (c = *--stackp) {
+	    case '(':
+	      if (fixup_jump)
+		store_jump(fixup_jump, jump, b);
+	      BUFPUSH(stop_memory);
+	      BUFPUSH(stackp[-1]);
+	      break;
+
+	    case '!':
+	      BUFPUSH(pop_and_fail);
+	      /* back patch */
+	      STORE_NUMBER(bufp->buffer+stackp[-1], b - bufp->buffer - stackp[-1] - 2);
+	      stackp--;
+	      /* fall through */
+	    case '=':
+	      BUFPUSH(stop_nowidth);
+	      /* tell stack-pos place to start_nowidth */
+	      STORE_NUMBER(bufp->buffer+stackp[-1], b - bufp->buffer - stackp[-1] - 2);
+	      BUFPUSH(0);	/* space to hold stack pos */
+	      BUFPUSH(0);
+	      break;
+
+	    case ':':
+	    default:
+	      break;
+	  }
+	  stackp--;
+	  begalt = *--stackp + bufp->buffer;
+	  stackp--;
+	  fixup_jump = *stackp ? *stackp + bufp->buffer - 1 : 0;
+	  laststart = *--stackp + bufp->buffer;
+	  if (c == '!' || c == '=') laststart = b;
+	  break;
+
+	case '|':
+	  /* Insert before the previous alternative a jump which
+	     jumps to this alternative if the former fails.  */
+	  GET_BUFFER_SPACE(6);
+	  insert_jump(on_failure_jump, begalt, b + 6, b);
+	  pending_exact = 0;
+	  b += 3;
+	  /* The alternative before the previous alternative has a
+	     jump after it which gets executed if it gets matched.
+	     Adjust that jump so it will jump to the previous
+	     alternative's analogous jump (put in below, which in
+	     turn will jump to the next (if any) alternative's such
+	     jump, etc.).  The last such jump jumps to the correct
+	     final destination.  */
+	  if (fixup_jump)
+	    store_jump(fixup_jump, jump, b);
+
+	  /* Leave space for a jump after previous alternative---to be 
+	     filled in later.  */
+	  fixup_jump = b;
+	  b += 3;
+
+	  laststart = 0;
+	  begalt = b;
+	  break;
+
+	case '{':
+	  /* If there is no previous pattern, this isn't an interval.  */
+	  if (!laststart)
+	    {
+	      if (re_syntax_options & RE_CONTEXTUAL_INVALID_OPS)
+		goto invalid_pattern;
+	      else
+		goto normal_backsl;
+	    }
+	  /* It also isn't an interval if not preceded by an re
+	     matching a single character or subexpression, or if
+	     the current type of intervals can't handle back
+	     references and the previous thing is a back reference.  */
+	  if (! (*laststart == anychar
+		 || *laststart == charset
+		 || *laststart == charset_not
+		 || *laststart == wordchar
+		 || *laststart == notwordchar
+		 || *laststart == start_memory
+		 || (*laststart == exactn
+		     && (laststart[1] == 1
+			 || laststart[1] == 2 && ismbchar(laststart[2])))
+		 || (! (re_syntax_options & RE_NO_BK_REFS)
+		     && *laststart == duplicate)))
+	    {
+	      /* Posix extended syntax is handled in previous
+		 statement; this is for Posix basic syntax.  */
+	      if (re_syntax_options & RE_INTERVALS)
+		goto invalid_pattern;
+
+	      goto normal_backsl;
+	    }
+	  lower_bound = -1;			/* So can see if are set.  */
+	  upper_bound = -1;
+	  GET_UNSIGNED_NUMBER(lower_bound);
+	  if (c == ',') {
+	    GET_UNSIGNED_NUMBER(upper_bound);
+	    if (upper_bound < 0)
+	      upper_bound = RE_DUP_MAX;
+	  }
+	  if (upper_bound < 0)
+	    upper_bound = lower_bound;
+	  if (c != '}' || lower_bound < 0 || upper_bound > RE_DUP_MAX
+	      || lower_bound > upper_bound 
+	      || (p != pend  && *p == '{')) {
+	    goto invalid_pattern;
+	  }
+	  greedy = 1;
+	  if (p != pend) {
+	    PATFETCH(c);
+	    if (c == '?') greedy = 0;
+	    else PATUNFETCH;
+	  }
+
+	  /* If upper_bound is zero, don't want to succeed at all; 
+	     jump from laststart to b + 3, which will be the end of
+	     the buffer after this jump is inserted.  */
+
+	  if (upper_bound == 0) {
+	    GET_BUFFER_SPACE(3);
+	    insert_jump(jump, laststart, b + 3, b);
+	    b += 3;
+	    break;
+	  }
+
+	  if (lower_bound == 0) {
+	    zero_times_ok = 1;
+	    if (upper_bound == RE_DUP_MAX) {
+	      many_times_ok = 1;
+	      goto repeat;
+	    }
+	    if (upper_bound == 1) {
+	      many_times_ok = 0;
+	      goto repeat;
+	    }
+	  }
+	  if (lower_bound == 1 && upper_bound == RE_DUP_MAX) {
+	    many_times_ok = 1;
+	    zero_times_ok = 0;
+	    goto repeat;
+	  }
+
+	  /* Star, etc. applied to an empty pattern is equivalent
+	     to an empty pattern.  */
+	  if (!laststart)  
+	    break;
+
+	  { /* If the upper bound is > 1, we need to insert
+	       more at the end of the loop.  */
+	    unsigned slots_needed = upper_bound == 1 ? 5 : 10;
+
+	    GET_BUFFER_SPACE(5);
+	    /* Initialize lower bound of the `succeed_n', even
+	       though it will be set during matching by its
+	       attendant `set_number_at' (inserted next),
+	       because `re_compile_fastmap' needs to know.
+	       Jump to the `jump_n' we might insert below.  */
+	    insert_jump_n(succeed_n, laststart, b + slots_needed, 
+			  b, lower_bound);
+	    b += 5; 	/* Just increment for the succeed_n here.  */
+
+	    /* Code to initialize the lower bound.  Insert 
+	       before the `succeed_n'.  The `5' is the last two
+	       bytes of this `set_number_at', plus 3 bytes of
+	       the following `succeed_n'.  */
+	    GET_BUFFER_SPACE(5);
+	    insert_op_2(set_number_at, laststart, b, 5, lower_bound);
+	    b += 5;
+
+	    if (upper_bound > 1)
+	      { /* More than one repetition is allowed, so
+		   append a backward jump to the `succeed_n'
+		   that starts this interval.
+
+		   When we've reached this during matching,
+		   we'll have matched the interval once, so
+		   jump back only `upper_bound - 1' times.  */
+		GET_BUFFER_SPACE(5);
+		store_jump_n(b, greedy?jump_n:finalize_push_n, laststart + 5, upper_bound - 1);
+		b += 5;
+
+		/* The location we want to set is the second
+		   parameter of the `jump_n'; that is `b-2' as
+		   an absolute address.  `laststart' will be
+		   the `set_number_at' we're about to insert;
+		   `laststart+3' the number to set, the source
+		   for the relative address.  But we are
+		   inserting into the middle of the pattern --
+		   so everything is getting moved up by 5.
+		   Conclusion: (b - 2) - (laststart + 3) + 5,
+		   i.e., b - laststart.
+
+		   We insert this at the beginning of the loop
+		   so that if we fail during matching, we'll
+		   reinitialize the bounds.  */
+		GET_BUFFER_SPACE(5);
+		insert_op_2(set_number_at, laststart, b, b - laststart, upper_bound - 1);
+		b += 5;
+
+		GET_BUFFER_SPACE(5);
+		BUFPUSH(set_number_at);
+		STORE_NUMBER_AND_INCR(b, -5);
+		STORE_NUMBER_AND_INCR(b, upper_bound - 1);
+	      }
+	    pending_exact = 0;
+	  }
+	  break;
+
+        case '\\':
+	  if (p == pend) goto invalid_pattern;
+          /* Do not translate the character after the \, so that we can
+             distinguish, e.g., \B from \b, even if we normally would
+             translate, e.g., B to b.  */
+	  PATFETCH_RAW(c);
+	  switch (c)
+	    {
+	    case 's':
+	    case 'S':
+	    case 'd':
+	    case 'D':
+	      while (b - bufp->buffer
+		     > bufp->allocated - 9 - (1 << BYTEWIDTH) / BYTEWIDTH)
+		EXTEND_BUFFER;
+
+	      laststart = b;
+	      if (c == 's' || c == 'd') {
+		BUFPUSH(charset);
+	      }
+	      else {
+		BUFPUSH(charset_not);
+	      }
+
+	      BUFPUSH((1 << BYTEWIDTH) / BYTEWIDTH);
+	      memset(b, 0, (1 << BYTEWIDTH) / BYTEWIDTH + 2);
+	      if (c == 's' || c == 'S') {
+		SET_LIST_BIT(' ');
+		SET_LIST_BIT('\t');
+		SET_LIST_BIT('\n');
+		SET_LIST_BIT('\r');
+		SET_LIST_BIT('\f');
+	      }
+	      else {
+		char cc;
+
+		for (cc = '0'; cc <= '9'; cc++) {
+		  SET_LIST_BIT(cc);
+		}
+	      }
+
+	      while ((int) b[-1] > 0 && b[b[-1] - 1] == 0) 
+		b[-1]--; 
+	      if (b[-1] != (1 << BYTEWIDTH) / BYTEWIDTH)
+		memmove(&b[b[-1]], &b[(1 << BYTEWIDTH) / BYTEWIDTH],
+		  2 + EXTRACT_UNSIGNED(&b[(1 << BYTEWIDTH) / BYTEWIDTH])*4);
+	      b += b[-1] + 2 + EXTRACT_UNSIGNED(&b[b[-1]])*4;
+	      break;
+
+	    case 'w':
+	      laststart = b;
+	      BUFPUSH(wordchar);
+	      break;
+
+	    case 'W':
+	      laststart = b;
+	      BUFPUSH(notwordchar);
+	      break;
+
+	    case '<':
+	      BUFPUSH(wordbeg);
+	      break;
+
+	    case '>':
+	      BUFPUSH(wordend);
+	      break;
+
+	    case 'b':
+	      BUFPUSH(wordbound);
+	      break;
+
+	    case 'B':
+	      BUFPUSH(notwordbound);
+	      break;
+
+	    case 'A':
+	      BUFPUSH(begbuf);
+	      break;
+
+	    case 'Z':
+	      BUFPUSH(endbuf);
+	      break;
+
+	      /* hex */
+	    case 'x':
+	      c1 = 0;
+	      c = scan_hex(p, 2, &numlen);
+	      p += numlen;
+	      if ((re_syntax_options & RE_MBCTYPE_MASK) && c > 0x7f)
+		  c1 = 0xff;
+	      goto numeric_char;
+
+	      /* octal */
+	    case '0':
+	      c1 = 0;
+	      c = scan_oct(p, 3, &numlen);
+	      p += numlen;
+	      if ((re_syntax_options & RE_MBCTYPE_MASK) && c > 0x7f)
+		  c1 = 0xff;
+	      goto numeric_char;
+
+	      /* back-ref or octal */
+	    case '1': case '2': case '3':
+	    case '4': case '5': case '6':
+	    case '7': case '8': case '9':
+	      {
+		  char *p_save;
+
+		  PATUNFETCH;
+		  p_save = p;
+
+		  c1 = 0;
+		  GET_UNSIGNED_NUMBER(c1);
+		  if (p < pend) PATUNFETCH;
+
+		  if (c1 >= regnum) {
+		      /* need to get octal */
+		      p = p_save;
+		      c = scan_oct(p_save, 3, &numlen);
+		      p = p_save + numlen;
+		      c1 = 0;
+		      if ((re_syntax_options & RE_MBCTYPE_MASK) && c > 0x7f)
+			  c1 = 0xff;
+		      goto numeric_char;
+		  }
+	      }
+
+              /* Can't back reference to a subexpression if inside of it.  */
+              for (stackt = stackp - 2;  stackt > stackb;  stackt -= 5)
+ 		if (*stackt == c1)
+		  goto normal_char;
+	      laststart = b;
+	      BUFPUSH(duplicate);
+	      BUFPUSH(c1);
+	      break;
+
+            default:
+	    normal_backsl:
+	      goto normal_char;
+	    }
+	  break;
+
+	default:
+	normal_char:		/* Expects the character in `c'.  */
+	  c1 = 0;
+	  if (ismbchar(c)) {
+	    c1 = c;
+	    PATFETCH(c);
+	  }
+	  else if (c > 0x7f) {
+	    c1 = 0xff;
+	  }
+	numeric_char:
+	  if (!pending_exact || pending_exact + *pending_exact + 1 != b
+	      || *pending_exact >= (c1 ? 0176 : 0177)
+	      || *p == '+' || *p == '?'
+	      || *p == '*' || *p == '^'
+	      || *p == '{')
+	    {
+	      laststart = b;
+	      BUFPUSH(exactn);
+	      pending_exact = b;
+	      BUFPUSH(0);
+	    }
+	  if (c1) {
+	    BUFPUSH(c1);
+	    (*pending_exact)++;
+	  }
+	  BUFPUSH(c);
+	  (*pending_exact)++;
+	}
+    }
+
+  if (fixup_jump)
+    store_jump(fixup_jump, jump, b);
+
+  if (stackp != stackb) goto unmatched_open;
+
+  bufp->used = b - bufp->buffer;
+  bufp->re_nsub = regnum;
+  bufp->must = calculate_must_string(bufp->buffer, b);
+  FREE_AND_RETURN(stackb, 0);
+
+ invalid_char:
+  FREE_AND_RETURN(stackb, "invalid character in regular expression");
+
+ invalid_pattern:
+  FREE_AND_RETURN(stackb, "invalid regular expression");
+
+ unmatched_open:
+  FREE_AND_RETURN(stackb, "unmatched (");
+
+ unmatched_close:
+  FREE_AND_RETURN(stackb, "unmatched )");
+
+ end_of_pattern:
+  FREE_AND_RETURN(stackb, "premature end of regular expression");
+
+ too_big:
+  FREE_AND_RETURN(stackb, "regular expression too big");
+
+ memory_exhausted:
+  FREE_AND_RETURN(stackb, "memory exhausted");
+
+ nested_meta:
+  FREE_AND_RETURN(stackb, "nested *?+ in regexp");
+}
+
+
+/* Store a jump of the form <OPCODE> <relative address>.
+   Store in the location FROM a jump operation to jump to relative
+   address FROM - TO.  OPCODE is the opcode to store.  */
+
+static void
+store_jump(from, opcode, to)
+     char *from, *to;
+     int opcode;
+{
+  from[0] = (char)opcode;
+  STORE_NUMBER(from + 1, to - (from + 3));
+}
+
+
+/* Open up space before char FROM, and insert there a jump to TO.
+   CURRENT_END gives the end of the storage not in use, so we know 
+   how much data to copy up. OP is the opcode of the jump to insert.
+
+   If you call this function, you must zero out pending_exact.  */
+
+static void
+insert_jump(op, from, to, current_end)
+     int op;
+     char *from, *to, *current_end;
+{
+  register char *pfrom = current_end;		/* Copy from here...  */
+  register char *pto = current_end + 3;		/* ...to here.  */
+
+  while (pfrom != from)			       
+    *--pto = *--pfrom;
+  store_jump(from, op, to);
+}
+
+
+/* Store a jump of the form <opcode> <relative address> <n> .
+
+   Store in the location FROM a jump operation to jump to relative
+   address FROM - TO.  OPCODE is the opcode to store, N is a number the
+   jump uses, say, to decide how many times to jump.
+
+   If you call this function, you must zero out pending_exact.  */
+
+static void
+store_jump_n(from, opcode, to, n)
+     char *from, *to;
+     int opcode;
+     unsigned n;
+{
+  from[0] = (char)opcode;
+  STORE_NUMBER(from + 1, to - (from + 3));
+  STORE_NUMBER(from + 3, n);
+}
+
+
+/* Similar to insert_jump, but handles a jump which needs an extra
+   number to handle minimum and maximum cases.  Open up space at
+   location FROM, and insert there a jump to TO.  CURRENT_END gives the
+   end of the storage in use, so we know how much data to copy up. OP is
+   the opcode of the jump to insert.
+
+   If you call this function, you must zero out pending_exact.  */
+
+static void
+insert_jump_n(op, from, to, current_end, n)
+     int op;
+     char *from, *to, *current_end;
+     unsigned n;
+{
+  register char *pfrom = current_end;		/* Copy from here...  */
+  register char *pto = current_end + 5;		/* ...to here.  */
+
+  while (pfrom != from)			       
+    *--pto = *--pfrom;
+  store_jump_n(from, op, to, n);
+}
+
+
+/* Open up space at location THERE, and insert operation OP.
+   CURRENT_END gives the end of the storage in use, so
+   we know how much data to copy up.
+
+   If you call this function, you must zero out pending_exact.  */
+
+static void
+insert_op(op, there, current_end)
+     int op;
+     char *there, *current_end;
+{
+  register char *pfrom = current_end;		/* Copy from here...  */
+  register char *pto = current_end + 1;		/* ...to here.  */
+
+  while (pfrom != there)			       
+    *--pto = *--pfrom;
+
+  there[0] = (char)op;
+}
+
+
+/* Open up space at location THERE, and insert operation OP followed by
+   NUM_1 and NUM_2.  CURRENT_END gives the end of the storage in use, so
+   we know how much data to copy up.
+
+   If you call this function, you must zero out pending_exact.  */
+
+static void
+insert_op_2(op, there, current_end, num_1, num_2)
+     int op;
+     char *there, *current_end;
+     int num_1, num_2;
+{
+  register char *pfrom = current_end;		/* Copy from here...  */
+  register char *pto = current_end + 5;		/* ...to here.  */
+
+  while (pfrom != there)			       
+    *--pto = *--pfrom;
+
+  there[0] = (char)op;
+  STORE_NUMBER(there + 1, num_1);
+  STORE_NUMBER(there + 3, num_2);
+}
+
+
+#define trans_eq(c1, c2, translate) (translate?(translate[c1]==translate[c2]):((c1)==(c2)))
+static int
+must_match(little, lend, big, bend, translate)
+     unsigned char *little, *lend;
+     unsigned char *big, *bend;
+     unsigned char *translate;
+{
+  int c;
+
+  while (little < lend && big < bend) {
+    c = *little++;
+    if (c == 0xff) {
+      if (!trans_eq(*big++, *little++, translate)) break;
+      continue;
+    }
+    if (!trans_eq(*big++, c, translate)) break;
+  }
+  if (little == lend) return 1;
+  return 0;
+}
+
+static int
+must_instr(little, llen, big, blen, translate)
+     unsigned char *little;
+     int llen;
+     unsigned char *big;
+     int blen;
+     char *translate;
+{
+  unsigned char *bend = big + blen;
+  register int c;
+  int fescape = 0;
+
+  if (blen < llen)
+    return 0;
+
+  c = *little;
+  if (c == 0xff) {
+    c = *++little;
+    fescape = 1;
+  }
+  else if (translate && !ismbchar(c)) {
+    c = translate[c];
+  }
+
+  while (big < bend) {
+    /* look for first character */
+    if (fescape) {
+      while (big < bend) {
+	if (*big == c) break;
+	big++;
+      }
+    }
+    else if (translate && !ismbchar(c)) {
+      while (big < bend) {
+	if (ismbchar(*big)) big++;
+	else if (translate[*big] == c) break;
+	big++;
+      }
+    }
+    else {
+      while (big < bend) {
+	if (*big == c) break;
+	if (ismbchar(*big)) big++;
+	big++;
+      }
+    }
+
+    if (must_match(little, little+llen, big, bend, translate))
+      return 1;
+
+    if (ismbchar(*big)) big++;
+    big++;
+  }
+  return 0;
+}
+
+
+/* Given a pattern, compute a fastmap from it.  The fastmap records
+   which of the (1 << BYTEWIDTH) possible characters can start a string
+   that matches the pattern.  This fastmap is used by re_search to skip
+   quickly over totally implausible text.
+
+   The caller must supply the address of a (1 << BYTEWIDTH)-byte data 
+   area as bufp->fastmap.
+   The other components of bufp describe the pattern to be used.  */
+void
+re_compile_fastmap(bufp)
+     struct re_pattern_buffer *bufp;
+{
+  unsigned char *pattern = (unsigned char *) bufp->buffer;
+  int size = bufp->used;
+  register char *fastmap = bufp->fastmap;
+  register unsigned char *p = pattern;
+  register unsigned char *pend = pattern + size;
+  register int j, k;
+  unsigned char *translate = (unsigned char *)bufp->translate;
+  unsigned is_a_succeed_n;
+
+  unsigned char **stackb = RE_TALLOC(NFAILURES, unsigned char*);
+  unsigned char **stackp = stackb;
+  unsigned char **stacke = stackb + NFAILURES;
+
+  memset(fastmap, 0, (1 << BYTEWIDTH));
+  bufp->fastmap_accurate = 1;
+  bufp->can_be_null = 0;
+
+  while (p)
+    {
+      is_a_succeed_n = 0;
+      if (p == pend)
+	{
+	  bufp->can_be_null = 1;
+	  break;
+	}
+#ifdef SWITCH_ENUM_BUG
+      switch ((int) ((enum regexpcode)*p++))
+#else
+      switch ((enum regexpcode)*p++)
+#endif
+	{
+	case exactn:
+	  if (p[1] == 0xff) {
+	      if (translate)
+		fastmap[translate[p[2]]] = 2;
+	      else
+		fastmap[p[2]] = 2;
+	  }
+	  else if (translate)
+	    fastmap[translate[p[1]]] = 1;
+	  else
+	    fastmap[p[1]] = 1;
+	  break;
+
+        case begline:
+	case begbuf:
+	case endbuf:
+	case wordbound:
+	case notwordbound:
+	case wordbeg:
+	case wordend:
+	case pop_and_fail:
+	  continue;
+
+	case endline:
+	  if (translate)
+	    fastmap[translate['\n']] = 1;
+	  else
+	    fastmap['\n'] = 1;
+
+	  if (bufp->can_be_null == 0)
+	    bufp->can_be_null = 2;
+	  break;
+
+	case jump_n:
+        case finalize_jump:
+	case maybe_finalize_jump:
+	case jump:
+	case dummy_failure_jump:
+          EXTRACT_NUMBER_AND_INCR(j, p);
+	  p += j;	
+	  if (j > 0)
+	    continue;
+          /* Jump backward reached implies we just went through
+	     the body of a loop and matched nothing.
+	     Opcode jumped to should be an on_failure_jump.
+	     Just treat it like an ordinary jump.
+	     For a * loop, it has pushed its failure point already;
+	     If so, discard that as redundant.  */
+
+          if ((enum regexpcode) *p != on_failure_jump
+	      && (enum regexpcode) *p != try_next
+	      && (enum regexpcode) *p != finalize_push
+	      && (enum regexpcode) *p != finalize_push_n)
+	    continue;
+          p++;
+          EXTRACT_NUMBER_AND_INCR(j, p);
+          p += j;	
+          if (stackp != stackb && *stackp == p)
+            stackp--;		/* pop */
+          continue;
+
+        case start_nowidth:
+	case stop_nowidth:
+        case finalize_push:
+	  p += 2;
+	  continue;
+
+        case finalize_push_n:
+	  p += 4;
+	  continue;
+
+	case try_next:
+        case on_failure_jump:
+	handle_on_failure_jump:
+          EXTRACT_NUMBER_AND_INCR(j, p);
+          if (p + j < pend) {
+	    if (stackp == stacke) {
+	      unsigned char **stackx;
+	      unsigned int len = stacke - stackb;
+
+	      EXPAND_FAIL_STACK(stackx, stackb, len);
+	    }
+	    *++stackp = p + j;	/* push */
+	  }
+	  else {
+            bufp->can_be_null = 1;
+	  }
+	  if (is_a_succeed_n)
+            EXTRACT_NUMBER_AND_INCR(k, p);	/* Skip the n.  */
+	  continue;
+
+	case succeed_n:
+	  is_a_succeed_n = 1;
+          /* Get to the number of times to succeed.  */
+          EXTRACT_NUMBER(k, p + 2);
+	  /* Increment p past the n for when k != 0.  */
+          if (k == 0) {
+	    p += 4;
+	  }
+	  else {
+	    goto handle_on_failure_jump;
+	  }
+          continue;
+
+	case set_number_at:
+          p += 4;
+          continue;
+
+        case start_memory:
+	case stop_memory:
+	  p++;
+	  continue;
+
+	case duplicate:
+	  bufp->can_be_null = 1;
+	  fastmap['\n'] = 1;
+	case anychar:
+	  for (j = 0; j < (1 << BYTEWIDTH); j++)
+	    if (j != '\n')
+	      fastmap[j] = 1;
+	  if (bufp->can_be_null)
+	    {
+	      FREE_AND_RETURN_VOID(stackb);
+	    }
+	  /* Don't return; check the alternative paths
+	     so we can set can_be_null if appropriate.  */
+	  break;
+
+	case wordchar:
+	  for (j = 0; j < (1 << BYTEWIDTH); j++)
+	    if (SYNTAX(j) == Sword)
+	      fastmap[j] = 1;
+	  break;
+
+	case notwordchar:
+	  for (j = 0; j < 0x80; j++)
+	    if (SYNTAX(j) != Sword)
+	      fastmap[j] = 1;
+	  for (j = 0x80; j < (1 << BYTEWIDTH); j++)
+	      fastmap[j] = 1;
+	  break;
+
+	case charset:
+	  /* NOTE: Charset for single-byte chars never contain
+		   multi-byte char.  See set_list_bits().  */
+	  for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
+	    if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
+	      {
+		if (translate)
+		  fastmap[translate[j]] = 1;
+		else
+		  fastmap[j] = 1;
+	      }
+	  {
+	    unsigned short size;
+	    unsigned c, end;
+
+	    p += p[-1] + 2;
+	    size = EXTRACT_UNSIGNED(&p[-2]);
+	    for (j = 0; j < (int)size; j++) {
+	      if ((unsigned char)p[j*4] == 0xff) {
+		for (c = (unsigned char)p[j*4+1],
+		    end = (unsigned char)p[j*4+3];
+		     c <= end; c++) {
+		  fastmap[c] = 2;
+		}
+	      }
+	      else {
+		/* set bits for 1st bytes of multi-byte chars.  */
+		for (c = (unsigned char)p[j*4],
+		     end = (unsigned char)p[j*4 + 2];
+		     c <= end; c++) {
+		  /* NOTE: Charset for multi-byte chars might contain
+		     single-byte chars.  We must reject them. */
+		  if (ismbchar(c))
+		    fastmap[c] = 1;
+		}
+	      }
+	    }
+	  }
+	  break;
+
+	case charset_not:
+	  /* S: set of all single-byte chars.
+	     M: set of all first bytes that can start multi-byte chars.
+	     s: any set of single-byte chars.
+	     m: any set of first bytes that can start multi-byte chars.
+
+	     We assume S+M = U.
+	       ___      _   _
+	       s+m = (S*s+M*m).  */
+	  /* Chars beyond end of map must be allowed */
+	  /* NOTE: Charset_not for single-byte chars might contain
+		   multi-byte chars.  See set_list_bits(). */
+	  for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
+	    if (!ismbchar(j))
+	      fastmap[j] = 1;
+
+	  for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
+	    if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
+	      {
+		if (!ismbchar(j))
+		  fastmap[j] = 1;
+	      }
+	  {
+	    unsigned short size;
+	    unsigned char c, beg;
+
+	    p += p[-1] + 2;
+	    size = EXTRACT_UNSIGNED(&p[-2]);
+	    if (size == 0) {
+		for (j = 0x80; j < (1 << BYTEWIDTH); j++)
+		    if (ismbchar(j))
+			fastmap[j] = 1;
+	    }
+	    for (j = 0,c = 0x80;j < (int)size; j++) {
+	      if ((unsigned char)p[j*4] == 0xff) {
+	        for (beg = (unsigned char)p[j*4+1]; c < beg; c++)
+		  fastmap[c] = 2;
+	        c = (unsigned char)p[j*4+3] + 1;
+	      }
+	      else {
+	        for (beg = (unsigned char)p[j*4 + 0]; c < beg; c++)
+		  if (ismbchar(c))
+		    fastmap[c] = 1;
+	        c = (unsigned char)p[j*4 + 2] + 1;
+	      }
+	    }
+	  }
+	  break;
+
+	case unused:	/* pacify gcc -Wall */
+	  break;
+	}
+
+      /* Get here means we have successfully found the possible starting
+         characters of one path of the pattern.  We need not follow this
+         path any farther.  Instead, look at the next alternative
+         remembered in the stack.  */
+      if (stackp != stackb)
+	p = *stackp--;		/* pop */
+      else
+	break;
+    }
+   FREE_AND_RETURN_VOID(stackb);
+}
+
+
+/* Using the compiled pattern in BUFP->buffer, first tries to match
+   STRING, starting first at index STARTPOS, then at STARTPOS + 1, and
+   so on.  RANGE is the number of places to try before giving up.  If
+   RANGE is negative, it searches backwards, i.e., the starting
+   positions tried are STARTPOS, STARTPOS - 1, etc.  STRING is of SIZE.
+   In REGS, return the indices of STRING that matched the entire
+   BUFP->buffer and its contained subexpressions.
+
+   The value returned is the position in the strings at which the match
+   was found, or -1 if no match was found, or -2 if error (such as
+   failure stack overflow).  */
+
+int
+re_search(bufp, string, size, startpos, range, regs)
+     struct re_pattern_buffer *bufp;
+     char *string;
+     int size, startpos, range;
+     struct re_registers *regs;
+{
+  register char *fastmap = bufp->fastmap;
+  register unsigned char *translate = (unsigned char *) bufp->translate;
+  int val, anchor = 0;
+
+  /* Check for out-of-range starting position.  */
+  if (startpos < 0  ||  startpos > size)
+    return -1;
+
+  /* If the search isn't to be a backwards one, don't waste time in a
+     search for a pattern that must be anchored.  */
+  if (bufp->used>0) {
+    switch ((enum regexpcode)bufp->buffer[0]) {
+    case begbuf:
+      if (range > 0) {
+	if (startpos > 0)
+	  return -1;
+	else 
+	  return re_match(bufp, string, size, 0, regs);
+      }
+      break;
+
+    case begline:
+      if (startpos == 0) {
+        val = re_match(bufp, string, size, 0, regs);
+        if (val >= 0) return 0;
+      }
+      anchor = 1;
+      break;
+
+    default:
+      break;
+    }
+  }
+#if 1
+  if (range > 0
+      && bufp->must
+      && !must_instr(bufp->must+1, bufp->must[0],
+		     string+startpos, size-startpos,
+		     translate)) {
+    return -1;
+  }
+#endif
+  /* Update the fastmap now if not correct already.  */
+  if (fastmap && !bufp->fastmap_accurate) {
+      re_compile_fastmap(bufp);
+  }
+
+  for (;;)
+    {
+      /* If a fastmap is supplied, skip quickly over characters that
+         cannot possibly be the start of a match.  Note, however, that
+         if the pattern can possibly match the null string, we must
+         test it at each starting point so that we take the first null
+         string we get.  */
+
+      if (fastmap && startpos < size
+	  && bufp->can_be_null != 1 && !(anchor && startpos == 0))
+	{
+	  if (range > 0)	/* Searching forwards.  */
+	    {
+	      register unsigned char *p, c;
+	      int irange = range;
+
+	      p = (unsigned char *)string+startpos;
+
+	      while (range > 0) {
+		c = *p++;
+		if (ismbchar(c)) {
+		  if (fastmap[c])
+		    break;
+		  c = *p++;
+		  range--;
+		  if (fastmap[c] == 2)
+		    break;
+		}
+		else 
+		  if (fastmap[translate ? translate[c] : c])
+		    break;
+		range--;
+	      }
+	      startpos += irange - range;
+	    }
+	  else			/* Searching backwards.  */
+	    {
+	      register unsigned char c;
+
+	      c = string[startpos];
+              c &= 0xff;
+	      if (translate ? !fastmap[translate[c]] : !fastmap[c])
+		goto advance;
+	    }
+	}
+
+      if (anchor && startpos > 0 && startpos < size
+	  && string[startpos-1] != '\n') goto advance;
+
+      if (fastmap && startpos == size && range >= 0
+	  && (bufp->can_be_null == 0 ||
+	      (bufp->can_be_null == 2 && size > 0
+	       && string[startpos-1] == '\n')))
+	return -1;
+
+      val = re_match(bufp, string, size, startpos, regs);
+      if (val >= 0)
+	return startpos;
+      if (val == -2)
+	return -2;
+
+#ifndef NO_ALLOCA
+#ifdef cALLOCA
+      alloca(0);
+#endif /* cALLOCA */
+#endif /* NO_ALLOCA */
+
+    advance:
+      if (!range) 
+        break;
+      else if (range > 0) {
+	const char *d = string + startpos;
+
+	if (ismbchar(*d)) {
+	  range--, startpos++;
+	  if (!range)
+	    break;
+	}
+	range--, startpos++;
+      }
+      else {
+	range++, startpos--;
+	{
+	  const char *s, *d, *p;
+
+	  s = string; d = string + startpos;
+	  for (p = d; p-- > s && ismbchar(*p); )
+	    /* --p >= s would not work on 80[12]?86. 
+	      (when the offset of s equals 0 other than huge model.)  */
+	    ;
+	  if (!((d - p) & 1)) {
+	    if (!range)
+	      break;
+	    range++, startpos--;
+	  }
+	}
+      }
+    }
+  return -1;
+}
+
+
+
+
+/* The following are used for re_match, defined below:  */
+
+/* Roughly the maximum number of failure points on the stack.  Would be
+   exactly that if always pushed MAX_NUM_FAILURE_ITEMS each time we failed.  */
+
+int re_max_failures = 2000;
+
+/* Routine used by re_match.  */
+/* static int memcmp_translate(); *//* already declared */
+
+
+/* Structure and accessing macros used in re_match:  */
+
+struct register_info
+{
+  unsigned is_active : 1;
+  unsigned matched_something : 1;
+};
+
+#define IS_ACTIVE(R)  ((R).is_active)
+#define MATCHED_SOMETHING(R)  ((R).matched_something)
+
+
+/* Macros used by re_match:  */
+
+/* I.e., regstart, regend, and reg_info.  */
+
+#define NUM_REG_ITEMS  3
+
+/* We push at most this many things on the stack whenever we
+   fail.  The `+ 2' refers to PATTERN_PLACE and STRING_PLACE, which are
+   arguments to the PUSH_FAILURE_POINT macro.  */
+
+#define MAX_NUM_FAILURE_ITEMS   (num_regs * NUM_REG_ITEMS + 2)
+
+
+/* We push this many things on the stack whenever we fail.  */
+
+#define NUM_FAILURE_ITEMS  (last_used_reg * NUM_REG_ITEMS + 2)
+
+
+/* This pushes most of the information about the current state we will want
+   if we ever fail back to it.  */
+
+#define PUSH_FAILURE_POINT(pattern_place, string_place)			\
+  {									\
+    long last_used_reg, this_reg;					\
+									\
+    /* Find out how many registers are active or have been matched.	\
+       (Aside from register zero, which is only set at the end.) */	\
+    for (last_used_reg = num_regs - 1; last_used_reg > 0; last_used_reg--)\
+      if (regstart[last_used_reg] != (unsigned char *)(-1L))		\
+        break;								\
+									\
+    if (stacke - stackp <= NUM_FAILURE_ITEMS)				\
+      {									\
+	unsigned char **stackx;						\
+	unsigned int len = stacke - stackb;				\
+	if (len > re_max_failures * MAX_NUM_FAILURE_ITEMS)		\
+	  {								\
+	    FREE_VARIABLES();						\
+	    FREE_AND_RETURN(stackb,(-2));				\
+	  }								\
+									\
+        /* Roughly double the size of the stack.  */			\
+        EXPAND_FAIL_STACK(stackx, stackb, len);				\
+      }									\
+									\
+    /* Now push the info for each of those registers.  */		\
+    for (this_reg = 1; this_reg <= last_used_reg; this_reg++)		\
+      {									\
+        *stackp++ = regstart[this_reg];					\
+        *stackp++ = regend[this_reg];					\
+        *stackp++ = (unsigned char *)&reg_info[this_reg];		\
+      }									\
+									\
+    /* Push how many registers we saved.  */				\
+    *stackp++ = (unsigned char *)last_used_reg;				\
+									\
+    *stackp++ = pattern_place;                                          \
+    *stackp++ = string_place;                                           \
+    *stackp++ = (unsigned char *)0; /* non-greedy flag */		\
+  }
+
+
+/* This pops what PUSH_FAILURE_POINT pushes.  */
+
+#define POP_FAILURE_POINT()						\
+  {									\
+    int temp;								\
+    stackp -= 3;		/* Remove failure points (and flag). */	\
+    temp = (int) *--stackp;	/* How many regs pushed.  */	        \
+    temp *= NUM_REG_ITEMS;	/* How much to take off the stack.  */	\
+    stackp -= temp; 		/* Remove the register info.  */	\
+  }
+
+#define PREFETCH if (d == dend) goto fail
+
+/* Call this when have matched something; it sets `matched' flags for the
+   registers corresponding to the subexpressions of which we currently
+   are inside.  */
+#define SET_REGS_MATCHED 						\
+  { unsigned this_reg;							\
+    for (this_reg = 0; this_reg < num_regs; this_reg++) 		\
+      { 								\
+        if (IS_ACTIVE(reg_info[this_reg]))				\
+          MATCHED_SOMETHING(reg_info[this_reg]) = 1;			\
+        else								\
+          MATCHED_SOMETHING(reg_info[this_reg]) = 0;			\
+      } 								\
+  }
+
+#define AT_STRINGS_BEG(d)  (d == string)
+#define AT_STRINGS_END(d)  (d == dend)	
+
+#define AT_WORD_BOUNDARY(d)						\
+  (AT_STRINGS_BEG(d) || AT_STRINGS_END(d) || IS_A_LETTER(d - 1) != IS_A_LETTER(d))
+
+/* We have two special cases to check for: 
+     1) if we're past the end of string1, we have to look at the first
+        character in string2;
+     2) if we're before the beginning of string2, we have to look at the
+        last character in string1; we assume there is a string1, so use
+        this in conjunction with AT_STRINGS_BEG.  */
+#define IS_A_LETTER(d) (SYNTAX(*(d)) == Sword)
+
+static void
+init_regs(regs, num_regs)
+    struct re_registers *regs;
+    unsigned num_regs;
+{
+    int i;
+
+    regs->num_regs = num_regs;
+    if (num_regs < RE_NREGS)
+	num_regs = RE_NREGS;
+
+    if (regs->allocated == 0) {
+	regs->beg = TMALLOC(num_regs, int);
+	regs->end = TMALLOC(num_regs, int);
+	regs->allocated = num_regs;
+    }
+    else if (regs->allocated < num_regs) {
+	TREALLOC(regs->beg, num_regs, int);
+	TREALLOC(regs->end, num_regs, int);
+    }
+    for (i=0; i<num_regs; i++) {
+	regs->beg[i] = regs->end[i] = -1;
+    }
+}
+
+/* Match the pattern described by BUFP against STRING, which is of
+   SIZE.  Start the match at index POS in STRING.  In REGS, return the
+   indices of STRING that matched the entire BUFP->buffer and its
+   contained subexpressions.
+
+   If bufp->fastmap is nonzero, then it had better be up to date.
+
+   The reason that the data to match are specified as two components
+   which are to be regarded as concatenated is so this function can be
+   used directly on the contents of an Emacs buffer.
+
+   -1 is returned if there is no match.  -2 is returned if there is an
+   error (such as match stack overflow).  Otherwise the value is the
+   length of the substring which was matched.  */
+
+int
+re_match(bufp, string_arg, size, pos, regs)
+     struct re_pattern_buffer *bufp;
+     char *string_arg;
+     int size, pos;
+     struct re_registers *regs;
+{
+  register unsigned char *p = (unsigned char *) bufp->buffer;
+
+  /* Pointer to beyond end of buffer.  */
+  register unsigned char *pend = p + bufp->used;
+
+  unsigned num_regs = bufp->re_nsub;
+
+  unsigned char *string = (unsigned char *) string_arg;
+
+  register unsigned char *d, *dend;
+  register int mcnt;			/* Multipurpose.  */
+  unsigned char *translate = (unsigned char *) bufp->translate;
+  unsigned is_a_jump_n = 0;
+
+ /* Failure point stack.  Each place that can handle a failure further
+    down the line pushes a failure point on this stack.  It consists of
+    restart, regend, and reg_info for all registers corresponding to the
+    subexpressions we're currently inside, plus the number of such
+    registers, and, finally, two char *'s.  The first char * is where to
+    resume scanning the pattern; the second one is where to resume
+    scanning the strings.  If the latter is zero, the failure point is a
+    ``dummy''; if a failure happens and the failure point is a dummy, it
+    gets discarded and the next next one is tried.  */
+
+  unsigned char **stackb;
+  unsigned char **stackp;
+  unsigned char **stacke;
+
+
+  /* Information on the contents of registers. These are pointers into
+     the input strings; they record just what was matched (on this
+     attempt) by a subexpression part of the pattern, that is, the
+     regnum-th regstart pointer points to where in the pattern we began
+     matching and the regnum-th regend points to right after where we
+     stopped matching the regnum-th subexpression.  (The zeroth register
+     keeps track of what the whole pattern matches.)  */
+
+  unsigned char **regstart = RE_TALLOC(num_regs, unsigned char*);
+  unsigned char **regend = RE_TALLOC(num_regs, unsigned char*);
+
+  /* The is_active field of reg_info helps us keep track of which (possibly
+     nested) subexpressions we are currently in. The matched_something
+     field of reg_info[reg_num] helps us tell whether or not we have
+     matched any of the pattern so far this time through the reg_num-th
+     subexpression.  These two fields get reset each time through any
+     loop their register is in.  */
+
+  struct register_info *reg_info = RE_TALLOC(num_regs, struct register_info);
+
+  /* The following record the register info as found in the above
+     variables when we find a match better than any we've seen before. 
+     This happens as we backtrack through the failure points, which in
+     turn happens only if we have not yet matched the entire string.  */
+
+  unsigned best_regs_set = 0;
+  unsigned char **best_regstart = RE_TALLOC(num_regs, unsigned char*);
+  unsigned char **best_regend = RE_TALLOC(num_regs, unsigned char*);
+
+  if (regs) {
+    init_regs(regs, num_regs);
+  }
+
+  /* Initialize the stack. */
+  stackb = RE_TALLOC(MAX_NUM_FAILURE_ITEMS * NFAILURES, unsigned char*);
+  stackp = stackb;
+  stacke = &stackb[MAX_NUM_FAILURE_ITEMS * NFAILURES];
+
+#ifdef DEBUG_REGEX
+  fprintf (stderr, "Entering re_match(%s%s)\n", string1_arg, string2_arg);
+#endif
+
+  /* Initialize subexpression text positions to -1 to mark ones that no
+     \( or ( and \) or ) has been seen for. Also set all registers to
+     inactive and mark them as not having matched anything or ever
+     failed. */
+  for (mcnt = 0; mcnt < num_regs; mcnt++) {
+      regstart[mcnt] = regend[mcnt] = (unsigned char *) (-1L);
+      IS_ACTIVE(reg_info[mcnt]) = 0;
+      MATCHED_SOMETHING(reg_info[mcnt]) = 0;
+  }
+
+  /* Set up pointers to ends of strings.
+     Don't allow the second string to be empty unless both are empty.  */
+
+
+  /* `p' scans through the pattern as `d' scans through the data. `dend'
+     is the end of the input string that `d' points within. `d' is
+     advanced into the following input string whenever necessary, but
+     this happens before fetching; therefore, at the beginning of the
+     loop, `d' can be pointing at the end of a string, but it cannot
+     equal string2.  */
+
+  d = string + pos, dend = string + size;
+
+
+  /* This loops over pattern commands.  It exits by returning from the
+     function if match is complete, or it drops through if match fails
+     at this starting point in the input data.  */
+
+  for (;;)
+    {
+#ifdef DEBUG_REGEX
+      fprintf(stderr,
+	      "regex loop(%d):  matching 0x%02d\n",
+	      p - (unsigned char *) bufp->buffer,
+	      *p);
+#endif
+      is_a_jump_n = 0;
+      /* End of pattern means we might have succeeded.  */
+      if (p == pend)
+	{
+	  /* If not end of string, try backtracking.  Otherwise done.  */
+          if (d != dend)
+	    {
+              if (stackp != stackb)
+                {
+                  /* More failure points to try.  */
+
+                  /* If exceeds best match so far, save it.  */
+                  if (! best_regs_set || (d > best_regend[0]))
+                    {
+                      best_regs_set = 1;
+                      best_regend[0] = d;	/* Never use regstart[0].  */
+
+                      for (mcnt = 1; mcnt < num_regs; mcnt++)
+                        {
+                          best_regstart[mcnt] = regstart[mcnt];
+                          best_regend[mcnt] = regend[mcnt];
+                        }
+                    }
+                  goto fail;	       
+                }
+              /* If no failure points, don't restore garbage.  */
+              else if (best_regs_set)   
+                {
+	      restore_best_regs:
+                  /* Restore best match.  */
+                  d = best_regend[0];
+
+		  for (mcnt = 0; mcnt < num_regs; mcnt++)
+		    {
+		      regstart[mcnt] = best_regstart[mcnt];
+		      regend[mcnt] = best_regend[mcnt];
+		    }
+                }
+            }
+
+	  /* If caller wants register contents data back, convert it 
+	     to indices.  */
+	  if (regs)
+	    {
+	      regs->beg[0] = pos;
+	      regs->end[0] = d - string;
+	      for (mcnt = 1; mcnt < num_regs; mcnt++)
+		{
+		  if (regend[mcnt] == (unsigned char *)(-1L))
+		    {
+		      regs->beg[mcnt] = -1;
+		      regs->end[mcnt] = -1;
+		      continue;
+		    }
+		  regs->beg[mcnt] = regstart[mcnt] - string;
+		  regs->end[mcnt] = regend[mcnt] - string;
+		}
+	    }
+	  FREE_VARIABLES();
+	  FREE_AND_RETURN(stackb, (d - pos - string));
+        }
+
+      /* Otherwise match next pattern command.  */
+#ifdef SWITCH_ENUM_BUG
+      switch ((int)((enum regexpcode)*p++))
+#else
+      switch ((enum regexpcode)*p++)
+#endif
+	{
+
+	/* \( [or `(', as appropriate] is represented by start_memory,
+           \) by stop_memory.  Both of those commands are followed by
+           a register number in the next byte.  The text matched
+           within the \( and \) is recorded under that number.  */
+	case start_memory:
+          regstart[*p] = d;
+          IS_ACTIVE(reg_info[*p]) = 1;
+          MATCHED_SOMETHING(reg_info[*p]) = 0;
+          p++;
+	  continue;
+
+	case stop_memory:
+          regend[*p] = d;
+          IS_ACTIVE(reg_info[*p]) = 0;
+
+          /* If just failed to match something this time around with a sub-
+	     expression that's in a loop, try to force exit from the loop.  */
+          if ((! MATCHED_SOMETHING(reg_info[*p])
+	       || (enum regexpcode) p[-3] == start_memory)
+	      && (p + 1) != pend)              
+            {
+	      register unsigned char *p2 = p + 1;
+              mcnt = 0;
+              switch (*p2++)
+                {
+                  case jump_n:
+		    is_a_jump_n = 1;
+                  case finalize_jump:
+		  case maybe_finalize_jump:
+		  case jump:
+		  case dummy_failure_jump:
+                    EXTRACT_NUMBER_AND_INCR(mcnt, p2);
+		    if (is_a_jump_n)
+		      p2 += 2;
+                    break;
+                }
+	      p2 += mcnt;
+
+              /* If the next operation is a jump backwards in the pattern
+	         to an on_failure_jump, exit from the loop by forcing a
+                 failure after pushing on the stack the on_failure_jump's 
+                 jump in the pattern, and d.  */
+	      if (mcnt < 0 && (enum regexpcode) *p2++ == on_failure_jump)
+		{
+                  EXTRACT_NUMBER_AND_INCR(mcnt, p2);
+                  PUSH_FAILURE_POINT(p2 + mcnt, d);
+                  goto fail;
+                }
+            }
+          p++;
+	  continue;
+
+	/* \<digit> has been turned into a `duplicate' command which is
+           followed by the numeric value of <digit> as the register number.  */
+        case duplicate:
+	  {
+	    int regno = *p++;   /* Get which register to match against */
+	    register unsigned char *d2, *dend2;
+
+	    /* Where in input to try to start matching.  */
+            d2 = regstart[regno];
+
+            /* Where to stop matching; if both the place to start and
+               the place to stop matching are in the same string, then
+               set to the place to stop, otherwise, for now have to use
+               the end of the first string.  */
+
+            dend2 = regend[regno];
+	    for (;;)
+	      {
+		/* At end of register contents => success */
+		if (d2 == dend2) break;
+
+		/* If necessary, advance to next segment in data.  */
+		PREFETCH;
+
+		/* How many characters left in this segment to match.  */
+		mcnt = dend - d;
+
+		/* Want how many consecutive characters we can match in
+                   one shot, so, if necessary, adjust the count.  */
+                if (mcnt > dend2 - d2)
+		  mcnt = dend2 - d2;
+
+		/* Compare that many; failure if mismatch, else move
+                   past them.  */
+		if (translate 
+                    ? memcmp_translate(d, d2, mcnt, translate) 
+                    : memcmp((char *)d, (char *)d2, mcnt))
+		  goto fail;
+		d += mcnt, d2 += mcnt;
+	      }
+	  }
+	  break;
+
+	case start_nowidth:
+          PUSH_FAILURE_POINT(0, d);
+	  EXTRACT_NUMBER_AND_INCR(mcnt, p);
+	  STORE_NUMBER(p+mcnt, stackp - stackb);
+	  continue;
+
+	case stop_nowidth:
+	  EXTRACT_NUMBER_AND_INCR(mcnt, p);
+	  stackp = stackb + mcnt;
+	  d = stackp[-2];
+	  POP_FAILURE_POINT();
+	  continue;
+
+	case pop_and_fail:
+	  EXTRACT_NUMBER(mcnt, p+1);
+	  stackp = stackb + mcnt;
+	  POP_FAILURE_POINT();
+	  goto fail;
+
+	case anychar:
+	  PREFETCH;
+	  /* Match anything but a newline, maybe even a null.  */
+	  if (ismbchar(*d)) {
+	    if (d + 1 == dend || d[1] == '\n' || d[1] == '\0')
+	      goto fail;
+	    SET_REGS_MATCHED;
+	    d += 2;
+	    break;
+	  }
+	  if ((translate ? translate[*d] : *d) == '\n'
+              || ((re_syntax_options & RE_DOT_NOT_NULL) 
+                  && (translate ? translate[*d] : *d) == '\000'))
+	    goto fail;
+	  SET_REGS_MATCHED;
+          d++;
+	  break;
+
+	case charset:
+	case charset_not:
+	  {
+	    int not;	    /* Nonzero for charset_not.  */
+	    int half;	    /* 2 if need to match latter half of mbc */
+	    int c;
+
+	    PREFETCH;
+	    c = (unsigned char)*d;
+	    if (ismbchar(c)) {
+	      if (d + 1 != dend) {
+	        c <<= 8;
+		c |= (unsigned char)d[1];
+	      }
+	    }
+	    else if (translate)
+	      c = (unsigned char)translate[c];
+
+	    half = not = is_in_list(c, p);
+	    if (*(p - 1) == (unsigned char)charset_not) {
+		not = !not;
+	    }
+
+	    p += 1 + *p + 2 + EXTRACT_UNSIGNED(&p[1 + *p])*4;
+
+	    if (!not) goto fail;
+	    SET_REGS_MATCHED;
+
+            d++;
+	    if (half != 2 && d != dend && c >= 1 << BYTEWIDTH)
+		d++;
+	    break;
+	  }
+
+	case begline:
+          if (size == 0
+	      || d == string
+              || (d && d[-1] == '\n'))
+            break;
+          else
+            goto fail;
+
+	case endline:
+	  if (d == dend || *d == '\n')
+	    break;
+	  goto fail;
+
+	/* Match at the very beginning of the string.  */
+	case begbuf:
+          if (AT_STRINGS_BEG(d))
+            break;
+          goto fail;
+
+	/* Match at the very end of the data.  */
+        case endbuf:
+	  if (AT_STRINGS_END(d))
+	    break;
+          goto fail;
+
+	/* `or' constructs are handled by starting each alternative with
+           an on_failure_jump that points to the start of the next
+           alternative.  Each alternative except the last ends with a
+           jump to the joining point.  (Actually, each jump except for
+           the last one really jumps to the following jump, because
+           tensioning the jumps is a hassle.)  */
+
+	/* The start of a stupid repeat has an on_failure_jump that points
+	   past the end of the repeat text. This makes a failure point so 
+           that on failure to match a repetition, matching restarts past
+           as many repetitions have been found with no way to fail and
+           look for another one.  */
+
+	/* A smart repeat is similar but loops back to the on_failure_jump
+	   so that each repetition makes another failure point.  */
+
+	case on_failure_jump:
+        on_failure:
+          EXTRACT_NUMBER_AND_INCR(mcnt, p);
+          PUSH_FAILURE_POINT(p + mcnt, d);
+          continue;
+
+	/* The end of a smart repeat has a maybe_finalize_jump back.
+	   Change it either to a finalize_jump or an ordinary jump.  */
+	case maybe_finalize_jump:
+          EXTRACT_NUMBER_AND_INCR(mcnt, p);
+	  {
+	    register unsigned char *p2 = p;
+	    /* Compare what follows with the beginning of the repeat.
+	       If we can establish that there is nothing that they would
+	       both match, we can change to finalize_jump.  */
+	    while (p2 + 1 != pend
+		   && (*p2 == (unsigned char)stop_memory
+		       || *p2 == (unsigned char)start_memory))
+	      p2 += 2;				/* Skip over reg number.  */
+	    if (p2 == pend)
+	      p[-3] = (unsigned char)finalize_jump;
+	    else if (*p2 == (unsigned char)exactn
+		     || *p2 == (unsigned char)endline)
+	      {
+		register int c = *p2 == (unsigned char)endline ? '\n' : p2[2];
+		register unsigned char *p1 = p + mcnt;
+		/* p1[0] ... p1[2] are an on_failure_jump.
+		   Examine what follows that.  */
+		if (p1[3] == (unsigned char)exactn && p1[5] != c)
+		  p[-3] = (unsigned char)finalize_jump;
+		else if (p1[3] == (unsigned char)charset
+			 || p1[3] == (unsigned char)charset_not) {
+		    int not;
+		    if (ismbchar(c))
+		      c = c << 8 | p2[3];
+		    /* `is_in_list()' is TRUE if c would match */
+		    /* That means it is not safe to finalize.  */
+		    not = is_in_list(c, p1 + 4);
+		    if (p1[3] == (unsigned char)charset_not)
+			not = !not;
+		    if (!not)
+			p[-3] = (unsigned char)finalize_jump;
+		  }
+	      }
+	  }
+	  p -= 2;		/* Point at relative address again.  */
+	  if (p[-1] != (unsigned char)finalize_jump)
+	    {
+	      p[-1] = (unsigned char)jump;	
+	      goto nofinalize;
+	    }
+        /* Note fall through.  */
+
+	/* The end of a stupid repeat has a finalize_jump back to the
+           start, where another failure point will be made which will
+           point to after all the repetitions found so far.  */
+
+        /* Take off failure points put on by matching on_failure_jump 
+           because didn't fail.  Also remove the register information
+           put on by the on_failure_jump.  */
+        case finalize_jump:
+          POP_FAILURE_POINT();
+        /* Note fall through.  */
+
+	/* Jump without taking off any failure points.  */
+        case jump:
+	nofinalize:
+	  EXTRACT_NUMBER_AND_INCR(mcnt, p);
+	  p += mcnt;
+	  continue;
+
+        case dummy_failure_jump:
+          /* Normally, the on_failure_jump pushes a failure point, which
+             then gets popped at finalize_jump.  We will end up at
+             finalize_jump, also, and with a pattern of, say, `a+', we
+             are skipping over the on_failure_jump, so we have to push
+             something meaningless for finalize_jump to pop.  */
+          PUSH_FAILURE_POINT(0, 0);
+          goto nofinalize;
+
+        /* Have to succeed matching what follows at least n times.  Then
+          just handle like an on_failure_jump.  */
+        case succeed_n: 
+          EXTRACT_NUMBER(mcnt, p + 2);
+          /* Originally, this is how many times we HAVE to succeed.  */
+          if (mcnt > 0)
+            {
+               mcnt--;
+	       p += 2;
+               STORE_NUMBER_AND_INCR(p, mcnt);
+	       PUSH_FAILURE_POINT(0, 0);
+            }
+	  else if (mcnt == 0)
+            {
+	      p[2] = unused;
+              p[3] = unused;
+              goto on_failure;
+            }
+	  continue;
+
+        case jump_n:
+          EXTRACT_NUMBER(mcnt, p + 2);
+          /* Originally, this is how many times we CAN jump.  */
+          if (mcnt)
+            {
+               mcnt--;
+               STORE_NUMBER(p + 2, mcnt);
+	       goto nofinalize;	     /* Do the jump without taking off
+			                any failure points.  */
+            }
+          /* If don't have to jump any more, skip over the rest of command.  */
+	  else      
+	    p += 4;		     
+	  continue;
+
+	case set_number_at:
+	  {
+  	    register unsigned char *p1;
+
+            EXTRACT_NUMBER_AND_INCR(mcnt, p);
+            p1 = p + mcnt;
+            EXTRACT_NUMBER_AND_INCR(mcnt, p);
+	    STORE_NUMBER(p1, mcnt);
+            continue;
+          }
+
+	case try_next:
+	  EXTRACT_NUMBER_AND_INCR(mcnt, p);
+	  if (p + mcnt < pend) {
+	    PUSH_FAILURE_POINT(p, d);
+	    stackp[-1] = (unsigned char*)1;
+	  }
+	  p += mcnt;
+	  continue;
+
+	case finalize_push:
+          POP_FAILURE_POINT();
+	  EXTRACT_NUMBER_AND_INCR(mcnt, p);
+          PUSH_FAILURE_POINT(p + mcnt, d);
+	  stackp[-1] = (unsigned char*)1;
+	  continue;
+
+	case finalize_push_n:
+          EXTRACT_NUMBER(mcnt, p + 2);
+          /* Originally, this is how many times we CAN jump.  */
+          if (mcnt) {
+	    mcnt--;
+	    STORE_NUMBER(p + 2, mcnt);
+	    POP_FAILURE_POINT();
+	    EXTRACT_NUMBER_AND_INCR(mcnt, p);
+	    PUSH_FAILURE_POINT(p + mcnt, d);
+	    stackp[-1] = (unsigned char*)1;
+	    p += 7;		/* skip n and set_number_at after destination */
+	  }
+          /* If don't have to push any more, skip over the rest of command.  */
+	  else 
+	    p += 4;   
+	  continue;
+
+        /* Ignore these.  Used to ignore the n of succeed_n's which
+           currently have n == 0.  */
+        case unused:
+	  continue;
+
+        case wordbound:
+	  if (AT_WORD_BOUNDARY(d))
+	    break;
+	  goto fail;
+
+	case notwordbound:
+	  if (AT_WORD_BOUNDARY(d))
+	    goto fail;
+	  break;
+
+	case wordbeg:
+	  if (IS_A_LETTER(d) && (AT_STRINGS_BEG(d) || !IS_A_LETTER(d - 1)))
+	    break;
+          goto fail;
+
+	case wordend:
+	  if (!AT_STRINGS_BEG(d) && IS_A_LETTER(d - 1)
+              && (!IS_A_LETTER(d) || AT_STRINGS_END(d)))
+	    break;
+          goto fail;
+
+	case wordchar:
+	  PREFETCH;
+          if (!IS_A_LETTER(d))
+            goto fail;
+	  d++;
+	  SET_REGS_MATCHED;
+	  break;
+
+	case notwordchar:
+	  PREFETCH;
+	  if (IS_A_LETTER(d))
+            goto fail;
+	  if (ismbchar(*d) && d + 1 != dend)
+	    d++;
+	  d++;
+          SET_REGS_MATCHED;
+	  break;
+
+	case exactn:
+	  /* Match the next few pattern characters exactly.
+	     mcnt is how many characters to match.  */
+	  mcnt = *p++;
+	  /* This is written out as an if-else so we don't waste time
+             testing `translate' inside the loop.  */
+          if (translate)
+	    {
+	      do
+		{
+		  unsigned char c;
+
+		  PREFETCH;
+		  c = *d++;
+		  if (*p == 0xff) {
+		    p++;  
+		    if (!--mcnt
+			|| d == dend
+			|| (unsigned char)*d++ != (unsigned char)*p++)
+		      goto fail;
+		    continue;
+		  }
+		  if (ismbchar(c)) {
+		    if (c != (unsigned char)*p++
+			|| !--mcnt	/* redundant check if pattern was
+					   compiled properly. */
+			|| d == dend
+			|| (unsigned char)*d++ != (unsigned char)*p++)
+		      goto fail;
+		    continue;
+		  }
+		  /* compiled code translation needed for ruby */
+		  if ((unsigned char)translate[c]
+		      != (unsigned char)translate[*p++])
+		    goto fail;
+		}
+	      while (--mcnt);
+	    }
+	  else
+	    {
+	      do
+		{
+		  PREFETCH;
+		  if (*p == 0xff) {p++; mcnt--;}
+		  if (*d++ != *p++) goto fail;
+		}
+	      while (--mcnt);
+	    }
+	  SET_REGS_MATCHED;
+          break;
+	}
+      if (stackp != stackb && (int)stackp[-1] == 1)
+	  POP_FAILURE_POINT();
+      continue;  /* Successfully executed one pattern command; keep going.  */
+
+    /* Jump here if any matching operation fails. */
+    fail:
+      if (stackp != stackb)
+	/* A restart point is known.  Restart there and pop it. */
+	{
+          short last_used_reg, this_reg;
+
+          /* If this failure point is from a dummy_failure_point, just
+             skip it.  */
+	  if (stackp[-3] == 0) {
+	    POP_FAILURE_POINT();
+	    goto fail;
+	  }
+	  stackp--;		/* discard flag */
+          d = *--stackp;
+	  p = *--stackp;
+          /* Restore register info.  */
+          last_used_reg = (long) *--stackp;
+
+          /* Make the ones that weren't saved -1 or 0 again. */
+          for (this_reg = num_regs - 1; this_reg > last_used_reg; this_reg--)
+            {
+              regend[this_reg] = (unsigned char *)(-1L);
+              regstart[this_reg] = (unsigned char *)(-1L);
+              IS_ACTIVE(reg_info[this_reg]) = 0;
+              MATCHED_SOMETHING(reg_info[this_reg]) = 0;
+            }
+
+          /* And restore the rest from the stack.  */
+          for ( ; this_reg > 0; this_reg--)
+            {
+              reg_info[this_reg] = *(struct register_info *) *--stackp;
+              regend[this_reg] = *--stackp;
+              regstart[this_reg] = *--stackp;
+            }
+	}
+      else
+        break;   /* Matching at this starting point really fails.  */
+    }
+
+  if (best_regs_set)
+    goto restore_best_regs;
+
+  FREE_AND_RETURN(stackb,(-1)); 	/* Failure to match.  */
+}
+
+
+static int
+memcmp_translate(s1, s2, len, translate)
+     unsigned char *s1, *s2;
+     register int len;
+     unsigned char *translate;
+{
+  register unsigned char *p1 = s1, *p2 = s2, c;
+  while (len)
+    {
+      c = *p1++;
+      if (ismbchar(c)) {
+	if (c != *p2++ || !--len || *p1++ != *p2++)
+	  return 1;
+      }
+      else
+	if (translate[c] != translate[*p2++])
+	  return 1;
+      len--;
+    }
+  return 0;
+}
+
+void
+re_copy_registers(regs1, regs2)
+     struct re_registers *regs1, *regs2;
+{
+    int i;
+
+    if (regs1 == regs2) return;
+    if (regs1->allocated == 0) {
+	regs1->beg = TMALLOC(regs2->num_regs, int);
+	regs1->end = TMALLOC(regs2->num_regs, int);
+	regs1->allocated = regs2->num_regs;
+    }
+    else if (regs1->allocated < regs2->num_regs) {
+	TREALLOC(regs1->beg, regs2->num_regs, int);
+	TREALLOC(regs1->end, regs2->num_regs, int);
+	regs1->allocated = regs2->num_regs;
+    }
+    for (i=0; i<regs2->num_regs; i++) {
+	regs1->beg[i] = regs2->beg[i];
+	regs1->end[i] = regs2->end[i];
+    }
+    regs1->num_regs = regs2->num_regs;
+}
+
+void
+re_free_registers(regs)
+     struct re_registers *regs;
+{
+    if (regs->allocated == 0) return;
+    if (regs->beg) free(regs->beg);
+    if (regs->end) free(regs->end);
+}
diff --git a/sample/io.rb b/sample/io.rb
deleted file mode 100644
index 0b38d2112d..0000000000
--- a/sample/io.rb
+++ /dev/null
@@ -1,44 +0,0 @@
-# IO test
-# usage: ruby io.rb file..
-
-home = ENV["HOME"]
-home.sub("m", "&&")
-print(home, "\n")
-print(home.reverse, "\n")
-
-if File.s("io.rb")
-  print(File.s("io.rb"), ": io.rb\n")
-end
-
-$/="f\n"
-for i in "abc\n\ndef\nghi\n"
-  print("tt: ", i)
-end
-
-printf("%s:(%d)%s\n", $0, ARGV.length, ARGV[0])
-passwd = open(ARGV[0], "r")
-#printf("%s", passwd.find{i|i =~ /\*/})
-
-n = 1
-for i in passwd #.grep(/^\*/)
-  printf("%6d: %s", n, i)
-  n = n + 1;
-end
-
-fp = open("|-", "r")
-
-if fp == nil
-  for i in 1..5
-    print(i, "\n")
-  end
-else
-  for line in fp
-    print(line)
-  end
-end
-
-def printUsage()
-  if $USAGE
-    apply($USAGE);
-  end
-end
diff --git a/st.c b/st.c
new file mode 100644
index 0000000000..6b25bc854b
--- /dev/null
+++ b/st.c
@@ -0,0 +1,435 @@
+/* This is a general purpose hash table package written by Peter Moore @ UCB. */
+
+static	char	sccsid[] = "@(#) st.c 5.1 89/12/14 Crucible";
+
+#include "config.h"
+#include <stdio.h>
+#include "st.h"
+
+#define ST_DEFAULT_MAX_DENSITY 5
+#define ST_DEFAULT_INIT_TABLE_SIZE 11
+
+    /*
+     * DEFAULT_MAX_DENSITY is the default for the largest we allow the
+     * average number of items per bin before increasing the number of
+     * bins
+     *
+     * DEFAULT_INIT_TABLE_SIZE is the default for the number of bins
+     * allocated initially
+     *
+     */
+static int numcmp();
+static int numhash();
+static struct st_hash_type type_numhash = {
+    numcmp,
+    numhash,
+};
+
+extern int strcmp();
+static int strhash();
+static struct st_hash_type type_strhash = {
+    strcmp,
+    strhash,
+};
+
+void *xmalloc();
+void *xcalloc();
+void *xrealloc();
+static void rehash();
+
+#define max(a,b) ((a) > (b) ? (a) : (b))
+#define nil(type) ((type*)0)
+#define alloc(type) (type*)xmalloc((unsigned)sizeof(type))
+#define Calloc(n,s) (char*)xcalloc((n),(s))
+
+#define EQUAL(table, x, y) ((*table->type->compare)(x, y) == 0)
+
+#define do_hash(key, table) (*(table)->type->hash)((key), (table)->num_bins)
+
+st_table*
+st_init_table_with_size(type, size)
+    struct st_hash_type *type;
+    int size;
+{
+    st_table *tbl;
+
+    if (size == 0) size = ST_DEFAULT_INIT_TABLE_SIZE;
+    else size /= ST_DEFAULT_MAX_DENSITY*0.87;
+
+    if (size < ST_DEFAULT_INIT_TABLE_SIZE)
+	size = ST_DEFAULT_INIT_TABLE_SIZE;
+
+    tbl = alloc(st_table);
+    tbl->type = type;
+    tbl->num_entries = 0;
+    tbl->num_bins = size;
+    tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
+    return tbl;
+}
+
+st_table*
+st_init_table(type)
+    struct st_hash_type *type;
+{
+    return st_init_table_with_size(type, 0);
+}
+
+st_table*
+st_init_numtable()
+{
+    return st_init_table(&type_numhash);
+}
+
+st_table*
+st_init_strtable()
+{
+    return st_init_table(&type_strhash);
+}
+
+void
+st_free_table(table)
+    st_table *table;
+{
+    register st_table_entry *ptr, *next;
+    int i;
+
+    for(i = 0; i < table->num_bins ; i++) {
+	ptr = table->bins[i];
+	while (ptr != nil(st_table_entry)) {
+	    next = ptr->next;
+	    free((char*)ptr);
+	    ptr = next;
+	}
+    }
+    free((char*)table->bins);
+    free((char*)table);
+}
+
+#define PTR_NOT_EQUAL(table, ptr, key) \
+(ptr != nil(st_table_entry) && !EQUAL(table, key, (ptr)->key))
+
+#define FIND_ENTRY(table, ptr, hash_val) \
+ptr = (table)->bins[hash_val];\
+if (PTR_NOT_EQUAL(table, ptr, key)) {\
+    while (PTR_NOT_EQUAL(table, ptr->next, key)) {\
+	ptr = ptr->next;\
+    }\
+    ptr = ptr->next;\
+}
+
+int
+st_lookup(table, key, value)
+    st_table *table;
+    register char *key;
+    char **value;
+{
+    int hash_val;
+    register st_table_entry *ptr;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, ptr, hash_val);
+
+    if (ptr == nil(st_table_entry)) {
+	return 0;
+    } else {
+	if (value != nil(char*))  *value = ptr->record;
+	return 1;
+    }
+}
+
+#define ADD_DIRECT(table, key, value, hash_val, tbl)\
+{\
+    if (table->num_entries/table->num_bins > ST_DEFAULT_MAX_DENSITY) {\
+	rehash(table);\
+	hash_val = do_hash(key, table);\
+    }\
+    \
+    tbl = alloc(st_table_entry);\
+    \
+    tbl->key = key;\
+    tbl->record = value;\
+    tbl->next = table->bins[hash_val];\
+    table->bins[hash_val] = tbl;\
+    table->num_entries++;\
+}
+
+int
+st_insert(table, key, value)
+    register st_table *table;
+    register char *key;
+    char *value;
+{
+    int hash_val;
+    st_table_entry *tbl;
+    register st_table_entry *ptr;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, ptr, hash_val);
+
+    if (ptr == nil(st_table_entry)) {
+	ADD_DIRECT(table,key,value,hash_val,tbl);
+	return 0;
+    } else {
+	ptr->record = value;
+	return 1;
+    }
+}
+
+void
+st_add_direct(table, key, value)
+    st_table *table;
+    char *key;
+    char *value;
+{
+    int hash_val;
+    st_table_entry *tbl;
+
+    hash_val = do_hash(key, table);
+    ADD_DIRECT(table, key, value, hash_val, tbl);
+}
+
+int
+st_find_or_add(table, key, slot)
+    st_table *table;
+    char *key;
+    char ***slot;
+{
+    int hash_val;
+    st_table_entry *tbl, *ptr;
+
+    hash_val = do_hash(key, table);
+
+    FIND_ENTRY(table, ptr, hash_val);
+
+    if (ptr == nil(st_table_entry)) {
+	ADD_DIRECT(table, key, (char*)0, hash_val, tbl)
+	if (slot != nil(char**)) *slot = &tbl->record;
+	return 0;
+    } else {
+	if (slot != nil(char**)) *slot = &ptr->record;
+	return 1;
+    }
+}
+
+static void
+rehash(table)
+    register st_table *table;
+{
+    register st_table_entry *ptr, *next, **old_bins = table->bins;
+    int i, old_num_bins = table->num_bins, hash_val;
+
+    table->num_bins = 1.79*old_num_bins;
+
+    if (table->num_bins%2 == 0) {
+	table->num_bins += 1;
+    }
+
+    table->num_entries = 0;
+    table->bins = (st_table_entry **)
+	Calloc((unsigned)table->num_bins, sizeof(st_table_entry*));
+
+    for(i = 0; i < old_num_bins ; i++) {
+	ptr = old_bins[i];
+	while (ptr != nil(st_table_entry)) {
+	    next = ptr->next;
+	    hash_val = do_hash(ptr->key, table);
+	    ptr->next = table->bins[hash_val];
+	    table->bins[hash_val] = ptr;
+	    table->num_entries++;
+	    ptr = next;
+	}
+    }
+    free((char*)old_bins);
+}
+
+st_table*
+st_copy(old_table)
+    st_table *old_table;
+{
+    st_table *new_table;
+    st_table_entry *ptr, *tbl;
+    int i, num_bins = old_table->num_bins;
+
+    new_table = alloc(st_table);
+    if (new_table == nil(st_table)) {
+	return nil(st_table);
+    }
+
+    *new_table = *old_table;
+    new_table->bins = (st_table_entry**)
+	Calloc((unsigned)num_bins, sizeof(st_table_entry*));
+
+    if (new_table->bins == nil(st_table_entry*)) {
+	free((char*)new_table);
+	return nil(st_table);
+    }
+
+    for(i = 0; i < num_bins ; i++) {
+	new_table->bins[i] = nil(st_table_entry);
+	ptr = old_table->bins[i];
+	while (ptr != nil(st_table_entry)) {
+	    tbl = alloc(st_table_entry);
+	    if (tbl == nil(st_table_entry)) {
+		free((char*)new_table->bins);
+		free((char*)new_table);
+		return nil(st_table);
+	    }
+	    *tbl = *ptr;
+	    tbl->next = new_table->bins[i];
+	    new_table->bins[i] = tbl;
+	    ptr = ptr->next;
+	}
+    }
+    return new_table;
+}
+
+int
+st_delete(table, key, value)
+    register st_table *table;
+    register char **key;
+    char **value;
+{
+    int hash_val;
+    st_table_entry *tmp;
+    register st_table_entry *ptr;
+
+    hash_val = do_hash(*key, table);
+
+    ptr = table->bins[hash_val];
+
+    if (ptr == nil(st_table_entry)) {
+	if (value != nil(char*)) *value = nil(char);
+	return 0;
+    }
+
+    if (EQUAL(table, *key, ptr->key)) {
+	table->bins[hash_val] = ptr->next;
+	table->num_entries--;
+	if (value != nil(char*)) *value = ptr->record;
+	*key = ptr->key;
+	free((char*)ptr);
+	return 1;
+    }
+
+    for(; ptr->next != nil(st_table_entry); ptr = ptr->next) {
+	if (EQUAL(table, ptr->next->key, *key)) {
+	    tmp = ptr->next;
+	    ptr->next = ptr->next->next;
+	    table->num_entries--;
+	    if (value != nil(char*)) *value = tmp->record;
+	    *key = tmp->key;
+	    free((char*)tmp);
+	    return 1;
+	}
+    }
+
+    return 0;
+}
+
+int
+st_delete_safe(table, key, value, never)
+    register st_table *table;
+    register char **key;
+    char **value;
+    char *never;
+{
+    int hash_val;
+    register st_table_entry *ptr;
+
+    hash_val = do_hash(*key, table);
+
+    ptr = table->bins[hash_val];
+
+    if (ptr == nil(st_table_entry)) {
+	if (value != nil(char*)) *value = nil(char);
+	return 0;
+    }
+
+    if (EQUAL(table, *key, ptr->key)) {
+	table->num_entries--;
+	*key = ptr->key;
+	if (value != nil(char*)) *value = ptr->record;
+	ptr->key = ptr->record = never;
+	return 1;
+    }
+
+    for(; ptr->next != nil(st_table_entry); ptr = ptr->next) {
+	if (EQUAL(table, ptr->next->key, *key)) {
+	    table->num_entries--;
+	    *key = ptr->key;
+	    if (value != nil(char*)) *value = ptr->record;
+	    ptr->key = ptr->record = never;
+	    return 1;
+	}
+    }
+
+    return 0;
+}
+
+void
+st_foreach(table, func, arg)
+    st_table *table;
+    enum st_retval (*func)();
+    char *arg;
+{
+    st_table_entry *ptr, *last, *tmp;
+    enum st_retval retval;
+    int i;
+
+    for(i = 0; i < table->num_bins; i++) {
+	last = nil(st_table_entry);
+	for(ptr = table->bins[i]; ptr != nil(st_table_entry);) {
+	    retval = (*func)(ptr->key, ptr->record, arg);
+	    switch (retval) {
+	    case ST_CONTINUE:
+		last = ptr;
+		ptr = ptr->next;
+		break;
+	    case ST_STOP:
+		return;
+	    case ST_DELETE:
+		tmp = ptr;
+		if (last == nil(st_table_entry)) {
+		    table->bins[i] = ptr->next;
+		} else {
+		    last->next = ptr->next;
+		}
+		ptr = ptr->next;
+		free((char*)tmp);
+		table->num_entries--;
+	    }
+	}
+    }
+}
+
+static int
+strhash(string, modulus)
+    register char *string;
+    int modulus;
+{
+    register int val = 0;
+    register int c;
+
+    while ((c = *string++) != '\0') {
+	val = val*997 + c;
+    }
+
+    return ((val < 0) ? -val : val)%modulus;
+}
+
+static int
+numcmp(x, y)
+    int x, y;
+{
+    return x != y;
+}
+
+static int
+numhash(n, modulus)
+    int n;
+    int modulus;
+{
+    return n % modulus;
+}
diff --git a/st.h b/st.h
new file mode 100644
index 0000000000..c27b110ce1
--- /dev/null
+++ b/st.h
@@ -0,0 +1,52 @@
+/* This is a general purpose hash table package written by Peter Moore @ UCB. */
+
+/* @(#) st.h 5.1 89/12/14 */
+
+#ifndef ST_INCLUDED
+
+#define ST_INCLUDED
+
+typedef struct st_table_entry st_table_entry;
+
+struct st_table_entry {
+    char *key;
+    char *record;
+    st_table_entry *next;
+};
+
+typedef struct st_table st_table;
+
+struct st_hash_type {
+    int (*compare)();
+    int (*hash)();
+};
+
+struct st_table {
+    struct st_hash_type *type;
+    int num_bins;
+    int num_entries;
+    st_table_entry **bins;
+};
+
+#define st_is_member(table,key) st_lookup(table,key,(char **) 0)
+
+enum st_retval {ST_CONTINUE, ST_STOP, ST_DELETE};
+
+st_table *st_init_table();
+st_table *st_init_table_with_size();
+st_table *st_init_numtable();
+st_table *st_init_strtable();
+int st_delete(), st_delete_safe(), st_insert();
+int st_lookup(), st_find_or_add();
+void st_foreach(), st_add_direct(), st_free_table();
+st_table *st_copy();
+
+#define ST_NUMCMP	((int (*)()) 0)
+#define ST_NUMHASH	((int (*)()) -2)
+
+#define st_numcmp	ST_NUMCMP
+#define st_numhash	ST_NUMHASH
+
+int st_strhash();
+
+#endif /* ST_INCLUDED */