Coverage for /pythoncovmergedfiles/medio/medio/src/turbohtml/tools/fuzz/html_structure_generators.py: 84%

1"""Keep table alternatives inside complete elements so attributes consume no fictitious DOM nodes.""" 

2 

3from __future__ import annotations 

4 

5import argparse 

6import random 

7import re 

8from collections import deque 

9from dataclasses import dataclass 

10from functools import cache 

11from html import escape 

12from pathlib import Path 

13from typing import TYPE_CHECKING, Final, TypeAlias 

14 

15from fuzz.html_generation_tables import ( 

16 ATTRIBUTE_VALUE_RULES, 

17 COMMON_RULES, 

18 HTML_RULES, 

19 HTML_TAGS, 

20 SOURCE_URLS, 

21 TAG_ATTRIBUTE_RULES, 

22 TableRule, 

23) 

24from fuzz.structure_generators import ( 

25 BudgetError, 

26 Generated, 

27 Grammar, 

28 GrammarError, 

29 Identifier, 

30 Production, 

31 ProductionFloorError, 

32 compile_grammar, 

33 generate, 

34 generation_sweep, 

35 html_grammar, 

36 write_corpus, 

37) 

38 

39if TYPE_CHECKING: 

40 from collections.abc import Sequence 

41 

42 

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

44 """Export bytes that the coverage-guided lane can consume directly.""" 

45 parser: Final = argparse.ArgumentParser() 

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

47 parser.add_argument("--count", type=int, default=64) 

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

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

50 parser.add_argument("--sweep", action="store_true") 

51 args: Final = parser.parse_args(argv) 

52 if args.count < 1: 

53 parser.error("count must be positive") 

54 try: 

55 cases: Final = ( 

56 generation_sweep(_GRAMMAR, args.count, args.budget) 

57 if args.sweep 

58 else tuple(html_generate(random.Random(args.seed + index), args.budget) for index in range(args.count)) 

59 ) 

60 except (GrammarError, BudgetError, ProductionFloorError) as error: 

61 parser.error(str(error)) 

62 write_corpus(cases, args.output) 

63 return 0 

64 

65 

66def html_generate(rng: random.Random, budget: int = 30) -> Generated: 

67 """Use one budget across tags, attributes and parser-created wrappers.""" 

68 return generate(_GRAMMAR, rng, budget) 

69 

70 

71def html_grammar_complete(vocabulary: HtmlVocabulary | None = None) -> Grammar: 

72 """Retain table alternatives separately so finite sweeps expose omitted rows.""" 

73 vocabulary = _VOCABULARY if vocabulary is None else vocabulary 

74 productions: Final = list(html_grammar().productions) 

75 values: Final = _Values((*vocabulary.common, *vocabulary.html, *vocabulary.values, *vocabulary.tag_attributes)) 

76 attributes: Final = tuple(rule for rule in vocabulary.html if _ATTRIBUTE.fullmatch(rule[2])) 

77 for tag in vocabulary.tags: 

78 productions.append( 

79 _element_production( 

80 f"html:domato:tag:{tag}", 

81 tag, 

82 (), 

83 _TAG_ORIGINS[tag] if vocabulary is _VOCABULARY else vocabulary.origin, 

84 ) 

85 ) 

86 for rule in attributes: 

87 productions.append( 

88 _element_production( 

89 f"html:domato:attribute:{rule[0]}", 

90 "span", 

91 values.expand(rule[2]), 

92 _origin(vocabulary, "html.txt", rule[0]), 

93 ) 

94 ) 

95 for rule in vocabulary.values: 

96 owner, route = values.owner(attributes, rule) 

97 productions.append( 

98 _element_production( 

99 f"html:domato:value:{rule[0]}", 

100 "span", 

101 values.expand(owner[2], route), 

102 _origin(vocabulary, "attributevalues.txt", rule[0]), 

103 ) 

104 ) 

105 for rule in vocabulary.tag_attributes: 

106 tag: Final = rule[1].removesuffix("_attributes").removesuffix("_attribute") 

107 if tag not in vocabulary.tags: 

