~ubuntu-branches/ubuntu/natty/smartmontools/natty : revision 23

1

/* Extended regular expression matching and search library.

2

3

This file is part of the GNU C Library.

4

Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.

5

6

The GNU C Library is free software; you can redistribute it and/or

7

modify it under the terms of the GNU Lesser General Public

8

License as published by the Free Software Foundation; either

9

version 2.1 of the License, or (at your option) any later version.

10

11

The GNU C Library is distributed in the hope that it will be useful,

12

but WITHOUT ANY WARRANTY; without even the implied warranty of

13

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU

14

Lesser General Public License for more details.

15

16

You should have received a copy of the GNU Lesser General Public

17

License along with the GNU C Library; if not, write to the Free

18

Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA

19

02111-1307 USA. */

20

21

static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,

22

int length, reg_syntax_t syntax);

23

static void re_compile_fastmap_iter (regex_t *bufp,

24

const re_dfastate_t *init_state,

25

char *fastmap);

26

static reg_errcode_t init_dfa (re_dfa_t *dfa, int pat_len);

27

static reg_errcode_t init_word_char (re_dfa_t *dfa);

28

#ifdef RE_ENABLE_I18N

29

static void free_charset (re_charset_t *cset);

30

#endif /* RE_ENABLE_I18N */

31

static void free_workarea_compile (regex_t *preg);

32

static reg_errcode_t create_initial_state (re_dfa_t *dfa);

33

static reg_errcode_t analyze (re_dfa_t *dfa);

34

static reg_errcode_t analyze_tree (re_dfa_t *dfa, bin_tree_t *node);

35

static void calc_first (re_dfa_t *dfa, bin_tree_t *node);

36

static void calc_next (re_dfa_t *dfa, bin_tree_t *node);

37

static void calc_epsdest (re_dfa_t *dfa, bin_tree_t *node);

38

static reg_errcode_t duplicate_node_closure (re_dfa_t *dfa, int top_org_node,

39

int top_clone_node, int root_node,

40

unsigned int constraint);

41

static reg_errcode_t duplicate_node (int *new_idx, re_dfa_t *dfa, int org_idx,

42

unsigned int constraint);

43

static int search_duplicated_node (re_dfa_t *dfa, int org_node,

44

unsigned int constraint);

45

static reg_errcode_t calc_eclosure (re_dfa_t *dfa);

46

static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,

47

int node, int root);

48

static void calc_inveclosure (re_dfa_t *dfa);

49

static int fetch_number (re_string_t *input, re_token_t *token,

50

reg_syntax_t syntax);

51

static re_token_t fetch_token (re_string_t *input, reg_syntax_t syntax);

52

static int peek_token (re_token_t *token, re_string_t *input,

53

reg_syntax_t syntax);

54

static int peek_token_bracket (re_token_t *token, re_string_t *input,

55

reg_syntax_t syntax);

56

static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,

57

reg_syntax_t syntax, reg_errcode_t *err);

58

static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,

59

re_token_t *token, reg_syntax_t syntax,

60

int nest, reg_errcode_t *err);

61

static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg,

62

re_token_t *token, reg_syntax_t syntax,

63

int nest, reg_errcode_t *err);

64

static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg,

65

re_token_t *token, reg_syntax_t syntax,

66

int nest, reg_errcode_t *err);

67

static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg,

68

re_token_t *token, reg_syntax_t syntax,

69

int nest, reg_errcode_t *err);

70

static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,

71

re_dfa_t *dfa, re_token_t *token,

72

reg_syntax_t syntax, reg_errcode_t *err);

73

static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,

74

re_token_t *token, reg_syntax_t syntax,

75

reg_errcode_t *err);

76

static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,

77

re_string_t *regexp,

78

re_token_t *token, int token_len,

79

re_dfa_t *dfa,

80

reg_syntax_t syntax);

81

static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,

82

re_string_t *regexp,

83

re_token_t *token);

84

#ifndef _LIBC

85

# ifdef RE_ENABLE_I18N

86

static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,

87

re_charset_t *mbcset, int *range_alloc,

88

bracket_elem_t *start_elem,

89

bracket_elem_t *end_elem);

90

static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,

91

re_charset_t *mbcset,

92

int *coll_sym_alloc,

93

const unsigned char *name);

94

# else /* not RE_ENABLE_I18N */

95

static reg_errcode_t build_range_exp (re_bitset_ptr_t sbcset,

96

bracket_elem_t *start_elem,

97

bracket_elem_t *end_elem);

98

static reg_errcode_t build_collating_symbol (re_bitset_ptr_t sbcset,

99

const unsigned char *name);

100

# endif /* not RE_ENABLE_I18N */

101

#endif /* not _LIBC */

102

#ifdef RE_ENABLE_I18N

103

static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,

104

re_charset_t *mbcset,

105

int *equiv_class_alloc,

106

const unsigned char *name);

107

static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset,

108

re_charset_t *mbcset,

109

int *char_class_alloc,

110

const unsigned char *class_name,

111

reg_syntax_t syntax);

112

#else /* not RE_ENABLE_I18N */

113

static reg_errcode_t build_equiv_class (re_bitset_ptr_t sbcset,

114

const unsigned char *name);

115

static reg_errcode_t build_charclass (re_bitset_ptr_t sbcset,

116

const unsigned char *class_name,

117

reg_syntax_t syntax);

118

#endif /* not RE_ENABLE_I18N */

119

static bin_tree_t *build_word_op (re_dfa_t *dfa, int not, reg_errcode_t *err);

120

static void free_bin_tree (bin_tree_t *tree);

121

static bin_tree_t *create_tree (bin_tree_t *left, bin_tree_t *right,

122

re_token_type_t type, int index);

123

static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);

124

125

/* This table gives an error message for each of the error codes listed

126

in regex.h. Obviously the order here has to be same as there.

127

POSIX doesn't require that we do anything for REG_NOERROR,

128

but why not be nice? */

129

130

const char __re_error_msgid[] attribute_hidden =

131

{

132

#define REG_NOERROR_IDX 0

133

gettext_noop ("Success") /* REG_NOERROR */

134

"\0"

135

#define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")

136

gettext_noop ("No match") /* REG_NOMATCH */

137

"\0"

138

#define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")

139

gettext_noop ("Invalid regular expression") /* REG_BADPAT */

140

"\0"

141

#define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")

142

gettext_noop ("Invalid collation character") /* REG_ECOLLATE */

143

"\0"

144

#define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")

145

gettext_noop ("Invalid character class name") /* REG_ECTYPE */

146

"\0"

147

#define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")

148

gettext_noop ("Trailing backslash") /* REG_EESCAPE */

149

"\0"

150

#define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")

151

gettext_noop ("Invalid back reference") /* REG_ESUBREG */

152

"\0"

153

#define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")

154

gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */

155

"\0"

156

#define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")

157

gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */

158

"\0"

159

#define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")

160

gettext_noop ("Unmatched \\{") /* REG_EBRACE */

161

"\0"

162

#define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")

163

gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */

164

"\0"

165

#define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")

166

gettext_noop ("Invalid range end") /* REG_ERANGE */

167

"\0"

168

#define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")

169

gettext_noop ("Memory exhausted") /* REG_ESPACE */

170

"\0"

171

#define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")

172

gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */

173

"\0"

174

#define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")

175

gettext_noop ("Premature end of regular expression") /* REG_EEND */

176

"\0"

177

#define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")

178

gettext_noop ("Regular expression too big") /* REG_ESIZE */

179

"\0"

180

#define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")

181

gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */

182

};

183

184

const size_t __re_error_msgid_idx[] attribute_hidden =

185

{

186

REG_NOERROR_IDX,

187

REG_NOMATCH_IDX,

188

REG_BADPAT_IDX,

189

REG_ECOLLATE_IDX,

190

REG_ECTYPE_IDX,

191

REG_EESCAPE_IDX,

192

REG_ESUBREG_IDX,

193

REG_EBRACK_IDX,

194

REG_EPAREN_IDX,

195

REG_EBRACE_IDX,

196

REG_BADBR_IDX,

197

REG_ERANGE_IDX,

198

REG_ESPACE_IDX,

199

REG_BADRPT_IDX,

200

REG_EEND_IDX,

201

REG_ESIZE_IDX,

202

REG_ERPAREN_IDX

203

};

204

205

/* Entry points for GNU code. */

206

207

/* re_compile_pattern is the GNU regular expression compiler: it

208

compiles PATTERN (of length LENGTH) and puts the result in BUFP.

209

Returns 0 if the pattern was valid, otherwise an error string.

210

211

Assumes the `allocated' (and perhaps `buffer') and `translate' fields

212

are set in BUFP on entry. */

213

214

const char *

215

re_compile_pattern (pattern, length, bufp)

216

const char *pattern;

217

size_t length;

218

struct re_pattern_buffer *bufp;

219

{

220

reg_errcode_t ret;

221

222

/* And GNU code determines whether or not to get register information

223

by passing null for the REGS argument to re_match, etc., not by

224

setting no_sub. */

225

bufp->no_sub = 0;

226

227

/* Match anchors at newline. */

228

bufp->newline_anchor = 1;

229

230

ret = re_compile_internal (bufp, pattern, length, re_syntax_options);

231

232

if (!ret)

233

return NULL;

234

return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);

235

}

236

#ifdef _LIBC

237

weak_alias (__re_compile_pattern, re_compile_pattern)

238

#endif

239

240

/* Set by `re_set_syntax' to the current regexp syntax to recognize. Can

241

also be assigned to arbitrarily: each pattern buffer stores its own

242

syntax, so it can be changed between regex compilations. */

243

/* This has no initializer because initialized variables in Emacs

244

become read-only after dumping. */

245

reg_syntax_t re_syntax_options;

246

247

248

/* Specify the precise syntax of regexps for compilation. This provides

249

for compatibility for various utilities which historically have

250

different, incompatible syntaxes.

251

252

The argument SYNTAX is a bit mask comprised of the various bits

253

defined in regex.h. We return the old syntax. */

254

255

reg_syntax_t

256

re_set_syntax (syntax)

257

reg_syntax_t syntax;

258

{

259

reg_syntax_t ret = re_syntax_options;

260

261

re_syntax_options = syntax;

262

return ret;

263

}

264

#ifdef _LIBC

265

weak_alias (__re_set_syntax, re_set_syntax)

266

#endif

267

268

int

269

re_compile_fastmap (bufp)

270

struct re_pattern_buffer *bufp;

271

{

272

re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;

273

char *fastmap = bufp->fastmap;

274

275

memset (fastmap, '\0', sizeof (char) * SBC_MAX);

276

re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);

277

if (dfa->init_state != dfa->init_state_word)

278

re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);

279

if (dfa->init_state != dfa->init_state_nl)

280

re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);

281

if (dfa->init_state != dfa->init_state_begbuf)

282

re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);

283

bufp->fastmap_accurate = 1;

284

return 0;

285

}

286

#ifdef _LIBC

287

weak_alias (__re_compile_fastmap, re_compile_fastmap)

288

#endif

289

290

static inline void

291

re_set_fastmap (char *fastmap, int icase, int ch)

292

{

293

fastmap[ch] = 1;

294

if (icase)

295

fastmap[tolower (ch)] = 1;

296

}

297

298

/* Helper function for re_compile_fastmap.

299

Compile fastmap for the initial_state INIT_STATE. */

300

301

static void

302

re_compile_fastmap_iter (bufp, init_state, fastmap)

303

regex_t *bufp;

304

const re_dfastate_t *init_state;

305

char *fastmap;

306

{

307

re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;

308

int node_cnt;

309

int icase = (MB_CUR_MAX == 1 && (bufp->syntax & RE_ICASE));

310

for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)

311

{

312

int node = init_state->nodes.elems[node_cnt];

313

re_token_type_t type = dfa->nodes[node].type;

314

315

if (type == CHARACTER)

316

re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);

317

else if (type == SIMPLE_BRACKET)

318

{

319

int i, j, ch;

320

for (i = 0, ch = 0; i < BITSET_UINTS; ++i)

321

for (j = 0; j < UINT_BITS; ++j, ++ch)

322

if (dfa->nodes[node].opr.sbcset[i] & (1 << j))

323

re_set_fastmap (fastmap, icase, ch);

324

}

325

#ifdef RE_ENABLE_I18N

326

else if (type == COMPLEX_BRACKET)

327

{

328

int i;

329

re_charset_t *cset = dfa->nodes[node].opr.mbcset;

330

if (cset->non_match || cset->ncoll_syms || cset->nequiv_classes

331

|| cset->nranges || cset->nchar_classes)

332

{

333

# ifdef _LIBC

334

if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0)

335

{

336

/* In this case we want to catch the bytes which are

337

the first byte of any collation elements.

338

e.g. In da_DK, we want to catch 'a' since "aa"

339

is a valid collation element, and don't catch

340

'b' since 'b' is the only collation element

341

which starts from 'b'. */

342

int j, ch;

343

const int32_t *table = (const int32_t *)

344

_NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);

345

for (i = 0, ch = 0; i < BITSET_UINTS; ++i)

346

for (j = 0; j < UINT_BITS; ++j, ++ch)

347

if (table[ch] < 0)

348

re_set_fastmap (fastmap, icase, ch);

349

}

350

# else

351

if (MB_CUR_MAX > 1)

352

for (i = 0; i < SBC_MAX; ++i)

353

if (__btowc (i) == WEOF)

354

re_set_fastmap (fastmap, icase, i);

355

# endif /* not _LIBC */

356

}

357

for (i = 0; i < cset->nmbchars; ++i)

358

{

359

char buf[256];

360

mbstate_t state;

361

memset (&state, '\0', sizeof (state));

362

__wcrtomb (buf, cset->mbchars[i], &state);

363

re_set_fastmap (fastmap, icase, *(unsigned char *) buf);

364

}

365

}

366

#endif /* RE_ENABLE_I18N */

367

else if (type == END_OF_RE || type == OP_PERIOD)

368

{

369

memset (fastmap, '\1', sizeof (char) * SBC_MAX);

370

if (type == END_OF_RE)

371

bufp->can_be_null = 1;

372

return;

373

}

374

}

375

}

376

377

/* Entry point for POSIX code. */

378

/* regcomp takes a regular expression as a string and compiles it.

379

380

PREG is a regex_t *. We do not expect any fields to be initialized,

381

since POSIX says we shouldn't. Thus, we set

382

383

`buffer' to the compiled pattern;

384

`used' to the length of the compiled pattern;

385

`syntax' to RE_SYNTAX_POSIX_EXTENDED if the

386

REG_EXTENDED bit in CFLAGS is set; otherwise, to

387

RE_SYNTAX_POSIX_BASIC;

388

`newline_anchor' to REG_NEWLINE being set in CFLAGS;

389

`fastmap' to an allocated space for the fastmap;

390

`fastmap_accurate' to zero;

391

`re_nsub' to the number of subexpressions in PATTERN.

392

393

PATTERN is the address of the pattern string.

394

395

CFLAGS is a series of bits which affect compilation.

396

397

If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we

398

use POSIX basic syntax.

399

400

If REG_NEWLINE is set, then . and [^...] don't match newline.

401

Also, regexec will try a match beginning after every newline.

402

403

If REG_ICASE is set, then we considers upper- and lowercase

404

versions of letters to be equivalent when matching.

405

406

If REG_NOSUB is set, then when PREG is passed to regexec, that

407

routine will report only success or failure, and nothing about the

408

registers.

409

410

It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for

411

the return codes and their meanings.) */

412

413

int

414

regcomp (preg, pattern, cflags)

415

regex_t *__restrict preg;

416

const char *__restrict pattern;

417

int cflags;

418

{

419

reg_errcode_t ret;

420

reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED

421

: RE_SYNTAX_POSIX_BASIC);

422

423

preg->buffer = NULL;

424

preg->allocated = 0;

