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...

Data Structures
struct	N_DIFF_LINE
	one line of an edit script More...
struct	N_DIFF_RESULT
	edit script turning one text into another More...

Macros
#define	N_DIFF_COMMON 0
	the line is present in both texts
#define	N_DIFF_CONTEXT_FULL ((size_t)-1)
	n_diff_to_unified() context asking for every common line, without hunk headers
#define	N_DIFF_DELETE 1
	the line is only in the first text
#define	N_DIFF_INSERT 2
	the line is only in the second text
#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_MAX_EDITS_DEFAULT 1000
	n_diff_lines() default ceiling on the number of differing lines searched
#define	N_DIFF_NO_LINE ((size_t)-1)
	N_DIFF_LINE line_a / line_b value when the line has no counterpart there.

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

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.

Data Structure Documentation

◆ N_DIFF_LINE

struct N_DIFF_LINE

one line of an edit script

Examples: ex_diff.c.

Definition at line 85 of file n_diff.h.

Collaboration diagram for N_DIFF_LINE:

Data Fields
size_t	line_a	zero based position in the first text, or N_DIFF_NO_LINE
size_t	line_b	zero based position in the second text, or N_DIFF_NO_LINE
int	op	N_DIFF_COMMON, N_DIFF_DELETE or N_DIFF_INSERT.
char *	text	line content, without its newline, owned by the result

◆ N_DIFF_RESULT

struct N_DIFF_RESULT

edit script turning one text into another

Examples: ex_diff.c.

Definition at line 97 of file n_diff.h.

Collaboration diagram for N_DIFF_RESULT:

Data Fields
LIST *	lines	LIST of N_DIFF_LINE*, in output order.
size_t	nb_common	number of N_DIFF_COMMON lines
size_t	nb_deleted	number of N_DIFF_DELETE lines
size_t	nb_inserted	number of N_DIFF_INSERT lines
int	truncated	1 when the edit limit was hit and the differing region was reported as one delete run followed by one insert run

Macro Definition Documentation

◆ N_DIFF_COMMON

#define N_DIFF_COMMON 0

the line is present in both texts

Definition at line 65 of file n_diff.h.

Referenced by _emit(), _myers(), n_diff_lines(), and n_diff_to_unified().

◆ 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

Examples: ex_diff.c.

Definition at line 75 of file n_diff.h.

Referenced by expect_unified(), main(), and n_diff_to_unified().

◆ N_DIFF_DELETE

#define N_DIFF_DELETE 1

the line is only in the first text

Examples: ex_diff.c.

Definition at line 67 of file n_diff.h.

Referenced by _emit(), _myers(), _op_char(), main(), n_diff_lines(), and n_diff_to_unified().

◆ N_DIFF_INSERT

#define N_DIFF_INSERT 2

the line is only in the second text

Examples: ex_diff.c.

Definition at line 69 of file n_diff.h.

Referenced by _myers(), _op_char(), main(), n_diff_lines(), and n_diff_to_unified().

◆ 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

Definition at line 82 of file n_diff.h.

Referenced by n_diff_lines().

◆ N_DIFF_MAX_EDITS_DEFAULT

#define N_DIFF_MAX_EDITS_DEFAULT 1000

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

Definition at line 78 of file n_diff.h.

Referenced by n_diff_lines().

◆ 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.

Examples: ex_diff.c.

Definition at line 72 of file n_diff.h.

Referenced by _myers(), main(), and n_diff_lines().

Function Documentation

◆ 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.

Returns: 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.

Definition at line 252 of file n_diff.c.

References _emit(), _myers(), _text_free(), _text_load(), DIFF_TEXT::count, DIFF_TEXT::line, N_DIFF_RESULT::lines, Malloc, MAX_LIST_ITEMS, N_DIFF_COMMON, N_DIFF_DELETE, N_DIFF_INSERT, N_DIFF_MAX_EDITS_CEILING, N_DIFF_MAX_EDITS_DEFAULT, N_DIFF_NO_LINE, n_diff_result_free(), new_generic_list(), and N_DIFF_RESULT::truncated.

Referenced by expect_unified(), and main().

Here is the call graph for this function:

Here is the caller graph for this 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.

Definition at line 333 of file n_diff.c.

References FreeNoLog, and list_destroy().

Referenced by expect_unified(), main(), and n_diff_lines().

Here is the call graph for this function:

Here is the caller graph for this 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.

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.

Parameters

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

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

Definition at line 391 of file n_diff.c.

References __n_assert, _out_finish(), _out_line(), _out_str(), DIFF_OUT::buf, DIFF_HEADER_BUF, FreeNoLog, last, line(), N_DIFF_RESULT::lines, list_foreach, Malloc, N_DIFF_COMMON, N_DIFF_CONTEXT_FULL, N_DIFF_DELETE, N_DIFF_INSERT, LIST::nb_items, and N_DIFF_LINE::op.

Referenced by expect_unified(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

Data Structures

Macros

Functions

Detailed Description

Data Structure Documentation

◆ N_DIFF_LINE

◆ N_DIFF_RESULT

Macro Definition Documentation

◆ N_DIFF_COMMON

◆ N_DIFF_CONTEXT_FULL

◆ N_DIFF_DELETE

◆ N_DIFF_INSERT

◆ N_DIFF_MAX_EDITS_CEILING

◆ N_DIFF_MAX_EDITS_DEFAULT

◆ N_DIFF_NO_LINE

Function Documentation

◆ n_diff_lines()

◆ n_diff_result_free()

◆ n_diff_to_unified()