Blame

Date:
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 /* Produce ed(1) script output from a diff_result. */

  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  * Copyright (c) 2020 Stefan Sperling <stsp@openbsd.org>

  5 fe621944 2020-11-10 stsp  *

  6 fe621944 2020-11-10 stsp  * Permission to use, copy, modify, and distribute this software for any

  7 fe621944 2020-11-10 stsp  * purpose with or without fee is hereby granted, provided that the above

  8 fe621944 2020-11-10 stsp  * copyright notice and this permission notice appear in all copies.

  9 fe621944 2020-11-10 stsp  *

 10 fe621944 2020-11-10 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES

 11 fe621944 2020-11-10 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF

 12 fe621944 2020-11-10 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR

 13 fe621944 2020-11-10 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES

 14 fe621944 2020-11-10 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN

 15 fe621944 2020-11-10 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF

 16 fe621944 2020-11-10 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

 17 fe621944 2020-11-10 stsp  */

 18 fe621944 2020-11-10 stsp 

 19 fe621944 2020-11-10 stsp #include <errno.h>

 20 fe621944 2020-11-10 stsp #include <stdio.h>

 21 fe621944 2020-11-10 stsp #include <stdlib.h>

 22 fe621944 2020-11-10 stsp #include <stdbool.h>

 23 fe621944 2020-11-10 stsp 

 24 fe621944 2020-11-10 stsp #include <arraylist.h>

 25 fe621944 2020-11-10 stsp #include <diff_main.h>

 26 fe621944 2020-11-10 stsp #include <diff_output.h>

 27 fe621944 2020-11-10 stsp 

 28 fe621944 2020-11-10 stsp #include "diff_internal.h"

 29 fe621944 2020-11-10 stsp 

 30 fe621944 2020-11-10 stsp static int

 31 fe621944 2020-11-10 stsp output_edscript_chunk(struct diff_output_info *outinfo,

 32 fe621944 2020-11-10 stsp     FILE *dest, const struct diff_input_info *info,

 33 fe621944 2020-11-10 stsp     const struct diff_result *result,

 34 fe621944 2020-11-10 stsp     struct diff_chunk_context *cc)

 35 fe621944 2020-11-10 stsp {

 36 fe621944 2020-11-10 stsp 	off_t outoff = 0, *offp;

 37 fe621944 2020-11-10 stsp 	int left_start, left_len, right_start, right_len;

 38 fe621944 2020-11-10 stsp 	int rc;

 39 fe621944 2020-11-10 stsp 

 40 fe621944 2020-11-10 stsp 	left_len = cc->left.end - cc->left.start;

 41 fe621944 2020-11-10 stsp 	if (left_len < 0)

 42 fe621944 2020-11-10 stsp 		return EINVAL;

 43 fe621944 2020-11-10 stsp 	else if (result->left->atoms.len == 0)

 44 fe621944 2020-11-10 stsp 		left_start = 0;

 45 fe621944 2020-11-10 stsp 	else if (left_len == 0 && cc->left.start > 0)

 46 fe621944 2020-11-10 stsp 		left_start = cc->left.start;

 47 fe621944 2020-11-10 stsp 	else

 48 fe621944 2020-11-10 stsp 		left_start = cc->left.start + 1;

 49 fe621944 2020-11-10 stsp 

 50 fe621944 2020-11-10 stsp 	right_len = cc->right.end - cc->right.start;

 51 fe621944 2020-11-10 stsp 	if (right_len < 0)

 52 fe621944 2020-11-10 stsp 		return EINVAL;

 53 fe621944 2020-11-10 stsp 	else if (result->right->atoms.len == 0)

 54 fe621944 2020-11-10 stsp 		right_start = 0;

 55 fe621944 2020-11-10 stsp 	else if (right_len == 0 && cc->right.start > 0)

 56 fe621944 2020-11-10 stsp 		right_start = cc->right.start;

 57 fe621944 2020-11-10 stsp 	else

 58 fe621944 2020-11-10 stsp 		right_start = cc->right.start + 1;

 59 fe621944 2020-11-10 stsp 

 60 fe621944 2020-11-10 stsp 	if (left_len == 0) {

 61 fe621944 2020-11-10 stsp 		/* addition */

 62 fe621944 2020-11-10 stsp 		if (right_len == 1) {

 63 fe621944 2020-11-10 stsp 			rc = fprintf(dest, "%da%d\n", left_start, right_start);

 64 fe621944 2020-11-10 stsp 		} else {

 65 fe621944 2020-11-10 stsp 			rc = fprintf(dest, "%da%d,%d\n", left_start,

 66 fe621944 2020-11-10 stsp 			    right_start, cc->right.end);

 67 fe621944 2020-11-10 stsp 		}

 68 fe621944 2020-11-10 stsp 	} else if (right_len == 0) {

 69 fe621944 2020-11-10 stsp 		/* deletion */

 70 fe621944 2020-11-10 stsp 		if (left_len == 1) {

 71 fe621944 2020-11-10 stsp 			rc = fprintf(dest, "%dd%d\n", left_start,

 72 fe621944 2020-11-10 stsp 			    right_start);

 73 fe621944 2020-11-10 stsp 		} else {

 74 fe621944 2020-11-10 stsp 			rc = fprintf(dest, "%d,%dd%d\n", left_start,

 75 fe621944 2020-11-10 stsp 			    cc->left.end, right_start);

 76 fe621944 2020-11-10 stsp 		}

 77 fe621944 2020-11-10 stsp 	} else {

 78 fe621944 2020-11-10 stsp 		/* change */

 79 fe621944 2020-11-10 stsp 		if (left_len == 1 && right_len == 1) {

 80 fe621944 2020-11-10 stsp 			rc = fprintf(dest, "%dc%d\n", left_start, right_start);

 81 fe621944 2020-11-10 stsp 		} else if (left_len == 1) {

 82 fe621944 2020-11-10 stsp 			rc = fprintf(dest, "%dc%d,%d\n", left_start,

 83 fe621944 2020-11-10 stsp 			    right_start, cc->right.end);

 84 fe621944 2020-11-10 stsp 		} else if (right_len == 1) {

 85 fe621944 2020-11-10 stsp 			rc = fprintf(dest, "%d,%dc%d\n", left_start,

 86 fe621944 2020-11-10 stsp 			    cc->left.end, right_start);

 87 fe621944 2020-11-10 stsp 		} else {

 88 fe621944 2020-11-10 stsp 			rc = fprintf(dest, "%d,%dc%d,%d\n", left_start,

 89 fe621944 2020-11-10 stsp 			    cc->left.end, right_start, cc->right.end);

 90 fe621944 2020-11-10 stsp 		}

 91 fe621944 2020-11-10 stsp 	}

 92 fe621944 2020-11-10 stsp 	if (rc < 0)

 93 fe621944 2020-11-10 stsp 		return errno;

 94 fe621944 2020-11-10 stsp 	if (outinfo) {

 95 fe621944 2020-11-10 stsp 		ARRAYLIST_ADD(offp, outinfo->line_offsets);

 96 fe621944 2020-11-10 stsp 		if (offp == NULL)

 97 fe621944 2020-11-10 stsp 			return ENOMEM;

 98 fe621944 2020-11-10 stsp 		outoff += rc;

 99 fe621944 2020-11-10 stsp 		*offp = outoff;

100 fe621944 2020-11-10 stsp 	}

101 fe621944 2020-11-10 stsp 

102 fe621944 2020-11-10 stsp 	return DIFF_RC_OK;

103 fe621944 2020-11-10 stsp }

