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 not 0 <= max_cost <= 0xFFFFFFFF:

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 not 0 <= max_cost <= 0xFFFFFFFF:

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

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

2071 new = AnyAll()

2072 if positive is not None:

2073 new.positive = positive

2074 if zerowidth is not None:

2075 new.zerowidth = zerowidth

2076 return new

2077

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

2079 return self

2080

2081class AnyU(Any):

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

2083 _op_name = "ANY_U"

2084

2085class Atomic(RegexBase):

2086 def __init__(self, subpattern):

2087 RegexBase.__init__(self)

2088 self.subpattern = subpattern

2089

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

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

2092

2093 def optimise(self, info, reverse):

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

2095

2096 if self.subpattern.is_empty():

2097 return self.subpattern

2098 return self

2099

2100 def pack_characters(self, info):

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

2102 return self

2103

2104 def remove_captures(self):

2105 self.subpattern = self.subpattern.remove_captures()

2106 return self

2107

2108 def can_be_affix(self):

2109 return self.subpattern.can_be_affix()

2110

2111 def contains_group(self):

2112 return self.subpattern.contains_group()

2113

2114 def get_firstset(self, reverse):

2115 return self.subpattern.get_firstset(reverse)

2116

2117 def has_simple_start(self):

2118 return self.subpattern.has_simple_start()

2119

2120 def _compile(self, reverse, fuzzy):

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

2122 [(OP.END, )])

2123

2124 def dump(self, indent, reverse):

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

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

2127

2128 def is_empty(self):

2129 return self.subpattern.is_empty()

2130

2131 def __eq__(self, other):

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

2133 other.subpattern)

2134

2135 def max_width(self):

2136 return self.subpattern.max_width()

2137

2138 def get_required_string(self, reverse):

2139 return self.subpattern.get_required_string(reverse)

2140

2141class Boundary(ZeroWidthBase):

2142 _opcode = OP.BOUNDARY

2143 _op_name = "BOUNDARY"

2144

2145class Branch(RegexBase):

2146 def __init__(self, branches):

2147 RegexBase.__init__(self)

2148 self.branches = branches

2149

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

2151 for b in self.branches:

2152 b.fix_groups(pattern, reverse, fuzzy)

2153

2154 def optimise(self, info, reverse):

2155 if not self.branches:

2156 return Sequence([])

2157

2158 # Flatten branches within branches.

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

2160

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

2162 if reverse:

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

2164 prefix = []

2165 else:

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

2167 suffix = []

2168

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

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

2171

2172 if len(branches) > 1:

2173 sequence = [Branch(branches)]

2174

2175 if not prefix or not suffix:

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

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

2178

2179 if firstset:

2180 if reverse:

2181 sequence.append(firstset)

2182 else:

2183 sequence.insert(0, firstset)

2184 else:

2185 sequence = branches

2186

2187 return make_sequence(prefix + sequence + suffix)

2188

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

2190 charset = set()

2191 pos = -1 if reverse else 0

2192

2193 for branch in branches:

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

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

2196 else:

2197 return

2198

2199 if not charset:

2200 return None

2201

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

2203

2204 def pack_characters(self, info):

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

2206 return self

2207

2208 def remove_captures(self):

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

2210 return self

2211

2212 def is_atomic(self):

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

2214

2215 def can_be_affix(self):

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

2217

2218 def contains_group(self):

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

2220

2221 def get_firstset(self, reverse):

2222 fs = set()

2223 for b in self.branches:

2224 fs |= b.get_firstset(reverse)

2225

2226 return fs or set([None])

2227

2228 def _compile(self, reverse, fuzzy):

2229 if not self.branches:

2230 return []

2231

2232 code = [(OP.BRANCH, )]

2233 for b in self.branches:

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

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

2236

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

2238

2239 return code

2240

2241 def dump(self, indent, reverse):

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

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

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

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

2246 b.dump(indent + 1, reverse)

2247

2248 @staticmethod

2249 def _flatten_branches(info, reverse, branches):

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

2251 new_branches = []

2252 for b in branches:

2253 b = b.optimise(info, reverse)

2254 if isinstance(b, Branch):

2255 new_branches.extend(b.branches)

2256 else:

2257 new_branches.append(b)

2258

2259 return new_branches

2260

2261 @staticmethod

2262 def _split_common_prefix(info, branches):

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

2264 # Get the items in the branches.

2265 alternatives = []

2266 for b in branches:

2267 if isinstance(b, Sequence):

2268 alternatives.append(b.items)

2269 else:

2270 alternatives.append([b])

2271

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

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

2274

2275 # What is the longest common prefix?

2276 prefix = alternatives[0]

2277 pos = 0

2278 end_pos = max_count

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

2280 prefix[pos] for a in alternatives):

2281 pos += 1

2282 count = pos

2283

2284 if info.flags & UNICODE:

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

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

2287 count = pos

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

2289 alternatives):

2290 count -= 1

2291

2292 # No common prefix is possible.

2293 if count == 0:

2294 return [], branches

2295

2296 # Rebuild the branches.

2297 new_branches = []

2298 for a in alternatives:

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

2300

2301 return prefix[ : count], new_branches

2302

2303 @staticmethod

2304 def _split_common_suffix(info, branches):

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

2306 # Get the items in the branches.

2307 alternatives = []

2308 for b in branches:

2309 if isinstance(b, Sequence):

2310 alternatives.append(b.items)

2311 else:

2312 alternatives.append([b])

2313

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

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

2316

2317 # What is the longest common suffix?

2318 suffix = alternatives[0]

2319 pos = -1

2320 end_pos = -1 - max_count

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

2322 suffix[pos] for a in alternatives):

2323 pos -= 1

2324 count = -1 - pos

2325

2326 if info.flags & UNICODE:

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

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

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

2330 in alternatives):

2331 count -= 1

2332

2333 # No common suffix is possible.

2334 if count == 0:

2335 return [], branches

2336

2337 # Rebuild the branches.

2338 new_branches = []

2339 for a in alternatives:

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

2341

2342 return suffix[-count : ], new_branches

2343

2344 @staticmethod

2345 def _can_split(items, count):

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

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

2348 return True

2349

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

2351 return True

2352

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

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

2355 return False

2356

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

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

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

2360 return False

2361

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

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

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

2365 return False

2366

2367 return True

2368

2369 @staticmethod

2370 def _can_split_rev(items, count):

2371 end = len(items)

2372

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

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

2375 return True

2376

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

2378 return True

2379

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

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

2382 return False

2383

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

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

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

2387 return False

2388

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

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

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

2392 return False

2393

2394 return True

2395

2396 @staticmethod

2397 def _merge_common_prefixes(info, reverse, branches):

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

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

2400 # character prefix.

2401 prefixed = defaultdict(list)

2402 order = {}

2403 new_branches = []

2404 for b in branches:

2405 if Branch._is_simple_character(b):

2406 # Branch starts with a simple character.

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

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

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

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

2411 # Branch starts with a simple character.

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

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

2414 else:

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

2416 new_branches)

2417

2418 new_branches.append(b)

2419

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

2421

2422 return new_branches

2423

2424 @staticmethod

2425 def _is_simple_character(c):

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

2427

2428 @staticmethod

2429 def _reduce_to_set(info, reverse, branches):

2430 # Can the branches be reduced to a set?

2431 new_branches = []

2432 items = set()

2433 case_flags = NOCASE

2434 for b in branches:

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

2436 # Branch starts with a single character.

2437 if b.case_flags != case_flags:

2438 # Different case sensitivity, so flush.

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

2440 new_branches)

2441

2442 case_flags = b.case_flags

2443

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

2445 else:

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

2447 new_branches)

2448

2449 new_branches.append(b)

2450

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

2452 new_branches)

2453

2454 return new_branches

2455

2456 @staticmethod

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

2458 # Flush the prefixed branches.

2459 if not prefixed:

2460 return

2461

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

2463 order[pair[0]]):

2464 if len(branches) == 1:

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

2466 else:

2467 subbranches = []

2468 optional = False

2469 for b in branches:

2470 if len(b) > 1:

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

2472 elif not optional:

2473 subbranches.append(Sequence())

2474 optional = True

2475

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

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

2478

2479 prefixed.clear()

2480 order.clear()

2481

2482 @staticmethod

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

2484 # Flush the set members.

2485 if not items:

2486 return

2487

2488 if len(items) == 1:

2489 item = list(items)[0]

2490 else:

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

2492

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

2494

2495 items.clear()

