rust-analyzer - Unnamed repository; edit this file 'description' to name the repository.


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

use crate::{Edition, LexedStr, PrefixEntryPoint, Step};

#[test]
fn vis() {
    check(PrefixEntryPoint::Vis, "pub(crate) fn foo() {}", "pub(crate)");
    check(PrefixEntryPoint::Vis, "fn foo() {}", "");
    check(PrefixEntryPoint::Vis, "pub(fn foo() {}", "pub");
    check(PrefixEntryPoint::Vis, "pub(crate fn foo() {}", "pub(crate");
}

#[test]
fn block() {
    check(PrefixEntryPoint::Block, "{}, 92", "{}");
    check(PrefixEntryPoint::Block, "{, 92)", "{, 92)");
    check(PrefixEntryPoint::Block, "()", "");
}

#[test]
fn stmt() {
    check(PrefixEntryPoint::Stmt, "92; fn", "92");
    check(PrefixEntryPoint::Stmt, "let _ = 92; 1", "let _ = 92");
    check(PrefixEntryPoint::Stmt, "pub fn f() {} = 92", "pub fn f() {}");
    check(PrefixEntryPoint::Stmt, "struct S;;", "struct S;");
    check(PrefixEntryPoint::Stmt, "fn f() {};", "fn f() {}");
    check(PrefixEntryPoint::Stmt, ";;;", ";");
    check(PrefixEntryPoint::Stmt, "+", "+");
    check(PrefixEntryPoint::Stmt, "@", "@");
    check(PrefixEntryPoint::Stmt, "loop {} - 1", "loop {}");
}

#[test]
fn pat() {
    check(PrefixEntryPoint::Pat, "x y", "x");
    check(PrefixEntryPoint::Pat, "fn f() {}", "fn");
    check(PrefixEntryPoint::Pat, ".. ..", "..");
}

#[test]
fn ty() {
    check(PrefixEntryPoint::Ty, "fn() foo", "fn()");
    check(PrefixEntryPoint::Ty, "Clone + Copy + fn", "Clone + Copy +");
    check(PrefixEntryPoint::Ty, "struct f", "struct");
}

#[test]
fn expr() {
    check(PrefixEntryPoint::Expr, "92 92", "92");
    check(PrefixEntryPoint::Expr, "+1", "+");
    check(PrefixEntryPoint::Expr, "-1", "-1");
    check(PrefixEntryPoint::Expr, "fn foo() {}", "fn");
    check(PrefixEntryPoint::Expr, "#[attr] ()", "#[attr] ()");
    check(PrefixEntryPoint::Expr, "foo.0", "foo.0");
    check(PrefixEntryPoint::Expr, "foo.0.1", "foo.0.1");
    check(PrefixEntryPoint::Expr, "foo.0. foo", "foo.0. foo");
}

#[test]
fn path() {
    check(PrefixEntryPoint::Path, "foo::bar baz", "foo::bar");
    check(PrefixEntryPoint::Path, "foo::<> baz", "foo::<>");
    check(PrefixEntryPoint::Path, "foo<> baz", "foo<>");
    check(PrefixEntryPoint::Path, "Fn() -> i32?", "Fn() -> i32");
    // FIXME: This shouldn't be accepted as path actually.
    check(PrefixEntryPoint::Path, "<_>::foo", "<_>::foo");
}

#[test]
fn item() {
    // FIXME: This shouldn't consume the semicolon.
    check(PrefixEntryPoint::Item, "fn foo() {};", "fn foo() {};");
    check(PrefixEntryPoint::Item, "#[attr] pub struct S {} 92", "#[attr] pub struct S {}");
    check(PrefixEntryPoint::Item, "item!{}?", "item!{}");
    check(PrefixEntryPoint::Item, "????", "?");
}

#[test]
fn meta_item() {
    check(PrefixEntryPoint::MetaItem, "attr, ", "attr");
    check(PrefixEntryPoint::MetaItem, "attr(some token {stream});", "attr(some token {stream})");
    check(PrefixEntryPoint::MetaItem, "path::attr = 2 * 2!", "path::attr = 2 * 2");
}

