8172376451

Committed 06 Mar 2024 12:52PM UTC coverage: 72.671% (+1.7%) from 70.936%

Build # 8172376451

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #28 from martineberlein/stable

Stable

Run Details

376 of 465 new or added lines in 22 files covered. (80.86%)

3 existing lines in 1 file now uncovered.

1646 of 2265 relevant lines covered (72.67%)

0.73 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

89.29

/src/debugging_framework/grammar.py

import sys
import re
import copy
from typing import Set, Optional, Tuple, Dict, Any, cast, Union, List

from isla.derivation_tree import DerivationTree
from debugging_framework.types import (
    Grammar,
    Expansion,
    START_SYMBOL,
    RE_NONTERMINAL,
    Option,
)


def is_valid_grammar(
    grammar: Grammar, start_symbol: str = START_SYMBOL, supported_opts: Set[str] = set()
) -> bool:
    """Check if the given `grammar` is valid.
    `start_symbol`: optional start symbol (default: `<start>`)
    `supported_opts`: options supported (default: none)"""

    defined_nonterminals, used_nonterminals = def_used_nonterminals(
        grammar, start_symbol
    )
    if defined_nonterminals is None or used_nonterminals is None:
        return False

    # Do not complain about '<start>' being not used,
    # even if start_symbol is different
    # TODO: eigentlich überflüssig, da das schon in def_used_nonterminals passiert
    if START_SYMBOL in grammar:
        used_nonterminals.add(START_SYMBOL)

    for unused_nonterminal in defined_nonterminals - used_nonterminals:
        print(repr(unused_nonterminal) + ": defined, but not used", file=sys.stderr)
    for undefined_nonterminal in used_nonterminals - defined_nonterminals:
        print(repr(undefined_nonterminal) + ": used, but not defined", file=sys.stderr)

    # Symbols must be reachable either from <start> or given start symbol
    unreachable = unreachable_nonterminals(grammar, start_symbol)
    msg_start_symbol = start_symbol

    if START_SYMBOL in grammar:
        unreachable = unreachable - reachable_nonterminals(grammar, START_SYMBOL)
        if start_symbol != START_SYMBOL:
            msg_start_symbol += " or " + START_SYMBOL

    for unreachable_nonterminal in unreachable:
        print(
            repr(unreachable_nonterminal) + ": unreachable from " + msg_start_symbol,
            file=sys.stderr,
        )

    used_but_not_supported_opts = set()
    if len(supported_opts) > 0:
        used_but_not_supported_opts = opts_used(grammar).difference(supported_opts)
        for opt in used_but_not_supported_opts:
            print("warning: option " + repr(opt) + " is not supported", file=sys.stderr)

    return used_nonterminals == defined_nonterminals and len(unreachable) == 0


def def_used_nonterminals(
    grammar: Grammar, start_symbol: str = START_SYMBOL
) -> Tuple[Optional[Set[str]], Optional[Set[str]]]:
    """Return a pair (`defined_nonterminals`, `used_nonterminals`) in `grammar`.
    In case of error, return (`None`, `None`)."""

    defined_nonterminals = set()
    used_nonterminals = {start_symbol}

    for defined_nonterminal in grammar:
        defined_nonterminals.add(defined_nonterminal)
        expansions = grammar[defined_nonterminal]
        if not isinstance(expansions, list):
            print(
                repr(defined_nonterminal) + ": expansion is not a list", file=sys.stderr
            )
            return None, None

        if len(expansions) == 0:
            print(repr(defined_nonterminal) + ": expansion list empty", file=sys.stderr)
            return None, None

        for expansion in expansions:
            if isinstance(expansion, tuple):
                expansion = expansion[0]
            if not isinstance(expansion, str):
                print(
                    repr(defined_nonterminal)
                    + ": "
                    + repr(expansion)
                    + ": not a string",
                    file=sys.stderr,
                )
                return None, None

            for used_nonterminal in nonterminals(expansion):
                used_nonterminals.add(used_nonterminal)

    return defined_nonterminals, used_nonterminals


