thodg/got/lib/diff_main.c

• Show log

  Commit

• Hash : fe621944
  Author :
  Date : 2020-11-10T22:54:37
  

  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.

Download

• lib/diff_main.c

• /* Generic infrastructure to implement various diff algorithms (implementation). */
  /*
   * 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.
   */
  
  
  #include <sys/queue.h>
  #include <ctype.h>
  #include <errno.h>
  #include <stdint.h>
  #include <stdlib.h>
  #include <stdbool.h>
  #include <stdio.h>
  #include <string.h>
  #include <limits.h>
  #include <unistd.h>
  
  #include <assert.h>
  
  #include <arraylist.h>
  #include <diff_main.h>
  
  #include "diff_internal.h"
  #include "diff_debug.h"
  
  static int
  read_at(FILE *f, off_t at_pos, unsigned char *buf, size_t len)
  {
  	int r;
  	if (fseeko(f, at_pos, SEEK_SET) == -1)
  		return errno;
  	r = fread(buf, sizeof(char), len, f);
  	if ((r == 0 || r < len) && ferror(f))
  		return errno;
  	if (r != len)
  		return EIO;
  	return 0;
  }
  
  static int
  buf_cmp(const unsigned char *left, size_t left_len,
  	const unsigned char *right, size_t right_len,
  	bool ignore_whitespace)
  {
  	int cmp;
  
  	if (ignore_whitespace) {
  		int il = 0, ir = 0;
  		while (il < left_len && ir < right_len) {
  			unsigned char cl = left[il];
  			unsigned char cr = right[ir];
  
  			if (isspace(cl) && il < left_len) {
  				il++;
  				continue;
  			}
  			if (isspace(cr) && ir < right_len) {
  				ir++;
  				continue;
  			}
  
  			if (cl > cr)
  				return 1;
  			if (cr > cl)
  				return -1;
  			il++;
  			ir++;
  		}
  		while (il < left_len) {
  			unsigned char cl = left[il++];
  			if (!isspace(cl))
  				return 1;
  		}
  		while (ir < right_len) {
  			unsigned char cr = right[ir++];
  			if (!isspace(cr))
  				return -1;
  		}
  
  		return 0;
  	}
  
  	cmp = memcmp(left, right, MIN(left_len, right_len));
  	if (cmp)
  		return cmp;
  	if (left_len == right_len)
  		return 0;
  	return (left_len > right_len) ? 1 : -1;
  }
  
  int
  diff_atom_cmp(int *cmp,
  	      const struct diff_atom *left,
  	      const struct diff_atom *right)
  {
  	off_t remain_left, remain_right;
  	int flags = (left->root->diff_flags | right->root->diff_flags);
  	bool ignore_whitespace = (flags & DIFF_FLAG_IGNORE_WHITESPACE);
  
  	if (!left->len && !right->len) {
  		*cmp = 0;
  		return 0;
  	}
  	if (!ignore_whitespace) {
  		if (!right->len) {
  			*cmp = 1;
  			return 0;
  		}
  		if (!left->len) {
  			*cmp = -1;
  			return 0;
  		}
  	}
  
  	if (left->at != NULL && right->at != NULL) {
  		*cmp = buf_cmp(left->at, left->len, right->at, right->len,
  		    ignore_whitespace);
  		return 0;
  	}
  
  	remain_left = left->len;
  	remain_right = right->len;
  	while (remain_left > 0 || remain_right > 0) {
  		const size_t chunksz = 8192;
  		unsigned char buf_left[chunksz], buf_right[chunksz];
  		const uint8_t *p_left, *p_right;
  		off_t n_left, n_right;
  		ssize_t r;
  
  		if (!remain_right) {
  			*cmp = 1;
  			return 0;
  		}
  		if (!remain_left) {
  			*cmp = -1;
  			return 0;
  		}
  
  		n_left = MIN(chunksz, remain_left);
  		n_right = MIN(chunksz, remain_right);
  
  		if (left->at == NULL) {
  			r = read_at(left->root->f,
  				    left->pos + (left->len - remain_left),
  				    buf_left, n_left);
  			if (r) {
  				*cmp = 0;
  				return r;
  			}
  			p_left = buf_left;
  		} else {
  			p_left = left->at + (left->len - remain_left);
  		}
  
  		if (right->at == NULL) {
  			r = read_at(right->root->f,
  				    right->pos + (right->len - remain_right),
  				    buf_right, n_right);
  			if (r) {
  				*cmp = 0;
  				return r;
  			}
  			p_right = buf_right;
  		} else {
  			p_right = right->at + (right->len - remain_right);
  		}
  
  		r = buf_cmp(p_left, n_left, p_right, n_right,
  		    ignore_whitespace);
  		if (r) {
  			*cmp = r;
  			return 0;
  		}
  
  		remain_left -= n_left;
  		remain_right -= n_right;
  	}
  
  	*cmp = 0;
  	return 0;
  }
  
  int
  diff_atom_same(bool *same,
  	       const struct diff_atom *left,
  	       const struct diff_atom *right)
  {
  	int cmp;
  	int r;
  	if (left->hash != right->hash) {
  		*same = false;
  		return 0;
  	}
  	r = diff_atom_cmp(&cmp, left, right);
  	if (r) {
  		*same = true;
  		return r;
  	}
  	*same = (cmp == 0);
  	return 0;
  }
  
  static struct diff_chunk *
  diff_state_add_solved_chunk(struct diff_state *state,
  			    const struct diff_chunk *chunk)
  {
  	diff_chunk_arraylist_t *result;
  	struct diff_chunk *new_chunk;
  	enum diff_chunk_type last_t;
  	enum diff_chunk_type new_t;
  	struct diff_chunk *last;
  
  	/* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
  	 * never directly follows a plus chunk. */
  	result = &state->result->chunks;
  
  	last_t = result->len ? diff_chunk_type(&result->head[result->len - 1])
  		: CHUNK_EMPTY;
  	new_t = diff_chunk_type(chunk);
  
  	debug("ADD %s chunk #%u:\n", chunk->solved ? "solved" : "UNSOLVED",
  	      result->len);
  	debug("L\n");
  	debug_dump_atoms(&state->left, chunk->left_start, chunk->left_count);
  	debug("R\n");
  	debug_dump_atoms(&state->right, chunk->right_start, chunk->right_count);
  
  	if (result->len) {
  		last = &result->head[result->len - 1];
  		assert(chunk->left_start
  		       == last->left_start + last->left_count);
  		assert(chunk->right_start
  		       == last->right_start + last->right_count);
  	}
  
  	if (new_t == last_t) {
  		new_chunk = &result->head[result->len - 1];
  		new_chunk->left_count += chunk->left_count;
  		new_chunk->right_count += chunk->right_count;
  		debug("  - added chunk touches previous one of same type, joined:\n");
  		debug("L\n");
  		debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
  		debug("R\n");
  		debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
  	} else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
  		enum diff_chunk_type prev_last_t =
  			result->len > 1 ?
  				diff_chunk_type(&result->head[result->len - 2])
  				: CHUNK_EMPTY;
  		/* If a minus-chunk follows a plus-chunk, place it above the plus-chunk->
  		 * Is the one before that also a minus? combine. */
  		if (prev_last_t == CHUNK_MINUS) {
  			new_chunk = &result->head[result->len - 2];
  			new_chunk->left_count += chunk->left_count;
  			new_chunk->right_count += chunk->right_count;
  
  			debug("  - added minus-chunk follows plus-chunk,"
  			      " put before that plus-chunk and joined"
  			      " with preceding minus-chunk:\n");
  			debug("L\n");
  			debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
  			debug("R\n");
  			debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
  		} else {
  			ARRAYLIST_INSERT(new_chunk, *result, result->len - 1);
  			if (!new_chunk)
  				return NULL;
  			*new_chunk = *chunk;
  
  			/* The new minus chunk indicates to which position on
  			 * the right it corresponds, even though it doesn't add
  			 * any lines on the right. By moving above a plus chunk,
  			 * that position on the right has shifted. */
  			last = &result->head[result->len - 1];
  			new_chunk->right_start = last->right_start;
  
  			debug("  - added minus-chunk follows plus-chunk,"
  			      " put before that plus-chunk\n");
  		}
  
  		/* That last_t == CHUNK_PLUS indicates to which position on the
  		 * left it corresponds, even though it doesn't add any lines on
  		 * the left. By inserting/extending the prev_last_t ==
  		 * CHUNK_MINUS, that position on the left has shifted. */
  		last = &result->head[result->len - 1];
  		last->left_start = new_chunk->left_start
  			+ new_chunk->left_count;
  
  	} else {
  		ARRAYLIST_ADD(new_chunk, *result);
  		if (!new_chunk)
  			return NULL;
  		*new_chunk = *chunk;
  	}
  	return new_chunk;
  }
  
  /* Even if a left or right side is empty, diff output may need to know the
   * position in that file.
   * So left_start or right_start must never be NULL -- pass left_count or
   * right_count as zero to indicate staying at that position without consuming
   * any lines. */
  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_chunk *new_chunk;
  	struct diff_chunk chunk = {
  		.solved = solved,
  		.left_start = left_start,
  		.left_count = left_count,
  		.right_start = right_start,
  		.right_count = right_count,
  	};
  
  	/* An unsolved chunk means store as intermediate result for later
  	 * re-iteration.
  	 * If there already are intermediate results, that means even a
  	 * following solved chunk needs to go to intermediate results, so that
  	 * it is later put in the final correct position in solved chunks.
  	 */
  	if (!solved || state->temp_result.len) {
  		/* Append to temp_result */
  		debug("ADD %s chunk to temp result:\n",
  		      chunk.solved ? "solved" : "UNSOLVED");
  		debug("L\n");
  		debug_dump_atoms(&state->left, left_start, left_count);
  		debug("R\n");
  		debug_dump_atoms(&state->right, right_start, right_count);
  		ARRAYLIST_ADD(new_chunk, state->temp_result);
  		if (!new_chunk)
  			return NULL;
  		*new_chunk = chunk;
  		return new_chunk;
  	}
  
  	return diff_state_add_solved_chunk(state, &chunk);
  }
  
  void
  diff_data_init_root(struct diff_data *d, FILE *f, const uint8_t *data,
      unsigned long long len, int diff_flags)
  {
  	*d = (struct diff_data){
  		.f = f,
  		.pos = 0,
  		.data = data,
  		.len = len,
  		.root = d,
  		.diff_flags = diff_flags,
  	};
  }
  
  void
  diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
  			  struct diff_atom *from_atom, unsigned int atoms_count)
  {
  	struct diff_atom *last_atom;
  
  	debug("diff_data %p  parent %p  from_atom %p  atoms_count %u\n",
  	      d, parent, from_atom, atoms_count);
  	debug("  from_atom ");
  	debug_dump_atom(parent, NULL, from_atom);
  
  	if (atoms_count == 0) {
  		*d = (struct diff_data){
  			.f = NULL,
  			.pos = 0,
  			.data = NULL,
  			.len = 0,
  			.root = parent->root,
  			.atoms.head = NULL,
  			.atoms.len = atoms_count,
  		};
  
  		return;
  	}
  
  	last_atom = from_atom + atoms_count - 1;
  	*d = (struct diff_data){
  		.f = NULL,
  		.pos = from_atom->pos,
  		.data = from_atom->at,
  		.len = (last_atom->pos + last_atom->len) - from_atom->pos,
  		.root = parent->root,
  		.atoms.head = from_atom,
  		.atoms.len = atoms_count,
  	};
  
  	debug("subsection:\n");
  	debug_dump(d);
  }
  
  void
  diff_data_free(struct diff_data *diff_data)
  {
  	if (!diff_data)
  		return;
  	if (diff_data->atoms.allocated)
  		ARRAYLIST_FREE(diff_data->atoms);
  }
  
  int
  diff_algo_none(const struct diff_algo_config *algo_config,
  	       struct diff_state *state)
  {
  	debug("\n** %s\n", __func__);
  	debug("left:\n");
  	debug_dump(&state->left);
  	debug("right:\n");
  	debug_dump(&state->right);
  	debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
  			       0);
  
  	/* Add a chunk of equal lines, if any */
  	struct diff_atom *l = state->left.atoms.head;
  	unsigned int l_len = state->left.atoms.len;
  	struct diff_atom *r = state->right.atoms.head;
  	unsigned int r_len = state->right.atoms.len;
  	unsigned int equal_atoms_start = 0;
  	unsigned int equal_atoms_end = 0;
  	unsigned int l_idx = 0;
  	unsigned int r_idx = 0;
  
  	while (equal_atoms_start < l_len
  	       && equal_atoms_start < r_len) {
  		int err;
  		bool same;
  		err = diff_atom_same(&same, &l[equal_atoms_start],
  				     &r[equal_atoms_start]);
  		if (err)
  			return err;
  		if (!same)
  			break;
  		equal_atoms_start++;
  	}
  	while (equal_atoms_end < (l_len - equal_atoms_start)
  	       && equal_atoms_end < (r_len - equal_atoms_start)) {
  		int err;
  		bool same;
  		err = diff_atom_same(&same, &l[l_len - 1 - equal_atoms_end],
  				   &r[r_len - 1 - equal_atoms_end]);
  		if (err)
  			return err;
  		if (!same)
  			break;
  		equal_atoms_end++;
  	}
  
  	/* Add a chunk of equal lines at the start */
  	if (equal_atoms_start) {
  		if (!diff_state_add_chunk(state, true,
  					  l, equal_atoms_start,
  					  r, equal_atoms_start))
  			return ENOMEM;
  		l_idx += equal_atoms_start;
  		r_idx += equal_atoms_start;
  	}
  
  	/* Add a "minus" chunk with all lines from the left. */
  	if (equal_atoms_start + equal_atoms_end < l_len) {
  		unsigned int add_len = l_len - equal_atoms_start - equal_atoms_end;
  		if (!diff_state_add_chunk(state, true,
  					  &l[l_idx], add_len,
  					  &r[r_idx], 0))
  			return ENOMEM;
  		l_idx += add_len;
  	}
  
  	/* Add a "plus" chunk with all lines from the right. */
  	if (equal_atoms_start + equal_atoms_end < r_len) {
  		unsigned int add_len = r_len - equal_atoms_start - equal_atoms_end;
  		if (!diff_state_add_chunk(state, true,
  					  &l[l_idx], 0,
  					  &r[r_idx], add_len))
  			return ENOMEM;
  		r_idx += add_len;
  	}
  
  	/* Add a chunk of equal lines at the end */
  	if (equal_atoms_end) {
  		if (!diff_state_add_chunk(state, true,
  					  &l[l_idx], equal_atoms_end,
  					  &r[r_idx], equal_atoms_end))
  			return ENOMEM;
  	}
  
  	return DIFF_RC_OK;
  }
  
  int
  diff_run_algo(const struct diff_algo_config *algo_config,
  	      struct diff_state *state)
  {
  	int rc;
  
  	if (!algo_config || !algo_config->impl
  	    || !state->recursion_depth_left
  	    || !state->left.atoms.len || !state->right.atoms.len) {
  		debug("Fall back to diff_algo_none():%s%s%s\n",
  		      (!algo_config || !algo_config->impl) ? " no-cfg" : "",
  		      (!state->recursion_depth_left) ? " max-depth" : "",
  		      (!state->left.atoms.len || !state->right.atoms.len)?
  			      " trivial" : "");
  		return diff_algo_none(algo_config, state);
  	}
  
  	ARRAYLIST_FREE(state->temp_result);
  	ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
  	rc = algo_config->impl(algo_config, state);
  	switch (rc) {
  	case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
  		debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
  		      algo_config->fallback_algo);
  		rc = diff_run_algo(algo_config->fallback_algo, state);
  		goto return_rc;
  
  	case DIFF_RC_OK:
  		/* continue below */
  		break;
  
  	default:
  		/* some error happened */
  		goto return_rc;
  	}
  
  	/* Pick up any diff chunks that are still unsolved and feed to
  	 * inner_algo.  inner_algo will solve unsolved chunks and append to
  	 * result, and subsequent solved chunks on this level are then appended
  	 * to result afterwards. */
  	int i;
  	for (i = 0; i < state->temp_result.len; i++) {
  		struct diff_chunk *c = &state->temp_result.head[i];
  		if (c->solved) {
  			diff_state_add_solved_chunk(state, c);
  			continue;
  		}
  
  		/* c is an unsolved chunk, feed to inner_algo */
  		struct diff_state inner_state = {
  			.result = state->result,
  			.recursion_depth_left = state->recursion_depth_left - 1,
  			.kd_buf = state->kd_buf,
  			.kd_buf_size = state->kd_buf_size,
  		};
  		diff_data_init_subsection(&inner_state.left, &state->left,
  					  c->left_start, c->left_count);
  		diff_data_init_subsection(&inner_state.right, &state->right,
  					  c->right_start, c->right_count);
  
  		rc = diff_run_algo(algo_config->inner_algo, &inner_state);
  		state->kd_buf = inner_state.kd_buf;
  		state->kd_buf_size = inner_state.kd_buf_size;
  		if (rc != DIFF_RC_OK)
  			goto return_rc;
  	}
  
  	rc = DIFF_RC_OK;
  return_rc:
  	ARRAYLIST_FREE(state->temp_result);
  	return rc;
  }
  
  int
  diff_atomize_file(struct diff_data *d,
  		  const struct diff_config *config,
  		  FILE *f, const uint8_t *data, off_t len, int diff_flags)
  {
  	if (!config->atomize_func)
  		return EINVAL;
  
  	diff_data_init_root(d, f, data, len, diff_flags);
  
  	return config->atomize_func(config->atomize_func_data, d);
  
  }
  
  struct diff_result *
  diff_main(const struct diff_config *config, struct diff_data *left,
  	  struct diff_data *right)
  {
  	struct diff_result *result = malloc(sizeof(struct diff_result));
  	if (!result)
  		return NULL;
  
  	*result = (struct diff_result){};
  	result->left = left;
  	result->right = right;
  
  	struct diff_state state = {
  		.result = result,
  		.recursion_depth_left = config->max_recursion_depth ? : 32,
  		.kd_buf = NULL,
  		.kd_buf_size = 0,
  	};
  	diff_data_init_subsection(&state.left, left,
  				  left->atoms.head,
  				  left->atoms.len);
  	diff_data_init_subsection(&state.right, right,
  				  right->atoms.head,
  				  right->atoms.len);
  
  	result->rc = diff_run_algo(config->algo, &state);
  	free(state.kd_buf);
  
  	return result;
  }
  
  void
  diff_result_free(struct diff_result *result)
  {
  	if (!result)
  		return;
  	ARRAYLIST_FREE(result->chunks);
  	free(result);
  }
  

Download