Split off binary search

4 files changed, 98 insertions, 57 deletions

diff --git a/src/expr.rs b/src/expr.rs
index 08acd5de67d..e3146170f82 100644
--- a/src/expr.rs
+++ b/src/expr.rs
@@ -14,7 +14,8 @@ use rewrite::{Rewrite, RewriteContext};
 use lists::{write_list, itemize_list, ListFormatting, SeparatorTactic, ListTactic};
 use string::{StringFormat, rewrite_string};
 use StructLitStyle;
-use utils::{span_after, make_indent, extra_offset, first_line_width, last_line_width, wrap_str};
+use utils::{span_after, make_indent, extra_offset, first_line_width, last_line_width, wrap_str,
+            binary_search};
 use visitor::FmtVisitor;
 use config::BlockIndentStyle;
 use comment::{FindUncommented, rewrite_comment, contains_comment};
@@ -842,31 +843,19 @@ fn rewrite_call(context: &RewriteContext,
                 width: usize,
                 offset: usize)
                 -> Option<String> {
-    debug!("rewrite_call, width: {}, offset: {}", width, offset);
+    let callback = |callee_max_width| {
+                       rewrite_call_inner(context,
+                                          callee,
+                                          callee_max_width,
+                                          args,
+                                          span,
+                                          width,
+                                          offset)
+                   };
 
     // 2 is for parens
-    let mut hi = try_opt!(width.checked_sub(2)) * 2;
-    let mut lo = 0;
-    let mut tries = 0;
-
-    // Binary search for the best split between callee and arguments.
-    loop {
-        let middle = (lo + hi) / 2;
-
-        match rewrite_call_inner(context, callee, middle, args, span, width, offset) {
-            _ if tries > 10 => return None,
-            Ok(result) => return Some(result),
-            Err(Ordering::Less) => {
-                lo = middle;
-                tries += 1;
-            }
-            Err(Ordering::Greater) => {
-                hi = middle;
-                tries += 1;
-            }
-            _ => unreachable!(),
-        }
-    }
+    let max_width = try_opt!(width.checked_sub(2));
+    binary_search(1, max_width, callback)
 }
 
 fn rewrite_call_inner(context: &RewriteContext,
@@ -877,7 +866,8 @@ fn rewrite_call_inner(context: &RewriteContext,
                       width: usize,
                       offset: usize)
                       -> Result<String, Ordering> {
-    // FIXME using byte lens instead of char lens (and probably all over the place too)
+    // FIXME using byte lens instead of char lens (and probably all over the
+    // place too)
     let callee_str = match callee.rewrite(context, max_callee_width, offset) {
         Some(string) => {
             if !string.contains('\n') && string.len() > max_callee_width {
@@ -886,9 +876,8 @@ fn rewrite_call_inner(context: &RewriteContext,
                 string
             }
         }
-        None => return Err(Ordering::Less),
+        None => return Err(Ordering::Greater),
     };
-    debug!("rewrite_call, callee_str: `{}`", callee_str);
 
     let extra_offset = extra_offset(&callee_str, offset);
     // 2 is for parens.
@@ -916,7 +905,7 @@ fn rewrite_call_inner(context: &RewriteContext,
     let fmt = ListFormatting::for_fn(remaining_width, offset);
     let list_str = match write_list(&items.collect::<Vec<_>>(), &fmt) {
         Some(str) => str,
-        None => return Err(Ordering::Greater),
+        None => return Err(Ordering::Less),
     };
 
     Ok(format!("{}({})", callee_str, list_str))
diff --git a/src/lists.rs b/src/lists.rs
index e21327631d4..cf68d86dd2b 100644
--- a/src/lists.rs
+++ b/src/lists.rs
@@ -204,8 +204,8 @@ pub fn write_list<'b>(items: &[ListItem], formatting: &ListFormatting<'b>) -> Op
             }
         }
 
-        // FIXME: no magic numbers!
-        let item_str = wrap_str(&item.item[..], 100, formatting.v_width, formatting.indent);
+        let max_width = formatting.indent + formatting.v_width;
+        let item_str = wrap_str(&item.item[..], max_width, formatting.v_width, formatting.indent);
         result.push_str(&&try_opt!(item_str));
 
         // Post-comments
diff --git a/src/types.rs b/src/types.rs
index 58bb930510c..dace1d84bca 100644
--- a/src/types.rs
+++ b/src/types.rs
@@ -218,9 +218,14 @@ fn rewrite_segment(segment: &ast::PathSegment,
                                      ">",
                                      |param| param.get_span().lo,
                                      |param| param.get_span().hi,
-                                     // FIXME: need better params
+                                     // FIXME(#133): write_list should call
+                                     // rewrite itself, because it has a better
+                                     // context.
                                      |seg| {
-                                         seg.rewrite(context, 1000, offset + extra_offset).unwrap()
+                                         seg.rewrite(context,
+                                                     context.config.max_width,
+                                                     offset + extra_offset)
+                                            .unwrap()
                                      },
                                      list_lo,
                                      span_hi);
@@ -228,7 +233,7 @@ fn rewrite_segment(segment: &ast::PathSegment,
             let fmt = ListFormatting::for_fn(list_width, offset + extra_offset);
             let list_str = try_opt!(write_list(&items.collect::<Vec<_>>(), &fmt));
 
-            // update pos
+            // Update position of last bracket.
             *span_lo = next_span_lo;
 
             format!("{}<{}>", separator, list_str)
@@ -256,9 +261,6 @@ fn rewrite_segment(segment: &ast::PathSegment,
             let fmt = ListFormatting::for_fn(budget, offset + 1);
             let list_str = try_opt!(write_list(&items.collect::<Vec<_>>(), &fmt));
 
-            // update pos
-            *span_lo = data.span.hi + BytePos(1);
-
             format!("({}){}", list_str, output)
         }
         _ => String::new(),
diff --git a/src/utils.rs b/src/utils.rs
index 07807bf31aa..94f8fec2b0d 100644
--- a/src/utils.rs
+++ b/src/utils.rs
@@ -8,6 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+use std::cmp::Ordering;
+
 use syntax::ast::{self, Visibility, Attribute, MetaItem, MetaItem_};
 use syntax::codemap::{CodeMap, Span, BytePos};
 
@@ -164,38 +166,86 @@ macro_rules! try_opt {
     })
 }
 