def reachable_nonterminals(
    grammar: Grammar, start_symbol: str = START_SYMBOL
) -> Set[str]:
    reachable = set()

    def _find_reachable_nonterminals(grammar, symbol):
        nonlocal reachable
        reachable.add(symbol)
        for expansion in grammar.get(symbol, []):
            for nonterminal in nonterminals(expansion):
                if nonterminal not in reachable:
                    _find_reachable_nonterminals(grammar, nonterminal)

    _find_reachable_nonterminals(grammar, start_symbol)
    return reachable


def unreachable_nonterminals(grammar: Grammar, start_symbol=START_SYMBOL) -> Set[str]:
    return grammar.keys() - reachable_nonterminals(grammar, start_symbol)


def nonterminals(expansion: str):
    # In later chapters, we allow expansions to be tuples,
    # with the expansion being the first element
    if isinstance(expansion, tuple):
        expansion = expansion[0]

    return RE_NONTERMINAL.findall(expansion)


def is_nonterminal(s):
    return RE_NONTERMINAL.match(s)


def opts_used(grammar: Grammar) -> Set[str]:
    used_opts = set()
    for symbol in grammar:
        for expansion in grammar[symbol]:
            # |= in place or
            # https://stackoverflow.com/questions/3929278/what-does-ior-do-in-python
            used_opts |= set(exp_opts(expansion).keys())
    return used_opts


def exp_opts(expansion: Expansion) -> Dict[str, Any]:
    """Return the options of an expansion.  If options are not defined, return {}"""
    if isinstance(expansion, str):
        return {}
    return expansion[1]


def is_valid_probabilistic_grammar(
    grammar: Grammar, start_symbol: str = START_SYMBOL
) -> bool:
    if not is_valid_grammar(grammar, start_symbol):
        return False

    for nonterminal in grammar:
        expansions = grammar[nonterminal]
        _ = exp_probabilities(expansions, nonterminal)

    return True


def exp_probabilities(
    expansions: List[Expansion], nonterminal: str = "<symbol>"
) -> Dict[Expansion, float]:
    probabilities = [exp_prob(expansion) for expansion in expansions]
    prob_dist = prob_distribution(probabilities, nonterminal)  # type: ignore

    prob_mapping: Dict[Expansion, float] = {}
    for i in range(len(expansions)):
        expansion = exp_string(expansions[i])
        prob_mapping[expansion] = prob_dist[i]

    return prob_mapping


def all_terminals(tree: DerivationTree) -> str:
    (symbol, children) = tree
    if children is None:
        # This is a nonterminal symbol not expanded yet
        return symbol

    if len(children) == 0:
        # This is a terminal symbol
        return symbol

    # This is an expanded symbol:
    # Concatenate all terminal symbols from all children
    return "".join([all_terminals(c) for c in children])


def extend_grammar(grammar: Grammar, extension: Grammar = {}) -> Grammar:
    new_grammar = copy.deepcopy(grammar)
    new_grammar.update(extension)
    return new_grammar


def expansion_key(
    symbol: str,
    expansion: Union[Expansion, Tuple[str, Optional[List[Any]]], List[DerivationTree]],
) -> str:
    """Convert (symbol, `expansion`) into a key "SYMBOL -> EXPRESSION".
    `expansion` can be an expansion string, a derivation tree,
       or a list of derivation trees."""

    if isinstance(expansion, tuple):
        # Expansion or single derivation tree
        expansion, _ = expansion

    # Check for empty list expansion
    if isinstance(expansion, list) and not expansion:
        expansion = ""

    if not isinstance(expansion, str):
        # Derivation tree
        children = expansion
        expansion = all_terminals((symbol, children))

    assert isinstance(expansion, str)

    return symbol + " -> " + expansion


def set_prob(
    grammar: Grammar, symbol: str, expansion: Expansion, prob: Optional[float]
) -> None:
    """Set the probability of the given expansion of grammar[symbol]"""
    set_opts(grammar, symbol, expansion, opts(prob=prob))


