yara_x/compiler/

rules.rs

use std::fmt;
use std::io::{BufWriter, Read, Write};
use std::ops::{Bound, RangeBounds};
use std::slice::Iter;
#[cfg(feature = "logging")]
use std::time::Instant;

use anyhow::anyhow;
use daachorse::DoubleArrayAhoCorasick;
#[cfg(feature = "logging")]
use log::*;
use regex_automata::meta::Regex;
use rustc_hash::FxHashMap;
use serde::{Deserialize, Deserializer, Serialize, Serializer};

use crate::compiler::atoms::Atom;
use crate::compiler::errors::SerializationError;
use crate::compiler::report::CodeLoc;
use crate::compiler::warnings::Warning;
use crate::compiler::{
    IdentId, Imports, LiteralId, NamespaceId, PatternId, RegexId, RegexSetId,
    RuleId, SubPattern, SubPatternId,
};
use crate::models::PatternKind;
use crate::re::{BckCodeLoc, FwdCodeLoc, RegexpAtom};
use crate::string_pool::{BStringPool, StringPool};
use crate::{Rule, re, teddy, types, wasm};

/// Magic bytes prepended to any binary file generated by YARA-X.
const MAGIC: &[u8] = b"YARA-X\0\0";

/// Version of the serialization format.
///
/// This version is incremented every time a change is made to the binary
/// format in a way that breaks backwards compatibility.
const SERIALIZATION_VERSION: u32 = 2;

/// Aho-Corasick automaton bundled with an optional Teddy scanner if the
/// number of patterns is low enough. If the Teddy scanner is present, and
/// the length of the scanned data allows it, the Teddy scanner is used
/// because it is faster. In all other cases, the Aho-Corasick automaton is
/// used.
pub(crate) struct AhoCorasick {
    pub(crate) daachorse: DoubleArrayAhoCorasick<u32>,
    pub(crate) teddy: Option<teddy::Searcher>,
}

/// A set of YARA rules in compiled form.
///
/// This is the result from [`crate::Compiler::build`].
#[derive(Serialize, Deserialize)]
pub struct Rules {
    /// Pool with identifiers used in the rules. Each identifier has its
    /// own [`IdentId`], which can be used for retrieving the identifier
    /// from the pool as a `&str`.
    pub(in crate::compiler) ident_pool: StringPool<IdentId>,

    /// Pool with the regular expressions used in the rules conditions. Each
    /// regular expression has its own [`RegexId`]. Regular expressions
    /// include the starting and ending slashes (`/`), and the modifiers
    /// `i` and `s` if present (e.g: `/foobar/`, `/foo/i`, `/bar/s`).
    pub(in crate::compiler) regex_pool: StringPool<RegexId>,

    /// If `true`, the regular expressions in `regex_pool` are allowed to
    /// contain invalid escape sequences.
    pub(in crate::compiler) relaxed_re_syntax: bool,

    /// Pool with literal strings used in the rules. Each literal has its
    /// own [`LiteralId`], which can be used for retrieving the literal
    /// string as `&BStr`.
    pub(in crate::compiler) lit_pool: BStringPool<LiteralId>,

    /// WASM module as in raw form.
    pub(in crate::compiler) wasm_mod: Vec<u8>,