108 msg = f"tag attribute has no tag materialization: {tag}" 

109 raise GrammarError(msg) 

110 productions.append( 

111 _element_production( 

112 f"html:domato:tag-attribute:{rule[0]}", 

113 tag, 

114 values.expand(rule[2]), 

115 _origin(vocabulary, "tagattributes.txt", rule[0]), 

116 ) 

117 ) 

118 productions.extend(_hostile_productions()) 

119 return compile_grammar(productions, "root") 

120 

121 

122def _origin(vocabulary: HtmlVocabulary, filename: str, line: int) -> str: 

123 return f"{SOURCE_URLS[filename]}#L{line}" if vocabulary is _VOCABULARY else vocabulary.origin 

124 

125 

126def html_document(case: Generated) -> bool: 

127 """Use document parsing for profiles whose tags are ignored in a div fragment.""" 

128 return any(name.startswith("html:document:") for name in case.productions) 

129 

130 

131def _element_production(name: str, tag: str, attributes: Parts, origin: str) -> Production: 

132 if tag in {"html", "head", "body"}: 

133 parts: Final = ( 

134 b'<html id="', 

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

136 b'"', 

137 *(attributes if tag == "html" else ()), 

138 b"><head", 

139 *(attributes if tag == "head" else ()), 

140 b"><title>x</title></head><body", 

141 *(attributes if tag == "body" else ()), 

142 b'><a href="#', 

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

144 b'">x</a></body></html>', 

145 ) 

146 return Production("html:document:" + name, "root", parts, 8, origin, 4) 

147 if tag in {"frame", "frameset"}: 

148 parts = ( 

149 b'<frameset id="', 

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

151 b'"', 

152 *(attributes if tag == "frameset" else ()), 

153 b"><frame", 

154 *(attributes if tag == "frame" else ()), 

155 b' src="#', 

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

157 b'"></frameset>', 

158 ) 

159 return Production("html:document:" + name, "root", parts, 5, origin, 3) 

160 if tag == "plaintext": 

161 return Production( 

162 name, 

163 "root", 

164 ( 

165 b'<div id="', 

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

167 b'"><a href="#', 

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

169 b'">x</a><plaintext', 

170 *attributes, 

171 b">x", 

172 ), 

173 6, 

174 origin, 

175 3, 

176 ) 

177 prefix, suffix, nodes, height = _element_shape(tag) 

178 return Production(name, "node", (prefix, *attributes, suffix), nodes, origin, height) 

179 

180 

181def _element_shape(tag: str) -> tuple[bytes, bytes, int, int]: 

182 if shape := _SHAPES.get(tag): 

183 return shape 

184 if tag in _TABLE_SECTIONS: 

185 return b"<table><" + tag.encode("ascii"), b"><tr><td>x</td></tr></" + tag.encode("ascii") + b"></table>", 5, 4 

186 if tag in {"td", "th"}: 

187 return ( 

188 b"<table><tbody><tr><" + tag.encode("ascii"), 

189 b">x</" + tag.encode("ascii") + b"></tr></tbody></table>", 

190 5, 

191 4, 

192 ) 

193 if tag in _VOID: 

194 return b"<" + tag.encode("ascii"), b">", 1, 0 

195 return b"<" + tag.encode("ascii"), b">x</" + tag.encode("ascii") + b">", 2, 1 

196 

197 

198def _hostile_productions() -> tuple[Production, ...]: 

199 return ( 

200 Production( 

201 "html:hostile:formatting", "node", (b"<b><i>x</b>y</i>",), 5, _STANDARD + "#adoption-agency-algorithm", 2 

202 ), 

203 Production( 

204 "html:hostile:near-miss", 

205 "node", 

206 (b"<span>x</spna><b>y</b></span>",), 

207 4, 

208 _STANDARD + "#parsing-main-inbody", 

209 2, 

210 ), 

211 *( 

212 Production( 

213 f"html:foreign:svg:{tag}", 

214 "node", 

215 (f"<svg><{tag}><p>x</p></{tag}><circle/></svg>".encode("ascii"),), 

216 5, 

217 _STANDARD + "#html-integration-point", 

218 3, 

219 ) 

220 for tag in ("foreignObject", "desc", "title") 

221 ), 

222 ) 

