spdx 0.13.4

use crate::{
    AdditionItem, AdditionRef, LicenseItem, LicenseRef, LicenseReq, ParseMode,
    error::{ParseError, Reason},
    expression::{ExprNode, Expression, ExpressionReq, Operator},
    lexer::{Lexer, Token},
};
use alloc::{borrow::ToOwned, boxed::Box, string::String};
use smallvec::SmallVec;

impl Expression {
    /// Given a license expression, attempts to parse and validate it as a valid
    /// SPDX expression. Uses `ParseMode::Strict`.
    ///
    /// The validation can fail for many reasons:
    /// * The expression contains invalid characters
    /// * An unknown/invalid license or exception identifier was found. Only
    ///   [SPDX short identifiers](https://spdx.org/ids) are allowed
    /// * The expression contained unbalanced parentheses
    /// * A license or exception immediately follows another license or exception, without
    ///   a valid AND, OR, or WITH operator separating them
    /// * An AND, OR, or WITH doesn't have a license or `)` preceding it
    ///
    /// ```
    /// spdx::Expression::parse("MIT OR Apache-2.0 WITH LLVM-exception").unwrap();
    /// ```
    pub fn parse(original: &str) -> Result<Self, ParseError> {
        Self::parse_mode(original, ParseMode::STRICT)
    }

    /// Canonicalizes the input expression into a form that can be parsed with
    /// [`ParseMode::STRICT`]
    ///
    /// ## Transforms
    ///
    /// 1. '/' is replaced with ' OR '
    /// 1. Lower-cased operators ('or', 'and', 'with') are upper-cased
    /// 1. '+' is transformed to `-or-later` for GNU licenses, or `-only` with no '+'
    /// 1. Invalid/imprecise license identifiers (eg. `apache2`) are replaced
    ///    with their valid identifiers
    ///
    /// If the provided expression is not modified then `None` is returned
    ///
    /// Note that this only does fixup of otherwise valid expressions, passing
    /// the resulting string to [`Expression::parse`] can still result in
    /// additional parse errors, eg. unbalanced parentheses
    ///
    /// ```
    /// let expr = "apache with LLVM-exception/gpl-3.0+ and gplv2";
    /// assert_eq!(
    ///     spdx::Expression::canonicalize(expr).unwrap().unwrap(),
    ///     "Apache-2.0 WITH LLVM-exception OR GPL-3.0-or-later AND GPL-2.0-only"
    /// );
    /// ```
    pub fn canonicalize(original: &str) -> Result<Option<String>, ParseError> {
        let mut can = String::with_capacity(original.len());

        let lexer = Lexer::new_mode(original, ParseMode::LAX);

        let push_id = |s: &mut String, id: crate::LicenseId| {
            s.push_str(id.name);
            if id.is_gnu() && !id.name.ends_with("-only") && !id.name.ends_with("-or-later") {
                s.push_str("-only");
            }
        };

        // Keep track if the last license id is a GNU license that uses the -or-later
        // convention rather than the + like all other licenses
        let mut last = Option::<crate::LicenseId>::None;
        for tok in lexer {
            let tok = tok?;

            if !matches!(tok.token, Token::Plus) {
                if let Some(id) = last.take() {
                    push_id(&mut can, id);
                }
            }

            match tok.token {
                Token::Spdx(id) => {
                    last = Some(id);
                }
                Token::And => can.push_str(" AND "),
                Token::Or => can.push_str(" OR "),
                Token::With => can.push_str(" WITH "),
                Token::Plus => {
                    let Some(id) = last.take() else {
                        return Err(ParseError {
                            original: original.into(),
                            span: tok.span,
                            reason: Reason::Unexpected(&["<license>"]),
                        });
                    };

                    push_id(&mut can, id);
                    if id.is_gnu() {
                        if can.ends_with("-only") {
                            can.truncate(can.len() - 5);
                        }

                        can.push_str("-or-later");
                    } else {
                        can.push('+');
                    }
                }
                Token::OpenParen => can.push('('),
                Token::CloseParen => can.push(')'),
                Token::Exception(exc) => can.push_str(exc.name),
                Token::LicenseRef { doc_ref, lic_ref } => {
                    if let Some(dr) = doc_ref {
                        can.push_str("DocumentRef-");
                        can.push_str(dr);
                        can.push(':');
                    }

                    can.push_str("LicenseRef-");
                    can.push_str(lic_ref);
                }
                Token::AdditionRef { doc_ref, add_ref } => {
                    if let Some(dr) = doc_ref {
                        can.push_str("DocumentRef-");
                        can.push_str(dr);
                        can.push(':');
                    }

                    can.push_str("AdditionRef-");
                    can.push_str(add_ref);
                }
                Token::Unknown(_u) => unreachable!(),
            }
        }

        if let Some(id) = last {
            push_id(&mut can, id);
        }

        Ok((can != original).then_some(can))
    }

