[libc][NFC] add index mode to printf parser

[michaelrj]

Summary

This patch is a followup to the previous patch which implemented the
main printf parsing logic as well as sequential mode. This patch adds
index mode.

[sivachandra]

Few nits inline, but can you add tests so that I understand how the new API is to be used and then I might have more comments.

libc/src/stdio/printf_core/parser.h

27

Nit: Add a comment explain the difference between args_start vs args_cur. I think the naming is indicative enough, but would be nice if you can also add a note.

32

Nit: Move FLOAT_MASK below line 37 and add a comment explaining what it is.

47

Use inline_memset instead of this?

[michaelrj]

add unit tests and fix some problems that were exposed by those tests.

[michaelrj]

fix a minor bug and add a comprehensive test to hopefully prevent future issues.

[michaelrj]

clarify the type representations

[sivachandra]

I have not yet gone through the tests.

libc/src/stdio/printf_core/parser.cpp

380

Nit: s/cur_size/cur_type_desc ?

libc/src/stdio/printf_core/parser.h

30

Nit: Call it PrimaryType may be? The word super can be misleading because of other concepts like super classes.

34

Nit: Normally, things like this are named TypeDesc as a short for "type descriptor".

48

Nit: This is not an array of sizes anymore.

94

Looks like you can use a constexpr variable template instead of these functions?

125

Nit: s/set_size_arr/set_type_desc/ ?

152

Update the comment appropriately?

153

Nit: s/size_of_index/get_type_desc/ ?

[michaelrj]

address comments, rename internal type representation to TypeDesc

[sivachandra]

libc/src/stdio/printf_core/parser.h

106

Nit: set_type_desc to match get_type_desc below?

127

Update this comment with info about why this function exists. IIUC, it is adjusting to the current index in the varargs?

[michaelrj]

address final comments

libc/src/stdio/printf_core/parser.h

 
 namespace __llvm_libc {
 namespace printf_core {
 
 class Parser {
   const char *__restrict str;
 
   size_t cur_pos = 0;
+  internal::ArgList args_cur;
 
+#ifndef LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
   internal::ArgList args_start;
-  internal::ArgList args_cur;
   size_t args_index = 1;
 
+  // TODO: Make this a compile option.
+  static constexpr size_t SIZE_ARR_LEN = 32;
+  static constexpr uint8_t FLOAT_MASK = 0x80;
+  // size_arr stores the sizes of the variables in the ArgList. This is used in
+  // index mode to reduce repeated string parsing. The sizes are stored as
+  // sizeof(type), except for floating point types which are stored as
+  // sizeof(type) | FLOAT_MASK.
+  uint8_t size_arr[SIZE_ARR_LEN];
+
   // TODO: Look into object stores for optimization.
 
+#endif // LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
+
 public:
+#ifndef LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
+  Parser(const char *__restrict new_str, internal::ArgList &args)
+      : str(new_str), args_cur(args), args_start(args) {
+    for (size_t i = 0; i < SIZE_ARR_LEN; ++i)
+      size_arr[i] = 0;
+  }
+#else
   Parser(const char *__restrict new_str, internal::ArgList &args)
-      : str(new_str), args_start(args), args_cur(args) {}
+      : str(new_str), args_cur(args) {}
+#endif // LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
 
   // get_next_section will parse the format string until it has a fully
   // specified format section. This can either be a raw format section with no
   // conversion, or a format section with a conversion that has all of its
   // variables stored in the format section.
   FormatSection get_next_section();
 
 private:
   // parse_flags parses the flags inside a format string. It assumes that
   // str[*local_pos] is inside a format specifier, and parses any flags it
   // finds. It returns a FormatFlags object containing the set of found flags
   // arithmetically or'd together. local_pos will be moved past any flags found.
   FormatFlags parse_flags(size_t *local_pos);
 
   // parse_length_modifier parses the length modifier inside a format string. It
   // assumes that str[*local_pos] is inside a format specifier. It returns a
   // LengthModifier with the length modifier it found. It will advance local_pos
   // after the format specifier if one is found.
   LengthModifier parse_length_modifier(size_t *local_pos);
 
   // get_next_arg_value gets the next value from the arg list as type T.
   template <class T> T inline get_next_arg_value() {
-    ++args_index;
     return args_cur.next_var<T>();
   }
+
+  //----------------------------------------------------
+  // INDEX MODE ONLY FUNCTIONS AFTER HERE:
+  //----------------------------------------------------
+
+#ifndef LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
+
+  // parse_index parses the index of a value inside a format string. It
+  // assumes that str[*local_pos] points to character after a '%' or '*', and
+  // returns 0 if there is no closing $, or if it finds no number. If it finds a
+  // number, it will move local_pos past the end of the $, else it will not move
+  // local_pos.
+  size_t parse_index(size_t *local_pos);
+
+  // These functions are used to get the size of argument types while also
+  // adding the float mask for floating point types.
+  template <class T> static constexpr uint8_t inline get_arg_size() {
+    return sizeof(T);
+  }
+  template <> uint8_t inline get_arg_size<double>() {
+    return sizeof(double) | FLOAT_MASK;
+  }
+  template <> uint8_t inline get_arg_size<long double>() {
+    return sizeof(long double) | FLOAT_MASK;
+  }
+
+  void inline set_size_arr(size_t index, uint8_t value) {
+    if (index != 0 && index <= SIZE_ARR_LEN)
+      size_arr[index - 1] = value;
+  }
+
+  // get_arg_value gets the value from the arg list at index (starting at 1).
+  // This may require parsing the format string. An index of 0 is interpreted as
+  // the next value.
+  template <class T> T inline get_arg_value(size_t index) {
+    if (!(index == 0 || index == args_index))
+      args_to_index(index);
+
+    set_size_arr(index, get_arg_size<T>());
+
+    ++args_index;
+    return get_next_arg_value<T>();
+  }
+
+  // args_to_index assumes that this format string uses index mode. It moves
+  // args_index to index. If index is less than args_index, it will first move
+  // args_cur back to args_start and reset args_index to 1. Once index is
+  // greater than args_index, it will iterate through
+  void args_to_index(size_t index);
+
+  // size_of_index assumes that this format string uses index mode. It iterates
+  // through the format string until it finds the size of the conversion
+  // variable for index. If no appropriate format specifier is found, it
+  // returns 32.
+  uint8_t size_of_index(size_t index);
+
+#endif // LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
 };
 
 } // namespace printf_core
 } // namespace __llvm_libc
 
 #endif // LLVM_LIBC_SRC_STDIO_PRINTF_CORE_PARSER_H

