patina_internal_core 22.2.0

//! UEFI Dependency Expression (DEPEX) support
//!
//! This module provides a parser and evaluator for UEFI dependency expressions.
//!
//! ## License
//!
//! Copyright (c) Microsoft Corporation.
//!
//! SPDX-License-Identifier: Apache-2.0
//!
use alloc::{
    format,
    string::{String, ToString},
    vec::Vec,
};
use core::mem;
use r_efi::efi;
use uuid::Uuid;

/// The size of a GUID in bytes
const GUID_SIZE: usize = mem::size_of::<r_efi::efi::Guid>();

/// The initial size of the dependency expression stack in bytes
const DEPEX_STACK_SIZE_INCREMENT: usize = 0x100;

/// A UEFI dependency expression (DEPEX) opcode
#[derive(Debug, Clone, PartialEq)]
pub enum Opcode {
    /// If present, this must be the first and only opcode,
    /// may be used by DXE and SMM drivers.
    Before(Uuid),
    /// If present, this must be the first and only opcode,
    /// may be used by DXE and SMM drivers.
    After(Uuid),
    /// A Push opcode is followed by a GUID.
    Push(Uuid, bool),
    /// A logical AND operation of the two operands on the top
    /// of the stack.
    And,
    /// A logical OR operation of the two operands on the top
    /// of the stack.
    Or,
    /// A logical NOT operation of the operand on the top of
    /// the stack.
    Not,
    /// Pushes a true value onto the stack.
    True,
    /// Pushes a false value onto the stack.
    False,
    /// The End opcode is the last opcode in the expression.
    End,
    /// If present, this must be the first opcode in the expression.
    /// Used to schedule on request.
    Sor,
    /// An unknown opcode. Indicates an unrecognized opcode
    /// that should be treated as an error during evaluation.
    Unknown,
    /// A known opcode with an unexpected payload length.
    Malformed {
        /// The unhandled opcode value.
        opcode: u8,
        /// The length of the payload sent with the opcode.
        len: usize,
    },
}

/// Converts a UUID to an EFI GUID.
fn guid_from_uuid(uuid: &Uuid) -> Option<efi::Guid> {
    let fields = uuid.as_fields();
    let node = &fields.3[2..].try_into().ok()?;
    Some(efi::Guid::from_fields(fields.0, fields.1, fields.2, fields.3[0], fields.3[1], node))
}

/// Converts a byte slice to a GUID.
fn uuid_from_slice(slice: Option<&[u8]>) -> Option<Uuid> {
    Uuid::from_slice_le(slice?).ok()
}

impl<'a> From<&'a [u8]> for Opcode {
    /// Creates an Opcode from a byte slice.
    fn from(bytes: &'a [u8]) -> Self {
        let Some(&first_byte) = bytes.first() else {
            return Opcode::Unknown;
        };
        match first_byte {
            0x00 => match uuid_from_slice(bytes.get(1..GUID_SIZE + 1)) {
                Some(uuid) => Opcode::Before(uuid),
                None => Opcode::Malformed { opcode: 0x00, len: bytes.len() - 1 },
            },
            0x01 => match uuid_from_slice(bytes.get(1..GUID_SIZE + 1)) {
                Some(uuid) => Opcode::After(uuid),
                None => Opcode::Malformed { opcode: 0x01, len: bytes.len() - 1 },
            },
            0x02 => match uuid_from_slice(bytes.get(1..GUID_SIZE + 1)) {
                Some(uuid) => Opcode::Push(uuid, false),
                None => Opcode::Malformed { opcode: 0x02, len: bytes.len() - 1 },
            },
            0x03 => Opcode::And,
            0x04 => Opcode::Or,
            0x05 => Opcode::Not,
            0x06 => Opcode::True,
            0x07 => Opcode::False,
            0x08 => Opcode::End,
            0x09 => Opcode::Sor,
            _ => Opcode::Unknown,
        }
    }
}

impl Opcode {
    fn byte_size(&self) -> usize {
        match *self {
            Opcode::Before(_) | Opcode::After(_) | Opcode::Push(_, _) => 1 + GUID_SIZE,
            _ => 1,
        }
    }
}

/// Represents an associated dependency, where one guid must execute before or after another guid.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum AssociatedDependency {
    /// Indicates that the associated guid must be executed before the guid in the enum.
    Before(efi::Guid),
    /// Indicates that the associated guid must be executed after the guid in the enum.
    After(efi::Guid),
}

#[derive(Debug)]
/// A UEFI dependency expression (DEPEX)
pub struct Depex {
    expression: Vec<Opcode>,
}

impl From<&[u8]> for Depex {
    fn from(value: &[u8]) -> Self {
        let depex_parser = DepexParser::new(value);
        Self { expression: depex_parser.into_iter().collect() }
    }
}

