Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

5 files changed, 942 insertions, 0 deletions

diff --git a/src/tools/rust-analyzer/crates/cfg/Cargo.toml b/src/tools/rust-analyzer/crates/cfg/Cargo.toml
new file mode 100644
index 000000000..c9664a83a
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/cfg/Cargo.toml
@@ -0,0 +1,26 @@
+[package]
+name = "cfg"
+version = "0.0.0"
+description = "TBD"
+license = "MIT OR Apache-2.0"
+edition = "2021"
+rust-version = "1.57"
+
+[lib]
+doctest = false
+
+[dependencies]
+rustc-hash = "1.1.0"
+
+tt = { path = "../tt", version = "0.0.0" }
+
+[dev-dependencies]
+mbe = { path = "../mbe" }
+syntax = { path = "../syntax" }
+expect-test = "1.4.0"
+oorandom = "11.1.3"
+# We depend on both individually instead of using `features = ["derive"]` to microoptimize the
+# build graph: if the feature was enabled, syn would be built early on in the graph if `smolstr`
+# supports `arbitrary`. This way, we avoid feature unification.
+arbitrary = "1.1.0"
+derive_arbitrary = "1.1.0"
diff --git a/src/tools/rust-analyzer/crates/cfg/src/cfg_expr.rs b/src/tools/rust-analyzer/crates/cfg/src/cfg_expr.rs
new file mode 100644
index 000000000..fd9e31ed3
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/cfg/src/cfg_expr.rs
@@ -0,0 +1,145 @@
+//! The condition expression used in `#[cfg(..)]` attributes.
+//!
+//! See: <https://doc.rust-lang.org/reference/conditional-compilation.html#conditional-compilation>
+
+use std::{fmt, slice::Iter as SliceIter};
+
+use tt::SmolStr;
+
+/// A simple configuration value passed in from the outside.
+#[derive(Debug, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
+pub enum CfgAtom {
+    /// eg. `#[cfg(test)]`
+    Flag(SmolStr),
+    /// eg. `#[cfg(target_os = "linux")]`
+    ///
+    /// Note that a key can have multiple values that are all considered "active" at the same time.
+    /// For example, `#[cfg(target_feature = "sse")]` and `#[cfg(target_feature = "sse2")]`.
+    KeyValue { key: SmolStr, value: SmolStr },
+}
+
+impl CfgAtom {
+    /// Returns `true` when the atom comes from the target specification.
+    ///
+    /// If this returns `true`, then changing this atom requires changing the compilation target. If
+    /// it returns `false`, the atom might come from a build script or the build system.
+    pub fn is_target_defined(&self) -> bool {
+        match self {
+            CfgAtom::Flag(flag) => matches!(&**flag, "unix" | "windows"),
+            CfgAtom::KeyValue { key, value: _ } => matches!(
+                &**key,
+                "target_arch"
+                    | "target_os"
+                    | "target_env"
+                    | "target_family"
+                    | "target_endian"
+                    | "target_pointer_width"
+                    | "target_vendor" // NOTE: `target_feature` is left out since it can be configured via `-Ctarget-feature`
+            ),
+        }
+    }
+}
+
+impl fmt::Display for CfgAtom {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            CfgAtom::Flag(name) => name.fmt(f),
+            CfgAtom::KeyValue { key, value } => write!(f, "{} = {:?}", key, value),
+        }
+    }
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+#[cfg_attr(test, derive(derive_arbitrary::Arbitrary))]
+pub enum CfgExpr {
+    Invalid,
+    Atom(CfgAtom),
+    All(Vec<CfgExpr>),
+    Any(Vec<CfgExpr>),
+    Not(Box<CfgExpr>),
+}
+
+impl From<CfgAtom> for CfgExpr {
+    fn from(atom: CfgAtom) -> Self {
+        CfgExpr::Atom(atom)
+    }
+}
+
+impl CfgExpr {
+    pub fn parse(tt: &tt::Subtree) -> CfgExpr {
+        next_cfg_expr(&mut tt.token_trees.iter()).unwrap_or(CfgExpr::Invalid)
+    }
+    /// Fold the cfg by querying all basic `Atom` and `KeyValue` predicates.
+    pub fn fold(&self, query: &dyn Fn(&CfgAtom) -> bool) -> Option<bool> {
+        match self {
+            CfgExpr::Invalid => None,
+            CfgExpr::Atom(atom) => Some(query(atom)),
+            CfgExpr::All(preds) => {
+                preds.iter().try_fold(true, |s, pred| Some(s && pred.fold(query)?))
+            }
+            CfgExpr::Any(preds) => {
+                preds.iter().try_fold(false, |s, pred| Some(s || pred.fold(query)?))
+            }
+            CfgExpr::Not(pred) => pred.fold(query).map(|s| !s),
+        }
+    }
+}
+
+fn next_cfg_expr(it: &mut SliceIter<'_, tt::TokenTree>) -> Option<CfgExpr> {
+    let name = match it.next() {
+        None => return None,
+        Some(tt::TokenTree::Leaf(tt::Leaf::Ident(ident))) => ident.text.clone(),
+        Some(_) => return Some(CfgExpr::Invalid),
+    };
+
+    // Peek
+    let ret = match it.as_slice().first() {
+        Some(tt::TokenTree::Leaf(tt::Leaf::Punct(punct))) if punct.char == '=' => {
+            match it.as_slice().get(1) {
+                Some(tt::TokenTree::Leaf(tt::Leaf::Literal(literal))) => {
+                    it.next();
+                    it.next();
+                    // FIXME: escape? raw string?
+                    let value =
+                        SmolStr::new(literal.text.trim_start_matches('"').trim_end_matches('"'));
+                    CfgAtom::KeyValue { key: name, value }.into()
+                }
+                _ => return Some(CfgExpr::Invalid),
+            }
+        }
+        Some(tt::TokenTree::Subtree(subtree)) => {
+            it.next();
+            let mut sub_it = subtree.token_trees.iter();
+            let mut subs = std::iter::from_fn(|| next_cfg_expr(&mut sub_it)).collect();
+            match name.as_str() {
+                "all" => CfgExpr::All(subs),
+                "any" => CfgExpr::Any(subs),
+                "not" => CfgExpr::Not(Box::new(subs.pop().unwrap_or(CfgExpr::Invalid))),
+                _ => CfgExpr::Invalid,
+            }
+        }
+        _ => CfgAtom::Flag(name).into(),
+    };
+
+    // Eat comma separator
+    if let Some(tt::TokenTree::Leaf(tt::Leaf::Punct(punct))) = it.as_slice().first() {
+        if punct.char == ',' {
+            it.next();
+        }
+    }
+    Some(ret)
+}
+
+#[cfg(test)]
+impl arbitrary::Arbitrary<'_> for CfgAtom {
+    fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
+        if u.arbitrary()? {
+            Ok(CfgAtom::Flag(String::arbitrary(u)?.into()))
+        } else {
+            Ok(CfgAtom::KeyValue {
+                key: String::arbitrary(u)?.into(),
+                value: String::arbitrary(u)?.into(),
+            })
+        }
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/cfg/src/dnf.rs b/src/tools/rust-analyzer/crates/cfg/src/dnf.rs
new file mode 100644
index 000000000..fd80e1ebe
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/cfg/src/dnf.rs
@@ -0,0 +1,345 @@
+//! Disjunctive Normal Form construction.
+//!
+//! Algorithm from <https://www.cs.drexel.edu/~jjohnson/2015-16/fall/CS270/Lectures/3/dnf.pdf>,
+//! which would have been much easier to read if it used pattern matching. It's also missing the
+//! entire "distribute ANDs over ORs" part, which is not trivial. Oh well.
+//!
+//! This is currently both messy and inefficient. Feel free to improve, there are unit tests.
+
+use std::fmt::{self, Write};
+
+use rustc_hash::FxHashSet;
+
+use crate::{CfgAtom, CfgDiff, CfgExpr, CfgOptions, InactiveReason};
+
+/// A `#[cfg]` directive in Disjunctive Normal Form (DNF).
+pub struct DnfExpr {
+    conjunctions: Vec<Conjunction>,
+}
+
+struct Conjunction {
+    literals: Vec<Literal>,
+}
+
+struct Literal {
+    negate: bool,
+    var: Option<CfgAtom>, // None = Invalid
+}
+
+impl DnfExpr {
+    pub fn new(expr: CfgExpr) -> Self {
+        let builder = Builder { expr: DnfExpr { conjunctions: Vec::new() } };
+
+        builder.lower(expr)
+    }
+
+    /// Computes a list of present or absent atoms in `opts` that cause this expression to evaluate
+    /// to `false`.
+    ///
+    /// Note that flipping a subset of these atoms might be sufficient to make the whole expression
+    /// evaluate to `true`. For that, see `compute_enable_hints`.
+    ///
+    /// Returns `None` when `self` is already true, or contains errors.
+    pub fn why_inactive(&self, opts: &CfgOptions) -> Option<InactiveReason> {
+        let mut res = InactiveReason { enabled: Vec::new(), disabled: Vec::new() };
+
+        for conj in &self.conjunctions {
+            let mut conj_is_true = true;
+            for lit in &conj.literals {
+                let atom = lit.var.as_ref()?;
+                let enabled = opts.enabled.contains(atom);
+                if lit.negate == enabled {
+                    // Literal is false, but needs to be true for this conjunction.
+                    conj_is_true = false;
+
+                    if enabled {
+                        res.enabled.push(atom.clone());
+                    } else {
+                        res.disabled.push(atom.clone());
+                    }
+                }
+            }
+
+            if conj_is_true {
+                // This expression is not actually inactive.
+                return None;
+            }
+        }
+
+        res.enabled.sort_unstable();
+        res.enabled.dedup();
+        res.disabled.sort_unstable();
+        res.disabled.dedup();
+        Some(res)
+    }
+
+    /// Returns `CfgDiff` objects that would enable this directive if applied to `opts`.
+    pub fn compute_enable_hints<'a>(
+        &'a self,
+        opts: &'a CfgOptions,
+    ) -> impl Iterator<Item = CfgDiff> + 'a {
+        // A cfg is enabled if any of `self.conjunctions` evaluate to `true`.
+
+        self.conjunctions.iter().filter_map(move |conj| {
+            let mut enable = FxHashSet::default();
+            let mut disable = FxHashSet::default();
+            for lit in &conj.literals {
+                let atom = lit.var.as_ref()?;
+                let enabled = opts.enabled.contains(atom);
+                if lit.negate && enabled {
+                    disable.insert(atom.clone());
+                }
+                if !lit.negate && !enabled {
+                    enable.insert(atom.clone());
+                }
+            }
+
+            // Check that this actually makes `conj` true.
+            for lit in &conj.literals {
+                let atom = lit.var.as_ref()?;
+                let enabled = enable.contains(atom)
+                    || (opts.enabled.contains(atom) && !disable.contains(atom));
+                if enabled == lit.negate {
+                    return None;
+                }
+            }
+
+            if enable.is_empty() && disable.is_empty() {
+                return None;
+            }
+
+            let mut diff = CfgDiff {
+                enable: enable.into_iter().collect(),
+                disable: disable.into_iter().collect(),
+            };
+
+            // Undo the FxHashMap randomization for consistent output.
+            diff.enable.sort_unstable();
+            diff.disable.sort_unstable();
+
+            Some(diff)
+        })
+    }
+}
+
+impl fmt::Display for DnfExpr {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if self.conjunctions.len() != 1 {
+            f.write_str("any(")?;
+        }
+        for (i, conj) in self.conjunctions.iter().enumerate() {
+            if i != 0 {
+                f.write_str(", ")?;
+            }
+
+            conj.fmt(f)?;
+        }
+        if self.conjunctions.len() != 1 {
+            f.write_char(')')?;
+        }
+
+        Ok(())
+    }
+}
+
+impl Conjunction {
+    fn new(parts: Vec<CfgExpr>) -> Self {
+        let mut literals = Vec::new();
+        for part in parts {
+            match part {
+                CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::Not(_) => {
+                    literals.push(Literal::new(part));
+                }
+                CfgExpr::All(conj) => {
+                    // Flatten.
+                    literals.extend(Conjunction::new(conj).literals);
+                }
+                CfgExpr::Any(_) => unreachable!("disjunction in conjunction"),
+            }
+        }
+
+        Self { literals }
+    }
+}
+
+impl fmt::Display for Conjunction {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if self.literals.len() != 1 {
+            f.write_str("all(")?;
+        }
+        for (i, lit) in self.literals.iter().enumerate() {
+            if i != 0 {
+                f.write_str(", ")?;
+            }
+
+            lit.fmt(f)?;
+        }
+        if self.literals.len() != 1 {
+            f.write_str(")")?;
+        }
+
+        Ok(())
+    }
+}
+
+impl Literal {
+    fn new(expr: CfgExpr) -> Self {
+        match expr {
+            CfgExpr::Invalid => Self { negate: false, var: None },
+            CfgExpr::Atom(atom) => Self { negate: false, var: Some(atom) },
+            CfgExpr::Not(expr) => match *expr {
+                CfgExpr::Invalid => Self { negate: true, var: None },
+                CfgExpr::Atom(atom) => Self { negate: true, var: Some(atom) },
+                _ => unreachable!("non-atom {:?}", expr),
+            },
+            CfgExpr::Any(_) | CfgExpr::All(_) => unreachable!("non-literal {:?}", expr),
+        }
+    }
+}
+
+impl fmt::Display for Literal {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if self.negate {
+            write!(f, "not(")?;
+        }
+
+        match &self.var {
+            Some(var) => var.fmt(f)?,
+            None => f.write_str("<invalid>")?,
+        }
+
+        if self.negate {
+            f.write_char(')')?;
+        }
+
+        Ok(())
+    }
+}
+
+struct Builder {
+    expr: DnfExpr,
+}
+
+impl Builder {
+    fn lower(mut self, expr: CfgExpr) -> DnfExpr {
+        let expr = make_nnf(expr);
+        let expr = make_dnf(expr);
+
+        match expr {
+            CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::Not(_) => {
+                self.expr.conjunctions.push(Conjunction::new(vec![expr]));
+            }
+            CfgExpr::All(conj) => {
+                self.expr.conjunctions.push(Conjunction::new(conj));
+            }
+            CfgExpr::Any(mut disj) => {
+                disj.reverse();
+                while let Some(conj) = disj.pop() {
+                    match conj {
+                        CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::All(_) | CfgExpr::Not(_) => {
+                            self.expr.conjunctions.push(Conjunction::new(vec![conj]));
+                        }
+                        CfgExpr::Any(inner_disj) => {
+                            // Flatten.
+                            disj.extend(inner_disj.into_iter().rev());
+                        }
+                    }
+                }
+            }
+        }
+
+        self.expr
+    }
+}
+
+fn make_dnf(expr: CfgExpr) -> CfgExpr {
+    match expr {
+        CfgExpr::Invalid | CfgExpr::Atom(_) | CfgExpr::Not(_) => expr,
+        CfgExpr::Any(e) => flatten(CfgExpr::Any(e.into_iter().map(make_dnf).collect())),
+        CfgExpr::All(e) => {
+            let e = e.into_iter().map(make_dnf).collect::<Vec<_>>();
+
+            flatten(CfgExpr::Any(distribute_conj(&e)))
+        }
+    }
+}
+
+/// Turns a conjunction of expressions into a disjunction of expressions.
+fn distribute_conj(conj: &[CfgExpr]) -> Vec<CfgExpr> {
+    fn go(out: &mut Vec<CfgExpr>, with: &mut Vec<CfgExpr>, rest: &[CfgExpr]) {
+        match rest {
+            [head, tail @ ..] => match head {
+                CfgExpr::Any(disj) => {
+                    for part in disj {
+                        with.push(part.clone());
+                        go(out, with, tail);
+                        with.pop();
+                    }
+                }
+                _ => {
+                    with.push(head.clone());
+                    go(out, with, tail);
+                    with.pop();
+                }
+            },
+            _ => {
+                // Turn accumulated parts into a new conjunction.
+                out.push(CfgExpr::All(with.clone()));
+            }
+        }
+    }
+
+    let mut out = Vec::new(); // contains only `all()`
+    let mut with = Vec::new();
+
+    go(&mut out, &mut with, conj);
+
+    out
+}
+
+fn make_nnf(expr: CfgExpr) -> CfgExpr {
+    match expr {
+        CfgExpr::Invalid | CfgExpr::Atom(_) => expr,
+        CfgExpr::Any(expr) => CfgExpr::Any(expr.into_iter().map(make_nnf).collect()),
+        CfgExpr::All(expr) => CfgExpr::All(expr.into_iter().map(make_nnf).collect()),
+        CfgExpr::Not(operand) => match *operand {
+            CfgExpr::Invalid | CfgExpr::Atom(_) => CfgExpr::Not(operand.clone()), // Original negated expr
+            CfgExpr::Not(expr) => {
+                // Remove double negation.
+                make_nnf(*expr)
+            }
+            // Convert negated conjunction/disjunction using DeMorgan's Law.
+            CfgExpr::Any(inner) => CfgExpr::All(
+                inner.into_iter().map(|expr| make_nnf(CfgExpr::Not(Box::new(expr)))).collect(),
+            ),
+            CfgExpr::All(inner) => CfgExpr::Any(
+                inner.into_iter().map(|expr| make_nnf(CfgExpr::Not(Box::new(expr)))).collect(),
+            ),
+        },
+    }
+}
+
+/// Collapses nested `any()` and `all()` predicates.
+fn flatten(expr: CfgExpr) -> CfgExpr {
+    match expr {
+        CfgExpr::All(inner) => CfgExpr::All(
+            inner
+                .into_iter()
+                .flat_map(|e| match e {
+                    CfgExpr::All(inner) => inner,
+                    _ => vec![e],
+                })
+                .collect(),
+        ),
+        CfgExpr::Any(inner) => CfgExpr::Any(
+            inner
+                .into_iter()
+                .flat_map(|e| match e {
+                    CfgExpr::Any(inner) => inner,
+                    _ => vec![e],
+                })
+                .collect(),
+        ),
+        _ => expr,
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/cfg/src/lib.rs b/src/tools/rust-analyzer/crates/cfg/src/lib.rs
new file mode 100644
index 000000000..d78ef4fb1
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/cfg/src/lib.rs
@@ -0,0 +1,202 @@
+//! cfg defines conditional compiling options, `cfg` attribute parser and evaluator
+
+#![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)]
+
+mod cfg_expr;
+mod dnf;
+#[cfg(test)]
+mod tests;
+
+use std::fmt;
+
+use rustc_hash::FxHashSet;
+use tt::SmolStr;
+
+pub use cfg_expr::{CfgAtom, CfgExpr};
+pub use dnf::DnfExpr;
+
+/// Configuration options used for conditional compilation on items with `cfg` attributes.
+/// We have two kind of options in different namespaces: atomic options like `unix`, and
+/// key-value options like `target_arch="x86"`.
+///
+/// Note that for key-value options, one key can have multiple values (but not none).
+/// `feature` is an example. We have both `feature="foo"` and `feature="bar"` if features
+/// `foo` and `bar` are both enabled. And here, we store key-value options as a set of tuple
+/// of key and value in `key_values`.
+///
+/// See: <https://doc.rust-lang.org/reference/conditional-compilation.html#set-configuration-options>
+#[derive(Clone, PartialEq, Eq, Default)]
+pub struct CfgOptions {
+    enabled: FxHashSet<CfgAtom>,
+}
+
+impl fmt::Debug for CfgOptions {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        let mut items = self
+            .enabled
+            .iter()
+            .map(|atom| match atom {
+                CfgAtom::Flag(it) => it.to_string(),
+                CfgAtom::KeyValue { key, value } => format!("{}={}", key, value),
+            })
+            .collect::<Vec<_>>();
+        items.sort();
+        f.debug_tuple("CfgOptions").field(&items).finish()
+    }
+}
+
+impl CfgOptions {
+    pub fn check(&self, cfg: &CfgExpr) -> Option<bool> {
+        cfg.fold(&|atom| self.enabled.contains(atom))
+    }
+
+    pub fn insert_atom(&mut self, key: SmolStr) {
+        self.enabled.insert(CfgAtom::Flag(key));
+    }
+
+    pub fn insert_key_value(&mut self, key: SmolStr, value: SmolStr) {
+        self.enabled.insert(CfgAtom::KeyValue { key, value });
+    }
+
+    pub fn apply_diff(&mut self, diff: CfgDiff) {
+        for atom in diff.enable {
+            self.enabled.insert(atom);
+        }
+
+        for atom in diff.disable {
+            self.enabled.remove(&atom);
+        }
+    }
+
+    pub fn get_cfg_keys(&self) -> impl Iterator<Item = &SmolStr> {
+        self.enabled.iter().map(|x| match x {
+            CfgAtom::Flag(key) => key,
+            CfgAtom::KeyValue { key, .. } => key,
+        })
+    }
+
+    pub fn get_cfg_values<'a>(
+        &'a self,
+        cfg_key: &'a str,
+    ) -> impl Iterator<Item = &'a SmolStr> + 'a {
+        self.enabled.iter().filter_map(move |x| match x {
+            CfgAtom::KeyValue { key, value } if cfg_key == key => Some(value),
+            _ => None,
+        })
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct CfgDiff {
+    // Invariants: No duplicates, no atom that's both in `enable` and `disable`.
+    enable: Vec<CfgAtom>,
+    disable: Vec<CfgAtom>,
+}
+
+impl CfgDiff {
+    /// Create a new CfgDiff. Will return None if the same item appears more than once in the set
+    /// of both.
+    pub fn new(enable: Vec<CfgAtom>, disable: Vec<CfgAtom>) -> Option<CfgDiff> {
+        let mut occupied = FxHashSet::default();
+        for item in enable.iter().chain(disable.iter()) {
+            if !occupied.insert(item) {
+                // was present
+                return None;
+            }
+        }
+
+        Some(CfgDiff { enable, disable })
+    }
+
+    /// Returns the total number of atoms changed by this diff.
+    pub fn len(&self) -> usize {
+        self.enable.len() + self.disable.len()
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+}
+
+impl fmt::Display for CfgDiff {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if !self.enable.is_empty() {
+            f.write_str("enable ")?;
+            for (i, atom) in self.enable.iter().enumerate() {
+                let sep = match i {
+                    0 => "",
+                    _ if i == self.enable.len() - 1 => " and ",
+                    _ => ", ",
+                };
+                f.write_str(sep)?;
+
+                atom.fmt(f)?;
+            }
+
+            if !self.disable.is_empty() {
+                f.write_str("; ")?;
+            }
+        }
+
+        if !self.disable.is_empty() {
+            f.write_str("disable ")?;
+            for (i, atom) in self.disable.iter().enumerate() {
+                let sep = match i {
+                    0 => "",
+                    _ if i == self.enable.len() - 1 => " and ",
+                    _ => ", ",
+                };
+                f.write_str(sep)?;
+
+                atom.fmt(f)?;
+            }
+        }
+
+        Ok(())
+    }
+}
+
+pub struct InactiveReason {
+    enabled: Vec<CfgAtom>,
+    disabled: Vec<CfgAtom>,
+}
+
+impl fmt::Display for InactiveReason {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        if !self.enabled.is_empty() {
+            for (i, atom) in self.enabled.iter().enumerate() {
+                let sep = match i {
+                    0 => "",
+                    _ if i == self.enabled.len() - 1 => " and ",
+                    _ => ", ",
+                };
+                f.write_str(sep)?;
+
+                atom.fmt(f)?;
+            }
+            let is_are = if self.enabled.len() == 1 { "is" } else { "are" };
+            write!(f, " {} enabled", is_are)?;
+
+            if !self.disabled.is_empty() {
+                f.write_str(" and ")?;
+            }
+        }
+
+        if !self.disabled.is_empty() {
+            for (i, atom) in self.disabled.iter().enumerate() {
+                let sep = match i {
+                    0 => "",
+                    _ if i == self.disabled.len() - 1 => " and ",
+                    _ => ", ",
+                };
+                f.write_str(sep)?;
+
+                atom.fmt(f)?;
+            }
+            let is_are = if self.disabled.len() == 1 { "is" } else { "are" };
+            write!(f, " {} disabled", is_are)?;
+        }
+
+        Ok(())
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/cfg/src/tests.rs b/src/tools/rust-analyzer/crates/cfg/src/tests.rs
new file mode 100644
index 000000000..bdc3f854e
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/cfg/src/tests.rs
@@ -0,0 +1,224 @@
+use arbitrary::{Arbitrary, Unstructured};
+use expect_test::{expect, Expect};
+use mbe::syntax_node_to_token_tree;
+use syntax::{ast, AstNode};
+
+use crate::{CfgAtom, CfgExpr, CfgOptions, DnfExpr};
+
+fn assert_parse_result(input: &str, expected: CfgExpr) {
+    let (tt, _) = {
+        let source_file = ast::SourceFile::parse(input).ok().unwrap();
+        let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
+        syntax_node_to_token_tree(tt.syntax())
+    };
+    let cfg = CfgExpr::parse(&tt);
+    assert_eq!(cfg, expected);
+}
+
+fn check_dnf(input: &str, expect: Expect) {
+    let (tt, _) = {
+        let source_file = ast::SourceFile::parse(input).ok().unwrap();
+        let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
+        syntax_node_to_token_tree(tt.syntax())
+    };
+    let cfg = CfgExpr::parse(&tt);
+    let actual = format!("#![cfg({})]", DnfExpr::new(cfg));
+    expect.assert_eq(&actual);
+}
+
+fn check_why_inactive(input: &str, opts: &CfgOptions, expect: Expect) {
+    let (tt, _) = {
+        let source_file = ast::SourceFile::parse(input).ok().unwrap();
+        let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
+        syntax_node_to_token_tree(tt.syntax())
+    };
+    let cfg = CfgExpr::parse(&tt);
+    let dnf = DnfExpr::new(cfg);
+    let why_inactive = dnf.why_inactive(opts).unwrap().to_string();
+    expect.assert_eq(&why_inactive);
+}
+
+#[track_caller]
+fn check_enable_hints(input: &str, opts: &CfgOptions, expected_hints: &[&str]) {
+    let (tt, _) = {
+        let source_file = ast::SourceFile::parse(input).ok().unwrap();
+        let tt = source_file.syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
+        syntax_node_to_token_tree(tt.syntax())
+    };
+    let cfg = CfgExpr::parse(&tt);
+    let dnf = DnfExpr::new(cfg);
+    let hints = dnf.compute_enable_hints(opts).map(|diff| diff.to_string()).collect::<Vec<_>>();
+    assert_eq!(hints, expected_hints);
+}
+
+#[test]
+fn test_cfg_expr_parser() {
+    assert_parse_result("#![cfg(foo)]", CfgAtom::Flag("foo".into()).into());
+    assert_parse_result("#![cfg(foo,)]", CfgAtom::Flag("foo".into()).into());
+    assert_parse_result(
+        "#![cfg(not(foo))]",
+        CfgExpr::Not(Box::new(CfgAtom::Flag("foo".into()).into())),
+    );
+    assert_parse_result("#![cfg(foo(bar))]", CfgExpr::Invalid);
+
+    // Only take the first
+    assert_parse_result(r#"#![cfg(foo, bar = "baz")]"#, CfgAtom::Flag("foo".into()).into());
+
+    assert_parse_result(
+        r#"#![cfg(all(foo, bar = "baz"))]"#,
+        CfgExpr::All(vec![
+            CfgAtom::Flag("foo".into()).into(),
+            CfgAtom::KeyValue { key: "bar".into(), value: "baz".into() }.into(),
+        ]),
+    );
+
+    assert_parse_result(
+        r#"#![cfg(any(not(), all(), , bar = "baz",))]"#,
+        CfgExpr::Any(vec![
+            CfgExpr::Not(Box::new(CfgExpr::Invalid)),
+            CfgExpr::All(vec![]),
+            CfgExpr::Invalid,
+            CfgAtom::KeyValue { key: "bar".into(), value: "baz".into() }.into(),
+        ]),
+    );
+}
+
+#[test]
+fn smoke() {
+    check_dnf("#![cfg(test)]", expect![[r#"#![cfg(test)]"#]]);
+    check_dnf("#![cfg(not(test))]", expect![[r#"#![cfg(not(test))]"#]]);
+    check_dnf("#![cfg(not(not(test)))]", expect![[r#"#![cfg(test)]"#]]);
+
+    check_dnf("#![cfg(all(a, b))]", expect![[r#"#![cfg(all(a, b))]"#]]);
+    check_dnf("#![cfg(any(a, b))]", expect![[r#"#![cfg(any(a, b))]"#]]);
+
+    check_dnf("#![cfg(not(a))]", expect![[r#"#![cfg(not(a))]"#]]);
+}
+
+#[test]
+fn distribute() {
+    check_dnf("#![cfg(all(any(a, b), c))]", expect![[r#"#![cfg(any(all(a, c), all(b, c)))]"#]]);
+    check_dnf("#![cfg(all(c, any(a, b)))]", expect![[r#"#![cfg(any(all(c, a), all(c, b)))]"#]]);
+    check_dnf(
+        "#![cfg(all(any(a, b), any(c, d)))]",
+        expect![[r#"#![cfg(any(all(a, c), all(a, d), all(b, c), all(b, d)))]"#]],
+    );
+
+    check_dnf(
+        "#![cfg(all(any(a, b, c), any(d, e, f), g))]",
+        expect![[
+            r#"#![cfg(any(all(a, d, g), all(a, e, g), all(a, f, g), all(b, d, g), all(b, e, g), all(b, f, g), all(c, d, g), all(c, e, g), all(c, f, g)))]"#
+        ]],
+    );
+}
+
+#[test]
+fn demorgan() {
+    check_dnf("#![cfg(not(all(a, b)))]", expect![[r#"#![cfg(any(not(a), not(b)))]"#]]);
+    check_dnf("#![cfg(not(any(a, b)))]", expect![[r#"#![cfg(all(not(a), not(b)))]"#]]);
+
+    check_dnf("#![cfg(not(all(not(a), b)))]", expect![[r#"#![cfg(any(a, not(b)))]"#]]);
+    check_dnf("#![cfg(not(any(a, not(b))))]", expect![[r#"#![cfg(all(not(a), b))]"#]]);
+}
+
+#[test]
+fn nested() {
+    check_dnf("#![cfg(all(any(a), not(all(any(b)))))]", expect![[r#"#![cfg(all(a, not(b)))]"#]]);
+
+    check_dnf("#![cfg(any(any(a, b)))]", expect![[r#"#![cfg(any(a, b))]"#]]);
+    check_dnf("#![cfg(not(any(any(a, b))))]", expect![[r#"#![cfg(all(not(a), not(b)))]"#]]);
+    check_dnf("#![cfg(all(all(a, b)))]", expect![[r#"#![cfg(all(a, b))]"#]]);
+    check_dnf("#![cfg(not(all(all(a, b))))]", expect![[r#"#![cfg(any(not(a), not(b)))]"#]]);
+}
+
+#[test]
+fn regression() {
+    check_dnf("#![cfg(all(not(not(any(any(any()))))))]", expect![[r##"#![cfg(any())]"##]]);
+    check_dnf("#![cfg(all(any(all(any()))))]", expect![[r##"#![cfg(any())]"##]]);
+    check_dnf("#![cfg(all(all(any())))]", expect![[r##"#![cfg(any())]"##]]);
+
+    check_dnf("#![cfg(all(all(any(), x)))]", expect![[r##"#![cfg(any())]"##]]);
+    check_dnf("#![cfg(all(all(any()), x))]", expect![[r##"#![cfg(any())]"##]]);
+    check_dnf("#![cfg(all(all(any(x))))]", expect![[r##"#![cfg(x)]"##]]);
+    check_dnf("#![cfg(all(all(any(x), x)))]", expect![[r##"#![cfg(all(x, x))]"##]]);
+}
+
+#[test]
+fn hints() {
+    let mut opts = CfgOptions::default();
+
+    check_enable_hints("#![cfg(test)]", &opts, &["enable test"]);
+    check_enable_hints("#![cfg(not(test))]", &opts, &[]);
+
+    check_enable_hints("#![cfg(any(a, b))]", &opts, &["enable a", "enable b"]);
+    check_enable_hints("#![cfg(any(b, a))]", &opts, &["enable b", "enable a"]);
+
+    check_enable_hints("#![cfg(all(a, b))]", &opts, &["enable a and b"]);
+
+    opts.insert_atom("test".into());
+
+    check_enable_hints("#![cfg(test)]", &opts, &[]);
+    check_enable_hints("#![cfg(not(test))]", &opts, &["disable test"]);
+}
+
+/// Tests that we don't suggest hints for cfgs that express an inconsistent formula.
+#[test]
+fn hints_impossible() {
+    let mut opts = CfgOptions::default();
+
+    check_enable_hints("#![cfg(all(test, not(test)))]", &opts, &[]);
+
+    opts.insert_atom("test".into());
+
+    check_enable_hints("#![cfg(all(test, not(test)))]", &opts, &[]);
+}
+
+#[test]
+fn why_inactive() {
+    let mut opts = CfgOptions::default();
+    opts.insert_atom("test".into());
+    opts.insert_atom("test2".into());
+
+    check_why_inactive("#![cfg(a)]", &opts, expect![["a is disabled"]]);
+    check_why_inactive("#![cfg(not(test))]", &opts, expect![["test is enabled"]]);
+
+    check_why_inactive(
+        "#![cfg(all(not(test), not(test2)))]",
+        &opts,
+        expect![["test and test2 are enabled"]],
+    );
+    check_why_inactive("#![cfg(all(a, b))]", &opts, expect![["a and b are disabled"]]);
+    check_why_inactive(
+        "#![cfg(all(not(test), a))]",
+        &opts,
+        expect![["test is enabled and a is disabled"]],
+    );
+    check_why_inactive(
+        "#![cfg(all(not(test), test2, a))]",
+        &opts,
+        expect![["test is enabled and a is disabled"]],
+    );
+    check_why_inactive(
+        "#![cfg(all(not(test), not(test2), a))]",
+        &opts,
+        expect![["test and test2 are enabled and a is disabled"]],
+    );
+}
+
+#[test]
+fn proptest() {
+    const REPEATS: usize = 512;
+
+    let mut rng = oorandom::Rand32::new(123456789);
+    let mut buf = Vec::new();
+    for _ in 0..REPEATS {
+        buf.clear();
+        while buf.len() < 512 {
+            buf.extend(rng.rand_u32().to_ne_bytes());
+        }
+
+        let mut u = Unstructured::new(&buf);
+        let cfg = CfgExpr::arbitrary(&mut u).unwrap();
+        DnfExpr::new(cfg);
+    }
+}