8171647283

Committed 06 Mar 2024 11:57AM UTC coverage: 72.671% (+2.0%) from 70.662%

Build # 8171647283

Build Type

Pull #26

github

Committed by

web-flow

Commit Message

Merge 08a98172c into f838bc853

Pull Request Pull Request #26: Release 0.2.0

Run Details

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

1 existing line 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

43.5

/src/debugging_framework/features.py

from typing import List, Set, Dict, Optional, Any
import re
from abc import ABC, abstractmethod
from collections import defaultdict

from isla.derivation_tree import DerivationTree

from debugging_framework.types import Grammar
from debugging_framework.grammar import reachable_nonterminals, is_nonterminal
from debugging_framework.oracle import OracleResult


class Feature(ABC):
    def __init__(self, non_terminal: str):
        self.non_terminal = non_terminal

    def __repr__(self) -> str:
        return (
            self._repr()
            .replace('"', "&quot;")
            .replace(",", "&comma;")
            .replace("[", "&lsqb;")
            .replace("]", "&rsqb;")
            .replace("{", "&lcub;")
            .replace("}", "&rcub;")
            .replace(":", "&colon;")
        )

    @abstractmethod
    def _repr(self) -> str:
        raise NotImplementedError

    def __hash__(self):
        return hash(self.__repr__())

    def __eq__(self, other):
        if isinstance(other, type(self)):
            return self.__hash__() == hash(other)
        return False

    @abstractmethod
    def default_value(self):
        raise NotImplementedError

    @abstractmethod
    def type(self):
        raise NotImplementedError

    @abstractmethod
    def evaluate(self, subtree: DerivationTree) -> Any:
        raise NotImplementedError

    @classmethod
    @abstractmethod
    def factory_method(cls, grammar):
        raise NotImplementedError


class ExistenceFeature(Feature):
    def __init__(self, non_terminal: str):
        super().__init__(non_terminal)

    def _repr(self) -> str:
        return f"exists({self.non_terminal})"

    @property
    def default_value(self):
        return 0

    @property
    def type(self):
        return int

    def evaluate(self, subtree: DerivationTree) -> int:
        current_node, _ = subtree
        return int(self.non_terminal == current_node)

    @classmethod
    def factory_method(cls, grammar) -> List[Feature]:
        return [cls(non_terminal) for non_terminal in grammar]


class DerivationFeature(Feature):
    def __init__(self, non_terminal: str, expansion: str):
        super().__init__(non_terminal)
        self.expansion = expansion

    def _repr(self) -> str:
        return f"exists({self.non_terminal} -> {self.expansion})"

    @property
    def default_value(self):
        return 0

    @property
    def type(self):
        return int

    def evaluate(self, subtree: DerivationTree) -> int:
        current_node, children = subtree

        expansion = "".join([child[0] for child in children])
        return int(self.non_terminal == current_node and self.expansion == expansion)

    @classmethod
    def factory_method(cls, grammar) -> List[Feature]:
        features = []

        for non_terminal in grammar:
            for expansion in grammar[non_terminal]:
                features.append(cls(non_terminal, expansion))

        return features


