5 Module N_DIFF
gullradriel edited this page 2026-10-09 00:55:18 +02:00

DIFF: compare two texts line by line

Splits two texts into lines and produces the shortest edit script turning the first into the second, using Myers' greedy algorithm with a stored trace. More...

Structures

Name
struct N_DIFF_RESULT
edit script turning one text into another
struct N_DIFF_LINE
one line of an edit script

Functions

Name
N_STR * n_diff_to_unified(const N_DIFF_RESULT * result, size_t context)
Render an edit script as unified diff text.
void n_diff_result_free(N_DIFF_RESULT ** result)
Free an edit script and every line it holds.
N_DIFF_RESULT * n_diff_lines(const char * text_a, const char * text_b, size_t max_edits)
Compare two texts line by line.

Defines

Name
N_DIFF_NO_LINE
N_DIFF_LINE line_a / line_b value when the line has no counterpart there.
N_DIFF_MAX_EDITS_DEFAULT
n_diff_lines() default ceiling on the number of differing lines searched
N_DIFF_MAX_EDITS_CEILING
hard ceiling n_diff_lines() clamps max_edits to, keeping the worst case trace under about 64 MB
N_DIFF_INSERT
the line is only in the second text
N_DIFF_DELETE
the line is only in the first text
N_DIFF_CONTEXT_FULL
n_diff_to_unified() context asking for every common line, without hunk headers
N_DIFF_COMMON
the line is present in both texts

Detailed Description

Splits two texts into lines and produces the shortest edit script turning the first into the second, using Myers' greedy algorithm with a stored trace.

Unlike an index aligned comparison, inserting one line does not report every following line as changed.

Line splitting: texts are cut on '

'. A trailing newline closes the last line instead of opening an empty one, so "a\nb\n" and "a\nb" both yield two lines and compare equal. Carriage returns are kept, so a text that switched from LF to CRLF shows up as a difference rather than being silently normalised.

Cost control: the forward pass keeps one trace snapshot per edit, so memory grows with the square of the edit script length. n_diff_lines() therefore refuses to search past max_edits differing lines; when the two texts are further apart than that it falls back to reporting the whole differing region as deleted-then-inserted and sets N_DIFF_RESULT.truncated. The result is always a valid edit script, only a coarser one. Identical leading and trailing lines are matched before the search starts, so the limit applies to the part that actually differs.

Functions Documentation

function n_diff_to_unified

N_STR * n_diff_to_unified(
    const N_DIFF_RESULT * result,
    size_t context
)

Render an edit script as unified diff text.

Parameters:

  • result The edit script. Must not be NULL.
  • context Common lines kept around each change, or N_DIFF_CONTEXT_FULL.

Return: A new N_STR (free with free_nstr), or NULL on failure.

Each line is prefixed with ' ', '-' or '+'. With a finite context the output is cut into hunks introduced by a "@@ -a,b +c,d @@" header and common lines further than context away from a change are dropped; with N_DIFF_CONTEXT_FULL every line is emitted and no header is written.

function n_diff_result_free

void n_diff_result_free(
    N_DIFF_RESULT ** result
)

Free an edit script and every line it holds.

Parameters:

  • result Pointer to pointer, set to NULL on return.

function n_diff_lines

N_DIFF_RESULT * n_diff_lines(
    const char * text_a,
    const char * text_b,
    size_t max_edits
)

Compare two texts line by line.

Parameters:

  • text_a The first text. NULL is treated as empty.
  • text_b The second text. NULL is treated as empty.
  • max_edits Ceiling on the number of differing lines to search for, or 0 for N_DIFF_MAX_EDITS_DEFAULT, clamped to N_DIFF_MAX_EDITS_CEILING. Past it the differing region is reported coarsely and truncated is set.

Return: A new N_DIFF_RESULT the caller must release with n_diff_result_free(), or NULL on allocation failure. Two empty texts give an empty, valid result.

Macros Documentation

define N_DIFF_NO_LINE

#define N_DIFF_NO_LINE ((size_t)-1)

N_DIFF_LINE line_a / line_b value when the line has no counterpart there.

define N_DIFF_MAX_EDITS_DEFAULT

#define N_DIFF_MAX_EDITS_DEFAULT 1000

n_diff_lines() default ceiling on the number of differing lines searched

define N_DIFF_MAX_EDITS_CEILING

#define N_DIFF_MAX_EDITS_CEILING 4000

hard ceiling n_diff_lines() clamps max_edits to, keeping the worst case trace under about 64 MB

define N_DIFF_INSERT

#define N_DIFF_INSERT 2

the line is only in the second text

define N_DIFF_DELETE

#define N_DIFF_DELETE 1

the line is only in the first text

define N_DIFF_CONTEXT_FULL

#define N_DIFF_CONTEXT_FULL ((size_t)-1)

n_diff_to_unified() context asking for every common line, without hunk headers

define N_DIFF_COMMON

#define N_DIFF_COMMON 0

the line is present in both texts