~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to regex/regex2.h

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
/*
 
2
 * First, the stuff that ends up in the outside-world include file
 
3
 = typedef off_t regoff_t;
 
4
 = typedef struct {
 
5
 =      int re_magic;
 
6
 =      size_t re_nsub;         // number of parenthesized subexpressions
 
7
 =      const char *re_endp;    // end pointer for REG_PEND
 
8
 =      struct re_guts *re_g;   // none of your business :-)
 
9
 = } regex_t;
 
10
 = typedef struct {
 
11
 =      regoff_t rm_so;         // start of match
 
12
 =      regoff_t rm_eo;         // end of match
 
13
 = } regmatch_t;
 
14
 */
 
15
/*
 
16
 * internals of regex_t
 
17
 */
 
18
#ifndef __regex2_h__
 
19
#define __regex2_h__
 
20
 
 
21
#define MAGIC1  ((('r'^0200)<<8) | 'e')
 
22
 
 
23
/*
 
24
 * The internal representation is a *strip*, a sequence of
 
25
 * operators ending with an endmarker.  (Some terminology etc. is a
 
26
 * historical relic of earlier versions which used multiple strips.)
 
27
 * Certain oddities in the representation are there to permit running
 
28
 * the machinery backwards; in particular, any deviation from sequential
 
29
 * flow must be marked at both its source and its destination.  Some
 
30
 * fine points:
 
31
 *
 
32
 * - OPLUS_ and O_PLUS are *inside* the loop they create.
 
33
 * - OQUEST_ and O_QUEST are *outside* the bypass they create.
 
34
 * - OCH_ and O_CH are *outside* the multi-way branch they create, while
 
35
 *   OOR1 and OOR2 are respectively the end and the beginning of one of
 
36
 *   the branches.  Note that there is an implicit OOR2 following OCH_
 
37
 *   and an implicit OOR1 preceding O_CH.
 
38
 *
 
39
 * In state representations, an operator's bit is on to signify a state
 
40
 * immediately *preceding* "execution" of that operator.
 
41
 */
 
42
typedef unsigned long sop;      /* strip operator */
 
43
typedef long sopno;
 
44
#define OPRMASK 0xf8000000
 
45
#define OPDMASK 0x07ffffff
 
46
#define OPSHIFT ((unsigned long)27)
 
47
#define OP(n)   ((unsigned long) ((n)&OPRMASK))
 
48
#define OPND(n) ((unsigned long) ((n)&OPDMASK))
 
49
#define SOP(op, opnd)   (unsigned long) ((op)|(opnd))
 
50
#define OSHIFT(A) ((unsigned long) (A) << OPSHIFT)
 
51
/* operators                       meaning      operand                 */
 
52
/*                                              (back, fwd are offsets) */
 
53
#define OEND    OSHIFT(1)       /* endmarker    -                       */
 
54
#define OCHAR   OSHIFT(2)       /* character    unsigned char           */
 
55
#define OBOL    OSHIFT(3)       /* left anchor  -                       */
 
56
#define OEOL    OSHIFT(4)       /* right anchor -                       */
 
57
#define OANY    OSHIFT(5)       /* .            -                       */
 
58
#define OANYOF  OSHIFT(6)       /* [...]        set number              */
 
59
#define OBACK_  OSHIFT(7)       /* begin \d     paren number            */
 
60
#define O_BACK  OSHIFT(8)       /* end \d       paren number            */
 
61
#define OPLUS_  OSHIFT(9)       /* + prefix     fwd to suffix           */
 
62
#define O_PLUS  OSHIFT(10)      /* + suffix     back to prefix          */
 
63
#define OQUEST_ OSHIFT(11)      /* ? prefix     fwd to suffix           */
 
64
#define O_QUEST OSHIFT(12)      /* ? suffix     back to prefix          */
 
65
#define OLPAREN OSHIFT(13)      /* (            fwd to )                */
 
66
#define ORPAREN OSHIFT(14)      /* )            back to (               */
 
67
#define OCH_    OSHIFT(15)      /* begin choice fwd to OOR2             */
 
68
#define OOR1    OSHIFT(16)      /* | pt. 1      back to OOR1 or OCH_    */
 
69
#define OOR2    OSHIFT(17)      /* | pt. 2      fwd to OOR2 or O_CH     */
 
