Introduce a dedicated data structure for text queries

Add an IndexableText structure for text queries.
Instead of linear search for a node this now uses a HashMap.
Remove the now irrelevant fields from TextDisplayItem.

6 files changed, 70 insertions, 49 deletions

diff --git a/components/gfx/display_list/mod.rs b/components/gfx/display_list/mod.rs
index a5d7118364e..23efeaf9445 100644
--- a/components/gfx/display_list/mod.rs
+++ b/components/gfx/display_list/mod.rs
@@ -20,15 +20,11 @@ use gfx_traits::{self, StackingContextId};
 use gfx_traits::print_tree::PrintTree;
 use msg::constellation_msg::PipelineId;
 use net_traits::image::base::{Image, PixelFormat};
-use range::Range;
 use servo_geometry::MaxRect;
 use std::cmp::Ordering;
 use std::collections::HashMap;
 use std::f32;
 use std::fmt;
-use std::sync::Arc;
-use text::TextRun;
-use text::glyph::ByteIndex;
 use webrender_api::{BorderRadius, BorderWidths, BoxShadowClipMode, ClipMode, ColorF};
 use webrender_api::{ComplexClipRegion, ExtendMode, ExternalScrollId, FilterOp, FontInstanceKey};
 use webrender_api::{GlyphInstance, GradientStop, ImageBorder, ImageKey, ImageRendering};
@@ -103,25 +99,6 @@ impl DisplayList {
         }
     }
 
