OILS / mycpp / gc_builtins.cc View on Github | oilshell.org

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