layout: Make line breaking able to restart from any position.

This commit removes the "merge-fragments" pass from inline reflow,
instead merging "on the fly". This ended up being simpler, as well as
more fine grained. Additionally, this patch makes the line breaker no
longer clone every fragment (!)

This functionality will be used in the implementation of
`text-overflow`.

1 files changed, 88 insertions, 68 deletions

diff --git a/components/layout/inline.rs b/components/layout/inline.rs
index 89b65b22fb6..370d7e325d9 100644
--- a/components/layout/inline.rs
+++ b/components/layout/inline.rs
@@ -169,7 +169,9 @@ bitflags! {
 struct LineBreaker {
     /// The floats we need to flow around.
     floats: Floats,
+    /// The resulting fragment list for the flow, consisting of possibly-broken fragments.
     new_fragments: Vec<Fragment>,
+    /// The next fragment or fragments that we need to work on.
     work_list: RingBuf<Fragment>,
     /// The line we're currently working on.
     pending_line: Line,
@@ -222,9 +224,31 @@ impl LineBreaker {
     fn scan_for_lines(&mut self, flow: &mut InlineFlow, layout_context: &LayoutContext) {
         self.reset_scanner();
 
+        // Create our fragment iterator.
         debug!("LineBreaker: scanning for lines, {} fragments", flow.fragments.len());
         let mut old_fragments = mem::replace(&mut flow.fragments, InlineFragments::new());
-        self.reflow_fragments(old_fragments.fragments.iter(), flow, layout_context);
+        let mut old_fragment_iter = old_fragments.fragments.into_iter();
+
+        // Set up our initial line state with the clean lines from a previous reflow.
+        //
+        // TODO(pcwalton): This would likely be better as a list of dirty line indices. That way we
+        // could resynchronize if we discover during reflow that all subsequent fragments must have
+        // the same position as they had in the previous reflow. I don't know how common this case
+        // really is in practice, but it's probably worth handling.
+        self.lines = mem::replace(&mut flow.lines, Vec::new());
+        match self.lines.as_slice().last() {
+            None => {}
+            Some(last_line) => {
+                for _ in range(FragmentIndex(0), last_line.range.end()) {
+                    self.new_fragments.push(old_fragment_iter.next().unwrap())
+                }
+            }
+        }
+
+        // Do the reflow.
+        self.reflow_fragments(old_fragment_iter, flow, layout_context);
+
+        // Place the fragments back into the flow.
         old_fragments.fragments = mem::replace(&mut self.new_fragments, vec![]);
         flow.fragments = old_fragments;
         flow.lines = mem::replace(&mut self.lines, Vec::new());
@@ -235,22 +259,13 @@ impl LineBreaker {
                               mut old_fragment_iter: I,
                               flow: &'a InlineFlow,
                               layout_context: &LayoutContext)
-                              where I: Iterator<&'a Fragment> {
+                              where I: Iterator<Fragment> {
         loop {
             // Acquire the next fragment to lay out from the work list or fragment list, as
             // appropriate.
-            let fragment = if self.work_list.is_empty() {
-                match old_fragment_iter.next() {
-                    None => break,
-                    Some(fragment) => {
-                        debug!("LineBreaker: working with fragment from flow: {}", fragment);
-                        (*fragment).clone()
-                    }
-                }
-            } else {
-                debug!("LineBreaker: working with fragment from work list: {}",
-                       self.work_list.front());
-                self.work_list.pop_front().unwrap()
+            let fragment = match self.next_unbroken_fragment(&mut old_fragment_iter) {
+                None => break,
+                Some(fragment) => fragment,
             };
 
             // Set up our reflow flags.
@@ -289,6 +304,65 @@ impl LineBreaker {
         }
     }
 
+    /// Acquires a new fragment to lay out from the work list or fragment list as appropriate.
+    /// Note that you probably don't want to call this method directly in order to be
+    /// incremental-reflow-safe; try `next_unbroken_fragment` instead.
+    fn next_fragment<I>(&mut self, old_fragment_iter: &mut I) -> Option<Fragment>
+                        where I: Iterator<Fragment> {
+        if self.work_list.is_empty() {
+            return match old_fragment_iter.next() {
+                None => None,
+                Some(fragment) => {
+                    debug!("LineBreaker: working with fragment from flow: {}", fragment);
+                    Some(fragment)
+                }
+            }
+        }
+
+        debug!("LineBreaker: working with fragment from work list: {}", self.work_list.front());
+        self.work_list.pop_front()
+    }
+
+    /// Acquires a new fragment to lay out from the work list or fragment list, merging it with any
+    /// subsequent fragments as appropriate. In effect, what this method does is to return the next
+    /// fragment to lay out, undoing line break operations that any previous reflows may have
+    /// performed. You probably want to be using this method instead of `next_fragment`.
+    fn next_unbroken_fragment<I>(&mut self, old_fragment_iter: &mut I) -> Option<Fragment>
+                                 where I: Iterator<Fragment> {
+        let mut result = match self.next_fragment(old_fragment_iter) {
+            None => return None,
+            Some(fragment) => fragment,
+        };
+
+        loop {
+            // FIXME(pcwalton): Yuck! I hate this `new_line_pos` stuff. Can we avoid having to do
+            // this?
+            result.restore_new_line_pos();
+
+            let candidate = match self.next_fragment(old_fragment_iter) {
+                None => return Some(result),
+                Some(fragment) => fragment,
+            };
+
+            let need_to_merge = match (&mut result.specific, &candidate.specific) {
+                (&ScannedTextFragment(ref mut result_info),
+                 &ScannedTextFragment(ref candidate_info))
+                    if arc_ptr_eq(&result_info.run, &candidate_info.run) &&
+                        result_info.range.end() + CharIndex(1) == candidate_info.range.begin() => {
+                    // We found a previously-broken fragment. Merge it up.
+                    result_info.range.extend_by(candidate_info.range.length() + CharIndex(1));
+                    true
+                }
+                _ => false,
+            };
+
+            if !need_to_merge {
+                self.work_list.push_front(candidate);
+                return Some(result)
+            }
+        }
+    }
+
     /// Commits a line to the list.
     fn flush_current_line(&mut self) {
         debug!("LineBreaker: flushing line {}: {}", self.lines.len(), self.pending_line);
@@ -637,58 +711,6 @@ impl InlineFragments {
     pub fn get_mut<'a>(&'a mut self, index: uint) -> &'a mut Fragment {
         &mut self.fragments[index]
     }
-
-    /// This function merges previously-line-broken fragments back into their
-    /// original, pre-line-breaking form.
-    pub fn merge_broken_lines(&mut self) {
-        let mut work: RingBuf<Fragment> =
-            mem::replace(&mut self.fragments, Vec::new()).into_iter().collect();
-
-        let mut out: Vec<Fragment> = Vec::new();
-
-        loop {
-            let mut left: Fragment =
-                match work.pop_front() {
-                    None       => break,
-                    Some(work) => work,
-                };
-
-            let right: Fragment =
-                match work.pop_front() {
-                    None => {
-                        out.push(left);
-                        break;
-                    }
-                    Some(work) => work,
-                };
-
-            left.restore_new_line_pos();
-
-            let right_is_from_same_fragment =
-                match (&mut left.specific, &right.specific) {
-                    (&ScannedTextFragment(ref mut left_info),
-                     &ScannedTextFragment(ref right_info)) => {
-                        if arc_ptr_eq(&left_info.run, &right_info.run)
-                        && left_info.range.end() + CharIndex(1) == right_info.range.begin() {
-                            left_info.range.extend_by(right_info.range.length() + CharIndex(1));
-                            true
-                        } else {
-                            false
-                        }
-                    }
-                    _ => false,
-                };
-
-            if right_is_from_same_fragment {
-                work.push_front(left);
-            } else {
-                out.push(left);
-                work.push_front(right);
-            }
-        }
-
-        mem::replace(&mut self.fragments, out);
-    }
 }
 
 /// Flows for inline layout.
@@ -1016,8 +1038,6 @@ impl Flow for InlineFlow {
         // Reset our state, so that we handle incremental reflow correctly.
         //
         // TODO(pcwalton): Do something smarter, like Gecko and WebKit?
-        debug!("lines: {}", self.lines);
-        self.fragments.merge_broken_lines();
         self.lines = Vec::new();
 
         // Determine how much indentation the first line wants.