def set_opts(
    grammar: Grammar, symbol: str, expansion: Expansion, opts: Option = {}
) -> None:
    """Set the options of the given expansion of grammar[symbol] to opts"""
    expansions = grammar[symbol]
    for i, exp in enumerate(expansions):
        if exp_string(exp) != exp_string(expansion):
            continue

        new_opts = exp_opts(exp)
        if opts == {} or new_opts == {}:
            new_opts = opts
        else:
            for key in opts:
                new_opts[key] = opts[key]

        if new_opts == {}:
            grammar[symbol][i] = exp_string(exp)
        else:
            grammar[symbol][i] = (exp_string(exp), new_opts)

        return


def opts(**kwargs: Any) -> Dict[str, Any]:
    return kwargs


def exp_prob(expansion: Expansion) -> float:
    """Return the options of an expansion"""
    return exp_opt(expansion, "prob")


def exp_opt(expansion: Expansion, attribute: str) -> Any:
    """Return the given attribution of an expansion.
    If attribute is not defined, return None"""
    return exp_opts(expansion).get(attribute, None)


def prob_distribution(
    probabilities: List[Optional[float]], nonterminal: str = "<symbol>"
):
    epsilon = 0.00001

    number_of_unspecified_probabilities = probabilities.count(None)
    if number_of_unspecified_probabilities == 0:
        sum_probabilities = cast(float, sum(probabilities))
        assert abs(sum_probabilities - 1.0) < epsilon, (
            nonterminal + ": sum of probabilities must be 1.0"
        )
        return probabilities

    sum_of_specified_probabilities = 0.0
    for p in probabilities:
        if p is not None:
            sum_of_specified_probabilities += p
    assert 0 <= sum_of_specified_probabilities <= 1.0, (
        nonterminal + ": sum of specified probabilities must be between 0.0 and 1.0"
    )

    default_probability = (
        1.0 - sum_of_specified_probabilities
    ) / number_of_unspecified_probabilities
    all_probabilities = []
    for p in probabilities:
        if p is None:
            p = default_probability
        all_probabilities.append(p)

    assert abs(sum(all_probabilities) - 1.0) < epsilon
    return all_probabilities


def exp_string(expansion: Expansion) -> str:
    """Return the string to be expanded"""
    if isinstance(expansion, str):
        return expansion
    return expansion[0]


def expansion_to_children(expansion: Expansion) -> List[DerivationTree]:
    # print("Converting " + repr(expansion))
    # strings contains all substrings -- both terminals and nonterminals such
    # that ''.join(strings) == expansion

    expansion = exp_string(expansion)
    assert isinstance(expansion, str)

    if expansion == "":  # Special case: epsilon expansion
        return [("", [])]

    strings = re.split(RE_NONTERMINAL, expansion)
    return [(s, None) if is_nonterminal(s) else (s, []) for s in strings if len(s) > 0]

