cpython/Modules/_sre.c at v2.4 · python/cpython

Repository navigation

History

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

481

482

483

484

485

486

487

488

489

490

491

492

493

494

495

496

497

498

499

500

501

502

503

504

505

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

530

531

532

533

534

535

536

537

538

539

540

541

542

543

544

545

546

547

548

549

550

551

552

553

554

555

556

557

558

559

560

561

562

563

564

565

566

567

568

569

570

571

572

573

574

575

576

577

578

579

580

581

582

583

584

585

586

587

588

589

590

591

592

593

594

595

596

597

598

599

600

601

602

603

604

605

606

607

608

609

610

611

612

613

614

615

616

617

618

619

620

621

622

623

624

625

626

627

628

629

630

631

632

633

634

635

636

637

638

639

640

641

642

643

644

645

646

647

648

649

650

651

652

653

654

655

656

657

658

659

660

661

662

663

664

665

666

667

668

669

670

671

672

673

674

675

676

677

678

679

680

681

682

683

684

685

686

687

688

689

690

691

692

693

694

695

696

697

698

699

700

701

702

703

704

705

706

707

708

709

710

711

712

713

714

715

716

717

718

719

720

721

722

723

724

725

726

727

728

729

730

731

732

733

734

735

736

737

738

739

740

741

742

743

744

745

746

747

748

749

750

751

752

753

754

755

756

757

758

759

760

761

762

763

764

765

766

767

768

769

770

771

772

773

774

775

776

777

778

779

780

781

782

783

784

785

786

787

788

789

790

791

792

793

794

795

796

797

798

799

800

801

802

803

804

805

806

807

808

809

810

811

812

813

814

815

816

817

818

819

820

821

822

823

824

825

826

827

828

829

830

831

832

833

834

835

836

837

838

839

840

841

842

843

844

845

846

847

848

849

850

851

852

853

854

855

856

857

858

859

860

861

862

863

864

865

866

867

868

869

870

871

872

873

874

875

876

877

878

879

880

881

882

883

884

885

886

887

888

889

890

891

892

893

894

895

896

897

898

899

900

901

902

903

904

905

906

907

908

909

910

911

912

913

914

915

916

917

918

919

920

921

922

923

924

925

926

927

928

929

930

931

932

933

934

935

936

937

938

939

940

941

942

943

944

945

946

947

948

949

950

951

952

953

954

955

956

957

958

959

960

961

962

963

964

965

966

967

968

969

970

971

972

973

974

975

976

977

978

979

980

981

982

983

984

985

986

987

988

989

990

991

992

993

994

995

996

997

998

999

1000

* Secret Labs' Regular Expression Engine

* regular expression matching engine

* partial history:

* 1999-10-24 fl created (based on existing template matcher code)

* 2000-03-06 fl first alpha, sort of

* 2000-08-01 fl fixes for 1.6b1

* 2000-08-07 fl use PyOS_CheckStack() if available

* 2000-09-20 fl added expand method

* 2001-03-20 fl lots of fixes for 2.1b2

* 2001-04-15 fl export copyright as Python attribute, not global

* 2001-04-28 fl added __copy__ methods (work in progress)

* 2001-05-14 fl fixes for 1.5.2 compatibility

* 2001-07-01 fl added BIGCHARSET support (from Martin von Loewis)

* 2001-10-18 fl fixed group reset issue (from Matthew Mueller)

* 2001-10-20 fl added split primitive; reenable unicode for 1.6/2.0/2.1

* 2001-10-21 fl added sub/subn primitive

* 2001-10-24 fl added finditer primitive (for 2.2 only)

* 2001-12-07 fl fixed memory leak in sub/subn (Guido van Rossum)

* 2002-11-09 fl fixed empty sub/subn return type

* 2003-04-18 mvl fully support 4-byte codes

* 2003-10-17 gn implemented non recursive scheme

* This version of the SRE library can be redistributed under CNRI's

* Python 1.6 license. For any other use, please contact Secret Labs

* AB (info@pythonware.com).

* Portions of this engine have been developed in cooperation with

* CNRI. Hewlett-Packard provided funding for 1.6 integration and

* other compatibility work.

#ifndef SRE_RECURSIVE

static char copyright[] =

#include "Python.h"

#include "structmember.h" /* offsetof */

#include "sre.h"

#include <ctype.h>

/* name of this module, minus the leading underscore */

#if !defined(SRE_MODULE)

#define SRE_MODULE "sre"

#endif

/* defining this one enables tracing */

#undef VERBOSE

#if PY_VERSION_HEX >= 0x01060000

#if PY_VERSION_HEX < 0x02020000 || defined(Py_USING_UNICODE)

/* defining this enables unicode support (default under 1.6a1 and later) */

#define HAVE_UNICODE

#endif

/* -------------------------------------------------------------------- */

/* optional features */

/* enables fast searching */

#define USE_FAST_SEARCH