    /// WASM module already compiled into native code for the current platform.
    /// When the rules are serialized, the compiled module is included only if
    /// the `native-code-serialization` is enabled.
    #[serde(
        serialize_with = "serialize_wasm_mod",
        deserialize_with = "deserialize_wasm_mod"
    )]
    pub(in crate::compiler) compiled_wasm_mod: Option<wasm::runtime::Module>,

    /// Vector with the names of all the imported modules. The vector contains
    /// the [`IdentId`] corresponding to the module's identifier.
    pub(in crate::compiler) imported_modules: Vec<IdentId>,

    /// Vector containing all the compiled rules. A [`RuleId`] is an index
    /// in this vector.
    pub(in crate::compiler) rules: Vec<RuleInfo>,

    /// Total number of patterns across all rules. This is equal to the last
    /// [`PatternId`] +  1.
    pub(in crate::compiler) num_patterns: usize,

    /// Vector with all the sub-patterns from all rules. A [`SubPatternId`]
    /// is an index in this vector. Each pattern is composed of one or more
    /// sub-patterns, if any of the sub-patterns matches, the pattern matches.
    ///
    /// For example, when a text pattern is accompanied by both the `ascii`
    /// and `wide` modifiers, two sub-patterns are generated for it: one for
    /// the ascii variant, and the other for the wide variant.
    ///
    /// Each sub-pattern in this vector is accompanied by the [`PatternId`]
    /// where the sub-pattern belongs to.
    pub(in crate::compiler) sub_patterns: Vec<(PatternId, SubPattern)>,

    /// Map that associates a `PatternId` to a certain file size bound.
    ///
    /// A condition like `filesize < 1000 and $a` only matches if `filesize`
    /// is less than 1000. Therefore, the pattern `$a` does not need be
    /// checked for files of size 1000 bytes or larger.
    ///
    /// In this case, the map will contain an entry associating `$a` to a
    /// `FilesizeBounds` value like:
    ///
    /// `FilesizeBounds{start: Bound::Unbounded, end: Bound:Excluded(1000)}`.
    pub(in crate::compiler) filesize_bounds:
        FxHashMap<PatternId, FilesizeBounds>,

    /// Map that associates a `PatternId` to a certain constraint on the
    /// file header (e.g. magic bytes at offset 0), if any.
    ///
    /// A condition like `uint16(0) == 0x5A4D and $a` or `$mz at 0 and $a`
    /// (where $mz = "MZ") only matches if the file starts with "MZ" (0x5A4D).
    /// In this case, the map will contain an entry associating `$a` to a
    /// `HeaderConstraint` that requires the file to start with those two
    /// bytes.
    ///
    /// This allows skipping pattern checks entirely if the scanned data
    /// doesn't start with the expected header prefix.
    pub(in crate::compiler) header_constraints:
        FxHashMap<PatternId, HeaderConstraint>,

    /// Vector that contains the [`SubPatternId`] for sub-patterns that can
    /// match only at a fixed offset within the scanned data. These sub-patterns
    /// are not added to the Aho-Corasick automaton.
    pub(in crate::compiler) anchored_sub_patterns: Vec<SubPatternId>,

    /// A vector that contains all the atoms extracted from the patterns. Each
    /// atom has an associated [`SubPatternId`] that indicates the sub-pattern
    /// it belongs to.
    pub(in crate::compiler) atoms: Vec<SubPatternAtom>,

    /// A vector that contains the code for all regexp patterns (this includes
    /// hex patterns which are just a special case of regexp). The code for
    /// each regexp is appended to the vector, during the compilation process
    /// and the atoms extracted from the regexp contain offsets within this
    /// vector. This vector contains both forward and backward code.
    pub(in crate::compiler) re_code: Vec<u8>,

    /// A [`types::Struct`] in serialized form that contains all the global
    /// variables. Each field in the structure corresponds to a global variable
    /// defined at compile time using [`crate::compiler::Compiler`].
    pub(in crate::compiler) serialized_globals: Vec<u8>,

    /// Aho-Corasick automaton containing the atoms extracted from the patterns.
    /// This allows to search for all the atoms in the scanned data at the same
    /// time in an efficient manner. The automaton is not serialized during when
    /// [`Rules::serialize`] is called, it needs to be wrapped in [`Option`] so
    /// that we can use `#[serde(skip)]` on it because [`AhoCorasick`] doesn't
    /// implement the [`Default`] trait.
    #[serde(skip)]
    pub(in crate::compiler) ac: Option<AhoCorasick>,

    /// Warnings that were produced while compiling these rules. These warnings
    /// are not serialized, rules that are obtained by deserializing previously
    /// serialized rules won't have any warnings.
    #[serde(skip)]
    pub(in crate::compiler) warnings: Vec<Warning>,

    /// Grouped `RegexSet` persistent definitions.
    ///
    /// Populated during `Compiler::build`, each entry maps a unique
    /// `RegexSetId` to an ordered list of `RegexpId`s. All regular
    /// expressions in a given set match the exact same target expression
    /// in the source code, allowing them to be compiled into a unified
    /// set automata for single-pass evaluation.
    pub(in crate::compiler) regex_sets: FxHashMap<RegexSetId, Vec<RegexId>>,

    /// BitVec where the N-th bit indicates whether the pattern with
    /// PatternId = N is a fast-scan pattern.
    ///
    /// A pattern can be fast-scanned if its occurrences are only evaluated
    /// as simple boolean checks (e.g. `$a`), meaning the scanner can stop
    /// tracking matches for it once the first match has been found. If a
    /// pattern is used in a context that requires tracking all matches (such
    /// as count `#a`, offset `@a`, length `!a`, anchored checks, or loop
    /// equivalents), it cannot be fast-scanned.
    pub(in crate::compiler) fast_scan_patterns: bitvec::vec::BitVec,
}

