Implement textual hit testing

13 files changed, 341 insertions, 75 deletions

diff --git a/core/src/hit_test.rs b/core/src/hit_test.rs
new file mode 100644
index 00000000..a4a7b610
--- /dev/null
+++ b/core/src/hit_test.rs
@@ -0,0 +1,28 @@
+use crate::Vector;
+
+/// The result of hit testing on text.
+#[derive(Debug, Clone, Copy, PartialEq)]
+pub enum HitTestResult {
+    /// The point was within the bounds of the returned character index.
+    CharOffset(usize),
+    /// The provided point was not within the bounds of a glyph. The index
+    /// of the character with the closest centeroid position is returned,
+    /// as well as its delta.
+    NearestCharOffset(usize, Vector),
+}
+
+impl HitTestResult {
+    /// Computes the cursor position corresponding to this [`HitTestResult`] .
+    pub fn cursor(&self) -> usize {
+        match self {
+            HitTestResult::CharOffset(i) => *i,
+            HitTestResult::NearestCharOffset(i, delta) => {
+                if delta.x > f32::EPSILON {
+                    i + 1
+                } else {
+                    *i
+                }
+            }
+        }
+    }
+}
diff --git a/core/src/lib.rs b/core/src/lib.rs
index c4288158..7c4c3c0c 100644
--- a/core/src/lib.rs
+++ b/core/src/lib.rs
@@ -22,6 +22,7 @@ mod align;
 mod background;
 mod color;
 mod font;
+mod hit_test;
 mod length;
 mod padding;
 mod point;
@@ -33,6 +34,7 @@ pub use align::{Align, HorizontalAlignment, VerticalAlignment};
 pub use background::Background;
 pub use color::Color;
 pub use font::Font;
+pub use hit_test::HitTestResult;
 pub use length::Length;
 pub use menu::Menu;
 pub use padding::Padding;
diff --git a/glow/src/backend.rs b/glow/src/backend.rs
index 1680fc00..d97cbceb 100644
--- a/glow/src/backend.rs
+++ b/glow/src/backend.rs
@@ -7,7 +7,9 @@ use iced_graphics::font;
 use iced_graphics::Layer;
 use iced_graphics::Primitive;
 use iced_native::mouse;
-use iced_native::{Font, HorizontalAlignment, Size, VerticalAlignment};
+use iced_native::{
+    Font, HitTestResult, HorizontalAlignment, Size, VerticalAlignment,
+};
 
 /// A [`glow`] graphics backend for [`iced`].
 ///
@@ -211,6 +213,25 @@ impl backend::Text for Backend {
     ) -> (f32, f32) {
         self.text_pipeline.measure(contents, size, font, bounds)
     }
+
+    fn hit_test(
+        &self,
+        contents: &str,
+        size: f32,
+        font: Font,
+        bounds: Size,
+        point: iced_native::Point,
+        nearest_only: bool,
+    ) -> HitTestResult {
+        self.text_pipeline.hit_test(
+            contents,
+            size,
+            font,
+            bounds,
+            point,
+            nearest_only,
+        )
+    }
 }
 
 #[cfg(feature = "image")]
diff --git a/glow/src/text.rs b/glow/src/text.rs
index a4c39dfe..bb882594 100644
--- a/glow/src/text.rs
+++ b/glow/src/text.rs
@@ -1,6 +1,7 @@
 use crate::Transformation;
 use glow_glyph::ab_glyph;
 use iced_graphics::font;
+use iced_native::HitTestResult;
 use std::{cell::RefCell, collections::HashMap};
 
 #[derive(Debug)]
@@ -109,6 +110,97 @@ impl Pipeline {
         }
     }
 