#[track_caller]
fn check(entry: PrefixEntryPoint, input: &str, prefix: &str) {
    let lexed = LexedStr::new(Edition::CURRENT, input);
    let input = lexed.to_input(Edition::CURRENT);

    let mut n_tokens = 0;
    for step in entry.parse(&input, Edition::CURRENT).iter() {
        match step {
            Step::Token { n_input_tokens, .. } => n_tokens += n_input_tokens as usize,
            Step::FloatSplit { .. } => n_tokens += 1,
            Step::Enter { .. } | Step::Exit | Step::Error { .. } => (),
        }
    }

    let mut i = 0;
    loop {
        if n_tokens == 0 {
            break;
        }
        if !lexed.kind(i).is_trivia() {
            n_tokens -= 1;
        }
        i += 1;
    }
    let buf = &lexed.as_str()[..lexed.text_start(i)];
    assert_eq!(buf, prefix);
}
use oorandom::Rand64;
use parking_lot::Mutex;
use std::fmt::Debug;
use std::sync::atomic::AtomicU16;
use std::sync::atomic::Ordering;
use triomphe::Arc;

/// A simple and approximate concurrent lru list.
///
/// We assume but do not verify that each node is only used with one
/// list. If this is not the case, it is not *unsafe*, but panics and
/// weird results will ensue.
///
/// Each "node" in the list is of type `Node` and must implement
/// `LruNode`, which is a trait that gives access to a field that
/// stores the index in the list. This index gives us a rough idea of
/// how recently the node has been used.
#[derive(Debug)]
pub(crate) struct Lru<Node>
where
    Node: LruNode,
{
    green_zone: AtomicU16,
    data: Mutex<LruData<Node>>,
}

#[derive(Debug)]
struct LruData<Node> {
    end_red_zone: u16,
    end_yellow_zone: u16,
    end_green_zone: u16,
    rng: Rand64,
    entries: Vec<Arc<Node>>,
}

pub(crate) trait LruNode: Sized + Debug {
    fn lru_index(&self) -> &LruIndex;
}

#[derive(Debug)]
pub(crate) struct LruIndex {
    /// Index in the appropriate LRU list, or std::u16::MAX if not a
    /// member.
    index: AtomicU16,
}

impl<Node> Default for Lru<Node>
where
    Node: LruNode,
{
    fn default() -> Self {
        Lru::new()
    }
}

// We always use a fixed seed for our randomness so that we have
// predictable results.
const LRU_SEED: &str = "Hello, Rustaceans";

impl<Node> Lru<Node>
where
    Node: LruNode,
{
    /// Creates a new LRU list where LRU caching is disabled.
    pub(crate) fn new() -> Self {
        Self::with_seed(LRU_SEED)
    }

    #[cfg_attr(not(test), allow(dead_code))]
    fn with_seed(seed: &str) -> Self {
        Lru { green_zone: AtomicU16::new(0), data: Mutex::new(LruData::with_seed(seed)) }
    }

    /// Adjust the total number of nodes permitted to have a value at
    /// once.  If `len` is zero, this disables LRU caching completely.
    pub(crate) fn set_lru_capacity(&self, len: u16) {
        let mut data = self.data.lock();

        // We require each zone to have at least 1 slot. Therefore,
        // the length cannot be just 1 or 2.
        if len == 0 {
            self.green_zone.store(0, Ordering::Release);
            data.resize(0, 0, 0);
        } else {
            let len = std::cmp::max(len, 3);

            // Top 10% is the green zone. This must be at least length 1.
            let green_zone = std::cmp::max(len / 10, 1);

            // Next 20% is the yellow zone.
            let yellow_zone = std::cmp::max(len / 5, 1);

            // Remaining 70% is the red zone.
            let red_zone = len - yellow_zone - green_zone;

            // We need quick access to the green zone.
            self.green_zone.store(green_zone, Ordering::Release);

            // Resize existing array.
            data.resize(green_zone, yellow_zone, red_zone);
        }
    }

    /// Records that `node` was used. This may displace an old node (if the LRU limits are
    pub(crate) fn record_use(&self, node: &Arc<Node>) -> Option<Arc<Node>> {
        tracing::debug!("record_use(node={:?})", node);

        // Load green zone length and check if the LRU cache is even enabled.
        let green_zone = self.green_zone.load(Ordering::Acquire);
        tracing::debug!("record_use: green_zone={}", green_zone);
        if green_zone == 0 {
            return None;
        }

        // Find current index of list (if any) and the current length
        // of our green zone.
        let index = node.lru_index().load();
        tracing::debug!("record_use: index={}", index);

        // Already a member of the list, and in the green zone -- nothing to do!
        if index < green_zone {
            return None;
        }

        self.data.lock().record_use(node)
    }

    pub(crate) fn purge(&self) {
        self.green_zone.store(0, Ordering::SeqCst);
        *self.data.lock() = LruData::with_seed(LRU_SEED);
    }
}

