resolvo 0.11.1

Fast package resolver written in Rust (CDCL based SAT solving)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140

use std::{
    fmt::{Display, Formatter},
    num::NonZeroU32,
};

use crate::{DenseIndex, Interner, internal::solver_id::SolvableIdOrRoot};

#[repr(transparent)]
#[derive(Copy, Clone, PartialOrd, Ord, Eq, PartialEq, Debug, Hash)]
pub(crate) struct ClauseId(NonZeroU32);

impl ClauseId {
    /// There is a guarentee that ClauseId(1) will always be
    /// "Clause::InstallRoot". This assumption is verified by the solver.
    pub(crate) fn install_root() -> Self {
        Self(unsafe { NonZeroU32::new_unchecked(1) })
    }
}

impl DenseIndex for ClauseId {
    fn from_index(x: usize) -> Self {
        // SAFETY: Safe because we always add 1 to the index
        Self(unsafe { NonZeroU32::new_unchecked((x + 1).try_into().expect("clause id too big")) })
    }

    fn to_index(self) -> usize {
        (self.0.get() - 1) as usize
    }
}

#[derive(Copy, Clone, Debug)]
pub(crate) struct LearntClauseId(u32);

impl DenseIndex for LearntClauseId {
    fn from_index(x: usize) -> Self {
        Self(x as u32)
    }

    fn to_index(self) -> usize {
        self.0 as usize
    }
}

/// The id associated to an arena of Candidates
#[repr(transparent)]
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub(crate) struct CandidatesId(u32);

impl DenseIndex for CandidatesId {
    fn from_index(x: usize) -> Self {
        Self(x as u32)
    }

    fn to_index(self) -> usize {
        self.0 as usize
    }
}

/// The id associated to an arena of PackageRequirements
#[repr(transparent)]
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub(crate) struct DependenciesId(NonZeroU32);

impl DenseIndex for DependenciesId {
    fn from_index(x: usize) -> Self {
        let raw: u32 = (x + 1).try_into().expect("dependencies id too big");
        // SAFETY: `raw` is `x + 1`, hence at least 1, hence non-zero.
        Self(unsafe { NonZeroU32::new_unchecked(raw) })
    }

    fn to_index(self) -> usize {
        (self.0.get() - 1) as usize
    }
}

impl<S> SolvableIdOrRoot<S> {
    /// Returns an object that can be used to format the solvable or root id.
    pub fn display<I: Interner<SolvableId = S>>(self, interner: &I) -> impl Display + '_ {
        DisplaySolvableIdOrRoot {
            interner,
            solvable_id: self,
        }
    }
}

pub(crate) struct DisplaySolvableIdOrRoot<'i, I: Interner> {
    interner: &'i I,
    solvable_id: SolvableIdOrRoot<I::SolvableId>,
}

impl<I: Interner> Display for DisplaySolvableIdOrRoot<'_, I> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        match self.solvable_id.solvable() {
            Some(solvable_id) => write!(f, "{}", self.interner.display_solvable(solvable_id)),
            None => write!(f, "root"),
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::VariableId;

    #[test]
    fn test_clause_id_size() {
        // Verify that the size of a ClauseId is the same as an Option<ClauseId>.
        assert_eq!(
            std::mem::size_of::<ClauseId>(),
            std::mem::size_of::<Option<ClauseId>>()
        );
    }

    #[test]
    fn test_variable_id_niche() {
        assert_eq!(std::mem::size_of::<VariableId>(), 4);
        assert_eq!(
            std::mem::size_of::<VariableId>(),
            std::mem::size_of::<Option<VariableId>>()
        );
    }

    #[test]
    fn test_dependencies_id_niche() {
        assert_eq!(std::mem::size_of::<DependenciesId>(), 4);
        assert_eq!(
            std::mem::size_of::<DependenciesId>(),
            std::mem::size_of::<Option<DependenciesId>>()
        );
    }

    #[test]
    fn test_variable_id_root_roundtrip() {
        assert!(VariableId::root().is_root());
        assert_eq!(VariableId::root().to_index(), 0);
        assert_eq!(VariableId::from_index(0), VariableId::root());
        assert!(!VariableId::from_index(1).is_root());
        assert_eq!(VariableId::from_index(7).to_index(), 7);
    }
}