Source
stdlib/builtins/builtins.hpp
1
// Copyright (c) 2026 BigBrain LLC. MIT-licensed (see LICENSE).2
// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.3
#pragma once5
/**6
* @file builtins.hpp7
* @brief cheatah `builtins` — Python's always-available built-ins (no `import`):8
* length, character/representation conversions, and hashing.9
*10
* The compiler auto-includes this header and resolves bare calls like `len("x")`11
* to `builtins::len`. The mathematical built-ins (`abs`/`min`/`max`/`round`/`pow`)12
* live in the `math` module. Unit tests: `stdlib/tests/builtins_test.cpp`; the13
* suite runs under AddressSanitizer (the `asan` preset) and Valgrind14
* (`security/run-valgrind.sh`) on every QA-gate run.15
*/16
#include <cmath>17
#include <concepts>18
#include <cstddef>19
#include <cstdint>20
#include <functional>21
#include <limits>22
#include <ostream>23
#include <sstream>24
#include <stdexcept>25
#include <string>26
#include <string_view>27
#include <type_traits>28
#include <unordered_map>29
#include <utility>30
#include <vector>32
namespace cheatah::builtins {34
/// Sized<C>: C reports a `.size()` — strings and STL containers (list/dict/array).35
template <typename C>36
concept Sized = requires(const C& c) {37
{ c.size() } -> std::convertible_to<std::size_t>;38
};40
/// Value<T>: a cheatah value — movable, so it can be stored, passed, and returned.41
/// This is the baseline concept purrc stamps on every emitted function/method42
/// parameter, so no cheatah code ever instantiates a fully unconstrained template43
/// (keeps compile errors comprehensible). See `constrain-all-templates` policy.44
template <typename T>45
concept Value = std::movable<std::remove_cvref_t<T>>;47
// ---- errors -------------------------------------------------------------------------------------48
//49
// `raise` throws an Error and `except` catches one. An Error carries a KIND alongside its message, so a50
// handler can select what it knows how to deal with (`except e of "index"`) and let everything else keep51
// travelling — which is the whole difference between recovering from a failure and swallowing one.52
//53
// The kind is a plain string, not a class hierarchy, because cheatah has no inheritance: "is-a" is a54
// concept, and a runtime taxonomy of errors is a discriminated value, not a base class. Kinds are open —55
// any string works — so a library can name its own failures without every caller having to know them.56
//57
// An Error is still a `str` wherever one is expected: it converts and compares as its MESSAGE, so58
// `io.print(e)` and `e == "boom"` read exactly as they did when a handler bound a bare string.60
/// Conventional kinds raised from the language core. Libraries are free to define their own.61
inline constexpr const char* kErrorKindError = "error"; ///< `raise "msg"` — unclassified62
inline constexpr const char* kErrorKindIndex = "index"; ///< subscript out of range63
inline constexpr const char* kErrorKindKey = "key"; ///< dict key absent64
inline constexpr const char* kErrorKindArithmetic = "arithmetic"; ///< divide / modulo by zero65
inline constexpr const char* kErrorKindUnknown = "unknown"; ///< a throw of a type we cannot inspect67
/**68
* A raised error: a `kind` naming what went wrong and a human `message`.69
*70
* Derives from `std::runtime_error` so it interoperates with C++ code that catches `std::exception` —71
* that inheritance is a C++ implementation detail and is not visible from cheatah, where an Error is an72
* ordinary value with two string fields.73
*/74
class Error : public std::runtime_error {75
public:76
/**77
* An unclassified error — what `raise "msg"` builds. Kind is @ref kErrorKindError.78
* @param message the human-readable description.79
* @complexity O(message).80
* @alloc copies the message (twice: the base class keeps its own).81
* @test CheatahBuiltins.ErrorCarriesKindAndMessage82
* @crtest PurrcPipeline.CompilesAndRunsTryExceptRaise83
*/84
explicit Error(std::string message)85
: std::runtime_error(message), kind_(kErrorKindError), message_(std::move(message)) {}87
/**88
* A classified error — what `raise Error("kind", "msg")` builds.89
* @param kind the open-ended kind string a handler selects on (`except e of "kind"`).90
* @param message the human-readable description.91
* @complexity O(kind + message).92
* @alloc copies both strings.93
* @test CheatahBuiltins.ErrorCarriesKindAndMessage94
*/95
Error(std::string kind, std::string message)96
: std::runtime_error(message), kind_(std::move(kind)), message_(std::move(message)) {}98
/**99
* @brief What CLASS of failure this is — the string `except … of` matches against.100
* @return the kind, by const reference; never empty for an Error built through these constructors.101
* @complexity O(1).102
* @alloc none.103
* @test CheatahBuiltins.ErrorCarriesKindAndMessage104
*/105
const std::string& kind() const noexcept { return kind_; }107
/**108
* @brief The human-readable description. This is also what @ref str and `operator<<` yield, so a109
* caught error prints as its message rather than as a struct.110
* @return the message, by const reference.111
* @complexity O(1).112
* @alloc none.113
* @test CheatahBuiltins.ErrorCarriesKindAndMessage114
*/115
const std::string& message() const noexcept { return message_; }117
// Deliberately NOT implicitly convertible to std::string. It would read nicely, but `str()` is a118
// heavily overloaded set and an implicit conversion makes half of it ambiguous the moment an Error119
// is printed. The `str` overload and the comparisons below give the same ergonomics explicitly.121
private:122
std::string kind_;123
std::string message_;124
};126
/**127
* @brief Compare an error against a string — by MESSAGE, so `e == "boom"` reads the way it did when a128
* handler bound a bare string. Compare `e.kind()` when you mean the kind.129
* @param e the error.130
* @param s the message to compare against.131
* @return true when the error's message is exactly @p s.132
* @complexity O(min(len)).133
* @alloc none.134
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage135
*/136
inline bool operator==(const Error& e, const std::string& s) { return e.message() == s; }138
/** @brief Message comparison, arguments reversed.139
* @param s the message to compare against.140
* @param e the error.141
* @return true when the error's message is exactly @p s.142
* @complexity O(min(len)). @alloc none.143
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage */144
inline bool operator==(const std::string& s, const Error& e) { return e.message() == s; }146
/** @brief Message comparison against a string literal.147
* @param e the error.148
* @param s the NUL-terminated message to compare against.149
* @return true when the error's message is exactly @p s.150
* @complexity O(min(len)). @alloc none.151
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage */152
inline bool operator==(const Error& e, const char* s) { return e.message() == s; }154
/** @brief Message comparison against a string literal, arguments reversed.155
* @param s the NUL-terminated message to compare against.156
* @param e the error.157
* @return true when the error's message is exactly @p s.158
* @complexity O(min(len)). @alloc none.159
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage */160
inline bool operator==(const char* s, const Error& e) { return e.message() == s; }162
/** @brief Stream an error as its MESSAGE — the kind would be noise in output that wanted the sentence.163
* @param os the destination stream.164
* @param e the error.165
* @return @p os, for chaining.166
* @complexity O(message). @alloc none beyond the stream's own.167
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage */168
inline std::ostream& operator<<(std::ostream& os, const Error& e) { return os << e.message(); }170
/**171
* The error currently being handled, normalized to an @ref Error.172
*173
* Called from inside a `catch (...)`, where `throw;` re-raises the in-flight exception so it can be174
* inspected by type. This is what lets ONE handler shape cover a raised Error, a `std::exception` from175
* any C++ library, and a throw of some type we have never heard of — the last of which used to travel176
* straight past every handler and abort the process.177
*178
* @return the in-flight exception as an Error: a raised Error verbatim, a `std::out_of_range` as kind179
* "index", a `std::domain_error` as "arithmetic", any other `std::exception` as "error", and180
* anything else as "unknown".181
* @complexity O(1) plus the message copy.182
* @alloc copies the kind and message.183
* @test CheatahBuiltins.CurrentErrorNormalizesEveryThrownType184
* @crtest PurrcPipeline.CompilesAndRunsTryExceptRaise185
*/186
inline Error current_error() {187
try {188
throw;189
} catch (const Error& e) {190
return e;191
} catch (const std::out_of_range& e) {192
return Error(kErrorKindIndex, e.what());193
} catch (const std::domain_error& e) {194
return Error(kErrorKindArithmetic, e.what());195
} catch (const std::exception& e) {196
return Error(kErrorKindError, e.what());197
} catch (...) {198
return Error(kErrorKindUnknown, "unknown error");199
}200
}202
/// Runs its action when the scope ends, however it ends — the body of a `finally`.203
template <std::invocable F>204
class Finally {205
public:206
/**207
* @brief Take ownership of the action to run at scope exit.208
* @param f the callable to invoke from the destructor.209
* @complexity O(1).210
* @alloc moves @p f into the guard.211
* @test CheatahBuiltins.FinallyRunsOnEveryExitPath212
*/213
explicit Finally(F f) : f_(std::move(f)) {}214
Finally(const Finally&) = delete;215
Finally& operator=(const Finally&) = delete;217
/**218
* @brief Run the action. Reached on every exit path — normal fall-through, `return`, `break`, or an219
* exception unwinding through the scope, which is the whole point of a guard over a220
* duplicated block.221
* @complexity that of the action.222
* @alloc that of the action.223
* @test CheatahBuiltins.FinallyRunsOnEveryExitPath224
* @test CheatahBuiltins.FinallySwallowsItsOwnThrowDuringUnwinding225
*/226
~Finally() {227
// A `finally` that throws while an exception is already unwinding would terminate the process,228
// which is a worse outcome than losing the second error — so it is swallowed here.229
// (The handler is one line deliberately: Finally is a template, so an instantiation whose230
// action cannot throw leaves a standalone `}` that no test can ever reach. The swallow itself231
// IS covered — see CheatahBuiltins.FinallySwallowsItsOwnThrowDuringUnwinding.)232
try {233
f_();234
} catch (...) {} // NOLINT(bugprone-empty-catch) — swallowing is the documented contract235
}237
private:238
F f_;239
};241
/**242
* @brief Build a scope guard around @p f — how `finally { … }` lowers.243
* @param f the callable to run when the enclosing scope ends.244
* @return the guard; keep it alive for the scope you want covered.245
* @complexity O(1).246
* @alloc moves @p f into the returned guard.247
* @test CheatahBuiltins.FinallyRunsOnEveryExitPath248
*/249
template <std::invocable F>250
Finally<F> make_finally(F f) {251
return Finally<F>(std::move(f));252
}254
/**255
* Length / element count.256
*257
* Forwards to the container's `.size()`; for strings this is the byte length,258
* not a Unicode code-point count.259
* @param c a string or sized container.260
* @return `c.size()`.261
* @complexity O(1).262
* @alloc none.263
* @test CheatahBuiltins.LenOrdChr264
* @crtest BuiltinsCompileRun.Len265
* @systest StdlibE2E.Builtins266
*/267
template <Sized C>268
std::size_t len(const C& c) { return c.size(); }269
/**270
* Length of a C-string / string literal.271
*272
* Returns the byte length of the view; any embedded NUL bytes are counted (the273
* length comes from the view, not from a terminating NUL).274
* @param s the string.275
* @return its byte length.276
* @complexity O(1).277
* @alloc none.278
* @test CheatahBuiltins.LenOrdChr279
* @crtest BuiltinsCompileRun.Len280
* @systest StdlibE2E.Builtins281
*/282
std::size_t len(std::string_view s);284
/**285
* Code point of the first byte.286
*287
* Returns the unsigned value of `s[0]` (0–255), ignoring trailing bytes;288
* an empty string yields 0 rather than throwing.289
* @param s a one-character string.290
* @return its byte value (0 if empty).291
* @complexity O(1).292
* @alloc none.293
* @test CheatahBuiltins.LenOrdChr294
* @crtest BuiltinsCompileRun.Ord295
* @systest StdlibE2E.Builtins296
*/297
int ord(std::string_view s);299
/**300
* ord() of a single char — what iterating a string yields (`for ch in s`), so ord(ch)301
* works inside such loops.302
* @param c the character (a single byte).303
* @return its unsigned byte value (0–255).304
* @complexity O(1). @alloc none. @test CheatahBuiltins.Ord305
* @crtest LangFeatures.Modulo306
*/307
constexpr int ord(char c) { return static_cast<unsigned char>(c); }308
/**309
* Character for a code point.310
*311
* Builds a one-byte string from the low 8 bits of @p codepoint (it is narrowed312
* to `char`), so values outside 0–255 wrap modulo 256 rather than producing313
* multi-byte output.314
* @param codepoint a byte value.315
* @return the one-character string.316
* @complexity O(1).317
* @alloc none (1-char small-string optimization).318
* @test CheatahBuiltins.LenOrdChr319
* @crtest BuiltinsCompileRun.Chr320
* @systest StdlibE2E.Builtins321
*/322
std::string chr(int codepoint);324
/**325
* Hex representation.326
*327
* Formats @p value in base 16 with lowercase digits and a `0x` prefix; negatives328
* are rendered as a leading `-` before the prefix (e.g. `-0x1f`), and 0 is `0x0`.329
* @param value the integer.330
* @return `"0x…"` (with sign).331
* @complexity O(log @p value).332
* @alloc allocates the result string, built from a temporary digits buffer.333
* @test CheatahBuiltins.BaseReprs334
* @crtest BuiltinsCompileRun.Hex335
* @systest StdlibE2E.Builtins336
*/337
std::string hex(long long value);338
/**339
* Octal representation.340
*341
* Formats @p value in base 8 with a `0o` prefix; negatives get a leading `-`342
* before the prefix (e.g. `-0o17`), and 0 is `0o0`.343
* @param value the integer.344
* @return `"0o…"` (with sign).345
* @complexity O(log @p value).346
* @alloc allocates the result string, built from a temporary digits buffer.347
* @test CheatahBuiltins.BaseReprs348
* @crtest BuiltinsCompileRun.Oct349
* @systest StdlibE2E.Builtins350
*/351
std::string oct(long long value);352
/**353
* Binary representation.354
*355
* Formats @p value in base 2 with a `0b` prefix; negatives get a leading `-`356
* before the prefix (e.g. `-0b101`), and 0 is `0b0`.357
* @param value the integer.358
* @return `"0b…"` (with sign).359
* @complexity O(log @p value).360
* @alloc allocates the result string, built from a temporary digits buffer.361
* @test CheatahBuiltins.BaseReprs362
* @crtest BuiltinsCompileRun.Bin363
* @systest StdlibE2E.Builtins364
*/365
std::string bin(long long value);367
/**368
* Printable-ASCII repr (non-printables/`\`/`'` escaped, single-quoted).369
*370
* Wraps @p s in single quotes, passing through printable ASCII (bytes 32–126)371
* verbatim while escaping `\` and `'` as `\\`/`\'` and emitting any other byte as372
* a two-digit `\xHH` hex escape.373
* @param s input.374
* @return the quoted repr.375
* @complexity O(n).376
* @alloc allocates the result string, plus a temporary ostringstream per escaped byte.377
* @test CheatahBuiltins.Ascii378
* @crtest BuiltinsCompileRun.Ascii379
* @systest StdlibE2E.Builtins380
*/381
std::string ascii(std::string_view s);383
/**384
* Truthiness of a string.385
*386
* Truthy iff non-empty; a whitespace-only or `"0"`/`"false"` string is still387
* truthy (only emptiness is false).388
* @param s input.389
* @return false iff @p s is empty.390
* @complexity O(1).391
* @alloc none.392
* @test CheatahBuiltins.Conversions393
* @crtest BuiltinsCompileRun.BoolFromString394
* @systest StdlibE2E.Builtins395
*/396
bool to_bool(std::string_view s);397
/**398
* Truthiness of a number.399
* @param x any arithmetic value.400
* @return @p x != 0.401
* @complexity O(1).402
* @alloc none.403
* @test CheatahBuiltins.Conversions404
* @crtest BuiltinsCompileRun.BoolFromNonzero405
* @systest StdlibE2E.Builtins406
*/407
template <typename T>408
requires std::is_arithmetic_v<T>409
bool to_bool(T x) { return x != T{}; }410
/**411
* Parse a base-10 integer.412
*413
* Parses leading whitespace and an optional sign followed by decimal digits via414
* `std::stoll`; it stops at the first non-digit (so trailing junk is ignored),415
* throws on no parseable digits, and throws on out-of-range values.416
* @param s the integer string.417
* @return its value (throws on bad input).418
* @complexity O(n).419
* @alloc allocates a temporary `std::string` for the parse.420
* @test CheatahBuiltins.Conversions421
* @crtest BuiltinsCompileRun.IntFromString422
* @systest StdlibE2E.Builtins423
*/424
long long to_int(std::string_view s);425
/**426
* Truncate a double to an integer.427
*428
* Truncates toward zero (drops the fractional part rather than rounding), so429
* `2.9` becomes 2 and `-2.9` becomes -2; values outside `long long` range are430
* undefined behavior.431
* @param x the value.432
* @return @p x toward zero.433
* @complexity O(1).434
* @alloc none.435
* @warning @p x outside `long long`'s range (or NaN) is undefined behavior — no clamp or check.436
* @test CheatahBuiltins.Conversions437
* @crtest BuiltinsCompileRun.IntFromFloat438
* @systest StdlibE2E.Builtins439
*/440
long long to_int(double x);441
/**442
* Parse a float.443
*444
* Parses leading whitespace and a floating-point literal via `std::stod`,445
* accepting decimal, scientific (`1e9`), `inf`, and `nan` forms; it stops at the446
* first unparsed character, throws when nothing parses, and throws on overflow.447
* @param s a floating-point string.448
* @return its value (throws on bad input).449
* @complexity O(n).450
* @alloc allocates a temporary `std::string` for the parse.451
* @test CheatahBuiltins.Conversions452
* @crtest BuiltinsCompileRun.FloatFromString453
* @systest StdlibE2E.Builtins454
*/455
double to_float(std::string_view s);456
/// Number: any built-in arithmetic type — every width float() accepts numerically.457
template <typename T>458
concept Number = std::is_arithmetic_v<T>;459
/**460
* `float()` of any NUMBER — one widening/identity conversion for every arithmetic type, so461
* overload resolution can never route a `double` (or an `i32`) through an integer overload462
* and silently TRUNCATE: `float(0.95)` must be 0.95, never 0.463
* @tparam T the arithmetic source type (`Number`).464
* @param x the value.465
* @return @p x as a `double`.466
* @complexity O(1).467
* @alloc none.468
* @test CheatahBuiltins.ToFloatFromInt469
* @test CheatahBuiltins.ToFloatFromFloat470
* @crtest BuiltinsCompileRun.FloatFromInt471
* @crtest BuiltinsCompileRun.FloatFromFloat472
* @systest StdlibE2E.Builtins473
*/474
template <Number T>475
constexpr double to_float(T x) { return static_cast<double>(x); }477
/// Streamable<T>: T can be written to a `std::ostream` with `operator<<` — the requirement478
/// for str() to render it. (Mirrors io's Printable, so bare `str(x)` and `io.str(x)` agree.)479
template <typename T>480
concept Streamable = requires(std::ostream& os, const T& v) {481
{ os << v } -> std::convertible_to<std::ostream&>;482
};484
/**485
* Python `str()`: stringify any streamable value (an always-available built-in, so it needs486
* no `import` — bare `str(x)` resolves here, like `int()`/`float()`/`bool()`).487
*488
* Renders @p value via its `operator<<` into a fresh `ostringstream`, so the text matches489
* whatever that stream insertion produces (e.g. default 6-significant-digit float precision),490
* agreeing with `io.print`/`io.str`.491
* @param value the value to render.492
* @return @p value formatted as text.493
* @complexity O(n) in the output length.494
* @alloc allocates the result string (via an ostringstream).495
* @test CheatahBuiltins.Str496
* @crtest BuiltinsCompileRun.Str497
* @systest StdlibE2E.Builtins498
*/499
template <Streamable T>500
std::string str(const T& value) {501
std::ostringstream os;502
os << value;503
return os.str();504
}506
/**507
* `str()` for a bool — Python's capitalized spelling.508
*509
* Overrides the default streaming of a bool (`1`/`0`) to emit `True`/`False`, matching510
* `io.str` and `io.print`.511
* @param b the boolean.512
* @return `"True"` or `"False"`.513
* @complexity O(1).514
* @alloc allocates the small result string.515
* @test CheatahBuiltins.Str516
* @crtest BuiltinsCompileRun.Str517
* @systest StdlibE2E.Builtins518
*/519
inline std::string str(bool b) { return b ? "True" : "False"; }521
/**522
* `str()` of an error is its MESSAGE — printing a caught error says what went wrong, without the kind523
* turning up uninvited in output that only wanted the sentence. Reach for `.kind()` when you want it.524
* @param e the error to render.525
* @return the error's message.526
* @complexity O(message).527
* @alloc copies the message.528
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage529
*/530
inline std::string str(const Error& e) { return e.message(); }532
/**533
* `str()` for the byte-width integers `i8`/`u8` (`std::int8_t`/`std::uint8_t`, which are534
* typedefs of `signed char`/`unsigned char`). Streaming a `char`-sized type would print a535
* CHARACTER; these overloads promote to a wider integer first so `i8`/`u8` render as NUMBERS —536
* the one seam through which `repr`, `print`, and container `str`/`repr` all inherit the fix.537
* Plain `char` is a distinct type (cheatah has no bare-`char` value type — single chars are538
* 1-char `std::string`), so it is deliberately not matched here.539
* @param v the `i8` value to render.540
* @return the value's decimal digits.541
* @complexity O(1).542
* @alloc allocates the small result string.543
* @test CheatahBuiltins.StrByteWidthIntsAreNumbers544
*/545
inline std::string str(signed char v) { return std::to_string(static_cast<int>(v)); }546
/**547
* `str()` for `u8` (`std::uint8_t`) — numeric, not a character. See @ref str(signed char).548
* @param v the `u8` value to render.549
* @return the value's decimal digits.550
* @complexity O(1).551
* @alloc allocates the small result string.552
* @test CheatahBuiltins.StrByteWidthIntsAreNumbers553
*/554
inline std::string str(unsigned char v) { return std::to_string(static_cast<unsigned>(v)); }556
/**557
* True division — the cheatah `/` operator (like Python 3): **always floating-point**,558
* so `6 / 2` is `3.0`, not `3`, and integer operands never silently truncate. Use the559
* `//` operator (@ref floordiv) when you want integer/floor division.560
* @param a numerator.561
* @param b denominator.562
* @return `double(a) / double(b)`.563
* @complexity O(1).564
* @alloc none.565
* @test CheatahBuiltins.Division566
* @crtest BuiltinsCompileRun.TrueDivision567
* @systest StdlibE2E.Builtins568
*/569
template <typename A, typename B>570
requires std::is_arithmetic_v<A> && std::is_arithmetic_v<B>571
double truediv(A a, B b) {572
return static_cast<double>(a) / static_cast<double>(b);573
}574
/**575
* Floor division — the cheatah `//` operator (like Python): the quotient floored toward576
* −∞. Integer operands give an integer (`7 // 2 == 3`, `-7 // 2 == -4`, flooring the way577
* Python does, not truncating toward zero like raw C++); a floating operand gives a578
* floored double (`7.0 // 2 == 3.0`).579
* @param a numerator.580
* @param b denominator; @p b == 0 throws `std::domain_error` (integer floor division by zero).581
* @return `floor(a / b)`, integral for integral operands.582
* @complexity O(1).583
* @alloc none.584
* @test CheatahBuiltins.Division585
* @test CheatahBuiltins.IntegerDivideAndModuloByZeroThrow586
* @crtest BuiltinsCompileRun.FloorDivision587
* @systest StdlibE2E.Builtins588
*/589
template <std::integral A, std::integral B>590
std::common_type_t<A, B> floordiv(A a, B b) {591
// A controlled error, not UB: integer divide-by-zero is undefined in C++ (SIGFPE/trap), so guard592
// it so pure-cheatah `x // 0` raises rather than corrupting the process. (Float `//` is IEEE-safe.)593
if (b == 0) throw std::domain_error("integer floor division by zero");594
std::common_type_t<A, B> q = a / b; // C++ truncates toward zero…595
if ((a % b != 0) && ((a < 0) != (b < 0))) --q; // …adjust to floor toward −∞596
return q;597
}598
/**599
* Floor division (`//`) for floating-point operands: floors the quotient toward −∞.600
*601
* Selected when at least one operand is floating-point (the all-integer case uses the602
* @ref floordiv overload above). Mirrors Python, where `7.0 // 2.0 == 3.0`.603
* @param a numerator.604
* @param b denominator.605
* @return `std::floor(double(a) / double(b))`.606
* @complexity O(1).607
* @alloc none.608
* @test CheatahBuiltins.Division609
* @crtest BuiltinsCompileRun.FloorDivision610
* @systest StdlibE2E.Builtins611
*/612
template <typename A, typename B>613
requires(std::is_arithmetic_v<A> && std::is_arithmetic_v<B> &&614
!(std::integral<A> && std::integral<B>))615
double floordiv(A a, B b) {616
return std::floor(static_cast<double>(a) / static_cast<double>(b));617
}619
/**620
* Content hash of a string.621
*622
* Hashes the bytes via `std::hash<std::string_view>` (equal contents hash623
* equally); the value is implementation-defined and unstable across runs and624
* compilers (do not persist it).625
* @param s input.626
* @return a `std::size_t` hash.627
* @complexity O(n).628
* @alloc none.629
* @test CheatahBuiltins.Hash630
* @systest StdlibE2E.Builtins631
* @note No @crtest: compile-run coverage is intentionally skipped because the632
* hash value is implementation-defined and has no portable expected stdout.633
*/634
std::size_t hash(std::string_view s);635
/**636
* Hash of any hashable value.637
*638
* Defers to `std::hash<T>` for the static type of @p x, so it requires a639
* specialization to exist for `T`; like the string overload, the result is640
* implementation-defined and unstable across runs.641
* @param x the value.642
* @return `std::hash<T>{}(x)`.643
* @complexity O(1) for scalars.644
* @alloc none.645
* @test CheatahBuiltins.Hash646
* @systest StdlibE2E.Builtins647
* @note No @crtest: compile-run coverage is intentionally skipped because the648
* hash value is implementation-defined and has no portable expected stdout.649
*/650
template <typename T>651
requires requires(const T& x) { std::hash<T>{}(x); }652
std::size_t hash(const T& x) { return std::hash<T>{}(x); }654
// ---- collection + method-style helpers ----655
//656
// These power cheatah's growable lists and the method-call syntax `obj.f(a)`,657
// which lowers to `cheatah::builtins::f(obj, a)`. Free-function form works too:658
// `append(xs, x)` and `xs.append(x)` are the same call.660
/**661
* Append @p x to list @p v in place (Python `list.append`).662
*663
* Grows @p v by one, converting @p x to the list's element type. Usable as a664
* method (`xs.append(x)`) or a bare call (`append(xs, x)`); the list is taken by665
* reference, so the caller's list is mutated.666
* @param v the list to grow.667
* @param x the value to append.668
* @complexity amortized O(1).669
* @alloc reallocates @p v when it outgrows its capacity.670
* @test CheatahBuiltins.Append671
* @crtest LangFeatures.AppendAndDictMutation672
* @systest StdlibE2E.Builtins673
*/674
template <typename T, typename U>675
requires std::convertible_to<std::remove_cvref_t<U>, T>676
void append(std::vector<T>& v, U&& x) {677
v.push_back(static_cast<T>(std::forward<U>(x)));678
}680
/**681
* Whether @p s begins with @p prefix (Python `str.startswith`).682
* @param s the string.683
* @param prefix the prefix to test.684
* @return true iff @p s starts with @p prefix.685
* @complexity O(len(@p prefix)).686
* @alloc none.687
* @test CheatahBuiltins.StringPredicates688
* @crtest LangFeatures.MethodPredicates689
* @systest StdlibE2E.Builtins690
*/691
inline bool startswith(std::string_view s, std::string_view prefix) {692
return s.size() >= prefix.size() && s.compare(0, prefix.size(), prefix) == 0;693
}695
/**696
* Whether @p s ends with @p suffix (Python `str.endswith`).697
* @param s the string.698
* @param suffix the suffix to test.699
* @return true iff @p s ends with @p suffix.700
* @complexity O(len(@p suffix)).701
* @alloc none.702
* @test CheatahBuiltins.StringPredicates703
* @crtest LangFeatures.MethodPredicates704
* @systest StdlibE2E.Builtins705
*/706
inline bool endswith(std::string_view s, std::string_view suffix) {707
return s.size() >= suffix.size() &&708
s.compare(s.size() - suffix.size(), suffix.size(), suffix) == 0;709
}711
/**712
* Whether @p sub occurs anywhere in @p s (Python `sub in s`).713
* @param s the string to search.714
* @param sub the substring to find.715
* @return true iff @p sub is a substring of @p s.716
* @complexity O(len(@p s) · len(@p sub)) worst case.717
* @alloc none.718
* @test CheatahBuiltins.StringPredicates719
* @crtest LangFeatures.MethodPredicates720
* @systest StdlibE2E.Builtins721
*/722
inline bool contains(std::string_view s, std::string_view sub) {723
return s.find(sub) != std::string_view::npos;724
}726
/**727
* Membership test for a dict: is @p key present? Backs the `in` operator (`k in d`).728
* @param d the dict to search.729
* @param key the key to look for.730
* @return true iff @p key is present in @p d.731
* @complexity O(1) average.732
* @alloc none.733
* @crtest LangFeatures.InOperator734
*/735
template <class K, class V, class H, class E, class A, class Key>736
bool contains(const std::unordered_map<K, V, H, E, A>& d, const Key& key) {737
return d.count(key) != 0;738
}740
/**741
* Membership test for a list: does any element equal @p value? Backs `x in xs`.742
* @param xs the list to scan.743
* @param value the value to look for.744
* @return true iff some element of @p xs compares equal to @p value.745
* @complexity O(n).746
* @alloc none.747
* @crtest LangFeatures.InOperator748
*/749
template <class T, class A, class Value>750
bool contains(const std::vector<T, A>& xs, const Value& value) {751
for (const T& x : xs) {752
if (x == value) return true;753
}754
return false;755
}757
/**758
* Python FLOOR-mod for integers: the result takes the DIVISOR's sign (-7 % 3 == 2), unlike759
* raw C++ `%`. Backs the `%` operator.760
* @param a the dividend.761
* @param b the divisor; @p b == 0 throws std::domain_error (integer modulo by zero).762
* @return a mod b with the sign of @p b (Python floor-mod semantics).763
* @complexity O(1).764
* @alloc none.765
* @test CheatahBuiltins.Mod766
* @test CheatahBuiltins.IntegerDivideAndModuloByZeroThrow767
* @crtest LangFeatures.Modulo768
*/769
template <class A, class B>770
requires(std::is_integral_v<A> && std::is_integral_v<B>)771
std::common_type_t<A, B> mod(A a, B b) {772
using R = std::common_type_t<A, B>;773
// A controlled error, not UB: integer `% 0` is undefined in C++ (SIGFPE/trap) — guard it so774
// pure-cheatah `x % 0` raises rather than corrupting the process. (Float `%` is IEEE-safe.)775
if (b == 0) throw std::domain_error("integer modulo by zero");776
const R r = static_cast<R>(a) % static_cast<R>(b);777
return (r != 0 && ((r < 0) != (b < 0))) ? r + static_cast<R>(b) : r;778
}780
/**781
* Python floor-mod for floats (either operand): fmod adjusted to the divisor's sign,782
* mirroring `7.5 % 2 == 1.5` and `-7.5 % 2 == 0.5`.783
* @param a the dividend.784
* @param b the divisor.785
* @return a mod b as a double, with the sign of @p b (Python floor-mod semantics).786
* @complexity O(1).787
* @alloc none.788
* @test CheatahBuiltins.Mod789
* @crtest LangFeatures.Modulo790
*/791
template <class A, class B>792
requires(!std::is_integral_v<A> || !std::is_integral_v<B>)793
double mod(A a, B b) {794
const double r = std::fmod(static_cast<double>(a), static_cast<double>(b));795
return (r != 0.0 && ((r < 0.0) != (static_cast<double>(b) < 0.0))) ? r + static_cast<double>(b)796
: r;797
}799
// ---- indexing & slicing (Python `seq[i]` / `seq[i:j]`) ----800
//801
// The compiler lowers value-position `seq[i]` to `index(seq, i)` and `seq[a:b]`802
// to `slice(seq, a, b)` (a missing bound becomes 0 / `slice_end`). Indices may be803
// negative (counted from the end). Indexing a string yields a length-1 string804
// (Python semantics), so `s[i] == "<"` type-checks; slicing yields the same kind.806
/// Sentinel for an omitted slice upper bound (`s[a:]`): "to the end".807
inline constexpr long long slice_end = std::numeric_limits<long long>::max();809
namespace detail {810
inline long long norm_index(long long i, long long n) { return i < 0 ? i + n : i; }811
} // namespace detail813
/**814
* Element at @p i of a string — a length-1 string (Python `s[i]`).815
* Negative @p i counts from the end; out-of-range throws `std::out_of_range`.816
* @param s the string.817
* @param i the index (may be negative).818
* @return the one-character string at @p i.819
* @complexity O(1).820
* @alloc none (1-char small-string optimization).821
* @test CheatahBuiltins.IndexString822
* @crtest LangFeatures.StringSlicingAndIndex823
* @systest StdlibE2E.Builtins824
*/825
inline std::string index(const std::string& s, long long i) {826
const long long n = static_cast<long long>(s.size());827
i = detail::norm_index(i, n);828
if (i < 0 || i >= n) throw std::out_of_range("string index out of range");829
return std::string(1, s[static_cast<std::size_t>(i)]);830
}832
/**833
* Element at @p i of a list/array (Python `xs[i]`), by CONST REFERENCE.834
* Negative @p i counts from the end; out-of-range throws `std::out_of_range`.835
*836
* Returning a reference — not a copy — is what makes `xs[i].field` free: reading one field of a837
* heap-owning element (a struct with strings/lists) no longer deep-copies the whole element. Value838
* semantics are UNCHANGED at the `.purr` level, because codegen binds a subscript with plain `auto`839
* (`let e = xs[i]` still copies), and the const-ness preserves cheatah's "list elements are840
* read-only" rule — whole-element `xs[i] = v` assignment goes through a different path.841
*842
* Lifetime: the reference is into @p c, so it is valid as long as @p c is and is not mutated.843
* Subscripting a temporary container is safe in the expression that does it (the temporary outlives844
* the full-expression); binding that reference to a name that outlives the statement is not, and845
* codegen never emits such a binding.846
* @param c the sequence.847
* @param i the index (may be negative).848
* @return a const reference to the element at @p i.849
* @complexity O(1).850
* @alloc none.851
* @test CheatahBuiltins.IndexList852
* @crtest LangFeatures.ListSlicingAndIndex853
* @systest StdlibE2E.Builtins854
*/855
template <typename C>856
requires requires(const C& c) { c.data(); c.size(); } // contiguous seq (vector/array), not a map857
auto index(const C& c, long long i) -> const std::decay_t<decltype(c[0])>& {858
const long long n = static_cast<long long>(c.size());859
i = detail::norm_index(i, n);860
if (i < 0 || i >= n) throw std::out_of_range("index out of range");861
return c[static_cast<std::size_t>(i)];862
}864
/**865
* Element at @p i of a `list[bool]` (Python `xs[i]`), by value.866
* `std::vector<bool>` is the one sequence type the contiguous overload above867
* cannot accept: it is bit-packed, so it has proxy references and no `.data()`.868
* Same semantics — negative @p i counts from the end; out-of-range throws.869
* @param c the bool list.870
* @param i the index (may be negative).871
* @return the element at @p i.872
* @complexity O(1).873
* @alloc none.874
* @test CheatahBuiltins.IndexBoolList875
* @crtest BuiltinsCompileRun.IndexBoolList876
* @systest StdlibE2E.Builtins877
*/878
inline bool index(const std::vector<bool>& c, long long i) {879
const long long n = static_cast<long long>(c.size());880
i = detail::norm_index(i, n);881
if (i < 0 || i >= n) throw std::out_of_range("index out of range");882
return c[static_cast<std::size_t>(i)];883
}885
/**886
* Value for @p key in a dict (Python `d[key]`), by CONST REFERENCE.887
* Same rationale and lifetime rules as the sequence overload above: `d[key].field` stops888
* deep-copying the mapped value, while `let v = d[key]` still copies.889
* @param m the dict.890
* @param key the key to look up.891
* @return a const reference to the mapped value; an absent key raises kind `"key"`, which is distinct892
* from the `"index"` a sequence subscript raises — a missing dict entry and a walked-off-the-end893
* list are different mistakes and a handler should be able to take one without the other.894
* @complexity O(1) average.895
* @alloc none.896
* @test CheatahBuiltins.IndexDict897
* @crtest LangFeatures.AppendAndDictMutation898
* @systest StdlibE2E.Builtins899
*/900
template <typename K, typename V, typename H, typename E, typename A, typename Key>901
requires requires(const std::unordered_map<K, V, H, E, A>& m, const Key& key) { m.find(key); }902
const V& index(const std::unordered_map<K, V, H, E, A>& m, const Key& key) {903
const auto it = m.find(key);904
if (it == m.end()) throw Error(kErrorKindKey, "key not found");905
return it->second;906
}908
/**909
* Substring `s[lo:hi]` (Python slice semantics: clamped, negatives from the end).910
* @param s the string.911
* @param lo start index (default 0 at the call site).912
* @param hi end index, or @ref slice_end for "to the end".913
* @return the slice (empty if `lo >= hi` after clamping).914
* @complexity O(hi-lo).915
* @alloc the result string.916
* @test CheatahBuiltins.SliceString917
* @crtest LangFeatures.StringSlicingAndIndex918
* @systest StdlibE2E.Builtins919
*/920
inline std::string slice(const std::string& s, long long lo, long long hi) {921
const long long n = static_cast<long long>(s.size());922
lo = detail::norm_index(lo, n);923
hi = (hi == slice_end) ? n : detail::norm_index(hi, n);924
if (lo < 0) lo = 0;925
if (hi > n) hi = n;926
if (lo >= hi) return std::string();927
return s.substr(static_cast<std::size_t>(lo), static_cast<std::size_t>(hi - lo));928
}930
/**931
* Sub-list `xs[lo:hi]` (Python slice semantics), returned as a new list.932
* @param c the sequence.933
* @param lo start index.934
* @param hi end index, or @ref slice_end for "to the end".935
* @return the slice as a `std::vector` of the element type.936
* @complexity O(hi-lo).937
* @alloc the result vector.938
* @test CheatahBuiltins.SliceList939
* @crtest LangFeatures.ListSlicingAndIndex940
* @systest StdlibE2E.Builtins941
*/942
template <typename C>943
requires requires(const C& c) { c.data(); c.size(); } // contiguous seq, not a map944
auto slice(const C& c, long long lo, long long hi) -> std::vector<std::decay_t<decltype(c[0])>> {945
const long long n = static_cast<long long>(c.size());946
lo = detail::norm_index(lo, n);947
hi = (hi == slice_end) ? n : detail::norm_index(hi, n);948
if (lo < 0) lo = 0;949
if (hi > n) hi = n;950
// assign() from the source range sizes the buffer ONCE — a push_back loop re-tests capacity every951
// iteration and reallocates O(log n) times, which also keeps the loop from ever vectorizing. For952
// trivially-copyable elements libstdc++ lowers this to a single memmove.953
// Clamping with a ternary rather than guarding the assign with an `if` keeps every line here954
// unconditionally executed (the coverage gate demands 100% lines), and assign() is happy with an955
// empty range, so a reversed lo/hi simply yields an empty list exactly as the old loop did.956
const long long stop = hi < lo ? lo : hi;957
std::vector<std::decay_t<decltype(c[0])>> out;958
out.assign(c.begin() + static_cast<std::size_t>(lo), c.begin() + static_cast<std::size_t>(stop));959
return out;960
}962
} // namespace cheatah::builtins