teamcraft/services/
duplicates.rs

1//! Likely duplicate items by name: before (or right after) an item is
2//! created, the items whose latest revision has a similar name are offered,
3//! so an existing part is reused instead of created twice. Read-only and
4//! limited to the items the actor may read.
5//!
6//! The candidates come from SQL (a name containing one of the words of the
7//! new name, at most `CANDIDATES`); the similarity is computed here, so it
8//! works without the optional `pg_trgm` extension.
9
10use serde::Serialize;
11use sqlx::PgPool;
12use uuid::Uuid;
13
14use crate::{auth::Actor, domain::ItemType, error::AppResult, services::access};
15
16/// Rows the SQL pre-filter hands over at most.
17const CANDIDATES: i64 = 200;
18/// Score from which a name counts as similar.
19pub const THRESHOLD: f64 = 0.6;
20
21#[derive(Clone, Debug, Serialize, PartialEq)]
22pub struct Duplicate {
23    pub item_id: Uuid,
24    pub number: String,
25    pub item_type: String,
26    pub project_code: Option<String>,
27    pub revision_id: Uuid,
28    pub code: String,
29    pub state: String,
30    pub name: String,
31    /// 0..1, 1 = the same name.
32    pub score: f64,
33}
34
35#[derive(sqlx::FromRow)]
36struct Candidate {
37    item_id: Uuid,
38    number: String,
39    item_type: String,
40    project_code: Option<String>,
41    revision_id: Uuid,
42    code: String,
43    state: String,
44    name: String,
45}
46
47/// Lower-case words of a name (letters and digits, at least two characters),
48/// each once: `"Bracket, M8 – left"` → `["bracket", "m8", "left"]`.
49pub fn words(name: &str) -> Vec<String> {
50    let mut out: Vec<String> = Vec::new();
51    for w in name
52        .split(|c: char| !c.is_alphanumeric())
53        .map(str::to_lowercase)
54        .filter(|w| w.chars().count() >= 2)
55    {
56        if !out.contains(&w) {
57            out.push(w);
58        }
59    }
60    out
61}
62
63/// Levenshtein distance over characters.
64fn edit_distance(a: &[char], b: &[char]) -> usize {
65    let mut prev: Vec<usize> = (0..=b.len()).collect();
66    let mut cur = vec![0; b.len() + 1];
67    for (i, ca) in a.iter().enumerate() {
68        cur[0] = i + 1;
69        for (j, cb) in b.iter().enumerate() {
70            let cost = usize::from(ca != cb);
71            cur[j + 1] = (prev[j] + cost).min(prev[j + 1] + 1).min(cur[j] + 1);
72        }
73        std::mem::swap(&mut prev, &mut cur);
74    }
75    prev[b.len()]
76}
77
78/// Similarity of two names, 0..1: the better of the word overlap (Jaccard)
79/// and the edit similarity of the names without spaces and punctuation, so
80/// both "Bracket left M8" / "M8 bracket left" and "Brakcet" / "Bracket"
81/// count as similar.
82pub fn similarity(a: &str, b: &str) -> f64 {
83    let (wa, wb) = (words(a), words(b));
84    // the Jaccard index |A∩B| / |A∪B| (the word lists hold each word once)
85    let common = wa.iter().filter(|w| wb.contains(w)).count();
86    let union = wa.len() + wb.len() - common;
87    let jaccard = if union == 0 {
88        0.0
89    } else {
90        common as f64 / union as f64
91    };
92    let compact = |s: &str| -> Vec<char> { words(s).concat().chars().collect() };
93    let (ca, cb) = (compact(a), compact(b));
94    let longest = ca.len().max(cb.len());
95    let edit = if longest == 0 {
96        0.0
97    } else {
98        1.0 - edit_distance(&ca, &cb) as f64 / longest as f64
99    };
100    jaccard.max(edit)
101}
102
103/// The items most similar to `name` (best first, at most `limit`), of the
104/// same type when one is given; `exclude` leaves out an item (the one just
105/// created).
106pub async fn likely_duplicates(
107    pool: &PgPool,
108    actor: &Actor,
109    name: &str,
110    item_type: Option<ItemType>,
111    exclude: Option<Uuid>,
112    limit: usize,
113) -> AppResult<Vec<Duplicate>> {
114    let patterns: Vec<String> = words(name)
115        .into_iter()
116        .filter(|w| w.chars().count() >= 3)
117        .take(8)
118        .map(|w| crate::domain::like_pattern(&w))
119        .collect();
120    if patterns.is_empty() {
121        return Ok(Vec::new());
122    }
123    let sql = format!(
124        "SELECT i.id AS item_id, i.number, i.item_type, p.code AS project_code,
125                lr.id AS revision_id, lr.code, lr.state, lr.name
126         FROM items i
127         LEFT JOIN projects p ON p.id = i.project_id
128         CROSS JOIN LATERAL (
129             SELECT r.id, r.code, r.state, r.name FROM revisions r
130             WHERE r.item_id = i.id ORDER BY r.seq DESC LIMIT 1
131         ) lr
132         WHERE i.id IN (SELECT r.item_id FROM revisions r WHERE r.name ILIKE ANY($1))
133           AND lr.name ILIKE ANY($1)
134           AND ($2::text IS NULL OR i.item_type = $2)
135           AND ($3::uuid IS NULL OR i.id <> $3)
136           AND {}
137         ORDER BY i.number
138         LIMIT {CANDIDATES}",
139        access::item_visible("i", 4)
140    );
141    let rows = sqlx::query_as::<_, Candidate>(&sql)
142        .bind(&patterns)
143        .bind(item_type.map(|t| t.as_str()))
144        .bind(exclude)
145        .bind(&actor.hidden_projects)
146        .fetch_all(pool)
147        .await?;
148    let mut found: Vec<Duplicate> = rows
149        .into_iter()
150        .filter_map(|c| {
151            let score = similarity(name, &c.name);
152            (score >= THRESHOLD).then(|| Duplicate {
153                item_id: c.item_id,
154                number: c.number,
155                item_type: c.item_type,
156                project_code: c.project_code,
157                revision_id: c.revision_id,
158                code: c.code,
159                state: c.state,
160                name: c.name,
161                score: (score * 100.0).round() / 100.0,
162            })
163        })
164        .collect();
165    found.sort_by(|a, b| {
166        b.score
167            .partial_cmp(&a.score)
168            .unwrap_or(std::cmp::Ordering::Equal)
169            .then_with(|| a.number.cmp(&b.number))
170    });
171    found.truncate(limit);
172    Ok(found)
173}
174
175#[cfg(test)]
176mod tests {
177    use super::*;
178
179    #[test]
180    fn words_are_lower_case_and_unique() {
181        assert_eq!(
182            words("Bracket, M8 – left bracket"),
183            ["bracket", "m8", "left"]
184        );
185        assert!(words("a - b").is_empty());
186        assert_eq!(words("Lagerbock Ø20"), ["lagerbock", "ø20"]);
187    }
188
189    #[test]
190    fn similar_names() {
191        assert_eq!(similarity("Bracket left", "bracket LEFT"), 1.0);
192        assert_eq!(similarity("M8 bracket left", "Bracket left M8"), 1.0);
193        assert!(similarity("Bracket", "Brakcet") >= THRESHOLD, "typo");
194        assert!(similarity("Motor mount plate", "Motor mount plate v2") >= THRESHOLD);
195        assert!(similarity("Bracket", "Gearbox housing") < THRESHOLD);
196        assert!(similarity("Shaft", "Shaft collar clamp large") < THRESHOLD);
197        assert_eq!(similarity("", ""), 0.0);
198        assert_eq!(edit_distance(&['a', 'b'], &[]), 2);
199    }
200}
teamcraft/services/duplicates.rs

teamcraft/services/
duplicates.rs