impl Rules {
    /// An iterator that yields the name of the modules imported by the
    /// rules.
    pub fn imports(&self) -> Imports<'_> {
        Imports {
            iter: self.imported_modules.iter(),
            ident_pool: &self.ident_pool,
        }
    }

    /// Warnings produced while compiling these rules.
    pub fn warnings(&self) -> &[Warning] {
        self.warnings.as_slice()
    }

    /// Serializes the rules as a sequence of bytes.
    ///
    /// The [`Rules`] can be restored back by passing the bytes to
    /// [`Rules::deserialize`].
    pub fn serialize(&self) -> Result<Vec<u8>, SerializationError> {
        let mut bytes = Vec::new();
        self.serialize_into(&mut bytes)?;
        Ok(bytes)
    }

    /// Deserializes the rules from a sequence of bytes produced by
    /// [`Rules::serialize`].
    ///
    /// # Safety
    ///
    /// As long as you are deserializing rules from binary content produced
    /// by [`Rules::serialize`] you are safe. But you should never attempt
    /// to do so from binary content that was produced or could be manipulated
    /// by a third party. This implies a security risk and your program may
    /// panic during scanning.
    pub fn deserialize<B>(bytes: B) -> Result<Self, SerializationError>
    where
        B: AsRef<[u8]>,
    {
        let bytes = bytes.as_ref();
        let version_offset = MAGIC.len();
        let data_offset = version_offset + size_of::<u32>();

        if bytes.len() < data_offset || &bytes[0..version_offset] != MAGIC {
            return Err(SerializationError::InvalidFormat);
        }

        let version = u32::from_le_bytes(
            bytes[version_offset..data_offset].try_into().unwrap(),
        );

        if version != SERIALIZATION_VERSION {
            return Err(SerializationError::InvalidVersion {
                expected: SERIALIZATION_VERSION,
                actual: version,
            });
        }

        #[cfg(feature = "logging")]
        let start = Instant::now();

        // Skip the header and deserialize the remaining data.
        let (mut rules, _len): (Self, usize) =
            bincode::serde::decode_from_slice(
                &bytes[data_offset..],
                bincode::config::standard(),
            )?;

        #[cfg(feature = "logging")]
        info!("Deserialization time: {:?}", Instant::elapsed(&start));

        // `rules.compiled_wasm_mod` can be `None` for two reasons:
        //
        //  1- The rules were serialized without compiled rules (i.e: the
        //     `native-code-serialization` feature was disabled, which is
        //     the default).
        //
        //  2- The rules were serialized with compiled rules, but they were
        //     compiled for a different platform, and `deserialize_wasm_mod`
        //     returned `None`.
        //
        // In both cases we try to build the module again from the data in
        // `rules.wasm_mode`.
        if rules.compiled_wasm_mod.is_none() {
            #[cfg(feature = "logging")]
            let start = Instant::now();

            rules.compiled_wasm_mod = Some(
                wasm::runtime::Module::from_binary(
                    wasm::get_engine(),
                    rules.wasm_mod.as_slice(),
                )
                .map_err(|e| SerializationError::from(anyhow!(e)))?,
            );

            #[cfg(feature = "logging")]
            info!("WASM build time: {:?}", Instant::elapsed(&start));
        }

        rules.build_ac_automaton();

        // Make sure that the maximum SubPatternId is within the boundaries
        // of sub_patterns array. This check is important because during
        // the scanning phase we use SubPatternId as indexes in the array
        // without boundary checks for better performance.
        let max_sub_pattern_id = rules
            .atoms
            .iter()
            .map(|atom| atom.sub_pattern_id)
            .max()
            .unwrap_or(SubPatternId(0));

        if rules.sub_patterns.len() < max_sub_pattern_id.0 as usize {
            return Err(SerializationError::InvalidFormat);
        }

        Ok(rules)
    }

    /// Serializes the rules into a `writer`.
    pub fn serialize_into<W>(
        &self,
        writer: W,
    ) -> Result<(), SerializationError>
    where
        W: Write,
    {
        let mut writer = BufWriter::new(writer);

        // Write file header.
        writer.write_all(MAGIC)?;

        // Write version.
        writer.write_all(&SERIALIZATION_VERSION.to_le_bytes())?;

        bincode::serde::encode_into_std_write(
            self,
            &mut writer,
            bincode::config::standard(),
        )?;

        Ok(())
    }

    /// Deserializes the rules from a `reader`.
    pub fn deserialize_from<R>(
        mut reader: R,
    ) -> Result<Self, SerializationError>
    where
        R: Read,
    {
        let mut bytes = Vec::new();
        let _ = reader.read_to_end(&mut bytes)?;
        Self::deserialize(bytes)
    }

    /// Returns an iterator that yields the compiled rules.
    ///
    /// ```rust
    /// # use yara_x::Compiler;
    /// let mut compiler = Compiler::new();
    ///
    /// assert!(compiler
    ///     .add_source("rule foo {condition: true}")
    ///     .unwrap()
    ///     .add_source("rule bar {condition: true}")
    ///     .is_ok());
    ///
    /// let rules = compiler.build();
    /// let mut iter = rules.iter();
    ///
    /// assert_eq!(iter.len(), 2);
    /// assert_eq!(iter.next().map(|r| r.identifier()), Some("foo"));
    /// assert_eq!(iter.next().map(|r| r.identifier()), Some("bar"));
    /// ```
    pub fn iter(&self) -> RulesIter<'_> {
        RulesIter { rules: self, iterator: self.rules.iter() }
    }

    /// Returns a [`RuleInfo`] given its [`RuleId`].
    ///
    /// # Panics
    ///
    /// If no rule with such [`RuleId`] exists.
    pub(crate) fn get(&self, rule_id: RuleId) -> &RuleInfo {
        self.rules.get(rule_id.0 as usize).unwrap()
    }

    /// Returns a regular expression by [`RegexId`].
    ///
    /// # Panics
    ///
    /// If no regular expression with such [`RegexId`] exists.
    #[inline]
    pub(crate) fn get_regexp(&self, regexp_id: RegexId) -> Regex {
        let re = types::Regexp::new(self.regex_pool.get(regexp_id).unwrap());

        let parser = re::parser::Parser::new()
            .relaxed_re_syntax(self.relaxed_re_syntax);

        let hir = parser.parse(&re).unwrap().into_inner();

        // Set a size limit for the NFA automata. The default limit (10MB) is
        // too small for certain regexps seen in YARA rules in the wild, see:
        // https://github.com/VirusTotal/yara-x/issues/85
        let config = regex_automata::meta::Config::new()
            .nfa_size_limit(Some(50 * 1024 * 1024));

        regex_automata::meta::Builder::new()
            .configure(config)
            .build_from_hir(&hir)
            .unwrap_or_else(|err| {
                panic!("error compiling regex `{}`: {:#?}", re.as_str(), err)
            })
    }

    /// Returns a compiled multi-pattern `RegexSet` for a given `RegexSetId`.
    #[inline]
    pub(crate) fn get_regex_set(
        &self,
        set_id: RegexSetId,
    ) -> regex::bytes::RegexSet {
        let re_ids = self.regex_sets.get(&set_id).unwrap();
        let mut patterns = Vec::with_capacity(re_ids.len());

        for &re_id in re_ids {
            let re = types::Regexp::new(self.regex_pool.get(re_id).unwrap());
            let parser = re::parser::Parser::new()
                .relaxed_re_syntax(self.relaxed_re_syntax);
            let hir = parser.parse(&re).unwrap().into_inner();
            patterns.push(hir.to_string());
        }

        regex::bytes::RegexSetBuilder::new(patterns)
            .size_limit(1024 * 1024 * 1024)
            .build()
            .unwrap_or_else(|err| {
                panic!("error compiling RegexSet: {:#?}", err)
            })
    }

    /// Returns a sub-pattern by [`SubPatternId`].
    #[inline]
    pub(crate) fn get_sub_pattern(
        &self,
        sub_pattern_id: SubPatternId,
    ) -> &(PatternId, SubPattern) {
        unsafe { self.sub_patterns.get_unchecked(sub_pattern_id.0 as usize) }
    }

    /// Given a [`SubPatternId`], returns the [`RuleId`] corresponding to the
    /// rule that contains the sub-pattern, and the [`IdentId`] for the pattern's
    /// identifier.
    ///
    /// This operation is slow, because it implies iterating over all the rules
    /// and their sub-patterns until finding the one we are looking for.
    #[cfg(feature = "logging")]
    pub(crate) fn get_rule_and_pattern_by_sub_pattern_id(
        &self,
        sub_pattern_id: SubPatternId,
    ) -> Option<(RuleId, IdentId)> {
        let (target_pattern_id, _) = self.get_sub_pattern(sub_pattern_id);
        for (rule_id, rule) in self.rules.iter().enumerate() {
            for p in &rule.patterns {
                if p.pattern_id == *target_pattern_id {
                    return Some((rule_id.into(), p.ident_id));
                };
            }
        }
        None
    }

    #[cfg(feature = "rules-profiling")]
    #[inline]
    pub(crate) fn rules(&self) -> &[RuleInfo] {
        self.rules.as_slice()
    }

    #[inline]
    pub(crate) fn atoms(&self) -> &[SubPatternAtom] {
        self.atoms.as_slice()
    }

    #[inline]
    pub(crate) fn anchored_sub_patterns(&self) -> &[SubPatternId] {
        self.anchored_sub_patterns.as_slice()
    }

    #[inline]
    pub(crate) fn re_code(&self) -> &[u8] {
        self.re_code.as_slice()
    }

    #[inline]
    pub(crate) fn num_rules(&self) -> usize {
        self.rules.len()
    }

    #[inline]
    pub(crate) fn num_patterns(&self) -> usize {
        self.num_patterns
    }

    /// Returns the Aho-Corasick automaton that allows to search for pattern
    /// atoms.
    #[inline]
    pub(crate) fn ac_automaton(&self) -> &AhoCorasick {
        self.ac.as_ref().expect("Aho-Corasick automaton not compiled")
    }

    pub(crate) fn build_ac_automaton(&mut self) {
        if self.ac.is_some() {
            return;
        }

        #[cfg(feature = "logging")]
        let start = Instant::now();

        #[cfg(feature = "logging")]
        let mut num_atoms = [0_usize; 6];

        #[cfg(feature = "logging")]
        for x in &self.atoms {
            match x.atom.len() {
                atom_len @ 0..=4 => num_atoms[atom_len] += 1,
                _ => num_atoms[num_atoms.len() - 1] += 1,
            }

            if x.atom.len() < 2 {
                let (rule_id, pattern_ident_id) = self
                    .get_rule_and_pattern_by_sub_pattern_id(x.sub_pattern_id)
                    .unwrap();

                let rule = self.get(rule_id);

                info!(
                    "Very short atom in pattern `{}` in rule `{}:{}` (length: {})",
                    self.ident_pool.get(pattern_ident_id).unwrap(),
                    self.ident_pool.get(rule.namespace_ident_id).unwrap(),
                    self.ident_pool.get(rule.ident_id).unwrap(),
                    x.atom.len()
                );
            }
        }

        // The Teddy algorithm can't be used in all cases. It will be used if:
        // - The number of atoms is between 1 and 64.
        // - None of the atoms is empty.
        let use_teddy = self.atoms.len() <= 64
            && !self.atoms.is_empty()
            && !self.atoms.iter().any(|x| x.atom.as_ref().is_empty());

        let teddy_searcher = if use_teddy {
            let mut teddy_builder = teddy::Builder::new();
            self.atoms.iter().for_each(|x| teddy_builder.add(x.atom.as_ref()));
            teddy_builder.build()
        } else {
            None
        };

        let atoms = self.atoms.iter().map(|x| x.atom.as_ref());
        let ac = DoubleArrayAhoCorasick::new(atoms)
            .expect("failed to build Aho-Corasick automaton");

        self.ac = Some(AhoCorasick { daachorse: ac, teddy: teddy_searcher });

        #[cfg(feature = "logging")]
        {
            info!(
                "Aho-Corasick automaton build time: {:?}",
                Instant::elapsed(&start)
            );

            info!("Number of rules: {}", self.num_rules());
            info!("Number of patterns: {}", self.num_patterns());
            info!(
                "Number of anchored sub-patterns: {}",
                self.anchored_sub_patterns.len()
            );
            info!("Number of atoms: {}", self.atoms.len());
            info!("Atoms with len = 0: {}", num_atoms[0]);
            info!("Atoms with len = 1: {}", num_atoms[1]);
            info!("Atoms with len = 2: {}", num_atoms[2]);
            info!("Atoms with len = 3: {}", num_atoms[3]);
            info!("Atoms with len = 4: {}", num_atoms[4]);
            info!("Atoms with len > 4: {}", num_atoms[5]);
        }
    }

    #[inline]
    pub(crate) fn lit_pool(&self) -> &BStringPool<LiteralId> {
        &self.lit_pool
    }

    #[inline]
    pub(crate) fn ident_pool(&self) -> &StringPool<IdentId> {
        &self.ident_pool
    }

    #[inline]
    pub(crate) fn globals(&self) -> types::Struct {
        let (globals, _): (types::Struct, usize) =
            bincode::serde::decode_from_slice(
                self.serialized_globals.as_slice(),
                bincode::config::standard(),
            )
            .expect("error deserializing global variables");
        globals
    }

    #[inline]
    pub(crate) fn wasm_mod(&self) -> &wasm::runtime::Module {
        self.compiled_wasm_mod.as_ref().unwrap()
    }

    #[inline]
    pub(crate) fn filesize_bounds(
        &self,
        pattern_id: PatternId,
    ) -> Option<&FilesizeBounds> {
        self.filesize_bounds.get(&pattern_id)
    }

    #[inline]
    pub(crate) fn header_constraints(
        &self,
        pattern_id: PatternId,
    ) -> Option<&HeaderConstraint> {
        self.header_constraints.get(&pattern_id)
    }

    #[inline]
    pub(crate) fn is_fast_scan(&self, pattern_id: PatternId) -> bool {
        *self.fast_scan_patterns.get(usize::from(pattern_id)).unwrap()
    }
}