1	import sys	1✔
2	import re	1✔
3	import copy	1✔
4	from typing import Set, Optional, Tuple, Dict, Any, cast, Union, List	1✔
5
6	from isla.derivation_tree import DerivationTree	1✔
7	from debugging_framework.types import (	1✔
8	Grammar,
9	Expansion,
10	START_SYMBOL,
11	RE_NONTERMINAL,
12	Option,
13	)
14
15
16	def is_valid_grammar(	1✔
17	grammar: Grammar, start_symbol: str = START_SYMBOL, supported_opts: Set[str] = set()
18	) -> bool:
19	"""Check if the given `grammar` is valid.
20	`start_symbol`: optional start symbol (default: `<start>`)
21	`supported_opts`: options supported (default: none)"""
22
23	defined_nonterminals, used_nonterminals = def_used_nonterminals(	1✔
24	grammar, start_symbol
25	)
26	if defined_nonterminals is None or used_nonterminals is None:	1✔
NEW 27	return False	×
28
29	# Do not complain about '<start>' being not used,
30	# even if start_symbol is different
31	# TODO: eigentlich überflüssig, da das schon in def_used_nonterminals passiert
32	if START_SYMBOL in grammar:	1✔
33	used_nonterminals.add(START_SYMBOL)	1✔
34
35	for unused_nonterminal in defined_nonterminals - used_nonterminals:	1✔
36	print(repr(unused_nonterminal) + ": defined, but not used", file=sys.stderr)	1✔
37	for undefined_nonterminal in used_nonterminals - defined_nonterminals:	1✔
38	print(repr(undefined_nonterminal) + ": used, but not defined", file=sys.stderr)	1✔
39
40	# Symbols must be reachable either from <start> or given start symbol
41	unreachable = unreachable_nonterminals(grammar, start_symbol)	1✔
42	msg_start_symbol = start_symbol	1✔
43
44	if START_SYMBOL in grammar:	1✔
45	unreachable = unreachable - reachable_nonterminals(grammar, START_SYMBOL)	1✔
46	if start_symbol != START_SYMBOL:	1✔
NEW 47	msg_start_symbol += " or " + START_SYMBOL	×
48
49	for unreachable_nonterminal in unreachable:	1✔
50	print(	1✔
51	repr(unreachable_nonterminal) + ": unreachable from " + msg_start_symbol,
52	file=sys.stderr,
53	)
54
55	used_but_not_supported_opts = set()	1✔
56	if len(supported_opts) > 0:	1✔
NEW 57	used_but_not_supported_opts = opts_used(grammar).difference(supported_opts)	×
NEW 58	for opt in used_but_not_supported_opts:	×
NEW 59	print("warning: option " + repr(opt) + " is not supported", file=sys.stderr)	×
60
61	return used_nonterminals == defined_nonterminals and len(unreachable) == 0	1✔
62
63
64	def def_used_nonterminals(	1✔
65	grammar: Grammar, start_symbol: str = START_SYMBOL
66	) -> Tuple[Optional[Set[str]], Optional[Set[str]]]:
67	"""Return a pair (`defined_nonterminals`, `used_nonterminals`) in `grammar`.
68	In case of error, return (`None`, `None`)."""
69
70	defined_nonterminals = set()	1✔
71	used_nonterminals = {start_symbol}	1✔
72
73	for defined_nonterminal in grammar:	1✔
74	defined_nonterminals.add(defined_nonterminal)	1✔
75	expansions = grammar[defined_nonterminal]	1✔
76	if not isinstance(expansions, list):	1✔
77	print(	1✔
78	repr(defined_nonterminal) + ": expansion is not a list", file=sys.stderr
79	)
80	return None, None	1✔
81
82	if len(expansions) == 0:	1✔
83	print(repr(defined_nonterminal) + ": expansion list empty", file=sys.stderr)	1✔
84	return None, None	1✔
85
86	for expansion in expansions:	1✔
87	if isinstance(expansion, tuple):	1✔
88	expansion = expansion[0]	1✔
89	if not isinstance(expansion, str):	1✔
NEW 90	print(	×
91	repr(defined_nonterminal)
92	+ ": "
93	+ repr(expansion)
94	+ ": not a string",
95	file=sys.stderr,
96	)
NEW 97	return None, None	×
98
99	for used_nonterminal in nonterminals(expansion):	1✔
100	used_nonterminals.add(used_nonterminal)	1✔
101
102	return defined_nonterminals, used_nonterminals	1✔
103
104
105	def reachable_nonterminals(	1✔
106	grammar: Grammar, start_symbol: str = START_SYMBOL
107	) -> Set[str]:
108	reachable = set()	1✔
109
110	def _find_reachable_nonterminals(grammar, symbol):	1✔
111	nonlocal reachable
112	reachable.add(symbol)	1✔
113	for expansion in grammar.get(symbol, []):	1✔
114	for nonterminal in nonterminals(expansion):	1✔
115	if nonterminal not in reachable:	1✔
116	_find_reachable_nonterminals(grammar, nonterminal)	1✔
117
118	_find_reachable_nonterminals(grammar, start_symbol)	1✔
119	return reachable	1✔
120
121
122	def unreachable_nonterminals(grammar: Grammar, start_symbol=START_SYMBOL) -> Set[str]:	1✔
123	return grammar.keys() - reachable_nonterminals(grammar, start_symbol)	1✔
124
125
126	def nonterminals(expansion: str):	1✔
127	# In later chapters, we allow expansions to be tuples,
128	# with the expansion being the first element
129	if isinstance(expansion, tuple):	1✔
130	expansion = expansion[0]	1✔
131
132	return RE_NONTERMINAL.findall(expansion)	1✔
133
134
135	def is_nonterminal(s):	1✔
136	return RE_NONTERMINAL.match(s)	1✔
137
138
139	def opts_used(grammar: Grammar) -> Set[str]:	1✔
140	used_opts = set()	1✔
141	for symbol in grammar:	1✔
142	for expansion in grammar[symbol]:	1✔
143	# \|= in place or
144	# https://stackoverflow.com/questions/3929278/what-does-ior-do-in-python
145	used_opts \|= set(exp_opts(expansion).keys())	1✔
146	return used_opts	1✔
147
148
149	def exp_opts(expansion: Expansion) -> Dict[str, Any]:	1✔
150	"""Return the options of an expansion. If options are not defined, return {}"""
151	if isinstance(expansion, str):	1✔
152	return {}	1✔
153	return expansion[1]	1✔
154
155
156	def is_valid_probabilistic_grammar(	1✔
157	grammar: Grammar, start_symbol: str = START_SYMBOL
158	) -> bool:
NEW 159	if not is_valid_grammar(grammar, start_symbol):	×
NEW 160	return False	×
161
NEW 162	for nonterminal in grammar:	×
NEW 163	expansions = grammar[nonterminal]	×
NEW 164	_ = exp_probabilities(expansions, nonterminal)	×
165
NEW 166	return True	×
167
168
169	def exp_probabilities(	1✔
170	expansions: List[Expansion], nonterminal: str = "<symbol>"
171	) -> Dict[Expansion, float]:
172	probabilities = [exp_prob(expansion) for expansion in expansions]	1✔
173	prob_dist = prob_distribution(probabilities, nonterminal) # type: ignore	1✔
174
175	prob_mapping: Dict[Expansion, float] = {}	1✔
176	for i in range(len(expansions)):	1✔
177	expansion = exp_string(expansions[i])	1✔
178	prob_mapping[expansion] = prob_dist[i]	1✔
179
180	return prob_mapping	1✔
181
182
183	def all_terminals(tree: DerivationTree) -> str:	1✔
184	(symbol, children) = tree	1✔
185	if children is None:	1✔
186	# This is a nonterminal symbol not expanded yet
187	return symbol	1✔
188
189	if len(children) == 0:	1✔
190	# This is a terminal symbol
191	return symbol	1✔
192
193	# This is an expanded symbol:
194	# Concatenate all terminal symbols from all children
195	return "".join([all_terminals(c) for c in children])	1✔
196
197
198	def extend_grammar(grammar: Grammar, extension: Grammar = {}) -> Grammar:	1✔
199	new_grammar = copy.deepcopy(grammar)	1✔
200	new_grammar.update(extension)	1✔
201	return new_grammar	1✔
202
203
204	def expansion_key(	1✔
205	symbol: str,
206	expansion: Union[Expansion, Tuple[str, Optional[List[Any]]], List[DerivationTree]],
207	) -> str:
208	"""Convert (symbol, `expansion`) into a key "SYMBOL -> EXPRESSION".
209	`expansion` can be an expansion string, a derivation tree,
210	or a list of derivation trees."""
211
212	if isinstance(expansion, tuple):	1✔
213	# Expansion or single derivation tree
NEW 214	expansion, _ = expansion	×
215
216	# Check for empty list expansion
217	if isinstance(expansion, list) and not expansion:	1✔
218	expansion = ""	1✔
219
220	if not isinstance(expansion, str):	1✔
221	# Derivation tree
222	children = expansion	1✔
223	expansion = all_terminals((symbol, children))	1✔
224
225	assert isinstance(expansion, str)	1✔
226
227	return symbol + " -> " + expansion	1✔
228
229
230	def set_prob(	1✔
231	grammar: Grammar, symbol: str, expansion: Expansion, prob: Optional[float]
232	) -> None:
233	"""Set the probability of the given expansion of grammar[symbol]"""
234	set_opts(grammar, symbol, expansion, opts(prob=prob))	1✔
235
236
237	def set_opts(	1✔
238	grammar: Grammar, symbol: str, expansion: Expansion, opts: Option = {}
239	) -> None:
240	"""Set the options of the given expansion of grammar[symbol] to opts"""
241	expansions = grammar[symbol]	1✔
242	for i, exp in enumerate(expansions):	1✔
243	if exp_string(exp) != exp_string(expansion):	1✔
244	continue	1✔
245
246	new_opts = exp_opts(exp)	1✔
247	if opts == {} or new_opts == {}:	1✔
248	new_opts = opts	1✔
249	else:
NEW 250	for key in opts:	×
NEW 251	new_opts[key] = opts[key]	×
252
253	if new_opts == {}:	1✔
NEW 254	grammar[symbol][i] = exp_string(exp)	×
255	else:
256	grammar[symbol][i] = (exp_string(exp), new_opts)	1✔
257
258	return	1✔
259
260
261	def opts(**kwargs: Any) -> Dict[str, Any]:	1✔
262	return kwargs	1✔
263
264
265	def exp_prob(expansion: Expansion) -> float:	1✔
266	"""Return the options of an expansion"""
267	return exp_opt(expansion, "prob")	1✔
268
269
270	def exp_opt(expansion: Expansion, attribute: str) -> Any:	1✔
271	"""Return the given attribution of an expansion.
272	If attribute is not defined, return None"""
273	return exp_opts(expansion).get(attribute, None)	1✔
274
275
276	def prob_distribution(	1✔
277	probabilities: List[Optional[float]], nonterminal: str = "<symbol>"
278	):
279	epsilon = 0.00001	1✔
280
281	number_of_unspecified_probabilities = probabilities.count(None)	1✔
282	if number_of_unspecified_probabilities == 0:	1✔
283	sum_probabilities = cast(float, sum(probabilities))	1✔
284	assert abs(sum_probabilities - 1.0) < epsilon, (	1✔
285	nonterminal + ": sum of probabilities must be 1.0"
286	)
287	return probabilities	1✔
288
289	sum_of_specified_probabilities = 0.0	1✔
290	for p in probabilities:	1✔
291	if p is not None:	1✔
NEW 292	sum_of_specified_probabilities += p	×
293	assert 0 <= sum_of_specified_probabilities <= 1.0, (	1✔
294	nonterminal + ": sum of specified probabilities must be between 0.0 and 1.0"
295	)
296
297	default_probability = (	1✔
298	1.0 - sum_of_specified_probabilities
299	) / number_of_unspecified_probabilities
300	all_probabilities = []	1✔
301	for p in probabilities:	1✔
302	if p is None:	1✔
303	p = default_probability	1✔
304	all_probabilities.append(p)	1✔
305
306	assert abs(sum(all_probabilities) - 1.0) < epsilon	1✔
307	return all_probabilities	1✔
308
309
310	def exp_string(expansion: Expansion) -> str:	1✔
311	"""Return the string to be expanded"""
312	if isinstance(expansion, str):	1✔
313	return expansion	1✔
314	return expansion[0]	1✔
315
316
317	def expansion_to_children(expansion: Expansion) -> List[DerivationTree]:	1✔
318	# print("Converting " + repr(expansion))
319	# strings contains all substrings -- both terminals and nonterminals such
320	# that ''.join(strings) == expansion
321
322	expansion = exp_string(expansion)	1✔
323	assert isinstance(expansion, str)	1✔
324
325	if expansion == "": # Special case: epsilon expansion	1✔
326	return [("", [])]	1✔
327
328	strings = re.split(RE_NONTERMINAL, expansion)	1✔
329	return [(s, None) if is_nonterminal(s) else (s, []) for s in strings if len(s) > 0]	1✔

martineberlein / debugging-benchmark / 8172376451

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous