Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/regex/_regex

2# Secret Labs' Regular Expression Engine core module

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

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

8# AB (info@pythonware.com).

10# Portions of this engine have been developed in cooperation with

11# CNRI. Hewlett-Packard provided funding for 1.6 integration and

12# other compatibility work.

13#

14# 2010-01-16 mrab Python front-end re-written and extended

16import enum

17import string

18import unicodedata

19from collections import defaultdict

21from regex import _regex

23__all__ = ["A", "ASCII", "B", "BESTMATCH", "D", "DEBUG", "E", "ENHANCEMATCH",

24 "F", "FULLCASE", "I", "IGNORECASE", "L", "LOCALE", "M", "MULTILINE", "P",

25 "POSIX", "R", "REVERSE", "S", "DOTALL", "T", "TEMPLATE", "U", "UNICODE",

26 "V0", "VERSION0", "V1", "VERSION1", "W", "WORD", "X", "VERBOSE", "error",

27 "Scanner", "RegexFlag"]

29# The regex exception.

30class error(Exception):

31 """Exception raised for invalid regular expressions.

33 Attributes:

35 msg: The unformatted error message

36 pattern: The regular expression pattern

37 pos: The position in the pattern where compilation failed, or None

38 lineno: The line number where compilation failed, unless pos is None

39 colno: The column number where compilation failed, unless pos is None

40 """

42 def __init__(self, message, pattern=None, pos=None):

43 newline = '\n' if isinstance(pattern, str) else b'\n'

44 self.msg = message

45 self.pattern = pattern

46 self.pos = pos

47 if pattern is not None and pos is not None:

48 self.lineno = pattern.count(newline, 0, pos) + 1

49 self.colno = pos - pattern.rfind(newline, 0, pos)

51 message = "{} at position {}".format(message, pos)

53 if newline in pattern:

54 message += " (line {}, column {})".format(self.lineno,

55 self.colno)

57 Exception.__init__(self, message)

59# The exception for when a positional flag has been turned on in the old

60# behaviour.

61class _UnscopedFlagSet(Exception):

62 pass

64# The exception for when parsing fails and we want to try something else.

65class ParseError(Exception):

66 pass

68# The exception for when there isn't a valid first set.

69class _FirstSetError(Exception):

70 pass

72# Flags.

73class RegexFlag(enum.IntFlag):

74 A = ASCII = 0x80 # Assume ASCII locale.

75 B = BESTMATCH = 0x1000 # Best fuzzy match.

76 D = DEBUG = 0x200 # Print parsed pattern.

77 E = ENHANCEMATCH = 0x8000 # Attempt to improve the fit after finding the first

78 # fuzzy match.

79 F = FULLCASE = 0x4000 # Unicode full case-folding.

80 I = IGNORECASE = 0x2 # Ignore case.

81 L = LOCALE = 0x4 # Assume current 8-bit locale.

82 M = MULTILINE = 0x8 # Make anchors look for newline.

83 P = POSIX = 0x10000 # POSIX-style matching (leftmost longest).

84 R = REVERSE = 0x400 # Search backwards.

85 S = DOTALL = 0x10 # Make dot match newline.

86 U = UNICODE = 0x20 # Assume Unicode locale.

87 V0 = VERSION0 = 0x2000 # Old legacy behaviour.

88 V1 = VERSION1 = 0x100 # New enhanced behaviour.

89 W = WORD = 0x800 # Default Unicode word breaks.

90 X = VERBOSE = 0x40 # Ignore whitespace and comments.

91 T = TEMPLATE = 0x1 # Template (present because re module has it).

93 def __repr__(self):

94 if self._name_ is not None:

95 return 'regex.%s' % self._name_

97 value = self._value_

98 members = []

99 negative = value < 0

100

101 if negative:

102 value = ~value

103

104 for m in self.__class__:

105 if value & m._value_:

106 value &= ~m._value_

107 members.append('regex.%s' % m._name_)

108

109 if value:

110 members.append(hex(value))

111

112 res = '|'.join(members)

113

114 if negative:

115 if len(members) > 1:

116 res = '~(%s)' % res

117 else:

118 res = '~%s' % res

119

120 return res

121

122 __str__ = object.__str__

123

124# Put the flags into the module namespace. Being explicit here helps tools like

125# linters and IDEs understand the code better.

126ASCII = RegexFlag.ASCII

127BESTMATCH = RegexFlag.BESTMATCH

128DEBUG = RegexFlag.DEBUG

129DOTALL = RegexFlag.DOTALL

130ENHANCEMATCH = RegexFlag.ENHANCEMATCH

131FULLCASE = RegexFlag.FULLCASE

132IGNORECASE = RegexFlag.IGNORECASE

133LOCALE = RegexFlag.LOCALE

134MULTILINE = RegexFlag.MULTILINE

135POSIX = RegexFlag.POSIX

136REVERSE = RegexFlag.REVERSE

137TEMPLATE = RegexFlag.TEMPLATE

138UNICODE = RegexFlag.UNICODE

139VERBOSE = RegexFlag.VERBOSE

140VERSION0 = RegexFlag.VERSION0

141VERSION1 = RegexFlag.VERSION1

142WORD = RegexFlag.WORD

143A = RegexFlag.A

144B = RegexFlag.B

145D = RegexFlag.D

146E = RegexFlag.E

147F = RegexFlag.F

148I = RegexFlag.I

149L = RegexFlag.L

150M = RegexFlag.M

151P = RegexFlag.P

152R = RegexFlag.R

153S = RegexFlag.S

154U = RegexFlag.U

155V0 = RegexFlag.V0

156V1 = RegexFlag.V1

157W = RegexFlag.W

158X = RegexFlag.X

159T = RegexFlag.T

160

161DEFAULT_VERSION = VERSION1

162

163_ALL_VERSIONS = VERSION0 | VERSION1

164_ALL_ENCODINGS = ASCII | LOCALE | UNICODE

165

166# The default flags for the various versions.

167DEFAULT_FLAGS = {VERSION0: 0, VERSION1: FULLCASE}

168

169# The mask for the flags.

171 REVERSE)

173 _ALL_ENCODINGS)

174

175ALPHA = frozenset(string.ascii_letters)

176DIGITS = frozenset(string.digits)

177ALNUM = ALPHA | DIGITS

178OCT_DIGITS = frozenset(string.octdigits)

179HEX_DIGITS = frozenset(string.hexdigits)

180SPECIAL_CHARS = frozenset("()|?*+{^$.[\\#") | frozenset([""])

181NAMED_CHAR_PART = ALNUM | frozenset(" -")

182PROPERTY_NAME_PART = ALNUM | frozenset(" &_-.")

183SET_OPS = ("||", "~~", "&&", "--")

184

185# The width of the code words inside the regex engine.

186BYTES_PER_CODE = _regex.get_code_size()

187BITS_PER_CODE = BYTES_PER_CODE * 8

188

189# The repeat count which represents infinity.

190UNLIMITED = (1 << BITS_PER_CODE) - 1

191

192# The regular expression flags.

193REGEX_FLAGS = {"a": ASCII, "b": BESTMATCH, "e": ENHANCEMATCH, "f": FULLCASE,

194 "i": IGNORECASE, "L": LOCALE, "m": MULTILINE, "p": POSIX, "r": REVERSE,

195 "s": DOTALL, "u": UNICODE, "V0": VERSION0, "V1": VERSION1, "w": WORD, "x":

196 VERBOSE}

197

198# The case flags.

199CASE_FLAGS = FULLCASE | IGNORECASE

200NOCASE = 0

201FULLIGNORECASE = FULLCASE | IGNORECASE

202

203FULL_CASE_FOLDING = UNICODE | FULLIGNORECASE

204

205CASE_FLAGS_COMBINATIONS = {0: 0, FULLCASE: 0, IGNORECASE: IGNORECASE,

206 FULLIGNORECASE: FULLIGNORECASE}

207

208# The number of digits in hexadecimal escapes.

209HEX_ESCAPES = {"x": 2, "u": 4, "U": 8}

210

211# The names of the opcodes.

212OPCODES = """

213FAILURE

214SUCCESS

215ANY

216ANY_ALL

217ANY_ALL_REV

218ANY_REV

219ANY_U

220ANY_U_REV

221ATOMIC

222BOUNDARY

223BRANCH

224CALL_REF

225CHARACTER

226CHARACTER_IGN

227CHARACTER_IGN_REV

228CHARACTER_REV

229CONDITIONAL

230DEFAULT_BOUNDARY

231DEFAULT_END_OF_WORD

232DEFAULT_START_OF_WORD

233END

234END_OF_LINE

235END_OF_LINE_U

236END_OF_STRING

237END_OF_STRING_LINE

238END_OF_STRING_LINE_U

239END_OF_WORD

240FUZZY

241GRAPHEME_BOUNDARY

242GREEDY_REPEAT

243GROUP

244GROUP_CALL

245GROUP_EXISTS

246KEEP

247LAZY_REPEAT

248LOOKAROUND

249NEXT

250PROPERTY

251PROPERTY_IGN

252PROPERTY_IGN_REV

253PROPERTY_REV

254PRUNE

255RANGE

256RANGE_IGN

257RANGE_IGN_REV

258RANGE_REV

259REF_GROUP

260REF_GROUP_FLD

261REF_GROUP_FLD_REV

262REF_GROUP_IGN

263REF_GROUP_IGN_REV

264REF_GROUP_REV

265SEARCH_ANCHOR

266SET_DIFF

267SET_DIFF_IGN

268SET_DIFF_IGN_REV

269SET_DIFF_REV

270SET_INTER

271SET_INTER_IGN

272SET_INTER_IGN_REV

273SET_INTER_REV

274SET_SYM_DIFF

275SET_SYM_DIFF_IGN

276SET_SYM_DIFF_IGN_REV

277SET_SYM_DIFF_REV

278SET_UNION

279SET_UNION_IGN

280SET_UNION_IGN_REV

281SET_UNION_REV

282SKIP

283START_OF_LINE

284START_OF_LINE_U

285START_OF_STRING

286START_OF_WORD

287STRING

288STRING_FLD

289STRING_FLD_REV

290STRING_IGN

291STRING_IGN_REV

292STRING_REV

293FUZZY_EXT

294"""

295

296# Define the opcodes in a namespace.

297class Namespace:

298 pass

299

300OP = Namespace()

301for i, op in enumerate(OPCODES.split()):

302 setattr(OP, op, i)

303

304def _shrink_cache(cache_dict, args_dict, locale_sensitive, max_length, divisor=5):

305 """Make room in the given cache.

306

307 Args:

308 cache_dict: The cache dictionary to modify.

309 args_dict: The dictionary of named list args used by patterns.

310 max_length: Maximum # of entries in cache_dict before it is shrunk.

311 divisor: Cache will shrink to max_length - 1/divisor*max_length items.

312 """

313 # Toss out a fraction of the entries at random to make room for new ones.

314 # A random algorithm was chosen as opposed to simply cache_dict.popitem()

315 # as popitem could penalize the same regular expression repeatedly based

316 # on its internal hash value. Being random should spread the cache miss

317 # love around.

318 cache_keys = tuple(cache_dict.keys())

319 overage = len(cache_keys) - max_length

320 if overage < 0:

321 # Cache is already within limits. Normally this should not happen

322 # but it could due to multithreading.

323 return

324

325 number_to_toss = max_length // divisor + overage

326

327 # The import is done here to avoid a circular dependency.

328 import random

329 if not hasattr(random, 'sample'):

330 # Do nothing while resolving the circular dependency:

331 # re->random->warnings->tokenize->string->re

332 return

333

334 for doomed_key in random.sample(cache_keys, number_to_toss):

335 try:

336 del cache_dict[doomed_key]

337 except KeyError:

338 # Ignore problems if the cache changed from another thread.

339 pass

340

341 # Rebuild the arguments and locale-sensitivity dictionaries.

342 args_dict.clear()

343 sensitivity_dict = {}

344 for pattern, pattern_type, flags, args, default_version, locale in tuple(cache_dict):

345 args_dict[pattern, pattern_type, flags, default_version, locale] = args

346 try:

347 sensitivity_dict[pattern_type, pattern] = locale_sensitive[pattern_type, pattern]

348 except KeyError:

349 pass

350

351 locale_sensitive.clear()

352 locale_sensitive.update(sensitivity_dict)

353

354def _fold_case(info, string):

355 "Folds the case of a string."

356 flags = info.flags

357 if (flags & _ALL_ENCODINGS) == 0:

358 flags |= info.guess_encoding

359

360 return _regex.fold_case(flags, string)

361

362def is_cased_i(info, char):

363 "Checks whether a character is cased."

364 return len(_regex.get_all_cases(info.flags, char)) > 1

365

366def is_cased_f(flags, char):

367 "Checks whether a character is cased."

368 return len(_regex.get_all_cases(flags, char)) > 1

369

370def _compile_firstset(info, fs):

371 "Compiles the firstset for the pattern."

372 reverse = bool(info.flags & REVERSE)

373 fs = _check_firstset(info, reverse, fs)

374 if not fs or isinstance(fs, AnyAll):

375 return []

376

377 # Compile the firstset.

378 return fs.compile(reverse)

379

380def _check_firstset(info, reverse, fs):

381 "Checks the firstset for the pattern."

382 if not fs or None in fs:

383 return None

384

385 # If we ignore the case, for simplicity we won't build a firstset.

386 members = set()

387 case_flags = NOCASE

388 for i in fs:

389 if isinstance(i, Character) and not i.positive:

390 return None

391

392# if i.case_flags:

393# if isinstance(i, Character):

394# if is_cased_i(info, i.value):

395# return []

396# elif isinstance(i, SetBase):

397# return []

398 case_flags |= i.case_flags

399 members.add(i.with_flags(case_flags=NOCASE))

400

401 if case_flags == (FULLCASE | IGNORECASE):

402 return None

403

404 # Build the firstset.

405 fs = SetUnion(info, list(members), case_flags=case_flags & ~FULLCASE,

406 zerowidth=True)

407 fs = fs.optimise(info, reverse, in_set=True)

408

409 return fs

410

411def _flatten_code(code):

412 "Flattens the code from a list of tuples."

413 flat_code = []

414 for c in code:

415 flat_code.extend(c)

416

417 return flat_code

418

419def make_case_flags(info):

420 "Makes the case flags."

421 flags = info.flags & CASE_FLAGS

422

423 # Turn off FULLCASE if ASCII is turned on.

424 if info.flags & ASCII:

425 flags &= ~FULLCASE

426

427 return flags

428

429def make_character(info, value, in_set=False):

430 "Makes a character literal."

431 if in_set:

432 # A character set is built case-sensitively.

433 return Character(value)

434

435 return Character(value, case_flags=make_case_flags(info))

436

437def make_ref_group(info, name, position):

438 "Makes a group reference."

439 return RefGroup(info, name, position, case_flags=make_case_flags(info))

440

441def make_string_set(info, name):

442 "Makes a string set."

443 return StringSet(info, name, case_flags=make_case_flags(info))

444

445def make_property(info, prop, in_set):

446 "Makes a property."

447 if in_set:

448 return prop

449

450 return prop.with_flags(case_flags=make_case_flags(info))

451

452def _parse_pattern(source, info):

453 "Parses a pattern, eg. 'a|b|c'."

454 branches = [parse_sequence(source, info)]

455 while source.match("|"):

456 branches.append(parse_sequence(source, info))

457

458 if len(branches) == 1:

459 return branches[0]

460 return Branch(branches)

461

462def parse_sequence(source, info):

463 "Parses a sequence, eg. 'abc'."

464 sequence = [None]

465 case_flags = make_case_flags(info)

466 while True:

467 saved_pos = source.pos

468 ch = source.get()

469 if ch in SPECIAL_CHARS:

470 if ch in ")|":

471 # The end of a sequence. At the end of the pattern ch is "".

472 source.pos = saved_pos

473 break

474 elif ch == "\\":

475 # An escape sequence outside a set.

476 sequence.append(parse_escape(source, info, False))

477 elif ch == "(":

478 # A parenthesised subpattern or a flag.

479 element = parse_paren(source, info)

480 if element is None:

481 case_flags = make_case_flags(info)

482 else:

483 sequence.append(element)

484 elif ch == ".":

485 # Any character.

486 if info.flags & DOTALL:

487 sequence.append(AnyAll())

488 elif info.flags & WORD:

489 sequence.append(AnyU())

490 else:

491 sequence.append(Any())

492 elif ch == "[":

493 # A character set.

494 sequence.append(parse_set(source, info))

495 elif ch == "^":

496 # The start of a line or the string.

497 if info.flags & MULTILINE:

498 if info.flags & WORD:

499 sequence.append(StartOfLineU())

500 else:

501 sequence.append(StartOfLine())

502 else:

503 sequence.append(StartOfString())

504 elif ch == "$":

505 # The end of a line or the string.

506 if info.flags & MULTILINE:

507 if info.flags & WORD:

508 sequence.append(EndOfLineU())

509 else:

510 sequence.append(EndOfLine())

511 else:

512 if info.flags & WORD:

513 sequence.append(EndOfStringLineU())

514 else:

515 sequence.append(EndOfStringLine())

516 elif ch in "?*+{":

517 # Looks like a quantifier.

518 counts = parse_quantifier(source, info, ch)

519 if counts:

520 # It _is_ a quantifier.

521 apply_quantifier(source, info, counts, case_flags, ch,

522 saved_pos, sequence)

523 sequence.append(None)

524 else:

525 # It's not a quantifier. Maybe it's a fuzzy constraint.

526 constraints = parse_fuzzy(source, info, ch, case_flags)

527

528 if constraints:

529 # It _is_ a fuzzy constraint.

530 if is_actually_fuzzy(constraints):

531 apply_constraint(source, info, constraints, case_flags,

532 saved_pos, sequence)

533 sequence.append(None)

534 else:

535 # The element was just a literal.

536 sequence.append(Character(ord(ch),

537 case_flags=case_flags))

538 else:

539 # A literal.

540 sequence.append(Character(ord(ch), case_flags=case_flags))

541 else:

542 # A literal.

543 sequence.append(Character(ord(ch), case_flags=case_flags))

544

545 sequence = [item for item in sequence if item is not None]

546 return Sequence(sequence)

547

548def is_actually_fuzzy(constraints):

549 "Checks whether a fuzzy constraint is actually fuzzy."

550 if constraints.get("e") == (0, 0):

551 return False

552

553 if (constraints.get("s"), constraints.get("i"), constraints.get("d")) == ((0, 0), (0, 0), (0, 0)):

554 return False

555

556 return True

557

558def apply_quantifier(source, info, counts, case_flags, ch, saved_pos,

559 sequence):

560 element = sequence.pop()

561 if element is None:

562 if sequence:

563 raise error("multiple repeat", source.string, saved_pos)

564 raise error("nothing to repeat", source.string, saved_pos)

565

566 if isinstance(element, (GreedyRepeat, LazyRepeat, PossessiveRepeat)):

567 raise error("multiple repeat", source.string, saved_pos)

568

569 min_count, max_count = counts

570 saved_pos = source.pos

571 ch = source.get()

572 if ch == "?":

573 # The "?" suffix that means it's a lazy repeat.

574 repeated = LazyRepeat

575 elif ch == "+":

576 # The "+" suffix that means it's a possessive repeat.

577 repeated = PossessiveRepeat

578 else:

579 # No suffix means that it's a greedy repeat.

580 source.pos = saved_pos

581 repeated = GreedyRepeat

582

583 # Ignore the quantifier if it applies to a zero-width item or the number of

584 # repeats is fixed at 1.

585 if not element.is_empty() and (min_count != 1 or max_count != 1):

586 element = repeated(element, min_count, max_count)

587

588 sequence.append(element)

589

590def apply_constraint(source, info, constraints, case_flags, saved_pos,

591 sequence):