libc/src/stdio/printf_core/parser.cpp

 //===-- Format string parser implementation for printf ----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
+// #define LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE 1 // This will be a compile flag.
+
 #include "parser.h"
 
 #include "src/__support/arg_list.h"
 
 #include "src/__support/CPP/Bit.h"
 #include "src/__support/ctype_utils.h"
 #include "src/__support/str_to_integer.h"
 
 namespace __llvm_libc {
 namespace printf_core {
 
-#define LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE 1 // This will be a compile flag.
-
 #ifndef LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
 #define GET_ARG_VAL_SIMPLEST(arg_type, index) get_arg_value<arg_type>(index)
 #else
 #define GET_ARG_VAL_SIMPLEST(arg_type, _) get_next_arg_value<arg_type>()
 #endif // LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
 
 FormatSection Parser::get_next_section() {
   FormatSection section;
   section.raw_string = str + cur_pos;
   size_t starting_pos = cur_pos;
   if (str[cur_pos] == '%') {
     // format section
     section.has_conv = true;
 
     ++cur_pos;
     [[maybe_unused]] size_t conv_index = 0;
 
+#ifndef LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
+    conv_index = parse_index(&cur_pos);
+#endif // LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
+
     section.flags = parse_flags(&cur_pos);
 
     // handle width
     section.min_width = 0;
     if (str[cur_pos] == '*') {
       ++cur_pos;
 
       section.min_width = GET_ARG_VAL_SIMPLEST(int, parse_index(&cur_pos));
LengthModifier Parser::parse_length_modifier(size_t *local_pos) {
   case ('t'):
     ++*local_pos;
     return LengthModifier::t;
   default:
     return LengthModifier::none;
   }
 }
 
+//----------------------------------------------------
+// INDEX MODE ONLY FUNCTIONS AFTER HERE:
+//----------------------------------------------------
+
+#ifndef LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
+
+size_t Parser::parse_index(size_t *local_pos) {
+  if (internal::isdigit(str[*local_pos])) {
+    char *int_end;
+    size_t index = internal::strtointeger<size_t>(str + cur_pos, &int_end, 10);
+    if (int_end[0] != '$')
+      return 0;
+    *local_pos = 1 + int_end - str;
+    return index;
+  }
+  return 0;
+}
+
+uint8_t Parser::size_of_index(size_t index) {
+  // index mode is assumed, and the indicies start at 1, so an index
+  // of 0 is invalid.
+  size_t local_pos = 0;
+
+  while (str[local_pos]) {
+    if (str[local_pos] == '%') {
+      ++local_pos;
+
+      size_t conv_index = parse_index(&local_pos);
+
+      // the flags aren't relevant for this situation, but I need to skip past
+      // them so they're parsed but the result is discarded.
+      parse_flags(&local_pos);
+
+      // handle width
+      if (str[local_pos] == '*') {
+        ++local_pos;
+
+        size_t width_index = parse_index(&local_pos);
+        set_size_arr(width_index, get_arg_size<int>());
+        if (width_index == index)
+          return get_arg_size<int>();
+
+      } else if (internal::isdigit(str[local_pos])) {
+        while (internal::isdigit(str[local_pos]))
+          ++local_pos;
+      }
+
+      // handle precision
+      if (str[local_pos] == '.') {
+        ++local_pos;
+        if (str[local_pos] == '*') {
+          ++local_pos;
+
+          size_t precision_index = parse_index(&local_pos);
+          set_size_arr(precision_index, get_arg_size<int>());
+          if (precision_index == index)
+            return get_arg_size<int>();
+
+        } else if (internal::isdigit(str[local_pos])) {
+          while (internal::isdigit(str[local_pos]))
+            ++local_pos;
+        }
+      }
+
+      LengthModifier lm = parse_length_modifier(&local_pos);
+
+      // if we don't have an index for this conversion, then its position is
+      // unknown and all this information is irrelevant. The rest of this logic
+      // has been for skipping past this conversion properly to avoid
+      // weirdness with %%.
+      if (conv_index == 0) {
+        ++local_pos;
+        continue;
+      }
+
+      uint8_t conv_size = 0;
+      switch (str[local_pos]) {
+      case ('%'):
+        conv_size = 0;
+        break;
+      case ('c'):
+        conv_size = get_arg_size<int>();
+        break;
+      case ('d'):
+      case ('i'):
+      case ('o'):
+      case ('x'):
+      case ('X'):
+      case ('u'):
+        switch (lm) {
+        case (LengthModifier::hh):
+        case (LengthModifier::h):
+        case (LengthModifier::none):
+          conv_size = get_arg_size<int>();
+          break;
+        case (LengthModifier::l):
+          conv_size = get_arg_size<long>();
+          break;
+        case (LengthModifier::ll):
+        case (LengthModifier::L): // This isn't in the standard, but is in other
+                                  // libc implementations.
+          conv_size = get_arg_size<long long>();
+          break;
+        case (LengthModifier::j):
+          conv_size = get_arg_size<intmax_t>();
+          break;
+        case (LengthModifier::z):
+          conv_size = get_arg_size<size_t>();
+          break;
+        case (LengthModifier::t):
+          conv_size = get_arg_size<ptrdiff_t>();
+          break;
+        }
+        break;
+      case ('f'):
+      case ('F'):
+      case ('e'):
+      case ('E'):
+      case ('a'):
+      case ('A'):
+      case ('g'):
+      case ('G'):
+        if (lm != LengthModifier::L)
+          conv_size = get_arg_size<double>();
+        else
+          conv_size = get_arg_size<long double>();
+        break;
+      case ('n'):
+      case ('p'):
+      case ('s'):
+        conv_size = get_arg_size<void *>();
+        break;
+      default:
+        conv_size = get_arg_size<int>();
+        break;
+      }
+
+      set_size_arr(conv_index, conv_size);
+      if (conv_index == index)
+        return conv_size;
+    }
+    ++local_pos;
+  }
+
+  // If there is no size for the requested index, then just guess that it's an
+  // int.
+  return get_arg_size<int>();
+}
+
+void Parser::args_to_index(size_t index) {
+  if (index > args_index) {
+    args_index = 1;
+    args_cur = args_start;
+  }
+
+  while (args_index < index) {
+    size_t cur_size = 0;
+    if (args_index <= SIZE_ARR_LEN)
+      cur_size = size_arr[args_index - 1];
+
+    if (cur_size == 0)
+      cur_size = size_of_index(args_index);
+
+    if (cur_size == get_arg_size<uint32_t>())
+      args_cur.next_var<uint32_t>();
+    else if (cur_size == get_arg_size<uint64_t>())
+      args_cur.next_var<uint64_t>();
+    // Floating point numbers are stored separately from the other arguments.
+    else if (cur_size == get_arg_size<double>())
+      args_cur.next_var<double>();
+    else if (cur_size == get_arg_size<long double>())
+      args_cur.next_var<long double>();
+    else
+      args_cur.next_var<uint32_t>();
+
+    ++args_index;
+  }
+}
+
+#endif // LLVM_LIBC_PRINTF_DISABLE_INDEX_MODE
+
 } // namespace printf_core
 } // namespace __llvm_libc