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

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