Coverage for /pythoncovmergedfiles/medio/medio/src/turbohtml/tools/fuzz/xml_structure_generators.py: 48%

1"""XML lexical choices consume expansion steps without inventing DOM nodes.""" 

2 

3from __future__ import annotations 

4 

5import argparse 

6import random 

7from dataclasses import dataclass 

8from pathlib import Path 

9from typing import TYPE_CHECKING, Final 

10 

11from fuzz.structure_generators import ( 

12 BudgetError, 

13 Generated, 

14 GenerationBudget, 

15 Grammar, 

16 Identifier, 

17 Production, 

18 ProductionFloorError, 

19 Reference, 

20 compile_grammar, 

21 generate, 

22 generation_sweep, 

23 write_corpus, 

24) 

25 

26from turbohtml import CData, Comment, Doctype, Element, Html, ProcessingInstruction, Text, parse_xml 

27 

28if TYPE_CHECKING: 

29 from collections.abc import Callable, Iterator, Sequence 

30 

31 from turbohtml import Document, Node 

32 

33XmlRecord = tuple[str, str, str, tuple[tuple[str, str], ...], int] 

34 

35 

36def main(argv: Sequence[str] | None = None) -> int: 

37 """Keep corpus files independent of parser acceptance.""" 

38 parser: Final = argparse.ArgumentParser() 

39 parser.add_argument("--output", type=Path, required=True) 

40 parser.add_argument("--budget", type=int, default=30) 

41 parser.add_argument("--steps", type=int, default=120) 

42 parser.add_argument("--raw", action="store_true") 

43 parser.add_argument("--count", type=int, default=0) 

44 parser.add_argument("--seed", type=int, default=0) 

45 parser.add_argument("--byte-budget", type=int, default=64, help="maximum random raw input length") 

46 args: Final = parser.parse_args(argv) 

47 if args.count < 0: 

48 parser.error("count must be nonnegative") 

49 try: 

50 cases: Final = ( 

51 tuple(xml_raw_generate(random.Random(args.seed + index), args.byte_budget) for index in range(args.count)) 

52 if args.raw and args.count 

53 else xml_raw_inputs() 

54 if args.raw 

55 else tuple( 

56 xml_generate(random.Random(args.seed + index), args.budget, steps=args.steps) 

57 for index in range(args.count) 

58 ) 

59 if args.count 

60 else generation_sweep(_GRAMMAR, budget=GenerationBudget(args.budget, args.steps)) 

61 ) 

62 except (BudgetError, ProductionFloorError) as error: 

63 parser.error(str(error)) 

64 write_corpus(cases, args.output) 

65 return 0 

66 

67 

68def xml_generate(rng: random.Random, budget: int = 30, *, steps: int = 120) -> Generated: 

69 """Keep well-formed XML and raw-byte rejection seeds in distinct profiles.""" 

70 return generate(_GRAMMAR, rng, GenerationBudget(budget, steps)) 

71 

72 

73def xml_grammar() -> Grammar: 

74 """Retain production provenance for corpus audits.""" 

75 return _GRAMMAR 

76 

77 

78def xml_expected(case: Generated) -> tuple[XmlRecord, ...]: 

79 """Use literal production semantics independently of either parse.""" 

80 records: Final[list[XmlRecord]] = [] 

81 _expect(iter(case.productions), -1, records) 

82 return tuple(records) 

83 

84 

85def _expect(trace: Iterator[str], parent: int, records: list[XmlRecord]) -> None: 

86 positions: Final[dict[str, int]] = {} 

87 for item in _RULES[next(trace)].expected: 

88 owner: Final = parent if not item.parent else positions[item.parent] 

89 if isinstance(item, _Child): 

90 _expect(trace, owner, records) 

91 else: 

92 positions[item.label] = len(records) 

93 records.append((item.kind, item.name, item.data, item.attrs, owner)) 

94 

95 

96def xml_structure_check( 

97 case: Generated, 

98 *, 

99 read: Callable[[str], Document] = parse_xml, 

100 serialize: Callable[[Node], str] | None = None, 

101) -> str | None: 

102 """Require literal names, content, parents and bindings before comparing serialization.""" 

103 expected: Final = xml_expected(case) 

104 root: Final = read(case.data.decode("utf-8")) 

105 if xml_snapshot(root) != expected: 

106 return "parsed XML differs from production literals" 

107 printed: Final = root.serialize(Html(xml=True)) if serialize is None else serialize(root) 

108 if xml_snapshot(read(printed)) != expected: 

109 return "serialized XML differs from production literals" 

110 return None 

111 

112 