223 

224 

225class _Values: 

226 def __init__(self, rules: Sequence[TableRule]) -> None: 

227 self.rules: Final[dict[str, list[TableRule]]] = {} 

228 for rule in rules: 

229 self.rules.setdefault(rule[1], []).append(rule) 

230 self.minimum: Final[dict[str, TableRule]] = {} 

231 costs: Final[dict[str, int]] = {} 

232 changed = True 

233 while changed: 

234 changed = False 

235 for symbol, alternatives in self.rules.items(): 

236 if symbol in _PRIMITIVES: 

237 continue 

238 for rule in alternatives: 

239 children: Final = [item for item in _symbols(rule[2]) if item not in _PRIMITIVES] 

240 if all(child in costs for child in children): 

241 cost: Final = 1 + sum(costs[child] for child in children) 

242 if symbol not in costs or cost < costs[symbol]: 

243 costs[symbol] = cost 

244 self.minimum[symbol] = rule 

245 changed = True 

246 

247 def owner(self, attributes: Sequence[TableRule], target: TableRule) -> tuple[TableRule, tuple[TableRule, ...]]: 

248 for attribute in attributes: 

249 pending: Final[deque[tuple[str, tuple[TableRule, ...]]]] = deque( 

250 (symbol, ()) for symbol in _symbols(attribute[2]) 

251 ) 

252 visited: Final[set[str]] = set() 

253 while pending: 

254 symbol, path = pending.popleft() 

255 if symbol == target[1]: 

256 return attribute, (*path, target) 

257 if symbol not in visited and symbol not in _PRIMITIVES: 

258 visited.add(symbol) 

259 pending.extend( 

260 (child, (*path, rule)) for rule in self.rules.get(symbol, ()) for child in _symbols(rule[2]) 

261 ) 

262 msg = f"value alternative has no emitting attribute owner: {target[1]} at line {target[0]}" 

263 raise GrammarError(msg) 

264 

265 def expand(self, source: str, route: tuple[TableRule, ...] = ()) -> Parts: 

266 if attribute := _ATTRIBUTE.fullmatch(source): 

267 return ( 

268 f' {attribute[1]}="'.encode("ascii"), 

269 *( 

270 escape(part.decode("utf-8"), quote=True).encode("utf-8") if isinstance(part, bytes) else part 

271 for part in self.expand(attribute[2], route) 

272 ), 

273 b'"', 

274 ) 

275 parts: Final[list[bytes | Identifier]] = [] 

276 position = 0 

277 for token in _TOKEN.finditer(source): 

278 parts.extend(_literal(source[position : token.start()])) 

279 symbol, *parameters = token[1].split() 

280 if symbol in _PRIMITIVES: 

281 parts.extend(_primitive(symbol, parameters)) 

282 else: 

283 forced: Final = bool(route and route[0][1] == symbol) 

284 if (chosen := route[0] if forced else self.minimum.get(symbol)) is None: 

285 msg = f"unproductive value symbol: {symbol}" 

286 raise GrammarError(msg) 

287 parts.extend(self.expand(chosen[2], route[1:] if forced else ())) 

288 position = token.end() 

289 parts.extend(_literal(source[position:])) 

290 return tuple(parts) 

291 

292 

293@cache # owner() re-reads the same value sources for every one of the ~1000 value alternatives 

294def _symbols(source: str) -> tuple[str, ...]: 

295 return tuple(token[1].split()[0] for token in _TOKEN.finditer(source)) 

296 

297 

298def _literal(source: str) -> Parts: 

299 return (source.encode("utf-8"),) if source else () 

300 

301 

302def _primitive(symbol: str, parameters: Sequence[str]) -> Parts: 

303 if symbol == "elementid": 

304 return (Identifier("target", definition=False),) 

305 if symbol == "class": 

306 return (b"a",) 

307 if symbol == "import": 