2496

2497 @staticmethod

2498 def _is_full_case(items, i):

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

2500 return False

2501

2502 item = items[i]

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

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

2505

2506 @staticmethod

2507 def _is_folded(items):

2508 if len(items) < 2:

2509 return False

2510

2511 for i in items:

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

2513 i.case_flags):

2514 return False

2515

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

2517 folded = _regex.fold_case(FULL_CASE_FOLDING, folded)

2518

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

2520 expanding_chars = _regex.get_expand_on_folding()

2521

2522 for c in expanding_chars:

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

2524 return True

2525

2526 return False

2527

2528 def is_empty(self):

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

2530

2531 def __eq__(self, other):

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

2533

2534 def max_width(self):

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

2536

2537class CallGroup(RegexBase):

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

2539 RegexBase.__init__(self)

2540 self.info = info

2541 self.group = group

2542 self.position = position

2543

2544 self._key = self.__class__, self.group

2545

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

2547 try:

2548 self.group = int(self.group)

2549 except ValueError:

2550 try:

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

2552 except KeyError:

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

2554

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

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

2557

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

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

2560

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

2562

2563 self._key = self.__class__, self.group

2564

2565 def remove_captures(self):

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

2567

2568 def _compile(self, reverse, fuzzy):

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

2570

2571 def dump(self, indent, reverse):

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

2573

2574 def __eq__(self, other):

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

2576

2577 def max_width(self):

2578 return UNLIMITED

2579

2580 def __del__(self):

2581 self.info = None

2582

2583class CallRef(RegexBase):

2584 def __init__(self, ref, parsed):

2585 self.ref = ref

2586 self.parsed = parsed

2587

2588 def _compile(self, reverse, fuzzy):

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

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

2591

2592class Character(RegexBase):

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

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

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

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

2597 (FULLIGNORECASE, True): OP.CHARACTER_IGN_REV}

2598

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

2600 zerowidth=False):

2601 RegexBase.__init__(self)

2602 self.value = value

2603 self.positive = bool(positive)

2604 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

2605 self.zerowidth = bool(zerowidth)

2606

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

2608 FULLIGNORECASE):

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

2610 else:

2611 self.folded = chr(self.value)

2612

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

2614 self.case_flags, self.zerowidth)

2615

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

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

2618

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

2620 return self

2621

2622 def get_firstset(self, reverse):

2623 return set([self])

2624

2625 def has_simple_start(self):

2626 return True

2627

2628 def _compile(self, reverse, fuzzy):

2629 flags = 0

2630 if self.positive:

2631 flags |= POSITIVE_OP

2632 if self.zerowidth:

2633 flags |= ZEROWIDTH_OP

2634 if fuzzy:

2635 flags |= FUZZY_OP

2636

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

2638 self.value])

2639

2640 if len(self.folded) > 1:

2641 # The character expands on full case-folding.

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

2643 case_flags=self.case_flags)])

2644

2645 return code.compile(reverse, fuzzy)

2646

2647 def dump(self, indent, reverse):

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

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

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

2651

2652 def matches(self, ch):

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

2654

2655 def max_width(self):

2656 return len(self.folded)

2657

2658 def get_required_string(self, reverse):

2659 if not self.positive:

2660 return 1, None

2661

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

2663

2664 return 0, self

2665

2666class Conditional(RegexBase):

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

2668 RegexBase.__init__(self)

2669 self.info = info

2670 self.group = group

2671 self.yes_item = yes_item

2672 self.no_item = no_item

2673 self.position = position

2674

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

2676 try:

2677 self.group = int(self.group)

2678 except ValueError:

2679 try:

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

2681 except KeyError:

2682 if self.group == 'DEFINE':

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

2684 # that name.

2685 self.group = 0

2686 else:

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

2688

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

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

2691

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

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

2694

2695 def optimise(self, info, reverse):

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

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

2698

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

2700

2701 def pack_characters(self, info):

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

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

2704 return self

2705

2706 def remove_captures(self):

2707 self.yes_item = self.yes_item.remove_captures()

2708 self.no_item = self.no_item.remove_captures()

2709

2710 def is_atomic(self):

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

2712

2713 def can_be_affix(self):

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

2715

2716 def contains_group(self):

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

2718

2719 def get_firstset(self, reverse):

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

2721 self.no_item.get_firstset(reverse))

2722

2723 def _compile(self, reverse, fuzzy):

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

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

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

2727 if add_code:

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

2729 code.extend(add_code)

2730

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

2732

2733 return code

2734

2735 def dump(self, indent, reverse):

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

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

2738 if not self.no_item.is_empty():

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

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

2741

2742 def is_empty(self):

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

2744

2745 def __eq__(self, other):

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

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

2748

2749 def max_width(self):

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

2751

2752 def __del__(self):

2753 self.info = None

2754

2755class DefaultBoundary(ZeroWidthBase):

2756 _opcode = OP.DEFAULT_BOUNDARY

2757 _op_name = "DEFAULT_BOUNDARY"

2758

2759class DefaultEndOfWord(ZeroWidthBase):

2760 _opcode = OP.DEFAULT_END_OF_WORD

2761 _op_name = "DEFAULT_END_OF_WORD"

2762

2763class DefaultStartOfWord(ZeroWidthBase):

2764 _opcode = OP.DEFAULT_START_OF_WORD

2765 _op_name = "DEFAULT_START_OF_WORD"

2766

2767class EndOfLine(ZeroWidthBase):

2768 _opcode = OP.END_OF_LINE

2769 _op_name = "END_OF_LINE"

2770

2771class EndOfLineU(EndOfLine):

2772 _opcode = OP.END_OF_LINE_U

2773 _op_name = "END_OF_LINE_U"

2774

2775class EndOfString(ZeroWidthBase):

2776 _opcode = OP.END_OF_STRING

2777 _op_name = "END_OF_STRING"

2778

2779class EndOfStringLine(ZeroWidthBase):

2780 _opcode = OP.END_OF_STRING_LINE

2781 _op_name = "END_OF_STRING_LINE"

2782

2783class EndOfStringLineU(EndOfStringLine):

2784 _opcode = OP.END_OF_STRING_LINE_U

2785 _op_name = "END_OF_STRING_LINE_U"

2786

2787class EndOfWord(ZeroWidthBase):

2788 _opcode = OP.END_OF_WORD

2789 _op_name = "END_OF_WORD"

2790

2791class Failure(ZeroWidthBase):

2792 _op_name = "FAILURE"

2793

2794 def _compile(self, reverse, fuzzy):

2795 return [(OP.FAILURE, )]

2796

2797class Fuzzy(RegexBase):

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

2799 RegexBase.__init__(self)

2800 if constraints is None:

2801 constraints = {}

2802 self.subpattern = subpattern

2803 self.constraints = constraints

2804

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

2806 # defaults to unlimited.

2807 if "cost" in constraints:

2808 for e in "dis":

2809 if e in constraints["cost"]:

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

2811

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

2813 # 0, otherwise they default to unlimited.

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

2815 for e in "dis":

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

2817 else:

2818 for e in "dis":

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

2820

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

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

2823

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

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

2826 if "cost" in constraints:

2827 for e in "dis":

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

2829 else:

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

2831 constraints["e"][1]}

2832

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

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

2835

2836 def pack_characters(self, info):

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

2838 return self

2839

2840 def remove_captures(self):

2841 self.subpattern = self.subpattern.remove_captures()

2842 return self

2843

2844 def is_atomic(self):

2845 return self.subpattern.is_atomic()

2846

2847 def contains_group(self):

2848 return self.subpattern.contains_group()

2849

2850 def _compile(self, reverse, fuzzy):

2851 # The individual limits.

2852 arguments = []

2853 for e in "dise":

2854 v = self.constraints[e]

2855 arguments.append(v[0])

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

2857

2858 # The coeffs of the cost equation.

2859 for e in "dis":

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

2861

2862 # The maximum of the cost equation.

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

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

2865

2866 flags = 0

2867 if reverse:

2868 flags |= REVERSE_OP

2869

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

2871

2872 if test:

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

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

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

2876

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

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

2879

2880 def dump(self, indent, reverse):

2881 constraints = self._constraints_to_string()

2882 if constraints:

2883 constraints = " " + constraints

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

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

2886

2887 def is_empty(self):

2888 return self.subpattern.is_empty()

2889

2890 def __eq__(self, other):

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

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

2893

2894 def max_width(self):

2895 return UNLIMITED

2896

