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

92.0

/src/debugging_framework/grammar_fuzzer.py

from typing import Optional, List, Callable, Set, Union
import random

from isla.derivation_tree import DerivationTree
from debugging_framework.types import Grammar, Expansion, START_SYMBOL

from debugging_framework.grammar import (
    is_valid_grammar,
    expansion_to_children,
    nonterminals,
    all_terminals,
)


class Fuzzer:
    """Base class for fuzzers."""

    def __init__(self) -> None:
        pass

    def fuzz(self) -> str:
        """Return fuzz input"""
        return ""

    def run(self):
        """Return fuzz"""
        return self.fuzz()


class GrammarFuzzer(Fuzzer):
    """Produce strings from grammars efficiently, using derivation trees."""

    def __init__(
        self,
        grammar: Grammar,
        start_symbol: str = START_SYMBOL,
        min_nonterminals: int = 0,
        max_nonterminals: int = 10,
        disp: bool = False,
        log: Union[bool, int] = False,
    ) -> None:
        """Produce strings from `grammar`, starting with `start_symbol`.
        If `min_nonterminals` or `max_nonterminals` is given, use them as limits
        for the number of nonterminals produced.
        If `disp` is set, display the intermediate derivation trees.
        If `log` is set, show intermediate steps as text on standard output."""

        self.grammar = grammar
        self.start_symbol = start_symbol
        self.min_nonterminals = min_nonterminals
        self.max_nonterminals = max_nonterminals
        self.disp = disp
        self.log = log
        self.check_grammar()  # Invokes is_valid_grammar()

    def check_grammar(self) -> None:
        """Check the grammar passed"""
        assert self.start_symbol in self.grammar
        assert is_valid_grammar(
            self.grammar,
            start_symbol=self.start_symbol,
            supported_opts=self.supported_opts(),
        )

    def supported_opts(self) -> Set[str]:
        """Set of supported options. To be overloaded in subclasses."""
        return set()  # We don't support specific options

    def init_tree(self) -> DerivationTree:
        return (self.start_symbol, None)

    def choose_node_expansion(
        self, node: DerivationTree, children_alternatives: List[List[DerivationTree]]
    ) -> int:
        """Return index of expansion in `children_alternatives` to be selected.
        'children_alternatives`: a list of possible children for `node`.
        Defaults to random. To be overloaded in subclasses."""
        return random.randrange(0, len(children_alternatives))

    def expansion_to_children(self, expansion: Expansion) -> List[DerivationTree]:
        return expansion_to_children(expansion)

    def expand_node_randomly(self, node: DerivationTree) -> DerivationTree:
        """Choose a random expansion for `node` and return it"""
        (symbol, children) = node
        assert children is None

        if self.log:
            print("Expanding", all_terminals(node), "randomly")

        # Fetch the possible expansions from grammar...
        expansions = self.grammar[symbol]
        children_alternatives: List[List[DerivationTree]] = [
            self.expansion_to_children(expansion) for expansion in expansions
        ]

        # ... and select a random expansion
        index = self.choose_node_expansion(node, children_alternatives)
        chosen_children = children_alternatives[index]

        # Process children (for subclasses)
        chosen_children = self.process_chosen_children(
            chosen_children, expansions[index]
        )

        # Return with new children
        return (symbol, chosen_children)

    def process_chosen_children(
        self, chosen_children: List[DerivationTree], expansion: Expansion
    ) -> List[DerivationTree]:
        """Process children after selection.  By default, does nothing."""
        return chosen_children

    def possible_expansions(self, node: DerivationTree) -> int:
        (symbol, children) = node
        if children is None:
            return 1

        return sum(self.possible_expansions(c) for c in children)

    def any_possible_expansions(self, node: DerivationTree) -> bool:
        (symbol, children) = node
        if children is None:
            return True

        return any(self.any_possible_expansions(c) for c in children)

    def choose_tree_expansion(
        self, tree: DerivationTree, children: List[DerivationTree]
    ) -> int:
        """Return index of subtree in `children` to be selected for expansion.
        Defaults to random."""
        return random.randrange(0, len(children))

    def expand_tree_once(self, tree: DerivationTree) -> DerivationTree:
        """Choose an unexpanded symbol in tree; expand it.
        Can be overloaded in subclasses."""
        (symbol, children) = tree
        if children is None:
            # Expand this node
            return self.expand_node(tree)

        # Find all children with possible expansions
        expandable_children = [c for c in children if self.any_possible_expansions(c)]

        # `index_map` translates an index in `expandable_children`
        # back into the original index in `children`
        index_map = [i for (i, c) in enumerate(children) if c in expandable_children]

        # Select a random child
        child_to_be_expanded = self.choose_tree_expansion(tree, expandable_children)

        # Expand in place
        children[index_map[child_to_be_expanded]] = self.expand_tree_once(
            expandable_children[child_to_be_expanded]
        )

        return tree

    def symbol_cost(self, symbol: str, seen: Set[str] = set()) -> Union[int, float]:
        expansions = self.grammar[symbol]
        return min(self.expansion_cost(e, seen | {symbol}) for e in expansions)

    def expansion_cost(
        self, expansion: Expansion, seen: Set[str] = set()
    ) -> Union[int, float]:
        symbols = nonterminals(expansion)
        if len(symbols) == 0:
            return 1  # no symbol

        if any(s in seen for s in symbols):
            return float("inf")

        # the value of a expansion is the sum of all expandable variables
        # inside + 1
        return sum(self.symbol_cost(s, seen) for s in symbols) + 1

    def expand_node_by_cost(
        self, node: DerivationTree, choose: Callable = min
    ) -> DerivationTree:
        (symbol, children) = node
        assert children is None

        # Fetch the possible expansions from grammar...
        expansions = self.grammar[symbol]

        children_alternatives_with_cost = [
            (
                self.expansion_to_children(expansion),
                self.expansion_cost(expansion, {symbol}),
                expansion,
            )
            for expansion in expansions
        ]

        costs = [cost for (child, cost, expansion) in children_alternatives_with_cost]
        chosen_cost = choose(costs)
        children_with_chosen_cost = [
            child
            for (child, child_cost, _) in children_alternatives_with_cost
            if child_cost == chosen_cost
        ]
        expansion_with_chosen_cost = [
            expansion
            for (_, child_cost, expansion) in children_alternatives_with_cost
            if child_cost == chosen_cost
        ]

        index = self.choose_node_expansion(node, children_with_chosen_cost)

        chosen_children = children_with_chosen_cost[index]
        chosen_expansion = expansion_with_chosen_cost[index]
        chosen_children = self.process_chosen_children(
            chosen_children, chosen_expansion
        )

        # Return with a new list
        return (symbol, chosen_children)

    def expand_node_min_cost(self, node: DerivationTree) -> DerivationTree:
        if self.log:
            print("Expanding", all_terminals(node), "at minimum cost")

        return self.expand_node_by_cost(node, min)

    def expand_node_max_cost(self, node: DerivationTree) -> DerivationTree:
        if self.log:
            print("Expanding", all_terminals(node), "at maximum cost")

        return self.expand_node_by_cost(node, max)

    def log_tree(self, tree: DerivationTree) -> None:
        """Output a tree if self.log is set"""
        if self.log:
            print("Tree:", all_terminals(tree))
            # print(self.possible_expansions(tree), "possible expansion(s) left")

    def expand_tree_with_strategy(
        self,
        tree: DerivationTree,
        expand_node_method: Callable,
        limit: Optional[int] = None,
    ):
        """Expand tree using `expand_node_method` as node expansion function
        until the number of possible expansions reaches `limit`."""
        self.expand_node = expand_node_method  # type: ignore
        while (
            limit is None or self.possible_expansions(tree) < limit
        ) and self.any_possible_expansions(tree):
            tree = self.expand_tree_once(tree)
            self.log_tree(tree)
        return tree

    def expand_tree(self, tree: DerivationTree) -> DerivationTree:
        """Expand `tree` in a three-phase strategy until all expansions are complete."""
        self.log_tree(tree)
        tree = self.expand_tree_with_strategy(
            tree, self.expand_node_max_cost, self.min_nonterminals
        )
        tree = self.expand_tree_with_strategy(
            tree, self.expand_node_randomly, self.max_nonterminals
        )
        tree = self.expand_tree_with_strategy(tree, self.expand_node_min_cost)

        assert self.possible_expansions(tree) == 0

        return tree

    def fuzz_tree(self) -> DerivationTree:
        """Produce a derivation tree from the grammar."""
        tree = self.init_tree()
        # print(tree)

        # Expand all nonterminals
        tree = self.expand_tree(tree)
        if self.log:
            print(repr(all_terminals(tree)))

        return tree

    def fuzz(self) -> str:
        """Produce a string from the grammar."""
        self.derivation_tree = self.fuzz_tree()
        return all_terminals(self.derivation_tree)

