1 // Copyright 2019 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // Much of this logic is duplicated at
6 // tools/binary_size/libsupersize/function_signature.py.
7
8 #include <stddef.h>
9
10 #include <algorithm>
11 #include <deque>
12 #include <iostream>
13 #include <string>
14 #include <string_view>
15 #include <tuple>
16 #include <vector>
17
18 #include "tools/binary_size/libsupersize/caspian/function_signature.h"
19
20 namespace {
EndsWith(std::string_view str,std::string_view suffix,size_t pos=std::string_view::npos)21 bool EndsWith(std::string_view str,
22 std::string_view suffix,
23 size_t pos = std::string_view::npos) {
24 pos = std::min(pos, str.size());
25 size_t span = suffix.size();
26 return pos >= span && str.substr(pos - span, span) == suffix;
27 }
28
Slice(std::string_view sv,size_t lo,size_t hi)29 std::string_view Slice(std::string_view sv, size_t lo, size_t hi) {
30 return sv.substr(lo, hi - lo);
31 }
32 } // namespace
33
34 namespace caspian {
SplitBy(std::string_view str,char delim)35 std::vector<std::string_view> SplitBy(std::string_view str, char delim) {
36 std::vector<std::string_view> ret;
37 while (true) {
38 size_t pos = str.find(delim);
39 ret.push_back(str.substr(0, pos));
40 if (pos == std::string_view::npos) {
41 break;
42 }
43 str = str.substr(pos + 1);
44 }
45 return ret;
46 }
47
ParseJava(std::string_view full_name,std::deque<std::string> * owned_strings)48 std::tuple<std::string_view, std::string_view, std::string_view> ParseJava(
49 std::string_view full_name,
50 std::deque<std::string>* owned_strings) {
51 // |owned_strings| is used as an allocator, the relative order of its
52 // elements can be arbitrary.
53 std::string maybe_member_type;
54 size_t hash_idx = full_name.find('#');
55 std::string_view full_class_name;
56 std::string_view member;
57 std::string_view member_type;
58 if (hash_idx != std::string_view::npos) {
59 // Parse an already parsed full_name.
60 // Format: Class#symbol: type
61 full_class_name = full_name.substr(0, hash_idx);
62 size_t colon_idx = full_name.find(':');
63 member = Slice(full_name, hash_idx + 1, colon_idx);
64 if (colon_idx != std::string_view::npos) {
65 member_type = full_name.substr(colon_idx);
66 }
67 } else {
68 // Format: Class [returntype] functionName()
69 std::vector<std::string_view> parts = SplitBy(full_name, ' ');
70 full_class_name = parts[0];
71 if (parts.size() >= 2) {
72 member = parts.back();
73 }
74 if (parts.size() >= 3) {
75 maybe_member_type = ": " + std::string(parts[1]);
76 member_type = maybe_member_type;
77 }
78 }
79
80 std::vector<std::string_view> split = SplitBy(full_class_name, '.');
81 std::string_view short_class_name = split.back();
82
83 if (member.empty()) {
84 return std::make_tuple(full_name, full_name, short_class_name);
85 }
86 owned_strings->push_back(std::string(full_class_name) + std::string("#") +
87 std::string(member) + std::string(member_type));
88 full_name = owned_strings->back();
89
90 member = member.substr(0, member.find('('));
91
92 owned_strings->push_back(std::string(short_class_name) + std::string("#") +
93 std::string(member));
94 std::string_view name = owned_strings->back();
95
96 owned_strings->push_back(std::string(full_class_name) + std::string("#") +
97 std::string(member));
98 std::string_view template_name = owned_strings->back();
99
100 return std::make_tuple(full_name, template_name, name);
101 }
102
FindLastCharOutsideOfBrackets(std::string_view name,char target_char,size_t prev_idx)103 size_t FindLastCharOutsideOfBrackets(std::string_view name,
104 char target_char,
105 size_t prev_idx) {
106 int paren_balance_count = 0;
107 int angle_balance_count = 0;
108 std::string_view prefix = name.substr(0, prev_idx);
109 while (true) {
110 size_t idx = prefix.rfind(target_char);
111 if (idx == std::string_view::npos) {
112 return std::string_view::npos;
113 }
114 for (char c : prefix.substr(idx)) {
115 switch (c) {
116 case '<':
117 angle_balance_count++;
118 break;
119 case '>':
120 angle_balance_count--;
121 break;
122 case '(':
123 paren_balance_count++;
124 break;
125 case ')':
126 paren_balance_count--;
127 break;
128 }
129 }
130 if (angle_balance_count == 0 && paren_balance_count == 0) {
131 return idx;
132 }
133 prefix = prefix.substr(0, idx);
134 }
135 }
136
FindReturnValueSpace(std::string_view name,size_t paren_idx)137 size_t FindReturnValueSpace(std::string_view name, size_t paren_idx) {
138 size_t space_idx = paren_idx;
139 // Special case: const cast operators (see tests).
140 if (EndsWith(name, " const", paren_idx)) {
141 space_idx = paren_idx - 6;
142 }
143 while (true) {
144 space_idx = FindLastCharOutsideOfBrackets(name, ' ', space_idx);
145 // Special cases: "operator new", "operator< <templ>", "operator<< <tmpl>".
146 // No space is added for operator>><tmpl>.
147 // Currently does not handle operator->, operator->*
148 if (std::string_view::npos == space_idx) {
149 break;
150 }
151 if (EndsWith(name, "operator", space_idx)) {
152 space_idx -= 8;
153 } else if (EndsWith(name, "operator<", space_idx)) {
154 space_idx -= 9;
155 } else if (EndsWith(name, "operator<<", space_idx)) {
156 space_idx -= 10;
157 } else {
158 break;
159 }
160 }
161 return space_idx;
162 }
163
StripTemplateArgs(std::string_view name_view)164 std::string StripTemplateArgs(std::string_view name_view) {
165 // TODO(jaspercb): Could pass in |owned_strings| to avoid this allocation.
166 std::string name(name_view);
167 size_t last_right_idx = std::string::npos;
168 while (true) {
169 last_right_idx = name.substr(0, last_right_idx).rfind('>');
170 if (last_right_idx == std::string_view::npos) {
171 return name;
172 }
173 size_t left_idx =
174 FindLastCharOutsideOfBrackets(name, '<', last_right_idx + 1);
175 if (left_idx != std::string_view::npos) {
176 // Leave in empty <>s to denote that it's a template.
177 name = std::string(name.substr(0, left_idx + 1)) +
178 std::string(name.substr(last_right_idx));
179 last_right_idx = left_idx;
180 }
181 }
182 }
183
NormalizeTopLevelGccLambda(std::string_view name,size_t left_paren_idx)184 std::string NormalizeTopLevelGccLambda(std::string_view name,
185 size_t left_paren_idx) {
186 // cc::{lambda(PaintOp*)#63}::_FUN(cc:PaintOp*)
187 // -> cc::$lambda#63(cc:PaintOp*)
188
189 size_t left_brace_idx = name.find('{');
190 if (left_brace_idx == std::string_view::npos) {
191 exit(1);
192 }
193 size_t hash_idx = name.find('#', left_brace_idx + 1);
194 if (hash_idx == std::string_view::npos) {
195 exit(1);
196 }
197 size_t right_brace_idx = name.find('}', hash_idx + 1);
198 if (right_brace_idx == std::string_view::npos) {
199 exit(1);
200 }
201 std::string_view number = Slice(name, hash_idx + 1, right_brace_idx);
202
203 std::string ret;
204 ret += name.substr(0, left_brace_idx);
205 ret += "$lambda#";
206 ret += number;
207 ret += name.substr(left_paren_idx);
208 return ret;
209 }
210
NormalizeTopLevelClangLambda(std::string_view name,size_t left_paren_idx)211 std::string NormalizeTopLevelClangLambda(std::string_view name,
212 size_t left_paren_idx) {
213 // cc::$_21::__invoke(int) -> cc::$lambda#21(int)
214 size_t dollar_idx = name.find('$');
215 if (dollar_idx == std::string_view::npos) {
216 exit(1);
217 }
218 size_t colon_idx = name.find(':', dollar_idx + 1);
219 if (colon_idx == std::string_view::npos) {
220 exit(1);
221 }
222 std::string_view number = Slice(name, dollar_idx + 2, colon_idx);
223
224 std::string ret;
225 ret += name.substr(0, dollar_idx);
226 ret += "$lambda#";
227 ret += number;
228 ret += name.substr(left_paren_idx);
229 return ret;
230 }
231
FindParameterListParen(std::string_view name)232 size_t FindParameterListParen(std::string_view name) {
233 size_t start_idx = 0;
234 int angle_balance_count = 0;
235 int paren_balance_count = 0;
236 while (true) {
237 size_t idx = name.find('(', start_idx);
238 if (idx == std::string_view::npos) {
239 return std::string_view::npos;
240 }
241 for (char c : Slice(name, start_idx, idx)) {
242 switch (c) {
243 case '<':
244 angle_balance_count++;
245 break;
246 case '>':
247 angle_balance_count--;
248 break;
249 case '(':
250 paren_balance_count++;
251 break;
252 case ')':
253 paren_balance_count--;
254 break;
255 }
256 }
257 size_t operator_offset = Slice(name, start_idx, idx).find("operator<");
258 if (operator_offset != std::string_view::npos) {
259 if (name[start_idx + operator_offset + 9] == '<') {
260 // Handle operator<<, <<=
261 angle_balance_count -= 2;
262 } else {
263 // Handle operator<=
264 angle_balance_count -= 1;
265 }
266 } else {
267 operator_offset = Slice(name, start_idx, idx).find("operator>");
268 if (operator_offset != std::string_view::npos) {
269 if (name[start_idx + operator_offset + 9] == '>') {
270 // Handle operator>>,>>=
271 angle_balance_count += 2;
272 } else {
273 // Handle operator>=
274 angle_balance_count += 1;
275 }
276 }
277 }
278
279 // Adjust paren
280 if (angle_balance_count == 0 && paren_balance_count == 0) {
281 // Special case: skip "(anonymous namespace)".
282 if (name.substr(idx, 21) == "(anonymous namespace)") {
283 start_idx = idx + 21;
284 continue;
285 }
286 // Special case: skip "decltype (...)"
287 // Special case: skip "{lambda(PaintOp*)#63}"
288 if (idx && name[idx - 1] != ' ' && !EndsWith(name, "{lambda", idx)) {
289 return idx;
290 }
291 }
292
293 start_idx = idx + 1;
294 paren_balance_count++;
295 }
296 }
297
ParseCpp(std::string_view full_name,std::deque<std::string> * owned_strings)298 std::tuple<std::string_view, std::string_view, std::string_view> ParseCpp(
299 std::string_view full_name,
300 std::deque<std::string>* owned_strings) {
301 std::string name;
302 std::string_view name_view;
303 size_t left_paren_idx = FindParameterListParen(full_name);
304 if (left_paren_idx != std::string::npos && left_paren_idx > 0) {
305 size_t right_paren_idx = full_name.rfind(')');
306 if (right_paren_idx <= left_paren_idx) {
307 std::cerr << "ParseCpp() received bad symbol: " << full_name << std::endl;
308 exit(1);
309 }
310 size_t space_idx = FindReturnValueSpace(full_name, left_paren_idx);
311 std::string name_no_params =
312 std::string(Slice(full_name, space_idx + 1, left_paren_idx));
313 // Special case for top-level lambdas.
314 if (EndsWith(name_no_params, "}::_FUN")) {
315 // Don't use |name_no_params| in here since prior _idx will be off if
316 // there was a return value.
317 owned_strings->push_back(
318 NormalizeTopLevelGccLambda(full_name, left_paren_idx));
319 return ParseCpp(owned_strings->back(), owned_strings);
320 } else if (EndsWith(name_no_params, "::__invoke") &&
321 name_no_params.find('$') != std::string::npos) {
322 owned_strings->push_back(
323 NormalizeTopLevelClangLambda(full_name, left_paren_idx));
324 return ParseCpp(owned_strings->back(), owned_strings);
325 }
326
327 name = name_no_params + std::string(full_name.substr(right_paren_idx + 1));
328 name_view = name;
329 full_name = full_name.substr(space_idx + 1);
330 } else {
331 name_view = full_name;
332 }
333
334 owned_strings->emplace_back(name_view);
335 std::string_view template_name = owned_strings->back();
336
337 owned_strings->push_back(StripTemplateArgs(name_view));
338 std::string_view returned_name = owned_strings->back();
339
340 return std::make_tuple(full_name, template_name, returned_name);
341 }
342 } // namespace caspian
343