/* enables aggressive inlining (always on for Visual C) */

#undef USE_INLINE

/* enables copy/deepcopy handling (work in progress) */

#undef USE_BUILTIN_COPY

#if PY_VERSION_HEX < 0x01060000

#define PyObject_DEL(op) PyMem_DEL((op))

#endif

/* -------------------------------------------------------------------- */

#if defined(_MSC_VER)

#pragma optimize("agtw", on) /* doesn't seem to make much difference... */

#pragma warning(disable: 4710) /* who cares if functions are not inlined ;-) */

/* fastest possible local call under MSVC */

#define LOCAL(type) static __inline type __fastcall

#elif defined(USE_INLINE)

#define LOCAL(type) static inline type

#else

#define LOCAL(type) static type

#endif

/* error codes */

#define SRE_ERROR_ILLEGAL -1 /* illegal opcode */

#define SRE_ERROR_STATE -2 /* illegal state */

#define SRE_ERROR_RECURSION_LIMIT -3 /* runaway recursion */

#define SRE_ERROR_MEMORY -9 /* out of memory */

#if defined(VERBOSE)

#define TRACE(v) printf v

#else

#define TRACE(v)

#endif

/* -------------------------------------------------------------------- */

/* search engine state */

/* default character predicates (run sre_chars.py to regenerate tables) */

#define SRE_DIGIT_MASK 1

#define SRE_SPACE_MASK 2

#define SRE_LINEBREAK_MASK 4

#define SRE_ALNUM_MASK 8

#define SRE_WORD_MASK 16

/* FIXME: this assumes ASCII. create tables in init_sre() instead */

static char sre_char_info[128] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 2,

2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0,

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 25, 25, 25, 25, 25, 25, 25, 25,

25, 25, 0, 0, 0, 0, 0, 0, 0, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,

24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 0, 0,

0, 0, 16, 0, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,

24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 0, 0, 0, 0, 0 };

static char sre_char_lower[128] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26,

27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,

44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60,

61, 62, 63, 64, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107,

108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121,

122, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105,

106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119,

120, 121, 122, 123, 124, 125, 126, 127 };

#define SRE_IS_DIGIT(ch)\

((ch) < 128 ? (sre_char_info[(ch)] & SRE_DIGIT_MASK) : 0)

#define SRE_IS_SPACE(ch)\

((ch) < 128 ? (sre_char_info[(ch)] & SRE_SPACE_MASK) : 0)

#define SRE_IS_LINEBREAK(ch)\

((ch) < 128 ? (sre_char_info[(ch)] & SRE_LINEBREAK_MASK) : 0)

#define SRE_IS_ALNUM(ch)\

((ch) < 128 ? (sre_char_info[(ch)] & SRE_ALNUM_MASK) : 0)

#define SRE_IS_WORD(ch)\

((ch) < 128 ? (sre_char_info[(ch)] & SRE_WORD_MASK) : 0)

static unsigned int sre_lower(unsigned int ch)

{

return ((ch) < 128 ? (unsigned int)sre_char_lower[ch] : ch);

}

/* locale-specific character predicates */

/* !(c & ~N) == (c < N+1) for any unsigned c, this avoids

* warnings when c's type supports only numbers < N+1 */

#define SRE_LOC_IS_DIGIT(ch) (!((ch) & ~255) ? isdigit((ch)) : 0)

#define SRE_LOC_IS_SPACE(ch) (!((ch) & ~255) ? isspace((ch)) : 0)

#define SRE_LOC_IS_LINEBREAK(ch) ((ch) == '\n')

#define SRE_LOC_IS_ALNUM(ch) (!((ch) & ~255) ? isalnum((ch)) : 0)

#define SRE_LOC_IS_WORD(ch) (SRE_LOC_IS_ALNUM((ch)) || (ch) == '_')

static unsigned int sre_lower_locale(unsigned int ch)

{

return ((ch) < 256 ? (unsigned int)tolower((ch)) : ch);

}

/* unicode-specific character predicates */

#if defined(HAVE_UNICODE)

#define SRE_UNI_IS_DIGIT(ch) Py_UNICODE_ISDIGIT((Py_UNICODE)(ch))

#define SRE_UNI_IS_SPACE(ch) Py_UNICODE_ISSPACE((Py_UNICODE)(ch))

#define SRE_UNI_IS_LINEBREAK(ch) Py_UNICODE_ISLINEBREAK((Py_UNICODE)(ch))

#define SRE_UNI_IS_ALNUM(ch) Py_UNICODE_ISALNUM((Py_UNICODE)(ch))

#define SRE_UNI_IS_WORD(ch) (SRE_UNI_IS_ALNUM((ch)) || (ch) == '_')

static unsigned int sre_lower_unicode(unsigned int ch)

{

return (unsigned int) Py_UNICODE_TOLOWER((Py_UNICODE)(ch));

}

#endif

LOCAL(int)

