Libc-498.tar.gz

[apple/libc.git] / regex / regex2.h

diff --git a/regex/regex2.h b/regex/regex2.h
index d68f62b30bb41992ed69747c951c4ed043f1ce82..15a6bcf491b1577ae38a994310e000c84593edea 100644 (file)
--- a/regex/regex2.h
+++ b/regex/regex2.h
@@ -1,25 +1,5 @@
-/*
- * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
- *
- * @APPLE_LICENSE_HEADER_START@
- * 
- * The contents of this file constitute Original Code as defined in and
- * are subject to the Apple Public Source License Version 1.1 (the
- * "License").  You may not use this file except in compliance with the
- * License.  Please obtain a copy of the License at
- * http://www.apple.com/publicsource and read it before using this file.
- * 
- * This Original Code and all software distributed under the License are
- * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
- * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
- * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
- * License for the specific language governing rights and limitations
- * under the License.
- * 
- * @APPLE_LICENSE_HEADER_END@
- */
-/*
+/*-
+ * Copyright (c) 1992, 1993, 1994 Henry Spencer.

  * Copyright (c) 1992, 1993, 1994
  *     The Regents of the University of California.  All rights reserved.
  *
  * Copyright (c) 1992, 1993, 1994
  *     The Regents of the University of California.  All rights reserved.
  *


@@ -53,6 +33,9 @@
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.

+ *
+ *     @(#)regex2.h    8.4 (Berkeley) 3/20/94
+ * $FreeBSD: src/lib/libc/regex/regex2.h,v 1.8 2004/07/12 07:35:59 tjr Exp $

  */
 
 /*
  */
 
 /*


@@ -95,64 +78,104 @@
  */
 typedef unsigned long sop;     /* strip operator */
 typedef long sopno;
  */
 typedef unsigned long sop;     /* strip operator */
 typedef long sopno;

-#define        OPRMASK 0xf8000000
-#define        OPDMASK 0x07ffffff
+#define        OPRMASK 0xf8000000L
+#define        OPDMASK 0x07ffffffL

 #define        OPSHIFT ((unsigned)27)
 #define        OP(n)   ((n)&OPRMASK)
 #define        OPND(n) ((n)&OPDMASK)
 #define        SOP(op, opnd)   ((op)|(opnd))
 /* operators                      meaning      operand                 */
 /*                                             (back, fwd are offsets) */
 #define        OPSHIFT ((unsigned)27)
 #define        OP(n)   ((n)&OPRMASK)
 #define        OPND(n) ((n)&OPDMASK)
 #define        SOP(op, opnd)   ((op)|(opnd))
 /* operators                      meaning      operand                 */
 /*                                             (back, fwd are offsets) */