425

preg->used = 0;

426

427

/* Try to allocate space for the fastmap. */

428

preg->fastmap = re_malloc (char, SBC_MAX);

429

if (BE (preg->fastmap == NULL, 0))

430

return REG_ESPACE;

431

432

syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;

433

434

/* If REG_NEWLINE is set, newlines are treated differently. */

435

if (cflags & REG_NEWLINE)

436

{ /* REG_NEWLINE implies neither . nor [^...] match newline. */

437

syntax &= ~RE_DOT_NEWLINE;

438

syntax |= RE_HAT_LISTS_NOT_NEWLINE;

439

/* It also changes the matching behavior. */

440

preg->newline_anchor = 1;

441

}

442

else

443

preg->newline_anchor = 0;

444

preg->no_sub = !!(cflags & REG_NOSUB);

445

preg->translate = NULL;

446

447

ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);

448

449

/* POSIX doesn't distinguish between an unmatched open-group and an

450

unmatched close-group: both are REG_EPAREN. */

451

if (ret == REG_ERPAREN)

452

ret = REG_EPAREN;

453

454

/* We have already checked preg->fastmap != NULL. */

455

if (BE (ret == REG_NOERROR, 1))

456

/* Compute the fastmap now, since regexec cannot modify the pattern

457

buffer. This function nevers fails in this implementation. */

458

(void) re_compile_fastmap (preg);

459

else

460

{

461

/* Some error occurred while compiling the expression. */

462

re_free (preg->fastmap);

463

preg->fastmap = NULL;

464

}

465

466

return (int) ret;

467

}

468

#ifdef _LIBC

469

weak_alias (__regcomp, regcomp)

470

#endif

471

472

/* Returns a message corresponding to an error code, ERRCODE, returned

473

from either regcomp or regexec. We don't use PREG here. */

474

475

size_t

476

regerror (errcode, preg, errbuf, errbuf_size)

477

int errcode;

478

const regex_t *preg;

479

char *errbuf;

480

size_t errbuf_size;

481

{

482

const char *msg;

483

size_t msg_size;

484

485

if (BE (errcode < 0

486

|| errcode >= (int) (sizeof (__re_error_msgid_idx)

487

/ sizeof (__re_error_msgid_idx[0])), 0))

488

/* Only error codes returned by the rest of the code should be passed

489

to this routine. If we are given anything else, or if other regex

490

code generates an invalid error code, then the program has a bug.

491

Dump core so we can fix it. */

492

abort ();

493

494

msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);

495

496

msg_size = strlen (msg) + 1; /* Includes the null. */

497

498

if (BE (errbuf_size != 0, 1))

499

{

500

if (BE (msg_size > errbuf_size, 0))

501

{

502

#if defined HAVE_MEMPCPY || defined _LIBC

503

*((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';

504

#else

505

memcpy (errbuf, msg, errbuf_size - 1);

506

errbuf[errbuf_size - 1] = 0;

507

#endif

508

}

509

else

510

memcpy (errbuf, msg, msg_size);

511

}

512

513

return msg_size;

514

}

515

#ifdef _LIBC

516

weak_alias (__regerror, regerror)

517

#endif

518

519

520

static void

521

free_dfa_content (re_dfa_t *dfa)

522

{

523

int i, j;

524

525

re_free (dfa->subexps);

526

527

for (i = 0; i < dfa->nodes_len; ++i)

528

{

529

re_token_t *node = dfa->nodes + i;

530

#ifdef RE_ENABLE_I18N

531

if (node->type == COMPLEX_BRACKET && node->duplicated == 0)

532

free_charset (node->opr.mbcset);

533

else

534

#endif /* RE_ENABLE_I18N */

535

if (node->type == SIMPLE_BRACKET && node->duplicated == 0)

536

re_free (node->opr.sbcset);

537

}

538

re_free (dfa->nexts);

539

for (i = 0; i < dfa->nodes_len; ++i)

540

{

541

if (dfa->eclosures != NULL)

542

re_node_set_free (dfa->eclosures + i);

543

if (dfa->inveclosures != NULL)

544

re_node_set_free (dfa->inveclosures + i);

545

if (dfa->edests != NULL)

546

re_node_set_free (dfa->edests + i);

547

}

548

re_free (dfa->edests);

549

re_free (dfa->eclosures);

550

re_free (dfa->inveclosures);

551

re_free (dfa->nodes);

552

553

for (i = 0; i <= dfa->state_hash_mask; ++i)

554

{

555

struct re_state_table_entry *entry = dfa->state_table + i;

556

for (j = 0; j < entry->num; ++j)

557

{

558

re_dfastate_t *state = entry->array[j];

559

free_state (state);

560

}

561

re_free (entry->array);

562

}

563

re_free (dfa->state_table);

564

565

if (dfa->word_char != NULL)

566

re_free (dfa->word_char);

567

#ifdef DEBUG

568

re_free (dfa->re_str);

569

#endif

570

571

re_free (dfa);

572

}

573

574

575

/* Free dynamically allocated space used by PREG. */

576

577

void

578

regfree (preg)

579

regex_t *preg;

580

{

581

re_dfa_t *dfa = (re_dfa_t *) preg->buffer;

582

if (BE (dfa != NULL, 1))

583

free_dfa_content (dfa);

584

585

re_free (preg->fastmap);

586

}

587

#ifdef _LIBC

588

weak_alias (__regfree, regfree)

589

#endif

590

591

/* Entry points compatible with 4.2 BSD regex library. We don't define

592

them unless specifically requested. */

593

594

#if defined _REGEX_RE_COMP || defined _LIBC

595

596

/* BSD has one and only one pattern buffer. */

597

static struct re_pattern_buffer re_comp_buf;

598

599

char *

600

# ifdef _LIBC

601

/* Make these definitions weak in libc, so POSIX programs can redefine

602

these names if they don't use our functions, and still use

603

regcomp/regexec above without link errors. */

604

weak_function

605

# endif

606

re_comp (s)

607

const char *s;

608

{

609

reg_errcode_t ret;

610

char *fastmap;

611

612

if (!s)

613

{

614

if (!re_comp_buf.buffer)

615

return gettext ("No previous regular expression");

616

return 0;

617

}

618

619

if (re_comp_buf.buffer)

620

{

621

fastmap = re_comp_buf.fastmap;

622

re_comp_buf.fastmap = NULL;

623

__regfree (&re_comp_buf);

624

memset (&re_comp_buf, '\0', sizeof (re_comp_buf));

625

re_comp_buf.fastmap = fastmap;

626

}

627

628

if (re_comp_buf.fastmap == NULL)

629

{

630

re_comp_buf.fastmap = (char *) malloc (SBC_MAX);

631

if (re_comp_buf.fastmap == NULL)

632

return (char *) gettext (__re_error_msgid

633

+ __re_error_msgid_idx[(int) REG_ESPACE]);

634

}

635

636

/* Since `re_exec' always passes NULL for the `regs' argument, we

637

don't need to initialize the pattern buffer fields which affect it. */

638

639

/* Match anchors at newlines. */

640

re_comp_buf.newline_anchor = 1;

641

642

ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);

643

644

if (!ret)

645

return NULL;

646

647

/* Yes, we're discarding `const' here if !HAVE_LIBINTL. */

648

return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);

649

}

650

651

#ifdef _LIBC

652

libc_freeres_fn (free_mem)

653

{

654

__regfree (&re_comp_buf);

655

}

656

#endif

657

658

#endif /* _REGEX_RE_COMP */

659

660

/* Internal entry point.

661

Compile the regular expression PATTERN, whose length is LENGTH.

662

SYNTAX indicate regular expression's syntax. */

663

664

static reg_errcode_t

665

re_compile_internal (preg, pattern, length, syntax)

666

regex_t *preg;

667

const char * pattern;

668

int length;

669

reg_syntax_t syntax;

670

{

671

reg_errcode_t err = REG_NOERROR;

672

re_dfa_t *dfa;

673

re_string_t regexp;

674

675

/* Initialize the pattern buffer. */

676

preg->fastmap_accurate = 0;

677

preg->syntax = syntax;

678

preg->not_bol = preg->not_eol = 0;

679

preg->used = 0;

680

preg->re_nsub = 0;

681

preg->can_be_null = 0;

682

preg->regs_allocated = REGS_UNALLOCATED;

683

684

/* Initialize the dfa. */

685

dfa = (re_dfa_t *) preg->buffer;

686

if (preg->allocated < sizeof (re_dfa_t))

687

{

688

/* If zero allocated, but buffer is non-null, try to realloc

689

enough space. This loses if buffer's address is bogus, but

690

that is the user's responsibility. If ->buffer is NULL this

691

is a simple allocation. */

692

dfa = re_realloc (preg->buffer, re_dfa_t, 1);

693

if (dfa == NULL)

694

return REG_ESPACE;

695

preg->allocated = sizeof (re_dfa_t);

696

}

697

preg->buffer = (unsigned char *) dfa;

698

preg->used = sizeof (re_dfa_t);

699

700

err = init_dfa (dfa, length);

701

if (BE (err != REG_NOERROR, 0))

702

{

703

re_free (dfa);

704

preg->buffer = NULL;

705

preg->allocated = 0;

706

return err;

707

}

708

#ifdef DEBUG

709

dfa->re_str = re_malloc (char, length + 1);

710

strncpy (dfa->re_str, pattern, length + 1);

711

#endif

712

713

err = re_string_construct (&regexp, pattern, length, preg->translate,

714

syntax & RE_ICASE);

715

if (BE (err != REG_NOERROR, 0))

716

{

717

re_free (dfa);

718

preg->buffer = NULL;

719

preg->allocated = 0;

720

return err;

721

}

722

723

/* Parse the regular expression, and build a structure tree. */

724

preg->re_nsub = 0;

725

dfa->str_tree = parse (&regexp, preg, syntax, &err);

726

if (BE (dfa->str_tree == NULL, 0))

727

goto re_compile_internal_free_return;

728

729

/* Analyze the tree and collect information which is necessary to

730

create the dfa. */

731

err = analyze (dfa);

732

if (BE (err != REG_NOERROR, 0))

733

goto re_compile_internal_free_return;

734

735

/* Then create the initial state of the dfa. */

736

err = create_initial_state (dfa);

737

738

/* Release work areas. */

739

free_workarea_compile (preg);

740

re_string_destruct (&regexp);

741

742

if (BE (err != REG_NOERROR, 0))

743

{

744

re_compile_internal_free_return:

745

free_dfa_content (dfa);

746

preg->buffer = NULL;

747

preg->allocated = 0;

748

}

749

750

return err;

751

}

752

753

/* Initialize DFA. We use the length of the regular expression PAT_LEN

754

as the initial length of some arrays. */

755

756

static reg_errcode_t

757

init_dfa (dfa, pat_len)

758

re_dfa_t *dfa;

759

int pat_len;

760

{

761

int table_size;

762

763

memset (dfa, '\0', sizeof (re_dfa_t));

764

765

dfa->nodes_alloc = pat_len + 1;

766

dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);

767

768

dfa->states_alloc = pat_len + 1;

769

770

/* table_size = 2 ^ ceil(log pat_len) */

771

for (table_size = 1; table_size > 0; table_size <<= 1)

772

if (table_size > pat_len)

773

break;

774

775

dfa->state_table = calloc (sizeof (struct re_state_table_entry), table_size);

776

dfa->state_hash_mask = table_size - 1;

777

778

dfa->subexps_alloc = 1;

779

dfa->subexps = re_malloc (re_subexp_t, dfa->subexps_alloc);

780

dfa->word_char = NULL;

781

782

if (BE (dfa->nodes == NULL || dfa->state_table == NULL

783

|| dfa->subexps == NULL, 0))

784

{

785

/* We don't bother to free anything which was allocated. Very

786

soon the process will go down anyway. */

787

dfa->subexps = NULL;

788

dfa->state_table = NULL;

789

dfa->nodes = NULL;

790

return REG_ESPACE;

791

}

792

return REG_NOERROR;

793

}

794

795

/* Initialize WORD_CHAR table, which indicate which character is

796

"word". In this case "word" means that it is the word construction

797

character used by some operators like "\<", "\>", etc. */

798

799

static reg_errcode_t

800

init_word_char (dfa)

801

re_dfa_t *dfa;

802

{

803

int i, j, ch;

804

dfa->word_char = (re_bitset_ptr_t) calloc (sizeof (bitset), 1);

805

if (BE (dfa->word_char == NULL, 0))

806

return REG_ESPACE;

807

for (i = 0, ch = 0; i < BITSET_UINTS; ++i)

808

for (j = 0; j < UINT_BITS; ++j, ++ch)

809

if (isalnum (ch) || ch == '_')

810

dfa->word_char[i] |= 1 << j;

811

return REG_NOERROR;

812

}

813

814

/* Free the work area which are only used while compiling. */

815

816

static void

817

free_workarea_compile (preg)

818

regex_t *preg;

819

{

820

re_dfa_t *dfa = (re_dfa_t *) preg->buffer;

821

free_bin_tree (dfa->str_tree);

822

dfa->str_tree = NULL;

823

re_free (dfa->org_indices);

824

dfa->org_indices = NULL;

825

}

826

827

/* Create initial states for all contexts. */

828

829

static reg_errcode_t

830

create_initial_state (dfa)

831

re_dfa_t *dfa;

832

{

833

int first, i;

834

reg_errcode_t err;

835

re_node_set init_nodes;

836

837

/* Initial states have the epsilon closure of the node which is

838

the first node of the regular expression. */

839

first = dfa->str_tree->first;

840

dfa->init_node = first;

841

err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);

842

if (BE (err != REG_NOERROR, 0))

843

return err;

844

845

/* The back-references which are in initial states can epsilon transit,

846

since in this case all of the subexpressions can be null.

847

Then we add epsilon closures of the nodes which are the next nodes of

848

the back-references. */

849

if (dfa->nbackref > 0)

850

for (i = 0; i < init_nodes.nelem; ++i)

851

{

852

int node_idx = init_nodes.elems[i];

853

re_token_type_t type = dfa->nodes[node_idx].type;

854

855

int clexp_idx;

856

if (type != OP_BACK_REF)

857

continue;

858

for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)

859

{

860

re_token_t *clexp_node;

861

clexp_node = dfa->nodes + init_nodes.elems[clexp_idx];

862

if (clexp_node->type == OP_CLOSE_SUBEXP

863

&& clexp_node->opr.idx + 1 == dfa->nodes[node_idx].opr.idx)

864

break;

865

}

866

if (clexp_idx == init_nodes.nelem)

867

continue;

868

869

if (type == OP_BACK_REF)

870

{

871

int dest_idx = dfa->edests[node_idx].elems[0];

872

if (!re_node_set_contains (&init_nodes, dest_idx))

873

{

874

re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);

875

i = 0;

876

}

877

}

878

}

879

880

/* It must be the first time to invoke acquire_state. */

881

dfa->init_state = re_acquire_state_context (&err, dfa, &init_nodes, 0);

882

/* We don't check ERR here, since the initial state must not be NULL. */

883

if (BE (dfa->init_state == NULL, 0))

884

return err;

885

if (dfa->init_state->has_constraint)

886

{

887

dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,

888

CONTEXT_WORD);

889

dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,

890

CONTEXT_NEWLINE);

891

dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,

892

&init_nodes,

893

CONTEXT_NEWLINE

894

| CONTEXT_BEGBUF);

895

if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL

896

|| dfa->init_state_begbuf == NULL, 0))

897

return err;

898

}

899

else

900

dfa->init_state_word = dfa->init_state_nl

901

= dfa->init_state_begbuf = dfa->init_state;

902

903

re_node_set_free (&init_nodes);

904

return REG_NOERROR;

905

}

906

907

/* Analyze the structure tree, and calculate "first", "next", "edest",

908

"eclosure", and "inveclosure". */

909