sre_category(SRE_CODE category, unsigned int ch)

{

switch (category) {

case SRE_CATEGORY_DIGIT:

return SRE_IS_DIGIT(ch);

case SRE_CATEGORY_NOT_DIGIT:

return !SRE_IS_DIGIT(ch);

case SRE_CATEGORY_SPACE:

return SRE_IS_SPACE(ch);

case SRE_CATEGORY_NOT_SPACE:

return !SRE_IS_SPACE(ch);

case SRE_CATEGORY_WORD:

return SRE_IS_WORD(ch);

case SRE_CATEGORY_NOT_WORD:

return !SRE_IS_WORD(ch);

case SRE_CATEGORY_LINEBREAK:

return SRE_IS_LINEBREAK(ch);

case SRE_CATEGORY_NOT_LINEBREAK:

return !SRE_IS_LINEBREAK(ch);

case SRE_CATEGORY_LOC_WORD:

return SRE_LOC_IS_WORD(ch);

case SRE_CATEGORY_LOC_NOT_WORD:

return !SRE_LOC_IS_WORD(ch);

#if defined(HAVE_UNICODE)

case SRE_CATEGORY_UNI_DIGIT:

return SRE_UNI_IS_DIGIT(ch);

case SRE_CATEGORY_UNI_NOT_DIGIT:

return !SRE_UNI_IS_DIGIT(ch);

case SRE_CATEGORY_UNI_SPACE:

return SRE_UNI_IS_SPACE(ch);

case SRE_CATEGORY_UNI_NOT_SPACE:

return !SRE_UNI_IS_SPACE(ch);

case SRE_CATEGORY_UNI_WORD:

return SRE_UNI_IS_WORD(ch);

case SRE_CATEGORY_UNI_NOT_WORD:

return !SRE_UNI_IS_WORD(ch);

case SRE_CATEGORY_UNI_LINEBREAK:

return SRE_UNI_IS_LINEBREAK(ch);

case SRE_CATEGORY_UNI_NOT_LINEBREAK:

return !SRE_UNI_IS_LINEBREAK(ch);

#else

case SRE_CATEGORY_UNI_DIGIT:

return SRE_IS_DIGIT(ch);

case SRE_CATEGORY_UNI_NOT_DIGIT:

return !SRE_IS_DIGIT(ch);

case SRE_CATEGORY_UNI_SPACE:

return SRE_IS_SPACE(ch);

case SRE_CATEGORY_UNI_NOT_SPACE:

return !SRE_IS_SPACE(ch);

case SRE_CATEGORY_UNI_WORD:

return SRE_LOC_IS_WORD(ch);

case SRE_CATEGORY_UNI_NOT_WORD:

return !SRE_LOC_IS_WORD(ch);

case SRE_CATEGORY_UNI_LINEBREAK:

return SRE_IS_LINEBREAK(ch);

case SRE_CATEGORY_UNI_NOT_LINEBREAK:

return !SRE_IS_LINEBREAK(ch);

#endif

}

return 0;

}

/* helpers */

static void

data_stack_dealloc(SRE_STATE* state)

{

if (state->data_stack) {

free(state->data_stack);

state->data_stack = NULL;

}

state->data_stack_size = state->data_stack_base = 0;

}

static int

data_stack_grow(SRE_STATE* state, int size)

{

int minsize, cursize;

minsize = state->data_stack_base+size;

cursize = state->data_stack_size;

if (cursize < minsize) {

void* stack;

cursize = minsize+minsize/4+1024;

TRACE(("allocate/grow stack %d\n", cursize));

stack = realloc(state->data_stack, cursize);

if (!stack) {

data_stack_dealloc(state);

return SRE_ERROR_MEMORY;

}

state->data_stack = stack;

state->data_stack_size = cursize;

}

return 0;

}

/* generate 8-bit version */

#define SRE_CHAR unsigned char

#define SRE_AT sre_at

#define SRE_COUNT sre_count

#define SRE_CHARSET sre_charset

#define SRE_INFO sre_info

#define SRE_MATCH sre_match

#define SRE_MATCH_CONTEXT sre_match_context

#define SRE_SEARCH sre_search

#define SRE_LITERAL_TEMPLATE sre_literal_template

#if defined(HAVE_UNICODE)

#define SRE_RECURSIVE

#include "_sre.c"

#undef SRE_RECURSIVE

#undef SRE_LITERAL_TEMPLATE

#undef SRE_SEARCH

#undef SRE_MATCH

#undef SRE_MATCH_CONTEXT

#undef SRE_INFO

#undef SRE_CHARSET

#undef SRE_COUNT

#undef SRE_AT

#undef SRE_CHAR

/* generate 16-bit unicode version */

#define SRE_CHAR Py_UNICODE

#define SRE_AT sre_uat

#define SRE_COUNT sre_ucount

#define SRE_CHARSET sre_ucharset

#define SRE_INFO sre_uinfo