592 element = sequence.pop()

593 if element is None:

594 raise error("nothing for fuzzy constraint", source.string, saved_pos)

595

596 # If a group is marked as fuzzy then put all of the fuzzy part in the

597 # group.

598 if isinstance(element, Group):

599 element.subpattern = Fuzzy(element.subpattern, constraints)

600 sequence.append(element)

601 else:

602 sequence.append(Fuzzy(element, constraints))

603

604_QUANTIFIERS = {"?": (0, 1), "*": (0, None), "+": (1, None)}

605

606def parse_quantifier(source, info, ch):

607 "Parses a quantifier."

608 q = _QUANTIFIERS.get(ch)

609 if q:

610 # It's a quantifier.

611 return q

612

613 if ch == "{":

614 # Looks like a limited repeated element, eg. 'a{2,3}'.

615 counts = parse_limited_quantifier(source)

616 if counts:

617 return counts

618

619 return None

620

621def is_above_limit(count):

622 "Checks whether a count is above the maximum."

623 return count is not None and count >= UNLIMITED

624

625def parse_limited_quantifier(source):

626 "Parses a limited quantifier."

627 saved_pos = source.pos

628 min_count = parse_count(source)

629 if source.match(","):

630 max_count = parse_count(source)

631

632 # No minimum means 0 and no maximum means unlimited.

633 min_count = int(min_count or 0)

634 max_count = int(max_count) if max_count else None

635 else:

636 if not min_count:

637 source.pos = saved_pos

638 return None

639

640 min_count = max_count = int(min_count)

641

642 if not source.match ("}"):

643 source.pos = saved_pos

644 return None

645

646 if is_above_limit(min_count) or is_above_limit(max_count):

647 raise error("repeat count too big", source.string, saved_pos)

648

649 if max_count is not None and min_count > max_count:

650 raise error("min repeat greater than max repeat", source.string,

651 saved_pos)

652

653 return min_count, max_count

654

655def parse_fuzzy(source, info, ch, case_flags):

656 "Parses a fuzzy setting, if present."

657 saved_pos = source.pos

658

659 if ch != "{":

660 return None

661

662 constraints = {}

663 try:

664 parse_fuzzy_item(source, constraints)

665 while source.match(","):

666 parse_fuzzy_item(source, constraints)

667 except ParseError:

668 source.pos = saved_pos

669 return None

670

671 if source.match(":"):

672 constraints["test"] = parse_fuzzy_test(source, info, case_flags)

673

674 if not source.match("}"):

675 raise error("expected }", source.string, source.pos)

676

677 return constraints

678

679def parse_fuzzy_item(source, constraints):

680 "Parses a fuzzy setting item."

681 saved_pos = source.pos

682 try:

683 parse_cost_constraint(source, constraints)

684 except ParseError:

685 source.pos = saved_pos

686

687 parse_cost_equation(source, constraints)

688

689def parse_cost_constraint(source, constraints):

690 "Parses a cost constraint."

691 saved_pos = source.pos

692 ch = source.get()

693 if ch in ALPHA:

694 # Syntax: constraint [("<=" | "<") cost]

695 constraint = parse_constraint(source, constraints, ch)

696

697 max_inc = parse_fuzzy_compare(source)

698

699 if max_inc is None:

700 # No maximum cost.

701 constraints[constraint] = 0, None

702 else:

703 # There's a maximum cost.

704 cost_pos = source.pos

705 max_cost = parse_cost_limit(source)

706

707 # Inclusive or exclusive limit?

708 if not max_inc:

709 max_cost -= 1

710

711 if max_cost < 0:

712 raise error("bad fuzzy cost limit", source.string, cost_pos)

713

714 constraints[constraint] = 0, max_cost

715 elif ch in DIGITS:

716 # Syntax: cost ("<=" | "<") constraint ("<=" | "<") cost

717 source.pos = saved_pos

718

719 # Minimum cost.

720 cost_pos = source.pos

721 min_cost = parse_cost_limit(source)

722

723 min_inc = parse_fuzzy_compare(source)

724 if min_inc is None:

725 raise ParseError()

726

727 constraint = parse_constraint(source, constraints, source.get())

728

729 max_inc = parse_fuzzy_compare(source)

730 if max_inc is None:

731 raise ParseError()

732

733 # Maximum cost.

734 cost_pos = source.pos

735 max_cost = parse_cost_limit(source)

736

737 # Inclusive or exclusive limits?

738 if not min_inc:

739 min_cost += 1

740 if not max_inc:

741 max_cost -= 1

742

743 if not 0 <= min_cost <= max_cost:

744 raise error("bad fuzzy cost limit", source.string, cost_pos)

745

746 constraints[constraint] = min_cost, max_cost

747 else:

748 raise ParseError()

749

750def parse_cost_limit(source):

751 "Parses a cost limit."

752 cost_pos = source.pos

753 digits = parse_count(source)

754

755 try:

756 return int(digits)

757 except ValueError:

758 pass

759

760 raise error("bad fuzzy cost limit", source.string, cost_pos)

761

762def parse_constraint(source, constraints, ch):

763 "Parses a constraint."

764 if ch not in "deis":

765 raise ParseError()

766

767 if ch in constraints:

768 raise ParseError()

769

770 return ch

771

772def parse_fuzzy_compare(source):

773 "Parses a cost comparator."

774 if source.match("<="):

775 return True

776 elif source.match("<"):

777 return False

778 else:

779 return None

780

781def parse_cost_equation(source, constraints):

782 "Parses a cost equation."

783 if "cost" in constraints:

784 raise error("more than one cost equation", source.string, source.pos)

785

786 cost = {}

787

788 parse_cost_term(source, cost)

789 while source.match("+"):

790 parse_cost_term(source, cost)

791

792 max_inc = parse_fuzzy_compare(source)

793 if max_inc is None:

794 raise ParseError()

795

796 max_cost = int(parse_count(source))

797

798 if not max_inc:

799 max_cost -= 1

800

801 if max_cost < 0:

802 raise error("bad fuzzy cost limit", source.string, source.pos)

803

804 cost["max"] = max_cost

805

806 constraints["cost"] = cost

807

808def parse_cost_term(source, cost):

809 "Parses a cost equation term."

810 coeff = parse_count(source)

811 ch = source.get()

812 if ch not in "dis":

813 raise ParseError()

814

815 if ch in cost:

816 raise error("repeated fuzzy cost", source.string, source.pos)

817

818 cost[ch] = int(coeff or 1)

819

820def parse_fuzzy_test(source, info, case_flags):

821 saved_pos = source.pos

822 ch = source.get()

823 if ch in SPECIAL_CHARS:

824 if ch == "\\":

825 # An escape sequence outside a set.

826 return parse_escape(source, info, False)

827 elif ch == ".":

828 # Any character.

829 if info.flags & DOTALL:

830 return AnyAll()

831 elif info.flags & WORD:

832 return AnyU()

833 else:

834 return Any()

835 elif ch == "[":

836 # A character set.

837 return parse_set(source, info)

838 else:

839 raise error("expected character set", source.string, saved_pos)

840 elif ch:

841 # A literal.

842 return Character(ord(ch), case_flags=case_flags)

843 else:

844 raise error("expected character set", source.string, saved_pos)

845

846def parse_count(source):

847 "Parses a quantifier's count, which can be empty."

848 return source.get_while(DIGITS)

849

850def parse_paren(source, info):

851 """Parses a parenthesised subpattern or a flag. Returns FLAGS if it's an

852 inline flag.

853 """

854 saved_pos = source.pos

855 ch = source.get(True)

856 if ch == "?":

857 # (?...

858 saved_pos_2 = source.pos

859 ch = source.get(True)

860 if ch == "<":

861 # (?<...

862 saved_pos_3 = source.pos

863 ch = source.get()

864 if ch in ("=", "!"):

865 # (?<=... or (?<!...: lookbehind.

866 return parse_lookaround(source, info, True, ch == "=")

867

868 # (?<...: a named capture group.

869 source.pos = saved_pos_3

870 name = parse_name(source)

871 group = info.open_group(name)

872 source.expect(">")

873 saved_flags = info.flags

874 try:

875 subpattern = _parse_pattern(source, info)

876 source.expect(")")

877 finally:

878 info.flags = saved_flags

879 source.ignore_space = bool(info.flags & VERBOSE)

880

881 info.close_group()

882 return Group(info, group, subpattern)

883 if ch in ("=", "!"):

884 # (?=... or (?!...: lookahead.

885 return parse_lookaround(source, info, False, ch == "=")

886 if ch == "P":

887 # (?P...: a Python extension.

888 return parse_extension(source, info)

889 if ch == "#":

890 # (?#...: a comment.

891 return parse_comment(source)

892 if ch == "(":

893 # (?(...: a conditional subpattern.

894 return parse_conditional(source, info)

895 if ch == ">":

896 # (?>...: an atomic subpattern.

897 return parse_atomic(source, info)

898 if ch == "|":

899 # (?|...: a common/reset groups branch.

900 return parse_common(source, info)

901 if ch == "R" or "0" <= ch <= "9":

902 # (?R...: probably a call to a group.

903 return parse_call_group(source, info, ch, saved_pos_2)

904 if ch == "&":

905 # (?&...: a call to a named group.

906 return parse_call_named_group(source, info, saved_pos_2)

907 if (ch == "+" or ch == "-") and source.peek() in DIGITS:

908 return parse_rel_call_group(source, info, ch, saved_pos_2)

909

910 # (?...: probably a flags subpattern.

911 source.pos = saved_pos_2

912 return parse_flags_subpattern(source, info)

913

914 if ch == "*":

915 # (*...

916 saved_pos_2 = source.pos

917 word = source.get_while(set(")>"), include=False)

918 if word[ : 1].isalpha():

919 verb = VERBS.get(word)

920 if not verb:

921 raise error("unknown verb", source.string, saved_pos_2)

922

923 source.expect(")")

924

925 return verb

926

927 # (...: an unnamed capture group.

928 source.pos = saved_pos

929 group = info.open_group()

930 saved_flags = info.flags

931 try:

932 subpattern = _parse_pattern(source, info)

933 source.expect(")")

934 finally:

935 info.flags = saved_flags

936 source.ignore_space = bool(info.flags & VERBOSE)

937

938 info.close_group()

939

940 return Group(info, group, subpattern)

941

942def parse_extension(source, info):

943 "Parses a Python extension."

944 saved_pos = source.pos

945 ch = source.get()

946 if ch == "<":

947 # (?P<...: a named capture group.

948 name = parse_name(source)

949 group = info.open_group(name)

950 source.expect(">")

951 saved_flags = info.flags

952 try:

953 subpattern = _parse_pattern(source, info)

954 source.expect(")")

955 finally:

956 info.flags = saved_flags

957 source.ignore_space = bool(info.flags & VERBOSE)

958

959 info.close_group()

960

961 return Group(info, group, subpattern)

962 if ch == "=":

963 # (?P=...: a named group reference.

964 name = parse_name(source, allow_numeric=True)

965 source.expect(")")

966 if info.is_open_group(name):

967 raise error("cannot refer to an open group", source.string,

968 saved_pos)

969

970 return make_ref_group(info, name, saved_pos)

971 if ch == ">" or ch == "&":

972 # (?P>...: a call to a group.

973 return parse_call_named_group(source, info, saved_pos)

974

975 source.pos = saved_pos

976 raise error("unknown extension", source.string, saved_pos)

977

978def parse_comment(source):

979 "Parses a comment."

980 while True:

981 saved_pos = source.pos

982 c = source.get(True)

983

984 if not c or c == ")":

985 break

986

987 if c == "\\":

988 c = source.get(True)

989

990 source.pos = saved_pos

991 source.expect(")")

992

993 return None

994

995def parse_lookaround(source, info, behind, positive):

996 "Parses a lookaround."

997 saved_flags = info.flags

998 try:

999 subpattern = _parse_pattern(source, info)

1000 source.expect(")")

1001 finally:

1002 info.flags = saved_flags

1003 source.ignore_space = bool(info.flags & VERBOSE)

1004

1005 return LookAround(behind, positive, subpattern)

1006

1007def parse_conditional(source, info):

1008 "Parses a conditional subpattern."

1009 saved_flags = info.flags

1010 saved_pos = source.pos

1011 ch = source.get()

1012 if ch == "?":

1013 # (?(?...

1014 ch = source.get()

1015 if ch in ("=", "!"):

1016 # (?(?=... or (?(?!...: lookahead conditional.

1017 return parse_lookaround_conditional(source, info, False, ch == "=")

1018 if ch == "<":

1019 # (?(?<...

1020 ch = source.get()

1021 if ch in ("=", "!"):

1022 # (?(?<=... or (?(?<!...: lookbehind conditional.

1023 return parse_lookaround_conditional(source, info, True, ch ==

1024 "=")

1025

1026 source.pos = saved_pos

1027 raise error("expected lookaround conditional", source.string,

1028 source.pos)

1029

1030 source.pos = saved_pos

1031 try:

1032 group = parse_name(source, True)

1033 source.expect(")")

1034 yes_branch = parse_sequence(source, info)

1035 if source.match("|"):

1036 no_branch = parse_sequence(source, info)

1037 else:

1038 no_branch = Sequence()

1039

1040 source.expect(")")

1041 finally:

1042 info.flags = saved_flags

1043 source.ignore_space = bool(info.flags & VERBOSE)

1044

1045 if yes_branch.is_empty() and no_branch.is_empty():

1046 return Sequence()

1047

1048 return Conditional(info, group, yes_branch, no_branch, saved_pos)

1049

1050def parse_lookaround_conditional(source, info, behind, positive):

1051 saved_flags = info.flags

1052 try:

1053 subpattern = _parse_pattern(source, info)

1054 source.expect(")")

1055 finally:

1056 info.flags = saved_flags

1057 source.ignore_space = bool(info.flags & VERBOSE)

1058

1059 yes_branch = parse_sequence(source, info)

1060 if source.match("|"):

1061 no_branch = parse_sequence(source, info)

1062 else:

1063 no_branch = Sequence()

1064

1065 source.expect(")")

1066

1067 return LookAroundConditional(behind, positive, subpattern, yes_branch,

1068 no_branch)

1069

1070def parse_atomic(source, info):

1071 "Parses an atomic subpattern."

1072 saved_flags = info.flags

1073 try:

1074 subpattern = _parse_pattern(source, info)

1075 source.expect(")")

1076 finally:

1077 info.flags = saved_flags

1078 source.ignore_space = bool(info.flags & VERBOSE)

1079

1080 return Atomic(subpattern)

1081

1082def parse_common(source, info):

1083 "Parses a common groups branch."

1084 # Capture group numbers in different branches can reuse the group numbers.

1085 initial_group_count = info.group_count

1086 branches = [parse_sequence(source, info)]

1087 final_group_count = info.group_count

1088 while source.match("|"):

1089 info.group_count = initial_group_count

1090 branches.append(parse_sequence(source, info))

1091 final_group_count = max(final_group_count, info.group_count)

1092

1093 info.group_count = final_group_count

1094 source.expect(")")

1095

1096 if len(branches) == 1:

1097 return branches[0]

1098 return Branch(branches)

1099

1100def parse_call_group(source, info, ch, pos):

1101 "Parses a call to a group."

1102 if ch == "R":

1103 group = "0"

1104 else:

1105 group = ch + source.get_while(DIGITS)

1106

1107 source.expect(")")

1108

1109 return CallGroup(info, group, pos)

1110

1111def parse_rel_call_group(source, info, ch, pos):

1112 "Parses a relative call to a group."

1113 digits = source.get_while(DIGITS)

1114 if not digits:

1115 raise error("missing relative group number", source.string, source.pos)

1116

1117 offset = int(digits)

1118 group = info.group_count + offset if ch == "+" else info.group_count - offset + 1

1119 if group <= 0:

1120 raise error("invalid relative group number", source.string, source.pos)

1121

1122 source.expect(")")

1123

1124 return CallGroup(info, group, pos)

1125

1126def parse_call_named_group(source, info, pos):

1127 "Parses a call to a named group."

1128 group = parse_name(source)

1129 source.expect(")")

1130

1131 return CallGroup(info, group, pos)

1132

1133def parse_flag_set(source):

1134 "Parses a set of inline flags."

1135 flags = 0

1136

1137 try:

1138 while True:

1139 saved_pos = source.pos

1140 ch = source.get()

1141 if ch == "V":

1142 ch += source.get()

1143 flags |= REGEX_FLAGS[ch]

1144 except KeyError:

1145 source.pos = saved_pos

1146

1147 return flags

1148

1149def parse_flags(source, info):

1150 "Parses flags being turned on/off."

1151 flags_on = parse_flag_set(source)

1152 if source.match("-"):

1153 flags_off = parse_flag_set(source)

1154 if not flags_off:

1155 raise error("bad inline flags: no flags after '-'", source.string,

1156 source.pos)

1157 else:

1158 flags_off = 0

1159

1160 if flags_on & LOCALE:

1161 # Remember that this pattern as an inline locale flag.

1162 info.inline_locale = True

1163

1164 return flags_on, flags_off

1165

1166def parse_subpattern(source, info, flags_on, flags_off):

1167 "Parses a subpattern with scoped flags."

1168 saved_flags = info.flags

1169 info.flags = (info.flags | flags_on) & ~flags_off

1170

1171 # Ensure that there aren't multiple encoding flags set.

1172 if info.flags & (ASCII | LOCALE | UNICODE):

1173 info.flags = (info.flags & ~_ALL_ENCODINGS) | flags_on

1174

1175 source.ignore_space = bool(info.flags & VERBOSE)

1176 try:

1177 subpattern = _parse_pattern(source, info)

1178 source.expect(")")

1179 finally:

1180 info.flags = saved_flags

1181 source.ignore_space = bool(info.flags & VERBOSE)

1182

1183 return subpattern

1184

1185def parse_flags_subpattern(source, info):

1186 """Parses a flags subpattern. It could be inline flags or a subpattern

1187 possibly with local flags. If it's a subpattern, then that's returned;

1188 if it's a inline flags, then None is returned.

1189 """

1190 flags_on, flags_off = parse_flags(source, info)

1191

1192 if flags_off & GLOBAL_FLAGS:

1193 raise error("bad inline flags: cannot turn off global flag",

1194 source.string, source.pos)

1195

1196 if flags_on & flags_off:

1197 raise error("bad inline flags: flag turned on and off", source.string,

1198 source.pos)

1199

1200 # Handle flags which are global in all regex behaviours.

1201 new_global_flags = (flags_on & ~info.global_flags) & GLOBAL_FLAGS

1202 if new_global_flags:

1203 info.global_flags |= new_global_flags

1204

1205 # A global has been turned on, so reparse the pattern.

1206 raise _UnscopedFlagSet(info.global_flags)

1207

1208 # Ensure that from now on we have only scoped flags.

1209 flags_on &= ~GLOBAL_FLAGS

1210

1211 if source.match(":"):

1212 return parse_subpattern(source, info, flags_on, flags_off)

1213

1214 if source.match(")"):

1215 parse_positional_flags(source, info, flags_on, flags_off)

1216 return None

1217

1218 raise error("unknown extension", source.string, source.pos)

1219

1220def parse_positional_flags(source, info, flags_on, flags_off):

1221 "Parses positional flags."

1222 info.flags = (info.flags | flags_on) & ~flags_off

1223 source.ignore_space = bool(info.flags & VERBOSE)

1224

1225def parse_name(source, allow_numeric=False, allow_group_0=False):

1226 "Parses a name."

1227 name = source.get_while(set(")>"), include=False)

1228

1229 if not name:

1230 raise error("missing group name", source.string, source.pos)

1231

1232 if name.isdigit():

1233 min_group = 0 if allow_group_0 else 1