2897 def _constraints_to_string(self):

2898 constraints = []

2899

2900 for name in "ids":

2901 min, max = self.constraints[name]

2902 if max == 0:

2903 continue

2904

2905 con = ""

2906

2907 if min > 0:

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

2909

2910 con += name

2911

2912 if max is not None:

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

2914

2915 constraints.append(con)

2916

2917 cost = []

2918 for name in "ids":

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

2920 if coeff > 0:

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

2922

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

2924 if limit is not None and limit > 0:

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

2926 constraints.append(cost)

2927

2928 return ",".join(constraints)

2929

2930class Grapheme(RegexBase):

2931 def _compile(self, reverse, fuzzy):

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

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

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

2935 GraphemeBoundary()]))

2936

2937 return grapheme_matcher.compile(reverse, fuzzy)

2938

2939 def dump(self, indent, reverse):

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

2941

2942 def max_width(self):

2943 return UNLIMITED

2944

2945class GraphemeBoundary:

2946 def compile(self, reverse, fuzzy):

2947 return [(OP.GRAPHEME_BOUNDARY, 1)]

2948

2949class GreedyRepeat(RegexBase):

2950 _opcode = OP.GREEDY_REPEAT

2951 _op_name = "GREEDY_REPEAT"

2952

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

2954 RegexBase.__init__(self)

2955 self.subpattern = subpattern

2956 self.min_count = min_count

2957 self.max_count = max_count

2958

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

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

2961

2962 def optimise(self, info, reverse):

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

2964

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

2966

2967 def pack_characters(self, info):

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

2969 return self

2970

2971 def remove_captures(self):

2972 self.subpattern = self.subpattern.remove_captures()

2973 return self

2974

2975 def is_atomic(self):

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

2977

2978 def can_be_affix(self):

2979 return False

2980

2981 def contains_group(self):

2982 return self.subpattern.contains_group()

2983

2984 def get_firstset(self, reverse):

2985 fs = self.subpattern.get_firstset(reverse)

2986 if self.min_count == 0:

2987 fs.add(None)

2988

2989 return fs

2990

2991 def _compile(self, reverse, fuzzy):

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

2993 if self.max_count is None:

2994 repeat.append(UNLIMITED)

2995 else:

2996 repeat.append(self.max_count)

2997

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

2999 if not subpattern:

3000 return []

3001

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

3003

3004 def dump(self, indent, reverse):

3005 if self.max_count is None:

3006 limit = "INF"

3007 else:

3008 limit = self.max_count

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

3010 self.min_count, limit))

3011

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

3013

3014 def is_empty(self):

3015 return self.subpattern.is_empty()

3016

3017 def __eq__(self, other):

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

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

3020 other.max_count)

3021

3022 def max_width(self):

3023 if self.max_count is None:

3024 return UNLIMITED

3025

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

3027

3028 def get_required_string(self, reverse):

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

3030 if self.min_count == 0:

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

3032 return min(w, UNLIMITED), None

3033

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

3035 if req:

3036 return ofs, req

3037

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

3039 return min(w, UNLIMITED), None

3040

3041class PossessiveRepeat(GreedyRepeat):

3042 def is_atomic(self):

3043 return True

3044

3045 def _compile(self, reverse, fuzzy):

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

3047 if not subpattern:

3048 return []

3049

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

3051 if self.max_count is None:

3052 repeat.append(UNLIMITED)

3053 else:

3054 repeat.append(self.max_count)

3055

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

3057 (OP.END, )])

3058

3059 def dump(self, indent, reverse):

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

3061

3062 if self.max_count is None:

3063 limit = "INF"

3064 else:

3065 limit = self.max_count

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

3067 self.min_count, limit))

3068

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

3070

3071class Group(RegexBase):

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

3073 RegexBase.__init__(self)

3074 self.info = info

3075 self.group = group

3076 self.subpattern = subpattern

3077

3078 self.call_ref = None

3079

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

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

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

3083

3084 def optimise(self, info, reverse):

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

3086

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

3088

3089 def pack_characters(self, info):

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

3091 return self

3092

3093 def remove_captures(self):

3094 return self.subpattern.remove_captures()

3095

3096 def is_atomic(self):

3097 return self.subpattern.is_atomic()

3098

3099 def can_be_affix(self):

3100 return False

3101

3102 def contains_group(self):

3103 return True

3104

3105 def get_firstset(self, reverse):

3106 return self.subpattern.get_firstset(reverse)

3107

3108 def has_simple_start(self):

3109 return self.subpattern.has_simple_start()

3110

3111 def _compile(self, reverse, fuzzy):

3112 code = []

3113

3114 public_group = private_group = self.group

3115 if private_group < 0:

3116 public_group = self.info.private_groups[private_group]

3117 private_group = self.info.group_count - private_group

3118

3119 key = self.group, reverse, fuzzy

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

3121 if ref is not None:

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

3123

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

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

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

3127

3128 if ref is not None:

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

3130

3131 return code

3132

3133 def dump(self, indent, reverse):

3134 group = self.group

3135 if group < 0:

3136 group = self.info.private_groups[group]

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

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

3139

3140 def __eq__(self, other):

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

3142 (other.group, other.subpattern))

3143

3144 def max_width(self):

3145 return self.subpattern.max_width()

3146

3147 def get_required_string(self, reverse):

3148 return self.subpattern.get_required_string(reverse)

3149

3150 def __del__(self):

3151 self.info = None

3152

3153class Keep(ZeroWidthBase):

3154 _opcode = OP.KEEP

3155 _op_name = "KEEP"

3156

3157class LazyRepeat(GreedyRepeat):

3158 _opcode = OP.LAZY_REPEAT

3159 _op_name = "LAZY_REPEAT"

3160

3161class LookAround(RegexBase):

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

3163

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

3165 RegexBase.__init__(self)

3166 self.behind = bool(behind)

3167 self.positive = bool(positive)

3168 self.subpattern = subpattern

3169

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

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

3172

3173 def optimise(self, info, reverse):

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

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

3176 return subpattern

3177

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

3179

3180 def pack_characters(self, info):

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

3182 return self

3183

3184 def remove_captures(self):

3185 return self.subpattern.remove_captures()

3186

3187 def is_atomic(self):

3188 return self.subpattern.is_atomic()

3189

3190 def can_be_affix(self):

3191 return self.subpattern.can_be_affix()

3192

3193 def contains_group(self):

3194 return self.subpattern.contains_group()

3195

3196 def get_firstset(self, reverse):

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

3198 return self.subpattern.get_firstset(reverse)

3199

3200 return set([None])

3201

3202 def _compile(self, reverse, fuzzy):

3203 flags = 0

3204 if self.positive:

3205 flags |= POSITIVE_OP

3206 if fuzzy:

3207 flags |= FUZZY_OP

3208 if reverse:

3209 flags |= REVERSE_OP

3210

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

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

3213

3214 def dump(self, indent, reverse):

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

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

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

3218

3219 def is_empty(self):

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

3221

3222 def __eq__(self, other):

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

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

3225

3226 def max_width(self):

3227 return 0

3228

3229class LookAroundConditional(RegexBase):

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

3231

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

3233 RegexBase.__init__(self)

3234 self.behind = bool(behind)

3235 self.positive = bool(positive)

3236 self.subpattern = subpattern

3237 self.yes_item = yes_item

3238 self.no_item = no_item

3239

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

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

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

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

3244

3245 def optimise(self, info, reverse):

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

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

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

3249

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

3251 yes_item, no_item)

3252

3253 def pack_characters(self, info):

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

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

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

3257 return self

3258

3259 def remove_captures(self):

3260 self.subpattern = self.subpattern.remove_captures()

3261 self.yes_item = self.yes_item.remove_captures()

3262 self.no_item = self.no_item.remove_captures()

3263

3264 def is_atomic(self):

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

3266 self.no_item.is_atomic())

3267

3268 def can_be_affix(self):

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

3270 and self.no_item.can_be_affix())

3271

3272 def contains_group(self):

3273 return (self.subpattern.contains_group() or

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

3275

3276 def _compile(self, reverse, fuzzy):

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

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

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

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

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

3282 if add_code:

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

3284 code.extend(add_code)

3285

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

3287

3288 return code

3289

3290 def dump(self, indent, reverse):

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

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

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

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

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

3296 if not self.no_item.is_empty():

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

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

3299

3300 def is_empty(self):

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

3302

3303 def __eq__(self, other):

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

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

3306

3307 def max_width(self):

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

3309

3310 def get_required_string(self, reverse):

3311 return self.max_width(), None

3312

3313class PrecompiledCode(RegexBase):

3314 def __init__(self, code):

3315 self.code = code

3316

3317 def _compile(self, reverse, fuzzy):

3318 return [tuple(self.code)]

3319

3320class Property(RegexBase):

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

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

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

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

3325 True): OP.PROPERTY_IGN_REV}