113def xml_snapshot(root: Document) -> tuple[XmlRecord, ...]: 

114 """Keep parent ordinals stable when wrapper identities differ.""" 

115 nodes: Final = [root, *root.descendants] 

116 records: Final[list[XmlRecord]] = [] 

117 for node in nodes: 

118 parent: Final = -1 if node.parent is None else nodes.index(node.parent) 

119 if isinstance(node, Element): 

120 records.append(( 

121 f"element:{node.namespace.value}", 

122 node.tag, 

123 "", 

124 tuple(sorted((name, str(value)) for name, value in node.attrs.items())), 

125 parent, 

126 )) 

127 elif isinstance(node, Doctype): 

128 records.append(( 

129 "doctype", 

130 node.name, 

131 "", 

132 tuple( 

133 (name, value) 

134 for name, value in (("public", node.public_id), ("system", node.system_id)) 

135 if value is not None 

136 ), 

137 parent, 

138 )) 

139 elif isinstance(node, ProcessingInstruction): 

140 records.append(("pi", node.target, node.data, (), parent)) 

141 elif isinstance(node, (Text, Comment, CData)): 

142 records.append((type(node).__name__.lower(), "", node.data, (), parent)) 

143 else: 

144 records.append(("document", "", "", (), parent)) 

145 return tuple(records) 

146 

147 

148def xml_document_check(markup: str, serialize: Callable[[Node], str] | None = None) -> str | None: 

149 """Compare XML input semantics rather than reparsing an HTML interpretation.""" 

150 root: Final = parse_xml(markup) 

151 expected: Final = xml_snapshot(root) 

152 printed: Final = root.serialize(Html(xml=True)) if serialize is None else serialize(root) 

153 return None if xml_snapshot(parse_xml(printed)) == expected else "XML serialization changes the document" 

154 

155 

156def xml_source_generate(rng: random.Random) -> str: 

157 """Use XML documents so grammar cases reach the XML parser.""" 

158 return xml_generate(rng).data.decode("utf-8") 

159 

160 

161def xml_source_seeds() -> list[str]: 

162 """Force production coverage so random choices cannot leave alternatives untested.""" 

163 return [case.data.decode("utf-8") for case in generation_sweep(_GRAMMAR, budget=GenerationBudget(30, 120))] 

164 

165 

166def xml_source_controls() -> dict[str, bool]: 

167 """Make oracle no-ops fail on data loss and reparenting.""" 

168 return { 

169 "dropped attribute": xml_document_check( 

170 '<Root><Leaf key="value"/></Root>', 

171 lambda node: node.serialize(Html(xml=True)).replace(' key="value"', ""), 

172 ) 

173 is not None, 

174 "changed parent": xml_document_check( 

175 "<Root><Group><Leaf/></Group></Root>", 

176 lambda _node: "<Root><Group/><Leaf/></Root>", 

177 ) 

178 is not None, 

179 } 

180 

181 

182def xml_raw_generate(rng: random.Random, budget: int = 64) -> Generated: 

183 """Bound raw input length without claiming a DOM node cost.""" 

184 if budget < 0: 

185 msg = "byte budget must be nonnegative" 

186 raise BudgetError(msg) 

187 return Generated(rng.randbytes(rng.randint(0, budget)), 0, 0, ("xml:raw:bytes",), ()) 

188 

189 

190def xml_raw_inputs() -> tuple[Generated, ...]: 

191 """Preserve invalid UTF-8 and XML delimiters as bounded byte inputs.""" 

192 return tuple(Generated(source, 0, 0, (f"xml:raw:{index}",), ()) for index, source in enumerate(_RAW)) 

193 

194 

195@dataclass(frozen=True) 

196class _Literal: 

197 kind: str 

198 name: str = "" 

199 data: str = "" 

200 attrs: tuple[tuple[str, str], ...] = () 

201 parent: str = "" 

202 label: str = "" 

203 

204 

205@dataclass(frozen=True) 

206class _Child: 

207 parent: str = "" 

208 

209 

210@dataclass(frozen=True) 

211class _Rule: 

212 production: Production 

213 expected: tuple[_Literal | _Child, ...] 

214 

215 

216def _rules() -> dict[str, _Rule]: 