1234 if not allow_numeric or int(name) < min_group:

1235 raise error("bad character in group name", source.string,

1236 source.pos)

1237 else:

1238 if not name.isidentifier():

1239 raise error("bad character in group name", source.string,

1240 source.pos)

1241

1242 return name

1243

1244def is_octal(string):

1245 "Checks whether a string is octal."

1246 return all(ch in OCT_DIGITS for ch in string)

1247

1248def is_decimal(string):

1249 "Checks whether a string is decimal."

1250 return all(ch in DIGITS for ch in string)

1251

1252def is_hexadecimal(string):

1253 "Checks whether a string is hexadecimal."

1254 return all(ch in HEX_DIGITS for ch in string)

1255

1256def parse_escape(source, info, in_set):

1257 "Parses an escape sequence."

1258 saved_ignore = source.ignore_space

1259 source.ignore_space = False

1260 ch = source.get()

1261 source.ignore_space = saved_ignore

1262 if not ch:

1263 # A backslash at the end of the pattern.

1264 raise error("bad escape (end of pattern)", source.string, source.pos)

1265 if ch in HEX_ESCAPES:

1266 # A hexadecimal escape sequence.

1267 return parse_hex_escape(source, info, ch, HEX_ESCAPES[ch], in_set, ch)

1268 elif ch == "g" and not in_set:

1269 # A group reference.

1270 saved_pos = source.pos

1271 try:

1272 return parse_group_ref(source, info)

1273 except error:

1274 # Invalid as a group reference, so assume it's a literal.

1275 source.pos = saved_pos

1276

1277 return make_character(info, ord(ch), in_set)

1278 elif ch == "G" and not in_set:

1279 # A search anchor.

1280 return SearchAnchor()

1281 elif ch == "L" and not in_set:

1282 # A string set.

1283 return parse_string_set(source, info)

1284 elif ch == "N":

1285 # A named codepoint.

1286 return parse_named_char(source, info, in_set)

1287 elif ch in "pP":

1288 # A Unicode property, positive or negative.

1289 return parse_property(source, info, ch == "p", in_set)

1290 elif ch == "R" and not in_set:

1291 # A line ending.

1292 charset = [0x0A, 0x0B, 0x0C, 0x0D]

1293 if info.guess_encoding == UNICODE:

1294 charset.extend([0x85, 0x2028, 0x2029])

1295

1296 return Atomic(Branch([String([0x0D, 0x0A]), SetUnion(info, [Character(c)

1297 for c in charset])]))

1298 elif ch == "X" and not in_set:

1299 # A grapheme cluster.

1300 return Grapheme()

1301 elif ch in ALPHA:

1302 # An alphabetic escape sequence.

1303 # Positional escapes aren't allowed inside a character set.

1304 if not in_set:

1305 if info.flags & WORD:

1306 value = WORD_POSITION_ESCAPES.get(ch)

1307 elif info.flags & ASCII:

1308 value = ASCII_POSITION_ESCAPES.get(ch)

1309 elif info.flags & UNICODE:

1310 value = UNICODE_POSITION_ESCAPES.get(ch)

1311 else:

1312 value = POSITION_ESCAPES.get(ch)

1313

1314 if value:

1315 return value

1316

1317 if info.flags & ASCII:

1318 value = ASCII_CHARSET_ESCAPES.get(ch)

1319 elif info.flags & UNICODE:

1320 value = UNICODE_CHARSET_ESCAPES.get(ch)

1321 else:

1322 value = CHARSET_ESCAPES.get(ch)

1323

1324 if value:

1325 return value

1326

1327 value = CHARACTER_ESCAPES.get(ch)

1328 if value:

1329 return Character(ord(value))

1330

1331 raise error("bad escape \\%s" % ch, source.string, source.pos)

1332 elif ch in DIGITS:

1333 # A numeric escape sequence.

1334 return parse_numeric_escape(source, info, ch, in_set)

1335 else:

1336 # A literal.

1337 return make_character(info, ord(ch), in_set)

1338

1339def parse_numeric_escape(source, info, ch, in_set):

1340 "Parses a numeric escape sequence."

1341 if in_set or ch == "0":

1342 # Octal escape sequence, max 3 digits.

1343 return parse_octal_escape(source, info, [ch], in_set)

1344

1345 # At least 1 digit, so either octal escape or group.

1346 digits = ch

1347 saved_pos = source.pos

1348 ch = source.get()

1349 if ch in DIGITS:

1350 # At least 2 digits, so either octal escape or group.

1351 digits += ch

1352 saved_pos = source.pos

1353 ch = source.get()

1354 if is_octal(digits) and ch in OCT_DIGITS:

1355 # 3 octal digits, so octal escape sequence.

1356 encoding = info.flags & _ALL_ENCODINGS

1357 if encoding == ASCII or encoding == LOCALE:

1358 octal_mask = 0xFF

1359 else:

1360 octal_mask = 0x1FF

1361

1362 value = int(digits + ch, 8) & octal_mask

1363 return make_character(info, value)

1364

1365 # Group reference.

1366 source.pos = saved_pos

1367 if info.is_open_group(digits):

1368 raise error("cannot refer to an open group", source.string, source.pos)

1369

1370 return make_ref_group(info, digits, source.pos)

1371

1372def parse_octal_escape(source, info, digits, in_set):

1373 "Parses an octal escape sequence."

1374 saved_pos = source.pos

1375 ch = source.get()

1376 while len(digits) < 3 and ch in OCT_DIGITS:

1377 digits.append(ch)

1378 saved_pos = source.pos

1379 ch = source.get()

1380

1381 source.pos = saved_pos

1382 try:

1383 value = int("".join(digits), 8)

1384 return make_character(info, value, in_set)

1385 except ValueError:

1386 if digits[0] in OCT_DIGITS:

1387 raise error("incomplete escape \\%s" % ''.join(digits),

1388 source.string, source.pos)

1389 else:

1390 raise error("bad escape \\%s" % digits[0], source.string,

1391 source.pos)

1392

1393def parse_hex_escape(source, info, esc, expected_len, in_set, type):

1394 "Parses a hex escape sequence."

1395 saved_pos = source.pos

1396 digits = []

1397 for i in range(expected_len):

1398 ch = source.get()

1399 if ch not in HEX_DIGITS:

1400 raise error("incomplete escape \\%s%s" % (type, ''.join(digits)),

1401 source.string, saved_pos)

1402 digits.append(ch)

1403

1404 try:

1405 value = int("".join(digits), 16)

1406 except ValueError:

1407 pass

1408 else:

1409 if value < 0x110000:

1410 return make_character(info, value, in_set)

1411

1412 # Bad hex escape.

1413 raise error("bad hex escape \\%s%s" % (esc, ''.join(digits)),

1414 source.string, saved_pos)

1415

1416def parse_group_ref(source, info):

1417 "Parses a group reference."

1418 source.expect("<")

1419 saved_pos = source.pos

1420 name = parse_name(source, True)

1421 source.expect(">")

1422 if info.is_open_group(name):

1423 raise error("cannot refer to an open group", source.string, source.pos)

1424

1425 return make_ref_group(info, name, saved_pos)

1426

1427def parse_string_set(source, info):

1428 "Parses a string set reference."

1429 source.expect("<")

1430 name = parse_name(source, True)

1431 source.expect(">")

1432 if name is None or name not in info.kwargs:

1433 raise error("undefined named list", source.string, source.pos)

1434

1435 return make_string_set(info, name)

1436

1437def parse_named_char(source, info, in_set):

1438 "Parses a named character."

1439 saved_pos = source.pos

1440 if source.match("{"):

1441 name = source.get_while(NAMED_CHAR_PART, keep_spaces=True)

1442 if source.match("}"):

1443 try:

1444 value = unicodedata.lookup(name)

1445 return make_character(info, ord(value), in_set)

1446 except KeyError:

1447 raise error("undefined character name", source.string,

1448 source.pos)

1449

1450 source.pos = saved_pos

1451 return make_character(info, ord("N"), in_set)

1452

1453def parse_property(source, info, positive, in_set):

1454 "Parses a Unicode property."

1455 saved_pos = source.pos

1456 ch = source.get()

1457 if ch == "{":

1458 negate = source.match("^")

1459 prop_name, name = parse_property_name(source)

1460 if source.match("}"):

1461 # It's correctly delimited.

1462 if info.flags & ASCII:

1463 encoding = ASCII_ENCODING

1464 elif info.flags & UNICODE:

1465 encoding = UNICODE_ENCODING

1466 else:

1467 encoding = 0

1468

1469 prop = lookup_property(prop_name, name, positive != negate, source,

1470 encoding=encoding)

1471 return make_property(info, prop, in_set)

1472 elif ch and ch in "CLMNPSZ":

1473 # An abbreviated property, eg \pL.

1474 if info.flags & ASCII:

1475 encoding = ASCII_ENCODING

1476 elif info.flags & UNICODE:

1477 encoding = UNICODE_ENCODING

1478 else:

1479 encoding = 0

1480

1481 prop = lookup_property(None, ch, positive, source, encoding=encoding)

1482 return make_property(info, prop, in_set)

1483

1484 # Not a property, so treat as a literal "p" or "P".

1485 source.pos = saved_pos

1486 ch = "p" if positive else "P"

1487 return make_character(info, ord(ch), in_set)

1488

1489def parse_property_name(source):

1490 "Parses a property name, which may be qualified."

1491 name = source.get_while(PROPERTY_NAME_PART)

1492 saved_pos = source.pos

1493

1494 ch = source.get()

1495 if ch and ch in ":=":

1496 prop_name = name

1497 name = source.get_while(ALNUM | set(" &_-./")).strip()

1498

1499 if name:

1500 # Name after the ":" or "=", so it's a qualified name.

1501 saved_pos = source.pos

1502 else:

1503 # No name after the ":" or "=", so assume it's an unqualified name.

1504 prop_name, name = None, prop_name

1505 else:

1506 prop_name = None

1507

1508 source.pos = saved_pos

1509 return prop_name, name

1510

1511def parse_set(source, info):

1512 "Parses a character set."

1513 version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION

1514

1515 saved_ignore = source.ignore_space

1516 source.ignore_space = False

1517 # Negative set?

1518 negate = source.match("^")

1519 try:

1520 if version == VERSION0:

1521 item = parse_set_imp_union(source, info)

1522 else:

1523 item = parse_set_union(source, info)

1524

1525 if not source.match("]"):

1526 raise error("missing ]", source.string, source.pos)

1527 finally:

1528 source.ignore_space = saved_ignore

1529

1530 if negate:

1531 item = item.with_flags(positive=not item.positive)

1532

1533 item = item.with_flags(case_flags=make_case_flags(info))

1534

1535 return item

1536

1537def parse_set_union(source, info):

1538 "Parses a set union ([x||y])."

1539 items = [parse_set_symm_diff(source, info)]

1540 while source.match("||"):

1541 items.append(parse_set_symm_diff(source, info))

1542

1543 if len(items) == 1:

1544 return items[0]

1545 return SetUnion(info, items)

1546

1547def parse_set_symm_diff(source, info):

1548 "Parses a set symmetric difference ([x~~y])."

1549 items = [parse_set_inter(source, info)]

1550 while source.match("~~"):

1551 items.append(parse_set_inter(source, info))

1552

1553 if len(items) == 1:

1554 return items[0]

1555 return SetSymDiff(info, items)

1556

1557def parse_set_inter(source, info):

1558 "Parses a set intersection ([x&&y])."

1559 items = [parse_set_diff(source, info)]

1560 while source.match("&&"):

1561 items.append(parse_set_diff(source, info))

1562

1563 if len(items) == 1:

1564 return items[0]

1565 return SetInter(info, items)

1566

1567def parse_set_diff(source, info):

1568 "Parses a set difference ([x--y])."

1569 items = [parse_set_imp_union(source, info)]

1570 while source.match("--"):

1571 items.append(parse_set_imp_union(source, info))

1572

1573 if len(items) == 1:

1574 return items[0]

1575 return SetDiff(info, items)

1576

1577def parse_set_imp_union(source, info):

1578 "Parses a set implicit union ([xy])."

1579 version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION

1580

1581 items = [parse_set_member(source, info)]

1582 while True:

1583 saved_pos = source.pos

1584 if source.match("]"):

1585 # End of the set.

1586 source.pos = saved_pos

1587 break

1588

1589 if version == VERSION1 and any(source.match(op) for op in SET_OPS):

1590 # The new behaviour has set operators.

1591 source.pos = saved_pos

1592 break

1593

1594 items.append(parse_set_member(source, info))

1595

1596 if len(items) == 1:

1597 return items[0]

1598 return SetUnion(info, items)

1599

1600def parse_set_member(source, info):

1601 "Parses a member in a character set."

1602 # Parse a set item.

1603 start = parse_set_item(source, info)

1604 saved_pos1 = source.pos

1605 if (not isinstance(start, Character) or not start.positive or not

1606 source.match("-")):

1607 # It's not the start of a range.

1608 return start

1609

1610 version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION

1611

1612 # It looks like the start of a range of characters.

1613 saved_pos2 = source.pos

1614 if version == VERSION1 and source.match("-"):

1615 # It's actually the set difference operator '--', so return the

1616 # character.

1617 source.pos = saved_pos1

1618 return start

1619

1620 if source.match("]"):

1621 # We've reached the end of the set, so return both the character and

1622 # hyphen.

1623 source.pos = saved_pos2

1624 return SetUnion(info, [start, Character(ord("-"))])

1625

1626 # Parse a set item.

1627 end = parse_set_item(source, info)

1628 if not isinstance(end, Character) or not end.positive:

1629 # It's not a range, so return the character, hyphen and property.

1630 return SetUnion(info, [start, Character(ord("-")), end])

1631

1632 # It _is_ a range.

1633 if start.value > end.value:

1634 raise error("bad character range", source.string, source.pos)

1635

1636 if start.value == end.value:

1637 return start

1638

1639 return Range(start.value, end.value)

1640

1641def parse_set_item(source, info):

1642 "Parses an item in a character set."

1643 version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION

1644

1645 if source.match("\\"):

1646 # An escape sequence in a set.

1647 return parse_escape(source, info, True)

1648

1649 saved_pos = source.pos

1650 if source.match("[:"):

1651 # Looks like a POSIX character class.

1652 try:

1653 return parse_posix_class(source, info)

1654 except ParseError:

1655 # Not a POSIX character class.

1656 source.pos = saved_pos

1657

1658 if version == VERSION1 and source.match("["):

1659 # It's the start of a nested set.

1660

1661 # Negative set?

1662 negate = source.match("^")

1663 item = parse_set_union(source, info)

1664

1665 if not source.match("]"):

1666 raise error("missing ]", source.string, source.pos)

1667

1668 if negate:

1669 item = item.with_flags(positive=not item.positive)

1670

1671 return item

1672

1673 ch = source.get()

1674 if not ch:

1675 raise error("unterminated character set", source.string, source.pos)

1676

1677 return Character(ord(ch))

1678

1679def parse_posix_class(source, info):

1680 "Parses a POSIX character class."

1681 negate = source.match("^")

1682 prop_name, name = parse_property_name(source)

1683 if not source.match(":]"):

1684 raise ParseError()

1685

1686 return lookup_property(prop_name, name, not negate, source, posix=True)

1687

1688def float_to_rational(flt):

1689 "Converts a float to a rational pair."

1690 int_part = int(flt)

1691 error = flt - int_part

1692 if abs(error) < 0.0001:

1693 return int_part, 1

1694

1695 den, num = float_to_rational(1.0 / error)

1696

1697 return int_part * den + num, den

1698

1699def numeric_to_rational(numeric):

1700 "Converts a numeric string to a rational string, if possible."

1701 if numeric[ : 1] == "-":

1702 sign, numeric = numeric[0], numeric[1 : ]

1703 else:

1704 sign = ""

1705

1706 parts = numeric.split("/")

1707 if len(parts) == 2:

1708 num, den = float_to_rational(float(parts[0]) / float(parts[1]))

1709 elif len(parts) == 1:

1710 num, den = float_to_rational(float(parts[0]))

1711 else:

1712 raise ValueError()

1713

1714 result = "{}{}/{}".format(sign, num, den)

1715 if result.endswith("/1"):

1716 return result[ : -2]

1717

1718 return result

1719

1720def standardise_name(name):

1721 "Standardises a property or value name."

1722 try:

1723 return numeric_to_rational("".join(name))

1724 except (ValueError, ZeroDivisionError):

1725 return "".join(ch for ch in name if ch not in "_- ").upper()

1726

1727_POSIX_CLASSES = set('ALNUM DIGIT PUNCT XDIGIT'.split())

1728

1729_BINARY_VALUES = set('YES Y NO N TRUE T FALSE F'.split())

1730

1731def lookup_property(property, value, positive, source=None, posix=False, encoding=0):

1732 "Looks up a property."

1733 # Normalise the names (which may still be lists).

1734 property = standardise_name(property) if property else None

1735 value = standardise_name(value)

1736

1737 if (property, value) == ("GENERALCATEGORY", "ASSIGNED"):

1738 property, value, positive = "GENERALCATEGORY", "UNASSIGNED", not positive

1739

1740 if posix and not property and value.upper() in _POSIX_CLASSES:

1741 value = 'POSIX' + value

1742

1743 if property:

1744 # Both the property and the value are provided.

1745 prop = PROPERTIES.get(property)

1746 if not prop:

1747 if not source:

1748 raise error("unknown property")

1749

1750 raise error("unknown property", source.string, source.pos)

1751

1752 prop_id, value_dict = prop

1753 val_id = value_dict.get(value)

1754 if val_id is None:

1755 if not source:

1756 raise error("unknown property value")

1757

1758 raise error("unknown property value", source.string, source.pos)

1759

1760 return Property((prop_id << 16) | val_id, positive, encoding=encoding)

1761

1762 # Only the value is provided.

1763 # It might be the name of a GC, script or block value.

1764 for property in ("GC", "SCRIPT", "BLOCK"):

1765 prop_id, value_dict = PROPERTIES.get(property)

1766 val_id = value_dict.get(value)

1767 if val_id is not None:

1768 return Property((prop_id << 16) | val_id, positive, encoding=encoding)

1769

1770 # It might be the name of a binary property.

1771 prop = PROPERTIES.get(value)

1772 if prop:

1773 prop_id, value_dict = prop

1774 if set(value_dict) == _BINARY_VALUES:

1775 return Property((prop_id << 16) | 1, positive, encoding=encoding)

1776

1777 return Property(prop_id << 16, not positive, encoding=encoding)

1778

1779 # It might be the name of a binary property starting with a prefix.

1780 if value.startswith("IS"):

1781 prop = PROPERTIES.get(value[2 : ])

1782 if prop:

1783 prop_id, value_dict = prop

1784 if "YES" in value_dict:

1785 return Property((prop_id << 16) | 1, positive, encoding=encoding)

1786

1787 # It might be the name of a script or block starting with a prefix.

1788 for prefix, property in (("IS", "SCRIPT"), ("IN", "BLOCK")):

1789 if value.startswith(prefix):

1790 prop_id, value_dict = PROPERTIES.get(property)

1791 val_id = value_dict.get(value[2 : ])

1792 if val_id is not None:

1793 return Property((prop_id << 16) | val_id, positive, encoding=encoding)

1794

1795 # Unknown property.

1796 if not source:

1797 raise error("unknown property")

1798

1799 raise error("unknown property", source.string, source.pos)

1800

1801def _compile_replacement(source, pattern, is_unicode):

1802 "Compiles a replacement template escape sequence."

1803 ch = source.get()

1804 if ch in ALPHA:

1805 # An alphabetic escape sequence.

1806 value = CHARACTER_ESCAPES.get(ch)

1807 if value:

1808 return False, [ord(value)]

1809