impl From<Vec<u8>> for Depex {
    fn from(value: Vec<u8>) -> Self {
        Self::from(value.as_slice())
    }
}

impl From<&[Opcode]> for Depex {
    fn from(value: &[Opcode]) -> Self {
        Self { expression: value.to_vec() }
    }
}

impl Depex {
    /// Evaluates a DEPEX expression.
    pub fn eval(&mut self, protocols: &[efi::Guid]) -> bool {
        let mut stack = Vec::with_capacity(DEPEX_STACK_SIZE_INCREMENT);
        log::trace!("Depex:");
        for (index, opcode) in self.expression.iter_mut().enumerate() {
            match opcode {
                Opcode::Before(_) | Opcode::After(_) => {
                    log::trace!("  {opcode:#x?}");
                    if index != 0 {
                        debug_assert!(false, "Invalid BEFORE or AFTER not at start of depex {:#x?}", self.expression);
                        return false;
                    }

                    if self.expression.len() > 2 {
                        debug_assert!(
                            false,
                            "Invalid BEFORE or AFTER with additional opcodes {:#x?}.",
                            self.expression
                        );
                        return false;
                    }

                    if self.expression.len() == 2 && self.expression.get(1) != Some(&Opcode::End) {
                        debug_assert!(
                            false,
                            "Invalid BEFORE or AFTER with additional opcodes {:#x?}.",
                            self.expression
                        );
                        return false;
                    }
                    return false;
                }
                Opcode::Sor => {
                    log::trace!("  {opcode:#x?}");
                    if index != 0 {
                        debug_assert!(false, "Invalid SOR not at start of depex.");
                        return false;
                    }
                    return false;
                }
                Opcode::Push(guid, present) => {
                    if *present {
                        stack.push(true)
                    } else {
                        if let Some(guid) = guid_from_uuid(guid)
                            && protocols.contains(&guid)
                        {
                            *present = true;
                            stack.push(true);
                            continue;
                        }
                        stack.push(false);
                    }
                    log::trace!(
                        "  {opcode:x?} => {:?}, stack ->{:?}",
                        stack.last(),
                        stack.iter().rev().collect::<Vec<_>>()
                    );
                }
                Opcode::And => {
                    let operator1 = stack.pop().unwrap_or(false);
                    let operator2 = stack.pop().unwrap_or(false);
                    stack.push(operator1 && operator2);
                    log::trace!(
                        "  {opcode:x?}({operator1:?},{operator2:?}) => {:?}, stack ->{:?}",
                        stack.last(),
                        stack.iter().rev().collect::<Vec<_>>()
                    );
                }
                Opcode::Or => {
                    let operator1 = stack.pop().unwrap_or(false);
                    let operator2 = stack.pop().unwrap_or(false);
                    stack.push(operator1 || operator2);
                    log::trace!(
                        "  {opcode:x?}({operator1:?},{operator2:?}) => {:?}, stack ->{:?}",
                        stack.last(),
                        stack.iter().rev().collect::<Vec<_>>()
                    );
                }
                Opcode::Not => {
                    let operator = stack.pop().unwrap_or(false);
                    stack.push(!operator);
                    log::trace!(
                        "  {opcode:x?}({operator:?}) => {:?}, stack ->{:?}",
                        stack.last(),
                        stack.iter().rev().collect::<Vec<_>>()
                    );
                }
                Opcode::True => {
                    stack.push(true);
                    log::trace!(
                        "  {opcode:x?} => {:?}, stack ->{:?}",
                        stack.last(),
                        stack.iter().rev().collect::<Vec<_>>()
                    );
                }
                Opcode::False => {
                    stack.push(false);
                    log::trace!(
                        "  {opcode:x?} => {:?}, stack ->{:?}",
                        stack.last(),
                        stack.iter().rev().collect::<Vec<_>>()
                    );
                }
                Opcode::End => {
                    let operator = stack.pop().unwrap_or(false);
                    log::trace!(
                        "  {opcode:x?} => final result: {:?}, final stack ->{:?}",
                        operator,
                        stack.iter().rev().collect::<Vec<_>>()
                    );
                    return operator;
                }
                Opcode::Unknown => {
                    debug_assert!(false, "Exiting early due to an unknown opcode.");
                    return false;
                }
                Opcode::Malformed { opcode, len } => {
                    log::error!("Opcode [0x{opcode:x?}] expects a guid, only has a length of: {len}");
                    debug_assert!(
                        false,
                        "Exiting early because opcode [0x{opcode:x?}] expects a guid, only has a length of: {len}"
                    );
                    return false;
                }
            }
        }
        false
    }

