auto merge of #2584 : pcwalton/servo/binary-search, r=SimonSapin

in a text run.

This makes painting of text display items faster and matches what Gecko
does.

r? @SimonSapin

3 files changed, 101 insertions, 42 deletions

diff --git a/src/components/gfx/text/glyph.rs b/src/components/gfx/text/glyph.rs
index 2597b65cd1a..f0ea18059da 100644
--- a/src/components/gfx/text/glyph.rs
+++ b/src/components/gfx/text/glyph.rs
@@ -270,7 +270,7 @@ impl DetailedGlyph {
     }
 }
 
-#[deriving(Eq, Clone)]
+#[deriving(Eq, Clone, TotalEq, TotalOrd)]
 struct DetailedGlyphRecord {
     // source string offset/GlyphEntry offset in the TextRun
     entry_offset: CharIndex,
diff --git a/src/components/gfx/text/text_run.rs b/src/components/gfx/text/text_run.rs
index dab3ee3748e..3575686079e 100644
--- a/src/components/gfx/text/text_run.rs
+++ b/src/components/gfx/text/text_run.rs
@@ -5,12 +5,13 @@
 use font::{Font, FontDescriptor, RunMetrics, FontStyle, FontMetrics};
 use servo_util::geometry::Au;
 use servo_util::range::Range;
+use servo_util::vec::{Comparator, FullBinarySearchMethods};
 use std::slice::Items;
 use style::computed_values::text_decoration;
 use sync::Arc;
 use text::glyph::{CharIndex, GlyphStore};
 
-/// A text run.
+/// A single "paragraph" of text in one font size and style.
 #[deriving(Clone)]
 pub struct TextRun {
     pub text: Arc<String>,
@@ -18,37 +19,56 @@ pub struct TextRun {
     pub font_metrics: FontMetrics,
     pub font_style: FontStyle,
     pub decoration: text_decoration::T,
-    // An Arc pointing to a Vec of Arcs?! Wat.
-    pub glyphs: Arc<Vec<Arc<GlyphStore>>>,
+    /// The glyph runs that make up this text run.
+    pub glyphs: Arc<Vec<GlyphRun>>,
+}
+
+/// A single series of glyphs within a text run.
+#[deriving(Clone)]
+pub struct GlyphRun {
+    /// The glyphs.
+    glyph_store: Arc<GlyphStore>,
+    /// The range of characters in the containing run.
+    range: Range<CharIndex>,
 }
 
 pub struct SliceIterator<'a> {
-    glyph_iter: Items<'a, Arc<GlyphStore>>,
+    glyph_iter: Items<'a, GlyphRun>,
     range:      Range<CharIndex>,
-    offset:     CharIndex,
+}
+
+struct CharIndexComparator;
+
+impl Comparator<CharIndex,GlyphRun> for CharIndexComparator {
+    fn compare(&self, key: &CharIndex, value: &GlyphRun) -> Ordering {
+        if *key < value.range.begin() {
+            Less
+        } else if *key >= value.range.end() {
+            Greater
+        } else {
+            Equal
+        }
+    }
 }
 
 impl<'a> Iterator<(&'a GlyphStore, CharIndex, Range<CharIndex>)> for SliceIterator<'a> {
     // inline(always) due to the inefficient rt failures messing up inline heuristics, I think.
     #[inline(always)]
     fn next(&mut self) -> Option<(&'a GlyphStore, CharIndex, Range<CharIndex>)> {
-        loop {
-            let slice_glyphs = self.glyph_iter.next();
-            if slice_glyphs.is_none() {
-                return None;
-            }
-            let slice_glyphs = slice_glyphs.unwrap();
-
-            let slice_range = Range::new(self.offset, slice_glyphs.char_len());
-            let mut char_range = self.range.intersect(&slice_range);
-            char_range.shift_by(-self.offset);
+        let slice_glyphs = self.glyph_iter.next();
+        if slice_glyphs.is_none() {
+            return None;
+        }
+        let slice_glyphs = slice_glyphs.unwrap();
 
-            let old_offset = self.offset;
-            self.offset = self.offset + slice_glyphs.char_len();
-            if !char_range.is_empty() {
-                return Some((&**slice_glyphs, old_offset, char_range))
-            }
+        let mut char_range = self.range.intersect(&slice_glyphs.range);
+        let slice_range_begin = slice_glyphs.range.begin();
+        char_range.shift_by(-slice_range_begin);
+        if !char_range.is_empty() {
+            return Some((&*slice_glyphs.glyph_store, slice_range_begin, char_range))
         }
+
+        return None;
     }
 }
 
@@ -111,13 +131,13 @@ impl<'a> TextRun {
         return run;
     }
 
-    pub fn break_and_shape(font: &mut Font, text: &str) -> Vec<Arc<GlyphStore>> {
+    pub fn break_and_shape(font: &mut Font, text: &str) -> Vec<GlyphRun> {
         // TODO(Issue #230): do a better job. See Gecko's LineBreaker.
 
         let mut glyphs = vec!();
-        let mut byte_i = 0u;
+        let (mut byte_i, mut char_i) = (0u, CharIndex(0));
         let mut cur_slice_is_whitespace = false;
-        let mut byte_last_boundary = 0;
+        let (mut byte_last_boundary, mut char_last_boundary) = (0, CharIndex(0));
         while byte_i < text.len() {
             let range = text.char_range_at(byte_i);
             let ch = range.ch;
@@ -148,11 +168,16 @@ impl<'a> TextRun {
                 let slice = text.slice(byte_last_boundary, byte_i).to_string();
                 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));
+                glyphs.push(GlyphRun {
+                    glyph_store: font.shape_text(slice, !cur_slice_is_whitespace),
+                    range: Range::new(char_last_boundary, char_i - char_last_boundary),
+                });
                 byte_last_boundary = byte_i;
+                char_last_boundary = char_i;
             }
 
             byte_i = next;