217 rules: Final = [ 

218 _Rule( 

219 Production( 

220 "xml:document", 

221 "document", 

222 ( 

223 Reference("declaration", 0), 

224 Reference("misc", 1), 

225 Reference("doctype", 1), 

226 b'<Root id="', 

227 Identifier("target", definition=True), 

228 b'">', 

229 Reference("node", 2), 

230 b'<Ref target="#', 

231 Identifier("target", definition=False), 

232 b'"/></Root>', 

233 Reference("misc", 1), 

234 ), 

235 3, 

236 _STANDARD, 

237 2, 

238 ), 

239 ( 

240 _Literal("document", label="document"), 

241 _Child("document"), 

242 _Child("document"), 

243 _Child("document"), 

244 _Literal("element:html", "Root", attrs=(("id", "x"),), parent="document", label="root"), 

245 _Child("root"), 

246 _Literal("element:html", "Ref", attrs=(("target", "#x"),), parent="root"), 

247 _Child("document"), 

248 ), 

249 ), 

250 _Rule( 

251 Production( 

252 "xml:nested", "node", (b"<Group>", Reference("node"), Reference("node"), b"</Group>"), 1, _STANDARD 

253 ), 

254 (_Literal("element:html", "Group", label="group"), _Child("group"), _Child("group")), 

255 ), 

256 ] 

257 for index, declaration in enumerate(_DECLARATIONS): 

258 rules.append(_Rule(Production(f"xml:declaration:{index}", "declaration", (declaration,), 0, _STANDARD), ())) 

259 for index, (source, expected) in enumerate(_MISC): 

260 rules.append(_Rule(Production(f"xml:misc:{index}", "misc", (source,), len(expected), _STANDARD), expected)) 

261 for index, (source, attrs) in enumerate(_DOCTYPES): 

262 rules.append( 

263 _Rule( 

264 Production(f"xml:doctype:{index}", "doctype", (source,), int(bool(source)), _COMPETITOR), 

265 (_Literal("doctype", "Root", attrs=attrs),) if source else (), 

266 ) 

267 ) 

268 for index, (source, expected) in enumerate(_LEAVES): 

269 rules.append( 

270 _Rule( 

271 Production(f"xml:leaf:{index}", "node", (source,), len(expected), _STANDARD, int(len(expected) > 1)), 

272 expected, 

273 ) 

274 ) 

275 return {rule.production.name: rule for rule in rules} 

276 

277 

278_STANDARD: Final = "https://www.w3.org/TR/2008/REC-xml-20081126/" 

279_COMPETITOR: Final = "https://github.com/GNOME/libxml2/blob/c43dc98d27ac315a48d93dbd399c6c22cf7125b1/fuzz/xml.dict" 

280_DECLARATIONS: Final = ( 

281 b"", 

282 b'<?xml version="1.0"?>', 

283 b"<?xml version='1.0'?>", 

284 b'<?xml version="1.0" encoding="UTF-8"?>', 

285 b"<?xml version='1.0' encoding='UTF-8'?>", 

286 b'<?xml version="1.0" standalone="yes"?>', 

287 b'<?xml version="1.0" standalone="no"?>', 

288) 

289_MISC: Final = ( 

290 (b"", ()), 

291 (b" \t\r\n", ()), 

292 (b"<!--before-->", (_Literal("comment", data="before"),)), 

293 (b"<?probe data?>", (_Literal("pi", "probe", "data"),)), 

294 (b"<!--before--><?probe data?>", (_Literal("comment", data="before"), _Literal("pi", "probe", "data"))), 

295) 

296_DOCTYPES: Final = ( 

297 (b"", ()), 

298 (b"<!DOCTYPE Root>", ()), 

299 (b'<!DOCTYPE Root SYSTEM "root.dtd">', (("system", "root.dtd"),)), 

300 (b'<!DOCTYPE Root PUBLIC "public-id" "root.dtd">', (("public", "public-id"), ("system", "root.dtd"))), 

301 (b"<!DOCTYPE Root [<!ELEMENT Root ANY>]>", ()), 

302) 

