shuck_linter/facts/
core.rs

1use super::{
2    assignments::DeclarationAssignmentProbe,
3    command_options::PathWordFact,
4    commands::CommandFact,
5    redirects::{ComparableNameUse, RedirectFact},
6    substitutions::SubstitutionFact,
7};
8use rustc_hash::FxHashMap;
9use shuck_ast::{Command, IdRange, ListArena, Name, Redirect, Span, Stmt};
10use shuck_semantic::SemanticModel;
11use smallvec::SmallVec;
12
13pub use shuck_semantic::CommandId;
14
15#[derive(Debug, Clone, Copy)]
16pub(crate) struct CommandVisit<'a> {
17    pub(crate) stmt: &'a Stmt,
18    pub(crate) command: &'a Command,
19    pub(crate) redirects: &'a [Redirect],
20}
21
22impl<'a> CommandVisit<'a> {
23    pub(crate) fn new(stmt: &'a Stmt) -> Self {
24        Self {
25            stmt,
26            command: &stmt.command,
27            redirects: &stmt.redirects,
28        }
29    }
30}
31
32#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
33pub struct FactSpan {
34    start: usize,
35    end: usize,
36}
37
38impl FactSpan {
39    pub fn new(span: Span) -> Self {
40        Self {
41            start: span.start.offset,
42            end: span.end.offset,
43        }
44    }
45}
46
47impl From<Span> for FactSpan {
48    fn from(span: Span) -> Self {
49        Self::new(span)
50    }
51}
52
53#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
54pub struct WordNodeId(u32);
55
56impl WordNodeId {
57    pub(crate) fn new(index: usize) -> Self {
58        Self(fact_id_index_to_u32(index, "word node id"))
59    }
60
61    pub(crate) fn index(self) -> usize {
62        self.0 as usize
63    }
64}
65
66#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
67pub struct WordOccurrenceId(u32);
68
69impl WordOccurrenceId {
70    pub(crate) fn new(index: usize) -> Self {
71        Self(fact_id_index_to_u32(index, "word occurrence id"))
72    }
73
74    pub(crate) fn index(self) -> usize {
75        self.0 as usize
76    }
77}
78
79#[inline]
80fn fact_id_index_to_u32(index: usize, kind: &'static str) -> u32 {
81    if index > u32::MAX as usize {
82        fact_id_index_overflow(kind);
83    }
84    index as u32
85}
86
87#[cold]
88#[inline(never)]
89fn fact_id_index_overflow(kind: &'static str) -> ! {
90    panic!("{kind} must fit in u32");
91}
92
93#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
94pub(crate) enum CommandLookupKind {
95    Simple,
96    Builtin(BuiltinLookupKind),
97    Decl,
98    Binary,
99    Compound(CompoundLookupKind),
100    Function,
101    AnonymousFunction,
102}
103
104#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
105pub(crate) enum BuiltinLookupKind {
106    Break,
107    Continue,
108    Return,
109    Exit,
110}
111
112#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
113pub(crate) enum CompoundLookupKind {
114    If,
115    For,
116    Repeat,
117    Foreach,
118    ArithmeticFor,
119    While,
120    Until,
121    Case,
122    Select,
123    Subshell,
124    BraceGroup,
125    Arithmetic,
126    Time,
127    Conditional,
128    Coproc,
129    Always,
130}
131
132#[derive(Debug, Clone, Copy)]
133pub(crate) struct CommandLookupEntry {
134    pub(crate) kind: CommandLookupKind,
135    pub(crate) id: CommandId,
136}
137
138pub(crate) type CommandLookupIndex = FxHashMap<FactSpan, SmallVec<[CommandLookupEntry; 1]>>;
139
140#[derive(Debug, Clone, Default)]
141pub(crate) struct DenseCommandIdSet {
142    words: Vec<u64>,
143}
144
145impl DenseCommandIdSet {
146    const BITS: usize = u64::BITS as usize;
147
148    pub(crate) fn with_capacity(command_count: usize) -> Self {
149        Self {
150            words: vec![0; command_count.div_ceil(Self::BITS)],
151        }
152    }
153
154    pub(crate) fn insert(&mut self, id: CommandId) {
155        let index = id.index();
156        let word = index / Self::BITS;
157        let bit = index % Self::BITS;
158        if word >= self.words.len() {
159            self.words.resize(word + 1, 0);
160        }
161        self.words[word] |= 1u64 << bit;
162    }
163
164    pub(crate) fn contains(&self, id: CommandId) -> bool {
165        let index = id.index();
166        let word = index / Self::BITS;
167        let bit = index % Self::BITS;
168        self.words
169            .get(word)
170            .is_some_and(|w| (w & (1u64 << bit)) != 0)
171    }
172}
173
174#[derive(Debug, Clone)]
175pub(crate) struct FactStore<'a> {
176    pub(crate) redirect_facts: ListArena<RedirectFact<'a>>,
177    pub(crate) substitution_facts: ListArena<SubstitutionFact>,
178    pub(crate) scope_read_source_words: ListArena<PathWordFact<'a>>,
179    pub(crate) scope_name_read_uses: ListArena<ComparableNameUse>,
180    pub(crate) scope_heredoc_name_read_uses: ListArena<ComparableNameUse>,
181    pub(crate) scope_name_write_uses: ListArena<ComparableNameUse>,
182    pub(crate) declaration_assignment_probes: ListArena<DeclarationAssignmentProbe>,
183    pub(crate) word_occurrence_ids: ListArena<WordOccurrenceId>,
184    pub(crate) word_occurrence_ids_by_command: Vec<IdRange<WordOccurrenceId>>,
185    pub(crate) word_spans: ListArena<Span>,
186}
187
188#[derive(Debug, Clone)]
189pub(crate) struct CommandChildIndex {
190    ids: ListArena<CommandId>,
191    by_parent: Vec<IdRange<CommandId>>,
192}
193
194impl CommandChildIndex {
195    pub(crate) fn from_semantic_syntax_backed_children(
196        semantic: &SemanticModel,
197        command_fact_indices_by_id: &[Option<usize>],
198    ) -> Self {
199        let total_children = semantic
200            .commands()
201            .iter()
202            .copied()
203            .map(|parent| {
204                semantic
205                    .syntax_backed_command_children(parent)
206                    .iter()
207                    .copied()
208                    .filter(|child| command_fact_exists(command_fact_indices_by_id, *child))
209                    .count()
210            })
211            .sum();
212        let mut ids = ListArena::with_capacity(total_children);
213        let mut by_parent = Vec::with_capacity(semantic.command_count());
214        by_parent.resize_with(semantic.command_count(), IdRange::empty);
215
216        for parent in semantic.commands().iter().copied() {
217            by_parent[parent.index()] = ids.push_many(
218                semantic
219                    .syntax_backed_command_children(parent)
220                    .iter()
221                    .copied()
222                    .filter(|child| command_fact_exists(command_fact_indices_by_id, *child)),
223            );
224        }
225
226        Self { ids, by_parent }
227    }
228
229    pub(crate) fn child_ids(&self, id: CommandId) -> &[CommandId] {
230        self.by_parent
231            .get(id.index())
232            .copied()
233            .map_or(&[], |range| self.ids.get(range))
234    }
235}
236
237fn command_fact_exists(command_fact_indices_by_id: &[Option<usize>], id: CommandId) -> bool {
238    command_fact_indices_by_id
239        .get(id.index())
240        .is_some_and(Option::is_some)
241}
242
243impl<'a> FactStore<'a> {
244    pub(crate) fn empty() -> Self {
245        Self {
246            redirect_facts: ListArena::new(),
247            substitution_facts: ListArena::new(),
248            scope_read_source_words: ListArena::new(),
249            scope_name_read_uses: ListArena::new(),
250            scope_heredoc_name_read_uses: ListArena::new(),
251            scope_name_write_uses: ListArena::new(),
252            declaration_assignment_probes: ListArena::new(),
253            word_occurrence_ids: ListArena::new(),
254            word_occurrence_ids_by_command: Vec::new(),
255            word_spans: ListArena::new(),
256        }
257    }
258
259    pub(crate) fn redirect_facts(&self, range: IdRange<RedirectFact<'a>>) -> &[RedirectFact<'a>] {
260        self.redirect_facts.get(range)
261    }
262
263    pub(crate) fn substitution_facts(
264        &self,
265        range: IdRange<SubstitutionFact>,
266    ) -> &[SubstitutionFact] {
267        self.substitution_facts.get(range)
268    }
269
270    pub(crate) fn scope_read_source_words(
271        &self,
272        range: IdRange<PathWordFact<'a>>,
273    ) -> &[PathWordFact<'a>] {
274        self.scope_read_source_words.get(range)
275    }
276
277    pub(crate) fn scope_name_read_uses(
278        &self,
279        range: IdRange<ComparableNameUse>,
280    ) -> &[ComparableNameUse] {
281        self.scope_name_read_uses.get(range)
282    }
283
284    pub(crate) fn scope_heredoc_name_read_uses(
285        &self,
286        range: IdRange<ComparableNameUse>,
287    ) -> &[ComparableNameUse] {
288        self.scope_heredoc_name_read_uses.get(range)
289    }
290
291    pub(crate) fn scope_name_write_uses(
292        &self,
293        range: IdRange<ComparableNameUse>,
294    ) -> &[ComparableNameUse] {
295        self.scope_name_write_uses.get(range)
296    }
297
298    pub(crate) fn declaration_assignment_probes(
299        &self,
300        range: IdRange<DeclarationAssignmentProbe>,
301    ) -> &[DeclarationAssignmentProbe] {
302        self.declaration_assignment_probes.get(range)
303    }
304
305    pub(crate) fn word_occurrence_ids_for_command(&self, id: CommandId) -> &[WordOccurrenceId] {
306        self.word_occurrence_ids_by_command
307            .get(id.index())
308            .copied()
309            .map_or(&[], |range| self.word_occurrence_ids.get(range))
310    }
311
312    pub(crate) fn word_spans(&self, range: IdRange<Span>) -> &[Span] {
313        self.word_spans.get(range)
314    }
315}
316
317#[derive(Clone, Copy)]
318pub struct CommandFactRef<'facts, 'a> {
319    pub(crate) fact: &'facts CommandFact<'a>,
320    pub(crate) store: &'facts FactStore<'a>,
321}
322
323impl<'facts, 'a> CommandFactRef<'facts, 'a> {
324    pub(crate) fn new(fact: &'facts CommandFact<'a>, store: &'facts FactStore<'a>) -> Self {
325        Self { fact, store }
326    }
327}
328
329impl<'facts, 'a> std::fmt::Debug for CommandFactRef<'facts, 'a> {
330    fn fmt(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
331        self.fact.fmt(formatter)
332    }
333}
334
335impl<'facts, 'a> std::ops::Deref for CommandFactRef<'facts, 'a> {
336    type Target = CommandFact<'a>;
337
338    fn deref(&self) -> &Self::Target {
339        self.fact
340    }
341}
342
343#[derive(Clone, Copy)]
344pub struct CommandFacts<'facts, 'a> {
345    pub(crate) commands: &'facts [CommandFact<'a>],
346    pub(crate) store: &'facts FactStore<'a>,
347    pub(crate) indices_by_id: &'facts [Option<usize>],
348}
349
350impl<'facts, 'a> CommandFacts<'facts, 'a> {
351    pub(crate) fn new(
352        commands: &'facts [CommandFact<'a>],
353        store: &'facts FactStore<'a>,
354        indices_by_id: &'facts [Option<usize>],
355    ) -> Self {
356        Self {
357            commands,
358            store,
359            indices_by_id,
360        }
361    }
362
363    pub fn len(self) -> usize {
364        self.commands.len()
365    }
366
367    pub fn is_empty(self) -> bool {
368        self.commands.is_empty()
369    }
370
371    pub fn iter(self) -> CommandFactIter<'facts, 'a> {
372        CommandFactIter {
373            inner: self.commands.iter(),
374            store: self.store,
375        }
376    }
377
378    #[cfg(test)]
379    pub(crate) fn raw(self) -> &'facts [CommandFact<'a>] {
380        self.commands
381    }
382
383    pub fn get(self, index: usize) -> Option<CommandFactRef<'facts, 'a>> {
384        self.commands
385            .get(index)
386            .map(|fact| CommandFactRef::new(fact, self.store))
387    }
388
389    pub fn find(self, id: CommandId) -> Option<CommandFactRef<'facts, 'a>> {
390        self.indices_by_id
391            .get(id.index())
392            .copied()
393            .flatten()
394            .and_then(|index| self.commands.get(index))
395            .map(|fact| CommandFactRef::new(fact, self.store))
396    }
397
398    pub(crate) fn index_of(self, id: CommandId) -> Option<usize> {
399        self.indices_by_id.get(id.index()).copied().flatten()
400    }
401
402    pub(crate) fn iter_from(self, start: usize) -> CommandFactIter<'facts, 'a> {
403        let slice = self.commands.get(start..).unwrap_or(&[]);
404        CommandFactIter {
405            inner: slice.iter(),
406            store: self.store,
407        }
408    }
409
410    /// Iterate commands whose span is fully contained in `outer`.
411    ///
412    /// Relies on `self.commands` being sorted by `span.start.offset` ascending,
413    /// which `LinterFactsBuilder::build` enforces. Uses a binary search to skip
414    /// commands that start before `outer`, then walks forward only as far as
415    /// the outer span reaches.
416    pub(crate) fn contained_in(
417        self,
418        outer: Span,
419    ) -> impl Iterator<Item = CommandFactRef<'facts, 'a>> {
420        let start_offset = outer.start.offset;
421        let end_offset = outer.end.offset;
422        let start = self
423            .commands
424            .partition_point(|fact| fact.span().start.offset < start_offset);
425        let store = self.store;
426        self.commands[start..]
427            .iter()
428            .take_while(move |fact| fact.span().start.offset <= end_offset)
429            .filter(move |fact| fact.span().end.offset <= end_offset)
430            .map(move |fact| CommandFactRef::new(fact, store))
431    }
432
433    pub fn first(self) -> Option<CommandFactRef<'facts, 'a>> {
434        self.get(0)
435    }
436
437    pub fn last(self) -> Option<CommandFactRef<'facts, 'a>> {
438        self.commands
439            .last()
440            .map(|fact| CommandFactRef::new(fact, self.store))
441    }
442}
443
444impl<'facts, 'a> IntoIterator for CommandFacts<'facts, 'a> {
445    type Item = CommandFactRef<'facts, 'a>;
446    type IntoIter = CommandFactIter<'facts, 'a>;
447
448    fn into_iter(self) -> Self::IntoIter {
449        self.iter()
450    }
451}
452
453impl<'facts, 'a> IntoIterator for &CommandFacts<'facts, 'a> {
454    type Item = CommandFactRef<'facts, 'a>;
455    type IntoIter = CommandFactIter<'facts, 'a>;
456
457    fn into_iter(self) -> Self::IntoIter {
458        (*self).iter()
459    }
460}
461
462#[derive(Clone)]
463pub struct CommandFactIter<'facts, 'a> {
464    inner: std::slice::Iter<'facts, CommandFact<'a>>,
465    store: &'facts FactStore<'a>,
466}
467
468impl<'facts, 'a> Iterator for CommandFactIter<'facts, 'a> {
469    type Item = CommandFactRef<'facts, 'a>;
470
471    fn next(&mut self) -> Option<Self::Item> {
472        self.inner
473            .next()
474            .map(|fact| CommandFactRef::new(fact, self.store))
475    }
476
477    fn size_hint(&self) -> (usize, Option<usize>) {
478        self.inner.size_hint()
479    }
480}
481
482impl<'facts, 'a> DoubleEndedIterator for CommandFactIter<'facts, 'a> {
483    fn next_back(&mut self) -> Option<Self::Item> {
484        self.inner
485            .next_back()
486            .map(|fact| CommandFactRef::new(fact, self.store))
487    }
488}
489
490impl<'facts, 'a> ExactSizeIterator for CommandFactIter<'facts, 'a> {}
491
492#[derive(Debug, Clone, Copy, PartialEq, Eq)]
493pub enum SudoFamilyInvoker {
494    Sudo,
495    Doas,
496    Run0,
497}
498
499#[derive(Debug, Clone, PartialEq, Eq)]
500pub struct NamedSpan {
501    pub name: Name,
502    pub span: Span,
503}
504
505#[derive(Debug, Clone, PartialEq, Eq)]
506pub struct BacktickEscapedParameter {
507    pub name: Option<Name>,
508    pub diagnostic_span: Span,
509    pub reference_span: Span,
510    pub standalone_command_name: bool,
511}
shuck_linter/facts/core.rs

shuck_linter/facts/
core.rs
