aboutsummaryrefslogtreecommitdiff
path: root/backend/lib/Support
diff options
context:
space:
mode:
Diffstat (limited to 'backend/lib/Support')
-rw-r--r--backend/lib/Support/APFloat.cpp1336
-rw-r--r--backend/lib/Support/APInt.cpp520
-rw-r--r--backend/lib/Support/CMakeLists.txt49
-rw-r--r--backend/lib/Support/Error.cpp69
-rw-r--r--backend/lib/Support/SHA256.cpp149
-rw-r--r--backend/lib/Support/TextDiagnostic.cpp88
-rw-r--r--backend/lib/Support/YAML.cpp1247
7 files changed, 3458 insertions, 0 deletions
diff --git a/backend/lib/Support/APFloat.cpp b/backend/lib/Support/APFloat.cpp
new file mode 100644
index 0000000..c7b1503
--- /dev/null
+++ b/backend/lib/Support/APFloat.cpp
@@ -0,0 +1,1336 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/ADT/APFloat.h"
+
+#include "rcc/ADT/APInt.h"
+
+#include <algorithm>
+#include <array>
+#include <charconv>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <optional>
+#include <ranges>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+struct FloatSemanticsInfo final {
+ std::uint32_t BitWidth;
+ std::string_view Spelling;
+};
+
+constexpr std::array FloatSemanticsTable{
+ FloatSemanticsInfo{16, "f16"}, FloatSemanticsInfo{16, "bf16"},
+ FloatSemanticsInfo{32, "f32"}, FloatSemanticsInfo{64, "f64"},
+ FloatSemanticsInfo{128, "f128"}, FloatSemanticsInfo{128, "ppcf128"},
+ FloatSemanticsInfo{8, "f8e5m2"}, FloatSemanticsInfo{8, "f8e5m2fnuz"},
+ FloatSemanticsInfo{8, "f8e4m3"}, FloatSemanticsInfo{8, "f8e4m3fn"},
+ FloatSemanticsInfo{8, "f8e4m3fnuz"}, FloatSemanticsInfo{8, "f8e4m3b11fnuz"},
+ FloatSemanticsInfo{8, "f8e3m4"}, FloatSemanticsInfo{19, "tf32"},
+ FloatSemanticsInfo{8, "f8e8m0fnu"}, FloatSemanticsInfo{6, "f6e3m2fn"},
+ FloatSemanticsInfo{6, "f6e2m3fn"}, FloatSemanticsInfo{4, "f4e2m1fn"},
+ FloatSemanticsInfo{80, "x86fp80"},
+};
+
+static_assert(FloatSemanticsTable.size() == static_cast<std::size_t>(FloatSemantics::Count));
+
+[[nodiscard]] const FloatSemanticsInfo *getFloatSemanticsInfo(FloatSemantics Semantics) noexcept {
+ const auto Index = static_cast<std::size_t>(Semantics);
+ if (Index >= FloatSemanticsTable.size())
+ return nullptr;
+ return &FloatSemanticsTable[Index];
+}
+
+[[nodiscard]] bool isHexDigit(char Character) noexcept {
+ return (Character >= '0' && Character <= '9') || (Character >= 'a' && Character <= 'f') ||
+ (Character >= 'A' && Character <= 'F');
+}
+
+[[nodiscard]] unsigned hexDigitValue(char Character) noexcept {
+ if (Character >= '0' && Character <= '9')
+ return static_cast<unsigned>(Character - '0');
+ if (Character >= 'a' && Character <= 'f')
+ return static_cast<unsigned>(Character - 'a') + 10U;
+ return static_cast<unsigned>(Character - 'A') + 10U;
+}
+
+[[nodiscard]] bool parseHexWords(std::string_view Digits, std::uint32_t BitWidth,
+ std::vector<std::uint64_t> &Words) {
+ if (Digits.empty() || Digits.size() > (static_cast<std::size_t>(BitWidth) + 3U) / 4U)
+ return false;
+ Words.assign((BitWidth + 63U) / 64U, 0);
+ std::size_t Nibble = 0;
+ for (auto Iterator = Digits.rbegin(); Iterator != Digits.rend(); ++Iterator, ++Nibble) {
+ if (!isHexDigit(*Iterator))
+ return false;
+ Words[Nibble / 16U] |= static_cast<std::uint64_t>(hexDigitValue(*Iterator))
+ << ((Nibble % 16U) * 4U);
+ }
+ return (BitWidth % 64U) == 0 || (Words.back() >> (BitWidth % 64U)) == 0;
+}
+
+[[nodiscard]] bool parseWideFloatHexWords(std::string_view Digits,
+ std::vector<std::uint64_t> &Words) {
+ if (Digits.empty() || Digits.size() > 32U || !std::ranges::all_of(Digits, isHexDigit))
+ return false;
+ Words.assign(2, 0);
+ const auto ParseWord = [](std::string_view Text, std::uint64_t &Word) {
+ const auto Parsed = std::from_chars(Text.data(), Text.data() + Text.size(), Word, 16);
+ return Parsed.ec == std::errc{} && Parsed.ptr == Text.data() + Text.size();
+ };
+ const std::size_t FirstWordLength = std::min<std::size_t>(Digits.size(), 16U);
+ if (!ParseWord(Digits.substr(0, FirstWordLength), Words[0]))
+ return false;
+ if (Digits.size() == FirstWordLength)
+ return true;
+ return ParseWord(Digits.substr(FirstWordLength), Words[1]);
+}
+
+enum class SpecialFloatLiteralKind : std::uint8_t {
+ Infinity,
+ QuietNaN,
+ SignalingNaN,
+};
+
+struct SpecialFloatLiteral final {
+ SpecialFloatLiteralKind Kind = SpecialFloatLiteralKind::Infinity;
+ bool Negative = false;
+ std::array<std::uint64_t, 2> Payload{};
+};
+
+[[nodiscard]] Expected<std::optional<SpecialFloatLiteral>>
+parseSpecialFloatLiteral(std::string_view Token) {
+ if (!Token.starts_with('+') && !Token.starts_with('-'))
+ return std::optional<SpecialFloatLiteral>{};
+
+ SpecialFloatLiteral Result;
+ Result.Negative = Token.front() == '-';
+ Token.remove_prefix(1);
+ if (Token == "inf")
+ return Result;
+ if (Token == "qnan") {
+ Result.Kind = SpecialFloatLiteralKind::QuietNaN;
+ return Result;
+ }
+
+ if (!Token.starts_with("nan") && !Token.starts_with("snan"))
+ return std::optional<SpecialFloatLiteral>{};
+
+ const bool IsSignaling = Token.starts_with("snan");
+ const std::size_t NameLength = IsSignaling ? 4U : 3U;
+ const std::string_view Suffix = Token.substr(NameLength);
+ Result.Kind =
+ IsSignaling ? SpecialFloatLiteralKind::SignalingNaN : SpecialFloatLiteralKind::QuietNaN;
+ if (Suffix.size() < 5 || Suffix.front() != '(' || Suffix.back() != ')' ||
+ !Suffix.substr(1).starts_with("0x")) {
+ return makeUnexpected(ErrorCode::ParseError, "invalid floating-point NaN payload");
+ }
+
+ const std::string_view Digits = Suffix.substr(3, Suffix.size() - 4U);
+ if (Digits.empty() || !std::ranges::all_of(Digits, isHexDigit)) {
+ return makeUnexpected(ErrorCode::ParseError, "invalid floating-point NaN payload");
+ }
+ std::size_t Nibble = 0;
+ for (auto Iterator = Digits.rbegin(); Iterator != Digits.rend(); ++Iterator, ++Nibble) {
+ if (Nibble >= 32U)
+ break;
+ Result.Payload[Nibble / 16U] |= static_cast<std::uint64_t>(hexDigitValue(*Iterator))
+ << ((Nibble % 16U) * 4U);
+ }
+ return Result;
+}
+
+void setFloatBit(std::vector<std::uint64_t> &Words, std::uint32_t Bit) {
+ Words[Bit / 64U] |= std::uint64_t{1} << (Bit % 64U);
+}
+
+void clearFloatBit(std::vector<std::uint64_t> &Words, std::uint32_t Bit) {
+ Words[Bit / 64U] &= ~(std::uint64_t{1} << (Bit % 64U));
+}
+
+[[nodiscard]] bool hasFloatBit(std::span<const std::uint64_t> Words, std::uint32_t Bit) noexcept {
+ return (Words[Bit / 64U] & (std::uint64_t{1} << (Bit % 64U))) != 0;
+}
+
+void copyNaNPayload(std::vector<std::uint64_t> &Words, const std::array<std::uint64_t, 2> &Payload,
+ std::uint32_t PayloadBitWidth) {
+ for (std::uint32_t Bit = 0; Bit < PayloadBitWidth; ++Bit) {
+ if ((Payload[Bit / 64U] & (std::uint64_t{1} << (Bit % 64U))) != 0)
+ setFloatBit(Words, Bit);
+ }
+}
+
+void makeBinarySpecialFloat(std::vector<std::uint64_t> &Words, std::uint32_t BitWidth,
+ std::uint32_t ExponentBitWidth, const SpecialFloatLiteral &Literal) {
+ const std::uint32_t FractionBitWidth = BitWidth - ExponentBitWidth - 1U;
+ if (Literal.Negative)
+ setFloatBit(Words, BitWidth - 1U);
+ for (std::uint32_t Bit = FractionBitWidth; Bit < FractionBitWidth + ExponentBitWidth; ++Bit) {
+ setFloatBit(Words, Bit);
+ }
+ if (Literal.Kind == SpecialFloatLiteralKind::Infinity)
+ return;
+
+ copyNaNPayload(Words, Literal.Payload, FractionBitWidth);
+ const std::uint32_t QuietNaNBit = FractionBitWidth - 1U;
+ if (Literal.Kind == SpecialFloatLiteralKind::QuietNaN) {
+ setFloatBit(Words, QuietNaNBit);
+ return;
+ }
+ clearFloatBit(Words, QuietNaNBit);
+ bool HasPayload = false;
+ for (std::uint32_t Bit = 0; Bit < FractionBitWidth; ++Bit)
+ HasPayload = HasPayload || hasFloatBit(Words, Bit);
+ if (!HasPayload)
+ setFloatBit(Words, QuietNaNBit - 1U);
+}
+
+[[nodiscard]] Expected<std::vector<std::uint64_t>>
+makeSpecialFloatWords(FloatSemantics Semantics, const SpecialFloatLiteral &Literal) {
+ const auto BitWidth = getFloatSemanticsBitWidth(Semantics);
+ if (!BitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument, "floating-point semantics is unknown");
+ std::vector<std::uint64_t> Words((*BitWidth + 63U) / 64U, 0);
+ switch (Semantics) {
+ case FloatSemantics::IEEEHalf:
+ makeBinarySpecialFloat(Words, *BitWidth, 5, Literal);
+ return Words;
+ case FloatSemantics::BFloat:
+ case FloatSemantics::IEEESingle:
+ makeBinarySpecialFloat(Words, *BitWidth, 8, Literal);
+ return Words;
+ case FloatSemantics::IEEEDouble:
+ makeBinarySpecialFloat(Words, *BitWidth, 11, Literal);
+ return Words;
+ case FloatSemantics::IEEEQuad:
+ makeBinarySpecialFloat(Words, *BitWidth, 15, Literal);
+ return Words;
+ case FloatSemantics::X87DoubleExtended: {
+ if (Literal.Negative)
+ setFloatBit(Words, 79);
+ for (std::uint32_t Bit = 64; Bit < 79; ++Bit)
+ setFloatBit(Words, Bit);
+ if (Literal.Kind == SpecialFloatLiteralKind::Infinity) {
+ setFloatBit(Words, 63);
+ return Words;
+ }
+ copyNaNPayload(Words, Literal.Payload, 63);
+ setFloatBit(Words, 63);
+ if (Literal.Kind == SpecialFloatLiteralKind::QuietNaN) {
+ setFloatBit(Words, 62);
+ return Words;
+ }
+ clearFloatBit(Words, 62);
+ bool HasPayload = false;
+ for (std::uint32_t Bit = 0; Bit < 63; ++Bit)
+ HasPayload = HasPayload || hasFloatBit(Words, Bit);
+ if (!HasPayload)
+ setFloatBit(Words, 61);
+ return Words;
+ }
+ case FloatSemantics::PPCDoubleDouble: {
+ std::vector<std::uint64_t> HighPart(1, 0);
+ makeBinarySpecialFloat(HighPart, 64, 11, Literal);
+ Words[0] = HighPart.front();
+ return Words;
+ }
+ case FloatSemantics::Float8E5M2:
+ case FloatSemantics::Float8E5M2FNUZ:
+ case FloatSemantics::Float8E4M3:
+ case FloatSemantics::Float8E4M3FN:
+ case FloatSemantics::Float8E4M3FNUZ:
+ case FloatSemantics::Float8E4M3B11FNUZ:
+ case FloatSemantics::Float8E3M4:
+ case FloatSemantics::FloatTF32:
+ case FloatSemantics::Float8E8M0FNU:
+ case FloatSemantics::Float6E3M2FN:
+ case FloatSemantics::Float6E2M3FN:
+ case FloatSemantics::Float4E2M1FN:
+ case FloatSemantics::Count:
+ break;
+ }
+ return makeUnexpected(ErrorCode::Unsupported,
+ "floating-point special literal uses unsupported semantics");
+}
+
+struct BinaryFloatFormat final {
+ std::uint32_t Precision = 0;
+ std::int32_t MinExponent = 0;
+ std::int32_t MaxExponent = 0;
+ std::uint32_t ExponentBitWidth = 0;
+ std::uint32_t StorageBitWidth = 0;
+ bool HasExplicitIntegerBit = false;
+};
+
+[[nodiscard]] std::optional<BinaryFloatFormat>
+binaryFloatFormat(FloatSemantics Semantics) noexcept {
+ switch (Semantics) {
+ case FloatSemantics::IEEEHalf:
+ return BinaryFloatFormat{.Precision = 11,
+ .MinExponent = -14,
+ .MaxExponent = 15,
+ .ExponentBitWidth = 5,
+ .StorageBitWidth = 16};
+ case FloatSemantics::BFloat:
+ return BinaryFloatFormat{.Precision = 8,
+ .MinExponent = -126,
+ .MaxExponent = 127,
+ .ExponentBitWidth = 8,
+ .StorageBitWidth = 16};
+ case FloatSemantics::IEEESingle:
+ return BinaryFloatFormat{.Precision = 24,
+ .MinExponent = -126,
+ .MaxExponent = 127,
+ .ExponentBitWidth = 8,
+ .StorageBitWidth = 32};
+ case FloatSemantics::IEEEDouble:
+ return BinaryFloatFormat{.Precision = 53,
+ .MinExponent = -1022,
+ .MaxExponent = 1023,
+ .ExponentBitWidth = 11,
+ .StorageBitWidth = 64};
+ case FloatSemantics::IEEEQuad:
+ return BinaryFloatFormat{.Precision = 113,
+ .MinExponent = -16382,
+ .MaxExponent = 16383,
+ .ExponentBitWidth = 15,
+ .StorageBitWidth = 128};
+ case FloatSemantics::X87DoubleExtended:
+ return BinaryFloatFormat{.Precision = 64,
+ .MinExponent = -16382,
+ .MaxExponent = 16383,
+ .ExponentBitWidth = 15,
+ .StorageBitWidth = 80,
+ .HasExplicitIntegerBit = true};
+ case FloatSemantics::PPCDoubleDouble:
+ // Decimal PPC double-double literals use 106 bits of precision and are
+ // materialized as a canonical pair of doubles.
+ return BinaryFloatFormat{.Precision = 106,
+ .MinExponent = -969,
+ .MaxExponent = 1023,
+ .ExponentBitWidth = 0,
+ .StorageBitWidth = 128};
+ case FloatSemantics::Float8E5M2:
+ case FloatSemantics::Float8E5M2FNUZ:
+ case FloatSemantics::Float8E4M3:
+ case FloatSemantics::Float8E4M3FN:
+ case FloatSemantics::Float8E4M3FNUZ:
+ case FloatSemantics::Float8E4M3B11FNUZ:
+ case FloatSemantics::Float8E3M4:
+ case FloatSemantics::FloatTF32:
+ case FloatSemantics::Float8E8M0FNU:
+ case FloatSemantics::Float6E3M2FN:
+ case FloatSemantics::Float6E2M3FN:
+ case FloatSemantics::Float4E2M1FN:
+ case FloatSemantics::Count:
+ return std::nullopt;
+ }
+ return std::nullopt;
+}
+
+struct RoundedBinaryFloat final {
+ bool IsZero = false;
+ bool IsSubnormal = false;
+ std::int64_t Exponent = 0;
+ std::int64_t Scale = 0;
+ APInt Significand;
+};
+
+[[nodiscard]] RoundedBinaryFloat makeZeroRoundedBinaryFloat() {
+ RoundedBinaryFloat Result;
+ Result.IsZero = true;
+ return Result;
+}
+
+[[nodiscard]] bool checkedAddExponent(std::int64_t Left, std::int64_t Right,
+ std::int64_t &Result) noexcept {
+ if (Right > 0 && Left > std::numeric_limits<std::int64_t>::max() - Right)
+ return false;
+ if (Right < 0 && Left < std::numeric_limits<std::int64_t>::min() - Right)
+ return false;
+ Result = Left + Right;
+ return true;
+}
+
+[[nodiscard]] bool checkedSubtractExponent(std::int64_t Left, std::int64_t Right,
+ std::int64_t &Result) noexcept {
+ if (Right == std::numeric_limits<std::int64_t>::min()) {
+ if (Left >= 0)
+ return false;
+ Result = Left - Right;
+ return true;
+ }
+ return checkedAddExponent(Left, -Right, Result);
+}
+
+[[nodiscard]] Expected<APInt> divideAndRoundNearest(APInt Numerator, const APInt &Denominator) {
+ if (Denominator.isZero())
+ return makeUnexpected(ErrorCode::VerificationError,
+ "floating-point conversion has a zero denominator");
+
+ APInt Quotient;
+ const std::size_t NumeratorBits = Numerator.activeBitWidth();
+ const std::size_t DenominatorBits = Denominator.activeBitWidth();
+ if (NumeratorBits >= DenominatorBits) {
+ for (std::size_t Shift = NumeratorBits - DenominatorBits + 1U; Shift != 0; --Shift) {
+ const std::size_t ActualShift = Shift - 1U;
+ if (Numerator.compareToShifted(Denominator, ActualShift) < 0)
+ continue;
+ Numerator.subtract(Denominator.shiftedLeft(ActualShift));
+ Quotient.setBit(ActualShift);
+ }
+ }
+
+ const int HalfComparison = Numerator.shiftedLeft(1).compare(Denominator);
+ if (HalfComparison > 0 || (HalfComparison == 0 && (Quotient.word(0) & 1U) != 0))
+ Quotient.addSmall(1);
+ return Quotient;
+}
+
+[[nodiscard]] Expected<APInt> roundScaledRational(APInt Numerator, APInt Denominator,
+ std::int64_t Shift) {
+ const auto AbsoluteShift = [Shift]() -> std::uint64_t {
+ if (Shift >= 0)
+ return static_cast<std::uint64_t>(Shift);
+ return static_cast<std::uint64_t>(-(Shift + 1)) + 1U;
+ }();
+ if (AbsoluteShift > std::numeric_limits<std::size_t>::max()) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "floating-point literal has an unrepresentable binary exponent");
+ }
+ if (Shift >= 0)
+ Numerator = Numerator.shiftedLeft(static_cast<std::size_t>(AbsoluteShift));
+ else
+ Denominator = Denominator.shiftedLeft(static_cast<std::size_t>(AbsoluteShift));
+ return divideAndRoundNearest(std::move(Numerator), Denominator);
+}
+
+[[nodiscard]] Expected<std::int64_t>
+floorLog2OfRational(const APInt &Numerator, const APInt &Denominator, std::int64_t BinaryScale) {
+ if (Numerator.isZero() || Denominator.isZero()) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "floating-point conversion requires a nonzero rational value");
+ }
+ const std::size_t NumeratorBits = Numerator.activeBitWidth();
+ const std::size_t DenominatorBits = Denominator.activeBitWidth();
+ if (NumeratorBits > static_cast<std::size_t>(std::numeric_limits<std::int64_t>::max()) ||
+ DenominatorBits > static_cast<std::size_t>(std::numeric_limits<std::int64_t>::max())) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "floating-point literal significand is too large");
+ }
+ const std::int64_t BitDelta =
+ static_cast<std::int64_t>(NumeratorBits) - static_cast<std::int64_t>(DenominatorBits);
+ std::int64_t Candidate = 0;
+ if (!checkedAddExponent(BinaryScale, BitDelta, Candidate)) {
+ return makeUnexpected(BinaryScale >= 0 ? ErrorCode::ParseError : ErrorCode::Unsupported,
+ BinaryScale >= 0 ? "floating-point constant overflowed type"
+ : "floating-point constant underflowed type");
+ }
+
+ const std::int64_t RelativeShift = -BitDelta;
+ int Comparison = 0;
+ if (RelativeShift >= 0) {
+ if (static_cast<std::uint64_t>(RelativeShift) > std::numeric_limits<std::size_t>::max()) {
+ Comparison = -1;
+ } else {
+ Comparison =
+ -Denominator.compareToShifted(Numerator, static_cast<std::size_t>(RelativeShift));
+ }
+ } else {
+ const std::uint64_t AbsoluteShift = static_cast<std::uint64_t>(-(RelativeShift + 1)) + 1U;
+ if (AbsoluteShift > std::numeric_limits<std::size_t>::max())
+ Comparison = 1;
+ else
+ Comparison = Numerator.compareToShifted(Denominator, static_cast<std::size_t>(AbsoluteShift));
+ }
+ if (Comparison >= 0)
+ return Candidate;
+ if (Candidate == std::numeric_limits<std::int64_t>::min()) {
+ return makeUnexpected(ErrorCode::ParseError, "floating-point constant underflowed type");
+ }
+ return Candidate - 1;
+}
+
+[[nodiscard]] Expected<RoundedBinaryFloat> roundBinaryRational(const BinaryFloatFormat &Format,
+ const APInt &Numerator,
+ const APInt &Denominator,
+ std::int64_t BinaryScale,
+ bool PermitZeroResult = false) {
+ if (Numerator.isZero())
+ return makeZeroRoundedBinaryFloat();
+
+ auto FloorExponent = floorLog2OfRational(Numerator, Denominator, BinaryScale);
+ if (!FloorExponent)
+ return std::unexpected(FloorExponent.error());
+ if (*FloorExponent > Format.MaxExponent) {
+ return makeUnexpected(ErrorCode::ParseError, "floating-point constant overflowed type");
+ }
+
+ const std::int64_t SmallestUnit =
+ static_cast<std::int64_t>(Format.MinExponent) - (Format.Precision - 1U);
+ if (*FloorExponent < SmallestUnit - 1) {
+ if (PermitZeroResult)
+ return makeZeroRoundedBinaryFloat();
+ return makeUnexpected(ErrorCode::ParseError, "floating-point constant underflowed type");
+ }
+
+ const bool StartsNormal = *FloorExponent >= Format.MinExponent;
+ const std::int64_t Unit = StartsNormal ? *FloorExponent - (Format.Precision - 1U) : SmallestUnit;
+ std::int64_t Shift = 0;
+ if (!checkedSubtractExponent(BinaryScale, Unit, Shift)) {
+ return makeUnexpected(BinaryScale >= 0 ? ErrorCode::ParseError : ErrorCode::Unsupported,
+ BinaryScale >= 0 ? "floating-point constant overflowed type"
+ : "floating-point constant underflowed type");
+ }
+ auto Significand = roundScaledRational(Numerator, Denominator, Shift);
+ if (!Significand)
+ return std::unexpected(Significand.error());
+ if (Significand->isZero()) {
+ if (PermitZeroResult)
+ return makeZeroRoundedBinaryFloat();
+ return makeUnexpected(ErrorCode::ParseError, "floating-point constant underflowed type");
+ }
+
+ RoundedBinaryFloat Result;
+ Result.Significand = std::move(*Significand);
+ if (StartsNormal) {
+ Result.Exponent = *FloorExponent;
+ if (Result.Significand.activeBitWidth() > Format.Precision) {
+ Result.Significand.shiftRight(1);
+ if (Result.Exponent == Format.MaxExponent) {
+ return makeUnexpected(ErrorCode::ParseError, "floating-point constant overflowed type");
+ }
+ ++Result.Exponent;
+ }
+ Result.Scale = Result.Exponent - (Format.Precision - 1U);
+ return Result;
+ }
+
+ if (Result.Significand.activeBitWidth() >= Format.Precision) {
+ Result.IsSubnormal = false;
+ Result.Exponent = Format.MinExponent;
+ Result.Scale = Result.Exponent - (Format.Precision - 1U);
+ return Result;
+ }
+ Result.IsSubnormal = true;
+ Result.Exponent = Format.MinExponent;
+ Result.Scale = SmallestUnit;
+ return Result;
+}
+
+void appendSignificandWords(std::vector<std::uint64_t> &Words, const APInt &Significand) {
+ for (std::size_t Index = 0; Index < Words.size(); ++Index)
+ Words[Index] = Significand.word(Index);
+}
+
+[[nodiscard]] Expected<std::vector<std::uint64_t>>
+packIEEEBinaryFloat(const BinaryFloatFormat &Format, const RoundedBinaryFloat &Value,
+ bool Negative) {
+ if (Format.HasExplicitIntegerBit || Format.ExponentBitWidth == 0 || Format.StorageBitWidth == 0) {
+ return makeUnexpected(ErrorCode::VerificationError,
+ "floating-point format does not use IEEE binary storage");
+ }
+ std::vector<std::uint64_t> Words((Format.StorageBitWidth + 63U) / 64U, 0);
+ if (Value.IsZero) {
+ if (Negative)
+ setFloatBit(Words, Format.StorageBitWidth - 1U);
+ return Words;
+ }
+
+ appendSignificandWords(Words, Value.Significand);
+ const std::uint32_t FractionBitWidth = Format.Precision - 1U;
+ if (!Value.IsSubnormal)
+ clearFloatBit(Words, FractionBitWidth);
+ const std::int64_t Bias = 1 - static_cast<std::int64_t>(Format.MinExponent);
+ const std::uint64_t Exponent =
+ Value.IsSubnormal ? 0 : static_cast<std::uint64_t>(Value.Exponent + Bias);
+ for (std::uint32_t Bit = 0; Bit < Format.ExponentBitWidth; ++Bit) {
+ if ((Exponent & (std::uint64_t{1} << Bit)) != 0)
+ setFloatBit(Words, FractionBitWidth + Bit);
+ }
+ if (Negative)
+ setFloatBit(Words, Format.StorageBitWidth - 1U);
+ return Words;
+}
+
+[[nodiscard]] Expected<std::vector<std::uint64_t>>
+packX87Float(const BinaryFloatFormat &Format, const RoundedBinaryFloat &Value, bool Negative) {
+ if (!Format.HasExplicitIntegerBit || Format.StorageBitWidth != 80 || Format.Precision != 64) {
+ return makeUnexpected(ErrorCode::VerificationError, "x87 floating-point format is invalid");
+ }
+ std::vector<std::uint64_t> Words(2, 0);
+ if (Value.IsZero) {
+ if (Negative)
+ setFloatBit(Words, 79);
+ return Words;
+ }
+ Words[0] = Value.Significand.word(0);
+ if (!Value.IsSubnormal) {
+ const std::int64_t Bias = 1 - static_cast<std::int64_t>(Format.MinExponent);
+ Words[1] = static_cast<std::uint64_t>(Value.Exponent + Bias);
+ }
+ if (Negative)
+ setFloatBit(Words, 79);
+ return Words;
+}
+
+[[nodiscard]] Expected<std::vector<std::uint64_t>>
+packPPCDoubleDouble(const RoundedBinaryFloat &Value, bool Negative) {
+ const auto DoubleFormat = binaryFloatFormat(FloatSemantics::IEEEDouble);
+ if (!DoubleFormat)
+ return makeUnexpected(ErrorCode::VerificationError, "IEEE double format is unavailable");
+ if (Value.IsZero) {
+ RoundedBinaryFloat Zero = makeZeroRoundedBinaryFloat();
+ auto High = packIEEEBinaryFloat(*DoubleFormat, Zero, Negative);
+ if (!High)
+ return std::unexpected(High.error());
+ return std::vector<std::uint64_t>{High->front(), 0};
+ }
+
+ APInt One(1);
+ auto High = roundBinaryRational(*DoubleFormat, Value.Significand, One, Value.Scale, true);
+ if (!High)
+ return std::unexpected(High.error());
+ auto HighWords = packIEEEBinaryFloat(*DoubleFormat, *High, Negative);
+ if (!HighWords)
+ return std::unexpected(HighWords.error());
+
+ APInt SourceMagnitude = Value.Significand;
+ APInt HighMagnitude = High->Significand;
+ const std::int64_t CommonScale = std::min(Value.Scale, High->Scale);
+ if (!SourceMagnitude.isZero()) {
+ const std::int64_t SourceShift = Value.Scale - CommonScale;
+ if (SourceShift > 0)
+ SourceMagnitude = SourceMagnitude.shiftedLeft(static_cast<std::size_t>(SourceShift));
+ }
+ if (!HighMagnitude.isZero()) {
+ const std::int64_t HighShift = High->Scale - CommonScale;
+ if (HighShift > 0)
+ HighMagnitude = HighMagnitude.shiftedLeft(static_cast<std::size_t>(HighShift));
+ }
+
+ bool LowNegative = false;
+ APInt LowMagnitude;
+ if (SourceMagnitude.compare(HighMagnitude) >= 0) {
+ LowMagnitude = std::move(SourceMagnitude);
+ LowMagnitude.subtract(HighMagnitude);
+ LowNegative = Negative;
+ } else {
+ LowMagnitude = std::move(HighMagnitude);
+ LowMagnitude.subtract(SourceMagnitude);
+ LowNegative = !Negative;
+ }
+
+ auto Low = roundBinaryRational(*DoubleFormat, LowMagnitude, One, CommonScale, true);
+ if (!Low)
+ return std::unexpected(Low.error());
+ auto LowWords = packIEEEBinaryFloat(*DoubleFormat, *Low, LowNegative);
+ if (!LowWords)
+ return std::unexpected(LowWords.error());
+ return std::vector<std::uint64_t>{HighWords->front(), LowWords->front()};
+}
+
+[[nodiscard]] Expected<std::vector<std::uint64_t>>
+convertRationalToFloatWords(FloatSemantics Semantics, bool Negative, const APInt &Numerator,
+ const APInt &Denominator, std::int64_t BinaryScale) {
+ const auto Format = binaryFloatFormat(Semantics);
+ if (!Format) {
+ return makeUnexpected(ErrorCode::Unsupported,
+ "floating-point literal uses unsupported semantics");
+ }
+ auto Rounded = roundBinaryRational(*Format, Numerator, Denominator, BinaryScale);
+ if (!Rounded)
+ return std::unexpected(Rounded.error());
+ if (Semantics == FloatSemantics::PPCDoubleDouble) {
+ return packPPCDoubleDouble(*Rounded, Negative);
+ }
+ if (Format->HasExplicitIntegerBit)
+ return packX87Float(*Format, *Rounded, Negative);
+ return packIEEEBinaryFloat(*Format, *Rounded, Negative);
+}
+
+[[nodiscard]] bool isDecimalDigit(char Character) noexcept {
+ return Character >= '0' && Character <= '9';
+}
+
+[[nodiscard]] Expected<std::int32_t> parseFloatingExponent(std::string_view Text,
+ std::int32_t Limit) {
+ if (Text.empty())
+ return makeUnexpected(ErrorCode::ParseError, "floating-point exponent has no digits");
+ bool Negative = false;
+ if (Text.front() == '+' || Text.front() == '-') {
+ Negative = Text.front() == '-';
+ Text.remove_prefix(1);
+ }
+ if (Text.empty())
+ return makeUnexpected(ErrorCode::ParseError, "floating-point exponent has no digits");
+
+ std::int32_t Value = 0;
+ for (const char Character : Text) {
+ if (!isDecimalDigit(Character)) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "floating-point exponent contains a non-decimal digit");
+ }
+ const std::int32_t Digit = Character - '0';
+ if (Value >= Limit || Value > (Limit - Digit) / 10) {
+ Value = Limit;
+ continue;
+ }
+ Value = Value * 10 + Digit;
+ }
+ return Negative ? -Value : Value;
+}
+
+[[nodiscard]] APInt parseDecimalSignificand(std::string_view Digits) {
+ APInt Result;
+ std::size_t Position = 0;
+ std::size_t FirstChunkLength = Digits.size() % 9U;
+ if (FirstChunkLength == 0)
+ FirstChunkLength = std::min<std::size_t>(Digits.size(), 9U);
+ while (Position < Digits.size()) {
+ const std::size_t Length = Position == 0 ? FirstChunkLength : 9U;
+ std::uint32_t Chunk = 0;
+ for (std::size_t Index = 0; Index < Length; ++Index)
+ Chunk = Chunk * 10U + static_cast<std::uint32_t>(Digits[Position + Index] - '0');
+ Result.multiplySmall(Position == 0 ? 1U : 1000000000U);
+ Result.addSmall(Chunk);
+ Position += Length;
+ }
+ return Result;
+}
+
+[[nodiscard]] APInt parseHexSignificand(std::string_view Digits) {
+ APInt Result;
+ for (const char Character : Digits) {
+ Result.multiplySmall(16U);
+ Result.addSmall(hexDigitValue(Character));
+ }
+ return Result;
+}
+
+void multiplyByPowerOfFive(APInt &Value, std::uint64_t Exponent) {
+ for (std::uint64_t Index = 0; Index < Exponent; ++Index)
+ Value.multiplySmall(5U);
+}
+
+[[nodiscard]] APInt powerOfFive(std::uint64_t Exponent) {
+ APInt Result(1);
+ multiplyByPowerOfFive(Result, Exponent);
+ return Result;
+}
+
+[[nodiscard]] bool decimalDefinitelyOverflows(const BinaryFloatFormat &Format,
+ std::int64_t NormalizedExponent) noexcept {
+ const __int128 Left = (static_cast<__int128>(NormalizedExponent) - 1) * 42039;
+ const __int128 Right = static_cast<__int128>(12655) * Format.MaxExponent;
+ return Left >= Right;
+}
+
+[[nodiscard]] bool decimalDefinitelyUnderflows(const BinaryFloatFormat &Format,
+ std::int64_t NormalizedExponent) noexcept {
+ const __int128 Left = (static_cast<__int128>(NormalizedExponent) + 1) * 28738;
+ const __int128 Right = static_cast<__int128>(8651) *
+ (static_cast<std::int64_t>(Format.MinExponent) - Format.Precision);
+ return Left <= Right;
+}
+
+struct ParsedFiniteFloatLiteral final {
+ bool Negative = false;
+ APInt Numerator;
+ APInt Denominator{1};
+ std::int64_t BinaryScale = 0;
+};
+
+[[nodiscard]] Expected<ParsedFiniteFloatLiteral>
+parseDecimalFloatLiteral(std::string_view Token, const BinaryFloatFormat &Format) {
+ ParsedFiniteFloatLiteral Result;
+ if (Token.starts_with('+') || Token.starts_with('-')) {
+ Result.Negative = Token.front() == '-';
+ Token.remove_prefix(1);
+ }
+ if (Token.empty())
+ return makeUnexpected(ErrorCode::ParseError, "floating-point literal has no digits");
+
+ std::size_t Position = 0;
+ const std::size_t IntegerBegin = Position;
+ while (Position < Token.size() && isDecimalDigit(Token[Position]))
+ ++Position;
+ if (IntegerBegin == Position || Position == Token.size() || Token[Position] != '.') {
+ return makeUnexpected(ErrorCode::ParseError,
+ "decimal floating-point literal requires a decimal point");
+ }
+
+ std::string Digits(Token.substr(IntegerBegin, Position - IntegerBegin));
+ ++Position;
+ const std::size_t FractionBegin = Position;
+ while (Position < Token.size() && isDecimalDigit(Token[Position]))
+ ++Position;
+ Digits.append(Token.substr(FractionBegin, Position - FractionBegin));
+ const std::size_t FractionDigits = Position - FractionBegin;
+
+ std::int32_t Exponent = 0;
+ if (Position < Token.size() && (Token[Position] == 'e' || Token[Position] == 'E')) {
+ auto ParsedExponent = parseFloatingExponent(Token.substr(Position + 1U), 24000);
+ if (!ParsedExponent)
+ return std::unexpected(ParsedExponent.error());
+ Exponent = *ParsedExponent;
+ Position = Token.size();
+ }
+ if (Position != Token.size()) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "decimal floating-point literal has an invalid suffix");
+ }
+
+ const std::size_t FirstSignificant = Digits.find_first_not_of('0');
+ if (FirstSignificant == std::string::npos)
+ return Result;
+ const std::size_t LastSignificant = Digits.find_last_not_of('0');
+ const std::string_view Significant(Digits.data() + FirstSignificant,
+ LastSignificant - FirstSignificant + 1U);
+ const std::size_t TrailingZeroCount = Digits.size() - LastSignificant - 1U;
+ std::int64_t DecimalScale = static_cast<std::int64_t>(Exponent) -
+ static_cast<std::int64_t>(FractionDigits) +
+ static_cast<std::int64_t>(TrailingZeroCount);
+ const std::int64_t NormalizedExponent =
+ DecimalScale + static_cast<std::int64_t>(Significant.size() - 1U);
+ if (decimalDefinitelyOverflows(Format, NormalizedExponent)) {
+ return makeUnexpected(ErrorCode::ParseError, "floating-point constant overflowed type");
+ }
+ if (decimalDefinitelyUnderflows(Format, NormalizedExponent)) {
+ return makeUnexpected(ErrorCode::ParseError, "floating-point constant underflowed type");
+ }
+
+ Result.Numerator = parseDecimalSignificand(Significant);
+ Result.BinaryScale = DecimalScale;
+ if (DecimalScale >= 0) {
+ multiplyByPowerOfFive(Result.Numerator, static_cast<std::uint64_t>(DecimalScale));
+ } else {
+ Result.Denominator = powerOfFive(static_cast<std::uint64_t>(-(DecimalScale + 1)) + 1U);
+ }
+ return Result;
+}
+
+[[nodiscard]] Expected<ParsedFiniteFloatLiteral> parseHexFloatLiteral(std::string_view Token) {
+ ParsedFiniteFloatLiteral Result;
+ if (Token.starts_with('+') || Token.starts_with('-')) {
+ Result.Negative = Token.front() == '-';
+ Token.remove_prefix(1);
+ }
+ if (!Token.starts_with("0x")) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "hexadecimal floating-point literal must use the 0x prefix");
+ }
+ std::size_t Position = 2;
+ const std::size_t IntegerBegin = Position;
+ while (Position < Token.size() && isHexDigit(Token[Position]))
+ ++Position;
+ if (IntegerBegin == Position || Position == Token.size() || Token[Position] != '.') {
+ return makeUnexpected(ErrorCode::ParseError,
+ "hexadecimal floating-point literal requires a hexadecimal point");
+ }
+ std::string Digits(Token.substr(IntegerBegin, Position - IntegerBegin));
+ ++Position;
+ const std::size_t FractionBegin = Position;
+ while (Position < Token.size() && isHexDigit(Token[Position]))
+ ++Position;
+ Digits.append(Token.substr(FractionBegin, Position - FractionBegin));
+ const std::size_t FractionDigits = Position - FractionBegin;
+ if (Position == Token.size() || (Token[Position] != 'p' && Token[Position] != 'P')) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "hexadecimal floating-point literal requires a binary exponent");
+ }
+ auto Exponent = parseFloatingExponent(Token.substr(Position + 1U), 32767);
+ if (!Exponent)
+ return std::unexpected(Exponent.error());
+
+ const std::size_t FirstSignificant = Digits.find_first_not_of('0');
+ if (FirstSignificant == std::string::npos)
+ return Result;
+ const std::string_view Significant(Digits.data() + FirstSignificant,
+ Digits.size() - FirstSignificant);
+ Result.Numerator = parseHexSignificand(Significant);
+ Result.BinaryScale =
+ static_cast<std::int64_t>(*Exponent) - static_cast<std::int64_t>(FractionDigits) * 4;
+ return Result;
+}
+
+[[nodiscard]] Expected<std::uint64_t> parseRawDoubleBits(std::string_view Digits) {
+ if (Digits.empty())
+ return makeUnexpected(ErrorCode::ParseError,
+ "hexadecimal floating-point literal has no digits");
+ std::uint64_t Result = 0;
+ for (const char Character : Digits) {
+ if (!isHexDigit(Character)) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "hexadecimal floating-point literal contains a non-hexadecimal digit");
+ }
+ const std::uint64_t Digit = hexDigitValue(Character);
+ if (Result > (std::numeric_limits<std::uint64_t>::max() - Digit) / 16U) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "hexadecimal floating-point literal does not fit IEEE double");
+ }
+ Result = Result * 16U + Digit;
+ }
+ return Result;
+}
+
+[[nodiscard]] int compareScaledBinaryIntegers(const APInt &Left, std::int64_t LeftScale,
+ const APInt &Right, std::int64_t RightScale) {
+ if (Left.isZero())
+ return Right.isZero() ? 0 : -1;
+ if (Right.isZero())
+ return 1;
+ if (LeftScale == RightScale)
+ return Left.compare(Right);
+ if (LeftScale > RightScale)
+ return -Right.compareToShifted(Left, static_cast<std::size_t>(LeftScale - RightScale));
+ return Left.compareToShifted(Right, static_cast<std::size_t>(RightScale - LeftScale));
+}
+
+[[nodiscard]] Expected<std::vector<std::uint64_t>>
+convertRawDoubleNaN(FloatSemantics Semantics, bool Negative, std::uint64_t Fraction) {
+ if (Semantics == FloatSemantics::IEEEDouble) {
+ return std::vector<std::uint64_t>{(Negative ? std::uint64_t{1} << 63U : 0) |
+ 0x7ff0000000000000ULL | Fraction};
+ }
+ const auto Format = binaryFloatFormat(Semantics);
+ if (!Format || Format->HasExplicitIntegerBit || Format->StorageBitWidth > 64 ||
+ (Semantics != FloatSemantics::IEEEHalf && Semantics != FloatSemantics::BFloat &&
+ Semantics != FloatSemantics::IEEESingle)) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "unprefixed hexadecimal literal is invalid for type");
+ }
+ const std::uint32_t TargetFractionBits = Format->Precision - 1U;
+ const std::uint32_t DroppedBits = 53U - Format->Precision;
+ const std::uint64_t DroppedMask = (std::uint64_t{1} << DroppedBits) - 1U;
+ if ((Fraction & DroppedMask) != 0) {
+ return makeUnexpected(
+ ErrorCode::ParseError,
+ "hexadecimal floating-point literal is not exactly representable by its type");
+ }
+
+ const bool IsSignaling = (Fraction & (std::uint64_t{1} << 51U)) == 0;
+ std::uint64_t TargetFraction = Fraction >> DroppedBits;
+ const std::uint64_t QuietBit = std::uint64_t{1} << (TargetFractionBits - 1U);
+ if (IsSignaling) {
+ TargetFraction &= ~QuietBit;
+ if ((TargetFraction & (QuietBit - 1U)) == 0)
+ TargetFraction |= QuietBit >> 1U;
+ } else {
+ TargetFraction |= QuietBit;
+ }
+ const std::uint64_t Sign = Negative ? std::uint64_t{1} << (Format->StorageBitWidth - 1U) : 0;
+ const std::uint64_t Exponent = (std::uint64_t{1} << Format->ExponentBitWidth) - 1U;
+ return std::vector<std::uint64_t>{Sign | (Exponent << TargetFractionBits) | TargetFraction};
+}
+
+[[nodiscard]] Expected<std::vector<std::uint64_t>> convertRawDoubleLiteral(FloatSemantics Semantics,
+ std::uint64_t Bits) {
+ if (Semantics != FloatSemantics::IEEEHalf && Semantics != FloatSemantics::BFloat &&
+ Semantics != FloatSemantics::IEEESingle && Semantics != FloatSemantics::IEEEDouble) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "unprefixed hexadecimal literal is invalid for type");
+ }
+ if (Semantics == FloatSemantics::IEEEDouble)
+ return std::vector<std::uint64_t>{Bits};
+
+ const bool Negative = (Bits >> 63U) != 0;
+ const std::uint64_t Exponent = (Bits >> 52U) & 0x7ffU;
+ const std::uint64_t Fraction = Bits & 0x000fffffffffffffULL;
+ if (Exponent == 0x7ffU) {
+ if (Fraction != 0)
+ return convertRawDoubleNaN(Semantics, Negative, Fraction);
+ SpecialFloatLiteral Infinity{.Kind = SpecialFloatLiteralKind::Infinity, .Negative = Negative};
+ return makeSpecialFloatWords(Semantics, Infinity);
+ }
+
+ const auto Format = binaryFloatFormat(Semantics);
+ if (!Format)
+ return makeUnexpected(ErrorCode::VerificationError, "IEEE target format is unavailable");
+ if (Exponent == 0 && Fraction == 0) {
+ RoundedBinaryFloat Zero = makeZeroRoundedBinaryFloat();
+ return packIEEEBinaryFloat(*Format, Zero, Negative);
+ }
+
+ const bool IsSubnormal = Exponent == 0;
+ const std::uint64_t Significand = IsSubnormal ? Fraction : (std::uint64_t{1} << 52U) | Fraction;
+ const std::int64_t SourceScale =
+ (IsSubnormal ? -1022 : static_cast<std::int64_t>(Exponent) - 1023) - 52;
+ const APInt Source(Significand);
+ const APInt One(1);
+ auto Rounded = roundBinaryRational(*Format, Source, One, SourceScale);
+ if (!Rounded)
+ return std::unexpected(Rounded.error());
+ if (compareScaledBinaryIntegers(Source, SourceScale, Rounded->Significand, Rounded->Scale) != 0) {
+ return makeUnexpected(
+ ErrorCode::ParseError,
+ "hexadecimal floating-point literal is not exactly representable by its type");
+ }
+ return packIEEEBinaryFloat(*Format, *Rounded, Negative);
+}
+
+enum class PrintedFloatCategory : std::uint8_t {
+ Zero,
+ Finite,
+ Infinity,
+ QuietNaN,
+ SignalingNaN,
+};
+
+struct PrintedBinaryFloat final {
+ PrintedFloatCategory Category = PrintedFloatCategory::Zero;
+ bool Negative = false;
+ APInt Significand;
+ std::int32_t BinaryExponent = 0;
+ APInt NaNPayload;
+ std::uint32_t QuietNaNBit = 0;
+};
+
+[[nodiscard]] std::string hexadecimalWords(std::span<const std::uint64_t> Words,
+ std::uint32_t BitWidth) {
+ constexpr std::string_view Digits = "0123456789ABCDEF";
+ const std::size_t DigitCount = (static_cast<std::size_t>(BitWidth) + 3U) / 4U;
+ std::string Result(DigitCount, '0');
+ for (std::size_t Index = 0; Index < DigitCount; ++Index) {
+ const std::size_t Bit = Index * 4U;
+ const std::uint64_t Nibble = (Words[Bit / 64U] >> (Bit % 64U)) & 0xFU;
+ Result[DigitCount - Index - 1U] = Digits[static_cast<std::size_t>(Nibble)];
+ }
+ return Result;
+}
+
+[[nodiscard]] std::uint64_t extractFloatField(std::span<const std::uint64_t> Words,
+ std::uint32_t Begin, std::uint32_t Width) noexcept {
+ std::uint64_t Result = 0;
+ for (std::uint32_t Bit = 0; Bit < Width; ++Bit) {
+ if (hasFloatBit(Words, Begin + Bit))
+ Result |= std::uint64_t{1} << Bit;
+ }
+ return Result;
+}
+
+[[nodiscard]] APInt extractFloatBits(std::span<const std::uint64_t> Words, std::uint32_t Begin,
+ std::uint32_t Width) {
+ APInt Result;
+ for (std::uint32_t Bit = 0; Bit < Width; ++Bit) {
+ if (hasFloatBit(Words, Begin + Bit))
+ Result.setBit(Bit);
+ }
+ return Result;
+}
+
+[[nodiscard]] std::optional<PrintedBinaryFloat> decodePrintedFloat(const APFloat &Bits) {
+ std::optional<BinaryFloatFormat> Format = binaryFloatFormat(Bits.semantics());
+ std::span<const std::uint64_t> Words = Bits.words();
+ if (!Format)
+ return std::nullopt;
+
+ if (Bits.semantics() == FloatSemantics::PPCDoubleDouble) {
+ if (Words.size() != 2 || Words[1] != 0)
+ return std::nullopt;
+ Format = binaryFloatFormat(FloatSemantics::IEEEDouble);
+ Words = Words.first(1);
+ }
+ if (!Format || Format->ExponentBitWidth == 0)
+ return std::nullopt;
+
+ PrintedBinaryFloat Result;
+ Result.Negative = hasFloatBit(Words, Format->StorageBitWidth - 1U);
+ const std::uint32_t StoredSignificandWidth =
+ Format->HasExplicitIntegerBit ? Format->Precision : Format->Precision - 1U;
+ const std::uint64_t Exponent =
+ extractFloatField(Words, StoredSignificandWidth, Format->ExponentBitWidth);
+ const std::uint64_t MaximumExponent = (std::uint64_t{1} << Format->ExponentBitWidth) - 1U;
+
+ if (Exponent == MaximumExponent) {
+ const std::uint32_t PayloadWidth = Format->Precision - 1U;
+ Result.NaNPayload = extractFloatBits(Words, 0, PayloadWidth);
+ if (Result.NaNPayload.isZero()) {
+ Result.Category = PrintedFloatCategory::Infinity;
+ return Result;
+ }
+ Result.QuietNaNBit = PayloadWidth - 1U;
+ Result.Category = hasFloatBit(Words, Result.QuietNaNBit) ? PrintedFloatCategory::QuietNaN
+ : PrintedFloatCategory::SignalingNaN;
+ return Result;
+ }
+
+ Result.Significand = extractFloatBits(Words, 0, StoredSignificandWidth);
+ if (Exponent != 0 && !Format->HasExplicitIntegerBit)
+ Result.Significand.setBit(Format->Precision - 1U);
+ if (Result.Significand.isZero()) {
+ Result.Category = PrintedFloatCategory::Zero;
+ return Result;
+ }
+
+ const std::int64_t Bias = 1 - static_cast<std::int64_t>(Format->MinExponent);
+ const std::int64_t UnbiasedExponent =
+ Exponent == 0 ? Format->MinExponent : static_cast<std::int64_t>(Exponent) - Bias;
+ Result.BinaryExponent = static_cast<std::int32_t>(UnbiasedExponent - (Format->Precision - 1U));
+ Result.Category = PrintedFloatCategory::Finite;
+ return Result;
+}
+
+[[nodiscard]] std::string printNaNPayload(APInt Payload, std::uint32_t QuietNaNBit) {
+ Payload.clearBit(QuietNaNBit);
+ const auto Width =
+ static_cast<std::uint32_t>(std::max<std::size_t>(Payload.activeBitWidth(), 1U));
+ std::array<std::uint64_t, 2> Words{Payload.word(0), Payload.word(1)};
+ std::string Digits = hexadecimalWords(Words, Width);
+ const std::size_t FirstNonzero = Digits.find_first_not_of('0');
+ if (FirstNonzero == std::string::npos)
+ return "0x0";
+ Digits.erase(0, FirstNonzero);
+ return "0x" + Digits;
+}
+
+[[nodiscard]] std::string formatFiniteFloat(PrintedBinaryFloat Value) {
+ std::string Result;
+ if (Value.Negative)
+ Result.push_back('-');
+ if (Value.Category == PrintedFloatCategory::Zero) {
+ Result.append("0.000000e+00");
+ return Result;
+ }
+
+ const std::size_t TrailingZeros = Value.Significand.countrZero();
+ Value.Significand.shiftRight(TrailingZeros);
+ Value.BinaryExponent += static_cast<std::int32_t>(TrailingZeros);
+
+ std::int32_t DecimalExponent = 0;
+ if (Value.BinaryExponent >= 0) {
+ Value.Significand =
+ Value.Significand.shiftedLeft(static_cast<std::size_t>(Value.BinaryExponent));
+ } else {
+ DecimalExponent = Value.BinaryExponent;
+ for (std::int32_t Power = 0; Power < -Value.BinaryExponent; ++Power)
+ Value.Significand.multiplySmall(5);
+ }
+
+ std::string Digits = Value.Significand.toUnsignedDecimal();
+ while (Digits.size() > 1U && Digits.back() == '0') {
+ Digits.pop_back();
+ ++DecimalExponent;
+ }
+
+ constexpr std::size_t FormatPrecision = 6;
+ if (Digits.size() > FormatPrecision) {
+ std::size_t Removed = Digits.size() - FormatPrecision;
+ const bool RoundUp = Digits[FormatPrecision] >= '5';
+ Digits.resize(FormatPrecision);
+ if (RoundUp) {
+ std::size_t Position = Digits.size();
+ while (Position != 0 && Digits[Position - 1U] == '9') {
+ Digits[Position - 1U] = '0';
+ --Position;
+ }
+ if (Position == 0)
+ Digits.insert(Digits.begin(), '1');
+ else
+ ++Digits[Position - 1U];
+ }
+ while (Digits.size() > 1U && Digits.back() == '0') {
+ Digits.pop_back();
+ ++Removed;
+ }
+ DecimalExponent += static_cast<std::int32_t>(Removed);
+ }
+
+ DecimalExponent += static_cast<std::int32_t>(Digits.size() - 1U);
+ Result.push_back(Digits.front());
+ Result.push_back('.');
+ Result.append(Digits.substr(1));
+ Result.append(7U - Digits.size(), '0');
+ Result.push_back('e');
+ Result.push_back(DecimalExponent < 0 ? '-' : '+');
+ const std::uint32_t Magnitude = static_cast<std::uint32_t>(
+ DecimalExponent < 0 ? -static_cast<std::int64_t>(DecimalExponent) : DecimalExponent);
+ std::string Exponent = std::to_string(Magnitude);
+ if (Exponent.size() < 2U)
+ Result.push_back('0');
+ Result.append(Exponent);
+ return Result;
+}
+
+[[nodiscard]] std::string exactFloatingText(const APFloat &Bits) {
+ return "f0x" + hexadecimalWords(Bits.words(), Bits.bitWidth());
+}
+
+[[nodiscard]] std::string canonicalFloatingText(const APFloat &Bits) {
+ auto Decoded = decodePrintedFloat(Bits);
+ if (!Decoded)
+ return exactFloatingText(Bits);
+
+ std::string Candidate;
+ switch (Decoded->Category) {
+ case PrintedFloatCategory::Zero:
+ case PrintedFloatCategory::Finite:
+ Candidate = formatFiniteFloat(std::move(*Decoded));
+ break;
+ case PrintedFloatCategory::Infinity:
+ Candidate = Decoded->Negative ? "-inf" : "+inf";
+ break;
+ case PrintedFloatCategory::QuietNaN: {
+ APInt Payload = Decoded->NaNPayload;
+ Payload.clearBit(Decoded->QuietNaNBit);
+ if (Payload.isZero()) {
+ Candidate = Decoded->Negative ? "-qnan" : "+qnan";
+ break;
+ }
+ Candidate = Decoded->Negative ? "-nan(" : "+nan(";
+ Candidate.append(printNaNPayload(Decoded->NaNPayload, Decoded->QuietNaNBit));
+ Candidate.push_back(')');
+ break;
+ }
+ case PrintedFloatCategory::SignalingNaN:
+ Candidate = Decoded->Negative ? "-snan(" : "+snan(";
+ Candidate.append(printNaNPayload(Decoded->NaNPayload, Decoded->QuietNaNBit));
+ Candidate.push_back(')');
+ break;
+ }
+
+ auto Parsed = APFloat::parse(Bits.semantics(), Candidate);
+ if (!Parsed || *Parsed != Bits)
+ return exactFloatingText(Bits);
+ return Candidate;
+}
+
+} // namespace
+
+std::optional<std::uint32_t> getFloatSemanticsBitWidth(FloatSemantics Semantics) noexcept {
+ const auto *Info = getFloatSemanticsInfo(Semantics);
+ if (Info == nullptr)
+ return std::nullopt;
+ return Info->BitWidth;
+}
+
+std::string_view getFloatSemanticsSpelling(FloatSemantics Semantics) noexcept {
+ const auto *Info = getFloatSemanticsInfo(Semantics);
+ return Info == nullptr ? std::string_view{"invalid-float"} : Info->Spelling;
+}
+
+Expected<APFloat> APFloat::create(FloatSemantics Semantics, std::span<const std::uint64_t> Words) {
+ const auto BitWidth = getFloatSemanticsBitWidth(Semantics);
+ if (!BitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument, "floating value has unknown semantics");
+
+ const std::size_t RequiredWords = (*BitWidth + 63U) / 64U;
+ if (RequiredWords > 2 || Words.size() != RequiredWords) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "floating bit pattern has the wrong word count");
+ }
+ const std::uint32_t UsedBitsInLastWord = *BitWidth % 64U;
+ if (UsedBitsInLastWord != 0 && (Words.back() >> UsedBitsInLastWord) != 0) {
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "floating value has nonzero bits above its semantics width");
+ }
+
+ std::array<std::uint64_t, 2> StoredWords{};
+ std::ranges::copy(Words, StoredWords.begin());
+ return APFloat(Semantics, StoredWords, static_cast<std::uint8_t>(RequiredWords));
+}
+
+Expected<APFloat> APFloat::parse(FloatSemantics Semantics, std::string_view Text) {
+ const auto Format = binaryFloatFormat(Semantics);
+ if (!Format)
+ return makeUnexpected(ErrorCode::Unsupported, "floating-point semantics are unsupported");
+
+ std::vector<std::uint64_t> Words;
+ auto SpecialLiteral = parseSpecialFloatLiteral(Text);
+ if (!SpecialLiteral)
+ return std::unexpected(SpecialLiteral.error());
+ if (*SpecialLiteral) {
+ auto SpecialWords = makeSpecialFloatWords(Semantics, **SpecialLiteral);
+ if (!SpecialWords)
+ return std::unexpected(SpecialWords.error());
+ Words = std::move(*SpecialWords);
+ } else if (Text.starts_with("f0x")) {
+ const std::uint32_t BitWidth = getFloatSemanticsBitWidth(Semantics).value_or(0);
+ const std::string_view Digits = Text.substr(3);
+ if (Digits.size() != (static_cast<std::size_t>(BitWidth) + 3U) / 4U ||
+ !parseHexWords(Digits, BitWidth, Words)) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "exact floating-point bit pattern does not fit its type");
+ }
+ } else if (Text.starts_with("0x") && Text.find('.') != std::string_view::npos) {
+ auto Literal = parseHexFloatLiteral(Text);
+ if (!Literal)
+ return std::unexpected(Literal.error());
+ auto Converted = convertRationalToFloatWords(Semantics, Literal->Negative, Literal->Numerator,
+ Literal->Denominator, Literal->BinaryScale);
+ if (!Converted)
+ return std::unexpected(Converted.error());
+ Words = std::move(*Converted);
+ } else if (Text.starts_with("0x")) {
+ const std::uint32_t BitWidth = getFloatSemanticsBitWidth(Semantics).value_or(0);
+ std::string_view Digits = Text.substr(2);
+ char Prefix = '\0';
+ if (!Digits.empty() && !isHexDigit(Digits.front())) {
+ Prefix = Digits.front();
+ Digits.remove_prefix(1);
+ }
+ char ExpectedPrefix = '\0';
+ switch (Semantics) {
+ case FloatSemantics::IEEEHalf:
+ ExpectedPrefix = 'H';
+ break;
+ case FloatSemantics::BFloat:
+ ExpectedPrefix = 'R';
+ break;
+ case FloatSemantics::X87DoubleExtended:
+ ExpectedPrefix = 'K';
+ break;
+ case FloatSemantics::IEEEQuad:
+ ExpectedPrefix = 'L';
+ break;
+ case FloatSemantics::PPCDoubleDouble:
+ ExpectedPrefix = 'M';
+ break;
+ default:
+ break;
+ }
+ if (ExpectedPrefix != '\0') {
+ const bool HasWideWords =
+ Semantics == FloatSemantics::IEEEQuad || Semantics == FloatSemantics::PPCDoubleDouble;
+ const bool Parsed = HasWideWords ? parseWideFloatHexWords(Digits, Words)
+ : parseHexWords(Digits, BitWidth, Words);
+ if (Prefix != ExpectedPrefix || !Parsed) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "floating-point hexadecimal prefix does not match its type");
+ }
+ } else if (Prefix != '\0') {
+ return makeUnexpected(ErrorCode::ParseError, "unexpected floating-point hexadecimal prefix");
+ } else {
+ auto DoubleBits = parseRawDoubleBits(Digits);
+ if (!DoubleBits)
+ return std::unexpected(DoubleBits.error());
+ auto Converted = convertRawDoubleLiteral(Semantics, *DoubleBits);
+ if (!Converted)
+ return std::unexpected(Converted.error());
+ Words = std::move(*Converted);
+ }
+ } else {
+ auto Literal = parseDecimalFloatLiteral(Text, *Format);
+ if (!Literal)
+ return std::unexpected(Literal.error());
+ auto Converted = convertRationalToFloatWords(Semantics, Literal->Negative, Literal->Numerator,
+ Literal->Denominator, Literal->BinaryScale);
+ if (!Converted)
+ return std::unexpected(Converted.error());
+ Words = std::move(*Converted);
+ }
+ return create(Semantics, Words);
+}
+
+std::string APFloat::toString() const {
+ return canonicalFloatingText(*this);
+}
+
+} // namespace rcc
diff --git a/backend/lib/Support/APInt.cpp b/backend/lib/Support/APInt.cpp
new file mode 100644
index 0000000..9a6a49c
--- /dev/null
+++ b/backend/lib/Support/APInt.cpp
@@ -0,0 +1,520 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/ADT/APInt.h"
+
+#include <algorithm>
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <limits>
+#include <ranges>
+#include <span>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+[[nodiscard]] constexpr std::size_t wordCount(std::uint32_t BitWidth) noexcept {
+ return (static_cast<std::size_t>(BitWidth) + 63U) / 64U;
+}
+
+[[nodiscard]] constexpr std::uint64_t highWordMask(std::uint32_t BitWidth) noexcept {
+ const std::uint32_t UsedBits = BitWidth % 64U;
+ if (UsedBits == 0)
+ return std::numeric_limits<std::uint64_t>::max();
+ return (std::uint64_t{1} << UsedBits) - 1U;
+}
+
+[[nodiscard]] std::size_t significantWordCount(std::span<const std::uint64_t> Words) noexcept {
+ std::size_t Count = Words.size();
+ while (Count != 0 && Words[Count - 1U] == 0)
+ --Count;
+ return Count;
+}
+
+[[nodiscard]] Expected<void> verifyAPInt(std::uint32_t BitWidth,
+ std::span<const std::uint64_t> Words, ErrorCode Code) {
+ if (BitWidth == 0 || BitWidth > APInt::MaxBitWidth)
+ return makeUnexpected(Code, "APInt bit width is outside the supported range");
+ if (Words.size() != wordCount(BitWidth))
+ return makeUnexpected(Code, "APInt bit pattern has the wrong word count");
+ if ((Words.back() & ~highWordMask(BitWidth)) != 0)
+ return makeUnexpected(Code, "APInt has nonzero bits above its declared width");
+ return {};
+}
+
+[[nodiscard]] bool isHexDigit(char Character) noexcept {
+ return (Character >= '0' && Character <= '9') || (Character >= 'a' && Character <= 'f') ||
+ (Character >= 'A' && Character <= 'F');
+}
+
+[[nodiscard]] unsigned hexDigitValue(char Character) noexcept {
+ if (Character >= '0' && Character <= '9')
+ return static_cast<unsigned>(Character - '0');
+ if (Character >= 'a' && Character <= 'f')
+ return static_cast<unsigned>(Character - 'a') + 10U;
+ return static_cast<unsigned>(Character - 'A') + 10U;
+}
+
+void negateWords(std::vector<std::uint64_t> &Words, std::uint32_t BitWidth) {
+ for (std::uint64_t &Word : Words)
+ Word = ~Word;
+ std::uint64_t Carry = 1;
+ for (std::uint64_t &Word : Words) {
+ const std::uint64_t Previous = Word;
+ Word += Carry;
+ Carry = Carry != 0 && Word < Previous ? 1U : 0U;
+ }
+ Words.back() &= highWordMask(BitWidth);
+}
+
+[[nodiscard]] std::string unsignedDecimal(std::vector<std::uint64_t> Words) {
+ if (std::ranges::all_of(Words, [](std::uint64_t Word) { return Word == 0; }))
+ return "0";
+ std::string Digits;
+ while (!std::ranges::all_of(Words, [](std::uint64_t Word) { return Word == 0; })) {
+ unsigned __int128 Remainder = 0;
+ for (auto Iterator = Words.rbegin(); Iterator != Words.rend(); ++Iterator) {
+ const unsigned __int128 Dividend = (Remainder << 64U) | *Iterator;
+ *Iterator = static_cast<std::uint64_t>(Dividend / 10U);
+ Remainder = Dividend % 10U;
+ }
+ Digits.push_back(static_cast<char>('0' + static_cast<unsigned>(Remainder)));
+ }
+ std::ranges::reverse(Digits);
+ return Digits;
+}
+
+} // namespace
+
+APInt::APInt(std::uint64_t Value) {
+ if (Value == 0)
+ return;
+ Words.push_back(Value);
+ BitWidth = static_cast<std::uint32_t>(std::bit_width(Value));
+}
+
+Expected<APInt> APInt::create(std::uint32_t BitWidth, std::span<const std::uint64_t> Words) {
+ auto Verification = verifyAPInt(BitWidth, Words, ErrorCode::InvalidArgument);
+ if (!Verification)
+ return std::unexpected(Verification.error());
+ return APInt(BitWidth, std::vector<std::uint64_t>(Words.begin(), Words.end()));
+}
+
+Expected<APInt> APInt::fromUnsigned(std::uint32_t BitWidth, std::uint64_t Value) {
+ if (BitWidth == 0 || BitWidth > MaxBitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt bit width is outside the supported range");
+ if (BitWidth < 64U && (Value >> BitWidth) != 0)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "unsigned value does not fit the APInt bit width");
+
+ std::vector<std::uint64_t> Words(wordCount(BitWidth), 0);
+ Words.front() = Value;
+ return create(BitWidth, Words);
+}
+
+Expected<APInt> APInt::fromSigned(std::uint32_t BitWidth, std::int64_t Value) {
+ if (BitWidth == 0 || BitWidth > MaxBitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt bit width is outside the supported range");
+ if (BitWidth < 64U) {
+ const std::uint32_t MagnitudeBits = BitWidth - 1U;
+ const std::int64_t Minimum = -(std::int64_t{1} << MagnitudeBits);
+ const std::int64_t Maximum = (std::int64_t{1} << MagnitudeBits) - 1;
+ if (Value < Minimum || Value > Maximum)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "signed value does not fit the APInt bit width");
+ }
+
+ const std::uint64_t Fill =
+ Value < 0 ? std::numeric_limits<std::uint64_t>::max() : std::uint64_t{0};
+ std::vector<std::uint64_t> Words(wordCount(BitWidth), Fill);
+ Words.front() = static_cast<std::uint64_t>(Value);
+ Words.back() &= highWordMask(BitWidth);
+ return create(BitWidth, Words);
+}
+
+Expected<APInt> APInt::getLowBitsSet(std::uint32_t BitWidth, std::uint32_t SetBitCount) {
+ if (BitWidth == 0 || BitWidth > MaxBitWidth || SetBitCount > BitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument, "APInt low-bit mask has an invalid width");
+ std::vector<std::uint64_t> Words(wordCount(BitWidth), 0);
+ const std::size_t FullWords = SetBitCount / 64U;
+ std::ranges::fill_n(Words.begin(),
+ static_cast<std::vector<std::uint64_t>::difference_type>(FullWords),
+ std::numeric_limits<std::uint64_t>::max());
+ const std::uint32_t RemainingBits = SetBitCount % 64U;
+ if (RemainingBits != 0)
+ Words[FullWords] = (std::uint64_t{1} << RemainingBits) - 1U;
+ return create(BitWidth, Words);
+}
+
+Expected<APInt> APInt::parseDecimal(std::uint32_t BitWidth, std::string_view Text) {
+ if (BitWidth == 0 || BitWidth > MaxBitWidth)
+ return makeUnexpected(ErrorCode::ParseError, "APInt bit width is outside the supported range");
+ const bool Negative = Text.starts_with('-');
+ if (Negative)
+ Text.remove_prefix(1);
+ if (Text.empty())
+ return makeUnexpected(ErrorCode::ParseError, "APInt has no decimal digits");
+
+ std::vector<std::uint64_t> Words(wordCount(BitWidth), 0);
+ for (const char Character : Text) {
+ if (Character < '0' || Character > '9')
+ return makeUnexpected(ErrorCode::ParseError, "APInt contains a non-decimal digit");
+ std::uint64_t Carry = static_cast<unsigned>(Character - '0');
+ for (std::uint64_t &Word : Words) {
+ const unsigned __int128 Product = static_cast<unsigned __int128>(Word) * 10U + Carry;
+ Word = static_cast<std::uint64_t>(Product);
+ Carry = static_cast<std::uint64_t>(Product >> 64U);
+ }
+ }
+
+ Words.back() &= highWordMask(BitWidth);
+ if (Negative)
+ negateWords(Words, BitWidth);
+ return create(BitWidth, Words);
+}
+
+Expected<APInt> APInt::parseLLVMHex(std::uint32_t BitWidth, std::string_view Text) {
+ if (Text.size() < 4 || (Text[0] != 'u' && Text[0] != 's') || Text[1] != '0' || Text[2] != 'x') {
+ return makeUnexpected(ErrorCode::ParseError,
+ "integer hexadecimal spelling must use u0x or s0x");
+ }
+ const std::string_view Digits = Text.substr(3);
+ if (Digits.empty() || !std::ranges::all_of(Digits, isHexDigit)) {
+ return makeUnexpected(ErrorCode::ParseError,
+ "integer hexadecimal spelling contains a non-hexadecimal digit");
+ }
+
+ const auto *const FirstNonZero =
+ std::ranges::find_if(Digits, [](char Character) { return hexDigitValue(Character) != 0; });
+ std::size_t ActiveBits = 0;
+ if (FirstNonZero != Digits.end()) {
+ const unsigned MostSignificantNibble = hexDigitValue(*FirstNonZero);
+ const auto MostSignificantBits = static_cast<unsigned>(std::bit_width(MostSignificantNibble));
+ ActiveBits =
+ static_cast<std::size_t>(Digits.end() - FirstNonZero - 1U) * 4U + MostSignificantBits;
+ }
+
+ if (BitWidth == 0 || BitWidth > MaxBitWidth)
+ return makeUnexpected(ErrorCode::ParseError, "APInt bit width is outside the supported range");
+ std::vector<std::uint64_t> Words(wordCount(BitWidth), 0);
+ std::size_t Nibble = 0;
+ for (auto Iterator = Digits.rbegin(); Iterator != Digits.rend(); ++Iterator, ++Nibble) {
+ const std::size_t BitOffset = Nibble * 4U;
+ if (BitOffset >= BitWidth)
+ break;
+ Words[BitOffset / 64U] |= static_cast<std::uint64_t>(hexDigitValue(*Iterator))
+ << (BitOffset % 64U);
+ }
+
+ if (Text[0] == 's' && ActiveBits != 0 && ActiveBits < BitWidth) {
+ const std::size_t FirstWord = ActiveBits / 64U;
+ const unsigned FirstBit = static_cast<unsigned>(ActiveBits % 64U);
+ Words[FirstWord] |= std::numeric_limits<std::uint64_t>::max() << FirstBit;
+ for (std::size_t Index = FirstWord + 1U; Index < Words.size(); ++Index)
+ Words[Index] = std::numeric_limits<std::uint64_t>::max();
+ }
+ Words.back() &= highWordMask(BitWidth);
+ return create(BitWidth, Words);
+}
+
+bool APInt::isZero() const noexcept {
+ return std::ranges::all_of(Words, [](std::uint64_t Word) { return Word == 0; });
+}
+
+bool APInt::isNegative() const noexcept {
+ if (BitWidth == 0 || Words.empty())
+ return false;
+ const std::uint32_t SignBit = BitWidth - 1U;
+ return (Words[SignBit / 64U] & (std::uint64_t{1} << (SignBit % 64U))) != 0;
+}
+
+std::size_t APInt::activeBitWidth() const noexcept {
+ const std::size_t Count = significantWordCount(Words);
+ if (Count == 0)
+ return 0;
+ return (Count - 1U) * 64U + static_cast<std::size_t>(std::bit_width(Words[Count - 1U]));
+}
+
+std::size_t APInt::countrZero() const noexcept {
+ std::size_t Result = 0;
+ for (const std::uint64_t Word : Words) {
+ if (Word == 0) {
+ Result += 64U;
+ continue;
+ }
+ return Result + static_cast<std::size_t>(std::countr_zero(Word));
+ }
+ return Result;
+}
+
+std::size_t APInt::countlOne() const noexcept {
+ std::size_t Result = 0;
+ for (std::size_t Bit = BitWidth; Bit != 0 && testBit(Bit - 1U); --Bit)
+ ++Result;
+ return Result;
+}
+
+bool APInt::isAllOnes() const noexcept {
+ return BitWidth != 0 && countlOne() == BitWidth;
+}
+
+bool APInt::testBit(std::size_t Bit) const noexcept {
+ return Bit < BitWidth && (Words[Bit / 64U] & (std::uint64_t{1} << (Bit % 64U))) != 0;
+}
+
+std::uint64_t APInt::word(std::size_t Index) const noexcept {
+ return Index < Words.size() ? Words[Index] : 0;
+}
+
+Expected<APInt> APInt::bitwiseAnd(const APInt &Other) const {
+ if (BitWidth == 0 || BitWidth != Other.BitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt bitwise operands must have the same nonzero width");
+ std::vector<std::uint64_t> ResultWords(Words.size(), 0);
+ for (std::size_t Index = 0; Index != Words.size(); ++Index)
+ ResultWords[Index] = Words[Index] & Other.Words[Index];
+ return create(BitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::bitwiseOr(const APInt &Other) const {
+ if (BitWidth == 0 || BitWidth != Other.BitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt bitwise operands must have the same nonzero width");
+ std::vector<std::uint64_t> ResultWords(Words.size(), 0);
+ for (std::size_t Index = 0; Index != Words.size(); ++Index)
+ ResultWords[Index] = Words[Index] | Other.Words[Index];
+ return create(BitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::bitwiseXor(const APInt &Other) const {
+ if (BitWidth == 0 || BitWidth != Other.BitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt bitwise operands must have the same nonzero width");
+ std::vector<std::uint64_t> ResultWords(Words.size(), 0);
+ for (std::size_t Index = 0; Index != Words.size(); ++Index)
+ ResultWords[Index] = Words[Index] ^ Other.Words[Index];
+ return create(BitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::bitwiseNot() const {
+ if (BitWidth == 0)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt bitwise complement requires a nonzero width");
+ std::vector<std::uint64_t> ResultWords(Words.size(), 0);
+ for (std::size_t Index = 0; Index != Words.size(); ++Index)
+ ResultWords[Index] = ~Words[Index];
+ ResultWords.back() &= highWordMask(BitWidth);
+ return create(BitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::trunc(std::uint32_t NewBitWidth) const {
+ if (NewBitWidth == 0 || NewBitWidth >= BitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt truncation requires a smaller nonzero width");
+ std::vector<std::uint64_t> ResultWords(wordCount(NewBitWidth), 0);
+ std::ranges::copy_n(Words.begin(),
+ static_cast<std::vector<std::uint64_t>::difference_type>(ResultWords.size()),
+ ResultWords.begin());
+ ResultWords.back() &= highWordMask(NewBitWidth);
+ return create(NewBitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::zext(std::uint32_t NewBitWidth) const {
+ if (NewBitWidth <= BitWidth || NewBitWidth > MaxBitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt zero extension requires a larger supported width");
+ std::vector<std::uint64_t> ResultWords(wordCount(NewBitWidth), 0);
+ std::ranges::copy(Words, ResultWords.begin());
+ return create(NewBitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::sext(std::uint32_t NewBitWidth) const {
+ if (NewBitWidth <= BitWidth || NewBitWidth > MaxBitWidth)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt sign extension requires a larger supported width");
+ std::vector<std::uint64_t> ResultWords(wordCount(NewBitWidth),
+ isNegative() ? std::numeric_limits<std::uint64_t>::max()
+ : std::uint64_t{0});
+ std::ranges::copy(Words, ResultWords.begin());
+ if (isNegative() && BitWidth % 64U != 0)
+ ResultWords[wordCount(BitWidth) - 1U] |= ~highWordMask(BitWidth);
+ ResultWords.back() &= highWordMask(NewBitWidth);
+ return create(NewBitWidth, ResultWords);
+}
+
+Expected<APInt> APInt::logicalShiftRight(std::size_t Amount) const {
+ if (BitWidth == 0)
+ return makeUnexpected(ErrorCode::InvalidArgument,
+ "APInt logical shift requires a nonzero width");
+ std::vector<std::uint64_t> ResultWords(wordCount(BitWidth), 0);
+ if (Amount >= BitWidth)
+ return create(BitWidth, ResultWords);
+
+ const std::size_t WordOffset = Amount / 64U;
+ const unsigned BitOffset = static_cast<unsigned>(Amount % 64U);
+ for (std::size_t Index = 0; Index + WordOffset < Words.size(); ++Index) {
+ std::uint64_t Value = Words[Index + WordOffset] >> BitOffset;
+ if (BitOffset != 0 && Index + WordOffset + 1U < Words.size())
+ Value |= Words[Index + WordOffset + 1U] << (64U - BitOffset);
+ ResultWords[Index] = Value;
+ }
+ ResultWords.back() &= highWordMask(BitWidth);
+ return create(BitWidth, ResultWords);
+}
+
+int APInt::compare(const APInt &Other) const noexcept {
+ const std::size_t LeftCount = significantWordCount(Words);
+ const std::size_t RightCount = significantWordCount(Other.Words);
+ if (LeftCount != RightCount)
+ return LeftCount < RightCount ? -1 : 1;
+ for (std::size_t Index = LeftCount; Index != 0; --Index) {
+ if (Words[Index - 1U] != Other.Words[Index - 1U])
+ return Words[Index - 1U] < Other.Words[Index - 1U] ? -1 : 1;
+ }
+ return 0;
+}
+
+int APInt::compareToShifted(const APInt &Other, std::size_t OtherShift) const noexcept {
+ if (Other.isZero())
+ return isZero() ? 0 : 1;
+ if (isZero())
+ return -1;
+ const std::size_t LeftBits = activeBitWidth();
+ const std::size_t RightBits = Other.activeBitWidth();
+ if (OtherShift > std::numeric_limits<std::size_t>::max() - RightBits)
+ return -1;
+ const std::size_t ShiftedBits = RightBits + OtherShift;
+ if (LeftBits != ShiftedBits)
+ return LeftBits < ShiftedBits ? -1 : 1;
+ return compare(Other.shiftedLeft(OtherShift));
+}
+
+void APInt::multiplySmall(std::uint32_t Multiplier) {
+ if (Multiplier == 0 || isZero()) {
+ Words.clear();
+ BitWidth = 0;
+ return;
+ }
+ unsigned __int128 Carry = 0;
+ for (std::uint64_t &Word : Words) {
+ const unsigned __int128 Product = static_cast<unsigned __int128>(Word) * Multiplier + Carry;
+ Word = static_cast<std::uint64_t>(Product);
+ Carry = Product >> 64U;
+ }
+ if (Carry != 0)
+ Words.push_back(static_cast<std::uint64_t>(Carry));
+ normalizeMagnitude();
+}
+
+void APInt::addSmall(std::uint32_t Value) {
+ unsigned __int128 Carry = Value;
+ std::size_t Index = 0;
+ while (Carry != 0 && Index < Words.size()) {
+ const unsigned __int128 Sum = static_cast<unsigned __int128>(Words[Index]) + Carry;
+ Words[Index] = static_cast<std::uint64_t>(Sum);
+ Carry = Sum >> 64U;
+ ++Index;
+ }
+ if (Carry != 0)
+ Words.push_back(static_cast<std::uint64_t>(Carry));
+ normalizeMagnitude();
+}
+
+void APInt::setBit(std::size_t Bit) {
+ const std::size_t Index = Bit / 64U;
+ if (Index >= Words.size())
+ Words.resize(Index + 1U, 0);
+ Words[Index] |= std::uint64_t{1} << (Bit % 64U);
+ normalizeMagnitude();
+}
+
+void APInt::clearBit(std::size_t Bit) noexcept {
+ const std::size_t Index = Bit / 64U;
+ if (Index >= Words.size())
+ return;
+ Words[Index] &= ~(std::uint64_t{1} << (Bit % 64U));
+ normalizeMagnitude();
+}
+
+void APInt::shiftRight(std::size_t Amount) noexcept {
+ if (Amount == 0 || isZero())
+ return;
+ const std::size_t WordOffset = Amount / 64U;
+ if (WordOffset >= Words.size()) {
+ Words.clear();
+ BitWidth = 0;
+ return;
+ }
+ const unsigned BitOffset = static_cast<unsigned>(Amount % 64U);
+ const std::size_t NewSize = Words.size() - WordOffset;
+ for (std::size_t Index = 0; Index < NewSize; ++Index) {
+ std::uint64_t Value = Words[Index + WordOffset] >> BitOffset;
+ if (BitOffset != 0 && Index + WordOffset + 1U < Words.size())
+ Value |= Words[Index + WordOffset + 1U] << (64U - BitOffset);
+ Words[Index] = Value;
+ }
+ Words.resize(NewSize);
+ normalizeMagnitude();
+}
+
+APInt APInt::shiftedLeft(std::size_t Amount) const {
+ if (isZero() || Amount == 0)
+ return *this;
+ const std::size_t WordOffset = Amount / 64U;
+ const unsigned BitOffset = static_cast<unsigned>(Amount % 64U);
+ APInt Result;
+ Result.Words.assign(Words.size() + WordOffset + (BitOffset == 0 ? 0U : 1U), 0);
+ for (std::size_t Index = 0; Index < Words.size(); ++Index) {
+ const unsigned __int128 Shifted = static_cast<unsigned __int128>(Words[Index]) << BitOffset;
+ Result.Words[Index + WordOffset] |= static_cast<std::uint64_t>(Shifted);
+ if (BitOffset != 0)
+ Result.Words[Index + WordOffset + 1U] |= static_cast<std::uint64_t>(Shifted >> 64U);
+ }
+ Result.normalizeMagnitude();
+ return Result;
+}
+
+void APInt::subtract(const APInt &Other) noexcept {
+ std::uint64_t Borrow = 0;
+ for (std::size_t Index = 0; Index < Words.size(); ++Index) {
+ const unsigned __int128 Subtrahend =
+ (Index < Other.Words.size() ? static_cast<unsigned __int128>(Other.Words[Index]) : 0) +
+ Borrow;
+ const unsigned __int128 Current = Words[Index];
+ Words[Index] = static_cast<std::uint64_t>(Current - Subtrahend);
+ Borrow = Current < Subtrahend ? 1U : 0U;
+ }
+ normalizeMagnitude();
+}
+
+std::string APInt::toUnsignedDecimal() const {
+ return unsignedDecimal(Words);
+}
+
+std::string APInt::toSignedDecimal() const {
+ if (!isNegative())
+ return toUnsignedDecimal();
+
+ std::vector<std::uint64_t> Magnitude = Words;
+ negateWords(Magnitude, BitWidth);
+ return "-" + unsignedDecimal(std::move(Magnitude));
+}
+
+Expected<void> APInt::verify() const {
+ return verifyAPInt(BitWidth, Words, ErrorCode::VerificationError);
+}
+
+void APInt::normalizeMagnitude() noexcept {
+ while (!Words.empty() && Words.back() == 0)
+ Words.pop_back();
+ const std::size_t ActiveBits = activeBitWidth();
+ BitWidth = static_cast<std::uint32_t>(ActiveBits);
+}
+
+} // namespace rcc
diff --git a/backend/lib/Support/CMakeLists.txt b/backend/lib/Support/CMakeLists.txt
new file mode 100644
index 0000000..9a9fc53
--- /dev/null
+++ b/backend/lib/Support/CMakeLists.txt
@@ -0,0 +1,49 @@
+# SPDX-License-Identifier: GPL-3.0-or-later
+
+set(RCCBackendSupportSources APFloat.cpp APInt.cpp Error.cpp SHA256.cpp TextDiagnostic.cpp YAML.cpp)
+set(
+ RCCBackendSupportHeaders
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/ADT/APFloat.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/ADT/APInt.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Support/Error.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Support/SHA256.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Support/TextDiagnostic.h"
+ "${RCC_BACKEND_SOURCE_DIR}/include/rcc/Support/YAML.h"
+)
+
+add_library(RCCBackendSupport ${RCCBackendSupportSources})
+add_library(RCCBackend::Support ALIAS RCCBackendSupport)
+
+rcc_backend_configure_target(RCCBackendSupport)
+
+target_include_directories(
+ RCCBackendSupport
+ PUBLIC
+ "$<BUILD_INTERFACE:${RCC_BACKEND_SOURCE_DIR}/include>"
+ "$<INSTALL_INTERFACE:${CMAKE_INSTALL_INCLUDEDIR}>"
+)
+
+set_target_properties(
+ RCCBackendSupport
+ PROPERTIES
+ EXPORT_NAME Support
+ OUTPUT_NAME RCCBackendSupport
+)
+
+install(
+ TARGETS RCCBackendSupport
+ EXPORT RCCBackendTargets
+ ARCHIVE DESTINATION "${CMAKE_INSTALL_LIBDIR}"
+ LIBRARY DESTINATION "${CMAKE_INSTALL_LIBDIR}"
+ RUNTIME DESTINATION "${CMAKE_INSTALL_BINDIR}"
+)
+
+rcc_backend_register_format_files(
+ "${CMAKE_CURRENT_SOURCE_DIR}/APFloat.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/APInt.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/Error.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/SHA256.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/TextDiagnostic.cpp"
+ "${CMAKE_CURRENT_SOURCE_DIR}/YAML.cpp"
+ ${RCCBackendSupportHeaders}
+)
diff --git a/backend/lib/Support/Error.cpp b/backend/lib/Support/Error.cpp
new file mode 100644
index 0000000..d4793b5
--- /dev/null
+++ b/backend/lib/Support/Error.cpp
@@ -0,0 +1,69 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Support/Error.h"
+
+namespace rcc {
+
+std::string_view getErrorCodeName(ErrorCode Code) noexcept {
+ switch (Code) {
+ case ErrorCode::InvalidArgument:
+ return "invalid argument";
+ case ErrorCode::ParseError:
+ return "parse error";
+ case ErrorCode::VerificationError:
+ return "verification error";
+ case ErrorCode::Unsupported:
+ return "unsupported";
+ case ErrorCode::RegisterAllocationFailed:
+ return "register allocation failed";
+ case ErrorCode::FrameLayoutFailed:
+ return "frame layout failed";
+ case ErrorCode::SchedulingFailed:
+ return "scheduling failed";
+ case ErrorCode::BranchRelaxationFailed:
+ return "branch relaxation failed";
+ case ErrorCode::PseudoExpansionFailed:
+ return "pseudo expansion failed";
+ case ErrorCode::FinalEncodabilityFailed:
+ return "final encodability failed";
+ case ErrorCode::CFGOptimizationFailed:
+ return "CFG optimization failed";
+ case ErrorCode::AssemblyLoweringFailed:
+ return "assembly lowering failed";
+ case ErrorCode::InstructionEncodingFailed:
+ return "instruction encoding failed";
+ case ErrorCode::FixupApplicationFailed:
+ return "fixup application failed";
+ case ErrorCode::RelocationFailed:
+ return "relocation failed";
+ case ErrorCode::ObjectWritingFailed:
+ return "object writing failed";
+ case ErrorCode::InvalidInvocation:
+ return "invalid backend invocation";
+ case ErrorCode::ManifestError:
+ return "manifest error";
+ case ErrorCode::CacheMiss:
+ return "cache miss";
+ case ErrorCode::ReproducerError:
+ return "reproducer error";
+ case ErrorCode::ReductionFailed:
+ return "reduction failed";
+ case ErrorCode::FuzzingFailure:
+ return "fuzzing failure";
+ case ErrorCode::IoError:
+ return "I/O error";
+ case ErrorCode::InternalError:
+ return "internal error";
+ }
+
+ return "unknown error";
+}
+
+Error::Error(ErrorCode Code, std::string Message) : Code(Code), Message(std::move(Message)) {}
+
+Error withErrorContext(const Error &Failure, std::string Context) {
+ Context.append(Failure.message());
+ return Error(Failure.code(), std::move(Context));
+}
+
+} // namespace rcc
diff --git a/backend/lib/Support/SHA256.cpp b/backend/lib/Support/SHA256.cpp
new file mode 100644
index 0000000..8825f89
--- /dev/null
+++ b/backend/lib/Support/SHA256.cpp
@@ -0,0 +1,149 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Support/SHA256.h"
+
+#include <array>
+#include <bit>
+#include <cstddef>
+#include <cstdint>
+#include <span>
+#include <string>
+#include <string_view>
+#include <vector>
+
+namespace rcc {
+namespace {
+
+constexpr std::array<std::uint32_t, 64> RoundConstants{
+ 0x428a2f98U, 0x71374491U, 0xb5c0fbcfU, 0xe9b5dba5U, 0x3956c25bU, 0x59f111f1U, 0x923f82a4U,
+ 0xab1c5ed5U, 0xd807aa98U, 0x12835b01U, 0x243185beU, 0x550c7dc3U, 0x72be5d74U, 0x80deb1feU,
+ 0x9bdc06a7U, 0xc19bf174U, 0xe49b69c1U, 0xefbe4786U, 0x0fc19dc6U, 0x240ca1ccU, 0x2de92c6fU,
+ 0x4a7484aaU, 0x5cb0a9dcU, 0x76f988daU, 0x983e5152U, 0xa831c66dU, 0xb00327c8U, 0xbf597fc7U,
+ 0xc6e00bf3U, 0xd5a79147U, 0x06ca6351U, 0x14292967U, 0x27b70a85U, 0x2e1b2138U, 0x4d2c6dfcU,
+ 0x53380d13U, 0x650a7354U, 0x766a0abbU, 0x81c2c92eU, 0x92722c85U, 0xa2bfe8a1U, 0xa81a664bU,
+ 0xc24b8b70U, 0xc76c51a3U, 0xd192e819U, 0xd6990624U, 0xf40e3585U, 0x106aa070U, 0x19a4c116U,
+ 0x1e376c08U, 0x2748774cU, 0x34b0bcb5U, 0x391c0cb3U, 0x4ed8aa4aU, 0x5b9cca4fU, 0x682e6ff3U,
+ 0x748f82eeU, 0x78a5636fU, 0x84c87814U, 0x8cc70208U, 0x90befffaU, 0xa4506cebU, 0xbef9a3f7U,
+ 0xc67178f2U,
+};
+
+constexpr std::array<std::uint32_t, 8> InitialState{
+ 0x6a09e667U, 0xbb67ae85U, 0x3c6ef372U, 0xa54ff53aU,
+ 0x510e527fU, 0x9b05688cU, 0x1f83d9abU, 0x5be0cd19U,
+};
+
+[[nodiscard]] std::uint32_t loadBigEndian(const std::uint8_t *Input) noexcept {
+ return (static_cast<std::uint32_t>(Input[0]) << 24U) |
+ (static_cast<std::uint32_t>(Input[1]) << 16U) |
+ (static_cast<std::uint32_t>(Input[2]) << 8U) | static_cast<std::uint32_t>(Input[3]);
+}
+
+void storeBigEndian(std::uint32_t Value, std::uint8_t *Output) noexcept {
+ Output[0] = static_cast<std::uint8_t>(Value >> 24U);
+ Output[1] = static_cast<std::uint8_t>(Value >> 16U);
+ Output[2] = static_cast<std::uint8_t>(Value >> 8U);
+ Output[3] = static_cast<std::uint8_t>(Value);
+}
+
+void compress(std::array<std::uint32_t, 8> &State, const std::uint8_t *Block) noexcept {
+ std::array<std::uint32_t, 64> Words{};
+ for (std::size_t Index = 0; Index < 16; ++Index)
+ Words[Index] = loadBigEndian(Block + Index * 4U);
+ for (std::size_t Index = 16; Index < Words.size(); ++Index) {
+ const std::uint32_t S0 = std::rotr(Words[Index - 15], 7) ^ std::rotr(Words[Index - 15], 18) ^
+ (Words[Index - 15] >> 3U);
+ const std::uint32_t S1 = std::rotr(Words[Index - 2], 17) ^ std::rotr(Words[Index - 2], 19) ^
+ (Words[Index - 2] >> 10U);
+ Words[Index] = Words[Index - 16] + S0 + Words[Index - 7] + S1;
+ }
+
+ std::uint32_t A = State[0];
+ std::uint32_t B = State[1];
+ std::uint32_t C = State[2];
+ std::uint32_t D = State[3];
+ std::uint32_t E = State[4];
+ std::uint32_t F = State[5];
+ std::uint32_t G = State[6];
+ std::uint32_t H = State[7];
+ for (std::size_t Index = 0; Index < Words.size(); ++Index) {
+ const std::uint32_t Sum1 = std::rotr(E, 6) ^ std::rotr(E, 11) ^ std::rotr(E, 25);
+ const std::uint32_t Choice = (E & F) ^ (~E & G);
+ const std::uint32_t Temporary1 = H + Sum1 + Choice + RoundConstants[Index] + Words[Index];
+ const std::uint32_t Sum0 = std::rotr(A, 2) ^ std::rotr(A, 13) ^ std::rotr(A, 22);
+ const std::uint32_t Majority = (A & B) ^ (A & C) ^ (B & C);
+ const std::uint32_t Temporary2 = Sum0 + Majority;
+ H = G;
+ G = F;
+ F = E;
+ E = D + Temporary1;
+ D = C;
+ C = B;
+ B = A;
+ A = Temporary1 + Temporary2;
+ }
+ State[0] += A;
+ State[1] += B;
+ State[2] += C;
+ State[3] += D;
+ State[4] += E;
+ State[5] += F;
+ State[6] += G;
+ State[7] += H;
+}
+
+[[nodiscard]] std::string toHex(const SHA256Digest &Digest) {
+ constexpr std::string_view Digits = "0123456789abcdef";
+ std::string Result;
+ Result.resize(Digest.size() * 2U);
+ for (std::size_t Index = 0; Index < Digest.size(); ++Index) {
+ Result[Index * 2U] = Digits[Digest[Index] >> 4U];
+ Result[Index * 2U + 1U] = Digits[Digest[Index] & 0x0fU];
+ }
+ return Result;
+}
+
+} // namespace
+
+SHA256Digest sha256(std::span<const std::byte> Input) {
+ const auto *Bytes = reinterpret_cast<const std::uint8_t *>(Input.data());
+ std::array<std::uint32_t, 8> State = InitialState;
+ std::size_t Offset = 0;
+ while (Input.size() - Offset >= 64U) {
+ compress(State, Bytes + Offset);
+ Offset += 64U;
+ }
+
+ std::vector<std::uint8_t> Tail;
+ Tail.reserve(128);
+ Tail.insert(Tail.end(), Bytes + Offset, Bytes + Input.size());
+ Tail.push_back(0x80U);
+ while ((Tail.size() + 8U) % 64U != 0)
+ Tail.push_back(0);
+ const std::uint64_t BitLength = static_cast<std::uint64_t>(Input.size()) * 8U;
+ for (unsigned Byte = 0; Byte < 8; ++Byte) {
+ const unsigned Shift = 56U - Byte * 8U;
+ Tail.push_back(static_cast<std::uint8_t>(BitLength >> Shift));
+ }
+ for (std::size_t Index = 0; Index < Tail.size(); Index += 64U)
+ compress(State, Tail.data() + Index);
+
+ SHA256Digest Result{};
+ for (std::size_t Index = 0; Index < State.size(); ++Index)
+ storeBigEndian(State[Index], Result.data() + Index * 4U);
+ return Result;
+}
+
+SHA256Digest sha256(std::string_view Input) {
+ const auto *Bytes = reinterpret_cast<const std::byte *>(Input.data());
+ return sha256(std::span<const std::byte>(Bytes, Input.size()));
+}
+
+std::string sha256Hex(std::span<const std::byte> Input) {
+ return toHex(sha256(Input));
+}
+
+std::string sha256Hex(std::string_view Input) {
+ return toHex(sha256(Input));
+}
+
+} // namespace rcc
diff --git a/backend/lib/Support/TextDiagnostic.cpp b/backend/lib/Support/TextDiagnostic.cpp
new file mode 100644
index 0000000..e4c2dec
--- /dev/null
+++ b/backend/lib/Support/TextDiagnostic.cpp
@@ -0,0 +1,88 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Support/TextDiagnostic.h"
+
+#include <algorithm>
+#include <iterator>
+#include <sstream>
+#include <utility>
+
+namespace rcc {
+
+std::string_view getDiagnosticSeverityName(DiagnosticSeverity Severity) noexcept {
+ switch (Severity) {
+ case DiagnosticSeverity::Note:
+ return "note";
+ case DiagnosticSeverity::Warning:
+ return "warning";
+ case DiagnosticSeverity::Error:
+ return "error";
+ }
+
+ return "unknown";
+}
+
+TextSource::TextSource(std::string Name, std::string Text)
+ : Name(std::move(Name)), Text(std::move(Text)), LineOffsets{0} {
+ for (std::size_t Index = 0; Index < this->Text.size(); ++Index) {
+ if (this->Text[Index] == '\n')
+ LineOffsets.push_back(Index + 1);
+ }
+}
+
+TextPosition TextSource::positionAt(std::size_t Offset) const noexcept {
+ Offset = std::min(Offset, Text.size());
+ const auto LineIterator = std::upper_bound(LineOffsets.begin(), LineOffsets.end(), Offset);
+ const std::size_t LineIndex =
+ static_cast<std::size_t>(std::distance(LineOffsets.begin(), LineIterator) - 1);
+ return TextPosition{
+ .Offset = Offset,
+ .Line = LineIndex + 1,
+ .Column = Offset - LineOffsets[LineIndex] + 1,
+ };
+}
+
+TextRange TextSource::range(std::size_t Begin, std::size_t End) const noexcept {
+ Begin = std::min(Begin, Text.size());
+ End = std::clamp(End, Begin, Text.size());
+ return TextRange{.Begin = positionAt(Begin), .End = positionAt(End)};
+}
+
+std::string_view TextSource::line(std::size_t OneBasedLine) const noexcept {
+ if (OneBasedLine == 0 || OneBasedLine > LineOffsets.size())
+ return {};
+
+ const std::size_t Begin = LineOffsets[OneBasedLine - 1];
+ std::size_t End = OneBasedLine < LineOffsets.size() ? LineOffsets[OneBasedLine] - 1 : Text.size();
+ if (End > Begin && Text[End - 1] == '\r')
+ --End;
+ return std::string_view(Text).substr(Begin, End - Begin);
+}
+
+std::string formatTextDiagnostic(const TextDiagnostic &Diagnostic, const TextSource &Source) {
+ std::ostringstream Output;
+ const TextPosition Position = Diagnostic.Range.Begin;
+ const std::string_view SourceName =
+ Diagnostic.SourceName.empty() ? Source.name() : std::string_view(Diagnostic.SourceName);
+
+ Output << getDiagnosticSeverityName(Diagnostic.Severity) << ": " << SourceName << ':'
+ << Position.Line << ':' << Position.Column << ": " << Diagnostic.Message;
+
+ const std::string_view SourceLine = Source.line(Position.Line);
+ if (SourceLine.empty())
+ return Output.str();
+
+ Output << '\n' << SourceLine << '\n';
+ const std::size_t PrefixWidth = Position.Column > 0 ? Position.Column - 1 : 0;
+ for (std::size_t Index = 0; Index < PrefixWidth && Index < SourceLine.size(); ++Index)
+ Output << (SourceLine[Index] == '\t' ? '\t' : ' ');
+
+ Output << '^';
+ if (Diagnostic.Range.End.Line == Position.Line &&
+ Diagnostic.Range.End.Column > Position.Column + 1) {
+ Output << std::string(Diagnostic.Range.End.Column - Position.Column - 1, '~');
+ }
+ return Output.str();
+}
+
+} // namespace rcc
diff --git a/backend/lib/Support/YAML.cpp b/backend/lib/Support/YAML.cpp
new file mode 100644
index 0000000..1ee7131
--- /dev/null
+++ b/backend/lib/Support/YAML.cpp
@@ -0,0 +1,1247 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "rcc/Support/YAML.h"
+
+#include <algorithm>
+#include <limits>
+#include <optional>
+#include <string>
+#include <string_view>
+#include <utility>
+
+namespace rcc::yaml {
+namespace {
+
+struct PhysicalLine final {
+ std::size_t Begin = 0;
+ std::size_t ContentEnd = 0;
+ std::size_t End = 0;
+ std::size_t Indent = 0;
+ bool HasIndentTab = false;
+ bool IsBlank = true;
+};
+
+enum class DocumentMarker : std::uint8_t {
+ None,
+ Start,
+ End,
+};
+
+[[nodiscard]] bool isAsciiSpace(char Character) noexcept {
+ return Character == ' ' || Character == '\t';
+}
+
+[[nodiscard]] bool isHexDigit(char Character) noexcept {
+ return (Character >= '0' && Character <= '9') || (Character >= 'a' && Character <= 'f') ||
+ (Character >= 'A' && Character <= 'F');
+}
+
+[[nodiscard]] unsigned hexValue(char Character) noexcept {
+ if (Character >= '0' && Character <= '9')
+ return static_cast<unsigned>(Character - '0');
+ if (Character >= 'a' && Character <= 'f')
+ return static_cast<unsigned>(Character - 'a') + 10U;
+ return static_cast<unsigned>(Character - 'A') + 10U;
+}
+
+[[nodiscard]] bool isNullSpelling(std::string_view Value) noexcept {
+ return Value == "~" || Value == "null" || Value == "Null" || Value == "NULL";
+}
+
+void appendUTF8(std::string &Output, std::uint32_t CodePoint) {
+ if (CodePoint <= 0x7FU) {
+ Output.push_back(static_cast<char>(CodePoint));
+ return;
+ }
+ if (CodePoint <= 0x7FFU) {
+ Output.push_back(static_cast<char>(0xC0U | (CodePoint >> 6U)));
+ Output.push_back(static_cast<char>(0x80U | (CodePoint & 0x3FU)));
+ return;
+ }
+ if (CodePoint <= 0xFFFFU) {
+ Output.push_back(static_cast<char>(0xE0U | (CodePoint >> 12U)));
+ Output.push_back(static_cast<char>(0x80U | ((CodePoint >> 6U) & 0x3FU)));
+ Output.push_back(static_cast<char>(0x80U | (CodePoint & 0x3FU)));
+ return;
+ }
+ Output.push_back(static_cast<char>(0xF0U | (CodePoint >> 18U)));
+ Output.push_back(static_cast<char>(0x80U | ((CodePoint >> 12U) & 0x3FU)));
+ Output.push_back(static_cast<char>(0x80U | ((CodePoint >> 6U) & 0x3FU)));
+ Output.push_back(static_cast<char>(0x80U | (CodePoint & 0x3FU)));
+}
+
+} // namespace
+
+std::optional<NodeID> Node::mappingValue(std::string_view Key) const noexcept {
+ if (Kind != NodeKind::Mapping)
+ return std::nullopt;
+ const auto Iterator = std::find_if(Mapping.begin(), Mapping.end(),
+ [Key](const MappingEntry &Entry) { return Entry.Key == Key; });
+ if (Iterator == Mapping.end())
+ return std::nullopt;
+ return Iterator->Value;
+}
+
+const Node *Stream::node(NodeID ID) const noexcept {
+ if (!ID.isValid() || ID.rawValue() >= Nodes.size())
+ return nullptr;
+ return &Nodes[ID.rawValue()];
+}
+
+class Parser final {
+public:
+ Parser(std::string SourceName, std::string SourceText, ParseOptions Options)
+ : Parsed(std::move(SourceName), std::move(SourceText)), Options(Options) {
+ buildLineTable();
+ }
+
+ [[nodiscard]] ParseResult run() {
+ if (Options.MaximumDepth == 0) {
+ diagnose(0, 0, "maximum YAML nesting depth must be greater than zero");
+ return failureResult();
+ }
+ if (Options.MaximumNodes == 0 ||
+ Options.MaximumNodes >= std::numeric_limits<std::uint32_t>::max()) {
+ diagnose(0, 0, "maximum YAML node count is outside the supported range");
+ return failureResult();
+ }
+ if (Parsed.Source.text().find('\0') != std::string_view::npos) {
+ const std::size_t Offset = Parsed.Source.text().find('\0');
+ diagnose(Offset, Offset + 1, "NUL bytes are not allowed in YAML input");
+ return failureResult();
+ }
+
+ std::size_t LineIndex = 0;
+ skipBlankLines(LineIndex, Lines.size());
+ while (LineIndex < Lines.size()) {
+ if (Lines[LineIndex].Indent == 0 && Parsed.Source.text()[Lines[LineIndex].Begin] == '%') {
+ diagnose(Lines[LineIndex].Begin, Lines[LineIndex].ContentEnd,
+ "YAML directives are not supported");
+ return failureResult();
+ }
+ if (markerAt(LineIndex) == DocumentMarker::End) {
+ const std::size_t EndRemainder = markerRemainder(LineIndex, 3);
+ if (EndRemainder < Lines[LineIndex].ContentEnd &&
+ Parsed.Source.text()[EndRemainder] != '#') {
+ diagnose(EndRemainder, Lines[LineIndex].ContentEnd,
+ "document end marker may only be followed by a comment");
+ return failureResult();
+ }
+ ++LineIndex;
+ skipBlankLines(LineIndex, Lines.size());
+ continue;
+ }
+
+ const std::size_t DocumentStartLine = LineIndex;
+ const bool HasExplicitStart = markerAt(LineIndex) == DocumentMarker::Start;
+ std::size_t InlineStart = Lines[LineIndex].ContentEnd;
+ if (HasExplicitStart)
+ InlineStart = markerRemainder(LineIndex, 3);
+
+ const std::size_t SearchStart = HasExplicitStart ? LineIndex + 1 : LineIndex;
+ const std::size_t LimitLine = findDocumentBoundary(SearchStart);
+ NodeID Root;
+ if (HasExplicitStart && InlineStart < Lines[LineIndex].ContentEnd &&
+ Parsed.Source.text()[InlineStart] != '#') {
+ if (Parsed.Source.text()[InlineStart] == '|' || Parsed.Source.text()[InlineStart] == '>') {
+ Root = parseBlockScalar(LineIndex, InlineStart, 0, 1, LimitLine);
+ } else {
+ Root = parseInlineValueOnLine(LineIndex, InlineStart, 1, LimitLine);
+ }
+ } else {
+ if (HasExplicitStart)
+ ++LineIndex;
+ skipBlankLines(LineIndex, LimitLine);
+ if (LineIndex == LimitLine) {
+ const std::size_t Offset = HasExplicitStart ? Lines[DocumentStartLine].ContentEnd
+ : Lines[DocumentStartLine].Begin;
+ Root = addNullNode(Offset, Offset);
+ } else {
+ Root = parseBlockNode(LineIndex, Lines[LineIndex].Indent, 1, LimitLine);
+ }
+ }
+
+ if (Failed)
+ return failureResult();
+
+ skipBlankLines(LineIndex, LimitLine);
+ if (LineIndex != LimitLine) {
+ diagnose(Lines[LineIndex].Begin + Lines[LineIndex].Indent, Lines[LineIndex].ContentEnd,
+ "unexpected content after YAML document root");
+ return failureResult();
+ }
+
+ bool HasExplicitEnd = false;
+ if (LimitLine < Lines.size() && markerAt(LimitLine) == DocumentMarker::End) {
+ const std::size_t EndRemainder = markerRemainder(LimitLine, 3);
+ if (EndRemainder < Lines[LimitLine].ContentEnd &&
+ Parsed.Source.text()[EndRemainder] != '#') {
+ diagnose(EndRemainder, Lines[LimitLine].ContentEnd,
+ "document end marker may only be followed by a comment");
+ return failureResult();
+ }
+ HasExplicitEnd = true;
+ LineIndex = LimitLine + 1;
+ } else {
+ LineIndex = LimitLine;
+ }
+
+ const std::size_t DocumentBegin = Lines[DocumentStartLine].Begin;
+ const std::size_t DocumentEnd = HasExplicitEnd
+ ? Lines[LimitLine].ContentEnd
+ : (LimitLine == 0 ? 0 : Lines[LimitLine - 1].End);
+ Parsed.Documents.push_back(Document{
+ .Root = Root,
+ .Range = Parsed.Source.range(DocumentBegin, DocumentEnd),
+ .HasExplicitStart = HasExplicitStart,
+ .HasExplicitEnd = HasExplicitEnd,
+ });
+
+ skipBlankLines(LineIndex, Lines.size());
+ }
+
+ ParseResult Result;
+ Result.ParsedStream.emplace(std::move(Parsed));
+ return Result;
+ }
+
+private:
+ void buildLineTable() {
+ const std::string_view Text = Parsed.Source.text();
+ std::size_t Begin = 0;
+ while (Begin <= Text.size()) {
+ const std::size_t Newline = Text.find('\n', Begin);
+ const std::size_t End = Newline == std::string_view::npos ? Text.size() : Newline + 1;
+ std::size_t ContentEnd = Newline == std::string_view::npos ? Text.size() : Newline;
+ if (ContentEnd > Begin && Text[ContentEnd - 1] == '\r')
+ --ContentEnd;
+
+ PhysicalLine Line{
+ .Begin = Begin,
+ .ContentEnd = ContentEnd,
+ .End = End,
+ };
+ std::size_t Cursor = Begin;
+ while (Cursor < ContentEnd && Text[Cursor] == ' ')
+ ++Cursor;
+ Line.Indent = Cursor - Begin;
+ std::size_t ContentCursor = Cursor;
+ while (ContentCursor < ContentEnd && isAsciiSpace(Text[ContentCursor])) {
+ if (Text[ContentCursor] == '\t')
+ Line.HasIndentTab = true;
+ ++ContentCursor;
+ }
+ Line.IsBlank = ContentCursor == ContentEnd || Text[ContentCursor] == '#';
+ Lines.push_back(Line);
+
+ if (Newline == std::string_view::npos)
+ break;
+ Begin = End;
+ }
+ }
+
+ [[nodiscard]] ParseResult failureResult() {
+ ParseResult Result;
+ Result.Diagnostics = std::move(Diagnostics);
+ return Result;
+ }
+
+ void diagnose(std::size_t Begin, std::size_t End, std::string Message,
+ std::string SourceName = {}) {
+ if (Failed)
+ return;
+ Failed = true;
+ Diagnostics.push_back(TextDiagnostic{
+ .Severity = DiagnosticSeverity::Error,
+ .Category = "yaml",
+ .Message = std::move(Message),
+ .SourceName =
+ SourceName.empty() ? std::string(Parsed.Source.name()) : std::move(SourceName),
+ .Range = Parsed.Source.range(Begin, End),
+ });
+ }
+
+ void skipBlankLines(std::size_t &LineIndex, std::size_t LimitLine) {
+ while (LineIndex < LimitLine && Lines[LineIndex].IsBlank)
+ ++LineIndex;
+ }
+
+ [[nodiscard]] DocumentMarker markerAt(std::size_t LineIndex) const noexcept {
+ if (LineIndex >= Lines.size())
+ return DocumentMarker::None;
+ const PhysicalLine &Line = Lines[LineIndex];
+ if (Line.Indent != 0 || Line.ContentEnd - Line.Begin < 3)
+ return DocumentMarker::None;
+
+ const std::string_view Text = Parsed.Source.text();
+ const std::string_view Prefix = Text.substr(Line.Begin, 3);
+ if (Prefix != "---" && Prefix != "...")
+ return DocumentMarker::None;
+ if (Line.Begin + 3 < Line.ContentEnd) {
+ const char Next = Text[Line.Begin + 3];
+ if (!isAsciiSpace(Next) && Next != '#')
+ return DocumentMarker::None;
+ }
+ return Prefix == "---" ? DocumentMarker::Start : DocumentMarker::End;
+ }
+
+ [[nodiscard]] std::size_t markerRemainder(std::size_t LineIndex,
+ std::size_t MarkerWidth) const noexcept {
+ const PhysicalLine &Line = Lines[LineIndex];
+ std::size_t Cursor = Line.Begin + MarkerWidth;
+ const std::string_view Text = Parsed.Source.text();
+ while (Cursor < Line.ContentEnd && isAsciiSpace(Text[Cursor]))
+ ++Cursor;
+ return Cursor;
+ }
+
+ [[nodiscard]] std::size_t findDocumentBoundary(std::size_t StartLine) const noexcept {
+ for (std::size_t LineIndex = StartLine; LineIndex < Lines.size(); ++LineIndex) {
+ if (markerAt(LineIndex) != DocumentMarker::None)
+ return LineIndex;
+ }
+ return Lines.size();
+ }
+
+ [[nodiscard]] bool validateIndent(std::size_t LineIndex) {
+ if (!Lines[LineIndex].HasIndentTab)
+ return true;
+ diagnose(Lines[LineIndex].Begin, Lines[LineIndex].Begin + Lines[LineIndex].Indent,
+ "tab characters are not allowed in YAML indentation");
+ return false;
+ }
+
+ [[nodiscard]] NodeID parseBlockNode(std::size_t &LineIndex, std::size_t Indent, std::size_t Depth,
+ std::size_t LimitLine) {
+ if (!checkDepth(Depth))
+ return {};
+ skipBlankLines(LineIndex, LimitLine);
+ if (LineIndex >= LimitLine) {
+ const std::size_t Offset =
+ LimitLine < Lines.size() ? Lines[LimitLine].Begin : Parsed.Source.text().size();
+ return addNullNode(Offset, Offset);
+ }
+ if (!validateIndent(LineIndex))
+ return {};
+ if (Lines[LineIndex].Indent != Indent) {
+ diagnose(Lines[LineIndex].Begin + Lines[LineIndex].Indent, Lines[LineIndex].ContentEnd,
+ "inconsistent YAML indentation");
+ return {};
+ }
+
+ const std::size_t ContentStart = Lines[LineIndex].Begin + Indent;
+ if (isUnrecognizedPlainStart(Parsed.Source.text()[ContentStart])) {
+ diagnose(ContentStart, ContentStart + 1, "Unrecognized character while tokenizing.", "YAML");
+ return {};
+ }
+ if (isSequenceIndicator(ContentStart, Lines[LineIndex].ContentEnd))
+ return parseBlockSequence(LineIndex, Indent, Depth, LimitLine);
+ if (findBlockMappingColon(ContentStart, Lines[LineIndex].ContentEnd))
+ return parseBlockMapping(LineIndex, Indent, Depth, LimitLine);
+
+ NodeID Result;
+ if (Parsed.Source.text()[ContentStart] == '|' || Parsed.Source.text()[ContentStart] == '>') {
+ Result = parseBlockScalar(LineIndex, ContentStart, Indent, Depth, LimitLine);
+ } else {
+ Result = parseInlineValueOnLine(LineIndex, ContentStart, Depth, LimitLine);
+ }
+ return Result;
+ }
+
+ [[nodiscard]] NodeID parseBlockMapping(std::size_t &LineIndex, std::size_t Indent,
+ std::size_t Depth, std::size_t LimitLine) {
+ const std::size_t Begin = Lines[LineIndex].Begin + Indent;
+ std::vector<MappingEntry> Entries;
+ while (LineIndex < LimitLine) {
+ skipBlankLines(LineIndex, LimitLine);
+ if (LineIndex >= LimitLine || Lines[LineIndex].Indent < Indent)
+ break;
+ if (!validateIndent(LineIndex))
+ return {};
+ if (Lines[LineIndex].Indent > Indent) {
+ diagnose(Lines[LineIndex].Begin + Lines[LineIndex].Indent, Lines[LineIndex].ContentEnd,
+ "unexpected indentation in YAML mapping");
+ return {};
+ }
+
+ const std::size_t KeyStart = Lines[LineIndex].Begin + Indent;
+ if (!findBlockMappingColon(KeyStart, Lines[LineIndex].ContentEnd))
+ break;
+ if (!parseMappingEntry(LineIndex, KeyStart, Indent, Depth, LimitLine, Entries))
+ return {};
+ }
+
+ const std::size_t End =
+ LineIndex == 0 ? Begin : std::max(Begin, Lines[LineIndex - 1].ContentEnd);
+ return addMappingNode(Begin, End, CollectionStyle::Block, std::move(Entries));
+ }
+
+ [[nodiscard]] NodeID parseInlineStartedMapping(std::size_t &LineIndex, std::size_t KeyStart,
+ std::size_t MappingIndent, std::size_t Depth,
+ std::size_t LimitLine) {
+ const std::size_t Begin = KeyStart;
+ std::vector<MappingEntry> Entries;
+ if (!parseMappingEntry(LineIndex, KeyStart, MappingIndent, Depth, LimitLine, Entries))
+ return {};
+
+ while (LineIndex < LimitLine) {
+ skipBlankLines(LineIndex, LimitLine);
+ if (LineIndex >= LimitLine || Lines[LineIndex].Indent < MappingIndent)
+ break;
+ if (!validateIndent(LineIndex))
+ return {};
+ if (Lines[LineIndex].Indent > MappingIndent) {
+ diagnose(Lines[LineIndex].Begin + Lines[LineIndex].Indent, Lines[LineIndex].ContentEnd,
+ "unexpected indentation in YAML mapping");
+ return {};
+ }
+ const std::size_t ContinuationKey = Lines[LineIndex].Begin + MappingIndent;
+ if (!findBlockMappingColon(ContinuationKey, Lines[LineIndex].ContentEnd))
+ break;
+ if (!parseMappingEntry(LineIndex, ContinuationKey, MappingIndent, Depth, LimitLine, Entries))
+ return {};
+ }
+
+ const std::size_t End =
+ LineIndex == 0 ? Begin : std::max(Begin, Lines[LineIndex - 1].ContentEnd);
+ return addMappingNode(Begin, End, CollectionStyle::Block, std::move(Entries));
+ }
+
+ [[nodiscard]] bool parseMappingEntry(std::size_t &LineIndex, std::size_t KeyStart,
+ std::size_t ParentIndent, std::size_t Depth,
+ std::size_t LimitLine, std::vector<MappingEntry> &Entries) {
+ const PhysicalLine &Line = Lines[LineIndex];
+ const std::optional<std::size_t> Colon = findBlockMappingColon(KeyStart, Line.ContentEnd);
+ if (!Colon) {
+ diagnose(KeyStart, Line.ContentEnd, "expected ':' after YAML mapping key");
+ return false;
+ }
+
+ std::string Key;
+ TextRange KeyRange;
+ if (!parseMappingKey(KeyStart, *Colon, Key, KeyRange))
+ return false;
+ if (std::any_of(Entries.begin(), Entries.end(),
+ [&Key](const MappingEntry &Entry) { return Entry.Key == Key; })) {
+ diagnose(KeyStart, *Colon, "duplicate YAML mapping key '" + Key + "'");
+ return false;
+ }
+
+ std::size_t ValueStart = *Colon + 1;
+ const std::string_view Text = Parsed.Source.text();
+ while (ValueStart < Line.ContentEnd && isAsciiSpace(Text[ValueStart]))
+ ++ValueStart;
+
+ NodeID Value;
+ if (ValueStart == Line.ContentEnd || Text[ValueStart] == '#') {
+ const std::size_t CurrentLine = LineIndex;
+ std::size_t NestedLine = LineIndex + 1;
+ skipBlankLines(NestedLine, LimitLine);
+ if (NestedLine < LimitLine && Lines[NestedLine].Indent > ParentIndent) {
+ LineIndex = NestedLine;
+ Value = parseBlockNode(LineIndex, Lines[NestedLine].Indent, Depth + 1, LimitLine);
+ } else {
+ Value = addNullNode(*Colon + 1, *Colon + 1);
+ LineIndex = CurrentLine + 1;
+ }
+ } else if (Text[ValueStart] == '|' || Text[ValueStart] == '>') {
+ Value = parseBlockScalar(LineIndex, ValueStart, ParentIndent, Depth + 1, LimitLine);
+ } else {
+ Value = parseInlineValueOnLine(LineIndex, ValueStart, Depth + 1, LimitLine);
+ }
+ if (Failed)
+ return false;
+
+ Entries.push_back(MappingEntry{
+ .Key = std::move(Key),
+ .KeyRange = KeyRange,
+ .Value = Value,
+ });
+ return true;
+ }
+
+ [[nodiscard]] NodeID parseBlockSequence(std::size_t &LineIndex, std::size_t Indent,
+ std::size_t Depth, std::size_t LimitLine) {
+ const std::size_t Begin = Lines[LineIndex].Begin + Indent;
+ std::vector<NodeID> Items;
+ const std::string_view Text = Parsed.Source.text();
+
+ while (LineIndex < LimitLine) {
+ skipBlankLines(LineIndex, LimitLine);
+ if (LineIndex >= LimitLine || Lines[LineIndex].Indent < Indent)
+ break;
+ if (!validateIndent(LineIndex))
+ return {};
+ if (Lines[LineIndex].Indent > Indent) {
+ diagnose(Lines[LineIndex].Begin + Lines[LineIndex].Indent, Lines[LineIndex].ContentEnd,
+ "unexpected indentation in YAML sequence");
+ return {};
+ }
+
+ const std::size_t Dash = Lines[LineIndex].Begin + Indent;
+ if (!isSequenceIndicator(Dash, Lines[LineIndex].ContentEnd))
+ break;
+
+ std::size_t ItemStart = Dash + 1;
+ while (ItemStart < Lines[LineIndex].ContentEnd && isAsciiSpace(Text[ItemStart]))
+ ++ItemStart;
+
+ NodeID Item;
+ if (ItemStart == Lines[LineIndex].ContentEnd || Text[ItemStart] == '#') {
+ const std::size_t CurrentLine = LineIndex;
+ std::size_t NestedLine = LineIndex + 1;
+ skipBlankLines(NestedLine, LimitLine);
+ if (NestedLine < LimitLine && Lines[NestedLine].Indent > Indent) {
+ LineIndex = NestedLine;
+ Item = parseBlockNode(LineIndex, Lines[NestedLine].Indent, Depth + 1, LimitLine);
+ } else {
+ Item = addNullNode(Dash + 1, Dash + 1);
+ LineIndex = CurrentLine + 1;
+ }
+ } else if (Text[ItemStart] == '|' || Text[ItemStart] == '>') {
+ Item = parseBlockScalar(LineIndex, ItemStart, Indent, Depth + 1, LimitLine);
+ } else if (findBlockMappingColon(ItemStart, Lines[LineIndex].ContentEnd)) {
+ const std::size_t MappingIndent = ItemStart - Lines[LineIndex].Begin;
+ Item = parseInlineStartedMapping(LineIndex, ItemStart, MappingIndent, Depth + 1, LimitLine);
+ } else {
+ Item = parseInlineValueOnLine(LineIndex, ItemStart, Depth + 1, LimitLine);
+ }
+ if (Failed)
+ return {};
+ Items.push_back(Item);
+ }
+
+ const std::size_t End =
+ LineIndex == 0 ? Begin : std::max(Begin, Lines[LineIndex - 1].ContentEnd);
+ return addSequenceNode(Begin, End, CollectionStyle::Block, std::move(Items));
+ }
+
+ [[nodiscard]] NodeID parseInlineValueOnLine(std::size_t &LineIndex, std::size_t Begin,
+ std::size_t Depth, std::size_t LimitLine) {
+ const std::string_view Text = Parsed.Source.text();
+ const std::size_t InitialLine = LineIndex;
+ const std::size_t LineEnd = Lines[InitialLine].ContentEnd;
+ std::size_t ValueStart = Begin;
+ while (ValueStart < LineEnd && isAsciiSpace(Text[ValueStart]))
+ ++ValueStart;
+
+ const bool CanSpanLines =
+ ValueStart < LineEnd && (Text[ValueStart] == '[' || Text[ValueStart] == '{' ||
+ Text[ValueStart] == '\'' || Text[ValueStart] == '"');
+ if (!CanSpanLines) {
+ NodeID Result = parseInlineValue(ValueStart, LineEnd, Depth);
+ ++LineIndex;
+ return Result;
+ }
+
+ const std::size_t DocumentEnd =
+ LimitLine < Lines.size() ? Lines[LimitLine].Begin : Parsed.Source.text().size();
+ std::size_t Cursor = ValueStart;
+ NodeID Result = parseFlowNode(Cursor, DocumentEnd, Depth, false);
+ if (Failed)
+ return {};
+
+ const std::size_t LastValueOffset = Cursor == 0 ? 0 : Cursor - 1;
+ const std::size_t LastLine = Parsed.Source.positionAt(LastValueOffset).Line - 1;
+ if (LastLine >= Lines.size()) {
+ diagnose(Cursor, Cursor, "internal YAML line tracking failure");
+ return {};
+ }
+
+ std::size_t Tail = Cursor;
+ while (Tail < Lines[LastLine].ContentEnd && isAsciiSpace(Text[Tail]))
+ ++Tail;
+ if (Tail < Lines[LastLine].ContentEnd && Text[Tail] != '#') {
+ diagnose(Tail, Lines[LastLine].ContentEnd, "unexpected characters after YAML value");
+ return {};
+ }
+ LineIndex = LastLine + 1;
+ return Result;
+ }
+
+ [[nodiscard]] NodeID parseInlineValue(std::size_t Begin, std::size_t End, std::size_t Depth) {
+ if (!checkDepth(Depth))
+ return {};
+ const std::string_view Text = Parsed.Source.text();
+ while (Begin < End && isAsciiSpace(Text[Begin]))
+ ++Begin;
+ if (Begin == End || Text[Begin] == '#')
+ return addNullNode(Begin, Begin);
+
+ std::size_t Cursor = Begin;
+ NodeID Result = parseFlowNode(Cursor, End, Depth, false);
+ if (Failed)
+ return {};
+
+ while (Cursor < End && isAsciiSpace(Text[Cursor]))
+ ++Cursor;
+ if (Cursor < End && Text[Cursor] != '#') {
+ diagnose(Cursor, End, "unexpected characters after YAML value");
+ return {};
+ }
+ return Result;
+ }
+
+ [[nodiscard]] NodeID parseFlowNode(std::size_t &Cursor, std::size_t End, std::size_t Depth,
+ bool IsFlowValue) {
+ if (!checkDepth(Depth))
+ return {};
+ const std::string_view Text = Parsed.Source.text();
+ while (Cursor < End && isAsciiSpace(Text[Cursor]))
+ ++Cursor;
+ if (Cursor >= End) {
+ diagnose(End, End, "expected YAML value");
+ return {};
+ }
+
+ if (Text[Cursor] == '[')
+ return parseFlowSequence(Cursor, End, Depth);
+ if (Text[Cursor] == '{')
+ return parseFlowMapping(Cursor, End, Depth);
+ if (Text[Cursor] == '\'' || Text[Cursor] == '"')
+ return parseQuotedScalar(Cursor, End);
+ if (isUnrecognizedPlainStart(Text[Cursor])) {
+ diagnose(Cursor, Cursor + 1, "Unrecognized character while tokenizing.", "YAML");
+ return {};
+ }
+ if (Text[Cursor] == '&' || Text[Cursor] == '*' || Text[Cursor] == '!' || Text[Cursor] == '%') {
+ diagnose(Cursor, Cursor + 1, "YAML anchors, aliases, tags, and directives are not supported");
+ return {};
+ }
+
+ const std::size_t Begin = Cursor;
+ while (Cursor < End) {
+ const char Character = Text[Cursor];
+ if (IsFlowValue && (Character == ',' || Character == ']' || Character == '}'))
+ break;
+ if (Character == '#' && (Cursor == Begin || isAsciiSpace(Text[Cursor - 1])))
+ break;
+ ++Cursor;
+ }
+ std::size_t ScalarEnd = Cursor;
+ while (ScalarEnd > Begin && isAsciiSpace(Text[ScalarEnd - 1]))
+ --ScalarEnd;
+ if (ScalarEnd == Begin) {
+ diagnose(Begin, std::min(Begin + 1, End), "expected YAML scalar");
+ return {};
+ }
+ const std::string Value(Text.substr(Begin, ScalarEnd - Begin));
+ return isNullSpelling(Value) ? addNullNode(Begin, ScalarEnd)
+ : addScalarNode(Begin, ScalarEnd, ScalarStyle::Plain, Value);
+ }
+
+ [[nodiscard]] NodeID parseFlowSequence(std::size_t &Cursor, std::size_t End, std::size_t Depth) {
+ const std::size_t Begin = Cursor++;
+ std::vector<NodeID> Items;
+ const std::string_view Text = Parsed.Source.text();
+ skipFlowSpace(Cursor, End);
+ if (Cursor < End && Text[Cursor] == ']') {
+ ++Cursor;
+ return addSequenceNode(Begin, Cursor, CollectionStyle::Flow, std::move(Items));
+ }
+
+ while (Cursor < End) {
+ Items.push_back(parseFlowNode(Cursor, End, Depth + 1, true));
+ if (Failed)
+ return {};
+ skipFlowSpace(Cursor, End);
+ if (Cursor >= End) {
+ diagnose(Begin, End, "unterminated YAML flow sequence");
+ return {};
+ }
+ if (Text[Cursor] == ']') {
+ ++Cursor;
+ return addSequenceNode(Begin, Cursor, CollectionStyle::Flow, std::move(Items));
+ }
+ if (Text[Cursor] != ',') {
+ diagnose(Cursor, Cursor + 1, "expected ',' or ']' in YAML flow sequence");
+ return {};
+ }
+ ++Cursor;
+ skipFlowSpace(Cursor, End);
+ if (Cursor < End && Text[Cursor] == ']') {
+ ++Cursor;
+ return addSequenceNode(Begin, Cursor, CollectionStyle::Flow, std::move(Items));
+ }
+ }
+
+ diagnose(Begin, End, "unterminated YAML flow sequence");
+ return {};
+ }
+
+ [[nodiscard]] NodeID parseFlowMapping(std::size_t &Cursor, std::size_t End, std::size_t Depth) {
+ const std::size_t Begin = Cursor++;
+ std::vector<MappingEntry> Entries;
+ const std::string_view Text = Parsed.Source.text();
+ skipFlowSpace(Cursor, End);
+ if (Cursor < End && Text[Cursor] == '}') {
+ ++Cursor;
+ return addMappingNode(Begin, Cursor, CollectionStyle::Flow, std::move(Entries));
+ }
+
+ while (Cursor < End) {
+ std::string Key;
+ TextRange KeyRange;
+ if (!parseFlowKey(Cursor, End, Key, KeyRange))
+ return {};
+ if (std::any_of(Entries.begin(), Entries.end(),
+ [&Key](const MappingEntry &Entry) { return Entry.Key == Key; })) {
+ diagnose(KeyRange.Begin.Offset, KeyRange.End.Offset,
+ "duplicate YAML mapping key '" + Key + "'");
+ return {};
+ }
+ skipFlowSpace(Cursor, End);
+ if (Cursor >= End || Text[Cursor] != ':') {
+ diagnose(Cursor, std::min(Cursor + 1, End), "expected ':' after YAML flow mapping key");
+ return {};
+ }
+ ++Cursor;
+ skipFlowSpace(Cursor, End);
+ NodeID Value;
+ if (isFlowBlockSequenceStart(Cursor, End))
+ Value = parseFlowBlockSequence(Cursor, End, Depth + 1);
+ else if (Cursor < End && (Text[Cursor] == ',' || Text[Cursor] == '}'))
+ Value = addNullNode(Cursor, Cursor);
+ else
+ Value = parseFlowNode(Cursor, End, Depth + 1, true);
+ if (Failed)
+ return {};
+ Entries.push_back(MappingEntry{
+ .Key = std::move(Key),
+ .KeyRange = KeyRange,
+ .Value = Value,
+ });
+
+ skipFlowSpace(Cursor, End);
+ if (Cursor >= End) {
+ diagnose(Begin, End, "unterminated YAML flow mapping");
+ return {};
+ }
+ if (Text[Cursor] == '}') {
+ ++Cursor;
+ return addMappingNode(Begin, Cursor, CollectionStyle::Flow, std::move(Entries));
+ }
+ if (Text[Cursor] != ',') {
+ diagnose(Cursor, Cursor + 1, "expected ',' or '}' in YAML flow mapping");
+ return {};
+ }
+ ++Cursor;
+ skipFlowSpace(Cursor, End);
+ if (Cursor < End && Text[Cursor] == '}') {
+ ++Cursor;
+ return addMappingNode(Begin, Cursor, CollectionStyle::Flow, std::move(Entries));
+ }
+ }
+
+ diagnose(Begin, End, "unterminated YAML flow mapping");
+ return {};
+ }
+
+ [[nodiscard]] NodeID parseFlowBlockSequence(std::size_t &Cursor, std::size_t End,
+ std::size_t Depth) {
+ if (!checkDepth(Depth))
+ return {};
+ const std::size_t Begin = Cursor;
+ const std::size_t FirstLine = Parsed.Source.positionAt(Cursor).Line - 1;
+ const std::size_t Indent = Lines[FirstLine].Indent;
+ const std::string_view Text = Parsed.Source.text();
+ std::vector<NodeID> Items;
+ std::size_t LastItemEnd = Begin;
+
+ while (isFlowBlockSequenceStart(Cursor, End)) {
+ const std::size_t ItemLine = Parsed.Source.positionAt(Cursor).Line - 1;
+ if (Lines[ItemLine].Indent != Indent)
+ break;
+
+ const std::size_t Dash = Cursor++;
+ while (Cursor < Lines[ItemLine].ContentEnd && isAsciiSpace(Text[Cursor]))
+ ++Cursor;
+ if (Cursor == Lines[ItemLine].ContentEnd || Text[Cursor] == '#') {
+ diagnose(Dash, Lines[ItemLine].ContentEnd,
+ "empty block sequence entry inside a flow mapping is not supported");
+ return {};
+ }
+
+ const bool ItemCanSpan =
+ Text[Cursor] == '[' || Text[Cursor] == '{' || Text[Cursor] == '\'' || Text[Cursor] == '"';
+ const std::size_t ItemEnd = ItemCanSpan ? End : Lines[ItemLine].ContentEnd;
+ Items.push_back(parseFlowNode(Cursor, ItemEnd, Depth + 1, true));
+ if (Failed)
+ return {};
+ LastItemEnd = Cursor;
+ skipFlowSpace(Cursor, End);
+ }
+
+ return addSequenceNode(Begin, LastItemEnd, CollectionStyle::Block, std::move(Items));
+ }
+
+ [[nodiscard]] bool parseFlowKey(std::size_t &Cursor, std::size_t End, std::string &Key,
+ TextRange &Range) {
+ const std::string_view Text = Parsed.Source.text();
+ skipFlowSpace(Cursor, End);
+ if (Cursor >= End) {
+ diagnose(End, End, "expected YAML flow mapping key");
+ return false;
+ }
+
+ const std::size_t Begin = Cursor;
+ if (isUnrecognizedPlainStart(Text[Cursor])) {
+ diagnose(Cursor, Cursor + 1, "Unrecognized character while tokenizing.", "YAML");
+ return false;
+ }
+ if (Text[Cursor] == '\'' || Text[Cursor] == '"') {
+ ScalarStyle Style = ScalarStyle::Plain;
+ return parseQuotedText(Cursor, End, Key, Style, Range);
+ }
+
+ while (Cursor < End && Text[Cursor] != ':' && Text[Cursor] != ',' && Text[Cursor] != '}')
+ ++Cursor;
+ std::size_t KeyEnd = Cursor;
+ while (KeyEnd > Begin && isAsciiSpace(Text[KeyEnd - 1]))
+ --KeyEnd;
+ if (KeyEnd == Begin) {
+ diagnose(Begin, std::min(Begin + 1, End), "empty YAML mapping keys are not supported");
+ return false;
+ }
+ Key = std::string(Text.substr(Begin, KeyEnd - Begin));
+ Range = Parsed.Source.range(Begin, KeyEnd);
+ return true;
+ }
+
+ [[nodiscard]] NodeID parseQuotedScalar(std::size_t &Cursor, std::size_t End) {
+ std::string Value;
+ ScalarStyle Style = ScalarStyle::Plain;
+ TextRange Range;
+ if (!parseQuotedText(Cursor, End, Value, Style, Range))
+ return {};
+ return addScalarNode(Range.Begin.Offset, Range.End.Offset, Style, std::move(Value));
+ }
+
+ [[nodiscard]] bool parseQuotedText(std::size_t &Cursor, std::size_t End, std::string &Value,
+ ScalarStyle &Style, TextRange &Range) {
+ const std::string_view Text = Parsed.Source.text();
+ const std::size_t Begin = Cursor;
+ const char Quote = Text[Cursor++];
+
+ while (Cursor < End) {
+ const char Character = Text[Cursor++];
+ if (Character == Quote) {
+ if (Quote == '\'' && Cursor < End && Text[Cursor] == '\'') {
+ Value.push_back('\'');
+ ++Cursor;
+ continue;
+ }
+ Style = Quote == '\'' ? ScalarStyle::SingleQuoted : ScalarStyle::DoubleQuoted;
+ Range = Parsed.Source.range(Begin, Cursor);
+ return true;
+ }
+
+ if (Quote == '\'' || Character != '\\') {
+ if (static_cast<unsigned char>(Character) < 0x20U && Character != '\t') {
+ diagnose(Cursor - 1, Cursor, "control character is not allowed in quoted YAML scalar");
+ return false;
+ }
+ Value.push_back(Character);
+ continue;
+ }
+
+ if (Cursor >= End) {
+ diagnose(Cursor - 1, Cursor, "unterminated escape in YAML scalar");
+ return false;
+ }
+ const char Escape = Text[Cursor++];
+ switch (Escape) {
+ case '0':
+ Value.push_back('\0');
+ break;
+ case 'a':
+ Value.push_back('\a');
+ break;
+ case 'b':
+ Value.push_back('\b');
+ break;
+ case 't':
+ case '\t':
+ Value.push_back('\t');
+ break;
+ case 'n':
+ Value.push_back('\n');
+ break;
+ case 'v':
+ Value.push_back('\v');
+ break;
+ case 'f':
+ Value.push_back('\f');
+ break;
+ case 'r':
+ Value.push_back('\r');
+ break;
+ case 'e':
+ Value.push_back(static_cast<char>(0x1B));
+ break;
+ case ' ':
+ Value.push_back(' ');
+ break;
+ case '"':
+ Value.push_back('"');
+ break;
+ case '/':
+ Value.push_back('/');
+ break;
+ case '\\':
+ Value.push_back('\\');
+ break;
+ case 'N':
+ appendUTF8(Value, 0x85U);
+ break;
+ case '_':
+ appendUTF8(Value, 0xA0U);
+ break;
+ case 'L':
+ appendUTF8(Value, 0x2028U);
+ break;
+ case 'P':
+ appendUTF8(Value, 0x2029U);
+ break;
+ case 'x':
+ if (!parseUnicodeEscape(Cursor, End, 2, Value))
+ return false;
+ break;
+ case 'u':
+ if (!parseUnicodeEscape(Cursor, End, 4, Value))
+ return false;
+ break;
+ case 'U':
+ if (!parseUnicodeEscape(Cursor, End, 8, Value))
+ return false;
+ break;
+ default:
+ diagnose(Cursor - 1, Cursor, "unknown escape in double-quoted YAML scalar");
+ return false;
+ }
+ }
+
+ diagnose(Begin, End, "unterminated quoted YAML scalar");
+ return false;
+ }
+
+ [[nodiscard]] bool parseUnicodeEscape(std::size_t &Cursor, std::size_t End,
+ std::size_t DigitCount, std::string &Output) {
+ if (End - Cursor < DigitCount) {
+ diagnose(Cursor, End, "incomplete Unicode escape in YAML scalar");
+ return false;
+ }
+ std::uint32_t CodePoint = 0;
+ for (std::size_t Index = 0; Index < DigitCount; ++Index) {
+ if (!isHexDigit(Parsed.Source.text()[Cursor + Index])) {
+ diagnose(Cursor + Index, Cursor + Index + 1,
+ "invalid hexadecimal digit in YAML Unicode escape");
+ return false;
+ }
+ CodePoint = (CodePoint << 4U) | hexValue(Parsed.Source.text()[Cursor + Index]);
+ }
+ Cursor += DigitCount;
+ if (CodePoint > 0x10FFFFU || (CodePoint >= 0xD800U && CodePoint <= 0xDFFFU)) {
+ diagnose(Cursor - DigitCount, Cursor, "invalid Unicode scalar value in YAML escape");
+ return false;
+ }
+ appendUTF8(Output, CodePoint);
+ return true;
+ }
+
+ [[nodiscard]] NodeID parseBlockScalar(std::size_t &LineIndex, std::size_t IndicatorStart,
+ std::size_t ParentIndent, std::size_t Depth,
+ std::size_t LimitLine) {
+ if (!checkDepth(Depth))
+ return {};
+ const std::string_view Text = Parsed.Source.text();
+ const char Indicator = Text[IndicatorStart];
+ char Chomping = '\0';
+ std::optional<unsigned> ExplicitIndent;
+ std::size_t Cursor = IndicatorStart + 1;
+ while (Cursor < Lines[LineIndex].ContentEnd && !isAsciiSpace(Text[Cursor]) &&
+ Text[Cursor] != '#') {
+ const char Header = Text[Cursor++];
+ if ((Header == '+' || Header == '-') && Chomping == '\0') {
+ Chomping = Header;
+ continue;
+ }
+ if (Header >= '1' && Header <= '9' && !ExplicitIndent) {
+ ExplicitIndent = static_cast<unsigned>(Header - '0');
+ continue;
+ }
+ diagnose(Cursor - 1, Cursor, "invalid YAML block scalar header");
+ return {};
+ }
+ while (Cursor < Lines[LineIndex].ContentEnd && isAsciiSpace(Text[Cursor]))
+ ++Cursor;
+ if (Cursor < Lines[LineIndex].ContentEnd && Text[Cursor] != '#') {
+ diagnose(Cursor, Lines[LineIndex].ContentEnd,
+ "unexpected characters after YAML block scalar header");
+ return {};
+ }
+
+ const std::size_t HeaderLine = LineIndex;
+ std::size_t FirstContentLine = LineIndex + 1;
+ std::size_t FirstNonBlank = FirstContentLine;
+ while (FirstNonBlank < LimitLine && isWhitespaceOnlyLine(FirstNonBlank))
+ ++FirstNonBlank;
+
+ std::size_t ContentIndent = ParentIndent + 1;
+ if (ExplicitIndent)
+ ContentIndent = ParentIndent + *ExplicitIndent;
+ else if (FirstNonBlank < LimitLine)
+ ContentIndent = Lines[FirstNonBlank].Indent;
+
+ if (FirstNonBlank < LimitLine && Lines[FirstNonBlank].Indent <= ParentIndent) {
+ FirstContentLine = FirstNonBlank;
+ ContentIndent = ParentIndent + 1;
+ } else if (FirstNonBlank < LimitLine && Lines[FirstNonBlank].Indent < ContentIndent) {
+ diagnose(Lines[FirstNonBlank].Begin, Lines[FirstNonBlank].ContentEnd,
+ "block scalar content is less indented than its header");
+ return {};
+ }
+
+ struct ScalarLine final {
+ std::string Text;
+ bool HasLineBreak = false;
+ bool IsBlank = false;
+ bool IsMoreIndented = false;
+ };
+ std::vector<ScalarLine> ScalarLines;
+ std::size_t CurrentLine = FirstContentLine;
+ while (CurrentLine < LimitLine) {
+ const PhysicalLine &Line = Lines[CurrentLine];
+ const bool IsWhitespaceOnly = isWhitespaceOnlyLine(CurrentLine);
+ if (!IsWhitespaceOnly && Line.Indent < ContentIndent)
+ break;
+
+ ScalarLine ScalarPart;
+ ScalarPart.HasLineBreak = Line.End > Line.ContentEnd;
+ ScalarPart.IsBlank = IsWhitespaceOnly;
+ ScalarPart.IsMoreIndented = !IsWhitespaceOnly && Line.Indent > ContentIndent;
+ if (!IsWhitespaceOnly) {
+ const std::size_t TextBegin = Line.Begin + ContentIndent;
+ ScalarPart.Text = std::string(Text.substr(TextBegin, Line.ContentEnd - TextBegin));
+ }
+ ScalarLines.push_back(std::move(ScalarPart));
+ ++CurrentLine;
+ }
+
+ std::string Value;
+ for (std::size_t Index = 0; Index < ScalarLines.size(); ++Index) {
+ const ScalarLine &Line = ScalarLines[Index];
+ Value += Line.Text;
+ if (!Line.HasLineBreak)
+ continue;
+
+ bool FoldBreak = false;
+ if (Indicator == '>' && Index + 1 < ScalarLines.size()) {
+ const ScalarLine &Next = ScalarLines[Index + 1];
+ FoldBreak = !Line.IsBlank && !Next.IsBlank && !Line.IsMoreIndented && !Next.IsMoreIndented;
+ }
+ Value.push_back(FoldBreak ? ' ' : '\n');
+ }
+
+ if (Chomping != '+') {
+ while (!Value.empty() && Value.back() == '\n')
+ Value.pop_back();
+ if (Chomping != '-' && !ScalarLines.empty() && ScalarLines.back().HasLineBreak)
+ Value.push_back('\n');
+ }
+
+ LineIndex = CurrentLine;
+ const std::size_t End = CurrentLine > FirstContentLine ? Lines[CurrentLine - 1].ContentEnd
+ : Lines[HeaderLine].ContentEnd;
+ return addScalarNode(IndicatorStart, End,
+ Indicator == '|' ? ScalarStyle::Literal : ScalarStyle::Folded,
+ std::move(Value));
+ }
+
+ [[nodiscard]] bool parseMappingKey(std::size_t Begin, std::size_t End, std::string &Key,
+ TextRange &Range) {
+ const std::string_view Text = Parsed.Source.text();
+ while (Begin < End && isAsciiSpace(Text[Begin]))
+ ++Begin;
+ while (End > Begin && isAsciiSpace(Text[End - 1]))
+ --End;
+ if (Begin == End) {
+ diagnose(Begin, End, "empty YAML mapping keys are not supported");
+ return false;
+ }
+
+ if (isUnrecognizedPlainStart(Text[Begin])) {
+ diagnose(Begin, Begin + 1, "Unrecognized character while tokenizing.", "YAML");
+ return false;
+ }
+
+ if (Text[Begin] == '\'' || Text[Begin] == '"') {
+ std::size_t Cursor = Begin;
+ ScalarStyle Style = ScalarStyle::Plain;
+ if (!parseQuotedText(Cursor, End, Key, Style, Range))
+ return false;
+ while (Cursor < End && isAsciiSpace(Text[Cursor]))
+ ++Cursor;
+ if (Cursor != End) {
+ diagnose(Cursor, End, "unexpected characters after quoted YAML mapping key");
+ return false;
+ }
+ return true;
+ }
+ if (Text[Begin] == '?' || Text[Begin] == '[' || Text[Begin] == '{') {
+ diagnose(Begin, End, "complex YAML mapping keys are not supported");
+ return false;
+ }
+ Key = std::string(Text.substr(Begin, End - Begin));
+ Range = Parsed.Source.range(Begin, End);
+ return true;
+ }
+
+ [[nodiscard]] std::optional<std::size_t> findBlockMappingColon(std::size_t Begin,
+ std::size_t End) const noexcept {
+ const std::string_view Text = Parsed.Source.text();
+ char Quote = '\0';
+ unsigned FlowDepth = 0;
+ for (std::size_t Cursor = Begin; Cursor < End; ++Cursor) {
+ const char Character = Text[Cursor];
+ if (Quote == '\'') {
+ if (Character == '\'' && Cursor + 1 < End && Text[Cursor + 1] == '\'') {
+ ++Cursor;
+ } else if (Character == '\'') {
+ Quote = '\0';
+ }
+ continue;
+ }
+ if (Quote == '"') {
+ if (Character == '\\' && Cursor + 1 < End) {
+ ++Cursor;
+ } else if (Character == '"') {
+ Quote = '\0';
+ }
+ continue;
+ }
+ if (Character == '\'' || Character == '"') {
+ Quote = Character;
+ continue;
+ }
+ if (Character == '[' || Character == '{') {
+ ++FlowDepth;
+ continue;
+ }
+ if ((Character == ']' || Character == '}') && FlowDepth > 0) {
+ --FlowDepth;
+ continue;
+ }
+ if (Character == '#' && (Cursor == Begin || isAsciiSpace(Text[Cursor - 1])))
+ return std::nullopt;
+ if (Character != ':' || FlowDepth != 0)
+ continue;
+ if (Cursor + 1 == End || isAsciiSpace(Text[Cursor + 1]) || Text[Cursor + 1] == '#')
+ return Cursor;
+ }
+ return std::nullopt;
+ }
+
+ [[nodiscard]] bool isSequenceIndicator(std::size_t Offset, std::size_t End) const noexcept {
+ if (Offset >= End || Parsed.Source.text()[Offset] != '-')
+ return false;
+ return Offset + 1 == End || isAsciiSpace(Parsed.Source.text()[Offset + 1]) ||
+ Parsed.Source.text()[Offset + 1] == '#';
+ }
+
+ [[nodiscard]] static bool isUnrecognizedPlainStart(char Character) noexcept {
+ return Character == '@' || Character == '`';
+ }
+
+ void skipFlowSpace(std::size_t &Cursor, std::size_t End) const noexcept {
+ const std::string_view Text = Parsed.Source.text();
+ while (Cursor < End) {
+ if (isAsciiSpace(Text[Cursor]) || Text[Cursor] == '\r' || Text[Cursor] == '\n') {
+ ++Cursor;
+ continue;
+ }
+ if (Text[Cursor] != '#')
+ return;
+ while (Cursor < End && Text[Cursor] != '\n')
+ ++Cursor;
+ }
+ }
+
+ [[nodiscard]] bool isFlowBlockSequenceStart(std::size_t Cursor, std::size_t End) const noexcept {
+ if (Cursor >= End)
+ return false;
+ const std::size_t LineIndex = Parsed.Source.positionAt(Cursor).Line - 1;
+ if (LineIndex >= Lines.size())
+ return false;
+ const PhysicalLine &Line = Lines[LineIndex];
+ return Cursor == Line.Begin + Line.Indent && isSequenceIndicator(Cursor, Line.ContentEnd);
+ }
+
+ [[nodiscard]] bool isWhitespaceOnlyLine(std::size_t LineIndex) const noexcept {
+ const PhysicalLine &Line = Lines[LineIndex];
+ const std::string_view Text = Parsed.Source.text();
+ for (std::size_t Cursor = Line.Begin; Cursor < Line.ContentEnd; ++Cursor) {
+ if (!isAsciiSpace(Text[Cursor]))
+ return false;
+ }
+ return true;
+ }
+
+ [[nodiscard]] bool checkDepth(std::size_t Depth) {
+ if (Depth <= Options.MaximumDepth)
+ return true;
+ diagnose(0, 0, "maximum YAML nesting depth exceeded");
+ return false;
+ }
+
+ [[nodiscard]] NodeID addNullNode(std::size_t Begin, std::size_t End) {
+ return addNode(Node(NodeKind::Null, Parsed.Source.range(Begin, End)));
+ }
+
+ [[nodiscard]] NodeID addScalarNode(std::size_t Begin, std::size_t End, ScalarStyle Style,
+ std::string Value) {
+ Node NewNode(NodeKind::Scalar, Parsed.Source.range(Begin, End));
+ NewNode.ScalarStyleValue = Style;
+ NewNode.Scalar = std::move(Value);
+ return addNode(std::move(NewNode));
+ }
+
+ [[nodiscard]] NodeID addSequenceNode(std::size_t Begin, std::size_t End, CollectionStyle Style,
+ std::vector<NodeID> Items) {
+ Node NewNode(NodeKind::Sequence, Parsed.Source.range(Begin, End));
+ NewNode.CollectionStyleValue = Style;
+ NewNode.Sequence = std::move(Items);
+ return addNode(std::move(NewNode));
+ }
+
+ [[nodiscard]] NodeID addMappingNode(std::size_t Begin, std::size_t End, CollectionStyle Style,
+ std::vector<MappingEntry> Entries) {
+ Node NewNode(NodeKind::Mapping, Parsed.Source.range(Begin, End));
+ NewNode.CollectionStyleValue = Style;
+ NewNode.Mapping = std::move(Entries);
+ return addNode(std::move(NewNode));
+ }
+
+ [[nodiscard]] NodeID addNode(Node NewNode) {
+ if (Parsed.Nodes.size() >= Options.MaximumNodes) {
+ diagnose(NewNode.range().Begin.Offset, NewNode.range().End.Offset,
+ "maximum YAML node count exceeded");
+ return {};
+ }
+ const auto RawID = static_cast<std::uint32_t>(Parsed.Nodes.size());
+ Parsed.Nodes.push_back(std::move(NewNode));
+ return NodeID(RawID);
+ }
+
+ Stream Parsed;
+ ParseOptions Options;
+ std::vector<PhysicalLine> Lines;
+ std::vector<TextDiagnostic> Diagnostics;
+ bool Failed = false;
+};
+
+ParseResult parse(std::string SourceName, std::string SourceText, ParseOptions Options) {
+ return Parser(std::move(SourceName), std::move(SourceText), Options).run();
+}
+
+} // namespace rcc::yaml
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-30 07:14:33 +0000