Import Tint changes from Dawn

Changes:
  - 0fa7bb62b1daf3bc32e3423b716333be591fc0d8 [tint][utils] Support ANSI 256 colors by Ben Clayton <bclayton@google.com>
  - 082e40192ceb805963ddd5d6ce47041357465224 Fix clang-tidy warnings by David Neto <dneto@google.com>
GitOrigin-RevId: 0fa7bb62b1daf3bc32e3423b716333be591fc0d8
Change-Id: Ic06cd1eb2e03b1e14ab0cf4590abfb0693af3618
Reviewed-on: https://dawn-review.googlesource.com/c/tint/+/177861
Kokoro: Kokoro <noreply+kokoro@google.com>
Commit-Queue: Ben Clayton <bclayton@google.com>
Reviewed-by: Ben Clayton <bclayton@google.com>
diff --git a/src/tint/cmd/tint/main.cc b/src/tint/cmd/tint/main.cc
index 5a11673..06f2ef0 100644
--- a/src/tint/cmd/tint/main.cc
+++ b/src/tint/cmd/tint/main.cc
@@ -63,6 +63,7 @@
 #include "src/tint/utils/text/string_stream.h"
 #include "src/tint/utils/text/styled_text.h"
 #include "src/tint/utils/text/styled_text_printer.h"
+#include "src/tint/utils/text/styled_text_theme.h"
 
 #if TINT_BUILD_WGSL_READER
 #include "src/tint/lang/wgsl/reader/program_to_ir/program_to_ir.h"
diff --git a/src/tint/lang/wgsl/ast/transform/array_length_from_uniform.cc b/src/tint/lang/wgsl/ast/transform/array_length_from_uniform.cc
index e307e25..1cb8c08 100644
--- a/src/tint/lang/wgsl/ast/transform/array_length_from_uniform.cc
+++ b/src/tint/lang/wgsl/ast/transform/array_length_from_uniform.cc
@@ -27,6 +27,7 @@
 
 #include "src/tint/lang/wgsl/ast/transform/array_length_from_uniform.h"
 
+#include <cstdint>
 #include <memory>
 #include <string>
 #include <string_view>
diff --git a/src/tint/utils/system/BUILD.bazel b/src/tint/utils/system/BUILD.bazel
index 1cac5ca..4c739e3 100644
--- a/src/tint/utils/system/BUILD.bazel
+++ b/src/tint/utils/system/BUILD.bazel
@@ -66,7 +66,13 @@
     "terminal.h",
   ],
   deps = [
+    "//src/tint/utils/containers",
+    "//src/tint/utils/ice",
     "//src/tint/utils/macros",
+    "//src/tint/utils/math",
+    "//src/tint/utils/memory",
+    "//src/tint/utils/rtti",
+    "//src/tint/utils/traits",
   ],
   copts = COPTS,
   visibility = ["//visibility:public"],
diff --git a/src/tint/utils/system/BUILD.cmake b/src/tint/utils/system/BUILD.cmake
index 748da7d..f9b377f 100644
--- a/src/tint/utils/system/BUILD.cmake
+++ b/src/tint/utils/system/BUILD.cmake
@@ -44,7 +44,13 @@
 )
 
 tint_target_add_dependencies(tint_utils_system lib
+  tint_utils_containers
+  tint_utils_ice
   tint_utils_macros
+  tint_utils_math
+  tint_utils_memory
+  tint_utils_rtti
+  tint_utils_traits
 )
 
 if((NOT TINT_BUILD_IS_LINUX) AND (NOT TINT_BUILD_IS_MAC) AND (NOT TINT_BUILD_IS_WIN))
diff --git a/src/tint/utils/system/BUILD.gn b/src/tint/utils/system/BUILD.gn
index 5f101c1..285aa06 100644
--- a/src/tint/utils/system/BUILD.gn
+++ b/src/tint/utils/system/BUILD.gn
@@ -43,7 +43,15 @@
     "env.h",
     "terminal.h",
   ]
