/home/andy/git/oilshell/oil/mycpp/gc_builtins.cc
Line | Count | Source (jump to first uncovered line) |
1 | | #include <ctype.h> // isspace() |
2 | | #include <errno.h> // errno |
3 | | #include <float.h> // DBL_MIN, DBL_MAX |
4 | | #include <math.h> // INFINITY |
5 | | #include <stdio.h> // required for readline/readline.h (man readline) |
6 | | |
7 | | #include "_build/detected-cpp-config.h" |
8 | | #include "mycpp/runtime.h" |
9 | | #ifdef HAVE_READLINE |
10 | | #include "cpp/frontend_pyreadline.h" |
11 | | #endif |
12 | | |
13 | | // Translation of Python's print(). |
14 | 201 | void print(BigStr* s) { |
15 | 201 | fputs(s->data_, stdout); // print until first NUL |
16 | 201 | fputc('\n', stdout); |
17 | 201 | } |
18 | | |
19 | 23 | BigStr* str(int i) { |
20 | 23 | BigStr* s = OverAllocatedStr(kIntBufSize); |
21 | 23 | int length = snprintf(s->data(), kIntBufSize, "%d", i); |
22 | 23 | s->MaybeShrink(length); |
23 | 23 | return s; |
24 | 23 | } |
25 | | |
26 | | // TODO: |
27 | | // - This could use a fancy exact algorithm, not libc |
28 | | // - Does libc depend on locale? |
29 | 4 | BigStr* str(double d) { |
30 | 4 | char buf[64]; // overestimate, but we use snprintf() to be safe |
31 | | |
32 | | // Problem: |
33 | | // %f prints 3.0000000 and 3.500000 |
34 | | // %g prints 3 and 3.5 |
35 | | // |
36 | | // We want literal syntax to indicate float, so add '.' |
37 | | |
38 | 4 | int n = sizeof(buf) - 2; // in case we add '.0' |
39 | | |
40 | | // %.9g digits for string that can be converted back to the same FLOAT |
41 | | // (not double) |
42 | | // https://stackoverflow.com/a/21162120 |
43 | | // https://en.cppreference.com/w/cpp/types/numeric_limits/max_digits10 |
44 | 4 | int length = snprintf(buf, n, "%.9g", d); |
45 | | |
46 | | // %a is a hexfloat form, could use that somewhere |
47 | | // int length = snprintf(buf, n, "%a", d); |
48 | | |
49 | 4 | if (strchr(buf, 'i')) { // inf or -inf |
50 | 0 | return StrFromC(buf); |
51 | 0 | } |
52 | | |
53 | 4 | if (!strchr(buf, '.')) { // 12345 -> 12345.0 |
54 | 2 | buf[length] = '.'; |
55 | 2 | buf[length + 1] = '0'; |
56 | 2 | buf[length + 2] = '\0'; |
57 | 2 | } |
58 | | |
59 | 4 | return StrFromC(buf); |
60 | 4 | } |
61 | | |
62 | | // Do we need this API? Or is mylib.InternedStr(BigStr* s, int start, int end) |
63 | | // better for getting values out of Token.line without allocating? |
64 | | // |
65 | | // e.g. mylib.InternedStr(tok.line, tok.start, tok.start+1) |
66 | | // |
67 | | // Also for SmallStr, we don't care about interning. Only for HeapStr. |
68 | | |
69 | 2 | BigStr* intern(BigStr* s) { |
70 | | // TODO: put in table gHeap.interned_ |
71 | 2 | return s; |
72 | 2 | } |
73 | | |
74 | | // Print quoted string. TODO: use C-style strings (YSTR) |
75 | 58 | BigStr* repr(BigStr* s) { |
76 | | // Worst case: \0 becomes 4 bytes as '\\x00', and then two quote bytes. |
77 | 58 | int n = len(s); |
78 | 58 | int upper_bound = n * 4 + 2; |
79 | | |
80 | 58 | BigStr* result = OverAllocatedStr(upper_bound); |
81 | | |
82 | | // Single quote by default. |
83 | 58 | char quote = '\''; |
84 | 58 | if (memchr(s->data_, '\'', n) && !memchr(s->data_, '"', n)) { |
85 | 10 | quote = '"'; |
86 | 10 | } |
87 | 58 | char* p = result->data_; |
88 | | |
89 | | // From PyString_Repr() |
90 | 58 | *p++ = quote; |
91 | 487 | for (int i = 0; i < n; ++i) { |
92 | 429 | char c = s->data_[i]; |
93 | 429 | if (c == quote || c == '\\') { |
94 | 0 | *p++ = '\\'; |
95 | 0 | *p++ = c; |
96 | 429 | } else if (c == '\t') { |
97 | 7 | *p++ = '\\'; |
98 | 7 | *p++ = 't'; |
99 | 422 | } else if (c == '\n') { |
100 | 14 | *p++ = '\\'; |
101 | 14 | *p++ = 'n'; |
102 | 408 | } else if (c == '\r') { |
103 | 7 | *p++ = '\\'; |
104 | 7 | *p++ = 'r'; |
105 | 401 | } else if (isprint(c)) { |
106 | 383 | *p++ = c; |
107 | 383 | } else { // Unprintable is \xff |
108 | 18 | sprintf(p, "\\x%02x", c & 0xff); |
109 | 18 | p += 4; |
110 | 18 | } |
111 | 429 | } |
112 | 58 | *p++ = quote; |
113 | 58 | *p = '\0'; |
114 | | |
115 | 58 | int length = p - result->data_; |
116 | 58 | result->MaybeShrink(length); |
117 | 58 | return result; |
118 | 58 | } |
119 | | |
120 | | // Helper functions that don't use exceptions. |
121 | | |
122 | 66 | bool StringToInt(const char* s, int length, int base, int* result) { |
123 | 66 | if (length == 0) { |
124 | 0 | return false; // empty string isn't a valid integer |
125 | 0 | } |
126 | | |
127 | | // Note: sizeof(int) is often 4 bytes on both 32-bit and 64-bit |
128 | | // sizeof(long) is often 4 bytes on both 32-bit but 8 bytes on 64-bit |
129 | | // static_assert(sizeof(long) == 8); |
130 | | |
131 | 66 | char* pos; // mutated by strtol |
132 | | |
133 | 66 | errno = 0; |
134 | 66 | long v = strtol(s, &pos, base); |
135 | | |
136 | 66 | if (errno == ERANGE) { |
137 | 0 | switch (v) { |
138 | 0 | case LONG_MIN: |
139 | 0 | return false; // underflow of long, which may be 64 bits |
140 | 0 | case LONG_MAX: |
141 | 0 | return false; // overflow of long |
142 | 0 | } |
143 | 0 | } |
144 | | |
145 | | // It should ALSO fit in an int, not just a long |
146 | 66 | if (v > INT_MAX) { |
147 | 2 | return false; |
148 | 2 | } |
149 | 64 | if (v < INT_MIN) { |
150 | 2 | return false; |
151 | 2 | } |
152 | | |
153 | 62 | const char* end = s + length; |
154 | 62 | if (pos == end) { |
155 | 59 | *result = v; |
156 | 59 | return true; // strtol() consumed ALL characters. |
157 | 59 | } |
158 | | |
159 | 3 | while (pos < end) { |
160 | 3 | if (!isspace(*pos)) { |
161 | 3 | return false; // Trailing non-space |
162 | 3 | } |
163 | 0 | pos++; |
164 | 0 | } |
165 | | |
166 | 0 | *result = v; |
167 | 0 | return true; // Trailing space is OK |
168 | 3 | } |
169 | | |
170 | 23 | bool StringToInt64(const char* s, int length, int base, int64_t* result) { |
171 | 23 | if (length == 0) { |
172 | 2 | return false; // empty string isn't a valid integer |
173 | 2 | } |
174 | | |
175 | | // These should be the same type |
176 | 21 | static_assert(sizeof(long long) == sizeof(int64_t)); |
177 | | |
178 | 21 | char* pos; // mutated by strtol |
179 | | |
180 | 21 | errno = 0; |
181 | 21 | long long v = strtoll(s, &pos, base); |
182 | | |
183 | 21 | if (errno == ERANGE) { |
184 | 4 | switch (v) { |
185 | 2 | case LLONG_MIN: |
186 | 2 | return false; // underflow |
187 | 2 | case LLONG_MAX: |
188 | 2 | return false; // overflow |
189 | 4 | } |
190 | 4 | } |
191 | | |
192 | 17 | const char* end = s + length; |
193 | 17 | if (pos == end) { |
194 | 11 | *result = v; |
195 | 11 | return true; // strtol() consumed ALL characters. |
196 | 11 | } |
197 | | |
198 | 10 | while (pos < end) { |
199 | 8 | if (!isspace(*pos)) { |
200 | 4 | return false; // Trailing non-space |
201 | 4 | } |
202 | 4 | pos++; |
203 | 4 | } |
204 | | |
205 | 2 | *result = v; |
206 | 2 | return true; // Trailing space is OK |
207 | 6 | } |
208 | | |
209 | 43 | int to_int(BigStr* s, int base) { |
210 | 43 | int i; |
211 | 43 | if (StringToInt(s->data_, len(s), base, &i)) { |
212 | 36 | return i; // truncated to int |
213 | 36 | } else { |
214 | 7 | throw Alloc<ValueError>(); |
215 | 7 | } |
216 | 43 | } |
217 | | |
218 | 1.34k | BigStr* chr(int i) { |
219 | | // NOTE: i should be less than 256, in which we could return an object from |
220 | | // GLOBAL_STR() pool, like StrIter |
221 | 1.34k | auto result = NewStr(1); |
222 | 1.34k | result->data_[0] = i; |
223 | 1.34k | return result; |
224 | 1.34k | } |
225 | | |
226 | 832 | int ord(BigStr* s) { |
227 | 832 | assert(len(s) == 1); |
228 | | // signed to unsigned conversion, so we don't get values like -127 |
229 | 0 | uint8_t c = static_cast<uint8_t>(s->data_[0]); |
230 | 832 | return c; |
231 | 832 | } |
232 | | |
233 | 4 | bool to_bool(BigStr* s) { |
234 | 4 | return len(s) != 0; |
235 | 4 | } |
236 | | |
237 | 8 | double to_float(int i) { |
238 | 8 | return static_cast<double>(i); |
239 | 8 | } |
240 | | |
241 | 26 | double to_float(BigStr* s) { |
242 | 26 | char* begin = s->data_; |
243 | 26 | char* end = begin + len(s); |
244 | | |
245 | 26 | errno = 0; |
246 | 26 | double result = strtod(begin, &end); |
247 | | |
248 | 26 | if (errno == ERANGE) { // error: overflow or underflow |
249 | 8 | if (result >= HUGE_VAL) { |
250 | 2 | return INFINITY; |
251 | 6 | } else if (result <= -HUGE_VAL) { |
252 | 2 | return -INFINITY; |
253 | 4 | } else if (-DBL_MIN <= result && result <= DBL_MIN) { |
254 | 4 | return 0.0; |
255 | 4 | } else { |
256 | 0 | FAIL("Invalid value after ERANGE"); |
257 | 0 | } |
258 | 8 | } |
259 | 18 | if (end == begin) { // error: not a floating point number |
260 | 4 | throw Alloc<ValueError>(); |
261 | 4 | } |
262 | | |
263 | 14 | return result; |
264 | 18 | } |
265 | | |
266 | | // e.g. ('a' in 'abc') |
267 | 84 | bool str_contains(BigStr* haystack, BigStr* needle) { |
268 | | // Common case |
269 | 84 | if (len(needle) == 1) { |
270 | 72 | return memchr(haystack->data_, needle->data_[0], len(haystack)); |
271 | 72 | } |
272 | | |
273 | 12 | if (len(needle) > len(haystack)) { |
274 | 2 | return false; |
275 | 2 | } |
276 | | |
277 | | // General case. TODO: We could use a smarter substring algorithm. |
278 | | |
279 | 10 | const char* end = haystack->data_ + len(haystack); |
280 | 10 | const char* last_possible = end - len(needle); |
281 | 10 | const char* p = haystack->data_; |
282 | | |
283 | 22 | while (p <= last_possible) { |
284 | 20 | if (memcmp(p, needle->data_, len(needle)) == 0) { |
285 | 8 | return true; |
286 | 8 | } |
287 | 12 | p++; |
288 | 12 | } |
289 | 2 | return false; |
290 | 10 | } |
291 | | |
292 | 93 | BigStr* str_repeat(BigStr* s, int times) { |
293 | | // Python allows -1 too, and Oil used that |
294 | 93 | if (times <= 0) { |
295 | 20 | return kEmptyString; |
296 | 20 | } |
297 | 73 | int len_ = len(s); |
298 | 73 | int new_len = len_ * times; |
299 | 73 | BigStr* result = NewStr(new_len); |
300 | | |
301 | 73 | char* dest = result->data_; |
302 | 956 | for (int i = 0; i < times; i++) { |
303 | 883 | memcpy(dest, s->data_, len_); |
304 | 883 | dest += len_; |
305 | 883 | } |
306 | 73 | return result; |
307 | 93 | } |
308 | | |
309 | | // for os_path.join() |
310 | | // NOTE(Jesse): Perfect candidate for BoundedBuffer |
311 | 22 | BigStr* str_concat3(BigStr* a, BigStr* b, BigStr* c) { |
312 | 22 | int a_len = len(a); |
313 | 22 | int b_len = len(b); |
314 | 22 | int c_len = len(c); |
315 | | |
316 | 22 | int new_len = a_len + b_len + c_len; |
317 | 22 | BigStr* result = NewStr(new_len); |
318 | 22 | char* pos = result->data_; |
319 | | |
320 | 22 | memcpy(pos, a->data_, a_len); |
321 | 22 | pos += a_len; |
322 | | |
323 | 22 | memcpy(pos, b->data_, b_len); |
324 | 22 | pos += b_len; |
325 | | |
326 | 22 | memcpy(pos, c->data_, c_len); |
327 | | |
328 | 22 | assert(pos + c_len == result->data_ + new_len); |
329 | | |
330 | 0 | return result; |
331 | 22 | } |
332 | | |
333 | 71 | BigStr* str_concat(BigStr* a, BigStr* b) { |
334 | 71 | int a_len = len(a); |
335 | 71 | int b_len = len(b); |
336 | 71 | int new_len = a_len + b_len; |
337 | 71 | BigStr* result = NewStr(new_len); |
338 | 71 | char* buf = result->data_; |
339 | | |
340 | 71 | memcpy(buf, a->data_, a_len); |
341 | 71 | memcpy(buf + a_len, b->data_, b_len); |
342 | | |
343 | 71 | return result; |
344 | 71 | } |
345 | | |
346 | | // |
347 | | // Comparators |
348 | | // |
349 | | |
350 | 2.20k | bool str_equals(BigStr* left, BigStr* right) { |
351 | | // Fast path for identical strings. String deduplication during GC could |
352 | | // make this more likely. String interning could guarantee it, allowing us |
353 | | // to remove memcmp(). |
354 | 2.20k | if (left == right) { |
355 | 171 | return true; |
356 | 171 | } |
357 | | |
358 | 2.03k | if (left == nullptr || right == nullptr) { |
359 | 0 | return false; |
360 | 0 | } |
361 | | |
362 | | // obj_len equal implies string lengths are equal |
363 | | |
364 | 2.03k | if (left->len_ == right->len_) { |
365 | | // assert(len(left) == len(right)); |
366 | 328 | return memcmp(left->data_, right->data_, left->len_) == 0; |
367 | 328 | } |
368 | | |
369 | 1.70k | return false; |
370 | 2.03k | } |
371 | | |
372 | 10 | bool maybe_str_equals(BigStr* left, BigStr* right) { |
373 | 10 | if (left && right) { |
374 | 4 | return str_equals(left, right); |
375 | 4 | } |
376 | | |
377 | 6 | if (!left && !right) { |
378 | 2 | return true; // None == None |
379 | 2 | } |
380 | | |
381 | 4 | return false; // one is None and one is a BigStr* |
382 | 6 | } |
383 | | |
384 | | // TODO(Jesse): Make an inline version of this |
385 | 1.83k | bool are_equal(BigStr* left, BigStr* right) { |
386 | 1.83k | return str_equals(left, right); |
387 | 1.83k | } |
388 | | |
389 | | // TODO(Jesse): Make an inline version of this |
390 | 40 | bool are_equal(int left, int right) { |
391 | 40 | return left == right; |
392 | 40 | } |
393 | | |
394 | | // TODO(Jesse): Make an inline version of this |
395 | 32.4k | bool keys_equal(int left, int right) { |
396 | 32.4k | return left == right; |
397 | 32.4k | } |
398 | | |
399 | | // TODO(Jesse): Make an inline version of this |
400 | 1.74k | bool keys_equal(BigStr* left, BigStr* right) { |
401 | 1.74k | return are_equal(left, right); |
402 | 1.74k | } |
403 | | |
404 | 8 | bool are_equal(Tuple2<BigStr*, int>* t1, Tuple2<BigStr*, int>* t2) { |
405 | 8 | bool result = are_equal(t1->at0(), t2->at0()); |
406 | 8 | result = result && (t1->at1() == t2->at1()); |
407 | 8 | return result; |
408 | 8 | } |
409 | | |
410 | 4 | bool are_equal(Tuple2<int, int>* t1, Tuple2<int, int>* t2) { |
411 | 4 | return t1->at0() == t2->at0() && t1->at1() == t2->at1(); |
412 | 4 | } |
413 | | |
414 | 4 | bool keys_equal(Tuple2<int, int>* t1, Tuple2<int, int>* t2) { |
415 | 4 | return are_equal(t1, t2); |
416 | 4 | } |
417 | | |
418 | 4 | bool keys_equal(Tuple2<BigStr*, int>* t1, Tuple2<BigStr*, int>* t2) { |
419 | 4 | return are_equal(t1, t2); |
420 | 4 | } |
421 | | |
422 | 5 | bool str_equals_c(BigStr* s, const char* c_string, int c_len) { |
423 | | // Needs SmallStr change |
424 | 5 | if (len(s) == c_len) { |
425 | 5 | return memcmp(s->data_, c_string, c_len) == 0; |
426 | 5 | } else { |
427 | 0 | return false; |
428 | 0 | } |
429 | 5 | } |
430 | | |
431 | 258 | bool str_equals0(const char* c_string, BigStr* s) { |
432 | 258 | int n = strlen(c_string); |
433 | 258 | if (len(s) == n) { |
434 | 155 | return memcmp(s->data_, c_string, n) == 0; |
435 | 155 | } else { |
436 | 103 | return false; |
437 | 103 | } |
438 | 258 | } |
439 | | |
440 | 4 | int hash(BigStr* s) { |
441 | 4 | return s->hash(fnv1); |
442 | 4 | } |
443 | | |
444 | 8 | int max(int a, int b) { |
445 | 8 | return std::max(a, b); |
446 | 8 | } |
447 | | |
448 | 0 | int min(int a, int b) { |
449 | 0 | return std::min(a, b); |
450 | 0 | } |
451 | | |
452 | 2 | int max(List<int>* elems) { |
453 | 2 | int n = len(elems); |
454 | 2 | if (n < 1) { |
455 | 0 | throw Alloc<ValueError>(); |
456 | 0 | } |
457 | | |
458 | 2 | int ret = elems->at(0); |
459 | 10 | for (int i = 0; i < n; ++i) { |
460 | 8 | int cand = elems->at(i); |
461 | 8 | if (cand > ret) { |
462 | 2 | ret = cand; |
463 | 2 | } |
464 | 8 | } |
465 | | |
466 | 2 | return ret; |
467 | 2 | } |