auto merge of #5463 : alexcrichton/rust/faster-fmt, r=graydon

This is a minor step towards #3571, although I'm sure there's still more work to be done. Previously, `fmt!` collected a bunch of strings in a vector and then called `str::concat`. This changes the behavior by maintaining only one buffer and appending directly into that buffer. This avoids doubly-allocating memory, and it has the added bonus of reducing some allocations in `core::unstable::extfmt`

One of the unfortunate side effects of this is that the `rt` module in `extfmt.rs` had to be duplicated to avoid `stage0` errors. Dealing with the change in conversion functions may require a bit of a dance when a snapshot happens, but I think it's doable.

If the second speedup commit isn't deemed necessary, I got about a 15% speedup with just the first patch which doesn't require any modification of `extfmt.rs`, so no snapshot weirdness.

Here's some other things I ran into when looking at `fmt!`:
* I don't think that #2249 is relevant any more except for maybe removing one of `%i` or `%d`
* I'm not sure what was in mind for using traits with #3571, but I thought that formatters like `%u` could invoke the `to_uint()` method on the `NumCast` trait, but I ran into some problems like those in #5462

I'm having trouble thinking of other wins for `fmt!`, but if there's some suggestions I'd be more than willing to look into if they'd work out or not.

2 files changed, 72 insertions, 57 deletions

diff --git a/src/libsyntax/ext/build.rs b/src/libsyntax/ext/build.rs
index 18c7cd3f861..c2f4cbf3db2 100644
--- a/src/libsyntax/ext/build.rs
+++ b/src/libsyntax/ext/build.rs
@@ -108,6 +108,9 @@ pub fn mk_access(cx: @ext_ctxt, sp: span, +p: ~[ast::ident], m: ast::ident)
 pub fn mk_addr_of(cx: @ext_ctxt, sp: span, e: @ast::expr) -> @ast::expr {
     return mk_expr(cx, sp, ast::expr_addr_of(ast::m_imm, e));
 }