    /// Returns an iterator over the protocols pushed by this expression, paired with whether each
    /// was found to be present at the most recent evaluation, in expression order.
    ///
    /// The position of each item corresponds to the references used by [`Depex::infix_expression`].
    pub fn pushes(&self) -> impl Iterator<Item = (&Uuid, bool)> {
        self.expression.iter().filter_map(|opcode| match opcode {
            Opcode::Push(guid, present) => Some((guid, *present)),
            _ => None,
        })
    }

    /// Renders the dependency expression in fully parenthesized infix form.
    ///
    /// Each pushed protocol is referenced by its position in [`Depex::pushes`]. It can be paired
    /// with [`Depex::pushes`] to map the numbers back to GUIDs.
    pub fn infix_expression(&self) -> String {
        let mut stack: Vec<String> = Vec::new();
        let mut prefix = String::new();
        let mut push_index = 0usize;
        for opcode in &self.expression {
            match opcode {
                Opcode::Push(_, _) => {
                    push_index += 1;
                    stack.push(push_index.to_string());
                }
                Opcode::And => {
                    let rhs = stack.pop().unwrap_or_default();
                    let lhs = stack.pop().unwrap_or_default();
                    stack.push(format!("({lhs} AND {rhs})"));
                }
                Opcode::Or => {
                    let rhs = stack.pop().unwrap_or_default();
                    let lhs = stack.pop().unwrap_or_default();
                    stack.push(format!("({lhs} OR {rhs})"));
                }
                Opcode::Not => {
                    let operand = stack.pop().unwrap_or_default();
                    stack.push(format!("(NOT {operand})"));
                }
                Opcode::True => stack.push(String::from("TRUE")),
                Opcode::False => stack.push(String::from("FALSE")),
                Opcode::Before(guid) => stack.push(format!("BEFORE {guid:?}")),
                Opcode::After(guid) => stack.push(format!("AFTER {guid:?}")),
                Opcode::Sor => prefix = String::from("SOR "),
                Opcode::Unknown => stack.push(String::from("UNKNOWN")),
                Opcode::Malformed { opcode, len } => stack.push(format!("MALFORMED(0x{opcode:02x}, len {len})")),
                Opcode::End => break,
            }
        }
        format!("{prefix}{}", stack.pop().unwrap_or_default())
    }

    /// If the depex expression is an associated dependency, it returns the associated dependency.
    pub fn is_associated(&self) -> Option<AssociatedDependency> {
        match self.expression.first() {
            Some(Opcode::Before(uid)) => Some(AssociatedDependency::Before(guid_from_uuid(uid)?)),
            Some(Opcode::After(uid)) => Some(AssociatedDependency::After(guid_from_uuid(uid)?)),
            _ => None,
        }
    }

    /// indicates that this is a "schedule on request" depex.
    pub fn is_sor(&self) -> bool {
        self.expression.first() == Some(&Opcode::Sor)
    }

    /// Marks a SOR depex as "scheduled". Does nothing for non SOR DEPEX expressions.
    pub fn schedule(&mut self) {
        if self.is_sor() {
            self.expression.remove(0);
        }
    }
}

struct DepexParser {
    expression: Vec<u8>,
    index: usize,
}

impl DepexParser {
    fn new(expression: &[u8]) -> Self {
        Self { expression: expression.to_vec(), index: 0 }
    }
}

impl Iterator for DepexParser {
    type Item = Opcode;

    /// Iterates over the DEPEX expression, returning the next Opcode.
    fn next(&mut self) -> Option<Opcode> {
        if self.index >= self.expression.len() {
            return None;
        }

        let opcode = Opcode::from(self.expression.get(self.index..)?);
        self.index += opcode.byte_size();
        Some(opcode)
    }
}

#[cfg(test)]
#[coverage(off)]
mod tests {
    extern crate std;
    use alloc::vec;
    use core::str::FromStr;
    use r_efi::efi;
    use std::println;
    use uuid::Uuid;

    use super::*;

    #[test]
    fn malformed_opcodes_should_generate_correct_malformed_opcode_enum_variant() {
        // Verify "Before" opcode with no GUID
        assert_eq!(Opcode::from([0x00u8].as_slice()), Opcode::Malformed { opcode: 0x00, len: 0 });
        assert_eq!(
            Opcode::from([0x00u8, 0x01u8, 0x02u8, 0x03u8].as_slice()),
            Opcode::Malformed { opcode: 0x00, len: 3 }
        );

        // Verify "After" opcode with no GUID
        assert_eq!(Opcode::from([0x01u8].as_slice()), Opcode::Malformed { opcode: 0x01, len: 0 });
        assert_eq!(
            Opcode::from([0x01u8, 0x01u8, 0x02u8, 0x03u8].as_slice()),
            Opcode::Malformed { opcode: 0x01, len: 3 }
        );

        // Verify "Push" opcode with no GUID
        assert_eq!(Opcode::from([0x02u8].as_slice()), Opcode::Malformed { opcode: 0x02, len: 0 });
        assert_eq!(
            Opcode::from([0x02u8, 0x01u8, 0x02u8, 0x03u8].as_slice()),
            Opcode::Malformed { opcode: 0x02, len: 3 }
        );
    }