+// Wraps string-like values in an Option. Returns Some when the string adheres
+// to the Rewrite constraints defined for the Rewrite trait and else otherwise.
 pub fn wrap_str<S: AsRef<str>>(s: S, max_width: usize, width: usize, offset: usize) -> Option<S> {
-    let snippet = s.as_ref();
-
-    if !snippet.contains('\n') && snippet.len() > width {
-        return None;
-    } else {
-        let mut lines = snippet.lines();
+    {
+        let snippet = s.as_ref();
 
-        // The caller of this function has already placed `offset`
-        // characters on the first line.
-        let first_line_max_len = try_opt!(max_width.checked_sub(offset));
-        if lines.next().unwrap().len() > first_line_max_len {
+        if !snippet.contains('\n') && snippet.len() > width {
             return None;
-        }
+        } else {
+            let mut lines = snippet.lines();
+
+            // The caller of this function has already placed `offset`
+            // characters on the first line.
+            let first_line_max_len = try_opt!(max_width.checked_sub(offset));
+            if lines.next().unwrap().len() > first_line_max_len {
+                return None;
+            }
 
-        // The other lines must fit within the maximum width.
-        if lines.find(|line| line.len() > max_width).is_some() {
-            return None;
-        }
+            // The other lines must fit within the maximum width.
+            if lines.find(|line| line.len() > max_width).is_some() {
+                return None;
+            }
 
-        // `width` is the maximum length of the last line, excluding
-        // indentation.
-        // A special check for the last line, since the caller may
-        // place trailing characters on this line.
-        if snippet.lines().rev().next().unwrap().len() > offset + width {
-            return None;
+            // `width` is the maximum length of the last line, excluding
+            // indentation.
+            // A special check for the last line, since the caller may
+            // place trailing characters on this line.
+            if snippet.lines().rev().next().unwrap().len() > offset + width {
+                return None;
+            }
         }
     }
 
     Some(s)
 }
 
+// Binary search in integer range. Returns the first Ok value returned by the
+// callback.
+// The callback takes an integer and returns either an Ok, or an Err indicating
+// whether the `guess' was too high (Ordering::Less), or too low.
+// This function is guaranteed to try to the hi value first.
+pub fn binary_search<C, T>(mut lo: usize, mut hi: usize, callback: C) -> Option<T>
+    where C: Fn(usize) -> Result<T, Ordering>
+{
+    let mut middle = hi;
+
+    while lo <= hi {
+        match callback(middle) {
+            Ok(val) => return Some(val),
+            Err(Ordering::Less) => {
+                hi = middle - 1;
+            }
+            Err(..) => {
+                lo = middle + 1;
+            }
+        }
+        middle = (hi + lo) / 2;
+    }
+
+    None
+}
+
+#[test]
+fn bin_search_test() {
+    let closure = |i| {
+                      match i {
+                          4 => Ok(()),
+                          j if j > 4 => Err(Ordering::Less),
+                          j if j < 4 => Err(Ordering::Greater),
+                          _ => unreachable!(),
+                      }
+                  };
+
+    assert_eq!(Some(()), binary_search(1, 10, &closure));
+    assert_eq!(None, binary_search(1, 3, &closure));
+    assert_eq!(Some(()), binary_search(0, 44, &closure));
+    assert_eq!(Some(()), binary_search(4, 125, &closure));
+    assert_eq!(None, binary_search(6, 100, &closure));
+}
+
 #[test]
 fn power_rounding() {
     assert_eq!(0, round_up_to_power_of_two(0));