#define SRE_MATCH sre_umatch

#define SRE_MATCH_CONTEXT sre_umatch_context

#define SRE_SEARCH sre_usearch

#define SRE_LITERAL_TEMPLATE sre_uliteral_template

#endif

#endif /* SRE_RECURSIVE */

/* -------------------------------------------------------------------- */

/* String matching engine */

/* the following section is compiled twice, with different character

settings */

LOCAL(int)

SRE_AT(SRE_STATE* state, SRE_CHAR* ptr, SRE_CODE at)

{

/* check if pointer is at given position */

int this, that;

switch (at) {

case SRE_AT_BEGINNING:

case SRE_AT_BEGINNING_STRING:

return ((void*) ptr == state->beginning);

case SRE_AT_BEGINNING_LINE:

return ((void*) ptr == state->beginning ||

SRE_IS_LINEBREAK((int) ptr[-1]));

case SRE_AT_END:

return (((void*) (ptr+1) == state->end &&

SRE_IS_LINEBREAK((int) ptr[0])) ||

((void*) ptr == state->end));

case SRE_AT_END_LINE:

return ((void*) ptr == state->end ||

SRE_IS_LINEBREAK((int) ptr[0]));

case SRE_AT_END_STRING:

return ((void*) ptr == state->end);

case SRE_AT_BOUNDARY:

if (state->beginning == state->end)

return 0;

that = ((void*) ptr > state->beginning) ?

SRE_IS_WORD((int) ptr[-1]) : 0;

this = ((void*) ptr < state->end) ?

SRE_IS_WORD((int) ptr[0]) : 0;

return this != that;

case SRE_AT_NON_BOUNDARY:

if (state->beginning == state->end)

return 0;

that = ((void*) ptr > state->beginning) ?

SRE_IS_WORD((int) ptr[-1]) : 0;

this = ((void*) ptr < state->end) ?

SRE_IS_WORD((int) ptr[0]) : 0;

return this == that;

case SRE_AT_LOC_BOUNDARY:

if (state->beginning == state->end)

return 0;

that = ((void*) ptr > state->beginning) ?

SRE_LOC_IS_WORD((int) ptr[-1]) : 0;

this = ((void*) ptr < state->end) ?

SRE_LOC_IS_WORD((int) ptr[0]) : 0;

return this != that;

case SRE_AT_LOC_NON_BOUNDARY:

if (state->beginning == state->end)

return 0;

that = ((void*) ptr > state->beginning) ?

SRE_LOC_IS_WORD((int) ptr[-1]) : 0;

this = ((void*) ptr < state->end) ?

SRE_LOC_IS_WORD((int) ptr[0]) : 0;

return this == that;

#if defined(HAVE_UNICODE)

case SRE_AT_UNI_BOUNDARY:

if (state->beginning == state->end)

return 0;

that = ((void*) ptr > state->beginning) ?

SRE_UNI_IS_WORD((int) ptr[-1]) : 0;

this = ((void*) ptr < state->end) ?

SRE_UNI_IS_WORD((int) ptr[0]) : 0;

return this != that;

case SRE_AT_UNI_NON_BOUNDARY:

if (state->beginning == state->end)

return 0;

that = ((void*) ptr > state->beginning) ?

SRE_UNI_IS_WORD((int) ptr[-1]) : 0;

this = ((void*) ptr < state->end) ?

SRE_UNI_IS_WORD((int) ptr[0]) : 0;

return this == that;

#endif

}

return 0;

}

LOCAL(int)

SRE_CHARSET(SRE_CODE* set, SRE_CODE ch)

