← Back to branch summary

~hamo/ubuntu/precise/grub2/grub2.hi_res

« back to all changes in this revision

Viewing changes to gnulib/regex_internal.h

  • Committer: Bazaar Package Importer
  • Author(s): Colin Watson, Colin Watson, Evan Broder, Mario Limonciello
  • Date: 2010-11-24 13:59:55 UTC
  • mfrom: (1.17.6 upstream) (17.6.15 experimental)
  • Revision ID: james.westby@ubuntu.com-20101124135955-r6ii5sepayr7jt53
Tags: 1.99~20101124-1ubuntu1
https://launchpad.net/bugs/677758
[ Colin Watson ]
* Resynchronise with Debian experimental.  Remaining changes:
  - Adjust for default Ubuntu boot options ("quiet splash").
  - Default to hiding the menu; holding down Shift at boot will show it.
  - Set a monochromatic theme for Ubuntu.
  - Apply Ubuntu GRUB Legacy changes to legacy update-grub script: title,
    recovery mode, quiet option, tweak how memtest86+ is displayed, and
    use UUIDs where appropriate.
  - Fix backslash-escaping in merge_debconf_into_conf.
  - Remove "GNU/Linux" from default distributor string.
  - Add crashkernel= options if kdump and makedumpfile are available.
  - If other operating systems are installed, then automatically unhide
    the menu.  Otherwise, if GRUB_HIDDEN_TIMEOUT is 0, then use keystatus
    if available to check whether Shift is pressed.  If it is, show the
    menu, otherwise boot immediately.  If keystatus is not available, then
    fall back to a short delay interruptible with Escape.
  - Allow Shift to interrupt 'sleep --interruptible'.
  - Don't display introductory message about line editing unless we're
    actually offering a shell prompt.  Don't clear the screen just before
    booting if we never drew the menu in the first place.
  - Remove some verbose messages printed before reading the configuration
    file.
  - Suppress progress messages as the kernel and initrd load for
    non-recovery kernel menu entries.
  - Change prepare_grub_to_access_device to handle filesystems
    loop-mounted on file images.
  - Ignore devices loop-mounted from files in 10_linux.
  - Show the boot menu if the previous boot failed, that is if it failed
    to get to the end of one of the normal runlevels.
  - Don't generate /boot/grub/device.map during grub-install or
    grub-mkconfig by default.
  - Adjust upgrade version checks for Ubuntu.
  - Don't display "GRUB loading" unless Shift is held down.
  - Adjust versions of grub-doc and grub-legacy-doc conflicts to tolerate
    our backport of the grub-doc split.
  - Fix LVM/RAID probing in the absence of /boot/grub/device.map.
  - Look for .mo files in /usr/share/locale-langpack as well, in
    preference.
  - Make sure GRUB_TIMEOUT isn't quoted unnecessarily.
  - Probe all devices in 'grub-probe --target=drive' if
    /boot/grub/device.map is missing.
  - Build-depend on qemu-kvm rather than qemu-system for grub-pc tests.
  - Use qemu rather than qemu-system-i386.
  - Program vesafb on BIOS systems rather than efifb.
  - Add a grub-rescue-efi-amd64 package containing a rescue CD-ROM image
    for EFI-AMD64.
  - On Wubi, don't ask for an install device, but just update wubildr
    using the diverted grub-install.
  - When embedding the core image in a post-MBR gap, check for and avoid
    sectors matching any of a list of known signatures.
  - Disable video_bochs and video_cirrus on PC BIOS systems, as probing
    PCI space seems to break on some systems.
* Downgrade "ACPI shutdown failed" error to a debug message, since it can
  cause spurious test failures.

[ Evan Broder ]
* Enable lua from grub-extras.
* Incorporate the bitop library into lua.
* Add enum_pci function to grub module in lua.
* Switch back to gfxpayload=keep by default, unless the video hardware
  is known to not support it.

