1 /* 2 * LibXDiff by Davide Libenzi ( File Differential Library ) 3 * Copyright (C) 2003 Davide Libenzi 4 * 5 * This library is free software; you can redistribute it and/or 6 * modify it under the terms of the GNU Lesser General Public 7 * License as published by the Free Software Foundation; either 8 * version 2.1 of the License, or (at your option) any later version. 9 * 10 * This library is distributed in the hope that it will be useful, 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * Lesser General Public License for more details. 14 * 15 * You should have received a copy of the GNU Lesser General Public 16 * License along with this library; if not, see 17 * <http://www.gnu.org/licenses/>. 18 * 19 * Davide Libenzi <[email protected]> 20 * 21 */ 22 23 #include <limits.h> 24 #include <assert.h> 25 #include "xinclude.h" 26 27 28 29 30 long xdl_bogosqrt(long n) { 31 long i; 32 33 /* 34 * Classical integer square root approximation using shifts. 35 */ 36 for (i = 1; n > 0; n >>= 2) 37 i <<= 1; 38 39 return i; 40 } 41 42 43 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize, 44 xdemitcb_t *ecb) { 45 int i = 2; 46 mmbuffer_t mb[3]; 47 48 mb[0].ptr = (char *) pre; 49 mb[0].size = psize; 50 mb[1].ptr = (char *) rec; 51 mb[1].size = size; 52 if (size > 0 && rec[size - 1] != '\n') { 53 mb[2].ptr = (char *) "\n\\ No newline at end of file\n"; 54 mb[2].size = (long)strlen(mb[2].ptr); 55 i++; 56 } 57 if (ecb->outf(ecb->priv, mb, i) < 0) { 58 59 return -1; 60 } 61 62 return 0; 63 } 64 65 void *xdl_mmfile_first(mmfile_t *mmf, long *size) 66 { 67 *size = mmf->size; 68 return mmf->ptr; 69 } 70 71 72 long xdl_mmfile_size(mmfile_t *mmf) 73 { 74 return mmf->size; 75 } 76 77 78 int xdl_cha_init(chastore_t *cha, long isize, long icount) { 79 80 cha->head = cha->tail = NULL; 81 cha->isize = isize; 82 cha->nsize = icount * isize; 83 cha->ancur = cha->sncur = NULL; 84 cha->scurr = 0; 85 86 return 0; 87 } 88 89 90 void xdl_cha_free(chastore_t *cha) { 91 chanode_t *cur, *tmp; 92 93 for (cur = cha->head; (tmp = cur) != NULL;) { 94 cur = cur->next; 95 xdl_free(tmp); 96 } 97 } 98 99 100 void *xdl_cha_alloc(chastore_t *cha) { 101 chanode_t *ancur; 102 void *data; 103 104 if (!(ancur = cha->ancur) || ancur->icurr == cha->nsize) { 105 if (!(ancur = (chanode_t *) xdl_malloc(sizeof(chanode_t) + cha->nsize))) { 106 107 return NULL; 108 } 109 ancur->icurr = 0; 110 ancur->next = NULL; 111 if (cha->tail) 112 cha->tail->next = ancur; 113 if (!cha->head) 114 cha->head = ancur; 115 cha->tail = ancur; 116 cha->ancur = ancur; 117 } 118 119 data = (char *) ancur + sizeof(chanode_t) + ancur->icurr; 120 ancur->icurr += cha->isize; 121 122 return data; 123 } 124 125 long xdl_guess_lines(mmfile_t *mf, long sample) { 126 long nl = 0, size, tsize = 0; 127 char const *data, *cur, *top; 128 129 if ((cur = data = xdl_mmfile_first(mf, &size)) != NULL) { 130 for (top = data + size; nl < sample && cur < top; ) { 131 nl++; 132 if (!(cur = memchr(cur, '\n', top - cur))) 133 cur = top; 134 else 135 cur++; 136 } 137 tsize += (long) (cur - data); 138 } 139 140 if (nl && tsize) 141 nl = xdl_mmfile_size(mf) / (tsize / nl); 142 143 return nl + 1; 144 } 145 146 int xdl_blankline(const char *line, long size, long flags) 147 { 148 long i; 149 150 if (!(flags & XDF_WHITESPACE_FLAGS)) 151 return (size <= 1); 152 153 for (i = 0; i < size && XDL_ISSPACE(line[i]); i++) 154 ; 155 156 return (i == size); 157 } 158 159 /* 160 * Have we eaten everything on the line, except for an optional 161 * CR at the very end? 162 */ 163 static int ends_with_optional_cr(const char *l, long s, long i) 164 { 165 int complete = s && l[s-1] == '\n'; 166 167 if (complete) 168 s--; 169 if (s == i) 170 return 1; 171 /* do not ignore CR at the end of an incomplete line */ 172 if (complete && s == i + 1 && l[i] == '\r') 173 return 1; 174 return 0; 175 } 176 177 int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags) 178 { 179 int i1, i2; 180 181 if (s1 == s2 && !memcmp(l1, l2, s1)) 182 return 1; 183 if (!(flags & XDF_WHITESPACE_FLAGS)) 184 return 0; 185 186 i1 = 0; 187 i2 = 0; 188 189 /* 190 * -w matches everything that matches with -b, and -b in turn 191 * matches everything that matches with --ignore-space-at-eol, 192 * which in turn matches everything that matches with --ignore-cr-at-eol. 193 * 194 * Each flavor of ignoring needs different logic to skip whitespaces 195 * while we have both sides to compare. 196 */ 197 if (flags & XDF_IGNORE_WHITESPACE) { 198 goto skip_ws; 199 while (i1 < s1 && i2 < s2) { 200 if (l1[i1++] != l2[i2++]) 201 return 0; 202 skip_ws: 203 while (i1 < s1 && XDL_ISSPACE(l1[i1])) 204 i1++; 205 while (i2 < s2 && XDL_ISSPACE(l2[i2])) 206 i2++; 207 } 208 } else if (flags & XDF_IGNORE_WHITESPACE_CHANGE) { 209 while (i1 < s1 && i2 < s2) { 210 if (XDL_ISSPACE(l1[i1]) && XDL_ISSPACE(l2[i2])) { 211 /* Skip matching spaces and try again */ 212 while (i1 < s1 && XDL_ISSPACE(l1[i1])) 213 i1++; 214 while (i2 < s2 && XDL_ISSPACE(l2[i2])) 215 i2++; 216 continue; 217 } 218 if (l1[i1++] != l2[i2++]) 219 return 0; 220 } 221 } else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL) { 222 while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) { 223 i1++; 224 i2++; 225 } 226 } else if (flags & XDF_IGNORE_CR_AT_EOL) { 227 /* Find the first difference and see how the line ends */ 228 while (i1 < s1 && i2 < s2 && l1[i1] == l2[i2]) { 229 i1++; 230 i2++; 231 } 232 return (ends_with_optional_cr(l1, s1, i1) && 233 ends_with_optional_cr(l2, s2, i2)); 234 } 235 236 /* 237 * After running out of one side, the remaining side must have 238 * nothing but whitespace for the lines to match. Note that 239 * ignore-whitespace-at-eol case may break out of the loop 240 * while there still are characters remaining on both lines. 241 */ 242 if (i1 < s1) { 243 while (i1 < s1 && XDL_ISSPACE(l1[i1])) 244 i1++; 245 if (s1 != i1) 246 return 0; 247 } 248 if (i2 < s2) { 249 while (i2 < s2 && XDL_ISSPACE(l2[i2])) 250 i2++; 251 return (s2 == i2); 252 } 253 return 1; 254 } 255 256 static unsigned long xdl_hash_record_with_whitespace(char const **data, 257 char const *top, long flags) { 258 unsigned long ha = 5381; 259 char const *ptr = *data; 260 int cr_at_eol_only = (flags & XDF_WHITESPACE_FLAGS) == XDF_IGNORE_CR_AT_EOL; 261 262 for (; ptr < top && *ptr != '\n'; ptr++) { 263 if (cr_at_eol_only) { 264 /* do not ignore CR at the end of an incomplete line */ 265 if (*ptr == '\r' && 266 (ptr + 1 < top && ptr[1] == '\n')) 267 continue; 268 } 269 else if (XDL_ISSPACE(*ptr)) { 270 const char *ptr2 = ptr; 271 int at_eol; 272 while (ptr + 1 < top && XDL_ISSPACE(ptr[1]) 273 && ptr[1] != '\n') 274 ptr++; 275 at_eol = (top <= ptr + 1 || ptr[1] == '\n'); 276 if (flags & XDF_IGNORE_WHITESPACE) 277 ; /* already handled */ 278 else if (flags & XDF_IGNORE_WHITESPACE_CHANGE 279 && !at_eol) { 280 ha += (ha << 5); 281 ha ^= (unsigned long) ' '; 282 } 283 else if (flags & XDF_IGNORE_WHITESPACE_AT_EOL 284 && !at_eol) { 285 while (ptr2 != ptr + 1) { 286 ha += (ha << 5); 287 ha ^= (unsigned long) *ptr2; 288 ptr2++; 289 } 290 } 291 continue; 292 } 293 ha += (ha << 5); 294 ha ^= (unsigned long) *ptr; 295 } 296 *data = ptr < top ? ptr + 1: ptr; 297 298 return ha; 299 } 300 301 unsigned long xdl_hash_record(char const **data, char const *top, long flags) { 302 unsigned long ha = 5381; 303 char const *ptr = *data; 304 305 if (flags & XDF_WHITESPACE_FLAGS) 306 return xdl_hash_record_with_whitespace(data, top, flags); 307 308 for (; ptr < top && *ptr != '\n'; ptr++) { 309 ha += (ha << 5); 310 ha ^= (unsigned long) *ptr; 311 } 312 *data = ptr < top ? ptr + 1: ptr; 313 314 return ha; 315 } 316 317 unsigned int xdl_hashbits(unsigned int size) { 318 unsigned int val = 1, bits = 0; 319 320 for (; val < size && bits < CHAR_BIT * sizeof(unsigned int); val <<= 1, bits++); 321 return bits ? bits: 1; 322 } 323 324 325 int xdl_num_out(char *out, long val) { 326 char *ptr, *str = out; 327 char buf[32]; 328 329 ptr = buf + sizeof(buf) - 1; 330 *ptr = '\0'; 331 if (val < 0) { 332 *--ptr = '-'; 333 val = -val; 334 } 335 for (; val && ptr > buf; val /= 10) 336 *--ptr = "0123456789"[val % 10]; 337 if (*ptr) 338 for (; *ptr; ptr++, str++) 339 *str = *ptr; 340 else 341 *str++ = '0'; 342 *str = '\0'; 343 344 return str - out; 345 } 346 347 int xdl_emit_hunk_hdr(long s1, long c1, long s2, long c2, 348 const char *func, long funclen, xdemitcb_t *ecb) { 349 int nb = 0; 350 mmbuffer_t mb; 351 char buf[128]; 352 353 memcpy(buf, "@@ -", 4); 354 nb += 4; 355 356 nb += xdl_num_out(buf + nb, c1 ? s1: s1 - 1); 357 358 if (c1 != 1) { 359 memcpy(buf + nb, ",", 1); 360 nb += 1; 361 362 nb += xdl_num_out(buf + nb, c1); 363 } 364 365 memcpy(buf + nb, " +", 2); 366 nb += 2; 367 368 nb += xdl_num_out(buf + nb, c2 ? s2: s2 - 1); 369 370 if (c2 != 1) { 371 memcpy(buf + nb, ",", 1); 372 nb += 1; 373 374 nb += xdl_num_out(buf + nb, c2); 375 } 376 377 memcpy(buf + nb, " @@", 3); 378 nb += 3; 379 if (func && funclen) { 380 buf[nb++] = ' '; 381 if (funclen > (long)sizeof(buf) - nb - 1) 382 funclen = sizeof(buf) - nb - 1; 383 memcpy(buf + nb, func, funclen); 384 nb += funclen; 385 } 386 buf[nb++] = '\n'; 387 388 mb.ptr = buf; 389 mb.size = nb; 390 if (ecb->outf(ecb->priv, &mb, 1) < 0) 391 return -1; 392 393 return 0; 394 } 395 396 int xdl_fall_back_diff(xdfenv_t *diff_env, xpparam_t const *xpp, 397 int line1, int count1, int line2, int count2) 398 { 399 /* 400 * This probably does not work outside Git, since 401 * we have a very simple mmfile structure. 402 * 403 * Note: ideally, we would reuse the prepared environment, but 404 * the libxdiff interface does not (yet) allow for diffing only 405 * ranges of lines instead of the whole files. 406 */ 407 mmfile_t subfile1, subfile2; 408 xdfenv_t env; 409 410 subfile1.ptr = (char *)diff_env->xdf1.recs[line1 - 1]->ptr; 411 subfile1.size = diff_env->xdf1.recs[line1 + count1 - 2]->ptr + 412 diff_env->xdf1.recs[line1 + count1 - 2]->size - subfile1.ptr; 413 subfile2.ptr = (char *)diff_env->xdf2.recs[line2 - 1]->ptr; 414 subfile2.size = diff_env->xdf2.recs[line2 + count2 - 2]->ptr + 415 diff_env->xdf2.recs[line2 + count2 - 2]->size - subfile2.ptr; 416 if (xdl_do_diff(&subfile1, &subfile2, xpp, &env) < 0) 417 return -1; 418 419 memcpy(diff_env->xdf1.rchg + line1 - 1, env.xdf1.rchg, count1); 420 memcpy(diff_env->xdf2.rchg + line2 - 1, env.xdf2.rchg, count2); 421 422 xdl_free_env(&env); 423 424 return 0; 425 } 426