910

static reg_errcode_t

911

analyze (dfa)

912

re_dfa_t *dfa;

913

{

914

int i;

915

reg_errcode_t ret;

916

917

/* Allocate arrays. */

918

dfa->nexts = re_malloc (int, dfa->nodes_alloc);

919

dfa->org_indices = re_malloc (int, dfa->nodes_alloc);

920

dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);

921

dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);

922

dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_alloc);

923

if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL

924

|| dfa->eclosures == NULL || dfa->inveclosures == NULL, 0))

925

return REG_ESPACE;

926

/* Initialize them. */

927

for (i = 0; i < dfa->nodes_len; ++i)

928

{

929

dfa->nexts[i] = -1;

930

re_node_set_init_empty (dfa->edests + i);

931

re_node_set_init_empty (dfa->eclosures + i);

932

re_node_set_init_empty (dfa->inveclosures + i);

933

}

934

935

ret = analyze_tree (dfa, dfa->str_tree);

936

if (BE (ret == REG_NOERROR, 1))

937

{

938

ret = calc_eclosure (dfa);

939

if (ret == REG_NOERROR)

940

calc_inveclosure (dfa);

941

}

942

return ret;

943

}

944

945

/* Helper functions for analyze.

946

This function calculate "first", "next", and "edest" for the subtree

947

whose root is NODE. */

948

949

static reg_errcode_t

950

analyze_tree (dfa, node)

951

re_dfa_t *dfa;

952

bin_tree_t *node;

953

{

954

reg_errcode_t ret;

955

if (node->first == -1)

956

calc_first (dfa, node);

957

if (node->next == -1)

958

calc_next (dfa, node);

959

if (node->eclosure.nelem == 0)

960

calc_epsdest (dfa, node);

961

/* Calculate "first" etc. for the left child. */

962

if (node->left != NULL)

963

{

964

ret = analyze_tree (dfa, node->left);

965

if (BE (ret != REG_NOERROR, 0))

966

return ret;

967

}

968

/* Calculate "first" etc. for the right child. */

969

if (node->right != NULL)

970

{

971

ret = analyze_tree (dfa, node->right);

972

if (BE (ret != REG_NOERROR, 0))

973

return ret;

974

}

975

return REG_NOERROR;

976

}

977

978

/* Calculate "first" for the node NODE. */

979

static void

980

calc_first (dfa, node)

981

re_dfa_t *dfa;

982

bin_tree_t *node;

983

{

984

int idx, type;

985

idx = node->node_idx;

986

type = (node->type == 0) ? dfa->nodes[idx].type : node->type;

987

988

switch (type)

989

{

990

#ifdef DEBUG

991

case OP_OPEN_BRACKET:

992

case OP_CLOSE_BRACKET:

993

case OP_OPEN_DUP_NUM:

994

case OP_CLOSE_DUP_NUM:

995

case OP_NON_MATCH_LIST:

996

case OP_OPEN_COLL_ELEM:

997

case OP_CLOSE_COLL_ELEM:

998

case OP_OPEN_EQUIV_CLASS:

999

case OP_CLOSE_EQUIV_CLASS:

1000

case OP_OPEN_CHAR_CLASS:

1001

case OP_CLOSE_CHAR_CLASS:

1002

/* These must not be appeared here. */

1003

assert (0);

1004

#endif

1005

case END_OF_RE:

1006

case CHARACTER:

1007

case OP_PERIOD:

1008

case OP_DUP_ASTERISK:

1009

case OP_DUP_QUESTION:

1010

#ifdef RE_ENABLE_I18N

1011

case COMPLEX_BRACKET:

1012

#endif /* RE_ENABLE_I18N */

1013

case SIMPLE_BRACKET:

1014

case OP_BACK_REF:

1015

case ANCHOR:

1016

case OP_OPEN_SUBEXP:

1017

case OP_CLOSE_SUBEXP:

1018

node->first = idx;

1019

break;

1020

case OP_DUP_PLUS:

1021

#ifdef DEBUG

1022

assert (node->left != NULL);

1023

#endif

1024

if (node->left->first == -1)

1025

calc_first (dfa, node->left);

1026

node->first = node->left->first;

1027

break;

1028

case OP_ALT:

1029

node->first = idx;

1030

break;

1031

/* else fall through */

1032

default:

1033

#ifdef DEBUG

1034

assert (node->left != NULL);

1035

#endif

1036

if (node->left->first == -1)

1037

calc_first (dfa, node->left);

1038

node->first = node->left->first;

1039

break;

1040

}

1041

}

1042

1043

/* Calculate "next" for the node NODE. */

1044

1045

static void

1046

calc_next (dfa, node)

1047

re_dfa_t *dfa;

1048

bin_tree_t *node;

1049

{

1050

int idx, type;

1051

bin_tree_t *parent = node->parent;

1052

if (parent == NULL)

1053

{

1054

node->next = -1;

1055

idx = node->node_idx;

1056

if (node->type == 0)

1057

dfa->nexts[idx] = node->next;

1058

return;

1059

}

1060

1061

idx = parent->node_idx;

1062

type = (parent->type == 0) ? dfa->nodes[idx].type : parent->type;

1063

1064

switch (type)

1065

{

1066

case OP_DUP_ASTERISK:

1067

case OP_DUP_PLUS:

1068

node->next = idx;

1069

break;

1070

case CONCAT:

1071

if (parent->left == node)

1072

{

1073

if (parent->right->first == -1)

1074

calc_first (dfa, parent->right);

1075

node->next = parent->right->first;

1076

break;

1077

}

1078

/* else fall through */

1079

default:

1080

if (parent->next == -1)

1081

calc_next (dfa, parent);

1082

node->next = parent->next;

1083

break;

1084

}

1085

idx = node->node_idx;

1086

if (node->type == 0)

1087

dfa->nexts[idx] = node->next;

1088

}

1089

1090

/* Calculate "edest" for the node NODE. */

1091

1092

static void

1093

calc_epsdest (dfa, node)

1094

re_dfa_t *dfa;

1095

bin_tree_t *node;

1096

{

1097

int idx;

1098

idx = node->node_idx;

1099

if (node->type == 0)

1100

{

1101

if (dfa->nodes[idx].type == OP_DUP_ASTERISK

1102

|| dfa->nodes[idx].type == OP_DUP_PLUS

1103

|| dfa->nodes[idx].type == OP_DUP_QUESTION)

1104

{

1105

if (node->left->first == -1)

1106

calc_first (dfa, node->left);

1107

if (node->next == -1)

1108

calc_next (dfa, node);

1109

re_node_set_init_2 (dfa->edests + idx, node->left->first,

1110

node->next);

1111

}

1112

else if (dfa->nodes[idx].type == OP_ALT)

1113

{

1114

int left, right;

1115

if (node->left != NULL)

1116

{

1117

if (node->left->first == -1)

1118

calc_first (dfa, node->left);

1119

left = node->left->first;

1120

}

1121

else

1122

{

1123

if (node->next == -1)

1124

calc_next (dfa, node);

1125

left = node->next;

1126

}

1127

if (node->right != NULL)

1128

{

1129

if (node->right->first == -1)

1130

calc_first (dfa, node->right);

1131

right = node->right->first;

1132

}

1133

else

1134

{

1135

if (node->next == -1)

1136

calc_next (dfa, node);

1137

right = node->next;

1138

}

1139

re_node_set_init_2 (dfa->edests + idx, left, right);

1140

}

1141

else if (dfa->nodes[idx].type == ANCHOR

1142

|| dfa->nodes[idx].type == OP_OPEN_SUBEXP

1143

|| dfa->nodes[idx].type == OP_CLOSE_SUBEXP

1144

|| dfa->nodes[idx].type == OP_BACK_REF)

1145

re_node_set_init_1 (dfa->edests + idx, node->next);

1146

}

1147

}

1148

1149

/* Duplicate the epsilon closure of the node ROOT_NODE.

1150

Note that duplicated nodes have constraint INIT_CONSTRAINT in addition

1151

to their own constraint. */

1152

1153

static reg_errcode_t

1154

duplicate_node_closure (dfa, top_org_node, top_clone_node, root_node,

1155

init_constraint)

1156

re_dfa_t *dfa;

1157

int top_org_node, top_clone_node, root_node;

1158

unsigned int init_constraint;

1159

{

1160

reg_errcode_t err;

1161

int org_node, clone_node, ret;

1162

unsigned int constraint = init_constraint;

1163

for (org_node = top_org_node, clone_node = top_clone_node;;)

1164

{

1165

int org_dest, clone_dest;

1166

if (dfa->nodes[org_node].type == OP_BACK_REF)

1167

{

1168

/* If the back reference epsilon-transit, its destination must

1169

also have the constraint. Then duplicate the epsilon closure

1170

of the destination of the back reference, and store it in

1171

edests of the back reference. */

1172

org_dest = dfa->nexts[org_node];

1173

re_node_set_empty (dfa->edests + clone_node);

1174

err = duplicate_node (&clone_dest, dfa, org_dest, constraint);

1175

if (BE (err != REG_NOERROR, 0))

1176

return err;

1177

dfa->nexts[clone_node] = dfa->nexts[org_node];

1178

ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);

1179

if (BE (ret < 0, 0))

1180

return REG_ESPACE;

1181

}

1182

else if (dfa->edests[org_node].nelem == 0)

1183

{

1184

/* In case of the node can't epsilon-transit, don't duplicate the

1185

destination and store the original destination as the

1186

destination of the node. */

1187

dfa->nexts[clone_node] = dfa->nexts[org_node];

1188

break;

1189

}

1190

else if (dfa->edests[org_node].nelem == 1)

1191

{

1192

/* In case of the node can epsilon-transit, and it has only one

1193

destination. */

1194

org_dest = dfa->edests[org_node].elems[0];

1195

re_node_set_empty (dfa->edests + clone_node);

1196

if (dfa->nodes[org_node].type == ANCHOR)

1197

{

1198

/* In case of the node has another constraint, append it. */

1199

if (org_node == root_node && clone_node != org_node)

1200

{

1201

/* ...but if the node is root_node itself, it means the

1202

epsilon closure have a loop, then tie it to the

1203

destination of the root_node. */

1204

ret = re_node_set_insert (dfa->edests + clone_node,

1205

org_dest);

1206

if (BE (ret < 0, 0))

1207

return REG_ESPACE;

1208

break;

1209

}

1210

constraint |= dfa->nodes[org_node].opr.ctx_type;

1211

}

1212

err = duplicate_node (&clone_dest, dfa, org_dest, constraint);

1213

if (BE (err != REG_NOERROR, 0))

1214

return err;

1215

ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);

1216

if (BE (ret < 0, 0))

1217

return REG_ESPACE;

1218

}

1219

else /* dfa->edests[org_node].nelem == 2 */

1220

{

1221

/* In case of the node can epsilon-transit, and it has two

1222

destinations. E.g. '|', '*', '+', '?'. */

1223

org_dest = dfa->edests[org_node].elems[0];

1224

re_node_set_empty (dfa->edests + clone_node);

1225

/* Search for a duplicated node which satisfies the constraint. */

1226

clone_dest = search_duplicated_node (dfa, org_dest, constraint);

1227

if (clone_dest == -1)

1228

{

1229

/* There are no such a duplicated node, create a new one. */

1230

err = duplicate_node (&clone_dest, dfa, org_dest, constraint);

1231

if (BE (err != REG_NOERROR, 0))

1232

return err;

1233

ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);

1234

if (BE (ret < 0, 0))

1235

return REG_ESPACE;

1236

err = duplicate_node_closure (dfa, org_dest, clone_dest,

1237

root_node, constraint);

1238

if (BE (err != REG_NOERROR, 0))

1239

return err;

1240

}

1241

else

1242

{

1243

/* There are a duplicated node which satisfy the constraint,

1244

use it to avoid infinite loop. */

1245

ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);

1246

if (BE (ret < 0, 0))

1247

return REG_ESPACE;

1248

}

1249

1250

org_dest = dfa->edests[org_node].elems[1];

1251

err = duplicate_node (&clone_dest, dfa, org_dest, constraint);

1252

if (BE (err != REG_NOERROR, 0))

1253

return err;

1254

ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);

1255

if (BE (ret < 0, 0))

1256

return REG_ESPACE;

1257

}

1258

org_node = org_dest;

1259

clone_node = clone_dest;

1260

}

1261

return REG_NOERROR;

1262

}

1263

1264

/* Search for a node which is duplicated from the node ORG_NODE, and

1265

satisfies the constraint CONSTRAINT. */

1266

1267

static int

1268

search_duplicated_node (dfa, org_node, constraint)

1269

re_dfa_t *dfa;

1270

int org_node;

1271

unsigned int constraint;

1272

{

1273

int idx;

1274

for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)

1275

{

1276

if (org_node == dfa->org_indices[idx]

1277

&& constraint == dfa->nodes[idx].constraint)

1278

return idx; /* Found. */

1279

}

1280

return -1; /* Not found. */

1281

}

1282

1283

/* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.

1284

The new index will be stored in NEW_IDX and return REG_NOERROR if succeeded,

1285

otherwise return the error code. */

1286

1287

static reg_errcode_t

1288

duplicate_node (new_idx, dfa, org_idx, constraint)

1289

re_dfa_t *dfa;

1290

int *new_idx, org_idx;

1291

unsigned int constraint;

1292

{

1293

re_token_t dup;

1294

int dup_idx;

1295

1296

dup = dfa->nodes[org_idx];

1297

dup_idx = re_dfa_add_node (dfa, dup, 1);

1298

if (BE (dup_idx == -1, 0))

1299

return REG_ESPACE;

1300

dfa->nodes[dup_idx].constraint = constraint;

1301

if (dfa->nodes[org_idx].type == ANCHOR)

1302

dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;

1303

dfa->nodes[dup_idx].duplicated = 1;

1304

re_node_set_init_empty (dfa->edests + dup_idx);

1305

re_node_set_init_empty (dfa->eclosures + dup_idx);

1306

re_node_set_init_empty (dfa->inveclosures + dup_idx);

1307

1308

/* Store the index of the original node. */

1309

dfa->org_indices[dup_idx] = org_idx;

1310

*new_idx = dup_idx;

1311

return REG_NOERROR;

1312

}

1313

1314

static void

1315

calc_inveclosure (dfa)

1316

re_dfa_t *dfa;

1317

{

1318

int src, idx, dest;

1319

for (src = 0; src < dfa->nodes_len; ++src)

1320

{

1321

for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)

1322

{

1323

dest = dfa->eclosures[src].elems[idx];

1324

re_node_set_insert (dfa->inveclosures + dest, src);

1325

}

1326

}

1327

}

1328

1329

/* Calculate "eclosure" for all the node in DFA. */

1330

1331

static reg_errcode_t

1332

calc_eclosure (dfa)

1333

re_dfa_t *dfa;

1334

{

1335

int node_idx, incomplete;

1336

#ifdef DEBUG

1337

assert (dfa->nodes_len > 0);

1338

#endif

1339

incomplete = 0;

1340

/* For each nodes, calculate epsilon closure. */

1341

for (node_idx = 0; ; ++node_idx)

1342

{

1343

reg_errcode_t err;

1344

re_node_set eclosure_elem;

1345

if (node_idx == dfa->nodes_len)

1346

{

1347

if (!incomplete)

1348

break;

1349

incomplete = 0;

1350

node_idx = 0;

1351

}

1352

1353

#ifdef DEBUG

1354

assert (dfa->eclosures[node_idx].nelem != -1);

1355

#endif

1356

/* If we have already calculated, skip it. */

1357

if (dfa->eclosures[node_idx].nelem != 0)

1358

continue;

1359

/* Calculate epsilon closure of `node_idx'. */

1360

err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, 1);

1361

if (BE (err != REG_NOERROR, 0))

1362

return err;

1363

1364

if (dfa->eclosures[node_idx].nelem == 0)

1365

{

1366

incomplete = 1;

1367

re_node_set_free (&eclosure_elem);

1368

}

1369

}

