Fix logical ordering of floats and footnotes (#5185)

26 files changed, 458 insertions, 320 deletions

diff --git a/crates/typst/src/foundations/selector.rs b/crates/typst/src/foundations/selector.rs
index 3a9ab308..575baa13 100644
--- a/crates/typst/src/foundations/selector.rs
+++ b/crates/typst/src/foundations/selector.rs
@@ -10,7 +10,7 @@ use crate::foundations::{
     cast, func, repr, scope, ty, CastInfo, Content, Context, Dict, Element, FromValue,
     Func, Label, Reflect, Regex, Repr, Str, StyleChain, Type, Value,
 };
-use crate::introspection::{Introspector, Locatable, Location};
+use crate::introspection::{Introspector, Locatable, Location, Unqueriable};
 use crate::symbols::Symbol;
 
 /// A helper macro to create a field selector used in [`Selector::Elem`]
@@ -339,7 +339,7 @@ impl FromValue for LocatableSelector {
         fn validate(selector: &Selector) -> StrResult<()> {
             match selector {
                 Selector::Elem(elem, _) => {
-                    if !elem.can::<dyn Locatable>() {
+                    if !elem.can::<dyn Locatable>() || elem.can::<dyn Unqueriable>() {
                         Err(eco_format!("{} is not locatable", elem.name()))?
                     }
                 }
diff --git a/crates/typst/src/introspection/counter.rs b/crates/typst/src/introspection/counter.rs
index ba126e18..38da6363 100644
--- a/crates/typst/src/introspection/counter.rs
+++ b/crates/typst/src/introspection/counter.rs
@@ -12,7 +12,7 @@ use crate::foundations::{
     Element, Func, IntoValue, Label, LocatableSelector, NativeElement, Packed, Repr,
     Selector, Show, Smart, Str, StyleChain, Value,
 };
-use crate::introspection::{Introspector, Locatable, Location};
+use crate::introspection::{Introspector, Locatable, Location, Tag};
 use crate::layout::{Frame, FrameItem, PageElem};
 use crate::math::EquationElem;
 use crate::model::{FigureElem, FootnoteElem, HeadingElem, Numbering, NumberingPattern};
@@ -821,8 +821,8 @@ impl ManualPageCounter {
         for (_, item) in page.items() {
             match item {
                 FrameItem::Group(group) => self.visit(engine, &group.frame)?,
-                FrameItem::Tag(tag) => {
-                    let Some(elem) = tag.elem().to_packed::<CounterUpdateElem>() else {
+                FrameItem::Tag(Tag::Start(elem)) => {
+                    let Some(elem) = elem.to_packed::<CounterUpdateElem>() else {
                         continue;
                     };
                     if *elem.key() == CounterKey::Page {
diff --git a/crates/typst/src/introspection/introspector.rs b/crates/typst/src/introspection/introspector.rs
index 45307768..113f9afe 100644
--- a/crates/typst/src/introspection/introspector.rs
+++ b/crates/typst/src/introspection/introspector.rs
@@ -1,16 +1,15 @@
-use std::collections::{BTreeSet, HashMap};
+use std::collections::{BTreeSet, HashMap, HashSet};
 use std::fmt::{self, Debug, Formatter};
 use std::hash::Hash;
 use std::num::NonZeroUsize;
 use std::sync::RwLock;
 
-use ecow::{eco_format, EcoVec};
-use indexmap::IndexMap;
+use ecow::EcoVec;
 use smallvec::SmallVec;
 
 use crate::diag::{bail, StrResult};
 use crate::foundations::{Content, Label, Repr, Selector};
-use crate::introspection::{Location, TagKind};
+use crate::introspection::{Location, Tag};
 use crate::layout::{Frame, FrameItem, Page, Point, Position, Transform};
 use crate::model::Numbering;
 use crate::utils::NonZeroExt;
@@ -20,16 +19,20 @@ use crate::utils::NonZeroExt;
 pub struct Introspector {
     /// The number of pages in the document.
     pages: usize,
-    /// All introspectable elements.
-    elems: IndexMap<Location, (Content, Position)>,
-    /// Maps labels to their indices in the element list. We use a smallvec such
-    /// that if the label is unique, we don't need to allocate.
-    labels: HashMap<Label, SmallVec<[usize; 1]>>,
-    /// Maps from element keys to the locations of all elements that had this
-    /// key. Used for introspector-assisted location assignment.
-    keys: HashMap<u128, SmallVec<[Location; 1]>>,
     /// The page numberings, indexed by page number minus 1.
     page_numberings: Vec<Option<Numbering>>,
+
+    /// All introspectable elements.
+    elems: Vec<Pair>,
+    /// Lists all elements with a specific hash key. This is used for
+    /// introspector-assisted location assignment during measurement.
+    keys: MultiMap<u128, Location>,
+
+    /// Accelerates lookup of elements by location.
+    locations: HashMap<Location, usize>,
+    /// Accelerates lookup of elements by label.
+    labels: MultiMap<Label, usize>,
+
     /// Caches queries done on the introspector. This is important because
     /// even if all top-level queries are distinct, they often have shared
     /// subqueries. Example: Individual counter queries with `before` that
@@ -37,81 +40,56 @@ pub struct Introspector {
     queries: QueryCache,
 }
 
+/// A pair of content and its position.
+type Pair = (Content, Position);
+
 impl Introspector {
-    /// Applies new frames in-place, reusing the existing allocations.
+    /// Creates an introspector for a page list.
     #[typst_macros::time(name = "introspect")]
-    pub fn rebuild(&mut self, pages: &[Page]) {
-        self.pages = pages.len();
-        self.elems.clear();
-        self.labels.clear();
-        self.keys.clear();
-        self.page_numberings.clear();
-        self.queries.clear();
+    pub fn new(pages: &[Page]) -> Self {
+        IntrospectorBuilder::new().build(pages)
+    }
 
-        for (i, page) in pages.iter().enumerate() {
-            let page_nr = NonZeroUsize::new(1 + i).unwrap();
-            self.extract(&page.frame, page_nr, Transform::identity());
-            self.page_numberings.push(page.numbering.clone());
-        }
+    /// Iterates over all locatable elements.
+    pub fn all(&self) -> impl Iterator<Item = &Content> + '_ {
+        self.elems.iter().map(|(c, _)| c)
     }
 
-    /// Extract metadata from a frame.
-    fn extract(&mut self, frame: &Frame, page: NonZeroUsize, ts: Transform) {
-        for (pos, item) in frame.items() {
-            match item {
-                FrameItem::Group(group) => {
-                    let ts = ts
-                        .pre_concat(Transform::translate(pos.x, pos.y))
-                        .pre_concat(group.transform);
-                    self.extract(&group.frame, page, ts);
-                }
-                FrameItem::Tag(tag)
-                    if tag.kind() == TagKind::Start
-                        && !self.elems.contains_key(&tag.location()) =>
-                {
-                    let pos = pos.transform(ts);
-                    let loc = tag.location();
-                    let ret = self
-                        .elems
-                        .insert(loc, (tag.elem().clone(), Position { page, point: pos }));
-                    assert!(ret.is_none(), "duplicate locations");
-
-                    // Build the key map.
-                    self.keys.entry(tag.key()).or_default().push(loc);
-
-                    // Build the label cache.
-                    if let Some(label) = tag.elem().label() {
-                        self.labels.entry(label).or_default().push(self.elems.len() - 1);
-                    }
-                }
-                _ => {}
-            }
-        }
+    /// Retrieves the element with the given index.
+    #[track_caller]
+    fn get_by_idx(&self, idx: usize) -> &Content {
+        &self.elems[idx].0
     }
 
-    /// Iterate over all locatable elements.
-    pub fn all(&self) -> impl Iterator<Item = &Content> + '_ {
-        self.elems.values().map(|(c, _)| c)
+    /// Retrieves the position of the element with the given index.
+    #[track_caller]
+    fn get_pos_by_idx(&self, idx: usize) -> Position {
+        self.elems[idx].1
     }
 
-    /// Perform a binary search for `elem` among the `list`.
-    fn binary_search(&self, list: &[Content], elem: &Content) -> Result<usize, usize> {
-        list.binary_search_by_key(&self.elem_index(elem), |elem| self.elem_index(elem))
+    /// Retrieves an element by its location.
+    fn get_by_loc(&self, location: &Location) -> Option<&Content> {
+        self.locations.get(location).map(|&idx| self.get_by_idx(idx))
     }
 
-    /// Get an element by its location.
-    fn get(&self, location: &Location) -> Option<&Content> {
-        self.elems.get(location).map(|(elem, _)| elem)
+    /// Retrieves the position of the element with the given index.
+    fn get_pos_by_loc(&self, location: &Location) -> Option<Position> {
+        self.locations.get(location).map(|&idx| self.get_pos_by_idx(idx))
     }
 
-    /// Get the index of this element among all.
+    /// Performs a binary search for `elem` among the `list`.
+    fn binary_search(&self, list: &[Content], elem: &Content) -> Result<usize, usize> {
+        list.binary_search_by_key(&self.elem_index(elem), |elem| self.elem_index(elem))
+    }
+
+    /// Gets the index of this element.
     fn elem_index(&self, elem: &Content) -> usize {
         self.loc_index(&elem.location().unwrap())
     }
 
-    /// Get the index of the element with this location among all.
+    /// Gets the index of the element with this location among all.
     fn loc_index(&self, location: &Location) -> usize {
-        self.elems.get_index_of(location).unwrap_or(usize::MAX)
+        self.locations.get(location).copied().unwrap_or(usize::MAX)
     }
 }
 
@@ -125,20 +103,50 @@ impl Introspector {
         }
 
         let output = match selector {
-            Selector::Label(label) => self
-                .labels
-                .get(label)
-                .map(|indices| {
-                    indices.iter().map(|&index| self.elems[index].0.clone()).collect()
-                })
-                .unwrap_or_default(),
-            Selector::Elem(..) | Selector::Can(_) => self
+            Selector::Elem(..) => self
                 .all()
                 .filter(|elem| selector.matches(elem, None))
                 .cloned()
                 .collect(),
             Selector::Location(location) => {
-                self.get(location).cloned().into_iter().collect()
+                self.get_by_loc(location).cloned().into_iter().collect()
+            }
+            Selector::Label(label) => self
+                .labels
+                .get(label)
+                .iter()
+                .map(|&idx| self.get_by_idx(idx).clone())
+                .collect(),
+            Selector::Or(selectors) => selectors
+                .iter()
+                .flat_map(|sel| self.query(sel))
+                .map(|elem| self.elem_index(&elem))
+                .collect::<BTreeSet<usize>>()
+                .into_iter()
+                .map(|idx| self.get_by_idx(idx).clone())
+                .collect(),
+            Selector::And(selectors) => {
+                let mut results: Vec<_> =
+                    selectors.iter().map(|sel| self.query(sel)).collect();
+
+                // Extract the smallest result list and then keep only those
+                // elements in the smallest list that are also in all other
+                // lists.
+                results
+                    .iter()
+                    .enumerate()
+                    .min_by_key(|(_, vec)| vec.len())
+                    .map(|(i, _)| i)
+                    .map(|i| results.swap_remove(i))
+                    .iter()
+                    .flatten()
+                    .filter(|candidate| {
+                        results
+                            .iter()
+                            .all(|other| self.binary_search(other, candidate).is_ok())
+                    })
+                    .cloned()
+                    .collect()
             }
             Selector::Before { selector, end, inclusive } => {
                 let mut list = self.query(selector);
@@ -168,39 +176,8 @@ impl Introspector {
                 }
                 list
             }
-            Selector::And(selectors) => {
-                let mut results: Vec<_> =
-                    selectors.iter().map(|sel| self.query(sel)).collect();
-
-                // Extract the smallest result list and then keep only those
-                // elements in the smallest list that are also in all other
-                // lists.
-                results
-                    .iter()
-                    .enumerate()
-                    .min_by_key(|(_, vec)| vec.len())
-                    .map(|(i, _)| i)
-                    .map(|i| results.swap_remove(i))
-                    .iter()
-                    .flatten()
-                    .filter(|candidate| {
-                        results
-                            .iter()
-                            .all(|other| self.binary_search(other, candidate).is_ok())
-                    })
-                    .cloned()
-                    .collect()
-            }
-            Selector::Or(selectors) => selectors
-                .iter()
-                .flat_map(|sel| self.query(sel))
-                .map(|elem| self.elem_index(&elem))
-                .collect::<BTreeSet<usize>>()
-                .into_iter()
-                .map(|index| self.elems[index].0.clone())
-                .collect(),
             // Not supported here.
-            Selector::Regex(_) => EcoVec::new(),
+            Selector::Can(_) | Selector::Regex(_) => EcoVec::new(),
         };
 
         self.queries.insert(hash, output.clone());
@@ -210,12 +187,12 @@ impl Introspector {
     /// Query for the first element that matches the selector.
     pub fn query_first(&self, selector: &Selector) -> Option<Content> {
         match selector {
-            Selector::Location(location) => self.get(location).cloned(),
+            Selector::Location(location) => self.get_by_loc(location).cloned(),
             Selector::Label(label) => self
                 .labels
                 .get(label)
-                .and_then(|indices| indices.first())
-                .map(|&index| self.elems[index].0.clone()),
+                .first()
+                .map(|&idx| self.get_by_idx(idx).clone()),
             _ => self.query(selector).first().cloned(),
         }
     }
@@ -224,7 +201,7 @@ impl Introspector {
     pub fn query_unique(&self, selector: &Selector) -> StrResult<Content> {
         match selector {
             Selector::Location(location) => self
-                .get(location)
+                .get_by_loc(location)
                 .cloned()
                 .ok_or_else(|| "element does not exist in the document".into()),
             Selector::Label(label) => self.query_label(*label).cloned(),
@@ -243,15 +220,11 @@ impl Introspector {
 
     /// Query for a unique element with the label.
     pub fn query_label(&self, label: Label) -> StrResult<&Content> {
-        let indices = self.labels.get(&label).ok_or_else(|| {
-            eco_format!("label `{}` does not exist in the document", label.repr())
-        })?;
-
-        if indices.len() > 1 {
-            bail!("label `{}` occurs multiple times in the document", label.repr());
+        match *self.labels.get(&label) {
+            [idx] => Ok(self.get_by_idx(idx)),
+            [] => bail!("label `{}` does not exist in the document", label.repr()),
+            _ => bail!("label `{}` occurs multiple times in the document", label.repr()),
         }
-
-        Ok(&self.elems[indices[0]].0)
     }
 
     /// This is an optimized version of
@@ -259,7 +232,7 @@ impl Introspector {
     pub fn query_count_before(&self, selector: &Selector, end: Location) -> usize {
         // See `query()` for details.
         let list = self.query(selector);
-        if let Some(end) = self.get(&end) {
+        if let Some(end) = self.get_by_loc(&end) {
             match self.binary_search(&list, end) {
                 Ok(i) => i + 1,
                 Err(i) => i,
@@ -274,14 +247,6 @@ impl Introspector {
         NonZeroUsize::new(self.pages).unwrap_or(NonZeroUsize::ONE)
     }
 
-    /// Gets the page numbering for the given location, if any.
-    pub fn page_numbering(&self, location: Location) -> Option<&Numbering> {
-        let page = self.page(location);
-        self.page_numberings
-            .get(page.get() - 1)
-            .and_then(|slot| slot.as_ref())
-    }
-
     /// Find the page number for the given location.
     pub fn page(&self, location: Location) -> NonZeroUsize {
         self.position(location).page
@@ -289,12 +254,18 @@ impl Introspector {
 
     /// Find the position for the given location.
     pub fn position(&self, location: Location) -> Position {
-        self.elems
-            .get(&location)
-            .map(|&(_, pos)| pos)
+        self.get_pos_by_loc(&location)
             .unwrap_or(Position { page: NonZeroUsize::ONE, point: Point::zero() })
     }
 
+    /// Gets the page numbering for the given location, if any.
+    pub fn page_numbering(&self, location: Location) -> Option<&Numbering> {
+        let page = self.page(location);
+        self.page_numberings
+            .get(page.get() - 1)
+            .and_then(|slot| slot.as_ref())
+    }
+
     /// Try to find a location for an element with the given `key` hash
     /// that is closest after the `anchor`.
     ///
@@ -304,7 +275,7 @@ impl Introspector {
     pub fn locator(&self, key: u128, anchor: Location) -> Option<Location> {
         let anchor = self.loc_index(&anchor);
         self.keys
-            .get(&key)?
+            .get(&key)
             .iter()
             .copied()
             .min_by_key(|loc| self.loc_index(loc).wrapping_sub(anchor))
@@ -317,6 +288,33 @@ impl Debug for Introspector {
     }
 }
 
+/// A map from one keys to multiple elements.
+#[derive(Clone)]
+struct MultiMap<K, V>(HashMap<K, SmallVec<[V; 1]>>);
+
+impl<K, V> MultiMap<K, V>
+where
+    K: Hash + Eq,
+{
+    fn get(&self, key: &K) -> &[V] {
+        self.0.get(key).map_or(&[], |vec| vec.as_slice())
+    }
+
+    fn insert(&mut self, key: K, value: V) {
+        self.0.entry(key).or_default().push(value);
+    }
+
+    fn take(&mut self, key: &K) -> Option<impl Iterator<Item = V>> {
+        self.0.remove(key).map(|vec| vec.into_iter())
+    }
+}
+
+impl<K, V> Default for MultiMap<K, V> {
+    fn default() -> Self {
+        Self(HashMap::new())
+    }
+}
+
 /// Caches queries.
 #[derive(Default)]
 struct QueryCache(RwLock<HashMap<u128, EcoVec<Content>>>);
@@ -329,10 +327,6 @@ impl QueryCache {
     fn insert(&self, hash: u128, output: EcoVec<Content>) {
         self.0.write().unwrap().insert(hash, output);
     }
-
-    fn clear(&mut self) {
-        self.0.get_mut().unwrap().clear();
-    }
 }
 
 impl Clone for QueryCache {
@@ -340,3 +334,120 @@ impl Clone for QueryCache {
         Self(RwLock::new(self.0.read().unwrap().clone()))
     }
 }
+
+/// Builds the introspector.
+#[derive(Default)]
+struct IntrospectorBuilder {
+    page_numberings: Vec<Option<Numbering>>,
+    seen: HashSet<Location>,
+    insertions: MultiMap<Location, Vec<Pair>>,
+    keys: MultiMap<u128, Location>,
+    locations: HashMap<Location, usize>,
+    labels: MultiMap<Label, usize>,
+}
+
+impl IntrospectorBuilder {
+    /// Create an empty builder.
+    fn new() -> Self {
+        Self::default()
+    }
+
+    /// Build the introspector.
+    fn build(mut self, pages: &[Page]) -> Introspector {
+        self.page_numberings.reserve(pages.len());
+
+        // Discover all elements.
+        let mut root = Vec::new();
+        for (i, page) in pages.iter().enumerate() {
+            self.page_numberings.push(page.numbering.clone());
+            self.discover(
+                &mut root,
+                &page.frame,
+                NonZeroUsize::new(1 + i).unwrap(),
+                Transform::identity(),
+            );
+        }
+
+        self.locations.reserve(self.seen.len());
+
+        // Save all pairs and their descendants in the correct order.
+        let mut elems = Vec::with_capacity(self.seen.len());
+        for pair in root {
+            self.visit(&mut elems, pair);
+        }
+
+        Introspector {
+            pages: pages.len(),
+            page_numberings: self.page_numberings,
+            elems,
+            keys: self.keys,
+            locations: self.locations,
+            labels: self.labels,
+            queries: QueryCache::default(),
+        }
+    }
+
+    /// Processes the tags in the frame.
+    fn discover(
+        &mut self,
+        sink: &mut Vec<Pair>,
+        frame: &Frame,
+        page: NonZeroUsize,
+        ts: Transform,
+    ) {
+        for (pos, item) in frame.items() {
+            match item {
+                FrameItem::Group(group) => {
+                    let ts = ts
+                        .pre_concat(Transform::translate(pos.x, pos.y))
+                        .pre_concat(group.transform);
+
+                    if let Some(parent) = group.parent {
+                        let mut nested = vec![];
+                        self.discover(&mut nested, &group.frame, page, ts);
+                        self.insertions.insert(parent, nested);
+                    } else {
+                        self.discover(sink, &group.frame, page, ts);
+                    }
+                }
+                FrameItem::Tag(Tag::Start(elem)) => {
+                    let loc = elem.location().unwrap();
+                    if self.seen.insert(loc) {
+                        let point = pos.transform(ts);
+                        sink.push((elem.clone(), Position { page, point }));
+                    }
+                }
+                FrameItem::Tag(Tag::End(loc, key)) => {
+                    self.keys.insert(*key, *loc);
+                }
+                _ => {}
+            }
+        }
+    }
+
+    /// Saves a pair and all its descendants into `elems` and populates the
+    /// acceleration structures.
+    fn visit(&mut self, elems: &mut Vec<Pair>, pair: Pair) {
+        let elem = &pair.0;
+        let loc = elem.location().unwrap();
+        let idx = elems.len();
+
+        // Populate the location acceleration map.
+        self.locations.insert(loc, idx);
+
+        // Populate the label acceleration map.
+        if let Some(label) = elem.label() {
+            self.labels.insert(label, idx);
+        }
+
+        // Save the element.
+        elems.push(pair);
+
+        // Process potential descendants.
+        if let Some(insertions) = self.insertions.take(&loc) {
+            for pair in insertions.flatten() {
+                self.visit(elems, pair);
+            }
+        }
+    }
+}
diff --git a/crates/typst/src/introspection/location.rs b/crates/typst/src/introspection/location.rs
index 70076bca..8a7063fc 100644
--- a/crates/typst/src/introspection/location.rs
+++ b/crates/typst/src/introspection/location.rs
@@ -105,5 +105,9 @@ impl Repr for Location {
     }
 }
 
-/// Makes this element locatable through `engine.locate`.
+/// Makes this element as locatable through the introspector.
 pub trait Locatable {}
+
+/// Marks this element as not being queryable even though it is locatable for
+/// internal reasons.
+pub trait Unqueriable {}
diff --git a/crates/typst/src/introspection/tag.rs b/crates/typst/src/introspection/tag.rs
index 7cdea403..b2bae28e 100644
--- a/crates/typst/src/introspection/tag.rs
+++ b/crates/typst/src/introspection/tag.rs
@@ -7,79 +7,48 @@ use crate::foundations::{
 };
 use crate::introspection::Location;
 
-/// Holds a locatable element that was realized.
+/// Marks the start or end of a locatable element.
 #[derive(Clone, PartialEq, Hash)]
-pub struct Tag {
-    /// Whether this is a start or end tag.
-    kind: TagKind,
-    /// The introspectible element.
-    elem: Content,
-    /// The element's key hash.
-    key: u128,
+pub enum Tag {
+    /// The stored element starts here.
+    ///
+    /// Content placed in a tag **must** have a [`Location`] or there will be
+    /// panics.
+    Start(Content),
+    /// The element with the given location and key hash ends here.
+    ///
+    /// Note: The key hash is stored here instead of in `Start` simply to make
+    /// the two enum variants more balanced in size, keeping a `Tag`'s memory
+    /// size down. There are no semantic reasons for this.
+    End(Location, u128),
 }
 
 impl Tag {
-    /// Create a start tag from an element and its key hash.
-    ///
-    /// Panics if the element does not have a [`Location`].
-    #[track_caller]
-    pub fn new(elem: Content, key: u128) -> Self {
-        assert!(elem.location().is_some());
-        Self { elem, key, kind: TagKind::Start }
-    }
-
-    /// Returns the same tag with the given kind.
-    pub fn with_kind(self, kind: TagKind) -> Self {
-        Self { kind, ..self }
-    }
-
-    /// Whether this is a start or end tag.
-    pub fn kind(&self) -> TagKind {
-        self.kind
-    }
-
-    /// The locatable element that the tag holds.
-    pub fn elem(&self) -> &Content {
-        &self.elem
-    }
-
-    /// Access the location of the element.
+    /// Access the location of the tag.
     pub fn location(&self) -> Location {
-        self.elem.location().unwrap()
-    }
-
-    /// The element's key hash, which forms the base of its location (but is
-    /// locally disambiguated and combined with outer hashes).
-    ///
-    /// We need to retain this for introspector-assisted location assignment
-    /// during measurement.
-    pub fn key(&self) -> u128 {
-        self.key
+        match self {
+            Tag::Start(elem) => elem.location().unwrap(),
+            Tag::End(loc, _) => *loc,
+        }
     }
 }
 
 impl Debug for Tag {
     fn fmt(&self, f: &mut Formatter) -> fmt::Result {
-        write!(f, "Tag({:?}, {:?})", self.kind, self.elem.elem().name())
+        match self {
+            Tag::Start(elem) => write!(f, "Start({:?})", elem.elem().name()),
+            Tag::End(..) => f.pad("End"),
+        }
     }
 }
 
-/// Determines whether a tag marks the start or end of an element.
-#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Hash)]
-pub enum TagKind {
-    /// The tag indicates that the element starts here.
-    Start,
-    /// The tag indicates that the element end here.
-    End,
-}
-
 /// Holds a tag for a locatable element that was realized.
 ///
 /// The `TagElem` is handled by all layouters. The held element becomes
 /// available for introspection in the next compiler iteration.
 #[elem(Construct, Unlabellable)]
 pub struct TagElem {
-    /// The introspectible element.
+    /// The introspectable element.
     #[required]
     #[internal]
     pub tag: Tag,
diff --git a/crates/typst/src/layout/container.rs b/crates/typst/src/layout/container.rs
index cc1559c6..d97edd5a 100644
--- a/crates/typst/src/layout/container.rs
+++ b/crates/typst/src/layout/container.rs
@@ -190,7 +190,7 @@ impl Packed<BoxElem> {
 
         // Assign label to the frame.
         if let Some(label) = self.label() {
-            frame.group(|group| group.label = Some(label))
+            frame.label(label);
         }
 
         // Apply baseline shift. Do this after setting the size and applying the
@@ -562,7 +562,7 @@ impl Packed<BlockElem> {
 
         // Assign label to each frame in the fragment.
         if let Some(label) = self.label() {
-            frame.group(|group| group.label = Some(label));
+            frame.label(label);
         }
 
         Ok(frame)
@@ -723,7 +723,7 @@ impl Packed<BlockElem> {
         // Assign label to each frame in the fragment.
         if let Some(label) = self.label() {
             for frame in fragment.iter_mut() {
-                frame.group(|group| group.label = Some(label))
+                frame.label(label);
             }
         }
 
diff --git a/crates/typst/src/layout/flow/collect.rs b/crates/typst/src/layout/flow/collect.rs
index efb16427..ffb45fda 100644
--- a/crates/typst/src/layout/flow/collect.rs
+++ b/crates/typst/src/layout/flow/collect.rs
@@ -11,7 +11,7 @@ use crate::diag::{bail, SourceResult};
 use crate::engine::{Engine, Route, Sink, Traced};
 use crate::foundations::{Packed, Resolve, Smart, StyleChain};
 use crate::introspection::{
-    Introspector, Locator, LocatorLink, SplitLocator, Tag, TagElem,
+    Introspector, Location, Locator, LocatorLink, SplitLocator, Tag, TagElem,
 };
 use crate::layout::{
     layout_frame, Abs, AlignElem, Alignment, Axes, BlockElem, ColbreakElem,
@@ -62,7 +62,7 @@ struct Collector<'a, 'x, 'y> {
 impl<'a> Collector<'a, '_, '_> {
     /// Perform the collection.
     fn run(mut self) -> SourceResult<Vec<Child<'a>>> {
-        for (idx, &(child, styles)) in self.children.iter().enumerate() {
+        for &(child, styles) in self.children {
             if let Some(elem) = child.to_packed::<TagElem>() {
                 self.output.push(Child::Tag(&elem.tag));
             } else if let Some(elem) = child.to_packed::<VElem>() {
@@ -72,7 +72,7 @@ impl<'a> Collector<'a, '_, '_> {
             } else if let Some(elem) = child.to_packed::<BlockElem>() {
                 self.block(elem, styles);
             } else if let Some(elem) = child.to_packed::<PlaceElem>() {
-                self.place(idx, elem, styles)?;
+                self.place(elem, styles)?;
             } else if child.is::<FlushElem>() {
                 self.output.push(Child::Flush);
             } else if let Some(elem) = child.to_packed::<ColbreakElem>() {
@@ -220,7 +220,6 @@ impl<'a> Collector<'a, '_, '_> {
     /// Collects a placed element into a [`PlacedChild`].
     fn place(
         &mut self,
-        idx: usize,
         elem: &'a Packed<PlaceElem>,
         styles: StyleChain<'a>,
     ) -> SourceResult<()> {
@@ -257,7 +256,6 @@ impl<'a> Collector<'a, '_, '_> {
         let clearance = elem.clearance(styles);
         let delta = Axes::new(elem.dx(styles), elem.dy(styles)).resolve(styles);
         self.output.push(Child::Placed(self.boxed(PlacedChild {
-            idx,
             align_x,
             align_y,
             scope,
@@ -553,7 +551,6 @@ impl MultiSpill<'_, '_> {
 /// A child that encapsulates a prepared placed element.
 #[derive(Debug)]
 pub struct PlacedChild<'a> {
-    pub idx: usize,
     pub align_x: FixedAlignment,
     pub align_y: Smart<Option<FixedAlignment>>,
     pub scope: PlacementScope,
@@ -573,16 +570,27 @@ impl PlacedChild<'_> {
         self.cell.get_or_init(base, |base| {
             let align = self.alignment.unwrap_or_else(|| Alignment::CENTER);
             let aligned = AlignElem::set_alignment(align).wrap();
-            layout_frame(
+
+            let mut frame = layout_frame(
                 engine,
                 &self.elem.body,
                 self.locator.relayout(),
                 self.styles.chain(&aligned),
                 Region::new(base, Axes::splat(false)),
-            )
-            .map(|frame| frame.post_processed(self.styles))
+            )?;
+
+            if self.float {
+                frame.set_parent(self.elem.location().unwrap());
+            }
+
+            Ok(frame.post_processed(self.styles))
         })
     }
+
+    /// The element's location.
+    pub fn location(&self) -> Location {
+        self.elem.location().unwrap()
+    }
 }
 
 /// Wraps a parameterized computation and caches its latest output.
diff --git a/crates/typst/src/layout/flow/compose.rs b/crates/typst/src/layout/flow/compose.rs
index 6f14618e..3c52af38 100644
--- a/crates/typst/src/layout/flow/compose.rs
+++ b/crates/typst/src/layout/flow/compose.rs
@@ -1,18 +1,16 @@
 use std::num::NonZeroUsize;
 
-use super::{
-    distribute, Config, FlowResult, LineNumberConfig, PlacedChild, Skip, Stop, Work,
-};
+use super::{distribute, Config, FlowResult, LineNumberConfig, PlacedChild, Stop, Work};
 use crate::diag::SourceResult;
 use crate::engine::Engine;
 use crate::foundations::{Content, NativeElement, Packed, Resolve, Smart};
 use crate::introspection::{
-    Counter, CounterDisplayElem, CounterState, CounterUpdate, Locator, SplitLocator,
-    TagKind,
+    Counter, CounterDisplayElem, CounterState, CounterUpdate, Location, Locator,
+    SplitLocator, Tag,
 };
 use crate::layout::{
-    layout_fragment, layout_frame, Abs, Axes, Dir, FixedAlignment, Frame, FrameItem,
-    OuterHAlignment, PlacementScope, Point, Region, Regions, Rel, Size,
+    layout_fragment, layout_frame, Abs, Axes, Dir, FixedAlignment, Fragment, Frame,
+    FrameItem, OuterHAlignment, PlacementScope, Point, Region, Regions, Rel, Size,
 };
 use crate::model::{
     FootnoteElem, FootnoteEntry, LineNumberingScope, Numbering, ParLineMarker,
@@ -246,7 +244,8 @@ impl<'a, 'b> Composer<'a, 'b, '_, '_> {
         clearance: bool,
     ) -> FlowResult<()> {
         // If the float is already processed, skip it.
-        if self.skipped(Skip::Placed(placed.idx)) {
+        let loc = placed.location();
+        if self.skipped(loc) {
             return Ok(());
         }
 
@@ -317,7 +316,7 @@ impl<'a, 'b> Composer<'a, 'b, '_, '_> {
 
         // Put the float there.
         area.push_float(placed, frame, align_y);
-        area.skips.push(Skip::Placed(placed.idx));
+        area.skips.push(loc);
 
         // Trigger relayout.
         Err(Stop::Relayout(placed.scope))
@@ -391,7 +390,7 @@ impl<'a, 'b> Composer<'a, 'b, '_, '_> {
     ) -> FlowResult<()> {
         // Ignore reference footnotes and already processed ones.
         let loc = elem.location().unwrap();
-        if elem.is_ref() || self.skipped(Skip::Footnote(loc)) {
+        if elem.is_ref() || self.skipped(loc) {
             return Ok(());
         }
 
@@ -420,14 +419,7 @@ impl<'a, 'b> Composer<'a, 'b, '_, '_> {
         pod.size.y -= flow_need + separator_need + self.config.footnote.gap;
 
         // Layout the footnote entry.
-        let frames = layout_fragment(
-            self.engine,
-            &FootnoteEntry::new(elem.clone()).pack(),
-            Locator::synthesize(elem.location().unwrap()),
-            self.config.shared,
-            pod,
-        )?
-        .into_frames();
+        let frames = layout_footnote(self.engine, self.config, &elem, pod)?.into_frames();
 
         // Find nested footnotes in the entry.
         let nested = find_in_frames::<FootnoteElem>(&frames);
@@ -458,7 +450,7 @@ impl<'a, 'b> Composer<'a, 'b, '_, '_> {
 
         // Save the footnote's frame.
         area.push_footnote(self.config, first);
-        area.skips.push(Skip::Footnote(loc));
+        area.skips.push(loc);
         regions.size.y -= note_need;
 
         // Save the spill.
@@ -501,10 +493,10 @@ impl<'a, 'b> Composer<'a, 'b, '_, '_> {
 
     /// Checks whether an insertion was already processed and doesn't need to be
     /// handled again.
-    fn skipped(&self, skip: Skip) -> bool {
-        self.work.skips.contains(&skip)
-            || self.page_insertions.skips.contains(&skip)
-            || self.column_insertions.skips.contains(&skip)
+    fn skipped(&self, loc: Location) -> bool {
+        self.work.skips.contains(&loc)
+            || self.page_insertions.skips.contains(&loc)
+            || self.column_insertions.skips.contains(&loc)
     }
 
     /// The amount of width needed by insertions.
@@ -528,6 +520,29 @@ fn layout_footnote_separator(
     )
 }
 
+/// Lay out a footnote.
+fn layout_footnote(
+    engine: &mut Engine,
+    config: &Config,
+    elem: &Packed<FootnoteElem>,
+    pod: Regions,
+) -> SourceResult<Fragment> {
+    let loc = elem.location().unwrap();
+    layout_fragment(
+        engine,
+        &FootnoteEntry::new(elem.clone()).pack(),
+        Locator::synthesize(loc),
+        config.shared,
+        pod,
+    )
+    .map(|mut fragment| {
+        for frame in &mut fragment {
+            frame.set_parent(loc);
+        }
+        fragment
+    })
+}
+
 /// An additive list of insertions.
 #[derive(Default)]
 struct Insertions<'a, 'b> {
@@ -538,7 +553,7 @@ struct Insertions<'a, 'b> {
     top_size: Abs,
     bottom_size: Abs,
     width: Abs,
-    skips: Vec<Skip>,
+    skips: Vec<Location>,
 }
 
 impl<'a, 'b> Insertions<'a, 'b> {
@@ -836,8 +851,8 @@ fn find_in_frame_impl<T: NativeElement>(
         let y = y_offset + pos.y;
         match item {
             FrameItem::Group(group) => find_in_frame_impl(output, &group.frame, y),
-            FrameItem::Tag(tag) if tag.kind() == TagKind::Start => {
-                if let Some(elem) = tag.elem().to_packed::<T>() {
+            FrameItem::Tag(Tag::Start(elem)) => {
+                if let Some(elem) = elem.to_packed::<T>() {
                     output.push((y, elem.clone()));
                 }
             }
diff --git a/crates/typst/src/layout/flow/distribute.rs b/crates/typst/src/layout/flow/distribute.rs
index a738b3e6..eeb4e76f 100644
--- a/crates/typst/src/layout/flow/distribute.rs
+++ b/crates/typst/src/layout/flow/distribute.rs
@@ -20,7 +20,7 @@ pub fn distribute(composer: &mut Composer, regions: Regions) -> FlowResult<Frame
     };
     let init = distributor.snapshot();
     let forced = match distributor.run() {
-        Ok(()) => true,
+        Ok(()) => distributor.composer.work.done(),
         Err(Stop::Finish(forced)) => forced,
         Err(err) => return Err(err),
     };
diff --git a/crates/typst/src/layout/flow/mod.rs b/crates/typst/src/layout/flow/mod.rs
index 5db70ecb..66ec8e97 100644
--- a/crates/typst/src/layout/flow/mod.rs
+++ b/crates/typst/src/layout/flow/mod.rs
@@ -255,18 +255,7 @@ struct Work<'a, 'b> {
     /// Identifies floats and footnotes that can be skipped if visited because
     /// they were already handled and incorporated as column or page level
     /// insertions.
-    skips: Rc<HashSet<Skip>>,
-}
-
-/// Identifies an element that that can be skipped if visited because it was
-/// already processed.
-#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
-enum Skip {
-    /// Uniquely identifies a placed elements. We can't use a [`Location`]
-    /// because `PlaceElem` is not currently locatable.
-    Placed(usize),
-    /// Uniquely identifies a footnote.
-    Footnote(Location),
+    skips: Rc<HashSet<Location>>,
 }
 
 impl<'a, 'b> Work<'a, 'b> {
@@ -304,7 +293,7 @@ impl<'a, 'b> Work<'a, 'b> {
 
     /// Add skipped floats and footnotes from the insertion areas to the skip
     /// set.
-    fn extend_skips(&mut self, skips: &[Skip]) {
+    fn extend_skips(&mut self, skips: &[Location]) {
         if !skips.is_empty() {
             Rc::make_mut(&mut self.skips).extend(skips.iter().copied());
         }
diff --git a/crates/typst/src/layout/frame.rs b/crates/typst/src/layout/frame.rs
index 2f68e936..cf4153d6 100644
--- a/crates/typst/src/layout/frame.rs
+++ b/crates/typst/src/layout/frame.rs
@@ -7,7 +7,7 @@ use std::sync::Arc;
 use smallvec::SmallVec;
 
 use crate::foundations::{cast, dict, Dict, Label, StyleChain, Value};
-use crate::introspection::Tag;
+use crate::introspection::{Location, Tag};
 use crate::layout::{
     Abs, Axes, Corners, FixedAlignment, HideElem, Length, Point, Rel, Sides, Size,
     Transform,
@@ -407,8 +407,21 @@ impl Frame {
         }
     }
 
+    /// Add a label to the frame.
+    pub fn label(&mut self, label: Label) {
+        self.group(|g| g.label = Some(label));
+    }
+
+    /// Set a parent for the frame. As a result, all elements in the frame
+    /// become logically ordered immediately after the given location.
+    pub fn set_parent(&mut self, parent: Location) {
+        if !self.is_empty() {
+            self.group(|g| g.parent = Some(parent));
+        }
+    }
+
     /// Wrap the frame's contents in a group and modify that group with `f`.
-    pub fn group<F>(&mut self, f: F)
+    fn group<F>(&mut self, f: F)
     where
         F: FnOnce(&mut GroupItem),
     {
@@ -557,6 +570,9 @@ pub struct GroupItem {
     pub clip_path: Option<Path>,
     /// The group's label.
     pub label: Option<Label>,
+    /// The group's logical parent. All elements in this group are logically
+    /// ordered immediately after the parent's start location.
+    pub parent: Option<Location>,
 }
 
 impl GroupItem {
@@ -567,6 +583,7 @@ impl GroupItem {
             transform: Transform::identity(),
             clip_path: None,
             label: None,
+            parent: None,
         }
     }
 }
diff --git a/crates/typst/src/layout/inline/line.rs b/crates/typst/src/layout/inline/line.rs
index a7c41977..a512c32d 100644
--- a/crates/typst/src/layout/inline/line.rs
+++ b/crates/typst/src/layout/inline/line.rs
@@ -575,38 +575,34 @@ fn add_par_line_marker(
     locator: &mut SplitLocator,
     top: Abs,
 ) {
-    if let Some(numbering) = ParLine::numbering_in(styles) {
-        let number_margin = ParLine::number_margin_in(styles);
-        let number_align = ParLine::number_align_in(styles);
-
-        // Delay resolving the number clearance until line numbers are laid out
-        // to avoid inconsistent spacing depending on varying font size.
-        let number_clearance = ParLine::number_clearance_in(styles);
-
-        let mut par_line =
-            ParLineMarker::new(numbering, number_align, number_margin, number_clearance)
-                .pack();
-
-        // Elements in tags must have a location for introspection to work.
-        // We do the work here instead of going through all of the realization
-        // process just for this, given we don't need to actually place the
-        // marker as we manually search for it in the frame later (when
-        // building a root flow, where line numbers can be displayed), so we
-        // just need it to be in a tag and to be valid (to have a location).
-        let hash = crate::utils::hash128(&par_line);
-        let location = locator.next_location(engine.introspector, hash);
-        par_line.set_location(location);
-
-        // Create a tag through which we can search for this line's marker
-        // later. Its 'x' coordinate is not important, just the 'y'
-        // coordinate, as that's what is used for line numbers. We will place
-        // the tag among other subframes in the line such that it is aligned
-        // with the line's general baseline. However, the line number will
-        // still need to manually adjust its own 'y' position based on its own
-        // baseline.
-        let tag = Tag::new(par_line, hash);
-        output.push(Point::with_y(top), FrameItem::Tag(tag));
-    }
+    let Some(numbering) = ParLine::numbering_in(styles) else { return };
+    let margin = ParLine::number_margin_in(styles);
+    let align = ParLine::number_align_in(styles);
+
+    // Delay resolving the number clearance until line numbers are laid out to
+    // avoid inconsistent spacing depending on varying font size.
+    let clearance = ParLine::number_clearance_in(styles);
+
+    // Elements in tags must have a location for introspection to work. We do
+    // the work here instead of going through all of the realization process
+    // just for this, given we don't need to actually place the marker as we
+    // manually search for it in the frame later (when building a root flow,
+    // where line numbers can be displayed), so we just need it to be in a tag
+    // and to be valid (to have a location).
+    let mut marker = ParLineMarker::new(numbering, align, margin, clearance).pack();
+    let key = crate::utils::hash128(&marker);
+    let loc = locator.next_location(engine.introspector, key);
+    marker.set_location(loc);
+
+    // Create start and end tags through which we can search for this line's
+    // marker later. The 'x' coordinate is not important, just the 'y'
+    // coordinate, as that's what is used for line numbers. We will place the
+    // tags among other subframes in the line such that it is aligned with the
+    // line's general baseline. However, the line number will still need to
+    // manually adjust its own 'y' position based on its own baseline.
+    let pos = Point::with_y(top);
+    output.push(pos, FrameItem::Tag(Tag::Start(marker)));
+    output.push(pos, FrameItem::Tag(Tag::End(loc, key)));
 }
 
 /// How much a character should hang into the end margin.
diff --git a/crates/typst/src/layout/pages/collect.rs b/crates/typst/src/layout/pages/collect.rs
index 934fa415..2e7201e2 100644
--- a/crates/typst/src/layout/pages/collect.rs
+++ b/crates/typst/src/layout/pages/collect.rs
@@ -1,7 +1,7 @@
 use std::collections::HashSet;
 
 use crate::foundations::StyleChain;
-use crate::introspection::{Locator, SplitLocator, TagElem, TagKind};
+use crate::introspection::{Locator, SplitLocator, Tag, TagElem};
 use crate::layout::{PagebreakElem, Parity};
 use crate::realize::Pair;
 
@@ -121,7 +121,7 @@ pub fn collect<'a>(
 /// a pagebreak to after it. Returns the position right after the last
 /// non-migrated tag.
 ///
-/// This is important because we want the positions of introspectible elements
+/// This is important because we want the positions of introspectable elements
 /// that technically started before a pagebreak, but have no visible content
 /// yet, to be after the pagebreak. A typical case where this happens is `show
 /// heading: it => pagebreak() + it`.
@@ -136,9 +136,10 @@ fn migrate_unterminated_tags(children: &mut [Pair], mid: usize) -> usize {
     // are terminated).
     let excluded: HashSet<_> = children[start..mid]
         .iter()
-        .filter_map(|(c, _)| c.to_packed::<TagElem>())
-        .filter(|elem| elem.tag.kind() == TagKind::End)
-        .map(|elem| elem.tag.location())
+        .filter_map(|(c, _)| match c.to_packed::<TagElem>()?.tag {
+            Tag::Start(_) => None,
+            Tag::End(loc, _) => Some(loc),
+        })
         .collect();
 
     // A key function that partitions the area of interest into three groups:
diff --git a/crates/typst/src/layout/pages/finalize.rs b/crates/typst/src/layout/pages/finalize.rs
index 116a6baf..d1842613 100644
--- a/crates/typst/src/layout/pages/finalize.rs
+++ b/crates/typst/src/layout/pages/finalize.rs
@@ -40,7 +40,7 @@ pub fn finalize(
     }
 
     // Add the "before" marginals. The order in which we push things here is
-    // important as it affects the relative ordering of introspectible elements
+    // important as it affects the relative ordering of introspectable elements
     // and thus how counters resolve.
     if let Some(background) = background {
         frame.push_frame(Point::zero(), background);
diff --git a/crates/typst/src/layout/pages/mod.rs b/crates/typst/src/layout/pages/mod.rs
index 574703d7..6833d535 100644
--- a/crates/typst/src/layout/pages/mod.rs
+++ b/crates/typst/src/layout/pages/mod.rs
@@ -80,8 +80,9 @@ fn layout_document_impl(
     )?;
 
     let pages = layout_pages(&mut engine, &mut children, locator, styles)?;
+    let introspector = Introspector::new(&pages);
 
-    Ok(Document { pages, info, introspector: Introspector::default() })
+    Ok(Document { pages, info, introspector })
 }
 
 /// Layouts the document's pages.
diff --git a/crates/typst/src/layout/place.rs b/crates/typst/src/layout/place.rs
index 67b50926..6e34f4e2 100644
--- a/crates/typst/src/layout/place.rs
+++ b/crates/typst/src/layout/place.rs
@@ -1,4 +1,5 @@
-use crate::foundations::{elem, scope, Cast, Content, Smart};
+use crate::foundations::{elem, scope, Cast, Content, Packed, Smart};
+use crate::introspection::{Locatable, Unqueriable};
 use crate::layout::{Alignment, Em, Length, Rel};
 
 /// Places content relatively to its parent container.
@@ -65,7 +66,7 @@ use crate::layout::{Alignment, Em, Length, Rel};
 ///
 /// The zero-width weak spacing serves to discard spaces between the function
 /// call and the next word.
-#[elem(scope)]
+#[elem(scope, Locatable, Unqueriable)]
 pub struct PlaceElem {
     /// Relative to which position in the parent container to place the content.
     ///
@@ -163,6 +164,10 @@ pub struct PlaceElem {
     pub body: Content,
 }
 
+/// `PlaceElem` must be locatable to support logical ordering of floats, but I
+/// do not want to expose `query(place)` for now.
+impl Unqueriable for Packed<PlaceElem> {}
+
 #[scope]
 impl PlaceElem {
     #[elem]
diff --git a/crates/typst/src/lib.rs b/crates/typst/src/lib.rs
index 9888e4e4..7f0b8e69 100644
--- a/crates/typst/src/lib.rs
+++ b/crates/typst/src/lib.rs
@@ -152,7 +152,6 @@ fn compile_impl(
 
         // Layout!
         document = crate::layout::layout_document(&mut engine, &content, styles)?;
-        document.introspector.rebuild(&document.pages);
         iter += 1;
 
         if timed!("check stabilized", document.introspector.validate(&constraint)) {
diff --git a/crates/typst/src/realize.rs b/crates/typst/src/realize.rs
index 896c2a6a..b6a969ba 100644
--- a/crates/typst/src/realize.rs
+++ b/crates/typst/src/realize.rs
@@ -18,7 +18,7 @@ use crate::foundations::{
     SequenceElem, Show, ShowSet, Style, StyleChain, StyleVec, StyledElem, Styles,
     Synthesize, Transformation,
 };
-use crate::introspection::{Locatable, SplitLocator, Tag, TagElem, TagKind};
+use crate::introspection::{Locatable, SplitLocator, Tag, TagElem};
 use crate::layout::{
     AlignElem, BoxElem, HElem, InlineElem, PageElem, PagebreakElem, VElem,
 };
@@ -352,9 +352,9 @@ fn visit_show_rules<'a>(
 
     // If the element isn't yet prepared (we're seeing it for the first time),
     // prepare it.
-    let mut tag = None;
+    let mut tags = None;
     if !prepared {
-        tag = prepare(s.engine, s.locator, output.to_mut(), &mut map, styles)?;
+        tags = prepare(s.engine, s.locator, output.to_mut(), &mut map, styles)?;
     }
 
     // Apply a show rule step, if there is one.
@@ -393,9 +393,9 @@ fn visit_show_rules<'a>(
     };
 
     // Push start tag.
-    if let Some(tag) = &tag {
-        let start_tag = TagElem::packed(tag.clone());
-        visit(s, s.store(start_tag), styles)?;
+    let (start, end) = tags.unzip();
+    if let Some(tag) = start {
+        visit(s, s.store(TagElem::packed(tag)), styles)?;
     }
 
     let prev_outside = s.outside;
@@ -409,9 +409,8 @@ fn visit_show_rules<'a>(
     s.engine.route.decrease();
 
     // Push end tag.
-    if let Some(tag) = tag {
-        let end_tag = TagElem::packed(tag.with_kind(TagKind::End));
-        visit(s, s.store(end_tag), styles)?;
+    if let Some(tag) = end {
+        visit(s, s.store(TagElem::packed(tag)), styles)?;
     }
 
     Ok(true)
@@ -517,21 +516,19 @@ fn prepare(
     target: &mut Content,
     map: &mut Styles,
     styles: StyleChain,
-) -> SourceResult<Option<Tag>> {
+) -> SourceResult<Option<(Tag, Tag)>> {
     // Generate a location for the element, which uniquely identifies it in
     // the document. This has some overhead, so we only do it for elements
     // that are explicitly marked as locatable and labelled elements.
     //
     // The element could already have a location even if it is not prepared
     // when it stems from a query.
-    let mut key = None;
-    if target.location().is_some() {
-        key = Some(crate::utils::hash128(&target));
-    } else if target.can::<dyn Locatable>() || target.label().is_some() {
-        let hash = crate::utils::hash128(&target);
-        let location = locator.next_location(engine.introspector, hash);
-        target.set_location(location);
-        key = Some(hash);
+    let key = crate::utils::hash128(&target);
+    if target.location().is_none()
+        && (target.can::<dyn Locatable>() || target.label().is_some())
+    {
+        let loc = locator.next_location(engine.introspector, key);
+        target.set_location(loc);
     }
 
     // Apply built-in show-set rules. User-defined show-set rules are already
@@ -551,18 +548,20 @@ fn prepare(
     // available in rules.
     target.materialize(styles.chain(map));
 
-    // If the element is locatable, create a tag element to be able to find the
-    // element in the frames after layout. Do this after synthesis and
+    // If the element is locatable, create start and end tags to be able to find
+    // the element in the frames after layout. Do this after synthesis and
     // materialization, so that it includes the synthesized fields. Do it before
     // marking as prepared so that show-set rules will apply to this element
     // when queried.
-    let tag = key.map(|key| Tag::new(target.clone(), key));
+    let tags = target
+        .location()
+        .map(|loc| (Tag::Start(target.clone()), Tag::End(loc, key)));
 
     // Ensure that this preparation only runs once by marking the element as
     // prepared.
     target.mark_prepared();
 
-    Ok(tag)
+    Ok(tags)
 }
 
 /// Handles a styled element.
diff --git a/tests/ref/footnote-break-across-pages.png b/tests/ref/footnote-break-across-pages.png
index 2d05fcd5..878227cb 100644
--- a/tests/ref/footnote-break-across-pages.png
+++ b/tests/ref/footnote-break-across-pages.png
diff --git a/tests/ref/footnote-nested-break-across-pages.png b/tests/ref/footnote-nested-break-across-pages.png
new file mode 100644
index 00000000..889fb067
--- /dev/null
+++ b/tests/ref/footnote-nested-break-across-pages.png
diff --git a/tests/ref/footnote-nested.png b/tests/ref/footnote-nested.png
index 501b257e..06617d98 100644
--- a/tests/ref/footnote-nested.png
+++ b/tests/ref/footnote-nested.png
diff --git a/tests/ref/issue-4966-figure-float-counter.png b/tests/ref/issue-4966-figure-float-counter.png
new file mode 100644
index 00000000..9988baea
--- /dev/null
+++ b/tests/ref/issue-4966-figure-float-counter.png
diff --git a/tests/ref/place-float-counter.png b/tests/ref/place-float-counter.png
index 42d40ab5..3253fbab 100644
--- a/tests/ref/place-float-counter.png
+++ b/tests/ref/place-float-counter.png
diff --git a/tests/suite/layout/flow/footnote.typ b/tests/suite/layout/flow/footnote.typ
index 945ae4d3..4cf49777 100644
--- a/tests/suite/layout/flow/footnote.typ
+++ b/tests/suite/layout/flow/footnote.typ
@@ -9,13 +9,16 @@ A#footnote[A] \
 A #footnote[A]
 
 --- footnote-nested ---
-// Currently, numbers a bit out of order if a nested footnote ends up in the
-// same frame as another one. :(
 First \
 Second #footnote[A, #footnote[B, #footnote[C]]]
 Third #footnote[D, #footnote[E]] \
 Fourth #footnote[F]
 
+--- footnote-nested-break-across-pages ---
+#set page(height: 80pt)
+A #footnote([I: ] + lines(6) + footnote[II])
+B #footnote[III]
+
 --- footnote-entry ---
 // Test customization.
 #show footnote: set text(red)
diff --git a/tests/suite/layout/flow/place.typ b/tests/suite/layout/flow/place.typ
index f3b77118..ec27139f 100644
--- a/tests/suite/layout/flow/place.typ
+++ b/tests/suite/layout/flow/place.typ
@@ -165,7 +165,6 @@ C
   place(auto, float: true, block(width: 100%, height: 100%, fill: aqua))
 )
 
-
 --- place-float-column-align-auto ---
 #set page(height: 150pt, columns: 2)
 #set place(auto, float: true, clearance: 10pt)
diff --git a/tests/suite/model/figure.typ b/tests/suite/model/figure.typ
index fbd0ab29..19e81116 100644
--- a/tests/suite/model/figure.typ
+++ b/tests/suite/model/figure.typ
@@ -267,3 +267,25 @@ HI#footnote.entry(clearance: 2.5em)[There]
 // Test that figure caption separator is synthesized correctly.
 #show figure.caption: c => test(c.separator, [#": "])
 #figure(table[], caption: [This is a test caption])
+
+--- issue-4966-figure-float-counter ---
+#let c = context counter(figure.where(kind: image)).display()
+#set align(center)
+
+#c
+
+#figure(
+  square(c),
+  placement: bottom,
+  caption: [A]
+)
+
+#c
+
+#figure(
+  circle(c),
+  placement: top,
+  caption: [B]
+)
+
+#c