class NumericFeature(Feature):
    def _repr(self):
        return f"num({self.non_terminal})"

    @property
    def default_value(self):
        return float("-inf")

    @property
    def type(self):
        return float

    def evaluate(self, subtree: DerivationTree) -> Any:
        try:
            value = float(tree_to_string(subtree))
            return value
        except ValueError:
            return self.default_value

    @classmethod
    def factory_method(cls, grammar) -> List[Feature]:
        derivable_chars = cls.get_derivable_chars(grammar)
        return cls.get_features(derivable_chars)

    @classmethod
    def get_derivable_chars(cls, grammar: Grammar) -> Dict[str, Set[str]]:
        """
        Gets all the derivable characters for each rule in the grammar.
        :param grammar: The input grammar.
        :return: A mapping from each rule to a set of derivable characters.
        """
        # Regex for non-terminal symbols in expansions
        re_non_terminal = re.compile(r"(<[^<> ]*>)")

        # Mapping from non-terminals to derivable terminal chars
        derivable_chars = defaultdict(set)

        # Populate initial derivable_chars
        for rule, expansions in grammar.items():
            for expansion in expansions:
                # Remove non-terminal symbols and whitespace from expansion
                terminals = re.sub(re_non_terminal, "", expansion)
                # Add each terminal char to the set of derivable chars
                for char in terminals:
                    derivable_chars[rule].add(char)

        # Update derivable_chars until convergence
        while True:
            if not cls.update_derivable_chars(grammar, derivable_chars):
                break

        return derivable_chars

    @classmethod
    def update_derivable_chars(
        cls, grammar: Grammar, derivable_chars: Dict[str, Set[str]]
    ) -> bool:
        """
        Update the mapping of derivable characters for each rule.
        :param grammar: The input grammar.
        :param derivable_chars: The existing mapping of derivable characters.
        :return: True if any set of derivable chars was updated, False otherwise.
        """
        updated = False
        for rule in grammar:
            for reachable_rule in reachable_nonterminals(grammar, rule):
                before_update = len(derivable_chars[rule])
                derivable_chars[rule].update(derivable_chars[reachable_rule])
                after_update = len(derivable_chars[rule])

                # Set of derivable chars was updated
                if after_update > before_update:
                    updated = True
        return updated

    @classmethod
    def get_features(cls, derivable_chars: Dict[str, Set[str]]) -> List[Feature]:
        """
        Gets a list of NumericInterpretation features for each rule that derives only numeric characters.
        :param derivable_chars: The mapping of derivable characters.
        :return: A list of NumericInterpretation features.
        """
        features = []
        numeric_chars = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}
        numeric_symbols = {".", "-"}

        for non_terminal, chars in derivable_chars.items():
            non_numeric_chars = (chars - numeric_chars) - numeric_symbols
            has_numeric_chars = len(chars.intersection(numeric_chars)) > 0

            # Rule derives only numeric characters and at least one numeric character
            if len(non_numeric_chars) == 0 and has_numeric_chars:
                features.append(cls(non_terminal))

        return features


class LengthFeature(Feature):
    def _repr(self):
        return f"len({self.non_terminal})"

    @property
    def default_value(self):
        return 0

    def type(self):
        return int

    def evaluate(self, subtree: DerivationTree) -> Any:
        return len(tree_to_string(subtree))

    @classmethod
    def factory_method(cls, grammar) -> List[Feature]:
        features = []
        for non_terminal in grammar:
            features.append(cls(non_terminal))
        return features


class FeatureFactory:
    def __init__(self, grammar):
        self.grammar = grammar

    def build(self, feature_types=None) -> List[Feature]:
        if feature_types is None:
            feature_types = [
                ExistenceFeature,
                DerivationFeature,
                NumericFeature,
                LengthFeature,
            ]

        all_features = list()
        for feature_type in feature_types:
            all_features.extend(feature_type.factory_method(self.grammar))
        return all_features


class FeatureVector:
    def __init__(
        self,
        test_input: str,
        result: Optional[OracleResult] = None,
    ):
        self.test_input = test_input
        self.result = result
        self.features: Dict[Feature, Any] = dict()

    def get_feature_value(self, feature: Feature) -> Any:
        if feature in self.features:
            return self.features[feature]
        else:
            return feature.default_value

    def set_feature(self, feature: Feature, value: any):
        if feature in self.features.keys():
            self.features[feature] = max(value, self.features[feature])
        else:
            self.features[feature] = value

    def get_features(self) -> Dict[Feature, Any]:
        return self.features

    def __repr__(self):
        return f"{self.test_input}: {self.features}"


def tree_to_string(tree: DerivationTree) -> str:
    symbol, children, *_ = tree
    if children:
        return "".join(tree_to_string(c) for c in children)
    else:
        return "" if is_nonterminal(symbol) else symbol

