~ubuntu-branches/ubuntu/utopic/libxml2/utopic : revision 75

1

/*

2

* regexp.c: generic and extensible Regular Expression engine

3

*

4

* Basically designed with the purpose of compiling regexps for

5

* the variety of validation/shemas mechanisms now available in

6

* XML related specifications these include:

7

* - XML-1.0 DTD validation

8

* - XML Schemas structure part 1

9

* - XML Schemas Datatypes part 2 especially Appendix F

10

* - RELAX-NG/TREX i.e. the counter proposal

11

*

12

* See Copyright for the status of this software.

13

*

14

* Daniel Veillard <veillard@redhat.com>

15

*/

16

17

#define IN_LIBXML

18

#include "libxml.h"

19

20

#ifdef LIBXML_REGEXP_ENABLED

21

22

/* #define DEBUG_ERR */

23

24

#include <stdio.h>

25

#include <string.h>

26

#ifdef HAVE_LIMITS_H

27

#include <limits.h>

28

#endif

29

30

#include <libxml/tree.h>

31

#include <libxml/parserInternals.h>

32

#include <libxml/xmlregexp.h>

33

#include <libxml/xmlautomata.h>

34

#include <libxml/xmlunicode.h>

35

36

#ifndef INT_MAX

37

#define INT_MAX 123456789 /* easy to flag and big enough for our needs */

38

#endif

39

40

/* #define DEBUG_REGEXP_GRAPH */

41

/* #define DEBUG_REGEXP_EXEC */

42

/* #define DEBUG_PUSH */

43

/* #define DEBUG_COMPACTION */

44

45

#define MAX_PUSH 10000000

46

47

#ifdef ERROR

48

#undef ERROR

49

#endif

50

#define ERROR(str) \

51

ctxt->error = XML_REGEXP_COMPILE_ERROR; \

52

xmlRegexpErrCompile(ctxt, str);

53

#define NEXT ctxt->cur++

54

#define CUR (*(ctxt->cur))

55

#define NXT(index) (ctxt->cur[index])

56

57

#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)

58

#define NEXTL(l) ctxt->cur += l;

59

#define XML_REG_STRING_SEPARATOR '|'

60

/*

61

* Need PREV to check on a '-' within a Character Group. May only be used

62

* when it's guaranteed that cur is not at the beginning of ctxt->string!

63

*/

64

#define PREV (ctxt->cur[-1])

65

66

/**

67

* TODO:

68

*

69

* macro to flag unimplemented blocks

70

*/

71

#define TODO \

72

xmlGenericError(xmlGenericErrorContext, \

73

"Unimplemented block at %s:%d\n", \

74

__FILE__, __LINE__);

75

76

/************************************************************************

77

* *

78

* Datatypes and structures *

79

* *

80

************************************************************************/

81

82

/*

83

* Note: the order of the enums below is significant, do not shuffle

84

*/

85

typedef enum {

86

XML_REGEXP_EPSILON = 1,

87

XML_REGEXP_CHARVAL,

88

XML_REGEXP_RANGES,

89

XML_REGEXP_SUBREG, /* used for () sub regexps */

90

XML_REGEXP_STRING,

91

XML_REGEXP_ANYCHAR, /* . */

92

XML_REGEXP_ANYSPACE, /* \s */

93

XML_REGEXP_NOTSPACE, /* \S */

94

XML_REGEXP_INITNAME, /* \l */

95

XML_REGEXP_NOTINITNAME, /* \L */

96

XML_REGEXP_NAMECHAR, /* \c */

97

XML_REGEXP_NOTNAMECHAR, /* \C */

98

XML_REGEXP_DECIMAL, /* \d */

99

XML_REGEXP_NOTDECIMAL, /* \D */

100

XML_REGEXP_REALCHAR, /* \w */

101

XML_REGEXP_NOTREALCHAR, /* \W */

102

XML_REGEXP_LETTER = 100,

103

XML_REGEXP_LETTER_UPPERCASE,

104

XML_REGEXP_LETTER_LOWERCASE,

105

XML_REGEXP_LETTER_TITLECASE,

106

XML_REGEXP_LETTER_MODIFIER,

107

XML_REGEXP_LETTER_OTHERS,

108

XML_REGEXP_MARK,

109

XML_REGEXP_MARK_NONSPACING,

110

XML_REGEXP_MARK_SPACECOMBINING,

111

XML_REGEXP_MARK_ENCLOSING,

112

XML_REGEXP_NUMBER,

113

XML_REGEXP_NUMBER_DECIMAL,

114

XML_REGEXP_NUMBER_LETTER,

115

XML_REGEXP_NUMBER_OTHERS,

116

XML_REGEXP_PUNCT,

117

XML_REGEXP_PUNCT_CONNECTOR,

118

XML_REGEXP_PUNCT_DASH,

119

XML_REGEXP_PUNCT_OPEN,

120

XML_REGEXP_PUNCT_CLOSE,

121

XML_REGEXP_PUNCT_INITQUOTE,

122

XML_REGEXP_PUNCT_FINQUOTE,

123

XML_REGEXP_PUNCT_OTHERS,

124

XML_REGEXP_SEPAR,

125

XML_REGEXP_SEPAR_SPACE,

126

XML_REGEXP_SEPAR_LINE,

127

XML_REGEXP_SEPAR_PARA,

128

XML_REGEXP_SYMBOL,

129

XML_REGEXP_SYMBOL_MATH,

130

XML_REGEXP_SYMBOL_CURRENCY,

131

XML_REGEXP_SYMBOL_MODIFIER,

132

XML_REGEXP_SYMBOL_OTHERS,

133

XML_REGEXP_OTHER,

134

XML_REGEXP_OTHER_CONTROL,

135

XML_REGEXP_OTHER_FORMAT,

136

XML_REGEXP_OTHER_PRIVATE,

137

XML_REGEXP_OTHER_NA,

138

XML_REGEXP_BLOCK_NAME

139

} xmlRegAtomType;

140

141

typedef enum {

142

XML_REGEXP_QUANT_EPSILON = 1,

143

XML_REGEXP_QUANT_ONCE,

144

XML_REGEXP_QUANT_OPT,

145

XML_REGEXP_QUANT_MULT,

146

XML_REGEXP_QUANT_PLUS,

147

XML_REGEXP_QUANT_ONCEONLY,

148

XML_REGEXP_QUANT_ALL,

149

XML_REGEXP_QUANT_RANGE

150

} xmlRegQuantType;

151

152

typedef enum {

153

XML_REGEXP_START_STATE = 1,

154

XML_REGEXP_FINAL_STATE,

155

XML_REGEXP_TRANS_STATE,

156

XML_REGEXP_SINK_STATE,

157

XML_REGEXP_UNREACH_STATE

158

} xmlRegStateType;

159

160

typedef enum {

161

XML_REGEXP_MARK_NORMAL = 0,

162

XML_REGEXP_MARK_START,

163

XML_REGEXP_MARK_VISITED

164

} xmlRegMarkedType;

165

166

typedef struct _xmlRegRange xmlRegRange;

167

typedef xmlRegRange *xmlRegRangePtr;

168

169

struct _xmlRegRange {

170

int neg; /* 0 normal, 1 not, 2 exclude */

171

xmlRegAtomType type;

172

int start;

173

int end;

174

xmlChar *blockName;

175

};

176

177

typedef struct _xmlRegAtom xmlRegAtom;

178

typedef xmlRegAtom *xmlRegAtomPtr;

179

180

typedef struct _xmlAutomataState xmlRegState;

181

typedef xmlRegState *xmlRegStatePtr;

182

183

struct _xmlRegAtom {

184

int no;

185

xmlRegAtomType type;

186

xmlRegQuantType quant;

187

int min;

188

int max;

189

190

void *valuep;

191

void *valuep2;

192

int neg;

193

int codepoint;

194

xmlRegStatePtr start;

195

xmlRegStatePtr start0;

196

xmlRegStatePtr stop;

197

int maxRanges;

198

int nbRanges;

199

xmlRegRangePtr *ranges;

200

void *data;

201

};

202

203

typedef struct _xmlRegCounter xmlRegCounter;

204

typedef xmlRegCounter *xmlRegCounterPtr;

205

206

struct _xmlRegCounter {

207

int min;

208

int max;

209

};

210

211

typedef struct _xmlRegTrans xmlRegTrans;

212

typedef xmlRegTrans *xmlRegTransPtr;

213

214

struct _xmlRegTrans {

215

xmlRegAtomPtr atom;

216

int to;

217

int counter;

218

int count;

219

int nd;

220

};

221

222

struct _xmlAutomataState {

223

xmlRegStateType type;

224

xmlRegMarkedType mark;

225

xmlRegMarkedType markd;

226

xmlRegMarkedType reached;

227

int no;

228

int maxTrans;

229

int nbTrans;

230

xmlRegTrans *trans;

231

/* knowing states ponting to us can speed things up */

232

int maxTransTo;

233

int nbTransTo;

234

int *transTo;

235

};

236

237

typedef struct _xmlAutomata xmlRegParserCtxt;

238

typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;

239

240

#define AM_AUTOMATA_RNG 1

241

242

struct _xmlAutomata {

243

xmlChar *string;

244

xmlChar *cur;

245

246

int error;

247

int neg;

248

249

xmlRegStatePtr start;

250

xmlRegStatePtr end;

251

xmlRegStatePtr state;

252

253

xmlRegAtomPtr atom;

254

255

int maxAtoms;

256

int nbAtoms;

257

xmlRegAtomPtr *atoms;

258

259

int maxStates;

260

int nbStates;

261

xmlRegStatePtr *states;

262

263

int maxCounters;

264

int nbCounters;

265

xmlRegCounter *counters;

266

267

int determinist;

268

int negs;

269

int flags;

270

};

271

272

struct _xmlRegexp {

273

xmlChar *string;

274

int nbStates;

275

xmlRegStatePtr *states;

276

int nbAtoms;

277

xmlRegAtomPtr *atoms;

278

int nbCounters;

279

xmlRegCounter *counters;

280

int determinist;

281

int flags;

282

/*

283

* That's the compact form for determinists automatas

284

*/

285

int nbstates;

286

int *compact;

287

void **transdata;

288

int nbstrings;

289

xmlChar **stringMap;

290

};

291

292

typedef struct _xmlRegExecRollback xmlRegExecRollback;

293

typedef xmlRegExecRollback *xmlRegExecRollbackPtr;

294

295

struct _xmlRegExecRollback {

296

xmlRegStatePtr state;/* the current state */

297

int index; /* the index in the input stack */

298

int nextbranch; /* the next transition to explore in that state */

299

int *counts; /* save the automata state if it has some */

300

};

301

302

typedef struct _xmlRegInputToken xmlRegInputToken;

303

typedef xmlRegInputToken *xmlRegInputTokenPtr;

304

305

struct _xmlRegInputToken {

306

xmlChar *value;

307

void *data;

308

};

309

310

struct _xmlRegExecCtxt {

311

int status; /* execution status != 0 indicate an error */

312

int determinist; /* did we find an indeterministic behaviour */

313

xmlRegexpPtr comp; /* the compiled regexp */

314

xmlRegExecCallbacks callback;

315

void *data;

316

317

xmlRegStatePtr state;/* the current state */

318

int transno; /* the current transition on that state */

319

int transcount; /* the number of chars in char counted transitions */

320

321

/*

322

* A stack of rollback states

323

*/

324

int maxRollbacks;

325

int nbRollbacks;

326

xmlRegExecRollback *rollbacks;

327

328

/*

329

* The state of the automata if any

330

*/

331

int *counts;

332

333

/*

334

* The input stack

335

*/

336

int inputStackMax;

337

int inputStackNr;

338

int index;

339

int *charStack;

340

const xmlChar *inputString; /* when operating on characters */

341

xmlRegInputTokenPtr inputStack;/* when operating on strings */

342

343

/*

344

* error handling

345

*/

346

int errStateNo; /* the error state number */

347

xmlRegStatePtr errState; /* the error state */

348

xmlChar *errString; /* the string raising the error */

349

int *errCounts; /* counters at the error state */

350

int nbPush;

351

};

352

353

#define REGEXP_ALL_COUNTER 0x123456

354

#define REGEXP_ALL_LAX_COUNTER 0x123457

355

356

static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top);

357

static void xmlRegFreeState(xmlRegStatePtr state);

358

static void xmlRegFreeAtom(xmlRegAtomPtr atom);

359

static int xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr);

360

static int xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint);

361

static int xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint,

362

int neg, int start, int end, const xmlChar *blockName);

363

364

void xmlAutomataSetFlags(xmlAutomataPtr am, int flags);

365

366

/************************************************************************

367

* *

368

* Regexp memory error handler *

369

* *

370

************************************************************************/

371

/**

372

* xmlRegexpErrMemory:

373

* @extra: extra information

374

*

375

* Handle an out of memory condition

376

*/

377

static void

378

xmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra)

379

{

380

const char *regexp = NULL;

381

if (ctxt != NULL) {

382

regexp = (const char *) ctxt->string;

383

ctxt->error = XML_ERR_NO_MEMORY;

384

}

385

__xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,

386

XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, extra,

387

regexp, NULL, 0, 0,

388

"Memory allocation failed : %s\n", extra);

389

}

390

391

/**

392

* xmlRegexpErrCompile:

393

* @extra: extra information

394

*

395

* Handle a compilation failure

396

*/

397

static void

398

xmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra)

399

{

400

const char *regexp = NULL;

401

int idx = 0;

402

403

if (ctxt != NULL) {

404

regexp = (const char *) ctxt->string;

405

idx = ctxt->cur - ctxt->string;

406

ctxt->error = XML_REGEXP_COMPILE_ERROR;

407

}

408

__xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,

409

XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL, 0, extra,

410

regexp, NULL, idx, 0,

411

"failed to compile: %s\n", extra);

412

}

413

414

/************************************************************************

415

* *

416

* Allocation/Deallocation *

417

* *

418

************************************************************************/

419

420

static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt);

421

/**

422

* xmlRegEpxFromParse:

423

* @ctxt: the parser context used to build it

424

*

425

* Allocate a new regexp and fill it with the result from the parser

426

*

427

* Returns the new regexp or NULL in case of error

428

*/

429

static xmlRegexpPtr

430

xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) {

431

xmlRegexpPtr ret;

432

433

ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp));

434

if (ret == NULL) {

435

xmlRegexpErrMemory(ctxt, "compiling regexp");

436

return(NULL);

437

}

438

memset(ret, 0, sizeof(xmlRegexp));

439

ret->string = ctxt->string;

440

ret->nbStates = ctxt->nbStates;

441

ret->states = ctxt->states;

442

ret->nbAtoms = ctxt->nbAtoms;

443

ret->atoms = ctxt->atoms;

444

ret->nbCounters = ctxt->nbCounters;

445

ret->counters = ctxt->counters;

446

ret->determinist = ctxt->determinist;

447

ret->flags = ctxt->flags;

448

if (ret->determinist == -1) {

449

xmlRegexpIsDeterminist(ret);

450

}

451

452

if ((ret->determinist != 0) &&

453

(ret->nbCounters == 0) &&

454

(ctxt->negs == 0) &&

455

(ret->atoms != NULL) &&

456

(ret->atoms[0] != NULL) &&

457

(ret->atoms[0]->type == XML_REGEXP_STRING)) {

458

int i, j, nbstates = 0, nbatoms = 0;

459

int *stateRemap;

460

int *stringRemap;

461

int *transitions;

462

void **transdata;

463

xmlChar **stringMap;

464

xmlChar *value;

465

466

/*

467

* Switch to a compact representation

468

* 1/ counting the effective number of states left

469

* 2/ counting the unique number of atoms, and check that

470

* they are all of the string type

471

* 3/ build a table state x atom for the transitions

472

*/

473

474

stateRemap = xmlMalloc(ret->nbStates * sizeof(int));

475

if (stateRemap == NULL) {

476

xmlRegexpErrMemory(ctxt, "compiling regexp");

477

xmlFree(ret);

478

return(NULL);

479

}

480

for (i = 0;i < ret->nbStates;i++) {

481

if (ret->states[i] != NULL) {

482

stateRemap[i] = nbstates;

483

nbstates++;

484

} else {

485

stateRemap[i] = -1;

486

}

487

}

488

#ifdef DEBUG_COMPACTION

489

printf("Final: %d states\n", nbstates);

490

#endif

491

stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *));

492

if (stringMap == NULL) {

493

xmlRegexpErrMemory(ctxt, "compiling regexp");

494

xmlFree(stateRemap);

495

xmlFree(ret);

496

return(NULL);

497

}

498

stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int));

499

if (stringRemap == NULL) {

500

xmlRegexpErrMemory(ctxt, "compiling regexp");

501

xmlFree(stringMap);

502

xmlFree(stateRemap);

503

xmlFree(ret);

504

return(NULL);

505

}

506

for (i = 0;i < ret->nbAtoms;i++) {

507

if ((ret->atoms[i]->type == XML_REGEXP_STRING) &&

508

(ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) {

509

value = ret->atoms[i]->valuep;

510

for (j = 0;j < nbatoms;j++) {

511

if (xmlStrEqual(stringMap[j], value)) {

512

stringRemap[i] = j;

513

break;

514

}

515

}

516

if (j >= nbatoms) {

517

stringRemap[i] = nbatoms;

518

stringMap[nbatoms] = xmlStrdup(value);

519

if (stringMap[nbatoms] == NULL) {

520

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

521

xmlFree(stringMap[i]);

522

xmlFree(stringRemap);

523

xmlFree(stringMap);

524

xmlFree(stateRemap);

525

xmlFree(ret);

526

return(NULL);

527

}

528

nbatoms++;

529

}

530

} else {

531

xmlFree(stateRemap);

532

xmlFree(stringRemap);

533

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

534

xmlFree(stringMap[i]);

535

xmlFree(stringMap);

536

xmlFree(ret);

537

return(NULL);

538

}

539

}

540

#ifdef DEBUG_COMPACTION

541

printf("Final: %d atoms\n", nbatoms);

542

#endif

543

transitions = (int *) xmlMalloc((nbstates + 1) *

544

(nbatoms + 1) * sizeof(int));

545

if (transitions == NULL) {

546

xmlFree(stateRemap);

547

xmlFree(stringRemap);

548

xmlFree(stringMap);

549

xmlFree(ret);

550

return(NULL);

551

}

552

memset(transitions, 0, (nbstates + 1) * (nbatoms + 1) * sizeof(int));

553

554

/*

555

* Allocate the transition table. The first entry for each

556

* state corresponds to the state type.

557

*/

558

transdata = NULL;

559

560

for (i = 0;i < ret->nbStates;i++) {

561

int stateno, atomno, targetno, prev;

562

xmlRegStatePtr state;

563

xmlRegTransPtr trans;

564

565

stateno = stateRemap[i];

566

if (stateno == -1)

567

continue;

568

state = ret->states[i];

569

570

transitions[stateno * (nbatoms + 1)] = state->type;

571

572

for (j = 0;j < state->nbTrans;j++) {

573

trans = &(state->trans[j]);

574

if ((trans->to == -1) || (trans->atom == NULL))

575

continue;

576

atomno = stringRemap[trans->atom->no];

577

if ((trans->atom->data != NULL) && (transdata == NULL)) {

578

transdata = (void **) xmlMalloc(nbstates * nbatoms *

579

sizeof(void *));

580

if (transdata != NULL)

581

memset(transdata, 0,

582

nbstates * nbatoms * sizeof(void *));

583

else {

584

xmlRegexpErrMemory(ctxt, "compiling regexp");

585

break;

586

}

587

}

588

targetno = stateRemap[trans->to];

589

/*

590

* if the same atom can generate transitions to 2 different

591

* states then it means the automata is not determinist and

592

* the compact form can't be used !

593

*/

594

prev = transitions[stateno * (nbatoms + 1) + atomno + 1];

595

if (prev != 0) {

596

if (prev != targetno + 1) {

597

ret->determinist = 0;

598

#ifdef DEBUG_COMPACTION

599

printf("Indet: state %d trans %d, atom %d to %d : %d to %d\n",

600

i, j, trans->atom->no, trans->to, atomno, targetno);

601

printf(" previous to is %d\n", prev);

602

#endif

603

if (transdata != NULL)

604

xmlFree(transdata);

605

xmlFree(transitions);

606

xmlFree(stateRemap);

607

xmlFree(stringRemap);

608

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

609

xmlFree(stringMap[i]);

610

xmlFree(stringMap);

611

goto not_determ;

612

}

613

} else {

614

#if 0

615

printf("State %d trans %d: atom %d to %d : %d to %d\n",

616

i, j, trans->atom->no, trans->to, atomno, targetno);

617

#endif

618

transitions[stateno * (nbatoms + 1) + atomno + 1] =

619

targetno + 1; /* to avoid 0 */

620

if (transdata != NULL)

621

transdata[stateno * nbatoms + atomno] =

622

trans->atom->data;

623

}

624

}

625

}

626

ret->determinist = 1;

627

#ifdef DEBUG_COMPACTION

628

/*

629

* Debug

630

*/

631

for (i = 0;i < nbstates;i++) {

632

for (j = 0;j < nbatoms + 1;j++) {

633

printf("%02d ", transitions[i * (nbatoms + 1) + j]);

634

}

635

printf("\n");

636

}

637

printf("\n");

638

#endif

639

/*

640

* Cleanup of the old data

641

*/

642

if (ret->states != NULL) {

643

for (i = 0;i < ret->nbStates;i++)

644

xmlRegFreeState(ret->states[i]);

645

xmlFree(ret->states);

646

}

647

ret->states = NULL;

648

ret->nbStates = 0;

649

if (ret->atoms != NULL) {

650

for (i = 0;i < ret->nbAtoms;i++)

651

xmlRegFreeAtom(ret->atoms[i]);

652

xmlFree(ret->atoms);

653

}

654

ret->atoms = NULL;

655

ret->nbAtoms = 0;

656

657

ret->compact = transitions;

658

ret->transdata = transdata;

659

ret->stringMap = stringMap;

660

ret->nbstrings = nbatoms;

661

ret->nbstates = nbstates;

662

xmlFree(stateRemap);

663

xmlFree(stringRemap);

664

}

665

not_determ:

666

ctxt->string = NULL;

667

ctxt->nbStates = 0;

668

ctxt->states = NULL;

669

ctxt->nbAtoms = 0;

670

ctxt->atoms = NULL;

671

ctxt->nbCounters = 0;

672

ctxt->counters = NULL;

673

return(ret);

674

}

675

676

/**

677

* xmlRegNewParserCtxt:

678

* @string: the string to parse

679

*

680

* Allocate a new regexp parser context

681

*

682

* Returns the new context or NULL in case of error

683

*/

684

static xmlRegParserCtxtPtr

685

xmlRegNewParserCtxt(const xmlChar *string) {

686

xmlRegParserCtxtPtr ret;

687

688

ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt));

689

if (ret == NULL)

690

return(NULL);

691

memset(ret, 0, sizeof(xmlRegParserCtxt));

692

if (string != NULL)

693

ret->string = xmlStrdup(string);

694

ret->cur = ret->string;

695

ret->neg = 0;

696

ret->negs = 0;

697

ret->error = 0;

698

ret->determinist = -1;

699

return(ret);

700

}

701

702

/**

703

* xmlRegNewRange:

704

* @ctxt: the regexp parser context

705

* @neg: is that negative

706

* @type: the type of range

707

* @start: the start codepoint

708

* @end: the end codepoint

709

*

710

* Allocate a new regexp range

711

*

712

* Returns the new range or NULL in case of error

713

*/

714

static xmlRegRangePtr

715

xmlRegNewRange(xmlRegParserCtxtPtr ctxt,

716

int neg, xmlRegAtomType type, int start, int end) {

717

xmlRegRangePtr ret;

718

719

ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange));

720

if (ret == NULL) {

721

xmlRegexpErrMemory(ctxt, "allocating range");

722

return(NULL);

723

}

724

ret->neg = neg;

725

ret->type = type;

726

ret->start = start;

727

ret->end = end;

728

return(ret);

729

}

730

731

/**

732

* xmlRegFreeRange:

733

* @range: the regexp range

734

*

735

* Free a regexp range

736

*/

737

static void

738

xmlRegFreeRange(xmlRegRangePtr range) {

739

if (range == NULL)

740

return;

741

742

if (range->blockName != NULL)

743

xmlFree(range->blockName);

744

xmlFree(range);

745

}

746

747

/**

748

* xmlRegCopyRange:

749

* @range: the regexp range

750

*

751

* Copy a regexp range

752

*

753

* Returns the new copy or NULL in case of error.

754

*/

755

static xmlRegRangePtr

756

xmlRegCopyRange(xmlRegParserCtxtPtr ctxt, xmlRegRangePtr range) {

757

xmlRegRangePtr ret;

758

759

if (range == NULL)

760

return(NULL);

761

762

ret = xmlRegNewRange(ctxt, range->neg, range->type, range->start,

763

range->end);

764

if (ret == NULL)

765

return(NULL);

766

if (range->blockName != NULL) {

767

ret->blockName = xmlStrdup(range->blockName);

768

if (ret->blockName == NULL) {

769

xmlRegexpErrMemory(ctxt, "allocating range");

770

xmlRegFreeRange(ret);

771

return(NULL);

772

}

773

}

774

return(ret);

775

}

776

777

/**

778

* xmlRegNewAtom:

779

* @ctxt: the regexp parser context

780

* @type: the type of atom

781

*

782

* Allocate a new atom

783

*

784

* Returns the new atom or NULL in case of error

785

*/

786

static xmlRegAtomPtr

787

xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) {

788

xmlRegAtomPtr ret;

789

790

ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));

791

if (ret == NULL) {

792

xmlRegexpErrMemory(ctxt, "allocating atom");

793

return(NULL);

794

}

795

memset(ret, 0, sizeof(xmlRegAtom));

796

ret->type = type;

797

ret->quant = XML_REGEXP_QUANT_ONCE;

798

ret->min = 0;

799

ret->max = 0;

800

return(ret);

801

}

802

803

/**

804

* xmlRegFreeAtom:

805

* @atom: the regexp atom

806

*

807

* Free a regexp atom

808

*/

809

static void

810

xmlRegFreeAtom(xmlRegAtomPtr atom) {

811

int i;

812

813

if (atom == NULL)

814

return;

815

816

for (i = 0;i < atom->nbRanges;i++)

817

xmlRegFreeRange(atom->ranges[i]);

818

if (atom->ranges != NULL)

819

xmlFree(atom->ranges);

820

if ((atom->type == XML_REGEXP_STRING) && (atom->valuep != NULL))

821

xmlFree(atom->valuep);

822

if ((atom->type == XML_REGEXP_STRING) && (atom->valuep2 != NULL))

823

xmlFree(atom->valuep2);

824

if ((atom->type == XML_REGEXP_BLOCK_NAME) && (atom->valuep != NULL))

825

xmlFree(atom->valuep);

826

xmlFree(atom);

827

}

828

829

/**

830

* xmlRegCopyAtom:

831

* @ctxt: the regexp parser context

832

* @atom: the oiginal atom

833

*

834

* Allocate a new regexp range

835

*

836

* Returns the new atom or NULL in case of error

837

*/

838

static xmlRegAtomPtr

839

xmlRegCopyAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {

840

xmlRegAtomPtr ret;

841

842

ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));

843

if (ret == NULL) {

844

xmlRegexpErrMemory(ctxt, "copying atom");

845

return(NULL);

846

}

847

memset(ret, 0, sizeof(xmlRegAtom));

848

ret->type = atom->type;

849

ret->quant = atom->quant;

850

ret->min = atom->min;

851

ret->max = atom->max;

852

if (atom->nbRanges > 0) {

853

int i;

854

855

ret->ranges = (xmlRegRangePtr *) xmlMalloc(sizeof(xmlRegRangePtr) *

856

atom->nbRanges);

857

if (ret->ranges == NULL) {

858

xmlRegexpErrMemory(ctxt, "copying atom");

859

goto error;

860

}

861

for (i = 0;i < atom->nbRanges;i++) {

862

ret->ranges[i] = xmlRegCopyRange(ctxt, atom->ranges[i]);

863

if (ret->ranges[i] == NULL)

864

goto error;

865

ret->nbRanges = i + 1;

866

}

867

}

868

return(ret);

869

870

error:

871

xmlRegFreeAtom(ret);

872

return(NULL);

873

}

874

875

static xmlRegStatePtr

876

xmlRegNewState(xmlRegParserCtxtPtr ctxt) {

877

xmlRegStatePtr ret;

878

879

ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState));

880

if (ret == NULL) {

881

xmlRegexpErrMemory(ctxt, "allocating state");

882

return(NULL);

883

}

884

memset(ret, 0, sizeof(xmlRegState));

885

ret->type = XML_REGEXP_TRANS_STATE;

886

ret->mark = XML_REGEXP_MARK_NORMAL;

887

return(ret);

888

}

889

890

/**

891

* xmlRegFreeState:

892

* @state: the regexp state

893

*

894

* Free a regexp state

895

*/

896

static void

897

xmlRegFreeState(xmlRegStatePtr state) {

898

if (state == NULL)

899

return;

900

901

if (state->trans != NULL)

902

xmlFree(state->trans);

903

if (state->transTo != NULL)

904

xmlFree(state->transTo);

905

xmlFree(state);

906

}

907

908

/**

909

* xmlRegFreeParserCtxt:

910

* @ctxt: the regexp parser context

911

*

912

* Free a regexp parser context

913

*/

914

static void

915

xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) {

916

int i;

917

if (ctxt == NULL)

918

return;

919

920

if (ctxt->string != NULL)

921

xmlFree(ctxt->string);

922

if (ctxt->states != NULL) {

923

for (i = 0;i < ctxt->nbStates;i++)

924

xmlRegFreeState(ctxt->states[i]);

925

xmlFree(ctxt->states);

926

}

927

if (ctxt->atoms != NULL) {

928

for (i = 0;i < ctxt->nbAtoms;i++)

929

xmlRegFreeAtom(ctxt->atoms[i]);

930

xmlFree(ctxt->atoms);

931

}

932

if (ctxt->counters != NULL)

933

xmlFree(ctxt->counters);

934

xmlFree(ctxt);

935

}

936

937

/************************************************************************

938

* *

939

* Display of Data structures *

940

* *

941

************************************************************************/

942

943

static void

944

xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) {

945

switch (type) {

946

case XML_REGEXP_EPSILON:

947

fprintf(output, "epsilon "); break;

948

case XML_REGEXP_CHARVAL:

949

fprintf(output, "charval "); break;

950

case XML_REGEXP_RANGES:

951

fprintf(output, "ranges "); break;

952

case XML_REGEXP_SUBREG:

953

fprintf(output, "subexpr "); break;

954

case XML_REGEXP_STRING:

955

fprintf(output, "string "); break;

956

case XML_REGEXP_ANYCHAR:

957

fprintf(output, "anychar "); break;

958

case XML_REGEXP_ANYSPACE:

959

fprintf(output, "anyspace "); break;

960

case XML_REGEXP_NOTSPACE:

961

fprintf(output, "notspace "); break;

962

case XML_REGEXP_INITNAME:

963

fprintf(output, "initname "); break;

964

case XML_REGEXP_NOTINITNAME:

965

fprintf(output, "notinitname "); break;

966

case XML_REGEXP_NAMECHAR:

967

fprintf(output, "namechar "); break;

968

case XML_REGEXP_NOTNAMECHAR:

969

fprintf(output, "notnamechar "); break;

970

case XML_REGEXP_DECIMAL:

971

fprintf(output, "decimal "); break;

972

case XML_REGEXP_NOTDECIMAL:

973

fprintf(output, "notdecimal "); break;

974

case XML_REGEXP_REALCHAR:

975

fprintf(output, "realchar "); break;

976

case XML_REGEXP_NOTREALCHAR:

977

fprintf(output, "notrealchar "); break;

978

case XML_REGEXP_LETTER:

979

fprintf(output, "LETTER "); break;

980

case XML_REGEXP_LETTER_UPPERCASE:

981

fprintf(output, "LETTER_UPPERCASE "); break;

982

case XML_REGEXP_LETTER_LOWERCASE:

983

fprintf(output, "LETTER_LOWERCASE "); break;

984

case XML_REGEXP_LETTER_TITLECASE:

985

fprintf(output, "LETTER_TITLECASE "); break;

986

case XML_REGEXP_LETTER_MODIFIER:

987

fprintf(output, "LETTER_MODIFIER "); break;

988

case XML_REGEXP_LETTER_OTHERS:

989

fprintf(output, "LETTER_OTHERS "); break;

990

case XML_REGEXP_MARK:

991

fprintf(output, "MARK "); break;

992

case XML_REGEXP_MARK_NONSPACING:

993

fprintf(output, "MARK_NONSPACING "); break;

994

case XML_REGEXP_MARK_SPACECOMBINING:

995

fprintf(output, "MARK_SPACECOMBINING "); break;

996

case XML_REGEXP_MARK_ENCLOSING:

997

fprintf(output, "MARK_ENCLOSING "); break;

998

case XML_REGEXP_NUMBER:

999

fprintf(output, "NUMBER "); break;

1000

case XML_REGEXP_NUMBER_DECIMAL:

1001

fprintf(output, "NUMBER_DECIMAL "); break;

1002

case XML_REGEXP_NUMBER_LETTER:

1003

fprintf(output, "NUMBER_LETTER "); break;

1004

case XML_REGEXP_NUMBER_OTHERS:

1005

fprintf(output, "NUMBER_OTHERS "); break;

1006

case XML_REGEXP_PUNCT:

1007

fprintf(output, "PUNCT "); break;

1008

case XML_REGEXP_PUNCT_CONNECTOR:

1009

fprintf(output, "PUNCT_CONNECTOR "); break;

1010

case XML_REGEXP_PUNCT_DASH:

1011

fprintf(output, "PUNCT_DASH "); break;

1012

case XML_REGEXP_PUNCT_OPEN:

1013

fprintf(output, "PUNCT_OPEN "); break;

1014

case XML_REGEXP_PUNCT_CLOSE:

1015

fprintf(output, "PUNCT_CLOSE "); break;

1016

case XML_REGEXP_PUNCT_INITQUOTE:

1017

fprintf(output, "PUNCT_INITQUOTE "); break;

1018

case XML_REGEXP_PUNCT_FINQUOTE:

1019

fprintf(output, "PUNCT_FINQUOTE "); break;

1020

case XML_REGEXP_PUNCT_OTHERS:

1021

fprintf(output, "PUNCT_OTHERS "); break;

1022

case XML_REGEXP_SEPAR:

1023

fprintf(output, "SEPAR "); break;

1024

case XML_REGEXP_SEPAR_SPACE:

1025

fprintf(output, "SEPAR_SPACE "); break;

1026

case XML_REGEXP_SEPAR_LINE:

1027

fprintf(output, "SEPAR_LINE "); break;

1028

case XML_REGEXP_SEPAR_PARA:

1029

fprintf(output, "SEPAR_PARA "); break;

1030

case XML_REGEXP_SYMBOL:

1031

fprintf(output, "SYMBOL "); break;

1032

case XML_REGEXP_SYMBOL_MATH:

1033

fprintf(output, "SYMBOL_MATH "); break;

1034

case XML_REGEXP_SYMBOL_CURRENCY:

1035

fprintf(output, "SYMBOL_CURRENCY "); break;

1036

case XML_REGEXP_SYMBOL_MODIFIER:

1037

fprintf(output, "SYMBOL_MODIFIER "); break;

1038

case XML_REGEXP_SYMBOL_OTHERS:

1039

fprintf(output, "SYMBOL_OTHERS "); break;

1040

case XML_REGEXP_OTHER:

1041

fprintf(output, "OTHER "); break;

1042

case XML_REGEXP_OTHER_CONTROL:

1043

fprintf(output, "OTHER_CONTROL "); break;

1044

case XML_REGEXP_OTHER_FORMAT:

1045

fprintf(output, "OTHER_FORMAT "); break;

1046

case XML_REGEXP_OTHER_PRIVATE:

1047

fprintf(output, "OTHER_PRIVATE "); break;

1048

case XML_REGEXP_OTHER_NA:

1049

fprintf(output, "OTHER_NA "); break;

1050

case XML_REGEXP_BLOCK_NAME:

1051

fprintf(output, "BLOCK "); break;

1052

}

1053

}