-  deps = [ "${tint_src_dir}/utils/macros" ]
+  deps = [
+    "${tint_src_dir}/utils/containers",
+    "${tint_src_dir}/utils/ice",
+    "${tint_src_dir}/utils/macros",
+    "${tint_src_dir}/utils/math",
+    "${tint_src_dir}/utils/memory",
+    "${tint_src_dir}/utils/rtti",
+    "${tint_src_dir}/utils/traits",
+  ]
 
   if (!tint_build_is_linux && !tint_build_is_mac && !tint_build_is_win) {
     sources += [ "terminal_other.cc" ]
diff --git a/src/tint/utils/system/terminal_posix.cc b/src/tint/utils/system/terminal_posix.cc
index 699966d..fb2d93f 100644
--- a/src/tint/utils/system/terminal_posix.cc
+++ b/src/tint/utils/system/terminal_posix.cc
@@ -38,30 +38,15 @@
 #include <string_view>
 #include <utility>
 
+#include "src/tint/utils/containers/vector.h"
 #include "src/tint/utils/macros/defer.h"
 #include "src/tint/utils/system/env.h"
 #include "src/tint/utils/system/terminal.h"
 
 namespace tint {
+namespace {
 
-bool TerminalSupportsColors(FILE* f) {
-    if (!isatty(fileno(f))) {
-        return false;
-    }
-
-    if (auto term = GetEnvVar("TERM"); !term.empty()) {
-        return term == "cygwin" || term == "linux" || term == "rxvt-unicode-256color" ||
-               term == "rxvt-unicode" || term == "screen-256color" || term == "screen" ||
-               term == "tmux-256color" || term == "tmux" || term == "xterm-256color" ||
-               term == "xterm-color" || term == "xterm";
-    }
-
-    return false;
-}
-
-/// Probes the terminal using a Device Control escape sequence to get the background color.
-/// @see https://invisible-island.net/xterm/ctlseqs/ctlseqs.html#h2-Device-Control-functions
-std::optional<bool> TerminalIsDark(FILE* out) {
+std::optional<bool> TerminalIsDarkImpl(FILE* out) {
     if (!TerminalSupportsColors(out)) {
         return std::nullopt;
     }
@@ -83,23 +68,20 @@
     tcsetattr(out_fd, TCSADRAIN, &state);
 
     // Emit the device control escape sequence to query the terminal colors.
-    static constexpr std::string_view kQuery = "\x1b]11;?\x07";
+    static constexpr std::string_view kQuery = "\033]11;?\033\\";
     fwrite(kQuery.data(), 1, kQuery.length(), out);
-    fflush(out);
 
     // Timeout for attempting to read the response.
-    static constexpr auto kTimeout = std::chrono::milliseconds(100);
+    static constexpr auto kTimeout = std::chrono::milliseconds(300);
 
     // Record the start time.
     auto start = std::chrono::steady_clock::now();
 
     // Helpers for parsing the response.
-    std::optional<char> peek;
+    Vector<char, 8> peek;
     auto read = [&]() -> std::optional<char> {
-        if (peek) {
-            char c = *peek;
-            peek.reset();
-            return c;
+        if (!peek.IsEmpty()) {
+            return peek.Pop();
         }
         while ((std::chrono::steady_clock::now() - start) < kTimeout) {
             char c;
@@ -111,8 +93,15 @@
     };
 
     auto match = [&](std::string_view str) {
-        for (char c : str) {
-            if (c != read()) {
+        for (size_t i = 0; i < str.length(); i++) {
+            auto c = read();
+            if (c != str[i]) {
+                if (c) {
+                    peek.Push(*c);
+                }
+                while (i != 0) {
+                    peek.Push(str[--i]);
+                }
                 return false;
             }
         }
@@ -137,7 +126,7 @@
                 num = num * 16 + 10 + static_cast<uint32_t>(*c - 'A');
                 len++;
             } else {
-                peek = c;
+                peek.Push(*c);
                 break;
             }
         }
@@ -174,6 +163,10 @@
             return std::nullopt;
     }
 
+    if (!match("\x07") && !match("\x1b\x5c")) {
+        return std::nullopt;
+    }
+
     // https://en.wikipedia.org/wiki/Relative_luminance
     float r = static_cast<float>(r_i.num) / static_cast<float>(max);
     float g = static_cast<float>(g_i.num) / static_cast<float>(max);
@@ -181,4 +174,28 @@
     return (0.2126f * r + 0.7152f * g + 0.0722f * b) < 0.5f;
 }
 
+}  // namespace
+
+bool TerminalSupportsColors(FILE* f) {
+    if (!isatty(fileno(f))) {
+        return false;
+    }
+
+    if (auto term = GetEnvVar("TERM"); !term.empty()) {
+        return term == "cygwin" || term == "linux" || term == "rxvt-unicode-256color" ||
+               term == "rxvt-unicode" || term == "screen-256color" || term == "screen" ||
+               term == "tmux-256color" || term == "tmux" || term == "xterm-256color" ||
+               term == "xterm-color" || term == "xterm";
+    }
+
+    return false;
+}
+
+/// Probes the terminal using a Device Control escape sequence to get the background color.
+/// @see https://invisible-island.net/xterm/ctlseqs/ctlseqs.html#h2-Device-Control-functions
+std::optional<bool> TerminalIsDark(FILE* out) {
+    static std::optional<bool> result = TerminalIsDarkImpl(out);
+    return result;
+}
+
 }  // namespace tint
diff --git a/src/tint/utils/text/styled_text_printer.h b/src/tint/utils/text/styled_text_printer.h
index 468d906..a224537 100644
--- a/src/tint/utils/text/styled_text_printer.h
+++ b/src/tint/utils/text/styled_text_printer.h
@@ -57,10 +57,18 @@
     /// @param out the file to print to.
     static std::unique_ptr<StyledTextPrinter> CreatePlain(FILE* out);
 
+    /// Enumerator of ANSI terminal color support.
+    enum class ANSIColors {
+        k8Bit,   // Palette of 256 colors 'xterm-256color'
+        k24Bit,  // 8-bit per [R,G,B]
+    };
+
     /// @returns a Printer that uses ANSI escape sequences and theme @p theme.
     /// @param out the file to print to.
     /// @param theme the custom theme to use.
-    static std::unique_ptr<StyledTextPrinter> CreateANSI(FILE* out, const StyledTextTheme& theme);
+    static std::unique_ptr<StyledTextPrinter> CreateANSI(FILE* out,
+                                                         const StyledTextTheme& theme,
+                                                         ANSIColors colors);
 
     /// Destructor
     virtual ~StyledTextPrinter();
diff --git a/src/tint/utils/text/styled_text_printer_ansi.cc b/src/tint/utils/text/styled_text_printer_ansi.cc
index 8a6f39c..22e30ef 100644
--- a/src/tint/utils/text/styled_text_printer_ansi.cc
+++ b/src/tint/utils/text/styled_text_printer_ansi.cc
@@ -25,8 +25,10 @@
 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
+#include <array>
 #include <cstring>
 
+#include "src/tint/utils/containers/hashmap.h"
 #include "src/tint/utils/text/styled_text.h"
 #include "src/tint/utils/text/styled_text_printer.h"
 #include "src/tint/utils/text/styled_text_theme.h"
@@ -48,9 +50,9 @@
 
 #define ESCAPE "\u001b"
 
-class Printer : public StyledTextPrinter {
+class Printer24Bit : public StyledTextPrinter {
   public:
-    Printer(FILE* f, const StyledTextTheme& t) : file_(f), theme_(t) {}
+    Printer24Bit(FILE* f, const StyledTextTheme& t) : file_(f), theme_(t) {}
 
     void Print(const StyledText& style_text) override {
         StyledTextTheme::Attributes current;
@@ -106,11 +108,129 @@
     const StyledTextTheme& theme_;
 };
 
+class Printer8Bit : public StyledTextPrinter {
+  public:
+    static constexpr std::array<uint32_t, 256> kPalette = {
+        0x000000, 0x800000, 0x008000, 0x808000, 0x000080, 0x800080, 0x008080, 0xc0c0c0, 0x808080,
+        0xff0000, 0x00ff00, 0xffff00, 0x0000ff, 0xff00ff, 0x00ffff, 0xffffff, 0x000000, 0x00005f,
+        0x000087, 0x0000af, 0x0000d7, 0x0000ff, 0x005f00, 0x005f5f, 0x005f87, 0x005faf, 0x005fd7,
+        0x005fff, 0x008700, 0x00875f, 0x008787, 0x0087af, 0x0087d7, 0x0087ff, 0x00af00, 0x00af5f,
+        0x00af87, 0x00afaf, 0x00afd7, 0x00afff, 0x00d700, 0x00d75f, 0x00d787, 0x00d7af, 0x00d7d7,
+        0x00d7ff, 0x00ff00, 0x00ff5f, 0x00ff87, 0x00ffaf, 0x00ffd7, 0x00ffff, 0x5f0000, 0x5f005f,
+        0x5f0087, 0x5f00af, 0x5f00d7, 0x5f00ff, 0x5f5f00, 0x5f5f5f, 0x5f5f87, 0x5f5faf, 0x5f5fd7,
+        0x5f5fff, 0x5f8700, 0x5f875f, 0x5f8787, 0x5f87af, 0x5f87d7, 0x5f87ff, 0x5faf00, 0x5faf5f,
+        0x5faf87, 0x5fafaf, 0x5fafd7, 0x5fafff, 0x5fd700, 0x5fd75f, 0x5fd787, 0x5fd7af, 0x5fd7d7,
+        0x5fd7ff, 0x5fff00, 0x5fff5f, 0x5fff87, 0x5fffaf, 0x5fffd7, 0x5fffff, 0x870000, 0x87005f,
+        0x870087, 0x8700af, 0x8700d7, 0x8700ff, 0x875f00, 0x875f5f, 0x875f87, 0x875faf, 0x875fd7,
+        0x875fff, 0x878700, 0x87875f, 0x878787, 0x8787af, 0x8787d7, 0x8787ff, 0x87af00, 0x87af5f,
+        0x87af87, 0x87afaf, 0x87afd7, 0x87afff, 0x87d700, 0x87d75f, 0x87d787, 0x87d7af, 0x87d7d7,
+        0x87d7ff, 0x87ff00, 0x87ff5f, 0x87ff87, 0x87ffaf, 0x87ffd7, 0x87ffff, 0xaf0000, 0xaf005f,
+        0xaf0087, 0xaf00af, 0xaf00d7, 0xaf00ff, 0xaf5f00, 0xaf5f5f, 0xaf5f87, 0xaf5faf, 0xaf5fd7,
+        0xaf5fff, 0xaf8700, 0xaf875f, 0xaf8787, 0xaf87af, 0xaf87d7, 0xaf87ff, 0xafaf00, 0xafaf5f,
+        0xafaf87, 0xafafaf, 0xafafd7, 0xafafff, 0xafd700, 0xafd75f, 0xafd787, 0xafd7af, 0xafd7d7,
+        0xafd7ff, 0xafff00, 0xafff5f, 0xafff87, 0xafffaf, 0xafffd7, 0xafffff, 0xd70000, 0xd7005f,
+        0xd70087, 0xd700af, 0xd700d7, 0xd700ff, 0xd75f00, 0xd75f5f, 0xd75f87, 0xd75faf, 0xd75fd7,
+        0xd75fff, 0xd78700, 0xd7875f, 0xd78787, 0xd787af, 0xd787d7, 0xd787ff, 0xd7af00, 0xd7af5f,
+        0xd7af87, 0xd7afaf, 0xd7afd7, 0xd7afff, 0xd7d700, 0xd7d75f, 0xd7d787, 0xd7d7af, 0xd7d7d7,
+        0xd7d7ff, 0xd7ff00, 0xd7ff5f, 0xd7ff87, 0xd7ffaf, 0xd7ffd7, 0xd7ffff, 0xff0000, 0xff005f,
+        0xff0087, 0xff00af, 0xff00d7, 0xff00ff, 0xff5f00, 0xff5f5f, 0xff5f87, 0xff5faf, 0xff5fd7,
+        0xff5fff, 0xff8700, 0xff875f, 0xff8787, 0xff87af, 0xff87d7, 0xff87ff, 0xffaf00, 0xffaf5f,
+        0xffaf87, 0xffafaf, 0xffafd7, 0xffafff, 0xffd700, 0xffd75f, 0xffd787, 0xffd7af, 0xffd7d7,
+        0xffd7ff, 0xffff00, 0xffff5f, 0xffff87, 0xffffaf, 0xffffd7, 0xffffff, 0x080808, 0x121212,
+        0x1c1c1c, 0x262626, 0x303030, 0x3a3a3a, 0x444444, 0x4e4e4e, 0x585858, 0x606060, 0x666666,
+        0x767676, 0x808080, 0x8a8a8a, 0x949494, 0x9e9e9e, 0xa8a8a8, 0xb2b2b2, 0xbcbcbc, 0xc6c6c6,
+        0xd0d0d0, 0xdadada, 0xe4e4e4, 0xeeeeee,
+    };
+
+    Printer8Bit(FILE* f, const StyledTextTheme& t) : file_(f), theme_(t) {}
+
+    void Print(const StyledText& style_text) override {
+        StyledTextTheme::Attributes current;
+
+        style_text.Walk([&](std::string_view text, TextStyle text_style) {
+            auto style = theme_.Get(text_style);
+            if (!Equal(current.foreground, style.foreground)) {
+                current.foreground = style.foreground;
+                if (current.foreground.has_value()) {
+                    uint8_t color = Quantize(*style.foreground);
+                    fprintf(file_, ESCAPE "[38;5;%dm", static_cast<int>(color));
+                } else {
+                    fprintf(file_, ESCAPE "[39m");
+                }
+            }
+            if (!Equal(current.background, style.background)) {
+                current.background = style.background;
+                if (current.background.has_value()) {
+                    uint8_t color = Quantize(*style.background);
+                    fprintf(file_, ESCAPE "[48;5;%dm", static_cast<int>(color));
+                } else {
+                    fprintf(file_, ESCAPE "[49m");
+                }
+            }
+            if (!Equal(current.underlined, style.underlined)) {
+                current.underlined = style.underlined;
+                if (current.underlined == true) {
+                    fprintf(file_, ESCAPE "[4m");
+                } else {
+                    fprintf(file_, ESCAPE "[24m");
+                }
+            }
+            if (!Equal(current.bold, style.bold)) {
+                current.bold = style.bold;
+                if (current.bold == true) {
+                    fprintf(file_, ESCAPE "[1m");
+                } else {
+                    fprintf(file_, ESCAPE "[22m");
+                }
+            }
+            fwrite(text.data(), 1, text.size(), file_);
+        });
+        fprintf(file_, ESCAPE "[m");
+        fflush(file_);
+    }
+
+  private:
+    uint8_t Quantize(const StyledTextTheme::Color& color) {
+        return colors_.GetOrAdd(color, [&] {
+            uint8_t best_color = 0;
+            int best_score = std::numeric_limits<int>::max();
+            for (size_t i = 0; i < 256; i++) {
+                int r = static_cast<int>((kPalette[i] >> 16) & 0xff);
+                int g = static_cast<int>((kPalette[i] >> 8) & 0xff);
+                int b = static_cast<int>((kPalette[i] >> 0) & 0xff);
+                int diff = std::abs(r - static_cast<int>(color.r)) +
+                           std::abs(g - static_cast<int>(color.g)) +
+                           std::abs(b - static_cast<int>(color.b));
+                if (diff == 0) {
+                    return static_cast<uint8_t>(i);
+                }
+                if (diff < best_score) {
+                    best_score = diff;
+                    best_color = static_cast<uint8_t>(i);
+                }
+            }
+            return best_color;
+        });
+    }
+
+    FILE* const file_;
+    const StyledTextTheme& theme_;
+    Hashmap<StyledTextTheme::Color, uint8_t, 16> colors_;
+};
 }  // namespace
 
 std::unique_ptr<StyledTextPrinter> StyledTextPrinter::CreateANSI(FILE* out,
-                                                                 const StyledTextTheme& theme) {
-    return std::make_unique<Printer>(out, theme);
+                                                                 const StyledTextTheme& theme,
+                                                                 ANSIColors colors) {
+    switch (colors) {
+        case ANSIColors::k24Bit:
+            return std::make_unique<Printer24Bit>(out, theme);
+        case ANSIColors::k8Bit:
+            return std::make_unique<Printer8Bit>(out, theme);
+    }
+
+    // Should be unreachable.
+    return std::make_unique<Printer8Bit>(out, theme);
 }
 
 }  // namespace tint
diff --git a/src/tint/utils/text/styled_text_printer_posix.cc b/src/tint/utils/text/styled_text_printer_posix.cc
index 7d34fed..8a9ede9 100644
--- a/src/tint/utils/text/styled_text_printer_posix.cc
+++ b/src/tint/utils/text/styled_text_printer_posix.cc
@@ -30,6 +30,7 @@
 #include <unistd.h>
 #include <memory>
 
+#include "src/tint/utils/system/env.h"
 #include "src/tint/utils/system/terminal.h"
 #include "src/tint/utils/text/styled_text_printer.h"
 
@@ -38,7 +39,8 @@
 std::unique_ptr<StyledTextPrinter> StyledTextPrinter::Create(FILE* out,
                                                              const StyledTextTheme& theme) {
     if (TerminalSupportsColors(out)) {
-        return CreateANSI(out, theme);
+        bool true_color = GetEnvVar("COLORTERM") == "truecolor";
+        return CreateANSI(out, theme, true_color ? ANSIColors::k24Bit : ANSIColors::k8Bit);
     }
     return CreatePlain(out);
 }
diff --git a/src/tint/utils/text/styled_text_printer_windows.cc b/src/tint/utils/text/styled_text_printer_windows.cc
index ee9373b..86099a0 100644
--- a/src/tint/utils/text/styled_text_printer_windows.cc
+++ b/src/tint/utils/text/styled_text_printer_windows.cc
@@ -61,7 +61,7 @@
     if (HANDLE handle = ConsoleHandleFrom(out); handle != INVALID_HANDLE_VALUE) {
         SetConsoleOutputCP(CP_UTF8);
         if (SetConsoleMode(handle, ENABLE_PROCESSED_OUTPUT | ENABLE_VIRTUAL_TERMINAL_PROCESSING)) {
-            return CreateANSI(out, theme);
+            return CreateANSI(out, theme, ANSIColors::k24Bit);
         }
     }
     return CreatePlain(out);
diff --git a/src/tint/utils/text/styled_text_theme.h b/src/tint/utils/text/styled_text_theme.h
index b36db4f..c083dd1 100644
--- a/src/tint/utils/text/styled_text_theme.h
+++ b/src/tint/utils/text/styled_text_theme.h
@@ -31,6 +31,8 @@
 #include <stdint.h>
 #include <optional>
 
+#include "src/tint/utils/math/hash.h"
+
 /// Forward declarations
 namespace tint {
 class TextStyle;
@@ -55,6 +57,8 @@
         bool operator==(const Color& other) const {
             return r == other.r && g == other.g && b == other.b;
         }
+        /// @returns a hash code of this Color
+        tint::HashCode HashCode() const { return Hash(r, g, b); }
     };
 
     /// Attributes holds a number of optional attributes for a style of text.