#[cfg(feature = "native-code-serialization")]
fn serialize_wasm_mod<S>(
    wasm_mod: &Option<wasm::runtime::Module>,
    serializer: S,
) -> Result<S::Ok, S::Error>
where
    S: Serializer,
{
    if let Some(wasm_mod) = wasm_mod {
        let bytes = wasm_mod
            .serialize()
            .map_err(|err| serde::ser::Error::custom(err.to_string()))?;

        serializer.serialize_some(bytes.as_slice())
    } else {
        serializer.serialize_none()
    }
}

#[cfg(not(feature = "native-code-serialization"))]
fn serialize_wasm_mod<S>(
    _wasm_mod: &Option<wasm::runtime::Module>,
    serializer: S,
) -> Result<S::Ok, S::Error>
where
    S: Serializer,
{
    serializer.serialize_none()
}

pub fn deserialize_wasm_mod<'de, D>(
    deserializer: D,
) -> Result<Option<wasm::runtime::Module>, D::Error>
where
    D: Deserializer<'de>,
{
    let bytes: Option<&[u8]> = Deserialize::deserialize(deserializer)?;
    let module = if let Some(bytes) = bytes {
        wasm::runtime::Module::deserialize(wasm::get_engine(), bytes).ok()
    } else {
        None
    };

    Ok(module)
}