1370

return REG_NOERROR;

1371

}

1372

1373

/* Calculate epsilon closure of NODE. */

1374

1375

static reg_errcode_t

1376

calc_eclosure_iter (new_set, dfa, node, root)

1377

re_node_set *new_set;

1378

re_dfa_t *dfa;

1379

int node, root;

1380

{

1381

reg_errcode_t err;

1382

unsigned int constraint;

1383

int i, incomplete;

1384

re_node_set eclosure;

1385

incomplete = 0;

1386

err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);

1387

if (BE (err != REG_NOERROR, 0))

1388

return err;

1389

1390

/* This indicates that we are calculating this node now.

1391

We reference this value to avoid infinite loop. */

1392

dfa->eclosures[node].nelem = -1;

1393

1394

constraint = ((dfa->nodes[node].type == ANCHOR)

1395

? dfa->nodes[node].opr.ctx_type : 0);

1396

/* If the current node has constraints, duplicate all nodes.

1397

Since they must inherit the constraints. */

1398

if (constraint && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)

1399

{

1400

int org_node, cur_node;

1401

org_node = cur_node = node;

1402

err = duplicate_node_closure (dfa, node, node, node, constraint);

1403

if (BE (err != REG_NOERROR, 0))

1404

return err;

1405

}

1406

1407

/* Expand each epsilon destination nodes. */

1408

if (IS_EPSILON_NODE(dfa->nodes[node].type))

1409

for (i = 0; i < dfa->edests[node].nelem; ++i)

1410

{

1411

re_node_set eclosure_elem;

1412

int edest = dfa->edests[node].elems[i];

1413

/* If calculating the epsilon closure of `edest' is in progress,

1414

return intermediate result. */

1415

if (dfa->eclosures[edest].nelem == -1)

1416

{

1417

incomplete = 1;

1418

continue;

1419

}

1420

/* If we haven't calculated the epsilon closure of `edest' yet,

1421

calculate now. Otherwise use calculated epsilon closure. */

1422

if (dfa->eclosures[edest].nelem == 0)

1423

{

1424

err = calc_eclosure_iter (&eclosure_elem, dfa, edest, 0);

1425

if (BE (err != REG_NOERROR, 0))

1426

return err;

1427

}

1428

else

1429

eclosure_elem = dfa->eclosures[edest];

1430

/* Merge the epsilon closure of `edest'. */

1431

re_node_set_merge (&eclosure, &eclosure_elem);

1432

/* If the epsilon closure of `edest' is incomplete,

1433

the epsilon closure of this node is also incomplete. */

1434

if (dfa->eclosures[edest].nelem == 0)

1435

{

1436

incomplete = 1;

1437

re_node_set_free (&eclosure_elem);

1438

}

1439

}

1440

1441

/* Epsilon closures include itself. */

1442

re_node_set_insert (&eclosure, node);

1443

if (incomplete && !root)

1444

dfa->eclosures[node].nelem = 0;

1445

else

1446

dfa->eclosures[node] = eclosure;

1447

*new_set = eclosure;

1448

return REG_NOERROR;

1449

}

1450

1451

/* Functions for token which are used in the parser. */

1452

1453

/* Fetch a token from INPUT.

1454

We must not use this function inside bracket expressions. */

1455

1456

static re_token_t

1457

fetch_token (input, syntax)

1458

re_string_t *input;

1459

reg_syntax_t syntax;

1460

{

1461

re_token_t token;

1462

int consumed_byte;

1463

consumed_byte = peek_token (&token, input, syntax);

1464

re_string_skip_bytes (input, consumed_byte);

1465

return token;

1466

}

1467

1468

/* Peek a token from INPUT, and return the length of the token.

1469

We must not use this function inside bracket expressions. */

1470

1471

static int

1472

peek_token (token, input, syntax)

1473

re_token_t *token;

1474

re_string_t *input;

1475

reg_syntax_t syntax;

1476

{

1477

unsigned char c;

1478

1479

if (re_string_eoi (input))

1480

{

1481

token->type = END_OF_RE;

1482

return 0;

1483

}

1484

1485

c = re_string_peek_byte (input, 0);

1486

token->opr.c = c;

1487

1488

#ifdef RE_ENABLE_I18N

1489

token->mb_partial = 0;

1490

if (MB_CUR_MAX > 1 &&

1491

!re_string_first_byte (input, re_string_cur_idx (input)))

1492

{

1493

token->type = CHARACTER;

1494

token->mb_partial = 1;

1495

return 1;

1496

}

1497

#endif

1498

if (c == '\\')

1499

{

1500

unsigned char c2;

1501

if (re_string_cur_idx (input) + 1 >= re_string_length (input))

1502

{

1503

token->type = BACK_SLASH;

1504

return 1;

1505

}

1506

1507

c2 = re_string_peek_byte_case (input, 1);

1508

token->opr.c = c2;

1509

token->type = CHARACTER;

1510

switch (c2)

1511

{

1512

case '|':

1513

if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR))

1514

token->type = OP_ALT;

1515

break;

1516

case '1': case '2': case '3': case '4': case '5':

1517

case '6': case '7': case '8': case '9':

1518

if (!(syntax & RE_NO_BK_REFS))

1519

{

1520

token->type = OP_BACK_REF;

1521

token->opr.idx = c2 - '0';

1522

}

1523

break;

1524

case '<':

1525

if (!(syntax & RE_NO_GNU_OPS))

1526

{

1527

token->type = ANCHOR;

1528

token->opr.idx = WORD_FIRST;

1529

}

1530

break;

1531

case '>':

1532

if (!(syntax & RE_NO_GNU_OPS))

1533

{

1534

token->type = ANCHOR;

1535

token->opr.idx = WORD_LAST;

1536

}

1537

break;

1538

case 'b':

1539

if (!(syntax & RE_NO_GNU_OPS))

1540

{

1541

token->type = ANCHOR;

1542

token->opr.idx = WORD_DELIM;

1543

}

1544

break;

1545

case 'B':

1546

if (!(syntax & RE_NO_GNU_OPS))

1547

{

1548

token->type = ANCHOR;

1549

token->opr.idx = INSIDE_WORD;

1550

}

1551

break;

1552

case 'w':

1553

if (!(syntax & RE_NO_GNU_OPS))

1554

token->type = OP_WORD;

1555

break;

1556

case 'W':

1557

if (!(syntax & RE_NO_GNU_OPS))

1558

token->type = OP_NOTWORD;

1559

break;

1560

case '`':

1561

if (!(syntax & RE_NO_GNU_OPS))

1562

{

1563

token->type = ANCHOR;

1564

token->opr.idx = BUF_FIRST;

1565

}

1566

break;

1567

case '\'':

1568

if (!(syntax & RE_NO_GNU_OPS))

1569

{

1570

token->type = ANCHOR;

1571

token->opr.idx = BUF_LAST;

1572

}

1573

break;

1574

case '(':

1575

if (!(syntax & RE_NO_BK_PARENS))

1576

token->type = OP_OPEN_SUBEXP;

1577

break;

1578

case ')':

1579

if (!(syntax & RE_NO_BK_PARENS))

1580

token->type = OP_CLOSE_SUBEXP;

1581

break;

1582

case '+':

1583

if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))

1584

token->type = OP_DUP_PLUS;

1585

break;

1586

case '?':

1587

if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))

1588

token->type = OP_DUP_QUESTION;

1589

break;

1590

case '{':

1591

if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))

1592

token->type = OP_OPEN_DUP_NUM;

1593

break;

1594

case '}':

1595

if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))

1596

token->type = OP_CLOSE_DUP_NUM;

1597

break;

1598

default:

1599

break;

1600

}

1601

return 2;

1602

}

1603

1604

token->type = CHARACTER;

1605

switch (c)

1606

{

1607

case '\n':

1608

if (syntax & RE_NEWLINE_ALT)

1609

token->type = OP_ALT;

1610

break;

1611

case '|':

1612

if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR))

1613

token->type = OP_ALT;

1614

break;

1615

case '*':

1616

token->type = OP_DUP_ASTERISK;

1617

break;

1618

case '+':

1619

if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))

1620

token->type = OP_DUP_PLUS;

1621

break;

1622

case '?':

1623

if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))

1624

token->type = OP_DUP_QUESTION;

1625

break;

1626

case '{':

1627

if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))

1628

token->type = OP_OPEN_DUP_NUM;

1629

break;

1630

case '}':

1631

if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))

1632

token->type = OP_CLOSE_DUP_NUM;

1633

break;

1634

case '(':

1635

if (syntax & RE_NO_BK_PARENS)

1636

token->type = OP_OPEN_SUBEXP;

1637

break;

1638

case ')':

1639

if (syntax & RE_NO_BK_PARENS)

1640

token->type = OP_CLOSE_SUBEXP;

1641

break;

1642

case '[':

1643

token->type = OP_OPEN_BRACKET;

1644

break;

1645

case '.':

1646

token->type = OP_PERIOD;

1647

break;

1648

case '^':

1649

if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&

1650

re_string_cur_idx (input) != 0)

1651

{

1652

char prev = re_string_peek_byte (input, -1);

1653

if (prev != '|' && prev != '(' &&

1654

(!(syntax & RE_NEWLINE_ALT) || prev != '\n'))

1655

break;

1656

}

1657

token->type = ANCHOR;

1658

token->opr.idx = LINE_FIRST;

1659

break;

1660

case '$':

1661

if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&

1662

re_string_cur_idx (input) + 1 != re_string_length (input))

1663

{

1664

re_token_t next;

1665

re_string_skip_bytes (input, 1);

1666

peek_token (&next, input, syntax);

1667

re_string_skip_bytes (input, -1);

1668

if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)

1669

break;

1670

}

1671

token->type = ANCHOR;

1672

token->opr.idx = LINE_LAST;

1673

break;

1674

default:

1675

break;

1676

}

1677

return 1;

1678

}

1679

1680

/* Peek a token from INPUT, and return the length of the token.

1681

We must not use this function out of bracket expressions. */

1682

1683

static int

1684

peek_token_bracket (token, input, syntax)

1685

re_token_t *token;

1686

re_string_t *input;

1687

reg_syntax_t syntax;

1688

{

1689

unsigned char c;

1690

if (re_string_eoi (input))

1691

{

1692

token->type = END_OF_RE;

1693

return 0;

1694

}

1695

c = re_string_peek_byte (input, 0);

1696

token->opr.c = c;

1697

1698

#ifdef RE_ENABLE_I18N

1699

if (MB_CUR_MAX > 1 &&

1700

!re_string_first_byte (input, re_string_cur_idx (input)))

1701

{

1702

token->type = CHARACTER;

1703

return 1;

1704

}

1705

#endif /* RE_ENABLE_I18N */

1706

1707

if (c == '\\' && (syntax & RE_BACKSLASH_ESCAPE_IN_LISTS))

1708

{

1709

/* In this case, '\' escape a character. */

1710

unsigned char c2;

1711

re_string_skip_bytes (input, 1);

1712

c2 = re_string_peek_byte (input, 0);

1713

token->opr.c = c2;

1714

token->type = CHARACTER;

1715

return 1;

1716

}

1717

if (c == '[') /* '[' is a special char in a bracket exps. */

1718

{

1719

unsigned char c2;

1720

int token_len;

1721

c2 = re_string_peek_byte (input, 1);

1722

token->opr.c = c2;

1723

token_len = 2;

1724

switch (c2)

1725

{

1726

case '.':

1727

token->type = OP_OPEN_COLL_ELEM;

1728

break;

1729

case '=':

1730

token->type = OP_OPEN_EQUIV_CLASS;

1731

break;

1732

case ':':

1733

if (syntax & RE_CHAR_CLASSES)

1734

{

1735

token->type = OP_OPEN_CHAR_CLASS;

1736

break;

1737

}

1738

/* else fall through. */

1739

default:

1740

token->type = CHARACTER;

1741

token->opr.c = c;

1742

token_len = 1;

1743

break;

1744

}

1745

return token_len;

1746

}

1747

switch (c)

1748

{

1749

case '-':

1750

token->type = OP_CHARSET_RANGE;

1751

break;

1752

case ']':

1753

token->type = OP_CLOSE_BRACKET;

1754

break;

1755

case '^':

1756

token->type = OP_NON_MATCH_LIST;

1757

break;

1758

default:

1759

token->type = CHARACTER;

1760

}

1761

return 1;

1762

}

1763

1764

/* Functions for parser. */

1765

1766

/* Entry point of the parser.

1767

Parse the regular expression REGEXP and return the structure tree.

1768

If an error is occured, ERR is set by error code, and return NULL.

1769

This function build the following tree, from regular expression <reg_exp>:

1770

CAT

1771

/ \

1772

/ \

1773

<reg_exp> EOR

1774

1775

CAT means concatenation.

1776

EOR means end of regular expression. */

1777

1778

static bin_tree_t *

1779

parse (regexp, preg, syntax, err)

1780

re_string_t *regexp;

1781

regex_t *preg;

1782

reg_syntax_t syntax;

1783

reg_errcode_t *err;

1784

{

1785

re_dfa_t *dfa = (re_dfa_t *) preg->buffer;

1786

bin_tree_t *tree, *eor, *root;

1787

re_token_t current_token;

1788

int new_idx;

1789

current_token = fetch_token (regexp, syntax);

1790

tree = parse_reg_exp (regexp, preg, &current_token, syntax, 0, err);

1791

if (BE (*err != REG_NOERROR && tree == NULL, 0))

1792

return NULL;

1793

new_idx = re_dfa_add_node (dfa, current_token, 0);

1794

eor = create_tree (NULL, NULL, 0, new_idx);

1795

if (tree != NULL)

1796

root = create_tree (tree, eor, CONCAT, 0);

1797

else

1798

root = eor;

1799

if (BE (new_idx == -1 || eor == NULL || root == NULL, 0))

1800

{

1801

*err = REG_ESPACE;

1802

return NULL;

1803

}

1804

return root;

1805

}

1806

1807

/* This function build the following tree, from regular expression

1808

<branch1>|<branch2>:

1809

ALT

1810

/ \

1811

/ \

1812

1813

1814

ALT means alternative, which represents the operator `|'. */

1815

1816

static bin_tree_t *

1817

parse_reg_exp (regexp, preg, token, syntax, nest, err)

1818

re_string_t *regexp;

1819

regex_t *preg;

1820

re_token_t *token;

1821

reg_syntax_t syntax;

1822

int nest;

1823

reg_errcode_t *err;

1824

{

1825

re_dfa_t *dfa = (re_dfa_t *) preg->buffer;

1826

bin_tree_t *tree, *branch = NULL;

1827

int new_idx;

1828

tree = parse_branch (regexp, preg, token, syntax, nest, err);

1829

if (BE (*err != REG_NOERROR && tree == NULL, 0))

1830

return NULL;

1831

1832

while (token->type == OP_ALT)

1833

{

1834

re_token_t alt_token = *token;

1835

new_idx = re_dfa_add_node (dfa, alt_token, 0);

1836

*token = fetch_token (regexp, syntax);

1837

if (token->type != OP_ALT && token->type != END_OF_RE

1838

&& (nest == 0 || token->type != OP_CLOSE_SUBEXP))

1839

{

1840

branch = parse_branch (regexp, preg, token, syntax, nest, err);

1841

if (BE (*err != REG_NOERROR && branch == NULL, 0))

1842

{

1843

free_bin_tree (tree);

1844

return NULL;

1845

}

1846

}

1847

else

1848

branch = NULL;

1849

tree = create_tree (tree, branch, 0, new_idx);

1850

if (BE (new_idx == -1 || tree == NULL, 0))

1851

{

1852

*err = REG_ESPACE;

1853

return NULL;

1854

}

1855

dfa->has_plural_match = 1;

1856

}

1857

return tree;

1858

}

