OILS / mycpp / gc_builtins.cc View on Github | oils.pub

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