[ Mario Limonciello ]
* Built part_msdos and vfat into bootx64.efi (LP: #677758)

Show diffs side-by-side

added added

removed removed

Lines of Context:
gnulib/regex_internal.h
1
 
/* Extended regular expression matching and search library.
2
 
   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free
3
 
   Software Foundation, Inc.
4
 
   This file is part of the GNU C Library.
5
 
   Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
6
 
 
7
 
   This program is free software; you can redistribute it and/or modify
8
 
   it under the terms of the GNU General Public License as published by
9
 
   the Free Software Foundation; either version 2, or (at your option)
10
 
   any later version.
11
 
 
12
 
   This program is distributed in the hope that it will be useful,
13
 
   but WITHOUT ANY WARRANTY; without even the implied warranty of
14
 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
 
   GNU General Public License for more details.
16
 
 
17
 
   You should have received a copy of the GNU General Public License along
18
 
   with this program; if not, write to the Free Software Foundation,
19
 
   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
20
 
 
21
 
#ifndef _REGEX_INTERNAL_H
22
 
#define _REGEX_INTERNAL_H 1
23
 
 
24
 
#include <assert.h>
25
 
#include <ctype.h>
26
 
#include <stdbool.h>
27
 
#include <stdio.h>
28
 
#include <stdlib.h>
29
 
#include <string.h>
30
 
 
31
 
#include <langinfo.h>
32
 
#ifndef _LIBC
33
 
# include "localcharset.h"
34
 
#endif
35
 
#if defined HAVE_LOCALE_H || defined _LIBC
36
 
# include <locale.h>
37
 
#endif
38
 
 
39
 
#include <wchar.h>
40
 
#include <wctype.h>
41
 
#include <stdint.h>
42
 
#if defined _LIBC
43
 
# include <bits/libc-lock.h>
44
 
#else
45
 
# define __libc_lock_init(NAME) do { } while (0)
46
 
# define __libc_lock_lock(NAME) do { } while (0)
47
 
# define __libc_lock_unlock(NAME) do { } while (0)
48
 
#endif
49
 
 
50
 
/* In case that the system doesn't have isblank().  */
51
 
#if !defined _LIBC && ! (defined isblank || (HAVE_ISBLANK && HAVE_DECL_ISBLANK))
52
 
# define isblank(ch) ((ch) == ' ' || (ch) == '\t')
53
 
#endif
54
 
 
55
 
#ifdef _LIBC
56
 
# ifndef _RE_DEFINE_LOCALE_FUNCTIONS
57
 
#  define _RE_DEFINE_LOCALE_FUNCTIONS 1
58
 
#   include <locale/localeinfo.h>
59
 
#   include <locale/elem-hash.h>
60
 
#   include <locale/coll-lookup.h>
61
 
# endif
62
 
#endif
63
 
 
64
 
/* This is for other GNU distributions with internationalized messages.  */
65
 
#if (HAVE_LIBINTL_H && ENABLE_NLS) || defined _LIBC
66
 
# include <libintl.h>
67
 
# ifdef _LIBC
68
 
#  undef gettext
69
 
#  define gettext(msgid) \
70
 
  INTUSE(__dcgettext) (_libc_intl_domainname, msgid, LC_MESSAGES)
71
 
# endif
72
 
#else
73
 
# define gettext(msgid) (msgid)
74
 
#endif
75
 
 
76
 
#ifndef gettext_noop
77
 
/* This define is so xgettext can find the internationalizable
78
 
   strings.  */
79
 
# define gettext_noop(String) String
80
 
#endif
81
 
 
82
 
/* For loser systems without the definition.  */
83
 
#ifndef SIZE_MAX
84
 
# define SIZE_MAX ((size_t) -1)
85
 
#endif
86
 
 
87
 
#if (defined MB_CUR_MAX && HAVE_LOCALE_H && HAVE_WCTYPE_H && HAVE_ISWCTYPE && HAVE_WCSCOLL) || _LIBC
88
 
# define RE_ENABLE_I18N
89
 
#endif
90
 
 
91
 
#if __GNUC__ >= 3
92
 
# define BE(expr, val) __builtin_expect (expr, val)
93
 
#else
94
 
# define BE(expr, val) (expr)
95
 
# ifdef _LIBC
96
 
#  define inline
97
 
# endif
98
 
#endif
99
 
 
100
 
/* Number of ASCII characters.  */
101
 
#define ASCII_CHARS 0x80
102
 
 
103
 
/* Number of single byte characters.  */
104
 
#define SBC_MAX (UCHAR_MAX + 1)
105
 
 
106
 
#define COLL_ELEM_LEN_MAX 8
107
 
 
108
 
/* The character which represents newline.  */
109
 
#define NEWLINE_CHAR '\n'
110
 
#define WIDE_NEWLINE_CHAR L'\n'
111
 
 
112
 
/* Rename to standard API for using out of glibc.  */
113
 
#ifndef _LIBC
114
 
# define __wctype wctype
115
 
# define __iswctype iswctype
116
 
# define __btowc btowc
117
 
# define __wcrtomb wcrtomb
118
 
# define __mbrtowc mbrtowc
119
 
# define __regfree regfree
120
 
# define attribute_hidden
121
 
#endif /* not _LIBC */
122
 
 
123
 
#if __GNUC__ >= 4 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 1)
124
 
# define __attribute(arg) __attribute__ (arg)
125
 
#else
126
 
# define __attribute(arg)
127
 
#endif
128
 
 
129
 
typedef __re_idx_t Idx;
130
 
 
131
 
/* Special return value for failure to match.  */
132
 
#define REG_MISSING ((Idx) -1)
133
 
 
134
 
/* Special return value for internal error.  */
135
 
#define REG_ERROR ((Idx) -2)
136
 
 
137
 
/* Test whether N is a valid index, and is not one of the above.  */
138
 
#ifdef _REGEX_LARGE_OFFSETS
139
 
# define REG_VALID_INDEX(n) ((Idx) (n) < REG_ERROR)
140
 
#else
141
 
# define REG_VALID_INDEX(n) (0 <= (n))
142
 
#endif
143
 
 
144
 
/* Test whether N is a valid nonzero index.  */
145
 
#ifdef _REGEX_LARGE_OFFSETS
146
 
# define REG_VALID_NONZERO_INDEX(n) ((Idx) ((n) - 1) < (Idx) (REG_ERROR - 1))
147
 
#else
148
 
# define REG_VALID_NONZERO_INDEX(n) (0 < (n))
149
 
#endif
150
 
 
151
 
/* A hash value, suitable for computing hash tables.  */
152
 
typedef __re_size_t re_hashval_t;
153
 
 
154
 
/* An integer used to represent a set of bits.  It must be unsigned,
155
 
   and must be at least as wide as unsigned int.  */
156
 
typedef unsigned long int bitset_word_t;
157
 
/* All bits set in a bitset_word_t.  */
158
 
#define BITSET_WORD_MAX ULONG_MAX
159
 
 
160
 
/* Number of bits in a bitset_word_t.  For portability to hosts with
161
 
   padding bits, do not use '(sizeof (bitset_word_t) * CHAR_BIT)';
162
 
   instead, deduce it directly from BITSET_WORD_MAX.  Avoid
163
 
   greater-than-32-bit integers and unconditional shifts by more than
164
 
   31 bits, as they're not portable.  */
165
 
#if BITSET_WORD_MAX == 0xffffffffUL
166
 
# define BITSET_WORD_BITS 32
167
 
#elif BITSET_WORD_MAX >> 31 >> 4 == 1
168
 
# define BITSET_WORD_BITS 36
169
 
#elif BITSET_WORD_MAX >> 31 >> 16 == 1
170
 
# define BITSET_WORD_BITS 48
171
 
#elif BITSET_WORD_MAX >> 31 >> 28 == 1
172
 
# define BITSET_WORD_BITS 60
173
 
#elif BITSET_WORD_MAX >> 31 >> 31 >> 1 == 1
174
 
# define BITSET_WORD_BITS 64
175
 
#elif BITSET_WORD_MAX >> 31 >> 31 >> 9 == 1
176
 
# define BITSET_WORD_BITS 72
177
 
#elif BITSET_WORD_MAX >> 31 >> 31 >> 31 >> 31 >> 3 == 1
178
 
# define BITSET_WORD_BITS 128
179
 
#elif BITSET_WORD_MAX >> 31 >> 31 >> 31 >> 31 >> 31 >> 31 >> 31 >> 31 >> 7 == 1
180
 
# define BITSET_WORD_BITS 256
181
 
#elif BITSET_WORD_MAX >> 31 >> 31 >> 31 >> 31 >> 31 >> 31 >> 31 >> 31 >> 7 > 1
182
 
# define BITSET_WORD_BITS 257 /* any value > SBC_MAX will do here */
183
 
# if BITSET_WORD_BITS <= SBC_MAX
184
 
#  error "Invalid SBC_MAX"
185
 
# endif
186
 
#else
187
 
# error "Add case for new bitset_word_t size"
188
 
#endif
189
 
 
190
 
/* Number of bitset_word_t values in a bitset_t.  */
191
 
#define BITSET_WORDS ((SBC_MAX + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
192
 
 
193
 
typedef bitset_word_t bitset_t[BITSET_WORDS];
194
 
typedef bitset_word_t *re_bitset_ptr_t;
195
 
typedef const bitset_word_t *re_const_bitset_ptr_t;
196
 
 
197
 
#define PREV_WORD_CONSTRAINT 0x0001
198
 
#define PREV_NOTWORD_CONSTRAINT 0x0002
199
 
#define NEXT_WORD_CONSTRAINT 0x0004
200
 
#define NEXT_NOTWORD_CONSTRAINT 0x0008
201
 
#define PREV_NEWLINE_CONSTRAINT 0x0010
202
 
#define NEXT_NEWLINE_CONSTRAINT 0x0020
203
 
#define PREV_BEGBUF_CONSTRAINT 0x0040
204
 
#define NEXT_ENDBUF_CONSTRAINT 0x0080
205
 
#define WORD_DELIM_CONSTRAINT 0x0100
206
 
#define NOT_WORD_DELIM_CONSTRAINT 0x0200
207
 
 
208
 
typedef enum
209
 
{
210
 
  INSIDE_WORD = PREV_WORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
211
 
  WORD_FIRST = PREV_NOTWORD_CONSTRAINT | NEXT_WORD_CONSTRAINT,
212
 
  WORD_LAST = PREV_WORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
213
 
  INSIDE_NOTWORD = PREV_NOTWORD_CONSTRAINT | NEXT_NOTWORD_CONSTRAINT,
214
 
  LINE_FIRST = PREV_NEWLINE_CONSTRAINT,
215
 
  LINE_LAST = NEXT_NEWLINE_CONSTRAINT,
216
 
  BUF_FIRST = PREV_BEGBUF_CONSTRAINT,
217
 
  BUF_LAST = NEXT_ENDBUF_CONSTRAINT,
218
 
  WORD_DELIM = WORD_DELIM_CONSTRAINT,
219
 
  NOT_WORD_DELIM = NOT_WORD_DELIM_CONSTRAINT
220
 
} re_context_type;
221
 
 
222
 
typedef struct
223
 
{
224
 
  Idx alloc;
225
 
  Idx nelem;
226
 
  Idx *elems;
227
 
} re_node_set;
228
 
 
229
 
typedef enum
230
 
{
231
 
  NON_TYPE = 0,
232
 
 
233
 
  /* Node type, These are used by token, node, tree.  */
234
 
  CHARACTER = 1,
235
 
  END_OF_RE = 2,
236
 
  SIMPLE_BRACKET = 3,
237
 
  OP_BACK_REF = 4,
238
 
  OP_PERIOD = 5,
239
 
#ifdef RE_ENABLE_I18N
240
 
  COMPLEX_BRACKET = 6,
241
 
  OP_UTF8_PERIOD = 7,
242
 
#endif /* RE_ENABLE_I18N */
243
 
 
244
 
  /* We define EPSILON_BIT as a macro so that OP_OPEN_SUBEXP is used
245
 
     when the debugger shows values of this enum type.  */
246
 
#define EPSILON_BIT 8
247
 
  OP_OPEN_SUBEXP = EPSILON_BIT | 0,
248
 
  OP_CLOSE_SUBEXP = EPSILON_BIT | 1,
249
 
  OP_ALT = EPSILON_BIT | 2,
250
 
  OP_DUP_ASTERISK = EPSILON_BIT | 3,
251
 
  ANCHOR = EPSILON_BIT | 4,
252
 
 
253
 
  /* Tree type, these are used only by tree. */
254
 
  CONCAT = 16,
255
 
  SUBEXP = 17,
256
 
 
257
 
  /* Token type, these are used only by token.  */
258
 
  OP_DUP_PLUS = 18,
259
 
  OP_DUP_QUESTION,
260
 
  OP_OPEN_BRACKET,
261
 
  OP_CLOSE_BRACKET,
262
 
  OP_CHARSET_RANGE,
263
 
  OP_OPEN_DUP_NUM,
264
 
  OP_CLOSE_DUP_NUM,
265
 
  OP_NON_MATCH_LIST,
266
 
  OP_OPEN_COLL_ELEM,
267
 
  OP_CLOSE_COLL_ELEM,
268
 
  OP_OPEN_EQUIV_CLASS,
269
 
  OP_CLOSE_EQUIV_CLASS,
270
 
  OP_OPEN_CHAR_CLASS,
271
 
  OP_CLOSE_CHAR_CLASS,
272
 
  OP_WORD,
273
 
  OP_NOTWORD,
274
 
  OP_SPACE,
275
 
  OP_NOTSPACE,
276
 
  BACK_SLASH
277
 
 
278
 
} re_token_type_t;
279
 
 
280
 
#ifdef RE_ENABLE_I18N
281
 
typedef struct
282
 
{
283
 
  /* Multibyte characters.  */
284
 
  wchar_t *mbchars;
285
 
 
286
 
  /* Collating symbols.  */
287
 
# ifdef _LIBC
288
 
  int32_t *coll_syms;
289
 
# endif
290
 
 
291
 
  /* Equivalence classes. */
292
 
# ifdef _LIBC
293
 
  int32_t *equiv_classes;
294
 
# endif
295
 
 
296
 
  /* Range expressions. */
297
 
# ifdef _LIBC
298
 
  uint32_t *range_starts;
299
 
  uint32_t *range_ends;
300
 
# else /* not _LIBC */
301
 
  wchar_t *range_starts;
302
 
  wchar_t *range_ends;
303
 
# endif /* not _LIBC */
304
 
 
305
 
  /* Character classes. */
306
 
  wctype_t *char_classes;
307
 
 
308
 
  /* If this character set is the non-matching list.  */
309
 
  unsigned int non_match : 1;
310
 
 
311
 
  /* # of multibyte characters.  */
312
 
  Idx nmbchars;
313
 
 
314
 
  /* # of collating symbols.  */
315
 
  Idx ncoll_syms;
316
 
 
317
 
  /* # of equivalence classes. */
318
 
  Idx nequiv_classes;
319
 
 
320
 
  /* # of range expressions. */
321
 
  Idx nranges;
322
 
 
323
 
  /* # of character classes. */
324
 
  Idx nchar_classes;
325
 
} re_charset_t;
326
 
#endif /* RE_ENABLE_I18N */
327
 
 
328
 
typedef struct
329
 
{
330
 
  union
331
 
  {
332
 
    unsigned char c;            /* for CHARACTER */
333
 
    re_bitset_ptr_t sbcset;     /* for SIMPLE_BRACKET */
334
 
#ifdef RE_ENABLE_I18N
335
 
    re_charset_t *mbcset;       /* for COMPLEX_BRACKET */
336
 
#endif /* RE_ENABLE_I18N */
337
 
    Idx idx;                    /* for BACK_REF */
338
 
    re_context_type ctx_type;   /* for ANCHOR */
339
 
  } opr;
340
 
#if __GNUC__ >= 2 && !__STRICT_ANSI__
341
 
  re_token_type_t type : 8;
342
 
#else
343
 
  re_token_type_t type;
344
 
#endif
345
 
  unsigned int constraint : 10; /* context constraint */
346
 
  unsigned int duplicated : 1;
347
 
  unsigned int opt_subexp : 1;
348
 
#ifdef RE_ENABLE_I18N
349
 
  unsigned int accept_mb : 1;
350
 
  /* These 2 bits can be moved into the union if needed (e.g. if running out
351
 
     of bits; move opr.c to opr.c.c and move the flags to opr.c.flags).  */
352
 
  unsigned int mb_partial : 1;
353
 
#endif
354
 
  unsigned int word_char : 1;
355
 
} re_token_t;
356
 
 
357
 
#define IS_EPSILON_NODE(type) ((type) & EPSILON_BIT)
358
 
 
359
 
struct re_string_t
360
 
{
361
 
  /* Indicate the raw buffer which is the original string passed as an
362
 
     argument of regexec(), re_search(), etc..  */
363
 
  const unsigned char *raw_mbs;
364
 
  /* Store the multibyte string.  In case of "case insensitive mode" like
365
 
     REG_ICASE, upper cases of the string are stored, otherwise MBS points
366
 
     the same address that RAW_MBS points.  */
367
 
  unsigned char *mbs;
368
 
#ifdef RE_ENABLE_I18N
369
 
  /* Store the wide character string which is corresponding to MBS.  */
370
 
  wint_t *wcs;
371
 
  Idx *offsets;
372
 
  mbstate_t cur_state;
373
 
#endif
374
 
  /* Index in RAW_MBS.  Each character mbs[i] corresponds to
375
 
     raw_mbs[raw_mbs_idx + i].  */
376
 
  Idx raw_mbs_idx;
377
 
  /* The length of the valid characters in the buffers.  */
378
 
  Idx valid_len;
379
 
  /* The corresponding number of bytes in raw_mbs array.  */
380
 
  Idx valid_raw_len;
381
 
  /* The length of the buffers MBS and WCS.  */
382
 
  Idx bufs_len;
383
 
  /* The index in MBS, which is updated by re_string_fetch_byte.  */
384
 
  Idx cur_idx;
385
 
  /* length of RAW_MBS array.  */
386
 
  Idx raw_len;
387
 
  /* This is RAW_LEN - RAW_MBS_IDX + VALID_LEN - VALID_RAW_LEN.  */
388
 
  Idx len;
389
 
  /* End of the buffer may be shorter than its length in the cases such
390
 
     as re_match_2, re_search_2.  Then, we use STOP for end of the buffer
391
 
     instead of LEN.  */
392
 
  Idx raw_stop;
393
 
  /* This is RAW_STOP - RAW_MBS_IDX adjusted through OFFSETS.  */
394
 
  Idx stop;
395
 
 
396
 
  /* The context of mbs[0].  We store the context independently, since
397
 
     the context of mbs[0] may be different from raw_mbs[0], which is
398
 
     the beginning of the input string.  */
399
 
  unsigned int tip_context;
400
 
  /* The translation passed as a part of an argument of re_compile_pattern.  */
401
 
  RE_TRANSLATE_TYPE trans;
402
 
  /* Copy of re_dfa_t's word_char.  */
403
 
  re_const_bitset_ptr_t word_char;
404
 
  /* true if REG_ICASE.  */
405
 
  unsigned char icase;
406
 
  unsigned char is_utf8;
407
 
  unsigned char map_notascii;
408
 
  unsigned char mbs_allocated;
409
 
  unsigned char offsets_needed;
410
 
  unsigned char newline_anchor;
411
 
  unsigned char word_ops_used;
412
 
  int mb_cur_max;
413
 
};
414
 
typedef struct re_string_t re_string_t;
415
 
 
416
 
 
417
 
struct re_dfa_t;
418
 
typedef struct re_dfa_t re_dfa_t;
419
 
 
420
 
#ifndef _LIBC
421
 
# if defined __i386__ && !defined __EMX__
422
 
#  define internal_function   __attribute ((regparm (3), stdcall))
423
 
# else
424
 
#  define internal_function
425
 
# endif
426
 
#endif
427
 
 
428
 
static reg_errcode_t re_string_realloc_buffers (re_string_t *pstr,
429
 
                                                Idx new_buf_len)
430
 
     internal_function;
431
 
#ifdef RE_ENABLE_I18N
432
 
static void build_wcs_buffer (re_string_t *pstr) internal_function;
433
 
static reg_errcode_t build_wcs_upper_buffer (re_string_t *pstr)
434
 
     internal_function;
435
 
#endif /* RE_ENABLE_I18N */
436
 
static void build_upper_buffer (re_string_t *pstr) internal_function;
437
 
static void re_string_translate_buffer (re_string_t *pstr) internal_function;
438
 
static unsigned int re_string_context_at (const re_string_t *input, Idx idx,
439
 
                                          int eflags)
440
 
     internal_function __attribute ((pure));
441
 
#define re_string_peek_byte(pstr, offset) \
442
 
  ((pstr)->mbs[(pstr)->cur_idx + offset])
443
 
#define re_string_fetch_byte(pstr) \
444
 
  ((pstr)->mbs[(pstr)->cur_idx++])
445
 
#define re_string_first_byte(pstr, idx) \
446
 
  ((idx) == (pstr)->valid_len || (pstr)->wcs[idx] != WEOF)
447
 
#define re_string_is_single_byte_char(pstr, idx) \
448
 
  ((pstr)->wcs[idx] != WEOF && ((pstr)->valid_len == (idx) + 1 \
449
 
                                || (pstr)->wcs[(idx) + 1] != WEOF))
450
 
#define re_string_eoi(pstr) ((pstr)->stop <= (pstr)->cur_idx)
451
 
#define re_string_cur_idx(pstr) ((pstr)->cur_idx)
452
 
#define re_string_get_buffer(pstr) ((pstr)->mbs)
453
 
#define re_string_length(pstr) ((pstr)->len)
454
 
#define re_string_byte_at(pstr,idx) ((pstr)->mbs[idx])
455
 
#define re_string_skip_bytes(pstr,idx) ((pstr)->cur_idx += (idx))
456
 
#define re_string_set_index(pstr,idx) ((pstr)->cur_idx = (idx))
457
 
 
458
 
#include <alloca.h>
459
 
 
460
 
#ifndef _LIBC
461
 
# if HAVE_ALLOCA
462
 
/* The OS usually guarantees only one guard page at the bottom of the stack,
463
 
   and a page size can be as small as 4096 bytes.  So we cannot safely
464
 
   allocate anything larger than 4096 bytes.  Also care for the possibility
465
 
   of a few compiler-allocated temporary stack slots.  */
466
 
#  define __libc_use_alloca(n) ((n) < 4032)
467
 
# else
468
 
/* alloca is implemented with malloc, so just use malloc.  */
469
 
#  define __libc_use_alloca(n) 0
470
 
# endif
471
 
#endif
472
 
 
473
 
#ifndef MAX
474
 
# define MAX(a,b) ((a) < (b) ? (b) : (a))
475
 
#endif
476
 
 
477
 
#define re_malloc(t,n) ((t *) malloc ((n) * sizeof (t)))
478
 
#define re_realloc(p,t,n) ((t *) realloc (p, (n) * sizeof (t)))
479
 
#define re_free(p) free (p)
480
 
 
481
 
struct bin_tree_t
482
 
{
483
 
  struct bin_tree_t *parent;
484
 
  struct bin_tree_t *left;
485
 
  struct bin_tree_t *right;
486
 
  struct bin_tree_t *first;
487
 
  struct bin_tree_t *next;
488
 
 
489
 
  re_token_t token;
490
 
 
491
 
  /* `node_idx' is the index in dfa->nodes, if `type' == 0.
492
 
     Otherwise `type' indicate the type of this node.  */
493
 
  Idx node_idx;
494
 
};
495
 
typedef struct bin_tree_t bin_tree_t;
496
 
 
497
 
#define BIN_TREE_STORAGE_SIZE \
498
 
  ((1024 - sizeof (void *)) / sizeof (bin_tree_t))
499
 
 
500
 
struct bin_tree_storage_t
501
 
{
502
 
  struct bin_tree_storage_t *next;
503
 
  bin_tree_t data[BIN_TREE_STORAGE_SIZE];
504
 
};
505
 
typedef struct bin_tree_storage_t bin_tree_storage_t;
506
 
 
507
 
#define CONTEXT_WORD 1
508
 
#define CONTEXT_NEWLINE (CONTEXT_WORD << 1)
509
 
#define CONTEXT_BEGBUF (CONTEXT_NEWLINE << 1)
510
 
#define CONTEXT_ENDBUF (CONTEXT_BEGBUF << 1)
511
 
 
512
 
#define IS_WORD_CONTEXT(c) ((c) & CONTEXT_WORD)
513
 
#define IS_NEWLINE_CONTEXT(c) ((c) & CONTEXT_NEWLINE)
514
 
#define IS_BEGBUF_CONTEXT(c) ((c) & CONTEXT_BEGBUF)
515
 
#define IS_ENDBUF_CONTEXT(c) ((c) & CONTEXT_ENDBUF)
516
 
#define IS_ORDINARY_CONTEXT(c) ((c) == 0)
517
 
 
518
 
#define IS_WORD_CHAR(ch) (isalnum (ch) || (ch) == '_')
519
 
#define IS_NEWLINE(ch) ((ch) == NEWLINE_CHAR)
520
 
#define IS_WIDE_WORD_CHAR(ch) (iswalnum (ch) || (ch) == L'_')
521
 
#define IS_WIDE_NEWLINE(ch) ((ch) == WIDE_NEWLINE_CHAR)
522
 
 
523
 
#define NOT_SATISFY_PREV_CONSTRAINT(constraint,context) \
524
 
 ((((constraint) & PREV_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \
525
 
  || ((constraint & PREV_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \
526
 
  || ((constraint & PREV_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context))\
527
 
  || ((constraint & PREV_BEGBUF_CONSTRAINT) && !IS_BEGBUF_CONTEXT (context)))
528
 
 
529
 
#define NOT_SATISFY_NEXT_CONSTRAINT(constraint,context) \
530
 
 ((((constraint) & NEXT_WORD_CONSTRAINT) && !IS_WORD_CONTEXT (context)) \
531
 
  || (((constraint) & NEXT_NOTWORD_CONSTRAINT) && IS_WORD_CONTEXT (context)) \
532
 
  || (((constraint) & NEXT_NEWLINE_CONSTRAINT) && !IS_NEWLINE_CONTEXT (context)) \
533
 
  || (((constraint) & NEXT_ENDBUF_CONSTRAINT) && !IS_ENDBUF_CONTEXT (context)))
534
 
 
535
 
struct re_dfastate_t
536
 
{
537
 
  re_hashval_t hash;
538
 
  re_node_set nodes;
539
 
  re_node_set non_eps_nodes;
540
 
  re_node_set inveclosure;
541
 
  re_node_set *entrance_nodes;
542
 
  struct re_dfastate_t **trtable, **word_trtable;
543
 
  unsigned int context : 4;
544
 
  unsigned int halt : 1;
545
 
  /* If this state can accept `multi byte'.
546
 
     Note that we refer to multibyte characters, and multi character
547
 
     collating elements as `multi byte'.  */
548
 
  unsigned int accept_mb : 1;
549
 
  /* If this state has backreference node(s).  */
550
 
  unsigned int has_backref : 1;
551
 
  unsigned int has_constraint : 1;
552
 
};
553
 
typedef struct re_dfastate_t re_dfastate_t;
554
 
 
555
 
struct re_state_table_entry
556
 
{
557
 
  Idx num;
558
 
  Idx alloc;
559
 
  re_dfastate_t **array;
560
 
};
561
 
 
562
 
/* Array type used in re_sub_match_last_t and re_sub_match_top_t.  */
563
 
 
564
 
typedef struct
565
 
{
566
 
  Idx next_idx;
567
 
  Idx alloc;
568
 
  re_dfastate_t **array;
569
 
} state_array_t;
570
 
 
571
 
/* Store information about the node NODE whose type is OP_CLOSE_SUBEXP.  */
572
 
 
573
 
typedef struct
574
 
{
575
 
  Idx node;
576
 
  Idx str_idx; /* The position NODE match at.  */
577
 
  state_array_t path;
578
 
} re_sub_match_last_t;
579
 
 
580
 
/* Store information about the node NODE whose type is OP_OPEN_SUBEXP.
581
 
   And information about the node, whose type is OP_CLOSE_SUBEXP,
582
 
   corresponding to NODE is stored in LASTS.  */
583
 
 
584
 
typedef struct
585
 
{
586
 
  Idx str_idx;
587
 
  Idx node;
588
 
  state_array_t *path;
589
 
  Idx alasts; /* Allocation size of LASTS.  */
590
 
  Idx nlasts; /* The number of LASTS.  */
591
 
  re_sub_match_last_t **lasts;
592
 
} re_sub_match_top_t;
593
 
 
594
 
struct re_backref_cache_entry
595
 
{
596
 
  Idx node;
597
 
  Idx str_idx;
598
 
  Idx subexp_from;
599
 
  Idx subexp_to;
600
 
  char more;
601
 
  char unused;
602
 
  unsigned short int eps_reachable_subexps_map;
603
 
};
604
 
 
605
 
typedef struct
606
 
{
607
 
  /* The string object corresponding to the input string.  */
608
 
  re_string_t input;
609
 
#if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
610
 
  const re_dfa_t *const dfa;
611
 
#else
612
 
  const re_dfa_t *dfa;
613
 
#endif
614
 
  /* EFLAGS of the argument of regexec.  */
615
 
  int eflags;
616
 
  /* Where the matching ends.  */
617
 
  Idx match_last;
618
 
  Idx last_node;
619
 
  /* The state log used by the matcher.  */
620
 
  re_dfastate_t **state_log;
621
 
  Idx state_log_top;
622
 
  /* Back reference cache.  */
623
 
  Idx nbkref_ents;
624
 
  Idx abkref_ents;
625
 
  struct re_backref_cache_entry *bkref_ents;
626
 
  int max_mb_elem_len;
627
 
  Idx nsub_tops;
628
 
  Idx asub_tops;
629
 
  re_sub_match_top_t **sub_tops;
630
 
} re_match_context_t;
631
 
 
632
 
typedef struct
633
 
{
634
 
  re_dfastate_t **sifted_states;
635
 
  re_dfastate_t **limited_states;
636
 
  Idx last_node;
637
 
  Idx last_str_idx;
638
 
  re_node_set limits;
639
 
} re_sift_context_t;
640
 
 
641
 
struct re_fail_stack_ent_t
642
 
{
643
 
  Idx idx;
644
 
  Idx node;
645
 
  regmatch_t *regs;
646
 
  re_node_set eps_via_nodes;
647
 
};
648
 
 
649
 
struct re_fail_stack_t
650
 
{
651
 
  Idx num;
652
 
  Idx alloc;
653
 
  struct re_fail_stack_ent_t *stack;
654
 
};
655
 
 
656
 
struct re_dfa_t
657
 
{
658
 
  re_token_t *nodes;
659
 
  size_t nodes_alloc;
660
 
  size_t nodes_len;
661
 
  Idx *nexts;
662
 
  Idx *org_indices;
663
 
  re_node_set *edests;
664
 
  re_node_set *eclosures;
665
 
  re_node_set *inveclosures;
666
 
  struct re_state_table_entry *state_table;
667
 
  re_dfastate_t *init_state;
668
 
  re_dfastate_t *init_state_word;
669
 
  re_dfastate_t *init_state_nl;
670
 
  re_dfastate_t *init_state_begbuf;
671
 
  bin_tree_t *str_tree;
672
 
  bin_tree_storage_t *str_tree_storage;
673
 
  re_bitset_ptr_t sb_char;
674
 
  int str_tree_storage_idx;
675
 
 
676
 
  /* number of subexpressions `re_nsub' is in regex_t.  */
677
 
  re_hashval_t state_hash_mask;
678
 
  Idx init_node;
679
 
  Idx nbackref; /* The number of backreference in this dfa.  */
680
 
 
681
 
  /* Bitmap expressing which backreference is used.  */
682
 
  bitset_word_t used_bkref_map;
683
 
  bitset_word_t completed_bkref_map;
684
 
 
685
 
  unsigned int has_plural_match : 1;
686
 
  /* If this dfa has "multibyte node", which is a backreference or
687
 
     a node which can accept multibyte character or multi character
688
 
     collating element.  */
689
 
  unsigned int has_mb_node : 1;
690
 
  unsigned int is_utf8 : 1;
691
 
  unsigned int map_notascii : 1;
692
 
  unsigned int word_ops_used : 1;
693
 
  int mb_cur_max;
694
 
  bitset_t word_char;
695
 
  reg_syntax_t syntax;
696
 
  Idx *subexp_map;
697
 
#ifdef DEBUG
698
 
  char* re_str;
699
 
#endif
700
 
#ifdef _LIBC
701
 
  __libc_lock_define (, lock)
702
 
#endif
703
 
};
704
 
 
705
 
#define re_node_set_init_empty(set) memset (set, '\0', sizeof (re_node_set))
706
 
#define re_node_set_remove(set,id) \
707
 
  (re_node_set_remove_at (set, re_node_set_contains (set, id) - 1))
708
 
#define re_node_set_empty(p) ((p)->nelem = 0)
709
 
#define re_node_set_free(set) re_free ((set)->elems)
710
 
 
711
 
 
712
 
typedef enum
713
 
{
714
 
  SB_CHAR,
715
 
  MB_CHAR,
716
 
  EQUIV_CLASS,
717
 
  COLL_SYM,
718
 
  CHAR_CLASS
719
 
} bracket_elem_type;
720
 
 
721
 
typedef struct
722
 
{
723
 
  bracket_elem_type type;
724
 
  union
725
 
  {
726
 
    unsigned char ch;
727
 
    unsigned char *name;
728
 
    wchar_t wch;
729
 
  } opr;
730
 
} bracket_elem_t;
731
 
 
732
 
 
733
 
/* Inline functions for bitset_t operation.  */
734
 
 
735
 
static inline void
736
 
bitset_set (bitset_t set, Idx i)
737
 
{
738
 
  set[i / BITSET_WORD_BITS] |= (bitset_word_t) 1 << i % BITSET_WORD_BITS;
739
 
}
740
 
 
741
 
static inline void
742
 
bitset_clear (bitset_t set, Idx i)
743
 
{
744
 
  set[i / BITSET_WORD_BITS] &= ~ ((bitset_word_t) 1 << i % BITSET_WORD_BITS);
745
 
}
746
 
 
747
 
static inline bool
748
 
bitset_contain (const bitset_t set, Idx i)
749
 
{
750
 
  return (set[i / BITSET_WORD_BITS] >> i % BITSET_WORD_BITS) & 1;
751
 
}
752
 
 
753
 
static inline void
754
 
bitset_empty (bitset_t set)
755
 
{
756
 
  memset (set, '\0', sizeof (bitset_t));
757
 
}
758
 
 
759
 
static inline void
760
 
bitset_set_all (bitset_t set)
761
 
{
762
 
  memset (set, -1, sizeof (bitset_word_t) * (SBC_MAX / BITSET_WORD_BITS));
763
 
  if (SBC_MAX % BITSET_WORD_BITS != 0)
764
 
    set[BITSET_WORDS - 1] =
765
 
      ((bitset_word_t) 1 << SBC_MAX % BITSET_WORD_BITS) - 1;
766
 
}
767
 
 
768
 
static inline void
769
 
bitset_copy (bitset_t dest, const bitset_t src)
770
 
{
771
 
  memcpy (dest, src, sizeof (bitset_t));
772
 
}
773
 
 
774
 
static inline void
775
 
bitset_not (bitset_t set)
776
 
{
777
 
  int bitset_i;
778
 
  for (bitset_i = 0; bitset_i < SBC_MAX / BITSET_WORD_BITS; ++bitset_i)
779
 
    set[bitset_i] = ~set[bitset_i];
780
 
  if (SBC_MAX % BITSET_WORD_BITS != 0)
781
 
    set[BITSET_WORDS - 1] =
782
 
      ((((bitset_word_t) 1 << SBC_MAX % BITSET_WORD_BITS) - 1)
783
 
       & ~set[BITSET_WORDS - 1]);
784
 
}
785
 
 
786
 
static inline void
787
 
bitset_merge (bitset_t dest, const bitset_t src)
788
 
{
789
 
  int bitset_i;
790
 
  for (bitset_i = 0; bitset_i < BITSET_WORDS; ++bitset_i)
791
 
    dest[bitset_i] |= src[bitset_i];
792
 
}
793
 
 
794
 
static inline void
795
 
bitset_mask (bitset_t dest, const bitset_t src)
796
 
{
797
 
  int bitset_i;
798
 
  for (bitset_i = 0; bitset_i < BITSET_WORDS; ++bitset_i)
799
 
    dest[bitset_i] &= src[bitset_i];
800
 
}
801
 
 
802
 
#ifdef RE_ENABLE_I18N
803
 
/* Inline functions for re_string.  */
804
 
static inline int
805
 
internal_function __attribute ((pure))
806
 
re_string_char_size_at (const re_string_t *pstr, Idx idx)
807
 
{
808
 
  int byte_idx;
809
 
  if (pstr->mb_cur_max == 1)
810
 
    return 1;
811
 
  for (byte_idx = 1; idx + byte_idx < pstr->valid_len; ++byte_idx)
812
 
    if (pstr->wcs[idx + byte_idx] != WEOF)
813
 
      break;
814
 
  return byte_idx;
815
 
}
816
 
 
817
 
static inline wint_t
818
 
internal_function __attribute ((pure))
819
 
re_string_wchar_at (const re_string_t *pstr, Idx idx)
820
 
{
821
 
  if (pstr->mb_cur_max == 1)
822
 
    return (wint_t) pstr->mbs[idx];
823
 
  return (wint_t) pstr->wcs[idx];
824
 
}
825
 
 
826
 
static int
827
 
internal_function __attribute ((pure))
828
 
re_string_elem_size_at (const re_string_t *pstr, Idx idx)
829
 
{
830
 
# ifdef _LIBC
831
 
  const unsigned char *p, *extra;
832
 
  const int32_t *table, *indirect;
833
 
  int32_t tmp;
834
 
#  include <locale/weight.h>
835
 
  uint_fast32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
836
 
 
837
 
  if (nrules != 0)
838
 
    {
839
 
      table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
840
 
      extra = (const unsigned char *)
841
 
        _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
842
 
      indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
843
 
                                                _NL_COLLATE_INDIRECTMB);
844
 
      p = pstr->mbs + idx;
845
 
      tmp = findidx (&p);
846
 
      return p - pstr->mbs - idx;
847
 
    }
848
 
  else
849
 
# endif /* _LIBC */
850
 
    return 1;
851
 
}
852
 
#endif /* RE_ENABLE_I18N */
853
 
 
854
 
#ifndef __GNUC_PREREQ
855
 
# if defined __GNUC__ && defined __GNUC_MINOR__
856
 
#  define __GNUC_PREREQ(maj, min) \
857
 
         ((__GNUC__ << 16) + __GNUC_MINOR__ >= ((maj) << 16) + (min))
858
 
# else
859
 
#  define __GNUC_PREREQ(maj, min) 0
860
 
# endif
861
 
#endif
862
 
 
863
 
#if __GNUC_PREREQ (3,4)
864
 
# undef __attribute_warn_unused_result__
865
 
# define __attribute_warn_unused_result__ \
866
 
   __attribute__ ((__warn_unused_result__))
867
 
#else
868
 
# define __attribute_warn_unused_result__ /* empty */
869
 
#endif
870
 
 
871
 
#endif /*  _REGEX_INTERNAL_H */