/// Iterator that yields the of the compiled rules.
pub struct RulesIter<'a> {
    rules: &'a Rules,
    iterator: Iter<'a, RuleInfo>,
}

impl<'a> Iterator for RulesIter<'a> {
    type Item = Rule<'a, 'a>;

    fn next(&mut self) -> Option<Self::Item> {
        Some(Rule {
            ctx: None,
            rules: self.rules,
            rule_info: self.iterator.next()?,
        })
    }
}

impl ExactSizeIterator for RulesIter<'_> {
    #[inline]
    fn len(&self) -> usize {
        self.iterator.len()
    }
}

impl fmt::Debug for Rules {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for (id, rule) in self.rules.iter().enumerate() {
            let name = self.ident_pool.get(rule.ident_id).unwrap();
            let namespace =
                self.ident_pool.get(rule.namespace_ident_id).unwrap();
            writeln!(f, "RuleId({id})")?;
            writeln!(f, "  namespace: {namespace}")?;
            writeln!(f, "  name: {name}")?;
            writeln!(f, "  patterns:")?;
            for pattern in &rule.patterns {
                let ident = self.ident_pool.get(pattern.ident_id).unwrap();
                writeln!(f, "    {:?} {ident} ", pattern.pattern_id)?;
            }
        }

        for (id, (pattern_id, _)) in self.sub_patterns.iter().enumerate() {
            writeln!(f, "SubPatternId({id}) -> {pattern_id:?}")?;
        }

