Line data    Source code

       1              : //! Attribute lookups over the children of an AST object.
       2              : //!
       3              : //! [`attrs!`](crate::attrs) fixes the keys at compile time, rejects duplicate keys during constant
       4              : //! evaluation, and then scans the children against the constant key array. LLVM vectorizes that
       5              : //! comparison, which measured faster than a static perfect hash table and than a direct-index table
       6              : //! for every object size of the grammar.
       7              : //!
       8              : //! Duplicate keys resolve differently by key count (see docs/design/core_quirks.md):
       9              : //! - with a single key, the first child with that key is returned,
      10              : //! - with several keys, the last child with each key is returned.
      11              : 
      12              : pub use dashql_buffers::parser::AttributeKey;
      13              : use dashql_buffers::parser::Node;
      14              : 
      15              : /// Copy constant keys into an array, rejecting duplicates (evaluated at compile time)
      16            0 : pub const fn key_array<const N: usize>(keys: &[AttributeKey]) -> [AttributeKey; N] {
      17            0 :     assert!(keys.len() == N);
      18            0 :     let mut out = [AttributeKey::NONE; N];
      19            0 :     let mut i = 0;
      20            0 :     while i < N {
      21            0 :         let mut j = i + 1;
      22            0 :         while j < N {
      23            0 :             assert!(keys[i].0 != keys[j].0, "duplicate attribute key");
      24            0 :             j += 1;
      25              :         }
      26            0 :         out[i] = keys[i];
      27            0 :         i += 1;
      28              :     }
      29            0 :     out
      30            0 : }
      31              : 
      32              : /// Find the last child with each key
      33              : #[inline(always)]
      34       155744 : pub fn lookup_last<'a, const N: usize>(children: &'a [Node], keys: &[AttributeKey; N]) -> [Option<&'a Node>; N] {
      35       155744 :     let mut out = [None; N];
      36       276690 :     for child in children {
      37       276690 :         let key = child.attribute_key();
      38      1520809 :         for (slot, k) in out.iter_mut().zip(keys.iter()) {
      39      1520809 :             if key == *k {
      40       262467 :                 *slot = Some(child);
      41      1258342 :             }
      42              :         }
      43              :     }
      44       155744 :     out
      45       155744 : }
      46              : 
      47              : /// Find the first child with a key
      48              : #[inline(always)]
      49        69019 : pub fn lookup_first(children: &[Node], key: AttributeKey) -> [Option<&Node>; 1] {
      50        76975 :     [children.iter().find(|c| c.attribute_key() == key)]
      51        69019 : }
      52              : 
      53              : /// Look up attributes in the children of an object: `attrs!(children, [KEY_A, KEY_B])` returns
      54              : /// `[Option<&Node>; 2]`.
      55              : ///
      56              : /// A single key returns the first child with that key, several keys the last child with each key.
      57              : /// The keys must be constant expressions.
      58              : #[macro_export]
      59              : macro_rules! attrs {
      60              :     ($children:expr, [$key:expr $(,)?] $(,)?) => {
      61              :         $crate::attributes::lookup_first($children, $key)
      62              :     };
      63              :     ($children:expr, [$($key:expr),+ $(,)?] $(,)?) => {{
      64              :         const KEY_LIST: &[$crate::attributes::AttributeKey] = &[$($key),+];
      65              :         const KEYS: [$crate::attributes::AttributeKey; KEY_LIST.len()] = $crate::attributes::key_array(KEY_LIST);
      66              :         $crate::attributes::lookup_last($children, &KEYS)
      67              :     }};
      68              : }
      69              : 
      70              : #[cfg(test)]
      71              : mod tests {
      72              :     use dashql_buffers::parser::{AttributeKey, Node, NodeType, SymbolSpan};
      73              : 
      74            6 :     fn node(key: AttributeKey, value: u32) -> Node {
      75            6 :         Node::new(&SymbolSpan::new(0, 0), NodeType::NONE, key, 0, value, 0)
      76            6 :     }
      77              : 
      78              :     #[test]
      79            1 :     fn single_key_finds_first() {
      80            1 :         let children = [node(AttributeKey::SQL_SELECT_FROM, 1), node(AttributeKey::SQL_SELECT_FROM, 2)];
      81            1 :         let [from] = attrs!(&children, [AttributeKey::SQL_SELECT_FROM]);
      82            1 :         assert_eq!(from.unwrap().children_begin_or_value(), 1);
      83            1 :     }
      84              : 
      85              :     #[test]
      86            1 :     fn several_keys_find_last() {
      87            1 :         let children = [
      88            1 :             node(AttributeKey::SQL_SELECT_FROM, 1),
      89            1 :             node(AttributeKey::SQL_SELECT_WHERE, 2),
      90            1 :             node(AttributeKey::SQL_SELECT_FROM, 3),
      91            1 :             node(AttributeKey::NONE, 4),
      92            1 :         ];
      93            1 :         let [from, where_, limit] = attrs!(
      94            1 :             &children,
      95              :             [AttributeKey::SQL_SELECT_FROM, AttributeKey::SQL_SELECT_WHERE, AttributeKey::SQL_SELECT_LIMIT]
      96              :         );
      97            1 :         assert_eq!(from.unwrap().children_begin_or_value(), 3);
      98            1 :         assert_eq!(where_.unwrap().children_begin_or_value(), 2);
      99            1 :         assert!(limit.is_none());
     100            1 :     }
     101              : }