+pub fn mk_mut_addr_of(cx: @ext_ctxt, sp: span, e: @ast::expr) -> @ast::expr {
+    return mk_expr(cx, sp, ast::expr_addr_of(ast::m_mutbl, e));
+}
 pub fn mk_call_(cx: @ext_ctxt, sp: span, fn_expr: @ast::expr,
                 +args: ~[@ast::expr]) -> @ast::expr {
     mk_expr(cx, sp, ast::expr_call(fn_expr, args, ast::NoSugar))
diff --git a/src/libsyntax/ext/fmt.rs b/src/libsyntax/ext/fmt.rs
index 9973c9558c9..3ebe844950a 100644
--- a/src/libsyntax/ext/fmt.rs
+++ b/src/libsyntax/ext/fmt.rs
@@ -139,19 +139,17 @@ fn pieces_to_expr(cx: @ext_ctxt, sp: span,
         make_conv_struct(cx, sp, rt_conv_flags, rt_conv_width,
                          rt_conv_precision, rt_conv_ty)
     }
-    fn make_conv_call(cx: @ext_ctxt, sp: span, conv_type: ~str, cnv: &Conv,
-                      arg: @ast::expr) -> @ast::expr {
+    fn make_conv_call(cx: @ext_ctxt, sp: span, conv_type: &str, cnv: &Conv,
+                      arg: @ast::expr, buf: @ast::expr) -> @ast::expr {
         let fname = ~"conv_" + conv_type;
         let path = make_path_vec(cx, @fname);
         let cnv_expr = make_rt_conv_expr(cx, sp, cnv);
-        let args = ~[cnv_expr, arg];
+        let args = ~[cnv_expr, arg, buf];
         return mk_call_global(cx, arg.span, path, args);
     }
 
-    fn make_new_conv(cx: @ext_ctxt, sp: span, cnv: &Conv, arg: @ast::expr) ->
-       @ast::expr {
-        // FIXME: Move validation code into core::extfmt (Issue #2249)
-
+    fn make_new_conv(cx: @ext_ctxt, sp: span, cnv: &Conv,
+                     arg: @ast::expr, buf: @ast::expr) -> @ast::expr {
         fn is_signed_type(cnv: &Conv) -> bool {
             match cnv.ty {
               TyInt(s) => match s {
@@ -198,29 +196,20 @@ fn pieces_to_expr(cx: @ext_ctxt, sp: span,
           CountIs(_) => (),
           _ => cx.span_unimpl(sp, unsupported)
         }
-        match cnv.ty {
-          TyStr => return make_conv_call(cx, arg.span, ~"str", cnv, arg),
-          TyInt(sign) => match sign {
-            Signed => return make_conv_call(cx, arg.span, ~"int", cnv, arg),
-            Unsigned => {
-                return make_conv_call(cx, arg.span, ~"uint", cnv, arg)
-            }
-          },
-          TyBool => return make_conv_call(cx, arg.span, ~"bool", cnv, arg),
-          TyChar => return make_conv_call(cx, arg.span, ~"char", cnv, arg),
-          TyHex(_) => {
-            return make_conv_call(cx, arg.span, ~"uint", cnv, arg);
-          }
-          TyBits => return make_conv_call(cx, arg.span, ~"uint", cnv, arg),
-          TyOctal => return make_conv_call(cx, arg.span, ~"uint", cnv, arg),
-          TyFloat => {
-            return make_conv_call(cx, arg.span, ~"float", cnv, arg);
-          }
-          TyPoly => return make_conv_call(cx, arg.span, ~"poly", cnv,
-                       mk_addr_of(cx, sp, arg))
-        }
+        let (name, actual_arg) = match cnv.ty {
+            TyStr => ("str", arg),
+            TyInt(Signed) => ("int", arg),
+            TyBool => ("bool", arg),
+            TyChar => ("char", arg),
+            TyBits | TyOctal | TyHex(_) | TyInt(Unsigned) => ("uint", arg),
+            TyFloat => ("float", arg),
+            TyPoly => ("poly", mk_addr_of(cx, sp, arg))
+        };
+        return make_conv_call(cx, arg.span, name, cnv, actual_arg,
+                              mk_mut_addr_of(cx, arg.span, buf));
     }
     fn log_conv(c: &Conv) {
+        debug!("Building conversion:");
         match c.param {
           Some(p) => { debug!("param: %s", p.to_str()); }
           _ => debug!("param: none")
@@ -268,49 +257,72 @@ fn pieces_to_expr(cx: @ext_ctxt, sp: span,
           TyPoly => debug!("type: poly")
         }
     }
+
     let fmt_sp = args[0].span;
     let mut n = 0u;
-    let mut piece_exprs = ~[];
     let nargs = args.len();
-    for pieces.each |pc| {
-        match *pc {
-          PieceString(ref s) => {
-            piece_exprs.push(mk_uniq_str(cx, fmt_sp, copy *s))
-          }
-          PieceConv(ref conv) => {
-            n += 1u;
-            if n >= nargs {
-                cx.span_fatal(sp,
-                              ~"not enough arguments to fmt! " +
+
+    /* 'ident' is the local buffer building up the result of fmt! */
+    let ident = cx.parse_sess().interner.intern(@~"__fmtbuf");
+    let buf = || mk_path(cx, fmt_sp, ~[ident]);
+    let str_ident = cx.parse_sess().interner.intern(@~"str");
+    let push_ident = cx.parse_sess().interner.intern(@~"push_str");
+    let mut stms = ~[];
+
+    /* Translate each piece (portion of the fmt expression) by invoking the
+       corresponding function in core::unstable::extfmt. Each function takes a
+       buffer to insert data into along with the data being formatted. */
+    do vec::consume(pieces) |i, pc| {
+        match pc {
+            /* Raw strings get appended via str::push_str */
+            PieceString(s) => {
+                let portion = mk_uniq_str(cx, fmt_sp, s);
+
+                /* If this is the first portion, then initialize the local
+                   buffer with it directly */
+                if i == 0 {
+                    stms.push(mk_local(cx, fmt_sp, true, ident, portion));
+                } else {
+                    let args = ~[mk_mut_addr_of(cx, fmt_sp, buf()), portion];
+                    let call = mk_call_global(cx,
+                                              fmt_sp,
+                                              ~[str_ident, push_ident],
+                                              args);
+                    stms.push(mk_stmt(cx, fmt_sp, call));
+                }
+            }
+
+            /* Invoke the correct conv function in extfmt */
+            PieceConv(ref conv) => {
+                n += 1u;
+                if n >= nargs {
+                    cx.span_fatal(sp,
+                                  ~"not enough arguments to fmt! " +
                                   ~"for the given format string");
+                }
+
+                log_conv(conv);
+                /* If the first portion is a conversion, then the local buffer
+                   must be initialized as an empty string */
+                if i == 0 {
+                    stms.push(mk_local(cx, fmt_sp, true, ident,
+                                       mk_uniq_str(cx, fmt_sp, ~"")));
+                }
+                stms.push(mk_stmt(cx, fmt_sp,
+                                  make_new_conv(cx, fmt_sp, conv,
+                                                args[n], buf())));
             }
-            debug!("Building conversion:");
-            log_conv(conv);
-            let arg_expr = args[n];
-            let c_expr = make_new_conv(
-                cx,
-                fmt_sp,
-                conv,
-                arg_expr
-            );
-            piece_exprs.push(c_expr);
-          }
         }
     }
-    let expected_nargs = n + 1u; // n conversions + the fmt string
 
+    let expected_nargs = n + 1u; // n conversions + the fmt string
     if expected_nargs < nargs {
         cx.span_fatal
             (sp, fmt!("too many arguments to fmt!. found %u, expected %u",
                            nargs, expected_nargs));
     }
 
-    let arg_vec = mk_fixed_vec_e(cx, fmt_sp, piece_exprs);
-    return mk_call_global(cx,
-                          fmt_sp,
-                          ~[cx.parse_sess().interner.intern(@~"str"),
-                            cx.parse_sess().interner.intern(@~"concat")],
-                          ~[arg_vec]);
+    return mk_block(cx, fmt_sp, ~[], stms, Some(buf()));
 }
 //
 // Local Variables: