noir_XPath

A Noir library implementing XPath 2.0 functions and operators required by SPARQL 1.1, targeting zero-knowledge query proofs.

📚 Documentation

• VENDOR.md - Authoritative, up-to-date function inventory, gate-count tables, and known gaps
• TESTING.md - Test suite layout, how to run it, and the upstream (old jeswr/noir_XPath) → current test mapping
• SPARQL_COVERAGE.md - Mapping of SPARQL 1.1 functions to implementation status
• ARCHITECTURE.md - Technical architecture and design decisions
• scripts/README.md - Test generation from qt3tests

Overview

This library provides Noir implementations of XPath/XQuery functions as defined in XQuery 1.0 and XPath 2.0 Functions and Operators that are required by SPARQL 1.1 Query Language.

Installation

Add to your Nargo.toml:

[dependencies]
xpath = { git = "https://github.com/sparq-org/noir_XPath", tag = "v0.3.0", directory = "xpath" }

The xpath package depends on sparq_ieee754 (vendored under vendor/ieee754/), a vendored json_parser (under vendor/json_parser/), and the vendored noir-lang sha256 / sha512 digest crates (under vendor/sha256/ and vendor/sha512/); all resolve as path dependencies inside this repository.

Features

Currently Implemented

• Boolean Operations: fn:not, op:boolean-equal, op:boolean-less-than, op:boolean-greater-than, logical AND/OR

• Numeric Operations:

  • Integer: add, subtract, multiply, divide (div yields the xs:decimal quotient as a double, idiv truncates -- distinct ops), mod, abs, round, ceil, floor, min, max
  • Comparisons: equal, less-than, greater-than

• String Operations:

  • Basic: string-length, substring, upper-case, lower-case
  • Search: starts-with, ends-with, contains
  • Manipulation: substring-before, substring-after, concat

• DateTime Operations:

  • Construction: from epoch microseconds, from components
  • Component extraction: year, month, day, hours, minutes, seconds, microseconds, timezone
  • Comparisons: equal, less-than, greater-than
  • Efficient single-Field representation (epoch microseconds)

• Duration Operations:

  • Construction: from microseconds, from components
  • Extraction: days, hours, minutes, seconds
  • Arithmetic: add, subtract, multiply, divide, negate
  • DateTime arithmetic: add/subtract duration, compute difference
  • Comparisons: equal, less-than, greater-than

• Sequence/Aggregate Functions:

  • Tests: is_empty, exists, count
  • Aggregates: sum, avg, min, max (for integer arrays)
  • Boolean aggregates: all_true, any_true, count_true
  • Partial array operations (with explicit length)

• Comparison Utilities: Generic value comparison with Eq/Ord traits

• Float / double operations: IEEE-754 f32/f64 arithmetic, comparison, round/floor/ceil/abs, and casts, on the in-repo sparq_ieee754 library (see VENDOR.md for the gate-count tables)

• Bounded string / regex helpers: encode_for_uri, and a bounded, circuit-friendly regex subset (matches_literal/anchored/prefix, char-class matchers, replace_literal) — full fn:matches/fn:replace remain stubbed (infeasible as fixed-size data-oblivious circuits)

• SPARQL-namespace builtins: lang_matches (RFC 4647 basic filtering), sha256_hex / sha384_hex / sha512_hex (canonical lowercase-hex digests on the vendored noir-lang cores; MD5/SHA-1 deliberately omitted as broken), tz_from_datetime (TZ() lexical part: "Z" / "±HH:MM" / ""), group_concat (bounded GROUP_CONCAT string core), and sample_int (deterministic SAMPLE)

🔮 Future (Planned)

• Full regex functions (REGEX, REPLACE — needs a bounded-NFA ZK-regex strategy; tracked as sq-j8shy)
• Decimal type support (xsd:decimal exact arithmetic — tracked as sq-n5e7p; currently approximated in IEEE 754 double precision)
• Codepoint-positional SUBSTR for multi-byte UTF-8 (tracked as sq-hjvte)

SPARQL 1.1 Coverage

This library implements XPath 2.0 functions and operators required by SPARQL 1.1.

Quick Summary:

• ✅ 60+ functions fully implemented (boolean, numeric, datetime, duration, aggregates, string functions)
• ✅ String operations fully implemented (string-length, starts-with, ends-with, contains, substring, substring-before, substring-after, upper-case, lower-case, concat, normalize-space, translate, encode-for-uri, langMatches, etc. — builders return byte array tuples)
• ✅ Float/double support on the vendored sparq_ieee754 IEEE 754 library
• ✅ SHA256/SHA384/SHA512 with lowercase-hex output (vendored noir-lang cores); ❌ MD5/SHA1 deliberately omitted (broken)
• 🔮 Full regex deferred (bounded subset implemented; sq-j8shy)
• ❌ RAND/NOW not feasible (non-deterministic in ZK)

For complete function mapping, see SPARQL_COVERAGE.md

✅ Fully Implemented