1859

1860

/* This function build the following tree, from regular expression

1861

<exp1><exp2>:

1862

CAT

1863

/ \

1864

/ \

1865

1866

1867

CAT means concatenation. */

1868

1869

static bin_tree_t *

1870

parse_branch (regexp, preg, token, syntax, nest, err)

1871

re_string_t *regexp;

1872

regex_t *preg;

1873

re_token_t *token;

1874

reg_syntax_t syntax;

1875

int nest;

1876

reg_errcode_t *err;

1877

{

1878

bin_tree_t *tree, *exp;

1879

tree = parse_expression (regexp, preg, token, syntax, nest, err);

1880

if (BE (*err != REG_NOERROR && tree == NULL, 0))

1881

return NULL;

1882

1883

while (token->type != OP_ALT && token->type != END_OF_RE

1884

&& (nest == 0 || token->type != OP_CLOSE_SUBEXP))

1885

{

1886

exp = parse_expression (regexp, preg, token, syntax, nest, err);

1887

if (BE (*err != REG_NOERROR && exp == NULL, 0))

1888

{

1889

free_bin_tree (tree);

1890

return NULL;

1891

}

1892

if (tree != NULL && exp != NULL)

1893

{

1894

tree = create_tree (tree, exp, CONCAT, 0);

1895

if (tree == NULL)

1896

{

1897

*err = REG_ESPACE;

1898

return NULL;

1899

}

1900

}

1901

else if (tree == NULL)

1902

tree = exp;

1903

/* Otherwise exp == NULL, we don't need to create new tree. */

1904

}

1905

return tree;

1906

}

1907

1908

/* This function build the following tree, from regular expression a*:

1909

*

1910

|

1911

a

1912

*/

1913

1914

static bin_tree_t *

1915

parse_expression (regexp, preg, token, syntax, nest, err)

1916

re_string_t *regexp;

1917

regex_t *preg;

1918

re_token_t *token;

1919

reg_syntax_t syntax;

1920

int nest;

1921

reg_errcode_t *err;

1922

{

1923

re_dfa_t *dfa = (re_dfa_t *) preg->buffer;

1924

bin_tree_t *tree;

1925

int new_idx;

1926

switch (token->type)

1927

{

1928

case CHARACTER:

1929

new_idx = re_dfa_add_node (dfa, *token, 0);

1930

tree = create_tree (NULL, NULL, 0, new_idx);

1931

if (BE (new_idx == -1 || tree == NULL, 0))

1932

{

1933

*err = REG_ESPACE;

1934

return NULL;

1935

}

1936

#ifdef RE_ENABLE_I18N

1937

if (MB_CUR_MAX > 1)

1938

{

1939

while (!re_string_eoi (regexp)

1940

&& !re_string_first_byte (regexp, re_string_cur_idx (regexp)))

1941

{

1942

bin_tree_t *mbc_remain;

1943

*token = fetch_token (regexp, syntax);

1944

new_idx = re_dfa_add_node (dfa, *token, 0);

1945

mbc_remain = create_tree (NULL, NULL, 0, new_idx);

1946

tree = create_tree (tree, mbc_remain, CONCAT, 0);

1947

if (BE (new_idx == -1 || mbc_remain == NULL || tree == NULL, 0))

1948

{

1949

*err = REG_ESPACE;

1950

return NULL;

1951

}

1952

}

1953

}

1954

#endif

1955

break;

1956

case OP_OPEN_SUBEXP:

1957

tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);

1958

if (BE (*err != REG_NOERROR && tree == NULL, 0))

1959

return NULL;

1960

break;

1961

case OP_OPEN_BRACKET:

1962

tree = parse_bracket_exp (regexp, dfa, token, syntax, err);

1963

if (BE (*err != REG_NOERROR && tree == NULL, 0))

1964

return NULL;

1965

break;

1966

case OP_BACK_REF:

1967

if (BE (preg->re_nsub < token->opr.idx

1968

|| dfa->subexps[token->opr.idx - 1].end == -1, 0))

1969

{

1970

*err = REG_ESUBREG;

1971

return NULL;

1972

}

1973

dfa->used_bkref_map |= 1 << (token->opr.idx - 1);

1974

new_idx = re_dfa_add_node (dfa, *token, 0);

1975

tree = create_tree (NULL, NULL, 0, new_idx);

1976

if (BE (new_idx == -1 || tree == NULL, 0))

1977

{

1978

*err = REG_ESPACE;

1979

return NULL;

1980

}

1981

++dfa->nbackref;

1982

dfa->has_mb_node = 1;

1983

break;

1984

case OP_DUP_ASTERISK:

1985

case OP_DUP_PLUS:

1986

case OP_DUP_QUESTION:

1987

case OP_OPEN_DUP_NUM:

1988

if (syntax & RE_CONTEXT_INVALID_OPS)

1989

{

1990

*err = REG_BADRPT;

1991

return NULL;

1992

}

1993

else if (syntax & RE_CONTEXT_INDEP_OPS)

1994

{

1995

*token = fetch_token (regexp, syntax);

1996

return parse_expression (regexp, preg, token, syntax, nest, err);

1997

}

1998

/* else fall through */

1999

case OP_CLOSE_SUBEXP:

2000

if ((token->type == OP_CLOSE_SUBEXP) &&

2001

!(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD))

2002

{

2003

*err = REG_ERPAREN;

2004

return NULL;

2005

}

2006

/* else fall through */

2007

case OP_CLOSE_DUP_NUM:

2008

/* We treat it as a normal character. */

2009

2010

/* Then we can these characters as normal characters. */

2011

token->type = CHARACTER;

2012

new_idx = re_dfa_add_node (dfa, *token, 0);

2013

tree = create_tree (NULL, NULL, 0, new_idx);

2014

if (BE (new_idx == -1 || tree == NULL, 0))

2015

{

2016

*err = REG_ESPACE;

2017

return NULL;

2018

}

2019

break;

2020

case ANCHOR:

2021

if (dfa->word_char == NULL)

2022

{

2023

*err = init_word_char (dfa);

2024

if (BE (*err != REG_NOERROR, 0))

2025

return NULL;

2026

}

2027

if (token->opr.ctx_type == WORD_DELIM)

2028

{

2029

bin_tree_t *tree_first, *tree_last;

2030

int idx_first, idx_last;

2031

token->opr.ctx_type = WORD_FIRST;

2032

idx_first = re_dfa_add_node (dfa, *token, 0);

2033

tree_first = create_tree (NULL, NULL, 0, idx_first);

2034

token->opr.ctx_type = WORD_LAST;

2035

idx_last = re_dfa_add_node (dfa, *token, 0);

2036

tree_last = create_tree (NULL, NULL, 0, idx_last);

2037

token->type = OP_ALT;

2038

new_idx = re_dfa_add_node (dfa, *token, 0);

2039

tree = create_tree (tree_first, tree_last, 0, new_idx);

2040

if (BE (idx_first == -1 || idx_last == -1 || new_idx == -1

2041

|| tree_first == NULL || tree_last == NULL

2042

|| tree == NULL, 0))

2043

{

2044

*err = REG_ESPACE;

2045

return NULL;

2046

}

2047

}

2048

else

2049

{

2050

new_idx = re_dfa_add_node (dfa, *token, 0);

2051

tree = create_tree (NULL, NULL, 0, new_idx);

2052

if (BE (new_idx == -1 || tree == NULL, 0))

2053

{

2054

*err = REG_ESPACE;

2055

return NULL;

2056

}

2057

}

2058

/* We must return here, since ANCHORs can't be followed

2059

by repetition operators.

2060

eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",

2061

it must not be "<ANCHOR(^)><REPEAT(*)>". */

2062

*token = fetch_token (regexp, syntax);

2063

return tree;

2064

case OP_PERIOD:

2065

new_idx = re_dfa_add_node (dfa, *token, 0);

2066

tree = create_tree (NULL, NULL, 0, new_idx);

2067

if (BE (new_idx == -1 || tree == NULL, 0))

2068

{

2069

*err = REG_ESPACE;

2070

return NULL;

2071

}

2072

if (MB_CUR_MAX > 1)

2073

dfa->has_mb_node = 1;

2074

break;

2075

case OP_WORD:

2076

tree = build_word_op (dfa, 0, err);

2077

if (BE (*err != REG_NOERROR && tree == NULL, 0))

2078

return NULL;

2079

break;

2080

case OP_NOTWORD:

2081

tree = build_word_op (dfa, 1, err);

2082

if (BE (*err != REG_NOERROR && tree == NULL, 0))

2083

return NULL;

2084

break;

2085

case OP_ALT:

2086

case END_OF_RE:

2087

return NULL;

2088

case BACK_SLASH:

2089

*err = REG_EESCAPE;

2090

return NULL;

2091

default:

2092

/* Must not happen? */

2093

#ifdef DEBUG

2094

assert (0);

2095

#endif

2096

return NULL;

2097

}

2098

*token = fetch_token (regexp, syntax);

2099

2100

while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS

2101

|| token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)

2102

{

2103

tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);

2104

if (BE (*err != REG_NOERROR && tree == NULL, 0))

2105

return NULL;

2106

dfa->has_plural_match = 1;

2107

}

2108

2109

return tree;

2110

}

2111

2112

/* This function build the following tree, from regular expression

2113

(<reg_exp>):

2114

SUBEXP

2115

|

2116

<reg_exp>

2117

*/

2118

2119

static bin_tree_t *

2120

parse_sub_exp (regexp, preg, token, syntax, nest, err)

2121

re_string_t *regexp;

2122

regex_t *preg;

2123

re_token_t *token;

2124

reg_syntax_t syntax;

2125

int nest;

2126

reg_errcode_t *err;

2127

{

2128

re_dfa_t *dfa = (re_dfa_t *) preg->buffer;

2129

bin_tree_t *tree, *left_par, *right_par;

2130

size_t cur_nsub;

2131

int new_idx;

2132

cur_nsub = preg->re_nsub++;

2133

if (dfa->subexps_alloc < preg->re_nsub)

2134

{

2135

re_subexp_t *new_array;

2136

dfa->subexps_alloc *= 2;

2137

new_array = re_realloc (dfa->subexps, re_subexp_t, dfa->subexps_alloc);

2138

if (BE (new_array == NULL, 0))

2139

{

2140

dfa->subexps_alloc /= 2;

2141

*err = REG_ESPACE;

2142

return NULL;

2143

}

2144

dfa->subexps = new_array;

2145

}

2146

dfa->subexps[cur_nsub].start = dfa->nodes_len;

2147

dfa->subexps[cur_nsub].end = -1;

2148

2149

new_idx = re_dfa_add_node (dfa, *token, 0);

2150

left_par = create_tree (NULL, NULL, 0, new_idx);

2151

if (BE (new_idx == -1 || left_par == NULL, 0))

2152

{

2153

*err = REG_ESPACE;

2154

return NULL;

2155

}

2156

dfa->nodes[new_idx].opr.idx = cur_nsub;

2157

*token = fetch_token (regexp, syntax);

2158

2159

/* The subexpression may be a null string. */

2160

if (token->type == OP_CLOSE_SUBEXP)

2161

tree = NULL;

2162

else

2163

{

2164

tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);

2165

if (BE (*err != REG_NOERROR && tree == NULL, 0))

2166

return NULL;

2167

}

2168

if (BE (token->type != OP_CLOSE_SUBEXP, 0))

2169

{

2170

free_bin_tree (tree);

2171

*err = REG_BADPAT;

2172

return NULL;

2173

}

2174

new_idx = re_dfa_add_node (dfa, *token, 0);

2175

dfa->subexps[cur_nsub].end = dfa->nodes_len;

2176

right_par = create_tree (NULL, NULL, 0, new_idx);

2177

tree = ((tree == NULL) ? right_par

2178

: create_tree (tree, right_par, CONCAT, 0));

2179

tree = create_tree (left_par, tree, CONCAT, 0);

2180

if (BE (new_idx == -1 || right_par == NULL || tree == NULL, 0))

2181

{

2182

*err = REG_ESPACE;

2183

return NULL;

2184

}

2185

dfa->nodes[new_idx].opr.idx = cur_nsub;

2186

2187

return tree;

2188

}

2189

2190

/* This function parse repetition operators like "*", "+", "{1,3}" etc. */

2191

2192

static bin_tree_t *

2193

parse_dup_op (dup_elem, regexp, dfa, token, syntax, err)

2194

bin_tree_t *dup_elem;

2195

re_string_t *regexp;

2196

re_dfa_t *dfa;

2197

re_token_t *token;

2198

reg_syntax_t syntax;

2199

reg_errcode_t *err;

2200

{

2201

re_token_t dup_token;

2202

bin_tree_t *tree = dup_elem, *work_tree;

2203

int new_idx, start_idx = re_string_cur_idx (regexp);

2204

re_token_t start_token = *token;

2205

if (token->type == OP_OPEN_DUP_NUM)

2206

{

2207

int i;

2208

int end = 0;

2209

int start = fetch_number (regexp, token, syntax);

2210

bin_tree_t *elem;

2211

if (start == -1)

2212

{

2213

if (token->type == CHARACTER && token->opr.c == ',')

2214

start = 0; /* We treat "{,m}" as "{0,m}". */

2215

else

2216

{

2217

*err = REG_BADBR; /* <re>{} is invalid. */

2218

return NULL;

2219

}

2220

}

2221

if (BE (start != -2, 1))

2222

{

2223

/* We treat "{n}" as "{n,n}". */

2224

end = ((token->type == OP_CLOSE_DUP_NUM) ? start

2225

: ((token->type == CHARACTER && token->opr.c == ',')

2226

? fetch_number (regexp, token, syntax) : -2));

2227

}

2228

if (BE (start == -2 || end == -2, 0))

2229

{

2230

/* Invalid sequence. */

2231

if (token->type == OP_CLOSE_DUP_NUM)

2232

goto parse_dup_op_invalid_interval;

2233

else

2234

goto parse_dup_op_ebrace;

2235

}

2236

if (BE (start == 0 && end == 0, 0))

2237

{

2238

/* We treat "<re>{0}" and "<re>{0,0}" as null string. */

2239

*token = fetch_token (regexp, syntax);

2240

free_bin_tree (dup_elem);

2241

return NULL;

2242

}

2243

2244

/* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */

2245

elem = tree;

2246

for (i = 0; i < start; ++i)

2247

if (i != 0)

2248

{

2249

work_tree = duplicate_tree (elem, dfa);

2250

tree = create_tree (tree, work_tree, CONCAT, 0);

2251

if (BE (work_tree == NULL || tree == NULL, 0))

2252

goto parse_dup_op_espace;

2253

}

2254

2255

if (end == -1)

2256

{

2257

/* We treat "<re>{0,}" as "<re>*". */

2258

dup_token.type = OP_DUP_ASTERISK;

2259

if (start > 0)

2260

{

2261

elem = duplicate_tree (elem, dfa);

2262

new_idx = re_dfa_add_node (dfa, dup_token, 0);

2263

work_tree = create_tree (elem, NULL, 0, new_idx);

2264

tree = create_tree (tree, work_tree, CONCAT, 0);

2265

if (BE (elem == NULL || new_idx == -1 || work_tree == NULL

2266

|| tree == NULL, 0))

2267

goto parse_dup_op_espace;

2268

}

2269

else

2270

{

2271

new_idx = re_dfa_add_node (dfa, dup_token, 0);

2272

tree = create_tree (elem, NULL, 0, new_idx);

2273

if (BE (new_idx == -1 || tree == NULL, 0))

2274

goto parse_dup_op_espace;

2275

}

2276

}

2277

else if (end - start > 0)

2278

{

2279

/* Then extract "<re>{0,m}" to "<re>?<re>?...<re>?". */

2280

dup_token.type = OP_DUP_QUESTION;

2281

if (start > 0)

2282

{

2283

elem = duplicate_tree (elem, dfa);

2284

new_idx = re_dfa_add_node (dfa, dup_token, 0);

2285

elem = create_tree (elem, NULL, 0, new_idx);

2286

tree = create_tree (tree, elem, CONCAT, 0);

2287

if (BE (elem == NULL || new_idx == -1 || tree == NULL, 0))

2288

goto parse_dup_op_espace;

2289

}

2290

else

2291

{

2292

new_idx = re_dfa_add_node (dfa, dup_token, 0);

2293

tree = elem = create_tree (elem, NULL, 0, new_idx);

2294

if (BE (new_idx == -1 || tree == NULL, 0))

2295

goto parse_dup_op_espace;

2296

}

2297

for (i = 1; i < end - start; ++i)

2298

{

2299

work_tree = duplicate_tree (elem, dfa);

2300

tree = create_tree (tree, work_tree, CONCAT, 0);

2301

if (BE (work_tree == NULL || tree == NULL, 0))

2302

{

2303

*err = REG_ESPACE;

2304

return NULL;

2305

}

2306

}

2307

}

2308

}

2309

else

2310

{

2311

new_idx = re_dfa_add_node (dfa, *token, 0);

2312

tree = create_tree (tree, NULL, 0, new_idx);

2313

if (BE (new_idx == -1 || tree == NULL, 0))

2314

{

2315

*err = REG_ESPACE;

2316

return NULL;

2317

}

2318

}

2319

*token = fetch_token (regexp, syntax);

2320

return tree;

2321

2322

parse_dup_op_espace:

2323

free_bin_tree (tree);

2324

*err = REG_ESPACE;

2325

return NULL;

2326

2327

parse_dup_op_ebrace:

2328

if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))