3326

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

3328 zerowidth=False, encoding=0):

3329 RegexBase.__init__(self)

3330 self.value = value

3331 self.positive = bool(positive)

3332 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

3333 self.zerowidth = bool(zerowidth)

3334 self.encoding = encoding

3335

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

3337 self.case_flags, self.zerowidth)

3338

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

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

3341 self.encoding)

3342

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

3344 return self

3345

3346 def get_firstset(self, reverse):

3347 return set([self])

3348

3349 def has_simple_start(self):

3350 return True

3351

3352 def _compile(self, reverse, fuzzy):

3353 flags = 0

3354 if self.positive:

3355 flags |= POSITIVE_OP

3356 if self.zerowidth:

3357 flags |= ZEROWIDTH_OP

3358 if fuzzy:

3359 flags |= FUZZY_OP

3360 flags |= self.encoding << ENCODING_OP_SHIFT

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

3362

3363 def dump(self, indent, reverse):

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

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

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

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

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

3369

3370 def matches(self, ch):

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

3372

3373 def max_width(self):

3374 return 1

3375

3376class Prune(ZeroWidthBase):

3377 _op_name = "PRUNE"

3378

3379 def _compile(self, reverse, fuzzy):

3380 return [(OP.PRUNE, )]

3381

3382class Range(RegexBase):

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

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

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

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

3387 _op_name = "RANGE"

3388

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

3390 zerowidth=False):

3391 RegexBase.__init__(self)

3392 self.lower = lower

3393 self.upper = upper

3394 self.positive = bool(positive)

3395 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

3396 self.zerowidth = bool(zerowidth)

3397

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

3399 self.case_flags, self.zerowidth)

3400

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

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

3403

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

3405 # Is the range case-sensitive?

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

3407 return self

3408

3409 # Is full case-folding possible?

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

3411 FULLIGNORECASE):

3412 return self

3413

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

3415 expanding_chars = _regex.get_expand_on_folding()

3416

3417 # Get the folded characters in the range.

3418 items = []

3419 for ch in expanding_chars:

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

3421 folded = _regex.fold_case(FULL_CASE_FOLDING, ch)

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

3423 case_flags=self.case_flags))

3424

3425 if not items:

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

3427 return self

3428

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

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

3431 items.insert(0, self)

3432

3433 return Branch(items)

3434

3435 def _compile(self, reverse, fuzzy):

3436 flags = 0

3437 if self.positive:

3438 flags |= POSITIVE_OP

3439 if self.zerowidth:

3440 flags |= ZEROWIDTH_OP

3441 if fuzzy:

3442 flags |= FUZZY_OP

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

3444 self.upper)]

3445

3446 def dump(self, indent, reverse):

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

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

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

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

3451 CASE_TEXT[self.case_flags]))

3452

3453 def matches(self, ch):

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

3455

3456 def max_width(self):

3457 return 1

3458

3459class RefGroup(RegexBase):

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

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

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

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

3464 (FULLIGNORECASE, True): OP.REF_GROUP_FLD_REV}

3465

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

3467 RegexBase.__init__(self)

3468 self.info = info

3469 self.group = group

3470 self.position = position

3471 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

3472

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

3474

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

3476 try:

3477 self.group = int(self.group)

3478 except ValueError:

3479 try:

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

3481 except KeyError:

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

3483

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

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

3486

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

3488

3489 def remove_captures(self):

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

3491

3492 def _compile(self, reverse, fuzzy):

3493 flags = 0

3494 if fuzzy:

3495 flags |= FUZZY_OP

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

3497

3498 def dump(self, indent, reverse):

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

3500 CASE_TEXT[self.case_flags]))

3501

3502 def max_width(self):

3503 return UNLIMITED

3504

3505 def __del__(self):

3506 self.info = None

3507

3508class SearchAnchor(ZeroWidthBase):

3509 _opcode = OP.SEARCH_ANCHOR

3510 _op_name = "SEARCH_ANCHOR"

3511

3512class Sequence(RegexBase):

3513 def __init__(self, items=None):

3514 RegexBase.__init__(self)

3515 if items is None:

3516 items = []

3517

3518 self.items = items

3519

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

3521 for s in self.items:

3522 s.fix_groups(pattern, reverse, fuzzy)

3523

3524 def optimise(self, info, reverse):

3525 # Flatten the sequences.

3526 items = []

3527 for s in self.items:

3528 s = s.optimise(info, reverse)

3529 if isinstance(s, Sequence):

3530 items.extend(s.items)

3531 else:

3532 items.append(s)

3533

3534 return make_sequence(items)

3535

3536 def pack_characters(self, info):

3537 "Packs sequences of characters into strings."

3538 items = []

3539 characters = []

3540 case_flags = NOCASE

3541 for s in self.items:

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

3543 if s.case_flags != case_flags:

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

3545 # previous nor the new character are cased.

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

3547 Sequence._flush_characters(info, characters,

3548 case_flags, items)

3549

3550 case_flags = s.case_flags

3551

3552 characters.append(s.value)

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

3554 if s.case_flags != case_flags:

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

3556 # the previous nor the new string are cased.

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

3558 characters):

3559 Sequence._flush_characters(info, characters,

3560 case_flags, items)

3561

3562 case_flags = s.case_flags

3563

3564 characters.extend(s.characters)

3565 else:

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

3567

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

3569

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

3571

3572 return make_sequence(items)

3573

3574 def remove_captures(self):

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

3576 return self

3577

3578 def is_atomic(self):

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

3580

3581 def can_be_affix(self):

3582 return False

3583

3584 def contains_group(self):

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

3586

3587 def get_firstset(self, reverse):

3588 fs = set()

3589 items = self.items

3590 if reverse:

3591 items.reverse()

3592 for s in items:

3593 fs |= s.get_firstset(reverse)

3594 if None not in fs:

3595 return fs

3596 fs.discard(None)

3597

3598 return fs | set([None])

3599

3600 def has_simple_start(self):

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

3602

3603 def _compile(self, reverse, fuzzy):

3604 seq = self.items

3605 if reverse:

3606 seq = seq[::-1]

3607

3608 code = []

3609 for s in seq:

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

3611

3612 return code

3613

3614 def dump(self, indent, reverse):

3615 for s in self.items:

3616 s.dump(indent, reverse)

3617

3618 @staticmethod

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

3620 if not characters:

3621 return

3622

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

3624 if case_flags & IGNORECASE:

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

3626 case_flags = NOCASE

3627

3628 if (case_flags & FULLIGNORECASE) == FULLIGNORECASE:

3629 literals = Sequence._fix_full_casefold(characters)

3630

3631 for item in literals:

3632 chars = item.characters

3633

3634 if len(chars) == 1:

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

3636 else:

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

3638 else:

3639 if len(characters) == 1:

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

3641 else:

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

3643

3644 characters[:] = []

3645

3646 @staticmethod

3647 def _fix_full_casefold(characters):

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

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

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

3651 _regex.get_expand_on_folding()]

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

3653 for c in characters)).lower()

3654 chunks = []

3655

3656 for e in expanded:

3657 found = string.find(e)

3658

3659 while found >= 0:

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

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

3662

3663 pos = 0

3664 literals = []

3665

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

3667 if pos < start:

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

3669 case_flags=IGNORECASE))

3670

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

3672 case_flags=FULLIGNORECASE))

3673 pos = end

3674

3675 if pos < len(characters):

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

3677

3678 return literals

3679

3680 @staticmethod

3681 def _merge_chunks(chunks):

3682 if len(chunks) < 2:

3683 return chunks

3684

3685 chunks.sort()

3686

3687 start, end = chunks[0]

3688 new_chunks = []

3689

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

3691 if s <= end:

3692 end = max(end, e)

3693 else:

3694 new_chunks.append((start, end))

3695 start, end = s, e

3696

3697 new_chunks.append((start, end))

3698

3699 return new_chunks

3700

3701 def is_empty(self):

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

3703

3704 def __eq__(self, other):

3705 return type(self) is type(other) and self.items == other.items

3706

3707 def max_width(self):