• Boolean operations: All boolean functions and operators (fn:not, logical-and, logical-or, comparisons)
• Integer numeric operations: All arithmetic and comparison operators for integers
• String operations: All XPath string functions including substring extraction (substring, substring-before, substring-after), case conversion (upper-case, lower-case), comparison (starts-with, ends-with, contains), and manipulation (concat, normalize-space, translate, encode-for-uri). All return byte array tuples ([u8; N], u32) instead of string types.
• DateTime operations: Component extraction (year, month, day, hours, minutes, seconds, timezone, TZ), comparisons, and arithmetic
• Duration operations: All dayTimeDuration operations including arithmetic and comparisons
• Aggregate functions: COUNT, SUM, AVG, MIN, MAX, SAMPLE for integer sequences; GROUP_CONCAT string-join core
• SPARQL hash digests: SHA256, SHA384, SHA512 with canonical lowercase-hex output (MD5/SHA1 deliberately omitted as broken)
• langMatches: RFC 4647 basic filtering

⚠️ Partial Support

• Aggregates: integer sequences only (float/double aggregate lanes not yet provided)
• Regex: bounded circuit-friendly subset (matches_literal/anchored/prefix, char-class matchers, replace_literal); full fn:matches/fn:replace deferred (sq-j8shy)
• TZ(): implemented, with a representation caveat — XsdDateTime has no absent-timezone flag, so absence must be encoded as the TZ_OFFSET_NONE sentinel (see SPARQL_COVERAGE.md §17.4.5)

❌ Not Implemented

• Hash functions MD5, SHA1: deliberately omitted, permanently — both are cryptographically broken and there is no sound Noir implementation to vendor (SHA256/SHA384/SHA512 ARE implemented; see SPARQL_COVERAGE.md §17.4.6)
• RDF term functions: isIRI, isBlank, isLiteral, str, lang, datatype, IRI, BNODE, etc.
  • Reason: Out of scope for XPath function library
• Non-deterministic functions: RAND(), NOW()
  • Reason: Not meaningful in deterministic zero-knowledge proof context
  • Alternative: These values should be provided as inputs to the circuit

For a complete mapping of all SPARQL 1.1 functions to their implementation status, see SPARQL_COVERAGE.md. Remaining deferred features are tracked as issues rather than an in-repo roadmap document.

Usage

Boolean Operations

use dep::xpath::{fn_not, logical_and, logical_or, boolean_equal};

fn example() {
    let result = logical_and(true, fn_not(false));  // true
    assert(boolean_equal(result, true));
}

String Operations

use dep::xpath::{
    string_length,
    starts_with,
    ends_with,
    contains,
};

fn example() {
    let s: str<11> = "Hello World";
    
    // These functions work correctly (return boolean/numeric values):
    assert(string_length::<11>(s) == 11);
    assert(starts_with::<11, 5>(s, "Hello"));
    assert(ends_with::<11, 5>(s, "World"));
    assert(contains::<11, 5>(s, "lo Wo"));
}

Note: All string functions that create new strings — substring, substring-before, substring-after, upper_case, lower_case, concat, normalize_space, translate, etc. — are exported and return ([u8; N], u32) byte array tuples. Substring byte-position caveat: substring() uses BYTE positions in logical content, exact vs XPath F&O spec only for ASCII. For multi-byte UTF-8, codepoint-positional variant is not implemented (tracked in sq-hjvte). Comparison functions (starts-with, ends-with, contains) operate on logical string content (bytes before first NUL terminator), not buffer capacity.

Numeric Operations

use dep::xpath::{
    numeric_add_int, 
    numeric_multiply_int,
    numeric_mod_int,
    abs_int,
    min_int,
    max_int,
};

fn example() {
    // Integer operations
    let sum = numeric_add_int(5, 3);  // 8
    let product = numeric_multiply_int(-5, 3);  // -15
    let remainder = numeric_mod_int(7, 3);  // 1
    let absolute = abs_int(-42);  // 42
    let minimum = min_int(5, 3);  // 3
    let maximum = max_int(5, 3);  // 5
}

DateTime Operations

use dep::xpath::{
    XsdDateTime,
    datetime_from_components,
    datetime_from_components_with_tz,
    year_from_datetime,
    month_from_datetime,
    datetime_less_than,
    timezone_from_datetime,
};

fn example() {
    // Create a DateTime: 2024-06-15T14:30:45.123456Z (UTC)
    let dt = datetime_from_components(2024, 6, 15, 14, 30, 45, 123456);
    
    // Create a DateTime with timezone: 2024-06-15T14:30:45.123456-05:00
    let dt_tz = datetime_from_components_with_tz(2024, 6, 15, 14, 30, 45, 123456, -300);
    
    // Extract components
    assert(year_from_datetime(dt) == 2024);
    assert(month_from_datetime(dt) == 6);
    
    // Extract timezone as duration (SPARQL TIMEZONE function)
    let tz = timezone_from_datetime(dt_tz);
    // tz represents -PT5H (negative 5 hours)
    
    // Compare dates
    let dt_earlier = datetime_from_components(2024, 1, 1, 0, 0, 0, 0);
    assert(datetime_less_than(dt_earlier, dt));
}

Duration Operations