1810 if ch in HEX_ESCAPES and (ch == "x" or is_unicode):

1811 # A hexadecimal escape sequence.

1812 return False, [parse_repl_hex_escape(source, HEX_ESCAPES[ch], ch)]

1813

1814 if ch == "g":

1815 # A group preference.

1816 return True, [compile_repl_group(source, pattern)]

1817

1818 if ch == "N" and is_unicode:

1819 # A named character.

1820 value = parse_repl_named_char(source)

1821 if value is not None:

1822 return False, [value]

1823

1824 raise error("bad escape \\%s" % ch, source.string, source.pos)

1825

1826 if isinstance(source.sep, bytes):

1827 octal_mask = 0xFF

1828 else:

1829 octal_mask = 0x1FF

1830

1831 if ch == "0":

1832 # An octal escape sequence.

1833 digits = ch

1834 while len(digits) < 3:

1835 saved_pos = source.pos

1836 ch = source.get()

1837 if ch not in OCT_DIGITS:

1838 source.pos = saved_pos

1839 break

1840 digits += ch

1841

1842 return False, [int(digits, 8) & octal_mask]

1843

1844 if ch in DIGITS:

1845 # Either an octal escape sequence (3 digits) or a group reference (max

1846 # 2 digits).

1847 digits = ch

1848 saved_pos = source.pos

1849 ch = source.get()

1850 if ch in DIGITS:

1851 digits += ch

1852 saved_pos = source.pos

1853 ch = source.get()

1854 if ch and is_octal(digits + ch):

1855 # An octal escape sequence.

1856 return False, [int(digits + ch, 8) & octal_mask]

1857

1858 # A group reference.

1859 source.pos = saved_pos

1860 return True, [int(digits)]

1861

1862 if ch == "\\":

1863 # An escaped backslash is a backslash.

1864 return False, [ord("\\")]

1865

1866 if not ch:

1867 # A trailing backslash.

1868 raise error("bad escape (end of pattern)", source.string, source.pos)

1869

1870 # An escaped non-backslash is a backslash followed by the literal.

1871 return False, [ord("\\"), ord(ch)]

1872

1873def parse_repl_hex_escape(source, expected_len, type):

1874 "Parses a hex escape sequence in a replacement string."

1875 digits = []

1876 for i in range(expected_len):

1877 ch = source.get()

1878 if ch not in HEX_DIGITS:

1879 raise error("incomplete escape \\%s%s" % (type, ''.join(digits)),

1880 source.string, source.pos)

1881 digits.append(ch)

1882

1883 return int("".join(digits), 16)

1884

1885def parse_repl_named_char(source):

1886 "Parses a named character in a replacement string."

1887 saved_pos = source.pos

1888 if source.match("{"):

1889 name = source.get_while(ALPHA | set(" "))

1890

1891 if source.match("}"):

1892 try:

1893 value = unicodedata.lookup(name)

1894 return ord(value)

1895 except KeyError:

1896 raise error("undefined character name", source.string,

1897 source.pos)

1898

1899 source.pos = saved_pos

1900 return None

1901

1902def compile_repl_group(source, pattern):

1903 "Compiles a replacement template group reference."

1904 source.expect("<")

1905 name = parse_name(source, True, True)

1906

1907 source.expect(">")

1908 if name.isdigit():

1909 index = int(name)

1910 if not 0 <= index <= pattern.groups:

1911 raise error("invalid group reference", source.string, source.pos)

1912

1913 return index

1914

1915 try:

1916 return pattern.groupindex[name]

1917 except KeyError:

1918 raise IndexError("unknown group")

1919

1920# The regular expression is parsed into a syntax tree. The different types of

1921# node are defined below.

1922

1923INDENT = " "

1924POSITIVE_OP = 0x1

1925ZEROWIDTH_OP = 0x2

1926FUZZY_OP = 0x4

1927REVERSE_OP = 0x8

1928REQUIRED_OP = 0x10

1929ENCODING_OP_SHIFT = 5

1930

1931POS_TEXT = {False: "NON-MATCH", True: "MATCH"}

1932CASE_TEXT = {NOCASE: "", IGNORECASE: " SIMPLE_IGNORE_CASE", FULLCASE: "",

1933 FULLIGNORECASE: " FULL_IGNORE_CASE"}

1934

1935def make_sequence(items):

1936 if len(items) == 1:

1937 return items[0]

1938 return Sequence(items)

1939

1940# Common base class for all nodes.

1941class RegexBase:

1942 def __init__(self):

1943 self._key = self.__class__

1944

1945 def with_flags(self, positive=None, case_flags=None, zerowidth=None):

1946 if positive is None:

1947 positive = self.positive

1948 else:

1949 positive = bool(positive)

1950 if case_flags is None:

1951 case_flags = self.case_flags

1952 else:

1953 case_flags = CASE_FLAGS_COMBINATIONS[case_flags & CASE_FLAGS]

1954 if zerowidth is None:

1955 zerowidth = self.zerowidth

1956 else:

1957 zerowidth = bool(zerowidth)

1958

1959 if (positive == self.positive and case_flags == self.case_flags and

1960 zerowidth == self.zerowidth):

1961 return self

1962

1963 return self.rebuild(positive, case_flags, zerowidth)

1964

1965 def fix_groups(self, pattern, reverse, fuzzy):

1966 pass

1967

1968 def optimise(self, info, reverse):

1969 return self

1970

1971 def pack_characters(self, info):

1972 return self

1973

1974 def remove_captures(self):

1975 return self

1976

1977 def is_atomic(self):

1978 return True

1979

1980 def can_be_affix(self):

1981 return True

1982

1983 def contains_group(self):

1984 return False

1985

1986 def get_firstset(self, reverse):

1987 raise _FirstSetError()

1988

1989 def has_simple_start(self):

1990 return False

1991

1992 def compile(self, reverse=False, fuzzy=False):

1993 return self._compile(reverse, fuzzy)

1994

1995 def is_empty(self):

1996 return False

1997

1998 def __hash__(self):

1999 return hash(self._key)

2000

2001 def __eq__(self, other):

2002 return type(self) is type(other) and self._key == other._key

2003

2004 def __ne__(self, other):

2005 return not self.__eq__(other)

2006

2007 def get_required_string(self, reverse):

2008 return self.max_width(), None

2009

2010# Base class for zero-width nodes.

2011class ZeroWidthBase(RegexBase):

2012 def __init__(self, positive=True, encoding=0):

2013 RegexBase.__init__(self)

2014 self.positive = bool(positive)

2015 self.encoding = encoding

2016

2017 self._key = self.__class__, self.positive

2018

2019 def get_firstset(self, reverse):

2020 return set([None])

2021

2022 def _compile(self, reverse, fuzzy):

2023 flags = 0

2024 if self.positive:

2025 flags |= POSITIVE_OP

2026 if fuzzy:

2027 flags |= FUZZY_OP

2028 if reverse:

2029 flags |= REVERSE_OP

2030 flags |= self.encoding << ENCODING_OP_SHIFT

2031 return [(self._opcode, flags)]

2032

2033 def dump(self, indent, reverse):

2034 print("{}{} {}{}".format(INDENT * indent, self._op_name,

2035 POS_TEXT[self.positive], ["", " ASCII"][self.encoding]))

2036

2037 def max_width(self):

2038 return 0

2039

2040class Any(RegexBase):

2041 _opcode = {False: OP.ANY, True: OP.ANY_REV}

2042 _op_name = "ANY"

2043

2044 def has_simple_start(self):

2045 return True

2046

2047 def _compile(self, reverse, fuzzy):

2048 flags = 0

2049 if fuzzy:

2050 flags |= FUZZY_OP

2051 return [(self._opcode[reverse], flags)]

2052

2053 def dump(self, indent, reverse):

2054 print("{}{}".format(INDENT * indent, self._op_name))

2055

2056 def max_width(self):

2057 return 1

2058

2059class AnyAll(Any):

2060 _opcode = {False: OP.ANY_ALL, True: OP.ANY_ALL_REV}

2061 _op_name = "ANY_ALL"

2062

2063 def __init__(self):

2064 self.positive = True

2065 self.zerowidth = False

2066 self.case_flags = 0

2067

2068 self._key = self.__class__, self.positive

2069

2070class AnyU(Any):

2071 _opcode = {False: OP.ANY_U, True: OP.ANY_U_REV}

2072 _op_name = "ANY_U"

2073

2074class Atomic(RegexBase):

2075 def __init__(self, subpattern):

2076 RegexBase.__init__(self)

2077 self.subpattern = subpattern

2078

2079 def fix_groups(self, pattern, reverse, fuzzy):

2080 self.subpattern.fix_groups(pattern, reverse, fuzzy)

2081

2082 def optimise(self, info, reverse):

2083 self.subpattern = self.subpattern.optimise(info, reverse)

2084

2085 if self.subpattern.is_empty():

2086 return self.subpattern

2087 return self

2088

2089 def pack_characters(self, info):

2090 self.subpattern = self.subpattern.pack_characters(info)

2091 return self

2092

2093 def remove_captures(self):

2094 self.subpattern = self.subpattern.remove_captures()

2095 return self

2096

2097 def can_be_affix(self):

2098 return self.subpattern.can_be_affix()

2099

2100 def contains_group(self):

2101 return self.subpattern.contains_group()

2102

2103 def get_firstset(self, reverse):

2104 return self.subpattern.get_firstset(reverse)

2105

2106 def has_simple_start(self):

2107 return self.subpattern.has_simple_start()

2108

2109 def _compile(self, reverse, fuzzy):

2110 return ([(OP.ATOMIC, )] + self.subpattern.compile(reverse, fuzzy) +

2111 [(OP.END, )])

2112

2113 def dump(self, indent, reverse):

2114 print("{}ATOMIC".format(INDENT * indent))

2115 self.subpattern.dump(indent + 1, reverse)

2116

2117 def is_empty(self):

2118 return self.subpattern.is_empty()

2119

2120 def __eq__(self, other):

2121 return (type(self) is type(other) and self.subpattern ==

2122 other.subpattern)

2123

2124 def max_width(self):

2125 return self.subpattern.max_width()

2126

2127 def get_required_string(self, reverse):

2128 return self.subpattern.get_required_string(reverse)

2129

2130class Boundary(ZeroWidthBase):

2131 _opcode = OP.BOUNDARY

2132 _op_name = "BOUNDARY"

2133

2134class Branch(RegexBase):

2135 def __init__(self, branches):

2136 RegexBase.__init__(self)

2137 self.branches = branches

2138

2139 def fix_groups(self, pattern, reverse, fuzzy):

2140 for b in self.branches:

2141 b.fix_groups(pattern, reverse, fuzzy)

2142

2143 def optimise(self, info, reverse):

2144 if not self.branches:

2145 return Sequence([])

2146

2147 # Flatten branches within branches.

2148 branches = Branch._flatten_branches(info, reverse, self.branches)

2149

2150 # Move any common prefix or suffix out of the branches.

2151 if reverse:

2152 suffix, branches = Branch._split_common_suffix(info, branches)

2153 prefix = []

2154 else:

2155 prefix, branches = Branch._split_common_prefix(info, branches)

2156 suffix = []

2157

2158 # Try to reduce adjacent single-character branches to sets.

2159 branches = Branch._reduce_to_set(info, reverse, branches)

2160

2161 if len(branches) > 1:

2162 sequence = [Branch(branches)]

2163

2164 if not prefix or not suffix:

2165 # We might be able to add a quick precheck before the branches.

2166 firstset = self._add_precheck(info, reverse, branches)

2167

2168 if firstset:

2169 if reverse:

2170 sequence.append(firstset)

2171 else:

2172 sequence.insert(0, firstset)

2173 else:

2174 sequence = branches

2175

2176 return make_sequence(prefix + sequence + suffix)

2177

2178 def _add_precheck(self, info, reverse, branches):

2179 charset = set()

2180 pos = -1 if reverse else 0

2181

2182 for branch in branches:

2183 if type(branch) is Literal and branch.case_flags == NOCASE:

2184 charset.add(branch.characters[pos])

2185 else:

2186 return

2187

2188 if not charset:

2189 return None

2190

2191 return _check_firstset(info, reverse, [Character(c) for c in charset])

2192

2193 def pack_characters(self, info):

2194 self.branches = [b.pack_characters(info) for b in self.branches]

2195 return self

2196

2197 def remove_captures(self):

2198 self.branches = [b.remove_captures() for b in self.branches]

2199 return self

2200

2201 def is_atomic(self):

2202 return all(b.is_atomic() for b in self.branches)

2203

2204 def can_be_affix(self):

2205 return all(b.can_be_affix() for b in self.branches)

2206

2207 def contains_group(self):

2208 return any(b.contains_group() for b in self.branches)

2209

2210 def get_firstset(self, reverse):

2211 fs = set()

2212 for b in self.branches:

2213 fs |= b.get_firstset(reverse)

2214

2215 return fs or set([None])

2216

2217 def _compile(self, reverse, fuzzy):

2218 if not self.branches:

2219 return []

2220

2221 code = [(OP.BRANCH, )]

2222 for b in self.branches:

2223 code.extend(b.compile(reverse, fuzzy))

2224 code.append((OP.NEXT, ))

2225

2226 code[-1] = (OP.END, )

2227

2228 return code

2229

2230 def dump(self, indent, reverse):

2231 print("{}BRANCH".format(INDENT * indent))

2232 self.branches[0].dump(indent + 1, reverse)

2233 for b in self.branches[1 : ]:

2234 print("{}OR".format(INDENT * indent))

2235 b.dump(indent + 1, reverse)

2236

2237 @staticmethod

2238 def _flatten_branches(info, reverse, branches):

2239 # Flatten the branches so that there aren't branches of branches.

2240 new_branches = []

2241 for b in branches:

2242 b = b.optimise(info, reverse)

2243 if isinstance(b, Branch):

2244 new_branches.extend(b.branches)

2245 else:

2246 new_branches.append(b)

2247

2248 return new_branches

2249

2250 @staticmethod

2251 def _split_common_prefix(info, branches):

2252 # Common leading items can be moved out of the branches.

2253 # Get the items in the branches.

2254 alternatives = []

2255 for b in branches:

2256 if isinstance(b, Sequence):

2257 alternatives.append(b.items)

2258 else:

2259 alternatives.append([b])

2260

2261 # What is the maximum possible length of the prefix?

2262 max_count = min(len(a) for a in alternatives)

2263

2264 # What is the longest common prefix?

2265 prefix = alternatives[0]

2266 pos = 0

2267 end_pos = max_count

2268 while pos < end_pos and prefix[pos].can_be_affix() and all(a[pos] ==

2269 prefix[pos] for a in alternatives):

2270 pos += 1

2271 count = pos

2272

2273 if info.flags & UNICODE:

2274 # We need to check that we're not splitting a sequence of

2275 # characters which could form part of full case-folding.

2276 count = pos

2277 while count > 0 and not all(Branch._can_split(a, count) for a in

2278 alternatives):

2279 count -= 1

2280

2281 # No common prefix is possible.

2282 if count == 0:

2283 return [], branches

2284

2285 # Rebuild the branches.

2286 new_branches = []

2287 for a in alternatives:

2288 new_branches.append(make_sequence(a[count : ]))

2289

2290 return prefix[ : count], new_branches

2291

2292 @staticmethod

2293 def _split_common_suffix(info, branches):

2294 # Common trailing items can be moved out of the branches.

2295 # Get the items in the branches.

2296 alternatives = []

2297 for b in branches:

2298 if isinstance(b, Sequence):

2299 alternatives.append(b.items)

2300 else:

2301 alternatives.append([b])

2302

2303 # What is the maximum possible length of the suffix?

2304 max_count = min(len(a) for a in alternatives)

2305

2306 # What is the longest common suffix?

2307 suffix = alternatives[0]

2308 pos = -1

2309 end_pos = -1 - max_count

2310 while pos > end_pos and suffix[pos].can_be_affix() and all(a[pos] ==

2311 suffix[pos] for a in alternatives):

2312 pos -= 1

2313 count = -1 - pos

2314

2315 if info.flags & UNICODE:

2316 # We need to check that we're not splitting a sequence of

2317 # characters which could form part of full case-folding.

2318 while count > 0 and not all(Branch._can_split_rev(a, count) for a

2319 in alternatives):

2320 count -= 1

2321

2322 # No common suffix is possible.

2323 if count == 0:

2324 return [], branches

2325

2326 # Rebuild the branches.

2327 new_branches = []

2328 for a in alternatives:

2329 new_branches.append(make_sequence(a[ : -count]))

2330

2331 return suffix[-count : ], new_branches

2332

2333 @staticmethod

2334 def _can_split(items, count):

2335 # Check the characters either side of the proposed split.

2336 if not Branch._is_full_case(items, count - 1):

2337 return True

2338

2339 if not Branch._is_full_case(items, count):

2340 return True

2341

2342 # Check whether a 1-1 split would be OK.

2343 if Branch._is_folded(items[count - 1 : count + 1]):

2344 return False

2345

2346 # Check whether a 1-2 split would be OK.

2347 if (Branch._is_full_case(items, count + 2) and

2348 Branch._is_folded(items[count - 1 : count + 2])):

2349 return False

2350

2351 # Check whether a 2-1 split would be OK.

2352 if (Branch._is_full_case(items, count - 2) and

2353 Branch._is_folded(items[count - 2 : count + 1])):

2354 return False

2355

2356 return True

2357

2358 @staticmethod

2359 def _can_split_rev(items, count):

2360 end = len(items)

2361

2362 # Check the characters either side of the proposed split.

2363 if not Branch._is_full_case(items, end - count):

2364 return True

2365

2366 if not Branch._is_full_case(items, end - count - 1):

2367 return True

2368

2369 # Check whether a 1-1 split would be OK.

2370 if Branch._is_folded(items[end - count - 1 : end - count + 1]):

2371 return False

2372

2373 # Check whether a 1-2 split would be OK.

2374 if (Branch._is_full_case(items, end - count + 2) and

2375 Branch._is_folded(items[end - count - 1 : end - count + 2])):

2376 return False

2377

2378 # Check whether a 2-1 split would be OK.

2379 if (Branch._is_full_case(items, end - count - 2) and

2380 Branch._is_folded(items[end - count - 2 : end - count + 1])):

2381 return False

2382

2383 return True

2384

2385 @staticmethod

2386 def _merge_common_prefixes(info, reverse, branches):

2387 # Branches with the same case-sensitive character prefix can be grouped

2388 # together if they are separated only by other branches with a

2389 # character prefix.

2390 prefixed = defaultdict(list)

2391 order = {}

2392 new_branches = []

2393 for b in branches:

2394 if Branch._is_simple_character(b):

2395 # Branch starts with a simple character.

2396 prefixed[b.value].append([b])

2397 order.setdefault(b.value, len(order))

2398 elif (isinstance(b, Sequence) and b.items and

2399 Branch._is_simple_character(b.items[0])):

2400 # Branch starts with a simple character.

2401 prefixed[b.items[0].value].append(b.items)

2402 order.setdefault(b.items[0].value, len(order))

2403 else:

2404 Branch._flush_char_prefix(info, reverse, prefixed, order,

2405 new_branches)

2406

2407 new_branches.append(b)

2408

2409 Branch._flush_char_prefix(info, prefixed, order, new_branches)

2410

2411 return new_branches

2412

2413 @staticmethod

2414 def _is_simple_character(c):

2415 return isinstance(c, Character) and c.positive and not c.case_flags

2416

2417 @staticmethod

2418 def _reduce_to_set(info, reverse, branches):

2419 # Can the branches be reduced to a set?

2420 new_branches = []

2421 items = set()

2422 case_flags = NOCASE

2423 for b in branches:

2424 if isinstance(b, (Character, Property, SetBase)):

2425 # Branch starts with a single character.

