From 698f8c2f01ea549d77d7dc3338a12e04c11057b9 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:02:58 +0200 Subject: Adding upstream version 1.64.0+dfsg1. Signed-off-by: Daniel Baumann --- vendor/chalk-engine/src/table.rs | 173 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 173 insertions(+) create mode 100644 vendor/chalk-engine/src/table.rs (limited to 'vendor/chalk-engine/src/table.rs') diff --git a/vendor/chalk-engine/src/table.rs b/vendor/chalk-engine/src/table.rs new file mode 100644 index 000000000..e883cad32 --- /dev/null +++ b/vendor/chalk-engine/src/table.rs @@ -0,0 +1,173 @@ +use crate::index_struct; +use crate::strand::CanonicalStrand; +use crate::{Answer, AnswerMode}; +use rustc_hash::FxHashMap; +use std::collections::hash_map::Entry; +use std::collections::VecDeque; +use std::mem; + +use chalk_ir::interner::Interner; +use chalk_ir::{AnswerSubst, Canonical, Goal, InEnvironment, UCanonical}; +use tracing::{debug, info, instrument}; + +#[derive(Debug)] +pub(crate) struct Table { + /// The goal this table is trying to solve (also the key to look + /// it up). + pub(crate) table_goal: UCanonical>>, + + /// A goal is coinductive if it can assume itself to be true, more + /// or less. This is true for auto traits. + pub(crate) coinductive_goal: bool, + + /// True if this table is floundered, meaning that it doesn't have + /// enough types specified for us to solve. + floundered: bool, + + /// Stores the answers that we have found thus far. When we get a request + /// for an answer N, we will first check this vector. + answers: Vec>, + + /// An alternative storage for the answers we have so far, used to + /// detect duplicates. Not every answer in `answers` will be + /// represented here -- we discard answers from `answers_hash` + /// (but not `answers`) when better answers arrive (in particular, + /// answers with no ambiguity). + /// + /// FIXME -- Ideally we would exclude the region constraints and + /// delayed subgoals from the hash, but that's a bit tricky to do + /// with the current canonicalization setup. It should be ok not + /// to do so though it can result in more answers than we need. + answers_hash: FxHashMap>, bool>, + + /// Stores the active strands that we can "pull on" to find more + /// answers. + strands: VecDeque>, + + pub(crate) answer_mode: AnswerMode, +} + +index_struct! { + pub(crate) struct AnswerIndex { + value: usize, + } +} + +impl Table { + pub(crate) fn new( + table_goal: UCanonical>>, + coinductive_goal: bool, + ) -> Table { + Table { + table_goal, + coinductive_goal, + answers: Vec::new(), + floundered: false, + answers_hash: FxHashMap::default(), + strands: VecDeque::new(), + answer_mode: AnswerMode::Complete, + } + } + + /// Push a strand to the back of the queue of strands to be processed. + pub(crate) fn enqueue_strand(&mut self, strand: CanonicalStrand) { + self.strands.push_back(strand); + } + + pub(crate) fn strands_mut(&mut self) -> impl Iterator> { + self.strands.iter_mut() + } + + pub(crate) fn strands(&self) -> impl Iterator> { + self.strands.iter() + } + + pub(crate) fn take_strands(&mut self) -> VecDeque> { + mem::take(&mut self.strands) + } + + /// Remove the next strand from the queue that meets the given criteria + pub(crate) fn dequeue_next_strand_that( + &mut self, + test: impl Fn(&CanonicalStrand) -> bool, + ) -> Option> { + let first = self.strands.iter().position(test); + if let Some(first) = first { + self.strands.rotate_left(first); + self.strands.pop_front() + } else { + None + } + } + + /// Mark the table as floundered -- this also discards all pre-existing answers, + /// as they are no longer relevant. + pub(crate) fn mark_floundered(&mut self) { + self.floundered = true; + self.strands = Default::default(); + self.answers = Default::default(); + } + + /// Returns true if the table is floundered. + pub(crate) fn is_floundered(&self) -> bool { + self.floundered + } + + /// Adds `answer` to our list of answers, unless it is already present. + /// + /// Returns true if `answer` was added. + /// + /// # Panics + /// This will panic if a previous answer with the same substitution + /// was marked as ambgiuous, but the new answer is not. No current + /// tests trigger this case, and assumptions upstream assume that when + /// `true` is returned here, that a *new* answer was added (instead of an) + /// existing answer replaced. + #[instrument(level = "debug", skip(self))] + pub(super) fn push_answer(&mut self, answer: Answer) -> Option { + assert!(!self.floundered); + debug!( + "pre-existing entry: {:?}", + self.answers_hash.get(&answer.subst) + ); + + let added = match self.answers_hash.entry(answer.subst.clone()) { + Entry::Vacant(entry) => { + entry.insert(answer.ambiguous); + true + } + + Entry::Occupied(entry) => { + let was_ambiguous = entry.get(); + if *was_ambiguous && !answer.ambiguous { + panic!("New answer was not ambiguous whereas previous answer was."); + } + false + } + }; + + info!( + goal = ?self.table_goal, ?answer, + "new answer to table", + ); + if !added { + return None; + } + + let index = self.answers.len(); + self.answers.push(answer); + Some(AnswerIndex::from(index)) + } + + pub(super) fn answer(&self, index: AnswerIndex) -> Option<&Answer> { + self.answers.get(index.value) + } + + pub(super) fn next_answer_index(&self) -> AnswerIndex { + AnswerIndex::from(self.answers.len()) + } +} + +impl AnswerIndex { + pub(crate) const ZERO: AnswerIndex = AnswerIndex { value: 0 }; +} -- cgit v1.2.3