2329

{

2330

*err = REG_EBRACE;

2331

return NULL;

2332

}

2333

goto parse_dup_op_rollback;

2334

parse_dup_op_invalid_interval:

2335

if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))

2336

{

2337

*err = REG_BADBR;

2338

return NULL;

2339

}

2340

parse_dup_op_rollback:

2341

re_string_set_index (regexp, start_idx);

2342

*token = start_token;

2343

token->type = CHARACTER;

2344

return dup_elem;

2345

}

2346

2347

/* Size of the names for collating symbol/equivalence_class/character_class.

2348

I'm not sure, but maybe enough. */

2349

#define BRACKET_NAME_BUF_SIZE 32

2350

2351

#ifndef _LIBC

2352

/* Local function for parse_bracket_exp only used in case of NOT _LIBC.

2353

Build the range expression which starts from START_ELEM, and ends

2354

at END_ELEM. The result are written to MBCSET and SBCSET.

2355

RANGE_ALLOC is the allocated size of mbcset->range_starts, and

2356

mbcset->range_ends, is a pointer argument sinse we may

2357

update it. */

2358

2359

static reg_errcode_t

2360

# ifdef RE_ENABLE_I18N

2361

build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)

2362

re_charset_t *mbcset;

2363

int *range_alloc;

2364

# else /* not RE_ENABLE_I18N */

2365

build_range_exp (sbcset, start_elem, end_elem)

2366

# endif /* not RE_ENABLE_I18N */

2367

re_bitset_ptr_t sbcset;

2368

bracket_elem_t *start_elem, *end_elem;

2369

{

2370

unsigned int start_ch, end_ch;

2371

/* Equivalence Classes and Character Classes can't be a range start/end. */

2372

if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS

2373

|| end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,

2374

0))

2375

return REG_ERANGE;

2376

2377

/* We can handle no multi character collating elements without libc

2378

support. */

2379

if (BE ((start_elem->type == COLL_SYM

2380

&& strlen ((char *) start_elem->opr.name) > 1)

2381

|| (end_elem->type == COLL_SYM

2382

&& strlen ((char *) end_elem->opr.name) > 1), 0))

2383

return REG_ECOLLATE;

2384

2385

# ifdef RE_ENABLE_I18N

2386

{

2387

wchar_t wc, start_wc, end_wc;

2388

wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};

2389

2390

start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch

2391

: ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]

2392

: 0));

2393

end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch

2394

: ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]

2395

: 0));

2396

start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)

2397

? __btowc (start_ch) : start_elem->opr.wch);

2398

end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)

2399

? __btowc (end_ch) : end_elem->opr.wch);

2400

cmp_buf[0] = start_wc;

2401

cmp_buf[4] = end_wc;

2402

if (wcscoll (cmp_buf, cmp_buf + 4) > 0)

2403

return REG_ERANGE;

2404

2405

/* Check the space of the arrays. */

2406

if (*range_alloc == mbcset->nranges)

2407

{

2408

/* There are not enough space, need realloc. */

2409

wchar_t *new_array_start, *new_array_end;

2410

int new_nranges;

2411

2412

/* +1 in case of mbcset->nranges is 0. */

2413

new_nranges = 2 * mbcset->nranges + 1;

2414

/* Use realloc since mbcset->range_starts and mbcset->range_ends

2415

are NULL if *range_alloc == 0. */

2416

new_array_start = re_realloc (mbcset->range_starts, wchar_t,

2417

new_nranges);

2418

new_array_end = re_realloc (mbcset->range_ends, wchar_t,

2419

new_nranges);

2420

2421

if (BE (new_array_start == NULL || new_array_end == NULL, 0))

2422

return REG_ESPACE;

2423

2424

mbcset->range_starts = new_array_start;

2425

mbcset->range_ends = new_array_end;

2426

*range_alloc = new_nranges;

2427

}

2428

2429

mbcset->range_starts[mbcset->nranges] = start_wc;

2430

mbcset->range_ends[mbcset->nranges++] = end_wc;

2431

2432

/* Build the table for single byte characters. */

2433

for (wc = 0; wc <= SBC_MAX; ++wc)

2434

{

2435

cmp_buf[2] = wc;

2436

if (wcscoll (cmp_buf, cmp_buf + 2) <= 0

2437

&& wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)

2438

bitset_set (sbcset, wc);

2439

}

2440

}

2441

# else /* not RE_ENABLE_I18N */

2442

{

2443

unsigned int ch;

2444

start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch

2445

: ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]

2446

: 0));

2447

end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch

2448

: ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]

2449

: 0));

2450

if (start_ch > end_ch)

2451

return REG_ERANGE;

2452

/* Build the table for single byte characters. */

2453

for (ch = 0; ch <= SBC_MAX; ++ch)

2454

if (start_ch <= ch && ch <= end_ch)

2455

bitset_set (sbcset, ch);

2456

}

2457

# endif /* not RE_ENABLE_I18N */

2458

return REG_NOERROR;

2459

}

2460

#endif /* not _LIBC */

2461

2462

#ifndef _LIBC

2463

/* Helper function for parse_bracket_exp only used in case of NOT _LIBC..

2464

Build the collating element which is represented by NAME.

2465

The result are written to MBCSET and SBCSET.

2466

COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a

2467

pointer argument since we may update it. */

2468

2469

static reg_errcode_t

2470

# ifdef RE_ENABLE_I18N

2471

build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)

2472

re_charset_t *mbcset;

2473

int *coll_sym_alloc;

2474

# else /* not RE_ENABLE_I18N */

2475

build_collating_symbol (sbcset, name)

2476

# endif /* not RE_ENABLE_I18N */

2477

re_bitset_ptr_t sbcset;

2478

const unsigned char *name;

2479

{

2480

size_t name_len = strlen ((const char *) name);

2481

if (BE (name_len != 1, 0))

2482

return REG_ECOLLATE;

2483

else

2484

{

2485

bitset_set (sbcset, name[0]);

2486

return REG_NOERROR;

2487

}

2488

}

2489

#endif /* not _LIBC */

2490

2491

/* This function parse bracket expression like "[abc]", "[a-c]",

2492

"[[.a-a.]]" etc. */

2493

2494

static bin_tree_t *

2495

parse_bracket_exp (regexp, dfa, token, syntax, err)

2496

re_string_t *regexp;

2497

re_dfa_t *dfa;

2498

re_token_t *token;

2499

reg_syntax_t syntax;

2500

reg_errcode_t *err;

2501

{

2502

#ifdef _LIBC

2503

const unsigned char *collseqmb;

2504

const char *collseqwc;

2505

uint32_t nrules;

2506

int32_t table_size;

2507

const int32_t *symb_table;

2508

const unsigned char *extra;

2509

2510

/* Local function for parse_bracket_exp used in _LIBC environement.

2511

Seek the collating symbol entry correspondings to NAME.

2512

Return the index of the symbol in the SYMB_TABLE. */

2513

2514

static inline int32_t

2515

seek_collating_symbol_entry (name, name_len)

2516

const unsigned char *name;

2517

size_t name_len;

2518

{

2519

int32_t hash = elem_hash ((const char *) name, name_len);

2520

int32_t elem = hash % table_size;

2521

int32_t second = hash % (table_size - 2);

2522

while (symb_table[2 * elem] != 0)

2523

{

2524

/* First compare the hashing value. */

2525

if (symb_table[2 * elem] == hash

2526

/* Compare the length of the name. */

2527

&& name_len == extra[symb_table[2 * elem + 1]]

2528

/* Compare the name. */

2529

&& memcmp (name, &extra[symb_table[2 * elem + 1] + 1],

2530

name_len) == 0)

2531

{

2532

/* Yep, this is the entry. */

2533

break;

2534

}

2535

2536

/* Next entry. */

2537

elem += second;

2538

}

2539

return elem;

2540

}

2541

2542

/* Local function for parse_bracket_exp used in _LIBC environement.

2543

Look up the collation sequence value of BR_ELEM.

2544

Return the value if succeeded, UINT_MAX otherwise. */

2545

2546

static inline unsigned int

2547

lookup_collation_sequence_value (br_elem)

2548

bracket_elem_t *br_elem;

2549

{

2550

if (br_elem->type == SB_CHAR)

2551

{

2552

/*

2553

if (MB_CUR_MAX == 1)

2554

*/

2555

if (nrules == 0)

2556

return collseqmb[br_elem->opr.ch];

2557

else

2558

{

2559

wint_t wc = __btowc (br_elem->opr.ch);

2560

return collseq_table_lookup (collseqwc, wc);

2561

}

2562

}

2563

else if (br_elem->type == MB_CHAR)

2564

{

2565

return collseq_table_lookup (collseqwc, br_elem->opr.wch);

2566

}

2567

else if (br_elem->type == COLL_SYM)

2568

{

2569

size_t sym_name_len = strlen ((char *) br_elem->opr.name);

2570

if (nrules != 0)

2571

{

2572

int32_t elem, idx;

2573

elem = seek_collating_symbol_entry (br_elem->opr.name,

2574

sym_name_len);

2575

if (symb_table[2 * elem] != 0)

2576

{

2577

/* We found the entry. */

2578

idx = symb_table[2 * elem + 1];

2579

/* Skip the name of collating element name. */

2580

idx += 1 + extra[idx];

2581

/* Skip the byte sequence of the collating element. */

2582

idx += 1 + extra[idx];

2583

/* Adjust for the alignment. */

2584

idx = (idx + 3) & ~3;

2585

/* Skip the multibyte collation sequence value. */

2586

idx += sizeof (unsigned int);

2587

/* Skip the wide char sequence of the collating element. */

2588

idx += sizeof (unsigned int) *

2589

(1 + *(unsigned int *) (extra + idx));

2590

/* Return the collation sequence value. */

2591

return *(unsigned int *) (extra + idx);

2592

}

2593

else if (symb_table[2 * elem] == 0 && sym_name_len == 1)

2594

{

2595

/* No valid character. Match it as a single byte

2596

character. */

2597

return collseqmb[br_elem->opr.name[0]];

2598

}

2599

}

2600

else if (sym_name_len == 1)

2601

return collseqmb[br_elem->opr.name[0]];

2602

}

2603

return UINT_MAX;

2604

}

2605

2606

/* Local function for parse_bracket_exp used in _LIBC environement.

2607

Build the range expression which starts from START_ELEM, and ends

2608

at END_ELEM. The result are written to MBCSET and SBCSET.

2609

RANGE_ALLOC is the allocated size of mbcset->range_starts, and

2610

mbcset->range_ends, is a pointer argument sinse we may

2611

update it. */

2612

2613

static inline reg_errcode_t

2614

# ifdef RE_ENABLE_I18N

2615

build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)

2616

re_charset_t *mbcset;

2617

int *range_alloc;

2618

# else /* not RE_ENABLE_I18N */

2619

build_range_exp (sbcset, start_elem, end_elem)

2620

# endif /* not RE_ENABLE_I18N */

2621

re_bitset_ptr_t sbcset;

2622

bracket_elem_t *start_elem, *end_elem;

2623

{

2624

unsigned int ch;

2625

uint32_t start_collseq;

2626

uint32_t end_collseq;

2627

2628

# ifdef RE_ENABLE_I18N

2629

/* Check the space of the arrays. */

2630

if (*range_alloc == mbcset->nranges)

2631

{

2632

/* There are not enough space, need realloc. */

2633

uint32_t *new_array_start;

2634

uint32_t *new_array_end;

2635

int new_nranges;

2636

2637

/* +1 in case of mbcset->nranges is 0. */

2638

new_nranges = 2 * mbcset->nranges + 1;

2639

/* Use realloc since mbcset->range_starts and mbcset->range_ends

2640

are NULL if *range_alloc == 0. */

2641

new_array_start = re_realloc (mbcset->range_starts, uint32_t,

2642

new_nranges);

2643

new_array_end = re_realloc (mbcset->range_ends, uint32_t,

2644

new_nranges);

2645

2646

if (BE (new_array_start == NULL || new_array_end == NULL, 0))

2647

return REG_ESPACE;

2648

2649

mbcset->range_starts = new_array_start;

2650

mbcset->range_ends = new_array_end;

2651

*range_alloc = new_nranges;

2652

}

2653

# endif /* RE_ENABLE_I18N */

2654

2655

/* Equivalence Classes and Character Classes can't be a range

2656

start/end. */

2657

if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS

2658

|| end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,

2659

0))

2660

return REG_ERANGE;

2661

2662

start_collseq = lookup_collation_sequence_value (start_elem);

2663

end_collseq = lookup_collation_sequence_value (end_elem);

2664

/* Check start/end collation sequence values. */

2665

if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0))

2666

return REG_ECOLLATE;

2667

if (BE ((syntax & RE_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0))

2668

return REG_ERANGE;

2669

2670

# ifdef RE_ENABLE_I18N

2671

/* Got valid collation sequence values, add them as a new entry. */

2672

mbcset->range_starts[mbcset->nranges] = start_collseq;

2673

mbcset->range_ends[mbcset->nranges++] = end_collseq;

2674

# endif /* RE_ENABLE_I18N */

2675

2676

/* Build the table for single byte characters. */

2677

for (ch = 0; ch <= SBC_MAX; ch++)

2678

{

2679

uint32_t ch_collseq;

2680

/*

2681

if (MB_CUR_MAX == 1)

2682

*/

2683

if (nrules == 0)

2684

ch_collseq = collseqmb[ch];

2685

else

2686

ch_collseq = collseq_table_lookup (collseqwc, __btowc (ch));

2687

if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)

2688

bitset_set (sbcset, ch);

2689

}

2690

return REG_NOERROR;

2691

}

2692

2693

/* Local function for parse_bracket_exp used in _LIBC environement.

2694

Build the collating element which is represented by NAME.

2695

The result are written to MBCSET and SBCSET.

2696

COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a

2697

pointer argument sinse we may update it. */

2698

2699

static inline reg_errcode_t

2700

# ifdef RE_ENABLE_I18N

2701

build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)

2702

re_charset_t *mbcset;

2703

int *coll_sym_alloc;

2704

