fix: accept an IPv4 tail in uri IPv6 literals (#417)

Summary

Follow-up to #408. "format": "uri" still rejects a host such as [::ffff:192.0.2.1]. The IP-literal branch of the uri regex in parser/src/json/formats.rs has its own simplified IPv6 pattern that allows hex groups only.

RFC 3986 section 3.2.2 defines IP-literal with the same IPv6address rule that the ipv6 format has followed since #408. That rule allows the last 32 bits of the address to be written as a dotted IPv4 address.

This change moves the ipv6 pattern into a macro_rules! macro and uses it both for the ipv6 format and for the IPv6 part of the uri IP-literal. A macro is needed because concat! accepts only literals, so a const &str cannot be spliced into the uri pattern. The macro body is the old ipv6 string, moved verbatim: the concatenated string is byte-for-byte the same as on main. uri is the only other format with an IPv6 pattern.

The commented-out zone ID case in valid_uri (http://[fe80::1%25eth0]/) stays commented out. Zone IDs come from RFC 6874, and JSON Schema’s uri format refers to RFC 3986 only.

Repro

{"type": "string", "format": "uri"}

Now accepted (rejected on main):

http://[::ffff:192.0.2.1]/
http://[::ffff:192.0.2.1]:8080/path
http://[2001:db8::192.0.2.1]/
http://[1:2:3:4:5:6:192.0.2.1]/

Still rejected:

http://[::ffff:192.0.2.256]/
http://[::ffff:192.0.2]/
http://[::ffff:192.0.02.1]/
http://[1:2:3:4:5:6:7:192.0.2.1]/

Test plan

valid_uri: the commented http://[::ffff:192.0.2.1]/ case is enabled, and the 3 other hosts above are added. bad_uri gains the 4 invalid hosts above. With the new tests and formats.rs from main, the 4 new valid_uri cases fail and the 4 new bad_uri cases pass. With this change, all of them pass.
Hex-only literals: I enumerated 135 addresses (0 to 9 groups, with and without :: at every position, each with and without an IPv4 tail, plus malformed forms such as ::: and ::1::2). I matched each in full (re.fullmatch) against the old IP-literal sub-pattern from the uri regex and against the ipv6 pattern, in Python. They agree on all 70 inputs without an IPv4 tail. Of the 65 inputs with a tail, the new pattern accepts 22 and both reject 43. This was a check in Python, not in llguidance’s regex engine; the rstest cases above are the check in llguidance.
All tests pass locally except test_raw_parser, which was not run because its tokenizer was not available offline. Clippy and fmt are clean.

Signed-off-by: William Guo guowilliam3@gmail.com

Low-level Guidance (llguidance)

Performance results from MaskBench

2025-06-23 llguidance is now deemed v1.0.0
2025-06-11 Making Structured Outputs Go Brrr blog post released
2025-05-20 LLGuidance shipped in OpenAI for JSON Schema
2025-04-11 integration merged into Chromium
2025-03-25 integration merged into vLLM (v0.8.2)
2025-02-26 integration merged into SGLang (v0.4.4)
2025-02-01 integration merged into llama.cpp (b4613)
2025-01-21 JSONSchemaBench released, including paper and MaskBench
2025-01-07 Guidance v0.2.0 released, using llguidance as the grammar engine

About

This library implements constrained decoding (also called constrained sampling or structured outputs) for Large Language Models (LLMs). It can enforce arbitrary context-free grammar on the output of LLM and is fast - on the order of 50μs of CPU time per token (for 128k tokenizer) with negligible startup costs.

Following grammar formats are supported:

a large subset of JSON schemas
regular expressions
context-free grammars in a variation of Lark format; with embedded JSON schemas and regular expressions
llguidance - internal (JSON-based) format; slowly being deprecated in favor of the Lark-like format

The internal format is most powerful (though Lark-like format is catching up, and there are plans to convert the libraries to use it) and can be generated by the following libraries:

Guidance (Python)
guidance.ts (TypeScript)
hopefully more to come!

The library can be used from:

Integrations

The library is currently integrated in:

Guidance - library for interacting with LLMs
OpenAI models - LLGuidance powers Structured Output (JSON Schema only)
llama.cpp - available via -DLLAMA_LLGUIDANCE=ON option for cmake; llama.cpp can be also used Guidance Python package
Chromium - merged, to be used for JSON Schema enforcement for window.ai in Chromium-based browsers
SGLang - use --grammar-backend llguidance; when passing Lark grammar make sure to prefix them with %llguidance {}, just as in llama.cpp
vLLM - V0 PR and V1 PR
LLGTRT - OpenAI-compatible REST server using NVIDIA’s TensorRT-LLM
mistral.rs
onnxruntime-genai

Technical details

See Making Structured Outputs Go Brrr for an overview of the library, including the design decisions, performance, and how it compares to other approaches.

Given a context-free grammar, a tokenizer, and a prefix of tokens, llguidance computes a token mask - a set of tokens from the tokenizer - that, when added to the current token prefix, can lead to a valid string in the language defined by the grammar. Mask computation takes approximately 50μs of single-core CPU time for a tokenizer with 128k tokens. While this timing depends on the exact grammar, it holds, for example, for grammars derived from JSON schemas. There is no significant startup cost.

The library implements a context-free grammar parser using Earley’s algorithm on top of a lexer based on derivatives of regular expressions. Mask computation is achieved by traversing the prefix tree (trie) of all possible tokens, leveraging highly optimized code.

Grammars can be also used to speed up decode via fast-forward tokens.

Comparison and performance

See MaskBench in JSON Schema Bench for detailed performance comparisons.

LM-format-enforcer and llama.cpp grammars are similar to llguidance in that they dynamically build token masks for every step of the decoding process. Both are significantly slower - the former due to clean Python code and the latter due to the lack of a lexer and use of a backtracking parser, which, while elegant, is inefficient.

Outlines builds an automaton from constraints and then pre-computes token masks for all automaton states, potentially making sampling fast but inherently limiting constraint complexity and introducing significant startup cost and memory overhead. Llguidance computes token masks on the fly and has essentially no startup cost. The lexer’s automata in llguidance are built lazily and are typically much smaller, as the context-free grammar imposes the top-level structure.

XGrammar follows an approach similar to llama.cpp (explicit stack-based, character-level parser) with additional pre-computation of certain token masks, similar to Outlines. The pre-computation often runs into seconds, and sometimes minutes. If the pre-computation works well for a given input, the masks are computed quickly (under 8μs in half of masks we tested), however if it doesn’t fit the particular input, the mask computation times can run to tens or hundreds of milliseconds.

In llguidance, the full mask computation for a typical JSON schema takes about 1.5ms (for 128k tokenizer). However, very often the “slicer” optimization applies, and thus the avarage mask computation in JSON Schema Bench (2.5M tokens, 10k schemas) is under 50μs, with less than 1% of masks taking longer than 1ms, and 0.001% taking longer than 10ms (but still shorter than 30ms). The optimization doesn’t involve any significant pre-computation.

Thus, with 16 cores and a 10ms forward pass, llguidance can handle batch sizes up to 3200 without slowing down the model. (Note that a 10ms forward pass for small batch sizes typically increases to 20ms+ for batch sizes of 100-200.)

Building

install rust; 1.87 or later

If you just need the C or Rust library (llguidance), check the parser directory.

For Python bindings:

install python 3.11 or later; very likely you’ll need a virtual env/conda
run ./scripts/install-deps.sh
to build and after any changes, run ./scripts/test-guidance.sh

This builds the Python bindings for the library and runs the tests (which mostly live in the Guidance repo - it will clone it).

Contributing

This project welcomes contributions and suggestions. Most contributions require you to agree to a Contributor License Agreement (CLA) declaring that you have the right to, and actually do, grant us the rights to use your contribution. For details, visit https://cla.opensource.microsoft.com.

When you submit a pull request, a CLA bot will automatically determine whether you need to provide a CLA and decorate the PR appropriately (e.g., status check, comment). Simply follow the instructions provided by the bot. You will only need to do this once across all repos using our CLA.

This project has adopted the Microsoft Open Source Code of Conduct. For more information see the Code of Conduct FAQ or contact opencode@microsoft.com with any additional questions or comments.

Trademarks

This project may contain trademarks or logos for projects, products, or services. Authorized use of Microsoft trademarks or logos is subject to and must follow Microsoft’s Trademark & Brand Guidelines. Use of Microsoft trademarks or logos in modified versions of this project must not cause confusion or imply Microsoft sponsorship. Any use of third-party trademarks or logos are subject to those third-party’s policies.