3708 return sum(s.max_width() for s in self.items)

3709

3710 def get_required_string(self, reverse):

3711 seq = self.items

3712 if reverse:

3713 seq = seq[::-1]

3714

3715 offset = 0

3716

3717 for s in seq:

3718 ofs, req = s.get_required_string(reverse)

3719 offset += ofs

3720 if req:

3721 return offset, req

3722

3723 return offset, None

3724

3725class SetBase(RegexBase):

3726 def __init__(self, info, items, positive=True, case_flags=NOCASE,

3727 zerowidth=False):

3728 RegexBase.__init__(self)

3729 self.info = info

3730 self.items = tuple(items)

3731 self.positive = bool(positive)

3732 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

3733 self.zerowidth = bool(zerowidth)

3734

3735 self.char_width = 1

3736

3737 self._key = (self.__class__, self.items, self.positive,

3738 self.case_flags, self.zerowidth)

3739

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

3741 return type(self)(self.info, self.items, positive, case_flags,

3742 zerowidth).optimise(self.info, False)

3743

3744 def get_firstset(self, reverse):

3745 return set([self])

3746

3747 def has_simple_start(self):

3748 return True

3749

3750 def _compile(self, reverse, fuzzy):

3751 flags = 0

3752 if self.positive:

3753 flags |= POSITIVE_OP

3754 if self.zerowidth:

3755 flags |= ZEROWIDTH_OP

3756 if fuzzy:

3757 flags |= FUZZY_OP

3758 code = [(self._opcode[self.case_flags, reverse], flags)]

3759 for m in self.items:

3760 code.extend(m.compile())

3761

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

3763

3764 return code

3765

3766 def dump(self, indent, reverse):

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

3768 POS_TEXT[self.positive], CASE_TEXT[self.case_flags]))

3769 for i in self.items:

3770 i.dump(indent + 1, reverse)

3771

3772 def _handle_case_folding(self, info, in_set):

3773 # Is the set case-sensitive?

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

3775 return self

3776

3777 # Is full case-folding possible?

3778 if (not (self.info.flags & UNICODE) or (self.case_flags &

3779 FULLIGNORECASE) != FULLIGNORECASE):

3780 return self

3781

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

3783 expanding_chars = _regex.get_expand_on_folding()

3784

3785 # Get the folded characters in the set.

3786 items = []

3787 seen = set()

3788 for ch in expanding_chars:

3789 if self.matches(ord(ch)):

3790 folded = _regex.fold_case(FULL_CASE_FOLDING, ch)

3791 if folded not in seen:

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

3793 case_flags=self.case_flags))

3794 seen.add(folded)

3795

3796 if not items:

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

3798 return self

3799

3800 return Branch([self] + items)

3801

3802 def max_width(self):

3803 # Is the set case-sensitive?

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

3805 return 1

3806

3807 # Is full case-folding possible?

3808 if (not (self.info.flags & UNICODE) or (self.case_flags &

3809 FULLIGNORECASE) != FULLIGNORECASE):

3810 return 1

3811

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

3813 expanding_chars = _regex.get_expand_on_folding()

3814

3815 # Get the folded characters in the set.

3816 seen = set()

3817 for ch in expanding_chars:

3818 if self.matches(ord(ch)):

3819 folded = _regex.fold_case(FULL_CASE_FOLDING, ch)

3820 seen.add(folded)

3821

3822 if not seen:

3823 return 1

3824

3825 return max(len(folded) for folded in seen)

3826

3827 def __del__(self):

3828 self.info = None

3829

3830class SetDiff(SetBase):

3831 _opcode = {(NOCASE, False): OP.SET_DIFF, (IGNORECASE, False):

3832 OP.SET_DIFF_IGN, (FULLCASE, False): OP.SET_DIFF, (FULLIGNORECASE, False):

3833 OP.SET_DIFF_IGN, (NOCASE, True): OP.SET_DIFF_REV, (IGNORECASE, True):

3834 OP.SET_DIFF_IGN_REV, (FULLCASE, True): OP.SET_DIFF_REV, (FULLIGNORECASE,

3835 True): OP.SET_DIFF_IGN_REV}

3836 _op_name = "SET_DIFF"

3837

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

3839 items = self.items

3840 if len(items) > 2:

3841 items = [items[0], SetUnion(info, items[1 : ])]

3842

3843 if len(items) == 1:

3844 return items[0].with_flags(case_flags=self.case_flags,

3845 zerowidth=self.zerowidth).optimise(info, reverse, in_set)

3846

3847 self.items = tuple(m.optimise(info, reverse, in_set=True) for m in

3848 items)

3849

3850 return self._handle_case_folding(info, in_set)

3851

3852 def matches(self, ch):

3853 m = self.items[0].matches(ch) and not self.items[1].matches(ch)

3854 return m == self.positive

3855

3856class SetInter(SetBase):

3857 _opcode = {(NOCASE, False): OP.SET_INTER, (IGNORECASE, False):

3858 OP.SET_INTER_IGN, (FULLCASE, False): OP.SET_INTER, (FULLIGNORECASE,

3859 False): OP.SET_INTER_IGN, (NOCASE, True): OP.SET_INTER_REV, (IGNORECASE,

3860 True): OP.SET_INTER_IGN_REV, (FULLCASE, True): OP.SET_INTER_REV,

3861 (FULLIGNORECASE, True): OP.SET_INTER_IGN_REV}

3862 _op_name = "SET_INTER"

3863

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

3865 items = []

3866 for m in self.items:

3867 m = m.optimise(info, reverse, in_set=True)

3868 if isinstance(m, SetInter) and m.positive:

3869 # Intersection in intersection.

3870 items.extend(m.items)

3871 else:

3872 items.append(m)

3873

3874 if len(items) == 1:

3875 return items[0].with_flags(case_flags=self.case_flags,

3876 zerowidth=self.zerowidth).optimise(info, reverse, in_set)

3877

3878 self.items = tuple(items)

3879

3880 return self._handle_case_folding(info, in_set)

3881

3882 def matches(self, ch):

3883 m = all(i.matches(ch) for i in self.items)

3884 return m == self.positive

3885

3886class SetSymDiff(SetBase):

3887 _opcode = {(NOCASE, False): OP.SET_SYM_DIFF, (IGNORECASE, False):

3888 OP.SET_SYM_DIFF_IGN, (FULLCASE, False): OP.SET_SYM_DIFF, (FULLIGNORECASE,

3889 False): OP.SET_SYM_DIFF_IGN, (NOCASE, True): OP.SET_SYM_DIFF_REV,

3890 (IGNORECASE, True): OP.SET_SYM_DIFF_IGN_REV, (FULLCASE, True):

3891 OP.SET_SYM_DIFF_REV, (FULLIGNORECASE, True): OP.SET_SYM_DIFF_IGN_REV}

3892 _op_name = "SET_SYM_DIFF"

3893

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

3895 items = []

3896 for m in self.items:

3897 m = m.optimise(info, reverse, in_set=True)

3898 if isinstance(m, SetSymDiff) and m.positive:

3899 # Symmetric difference in symmetric difference.

3900 items.extend(m.items)

3901 else:

3902 items.append(m)

3903

3904 if len(items) == 1:

3905 return items[0].with_flags(case_flags=self.case_flags,

3906 zerowidth=self.zerowidth).optimise(info, reverse, in_set)

3907

3908 self.items = tuple(items)

3909

3910 return self._handle_case_folding(info, in_set)

3911

3912 def matches(self, ch):

3913 m = False

3914 for i in self.items:

3915 m = m != i.matches(ch)

3916

3917 return m == self.positive

3918

3919class SetUnion(SetBase):

3920 _opcode = {(NOCASE, False): OP.SET_UNION, (IGNORECASE, False):

3921 OP.SET_UNION_IGN, (FULLCASE, False): OP.SET_UNION, (FULLIGNORECASE,

3922 False): OP.SET_UNION_IGN, (NOCASE, True): OP.SET_UNION_REV, (IGNORECASE,

3923 True): OP.SET_UNION_IGN_REV, (FULLCASE, True): OP.SET_UNION_REV,

3924 (FULLIGNORECASE, True): OP.SET_UNION_IGN_REV}

3925 _op_name = "SET_UNION"

3926

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

3928 items = []

3929 for m in self.items:

3930 m = m.optimise(info, reverse, in_set=True)

3931 if isinstance(m, SetUnion) and m.positive:

3932 # Union in union.

3933 items.extend(m.items)

3934 elif isinstance(m, AnyAll):