+    pub fn hit_test(
+        &self,
+        content: &str,
+        size: f32,
+        font: iced_native::Font,
+        bounds: iced_native::Size,
+        point: iced_native::Point,
+        nearest_only: bool,
+    ) -> HitTestResult {
+        use glow_glyph::GlyphCruncher;
+
+        let glow_glyph::FontId(font_id) = self.find_font(font);
+
+        let section = glow_glyph::Section {
+            bounds: (bounds.width, bounds.height),
+            text: vec![glow_glyph::Text {
+                text: content,
+                scale: size.into(),
+                font_id: glow_glyph::FontId(font_id),
+                extra: glow_glyph::Extra::default(),
+            }],
+            ..Default::default()
+        };
+
+        let mut mb = self.measure_brush.borrow_mut();
+
+        // The underlying type is FontArc, so clones are cheap.
+        use ab_glyph::{Font, ScaleFont};
+        let font = mb.fonts()[font_id].clone().into_scaled(size);
+
+        // Implements an iterator over the glyph bounding boxes.
+        let bounds = mb.glyphs(section).map(
+            |glow_glyph::SectionGlyph {
+                 byte_index, glyph, ..
+             }| {
+                (
+                    *byte_index,
+                    iced_native::Rectangle::new(
+                        iced_native::Point::new(
+                            glyph.position.x - font.h_side_bearing(glyph.id),
+                            glyph.position.y - font.ascent(),
+                        ),
+                        iced_native::Size::new(
+                            font.h_advance(glyph.id),
+                            font.ascent() - font.descent(),
+                        ),
+                    ),
+                )
+            },
+        );
+
+        // Implements computation of the character index based on the byte index
+        // within the input string.
+        let char_index = |byte_index| {
+            let mut b_count = 0;
+            for (i, utf8_len) in
+                content.chars().map(|c| c.len_utf8()).enumerate()
+            {
+                if byte_index < (b_count + utf8_len) {
+                    return i;
+                }
+                b_count += utf8_len;
+            }
+            return byte_index;
+        };
+
+        if !nearest_only {
+            for (idx, bounds) in bounds.clone() {
+                if bounds.contains(point) {
+                    return HitTestResult::CharOffset(char_index(idx));
+                }
+            }
+        }
+
+        let (idx, nearest) = bounds.fold(
+            (0usize, iced_native::Point::ORIGIN),
+            |acc: (usize, iced_native::Point), (idx, bounds)| {
+                if bounds.center().distance(point) < acc.1.distance(point) {
+                    (idx, bounds.center())
+                } else {
+                    acc
+                }
+            },
+        );
+
+        HitTestResult::NearestCharOffset(
+            char_index(idx),
+            (point - nearest).into(),
+        )
+    }
+
     pub fn trim_measurement_cache(&mut self) {
         // TODO: We should probably use a `GlyphCalculator` for this. However,
         // it uses a lifetimed `GlyphCalculatorGuard` with side-effects on drop.
diff --git a/graphics/src/backend.rs b/graphics/src/backend.rs
index ed1b9e08..94124509 100644
--- a/graphics/src/backend.rs
+++ b/graphics/src/backend.rs
@@ -1,7 +1,7 @@
 //! Write a graphics backend.
 use iced_native::image;
 use iced_native::svg;
-use iced_native::{Font, Size};
+use iced_native::{Font, HitTestResult, Point, Size};
 
 /// The graphics backend of a [`Renderer`].
 ///
@@ -43,6 +43,23 @@ pub trait Text {
         font: Font,
         bounds: Size,
     ) -> (f32, f32);
+
+    /// Tests whether the provided point is within the boundaries of [`Text`]
+    /// laid out with the given parameters, returning information about
+    /// the nearest character.
+    ///
+    /// If nearest_only is true, the hit test does not consider whether the
+    /// the point is interior to any glyph bounds, returning only the character
+    /// with the nearest centeroid.
+    fn hit_test(
+        &self,
+        contents: &str,
+        size: f32,
+        font: Font,
+        bounds: Size,
+        point: Point,
+        nearest_only: bool,
+    ) -> HitTestResult;
 }
 
 /// A graphics backend that supports image rendering.
