commit 4e33d976f1909c8d92d1f17bee6225eb4b313ee0
parent 40abf3b3ae1abf5d457deeaaeab188201f6c5ac5
Author: Michael Camilleri <[email protected]>
Date: Sun, 12 Jul 2026 00:30:10 +0900
Bound untrusted XD parsing work before allocation
The source-byte cap alone still admitted quadratic main-actor work from
a syntactically valid puzzle: a single all-open row of a couple hundred
thousand cells made the answer-application passes re-walk the whole word
from every cell, and hundreds of malformed clues packed with
unterminated markup openers each rescanned to end-of-clue on every
render. Because parsing runs during imported-game creation and invite
acceptance, a hostile shared puzzle could freeze the accept or open flow
for minutes.
This commit enforces conservative budgets before any grid or clue
storage is allocated: grid width and height (128 — 2.5× the largest
published crossword), distinct clues (8,192), and accepted answers per
clue (32), with clue metadata values, answer readings, and rebus
expansions now sharing length caps so no single field can inflate the
segmentation work that follows. Violations fail closed with the new
gridTooLarge, tooManyClues and tooManyAcceptedAnswers parse errors,
each carrying a user-facing reason like the existing cases.
The answer-application passes are now word-scoped: each maximal open run
is enumerated once, its clue resolved once, and its accepted answers
segmented once, instead of re-deriving all of that from every cell of
the word. Accepted values are read from the pristine parsed grid rather
than the half-mutated array the old per-cell loop saw, so the cells of
one word are treated consistently. XDMarkup marks a delimiter whose
close-scan reaches the end of the clue as exhausted and never rescans
it, keeping markup linear with unchanged output. currentParserVersion
moves to 9 so existing games reparse and refresh their caches on next
load.
Co-Authored-By: Claude Fable 5 <[email protected]>
Diffstat:
5 files changed, 509 insertions(+), 142 deletions(-)
diff --git a/Crossmate.xcodeproj/project.pbxproj b/Crossmate.xcodeproj/project.pbxproj
@@ -71,6 +71,7 @@
449B0A09A36B276C93CFB9A4 /* GameStoreUnreadMovesTests.swift in Sources */ = {isa = PBXBuildFile; fileRef = 31C534911020BE4ED2E5065D /* GameStoreUnreadMovesTests.swift */; };
44FF4A5334A4086DEA7D8A7B /* GameShareItem.swift in Sources */ = {isa = PBXBuildFile; fileRef = 663934F0B7CA8BDD462DFAA4 /* GameShareItem.swift */; };
47584CBEF819C2F507D06DFF /* PlayerColor.swift in Sources */ = {isa = PBXBuildFile; fileRef = DB55FC337CF72C650373210A /* PlayerColor.swift */; };
+ 47B4FB563BA4A8A54E2C26E0 /* XDLimitsTests.swift in Sources */ = {isa = PBXBuildFile; fileRef = 9F6DB4116933BB66274AC6E8 /* XDLimitsTests.swift */; };
4819D7FBB407C9D76510EA2A /* TestHelpers.swift in Sources */ = {isa = PBXBuildFile; fileRef = F97B399E89BBB37730F2F1E9 /* TestHelpers.swift */; };
4A89595E3F6AB50E1D9E6BA8 /* ImportService.swift in Sources */ = {isa = PBXBuildFile; fileRef = 462CE0FD356F6137C9BFD30F /* ImportService.swift */; };
4B8CA45845618D75A3313816 /* GridSilhouette.swift in Sources */ = {isa = PBXBuildFile; fileRef = D16AC7215D0269195FEA8BA8 /* GridSilhouette.swift */; };
@@ -412,6 +413,7 @@
9AF6157D97271205626E207C /* MovesUpdaterTests.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = MovesUpdaterTests.swift; sourceTree = "<group>"; };
9B3E0C62CBF5ADF7C01C1D54 /* EngagementMessageAuthenticator.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = EngagementMessageAuthenticator.swift; sourceTree = "<group>"; };
9F13534332699C80382FE682 /* CellPatterns.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = CellPatterns.swift; sourceTree = "<group>"; };
+ 9F6DB4116933BB66274AC6E8 /* XDLimitsTests.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = XDLimitsTests.swift; sourceTree = "<group>"; };
9F8D856707B4D76FDBF4AE69 /* FriendEntity+DisplayName.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = "FriendEntity+DisplayName.swift"; sourceTree = "<group>"; };
A24FD313982C8094CD020106 /* EngagementMessageAuthenticatorTests.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = EngagementMessageAuthenticatorTests.swift; sourceTree = "<group>"; };
A253416F4FEA271A80B22A73 /* NYTAuthService.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = NYTAuthService.swift; sourceTree = "<group>"; };
@@ -635,6 +637,7 @@
C7F35A7BFE52279BC24677F5 /* TimeLogTests.swift */,
C8D6991C1EBAB2C64D9DF669 /* TipStoreTests.swift */,
4F4EBC0F07FF815274C028CA /* XDAcceptTests.swift */,
+ 9F6DB4116933BB66274AC6E8 /* XDLimitsTests.swift */,
F9FE0A9624DB87758F3D1768 /* XDMarkupTests.swift */,
ABB371EF2574E95782CB05FD /* Sync */,
);
@@ -1101,6 +1104,7 @@
F15591B48E4155CB19C1F084 /* TimeLogTests.swift in Sources */,
9AD5700398B1C1F29A3A75F6 /* TipStoreTests.swift in Sources */,
31F2B6A61ED352C7D800149F /* XDAcceptTests.swift in Sources */,
+ 47B4FB563BA4A8A54E2C26E0 /* XDLimitsTests.swift in Sources */,
786813F3418C32EFBF296220 /* XDMarkupTests.swift in Sources */,
9582AA583F5EA008FFC82B64 /* ZoneOrphaningTests.swift in Sources */,
);
diff --git a/Crossmate/Models/XD.swift b/Crossmate/Models/XD.swift
@@ -17,7 +17,7 @@ struct XD: Sendable {
/// serialized, and compared by `GameStore.preparePuzzleForLoad` to decide
/// whether a game must be reparsed and its cache refreshed. Bumped only when
/// that processing changes.
- static let currentParserVersion = 8
+ static let currentParserVersion = 9
/// Upper bound on a `.xd` source handed to `parse`. The largest puzzle we
/// ship is ~3 KB, so this is ~80× real content — no genuine puzzle is ever
@@ -33,6 +33,32 @@ struct XD: Sendable {
/// regex, so a single oversized clue under the source cap is still costly.
static let maxClueTextLength = 1_024
+ /// Upper bound on the grid's width and height, checked before any cell
+ /// storage is allocated. The byte cap alone admits a ~262,000-cell
+ /// single-row grid whose answer-application passes each walk the whole
+ /// row; the biggest genuine crossword we know of (NYT's annual Super Mega)
+ /// is 50×50, so 128 rejects nothing real while keeping every per-word pass
+ /// trivially small.
+ static let maxGridDimension = 128
+
+ /// Upper bound on distinct clues. A dense `maxGridDimension` grid tops out
+ /// around 5,000 words; real published puzzles stay under 800. Bounds the
+ /// per-clue answer-projection work that follows parsing.
+ static let maxClueCount = 8_192
+
+ /// Upper bound on one clue's combined alternative/`Accept` answers. Each
+ /// accepted answer is segmented against its whole word, so an unbounded
+ /// list is a work multiplier; genuine Schrödinger clues carry a handful.
+ static let maxAcceptedAnswersPerClue = 32
+
+ /// Upper bound on a single `Rebus:` expansion. Cell solutions feed the
+ /// joined-word strings that answer projection and accepted-answer
+ /// segmentation compare against, so one multi-kilobyte expansion inflates
+ /// every pass over its word. Real rebus fills are a word or two. An
+ /// over-long entry is dropped, so a grid that references it fails closed
+ /// with `unknownGridCharacter`.
+ static let maxRebusValueLength = 64
+
/// Single-character grid placeholders for multi-letter (rebus) fills, used
/// by every converter that *writes* `.xd`. The grid is one character per
/// cell, so a cell whose fill is longer than one letter shows one of these
@@ -135,6 +161,9 @@ struct XD: Sendable {
case missingClues
case raggedGrid
case sourceTooLarge
+ case gridTooLarge
+ case tooManyClues
+ case tooManyAcceptedAnswers(String)
case malformedClue(String)
case unknownGridCharacter(Character)
case unsupportedAnswerCharacter(Character)
@@ -152,6 +181,12 @@ struct XD: Sendable {
return ".xd grid rows have inconsistent widths"
case .sourceTooLarge:
return ".xd source exceeds the maximum allowed size"
+ case .gridTooLarge:
+ return ".xd grid exceeds the maximum supported dimensions"
+ case .tooManyClues:
+ return ".xd source has more clues than the maximum supported"
+ case .tooManyAcceptedAnswers(let clue):
+ return ".xd clue has more accepted answers than the maximum supported: \(clue)"
case .malformedClue(let line):
return "malformed .xd clue: \(line)"
case .unknownGridCharacter(let ch):
@@ -182,6 +217,12 @@ struct XD: Sendable {
return "has a grid Crossmate couldn't read"
case .sourceTooLarge:
return "is too large for Crossmate to open"
+ case .gridTooLarge:
+ return "has a grid too large for Crossmate to open"
+ case .tooManyClues:
+ return "has too many clues for Crossmate to open"
+ case .tooManyAcceptedAnswers:
+ return "has a clue with more alternative answers than Crossmate supports"
case .malformedClue:
return "has a clue Crossmate couldn't read"
case .unknownGridCharacter, .unsupportedAnswerCharacter:
@@ -375,7 +416,8 @@ struct XD: Sendable {
guard let equals = entry.firstIndex(of: "=") else { continue }
let key = entry[..<equals]
let val = entry[entry.index(after: equals)...]
- guard key.count == 1, let keyChar = key.first, !val.isEmpty else { continue }
+ guard key.count == 1, let keyChar = key.first, !val.isEmpty,
+ val.count <= maxRebusValueLength else { continue }
map[keyChar] = unescapeRebusValue(val)
}
return map
@@ -547,6 +589,13 @@ struct XD: Sendable {
let trimmed = line.trimmingCharacters(in: .whitespaces)
if trimmed.isEmpty { continue }
+ // Both dimensions are bounded here, before any Cell storage is
+ // allocated: the source-byte cap alone still admits a single
+ // ~262,000-cell row (or column) that the answer-application
+ // passes would then walk per word.
+ guard trimmed.count <= maxGridDimension, gridLines.count < maxGridDimension else {
+ throw ParseError.gridTooLarge
+ }
if let w = width, trimmed.count != w {
throw ParseError.raggedGrid
}
@@ -637,6 +686,12 @@ struct XD: Sendable {
let key = ClueKey(number: number, direction: Character(String(match.1)))
let metadataKey = String(match.3).trimmingCharacters(in: .whitespaces)
guard !metadataKey.isEmpty else { throw ParseError.malformedClue(line) }
+ // Metadata values feed post-parse work (`Accept` values are
+ // segmented against their whole word), so they get the same
+ // length budget as clue text.
+ guard match.4.count <= maxClueTextLength else {
+ throw ParseError.malformedClue(line)
+ }
metadataByClue[key, default: [:]][metadataKey, default: []].append(String(match.4))
continue
}
@@ -662,6 +717,11 @@ struct XD: Sendable {
.components(separatedBy: " / ")
.map { $0.trimmingCharacters(in: .whitespaces) }
.filter { !$0.isEmpty }
+ // Answers are segmented over their word cell-by-cell, so an
+ // unbounded reading is a work (and memo-table) multiplier.
+ guard readings.allSatisfy({ $0.count <= maxClueTextLength }) else {
+ throw ParseError.malformedClue(line)
+ }
if let canonical = readings.first {
clueAnswers[key] = canonical
if readings.count > 1 {
@@ -677,6 +737,9 @@ struct XD: Sendable {
}
if clueTexts[key] == nil {
+ guard clueOrder.count < maxClueCount else {
+ throw ParseError.tooManyClues
+ }
clueOrder.append(key)
}
clueTexts[key] = afterDot
@@ -692,6 +755,9 @@ struct XD: Sendable {
alternativeAnswers: clueAlternatives[key] ?? [],
metadata: metadataByClue[key] ?? [:]
)
+ guard clue.acceptedAnswers.count <= maxAcceptedAnswersPerClue else {
+ throw ParseError.tooManyAcceptedAnswers("\(key.direction)\(key.number)")
+ }
if key.direction == "A" {
across.append(clue)
} else {
@@ -701,55 +767,61 @@ struct XD: Sendable {
return (across, down)
}
+ /// Applies exact-cell-answer projections and `Accept`/alternative answers.
+ /// Both passes are word-scoped: each maximal open run is visited once, its
+ /// clue resolved once, and its accepted answers segmented once. (The former
+ /// per-cell passes re-walked the containing word — and re-segmented every
+ /// accepted answer — from each of its cells, making a long open row
+ /// quadratic before a game could be created.)
private static func applyAcceptedAnswers(
cells: [[Cell]],
across: [Clue],
down: [Clue],
numbering: Numbering
) -> [[Cell]] {
- var cells = cells
let acrossByNumber = Dictionary(uniqueKeysWithValues: across.map { ($0.number, $0) })
let downByNumber = Dictionary(uniqueKeysWithValues: down.map { ($0.number, $0) })
- let positionsOutsideExactCellAnswers = positionsOutsideExactCellAnswers(
- cells: cells,
- across: acrossByNumber,
- down: downByNumber,
- numbering: numbering
- )
- for r in cells.indices {
- for c in cells[r].indices {
- guard case .open(let solution, let acceptedSolutions, let special) = cells[r][c] else { continue }
- let position = Position(row: r, col: c)
- let effectiveSolution = positionsOutsideExactCellAnswers.contains(position) ? nil : solution
- var merged = acceptedSolutions
- if let accepted = acceptedCellValues(
- atRow: r,
- col: c,
- direction: .across,
+ var outsideExactCellAnswers: Set<Position> = []
+ var acceptedByPosition: [Position: Set<String>] = [:]
+ for direction in [Direction.across, .down] {
+ let cluesByNumber = direction == .across ? acrossByNumber : downByNumber
+ for word in openWords(direction: direction, cells: cells) {
+ guard let first = word.first,
+ let number = numbering.number(atRow: first.row, col: first.col),
+ let clue = cluesByNumber[number]
+ else { continue }
+ collectPositionsOutsideExactCellAnswer(
+ word: word,
+ clue: clue,
cells: cells,
- cluesByNumber: acrossByNumber,
- numbering: numbering
- ) {
- merged.formUnion(accepted)
- }
- if let accepted = acceptedCellValues(
- atRow: r,
- col: c,
- direction: .down,
+ into: &outsideExactCellAnswers
+ )
+ collectAcceptedCellValues(
+ word: word,
+ clue: clue,
cells: cells,
- cluesByNumber: downByNumber,
- numbering: numbering
- ) {
+ into: &acceptedByPosition
+ )
+ }
+ }
+
+ var result = cells
+ for r in result.indices {
+ for c in result[r].indices {
+ guard case .open(let solution, let acceptedSolutions, let special) = result[r][c] else { continue }
+ let position = Position(row: r, col: c)
+ let effectiveSolution = outsideExactCellAnswers.contains(position) ? nil : solution
+ var merged = acceptedSolutions
+ if let accepted = acceptedByPosition[position] {
merged.formUnion(accepted)
}
if effectiveSolution != solution || merged != acceptedSolutions {
- cells[r][c] = .open(solution: effectiveSolution, acceptedSolutions: merged, special: special)
+ result[r][c] = .open(solution: effectiveSolution, acceptedSolutions: merged, special: special)
}
}
}
-
- return cells
+ return result
}
private static func applyClueAnswers(
@@ -902,127 +974,96 @@ struct XD: Sendable {
let col: Int
}
- private static func positionsOutsideExactCellAnswers(
- cells: [[Cell]],
- across: [Int: Clue],
- down: [Int: Clue],
- numbering: Numbering
- ) -> Set<Position> {
- var positions: Set<Position> = []
- var seenWords: Set<WordKey> = []
+ /// Enumerates every maximal run of open cells in the given direction,
+ /// including single-cell runs (which can still carry a crossing clue's
+ /// number). Each cell belongs to exactly one run per direction, so
+ /// iterating runs covers the grid linearly.
+ private static func openWords(direction: Direction, cells: [[Cell]]) -> [[Position]] {
+ let delta = direction.delta
+ var words: [[Position]] = []
for r in cells.indices {
for c in cells[r].indices {
- positions.formUnion(
- positionsOutsideExactCellAnswer(
- fromRow: r,
- col: c,
- direction: .across,
- cells: cells,
- cluesByNumber: across,
- seenWords: &seenWords,
- numbering: numbering
- )
- )
- positions.formUnion(
- positionsOutsideExactCellAnswer(
- fromRow: r,
- col: c,
- direction: .down,
- cells: cells,
- cluesByNumber: down,
- seenWords: &seenWords,
- numbering: numbering
- )
- )
+ guard isOpen(cells, r, c), !isOpen(cells, r - delta.row, c - delta.col) else { continue }
+ var word: [Position] = []
+ var row = r
+ var col = c
+ while isOpen(cells, row, col) {
+ word.append(Position(row: row, col: col))
+ row += delta.row
+ col += delta.col
+ }
+ words.append(word)
}
}
- return positions
- }
-
- private struct WordKey: Hashable {
- let direction: Direction
- let row: Int
- let col: Int
+ return words
}
- private static func positionsOutsideExactCellAnswer(
- fromRow row: Int,
- col: Int,
- direction: Direction,
+ /// The exact-cell-answer projection: when a multi-cell word's clue answer
+ /// matches exactly one cell's inferred solution, every other cell of that
+ /// word loses its inferred solution (the answer lives wholly in that cell).
+ private static func collectPositionsOutsideExactCellAnswer(
+ word: [Position],
+ clue: Clue,
cells: [[Cell]],
- cluesByNumber: [Int: Clue],
- seenWords: inout Set<WordKey>,
- numbering: Numbering
- ) -> Set<Position> {
- let word = wordCells(fromRow: row, col: col, direction: direction, cells: cells)
- guard let first = word.first else { return [] }
- let key = WordKey(direction: direction, row: first.row, col: first.col)
- guard seenWords.insert(key).inserted,
- word.count > 1,
- let number = clueNumber(forWord: word, numbering: numbering),
- let clue = cluesByNumber[number]
- else { return [] }
-
- guard let answer = clue.answer else { return [] }
- let solutions = word.compactMap { position -> String? in
- guard case .open(let solution?, _, _) = cells[position.row][position.col] else { return nil }
- return solution
- }
- guard solutions.count == word.count else { return [] }
+ into positions: inout Set<Position>
+ ) {
+ guard word.count > 1, let answer = clue.answer else { return }
+ let solutions = word.compactMap { solution(atRow: $0.row, col: $0.col, cells: cells) }
+ guard solutions.count == word.count else { return }
- if normalizedAnswer(answer) == normalizedAnswer(solutions.joined()) {
- return []
- }
+ let normalized = normalizedAnswer(answer)
+ if normalized == normalizedAnswer(solutions.joined()) { return }
- let matchingIndices = solutions.indices.filter { normalizedAnswer(answer) == normalizedAnswer(solutions[$0]) }
- guard matchingIndices.count == 1, let matchingIndex = matchingIndices.first else { return [] }
+ let matchingIndices = solutions.indices.filter { normalized == normalizedAnswer(solutions[$0]) }
+ guard matchingIndices.count == 1, let matchingIndex = matchingIndices.first else { return }
- return Set(word.indices.compactMap { index in
- index == matchingIndex ? nil : Position(row: word[index].row, col: word[index].col)
- })
+ for index in word.indices where index != matchingIndex {
+ positions.insert(word[index])
+ }
}
- private static func acceptedCellValues(
- atRow row: Int,
- col: Int,
- direction: Direction,
+ /// Distributes a clue's accepted answers onto the cells of its word: a
+ /// single-cell word (or a cell holding the entire answer) accepts each
+ /// alternative whole; otherwise each alternative is segmented against the
+ /// word's canonical solutions and only the differing cell values are kept.
+ private static func collectAcceptedCellValues(
+ word: [Position],
+ clue: Clue,
cells: [[Cell]],
- cluesByNumber: [Int: Clue],
- numbering: Numbering
- ) -> Set<String>? {
- let word = wordCells(fromRow: row, col: col, direction: direction, cells: cells)
- guard let wordIndex = word.firstIndex(where: { $0.row == row && $0.col == col }) else { return nil }
- guard let number = clueNumber(forWord: word, numbering: numbering),
- let clue = cluesByNumber[number],
- !clue.acceptedAnswers.isEmpty else { return nil }
-
- if let solution = solution(atRow: row, col: col, cells: cells),
- let answer = clue.answer,
- normalizedAnswer(answer) == normalizedAnswer(solution) {
- return Set(clue.acceptedAnswers)
+ into accepted: inout [Position: Set<String>]
+ ) {
+ let acceptedAnswers = clue.acceptedAnswers
+ guard !acceptedAnswers.isEmpty else { return }
+
+ if word.count == 1, let position = word.first {
+ accepted[position, default: []].formUnion(acceptedAnswers)
+ return
}
- if word.count == 1 {
- return Set(clue.acceptedAnswers)
- }
+ let solutions = word.map { solution(atRow: $0.row, col: $0.col, cells: cells) }
+ let complete = solutions.compactMap { $0 }
- let solutions = word.compactMap { position -> String? in
- guard case .open(let solution?, _, _) = cells[position.row][position.col] else { return nil }
- return solution
+ var segmentations: [[String]] = []
+ if complete.count == word.count,
+ (clue.answer ?? complete.joined()) == complete.joined() {
+ for acceptedAnswer in acceptedAnswers {
+ if let segments = segmentAcceptedAnswer(acceptedAnswer, canonicalSegments: complete) {
+ segmentations.append(segments)
+ }
+ }
}
- guard solutions.count == word.count else { return nil }
- let canonicalAnswer = clue.answer ?? solutions.joined()
- guard canonicalAnswer == solutions.joined() else { return nil }
-
- var accepted: Set<String> = []
- for acceptedAnswer in clue.acceptedAnswers {
- guard let segments = segmentAcceptedAnswer(acceptedAnswer, canonicalSegments: solutions),
- segments.indices.contains(wordIndex),
- segments[wordIndex] != solutions[wordIndex] else { continue }
- accepted.insert(segments[wordIndex])
+ for (index, position) in word.enumerated() {
+ if let solution = solutions[index], let answer = clue.answer,
+ normalizedAnswer(answer) == normalizedAnswer(solution) {
+ accepted[position, default: []].formUnion(acceptedAnswers)
+ continue
+ }
+ for segments in segmentations
+ where segments.indices.contains(index) && segments[index] != complete[index] {
+ accepted[position, default: []].insert(segments[index])
+ }
}
- return accepted
}
private static func solution(atRow row: Int, col: Int, cells: [[Cell]]) -> String? {
@@ -1110,11 +1151,6 @@ struct XD: Sendable {
}
}
- private static func clueNumber(forWord word: [(row: Int, col: Int)], numbering: Numbering) -> Int? {
- guard let first = word.first else { return nil }
- return numbering.number(atRow: first.row, col: first.col)
- }
-
private static func wordCells(
fromRow row: Int,
col: Int,
diff --git a/Crossmate/Models/XDMarkup.swift b/Crossmate/Models/XDMarkup.swift
@@ -63,8 +63,15 @@ enum XDMarkup {
var segments: [Segment] = []
var plain = ""
var i = 0
+ // Markers whose close-scan already reached the end of the source: no
+ // later opener of that marker can close either, so skip its scan.
+ // Without this, every unterminated opener rescans to the end — a clue
+ // packed with `{/` openers costs O(n²), and hundreds of such clues in
+ // one hostile puzzle add up to real main-actor stalls.
+ var exhaustedMarkers: Set<Character> = []
while i < chars.count {
- if chars[i] == "{", i + 1 < chars.count, let style = style(for: chars[i + 1]) {
+ if chars[i] == "{", i + 1 < chars.count, let style = style(for: chars[i + 1]),
+ !exhaustedMarkers.contains(chars[i + 1]) {
let marker = chars[i + 1]
if let close = closingIndex(chars, after: i + 2, marker: marker) {
if !plain.isEmpty {
@@ -75,6 +82,7 @@ enum XDMarkup {
i = close + 2
continue
}
+ exhaustedMarkers.insert(marker)
}
plain.append(chars[i])
i += 1
diff --git a/Tests/Unit/XDLimitsTests.swift b/Tests/Unit/XDLimitsTests.swift
@@ -0,0 +1,290 @@
+import Foundation
+import Testing
+
+@testable import Crossmate
+
+/// Adversarial boundary coverage for the parser's pre-allocation budgets:
+/// grid geometry, clue count, per-clue text/metadata/answer lengths, accepted
+/// answers, and rebus expansions. Each limit is tested from both sides — the
+/// hostile case fails closed, the maximum legitimate case still parses.
+@Suite("XD parsing limits")
+struct XDLimitsTests {
+
+ /// Parses the source, returning the ParseError it threw (nil on success
+ /// or on a non-ParseError failure).
+ private func parseError(from source: String) -> XD.ParseError? {
+ do {
+ _ = try XD.parse(source)
+ return nil
+ } catch let error as XD.ParseError {
+ return error
+ } catch {
+ return nil
+ }
+ }
+
+ // MARK: - Grid geometry
+
+ @Test("A grid wider than the maximum is rejected before allocation")
+ func gridWiderThanMaximumIsRejected() {
+ let row = String(repeating: "A", count: XD.maxGridDimension + 1)
+ let source = """
+ Title: Wide
+
+
+ \(row)
+
+
+ A1. Never reached
+ """
+
+ guard case .some(.gridTooLarge) = parseError(from: source) else {
+ Issue.record("expected gridTooLarge")
+ return
+ }
+ }
+
+ @Test("A grid taller than the maximum is rejected before allocation")
+ func gridTallerThanMaximumIsRejected() {
+ let rows = Array(repeating: "A", count: XD.maxGridDimension + 1).joined(separator: "\n")
+ let source = """
+ Title: Tall
+
+
+ \(rows)
+
+
+ D1. Never reached
+ """
+
+ guard case .some(.gridTooLarge) = parseError(from: source) else {
+ Issue.record("expected gridTooLarge")
+ return
+ }
+ }
+
+ @Test("A grid at the maximum width still parses")
+ func gridAtMaximumWidthParses() throws {
+ let row = String(repeating: "A", count: XD.maxGridDimension)
+ let source = """
+ Title: Widest
+
+
+ \(row)
+
+
+ A1. All As
+ """
+
+ let xd = try XD.parse(source)
+ #expect(xd.width == XD.maxGridDimension)
+ #expect(xd.height == 1)
+ }
+
+ @Test("A grid at the maximum height still parses")
+ func gridAtMaximumHeightParses() throws {
+ let rows = Array(repeating: "A", count: XD.maxGridDimension).joined(separator: "\n")
+ let source = """
+ Title: Tallest
+
+
+ \(rows)
+
+
+ D1. All As
+ """
+
+ let xd = try XD.parse(source)
+ #expect(xd.width == 1)
+ #expect(xd.height == XD.maxGridDimension)
+ }
+
+ @Test("A maximum-width all-open row with an answer-less clue fails closed")
+ func answerlessOpenRowFailsClosed() {
+ // The audit's quadratic shape: one long open row whose only clue has
+ // no answer. The word-scoped passes visit the row once and the missing
+ // inferred solutions reject it promptly.
+ let row = String(repeating: ".", count: XD.maxGridDimension)
+ let source = """
+ Title: Open Row
+
+
+ \(row)
+
+
+ A1. No answer given
+ """
+
+ guard case .some(.missingInferredSolution) = parseError(from: source) else {
+ Issue.record("expected missingInferredSolution")
+ return
+ }
+ }
+
+ // MARK: - Clue budgets
+
+ @Test("More distinct clues than the maximum are rejected")
+ func tooManyDistinctCluesAreRejected() {
+ let clues = (1...(XD.maxClueCount + 1))
+ .map { "A\($0). x" }
+ .joined(separator: "\n")
+ let source = """
+ Title: Cluepocalypse
+
+
+ A
+
+
+ \(clues)
+ """
+
+ guard case .some(.tooManyClues) = parseError(from: source) else {
+ Issue.record("expected tooManyClues")
+ return
+ }
+ }
+
+ @Test("A clue count at the maximum still parses")
+ func clueCountAtMaximumParses() throws {
+ let clues = (1...XD.maxClueCount)
+ .map { "A\($0). x" }
+ .joined(separator: "\n")
+ let source = """
+ Title: Many Clues
+
+
+ A
+
+
+ \(clues)
+ """
+
+ let xd = try XD.parse(source)
+ #expect(xd.acrossClues.count == XD.maxClueCount)
+ }
+
+ @Test("An over-long clue metadata value is rejected")
+ func overLongClueMetadataValueIsRejected() {
+ let value = String(repeating: "x", count: XD.maxClueTextLength + 1)
+ let source = """
+ Title: Long Metadata
+
+
+ A
+
+
+ A1. Letter ~ A
+ A1 ^Note: \(value)
+ """
+
+ guard case .some(.malformedClue) = parseError(from: source) else {
+ Issue.record("expected malformedClue")
+ return
+ }
+ }
+
+ @Test("An over-long answer reading is rejected")
+ func overLongAnswerReadingIsRejected() {
+ let answer = String(repeating: "A", count: XD.maxClueTextLength + 1)
+ let source = """
+ Title: Long Answer
+
+
+ A
+
+
+ A1. Letter ~ \(answer)
+ """
+
+ guard case .some(.malformedClue) = parseError(from: source) else {
+ Issue.record("expected malformedClue")
+ return
+ }
+ }
+
+ @Test("More accepted answers than the maximum are rejected")
+ func tooManyAcceptedAnswersAreRejected() {
+ let tokens = (1...(XD.maxAcceptedAnswersPerClue + 1))
+ .map { "B\($0)" }
+ .joined(separator: " ")
+ let source = """
+ Title: Accepting
+
+
+ A
+
+
+ A1. Letter ~ A
+ A1 ^Accept: \(tokens)
+ """
+
+ guard case .some(.tooManyAcceptedAnswers) = parseError(from: source) else {
+ Issue.record("expected tooManyAcceptedAnswers")
+ return
+ }
+ }
+
+ @Test("An accepted-answer count at the maximum still parses")
+ func acceptedAnswersAtMaximumParse() throws {
+ let tokens = (1...XD.maxAcceptedAnswersPerClue)
+ .map { "B\($0)" }
+ .joined(separator: " ")
+ let source = """
+ Title: Accepting
+
+
+ A
+
+
+ A1. Letter ~ A
+ A1 ^Accept: \(tokens)
+ """
+
+ let xd = try XD.parse(source)
+ #expect(xd.acrossClues.first?.acceptedAnswers.count == XD.maxAcceptedAnswersPerClue)
+ }
+
+ // MARK: - Rebus budget
+
+ @Test("An over-long rebus expansion fails closed at its grid cell")
+ func overLongRebusValueFailsClosed() {
+ let value = String(repeating: "A", count: XD.maxRebusValueLength + 1)
+ let source = """
+ Title: Big Rebus
+ Rebus: 1=\(value)
+
+
+ 1
+
+
+ A1. Never reached
+ """
+
+ guard case .some(.unknownGridCharacter) = parseError(from: source) else {
+ Issue.record("expected unknownGridCharacter")
+ return
+ }
+ }
+
+ @Test("A rebus expansion at the maximum length still parses")
+ func rebusValueAtMaximumParses() throws {
+ let value = String(repeating: "A", count: XD.maxRebusValueLength)
+ let source = """
+ Title: Big Rebus
+ Rebus: 1=\(value)
+
+
+ 1
+
+
+ A1. Long fill ~ \(value)
+ """
+
+ let xd = try XD.parse(source)
+ guard case .open(let solution?, _, _) = xd.cells[0][0] else {
+ Issue.record("expected an open cell with a solution")
+ return
+ }
+ #expect(solution.count == XD.maxRebusValueLength)
+ }
+}
diff --git a/Tests/Unit/XDMarkupTests.swift b/Tests/Unit/XDMarkupTests.swift
@@ -85,4 +85,33 @@ struct XDMarkupTests {
#expect(runs(XDMarkup.attributed(source)) == [Run(text: source, intent: nil)])
#expect(XDMarkup.stripped(source) == source)
}
+
+ @Test("A clue packed with unterminated openers stays literal")
+ func manyUnterminatedOpenersStayLiteral() {
+ // Adversarial shape: every `{/` opener used to rescan to the end of
+ // the clue looking for a close that never comes, making the scan
+ // quadratic. The exhausted-marker fast path keeps it linear; the
+ // output must be unchanged — all literal.
+ let source = String(repeating: "{/", count: 500)
+ #expect(XDMarkup.stripped(source) == source)
+ #expect(runs(XDMarkup.attributed(source)) == [Run(text: source, intent: nil)])
+ }
+
+ @Test("An exhausted marker leaves other markers' spans intact")
+ func exhaustedMarkerLeavesOtherMarkersIntact() {
+ let source = "{/a {*b*} {-c"
+ #expect(runs(XDMarkup.attributed(source)) == [
+ Run(text: "{/a ", intent: nil),
+ Run(text: "b", intent: .stronglyEmphasized),
+ Run(text: " {-c", intent: nil)
+ ])
+ #expect(XDMarkup.stripped(source) == "{/a b {-c")
+ }
+
+ @Test("A repeated unterminated marker stays literal at every occurrence")
+ func repeatedUnterminatedMarkerStaysLiteral() {
+ let source = "{/first {/second {/third"
+ #expect(runs(XDMarkup.attributed(source)) == [Run(text: source, intent: nil)])
+ #expect(XDMarkup.stripped(source) == source)
+ }
}