70
#define O_CH    OSHIFT(18)      /* end choice   back to OOR1            */
 
71
#define OBOW    OSHIFT(19)      /* begin word   -                       */
 
72
#define OEOW    OSHIFT(20)      /* end word     -                       */
 
73
 
 
74
/*
 
75
 * Structure for [] character-set representation.  Character sets are
 
76
 * done as bit vectors, grouped 8 to a byte vector for compactness.
 
77
 * The individual set therefore has both a pointer to the byte vector
 
78
 * and a mask to pick out the relevant bit of each byte.  A hash code
 
79
 * simplifies testing whether two sets could be identical.
 
80
 *
 
81
 * This will get trickier for multicharacter collating elements.  As
 
82
 * preliminary hooks for dealing with such things, we also carry along
 
83
 * a string of multi-character elements, and decide the size of the
 
84
 * vectors at run time.
 
85
 */
 
86
#ifdef __WIN__
 
87
typedef unsigned char uch ;
 
88
#endif
 
89
 
 
90
typedef struct {
 
91
        uch *ptr;               /* -> uch [csetsize] */
 
92
        uch mask;               /* bit within array */
 
93
        uch hash;               /* hash code */
 
94
        size_t smultis;
 
95
        char *multis;           /* -> char[smulti]  ab\0cd\0ef\0\0 */
 
96
} cset;
 
97
/* note that CHadd and CHsub are unsafe, and CHIN doesn't yield 0/1 */
 
98
#define CHadd(cs, c)    ((cs)->ptr[(uch)(c)] |= (cs)->mask, (cs)->hash += (uch) (c))
 
99
#define CHsub(cs, c)    ((cs)->ptr[(uch)(c)] &= ~(cs)->mask, (cs)->hash -= (uch)(c))
 
100
#define CHIN(cs, c)     ((cs)->ptr[(uch)(c)] & (cs)->mask)
 
101
#define MCadd(p, cs, cp)        mcadd(p, cs, cp)        /* regcomp() internal fns */
 
102
#define MCsub(p, cs, cp)        mcsub(p, cs, cp)
 
103
#define MCin(p, cs, cp) mcin(p, cs, cp)
 
104
 
 
105
/* stuff for character categories */
 
106
typedef unsigned char cat_t;
 
107
 
 
108
/*
 
109
 * main compiled-expression structure
 
110
 */
 
111
struct re_guts {
 
112
        int magic;
 
113
#               define  MAGIC2  ((('R'^0200)<<8)|'E')
 
114
        sop *strip;             /* malloced area for strip */
 
115
        int csetsize;           /* number of bits in a cset vector */
 
116
        int ncsets;             /* number of csets in use */
 
117
        cset *sets;             /* -> cset [ncsets] */
 
118
        uch *setbits;           /* -> uch[csetsize][ncsets/CHAR_BIT] */
 
119
        int cflags;             /* copy of regcomp() cflags argument */
 
120
        sopno nstates;          /* = number of sops */
 
121
        sopno firststate;       /* the initial OEND (normally 0) */
 
122
        sopno laststate;        /* the final OEND */
 
123
        int iflags;             /* internal flags */
 
124
#               define  USEBOL  01      /* used ^ */
 
125
#               define  USEEOL  02      /* used $ */
 
126
#               define  BAD     04      /* something wrong */
 
127
        int nbol;               /* number of ^ used */
 
128
        int neol;               /* number of $ used */
 
129
        int ncategories;        /* how many character categories */
 
130
        cat_t *categories;      /* ->catspace[-CHAR_MIN] */
 
131
        char *must;             /* match must contain this string */
 
132
        int mlen;               /* length of must */
 
133
        size_t nsub;            /* copy of re_nsub */
 
134
        int backrefs;           /* does it use back references? */
 
135
        sopno nplus;            /* how deep does it nest +s? */
 
136
        /* catspace must be last */
 
137
        cat_t catspace[1];      /* actually [NC] */
 
138
};
 
139
 
 
140
/* misc utilities */
 
141
#undef OUT                      /* May be defined in windows */
 
142
#define OUT     (CHAR_MAX+1)    /* a non-character value */
 
143
#define ISWORD(s,c)     (my_isalnum(s,c) || (c) == '_')
 
144
 
 
145
#endif /* __regex2_h__ */