Game of Trees Repos

Blame

Date:: Tue Nov 10 22:54:37 2020 UTC
Message:: merge new diff implementation from the git.gameoftrees.org diff.git repository This new diff implementation was started by Neels Hofmeyr during the u2k20 hackathon and now replaces diffreg.c code lifted from the OpenBSD base system. The integration of this code into Got was done by me. Got now uses the patience diff algorithm by default. The diff.git repository will remain the primary repository for the diff code, which already compiles and runs on other operating systems such as Linux. Any fixes and improvements for files inherited from the diff.git repository should be written against that repository and synced to got.git afterwards.
Actions:: History | Blob | Raw File
  1 fe621944 2020-11-10 stsp /* Split source by line breaks, and calculate a simplistic checksum. */
  2 fe621944 2020-11-10 stsp /*
  3 fe621944 2020-11-10 stsp  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
  4 fe621944 2020-11-10 stsp  *
  5 fe621944 2020-11-10 stsp  * Permission to use, copy, modify, and distribute this software for any
  6 fe621944 2020-11-10 stsp  * purpose with or without fee is hereby granted, provided that the above
  7 fe621944 2020-11-10 stsp  * copyright notice and this permission notice appear in all copies.
  8 fe621944 2020-11-10 stsp  *
  9 fe621944 2020-11-10 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 10 fe621944 2020-11-10 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 11 fe621944 2020-11-10 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 12 fe621944 2020-11-10 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 13 fe621944 2020-11-10 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 14 fe621944 2020-11-10 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 15 fe621944 2020-11-10 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 16 fe621944 2020-11-10 stsp  */
 17 fe621944 2020-11-10 stsp 
 18 fe621944 2020-11-10 stsp #include <errno.h>
 19 fe621944 2020-11-10 stsp #include <inttypes.h>
 20 fe621944 2020-11-10 stsp #include <stdbool.h>
 21 fe621944 2020-11-10 stsp #include <stdio.h>
 22 fe621944 2020-11-10 stsp #include <stdlib.h>
 23 fe621944 2020-11-10 stsp #include <unistd.h>
 24 fe621944 2020-11-10 stsp #include <ctype.h>
 25 fe621944 2020-11-10 stsp 
 26 fe621944 2020-11-10 stsp #include <arraylist.h>
 27 fe621944 2020-11-10 stsp #include <diff_main.h>
 28 fe621944 2020-11-10 stsp 
 29 fe621944 2020-11-10 stsp #include "diff_internal.h"
 30 fe621944 2020-11-10 stsp #include "diff_debug.h"
 31 fe621944 2020-11-10 stsp 
 32 fe621944 2020-11-10 stsp static int
 33 fe621944 2020-11-10 stsp diff_data_atomize_text_lines_fd(struct diff_data *d)
 34 fe621944 2020-11-10 stsp {
 35 fe621944 2020-11-10 stsp 	off_t pos = 0;
 36 fe621944 2020-11-10 stsp 	const off_t end = pos + d->len;
 37 fe621944 2020-11-10 stsp 	unsigned int array_size_estimate = d->len / 50;
 38 fe621944 2020-11-10 stsp 	unsigned int pow2 = 1;
 39 fe621944 2020-11-10 stsp 	bool ignore_whitespace = (d->diff_flags & DIFF_FLAG_IGNORE_WHITESPACE);
 40 fe621944 2020-11-10 stsp 
 41 fe621944 2020-11-10 stsp 	while (array_size_estimate >>= 1)
 42 fe621944 2020-11-10 stsp 		pow2++;
 43 fe621944 2020-11-10 stsp 
 44 fe621944 2020-11-10 stsp 	ARRAYLIST_INIT(d->atoms, 1 << pow2);
 45 fe621944 2020-11-10 stsp 
 46 fe621944 2020-11-10 stsp 	if (fseek(d->root->f, 0L, SEEK_SET) == -1)
 47 fe621944 2020-11-10 stsp 		return errno;
 48 fe621944 2020-11-10 stsp 
 49 fe621944 2020-11-10 stsp 	while (pos < end) {
 50 fe621944 2020-11-10 stsp 		off_t line_end = pos;
 51 fe621944 2020-11-10 stsp 		unsigned int hash = 0;
 52 fe621944 2020-11-10 stsp 		unsigned char buf[512];
 53 fe621944 2020-11-10 stsp 		size_t r, i;
 54 fe621944 2020-11-10 stsp 		struct diff_atom *atom;
 55 fe621944 2020-11-10 stsp 		int eol = 0;
 56 fe621944 2020-11-10 stsp 
 57 fe621944 2020-11-10 stsp 		while (eol == 0 && line_end < end) {
 58 fe621944 2020-11-10 stsp 			r = fread(buf, sizeof(char), sizeof(buf), d->root->f);
 59 fe621944 2020-11-10 stsp 			if (r == 0 && ferror(d->root->f))
 60 fe621944 2020-11-10 stsp 				return errno;
 61 fe621944 2020-11-10 stsp 			i = 0;
 62 fe621944 2020-11-10 stsp 			while (eol == 0 && i < r) {
 63 fe621944 2020-11-10 stsp 				if (buf[i] != '\r' && buf[i] != '\n') {
 64 fe621944 2020-11-10 stsp 					if (!ignore_whitespace
 65 fe621944 2020-11-10 stsp 					    || !isspace(buf[i]))
 66 fe621944 2020-11-10 stsp 						hash = hash * 23 + buf[i];
 67 fe621944 2020-11-10 stsp 					line_end++;
 68 fe621944 2020-11-10 stsp 				} else
 69 fe621944 2020-11-10 stsp 					eol = buf[i];
 70 fe621944 2020-11-10 stsp 				i++;
 71 fe621944 2020-11-10 stsp 			}
 72 fe621944 2020-11-10 stsp 		}
 73 fe621944 2020-11-10 stsp 
 74 fe621944 2020-11-10 stsp 		/* When not at the end of data, the line ending char ('\r' or
 75 fe621944 2020-11-10 stsp 		 * '\n') must follow */
 76 fe621944 2020-11-10 stsp 		if (line_end < end)
 77 fe621944 2020-11-10 stsp 			line_end++;
 78 fe621944 2020-11-10 stsp 		/* If that was an '\r', also pull in any following '\n' */
 79 fe621944 2020-11-10 stsp 		if (line_end < end && eol == '\r') {
 80 fe621944 2020-11-10 stsp 			if (fseeko(d->root->f, line_end, SEEK_SET) == -1)
 81 fe621944 2020-11-10 stsp 				return errno;
 82 fe621944 2020-11-10 stsp 			r = fread(buf, sizeof(char), sizeof(buf), d->root->f);
 83 fe621944 2020-11-10 stsp 			if (r == 0 && ferror(d->root->f))
 84 fe621944 2020-11-10 stsp 				return errno;
 85 fe621944 2020-11-10 stsp 			if (r == 1 && buf[0] == '\n' )
 86 fe621944 2020-11-10 stsp 				line_end++;
 87 fe621944 2020-11-10 stsp 		}
 88 fe621944 2020-11-10 stsp 
 89 fe621944 2020-11-10 stsp 		/* Record the found line as diff atom */
 90 fe621944 2020-11-10 stsp 		ARRAYLIST_ADD(atom, d->atoms);
 91 fe621944 2020-11-10 stsp 		if (!atom)
 92 fe621944 2020-11-10 stsp 			return ENOMEM;
 93 fe621944 2020-11-10 stsp 
 94 fe621944 2020-11-10 stsp 		*atom = (struct diff_atom){
 95 fe621944 2020-11-10 stsp 			.root = d,
 96 fe621944 2020-11-10 stsp 			.pos = pos,
 97 fe621944 2020-11-10 stsp 			.at = NULL,	/* atom data is not memory-mapped */
 98 fe621944 2020-11-10 stsp 			.len = line_end - pos,
 99 fe621944 2020-11-10 stsp 			.hash = hash,
100 fe621944 2020-11-10 stsp 		};
101 fe621944 2020-11-10 stsp 
102 fe621944 2020-11-10 stsp 		/* Starting point for next line: */
103 fe621944 2020-11-10 stsp 		pos = line_end;
104 fe621944 2020-11-10 stsp 		if (fseeko(d->root->f, pos, SEEK_SET) == -1)
105 fe621944 2020-11-10 stsp 			return errno;
106 fe621944 2020-11-10 stsp 	}
107 fe621944 2020-11-10 stsp 
108 fe621944 2020-11-10 stsp 	return DIFF_RC_OK;
109 fe621944 2020-11-10 stsp }
110 fe621944 2020-11-10 stsp 
111 fe621944 2020-11-10 stsp static int
112 fe621944 2020-11-10 stsp diff_data_atomize_text_lines_mmap(struct diff_data *d)
113 fe621944 2020-11-10 stsp {
114 fe621944 2020-11-10 stsp 	const uint8_t *pos = d->data;
115 fe621944 2020-11-10 stsp 	const uint8_t *end = pos + d->len;
116 fe621944 2020-11-10 stsp 	bool ignore_whitespace = (d->diff_flags & DIFF_FLAG_IGNORE_WHITESPACE);
117 fe621944 2020-11-10 stsp 
118 fe621944 2020-11-10 stsp 	unsigned int array_size_estimate = d->len / 50;
119 fe621944 2020-11-10 stsp 	unsigned int pow2 = 1;
120 fe621944 2020-11-10 stsp 	while (array_size_estimate >>= 1)
121 fe621944 2020-11-10 stsp 		pow2++;
122 fe621944 2020-11-10 stsp 
123 fe621944 2020-11-10 stsp 	ARRAYLIST_INIT(d->atoms, 1 << pow2);
124 fe621944 2020-11-10 stsp 
125 fe621944 2020-11-10 stsp 	while (pos < end) {
126 fe621944 2020-11-10 stsp 		const uint8_t *line_end = pos;
127 fe621944 2020-11-10 stsp 		unsigned int hash = 0;
128 fe621944 2020-11-10 stsp 
129 fe621944 2020-11-10 stsp 		while (line_end < end && *line_end != '\r' && *line_end != '\n') {
130 fe621944 2020-11-10 stsp 			if (!ignore_whitespace
131 fe621944 2020-11-10 stsp 			    || !isspace(*line_end))
132 fe621944 2020-11-10 stsp 				hash = hash * 23 + *line_end;
133 fe621944 2020-11-10 stsp 			line_end++;
134 fe621944 2020-11-10 stsp 		}
135 fe621944 2020-11-10 stsp 
136 fe621944 2020-11-10 stsp 		/* When not at the end of data, the line ending char ('\r' or
137 fe621944 2020-11-10 stsp 		 * '\n') must follow */
138 fe621944 2020-11-10 stsp 		if (line_end < end)
139 fe621944 2020-11-10 stsp 			line_end++;
140 fe621944 2020-11-10 stsp 		/* If that was an '\r', also pull in any following '\n' */
141 fe621944 2020-11-10 stsp 		if (line_end < end - 1 && line_end[0] == '\r' &&
142 fe621944 2020-11-10 stsp 		    line_end[1] == '\n')
143 fe621944 2020-11-10 stsp 			line_end++;
144 fe621944 2020-11-10 stsp 
145 fe621944 2020-11-10 stsp 		/* Record the found line as diff atom */
146 fe621944 2020-11-10 stsp 		struct diff_atom *atom;
147 fe621944 2020-11-10 stsp 		ARRAYLIST_ADD(atom, d->atoms);
148 fe621944 2020-11-10 stsp 		if (!atom)
149 fe621944 2020-11-10 stsp 			return ENOMEM;
150 fe621944 2020-11-10 stsp 
151 fe621944 2020-11-10 stsp 		*atom = (struct diff_atom){
152 fe621944 2020-11-10 stsp 			.root = d,
153 fe621944 2020-11-10 stsp 			.pos = (off_t)(pos - d->data),
154 fe621944 2020-11-10 stsp 			.at = pos,
155 fe621944 2020-11-10 stsp 			.len = line_end - pos,
156 fe621944 2020-11-10 stsp 			.hash = hash,
157 fe621944 2020-11-10 stsp 		};
158 fe621944 2020-11-10 stsp 
159 fe621944 2020-11-10 stsp 		/* Starting point for next line: */
160 fe621944 2020-11-10 stsp 		pos = line_end;
161 fe621944 2020-11-10 stsp 	}
162 fe621944 2020-11-10 stsp 
163 fe621944 2020-11-10 stsp 	return DIFF_RC_OK;
164 fe621944 2020-11-10 stsp }
165 fe621944 2020-11-10 stsp 
166 fe621944 2020-11-10 stsp static int
167 fe621944 2020-11-10 stsp diff_data_atomize_text_lines(struct diff_data *d)
168 fe621944 2020-11-10 stsp {
169 fe621944 2020-11-10 stsp 	if (d->data == NULL)
170 fe621944 2020-11-10 stsp 		return diff_data_atomize_text_lines_fd(d);
171 fe621944 2020-11-10 stsp 	else
172 fe621944 2020-11-10 stsp 		return diff_data_atomize_text_lines_mmap(d);
173 fe621944 2020-11-10 stsp }
174 fe621944 2020-11-10 stsp 
175 fe621944 2020-11-10 stsp int
176 fe621944 2020-11-10 stsp diff_atomize_text_by_line(void *func_data, struct diff_data *d)
177 fe621944 2020-11-10 stsp {
178 fe621944 2020-11-10 stsp 	return diff_data_atomize_text_lines(d);
179 fe621944 2020-11-10 stsp }