    /// Parses an expression with the specified `ParseMode`.
    ///
    /// With `ParseMode::Lax` it permits some non-SPDX syntax, such as imprecise
    /// license names and "/" used instead of "OR" in expressions.
    ///
    /// ```
    /// spdx::Expression::parse_mode(
    ///     "mit/Apache-2.0 WITH LLVM-exception",
    ///     spdx::ParseMode::LAX
    /// ).unwrap();
    /// ```
    pub fn parse_mode(original: &str, mode: ParseMode) -> Result<Self, ParseError> {
        use core::ops::Range;

        // Operator precedence in SPDX 2.1
        // +
        // WITH
        // AND
        // OR
        #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug)]
        enum Op {
            //Plus,
            //With,
            And,
            Or,
            Open,
        }

        struct OpAndSpan {
            op: Op,
            span: Range<usize>,
        }

        let lexer = Lexer::new_mode(original, mode);
        let mut op_stack = SmallVec::<[OpAndSpan; 3]>::new();
        let mut expr_queue = SmallVec::<[ExprNode; 5]>::new();

        // Keep track of the last token to simplify validation of the token stream
        let mut last_token: Option<Token<'_>> = None;

        let apply_op = |op: OpAndSpan, q: &mut SmallVec<[ExprNode; 5]>| {
            let op = match op.op {
                Op::And => Operator::And,
                Op::Or => Operator::Or,
                Op::Open => unreachable!(),
            };

            q.push(ExprNode::Op(op));
            Ok(())
        };

        let make_err_for_token = |last_token: Option<Token<'_>>, span: Range<usize>| {
            let expected: &[&str] = match last_token {
                None | Some(Token::And | Token::Or | Token::OpenParen) => &["<license>", "("],
                Some(Token::CloseParen) => &["AND", "OR"],
                Some(Token::Exception(_) | Token::AdditionRef { .. }) => &["AND", "OR", ")"],
                Some(Token::Spdx(_) | Token::Unknown(_)) => &["AND", "OR", "WITH", ")", "+"],
                Some(Token::LicenseRef { .. } | Token::Plus) => &["AND", "OR", "WITH", ")"],
                Some(Token::With) => &["<addition>"],
            };

            Err(ParseError {
                original: original.to_owned(),
                span,
                reason: Reason::Unexpected(expected),
            })
        };