1054

1055

static void

1056

xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) {

1057

switch (type) {

1058

case XML_REGEXP_QUANT_EPSILON:

1059

fprintf(output, "epsilon "); break;

1060

case XML_REGEXP_QUANT_ONCE:

1061

fprintf(output, "once "); break;

1062

case XML_REGEXP_QUANT_OPT:

1063

fprintf(output, "? "); break;

1064

case XML_REGEXP_QUANT_MULT:

1065

fprintf(output, "* "); break;

1066

case XML_REGEXP_QUANT_PLUS:

1067

fprintf(output, "+ "); break;

1068

case XML_REGEXP_QUANT_RANGE:

1069

fprintf(output, "range "); break;

1070

case XML_REGEXP_QUANT_ONCEONLY:

1071

fprintf(output, "onceonly "); break;

1072

case XML_REGEXP_QUANT_ALL:

1073

fprintf(output, "all "); break;

1074

}

1075

}

1076

static void

1077

xmlRegPrintRange(FILE *output, xmlRegRangePtr range) {

1078

fprintf(output, " range: ");

1079

if (range->neg)

1080

fprintf(output, "negative ");

1081

xmlRegPrintAtomType(output, range->type);

1082

fprintf(output, "%c - %c\n", range->start, range->end);

1083

}

1084

1085

static void

1086

xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) {

1087

fprintf(output, " atom: ");

1088

if (atom == NULL) {

1089

fprintf(output, "NULL\n");

1090

return;

1091

}

1092

if (atom->neg)

1093

fprintf(output, "not ");

1094

xmlRegPrintAtomType(output, atom->type);

1095

xmlRegPrintQuantType(output, atom->quant);

1096

if (atom->quant == XML_REGEXP_QUANT_RANGE)

1097

fprintf(output, "%d-%d ", atom->min, atom->max);

1098

if (atom->type == XML_REGEXP_STRING)

1099

fprintf(output, "'%s' ", (char *) atom->valuep);

1100

if (atom->type == XML_REGEXP_CHARVAL)

1101

fprintf(output, "char %c\n", atom->codepoint);

1102

else if (atom->type == XML_REGEXP_RANGES) {

1103

int i;

1104

fprintf(output, "%d entries\n", atom->nbRanges);

1105

for (i = 0; i < atom->nbRanges;i++)

1106

xmlRegPrintRange(output, atom->ranges[i]);

1107

} else if (atom->type == XML_REGEXP_SUBREG) {

1108

fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no);

1109

} else {

1110

fprintf(output, "\n");

1111

}

1112

}

1113

1114

static void

1115

xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) {

1116

fprintf(output, " trans: ");

1117

if (trans == NULL) {

1118

fprintf(output, "NULL\n");

1119

return;

1120

}

1121

if (trans->to < 0) {

1122

fprintf(output, "removed\n");

1123

return;

1124

}

1125

if (trans->nd != 0) {

1126

if (trans->nd == 2)

1127

fprintf(output, "last not determinist, ");

1128

else

1129

fprintf(output, "not determinist, ");

1130

}

1131

if (trans->counter >= 0) {

1132

fprintf(output, "counted %d, ", trans->counter);

1133

}

1134

if (trans->count == REGEXP_ALL_COUNTER) {

1135

fprintf(output, "all transition, ");

1136

} else if (trans->count >= 0) {

1137

fprintf(output, "count based %d, ", trans->count);

1138

}

1139

if (trans->atom == NULL) {

1140

fprintf(output, "epsilon to %d\n", trans->to);

1141

return;

1142

}

1143

if (trans->atom->type == XML_REGEXP_CHARVAL)

1144

fprintf(output, "char %c ", trans->atom->codepoint);

1145

fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to);

1146

}

1147

1148

static void

1149

xmlRegPrintState(FILE *output, xmlRegStatePtr state) {

1150

int i;

1151

1152

fprintf(output, " state: ");

1153

if (state == NULL) {

1154

fprintf(output, "NULL\n");

1155

return;

1156

}

1157

if (state->type == XML_REGEXP_START_STATE)

1158

fprintf(output, "START ");

1159

if (state->type == XML_REGEXP_FINAL_STATE)

1160

fprintf(output, "FINAL ");

1161

1162

fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans);

1163

for (i = 0;i < state->nbTrans; i++) {

1164

xmlRegPrintTrans(output, &(state->trans[i]));

1165

}

1166

}

1167

1168

#ifdef DEBUG_REGEXP_GRAPH

1169

static void

1170

xmlRegPrintCtxt(FILE *output, xmlRegParserCtxtPtr ctxt) {

1171

int i;

1172

1173

fprintf(output, " ctxt: ");

1174

if (ctxt == NULL) {

1175

fprintf(output, "NULL\n");

1176

return;

1177

}

1178

fprintf(output, "'%s' ", ctxt->string);

1179

if (ctxt->error)

1180

fprintf(output, "error ");

1181

if (ctxt->neg)

1182

fprintf(output, "neg ");

1183

fprintf(output, "\n");

1184

fprintf(output, "%d atoms:\n", ctxt->nbAtoms);

1185

for (i = 0;i < ctxt->nbAtoms; i++) {

1186

fprintf(output, " %02d ", i);

1187

xmlRegPrintAtom(output, ctxt->atoms[i]);

1188

}

1189

if (ctxt->atom != NULL) {

1190

fprintf(output, "current atom:\n");

1191

xmlRegPrintAtom(output, ctxt->atom);

1192

}

1193

fprintf(output, "%d states:", ctxt->nbStates);

1194

if (ctxt->start != NULL)

1195

fprintf(output, " start: %d", ctxt->start->no);

1196

if (ctxt->end != NULL)

1197

fprintf(output, " end: %d", ctxt->end->no);

1198

fprintf(output, "\n");

1199

for (i = 0;i < ctxt->nbStates; i++) {

1200

xmlRegPrintState(output, ctxt->states[i]);

1201

}

1202

fprintf(output, "%d counters:\n", ctxt->nbCounters);

1203

for (i = 0;i < ctxt->nbCounters; i++) {

1204

fprintf(output, " %d: min %d max %d\n", i, ctxt->counters[i].min,

1205

ctxt->counters[i].max);

1206

}

1207

}

1208

#endif

1209

1210

/************************************************************************

1211

* *

1212

* Finite Automata structures manipulations *

1213

* *

1214

************************************************************************/

1215

1216

static void

1217

xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom,

1218

int neg, xmlRegAtomType type, int start, int end,

1219

xmlChar *blockName) {

1220

xmlRegRangePtr range;

1221

1222

if (atom == NULL) {

1223

ERROR("add range: atom is NULL");

1224

return;

1225

}

1226

if (atom->type != XML_REGEXP_RANGES) {

1227

ERROR("add range: atom is not ranges");

1228

return;

1229

}

1230

if (atom->maxRanges == 0) {

1231

atom->maxRanges = 4;

1232

atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges *

1233

sizeof(xmlRegRangePtr));

1234

if (atom->ranges == NULL) {

1235

xmlRegexpErrMemory(ctxt, "adding ranges");

1236

atom->maxRanges = 0;

1237

return;

1238

}

1239

} else if (atom->nbRanges >= atom->maxRanges) {

1240

xmlRegRangePtr *tmp;

1241

atom->maxRanges *= 2;

1242

tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges *

1243

sizeof(xmlRegRangePtr));

1244

if (tmp == NULL) {

1245

xmlRegexpErrMemory(ctxt, "adding ranges");

1246

atom->maxRanges /= 2;

1247

return;

1248

}

1249

atom->ranges = tmp;

1250

}

1251

range = xmlRegNewRange(ctxt, neg, type, start, end);

1252

if (range == NULL)

1253

return;

1254

range->blockName = blockName;

1255

atom->ranges[atom->nbRanges++] = range;

1256

1257

}

1258

1259

static int

1260

xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) {

1261

if (ctxt->maxCounters == 0) {

1262

ctxt->maxCounters = 4;

1263

ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters *

1264

sizeof(xmlRegCounter));

1265

if (ctxt->counters == NULL) {

1266

xmlRegexpErrMemory(ctxt, "allocating counter");

1267

ctxt->maxCounters = 0;

1268

return(-1);

1269

}

1270

} else if (ctxt->nbCounters >= ctxt->maxCounters) {

1271

xmlRegCounter *tmp;

1272

ctxt->maxCounters *= 2;

1273

tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters *

1274

sizeof(xmlRegCounter));

1275

if (tmp == NULL) {

1276

xmlRegexpErrMemory(ctxt, "allocating counter");

1277

ctxt->maxCounters /= 2;

1278

return(-1);

1279

}

1280

ctxt->counters = tmp;

1281

}

1282

ctxt->counters[ctxt->nbCounters].min = -1;

1283

ctxt->counters[ctxt->nbCounters].max = -1;

1284

return(ctxt->nbCounters++);

1285

}

1286

1287

static int

1288

xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {

1289

if (atom == NULL) {

1290

ERROR("atom push: atom is NULL");

1291

return(-1);

1292

}

1293

if (ctxt->maxAtoms == 0) {

1294

ctxt->maxAtoms = 4;

1295

ctxt->atoms = (xmlRegAtomPtr *) xmlMalloc(ctxt->maxAtoms *

1296

sizeof(xmlRegAtomPtr));

1297

if (ctxt->atoms == NULL) {

1298

xmlRegexpErrMemory(ctxt, "pushing atom");

1299

ctxt->maxAtoms = 0;

1300

return(-1);

1301

}

1302

} else if (ctxt->nbAtoms >= ctxt->maxAtoms) {

1303

xmlRegAtomPtr *tmp;

1304

ctxt->maxAtoms *= 2;

1305

tmp = (xmlRegAtomPtr *) xmlRealloc(ctxt->atoms, ctxt->maxAtoms *

1306

sizeof(xmlRegAtomPtr));

1307

if (tmp == NULL) {

1308

xmlRegexpErrMemory(ctxt, "allocating counter");

1309

ctxt->maxAtoms /= 2;

1310

return(-1);

1311

}

1312

ctxt->atoms = tmp;

1313

}

1314

atom->no = ctxt->nbAtoms;

1315

ctxt->atoms[ctxt->nbAtoms++] = atom;

1316

return(0);

1317

}

1318

1319

static void

1320

xmlRegStateAddTransTo(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr target,

1321

int from) {

1322

if (target->maxTransTo == 0) {

1323

target->maxTransTo = 8;

1324

target->transTo = (int *) xmlMalloc(target->maxTransTo *

1325

sizeof(int));

1326

if (target->transTo == NULL) {

1327

xmlRegexpErrMemory(ctxt, "adding transition");

1328

target->maxTransTo = 0;

1329

return;

1330

}

1331

} else if (target->nbTransTo >= target->maxTransTo) {

1332

int *tmp;

1333

target->maxTransTo *= 2;

1334

tmp = (int *) xmlRealloc(target->transTo, target->maxTransTo *

1335

sizeof(int));

1336

if (tmp == NULL) {

1337

xmlRegexpErrMemory(ctxt, "adding transition");

1338

target->maxTransTo /= 2;

1339

return;

1340

}

1341

target->transTo = tmp;

1342

}

1343

target->transTo[target->nbTransTo] = from;

1344

target->nbTransTo++;

1345

}

1346

1347

static void

1348

xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,

1349

xmlRegAtomPtr atom, xmlRegStatePtr target,

1350

int counter, int count) {

1351

1352

int nrtrans;

1353

1354

if (state == NULL) {

1355

ERROR("add state: state is NULL");

1356

return;

1357

}

1358

if (target == NULL) {

1359

ERROR("add state: target is NULL");

1360

return;

1361

}

1362

/*

1363

* Other routines follow the philosophy 'When in doubt, add a transition'

1364

* so we check here whether such a transition is already present and, if

1365

* so, silently ignore this request.

1366

*/

1367

1368

for (nrtrans = state->nbTrans - 1; nrtrans >= 0; nrtrans--) {

1369

xmlRegTransPtr trans = &(state->trans[nrtrans]);

1370

if ((trans->atom == atom) &&

1371

(trans->to == target->no) &&

1372

(trans->counter == counter) &&

1373

(trans->count == count)) {

1374

#ifdef DEBUG_REGEXP_GRAPH

1375

printf("Ignoring duplicate transition from %d to %d\n",

1376

state->no, target->no);

1377

#endif

1378

return;

1379

}

1380

}

1381

1382

if (state->maxTrans == 0) {

1383

state->maxTrans = 8;

1384

state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans *

1385

sizeof(xmlRegTrans));

1386

if (state->trans == NULL) {

1387

xmlRegexpErrMemory(ctxt, "adding transition");

1388

state->maxTrans = 0;

1389

return;

1390

}

1391

} else if (state->nbTrans >= state->maxTrans) {

1392

xmlRegTrans *tmp;

1393

state->maxTrans *= 2;

1394

tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans *

1395

sizeof(xmlRegTrans));

1396

if (tmp == NULL) {

1397

xmlRegexpErrMemory(ctxt, "adding transition");

1398

state->maxTrans /= 2;

1399

return;

1400

}

1401

state->trans = tmp;

1402

}

1403

#ifdef DEBUG_REGEXP_GRAPH

1404

printf("Add trans from %d to %d ", state->no, target->no);

1405

if (count == REGEXP_ALL_COUNTER)

1406

printf("all transition\n");

1407

else if (count >= 0)

1408

printf("count based %d\n", count);

1409

else if (counter >= 0)

1410

printf("counted %d\n", counter);

1411

else if (atom == NULL)

1412

printf("epsilon transition\n");

1413

else if (atom != NULL)

1414

xmlRegPrintAtom(stdout, atom);

1415

#endif

1416

1417

state->trans[state->nbTrans].atom = atom;

1418

state->trans[state->nbTrans].to = target->no;

1419

state->trans[state->nbTrans].counter = counter;

1420

state->trans[state->nbTrans].count = count;

1421

state->trans[state->nbTrans].nd = 0;

1422

state->nbTrans++;

1423

xmlRegStateAddTransTo(ctxt, target, state->no);

1424

}

1425

1426

static int

1427

xmlRegStatePush(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) {

1428

if (state == NULL) return(-1);

1429

if (ctxt->maxStates == 0) {

1430

ctxt->maxStates = 4;

1431

ctxt->states = (xmlRegStatePtr *) xmlMalloc(ctxt->maxStates *

1432

sizeof(xmlRegStatePtr));

1433

if (ctxt->states == NULL) {

1434

xmlRegexpErrMemory(ctxt, "adding state");

1435

ctxt->maxStates = 0;

1436

return(-1);

1437

}

1438

} else if (ctxt->nbStates >= ctxt->maxStates) {

1439

xmlRegStatePtr *tmp;

1440

ctxt->maxStates *= 2;

1441

tmp = (xmlRegStatePtr *) xmlRealloc(ctxt->states, ctxt->maxStates *

1442

sizeof(xmlRegStatePtr));

1443

if (tmp == NULL) {

1444

xmlRegexpErrMemory(ctxt, "adding state");

1445

ctxt->maxStates /= 2;

1446

return(-1);

1447

}

1448

ctxt->states = tmp;

1449

}

1450

state->no = ctxt->nbStates;

1451

ctxt->states[ctxt->nbStates++] = state;

1452

return(0);

1453

}

1454

1455

/**

1456

* xmlFAGenerateAllTransition:

1457

* @ctxt: a regexp parser context

1458

* @from: the from state

1459

* @to: the target state or NULL for building a new one

1460

* @lax:

1461

*

1462

*/

1463

static void

1464

xmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt,

1465

xmlRegStatePtr from, xmlRegStatePtr to,

1466

int lax) {

1467

if (to == NULL) {

1468

to = xmlRegNewState(ctxt);

1469

xmlRegStatePush(ctxt, to);

1470

ctxt->state = to;

1471

}

1472

if (lax)

1473

xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_LAX_COUNTER);

1474

else

1475

xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_COUNTER);

1476

}

1477

1478

/**

1479

* xmlFAGenerateEpsilonTransition:

1480

* @ctxt: a regexp parser context

1481

* @from: the from state

1482

* @to: the target state or NULL for building a new one

1483

*

1484

*/

1485

static void

1486

xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt,

1487

xmlRegStatePtr from, xmlRegStatePtr to) {

1488

if (to == NULL) {

1489

to = xmlRegNewState(ctxt);

1490

xmlRegStatePush(ctxt, to);

1491

ctxt->state = to;

1492

}

1493

xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1);

1494

}

1495

1496

/**

1497

* xmlFAGenerateCountedEpsilonTransition:

1498

* @ctxt: a regexp parser context

1499

* @from: the from state

1500

* @to: the target state or NULL for building a new one

1501

* counter: the counter for that transition

1502

*

1503

*/

1504

static void

1505

xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt,

1506

xmlRegStatePtr from, xmlRegStatePtr to, int counter) {

1507

if (to == NULL) {

1508

to = xmlRegNewState(ctxt);

1509

xmlRegStatePush(ctxt, to);

1510

ctxt->state = to;

1511

}

1512

xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1);

1513

}

1514

1515

/**

1516

* xmlFAGenerateCountedTransition:

1517

* @ctxt: a regexp parser context

1518

* @from: the from state

1519

* @to: the target state or NULL for building a new one

1520

* counter: the counter for that transition

1521

*

1522

*/

1523

static void

1524

xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt,

1525

xmlRegStatePtr from, xmlRegStatePtr to, int counter) {

1526

if (to == NULL) {

1527

to = xmlRegNewState(ctxt);

1528

xmlRegStatePush(ctxt, to);

1529

ctxt->state = to;

1530

}

1531

xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter);

1532

}

1533

1534

/**

1535

* xmlFAGenerateTransitions:

1536

* @ctxt: a regexp parser context

1537

* @from: the from state

1538

* @to: the target state or NULL for building a new one

1539

* @atom: the atom generating the transition

1540

*

1541

* Returns 0 if success and -1 in case of error.

1542

*/

1543

static int

1544

xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from,

1545

xmlRegStatePtr to, xmlRegAtomPtr atom) {

1546

xmlRegStatePtr end;

1547

1548

if (atom == NULL) {

1549

ERROR("genrate transition: atom == NULL");

1550

return(-1);

1551

}

1552

if (atom->type == XML_REGEXP_SUBREG) {

1553

/*

1554

* this is a subexpression handling one should not need to

1555

* create a new node except for XML_REGEXP_QUANT_RANGE.

1556

*/

1557

if (xmlRegAtomPush(ctxt, atom) < 0) {

1558

return(-1);

1559

}

1560

if ((to != NULL) && (atom->stop != to) &&

1561

(atom->quant != XML_REGEXP_QUANT_RANGE)) {

1562

/*

1563

* Generate an epsilon transition to link to the target

1564

*/

1565

xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);

1566

#ifdef DV

1567

} else if ((to == NULL) && (atom->quant != XML_REGEXP_QUANT_RANGE) &&

1568

(atom->quant != XML_REGEXP_QUANT_ONCE)) {

1569

to = xmlRegNewState(ctxt);

1570

xmlRegStatePush(ctxt, to);

1571

ctxt->state = to;

1572

xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);

1573

#endif

1574

}

1575

switch (atom->quant) {

1576

case XML_REGEXP_QUANT_OPT:

1577

atom->quant = XML_REGEXP_QUANT_ONCE;

1578

/*

1579

* transition done to the state after end of atom.

1580

* 1. set transition from atom start to new state

1581

* 2. set transition from atom end to this state.

1582

*/

1583

if (to == NULL) {

1584

xmlFAGenerateEpsilonTransition(ctxt, atom->start, 0);

1585

xmlFAGenerateEpsilonTransition(ctxt, atom->stop,

1586

ctxt->state);

1587

} else {

1588

xmlFAGenerateEpsilonTransition(ctxt, atom->start, to);

1589

}

1590

break;

1591

case XML_REGEXP_QUANT_MULT:

1592

atom->quant = XML_REGEXP_QUANT_ONCE;

1593

xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);

1594

xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);

1595

break;

1596

case XML_REGEXP_QUANT_PLUS:

1597

atom->quant = XML_REGEXP_QUANT_ONCE;

1598

xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);

1599

break;

1600

case XML_REGEXP_QUANT_RANGE: {

1601

int counter;

1602

xmlRegStatePtr inter, newstate;

1603

1604

/*

1605

* create the final state now if needed

1606

*/

1607

if (to != NULL) {

1608

newstate = to;

1609

} else {

1610

newstate = xmlRegNewState(ctxt);

1611

xmlRegStatePush(ctxt, newstate);

1612

}

1613

1614

/*

1615

* The principle here is to use counted transition

1616

* to avoid explosion in the number of states in the

1617

* graph. This is clearly more complex but should not

1618

* be exploitable at runtime.

1619

*/

1620

if ((atom->min == 0) && (atom->start0 == NULL)) {

1621

xmlRegAtomPtr copy;

1622

/*

1623

* duplicate a transition based on atom to count next

1624

* occurences after 1. We cannot loop to atom->start

1625

* directly because we need an epsilon transition to

1626

* newstate.

1627

*/

1628

/* ???? For some reason it seems we never reach that

1629

case, I suppose this got optimized out before when

1630

building the automata */

1631

copy = xmlRegCopyAtom(ctxt, atom);

1632

if (copy == NULL)

1633

return(-1);

1634

copy->quant = XML_REGEXP_QUANT_ONCE;

1635

copy->min = 0;

1636

copy->max = 0;

1637

1638

if (xmlFAGenerateTransitions(ctxt, atom->start, NULL, copy)

1639

< 0)

1640

return(-1);

1641

inter = ctxt->state;

1642

counter = xmlRegGetCounter(ctxt);

1643

ctxt->counters[counter].min = atom->min - 1;

1644

ctxt->counters[counter].max = atom->max - 1;

1645

/* count the number of times we see it again */

1646

xmlFAGenerateCountedEpsilonTransition(ctxt, inter,

1647

atom->stop, counter);

1648

/* allow a way out based on the count */

1649

xmlFAGenerateCountedTransition(ctxt, inter,

1650

newstate, counter);

1651

/* and also allow a direct exit for 0 */

1652

xmlFAGenerateEpsilonTransition(ctxt, atom->start,

1653

newstate);

1654

} else {

1655

/*

1656

* either we need the atom at least once or there

1657

* is an atom->start0 allowing to easilly plug the

1658

* epsilon transition.

1659

*/

1660

counter = xmlRegGetCounter(ctxt);

1661

ctxt->counters[counter].min = atom->min - 1;

1662

ctxt->counters[counter].max = atom->max - 1;

1663

/* count the number of times we see it again */

1664

xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,

1665

atom->start, counter);

1666

/* allow a way out based on the count */

1667

xmlFAGenerateCountedTransition(ctxt, atom->stop,

1668

newstate, counter);

1669

/* and if needed allow a direct exit for 0 */

1670

if (atom->min == 0)

1671

xmlFAGenerateEpsilonTransition(ctxt, atom->start0,

1672

newstate);

1673

1674

}

1675

atom->min = 0;

1676

atom->max = 0;

1677

atom->quant = XML_REGEXP_QUANT_ONCE;

1678

ctxt->state = newstate;

1679

}

1680

default:

1681

break;

1682

}

1683

return(0);

1684

}

1685

if ((atom->min == 0) && (atom->max == 0) &&

1686

(atom->quant == XML_REGEXP_QUANT_RANGE)) {

1687

/*

1688

* we can discard the atom and generate an epsilon transition instead

1689

*/

1690

if (to == NULL) {

1691

to = xmlRegNewState(ctxt);

1692

if (to != NULL)

1693

xmlRegStatePush(ctxt, to);

1694

else {

1695

return(-1);

1696

}

1697

}

1698

xmlFAGenerateEpsilonTransition(ctxt, from, to);

1699

ctxt->state = to;

1700

xmlRegFreeAtom(atom);

1701

return(0);

1702

}

1703

if (to == NULL) {

1704

to = xmlRegNewState(ctxt);

1705

if (to != NULL)

1706

xmlRegStatePush(ctxt, to);

1707

else {

1708

return(-1);

1709

}

1710

}

1711

end = to;

1712

if ((atom->quant == XML_REGEXP_QUANT_MULT) ||

1713

(atom->quant == XML_REGEXP_QUANT_PLUS)) {

1714

/*

1715

* Do not pollute the target state by adding transitions from

1716

* it as it is likely to be the shared target of multiple branches.

1717

* So isolate with an epsilon transition.

1718

*/

1719

xmlRegStatePtr tmp;

1720

1721

tmp = xmlRegNewState(ctxt);

1722

if (tmp != NULL)

1723

xmlRegStatePush(ctxt, tmp);

1724

else {

1725

return(-1);

1726

}

1727

xmlFAGenerateEpsilonTransition(ctxt, tmp, to);

1728

to = tmp;

1729

}

1730

if (xmlRegAtomPush(ctxt, atom) < 0) {

1731

return(-1);

1732

}

1733

xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1);

1734

ctxt->state = end;

1735

switch (atom->quant) {

1736

case XML_REGEXP_QUANT_OPT:

1737

atom->quant = XML_REGEXP_QUANT_ONCE;

1738

xmlFAGenerateEpsilonTransition(ctxt, from, to);

1739

break;

1740

case XML_REGEXP_QUANT_MULT:

1741

atom->quant = XML_REGEXP_QUANT_ONCE;

1742

xmlFAGenerateEpsilonTransition(ctxt, from, to);

1743

xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);

1744

break;

1745

case XML_REGEXP_QUANT_PLUS:

1746

atom->quant = XML_REGEXP_QUANT_ONCE;

1747

xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);

1748

break;

1749

case XML_REGEXP_QUANT_RANGE:

1750

#if DV_test

1751

if (atom->min == 0) {

1752

xmlFAGenerateEpsilonTransition(ctxt, from, to);

1753

}

1754

#endif

1755

break;

1756

default:

1757

break;

1758

}

1759

return(0);

1760

}

1761

1762

/**

1763

* xmlFAReduceEpsilonTransitions:

1764

* @ctxt: a regexp parser context

1765

* @fromnr: the from state

1766

* @tonr: the to state

1767

* @counter: should that transition be associated to a counted

1768

*

1769

*/

1770

static void

1771

xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr,

1772

int tonr, int counter) {

1773

int transnr;

1774

xmlRegStatePtr from;

1775

xmlRegStatePtr to;

1776

1777

#ifdef DEBUG_REGEXP_GRAPH

1778

printf("xmlFAReduceEpsilonTransitions(%d, %d)\n", fromnr, tonr);

1779

#endif

1780

from = ctxt->states[fromnr];

1781

if (from == NULL)

1782

return;

1783

to = ctxt->states[tonr];

1784

if (to == NULL)

1785

return;

1786

if ((to->mark == XML_REGEXP_MARK_START) ||

1787

(to->mark == XML_REGEXP_MARK_VISITED))

1788

return;

1789

1790

to->mark = XML_REGEXP_MARK_VISITED;

1791

if (to->type == XML_REGEXP_FINAL_STATE) {

1792

#ifdef DEBUG_REGEXP_GRAPH

1793

printf("State %d is final, so %d becomes final\n", tonr, fromnr);

1794

#endif

1795

from->type = XML_REGEXP_FINAL_STATE;

1796

}

1797

for (transnr = 0;transnr < to->nbTrans;transnr++) {

1798

if (to->trans[transnr].to < 0)

1799

continue;

1800

if (to->trans[transnr].atom == NULL) {

1801

/*

1802

* Don't remove counted transitions

1803

* Don't loop either

1804

*/

1805

if (to->trans[transnr].to != fromnr) {

1806

if (to->trans[transnr].count >= 0) {

1807

int newto = to->trans[transnr].to;

1808

1809

xmlRegStateAddTrans(ctxt, from, NULL,

1810

ctxt->states[newto],

1811

-1, to->trans[transnr].count);

1812

} else {

1813

#ifdef DEBUG_REGEXP_GRAPH

1814

printf("Found epsilon trans %d from %d to %d\n",

1815

transnr, tonr, to->trans[transnr].to);

1816

#endif

1817

if (to->trans[transnr].counter >= 0) {

1818

xmlFAReduceEpsilonTransitions(ctxt, fromnr,

1819

to->trans[transnr].to,

1820

to->trans[transnr].counter);

1821

} else {

1822

xmlFAReduceEpsilonTransitions(ctxt, fromnr,

1823

to->trans[transnr].to,

1824

counter);

1825

}

1826

}

1827

}

1828

} else {

1829

int newto = to->trans[transnr].to;

1830

1831

if (to->trans[transnr].counter >= 0) {

1832

xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,

1833

ctxt->states[newto],

1834

to->trans[transnr].counter, -1);

1835

} else {

1836

xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,

1837

ctxt->states[newto], counter, -1);

1838

}

1839

}

1840

}

1841

to->mark = XML_REGEXP_MARK_NORMAL;

1842

}

1843

1844

/**

1845

* xmlFAEliminateSimpleEpsilonTransitions:

1846

* @ctxt: a regexp parser context

1847

*

1848

* Eliminating general epsilon transitions can get costly in the general

1849

* algorithm due to the large amount of generated new transitions and

1850

* associated comparisons. However for simple epsilon transition used just

1851

* to separate building blocks when generating the automata this can be

1852

* reduced to state elimination:

1853

* - if there exists an epsilon from X to Y

1854

* - if there is no other transition from X

1855

* then X and Y are semantically equivalent and X can be eliminated

1856

* If X is the start state then make Y the start state, else replace the

1857

* target of all transitions to X by transitions to Y.

1858

*/

1859

static void

1860

xmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {

1861

int statenr, i, j, newto;

1862

xmlRegStatePtr state, tmp;

1863

1864

for (statenr = 0;statenr < ctxt->nbStates;statenr++) {

1865

state = ctxt->states[statenr];

1866

if (state == NULL)

1867

continue;

1868

if (state->nbTrans != 1)

1869

continue;

1870

if (state->type == XML_REGEXP_UNREACH_STATE)

1871

continue;

1872

/* is the only transition out a basic transition */

1873

if ((state->trans[0].atom == NULL) &&

1874

(state->trans[0].to >= 0) &&

1875

(state->trans[0].to != statenr) &&

1876

(state->trans[0].counter < 0) &&

1877

(state->trans[0].count < 0)) {

1878

newto = state->trans[0].to;

1879

1880

if (state->type == XML_REGEXP_START_STATE) {

1881

#ifdef DEBUG_REGEXP_GRAPH

1882

printf("Found simple epsilon trans from start %d to %d\n",

1883

statenr, newto);

1884

#endif

1885

} else {

1886

#ifdef DEBUG_REGEXP_GRAPH

1887

printf("Found simple epsilon trans from %d to %d\n",

1888

statenr, newto);

1889

#endif

1890

for (i = 0;i < state->nbTransTo;i++) {

1891

tmp = ctxt->states[state->transTo[i]];

1892

for (j = 0;j < tmp->nbTrans;j++) {

1893

if (tmp->trans[j].to == statenr) {

1894

#ifdef DEBUG_REGEXP_GRAPH

1895

printf("Changed transition %d on %d to go to %d\n",

1896

j, tmp->no, newto);

1897

#endif

1898

tmp->trans[j].to = -1;

1899

xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom,

1900

ctxt->states[newto],

1901

tmp->trans[j].counter,

1902

tmp->trans[j].count);

1903

}

1904

}

1905

}

1906

if (state->type == XML_REGEXP_FINAL_STATE)

1907

ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE;

1908

/* eliminate the transition completely */

1909

state->nbTrans = 0;

1910

1911

state->type = XML_REGEXP_UNREACH_STATE;

1912

1913

}

1914

1915

}

1916

}

1917

}

1918

/**

1919

* xmlFAEliminateEpsilonTransitions:

1920

* @ctxt: a regexp parser context

1921

*

1922

*/

1923

static void

1924

xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {

1925

int statenr, transnr;

1926

xmlRegStatePtr state;

1927

int has_epsilon;

1928

1929

if (ctxt->states == NULL) return;

1930

1931

/*

1932

* Eliminate simple epsilon transition and the associated unreachable

1933

* states.

1934

*/

1935

xmlFAEliminateSimpleEpsilonTransitions(ctxt);

1936

for (statenr = 0;statenr < ctxt->nbStates;statenr++) {

1937

state = ctxt->states[statenr];

1938

if ((state != NULL) && (state->type == XML_REGEXP_UNREACH_STATE)) {

1939

#ifdef DEBUG_REGEXP_GRAPH

1940

printf("Removed unreachable state %d\n", statenr);

1941

#endif

1942

xmlRegFreeState(state);

1943

ctxt->states[statenr] = NULL;

1944

}

1945

}

1946

1947

has_epsilon = 0;

1948

1949

/*

1950

* Build the completed transitions bypassing the epsilons

1951

* Use a marking algorithm to avoid loops

1952

* Mark sink states too.

1953

* Process from the latests states backward to the start when

1954

* there is long cascading epsilon chains this minimize the

1955

* recursions and transition compares when adding the new ones

1956

*/

1957

for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) {

1958

state = ctxt->states[statenr];

1959

if (state == NULL)

1960

continue;

1961

if ((state->nbTrans == 0) &&

1962

(state->type != XML_REGEXP_FINAL_STATE)) {

1963

state->type = XML_REGEXP_SINK_STATE;

1964

}

1965

for (transnr = 0;transnr < state->nbTrans;transnr++) {

1966

if ((state->trans[transnr].atom == NULL) &&

1967

(state->trans[transnr].to >= 0)) {

1968

if (state->trans[transnr].to == statenr) {

1969

state->trans[transnr].to = -1;

1970

#ifdef DEBUG_REGEXP_GRAPH

1971

printf("Removed loopback epsilon trans %d on %d\n",

1972

transnr, statenr);

1973

#endif

1974

} else if (state->trans[transnr].count < 0) {

1975

int newto = state->trans[transnr].to;

1976

1977

#ifdef DEBUG_REGEXP_GRAPH

1978

printf("Found epsilon trans %d from %d to %d\n",

1979

transnr, statenr, newto);

1980

#endif

1981

has_epsilon = 1;

1982

state->trans[transnr].to = -2;

1983

state->mark = XML_REGEXP_MARK_START;

1984

xmlFAReduceEpsilonTransitions(ctxt, statenr,

1985

newto, state->trans[transnr].counter);

1986

state->mark = XML_REGEXP_MARK_NORMAL;

1987

#ifdef DEBUG_REGEXP_GRAPH

1988

} else {

1989

printf("Found counted transition %d on %d\n",

1990

transnr, statenr);

1991

#endif

1992

}

1993

}

1994

}

1995

}

1996

/*

1997

* Eliminate the epsilon transitions

1998

*/

1999

if (has_epsilon) {

2000

for (statenr = 0;statenr < ctxt->nbStates;statenr++) {

2001

state = ctxt->states[statenr];

2002

if (state == NULL)

2003

continue;

2004

for (transnr = 0;transnr < state->nbTrans;transnr++) {

2005

xmlRegTransPtr trans = &(state->trans[transnr]);

2006

if ((trans->atom == NULL) &&

2007

(trans->count < 0) &&

2008

(trans->to >= 0)) {

2009

trans->to = -1;

2010

}

2011

}

2012

}

2013

}

2014

2015

/*

2016

* Use this pass to detect unreachable states too

2017

*/

2018

for (statenr = 0;statenr < ctxt->nbStates;statenr++) {

2019

state = ctxt->states[statenr];

2020

if (state != NULL)

2021

state->reached = XML_REGEXP_MARK_NORMAL;

2022

}

2023

state = ctxt->states[0];

2024

if (state != NULL)

2025

state->reached = XML_REGEXP_MARK_START;

2026

