Move folly/Hash.h to folly/hash/, leaving a shim
[folly.git] / folly / Format-inl.h
index f33ff62b274f1f36a44de0e21da2a7fc2f97f54e..60fdf2452c62a1a27768ed9668c0b588e8cf7525 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
 #error This file may only be included from Format.h.
 #endif
 
-#include "folly/Exception.h"
-#include "folly/Traits.h"
+#include <array>
+#include <cinttypes>
+#include <deque>
+#include <map>
+#include <unordered_map>
+#include <vector>
+
+#include <folly/Exception.h>
+#include <folly/FormatTraits.h>
+#include <folly/Traits.h>
+#include <folly/portability/Windows.h>
+
+// Ignore -Wformat-nonliteral warnings within this file
+FOLLY_PUSH_WARNING
+FOLLY_GCC_DISABLE_WARNING("-Wformat-nonliteral")
 
 namespace folly {
 
 namespace detail {
 
+// Updates the end of the buffer after the comma separators have been added.
+void insertThousandsGroupingUnsafe(char* start_buffer, char** end_buffer);
+
 extern const char formatHexUpper[256][2];
 extern const char formatHexLower[256][2];
 extern const char formatOctal[512][3];
@@ -44,8 +60,8 @@ const size_t kMaxBinaryLength = 8 * sizeof(uintmax_t);
  * [buf+begin, buf+bufLen).
  */
 template <class Uint>
-size_t uintToHex(char* buffer, size_t bufLen, Uint v,
-                 const char (&repr)[256][2]) {
+size_t
+uintToHex(char* buffer, size_t bufLen, Uint v, const char (&repr)[256][2]) {
   // 'v >>= 7, v >>= 1' is no more than a work around to get rid of shift size
   // warning when Uint = uint8_t (it's false as v >= 256 implies sizeof(v) > 1).
   for (; !less_than<unsigned, 256>(v); v >>= 7, v >>= 1) {
@@ -135,32 +151,26 @@ size_t uintToBinary(char* buffer, size_t bufLen, Uint v) {
   return bufLen;
 }
 
-}  // namespace detail
+} // namespace detail
 
+template <class Derived, bool containerMode, class... Args>
+BaseFormatter<Derived, containerMode, Args...>::BaseFormatter(
+    StringPiece str,
+    Args&&... args)
+    : str_(str), values_(std::forward<Args>(args)...) {}
 
-template <bool containerMode, class... Args>
-Formatter<containerMode, Args...>::Formatter(StringPiece str, Args&&... args)
-  : str_(str),
-    values_(FormatValue<typename std::decay<Args>::type>(
-        std::forward<Args>(args))...) {
-  static_assert(!containerMode || sizeof...(Args) == 1,
-                "Exactly one argument required in container mode");
-}
-
-template <bool containerMode, class... Args>
+template <class Derived, bool containerMode, class... Args>
 template <class Output>
-void Formatter<containerMode, Args...>::operator()(Output& out) const {
-  auto p = str_.begin();
-  auto end = str_.end();
-
+void BaseFormatter<Derived, containerMode, Args...>::operator()(
+    Output& out) const {
   // Copy raw string (without format specifiers) to output;
   // not as simple as we'd like, as we still need to translate "}}" to "}"
   // and throw if we see any lone "}"
-  auto outputString = [&out] (StringPiece s) {
+  auto outputString = [&out](StringPiece s) {
     auto p = s.begin();
     auto end = s.end();
     while (p != end) {
-      auto q = static_cast<const char*>(memchr(p, '}', end - p));
+      auto q = static_cast<const char*>(memchr(p, '}', size_t(end - p)));
       if (!q) {
         out(StringPiece(p, end));
         break;
@@ -170,18 +180,20 @@ void Formatter<containerMode, Args...>::operator()(Output& out) const {
       p = q;
 
       if (p == end || *p != '}') {
-        throw std::invalid_argument(
-            "folly::format: single '}' in format string");
+        throwBadFormatArg("folly::format: single '}' in format string");
       }
       ++p;
     }
   };
 
+  auto p = str_.begin();
+  auto end = str_.end();
+
   int nextArg = 0;
   bool hasDefaultArgIndex = false;
   bool hasExplicitArgIndex = false;
   while (p != end) {
-    auto q = static_cast<const char*>(memchr(p, '{', end - p));
+    auto q = static_cast<const char*>(memchr(p, '{', size_t(end - p)));
     if (!q) {
       outputString(StringPiece(p, end));
       break;
@@ -190,8 +202,7 @@ void Formatter<containerMode, Args...>::operator()(Output& out) const {
     p = q + 1;
 
     if (p == end) {
-      throw std::invalid_argument(
-          "folly::format: '}' at end of format string");
+      throwBadFormatArg("folly::format: '}' at end of format string");
     }
 
     // "{{" -> "{"
@@ -202,16 +213,19 @@ void Formatter<containerMode, Args...>::operator()(Output& out) const {
     }
 
     // Format string
-    q = static_cast<const char*>(memchr(p, '}', end - p));
+    q = static_cast<const char*>(memchr(p, '}', size_t(end - p)));
     if (q == nullptr) {
-      throw std::invalid_argument("folly::format: missing ending '}'");
+      throwBadFormatArg("folly::format: missing ending '}'");
     }
     FormatArg arg(StringPiece(p, q));
     p = q + 1;
 
     int argIndex = 0;
-    auto piece = arg.splitKey<true>();  // empty key component is okay
-    if (containerMode) {  // static
+    auto piece = arg.splitKey<true>(); // empty key component is okay
+    if (containerMode) { // static
+      arg.enforce(
+          arg.width != FormatArg::kDynamicWidth,
+          "dynamic field width not supported in vformat()");
       if (piece.empty()) {
         arg.setNextIntKey(nextArg++);
         hasDefaultArgIndex = true;
@@ -221,12 +235,27 @@ void Formatter<containerMode, Args...>::operator()(Output& out) const {
       }
     } else {
       if (piece.empty()) {
+        if (arg.width == FormatArg::kDynamicWidth) {
+          arg.enforce(
+              arg.widthIndex == FormatArg::kNoIndex,
+              "cannot provide width arg index without value arg index");
+          int sizeArg = nextArg++;
+          arg.width = asDerived().getSizeArg(size_t(sizeArg), arg);
+        }
+
         argIndex = nextArg++;
         hasDefaultArgIndex = true;
       } else {
+        if (arg.width == FormatArg::kDynamicWidth) {
+          arg.enforce(
+              arg.widthIndex != FormatArg::kNoIndex,
+              "cannot provide value arg index without width arg index");
+          arg.width = asDerived().getSizeArg(size_t(arg.widthIndex), arg);
+        }
+
         try {
           argIndex = to<int>(piece);
-        } catch (const std::out_of_range& e) {
+        } catch (const std::out_of_range&) {
           arg.error("argument index must be integer");
         }
         arg.enforce(argIndex >= 0, "argument index must be non-negative");
@@ -235,18 +264,20 @@ void Formatter<containerMode, Args...>::operator()(Output& out) const {
     }
 
     if (hasDefaultArgIndex && hasExplicitArgIndex) {
-      throw std::invalid_argument(
+      throwBadFormatArg(
           "folly::format: may not have both default and explicit arg indexes");
     }
 
-    doFormat(argIndex, arg, out);
+    asDerived().doFormat(size_t(argIndex), arg, out);
   }
 }
 
-template <bool containerMode, class... Args>
-void writeTo(FILE* fp, const Formatter<containerMode, Args...>& formatter) {
-  auto writer = [fp] (StringPiece sp) {
-    ssize_t n = fwrite(sp.data(), 1, sp.size(), fp);
+template <class Derived, bool containerMode, class... Args>
+void writeTo(
+    FILE* fp,
+    const BaseFormatter<Derived, containerMode, Args...>& formatter) {
+  auto writer = [fp](StringPiece sp) {
+    size_t n = fwrite(sp.data(), 1, sp.size(), fp);
     if (n < sp.size()) {
       throwSystemError("Formatter writeTo", "fwrite failed");
     }
@@ -258,45 +289,53 @@ namespace format_value {
 
 template <class FormatCallback>
 void formatString(StringPiece val, FormatArg& arg, FormatCallback& cb) {
+  if (arg.width != FormatArg::kDefaultWidth && arg.width < 0) {
+    throwBadFormatArg("folly::format: invalid width");
+  }
+  if (arg.precision != FormatArg::kDefaultPrecision && arg.precision < 0) {
+    throwBadFormatArg("folly::format: invalid precision");
+  }
+
   if (arg.precision != FormatArg::kDefaultPrecision &&
-      val.size() > arg.precision) {
-    val.reset(val.data(), arg.precision);
+      val.size() > static_cast<size_t>(arg.precision)) {
+    val.reset(val.data(), static_cast<size_t>(arg.precision));
   }
 
   constexpr int padBufSize = 128;
   char padBuf[padBufSize];
 
   // Output padding, no more than padBufSize at once
-  auto pad = [&padBuf, &cb, padBufSize] (int chars) {
+  auto pad = [&padBuf, &cb, padBufSize](int chars) {
     while (chars) {
       int n = std::min(chars, padBufSize);
-      cb(StringPiece(padBuf, n));
+      cb(StringPiece(padBuf, size_t(n)));
       chars -= n;
     }
   };
 
   int padRemaining = 0;
-  if (arg.width != FormatArg::kDefaultWidth && val.size() < arg.width) {
+  if (arg.width != FormatArg::kDefaultWidth &&
+      val.size() < static_cast<size_t>(arg.width)) {
     char fill = arg.fill == FormatArg::kDefaultFill ? ' ' : arg.fill;
-    int padChars = arg.width - val.size();
-    memset(padBuf, fill, std::min(padBufSize, padChars));
+    int padChars = static_cast<int>(arg.width - val.size());
+    memset(padBuf, fill, size_t(std::min(padBufSize, padChars)));
 
     switch (arg.align) {
-    case FormatArg::Align::DEFAULT:
-    case FormatArg::Align::LEFT:
-      padRemaining = padChars;
-      break;
-    case FormatArg::Align::CENTER:
-      pad(padChars / 2);
-      padRemaining = padChars - padChars / 2;
-      break;
-    case FormatArg::Align::RIGHT:
-    case FormatArg::Align::PAD_AFTER_SIGN:
-      pad(padChars);
-      break;
-    default:
-      abort();
-      break;
+      case FormatArg::Align::DEFAULT:
+      case FormatArg::Align::LEFT:
+        padRemaining = padChars;
+        break;
+      case FormatArg::Align::CENTER:
+        pad(padChars / 2);
+        padRemaining = padChars - padChars / 2;
+        break;
+      case FormatArg::Align::RIGHT:
+      case FormatArg::Align::PAD_AFTER_SIGN:
+        pad(padChars);
+        break;
+      default:
+        abort();
+        break;
     }
   }
 
@@ -308,40 +347,49 @@ void formatString(StringPiece val, FormatArg& arg, FormatCallback& cb) {
 }
 
 template <class FormatCallback>
-void formatNumber(StringPiece val, int prefixLen, FormatArg& arg,
-                  FormatCallback& cb) {
+void formatNumber(
+    StringPiece val,
+    int prefixLen,
+    FormatArg& arg,
+    FormatCallback& cb) {
   // precision means something different for numbers
   arg.precision = FormatArg::kDefaultPrecision;
   if (arg.align == FormatArg::Align::DEFAULT) {
     arg.align = FormatArg::Align::RIGHT;
   } else if (prefixLen && arg.align == FormatArg::Align::PAD_AFTER_SIGN) {
     // Split off the prefix, then do any padding if necessary
-    cb(val.subpiece(0, prefixLen));
-    val.advance(prefixLen);
+    cb(val.subpiece(0, size_t(prefixLen)));
+    val.advance(size_t(prefixLen));
     arg.width = std::max(arg.width - prefixLen, 0);
   }
   format_value::formatString(val, arg, cb);
 }
 
-template <class FormatCallback, bool containerMode, class... Args>
-void formatFormatter(const Formatter<containerMode, Args...>& formatter,
-                     FormatArg& arg,
-                     FormatCallback& cb) {
+template <
+    class FormatCallback,
+    class Derived,
+    bool containerMode,
+    class... Args>
+void formatFormatter(
+    const BaseFormatter<Derived, containerMode, Args...>& formatter,
+    FormatArg& arg,
+    FormatCallback& cb) {
   if (arg.width == FormatArg::kDefaultWidth &&
       arg.precision == FormatArg::kDefaultPrecision) {
     // nothing to do
     formatter(cb);
-  } else if (arg.align != FormatArg::Align::LEFT &&
-             arg.align != FormatArg::Align::DEFAULT) {
+  } else if (
+      arg.align != FormatArg::Align::LEFT &&
+      arg.align != FormatArg::Align::DEFAULT) {
     // We can only avoid creating a temporary string if we align left,
     // as we'd need to know the size beforehand otherwise
     format_value::formatString(formatter.fbstr(), arg, cb);
   } else {
-    auto fn = [&arg, &cb] (StringPiece sp) mutable {
+    auto fn = [&arg, &cb](StringPiece sp) mutable {
       int sz = static_cast<int>(sp.size());
       if (arg.precision != FormatArg::kDefaultPrecision) {
         sz = std::min(arg.precision, sz);
-        sp.reset(sp.data(), sz);
+        sp.reset(sp.data(), size_t(sz));
         arg.precision -= sz;
       }
       if (!sp.empty()) {
@@ -359,19 +407,23 @@ void formatFormatter(const Formatter<containerMode, Args...>& formatter,
   }
 }
 
-}  // namespace format_value
+} // namespace format_value
 
 // Definitions for default FormatValue classes
 
 // Integral types (except bool)
 template <class T>
 class FormatValue<
-  T, typename std::enable_if<
-    std::is_integral<T>::value &&
-    !std::is_same<T, bool>::value>::type>
-  {
+    T,
+    typename std::enable_if<
+        std::is_integral<T>::value && !std::is_same<T, bool>::value>::type> {
  public:
-  explicit FormatValue(T val) : val_(val) { }
+  explicit FormatValue(T val) : val_(val) {}
+
+  T getValue() const {
+    return val_;
+  }
+
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     arg.validate(FormatArg::Type::INTEGER);
@@ -392,28 +444,29 @@ class FormatValue<
     char sign;
     if (std::is_signed<T>::value) {
       if (folly::is_negative(val_)) {
-        uval = static_cast<UT>(-val_);
+        uval = UT(-static_cast<UT>(val_));
         sign = '-';
       } else {
         uval = static_cast<UT>(val_);
         switch (arg.sign) {
-        case FormatArg::Sign::PLUS_OR_MINUS:
-          sign = '+';
-          break;
-        case FormatArg::Sign::SPACE_OR_MINUS:
-          sign = ' ';
-          break;
-        default:
-          sign = '\0';
-          break;
+          case FormatArg::Sign::PLUS_OR_MINUS:
+            sign = '+';
+            break;
+          case FormatArg::Sign::SPACE_OR_MINUS:
+            sign = ' ';
+            break;
+          default:
+            sign = '\0';
+            break;
         }
       }
     } else {
-      uval = val_;
+      uval = static_cast<UT>(val_);
       sign = '\0';
 
-      arg.enforce(arg.sign == FormatArg::Sign::DEFAULT,
-                  "sign specifications not allowed for unsigned values");
+      arg.enforce(
+          arg.sign == FormatArg::Sign::DEFAULT,
+          "sign specifications not allowed for unsigned values");
     }
 
     // max of:
@@ -428,94 +481,133 @@ class FormatValue<
     char* valBufBegin = nullptr;
     char* valBufEnd = nullptr;
 
-    // Defer to sprintf
-    auto useSprintf = [&] (const char* format) mutable {
-      valBufBegin = valBuf + 3;  // room for sign and base prefix
-      valBufEnd = valBufBegin + sprintf(valBufBegin, format,
-                                        static_cast<uintmax_t>(uval));
-    };
-
     int prefixLen = 0;
-
     switch (presentation) {
-    case 'n':  // TODO(tudorb): locale awareness?
-    case 'd':
-      arg.enforce(!arg.basePrefix,
-                  "base prefix not allowed with '", presentation,
-                  "' specifier");
-      if (arg.thousandsSeparator) {
-        useSprintf("%'ju");
-      } else {
+      case 'n': {
+        arg.enforce(
+            !arg.basePrefix,
+            "base prefix not allowed with '",
+            presentation,
+            "' specifier");
+
+        arg.enforce(
+            !arg.thousandsSeparator,
+            "cannot use ',' with the '",
+            presentation,
+            "' specifier");
+
+        valBufBegin = valBuf + 3; // room for sign and base prefix
+#if defined(__ANDROID__)
+        int len = snprintf(
+            valBufBegin,
+            (valBuf + valBufSize) - valBufBegin,
+            "%" PRIuMAX,
+            static_cast<uintmax_t>(uval));
+#else
+        int len = snprintf(
+            valBufBegin,
+            size_t((valBuf + valBufSize) - valBufBegin),
+            "%ju",
+            static_cast<uintmax_t>(uval));
+#endif
+        // valBufSize should always be big enough, so this should never
+        // happen.
+        assert(len < valBuf + valBufSize - valBufBegin);
+        valBufEnd = valBufBegin + len;
+        break;
+      }
+      case 'd':
+        arg.enforce(
+            !arg.basePrefix,
+            "base prefix not allowed with '",
+            presentation,
+            "' specifier");
+        valBufBegin = valBuf + 3; // room for sign and base prefix
+
         // Use uintToBuffer, faster than sprintf
-        valBufBegin = valBuf + 3;
         valBufEnd = valBufBegin + uint64ToBufferUnsafe(uval, valBufBegin);
-      }
-      break;
-    case 'c':
-      arg.enforce(!arg.basePrefix,
-                  "base prefix not allowed with '", presentation,
-                  "' specifier");
-      arg.enforce(!arg.thousandsSeparator,
-                  "thousands separator (',') not allowed with '",
-                  presentation, "' specifier");
-      valBufBegin = valBuf + 3;
-      *valBufBegin = static_cast<char>(uval);
-      valBufEnd = valBufBegin + 1;
-      break;
-    case 'o':
-    case 'O':
-      arg.enforce(!arg.thousandsSeparator,
-                  "thousands separator (',') not allowed with '",
-                  presentation, "' specifier");
-      valBufEnd = valBuf + valBufSize - 1;
-      valBufBegin = valBuf + detail::uintToOctal(valBuf, valBufSize - 1, uval);
-      if (arg.basePrefix) {
-        *--valBufBegin = '0';
-        prefixLen = 1;
-      }
-      break;
-    case 'x':
-      arg.enforce(!arg.thousandsSeparator,
-                  "thousands separator (',') not allowed with '",
-                  presentation, "' specifier");
-      valBufEnd = valBuf + valBufSize - 1;
-      valBufBegin = valBuf + detail::uintToHexLower(valBuf, valBufSize - 1,
-                                                    uval);
-      if (arg.basePrefix) {
-        *--valBufBegin = 'x';
-        *--valBufBegin = '0';
-        prefixLen = 2;
-      }
-      break;
-    case 'X':
-      arg.enforce(!arg.thousandsSeparator,
-                  "thousands separator (',') not allowed with '",
-                  presentation, "' specifier");
-      valBufEnd = valBuf + valBufSize - 1;
-      valBufBegin = valBuf + detail::uintToHexUpper(valBuf, valBufSize - 1,
-                                                    uval);
-      if (arg.basePrefix) {
-        *--valBufBegin = 'X';
-        *--valBufBegin = '0';
-        prefixLen = 2;
-      }
-      break;
-    case 'b':
-    case 'B':
-      arg.enforce(!arg.thousandsSeparator,
-                  "thousands separator (',') not allowed with '",
-                  presentation, "' specifier");
-      valBufEnd = valBuf + valBufSize - 1;
-      valBufBegin = valBuf + detail::uintToBinary(valBuf, valBufSize - 1,
-                                                  uval);
-      if (arg.basePrefix) {
-        *--valBufBegin = presentation;  // 0b or 0B
-        *--valBufBegin = '0';
-        prefixLen = 2;
-      }
-      break;
-    default:
-      arg.error("invalid specifier '", presentation, "'");
+        if (arg.thousandsSeparator) {
+          detail::insertThousandsGroupingUnsafe(valBufBegin, &valBufEnd);
+        }
+        break;
+      case 'c':
+        arg.enforce(
+            !arg.basePrefix,
+            "base prefix not allowed with '",
+            presentation,
+            "' specifier");
+        arg.enforce(
+            !arg.thousandsSeparator,
+            "thousands separator (',') not allowed with '",
+            presentation,
+            "' specifier");
+        valBufBegin = valBuf + 3;
+        *valBufBegin = static_cast<char>(uval);
+        valBufEnd = valBufBegin + 1;
+        break;
+      case 'o':
+      case 'O':
+        arg.enforce(
+            !arg.thousandsSeparator,
+            "thousands separator (',') not allowed with '",
+            presentation,
+            "' specifier");
+        valBufEnd = valBuf + valBufSize - 1;
+        valBufBegin =
+            valBuf + detail::uintToOctal(valBuf, valBufSize - 1, uval);
+        if (arg.basePrefix) {
+          *--valBufBegin = '0';
+          prefixLen = 1;
+        }
+        break;
+      case 'x':
+        arg.enforce(
+            !arg.thousandsSeparator,
+            "thousands separator (',') not allowed with '",
+            presentation,
+            "' specifier");
+        valBufEnd = valBuf + valBufSize - 1;
+        valBufBegin =
+            valBuf + detail::uintToHexLower(valBuf, valBufSize - 1, uval);
+        if (arg.basePrefix) {
+          *--valBufBegin = 'x';
+          *--valBufBegin = '0';
+          prefixLen = 2;
+        }
+        break;
+      case 'X':
+        arg.enforce(
+            !arg.thousandsSeparator,
+            "thousands separator (',') not allowed with '",
+            presentation,
+            "' specifier");
+        valBufEnd = valBuf + valBufSize - 1;
+        valBufBegin =
+            valBuf + detail::uintToHexUpper(valBuf, valBufSize - 1, uval);
+        if (arg.basePrefix) {
+          *--valBufBegin = 'X';
+          *--valBufBegin = '0';
+          prefixLen = 2;
+        }
+        break;
+      case 'b':
+      case 'B':
+        arg.enforce(
+            !arg.thousandsSeparator,
+            "thousands separator (',') not allowed with '",
+            presentation,
+            "' specifier");
+        valBufEnd = valBuf + valBufSize - 1;
+        valBufBegin =
+            valBuf + detail::uintToBinary(valBuf, valBufSize - 1, uval);
+        if (arg.basePrefix) {
+          *--valBufBegin = presentation; // 0b or 0B
+          *--valBufBegin = '0';
+          prefixLen = 2;
+        }
+        break;
+      default:
+        arg.error("invalid specifier '", presentation, "'");
     }
 
     if (sign) {
@@ -523,8 +615,8 @@ class FormatValue<
       ++prefixLen;
     }
 
-    format_value::formatNumber(StringPiece(valBufBegin, valBufEnd), prefixLen,
-                               arg, cb);
+    format_value::formatNumber(
+        StringPiece(valBufBegin, valBufEnd), prefixLen, arg, cb);
   }
 
  private:
@@ -535,14 +627,14 @@ class FormatValue<
 template <>
 class FormatValue<bool> {
  public:
-  explicit FormatValue(bool val) : val_(val) { }
+  explicit FormatValue(bool val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     if (arg.presentation == FormatArg::kDefaultPresentation) {
       arg.validate(FormatArg::Type::OTHER);
       format_value::formatString(val_ ? "true" : "false", arg, cb);
-    } else {  // number
+    } else { // number
       FormatValue<int>(val_).format(arg, cb);
     }
   }
@@ -555,131 +647,19 @@ class FormatValue<bool> {
 template <>
 class FormatValue<double> {
  public:
-  explicit FormatValue(double val) : val_(val) { }
+  explicit FormatValue(double val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
-    using ::double_conversion::DoubleToStringConverter;
-    using ::double_conversion::StringBuilder;
-
-    arg.validate(FormatArg::Type::FLOAT);
-
-    if (arg.presentation == FormatArg::kDefaultPresentation) {
-      arg.presentation = 'g';
-    }
-
-    const char* infinitySymbol = isupper(arg.presentation) ? "INF" : "inf";
-    const char* nanSymbol = isupper(arg.presentation) ? "NAN" : "nan";
-    char exponentSymbol = isupper(arg.presentation) ? 'E' : 'e';
-
-    if (arg.precision == FormatArg::kDefaultPrecision) {
-      arg.precision = 6;
-    }
-
-    // 2+: for null terminator and optional sign shenanigans.
-    char buf[2 + std::max({
-        (2 + DoubleToStringConverter::kMaxFixedDigitsBeforePoint +
-         DoubleToStringConverter::kMaxFixedDigitsAfterPoint),
-        (8 + DoubleToStringConverter::kMaxExponentialDigits),
-        (7 + DoubleToStringConverter::kMaxPrecisionDigits)})];
-    StringBuilder builder(buf + 1, sizeof(buf) - 1);
-
-    char plusSign;
-    switch (arg.sign) {
-    case FormatArg::Sign::PLUS_OR_MINUS:
-      plusSign = '+';
-      break;
-    case FormatArg::Sign::SPACE_OR_MINUS:
-      plusSign = ' ';
-      break;
-    default:
-      plusSign = '\0';
-      break;
-    };
-
-    double val = val_;
-    switch (arg.presentation) {
-    case '%':
-      val *= 100;
-    case 'f':
-    case 'F':
-      {
-        if (arg.precision >
-            DoubleToStringConverter::kMaxFixedDigitsAfterPoint) {
-          arg.precision = DoubleToStringConverter::kMaxFixedDigitsAfterPoint;
-        }
-        DoubleToStringConverter conv(
-            DoubleToStringConverter::EMIT_POSITIVE_EXPONENT_SIGN,
-            infinitySymbol,
-            nanSymbol,
-            exponentSymbol,
-            -4, arg.precision,
-            0, 0);
-        arg.enforce(conv.ToFixed(val, arg.precision, &builder),
-                    "fixed double conversion failed");
-      }
-      break;
-    case 'e':
-    case 'E':
-      {
-        if (arg.precision > DoubleToStringConverter::kMaxExponentialDigits) {
-          arg.precision = DoubleToStringConverter::kMaxExponentialDigits;
-        }
-
-        DoubleToStringConverter conv(
-            DoubleToStringConverter::EMIT_POSITIVE_EXPONENT_SIGN,
-            infinitySymbol,
-            nanSymbol,
-            exponentSymbol,
-            -4, arg.precision,
-            0, 0);
-        arg.enforce(conv.ToExponential(val, arg.precision, &builder));
-      }
-      break;
-    case 'n':  // should be locale-aware, but isn't
-    case 'g':
-    case 'G':
-      {
-        if (arg.precision < DoubleToStringConverter::kMinPrecisionDigits) {
-          arg.precision = DoubleToStringConverter::kMinPrecisionDigits;
-        } else if (arg.precision >
-                   DoubleToStringConverter::kMaxPrecisionDigits) {
-          arg.precision = DoubleToStringConverter::kMaxPrecisionDigits;
-        }
-        DoubleToStringConverter conv(
-            DoubleToStringConverter::EMIT_POSITIVE_EXPONENT_SIGN,
-            infinitySymbol,
-            nanSymbol,
-            exponentSymbol,
-            -4, arg.precision,
-            0, 0);
-        arg.enforce(conv.ToShortest(val, &builder));
-      }
-      break;
-    default:
-      arg.error("invalid specifier '", arg.presentation, "'");
-    }
-
-    int len = builder.position();
-    builder.Finalize();
-    DCHECK_GT(len, 0);
-
-    // Add '+' or ' ' sign if needed
-    char* p = buf + 1;
-    // anything that's neither negative nor nan
-    int prefixLen = 0;
-    if (plusSign && (*p != '-' && *p != 'n' && *p != 'N')) {
-      *--p = plusSign;
-      ++len;
-      prefixLen = 1;
-    } else if (*p == '-') {
-      prefixLen = 1;
-    }
-
-    format_value::formatNumber(StringPiece(p, len), prefixLen, arg, cb);
+    fbstring piece;
+    int prefixLen;
+    formatHelper(piece, prefixLen, arg);
+    format_value::formatNumber(piece, prefixLen, arg, cb);
   }
 
  private:
+  void formatHelper(fbstring& piece, int& prefixLen, FormatArg& arg) const;
+
   double val_;
 };
 
@@ -687,7 +667,7 @@ class FormatValue<double> {
 template <>
 class FormatValue<float> {
  public:
-  explicit FormatValue(float val) : val_(val) { }
+  explicit FormatValue(float val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
@@ -698,28 +678,33 @@ class FormatValue<float> {
   float val_;
 };
 
-// Sring-y types (implicitly convertible to StringPiece, except char*)
+// String-y types (implicitly convertible to StringPiece, except char*)
 template <class T>
 class FormatValue<
-  T, typename std::enable_if<
-      (!std::is_pointer<T>::value ||
-       !std::is_same<char, typename std::decay<
-          typename std::remove_pointer<T>::type>::type>::value) &&
-      std::is_convertible<T, StringPiece>::value>::type>
-  {
+    T,
+    typename std::enable_if<
+        (!std::is_pointer<T>::value ||
+         !std::is_same<
+             char,
+             typename std::decay<typename std::remove_pointer<T>::type>::type>::
+             value) &&
+        std::is_convertible<T, StringPiece>::value>::type> {
  public:
-  explicit FormatValue(StringPiece val) : val_(val) { }
+  explicit FormatValue(StringPiece val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     if (arg.keyEmpty()) {
       arg.validate(FormatArg::Type::OTHER);
-      arg.enforce(arg.presentation == FormatArg::kDefaultPresentation ||
-                  arg.presentation == 's',
-                  "invalid specifier '", arg.presentation, "'");
+      arg.enforce(
+          arg.presentation == FormatArg::kDefaultPresentation ||
+              arg.presentation == 's',
+          "invalid specifier '",
+          arg.presentation,
+          "'");
       format_value::formatString(val_, arg, cb);
     } else {
-      FormatValue<char>(val_.at(arg.splitIntKey())).format(arg, cb);
+      FormatValue<char>(val_.at(size_t(arg.splitIntKey()))).format(arg, cb);
     }
   }
 
@@ -731,13 +716,16 @@ class FormatValue<
 template <>
 class FormatValue<std::nullptr_t> {
  public:
-  explicit FormatValue(std::nullptr_t) { }
+  explicit FormatValue(std::nullptr_t) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     arg.validate(FormatArg::Type::OTHER);
-    arg.enforce(arg.presentation == FormatArg::kDefaultPresentation,
-                "invalid specifier '", arg.presentation, "'");
+    arg.enforce(
+        arg.presentation == FormatArg::kDefaultPresentation,
+        "invalid specifier '",
+        arg.presentation,
+        "'");
     format_value::formatString("(null)", arg, cb);
   }
 };
@@ -745,12 +733,11 @@ class FormatValue<std::nullptr_t> {
 // Partial specialization of FormatValue for char*
 template <class T>
 class FormatValue<
-  T*,
-  typename std::enable_if<
-      std::is_same<char, typename std::decay<T>::type>::value>::type>
-  {
+    T*,
+    typename std::enable_if<
+        std::is_same<char, typename std::decay<T>::type>::value>::type> {
  public:
-  explicit FormatValue(T* val) : val_(val) { }
+  explicit FormatValue(T* val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
@@ -761,8 +748,8 @@ class FormatValue<
         FormatValue<StringPiece>(val_).format(arg, cb);
       }
     } else {
-      FormatValue<typename std::decay<T>::type>(
-          val_[arg.splitIntKey()]).format(arg, cb);
+      FormatValue<typename std::decay<T>::type>(val_[arg.splitIntKey()])
+          .format(arg, cb);
     }
   }
 
@@ -773,12 +760,11 @@ class FormatValue<
 // Partial specialization of FormatValue for void*
 template <class T>
 class FormatValue<
-  T*,
-  typename std::enable_if<
-      std::is_same<void, typename std::decay<T>::type>::value>::type>
-  {
+    T*,
+    typename std::enable_if<
+        std::is_same<void, typename std::decay<T>::type>::value>::type> {
  public:
-  explicit FormatValue(T* val) : val_(val) { }
+  explicit FormatValue(T* val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
@@ -787,15 +773,18 @@ class FormatValue<
     } else {
       // Print as a pointer, in hex.
       arg.validate(FormatArg::Type::OTHER);
-      arg.enforce(arg.presentation == FormatArg::kDefaultPresentation,
-                  "invalid specifier '", arg.presentation, "'");
+      arg.enforce(
+          arg.presentation == FormatArg::kDefaultPresentation,
+          "invalid specifier '",
+          arg.presentation,
+          "'");
       arg.basePrefix = true;
       arg.presentation = 'x';
       if (arg.align == FormatArg::Align::DEFAULT) {
         arg.align = FormatArg::Align::LEFT;
       }
-      FormatValue<uintptr_t>(
-          reinterpret_cast<uintptr_t>(val_)).doFormat(arg, cb);
+      FormatValue<uintptr_t>(reinterpret_cast<uintptr_t>(val_))
+          .doFormat(arg, cb);
     }
   }
 
@@ -807,17 +796,17 @@ template <class T, class = void>
 class TryFormatValue {
  public:
   template <class FormatCallback>
-  static void formatOrFail(T& value, FormatArg& arg, FormatCallback& cb) {
+  static void
+  formatOrFail(T& /* value */, FormatArg& arg, FormatCallback& /* cb */) {
     arg.error("No formatter available for this type");
   }
 };
 
 template <class T>
 class TryFormatValue<
-  T,
-  typename std::enable_if<
-      0 < sizeof(FormatValue<typename std::decay<T>::type>)>::type>
-  {
+    T,
+    typename std::enable_if<
+        0 < sizeof(FormatValue<typename std::decay<T>::type>)>::type> {
  public:
   template <class FormatCallback>
   static void formatOrFail(T& value, FormatArg& arg, FormatCallback& cb) {
@@ -828,13 +817,12 @@ class TryFormatValue<
 // Partial specialization of FormatValue for other pointers
 template <class T>
 class FormatValue<
-  T*,
-  typename std::enable_if<
-      !std::is_same<char, typename std::decay<T>::type>::value &&
-      !std::is_same<void, typename std::decay<T>::type>::value>::type>
-  {
+    T*,
+    typename std::enable_if<
+        !std::is_same<char, typename std::decay<T>::type>::value &&
+        !std::is_same<void, typename std::decay<T>::type>::value>::type> {
  public:
-  explicit FormatValue(T* val) : val_(val) { }
+  explicit FormatValue(T* val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
@@ -844,114 +832,89 @@ class FormatValue<
       TryFormatValue<T>::formatOrFail(val_[arg.splitIntKey()], arg, cb);
     }
   }
+
  private:
   T* val_;
 };
 
 namespace detail {
 
-// Shortcut, so we don't have to use enable_if everywhere
-struct FormatTraitsBase {
-  typedef void enabled;
-};
-
-// Traits that define enabled, value_type, and at() for anything
-// indexable with integral keys: pointers, arrays, vectors, and maps
-// with integral keys
-template <class T, class Enable=void> struct IndexableTraits;
-
-// Base class for sequences (vectors, deques)
-template <class C>
-struct IndexableTraitsSeq : public FormatTraitsBase {
-  typedef C container_type;
-  typedef typename C::value_type value_type;
-  static const value_type& at(const C& c, int idx) {
-    return c.at(idx);
-  }
-};
-
-// Base class for associative types (maps)
-template <class C>
-struct IndexableTraitsAssoc : public FormatTraitsBase {
-  typedef typename C::value_type::second_type value_type;
-  static const value_type& at(const C& c, int idx) {
-    return c.at(static_cast<typename C::key_type>(idx));
-  }
-};
-
 // std::array
 template <class T, size_t N>
 struct IndexableTraits<std::array<T, N>>
-  : public IndexableTraitsSeq<std::array<T, N>> {
-};
+    : public IndexableTraitsSeq<std::array<T, N>> {};
 
 // std::vector
 template <class T, class A>
 struct IndexableTraits<std::vector<T, A>>
-  : public IndexableTraitsSeq<std::vector<T, A>> {
-};
+    : public IndexableTraitsSeq<std::vector<T, A>> {};
 
 // std::deque
 template <class T, class A>
 struct IndexableTraits<std::deque<T, A>>
-  : public IndexableTraitsSeq<std::deque<T, A>> {
-};
-
-// fbvector
-template <class T, class A>
-struct IndexableTraits<fbvector<T, A>>
-  : public IndexableTraitsSeq<fbvector<T, A>> {
-};
-
-// small_vector
-template <class T, size_t M, class A, class B, class C>
-struct IndexableTraits<small_vector<T, M, A, B, C>>
-  : public IndexableTraitsSeq<small_vector<T, M, A, B, C>> {
-};
+    : public IndexableTraitsSeq<std::deque<T, A>> {};
 
 // std::map with integral keys
 template <class K, class T, class C, class A>
 struct IndexableTraits<
-  std::map<K, T, C, A>,
-  typename std::enable_if<std::is_integral<K>::value>::type>
-  : public IndexableTraitsAssoc<std::map<K, T, C, A>> {
-};
+    std::map<K, T, C, A>,
+    typename std::enable_if<std::is_integral<K>::value>::type>
+    : public IndexableTraitsAssoc<std::map<K, T, C, A>> {};
 
 // std::unordered_map with integral keys
 template <class K, class T, class H, class E, class A>
 struct IndexableTraits<
-  std::unordered_map<K, T, H, E, A>,
-  typename std::enable_if<std::is_integral<K>::value>::type>
-  : public IndexableTraitsAssoc<std::unordered_map<K, T, H, E, A>> {
-};
+    std::unordered_map<K, T, H, E, A>,
+    typename std::enable_if<std::is_integral<K>::value>::type>
+    : public IndexableTraitsAssoc<std::unordered_map<K, T, H, E, A>> {};
 
-}  // namespace detail
+} // namespace detail
 
 // Partial specialization of FormatValue for integer-indexable containers
 template <class T>
-class FormatValue<
-  T,
-  typename detail::IndexableTraits<T>::enabled> {
+class FormatValue<T, typename detail::IndexableTraits<T>::enabled> {
  public:
-  explicit FormatValue(const T& val) : val_(val) { }
+  explicit FormatValue(const T& val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     FormatValue<typename std::decay<
-      typename detail::IndexableTraits<T>::value_type>::type>(
-        detail::IndexableTraits<T>::at(
-            val_, arg.splitIntKey())).format(arg, cb);
+        typename detail::IndexableTraits<T>::value_type>::type>(
+        detail::IndexableTraits<T>::at(val_, arg.splitIntKey()))
+        .format(arg, cb);
   }
 
  private:
   const T& val_;
 };
 
+template <class Container, class Value>
+class FormatValue<
+    detail::DefaultValueWrapper<Container, Value>,
+    typename detail::IndexableTraits<Container>::enabled> {
+ public:
+  explicit FormatValue(const detail::DefaultValueWrapper<Container, Value>& val)
+      : val_(val) {}
+
+  template <class FormatCallback>
+  void format(FormatArg& arg, FormatCallback& cb) const {
+    FormatValue<typename std::decay<
+        typename detail::IndexableTraits<Container>::value_type>::type>(
+        detail::IndexableTraits<Container>::at(
+            val_.container, arg.splitIntKey(), val_.defaultValue))
+        .format(arg, cb);
+  }
+
+ private:
+  const detail::DefaultValueWrapper<Container, Value>& val_;
+};
+
 namespace detail {
 
 // Define enabled, key_type, convert from StringPiece to the key types
 // that we support
-template <class T> struct KeyFromStringPiece;
+template <class T>
+struct KeyFromStringPiece;
 
 // std::string
 template <>
@@ -968,7 +931,7 @@ template <>
 struct KeyFromStringPiece<fbstring> : public FormatTraitsBase {
   typedef fbstring key_type;
   static fbstring convert(StringPiece s) {
-    return s.toFbstring();
+    return s.to<fbstring>();
   }
 };
 
@@ -982,74 +945,98 @@ struct KeyFromStringPiece<StringPiece> : public FormatTraitsBase {
 };
 
 // Base class for associative types keyed by strings
-template <class T> struct KeyableTraitsAssoc : public FormatTraitsBase {
+template <class T>
+struct KeyableTraitsAssoc : public FormatTraitsBase {
   typedef typename T::key_type key_type;
   typedef typename T::value_type::second_type value_type;
   static const value_type& at(const T& map, StringPiece key) {
     return map.at(KeyFromStringPiece<key_type>::convert(key));
   }
+  static const value_type&
+  at(const T& map, StringPiece key, const value_type& dflt) {
+    auto pos = map.find(KeyFromStringPiece<key_type>::convert(key));
+    return pos != map.end() ? pos->second : dflt;
+  }
 };
 
 // Define enabled, key_type, value_type, at() for supported string-keyed
 // types
-template <class T, class Enabled=void> struct KeyableTraits;
+template <class T, class Enabled = void>
+struct KeyableTraits;
 
 // std::map with string key
 template <class K, class T, class C, class A>
 struct KeyableTraits<
-  std::map<K, T, C, A>,
-  typename KeyFromStringPiece<K>::enabled>
-  : public KeyableTraitsAssoc<std::map<K, T, C, A>> {
-};
+    std::map<K, T, C, A>,
+    typename KeyFromStringPiece<K>::enabled>
+    : public KeyableTraitsAssoc<std::map<K, T, C, A>> {};
 
 // std::unordered_map with string key
 template <class K, class T, class H, class E, class A>
 struct KeyableTraits<
-  std::unordered_map<K, T, H, E, A>,
-  typename KeyFromStringPiece<K>::enabled>
-  : public KeyableTraitsAssoc<std::unordered_map<K, T, H, E, A>> {
-};
+    std::unordered_map<K, T, H, E, A>,
+    typename KeyFromStringPiece<K>::enabled>
+    : public KeyableTraitsAssoc<std::unordered_map<K, T, H, E, A>> {};
 
-}  // namespace detail
+} // namespace detail
 
 // Partial specialization of FormatValue for string-keyed containers
 template <class T>
-class FormatValue<
-  T,
-  typename detail::KeyableTraits<T>::enabled> {
+class FormatValue<T, typename detail::KeyableTraits<T>::enabled> {
  public:
-  explicit FormatValue(const T& val) : val_(val) { }
+  explicit FormatValue(const T& val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     FormatValue<typename std::decay<
-      typename detail::KeyableTraits<T>::value_type>::type>(
-        detail::KeyableTraits<T>::at(
-            val_, arg.splitKey())).format(arg, cb);
+        typename detail::KeyableTraits<T>::value_type>::type>(
+        detail::KeyableTraits<T>::at(val_, arg.splitKey()))
+        .format(arg, cb);
   }
 
  private:
   const T& val_;
 };
 
+template <class Container, class Value>
+class FormatValue<
+    detail::DefaultValueWrapper<Container, Value>,
+    typename detail::KeyableTraits<Container>::enabled> {
+ public:
+  explicit FormatValue(const detail::DefaultValueWrapper<Container, Value>& val)
+      : val_(val) {}
+
+  template <class FormatCallback>
+  void format(FormatArg& arg, FormatCallback& cb) const {
+    FormatValue<typename std::decay<
+        typename detail::KeyableTraits<Container>::value_type>::type>(
+        detail::KeyableTraits<Container>::at(
+            val_.container, arg.splitKey(), val_.defaultValue))
+        .format(arg, cb);
+  }
+
+ private:
+  const detail::DefaultValueWrapper<Container, Value>& val_;
+};
+
 // Partial specialization of FormatValue for pairs
 template <class A, class B>
 class FormatValue<std::pair<A, B>> {
  public:
-  explicit FormatValue(const std::pair<A, B>& val) : val_(val) { }
+  explicit FormatValue(const std::pair<A, B>& val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     int key = arg.splitIntKey();
     switch (key) {
-    case 0:
-      FormatValue<typename std::decay<A>::type>(val_.first).format(arg, cb);
-      break;
-    case 1:
-      FormatValue<typename std::decay<B>::type>(val_.second).format(arg, cb);
-      break;
-    default:
-      arg.error("invalid index for pair");
+      case 0:
+        FormatValue<typename std::decay<A>::type>(val_.first).format(arg, cb);
+        break;
+      case 1:
+        FormatValue<typename std::decay<B>::type>(val_.second).format(arg, cb);
+        break;
+      default:
+        arg.error("invalid index for pair");
     }
   }
 
@@ -1061,14 +1048,15 @@ class FormatValue<std::pair<A, B>> {
 template <class... Args>
 class FormatValue<std::tuple<Args...>> {
   typedef std::tuple<Args...> Tuple;
+
  public:
-  explicit FormatValue(const Tuple& val) : val_(val) { }
+  explicit FormatValue(const Tuple& val) : val_(val) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     int key = arg.splitIntKey();
     arg.enforce(key >= 0, "tuple index must be non-negative");
-    doFormat(key, arg, cb);
+    doFormat(size_t(key), arg, cb);
   }
 
  private:
@@ -1076,7 +1064,7 @@ class FormatValue<std::tuple<Args...>> {
 
   template <size_t K, class Callback>
   typename std::enable_if<K == valueCount>::type
-  doFormatFrom(size_t i, FormatArg& arg, Callback& cb) const {
+  doFormatFrom(size_t i, FormatArg& arg, Callback& /* cb */) const {
     arg.enforce("tuple index out of range, max=", i);
   }
 
@@ -1085,10 +1073,10 @@ class FormatValue<std::tuple<Args...>> {
   doFormatFrom(size_t i, FormatArg& arg, Callback& cb) const {
     if (i == K) {
       FormatValue<typename std::decay<
-        typename std::tuple_element<K, Tuple>::type>::type>(
-          std::get<K>(val_)).format(arg, cb);
+          typename std::tuple_element<K, Tuple>::type>::type>(std::get<K>(val_))
+          .format(arg, cb);
     } else {
-      doFormatFrom<K+1>(i, arg, cb);
+      doFormatFrom<K + 1>(i, arg, cb);
     }
   }
 
@@ -1101,16 +1089,21 @@ class FormatValue<std::tuple<Args...>> {
 };
 
 // Partial specialization of FormatValue for nested Formatters
-template <bool containerMode, class... Args>
-class FormatValue<Formatter<containerMode, Args...>, void> {
-  typedef Formatter<containerMode, Args...> FormatterValue;
+template <bool containerMode, class... Args, template <bool, class...> class F>
+class FormatValue<
+    F<containerMode, Args...>,
+    typename std::enable_if<
+        detail::IsFormatter<F<containerMode, Args...>>::value>::type> {
+  typedef typename F<containerMode, Args...>::BaseType FormatterValue;
+
  public:
-  explicit FormatValue(const FormatterValue& f) : f_(f) { }
+  explicit FormatValue(const FormatterValue& f) : f_(f) {}
 
   template <class FormatCallback>
   void format(FormatArg& arg, FormatCallback& cb) const {
     format_value::formatFormatter(f_, arg, cb);
   }
+
  private:
   const FormatterValue& f_;
 };
@@ -1119,11 +1112,13 @@ class FormatValue<Formatter<containerMode, Args...>, void> {
  * Formatter objects can be appended to strings, and therefore they're
  * compatible with folly::toAppend and folly::to.
  */
-template <class Tgt, bool containerMode, class... Args>
-typename std::enable_if<
-   IsSomeString<Tgt>::value>::type
-toAppend(const Formatter<containerMode, Args...>& value, Tgt * result) {
+template <class Tgt, class Derived, bool containerMode, class... Args>
+typename std::enable_if<IsSomeString<Tgt>::value>::type toAppend(
+    const BaseFormatter<Derived, containerMode, Args...>& value,
+    Tgt* result) {
   value.appendTo(*result);
 }
 
-}  // namespace folly
+} // namespace folly
+
+FOLLY_POP_WARNING