# else /* not RE_ENABLE_I18N */

2705

build_collating_symbol (sbcset, name)

2706

# endif /* not RE_ENABLE_I18N */

2707

re_bitset_ptr_t sbcset;

2708

const unsigned char *name;

2709

{

2710

int32_t elem, idx;

2711

size_t name_len = strlen ((const char *) name);

2712

if (nrules != 0)

2713

{

2714

elem = seek_collating_symbol_entry (name, name_len);

2715

if (symb_table[2 * elem] != 0)

2716

{

2717

/* We found the entry. */

2718

idx = symb_table[2 * elem + 1];

2719

/* Skip the name of collating element name. */

2720

idx += 1 + extra[idx];

2721

}

2722

else if (symb_table[2 * elem] == 0 && name_len == 1)

2723

{

2724

/* No valid character, treat it as a normal

2725

character. */

2726

bitset_set (sbcset, name[0]);

2727

return REG_NOERROR;

2728

}

2729

else

2730

return REG_ECOLLATE;

2731

2732

# ifdef RE_ENABLE_I18N

2733

/* Got valid collation sequence, add it as a new entry. */

2734

/* Check the space of the arrays. */

2735

if (*coll_sym_alloc == mbcset->ncoll_syms)

2736

{

2737

/* Not enough, realloc it. */

2738

/* +1 in case of mbcset->ncoll_syms is 0. */

2739

*coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;

2740

/* Use realloc since mbcset->coll_syms is NULL

2741

if *alloc == 0. */

2742

mbcset->coll_syms = re_realloc (mbcset->coll_syms, int32_t,

2743

*coll_sym_alloc);

2744

if (BE (mbcset->coll_syms == NULL, 0))

2745

return REG_ESPACE;

2746

}

2747

mbcset->coll_syms[mbcset->ncoll_syms++] = idx;

2748

# endif /* RE_ENABLE_I18N */

2749

return REG_NOERROR;

2750

}

2751

else

2752

{

2753

if (BE (name_len != 1, 0))

2754

return REG_ECOLLATE;

2755

else

2756

{

2757

bitset_set (sbcset, name[0]);

2758

return REG_NOERROR;

2759

}

2760

}

2761

}

2762

#endif

2763

2764

re_token_t br_token;

2765

re_bitset_ptr_t sbcset;

2766

#ifdef RE_ENABLE_I18N

2767

re_charset_t *mbcset;

2768

int coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;

2769

int equiv_class_alloc = 0, char_class_alloc = 0;

2770

#else /* not RE_ENABLE_I18N */

2771

int non_match = 0;

2772

#endif /* not RE_ENABLE_I18N */

2773

bin_tree_t *work_tree;

2774

int token_len, new_idx;

2775

#ifdef _LIBC

2776

collseqmb = (const unsigned char *)

2777

_NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);

2778

nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);

2779

if (nrules)

2780

{

2781

/*

2782

if (MB_CUR_MAX > 1)

2783

*/

2784

collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);

2785

table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);

2786

symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,

2787

_NL_COLLATE_SYMB_TABLEMB);

2788

extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,

2789

_NL_COLLATE_SYMB_EXTRAMB);

2790

}

2791

#endif

2792

sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);

2793

#ifdef RE_ENABLE_I18N

2794

mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);

2795

#endif /* RE_ENABLE_I18N */

2796

#ifdef RE_ENABLE_I18N

2797

if (BE (sbcset == NULL || mbcset == NULL, 0))

2798

#else

2799

if (BE (sbcset == NULL, 0))

2800

#endif /* RE_ENABLE_I18N */

2801

{

2802

*err = REG_ESPACE;

2803

return NULL;

2804

}

2805

2806

token_len = peek_token_bracket (token, regexp, syntax);

2807

if (BE (token->type == END_OF_RE, 0))

2808

{

2809

*err = REG_BADPAT;

2810

goto parse_bracket_exp_free_return;

2811

}

2812

if (token->type == OP_NON_MATCH_LIST)

2813

{

2814

#ifdef RE_ENABLE_I18N

2815

int i;

2816

mbcset->non_match = 1;

2817

#else /* not RE_ENABLE_I18N */

2818

non_match = 1;

2819

#endif /* not RE_ENABLE_I18N */

2820

if (syntax & RE_HAT_LISTS_NOT_NEWLINE)

2821

bitset_set (sbcset, '\0');

2822

re_string_skip_bytes (regexp, token_len); /* Skip a token. */

2823

token_len = peek_token_bracket (token, regexp, syntax);

2824

if (BE (token->type == END_OF_RE, 0))

2825

{

2826

*err = REG_BADPAT;

2827

goto parse_bracket_exp_free_return;

2828

}

2829

#ifdef RE_ENABLE_I18N

2830

if (MB_CUR_MAX > 1)

2831

for (i = 0; i < SBC_MAX; ++i)

2832

if (__btowc (i) == WEOF)

2833

bitset_set (sbcset, i);

2834

#endif /* RE_ENABLE_I18N */

2835

}

2836

2837

/* We treat the first ']' as a normal character. */

2838

if (token->type == OP_CLOSE_BRACKET)

2839

token->type = CHARACTER;

2840

2841

while (1)

2842

{

2843

bracket_elem_t start_elem, end_elem;

2844

unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];

2845

unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];

2846

reg_errcode_t ret;

2847

int token_len2 = 0, is_range_exp = 0;

2848

re_token_t token2;

2849

2850

start_elem.opr.name = start_name_buf;

2851

ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,

2852

syntax);

2853

if (BE (ret != REG_NOERROR, 0))

2854

{

2855

*err = ret;

2856

goto parse_bracket_exp_free_return;

2857

}

2858

2859

token_len = peek_token_bracket (token, regexp, syntax);

2860

if (BE (token->type == END_OF_RE, 0))

2861

{

2862

*err = REG_BADPAT;

2863

goto parse_bracket_exp_free_return;

2864

}

2865

if (token->type == OP_CHARSET_RANGE)

2866

{

2867

re_string_skip_bytes (regexp, token_len); /* Skip '-'. */

2868

token_len2 = peek_token_bracket (&token2, regexp, syntax);

2869

if (BE (token->type == END_OF_RE, 0))

2870

{

2871

*err = REG_BADPAT;

2872

goto parse_bracket_exp_free_return;

2873

}

2874

if (token2.type == OP_CLOSE_BRACKET)

2875

{

2876

/* We treat the last '-' as a normal character. */

2877

re_string_skip_bytes (regexp, -token_len);

2878

token->type = CHARACTER;

2879

}

2880

else

2881

is_range_exp = 1;

2882

}

2883

2884

if (is_range_exp == 1)

2885

{

2886

end_elem.opr.name = end_name_buf;

2887

ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,

2888

dfa, syntax);

2889

if (BE (ret != REG_NOERROR, 0))

2890

{

2891

*err = ret;

2892

goto parse_bracket_exp_free_return;

2893

}

2894

2895

token_len = peek_token_bracket (token, regexp, syntax);

2896

if (BE (token->type == END_OF_RE, 0))

2897

{

2898

*err = REG_BADPAT;

2899

goto parse_bracket_exp_free_return;

2900

}

2901

*err = build_range_exp (sbcset,

2902

#ifdef RE_ENABLE_I18N

2903

mbcset, &range_alloc,

2904

#endif /* RE_ENABLE_I18N */

2905

&start_elem, &end_elem);

2906

if (BE (*err != REG_NOERROR, 0))

2907

goto parse_bracket_exp_free_return;

2908

}

2909

else

2910

{

2911

switch (start_elem.type)

2912

{

2913

case SB_CHAR:

2914

bitset_set (sbcset, start_elem.opr.ch);

2915

break;

2916

#ifdef RE_ENABLE_I18N

2917

case MB_CHAR:

2918

/* Check whether the array has enough space. */

2919

if (mbchar_alloc == mbcset->nmbchars)

2920

{

2921

/* Not enough, realloc it. */

2922

/* +1 in case of mbcset->nmbchars is 0. */

2923

mbchar_alloc = 2 * mbcset->nmbchars + 1;

2924

/* Use realloc since array is NULL if *alloc == 0. */

2925

mbcset->mbchars = re_realloc (mbcset->mbchars, wchar_t,

2926

mbchar_alloc);

2927

if (BE (mbcset->mbchars == NULL, 0))

2928

goto parse_bracket_exp_espace;

2929

}

2930

mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;

2931

break;

2932

#endif /* RE_ENABLE_I18N */

2933

case EQUIV_CLASS:

2934

*err = build_equiv_class (sbcset,

2935

#ifdef RE_ENABLE_I18N

2936

mbcset, &equiv_class_alloc,

2937

#endif /* RE_ENABLE_I18N */

2938

start_elem.opr.name);

2939

if (BE (*err != REG_NOERROR, 0))

2940

goto parse_bracket_exp_free_return;

2941

break;

2942

case COLL_SYM:

2943

*err = build_collating_symbol (sbcset,

2944

#ifdef RE_ENABLE_I18N

2945

mbcset, &coll_sym_alloc,

2946

#endif /* RE_ENABLE_I18N */

2947

start_elem.opr.name);

2948

if (BE (*err != REG_NOERROR, 0))

2949

goto parse_bracket_exp_free_return;

2950

break;

2951

case CHAR_CLASS:

2952

*err = build_charclass (sbcset,

2953

#ifdef RE_ENABLE_I18N

2954

mbcset, &char_class_alloc,

2955

#endif /* RE_ENABLE_I18N */

2956

start_elem.opr.name, syntax);

2957

if (BE (*err != REG_NOERROR, 0))

2958

goto parse_bracket_exp_free_return;

2959

break;

2960

default:

2961

assert (0);

2962

break;

2963

}

2964

}

2965

if (token->type == OP_CLOSE_BRACKET)

2966

break;

2967

}

2968

2969

re_string_skip_bytes (regexp, token_len); /* Skip a token. */

2970

2971

/* If it is non-matching list. */

2972

#ifdef RE_ENABLE_I18N

2973

if (mbcset->non_match)

2974

#else /* not RE_ENABLE_I18N */

2975

if (non_match)

2976

#endif /* not RE_ENABLE_I18N */

2977

bitset_not (sbcset);

2978

2979

/* Build a tree for simple bracket. */

2980

br_token.type = SIMPLE_BRACKET;

2981

br_token.opr.sbcset = sbcset;

2982

new_idx = re_dfa_add_node (dfa, br_token, 0);

2983

work_tree = create_tree (NULL, NULL, 0, new_idx);

2984

if (BE (new_idx == -1 || work_tree == NULL, 0))

2985

goto parse_bracket_exp_espace;

2986

2987

#ifdef RE_ENABLE_I18N

2988

if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes

2989

|| mbcset->nranges || (MB_CUR_MAX > 1 && (mbcset->nchar_classes

2990

|| mbcset->non_match)))

2991

{

2992

re_token_t alt_token;

2993

bin_tree_t *mbc_tree;

2994

/* Build a tree for complex bracket. */

2995

br_token.type = COMPLEX_BRACKET;

2996

br_token.opr.mbcset = mbcset;

2997

dfa->has_mb_node = 1;

2998

new_idx = re_dfa_add_node (dfa, br_token, 0);

2999

mbc_tree = create_tree (NULL, NULL, 0, new_idx);

3000

if (BE (new_idx == -1 || mbc_tree == NULL, 0))

3001

goto parse_bracket_exp_espace;

3002

/* Then join them by ALT node. */

3003

dfa->has_plural_match = 1;

3004

alt_token.type = OP_ALT;

3005

new_idx = re_dfa_add_node (dfa, alt_token, 0);

3006

work_tree = create_tree (work_tree, mbc_tree, 0, new_idx);

3007

if (BE (new_idx != -1 && mbc_tree != NULL, 1))

3008

return work_tree;

3009

}

3010

else

3011

{

3012

free_charset (mbcset);

3013

return work_tree;

3014

}

3015

#else /* not RE_ENABLE_I18N */

3016

return work_tree;

3017

#endif /* not RE_ENABLE_I18N */

3018

3019

parse_bracket_exp_espace:

3020

*err = REG_ESPACE;

3021

parse_bracket_exp_free_return:

3022

re_free (sbcset);

3023

#ifdef RE_ENABLE_I18N

3024

free_charset (mbcset);

3025

#endif /* RE_ENABLE_I18N */

3026

return NULL;

3027

}

3028

3029

/* Parse an element in the bracket expression. */

3030

3031

static reg_errcode_t

3032

parse_bracket_element (elem, regexp, token, token_len, dfa, syntax)

3033

bracket_elem_t *elem;

3034

re_string_t *regexp;

3035

re_token_t *token;

3036

int token_len;

3037

re_dfa_t *dfa;

3038

reg_syntax_t syntax;

3039

{

3040

#ifdef RE_ENABLE_I18N

3041

int cur_char_size;

3042

cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));

3043

if (cur_char_size > 1)

3044

{

3045

elem->type = MB_CHAR;

3046

elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));

3047

re_string_skip_bytes (regexp, cur_char_size);

3048

return REG_NOERROR;

3049

}

3050

#endif /* RE_ENABLE_I18N */

3051

re_string_skip_bytes (regexp, token_len); /* Skip a token. */

3052

if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS

3053

|| token->type == OP_OPEN_EQUIV_CLASS)

3054

return parse_bracket_symbol (elem, regexp, token);

3055

elem->type = SB_CHAR;

3056

elem->opr.ch = token->opr.c;

3057

return REG_NOERROR;

3058

}

3059

3060

/* Parse a bracket symbol in the bracket expression. Bracket symbols are

3061

such as [:<character_class>:], [.<collating_element>.], and

3062

[=<equivalent_class>=]. */

3063

3064

static reg_errcode_t

3065

parse_bracket_symbol (elem, regexp, token)

3066

bracket_elem_t *elem;

3067

re_string_t *regexp;

3068

re_token_t *token;

3069

{

3070

unsigned char ch, delim = token->opr.c;

3071

int i = 0;

3072

for (;; ++i)

3073

{

3074

if (re_string_eoi(regexp) || i >= BRACKET_NAME_BUF_SIZE)

3075

return REG_EBRACK;

3076

if (token->type == OP_OPEN_CHAR_CLASS)

3077

ch = re_string_fetch_byte_case (regexp);

3078

else

3079

ch = re_string_fetch_byte (regexp);

3080

if (ch == delim && re_string_peek_byte (regexp, 0) == ']')

3081

break;

3082

elem->opr.name[i] = ch;

3083

}

3084

re_string_skip_bytes (regexp, 1);

3085

elem->opr.name[i] = '\0';

3086

switch (token->type)

3087

{

3088

case OP_OPEN_COLL_ELEM:

3089

elem->type = COLL_SYM;

3090

break;

3091

case OP_OPEN_EQUIV_CLASS:

3092

elem->type = EQUIV_CLASS;

3093

break;

3094

case OP_OPEN_CHAR_CLASS:

3095

elem->type = CHAR_CLASS;

3096

break;

3097

default:

3098

break;

3099

}

3100

return REG_NOERROR;

3101

}

3102

3103

/* Helper function for parse_bracket_exp.

3104

Build the equivalence class which is represented by NAME.

3105

The result are written to MBCSET and SBCSET.

3106

EQUIV_CLASS_ALLOC is the allocated size of mbcset->equiv_classes,

3107

is a pointer argument sinse we may update it. */

3108

3109

static reg_errcode_t

3110

#ifdef RE_ENABLE_I18N

3111

build_equiv_class (sbcset, mbcset, equiv_class_alloc, name)

3112

re_charset_t *mbcset;

3113

int *equiv_class_alloc;

3114

#else /* not RE_ENABLE_I18N */

3115

build_equiv_class (sbcset, name)

3116

#endif /* not RE_ENABLE_I18N */

3117

re_bitset_ptr_t sbcset;

3118

const unsigned char *name;

3119