3935 return AnyAll()

3936 else:

3937 items.append(m)

3938

3939 # Are there complementary properties?

3940 properties = (set(), set())

3941

3942 for m in items:

3943 if isinstance(m, Property):

3944 properties[m.positive].add((m.value, m.case_flags, m.zerowidth))

3945

3946 if properties[0] & properties[1]:

3947 return AnyAll()

3948

3949 if len(items) == 1:

3950 i = items[0]

3951 return i.with_flags(positive=i.positive == self.positive,

3952 case_flags=self.case_flags,

3953 zerowidth=self.zerowidth).optimise(info, reverse, in_set)

3954

3955 self.items = tuple(items)

3956

3957 return self._handle_case_folding(info, in_set)

3958

3959 def _compile(self, reverse, fuzzy):

3960 flags = 0

3961 if self.positive:

3962 flags |= POSITIVE_OP

3963 if self.zerowidth:

3964 flags |= ZEROWIDTH_OP

3965 if fuzzy:

3966 flags |= FUZZY_OP

3967

3968 characters, others = defaultdict(list), []

3969 for m in self.items:

3970 if isinstance(m, Character):

3971 characters[m.positive].append(m.value)

3972 else:

3973 others.append(m)

3974

3975 code = [(self._opcode[self.case_flags, reverse], flags)]

3976

3977 for positive, values in characters.items():

3978 flags = 0

3979 if positive:

3980 flags |= POSITIVE_OP

3981 if len(values) == 1:

3982 code.append((OP.CHARACTER, flags, values[0]))

3983 else:

3984 code.append((OP.STRING, flags, len(values)) + tuple(values))

3985

3986 for m in others:

3987 code.extend(m.compile())

3988

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

3990

3991 return code

3992

3993 def matches(self, ch):

3994 m = any(i.matches(ch) for i in self.items)

3995 return m == self.positive

3996

3997class Skip(ZeroWidthBase):

3998 _op_name = "SKIP"

3999 _opcode = OP.SKIP

4000

4001class StartOfLine(ZeroWidthBase):

4002 _opcode = OP.START_OF_LINE

4003 _op_name = "START_OF_LINE"

4004

4005class StartOfLineU(StartOfLine):

4006 _opcode = OP.START_OF_LINE_U

4007 _op_name = "START_OF_LINE_U"

4008

4009class StartOfString(ZeroWidthBase):

4010 _opcode = OP.START_OF_STRING

4011 _op_name = "START_OF_STRING"

4012

4013class StartOfWord(ZeroWidthBase):

4014 _opcode = OP.START_OF_WORD

4015 _op_name = "START_OF_WORD"

4016

4017class String(RegexBase):

4018 _opcode = {(NOCASE, False): OP.STRING, (IGNORECASE, False): OP.STRING_IGN,

4019 (FULLCASE, False): OP.STRING, (FULLIGNORECASE, False): OP.STRING_FLD,

4020 (NOCASE, True): OP.STRING_REV, (IGNORECASE, True): OP.STRING_IGN_REV,

4021 (FULLCASE, True): OP.STRING_REV, (FULLIGNORECASE, True):

4022 OP.STRING_FLD_REV}

4023

4024 def __init__(self, characters, case_flags=NOCASE):

4025 self.characters = tuple(characters)

4026 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

4027

4028 if (self.case_flags & FULLIGNORECASE) == FULLIGNORECASE:

4029 folded_characters = []

4030 for char in self.characters:

4031 folded = _regex.fold_case(FULL_CASE_FOLDING, chr(char))

4032 folded_characters.extend(ord(c) for c in folded)

4033 else:

4034 folded_characters = self.characters

4035

4036 self.folded_characters = tuple(folded_characters)

4037 self.required = False

4038

4039 self._key = self.__class__, self.characters, self.case_flags

4040

4041 def get_firstset(self, reverse):

4042 if reverse:

4043 pos = -1

4044 else:

4045 pos = 0

4046 return set([Character(self.characters[pos],

4047 case_flags=self.case_flags)])

4048

4049 def has_simple_start(self):

4050 return True

4051

4052 def _compile(self, reverse, fuzzy):

4053 flags = 0

4054 if fuzzy:

4055 flags |= FUZZY_OP

4056 if self.required:

4057 flags |= REQUIRED_OP

4058 return [(self._opcode[self.case_flags, reverse], flags,

4059 len(self.folded_characters)) + self.folded_characters]

4060

4061 def dump(self, indent, reverse):

4062 display = ascii("".join(chr(c) for c in self.characters)).lstrip("bu")

4063 print("{}STRING {}{}".format(INDENT * indent, display,

4064 CASE_TEXT[self.case_flags]))

4065

4066 def max_width(self):

4067 return len(self.folded_characters)

4068

4069 def get_required_string(self, reverse):

4070 return 0, self

4071

4072class Literal(String):

4073 def dump(self, indent, reverse):

4074 literal = ''.join(chr(c) for c in self.characters)

4075 display = ascii(literal).lstrip("bu")

4076 print("{}LITERAL MATCH {}{}".format(INDENT * indent, display,

4077 CASE_TEXT[self.case_flags]))

4078

4079class StringSet(Branch):

4080 def __init__(self, info, name, case_flags=NOCASE):

4081 self.info = info

4082 self.name = name

4083 self.case_flags = CASE_FLAGS_COMBINATIONS[case_flags]

4084

4085 self._key = self.__class__, self.name, self.case_flags

4086

4087 self.set_key = (name, self.case_flags)

4088 if self.set_key not in info.named_lists_used:

4089 info.named_lists_used[self.set_key] = len(info.named_lists_used)

4090

4091 index = self.info.named_lists_used[self.set_key]

4092 items = self.info.kwargs[self.name]

4093

4094 case_flags = self.case_flags

4095

4096 encoding = self.info.flags & _ALL_ENCODINGS

4097 fold_flags = encoding | case_flags

4098

4099 choices = []

4100

4101 for string in items:

4102 if isinstance(string, str):

4103 string = [ord(c) for c in string]

4104

4105 choices.append([Character(c, case_flags=case_flags) for c in

4106 string])

4107

4108 # Sort from longest to shortest.

4109 choices.sort(key=len, reverse=True)

4110

4111 self.branches = [Sequence(choice) for choice in choices]

4112

4113 def dump(self, indent, reverse):

4114 print("{}STRING_SET {}{}".format(INDENT * indent, self.name,

4115 CASE_TEXT[self.case_flags]))

4116

4117 def __del__(self):

4118 self.info = None

4119

4120class Source:

4121 "Scanner for the regular expression source string."

4122 def __init__(self, string):

4123 if isinstance(string, str):

4124 self.string = string

4125 self.char_type = chr

4126 else:

4127 self.string = string.decode("latin-1")

4128 self.char_type = lambda c: bytes([c])

4129

4130 self.pos = 0

4131 self.ignore_space = False

4132 self.sep = string[ : 0]

4133

4134 def peek(self, override_ignore=False):

4135 string = self.string

4136 pos = self.pos

4137

4138 try:

4139 if self.ignore_space and not override_ignore:

4140 while True:

4141 if string[pos].isspace():

4142 # Skip over the whitespace.

4143 pos += 1

4144 elif string[pos] == "#":

4145 # Skip over the comment to the end of the line.

4146 pos = string.index("\n", pos)

4147 else:

4148 break

4149

4150 return string[pos]

4151 except IndexError:

4152 # We've reached the end of the string.

4153 return string[ : 0]

4154 except ValueError:

4155 # The comment extended to the end of the string.

4156 return string[ : 0]

4157

4158 def get(self, override_ignore=False):

4159 string = self.string

4160 pos = self.pos

4161

4162 try:

4163 if self.ignore_space and not override_ignore:

4164 while True:

4165 if string[pos].isspace():

4166 # Skip over the whitespace.

4167 pos += 1

4168 elif string[pos] == "#":

4169 # Skip over the comment to the end of the line.

4170 pos = string.index("\n", pos)

4171 else:

4172 break

4173

4174 ch = string[pos]

4175 self.pos = pos + 1

4176 return ch

4177 except IndexError:

4178 # We've reached the end of the string.

4179 self.pos = pos

4180 return string[ : 0]

4181 except ValueError:

4182 # The comment extended to the end of the string.

4183 self.pos = len(string)

4184 return string[ : 0]

4185

4186 def get_many(self, count=1):

4187 string = self.string

4188 pos = self.pos

4189