2426 if b.case_flags != case_flags:

2427 # Different case sensitivity, so flush.

2428 Branch._flush_set_members(info, reverse, items, case_flags,

2429 new_branches)

2430

2431 case_flags = b.case_flags

2432

2433 items.add(b.with_flags(case_flags=NOCASE))

2434 else:

2435 Branch._flush_set_members(info, reverse, items, case_flags,

2436 new_branches)

2437

2438 new_branches.append(b)

2439

2440 Branch._flush_set_members(info, reverse, items, case_flags,

2441 new_branches)

2442

2443 return new_branches

2444

2445 @staticmethod

2446 def _flush_char_prefix(info, reverse, prefixed, order, new_branches):

2447 # Flush the prefixed branches.

2448 if not prefixed:

2449 return

2450

2451 for value, branches in sorted(prefixed.items(), key=lambda pair:

2452 order[pair[0]]):

2453 if len(branches) == 1:

2454 new_branches.append(make_sequence(branches[0]))

2455 else:

2456 subbranches = []

2457 optional = False

2458 for b in branches:

2459 if len(b) > 1:

2460 subbranches.append(make_sequence(b[1 : ]))

2461 elif not optional:

2462 subbranches.append(Sequence())

2463 optional = True

2464

2465 sequence = Sequence([Character(value), Branch(subbranches)])

2466 new_branches.append(sequence.optimise(info, reverse))

2467

2468 prefixed.clear()

2469 order.clear()

2470

2471 @staticmethod

2472 def _flush_set_members(info, reverse, items, case_flags, new_branches):

2473 # Flush the set members.

2474 if not items:

2475 return

2476

2477 if len(items) == 1:

2478 item = list(items)[0]

2479 else:

2480 item = SetUnion(info, list(items)).optimise(info, reverse)

2481

2482 new_branches.append(item.with_flags(case_flags=case_flags))

2483

2484 items.clear()

2485

2486 @staticmethod

2487 def _is_full_case(items, i):

2488 if not 0 <= i < len(items):

2489 return False

2490

2491 item = items[i]

2492 return (isinstance(item, Character) and item.positive and

2493 (item.case_flags & FULLIGNORECASE) == FULLIGNORECASE)

2494

2495 @staticmethod

2496 def _is_folded(items):

2497 if len(items) < 2:

2498 return False

2499

2500 for i in items:

2501 if (not isinstance(i, Character) or not i.positive or not

2502 i.case_flags):

2503 return False

2504

2505 folded = "".join(chr(i.value) for i in items)

2506 folded = _regex.fold_case(FULL_CASE_FOLDING, folded)

2507

2508 # Get the characters which expand to multiple codepoints on folding.

2509 expanding_chars = _regex.get_expand_on_folding()

2510

2511 for c in expanding_chars:

2512 if folded == _regex.fold_case(FULL_CASE_FOLDING, c):

2513 return True

2514

2515 return False

2516

2517 def is_empty(self):

2518 return all(b.is_empty() for b in self.branches)

2519

2520 def __eq__(self, other):

2521 return type(self) is type(other) and self.branches == other.branches

2522

2523 def max_width(self):

2524 return max(b.max_width() for b in self.branches)

2525

2526class CallGroup(RegexBase):

2527 def __init__(self, info, group, position):

2528 RegexBase.__init__(self)

2529 self.info = info

2530 self.group = group

2531 self.position = position

2532

2533 self._key = self.__class__, self.group

2534

2535 def fix_groups(self, pattern, reverse, fuzzy):

2536 try:

2537 self.group = int(self.group)

2538 except ValueError:

2539 try:

2540 self.group = self.info.group_index[self.group]

2541 except KeyError:

2542 raise error("invalid group reference", pattern, self.position)

2543

2544 if not 0 <= self.group <= self.info.group_count:

2545 raise error("unknown group", pattern, self.position)

2546

2547 if self.group > 0 and self.info.open_group_count[self.group] > 1:

2548 raise error("ambiguous group reference", pattern, self.position)

2549

2550 self.info.group_calls.append((self, reverse, fuzzy))

2551

2552 self._key = self.__class__, self.group

2553

2554 def remove_captures(self):

2555 raise error("group reference not allowed", self.pattern, self.position)

2556

2557 def _compile(self, reverse, fuzzy):

2558 return [(OP.GROUP_CALL, self.call_ref)]

2559

2560 def dump(self, indent, reverse):

2561 print("{}GROUP_CALL {}".format(INDENT * indent, self.group))

2562

2563 def __eq__(self, other):

2564 return type(self) is type(other) and self.group == other.group

2565

2566 def max_width(self):

2567 return UNLIMITED

2568

2569 def __del__(self):

2570 self.info = None

2571

2572class CallRef(RegexBase):

2573 def __init__(self, ref, parsed):

2574 self.ref = ref

2575 self.parsed = parsed

2576

2577 def _compile(self, reverse, fuzzy):

2578 return ([(OP.CALL_REF, self.ref)] + self.parsed._compile(reverse,

2579 fuzzy) + [(OP.END, )])

2580

2581class Character(RegexBase):

2582 _opcode = {(NOCASE, False): OP.CHARACTER, (IGNORECASE, False):

2583 OP.CHARACTER_IGN, (FULLCASE, False): OP.CHARACTER, (FULLIGNORECASE,

2584 False): OP.CHARACTER_IGN, (NOCASE, True): OP.CHARACTER_REV, (IGNORECASE,

2585 True): OP.CHARACTER_IGN_REV, (FULLCASE, True): OP.CHARACTER_REV,

2586 (FULLIGNORECASE, True): OP.CHARACTER_IGN_REV}

2587

2588 def __init__(self, value, positive=True, case_flags=NOCASE,

2589 zerowidth=False):

2590 RegexBase.__init__(self)

2591 self.value = value

2592 self.positive = bool(positive)

2593 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

2594 self.zerowidth = bool(zerowidth)

2595

2596 if (self.positive and (self.case_flags & FULLIGNORECASE) ==

2597 FULLIGNORECASE):

2598 self.folded = _regex.fold_case(FULL_CASE_FOLDING, chr(self.value))

2599 else:

2600 self.folded = chr(self.value)

2601

2602 self._key = (self.__class__, self.value, self.positive,

2603 self.case_flags, self.zerowidth)

2604

2605 def rebuild(self, positive, case_flags, zerowidth):

2606 return Character(self.value, positive, case_flags, zerowidth)

2607

2608 def optimise(self, info, reverse, in_set=False):

2609 return self

2610

2611 def get_firstset(self, reverse):

2612 return set([self])

2613

2614 def has_simple_start(self):

2615 return True

2616

2617 def _compile(self, reverse, fuzzy):

2618 flags = 0

2619 if self.positive:

2620 flags |= POSITIVE_OP

2621 if self.zerowidth:

2622 flags |= ZEROWIDTH_OP

2623 if fuzzy:

2624 flags |= FUZZY_OP

2625

2626 code = PrecompiledCode([self._opcode[self.case_flags, reverse], flags,

2627 self.value])

2628

2629 if len(self.folded) > 1:

2630 # The character expands on full case-folding.

2631 code = Branch([code, String([ord(c) for c in self.folded],

2632 case_flags=self.case_flags)])

2633

2634 return code.compile(reverse, fuzzy)

2635

2636 def dump(self, indent, reverse):

2637 display = ascii(chr(self.value)).lstrip("bu")

2638 print("{}CHARACTER {} {}{}".format(INDENT * indent,

2639 POS_TEXT[self.positive], display, CASE_TEXT[self.case_flags]))

2640

2641 def matches(self, ch):

2642 return (ch == self.value) == self.positive

2643

2644 def max_width(self):

2645 return len(self.folded)

2646

2647 def get_required_string(self, reverse):

2648 if not self.positive:

2649 return 1, None

2650

2651 self.folded_characters = tuple(ord(c) for c in self.folded)

2652

2653 return 0, self

2654

2655class Conditional(RegexBase):

2656 def __init__(self, info, group, yes_item, no_item, position):

2657 RegexBase.__init__(self)

2658 self.info = info

2659 self.group = group

2660 self.yes_item = yes_item

2661 self.no_item = no_item

2662 self.position = position

2663

2664 def fix_groups(self, pattern, reverse, fuzzy):

2665 try:

2666 self.group = int(self.group)

2667 except ValueError:

2668 try:

2669 self.group = self.info.group_index[self.group]

2670 except KeyError:

2671 if self.group == 'DEFINE':

2672 # 'DEFINE' is a special name unless there's a group with

2673 # that name.

2674 self.group = 0

2675 else:

2676 raise error("unknown group", pattern, self.position)

2677

2678 if not 0 <= self.group <= self.info.group_count:

2679 raise error("invalid group reference", pattern, self.position)

2680

2681 self.yes_item.fix_groups(pattern, reverse, fuzzy)

2682 self.no_item.fix_groups(pattern, reverse, fuzzy)

2683

2684 def optimise(self, info, reverse):

2685 yes_item = self.yes_item.optimise(info, reverse)

2686 no_item = self.no_item.optimise(info, reverse)

2687

2688 return Conditional(info, self.group, yes_item, no_item, self.position)

2689

2690 def pack_characters(self, info):

2691 self.yes_item = self.yes_item.pack_characters(info)

2692 self.no_item = self.no_item.pack_characters(info)

2693 return self

2694

2695 def remove_captures(self):

2696 self.yes_item = self.yes_item.remove_captures()

2697 self.no_item = self.no_item.remove_captures()

2698

2699 def is_atomic(self):

2700 return self.yes_item.is_atomic() and self.no_item.is_atomic()

2701

2702 def can_be_affix(self):

2703 return self.yes_item.can_be_affix() and self.no_item.can_be_affix()

2704

2705 def contains_group(self):

2706 return self.yes_item.contains_group() or self.no_item.contains_group()

2707

2708 def get_firstset(self, reverse):

2709 return (self.yes_item.get_firstset(reverse) |

2710 self.no_item.get_firstset(reverse))

2711

2712 def _compile(self, reverse, fuzzy):

2713 code = [(OP.GROUP_EXISTS, self.group)]

2714 code.extend(self.yes_item.compile(reverse, fuzzy))

2715 add_code = self.no_item.compile(reverse, fuzzy)

2716 if add_code:

2717 code.append((OP.NEXT, ))

2718 code.extend(add_code)

2719

2720 code.append((OP.END, ))

2721

2722 return code

2723

2724 def dump(self, indent, reverse):

2725 print("{}GROUP_EXISTS {}".format(INDENT * indent, self.group))

2726 self.yes_item.dump(indent + 1, reverse)

2727 if not self.no_item.is_empty():

2728 print("{}OR".format(INDENT * indent))

2729 self.no_item.dump(indent + 1, reverse)

2730

2731 def is_empty(self):

2732 return self.yes_item.is_empty() and self.no_item.is_empty()

2733

2734 def __eq__(self, other):

2735 return type(self) is type(other) and (self.group, self.yes_item,

2736 self.no_item) == (other.group, other.yes_item, other.no_item)

2737

2738 def max_width(self):

2739 return max(self.yes_item.max_width(), self.no_item.max_width())

2740

2741 def __del__(self):

2742 self.info = None

2743

2744class DefaultBoundary(ZeroWidthBase):

2745 _opcode = OP.DEFAULT_BOUNDARY

2746 _op_name = "DEFAULT_BOUNDARY"

2747

2748class DefaultEndOfWord(ZeroWidthBase):

2749 _opcode = OP.DEFAULT_END_OF_WORD

2750 _op_name = "DEFAULT_END_OF_WORD"

2751

2752class DefaultStartOfWord(ZeroWidthBase):

2753 _opcode = OP.DEFAULT_START_OF_WORD

2754 _op_name = "DEFAULT_START_OF_WORD"

2755

2756class EndOfLine(ZeroWidthBase):

2757 _opcode = OP.END_OF_LINE

2758 _op_name = "END_OF_LINE"

2759

2760class EndOfLineU(EndOfLine):

2761 _opcode = OP.END_OF_LINE_U

2762 _op_name = "END_OF_LINE_U"

2763

2764class EndOfString(ZeroWidthBase):

2765 _opcode = OP.END_OF_STRING

2766 _op_name = "END_OF_STRING"

2767

2768class EndOfStringLine(ZeroWidthBase):

2769 _opcode = OP.END_OF_STRING_LINE

2770 _op_name = "END_OF_STRING_LINE"

2771

2772class EndOfStringLineU(EndOfStringLine):

2773 _opcode = OP.END_OF_STRING_LINE_U

2774 _op_name = "END_OF_STRING_LINE_U"

2775

2776class EndOfWord(ZeroWidthBase):

2777 _opcode = OP.END_OF_WORD

2778 _op_name = "END_OF_WORD"

2779

2780class Failure(ZeroWidthBase):

2781 _op_name = "FAILURE"

2782

2783 def _compile(self, reverse, fuzzy):

2784 return [(OP.FAILURE, )]

2785

2786class Fuzzy(RegexBase):

2787 def __init__(self, subpattern, constraints=None):

2788 RegexBase.__init__(self)

2789 if constraints is None:

2790 constraints = {}

2791 self.subpattern = subpattern

2792 self.constraints = constraints

2793

2794 # If an error type is mentioned in the cost equation, then its maximum

2795 # defaults to unlimited.

2796 if "cost" in constraints:

2797 for e in "dis":

2798 if e in constraints["cost"]:

2799 constraints.setdefault(e, (0, None))

2800

2801 # If any error type is mentioned, then all the error maxima default to

2802 # 0, otherwise they default to unlimited.

2803 if set(constraints) & set("dis"):

2804 for e in "dis":

2805 constraints.setdefault(e, (0, 0))

2806 else:

2807 for e in "dis":

2808 constraints.setdefault(e, (0, None))

2809

2810 # The maximum of the generic error type defaults to unlimited.

2811 constraints.setdefault("e", (0, None))

2812

2813 # The cost equation defaults to equal costs. Also, the cost of any

2814 # error type not mentioned in the cost equation defaults to 0.

2815 if "cost" in constraints:

2816 for e in "dis":

2817 constraints["cost"].setdefault(e, 0)

2818 else:

2819 constraints["cost"] = {"d": 1, "i": 1, "s": 1, "max":

2820 constraints["e"][1]}

2821

2822 def fix_groups(self, pattern, reverse, fuzzy):

2823 self.subpattern.fix_groups(pattern, reverse, True)

2824

2825 def pack_characters(self, info):

2826 self.subpattern = self.subpattern.pack_characters(info)

2827 return self

2828

2829 def remove_captures(self):

2830 self.subpattern = self.subpattern.remove_captures()

2831 return self

2832

2833 def is_atomic(self):

2834 return self.subpattern.is_atomic()

2835

2836 def contains_group(self):

2837 return self.subpattern.contains_group()

2838

2839 def _compile(self, reverse, fuzzy):

2840 # The individual limits.

2841 arguments = []

2842 for e in "dise":

2843 v = self.constraints[e]

2844 arguments.append(v[0])

2845 arguments.append(UNLIMITED if v[1] is None else v[1])

2846

2847 # The coeffs of the cost equation.

2848 for e in "dis":

2849 arguments.append(self.constraints["cost"][e])

2850

2851 # The maximum of the cost equation.

2852 v = self.constraints["cost"]["max"]

2853 arguments.append(UNLIMITED if v is None else v)

2854

2855 flags = 0

2856 if reverse:

2857 flags |= REVERSE_OP

2858

2859 test = self.constraints.get("test")

2860

2861 if test:

2862 return ([(OP.FUZZY_EXT, flags) + tuple(arguments)] +

2863 test.compile(reverse, True) + [(OP.NEXT,)] +

2864 self.subpattern.compile(reverse, True) + [(OP.END,)])

2865

2866 return ([(OP.FUZZY, flags) + tuple(arguments)] +

2867 self.subpattern.compile(reverse, True) + [(OP.END,)])

2868

2869 def dump(self, indent, reverse):

2870 constraints = self._constraints_to_string()

2871 if constraints:

2872 constraints = " " + constraints

2873 print("{}FUZZY{}".format(INDENT * indent, constraints))

2874 self.subpattern.dump(indent + 1, reverse)

2875

2876 def is_empty(self):

2877 return self.subpattern.is_empty()

2878

2879 def __eq__(self, other):

2880 return (type(self) is type(other) and self.subpattern ==

2881 other.subpattern and self.constraints == other.constraints)

2882

2883 def max_width(self):

2884 return UNLIMITED

2885

2886 def _constraints_to_string(self):

2887 constraints = []

2888

2889 for name in "ids":

2890 min, max = self.constraints[name]

2891 if max == 0:

2892 continue

2893

2894 con = ""

2895

2896 if min > 0:

2897 con = "{}<=".format(min)

2898

2899 con += name

2900

2901 if max is not None:

2902 con += "<={}".format(max)

2903

2904 constraints.append(con)

2905

2906 cost = []

2907 for name in "ids":

2908 coeff = self.constraints["cost"][name]

2909 if coeff > 0:

2910 cost.append("{}{}".format(coeff, name))

2911

2912 limit = self.constraints["cost"]["max"]

2913 if limit is not None and limit > 0:

2914 cost = "{}<={}".format("+".join(cost), limit)

2915 constraints.append(cost)

2916

2917 return ",".join(constraints)

2918

2919class Grapheme(RegexBase):

2920 def _compile(self, reverse, fuzzy):

2921 # Match at least 1 character until a grapheme boundary is reached. Note

2922 # that this is the same whether matching forwards or backwards.

2923 grapheme_matcher = Atomic(Sequence([LazyRepeat(AnyAll(), 1, None),

2924 GraphemeBoundary()]))

2925

2926 return grapheme_matcher.compile(reverse, fuzzy)

2927

2928 def dump(self, indent, reverse):

2929 print("{}GRAPHEME".format(INDENT * indent))

2930

2931 def max_width(self):

2932 return UNLIMITED

2933

2934class GraphemeBoundary:

2935 def compile(self, reverse, fuzzy):

2936 return [(OP.GRAPHEME_BOUNDARY, 1)]

2937

2938class GreedyRepeat(RegexBase):

2939 _opcode = OP.GREEDY_REPEAT

2940 _op_name = "GREEDY_REPEAT"

2941

2942 def __init__(self, subpattern, min_count, max_count):

2943 RegexBase.__init__(self)

2944 self.subpattern = subpattern

2945 self.min_count = min_count

2946 self.max_count = max_count

2947

2948 def fix_groups(self, pattern, reverse, fuzzy):

2949 self.subpattern.fix_groups(pattern, reverse, fuzzy)

2950

2951 def optimise(self, info, reverse):

2952 subpattern = self.subpattern.optimise(info, reverse)

2953

2954 return type(self)(subpattern, self.min_count, self.max_count)

2955

2956 def pack_characters(self, info):

2957 self.subpattern = self.subpattern.pack_characters(info)

2958 return self

2959

2960 def remove_captures(self):

2961 self.subpattern = self.subpattern.remove_captures()

2962 return self

2963

2964 def is_atomic(self):

2965 return self.min_count == self.max_count and self.subpattern.is_atomic()

2966

2967 def can_be_affix(self):

2968 return False

2969

2970 def contains_group(self):

2971 return self.subpattern.contains_group()

2972

2973 def get_firstset(self, reverse):

2974 fs = self.subpattern.get_firstset(reverse)

2975 if self.min_count == 0:

2976 fs.add(None)

2977

2978 return fs

2979

2980 def _compile(self, reverse, fuzzy):

2981 repeat = [self._opcode, self.min_count]

2982 if self.max_count is None:

2983 repeat.append(UNLIMITED)

2984 else:

2985 repeat.append(self.max_count)

2986

2987 subpattern = self.subpattern.compile(reverse, fuzzy)

2988 if not subpattern:

