1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
/* Generic infrastructure to implement various diff algorithms. */
/*
* Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
#ifndef MAX
#define MAX(A,B) ((A)>(B)?(A):(B))
#endif
#ifndef MIN
#define MIN(A,B) ((A)<(B)?(A):(B))
#endif
static inline bool
diff_range_empty(const struct diff_range *r)
{
return r->start == r->end;
}
static inline bool
diff_ranges_touch(const struct diff_range *a, const struct diff_range *b)
{
return (a->end >= b->start) && (a->start <= b->end);
}
static inline void
diff_ranges_merge(struct diff_range *a, const struct diff_range *b)
{
*a = (struct diff_range){
.start = MIN(a->start, b->start),
.end = MAX(a->end, b->end),
};
}
static inline int
diff_range_len(const struct diff_range *r)
{
if (!r)
return 0;
return r->end - r->start;
}
/* Indicate whether two given diff atoms match. */
int
diff_atom_same(bool *same,
const struct diff_atom *left,
const struct diff_atom *right);
/* A diff chunk represents a set of atoms on the left and/or a set of atoms on
* the right.
*
* If solved == false:
* The diff algorithm has divided the source file, and this is a chunk that the
* inner_algo should run on next.
* The lines on the left should be diffed against the lines on the right.
* (If there are no left lines or no right lines, it implies solved == true,
* because there is nothing to diff.)
*
* If solved == true:
* If there are only left atoms, it is a chunk removing atoms from the left ("a
* minus chunk").
* If there are only right atoms, it is a chunk adding atoms from the right ("a
* plus chunk").
* If there are both left and right lines, it is a chunk of equal content on
* both sides, and left_count == right_count:
*
* - foo }
* - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
* - baz } right_start = NULL, right_count = 0 }
* moo }
* goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
* zoo } right_start = &right.atoms.head[0], right_count = 3 }
* +loo }
* +roo }-- diff_chunk{ left_start = NULL, left_count = 0,
* +too } right_start = &right.atoms.head[3], right_count = 3 }
*
*/
struct diff_chunk {
bool solved;
struct diff_atom *left_start;
unsigned int left_count;
struct diff_atom *right_start;
unsigned int right_count;
};
#define DIFF_RESULT_ALLOC_BLOCKSIZE 128
struct diff_chunk_context;
bool
diff_chunk_context_empty(const struct diff_chunk_context *cc);
bool
diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
const struct diff_chunk_context *other);
void
diff_chunk_contexts_merge(struct diff_chunk_context *cc,
const struct diff_chunk_context *other);
struct diff_state {
/* The final result passed to the original diff caller. */
struct diff_result *result;
/* The root diff_data is in result->left,right, these are (possibly)
* subsections of the root data. */
struct diff_data left;
struct diff_data right;
unsigned int recursion_depth_left;
/* Remaining chunks from one diff algorithm pass, if any solved == false
* chunks came up. */
diff_chunk_arraylist_t temp_result;
/* State buffer used by Myers algorithm. */
int *kd_buf;
size_t kd_buf_size; /* in units of sizeof(int), not bytes */
};
struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
struct diff_atom *left_start,
unsigned int left_count,
struct diff_atom *right_start,
unsigned int right_count);
struct diff_output_info;
int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
const char *prefix, struct diff_atom *start_atom,
unsigned int count);
int diff_output_trailing_newline_msg(struct diff_output_info *outinfo,
FILE *dest,
const struct diff_chunk *c);
#define DIFF_FUNCTION_CONTEXT_SIZE 55
int diff_output_match_function_prototype(char *prototype, size_t prototype_size,
int *last_prototype_idx,
const struct diff_result *result,
const struct diff_chunk_context *cc);
struct diff_output_info *diff_output_info_alloc(void);
void
diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
struct diff_atom *from_atom, unsigned int atoms_count);
|
