Optimization to `Introspector::extract` (#734)

3 files changed, 16 insertions, 12 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 41ad4239..493bc737 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -731,9 +731,9 @@ dependencies = [
 
 [[package]]
 name = "indexmap"
-version = "1.9.2"
+version = "1.9.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
-checksum = "1885e79c1fc4b10f0e172c475f458b7f7b93061064d98c3293e98c5ba0c8b399"
+checksum = "bd070e393353796e801d209ad339e89596eb4c8d430d18ede6a1cced8fafbd99"
 dependencies = [
  "autocfg",
  "hashbrown",
@@ -1606,6 +1606,7 @@ dependencies = [
  "flate2",
  "if_chain",
  "image",
+ "indexmap",
  "log",
  "miniz_oxide 0.5.4",
  "once_cell",
diff --git a/Cargo.toml b/Cargo.toml
index 52aa3708..5df03cf2 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -43,6 +43,7 @@ unicode-xid = "0.2"
 unscanny = "0.1"
 usvg = { version = "0.22", default-features = false }
 xmp-writer = "0.1"
+indexmap = "1.9.3"
 
 [profile.dev]
 debug = 0
diff --git a/src/model/introspect.rs b/src/model/introspect.rs
index 31808872..9697f850 100644
--- a/src/model/introspect.rs
+++ b/src/model/introspect.rs
@@ -2,6 +2,8 @@ use std::fmt::{self, Debug, Formatter};
 use std::hash::Hash;
 use std::num::NonZeroUsize;
 
+use indexmap::IndexMap;
+
 use super::{Content, Selector};
 use crate::diag::StrResult;
 use crate::doc::{Frame, FrameItem, Meta, Position};
@@ -83,7 +85,7 @@ impl StabilityProvider {
 /// Can be queried for elements and their positions.
 pub struct Introspector {
     pages: usize,
-    elems: Vec<(Content, Position)>,
+    elems: IndexMap<Option<Location>, (Content, Position)>,
     // Indexed by page number.
     page_numberings: Vec<Value>,
 }
@@ -93,7 +95,7 @@ impl Introspector {
     pub fn new(frames: &[Frame]) -> Self {
         let mut introspector = Self {
             pages: frames.len(),
-            elems: vec![],
+            elems: IndexMap::new(),
             page_numberings: vec![],
         };
         for (i, frame) in frames.iter().enumerate() {
@@ -105,7 +107,7 @@ impl Introspector {
 
     /// Iterate over all elements.
     pub fn all(&self) -> impl Iterator<Item = &Content> {
-        self.elems.iter().map(|(elem, _)| elem)
+        self.elems.values().map(|(elem, _)| elem)
     }
 
     /// Extract metadata from a frame.
@@ -119,13 +121,14 @@ impl Introspector {
                     self.extract(&group.frame, page, ts);
                 }
                 FrameItem::Meta(Meta::Elem(content), _)
-                    if !self
-                        .elems
-                        .iter()
-                        .any(|(prev, _)| prev.location() == content.location()) =>
+                    if !self.elems.contains_key(&content.location()) =>
                 {
                     let pos = pos.transform(ts);
-                    self.elems.push((content.clone(), Position { page, point: pos }));
+                    let ret = self.elems.insert(
+                        content.location(),
+                        (content.clone(), Position { page, point: pos }),
+                    );
+                    assert!(ret.is_none(), "duplicate locations");
                 }
                 FrameItem::Meta(Meta::PageNumbering(numbering), _) => {
                     self.page_numberings.push(numbering.clone());
@@ -202,8 +205,7 @@ impl Introspector {
     /// Find the position for the given location.
     pub fn position(&self, location: Location) -> Position {
         self.elems
-            .iter()
-            .find(|(elem, _)| elem.location() == Some(location))
+            .get(&Some(location))
             .map(|(_, loc)| *loc)
             .unwrap_or(Position { page: NonZeroUsize::ONE, point: Point::zero() })
     }