        Ok(())
    }
}

/// Metadata values.
#[derive(Serialize, Deserialize)]
pub(crate) enum MetaValue {
    Bool(bool),
    Integer(i64),
    Float(f64),
    String(LiteralId),
    Bytes(LiteralId),
}

/// Information about each of the individual rules included in [`Rules`].
#[derive(Serialize, Deserialize)]
pub(crate) struct RuleInfo {
    /// The ID of the namespace the rule belongs to.
    pub namespace_id: NamespaceId,
    /// The ID of the rule namespace in the identifiers pool.
    pub namespace_ident_id: IdentId,
    /// The ID of the rule identifier in the identifiers pool.
    pub ident_id: IdentId,
    /// Tags associated to the rule.
    pub tags: Vec<IdentId>,
    /// Reference to the rule identifier in the source code. This field is
    /// ignored while serializing and deserializing compiles rules, as it
    /// is used only during the compilation phase, but not during the scan
    /// phase.
    #[serde(skip)]
    pub ident_ref: CodeLoc,
    /// Metadata associated to the rule.
    pub metadata: Vec<(IdentId, MetaValue)>,
    /// Vector with all the patterns defined by this rule. The bool in the
    /// tuple indicates if the pattern is private.
    pub patterns: Vec<PatternInfo>,
    /// Number of private patterns in the rule. The number of non-private
    /// patterns can be computed as patterns.len - num_private_patterns.
    pub num_private_patterns: usize,
    /// True if the rule is global.
    pub is_global: bool,
    /// True if the rule is private.
    pub is_private: bool,
}

