### What and why License scanning reports can contain SPDX compound expressions such as `MIT AND Apache-2.0` or `GPL-2.0-or-later WITH Bison-exception-2.2` instead of plain license names. The current `DeniedLicensesChecker` performs only exact string matching against policy names, so compound expressions are never matched correctly. This issue introduces `Gitlab::SPDX::ExpressionParser`, a recursive-descent parser that decomposes an SPDX expression string into a parse tree (root `Node`) that a policy checker can evaluate recursively. The parser is a pure, stateless utility with no database or network calls. It ships independently of the checker so it can be reviewed on its own merits. ### Scope - Add `ee/lib/gitlab/spdx/expression_parser.rb` — full parser supporting AND, OR, WITH, `+` (version-range), LicenseRef, and DocumentRef expressions. - Add `ee/spec/lib/gitlab/spdx/expression_parser_spec.rb` — full spec. - No feature flag, no checker, no wiring to `UpdateLicenseApprovalsService` in this issue. ### Implementation notes The parser uses a standard [recursive-descent parsing](https://en.wikipedia.org/wiki/Recursive_descent_parser) algorithm — one method per grammar production rule, each calling the next level down. Operator precedence falls out naturally from the call hierarchy rather than needing an explicit precedence table. The grammar it implements is the SPDX compound-expression subset: ``` expression ::= or_expression or_expression ::= and_expression ( OR and_expression )* and_expression ::= with_expression ( AND with_expression )* with_expression ::= simple_expression ( WITH simple_expression )? simple_expression ::= '(' expression ')' | license_id license_id ::= IDSTRING '+'? ``` Operator precedence (highest to lowest, per [SPDX spec](https://spdx.github.io/spdx-spec/v3.0.1/annexes/spdx-license-expressions/#order-of-precedence-and-parentheses)): 1. `+` (version-range suffix, resolved at tokenization time) 2. `WITH` 3. `AND` 4. `OR` 5. Parentheses for explicit grouping Operators (`AND`, `OR`, `WITH`) are matched case-insensitively but must be all-uppercase or all-lowercase. Mixed case (e.g. `And`) is treated as an identifier token and causes a parse error, falling back to a `:literal` root node. The parser returns an `ExpressionResult` with two fields: - `node` — the root `Node` of the parse tree, ready to be walked recursively by the checker. - `literal` — the original unmodified input string. #### Parse tree examples `MIT AND Apache-2.0`: ``` :and ├── :id "MIT" └── :id "Apache-2.0" ``` `MIT AND (Apache-2.0 OR GPL-2.0)`: ``` :and ├── :id "MIT" └── :or ├── :id "Apache-2.0" └── :id "GPL-2.0" ``` `GPL-2.0-or-later WITH Bison-exception-2.2 AND MIT` (WITH binds tighter than AND per the SPDX spec): ``` :and ├── :with "WITH" │ ├── :id "GPL-2.0-or-later" │ └── :id "Bison-exception-2.2" └── :id "MIT" ``` `CDDL-1.0+ AND MIT` (`+` is resolved at tokenization time into a single `:plus` token): ``` :and ├── :plus "CDDL-1.0+" └── :id "MIT" ``` #### Node types | type | value | children | meaning | |---|---|---|---| | `:id` | identifier string | `[]` | plain license identifier | | `:plus` | full token e.g. `"CDDL-1.0+"` | `[]` | version-or-later; base = `value.chomp('+')` | | `:with` | original operator text | `[license, exception]` | license with exception | | `:and` | `nil` | `[left, right]` | conjunction — dependency carries all licenses | | `:or` | `nil` | `[left, right]` | disjunction — any one license satisfies | | `:literal` | original raw input | `[]` | parse-error fallback; checker uses exact string match | Mixed expressions (AND+OR, WITH+AND, etc.) produce a correct tree — there is no fallback for mixed operators. Only genuine parse errors fall back to a `:literal` root node. Expressions up to 1024 characters are supported. Recursion depth is bounded by parenthesis nesting depth, not expression length. **Structural requirements:** - Use `StringScanner` (stdlib) for tokenization — captures character offsets, idiomatic Ruby. - Place `ParseError`, `Node`, `Token`, and `ExpressionResult` at the `Gitlab::SPDX` module level. - Use `keyword_init: true` on all structs. - Freeze all string constants. - Follow top-down method ordering (high-level orchestrators before helpers). - Use `fast_spec_helper` in the spec. - Use direct RSpec matchers (`have_attributes`, `contain_exactly`, `raise_error` with `/regex/`). - Include unit tests for `Node`, `Token`, and `ExpressionResult`. ### Acceptance criteria - [ ] `Gitlab::SPDX::ExpressionParser.new('MIT AND Apache-2.0').parse` returns an `ExpressionResult` whose `node` is `type: :and` with two `:id` children `'MIT'` and `'Apache-2.0'`. - [ ] `Gitlab::SPDX::ExpressionParser.new('MIT OR Apache-2.0').parse` returns an `ExpressionResult` whose `node` is `type: :or` with two `:id` children `'MIT'` and `'Apache-2.0'`. - [ ] `Gitlab::SPDX::ExpressionParser.new('GPL-2.0-or-later WITH Bison-exception-2.2').parse` returns an `ExpressionResult` whose `node` is `type: :with`, `value: 'WITH'`, with children `[:id('GPL-2.0-or-later'), :id('Bison-exception-2.2')]`. - [ ] `Gitlab::SPDX::ExpressionParser.new('CDDL-1.0+').parse` returns an `ExpressionResult` whose `node` is `type: :plus`, `value: 'CDDL-1.0+'`. The checker derives the base version via `node.value.chomp('+')` - [ ] `Gitlab::SPDX::ExpressionParser.new('MIT').parse` returns an `ExpressionResult` whose `node` is `type: :id`, `value: 'MIT'`. - [ ] Mixed expressions (AND+OR, WITH+AND, etc.) produce a correct parse tree — no fallback to `:literal`. E.g. `'MIT AND (Apache-2.0 OR GPL-2.0)'` returns `type: :and` at the root with `type: :or` as the right child. - [ ] Parse errors fall back to `type: :literal` with the original string as `node.value` and `literal`. - [ ] Error messages include the expression string and character offset. - [ ] All string constants are frozen. - [ ] `Node`, `Token`, and `ExpressionResult` construction uses keyword arguments; positional construction raises `ArgumentError`. - [ ] Spec uses `fast_spec_helper` and `feature_category` metadata. ### References - POC MR: !235265 - Alan's Parser MR: !234469