Coverage for scripts/check_bnf_coverage.py: 84%
63 statements
« prev ^ index » next coverage.py v7.15.2, created at 2026-07-23 22:58 +0000
1"""
2Cross-check the grammar/*.lark files against the official ADQL 2.1 Annex A
3nonterminal list.
5This is a *coverage* check, not a proof of equivalence: grammar equivalence
6between two context-free grammars is undecidable in general, so no tool can
7mechanically "prove" the grammar is correct. What this script *can* do is
8mechanically verify that every structural nonterminal defined in Annex A has
9some corresponding rule somewhere in grammar/{lexer,literals,core,adql}.lark
10-- either under the same name, or under a deliberate, explicitly-listed
11alias (documented below and cross-referenced by the `[AnnexA #x]` comments
12throughout those files).
14Run it after editing the grammar to catch accidental omissions:
16 uv run python scripts/check_bnf_coverage.py
18Source of Annex A: IVOA Recommendation ADQL 2.1 (2023-12-15), Annex A ("ADQL
19grammar"), supplied verbatim by the user and saved in annex_a_v21.txt
20alongside this script (the official ivoa.net/ivoa.info mirrors disallow
21automated fetching, and no other reliably fetchable mirror of the exact 2.1
22Annex A text could be found -- see this project's chat history).
24Known, intentional non-matches (not bugs -- see comments below):
25 - Pure punctuation/character-literal nonterminals (<comma> ::= , etc.):
26 represented as inline string literals in Lark, never as named rules.
27 - Pure lexer-bookkeeping nonterminals (<token>, <newline>, <space>, the
28 Latin-letter character classes...): meaningless in a Lark grammar, whose
29 regex terminals already cover arbitrary Unicode input.
30 - Decomposed literal/identifier lexical rules (<digit>, <mantissa>,
31 <exact_numeric_literal>, <coordinate1>...): folded into a single regex
32 terminal (SIGNED_NUMBER, NAME, STRING) rather than kept as separate
33 named sub-rules.
34 - `table_subquery` / `subquery` / `query_expression`: Annex A threads a
35 parenthesized subquery through three wrapper nonterminals
36 (query_expression -> subquery -> table_subquery); this grammar goes
37 straight to `select_expression` wherever any of those is used, which
38 accepts the same input.
39 - Geometry functions returning a number or a string (CONTAINS/INTERSECTS/
40 AREA/COORD1/COORD2/DISTANCE/COORDSYS) are, in Annex A, reached via
41 numeric_value_function / string_value_function rather than through a
42 dedicated "geometry_value" branch of value_expression -- this grammar
43 folds all geometry functions into one `geometry_function` dispatch
44 point reached via `function_call`/`primary` instead, a harmless
45 simplification (see the SECTION 5 header comment in core.lark).
46 - A handful of structural simplifications, e.g. GROUP BY accepting any
47 value_expression rather than only grouping_column_reference (a
48 deliberate, harmless superset matching real-world usage).
49"""
51import re
52from pathlib import Path
54_HERE = Path(__file__).parent
55_GRAMMAR_DIR = _HERE.parent / "src" / "pyadql" / "grammar"
56GRAMMAR_FILES = ["lexer.lark", "literals.lark", "core.lark", "adql.lark"]
57BNF_PATH = _HERE / "annex_a_v21.txt"
59# Deliberate renamings: AnnexA nonterminal name -> our Lark rule/alias name
60# (or a list of candidate names, when Annex A's one nonterminal maps to more
61# than one of ours -- e.g. distance_function's two overloads). Each mapping
62# here is documented by an `[AnnexA #x]` comment next to the corresponding
63# rule in grammar/core.lark or grammar/literals.lark.
64ALIASES = {
65 "point": "point_expr",
66 "circle": "circle_expr",
67 "box": "box_expr",
68 "polygon": "polygon_expr",
69 "region": "region_expr",
70 "centroid": "centroid_expr",
71 "area": "area_expr",
72 "coord1": "coord1_expr",
73 "coord2": "coord2_expr",
74 "extract_coordsys": "coordsys_expr",
75 "distance_function": ["distance_points", "distance_coords"],
76 "contains": "contains_expr",
77 "intersects": "intersects_expr",
78 "point_value": ["point_expr", "centroid_expr", "udf_as_point"],
79 "coord_value": ["point_expr", "centroid_expr", "udf_as_point", "column_reference"],
80 "circle_center": [
81 "coordinates",
82 "point_expr",
83 "centroid_expr",
84 "udf_as_point",
85 "column_reference",
86 ],
87 "box_center": [
88 "coordinates",
89 "point_expr",
90 "centroid_expr",
91 "udf_as_point",
92 "column_reference",
93 ],
94 "polygon_vertices": ["polygon_vertices_coords", "polygon_vertices_points"],
95 # table_subquery / subquery / query_expression: all three collapse to
96 # select_expression here, see module docstring.
97 "table_subquery": "select_expression",
98 "subquery": "select_expression",
99 "query_expression": "select_expression",
100 "correlation_name": "correlated_name",
101 "join_condition": "on_spec",
102 "named_columns_join": "using_spec",
103 "join_column_list": "column_name_list",
104 "qualified_join": "joined",
105 "outer_join_type": "join_type",
106 "qualifier": "correlated_name",
107 "identifier": "NAME",
108 "regular_identifier": "NAME",
109 "delimited_identifier": "NAME",
110 "keyword": "NAME",
111 "not_equals_operator": "COMP_OP",
112 "not_equals_operator1": "COMP_OP",
113 "not_equals_operator2": "COMP_OP",
114 "less_than_operator": "COMP_OP",
115 "less_than_or_equals_operator": "COMP_OP",
116 "greater_than_operator": "COMP_OP",
117 "greater_than_or_equals_operator": "COMP_OP",
118 "equals_operator": "COMP_OP",
119 "unsigned_decimal": "UNSIGNED_INT",
120 "exact_numeric_literal": "SIGNED_NUMBER",
121 "approximate_numeric_literal": "SIGNED_NUMBER",
122 "mantissa": "SIGNED_NUMBER",
123 "exponent": "SIGNED_NUMBER",
124 "signed_integer": "SIGNED_NUMBER",
125 "sign": "factor",
126 "unsigned_numeric_literal": "number_literal",
127 "unsigned_literal": "literal",
128 "unsigned_value_specification": "literal",
129 "general_literal": "string_literal",
130 "character_string_literal": "STRING",
131 "value_expression_primary": "primary",
132 "numeric_primary": "primary",
133 "character_primary": "primary",
134 "character_factor": "string_operand",
135 "character_value_expression": "string_concat",
136 "string_value_expression": "value_expression",
137 "match_value": "value_expression",
138 "pattern": "value_expression",
139 "group_by_term": "value_expression",
140 "group_by_term_list": "group_by_clause",
141 "order_by_expression": "value_expression",
142 "order_by_term": "sort_spec",
143 "order_by_term_list": "order_by_clause",
144 "order_by_direction": "order_direction",
145 "schema_name": "table_name",
146 "catalog_name": "table_name",
147 "unqualified_schema name": "table_name",
148 "set_function_specification": "set_function",
149 "general_set_function": "set_function",
150 "set_function_type": "SET_FUNC_NAME",
151 "math_function": "numeric_function",
152 "trig_function": "numeric_function",
153 "in_unit_function": "numeric_function",
154 "case_folding_function": "string_function",
155 "string_geometry_function": "coordsys_expr",
156 "string_value_function": "string_function",
157 "numeric_value_function": ["numeric_function", "geometry_function"],
158 "geometry_value_expression": "function_call",
159 "geometry_value_function": "geometry_function",
160 "predicate_geometry_function": "geometry_function",
161 "non_predicate_geometry_function": "geometry_function",
162 "numeric_geometry_function": "geometry_function",
163 "user_defined_function_name": "correlated_name",
164 "user_defined_function_param": "value_expression",
165 "in_predicate_value": "in_predicate_value",
166 "with_query": "with_query",
167 "comment": "COMMENT_TERM",
168 "comment_character": "COMMENT_TERM",
169 "comment_introducer": "COMMENT_TERM",
170 "concatenation": "concat",
171 "concatenation_operator": "concat",
172 "coordinate1": "coordinates",
173 "coordinate2": "coordinates",
174 "exact_numeric_type": "EXACT_NUMERIC_KW",
175 "approximate_numeric_type": ["REAL_KW", "DOUBLE_KW"],
176}
178# Pure lexer/character-level plumbing that a Lark grammar legitimately never
179# needs as separate named rules (see module docstring).
180LEXER_LEVEL_NOT_APPLICABLE = {
181 "nondelimiter_token",
182 "delimiter_token",
183 "token",
184 "nondoublequote_character",
185 "nonquote_character",
186 "newline",
187 "space",
188 "separator",
189 "simple_Latin_letter",
190 "simple_Latin_upper_case_letter",
191 "simple_Latin_lower_case_letter",
192 "quote_symbol",
193 "double_quote_symbol",
194 "delimited_identifier_body",
195 "delimited_identifier_part",
196 "character_representation",
197 "default_function_prefix",
198 "ADQL_language_character",
199 "ADQL_reserved_word",
200 "SQL_embedded_language_character",
201 "SQL_reserved_word",
202 "SQL_special_character",
203 "digit",
204 # <double_period> (..) is defined in the token catalog but not actually
205 # referenced by any active production in Annex A -- a vestige of the
206 # SQL92-derived lexer alphabet, not a real ADQL construct.
207 "double_period",
208}
211def extract_lark_names(path: Path) -> set:
212 """Return every rule name and `-> alias` name defined in a .lark file
213 (comments stripped first). This is the Lark side of the comparison."""
214 text = path.read_text(encoding="utf-8")
215 no_comments = re.sub(r"//.*", "", text)
216 names = set(
217 re.findall(
218 r"^\??([a-zA-Z_][a-zA-Z0-9_]*)(?:\.-?\d+)?\s*:", no_comments, re.MULTILINE
219 )
220 )
221 names |= set(re.findall(r"->\s*([a-zA-Z_][a-zA-Z0-9_]*)", no_comments))
222 return names
225def extract_bnf_definitions(bnf_text: str) -> set:
226 """Return every nonterminal name defined (`<name> ::= ...`) anywhere in
227 a BNF text. This is the Annex A side of the comparison."""
228 return {
229 n.strip()
230 for n in re.findall(
231 r"^\s*<([A-Za-z_][A-Za-z0-9_ ]*)>\s*::=", bnf_text, re.MULTILINE
232 )
233 }
236def find_punctuation_like(bnf_text: str, bnf_defined: set) -> set:
237 """Return the subset of `bnf_defined` whose own definition is a single
238 short literal char/operator with no nested <...> (e.g. `<comma> ::= ,`
239 or `<left_paren> ::= (`) -- these are written as inline string literals
240 in Lark, never as their own named rule, so they don't count as a
241 coverage gap."""
242 punctuation_like = set()
243 for nt in bnf_defined:
244 m = re.search(
245 rf"<{re.escape(nt)}>\s*::=\s*(.*?)(?=\n\s*<[A-Za-z_]|\Z)",
246 bnf_text,
247 re.DOTALL,
248 )
249 if m and len(m.group(1).strip()) <= 3 and "<" not in m.group(1):
250 punctuation_like.add(nt)
251 return punctuation_like
254def is_covered(nt: str, lark_defined_lower: set, aliases: dict = ALIASES) -> bool:
255 """True if BNF nonterminal `nt` has a same-named or aliased match in
256 `lark_defined_lower` (a lowercased set of Lark rule/alias names, as
257 produced by extract_lark_names)."""
258 if nt.lower() in lark_defined_lower:
259 return True
260 alias = aliases.get(nt, aliases.get(nt.replace(" ", "_")))
261 if alias is None:
262 return False
263 candidates = alias if isinstance(alias, list) else [alias]
264 return any(c.lower() in lark_defined_lower for c in candidates)
267def load_lark_defined_names() -> set:
268 """Union of extract_lark_names(...) over every file in GRAMMAR_FILES."""
269 names = set()
270 for fname in GRAMMAR_FILES:
271 names |= extract_lark_names(_GRAMMAR_DIR / fname)
272 return names
275def main():
276 bnf_text = BNF_PATH.read_text(encoding="utf-8")
277 bnf_defined = extract_bnf_definitions(bnf_text)
278 punctuation_like = find_punctuation_like(bnf_text, bnf_defined)
279 structural_bnf = bnf_defined - punctuation_like
281 lark_defined = load_lark_defined_names()
282 lark_defined_lower = {r.lower() for r in lark_defined}
284 missing = sorted(
285 nt
286 for nt in structural_bnf
287 if nt not in LEXER_LEVEL_NOT_APPLICABLE
288 and not is_covered(nt, lark_defined_lower)
289 )
291 print(f"Annex A 2.1 nonterminals (total) : {len(bnf_defined)}")
292 print(f" .. pure punctuation/character literals : {len(punctuation_like)}")
293 print(
294 f" .. pure lexer bookkeeping (token/space/..): {len(LEXER_LEVEL_NOT_APPLICABLE)}"
295 )
296 print(f" .. structural nonterminals checked : {len(structural_bnf)}")
297 print(f"Rules/aliases/terminals defined in grammar/*.lark : {len(lark_defined)}")
298 print()
299 if missing:
300 print(
301 f"=== Structural Annex A nonterminals with NO coverage found ({len(missing)}) ==="
302 )
303 for nt in missing:
304 print(" -", nt)
305 print()
306 print("Each of these is either a further lexical decomposition folded into a")
307 print("single regex terminal, or a deliberate structural simplification -- see")
308 print("this script's module docstring and the [AnnexA #x] comments in")
309 print("grammar/core.lark. None of them indicate a missing ADQL construct as of")
310 print("the last manual review.")
311 else:
312 print("All structural Annex A nonterminals are covered.")
315if __name__ == "__main__":
316 main()