use std::cell::{Cell, RefCell};
use std::collections::HashMap;
use super::Ancestors;
use super::chain::Chain;
use crate::checker::Checker;
use crate::node::Node;
impl<'tree, 'chain> Ancestors<'tree, 'chain> {
pub(crate) fn fold_down(
self,
node: &Node<'tree>,
skip: usize,
lane: FoldLane,
init: u8,
step: impl Fn(u8, &Node<'tree>, Ancestors<'tree, 'chain>, &Node<'tree>) -> u8,
) -> u8 {
let Some(chain) = self.chain else {
return fold_climbed(node, skip, init, step);
};
let end = chain.len().saturating_sub(skip);
let step_at = |state: u8, depth: usize| {
step(
state,
&chain[depth],
self.above(depth),
chain.get(depth + 1).unwrap_or(node),
)
};
match self.folds {
Some(cache) => cache.fold(lane, chain, end, init, step_at),
None => (0..end).fold(init, step_at),
}
}
#[doc(hidden)]
pub fn has_ancestor_before_stop<C: Checker>(
self,
node: &Node<'tree>,
lane: GateLane,
check: fn(&Node) -> bool,
stop: fn(&Node) -> bool,
) -> bool {
self.ancestor_before_stop::<C>(node, lane.fold_lane(), check, stop)
}
pub(crate) fn ancestor_before_stop<C: Checker>(
self,
node: &Node<'tree>,
lane: FoldLane,
check: fn(&Node) -> bool,
stop: fn(&Node) -> bool,
) -> bool {
if !self.memoises_folds() {
return node.count_specific_ancestors::<C>(self, check, stop) > 0;
}
self.fold_down(node, 0, lane, 0, |held, ancestor, outer, _| {
if stop(ancestor) {
0
} else if check(ancestor) && !C::is_else_if(ancestor, outer) {
1
} else {
held
}
}) == 1
}
#[doc(hidden)]
#[must_use]
pub fn has_ancestor_of_kind(
self,
node: &Node<'tree>,
lane: KindLane,
kinds: &'static [u16],
) -> bool {
let scan = || {
self.iter(node)
.any(|(ancestor, _)| kinds.contains(&ancestor.kind_id()))
};
if !self.memoises_folds() {
return scan();
}
let folded = self.fold_down(node, 0, lane.fold_lane(), 0, |held, ancestor, _, _| {
u8::from(held == 1 || kinds.contains(&ancestor.kind_id()))
}) == 1;
#[cfg(chain_audit)]
assert_eq!(
folded,
scan(),
"the {lane:?} fold disagrees with the scan on a {} node: a lane \
holds one kind list per walk",
node.kind()
);
folded
}
#[doc(hidden)]
#[must_use]
pub fn nearest_level_answer(
self,
node: &Node<'tree>,
question: LevelQuestion,
code: &[u8],
answer: fn(&[u8], &Node<'tree>, Ancestors<'tree, 'chain>) -> Option<bool>,
) -> bool {
let climb = || {
self.iter(node)
.find_map(|(level, chain)| answer(code, &level, chain))
.unwrap_or(false)
};
let Some(memo) = self.node_memo(question.memo_question()) else {
return climb();
};
let mut deferred = 0;
let mut found = false;
for (level, chain) in self.iter(node) {
if let Some(known) = memo.get(&level) {
found = known;
break;
}
if let Some(own) = answer(code, &level, chain) {
memo.set(&level, own);
found = own;
break;
}
deferred += 1;
}
for (level, _) in self.iter(node).take(deferred) {
memo.set(&level, found);
}
#[cfg(chain_audit)]
assert_eq!(
found,
climb(),
"the {question:?} memo disagrees with the climb on a {} node: a \
question holds one answer fn per walk",
node.kind()
);
found
}
pub(crate) fn node_memo(self, question: MemoQuestion) -> Option<&'chain NodeMemo> {
self.folds.map(|cache| &cache.nodes[question as usize])
}
pub(crate) fn memoised(
self,
question: MemoQuestion,
node: &Node<'_>,
answer: impl FnOnce() -> bool,
) -> bool {
let memo = self.node_memo(question);
if let Some(known) = memo.and_then(|memo| memo.get(node)) {
return known;
}
let answer = answer();
if let Some(memo) = memo {
memo.set(node, answer);
}
answer
}
#[doc(hidden)]
pub fn memoised_answer(
self,
question: NodeQuestion,
node: &Node<'_>,
answer: impl FnOnce() -> bool,
) -> bool {
self.memoised(question.memo_question(), node, answer)
}
pub(crate) fn classified(
self,
slot: WordSlot,
node: &Node<'_>,
classify: impl FnOnce() -> u8,
) -> u8 {
let Some(cache) = self.folds.filter(|cache| cache.visited.get() == node.id()) else {
return classify();
};
let cell = &cache.words[slot as usize];
let (id, answer) = cell.get();
if id == node.id() {
return answer;
}
let answer = classify();
cell.set((node.id(), answer));
answer
}
pub(crate) fn memoises_folds(self) -> bool {
self.folds.is_some() && self.chain.is_some()
}
}
fn deepest_stored(slots: &[(usize, u8)], chain: Chain<'_, '_>, from: usize) -> usize {
(1..=from)
.rev()
.find(|&depth| {
fold_slot_probes::record();
slots[depth].0 == chain[depth].id()
})
.unwrap_or(0)
}
fn fold_climbed<'tree, 'chain>(
node: &Node<'tree>,
skip: usize,
init: u8,
step: impl Fn(u8, &Node<'tree>, Ancestors<'tree, 'chain>, &Node<'tree>) -> u8,
) -> u8
where
'tree: 'chain,
{
let climbed = climbed_chain(node);
let end = climbed.len().saturating_sub(skip);
(0..end).fold(init, |state, depth| {
let below = climbed.get(depth + 1).unwrap_or(node);
step(state, &climbed[depth], Ancestors::unknown(), below)
})
}
pub(super) fn climbed_chain<'tree>(node: &Node<'tree>) -> Vec<Node<'tree>> {
let mut climbed: Vec<_> = std::iter::successors(node.parent(), Node::parent).collect();
climbed.reverse();
climbed
}
#[doc(hidden)]
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum GateLane {
InsideHeader,
InsideExport,
InsideAmbient,
InsideBooleanChain,
}
impl GateLane {
const fn fold_lane(self) -> FoldLane {
match self {
Self::InsideHeader => FoldLane::InsideHeader,
Self::InsideExport => FoldLane::InsideExport,
Self::InsideAmbient => FoldLane::InsideAmbient,
Self::InsideBooleanChain => FoldLane::InsideBooleanChain,
}
}
}
#[doc(hidden)]
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum KindLane {
InsideFunction,
}
impl KindLane {
const fn fold_lane(self) -> FoldLane {
match self {
Self::InsideFunction => FoldLane::InsideFunction,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum FoldLane {
DocInBody,
DocScope,
BareStringClimb,
InsideQuote,
InsideHeader,
InsideExport,
InsideAmbient,
InsideBooleanChain,
NamedBinding,
LambdaDepth,
InsideFunction,
}
impl FoldLane {
const COUNT: usize = 11;
}
const _: () = assert!(FoldLane::InsideFunction as usize + 1 == FoldLane::COUNT);
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum MemoQuestion {
ConditionalDeclares,
ArgumentSlotsReadable,
SwitchArmList,
GuardOperator,
NamesAnArrow,
KeywordListHasDo,
ArgumentIsTrailing,
KeywordsLeadTheirList,
BareStringParenthesisLine,
CodeBeforeOnLine,
InConstBinding,
}
impl MemoQuestion {
const COUNT: usize = 11;
}
const _: () = assert!(MemoQuestion::InConstBinding as usize + 1 == MemoQuestion::COUNT);
#[doc(hidden)]
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum NodeQuestion {
BareStringParenthesisLine,
}
impl NodeQuestion {
const fn memo_question(self) -> MemoQuestion {
match self {
Self::BareStringParenthesisLine => MemoQuestion::BareStringParenthesisLine,
}
}
}
#[doc(hidden)]
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum LevelQuestion {
CodeBeforeOnLine,
InConstBinding,
}
impl LevelQuestion {
const fn memo_question(self) -> MemoQuestion {
match self {
Self::CodeBeforeOnLine => MemoQuestion::CodeBeforeOnLine,
Self::InConstBinding => MemoQuestion::InConstBinding,
}
}
}
#[derive(Debug, Default)]
pub struct FoldCache {
lanes: [RefCell<Vec<(usize, u8)>>; FoldLane::COUNT],
nodes: [NodeMemo; MemoQuestion::COUNT],
words: [Cell<(usize, u8)>; WordSlot::COUNT],
visited: Cell<usize>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum WordSlot {
ElixirCallTarget,
TclCommandWord,
}
impl WordSlot {
const COUNT: usize = 2;
}
const _: () = assert!(WordSlot::TclCommandWord as usize + 1 == WordSlot::COUNT);
#[derive(Debug, Default)]
pub(crate) struct NodeMemo(RefCell<HashMap<usize, bool>>);
impl NodeMemo {
pub(crate) fn get(&self, node: &Node<'_>) -> Option<bool> {
self.0.borrow().get(&node.id()).copied()
}
pub(crate) fn set(&self, node: &Node<'_>, answer: bool) {
self.0.borrow_mut().insert(node.id(), answer);
}
}
impl FoldCache {
pub(super) fn record_visit(&self, node: &Node<'_>) {
self.visited.set(node.id());
}
fn fold(
&self,
lane: FoldLane,
chain: Chain<'_, '_>,
end: usize,
init: u8,
step: impl Fn(u8, usize) -> u8,
) -> u8 {
let Ok(mut slots) = self.lanes[lane as usize].try_borrow_mut() else {
debug_assert!(
same_lane_reentry::allowed(),
"a fold step re-entered its own lane {lane:?}"
);
return (0..end).fold(init, step);
};
let memo_end = end.min(chain.len().saturating_sub(1));
if slots.len() <= memo_end {
slots.resize(memo_end + 1, (0, 0));
}
let mut depth = deepest_stored(&slots, chain, memo_end);
let mut state = if depth == 0 { init } else { slots[depth].1 };
while depth < memo_end {
fold_steps::record();
state = step(state, depth);
depth += 1;
slots[depth] = (chain[depth].id(), state);
}
if end > memo_end {
state = step(state, memo_end);
}
state
}
}
crate::observation::counter!(fold_steps, cfg(any(test, feature = "test-support")));
crate::observation::counter!(fold_slot_probes, cfg(any(test, feature = "test-support")));
pub(super) mod same_lane_reentry {
use std::cell::Cell;
thread_local! {
static ALLOWED: Cell<bool> = const { Cell::new(false) };
}
pub(super) fn allowed() -> bool {
ALLOWED.get()
}
#[cfg(test)]
pub(in crate::node::ancestors) fn allow(allowed: bool) {
ALLOWED.set(allowed);
}
}