ryo_analysis/query/
borrow_v2.rs

1//! BorrowTrackerV2 - VarId-based borrow tracking for DataFlowGraphV2.
2//!
3//! Key improvements over V1:
4//! - Uses VarId instead of petgraph::NodeIndex
5//! - Integrates seamlessly with DataFlowGraphV2
6//! - Same borrow conflict detection semantics
7
8use super::var_id::VarId;
9use smallvec::SmallVec;
10use std::collections::HashMap;
11use std::fmt;
12
13// ============================================================================
14// Borrow Kind (shared vocabulary)
15// ============================================================================
16
17/// Kind of borrow.
18#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
19pub enum BorrowKind {
20    /// Shared/immutable borrow (&T).
21    Shared,
22    /// Mutable borrow (&mut T).
23    Mutable,
24}
25
26impl BorrowKind {
27    /// Check if this borrow conflicts with another.
28    ///
29    /// Mutable borrows conflict with everything.
30    /// Shared borrows only conflict with mutable borrows.
31    pub fn conflicts_with(&self, other: BorrowKind) -> bool {
32        matches!(
33            (self, other),
34            (BorrowKind::Mutable, _) | (_, BorrowKind::Mutable)
35        )
36    }
37}
38
39// ============================================================================
40// Borrow State V2
41// ============================================================================
42
43/// The ownership/borrow state of a variable (V2 - uses VarId).
44#[derive(Debug, Clone, PartialEq, Eq, Default)]
45pub enum BorrowStateV2 {
46    /// Variable owns its value (T).
47    #[default]
48    Owned,
49
50    /// Variable is a shared reference (&T).
51    SharedRef {
52        /// The variable being borrowed from.
53        source: VarId,
54        /// Line where the borrow started.
55        start_line: u32,
56    },
57
58    /// Variable is a mutable reference (&mut T).
59    MutRef {
60        /// The variable being borrowed from.
61        source: VarId,
62        /// Line where the borrow started.
63        start_line: u32,
64    },
65
66    /// Ownership has been moved to another variable.
67    Moved {
68        /// The variable that now owns the value.
69        to: VarId,
70        /// Line where the move occurred.
71        at_line: u32,
72    },
73
74    /// Variable has been dropped (out of scope).
75    Dropped {
76        /// Line where the drop occurred.
77        at_line: u32,
78    },
79
80    /// Copy semantics - value was copied, original still valid.
81    Copied {
82        /// The variable that received the copy.
83        to: VarId,
84        /// Line where the copy occurred.
85        at_line: u32,
86    },
87}
88
89impl BorrowStateV2 {
90    /// Check if the variable can be used (read).
91    pub fn can_read(&self) -> bool {
92        matches!(
93            self,
94            BorrowStateV2::Owned
95                | BorrowStateV2::SharedRef { .. }
96                | BorrowStateV2::MutRef { .. }
97                | BorrowStateV2::Copied { .. }
98        )
99    }
100
101    /// Check if the variable can be mutated.
102    pub fn can_mutate(&self) -> bool {
103        matches!(self, BorrowStateV2::Owned | BorrowStateV2::MutRef { .. })
104    }
105
106    /// Check if the variable has been invalidated (moved or dropped).
107    pub fn is_invalidated(&self) -> bool {
108        matches!(
109            self,
110            BorrowStateV2::Moved { .. } | BorrowStateV2::Dropped { .. }
111        )
112    }
113
114    /// Check if this is a reference (shared or mutable).
115    pub fn is_reference(&self) -> bool {
116        matches!(
117            self,
118            BorrowStateV2::SharedRef { .. } | BorrowStateV2::MutRef { .. }
119        )
120    }
121
122    /// Get the source variable if this is a reference.
123    pub fn borrow_source(&self) -> Option<VarId> {
124        match self {
125            BorrowStateV2::SharedRef { source, .. } | BorrowStateV2::MutRef { source, .. } => {
126                Some(*source)
127            }
128            _ => None,
129        }
130    }
131}
132
133// ============================================================================
134// Active Borrow V2
135// ============================================================================
136
137/// Represents an active borrow of a variable (V2 - uses VarId).
138#[derive(Debug, Clone, PartialEq, Eq)]
139pub struct ActiveBorrowV2 {
140    /// The variable that holds the borrow (the reference variable).
141    pub borrower: VarId,
142    /// The kind of borrow.
143    pub kind: BorrowKind,
144    /// Line where the borrow started.
145    pub start_line: u32,
146    /// Line where the borrow ended (None = still active).
147    pub end_line: Option<u32>,
148}
149
150impl ActiveBorrowV2 {
151    /// Create a new active borrow.
152    pub fn new(borrower: VarId, kind: BorrowKind, start_line: u32) -> Self {
153        Self {
154            borrower,
155            kind,
156            start_line,
157            end_line: None,
158        }
159    }
160
161    /// Check if this borrow is still active at the given line.
162    pub fn is_active_at(&self, line: u32) -> bool {
163        line >= self.start_line && self.end_line.is_none_or(|end| line < end)
164    }
165
166    /// End this borrow at the given line.
167    pub fn end_at(&mut self, line: u32) {
168        self.end_line = Some(line);
169    }
170
171    /// Check if this borrow conflicts with a new borrow.
172    pub fn conflicts_with(&self, new_kind: BorrowKind, at_line: u32) -> bool {
173        self.is_active_at(at_line) && self.kind.conflicts_with(new_kind)
174    }
175}
176
177// ============================================================================
178// Borrow Conflict
179// ============================================================================
180
181/// A detected borrow conflict.
182#[derive(Debug, Clone, PartialEq, Eq)]
183pub struct BorrowConflict {
184    /// The variable being borrowed.
185    pub variable: VarId,
186    /// The existing borrow that conflicts.
187    pub existing: ActiveBorrowV2,
188    /// The new borrow kind that was attempted.
189    pub new_kind: BorrowKind,
190    /// Line where the new borrow was attempted.
191    pub new_line: u32,
192}
193
194impl BorrowConflict {
195    /// Create a new borrow conflict.
196    pub fn new(
197        variable: VarId,
198        existing: ActiveBorrowV2,
199        new_kind: BorrowKind,
200        new_line: u32,
201    ) -> Self {
202        Self {
203            variable,
204            existing,
205            new_kind,
206            new_line,
207        }
208    }
209}
210
211impl fmt::Display for BorrowConflict {
212    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
213        let existing_kind = match self.existing.kind {
214            BorrowKind::Shared => "shared",
215            BorrowKind::Mutable => "mutable",
216        };
217        let new_kind = match self.new_kind {
218            BorrowKind::Shared => "shared",
219            BorrowKind::Mutable => "mutable",
220        };
221
222        if self.existing.kind == BorrowKind::Mutable && self.new_kind == BorrowKind::Mutable {
223            write!(
224                f,
225                "cannot borrow as mutable more than once: \
226                 first borrow at line {}, second borrow at line {}",
227                self.existing.start_line, self.new_line
228            )
229        } else {
230            write!(
231                f,
232                "cannot borrow as {} because already borrowed as {}: \
233                 existing borrow at line {}, new borrow at line {}",
234                new_kind, existing_kind, self.existing.start_line, self.new_line
235            )
236        }
237    }
238}
239
240// ============================================================================
241// Move Error
242// ============================================================================
243
244/// A use-after-move error.
245#[derive(Debug, Clone, PartialEq, Eq)]
246pub struct MoveError {
247    /// The variable that was moved.
248    pub variable: VarId,
249    /// Line where the move occurred.
250    pub moved_at: u32,
251    /// Line where the invalid use occurred.
252    pub used_at: u32,
253}
254
255impl fmt::Display for MoveError {
256    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
257        write!(
258            f,
259            "use of moved value: moved at line {}, used at line {}",
260            self.moved_at, self.used_at
261        )
262    }
263}
264
265// ============================================================================
266// Borrow Analysis Result
267// ============================================================================
268
269/// Result of borrow analysis for a symbol.
270#[derive(Debug, Clone)]
271pub struct BorrowAnalysis {
272    /// Borrow conflicts found.
273    pub conflicts: Vec<BorrowConflict>,
274    /// Use-after-move errors found.
275    pub move_errors: Vec<MoveError>,
276}
277
278impl BorrowAnalysis {
279    /// Check if there are any issues.
280    pub fn has_issues(&self) -> bool {
281        !self.conflicts.is_empty() || !self.move_errors.is_empty()
282    }
283
284    /// Get total issue count.
285    pub fn issue_count(&self) -> usize {
286        self.conflicts.len() + self.move_errors.len()
287    }
288}
289
290// ============================================================================
291// Borrow Tracker V2
292// ============================================================================
293
294/// Tracks active borrows for a set of variables (V2 - uses VarId).
295///
296/// Integrates with DataFlowGraphV2 for borrow conflict detection.
297#[derive(Debug, Clone, Default)]
298pub struct BorrowTrackerV2 {
299    /// Active borrows indexed by the borrowed variable.
300    /// Uses SmallVec since most variables have 0-2 borrows.
301    borrows: HashMap<VarId, SmallVec<[ActiveBorrowV2; 2]>>,
302}
303
304impl BorrowTrackerV2 {
305    /// Create a new empty tracker.
306    pub fn new() -> Self {
307        Self::default()
308    }
309
310    /// Create with pre-allocated capacity.
311    pub fn with_capacity(capacity: usize) -> Self {
312        Self {
313            borrows: HashMap::with_capacity(capacity),
314        }
315    }
316
317    /// Add a borrow.
318    ///
319    /// Returns any conflicts with existing borrows.
320    pub fn add_borrow(
321        &mut self,
322        source: VarId,
323        borrower: VarId,
324        kind: BorrowKind,
325        line: u32,
326    ) -> Vec<BorrowConflict> {
327        let conflicts = self.conflicts(source, kind, line);
328
329        self.borrows
330            .entry(source)
331            .or_default()
332            .push(ActiveBorrowV2::new(borrower, kind, line));
333
334        conflicts
335    }
336
337    /// End a borrow.
338    pub fn end_borrow(&mut self, borrower: VarId, line: u32) {
339        for borrows in self.borrows.values_mut() {
340            for borrow in borrows.iter_mut() {
341                if borrow.borrower == borrower && borrow.end_line.is_none() {
342                    borrow.end_at(line);
343                }
344            }
345        }
346    }
347
348    /// Query conflicts with a potential new borrow.
349    pub fn conflicts(&self, source: VarId, kind: BorrowKind, at_line: u32) -> Vec<BorrowConflict> {
350        self.borrows
351            .get(&source)
352            .map(|borrows| {
353                borrows
354                    .iter()
355                    .filter(|b| b.conflicts_with(kind, at_line))
356                    .map(|b| BorrowConflict::new(source, b.clone(), kind, at_line))
357                    .collect()
358            })
359            .unwrap_or_default()
360    }
361
362    /// Get all active borrows of a variable at a given line.
363    pub fn active_borrows_at(&self, source: VarId, line: u32) -> Vec<&ActiveBorrowV2> {
364        self.borrows
365            .get(&source)
366            .map(|borrows| borrows.iter().filter(|b| b.is_active_at(line)).collect())
367            .unwrap_or_default()
368    }
369
370    /// Get all active borrows of a variable (regardless of line).
371    pub fn active_borrows(&self, source: VarId) -> &[ActiveBorrowV2] {
372        self.borrows
373            .get(&source)
374            .map(|v| v.as_slice())
375            .unwrap_or(&[])
376    }
377
378    /// Clear all borrows.
379    pub fn clear(&mut self) {
380        self.borrows.clear();
381    }
382
383    /// Check if any borrows are currently active for a variable.
384    pub fn has_active_borrows(&self, source: VarId, at_line: u32) -> bool {
385        self.borrows
386            .get(&source)
387            .map(|borrows| borrows.iter().any(|b| b.is_active_at(at_line)))
388            .unwrap_or(false)
389    }
390
391    /// Check if a mutable borrow is active for a variable.
392    pub fn has_active_mut_borrow(&self, source: VarId, at_line: u32) -> bool {
393        self.borrows
394            .get(&source)
395            .map(|borrows| {
396                borrows
397                    .iter()
398                    .any(|b| b.is_active_at(at_line) && b.kind == BorrowKind::Mutable)
399            })
400            .unwrap_or(false)
401    }
402
403    /// Get the number of tracked variables.
404    pub fn tracked_var_count(&self) -> usize {
405        self.borrows.len()
406    }
407
408    /// Get the total number of borrows (active and ended).
409    pub fn total_borrow_count(&self) -> usize {
410        self.borrows.values().map(|v| v.len()).sum()
411    }
412}
413
414#[cfg(test)]
415mod tests {
416    use super::*;
417    use crate::symbol::SymbolId;
418    use slotmap::SlotMap;
419
420    /// Test helper to create VarIds from a shared mapping.
421    struct TestVars {
422        symbols: SlotMap<SymbolId, &'static str>,
423        mapping: super::super::var_id::VarSymbolMapping,
424    }
425
426    impl TestVars {
427        fn new() -> Self {
428            Self {
429                symbols: SlotMap::with_key(),
430                mapping: super::super::var_id::VarSymbolMapping::new(),
431            }
432        }
433
434        fn var(&mut self, name: &'static str) -> VarId {
435            let sym = self.symbols.insert(name);
436            self.mapping.register(sym)
437        }
438    }
439
440    #[test]
441    fn test_borrow_state_can_read() {
442        let mut vars = TestVars::new();
443        let v = vars.var("v");
444
445        assert!(BorrowStateV2::Owned.can_read());
446        assert!(BorrowStateV2::SharedRef {
447            source: v,
448            start_line: 1
449        }
450        .can_read());
451        assert!(BorrowStateV2::MutRef {
452            source: v,
453            start_line: 1
454        }
455        .can_read());
456        assert!(!BorrowStateV2::Moved { to: v, at_line: 1 }.can_read());
457        assert!(!BorrowStateV2::Dropped { at_line: 1 }.can_read());
458    }
459
460    #[test]
461    fn test_borrow_state_can_mutate() {
462        let mut vars = TestVars::new();
463        let v = vars.var("v");
464
465        assert!(BorrowStateV2::Owned.can_mutate());
466        assert!(BorrowStateV2::MutRef {
467            source: v,
468            start_line: 1
469        }
470        .can_mutate());
471        assert!(!BorrowStateV2::SharedRef {
472            source: v,
473            start_line: 1
474        }
475        .can_mutate());
476        assert!(!BorrowStateV2::Moved { to: v, at_line: 1 }.can_mutate());
477    }
478
479    #[test]
480    fn test_active_borrow_is_active_at() {
481        let mut vars = TestVars::new();
482        let borrower = vars.var("borrower");
483        let mut borrow = ActiveBorrowV2::new(borrower, BorrowKind::Shared, 10);
484
485        assert!(borrow.is_active_at(10));
486        assert!(borrow.is_active_at(15));
487        assert!(borrow.is_active_at(100));
488        assert!(!borrow.is_active_at(5));
489
490        borrow.end_at(20);
491        assert!(borrow.is_active_at(10));
492        assert!(borrow.is_active_at(15));
493        assert!(!borrow.is_active_at(20));
494        assert!(!borrow.is_active_at(25));
495    }
496
497    #[test]
498    fn test_borrow_tracker_no_conflict_shared() {
499        let mut tracker = BorrowTrackerV2::new();
500        let mut vars = TestVars::new();
501        let source = vars.var("source");
502        let b1 = vars.var("b1");
503        let b2 = vars.var("b2");
504
505        // Multiple shared borrows should not conflict
506        let conflicts = tracker.add_borrow(source, b1, BorrowKind::Shared, 10);
507        assert!(conflicts.is_empty());
508
509        let conflicts = tracker.add_borrow(source, b2, BorrowKind::Shared, 15);
510        assert!(conflicts.is_empty());
511    }
512
513    #[test]
514    fn test_borrow_tracker_conflict_mut_mut() {
515        let mut tracker = BorrowTrackerV2::new();
516        let mut vars = TestVars::new();
517        let source = vars.var("source");
518        let b1 = vars.var("b1");
519        let b2 = vars.var("b2");
520
521        let conflicts = tracker.add_borrow(source, b1, BorrowKind::Mutable, 10);
522        assert!(conflicts.is_empty());
523
524        // Second mutable borrow should conflict
525        let conflicts = tracker.add_borrow(source, b2, BorrowKind::Mutable, 15);
526        assert_eq!(conflicts.len(), 1);
527        assert_eq!(conflicts[0].existing.borrower, b1);
528        assert_eq!(conflicts[0].new_kind, BorrowKind::Mutable);
529    }
530
531    #[test]
532    fn test_borrow_tracker_conflict_shared_then_mut() {
533        let mut tracker = BorrowTrackerV2::new();
534        let mut vars = TestVars::new();
535        let source = vars.var("source");
536        let b1 = vars.var("b1");
537        let b2 = vars.var("b2");
538
539        let conflicts = tracker.add_borrow(source, b1, BorrowKind::Shared, 10);
540        assert!(conflicts.is_empty());
541
542        // Mutable borrow while shared borrow is active should conflict
543        let conflicts = tracker.add_borrow(source, b2, BorrowKind::Mutable, 15);
544        assert_eq!(conflicts.len(), 1);
545    }
546
547    #[test]
548    fn test_borrow_tracker_end_borrow() {
549        let mut tracker = BorrowTrackerV2::new();
550        let mut vars = TestVars::new();
551        let source = vars.var("source");
552        let borrower = vars.var("borrower");
553        let b2 = vars.var("b2");
554
555        tracker.add_borrow(source, borrower, BorrowKind::Mutable, 10);
556        tracker.end_borrow(borrower, 20);
557
558        // After ending the borrow, new mutable borrow should not conflict
559        let conflicts = tracker.add_borrow(source, b2, BorrowKind::Mutable, 25);
560        assert!(conflicts.is_empty());
561    }
562
563    #[test]
564    fn test_borrow_tracker_has_active_borrows() {
565        let mut tracker = BorrowTrackerV2::new();
566        let mut vars = TestVars::new();
567        let source = vars.var("source");
568        let borrower = vars.var("borrower");
569
570        assert!(!tracker.has_active_borrows(source, 10));
571
572        tracker.add_borrow(source, borrower, BorrowKind::Shared, 10);
573        assert!(tracker.has_active_borrows(source, 15));
574
575        tracker.end_borrow(borrower, 20);
576        assert!(!tracker.has_active_borrows(source, 25));
577    }
578
579    #[test]
580    fn test_borrow_tracker_stats() {
581        let mut tracker = BorrowTrackerV2::new();
582        let mut vars = TestVars::new();
583        let s1 = vars.var("s1");
584        let s2 = vars.var("s2");
585        let b1 = vars.var("b1");
586        let b2 = vars.var("b2");
587        let b3 = vars.var("b3");
588
589        tracker.add_borrow(s1, b1, BorrowKind::Shared, 10);
590        tracker.add_borrow(s1, b2, BorrowKind::Shared, 15);
591        tracker.add_borrow(s2, b3, BorrowKind::Mutable, 20);
592
593        assert_eq!(tracker.tracked_var_count(), 2);
594        assert_eq!(tracker.total_borrow_count(), 3);
595    }
596}
ryo_analysis/query/borrow_v2.rs

ryo_analysis/query/
borrow_v2.rs