diff --git a/graphics/src/lib.rs b/graphics/src/lib.rs
index 14388653..687294fc 100644
--- a/graphics/src/lib.rs
+++ b/graphics/src/lib.rs
@@ -40,6 +40,6 @@ pub use transformation::Transformation;
 pub use viewport::Viewport;
 
 pub use iced_native::{
-    Background, Color, Font, HorizontalAlignment, Point, Rectangle, Size,
-    Vector, VerticalAlignment,
+    Background, Color, Font, HitTestResult, HorizontalAlignment, Point,
+    Rectangle, Size, Vector, VerticalAlignment,
 };
diff --git a/graphics/src/widget/text.rs b/graphics/src/widget/text.rs
index 7e22e680..e1b4e4e8 100644
--- a/graphics/src/widget/text.rs
+++ b/graphics/src/widget/text.rs
@@ -4,7 +4,8 @@ use crate::{Primitive, Renderer};
 use iced_native::mouse;
 use iced_native::text;
 use iced_native::{
-    Color, Font, HorizontalAlignment, Rectangle, Size, VerticalAlignment,
+    Color, Font, HitTestResult, HorizontalAlignment, Point, Rectangle, Size,
+    VerticalAlignment,
 };
 
 /// A paragraph of text.
@@ -35,6 +36,25 @@ where
             .measure(content, f32::from(size), font, bounds)
     }
 
