Implementation:Ggml org Llama cpp Regex Partial
| Knowledge Sources | |
|---|---|
| Domains | Parsing, Regex |
| Last Updated | 2026-02-15 00:00 GMT |
Overview
Implements regex matching with support for detecting partial matches at the end of input, where the input may be an incomplete prefix of a full match.
Description
The `common_regex::search()` method first tries a full match using `std::regex_match`/`std::regex_search`. If that fails, it attempts a partial match by transforming the original regex pattern into a reversed partial regex and running it against the reversed input. The `regex_to_reversed_partial_regex()` function inverts and restructures the pattern so that matching it against reversed input detects if the input ends with a prefix of something the original regex would match. Handles character classes, quantifiers, groups, alternations, and repetition ranges during transformation.
Usage
Use this module in constrained decoding scenarios where streaming token generation must respect regex-based format constraints. It detects whether generated text could still match a regex constraint if more tokens were added, allowing the system to avoid premature rejection of valid partial outputs.
Code Reference
Source Location
- Repository: Ggml_org_Llama_cpp
- File: common/regex-partial.cpp
- Lines: 1-204
Signature
common_regex::common_regex(const std::string & pattern);
common_regex_match common_regex::search(const std::string & input, size_t pos, bool as_match = false) const;
std::string regex_to_reversed_partial_regex(const std::string & pattern);
Import
#include "regex-partial.h"
I/O Contract
Inputs
| Name | Type | Required | Description |
|---|---|---|---|
| pattern | const std::string & | Yes | The regex pattern to compile for full and partial matching |
| input | const std::string & | Yes | The input string to search for full or partial matches |
| pos | size_t | Yes | Starting position within the input string |
| as_match | bool | No | If true, requires the entire remaining input to match (like regex_match vs regex_search) |
Outputs
| Name | Type | Description |
|---|---|---|
| match result | common_regex_match | Contains match type (NONE, PARTIAL, FULL) and group positions |
| reversed regex | std::string | The transformed regex pattern for reversed partial matching (from regex_to_reversed_partial_regex) |
Usage Examples
#include "regex-partial.h"
// Create a regex with partial match support
common_regex rx("[0-9]{4}-[0-9]{2}-[0-9]{2}");
// Full match
auto result = rx.search("2024-01-15", 0);
// result.type == COMMON_REGEX_MATCH_TYPE_FULL
// Partial match (incomplete date)
auto partial = rx.search("2024-01", 0, true);
// partial.type == COMMON_REGEX_MATCH_TYPE_PARTIAL
// No match
auto none = rx.search("hello", 0, true);
// none.type == COMMON_REGEX_MATCH_TYPE_NONE
// Test helper for reversed partial regex
std::string reversed = regex_to_reversed_partial_regex("abcd");
// reversed == "^((?:(?:(?:d)?c)?b)?a)"