Skip to main content

sheetkit_core/utils/
cell_ref.rs

1//! Cell reference conversion utilities.
2//!
3//! Provides functions for converting between A1-style cell references
4//! (e.g. `"A1"`, `"$AB$100"`, `"XFD1048576"`) and 1-based `(col, row)`
5//! numeric coordinates.
6
7use crate::error::{Error, Result};
8use crate::utils::constants::{MAX_COLUMNS, MAX_ROWS};
9use sheetkit_xml::cell_ref::parse_a1_reference;
10use sheetkit_xml::worksheet::CompactCellRef;
11
12/// Create a validated compact A1 reference from 1-based coordinates.
13pub(crate) fn compact_cell_ref(col: u32, row: u32) -> Result<CompactCellRef> {
14    CompactCellRef::from_coordinates(col, row)
15        .map_err(|error| Error::InvalidCellReference(error.to_string()))
16}
17
18/// Decode a [`CompactCellRef`] into `(column, row)`.
19///
20/// Every constructor, including deserialization, admits only canonical,
21/// in-range A1 references, so syntax and range checks are not repeated.
22fn compact_coordinates(reference: &CompactCellRef) -> (u32, u32) {
23    let mut column = 0u32;
24    let mut row = 0u32;
25    for &byte in reference.as_str().as_bytes() {
26        if byte.is_ascii_uppercase() {
27            column = column * 26 + u32::from(byte - b'A') + 1;
28        } else {
29            row = row * 10 + u32::from(byte - b'0');
30        }
31    }
32    debug_assert!(parse_a1_reference(reference.as_str()).is_ok_and(|parsed| {
33        parsed.is_canonical() && parsed.column() == column && parsed.row() == row
34    }));
35    (column, row)
36}
37
38/// Validate worksheet cell structure, then sort rows and cells, cache cell
39/// columns for binary search, and release excess cell capacity.
40pub(crate) fn validate_and_index_worksheet(
41    worksheet: &mut sheetkit_xml::worksheet::WorksheetXml,
42) -> Result<()> {
43    const COLUMN_WORDS: usize = (MAX_COLUMNS as usize).div_ceil(u64::BITS as usize);
44    let mut seen_rows = vec![0u64; (MAX_ROWS as usize).div_ceil(u64::BITS as usize)];
45    // Shared across rows; only rows whose columns are not strictly
46    // increasing use it, and they clear the words they set.
47    let mut seen_columns = [0u64; COLUMN_WORDS];
48    let column_bit = |column: u32| {
49        let index = (column - 1) as usize;
50        (
51            index / u64::BITS as usize,
52            1u64 << (index % u64::BITS as usize),
53        )
54    };
55
56    for row in &mut worksheet.sheet_data.rows {
57        if !(1..=MAX_ROWS).contains(&row.r) {
58            return Err(Error::InvalidRowNumber(row.r));
59        }
60
61        let row_index = (row.r - 1) as usize;
62        let row_word = row_index / u64::BITS as usize;
63        let row_mask = 1u64 << (row_index % u64::BITS as usize);
64        if seen_rows[row_word] & row_mask != 0 {
65            return Err(Error::InvalidCellReference(format!(
66                "duplicate worksheet row {}",
67                row.r
68            )));
69        }
70        seen_rows[row_word] |= row_mask;
71
72        let mut last_column = 0u32;
73        let mut uses_bitset = false;
74        for index in 0..row.cells.len() {
75            let cell = &row.cells[index];
76            let (column, cell_row) = compact_coordinates(&cell.r);
77            if cell_row != row.r {
78                return Err(Error::InvalidCellReference(format!(
79                    "cell '{}' does not belong to worksheet row {}",
80                    cell.r, row.r
81                )));
82            }
83
84            if !uses_bitset && column <= last_column {
85                // Strictly increasing columns cannot repeat. On the first
86                // out-of-order cell, record every earlier column of the row.
87                uses_bitset = true;
88                for earlier in &row.cells[..index] {
89                    let (word, mask) = column_bit(earlier.col);
90                    seen_columns[word] |= mask;
91                }
92            }
93            if uses_bitset {
94                let (word, mask) = column_bit(column);
95                if seen_columns[word] & mask != 0 {
96                    return Err(Error::InvalidCellReference(format!(
97                        "duplicate worksheet cell reference '{}'",
98                        row.cells[index].r
99                    )));
100                }
101                seen_columns[word] |= mask;
102            }
103            last_column = column;
104            // Callers discard the worksheet on error, so caching the column
105            // before the whole sheet is validated cannot leak partial state.
106            row.cells[index].col = column;
107        }
108        if uses_bitset {
109            for cell in &row.cells {
110                seen_columns[column_bit(cell.col).0] = 0;
111            }
112        }
113    }
114
115    worksheet.sheet_data.rows.sort_unstable_by_key(|row| row.r);
116    for row in &mut worksheet.sheet_data.rows {
117        row.cells.sort_unstable_by_key(|cell| cell.col);
118        row.cells.shrink_to_fit();
119    }
120    Ok(())
121}
122
123/// Convert a column name (e.g. `"A"`, `"Z"`, `"AA"`, `"XFD"`) to a 1-based
124/// column number.
125///
126/// # Examples
127///
128/// ```
129/// use sheetkit_core::utils::cell_ref::column_name_to_number;
130///
131/// assert_eq!(column_name_to_number("A").unwrap(), 1);
132/// assert_eq!(column_name_to_number("Z").unwrap(), 26);
133/// assert_eq!(column_name_to_number("AA").unwrap(), 27);
134/// assert_eq!(column_name_to_number("XFD").unwrap(), 16384);
135/// ```
136pub fn column_name_to_number(name: &str) -> Result<u32> {
137    if name.is_empty() {
138        return Err(Error::InvalidCellReference("empty column name".to_string()));
139    }
140
141    let mut result: u32 = 0;
142
143    for c in name.chars() {
144        if !c.is_ascii_alphabetic() {
145            return Err(Error::InvalidCellReference(format!(
146                "non-alphabetic character in column name: '{c}'"
147            )));
148        }
149
150        let digit = (c.to_ascii_uppercase() as u32) - ('A' as u32) + 1;
151
152        result = result
153            .checked_mul(26)
154            .and_then(|r| r.checked_add(digit))
155            .ok_or(Error::InvalidColumnNumber(0))?;
156    }
157
158    if result > MAX_COLUMNS {
159        return Err(Error::InvalidColumnNumber(result));
160    }
161
162    Ok(result)
163}
164
165/// Convert a 1-based column number to its letter name.
166///
167/// # Examples
168///
169/// ```
170/// use sheetkit_core::utils::cell_ref::column_number_to_name;
171///
172/// assert_eq!(column_number_to_name(1).unwrap(), "A");
173/// assert_eq!(column_number_to_name(26).unwrap(), "Z");
174/// assert_eq!(column_number_to_name(27).unwrap(), "AA");
175/// assert_eq!(column_number_to_name(16384).unwrap(), "XFD");
176/// ```
177pub fn column_number_to_name(num: u32) -> Result<String> {
178    if !(1..=MAX_COLUMNS).contains(&num) {
179        return Err(Error::InvalidColumnNumber(num));
180    }
181
182    let mut col = num;
183    let mut result = String::with_capacity(3);
184
185    while col > 0 {
186        col -= 1; // adjust to 0-indexed
187        let remainder = (col % 26) as u8;
188        result.insert(0, (b'A' + remainder) as char);
189        col /= 26;
190    }
191
192    Ok(result)
193}
194
195/// Parse an A1-style cell reference into `(col, row)` coordinates (both
196/// 1-based).
197///
198/// Absolute-reference markers (`$`) are stripped before parsing.
199///
200/// # Examples
201///
202/// ```
203/// use sheetkit_core::utils::cell_ref::cell_name_to_coordinates;
204///
205/// assert_eq!(cell_name_to_coordinates("A1").unwrap(), (1, 1));
206/// assert_eq!(cell_name_to_coordinates("$B$2").unwrap(), (2, 2));
207/// assert_eq!(cell_name_to_coordinates("AA100").unwrap(), (27, 100));
208/// ```
209pub fn cell_name_to_coordinates(cell: &str) -> Result<(u32, u32)> {
210    let parsed =
211        parse_a1_reference(cell).map_err(|error| Error::InvalidCellReference(error.to_string()))?;
212    Ok((parsed.column(), parsed.row()))
213}
214
215/// Convert 1-based `(col, row)` coordinates to an A1-style cell reference.
216///
217/// # Examples
218///
219/// ```
220/// use sheetkit_core::utils::cell_ref::coordinates_to_cell_name;
221///
222/// assert_eq!(coordinates_to_cell_name(1, 1).unwrap(), "A1");
223/// assert_eq!(coordinates_to_cell_name(27, 100).unwrap(), "AA100");
224/// ```
225pub fn coordinates_to_cell_name(col: u32, row: u32) -> Result<String> {
226    if !(1..=MAX_COLUMNS).contains(&col) {
227        return Err(Error::InvalidColumnNumber(col));
228    }
229    if !(1..=MAX_ROWS).contains(&row) {
230        return Err(Error::InvalidRowNumber(row));
231    }
232
233    let col_name = column_number_to_name(col)?;
234    Ok(format!("{col_name}{row}"))
235}
236
237#[cfg(test)]
238mod tests {
239    use super::*;
240
241    #[test]
242    fn test_column_name_a() {
243        assert_eq!(column_name_to_number("A").unwrap(), 1);
244    }
245
246    #[test]
247    fn test_column_name_z() {
248        assert_eq!(column_name_to_number("Z").unwrap(), 26);
249    }
250
251    #[test]
252    fn test_column_name_aa() {
253        assert_eq!(column_name_to_number("AA").unwrap(), 27);
254    }
255
256    #[test]
257    fn test_column_name_az() {
258        assert_eq!(column_name_to_number("AZ").unwrap(), 52);
259    }
260
261    #[test]
262    fn test_column_name_ba() {
263        assert_eq!(column_name_to_number("BA").unwrap(), 53);
264    }
265
266    #[test]
267    fn test_column_name_xfd() {
268        assert_eq!(column_name_to_number("XFD").unwrap(), 16384);
269    }
270
271    #[test]
272    fn test_column_name_lowercase() {
273        assert_eq!(column_name_to_number("a").unwrap(), 1);
274        assert_eq!(column_name_to_number("xfd").unwrap(), 16384);
275    }
276
277    #[test]
278    fn test_column_name_xfe_out_of_range() {
279        assert!(column_name_to_number("XFE").is_err());
280    }
281
282    #[test]
283    fn test_column_name_empty() {
284        assert!(column_name_to_number("").is_err());
285    }
286
287    #[test]
288    fn test_column_name_with_digit() {
289        assert!(column_name_to_number("A1").is_err());
290    }
291
292    #[test]
293    fn test_column_number_1() {
294        assert_eq!(column_number_to_name(1).unwrap(), "A");
295    }
296
297    #[test]
298    fn test_column_number_26() {
299        assert_eq!(column_number_to_name(26).unwrap(), "Z");
300    }
301
302    #[test]
303    fn test_column_number_27() {
304        assert_eq!(column_number_to_name(27).unwrap(), "AA");
305    }
306
307    #[test]
308    fn test_column_number_52() {
309        assert_eq!(column_number_to_name(52).unwrap(), "AZ");
310    }
311
312    #[test]
313    fn test_column_number_53() {
314        assert_eq!(column_number_to_name(53).unwrap(), "BA");
315    }
316
317    #[test]
318    fn test_column_number_16384() {
319        assert_eq!(column_number_to_name(16384).unwrap(), "XFD");
320    }
321
322    #[test]
323    fn test_column_number_0_err() {
324        assert!(column_number_to_name(0).is_err());
325    }
326
327    #[test]
328    fn test_column_number_16385_err() {
329        assert!(column_number_to_name(16385).is_err());
330    }
331
332    #[test]
333    fn test_column_roundtrip_all() {
334        for n in 1..=MAX_COLUMNS {
335            let name = column_number_to_name(n).unwrap();
336            let back = column_name_to_number(&name).unwrap();
337            assert_eq!(n, back, "roundtrip failed for column {n} (name={name})");
338        }
339    }
340
341    #[test]
342    fn test_cell_a1() {
343        assert_eq!(cell_name_to_coordinates("A1").unwrap(), (1, 1));
344    }
345
346    #[test]
347    fn test_cell_z10() {
348        assert_eq!(cell_name_to_coordinates("Z10").unwrap(), (26, 10));
349    }
350
351    #[test]
352    fn test_cell_aa1() {
353        assert_eq!(cell_name_to_coordinates("AA1").unwrap(), (27, 1));
354    }
355
356    #[test]
357    fn test_cell_absolute_a1() {
358        assert_eq!(cell_name_to_coordinates("$A$1").unwrap(), (1, 1));
359    }
360
361    #[test]
362    fn test_cell_absolute_ab100() {
363        assert_eq!(cell_name_to_coordinates("$AB$100").unwrap(), (28, 100));
364    }
365
366    #[test]
367    fn test_cell_mixed_absolute() {
368        assert_eq!(cell_name_to_coordinates("$A1").unwrap(), (1, 1));
369        assert_eq!(cell_name_to_coordinates("A$1").unwrap(), (1, 1));
370    }
371
372    #[test]
373    fn test_cell_max() {
374        assert_eq!(
375            cell_name_to_coordinates("XFD1048576").unwrap(),
376            (16384, 1_048_576)
377        );
378    }
379
380    #[test]
381    fn test_cell_empty_err() {
382        assert!(cell_name_to_coordinates("").is_err());
383    }
384
385    #[test]
386    fn test_cell_only_letters_err() {
387        assert!(cell_name_to_coordinates("ABC").is_err());
388    }
389
390    #[test]
391    fn test_cell_only_digits_err() {
392        assert!(cell_name_to_coordinates("123").is_err());
393    }
394
395    #[test]
396    fn test_cell_row_zero_err() {
397        assert!(cell_name_to_coordinates("A0").is_err());
398    }
399
400    #[test]
401    fn test_cell_row_too_large_err() {
402        assert!(cell_name_to_coordinates("A1048577").is_err());
403    }
404
405    #[test]
406    fn test_cell_col_too_large_err() {
407        assert!(cell_name_to_coordinates("XFE1").is_err());
408    }
409
410    #[test]
411    fn test_cell_rejects_misplaced_absolute_markers() {
412        for reference in ["A$1$", "$A1$", "$$A1", "A$$1"] {
413            assert!(
414                cell_name_to_coordinates(reference).is_err(),
415                "accepted {reference}"
416            );
417        }
418    }
419
420    #[test]
421    fn test_cell_rejects_trailing_junk_overflow_and_utf8() {
422        for reference in ["A1junk", "A42949672960", "A1é"] {
423            assert!(
424                cell_name_to_coordinates(reference).is_err(),
425                "accepted {reference}"
426            );
427        }
428    }
429
430    #[test]
431    fn test_coords_1_1() {
432        assert_eq!(coordinates_to_cell_name(1, 1).unwrap(), "A1");
433    }
434
435    #[test]
436    fn test_coords_27_100() {
437        assert_eq!(coordinates_to_cell_name(27, 100).unwrap(), "AA100");
438    }
439
440    #[test]
441    fn test_coords_max() {
442        assert_eq!(
443            coordinates_to_cell_name(16384, 1_048_576).unwrap(),
444            "XFD1048576"
445        );
446    }
447
448    #[test]
449    fn test_coords_col_0_err() {
450        assert!(coordinates_to_cell_name(0, 1).is_err());
451    }
452
453    #[test]
454    fn test_coords_row_0_err() {
455        assert!(coordinates_to_cell_name(1, 0).is_err());
456    }
457
458    #[test]
459    fn test_coords_col_too_large_err() {
460        assert!(coordinates_to_cell_name(16385, 1).is_err());
461    }
462
463    #[test]
464    fn test_coords_row_too_large_err() {
465        assert!(coordinates_to_cell_name(1, 1_048_577).is_err());
466    }
467
468    #[test]
469    fn test_cell_roundtrip() {
470        let cases = vec![
471            (1, 1, "A1"),
472            (26, 1, "Z1"),
473            (27, 1, "AA1"),
474            (52, 10, "AZ10"),
475            (16384, 1_048_576, "XFD1048576"),
476        ];
477
478        for (col, row, expected_name) in cases {
479            let name = coordinates_to_cell_name(col, row).unwrap();
480            assert_eq!(name, expected_name);
481
482            let (c, r) = cell_name_to_coordinates(&name).unwrap();
483            assert_eq!((c, r), (col, row));
484        }
485    }
486
487    fn worksheet_cell(reference: &str) -> sheetkit_xml::worksheet::Cell {
488        sheetkit_xml::worksheet::Cell {
489            r: CompactCellRef::new(reference).unwrap(),
490            col: 0,
491            s: None,
492            t: sheetkit_xml::worksheet::CellTypeTag::None,
493            v: None,
494            f: None,
495            is: None,
496        }
497    }
498
499    fn worksheet_row(row: u32, references: &[&str]) -> sheetkit_xml::worksheet::Row {
500        sheetkit_xml::worksheet::Row {
501            r: row,
502            spans: None,
503            s: None,
504            custom_format: None,
505            ht: None,
506            custom_height: None,
507            hidden: None,
508            outline_level: None,
509            cells: references
510                .iter()
511                .map(|reference| worksheet_cell(reference))
512                .collect(),
513        }
514    }
515
516    #[test]
517    fn worksheet_indexing_rejects_row_mismatch_and_duplicate_coordinates() {
518        let mut mismatch = sheetkit_xml::worksheet::WorksheetXml::default();
519        mismatch.sheet_data.rows.push(worksheet_row(2, &["A1"]));
520        assert!(validate_and_index_worksheet(&mut mismatch).is_err());
521
522        let mut duplicate_cells = sheetkit_xml::worksheet::WorksheetXml::default();
523        duplicate_cells
524            .sheet_data
525            .rows
526            .push(worksheet_row(1, &["A1", "A1"]));
527        assert!(validate_and_index_worksheet(&mut duplicate_cells).is_err());
528
529        let mut duplicate_rows = sheetkit_xml::worksheet::WorksheetXml::default();
530        duplicate_rows
531            .sheet_data
532            .rows
533            .extend([worksheet_row(1, &["A1"]), worksheet_row(1, &["B1"])]);
534        assert!(validate_and_index_worksheet(&mut duplicate_rows).is_err());
535    }
536
537    #[test]
538    fn worksheet_indexing_detects_out_of_order_duplicates_without_leaking_rows() {
539        let duplicate_message = |references: &[&str]| {
540            let mut worksheet = sheetkit_xml::worksheet::WorksheetXml::default();
541            worksheet.sheet_data.rows.push(worksheet_row(1, references));
542            validate_and_index_worksheet(&mut worksheet)
543                .unwrap_err()
544                .to_string()
545        };
546        assert!(duplicate_message(&["A1", "C1", "B1", "A1"]).contains("duplicate"));
547        assert!(duplicate_message(&["C1", "A1", "C1"]).contains("duplicate"));
548        // The first error in document order wins over later invalid cells.
549        assert!(duplicate_message(&["B1", "B1", "C2"]).contains("duplicate"));
550        assert!(duplicate_message(&["B1", "C2", "B1"]).contains("does not belong"));
551
552        // Columns recorded for one unordered row must not leak into the next.
553        let mut worksheet = sheetkit_xml::worksheet::WorksheetXml::default();
554        worksheet.sheet_data.rows.extend([
555            worksheet_row(1, &["B1", "A1"]),
556            worksheet_row(2, &["B2", "A2"]),
557            worksheet_row(3, &["A3", "B3"]),
558        ]);
559        validate_and_index_worksheet(&mut worksheet).unwrap();
560        let columns: Vec<Vec<u32>> = worksheet
561            .sheet_data
562            .rows
563            .iter()
564            .map(|row| row.cells.iter().map(|cell| cell.col).collect())
565            .collect();
566        assert_eq!(columns, [[1, 2], [1, 2], [1, 2]]);
567    }
568
569    #[test]
570    fn worksheet_indexing_validates_before_sorting_and_populates_columns() {
571        let mut worksheet = sheetkit_xml::worksheet::WorksheetXml::default();
572        worksheet
573            .sheet_data
574            .rows
575            .extend([worksheet_row(2, &["B2", "A2"]), worksheet_row(1, &["C1"])]);
576
577        validate_and_index_worksheet(&mut worksheet).unwrap();
578
579        assert_eq!(
580            worksheet
581                .sheet_data
582                .rows
583                .iter()
584                .map(|row| row.r)
585                .collect::<Vec<_>>(),
586            [1, 2]
587        );
588        assert_eq!(
589            worksheet.sheet_data.rows[1]
590                .cells
591                .iter()
592                .map(|cell| (cell.r.as_str(), cell.col))
593                .collect::<Vec<_>>(),
594            [("A2", 1), ("B2", 2)]
595        );
596    }
597}