{

3120

#if defined _LIBC && defined RE_ENABLE_I18N

3121

uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);

3122

if (nrules != 0)

3123

{

3124

const int32_t *table, *indirect;

3125

const unsigned char *weights, *extra, *cp;

3126

unsigned char char_buf[2];

3127

int32_t idx1, idx2;

3128

unsigned int ch;

3129

size_t len;

3130

/* This #include defines a local function! */

3131

# include <locale/weight.h>

3132

/* Calculate the index for equivalence class. */

3133

cp = name;

3134

table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);

3135

weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE,

3136

_NL_COLLATE_WEIGHTMB);

3137

extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,

3138

_NL_COLLATE_EXTRAMB);

3139

indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,

3140

_NL_COLLATE_INDIRECTMB);

3141

idx1 = findidx (&cp);

3142

if (BE (idx1 == 0 || cp < name + strlen ((const char *) name), 0))

3143

/* This isn't a valid character. */

3144

return REG_ECOLLATE;

3145

3146

/* Build single byte matcing table for this equivalence class. */

3147

char_buf[1] = (unsigned char) '\0';

3148

len = weights[idx1];

3149

for (ch = 0; ch < SBC_MAX; ++ch)

3150

{

3151

char_buf[0] = ch;

3152

cp = char_buf;

3153

idx2 = findidx (&cp);

3154

/*

3155

idx2 = table[ch];

3156

*/

3157

if (idx2 == 0)

3158

/* This isn't a valid character. */

3159

continue;

3160

if (len == weights[idx2])

3161

{

3162

int cnt = 0;

3163

while (cnt <= len &&

3164

weights[idx1 + 1 + cnt] == weights[idx2 + 1 + cnt])

3165

++cnt;

3166

3167

if (cnt > len)

3168

bitset_set (sbcset, ch);

3169

}

3170

}

3171

/* Check whether the array has enough space. */

3172

if (*equiv_class_alloc == mbcset->nequiv_classes)

3173

{

3174

/* Not enough, realloc it. */

3175

/* +1 in case of mbcset->nequiv_classes is 0. */

3176

*equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;

3177

/* Use realloc since the array is NULL if *alloc == 0. */

3178

mbcset->equiv_classes = re_realloc (mbcset->equiv_classes, int32_t,

3179

*equiv_class_alloc);

3180

if (BE (mbcset->equiv_classes == NULL, 0))

3181

return REG_ESPACE;

3182

}

3183

mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1;

3184

}

3185

else

3186

#endif /* _LIBC && RE_ENABLE_I18N */

3187

{

3188

if (BE (strlen ((const char *) name) != 1, 0))

3189

return REG_ECOLLATE;

3190

bitset_set (sbcset, *name);

3191

}

3192

return REG_NOERROR;

3193

}

3194

3195

/* Helper function for parse_bracket_exp.

3196

Build the character class which is represented by NAME.

3197

The result are written to MBCSET and SBCSET.

3198

CHAR_CLASS_ALLOC is the allocated size of mbcset->char_classes,

3199

is a pointer argument sinse we may update it. */

3200

3201

static reg_errcode_t

3202

#ifdef RE_ENABLE_I18N

3203

build_charclass (sbcset, mbcset, char_class_alloc, class_name, syntax)

3204

re_charset_t *mbcset;

3205

int *char_class_alloc;

3206

#else /* not RE_ENABLE_I18N */

3207

build_charclass (sbcset, class_name, syntax)

3208

#endif /* not RE_ENABLE_I18N */

3209

re_bitset_ptr_t sbcset;

3210

const unsigned char *class_name;

3211

reg_syntax_t syntax;

3212

{

3213

int i;

3214

const char *name = (const char *) class_name;

3215

3216

/* In case of REG_ICASE "upper" and "lower" match the both of

3217

upper and lower cases. */

3218

if ((syntax & RE_ICASE)

3219

&& (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0))

3220

name = "alpha";

3221

3222

#ifdef RE_ENABLE_I18N

3223

/* Check the space of the arrays. */

3224

if (*char_class_alloc == mbcset->nchar_classes)

3225

{

3226

/* Not enough, realloc it. */

3227

/* +1 in case of mbcset->nchar_classes is 0. */

3228

*char_class_alloc = 2 * mbcset->nchar_classes + 1;

3229

/* Use realloc since array is NULL if *alloc == 0. */

3230

mbcset->char_classes = re_realloc (mbcset->char_classes, wctype_t,

3231

*char_class_alloc);

3232

if (BE (mbcset->char_classes == NULL, 0))

3233

return REG_ESPACE;

3234

}

3235

mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name);

3236

#endif /* RE_ENABLE_I18N */

3237

3238

#define BUILD_CHARCLASS_LOOP(ctype_func)\

3239

for (i = 0; i < SBC_MAX; ++i) \

3240

{ \

3241

if (ctype_func (i)) \

3242

bitset_set (sbcset, i); \

3243

}

3244

3245

if (strcmp (name, "alnum") == 0)

3246

BUILD_CHARCLASS_LOOP (isalnum)

3247

else if (strcmp (name, "cntrl") == 0)

3248

BUILD_CHARCLASS_LOOP (iscntrl)

3249

else if (strcmp (name, "lower") == 0)

3250

BUILD_CHARCLASS_LOOP (islower)

3251

else if (strcmp (name, "space") == 0)

3252

BUILD_CHARCLASS_LOOP (isspace)

3253

else if (strcmp (name, "alpha") == 0)

3254

BUILD_CHARCLASS_LOOP (isalpha)

3255

else if (strcmp (name, "digit") == 0)

3256

BUILD_CHARCLASS_LOOP (isdigit)

3257

else if (strcmp (name, "print") == 0)

3258

BUILD_CHARCLASS_LOOP (isprint)

3259

else if (strcmp (name, "upper") == 0)

3260

BUILD_CHARCLASS_LOOP (isupper)

3261

else if (strcmp (name, "blank") == 0)

3262

BUILD_CHARCLASS_LOOP (isblank)

3263

else if (strcmp (name, "graph") == 0)

3264

BUILD_CHARCLASS_LOOP (isgraph)

3265

else if (strcmp (name, "punct") == 0)

3266

BUILD_CHARCLASS_LOOP (ispunct)

3267

else if (strcmp (name, "xdigit") == 0)

3268

BUILD_CHARCLASS_LOOP (isxdigit)

3269

else

3270

return REG_ECTYPE;

3271

3272

return REG_NOERROR;

3273

}

3274

3275

static bin_tree_t *

3276

build_word_op (dfa, not, err)

3277

re_dfa_t *dfa;

3278

int not;

3279

reg_errcode_t *err;

3280

{

3281

re_bitset_ptr_t sbcset;

3282

#ifdef RE_ENABLE_I18N

3283

re_charset_t *mbcset;

3284

int alloc = 0;

3285

#else /* not RE_ENABLE_I18N */

3286

int non_match = 0;

3287

#endif /* not RE_ENABLE_I18N */

3288

reg_errcode_t ret;

3289

re_token_t br_token;

3290

bin_tree_t *tree;

3291

int new_idx;

3292

3293

sbcset = (re_bitset_ptr_t) calloc (sizeof (unsigned int), BITSET_UINTS);

3294

#ifdef RE_ENABLE_I18N

3295

mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);

3296

#endif /* RE_ENABLE_I18N */

3297

3298

#ifdef RE_ENABLE_I18N

3299

if (BE (sbcset == NULL || mbcset == NULL, 0))

3300

#else /* not RE_ENABLE_I18N */

3301

if (BE (sbcset == NULL, 0))

3302

#endif /* not RE_ENABLE_I18N */

3303

{

3304

*err = REG_ESPACE;

3305

return NULL;

3306

}

3307

3308

if (not)

3309

{

3310

#ifdef RE_ENABLE_I18N

3311

int i;

3312

/*

3313

if (syntax & RE_HAT_LISTS_NOT_NEWLINE)

3314

bitset_set(cset->sbcset, '\0');

3315

*/

3316

mbcset->non_match = 1;

3317

if (MB_CUR_MAX > 1)

3318

for (i = 0; i < SBC_MAX; ++i)

3319

if (__btowc (i) == WEOF)

3320

bitset_set (sbcset, i);

3321

#else /* not RE_ENABLE_I18N */

3322

non_match = 1;

3323

#endif /* not RE_ENABLE_I18N */

3324

}

3325

3326

/* We don't care the syntax in this case. */

3327

ret = build_charclass (sbcset,

3328

#ifdef RE_ENABLE_I18N

3329

mbcset, &alloc,

3330

#endif /* RE_ENABLE_I18N */

3331

(const unsigned char *) "alpha", 0);

3332

3333

if (BE (ret != REG_NOERROR, 0))

3334

{

3335

re_free (sbcset);

3336

#ifdef RE_ENABLE_I18N

3337

free_charset (mbcset);

3338

#endif /* RE_ENABLE_I18N */

3339

*err = ret;

3340

return NULL;

3341

}

3342

/* \w match '_' also. */

3343

bitset_set (sbcset, '_');

3344

3345

/* If it is non-matching list. */

3346

#ifdef RE_ENABLE_I18N

3347

if (mbcset->non_match)

3348

#else /* not RE_ENABLE_I18N */

3349

if (non_match)

3350

#endif /* not RE_ENABLE_I18N */

3351

bitset_not (sbcset);

3352

3353

/* Build a tree for simple bracket. */

3354

br_token.type = SIMPLE_BRACKET;

3355

br_token.opr.sbcset = sbcset;

3356

new_idx = re_dfa_add_node (dfa, br_token, 0);

3357

tree = create_tree (NULL, NULL, 0, new_idx);

3358

if (BE (new_idx == -1 || tree == NULL, 0))

3359

goto build_word_op_espace;

3360

3361

#ifdef RE_ENABLE_I18N

3362

if (MB_CUR_MAX > 1)

3363

{

3364

re_token_t alt_token;

3365

bin_tree_t *mbc_tree;

3366

/* Build a tree for complex bracket. */

3367

br_token.type = COMPLEX_BRACKET;

3368

br_token.opr.mbcset = mbcset;

3369

dfa->has_mb_node = 1;

3370

new_idx = re_dfa_add_node (dfa, br_token, 0);

3371

mbc_tree = create_tree (NULL, NULL, 0, new_idx);

3372

if (BE (new_idx == -1 || mbc_tree == NULL, 0))

3373

goto build_word_op_espace;

3374

/* Then join them by ALT node. */

3375

alt_token.type = OP_ALT;

3376

new_idx = re_dfa_add_node (dfa, alt_token, 0);

3377

tree = create_tree (tree, mbc_tree, 0, new_idx);

3378

if (BE (new_idx != -1 && mbc_tree != NULL, 1))

3379

return tree;

3380

}

3381

else

3382

{

3383

free_charset (mbcset);

3384

return tree;

3385

}

3386

#else /* not RE_ENABLE_I18N */

3387

return tree;

3388

#endif /* not RE_ENABLE_I18N */

3389

3390

build_word_op_espace:

3391

re_free (sbcset);

3392

#ifdef RE_ENABLE_I18N

3393

free_charset (mbcset);

3394

#endif /* RE_ENABLE_I18N */

3395

*err = REG_ESPACE;

3396

return NULL;

3397

}

3398

3399

/* This is intended for the expressions like "a{1,3}".

3400

Fetch a number from `input', and return the number.

3401

Return -1, if the number field is empty like "{,1}".

3402

Return -2, If an error is occured. */

3403

3404

static int

3405

fetch_number (input, token, syntax)

3406

re_string_t *input;

3407

re_token_t *token;

3408

reg_syntax_t syntax;

3409

{

3410

int num = -1;

3411

unsigned char c;

3412

while (1)

3413

{

3414

*token = fetch_token (input, syntax);

3415

c = token->opr.c;

3416

if (BE (token->type == END_OF_RE, 0))

3417

return -2;

3418

if (token->type == OP_CLOSE_DUP_NUM || c == ',')

3419

break;

3420

num = ((token->type != CHARACTER || c < '0' || '9' < c || num == -2)

3421

? -2 : ((num == -1) ? c - '0' : num * 10 + c - '0'));

3422

num = (num > RE_DUP_MAX) ? -2 : num;

3423

}

3424

return num;

3425

}

3426

3427

#ifdef RE_ENABLE_I18N

3428

static void

3429

free_charset (re_charset_t *cset)

3430

{

3431

re_free (cset->mbchars);

3432

# ifdef _LIBC

3433

re_free (cset->coll_syms);

3434

re_free (cset->equiv_classes);

3435

re_free (cset->range_starts);

3436

re_free (cset->range_ends);

3437

# endif

3438

re_free (cset->char_classes);

3439

re_free (cset);

3440

}

3441

#endif /* RE_ENABLE_I18N */

3442

3443

/* Functions for binary tree operation. */

3444

3445

/* Create a node of tree.

3446

Note: This function automatically free left and right if malloc fails. */

3447

3448

static bin_tree_t *

3449

create_tree (left, right, type, index)

3450

bin_tree_t *left;

3451

bin_tree_t *right;

3452

re_token_type_t type;

3453

int index;

3454

{

3455

bin_tree_t *tree;

3456

tree = re_malloc (bin_tree_t, 1);

3457

if (BE (tree == NULL, 0))

3458

{

3459

free_bin_tree (left);

3460

free_bin_tree (right);

3461

return NULL;

3462

}

3463

tree->parent = NULL;

3464

tree->left = left;

3465

tree->right = right;

3466

tree->type = type;

3467

tree->node_idx = index;

3468

tree->first = -1;

3469

tree->next = -1;

3470

re_node_set_init_empty (&tree->eclosure);

3471

3472

if (left != NULL)

3473

left->parent = tree;

3474

if (right != NULL)

3475

right->parent = tree;

3476

return tree;

3477

}

3478

3479

/* Free the sub tree pointed by TREE. */

3480

3481

static void

3482

free_bin_tree (tree)

3483

bin_tree_t *tree;

3484

{

3485

if (tree == NULL)

3486

return;

3487

/*re_node_set_free (&tree->eclosure);*/

3488

free_bin_tree (tree->left);

3489

free_bin_tree (tree->right);

3490

re_free (tree);

3491

}

3492

3493

/* Duplicate the node SRC, and return new node. */

3494

3495

static bin_tree_t *

3496

duplicate_tree (src, dfa)

3497

const bin_tree_t *src;

3498

re_dfa_t *dfa;

3499

{

3500

bin_tree_t *left = NULL, *right = NULL, *new_tree;

3501

int new_node_idx;

3502

/* Since node indies must be according to Post-order of the tree,

3503

we must duplicate the left at first. */

3504

if (src->left != NULL)

3505

{

3506

left = duplicate_tree (src->left, dfa);

3507

if (left == NULL)

3508

return NULL;

3509

}

3510

3511

/* Secondaly, duplicate the right. */

3512

if (src->right != NULL)

3513

{

3514

right = duplicate_tree (src->right, dfa);

3515

if (right == NULL)

3516

{

3517

free_bin_tree (left);

3518

return NULL;

3519

}

3520

}

3521

3522

/* At last, duplicate itself. */

3523

if (src->type == NON_TYPE)

3524

{

3525

new_node_idx = re_dfa_add_node (dfa, dfa->nodes[src->node_idx], 0);

3526

dfa->nodes[new_node_idx].duplicated = 1;

3527

if (BE (new_node_idx == -1, 0))

3528

{

3529

free_bin_tree (left);

3530

free_bin_tree (right);

3531

return NULL;

3532

}

3533

}

3534

else

3535

new_node_idx = src->type;

3536

3537

new_tree = create_tree (left, right, src->type, new_node_idx);

3538

if (BE (new_tree == NULL, 0))

3539

{

3540

free_bin_tree (left);

3541

free_bin_tree (right);

3542

}

3543

return new_tree;

3544

}