1	from typing import Optional, List, Callable, Set, Union	1✔
2	import random	1✔
3
4	from isla.derivation_tree import DerivationTree	1✔
5	from debugging_framework.types import Grammar, Expansion, START_SYMBOL	1✔
6
7	from debugging_framework.grammar import (	1✔
8	is_valid_grammar,
9	expansion_to_children,
10	nonterminals,
11	all_terminals,
12	)
13
14
15	class Fuzzer:	1✔
16	"""Base class for fuzzers."""	1✔
17
18	def __init__(self) -> None:	1✔
NEW 19	pass	×
20
21	def fuzz(self) -> str:	1✔
22	"""Return fuzz input"""
NEW 23	return ""	×
24
25	def run(self):	1✔
26	"""Return fuzz"""
NEW 27	return self.fuzz()	×
28
29
30	class GrammarFuzzer(Fuzzer):	1✔
31	"""Produce strings from grammars efficiently, using derivation trees."""	1✔
32
33	def __init__(	1✔
34	self,
35	grammar: Grammar,
36	start_symbol: str = START_SYMBOL,
37	min_nonterminals: int = 0,
38	max_nonterminals: int = 10,
39	disp: bool = False,
40	log: Union[bool, int] = False,
41	) -> None:
42	"""Produce strings from `grammar`, starting with `start_symbol`.
43	If `min_nonterminals` or `max_nonterminals` is given, use them as limits
44	for the number of nonterminals produced.
45	If `disp` is set, display the intermediate derivation trees.
46	If `log` is set, show intermediate steps as text on standard output."""
47
48	self.grammar = grammar	1✔
49	self.start_symbol = start_symbol	1✔
50	self.min_nonterminals = min_nonterminals	1✔
51	self.max_nonterminals = max_nonterminals	1✔
52	self.disp = disp	1✔
53	self.log = log	1✔
54	self.check_grammar() # Invokes is_valid_grammar()	1✔
55
56	def check_grammar(self) -> None:	1✔
57	"""Check the grammar passed"""
58	assert self.start_symbol in self.grammar	1✔
59	assert is_valid_grammar(	1✔
60	self.grammar,
61	start_symbol=self.start_symbol,
62	supported_opts=self.supported_opts(),
63	)
64
65	def supported_opts(self) -> Set[str]:	1✔
66	"""Set of supported options. To be overloaded in subclasses."""
67	return set() # We don't support specific options	1✔
68
69	def init_tree(self) -> DerivationTree:	1✔
70	return (self.start_symbol, None)	1✔
71
72	def choose_node_expansion(	1✔
73	self, node: DerivationTree, children_alternatives: List[List[DerivationTree]]
74	) -> int:
75	"""Return index of expansion in `children_alternatives` to be selected.
76	'children_alternatives`: a list of possible children for `node`.
77	Defaults to random. To be overloaded in subclasses."""
78	return random.randrange(0, len(children_alternatives))	1✔
79
80	def expansion_to_children(self, expansion: Expansion) -> List[DerivationTree]:	1✔
81	return expansion_to_children(expansion)	1✔
82
83	def expand_node_randomly(self, node: DerivationTree) -> DerivationTree:	1✔
84	"""Choose a random expansion for `node` and return it"""
85	(symbol, children) = node	1✔
86	assert children is None	1✔
87
88	if self.log:	1✔
NEW 89	print("Expanding", all_terminals(node), "randomly")	×
90
91	# Fetch the possible expansions from grammar...
92	expansions = self.grammar[symbol]	1✔
93	children_alternatives: List[List[DerivationTree]] = [	1✔
94	self.expansion_to_children(expansion) for expansion in expansions
95	]
96
97	# ... and select a random expansion
98	index = self.choose_node_expansion(node, children_alternatives)	1✔
99	chosen_children = children_alternatives[index]	1✔
100
101	# Process children (for subclasses)
102	chosen_children = self.process_chosen_children(	1✔
103	chosen_children, expansions[index]
104	)
105
106	# Return with new children
107	return (symbol, chosen_children)	1✔
108
109	def process_chosen_children(	1✔
110	self, chosen_children: List[DerivationTree], expansion: Expansion
111	) -> List[DerivationTree]:
112	"""Process children after selection. By default, does nothing."""
113	return chosen_children	1✔
114
115	def possible_expansions(self, node: DerivationTree) -> int:	1✔
116	(symbol, children) = node	1✔
117	if children is None:	1✔
118	return 1	1✔
119
120	return sum(self.possible_expansions(c) for c in children)	1✔
121
122	def any_possible_expansions(self, node: DerivationTree) -> bool:	1✔
123	(symbol, children) = node	1✔
124	if children is None:	1✔
125	return True	1✔
126
127	return any(self.any_possible_expansions(c) for c in children)	1✔
128
129	def choose_tree_expansion(	1✔
130	self, tree: DerivationTree, children: List[DerivationTree]
131	) -> int:
132	"""Return index of subtree in `children` to be selected for expansion.
133	Defaults to random."""
134	return random.randrange(0, len(children))	1✔
135
136	def expand_tree_once(self, tree: DerivationTree) -> DerivationTree:	1✔
137	"""Choose an unexpanded symbol in tree; expand it.
138	Can be overloaded in subclasses."""
139	(symbol, children) = tree	1✔
140	if children is None:	1✔
141	# Expand this node
142	return self.expand_node(tree)	1✔
143
144	# Find all children with possible expansions
145	expandable_children = [c for c in children if self.any_possible_expansions(c)]	1✔
146
147	# `index_map` translates an index in `expandable_children`
148	# back into the original index in `children`
149	index_map = [i for (i, c) in enumerate(children) if c in expandable_children]	1✔
150
151	# Select a random child
152	child_to_be_expanded = self.choose_tree_expansion(tree, expandable_children)	1✔
153
154	# Expand in place
155	children[index_map[child_to_be_expanded]] = self.expand_tree_once(	1✔
156	expandable_children[child_to_be_expanded]
157	)
158
159	return tree	1✔
160
161	def symbol_cost(self, symbol: str, seen: Set[str] = set()) -> Union[int, float]:	1✔
162	expansions = self.grammar[symbol]	1✔
163	return min(self.expansion_cost(e, seen \| {symbol}) for e in expansions)	1✔
164
165	def expansion_cost(	1✔
166	self, expansion: Expansion, seen: Set[str] = set()
167	) -> Union[int, float]:
168	symbols = nonterminals(expansion)	1✔
169	if len(symbols) == 0:	1✔
170	return 1 # no symbol	1✔
171
172	if any(s in seen for s in symbols):	1✔
173	return float("inf")	1✔
174
175	# the value of a expansion is the sum of all expandable variables
176	# inside + 1
177	return sum(self.symbol_cost(s, seen) for s in symbols) + 1	1✔
178
179	def expand_node_by_cost(	1✔
180	self, node: DerivationTree, choose: Callable = min
181	) -> DerivationTree:
182	(symbol, children) = node	1✔
183	assert children is None	1✔
184
185	# Fetch the possible expansions from grammar...
186	expansions = self.grammar[symbol]	1✔
187
188	children_alternatives_with_cost = [	1✔
189	(
190	self.expansion_to_children(expansion),
191	self.expansion_cost(expansion, {symbol}),
192	expansion,
193	)
194	for expansion in expansions
195	]
196
197	costs = [cost for (child, cost, expansion) in children_alternatives_with_cost]	1✔
198	chosen_cost = choose(costs)	1✔
199	children_with_chosen_cost = [	1✔
200	child
201	for (child, child_cost, _) in children_alternatives_with_cost
202	if child_cost == chosen_cost
203	]
204	expansion_with_chosen_cost = [	1✔
205	expansion
206	for (_, child_cost, expansion) in children_alternatives_with_cost
207	if child_cost == chosen_cost
208	]
209
210	index = self.choose_node_expansion(node, children_with_chosen_cost)	1✔
211
212	chosen_children = children_with_chosen_cost[index]	1✔
213	chosen_expansion = expansion_with_chosen_cost[index]	1✔
214	chosen_children = self.process_chosen_children(	1✔
215	chosen_children, chosen_expansion
216	)
217
218	# Return with a new list
219	return (symbol, chosen_children)	1✔
220
221	def expand_node_min_cost(self, node: DerivationTree) -> DerivationTree:	1✔
222	if self.log:	1✔
NEW 223	print("Expanding", all_terminals(node), "at minimum cost")	×
224
225	return self.expand_node_by_cost(node, min)	1✔
226
227	def expand_node_max_cost(self, node: DerivationTree) -> DerivationTree:	1✔
NEW 228	if self.log:	×
NEW 229	print("Expanding", all_terminals(node), "at maximum cost")	×
230
NEW 231	return self.expand_node_by_cost(node, max)	×
232
233	def log_tree(self, tree: DerivationTree) -> None:	1✔
234	"""Output a tree if self.log is set"""
235	if self.log:	1✔
NEW 236	print("Tree:", all_terminals(tree))	×
237	# print(self.possible_expansions(tree), "possible expansion(s) left")
238
239	def expand_tree_with_strategy(	1✔
240	self,
241	tree: DerivationTree,
242	expand_node_method: Callable,
243	limit: Optional[int] = None,
244	):
245	"""Expand tree using `expand_node_method` as node expansion function
246	until the number of possible expansions reaches `limit`."""
247	self.expand_node = expand_node_method # type: ignore	1✔
248	while (	1✔
249	limit is None or self.possible_expansions(tree) < limit
250	) and self.any_possible_expansions(tree):
251	tree = self.expand_tree_once(tree)	1✔
252	self.log_tree(tree)	1✔
253	return tree	1✔
254
255	def expand_tree(self, tree: DerivationTree) -> DerivationTree:	1✔
256	"""Expand `tree` in a three-phase strategy until all expansions are complete."""
257	self.log_tree(tree)	1✔
258	tree = self.expand_tree_with_strategy(	1✔
259	tree, self.expand_node_max_cost, self.min_nonterminals
260	)
261	tree = self.expand_tree_with_strategy(	1✔
262	tree, self.expand_node_randomly, self.max_nonterminals
263	)
264	tree = self.expand_tree_with_strategy(tree, self.expand_node_min_cost)	1✔
265
266	assert self.possible_expansions(tree) == 0	1✔
267
268	return tree	1✔
269
270	def fuzz_tree(self) -> DerivationTree:	1✔
271	"""Produce a derivation tree from the grammar."""
272	tree = self.init_tree()	1✔
273	# print(tree)
274
275	# Expand all nonterminals
276	tree = self.expand_tree(tree)	1✔
277	if self.log:	1✔
NEW 278	print(repr(all_terminals(tree)))	×
279
280	return tree	1✔
281
282	def fuzz(self) -> str:	1✔
283	"""Produce a string from the grammar."""
284	self.derivation_tree = self.fuzz_tree()	1✔
285	return all_terminals(self.derivation_tree)	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