Fix infinite loop with footnote which never fits (#5498)

6 files changed, 76 insertions, 5 deletions

diff --git a/crates/typst-layout/src/flow/compose.rs b/crates/typst-layout/src/flow/compose.rs
index 32645675..3cf66f9e 100644
--- a/crates/typst-layout/src/flow/compose.rs
+++ b/crates/typst-layout/src/flow/compose.rs
@@ -15,7 +15,7 @@ use typst_library::model::{
     FootnoteElem, FootnoteEntry, LineNumberingScope, Numbering, ParLineMarker,
 };
 use typst_syntax::Span;
-use typst_utils::NonZeroExt;
+use typst_utils::{NonZeroExt, Numeric};
 
 use super::{distribute, Config, FlowResult, LineNumberConfig, PlacedChild, Stop, Work};
 
@@ -374,7 +374,11 @@ impl<'a, 'b> Composer<'a, 'b, '_, '_> {
 
         let mut relayout = false;
         let mut regions = *regions;
-        let mut migratable = migratable && !breakable && regions.may_progress();
+
+        // The first footnote's origin frame should be migratable if the region
+        // may progress (already checked by the footnote function) and if the
+        // origin frame isn't breakable (checked here).
+        let mut migratable = migratable && !breakable;
 
         for (y, elem) in notes {
             // The amount of space used by the in-flow content that contains the
@@ -464,11 +468,35 @@ impl<'a, 'b> Composer<'a, 'b, '_, '_> {
         // If the first frame is empty, then none of its content fit. If
         // possible, we then migrate the origin frame to the next region to
         // uphold the footnote invariant (that marker and entry are on the same
-        // page). If not, we just queue the footnote for the next page.
+        // page). If not, we just queue the footnote for the next page, but
+        // only if that would actually make a difference (that is, if the
+        // footnote isn't alone in the page after not fitting in any previous
+        // pages, as it probably won't ever fit then).
+        //
+        // Note that a non-zero flow need also indicates that queueing would
+        // make a difference, because the flow need is subtracted from the
+        // available height in the entry's pod even if what caused that need
+        // wasn't considered for the input `regions`. For example, floats just
+        // pass the `regions` they received along to their footnotes, which
+        // don't take into account the space occupied by the floats themselves,
+        // but they do indicate their footnotes have a non-zero flow need, so
+        // queueing them can matter as, in the following pages, the flow need
+        // will be set to zero and the footnote will be alone in the page.
+        // Then, `may_progress()` will also be false (this time, correctly) and
+        // the footnote is laid out, as queueing wouldn't improve the lack of
+        // space anymore and would result in an infinite loop.
+        //
+        // However, it is worth noting that migration does take into account
+        // the original region, before inserting what prompted the flow need.
+        // Logically, if moving the original frame can't improve the lack of
+        // space, then migration should be inhibited. The space occupied by the
+        // original frame is not relevant for that check. Therefore,
+        // `regions.may_progress()` must still be checked separately for
+        // migration, regardless of the presence of flow need.
         if first.is_empty() && exist_non_empty_frame {
-            if migratable {
+            if migratable && regions.may_progress() {
                 return Err(Stop::Finish(false));
-            } else {
+            } else if regions.may_progress() || !flow_need.is_zero() {
                 self.footnote_queue.push(elem);
                 return Ok(());
             }
diff --git a/tests/ref/issue-5496-footnote-in-float-never-fits.png b/tests/ref/issue-5496-footnote-in-float-never-fits.png
new file mode 100644
index 00000000..4ae5903d
--- /dev/null
+++ b/tests/ref/issue-5496-footnote-in-float-never-fits.png
diff --git a/tests/ref/issue-5496-footnote-never-fits-multiple.png b/tests/ref/issue-5496-footnote-never-fits-multiple.png
new file mode 100644
index 00000000..24fcf709
--- /dev/null
+++ b/tests/ref/issue-5496-footnote-never-fits-multiple.png
diff --git a/tests/ref/issue-5496-footnote-never-fits.png b/tests/ref/issue-5496-footnote-never-fits.png
new file mode 100644
index 00000000..4ae5903d
--- /dev/null
+++ b/tests/ref/issue-5496-footnote-never-fits.png
diff --git a/tests/ref/issue-5496-footnote-separator-never-fits.png b/tests/ref/issue-5496-footnote-separator-never-fits.png
new file mode 100644
index 00000000..4fe4fdee
--- /dev/null
+++ b/tests/ref/issue-5496-footnote-separator-never-fits.png
diff --git a/tests/suite/layout/flow/footnote.typ b/tests/suite/layout/flow/footnote.typ
index 885ef627..d7b31b99 100644
--- a/tests/suite/layout/flow/footnote.typ
+++ b/tests/suite/layout/flow/footnote.typ
@@ -315,3 +315,46 @@ A #footnote(numbering: "*")[B]<fn>, C @fn, D @fn, E @fn.
   float: true,
   footnote[b]
 )
+
+--- issue-5496-footnote-never-fits ---
+// Test whether a footnote which is always too large would cause an infinite
+// loop.
+#set page(width: 20pt, height: 20pt)
+#set footnote.entry(indent: 0pt)
+
+#footnote(text(size: 15pt)[a] * 100)
+
+--- issue-5496-footnote-in-float-never-fits ---
+// Test whether an overlarge footnote in a float also does not cause an
+// infinite loop.
+#set page(width: 20pt, height: 20pt)
+
+#place(
+  top,
+  float: true,
+  footnote(text(size: 15pt)[a] * 100)
+)
+
+--- issue-5496-footnote-never-fits-multiple ---
+// Test whether multiple overlarge footnotes are properly split up across
+// pages.
+#set page(width: 20pt, height: 20pt)
+#set footnote.entry(indent: 0pt)
+
+A
+
+#footnote(text(size: 15pt)[a] * 100)
+#footnote(text(size: 15pt)[b] * 100)
+#footnote[Fit]
+
+B
+
+C
+
+--- issue-5496-footnote-separator-never-fits ---
+// Test whether an overlarge footnote separator does not cause an infinite
+// loop and compiles.
+#set page(height: 2em)
+#set footnote.entry(separator: v(5em))
+
+#footnote[]