minidiff

minidiff.c

void topicdiff(struct minicat* state,
               const char* where,
               const char* oldtopic,
               const char* newtopic)
{
	if ( !oldtopic )
		oldtopic = "";
	if ( !newtopic )
		newtopic = "";

	size_t oldtopic_len = strlen(oldtopic);
	size_t newtopic_len = strlen(newtopic);

	size_t width = (1+newtopic_len);
	size_t height = (1+oldtopic_len);

	size_t* distances =
		(size_t*) calloc(sizeof(size_t), width * height);
	if ( !distances )
		return;

	for ( size_t i = 0; i < oldtopic_len; i++ )
		distances[(1 + i) * width + 0] = 1 + i;

	for ( size_t j = 0; j < newtopic_len; j++ )
		distances[0 * width + (1 + j)] = 1 + j;

	for ( size_t j = 0; j < newtopic_len; j++ )
	{
		for ( size_t i = 0; i < oldtopic_len; i++ )
		{
			if ( oldtopic[i] == newtopic[j] )
			{
				distances[(1 + i) * width + (1 + j)] =
					distances[(1 + i - 1) * width + (1 + j - 1)];
			}
			else
			{
				size_t del = distances[(1 + i - 1) * width + (1 + j)] + 1;
				size_t ins = distances[(1 + i) * width + (1 + j - 1)] + 1;
				size_t sub = distances[(1 + i - 1) * width + (1 + j - 1)] + 1;
				size_t min = del;
				if ( ins < min )
					min = ins;
				if ( sub < min )
					min = sub;
				distances[(1 + i) * width + (1 + j)] = min;
			}
		}
	}

	size_t distance = distances[oldtopic_len * width + newtopic_len];

	enum topic_edit_change
	{
		TOPIC_EDIT_SUB,
		TOPIC_EDIT_INS,
		TOPIC_EDIT_DEL,
	};

	struct topic_edit
	{
		size_t i;
		size_t j;
		enum topic_edit_change change;
	};

	struct topic_edit* edits = /* + 1 to avoid zero-sized allocation. */
		(struct topic_edit*) calloc(sizeof(struct topic_edit), distance + 1);
	if ( !edits )
	{
		free(distances);
		return;
	}

	{
		size_t i = oldtopic_len;
		size_t j = newtopic_len;
		while ( i != 0 && j != 0 )
		{
			size_t value = distances[i * width + j];

			if ( value && i &&
			     distances[(i-1) * width + (j)] == value - 1 )
			{
				i--;
				edits[value-1].i = i;
				edits[value-1].j = j;
				edits[value-1].change = TOPIC_EDIT_DEL;
				continue;
			}

			if ( value && j &&
			     distances[(i) * width + (j-1)] == value - 1 )
			{
				j--;
				edits[value-1].i = i;
				edits[value-1].j = j;
				edits[value-1].change = TOPIC_EDIT_INS;
				continue;
			}

			if ( value && i && j &&
			     distances[(i-1) * width + (j-1)] == value - 1 )
			{
				i--;
				j--;
				edits[value-1].i = i;
				edits[value-1].j = j;
				edits[value-1].change = TOPIC_EDIT_SUB;
				continue;
			}

			if ( i )
				i--;
			if ( j )
				j--;
			continue;
		}
	}

	char msg[512];
	msg[0] = 0;

	char* out = msg;
	size_t out_size = sizeof(msg);
	bool del_color = false;
	bool ins_color = false;

	{
		size_t i = 0;
		size_t j = 0;
		size_t d_del = 0;
		size_t d_ins = 0;
		while ( i < oldtopic_len || j < newtopic_len )
		{
			if ( d_del < distance && edits[d_del].i == i )
			{
				if ( edits[d_del].change == TOPIC_EDIT_DEL ||
				     edits[d_del].change == TOPIC_EDIT_SUB )
				{
					if ( ins_color )
						string_append(&out, &out_size, "\x03""05");
					else if ( !del_color )
						string_append(&out, &out_size, "\x1F\x03""05");
					ins_color = false;
					del_color = true;
					string_append_c(&out, &out_size, oldtopic[i++]);
				}
				d_del++;
			}
			else if ( d_ins < distance && edits[d_ins].j == j )
			{
				if ( edits[d_ins].change == TOPIC_EDIT_INS ||
				     edits[d_ins].change == TOPIC_EDIT_SUB )
					{
					if ( del_color )
						string_append(&out, &out_size, "\x03""03");
					else if ( !ins_color )
						string_append(&out, &out_size, "\x1F\x03""03");
					del_color = false;
					ins_color = true;
					string_append_c(&out, &out_size, newtopic[j++]);
				}
				d_ins++;
			}
			else
			{
				if ( del_color || ins_color )
					string_append(&out, &out_size, "\x0F");
				del_color = false;
				ins_color = false;
				string_append_c(&out, &out_size, oldtopic[j++, i++]);
			}
		}
	}

	irc_command_botprivmsgf(state->irc_connection, where, "(diff) %s", msg);

	free(edits);
	free(distances);
}