auto merge of #548 : sfowler/servo/glyph-store-cache, r=pcwalton

This PR makes text runs store the results of shaping as a vector of ARC<GlyphStore>; each element of the vector holds the shaped glyphs for a nonbreakable unit of text (basically a word). This change allows us to cache the shaped glyphs for the words, an approach that Gecko (and probably WebKit) uses. We get pretty good cache hit ratios even on the first run of layout for a page (I saw 62% on Wikipedia's main page today), although a lot of that is due to whitespace. This really comes into its own on subsequent layout runs, though, which are completely cached in the typical case.

8 files changed, 290 insertions, 176 deletions

diff --git a/src/components/gfx/font.rs b/src/components/gfx/font.rs
index ae0d2e4acc0..8e31f138c1e 100644
--- a/src/components/gfx/font.rs
+++ b/src/components/gfx/font.rs
@@ -14,15 +14,19 @@ use std::result;
 use std::ptr;
 use std::str;
 use std::vec;
+use servo_util::cache::{Cache, HashCache};
 use text::glyph::{GlyphStore, GlyphIndex};
 use text::shaping::ShaperMethods;
 use text::{Shaper, TextRun};
+use extra::arc::ARC;
 
 use azure::{AzFloat, AzScaledFontRef};
 use azure::scaled_font::ScaledFont;
 use azure::azure_hl::{BackendType, ColorPattern};
 use geom::{Point2D, Rect, Size2D};
 
+use servo_util::time;
+use servo_util::time::profile;
 use servo_util::time::ProfilerChan;
 
 // FontHandle encapsulates access to the platform's font API,
@@ -86,7 +90,7 @@ pub struct FontMetrics {
 }
 
 // TODO(Issue #200): use enum from CSS bindings for 'font-weight'
-#[deriving(Eq)]
+#[deriving(Clone, Eq)]
 pub enum CSSFontWeight {
     FontWeight100,
     FontWeight200,
@@ -114,7 +118,7 @@ impl CSSFontWeight {
 // the instance's properties.
 //
 // For now, the cases are differentiated with a typedef
-#[deriving(Eq)]
+#[deriving(Clone, Eq)]
 pub struct FontStyle {
     pt_size: float,
     weight: CSSFontWeight,
@@ -139,7 +143,7 @@ struct ResolvedFont {
 // It's used to swizzle/unswizzle gfx::Font instances when
 // communicating across tasks, such as the display list between layout
 // and render tasks.
-#[deriving(Eq)]
+#[deriving(Clone, Eq)]
 pub struct FontDescriptor {
     style: UsedFontStyle,
     selector: FontSelector,
@@ -155,7 +159,7 @@ impl FontDescriptor {
 }
 
 // A FontSelector is a platform-specific strategy for serializing face names.
-#[deriving(Eq)]
+#[deriving(Clone, Eq)]
 pub enum FontSelector {
     SelectorPlatformIdentifier(~str),
 }
@@ -206,6 +210,24 @@ pub struct RunMetrics {
     bounding_box: Rect<Au>
 }
 
+impl RunMetrics {
+    pub fn new(advance: Au, ascent: Au, descent: Au) -> RunMetrics {
+        let bounds = Rect(Point2D(Au(0), -ascent),
+                          Size2D(advance, ascent + descent));
+
+        // TODO(Issue #125): support loose and tight bounding boxes; using the
+        // ascent+descent and advance is sometimes too generous and
+        // looking at actual glyph extents can yield a tighter box.
+
+        RunMetrics { 
+            advance_width: advance,
+            bounding_box: bounds,
+            ascent: ascent,
+            descent: descent,
+        }
+    }
+}
+
 /**
 A font instance. Layout can use this to calculate glyph metrics
 and the renderer can use it to render text.
@@ -218,6 +240,7 @@ pub struct Font {
     metrics: FontMetrics,
     backend: BackendType,
     profiler_chan: ProfilerChan,
+    shape_cache: HashCache<~str, ARC<GlyphStore>>,
 }
 
 impl Font {
@@ -245,6 +268,7 @@ impl Font {
             metrics: metrics,
             backend: backend,
             profiler_chan: profiler_chan,
+            shape_cache: HashCache::new(),
         });
     }
 
@@ -261,6 +285,7 @@ impl Font {
             metrics: metrics,
             backend: backend,
             profiler_chan: profiler_chan,
+            shape_cache: HashCache::new(),
         }
     }
 
@@ -366,20 +391,22 @@ impl Font {
         let mut azglyphs = ~[];
         vec::reserve(&mut azglyphs, range.length());
 
-        for run.glyphs.iter_glyphs_for_char_range(range) |_i, glyph| {
-            let glyph_advance = glyph.advance_();
-            let glyph_offset = glyph.offset().get_or_default(Au::zero_point());
-
-            let azglyph = struct__AzGlyph {
-                mIndex: glyph.index() as uint32_t,
-                mPosition: struct__AzPoint {
-                    x: (origin.x + glyph_offset.x).to_px() as AzFloat,
-                    y: (origin.y + glyph_offset.y).to_px() as AzFloat
-                }
+        for run.iter_slices_for_range(range) |glyphs, _offset, slice_range| {
+            for glyphs.iter_glyphs_for_char_range(slice_range) |_i, glyph| {
+                let glyph_advance = glyph.advance_();
+                let glyph_offset = glyph.offset().get_or_default(Au::zero_point());
+
+                let azglyph = struct__AzGlyph {
+                    mIndex: glyph.index() as uint32_t,
+                    mPosition: struct__AzPoint {
+                        x: (origin.x + glyph_offset.x).to_px() as AzFloat,
+                        y: (origin.y + glyph_offset.y).to_px() as AzFloat
+                    }
+                };
+                origin = Point2D(origin.x + glyph_advance, origin.y);
+                azglyphs.push(azglyph)
             };
-            origin = Point2D(origin.x + glyph_advance, origin.y);
-            azglyphs.push(azglyph)
-        };
+        }
 
         let azglyph_buf_len = azglyphs.len();
         if azglyph_buf_len == 0 { return; } // Otherwise the Quartz backend will assert.
@@ -404,29 +431,34 @@ impl Font {
         // TODO(Issue #199): alter advance direction for RTL
         // TODO(Issue #98): using inter-char and inter-word spacing settings  when measuring text
         let mut advance = Au(0);
-        for run.glyphs.iter_glyphs_for_char_range(range) |_i, glyph| {
-            advance += glyph.advance_();
+        for run.iter_slices_for_range(range) |glyphs, _offset, slice_range| {
+            for glyphs.iter_glyphs_for_char_range(slice_range) |_i, glyph| {
+                advance += glyph.advance_();
+            }
         }
-        let bounds = Rect(Point2D(Au(0), -self.metrics.ascent),
-                          Size2D(advance, self.metrics.ascent + self.metrics.descent));
-
-        // TODO(Issue #125): support loose and tight bounding boxes; using the
-        // ascent+descent and advance is sometimes too generous and
-        // looking at actual glyph extents can yield a tighter box.
+        RunMetrics::new(advance, self.metrics.ascent, self.metrics.descent)
+    }
 
-        RunMetrics { 
-            advance_width: advance,
-            bounding_box: bounds,
-            ascent: self.metrics.ascent,
-            descent: self.metrics.descent,
+    pub fn measure_text_for_slice(&self,
+                                  glyphs: &GlyphStore,
+                                  slice_range: &Range)
+                                  -> RunMetrics {
+        let mut advance = Au(0);
+        for glyphs.iter_glyphs_for_char_range(slice_range) |_i, glyph| {
+            advance += glyph.advance_();
         }
+        RunMetrics::new(advance, self.metrics.ascent, self.metrics.descent)
     }
 
-    pub fn shape_text(@mut self, text: &str, store: &mut GlyphStore) {
-        // TODO(Issue #229): use a more efficient strategy for repetitive shaping.
-        // For example, Gecko uses a per-"word" hashtable of shaper results.
-        let shaper = self.get_shaper();
-        shaper.shape_text(text, store);
+    pub fn shape_text(@mut self, text: ~str, is_whitespace: bool) -> ARC<GlyphStore> {
+        do profile(time::LayoutShapingCategory, self.profiler_chan.clone()) {
+            let shaper = self.get_shaper();
+            do self.shape_cache.find_or_create(&text) |txt| {
+                let mut glyphs = GlyphStore::new(text.char_len(), is_whitespace);
+                shaper.shape_text(*txt, &mut glyphs);
+                ARC(glyphs)
+            }
+        }
     }
 
     pub fn get_descriptor(&self) -> FontDescriptor {
diff --git a/src/components/gfx/font_context.rs b/src/components/gfx/font_context.rs
index d4479a8e310..1eff76495cd 100644
--- a/src/components/gfx/font_context.rs
+++ b/src/components/gfx/font_context.rs
@@ -6,8 +6,7 @@ use font::{Font, FontDescriptor, FontGroup, FontHandleMethods, FontStyle,
            SelectorPlatformIdentifier};
 use font::{SpecifiedFontStyle, UsedFontStyle};
 use font_list::FontList;
-use servo_util::cache::Cache;
-use servo_util::cache::LRUCache;
+use servo_util::cache::{Cache, LRUCache};
 use servo_util::time::ProfilerChan;
 
 use platform::font::FontHandle;
@@ -15,7 +14,6 @@ use platform::font_context::FontContextHandle;
 
 use azure::azure_hl::BackendType;
 use std::hashmap::HashMap;
-use std::str;
 use std::result;
 
 // TODO(Rust #3934): creating lots of new dummy styles is a workaround
@@ -90,7 +88,7 @@ impl<'self> FontContext {
             None => {
                 debug!("font group cache miss");
                 let fg = self.create_font_group(style);
-                self.group_cache.insert(style, fg);
+                self.group_cache.insert(style.clone(), fg);
                 fg
             }
         }
@@ -107,7 +105,7 @@ impl<'self> FontContext {
                 let result = self.create_font_instance(desc);
                 match result {
                     Ok(font) => {
-                        self.instance_cache.insert(desc, font);
+                        self.instance_cache.insert(desc.clone(), font);
                     }, _ => {}
                 };
                 result
diff --git a/src/components/gfx/text/glyph.rs b/src/components/gfx/text/glyph.rs
index 7789b4174e7..a873b3b841a 100644
--- a/src/components/gfx/text/glyph.rs
+++ b/src/components/gfx/text/glyph.rs
@@ -507,20 +507,30 @@ impl<'self> GlyphInfo<'self> {
 pub struct GlyphStore {
     entry_buffer: ~[GlyphEntry],
     detail_store: DetailedGlyphStore,
+    is_whitespace: bool,
 }
 
 impl<'self> GlyphStore {
     // Initializes the glyph store, but doesn't actually shape anything.
     // Use the set_glyph, set_glyphs() methods to store glyph data.
-    pub fn new(length: uint) -> GlyphStore {
+    pub fn new(length: uint, is_whitespace: bool) -> GlyphStore {
         assert!(length > 0);
 
         GlyphStore {
             entry_buffer: vec::from_elem(length, GlyphEntry::initial()),
             detail_store: DetailedGlyphStore::new(),
+            is_whitespace: is_whitespace,
         }
     }
 
+    pub fn char_len(&self) -> uint {
+        self.entry_buffer.len()
+    }
+
+    pub fn is_whitespace(&self) -> bool {
+        self.is_whitespace
+    }
+
     pub fn finalize_changes(&mut self) {
         self.detail_store.ensure_sorted();
     }
diff --git a/src/components/gfx/text/text_run.rs b/src/components/gfx/text/text_run.rs
index 50f5c6561b6..cfcbab54680 100644
--- a/src/components/gfx/text/text_run.rs
+++ b/src/components/gfx/text/text_run.rs
@@ -4,18 +4,17 @@
 
 use font_context::FontContext;
 use geometry::Au;
-use text::glyph::{BreakTypeNormal, GlyphStore};
+use text::glyph::GlyphStore;
 use font::{Font, FontDescriptor, RunMetrics};
-use servo_util::time;
-use servo_util::time::profile;
 use servo_util::range::Range;
+use extra::arc::ARC;
 
 /// A text run.
 pub struct TextRun {
     text: ~str,
     font: @mut Font,
     underline: bool,
-    glyphs: GlyphStore,
+    glyphs: ~[ARC<GlyphStore>],
 }
 
 /// This is a hack until TextRuns are normally sendable, or we instead use ARC<TextRun> everywhere.
@@ -23,7 +22,7 @@ pub struct SendableTextRun {
     text: ~str,
     font: FontDescriptor,
     underline: bool,
-    priv glyphs: GlyphStore,
+    priv glyphs: ~[ARC<GlyphStore>],
 }
 
 impl SendableTextRun {
@@ -37,24 +36,20 @@ impl SendableTextRun {
             text: copy self.text,
             font: font,
             underline: self.underline,
-            glyphs: copy self.glyphs
+            glyphs: self.glyphs.clone(),
         }
     }
 }
 
 impl<'self> TextRun {
     pub fn new(font: @mut Font, text: ~str, underline: bool) -> TextRun {
-        let mut glyph_store = GlyphStore::new(text.char_len());
-        TextRun::compute_potential_breaks(text, &mut glyph_store);
-        do profile(time::LayoutShapingCategory, font.profiler_chan.clone()) {
-            font.shape_text(text, &mut glyph_store);
-        }
+        let glyphs = TextRun::break_and_shape(font, text);
 
         let run = TextRun {
             text: text,
             font: font,
             underline: underline,
-            glyphs: glyph_store,
+            glyphs: glyphs,
         };
         return run;
     }
@@ -63,46 +58,59 @@ impl<'self> TextRun {
         self.font.teardown();
     }
 
-    pub fn compute_potential_breaks(text: &str, glyphs: &mut GlyphStore) {
+    pub fn break_and_shape(font: @mut Font, text: &str) -> ~[ARC<GlyphStore>] {
         // TODO(Issue #230): do a better job. See Gecko's LineBreaker.
 
+        let mut glyphs = ~[];
         let mut byte_i = 0u;
-        let mut char_j = 0u;
-        let mut prev_is_whitespace = false;
+        let mut cur_slice_is_whitespace = false;
+        let mut byte_last_boundary = 0;
         while byte_i < text.len() {
             let range = text.char_range_at(byte_i);
             let ch = range.ch;
             let next = range.next;
-            // set char properties.
-            match ch {
-                ' '  => { glyphs.set_char_is_space(char_j); },
-                '\t' => { glyphs.set_char_is_tab(char_j); },
-                '\n' => { glyphs.set_char_is_newline(char_j); },
-                _ => {}
-            }
 
-            // set line break opportunities at whitespace/non-whitespace boundaries.
-            if prev_is_whitespace {
+            // Slices alternate between whitespace and non-whitespace,
+            // representing line break opportunities.
+            let can_break_before = if cur_slice_is_whitespace {
                 match ch {
-                    ' ' | '\t' | '\n' => {},
+                    ' ' | '\t' | '\n' => false,
                     _ => {
-                        glyphs.set_can_break_before(char_j, BreakTypeNormal);
-                        prev_is_whitespace = false;
+                        cur_slice_is_whitespace = false;
+                        true
                     }
                 }
             } else {
                 match ch {
                     ' ' | '\t' | '\n' => {
-                        glyphs.set_can_break_before(char_j, BreakTypeNormal);
-                        prev_is_whitespace = true;
+                        cur_slice_is_whitespace = true;
+                        true
                     },
-                    _ => { }
+                    _ => false
                 }
+            };
+
+            // Create a glyph store for this slice if it's nonempty.
+            if can_break_before && byte_i > byte_last_boundary {
+                let slice = text.slice(byte_last_boundary, byte_i).to_owned();
+                debug!("creating glyph store for slice %? (ws? %?), %? - %? in run %?",
+                        slice, !cur_slice_is_whitespace, byte_last_boundary, byte_i, text);
+                glyphs.push(font.shape_text(slice, !cur_slice_is_whitespace));
+                byte_last_boundary = byte_i;
             }
 
             byte_i = next;
-            char_j += 1;
         }
+
+        // Create a glyph store for the final slice if it's nonempty.
+        if byte_i > byte_last_boundary {
+            let slice = text.slice(byte_last_boundary, text.len()).to_owned();
+            debug!("creating glyph store for final slice %? (ws? %?), %? - %? in run %?",
+                slice, cur_slice_is_whitespace, byte_last_boundary, text.len(), text);
+            glyphs.push(font.shape_text(slice, cur_slice_is_whitespace));
+        }
+
+        glyphs
     }
 
     pub fn serialize(&self) -> SendableTextRun {
@@ -110,50 +118,80 @@ impl<'self> TextRun {
             text: copy self.text,
             font: self.font.get_descriptor(),
             underline: self.underline,
-            glyphs: copy self.glyphs,
+            glyphs: self.glyphs.clone(),
+        }
+    }
+
+    pub fn char_len(&self) -> uint {
+        do self.glyphs.foldl(0u) |len, slice_glyphs| {
+            len + slice_glyphs.get().char_len()
         }
     }
 
-    pub fn char_len(&self) -> uint { self.glyphs.entry_buffer.len() }
-    pub fn glyphs(&'self self) -> &'self GlyphStore { &self.glyphs }
+    pub fn glyphs(&'self self) -> &'self ~[ARC<GlyphStore>] { &self.glyphs }
 
     pub fn range_is_trimmable_whitespace(&self, range: &Range) -> bool {
-        for range.eachi |i| {
-            if  !self.glyphs.char_is_space(i) &&
-                !self.glyphs.char_is_tab(i)   &&
-                !self.glyphs.char_is_newline(i) { return false; }
+        for self.iter_slices_for_range(range) |slice_glyphs, _, _| {
+            if !slice_glyphs.is_whitespace() { return false; }
         }
-        return true;
+        true
     }
 
     pub fn metrics_for_range(&self, range: &Range) -> RunMetrics {
         self.font.measure_text(self, range)
     }
 
+    pub fn metrics_for_slice(&self, glyphs: &GlyphStore, slice_range: &Range) -> RunMetrics {
+        self.font.measure_text_for_slice(glyphs, slice_range)
+    }
+
     pub fn min_width_for_range(&self, range: &Range) -> Au {
         let mut max_piece_width = Au(0);
         debug!("iterating outer range %?", range);
-        for self.iter_indivisible_pieces_for_range(range) |piece_range| {
-            debug!("iterated on %?", piece_range);
-            let metrics = self.font.measure_text(self, piece_range);
+        for self.iter_slices_for_range(range) |glyphs, offset, slice_range| {
+            debug!("iterated on %?[%?]", offset, slice_range);
+            let metrics = self.font.measure_text_for_slice(glyphs, slice_range);
             max_piece_width = Au::max(max_piece_width, metrics.advance_width);
         }
-        return max_piece_width;
+        max_piece_width
+    }
+
+    pub fn iter_slices_for_range(&self,
+                                 range: &Range,
+                                 f: &fn(&GlyphStore, uint, &Range) -> bool)
+                                 -> bool {
+        let mut offset = 0;
+        for self.glyphs.each |slice_glyphs| {
+            // Determine the range of this slice that we need.
+            let slice_range = Range::new(offset, slice_glyphs.get().char_len());
+            let mut char_range = range.intersect(&slice_range);
+            char_range.shift_by(-(offset.to_int()));
+
+            let unwrapped_glyphs = slice_glyphs.get();
+            if !char_range.is_empty() {
+                if !f(unwrapped_glyphs, offset, &char_range) { break }
+            }
+            offset += unwrapped_glyphs.char_len();
+        }
+        true
     }
 
     pub fn iter_natural_lines_for_range(&self, range: &Range, f: &fn(&Range) -> bool) -> bool {
         let mut clump = Range::new(range.begin(), 0);
         let mut in_clump = false;
 
-        // clump non-linebreaks of nonzero length
-        for range.eachi |i| {
-            match (self.glyphs.char_is_newline(i), in_clump) {
-                (false, true)  => { clump.extend_by(1); }
-                (false, false) => { in_clump = true; clump.reset(i, 1); }
-                (true, false) => { /* chomp whitespace */ }
-                (true, true)  => {
+        for self.iter_slices_for_range(range) |glyphs, offset, slice_range| {
+            match (glyphs.is_whitespace(), in_clump) {
+                (false, true)  => { clump.extend_by(slice_range.length().to_int()); }
+                (false, false) => {
+                    in_clump = true;
+                    clump = *slice_range;
+                    clump.shift_by(offset.to_int());
+                }
+                (true, false)  => { /* chomp whitespace */ }
+                (true, true)   => {
                     in_clump = false;
-                    // don't include the linebreak character itself in the clump.
+                    // The final whitespace clump is not included.
                     if !f(&clump) { break }
                 }
             }
@@ -167,28 +205,4 @@ impl<'self> TextRun {
 
         true
     }
-
-    pub fn iter_indivisible_pieces_for_range(&self, range: &Range, f: &fn(&Range) -> bool) -> bool {
-        let mut clump = Range::new(range.begin(), 0);
-
-        loop {
-            // extend clump to non-break-before characters.
-            while clump.end() < range.end() 
-                && self.glyphs.can_break_before(clump.end()) != BreakTypeNormal {
-
-                clump.extend_by(1);
-            }
-
-            // now clump.end() is break-before or range.end()
-            if !f(&clump) || clump.end() == range.end() {
-                break
-            }
-
-            // now clump includes one break-before character, or starts from range.end()
-            let end = clump.end(); // FIXME: borrow checker workaround
-            clump.reset(end, 1);
-        }
-
-        true
-    }
 }
diff --git a/src/components/main/layout/box.rs b/src/components/main/layout/box.rs
index fb32876f410..c101803397f 100644
--- a/src/components/main/layout/box.rs
+++ b/src/components/main/layout/box.rs
@@ -289,51 +289,52 @@ impl RenderBox {
                        text_box.range,
                        max_width);
 
-                for text_box.run.iter_indivisible_pieces_for_range(
-                        &text_box.range) |piece_range| {
-                    debug!("split_to_width: considering piece (range=%?, remain_width=%?)",
-                           piece_range,
+                for text_box.run.iter_slices_for_range(&text_box.range)
+                                                        |glyphs, offset, slice_range| {
+                    debug!("split_to_width: considering slice (offset=%?, range=%?, remain_width=%?)",
+                           offset,
+                           slice_range,
                            remaining_width);
 
-                    let metrics = text_box.run.metrics_for_range(piece_range);
+                    let metrics = text_box.run.metrics_for_slice(glyphs, slice_range);
                     let advance = metrics.advance_width;
                     let should_continue: bool;
 
                     if advance <= remaining_width {
                         should_continue = true;
 
-                        if starts_line &&
-                                pieces_processed_count == 0 &&
-                                text_box.run.range_is_trimmable_whitespace(piece_range) {
+                        if starts_line && pieces_processed_count == 0 && glyphs.is_whitespace() {
                             debug!("split_to_width: case=skipping leading trimmable whitespace");
-                            left_range.shift_by(piece_range.length() as int);
+                            left_range.shift_by(slice_range.length() as int);
                         } else {
                             debug!("split_to_width: case=enlarging span");
                             remaining_width -= advance;
-                            left_range.extend_by(piece_range.length() as int);
+                            left_range.extend_by(slice_range.length() as int);
                         }
                     } else {    // The advance is more than the remaining width.
                         should_continue = false;
+                        let slice_begin = offset + slice_range.begin();
+                        let slice_end = offset + slice_range.end();
 
-                        if text_box.run.range_is_trimmable_whitespace(piece_range) {
+                        if glyphs.is_whitespace() {
                             // If there are still things after the trimmable whitespace, create the
                             // right chunk.
-                            if piece_range.end() < text_box.range.end() {
+                            if slice_end < text_box.range.end() {
                                 debug!("split_to_width: case=skipping trimmable trailing \
                                         whitespace, then split remainder");
                                 let right_range_end =
-                                    text_box.range.end() - piece_range.end();
-                                right_range = Some(Range::new(piece_range.end(), right_range_end));
+                                    text_box.range.end() - slice_end;
+                                right_range = Some(Range::new(slice_end, right_range_end));
                             } else {
                                 debug!("split_to_width: case=skipping trimmable trailing \
                                         whitespace");
                             }
-                        } else if piece_range.begin() < text_box.range.end() {
+                        } else if slice_begin < text_box.range.end() {
                             // There are still some things left over at the end of the line. Create
                             // the right chunk.
                             let right_range_end =
-                                text_box.range.end() - piece_range.begin();
-                            right_range = Some(Range::new(piece_range.begin(), right_range_end));
+                                text_box.range.end() - slice_begin;
+                            right_range = Some(Range::new(slice_begin, right_range_end));
                             debug!("split_to_width: case=splitting remainder with right range=%?",
                                    right_range);
                         }
@@ -449,13 +450,8 @@ impl RenderBox {
                 let mut max_line_width = Au(0);
                 for text_box.run.iter_natural_lines_for_range(&text_box.range)
                         |line_range| {
-                    let mut line_width: Au = Au(0);
-                    for text_box.run.glyphs.iter_glyphs_for_char_range(line_range)
-                            |_, glyph| {
-                        line_width += glyph.advance_()
-                    }
-
-                    max_line_width = Au::max(max_line_width, line_width);
+                    let line_metrics = text_box.run.metrics_for_range(line_range);
+                    max_line_width = Au::max(max_line_width, line_metrics.advance_width);
                 }
 
                 max_line_width
@@ -857,10 +853,8 @@ impl RenderBox {
             GenericRenderBoxClass(*) => ~"GenericRenderBox",
             ImageRenderBoxClass(*) => ~"ImageRenderBox",
             TextRenderBoxClass(text_box) => {
-                fmt!("TextRenderBox(text=%s)",
-                     text_box.run.text.slice(
-                         text_box.range.begin(),
-                         text_box.range.begin() + text_box.range.length()))
+                fmt!("TextRenderBox(text=%s)", text_box.run.text.slice_chars(text_box.range.begin(),
+                                                                             text_box.range.end()))
             }
             UnscannedTextRenderBoxClass(text_box) => {
                 fmt!("UnscannedTextRenderBox(%s)", text_box.text)
@@ -870,5 +864,3 @@ impl RenderBox {
         fmt!("box b%?: %s", self.id(), representation)
     }
 }
-
-
diff --git a/src/components/main/layout/text.rs b/src/components/main/layout/text.rs
index e335fac37a5..b6b3e43eb99 100644
--- a/src/components/main/layout/text.rs
+++ b/src/components/main/layout/text.rs
@@ -21,15 +21,16 @@ use servo_util::range::Range;
 /// Creates a TextRenderBox from a range and a text run.
 pub fn adapt_textbox_with_range(mut base: RenderBoxBase, run: @TextRun, range: Range)
                                 -> TextRenderBox {
-    assert!(range.begin() < run.char_len());
-    assert!(range.end() <= run.char_len());
-    assert!(range.length() > 0);
-
-    debug!("Creating textbox with span: (strlen=%u, off=%u, len=%u) of textrun: %s",
+    debug!("Creating textbox with span: (strlen=%u, off=%u, len=%u) of textrun (%s) (len=%u)",
            run.char_len(),
            range.begin(),
            range.length(),
-           run.text);
+           run.text,
+           run.char_len());
+
+    assert!(range.begin() < run.char_len());
+    assert!(range.end() <= run.char_len());
+    assert!(range.length() > 0);
 
     let metrics = run.metrics_for_range(&range);
     base.position.size = metrics.bounding_box.size;
@@ -170,7 +171,7 @@ impl TextRunScanner {
                     let fontgroup = ctx.font_ctx.get_resolved_font_for_style(&font_style);
                     let run = @fontgroup.create_textrun(transformed_text, underline);
 
-                    debug!("TextRunScanner: pushing single text box in range: %?", self.clump);
+                    debug!("TextRunScanner: pushing single text box in range: %? (%?)", self.clump, text);
                     let new_box = do old_box.with_base |old_box_base| {
                         let range = Range::new(0, run.char_len());
                         @mut adapt_textbox_with_range(*old_box_base, run, range)
diff --git a/src/components/util/cache.rs b/src/components/util/cache.rs
index a03afdf961d..5e35a440088 100644
--- a/src/components/util/cache.rs
+++ b/src/components/util/cache.rs
@@ -2,8 +2,10 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
-pub trait Cache<K: Copy + Eq, V: Copy> {
-    fn insert(&mut self, key: &K, value: V);
+use std::hashmap::HashMap;
+
+pub trait Cache<K: Eq, V: Clone> {
+    fn insert(&mut self, key: K, value: V);
     fn find(&mut self, key: &K) -> Option<V>;
     fn find_or_create(&mut self, key: &K, blk: &fn(&K) -> V) -> V;
     fn evict_all(&mut self);
@@ -13,34 +15,35 @@ pub struct MonoCache<K, V> {
     entry: Option<(K,V)>,
 }
 
-impl<K: Copy + Eq, V: Copy> MonoCache<K,V> {
+impl<K: Clone + Eq, V: Clone> MonoCache<K,V> {
     pub fn new(_size: uint) -> MonoCache<K,V> {
         MonoCache { entry: None }
     }
 }
 
-impl<K: Copy + Eq, V: Copy> Cache<K,V> for MonoCache<K,V> {
-    fn insert(&mut self, key: &K, value: V) {
-        self.entry = Some((copy *key, value));
+impl<K: Clone + Eq, V: Clone> Cache<K,V> for MonoCache<K,V> {
+    fn insert(&mut self, key: K, value: V) {
+        self.entry = Some((key, value));
     }
 
     fn find(&mut self, key: &K) -> Option<V> {
         match self.entry {
             None => None,
-            Some((ref k, ref v)) => if *k == *key { Some(copy *v) } else { None }
+            Some((ref k, ref v)) => if *k == *key { Some(v.clone()) } else { None }
         }
     }
 
     fn find_or_create(&mut self, key: &K, blk: &fn(&K) -> V) -> V {
-        return match self.find(key) {
+        match self.entry {
             None => { 
                 let value = blk(key);
-                self.entry = Some((copy *key, copy value));
+                self.entry = Some((key.clone(), value.clone()));
                 value
             },
-            Some(v) => v
-        };
+            Some((ref _k, ref v)) => v.clone()
+        }
     }
+
     fn evict_all(&mut self) {
         self.entry = None;
     }
@@ -60,12 +63,60 @@ fn test_monocache() {
     assert!(cache.find(&1).is_none());
 }
 
+pub struct HashCache<K, V> {
+    entries: HashMap<K, V>,
+}
+
+impl<K: Clone + Eq + Hash, V: Clone> HashCache<K,V> {
+    pub fn new() -> HashCache<K, V> {
+        HashCache {
+          entries: HashMap::new(),
+        }
+    }
+}
+
+impl<K: Clone + Eq + Hash, V: Clone> Cache<K,V> for HashCache<K,V> {
+    fn insert(&mut self, key: K, value: V) {
+        self.entries.insert(key, value);
+    }
+
+    fn find(&mut self, key: &K) -> Option<V> {
+        match self.entries.find(key) {
+            Some(v) => Some(v.clone()),
+            None    => None,
+        }
+    }
+
+    fn find_or_create(&mut self, key: &K, blk: &fn(&K) -> V) -> V {
+        self.entries.find_or_insert_with(key.clone(), blk).clone()
+    }
+
+    fn evict_all(&mut self) {
+        self.entries.clear();
+    }
+}
+
+#[test]
+fn test_hashcache() {
+    let cache = HashCache::new();
+    let one = @"one";
+    let two = @"two";
+
+    cache.insert(&1, one);
+    assert!(cache.find(&1).is_some());
+    assert!(cache.find(&2).is_none());
+
+    cache.find_or_create(&2, |_v| { two });
+    assert!(cache.find(&1).is_some());
+    assert!(cache.find(&2).is_some());
+}
+
 pub struct LRUCache<K, V> {
     entries: ~[(K, V)],
     cache_size: uint,
 }
 
-impl<K: Copy + Eq, V: Copy> LRUCache<K,V> {
+impl<K: Clone + Eq, V: Clone> LRUCache<K,V> {
     pub fn new(size: uint) -> LRUCache<K, V> {
         LRUCache {
           entries: ~[],
@@ -74,21 +125,21 @@ impl<K: Copy + Eq, V: Copy> LRUCache<K,V> {
     }
 
     pub fn touch(&mut self, pos: uint) -> V {
-        let (key, val) = copy self.entries[pos];
-        if pos != self.cache_size {
-            self.entries.remove(pos);
-            self.entries.push((key, copy val));
+        let last_index = self.entries.len() - 1;
+        if pos != last_index {
+            let entry = self.entries.remove(pos);
+            self.entries.push(entry);
         }
-        val
+        self.entries[last_index].second_ref().clone()
     }
 }
 
-impl<K: Copy + Eq, V: Copy> Cache<K,V> for LRUCache<K,V> {
-    fn insert(&mut self, key: &K, val: V) {
+impl<K: Clone + Eq, V: Clone> Cache<K,V> for LRUCache<K,V> {
+    fn insert(&mut self, key: K, val: V) {
         if self.entries.len() == self.cache_size {
             self.entries.remove(0);
         }
-        self.entries.push((copy *key, val));
+        self.entries.push((key, val));
     }
 
     fn find(&mut self, key: &K) -> Option<V> {
@@ -102,9 +153,9 @@ impl<K: Copy + Eq, V: Copy> Cache<K,V> for LRUCache<K,V> {
         match self.entries.position(|&(k, _)| k == *key) {
             Some(pos) => self.touch(pos),
             None => {
-              let val = blk(key);
-              self.insert(key, copy val);
-              val
+                let val = blk(key);
+                self.insert(key.clone(), val.clone());
+                val
             }
         }
     }
diff --git a/src/components/util/range.rs b/src/components/util/range.rs
index 3b55c48f8d0..72719a97f8d 100644
--- a/src/components/util/range.rs
+++ b/src/components/util/range.rs
@@ -3,6 +3,7 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 use std::uint;
+use std::cmp::{max, min};
 
 enum RangeRelation {
     OverlapsBegin(/* overlap */ uint),
@@ -51,6 +52,10 @@ impl Range {
         self.begin() < s.len() && self.end() <= s.len() && self.length() <= s.len()
     }
 
+    pub fn is_empty(&self) -> bool {
+        self.len == 0
+    }
+
     pub fn shift_by(&mut self, i: int) { 
         self.off = ((self.off as int) + i) as uint;
     }
@@ -73,6 +78,17 @@ impl Range {
         self.len = len_i;
     }
 
+    pub fn intersect(&self, other: &Range) -> Range {
+        let begin = max(self.begin(), other.begin());
+        let end = min(self.end(), other.end());
+
+        if end < begin {
+            Range::empty()
+        } else {
+            Range::new(begin, end - begin)
+        }
+    }
+
     /// Computes the relationship between two ranges (`self` and `other`),
     /// from the point of view of `self`. So, 'EntirelyBefore' means
     /// that the `self` range is entirely before `other` range.