Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""Stage: group.
3Consumes: tokens (classified), segments, structure, extracted (the
4role + inner span per delimited region, for the #329 pass below --
5the only stage after tokenize that reads it).
6Produces: pieces + piece_tags per segment (runs of token indices --
7tokens are NEVER joined into strings: the anti-#100 invariant); maiden
8tail tokens get role=MAIDEN; marker tokens land in dropped.
9Reads: token tags (from classify), Lexicon.given_name_titles (the
10P5 licence, #369) and Policy.extra_suffix_delimiters, whose
11delimiter-core tokens tail segments drop (v1 suffix_delimiter parity)
12-- no other Policy field. Policy.lenient_comma_suffixes left this list
13with #436: it reached here only through segment_suffix_reading, whose
14render consumer was this stage's one-entry join and now lives in
15post_rules. The v1 "derived titles/prefixes"
16registration becomes piece_tags entries -- per-parse state that
17dissolves with the state (v1 kept per-parse sets for the same reason).
19Implements rules P2, P3, P4 and M2, and the
20group half of M1 (#329: the marker dropped inside EXTRACTED maiden
21content, which M2's pieces walk cannot reach because extract's
22content never enters pieces); each is cited at its code below. Also
23implements rule P5 (cited below at the bound-given join) and ports
24the "Ph. D."-split merge (v1 fix_phd; decisions.md#phd-merge).
26The piece-level predicates moved to _pieces in #439 -- the S2
27trailing peel, the leading-title and title-piece tests, the
28suffix-piece test, the no-name-segment test. Most are shared with
29assign; is_title_piece and trailing_start are group's alone and
30travelled because the shared ones call them. They had collected here
31by import direction rather than by topic (assign imported group and
32could not be imported back), which is the accumulation
33mechanisms.md#ONE-PREDICATE-PER-QUESTION describes; group imports them
34back like any other caller, and still does the work H3 and S2 describe
35with them. What remains defined here is group's own: _is_prefix_piece,
36_is_conj_piece, _is_rootname and _is_maiden_marker_piece.
37"""
38from __future__ import annotations
40import bisect
41import dataclasses
42from collections.abc import Iterable, Sequence, Set
43from enum import IntEnum
45from nameparser._lexicon import _run_addresses_by_given
46from nameparser._pipeline._pieces import (
47 is_leading_title, is_suffix_piece, is_title_piece,
48 leading_titles, peel_walk, tail_reading, trailing_start,
49)
50from nameparser._pipeline._state import (
51 ParseState, PendingAmbiguity, Structure, WorkToken,
52)
53from nameparser._pipeline._vocab import D, PH
54from nameparser._pipeline._vocab import delimiter_cores
55from nameparser._types import AmbiguityKind, Role
57# the credential-pair regexes live in _vocab, whose own
58# is_wholly_suffix merges the same pair -- and since #319 that
59# predicate has TWO callers to stay in sync with, segment's
60# suffix-comma structure test and script_segment's decline of a
61# wholly-suffix post-comma run, both of which see the merged reading
63Piece = list[int]
64#: What the marker pass took out of a segment: the marker's tokens (to
65#: be dropped -- more than one where the entry is a phrase, 'z domu')
66#: and the maiden-name pieces (to take Role.MAIDEN).
67MaidenTake = tuple[Piece, list[Piece]]
70class BoundJoin(IntEnum):
71 """v1 _join_bound_first_name's reserve_last, as the three states it
72 actually has. IntEnum: the value IS the number of name pieces
73 assign's peel must leave in the JOINED view for the join to stand
74 (#425), so the >= comparison below reads unchanged. Post-comma no
75 peel is run -- the pair alone is that one piece -- and DISABLED
76 is a mode, never compared: as a threshold 0 would join everything,
77 which is why the block is entered on identity first."""
79 DISABLED = 0 # the FAMILY_COMMA family segment (v1 never joined it)
80 LENIENT = 1 # FAMILY_COMMA's post-comma segment (reserve_last=False)
81 STRICT = 2 # main segments (reserve_last=True: keep a family piece)
84# rules.md#S2: "a trailing word of the suffix vocabulary reads as a
85# suffix" -- group does not decide that; it stops before whatever
86# trailing_start says the run is, so the chain and the maiden walk
87# end where assign's peel begins (#424).
88# rules.md#P2: "a particle joins the words after it into one name
89# part, the join running until the next particle starts a group of
90# its own, a trailing suffix begins" -- and on to the maiden marker
91# (M2) or the name's end; the final group reads as the family name,
92# earlier groups by position. (history: decisions.md#P2)
93# rules.md#P4: "a particle in the name's leading position chains
94# nothing: the words stay separate" (history: decisions.md#P2)
95def _is_prefix_piece(piece: Sequence[int], ptags: Set[str],
96 tokens: Sequence[WorkToken]) -> bool:
97 if "prefix" in ptags:
98 return True
99 return len(piece) == 1 and "particle" in tokens[piece[0]].tags
102# rules.md#M2: "a recognized maiden marker standing after at least
103# one name word takes the words after it" -- up to any suffix word,
104# or the trailing numeral assign reads as the suffix, as the maiden
105# name, the marker itself dropped
106# (history: decisions.md#M2)
107#
108# A marker piece is a LONE marker -- M2's own "standing as a word of
109# its own". The consumer runs before every join but the Ph. D. merge
110# (see _group_segment), so a marker inside a wider piece is one the
111# consumer left there: declined ("Jane van der Berg née" reads family
112# 'van der Berg née'), or never examined (a leading marker, or a second
113# marker behind the span it took). Matching inside joined pieces would
114# re-read those.
115#
116# With the pass ahead of the joins no default-vocabulary input reaches
117# the lone-piece half through the one caller left that sees joined
118# pieces (P5's marker decline, marker(fk + 1)): a marker-headed wider
119# piece needs a connective right after a declined marker, and a
120# connective after a marker is a word the consumer takes. Measured at
121# #420's review --
122# dropping `len(piece) == 1` leaves the suite and a 337k-name sweep
123# identical -- so it stays as the rule's definition, not as a guard a
124# pin holds.
125def _is_maiden_marker_piece(piece: Sequence[int],
126 tokens: Sequence[WorkToken]) -> bool:
127 return (len(piece) == 1
128 and "vocab:maiden-marker" in tokens[piece[0]].tags)
131# mechanisms.md#ONE-PREDICATE-PER-QUESTION: "where the reader comes
132# AFTER the decider, record the answer on the state instead" -- which is
133# what the marker tags are. classify owns the phrase lookahead; group,
134# running later, reads what it wrote.
135def marker_run_length(following: Iterable[Set[str]]) -> int:
136 """How many tokens a marker run spans, given the tag sets of what
137 FOLLOWS its head, in order: 1 plus the leading continuations.
139 One walk for both places group asks -- over pieces below and over
140 token indices in the clause drop at the end of this module, 700
141 lines apart and differing only in index space. `following` is
142 consumed lazily and only until the run ends, so a caller passes a
143 generator over the rest of its sequence rather than materializing
144 one."""
145 run = 1
146 for tags in following:
147 if "vocab:maiden-marker-cont" not in tags:
148 break
149 run += 1
150 return run
153def _marker_run_pieces(seen: Sequence[int], pieces: Sequence[Sequence[int]],
154 tokens: Sequence[WorkToken], m: int) -> int:
155 """How many of `seen`'s pieces the marker run at seen[m] spans: 1
156 for a single-word marker, more for a phrase entry ('z domu').
158 classify already decided where the run ends and recorded it on the
159 tokens -- "vocab:maiden-marker" on the head,
160 "vocab:maiden-marker-cont" on the rest.
162 Each continuation is the NEXT piece and is always in `seen`, and
163 that holds because classify REFUSES to tag a run whose tokens are
164 not structurally contiguous. It is not a property of this walk, and
165 the reasons `seen` can skip a token are wider than they look. No
166 join has run yet, so a piece is one token. `seen` itself skips a
167 tail segment's delimiter cores, and a core between two marker words
168 would be a token between them, which classify would not have tagged
169 as a run. But `pieces` comes from a SEGMENT, and segment keeps only
170 the tokens no stage has given a role, bucketed by the commas before
171 them -- so a run half inside a bracketed clause, or split across a
172 structure comma, is one no segment holds whole. Walking cont tags
173 without classify's refusal read a proper PREFIX of the phrase as
174 the whole marker, and 'Anna z (domu) Nowak' lost its given name to
175 a bare preposition. Any future stage that removes a token from a
176 segment owes this the same refusal.
178 What classify guarantees is exactly the main stream's half of that
179 and no more: a run of ROLE-LESS tokens stays inside one segment. It
180 can also tag a run across two adjacent clauses of the same role,
181 which this walk never sees because a role-bearing token is in no
182 segment at all -- see _tag_marker_runs, which states the limit.
183 """
184 return marker_run_length(
185 tokens[pieces[seen[k]][0]].tags for k in range(m + 1, len(seen)))
188def _maiden_take(pieces: Sequence[Sequence[int]],
189 ptags: Sequence[Set[str]],
190 tokens: Sequence[WorkToken],
191 cores: Set[str]) -> tuple[list[int], list[int]] | None:
192 """The piece indices the marker pass removes, split the way
193 MaidenTake declares them: the MARKER's pieces (one, or several for
194 a phrase entry like 'z domu') and the maiden name's. None when the
195 pass declines.
197 Split here rather than by the caller because `run` is known here
198 and nowhere else -- it comes off the continuation tags, which are
199 read to find the walk's starting point in the first place.
201 Computed before any join (the Ph. D. merge aside), so "up to any
202 trailing suffix" means the first suffix WORD after the marker: a
203 connective beside that suffix cannot un-suffix it first. 'Jane
204 Smith née Jr y Jones' declines where the joined reading took
205 'Jr y Jones' as the maiden name, and 'Jane Smith née Jones Jr y
206 Smith' takes only 'Jones'. The one reading the order costs; M2's
207 Accepted row and decisions.md#M2 (#420) record it.
209 A tail segment's delimiter cores (`cores`, empty elsewhere) are
210 structure, not words, and group() drops them after the pass --
211 before the pass moved ahead of the joins it dropped them first.
212 So the walk steps over them: a core is neither a word the marker
213 can take ('PhD née - Jones' read maiden '- Jones') nor the name
214 word M2 needs ahead of the marker ('- née Jones' took 'Jones',
215 leaving the core alone, which the drop then kept as the segment's
216 only piece). They stay in place for the drop, which still sees
217 the segment as written, which is why this returns indices rather
218 than a slice.
219 """
220 seen = [k for k in range(len(pieces))
221 if not (len(pieces[k]) == 1
222 and tokens[pieces[k][0]].text in cores)]
223 m = next((v for v in range(1, len(seen))
224 if _is_maiden_marker_piece(pieces[seen[v]], tokens)), None)
225 if m is None:
226 return None
227 # the marker may be a phrase, in which case it is several pieces
228 run = _marker_run_pieces(seen, pieces, tokens, m)
229 # "up to any trailing suffix": a suffix WORD anywhere after the
230 # marker ends the maiden name, and so does the trailing numeral as
231 # assign will read it, which the suffix-piece test does not see
232 # (#424): 'John née Jones Smith V' took the V as maiden text. The
233 # numeral only -- trailing_start says why the acronym fork is
234 # left to assign here. Read from the MARKER, not after it: a
235 # numeral straight after the marker then has the piece before it
236 # the fork wants, and 'Jane Smith née V' declines like 'Jane Smith
237 # née PhD' -- nothing after the marker but a suffix, so the marker
238 # stays a word -- as 1.4.0 read it.
239 skip = frozenset(range(len(pieces))) - frozenset(seen)
240 trailing = trailing_start(seen[m], pieces, ptags, tokens, skip,
241 numeral_only=True)
242 # The fork reads the piece before the numeral, and the take
243 # REMOVES that piece: afterwards assign sees the piece before the
244 # marker there, and if that is initial-shaped the fork will not
245 # fire -- a walk that stopped anyway handed the V to the family
246 # ('J. née Jones Smith V'). So the numeral must read as the suffix
247 # as the take would leave the name too, and the question is asked
248 # the way P5's reserve asks it (#425): the peel is run over the
249 # VIEW the take would leave, not one condition of it -- the first
250 # re-ask checked the preceding piece alone, and a title before the
251 # marker ('Dr. née Jones Smith V') leaves the numeral as assign's
252 # whole rest, where no fork fires at all (the code review).
253 if trailing < len(pieces):
254 left = [i for i in seen if i < seen[m] or i >= trailing]
255 view = [pieces[i] for i in left]
256 view_tags = [ptags[i] for i in left]
257 if trailing_start(leading_titles(view, view_tags, tokens),
258 view, view_tags, tokens,
259 numeral_only=True) == len(view):
260 trailing = len(pieces)
261 j = m + run
262 while (j < len(seen) and seen[j] < trailing
263 and not is_suffix_piece(pieces[seen[j]], ptags[seen[j]],
264 tokens)):
265 j += 1
266 # j == m + run means nothing followed the marker but a suffix, so
267 # the pass declines and the marker stays ordinary words
268 # (rules.md#M2). The walk starts past the WHOLE marker: a phrase's
269 # second word is the marker, not the first word it takes.
270 if j <= m + run:
271 return None
272 return seen[m:m + run], seen[m + run:j]
275# rules.md#P3: "a recognized connective joins its neighbors into one
276# name part, connective runs included — except a single-letter
277# connective in a three-word name, which stays a name word, and a
278# single-letter connective that reads as an initial instead, which
279# never joins" (history: decisions.md#P3)
280def _is_conj_piece(piece: Sequence[int], ptags: Set[str],
281 tokens: Sequence[WorkToken]) -> bool:
282 if "conjunction" in ptags:
283 return True
284 return len(piece) == 1 and "conjunction" in tokens[piece[0]].tags
287def _is_rootname(piece: Sequence[int], ptags: Set[str],
288 tokens: Sequence[WorkToken]) -> bool:
289 if len(piece) == 1 and "initial" in tokens[piece[0]].tags:
290 return False
291 return not (is_title_piece(piece, ptags, tokens)
292 or _is_prefix_piece(piece, ptags, tokens)
293 or is_suffix_piece(piece, ptags, tokens))
296def _group_segment(seg: tuple[int, ...], additional: int,
297 tokens: Sequence[WorkToken],
298 bound_join: BoundJoin = BoundJoin.STRICT,
299 ambiguities: list[PendingAmbiguity] | None = None,
300 cores: Set[str] = frozenset(),
301 given_name_titles: Set[str] = frozenset(),
302 opens_the_name: bool = False,
303 ) -> tuple[list[Piece], list[set[str]], MaidenTake | None]:
304 pieces: list[Piece] = [[i] for i in seg]
305 ptags: list[set[str]] = [set() for _ in seg]
306 # Out-parameter, same shape as _assign_main: forks are reported
307 # where they are decided. A caller that passes None (or a throwaway
308 # list) suppresses reporting -- see group() for when that applies.
309 if ambiguities is None:
310 ambiguities = []
312 def title(k: int) -> bool:
313 return is_title_piece(pieces[k], ptags[k], tokens)
315 def prefix(k: int) -> bool:
316 return _is_prefix_piece(pieces[k], ptags[k], tokens)
318 def suffix(k: int) -> bool:
319 return is_suffix_piece(pieces[k], ptags[k], tokens)
321 def conj(k: int) -> bool:
322 return _is_conj_piece(pieces[k], ptags[k], tokens)
324 def marker(k: int) -> bool:
325 return _is_maiden_marker_piece(pieces[k], tokens)
327 def joined_tags(lo: int, hi: int, add: Set[str] = frozenset(),
328 drop: Set[str] = frozenset()) -> set[str]:
329 # the ONE definition of a merged piece's tags: merge() applies
330 # it, and P5's reserve reads it to model the join it is
331 # weighing (#425) -- so the view cannot drift from the merge.
332 # A merged piece inherits every part's tags, so a site whose
333 # product is not what its parts were drops what no longer
334 # applies: the particle chain drops `prefix`, the bound join
335 # `title` (a derived title tag on the pair would have assign
336 # peel the given name as a leading title).
337 return (set().union(*ptags[lo:hi]) | add) - drop
339 def merge(lo: int, hi: int, add: Set[str] = frozenset(),
340 drop: Set[str] = frozenset()) -> None:
341 # pieces/ptags are parallel arrays; every merge must update
342 # both in lockstep.
343 #
344 # Extend the first piece IN PLACE rather than rebuilding the
345 # merged list. The obvious spelling --
346 # pieces[lo:hi] = [[i for p in pieces[lo:hi] for i in p]]
347 # -- re-flattens everything accumulated so far on every call, so
348 # a chain that merges into the same piece n times copies
349 # 1+2+...+n and the stage goes quadratic in the length of the
350 # chain. A conjunction run ("and " * n) does exactly that: it
351 # measured 2.4x-2.9x per doubling against the 2.0x every other
352 # shape holds. No piece list is aliased outside this function
353 # (each starts as a fresh [i], and the callers only read
354 # pieces[k] before a merge), so mutating is safe; verified
355 # identical token/role/tag/span/ambiguity output over 54,877
356 # names. tests/v2/test_benchmark.py's "and " shape is the guard.
357 #
358 # Every call site passes lo < hi, and this REQUIRES it: with
359 # lo >= hi the slice assignment would insert rather than
360 # replace, putting a second reference to pieces[lo] into the
361 # array, and the next merge to touch either index would extend
362 # the same list twice. The old rebuild-a-fresh-list spelling
363 # was harmless there. Keep the bound if you add a caller.
364 combined = pieces[lo]
365 for piece in pieces[lo + 1:hi]:
366 combined.extend(piece)
367 pieces[lo:hi] = [combined]
368 ptags[lo:hi] = [joined_tags(lo, hi, add, drop)]
370 # ph-d merge first: "Ph." "D." adjacent -> one suffix piece
371 # (decisions.md#phd-merge; v1 fix_phd did this by regex on the
372 # raw string)
373 # A suffix never BEGINS a name: position outranks the vocabulary
374 # match (#371). This merge is what makes a leading "Ph." "D." a
375 # credential at all -- every other suffix-shaped word standing
376 # first already falls out as a title (H2's abbreviation clause, or
377 # TITLES membership) or as a name word, so the pair is the only
378 # shape that reaches the defect, and it reached it by emptying the
379 # family: "Ph. D. Van Johnson" read given 'Van Johnson' with no
380 # surname at all.
381 #
382 # WHERE THE INPUT BEGINS, and that is v1's own boundary rather
383 # than a new one: fix_phd was a regex requiring a preceding space
384 # (`\s(ph\.?\s+d\.?)`), so it could never fire at the head of the
385 # string and fired everywhere else -- mid-name as readily as
386 # trailing. Three tests, because "the head" has three meanings
387 # here and only one of them is v1's:
388 # `k == 0` the first PIECE, which is not the first word --
389 # extract_delimited removes a bracketed or quoted
390 # clause before segment runs, so `"Bob" Ph. D. John
391 # Smith` reaches this with the pair at k == 0 and a
392 # word standing before it in the input. v1 merges
393 # there; declining broke parity on 112 measured
394 # names, every one opening with a quote or bracket.
395 # `a[0] == 0` the first TOKEN, which is v1's boundary.
396 # seg_idx 0 and not after a family comma: a credential run
397 # legitimately opens segment 1 ("Smith, Ph. D.
398 # Jr.", C1's listing form), and segment 0 before a
399 # comma is the family the comma named, where v1
400 # merges too ("Ph. D., John" reads last 'Ph. D.').
401 #
402 # A leading TITLE is therefore NOT stepped over, unlike the #367
403 # scan below, and the two disagree on purpose: that scan asks
404 # where the NAME begins, this asks where the STRING does. `Sir
405 # Ph. D. Van Johnson` keeps suffix 'Ph. D.' with an empty family,
406 # which is #371's symptom surviving one word to the left -- 1.4.0
407 # parity, stated as a boundary in rules.md#S2 rather than fixed
408 # here, because "the first piece of the name" cannot be computed
409 # before this merge: `is_leading_title` is true of `Ph.` itself,
410 # so the scan would step over the very piece being judged.
411 k = 0
412 while k < len(pieces) - 1:
413 a, b = pieces[k], pieces[k + 1]
414 if (not (opens_the_name and k == 0 and a[0] == 0)
415 and len(a) == 1 and len(b) == 1
416 and PH.fullmatch(tokens[a[0]].text)
417 and D.fullmatch(tokens[b[0]].text)):
418 merge(k, k + 2, add={"suffix"})
419 else:
420 k += 1
422 # rules.md#M2: "a recognized maiden marker standing after at least
423 # one name word takes the words after it" -- up to any suffix
424 # word, or the trailing numeral assign reads as the suffix, as the
425 # maiden name, the marker itself dropped
426 # (history: decisions.md#M2) -- the marker pass (#274), and it runs
427 # BEFORE every join below. Each join rule asks a question about the
428 # name -- how many words it has (P3's carve-out, P5's reserve),
429 # what the word after a particle or a bound word is -- and the
430 # marker and the maiden name are not part of that name: they leave.
431 # Asked while they were still pieces, the count answered for a name
432 # that would not exist ('juan y garcia nee jones' counted five, 'y'
433 # joined, and the family was empty once the clause left: #418), and
434 # a join could absorb the marker before the pass looked for a lone
435 # one ('Jane van der Berg née y Jones' kept the marker in the
436 # family: #412). Removing the pieces first makes both impossible by
437 # construction, with no stop on the chain (#399, #417) and no
438 # exclusion in the reserve (#411) left to keep in step.
439 #
440 # The tokens are not touched here: this function reads them and
441 # returns what it took, and group() records the drop and the roles.
442 taken: MaidenTake | None = None
443 take = _maiden_take(pieces, ptags, tokens, cores)
444 if take is not None:
445 marker_ks, maiden_ks = take
446 taken = ([i for k in marker_ks for i in pieces[k]],
447 [pieces[k] for k in maiden_ks])
448 for k in reversed(marker_ks + maiden_ks):
449 del pieces[k]
450 del ptags[k]
452 if len(pieces) + additional >= 3:
453 total = sum(_is_rootname(p, t, tokens)
454 for p, t in zip(pieces, ptags)) + additional
455 # contiguous conjunction runs merge first (v1: "of the")
456 k = 0
457 while k < len(pieces) - 1:
458 if conj(k) and conj(k + 1):
459 merge(k, k + 2, add={"conjunction"})
460 else:
461 k += 1
462 # each conjunction joins its neighbors, rules.md#P3: "except a
463 # single-letter connective in a three-word name, which stays a
464 # name word" (v1's Google Code issue 11 carve-out, the
465 # "john e smith" bug). The threshold reads the ROOTNAME count,
466 # so a conjunction that is also suffix vocabulary raises the
467 # bar for itself -- #397 measures that on "i".
468 k = 0
469 while k < len(pieces):
470 if not conj(k):
471 k += 1
472 continue
473 text = " ".join(tokens[i].text for i in pieces[k])
474 if len(text) == 1 and total < 4 and text.isalpha():
475 k += 1
476 continue
477 start = max(0, k - 1)
478 end = min(len(pieces), k + 2)
479 neighbor = start if start < k else end - 1
480 derived = set()
481 if title(neighbor):
482 derived.add("title")
483 if prefix(neighbor):
484 derived.add("prefix")
485 merge(start, end, add=derived)
486 k = start + 1
487 # prefix chains: a non-leading prefix run absorbs everything to
488 # the next prefix or suffix (v1's leading_first_name rule keeps
489 # the first piece a name: "Van Johnson")
490 #
491 # "Leading" means the first piece of the NAME, not of the input
492 # (#367): a title is not part of the name, so it must not decide
493 # whether the name begins with a particle. Keyed on index 0, a
494 # title displaced the particle and the chain fired, so identical
495 # name text parsed two ways ("Van Johnson" -> given Van, family
496 # Johnson; "Dr. Van Johnson" -> family "Van Johnson").
497 #
498 # "Title AND NOT prefix" rather than the plain "not a title" the
499 # rule is stated as, and the difference is not academic: `st`,
500 # `do` and `freiherr` are each BOTH a title and an ambiguous
501 # particle, so the plain test skipped over the very piece the
502 # exception exists to protect and "St John Smith" -- no title in
503 # front of it at all -- collapsed from title St, given John,
504 # family Smith into one given "St John Smith". A piece that
505 # could be the name's own first piece stops the scan; only a
506 # piece that can ONLY be a title is stepped over.
507 #
508 # Computed once, before the loop: every merge below starts at
509 # some k at or past this index, so no merge can move it.
510 #
511 # Suffix pieces are deliberately NOT skipped, and the reason is
512 # what skipping them WOULD do rather than what it would cost.
513 # (The "Ph. D. Van Johnson" example that opened this argument
514 # left it with #371: the pair no longer merges at the head of
515 # the input, so there is no suffix-shaped leading piece there
516 # to skip or not. "Dr. Ph. D. Van Johnson" is the replacement
517 # -- family 'Van Johnson' as shipped, family 'Johnson' with
518 # the skip.)
519 # The shapes that decide it are the ones whose leading piece
520 # lands in `given` instead: "Ph.D. Van Johnson", "II Van
521 # Johnson" and "Msc.Ed. Van Johnson" each read given
522 # 'Ph.D.'/'II'/'Msc.Ed.' with family 'Van Johnson', and
523 # skipping the piece moves `Van` out of the family and into the
524 # middle name (given 'Ph.D.', middle 'Van', family 'Johnson')
525 # -- a worse reading, on three shapes, to fix none. "Jr. Van
526 # Johnson", the shape that looks like it needs the skip,
527 # classifies its leading piece as a TITLE and is already
528 # covered here.
529 #
530 # A maiden marker the consumer took is already gone (the pass
531 # above), so the chain cannot carry a maiden name into the
532 # family the way "Ursula von der Leyen geb. Albrecht" once read
533 # family 'von der Leyen geb. Albrecht' (#399). A marker still
534 # here is one the consumer DECLINED -- nothing after it but a
535 # suffix, or nothing at all -- and M2 says that is just a word,
536 # so the chain takes it like any other: "Jane van der Berg née"
537 # reads family 'van der Berg née'. Stopping at it instead
538 # stranded it as a lone trailing piece that took the family
539 # field (#399's review), and a stop gated on "will the consumer
540 # take it" had to restate the consumer's condition and got it
541 # wrong one suffix later (#417).
542 #
543 # The `, 0` fallback is inert by construction rather than a
544 # default worth testing: it is reached only when every piece is
545 # a title and none is a prefix, and the loop below merges
546 # nothing unless some piece is a prefix.
547 # `title(k)` alone missed H2's unlisted abbreviations, which
548 # assign peels as titles all the same, so 'Xyz. van Johnson'
549 # chained where 'Dr. van Johnson' did not (#424 found it
550 # through the acronym fork: the chain had swallowed the given
551 # word and left assign two pieces where the fork counted
552 # three). The scan asks assign's own test.
553 leading = next((k for k in range(len(pieces))
554 if not is_leading_title(pieces[k], ptags[k],
555 tokens)
556 or prefix(k)), 0)
557 # rules.md#P2: "a trailing suffix begins" -- where it begins
558 # is read by assign's peel over the pieces as they stand
559 # (#424), once per segment and kept as a length from the end,
560 # which the chain's merges ahead of it do not move -- except
561 # where a particle that is suffix vocabulary too (vd, mc, do)
562 # starts the run: the prefix run below takes it as a particle,
563 # as P6 reads it after a comma, and 'John van Mc' keeps family
564 # 'van Mc' (every baseline's reading). A suffix WORD stops the
565 # chain wherever it stands, and the trailing
566 # run -- the numeral, or the bare acronym with words to spare
567 # -- stops it where the suffix-piece test alone did not ('John
568 # van der Berg V' read family 'van der Berg V'). The chain
569 # takes both forks, and asks again after its merges whether
570 # the acronym still has the pieces the fork counted (below).
571 name_start = leading_titles(pieces, ptags, tokens)
572 tail = len(pieces) - trailing_start(name_start, pieces, ptags,
573 tokens)
574 def chain(tail: int) -> None:
575 k = 0
576 while k < len(pieces):
577 if k == leading or not prefix(k):
578 k += 1
579 continue
580 j = k + 1
581 while j < len(pieces) and prefix(j):
582 j += 1
583 while (j < len(pieces) - tail and not prefix(j)
584 and not suffix(j)):
585 j += 1
586 # The other half of PARTICLE_OR_GIVEN. _assign reports the
587 # fork when an ambiguous particle stays a lone leading piece
588 # ("Van Johnson" -> given under the default order, family
589 # under FAMILY_FIRST); the chain here takes the opposite
590 # branch when the particle is not the name's leading piece.
591 # A fork whose two sides are decided in different stages
592 # needs an emitter in each.
593 #
594 # Narrow, and #367 is why. `all(is_leading_title(...))`
595 # says every piece ahead of this one is a title, and the
596 # loop skipped k == leading, so `leading` is STRICTLY
597 # before k -- and being before k it is one of those titles,
598 # while being `leading` it satisfies `not title or prefix`.
599 # For both, it must be a prefix as well: a word in both
600 # vocabularies (`st`, `do`, `freiherr` by default, or any
601 # overlap a caller configures). A plain title alone can no
602 # longer put a particle off the name's leading piece; it is
603 # stepped over and _assign reports the fork instead.
604 #
605 # What that leaves is wider than one shape: any number of
606 # plain title pieces, then a piece in BOTH vocabularies,
607 # then any number of further titles, then the ambiguous
608 # particle whose chain claims something. "Freiherr von
609 # Richthofen" is the canonical spelling and the one
610 # tests/v2/cases.py and tests/v2/test_parser.py lead with,
611 # but "St Van Johnson", "Do St Johnson" (the chained
612 # particle itself in both vocabularies) and "Dr. Do van
613 # Johnson" (a plain title AHEAD of the both-vocabulary
614 # word) all reach here too. What none of them can do is
615 # dispense with the both-vocabulary WORD. The conjunction
616 # merge is the only other way a piece acquires `title` or
617 # `prefix`, and it cannot manufacture the pair: it derives
618 # from ONE neighbor, which is the left one whenever there
619 # is a left one, and its right operands are always fresh
620 # pieces (the loop runs left to right, so nothing to the
621 # right has been merged yet). Both tags therefore have to
622 # come from the piece it extends, which bottoms out at a
623 # lone token in both vocabularies.
624 #
625 # j > k + 1 is what makes this a DECISION rather than a
626 # shape: when the next piece is a suffix the inner scan
627 # never advances, merge(k, k+1) folds a piece into itself,
628 # and the particle stays a lone leading piece -- nothing
629 # was chained, and _assign reports that case instead.
630 # Without this the two emitters both fire on the same token.
631 # (Tag test first: it is a set lookup and almost no name has
632 # an ambiguous particle, while title() is a call per piece.)
633 if (j > k + 1
634 and "vocab:particle-ambiguous"
635 in tokens[pieces[k][0]].tags
636 and all(is_leading_title(pieces[x], ptags[x],
637 tokens)
638 for x in range(k))):
639 i = pieces[k][0]
640 ambiguities.append(PendingAmbiguity(
641 AmbiguityKind.PARTICLE_OR_GIVEN,
642 f"{tokens[i].text!r} was chained onto the following "
643 f"name piece; it is also a given name in other "
644 f"names",
645 (i,)))
646 merge(k, j, drop={"prefix"})
647 k += 1
649 # The peel was read over the pieces as they stand, and the
650 # chain's own merges can change what it counts: behind a word
651 # in both the title and particle vocabularies the scan above
652 # stops where assign's title peel does not (P4, #367), so the
653 # chain takes the name's first word, and the acronym the fork
654 # counted with three pieces meets assign with two -- 'Freiherr
655 # von Berg Ma' read given 'von Berg', family 'Ma' (1.4.0's
656 # reading; the reviews found it behind the claim that the
657 # merges leave the count alone). So the peel is asked again
658 # over the pieces the chain leaves, and where it no longer
659 # takes what the chain stopped before, the chain runs again
660 # without that stop: what assign will not peel is a name word,
661 # and the chain takes it. The numeral cannot flip (a chain
662 # group is never initial-shaped), so the second run is the
663 # acronym's alone, and rare; the snapshot is one copy per
664 # segment with a trailing run, linear like the rest.
665 if tail:
666 kept = ([list(q) for q in pieces], [set(t) for t in ptags],
667 len(ambiguities))
668 chain(tail)
669 left = len(pieces) - trailing_start(
670 leading_titles(pieces, ptags, tokens), pieces, ptags,
671 tokens)
672 if left < tail:
673 pieces[:], ptags[:] = kept[0], kept[1]
674 del ambiguities[kept[2]:]
675 chain(left)
676 else:
677 chain(0)
678 # rules.md#P5: "a recognized bound given-name word joins the
679 # word after it into one given name" (history: decisions.md#P5)
680 # -- bound given names: the first non-title piece joins the next
681 # ONCE (pairwise, v1 parity: 'Salem, Abdul Rahman Ahmed' keeps
682 # Ahmed a middle name). BoundJoin encodes v1's reserve_last.
683 # "the first non-title piece" by assign's count (#424): group's
684 # title test does not see H2's unlisted abbreviations, and
685 # 'Xyz. abdul John Smith' joined nothing where 'Dr. abdul John
686 # Smith' read given 'abdul John'.
687 fk = leading_titles(pieces, ptags, tokens)
688 if (bound_join is not BoundJoin.DISABLED
689 and fk + 1 < len(pieces)
690 and len(pieces[fk]) == 1
691 and "vocab:bound-given" in tokens[pieces[fk][0]].tags):
692 # P5 joins the bound word to "the word after it", and a
693 # marker is not a name word -- it is the announcement that
694 # another name follows. The only marker left by now is one
695 # the consumer declined (nothing after it, or nothing but
696 # a suffix), and the join must still not take it: 'Berg,
697 # abdul nee PhD' read given 'abdul nee', and 'Berg, abdul
698 # nee' clears the LENIENT reserve the same way. Measured
699 # rather than assumed -- dropping this undid #411 on
700 # exactly that row. Nor is a suffix piece (#421) --
701 # rules.md#P5: "nor a word of the unambiguous suffix
702 # vocabulary (S2), wherever position will then place it"
703 # -- and declining it is also what keeps merge()'s tag
704 # union from making the joined piece a suffix piece.
705 if marker(fk + 1) or suffix(fk + 1):
706 pass
707 elif bound_join is BoundJoin.LENIENT:
708 # post-comma the family is fixed and the pair is the
709 # given whatever follows, so no peel is read
710 # (decisions.md#P5, #423)
711 merge(fk, fk + 2, drop={"title"})
712 else:
713 # rules.md#P5: "the join is tried on the pieces as it
714 # would leave them, and the same reading assign runs
715 # over them — its trailing peel (S2) and its trailing
716 # title run (H5), each read over what the other leaves
717 # until neither takes anything more — is read over that
718 # view, the name words it leaves being the words to
719 # spare"
720 # (history: decisions.md#P5). The view is what
721 # merge() builds -- the same slice assignment, the same
722 # joined_tags -- and the reading is assign's own, the
723 # ONE function that runs the peel and the H5 chain to
724 # their fixed point (_pieces.tail_reading), so the
725 # reserve and the assignment cannot drift. Modelling it
726 # here as a subtraction instead is what let them: 'abdul
727 # rahman MA' declined the join and 'abdul rahman MA
728 # Prof.' took it, where H5 says the title changes
729 # nothing (decisions.md#H5, 2026-09-09). And the join
730 # changes no suffix reading -- rules.md#P5: "a word the
731 # peel reads as a suffix unjoined must read so joined,
732 # or the join declines" -- compared as the peeled
733 # pieces themselves: 'abdul V' peels the V unjoined and
734 # nothing joined, 'abdul Smith Ma' peels the acronym
735 # unjoined and keeps it joined. Shapes pinned in
736 # test_group.py.
737 rest, chain_took, before = tail_reading(
738 peel_walk(fk, ptags), pieces, ptags, tokens)
739 view, view_tags = list(pieces), list(ptags)
740 view[fk:fk + 2] = [pieces[fk] + pieces[fk + 1]]
741 view_tags[fk:fk + 2] = [joined_tags(fk, fk + 2,
742 drop={"title"})]
743 view_rest, _, after = tail_reading(
744 peel_walk(fk, view_tags), view, view_tags, tokens)
745 same_suffixes = (
746 [tuple(view[j]) for j in view_rest[after.names:]]
747 == [tuple(pieces[j]) for j in rest[before.names:]])
748 # rules.md#P5: "a trailing roman numeral, or a bare
749 # acronym the peel takes, or a trailing title word the
750 # run takes, is no word to spare" -- and the join joins
751 # two NAME words, so a piece the chain takes is no more
752 # joinable than a marker or a suffix piece is: 'Sir
753 # abdul Prof.' reads title 'Sir Prof.', given 'abdul'.
754 # Read off the UNJOINED view, the one that still has
755 # the title as a piece of its own -- the join would
756 # swallow it, and a swallowed title is a title the
757 # joined view can no longer see. The suffix comparison
758 # alone said this while the counts were subtractions,
759 # by leaving the chained piece in the tail it compared;
760 # under the shared reading the chain takes it out of
761 # both views, so the rule is asked as the rule.
762 chained = fk + 1 in chain_took
763 # A given-name title ahead of the bound word asserts
764 # that a given name follows -- the assertion H1 reads
765 # when it keeps "Sir John" a given name -- so behind
766 # one there is no family to spare (#369). Asked of the
767 # title run through the ONE predicate post_rules asks
768 # for H1, so the two rules cannot disagree about what
769 # one run asserts; what it reads is the whole run's key
770 # or that key's LAST word (#489). And it is the same
771 # RUN on both sides: `range(fk)` is the pieces AHEAD of
772 # the bound word, and H1 asks its own question of the
773 # leading run too (_post_rules._addressing_run). They
774 # did disagree for one commit -- H1 keyed every TITLE
775 # token, so the trailing title in 'Sir abdul rahman
776 # Prof.' joined this run and flipped the join's own
777 # premise, handing the licensed pair to the family.
778 # Reading the leading run at both sites is what makes
779 # that unreachable rather than merely unlikely: a
780 # trailing title is behind the word, and neither site
781 # can see it. What H2's unlisted abbreviations do
782 # inside such a run is the predicate's own business,
783 # and its docstring is where they are worked through.
784 # The licence lifts the reserve for two name
785 # WORDS: the piece the join would take must be one word
786 # -- a particle chain is the family name P2 built ('Sir
787 # abdul van der Berg' keeps family 'van der Berg').
788 licensed = (fk > 0 and len(pieces[fk + 1]) == 1
789 and _run_addresses_by_given(
790 (tokens[i].text
791 for k in range(fk)
792 for i in pieces[k]),
793 given_name_titles))
794 reserve = BoundJoin.LENIENT if licensed else BoundJoin.STRICT
795 if (not chained and same_suffixes
796 and after.names >= reserve):
797 # the pair is a given name whatever tag the word
798 # carried (rules.md#P5); joined_tags says why the
799 # title tag is dropped. Pinned in test_group.py.
800 merge(fk, fk + 2, drop={"title"})
801 return pieces, ptags, taken
804def group(state: ParseState) -> ParseState:
805 tokens = list(state.tokens)
806 dropped = list(state.dropped)
807 ambiguities = list(state.ambiguities)
808 all_pieces: list[tuple[tuple[int, ...], ...]] = []
809 all_ptags: list[tuple[frozenset[str], ...]] = []
810 # v1 parity: additional_parts_count=1 applies only to FAMILY_COMMA
811 # parts; the SUFFIX_COMMA pre-comma segment gets 0.
812 additional = 1 if state.structure is Structure.FAMILY_COMMA else 0
813 # v1 expand_suffix_delimiter parity (#206): tail segments (wholly
814 # consumed as suffixes by assign) drop delimiter-core tokens, the
815 # same structural mechanism as the maiden marker (taken out in
816 # _group_segment, recorded in `dropped` just below)
817 cores = delimiter_cores(state.policy.extra_suffix_delimiters)
818 tail_start = {Structure.SUFFIX_COMMA: 1,
819 Structure.FAMILY_COMMA: 2}.get(state.structure)
820 family_comma = state.structure is Structure.FAMILY_COMMA
821 for seg_idx, seg in enumerate(state.segments):
822 if family_comma:
823 bound_join = (BoundJoin.LENIENT if seg_idx == 1
824 else BoundJoin.DISABLED)
825 else:
826 bound_join = BoundJoin.STRICT
827 # Suppressed after a family comma for the same reason _assign
828 # suppresses it there: the family name is already fixed, so
829 # there is no fork left to report.
830 tail = tail_start is not None and seg_idx >= tail_start
831 seg_cores = cores if tail else frozenset()
832 pieces, ptags, taken = _group_segment(
833 seg, additional, tokens, bound_join,
834 None if family_comma else ambiguities,
835 seg_cores,
836 state.lexicon.given_name_titles,
837 opens_the_name=(seg_idx == 0 and not family_comma))
838 # the marker is dropped and the maiden name's tokens become
839 # MAIDEN (#274); which pieces those are was settled in
840 # _group_segment, before the joins
841 if taken is not None:
842 marker_piece, maiden_pieces = taken
843 dropped.extend(marker_piece)
844 for piece in maiden_pieces:
845 for i in piece:
846 tokens[i] = dataclasses.replace(
847 tokens[i], role=Role.MAIDEN)
848 # rules.md#C1: "a part that is nothing but suffix words is the
849 # credential run and reads as suffixes, whole" -- WHOLE is this
850 # block's half of the rule, the routing being assign's.
851 #
852 # v1 expand_suffix_delimiter parity (#206): a delimiter core
853 # inside a segment separates suffix entries and is dropped, but
854 # a segment that IS only the core stays whole (v1 expand()
855 # splits within a part, never erases a lone part). Keyed on
856 # `tail` through `seg_cores`, which is empty off a tail
857 # segment, because the #206 parity is a TAIL rule.
858 #
859 # What this block decides is the #206 core DROP and nothing
860 # else: a delimiter core inside a tail segment leaves the
861 # pieces, and `dropped` is where that fact is recorded -- for
862 # the render, and for post_rules' entry pass, which reads it
863 # back as the one dropped token that separates two entries.
864 #
865 # It used to decide the ENTRY too, marking a continuation
866 # token "joined" between pieces off segment SHAPE -- `tail` by
867 # index, ORed since #429 with segment_suffix_reading's
868 # per-piece content verdict, gated per piece and sticky across
869 # an interleaved title. post_rules derives that from the
870 # commas the writer typed instead (#436/#437, rules.md#R1),
871 # which is what the input answers directly. The stickiness
872 # survives by construction rather than by code:
873 # 'Smith, MD Dr. PhD' has no comma between MD and PhD and a
874 # title between them renders elsewhere, so they join, while
875 # 'Smith Jr., Mr. Jr.' has the writer's own comma and they do
876 # not.
877 if seg_cores:
878 kept: list[int] = []
879 for k in range(len(pieces)):
880 is_core = (len(pieces[k]) == 1
881 and tokens[pieces[k][0]].text in seg_cores
882 and len(pieces) > 1)
883 if is_core:
884 dropped.extend(pieces[k])
885 continue
886 kept.append(k)
887 if len(kept) != len(pieces):
888 pieces = [pieces[k] for k in kept]
889 ptags = [ptags[k] for k in kept]
890 # continuation tokens of a suffix-merged piece (the ph-d merge)
891 # carry the stable "joined" tag: the suffix string view joins
892 # SUFFIX tokens with ", ", and the tag lets it heal the split
893 for piece, piece_tags_ in zip(pieces, ptags):
894 if "suffix" in piece_tags_ and len(piece) > 1:
895 for i in piece[1:]:
896 tokens[i] = dataclasses.replace(
897 tokens[i], tags=tokens[i].tags | {"joined"})
898 all_pieces.append(tuple(tuple(p) for p in pieces))
899 all_ptags.append(tuple(frozenset(t) for t in ptags))
900 # rules.md#M1: "a leading recognized marker being dropped where
901 # the clause holds a word past it; a clause of nothing but its
902 # marker keeps its words" — a marker inside EXTRACTED maiden
903 # content (#329).
904 # classify tags
905 # such a marker like any other token -- what the #274 rule above
906 # lacks is not the TAG but the token: extract claims a delimited
907 # clause and tokenize gives its tokens Role.MAIDEN up front, so
908 # segment (main stream = role is None) leaves them out of every
909 # segment, they never enter `pieces`, and a rule that walks pieces
910 # cannot reach them.
911 #
912 # Scoped to the CLAUSE, via state.extracted (one role + inner span
913 # per delimited region), rather than to a maiden token's
914 # neighbours. Both reasons are load-bearing:
915 # * Role.MAIDEN is not proof of extraction -- the #274 rule above
916 # sets it too, on the bare form, earlier in this same function.
917 # A neighbour test would fire there and eat the 'Nee' out of
918 # "Jane Smith nee Nee Jones". Keying on extracted spans puts
919 # the bare path out of reach by construction.
920 # * Separate clauses are separate content. In "(Nee) (Jones)" the
921 # two land as one contiguous run of maiden tokens, so only the
922 # clause bound keeps the lone "(Nee)" intact.
923 # Drop the clause's LEADING MARKER only when the clause holds a
924 # word past it: `Nee` is a real surname (Irish Ni/Nee, and a
925 # Chinese romanization), so a one-token "(Nee)" is a maiden name,
926 # not a marker. The marker and no more, whatever the clause holds
927 # past it: cases.py's maiden_marker_delimited_three_token_clause is
928 # the row that bounds this in both directions, every other
929 # delimited row having a two-token clause where the two readings
930 # agree. The marker is one token for a word entry and the whole run
931 # for a phrase one ('z domu'), which is why the loop below counts
932 # continuation tags rather than assuming one.
933 # Spans index the original string by the anti-#100
934 # invariant, and script_segment only ever splits a token into
935 # sub-slices, so containment stays exact.
936 #
937 # Bisect rather than scan the token list per clause: that is
938 # quadratic in the number of delimited pairs, and "(a) " * 3200 --
939 # 4x test_benchmark's base, NOT a doubling -- measured a 14.1x cost
940 # against the 4.1x the same shape holds under a policy with no
941 # maiden_delimiters. The control is what says which unit a ratio is
942 # in: linear is ~4 for 4x the input and ~2 for a doubling, so a 4.1x
943 # control cannot be per doubling. Re-measured 2026-08-03 at 11.2x
944 # against 4.2x (3.2x against 2.1x per doubling) -- the separation
945 # replicates, the exact ratio moves with the runner. Same idiom,
946 # and the same reason, as _extract._overlaps and _tokenize's origin
947 # resolution. test_benchmark's maiden_pairs shape is the guard.
948 if any(role is Role.MAIDEN for role, _ in state.extracted):
949 starts = [t.span.start for t in tokens]
950 for role, clause in state.extracted:
951 if role is not Role.MAIDEN:
952 continue
953 # first token starting at or after the clause opens; tokens
954 # are span-sorted and group never reorders or resizes them
955 first = bisect.bisect_left(starts, clause.start)
956 if (first >= len(tokens)
957 or "vocab:maiden-marker" not in tokens[first].tags):
958 continue
959 # How many tokens the marker is: one, or the whole run of a
960 # phrase entry, as classify recorded it. Same walk the
961 # piece test above makes, in token-index space.
962 run = marker_run_length(
963 tokens[k].tags for k in range(first + 1, len(tokens)))
964 # Testing the end of the token AFTER the run proves the run
965 # AND that token are all inside: tokens do not overlap and
966 # are index-ordered, so every earlier one ends no later,
967 # and bisect already put first.start at or after
968 # clause.start. That is also the "more than the marker"
969 # test, since the tokens inside a clause are contiguous in
970 # index order -- a clause holding nothing but its marker
971 # keeps its words, exactly as a one-token "(Nee)" does.
972 if (first + run < len(tokens)
973 and tokens[first + run].span.end <= clause.end):
974 dropped.extend(range(first, first + run))
975 return dataclasses.replace(
976 state, tokens=tuple(tokens), pieces=tuple(all_pieces),
977 piece_tags=tuple(all_ptags), dropped=tuple(dropped),
978 ambiguities=tuple(ambiguities))