yyjson-recursion-limit.patch

Overview

This patch enhances the **yyjson** C JSON parsing library by introducing a configurable recursion depth limit during JSON parsing. The primary purpose is to prevent unbounded recursion when parsing deeply nested JSON arrays or objects, which can lead to stack overflow or excessive resource consumption.

The patch defines a new macro `YYJSON_READER_CONTAINER_RECURSION_LIMIT` (defaulting to 1024) that limits the maximum allowed recursion depth for nested JSON containers (arrays and objects) during parsing. When the parser exceeds this depth, it triggers a specific parsing error (`YYJSON_READ_ERROR_RECURSION_DEPTH`), allowing the caller to detect and handle excessively deep JSON structures gracefully.

Detailed Explanation

Changes in yyjson.c

• Definition of Recursion Limit Macro

  #ifndef YYJSON_READER_CONTAINER_RECURSION_LIMIT
  #define YYJSON_READER_CONTAINER_RECURSION_LIMIT 1024
  #endif
  

  This macro sets the maximum allowed recursion depth for JSON arrays and objects during parsing. Users can override this limit by defining the macro before including or compiling yyjson.c.

• New Error Handling Label

  fail_recursion:
      return_err(cur, RECURSION_DEPTH, "array and object recursion depth exceeded");
  

  When the recursion limit is exceeded, the parser jumps to this label to return a precise error.

• Tracking Container Depth

  Within the main recursive parsing functions (read_root_minify() and read_root_pretty()), a local variable:

  u32 container_depth = 0;
  

  is introduced to track the current recursion depth of nested containers (arrays or objects).

• Incrementing and Decrementing Depth

  At the start of parsing a new array or object (arr_begin: and obj_begin: labels), the parser increments container_depth and checks against the recursion limit:

  container_depth++;
  if (unlikely(container_depth >= YYJSON_READER_CONTAINER_RECURSION_LIMIT)) {
      goto fail_recursion;
  }
  

  At the end of parsing an array or object (arr_end: and obj_end:), it decrements container_depth:

  container_depth--;
  

  This ensures the parser keeps an accurate count of recursion levels as it descends and ascends in the JSON structure.

• Error Code for Recursion Limit

  The patch adds a new error code constant in yyjson.h:

  /** Document exceeded YYJSON_READER_CONTAINER_RECURSION_LIMIT.  */
  static const yyjson_read_code YYJSON_READ_ERROR_RECURSION_DEPTH = 14;
  

  This error code is returned when the recursion depth limit is reached.

Key Entities and Functions

Macro

• YYJSON_READER_CONTAINER_RECURSION_LIMIT

  • Type: uint32_t macro

  • Default: 1024

  • Purpose: Sets the maximum allowed recursion depth during parsing of JSON arrays and objects.

  • Usage: Can be overridden by defining before compilation to allow deeper or shallower recursion limits.

Error Code

• YYJSON_READ_ERROR_RECURSION_DEPTH (14)

  • Type: yyjson_read_code constant

  • Meaning: The JSON document exceeded the configured container recursion limit.

  • Usage: Returned by the parser on recursion depth overflow.

Functions/Methods (in yyjson.c)

• *read_root_minify(u8 hdr, ...) and *read_root_pretty(u8 hdr, ...)

  These internal static inline functions parse JSON data in compact or pretty formats, respectively. The patch adds:

  • A local variable to track recursion depth.

  • Checks to enforce the recursion depth limit when entering arrays or objects.

  • Error handling for recursion overflow.

Parameters (common to both)

• u8 *hdr: Pointer to the input JSON buffer with padding.

• Various local variables and context pointers to track parsing state.

Return Value

• Returns a pointer to a yyjson_doc on success or NULL with an error set on failure.

Usage Example (internal)

// At start of parsing an array
container_depth++;
if (container_depth >= YYJSON_READER_CONTAINER_RECURSION_LIMIT) {
    goto fail_recursion;
}
// Parse array elements...