1	from typing import List, Set, Dict, Optional, Any	1✔
2	import re	1✔
3	from abc import ABC, abstractmethod	1✔
4	from collections import defaultdict	1✔
5
6	from isla.derivation_tree import DerivationTree	1✔
7
8	from debugging_framework.types import Grammar	1✔
9	from debugging_framework.grammar import reachable_nonterminals, is_nonterminal	1✔
10	from debugging_framework.oracle import OracleResult	1✔
11
12
13	class Feature(ABC):	1✔
14	def __init__(self, non_terminal: str):	1✔
15	self.non_terminal = non_terminal	×
16
17	def __repr__(self) -> str:	1✔
NEW 18	return (	×
19	self._repr()
20	.replace('"', """)
21	.replace(",", ",")
22	.replace("[", "[")
23	.replace("]", "]")
24	.replace("{", "{")
25	.replace("}", "}")
26	.replace(":", "&colon;")
27	)
28
29	@abstractmethod	1✔
30	def _repr(self) -> str:	1✔
NEW 31	raise NotImplementedError	×
32
33	def __hash__(self):	1✔
34	return hash(self.__repr__())	×
35
36	def __eq__(self, other):	1✔
37	if isinstance(other, type(self)):	×
38	return self.__hash__() == hash(other)	×
39	return False	×
40
41	@abstractmethod	1✔
42	def default_value(self):	1✔
43	raise NotImplementedError	×
44
45	@abstractmethod	1✔
46	def type(self):	1✔
47	raise NotImplementedError	×
48
49	@abstractmethod	1✔
50	def evaluate(self, subtree: DerivationTree) -> Any:	1✔
51	raise NotImplementedError	×
52
53	@classmethod	1✔
54	@abstractmethod	1✔
55	def factory_method(cls, grammar):	1✔
56	raise NotImplementedError	×
57
58
59	class ExistenceFeature(Feature):	1✔
60	def __init__(self, non_terminal: str):	1✔
61	super().__init__(non_terminal)	×
62
63	def _repr(self) -> str:	1✔
64	return f"exists({self.non_terminal})"	×
65
66	@property	1✔
67	def default_value(self):	1✔
68	return 0	×
69
70	@property	1✔
71	def type(self):	1✔
72	return int	×
73
74	def evaluate(self, subtree: DerivationTree) -> int:	1✔
75	current_node, _ = subtree	×
76	return int(self.non_terminal == current_node)	×
77
78	@classmethod	1✔
79	def factory_method(cls, grammar) -> List[Feature]:	1✔
80	return [cls(non_terminal) for non_terminal in grammar]	×
81
82
83	class DerivationFeature(Feature):	1✔
84	def __init__(self, non_terminal: str, expansion: str):	1✔
85	super().__init__(non_terminal)	×
86	self.expansion = expansion	×
87
88	def _repr(self) -> str:	1✔
89	return f"exists({self.non_terminal} -> {self.expansion})"	×
90
91	@property	1✔
92	def default_value(self):	1✔
93	return 0	×
94
95	@property	1✔
96	def type(self):	1✔
97	return int	×
98
99	def evaluate(self, subtree: DerivationTree) -> int:	1✔
100	current_node, children = subtree	×
101
102	expansion = "".join([child[0] for child in children])	×
103	return int(self.non_terminal == current_node and self.expansion == expansion)	×
104
105	@classmethod	1✔
106	def factory_method(cls, grammar) -> List[Feature]:	1✔
107	features = []	×
108
109	for non_terminal in grammar:	×
110	for expansion in grammar[non_terminal]:	×
111	features.append(cls(non_terminal, expansion))	×
112
113	return features	×
114
115
116	class NumericFeature(Feature):	1✔
117	def _repr(self):	1✔
118	return f"num({self.non_terminal})"	×
119
120	@property	1✔
121	def default_value(self):	1✔
122	return float("-inf")	×
123
124	@property	1✔
125	def type(self):	1✔
126	return float	×
127
128	def evaluate(self, subtree: DerivationTree) -> Any:	1✔
129	try:	×
130	value = float(tree_to_string(subtree))	×
131	return value	×
132	except ValueError:	×
133	return self.default_value	×
134
135	@classmethod	1✔
136	def factory_method(cls, grammar) -> List[Feature]:	1✔
137	derivable_chars = cls.get_derivable_chars(grammar)	×
138	return cls.get_features(derivable_chars)	×
139
140	@classmethod	1✔
141	def get_derivable_chars(cls, grammar: Grammar) -> Dict[str, Set[str]]:	1✔
142	"""
143	Gets all the derivable characters for each rule in the grammar.
144	:param grammar: The input grammar.
145	:return: A mapping from each rule to a set of derivable characters.
146	"""
147	# Regex for non-terminal symbols in expansions
148	re_non_terminal = re.compile(r"(<[^<> ]*>)")	×
149
150	# Mapping from non-terminals to derivable terminal chars
151	derivable_chars = defaultdict(set)	×
152
153	# Populate initial derivable_chars
154	for rule, expansions in grammar.items():	×
155	for expansion in expansions:	×
156	# Remove non-terminal symbols and whitespace from expansion
157	terminals = re.sub(re_non_terminal, "", expansion)	×
158	# Add each terminal char to the set of derivable chars
159	for char in terminals:	×
160	derivable_chars[rule].add(char)	×
161
162	# Update derivable_chars until convergence
163	while True:	×
164	if not cls.update_derivable_chars(grammar, derivable_chars):	×
165	break	×
166
167	return derivable_chars	×
168
169	@classmethod	1✔
170	def update_derivable_chars(	1✔
171	cls, grammar: Grammar, derivable_chars: Dict[str, Set[str]]
172	) -> bool:
173	"""
174	Update the mapping of derivable characters for each rule.
175	:param grammar: The input grammar.
176	:param derivable_chars: The existing mapping of derivable characters.
177	:return: True if any set of derivable chars was updated, False otherwise.
178	"""
179	updated = False	×
180	for rule in grammar:	×
181	for reachable_rule in reachable_nonterminals(grammar, rule):	×
182	before_update = len(derivable_chars[rule])	×
183	derivable_chars[rule].update(derivable_chars[reachable_rule])	×
184	after_update = len(derivable_chars[rule])	×
185
186	# Set of derivable chars was updated
187	if after_update > before_update:	×
188	updated = True	×
189	return updated	×
190
191	@classmethod	1✔
192	def get_features(cls, derivable_chars: Dict[str, Set[str]]) -> List[Feature]:	1✔
193	"""
194	Gets a list of NumericInterpretation features for each rule that derives only numeric characters.
195	:param derivable_chars: The mapping of derivable characters.
196	:return: A list of NumericInterpretation features.
197	"""
198	features = []	×
199	numeric_chars = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}	×
200	numeric_symbols = {".", "-"}	×
201
202	for non_terminal, chars in derivable_chars.items():	×
203	non_numeric_chars = (chars - numeric_chars) - numeric_symbols	×
204	has_numeric_chars = len(chars.intersection(numeric_chars)) > 0	×
205
206	# Rule derives only numeric characters and at least one numeric character
207	if len(non_numeric_chars) == 0 and has_numeric_chars:	×
208	features.append(cls(non_terminal))	×
209
210	return features	×
211
212
213	class LengthFeature(Feature):	1✔
214	def _repr(self):	1✔
215	return f"len({self.non_terminal})"	×
216
217	@property	1✔
218	def default_value(self):	1✔
219	return 0	×
220
221	def type(self):	1✔
222	return int	×
223
224	def evaluate(self, subtree: DerivationTree) -> Any:	1✔
225	return len(tree_to_string(subtree))	×
226
227	@classmethod	1✔
228	def factory_method(cls, grammar) -> List[Feature]:	1✔
229	features = []	×
230	for non_terminal in grammar:	×
231	features.append(cls(non_terminal))	×
232	return features	×
233
234
235	class FeatureFactory:	1✔
236	def __init__(self, grammar):	1✔
237	self.grammar = grammar	×
238
239	def build(self, feature_types=None) -> List[Feature]:	1✔
240	if feature_types is None:	×
241	feature_types = [	×
242	ExistenceFeature,
243	DerivationFeature,
244	NumericFeature,
245	LengthFeature,
246	]
247
248	all_features = list()	×
249	for feature_type in feature_types:	×
250	all_features.extend(feature_type.factory_method(self.grammar))	×
251	return all_features	×
252
253
254	class FeatureVector:	1✔
255	def __init__(	1✔
256	self,
257	test_input: str,
258	result: Optional[OracleResult] = None,
259	):
260	self.test_input = test_input	×
261	self.result = result	×
262	self.features: Dict[Feature, Any] = dict()	×
263
264	def get_feature_value(self, feature: Feature) -> Any:	1✔
265	if feature in self.features:	×
266	return self.features[feature]	×
267	else:
268	return feature.default_value	×
269
270	def set_feature(self, feature: Feature, value: any):	1✔
271	if feature in self.features.keys():	×
272	self.features[feature] = max(value, self.features[feature])	×
273	else:
274	self.features[feature] = value	×
275
276	def get_features(self) -> Dict[Feature, Any]:	1✔
277	return self.features	×
278
279	def __repr__(self):	1✔
280	return f"{self.test_input}: {self.features}"	×
281
282
283	def tree_to_string(tree: DerivationTree) -> str:	1✔
284	symbol, children, *_ = tree	×
285	if children:	×
286	return "".join(tree_to_string(c) for c in children)	×
287	else:
288	return "" if is_nonterminal(symbol) else symbol	×

martineberlein / debugging-benchmark / 8171647283

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