use dep::xpath::{
    duration_from_components,
    datetime_add_duration,
    datetime_difference,
    days_from_duration,
};

fn example() {
    // Create a duration: 1 day, 2 hours, 30 minutes
    let dur = duration_from_components(false, 1, 2, 30, 0, 0);
    
    // Add duration to datetime
    let dt = datetime_from_components(2024, 1, 1, 0, 0, 0, 0);
    let dt_later = datetime_add_duration(dt, dur);
    
    // Compute difference between datetimes
    let diff = datetime_difference(dt_later, dt);
    assert(days_from_duration(diff) == 1);
}

Sequence/Aggregate Operations

use dep::xpath::{sum_int, avg_int, min_int_seq, max_int_seq, count};

fn example() {
    let values: [i64; 5] = [10, 20, 30, 40, 50];
    
    assert(count(values) == 5);
    assert(sum_int(values) == 150);
    assert(avg_int(values) == 30);
    // fn:min/fn:max return (value, present); present == false is the
    // empty sequence (fn:min(()) = () per F&O -- never an assert, so an
    // empty input keeps the circuit satisfiable). fn:avg over an empty
    // sequence remains an error in this library.
    assert(min_int_seq(values) == (10, true));
    assert(max_int_seq(values) == (50, true));
    let empty: [i64; 0] = [];
    assert(min_int_seq(empty) == (0, false));
}

Architecture

The library uses efficient representations optimized for zero-knowledge circuits:

• DateTime: Single Field storing UTC epoch microseconds

  • Minimizes constraint count
  • Efficient single-field comparisons
  • Component extraction computed on-demand

• Floats: IEEE 754 bit representation via noir_IEEE754

See ARCHITECTURE.md for details.

Project Structure

noir_XPath/
├── xpath/                    # Main library
│   └── src/
│       ├── lib.nr           # Module exports
│       ├── types.nr         # Type definitions (XsdDateTime, XsdDayTimeDuration)
│       ├── boolean.nr       # Boolean operations
│       ├── numeric.nr       # Numeric operations
│       ├── datetime.nr      # DateTime operations
│       ├── duration.nr      # Duration operations
│       ├── sequence.nr      # Sequence/aggregate functions
│       ├── comparison.nr    # Comparison utilities
│       ├── string.nr        # String operations
│       ├── regex.nr         # Bounded regex subset
│       └── hash.nr          # SHA-2 digests + Pedersen content hash
├── xpath_unit_tests/        # Unit tests
├── test_packages/           # Auto-generated tests from qt3tests
└── scripts/                 # Test generation scripts
    ├── generate_tests.py    # Generate Noir tests from W3C qt3tests
    └── README.md            # Script documentation

Testing

Requires the pinned toolchain nargo 1.0.0-beta.21.

# Run the REAL suite: library inline tests + unit-test bin + the real
# (non-stub) test_packages, honoring the KNOWN_FAILING skip list.
# (Do NOT run `nargo test --workspace` from the root: it would include the
# ~247 stub-wired packages that assert(false) BY DESIGN and always fail.)
bash scripts/run_real_tests.sh

# Or run individual real targets directly:
nargo test --package xpath                # library inline tests
nargo test --package xpath_unit_tests     # dedicated unit-test bin

For the test layout, the REAL-vs-stub partition, the KNOWN_FAILING semantics, and the upstream→current test mapping, see TESTING.md.

Test Generation

Generate Noir tests from the W3C qt3tests suite:

cd scripts
python generate_tests.py

# Or for specific functions
python generate_tests.py --functions "fn:abs,op:numeric-add"

See scripts/README.md for details.

Dependencies

All are vendored in-repo (path dependencies) so the workspace builds hermetically:

• sparq_ieee754 (vendor/ieee754/) - IEEE 754 f32/f64 operations; developed in sparq-org/sparq under zk/ieee754. See vendor/ieee754/VENDOR-PROVENANCE.md.
• json_parser (vendor/json_parser/) - vendored copy of noir-lang/noir_json_parser. See vendor/json_parser/VENDOR-PROVENANCE.md.
• sha256 (vendor/sha256/) - vendored noir-lang/sha256 v0.3.0 (SPARQL SHA256 digest core). See vendor/sha256/VENDOR-PROVENANCE.md.
• sha512 (vendor/sha512/) - vendored noir-lang/sha512 (SPARQL SHA384/SHA512 digest cores). See vendor/sha512/VENDOR-PROVENANCE.md.

References

• SPARQL 1.1 Query Language
• XQuery 1.0 and XPath 2.0 Functions and Operators
• W3C QT3 Test Suite

Extending for Additional Functions

To add support for additional XPath/SPARQL functions:

1. Implement the function in the appropriate module (numeric.nr, datetime.nr, etc.)
2. Export from lib.nr to make it part of the public API
3. Add tests:
   • Inline tests in the module
   • Comprehensive tests in xpath_unit_tests/
   • Map to qt3tests in scripts/generate_tests.py (if applicable)
4. Update documentation:
   • Add to SPARQL_COVERAGE.md
   • Add example to README.md
   • Update TESTING.md

See TESTING.md for detailed testing guidelines.

License

MIT