104 fe621944 2020-11-10 stsp 

105 fe621944 2020-11-10 stsp int

106 fe621944 2020-11-10 stsp diff_output_edscript(struct diff_output_info **output_info,

107 fe621944 2020-11-10 stsp     FILE *dest, const struct diff_input_info *info,

108 fe621944 2020-11-10 stsp     const struct diff_result *result)

109 fe621944 2020-11-10 stsp {

110 fe621944 2020-11-10 stsp 	struct diff_output_info *outinfo = NULL;

111 fe621944 2020-11-10 stsp 	struct diff_chunk_context cc = {};

112 fe621944 2020-11-10 stsp 	int i, rc;

113 fe621944 2020-11-10 stsp 

114 fe621944 2020-11-10 stsp 	if (!result)

115 fe621944 2020-11-10 stsp 		return EINVAL;

116 fe621944 2020-11-10 stsp 	if (result->rc != DIFF_RC_OK)

117 fe621944 2020-11-10 stsp 		return result->rc;

118 fe621944 2020-11-10 stsp 

119 fe621944 2020-11-10 stsp 	if (output_info) {

120 fe621944 2020-11-10 stsp 		*output_info = diff_output_info_alloc();

121 fe621944 2020-11-10 stsp 		if (*output_info == NULL)

122 fe621944 2020-11-10 stsp 			return ENOMEM;

123 fe621944 2020-11-10 stsp 		outinfo = *output_info;

124 fe621944 2020-11-10 stsp 	}

125 fe621944 2020-11-10 stsp 

126 fe621944 2020-11-10 stsp 	for (i = 0; i < result->chunks.len; i++) {

127 fe621944 2020-11-10 stsp 		struct diff_chunk *chunk = &result->chunks.head[i];

128 fe621944 2020-11-10 stsp 		enum diff_chunk_type t = diff_chunk_type(chunk);

129 fe621944 2020-11-10 stsp 		struct diff_chunk_context next;

130 fe621944 2020-11-10 stsp 

131 fe621944 2020-11-10 stsp 		if (t != CHUNK_MINUS && t != CHUNK_PLUS)

132 fe621944 2020-11-10 stsp 			continue;

133 fe621944 2020-11-10 stsp 

134 fe621944 2020-11-10 stsp 		if (diff_chunk_context_empty(&cc)) {

135 fe621944 2020-11-10 stsp 			/* Note down the start point, any number of subsequent

136 fe621944 2020-11-10 stsp 			 * chunks may be joined up to this chunk by being

137 fe621944 2020-11-10 stsp 			 * directly adjacent. */

138 fe621944 2020-11-10 stsp 			diff_chunk_context_get(&cc, result, i, 0);

139 fe621944 2020-11-10 stsp 			continue;

140 fe621944 2020-11-10 stsp 		}

141 fe621944 2020-11-10 stsp 

142 fe621944 2020-11-10 stsp 		/* There already is a previous chunk noted down for being

143 fe621944 2020-11-10 stsp 		 * printed. Does it join up with this one? */

144 fe621944 2020-11-10 stsp 		diff_chunk_context_get(&next, result, i, 0);

145 fe621944 2020-11-10 stsp 

146 fe621944 2020-11-10 stsp 		if (diff_chunk_contexts_touch(&cc, &next)) {

147 fe621944 2020-11-10 stsp 			/* This next context touches or overlaps the previous

148 fe621944 2020-11-10 stsp 			 * one, join. */

149 fe621944 2020-11-10 stsp 			diff_chunk_contexts_merge(&cc, &next);

150 fe621944 2020-11-10 stsp 			continue;

151 fe621944 2020-11-10 stsp 		}

152 fe621944 2020-11-10 stsp 

153 fe621944 2020-11-10 stsp 		rc = output_edscript_chunk(outinfo, dest, info, result, &cc);

154 fe621944 2020-11-10 stsp 		if (rc != DIFF_RC_OK)

155 fe621944 2020-11-10 stsp 			return rc;

156 fe621944 2020-11-10 stsp 		cc = next;

157 fe621944 2020-11-10 stsp 	}

158 fe621944 2020-11-10 stsp 

159 fe621944 2020-11-10 stsp 	if (!diff_chunk_context_empty(&cc))

160 fe621944 2020-11-10 stsp 		return output_edscript_chunk(outinfo, dest, info, result, &cc);

161 fe621944 2020-11-10 stsp 	return DIFF_RC_OK;

162 fe621944 2020-11-10 stsp }