/// Information about each of pattern in a rule.
#[derive(Serialize, Deserialize)]
pub(crate) struct PatternInfo {
    /// Unique ID for this pattern.
    pub pattern_id: PatternId,
    /// The pattern identifier.
    pub ident_id: IdentId,
    /// Indicates if the pattern is text, hex or regexp.
    pub kind: PatternKind,
    /// True if the pattern is private.
    pub is_private: bool,
}

/// Describes the bounds for `filesize` imposed by a rule condition.
///
/// For example, the condition `filesize < 1000 and $a` only matches files
/// smaller than 10MB. That would be represented by:
///
/// ```text
/// FilesizeBounds { start: Bound::Unbounded, end: Bound::Excluded(1000) }
/// ```
///
/// In contrast, the condition `filesize < 1000 or $a` does not any bounds
/// to `filesize`, since the use of `or` allows files larger than
/// 10MB to also match. This case is represented by:
///
/// ```text
/// FilesizeBounds { start: Bound::Unbounded, end: Bound::Unbounded }
/// ```
#[derive(Debug, PartialEq, Serialize, Deserialize, Clone, Hash, Eq)]
pub(crate) struct FilesizeBounds {
    start: Bound<i64>,
    end: Bound<i64>,
}

impl Default for FilesizeBounds {
    fn default() -> Self {
        Self { start: Bound::Unbounded, end: Bound::Unbounded }
    }
}

impl<T: RangeBounds<i64>> From<T> for FilesizeBounds {
    fn from(value: T) -> Self {
        Self {
            start: value.start_bound().cloned(),
            end: value.end_bound().cloned(),
        }
    }
}

impl FilesizeBounds {
    pub fn unbounded(&self) -> bool {
        matches!(self.start, Bound::Unbounded)
            && matches!(self.end, Bound::Unbounded)
    }

    pub fn contains(&self, value: i64) -> bool {
        let start_ok = match self.start {
            Bound::Included(start) => value >= start,
            Bound::Excluded(start) => value > start,
            Bound::Unbounded => true,
        };

        let end_ok = match self.end {
            Bound::Included(end) => value <= end,
            Bound::Excluded(end) => value < end,
            Bound::Unbounded => true,
        };

        start_ok && end_ok
    }
    pub fn max_start(&mut self, bound: Bound<i64>) -> &mut Self {
        match (&self.start, &bound) {
            (Bound::Included(current), Bound::Included(new)) => {
                if new > current {
                    self.start = Bound::Included(*new);
                }
            }
            (Bound::Included(current), Bound::Excluded(new)) => {
                if new >= current {
                    self.start = Bound::Excluded(*new);
                }
            }
            (Bound::Excluded(current), Bound::Included(new)) => {
                if new > current {
                    self.start = Bound::Included(*new);
                }
            }
            (Bound::Excluded(current), Bound::Excluded(new)) => {
                if new > current {
                    self.start = Bound::Excluded(*new);
                }
            }
            (Bound::Unbounded, new) => {
                self.start = *new;
            }
            (_, Bound::Unbounded) => {}
        }
        self
    }