{

/* check if character is a member of the given set */

int ok = 1;

for (;;) {

switch (*set++) {

case SRE_OP_FAILURE:

return !ok;

case SRE_OP_LITERAL:

/* <LITERAL> <code> */

if (ch == set[0])

return ok;

set++;

break;

case SRE_OP_CATEGORY:

/* <CATEGORY> <code> */

if (sre_category(set[0], (int) ch))

return ok;

set += 1;

break;

case SRE_OP_CHARSET:

if (sizeof(SRE_CODE) == 2) {

/* <CHARSET> <bitmap> (16 bits per code word) */

if (ch < 256 && (set[ch >> 4] & (1 << (ch & 15))))

return ok;

set += 16;

}

else {

/* <CHARSET> <bitmap> (32 bits per code word) */

if (ch < 256 && (set[ch >> 5] & (1 << (ch & 31))))

return ok;

set += 8;

}

break;

case SRE_OP_RANGE:

/* <RANGE> <lower> <upper> */

if (set[0] <= ch && ch <= set[1])

return ok;

set += 2;

break;

case SRE_OP_NEGATE:

ok = !ok;

break;

case SRE_OP_BIGCHARSET:

/* <BIGCHARSET> <blockcount> <256 blockindices> <blocks> */

{

int count, block;

count = *(set++);

if (sizeof(SRE_CODE) == 2) {

block = ((unsigned char*)set)[ch >> 8];

set += 128;

if (set[block*16 + ((ch & 255)>>4)] & (1 << (ch & 15)))

return ok;

set += count*16;

}

else {

/* !(c & ~N) == (c < N+1) for any unsigned c, this avoids

* warnings when c's type supports only numbers < N+1 */

if (!(ch & ~65535))

block = ((unsigned char*)set)[ch >> 8];

else

block = -1;

set += 64;

if (block >=0 &&

(set[block*8 + ((ch & 255)>>5)] & (1 << (ch & 31))))

return ok;

set += count*8;

}

break;

}

default:

/* internal error -- there's not much we can do about it

here, so let's just pretend it didn't match... */

return 0;

}

LOCAL(int) SRE_MATCH(SRE_STATE* state, SRE_CODE* pattern);

LOCAL(int)

SRE_COUNT(SRE_STATE* state, SRE_CODE* pattern, int maxcount)

{

SRE_CODE chr;

SRE_CHAR* ptr = state->ptr;

SRE_CHAR* end = state->end;

int i;

/* adjust end */

if (maxcount < end - ptr && maxcount != 65535)

end = ptr + maxcount;

switch (pattern[0]) {

case SRE_OP_IN:

/* repeated set */

TRACE(("|%p|%p|COUNT IN\n", pattern, ptr));

while (ptr < end && SRE_CHARSET(pattern + 2, *ptr))

ptr++;

break;

case SRE_OP_ANY:

/* repeated dot wildcard. */

TRACE(("|%p|%p|COUNT ANY\n", pattern, ptr));

while (ptr < end && !SRE_IS_LINEBREAK(*ptr))

ptr++;

break;

case SRE_OP_ANY_ALL:

/* repeated dot wildcard. skip to the end of the target

string, and backtrack from there */

TRACE(("|%p|%p|COUNT ANY_ALL\n", pattern, ptr));

ptr = end;

break;

case SRE_OP_LITERAL:

/* repeated literal */

chr = pattern[1];

TRACE(("|%p|%p|COUNT LITERAL %d\n", pattern, ptr, chr));

while (ptr < end && (SRE_CODE) *ptr == chr)

ptr++;

break;

case SRE_OP_LITERAL_IGNORE:

/* repeated literal */

chr = pattern[1];

TRACE(("|%p|%p|COUNT LITERAL_IGNORE %d\n", pattern, ptr, chr));

while (ptr < end && (SRE_CODE) state->lower(*ptr) == chr)

ptr++;

break;

case SRE_OP_NOT_LITERAL:

/* repeated non-literal */

chr = pattern[1];

TRACE(("|%p|%p|COUNT NOT_LITERAL %d\n", pattern, ptr, chr));

while (ptr < end && (SRE_CODE) *ptr != chr)

ptr++;

break;

case SRE_OP_NOT_LITERAL_IGNORE:

/* repeated non-literal */

chr = pattern[1];

TRACE(("|%p|%p|COUNT NOT_LITERAL_IGNORE %d\n", pattern, ptr, chr));

while (ptr < end && (SRE_CODE) state->lower(*ptr) != chr)

ptr++;

break;

default:

/* repeated single character pattern */

TRACE(("|%p|%p|COUNT SUBPATTERN\n", pattern, ptr));

while ((SRE_CHAR*) state->ptr < end) {

i = SRE_MATCH(state, pattern);

if (i < 0)

return i;

if (!i)

break;

}

TRACE(("|%p|%p|COUNT %d\n", pattern, ptr,

(SRE_CHAR*) state->ptr - ptr));

return (SRE_CHAR*) state->ptr - ptr;

}

TRACE(("|%p|%p|COUNT %d\n", pattern, ptr, ptr - (SRE_CHAR*) state->ptr));

return ptr - (SRE_CHAR*) state->ptr;

}

#if 0 /* not used in this release */

LOCAL(int)

SRE_INFO(SRE_STATE* state, SRE_CODE* pattern)

{

/* check if an SRE_OP_INFO block matches at the current position.

returns the number of SRE_CODE objects to skip if successful, 0

if no match */

SRE_CHAR* end = state->end;

SRE_CHAR* ptr = state->ptr;

int i;

/* check minimal length */

if (pattern[3] && (end - ptr) < pattern[3])

return 0;

/* check known prefix */

if (pattern[2] & SRE_INFO_PREFIX && pattern[5] > 1) {

/* <length> <skip> <prefix data> <overlap data> */

for (i = 0; i < pattern[5]; i++)

if ((SRE_CODE) ptr[i] != pattern[7 + i])

return 0;

return pattern[0] + 2 * pattern[6];

}

return pattern[0];

}

#endif

/* The macros below should be used to protect recursive SRE_MATCH()

* calls that *failed* and do *not* return immediately (IOW, those

* that will backtrack). Explaining:

* - Recursive SRE_MATCH() returned true: that's usually a success

* (besides atypical cases like ASSERT_NOT), therefore there's no

* reason to restore lastmark;

* - Recursive SRE_MATCH() returned false but the current SRE_MATCH()

* is returning to the caller: If the current SRE_MATCH() is the

* top function of the recursion, returning false will be a matching

* failure, and it doesn't matter where lastmark is pointing to.

* If it's *not* the top function, it will be a recursive SRE_MATCH()

* failure by itself, and the calling SRE_MATCH() will have to deal

* with the failure by the same rules explained here (it will restore

* lastmark by itself if necessary);

* - Recursive SRE_MATCH() returned false, and will continue the

* outside 'for' loop: must be protected when breaking, since the next

* OP could potentially depend on lastmark;

* - Recursive SRE_MATCH() returned false, and will be called again

* inside a local for/while loop: must be protected between each

* loop iteration, since the recursive SRE_MATCH() could do anything,

* and could potentially depend on lastmark.

* For more information, check the discussion at SF patch #712900.

#define LASTMARK_SAVE() \

do { \

ctx->lastmark = state->lastmark; \

ctx->lastindex = state->lastindex; \

} while (0)

#define LASTMARK_RESTORE() \

do { \

state->lastmark = ctx->lastmark; \

state->lastindex = ctx->lastindex; \

} while (0)

#define RETURN_ERROR(i) do { return i; } while(0)

#define RETURN_FAILURE do { ret = 0; goto exit; } while(0)

#define RETURN_SUCCESS do { ret = 1; goto exit; } while(0)

#define RETURN_ON_ERROR(i) \

do { if (i < 0) RETURN_ERROR(i); } while (0)

#define RETURN_ON_SUCCESS(i) \

do { RETURN_ON_ERROR(i); if (i > 0) RETURN_SUCCESS; } while (0)

#define RETURN_ON_FAILURE(i) \

do { RETURN_ON_ERROR(i); if (i == 0) RETURN_FAILURE; } while (0)

#define SFY(x) #x

#define DATA_STACK_ALLOC(state, type, ptr) \

do { \

alloc_pos = state->data_stack_base; \

TRACE(("allocating %s in %d (%d)\n", \

SFY(type), alloc_pos, sizeof(type))); \

if (state->data_stack_size < alloc_pos+sizeof(type)) { \

int j = data_stack_grow(state, sizeof(type)); \

if (j < 0) return j; \

if (ctx_pos != -1) \

DATA_STACK_LOOKUP_AT(state, SRE_MATCH_CONTEXT, ctx, ctx_pos); \

} \

ptr = (type*)(state->data_stack+alloc_pos); \

state->data_stack_base += sizeof(type); \

} while (0)

#define DATA_STACK_LOOKUP_AT(state, type, ptr, pos) \

do { \

TRACE(("looking up %s at %d\n", SFY(type), pos)); \

ptr = (type*)(state->data_stack+pos); \

} while (0)

#define DATA_STACK_PUSH(state, data, size) \

do { \

TRACE(("copy data in %p to %d (%d)\n", \

data, state->data_stack_base, size)); \

if (state->data_stack_size < state->data_stack_base+size) { \

int j = data_stack_grow(state, size); \

if (j < 0) return j; \

if (ctx_pos != -1) \

DATA_STACK_LOOKUP_AT(state, SRE_MATCH_CONTEXT, ctx, ctx_pos); \

} \

memcpy(state->data_stack+state->data_stack_base, data, size); \

state->data_stack_base += size; \

} while (0)

#define DATA_STACK_POP(state, data, size, discard) \

do { \

TRACE(("copy data to %p from %d (%d)\n", \

data, state->data_stack_base-size, size)); \

memcpy(data, state->data_stack+state->data_stack_base-size, size); \

if (discard) \

state->data_stack_base -= size; \

} while (0)

#define DATA_STACK_POP_DISCARD(state, size) \

do { \

TRACE(("discard data from %d (%d)\n", \

state->data_stack_base-size, size)); \

state->data_stack_base -= size; \

} while(0)

#define DATA_PUSH(x) \

DATA_STACK_PUSH(state, (x), sizeof(*(x)))

#define DATA_POP(x) \

DATA_STACK_POP(state, (x), sizeof(*(x)), 1)

#define DATA_POP_DISCARD(x) \

DATA_STACK_POP_DISCARD(state, sizeof(*(x)))

#define DATA_ALLOC(t,p) \

DATA_STACK_ALLOC(state, t, p)

#define DATA_LOOKUP_AT(t,p,pos) \

DATA_STACK_LOOKUP_AT(state,t,p,pos)

#define MARK_PUSH(lastmark) \

do if (lastmark > 0) { \

i = lastmark; /* ctx->lastmark may change if reallocated */ \

DATA_STACK_PUSH(state, state->mark, (i+1)*sizeof(void*)); \

} while (0)

#define MARK_POP(lastmark) \

do if (lastmark > 0) { \

DATA_STACK_POP(state, state->mark, (lastmark+1)*sizeof(void*), 1); \

} while (0)

#define MARK_POP_KEEP(lastmark) \

do if (lastmark > 0) { \

DATA_STACK_POP(state, state->mark, (lastmark+1)*sizeof(void*), 0); \

} while (0)

#define MARK_POP_DISCARD(lastmark) \

do if (lastmark > 0) { \

DATA_STACK_POP_DISCARD(state, (lastmark+1)*sizeof(void*)); \

} while (0)

#define JUMP_NONE 0

#define JUMP_MAX_UNTIL_1 1

#define JUMP_MAX_UNTIL_2 2

#define JUMP_MAX_UNTIL_3 3

#define JUMP_MIN_UNTIL_1 4

#define JUMP_MIN_UNTIL_2 5

#define JUMP_MIN_UNTIL_3 6

#define JUMP_REPEAT 7

#define JUMP_REPEAT_ONE_1 8

#define JUMP_REPEAT_ONE_2 9

#define JUMP_MIN_REPEAT_ONE 10

#define JUMP_BRANCH 11

#define JUMP_ASSERT 12

#define JUMP_ASSERT_NOT 13

#define DO_JUMP(jumpvalue, jumplabel, nextpattern) \

DATA_ALLOC(SRE_MATCH_CONTEXT, nextctx); \

nextctx->last_ctx_pos = ctx_pos; \

nextctx->jump = jumpvalue; \

nextctx->pattern = nextpattern; \

ctx_pos = alloc_pos; \

ctx = nextctx; \

goto entrance; \

jumplabel: \

while (0) /* gcc doesn't like labels at end of scopes */ \

typedef struct {

int last_ctx_pos;

int jump;

SRE_CHAR* ptr;

SRE_CODE* pattern;

int count;

int lastmark;

int lastindex;

union {

SRE_CODE chr;

SRE_REPEAT* rep;

} u;

} SRE_MATCH_CONTEXT;

/* check if string matches the given pattern. returns <0 for

error, 0 for failure, and 1 for success */

LOCAL(int)

SRE_MATCH(SRE_STATE* state, SRE_CODE* pattern)

{

SRE_CHAR* end = state->end;

int alloc_pos, ctx_pos = -1;

int i, ret = 0;

int jump;

SRE_MATCH_CONTEXT* ctx;

SRE_MATCH_CONTEXT* nextctx;

TRACE(("|%p|%p|ENTER\n", pattern, state->ptr));

DATA_ALLOC(SRE_MATCH_CONTEXT, ctx);

ctx->last_ctx_pos = -1;

ctx->jump = JUMP_NONE;

ctx->pattern = pattern;

ctx_pos = alloc_pos;

entrance:

ctx->ptr = state->ptr;

if (ctx->pattern[0] == SRE_OP_INFO) {

/* optimization info block */

/* <INFO> <1=skip> <2=flags> <3=min> ... */

if (ctx->pattern[3] && (end - ctx->ptr) < ctx->pattern[3]) {

TRACE(("reject (got %d chars, need %d)\n",

(end - ctx->ptr), ctx->pattern[3]));

RETURN_FAILURE;

}

ctx->pattern += ctx->pattern[1] + 1;

}

for (;;) {

switch (*ctx->pattern++) {

case SRE_OP_MARK:

/* set mark */

/* <MARK> <gid> */

TRACE(("|%p|%p|MARK %d\n", ctx->pattern,

ctx->ptr, ctx->pattern[0]));

i = ctx->pattern[0];

if (i & 1)

state->lastindex = i/2 + 1;

if (i > state->lastmark) {

/* state->lastmark is the highest valid index in the

state->mark array. If it is increased by more than 1,

the intervening marks must be set to NULL to signal

that these marks have not been encountered. */

int j = state->lastmark + 1;

while (j < i)

state->mark[j++] = NULL;

state->lastmark = i;

}

state->mark[i] = ctx->ptr;

ctx->pattern++;

break;

case SRE_OP_LITERAL:

/* match literal string */

/* <LITERAL> <code> */

TRACE(("|%p|%p|LITERAL %d\n", ctx->pattern,

ctx->ptr, *ctx->pattern));

if (ctx->ptr >= end || (SRE_CODE) ctx->ptr[0] != ctx->pattern[0])

RETURN_FAILURE;

ctx->pattern++;

ctx->ptr++;

break;

case SRE_OP_NOT_LITERAL:

/* match anything that is not literal character */

/* <NOT_LITERAL> <code> */

TRACE(("|%p|%p|NOT_LITERAL %d\n", ctx->pattern,

ctx->ptr, *ctx->pattern));

if (ctx->ptr >= end || (SRE_CODE) ctx->ptr[0] == ctx->pattern[0])

RETURN_FAILURE;

ctx->pattern++;

ctx->ptr++;

break;

case SRE_OP_SUCCESS:

/* end of pattern */

TRACE(("|%p|%p|SUCCESS\n", ctx->pattern, ctx->ptr));

state->ptr = ctx->ptr;

RETURN_SUCCESS;

case SRE_OP_AT:

/* match at given position */

/* <AT> <code> */

TRACE(("|%p|%p|AT %d\n", ctx->pattern, ctx->ptr, *ctx->pattern));

if (!SRE_AT(state, ctx->ptr, *ctx->pattern))

RETURN_FAILURE;

ctx->pattern++;

break;

case SRE_OP_CATEGORY:

/* match at given category */

/* <CATEGORY> <code> */

TRACE(("|%p|%p|CATEGORY %d\n", ctx->pattern,

ctx->ptr, *ctx->pattern));

if (ctx->ptr >= end || !sre_category(ctx->pattern[0], ctx->ptr[0]))

RETURN_FAILURE;

ctx->pattern++;

ctx->ptr++;

break;

case SRE_OP_ANY:

/* match anything (except a newline) */

/* <ANY> */

TRACE(("|%p|%p|ANY\n", ctx->pattern, ctx->ptr));

if (ctx->ptr >= end || SRE_IS_LINEBREAK(ctx->ptr[0]))

RETURN_FAILURE;

ctx->ptr++;

break;

case SRE_OP_ANY_ALL:

/* match anything */

/* <ANY_ALL> */

TRACE(("|%p|%p|ANY_ALL\n", ctx->pattern, ctx->ptr));

if (ctx->ptr >= end)

RETURN_FAILURE;

ctx->ptr++;

break;

case SRE_OP_IN:

/* match set member (or non_member) */

/* <IN> <skip> <set> */

TRACE(("|%p|%p|IN\n", ctx->pattern, ctx->ptr));

if (ctx->ptr >= end || !SRE_CHARSET(ctx->pattern + 1, *ctx->ptr))

RETURN_FAILURE;

ctx->pattern += ctx->pattern[0];

ctx->ptr++;

break;

case SRE_OP_LITERAL_IGNORE:

TRACE(("|%p|%p|LITERAL_IGNORE %d\n",

ctx->pattern, ctx->ptr, ctx->pattern[0]));

if (ctx->ptr >= end ||

state->lower(*ctx->ptr) != state->lower(*ctx->pattern))

RETURN_FAILURE;

ctx->pattern++;

ctx->ptr++;

break;

case SRE_OP_NOT_LITERAL_IGNORE:

TRACE(("|%p|%p|NOT_LITERAL_IGNORE %d\n",

ctx->pattern, ctx->ptr, *ctx->pattern));

if (ctx->ptr >= end ||

state->lower(*ctx->ptr) == state->lower(*ctx->pattern))

RETURN_FAILURE;

ctx->pattern++;

ctx->ptr++;

break;

case SRE_OP_IN_IGNORE:

TRACE(("|%p|%p|IN_IGNORE\n", ctx->pattern, ctx->ptr));

if (ctx->ptr >= end

|| !SRE_CHARSET(ctx->pattern+1,

(SRE_CODE)state->lower(*ctx->ptr)))

RETURN_FAILURE;

ctx->pattern += ctx->pattern[0];

ctx->ptr++;

break;

case SRE_OP_JUMP:

case SRE_OP_INFO:

/* jump forward */

/* <JUMP> <offset> */

TRACE(("|%p|%p|JUMP %d\n", ctx->pattern,

ctx->ptr, ctx->pattern[0]));

ctx->pattern += ctx->pattern[0];

break;

case SRE_OP_BRANCH:

/* alternation */

/* <BRANCH> <0=skip> code <JUMP> ... <NULL> */

TRACE(("|%p|%p|BRANCH\n", ctx->pattern, ctx->ptr));

LASTMARK_SAVE();

ctx->u.rep = state->repeat;

if (ctx->u.rep)

MARK_PUSH(ctx->lastmark);

for (; ctx->pattern[0]; ctx->pattern += ctx->pattern[0]) {

if (ctx->pattern[1] == SRE_OP_LITERAL &&

(ctx->ptr >= end ||

(SRE_CODE) *ctx->ptr != ctx->pattern[2]))

continue;

if (ctx->pattern[1] == SRE_OP_IN &&

(ctx->ptr >= end ||

!SRE_CHARSET(ctx->pattern + 3, (SRE_CODE) *ctx->ptr)))

continue;

state->ptr = ctx->ptr;

DO_JUMP(JUMP_BRANCH, jump_branch, ctx->pattern+1);

if (ret) {

if (ctx->u.rep)

MARK_POP_DISCARD(ctx->lastmark);

RETURN_ON_ERROR(ret);

RETURN_SUCCESS;

}

View remainder of file in raw view

FilesExpand file tree

_sre.c

Latest commit

History

_sre.c

File metadata and controls