+    fn hit_test(
+        &self,
+        content: &str,
+        size: f32,
+        font: Font,
+        bounds: Size,
+        point: Point,
+        nearest_only: bool,
+    ) -> HitTestResult {
+        self.backend().hit_test(
+            content,
+            size,
+            font,
+            bounds,
+            point,
+            nearest_only,
+        )
+    }
+
     fn draw(
         &mut self,
         defaults: &Self::Defaults,
diff --git a/native/src/lib.rs b/native/src/lib.rs
index cbb02506..06bfd3c5 100644
--- a/native/src/lib.rs
+++ b/native/src/lib.rs
@@ -61,8 +61,8 @@ mod debug;
 mod debug;
 
 pub use iced_core::{
-    menu, Align, Background, Color, Font, HorizontalAlignment, Length, Menu,
-    Padding, Point, Rectangle, Size, Vector, VerticalAlignment,
+    menu, Align, Background, Color, Font, HitTestResult, HorizontalAlignment,
+    Length, Menu, Padding, Point, Rectangle, Size, Vector, VerticalAlignment,
 };
 pub use iced_futures::{executor, futures, Command};
 
diff --git a/native/src/renderer/null.rs b/native/src/renderer/null.rs
index bb57c163..3ae05f10 100644
--- a/native/src/renderer/null.rs
+++ b/native/src/renderer/null.rs
@@ -1,8 +1,8 @@
 use crate::{
     button, checkbox, column, container, pane_grid, progress_bar, radio, row,
     scrollable, slider, text, text_input, toggler, Color, Element, Font,
-    HorizontalAlignment, Layout, Padding, Point, Rectangle, Renderer, Size,
-    VerticalAlignment,
+    HitTestResult, HorizontalAlignment, Layout, Padding, Point, Rectangle,
+    Renderer, Size, Vector, VerticalAlignment,
 };
 
 /// A renderer that does nothing.
@@ -67,6 +67,18 @@ impl text::Renderer for Null {
         (0.0, 20.0)
     }
 
+    fn hit_test(
+        &self,
+        _contents: &str,
+        _size: f32,
+        _font: Self::Font,
+        _bounds: Size,
+        _point: Point,
+        _nearest_only: bool,
+    ) -> HitTestResult {
+        HitTestResult::NearestCharOffset(0, Vector::new(0., 0.))
+    }
+
     fn draw(
         &mut self,
         _defaults: &Self::Defaults,
diff --git a/native/src/widget/text.rs b/native/src/widget/text.rs
index 6cc18e6c..f37f90a9 100644
--- a/native/src/widget/text.rs
+++ b/native/src/widget/text.rs
@@ -1,7 +1,7 @@
 //! Write some text for your users to read.
 use crate::{
-    layout, Color, Element, Hasher, HorizontalAlignment, Layout, Length, Point,
-    Rectangle, Size, VerticalAlignment, Widget,
+    layout, Color, Element, Hasher, HitTestResult, HorizontalAlignment, Layout,
+    Length, Point, Rectangle, Size, VerticalAlignment, Widget,
 };
 
 use std::hash::Hash;
@@ -179,6 +179,23 @@ pub trait Renderer: crate::Renderer {
         bounds: Size,
     ) -> (f32, f32);
 
+    /// Tests whether the provided point is within the boundaries of [`Text`]
+    /// laid out with the given parameters, returning information about
+    /// the nearest character.
+    ///
+    /// If nearest_only is true, the hit test does not consider whether the
+    /// the point is interior to any glyph bounds, returning only the character
+    /// with the nearest centeroid.
+    fn hit_test(
+        &self,
+        contents: &str,
+        size: f32,
+        font: Self::Font,
+        bounds: Size,
+        point: Point,
+        nearest_only: bool,
+    ) -> HitTestResult;
+
     /// Draws a [`Text`] fragment.
     ///
     /// It receives:
diff --git a/native/src/widget/text_input.rs b/native/src/widget/text_input.rs
index bb64d5b7..f1a7a1a0 100644
--- a/native/src/widget/text_input.rs
+++ b/native/src/widget/text_input.rs
@@ -707,15 +707,15 @@ pub trait Renderer: text::Renderer + Sized {
 
         let offset = self.offset(text_bounds, font, size, &value, &state);
 
-        find_cursor_position(
-            self,
-            &value,
+        self.hit_test(
+            &value.to_string(),
+            size.into(),
             font,
-            size,
-            x + offset,
-            0,
-            value.len(),
+            Size::INFINITY,
+            Point::new(x + offset, text_bounds.height / 2.0),
+            true,
         )
+        .cursor()
     }
 }
 
@@ -803,62 +803,6 @@ impl State {
     }
 }
 
-// TODO: Reduce allocations
-fn find_cursor_position<Renderer: self::Renderer>(
-    renderer: &Renderer,
-    value: &Value,
-    font: Renderer::Font,
-    size: u16,
-    target: f32,
-    start: usize,
-    end: usize,
-) -> usize {
-    if start >= end {
-        if start == 0 {
-            return 0;
-        }
-
-        let prev = value.until(start - 1);
-        let next = value.until(start);
-
-        let prev_width = renderer.measure_value(&prev.to_string(), size, font);
-        let next_width = renderer.measure_value(&next.to_string(), size, font);
-
-        if next_width - target > target - prev_width {
-            return start - 1;
-        } else {
-            return start;
-        }
-    }
-
-    let index = (end - start) / 2;
-    let subvalue = value.until(start + index);
-
-    let width = renderer.measure_value(&subvalue.to_string(), size, font);
-
-    if width > target {
-        find_cursor_position(
-            renderer,
-            value,
-            font,
-            size,
-            target,
-            start,
-            start + index,
-        )
-    } else {
-        find_cursor_position(
-            renderer,
-            value,
-            font,
-            size,
-            target,
-            start + index + 1,
-            end,
-        )
-    }
-}
-
 mod platform {
     use crate::keyboard;
 
diff --git a/wgpu/src/backend.rs b/wgpu/src/backend.rs
index 4f34045b..fe8ed255 100644
--- a/wgpu/src/backend.rs
+++ b/wgpu/src/backend.rs
@@ -7,7 +7,9 @@ use iced_graphics::font;
 use iced_graphics::layer::Layer;
 use iced_graphics::{Primitive, Viewport};
 use iced_native::mouse;
-use iced_native::{Font, HorizontalAlignment, Size, VerticalAlignment};
+use iced_native::{
+    Font, HitTestResult, HorizontalAlignment, Size, VerticalAlignment,
+};
 
 #[cfg(any(feature = "image_rs", feature = "svg"))]
 use crate::image;
@@ -274,6 +276,25 @@ impl backend::Text for Backend {
     ) -> (f32, f32) {
         self.text_pipeline.measure(contents, size, font, bounds)
     }
+
+    fn hit_test(
+        &self,
+        contents: &str,
+        size: f32,
+        font: Font,
+        bounds: Size,
+        point: iced_native::Point,
+        nearest_only: bool,
+    ) -> HitTestResult {
+        self.text_pipeline.hit_test(
+            contents,
+            size,
+            font,
+            bounds,
+            point,
+            nearest_only,
+        )
+    }
 }
 
 #[cfg(feature = "image_rs")]
diff --git a/wgpu/src/text.rs b/wgpu/src/text.rs
index 2b5b94c9..f227cb6f 100644
--- a/wgpu/src/text.rs
+++ b/wgpu/src/text.rs
@@ -1,5 +1,6 @@
 use crate::Transformation;
 use iced_graphics::font;
+use iced_native::HitTestResult;
 use std::{cell::RefCell, collections::HashMap};
 use wgpu_glyph::ab_glyph;
 
@@ -117,6 +118,97 @@ impl Pipeline {
         }
     }
 