while (state != NULL) {

2027

xmlRegStatePtr target = NULL;

2028

state->reached = XML_REGEXP_MARK_VISITED;

2029

/*

2030

* Mark all states reachable from the current reachable state

2031

*/

2032

for (transnr = 0;transnr < state->nbTrans;transnr++) {

2033

if ((state->trans[transnr].to >= 0) &&

2034

((state->trans[transnr].atom != NULL) ||

2035

(state->trans[transnr].count >= 0))) {

2036

int newto = state->trans[transnr].to;

2037

2038

if (ctxt->states[newto] == NULL)

2039

continue;

2040

if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) {

2041

ctxt->states[newto]->reached = XML_REGEXP_MARK_START;

2042

target = ctxt->states[newto];

2043

}

2044

}

2045

}

2046

2047

/*

2048

* find the next accessible state not explored

2049

*/

2050

if (target == NULL) {

2051

for (statenr = 1;statenr < ctxt->nbStates;statenr++) {

2052

state = ctxt->states[statenr];

2053

if ((state != NULL) && (state->reached ==

2054

XML_REGEXP_MARK_START)) {

2055

target = state;

2056

break;

2057

}

2058

}

2059

}

2060

state = target;

2061

}

2062

for (statenr = 0;statenr < ctxt->nbStates;statenr++) {

2063

state = ctxt->states[statenr];

2064

if ((state != NULL) && (state->reached == XML_REGEXP_MARK_NORMAL)) {

2065

#ifdef DEBUG_REGEXP_GRAPH

2066

printf("Removed unreachable state %d\n", statenr);

2067

#endif

2068

xmlRegFreeState(state);

2069

ctxt->states[statenr] = NULL;

2070

}

2071

}

2072

2073

}

2074

2075

static int

2076

xmlFACompareRanges(xmlRegRangePtr range1, xmlRegRangePtr range2) {

2077

int ret = 0;

2078

2079

if ((range1->type == XML_REGEXP_RANGES) ||

2080

(range2->type == XML_REGEXP_RANGES) ||

2081

(range2->type == XML_REGEXP_SUBREG) ||

2082

(range1->type == XML_REGEXP_SUBREG) ||

2083

(range1->type == XML_REGEXP_STRING) ||

2084

(range2->type == XML_REGEXP_STRING))

2085

return(-1);

2086

2087

/* put them in order */

2088

if (range1->type > range2->type) {

2089

xmlRegRangePtr tmp;

2090

2091

tmp = range1;

2092

range1 = range2;

2093

range2 = tmp;

2094

}

2095

if ((range1->type == XML_REGEXP_ANYCHAR) ||

2096

(range2->type == XML_REGEXP_ANYCHAR)) {

2097

ret = 1;

2098

} else if ((range1->type == XML_REGEXP_EPSILON) ||

2099

(range2->type == XML_REGEXP_EPSILON)) {

2100

return(0);

2101

} else if (range1->type == range2->type) {

2102

if (range1->type != XML_REGEXP_CHARVAL)

2103

ret = 1;

2104

else if ((range1->end < range2->start) ||

2105

(range2->end < range1->start))

2106

ret = 0;

2107

else

2108

ret = 1;

2109

} else if (range1->type == XML_REGEXP_CHARVAL) {

2110

int codepoint;

2111

int neg = 0;

2112

2113

/*

2114

* just check all codepoints in the range for acceptance,

2115

* this is usually way cheaper since done only once at

2116

* compilation than testing over and over at runtime or

2117

* pushing too many states when evaluating.

2118

*/

2119

if (((range1->neg == 0) && (range2->neg != 0)) ||

2120

((range1->neg != 0) && (range2->neg == 0)))

2121

neg = 1;

2122

2123

for (codepoint = range1->start;codepoint <= range1->end ;codepoint++) {

2124

ret = xmlRegCheckCharacterRange(range2->type, codepoint,

2125

0, range2->start, range2->end,

2126

range2->blockName);

2127

if (ret < 0)

2128

return(-1);

2129

if (((neg == 1) && (ret == 0)) ||

2130

((neg == 0) && (ret == 1)))

2131

return(1);

2132

}

2133

return(0);

2134

} else if ((range1->type == XML_REGEXP_BLOCK_NAME) ||

2135

(range2->type == XML_REGEXP_BLOCK_NAME)) {

2136

if (range1->type == range2->type) {

2137

ret = xmlStrEqual(range1->blockName, range2->blockName);

2138

} else {

2139

/*

2140

* comparing a block range with anything else is way

2141

* too costly, and maintining the table is like too much

2142

* memory too, so let's force the automata to save state

2143

* here.

2144

*/

2145

return(1);

2146

}

2147

} else if ((range1->type < XML_REGEXP_LETTER) ||

2148

(range2->type < XML_REGEXP_LETTER)) {

2149

if ((range1->type == XML_REGEXP_ANYSPACE) &&

2150

(range2->type == XML_REGEXP_NOTSPACE))

2151

ret = 0;

2152

else if ((range1->type == XML_REGEXP_INITNAME) &&

2153

(range2->type == XML_REGEXP_NOTINITNAME))

2154

ret = 0;

2155

else if ((range1->type == XML_REGEXP_NAMECHAR) &&

2156

(range2->type == XML_REGEXP_NOTNAMECHAR))

2157

ret = 0;

2158

else if ((range1->type == XML_REGEXP_DECIMAL) &&

2159

(range2->type == XML_REGEXP_NOTDECIMAL))

2160

ret = 0;

2161

else if ((range1->type == XML_REGEXP_REALCHAR) &&

2162

(range2->type == XML_REGEXP_NOTREALCHAR))

2163

ret = 0;

2164

else {

2165

/* same thing to limit complexity */

2166

return(1);

2167

}

2168

} else {

2169

ret = 0;

2170

/* range1->type < range2->type here */

2171

switch (range1->type) {

2172

case XML_REGEXP_LETTER:

2173

/* all disjoint except in the subgroups */

2174

if ((range2->type == XML_REGEXP_LETTER_UPPERCASE) ||

2175

(range2->type == XML_REGEXP_LETTER_LOWERCASE) ||

2176

(range2->type == XML_REGEXP_LETTER_TITLECASE) ||

2177

(range2->type == XML_REGEXP_LETTER_MODIFIER) ||

2178

(range2->type == XML_REGEXP_LETTER_OTHERS))

2179

ret = 1;

2180

break;

2181

case XML_REGEXP_MARK:

2182

if ((range2->type == XML_REGEXP_MARK_NONSPACING) ||

2183

(range2->type == XML_REGEXP_MARK_SPACECOMBINING) ||

2184

(range2->type == XML_REGEXP_MARK_ENCLOSING))

2185

ret = 1;

2186

break;

2187

case XML_REGEXP_NUMBER:

2188

if ((range2->type == XML_REGEXP_NUMBER_DECIMAL) ||

2189

(range2->type == XML_REGEXP_NUMBER_LETTER) ||

2190

(range2->type == XML_REGEXP_NUMBER_OTHERS))

2191

ret = 1;

2192

break;

2193

case XML_REGEXP_PUNCT:

2194

if ((range2->type == XML_REGEXP_PUNCT_CONNECTOR) ||

2195

(range2->type == XML_REGEXP_PUNCT_DASH) ||

2196

(range2->type == XML_REGEXP_PUNCT_OPEN) ||

2197

(range2->type == XML_REGEXP_PUNCT_CLOSE) ||

2198

(range2->type == XML_REGEXP_PUNCT_INITQUOTE) ||

2199

(range2->type == XML_REGEXP_PUNCT_FINQUOTE) ||

2200

(range2->type == XML_REGEXP_PUNCT_OTHERS))

2201

ret = 1;

2202

break;

2203

case XML_REGEXP_SEPAR:

2204

if ((range2->type == XML_REGEXP_SEPAR_SPACE) ||

2205

(range2->type == XML_REGEXP_SEPAR_LINE) ||

2206

(range2->type == XML_REGEXP_SEPAR_PARA))

2207

ret = 1;

2208

break;

2209

case XML_REGEXP_SYMBOL:

2210

if ((range2->type == XML_REGEXP_SYMBOL_MATH) ||

2211

(range2->type == XML_REGEXP_SYMBOL_CURRENCY) ||

2212

(range2->type == XML_REGEXP_SYMBOL_MODIFIER) ||

2213

(range2->type == XML_REGEXP_SYMBOL_OTHERS))

2214

ret = 1;

2215

break;

2216

case XML_REGEXP_OTHER:

2217

if ((range2->type == XML_REGEXP_OTHER_CONTROL) ||

2218

(range2->type == XML_REGEXP_OTHER_FORMAT) ||

2219

(range2->type == XML_REGEXP_OTHER_PRIVATE))

2220

ret = 1;

2221

break;

2222

default:

2223

if ((range2->type >= XML_REGEXP_LETTER) &&

2224

(range2->type < XML_REGEXP_BLOCK_NAME))

2225

ret = 0;

2226

else {

2227

/* safety net ! */

2228

return(1);

2229

}

2230

}

2231

}

2232

if (((range1->neg == 0) && (range2->neg != 0)) ||

2233

((range1->neg != 0) && (range2->neg == 0)))

2234

ret = !ret;

2235

return(ret);

2236

}

2237

2238

/**

2239

* xmlFACompareAtomTypes:

2240

* @type1: an atom type

2241

* @type2: an atom type

2242

*

2243

* Compares two atoms type to check whether they intersect in some ways,

2244

* this is used by xmlFACompareAtoms only

2245

*

2246

* Returns 1 if they may intersect and 0 otherwise

2247

*/

2248

static int

2249

xmlFACompareAtomTypes(xmlRegAtomType type1, xmlRegAtomType type2) {

2250

if ((type1 == XML_REGEXP_EPSILON) ||

2251

(type1 == XML_REGEXP_CHARVAL) ||

2252

(type1 == XML_REGEXP_RANGES) ||

2253

(type1 == XML_REGEXP_SUBREG) ||

2254

(type1 == XML_REGEXP_STRING) ||

2255

(type1 == XML_REGEXP_ANYCHAR))

2256

return(1);

2257

if ((type2 == XML_REGEXP_EPSILON) ||

2258

(type2 == XML_REGEXP_CHARVAL) ||

2259

(type2 == XML_REGEXP_RANGES) ||

2260

(type2 == XML_REGEXP_SUBREG) ||

2261

(type2 == XML_REGEXP_STRING) ||

2262

(type2 == XML_REGEXP_ANYCHAR))

2263

return(1);

2264

2265

if (type1 == type2) return(1);

2266

2267

/* simplify subsequent compares by making sure type1 < type2 */

2268

if (type1 > type2) {

2269

xmlRegAtomType tmp = type1;

2270

type1 = type2;

2271

type2 = tmp;

2272

}

2273

switch (type1) {

2274

case XML_REGEXP_ANYSPACE: /* \s */

2275

/* can't be a letter, number, mark, pontuation, symbol */

2276

if ((type2 == XML_REGEXP_NOTSPACE) ||

2277

((type2 >= XML_REGEXP_LETTER) &&

2278

(type2 <= XML_REGEXP_LETTER_OTHERS)) ||

2279

((type2 >= XML_REGEXP_NUMBER) &&

2280

(type2 <= XML_REGEXP_NUMBER_OTHERS)) ||

2281

((type2 >= XML_REGEXP_MARK) &&

2282

(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||

2283

((type2 >= XML_REGEXP_PUNCT) &&

2284

(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||

2285

((type2 >= XML_REGEXP_SYMBOL) &&

2286

(type2 <= XML_REGEXP_SYMBOL_OTHERS))

2287

) return(0);

2288

break;

2289

case XML_REGEXP_NOTSPACE: /* \S */

2290

break;

2291

case XML_REGEXP_INITNAME: /* \l */

2292

/* can't be a number, mark, separator, pontuation, symbol or other */

2293

if ((type2 == XML_REGEXP_NOTINITNAME) ||

2294

((type2 >= XML_REGEXP_NUMBER) &&

2295

(type2 <= XML_REGEXP_NUMBER_OTHERS)) ||

2296

((type2 >= XML_REGEXP_MARK) &&

2297

(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||

2298

((type2 >= XML_REGEXP_SEPAR) &&

2299

(type2 <= XML_REGEXP_SEPAR_PARA)) ||

2300

((type2 >= XML_REGEXP_PUNCT) &&

2301

(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||

2302

((type2 >= XML_REGEXP_SYMBOL) &&

2303

(type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||

2304

((type2 >= XML_REGEXP_OTHER) &&

2305

(type2 <= XML_REGEXP_OTHER_NA))

2306

) return(0);

2307

break;

2308

case XML_REGEXP_NOTINITNAME: /* \L */

2309

break;

2310

case XML_REGEXP_NAMECHAR: /* \c */

2311

/* can't be a mark, separator, pontuation, symbol or other */

2312

if ((type2 == XML_REGEXP_NOTNAMECHAR) ||

2313

((type2 >= XML_REGEXP_MARK) &&

2314

(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||

2315

((type2 >= XML_REGEXP_PUNCT) &&

2316

(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||

2317

((type2 >= XML_REGEXP_SEPAR) &&

2318

(type2 <= XML_REGEXP_SEPAR_PARA)) ||

2319

((type2 >= XML_REGEXP_SYMBOL) &&

2320

(type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||

2321

((type2 >= XML_REGEXP_OTHER) &&

2322

(type2 <= XML_REGEXP_OTHER_NA))

2323

) return(0);

2324

break;

2325

case XML_REGEXP_NOTNAMECHAR: /* \C */

2326

break;

2327

case XML_REGEXP_DECIMAL: /* \d */

2328

/* can't be a letter, mark, separator, pontuation, symbol or other */

2329

if ((type2 == XML_REGEXP_NOTDECIMAL) ||

2330

(type2 == XML_REGEXP_REALCHAR) ||

2331

((type2 >= XML_REGEXP_LETTER) &&

2332

(type2 <= XML_REGEXP_LETTER_OTHERS)) ||

2333

((type2 >= XML_REGEXP_MARK) &&

2334

(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||

2335

((type2 >= XML_REGEXP_PUNCT) &&

2336

(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||

2337

((type2 >= XML_REGEXP_SEPAR) &&

2338

(type2 <= XML_REGEXP_SEPAR_PARA)) ||

2339

((type2 >= XML_REGEXP_SYMBOL) &&

2340

(type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||

2341

((type2 >= XML_REGEXP_OTHER) &&

2342

(type2 <= XML_REGEXP_OTHER_NA))

2343

)return(0);

2344

break;

2345

case XML_REGEXP_NOTDECIMAL: /* \D */

2346

break;

2347

case XML_REGEXP_REALCHAR: /* \w */

2348

/* can't be a mark, separator, pontuation, symbol or other */

2349

if ((type2 == XML_REGEXP_NOTDECIMAL) ||

2350

((type2 >= XML_REGEXP_MARK) &&

2351

(type2 <= XML_REGEXP_MARK_ENCLOSING)) ||

2352

((type2 >= XML_REGEXP_PUNCT) &&

2353

(type2 <= XML_REGEXP_PUNCT_OTHERS)) ||

2354

((type2 >= XML_REGEXP_SEPAR) &&

2355

(type2 <= XML_REGEXP_SEPAR_PARA)) ||

2356

((type2 >= XML_REGEXP_SYMBOL) &&

2357

(type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||

2358

((type2 >= XML_REGEXP_OTHER) &&

2359

(type2 <= XML_REGEXP_OTHER_NA))

2360

)return(0);

2361

break;

2362

case XML_REGEXP_NOTREALCHAR: /* \W */

2363

break;

2364

/*

2365

* at that point we know both type 1 and type2 are from

2366

* character categories are ordered and are different,

2367

* it becomes simple because this is a partition

2368

*/

2369

case XML_REGEXP_LETTER:

2370

if (type2 <= XML_REGEXP_LETTER_OTHERS)

2371

return(1);

2372

return(0);

2373

case XML_REGEXP_LETTER_UPPERCASE:

2374

case XML_REGEXP_LETTER_LOWERCASE:

2375

case XML_REGEXP_LETTER_TITLECASE:

2376

case XML_REGEXP_LETTER_MODIFIER:

2377

case XML_REGEXP_LETTER_OTHERS:

2378

return(0);

2379

case XML_REGEXP_MARK:

2380

if (type2 <= XML_REGEXP_MARK_ENCLOSING)

2381

return(1);

2382

return(0);

2383

case XML_REGEXP_MARK_NONSPACING:

2384

case XML_REGEXP_MARK_SPACECOMBINING:

2385

case XML_REGEXP_MARK_ENCLOSING:

2386

return(0);

2387

case XML_REGEXP_NUMBER:

2388

if (type2 <= XML_REGEXP_NUMBER_OTHERS)

2389

return(1);

2390

return(0);

2391

case XML_REGEXP_NUMBER_DECIMAL:

2392

case XML_REGEXP_NUMBER_LETTER:

2393

case XML_REGEXP_NUMBER_OTHERS:

2394

return(0);

2395

case XML_REGEXP_PUNCT:

2396

if (type2 <= XML_REGEXP_PUNCT_OTHERS)

2397

return(1);

2398

return(0);

2399

case XML_REGEXP_PUNCT_CONNECTOR:

2400

case XML_REGEXP_PUNCT_DASH:

2401

case XML_REGEXP_PUNCT_OPEN:

2402

case XML_REGEXP_PUNCT_CLOSE:

2403

case XML_REGEXP_PUNCT_INITQUOTE:

2404

case XML_REGEXP_PUNCT_FINQUOTE:

2405

case XML_REGEXP_PUNCT_OTHERS:

2406

return(0);

2407

case XML_REGEXP_SEPAR:

2408

if (type2 <= XML_REGEXP_SEPAR_PARA)

2409

return(1);

2410

return(0);

2411

case XML_REGEXP_SEPAR_SPACE:

2412

case XML_REGEXP_SEPAR_LINE:

2413

case XML_REGEXP_SEPAR_PARA:

2414

return(0);

2415

case XML_REGEXP_SYMBOL:

2416

if (type2 <= XML_REGEXP_SYMBOL_OTHERS)

2417

return(1);

2418

return(0);

2419

case XML_REGEXP_SYMBOL_MATH:

2420

case XML_REGEXP_SYMBOL_CURRENCY:

2421

case XML_REGEXP_SYMBOL_MODIFIER:

2422

case XML_REGEXP_SYMBOL_OTHERS:

2423

return(0);

2424

case XML_REGEXP_OTHER:

2425

if (type2 <= XML_REGEXP_OTHER_NA)

2426

return(1);

2427

return(0);

2428

case XML_REGEXP_OTHER_CONTROL:

2429

case XML_REGEXP_OTHER_FORMAT:

2430

case XML_REGEXP_OTHER_PRIVATE:

2431

case XML_REGEXP_OTHER_NA:

2432

return(0);

2433

default:

2434

break;

2435

}

2436

return(1);

2437

}

2438

2439

/**

2440

* xmlFAEqualAtoms:

2441

* @atom1: an atom

2442

* @atom2: an atom

2443

* @deep: if not set only compare string pointers

2444

*

2445

* Compares two atoms to check whether they are the same exactly

2446

* this is used to remove equivalent transitions

2447

*

2448

* Returns 1 if same and 0 otherwise

2449

*/

2450

static int

2451

xmlFAEqualAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) {

2452

int ret = 0;

2453

2454

if (atom1 == atom2)

2455

return(1);

2456

if ((atom1 == NULL) || (atom2 == NULL))

2457

return(0);

2458

2459

if (atom1->type != atom2->type)

2460

return(0);

2461

switch (atom1->type) {

2462

case XML_REGEXP_EPSILON:

2463

ret = 0;

2464

break;

2465

case XML_REGEXP_STRING:

2466

if (!deep)

2467

ret = (atom1->valuep == atom2->valuep);

2468

else

2469

ret = xmlStrEqual((xmlChar *)atom1->valuep,

2470

(xmlChar *)atom2->valuep);

2471

break;

2472

case XML_REGEXP_CHARVAL:

2473

ret = (atom1->codepoint == atom2->codepoint);

2474

break;

2475

case XML_REGEXP_RANGES:

2476

/* too hard to do in the general case */

2477

ret = 0;

2478

default:

2479

break;

2480

}

2481

return(ret);

2482

}

2483

2484

/**

2485

* xmlFACompareAtoms:

2486

* @atom1: an atom

2487

* @atom2: an atom

2488

* @deep: if not set only compare string pointers

2489

*

2490

* Compares two atoms to check whether they intersect in some ways,

2491

* this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only

2492

*

2493

* Returns 1 if yes and 0 otherwise

2494

*/

2495

static int

2496

xmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) {

2497

int ret = 1;

2498

2499

if (atom1 == atom2)

2500

return(1);

2501

if ((atom1 == NULL) || (atom2 == NULL))

2502

return(0);

2503

2504

if ((atom1->type == XML_REGEXP_ANYCHAR) ||

2505

(atom2->type == XML_REGEXP_ANYCHAR))

2506

return(1);

2507

2508

if (atom1->type > atom2->type) {

2509

xmlRegAtomPtr tmp;

2510

tmp = atom1;

2511

atom1 = atom2;

2512

atom2 = tmp;

2513

}

2514

if (atom1->type != atom2->type) {

2515

ret = xmlFACompareAtomTypes(atom1->type, atom2->type);

2516

/* if they can't intersect at the type level break now */

2517

if (ret == 0)

2518

return(0);

2519

}

2520

switch (atom1->type) {

2521

case XML_REGEXP_STRING:

2522

if (!deep)

2523

ret = (atom1->valuep != atom2->valuep);

2524

else

2525

ret = xmlRegStrEqualWildcard((xmlChar *)atom1->valuep,

2526

(xmlChar *)atom2->valuep);

2527

break;

2528

case XML_REGEXP_EPSILON:

2529

goto not_determinist;

2530

case XML_REGEXP_CHARVAL:

2531

if (atom2->type == XML_REGEXP_CHARVAL) {

2532

ret = (atom1->codepoint == atom2->codepoint);

2533

} else {

2534

ret = xmlRegCheckCharacter(atom2, atom1->codepoint);

2535

if (ret < 0)

2536

ret = 1;

2537

}

2538

break;

2539

case XML_REGEXP_RANGES:

2540

if (atom2->type == XML_REGEXP_RANGES) {

2541

int i, j, res;

2542

xmlRegRangePtr r1, r2;

2543

2544

/*

2545

* need to check that none of the ranges eventually matches

2546

*/

2547

for (i = 0;i < atom1->nbRanges;i++) {

2548

for (j = 0;j < atom2->nbRanges;j++) {

2549

r1 = atom1->ranges[i];

2550

r2 = atom2->ranges[j];

2551

res = xmlFACompareRanges(r1, r2);

2552

if (res == 1) {

2553

ret = 1;

2554

goto done;

2555

}

2556

}

2557

}

2558

ret = 0;

2559

}

2560

break;

2561

default:

2562

goto not_determinist;

2563

}

2564

done:

2565

if (atom1->neg != atom2->neg) {

2566

ret = !ret;

2567

}

2568

if (ret == 0)

2569

return(0);

2570

not_determinist:

2571

return(1);

2572

}

2573

2574

/**

2575

* xmlFARecurseDeterminism:

2576

* @ctxt: a regexp parser context

2577

*

2578

* Check whether the associated regexp is determinist,

2579

* should be called after xmlFAEliminateEpsilonTransitions()

2580

*

2581

*/

2582

static int

2583

xmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,

2584

int to, xmlRegAtomPtr atom) {

2585

int ret = 1;

2586

int res;

2587

int transnr, nbTrans;

2588

xmlRegTransPtr t1;

2589

int deep = 1;

2590

2591

if (state == NULL)

2592

return(ret);

2593

if (state->markd == XML_REGEXP_MARK_VISITED)

2594

return(ret);

2595

2596

if (ctxt->flags & AM_AUTOMATA_RNG)

2597

deep = 0;

2598

2599

/*

2600

* don't recurse on transitions potentially added in the course of

2601

* the elimination.

2602

*/

2603

nbTrans = state->nbTrans;

2604

for (transnr = 0;transnr < nbTrans;transnr++) {

2605

t1 = &(state->trans[transnr]);

2606

/*

2607

* check transitions conflicting with the one looked at

2608

*/

2609

if (t1->atom == NULL) {

2610

if (t1->to < 0)

2611

continue;

2612

state->markd = XML_REGEXP_MARK_VISITED;

2613

res = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],

2614

to, atom);

2615

state->markd = 0;

2616

if (res == 0) {

2617

ret = 0;

2618

/* t1->nd = 1; */

2619

}

2620

continue;

2621

}

2622

if (t1->to != to)

2623

continue;

2624

if (xmlFACompareAtoms(t1->atom, atom, deep)) {

2625

ret = 0;

2626

/* mark the transition as non-deterministic */

2627

t1->nd = 1;

2628

}

2629

}

2630

return(ret);

2631

}

2632

2633

/**

2634

* xmlFAComputesDeterminism:

2635

* @ctxt: a regexp parser context

2636

*

2637

* Check whether the associated regexp is determinist,

2638

* should be called after xmlFAEliminateEpsilonTransitions()

2639

*

2640

*/

2641

static int

2642

xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) {

2643

int statenr, transnr;

2644

xmlRegStatePtr state;

2645

xmlRegTransPtr t1, t2, last;

2646

int i;

2647

int ret = 1;

2648

int deep = 1;

2649

2650

#ifdef DEBUG_REGEXP_GRAPH

2651

printf("xmlFAComputesDeterminism\n");

2652

xmlRegPrintCtxt(stdout, ctxt);

2653

#endif

2654

if (ctxt->determinist != -1)

2655

return(ctxt->determinist);

2656

2657

if (ctxt->flags & AM_AUTOMATA_RNG)

2658

deep = 0;

2659

2660

/*

2661

* First cleanup the automata removing cancelled transitions

2662

*/

2663

for (statenr = 0;statenr < ctxt->nbStates;statenr++) {

2664

state = ctxt->states[statenr];

2665

if (state == NULL)

2666

continue;

2667

if (state->nbTrans < 2)

2668

continue;

2669

for (transnr = 0;transnr < state->nbTrans;transnr++) {

2670

t1 = &(state->trans[transnr]);

2671

/*

2672

* Determinism checks in case of counted or all transitions

2673

* will have to be handled separately

2674

*/

2675

if (t1->atom == NULL) {

2676

/* t1->nd = 1; */

2677

continue;

2678

}

2679

if (t1->to == -1) /* eliminated */

2680

continue;

2681

for (i = 0;i < transnr;i++) {

2682

t2 = &(state->trans[i]);

2683

if (t2->to == -1) /* eliminated */

2684

continue;

2685

if (t2->atom != NULL) {

2686

if (t1->to == t2->to) {

2687

/*

2688

* Here we use deep because we want to keep the

2689

* transitions which indicate a conflict

2690

*/

2691

if (xmlFAEqualAtoms(t1->atom, t2->atom, deep) &&

2692

(t1->counter == t2->counter) &&

2693

(t1->count == t2->count))

2694

t2->to = -1; /* eliminated */

2695

}

2696

}

2697

}

2698

}

2699

}

2700

2701

/*

2702

* Check for all states that there aren't 2 transitions

2703

* with the same atom and a different target.

2704

*/

2705

for (statenr = 0;statenr < ctxt->nbStates;statenr++) {

2706

state = ctxt->states[statenr];

2707

if (state == NULL)

2708

continue;

2709

if (state->nbTrans < 2)

2710

continue;

2711

last = NULL;

2712

for (transnr = 0;transnr < state->nbTrans;transnr++) {

2713

t1 = &(state->trans[transnr]);

2714

/*

2715

* Determinism checks in case of counted or all transitions

2716

* will have to be handled separately

2717

*/

2718

if (t1->atom == NULL) {

2719

continue;

2720

}

2721

if (t1->to == -1) /* eliminated */

2722

continue;

2723

for (i = 0;i < transnr;i++) {

2724

t2 = &(state->trans[i]);

2725

if (t2->to == -1) /* eliminated */

2726

continue;

2727

if (t2->atom != NULL) {

2728

/*

2729

* But here we don't use deep because we want to

2730

* find transitions which indicate a conflict

2731

*/

2732

if (xmlFACompareAtoms(t1->atom, t2->atom, 1)) {

2733

ret = 0;

2734

/* mark the transitions as non-deterministic ones */

2735

t1->nd = 1;

2736

t2->nd = 1;

2737

last = t1;

2738

}

2739

} else if (t1->to != -1) {

2740

/*

2741

* do the closure in case of remaining specific

2742

* epsilon transitions like choices or all

2743

*/

2744

ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],

2745

t2->to, t2->atom);

2746

/* don't shortcut the computation so all non deterministic

2747

transition get marked down

2748

if (ret == 0)

2749

return(0);

2750

*/

2751

if (ret == 0) {

2752

t1->nd = 1;

2753

/* t2->nd = 1; */

2754

last = t1;

2755

}

2756

}

2757

}

2758

/* don't shortcut the computation so all non deterministic

2759

transition get marked down

2760

if (ret == 0)

2761

break; */

2762

}

2763

2764

/*

2765

* mark specifically the last non-deterministic transition

2766

* from a state since there is no need to set-up rollback

2767

* from it

2768

*/

2769

if (last != NULL) {

2770

last->nd = 2;

2771

}

2772

2773

/* don't shortcut the computation so all non deterministic

2774

transition get marked down

2775

if (ret == 0)

2776

break; */

2777

}

2778

2779

ctxt->determinist = ret;

2780

return(ret);

2781

}

2782

2783

/************************************************************************

2784

* *

2785

* Routines to check input against transition atoms *

2786

* *

2787

************************************************************************/

2788

2789

static int

2790

xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg,

2791

int start, int end, const xmlChar *blockName) {

2792

int ret = 0;

2793

2794

switch (type) {

2795

case XML_REGEXP_STRING:

2796

case XML_REGEXP_SUBREG:

2797

case XML_REGEXP_RANGES:

2798

case XML_REGEXP_EPSILON:

2799

return(-1);

2800

case XML_REGEXP_ANYCHAR:

2801

ret = ((codepoint != '\n') && (codepoint != '\r'));

2802

break;

2803

case XML_REGEXP_CHARVAL:

2804

ret = ((codepoint >= start) && (codepoint <= end));

2805

break;

2806

case XML_REGEXP_NOTSPACE:

2807

neg = !neg;

2808

case XML_REGEXP_ANYSPACE:

2809

ret = ((codepoint == '\n') || (codepoint == '\r') ||

2810

(codepoint == '\t') || (codepoint == ' '));

2811

break;

2812

case XML_REGEXP_NOTINITNAME:

2813

neg = !neg;

2814

case XML_REGEXP_INITNAME:

2815

ret = (IS_LETTER(codepoint) ||

2816

(codepoint == '_') || (codepoint == ':'));

2817

break;

2818

case XML_REGEXP_NOTNAMECHAR:

2819

neg = !neg;

2820

case XML_REGEXP_NAMECHAR:

2821

ret = (IS_LETTER(codepoint) || IS_DIGIT(codepoint) ||

2822

(codepoint == '.') || (codepoint == '-') ||

2823

(codepoint == '_') || (codepoint == ':') ||

2824

IS_COMBINING(codepoint) || IS_EXTENDER(codepoint));

2825

break;

2826

case XML_REGEXP_NOTDECIMAL:

2827

neg = !neg;

2828

case XML_REGEXP_DECIMAL:

2829

ret = xmlUCSIsCatNd(codepoint);

2830

break;

2831

case XML_REGEXP_REALCHAR:

2832

neg = !neg;

2833

case XML_REGEXP_NOTREALCHAR:

2834

ret = xmlUCSIsCatP(codepoint);

2835

if (ret == 0)

2836

ret = xmlUCSIsCatZ(codepoint);

2837

if (ret == 0)

2838

ret = xmlUCSIsCatC(codepoint);

2839

break;

2840

case XML_REGEXP_LETTER:

2841

ret = xmlUCSIsCatL(codepoint);

2842

break;

2843

case XML_REGEXP_LETTER_UPPERCASE:

2844

ret = xmlUCSIsCatLu(codepoint);

2845

break;

2846

case XML_REGEXP_LETTER_LOWERCASE:

2847

ret = xmlUCSIsCatLl(codepoint);

2848

break;

2849

case XML_REGEXP_LETTER_TITLECASE:

2850

ret = xmlUCSIsCatLt(codepoint);

2851

break;

2852

case XML_REGEXP_LETTER_MODIFIER:

2853

ret = xmlUCSIsCatLm(codepoint);

2854

break;

2855

case XML_REGEXP_LETTER_OTHERS:

2856

ret = xmlUCSIsCatLo(codepoint);

2857

break;

2858

case XML_REGEXP_MARK:

2859

ret = xmlUCSIsCatM(codepoint);

2860

break;

2861

case XML_REGEXP_MARK_NONSPACING:

2862

ret = xmlUCSIsCatMn(codepoint);

2863

break;

2864

case XML_REGEXP_MARK_SPACECOMBINING:

2865

ret = xmlUCSIsCatMc(codepoint);

2866

break;

2867

case XML_REGEXP_MARK_ENCLOSING:

2868

ret = xmlUCSIsCatMe(codepoint);

2869

break;

2870

case XML_REGEXP_NUMBER:

2871

ret = xmlUCSIsCatN(codepoint);

2872

break;

2873

case XML_REGEXP_NUMBER_DECIMAL:

2874

ret = xmlUCSIsCatNd(codepoint);

2875

break;

2876

case XML_REGEXP_NUMBER_LETTER:

2877

ret = xmlUCSIsCatNl(codepoint);

2878

break;

2879

case XML_REGEXP_NUMBER_OTHERS:

2880

ret = xmlUCSIsCatNo(codepoint);

2881

break;

2882

case XML_REGEXP_PUNCT:

2883

ret = xmlUCSIsCatP(codepoint);

2884

break;

2885

case XML_REGEXP_PUNCT_CONNECTOR:

2886

ret = xmlUCSIsCatPc(codepoint);

2887

break;

2888

case XML_REGEXP_PUNCT_DASH:

2889

ret = xmlUCSIsCatPd(codepoint);

2890

break;

2891

case XML_REGEXP_PUNCT_OPEN:

2892

ret = xmlUCSIsCatPs(codepoint);

2893

break;

2894

case XML_REGEXP_PUNCT_CLOSE:

2895

ret = xmlUCSIsCatPe(codepoint);

2896

break;

2897

case XML_REGEXP_PUNCT_INITQUOTE:

2898

ret = xmlUCSIsCatPi(codepoint);

2899

break;

2900

case XML_REGEXP_PUNCT_FINQUOTE:

2901

ret = xmlUCSIsCatPf(codepoint);

2902

break;

2903

case XML_REGEXP_PUNCT_OTHERS:

2904

ret = xmlUCSIsCatPo(codepoint);

2905

break;

2906

case XML_REGEXP_SEPAR:

2907

ret = xmlUCSIsCatZ(codepoint);

2908

break;

2909

case XML_REGEXP_SEPAR_SPACE:

2910

ret = xmlUCSIsCatZs(codepoint);

2911

break;

2912

case XML_REGEXP_SEPAR_LINE:

2913

ret = xmlUCSIsCatZl(codepoint);

2914

break;

2915

case XML_REGEXP_SEPAR_PARA:

2916

ret = xmlUCSIsCatZp(codepoint);

2917

break;

2918

case XML_REGEXP_SYMBOL:

2919

ret = xmlUCSIsCatS(codepoint);

2920

break;

2921

case XML_REGEXP_SYMBOL_MATH:

2922

ret = xmlUCSIsCatSm(codepoint);

2923

break;

2924

case XML_REGEXP_SYMBOL_CURRENCY:

2925

ret = xmlUCSIsCatSc(codepoint);

2926

break;

2927

case XML_REGEXP_SYMBOL_MODIFIER:

2928

ret = xmlUCSIsCatSk(codepoint);

2929

break;

2930

case XML_REGEXP_SYMBOL_OTHERS:

2931

ret = xmlUCSIsCatSo(codepoint);

2932

break;

2933

case XML_REGEXP_OTHER:

2934

ret = xmlUCSIsCatC(codepoint);

2935

break;

2936

case XML_REGEXP_OTHER_CONTROL:

2937

ret = xmlUCSIsCatCc(codepoint);

2938

break;

2939

case XML_REGEXP_OTHER_FORMAT:

2940

ret = xmlUCSIsCatCf(codepoint);

2941

break;

2942

case XML_REGEXP_OTHER_PRIVATE:

2943

ret = xmlUCSIsCatCo(codepoint);

2944

break;

2945

case XML_REGEXP_OTHER_NA:

2946

/* ret = xmlUCSIsCatCn(codepoint); */

2947

/* Seems it doesn't exist anymore in recent Unicode releases */

2948

ret = 0;

2949

break;

2950

case XML_REGEXP_BLOCK_NAME:

2951

ret = xmlUCSIsBlock(codepoint, (const char *) blockName);

2952

break;

2953

}

2954

if (neg)

2955

return(!ret);

2956

return(ret);

2957

}

2958

2959

static int

2960

xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) {

2961

int i, ret = 0;

2962

xmlRegRangePtr range;

2963

2964

if ((atom == NULL) || (!IS_CHAR(codepoint)))

2965

return(-1);

2966

2967

switch (atom->type) {

2968

case XML_REGEXP_SUBREG:

2969

case XML_REGEXP_EPSILON:

2970

return(-1);

2971

case XML_REGEXP_CHARVAL:

2972

return(codepoint == atom->codepoint);

2973

case XML_REGEXP_RANGES: {

2974

int accept = 0;

2975

2976

for (i = 0;i < atom->nbRanges;i++) {

2977

range = atom->ranges[i];

2978

if (range->neg == 2) {

2979

ret = xmlRegCheckCharacterRange(range->type, codepoint,

2980

0, range->start, range->end,

2981

range->blockName);

2982

if (ret != 0)

2983

return(0); /* excluded char */

2984

} else if (range->neg) {

2985

ret = xmlRegCheckCharacterRange(range->type, codepoint,

2986

0, range->start, range->end,

2987

range->blockName);

2988

if (ret == 0)

2989

accept = 1;

2990

else

2991

return(0);

2992

} else {

2993

ret = xmlRegCheckCharacterRange(range->type, codepoint,

2994

0, range->start, range->end,

2995

range->blockName);

2996

if (ret != 0)

2997

accept = 1; /* might still be excluded */

2998

}

2999

}

3000

return(accept);

3001

}

3002

case XML_REGEXP_STRING:

3003

printf("TODO: XML_REGEXP_STRING\n");

3004

return(-1);

3005

case XML_REGEXP_ANYCHAR:

3006

case XML_REGEXP_ANYSPACE:

3007

case XML_REGEXP_NOTSPACE:

3008

case XML_REGEXP_INITNAME:

3009

case XML_REGEXP_NOTINITNAME:

3010

case XML_REGEXP_NAMECHAR:

3011

case XML_REGEXP_NOTNAMECHAR:

3012

case XML_REGEXP_DECIMAL:

3013

case XML_REGEXP_NOTDECIMAL:

3014

case XML_REGEXP_REALCHAR:

3015

case XML_REGEXP_NOTREALCHAR:

3016

case XML_REGEXP_LETTER:

3017

case XML_REGEXP_LETTER_UPPERCASE:

3018

case XML_REGEXP_LETTER_LOWERCASE:

3019

case XML_REGEXP_LETTER_TITLECASE:

3020

case XML_REGEXP_LETTER_MODIFIER:

3021

case XML_REGEXP_LETTER_OTHERS:

3022

case XML_REGEXP_MARK:

3023

case XML_REGEXP_MARK_NONSPACING:

3024

case XML_REGEXP_MARK_SPACECOMBINING:

3025

case XML_REGEXP_MARK_ENCLOSING:

3026

case XML_REGEXP_NUMBER:

3027

case XML_REGEXP_NUMBER_DECIMAL:

3028

case XML_REGEXP_NUMBER_LETTER:

3029

case XML_REGEXP_NUMBER_OTHERS:

3030

case XML_REGEXP_PUNCT:

3031

case XML_REGEXP_PUNCT_CONNECTOR:

3032

case XML_REGEXP_PUNCT_DASH:

3033

case XML_REGEXP_PUNCT_OPEN:

3034

case XML_REGEXP_PUNCT_CLOSE:

3035

case XML_REGEXP_PUNCT_INITQUOTE:

3036

case XML_REGEXP_PUNCT_FINQUOTE:

3037

case XML_REGEXP_PUNCT_OTHERS:

3038

case XML_REGEXP_SEPAR:

3039

case XML_REGEXP_SEPAR_SPACE:

3040

case XML_REGEXP_SEPAR_LINE:

3041

case XML_REGEXP_SEPAR_PARA:

3042

case XML_REGEXP_SYMBOL:

3043

case XML_REGEXP_SYMBOL_MATH:

3044

case XML_REGEXP_SYMBOL_CURRENCY:

3045

case XML_REGEXP_SYMBOL_MODIFIER:

3046

case XML_REGEXP_SYMBOL_OTHERS:

3047

case XML_REGEXP_OTHER:

3048

case XML_REGEXP_OTHER_CONTROL:

3049

case XML_REGEXP_OTHER_FORMAT:

3050

case XML_REGEXP_OTHER_PRIVATE:

3051

case XML_REGEXP_OTHER_NA:

3052

case XML_REGEXP_BLOCK_NAME:

3053

ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0,

3054

(const xmlChar *)atom->valuep);

3055

if (atom->neg)

3056

ret = !ret;

3057

break;

3058

}

3059

return(ret);

3060

}

3061

3062

/************************************************************************

3063

* *

3064

* Saving and restoring state of an execution context *

3065

* *

3066

************************************************************************/

3067

3068

#ifdef DEBUG_REGEXP_EXEC

3069

static void

3070

xmlFARegDebugExec(xmlRegExecCtxtPtr exec) {

3071

printf("state: %d:%d:idx %d", exec->state->no, exec->transno, exec->index);

3072

if (exec->inputStack != NULL) {

3073

int i;

3074

printf(": ");

3075

for (i = 0;(i < 3) && (i < exec->inputStackNr);i++)

3076

printf("%s ", (const char *)

3077

exec->inputStack[exec->inputStackNr - (i + 1)].value);

3078

} else {

3079

printf(": %s", &(exec->inputString[exec->index]));

3080

}

3081

printf("\n");

3082

}

3083

#endif

3084

3085

static void

3086

xmlFARegExecSave(xmlRegExecCtxtPtr exec) {

3087

#ifdef DEBUG_REGEXP_EXEC

3088

printf("saving ");

3089

exec->transno++;

3090

xmlFARegDebugExec(exec);

3091

exec->transno--;

3092

#endif

3093

#ifdef MAX_PUSH

3094

if (exec->nbPush > MAX_PUSH) {

3095

return;

3096

}

3097

exec->nbPush++;

3098

#endif

3099

3100

if (exec->maxRollbacks == 0) {

3101

exec->maxRollbacks = 4;

3102

exec->rollbacks = (xmlRegExecRollback *) xmlMalloc(exec->maxRollbacks *

3103

sizeof(xmlRegExecRollback));

3104

if (exec->rollbacks == NULL) {

3105

xmlRegexpErrMemory(NULL, "saving regexp");

3106

exec->maxRollbacks = 0;

3107

return;

3108

}

3109

memset(exec->rollbacks, 0,

3110

exec->maxRollbacks * sizeof(xmlRegExecRollback));

3111

} else if (exec->nbRollbacks >= exec->maxRollbacks) {

3112

xmlRegExecRollback *tmp;

3113

int len = exec->maxRollbacks;

3114

3115

exec->maxRollbacks *= 2;

3116

tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks,

3117

exec->maxRollbacks * sizeof(xmlRegExecRollback));

3118

if (tmp == NULL) {

3119

xmlRegexpErrMemory(NULL, "saving regexp");

3120

exec->maxRollbacks /= 2;

3121

return;

3122

}

3123

exec->rollbacks = tmp;

3124

tmp = &exec->rollbacks[len];

3125

memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback));

3126

}

3127

exec->rollbacks[exec->nbRollbacks].state = exec->state;

3128

exec->rollbacks[exec->nbRollbacks].index = exec->index;

3129

exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1;

3130

if (exec->comp->nbCounters > 0) {

3131

if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {

3132

exec->rollbacks[exec->nbRollbacks].counts = (int *)

3133

xmlMalloc(exec->comp->nbCounters * sizeof(int));

3134

if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {

3135

xmlRegexpErrMemory(NULL, "saving regexp");

3136

exec->status = -5;

3137

return;

3138

}

3139

}

3140

memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts,

3141

exec->comp->nbCounters * sizeof(int));

3142

}

3143

exec->nbRollbacks++;

3144

}

3145

3146

static void

3147

xmlFARegExecRollBack(xmlRegExecCtxtPtr exec) {

3148

if (exec->nbRollbacks <= 0) {

3149

exec->status = -1;

3150

#ifdef DEBUG_REGEXP_EXEC

3151

printf("rollback failed on empty stack\n");

3152

#endif

3153

return;

3154

}

3155

exec->nbRollbacks--;

3156

exec->state = exec->rollbacks[exec->nbRollbacks].state;

3157

exec->index = exec->rollbacks[exec->nbRollbacks].index;

3158

exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch;

3159

if (exec->comp->nbCounters > 0) {

3160

if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {

3161

fprintf(stderr, "exec save: allocation failed");

3162

exec->status = -6;

3163

return;

3164

}

3165

memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts,

3166

exec->comp->nbCounters * sizeof(int));

3167

}

3168

3169

#ifdef DEBUG_REGEXP_EXEC

3170

printf("restored ");

3171

xmlFARegDebugExec(exec);

3172

#endif

3173

}

3174

3175

/************************************************************************

3176

* *

3177

* Verifier, running an input against a compiled regexp *

3178

* *

3179

************************************************************************/

3180

3181

static int

3182

xmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) {

3183

xmlRegExecCtxt execval;

3184

xmlRegExecCtxtPtr exec = &execval;

3185

int ret, codepoint = 0, len, deter;

3186

3187

exec->inputString = content;

3188

exec->index = 0;

3189

exec->nbPush = 0;

3190

exec->determinist = 1;

3191

exec->maxRollbacks = 0;

3192

exec->nbRollbacks = 0;

3193

exec->rollbacks = NULL;

3194

exec->status = 0;

3195

exec->comp = comp;

3196

exec->state = comp->states[0];

3197

exec->transno = 0;

3198

exec->transcount = 0;

3199

exec->inputStack = NULL;

3200

exec->inputStackMax = 0;

3201

if (comp->nbCounters > 0) {

3202

exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int));

3203

if (exec->counts == NULL) {

3204

xmlRegexpErrMemory(NULL, "running regexp");

3205

return(-1);

3206

}

3207

memset(exec->counts, 0, comp->nbCounters * sizeof(int));

3208

} else

3209

exec->counts = NULL;

3210

while ((exec->status == 0) && (exec->state != NULL) &&

3211

((exec->inputString[exec->index] != 0) ||

3212

((exec->state != NULL) &&

3213

(exec->state->type != XML_REGEXP_FINAL_STATE)))) {

3214

xmlRegTransPtr trans;

3215

xmlRegAtomPtr atom;

3216

3217

/*

3218

* If end of input on non-terminal state, rollback, however we may

3219

* still have epsilon like transition for counted transitions

3220

* on counters, in that case don't break too early. Additionally,

3221

* if we are working on a range like "AB{0,2}", where B is not present,

3222

* we don't want to break.

3223

*/

3224

len = 1;

3225

if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL)) {

3226

/*

3227

* if there is a transition, we must check if

3228

* atom allows minOccurs of 0

3229

*/

3230

if (exec->transno < exec->state->nbTrans) {

3231

trans = &exec->state->trans[exec->transno];

3232

if (trans->to >=0) {

3233

atom = trans->atom;

3234

if (!((atom->min == 0) && (atom->max > 0)))

3235

goto rollback;

3236

}

3237

} else

3238

goto rollback;

3239

}

3240

3241

exec->transcount = 0;

3242

for (;exec->transno < exec->state->nbTrans;exec->transno++) {

3243

trans = &exec->state->trans[exec->transno];

3244

if (trans->to < 0)

3245

continue;

3246

atom = trans->atom;

3247

ret = 0;

3248

deter = 1;

3249

if (trans->count >= 0) {

3250

int count;

3251

xmlRegCounterPtr counter;

3252

3253

if (exec->counts == NULL) {

3254

exec->status = -1;

3255

goto error;

3256

}

3257

/*

3258

* A counted transition.

3259

*/

3260

3261

count = exec->counts[trans->count];

3262

counter = &exec->comp->counters[trans->count];

3263

#ifdef DEBUG_REGEXP_EXEC

3264

printf("testing count %d: val %d, min %d, max %d\n",

3265

trans->count, count, counter->min, counter->max);

3266

#endif

3267

ret = ((count >= counter->min) && (count <= counter->max));

3268

if ((ret) && (counter->min != counter->max))

3269

deter = 0;

3270

} else if (atom == NULL) {

3271

fprintf(stderr, "epsilon transition left at runtime\n");

3272

exec->status = -2;

3273

break;

3274

} else if (exec->inputString[exec->index] != 0) {

3275

codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);

3276

ret = xmlRegCheckCharacter(atom, codepoint);

3277

if ((ret == 1) && (atom->min >= 0) && (atom->max > 0)) {

3278

xmlRegStatePtr to = comp->states[trans->to];

3279

3280

/*

3281

* this is a multiple input sequence

3282

* If there is a counter associated increment it now.

3283

* before potentially saving and rollback

3284

* do not increment if the counter is already over the

3285

* maximum limit in which case get to next transition

3286

*/

3287

if (trans->counter >= 0) {

3288

xmlRegCounterPtr counter;

3289

3290

if ((exec->counts == NULL) ||

3291

(exec->comp == NULL) ||

3292

(exec->comp->counters == NULL)) {

3293

exec->status = -1;

3294

goto error;

3295

}

3296

counter = &exec->comp->counters[trans->counter];

3297

if (exec->counts[trans->counter] >= counter->max)

3298

continue; /* for loop on transitions */

3299

3300

#ifdef DEBUG_REGEXP_EXEC

3301

printf("Increasing count %d\n", trans->counter);

3302

#endif

3303

exec->counts[trans->counter]++;

3304

}

3305

if (exec->state->nbTrans > exec->transno + 1) {

3306

xmlFARegExecSave(exec);

3307

}

3308

exec->transcount = 1;

3309

do {

3310

/*

3311

* Try to progress as much as possible on the input

3312

*/

3313

if (exec->transcount == atom->max) {

3314

break;

3315

}

3316

exec->index += len;

3317

/*

3318

* End of input: stop here

3319

*/

3320

if (exec->inputString[exec->index] == 0) {

3321

exec->index -= len;

3322

break;

3323

}

3324

if (exec->transcount >= atom->min) {

3325

int transno = exec->transno;

3326

xmlRegStatePtr state = exec->state;

3327

3328

/*

3329

* The transition is acceptable save it

3330

*/

3331

exec->transno = -1; /* trick */

3332

exec->state = to;

3333

xmlFARegExecSave(exec);

3334

exec->transno = transno;

3335

exec->state = state;

3336

}

3337

codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),

3338

len);

3339

ret = xmlRegCheckCharacter(atom, codepoint);

3340

exec->transcount++;

3341

} while (ret == 1);

3342

if (exec->transcount < atom->min)

3343

ret = 0;

3344

3345

/*

3346

* If the last check failed but one transition was found

3347

* possible, rollback

3348

*/

3349

if (ret < 0)

3350

ret = 0;

3351

if (ret == 0) {

3352

goto rollback;

3353

}

3354

if (trans->counter >= 0) {

3355

if (exec->counts == NULL) {

3356

exec->status = -1;

3357

goto error;

3358

}

3359

#ifdef DEBUG_REGEXP_EXEC

3360

printf("Decreasing count %d\n", trans->counter);

3361

#endif

3362

exec->counts[trans->counter]--;

3363

}

3364

} else if ((ret == 0) && (atom->min == 0) && (atom->max > 0)) {

3365

/*

3366

* we don't match on the codepoint, but minOccurs of 0

3367

* says that's ok. Setting len to 0 inhibits stepping

3368

* over the codepoint.

3369

*/

3370

exec->transcount = 1;

3371

len = 0;

3372

ret = 1;

3373

}

3374

} else if ((atom->min == 0) && (atom->max > 0)) {

3375

/* another spot to match when minOccurs is 0 */

3376

exec->transcount = 1;

3377

len = 0;

3378

ret = 1;

3379

}

3380

if (ret == 1) {

3381

if ((trans->nd == 1) ||

3382

((trans->count >= 0) && (deter == 0) &&

3383

(exec->state->nbTrans > exec->transno + 1))) {

3384

#ifdef DEBUG_REGEXP_EXEC

3385

if (trans->nd == 1)

3386

printf("Saving on nd transition atom %d for %c at %d\n",

3387

trans->atom->no, codepoint, exec->index);

3388

else

3389

printf("Saving on counted transition count %d for %c at %d\n",

3390

trans->count, codepoint, exec->index);

3391

#endif

3392

xmlFARegExecSave(exec);

3393

}

3394

if (trans->counter >= 0) {

3395

xmlRegCounterPtr counter;

3396

3397

/* make sure we don't go over the counter maximum value */

3398

if ((exec->counts == NULL) ||

3399

(exec->comp == NULL) ||

3400

(exec->comp->counters == NULL)) {

3401

exec->status = -1;

3402

goto error;

3403

}

3404

counter = &exec->comp->counters[trans->counter];

3405

if (exec->counts[trans->counter] >= counter->max)

3406

continue; /* for loop on transitions */

3407

#ifdef DEBUG_REGEXP_EXEC

3408

printf("Increasing count %d\n", trans->counter);

3409

#endif

3410

exec->counts[trans->counter]++;

3411

}

3412

if ((trans->count >= 0) &&

3413

(trans->count < REGEXP_ALL_COUNTER)) {

3414

if (exec->counts == NULL) {

3415

exec->status = -1;

3416

goto error;

3417

}

3418

#ifdef DEBUG_REGEXP_EXEC

3419

printf("resetting count %d on transition\n",

3420

trans->count);

3421

#endif

3422

exec->counts[trans->count] = 0;

3423

}

3424

#ifdef DEBUG_REGEXP_EXEC

3425

printf("entering state %d\n", trans->to);

3426

#endif

3427

exec->state = comp->states[trans->to];

3428

exec->transno = 0;

3429

if (trans->atom != NULL) {

3430

exec->index += len;

3431

}

3432

goto progress;

3433

} else if (ret < 0) {

3434

exec->status = -4;

3435

break;

3436

}

3437

}

3438

if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {

3439

rollback:

3440

/*

3441

* Failed to find a way out

3442

*/

3443

exec->determinist = 0;

3444

#ifdef DEBUG_REGEXP_EXEC

3445

printf("rollback from state %d on %d:%c\n", exec->state->no,

3446

codepoint,codepoint);

3447

#endif

3448

xmlFARegExecRollBack(exec);

3449

}

3450

progress:

3451

continue;

3452

}

3453

error:

3454

if (exec->rollbacks != NULL) {

3455

if (exec->counts != NULL) {

3456

int i;

3457

3458

for (i = 0;i < exec->maxRollbacks;i++)

3459

if (exec->rollbacks[i].counts != NULL)

3460

xmlFree(exec->rollbacks[i].counts);

3461

}

3462

xmlFree(exec->rollbacks);

3463

}

3464

if (exec->state == NULL)

3465

return(-1);

3466

if (exec->counts != NULL)

3467

xmlFree(exec->counts);

3468

if (exec->status == 0)

3469

return(1);

3470

if (exec->status == -1) {

3471

if (exec->nbPush > MAX_PUSH)

3472

return(-1);

3473

return(0);

3474

}

3475

return(exec->status);

3476

}

