diff options
Diffstat (limited to 'docs/handbook/cmark/reference-system.md')
| -rw-r--r-- | docs/handbook/cmark/reference-system.md | 307 |
1 files changed, 307 insertions, 0 deletions
diff --git a/docs/handbook/cmark/reference-system.md b/docs/handbook/cmark/reference-system.md new file mode 100644 index 0000000000..0e63b5c796 --- /dev/null +++ b/docs/handbook/cmark/reference-system.md @@ -0,0 +1,307 @@ +# cmark — Reference System + +## Overview + +The reference system (`references.c`, `references.h`) manages link reference definitions — the `[label]: URL "title"` constructs in CommonMark. During block parsing, reference definitions are extracted and stored. During inline parsing, reference links (`[text][label]` and `[text]`) look up these stored definitions. + +## Data Structures + +### Reference Entry + +```c +typedef struct cmark_reference { + struct cmark_reference *next; // Unused — leftover from old linked-list design + unsigned char *url; + unsigned char *title; + unsigned char *label; + unsigned int age; // Insertion order (for stable sorting) + unsigned int size; // Length of the label string +} cmark_reference; +``` + +Each reference stores: +- `label` — The normalized reference label (case-folded, whitespace-collapsed) +- `url` — The destination URL +- `title` — Optional title string (may be NULL) +- `age` — Monotonically increasing counter for insertion order +- `size` — Byte length of the label + +### Reference Map + +```c +struct cmark_reference_map { + cmark_mem *mem; + cmark_reference **refs; // Sorted array of reference pointers + unsigned int size; // Number of entries + unsigned int ref_size; // Cumulative size of all labels + URLs + titles + unsigned int max_ref_size; // Maximum allowed ref_size (anti-DoS limit) + cmark_reference *last; // Most recently added reference + unsigned int asize; // Allocated capacity of refs array +}; +``` + +The map uses a **sorted array with binary search** for lookup, not a hash table. This gives O(log n) lookup and O(n) insertion with shifting. + +### Anti-DoS Limiting + +The `ref_size` and `max_ref_size` fields prevent pathological inputs from causing excessive memory usage: + +```c +unsigned int max_ref_size; // Set to 100 * input length at parser init +unsigned int ref_size; // Sum of all label + url + title lengths +``` + +When `ref_size` exceeds `max_ref_size`, new reference additions are silently rejected. This prevents quadratic memory blowup from inputs with many reference definitions. + +## Label Normalization + +```c +static unsigned char *normalize_reference(cmark_mem *mem, + cmark_chunk *ref) { + cmark_strbuf normalized = CMARK_BUF_INIT(mem); + + if (ref == NULL) return NULL; + + if (ref->len == 0) return NULL; + + cmark_utf8proc_case_fold(&normalized, ref->data, ref->len); + cmark_strbuf_trim(&normalized); + cmark_strbuf_normalize_whitespace(&normalized); + + return cmark_strbuf_detach(&normalized); +} +``` + +The normalization process (per CommonMark spec): +1. **Case fold** — Uses Unicode case folding (not simple lowercasing), via `cmark_utf8proc_case_fold()` +2. **Trim** — Remove leading and trailing whitespace +3. **Collapse whitespace** — Replace runs of whitespace with a single space + +This means `[Foo Bar]`, `[FOO BAR]`, and `[foo bar]` all normalize to the same label. + +## Reference Creation + +```c +static void cmark_reference_create(cmark_reference_map *map, + cmark_chunk *label, + cmark_chunk *url, + cmark_chunk *title) { + cmark_reference *ref; + unsigned char *reflabel = normalize_reference(map->mem, label); + + if (reflabel == NULL) return; + + // Anti-DoS: check cumulative size limit + if (map->ref_size > map->max_ref_size) { + map->mem->free(reflabel); + return; + } + + ref = (cmark_reference *)map->mem->calloc(1, sizeof(*ref)); + ref->label = reflabel; + ref->url = cmark_clean_url(map->mem, url); + ref->title = cmark_clean_title(map->mem, title); + ref->age = map->size; + ref->size = (unsigned int)strlen((char *)reflabel); + + // Track cumulative size + map->ref_size += ref->size; + if (ref->url) map->ref_size += (unsigned int)strlen((char *)ref->url); + if (ref->title) map->ref_size += (unsigned int)strlen((char *)ref->title); + + // Add to array + if (map->size >= map->asize) { + // Grow array (double capacity) + map->asize = map->asize ? 2 * map->asize : 8; + map->refs = (cmark_reference **)map->mem->realloc( + map->refs, map->asize * sizeof(cmark_reference *)); + } + map->refs[map->size] = ref; + map->size++; + map->last = ref; +} +``` + +References are appended to the array in insertion order. The array is NOT kept sorted during insertion — it's sorted once at lookup time (lazily). + +## Reference Lookup + +```c +cmark_reference *cmark_reference_lookup(cmark_reference_map *map, + cmark_chunk *label) { + if (label->len < 1 || label->len > MAX_LINK_LABEL_LENGTH) return NULL; + if (map == NULL || map->size == 0) return NULL; + + unsigned char *norm = normalize_reference(map->mem, label); + if (norm == NULL) return NULL; + + // Sort on first lookup + if (!map->sorted) { + qsort(map->refs, map->size, sizeof(cmark_reference *), refcmp); + // Remove duplicates (keep first occurrence) + // ... + map->sorted = true; + } + + // Binary search + cmark_reference **found = (cmark_reference **)bsearch( + &norm, map->refs, map->size, sizeof(cmark_reference *), refcmp); + + map->mem->free(norm); + return found ? *found : NULL; +} +``` + +### Lazy Sorting + +The reference map is NOT sorted during insertion. On the first call to `cmark_reference_lookup()`, the array is sorted using `qsort()` with a comparison function: + +```c +static int refcmp(const void *a, const void *b) { + const cmark_reference *refa = *(const cmark_reference **)a; + const cmark_reference *refb = *(const cmark_reference **)b; + int cmp = strcmp((char *)refa->label, (char *)refb->label); + if (cmp != 0) return cmp; + // Tie-break by age (earlier wins) + if (refa->age < refb->age) return -1; + if (refa->age > refb->age) return 1; + return 0; +} +``` + +When labels collide (same normalized label), the first definition wins (lowest `age`). + +After sorting, duplicates are removed — entries with the same label as the preceding entry are freed: +```c +unsigned int write = 0; +for (unsigned int read = 0; read < map->size; read++) { + if (write > 0 && + strcmp((char *)map->refs[write-1]->label, + (char *)map->refs[read]->label) == 0) { + // Duplicate — free it + cmark_reference_free(map->mem, map->refs[read]); + } else { + map->refs[write++] = map->refs[read]; + } +} +map->size = write; +``` + +### Binary Search + +After sorting and deduplication, lookups use standard `bsearch()`, giving O(log n) lookup time. + +## URL and Title Cleaning + +When creating references, URLs and titles are cleaned: + +### `cmark_clean_url()` +```c +unsigned char *cmark_clean_url(cmark_mem *mem, cmark_chunk *url); +``` +- Removes surrounding `<` and `>` if present (angle-bracket URLs) +- Unescapes backslash escapes +- Decodes entity references +- Percent-encodes non-URL-safe characters via `houdini_escape_href()` + +### `cmark_clean_title()` +```c +unsigned char *cmark_clean_title(cmark_mem *mem, cmark_chunk *title); +``` +- Strips the first and last character (the delimiter: `"`, `'`, or `(`) +- Unescapes backslash escapes +- Decodes entity references + +## Integration with Parser + +### Extraction during Block Parsing + +Reference definitions are extracted when paragraphs are finalized: + +```c +// In blocks.c, during paragraph finalization: +while (cmark_parse_reference_inline(parser->mem, &node_content, + parser->refmap)) { + // Keep parsing references from the start of the paragraph +} +``` + +### `cmark_parse_reference_inline()` + +```c +int cmark_parse_reference_inline(cmark_mem *mem, cmark_strbuf *input, + cmark_reference_map *refmap) { + // Parse: [label]: destination "title" + // Returns 1 if a reference was found and consumed, 0 otherwise + subject subj; + // ... initialize subject on the input buffer + // Parse label + cmark_chunk lab = cmark_chunk_literal(""); + cmark_chunk url = cmark_chunk_literal(""); + cmark_chunk title = cmark_chunk_literal(""); + + if (!link_label(&subj, &lab) || lab.len == 0) return 0; + if (peek_char(&subj) != ':') return 0; + advance(&subj); + spnl(&subj); // skip spaces and up to one newline + if (!manual_scan_link_url(&subj, &url)) return 0; + // ... parse optional title + // ... validate: rest of line must be blank + cmark_reference_create(refmap, &lab, &url, &title); + // Remove consumed bytes from input + return 1; +} +``` + +The parser repeatedly calls this function on paragraph content. Each successful parse removes the reference definition from the paragraph. If the entire paragraph consists of reference definitions, the paragraph node is removed from the AST. + +### Lookup during Inline Parsing + +In `inlines.c`, when a potential reference link is found: + +```c +cmark_reference *ref = cmark_reference_lookup(subj->refmap, &raw_label); +if (ref) { + // Create link node with ref->url and ref->title +} +``` + +## Label Length Limit + +```c +#define MAX_LINK_LABEL_LENGTH 999 +``` + +Reference labels longer than 999 characters are rejected, per the CommonMark spec. + +## Map Lifecycle + +```c +cmark_reference_map *cmark_reference_map_new(cmark_mem *mem); +void cmark_reference_map_free(cmark_reference_map *map); +``` + +The map is created during parser initialization and freed when the parser is freed. The AST's reference links have already been resolved and store their own copies of URL and title — the reference map is not needed after parsing. + +### Cleanup + +```c +void cmark_reference_map_free(cmark_reference_map *map) { + if (map == NULL) return; + for (unsigned int i = 0; i < map->size; i++) { + cmark_reference_free(map->mem, map->refs[i]); + } + map->mem->free(map->refs); + map->mem->free(map); +} +``` + +Each reference and its strings (label, url, title) are freed, then the array and map struct are freed. + +## Cross-References + +- [references.c](../../cmark/src/references.c) — Implementation +- [references.h](../../cmark/src/references.h) — Data structures +- [block-parsing.md](block-parsing.md) — Reference extraction during paragraph finalization +- [inline-parsing.md](inline-parsing.md) — Reference lookup during link resolution +- [utf8-handling.md](utf8-handling.md) — Case folding used in label normalization |