+    pub fn hit_test(
+        &self,
+        content: &str,
+        size: f32,
+        font: iced_native::Font,
+        bounds: iced_native::Size,
+        point: iced_native::Point,
+        nearest_only: bool,
+    ) -> HitTestResult {
+        use wgpu_glyph::GlyphCruncher;
+
+        let wgpu_glyph::FontId(font_id) = self.find_font(font);
+
+        let section = wgpu_glyph::Section {
+            bounds: (bounds.width, bounds.height),
+            text: vec![wgpu_glyph::Text {
+                text: content,
+                scale: size.into(),
+                font_id: wgpu_glyph::FontId(font_id),
+                extra: wgpu_glyph::Extra::default(),
+            }],
+            ..Default::default()
+        };
+
+        let mut mb = self.measure_brush.borrow_mut();
+
+        // The underlying type is FontArc, so clones are cheap.
+        use wgpu_glyph::ab_glyph::{Font, ScaleFont};
+        let font = mb.fonts()[font_id].clone().into_scaled(size);
+
+        // Implements an iterator over the glyph bounding boxes.
+        let bounds = mb.glyphs(section).map(
+            |wgpu_glyph::SectionGlyph {
+                 byte_index, glyph, ..
+             }| {
+                (
+                    *byte_index,
+                    iced_native::Rectangle::new(
+                        iced_native::Point::new(
+                            glyph.position.x - font.h_side_bearing(glyph.id),
+                            glyph.position.y - font.ascent(),
+                        ),
+                        iced_native::Size::new(
+                            font.h_advance(glyph.id),
+                            font.ascent() - font.descent(),
+                        ),
+                    ),
+                )
+            },
+        );
+
+        // Implements computation of the character index based on the byte index
+        // within the input string.
+        let char_index = |byte_index| {
+            let mut b_count = 0;
+            for (i, utf8_len) in
+                content.chars().map(|c| c.len_utf8()).enumerate()
+            {
+                if byte_index < (b_count + utf8_len) {
+                    return i;
+                }
+                b_count += utf8_len;
+            }
+            return byte_index;
+        };
+
+        if !nearest_only {
+            for (idx, bounds) in bounds.clone() {
+                if bounds.contains(point) {
+                    return HitTestResult::CharOffset(char_index(idx));
+                }
+            }
+        }
+
+        let (idx, nearest) = bounds.fold(
+            (0usize, iced_native::Point::ORIGIN),
+            |acc: (usize, iced_native::Point), (idx, bounds)| {
+                if bounds.center().distance(point) < acc.1.distance(point) {
+                    (idx, bounds.center())
+                } else {
+                    acc
+                }
+            },
+        );
+
+        HitTestResult::NearestCharOffset(
+            char_index(idx),
+            (point - nearest).into(),
+        )
+    }
+
     pub fn trim_measurement_cache(&mut self) {
         // TODO: We should probably use a `GlyphCalculator` for this. However,
         // it uses a lifetimed `GlyphCalculatorGuard` with side-effects on drop.