-#define        OEND    (1<<OPSHIFT)    /* endmarker    -                       */
-#define        OCHAR   (2<<OPSHIFT)    /* character    unsigned char           */
-#define        OBOL    (3<<OPSHIFT)    /* left anchor  -                       */
-#define        OEOL    (4<<OPSHIFT)    /* right anchor -                       */
-#define        OANY    (5<<OPSHIFT)    /* .            -                       */
-#define        OANYOF  (6<<OPSHIFT)    /* [...]        set number              */
-#define        OBACK_  (7<<OPSHIFT)    /* begin \d     paren number            */
-#define        O_BACK  (8<<OPSHIFT)    /* end \d       paren number            */
-#define        OPLUS_  (9<<OPSHIFT)    /* + prefix     fwd to suffix           */
-#define        O_PLUS  (10<<OPSHIFT)   /* + suffix     back to prefix          */
-#define        OQUEST_ (11<<OPSHIFT)   /* ? prefix     fwd to suffix           */
-#define        O_QUEST (12<<OPSHIFT)   /* ? suffix     back to prefix          */
-#define        OLPAREN (13<<OPSHIFT)   /* (            fwd to )                */
-#define        ORPAREN (14<<OPSHIFT)   /* )            back to (               */
-#define        OCH_    (15<<OPSHIFT)   /* begin choice fwd to OOR2             */
-#define        OOR1    (16<<OPSHIFT)   /* | pt. 1      back to OOR1 or OCH_    */
-#define        OOR2    (17<<OPSHIFT)   /* | pt. 2      fwd to OOR2 or O_CH     */
-#define        O_CH    (18<<OPSHIFT)   /* end choice   back to OOR1            */
-#define        OBOW    (19<<OPSHIFT)   /* begin word   -                       */
-#define        OEOW    (20<<OPSHIFT)   /* end word     -                       */
+#define        OEND    (1L<<OPSHIFT)   /* endmarker    -                       */
+#define        OCHAR   (2L<<OPSHIFT)   /* character    wide character          */
+#define        OBOL    (3L<<OPSHIFT)   /* left anchor  -                       */
+#define        OEOL    (4L<<OPSHIFT)   /* right anchor -                       */
+#define        OANY    (5L<<OPSHIFT)   /* .            -                       */
+#define        OANYOF  (6L<<OPSHIFT)   /* [...]        set number              */
+#define        OBACK_  (7L<<OPSHIFT)   /* begin \d     paren number            */
+#define        O_BACK  (8L<<OPSHIFT)   /* end \d       paren number            */
+#define        OPLUS_  (9L<<OPSHIFT)   /* + prefix     fwd to suffix           */
+#define        O_PLUS  (10L<<OPSHIFT)  /* + suffix     back to prefix          */
+#define        OQUEST_ (11L<<OPSHIFT)  /* ? prefix     fwd to suffix           */
+#define        O_QUEST (12L<<OPSHIFT)  /* ? suffix     back to prefix          */
+#define        OLPAREN (13L<<OPSHIFT)  /* (            fwd to )                */
+#define        ORPAREN (14L<<OPSHIFT)  /* )            back to (               */
+#define        OCH_    (15L<<OPSHIFT)  /* begin choice fwd to OOR2             */
+#define        OOR1    (16L<<OPSHIFT)  /* | pt. 1      back to OOR1 or OCH_    */
+#define        OOR2    (17L<<OPSHIFT)  /* | pt. 2      fwd to OOR2 or O_CH     */
+#define        O_CH    (18L<<OPSHIFT)  /* end choice   back to OOR1            */
+#define        OBOW    (19L<<OPSHIFT)  /* begin word   -                       */
+#define        OEOW    (20L<<OPSHIFT)  /* end word     -                       */

 
 /*
 
 /*

- * Structure for [] character-set representation.  Character sets are
- * done as bit vectors, grouped 8 to a byte vector for compactness.
- * The individual set therefore has both a pointer to the byte vector
- * and a mask to pick out the relevant bit of each byte.  A hash code
- * simplifies testing whether two sets could be identical.
- *
- * This will get trickier for multicharacter collating elements.  As
- * preliminary hooks for dealing with such things, we also carry along
- * a string of multi-character elements, and decide the size of the
- * vectors at run time.
+ * Structures for [] character-set representation.

  */
 typedef struct {
  */
 typedef struct {

-       uch *ptr;               /* -> uch [csetsize] */
-       uch mask;               /* bit within array */
-       uch hash;               /* hash code */
-       size_t smultis;
-       char *multis;           /* -> char[smulti]  ab\0cd\0ef\0\0 */
+       wint_t          min;
+       wint_t          max;
+} crange;
+typedef struct {
+       unsigned char   bmp[NC / 8];
+       wctype_t        *types;
+       int             ntypes;
+       wint_t          *wides;
+       int             nwides;
+       crange          *ranges;
+       int             nranges;
+       int             invert;
+       int             icase;
+       int             *equiv_classes;
+       int             nequiv_classes;

 } cset;
 } cset;

-/* note that CHadd and CHsub are unsafe, and CHIN doesn't yield 0/1 */
-#define        CHadd(cs, c)    ((cs)->ptr[(uch)(c)] |= (cs)->mask, (cs)->hash += (c))
-#define        CHsub(cs, c)    ((cs)->ptr[(uch)(c)] &= ~(cs)->mask, (cs)->hash -= (c))
-#define        CHIN(cs, c)     ((cs)->ptr[(uch)(c)] & (cs)->mask)
-#define        MCadd(p, cs, cp)        mcadd(p, cs, cp)        /* regcomp() internal fns */
-#define        MCsub(p, cs, cp)        mcsub(p, cs, cp)
-#define        MCin(p, cs, cp) mcin(p, cs, cp)

 
 

