address review: allocate a free list id when the largest id is already taken

crates/formats/src/model/to_doc.rs

@@ -118,6 +118,23 @@ struct Builder<'a> {
     revs: std::collections::HashMap<(u8, RevMark), u32>,
     /// Link and font bytes given to runs so far ([`MAX_RUN_STRINGS`]).
     run_strings: usize,
+    /// The ids the next list's abstract and concrete numbering take: past every id in `doc`,
+    /// found once rather than by a scan of every numbering per list.
+    next_abstract: u32,
+    next_num: u32,
+    /// Ids in use, for when a document already holds `u32::MAX` and the next id wraps.
+    used_abstract: std::collections::HashSet<u32>,
+    used_num: std::collections::HashSet<u32>,
+}
+
+/// The next id from `next` that is not in `used`, wrapping past `u32::MAX` to `min`; marks it used.
+fn free_id(used: &mut std::collections::HashSet<u32>, next: &mut u32, min: u32) -> u32 {
+    let mut id = *next;
+    while !used.insert(id) {
+        id = id.checked_add(1).unwrap_or(min);
+    }
+    *next = id.checked_add(1).unwrap_or(min);
+    id
 }
 
 fn rev_key(kind: RevisionKind) -> u8 {
@@ -137,7 +154,11 @@ impl<'a> Builder<'a> {
                 revs.entry((rev_key(r.kind), mark)).or_insert(i as u32);
             }
         }
-        Builder { doc, revs, run_strings: 0 }
+        let next_abstract = doc.numbering.abstracts.iter().map(|a| a.id.saturating_add(1)).max().unwrap_or(0);
+        let next_num = doc.numbering.nums.iter().map(|n| n.id.saturating_add(1)).max().unwrap_or(1).max(1);
+        let used_abstract = doc.numbering.abstracts.iter().map(|a| a.id).collect();
+        let used_num = doc.numbering.nums.iter().map(|n| n.id).collect();
+        Builder { doc, revs, run_strings: 0, next_abstract, next_num, used_abstract, used_num }
     }
 
     /// The document revision for a tracked change, added the first time it is seen.
@@ -291,9 +312,9 @@ impl<'a> Builder<'a> {
             })
             .collect();
         let numbering = &mut self.doc.numbering;
-        let aid = numbering.abstracts.iter().map(|a| a.id + 1).max().unwrap_or(0);
+        let aid = free_id(&mut self.used_abstract, &mut self.next_abstract, 0);
+        let nid = free_id(&mut self.used_num, &mut self.next_num, 1);
         numbering.abstracts.push(AbstractNum { id: aid, name: None, levels, ..Default::default() });
-        let nid = numbering.nums.iter().map(|n| n.id + 1).max().unwrap_or(1).max(1);
         numbering.nums.push(Num { id: nid, abstract_id: aid, ..Default::default() });
         nid
     }
@@ -449,3 +470,16 @@ pub fn part_blocks(doc: &mut Document, blocks: &[FBlock]) -> Blocks {
     }
     out
 }
+
+#[cfg(test)]
+mod free_id_tests {
+    use super::free_id;
+
+    #[test]
+    fn a_document_holding_the_largest_id_still_gets_free_ones() {
+        let mut used: std::collections::HashSet<u32> = [1, 2, u32::MAX].into();
+        let mut next = u32::MAX;
+        let ids: Vec<u32> = (0..3).map(|_| free_id(&mut used, &mut next, 1)).collect();
+        assert_eq!(ids, [3, 4, 5]);
+    }
+}

crates/formats/src/tests.rs

@@ -1019,3 +1019,14 @@ fn latex_export_keeps_repeated_spaces() {
     let d = crate::import("tex", tex.as_bytes()).unwrap().unwrap();
     assert_eq!(para_texts(&d), vec!["a  b   c".to_string()]);
 }
+
+#[test]
+fn many_imported_lists_take_fresh_numbering_ids_in_turn() {
+    // Each list found its ids by scanning every numbering made before it (quadratic in lists).
+    let md: String = (0..4000).map(|i| if i % 2 == 0 { "- a\n\n" } else { "1. b\n\n" }).collect();
+    let d = import("md", md.as_bytes()).expect("handled").expect("import");
+    let ids: Vec<u32> = d.numbering.nums.iter().map(|n| n.id).collect();
+    assert_eq!(ids, (1..=4000).collect::<Vec<u32>>());
+    let abstracts: Vec<u32> = d.numbering.abstracts.iter().map(|a| a.id).collect();
+    assert_eq!(abstracts, (0..4000).collect::<Vec<u32>>());
+}