impl<Node> LruData<Node>
where
    Node: LruNode,
{
    fn with_seed(seed_str: &str) -> Self {
        Self::with_rng(rng_with_seed(seed_str))
    }

    fn with_rng(rng: Rand64) -> Self {
        LruData { end_yellow_zone: 0, end_green_zone: 0, end_red_zone: 0, entries: Vec::new(), rng }
    }

    fn green_zone(&self) -> std::ops::Range<u16> {
        0..self.end_green_zone
    }

    fn yellow_zone(&self) -> std::ops::Range<u16> {
        self.end_green_zone..self.end_yellow_zone
    }

    fn red_zone(&self) -> std::ops::Range<u16> {
        self.end_yellow_zone..self.end_red_zone
    }

    fn resize(&mut self, len_green_zone: u16, len_yellow_zone: u16, len_red_zone: u16) {
        self.end_green_zone = len_green_zone;
        self.end_yellow_zone = self.end_green_zone + len_yellow_zone;
        self.end_red_zone = self.end_yellow_zone + len_red_zone;
        let entries =
            std::mem::replace(&mut self.entries, Vec::with_capacity(self.end_red_zone as usize));

        tracing::debug!("green_zone = {:?}", self.green_zone());
        tracing::debug!("yellow_zone = {:?}", self.yellow_zone());
        tracing::debug!("red_zone = {:?}", self.red_zone());

        // We expect to resize when the LRU cache is basically empty.
        // So just forget all the old LRU indices to start.
        for entry in entries {
            entry.lru_index().clear();
        }
    }

    /// Records that a node was used. If it is already a member of the
    /// LRU list, it is promoted to the green zone (unless it's
    /// already there). Otherwise, it is added to the list first and
    /// *then* promoted to the green zone. Adding a new node to the
    /// list may displace an old member of the red zone, in which case
    /// that is returned.
    fn record_use(&mut self, node: &Arc<Node>) -> Option<Arc<Node>> {
        tracing::debug!("record_use(node={:?})", node);

        // NB: When this is invoked, we have typically already loaded
        // the LRU index (to check if it is in green zone). But that
        // check was done outside the lock and -- for all we know --
        // the index may have changed since. So we always reload.
        let index = node.lru_index().load();

        if index < self.end_green_zone {
            None
        } else if index < self.end_yellow_zone {
            self.promote_yellow_to_green(node, index);
            None
        } else if index < self.end_red_zone {
            self.promote_red_to_green(node, index);
            None
        } else {
            self.insert_new(node)
        }
    }

    /// Inserts a node that is not yet a member of the LRU list. If
    /// the list is at capacity, this can displace an existing member.
    fn insert_new(&mut self, node: &Arc<Node>) -> Option<Arc<Node>> {
        debug_assert!(!node.lru_index().is_in_lru());

        // Easy case: we still have capacity. Push it, and then promote
        // it up to the appropriate zone.
        let len = self.entries.len() as u16;
        if len < self.end_red_zone {
            self.entries.push(node.clone());
            node.lru_index().store(len);
            tracing::debug!("inserted node {:?} at {}", node, len);
            return self.record_use(node);
        }

        // Harder case: no capacity. Create some by evicting somebody from red
        // zone and then promoting.
        let victim_index = self.pick_index(self.red_zone());
        let victim_node = std::mem::replace(&mut self.entries[victim_index as usize], node.clone());
        tracing::debug!("evicting red node {:?} from {}", victim_node, victim_index);
        victim_node.lru_index().clear();
        self.promote_red_to_green(node, victim_index);
        Some(victim_node)
    }

    /// Promotes the node `node`, stored at `red_index` (in the red
    /// zone), into a green index, demoting yellow/green nodes at
    /// random.
    ///
    /// NB: It is not required that `node.lru_index()` is up-to-date
    /// when entering this method.
    fn promote_red_to_green(&mut self, node: &Arc<Node>, red_index: u16) {
        debug_assert!(self.red_zone().contains(&red_index));

        // Pick a yellow at random and switch places with it.
        //
        // Subtle: we do not update `node.lru_index` *yet* -- we're
        // going to invoke `self.promote_yellow` next, and it will get
        // updated then.
        let yellow_index = self.pick_index(self.yellow_zone());
        tracing::debug!(
            "demoting yellow node {:?} from {} to red at {}",
            self.entries[yellow_index as usize],
            yellow_index,
            red_index,
        );
        self.entries.swap(yellow_index as usize, red_index as usize);
        self.entries[red_index as usize].lru_index().store(red_index);

        // Now move ourselves up into the green zone.
        self.promote_yellow_to_green(node, yellow_index);
    }

    /// Promotes the node `node`, stored at `yellow_index` (in the
    /// yellow zone), into a green index, demoting a green node at
    /// random to replace it.
    ///
    /// NB: It is not required that `node.lru_index()` is up-to-date
    /// when entering this method.
    fn promote_yellow_to_green(&mut self, node: &Arc<Node>, yellow_index: u16) {
        debug_assert!(self.yellow_zone().contains(&yellow_index));

        // Pick a yellow at random and switch places with it.
        let green_index = self.pick_index(self.green_zone());
        tracing::debug!(
            "demoting green node {:?} from {} to yellow at {}",
            self.entries[green_index as usize],
            green_index,
            yellow_index
        );
        self.entries.swap(green_index as usize, yellow_index as usize);
        self.entries[yellow_index as usize].lru_index().store(yellow_index);
        node.lru_index().store(green_index);

        tracing::debug!("promoted {:?} to green index {}", node, green_index);
    }

    fn pick_index(&mut self, zone: std::ops::Range<u16>) -> u16 {
        let end_index = std::cmp::min(zone.end, self.entries.len() as u16);
        self.rng.rand_range(zone.start as u64..end_index as u64) as u16
    }
}

impl Default for LruIndex {
    fn default() -> Self {
        Self { index: AtomicU16::new(u16::MAX) }
    }
}

impl LruIndex {
    fn load(&self) -> u16 {
        self.index.load(Ordering::Acquire) // see note on ordering below
    }

    fn store(&self, value: u16) {
        self.index.store(value, Ordering::Release) // see note on ordering below
    }

    fn clear(&self) {
        self.store(u16::MAX);
    }

    fn is_in_lru(&self) -> bool {
        self.load() != u16::MAX
    }
}

fn rng_with_seed(seed_str: &str) -> Rand64 {
    let mut seed: [u8; 16] = [0; 16];
    for (i, &b) in seed_str.as_bytes().iter().take(16).enumerate() {
        seed[i] = b;
    }
    Rand64::new(u128::from_le_bytes(seed))
}

// A note on ordering:
//
// I chose to use AcqRel for the ordering but I don't think it's
// strictly needed.  All writes occur under a lock, so they should be
// ordered w/r/t one another.  As for the reads, they can occur
// outside the lock, but they don't themselves enable dependent reads
// -- if the reads are out of bounds, we would acquire a lock.