-/* stuff for character categories */
-typedef unsigned char cat_t;
+#include "collate.h"
+
+static int
+CHIN1(cs, ch, loc)
+cset *cs;
+wint_t ch;
+locale_t loc;
+{
+       int i;
+
+       assert(ch >= 0);
+       for (i = 0; i < cs->nequiv_classes; i++)
+               /* sadly, we can only deal with single characters from an
+                * equivalence class */
+               if (__collate_equiv_match(cs->equiv_classes[i], NULL, 0, ch, NULL, 0, NULL, NULL, loc) > 0)
+                       return (!cs->invert);
+       if (ch < NC)
+               return (((cs->bmp[ch >> 3] & (1 << (ch & 7))) != 0) ^
+                   cs->invert);
+       for (i = 0; i < cs->nwides; i++)
+               if (ch == cs->wides[i])
+                       return (!cs->invert);
+       for (i = 0; i < cs->nranges; i++)
+               if (cs->ranges[i].min <= ch && ch <= cs->ranges[i].max)
+                       return (!cs->invert);
+       for (i = 0; i < cs->ntypes; i++)
+               if (iswctype_l(ch, cs->types[i], loc))
+                       return (!cs->invert);
+       return (cs->invert);
+}
+
+static __inline int
+CHIN(cs, ch, loc)
+cset *cs;
+wint_t ch;
+locale_t loc;
+{
+
+       assert(ch >= 0);
+       if (ch < NC && cs->nequiv_classes == 0)
+               return (((cs->bmp[ch >> 3] & (1 << (ch & 7))) != 0) ^
+                   cs->invert);
+       else if (cs->icase)
+               return (CHIN1(cs, ch, loc) || CHIN1(cs, towlower_l(ch, loc), loc) ||
+                   CHIN1(cs, towupper_l(ch, loc), loc));
+       else
+               return (CHIN1(cs, ch, loc));
+}

 
 /*
  * main compiled-expression structure
 
 /*
  * main compiled-expression structure


@@ -161,10 +184,8 @@ struct re_guts {
        int magic;
 #              define  MAGIC2  ((('R'^0200)<<8)|'E')
        sop *strip;             /* malloced area for strip */
        int magic;
 #              define  MAGIC2  ((('R'^0200)<<8)|'E')
        sop *strip;             /* malloced area for strip */

-       int csetsize;           /* number of bits in a cset vector */

        int ncsets;             /* number of csets in use */
        cset *sets;             /* -> cset [ncsets] */
        int ncsets;             /* number of csets in use */
        cset *sets;             /* -> cset [ncsets] */

-       uch *setbits;           /* -> uch[csetsize][ncsets/CHAR_BIT] */

        int cflags;             /* copy of regcomp() cflags argument */
        sopno nstates;          /* = number of sops */
        sopno firststate;       /* the initial OEND (normally 0) */
        int cflags;             /* copy of regcomp() cflags argument */
        sopno nstates;          /* = number of sops */
        sopno firststate;       /* the initial OEND (normally 0) */


@@ -175,17 +196,17 @@ struct re_guts {
 #              define  BAD     04      /* something wrong */
        int nbol;               /* number of ^ used */
        int neol;               /* number of $ used */
 #              define  BAD     04      /* something wrong */
        int nbol;               /* number of ^ used */
        int neol;               /* number of $ used */

-       int ncategories;        /* how many character categories */
-       cat_t *categories;      /* ->catspace[-CHAR_MIN] */

        char *must;             /* match must contain this string */
        char *must;             /* match must contain this string */

+       int moffset;            /* latest point at which must may be located */
+       int *charjump;          /* Boyer-Moore char jump table */
+       int *matchjump;         /* Boyer-Moore match jump table */

        int mlen;               /* length of must */
        size_t nsub;            /* copy of re_nsub */
        int backrefs;           /* does it use back references? */
        sopno nplus;            /* how deep does it nest +s? */
        int mlen;               /* length of must */
        size_t nsub;            /* copy of re_nsub */
        int backrefs;           /* does it use back references? */
        sopno nplus;            /* how deep does it nest +s? */

-       /* catspace must be last */
-       cat_t catspace[1];      /* actually [NC] */
+       locale_t loc;           /* current locale */

 };
 
 /* misc utilities */
 };
 
 /* misc utilities */

-#define        OUT     (CHAR_MAX+1)    /* a non-character value */
-#define        ISWORD(c)       (isalnum(c) || (c) == '_')
+#define        OUT     (-130)  /* a non-character value */
+#define ISWORD(c,l)     (iswalnum_l((uch)(c), l) || (c) == '_')