use crate::checksum::{fit_length, is_mrz_charset, verify};
use crate::dates::Date;
pub const UNKNOWN: char = '?';
pub const MRZ_ALPHABET: &str = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ<";
const MAX_UNKNOWNS: usize = 2;
const MAX_WIDTH_DEFICIT: usize = 2;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum FieldKind {
DocumentNumber,
Date,
PersonalNumber,
Other,
}
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum Resolution {
Unique(String),
Ambiguous {
candidates: Vec<String>,
},
Unresolvable,
}
impl Resolution {
pub fn unique(&self) -> Option<&str> {
match self {
Resolution::Unique(s) => Some(s.as_str()),
_ => None,
}
}
}
pub fn width_candidates(line: &str, target: usize) -> Vec<String> {
let n: String = line.chars().filter(|c| !c.is_whitespace()).collect();
if !n.is_ascii() || target == 0 {
return Vec::new();
}
let mut out: Vec<String> = Vec::new();
for candidate in fit_length(&n, target) {
push_unique(&mut out, candidate, target);
}
let len = n.len();
if len < target {
let deficit = target - len;
if deficit <= MAX_WIDTH_DEFICIT {
let bytes = n.as_bytes();
for at in 0..=len {
let mut s = String::with_capacity(target);
s.push_str(&n[..at]);
for _ in 0..deficit {
s.push(UNKNOWN);
}
s.push_str(&n[at..]);
debug_assert_eq!(bytes.len() + deficit, s.len());
push_unique(&mut out, s, target);
}
}
}
out
}
fn push_unique(out: &mut Vec<String>, candidate: String, target: usize) {
if candidate.len() == target && !out.contains(&candidate) {
out.push(candidate);
}
}
pub fn solve_field(field: &str, check: char, kind: FieldKind) -> Resolution {
if !field.is_ascii() || check == UNKNOWN {
return Resolution::Unresolvable;
}
let chars: Vec<char> = field.chars().collect();
let unknowns: Vec<usize> = chars
.iter()
.enumerate()
.filter(|(_, c)| **c == UNKNOWN)
.map(|(i, _)| i)
.collect();
if unknowns.len() > MAX_UNKNOWNS {
return Resolution::Unresolvable;
}
if chars
.iter()
.any(|c| *c != UNKNOWN && !is_mrz_charset(&c.to_string()))
{
return Resolution::Unresolvable;
}
let alphabet: Vec<char> = MRZ_ALPHABET.chars().collect();
let mut hits: Vec<String> = Vec::new();
let total = alphabet.len().pow(unknowns.len() as u32);
for combo in 0..total {
let mut candidate = chars.clone();
let mut rest = combo;
for &pos in &unknowns {
candidate[pos] = alphabet[rest % alphabet.len()];
rest /= alphabet.len();
}
let s: String = candidate.into_iter().collect();
if verify(&s, check) && satisfies(&s, kind) {
hits.push(s);
}
}
hits.sort();
match hits.len() {
0 => Resolution::Unresolvable,
1 => Resolution::Unique(hits.remove(0)),
_ => Resolution::Ambiguous { candidates: hits },
}
}
const MAX_SUBSTITUTIONS: usize = 1;
const MAX_SUBSTITUTION_CANDIDATES: usize = 256;
pub const CONFUSABLES: &[(char, &str)] = &[
('0', "ODQ"),
('1', "ILTU"),
('2', "Z7"),
('4', "A"),
('5', "S"),
('6', "G"),
('7', "T2"),
('8', "B"),
('9', "G"),
('M', "N"),
];
fn confusable_alternatives(c: char) -> Vec<char> {
let mut alts: Vec<char> = Vec::new();
for &(key, group) in CONFUSABLES {
if c == key {
for g in group.chars() {
if g != c && !alts.contains(&g) {
alts.push(g);
}
}
} else if group.contains(c) && key != c && !alts.contains(&key) {
alts.push(key);
}
}
alts
}
pub fn substitution_candidates(field: &str) -> Vec<String> {
if !field.is_ascii() || field.contains(UNKNOWN) {
return Vec::new();
}
let chars: Vec<char> = field.chars().collect();
let mut out: Vec<String> = Vec::new();
'positions: for i in 0..chars.len() {
for alt in confusable_alternatives(chars[i]) {
let mut candidate = chars.clone();
candidate[i] = alt;
let s: String = candidate.into_iter().collect();
debug_assert_eq!(
s.chars().zip(field.chars()).filter(|(a, b)| a != b).count(),
MAX_SUBSTITUTIONS,
"substitution_candidates must change exactly one position"
);
if s != field && !out.contains(&s) {
out.push(s);
if out.len() >= MAX_SUBSTITUTION_CANDIDATES {
break 'positions;
}
}
}
}
out
}
pub fn solve_substitution(field: &str, check: char, kind: FieldKind) -> Resolution {
if !field.is_ascii() || check == UNKNOWN {
return Resolution::Unresolvable;
}
if verify(field, check) && satisfies(field, kind) {
return Resolution::Unique(field.to_string());
}
let mut hits: Vec<String> = Vec::new();
for candidate in substitution_candidates(field) {
if verify(&candidate, check) && satisfies(&candidate, kind) && !hits.contains(&candidate) {
hits.push(candidate);
}
}
hits.sort();
match hits.len() {
0 => Resolution::Unresolvable,
1 => Resolution::Unique(hits.remove(0)),
_ => Resolution::Ambiguous { candidates: hits },
}
}
pub fn solve_class_sweep(field: &str, check_digit: char, kind: FieldKind) -> Resolution {
if !field.is_ascii() || field.contains(UNKNOWN) || check_digit == UNKNOWN {
return Resolution::Unresolvable;
}
if verify(field, check_digit) && satisfies(field, kind) {
return Resolution::Unresolvable;
}
let chars: Vec<char> = field.chars().collect();
let mut classes: Vec<char> = Vec::new();
for &c in chars.iter().chain(std::iter::once(&check_digit)) {
if !classes.contains(&c) {
classes.push(c);
}
}
let mut hits: Vec<String> = Vec::new();
'classes: for x in classes {
let occurrences = chars.iter().filter(|&&c| c == x).count() + usize::from(check_digit == x);
if occurrences < 2 {
continue;
}
for y in confusable_alternatives(x) {
let swept_field: String = chars.iter().map(|&c| if c == x { y } else { c }).collect();
let swept_check = if check_digit == x { y } else { check_digit };
if verify(&swept_field, swept_check)
&& satisfies(&swept_field, kind)
&& !hits.contains(&swept_field)
{
hits.push(swept_field);
if hits.len() >= MAX_SUBSTITUTION_CANDIDATES {
break 'classes;
}
}
}
}
hits.sort();
match hits.len() {
0 => Resolution::Unresolvable,
1 => Resolution::Unique(hits.remove(0)),
_ => Resolution::Ambiguous { candidates: hits },
}
}
pub(crate) fn concrete_fillings(line: &str) -> Vec<String> {
if !line.is_ascii() {
return Vec::new();
}
let chars: Vec<char> = line.chars().collect();
let unknowns: Vec<usize> = chars
.iter()
.enumerate()
.filter(|(_, c)| **c == UNKNOWN)
.map(|(i, _)| i)
.collect();
if unknowns.is_empty() {
return vec![line.to_string()];
}
if unknowns.len() > MAX_UNKNOWNS {
return Vec::new();
}
let alphabet: Vec<char> = MRZ_ALPHABET.chars().collect();
let mut out = Vec::with_capacity(alphabet.len().pow(unknowns.len() as u32));
for combo in 0..alphabet.len().pow(unknowns.len() as u32) {
let mut candidate = chars.clone();
let mut rest = combo;
for &pos in &unknowns {
candidate[pos] = alphabet[rest % alphabet.len()];
rest /= alphabet.len();
}
out.push(candidate.into_iter().collect());
}
out
}
fn satisfies(field: &str, kind: FieldKind) -> bool {
match kind {
FieldKind::Other => true,
FieldKind::DocumentNumber | FieldKind::PersonalNumber => left_justified(field),
FieldKind::Date => is_plausible_yymmdd(field),
}
}
fn left_justified(field: &str) -> bool {
!field.trim_end_matches('<').contains('<')
}
fn is_plausible_yymmdd(field: &str) -> bool {
if field.len() != 6 || !field.bytes().all(|b| b.is_ascii_digit()) {
return false;
}
let yy: i32 = field[0..2].parse().expect("two ascii digits");
let month: u32 = field[2..4].parse().expect("two ascii digits");
let day: u32 = field[4..6].parse().expect("two ascii digits");
Date::new(1900 + yy, month, day).is_well_formed()
|| Date::new(2000 + yy, month, day).is_well_formed()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::checksum::check_digit;
#[test]
fn width_candidates_are_all_target_width_and_deduplicated() {
for target in [30usize, 36, 44] {
let short: String = "A".repeat(target - 1);
let candidates = width_candidates(&short, target);
assert!(!candidates.is_empty());
for c in &candidates {
assert_eq!(c.len(), target, "candidate {c:?} is not {target} wide");
}
let mut sorted = candidates.clone();
sorted.sort();
sorted.dedup();
assert_eq!(sorted.len(), candidates.len(), "duplicate candidates");
}
}
#[test]
fn width_candidates_sweep_every_insertion_point() {
let candidates = width_candidates("ABCDE", 6);
assert!(candidates.contains(&"?ABCDE".to_string()));
assert!(candidates.contains(&"AB?CDE".to_string()));
assert!(candidates.contains(&"ABCDE?".to_string()));
}
#[test]
fn width_candidates_refuses_a_deficit_it_cannot_bound() {
let candidates = width_candidates("AB", 30);
assert!(
candidates.iter().all(|c| !c.contains(UNKNOWN)),
"a 28-character deficit must not be swept position by position"
);
}
#[test]
fn a_field_with_no_unknowns_is_just_verified() {
assert_eq!(
solve_field("L898902C<", '3', FieldKind::DocumentNumber),
Resolution::Unique("L898902C<".to_string())
);
assert_eq!(
solve_field("L898902C<", '4', FieldKind::DocumentNumber),
Resolution::Unresolvable
);
}
#[test]
fn an_unreadable_check_digit_proves_nothing() {
assert_eq!(
solve_field("6908?22", UNKNOWN, FieldKind::Other),
Resolution::Unresolvable
);
}
#[test]
fn too_many_unknowns_is_refused_not_attempted() {
assert_eq!(
solve_field("???????", '0', FieldKind::Other),
Resolution::Unresolvable
);
}
#[test]
fn left_justified_rejects_an_interior_filler() {
assert!(left_justified("B1987309"));
assert!(left_justified("B198730<"));
assert!(!left_justified("B<987309"));
}
#[test]
fn plausible_dates_reject_impossible_calendars() {
assert!(!is_plausible_yymmdd("890229")); assert!(is_plausible_yymmdd("000229")); assert!(is_plausible_yymmdd("301230"));
assert!(!is_plausible_yymmdd("301332"));
assert!(!is_plausible_yymmdd("D01230"));
assert!(!is_plausible_yymmdd("30123"));
}
#[test]
fn confusable_alternatives_are_bidirectional_and_exclude_identity() {
let mut zero = confusable_alternatives('0');
zero.sort();
assert_eq!(zero, vec!['D', 'O', 'Q']);
assert_eq!(confusable_alternatives('O'), vec!['0']);
assert!(confusable_alternatives('Y').is_empty());
}
#[test]
fn substitution_candidates_never_includes_the_identity_reading() {
for field in ["13E1AE", "AB0234C7", "L898902C", "OOOOOO"] {
let candidates = substitution_candidates(field);
assert!(
!candidates.contains(&field.to_string()),
"{field:?} candidates must never include the unchanged input"
);
}
}
#[test]
fn substitution_candidates_respects_the_cap_on_a_worst_case_input() {
let field = "1".repeat(100);
let candidates = substitution_candidates(&field);
assert_eq!(candidates.len(), MAX_SUBSTITUTION_CANDIDATES);
}
#[test]
fn solve_substitution_leaves_an_already_verifying_field_unchanged() {
assert_eq!(
solve_substitution("L898902C<", '3', FieldKind::DocumentNumber),
Resolution::Unique("L898902C<".to_string())
);
}
#[test]
fn solve_substitution_resolves_a_single_confusable_glyph() {
let field = "13E1AE";
let check = '1';
assert_eq!(check_digit(field).unwrap(), 1, "fixture's own check digit");
let corrupted = "I3E1AE";
assert!(
!verify(corrupted, check),
"the OCR misread must not verify as-is"
);
assert_eq!(
solve_substitution(corrupted, check, FieldKind::Other),
Resolution::Unique(field.to_string())
);
}
#[test]
fn solve_class_sweep_resolves_a_uniform_class_across_field_and_check_digit() {
let misread = "OOOOOOOOO"; assert_eq!(
check_digit("000000000").unwrap(),
0,
"sanity: 9 zeros checksum to 0"
);
assert_eq!(
solve_class_sweep(misread, 'O', FieldKind::DocumentNumber),
Resolution::Unique("000000000".to_string()),
);
}
#[test]
fn solve_class_sweep_refuses_an_already_valid_field_even_when_a_class_would_also_validate() {
let field = "OO";
assert!(
verify(field, '0'),
"fixture must already validate as printed"
);
assert!(
verify("00", '0'),
"the swept reading would *also* validate -- the trap this guards against"
);
assert_eq!(
solve_class_sweep(field, '0', FieldKind::Other),
Resolution::Unresolvable,
"a field that already checksums must never be swept, however tempting the class"
);
}
#[test]
fn solve_class_sweep_ignores_a_single_occurrence() {
assert!(
!confusable_alternatives('A').is_empty(),
"the table does cover 'A'"
);
assert!(!verify("A0B", '9'), "fixture must not already validate");
assert_eq!(
solve_class_sweep("A0B", '9', FieldKind::Other),
Resolution::Unresolvable,
);
}
#[test]
fn solve_class_sweep_reports_ambiguity_instead_of_guessing() {
let field = "<<O<<O<<M<<M";
assert!(!verify(field, '4'), "fixture must not already validate");
assert!(verify("<<0<<0<<M<<M", '4'), "the O-class sweep validates");
assert!(
verify("<<O<<O<<N<<N", '4'),
"the M-class sweep validates too"
);
assert_eq!(
solve_class_sweep(field, '4', FieldKind::Other),
Resolution::Ambiguous {
candidates: vec!["<<0<<0<<M<<M".to_string(), "<<O<<O<<N<<N".to_string()],
}
);
}
#[test]
fn solve_class_sweep_rejects_an_interior_filler_in_a_document_number() {
let field = "O<OB";
assert!(!verify(field, '7'), "fixture must not already validate");
assert!(
verify("0<0B", '7'),
"the swept reading's checksum does verify"
);
assert!(
"0<0B".trim_end_matches('<').contains('<'),
"fixture sanity: the swept reading really does carry an interior filler"
);
assert_eq!(
solve_class_sweep(field, '7', FieldKind::DocumentNumber),
Resolution::Unresolvable,
"an interior filler must be rejected even though the checksum verifies",
);
}
#[test]
fn solve_class_sweep_rejects_a_swept_reading_that_names_no_calendar_date() {
let field = "OO1340";
assert!(
!(verify(field, '4') && is_plausible_yymmdd(field)),
"the already-valid guard must not fire for this fixture"
);
assert!(
verify("001340", '4'),
"the swept reading's checksum does verify"
);
assert!(
!is_plausible_yymmdd("001340"),
"fixture sanity: month 13 is not real"
);
assert_eq!(
solve_class_sweep(field, '4', FieldKind::Date),
Resolution::Unresolvable,
"an impossible calendar date must be rejected even though the checksum verifies",
);
}
#[test]
fn solve_class_sweep_leaves_cross_residue_rejection_untouched() {
let true_field = "2C2";
assert_eq!(
check_digit(true_field).unwrap(),
2,
"sanity: fixture's own check digit"
);
assert!(verify(true_field, '2'), "sanity: the true reading verifies");
let misread = "7C7"; assert!(!verify(misread, '7'), "fixture must not already validate");
assert_eq!(
solve_class_sweep(misread, '7', FieldKind::Other),
Resolution::Unique(true_field.to_string()),
);
}
#[test]
fn solve_class_sweep_never_touches_an_already_valid_field() {
for field in ["0000000", "OOOOOOO", "TTTTTT", "OK<<<<"] {
let check = char::from_digit(check_digit(field).unwrap(), 10).unwrap();
assert!(
verify(field, check),
"{field:?} fixture must already validate"
);
assert_eq!(
solve_class_sweep(field, check, FieldKind::Other),
Resolution::Unresolvable,
"{field:?} already validates; the sweep must not touch it"
);
}
}
#[test]
fn solve_substitution_reports_ambiguity_instead_of_guessing() {
let corrupted = "O0ZVEZ";
let check = '9';
assert!(!verify(corrupted, check));
assert_eq!(
solve_substitution(corrupted, check, FieldKind::Other),
Resolution::Ambiguous {
candidates: vec!["00ZVEZ".to_string(), "OOZVEZ".to_string()],
}
);
}
}