2989 return []

2990

2991 return ([tuple(repeat)] + subpattern + [(OP.END, )])

2992

2993 def dump(self, indent, reverse):

2994 if self.max_count is None:

2995 limit = "INF"

2996 else:

2997 limit = self.max_count

2998 print("{}{} {} {}".format(INDENT * indent, self._op_name,

2999 self.min_count, limit))

3000

3001 self.subpattern.dump(indent + 1, reverse)

3002

3003 def is_empty(self):

3004 return self.subpattern.is_empty()

3005

3006 def __eq__(self, other):

3007 return type(self) is type(other) and (self.subpattern, self.min_count,

3008 self.max_count) == (other.subpattern, other.min_count,

3009 other.max_count)

3010

3011 def max_width(self):

3012 if self.max_count is None:

3013 return UNLIMITED

3014

3015 return self.subpattern.max_width() * self.max_count

3016

3017 def get_required_string(self, reverse):

3018 max_count = UNLIMITED if self.max_count is None else self.max_count

3019 if self.min_count == 0:

3020 w = self.subpattern.max_width() * max_count

3021 return min(w, UNLIMITED), None

3022

3023 ofs, req = self.subpattern.get_required_string(reverse)

3024 if req:

3025 return ofs, req

3026

3027 w = self.subpattern.max_width() * max_count

3028 return min(w, UNLIMITED), None

3029

3030class PossessiveRepeat(GreedyRepeat):

3031 def is_atomic(self):

3032 return True

3033

3034 def _compile(self, reverse, fuzzy):

3035 subpattern = self.subpattern.compile(reverse, fuzzy)

3036 if not subpattern:

3037 return []

3038

3039 repeat = [self._opcode, self.min_count]

3040 if self.max_count is None:

3041 repeat.append(UNLIMITED)

3042 else:

3043 repeat.append(self.max_count)

3044

3045 return ([(OP.ATOMIC, ), tuple(repeat)] + subpattern + [(OP.END, ),

3046 (OP.END, )])

3047

3048 def dump(self, indent, reverse):

3049 print("{}ATOMIC".format(INDENT * indent))

3050

3051 if self.max_count is None:

3052 limit = "INF"

3053 else:

3054 limit = self.max_count

3055 print("{}{} {} {}".format(INDENT * (indent + 1), self._op_name,

3056 self.min_count, limit))

3057

3058 self.subpattern.dump(indent + 2, reverse)

3059

3060class Group(RegexBase):

3061 def __init__(self, info, group, subpattern):

3062 RegexBase.__init__(self)

3063 self.info = info

3064 self.group = group

3065 self.subpattern = subpattern

3066

3067 self.call_ref = None

3068

3069 def fix_groups(self, pattern, reverse, fuzzy):

3070 self.info.defined_groups[self.group] = (self, reverse, fuzzy)

3071 self.subpattern.fix_groups(pattern, reverse, fuzzy)

3072

3073 def optimise(self, info, reverse):

3074 subpattern = self.subpattern.optimise(info, reverse)

3075

3076 return Group(self.info, self.group, subpattern)

3077

3078 def pack_characters(self, info):

3079 self.subpattern = self.subpattern.pack_characters(info)

3080 return self

3081

3082 def remove_captures(self):

3083 return self.subpattern.remove_captures()

3084

3085 def is_atomic(self):

3086 return self.subpattern.is_atomic()

3087

3088 def can_be_affix(self):

3089 return False

3090

3091 def contains_group(self):

3092 return True

3093

3094 def get_firstset(self, reverse):

3095 return self.subpattern.get_firstset(reverse)

3096

3097 def has_simple_start(self):

3098 return self.subpattern.has_simple_start()

3099

3100 def _compile(self, reverse, fuzzy):

3101 code = []

3102

3103 public_group = private_group = self.group

3104 if private_group < 0:

3105 public_group = self.info.private_groups[private_group]

3106 private_group = self.info.group_count - private_group

3107

3108 key = self.group, reverse, fuzzy

3109 ref = self.info.call_refs.get(key)

3110 if ref is not None:

3111 code += [(OP.CALL_REF, ref)]

3112

3113 code += [(OP.GROUP, int(not reverse), private_group, public_group)]

3114 code += self.subpattern.compile(reverse, fuzzy)

3115 code += [(OP.END, )]

3116

3117 if ref is not None:

3118 code += [(OP.END, )]

3119

3120 return code

3121

3122 def dump(self, indent, reverse):

3123 group = self.group

3124 if group < 0:

3125 group = self.info.private_groups[group]

3126 print("{}GROUP {}".format(INDENT * indent, group))

3127 self.subpattern.dump(indent + 1, reverse)

3128

3129 def __eq__(self, other):

3130 return (type(self) is type(other) and (self.group, self.subpattern) ==

3131 (other.group, other.subpattern))

3132

3133 def max_width(self):

3134 return self.subpattern.max_width()

3135

3136 def get_required_string(self, reverse):

3137 return self.subpattern.get_required_string(reverse)

3138

3139 def __del__(self):

3140 self.info = None

3141

3142class Keep(ZeroWidthBase):

3143 _opcode = OP.KEEP

3144 _op_name = "KEEP"

3145

3146class LazyRepeat(GreedyRepeat):

3147 _opcode = OP.LAZY_REPEAT

3148 _op_name = "LAZY_REPEAT"

3149

3150class LookAround(RegexBase):

3151 _dir_text = {False: "AHEAD", True: "BEHIND"}

3152

3153 def __init__(self, behind, positive, subpattern):

3154 RegexBase.__init__(self)

3155 self.behind = bool(behind)

3156 self.positive = bool(positive)

3157 self.subpattern = subpattern

3158

3159 def fix_groups(self, pattern, reverse, fuzzy):

3160 self.subpattern.fix_groups(pattern, self.behind, fuzzy)

3161

3162 def optimise(self, info, reverse):

3163 subpattern = self.subpattern.optimise(info, self.behind)

3164 if self.positive and subpattern.is_empty():

3165 return subpattern

3166

3167 return LookAround(self.behind, self.positive, subpattern)

3168

3169 def pack_characters(self, info):

3170 self.subpattern = self.subpattern.pack_characters(info)

3171 return self

3172

3173 def remove_captures(self):

3174 return self.subpattern.remove_captures()

3175

3176 def is_atomic(self):

3177 return self.subpattern.is_atomic()

3178

3179 def can_be_affix(self):

3180 return self.subpattern.can_be_affix()

3181

3182 def contains_group(self):

3183 return self.subpattern.contains_group()

3184

3185 def get_firstset(self, reverse):

3186 if self.positive and self.behind == reverse:

3187 return self.subpattern.get_firstset(reverse)

3188

3189 return set([None])

3190

3191 def _compile(self, reverse, fuzzy):

3192 flags = 0

3193 if self.positive:

3194 flags |= POSITIVE_OP

3195 if fuzzy:

3196 flags |= FUZZY_OP

3197 if reverse:

3198 flags |= REVERSE_OP

3199

3200 return ([(OP.LOOKAROUND, flags, int(not self.behind))] +

3201 self.subpattern.compile(self.behind) + [(OP.END, )])

3202

3203 def dump(self, indent, reverse):

3204 print("{}LOOK{} {}".format(INDENT * indent,

3205 self._dir_text[self.behind], POS_TEXT[self.positive]))

3206 self.subpattern.dump(indent + 1, self.behind)

3207

3208 def is_empty(self):

3209 return self.positive and self.subpattern.is_empty()

3210

3211 def __eq__(self, other):

3212 return type(self) is type(other) and (self.behind, self.positive,

3213 self.subpattern) == (other.behind, other.positive, other.subpattern)

3214

3215 def max_width(self):

3216 return 0

3217

3218class LookAroundConditional(RegexBase):

3219 _dir_text = {False: "AHEAD", True: "BEHIND"}

3220

3221 def __init__(self, behind, positive, subpattern, yes_item, no_item):

3222 RegexBase.__init__(self)

3223 self.behind = bool(behind)

3224 self.positive = bool(positive)

3225 self.subpattern = subpattern

3226 self.yes_item = yes_item

3227 self.no_item = no_item

3228

3229 def fix_groups(self, pattern, reverse, fuzzy):

3230 self.subpattern.fix_groups(pattern, reverse, fuzzy)

3231 self.yes_item.fix_groups(pattern, reverse, fuzzy)

3232 self.no_item.fix_groups(pattern, reverse, fuzzy)

3233

3234 def optimise(self, info, reverse):

3235 subpattern = self.subpattern.optimise(info, self.behind)

3236 yes_item = self.yes_item.optimise(info, self.behind)

3237 no_item = self.no_item.optimise(info, self.behind)

3238

3239 return LookAroundConditional(self.behind, self.positive, subpattern,

3240 yes_item, no_item)

3241

3242 def pack_characters(self, info):

3243 self.subpattern = self.subpattern.pack_characters(info)

3244 self.yes_item = self.yes_item.pack_characters(info)

3245 self.no_item = self.no_item.pack_characters(info)

3246 return self

3247

3248 def remove_captures(self):

3249 self.subpattern = self.subpattern.remove_captures()

3250 self.yes_item = self.yes_item.remove_captures()

3251 self.no_item = self.no_item.remove_captures()

3252

3253 def is_atomic(self):

3254 return (self.subpattern.is_atomic() and self.yes_item.is_atomic() and

3255 self.no_item.is_atomic())

3256

3257 def can_be_affix(self):

3258 return (self.subpattern.can_be_affix() and self.yes_item.can_be_affix()

3259 and self.no_item.can_be_affix())

3260

3261 def contains_group(self):

3262 return (self.subpattern.contains_group() or

3263 self.yes_item.contains_group() or self.no_item.contains_group())

3264

3265 def _compile(self, reverse, fuzzy):

3266 code = [(OP.CONDITIONAL, int(self.positive), int(not self.behind))]

3267 code.extend(self.subpattern.compile(self.behind, fuzzy))

3268 code.append((OP.NEXT, ))

3269 code.extend(self.yes_item.compile(reverse, fuzzy))

3270 add_code = self.no_item.compile(reverse, fuzzy)

3271 if add_code:

3272 code.append((OP.NEXT, ))

3273 code.extend(add_code)

3274

3275 code.append((OP.END, ))

3276

3277 return code

3278

3279 def dump(self, indent, reverse):

3280 print("{}CONDITIONAL {} {}".format(INDENT * indent,

3281 self._dir_text[self.behind], POS_TEXT[self.positive]))

3282 self.subpattern.dump(indent + 1, self.behind)

3283 print("{}EITHER".format(INDENT * indent))

3284 self.yes_item.dump(indent + 1, reverse)

3285 if not self.no_item.is_empty():

3286 print("{}OR".format(INDENT * indent))

3287 self.no_item.dump(indent + 1, reverse)

3288

3289 def is_empty(self):

3290 return self.subpattern.is_empty() and self.yes_item.is_empty()

3291

3292 def __eq__(self, other):

3293 return type(self) is type(other) and (self.subpattern, self.yes_item,

3294 self.no_item) == (other.subpattern, other.yes_item, other.no_item)

3295

3296 def max_width(self):

3297 return max(self.yes_item.max_width(), self.no_item.max_width())

3298

3299 def get_required_string(self, reverse):

3300 return self.max_width(), None

3301

3302class PrecompiledCode(RegexBase):

3303 def __init__(self, code):

3304 self.code = code

3305

3306 def _compile(self, reverse, fuzzy):

3307 return [tuple(self.code)]

3308

3309class Property(RegexBase):

3310 _opcode = {(NOCASE, False): OP.PROPERTY, (IGNORECASE, False):

3311 OP.PROPERTY_IGN, (FULLCASE, False): OP.PROPERTY, (FULLIGNORECASE, False):

3312 OP.PROPERTY_IGN, (NOCASE, True): OP.PROPERTY_REV, (IGNORECASE, True):

3313 OP.PROPERTY_IGN_REV, (FULLCASE, True): OP.PROPERTY_REV, (FULLIGNORECASE,

3314 True): OP.PROPERTY_IGN_REV}

3315

3316 def __init__(self, value, positive=True, case_flags=NOCASE,

3317 zerowidth=False, encoding=0):

3318 RegexBase.__init__(self)

3319 self.value = value

3320 self.positive = bool(positive)

3321 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

3322 self.zerowidth = bool(zerowidth)

3323 self.encoding = encoding

3324

3325 self._key = (self.__class__, self.value, self.positive,

3326 self.case_flags, self.zerowidth)

3327

3328 def rebuild(self, positive, case_flags, zerowidth):

3329 return Property(self.value, positive, case_flags, zerowidth,

3330 self.encoding)

3331

3332 def optimise(self, info, reverse, in_set=False):

3333 return self

3334

3335 def get_firstset(self, reverse):

3336 return set([self])

3337

3338 def has_simple_start(self):

3339 return True

3340

3341 def _compile(self, reverse, fuzzy):

3342 flags = 0

3343 if self.positive:

3344 flags |= POSITIVE_OP

3345 if self.zerowidth:

3346 flags |= ZEROWIDTH_OP

3347 if fuzzy:

3348 flags |= FUZZY_OP

3349 flags |= self.encoding << ENCODING_OP_SHIFT

3350 return [(self._opcode[self.case_flags, reverse], flags, self.value)]

3351

3352 def dump(self, indent, reverse):

3353 prop = PROPERTY_NAMES[self.value >> 16]

3354 name, value = prop[0], prop[1][self.value & 0xFFFF]

3355 print("{}PROPERTY {} {}:{}{}{}".format(INDENT * indent,

3356 POS_TEXT[self.positive], name, value, CASE_TEXT[self.case_flags],

3357 ["", " ASCII"][self.encoding]))

3358

3359 def matches(self, ch):

3360 return _regex.has_property_value(self.value, ch) == self.positive

3361

3362 def max_width(self):

3363 return 1

3364

3365class Prune(ZeroWidthBase):

3366 _op_name = "PRUNE"

3367

3368 def _compile(self, reverse, fuzzy):

3369 return [(OP.PRUNE, )]

3370

3371class Range(RegexBase):

3372 _opcode = {(NOCASE, False): OP.RANGE, (IGNORECASE, False): OP.RANGE_IGN,

3373 (FULLCASE, False): OP.RANGE, (FULLIGNORECASE, False): OP.RANGE_IGN,

3374 (NOCASE, True): OP.RANGE_REV, (IGNORECASE, True): OP.RANGE_IGN_REV,

3375 (FULLCASE, True): OP.RANGE_REV, (FULLIGNORECASE, True): OP.RANGE_IGN_REV}

3376 _op_name = "RANGE"

3377

3378 def __init__(self, lower, upper, positive=True, case_flags=NOCASE,

3379 zerowidth=False):

3380 RegexBase.__init__(self)

3381 self.lower = lower

3382 self.upper = upper

3383 self.positive = bool(positive)

3384 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

3385 self.zerowidth = bool(zerowidth)

3386

3387 self._key = (self.__class__, self.lower, self.upper, self.positive,

3388 self.case_flags, self.zerowidth)

3389

3390 def rebuild(self, positive, case_flags, zerowidth):

3391 return Range(self.lower, self.upper, positive, case_flags, zerowidth)

3392

3393 def optimise(self, info, reverse, in_set=False):

3394 # Is the range case-sensitive?

3395 if not self.positive or not (self.case_flags & IGNORECASE) or in_set:

3396 return self

3397

3398 # Is full case-folding possible?

3399 if (not (info.flags & UNICODE) or (self.case_flags & FULLIGNORECASE) !=

3400 FULLIGNORECASE):

3401 return self

3402

3403 # Get the characters which expand to multiple codepoints on folding.

3404 expanding_chars = _regex.get_expand_on_folding()

3405

3406 # Get the folded characters in the range.

3407 items = []

3408 for ch in expanding_chars:

3409 if self.lower <= ord(ch) <= self.upper:

3410 folded = _regex.fold_case(FULL_CASE_FOLDING, ch)

3411 items.append(String([ord(c) for c in folded],

3412 case_flags=self.case_flags))

3413

3414 if not items:

3415 # We can fall back to simple case-folding.

3416 return self

3417

3418 if len(items) < self.upper - self.lower + 1:

3419 # Not all the characters are covered by the full case-folding.

3420 items.insert(0, self)

3421

3422 return Branch(items)

3423

3424 def _compile(self, reverse, fuzzy):

3425 flags = 0

3426 if self.positive:

3427 flags |= POSITIVE_OP

3428 if self.zerowidth:

3429 flags |= ZEROWIDTH_OP

3430 if fuzzy:

3431 flags |= FUZZY_OP

3432 return [(self._opcode[self.case_flags, reverse], flags, self.lower,

3433 self.upper)]

3434

3435 def dump(self, indent, reverse):

3436 display_lower = ascii(chr(self.lower)).lstrip("bu")

3437 display_upper = ascii(chr(self.upper)).lstrip("bu")

3438 print("{}RANGE {} {} {}{}".format(INDENT * indent,

3439 POS_TEXT[self.positive], display_lower, display_upper,

3440 CASE_TEXT[self.case_flags]))

3441

3442 def matches(self, ch):

3443 return (self.lower <= ch <= self.upper) == self.positive

3444

3445 def max_width(self):

3446 return 1

3447

3448class RefGroup(RegexBase):

3449 _opcode = {(NOCASE, False): OP.REF_GROUP, (IGNORECASE, False):

3450 OP.REF_GROUP_IGN, (FULLCASE, False): OP.REF_GROUP, (FULLIGNORECASE,

3451 False): OP.REF_GROUP_FLD, (NOCASE, True): OP.REF_GROUP_REV, (IGNORECASE,

3452 True): OP.REF_GROUP_IGN_REV, (FULLCASE, True): OP.REF_GROUP_REV,

3453 (FULLIGNORECASE, True): OP.REF_GROUP_FLD_REV}

3454

3455 def __init__(self, info, group, position, case_flags=NOCASE):

3456 RegexBase.__init__(self)

3457 self.info = info

3458 self.group = group

3459 self.position = position

3460 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

3461

3462 self._key = self.__class__, self.group, self.case_flags

3463

3464 def fix_groups(self, pattern, reverse, fuzzy):

3465 try:

3466 self.group = int(self.group)

3467 except ValueError:

3468 try:

3469 self.group = self.info.group_index[self.group]

3470 except KeyError:

3471 raise error("unknown group", pattern, self.position)

3472

3473 if not 1 <= self.group <= self.info.group_count:

3474 raise error("invalid group reference", pattern, self.position)

3475

3476 self._key = self.__class__, self.group, self.case_flags

3477

3478 def remove_captures(self):

3479 raise error("group reference not allowed", self.pattern, self.position)

3480

3481 def _compile(self, reverse, fuzzy):

3482 flags = 0

3483 if fuzzy:

3484 flags |= FUZZY_OP

3485 return [(self._opcode[self.case_flags, reverse], flags, self.group)]

3486

3487 def dump(self, indent, reverse):

3488 print("{}REF_GROUP {}{}".format(INDENT * indent, self.group,

3489 CASE_TEXT[self.case_flags]))

3490

3491 def max_width(self):

3492 return UNLIMITED

3493

3494 def __del__(self):

3495 self.info = None

3496

3497class SearchAnchor(ZeroWidthBase):

3498 _opcode = OP.SEARCH_ANCHOR

3499 _op_name = "SEARCH_ANCHOR"

3500

3501class Sequence(RegexBase):

3502 def __init__(self, items=None):

3503 RegexBase.__init__(self)

3504 if items is None:

3505 items = []

3506

3507 self.items = items

3508

3509 def fix_groups(self, pattern, reverse, fuzzy):

3510 for s in self.items:

3511 s.fix_groups(pattern, reverse, fuzzy)

3512

3513 def optimise(self, info, reverse):

3514 # Flatten the sequences.