308 if tuple(parameters) != ("from=cssgrammar", "symbol=declaration5"): 

309 msg = f"unsupported grammar import: {parameters}" 

310 raise GrammarError(msg) 

311 return (b"color: red; color: red; color: red; color: red; color: red",) 

312 if symbol in {"int", "float"}: 

313 return ( 

314 next((item.removeprefix("min=") for item in parameters if item.startswith("min=")), "0").encode("ascii"), 

315 ) 

316 if symbol == "char": 

317 return ( 

318 chr(int(next((item.removeprefix("min=") for item in parameters if item.startswith("min=")), "120"))).encode( 

319 "utf-8" 

320 ), 

321 ) 

322 return (_PRIMITIVES[symbol],) 

323 

324 

325@dataclass(frozen=True) 

326class HtmlVocabulary: 

327 """Keep source alternatives explicit when a pinned table is updated.""" 

328 

329 tags: tuple[str, ...] 

330 html: tuple[TableRule, ...] 

331 values: tuple[TableRule, ...] 

332 tag_attributes: tuple[TableRule, ...] 

333 common: tuple[TableRule, ...] = () 

334 origin: str = "supplied HTML vocabulary" 

335 

336 

337Parts: TypeAlias = tuple[bytes | Identifier, ...] 

338 

339_STANDARD: Final = "https://html.spec.whatwg.org/multipage/parsing.html" 

340_TOKEN: Final = re.compile(r"<([^<>]+)>") 

341_ATTRIBUTE: Final = re.compile(r'([a-zA-Z][a-zA-Z0-9:_-]*)="([^"]*)"') 

342_TABLE_SECTIONS: Final = frozenset({"tbody", "thead", "tfoot"}) 

343_SHAPES: Final = { 

344 "table": (b"<table", b"><tbody><tr><td>x</td></tr></tbody></table>", 5, 4), 

345 "tr": (b"<table><tbody><tr", b"><td>x</td></tr></tbody></table>", 5, 4), 

346 "col": (b"<table><colgroup><col", b"></colgroup></table>", 3, 2), 

347 "colgroup": (b"<table><colgroup", b"><col></colgroup></table>", 3, 2), 

348 "caption": (b"<table><caption", b">x</caption></table>", 3, 2), 

349 "option": (b"<select><option", b">x</option></select>", 3, 2), 

350 "optgroup": (b"<select><optgroup", b"><option>x</option></optgroup></select>", 4, 3), 

351 "template": (b"<template", b"></template>", 2, 0), 

352} 

353_VOID: Final = frozenset({ 

354 "area", 

355 "base", 

356 "basefont", 

357 "bgsound", 

358 "br", 

359 "col", 

360 "embed", 

361 "hr", 

362 "image", 

363 "img", 

364 "input", 

365 "keygen", 

366 "link", 

367 "meta", 

368 "param", 

369 "source", 

370 "track", 

371 "wbr", 

372}) 

373_PRIMITIVES: Final = { 

374 "elementid": b"x", 

375 "class": b"a", 

376 "import": b"", 

377 "int": b"0", 

378 "float": b"0", 

379 "char": b"x", 

380 "htmlsafestring": b"x", 

381 "string": b"x", 

382 "hex": b"0", 

383 "lt": b"<", 

384 "gt": b">", 

385 "hash": b"#", 

386 "space": b" ", 

387 "cr": b"\r", 

388 "lf": b"\n", 

389} 

390 

391_TAG_ORIGINS: Final = { 

392 tag: f"{SOURCE_URLS['common.txt']}#L{line}" for line, symbol, tag in COMMON_RULES if symbol == "tagname" 

393} 

394_VOCABULARY: Final = HtmlVocabulary(HTML_TAGS, HTML_RULES, ATTRIBUTE_VALUE_RULES, TAG_ATTRIBUTE_RULES, COMMON_RULES) 

395_GRAMMAR: Final = html_grammar_complete() 

396 

397__all__ = ["HtmlVocabulary", "html_document", "html_generate", "html_grammar_complete", "main"] 

398 

399if __name__ == "__main__": 

400 raise SystemExit(main())