    pub fn min_end(&mut self, bound: Bound<i64>) -> &mut Self {
        match (&self.end, &bound) {
            (Bound::Included(current), Bound::Included(new)) => {
                if new < current {
                    self.end = Bound::Included(*new);
                }
            }
            (Bound::Included(current), Bound::Excluded(new)) => {
                if new <= current {
                    self.end = Bound::Excluded(*new);
                }
            }
            (Bound::Excluded(current), Bound::Included(new)) => {
                if new < current {
                    self.end = Bound::Included(*new);
                }
            }
            (Bound::Excluded(current), Bound::Excluded(new)) => {
                if new < current {
                    self.end = Bound::Excluded(*new)
                }
            }
            (Bound::Unbounded, new) => {
                self.end = *new;
            }
            (_, Bound::Unbounded) => {}
        }
        self
    }
}

/// Describes the requirements on the file header imposed by a rule condition.
///
/// For example, the condition `uint32(0) == 0x464c457f` requires that the first
/// 4 bytes of the file are `0x7f, 0x45, 0x4c, 0x46`.
#[derive(
    Debug, PartialEq, Serialize, Deserialize, Clone, Hash, Eq, Default,
)]
pub(crate) enum HeaderConstraint {
    #[default]
    Unconstrained,
    Unsatisfiable,
    Constrained(Vec<u8>),
}

impl HeaderConstraint {
    pub fn unconstrained(&self) -> bool {
        matches!(self, Self::Unconstrained)
    }

    pub fn is_satisfied(&self, data: &[u8]) -> bool {
        match self {
            Self::Unconstrained => true,
            Self::Unsatisfiable => false,
            Self::Constrained(bytes) => data.starts_with(bytes),
        }
    }
}

/// Represents an atom extracted from a pattern and added to the Aho-Corasick
/// automata.
///
/// Each time the Aho-Corasick finds one of these atoms, it proceeds to verify
/// if the corresponding sub-pattern actually matches or not. The verification
/// process depend on the type of sub-pattern.
#[derive(Serialize, Deserialize)]
pub(crate) struct SubPatternAtom {
    /// The [`SubPatternId`] that identifies the sub-pattern this atom
    /// belongs to.
    sub_pattern_id: SubPatternId,
    /// The atom itself.
    atom: Atom,
    /// The index within `re_code` where the forward code for this atom starts.
    fwd_code: Option<FwdCodeLoc>,
    /// The index within `re_code` where the backward code for this atom starts.
    bck_code: Option<BckCodeLoc>,
}

impl SubPatternAtom {
    #[inline]
    pub(crate) fn from_atom(sub_pattern_id: SubPatternId, atom: Atom) -> Self {
        Self { sub_pattern_id, atom, bck_code: None, fwd_code: None }
    }

    pub(crate) fn from_regexp_atom(
        sub_pattern_id: SubPatternId,
        value: RegexpAtom,
    ) -> Self {
        Self {
            sub_pattern_id,
            atom: value.atom,
            fwd_code: value.fwd_code,
            bck_code: value.bck_code,
        }
    }

    #[inline]
    pub(crate) fn sub_pattern_id(&self) -> SubPatternId {
        self.sub_pattern_id
    }

    #[cfg(feature = "exact-atoms")]
    #[inline]
    pub(crate) fn is_exact(&self) -> bool {
        self.atom.is_exact()
    }

    #[inline]
    pub(crate) fn len(&self) -> usize {
        self.atom.len()
    }

    #[inline]
    pub(crate) fn backtrack(&self) -> usize {
        self.atom.backtrack() as usize
    }

    #[inline]
    pub(crate) fn as_slice(&self) -> &[u8] {
        self.atom.as_ref()
    }

    #[inline]
    pub(crate) fn fwd_code(&self) -> Option<FwdCodeLoc> {
        self.fwd_code
    }

    #[inline]
    pub(crate) fn bck_code(&self) -> Option<BckCodeLoc> {
        self.bck_code
    }
}