3477

3478

/************************************************************************

3479

* *

3480

* Progressive interface to the verifier one atom at a time *

3481

* *

3482

************************************************************************/

3483

#ifdef DEBUG_ERR

3484

static void testerr(xmlRegExecCtxtPtr exec);

3485

#endif

3486

3487

/**

3488

* xmlRegNewExecCtxt:

3489

* @comp: a precompiled regular expression

3490

* @callback: a callback function used for handling progresses in the

3491

* automata matching phase

3492

* @data: the context data associated to the callback in this context

3493

*

3494

* Build a context used for progressive evaluation of a regexp.

3495

*

3496

* Returns the new context

3497

*/

3498

xmlRegExecCtxtPtr

3499

xmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) {

3500

xmlRegExecCtxtPtr exec;

3501

3502

if (comp == NULL)

3503

return(NULL);

3504

if ((comp->compact == NULL) && (comp->states == NULL))

3505

return(NULL);

3506

exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt));

3507

if (exec == NULL) {

3508

xmlRegexpErrMemory(NULL, "creating execution context");

3509

return(NULL);

3510

}

3511

memset(exec, 0, sizeof(xmlRegExecCtxt));

3512

exec->inputString = NULL;

3513

exec->index = 0;

3514

exec->determinist = 1;

3515

exec->maxRollbacks = 0;

3516

exec->nbRollbacks = 0;

3517

exec->rollbacks = NULL;

3518

exec->status = 0;

3519

exec->comp = comp;

3520

if (comp->compact == NULL)

3521

exec->state = comp->states[0];

3522

exec->transno = 0;

3523

exec->transcount = 0;

3524

exec->callback = callback;

3525

exec->data = data;

3526

if (comp->nbCounters > 0) {

3527

/*

3528

* For error handling, exec->counts is allocated twice the size

3529

* the second half is used to store the data in case of rollback

3530

*/

3531

exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int)

3532

* 2);

3533

if (exec->counts == NULL) {

3534

xmlRegexpErrMemory(NULL, "creating execution context");

3535

xmlFree(exec);

3536

return(NULL);

3537

}

3538

memset(exec->counts, 0, comp->nbCounters * sizeof(int) * 2);

3539

exec->errCounts = &exec->counts[comp->nbCounters];

3540

} else {

3541

exec->counts = NULL;

3542

exec->errCounts = NULL;

3543

}

3544

exec->inputStackMax = 0;

3545

exec->inputStackNr = 0;

3546

exec->inputStack = NULL;

3547

exec->errStateNo = -1;

3548

exec->errString = NULL;

3549

exec->nbPush = 0;

3550

return(exec);

3551

}

3552

3553

/**

3554

* xmlRegFreeExecCtxt:

3555

* @exec: a regular expression evaulation context

3556

*

3557

* Free the structures associated to a regular expression evaulation context.

3558

*/

3559

void

3560

xmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) {

3561

if (exec == NULL)

3562

return;

3563

3564

if (exec->rollbacks != NULL) {

3565

if (exec->counts != NULL) {

3566

int i;

3567

3568

for (i = 0;i < exec->maxRollbacks;i++)

3569

if (exec->rollbacks[i].counts != NULL)

3570

xmlFree(exec->rollbacks[i].counts);

3571

}

3572

xmlFree(exec->rollbacks);

3573

}

3574

if (exec->counts != NULL)

3575

xmlFree(exec->counts);

3576

if (exec->inputStack != NULL) {

3577

int i;

3578

3579

for (i = 0;i < exec->inputStackNr;i++) {

3580

if (exec->inputStack[i].value != NULL)

3581

xmlFree(exec->inputStack[i].value);

3582

}

3583

xmlFree(exec->inputStack);

3584

}

3585

if (exec->errString != NULL)

3586

xmlFree(exec->errString);

3587

xmlFree(exec);

3588

}

3589

3590

static void

3591

xmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value,

3592

void *data) {

3593

#ifdef DEBUG_PUSH

3594

printf("saving value: %d:%s\n", exec->inputStackNr, value);

3595

#endif

3596

if (exec->inputStackMax == 0) {

3597

exec->inputStackMax = 4;

3598

exec->inputStack = (xmlRegInputTokenPtr)

3599

xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken));

3600

if (exec->inputStack == NULL) {

3601

xmlRegexpErrMemory(NULL, "pushing input string");

3602

exec->inputStackMax = 0;

3603

return;

3604

}

3605

} else if (exec->inputStackNr + 1 >= exec->inputStackMax) {

3606

xmlRegInputTokenPtr tmp;

3607

3608

exec->inputStackMax *= 2;

3609

tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack,

3610

exec->inputStackMax * sizeof(xmlRegInputToken));

3611

if (tmp == NULL) {

3612

xmlRegexpErrMemory(NULL, "pushing input string");

3613

exec->inputStackMax /= 2;

3614

return;

3615

}

3616

exec->inputStack = tmp;

3617

}

3618

exec->inputStack[exec->inputStackNr].value = xmlStrdup(value);

3619

exec->inputStack[exec->inputStackNr].data = data;

3620

exec->inputStackNr++;

3621

exec->inputStack[exec->inputStackNr].value = NULL;

3622

exec->inputStack[exec->inputStackNr].data = NULL;

3623

}

3624

3625

/**

3626

* xmlRegStrEqualWildcard:

3627

* @expStr: the string to be evaluated

3628

* @valStr: the validation string

3629

*

3630

* Checks if both strings are equal or have the same content. "*"

3631

* can be used as a wildcard in @valStr; "|" is used as a seperator of

3632

* substrings in both @expStr and @valStr.

3633

*

3634

* Returns 1 if the comparison is satisfied and the number of substrings

3635

* is equal, 0 otherwise.

3636

*/

3637

3638

static int

3639

xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr) {

3640

if (expStr == valStr) return(1);

3641

if (expStr == NULL) return(0);

3642

if (valStr == NULL) return(0);

3643

do {

3644

/*

3645

* Eval if we have a wildcard for the current item.

3646

*/

3647

if (*expStr != *valStr) {

3648

/* if one of them starts with a wildcard make valStr be it */

3649

if (*valStr == '*') {

3650

const xmlChar *tmp;

3651

3652

tmp = valStr;

3653

valStr = expStr;

3654

expStr = tmp;

3655

}

3656

if ((*valStr != 0) && (*expStr != 0) && (*expStr++ == '*')) {

3657

do {

3658

if (*valStr == XML_REG_STRING_SEPARATOR)

3659

break;

3660

valStr++;

3661

} while (*valStr != 0);

3662

continue;

3663

} else

3664

return(0);

3665

}

3666

expStr++;

3667

valStr++;

3668

} while (*valStr != 0);

3669

if (*expStr != 0)

3670

return (0);

3671

else

3672

return (1);

3673

}

3674

3675

/**

3676

* xmlRegCompactPushString:

3677

* @exec: a regexp execution context

3678

* @comp: the precompiled exec with a compact table

3679

* @value: a string token input

3680

* @data: data associated to the token to reuse in callbacks

3681

*

3682

* Push one input token in the execution context

3683

*

3684

* Returns: 1 if the regexp reached a final state, 0 if non-final, and

3685

* a negative value in case of error.

3686

*/

3687

static int

3688

xmlRegCompactPushString(xmlRegExecCtxtPtr exec,

3689

xmlRegexpPtr comp,

3690

const xmlChar *value,

3691

void *data) {

3692

int state = exec->index;

3693

int i, target;

3694

3695

if ((comp == NULL) || (comp->compact == NULL) || (comp->stringMap == NULL))

3696

return(-1);

3697

3698

if (value == NULL) {

3699

/*

3700

* are we at a final state ?

3701

*/

3702

if (comp->compact[state * (comp->nbstrings + 1)] ==

3703

XML_REGEXP_FINAL_STATE)

3704

return(1);

3705

return(0);

3706

}

3707

3708

#ifdef DEBUG_PUSH

3709

printf("value pushed: %s\n", value);

3710

#endif

3711

3712

/*

3713

* Examine all outside transitions from current state

3714

*/

3715

for (i = 0;i < comp->nbstrings;i++) {

3716

target = comp->compact[state * (comp->nbstrings + 1) + i + 1];

3717

if ((target > 0) && (target <= comp->nbstates)) {

3718

target--; /* to avoid 0 */

3719

if (xmlRegStrEqualWildcard(comp->stringMap[i], value)) {

3720

exec->index = target;

3721

if ((exec->callback != NULL) && (comp->transdata != NULL)) {

3722

exec->callback(exec->data, value,

3723

comp->transdata[state * comp->nbstrings + i], data);

3724

}

3725

#ifdef DEBUG_PUSH

3726

printf("entering state %d\n", target);

3727

#endif

3728

if (comp->compact[target * (comp->nbstrings + 1)] ==

3729

XML_REGEXP_SINK_STATE)

3730

goto error;

3731

3732

if (comp->compact[target * (comp->nbstrings + 1)] ==

3733

XML_REGEXP_FINAL_STATE)

3734

return(1);

3735

return(0);

3736

}

3737

}

3738

}

3739

/*

3740

* Failed to find an exit transition out from current state for the

3741

* current token

3742

*/

3743

#ifdef DEBUG_PUSH

3744

printf("failed to find a transition for %s on state %d\n", value, state);

3745

#endif

3746

error:

3747

if (exec->errString != NULL)

3748

xmlFree(exec->errString);

3749

exec->errString = xmlStrdup(value);

3750

exec->errStateNo = state;

3751

exec->status = -1;

3752

#ifdef DEBUG_ERR

3753

testerr(exec);

3754

#endif

3755

return(-1);

3756

}

3757

3758

/**

3759

* xmlRegExecPushStringInternal:

3760

* @exec: a regexp execution context or NULL to indicate the end

3761

* @value: a string token input

3762

* @data: data associated to the token to reuse in callbacks

3763

* @compound: value was assembled from 2 strings

3764

*

3765

* Push one input token in the execution context

3766

*

3767

* Returns: 1 if the regexp reached a final state, 0 if non-final, and

3768

* a negative value in case of error.

3769

*/

3770

static int

3771

xmlRegExecPushStringInternal(xmlRegExecCtxtPtr exec, const xmlChar *value,

3772

void *data, int compound) {

3773

xmlRegTransPtr trans;

3774

xmlRegAtomPtr atom;

3775

int ret;

3776

int final = 0;

3777

int progress = 1;

3778

3779

if (exec == NULL)

3780

return(-1);

3781

if (exec->comp == NULL)

3782

return(-1);

3783

if (exec->status != 0)

3784

return(exec->status);

3785

3786

if (exec->comp->compact != NULL)

3787

return(xmlRegCompactPushString(exec, exec->comp, value, data));

3788

3789

if (value == NULL) {

3790

if (exec->state->type == XML_REGEXP_FINAL_STATE)

3791

return(1);

3792

final = 1;

3793

}

3794

3795

#ifdef DEBUG_PUSH

3796

printf("value pushed: %s\n", value);

3797

#endif

3798

/*

3799

* If we have an active rollback stack push the new value there

3800

* and get back to where we were left

3801

*/

3802

if ((value != NULL) && (exec->inputStackNr > 0)) {

3803

xmlFARegExecSaveInputString(exec, value, data);

3804

value = exec->inputStack[exec->index].value;

3805

data = exec->inputStack[exec->index].data;

3806

#ifdef DEBUG_PUSH

3807

printf("value loaded: %s\n", value);

3808

#endif

3809

}

3810

3811

while ((exec->status == 0) &&

3812

((value != NULL) ||

3813

((final == 1) &&

3814

(exec->state->type != XML_REGEXP_FINAL_STATE)))) {

3815

3816

/*

3817

* End of input on non-terminal state, rollback, however we may

3818

* still have epsilon like transition for counted transitions

3819

* on counters, in that case don't break too early.

3820

*/

3821

if ((value == NULL) && (exec->counts == NULL))

3822

goto rollback;

3823

3824

exec->transcount = 0;

3825

for (;exec->transno < exec->state->nbTrans;exec->transno++) {

3826

trans = &exec->state->trans[exec->transno];

3827

if (trans->to < 0)

3828

continue;

3829

atom = trans->atom;

3830

ret = 0;

3831

if (trans->count == REGEXP_ALL_LAX_COUNTER) {

3832

int i;

3833

int count;

3834

xmlRegTransPtr t;

3835

xmlRegCounterPtr counter;

3836

3837

ret = 0;

3838

3839

#ifdef DEBUG_PUSH

3840

printf("testing all lax %d\n", trans->count);

3841

#endif

3842

/*

3843

* Check all counted transitions from the current state

3844

*/

3845

if ((value == NULL) && (final)) {

3846

ret = 1;

3847

} else if (value != NULL) {

3848

for (i = 0;i < exec->state->nbTrans;i++) {

3849

t = &exec->state->trans[i];

3850

if ((t->counter < 0) || (t == trans))

3851

continue;

3852

counter = &exec->comp->counters[t->counter];

3853

count = exec->counts[t->counter];

3854

if ((count < counter->max) &&

3855

(t->atom != NULL) &&

3856

(xmlStrEqual(value, t->atom->valuep))) {

3857

ret = 0;

3858

break;

3859

}

3860

if ((count >= counter->min) &&

3861

(count < counter->max) &&

3862

(t->atom != NULL) &&

3863

(xmlStrEqual(value, t->atom->valuep))) {

3864

ret = 1;

3865

break;

3866

}

3867

}

3868

}

3869

} else if (trans->count == REGEXP_ALL_COUNTER) {

3870

int i;

3871

int count;

3872

xmlRegTransPtr t;

3873

xmlRegCounterPtr counter;

3874

3875

ret = 1;

3876

3877

#ifdef DEBUG_PUSH

3878

printf("testing all %d\n", trans->count);

3879

#endif

3880

/*

3881

* Check all counted transitions from the current state

3882

*/

3883

for (i = 0;i < exec->state->nbTrans;i++) {

3884

t = &exec->state->trans[i];

3885

if ((t->counter < 0) || (t == trans))

3886

continue;

3887

counter = &exec->comp->counters[t->counter];

3888

count = exec->counts[t->counter];

3889

if ((count < counter->min) || (count > counter->max)) {

3890

ret = 0;

3891

break;

3892

}

3893

}

3894

} else if (trans->count >= 0) {

3895

int count;

3896

xmlRegCounterPtr counter;

3897

3898

/*

3899

* A counted transition.

3900

*/

3901

3902

count = exec->counts[trans->count];

3903

counter = &exec->comp->counters[trans->count];

3904

#ifdef DEBUG_PUSH

3905

printf("testing count %d: val %d, min %d, max %d\n",

3906

trans->count, count, counter->min, counter->max);

3907

#endif

3908

ret = ((count >= counter->min) && (count <= counter->max));

3909

} else if (atom == NULL) {

3910

fprintf(stderr, "epsilon transition left at runtime\n");

3911

exec->status = -2;

3912

break;

3913

} else if (value != NULL) {

3914

ret = xmlRegStrEqualWildcard(atom->valuep, value);

3915

if (atom->neg) {

3916

ret = !ret;

3917

if (!compound)

3918

ret = 0;

3919

}

3920

if ((ret == 1) && (trans->counter >= 0)) {

3921

xmlRegCounterPtr counter;

3922

int count;

3923

3924

count = exec->counts[trans->counter];

3925

counter = &exec->comp->counters[trans->counter];

3926

if (count >= counter->max)

3927

ret = 0;

3928

}

3929

3930

if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {

3931

xmlRegStatePtr to = exec->comp->states[trans->to];

3932

3933

/*

3934

* this is a multiple input sequence

3935

*/

3936

if (exec->state->nbTrans > exec->transno + 1) {

3937

if (exec->inputStackNr <= 0) {

3938

xmlFARegExecSaveInputString(exec, value, data);

3939

}

3940

xmlFARegExecSave(exec);

3941

}

3942

exec->transcount = 1;

3943

do {

3944

/*

3945

* Try to progress as much as possible on the input

3946

*/

3947

if (exec->transcount == atom->max) {

3948

break;

3949

}

3950

exec->index++;

3951

value = exec->inputStack[exec->index].value;

3952

data = exec->inputStack[exec->index].data;

3953

#ifdef DEBUG_PUSH

3954

printf("value loaded: %s\n", value);

3955

#endif

3956

3957

/*

3958

* End of input: stop here

3959

*/

3960

if (value == NULL) {

3961

exec->index --;

3962

break;

3963

}

3964

if (exec->transcount >= atom->min) {

3965

int transno = exec->transno;

3966

xmlRegStatePtr state = exec->state;

3967

3968

/*

3969

* The transition is acceptable save it

3970

*/

3971

exec->transno = -1; /* trick */

3972

exec->state = to;

3973

if (exec->inputStackNr <= 0) {

3974

xmlFARegExecSaveInputString(exec, value, data);

3975

}

3976

xmlFARegExecSave(exec);

3977

exec->transno = transno;

3978

exec->state = state;

3979

}

3980

ret = xmlStrEqual(value, atom->valuep);

3981

exec->transcount++;

3982

} while (ret == 1);

3983

if (exec->transcount < atom->min)

3984

ret = 0;

3985

3986

/*

3987

* If the last check failed but one transition was found

3988

* possible, rollback

3989

*/

3990

if (ret < 0)

3991

ret = 0;

3992

if (ret == 0) {

3993

goto rollback;

3994

}

3995

}

3996

}

3997

if (ret == 1) {

3998

if ((exec->callback != NULL) && (atom != NULL) &&

3999

(data != NULL)) {

4000

exec->callback(exec->data, atom->valuep,

4001

atom->data, data);

4002

}

4003

if (exec->state->nbTrans > exec->transno + 1) {

4004

if (exec->inputStackNr <= 0) {

4005

xmlFARegExecSaveInputString(exec, value, data);

4006

}

4007

xmlFARegExecSave(exec);

4008

}

4009

if (trans->counter >= 0) {

4010

#ifdef DEBUG_PUSH

4011

printf("Increasing count %d\n", trans->counter);

4012

#endif

4013

exec->counts[trans->counter]++;

4014

}

4015

if ((trans->count >= 0) &&

4016

(trans->count < REGEXP_ALL_COUNTER)) {

4017

#ifdef DEBUG_REGEXP_EXEC

4018

printf("resetting count %d on transition\n",

4019

trans->count);

4020

#endif

4021

exec->counts[trans->count] = 0;

4022

}

4023

#ifdef DEBUG_PUSH

4024

printf("entering state %d\n", trans->to);

4025

#endif

4026

if ((exec->comp->states[trans->to] != NULL) &&

4027

(exec->comp->states[trans->to]->type ==

4028

XML_REGEXP_SINK_STATE)) {

4029

/*

4030

* entering a sink state, save the current state as error

4031

* state.

4032

*/

4033

if (exec->errString != NULL)

4034

xmlFree(exec->errString);

4035

exec->errString = xmlStrdup(value);

4036

exec->errState = exec->state;

4037

memcpy(exec->errCounts, exec->counts,

4038

exec->comp->nbCounters * sizeof(int));

4039

}

4040

exec->state = exec->comp->states[trans->to];

4041

exec->transno = 0;

4042

if (trans->atom != NULL) {

4043

if (exec->inputStack != NULL) {

4044

exec->index++;

4045

if (exec->index < exec->inputStackNr) {

4046

value = exec->inputStack[exec->index].value;

4047

data = exec->inputStack[exec->index].data;

4048

#ifdef DEBUG_PUSH

4049

printf("value loaded: %s\n", value);

4050

#endif

4051

} else {

4052

value = NULL;

4053

data = NULL;

4054

#ifdef DEBUG_PUSH

4055

printf("end of input\n");

4056

#endif

4057

}

4058

} else {

4059

value = NULL;

4060

data = NULL;

4061

#ifdef DEBUG_PUSH

4062

printf("end of input\n");

4063

#endif

4064

}

4065

}

4066

goto progress;

4067

} else if (ret < 0) {

4068

exec->status = -4;

4069

break;

4070

}

4071

}

4072

if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {

4073

rollback:

4074

/*

4075

* if we didn't yet rollback on the current input

4076

* store the current state as the error state.

4077

*/

4078

if ((progress) && (exec->state != NULL) &&

4079

(exec->state->type != XML_REGEXP_SINK_STATE)) {

4080

progress = 0;

4081

if (exec->errString != NULL)

4082

xmlFree(exec->errString);

4083

exec->errString = xmlStrdup(value);

4084

exec->errState = exec->state;

4085

memcpy(exec->errCounts, exec->counts,

4086

exec->comp->nbCounters * sizeof(int));

4087

}

4088

4089

/*

4090

* Failed to find a way out

4091

*/

4092

exec->determinist = 0;

4093

xmlFARegExecRollBack(exec);

4094

if (exec->status == 0) {

4095

value = exec->inputStack[exec->index].value;

4096

data = exec->inputStack[exec->index].data;

4097

#ifdef DEBUG_PUSH

4098

printf("value loaded: %s\n", value);

4099

#endif

4100

}

4101

}

4102

continue;

4103

progress:

4104

progress = 1;

4105

continue;

4106

}

4107

if (exec->status == 0) {

4108

return(exec->state->type == XML_REGEXP_FINAL_STATE);

4109

}

4110

#ifdef DEBUG_ERR

4111

if (exec->status < 0) {

4112

testerr(exec);

4113

}

4114

#endif

4115

return(exec->status);

4116

}

