projects/linux·blob master · refs

247 lines · 8.1 KiB

1#!/usr/bin/env python3
2# xxpylint: disable=R0903
3# Copyright(c) 2025: Mauro Carvalho Chehab <[email protected]>.
4# SPDX-License-Identifier: GPL-2.0
5
6"""
7Convert ABI what into regular expressions
8"""
9
10import re
11import sys
12
13from pprint import pformat
14
15from abi.abi_parser import AbiParser
16from abi.helpers import AbiDebug
17
18class AbiRegex(AbiParser):
19 """
20 Extends AbiParser to search ABI nodes with regular expressions.
21
22 There some optimizations here to allow a quick symbol search:
23 instead of trying to place all symbols altogether an doing linear
24 search which is very time consuming, create a tree with one depth,
25 grouping similar symbols altogether.
26
27 Yet, sometimes a full search will be needed, so we have a special branch
28 on such group tree where other symbols are placed.
29 """
30
31 #: Escape only ASCII visible characters.
32 escape_symbols = r"([\x21-\x29\x2b-\x2d\x3a-\x40\x5c\x60\x7b-\x7e])"
33
34 #: Special group for other nodes.
35 leave_others = "others"
36
37 # Tuples with regular expressions to be compiled and replacement data
38 re_whats = [
39 # Drop escape characters that might exist
40 (re.compile("\\\\"), ""),
41
42 # Temporarily escape dot characters
43 (re.compile(r"\."), "\xf6"),
44
45 # Temporarily change [0-9]+ type of patterns
46 (re.compile(r"\[0\-9\]\+"), "\xff"),
47
48 # Temporarily change [\d+-\d+] type of patterns
49 (re.compile(r"\[0\-\d+\]"), "\xff"),
50 (re.compile(r"\[0:\d+\]"), "\xff"),
51 (re.compile(r"\[(\d+)\]"), "\xf4\\\\d+\xf5"),
52
53 # Temporarily change [0-9] type of patterns
54 (re.compile(r"\[(\d)\-(\d)\]"), "\xf4\1-\2\xf5"),
55
56 # Handle multiple option patterns
57 (re.compile(r"[\{\<\[]([\w_]+)(?:[,|]+([\w_]+)){1,}[\}\>\]]"), r"(\1|\2)"),
58
59 # Handle wildcards
60 (re.compile(r"([^\/])\*"), "\\1\\\\w\xf7"),
61 (re.compile(r"/\*/"), "/.*/"),
62 (re.compile(r"/\xf6\xf6\xf6"), "/.*"),
63 (re.compile(r"\<[^\>]+\>"), "\\\\w\xf7"),
64 (re.compile(r"\{[^\}]+\}"), "\\\\w\xf7"),
65 (re.compile(r"\[[^\]]+\]"), "\\\\w\xf7"),
66
67 (re.compile(r"XX+"), "\\\\w\xf7"),
68 (re.compile(r"(?<![A-Z])[XYZ](?![A-Z])"), "\\\\w\xf7"),
69 (re.compile(r"_[AB]_"), "_\\\\w\xf7_"),
70
71 # Recover [0-9] type of patterns
72 (re.compile(r"\xf4"), "["),
73 (re.compile(r"\xf5"), "]"),
74
75 # Remove duplicated spaces
76 (re.compile(r"\s+"), r" "),
77
78 # Special case: drop comparison as in:
79 # What: foo = <something>
80 # (this happens on a few IIO definitions)
81 (re.compile(r"\s*\=.*$"), ""),
82
83 # Escape all other symbols
84 (re.compile(escape_symbols), r"\\\1"),
85 (re.compile(r"\\\\"), r"\\"),
86 (re.compile(r"\\([\[\]\(\)\|])"), r"\1"),
87 (re.compile(r"(\d+)\\(-\d+)"), r"\1\2"),
88
89 (re.compile(r"\xff"), r"\\d+"),
90
91 # Special case: IIO ABI which a parenthesis.
92 (re.compile(r"sqrt(.*)"), r"sqrt(.*)"),
93
94 # Simplify regexes with multiple .*
95 (re.compile(r"(?:\.\*){2,}"), ""),
96
97 # Recover dot characters
98 (re.compile(r"\xf6"), "\\."),
99 # Recover plus characters
100 (re.compile(r"\xf7"), "+"),
101 ]
102
103 #: Regex to check if the symbol name has a number on it.
104 re_has_num = re.compile(r"\\d")
105
106 #: Symbol name after escape_chars that are considered a devnode basename.
107 re_symbol_name = re.compile(r"(\w|\\[\.\-\:])+$")
108
109 #: List of popular group names to be skipped to minimize regex group size
110 #: Use AbiDebug.SUBGROUP_SIZE to detect those.
111 skip_names = set(["devices", "hwmon"])
112
113 def regex_append(self, what, new):
114 """
115 Get a search group for a subset of regular expressions.
116
117 As ABI may have thousands of symbols, using a for to search all
118 regular expressions is at least O(n^2). When there are wildcards,
119 the complexity increases substantially, eventually becoming exponential.
120
121 To avoid spending too much time on them, use a logic to split
122 them into groups. The smaller the group, the better, as it would
123 mean that searches will be confined to a small number of regular
124 expressions.
125
126 The conversion to a regex subset is tricky, as we need something
127 that can be easily obtained from the sysfs symbol and from the
128 regular expression. So, we need to discard nodes that have
129 wildcards.
130
131 If it can't obtain a subgroup, place the regular expression inside
132 a special group (self.leave_others).
133 """
134
135 search_group = None
136
137 for search_group in reversed(new.split("/")):
138 if not search_group or search_group in self.skip_names:
139 continue
140 if self.re_symbol_name.match(search_group):
141 break
142
143 if not search_group:
144 search_group = self.leave_others
145
146 if self.debug & AbiDebug.SUBGROUP_MAP:
147 self.log.debug("%s: mapped as %s", what, search_group)
148
149 try:
150 if search_group not in self.regex_group:
151 self.regex_group[search_group] = []
152
153 self.regex_group[search_group].append(re.compile(new))
154 if self.search_string:
155 if what.find(self.search_string) >= 0:
156 print(f"What: {what}")
157 except re.error:
158 self.log.warning("Ignoring '%s' as it produced an invalid regex:\n"
159 " '%s'", what, new)
160
161 def get_regexes(self, what):
162 """
163 Given an ABI devnode, return a list of all regular expressions that
164 may match it, based on the sub-groups created by regex_append().
165 """
166
167 re_list = []
168
169 patches = what.split("/")
170 patches.reverse()
171 patches.append(self.leave_others)
172
173 for search_group in patches:
174 if search_group in self.regex_group:
175 re_list += self.regex_group[search_group]
176
177 return re_list
178
179 def __init__(self, *args, **kwargs):
180 """
181 Override init method to get verbose argument
182 """
183
184 self.regex_group = None
185 self.search_string = None
186 self.re_string = None
187
188 if "search_string" in kwargs:
189 self.search_string = kwargs.get("search_string")
190 del kwargs["search_string"]
191
192 if self.search_string:
193
194 try:
195 self.re_string = re.compile(self.search_string)
196 except re.error as e:
197 msg = f"{self.search_string} is not a valid regular expression"
198 raise ValueError(msg) from e
199
200 super().__init__(*args, **kwargs)
201
202 def parse_abi(self, *args, **kwargs):
203
204 super().parse_abi(*args, **kwargs)
205
206 self.regex_group = {}
207
208 print("Converting ABI What fields into regexes...", file=sys.stderr)
209
210 for t in sorted(self.data.items(), key=lambda x: x[0]):
211 v = t[1]
212 if v.get("type") == "File":
213 continue
214
215 v["regex"] = []
216
217 for what in v.get("what", []):
218 if not what.startswith("/sys"):
219 continue
220
221 new = what
222 for r, s in self.re_whats:
223 try:
224 new = r.sub(s, new)
225 except re.error as e:
226 # Help debugging troubles with new regexes
227 raise re.error(f"{e}\nwhile re.sub('{r.pattern}', {s}, str)") from e
228
229 v["regex"].append(new)
230
231 if self.debug & AbiDebug.REGEX:
232 self.log.debug("%-90s <== %s", new, what)
233
234 # Store regex into a subgroup to speedup searches
235 self.regex_append(what, new)
236
237 if self.debug & AbiDebug.SUBGROUP_DICT:
238 self.log.debug("%s", pformat(self.regex_group))
239
240 if self.debug & AbiDebug.SUBGROUP_SIZE:
241 biggestd_keys = sorted(self.regex_group.keys(),
242 key= lambda k: len(self.regex_group[k]),
243 reverse=True)
244
245 print("Top regex subgroups:", file=sys.stderr)
246 for k in biggestd_keys[:10]:
247 print(f"{k} has {len(self.regex_group[k])} elements", file=sys.stderr)