← All repositories

crossmate

A collaborative crossword app for iPhone and iPad

git clone https://code.inqk.net/crossmate.git


Crossmate/Models/XD.swift (64173B)

1import Foundation
2
3/// Minimal `.xd` decoder. See https://github.com/century-arcade/xd for the
4/// full specification. Supports just enough of the format to parse our
5/// bundled puzzles: metadata, grid (with rebus), and across/down clues.
6struct XD: Sendable {
7    /// Version of the source→XD conversion (`NYTToXDConverter` /
8    /// `PUZToXDConverter`) that produced a persisted XD source. Written into the
9    /// `ConVer:` header and compared by `NYTPuzzleUpgrader` to decide whether an
10    /// owned NYT game should be re-fetched and re-converted. Only bumped when a
11    /// converter changes; puzzles generated in-house (Crossmake, bundled) carry
12    /// no converter version at all.
13    static let currentConverterVersion = 13
14
15    /// Version of the XD→Puzzle/Core Data processing (`XD.parse`, `Puzzle(xd:)`,
16    /// and the cached summary fields). Held on the game entity, never
17    /// serialized, and compared by `GameStore.preparePuzzleForLoad` to decide
18    /// whether a game must be reparsed and its cache refreshed. Bumped only when
19    /// that processing changes.
20    static let currentParserVersion = 11
21
22    /// Upper bound on a `.xd` source handed to `parse`. The largest puzzle we
23    /// ship is ~3 KB, so this is ~80× real content — no genuine puzzle is ever
24    /// rejected, but it caps parse cost and memory on an untrusted source (a
25    /// synced Game asset, an invite payload, an imported file). Does not replace
26    /// the algorithmic fix in `segment`; it bounds the general boundary cost.
27    static let maxSourceBytes = 262_144
28
29    /// Upper bound on a single clue's text. The longest real clue is under 100
30    /// characters. The overall source cap alone doesn't tame per-clue cost:
31    /// `XDMarkup.segments` rescans to end-of-string for every unclosed markup
32    /// span (O(n²) in one clue) and `parseCrossReferences` runs a backtracking
33    /// regex, so a single oversized clue under the source cap is still costly.
34    static let maxClueTextLength = 1_024
35
36    /// Upper bound on the grid's width and height, checked before any cell
37    /// storage is allocated. The byte cap alone admits a ~262,000-cell
38    /// single-row grid whose answer-application passes each walk the whole
39    /// row; the biggest genuine crossword we know of (NYT's annual Super Mega)
40    /// is 50×50, so 128 rejects nothing real while keeping every per-word pass
41    /// trivially small.
42    static let maxGridDimension = 128
43
44    /// Upper bound on distinct clues. A dense `maxGridDimension` grid tops out
45    /// around 5,000 words; real published puzzles stay under 800. Bounds the
46    /// per-clue answer-projection work that follows parsing.
47    static let maxClueCount = 8_192
48
49    /// Upper bound on one clue's combined alternative/`Accept` answers. Each
50    /// accepted answer is segmented against its whole word, so an unbounded
51    /// list is a work multiplier; genuine Schrödinger clues carry a handful.
52    static let maxAcceptedAnswersPerClue = 32
53
54    /// Upper bound on a single `Rebus:` expansion. Cell solutions feed the
55    /// joined-word strings that answer projection and accepted-answer
56    /// segmentation compare against, so one multi-kilobyte expansion inflates
57    /// every pass over its word. Real rebus fills are a word or two. An
58    /// over-long entry is dropped, so a grid that references it fails closed
59    /// with `unknownGridCharacter`.
60    static let maxRebusValueLength = 64
61
62    /// Upper bound on definition lines in the `## Decorations` section. Parsing is
63    /// linear in the source, which `maxSourceBytes` already bounds, so this
64    /// exists only to cap the per-character dictionary a malformed source can
65    /// grow. A design grid can reference at most `maxGridDimension²` distinct
66    /// characters, and real decorations use a few dozen.
67    static let maxDecorationDefinitions = 4_096
68
69    /// Single-character grid placeholders for multi-letter (rebus) fills, used
70    /// by every converter that *writes* `.xd`. The grid is one character per
71    /// cell, so a cell whose fill is longer than one letter shows one of these
72    /// and is expanded via the `Rebus:` header (the `1` in `1=LW`). The spec
73    /// allows "digits, most symbols, and printable unicode characters" here; we
74    /// take digits first (the conventional, readable encoding) then the ASCII
75    /// symbols, where "most" excludes the characters the grid/header parser
76    /// already reserves — letters (grid fill), `#`/`_`/`.` (block/empty),
77    /// `@`/`*` (`Specials:` markers), and `=`/space (`Rebus:` `key=value`
78    /// syntax, split on whitespace by `parseRebusHeader`). We stop at ASCII
79    /// rather than walking into unicode; real puzzles use a handful of distinct
80    /// fills, nowhere near the ceiling. (Walking ASCII naïvely from `'1'`
81    /// overflows into `=` by the 13th key, producing an unparseable `==VALUE`
82    /// entry and a rejected grid char.)
83    static let rebusPlaceholders: [Character] = {
84        let reserved: Set<Character> = ["#", "_", ".", "@", "*", "=", " "]
85        let symbols = (UInt8(33)...UInt8(126))
86            .map { Character(UnicodeScalar($0)) }
87            .filter { !$0.isLetter && !$0.isNumber && !reserved.contains($0) }
88        return Array("123456789") + symbols
89    }()
90
91    let title: String?
92    let publisher: String?
93    let author: String?
94    let copyright: String?
95    let date: Date?
96    let converterVersion: Int
97    let width: Int
98    let height: Int
99    let cells: [[Cell]]
100    let acrossClues: [Clue]
101    let downClues: [Clue]
102    let relatives: [[ClueRef]]
103    /// Per-cell decoration layers from the `## Decorations` section, in the order
104    /// their definition lines appeared — which is also the order they paint.
105    /// Empty for the (overwhelmingly common) source that has no such section.
106    let decorations: [GridPosition: [Decoration]]
107
108    /// A single clue identified by its number and direction. Used to describe
109    /// groups of mutually-related clues (a theme's revealer plus the answers
110    /// it references, or a simple "See 14-Across" pair).
111    struct ClueRef: Sendable, Hashable {
112        let number: Int
113        let direction: Puzzle.Direction
114    }
115
116    /// A single grid cell as it appears in the .xd source. Open cells carry
117    /// an optional solution string which may be 1+ characters long once any
118    /// `Rebus:` mapping has been applied, plus an optional per-cell special
119    /// marker.
120    enum Cell: Sendable, Equatable {
121        case block
122        case open(solution: String?, acceptedSolutions: Set<String>, special: Puzzle.Special?)
123    }
124
125    /// Decoration layers are format-independent, so they live on `Puzzle`
126    /// alongside `Special`; this alias keeps the parser's references short.
127    typealias Decoration = Puzzle.Decoration
128
129    struct Clue: Sendable, Equatable {
130        let number: Int
131        let text: String
132        let answer: String?
133        /// Alternative full-word answers from a slash-separated `~` field
134        /// (`~ CIGAR / PENIS`): the first reading becomes `answer`, the rest
135        /// are recorded here as Schrödinger alternatives.
136        let alternativeAnswers: [String]
137        let metadata: [String: [String]]
138
139        var acceptedAnswers: [String] {
140            alternativeAnswers + metadata["Accept", default: []].flatMap(Self.parseEscapedTokens)
141        }
142
143        private static func parseEscapedTokens(_ source: String) -> [String] {
144            var tokens: [String] = []
145            var current = ""
146            var escaping = false
147
148            for ch in source {
149                if escaping {
150                    current.append(ch)
151                    escaping = false
152                } else if ch == "\\" {
153                    escaping = true
154                } else if ch.isWhitespace {
155                    if !current.isEmpty {
156                        tokens.append(current)
157                        current = ""
158                    }
159                } else {
160                    current.append(ch)
161                }
162            }
163
164            if escaping {
165                current.append("\\")
166            }
167            if !current.isEmpty {
168                tokens.append(current)
169            }
170            return tokens
171        }
172    }
173
174    enum ParseError: Error, CustomStringConvertible {
175        case missingGrid
176        case missingClues
177        case raggedGrid
178        case sourceTooLarge
179        case gridTooLarge
180        case tooManyClues
181        case tooManyAcceptedAnswers(String)
182        case malformedClue(String)
183        case unknownGridCharacter(Character)
184        case unsupportedAnswerCharacter(Character)
185        case clueAnswerMismatch(String)
186        case ambiguousClueAnswer(String)
187        case missingInferredSolution(row: Int, col: Int)
188        case decorationGridMismatch(expected: String, found: String)
189        case unknownDecorationCharacter(Character)
190        case malformedDecoration(String)
191        case tooManyDecorations
192
193        var description: String {
194            switch self {
195            case .missingGrid:
196                return ".xd source has no grid section"
197            case .missingClues:
198                return ".xd source has no clues section"
199            case .raggedGrid:
200                return ".xd grid rows have inconsistent widths"
201            case .sourceTooLarge:
202                return ".xd source exceeds the maximum allowed size"
203            case .gridTooLarge:
204                return ".xd grid exceeds the maximum supported dimensions"
205            case .tooManyClues:
206                return ".xd source has more clues than the maximum supported"
207            case .tooManyAcceptedAnswers(let clue):
208                return ".xd clue has more accepted answers than the maximum supported: \(clue)"
209            case .malformedClue(let line):
210                return "malformed .xd clue: \(line)"
211            case .unknownGridCharacter(let ch):
212                return "unknown .xd grid character: \(ch)"
213            case .unsupportedAnswerCharacter(let ch):
214                return "unsupported non-ASCII answer character: \(ch)"
215            case .clueAnswerMismatch(let clue):
216                return ".xd clue answer does not match grid: \(clue)"
217            case .ambiguousClueAnswer(let clue):
218                return ".xd clue answer cannot be unambiguously projected onto grid: \(clue)"
219            case .missingInferredSolution(let row, let col):
220                return ".xd grid cell at row \(row + 1), column \(col + 1) has no inferred solution"
221            case .decorationGridMismatch(let expected, let found):
222                return ".xd decoration design grid is \(found), but the puzzle grid is \(expected)"
223            case .unknownDecorationCharacter(let ch):
224                return "unknown .xd decoration design character: \(ch)"
225            case .malformedDecoration(let line):
226                return "malformed .xd decoration definition: \(line)"
227            case .tooManyDecorations:
228                return ".xd has more decoration definitions than the maximum supported"
229            }
230        }
231
232        /// A non-technical sentence fragment for the user-facing alert, phrased
233        /// to follow "The puzzle for {date} …". The specifics that matter for a
234        /// bug report — the offending character, the malformed clue line, the
235        /// grid coordinates — stay out of this and ride in `description` to the
236        /// diagnostic log instead.
237        var userFacingReason: String {
238            switch self {
239            case .missingGrid:
240                return "is missing its grid"
241            case .missingClues:
242                return "is missing its clues"
243            case .raggedGrid:
244                return "has a grid Crossmate couldn't read"
245            case .sourceTooLarge:
246                return "is too large for Crossmate to open"
247            case .gridTooLarge:
248                return "has a grid too large for Crossmate to open"
249            case .tooManyClues:
250                return "has too many clues for Crossmate to open"
251            case .tooManyAcceptedAnswers:
252                return "has a clue with more alternative answers than Crossmate supports"
253            case .malformedClue:
254                return "has a clue Crossmate couldn't read"
255            case .unknownGridCharacter, .unsupportedAnswerCharacter:
256                return "contains a character Crossmate doesn't support"
257            case .clueAnswerMismatch:
258                return "has an answer that doesn't match its grid"
259            case .ambiguousClueAnswer:
260                return "has an answer Crossmate couldn't place in its grid"
261            case .missingInferredSolution:
262                return "has a square Crossmate couldn't solve"
263            case .decorationGridMismatch, .unknownDecorationCharacter, .malformedDecoration, .tooManyDecorations:
264                return "has decoration Crossmate couldn't read"
265            }
266        }
267    }
268
269    static func parse(_ source: String) throws -> XD {
270        guard source.utf8.count <= maxSourceBytes else {
271            throw ParseError.sourceTooLarge
272        }
273        let allSections = splitIntoSections(source)
274        // Named optional sections are lifted out first so they can appear in any
275        // order (or not at all) without disturbing the positional three that
276        // every `.xd` source has carried since v1.
277        let decorationsSection = allSections.first { isNamed($0, "Decorations") }
278        let sections = allSections.filter { !isNamed($0, "Decorations") }.map(\.lines)
279        guard sections.count >= 2 else { throw ParseError.missingGrid }
280        guard sections.count >= 3 else { throw ParseError.missingClues }
281
282        let metadata = parseMetadata(sections[0])
283        // `ConVer:` is the current token; `CmVer:` is the legacy name kept for
284        // sources persisted or synced before the rename (and older peers still
285        // emit it). Read the new token first, fall back to the old.
286        let converterVersion = parseConverterVersionHeader(
287            metadata.first("ConVer") ?? metadata.first("CmVer")
288        )
289        let rebus = parseRebusHeader(metadata.first("Rebus"))
290        let standardSpecial = parseStandardSpecialHeader(metadata.first("Special"))
291        let relatives = parseRelativesHeader(metadata.first("Relatives"))
292        let (rawCells, width, height) = try parseGrid(
293            sections[1],
294            rebus: rebus,
295            standardSpecial: standardSpecial,
296            specialsHeader: metadata.first("Specials")
297        )
298        let (across, down) = try parseClues(sections[2])
299        // Clue numbering is pure grid topology (block layout), which never
300        // changes once the grid is parsed — so compute it once here instead of
301        // re-deriving a cell's number with a full grid rescan inside the
302        // per-cell answer-application passes below (which made those passes
303        // O(cells²)).
304        let numbering = Numbering.build(rawCells)
305        let solvedCells = try applyClueAnswers(cells: rawCells, across: across, down: down, numbering: numbering)
306        let cells = applyAcceptedAnswers(cells: solvedCells, across: across, down: down, numbering: numbering)
307        try validateASCIIEntryOptions(cells: cells)
308        // Parsed last: the design grid is validated against the puzzle's own
309        // dimensions, which aren't known until the grid section is parsed.
310        let decorations = try parseDecorations(decorationsSection?.lines, width: width, height: height)
311
312        return XD(
313            title: metadata.first("Title"),
314            publisher: metadata.first("Publisher"),
315            author: metadata.first("Author"),
316            copyright: metadata.first("Copyright"),
317            date: parseDateHeader(metadata.first("Date")),
318            converterVersion: converterVersion,
319            width: width,
320            height: height,
321            cells: cells,
322            acrossClues: across,
323            downClues: down,
324            relatives: relatives,
325            decorations: decorations
326        )
327    }
328
329    private static func isNamed(_ section: Section, _ name: String) -> Bool {
330        section.name?.caseInsensitiveCompare(name) == .orderedSame
331    }
332
333    private static func validateASCIIEntryOptions(cells: [[Cell]]) throws {
334        for row in cells {
335            for cell in row {
336                guard case .open(let solution, let acceptedSolutions, _) = cell else { continue }
337                if let solution, isASCIIAnswer(solution) { continue }
338                if acceptedSolutions.contains(where: isASCIIAnswer) { continue }
339                if let solution, let ch = firstNonASCIICharacter(in: solution) {
340                    throw ParseError.unsupportedAnswerCharacter(ch)
341                }
342                for accepted in acceptedSolutions {
343                    if let ch = firstNonASCIICharacter(in: accepted) {
344                        throw ParseError.unsupportedAnswerCharacter(ch)
345                    }
346                }
347            }
348        }
349    }
350
351    private static func isASCIIAnswer(_ value: String) -> Bool {
352        !value.isEmpty && value.unicodeScalars.allSatisfy(\.isASCII)
353    }
354
355    private static func firstNonASCIICharacter(in value: String) -> Character? {
356        value.first { character in
357            character.unicodeScalars.contains { !$0.isASCII }
358        }
359    }
360
361    // MARK: - Sections
362
363    /// One top-level section of the source, with the `## Name` label that
364    /// introduced it (if any). The first three sections are still identified by
365    /// order — metadata, grid, clues — because the vast majority of `.xd`
366    /// sources carry no labels at all. Optional sections that arrive later
367    /// (`## Decorations`) are found by name instead, so their position can't matter
368    /// and an unrecognised label is simply skipped rather than shifting the
369    /// positional three.
370    private struct Section {
371        let name: String?
372        let lines: [String]
373    }
374
375    /// Splits the source into top-level sections. Per the .xd spec, sections
376    /// are delimited either by runs of two or more blank lines, or by
377    /// `## SectionName` header lines. We accept both: blank-line runs end the
378    /// current section, and a `##` line also ends the current section (the
379    /// header line is consumed, and its label attaches to the section that
380    /// *follows* it).
381    private static func splitIntoSections(_ source: String) -> [Section] {
382        let lines = source
383            .split(separator: "\n", omittingEmptySubsequences: false)
384            .map(String.init)
385
386        var sections: [Section] = []
387        var current: [String] = []
388        var currentName: String? = nil
389        var blankRun = 0
390
391        func flush() {
392            while current.last?.trimmingCharacters(in: .whitespaces).isEmpty == true {
393                current.removeLast()
394            }
395            while current.first?.trimmingCharacters(in: .whitespaces).isEmpty == true {
396                current.removeFirst()
397            }
398            if !current.isEmpty {
399                sections.append(Section(name: currentName, lines: current))
400            }
401            current = []
402            currentName = nil
403        }
404
405        for rawLine in lines {
406            let line = rawLine.trimmingCharacters(in: CharacterSet(charactersIn: "\r"))
407            let trimmed = line.trimmingCharacters(in: .whitespaces)
408
409            // The test is deliberately `"## "` (with the trailing space) or a
410            // bare `"##"`, never `hasPrefix("##")`: `#` is the block character,
411            // so an all-block grid row such as `###` would otherwise be
412            // mistaken for a section header and split the grid in two.
413            if trimmed.hasPrefix("## ") || trimmed == "##" {
414                flush()
415                let label = trimmed.dropFirst(2).trimmingCharacters(in: .whitespaces)
416                currentName = label.isEmpty ? nil : label
417                blankRun = 0
418                continue
419            }
420
421            if trimmed.isEmpty {
422                blankRun += 1
423                if blankRun >= 2 {
424                    flush()
425                }
426                continue
427            }
428
429            blankRun = 0
430            current.append(line)
431        }
432        flush()
433        return sections
434    }
435
436    // MARK: - Metadata
437
438    private struct Metadata {
439        var entries: [String: [String]] = [:]
440
441        func first(_ key: String) -> String? {
442            entries[key]?.first
443        }
444
445        func values(for key: String) -> [String] {
446            entries[key, default: []]
447        }
448    }
449
450    /// Reads a single metadata header value (e.g. `Date`, `Title`) from raw
451    /// `.xd` source without a full parse. Lets a caller name the puzzle that
452    /// failed to parse — the metadata section is independent of the grid/clue
453    /// sections that the parser rejects.
454    static func metadataValue(_ key: String, in source: String) -> String? {
455        guard let header = splitIntoSections(source).first else { return nil }
456        return parseMetadata(header.lines).first(key)
457    }
458
459    private static func parseMetadata(_ lines: [String]) -> Metadata {
460        var metadata = Metadata()
461        for line in lines {
462            guard let colon = line.firstIndex(of: ":") else { continue }
463            let key = line[..<colon].trimmingCharacters(in: .whitespaces)
464            let value = line[line.index(after: colon)...].trimmingCharacters(in: .whitespaces)
465            if !key.isEmpty {
466                metadata.entries[key, default: []].append(value)
467            }
468        }
469        return metadata
470    }
471
472    /// Parses a `Rebus:` header value such as `1=ONE 2=TWO 3=THREE` into a
473    /// map from grid placeholder character to its expanded solution string.
474    private static func parseRebusHeader(_ value: String?) -> [Character: String] {
475        guard let value, !value.isEmpty else { return [:] }
476        var map: [Character: String] = [:]
477        for entry in value.split(whereSeparator: { $0.isWhitespace }) {
478            guard let equals = entry.firstIndex(of: "=") else { continue }
479            let key = entry[..<equals]
480            let val = entry[entry.index(after: equals)...]
481            guard key.count == 1, let keyChar = key.first, !val.isEmpty,
482                  val.count <= maxRebusValueLength else { continue }
483            map[keyChar] = unescapeRebusValue(val)
484        }
485        return map
486    }
487
488    /// Reverses `NYTToXDConverter.escapeRebusValue`. A backslash introduces an
489    /// escape: `\\` is a literal backslash, and `\name` is a named escape whose
490    /// name is the following run of letters (currently just `\space` → a space,
491    /// which lets a gap cell's blank fill survive the whitespace-split header).
492    /// An unrecognised escape is preserved verbatim so an older parser never
493    /// silently drops a value a newer writer produced.
494    private static func unescapeRebusValue(_ value: Substring) -> String {
495        guard value.contains("\\") else { return String(value) }
496        var out = ""
497        var i = value.startIndex
498        while i < value.endIndex {
499            guard value[i] == "\\" else {
500                out.append(value[i])
501                i = value.index(after: i)
502                continue
503            }
504            let next = value.index(after: i)
505            guard next < value.endIndex else { out.append("\\"); break }
506            if value[next] == "\\" {
507                out.append("\\")
508                i = value.index(after: next)
509                continue
510            }
511            var j = next
512            while j < value.endIndex, value[j].isLetter { j = value.index(after: j) }
513            let name = value[next..<j]
514            switch name {
515            case "space": out.append(" ")
516            default: out.append("\\"); out.append(contentsOf: name)
517            }
518            i = j
519        }
520        return out
521    }
522
523    /// Parses a `Date:` header value as strict ISO `YYYY-MM-DD`. Returns
524    /// `nil` if the value is missing, empty, or in any other format.
525    private static func parseDateHeader(_ value: String?) -> Date? {
526        guard let value else { return nil }
527        let trimmed = value.trimmingCharacters(in: .whitespaces)
528        guard let match = trimmed.firstMatch(of: /^(\d{4})-(\d{2})-(\d{2})$/),
529              let year = Int(match.1),
530              let month = Int(match.2),
531              let day = Int(match.3)
532        else { return nil }
533        // Pin to America/New_York: puzzle dates are publication dates in NYT's
534        // timezone, and downstream fetchers (NYTPuzzleFetcher) format the Date
535        // back to a YYYY-MM-DD string in that zone. Without an explicit zone
536        // the system default fires here, which on a device east of NY yields a
537        // Date that formats back to the previous day — wrong puzzle.
538        var calendar = Calendar(identifier: .gregorian)
539        calendar.timeZone = TimeZone(identifier: "America/New_York") ?? .gmt
540        var comps = DateComponents()
541        comps.calendar = calendar
542        comps.timeZone = calendar.timeZone
543        comps.year = year
544        comps.month = month
545        comps.day = day
546        return calendar.date(from: comps)
547    }
548
549    /// Parses a Crossmate converter-version header (`ConVer:`, or the legacy
550    /// `CmVer:`). A missing or unconverted source is version 1, which keeps
551    /// generated puzzles (no header) and older fixtures identifiable as
552    /// non-current — harmless, since only owned NYT games act on this value.
553    private static func parseConverterVersionHeader(_ value: String?) -> Int {
554        guard let value else { return 1 }
555        let trimmed = value.trimmingCharacters(in: .whitespaces)
556        guard let version = Int(trimmed), version >= 1 else { return 1 }
557        return version
558    }
559
560    /// Returns `source` with its converter-version header set to `version`,
561    /// rewriting an existing `ConVer:`/`CmVer:` line in place, or inserting a
562    /// `ConVer:` line after the title if none is present. Only the metadata
563    /// block — the lines before the first blank line — is inspected, so the grid
564    /// and clues are never touched. Used by the upgrader to record that a
565    /// structurally-diverged NYT source has been evaluated at the current
566    /// converter version without disturbing the grid the player is solving.
567    static func settingConverterVersionHeader(in source: String, to version: Int) -> String {
568        var lines = source.components(separatedBy: "\n")
569        let newLine = "ConVer: \(version)"
570        for i in lines.indices {
571            let trimmed = lines[i].trimmingCharacters(in: .whitespaces)
572            if trimmed.isEmpty { break } // end of the metadata block
573            if trimmed.hasPrefix("ConVer:") || trimmed.hasPrefix("CmVer:") {
574                lines[i] = newLine
575                return lines.joined(separator: "\n")
576            }
577        }
578        // No existing header: insert after the first metadata line (the title).
579        lines.insert(newLine, at: lines.isEmpty ? 0 : 1)
580        return lines.joined(separator: "\n")
581    }
582
583    /// Parses a `Relatives:` header value into groups of cross-referenced
584    /// clues. Groups are separated by `;`, tokens within a group by `,`, and
585    /// each token is `{number}{A|D}` (e.g. `17A`, `57A`). This is a Crossmate
586    /// extension to `.xd`; unknown/invalid tokens are silently dropped.
587    /// Single-token groups are allowed so formatted NYT clues can mark their
588    /// own answer cells as thematic.
589    private static func parseRelativesHeader(_ value: String?) -> [[ClueRef]] {
590        guard let value, !value.isEmpty else { return [] }
591        var groups: [[ClueRef]] = []
592        for groupSlice in value.split(separator: ";") {
593            var refs: [ClueRef] = []
594            for tokenSlice in groupSlice.split(separator: ",") {
595                let token = tokenSlice.trimmingCharacters(in: .whitespaces)
596                guard let last = token.last else { continue }
597                let direction: Puzzle.Direction
598                switch last {
599                case "A", "a": direction = .across
600                case "D", "d": direction = .down
601                default: continue
602                }
603                guard let number = Int(token.dropLast()), number > 0 else { continue }
604                refs.append(ClueRef(number: number, direction: direction))
605            }
606            if !refs.isEmpty { groups.append(refs) }
607        }
608        return groups
609    }
610
611    private static func parseSpecialsHeader(_ value: String?) -> [Character: Puzzle.Special] {
612        guard let value, !value.isEmpty else { return [:] }
613        var specials: [Character: Puzzle.Special] = [:]
614        for assignment in value.split(whereSeparator: { $0.isWhitespace }) {
615            guard let equals = assignment.firstIndex(of: "=") else { continue }
616            let symbolPart = assignment[..<equals]
617            let kindPart = assignment[assignment.index(after: equals)...]
618            guard symbolPart.count == 1, let symbol = symbolPart.first else { continue }
619            let kind: Puzzle.Special
620            switch kindPart.lowercased() {
621            case "circle", "circled": kind = .circled
622            case "shaded": kind = .shaded
623            default: continue
624            }
625            specials[symbol] = kind
626        }
627        return specials
628    }
629
630    private static func parseStandardSpecialHeader(_ value: String?) -> Puzzle.Special? {
631        guard let value else { return nil }
632        switch value.trimmingCharacters(in: .whitespaces).lowercased() {
633        case "circle", "circled": return .circled
634        case "shaded": return .shaded
635        default: return nil
636        }
637    }
638
639    // MARK: - Grid
640
641    private static func parseGrid(
642        _ lines: [String],
643        rebus: [Character: String],
644        standardSpecial: Puzzle.Special?,
645        specialsHeader: String?
646    ) throws -> (cells: [[Cell]], width: Int, height: Int) {
647        var gridLines: [String] = []
648        var width: Int? = nil
649
650        for line in lines {
651            let trimmed = line.trimmingCharacters(in: .whitespaces)
652            if trimmed.isEmpty { continue }
653
654            // Both dimensions are bounded here, before any Cell storage is
655            // allocated: the source-byte cap alone still admits a single
656            // ~262,000-cell row (or column) that the answer-application
657            // passes would then walk per word.
658            guard trimmed.count <= maxGridDimension, gridLines.count < maxGridDimension else {
659                throw ParseError.gridTooLarge
660            }
661            if let w = width, trimmed.count != w {
662                throw ParseError.raggedGrid
663            }
664            width = trimmed.count
665            gridLines.append(trimmed)
666        }
667
668        guard let w = width, !gridLines.isEmpty else { throw ParseError.missingGrid }
669
670        let specialSymbols = parseSpecialsHeader(specialsHeader)
671        var rows: [[Cell]] = []
672        for line in gridLines {
673            var row: [Cell] = []
674            for ch in line {
675                row.append(try gridCell(
676                    for: ch,
677                    rebus: rebus,
678                    standardSpecial: standardSpecial,
679                    specialSymbols: specialSymbols
680                ))
681            }
682            rows.append(row)
683        }
684
685        return (rows, w, rows.count)
686    }
687
688    private static func gridCell(
689        for ch: Character,
690        rebus: [Character: String],
691        standardSpecial: Puzzle.Special?,
692        specialSymbols: [Character: Puzzle.Special]
693    ) throws -> Cell {
694        // Blocks: '#' is a normal block; '_' marks a non-existing cell on the
695        // edge of an irregularly-shaped grid. Both render as non-playable.
696        if ch == "#" || ch == "_" {
697            return .block
698        }
699        // '.' is an open cell with no known solution.
700        if ch == "." {
701            return .open(solution: nil, acceptedSolutions: [], special: nil)
702        }
703        let lowercaseSpecial = ch.isLetter && ch.isLowercase ? standardSpecial : nil
704        if let expansion = rebus[ch] {
705            return .open(
706                solution: expansion.uppercased(),
707                acceptedSolutions: [],
708                special: specialSymbols[ch] ?? lowercaseSpecial
709            )
710        }
711        if let special = specialSymbols[ch] {
712            return .open(solution: nil, acceptedSolutions: [], special: special)
713        }
714        if ch.isLetter {
715            return .open(solution: String(ch).uppercased(), acceptedSolutions: [], special: lowercaseSpecial)
716        }
717        throw ParseError.unknownGridCharacter(ch)
718    }
719
720    // MARK: - Decorations
721
722    /// Parses the optional `## Decorations` section: a design grid of the same
723    /// dimensions as the puzzle, plus `<char>. <kind>=<value> [before|after]`
724    /// definition lines.
725    ///
726    /// The two line kinds are told apart by whitespace — a definition line
727    /// always has some (at minimum the space after `<char>.`) and a design-grid
728    /// line never does — so the section reads correctly whichever order they
729    /// appear in, and the blank line between them is decorative.
730    private static func parseDecorations(
731        _ lines: [String]?,
732        width: Int,
733        height: Int
734    ) throws -> [GridPosition: [Decoration]] {
735        guard let lines, !lines.isEmpty else { return [:] }
736
737        var gridLines: [String] = []
738        var definitionLines: [String] = []
739        for line in lines {
740            let trimmed = line.trimmingCharacters(in: .whitespaces)
741            if trimmed.isEmpty { continue }
742            if trimmed.contains(where: \.isWhitespace) {
743                definitionLines.append(trimmed)
744            } else {
745                gridLines.append(trimmed)
746            }
747        }
748
749        guard definitionLines.count <= maxDecorationDefinitions else {
750            throw ParseError.tooManyDecorations
751        }
752
753        // A design grid that doesn't match the puzzle can't be interpreted at
754        // all — unlike a bad definition line, which costs only its own layer —
755        // so a mismatch fails the parse instead of being cropped or padded into
756        // a shape that would silently decorate the wrong squares.
757        guard gridLines.count == height, gridLines.allSatisfy({ $0.count == width }) else {
758            let found = gridLines.isEmpty
759                ? "empty"
760                : "\(gridLines.map(\.count).max() ?? 0)×\(gridLines.count)"
761            throw ParseError.decorationGridMismatch(expected: "\(width)×\(height)", found: found)
762        }
763
764        var definedCharacters: Set<Character> = []
765        var decorationsByCharacter: [Character: [Decoration]] = [:]
766        for line in definitionLines {
767            let (key, decoration) = try parseDecorationDefinition(line)
768            // The character counts as defined even when its kind isn't one we
769            // understand, so a source written against a newer spec revision
770            // still resolves its design grid instead of failing outright.
771            definedCharacters.insert(key)
772            if let decoration {
773                decorationsByCharacter[key, default: []].append(decoration)
774            }
775        }
776
777        var result: [GridPosition: [Decoration]] = [:]
778        for (row, line) in gridLines.enumerated() {
779            for (col, ch) in line.enumerated() {
780                if ch == "." { continue }
781                guard definedCharacters.contains(ch) else {
782                    throw ParseError.unknownDecorationCharacter(ch)
783                }
784                guard let layers = decorationsByCharacter[ch], !layers.isEmpty else { continue }
785                result[GridPosition(row: row, col: col)] = layers
786            }
787        }
788        return result
789    }
790
791    /// Parses one `<char>. <kind>=<value> [before|after]` line into the design
792    /// character it defines plus the layer it declares. Returns a `nil` layer
793    /// for a structurally sound line whose kind we don't recognise, so a single
794    /// unknown kind costs one layer rather than the whole section.
795    private static func parseDecorationDefinition(
796        _ line: String
797    ) throws -> (key: Character, decoration: Decoration?) {
798        guard let key = line.first,
799              let dot = line.firstIndex(of: "."),
800              line.distance(from: line.startIndex, to: dot) == 1 else {
801            throw ParseError.malformedDecoration(line)
802        }
803        var body = line[line.index(after: dot)...].trimmingCharacters(in: .whitespaces)
804        guard !body.isEmpty else { throw ParseError.malformedDecoration(line) }
805
806        // The phase keyword is stripped off the end rather than tokenised out of
807        // a whitespace split, so a value can itself contain spaces
808        // (`text=NEW YORK`) without needing an escape.
809        var phase = Decoration.Phase.before
810        for (keyword, candidate) in [("after", Decoration.Phase.after), ("before", Decoration.Phase.before)]
811        where body.hasSuffix(" " + keyword) {
812            phase = candidate
813            body = String(body.dropLast(keyword.count + 1)).trimmingCharacters(in: .whitespaces)
814            break
815        }
816
817        guard let equals = body.firstIndex(of: "=") else {
818            throw ParseError.malformedDecoration(line)
819        }
820        let kind = String(body[..<equals]).lowercased()
821        let value = String(body[body.index(after: equals)...])
822        guard !value.isEmpty else { throw ParseError.malformedDecoration(line) }
823
824        guard let content = decorationContent(kind: kind, value: value) else {
825            return (key, nil)
826        }
827        return (key, Decoration(content: content, phase: phase))
828    }
829
830    private static func decorationContent(kind: String, value: String) -> Decoration.Content? {
831        switch kind {
832        case "mark":
833            switch value.lowercased() {
834            case "circle", "circled": return .mark(.circled)
835            case "shaded": return .mark(.shaded)
836            default: return nil
837            }
838        case "bg": return decorationColor(layer: .background, value: value)
839        case "fg": return decorationColor(layer: .foreground, value: value)
840        case "text": return .text(value)
841        case "data": return decorationData(value)
842        default: return nil
843        }
844    }
845
846    /// Splits a `bg` / `fg` value into its appearance variants: a lone colour
847    /// applies to both, `<light>;<dark>` gives one for each. More than two parts
848    /// (or an empty one) is malformed and yields no layer rather than a guess at
849    /// which variant was meant.
850    private static func decorationColor(
851        layer: Decoration.ColorLayer,
852        value: String
853    ) -> Decoration.Content? {
854        let parts = value
855            .split(separator: ";", omittingEmptySubsequences: false)
856            .map { $0.trimmingCharacters(in: .whitespaces) }
857        guard (1...2).contains(parts.count), parts.allSatisfy({ !$0.isEmpty }) else {
858            return nil
859        }
860        return .color(layer: layer, light: parts[0], dark: parts.count == 2 ? parts[1] : nil)
861    }
862
863    /// Splits a `data` value's `<mime-type>[;<encoding>],<payload>` descriptor.
864    /// Base64's alphabet contains no comma, so splitting on the first one is
865    /// unambiguous however large the payload. An omitted encoding defaults to
866    /// base64, matching the data-URI convention the syntax borrows from.
867    private static func decorationData(_ value: String) -> Decoration.Content? {
868        guard let comma = value.firstIndex(of: ",") else { return nil }
869        let descriptor = value[..<comma]
870        let payload = String(value[value.index(after: comma)...])
871        guard !payload.isEmpty else { return nil }
872        let parts = descriptor.split(separator: ";", maxSplits: 1, omittingEmptySubsequences: false)
873        let mimeType = String(parts[0])
874        guard !mimeType.isEmpty else { return nil }
875        let encoding = parts.count > 1 && !parts[1].isEmpty ? String(parts[1]) : "base64"
876        return .data(mimeType: mimeType, encoding: encoding, payload: payload)
877    }
878
879    // MARK: - Clues
880
881    private static func parseClues(
882        _ lines: [String]
883    ) throws -> (across: [Clue], down: [Clue]) {
884        struct ClueKey: Hashable {
885            let number: Int
886            let direction: Character
887        }
888
889        var clueTexts: [ClueKey: String] = [:]
890        var clueAnswers: [ClueKey: String] = [:]
891        var clueAlternatives: [ClueKey: [String]] = [:]
892        var clueOrder: [ClueKey] = []
893        var metadataByClue: [ClueKey: [String: [String]]] = [:]
894
895        for rawLine in lines {
896            let line = rawLine.trimmingCharacters(in: .whitespaces)
897            if line.isEmpty { continue }
898
899            guard let leading = line.first, leading == "A" || leading == "D" else {
900                throw ParseError.malformedClue(line)
901            }
902
903            // The metadata-clue form is `A1 ^Format: value`; the `^` marker is
904            // what distinguishes it from an ordinary `A1. clue` line. Gate the
905            // regex on its presence so the common case (no `^`) skips the
906            // per-line match entirely — the pattern requires `\^` anyway, so a
907            // line without it can never match.
908            if line.contains("^"),
909               let match = line.firstMatch(of: /^([AD])(\d+)\s+\^([^:]+):\s*(.*)$/) {
910                guard let number = Int(match.2) else { throw ParseError.malformedClue(line) }
911                let key = ClueKey(number: number, direction: Character(String(match.1)))
912                let metadataKey = String(match.3).trimmingCharacters(in: .whitespaces)
913                guard !metadataKey.isEmpty else { throw ParseError.malformedClue(line) }
914                // Metadata values feed post-parse work (`Accept` values are
915                // segmented against their whole word), so they get the same
916                // length budget as clue text.
917                guard match.4.count <= maxClueTextLength else {
918                    throw ParseError.malformedClue(line)
919                }
920                metadataByClue[key, default: [:]][metadataKey, default: []].append(String(match.4))
921                continue
922            }
923
924            guard let dot = line.firstIndex(of: ".") else {
925                throw ParseError.malformedClue(line)
926            }
927
928            let numberSlice = line[line.index(after: line.startIndex)..<dot]
929            guard let number = Int(numberSlice) else {
930                throw ParseError.malformedClue(line)
931            }
932            let key = ClueKey(number: number, direction: leading)
933
934            var afterDot = line[line.index(after: dot)...]
935                .trimmingCharacters(in: .whitespaces)
936
937            if let tilde = afterDot.range(of: " ~ ", options: .backwards) {
938                // A slash-separated answer field (`~ CIGAR / PENIS`) declares a
939                // Schrödinger clue: the first reading is canonical, the rest are
940                // accepted alternatives. A plain field stays a single answer.
941                let readings = afterDot[tilde.upperBound...]
942                    .components(separatedBy: " / ")
943                    .map { $0.trimmingCharacters(in: .whitespaces) }
944                    .filter { !$0.isEmpty }
945                // Answers are segmented over their word cell-by-cell, so an
946                // unbounded reading is a work (and memo-table) multiplier.
947                guard readings.allSatisfy({ $0.count <= maxClueTextLength }) else {
948                    throw ParseError.malformedClue(line)
949                }
950                if let canonical = readings.first {
951                    clueAnswers[key] = canonical
952                    if readings.count > 1 {
953                        clueAlternatives[key] = Array(readings.dropFirst())
954                    }
955                }
956                afterDot = String(afterDot[..<tilde.lowerBound])
957                    .trimmingCharacters(in: .whitespaces)
958            }
959
960            guard afterDot.count <= maxClueTextLength else {
961                throw ParseError.malformedClue(line)
962            }
963
964            if clueTexts[key] == nil {
965                guard clueOrder.count < maxClueCount else {
966                    throw ParseError.tooManyClues
967                }
968                clueOrder.append(key)
969            }
970            clueTexts[key] = afterDot
971        }
972
973        var across: [Clue] = []
974        var down: [Clue] = []
975        for key in clueOrder {
976            let clue = Clue(
977                number: key.number,
978                text: clueTexts[key] ?? "",
979                answer: clueAnswers[key],
980                alternativeAnswers: clueAlternatives[key] ?? [],
981                metadata: metadataByClue[key] ?? [:]
982            )
983            guard clue.acceptedAnswers.count <= maxAcceptedAnswersPerClue else {
984                throw ParseError.tooManyAcceptedAnswers("\(key.direction)\(key.number)")
985            }
986            if key.direction == "A" {
987                across.append(clue)
988            } else {
989                down.append(clue)
990            }
991        }
992        return (across, down)
993    }
994
995    /// Applies exact-cell-answer projections and `Accept`/alternative answers.
996    /// Both passes are word-scoped: each maximal open run is visited once, its
997    /// clue resolved once, and its accepted answers segmented once. (The former
998    /// per-cell passes re-walked the containing word — and re-segmented every
999    /// accepted answer — from each of its cells, making a long open row
1000    /// quadratic before a game could be created.)
1001    private static func applyAcceptedAnswers(
1002        cells: [[Cell]],
1003        across: [Clue],
1004        down: [Clue],
1005        numbering: Numbering
1006    ) -> [[Cell]] {
1007        let acrossByNumber = Dictionary(uniqueKeysWithValues: across.map { ($0.number, $0) })
1008        let downByNumber = Dictionary(uniqueKeysWithValues: down.map { ($0.number, $0) })
1009
1010        var outsideExactCellAnswers: Set<Position> = []
1011        var acceptedByPosition: [Position: Set<String>] = [:]
1012        for direction in [Direction.across, .down] {
1013            let cluesByNumber = direction == .across ? acrossByNumber : downByNumber
1014            for word in openWords(direction: direction, cells: cells) {
1015                guard let first = word.first,
1016                      let number = numbering.number(atRow: first.row, col: first.col),
1017                      let clue = cluesByNumber[number]
1018                else { continue }
1019                collectPositionsOutsideExactCellAnswer(
1020                    word: word,
1021                    clue: clue,
1022                    cells: cells,
1023                    into: &outsideExactCellAnswers
1024                )
1025                collectAcceptedCellValues(
1026                    word: word,
1027                    clue: clue,
1028                    cells: cells,
1029                    into: &acceptedByPosition
1030                )
1031            }
1032        }
1033
1034        var result = cells
1035        for r in result.indices {
1036            for c in result[r].indices {
1037                guard case .open(let solution, let acceptedSolutions, let special) = result[r][c] else { continue }
1038                let position = Position(row: r, col: c)
1039                let effectiveSolution = outsideExactCellAnswers.contains(position) ? nil : solution
1040                var merged = acceptedSolutions
1041                if let accepted = acceptedByPosition[position] {
1042                    merged.formUnion(accepted)
1043                }
1044                if effectiveSolution != solution || merged != acceptedSolutions {
1045                    result[r][c] = .open(solution: effectiveSolution, acceptedSolutions: merged, special: special)
1046                }
1047            }
1048        }
1049        return result
1050    }
1051
1052    private static func applyClueAnswers(
1053        cells: [[Cell]],
1054        across: [Clue],
1055        down: [Clue],
1056        numbering: Numbering
1057    ) throws -> [[Cell]] {
1058        var cells = cells
1059        for clue in across {
1060            try applyClueAnswer(clue, direction: .across, cells: &cells, numbering: numbering)
1061        }
1062        for clue in down {
1063            try applyClueAnswer(clue, direction: .down, cells: &cells, numbering: numbering)
1064        }
1065
1066        for r in cells.indices {
1067            for c in cells[r].indices {
1068                if case .open(nil, _, _) = cells[r][c] {
1069                    throw ParseError.missingInferredSolution(row: r, col: c)
1070                }
1071            }
1072        }
1073        return cells
1074    }
1075
1076    private static func applyClueAnswer(
1077        _ clue: Clue,
1078        direction: Direction,
1079        cells: inout [[Cell]],
1080        numbering: Numbering
1081    ) throws {
1082        guard let answer = clue.answer,
1083              let word = wordCells(forClueNumber: clue.number, direction: direction, cells: cells, numbering: numbering)
1084        else { return }
1085        guard wordNeedsAnswerProjection(word, cells: cells) else { return }
1086
1087        let clueID = "\(direction == .across ? "A" : "D")\(clue.number)"
1088        let segmentations = segment(answer: answer, over: word, cells: cells, maxResults: 2)
1089        guard !segmentations.isEmpty else {
1090            throw ParseError.clueAnswerMismatch(clueID)
1091        }
1092        guard segmentations.count == 1, let segments = segmentations.first else {
1093            throw ParseError.ambiguousClueAnswer(clueID)
1094        }
1095
1096        for (position, segment) in zip(word, segments) {
1097            guard case .open(let solution, let acceptedSolutions, let special) = cells[position.row][position.col] else { continue }
1098            let normalizedSegment = normalizedAnswer(segment)
1099            if let solution {
1100                guard normalizedAnswer(solution) == normalizedSegment else {
1101                    throw ParseError.clueAnswerMismatch(clueID)
1102                }
1103            } else {
1104                cells[position.row][position.col] = .open(
1105                    solution: normalizedSegment,
1106                    acceptedSolutions: acceptedSolutions,
1107                    special: special
1108                )
1109            }
1110        }
1111    }
1112
1113    private static func wordNeedsAnswerProjection(
1114        _ word: [(row: Int, col: Int)],
1115        cells: [[Cell]]
1116    ) -> Bool {
1117        word.contains { position in
1118            guard case .open(let solution, _, let special) = cells[position.row][position.col] else {
1119                return false
1120            }
1121            return solution == nil || special != nil
1122        }
1123    }
1124
1125    private static func segment(
1126        answer: String,
1127        over word: [(row: Int, col: Int)],
1128        cells: [[Cell]],
1129        maxResults: Int
1130    ) -> [[String]] {
1131        let chars = Array(answer)
1132
1133        // The set of valid segmentations of the answer suffix from a given
1134        // `(cellIndex, answerIndex)` state is independent of how that state was
1135        // reached, so we memoize it. Without this, a crafted answer that admits
1136        // no valid segmentation over many free cells walks the entire
1137        // C(answer-1, cells-1) composition tree — a sub-1KB puzzle can drive
1138        // minutes-to-hours of work on the main actor during invite accept.
1139        // Memoizing collapses that to an O(word × answer) word-break DP.
1140        var memo: [Int: [[String]]] = [:]
1141
1142        func solve(cellIndex: Int, answerIndex: Int) -> [[String]] {
1143            if cellIndex == word.count {
1144                return answerIndex == chars.count ? [[]] : []
1145            }
1146            guard answerIndex < chars.count else { return [] }
1147
1148            let key = cellIndex * (chars.count + 1) + answerIndex
1149            if let cached = memo[key] { return cached }
1150
1151            let position = word[cellIndex]
1152            guard case .open(let solution, _, _) = cells[position.row][position.col] else {
1153                memo[key] = []
1154                return []
1155            }
1156            let remainingCells = word.count - cellIndex - 1
1157
1158            var results: [[String]] = []
1159            // Prepend `segment` to every valid completion of the remaining
1160            // cells, capped at `maxResults`. Each subproblem is itself capped at
1161            // `maxResults`, which is sufficient because the caller never needs
1162            // more than that many total.
1163            func extend(length: Int) {
1164                let endIndex = answerIndex + length
1165                guard endIndex <= chars.count else { return }
1166                let segment = String(chars[answerIndex..<endIndex])
1167                for suffix in solve(cellIndex: cellIndex + 1, answerIndex: endIndex) {
1168                    results.append([segment] + suffix)
1169                    if results.count >= maxResults { break }
1170                }
1171            }
1172
1173            if let solution {
1174                let solutionLength = Array(solution).count
1175                let endIndex = answerIndex + solutionLength
1176                if endIndex <= chars.count,
1177                   normalizedAnswer(String(chars[answerIndex..<endIndex])) == normalizedAnswer(solution) {
1178                    extend(length: solutionLength)
1179                }
1180            } else {
1181                let maxLength = chars.count - answerIndex - remainingCells
1182                if maxLength >= 1 {
1183                    for length in 1...maxLength {
1184                        extend(length: length)
1185                        if results.count >= maxResults { break }
1186                    }
1187                }
1188            }
1189
1190            memo[key] = results
1191            return results
1192        }
1193
1194        return solve(cellIndex: 0, answerIndex: 0)
1195    }
1196
1197    private struct Position: Hashable {
1198        let row: Int
1199        let col: Int
1200    }
1201
1202    /// Enumerates every maximal run of open cells in the given direction,
1203    /// including single-cell runs (which can still carry a crossing clue's
1204    /// number). Each cell belongs to exactly one run per direction, so
1205    /// iterating runs covers the grid linearly.
1206    private static func openWords(direction: Direction, cells: [[Cell]]) -> [[Position]] {
1207        let delta = direction.delta
1208        var words: [[Position]] = []
1209        for r in cells.indices {
1210            for c in cells[r].indices {
1211                guard isOpen(cells, r, c), !isOpen(cells, r - delta.row, c - delta.col) else { continue }
1212                var word: [Position] = []
1213                var row = r
1214                var col = c
1215                while isOpen(cells, row, col) {
1216                    word.append(Position(row: row, col: col))
1217                    row += delta.row
1218                    col += delta.col
1219                }
1220                words.append(word)
1221            }
1222        }
1223        return words
1224    }
1225
1226    /// The exact-cell-answer projection: when a multi-cell word's clue answer
1227    /// matches exactly one cell's inferred solution, every other cell of that
1228    /// word loses its inferred solution (the answer lives wholly in that cell).
1229    private static func collectPositionsOutsideExactCellAnswer(
1230        word: [Position],
1231        clue: Clue,
1232        cells: [[Cell]],
1233        into positions: inout Set<Position>
1234    ) {
1235        guard word.count > 1, let answer = clue.answer else { return }
1236        let solutions = word.compactMap { solution(atRow: $0.row, col: $0.col, cells: cells) }
1237        guard solutions.count == word.count else { return }
1238
1239        let normalized = normalizedAnswer(answer)
1240        if normalized == normalizedAnswer(solutions.joined()) { return }
1241
1242        let matchingIndices = solutions.indices.filter { normalized == normalizedAnswer(solutions[$0]) }
1243        guard matchingIndices.count == 1, let matchingIndex = matchingIndices.first else { return }
1244
1245        for index in word.indices where index != matchingIndex {
1246            positions.insert(word[index])
1247        }
1248    }
1249
1250    /// Distributes a clue's accepted answers onto the cells of its word: a
1251    /// single-cell word (or a cell holding the entire answer) accepts each
1252    /// alternative whole; otherwise each alternative is segmented against the
1253    /// word's canonical solutions and only the differing cell values are kept.
1254    private static func collectAcceptedCellValues(
1255        word: [Position],
1256        clue: Clue,
1257        cells: [[Cell]],
1258        into accepted: inout [Position: Set<String>]
1259    ) {
1260        let acceptedAnswers = clue.acceptedAnswers
1261        guard !acceptedAnswers.isEmpty else { return }
1262
1263        if word.count == 1, let position = word.first {
1264            accepted[position, default: []].formUnion(acceptedAnswers)
1265            return
1266        }
1267
1268        let solutions = word.map { solution(atRow: $0.row, col: $0.col, cells: cells) }
1269        let complete = solutions.compactMap { $0 }
1270
1271        var segmentations: [[String]] = []
1272        if complete.count == word.count,
1273           (clue.answer ?? complete.joined()) == complete.joined() {
1274            for acceptedAnswer in acceptedAnswers {
1275                if let segments = segmentAcceptedAnswer(acceptedAnswer, canonicalSegments: complete) {
1276                    segmentations.append(segments)
1277                }
1278            }
1279        }
1280
1281        for (index, position) in word.enumerated() {
1282            if let solution = solutions[index], let answer = clue.answer,
1283               normalizedAnswer(answer) == normalizedAnswer(solution) {
1284                accepted[position, default: []].formUnion(acceptedAnswers)
1285                continue
1286            }
1287            for segments in segmentations
1288            where segments.indices.contains(index) && segments[index] != complete[index] {
1289                accepted[position, default: []].insert(segments[index])
1290            }
1291        }
1292    }
1293
1294    private static func solution(atRow row: Int, col: Int, cells: [[Cell]]) -> String? {
1295        guard case .open(let solution?, _, _) = cells[row][col] else { return nil }
1296        return solution
1297    }
1298
1299    private static func normalizedAnswer(_ value: String) -> String {
1300        value.precomposedStringWithCanonicalMapping.uppercased()
1301    }
1302
1303    private static func segmentAcceptedAnswer(
1304        _ acceptedAnswer: String,
1305        canonicalSegments: [String]
1306    ) -> [String]? {
1307        let accepted = Array(acceptedAnswer)
1308        let canonical = canonicalSegments.map(Array.init)
1309
1310        // Equal-length alternative: mirror the canonical cell segmentation
1311        // exactly. This covers whole-word Schrödinger answers where several
1312        // cells differ at once (e.g. CIGAR / PENIS over single-letter cells),
1313        // which the single-replacement search below cannot align.
1314        let canonicalLength = canonical.reduce(0) { $0 + $1.count }
1315        if accepted.count == canonicalLength {
1316            var segments: [String] = []
1317            var offset = 0
1318            var differs = false
1319            for cell in canonical {
1320                let slice = accepted[offset..<offset + cell.count]
1321                if !slice.elementsEqual(cell) { differs = true }
1322                segments.append(String(slice))
1323                offset += cell.count
1324            }
1325            return differs ? segments : nil
1326        }
1327
1328        for replacedIndex in canonical.indices {
1329            let prefixLength = canonical[..<replacedIndex].reduce(0) { $0 + $1.count }
1330            let suffixLength = canonical[canonical.index(after: replacedIndex)...].reduce(0) { $0 + $1.count }
1331            guard accepted.count >= prefixLength + suffixLength else { continue }
1332
1333            let prefix = canonical[..<replacedIndex].flatMap { $0 }
1334            let suffix = canonical[canonical.index(after: replacedIndex)...].flatMap { $0 }
1335            guard accepted.prefix(prefix.count).elementsEqual(prefix) else { continue }
1336            guard accepted.suffix(suffix.count).elementsEqual(suffix) else { continue }
1337
1338            let replacementEnd = accepted.count - suffixLength
1339            let replacement = Array(accepted[prefixLength..<replacementEnd])
1340            guard !replacement.isEmpty, replacement != canonical[replacedIndex] else { continue }
1341
1342            var segments = canonical.map { String($0) }
1343            segments[replacedIndex] = String(replacement)
1344            return segments
1345        }
1346
1347        return nil
1348    }
1349
1350    private enum Direction: Hashable {
1351        case across
1352        case down
1353
1354        var delta: (row: Int, col: Int) {
1355            switch self {
1356            case .across: return (0, 1)
1357            case .down: return (1, 0)
1358            }
1359        }
1360    }
1361
1362    private static func wordCells(
1363        forClueNumber number: Int,
1364        direction: Direction,
1365        cells: [[Cell]],
1366        numbering: Numbering
1367    ) -> [(row: Int, col: Int)]? {
1368        guard let start = numbering.start(forNumber: number) else { return nil }
1369        switch direction {
1370        case .across where start.startsAcross:
1371            return wordCells(fromRow: start.row, col: start.col, direction: direction, cells: cells)
1372        case .down where start.startsDown:
1373            return wordCells(fromRow: start.row, col: start.col, direction: direction, cells: cells)
1374        default:
1375            return nil
1376        }
1377    }
1378
1379    private static func wordCells(
1380        fromRow row: Int,
1381        col: Int,
1382        direction: Direction,
1383        cells: [[Cell]]
1384    ) -> [(row: Int, col: Int)] {
1385        guard !isBlock(cells, row, col) else { return [] }
1386        let delta = direction.delta
1387        var startRow = row
1388        var startCol = col
1389        while isOpen(cells, startRow - delta.row, startCol - delta.col) {
1390            startRow -= delta.row
1391            startCol -= delta.col
1392        }
1393
1394        var result: [(row: Int, col: Int)] = []
1395        var r = startRow
1396        var c = startCol
1397        while isOpen(cells, r, c) {
1398            result.append((r, c))
1399            r += delta.row
1400            c += delta.col
1401        }
1402        return result
1403    }
1404
1405    /// Precomputed clue numbering for one grid. Built once per parse from the
1406    /// block topology, then queried in O(1) by the answer-application passes —
1407    /// replacing the former per-cell full-grid rescans that made those passes
1408    /// O(cells²). The counter walk here mirrors the .xd numbering convention:
1409    /// row-major, incrementing at every cell that starts an across or down word.
1410    private struct Numbering {
1411        /// Start cell → its clue number.
1412        private let numberByPosition: [Position: Int]
1413        /// Clue number → its start cell and which directions it opens.
1414        private let startByNumber: [Int: (row: Int, col: Int, startsAcross: Bool, startsDown: Bool)]
1415
1416        static func build(_ cells: [[Cell]]) -> Numbering {
1417            var numberByPosition: [Position: Int] = [:]
1418            var startByNumber: [Int: (row: Int, col: Int, startsAcross: Bool, startsDown: Bool)] = [:]
1419            var counter = 1
1420            for r in cells.indices {
1421                for c in cells[r].indices {
1422                    guard isOpen(cells, r, c) else { continue }
1423                    let startsAcross = !isOpen(cells, r, c - 1) && isOpen(cells, r, c + 1)
1424                    let startsDown = !isOpen(cells, r - 1, c) && isOpen(cells, r + 1, c)
1425                    guard startsAcross || startsDown else { continue }
1426                    numberByPosition[Position(row: r, col: c)] = counter
1427                    startByNumber[counter] = (r, c, startsAcross, startsDown)
1428                    counter += 1
1429                }
1430            }
1431            return Numbering(numberByPosition: numberByPosition, startByNumber: startByNumber)
1432        }
1433
1434        func number(atRow row: Int, col: Int) -> Int? {
1435            numberByPosition[Position(row: row, col: col)]
1436        }
1437
1438        func start(forNumber number: Int) -> (row: Int, col: Int, startsAcross: Bool, startsDown: Bool)? {
1439            startByNumber[number]
1440        }
1441    }
1442
1443    private static func isOpen(_ cells: [[Cell]], _ row: Int, _ col: Int) -> Bool {
1444        guard row >= 0, row < cells.count, col >= 0, col < cells[row].count else { return false }
1445        return !isBlock(cells, row, col)
1446    }
1447
1448    private static func isBlock(_ cells: [[Cell]], _ row: Int, _ col: Int) -> Bool {
1449        guard row >= 0, row < cells.count, col >= 0, col < cells[row].count else { return true }
1450        if case .block = cells[row][col] { return true }
1451        return false
1452    }
1453}