4190 try:

4191 if self.ignore_space:

4192 substring = []

4193

4194 while len(substring) < count:

4195 while True:

4196 if string[pos].isspace():

4197 # Skip over the whitespace.

4198 pos += 1

4199 elif string[pos] == "#":

4200 # Skip over the comment to the end of the line.

4201 pos = string.index("\n", pos)

4202 else:

4203 break

4204

4205 substring.append(string[pos])

4206 pos += 1

4207

4208 substring = "".join(substring)

4209 else:

4210 substring = string[pos : pos + count]

4211 pos += len(substring)

4212

4213 self.pos = pos

4214 return substring

4215 except IndexError:

4216 # We've reached the end of the string.

4217 self.pos = len(string)

4218 return "".join(substring)

4219 except ValueError:

4220 # The comment extended to the end of the string.

4221 self.pos = len(string)

4222 return "".join(substring)

4223

4224 def get_while(self, test_set, include=True, keep_spaces=False):

4225 string = self.string

4226 pos = self.pos

4227

4228 if self.ignore_space and not keep_spaces:

4229 try:

4230 substring = []

4231

4232 while True:

4233 if string[pos].isspace():

4234 # Skip over the whitespace.

4235 pos += 1

4236 elif string[pos] == "#":

4237 # Skip over the comment to the end of the line.

4238 pos = string.index("\n", pos)

4239 elif (string[pos] in test_set) == include:

4240 substring.append(string[pos])

4241 pos += 1

4242 else:

4243 break

4244

4245 self.pos = pos

4246 except IndexError:

4247 # We've reached the end of the string.

4248 self.pos = len(string)

4249 except ValueError:

4250 # The comment extended to the end of the string.

4251 self.pos = len(string)

4252

4253 return "".join(substring)

4254 else:

4255 try:

4256 while (string[pos] in test_set) == include:

4257 pos += 1

4258

4259 substring = string[self.pos : pos]

4260

4261 self.pos = pos

4262

4263 return substring

4264 except IndexError:

4265 # We've reached the end of the string.

4266 substring = string[self.pos : pos]

4267

4268 self.pos = pos

4269

4270 return substring

4271

4272 def skip_while(self, test_set, include=True):

4273 string = self.string

4274 pos = self.pos

4275

4276 try:

4277 if self.ignore_space:

4278 while True:

4279 if string[pos].isspace():

4280 # Skip over the whitespace.

4281 pos += 1

4282 elif string[pos] == "#":

4283 # Skip over the comment to the end of the line.

4284 pos = string.index("\n", pos)

4285 elif (string[pos] in test_set) == include:

4286 pos += 1

4287 else:

4288 break

4289 else:

4290 while (string[pos] in test_set) == include:

4291 pos += 1

4292

4293 self.pos = pos

4294 except IndexError:

4295 # We've reached the end of the string.

4296 self.pos = len(string)

4297 except ValueError:

4298 # The comment extended to the end of the string.

4299 self.pos = len(string)

4300

4301 def match(self, substring):

4302 string = self.string

4303 pos = self.pos

4304

4305 if self.ignore_space:

4306 try:

4307 for c in substring:

4308 while True:

4309 if string[pos].isspace():

4310 # Skip over the whitespace.

4311 pos += 1

4312 elif string[pos] == "#":

4313 # Skip over the comment to the end of the line.

4314 pos = string.index("\n", pos)

4315 else:

4316 break

4317

4318 if string[pos] != c:

4319 return False

4320

4321 pos += 1

4322

4323 self.pos = pos

4324

4325 return True

4326 except IndexError:

4327 # We've reached the end of the string.

4328 return False

4329 except ValueError:

4330 # The comment extended to the end of the string.

4331 return False

4332 else:

4333 if not string.startswith(substring, pos):

4334 return False

4335

4336 self.pos = pos + len(substring)

4337

4338 return True

4339

4340 def expect(self, substring):

4341 if not self.match(substring):

4342 raise error("missing {}".format(substring), self.string, self.pos)

4343

4344 def at_end(self):

4345 string = self.string

4346 pos = self.pos

4347

4348 try:

4349 if self.ignore_space:

4350 while True:

4351 if string[pos].isspace():

4352 pos += 1

4353 elif string[pos] == "#":

4354 pos = string.index("\n", pos)

4355 else:

4356 break

4357

4358 return pos >= len(string)

4359 except IndexError:

4360 # We've reached the end of the string.

4361 return True

4362 except ValueError:

4363 # The comment extended to the end of the string.

4364 return True

4365

4366class Info:

4367 "Info about the regular expression."

4368

4369 def __init__(self, flags=0, char_type=None, kwargs={}):

4370 if (flags & _ALL_VERSIONS) == _ALL_VERSIONS:

4371 raise ValueError("VERSION0 and VERSION1 flags are mutually incompatible")

4372

4373 flags |= DEFAULT_FLAGS[(flags & _ALL_VERSIONS) or DEFAULT_VERSION]

4374 self.flags = flags

4375 self.global_flags = flags

4376 self.inline_locale = False

4377

4378 self.kwargs = kwargs

4379

4380 self.group_count = 0

4381 self.group_index = {}

4382 self.group_name = {}

4383 self.char_type = char_type

4384 self.named_lists_used = {}

4385 self.open_groups = []

4386 self.open_group_count = {}

4387 self.defined_groups = {}

4388 self.group_calls = []

4389 self.private_groups = {}

4390

4391 def open_group(self, name=None):

4392 group = self.group_index.get(name)

4393 if group is None:

4394 while True:

4395 self.group_count += 1

4396 if name is None or self.group_count not in self.group_name:

4397 break

4398

4399 group = self.group_count

4400 if name:

4401 self.group_index[name] = group

4402 self.group_name[group] = name

4403

4404 if group in self.open_groups:

4405 # We have a nested named group. We'll assign it a private group

4406 # number, initially negative until we can assign a proper

4407 # (positive) number.

4408 group_alias = -(len(self.private_groups) + 1)

4409 self.private_groups[group_alias] = group

4410 group = group_alias

4411

4412 self.open_groups.append(group)

4413 self.open_group_count[group] = self.open_group_count.get(group, 0) + 1

4414

4415 return group

4416

4417 def close_group(self):

4418 self.open_groups.pop()

4419

4420 def is_open_group(self, name):

4421 # In version 1, a group reference can refer to an open group. We'll

4422 # just pretend the group isn't open.

4423 version = (self.flags & _ALL_VERSIONS) or DEFAULT_VERSION

4424 if version == VERSION1:

4425 return False

4426

4427 if name.isdigit():

4428 group = int(name)

4429 else:

4430 group = self.group_index.get(name)

4431

4432 return group in self.open_groups

4433

4434def _check_group_features(info, parsed):

4435 """Checks whether the reverse and fuzzy features of the group calls match

4436 the groups which they call.

4437 """

4438 call_refs = {}

4439 additional_groups = []

4440 for call, reverse, fuzzy in info.group_calls:

4441 # Look up the reference of this group call.

4442 key = (call.group, reverse, fuzzy)

4443 ref = call_refs.get(key)

4444 if ref is None:

4445 # This group doesn't have a reference yet, so look up its features.

4446 if call.group == 0:

4447 # Calling the pattern as a whole.

4448 rev = bool(info.flags & REVERSE)

4449 fuz = isinstance(parsed, Fuzzy)

4450 if (rev, fuz) != (reverse, fuzzy):

4451 # The pattern as a whole doesn't have the features we want,

4452 # so we'll need to make a copy of it with the desired

4453 # features.

4454 additional_groups.append((CallRef(len(call_refs), parsed),

4455 reverse, fuzzy))

4456 else:

4457 # Calling a capture group.

4458 def_info = info.defined_groups[call.group]

4459 group = def_info[0]

4460 if def_info[1 : ] != (reverse, fuzzy):

4461 # The group doesn't have the features we want, so we'll

4462 # need to make a copy of it with the desired features.

4463 additional_groups.append((group, reverse, fuzzy))

4464

4465 ref = len(call_refs)

4466 call_refs[key] = ref

4467

4468 call.call_ref = ref

4469

4470 info.call_refs = call_refs

4471 info.additional_groups = additional_groups

4472

4473def _get_required_string(parsed, flags):

4474 "Gets the required string and related info of a parsed pattern."

4475

4476 req_offset, required = parsed.get_required_string(bool(flags & REVERSE))

4477 if required:

4478 required.required = True

4479 if req_offset >= UNLIMITED:

