AK: Add dbgln() format checking

This checks the following things:
- No unclosed braces in format string
    `dbgln("a:{}}", a)` where the '}}' would be interpreted as a
    literal '}'
    `dbgln("a:{", a)` where someone with a faulty keyboard like mine
    could generate
- No extra closed braces in format string
    `dbgln("a:{{}", a)` where the '{{' would interpreted as a literal '{'
    `dbgln("a:}", a)` where someone with a faulty keyboard could
    generate
- No references to nonexistent arguments
    `dbgln("a:{} b:{}", a)` where the value of `b` is not in the
    arguments list
- No unconsumed argument
    `dbgln("a:{1}", not_used, 1)` where `not_used` is extraneous

1 files changed, 172 insertions, 1 deletions

diff --git a/AK/Format.h b/AK/Format.h
index 5bbf346dba..ede7a2585a 100644
--- a/AK/Format.h
+++ b/AK/Format.h
@@ -26,6 +26,8 @@
 
 #pragma once
 
+#include <AK/AllOf.h>
+#include <AK/AnyOf.h>
 #include <AK/Array.h>
 #include <AK/GenericLexer.h>
 #include <AK/Optional.h>
@@ -35,6 +37,160 @@
 #    include <stdio.h>
 #endif
 
+#ifndef DBGLN_NO_COMPILETIME_FORMAT_CHECK
+// Note: Clang 12 adds support for CTAD, this would fail with any version prior to that.
+#    if defined(__clang__) && __clang_major__ < 12
+#        define DBGLN_NO_COMPILETIME_FORMAT_CHECK
+#    endif
+#endif
+
+#ifndef DBGLN_NO_COMPILETIME_FORMAT_CHECK
+namespace {
+
+template<size_t N>
+consteval auto extract_used_argument_index(const char (&fmt)[N], size_t specifier_start_index, size_t specifier_end_index, size_t& next_implicit_argument_index)
+{
+    struct {
+        size_t index_value { 0 };
+        bool saw_explicit_index { false };
+    } state;
+    for (size_t i = specifier_start_index; i < specifier_end_index; ++i) {
+        auto c = fmt[i];
+        if (c > '9' || c < '0')
+            break;
+
+        state.index_value *= 10;
+        state.index_value += c - '0';
+        state.saw_explicit_index = true;
+    }
+
+    if (!state.saw_explicit_index)
+        return next_implicit_argument_index++;
+
+    return state.index_value;
+}
+
+// FIXME: We should rather parse these format strings at compile-time if possible.
+template<size_t N>
+consteval auto count_fmt_params(const char (&fmt)[N])
+{
+    struct {
+        // FIXME: Switch to variable-sized storage whenever we can come up with one :)
+        Array<size_t, 128> used_arguments { 0 };
+        size_t total_used_argument_count { 0 };
+        size_t next_implicit_argument_index { 0 };
+        bool has_explicit_argument_references { false };
+
+        size_t unclosed_braces { 0 };
+        size_t extra_closed_braces { 0 };
+
+        Array<size_t, 4> last_format_specifier_start { 0 };
+        size_t total_used_last_format_specifier_start_count { 0 };
+
+        StringLiteral<128> internal_error { { 0 } };
+    } result;
+
+    for (size_t i = 0; i < N; ++i) {
+        auto ch = fmt[i];
+        switch (ch) {
+        case '{':
+            if (i + 1 < N && fmt[i + 1] == '{') {
+                ++i;
+                continue;
+            }
+
+            // Note: There's no compile-time throw, so we have to abuse a compile-time string to store errors.
+            if (result.total_used_last_format_specifier_start_count >= result.last_format_specifier_start.size() - 1)
+                result.internal_error = "Format-String Checker internal error: Format specifier nested too deep";
+
+            result.last_format_specifier_start[result.total_used_last_format_specifier_start_count++] = i + 1;
+
+            ++result.unclosed_braces;
+            break;
+        case '}':
+            if (i + 1 < N && fmt[i + 1] == '}') {
+                ++i;
+                continue;
+            }
+            if (result.unclosed_braces) {
+                --result.unclosed_braces;
+
+                if (result.total_used_last_format_specifier_start_count == 0)
+                    result.internal_error = "Format-String Checker internal error: Expected location information";
+
+                const auto specifier_start_index = result.last_format_specifier_start[--result.total_used_last_format_specifier_start_count];
+
+                if (result.total_used_argument_count >= result.used_arguments.size())
+                    result.internal_error = "Format-String Checker internal error: Too many format arguments in format string";
+
+                auto used_argument_index = extract_used_argument_index<N>(fmt, specifier_start_index, i, result.next_implicit_argument_index);
+                if (used_argument_index + 1 != result.next_implicit_argument_index)
+                    result.has_explicit_argument_references = true;
+                result.used_arguments[result.total_used_argument_count++] = used_argument_index;
+
+            } else {
+                ++result.extra_closed_braces;
+            }
+            break;
+        default:
+            continue;
+        }
+    }
+    return result;
+}
+}
+
+template<size_t N, StringLiteral<N> fmt, size_t param_count, auto check = count_fmt_params<N>(fmt.data)>
+constexpr bool check_format_parameter_consistency()
+{
+    static_assert(check.internal_error.data[0] == 0, "Some internal error occured, try looking at the check function type for the error");
+    static_assert(check.unclosed_braces == 0, "Extra unclosed braces in format string");
+    static_assert(check.extra_closed_braces == 0, "Extra closing braces in format string");
+
+    {
+        constexpr auto begin = check.used_arguments.begin();
+        constexpr auto end = check.used_arguments.begin() + check.total_used_argument_count;
+        constexpr auto has_all_referenced_arguments = !AK::any_of(begin, end, [](auto& entry) { return entry >= param_count; });
+        static_assert(has_all_referenced_arguments, "Format string references nonexistent parameter");
+    }
+
+    if constexpr (!check.has_explicit_argument_references)
+        static_assert(check.total_used_argument_count == param_count, "Format string does not reference all passed parameters");
+
+    // Ensure that no passed parameter is ignored or otherwise not referenced in the format
+    // As this check is generally pretty expensive, try to avoid it where it cannot fail.
+    // We will only do this check if the format string has explicit argument refs
+    // otherwise, the check above covers this check too, as implicit refs
+    // monotonically increase, and cannot have 'gaps'.
+    if constexpr (check.has_explicit_argument_references) {
+        constexpr auto all_parameters = iota_array<size_t, param_count>(0);
+        auto contains = [](auto begin, auto end, auto entry) {
+            for (; begin != end; begin++) {
+                if (*begin == entry)
+                    return true;
+            }
+
+            return false;
+        };
+        constexpr auto references_all_arguments = AK::all_of(
+            all_parameters.begin(),
+            all_parameters.end(),
+            [&](auto& entry) {
+                return contains(
+                    check.used_arguments.begin(),
+                    check.used_arguments.begin() + check.total_used_argument_count,
+                    entry);
+            });
+        static_assert(references_all_arguments, "Format string does not reference all passed parameters");
+    }
+
+    return true;
+}
+
+template<auto fmt, auto param_count>
+concept ConsistentFormatParameters = check_format_parameter_consistency<fmt.size, fmt, param_count>();
+#endif
+
 namespace AK {
 
 class TypeErasedFormatParams;
@@ -392,6 +548,14 @@ inline void warnln() { outln(stderr); }
 
 void vdbgln(StringView fmtstr, TypeErasedFormatParams);
 
+#ifndef DBGLN_NO_COMPILETIME_FORMAT_CHECK
+template<StringLiteral fmt, bool enabled = true, typename... Parameters>
+void dbgln(const Parameters&... parameters) requires ConsistentFormatParameters<fmt, sizeof...(Parameters)>
+{
+    dbgln<enabled>(StringView { fmt.data }, parameters...);
+}
+#endif
+
 template<bool enabled = true, typename... Parameters>
 void dbgln(StringView fmtstr, const Parameters&... parameters)
 {
@@ -400,6 +564,7 @@ void dbgln(StringView fmtstr, const Parameters&... parameters)
 }
 template<bool enabled = true, typename... Parameters>
 void dbgln(const char* fmtstr, const Parameters&... parameters) { dbgln<enabled>(StringView { fmtstr }, parameters...); }
+
 template<bool enabled = true>
 void dbgln() { dbgln<enabled>(""); }
 
@@ -484,4 +649,10 @@ using AK::dbgln;
 using AK::FormatIfSupported;
 using AK::FormatString;
 
-#define dbgln_if(flag, format, ...) dbgln<flag>(format, ##__VA_ARGS__)
+#ifdef DBGLN_NO_COMPILETIME_FORMAT_CHECK
+#    define dbgln(fmt, ...) dbgln(fmt, ##__VA_ARGS__)
+#    define dbgln_if(flag, fmt, ...) dbgln<flag>(fmt, ##__VA_ARGS__)
+#else
+#    define dbgln(fmt, ...) dbgln<fmt>(__VA_ARGS__)
+#    define dbgln_if(flag, fmt, ...) dbgln<fmt, flag>(__VA_ARGS__)
+#endif