4117

4118

/**

4119

* xmlRegExecPushString:

4120

* @exec: a regexp execution context or NULL to indicate the end

4121

* @value: a string token input

4122

* @data: data associated to the token to reuse in callbacks

4123

*

4124

* Push one input token in the execution context

4125

*

4126

* Returns: 1 if the regexp reached a final state, 0 if non-final, and

4127

* a negative value in case of error.

4128

*/

4129

int

4130

xmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value,

4131

void *data) {

4132

return(xmlRegExecPushStringInternal(exec, value, data, 0));

4133

}

4134

4135

/**

4136

* xmlRegExecPushString2:

4137

* @exec: a regexp execution context or NULL to indicate the end

4138

* @value: the first string token input

4139

* @value2: the second string token input

4140

* @data: data associated to the token to reuse in callbacks

4141

*

4142

* Push one input token in the execution context

4143

*

4144

* Returns: 1 if the regexp reached a final state, 0 if non-final, and

4145

* a negative value in case of error.

4146

*/

4147

int

4148

xmlRegExecPushString2(xmlRegExecCtxtPtr exec, const xmlChar *value,

4149

const xmlChar *value2, void *data) {

4150

xmlChar buf[150];

4151

int lenn, lenp, ret;

4152

xmlChar *str;

4153

4154

if (exec == NULL)

4155

return(-1);

4156

if (exec->comp == NULL)

4157

return(-1);

4158

if (exec->status != 0)

4159

return(exec->status);

4160

4161

if (value2 == NULL)

4162

return(xmlRegExecPushString(exec, value, data));

4163

4164

lenn = strlen((char *) value2);

4165

lenp = strlen((char *) value);

4166

4167

if (150 < lenn + lenp + 2) {

4168

str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);

4169

if (str == NULL) {

4170

exec->status = -1;

4171

return(-1);

4172

}

4173

} else {

4174

str = buf;

4175

}

4176

memcpy(&str[0], value, lenp);

4177

str[lenp] = XML_REG_STRING_SEPARATOR;

4178

memcpy(&str[lenp + 1], value2, lenn);

4179

str[lenn + lenp + 1] = 0;

4180

4181

if (exec->comp->compact != NULL)

4182

ret = xmlRegCompactPushString(exec, exec->comp, str, data);

4183

else

4184

ret = xmlRegExecPushStringInternal(exec, str, data, 1);

4185

4186

if (str != buf)

4187

xmlFree(str);

4188

return(ret);

4189

}

4190

4191

/**

4192

* xmlRegExecGetValues:

4193

* @exec: a regexp execution context

4194

* @err: error extraction or normal one

4195

* @nbval: pointer to the number of accepted values IN/OUT

4196

* @nbneg: return number of negative transitions

4197

* @values: pointer to the array of acceptable values

4198

* @terminal: return value if this was a terminal state

4199

*

4200

* Extract informations from the regexp execution, internal routine to

4201

* implement xmlRegExecNextValues() and xmlRegExecErrInfo()

4202

*

4203

* Returns: 0 in case of success or -1 in case of error.

4204

*/

4205

static int

4206

xmlRegExecGetValues(xmlRegExecCtxtPtr exec, int err,

4207

int *nbval, int *nbneg,

4208

xmlChar **values, int *terminal) {

4209

int maxval;

4210

int nb = 0;

4211

4212

if ((exec == NULL) || (nbval == NULL) || (nbneg == NULL) ||

4213

(values == NULL) || (*nbval <= 0))

4214

return(-1);

4215

4216

maxval = *nbval;

4217

*nbval = 0;

4218

*nbneg = 0;

4219

if ((exec->comp != NULL) && (exec->comp->compact != NULL)) {

4220

xmlRegexpPtr comp;

4221

int target, i, state;

4222

4223

comp = exec->comp;

4224

4225

if (err) {

4226

if (exec->errStateNo == -1) return(-1);

4227

state = exec->errStateNo;

4228

} else {

4229

state = exec->index;

4230

}

4231

if (terminal != NULL) {

4232

if (comp->compact[state * (comp->nbstrings + 1)] ==

4233

XML_REGEXP_FINAL_STATE)

4234

*terminal = 1;

4235

else

4236

*terminal = 0;

4237

}

4238

for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {

4239

target = comp->compact[state * (comp->nbstrings + 1) + i + 1];

4240

if ((target > 0) && (target <= comp->nbstates) &&

4241

(comp->compact[(target - 1) * (comp->nbstrings + 1)] !=

4242

XML_REGEXP_SINK_STATE)) {

4243

values[nb++] = comp->stringMap[i];

4244

(*nbval)++;

4245

}

4246

}

4247

for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {

4248

target = comp->compact[state * (comp->nbstrings + 1) + i + 1];

4249

if ((target > 0) && (target <= comp->nbstates) &&

4250

(comp->compact[(target - 1) * (comp->nbstrings + 1)] ==

4251

XML_REGEXP_SINK_STATE)) {

4252

values[nb++] = comp->stringMap[i];

4253

(*nbneg)++;

4254

}

4255

}

4256

} else {

4257

int transno;

4258

xmlRegTransPtr trans;

4259

xmlRegAtomPtr atom;

4260

xmlRegStatePtr state;

4261

4262

if (terminal != NULL) {

4263

if (exec->state->type == XML_REGEXP_FINAL_STATE)

4264

*terminal = 1;

4265

else

4266

*terminal = 0;

4267

}

4268

4269

if (err) {

4270

if (exec->errState == NULL) return(-1);

4271

state = exec->errState;

4272

} else {

4273

if (exec->state == NULL) return(-1);

4274

state = exec->state;

4275

}

4276

for (transno = 0;

4277

(transno < state->nbTrans) && (nb < maxval);

4278

transno++) {

4279

trans = &state->trans[transno];

4280

if (trans->to < 0)

4281

continue;

4282

atom = trans->atom;

4283

if ((atom == NULL) || (atom->valuep == NULL))

4284

continue;

4285

if (trans->count == REGEXP_ALL_LAX_COUNTER) {

4286

/* this should not be reached but ... */

4287

TODO;

4288

} else if (trans->count == REGEXP_ALL_COUNTER) {

4289

/* this should not be reached but ... */

4290

TODO;

4291

} else if (trans->counter >= 0) {

4292

xmlRegCounterPtr counter = NULL;

4293

int count;

4294

4295

if (err)

4296

count = exec->errCounts[trans->counter];

4297

else

4298

count = exec->counts[trans->counter];

4299

if (exec->comp != NULL)

4300

counter = &exec->comp->counters[trans->counter];

4301

if ((counter == NULL) || (count < counter->max)) {

4302

if (atom->neg)

4303

values[nb++] = (xmlChar *) atom->valuep2;

4304

else

4305

values[nb++] = (xmlChar *) atom->valuep;

4306

(*nbval)++;

4307

}

4308

} else {

4309

if ((exec->comp->states[trans->to] != NULL) &&

4310

(exec->comp->states[trans->to]->type !=

4311

XML_REGEXP_SINK_STATE)) {

4312

if (atom->neg)

4313

values[nb++] = (xmlChar *) atom->valuep2;

4314

else

4315

values[nb++] = (xmlChar *) atom->valuep;

4316

(*nbval)++;

4317

}

4318

}

4319

}

4320

for (transno = 0;

4321

(transno < state->nbTrans) && (nb < maxval);

4322

transno++) {

4323

trans = &state->trans[transno];

4324

if (trans->to < 0)

4325

continue;

4326

atom = trans->atom;

4327

if ((atom == NULL) || (atom->valuep == NULL))

4328

continue;

4329

if (trans->count == REGEXP_ALL_LAX_COUNTER) {

4330

continue;

4331

} else if (trans->count == REGEXP_ALL_COUNTER) {

4332

continue;

4333

} else if (trans->counter >= 0) {

4334

continue;

4335

} else {

4336

if ((exec->comp->states[trans->to] != NULL) &&

4337

(exec->comp->states[trans->to]->type ==

4338

XML_REGEXP_SINK_STATE)) {

4339

if (atom->neg)

4340

values[nb++] = (xmlChar *) atom->valuep2;

4341

else

4342

values[nb++] = (xmlChar *) atom->valuep;

4343

(*nbneg)++;

4344

}

4345

}

4346

}

4347

}

4348

return(0);

4349

}

4350

4351

/**

4352

* xmlRegExecNextValues:

4353

* @exec: a regexp execution context

4354

* @nbval: pointer to the number of accepted values IN/OUT

4355

* @nbneg: return number of negative transitions

4356

* @values: pointer to the array of acceptable values

4357

* @terminal: return value if this was a terminal state

4358

*

4359

* Extract informations from the regexp execution,

4360

* the parameter @values must point to an array of @nbval string pointers

4361

* on return nbval will contain the number of possible strings in that

4362

* state and the @values array will be updated with them. The string values

4363

* returned will be freed with the @exec context and don't need to be

4364

* deallocated.

4365

*

4366

* Returns: 0 in case of success or -1 in case of error.

4367

*/

4368

int

4369

xmlRegExecNextValues(xmlRegExecCtxtPtr exec, int *nbval, int *nbneg,

4370

xmlChar **values, int *terminal) {

4371

return(xmlRegExecGetValues(exec, 0, nbval, nbneg, values, terminal));

4372

}

4373

4374

/**

4375

* xmlRegExecErrInfo:

4376

* @exec: a regexp execution context generating an error

4377

* @string: return value for the error string

4378

* @nbval: pointer to the number of accepted values IN/OUT

4379

* @nbneg: return number of negative transitions

4380

* @values: pointer to the array of acceptable values

4381

* @terminal: return value if this was a terminal state

4382

*

4383

* Extract error informations from the regexp execution, the parameter

4384

* @string will be updated with the value pushed and not accepted,

4385

* the parameter @values must point to an array of @nbval string pointers

4386

* on return nbval will contain the number of possible strings in that

4387

* state and the @values array will be updated with them. The string values

4388

* returned will be freed with the @exec context and don't need to be

4389

* deallocated.

4390

*

4391

* Returns: 0 in case of success or -1 in case of error.

4392

*/

4393

int

4394

xmlRegExecErrInfo(xmlRegExecCtxtPtr exec, const xmlChar **string,

4395

int *nbval, int *nbneg, xmlChar **values, int *terminal) {

4396

if (exec == NULL)

4397

return(-1);

4398

if (string != NULL) {

4399

if (exec->status != 0)

4400

*string = exec->errString;

4401

else

4402

*string = NULL;

4403

}

4404

return(xmlRegExecGetValues(exec, 1, nbval, nbneg, values, terminal));

4405

}

4406

4407

#ifdef DEBUG_ERR

4408

static void testerr(xmlRegExecCtxtPtr exec) {

4409

const xmlChar *string;

4410

xmlChar *values[5];

4411

int nb = 5;

4412

int nbneg;

4413

int terminal;

4414

xmlRegExecErrInfo(exec, &string, &nb, &nbneg, &values[0], &terminal);

4415

}

4416

#endif

4417

4418

#if 0

4419

static int

4420

xmlRegExecPushChar(xmlRegExecCtxtPtr exec, int UCS) {

4421

xmlRegTransPtr trans;

4422

xmlRegAtomPtr atom;

4423

int ret;

4424

int codepoint, len;

4425

4426

if (exec == NULL)

4427

return(-1);

4428

if (exec->status != 0)

4429

return(exec->status);

4430

4431

while ((exec->status == 0) &&

4432

((exec->inputString[exec->index] != 0) ||

4433

(exec->state->type != XML_REGEXP_FINAL_STATE))) {

4434

4435

/*

4436

* End of input on non-terminal state, rollback, however we may

4437

* still have epsilon like transition for counted transitions

4438

* on counters, in that case don't break too early.

4439

*/

4440

if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL))

4441

goto rollback;

4442

4443

exec->transcount = 0;

4444

for (;exec->transno < exec->state->nbTrans;exec->transno++) {

4445

trans = &exec->state->trans[exec->transno];

4446

if (trans->to < 0)

4447

continue;

4448

atom = trans->atom;

4449

ret = 0;

4450

if (trans->count >= 0) {

4451

int count;

4452

xmlRegCounterPtr counter;

4453

4454

/*

4455

* A counted transition.

4456

*/

4457

4458

count = exec->counts[trans->count];

4459

counter = &exec->comp->counters[trans->count];

4460

#ifdef DEBUG_REGEXP_EXEC

4461

printf("testing count %d: val %d, min %d, max %d\n",

4462

trans->count, count, counter->min, counter->max);

4463

#endif

4464

ret = ((count >= counter->min) && (count <= counter->max));

4465

} else if (atom == NULL) {

4466

fprintf(stderr, "epsilon transition left at runtime\n");

4467

exec->status = -2;

4468

break;

4469

} else if (exec->inputString[exec->index] != 0) {

4470

codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);

4471

ret = xmlRegCheckCharacter(atom, codepoint);

4472

if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {

4473

xmlRegStatePtr to = exec->comp->states[trans->to];

4474

4475

/*

4476

* this is a multiple input sequence

4477

*/

4478

if (exec->state->nbTrans > exec->transno + 1) {

4479

xmlFARegExecSave(exec);

4480

}

4481

exec->transcount = 1;

4482

do {

4483

/*

4484

* Try to progress as much as possible on the input

4485

*/

4486

if (exec->transcount == atom->max) {

4487

break;

4488

}

4489

exec->index += len;

4490

/*

4491

* End of input: stop here

4492

*/

4493

if (exec->inputString[exec->index] == 0) {

4494

exec->index -= len;

4495

break;

4496

}

4497

if (exec->transcount >= atom->min) {

4498

int transno = exec->transno;

4499

xmlRegStatePtr state = exec->state;

4500

4501

/*

4502

* The transition is acceptable save it

4503

*/

4504

exec->transno = -1; /* trick */

4505

exec->state = to;

4506

xmlFARegExecSave(exec);

4507

exec->transno = transno;

4508

exec->state = state;

4509

}

4510

codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),

4511

len);

4512

ret = xmlRegCheckCharacter(atom, codepoint);

4513

exec->transcount++;

4514

} while (ret == 1);

4515

if (exec->transcount < atom->min)

4516

ret = 0;

4517

4518

/*

4519

* If the last check failed but one transition was found

4520

* possible, rollback

4521

*/

4522

if (ret < 0)

4523

ret = 0;

4524

if (ret == 0) {

4525

goto rollback;

4526

}

4527

}

4528

}

4529

if (ret == 1) {

4530

if (exec->state->nbTrans > exec->transno + 1) {

4531

xmlFARegExecSave(exec);

4532

}

4533

/*

4534

* restart count for expressions like this ((abc){2})*

4535

*/

4536

if (trans->count >= 0) {

4537

#ifdef DEBUG_REGEXP_EXEC

4538

printf("Reset count %d\n", trans->count);

4539

#endif

4540

exec->counts[trans->count] = 0;

4541

}

4542

if (trans->counter >= 0) {

4543

#ifdef DEBUG_REGEXP_EXEC

4544

printf("Increasing count %d\n", trans->counter);

4545

#endif

4546

exec->counts[trans->counter]++;

4547

}

4548

#ifdef DEBUG_REGEXP_EXEC

4549

printf("entering state %d\n", trans->to);

4550

#endif

4551

exec->state = exec->comp->states[trans->to];

4552

exec->transno = 0;

4553

if (trans->atom != NULL) {

4554

exec->index += len;

4555

}

4556

goto progress;

4557

} else if (ret < 0) {

4558

exec->status = -4;

4559

break;

4560

}

4561

}

4562

if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {

4563

rollback:

4564

/*

4565

* Failed to find a way out

4566

*/

4567

exec->determinist = 0;

4568

xmlFARegExecRollBack(exec);

4569

}

4570

progress:

4571

continue;

4572

}

4573

}

4574

#endif

4575

/************************************************************************

4576

* *

4577

* Parser for the Schemas Datatype Regular Expressions *

4578

* http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs *

4579

* *

4580

************************************************************************/

4581

4582

/**

4583

* xmlFAIsChar:

4584

* @ctxt: a regexp parser context

4585

*

4586

* [10] Char ::= [^.\?*+()|#x5B#x5D]

4587

*/

4588

static int

4589

xmlFAIsChar(xmlRegParserCtxtPtr ctxt) {

4590

int cur;

4591

int len;

4592

4593

cur = CUR_SCHAR(ctxt->cur, len);

4594

if ((cur == '.') || (cur == '\\') || (cur == '?') ||

4595

(cur == '*') || (cur == '+') || (cur == '(') ||

4596

(cur == ')') || (cur == '|') || (cur == 0x5B) ||

4597

(cur == 0x5D) || (cur == 0))

4598

return(-1);

4599

return(cur);

4600

}

4601

4602

/**

4603

* xmlFAParseCharProp:

4604

* @ctxt: a regexp parser context

4605

*

4606

* [27] charProp ::= IsCategory | IsBlock

4607

* [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |

4608

* Separators | Symbols | Others

4609

* [29] Letters ::= 'L' [ultmo]?

4610

* [30] Marks ::= 'M' [nce]?

4611

* [31] Numbers ::= 'N' [dlo]?

4612

* [32] Punctuation ::= 'P' [cdseifo]?

4613

* [33] Separators ::= 'Z' [slp]?

4614

* [34] Symbols ::= 'S' [mcko]?

4615

* [35] Others ::= 'C' [cfon]?

4616

* [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+

4617

*/

4618

static void

4619

xmlFAParseCharProp(xmlRegParserCtxtPtr ctxt) {

4620

int cur;

4621

xmlRegAtomType type = (xmlRegAtomType) 0;

4622

xmlChar *blockName = NULL;

4623

4624

cur = CUR;

4625

if (cur == 'L') {

4626

NEXT;

4627

cur = CUR;

4628

if (cur == 'u') {

4629

NEXT;

4630

type = XML_REGEXP_LETTER_UPPERCASE;

4631

} else if (cur == 'l') {

4632

NEXT;

4633

type = XML_REGEXP_LETTER_LOWERCASE;

4634

} else if (cur == 't') {

4635

NEXT;

4636

type = XML_REGEXP_LETTER_TITLECASE;

4637

} else if (cur == 'm') {

4638

NEXT;

4639

type = XML_REGEXP_LETTER_MODIFIER;

4640

} else if (cur == 'o') {

4641

NEXT;

4642

type = XML_REGEXP_LETTER_OTHERS;

4643

} else {

4644

type = XML_REGEXP_LETTER;

4645

}

4646

} else if (cur == 'M') {

4647

NEXT;

4648

cur = CUR;

4649

if (cur == 'n') {

4650

NEXT;

4651

/* nonspacing */

4652

type = XML_REGEXP_MARK_NONSPACING;

4653

} else if (cur == 'c') {

4654

NEXT;

4655

/* spacing combining */

4656

type = XML_REGEXP_MARK_SPACECOMBINING;

4657

} else if (cur == 'e') {

4658

NEXT;

4659

/* enclosing */

4660

type = XML_REGEXP_MARK_ENCLOSING;

4661

} else {

4662

/* all marks */

4663

type = XML_REGEXP_MARK;

4664

}

4665

} else if (cur == 'N') {

4666

NEXT;

4667

cur = CUR;

4668

if (cur == 'd') {

4669

NEXT;

4670

/* digital */

4671

type = XML_REGEXP_NUMBER_DECIMAL;

4672

} else if (cur == 'l') {

4673

NEXT;

4674

/* letter */

4675

type = XML_REGEXP_NUMBER_LETTER;

4676

} else if (cur == 'o') {

4677

NEXT;

4678

/* other */

4679

type = XML_REGEXP_NUMBER_OTHERS;

4680

} else {

4681

/* all numbers */

4682

type = XML_REGEXP_NUMBER;

4683

}

4684

} else if (cur == 'P') {

4685

NEXT;

4686

cur = CUR;

4687

if (cur == 'c') {

4688

NEXT;

4689

/* connector */

4690

type = XML_REGEXP_PUNCT_CONNECTOR;

4691

} else if (cur == 'd') {

4692

NEXT;

4693

/* dash */

4694

type = XML_REGEXP_PUNCT_DASH;

4695

} else if (cur == 's') {

4696

NEXT;

4697

/* open */

4698

type = XML_REGEXP_PUNCT_OPEN;

4699

} else if (cur == 'e') {

4700

NEXT;

4701

/* close */

4702

type = XML_REGEXP_PUNCT_CLOSE;

4703

} else if (cur == 'i') {

4704

NEXT;

4705

/* initial quote */

4706

type = XML_REGEXP_PUNCT_INITQUOTE;

4707

} else if (cur == 'f') {

4708

NEXT;

4709

/* final quote */

4710

type = XML_REGEXP_PUNCT_FINQUOTE;

4711

} else if (cur == 'o') {

4712

NEXT;

4713

/* other */

4714

type = XML_REGEXP_PUNCT_OTHERS;

4715

} else {

4716

/* all punctuation */

4717

type = XML_REGEXP_PUNCT;

4718

}

4719

} else if (cur == 'Z') {

4720

NEXT;

4721

cur = CUR;

4722

if (cur == 's') {

4723

NEXT;

4724

/* space */

4725

type = XML_REGEXP_SEPAR_SPACE;

4726

} else if (cur == 'l') {

4727

NEXT;

4728

/* line */

4729

type = XML_REGEXP_SEPAR_LINE;

4730

} else if (cur == 'p') {

4731

NEXT;

4732

/* paragraph */

4733

type = XML_REGEXP_SEPAR_PARA;

4734

} else {

4735

/* all separators */

4736

type = XML_REGEXP_SEPAR;

4737

}

4738

} else if (cur == 'S') {

4739

NEXT;

4740

cur = CUR;

4741

if (cur == 'm') {

4742

NEXT;

4743

type = XML_REGEXP_SYMBOL_MATH;

4744

/* math */

4745

} else if (cur == 'c') {

4746

NEXT;

4747

type = XML_REGEXP_SYMBOL_CURRENCY;

4748

/* currency */

4749

} else if (cur == 'k') {

4750

NEXT;

4751

type = XML_REGEXP_SYMBOL_MODIFIER;

4752

/* modifiers */

4753

} else if (cur == 'o') {

4754

NEXT;

4755

type = XML_REGEXP_SYMBOL_OTHERS;

4756

/* other */

4757

} else {

4758

/* all symbols */

4759

type = XML_REGEXP_SYMBOL;

4760

}

4761

} else if (cur == 'C') {

4762

NEXT;

4763

cur = CUR;

4764

if (cur == 'c') {

4765

NEXT;

4766

/* control */

4767

type = XML_REGEXP_OTHER_CONTROL;

4768

} else if (cur == 'f') {

4769

NEXT;

4770

/* format */

4771

type = XML_REGEXP_OTHER_FORMAT;

4772

} else if (cur == 'o') {

4773

NEXT;

4774

/* private use */

4775

type = XML_REGEXP_OTHER_PRIVATE;

4776

} else if (cur == 'n') {

4777

NEXT;

4778

/* not assigned */

4779

type = XML_REGEXP_OTHER_NA;

4780

} else {

4781

/* all others */

4782

type = XML_REGEXP_OTHER;

4783

}

4784

} else if (cur == 'I') {

4785

const xmlChar *start;

4786

NEXT;

4787

cur = CUR;

4788

if (cur != 's') {

4789

ERROR("IsXXXX expected");

4790

return;

4791

}

4792

NEXT;

4793

start = ctxt->cur;

4794

cur = CUR;

4795

if (((cur >= 'a') && (cur <= 'z')) ||

4796

((cur >= 'A') && (cur <= 'Z')) ||

4797

((cur >= '0') && (cur <= '9')) ||

4798

(cur == 0x2D)) {

4799

NEXT;

4800

cur = CUR;

4801

while (((cur >= 'a') && (cur <= 'z')) ||

4802

((cur >= 'A') && (cur <= 'Z')) ||

4803

((cur >= '0') && (cur <= '9')) ||

4804

(cur == 0x2D)) {

4805

NEXT;

4806

cur = CUR;

4807

}

4808

}

4809

type = XML_REGEXP_BLOCK_NAME;

4810

blockName = xmlStrndup(start, ctxt->cur - start);

4811

} else {

4812

ERROR("Unknown char property");

4813

return;

4814

}

4815

if (ctxt->atom == NULL) {

4816

ctxt->atom = xmlRegNewAtom(ctxt, type);

4817

if (ctxt->atom != NULL)

4818

ctxt->atom->valuep = blockName;

4819

} else if (ctxt->atom->type == XML_REGEXP_RANGES) {

4820

xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,

4821

type, 0, 0, blockName);

4822

}

4823

}

4824

4825

/**

4826

* xmlFAParseCharClassEsc:

4827

* @ctxt: a regexp parser context

4828

*

4829

* [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )

4830

* [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]

4831

* [25] catEsc ::= '\p{' charProp '}'

4832

* [26] complEsc ::= '\P{' charProp '}'

4833

* [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])

4834

*/

4835

static void

4836

xmlFAParseCharClassEsc(xmlRegParserCtxtPtr ctxt) {

4837

int cur;

4838

4839

if (CUR == '.') {

4840

if (ctxt->atom == NULL) {

4841

ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_ANYCHAR);

4842

} else if (ctxt->atom->type == XML_REGEXP_RANGES) {

4843

xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,

4844

XML_REGEXP_ANYCHAR, 0, 0, NULL);

4845

}

4846

NEXT;

4847

return;

4848

}

4849

if (CUR != '\\') {

4850

ERROR("Escaped sequence: expecting \\");

4851

return;

4852

}

4853

NEXT;

4854

cur = CUR;

4855

if (cur == 'p') {

4856

NEXT;

4857

if (CUR != '{') {

4858

ERROR("Expecting '{'");

4859

return;

4860

}

4861

NEXT;

4862

xmlFAParseCharProp(ctxt);

4863

if (CUR != '}') {

4864

ERROR("Expecting '}'");

4865

return;

4866

}

4867

NEXT;

4868

} else if (cur == 'P') {

4869

NEXT;

4870

if (CUR != '{') {

4871

ERROR("Expecting '{'");

4872

return;

4873

}

4874

NEXT;

4875

xmlFAParseCharProp(ctxt);

4876

ctxt->atom->neg = 1;

4877

if (CUR != '}') {

4878

ERROR("Expecting '}'");

4879

return;

4880

}

4881

NEXT;

4882

} else if ((cur == 'n') || (cur == 'r') || (cur == 't') || (cur == '\\') ||

4883

(cur == '|') || (cur == '.') || (cur == '?') || (cur == '*') ||

4884

(cur == '+') || (cur == '(') || (cur == ')') || (cur == '{') ||

4885

(cur == '}') || (cur == 0x2D) || (cur == 0x5B) || (cur == 0x5D) ||

4886

(cur == 0x5E)) {

4887

if (ctxt->atom == NULL) {

4888

ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);

4889

if (ctxt->atom != NULL) {

4890

switch (cur) {

4891

case 'n':

4892

ctxt->atom->codepoint = '\n';

4893

break;

4894

case 'r':

4895

ctxt->atom->codepoint = '\r';

4896

break;

4897

case 't':

4898

ctxt->atom->codepoint = '\t';

4899

break;

4900

default:

4901

ctxt->atom->codepoint = cur;

4902

}

4903

}

4904

} else if (ctxt->atom->type == XML_REGEXP_RANGES) {

4905

switch (cur) {

4906

case 'n':

4907

cur = '\n';

4908

break;

4909

case 'r':

4910

cur = '\r';

4911

break;

4912

case 't':

4913

cur = '\t';

4914

break;

4915

}

4916

xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,

4917

XML_REGEXP_CHARVAL, cur, cur, NULL);

4918

}

4919

NEXT;

4920

} else if ((cur == 's') || (cur == 'S') || (cur == 'i') || (cur == 'I') ||

4921

(cur == 'c') || (cur == 'C') || (cur == 'd') || (cur == 'D') ||

4922

(cur == 'w') || (cur == 'W')) {

4923

xmlRegAtomType type = XML_REGEXP_ANYSPACE;

4924

4925

switch (cur) {

4926

case 's':

4927

type = XML_REGEXP_ANYSPACE;

4928

break;

4929

case 'S':

4930

type = XML_REGEXP_NOTSPACE;

4931

break;

4932

case 'i':

4933

type = XML_REGEXP_INITNAME;

4934

break;

4935

case 'I':

4936

type = XML_REGEXP_NOTINITNAME;

4937

break;

4938

case 'c':

4939

type = XML_REGEXP_NAMECHAR;

4940

break;

4941

case 'C':

4942

type = XML_REGEXP_NOTNAMECHAR;

4943

break;

4944

case 'd':

4945

type = XML_REGEXP_DECIMAL;

4946

break;

4947

case 'D':

4948

type = XML_REGEXP_NOTDECIMAL;

4949

break;

4950

case 'w':

4951

type = XML_REGEXP_REALCHAR;

4952

break;

4953

case 'W':

4954

type = XML_REGEXP_NOTREALCHAR;

4955

break;

4956

}

4957

NEXT;

4958

if (ctxt->atom == NULL) {

4959

ctxt->atom = xmlRegNewAtom(ctxt, type);

4960

} else if (ctxt->atom->type == XML_REGEXP_RANGES) {

4961

xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,

4962

type, 0, 0, NULL);

4963

}

4964

} else {

4965

ERROR("Wrong escape sequence, misuse of character '\\'");

4966

}

4967

}

4968

4969

/**

4970

* xmlFAParseCharRange:

4971

* @ctxt: a regexp parser context

4972

*

4973

* [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash

4974

* [18] seRange ::= charOrEsc '-' charOrEsc

4975

* [20] charOrEsc ::= XmlChar | SingleCharEsc

4976

* [21] XmlChar ::= [^\#x2D#x5B#x5D]

4977

* [22] XmlCharIncDash ::= [^\#x5B#x5D]

4978

*/

4979

static void

4980

xmlFAParseCharRange(xmlRegParserCtxtPtr ctxt) {

4981

int cur, len;

4982

int start = -1;

4983

int end = -1;

4984

4985

if (CUR == '\0') {

4986

ERROR("Expecting ']'");

4987

return;

4988

}

4989

4990

cur = CUR;

4991

if (cur == '\\') {

4992

NEXT;

4993

cur = CUR;

4994

switch (cur) {

4995

case 'n': start = 0xA; break;

4996

case 'r': start = 0xD; break;

4997

case 't': start = 0x9; break;

4998

case '\\': case '|': case '.': case '-': case '^': case '?':

4999

case '*': case '+': case '{': case '}': case '(': case ')':

5000

case '[': case ']':

5001

start = cur; break;

5002

default:

5003

ERROR("Invalid escape value");

5004

return;

5005

}

5006

end = start;

5007

len = 1;

5008

} else if ((cur != 0x5B) && (cur != 0x5D)) {

5009

end = start = CUR_SCHAR(ctxt->cur, len);

5010

} else {

5011

ERROR("Expecting a char range");

5012

return;

5013

}

5014

/*

5015

* Since we are "inside" a range, we can assume ctxt->cur is past

5016

* the start of ctxt->string, and PREV should be safe

5017

*/

5018

if ((start == '-') && (NXT(1) != ']') && (PREV != '[') && (PREV != '^')) {

5019

NEXTL(len);

5020

return;

5021

}

5022

NEXTL(len);

5023

cur = CUR;

5024

if ((cur != '-') || (NXT(1) == ']')) {

5025

xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,

5026

XML_REGEXP_CHARVAL, start, end, NULL);

5027

return;

5028

}

