1 /* 2 * Copyright (c) 2018 Martin Pieuchot 3 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 #include <sys/types.h> 19 #include <sys/capsicum.h> 20 #ifndef DIFF_NO_MMAP 21 #include <sys/mman.h> 22 #endif 23 #include <sys/stat.h> 24 25 #include <capsicum_helpers.h> 26 #include <err.h> 27 #include <fcntl.h> 28 #include <stdbool.h> 29 #include <stdint.h> 30 #include <stdio.h> 31 #include <stdlib.h> 32 #include <string.h> 33 #include <time.h> 34 #include <unistd.h> 35 36 #include "pr.h" 37 #include "diff.h" 38 #include <arraylist.h> 39 #include <diff_main.h> 40 #include <diff_output.h> 41 42 const char *format_label(const char *, struct stat *); 43 44 enum diffreg_algo { 45 DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE = 0, 46 DIFFREG_ALGO_MYERS_THEN_PATIENCE = 1, 47 DIFFREG_ALGO_PATIENCE = 2, 48 DIFFREG_ALGO_NONE = 3, 49 }; 50 51 int diffreg_new(char *, char *, int, int); 52 FILE * openfile(const char *, char **, struct stat *); 53 54 static const struct diff_algo_config myers_then_patience; 55 static const struct diff_algo_config myers_then_myers_divide; 56 static const struct diff_algo_config patience; 57 static const struct diff_algo_config myers_divide; 58 59 static const struct diff_algo_config myers_then_patience = (struct diff_algo_config){ 60 .impl = diff_algo_myers, 61 .permitted_state_size = 1024 * 1024 * sizeof(int), 62 .fallback_algo = &patience, 63 }; 64 65 static const struct diff_algo_config myers_then_myers_divide = 66 (struct diff_algo_config){ 67 .impl = diff_algo_myers, 68 .permitted_state_size = 1024 * 1024 * sizeof(int), 69 .fallback_algo = &myers_divide, 70 }; 71 72 static const struct diff_algo_config patience = (struct diff_algo_config){ 73 .impl = diff_algo_patience, 74 /* After subdivision, do Patience again: */ 75 .inner_algo = &patience, 76 /* If subdivision failed, do Myers Divide et Impera: */ 77 .fallback_algo = &myers_then_myers_divide, 78 }; 79 80 static const struct diff_algo_config myers_divide = (struct diff_algo_config){ 81 .impl = diff_algo_myers_divide, 82 /* When division succeeded, start from the top: */ 83 .inner_algo = &myers_then_myers_divide, 84 /* (fallback_algo = NULL implies diff_algo_none). */ 85 }; 86 87 static const struct diff_algo_config no_algo = (struct diff_algo_config){ 88 .impl = diff_algo_none, 89 }; 90 91 /* If the state for a forward-Myers is small enough, use Myers, otherwise first 92 * do a Myers-divide. */ 93 static const struct diff_config diff_config_myers_then_myers_divide = { 94 .atomize_func = diff_atomize_text_by_line, 95 .algo = &myers_then_myers_divide, 96 }; 97 98 /* If the state for a forward-Myers is small enough, use Myers, otherwise first 99 * do a Patience. */ 100 static const struct diff_config diff_config_myers_then_patience = { 101 .atomize_func = diff_atomize_text_by_line, 102 .algo = &myers_then_patience, 103 }; 104 105 /* Directly force Patience as a first divider of the source file. */ 106 static const struct diff_config diff_config_patience = { 107 .atomize_func = diff_atomize_text_by_line, 108 .algo = &patience, 109 }; 110 111 /* Directly force Patience as a first divider of the source file. */ 112 static const struct diff_config diff_config_no_algo = { 113 .atomize_func = diff_atomize_text_by_line, 114 }; 115 116 const char * 117 format_label(const char *oldlabel, struct stat *stb) 118 { 119 const char *time_format = "%Y-%m-%d %H:%M:%S"; 120 char *newlabel; 121 char buf[256]; 122 char end[10]; 123 struct tm tm, *tm_ptr; 124 int nsec = stb->st_mtim.tv_nsec; 125 size_t newlabellen, timelen, endlen; 126 tm_ptr = localtime_r(&stb->st_mtime, &tm); 127 128 timelen = strftime(buf, 256, time_format, tm_ptr); 129 endlen = strftime(end, 10, "%z", tm_ptr); 130 131 /* 132 * The new label is the length of the time, old label, timezone, 133 * 9 characters for nanoseconds, and 4 characters for a period 134 * and for formatting. 135 */ 136 newlabellen = timelen + strlen(oldlabel) + endlen + 9 + 4; 137 newlabel = calloc(newlabellen, sizeof(char)); 138 139 snprintf(newlabel, newlabellen ,"%s\t%s.%.9d %s\n", 140 oldlabel, buf, nsec, end); 141 142 return newlabel; 143 } 144 145 int 146 diffreg_new(char *file1, char *file2, int flags, int capsicum) 147 { 148 char *str1, *str2; 149 FILE *f1, *f2; 150 struct pr *pr = NULL; 151 struct stat st1, st2; 152 struct diff_input_info info; 153 struct diff_data left = {}, right = {}; 154 struct diff_result *result = NULL; 155 bool force_text, have_binary; 156 int rc, atomizer_flags, rflags, diff_flags = 0; 157 int context_lines = diff_context; 158 const struct diff_config *cfg; 159 enum diffreg_algo algo; 160 cap_rights_t rights_ro; 161 162 algo = DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE; 163 164 switch (algo) { 165 default: 166 case DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE: 167 cfg = &diff_config_myers_then_myers_divide; 168 break; 169 case DIFFREG_ALGO_MYERS_THEN_PATIENCE: 170 cfg = &diff_config_myers_then_patience; 171 break; 172 case DIFFREG_ALGO_PATIENCE: 173 cfg = &diff_config_patience; 174 break; 175 case DIFFREG_ALGO_NONE: 176 cfg = &diff_config_no_algo; 177 break; 178 } 179 180 f1 = openfile(file1, &str1, &st1); 181 f2 = openfile(file2, &str2, &st2); 182 183 if (flags & D_PAGINATION) 184 pr = start_pr(file1, file2); 185 186 if (capsicum) { 187 cap_rights_init(&rights_ro, CAP_READ, CAP_FSTAT, CAP_SEEK); 188 if (caph_rights_limit(fileno(f1), &rights_ro) < 0) 189 err(2, "unable to limit rights on: %s", file1); 190 if (caph_rights_limit(fileno(f2), &rights_ro) < 0) 191 err(2, "unable to limit rights on: %s", file2); 192 if (fileno(f1) == STDIN_FILENO || fileno(f2) == STDIN_FILENO) { 193 /* stdin has already been limited */ 194 if (caph_limit_stderr() == -1) 195 err(2, "unable to limit stderr"); 196 if (caph_limit_stdout() == -1) 197 err(2, "unable to limit stdout"); 198 } else if (caph_limit_stdio() == -1) 199 err(2, "unable to limit stdio"); 200 caph_cache_catpages(); 201 caph_cache_tzdata(); 202 if (caph_enter() < 0) 203 err(2, "unable to enter capability mode"); 204 } 205 /* 206 * If we have been given a label use that for the paths, if not format 207 * the path with the files modification time. 208 */ 209 info.flags = 0; 210 info.left_path = (label[0] != NULL) ? 211 label[0] : format_label(file1, &stb1); 212 info.right_path = (label[1] != NULL) ? 213 label[1] : format_label(file2, &stb2); 214 215 if (flags & D_FORCEASCII) 216 diff_flags |= DIFF_FLAG_FORCE_TEXT_DATA; 217 if (flags & D_IGNOREBLANKS) 218 diff_flags |= DIFF_FLAG_IGNORE_WHITESPACE; 219 if (flags & D_PROTOTYPE) 220 diff_flags |= DIFF_FLAG_SHOW_PROTOTYPES; 221 222 if (diff_atomize_file(&left, cfg, f1, (uint8_t *)str1, st1.st_size, diff_flags)) { 223 rc = D_ERROR; 224 goto done; 225 } 226 if (diff_atomize_file(&right, cfg, f2, (uint8_t *)str2, st2.st_size, diff_flags)) { 227 rc = D_ERROR; 228 goto done; 229 } 230 231 result = diff_main(cfg, &left, &right); 232 if (result->rc != DIFF_RC_OK) { 233 rc = D_ERROR; 234 status |= 2; 235 goto done; 236 } 237 /* 238 * If there wasn't an error, but we don't have any printable chunks 239 * then the files must match. 240 */ 241 if (!diff_result_contains_printable_chunks(result)) { 242 rc = D_SAME; 243 goto done; 244 } 245 246 atomizer_flags = (result->left->atomizer_flags | result->right->atomizer_flags); 247 rflags = (result->left->root->diff_flags | result->right->root->diff_flags); 248 force_text = (rflags & DIFF_FLAG_FORCE_TEXT_DATA); 249 have_binary = (atomizer_flags & DIFF_ATOMIZER_FOUND_BINARY_DATA); 250 251 if (have_binary && !force_text) { 252 rc = D_BINARY; 253 status |= 1; 254 goto done; 255 } 256 257 if (color) 258 diff_output_set_colors(color, del_code, add_code); 259 if (diff_format == D_NORMAL) { 260 rc = diff_output_plain(NULL, stdout, &info, result, false); 261 } else if (diff_format == D_EDIT) { 262 rc = diff_output_edscript(NULL, stdout, &info, result); 263 } else { 264 rc = diff_output_unidiff(NULL, stdout, &info, result, 265 context_lines); 266 } 267 if (rc != DIFF_RC_OK) { 268 rc = D_ERROR; 269 status |= 2; 270 } else { 271 rc = D_DIFFER; 272 status |= 1; 273 } 274 done: 275 if (pr != NULL) 276 stop_pr(pr); 277 diff_result_free(result); 278 diff_data_free(&left); 279 diff_data_free(&right); 280 #ifndef DIFF_NO_MMAP 281 if (str1) 282 munmap(str1, st1.st_size); 283 if (str2) 284 munmap(str2, st2.st_size); 285 #endif 286 fclose(f1); 287 fclose(f2); 288 289 return rc; 290 } 291 292 FILE * 293 openfile(const char *path, char **p, struct stat *st) 294 { 295 FILE *f = NULL; 296 297 if (strcmp(path, "-") == 0) 298 f = stdin; 299 else 300 f = fopen(path, "r"); 301 302 if (f == NULL) 303 err(2, "%s", path); 304 305 if (fstat(fileno(f), st) == -1) 306 err(2, "%s", path); 307 308 #ifndef DIFF_NO_MMAP 309 *p = mmap(NULL, st->st_size, PROT_READ, MAP_PRIVATE, fileno(f), 0); 310 if (*p == MAP_FAILED) 311 #endif 312 *p = NULL; /* fall back on file I/O */ 313 314 return f; 315 } 316 317 bool 318 can_libdiff(int flags) 319 { 320 /* libdiff's atomizer can only deal with files */ 321 if (!S_ISREG(stb1.st_mode) || !S_ISREG(stb2.st_mode)) 322 return false; 323 324 /* Is this one of the supported input/output modes for diffreg_new? */ 325 if ((flags == 0 || !(flags & ~D_NEWALGO_FLAGS)) && 326 ignore_pats == NULL && ( 327 diff_format == D_NORMAL || 328 #if 0 329 diff_format == D_EDIT || 330 #endif 331 diff_format == D_UNIFIED) && 332 (diff_algorithm == D_DIFFMYERS || diff_algorithm == D_DIFFPATIENCE)) { 333 return true; 334 } 335 336 /* Fallback to using stone. */ 337 return false; 338 } 339