        // Basic implementation of the https://en.wikipedia.org/wiki/Shunting-yard_algorithm
        'outer: for tok in lexer {
            let lt = tok?;
            match &lt.token {
                Token::Spdx(id) => match last_token {
                    None | Some(Token::And | Token::Or | Token::OpenParen) => {
                        if !mode.allow_deprecated && id.is_deprecated() {
                            return Err(ParseError {
                                original: original.to_owned(),
                                span: lt.span,
                                reason: Reason::DeprecatedLicenseId,
                            });
                        }

                        expr_queue.push(ExprNode::Req(ExpressionReq {
                            req: LicenseReq::from(*id),
                            span: lt.span.start as u32..lt.span.end as u32,
                        }));
                    }
                    _ => return make_err_for_token(last_token, lt.span),
                },
                Token::LicenseRef { doc_ref, lic_ref } => match last_token {
                    None | Some(Token::And | Token::Or | Token::OpenParen) => {
                        expr_queue.push(ExprNode::Req(ExpressionReq {
                            req: LicenseReq {
                                license: LicenseItem::Other(Box::new(LicenseRef {
                                    doc_ref: doc_ref.map(String::from),
                                    lic_ref: String::from(*lic_ref),
                                })),
                                addition: None,
                            },
                            span: lt.span.start as u32..lt.span.end as u32,
                        }));
                    }
                    _ => return make_err_for_token(last_token, lt.span),
                },
                Token::Plus => match last_token {
                    Some(Token::Spdx(_)) => match expr_queue.last_mut().unwrap() {
                        ExprNode::Req(ExpressionReq {
                            req:
                                LicenseReq {
                                    license: LicenseItem::Spdx { or_later, id },
                                    ..
                                },
                            ..
                        }) => {
                            // Handle GNU licenses differently, as they should *NOT* be used with the `+`
                            if id.is_gnu() {
                                if !mode.allow_postfix_plus_on_gpl {
                                    return Err(ParseError {
                                        original: original.to_owned(),
                                        span: lt.span,
                                        reason: Reason::GnuNoPlus,
                                    });
                                }

                                if id.name.ends_with("-or-later") {
                                    return Err(ParseError {
                                        original: original.to_owned(),
                                        span: lt.span,
                                        reason: Reason::GnuPlusWithSuffix,
                                    });
                                }

                                *id = crate::gnu_license_id(
                                    id.name.strip_suffix("-only").unwrap_or(id.name),
                                    true,
                                )
                                .ok_or_else(|| ParseError {
                                    original: original.to_owned(),
                                    span: lt.span,
                                    reason: Reason::UnknownLicense,
                                })?;
                            } else {
                                *or_later = true;
                            }
                        }
                        _ => unreachable!(),
                    },
                    _ => return make_err_for_token(last_token, lt.span),
                },
                Token::With => match last_token {
                    Some(
                        Token::Spdx(_) | Token::LicenseRef { .. } | Token::Plus | Token::Unknown(_),
                    ) => {}
                    _ => return make_err_for_token(last_token, lt.span),
                },
                Token::Or | Token::And => match last_token {
                    Some(
                        Token::Spdx(_)
                        | Token::LicenseRef { .. }
                        | Token::CloseParen
                        | Token::Exception(_)
                        | Token::AdditionRef { .. }
                        | Token::Plus
                        | Token::Unknown(_),
                    ) => {
                        let new_op = match lt.token {
                            Token::Or => Op::Or,
                            Token::And => Op::And,
                            _ => unreachable!(),
                        };

                        while let Some(op) = op_stack.last() {
                            match &op.op {
                                Op::Open => break,
                                top => {
                                    if *top < new_op {
                                        let top = op_stack.pop().unwrap();

                                        match top.op {
                                            Op::And | Op::Or => apply_op(top, &mut expr_queue)?,
                                            Op::Open => unreachable!(),
                                        }
                                    } else {
                                        break;
                                    }
                                }
                            }
                        }

                        op_stack.push(OpAndSpan {
                            op: new_op,
                            span: lt.span,
                        });
                    }
                    _ => return make_err_for_token(last_token, lt.span),
                },
                Token::OpenParen => match last_token {
                    None | Some(Token::And | Token::Or | Token::OpenParen) => {
                        op_stack.push(OpAndSpan {
                            op: Op::Open,
                            span: lt.span,
                        });
                    }
                    _ => return make_err_for_token(last_token, lt.span),
                },
                Token::CloseParen => {
                    match last_token {
                        Some(
                            Token::Spdx(_)
                            | Token::LicenseRef { .. }
                            | Token::Plus
                            | Token::Exception(_)
                            | Token::AdditionRef { .. }
                            | Token::CloseParen
                            | Token::Unknown(_),
                        ) => {
                            while let Some(top) = op_stack.pop() {
                                match top.op {
                                    Op::And | Op::Or => apply_op(top, &mut expr_queue)?,
                                    Op::Open => {
                                        // This is the only place we go back to the top of the outer loop,
                                        // so make sure we correctly record this token
                                        last_token = Some(Token::CloseParen);
                                        continue 'outer;
                                    }
                                }
                            }

                            // We didn't have an opening parentheses if we get here
                            return Err(ParseError {
                                original: original.to_owned(),
                                span: lt.span,
                                reason: Reason::UnopenedParens,
                            });
                        }
                        _ => return make_err_for_token(last_token, lt.span),
                    }
                }
                Token::Exception(exc) => match last_token {
                    Some(Token::With) => match expr_queue.last_mut() {
                        Some(ExprNode::Req(lic)) => {
                            lic.req.addition = Some(AdditionItem::Spdx(*exc));
                        }
                        _ => unreachable!(),
                    },
                    _ => return make_err_for_token(last_token, lt.span),
                },
                Token::AdditionRef { doc_ref, add_ref } => match last_token {
                    Some(Token::With) => match expr_queue.last_mut() {
                        Some(ExprNode::Req(lic)) => {
                            lic.req.addition = Some(AdditionItem::Other(Box::new(AdditionRef {
                                doc_ref: doc_ref.map(String::from),
                                add_ref: String::from(*add_ref),
                            })));
                        }
                        _ => unreachable!(),
                    },
                    _ => return make_err_for_token(last_token, lt.span),
                },
                Token::Unknown(unknown) => {
                    match last_token {
                        None | Some(Token::And | Token::Or | Token::OpenParen) => {
                            // This is the same position as a valid SPDX license id,
                            // so assume that is what the user was attempting
                            expr_queue.push(ExprNode::Req(ExpressionReq {
                                req: LicenseReq {
                                    license: LicenseItem::Other(Box::new(LicenseRef {
                                        doc_ref: None,
                                        lic_ref: (*unknown).to_owned(),
                                    })),
                                    addition: None,
                                },
                                span: lt.span.start as u32..lt.span.end as u32,
                            }));
                        }
                        Some(Token::With) => {
                            let Some(ExprNode::Req(lic)) = expr_queue.last_mut() else {
                                return make_err_for_token(last_token, lt.span);
                            };

                            lic.req.addition = Some(AdditionItem::Other(Box::new(AdditionRef {
                                doc_ref: None,
                                add_ref: (*unknown).to_owned(),
                            })));
                        }
                        _ => return make_err_for_token(last_token, lt.span),
                    }
                }
            }

            last_token = Some(lt.token);
        }

        // Validate that the terminating token is valid
        match last_token {
            Some(
                Token::Spdx(_)
                | Token::LicenseRef { .. }
                | Token::Exception(_)
                | Token::AdditionRef { .. }
                | Token::CloseParen
                | Token::Plus
                | Token::Unknown(_),
            ) => {}
            // We have to have at least one valid license requirement
            None => {
                return Err(ParseError {
                    original: original.to_owned(),
                    span: 0..original.len(),
                    reason: Reason::Empty,
                });
            }
            Some(_) => return make_err_for_token(last_token, original.len()..original.len()),
        }

        while let Some(top) = op_stack.pop() {
            match top.op {
                Op::And | Op::Or => apply_op(top, &mut expr_queue)?,
                Op::Open => {
                    return Err(ParseError {
                        original: original.to_owned(),
                        span: top.span,
                        reason: Reason::UnclosedParens,
                    });
                }
            }
        }

        // TODO: Investigate using https://github.com/oli-obk/quine-mc_cluskey to simplify
        // expressions, but not really critical. Just cool.

        Ok(Expression {
            original: original.to_owned(),
            expr: expr_queue,
        })
    }
}