    #[test]
    fn true_should_eval_true() {
        let mut depex = Depex::from(vec![0x06, 0x08]);
        assert!(depex.eval(&[]));
    }

    #[test]
    fn false_should_eval_false() {
        let mut depex = Depex::from(vec![0x07, 0x08]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn before_should_eval_false() {
        let mut depex = Depex::from(vec![
            0x00, 0xFA, 0xBD, 0xB6, 0x76, 0xCD, 0x2A, 0x62, 0x44, 0x9E, 0x3F, 0xCB, 0x58, 0xC9, 0x69, 0xD9, 0x37, 0x08,
        ]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn after_should_eval_false() {
        let mut depex = Depex::from(vec![
            0x01, 0xFA, 0xBD, 0xB6, 0x76, 0xCD, 0x2A, 0x62, 0x44, 0x9E, 0x3F, 0xCB, 0x58, 0xC9, 0x69, 0xD9, 0x37, 0x08,
        ]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn before_should_return_is_associated() {
        let depex = Depex::from(vec![
            0x00, 0xFA, 0xBD, 0xB6, 0x76, 0xCD, 0x2A, 0x62, 0x44, 0x9E, 0x3F, 0xCB, 0x58, 0xC9, 0x69, 0xD9, 0x37, 0x08,
        ]);

        assert_eq!(
            depex.is_associated(),
            Some(AssociatedDependency::Before(
                guid_from_uuid(&Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap()).unwrap()
            ))
        );
    }

    #[test]
    fn after_should_return_is_associated() {
        let depex = Depex::from(vec![
            0x01, 0xFA, 0xBD, 0xB6, 0x76, 0xCD, 0x2A, 0x62, 0x44, 0x9E, 0x3F, 0xCB, 0x58, 0xC9, 0x69, 0xD9, 0x37, 0x08,
        ]);

        assert_eq!(
            depex.is_associated(),
            Some(AssociatedDependency::After(
                guid_from_uuid(&Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap()).unwrap()
            ))
        );
    }

    #[test]
    fn sor_first_opcode_should_eval_false() {
        // Treated as a no-op, with no other operands, false should be returned
        let mut depex = Depex::from(vec![0x09, 0x08]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn sor_first_opcode_followed_by_true_should_eval_false() {
        let mut depex = Depex::from(vec![0x09, 0x06, 0x08]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn sor_first_opcode_followed_by_true_should_eval_true_after_schedule() {
        let mut depex = Depex::from(vec![0x09, 0x06, 0x08]);
        assert!(!depex.eval(&[]));

        depex.schedule();
        assert!(depex.eval(&[]));
    }

    #[test]
    fn sor_not_first_opcode_should_eval_false() {
        let mut depex = Depex::from(vec![0x06, 0x09, 0x08]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn replacetrue_should_eval_false() {
        let mut depex = Depex::from(vec![0xFF, 0x08]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn unknown_opcode_should_return_false() {
        let mut depex = Depex::from(vec![0xE0, 0x08]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn not_true_should_eval_false() {
        let mut depex = Depex::from(vec![0x07, 0x06, 0x08]);
        assert!(depex.eval(&[]));
    }

    #[test]
    fn not_false_should_eval_true() {
        let mut depex = Depex::from(vec![0x07, 0x05, 0x08]);
        assert!(depex.eval(&[]));
    }

    #[test]
    /// Tests a DEPEX expression with all AND operations that should evaluate to true when all protocols are installed.
    ///
    /// This test is based on the following dependency expression:
    ///   PUSH EfiPcdProtocolGuid
    ///   PUSH EfiDevicePathUtilitiesProtocolGuid
    ///   PUSH EfiHiiStringProtocolGuid
    ///   PUSH EfiHiiDatabaseProtocolGuid
    ///   PUSH EfiHiiConfigRoutingProtocolGuid
    ///   PUSH EfiResetArchProtocolGuid
    ///   PUSH EfiVariableWriteArchProtocolGuid
    ///   PUSH EfiVariableArchProtocolGuid
    ///   AND
    ///   AND
    ///   AND
    ///   AND
    ///   AND
    ///   AND
    ///   AND
    ///   END
    fn all_protocols_installed_and_should_eval_true() {
        let efi_pcd_prot_uuid = Uuid::from_str("13a3f0f6-264a-3ef0-f2e0-dec512342f34").unwrap();
        let efi_pcd_prot_guid: efi::Guid = guid_from_uuid(&efi_pcd_prot_uuid).unwrap();
        let efi_device_path_utilities_prot_uuid = Uuid::from_str("0379be4e-d706-437d-b037-edb82fb772a4").unwrap();
        let efi_device_path_utilities_prot_guid: efi::Guid =
            guid_from_uuid(&efi_device_path_utilities_prot_uuid).unwrap();
        let efi_hii_string_prot_uuid = Uuid::from_str("0fd96974-23aa-4cdc-b9cb-98d17750322a").unwrap();
        let efi_hii_string_prot_guid: efi::Guid = guid_from_uuid(&efi_hii_string_prot_uuid).unwrap();
        let efi_hii_db_prot_uuid = Uuid::from_str("ef9fc172-a1b2-4693-b327-6d32fc416042").unwrap();
        let efi_hii_db_prot_guid: efi::Guid = guid_from_uuid(&efi_hii_db_prot_uuid).unwrap();
        let efi_hii_config_routing_prot_uuid = Uuid::from_str("587e72d7-cc50-4f79-8209-ca291fc1a10f").unwrap();
        let efi_hii_config_routing_prot_guid: efi::Guid = guid_from_uuid(&efi_hii_config_routing_prot_uuid).unwrap();
        let efi_reset_arch_prot_uuid = Uuid::from_str("27cfac88-46cc-11d4-9a38-0090273fc14d").unwrap();
        let efi_reset_arch_prot_guid: efi::Guid = guid_from_uuid(&efi_reset_arch_prot_uuid).unwrap();
        let efi_var_write_arch_prot_uuid = Uuid::from_str("6441f818-6362-eb44-5700-7dba31dd2453").unwrap();
        let efi_var_write_arch_prot_guid: efi::Guid = guid_from_uuid(&efi_var_write_arch_prot_uuid).unwrap();
        let efi_var_arch_prot_uuid = Uuid::from_str("1e5668e2-8481-11d4-bcf1-0080c73c8881").unwrap();
        let efi_var_arch_prot_guid: efi::Guid = guid_from_uuid(&efi_var_arch_prot_uuid).unwrap();

        let protocols = [
            efi_pcd_prot_guid,
            efi_device_path_utilities_prot_guid,
            efi_hii_string_prot_guid,
            efi_hii_db_prot_guid,
            efi_hii_config_routing_prot_guid,
            efi_reset_arch_prot_guid,
            efi_var_write_arch_prot_guid,
            efi_var_arch_prot_guid,
        ];

        println!("Testing DEPEX for BdsDxe DXE driver...\n");

        let expression: &[u8] = &[
            0x02, 0xF6, 0xF0, 0xA3, 0x13, 0x4A, 0x26, 0xF0, 0x3E, 0xF2, 0xE0, 0xDE, 0xC5, 0x12, 0x34, 0x2F, 0x34, 0x02,
            0x4E, 0xBE, 0x79, 0x03, 0x06, 0xD7, 0x7D, 0x43, 0xB0, 0x37, 0xED, 0xB8, 0x2F, 0xB7, 0x72, 0xA4, 0x02, 0x74,
            0x69, 0xD9, 0x0F, 0xAA, 0x23, 0xDC, 0x4C, 0xB9, 0xCB, 0x98, 0xD1, 0x77, 0x50, 0x32, 0x2A, 0x02, 0x72, 0xC1,
            0x9F, 0xEF, 0xB2, 0xA1, 0x93, 0x46, 0xB3, 0x27, 0x6D, 0x32, 0xFC, 0x41, 0x60, 0x42, 0x02, 0xD7, 0x72, 0x7E,
            0x58, 0x50, 0xCC, 0x79, 0x4F, 0x82, 0x09, 0xCA, 0x29, 0x1F, 0xC1, 0xA1, 0x0F, 0x02, 0x88, 0xAC, 0xCF, 0x27,
            0xCC, 0x46, 0xD4, 0x11, 0x9A, 0x38, 0x00, 0x90, 0x27, 0x3F, 0xC1, 0x4D, 0x02, 0x18, 0xF8, 0x41, 0x64, 0x62,
            0x63, 0x44, 0xEB, 0x57, 0x00, 0x7D, 0xBA, 0x31, 0xDD, 0x24, 0x53, 0x02, 0xE2, 0x68, 0x56, 0x1E, 0x81, 0x84,
            0xD4, 0x11, 0xBC, 0xF1, 0x00, 0x80, 0xC7, 0x3C, 0x88, 0x81, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x08,
        ];
        let mut depex = Depex::from(expression.to_vec());

        assert!(depex.eval(&protocols));
    }

    #[test]
    /// Tests a DEPEX expression with AND and OR operations that should evaluate to true when all protocols are installed.
    ///
    /// This test is based on the following dependency expression:
    ///   PUSH EfiVariableArchProtocolGuid
    ///   PUSH EfiVariableWriteArchProtocolGuid
    ///   PUSH EfiTcgProtocolGuid
    ///   PUSH EfiTrEEProtocolGuid
    ///   OR
    ///   AND
    ///   AND
    ///   PUSH EfiPcdProtocolGuid
    ///   PUSH EfiDevicePathUtilitiesProtocolGuid
    ///   AND
    ///   AND
    ///   END
    fn all_protocols_installed_or_and_should_eval_true() {
        let efi_var_arch_prot_uuid = Uuid::from_str("1e5668e2-8481-11d4-bcf1-0080c73c8881").unwrap();
        let efi_var_arch_prot_guid: efi::Guid = guid_from_uuid(&efi_var_arch_prot_uuid).unwrap();
        let efi_var_write_arch_prot_uuid = Uuid::from_str("6441f818-6362-eb44-5700-7dba31dd2453").unwrap();
        let efi_var_write_arch_prot_guid: efi::Guid = guid_from_uuid(&efi_var_write_arch_prot_uuid).unwrap();
        let efi_tcg_prot_uuid = Uuid::from_str("f541796d-a62e-4954-a775-9584f61b9cdd").unwrap();
        let efi_tcg_prot_guid: efi::Guid = guid_from_uuid(&efi_tcg_prot_uuid).unwrap();
        let efi_tree_prot_uuid = Uuid::from_str("607f766c-7455-42be-930b-e4d76db2720f").unwrap();
        let efi_tree_prot_guid: efi::Guid = guid_from_uuid(&efi_tree_prot_uuid).unwrap();
        let efi_pcd_prot_uuid = Uuid::from_str("13a3f0f6-264a-3ef0-f2e0-dec512342f34").unwrap();
        let efi_pcd_prot_guid: efi::Guid = guid_from_uuid(&efi_pcd_prot_uuid).unwrap();
        let efi_device_path_utilities_prot_uuid = Uuid::from_str("0379be4e-d706-437d-b037-edb82fb772a4").unwrap();
        let efi_device_path_utilities_prot_guid: efi::Guid =
            guid_from_uuid(&efi_device_path_utilities_prot_uuid).unwrap();

        let protocols = [
            efi_var_arch_prot_guid,
            efi_var_write_arch_prot_guid,
            efi_tcg_prot_guid,
            efi_tree_prot_guid,
            efi_pcd_prot_guid,
            efi_device_path_utilities_prot_guid,
        ];

        println!("Testing DEPEX for TcgMor DXE driver...\n");

        let expression: &[u8] = &[
            0x02, 0xE2, 0x68, 0x56, 0x1E, 0x81, 0x84, 0xD4, 0x11, 0xBC, 0xF1, 0x00, 0x80, 0xC7, 0x3C, 0x88, 0x81, 0x02,
            0x18, 0xF8, 0x41, 0x64, 0x62, 0x63, 0x44, 0xEB, 0x57, 0x0, 0x7D, 0xBA, 0x31, 0xDD, 0x24, 0x53, 0x02, 0x6D,
            0x79, 0x41, 0xF5, 0x2E, 0xA6, 0x54, 0x49, 0xA7, 0x75, 0x95, 0x84, 0xF6, 0x1B, 0x9C, 0xDD, 0x02, 0x6C, 0x76,
            0x7F, 0x60, 0x55, 0x74, 0xBE, 0x42, 0x93, 0x0B, 0xE4, 0xD7, 0x6D, 0xB2, 0x72, 0x0F, 0x04, 0x03, 0x03, 0x02,
            0xF6, 0xF0, 0xA3, 0x13, 0x4A, 0x26, 0xF0, 0x3E, 0xF2, 0xE0, 0xDE, 0xC5, 0x12, 0x34, 0x2F, 0x34, 0x02, 0x4E,
            0xBE, 0x79, 0x03, 0x06, 0xD7, 0x7D, 0x43, 0xB0, 0x37, 0xED, 0xB8, 0x2F, 0xB7, 0x72, 0xA4, 0x03, 0x03, 0x08,
        ];
        let mut depex = Depex::from(expression.to_vec());

        assert!(depex.eval(&protocols));
    }

    #[test]
    /// This test is based on the following dependency expression:
    ///   PUSH EfiVariableArchProtocolGuid
    ///   PUSH EfiVariableWriteArchProtocolGuid
    ///   PUSH EfiTcgProtocolGuid
    ///   PUSH EfiTrEEProtocolGuid
    ///   OR
    ///   AND
    ///   AND
    ///   PUSH EfiPcdProtocolGuid
    ///   PUSH EfiDevicePathUtilitiesProtocolGuid
    ///   AND
    ///   AND
    ///   END
    fn opcode_list_to_depex_should_work() {
        let efi_var_arch_prot_uuid = Uuid::from_str("1e5668e2-8481-11d4-bcf1-0080c73c8881").unwrap();
        let efi_var_arch_prot_guid: efi::Guid = guid_from_uuid(&efi_var_arch_prot_uuid).unwrap();
        let efi_var_write_arch_prot_uuid = Uuid::from_str("6441f818-6362-eb44-5700-7dba31dd2453").unwrap();
        let efi_var_write_arch_prot_guid: efi::Guid = guid_from_uuid(&efi_var_write_arch_prot_uuid).unwrap();
        let efi_tcg_prot_uuid = Uuid::from_str("f541796d-a62e-4954-a775-9584f61b9cdd").unwrap();
        let efi_tcg_prot_guid: efi::Guid = guid_from_uuid(&efi_tcg_prot_uuid).unwrap();
        let efi_tree_prot_uuid = Uuid::from_str("607f766c-7455-42be-930b-e4d76db2720f").unwrap();
        let efi_tree_prot_guid: efi::Guid = guid_from_uuid(&efi_tree_prot_uuid).unwrap();
        let efi_pcd_prot_uuid = Uuid::from_str("13a3f0f6-264a-3ef0-f2e0-dec512342f34").unwrap();
        let efi_pcd_prot_guid: efi::Guid = guid_from_uuid(&efi_pcd_prot_uuid).unwrap();
        let efi_device_path_utilities_prot_uuid = Uuid::from_str("0379be4e-d706-437d-b037-edb82fb772a4").unwrap();
        let efi_device_path_utilities_prot_guid: efi::Guid =
            guid_from_uuid(&efi_device_path_utilities_prot_uuid).unwrap();

        let protocols = [
            efi_var_arch_prot_guid,
            efi_var_write_arch_prot_guid,
            efi_tcg_prot_guid,
            efi_tree_prot_guid,
            efi_pcd_prot_guid,
            efi_device_path_utilities_prot_guid,
        ];

        let expression: &[Opcode] = &[
            Opcode::Push(efi_var_arch_prot_uuid, true),
            Opcode::Push(efi_var_write_arch_prot_uuid, false),
            Opcode::Push(efi_tcg_prot_uuid, false),
            Opcode::Push(efi_tree_prot_uuid, false),
            Opcode::Or,
            Opcode::And,
            Opcode::And,
            Opcode::Push(efi_pcd_prot_uuid, false),
            Opcode::Push(efi_device_path_utilities_prot_uuid, false),
            Opcode::And,
            Opcode::And,
            Opcode::End,
        ];

        let mut depex = Depex::from(expression);

        assert!(depex.eval(&protocols));
    }

    #[test]
    fn guid_to_uuid_conversion_should_produce_correct_bytes() {
        let device_path_protocol_guid_bytes: &[u8] =
            &[0x4E, 0xBE, 0x79, 0x03, 0x06, 0xD7, 0x7D, 0x43, 0xB0, 0x37, 0xED, 0xB8, 0x2F, 0xB7, 0x72, 0xA4];

        let uuid = uuid_from_slice(Some(device_path_protocol_guid_bytes)).unwrap();
        assert_eq!(uuid, uuid::Uuid::from_str("0379be4e-d706-437d-b037-edb82fb772a4").unwrap());

        let guid = guid_from_uuid(&uuid);
        assert_eq!(guid.unwrap().as_bytes(), device_path_protocol_guid_bytes);
    }

    #[test]
    fn guid_not_in_protocol_db_should_eval_false() {
        let mut depex = Depex::from(vec![
            0x02, 0xF6, 0xF0, 0xA3, 0x13, 0x4A, 0x26, 0xF0, 0x3E, 0xF2, 0xE0, 0xDE, 0xC5, 0x12, 0x34, 0x2F, 0x34, 0x08,
        ]);
        assert!(!depex.eval(&[]));
    }

    #[test]
    fn opcode_before_should_panic_when_not_at_start_of_depex() {
        let opcodes = [Opcode::And, Opcode::Before(Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap())];
        let mut depex = Depex::from(opcodes.as_slice());
        depex.eval(&[]);
    }

    #[test]
    fn opcode_after_should_panic_when_not_at_start_of_depex() {
        let opcodes = [Opcode::And, Opcode::After(Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap())];
        let mut depex = Depex::from(opcodes.as_slice());
        depex.eval(&[]);
    }

    #[test]
    fn opcode_before_should_panic_when_final_opcode_is_not_end() {
        let opcodes = [Opcode::Before(Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap()), Opcode::And];
        let mut depex = Depex::from(opcodes.as_slice());
        depex.eval(&[]);
    }

    #[test]
    fn opcode_after_should_panic_when_final_opcode_is_not_end() {
        let opcodes = [Opcode::After(Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap()), Opcode::And];
        let mut depex = Depex::from(opcodes.as_slice());
        depex.eval(&[]);
    }

    #[test]
    fn opcode_before_should_panic_when_additional_opcodes_after() {
        let opcodes =
            [Opcode::Before(Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap()), Opcode::And, Opcode::End];
        let mut depex = Depex::from(opcodes.as_slice());
        depex.eval(&[]);
    }

    #[test]
    fn opcode_after_should_panic_when_additional_opcodes_after() {
        let opcodes =
            [Opcode::After(Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap()), Opcode::And, Opcode::End];
        let mut depex = Depex::from(opcodes.as_slice());
        depex.eval(&[]);
    }

    #[test]
    fn malformed_opcode_should_panic_with_well_defined_message() {
        let opcodes = [Opcode::Malformed { opcode: 0x00, len: 0 }];
        let mut depex = Depex::from(opcodes.as_slice());
        depex.eval(&[]);
    }

    #[test]
    fn pushes_should_yield_protocols_in_order_with_presence() {
        let guid_a = Uuid::from_str("1e5668e2-8481-11d4-bcf1-0080c73c8881").unwrap();
        let guid_b = Uuid::from_str("6441f818-6362-eb44-5700-7dba31dd2453").unwrap();
        let expression: &[Opcode] =
            &[Opcode::Push(guid_a, true), Opcode::Push(guid_b, false), Opcode::And, Opcode::End];
        let depex = Depex::from(expression);

        let pushes: Vec<(Uuid, bool)> = depex.pushes().map(|(guid, present)| (*guid, present)).collect();
        assert_eq!(pushes, vec![(guid_a, true), (guid_b, false)]);
    }

    #[test]
    fn infix_expression_should_render_numbered_and_and_or() {
        let guid = Uuid::from_str("1e5668e2-8481-11d4-bcf1-0080c73c8881").unwrap();
        // 1 2 AND 3 4 AND OR
        let expression: &[Opcode] = &[
            Opcode::Push(guid, false),
            Opcode::Push(guid, false),
            Opcode::And,
            Opcode::Push(guid, false),
            Opcode::Push(guid, false),
            Opcode::And,
            Opcode::Or,
            Opcode::End,
        ];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), "((1 AND 2) OR (3 AND 4))");
    }

    #[test]
    fn infix_expression_should_render_not_true_false() {
        let expression: &[Opcode] = &[Opcode::True, Opcode::Not, Opcode::End];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), "(NOT TRUE)");

        let expression: &[Opcode] = &[Opcode::False, Opcode::End];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), "FALSE");
    }

    #[test]
    fn infix_expression_should_be_empty_for_empty_expression() {
        let expression: &[Opcode] = &[];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), "");
    }

    #[test]
    fn infix_expression_should_render_before_and_after() {
        let guid = Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap();

        let expression: &[Opcode] = &[Opcode::Before(guid), Opcode::End];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), format!("BEFORE {guid:?}"));

        let expression: &[Opcode] = &[Opcode::After(guid), Opcode::End];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), format!("AFTER {guid:?}"));
    }

    #[test]
    fn infix_expression_should_render_sor_as_prefix() {
        let expression: &[Opcode] = &[Opcode::Sor, Opcode::True, Opcode::End];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), "SOR TRUE");
    }

    #[test]
    fn infix_expression_should_render_unknown_and_malformed() {
        let expression: &[Opcode] = &[Opcode::Unknown, Opcode::End];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), "UNKNOWN");

        let expression: &[Opcode] = &[Opcode::Malformed { opcode: 0x02, len: 3 }, Opcode::End];
        let depex = Depex::from(expression);
        assert_eq!(depex.infix_expression(), "MALFORMED(0x02, len 3)");
    }

    #[test]
    fn infix_expression_should_render_complex_before_after_and_or() {
        let guid_a = Uuid::from_str("1e5668e2-8481-11d4-bcf1-0080c73c8881").unwrap();
        let guid_b = Uuid::from_str("6441f818-6362-eb44-5700-7dba31dd2453").unwrap();
        let guid_before = Uuid::from_str("76b6bdfa-2acd-4462-9e3f-cb58c969d937").unwrap();
        let guid_after = Uuid::from_str("0379be4e-d706-437d-b037-edb82fb772a4").unwrap();

        // Postfix: A B AND  BEFORE  AFTER  OR  AND
        let expression: &[Opcode] = &[
            Opcode::Push(guid_a, false),
            Opcode::Push(guid_b, false),
            Opcode::And,
            Opcode::Before(guid_before),
            Opcode::After(guid_after),
            Opcode::Or,
            Opcode::And,
            Opcode::End,
        ];
        let depex = Depex::from(expression);
        assert_eq!(
            depex.infix_expression(),
            format!("((1 AND 2) AND (BEFORE {guid_before:?} OR AFTER {guid_after:?}))")
        );
    }
}