5029

NEXT;

5030

cur = CUR;

5031

if (cur == '\\') {

5032

NEXT;

5033

cur = CUR;

5034

switch (cur) {

5035

case 'n': end = 0xA; break;

5036

case 'r': end = 0xD; break;

5037

case 't': end = 0x9; break;

5038

case '\\': case '|': case '.': case '-': case '^': case '?':

5039

case '*': case '+': case '{': case '}': case '(': case ')':

5040

case '[': case ']':

5041

end = cur; break;

5042

default:

5043

ERROR("Invalid escape value");

5044

return;

5045

}

5046

len = 1;

5047

} else if ((cur != 0x5B) && (cur != 0x5D)) {

5048

end = CUR_SCHAR(ctxt->cur, len);

5049

} else {

5050

ERROR("Expecting the end of a char range");

5051

return;

5052

}

5053

NEXTL(len);

5054

/* TODO check that the values are acceptable character ranges for XML */

5055

if (end < start) {

5056

ERROR("End of range is before start of range");

5057

} else {

5058

xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,

5059

XML_REGEXP_CHARVAL, start, end, NULL);

5060

}

5061

return;

5062

}

5063

5064

/**

5065

* xmlFAParsePosCharGroup:

5066

* @ctxt: a regexp parser context

5067

*

5068

* [14] posCharGroup ::= ( charRange | charClassEsc )+

5069

*/

5070

static void

5071

xmlFAParsePosCharGroup(xmlRegParserCtxtPtr ctxt) {

5072

do {

5073

if (CUR == '\\') {

5074

xmlFAParseCharClassEsc(ctxt);

5075

} else {

5076

xmlFAParseCharRange(ctxt);

5077

}

5078

} while ((CUR != ']') && (CUR != '^') && (CUR != '-') &&

5079

(CUR != 0) && (ctxt->error == 0));

5080

}

5081

5082

/**

5083

* xmlFAParseCharGroup:

5084

* @ctxt: a regexp parser context

5085

*

5086

* [13] charGroup ::= posCharGroup | negCharGroup | charClassSub

5087

* [15] negCharGroup ::= '^' posCharGroup

5088

* [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr

5089

* [12] charClassExpr ::= '[' charGroup ']'

5090

*/

5091

static void

5092

xmlFAParseCharGroup(xmlRegParserCtxtPtr ctxt) {

5093

int n = ctxt->neg;

5094

while ((CUR != ']') && (ctxt->error == 0)) {

5095

if (CUR == '^') {

5096

int neg = ctxt->neg;

5097

5098

NEXT;

5099

ctxt->neg = !ctxt->neg;

5100

xmlFAParsePosCharGroup(ctxt);

5101

ctxt->neg = neg;

5102

} else if ((CUR == '-') && (NXT(1) == '[')) {

5103

int neg = ctxt->neg;

5104

ctxt->neg = 2;

5105

NEXT; /* eat the '-' */

5106

NEXT; /* eat the '[' */

5107

xmlFAParseCharGroup(ctxt);

5108

if (CUR == ']') {

5109

NEXT;

5110

} else {

5111

ERROR("charClassExpr: ']' expected");

5112

break;

5113

}

5114

ctxt->neg = neg;

5115

break;

5116

} else if (CUR != ']') {

5117

xmlFAParsePosCharGroup(ctxt);

5118

}

5119

}

5120

ctxt->neg = n;

5121

}

5122

5123

/**

5124

* xmlFAParseCharClass:

5125

* @ctxt: a regexp parser context

5126

*

5127

* [11] charClass ::= charClassEsc | charClassExpr

5128

* [12] charClassExpr ::= '[' charGroup ']'

5129

*/

5130

static void

5131

xmlFAParseCharClass(xmlRegParserCtxtPtr ctxt) {

5132

if (CUR == '[') {

5133

NEXT;

5134

ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_RANGES);

5135

if (ctxt->atom == NULL)

5136

return;

5137

xmlFAParseCharGroup(ctxt);

5138

if (CUR == ']') {

5139

NEXT;

5140

} else {

5141

ERROR("xmlFAParseCharClass: ']' expected");

5142

}

5143

} else {

5144

xmlFAParseCharClassEsc(ctxt);

5145

}

5146

}

5147

5148

/**

5149

* xmlFAParseQuantExact:

5150

* @ctxt: a regexp parser context

5151

*

5152

* [8] QuantExact ::= [0-9]+

5153

*

5154

* Returns 0 if success or -1 in case of error

5155

*/

5156

static int

5157

xmlFAParseQuantExact(xmlRegParserCtxtPtr ctxt) {

5158

int ret = 0;

5159

int ok = 0;

5160

5161

while ((CUR >= '0') && (CUR <= '9')) {

5162

ret = ret * 10 + (CUR - '0');

5163

ok = 1;

5164

NEXT;

5165

}

5166

if (ok != 1) {

5167

return(-1);

5168

}

5169

return(ret);

5170

}

5171

5172

/**

5173

* xmlFAParseQuantifier:

5174

* @ctxt: a regexp parser context

5175

*

5176

* [4] quantifier ::= [?*+] | ( '{' quantity '}' )

5177

* [5] quantity ::= quantRange | quantMin | QuantExact

5178

* [6] quantRange ::= QuantExact ',' QuantExact

5179

* [7] quantMin ::= QuantExact ','

5180

* [8] QuantExact ::= [0-9]+

5181

*/

5182

static int

5183

xmlFAParseQuantifier(xmlRegParserCtxtPtr ctxt) {

5184

int cur;

5185

5186

cur = CUR;

5187

if ((cur == '?') || (cur == '*') || (cur == '+')) {

5188

if (ctxt->atom != NULL) {

5189

if (cur == '?')

5190

ctxt->atom->quant = XML_REGEXP_QUANT_OPT;

5191

else if (cur == '*')

5192

ctxt->atom->quant = XML_REGEXP_QUANT_MULT;

5193

else if (cur == '+')

5194

ctxt->atom->quant = XML_REGEXP_QUANT_PLUS;

5195

}

5196

NEXT;

5197

return(1);

5198

}

5199

if (cur == '{') {

5200

int min = 0, max = 0;

5201

5202

NEXT;

5203

cur = xmlFAParseQuantExact(ctxt);

5204

if (cur >= 0)

5205

min = cur;

5206

if (CUR == ',') {

5207

NEXT;

5208

if (CUR == '}')

5209

max = INT_MAX;

5210

else {

5211

cur = xmlFAParseQuantExact(ctxt);

5212

if (cur >= 0)

5213

max = cur;

5214

else {

5215

ERROR("Improper quantifier");

5216

}

5217

}

5218

}

5219

if (CUR == '}') {

5220

NEXT;

5221

} else {

5222

ERROR("Unterminated quantifier");

5223

}

5224

if (max == 0)

5225

max = min;

5226

if (ctxt->atom != NULL) {

5227

ctxt->atom->quant = XML_REGEXP_QUANT_RANGE;

5228

ctxt->atom->min = min;

5229

ctxt->atom->max = max;

5230

}

5231

return(1);

5232

}

5233

return(0);

5234

}

5235

5236

/**

5237

* xmlFAParseAtom:

5238

* @ctxt: a regexp parser context

5239

*

5240

* [9] atom ::= Char | charClass | ( '(' regExp ')' )

5241

*/

5242

static int

5243

xmlFAParseAtom(xmlRegParserCtxtPtr ctxt) {

5244

int codepoint, len;

5245

5246

codepoint = xmlFAIsChar(ctxt);

5247

if (codepoint > 0) {

5248

ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);

5249

if (ctxt->atom == NULL)

5250

return(-1);

5251

codepoint = CUR_SCHAR(ctxt->cur, len);

5252

ctxt->atom->codepoint = codepoint;

5253

NEXTL(len);

5254

return(1);

5255

} else if (CUR == '|') {

5256

return(0);

5257

} else if (CUR == 0) {

5258

return(0);

5259

} else if (CUR == ')') {

5260

return(0);

5261

} else if (CUR == '(') {

5262

xmlRegStatePtr start, oldend, start0;

5263

5264

NEXT;

5265

/*

5266

* this extra Epsilon transition is needed if we count with 0 allowed

5267

* unfortunately this can't be known at that point

5268

*/

5269

xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);

5270

start0 = ctxt->state;

5271

xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);

5272

start = ctxt->state;

5273

oldend = ctxt->end;

5274

ctxt->end = NULL;

5275

ctxt->atom = NULL;

5276

xmlFAParseRegExp(ctxt, 0);

5277

if (CUR == ')') {

5278

NEXT;

5279

} else {

5280

ERROR("xmlFAParseAtom: expecting ')'");

5281

}

5282

ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_SUBREG);

5283

if (ctxt->atom == NULL)

5284

return(-1);

5285

ctxt->atom->start = start;

5286

ctxt->atom->start0 = start0;

5287

ctxt->atom->stop = ctxt->state;

5288

ctxt->end = oldend;

5289

return(1);

5290

} else if ((CUR == '[') || (CUR == '\\') || (CUR == '.')) {

5291

xmlFAParseCharClass(ctxt);

5292

return(1);

5293

}

5294

return(0);

5295

}

5296

5297

/**

5298

* xmlFAParsePiece:

5299

* @ctxt: a regexp parser context

5300

*

5301

* [3] piece ::= atom quantifier?

5302

*/

5303

static int

5304

xmlFAParsePiece(xmlRegParserCtxtPtr ctxt) {

5305

int ret;

5306

5307

ctxt->atom = NULL;

5308

ret = xmlFAParseAtom(ctxt);

5309

if (ret == 0)

5310

return(0);

5311

if (ctxt->atom == NULL) {

5312

ERROR("internal: no atom generated");

5313

}

5314

xmlFAParseQuantifier(ctxt);

5315

return(1);

5316

}

5317

5318

/**

5319

* xmlFAParseBranch:

5320

* @ctxt: a regexp parser context

5321

* @to: optional target to the end of the branch

5322

*

5323

* @to is used to optimize by removing duplicate path in automata

5324

* in expressions like (a|b)(c|d)

5325

*

5326

* [2] branch ::= piece*

5327

*/

5328

static int

5329

xmlFAParseBranch(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr to) {

5330

xmlRegStatePtr previous;

5331

int ret;

5332

5333

previous = ctxt->state;

5334

ret = xmlFAParsePiece(ctxt);

5335

if (ret != 0) {

5336

if (xmlFAGenerateTransitions(ctxt, previous,

5337

(CUR=='|' || CUR==')') ? to : NULL, ctxt->atom) < 0)

5338

return(-1);

5339

previous = ctxt->state;

5340

ctxt->atom = NULL;

5341

}

5342

while ((ret != 0) && (ctxt->error == 0)) {

5343

ret = xmlFAParsePiece(ctxt);

5344

if (ret != 0) {

5345

if (xmlFAGenerateTransitions(ctxt, previous,

5346

(CUR=='|' || CUR==')') ? to : NULL, ctxt->atom) < 0)

5347

return(-1);

5348

previous = ctxt->state;

5349

ctxt->atom = NULL;

5350

}

5351

}

5352

return(0);

5353

}

5354

5355

/**

5356

* xmlFAParseRegExp:

5357

* @ctxt: a regexp parser context

5358

* @top: is this the top-level expression ?

5359

*

5360

* [1] regExp ::= branch ( '|' branch )*

5361

*/

5362

static void

5363

xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top) {

5364

xmlRegStatePtr start, end;

5365

5366

/* if not top start should have been generated by an epsilon trans */

5367

start = ctxt->state;

5368

ctxt->end = NULL;

5369

xmlFAParseBranch(ctxt, NULL);

5370

if (top) {

5371

#ifdef DEBUG_REGEXP_GRAPH

5372

printf("State %d is final\n", ctxt->state->no);

5373

#endif

5374

ctxt->state->type = XML_REGEXP_FINAL_STATE;

5375

}

5376

if (CUR != '|') {

5377

ctxt->end = ctxt->state;

5378

return;

5379

}

5380

end = ctxt->state;

5381

while ((CUR == '|') && (ctxt->error == 0)) {

5382

NEXT;

5383

if (CUR == 0) {

5384

ERROR("expecting a branch after |")

5385

return;

5386

}

5387

ctxt->state = start;

5388

ctxt->end = NULL;

5389

xmlFAParseBranch(ctxt, end);

5390

}

5391

if (!top) {

5392

ctxt->state = end;

5393

ctxt->end = end;

5394

}

5395

}

5396

5397

/************************************************************************

5398

* *

5399

* The basic API *

5400

* *

5401

************************************************************************/

5402

5403

/**

5404

* xmlRegexpPrint:

5405

* @output: the file for the output debug

5406

* @regexp: the compiled regexp

5407

*

5408

* Print the content of the compiled regular expression

5409

*/

5410

void

5411

xmlRegexpPrint(FILE *output, xmlRegexpPtr regexp) {

5412

int i;

5413

5414

if (output == NULL)

5415

return;

5416

fprintf(output, " regexp: ");

5417

if (regexp == NULL) {

5418

fprintf(output, "NULL\n");

5419

return;

5420

}

5421

fprintf(output, "'%s' ", regexp->string);

5422

fprintf(output, "\n");

5423

fprintf(output, "%d atoms:\n", regexp->nbAtoms);

5424

for (i = 0;i < regexp->nbAtoms; i++) {

5425

fprintf(output, " %02d ", i);

5426

xmlRegPrintAtom(output, regexp->atoms[i]);

5427

}

5428

fprintf(output, "%d states:", regexp->nbStates);

5429

fprintf(output, "\n");

5430

for (i = 0;i < regexp->nbStates; i++) {

5431

xmlRegPrintState(output, regexp->states[i]);

5432

}

5433

fprintf(output, "%d counters:\n", regexp->nbCounters);

5434

for (i = 0;i < regexp->nbCounters; i++) {

5435

fprintf(output, " %d: min %d max %d\n", i, regexp->counters[i].min,

5436

regexp->counters[i].max);

5437

}

5438

}

5439

5440

/**

5441

* xmlRegexpCompile:

5442

* @regexp: a regular expression string

5443

*

5444

* Parses a regular expression conforming to XML Schemas Part 2 Datatype

5445

* Appendix F and builds an automata suitable for testing strings against

5446

* that regular expression

5447

*

5448

* Returns the compiled expression or NULL in case of error

5449

*/

5450

xmlRegexpPtr

5451

xmlRegexpCompile(const xmlChar *regexp) {

5452

xmlRegexpPtr ret;

5453

xmlRegParserCtxtPtr ctxt;

5454

5455

ctxt = xmlRegNewParserCtxt(regexp);

5456

if (ctxt == NULL)

5457

return(NULL);

5458

5459

/* initialize the parser */

5460

ctxt->end = NULL;

5461

ctxt->start = ctxt->state = xmlRegNewState(ctxt);

5462

xmlRegStatePush(ctxt, ctxt->start);

5463

5464

/* parse the expression building an automata */

5465

xmlFAParseRegExp(ctxt, 1);

5466

if (CUR != 0) {

5467

ERROR("xmlFAParseRegExp: extra characters");

5468

}

5469

if (ctxt->error != 0) {

5470

xmlRegFreeParserCtxt(ctxt);

5471

return(NULL);

5472

}

5473

ctxt->end = ctxt->state;

5474

ctxt->start->type = XML_REGEXP_START_STATE;

5475

ctxt->end->type = XML_REGEXP_FINAL_STATE;

5476

5477

/* remove the Epsilon except for counted transitions */

5478

xmlFAEliminateEpsilonTransitions(ctxt);

5479

5480

5481

if (ctxt->error != 0) {

5482

xmlRegFreeParserCtxt(ctxt);

5483

return(NULL);

5484

}

5485

ret = xmlRegEpxFromParse(ctxt);

5486

xmlRegFreeParserCtxt(ctxt);

5487

return(ret);

5488

}

5489

5490

/**

5491

* xmlRegexpExec:

5492

* @comp: the compiled regular expression

5493

* @content: the value to check against the regular expression

5494

*

5495

* Check if the regular expression generates the value

5496

*

5497

* Returns 1 if it matches, 0 if not and a negative value in case of error

5498

*/

5499

int

5500

xmlRegexpExec(xmlRegexpPtr comp, const xmlChar *content) {

5501

if ((comp == NULL) || (content == NULL))

5502

return(-1);

5503

return(xmlFARegExec(comp, content));

5504

}

5505

5506

/**

5507

* xmlRegexpIsDeterminist:

5508

* @comp: the compiled regular expression

5509

*

5510

* Check if the regular expression is determinist

5511

*

5512

* Returns 1 if it yes, 0 if not and a negative value in case of error

5513

*/

5514

int

5515

xmlRegexpIsDeterminist(xmlRegexpPtr comp) {

5516

xmlAutomataPtr am;

5517

int ret;

5518

5519

if (comp == NULL)

5520

return(-1);

5521

if (comp->determinist != -1)

5522

return(comp->determinist);

5523

5524

am = xmlNewAutomata();

5525

if (am->states != NULL) {

5526

int i;

5527

5528

for (i = 0;i < am->nbStates;i++)

5529

xmlRegFreeState(am->states[i]);

5530

xmlFree(am->states);

5531

}

5532

am->nbAtoms = comp->nbAtoms;

5533

am->atoms = comp->atoms;

5534

am->nbStates = comp->nbStates;

5535

am->states = comp->states;

5536

am->determinist = -1;

5537

am->flags = comp->flags;

5538

ret = xmlFAComputesDeterminism(am);

5539

am->atoms = NULL;

5540

am->states = NULL;

5541

xmlFreeAutomata(am);

5542

comp->determinist = ret;

5543

return(ret);

5544

}

5545

5546

/**

5547

* xmlRegFreeRegexp:

5548

* @regexp: the regexp

5549

*

5550

* Free a regexp

5551

*/

5552

void

5553

xmlRegFreeRegexp(xmlRegexpPtr regexp) {

5554

int i;

5555

if (regexp == NULL)

5556

return;

5557

5558

if (regexp->string != NULL)

5559

xmlFree(regexp->string);

5560

if (regexp->states != NULL) {

5561

for (i = 0;i < regexp->nbStates;i++)

5562

xmlRegFreeState(regexp->states[i]);

5563

xmlFree(regexp->states);

5564

}

5565

if (regexp->atoms != NULL) {

5566

for (i = 0;i < regexp->nbAtoms;i++)

5567

xmlRegFreeAtom(regexp->atoms[i]);

5568

xmlFree(regexp->atoms);

5569

}

5570

if (regexp->counters != NULL)

5571

xmlFree(regexp->counters);

5572

if (regexp->compact != NULL)

5573

xmlFree(regexp->compact);

5574

if (regexp->transdata != NULL)

5575

xmlFree(regexp->transdata);

5576

if (regexp->stringMap != NULL) {

5577

for (i = 0; i < regexp->nbstrings;i++)

5578

xmlFree(regexp->stringMap[i]);

5579

xmlFree(regexp->stringMap);

5580

}

5581

5582

xmlFree(regexp);

5583

}

5584

5585

#ifdef LIBXML_AUTOMATA_ENABLED

5586

/************************************************************************

5587

* *

5588

* The Automata interface *

5589

* *

5590

************************************************************************/

5591

5592

/**

5593

* xmlNewAutomata:

5594

*

5595

* Create a new automata

5596

*

5597

* Returns the new object or NULL in case of failure

5598

*/

5599

xmlAutomataPtr

5600

xmlNewAutomata(void) {

5601

xmlAutomataPtr ctxt;

5602

5603

ctxt = xmlRegNewParserCtxt(NULL);

5604

if (ctxt == NULL)

5605

return(NULL);

5606

5607

/* initialize the parser */

5608

ctxt->end = NULL;

5609

ctxt->start = ctxt->state = xmlRegNewState(ctxt);

5610

if (ctxt->start == NULL) {

5611

xmlFreeAutomata(ctxt);

5612

return(NULL);

5613

}

5614

ctxt->start->type = XML_REGEXP_START_STATE;

5615

if (xmlRegStatePush(ctxt, ctxt->start) < 0) {

5616

xmlRegFreeState(ctxt->start);

5617

xmlFreeAutomata(ctxt);

5618

return(NULL);

5619

}

5620

ctxt->flags = 0;

5621

5622

return(ctxt);

5623

}

5624

5625

/**

5626

* xmlFreeAutomata:

5627

* @am: an automata

5628

*

5629

* Free an automata

5630

*/

5631

void

5632

xmlFreeAutomata(xmlAutomataPtr am) {

5633

if (am == NULL)

5634

return;

5635

xmlRegFreeParserCtxt(am);

5636

}

5637

5638

/**

5639

* xmlAutomataSetFlags:

5640

* @am: an automata

5641

* @flags: a set of internal flags

5642

*

5643

* Set some flags on the automata

5644

*/

5645

void

5646

xmlAutomataSetFlags(xmlAutomataPtr am, int flags) {

5647

if (am == NULL)

5648

return;

5649

am->flags |= flags;

5650

}

5651

5652

/**

5653

* xmlAutomataGetInitState:

5654

* @am: an automata

5655

*

5656

* Initial state lookup

5657

*

5658

* Returns the initial state of the automata

5659

*/

5660

xmlAutomataStatePtr

5661

xmlAutomataGetInitState(xmlAutomataPtr am) {

5662

if (am == NULL)

5663

return(NULL);

5664

return(am->start);

5665

}

5666

5667

/**

5668

* xmlAutomataSetFinalState:

5669

* @am: an automata

5670

* @state: a state in this automata

5671

*

5672

* Makes that state a final state

5673

*

5674

* Returns 0 or -1 in case of error

5675

*/

5676

int

5677

xmlAutomataSetFinalState(xmlAutomataPtr am, xmlAutomataStatePtr state) {

5678

if ((am == NULL) || (state == NULL))

5679

return(-1);

5680

state->type = XML_REGEXP_FINAL_STATE;

5681

return(0);

5682

}

5683

5684

/**

5685

* xmlAutomataNewTransition:

5686

* @am: an automata

5687

* @from: the starting point of the transition

5688

* @to: the target point of the transition or NULL

5689

* @token: the input string associated to that transition

5690

* @data: data passed to the callback function if the transition is activated

5691

*

5692

* If @to is NULL, this creates first a new target state in the automata

5693

* and then adds a transition from the @from state to the target state

5694

* activated by the value of @token

5695

*

5696

* Returns the target state or NULL in case of error

5697

*/

5698

xmlAutomataStatePtr

5699

xmlAutomataNewTransition(xmlAutomataPtr am, xmlAutomataStatePtr from,

5700

xmlAutomataStatePtr to, const xmlChar *token,

5701

void *data) {

5702

xmlRegAtomPtr atom;

5703

5704

if ((am == NULL) || (from == NULL) || (token == NULL))

5705

return(NULL);

5706

atom = xmlRegNewAtom(am, XML_REGEXP_STRING);

5707

if (atom == NULL)

5708

return(NULL);

5709

atom->data = data;

5710

if (atom == NULL)

5711

return(NULL);

5712

atom->valuep = xmlStrdup(token);

5713

5714

if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {

5715

xmlRegFreeAtom(atom);

5716

return(NULL);

5717

}

5718

if (to == NULL)

5719

return(am->state);

5720

return(to);

5721

}

5722

5723

/**

5724

* xmlAutomataNewTransition2:

5725

* @am: an automata

5726

* @from: the starting point of the transition

5727

* @to: the target point of the transition or NULL

5728

* @token: the first input string associated to that transition

5729

* @token2: the second input string associated to that transition

5730

* @data: data passed to the callback function if the transition is activated

5731

*

5732

* If @to is NULL, this creates first a new target state in the automata

5733

* and then adds a transition from the @from state to the target state

5734

* activated by the value of @token

5735

*

5736

* Returns the target state or NULL in case of error

5737

*/

5738

xmlAutomataStatePtr

5739

xmlAutomataNewTransition2(xmlAutomataPtr am, xmlAutomataStatePtr from,

5740

xmlAutomataStatePtr to, const xmlChar *token,

5741

const xmlChar *token2, void *data) {

5742

xmlRegAtomPtr atom;

5743

5744

if ((am == NULL) || (from == NULL) || (token == NULL))

5745

return(NULL);

5746

atom = xmlRegNewAtom(am, XML_REGEXP_STRING);

5747

if (atom == NULL)

5748

return(NULL);

5749

atom->data = data;

5750

if ((token2 == NULL) || (*token2 == 0)) {

5751

atom->valuep = xmlStrdup(token);

5752

} else {

5753

int lenn, lenp;

5754

xmlChar *str;

5755

5756

lenn = strlen((char *) token2);

5757

lenp = strlen((char *) token);

5758

5759

str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);

5760

if (str == NULL) {

5761

xmlRegFreeAtom(atom);

5762

return(NULL);

5763

}

5764

memcpy(&str[0], token, lenp);

5765

str[lenp] = '|';

5766

memcpy(&str[lenp + 1], token2, lenn);

5767

str[lenn + lenp + 1] = 0;

5768

5769

atom->valuep = str;

5770

}

5771

5772

if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {

5773

xmlRegFreeAtom(atom);

5774

return(NULL);

5775

}

5776

if (to == NULL)

5777

return(am->state);

5778

return(to);

5779

}

5780

5781

/**

5782

* xmlAutomataNewNegTrans:

5783

* @am: an automata

5784

* @from: the starting point of the transition

5785

* @to: the target point of the transition or NULL

5786

* @token: the first input string associated to that transition

5787

* @token2: the second input string associated to that transition

5788

* @data: data passed to the callback function if the transition is activated

5789

*

5790

* If @to is NULL, this creates first a new target state in the automata

5791

* and then adds a transition from the @from state to the target state

5792

* activated by any value except (@token,@token2)

5793

* Note that if @token2 is not NULL, then (X, NULL) won't match to follow

5794

# the semantic of XSD ##other

5795

*

5796

* Returns the target state or NULL in case of error

5797

*/

5798

xmlAutomataStatePtr

5799

xmlAutomataNewNegTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,

5800

xmlAutomataStatePtr to, const xmlChar *token,

5801

const xmlChar *token2, void *data) {

5802

xmlRegAtomPtr atom;

5803

xmlChar err_msg[200];

5804

5805

if ((am == NULL) || (from == NULL) || (token == NULL))

5806

return(NULL);

5807

atom = xmlRegNewAtom(am, XML_REGEXP_STRING);

5808

if (atom == NULL)

5809

return(NULL);

5810

atom->data = data;

5811

atom->neg = 1;

5812

if ((token2 == NULL) || (*token2 == 0)) {

5813

atom->valuep = xmlStrdup(token);

5814

} else {

5815

int lenn, lenp;

5816

xmlChar *str;

5817

5818

lenn = strlen((char *) token2);

5819

lenp = strlen((char *) token);

5820

5821

str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);

5822

if (str == NULL) {

5823

xmlRegFreeAtom(atom);

5824

return(NULL);

5825

}

5826

memcpy(&str[0], token, lenp);

5827

str[lenp] = '|';

5828

memcpy(&str[lenp + 1], token2, lenn);

5829

str[lenn + lenp + 1] = 0;

5830

5831

atom->valuep = str;

5832

}

5833

snprintf((char *) err_msg, 199, "not %s", (const char *) atom->valuep);

5834

err_msg[199] = 0;

5835

atom->valuep2 = xmlStrdup(err_msg);

5836

5837

if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {

5838

xmlRegFreeAtom(atom);

5839

return(NULL);

5840

}

5841

am->negs++;

5842

if (to == NULL)

5843

return(am->state);

5844

return(to);

5845

}

5846

5847

/**

5848

* xmlAutomataNewCountTrans2:

5849

* @am: an automata

5850

* @from: the starting point of the transition

5851

* @to: the target point of the transition or NULL

5852

* @token: the input string associated to that transition

5853

* @token2: the second input string associated to that transition

5854

* @min: the minimum successive occurences of token

5855

* @max: the maximum successive occurences of token

5856

* @data: data associated to the transition

5857

*

5858

* If @to is NULL, this creates first a new target state in the automata

5859

* and then adds a transition from the @from state to the target state

5860

* activated by a succession of input of value @token and @token2 and

5861

* whose number is between @min and @max

5862

*

5863

* Returns the target state or NULL in case of error

5864

*/

5865

xmlAutomataStatePtr

5866

xmlAutomataNewCountTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from,

5867

xmlAutomataStatePtr to, const xmlChar *token,

5868

const xmlChar *token2,

5869

int min, int max, void *data) {

5870

xmlRegAtomPtr atom;

5871

int counter;

5872

5873

if ((am == NULL) || (from == NULL) || (token == NULL))

5874

return(NULL);

5875

if (min < 0)

5876

return(NULL);

5877

if ((max < min) || (max < 1))

5878

return(NULL);

5879

atom = xmlRegNewAtom(am, XML_REGEXP_STRING);

5880

if (atom == NULL)

5881

return(NULL);

5882

if ((token2 == NULL) || (*token2 == 0)) {

5883

atom->valuep = xmlStrdup(token);

5884

} else {

5885

int lenn, lenp;

5886

xmlChar *str;

5887

5888

lenn = strlen((char *) token2);

5889

lenp = strlen((char *) token);

5890

5891

str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);

5892

if (str == NULL) {

5893

xmlRegFreeAtom(atom);

5894

return(NULL);

5895

}

5896

memcpy(&str[0], token, lenp);

5897

str[lenp] = '|';

5898

memcpy(&str[lenp + 1], token2, lenn);

5899

str[lenn + lenp + 1] = 0;

5900

5901

atom->valuep = str;

5902

}

5903

atom->data = data;

5904

if (min == 0)

5905

atom->min = 1;

5906

else

5907

atom->min = min;

5908

atom->max = max;

5909

5910

/*

5911

* associate a counter to the transition.

5912

*/

5913

counter = xmlRegGetCounter(am);

5914

am->counters[counter].min = min;

5915

am->counters[counter].max = max;

5916

5917

/* xmlFAGenerateTransitions(am, from, to, atom); */

5918

if (to == NULL) {

5919

to = xmlRegNewState(am);

5920

xmlRegStatePush(am, to);

5921

}

5922

xmlRegStateAddTrans(am, from, atom, to, counter, -1);

5923

xmlRegAtomPush(am, atom);

5924

am->state = to;

5925

5926

if (to == NULL)

5927

to = am->state;

5928

if (to == NULL)

5929

return(NULL);

5930

if (min == 0)

5931

xmlFAGenerateEpsilonTransition(am, from, to);

5932

return(to);

5933

}

5934

5935

/**

5936

* xmlAutomataNewCountTrans:

5937

* @am: an automata

5938

* @from: the starting point of the transition

5939

* @to: the target point of the transition or NULL

5940

* @token: the input string associated to that transition

5941

* @min: the minimum successive occurences of token

5942

* @max: the maximum successive occurences of token

5943

* @data: data associated to the transition

5944

*

5945

* If @to is NULL, this creates first a new target state in the automata

5946

* and then adds a transition from the @from state to the target state

5947

* activated by a succession of input of value @token and whose number

5948

* is between @min and @max

5949

*

5950

* Returns the target state or NULL in case of error

5951

*/

5952

xmlAutomataStatePtr

5953

xmlAutomataNewCountTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,

5954

xmlAutomataStatePtr to, const xmlChar *token,

5955

int min, int max, void *data) {

5956

xmlRegAtomPtr atom;

5957

int counter;

5958

5959

if ((am == NULL) || (from == NULL) || (token == NULL))

5960

return(NULL);

5961

if (min < 0)

5962

return(NULL);

5963

if ((max < min) || (max < 1))

5964

return(NULL);

5965

atom = xmlRegNewAtom(am, XML_REGEXP_STRING);

5966

if (atom == NULL)

5967

return(NULL);

5968

atom->valuep = xmlStrdup(token);

5969

atom->data = data;

5970

if (min == 0)

5971

atom->min = 1;

5972

else

5973

atom->min = min;

5974

atom->max = max;

5975

5976

/*

5977

* associate a counter to the transition.

5978

*/

5979

counter = xmlRegGetCounter(am);

5980

am->counters[counter].min = min;

5981

am->counters[counter].max = max;

5982

5983

/* xmlFAGenerateTransitions(am, from, to, atom); */

5984

if (to == NULL) {

5985

to = xmlRegNewState(am);

5986

xmlRegStatePush(am, to);

5987

}

5988

xmlRegStateAddTrans(am, from, atom, to, counter, -1);

5989

xmlRegAtomPush(am, atom);

5990

am->state = to;

5991

5992

if (to == NULL)

5993

to = am->state;

5994

if (to == NULL)

5995

return(NULL);

5996

if (min == 0)

5997

xmlFAGenerateEpsilonTransition(am, from, to);

5998

return(to);

5999

}

6000

6001

/**

6002

* xmlAutomataNewOnceTrans2:

6003

* @am: an automata

6004

* @from: the starting point of the transition

6005

* @to: the target point of the transition or NULL

6006

* @token: the input string associated to that transition

6007

* @token2: the second input string associated to that transition

6008

* @min: the minimum successive occurences of token

6009

* @max: the maximum successive occurences of token

6010

* @data: data associated to the transition

6011

*

6012

* If @to is NULL, this creates first a new target state in the automata

6013

* and then adds a transition from the @from state to the target state

6014

* activated by a succession of input of value @token and @token2 and whose

6015

* number is between @min and @max, moreover that transition can only be

6016

* crossed once.

6017

*

6018

* Returns the target state or NULL in case of error

6019

*/

6020

xmlAutomataStatePtr

6021

xmlAutomataNewOnceTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from,

6022

xmlAutomataStatePtr to, const xmlChar *token,

6023

const xmlChar *token2,

6024

int min, int max, void *data) {

6025

xmlRegAtomPtr atom;

6026

int counter;

6027

6028

if ((am == NULL) || (from == NULL) || (token == NULL))

6029

return(NULL);

6030

if (min < 1)

6031

return(NULL);

6032

if ((max < min) || (max < 1))

6033

return(NULL);

6034

atom = xmlRegNewAtom(am, XML_REGEXP_STRING);

6035

if (atom == NULL)

6036

return(NULL);

6037

if ((token2 == NULL) || (*token2 == 0)) {

6038

atom->valuep = xmlStrdup(token);

6039

} else {

6040

int lenn, lenp;

6041

xmlChar *str;

6042

6043

lenn = strlen((char *) token2);

6044

lenp = strlen((char *) token);

6045

6046

str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);

6047

if (str == NULL) {

6048

xmlRegFreeAtom(atom);

6049

return(NULL);

6050

}

6051

memcpy(&str[0], token, lenp);

6052

str[lenp] = '|';

6053

memcpy(&str[lenp + 1], token2, lenn);

6054

str[lenn + lenp + 1] = 0;

6055

6056

atom->valuep = str;

6057

}

6058

atom->data = data;

6059

atom->quant = XML_REGEXP_QUANT_ONCEONLY;

6060

atom->min = min;

6061

atom->max = max;

6062

/*

6063

* associate a counter to the transition.

6064

*/

6065

counter = xmlRegGetCounter(am);

6066

am->counters[counter].min = 1;

6067

am->counters[counter].max = 1;

6068

6069

/* xmlFAGenerateTransitions(am, from, to, atom); */

6070

if (to == NULL) {

6071

to = xmlRegNewState(am);

6072

xmlRegStatePush(am, to);

6073

}

6074

xmlRegStateAddTrans(am, from, atom, to, counter, -1);

6075

xmlRegAtomPush(am, atom);

6076

am->state = to;

6077

return(to);

6078

}

6079

6080

6081

6082

