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 <algorithm>17
#include <array>18
#include <cmath>19
#include <iterator>20
#include <concepts>21
#include <cstddef>22
#include <cstdint>23
#include <functional>24
#include <limits>25
#include <ostream>26
#include <sstream>27
#include <stdexcept>28
#include <string>29
#include <string_view>30
#include <type_traits>31
#include <unordered_map>32
#include <utility>33
#include <vector>35
namespace cheatah::builtins {37
/// Sized<C>: C reports a `.size()` — strings and STL containers (list/dict/array).38
template <typename C>39
concept Sized = requires(const C& c) {40
{ c.size() } -> std::convertible_to<std::size_t>;41
};43
/// Value<T>: a cheatah value — movable, so it can be stored, passed, and returned.44
/// This is the baseline concept purrc stamps on every emitted function/method45
/// parameter, so no cheatah code ever instantiates a fully unconstrained template46
/// (keeps compile errors comprehensible). See `constrain-all-templates` policy.47
template <typename T>48
concept Value = std::movable<std::remove_cvref_t<T>>;50
// ---- errors -------------------------------------------------------------------------------------51
//52
// `raise` throws an Error and `except` catches one. An Error carries a KIND alongside its message, so a53
// handler can select what it knows how to deal with (`except e of "index"`) and let everything else keep54
// travelling — which is the whole difference between recovering from a failure and swallowing one.55
//56
// The kind is a plain string, not a class hierarchy, because cheatah has no inheritance: "is-a" is a57
// concept, and a runtime taxonomy of errors is a discriminated value, not a base class. Kinds are open —58
// any string works — so a library can name its own failures without every caller having to know them.59
//60
// An Error is still a `str` wherever one is expected: it converts and compares as its MESSAGE, so61
// `io.print(e)` and `e == "boom"` read exactly as they did when a handler bound a bare string.63
/// Conventional kinds raised from the language core. Libraries are free to define their own.64
inline constexpr const char* kErrorKindError = "error"; ///< `raise "msg"` — unclassified65
inline constexpr const char* kErrorKindIndex = "index"; ///< subscript out of range66
inline constexpr const char* kErrorKindKey = "key"; ///< dict key absent67
inline constexpr const char* kErrorKindArithmetic = "arithmetic"; ///< divide / modulo by zero68
inline constexpr const char* kErrorKindUnknown = "unknown"; ///< a throw of a type we cannot inspect70
/**71
* A raised error: a `kind` naming what went wrong and a human `message`.72
*73
* Derives from `std::runtime_error` so it interoperates with C++ code that catches `std::exception` —74
* that inheritance is a C++ implementation detail and is not visible from cheatah, where an Error is an75
* ordinary value with two string fields.76
*/77
class Error : public std::runtime_error {78
public:79
/**80
* An unclassified error — what `raise "msg"` builds. Kind is @ref kErrorKindError.81
* @param message the human-readable description.82
* @complexity O(message).83
* @alloc copies the message (twice: the base class keeps its own).84
* @test CheatahBuiltins.ErrorCarriesKindAndMessage85
* @crtest PurrcPipeline.CompilesAndRunsTryExceptRaise86
*/87
explicit Error(std::string message)88
: std::runtime_error(message), kind_(kErrorKindError), message_(std::move(message)) {}90
/**91
* A classified error — what `raise Error("kind", "msg")` builds.92
* @param kind the open-ended kind string a handler selects on (`except e of "kind"`).93
* @param message the human-readable description.94
* @complexity O(kind + message).95
* @alloc copies both strings.96
* @test CheatahBuiltins.ErrorCarriesKindAndMessage97
*/98
Error(std::string kind, std::string message)99
: std::runtime_error(message), kind_(std::move(kind)), message_(std::move(message)) {}101
/**102
* @brief What CLASS of failure this is — the string `except … of` matches against.103
* @return the kind, by const reference; never empty for an Error built through these constructors.104
* @complexity O(1).105
* @alloc none.106
* @test CheatahBuiltins.ErrorCarriesKindAndMessage107
*/108
const std::string& kind() const noexcept { return kind_; }110
/**111
* @brief The human-readable description. This is also what @ref str and `operator<<` yield, so a112
* caught error prints as its message rather than as a struct.113
* @return the message, by const reference.114
* @complexity O(1).115
* @alloc none.116
* @test CheatahBuiltins.ErrorCarriesKindAndMessage117
*/118
const std::string& message() const noexcept { return message_; }120
// Deliberately NOT implicitly convertible to std::string. It would read nicely, but `str()` is a121
// heavily overloaded set and an implicit conversion makes half of it ambiguous the moment an Error122
// is printed. The `str` overload and the comparisons below give the same ergonomics explicitly.124
private:125
std::string kind_;126
std::string message_;127
};129
/**130
* @brief Compare an error against a string — by MESSAGE, so `e == "boom"` reads the way it did when a131
* handler bound a bare string. Compare `e.kind()` when you mean the kind.132
* @param e the error.133
* @param s the message to compare against.134
* @return true when the error's message is exactly @p s.135
* @complexity O(min(len)).136
* @alloc none.137
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage138
*/139
inline bool operator==(const Error& e, const std::string& s) { return e.message() == s; }141
/** @brief Message comparison, arguments reversed.142
* @param s the message to compare against.143
* @param e the error.144
* @return true when the error's message is exactly @p s.145
* @complexity O(min(len)). @alloc none.146
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage */147
inline bool operator==(const std::string& s, const Error& e) { return e.message() == s; }149
/** @brief Message comparison against a string literal.150
* @param e the error.151
* @param s the NUL-terminated message to compare against.152
* @return true when the error's message is exactly @p s.153
* @complexity O(len(@p s)). @alloc none.154
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage */155
inline bool operator==(const Error& e, const char* s) { return e.message() == s; }157
/** @brief Message comparison against a string literal, arguments reversed.158
* @param s the NUL-terminated message to compare against.159
* @param e the error.160
* @return true when the error's message is exactly @p s.161
* @complexity O(min(len)). @alloc none.162
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage */163
inline bool operator==(const char* s, const Error& e) { return e.message() == s; }165
/** @brief Stream an error as its MESSAGE — the kind would be noise in output that wanted the sentence.166
* @param os the destination stream.167
* @param e the error.168
* @return @p os, for chaining.169
* @complexity O(message). @alloc none beyond the stream's own.170
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage */171
inline std::ostream& operator<<(std::ostream& os, const Error& e) { return os << e.message(); }173
/**174
* The error currently being handled, normalized to an @ref Error.175
*176
* Called from inside a `catch (...)`, where `throw;` re-raises the in-flight exception so it can be177
* inspected by type. This is what lets ONE handler shape cover a raised Error, a `std::exception` from178
* any C++ library, and a throw of some type we have never heard of — the last of which used to travel179
* straight past every handler and abort the process.180
*181
* @return the in-flight exception as an Error: a raised Error verbatim, a `std::out_of_range` as kind182
* "index", a `std::domain_error` as "arithmetic", any other `std::exception` as "error", and183
* anything else as "unknown".184
* @complexity O(1) plus the message copy.185
* @alloc copies the kind and message.186
* @test CheatahBuiltins.CurrentErrorNormalizesEveryThrownType187
* @crtest PurrcPipeline.CompilesAndRunsTryExceptRaise188
*/189
inline Error current_error() {190
try {191
throw;192
} catch (const Error& e) {193
return e;194
} catch (const std::out_of_range& e) {195
return {kErrorKindIndex, e.what()};196
} catch (const std::domain_error& e) {197
return {kErrorKindArithmetic, e.what()};198
} catch (const std::exception& e) {199
return {kErrorKindError, e.what()};200
} catch (...) {201
return {kErrorKindUnknown, "unknown error"};202
}203
}205
/// Runs its action when the scope ends, however it ends — the body of a `finally`.206
template <std::invocable F>207
class Finally {208
public:209
/**210
* @brief Take ownership of the action to run at scope exit.211
* @param f the callable to invoke from the destructor.212
* @complexity O(1).213
* @alloc moves @p f into the guard.214
* @test CheatahBuiltins.FinallyRunsOnEveryExitPath215
*/216
explicit Finally(F f) : f_(std::move(f)) {}217
Finally(const Finally&) = delete;218
Finally& operator=(const Finally&) = delete;219
Finally(Finally&&) = delete; // a guard is pinned to its scope — never transferred.220
Finally& operator=(Finally&&) = delete;222
/**223
* @brief Run the action. Reached on every exit path — normal fall-through, `return`, `break`, or an224
* exception unwinding through the scope, which is the whole point of a guard over a225
* duplicated block.226
* @complexity that of the action.227
* @alloc that of the action.228
* @test CheatahBuiltins.FinallyRunsOnEveryExitPath229
* @test CheatahBuiltins.FinallySwallowsItsOwnThrowDuringUnwinding230
*/231
~Finally() {232
// A `finally` that throws while an exception is already unwinding would terminate the process,233
// which is a worse outcome than losing the second error — so it is swallowed here.234
// (The handler is one line deliberately: Finally is a template, so an instantiation whose235
// action cannot throw leaves a standalone `}` that no test can ever reach. The swallow itself236
// IS covered — see CheatahBuiltins.FinallySwallowsItsOwnThrowDuringUnwinding.)237
try {238
f_();239
} catch (...) {} // NOLINT(bugprone-empty-catch) — swallowing is the documented contract240
}242
private:243
F f_;244
};246
/**247
* @brief Build a scope guard around @p f — how `finally { … }` lowers.248
* @param f the callable to run when the enclosing scope ends.249
* @return the guard; keep it alive for the scope you want covered.250
* @complexity O(1).251
* @alloc moves @p f into the returned guard.252
* @test CheatahBuiltins.FinallyRunsOnEveryExitPath253
*/254
template <std::invocable F>255
Finally<F> make_finally(F f) {256
return Finally<F>(std::move(f));257
}259
/**260
* Length / element count.261
*262
* Forwards to the container's `.size()`; for strings this is the byte length,263
* not a Unicode code-point count.264
* @param c a string or sized container.265
* @return `c.size()`.266
* @complexity O(1).267
* @alloc none.268
* @test CheatahBuiltins.LenOrdChr269
* @crtest BuiltinsCompileRun.Len270
* @systest StdlibE2E.Builtins271
*/272
template <Sized C>273
std::size_t len(const C& c) { return c.size(); }274
/**275
* Length of a C-string / string literal.276
*277
* Returns the byte length of the view; any embedded NUL bytes are counted (the278
* length comes from the view, not from a terminating NUL).279
* @param s the string.280
* @return its byte length.281
* @complexity O(1).282
* @alloc none.283
* @test CheatahBuiltins.LenOrdChr284
* @crtest BuiltinsCompileRun.Len285
* @systest StdlibE2E.Builtins286
*/287
std::size_t len(std::string_view s);289
/**290
* Code point of the first byte.291
*292
* Returns the unsigned value of `s[0]` (0–255), ignoring trailing bytes;293
* an empty string yields 0 rather than throwing.294
* @param s a one-character string.295
* @return its byte value (0 if empty).296
* @complexity O(1).297
* @alloc none.298
* @test CheatahBuiltins.LenOrdChr299
* @crtest BuiltinsCompileRun.Ord300
* @systest StdlibE2E.Builtins301
*/302
int ord(std::string_view s);304
/**305
* ord() of a single char — what iterating a string yields (`for ch in s`), so ord(ch)306
* works inside such loops.307
* @param c the character (a single byte).308
* @return its unsigned byte value (0–255).309
* @complexity O(1). @alloc none. @test CheatahBuiltins.Ord310
* @crtest LangFeatures.Modulo311
*/312
constexpr int ord(char c) { return static_cast<unsigned char>(c); }313
/**314
* Character for a code point.315
*316
* Builds a one-byte string from the low 8 bits of @p codepoint (it is narrowed317
* to `char`), so values outside 0–255 wrap modulo 256 rather than producing318
* multi-byte output.319
* @param codepoint a byte value.320
* @return the one-character string.321
* @complexity O(1).322
* @alloc none (1-char small-string optimization).323
* @test CheatahBuiltins.LenOrdChr324
* @crtest BuiltinsCompileRun.Chr325
* @systest StdlibE2E.Builtins326
*/327
std::string chr(int codepoint);329
/**330
* Hex representation.331
*332
* Formats @p value in base 16 with lowercase digits and a `0x` prefix; negatives333
* are rendered as a leading `-` before the prefix (e.g. `-0x1f`), and 0 is `0x0`.334
* @param value the integer.335
* @return `"0x…"` (with sign).336
* @complexity O(log @p value).337
* @alloc allocates the result string, built from a temporary digits buffer.338
* @test CheatahBuiltins.BaseReprs339
* @crtest BuiltinsCompileRun.Hex340
* @systest StdlibE2E.Builtins341
*/342
std::string hex(long long value);343
/**344
* Octal representation.345
*346
* Formats @p value in base 8 with a `0o` prefix; negatives get a leading `-`347
* before the prefix (e.g. `-0o17`), and 0 is `0o0`.348
* @param value the integer.349
* @return `"0o…"` (with sign).350
* @complexity O(log @p value).351
* @alloc allocates the result string, built from a temporary digits buffer.352
* @test CheatahBuiltins.BaseReprs353
* @crtest BuiltinsCompileRun.Oct354
* @systest StdlibE2E.Builtins355
*/356
std::string oct(long long value);357
/**358
* Binary representation.359
*360
* Formats @p value in base 2 with a `0b` prefix; negatives get a leading `-`361
* before the prefix (e.g. `-0b101`), and 0 is `0b0`.362
* @param value the integer.363
* @return `"0b…"` (with sign).364
* @complexity O(log @p value).365
* @alloc allocates the result string, built from a temporary digits buffer.366
* @test CheatahBuiltins.BaseReprs367
* @crtest BuiltinsCompileRun.Bin368
* @systest StdlibE2E.Builtins369
*/370
std::string bin(long long value);372
/**373
* Printable-ASCII repr (non-printables/`\`/`'` escaped, single-quoted).374
*375
* Wraps @p s in single quotes, passing through printable ASCII (bytes 32–126)376
* verbatim while escaping `\` and `'` as `\\`/`\'` and emitting any other byte as377
* a two-digit `\xHH` hex escape.378
* @param s input.379
* @return the quoted repr.380
* @complexity O(n).381
* @alloc allocates the result string, plus a temporary ostringstream per escaped byte.382
* @test CheatahBuiltins.Ascii383
* @crtest BuiltinsCompileRun.Ascii384
* @systest StdlibE2E.Builtins385
*/386
std::string ascii(std::string_view s);388
/**389
* Truthiness of a string.390
*391
* Truthy iff non-empty; a whitespace-only or `"0"`/`"false"` string is still392
* truthy (only emptiness is false).393
* @param s input.394
* @return false iff @p s is empty.395
* @complexity O(1).396
* @alloc none.397
* @test CheatahBuiltins.Conversions398
* @crtest BuiltinsCompileRun.BoolFromString399
* @systest StdlibE2E.Builtins400
*/401
bool to_bool(std::string_view s);402
/**403
* Truthiness of a number.404
* @param x any arithmetic value.405
* @return @p x != 0.406
* @complexity O(1).407
* @alloc none.408
* @test CheatahBuiltins.Conversions409
* @crtest BuiltinsCompileRun.BoolFromNonzero410
* @systest StdlibE2E.Builtins411
*/412
template <typename T>413
requires std::is_arithmetic_v<T>414
bool to_bool(T x) { return x != T{}; }415
/**416
* Parse a base-10 integer.417
*418
* Parses leading whitespace and an optional sign followed by decimal digits via419
* `std::stoll`; it stops at the first non-digit (so trailing junk is ignored),420
* throws on no parseable digits, and throws on out-of-range values.421
* @param s the integer string.422
* @return its value (throws on bad input).423
* @complexity O(n).424
* @alloc allocates a temporary `std::string` for the parse.425
* @test CheatahBuiltins.Conversions426
* @crtest BuiltinsCompileRun.IntFromString427
* @systest StdlibE2E.Builtins428
*/429
long long to_int(std::string_view s);430
/**431
* Truncate a double to an integer.432
*433
* Truncates toward zero (drops the fractional part rather than rounding), so434
* `2.9` becomes 2 and `-2.9` becomes -2; values outside `long long` range are435
* undefined behavior.436
* @param x the value.437
* @return @p x toward zero.438
* @complexity O(1).439
* @alloc none.440
* @warning @p x outside `long long`'s range (or NaN) is undefined behavior — no clamp or check.441
* @test CheatahBuiltins.Conversions442
* @crtest BuiltinsCompileRun.IntFromFloat443
* @systest StdlibE2E.Builtins444
*/445
long long to_int(double x);446
/**447
* Parse a float.448
*449
* Parses leading whitespace and a floating-point literal via `std::stod`,450
* accepting decimal, scientific (`1e9`), `inf`, and `nan` forms; it stops at the451
* first unparsed character, throws when nothing parses, and throws on overflow.452
* @param s a floating-point string.453
* @return its value (throws on bad input).454
* @complexity O(n).455
* @alloc allocates a temporary `std::string` for the parse.456
* @test CheatahBuiltins.Conversions457
* @crtest BuiltinsCompileRun.FloatFromString458
* @systest StdlibE2E.Builtins459
*/460
double to_float(std::string_view s);461
/// Number: any built-in arithmetic type — every width float() accepts numerically.462
template <typename T>463
concept Number = std::is_arithmetic_v<T>;464
/**465
* `float()` of any NUMBER — one widening/identity conversion for every arithmetic type, so466
* overload resolution can never route a `double` (or an `i32`) through an integer overload467
* and silently TRUNCATE: `float(0.95)` must be 0.95, never 0.468
* @tparam T the arithmetic source type (`Number`).469
* @param x the value.470
* @return @p x as a `double`.471
* @complexity O(1).472
* @alloc none.473
* @test CheatahBuiltins.ToFloatFromInt474
* @test CheatahBuiltins.ToFloatFromFloat475
* @crtest BuiltinsCompileRun.FloatFromInt476
* @crtest BuiltinsCompileRun.FloatFromFloat477
* @systest StdlibE2E.Builtins478
*/479
template <Number T>480
constexpr double to_float(T x) { return static_cast<double>(x); }482
/// Streamable<T>: T can be written to a `std::ostream` with `operator<<` — the requirement483
/// for str() to render it. (Mirrors io's Printable, so bare `str(x)` and `io.str(x)` agree.)484
template <typename T>485
concept Streamable = requires(std::ostream& os, const T& v) {486
{ os << v } -> std::convertible_to<std::ostream&>;487
};489
/**490
* Python `str()`: stringify any streamable value (an always-available built-in, so it needs491
* no `import` — bare `str(x)` resolves here, like `int()`/`float()`/`bool()`).492
*493
* Renders @p value via its `operator<<` into a fresh `ostringstream`, so the text matches494
* whatever that stream insertion produces (e.g. default 6-significant-digit float precision),495
* agreeing with `io.print`/`io.str`.496
* @param value the value to render.497
* @return @p value formatted as text.498
* @complexity O(n) in the output length.499
* @alloc allocates the result string (via an ostringstream).500
* @test CheatahBuiltins.Str501
* @crtest BuiltinsCompileRun.Str502
* @systest StdlibE2E.String503
*/504
template <Streamable T>505
std::string str(const T& value) {506
std::ostringstream os;507
os << value;508
return os.str();509
}511
/**512
* `str()` for a bool — Python's capitalized spelling.513
*514
* Overrides the default streaming of a bool (`1`/`0`) to emit `True`/`False`, matching515
* `io.str` and `io.print`.516
* @param b the boolean.517
* @return `"True"` or `"False"`.518
* @complexity O(1).519
* @alloc allocates the small result string.520
* @test CheatahBuiltins.Str521
* @crtest BuiltinsCompileRun.Str522
* @systest StdlibE2E.Builtins523
*/524
inline std::string str(bool b) { return b ? "True" : "False"; }526
/**527
* `str()` of an error is its MESSAGE — printing a caught error says what went wrong, without the kind528
* turning up uninvited in output that only wanted the sentence. Reach for `.kind()` when you want it.529
* @param e the error to render.530
* @return the error's message.531
* @complexity O(message).532
* @alloc copies the message.533
* @test CheatahBuiltins.ErrorComparesAndPrintsAsItsMessage534
*/535
inline std::string str(const Error& e) { return e.message(); }537
/**538
* `str()` for the byte-width integers `i8`/`u8` (`std::int8_t`/`std::uint8_t`, which are539
* typedefs of `signed char`/`unsigned char`). Streaming a `char`-sized type would print a540
* CHARACTER; these overloads promote to a wider integer first so `i8`/`u8` render as NUMBERS —541
* the one seam through which `repr`, `print`, and container `str`/`repr` all inherit the fix.542
* Plain `char` is a distinct type (cheatah has no bare-`char` value type — single chars are543
* 1-char `std::string`), so it is deliberately not matched here.544
* @param v the `i8` value to render.545
* @return the value's decimal digits.546
* @complexity O(1).547
* @alloc allocates the small result string.548
* @test CheatahBuiltins.StrByteWidthIntsAreNumbers549
*/550
inline std::string str(signed char v) { return std::to_string(static_cast<int>(v)); }551
/**552
* `str()` for `u8` (`std::uint8_t`) — numeric, not a character. See @ref str(signed char).553
* @param v the `u8` value to render.554
* @return the value's decimal digits.555
* @complexity O(1).556
* @alloc allocates the small result string.557
* @test CheatahBuiltins.StrByteWidthIntsAreNumbers558
*/559
inline std::string str(unsigned char v) { return std::to_string(static_cast<unsigned>(v)); }561
/**562
* True division — the cheatah `/` operator (like Python 3): **always floating-point**,563
* so `6 / 2` is `3.0`, not `3`, and integer operands never silently truncate. Use the564
* `//` operator (@ref floordiv) when you want integer/floor division.565
* @param a numerator.566
* @param b denominator.567
* @return `double(a) / double(b)`.568
* @complexity O(1).569
* @alloc none.570
* @test CheatahBuiltins.Division571
* @crtest BuiltinsCompileRun.TrueDivision572
* @systest StdlibE2E.Math573
*/574
template <typename A, typename B>575
requires std::is_arithmetic_v<A> && std::is_arithmetic_v<B>576
double truediv(A a, B b) {577
return static_cast<double>(a) / static_cast<double>(b);578
}579
/**580
* Floor division — the cheatah `//` operator (like Python): the quotient floored toward581
* −∞. Integer operands give an integer (`7 // 2 == 3`, `-7 // 2 == -4`, flooring the way582
* Python does, not truncating toward zero like raw C++); a floating operand gives a583
* floored double (`7.0 // 2 == 3.0`).584
* @param a numerator.585
* @param b denominator; @p b == 0 throws `std::domain_error` (integer floor division by zero).586
* @return `floor(a / b)`, integral for integral operands.587
* @complexity O(1).588
* @alloc none.589
* @test CheatahBuiltins.Division590
* @test CheatahBuiltins.IntegerDivideAndModuloByZeroThrow591
* @crtest BuiltinsCompileRun.FloorDivision592
* @systest StdlibE2E.Builtins593
*/594
template <std::integral A, std::integral B>595
std::common_type_t<A, B> floordiv(A a, B b) {596
// A controlled error, not UB: integer divide-by-zero is undefined in C++ (SIGFPE/trap), so guard597
// it so pure-cheatah `x // 0` raises rather than corrupting the process. (Float `//` is IEEE-safe.)598
if (b == 0) throw std::domain_error("integer floor division by zero");599
std::common_type_t<A, B> q = a / b; // C++ truncates toward zero…600
if ((a % b != 0) && ((a < 0) != (b < 0))) --q; // …adjust to floor toward −∞601
return q;602
}603
/**604
* Floor division (`//`) for floating-point operands: floors the quotient toward −∞.605
*606
* Selected when at least one operand is floating-point (the all-integer case uses the607
* @ref floordiv overload above). Mirrors Python, where `7.0 // 2.0 == 3.0`.608
* @param a numerator.609
* @param b denominator.610
* @return `std::floor(double(a) / double(b))`.611
* @complexity O(1).612
* @alloc none.613
* @test CheatahBuiltins.Division614
* @crtest BuiltinsCompileRun.FloorDivision615
* @systest StdlibE2E.Builtins616
*/617
template <typename A, typename B>618
requires(std::is_arithmetic_v<A> && std::is_arithmetic_v<B> &&619
!(std::integral<A> && std::integral<B>))620
double floordiv(A a, B b) {621
return std::floor(static_cast<double>(a) / static_cast<double>(b));622
}624
/**625
* Content hash of a string.626
*627
* Hashes the bytes via `std::hash<std::string_view>` (equal contents hash628
* equally); the value is implementation-defined and unstable across runs and629
* compilers (do not persist it).630
* @param s input.631
* @return a `std::size_t` hash.632
* @complexity O(n).633
* @alloc none.634
* @test CheatahBuiltins.Hash635
* @systest StdlibE2E.Builtins636
* @note No `@crtest`: compile-run coverage is intentionally skipped because the637
* hash value is implementation-defined and has no portable expected stdout.638
*/639
std::size_t hash(std::string_view s);640
/**641
* Hash of any hashable value.642
*643
* Defers to `std::hash<T>` for the static type of @p x, so it requires a644
* specialization to exist for `T`; like the string overload, the result is645
* implementation-defined and unstable across runs.646
* @param x the value.647
* @return `std::hash<T>{}(x)`.648
* @complexity O(1) for scalars.649
* @alloc none.650
* @test CheatahBuiltins.Hash651
* @systest StdlibE2E.Builtins652
* @note No `@crtest`: compile-run coverage is intentionally skipped because the653
* hash value is implementation-defined and has no portable expected stdout.654
*/655
template <typename T>656
requires requires(const T& x) { std::hash<T>{}(x); }657
std::size_t hash(const T& x) { return std::hash<T>{}(x); }659
// ---- collection + method-style helpers ----660
//661
// These power cheatah's growable lists and the method-call syntax `obj.f(a)`,662
// which lowers to `cheatah::builtins::f(obj, a)`. Free-function form works too:663
// `append(xs, x)` and `xs.append(x)` are the same call.665
/**666
* Append @p x to list @p v in place (Python `list.append`).667
*668
* Grows @p v by one, converting @p x to the list's element type. Usable as a669
* method (`xs.append(x)`) or a bare call (`append(xs, x)`); the list is taken by670
* reference, so the caller's list is mutated.671
* @param v the list to grow.672
* @param x the value to append.673
* @complexity amortized O(1).674
* @alloc reallocates @p v when it outgrows its capacity.675
* @test CheatahBuiltins.Append676
* @crtest LangFeatures.AppendAndDictMutation677
* @systest StdlibE2E.Builtins678
*/679
template <typename T, typename U>680
requires std::convertible_to<std::remove_cvref_t<U>, T>681
void append(std::vector<T>& v, U&& x) {682
v.push_back(static_cast<T>(std::forward<U>(x)));683
}685
/**686
* Whether @p s begins with @p prefix (Python `str.startswith`).687
* @param s the string.688
* @param prefix the prefix to test.689
* @return true iff @p s starts with @p prefix.690
* @complexity O(len(@p prefix)).691
* @alloc none.692
* @test CheatahBuiltins.StringPredicates693
* @crtest LangFeatures.MethodPredicates694
* @systest StdlibE2E.Builtins695
*/696
inline bool startswith(std::string_view s, std::string_view prefix) {697
return s.size() >= prefix.size() && s.compare(0, prefix.size(), prefix) == 0;698
}700
/**701
* Whether @p s ends with @p suffix (Python `str.endswith`).702
* @param s the string.703
* @param suffix the suffix to test.704
* @return true iff @p s ends with @p suffix.705
* @complexity O(len(@p suffix)).706
* @alloc none.707
* @test CheatahBuiltins.StringPredicates708
* @crtest LangFeatures.MethodPredicates709
* @systest StdlibE2E.Builtins710
*/711
inline bool endswith(std::string_view s, std::string_view suffix) {712
return s.size() >= suffix.size() &&713
s.compare(s.size() - suffix.size(), suffix.size(), suffix) == 0;714
}716
/**717
* Whether @p sub occurs anywhere in @p s (Python `sub in s`).718
* @param s the string to search.719
* @param sub the substring to find.720
* @return true iff @p sub is a substring of @p s.721
* @complexity O(len(@p s) · len(@p sub)) worst case.722
* @alloc none.723
* @test CheatahBuiltins.StringPredicates724
* @crtest LangFeatures.MethodPredicates725
* @systest StdlibE2E.Builtins726
*/727
inline bool contains(std::string_view s, std::string_view sub) {728
return s.find(sub) != std::string_view::npos;729
}731
/**732
* Membership test for a dict: is @p key present? Backs the `in` operator (`k in d`).733
* @param d the dict to search.734
* @param key the key to look for.735
* @return true iff @p key is present in @p d.736
* @complexity O(1) average.737
* @alloc none.738
* @crtest LangFeatures.InOperator739
*/740
template <class K, class V, class H, class E, class A, class Key>741
bool contains(const std::unordered_map<K, V, H, E, A>& d, const Key& key) {742
return d.count(key) != 0;743
}745
/**746
* Membership test for a list: does any element equal @p value? Backs `x in xs`.747
* @param xs the list to scan.748
* @param value the value to look for.749
* @return true iff some element of @p xs compares equal to @p value.750
* @complexity O(n).751
* @alloc none.752
* @crtest LangFeatures.InOperator753
*/754
template <class T, class A, class Value>755
bool contains(const std::vector<T, A>& xs, const Value& value) {756
for (const T& x : xs) {757
if (x == value) return true;758
}759
return false;760
}762
/**763
* Python FLOOR-mod for integers: the result takes the DIVISOR's sign (-7 % 3 == 2), unlike764
* raw C++ `%`. Backs the `%` operator.765
* @param a the dividend.766
* @param b the divisor; @p b == 0 throws std::domain_error (integer modulo by zero).767
* @return a mod b with the sign of @p b (Python floor-mod semantics).768
* @complexity O(1).769
* @alloc none.770
* @test CheatahBuiltins.Mod771
* @test CheatahBuiltins.IntegerDivideAndModuloByZeroThrow772
* @crtest LangFeatures.Modulo773
*/774
template <class A, class B>775
requires(std::is_integral_v<A> && std::is_integral_v<B>)776
std::common_type_t<A, B> mod(A a, B b) {777
using R = std::common_type_t<A, B>;778
// A controlled error, not UB: integer `% 0` is undefined in C++ (SIGFPE/trap) — guard it so779
// pure-cheatah `x % 0` raises rather than corrupting the process. (Float `%` is IEEE-safe.)780
if (b == 0) throw std::domain_error("integer modulo by zero");781
const R r = static_cast<R>(a) % static_cast<R>(b);782
return (r != 0 && ((r < 0) != (b < 0))) ? r + static_cast<R>(b) : r;783
}785
/**786
* Python floor-mod for floats (either operand): fmod adjusted to the divisor's sign,787
* mirroring `7.5 % 2 == 1.5` and `-7.5 % 2 == 0.5`.788
* @param a the dividend.789
* @param b the divisor.790
* @return a mod b as a double, with the sign of @p b (Python floor-mod semantics).791
* @complexity O(1).792
* @alloc none.793
* @test CheatahBuiltins.Mod794
* @crtest LangFeatures.Modulo795
*/796
template <class A, class B>797
requires(!std::is_integral_v<A> || !std::is_integral_v<B>)798
double mod(A a, B b) {799
const double r = std::fmod(static_cast<double>(a), static_cast<double>(b));800
return (r != 0.0 && ((r < 0.0) != (static_cast<double>(b) < 0.0))) ? r + static_cast<double>(b)801
: r;802
}804
// ---- indexing & slicing (Python `seq[i]` / `seq[i:j]`) ----805
//806
// The compiler lowers value-position `seq[i]` to `index(seq, i)` and `seq[a:b]`807
// to `slice(seq, a, b)` (a missing bound becomes 0 / `slice_end`). Indices may be808
// negative (counted from the end). Indexing a string yields a length-1 string809
// (Python semantics), so `s[i] == "<"` type-checks; slicing yields the same kind.811
/// Sentinel for an omitted slice upper bound (`s[a:]`): "to the end".812
inline constexpr long long slice_end = std::numeric_limits<long long>::max();814
namespace detail {815
inline long long norm_index(long long i, long long n) { return i < 0 ? i + n : i; }816
} // namespace detail818
/**819
* Element at @p i of a string — a length-1 string (Python `s[i]`).820
* Negative @p i counts from the end; out-of-range throws `std::out_of_range`.821
* @param s the string.822
* @param i the index (may be negative).823
* @return the one-character string at @p i.824
* @complexity O(1).825
* @alloc none (1-char small-string optimization).826
* @test CheatahBuiltins.IndexString827
* @crtest LangFeatures.StringSlicingAndIndex828
* @systest StdlibE2E.Builtins829
*/830
inline std::string index(const std::string& s, long long i) {831
const auto n = static_cast<long long>(s.size());832
i = detail::norm_index(i, n);833
if (i < 0 || i >= n) throw std::out_of_range("string index out of range");834
std::string out(1, s[static_cast<std::size_t>(i)]); // (1, c) must not become a braced list: {1, c} is two chars835
return out;836
}838
/**839
* Element at @p i of a list/array (Python `xs[i]`), by CONST REFERENCE.840
* Negative @p i counts from the end; out-of-range throws `std::out_of_range`.841
*842
* Returning a reference — not a copy — is what makes `xs[i].field` free: reading one field of a843
* heap-owning element (a struct with strings/lists) no longer deep-copies the whole element. Value844
* semantics are UNCHANGED at the `.purr` level, because codegen binds a subscript with plain `auto`845
* (`let e = xs[i]` still copies), and the const-ness preserves cheatah's "list elements are846
* read-only" rule — whole-element `xs[i] = v` assignment goes through a different path.847
*848
* Lifetime: the reference is into @p c, so it is valid as long as @p c is and is not mutated.849
* Subscripting a temporary container is safe in the expression that does it (the temporary outlives850
* the full-expression); binding that reference to a name that outlives the statement is not, and851
* codegen never emits such a binding.852
* @param c the sequence.853
* @param i the index (may be negative).854
* @return a const reference to the element at @p i.855
* @complexity O(1).856
* @alloc none.857
* @test CheatahBuiltins.IndexList858
* @crtest LangFeatures.ListSlicingAndIndex859
* @systest StdlibE2E.Builtins860
*/861
template <typename C>862
requires requires(const C& c) { c.data(); c.size(); } // contiguous seq (vector/array), not a map863
auto index(const C& c, long long i) -> const std::decay_t<decltype(c[0])>& {864
const auto n = static_cast<long long>(c.size());865
i = detail::norm_index(i, n);866
if (i < 0 || i >= n) throw std::out_of_range("index out of range");867
return c[static_cast<std::size_t>(i)];868
}870
/**871
* Element at @p i of a `list[bool]` (Python `xs[i]`), by value.872
* `std::vector<bool>` is the one sequence type the contiguous overload above873
* cannot accept: it is bit-packed, so it has proxy references and no `.data()`.874
* Same semantics — negative @p i counts from the end; out-of-range throws.875
* @param c the bool list.876
* @param i the index (may be negative).877
* @return the element at @p i.878
* @complexity O(1).879
* @alloc none.880
* @test CheatahBuiltins.IndexBoolList881
* @crtest BuiltinsCompileRun.IndexBoolList882
* @systest StdlibE2E.Builtins883
*/884
inline bool index(const std::vector<bool>& c, long long i) {885
const auto n = static_cast<long long>(c.size());886
i = detail::norm_index(i, n);887
if (i < 0 || i >= n) throw std::out_of_range("index out of range");888
return c[static_cast<std::size_t>(i)];889
}891
/**892
* Value for @p key in a dict (Python `d[key]`), by CONST REFERENCE.893
* Same rationale and lifetime rules as the sequence overload above: `d[key].field` stops894
* deep-copying the mapped value, while `let v = d[key]` still copies.895
* @param m the dict.896
* @param key the key to look up.897
* @return a const reference to the mapped value; an absent key raises kind `"key"`, which is distinct898
* from the `"index"` a sequence subscript raises — a missing dict entry and a walked-off-the-end899
* list are different mistakes and a handler should be able to take one without the other.900
* @complexity O(1) average.901
* @alloc none.902
* @test CheatahBuiltins.IndexDict903
* @crtest LangFeatures.AppendAndDictMutation904
* @systest Callback.RichTypesThroughStdFunction905
*/906
template <typename K, typename V, typename H, typename E, typename A, typename Key>907
requires requires(const std::unordered_map<K, V, H, E, A>& m, const Key& key) { m.find(key); }908
const V& index(const std::unordered_map<K, V, H, E, A>& m, const Key& key) {909
const auto it = m.find(key);910
if (it == m.end()) throw Error(kErrorKindKey, "key not found");911
return it->second;912
}914
/**915
* Substring `s[lo:hi]` (Python slice semantics: clamped, negatives from the end).916
* @param s the string.917
* @param lo start index (default 0 at the call site).918
* @param hi end index, or @ref slice_end for "to the end".919
* @return the slice (empty if `lo >= hi` after clamping).920
* @complexity O(hi-lo).921
* @alloc the result string.922
* @test CheatahBuiltins.SliceString923
* @crtest LangFeatures.StringSlicingAndIndex924
* @systest StdlibE2E.Ed25519925
*/926
inline std::string slice(const std::string& s, long long lo, long long hi) {927
const auto n = static_cast<long long>(s.size());928
lo = detail::norm_index(lo, n);929
hi = (hi == slice_end) ? n : detail::norm_index(hi, n);930
if (lo < 0) lo = 0;931
if (hi > n) hi = n;932
if (lo >= hi) return {};933
return s.substr(static_cast<std::size_t>(lo), static_cast<std::size_t>(hi - lo));934
}936
/**937
* Sub-list `xs[lo:hi]` (Python slice semantics), returned as a new list.938
* @param c the sequence.939
* @param lo start index.940
* @param hi end index, or @ref slice_end for "to the end".941
* @return the slice as a `std::vector` of the element type.942
* @complexity O(hi-lo).943
* @alloc the result vector.944
* @test CheatahBuiltins.SliceList945
* @crtest LangFeatures.ListSlicingAndIndex946
* @systest StdlibE2E.Builtins947
*/948
template <typename C>949
requires requires(const C& c) { c.data(); c.size(); } // contiguous seq, not a map950
auto slice(const C& c, long long lo, long long hi) -> std::vector<std::decay_t<decltype(c[0])>> {951
const auto n = static_cast<long long>(c.size());952
lo = detail::norm_index(lo, n);953
hi = (hi == slice_end) ? n : detail::norm_index(hi, n);954
if (lo < 0) lo = 0;955
if (hi > n) hi = n;956
// assign() from the source range sizes the buffer ONCE — a push_back loop re-tests capacity every957
// iteration and reallocates O(log n) times, which also keeps the loop from ever vectorizing. For958
// trivially-copyable elements libstdc++ lowers this to a single memmove.959
// Clamping with a ternary rather than guarding the assign with an `if` keeps every line here960
// unconditionally executed (the coverage gate demands 100% lines), and assign() is happy with an961
// empty range, so a reversed lo/hi simply yields an empty list exactly as the old loop did.962
const long long stop = hi < lo ? lo : hi;963
std::vector<std::decay_t<decltype(c[0])>> out;964
out.assign(c.begin() + static_cast<std::size_t>(lo), c.begin() + static_cast<std::size_t>(stop));965
return out;966
}968
// ---- slice ASSIGNMENT ------------------------------------------------------------------969
// `seq[lo:hi] = rhs` lowers to `slice_assign(seq, lo, hi, rhs)`. Bounds are normalised exactly as970
// @ref slice does, so the write addresses the elements the matching read would have returned.971
//972
// Each container decides what an assignment MEANS, by overload resolution — the compiler has no973
// type information to decide with. A list REPLACES the range and resizes (Python); ndarray and974
// fixarray COPY the values into storage they already own (they are arrays: an assignment fills975
// them, it never rebinds or resizes them); a string refuses, being immutable.977
/**978
* The empty sequence on the right of a slice assignment (`xs[a:b] = []`).979
*980
* An empty list literal carries no element type, so it cannot be spelled as a `std::vector`981
* without one. The compiler emits this tag instead and each container decides what it means:982
* a list DELETES the range, while a fixed-extent array refuses, having nothing to shrink.983
*/984
struct empty_seq {};986
// ndarray.hpp reopens this namespace without including this header, so it spells the same987
// sentinel locally. If either value ever moves, this fails rather than silently disagreeing.988
static_assert(slice_end == std::numeric_limits<long long>::max(),989
"builtins::slice_end and ndarray's nd_slice_end must hold the same value");991
/**992
* Delete `v[lo:hi]` — the `xs[a:b] = []` form.993
* @tparam T the element type.994
* @param v the list to modify in place.995
* @param lo start index (negative counts from the end).996
* @param hi end index, or @ref slice_end for "to the end".997
* @complexity O(size) — the tail shifts down.998
* @alloc none — erasing never reallocates.999
* @test CheatahBuiltins.SliceAssignList1000
* @crtest LangFeatures.ListSliceAssignment1001
* @systest StdlibE2E.Builtins1002
*/1003
template <typename T>1004
void slice_assign(std::vector<T>& v, long long lo, long long hi, empty_seq /*empty*/) {1005
const auto n = static_cast<long long>(v.size());1006
lo = detail::norm_index(lo, n);1007
hi = (hi == slice_end) ? n : detail::norm_index(hi, n);1008
if (lo < 0) lo = 0;1009
if (lo > n) lo = n;1010
if (hi > n) hi = n;1011
if (hi < lo) hi = lo;1012
v.erase(v.begin() + static_cast<std::size_t>(lo), v.begin() + static_cast<std::size_t>(hi));1013
}1015
/**1016
* Write @p rhs into `v[lo:hi]` of a fixed-size `array<T, N>` — it is FILLED, never resized.1017
*1018
* The extent is part of the type, so a source of the wrong length is an error rather than a1019
* partial write. Bounds follow @ref slice. This is the same contract `fixarray` and `ndarray`1020
* keep: an assignment into an array copies values into storage the array already owns.1021
* @tparam T the element type.1022
* @tparam N the extent.1023
* @tparam R the source range type.1024
* @param v the array to write into.1025
* @param lo start index (negative counts from the end).1026
* @param hi end index, or @ref slice_end for "to the end".1027
* @param rhs the elements to copy in.1028
* @complexity O(hi - lo).1029
* @alloc none — the destination already owns its storage.1030
* @test CheatahBuiltins.SliceAssignFixedArray1031
* @crtest LangFeatures.ListSliceAssignment1032
* @systest StdlibE2E.Builtins1033
*/1034
template <typename T, std::size_t N, typename R>1035
requires requires(const R& r) { r.begin(); r.end(); }1036
void slice_assign(std::array<T, N>& v, long long lo, long long hi, const R& rhs) {1037
constexpr auto n = static_cast<long long>(N);1038
lo = detail::norm_index(lo, n);1039
hi = (hi == slice_end) ? n : detail::norm_index(hi, n);1040
if (lo < 0) lo = 0;1041
if (lo > n) lo = n;1042
if (hi > n) hi = n;1043
if (hi < lo) hi = lo;1044
const auto want = static_cast<std::size_t>(hi - lo);1045
const auto got = static_cast<std::size_t>(std::distance(rhs.begin(), rhs.end()));1046
if (got != want) {1047
throw std::runtime_error("array: a slice assignment fills a fixed extent — the source has " +1048
std::to_string(got) + " element(s) for " + std::to_string(want) +1049
" slot(s)");1050
}1051
std::copy(rhs.begin(), rhs.end(), v.begin() + static_cast<std::size_t>(lo));1052
}1054
/// @cond INTERNAL1055
/// A fixed-size array has nothing to delete — its extent is part of its type.1056
template <typename T, std::size_t N>1057
void slice_assign(std::array<T, N>& v, long long lo, long long hi, empty_seq /*empty*/) {1058
(void)v; (void)lo; (void)hi;1059
throw std::runtime_error(1060
"array: a[lo:hi] = [] has no meaning — a fixed-size array is filled, not resized");1061
}1062
/// @endcond1064
/// @cond INTERNAL1065
/// A string is immutable, exactly as in Python, so `s[a:b] = …` has no meaning. Declared (rather1066
/// than left to fail on overload resolution) so the error is a sentence instead of a page of1067
/// candidate templates.1068
template <typename R>1069
void slice_assign(std::string& s, long long lo, long long hi, const R& rhs) {1070
static_assert(sizeof(R) == 0,1071
"cheatah: a str is immutable — s[a:b] = ... is not allowed (as in Python). "1072
"Build a new string, e.g. s = s[:a] + replacement + s[b:].");1073
(void)s; (void)lo; (void)hi; (void)rhs;1074
}1075
/// @endcond1077
/**1078
* Replace `v[lo:hi]` with the elements of @p rhs, resizing the list (Python list semantics).1079
*1080
* Bounds follow @ref slice: negatives count from the end, out-of-range values clamp, and a1081
* reversed range is an insertion point. The list GROWS or SHRINKS to fit @p rhs, so1082
* `xs[1:3] = []` deletes those elements and `xs[1:1] = ys` inserts without removing any.1083
*1084
* @p rhs is copied into a temporary before the list is touched. That is what makes1085
* `xs[1:3] = xs` and an overlapping source well defined instead of undefined: `erase` would1086
* otherwise invalidate the very range `insert` is reading from.1087
* @tparam T the element type.1088
* @tparam R the source range type.1089
* @param v the list to modify in place.1090
* @param lo start index (negative counts from the end).1091
* @param hi end index, or @ref slice_end for "to the end".1092
* @param rhs the elements to write.1093
* @complexity O(size + |rhs|) — the tail shifts when the length changes.1094
* @alloc one temporary holding @p rhs, plus a reallocation when the list grows.1095
* @test CheatahBuiltins.SliceAssignList1096
* @test CheatahBuiltins.SliceAssignAliasing1097
* @crtest LangFeatures.ListSliceAssignment1098
* @systest StdlibE2E.Builtins1099
*/1100
template <typename T, typename R>1101
requires requires(const R& r) { r.begin(); r.end(); }1102
void slice_assign(std::vector<T>& v, long long lo, long long hi, const R& rhs) {1103
const auto n = static_cast<long long>(v.size());1104
lo = detail::norm_index(lo, n);1105
hi = (hi == slice_end) ? n : detail::norm_index(hi, n);1106
if (lo < 0) lo = 0;1107
if (lo > n) lo = n;1108
if (hi > n) hi = n;1109
if (hi < lo) hi = lo;1110
// Materialise FIRST — @p rhs may be `v` itself, or a range into it.1111
std::vector<T> tmp(rhs.begin(), rhs.end());1112
const auto ulo = static_cast<std::size_t>(lo);1113
if (static_cast<long long>(tmp.size()) == hi - lo) {1114
std::copy(tmp.begin(), tmp.end(), v.begin() + ulo); // same length: no resize1115
return;1116
}1117
v.erase(v.begin() + ulo, v.begin() + static_cast<std::size_t>(hi));1118
v.insert(v.begin() + ulo, tmp.begin(), tmp.end());1119
}1121
/// @cond INTERNAL1122
/// A list slice is filled from a sequence, never from a bare element — `xs[1:3] = 9` is the1123
/// mistake this catches, with a sentence rather than a missing-begin() error.1124
template <typename T, typename R>1125
requires(!requires(const R& r) { r.begin(); r.end(); })1126
void slice_assign(std::vector<T>& v, long long lo, long long hi, const R& rhs) {1127
static_assert(sizeof(R) == 0,1128
"cheatah: a list slice is assigned from a list — write xs[a:b] = [value], "1129
"not xs[a:b] = value.");1130
(void)v; (void)lo; (void)hi; (void)rhs;1131
}1132
/// @endcond1134
} // namespace cheatah::builtins