-    // Returns the text index within a node for the point of interest.
-    pub fn text_index(&self, node: OpaqueNode, point_in_item: LayoutPoint) -> Option<usize> {
-        for item in &self.list {
-            match item {
-                &DisplayItem::Text(ref text) => {
-                    let base = item.base();
-                    if base.metadata.node == node {
-                        let point = point_in_item + item.base().bounds.origin.to_vector();
-                        let offset = point - text.baseline_origin;
-                        return Some(text.text_run.range_index_of_advance(&text.range, offset.x));
-                    }
-                },
-                _ => {},
-            }
-        }
-
-        None
-    }
-
     pub fn print(&self) {
         let mut print_tree = PrintTree::new("Display List".to_owned());
         self.print_with_tree(&mut print_tree);
@@ -650,16 +627,6 @@ pub struct SolidColorDisplayItem {
 pub struct TextDisplayItem {
     /// Fields common to all display items.
     pub base: BaseDisplayItem,
-
-    /// The text run.
-    #[ignore_malloc_size_of = "Because it is non-owning"]
-    pub text_run: Arc<TextRun>,
-
-    /// The range of text within the text run.
-    pub range: Range<ByteIndex>,
-
-    /// The position of the start of the baseline of this text.
-    pub baseline_origin: LayoutPoint,
     /// A collection of (non-whitespace) glyphs to be displayed.
     pub glyphs: Vec<GlyphInstance>,
     /// Reference to the font to be used.
diff --git a/components/gfx/text/text_run.rs b/components/gfx/text/text_run.rs
index a85c8aababd..62126ab838a 100644
--- a/components/gfx/text/text_run.rs
+++ b/components/gfx/text/text_run.rs
@@ -333,10 +333,10 @@ impl<'a> TextRun {
     }
 
     /// Returns the index in the range of the first glyph advancing over given advance
-    pub fn range_index_of_advance(&self, range: &Range<ByteIndex>, advance: f32) -> usize {
+    pub fn range_index_of_advance(&self, range: &Range<ByteIndex>, advance: Au) -> usize {
         // TODO(Issue #199): alter advance direction for RTL
         // TODO(Issue #98): using inter-char and inter-word spacing settings when measuring text
-        let mut remaining = Au::from_f32_px(advance);
+        let mut remaining = advance;
         self.natural_word_slices_in_range(range)
             .map(|slice| {
                 let (slice_index, slice_advance) =
diff --git a/components/layout/display_list/builder.rs b/components/layout/display_list/builder.rs
index 15a03050e41..da1867980ee 100644
--- a/components/layout/display_list/builder.rs
+++ b/components/layout/display_list/builder.rs
@@ -332,6 +332,9 @@ pub struct DisplayListBuildState<'a> {
     /// Vector containing iframe sizes, used to inform the constellation about
     /// new iframe sizes
     pub iframe_sizes: Vec<(BrowsingContextId, TypedSize2D<f32, CSSPixel>)>,
+
+    /// Stores text runs to answer text queries used to place a cursor inside text.
+    pub indexable_text: IndexableText,
 }
 
 impl<'a> DisplayListBuildState<'a> {
@@ -350,6 +353,7 @@ impl<'a> DisplayListBuildState<'a> {
             current_stacking_context_id: StackingContextId::root(),
             current_clipping_and_scrolling: root_clip_indices,
             iframe_sizes: Vec::new(),
+            indexable_text: IndexableText::default(),
         }
     }
 
@@ -2175,7 +2179,7 @@ impl FragmentDisplayListBuilding for Fragment {
         // Create display items for text decorations.
         let text_decorations = self.style().get_inheritedtext().text_decorations_in_effect;
 
-        let stacking_relative_content_box = LogicalRect::from_physical(
+        let logical_stacking_relative_content_box = LogicalRect::from_physical(
             self.style.writing_mode,
             *stacking_relative_content_box,
             container_size,
@@ -2183,9 +2187,10 @@ impl FragmentDisplayListBuilding for Fragment {
 
         // Underline
         if text_decorations.underline {
-            let mut stacking_relative_box = stacking_relative_content_box;
-            stacking_relative_box.start.b =
-                stacking_relative_content_box.start.b + metrics.ascent - metrics.underline_offset;
+            let mut stacking_relative_box = logical_stacking_relative_content_box;
+            stacking_relative_box.start.b = logical_stacking_relative_content_box.start.b +
+                metrics.ascent -
+                metrics.underline_offset;
             stacking_relative_box.size.block = metrics.underline_size;
             self.build_display_list_for_text_decoration(
                 state,
@@ -2197,7 +2202,7 @@ impl FragmentDisplayListBuilding for Fragment {
 
         // Overline
         if text_decorations.overline {
-            let mut stacking_relative_box = stacking_relative_content_box;
+            let mut stacking_relative_box = logical_stacking_relative_content_box;
             stacking_relative_box.size.block = metrics.underline_size;
             self.build_display_list_for_text_decoration(
                 state,
@@ -2214,11 +2219,16 @@ impl FragmentDisplayListBuilding for Fragment {
             baseline_origin,
         );
         if !glyphs.is_empty() {
-            state.add_display_item(DisplayItem::Text(Box::new(TextDisplayItem {
-                base: base.clone(),
+            let indexable_text = IndexableTextItem {
+                origin: stacking_relative_content_box.origin,
                 text_run: text_fragment.run.clone(),
                 range: text_fragment.range,
-                baseline_origin: baseline_origin.to_layout(),
+                baseline_origin,
+            };
+            state.indexable_text.insert(self.node, indexable_text);
+
+            state.add_display_item(DisplayItem::Text(Box::new(TextDisplayItem {
+                base: base.clone(),
                 glyphs: glyphs,
                 font_key: text_fragment.run.font_key,
                 text_color: text_color.to_layout(),
@@ -2230,7 +2240,7 @@ impl FragmentDisplayListBuilding for Fragment {
 
         // Line-Through
         if text_decorations.line_through {
-            let mut stacking_relative_box = stacking_relative_content_box;
+            let mut stacking_relative_box = logical_stacking_relative_content_box;
             stacking_relative_box.start.b =
                 stacking_relative_box.start.b + metrics.ascent - metrics.strikeout_offset;
             stacking_relative_box.size.block = metrics.strikeout_size;
@@ -3238,3 +3248,42 @@ pub struct BackgroundPlacement {
     /// measures above it is only shown within these bounds.
     css_clip: Rect<Au>,
 }
+
+pub struct IndexableTextItem {
+    /// The placement of the text item on the plane.
+    pub origin: Point2D<Au>,
+    /// The text run.
+    pub text_run: Arc<TextRun>,
+    /// The range of text within the text run.
+    pub range: Range<ByteIndex>,
+    /// The position of the start of the baseline of this text.
+    pub baseline_origin: Point2D<Au>,
+}
+
+#[derive(Default)]
+pub struct IndexableText {
+    inner: FnvHashMap<OpaqueNode, IndexableTextItem>,
+}
+
+impl IndexableText {
+    fn insert(&mut self, node: OpaqueNode, item: IndexableTextItem) {
+        // Guard against duplicate nodes.
+        if self.inner.insert(node, item).is_some() {
+            debug!(
+                "TODO(#20020): Text indexing for {:?} is broken because of multiple text runs.",
+                node
+            );
+        };
+    }
+
+    // Returns the text index within a node for the point of interest.
+    pub fn text_index(&self, node: OpaqueNode, point_in_item: Point2D<Au>) -> Option<usize> {
+        if let Some(item) = self.inner.get(&node) {
+            let point = point_in_item + item.origin.to_vector();
+            let offset = point - item.baseline_origin;
+            Some(item.text_run.range_index_of_advance(&item.range, offset.x))
+        } else {
+            None
+        }
+    }
+}
diff --git a/components/layout/display_list/mod.rs b/components/layout/display_list/mod.rs
index c5f1aa2aa71..917c39687b2 100644
--- a/components/layout/display_list/mod.rs
+++ b/components/layout/display_list/mod.rs
@@ -6,6 +6,7 @@ pub use self::builder::BlockFlowDisplayListBuilding;
 pub use self::builder::BorderPaintingMode;
 pub use self::builder::DisplayListBuildState;
 pub use self::builder::FlexFlowDisplayListBuilding;
+pub use self::builder::IndexableText;
 pub use self::builder::InlineFlowDisplayListBuilding;
 pub use self::builder::ListItemFlowDisplayListBuilding;
 pub use self::builder::StackingContextCollectionFlags;
diff --git a/components/layout/query.rs b/components/layout/query.rs
index bea54d43364..e8a40c3012c 100644
--- a/components/layout/query.rs
+++ b/components/layout/query.rs
@@ -7,6 +7,7 @@
 use app_units::Au;
 use construct::ConstructionResult;
 use context::LayoutContext;
+use display_list::IndexableText;
 use euclid::{Point2D, Vector2D, Rect, Size2D};
 use flow::{Flow, GetBaseFlow};
 use fragment::{Fragment, FragmentBorderBoxIterator, SpecificFragmentInfo};
@@ -51,6 +52,8 @@ pub struct LayoutThreadData {
     /// The root stacking context.
     pub display_list: Option<Arc<DisplayList>>,
 
+    pub indexable_text: IndexableText,
+
     /// A queued response for the union of the content boxes of a node.
     pub content_box_response: Option<Rect<Au>>,
 
diff --git a/components/layout_thread/lib.rs b/components/layout_thread/lib.rs
index a5c3e03293f..85d056d3d4a 100644
--- a/components/layout_thread/lib.rs
+++ b/components/layout_thread/lib.rs
@@ -68,7 +68,7 @@ use layout::context::LayoutContext;
 use layout::context::RegisteredPainter;
 use layout::context::RegisteredPainters;
 use layout::context::malloc_size_of_persistent_local_context;
-use layout::display_list::ToLayout;
+use layout::display_list::{IndexableText, ToLayout};
 use layout::display_list::WebRenderDisplayListConverter;
 use layout::flow::{Flow, GetBaseFlow, ImmutableFlowUtils, MutableOwnedFlowUtils};
 use layout::flow_ref::FlowRef;
@@ -515,6 +515,7 @@ impl LayoutThread {
                 LayoutThreadData {
                     constellation_chan: constellation_chan,
                     display_list: None,
+                    indexable_text: IndexableText::default(),
                     content_box_response: None,
                     content_boxes_response: Vec::new(),
                     client_rect_response: Rect::zero(),
@@ -1002,6 +1003,9 @@ impl LayoutThread {
                         }
                     }
 
+                    rw_data.indexable_text = std::mem::replace(
+                        &mut build_state.indexable_text,
+                        IndexableText::default());
                     rw_data.display_list = Some(Arc::new(build_state.to_display_list()));
                 }
             }
@@ -1366,10 +1370,7 @@ impl LayoutThread {
                     Au::from_f32_px(point_in_node.y)
                 );
                 rw_data.text_index_response = TextIndexResponse(
-                    rw_data.display_list
-                    .as_ref()
-                    .expect("Tried to hit test with no display list")
-                    .text_index(opaque_node, point_in_node.to_layout())
+                    rw_data.indexable_text.text_index(opaque_node, point_in_node)
                 );
             },
             ReflowGoal::NodeGeometryQuery(node) => {