/**

6083

* xmlAutomataNewOnceTrans:

6084

* @am: an automata

6085

* @from: the starting point of the transition

6086

* @to: the target point of the transition or NULL

6087

* @token: the input string associated to that transition

6088

* @min: the minimum successive occurences of token

6089

* @max: the maximum successive occurences of token

6090

* @data: data associated to the transition

6091

*

6092

* If @to is NULL, this creates first a new target state in the automata

6093

* and then adds a transition from the @from state to the target state

6094

* activated by a succession of input of value @token and whose number

6095

* is between @min and @max, moreover that transition can only be crossed

6096

* once.

6097

*

6098

* Returns the target state or NULL in case of error

6099

*/

6100

xmlAutomataStatePtr

6101

xmlAutomataNewOnceTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,

6102

xmlAutomataStatePtr to, const xmlChar *token,

6103

int min, int max, void *data) {

6104

xmlRegAtomPtr atom;

6105

int counter;

6106

6107

if ((am == NULL) || (from == NULL) || (token == NULL))

6108

return(NULL);

6109

if (min < 1)

6110

return(NULL);

6111

if ((max < min) || (max < 1))

6112

return(NULL);

6113

atom = xmlRegNewAtom(am, XML_REGEXP_STRING);

6114

if (atom == NULL)

6115

return(NULL);

6116

atom->valuep = xmlStrdup(token);

6117

atom->data = data;

6118

atom->quant = XML_REGEXP_QUANT_ONCEONLY;

6119

atom->min = min;

6120

atom->max = max;

6121

/*

6122

* associate a counter to the transition.

6123

*/

6124

counter = xmlRegGetCounter(am);

6125

am->counters[counter].min = 1;

6126

am->counters[counter].max = 1;

6127

6128

/* xmlFAGenerateTransitions(am, from, to, atom); */

6129

if (to == NULL) {

6130

to = xmlRegNewState(am);

6131

xmlRegStatePush(am, to);

6132

}

6133

xmlRegStateAddTrans(am, from, atom, to, counter, -1);

6134

xmlRegAtomPush(am, atom);

6135

am->state = to;

6136

return(to);

6137

}

6138

6139

/**

6140

* xmlAutomataNewState:

6141

* @am: an automata

6142

*

6143

* Create a new disconnected state in the automata

6144

*

6145

* Returns the new state or NULL in case of error

6146

*/

6147

xmlAutomataStatePtr

6148

xmlAutomataNewState(xmlAutomataPtr am) {

6149

xmlAutomataStatePtr to;

6150

6151

if (am == NULL)

6152

return(NULL);

6153

to = xmlRegNewState(am);

6154

xmlRegStatePush(am, to);

6155

return(to);

6156

}

6157

6158

/**

6159

* xmlAutomataNewEpsilon:

6160

* @am: an automata

6161

* @from: the starting point of the transition

6162

* @to: the target point of the transition or NULL

6163

*

6164

* If @to is NULL, this creates first a new target state in the automata

6165

* and then adds an epsilon transition from the @from state to the

6166

* target state

6167

*

6168

* Returns the target state or NULL in case of error

6169

*/

6170

xmlAutomataStatePtr

6171

xmlAutomataNewEpsilon(xmlAutomataPtr am, xmlAutomataStatePtr from,

6172

xmlAutomataStatePtr to) {

6173

if ((am == NULL) || (from == NULL))

6174

return(NULL);

6175

xmlFAGenerateEpsilonTransition(am, from, to);

6176

if (to == NULL)

6177

return(am->state);

6178

return(to);

6179

}

6180

6181

/**

6182

* xmlAutomataNewAllTrans:

6183

* @am: an automata

6184

* @from: the starting point of the transition

6185

* @to: the target point of the transition or NULL

6186

* @lax: allow to transition if not all all transitions have been activated

6187

*

6188

* If @to is NULL, this creates first a new target state in the automata

6189

* and then adds a an ALL transition from the @from state to the

6190

* target state. That transition is an epsilon transition allowed only when

6191

* all transitions from the @from node have been activated.

6192

*

6193

* Returns the target state or NULL in case of error

6194

*/

6195

xmlAutomataStatePtr

6196

xmlAutomataNewAllTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,

6197

xmlAutomataStatePtr to, int lax) {

6198

if ((am == NULL) || (from == NULL))

6199

return(NULL);

6200

xmlFAGenerateAllTransition(am, from, to, lax);

6201

if (to == NULL)

6202

return(am->state);

6203

return(to);

6204

}

6205

6206

/**

6207

* xmlAutomataNewCounter:

6208

* @am: an automata

6209

* @min: the minimal value on the counter

6210

* @max: the maximal value on the counter

6211

*

6212

* Create a new counter

6213

*

6214

* Returns the counter number or -1 in case of error

6215

*/

6216

int

6217

xmlAutomataNewCounter(xmlAutomataPtr am, int min, int max) {

6218

int ret;

6219

6220

if (am == NULL)

6221

return(-1);

6222

6223

ret = xmlRegGetCounter(am);

6224

if (ret < 0)

6225

return(-1);

6226

am->counters[ret].min = min;

6227

am->counters[ret].max = max;

6228

return(ret);

6229

}

6230

6231

/**

6232

* xmlAutomataNewCountedTrans:

6233

* @am: an automata

6234

* @from: the starting point of the transition

6235

* @to: the target point of the transition or NULL

6236

* @counter: the counter associated to that transition

6237

*

6238

* If @to is NULL, this creates first a new target state in the automata

6239

* and then adds an epsilon transition from the @from state to the target state

6240

* which will increment the counter provided

6241

*

6242

* Returns the target state or NULL in case of error

6243

*/

6244

xmlAutomataStatePtr

6245

xmlAutomataNewCountedTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,

6246

xmlAutomataStatePtr to, int counter) {

6247

if ((am == NULL) || (from == NULL) || (counter < 0))

6248

return(NULL);

6249

xmlFAGenerateCountedEpsilonTransition(am, from, to, counter);

6250

if (to == NULL)

6251

return(am->state);

6252

return(to);

6253

}

6254

6255

/**

6256

* xmlAutomataNewCounterTrans:

6257

* @am: an automata

6258

* @from: the starting point of the transition

6259

* @to: the target point of the transition or NULL

6260

* @counter: the counter associated to that transition

6261

*

6262

* If @to is NULL, this creates first a new target state in the automata

6263

* and then adds an epsilon transition from the @from state to the target state

6264

* which will be allowed only if the counter is within the right range.

6265

*

6266

* Returns the target state or NULL in case of error

6267

*/

6268

xmlAutomataStatePtr

6269

xmlAutomataNewCounterTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,

6270

xmlAutomataStatePtr to, int counter) {

6271

if ((am == NULL) || (from == NULL) || (counter < 0))

6272

return(NULL);

6273

xmlFAGenerateCountedTransition(am, from, to, counter);

6274

if (to == NULL)

6275

return(am->state);

6276

return(to);

6277

}

6278

6279

/**

6280

* xmlAutomataCompile:

6281

* @am: an automata

6282

*

6283

* Compile the automata into a Reg Exp ready for being executed.

6284

* The automata should be free after this point.

6285

*

6286

* Returns the compiled regexp or NULL in case of error

6287

*/

6288

xmlRegexpPtr

6289

xmlAutomataCompile(xmlAutomataPtr am) {

6290

xmlRegexpPtr ret;

6291

6292

if ((am == NULL) || (am->error != 0)) return(NULL);

6293

xmlFAEliminateEpsilonTransitions(am);

6294

/* xmlFAComputesDeterminism(am); */

6295

ret = xmlRegEpxFromParse(am);

6296

6297

return(ret);

6298

}

6299

6300

/**

6301

* xmlAutomataIsDeterminist:

6302

* @am: an automata

6303

*

6304

* Checks if an automata is determinist.

6305

*

6306

* Returns 1 if true, 0 if not, and -1 in case of error

6307

*/

6308

int

6309

xmlAutomataIsDeterminist(xmlAutomataPtr am) {

6310

int ret;

6311

6312

if (am == NULL)

6313

return(-1);

6314

6315

ret = xmlFAComputesDeterminism(am);

6316

return(ret);

6317

}

6318

#endif /* LIBXML_AUTOMATA_ENABLED */

6319

6320

#ifdef LIBXML_EXPR_ENABLED

6321

/************************************************************************

6322

* *

6323

* Formal Expression handling code *

6324

* *

6325

************************************************************************/

6326

/************************************************************************

6327

* *

6328

* Expression handling context *

6329

* *

6330

************************************************************************/

6331

6332

struct _xmlExpCtxt {

6333

xmlDictPtr dict;

6334

xmlExpNodePtr *table;

6335

int size;

6336

int nbElems;

6337

int nb_nodes;

6338

int maxNodes;

6339

const char *expr;

6340

const char *cur;

6341

int nb_cons;

6342

int tabSize;

6343

};

6344

6345

/**

6346

* xmlExpNewCtxt:

6347

* @maxNodes: the maximum number of nodes

6348

* @dict: optional dictionnary to use internally

6349

*

6350

* Creates a new context for manipulating expressions

6351

*

6352

* Returns the context or NULL in case of error

6353

*/

6354

xmlExpCtxtPtr

6355

xmlExpNewCtxt(int maxNodes, xmlDictPtr dict) {

6356

xmlExpCtxtPtr ret;

6357

int size = 256;

6358

6359

if (maxNodes <= 4096)

6360

maxNodes = 4096;

6361

6362

ret = (xmlExpCtxtPtr) xmlMalloc(sizeof(xmlExpCtxt));

6363

if (ret == NULL)

6364

return(NULL);

6365

memset(ret, 0, sizeof(xmlExpCtxt));

6366

ret->size = size;

6367

ret->nbElems = 0;

6368

ret->maxNodes = maxNodes;

6369

ret->table = xmlMalloc(size * sizeof(xmlExpNodePtr));

6370

if (ret->table == NULL) {

6371

xmlFree(ret);

6372

return(NULL);

6373

}

6374

memset(ret->table, 0, size * sizeof(xmlExpNodePtr));

6375

if (dict == NULL) {

6376

ret->dict = xmlDictCreate();

6377

if (ret->dict == NULL) {

6378

xmlFree(ret->table);

6379

xmlFree(ret);

6380

return(NULL);

6381

}

6382

} else {

6383

ret->dict = dict;

6384

xmlDictReference(ret->dict);

6385

}

6386

return(ret);

6387

}

6388

6389

/**

6390

* xmlExpFreeCtxt:

6391

* @ctxt: an expression context

6392

*

6393

* Free an expression context

6394

*/

6395

void

6396

xmlExpFreeCtxt(xmlExpCtxtPtr ctxt) {

6397

if (ctxt == NULL)

6398

return;

6399

xmlDictFree(ctxt->dict);

6400

if (ctxt->table != NULL)

6401

xmlFree(ctxt->table);

6402

xmlFree(ctxt);

6403

}

6404

6405

/************************************************************************

6406

* *

6407

* Structure associated to an expression node *

6408

* *

6409

************************************************************************/

6410

#define MAX_NODES 10000

6411

6412

/* #define DEBUG_DERIV */

6413

6414

/*

6415

* TODO:

6416

* - Wildcards

6417

* - public API for creation

6418

*

6419

* Started

6420

* - regression testing

6421

*

6422

* Done

6423

* - split into module and test tool

6424

* - memleaks

6425

*/

6426

6427

typedef enum {

6428

XML_EXP_NILABLE = (1 << 0)

6429

} xmlExpNodeInfo;

6430

6431

#define IS_NILLABLE(node) ((node)->info & XML_EXP_NILABLE)

6432

6433

struct _xmlExpNode {

6434

unsigned char type;/* xmlExpNodeType */

6435

unsigned char info;/* OR of xmlExpNodeInfo */

6436

unsigned short key; /* the hash key */

6437

unsigned int ref; /* The number of references */

6438

int c_max; /* the maximum length it can consume */

6439

xmlExpNodePtr exp_left;

6440

xmlExpNodePtr next;/* the next node in the hash table or free list */

6441

union {

6442

struct {

6443

int f_min;

6444

int f_max;

6445

} count;

6446

struct {

6447

xmlExpNodePtr f_right;

6448

} children;

6449

const xmlChar *f_str;

6450

} field;

6451

};

6452

6453

#define exp_min field.count.f_min

6454

#define exp_max field.count.f_max

6455

/* #define exp_left field.children.f_left */

6456

#define exp_right field.children.f_right

6457

#define exp_str field.f_str

6458

6459

static xmlExpNodePtr xmlExpNewNode(xmlExpCtxtPtr ctxt, xmlExpNodeType type);

6460

static xmlExpNode forbiddenExpNode = {

6461

XML_EXP_FORBID, 0, 0, 0, 0, NULL, NULL, {{ 0, 0}}

6462

};

6463

xmlExpNodePtr forbiddenExp = &forbiddenExpNode;

6464

static xmlExpNode emptyExpNode = {

6465

XML_EXP_EMPTY, 1, 0, 0, 0, NULL, NULL, {{ 0, 0}}

6466

};

6467

xmlExpNodePtr emptyExp = &emptyExpNode;

6468

6469

/************************************************************************

6470

* *

6471

* The custom hash table for unicity and canonicalization *

6472

* of sub-expressions pointers *

6473

* *

6474

************************************************************************/

6475

/*

6476

* xmlExpHashNameComputeKey:

6477

* Calculate the hash key for a token

6478

*/

6479

static unsigned short

6480

xmlExpHashNameComputeKey(const xmlChar *name) {

6481

unsigned short value = 0L;

6482

char ch;

6483

6484

if (name != NULL) {

6485

value += 30 * (*name);

6486

while ((ch = *name++) != 0) {

6487

value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

6488

}

6489

}

6490

return (value);

6491

}

6492

6493

/*

6494

* xmlExpHashComputeKey:

6495

* Calculate the hash key for a compound expression

6496

*/

6497

static unsigned short

6498

xmlExpHashComputeKey(xmlExpNodeType type, xmlExpNodePtr left,

6499

xmlExpNodePtr right) {

6500

unsigned long value;

6501

unsigned short ret;

6502

6503

switch (type) {

6504

case XML_EXP_SEQ:

6505

value = left->key;

6506

value += right->key;

6507

value *= 3;

6508

ret = (unsigned short) value;

6509

break;

6510

case XML_EXP_OR:

6511

value = left->key;

6512

value += right->key;

6513

value *= 7;

6514

ret = (unsigned short) value;

6515

break;

6516

case XML_EXP_COUNT:

6517

value = left->key;

6518

value += right->key;

6519

ret = (unsigned short) value;

6520

break;

6521

default:

6522

ret = 0;

6523

}

6524

return(ret);

6525

}

6526

6527

6528

static xmlExpNodePtr

6529

xmlExpNewNode(xmlExpCtxtPtr ctxt, xmlExpNodeType type) {

6530

xmlExpNodePtr ret;

6531

6532

if (ctxt->nb_nodes >= MAX_NODES)

6533

return(NULL);

6534

ret = (xmlExpNodePtr) xmlMalloc(sizeof(xmlExpNode));

6535

if (ret == NULL)

6536

return(NULL);

6537

memset(ret, 0, sizeof(xmlExpNode));

6538

ret->type = type;

6539

ret->next = NULL;

6540

ctxt->nb_nodes++;

6541

ctxt->nb_cons++;

6542

return(ret);

6543

}

6544

6545

/**

6546

* xmlExpHashGetEntry:

6547

* @table: the hash table

6548

*

6549

* Get the unique entry from the hash table. The entry is created if

6550

* needed. @left and @right are consumed, i.e. their ref count will

6551

* be decremented by the operation.

6552

*

6553

* Returns the pointer or NULL in case of error

6554

*/

6555

static xmlExpNodePtr

6556

xmlExpHashGetEntry(xmlExpCtxtPtr ctxt, xmlExpNodeType type,

6557

xmlExpNodePtr left, xmlExpNodePtr right,

6558

const xmlChar *name, int min, int max) {

6559

unsigned short kbase, key;

6560

xmlExpNodePtr entry;

6561

xmlExpNodePtr insert;

6562

6563

if (ctxt == NULL)

6564

return(NULL);

6565

6566

/*

6567

* Check for duplicate and insertion location.

6568

*/

6569

if (type == XML_EXP_ATOM) {

6570

kbase = xmlExpHashNameComputeKey(name);

6571

} else if (type == XML_EXP_COUNT) {

6572

/* COUNT reduction rule 1 */

6573

/* a{1} -> a */

6574

if (min == max) {

6575

if (min == 1) {

6576

return(left);

6577

}

6578

if (min == 0) {

6579

xmlExpFree(ctxt, left);

6580

return(emptyExp);

6581

}

6582

}

6583

if (min < 0) {

6584

xmlExpFree(ctxt, left);

6585

return(forbiddenExp);

6586

}

6587

if (max == -1)

6588

kbase = min + 79;

6589

else

6590

kbase = max - min;

6591

kbase += left->key;

6592

} else if (type == XML_EXP_OR) {

6593

/* Forbid reduction rules */

6594

if (left->type == XML_EXP_FORBID) {

6595

xmlExpFree(ctxt, left);

6596

return(right);

6597

}

6598

if (right->type == XML_EXP_FORBID) {

6599

xmlExpFree(ctxt, right);

6600

return(left);

6601

}

6602

6603

/* OR reduction rule 1 */

6604

/* a | a reduced to a */

6605

if (left == right) {

6606

left->ref--;

6607

return(left);

6608

}

6609

/* OR canonicalization rule 1 */

6610

/* linearize (a | b) | c into a | (b | c) */

6611

if ((left->type == XML_EXP_OR) && (right->type != XML_EXP_OR)) {

6612

xmlExpNodePtr tmp = left;

6613

left = right;

6614

right = tmp;

6615

}

6616

/* OR reduction rule 2 */

6617

/* a | (a | b) and b | (a | b) are reduced to a | b */

6618

if (right->type == XML_EXP_OR) {

6619

if ((left == right->exp_left) ||

6620

(left == right->exp_right)) {

6621

xmlExpFree(ctxt, left);

6622

return(right);

6623

}

6624

}

6625

/* OR canonicalization rule 2 */

6626

/* linearize (a | b) | c into a | (b | c) */

6627

if (left->type == XML_EXP_OR) {

6628

xmlExpNodePtr tmp;

6629

6630

/* OR canonicalization rule 2 */

6631

if ((left->exp_right->type != XML_EXP_OR) &&

6632

(left->exp_right->key < left->exp_left->key)) {

6633

tmp = left->exp_right;

6634

left->exp_right = left->exp_left;

6635

left->exp_left = tmp;

6636

}

6637

left->exp_right->ref++;

6638

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left->exp_right, right,

6639

NULL, 0, 0);

6640

left->exp_left->ref++;

6641

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left->exp_left, tmp,

6642

NULL, 0, 0);

6643

6644

xmlExpFree(ctxt, left);

6645

return(tmp);

6646

}

6647

if (right->type == XML_EXP_OR) {

6648

/* Ordering in the tree */

6649

/* C | (A | B) -> A | (B | C) */

6650

if (left->key > right->exp_right->key) {

6651

xmlExpNodePtr tmp;

6652

right->exp_right->ref++;

6653

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_right,

6654

left, NULL, 0, 0);

6655

right->exp_left->ref++;

6656

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_left,

6657

tmp, NULL, 0, 0);

6658

xmlExpFree(ctxt, right);

6659

return(tmp);

6660

}

6661

/* Ordering in the tree */

6662

/* B | (A | C) -> A | (B | C) */

6663

if (left->key > right->exp_left->key) {

6664

xmlExpNodePtr tmp;

6665

right->exp_right->ref++;

6666

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left,

6667

right->exp_right, NULL, 0, 0);

6668

right->exp_left->ref++;

6669

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_left,

6670

tmp, NULL, 0, 0);

6671

xmlExpFree(ctxt, right);

6672

return(tmp);

6673

}

6674

}

6675

/* we know both types are != XML_EXP_OR here */

6676

else if (left->key > right->key) {

6677

xmlExpNodePtr tmp = left;

6678

left = right;

6679

right = tmp;

6680

}

6681

kbase = xmlExpHashComputeKey(type, left, right);

6682

} else if (type == XML_EXP_SEQ) {

6683

/* Forbid reduction rules */

6684

if (left->type == XML_EXP_FORBID) {

6685

xmlExpFree(ctxt, right);

6686

return(left);

6687

}

6688

if (right->type == XML_EXP_FORBID) {

6689

xmlExpFree(ctxt, left);

6690

return(right);

6691

}

6692

/* Empty reduction rules */

6693

if (right->type == XML_EXP_EMPTY) {

6694

return(left);

6695

}

6696

if (left->type == XML_EXP_EMPTY) {

6697

return(right);

6698

}

6699

kbase = xmlExpHashComputeKey(type, left, right);

6700

} else

6701

return(NULL);

6702

6703

key = kbase % ctxt->size;

6704

if (ctxt->table[key] != NULL) {

6705

for (insert = ctxt->table[key]; insert != NULL;

6706

insert = insert->next) {

6707

if ((insert->key == kbase) &&

6708

(insert->type == type)) {

6709

if (type == XML_EXP_ATOM) {

6710

if (name == insert->exp_str) {

6711

insert->ref++;

6712

return(insert);

6713

}

6714

} else if (type == XML_EXP_COUNT) {

6715

if ((insert->exp_min == min) && (insert->exp_max == max) &&

6716

(insert->exp_left == left)) {

6717

insert->ref++;

6718

left->ref--;

6719

return(insert);

6720

}

6721

} else if ((insert->exp_left == left) &&

6722

(insert->exp_right == right)) {

6723

insert->ref++;

6724

left->ref--;

6725

right->ref--;

6726

return(insert);

6727

}

6728

}

6729

}

6730

}

6731

6732

entry = xmlExpNewNode(ctxt, type);

6733

if (entry == NULL)

6734

return(NULL);

6735

entry->key = kbase;

6736

if (type == XML_EXP_ATOM) {

6737

entry->exp_str = name;

6738

entry->c_max = 1;

6739

} else if (type == XML_EXP_COUNT) {

6740

entry->exp_min = min;

6741

entry->exp_max = max;

6742

entry->exp_left = left;

6743

if ((min == 0) || (IS_NILLABLE(left)))

6744

entry->info |= XML_EXP_NILABLE;

6745

if (max < 0)

6746

entry->c_max = -1;

6747

else

6748

entry->c_max = max * entry->exp_left->c_max;

6749

} else {

6750

entry->exp_left = left;

6751

entry->exp_right = right;

6752

if (type == XML_EXP_OR) {

6753

if ((IS_NILLABLE(left)) || (IS_NILLABLE(right)))

6754

entry->info |= XML_EXP_NILABLE;

6755

if ((entry->exp_left->c_max == -1) ||

6756

(entry->exp_right->c_max == -1))

6757

entry->c_max = -1;

6758

else if (entry->exp_left->c_max > entry->exp_right->c_max)

6759

entry->c_max = entry->exp_left->c_max;

6760

else

6761

entry->c_max = entry->exp_right->c_max;

6762

} else {

6763

if ((IS_NILLABLE(left)) && (IS_NILLABLE(right)))

6764

entry->info |= XML_EXP_NILABLE;

6765

if ((entry->exp_left->c_max == -1) ||

6766

(entry->exp_right->c_max == -1))

6767

entry->c_max = -1;

6768

else

6769

entry->c_max = entry->exp_left->c_max + entry->exp_right->c_max;

6770

}

6771

}

6772

entry->ref = 1;

6773

if (ctxt->table[key] != NULL)

6774

entry->next = ctxt->table[key];

6775

6776

ctxt->table[key] = entry;

6777

ctxt->nbElems++;

6778

6779

return(entry);

6780

}

6781

6782

/**

6783

* xmlExpFree:

6784

* @ctxt: the expression context

6785

* @exp: the expression

6786

*

6787

* Dereference the expression

6788

*/

6789

void

6790

xmlExpFree(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp) {

6791

if ((exp == NULL) || (exp == forbiddenExp) || (exp == emptyExp))

6792

return;

6793

exp->ref--;

6794

if (exp->ref == 0) {

6795

unsigned short key;

6796

6797

/* Unlink it first from the hash table */

6798

key = exp->key % ctxt->size;

6799

if (ctxt->table[key] == exp) {

6800

ctxt->table[key] = exp->next;

6801

} else {

6802

xmlExpNodePtr tmp;

6803

6804

tmp = ctxt->table[key];

6805

while (tmp != NULL) {

6806

if (tmp->next == exp) {

6807

tmp->next = exp->next;

6808

break;

6809

}

6810

tmp = tmp->next;

6811

}

6812

}

6813

6814

if ((exp->type == XML_EXP_SEQ) || (exp->type == XML_EXP_OR)) {

6815

xmlExpFree(ctxt, exp->exp_left);

6816

xmlExpFree(ctxt, exp->exp_right);

6817

} else if (exp->type == XML_EXP_COUNT) {

6818

xmlExpFree(ctxt, exp->exp_left);

6819

}

6820

xmlFree(exp);

6821

ctxt->nb_nodes--;

6822

}

6823

}

6824

6825

/**

6826

* xmlExpRef:

6827

* @exp: the expression

6828

*

6829

* Increase the reference count of the expression

6830

*/

6831

void

6832

xmlExpRef(xmlExpNodePtr exp) {

6833

if (exp != NULL)

6834

exp->ref++;

6835

}

6836

6837

/**

6838

* xmlExpNewAtom:

6839

* @ctxt: the expression context

6840

* @name: the atom name

6841

* @len: the atom name length in byte (or -1);

6842

*

6843

* Get the atom associated to this name from that context

6844

*

6845

* Returns the node or NULL in case of error

6846

*/

6847

xmlExpNodePtr

6848

xmlExpNewAtom(xmlExpCtxtPtr ctxt, const xmlChar *name, int len) {

6849

if ((ctxt == NULL) || (name == NULL))

6850

return(NULL);

6851

name = xmlDictLookup(ctxt->dict, name, len);

6852

if (name == NULL)

6853

return(NULL);

6854

return(xmlExpHashGetEntry(ctxt, XML_EXP_ATOM, NULL, NULL, name, 0, 0));

6855

}

6856

6857

/**

6858

* xmlExpNewOr:

6859

* @ctxt: the expression context

6860

* @left: left expression

6861

* @right: right expression

6862

*

6863

* Get the atom associated to the choice @left | @right

6864

* Note that @left and @right are consumed in the operation, to keep

6865

* an handle on them use xmlExpRef() and use xmlExpFree() to release them,

6866

* this is true even in case of failure (unless ctxt == NULL).

6867

*

6868

* Returns the node or NULL in case of error

6869

*/

6870

xmlExpNodePtr

6871

xmlExpNewOr(xmlExpCtxtPtr ctxt, xmlExpNodePtr left, xmlExpNodePtr right) {

6872

if (ctxt == NULL)

6873

return(NULL);

6874

if ((left == NULL) || (right == NULL)) {

6875

xmlExpFree(ctxt, left);

6876

xmlExpFree(ctxt, right);

6877

return(NULL);

6878

}

6879

return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, left, right, NULL, 0, 0));

6880

}

6881

6882

/**

6883

* xmlExpNewSeq:

6884

* @ctxt: the expression context

6885

* @left: left expression

6886

* @right: right expression

6887

*

6888

* Get the atom associated to the sequence @left , @right

6889

* Note that @left and @right are consumed in the operation, to keep

6890

* an handle on them use xmlExpRef() and use xmlExpFree() to release them,

6891

* this is true even in case of failure (unless ctxt == NULL).

6892

*

6893

* Returns the node or NULL in case of error

6894

*/

6895

xmlExpNodePtr

6896

xmlExpNewSeq(xmlExpCtxtPtr ctxt, xmlExpNodePtr left, xmlExpNodePtr right) {

6897

if (ctxt == NULL)

6898

return(NULL);

6899

if ((left == NULL) || (right == NULL)) {

6900

xmlExpFree(ctxt, left);

6901

xmlExpFree(ctxt, right);

6902

return(NULL);

6903

}

6904

return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, left, right, NULL, 0, 0));

6905

}

6906

6907

/**

6908

* xmlExpNewRange:

6909

* @ctxt: the expression context

6910

* @subset: the expression to be repeated

6911

* @min: the lower bound for the repetition

6912

* @max: the upper bound for the repetition, -1 means infinite

6913

*

6914

* Get the atom associated to the range (@subset){@min, @max}

6915

* Note that @subset is consumed in the operation, to keep

6916

* an handle on it use xmlExpRef() and use xmlExpFree() to release it,

6917

* this is true even in case of failure (unless ctxt == NULL).

6918

*

6919

* Returns the node or NULL in case of error

6920

*/

6921

xmlExpNodePtr

6922

xmlExpNewRange(xmlExpCtxtPtr ctxt, xmlExpNodePtr subset, int min, int max) {

6923

if (ctxt == NULL)

6924

return(NULL);

6925

if ((subset == NULL) || (min < 0) || (max < -1) ||

6926

((max >= 0) && (min > max))) {

6927

xmlExpFree(ctxt, subset);

6928

return(NULL);

6929

}

6930

return(xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, subset,

6931

NULL, NULL, min, max));

6932

}

6933

6934

/************************************************************************

6935

* *

6936

* Public API for operations on expressions *

6937

* *

6938

************************************************************************/

6939

6940

static int

6941

xmlExpGetLanguageInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,

6942

const xmlChar**list, int len, int nb) {

6943

int tmp, tmp2;

6944

tail:

6945

switch (exp->type) {

6946

case XML_EXP_EMPTY:

6947

return(0);

6948

case XML_EXP_ATOM:

6949

for (tmp = 0;tmp < nb;tmp++)

6950

if (list[tmp] == exp->exp_str)

6951

return(0);

6952

if (nb >= len)

6953

return(-2);

6954

list[nb] = exp->exp_str;

6955

return(1);

6956

case XML_EXP_COUNT:

6957

exp = exp->exp_left;

6958

goto tail;

6959

case XML_EXP_SEQ:

6960

case XML_EXP_OR:

6961

tmp = xmlExpGetLanguageInt(ctxt, exp->exp_left, list, len, nb);

6962

if (tmp < 0)

6963

return(tmp);

6964

tmp2 = xmlExpGetLanguageInt(ctxt, exp->exp_right, list, len,

6965

nb + tmp);

6966

if (tmp2 < 0)

6967

return(tmp2);

6968

return(tmp + tmp2);

6969

}

6970

return(-1);

6971

}

6972

6973

/**

6974

* xmlExpGetLanguage:

6975

* @ctxt: the expression context

6976

* @exp: the expression

6977

* @langList: where to store the tokens

6978

* @len: the allocated length of @list

6979

*

6980

* Find all the strings used in @exp and store them in @list

6981

*

6982

* Returns the number of unique strings found, -1 in case of errors and

6983

* -2 if there is more than @len strings

6984

*/

6985

int

6986

xmlExpGetLanguage(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,

6987

const xmlChar**langList, int len) {

6988

if ((ctxt == NULL) || (exp == NULL) || (langList == NULL) || (len <= 0))

6989

return(-1);

6990

return(xmlExpGetLanguageInt(ctxt, exp, langList, len, 0));

6991

}

6992

6993

static int

6994

xmlExpGetStartInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,

6995

const xmlChar**list, int len, int nb) {

6996

int tmp, tmp2;

6997

tail:

6998

switch (exp->type) {

6999

case XML_EXP_FORBID:

7000

return(0);

7001

case XML_EXP_EMPTY:

7002

return(0);

7003

case XML_EXP_ATOM:

7004

for (tmp = 0;tmp < nb;tmp++)

7005

if (list[tmp] == exp->exp_str)

7006

return(0);

7007

if (nb >= len)

7008

return(-2);

7009

list[nb] = exp->exp_str;

7010

return(1);

7011

case XML_EXP_COUNT:

7012

exp = exp->exp_left;

7013

goto tail;

7014

case XML_EXP_SEQ:

7015

tmp = xmlExpGetStartInt(ctxt, exp->exp_left, list, len, nb);

7016

if (tmp < 0)

7017

return(tmp);

7018

if (IS_NILLABLE(exp->exp_left)) {

7019

tmp2 = xmlExpGetStartInt(ctxt, exp->exp_right, list, len,

7020

nb + tmp);

7021

if (tmp2 < 0)

7022

return(tmp2);

7023

tmp += tmp2;

7024

}

7025

return(tmp);

7026

case XML_EXP_OR:

7027

tmp = xmlExpGetStartInt(ctxt, exp->exp_left, list, len, nb);

7028

if (tmp < 0)

7029

return(tmp);

7030

tmp2 = xmlExpGetStartInt(ctxt, exp->exp_right, list, len,

7031

nb + tmp);

7032

if (tmp2 < 0)

7033

return(tmp2);

7034

return(tmp + tmp2);

7035

}

7036

return(-1);

7037

}

7038

7039

/**

7040

* xmlExpGetStart:

7041

* @ctxt: the expression context

7042

* @exp: the expression

7043

* @tokList: where to store the tokens

7044

* @len: the allocated length of @list

7045

*

7046

* Find all the strings that appears at the start of the languages

7047

* accepted by @exp and store them in @list. E.g. for (a, b) | c

7048

* it will return the list [a, c]

7049

*

7050

* Returns the number of unique strings found, -1 in case of errors and

7051

* -2 if there is more than @len strings

7052

*/

7053

int

7054

xmlExpGetStart(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,

7055

const xmlChar**tokList, int len) {

7056

if ((ctxt == NULL) || (exp == NULL) || (tokList == NULL) || (len <= 0))

7057

return(-1);

7058

return(xmlExpGetStartInt(ctxt, exp, tokList, len, 0));

7059

}

7060

7061

/**

7062

* xmlExpIsNillable:

7063

* @exp: the expression

7064

*

7065

* Finds if the expression is nillable, i.e. if it accepts the empty sequqnce

7066

*

7067

* Returns 1 if nillable, 0 if not and -1 in case of error

7068

*/

7069

int

7070

xmlExpIsNillable(xmlExpNodePtr exp) {

7071

if (exp == NULL)

7072

return(-1);

7073

return(IS_NILLABLE(exp) != 0);

7074

}

7075

7076

static xmlExpNodePtr

7077

xmlExpStringDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar *str)

7078

{

7079

xmlExpNodePtr ret;

7080

7081

switch (exp->type) {

7082

case XML_EXP_EMPTY:

7083

return(forbiddenExp);

7084

case XML_EXP_FORBID:

7085

return(forbiddenExp);

7086

case XML_EXP_ATOM:

7087

if (exp->exp_str == str) {

7088

#ifdef DEBUG_DERIV

7089

printf("deriv atom: equal => Empty\n");

7090

#endif

7091

ret = emptyExp;

7092

} else {

7093

#ifdef DEBUG_DERIV

7094

printf("deriv atom: mismatch => forbid\n");

7095

#endif

7096

/* TODO wildcards here */

7097

ret = forbiddenExp;

7098

}

7099

return(ret);

7100

case XML_EXP_OR: {

7101

xmlExpNodePtr tmp;

7102

7103

#ifdef DEBUG_DERIV

7104

printf("deriv or: => or(derivs)\n");

7105

#endif

7106

tmp = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);

7107

if (tmp == NULL) {

7108

return(NULL);

7109

}

7110

ret = xmlExpStringDeriveInt(ctxt, exp->exp_right, str);

7111

if (ret == NULL) {

7112

xmlExpFree(ctxt, tmp);

7113

return(NULL);

7114

}

7115

ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, tmp, ret,

7116

NULL, 0, 0);

7117

return(ret);

7118

}

7119

case XML_EXP_SEQ:

7120

#ifdef DEBUG_DERIV

7121

printf("deriv seq: starting with left\n");

7122

#endif

7123

ret = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);

7124

if (ret == NULL) {

7125

return(NULL);

7126

} else if (ret == forbiddenExp) {

7127

if (IS_NILLABLE(exp->exp_left)) {

7128

#ifdef DEBUG_DERIV

7129

printf("deriv seq: left failed but nillable\n");

7130

#endif

7131

ret = xmlExpStringDeriveInt(ctxt, exp->exp_right, str);

7132

}

7133

} else {

7134

#ifdef DEBUG_DERIV

7135

printf("deriv seq: left match => sequence\n");

7136

#endif

7137

exp->exp_right->ref++;

7138

ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, exp->exp_right,

7139

NULL, 0, 0);