// At end of parsing an array
container_depth--;

Implementation Details and Algorithms

• Recursion Depth Tracking

  The parser uses a simple integer counter (container_depth) to track how deep the current parsing stack is nested within arrays or objects.

• Fail-Fast Error Handling

  Upon exceeding the recursion limit, the parser immediately jumps to the fail_recursion label, returning a specific error code and message. This prevents excessive stack usage and provides a clear diagnostic to the caller.

• Integration with Existing Error Mechanism

  The new recursion error is integrated into the existing error reporting system (return_err) used throughout the parser, making it consistent with other parsing errors like unexpected characters or content.

• Configurable Limit

  By defining YYJSON_READER_CONTAINER_RECURSION_LIMIT externally, applications using yyjson can tailor recursion limits based on their memory and safety requirements.

Interaction with Other Parts of the System

• JSON Parsing Workflow

  This patch modifies the core JSON parsing functions in yyjson.c (read_root_minify and read_root_pretty), which are ultimately called by public parsing APIs such as yyjson_read_opts(). The recursion limit affects these low-level parsing routines directly.

• Error Reporting

  The new error code (YYJSON_READ_ERROR_RECURSION_DEPTH) is added to the enumerated error codes in yyjson.h. Callers of the parsing API can check this error code to detect recursion depth errors and handle them appropriately (e.g., reject deeply nested JSON).

• Memory Safety

  By limiting recursion, the patch prevents stack overflows potentially caused by malicious or malformed JSON documents with extremely deep nesting.

• Configuration

  Users of the yyjson library (including the Rust backend or Python bindings) can define or override the recursion limit macro to balance between permissiveness and protection against deep nesting.

Usage Example

#include "yyjson.h"

// Optionally override recursion limit before including yyjson.c
#define YYJSON_READER_CONTAINER_RECURSION_LIMIT 500

int main() {
    const char *json = "[[[...]]]";  // Deeply nested JSON
    yyjson_read_err err;
    yyjson_doc *doc = yyjson_read(json, strlen(json), 0, &err);
    if (!doc) {
        if (err.code == YYJSON_READ_ERROR_RECURSION_DEPTH) {
            printf("JSON parsing failed: recursion depth exceeded\n");
        } else {
            printf("JSON parsing failed: %s\n", err.msg);
        }
        return 1;
    }
    // Use doc...
    yyjson_doc_free(doc);
    return 0;
}

Mermaid Diagram: Flow of Recursion Depth Checking in JSON Parsing

flowchart TD
    Start[Start Parsing Container]
    IncDepth[Increment container_depth]
    CheckLimit{container_depth >= YYJSON_READER_CONTAINER_RECURSION_LIMIT?}
    FailRecursion[Return RECURSION_DEPTH Error]
    ParseElements[Parse Array/Object Elements]
    DecDepth[Decrement container_depth]
    ReturnSuccess[Return Parsed Container]

    Start --> IncDepth --> CheckLimit
    CheckLimit -- Yes --> FailRecursion
    CheckLimit -- No --> ParseElements --> DecDepth --> ReturnSuccess

This flowchart shows how recursion depth is incremented when entering a container, checked against the limit, and decremented after parsing, with error handling if the limit is exceeded.

Summary

• Adds a configurable recursion depth limit to the yyjson JSON parser.

• Prevents infinite or excessive recursion during parsing of nested arrays and objects.

• Introduces a new error code (YYJSON_READ_ERROR_RECURSION_DEPTH) to signal this condition.

• Integrates recursion depth tracking in core parsing functions with fail-fast error handling.

• Enhances parser robustness and security against maliciously deep JSON documents.

• Allows users to override default recursion limits per their application needs.

This patch is a critical safeguard improvement for yyjson, enhancing the parser's resilience and configurability without impacting normal parsing performance for typical JSON documents.