+            char_i = char_i + CharIndex(1);
         }
 
         // Create a glyph store for the final slice if it's nonempty.
@@ -160,19 +185,23 @@ impl<'a> TextRun {
             let slice = text.slice_from(byte_last_boundary).to_string();
             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.push(GlyphRun {
+                glyph_store: font.shape_text(slice, cur_slice_is_whitespace),
+                range: Range::new(char_last_boundary, char_i - char_last_boundary),
+            });
         }
 
         glyphs
     }
 
     pub fn char_len(&self) -> CharIndex {
-        self.glyphs.iter().fold(CharIndex(0), |len, slice_glyphs| {
-            len + slice_glyphs.char_len()
-        })
+        match self.glyphs.last() {
+            None => CharIndex(0),
+            Some(ref glyph_run) => glyph_run.range.end(),
+        }
     }
 
-    pub fn glyphs(&'a self) -> &'a Vec<Arc<GlyphStore>> {
+    pub fn glyphs(&'a self) -> &'a Vec<GlyphRun> {
         &*self.glyphs
     }
 
@@ -222,11 +251,19 @@ impl<'a> TextRun {
         max_piece_width
     }
 
+    /// Returns the index of the first glyph run containing the given character index.
+    fn index_of_first_glyph_run_containing(&self, index: CharIndex) -> Option<uint> {
+        self.glyphs.as_slice().binary_search_index_by(&index, CharIndexComparator)
+    }
+
     pub fn iter_slices_for_range(&'a self, range: &Range<CharIndex>) -> SliceIterator<'a> {
+        let index = match self.index_of_first_glyph_run_containing(range.begin()) {
+            None => self.glyphs.len(),
+            Some(index) => index,
+        };
         SliceIterator {
-            glyph_iter: self.glyphs.iter(),
+            glyph_iter: self.glyphs.slice_from(index).iter(),
             range:      *range,
-            offset:     CharIndex(0),
         }
     }
 
diff --git a/src/components/util/vec.rs b/src/components/util/vec.rs
index 226c345aafd..f5c01786d9a 100644
--- a/src/components/util/vec.rs
+++ b/src/components/util/vec.rs
@@ -4,17 +4,33 @@
 
 use std::cmp::{Ord, Eq};
 
-pub trait BinarySearchMethods<'a, T: Ord + Eq> {
+/// FIXME(pcwalton): Workaround for lack of unboxed closures. This is called in
+/// performance-critical code, so a closure is insufficient.
+pub trait Comparator<K,T> {
+    fn compare(&self, key: &K, value: &T) -> Ordering;
+}
+
+pub trait BinarySearchMethods<'a, T: TotalOrd + Ord + Eq> {
     fn binary_search(&self, key: &T) -> Option<&'a T>;
     fn binary_search_index(&self, key: &T) -> Option<uint>;
 }
 
-impl<'a, T: Ord + Eq> BinarySearchMethods<'a, T> for &'a [T] {
+pub trait FullBinarySearchMethods<T> {
+    fn binary_search_index_by<K,C:Comparator<K,T>>(&self, key: &K, cmp: C) -> Option<uint>;
+}
+
+impl<'a, T: TotalOrd + Ord + Eq> BinarySearchMethods<'a, T> for &'a [T] {
     fn binary_search(&self, key: &T) -> Option<&'a T> {
         self.binary_search_index(key).map(|i| &self[i])
     }
 
     fn binary_search_index(&self, key: &T) -> Option<uint> {
+        self.binary_search_index_by(key, DefaultComparator)
+    }
+}
+
+impl<'a, T> FullBinarySearchMethods<T> for &'a [T] {
+    fn binary_search_index_by<K,C:Comparator<K,T>>(&self, key: &K, cmp: C) -> Option<uint> {
         if self.len() == 0 {
             return None;
         }
@@ -27,20 +43,26 @@ impl<'a, T: Ord + Eq> BinarySearchMethods<'a, T> for &'a [T] {
             let mid = ((low as uint) + (high as uint)) >> 1;
             let midv = &self[mid];
 
-            if midv < key {
-                low = (mid as int) + 1;
-            } else if midv > key {
-                high = (mid as int) - 1;
-            } else {
-                return Some(mid);
+            match cmp.compare(key, midv) {
+                Greater => low = (mid as int) + 1,
+                Less => high = (mid as int) - 1,
+                Equal => return Some(mid),
             }
         }
         return None;
     }
 }
 
+struct DefaultComparator;
+
+impl<T:Eq + Ord + TotalOrd> Comparator<T,T> for DefaultComparator {
+    fn compare(&self, key: &T, value: &T) -> Ordering {
+        (*key).cmp(value)
+    }
+}
+
 #[cfg(test)]
-fn test_find_all_elems<T: Eq + Ord>(arr: &[T]) {
+fn test_find_all_elems<T: Eq + Ord + TotalEq + TotalOrd>(arr: &[T]) {
     let mut i = 0;
     while i < arr.len() {
         assert!(test_match(&arr[i], arr.binary_search(&arr[i])));
@@ -49,7 +71,7 @@ fn test_find_all_elems<T: Eq + Ord>(arr: &[T]) {
 }
 
 #[cfg(test)]
-fn test_miss_all_elems<T: Eq + Ord>(arr: &[T], misses: &[T]) {
+fn test_miss_all_elems<T: Eq + Ord + TotalEq + TotalOrd>(arr: &[T], misses: &[T]) {
     let mut i = 0;
     while i < misses.len() {
         let res = arr.binary_search(&misses[i]);