7140

}

7141

return(ret);

7142

case XML_EXP_COUNT: {

7143

int min, max;

7144

xmlExpNodePtr tmp;

7145

7146

if (exp->exp_max == 0)

7147

return(forbiddenExp);

7148

ret = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);

7149

if (ret == NULL)

7150

return(NULL);

7151

if (ret == forbiddenExp) {

7152

#ifdef DEBUG_DERIV

7153

printf("deriv count: pattern mismatch => forbid\n");

7154

#endif

7155

return(ret);

7156

}

7157

if (exp->exp_max == 1)

7158

return(ret);

7159

if (exp->exp_max < 0) /* unbounded */

7160

max = -1;

7161

else

7162

max = exp->exp_max - 1;

7163

if (exp->exp_min > 0)

7164

min = exp->exp_min - 1;

7165

else

7166

min = 0;

7167

exp->exp_left->ref++;

7168

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left, NULL,

7169

NULL, min, max);

7170

if (ret == emptyExp) {

7171

#ifdef DEBUG_DERIV

7172

printf("deriv count: match to empty => new count\n");

7173

#endif

7174

return(tmp);

7175

}

7176

#ifdef DEBUG_DERIV

7177

printf("deriv count: match => sequence with new count\n");

7178

#endif

7179

return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, tmp,

7180

NULL, 0, 0));

7181

}

7182

}

7183

return(NULL);

7184

}

7185

7186

/**

7187

* xmlExpStringDerive:

7188

* @ctxt: the expression context

7189

* @exp: the expression

7190

* @str: the string

7191

* @len: the string len in bytes if available

7192

*

7193

* Do one step of Brzozowski derivation of the expression @exp with

7194

* respect to the input string

7195

*

7196

* Returns the resulting expression or NULL in case of internal error

7197

*/

7198

xmlExpNodePtr

7199

xmlExpStringDerive(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,

7200

const xmlChar *str, int len) {

7201

const xmlChar *input;

7202

7203

if ((exp == NULL) || (ctxt == NULL) || (str == NULL)) {

7204

return(NULL);

7205

}

7206

/*

7207

* check the string is in the dictionnary, if yes use an interned

7208

* copy, otherwise we know it's not an acceptable input

7209

*/

7210

input = xmlDictExists(ctxt->dict, str, len);

7211

if (input == NULL) {

7212

return(forbiddenExp);

7213

}

7214

return(xmlExpStringDeriveInt(ctxt, exp, input));

7215

}

7216

7217

static int

7218

xmlExpCheckCard(xmlExpNodePtr exp, xmlExpNodePtr sub) {

7219

int ret = 1;

7220

7221

if (sub->c_max == -1) {

7222

if (exp->c_max != -1)

7223

ret = 0;

7224

} else if ((exp->c_max >= 0) && (exp->c_max < sub->c_max)) {

7225

ret = 0;

7226

}

7227

#if 0

7228

if ((IS_NILLABLE(sub)) && (!IS_NILLABLE(exp)))

7229

ret = 0;

7230

#endif

7231

return(ret);

7232

}

7233

7234

static xmlExpNodePtr xmlExpExpDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,

7235

xmlExpNodePtr sub);

7236

/**

7237

* xmlExpDivide:

7238

* @ctxt: the expressions context

7239

* @exp: the englobing expression

7240

* @sub: the subexpression

7241

* @mult: the multiple expression

7242

* @remain: the remain from the derivation of the multiple

7243

*

7244

* Check if exp is a multiple of sub, i.e. if there is a finite number n

7245

* so that sub{n} subsume exp

7246

*

7247

* Returns the multiple value if successful, 0 if it is not a multiple

7248

* and -1 in case of internel error.

7249

*/

7250

7251

static int

7252

xmlExpDivide(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub,

7253

xmlExpNodePtr *mult, xmlExpNodePtr *remain) {

7254

int i;

7255

xmlExpNodePtr tmp, tmp2;

7256

7257

if (mult != NULL) *mult = NULL;

7258

if (remain != NULL) *remain = NULL;

7259

if (exp->c_max == -1) return(0);

7260

if (IS_NILLABLE(exp) && (!IS_NILLABLE(sub))) return(0);

7261

7262

for (i = 1;i <= exp->c_max;i++) {

7263

sub->ref++;

7264

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT,

7265

sub, NULL, NULL, i, i);

7266

if (tmp == NULL) {

7267

return(-1);

7268

}

7269

if (!xmlExpCheckCard(tmp, exp)) {

7270

xmlExpFree(ctxt, tmp);

7271

continue;

7272

}

7273

tmp2 = xmlExpExpDeriveInt(ctxt, tmp, exp);

7274

if (tmp2 == NULL) {

7275

xmlExpFree(ctxt, tmp);

7276

return(-1);

7277

}

7278

if ((tmp2 != forbiddenExp) && (IS_NILLABLE(tmp2))) {

7279

if (remain != NULL)

7280

*remain = tmp2;

7281

else

7282

xmlExpFree(ctxt, tmp2);

7283

if (mult != NULL)

7284

*mult = tmp;

7285

else

7286

xmlExpFree(ctxt, tmp);

7287

#ifdef DEBUG_DERIV

7288

printf("Divide succeeded %d\n", i);

7289

#endif

7290

return(i);

7291

}

7292

xmlExpFree(ctxt, tmp);

7293

xmlExpFree(ctxt, tmp2);

7294

}

7295

#ifdef DEBUG_DERIV

7296

printf("Divide failed\n");

7297

#endif

7298

return(0);

7299

}

7300

7301

/**

7302

* xmlExpExpDeriveInt:

7303

* @ctxt: the expressions context

7304

* @exp: the englobing expression

7305

* @sub: the subexpression

7306

*

7307

* Try to do a step of Brzozowski derivation but at a higher level

7308

* the input being a subexpression.

7309

*

7310

* Returns the resulting expression or NULL in case of internal error

7311

*/

7312

static xmlExpNodePtr

7313

xmlExpExpDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {

7314

xmlExpNodePtr ret, tmp, tmp2, tmp3;

7315

const xmlChar **tab;

7316

int len, i;

7317

7318

/*

7319

* In case of equality and if the expression can only consume a finite

7320

* amount, then the derivation is empty

7321

*/

7322

if ((exp == sub) && (exp->c_max >= 0)) {

7323

#ifdef DEBUG_DERIV

7324

printf("Equal(exp, sub) and finite -> Empty\n");

7325

#endif

7326

return(emptyExp);

7327

}

7328

/*

7329

* decompose sub sequence first

7330

*/

7331

if (sub->type == XML_EXP_EMPTY) {

7332

#ifdef DEBUG_DERIV

7333

printf("Empty(sub) -> Empty\n");

7334

#endif

7335

exp->ref++;

7336

return(exp);

7337

}

7338

if (sub->type == XML_EXP_SEQ) {

7339

#ifdef DEBUG_DERIV

7340

printf("Seq(sub) -> decompose\n");

7341

#endif

7342

tmp = xmlExpExpDeriveInt(ctxt, exp, sub->exp_left);

7343

if (tmp == NULL)

7344

return(NULL);

7345

if (tmp == forbiddenExp)

7346

return(tmp);

7347

ret = xmlExpExpDeriveInt(ctxt, tmp, sub->exp_right);

7348

xmlExpFree(ctxt, tmp);

7349

return(ret);

7350

}

7351

if (sub->type == XML_EXP_OR) {

7352

#ifdef DEBUG_DERIV

7353

printf("Or(sub) -> decompose\n");

7354

#endif

7355

tmp = xmlExpExpDeriveInt(ctxt, exp, sub->exp_left);

7356

if (tmp == forbiddenExp)

7357

return(tmp);

7358

if (tmp == NULL)

7359

return(NULL);

7360

ret = xmlExpExpDeriveInt(ctxt, exp, sub->exp_right);

7361

if ((ret == NULL) || (ret == forbiddenExp)) {

7362

xmlExpFree(ctxt, tmp);

7363

return(ret);

7364

}

7365

return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, tmp, ret, NULL, 0, 0));

7366

}

7367

if (!xmlExpCheckCard(exp, sub)) {

7368

#ifdef DEBUG_DERIV

7369

printf("CheckCard(exp, sub) failed -> Forbid\n");

7370

#endif

7371

return(forbiddenExp);

7372

}

7373

switch (exp->type) {

7374

case XML_EXP_EMPTY:

7375

if (sub == emptyExp)

7376

return(emptyExp);

7377

#ifdef DEBUG_DERIV

7378

printf("Empty(exp) -> Forbid\n");

7379

#endif

7380

return(forbiddenExp);

7381

case XML_EXP_FORBID:

7382

#ifdef DEBUG_DERIV

7383

printf("Forbid(exp) -> Forbid\n");

7384

#endif

7385

return(forbiddenExp);

7386

case XML_EXP_ATOM:

7387

if (sub->type == XML_EXP_ATOM) {

7388

/* TODO: handle wildcards */

7389

if (exp->exp_str == sub->exp_str) {

7390

#ifdef DEBUG_DERIV

7391

printf("Atom match -> Empty\n");

7392

#endif

7393

return(emptyExp);

7394

}

7395

#ifdef DEBUG_DERIV

7396

printf("Atom mismatch -> Forbid\n");

7397

#endif

7398

return(forbiddenExp);

7399

}

7400

if ((sub->type == XML_EXP_COUNT) &&

7401

(sub->exp_max == 1) &&

7402

(sub->exp_left->type == XML_EXP_ATOM)) {

7403

/* TODO: handle wildcards */

7404

if (exp->exp_str == sub->exp_left->exp_str) {

7405

#ifdef DEBUG_DERIV

7406

printf("Atom match -> Empty\n");

7407

#endif

7408

return(emptyExp);

7409

}

7410

#ifdef DEBUG_DERIV

7411

printf("Atom mismatch -> Forbid\n");

7412

#endif

7413

return(forbiddenExp);

7414

}

7415

#ifdef DEBUG_DERIV

7416

printf("Compex exp vs Atom -> Forbid\n");

7417

#endif

7418

return(forbiddenExp);

7419

case XML_EXP_SEQ:

7420

/* try to get the sequence consumed only if possible */

7421

if (xmlExpCheckCard(exp->exp_left, sub)) {

7422

/* See if the sequence can be consumed directly */

7423

#ifdef DEBUG_DERIV

7424

printf("Seq trying left only\n");

7425

#endif

7426

ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);

7427

if ((ret != forbiddenExp) && (ret != NULL)) {

7428

#ifdef DEBUG_DERIV

7429

printf("Seq trying left only worked\n");

7430

#endif

7431

/*

7432

* TODO: assumption here that we are determinist

7433

* i.e. we won't get to a nillable exp left

7434

* subset which could be matched by the right

7435

* part too.

7436

* e.g.: (a | b)+,(a | c) and 'a+,a'

7437

*/

7438

exp->exp_right->ref++;

7439

return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret,

7440

exp->exp_right, NULL, 0, 0));

7441

}

7442

#ifdef DEBUG_DERIV

7443

} else {

7444

printf("Seq: left too short\n");

7445

#endif

7446

}

7447

/* Try instead to decompose */

7448

if (sub->type == XML_EXP_COUNT) {

7449

int min, max;

7450

7451

#ifdef DEBUG_DERIV

7452

printf("Seq: sub is a count\n");

7453

#endif

7454

ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub->exp_left);

7455

if (ret == NULL)

7456

return(NULL);

7457

if (ret != forbiddenExp) {

7458

#ifdef DEBUG_DERIV

7459

printf("Seq , Count match on left\n");

7460

#endif

7461

if (sub->exp_max < 0)

7462

max = -1;

7463

else

7464

max = sub->exp_max -1;

7465

if (sub->exp_min > 0)

7466

min = sub->exp_min -1;

7467

else

7468

min = 0;

7469

exp->exp_right->ref++;

7470

tmp = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret,

7471

exp->exp_right, NULL, 0, 0);

7472

if (tmp == NULL)

7473

return(NULL);

7474

7475

sub->exp_left->ref++;

7476

tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT,

7477

sub->exp_left, NULL, NULL, min, max);

7478

if (tmp2 == NULL) {

7479

xmlExpFree(ctxt, tmp);

7480

return(NULL);

7481

}

7482

ret = xmlExpExpDeriveInt(ctxt, tmp, tmp2);

7483

xmlExpFree(ctxt, tmp);

7484

xmlExpFree(ctxt, tmp2);

7485

return(ret);

7486

}

7487

}

7488

/* we made no progress on structured operations */

7489

break;

7490

case XML_EXP_OR:

7491

#ifdef DEBUG_DERIV

7492

printf("Or , trying both side\n");

7493

#endif

7494

ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);

7495

if (ret == NULL)

7496

return(NULL);

7497

tmp = xmlExpExpDeriveInt(ctxt, exp->exp_right, sub);

7498

if (tmp == NULL) {

7499

xmlExpFree(ctxt, ret);

7500

return(NULL);

7501

}

7502

return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, tmp, NULL, 0, 0));

7503

case XML_EXP_COUNT: {

7504

int min, max;

7505

7506

if (sub->type == XML_EXP_COUNT) {

7507

/*

7508

* Try to see if the loop is completely subsumed

7509

*/

7510

tmp = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub->exp_left);

7511

if (tmp == NULL)

7512

return(NULL);

7513

if (tmp == forbiddenExp) {

7514

int mult;

7515

7516

#ifdef DEBUG_DERIV

7517

printf("Count, Count inner don't subsume\n");

7518

#endif

7519

mult = xmlExpDivide(ctxt, sub->exp_left, exp->exp_left,

7520

NULL, &tmp);

7521

if (mult <= 0) {

7522

#ifdef DEBUG_DERIV

7523

printf("Count, Count not multiple => forbidden\n");

7524

#endif

7525

return(forbiddenExp);

7526

}

7527

if (sub->exp_max == -1) {

7528

max = -1;

7529

if (exp->exp_max == -1) {

7530

if (exp->exp_min <= sub->exp_min * mult)

7531

min = 0;

7532

else

7533

min = exp->exp_min - sub->exp_min * mult;

7534

} else {

7535

#ifdef DEBUG_DERIV

7536

printf("Count, Count finite can't subsume infinite\n");

7537

#endif

7538

xmlExpFree(ctxt, tmp);

7539

return(forbiddenExp);

7540

}

7541

} else {

7542

if (exp->exp_max == -1) {

7543

#ifdef DEBUG_DERIV

7544

printf("Infinite loop consume mult finite loop\n");

7545

#endif

7546

if (exp->exp_min > sub->exp_min * mult) {

7547

max = -1;

7548

min = exp->exp_min - sub->exp_min * mult;

7549

} else {

7550

max = -1;

7551

min = 0;

7552

}

7553

} else {

7554

if (exp->exp_max < sub->exp_max * mult) {

7555

#ifdef DEBUG_DERIV

7556

printf("loops max mult mismatch => forbidden\n");

7557

#endif

7558

xmlExpFree(ctxt, tmp);

7559

return(forbiddenExp);

7560

}

7561

if (sub->exp_max * mult > exp->exp_min)

7562

min = 0;

7563

else

7564

min = exp->exp_min - sub->exp_max * mult;

7565

max = exp->exp_max - sub->exp_max * mult;

7566

}

7567

}

7568

} else if (!IS_NILLABLE(tmp)) {

7569

/*

7570

* TODO: loop here to try to grow if working on finite

7571

* blocks.

7572

*/

7573

#ifdef DEBUG_DERIV

7574

printf("Count, Count remain not nillable => forbidden\n");

7575

#endif

7576

xmlExpFree(ctxt, tmp);

7577

return(forbiddenExp);

7578

} else if (sub->exp_max == -1) {

7579

if (exp->exp_max == -1) {

7580

if (exp->exp_min <= sub->exp_min) {

7581

#ifdef DEBUG_DERIV

7582

printf("Infinite loops Okay => COUNT(0,Inf)\n");

7583

#endif

7584

max = -1;

7585

min = 0;

7586

} else {

7587

#ifdef DEBUG_DERIV

7588

printf("Infinite loops min => Count(X,Inf)\n");

7589

#endif

7590

max = -1;

7591

min = exp->exp_min - sub->exp_min;

7592

}

7593

} else if (exp->exp_min > sub->exp_min) {

7594

#ifdef DEBUG_DERIV

7595

printf("loops min mismatch 1 => forbidden ???\n");

7596

#endif

7597

xmlExpFree(ctxt, tmp);

7598

return(forbiddenExp);

7599

} else {

7600

max = -1;

7601

min = 0;

7602

}

7603

} else {

7604

if (exp->exp_max == -1) {

7605

#ifdef DEBUG_DERIV

7606

printf("Infinite loop consume finite loop\n");

7607

#endif

7608

if (exp->exp_min > sub->exp_min) {

7609

max = -1;

7610

min = exp->exp_min - sub->exp_min;

7611

} else {

7612

max = -1;

7613

min = 0;

7614

}

7615

} else {

7616

if (exp->exp_max < sub->exp_max) {

7617

#ifdef DEBUG_DERIV

7618

printf("loops max mismatch => forbidden\n");

7619

#endif

7620

xmlExpFree(ctxt, tmp);

7621

return(forbiddenExp);

7622

}

7623

if (sub->exp_max > exp->exp_min)

7624

min = 0;

7625

else

7626

min = exp->exp_min - sub->exp_max;

7627

max = exp->exp_max - sub->exp_max;

7628

}

7629

}

7630

#ifdef DEBUG_DERIV

7631

printf("loops match => SEQ(COUNT())\n");

7632

#endif

7633

exp->exp_left->ref++;

7634

tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left,

7635

NULL, NULL, min, max);

7636

if (tmp2 == NULL) {

7637

return(NULL);

7638

}

7639

ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, tmp, tmp2,

7640

NULL, 0, 0);

7641

return(ret);

7642

}

7643

tmp = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);

7644

if (tmp == NULL)

7645

return(NULL);

7646

if (tmp == forbiddenExp) {

7647

#ifdef DEBUG_DERIV

7648

printf("loop mismatch => forbidden\n");

7649

#endif

7650

return(forbiddenExp);

7651

}

7652

if (exp->exp_min > 0)

7653

min = exp->exp_min - 1;

7654

else

7655

min = 0;

7656

if (exp->exp_max < 0)

7657

max = -1;

7658

else

7659

max = exp->exp_max - 1;

7660

7661

#ifdef DEBUG_DERIV

7662

printf("loop match => SEQ(COUNT())\n");

7663

#endif

7664

exp->exp_left->ref++;

7665

tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left,

7666

NULL, NULL, min, max);

7667

if (tmp2 == NULL)

7668

return(NULL);

7669

ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, tmp, tmp2,

7670

NULL, 0, 0);

7671

return(ret);

7672

}

7673

}

7674

7675

#ifdef DEBUG_DERIV

7676

printf("Fallback to derivative\n");

7677

#endif

7678

if (IS_NILLABLE(sub)) {

7679

if (!(IS_NILLABLE(exp)))

7680

return(forbiddenExp);

7681

else

7682

ret = emptyExp;

7683

} else

7684

ret = NULL;

7685

/*

7686

* here the structured derivation made no progress so

7687

* we use the default token based derivation to force one more step

7688

*/

7689

if (ctxt->tabSize == 0)

7690

ctxt->tabSize = 40;

7691

7692

tab = (const xmlChar **) xmlMalloc(ctxt->tabSize *

7693

sizeof(const xmlChar *));

7694

if (tab == NULL) {

7695

return(NULL);

7696

}

7697

7698

/*

7699

* collect all the strings accepted by the subexpression on input

7700

*/

7701

len = xmlExpGetStartInt(ctxt, sub, tab, ctxt->tabSize, 0);

7702

while (len < 0) {

7703

const xmlChar **temp;

7704

temp = (const xmlChar **) xmlRealloc((xmlChar **) tab, ctxt->tabSize * 2 *

7705

sizeof(const xmlChar *));

7706

if (temp == NULL) {

7707

xmlFree((xmlChar **) tab);

7708

return(NULL);

7709

}

7710

tab = temp;

7711

ctxt->tabSize *= 2;

7712

len = xmlExpGetStartInt(ctxt, sub, tab, ctxt->tabSize, 0);

7713

}

7714

for (i = 0;i < len;i++) {

7715

tmp = xmlExpStringDeriveInt(ctxt, exp, tab[i]);

7716

if ((tmp == NULL) || (tmp == forbiddenExp)) {

7717

xmlExpFree(ctxt, ret);

7718

xmlFree((xmlChar **) tab);

7719

return(tmp);

7720

}

7721

tmp2 = xmlExpStringDeriveInt(ctxt, sub, tab[i]);

7722

if ((tmp2 == NULL) || (tmp2 == forbiddenExp)) {

7723

xmlExpFree(ctxt, tmp);

7724

xmlExpFree(ctxt, ret);

7725

xmlFree((xmlChar **) tab);

7726

return(tmp);

7727

}

7728

tmp3 = xmlExpExpDeriveInt(ctxt, tmp, tmp2);

7729

xmlExpFree(ctxt, tmp);

7730

xmlExpFree(ctxt, tmp2);

7731

7732

if ((tmp3 == NULL) || (tmp3 == forbiddenExp)) {

7733

xmlExpFree(ctxt, ret);

7734

xmlFree((xmlChar **) tab);

7735

return(tmp3);

7736

}

7737

7738

if (ret == NULL)

7739

ret = tmp3;

7740

else {

7741

ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, tmp3, NULL, 0, 0);

7742

if (ret == NULL) {

7743

xmlFree((xmlChar **) tab);

7744

return(NULL);

7745

}

7746

}

7747

}

7748

xmlFree((xmlChar **) tab);

7749

return(ret);

7750

}

7751

7752

/**

7753

* xmlExpExpDerive:

7754

* @ctxt: the expressions context

7755

* @exp: the englobing expression

7756

* @sub: the subexpression

7757

*

7758

* Evaluates the expression resulting from @exp consuming a sub expression @sub

7759

* Based on algebraic derivation and sometimes direct Brzozowski derivation

7760

* it usually tatkes less than linear time and can handle expressions generating

7761

* infinite languages.

7762

*

7763

* Returns the resulting expression or NULL in case of internal error, the

7764

* result must be freed

7765

*/

7766

xmlExpNodePtr

7767

xmlExpExpDerive(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {

7768

if ((exp == NULL) || (ctxt == NULL) || (sub == NULL))

7769

return(NULL);

7770

7771

/*

7772

* O(1) speedups

7773

*/

7774

if (IS_NILLABLE(sub) && (!IS_NILLABLE(exp))) {

7775

#ifdef DEBUG_DERIV

7776

printf("Sub nillable and not exp : can't subsume\n");

7777

#endif

7778

return(forbiddenExp);

7779

}

7780

if (xmlExpCheckCard(exp, sub) == 0) {

7781

#ifdef DEBUG_DERIV

7782

printf("sub generate longuer sequances than exp : can't subsume\n");

7783

#endif

7784

return(forbiddenExp);

7785

}

7786

return(xmlExpExpDeriveInt(ctxt, exp, sub));

7787

}

7788

7789

/**

7790

* xmlExpSubsume:

7791

* @ctxt: the expressions context

7792

* @exp: the englobing expression

7793

* @sub: the subexpression

7794

*

7795

* Check whether @exp accepts all the languages accexpted by @sub

7796

* the input being a subexpression.

7797

*

7798

* Returns 1 if true 0 if false and -1 in case of failure.

7799

*/

7800

int

7801

xmlExpSubsume(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {

7802

xmlExpNodePtr tmp;

7803

7804

if ((exp == NULL) || (ctxt == NULL) || (sub == NULL))

7805

return(-1);

7806

7807

/*

7808

* TODO: speedup by checking the language of sub is a subset of the

7809

* language of exp

7810

*/

7811

/*

7812

* O(1) speedups

7813

*/

7814

if (IS_NILLABLE(sub) && (!IS_NILLABLE(exp))) {

7815

#ifdef DEBUG_DERIV

7816

printf("Sub nillable and not exp : can't subsume\n");

7817

#endif

7818

return(0);

7819

}

7820

if (xmlExpCheckCard(exp, sub) == 0) {

7821

#ifdef DEBUG_DERIV

7822

printf("sub generate longuer sequances than exp : can't subsume\n");

7823

#endif

7824

return(0);

7825

}

7826

tmp = xmlExpExpDeriveInt(ctxt, exp, sub);

7827

#ifdef DEBUG_DERIV

7828

printf("Result derivation :\n");

7829

PRINT_EXP(tmp);

7830

#endif

7831

if (tmp == NULL)

7832

return(-1);

7833

if (tmp == forbiddenExp)

7834

return(0);

7835

if (tmp == emptyExp)

7836

return(1);

7837

if ((tmp != NULL) && (IS_NILLABLE(tmp))) {

7838

xmlExpFree(ctxt, tmp);

7839

return(1);

7840

}

7841

xmlExpFree(ctxt, tmp);

7842

return(0);

7843

}

7844

7845

/************************************************************************

7846

* *

7847

* Parsing expression *

7848

* *

7849

************************************************************************/

7850

7851

static xmlExpNodePtr xmlExpParseExpr(xmlExpCtxtPtr ctxt);

7852

7853

#undef CUR

7854

#define CUR (*ctxt->cur)

7855

#undef NEXT

7856

#define NEXT ctxt->cur++;

7857

#undef IS_BLANK

7858

#define IS_BLANK(c) ((c == ' ') || (c == '\n') || (c == '\r') || (c == '\t'))

7859

#define SKIP_BLANKS while (IS_BLANK(*ctxt->cur)) ctxt->cur++;

7860

7861

static int

7862

xmlExpParseNumber(xmlExpCtxtPtr ctxt) {

7863

int ret = 0;

7864

7865

SKIP_BLANKS

7866

if (CUR == '*') {

7867

return(-1);

7869

}

7870

if ((CUR < '0') || (CUR > '9'))

7871

return(-1);

7872

while ((CUR >= '0') && (CUR <= '9')) {

7873

ret = ret * 10 + (CUR - '0');

7874

}

7876

return(ret);

7877

}

7878

7879

static xmlExpNodePtr

7880

xmlExpParseOr(xmlExpCtxtPtr ctxt) {

7881

const char *base;

7882

xmlExpNodePtr ret;

7883

const xmlChar *val;

7884

7885

SKIP_BLANKS

7886

base = ctxt->cur;

7887

if (*ctxt->cur == '(') {

7888

ret = xmlExpParseExpr(ctxt);

7890

SKIP_BLANKS

7891

if (*ctxt->cur != ')') {

7892

fprintf(stderr, "unbalanced '(' : %s\n", base);

7893

xmlExpFree(ctxt, ret);

7894

return(NULL);

7895

}

7896

NEXT;

7897

SKIP_BLANKS

7898

goto parse_quantifier;

7899

}

7900

while ((CUR != 0) && (!(IS_BLANK(CUR))) && (CUR != '(') &&

7901

(CUR != ')') && (CUR != '|') && (CUR != ',') && (CUR != '{') &&

7902

(CUR != '*') && (CUR != '+') && (CUR != '?') && (CUR != '}'))

7903

NEXT;

7904

val = xmlDictLookup(ctxt->dict, BAD_CAST base, ctxt->cur - base);

7905

if (val == NULL)

7906

return(NULL);

7907

ret = xmlExpHashGetEntry(ctxt, XML_EXP_ATOM, NULL, NULL, val, 0, 0);

7908

if (ret == NULL)

7909

return(NULL);

7910

SKIP_BLANKS

7911

parse_quantifier:

7912

if (CUR == '{') {

7913

int min, max;

7914

7915

min = xmlExpParseNumber(ctxt);

7917

if (min < 0) {

7918

xmlExpFree(ctxt, ret);

7919

return(NULL);

7920

}

7921

SKIP_BLANKS

7922

if (CUR == ',') {

7923

max = xmlExpParseNumber(ctxt);

7925

SKIP_BLANKS

7926

} else

7927

max = min;

7928

if (CUR != '}') {

7929

xmlExpFree(ctxt, ret);

7930

return(NULL);

7931

}

7932

ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,

7934

min, max);

7935

SKIP_BLANKS

7936

} else if (CUR == '?') {

7937

ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,

7939

0, 1);

7940

SKIP_BLANKS

7941

} else if (CUR == '+') {

7942

ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,

7944

1, -1);

7945

SKIP_BLANKS

7946

} else if (CUR == '*') {

7947

ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,

7949

0, -1);

7950

SKIP_BLANKS

7951

}

7952

return(ret);

7953

}

7954

7955

7956

static xmlExpNodePtr

7957

xmlExpParseSeq(xmlExpCtxtPtr ctxt) {

7958

xmlExpNodePtr ret, right;

7959

7960

ret = xmlExpParseOr(ctxt);

7961

SKIP_BLANKS

7962

while (CUR == '|') {

7963

right = xmlExpParseOr(ctxt);

7965

if (right == NULL) {

7966

xmlExpFree(ctxt, ret);

7967

return(NULL);

7968

}

7969

ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, right, NULL, 0, 0);

7970

if (ret == NULL)

7971

return(NULL);

7972

}

7973

return(ret);

7974

}

7975

7976

static xmlExpNodePtr

7977

xmlExpParseExpr(xmlExpCtxtPtr ctxt) {

7978

xmlExpNodePtr ret, right;

7979

7980

ret = xmlExpParseSeq(ctxt);

7981

SKIP_BLANKS

7982

while (CUR == ',') {

7983

right = xmlExpParseSeq(ctxt);

7985

if (right == NULL) {

7986

xmlExpFree(ctxt, ret);

7987

return(NULL);

7988

}

7989

ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, right, NULL, 0, 0);

7990

if (ret == NULL)

7991

return(NULL);

7992

}

7993

return(ret);

7994

}

7995

7996

/**

7997

* xmlExpParse:

7998

* @ctxt: the expressions context

7999

* @expr: the 0 terminated string

8000

*

8001

* Minimal parser for regexps, it understand the following constructs

8002

* - string terminals

8003

* - choice operator |

8004

* - sequence operator ,

8005

* - subexpressions (...)

8006

* - usual cardinality operators + * and ?

8007

* - finite sequences { min, max }

8008

* - infinite sequences { min, * }

8009

* There is minimal checkings made especially no checking on strings values

8010

*

8011

* Returns a new expression or NULL in case of failure

8012

*/

8013

xmlExpNodePtr

8014

xmlExpParse(xmlExpCtxtPtr ctxt, const char *expr) {

8015

xmlExpNodePtr ret;

8016

8017

ctxt->expr = expr;

8018

ctxt->cur = expr;

8019

8020

ret = xmlExpParseExpr(ctxt);

8021

SKIP_BLANKS

8022

if (*ctxt->cur != 0) {

8023

xmlExpFree(ctxt, ret);

8024

return(NULL);

8025

}

8026

return(ret);

8027

}

8028

8029

static void

8030

xmlExpDumpInt(xmlBufferPtr buf, xmlExpNodePtr expr, int glob) {

8031

xmlExpNodePtr c;

8032

8033

if (expr == NULL) return;

8034

if (glob) xmlBufferWriteChar(buf, "(");

8035

switch (expr->type) {

8036

case XML_EXP_EMPTY:

8037

xmlBufferWriteChar(buf, "empty");

8038

break;

8039

case XML_EXP_FORBID:

8040

xmlBufferWriteChar(buf, "forbidden");

8041

break;

8042

case XML_EXP_ATOM:

8043

xmlBufferWriteCHAR(buf, expr->exp_str);

8044

break;

8045

case XML_EXP_SEQ:

8046

c = expr->exp_left;

8047

if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))

8048

xmlExpDumpInt(buf, c, 1);

8049

else

8050

xmlExpDumpInt(buf, c, 0);

8051

xmlBufferWriteChar(buf, " , ");

8052

c = expr->exp_right;

8053

if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))

8054

xmlExpDumpInt(buf, c, 1);

8055

else

8056

xmlExpDumpInt(buf, c, 0);

8057

break;

8058

case XML_EXP_OR:

8059

c = expr->exp_left;

8060

if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))

8061

xmlExpDumpInt(buf, c, 1);

8062

else

8063

xmlExpDumpInt(buf, c, 0);

8064

xmlBufferWriteChar(buf, " | ");

8065

c = expr->exp_right;

8066

if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))

8067

xmlExpDumpInt(buf, c, 1);

8068

else

8069

xmlExpDumpInt(buf, c, 0);

8070

break;

8071

case XML_EXP_COUNT: {

8072

char rep[40];

8073

8074

c = expr->exp_left;

8075

if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))

8076

xmlExpDumpInt(buf, c, 1);

8077

else

8078

xmlExpDumpInt(buf, c, 0);

8079

if ((expr->exp_min == 0) && (expr->exp_max == 1)) {

8080

rep[0] = '?';

8081

rep[1] = 0;

8082

} else if ((expr->exp_min == 0) && (expr->exp_max == -1)) {

8083

rep[0] = '*';

8084

rep[1] = 0;

8085

} else if ((expr->exp_min == 1) && (expr->exp_max == -1)) {

8086

rep[0] = '+';

8087

rep[1] = 0;

8088

} else if (expr->exp_max == expr->exp_min) {

8089

snprintf(rep, 39, "{%d}", expr->exp_min);

8090

} else if (expr->exp_max < 0) {

8091

snprintf(rep, 39, "{%d,inf}", expr->exp_min);

8092

} else {

8093

snprintf(rep, 39, "{%d,%d}", expr->exp_min, expr->exp_max);

8094

}

8095

rep[39] = 0;

8096

xmlBufferWriteChar(buf, rep);

8097

break;

8098

}

8099

default:

8100

fprintf(stderr, "Error in tree\n");

8101

}

8102

if (glob)

8103

xmlBufferWriteChar(buf, ")");

8104

}

8105

/**

8106

* xmlExpDump:

8107

* @buf: a buffer to receive the output

8108

* @expr: the compiled expression

8109

*

8110

* Serialize the expression as compiled to the buffer

8111

*/

8112

void

8113

xmlExpDump(xmlBufferPtr buf, xmlExpNodePtr expr) {

8114

if ((buf == NULL) || (expr == NULL))

8115

return;

8116

xmlExpDumpInt(buf, expr, 0);

8117

}

8118

8119

/**

8120

* xmlExpMaxToken:

8121

* @expr: a compiled expression

8122

*

8123

* Indicate the maximum number of input a expression can accept

8124

*

8125

* Returns the maximum length or -1 in case of error

8126

*/

8127

int

8128

xmlExpMaxToken(xmlExpNodePtr expr) {

8129

if (expr == NULL)

8130

return(-1);

8131

return(expr->c_max);

8132

}

8133

8134

/**

8135

* xmlExpCtxtNbNodes:

8136

* @ctxt: an expression context

8137

*

8138

* Debugging facility provides the number of allocated nodes at a that point

8139

*

8140

* Returns the number of nodes in use or -1 in case of error

8141

*/

8142

int

8143

xmlExpCtxtNbNodes(xmlExpCtxtPtr ctxt) {

8144

if (ctxt == NULL)

8145

return(-1);

8146

return(ctxt->nb_nodes);

8147

}

8148

8149

/**

8150

* xmlExpCtxtNbCons:

8151

* @ctxt: an expression context

8152

*

8153

* Debugging facility provides the number of allocated nodes over lifetime

8154

*

8155

* Returns the number of nodes ever allocated or -1 in case of error

8156

*/

8157

int

8158

xmlExpCtxtNbCons(xmlExpCtxtPtr ctxt) {

8159

if (ctxt == NULL)

8160

return(-1);

8161

return(ctxt->nb_cons);

8162

}

8163

8164

#endif /* LIBXML_EXPR_ENABLED */

8165

#define bottom_xmlregexp

8166

#include "elfgcchack.h"

8167

#endif /* LIBXML_REGEXP_ENABLED */