3515 items = []

3516 for s in self.items:

3517 s = s.optimise(info, reverse)

3518 if isinstance(s, Sequence):

3519 items.extend(s.items)

3520 else:

3521 items.append(s)

3522

3523 return make_sequence(items)

3524

3525 def pack_characters(self, info):

3526 "Packs sequences of characters into strings."

3527 items = []

3528 characters = []

3529 case_flags = NOCASE

3530 for s in self.items:

3531 if type(s) is Character and s.positive and not s.zerowidth:

3532 if s.case_flags != case_flags:

3533 # Different case sensitivity, so flush, unless neither the

3534 # previous nor the new character are cased.

3535 if s.case_flags or is_cased_i(info, s.value):

3536 Sequence._flush_characters(info, characters,

3537 case_flags, items)

3538

3539 case_flags = s.case_flags

3540

3541 characters.append(s.value)

3542 elif type(s) is String or type(s) is Literal:

3543 if s.case_flags != case_flags:

3544 # Different case sensitivity, so flush, unless the neither

3545 # the previous nor the new string are cased.

3546 if s.case_flags or any(is_cased_i(info, c) for c in

3547 characters):

3548 Sequence._flush_characters(info, characters,

3549 case_flags, items)

3550

3551 case_flags = s.case_flags

3552

3553 characters.extend(s.characters)

3554 else:

3555 Sequence._flush_characters(info, characters, case_flags, items)

3556

3557 items.append(s.pack_characters(info))

3558

3559 Sequence._flush_characters(info, characters, case_flags, items)

3560

3561 return make_sequence(items)

3562

3563 def remove_captures(self):

3564 self.items = [s.remove_captures() for s in self.items]

3565 return self

3566

3567 def is_atomic(self):

3568 return all(s.is_atomic() for s in self.items)

3569

3570 def can_be_affix(self):

3571 return False

3572

3573 def contains_group(self):

3574 return any(s.contains_group() for s in self.items)

3575

3576 def get_firstset(self, reverse):

3577 fs = set()

3578 items = self.items

3579 if reverse:

3580 items.reverse()

3581 for s in items:

3582 fs |= s.get_firstset(reverse)

3583 if None not in fs:

3584 return fs

3585 fs.discard(None)

3586

3587 return fs | set([None])

3588

3589 def has_simple_start(self):

3590 return bool(self.items) and self.items[0].has_simple_start()

3591

3592 def _compile(self, reverse, fuzzy):

3593 seq = self.items

3594 if reverse:

3595 seq = seq[::-1]

3596

3597 code = []

3598 for s in seq:

3599 code.extend(s.compile(reverse, fuzzy))

3600

3601 return code

3602

3603 def dump(self, indent, reverse):

3604 for s in self.items:

3605 s.dump(indent, reverse)

3606

3607 @staticmethod

3608 def _flush_characters(info, characters, case_flags, items):

3609 if not characters:

3610 return

3611

3612 # Disregard case_flags if all of the characters are case-less.

3613 if case_flags & IGNORECASE:

3614 if not any(is_cased_i(info, c) for c in characters):

3615 case_flags = NOCASE

3616

3617 if (case_flags & FULLIGNORECASE) == FULLIGNORECASE:

3618 literals = Sequence._fix_full_casefold(characters)

3619

3620 for item in literals:

3621 chars = item.characters

3622

3623 if len(chars) == 1:

3624 items.append(Character(chars[0], case_flags=item.case_flags))

3625 else:

3626 items.append(String(chars, case_flags=item.case_flags))

3627 else:

3628 if len(characters) == 1:

3629 items.append(Character(characters[0], case_flags=case_flags))

3630 else:

3631 items.append(String(characters, case_flags=case_flags))

3632

3633 characters[:] = []

3634

3635 @staticmethod

3636 def _fix_full_casefold(characters):

3637 # Split a literal needing full case-folding into chunks that need it

3638 # and chunks that can use simple case-folding, which is faster.

3639 expanded = [_regex.fold_case(FULL_CASE_FOLDING, c) for c in

3640 _regex.get_expand_on_folding()]

3641 string = _regex.fold_case(FULL_CASE_FOLDING, ''.join(chr(c)

3642 for c in characters)).lower()

3643 chunks = []

3644

3645 for e in expanded:

3646 found = string.find(e)

3647

3648 while found >= 0:

3649 chunks.append((found, found + len(e)))

3650 found = string.find(e, found + 1)

3651

3652 pos = 0

3653 literals = []

3654

3655 for start, end in Sequence._merge_chunks(chunks):

3656 if pos < start:

3657 literals.append(Literal(characters[pos : start],

3658 case_flags=IGNORECASE))

3659

3660 literals.append(Literal(characters[start : end],

3661 case_flags=FULLIGNORECASE))

3662 pos = end

3663

3664 if pos < len(characters):

3665 literals.append(Literal(characters[pos : ], case_flags=IGNORECASE))

3666

3667 return literals

3668

3669 @staticmethod

3670 def _merge_chunks(chunks):

3671 if len(chunks) < 2:

3672 return chunks

3673

3674 chunks.sort()

3675

3676 start, end = chunks[0]

3677 new_chunks = []

3678

3679 for s, e in chunks[1 : ]:

3680 if s <= end:

3681 end = max(end, e)

3682 else:

3683 new_chunks.append((start, end))

3684 start, end = s, e

3685

3686 new_chunks.append((start, end))

3687

3688 return new_chunks

3689

3690 def is_empty(self):

3691 return all(i.is_empty() for i in self.items)

3692

3693 def __eq__(self, other):

3694 return type(self) is type(other) and self.items == other.items

3695

3696 def max_width(self):

3697 return sum(s.max_width() for s in self.items)

3698

3699 def get_required_string(self, reverse):

3700 seq = self.items

3701 if reverse:

3702 seq = seq[::-1]

3703

3704 offset = 0

3705

3706 for s in seq:

3707 ofs, req = s.get_required_string(reverse)

3708 offset += ofs

3709 if req:

3710 return offset, req

3711

3712 return offset, None

3713

3714class SetBase(RegexBase):

3715 def __init__(self, info, items, positive=True, case_flags=NOCASE,

3716 zerowidth=False):

3717 RegexBase.__init__(self)

3718 self.info = info

3719 self.items = tuple(items)

3720 self.positive = bool(positive)

3721 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

3722 self.zerowidth = bool(zerowidth)

3723

3724 self.char_width = 1

3725

3726 self._key = (self.__class__, self.items, self.positive,

3727 self.case_flags, self.zerowidth)

3728

3729 def rebuild(self, positive, case_flags, zerowidth):

3730 return type(self)(self.info, self.items, positive, case_flags,

3731 zerowidth).optimise(self.info, False)

3732

3733 def get_firstset(self, reverse):

3734 return set([self])

3735

3736 def has_simple_start(self):

3737 return True

3738

3739 def _compile(self, reverse, fuzzy):

3740 flags = 0

3741 if self.positive:

3742 flags |= POSITIVE_OP

3743 if self.zerowidth:

3744 flags |= ZEROWIDTH_OP

3745 if fuzzy:

3746 flags |= FUZZY_OP

3747 code = [(self._opcode[self.case_flags, reverse], flags)]

3748 for m in self.items:

3749 code.extend(m.compile())

3750

3751 code.append((OP.END, ))

3752

3753 return code

3754

3755 def dump(self, indent, reverse):

3756 print("{}{} {}{}".format(INDENT * indent, self._op_name,

3757 POS_TEXT[self.positive], CASE_TEXT[self.case_flags]))

3758 for i in self.items:

3759 i.dump(indent + 1, reverse)

3760

3761 def _handle_case_folding(self, info, in_set):

3762 # Is the set case-sensitive?

3763 if not self.positive or not (self.case_flags & IGNORECASE) or in_set:

3764 return self

3765

3766 # Is full case-folding possible?

3767 if (not (self.info.flags & UNICODE) or (self.case_flags &

3768 FULLIGNORECASE) != FULLIGNORECASE):

3769 return self

3770

3771 # Get the characters which expand to multiple codepoints on folding.

3772 expanding_chars = _regex.get_expand_on_folding()

3773

3774 # Get the folded characters in the set.

3775 items = []

3776 seen = set()

3777 for ch in expanding_chars:

3778 if self.matches(ord(ch)):

3779 folded = _regex.fold_case(FULL_CASE_FOLDING, ch)

3780 if folded not in seen:

3781 items.append(String([ord(c) for c in folded],

3782 case_flags=self.case_flags))

3783 seen.add(folded)

3784

3785 if not items:

3786 # We can fall back to simple case-folding.

3787 return self

3788

3789 return Branch([self] + items)

3790

3791 def max_width(self):

3792 # Is the set case-sensitive?

3793 if not self.positive or not (self.case_flags & IGNORECASE):

3794 return 1

3795

3796 # Is full case-folding possible?

3797 if (not (self.info.flags & UNICODE) or (self.case_flags &

3798 FULLIGNORECASE) != FULLIGNORECASE):

3799 return 1

3800

3801 # Get the characters which expand to multiple codepoints on folding.

3802 expanding_chars = _regex.get_expand_on_folding()

3803

3804 # Get the folded characters in the set.

3805 seen = set()

3806 for ch in expanding_chars:

3807 if self.matches(ord(ch)):

3808 folded = _regex.fold_case(FULL_CASE_FOLDING, ch)

3809 seen.add(folded)

3810

3811 if not seen:

3812 return 1

3813

3814 return max(len(folded) for folded in seen)

3815

3816 def __del__(self):

3817 self.info = None

3818

3819class SetDiff(SetBase):

3820 _opcode = {(NOCASE, False): OP.SET_DIFF, (IGNORECASE, False):

3821 OP.SET_DIFF_IGN, (FULLCASE, False): OP.SET_DIFF, (FULLIGNORECASE, False):

3822 OP.SET_DIFF_IGN, (NOCASE, True): OP.SET_DIFF_REV, (IGNORECASE, True):

3823 OP.SET_DIFF_IGN_REV, (FULLCASE, True): OP.SET_DIFF_REV, (FULLIGNORECASE,

3824 True): OP.SET_DIFF_IGN_REV}

3825 _op_name = "SET_DIFF"

3826

3827 def optimise(self, info, reverse, in_set=False):

3828 items = self.items

3829 if len(items) > 2:

3830 items = [items[0], SetUnion(info, items[1 : ])]

3831

3832 if len(items) == 1:

3833 return items[0].with_flags(case_flags=self.case_flags,

3834 zerowidth=self.zerowidth).optimise(info, reverse, in_set)

3835

3836 self.items = tuple(m.optimise(info, reverse, in_set=True) for m in

3837 items)

3838

3839 return self._handle_case_folding(info, in_set)

3840

3841 def matches(self, ch):

3842 m = self.items[0].matches(ch) and not self.items[1].matches(ch)

3843 return m == self.positive

3844

3845class SetInter(SetBase):

3846 _opcode = {(NOCASE, False): OP.SET_INTER, (IGNORECASE, False):

3847 OP.SET_INTER_IGN, (FULLCASE, False): OP.SET_INTER, (FULLIGNORECASE,

3848 False): OP.SET_INTER_IGN, (NOCASE, True): OP.SET_INTER_REV, (IGNORECASE,

3849 True): OP.SET_INTER_IGN_REV, (FULLCASE, True): OP.SET_INTER_REV,

3850 (FULLIGNORECASE, True): OP.SET_INTER_IGN_REV}

3851 _op_name = "SET_INTER"

3852

3853 def optimise(self, info, reverse, in_set=False):

3854 items = []

3855 for m in self.items:

3856 m = m.optimise(info, reverse, in_set=True)

3857 if isinstance(m, SetInter) and m.positive:

3858 # Intersection in intersection.

3859 items.extend(m.items)

3860 else:

3861 items.append(m)

3862

3863 if len(items) == 1:

3864 return items[0].with_flags(case_flags=self.case_flags,

3865 zerowidth=self.zerowidth).optimise(info, reverse, in_set)

3866

3867 self.items = tuple(items)

3868

3869 return self._handle_case_folding(info, in_set)

3870

3871 def matches(self, ch):

3872 m = all(i.matches(ch) for i in self.items)

3873 return m == self.positive

3874

3875class SetSymDiff(SetBase):

3876 _opcode = {(NOCASE, False): OP.SET_SYM_DIFF, (IGNORECASE, False):

3877 OP.SET_SYM_DIFF_IGN, (FULLCASE, False): OP.SET_SYM_DIFF, (FULLIGNORECASE,

3878 False): OP.SET_SYM_DIFF_IGN, (NOCASE, True): OP.SET_SYM_DIFF_REV,

3879 (IGNORECASE, True): OP.SET_SYM_DIFF_IGN_REV, (FULLCASE, True):

3880 OP.SET_SYM_DIFF_REV, (FULLIGNORECASE, True): OP.SET_SYM_DIFF_IGN_REV}

3881 _op_name = "SET_SYM_DIFF"

3882

3883 def optimise(self, info, reverse, in_set=False):

3884 items = []

3885 for m in self.items:

3886 m = m.optimise(info, reverse, in_set=True)

3887 if isinstance(m, SetSymDiff) and m.positive:

3888 # Symmetric difference in symmetric difference.

3889 items.extend(m.items)

3890 else:

3891 items.append(m)

3892

3893 if len(items) == 1:

3894 return items[0].with_flags(case_flags=self.case_flags,

3895 zerowidth=self.zerowidth).optimise(info, reverse, in_set)

3896

3897 self.items = tuple(items)

3898

3899 return self._handle_case_folding(info, in_set)

3900

3901 def matches(self, ch):

3902 m = False

3903 for i in self.items:

3904 m = m != i.matches(ch)

3905

3906 return m == self.positive

3907

3908class SetUnion(SetBase):

3909 _opcode = {(NOCASE, False): OP.SET_UNION, (IGNORECASE, False):

3910 OP.SET_UNION_IGN, (FULLCASE, False): OP.SET_UNION, (FULLIGNORECASE,

3911 False): OP.SET_UNION_IGN, (NOCASE, True): OP.SET_UNION_REV, (IGNORECASE,

3912 True): OP.SET_UNION_IGN_REV, (FULLCASE, True): OP.SET_UNION_REV,

3913 (FULLIGNORECASE, True): OP.SET_UNION_IGN_REV}

3914 _op_name = "SET_UNION"

3915

3916 def optimise(self, info, reverse, in_set=False):

3917 items = []

3918 for m in self.items:

3919 m = m.optimise(info, reverse, in_set=True)

3920 if isinstance(m, SetUnion) and m.positive:

3921 # Union in union.

3922 items.extend(m.items)

3923 elif isinstance(m, AnyAll):

3924 return AnyAll()

3925 else:

3926 items.append(m)

3927

3928 # Are there complementary properties?

3929 properties = (set(), set())

3930

3931 for m in items:

3932 if isinstance(m, Property):

3933 properties[m.positive].add((m.value, m.case_flags, m.zerowidth))

3934

3935 if properties[0] & properties[1]:

3936 return AnyAll()

3937

3938 if len(items) == 1:

3939 i = items[0]

3940 return i.with_flags(positive=i.positive == self.positive,

3941 case_flags=self.case_flags,

3942 zerowidth=self.zerowidth).optimise(info, reverse, in_set)

3943

3944 self.items = tuple(items)

3945

3946 return self._handle_case_folding(info, in_set)

3947

3948 def _compile(self, reverse, fuzzy):

3949 flags = 0

3950 if self.positive:

3951 flags |= POSITIVE_OP

3952 if self.zerowidth:

3953 flags |= ZEROWIDTH_OP

3954 if fuzzy:

3955 flags |= FUZZY_OP

3956

3957 characters, others = defaultdict(list), []

3958 for m in self.items:

3959 if isinstance(m, Character):

3960 characters[m.positive].append(m.value)

3961 else:

3962 others.append(m)

3963

3964 code = [(self._opcode[self.case_flags, reverse], flags)]

3965

3966 for positive, values in characters.items():

3967 flags = 0

3968 if positive:

3969 flags |= POSITIVE_OP

3970 if len(values) == 1:

3971 code.append((OP.CHARACTER, flags, values[0]))

3972 else:

3973 code.append((OP.STRING, flags, len(values)) + tuple(values))

3974

3975 for m in others:

3976 code.extend(m.compile())

3977

3978 code.append((OP.END, ))

3979

3980 return code

3981

3982 def matches(self, ch):

3983 m = any(i.matches(ch) for i in self.items)

3984 return m == self.positive

3985

3986class Skip(ZeroWidthBase):

3987 _op_name = "SKIP"

3988 _opcode = OP.SKIP

3989

3990class StartOfLine(ZeroWidthBase):

3991 _opcode = OP.START_OF_LINE

3992 _op_name = "START_OF_LINE"

3993

3994class StartOfLineU(StartOfLine):

3995 _opcode = OP.START_OF_LINE_U

3996 _op_name = "START_OF_LINE_U"

3997

3998class StartOfString(ZeroWidthBase):

3999 _opcode = OP.START_OF_STRING

4000 _op_name = "START_OF_STRING"

4001

4002class StartOfWord(ZeroWidthBase):

4003 _opcode = OP.START_OF_WORD

4004 _op_name = "START_OF_WORD"

4005

4006class String(RegexBase):

4007 _opcode = {(NOCASE, False): OP.STRING, (IGNORECASE, False): OP.STRING_IGN,

4008 (FULLCASE, False): OP.STRING, (FULLIGNORECASE, False): OP.STRING_FLD,

4009 (NOCASE, True): OP.STRING_REV, (IGNORECASE, True): OP.STRING_IGN_REV,

4010 (FULLCASE, True): OP.STRING_REV, (FULLIGNORECASE, True):

4011 OP.STRING_FLD_REV}

4012

4013 def __init__(self, characters, case_flags=NOCASE):

4014 self.characters = tuple(characters)

4015 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

4016

4017 if (self.case_flags & FULLIGNORECASE) == FULLIGNORECASE:

4018 folded_characters = []

4019 for char in self.characters:

4020 folded = _regex.fold_case(FULL_CASE_FOLDING, chr(char))

4021 folded_characters.extend(ord(c) for c in folded)

4022 else:

4023 folded_characters = self.characters

4024

4025 self.folded_characters = tuple(folded_characters)

4026 self.required = False

4027

4028 self._key = self.__class__, self.characters, self.case_flags

4029

4030 def get_firstset(self, reverse):

4031 if reverse:

4032 pos = -1

4033 else:

4034 pos = 0

4035 return set([Character(self.characters[pos],

4036 case_flags=self.case_flags)])

4037

4038 def has_simple_start(self):

4039 return True

4040

4041 def _compile(self, reverse, fuzzy):

4042 flags = 0

4043 if fuzzy:

4044 flags |= FUZZY_OP

4045 if self.required:

4046 flags |= REQUIRED_OP

4047 return [(self._opcode[self.case_flags, reverse], flags,

4048 len(self.folded_characters)) + self.folded_characters]

4049

4050 def dump(self, indent, reverse):

4051 display = ascii("".join(chr(c) for c in self.characters)).lstrip("bu")

4052 print("{}STRING {}{}".format(INDENT * indent, display,

4053 CASE_TEXT[self.case_flags]))

4054

4055 def max_width(self):

4056 return len(self.folded_characters)

4057

4058 def get_required_string(self, reverse):

4059 return 0, self

4060

4061class Literal(String):

4062 def dump(self, indent, reverse):

4063 literal = ''.join(chr(c) for c in self.characters)

4064 display = ascii(literal).lstrip("bu")

4065 print("{}LITERAL MATCH {}{}".format(INDENT * indent, display,

4066 CASE_TEXT[self.case_flags]))

4067

4068class StringSet(Branch):

4069 def __init__(self, info, name, case_flags=NOCASE):

