Line data    Source code

       1              : //! The name search index of a catalog entry.
       2              : //!
       3              : //! Every suffix of every name, sorted case-insensitively as (name, suffix offset) pairs, so that a
       4              : //! prefix search over the suffixes finds substring matches. Equal suffixes keep the order of the
       5              : //! names.
       6              : 
       7              : use super::entry::CatalogObjectRef;
       8              : use crate::utils::{ci_cmp, ci_starts_with};
       9              : use dashql_buffers::analyzer::NameTag;
      10              : use dashql_parser::span::TextSpan;
      11              : use std::sync::{Arc, OnceLock};
      12              : 
      13              : /// A name of the index (the fields of `RegisteredName` the completion reads)
      14              : #[derive(Clone, Debug)]
      15              : pub struct IndexedName {
      16              :     /// The name text
      17              :     pub text: Arc<str>,
      18              :     /// How often the name occurs in the entry
      19              :     pub occurrences: u32,
      20              :     /// The location of the first occurrence in the script text
      21              :     pub location: TextSpan,
      22              :     /// The analyzer tags
      23              :     pub tags: NameTag,
      24              :     /// The objects the name resolves to
      25              :     pub objects: Vec<CatalogObjectRef>,
      26              : }
      27              : 
      28              : /// A substring search index over the names of a catalog entry.
      29              : ///
      30              : /// The names are collected when the entry is created, the suffixes are sorted on the first search, so
      31              : /// that analyses which are never searched don't pay for the index.
      32              : #[derive(Debug, Default)]
      33              : pub struct NameSearchIndex {
      34              :     /// The indexed names, the suffixes refer to them by index
      35              :     pub names: Vec<IndexedName>,
      36              :     /// (name index, byte offset of the suffix), sorted case-insensitively by the suffix, built on first use
      37              :     suffixes: OnceLock<Vec<(u32, u32)>>,
      38              : }
      39              : 
      40              : impl NameSearchIndex {
      41         3737 :     pub fn new(names: Vec<IndexedName>) -> Self {
      42         3737 :         Self {
      43         3737 :             names,
      44         3737 :             suffixes: OnceLock::new(),
      45         3737 :         }
      46         3737 :     }
      47              : 
      48              :     /// The sorted suffixes
      49          262 :     fn suffixes(&self) -> &[(u32, u32)] {
      50          262 :         self.suffixes.get_or_init(|| {
      51          226 :             let mut suffixes = Vec::new();
      52         1149 :             for (i, name) in self.names.iter().enumerate() {
      53         5575 :                 suffixes.extend((0..name.text.len() as u32).map(|offset| (i as u32, offset)));
      54              :             }
      55              :             // Stable, so equal keys keep the order of the names
      56        38793 :             suffixes.sort_by(|a, b| ci_cmp(self.suffix(*a), self.suffix(*b)));
      57          226 :             suffixes
      58          226 :         })
      59          262 :     }
      60              : 
      61              :     /// Were the suffixes sorted already?
      62           99 :     pub fn is_built(&self) -> bool {
      63           99 :         self.suffixes.get().is_some()
      64           99 :     }
      65              : 
      66              :     /// The number of indexed suffixes
      67            2 :     pub fn len(&self) -> usize {
      68            2 :         self.suffixes().len()
      69            2 :     }
      70              : 
      71            1 :     pub fn is_empty(&self) -> bool {
      72            1 :         self.suffixes().is_empty()
      73            1 :     }
      74              : 
      75              :     /// The bytes of the suffix index
      76            2 :     pub fn byte_size(&self) -> usize {
      77            2 :         self.suffixes().len() * std::mem::size_of::<(u32, u32)>()
      78            2 :     }
      79              : 
      80        79405 :     fn suffix(&self, entry: (u32, u32)) -> &[u8] {
      81        79405 :         &self.names[entry.0 as usize].text.as_bytes()[entry.1 as usize..]
      82        79405 :     }
      83              : 
      84              :     /// The names that have a suffix starting with `prefix`, once per matching suffix, in index order
      85          257 :     pub fn search<'a>(&'a self, prefix: &'a [u8]) -> impl Iterator<Item = &'a IndexedName> + 'a {
      86          257 :         let suffixes = self.suffixes();
      87         1197 :         let begin = suffixes.partition_point(|&e| ci_cmp(self.suffix(e), prefix) == std::cmp::Ordering::Less);
      88          257 :         suffixes[begin..]
      89          257 :             .iter()
      90          624 :             .take_while(move |&&e| ci_starts_with(self.suffix(e), prefix))
      91          418 :             .map(move |&(name, _)| &self.names[name as usize])
      92          257 :     }
      93              : }