303_LEAVES: Final = ( 

304 (b"<Leaf/>", (_Literal("element:html", "Leaf"),)), 

305 (b"<Leaf></Leaf>", (_Literal("element:html", "Leaf"),)), 

306 *[ 

307 ( 

308 f"<{name}>x</{name}>".encode(), 

309 (_Literal("element:html", name, label="leaf"), _Literal("text", data="x", parent="leaf")), 

310 ) 

311 for name in ("Leaf", "leaf", "_name", "name-1", "name.1", "é", "水") 

312 ], 

313 *[ 

314 ( 

315 f"<Leaf>{encoded}</Leaf>".encode(), 

316 (_Literal("element:html", "Leaf", label="leaf"), _Literal("text", data=decoded, parent="leaf")), 

317 ) 

318 for encoded, decoded in ( 

319 ("x", "x"), 

320 ("a\tb\r\nc\rd", "a\tb\nc\nd"), 

321 ("&amp;&lt;&gt;&quot;&apos;", "&<>\"'"), 

322 ("&#9;&#10;&#13;", "\t\n\r"), 

323 ("&#65;&#x1F600;", "A😀"), 

324 ("é水😀", "é水😀"), 

325 ) 

326 ], 

327 *[ 

328 ( 

329 f"<Leaf value={quote}{encoded}{quote}/>".encode(), 

330 (_Literal("element:html", "Leaf", attrs=(("value", decoded),)),), 

331 ) 

332 for quote in ("'", '"') 

333 for encoded, decoded in ( 

334 ("", ""), 

335 ("a b", "a b"), 

336 ("&quot;&apos;", "\"'"), 

337 ("a\tb\r\nc\rd", "a b c d"), 

338 ("&amp;&lt;", "&<"), 

339 ("&#9;&#10;&#13;", "\t\n\r"), 

340 ("é水😀", "é水😀"), 

341 ) 

342 ], 

343 ( 

344 b"<Leaf>a<Inner/>b</Leaf>", 

345 ( 

346 _Literal("element:html", "Leaf", label="leaf"), 

347 _Literal("text", data="a", parent="leaf"), 

348 _Literal("element:html", "Inner", parent="leaf"), 

349 _Literal("text", data="b", parent="leaf"), 

350 ), 

351 ), 

352 ( 

353 b"<Leaf><!--inside--></Leaf>", 

354 (_Literal("element:html", "Leaf", label="leaf"), _Literal("comment", data="inside", parent="leaf")), 

355 ), 

356 ( 

357 b"<Leaf><?probe data?></Leaf>", 

358 (_Literal("element:html", "Leaf", label="leaf"), _Literal("pi", "probe", "data", parent="leaf")), 

359 ), 

360 *[ 

361 ( 

362 f"<Leaf><![CDATA[{text}]]></Leaf>".encode(), 

363 (_Literal("element:html", "Leaf", label="leaf"), _Literal("cdata", data=text, parent="leaf")), 

364 ) 

365 for text in ("", "x", "<&", "é水😀") 

366 ], 

367 ( 

368 b'<p:Leaf xmlns:p="urn:p" p:key="value"/>', 

369 (_Literal("element:html", "p:Leaf", attrs=(("p:key", "value"), ("xmlns:p", "urn:p"))),), 

370 ), 

371 (b'<Leaf xmlns="urn:d"/>', (_Literal("element:html", "Leaf", attrs=(("xmlns", "urn:d"),)),)), 

372 (b'<Leaf xml:lang="en"/>', (_Literal("element:html", "Leaf", attrs=(("xml:lang", "en"),)),)), 

373 ( 

374 b'<Leaf xmlns="urn:d"><Inner xmlns=""/></Leaf>', 

375 ( 

376 _Literal("element:html", "Leaf", attrs=(("xmlns", "urn:d"),), label="leaf"), 

377 _Literal("element:html", "Inner", attrs=(("xmlns", ""),), parent="leaf"), 

378 ), 

379 ), 

380 ( 

381 b'<p:Leaf xmlns:p="urn:a"><p:Inner xmlns:p="urn:b"/></p:Leaf>', 

382 ( 

383 _Literal("element:html", "p:Leaf", attrs=(("xmlns:p", "urn:a"),), label="leaf"), 

384 _Literal("element:html", "p:Inner", attrs=(("xmlns:p", "urn:b"),), parent="leaf"), 

385 ), 

386 ), 

387) 

388_RAW: Final = ( 

389 b"", 

390 b"\xff", 

391 b"\xc0\xaf", 

392 b"<", 

393 b"<Root>", 

394 b"<Root/>tail", 

395 b"<Root>&unknown;</Root>", 

396 b"<Root>&#0;</Root>", 

397 b"<Root a='x' a='y'/>", 

398 b"<Root><!--a--b--></Root>", 

399) 

400_RULES: Final = _rules() 

401_GRAMMAR: Final = compile_grammar(tuple(rule.production for rule in _RULES.values()), "document") 

402 

403__all__ = [ 

404 "XmlRecord", 

405 "main", 

406 "xml_document_check", 

407 "xml_expected", 

408 "xml_generate", 

409 "xml_grammar", 

410 "xml_raw_generate", 

411 "xml_raw_inputs", 

412 "xml_snapshot", 

413 "xml_source_controls", 

414 "xml_source_generate", 

415 "xml_source_seeds", 

416 "xml_structure_check", 

417] 

418 

419if __name__ == "__main__": 

420 raise SystemExit(main())