4070 self.info = info

4071 self.name = name

4072 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

4073

4074 self._key = self.__class__, self.name, self.case_flags

4075

4076 self.set_key = (name, self.case_flags)

4077 if self.set_key not in info.named_lists_used:

4078 info.named_lists_used[self.set_key] = len(info.named_lists_used)

4079

4080 index = self.info.named_lists_used[self.set_key]

4081 items = self.info.kwargs[self.name]

4082

4083 case_flags = self.case_flags

4084

4085 encoding = self.info.flags & _ALL_ENCODINGS

4086 fold_flags = encoding | case_flags

4087

4088 choices = []

4089

4090 for string in items:

4091 if isinstance(string, str):

4092 string = [ord(c) for c in string]

4093

4094 choices.append([Character(c, case_flags=case_flags) for c in

4095 string])

4096

4097 # Sort from longest to shortest.

4098 choices.sort(key=len, reverse=True)

4099

4100 self.branches = [Sequence(choice) for choice in choices]

4101

4102 def dump(self, indent, reverse):

4103 print("{}STRING_SET {}{}".format(INDENT * indent, self.name,

4104 CASE_TEXT[self.case_flags]))

4105

4106 def __del__(self):

4107 self.info = None

4108

4109class Source:

4110 "Scanner for the regular expression source string."

4111 def __init__(self, string):

4112 if isinstance(string, str):

4113 self.string = string

4114 self.char_type = chr

4115 else:

4116 self.string = string.decode("latin-1")

4117 self.char_type = lambda c: bytes([c])

4118

4119 self.pos = 0

4120 self.ignore_space = False

4121 self.sep = string[ : 0]

4122

4123 def peek(self, override_ignore=False):

4124 string = self.string

4125 pos = self.pos

4126

4127 try:

4128 if self.ignore_space and not override_ignore:

4129 while True:

4130 if string[pos].isspace():

4131 # Skip over the whitespace.

4132 pos += 1

4133 elif string[pos] == "#":

4134 # Skip over the comment to the end of the line.

4135 pos = string.index("\n", pos)

4136 else:

4137 break

4138

4139 return string[pos]

4140 except IndexError:

4141 # We've reached the end of the string.

4142 return string[ : 0]

4143 except ValueError:

4144 # The comment extended to the end of the string.

4145 return string[ : 0]

4146

4147 def get(self, override_ignore=False):

4148 string = self.string

4149 pos = self.pos

4150

4151 try:

4152 if self.ignore_space and not override_ignore:

4153 while True:

4154 if string[pos].isspace():

4155 # Skip over the whitespace.

4156 pos += 1

4157 elif string[pos] == "#":

4158 # Skip over the comment to the end of the line.

4159 pos = string.index("\n", pos)

4160 else:

4161 break

4162

4163 ch = string[pos]

4164 self.pos = pos + 1

4165 return ch

4166 except IndexError:

4167 # We've reached the end of the string.

4168 self.pos = pos

4169 return string[ : 0]

4170 except ValueError:

4171 # The comment extended to the end of the string.

4172 self.pos = len(string)

4173 return string[ : 0]

4174

4175 def get_many(self, count=1):

4176 string = self.string

4177 pos = self.pos

4178

4179 try:

4180 if self.ignore_space:

4181 substring = []

4182

4183 while len(substring) < count:

4184 while True:

4185 if string[pos].isspace():

4186 # Skip over the whitespace.

4187 pos += 1

4188 elif string[pos] == "#":

4189 # Skip over the comment to the end of the line.

4190 pos = string.index("\n", pos)

4191 else:

4192 break

4193

4194 substring.append(string[pos])

4195 pos += 1

4196

4197 substring = "".join(substring)

4198 else:

4199 substring = string[pos : pos + count]

4200 pos += len(substring)

4201

4202 self.pos = pos

4203 return substring

4204 except IndexError:

4205 # We've reached the end of the string.

4206 self.pos = len(string)

4207 return "".join(substring)

4208 except ValueError:

4209 # The comment extended to the end of the string.

4210 self.pos = len(string)

4211 return "".join(substring)

4212

4213 def get_while(self, test_set, include=True, keep_spaces=False):

4214 string = self.string

4215 pos = self.pos

4216

4217 if self.ignore_space and not keep_spaces:

4218 try:

4219 substring = []

4220

4221 while True:

4222 if string[pos].isspace():

4223 # Skip over the whitespace.

4224 pos += 1

4225 elif string[pos] == "#":

4226 # Skip over the comment to the end of the line.

4227 pos = string.index("\n", pos)

4228 elif (string[pos] in test_set) == include:

4229 substring.append(string[pos])

4230 pos += 1

4231 else:

4232 break

4233

4234 self.pos = pos

4235 except IndexError:

4236 # We've reached the end of the string.

4237 self.pos = len(string)

4238 except ValueError:

4239 # The comment extended to the end of the string.

4240 self.pos = len(string)

4241

4242 return "".join(substring)

4243 else:

4244 try:

4245 while (string[pos] in test_set) == include:

4246 pos += 1

4247

4248 substring = string[self.pos : pos]

4249

4250 self.pos = pos

4251

4252 return substring

4253 except IndexError:

4254 # We've reached the end of the string.

4255 substring = string[self.pos : pos]

4256

4257 self.pos = pos

4258

4259 return substring

4260

4261 def skip_while(self, test_set, include=True):

4262 string = self.string

4263 pos = self.pos

4264

4265 try:

4266 if self.ignore_space:

4267 while True:

4268 if string[pos].isspace():

4269 # Skip over the whitespace.

4270 pos += 1

4271 elif string[pos] == "#":

4272 # Skip over the comment to the end of the line.

4273 pos = string.index("\n", pos)

4274 elif (string[pos] in test_set) == include:

4275 pos += 1

4276 else:

4277 break

4278 else:

4279 while (string[pos] in test_set) == include:

4280 pos += 1

4281

4282 self.pos = pos

4283 except IndexError:

4284 # We've reached the end of the string.

4285 self.pos = len(string)

4286 except ValueError:

4287 # The comment extended to the end of the string.

4288 self.pos = len(string)

4289

4290 def match(self, substring):

4291 string = self.string

4292 pos = self.pos

4293

4294 if self.ignore_space:

4295 try:

4296 for c in substring:

4297 while True:

4298 if string[pos].isspace():

4299 # Skip over the whitespace.

4300 pos += 1

4301 elif string[pos] == "#":

4302 # Skip over the comment to the end of the line.

4303 pos = string.index("\n", pos)

4304 else:

4305 break

4306

4307 if string[pos] != c:

4308 return False

4309

4310 pos += 1

4311

4312 self.pos = pos

4313

4314 return True

4315 except IndexError:

4316 # We've reached the end of the string.

4317 return False

4318 except ValueError:

4319 # The comment extended to the end of the string.

4320 return False

4321 else:

4322 if not string.startswith(substring, pos):

4323 return False

4324

4325 self.pos = pos + len(substring)

4326

4327 return True

4328

4329 def expect(self, substring):

4330 if not self.match(substring):

4331 raise error("missing {}".format(substring), self.string, self.pos)

4332

4333 def at_end(self):

4334 string = self.string

4335 pos = self.pos

4336

4337 try:

4338 if self.ignore_space:

4339 while True:

4340 if string[pos].isspace():

4341 pos += 1

4342 elif string[pos] == "#":

4343 pos = string.index("\n", pos)

4344 else:

4345 break

4346

4347 return pos >= len(string)

4348 except IndexError:

4349 # We've reached the end of the string.

4350 return True

4351 except ValueError:

4352 # The comment extended to the end of the string.

4353 return True

4354

4355class Info:

4356 "Info about the regular expression."

4357

4358 def __init__(self, flags=0, char_type=None, kwargs={}):

4359 flags |= DEFAULT_FLAGS[(flags & _ALL_VERSIONS) or DEFAULT_VERSION]

4360 self.flags = flags

4361 self.global_flags = flags

4362 self.inline_locale = False

4363

4364 self.kwargs = kwargs

4365

4366 self.group_count = 0

4367 self.group_index = {}

4368 self.group_name = {}

4369 self.char_type = char_type

4370 self.named_lists_used = {}

4371 self.open_groups = []

4372 self.open_group_count = {}

4373 self.defined_groups = {}

4374 self.group_calls = []

4375 self.private_groups = {}

4376

4377 def open_group(self, name=None):

4378 group = self.group_index.get(name)

4379 if group is None:

4380 while True:

4381 self.group_count += 1

4382 if name is None or self.group_count not in self.group_name:

4383 break

4384

4385 group = self.group_count

4386 if name:

4387 self.group_index[name] = group

4388 self.group_name[group] = name

4389

4390 if group in self.open_groups:

4391 # We have a nested named group. We'll assign it a private group

4392 # number, initially negative until we can assign a proper

4393 # (positive) number.

4394 group_alias = -(len(self.private_groups) + 1)

4395 self.private_groups[group_alias] = group

4396 group = group_alias

4397

4398 self.open_groups.append(group)

4399 self.open_group_count[group] = self.open_group_count.get(group, 0) + 1

4400

4401 return group

4402

4403 def close_group(self):

4404 self.open_groups.pop()

4405

4406 def is_open_group(self, name):

4407 # In version 1, a group reference can refer to an open group. We'll

4408 # just pretend the group isn't open.

4409 version = (self.flags & _ALL_VERSIONS) or DEFAULT_VERSION

4410 if version == VERSION1:

4411 return False

4412

4413 if name.isdigit():

4414 group = int(name)

4415 else:

4416 group = self.group_index.get(name)

4417

4418 return group in self.open_groups

4419

4420def _check_group_features(info, parsed):

4421 """Checks whether the reverse and fuzzy features of the group calls match

4422 the groups which they call.

4423 """

4424 call_refs = {}

4425 additional_groups = []

4426 for call, reverse, fuzzy in info.group_calls:

4427 # Look up the reference of this group call.

4428 key = (call.group, reverse, fuzzy)

4429 ref = call_refs.get(key)

4430 if ref is None:

4431 # This group doesn't have a reference yet, so look up its features.

4432 if call.group == 0:

4433 # Calling the pattern as a whole.

4434 rev = bool(info.flags & REVERSE)

4435 fuz = isinstance(parsed, Fuzzy)

4436 if (rev, fuz) != (reverse, fuzzy):

4437 # The pattern as a whole doesn't have the features we want,

4438 # so we'll need to make a copy of it with the desired

4439 # features.

4440 additional_groups.append((CallRef(len(call_refs), parsed),

4441 reverse, fuzzy))

4442 else:

4443 # Calling a capture group.

4444 def_info = info.defined_groups[call.group]

4445 group = def_info[0]

4446 if def_info[1 : ] != (reverse, fuzzy):

4447 # The group doesn't have the features we want, so we'll

4448 # need to make a copy of it with the desired features.

4449 additional_groups.append((group, reverse, fuzzy))

4450

4451 ref = len(call_refs)

4452 call_refs[key] = ref

4453

4454 call.call_ref = ref

4455

4456 info.call_refs = call_refs

4457 info.additional_groups = additional_groups

4458

4459def _get_required_string(parsed, flags):

4460 "Gets the required string and related info of a parsed pattern."

4461

4462 req_offset, required = parsed.get_required_string(bool(flags & REVERSE))

4463 if required:

4464 required.required = True

4465 if req_offset >= UNLIMITED:

4466 req_offset = -1

4467

4468 req_flags = required.case_flags

4469 if not (flags & UNICODE):

4470 req_flags &= ~UNICODE

4471

4472 req_chars = required.folded_characters

4473 else:

4474 req_offset = 0

4475 req_chars = ()

4476 req_flags = 0

4477

4478 return req_offset, req_chars, req_flags

4479

4480class Scanner:

4481 def __init__(self, lexicon, flags=0):

4482 self.lexicon = lexicon

4483

4484 # Combine phrases into a compound pattern.

4485 patterns = []

4486 for phrase, action in lexicon:

4487 # Parse the regular expression.

4488 source = Source(phrase)

4489 info = Info(flags, source.char_type)

4490 source.ignore_space = bool(info.flags & VERBOSE)

4491 parsed = _parse_pattern(source, info)

4492 if not source.at_end():

4493 raise error("unbalanced parenthesis", source.string,

4494 source.pos)

4495

4496 # We want to forbid capture groups within each phrase.

4497 patterns.append(parsed.remove_captures())

4498

4499 # Combine all the subpatterns into one pattern.

4500 info = Info(flags)

4501 patterns = [Group(info, g + 1, p) for g, p in enumerate(patterns)]

4502 parsed = Branch(patterns)

4503

4504 # Optimise the compound pattern.

4505 reverse = bool(info.flags & REVERSE)

4506 parsed = parsed.optimise(info, reverse)

4507 parsed = parsed.pack_characters(info)

4508

4509 # Get the required string.

4510 req_offset, req_chars, req_flags = _get_required_string(parsed,

4511 info.flags)

4512

4513 # Check the features of the groups.

4514 _check_group_features(info, parsed)

4515

4516 # Complain if there are any group calls. They are not supported by the

4517 # Scanner class.

4518 if info.call_refs:

4519 raise error("recursive regex not supported by Scanner",

4520 source.string, source.pos)

4521

4522 reverse = bool(info.flags & REVERSE)

4523

4524 # Compile the compound pattern. The result is a list of tuples.

4525 code = parsed.compile(reverse) + [(OP.SUCCESS, )]

4526

4527 # Flatten the code into a list of ints.

4528 code = _flatten_code(code)

4529

4530 if not parsed.has_simple_start():

4531 # Get the first set, if possible.

4532 try:

4533 fs_code = _compile_firstset(info, parsed.get_firstset(reverse))

4534 fs_code = _flatten_code(fs_code)

4535 code = fs_code + code

4536 except _FirstSetError:

4537 pass

4538

4539 # Check the global flags for conflicts.

4540 version = (info.flags & _ALL_VERSIONS) or DEFAULT_VERSION

4541 if version not in (0, VERSION0, VERSION1):

4542 raise ValueError("VERSION0 and VERSION1 flags are mutually incompatible")

4543

4544 # Create the PatternObject.

4545 #

4546 # Local flags like IGNORECASE affect the code generation, but aren't

4547 # needed by the PatternObject itself. Conversely, global flags like

4548 # LOCALE _don't_ affect the code generation but _are_ needed by the

4549 # PatternObject.

4550 self.scanner = _regex.compile(None, (flags & GLOBAL_FLAGS) | version,

4551 code, {}, {}, {}, [], req_offset, req_chars, req_flags,

4552 len(patterns))

4553

4554 def scan(self, string):

4555 result = []

4556 append = result.append

4557 match = self.scanner.scanner(string).match

4558 i = 0

4559 while True:

4560 m = match()

4561 if not m:

4562 break

4563 j = m.end()

4564 if i == j:

4565 break

4566 action = self.lexicon[m.lastindex - 1][1]

4567 if hasattr(action, '__call__'):

4568 self.match = m

4569 action = action(self, m.group())

4570 if action is not None:

4571 append(action)

4572 i = j

4573

4574 return result, string[i : ]

4575

4576# Get the known properties dict.

4577PROPERTIES = _regex.get_properties()

4578

4579# Build the inverse of the properties dict.

4580PROPERTY_NAMES = {}

4581for prop_name, (prop_id, values) in PROPERTIES.items():

4582 name, prop_values = PROPERTY_NAMES.get(prop_id, ("", {}))

4583 name = max(name, prop_name, key=len)

4584 PROPERTY_NAMES[prop_id] = name, prop_values

4585

4586 for val_name, val_id in values.items():

4587 prop_values[val_id] = max(prop_values.get(val_id, ""), val_name,

4588 key=len)

4589

4590# Character escape sequences.

4591CHARACTER_ESCAPES = {

4592 "a": "\a",

4593 "b": "\b",

4594 "f": "\f",

4595 "n": "\n",

4596 "r": "\r",

4597 "t": "\t",

4598 "v": "\v",

4599}

4600

4601ASCII_ENCODING = 1

4602UNICODE_ENCODING = 2

4603

4604# Predefined character set escape sequences.

4605CHARSET_ESCAPES = {

4606 "d": lookup_property(None, "Digit", True),

4607 "D": lookup_property(None, "Digit", False),

4608 "h": lookup_property(None, "Blank", True),

4609 "s": lookup_property(None, "Space", True),

4610 "S": lookup_property(None, "Space", False),

4611 "w": lookup_property(None, "Word", True),

4612 "W": lookup_property(None, "Word", False),

4613}

4614

4615ASCII_CHARSET_ESCAPES = dict(CHARSET_ESCAPES)

4616ASCII_CHARSET_ESCAPES.update({

4617 "d": lookup_property(None, "Digit", True, encoding=ASCII_ENCODING),

4618 "D": lookup_property(None, "Digit", False, encoding=ASCII_ENCODING),

4619 "s": lookup_property(None, "Space", True, encoding=ASCII_ENCODING),

4620 "S": lookup_property(None, "Space", False, encoding=ASCII_ENCODING),

4621 "w": lookup_property(None, "Word", True, encoding=ASCII_ENCODING),

4622 "W": lookup_property(None, "Word", False, encoding=ASCII_ENCODING),

4623})

4624UNICODE_CHARSET_ESCAPES = dict(CHARSET_ESCAPES)

4625UNICODE_CHARSET_ESCAPES.update({

4626 "d": lookup_property(None, "Digit", True, encoding=UNICODE_ENCODING),

4627 "D": lookup_property(None, "Digit", False, encoding=UNICODE_ENCODING),

4628 "s": lookup_property(None, "Space", True, encoding=UNICODE_ENCODING),

4629 "S": lookup_property(None, "Space", False, encoding=UNICODE_ENCODING),

4630 "w": lookup_property(None, "Word", True, encoding=UNICODE_ENCODING),

4631 "W": lookup_property(None, "Word", False, encoding=UNICODE_ENCODING),

4632})

4633

4634# Positional escape sequences.

4635POSITION_ESCAPES = {

4636 "A": StartOfString(),

4637 "b": Boundary(),

4638 "B": Boundary(False),

4639 "K": Keep(),

4640 "m": StartOfWord(),

4641 "M": EndOfWord(),

4642 "Z": EndOfString(),

4643 "z": EndOfString(),

4644}

4645ASCII_POSITION_ESCAPES = dict(POSITION_ESCAPES)

4646ASCII_POSITION_ESCAPES.update({

4647 "b": Boundary(encoding=ASCII_ENCODING),

4648 "B": Boundary(False, encoding=ASCII_ENCODING),

4649 "m": StartOfWord(encoding=ASCII_ENCODING),

4650 "M": EndOfWord(encoding=ASCII_ENCODING),

4651})

4652UNICODE_POSITION_ESCAPES = dict(POSITION_ESCAPES)

4653UNICODE_POSITION_ESCAPES.update({

4654 "b": Boundary(encoding=UNICODE_ENCODING),

4655 "B": Boundary(False, encoding=UNICODE_ENCODING),

4656 "m": StartOfWord(encoding=UNICODE_ENCODING),

4657 "M": EndOfWord(encoding=UNICODE_ENCODING),

4658})

4659

4660# Positional escape sequences when WORD flag set.

4661WORD_POSITION_ESCAPES = dict(POSITION_ESCAPES)

4662WORD_POSITION_ESCAPES.update({

4663 "b": DefaultBoundary(),

4664 "B": DefaultBoundary(False),

4665 "m": DefaultStartOfWord(),

4666 "M": DefaultEndOfWord(),

4667})

4668

4669# Regex control verbs.

4670VERBS = {

4671 "FAIL": Failure(),

4672 "F": Failure(),

4673 "PRUNE": Prune(),

4674 "SKIP": Skip(),

4675}

Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/regex/_regex_core.py: 26%

2903 statements