4480 req_offset = -1

4481

4482 req_flags = required.case_flags

4483 if not (flags & UNICODE):

4484 req_flags &= ~UNICODE

4485

4486 req_chars = required.folded_characters

4487 else:

4488 req_offset = 0

4489 req_chars = ()

4490 req_flags = 0

4491

4492 return req_offset, req_chars, req_flags

4493

4494class Scanner:

4495 def __init__(self, lexicon, flags=0):

4496 self.lexicon = lexicon

4497

4498 # Combine phrases into a compound pattern.

4499 patterns = []

4500 for phrase, action in lexicon:

4501 # Parse the regular expression.

4502 source = Source(phrase)

4503 info = Info(flags, source.char_type)

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

4505 parsed = _parse_pattern(source, info)

4506 if not source.at_end():

4507 raise error("unbalanced parenthesis", source.string,

4508 source.pos)

4509

4510 # We want to forbid capture groups within each phrase.

4511 patterns.append(parsed.remove_captures())

4512

4513 # Combine all the subpatterns into one pattern.

4514 info = Info(flags)

4515 patterns = [Group(info, g + 1, p) for g, p in enumerate(patterns)]

4516 parsed = Branch(patterns)

4517

4518 # Optimise the compound pattern.

4519 reverse = bool(info.flags & REVERSE)

4520 parsed = parsed.optimise(info, reverse)

4521 parsed = parsed.pack_characters(info)

4522

4523 # Get the required string.

4524 req_offset, req_chars, req_flags = _get_required_string(parsed,

4525 info.flags)

4526

4527 # Check the features of the groups.

4528 _check_group_features(info, parsed)

4529

4530 # Complain if there are any group calls. They are not supported by the

4531 # Scanner class.

4532 if info.call_refs:

4533 raise error("recursive regex not supported by Scanner",

4534 source.string, source.pos)

4535

4536 reverse = bool(info.flags & REVERSE)

4537

4538 # Compile the compound pattern. The result is a list of tuples.

4539 code = parsed.compile(reverse) + [(OP.SUCCESS, )]

4540

4541 # Flatten the code into a list of ints.

4542 code = _flatten_code(code)

4543

4544 if not parsed.has_simple_start():

4545 # Get the first set, if possible.

4546 try:

4547 fs_code = _compile_firstset(info, parsed.get_firstset(reverse))

4548 fs_code = _flatten_code(fs_code)

4549 code = fs_code + code

4550 except _FirstSetError:

4551 pass

4552

4553 # Check the global flags for conflicts.

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

4555 if version not in (0, VERSION0, VERSION1):

4556 raise ValueError("VERSION0 and VERSION1 flags are mutually incompatible")

4557

4558 # Create the PatternObject.

4559 #

4560 # Local flags like IGNORECASE affect the code generation, but aren't

4561 # needed by the PatternObject itself. Conversely, global flags like

4562 # LOCALE _don't_ affect the code generation but _are_ needed by the

4563 # PatternObject.

4564 self.scanner = _regex.compile(None, (flags & GLOBAL_FLAGS) | version,

4565 code, {}, {}, {}, [], req_offset, req_chars, req_flags,

4566 len(patterns))

4567

4568 def scan(self, string):

4569 result = []

4570 append = result.append

4571 match = self.scanner.scanner(string).match

4572 i = 0

4573 while True:

4574 m = match()

4575 if not m:

4576 break

4577 j = m.end()

4578 if i == j:

4579 break

4580 action = self.lexicon[m.lastindex - 1][1]

4581 if hasattr(action, '__call__'):

4582 self.match = m

4583 action = action(self, m.group())

4584 if action is not None:

4585 append(action)

4586 i = j

4587

4588 return result, string[i : ]

4589

4590# Get the known properties dict.

4591PROPERTIES = _regex.get_properties()

4592

4593# Build the inverse of the properties dict.

4594PROPERTY_NAMES = {}

4595for prop_name, (prop_id, values) in PROPERTIES.items():

4596 name, prop_values = PROPERTY_NAMES.get(prop_id, ("", {}))

4597 name = max(name, prop_name, key=len)

4598 PROPERTY_NAMES[prop_id] = name, prop_values

4599

4600 for val_name, val_id in values.items():

4601 prop_values[val_id] = max(prop_values.get(val_id, ""), val_name,

4602 key=len)

4603

4604# Character escape sequences.

4605CHARACTER_ESCAPES = {

4606 "a": "\a",

4607 "b": "\b",

4608 "f": "\f",

4609 "n": "\n",

4610 "r": "\r",

4611 "t": "\t",

4612 "v": "\v",

4613}

4614

4615ASCII_ENCODING = 1

4616UNICODE_ENCODING = 2

4617

4618# Predefined character set escape sequences.

4619CHARSET_ESCAPES = {

4620 "d": lookup_property(None, "Digit", True),

4621 "D": lookup_property(None, "Digit", False),

4622 "h": lookup_property(None, "Blank", True),

4623 "s": lookup_property(None, "Space", True),

4624 "S": lookup_property(None, "Space", False),

4625 "w": lookup_property(None, "Word", True),

4626 "W": lookup_property(None, "Word", False),

4627}

4628

4629ASCII_CHARSET_ESCAPES = dict(CHARSET_ESCAPES)

4630ASCII_CHARSET_ESCAPES.update({

4631 "d": lookup_property(None, "Digit", True, encoding=ASCII_ENCODING),

4632 "D": lookup_property(None, "Digit", False, encoding=ASCII_ENCODING),

4633 "s": lookup_property(None, "Space", True, encoding=ASCII_ENCODING),

4634 "S": lookup_property(None, "Space", False, encoding=ASCII_ENCODING),

4635 "w": lookup_property(None, "Word", True, encoding=ASCII_ENCODING),

4636 "W": lookup_property(None, "Word", False, encoding=ASCII_ENCODING),

4637})

4638UNICODE_CHARSET_ESCAPES = dict(CHARSET_ESCAPES)

4639UNICODE_CHARSET_ESCAPES.update({

4640 "d": lookup_property(None, "Digit", True, encoding=UNICODE_ENCODING),

4641 "D": lookup_property(None, "Digit", False, encoding=UNICODE_ENCODING),

4642 "s": lookup_property(None, "Space", True, encoding=UNICODE_ENCODING),

4643 "S": lookup_property(None, "Space", False, encoding=UNICODE_ENCODING),

4644 "w": lookup_property(None, "Word", True, encoding=UNICODE_ENCODING),

4645 "W": lookup_property(None, "Word", False, encoding=UNICODE_ENCODING),

4646})

4647

4648# Positional escape sequences.

4649POSITION_ESCAPES = {

4650 "A": StartOfString(),

4651 "b": Boundary(),

4652 "B": Boundary(False),

4653 "K": Keep(),

4654 "m": StartOfWord(),

4655 "M": EndOfWord(),

4656 "Z": EndOfString(),

4657 "z": EndOfString(),

4658}

4659ASCII_POSITION_ESCAPES = dict(POSITION_ESCAPES)

4660ASCII_POSITION_ESCAPES.update({

4661 "b": Boundary(encoding=ASCII_ENCODING),

4662 "B": Boundary(False, encoding=ASCII_ENCODING),

4663 "m": StartOfWord(encoding=ASCII_ENCODING),

4664 "M": EndOfWord(encoding=ASCII_ENCODING),

4665})

4666UNICODE_POSITION_ESCAPES = dict(POSITION_ESCAPES)

4667UNICODE_POSITION_ESCAPES.update({

4668 "b": Boundary(encoding=UNICODE_ENCODING),

4669 "B": Boundary(False, encoding=UNICODE_ENCODING),

4670 "m": StartOfWord(encoding=UNICODE_ENCODING),

4671 "M": EndOfWord(encoding=UNICODE_ENCODING),

4672})

4673

4674# Positional escape sequences when WORD flag set.

4675WORD_POSITION_ESCAPES = dict(POSITION_ESCAPES)

4676WORD_POSITION_ESCAPES.update({

4677 "b": DefaultBoundary(),

4678 "B": DefaultBoundary(False),

4679 "m": DefaultStartOfWord(),

4680 "M": DefaultEndOfWord(),

4681})

4682

4683# Regex control verbs.

4684VERBS = {

4685 "FAIL": Failure(),

4686 "F": Failure(),

4687 "PRUNE": Prune(),

4688 "SKIP": Skip(),

4689}

Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/regex/_regex_core.py: 43%

2914 statements