layout: Implement `text-align: justify` and `text-justify` per

CSS-TEXT-3 § 7.3.

`text-justify: distribute` is not supported.

The behavior of `text-justify: none` does not seem to match what Firefox
and Chrome do, but it seems to match the spec.

Closes #213.

2 files changed, 254 insertions, 43 deletions

diff --git a/components/layout/fragment.rs b/components/layout/fragment.rs
index 281eeaaa5d2..2b802c43cdd 100644
--- a/components/layout/fragment.rs
+++ b/components/layout/fragment.rs
@@ -598,9 +598,10 @@ pub struct SplitInfo {
 
 impl SplitInfo {
     fn new(range: Range<CharIndex>, info: &ScannedTextFragmentInfo) -> SplitInfo {
+        let inline_size = info.run.advance_for_range(&range);
         SplitInfo {
             range: range,
-            inline_size: info.run.advance_for_range(&range),
+            inline_size: inline_size,
         }
     }
 }
@@ -1169,7 +1170,9 @@ impl Fragment {
     pub fn inline_start_offset(&self) -> Au {
         match self.specific {
             SpecificFragmentInfo::TableWrapper => self.margin.inline_start,
-            SpecificFragmentInfo::Table | SpecificFragmentInfo::TableCell | SpecificFragmentInfo::TableRow => self.border_padding.inline_start,
+            SpecificFragmentInfo::Table |
+            SpecificFragmentInfo::TableCell |
+            SpecificFragmentInfo::TableRow => self.border_padding.inline_start,
             SpecificFragmentInfo::TableColumn(_) => Au(0),
             _ => self.margin.inline_start + self.border_padding.inline_start,
         }
@@ -1208,9 +1211,12 @@ impl Fragment {
     pub fn compute_intrinsic_inline_sizes(&mut self) -> IntrinsicISizesContribution {
         let mut result = self.style_specified_intrinsic_inline_size();
         match self.specific {
-            SpecificFragmentInfo::Generic | SpecificFragmentInfo::Iframe(_) |
-            SpecificFragmentInfo::Table | SpecificFragmentInfo::TableCell |
-            SpecificFragmentInfo::TableColumn(_) | SpecificFragmentInfo::TableRow |
+            SpecificFragmentInfo::Generic |
+            SpecificFragmentInfo::Iframe(_) |
+            SpecificFragmentInfo::Table |
+            SpecificFragmentInfo::TableCell |
+            SpecificFragmentInfo::TableColumn(_) |
+            SpecificFragmentInfo::TableRow |
             SpecificFragmentInfo::TableWrapper |
             SpecificFragmentInfo::InlineAbsoluteHypothetical(_) => {}
             SpecificFragmentInfo::InlineBlock(ref mut info) => {
@@ -1274,8 +1280,13 @@ impl Fragment {
     /// TODO: What exactly does this function return? Why is it Au(0) for SpecificFragmentInfo::Generic?
     pub fn content_inline_size(&self) -> Au {
         match self.specific {
-            SpecificFragmentInfo::Generic | SpecificFragmentInfo::Iframe(_) | SpecificFragmentInfo::Table | SpecificFragmentInfo::TableCell |
-            SpecificFragmentInfo::TableRow | SpecificFragmentInfo::TableWrapper | SpecificFragmentInfo::InlineBlock(_) |
+            SpecificFragmentInfo::Generic |
+            SpecificFragmentInfo::Iframe(_) |
+            SpecificFragmentInfo::Table |
+            SpecificFragmentInfo::TableCell |
+            SpecificFragmentInfo::TableRow |
+            SpecificFragmentInfo::TableWrapper |
+            SpecificFragmentInfo::InlineBlock(_) |
             SpecificFragmentInfo::InlineAbsoluteHypothetical(_) => Au(0),
             SpecificFragmentInfo::Canvas(ref canvas_fragment_info) => {
                 canvas_fragment_info.replaced_image_fragment_info.computed_inline_size()
@@ -1288,16 +1299,25 @@ impl Fragment {
                 let text_bounds = run.metrics_for_range(range).bounding_box;
                 text_bounds.size.width
             }
-            SpecificFragmentInfo::TableColumn(_) => panic!("Table column fragments do not have inline_size"),
-            SpecificFragmentInfo::UnscannedText(_) => panic!("Unscanned text fragments should have been scanned by now!"),
+            SpecificFragmentInfo::TableColumn(_) => {
+                panic!("Table column fragments do not have inline_size")
+            }
+            SpecificFragmentInfo::UnscannedText(_) => {
+                panic!("Unscanned text fragments should have been scanned by now!")
+            }
         }
     }
 
     /// Returns, and computes, the block-size of this fragment.
     pub fn content_block_size(&self, layout_context: &LayoutContext) -> Au {
         match self.specific {
-            SpecificFragmentInfo::Generic | SpecificFragmentInfo::Iframe(_) | SpecificFragmentInfo::Table | SpecificFragmentInfo::TableCell |
-            SpecificFragmentInfo::TableRow | SpecificFragmentInfo::TableWrapper | SpecificFragmentInfo::InlineBlock(_) |
+            SpecificFragmentInfo::Generic |
+            SpecificFragmentInfo::Iframe(_) |
+            SpecificFragmentInfo::Table |
+            SpecificFragmentInfo::TableCell |
+            SpecificFragmentInfo::TableRow |
+            SpecificFragmentInfo::TableWrapper |
+            SpecificFragmentInfo::InlineBlock(_) |
             SpecificFragmentInfo::InlineAbsoluteHypothetical(_) => Au(0),
             SpecificFragmentInfo::Image(ref image_fragment_info) => {
                 image_fragment_info.replaced_image_fragment_info.computed_block_size()
@@ -1309,8 +1329,12 @@ impl Fragment {
                 // Compute the block-size based on the line-block-size and font size.
                 self.calculate_line_height(layout_context)
             }
-            SpecificFragmentInfo::TableColumn(_) => panic!("Table column fragments do not have block_size"),
-            SpecificFragmentInfo::UnscannedText(_) => panic!("Unscanned text fragments should have been scanned by now!"),
+            SpecificFragmentInfo::TableColumn(_) => {
+                panic!("Table column fragments do not have block_size")
+            }
+            SpecificFragmentInfo::UnscannedText(_) => {
+                panic!("Unscanned text fragments should have been scanned by now!")
+            }
         }
     }
 
@@ -1463,7 +1487,8 @@ impl Fragment {
                                                               max_inline_size: Au,
                                                               flags: SplitOptions)
                                                               -> Option<SplitResult>
-                                                              where I: Iterator<Item=TextRunSlice<'a>> {
+                                                              where I: Iterator<Item=
+                                                                                TextRunSlice<'a>> {
         let text_fragment_info =
             if let SpecificFragmentInfo::ScannedText(ref text_fragment_info) = self.specific {
                 text_fragment_info
@@ -1475,6 +1500,7 @@ impl Fragment {
         let mut remaining_inline_size = max_inline_size;
         let mut inline_start_range = Range::new(text_fragment_info.range.begin(), CharIndex(0));
         let mut inline_end_range = None;
+        let mut overflowing = false;
 
         debug!("calculate_split_position: splitting text fragment (strlen={}, range={:?}, \
                 max_inline_size={:?})",
@@ -1508,12 +1534,23 @@ impl Fragment {
                 continue
             }
 
-            // The advance is more than the remaining inline-size, so split here.
-            let slice_begin = slice.text_run_range().begin();
+            // The advance is more than the remaining inline-size, so split here. First, check to
+            // see if we're going to overflow the line. If so, perform a best-effort split.
+            let mut remaining_range = slice.text_run_range();
+            if inline_start_range.is_empty() {
+                // We're going to overflow the line.
+                overflowing = true;
+                inline_start_range = slice.text_run_range();
+                remaining_range = Range::new(slice.text_run_range().end(), CharIndex(0));
+                remaining_range.extend_to(text_fragment_info.range.end());
+            }
+
+            // Check to see if we need to create an inline-end chunk.
+            let slice_begin = remaining_range.begin();
             if slice_begin < text_fragment_info.range.end() {
                 // There still some things left over at the end of the line, so create the
                 // inline-end chunk.
-                let mut inline_end = slice.text_run_range();
+                let mut inline_end = remaining_range;
                 inline_end.extend_to(text_fragment_info.range.end());
                 inline_end_range = Some(inline_end);
                 debug!("calculate_split_position: splitting remainder with inline-end range={:?}",
@@ -1525,8 +1562,7 @@ impl Fragment {
         }
 
         // If we failed to find a suitable split point, we're on the verge of overflowing the line.
-        let inline_start_is_some = inline_start_range.length() > CharIndex(0);
-        if pieces_processed_count == 1 || !inline_start_is_some {
+        if inline_start_range.is_empty() || overflowing {
             // If we've been instructed to retry at character boundaries (probably via
             // `overflow-wrap: break-word`), do so.
             if flags.contains(RETRY_AT_CHARACTER_BOUNDARIES) {
@@ -1547,7 +1583,38 @@ impl Fragment {
             }
         }
 
-        let inline_start = if inline_start_is_some {
+        // Remove trailing whitespace from the inline-start split, if necessary.
+        //
+        // FIXME(pcwalton): Is there a more clever (i.e. faster) way to do this?
+        strip_trailing_whitespace(&**text_fragment_info.run, &mut inline_start_range);
+
+        // Remove leading whitespace from the inline-end split, if necessary.
+        //
+        // FIXME(pcwalton): Is there a more clever (i.e. faster) way to do this?
+        if let Some(ref mut inline_end_range) = inline_end_range {
+            let inline_end_fragment_text =
+                text_fragment_info.run.text.slice_chars(inline_end_range.begin().to_uint(),
+                                                        inline_end_range.end().to_uint());
+            let mut leading_whitespace_character_count = 0i;
+            for ch in inline_end_fragment_text.chars() {
+                if ch.is_whitespace() {
+                    leading_whitespace_character_count += 1
+                } else {
+                    break
+                }
+            }
+            inline_end_range.adjust_by(CharIndex(leading_whitespace_character_count),
+                                       -CharIndex(leading_whitespace_character_count));
+        }
+
+        // Normalize our split so that the inline-end fragment will never be `Some` while the
+        // inline-start fragment is `None`.
+        if inline_start_range.is_empty() && inline_end_range.is_some() {
+            inline_start_range = inline_end_range.unwrap();
+            inline_end_range = None
+        }
+
+        let inline_start = if !inline_start_range.is_empty() {
             Some(SplitInfo::new(inline_start_range, &**text_fragment_info))
         } else {
             None
@@ -1563,6 +1630,24 @@ impl Fragment {
         })
     }
 
+    /// Attempts to strip trailing whitespace from this fragment by adjusting the text run range.
+    /// Returns true if any modifications were made.
+    pub fn strip_trailing_whitespace_if_necessary(&mut self) -> bool {
+        let text_fragment_info =
+            if let SpecificFragmentInfo::ScannedText(ref mut text_fragment_info) = self.specific {
+                text_fragment_info
+            } else {
+                return false
+            };
+
+        let run = text_fragment_info.run.clone();
+        if strip_trailing_whitespace(&**run, &mut text_fragment_info.range) {
+            self.border_box.size.inline = run.advance_for_range(&text_fragment_info.range);
+            return true
+        }
+        false
+    }
+
     /// Returns true if this fragment is an unscanned text fragment that consists entirely of
     /// whitespace that should be stripped.
     pub fn is_ignorable_whitespace(&self) -> bool {
@@ -1982,3 +2067,25 @@ pub enum CoordinateSystem {
     Self,
 }
 
+/// Given a range and a text run, adjusts the range to eliminate trailing whitespace. Returns true
+/// if any modifications were made.
+fn strip_trailing_whitespace(text_run: &TextRun, range: &mut Range<CharIndex>) -> bool {
+    // FIXME(pcwalton): Is there a more clever (i.e. faster) way to do this?
+    let text = text_run.text.slice_chars(range.begin().to_uint(), range.end().to_uint());
+    let mut trailing_whitespace_character_count = 0i;
+    for ch in text.chars().rev() {
+        if ch.is_whitespace() {
+            trailing_whitespace_character_count += 1
+        } else {
+            break
+        }
+    }
+
+    if trailing_whitespace_character_count == 0 {
+        return false
+    }
+
+    range.extend_by(-CharIndex(trailing_whitespace_character_count));
+    return true
+}
+
diff --git a/components/layout/inline.rs b/components/layout/inline.rs
index ac10e813e77..c864b56e111 100644
--- a/components/layout/inline.rs
+++ b/components/layout/inline.rs
@@ -34,7 +34,8 @@ use std::mem;
 use std::num::ToPrimitive;
 use std::ops::{Add, Sub, Mul, Div, Rem, Neg, Shl, Shr, Not, BitOr, BitAnd, BitXor};
 use std::u16;
-use style::computed_values::{overflow, text_align, text_overflow, vertical_align, white_space};
+use style::computed_values::{overflow, text_align, text_justify, text_overflow, vertical_align};
+use style::computed_values::{white_space};
 use style::ComputedValues;
 use std::sync::Arc;
 
@@ -301,6 +302,18 @@ impl LineBreaker {
                     self.lines.len());
             self.flush_current_line()
         }
+
+        // Strip trailing whitespace from the last line if necessary.
+        if let Some(ref mut last_line) = self.lines.last_mut() {
+            if let Some(ref mut last_fragment) = self.new_fragments.last_mut() {
+                let previous_inline_size = last_line.bounds.size.inline -
+                    last_fragment.border_box.size.inline;
+                if last_fragment.strip_trailing_whitespace_if_necessary() {
+                    last_line.bounds.size.inline = previous_inline_size +
+                        last_fragment.border_box.size.inline;
+                }
+            }
+        }
     }
 
     /// Acquires a new fragment to lay out from the work list or fragment list as appropriate.
@@ -534,7 +547,7 @@ impl LineBreaker {
     /// Tries to append the given fragment to the line, splitting it if necessary. Returns true if
     /// we successfully pushed the fragment to the line or false if we couldn't.
     fn append_fragment_to_line_if_possible(&mut self,
-                                           fragment: Fragment,
+                                           mut fragment: Fragment,
                                            flow: &InlineFlow,
                                            layout_context: &LayoutContext,
                                            flags: InlineReflowFlags)
@@ -546,7 +559,8 @@ impl LineBreaker {
             self.pending_line.green_zone = line_bounds.size;
         }
 
-        debug!("LineBreaker: trying to append to line {} (fragment size: {:?}, green zone: {:?}): {:?}",
+        debug!("LineBreaker: trying to append to line {} (fragment size: {:?}, green zone: {:?}): \
+               {:?}",
                self.lines.len(),
                fragment.border_box.size,
                self.pending_line.green_zone,
@@ -581,7 +595,7 @@ impl LineBreaker {
             debug!("LineBreaker: fragment can't split and line {} is empty, so overflowing",
                     self.lines.len());
             self.push_fragment_to_line(layout_context, fragment);
-            return true
+            return false
         }
 
         // Split it up!
@@ -609,13 +623,15 @@ impl LineBreaker {
         // Push the first fragment onto the line we're working on and start off the next line with
         // the second fragment. If there's no second fragment, the next line will start off empty.
         match (inline_start_fragment, inline_end_fragment) {
-            (Some(inline_start_fragment), Some(inline_end_fragment)) => {
+            (Some(inline_start_fragment), Some(mut inline_end_fragment)) => {
                 self.push_fragment_to_line(layout_context, inline_start_fragment);
+                self.flush_current_line();
                 self.work_list.push_front(inline_end_fragment)
             },
-            (Some(fragment), None) | (None, Some(fragment)) => {
-                self.push_fragment_to_line(layout_context, fragment)
+            (Some(mut fragment), None) => {
+                self.push_fragment_to_line(layout_context, fragment);
             }
+            (None, Some(_)) => debug_assert!(false, "un-normalized split result"),
             (None, None) => {}
         }
 
@@ -856,25 +872,40 @@ impl InlineFlow {
         }
     }
 
-    /// Sets fragment positions in the inline direction based on alignment for one line.
+    /// Sets fragment positions in the inline direction based on alignment for one line. This
+    /// performs text justification if mandated by the style.
     fn set_inline_fragment_positions(fragments: &mut InlineFragments,
                                      line: &Line,
                                      line_align: text_align::T,
-                                     indentation: Au) {
+                                     indentation: Au,
+                                     is_last_line: bool) {
         // Figure out how much inline-size we have.
         let slack_inline_size = max(Au(0), line.green_zone.inline - line.bounds.size.inline);
 
-        // Set the fragment inline positions based on that alignment.
-        let mut inline_start_position_for_fragment = line.bounds.start.i + indentation +
-                match line_align {
-                // So sorry, but justified text is more complicated than shuffling line
-                // coordinates.
-                //
-                // TODO(burg, issue #213): Implement `text-align: justify`.
-                text_align::T::left | text_align::T::justify => Au(0),
-                text_align::T::center => slack_inline_size.scale_by(0.5),
-                text_align::T::right => slack_inline_size,
-            };
+        // Compute the value we're going to use for `text-justify`.
+        let text_justify = if fragments.fragments.is_empty() {
+            return
+        } else {
+            fragments.fragments[0].style().get_inheritedtext().text_justify
+        };
+
+        // Set the fragment inline positions based on that alignment, and justify the text if
+        // necessary.
+        let mut inline_start_position_for_fragment = line.bounds.start.i + indentation;
+        match line_align {
+            text_align::T::justify if !is_last_line && text_justify != text_justify::T::none => {
+                InlineFlow::justify_inline_fragments(fragments, line, slack_inline_size)
+            }
+            text_align::T::left | text_align::T::justify => {}
+            text_align::T::center => {
+                inline_start_position_for_fragment = inline_start_position_for_fragment +
+                    slack_inline_size.scale_by(0.5)
+            }
+            text_align::T::right => {
+                inline_start_position_for_fragment = inline_start_position_for_fragment +
+                    slack_inline_size
+            }
+        }
 
         for fragment_index in range(line.range.begin(), line.range.end()) {
             let fragment = fragments.get_mut(fragment_index.to_uint());
@@ -889,6 +920,75 @@ impl InlineFlow {
         }
     }
 
+    /// Justifies the given set of inline fragments, distributing the `slack_inline_size` among all
+    /// of them according to the value of `text-justify`.
+    fn justify_inline_fragments(fragments: &mut InlineFragments,
+                                line: &Line,
+                                slack_inline_size: Au) {
+        // Fast path.
+        if slack_inline_size == Au(0) {
+            return
+        }
+
+        // First, calculate the number of expansion opportunities (spaces, normally).
+        let mut expansion_opportunities = 0i32;
+        for fragment_index in line.range.each_index() {
+            let fragment = fragments.get(fragment_index.to_uint());
+            let scanned_text_fragment_info =
+                if let SpecificFragmentInfo::ScannedText(ref info) = fragment.specific {
+                    info
+                } else {
+                    continue
+                };
+            for slice in scanned_text_fragment_info.run.character_slices_in_range(
+                    &scanned_text_fragment_info.range) {
+                expansion_opportunities += slice.glyphs.space_count_in_range(&slice.range) as i32
+            }
+        }
+
+        // Then distribute all the space across the expansion opportunities.
+        let space_per_expansion_opportunity = slack_inline_size.to_subpx() /
+            (expansion_opportunities as f64);
+        for fragment_index in line.range.each_index() {
+            let fragment = fragments.get_mut(fragment_index.to_uint());
+            let mut scanned_text_fragment_info =
+                if let SpecificFragmentInfo::ScannedText(ref mut info) = fragment.specific {
+                    info
+                } else {
+                    continue
+                };
+            let fragment_range = scanned_text_fragment_info.range;
+
+            // FIXME(pcwalton): This is an awful lot of uniqueness making. I don't see any easy way
+            // to get rid of it without regressing the performance of the non-justified case,
+            // though.
+            let run = scanned_text_fragment_info.run.make_unique();
+            {
+                let glyph_runs = run.glyphs.make_unique();
+                for mut glyph_run in glyph_runs.iter_mut() {
+                    let mut range = glyph_run.range.intersect(&fragment_range);
+                    if range.is_empty() {
+                        continue
+                    }
+                    range.shift_by(-glyph_run.range.begin());
+
+                    let glyph_store = glyph_run.glyph_store.make_unique();
+                    glyph_store.distribute_extra_space_in_range(&range,
+                                                                space_per_expansion_opportunity);
+                }
+            }
+
+            // Recompute the fragment's border box size.
+            let new_inline_size = run.advance_for_range(&fragment_range);
+            let new_size = LogicalSize::new(fragment.style.writing_mode,
+                                            new_inline_size,
+                                            fragment.border_box.size.block);
+            fragment.border_box = LogicalRect::from_point_size(fragment.style.writing_mode,
+                                                               fragment.border_box.start,
+                                                               new_size);
+        }
+    }
+
     /// Sets final fragment positions in the block direction for one line. Assumes that the
     /// fragment positions were initially set to the distance from the baseline first.
     fn set_block_fragment_positions(fragments: &mut InlineFragments,
@@ -1083,12 +1183,16 @@ impl Flow for InlineFlow {
 
         // Now, go through each line and lay out the fragments inside.
         let mut line_distance_from_flow_block_start = Au(0);
-        for line in self.lines.iter_mut() {
-            // Lay out fragments in the inline direction.
+        let line_count = self.lines.len();
+        for line_index in range(0, line_count) {
+            let line = &mut self.lines[line_index];
+
+            // Lay out fragments in the inline direction, and justify them if necessary.
             InlineFlow::set_inline_fragment_positions(&mut self.fragments,
                                                       line,
                                                       self.base.flags.text_align(),
-                                                      indentation);
+                                                      indentation,
+                                                      line_index + 1 == line_count);
 
             // Set the block-start position of the current line.
             // `line_height_offset` is updated at the end of the previous loop.