<commit_before>/*
 * libopensync - A synchronization framework
 * Copyright (C) 2004-2005  <NAME> <<EMAIL>>
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 * 
 */
 
#include "opensync.h"
#include "opensync_internals.h"

#include "opensync-module.h"
#include "opensync-data.h"
#include "opensync-format.h"
#include "opensync_format_env_internals.h"

/*! @brief Loads the modules from a given directory
 * 
 * Loads all modules from a directory into a osync environment
 * 
 * @param env Pointer to a OSyncFormatEnv environment
 * @param path The path where to look for plugins, NULL for the default sync module directory
 * @param must_exist If set to TRUE, this function will return an error if the directory does not exist
 * @param error Pointer to a error struct to return an error
 * @returns TRUE on success, FALSE otherwise
 * 
 */
static osync_bool _osync_format_env_load_modules(OSyncFormatEnv *env, const char *path, osync_bool must_exist, OSyncError **error)
{
	GDir *dir = NULL;
	GError *gerror = NULL;
	char *filename = NULL;
	OSyncModule *module = NULL;
	const gchar *de = NULL;
	GList *m = NULL;
	
	osync_trace(TRACE_ENTRY, "%s(%p, %s, %i, %p)", __func__, env, path, must_exist, error);
	osync_assert(env);
	osync_assert(path);
	
	//Load all available shared libraries (plugins)
	if (!g_file_test(path, G_FILE_TEST_IS_DIR)) {
		if (must_exist) {
			osync_error_set(error, OSYNC_ERROR_GENERIC, "Path is not loadable");
			goto error;
		} else {
			osync_trace(TRACE_EXIT, "%s: Directory does not exist (non-fatal)", __func__);
			return TRUE;
		}
	}
	
	dir = g_dir_open(path, 0, &gerror);
	if (!dir) {
		osync_error_set(error, OSYNC_ERROR_IO_ERROR, "Unable to open directory %s: %s", path, gerror->message);
		g_error_free(gerror);
		goto error;
	}
	
	while ((de = g_dir_read_name(dir))) {
		filename = g_strdup_printf ("%s%c%s", path, G_DIR_SEPARATOR, de);
		
		if (!g_file_test(filename, G_FILE_TEST_IS_REGULAR) || !g_pattern_match_simple("*."G_MODULE_SUFFIX, filename)) {
			g_free(filename);
			continue;
		}
		
		module = osync_module_new(error);
		if (!module)
			goto error_free_filename;
		
		if (!osync_module_load(module, filename, error)) {
			osync_trace(TRACE_INTERNAL, "Unable to load module %s: %s", filename, osync_error_print(error));
			osync_error_unref(error);
			osync_module_free(module);
			g_free(filename);
			continue;
		}
		
		if (!osync_module_check(module, error)) {
			if (osync_error_is_set(error)) {
				osync_trace(TRACE_INTERNAL, "Module check error for %s: %s", filename, osync_error_print(error));
				osync_error_unref(error);
			}
			osync_module_free(module);
			g_free(filename);
			continue;
		}
	
		if (!osync_module_get_format_info(module, env, error)) {
			if (osync_error_is_set(error)) {
				osync_trace(TRACE_INTERNAL, "Module get format error for %s: %s", filename, osync_error_print(error));
				osync_error_unref(error);
			}
			osync_module_free(module);
			g_free(filename);
			continue;
		}
		
		env->modules = g_list_append(env->modules, module);
		
		g_free(filename);
	}
	
	g_dir_close(dir);
	
	/* Load the converters, filters, etc */
	for (m = env->modules; m; m = m->next) {
		module = m->data;
		if (!osync_module_get_conversion_info(module, env, error)) {
			osync_trace(TRACE_INTERNAL, "Module get conversion error %s", osync_error_print(error));
			osync_error_unref(error);
		}
	}
	
	osync_trace(TRACE_EXIT, "%s", __func__);
	return TRUE;

error_free_filename:
	g_free(filename);
	g_dir_close(dir);
error:
	osync_trace(TRACE_EXIT_ERROR, "%s: %s", __func__, osync_error_print(error));
	return FALSE;
}

/** Compare the distance of two vertices
 *
 * First, try to minimize the losses. Then,
 * try to minimize the conversions between
 * different objtypes. Then, try to minimize
 * the total number of conversions.
 */
static int _compare_vertice_distance(const void *a, const void *b)
{
	const vertice *va = a;
	const vertice *vb = b;
	if (va->losses < vb->losses)
		return -1;
	else if (va->losses > vb->losses)
		return 1;
	else if (va->objtype_changes < vb->objtype_changes)
		return -1;
	else if (va->objtype_changes > vb->objtype_changes)
		return 1;
	else if (va->conversions < vb->conversions)
		return -1;
	else if (va->conversions > vb->conversions)
		return 1;
	else
		return 0;
}

/** Function used on a path search for a OSyncList of OSyncObjFormatSinks 
 *
 * @see osync_conv_find_path_fn(), osync_change_convert_fmtnames()
 */
static osync_bool _target_fn_format_sinks(const void *data, OSyncObjFormat *fmt)
{
	OSyncList *f, *formats = (OSyncList *) data;
	for (f = formats; f; f = f->next) {
		OSyncObjFormatSink *format_sink = f->data;
		const char *format = osync_objformat_sink_get_objformat(format_sink);
		/*if (osync_objformat_is_equal(fmt, format))*/
		if (!strcmp(format, osync_objformat_get_name(fmt)))
			/* Found */
			return TRUE;
	}

	/* Not found */
	return FALSE;
}

/** Function used on path searchs for a single format
 *
 * @see osync_conv_find_path_fn(), osync_change_convert()
 */
static osync_bool _target_fn_simple(const void *data, OSyncObjFormat *fmt)
{
	OSyncObjFormat *target = (OSyncObjFormat *)data;
	return osync_objformat_is_equal(target, fmt);
}

static vertice *_vertice_new(OSyncError **error)
{
	vertice *v = osync_try_malloc0(sizeof(vertice), error);
	if (!v)
		return NULL;

	v->ref_count = 1;

	return v;
}

/** Increment a vertice reference count */
static vertice *_vertice_ref(vertice *vertice)
{
	osync_assert(vertice);
	
	g_atomic_int_inc(&(vertice->ref_count));

	return vertice;
}

/** Dereference a vertice
 */
static void _vertice_unref(vertice *vertice)
{
	osync_assert(vertice);
		
	if (g_atomic_int_dec_and_test(&(vertice->ref_count))) {

		g_list_free(vertice->path);

		if(vertice->data)
			osync_data_unref(vertice->data);

		g_free(vertice);
	}
}

static osync_bool _validate_path_with_detector(vertice *ve, OSyncFormatEnv *env, OSyncFormatConverter *converter) {

	// check if a detector validate this path
	OSyncList *cs = NULL;
	OSyncList *cd = NULL;
	osync_bool has_detector = FALSE;
	osync_bool has_nondetector = FALSE;
	osync_bool detector_success = FALSE;
	osync_trace(TRACE_INTERNAL, "Converter %s to %s type %i", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)), osync_converter_get_type(converter));

	// Looking after detector without adhoc converter
	OSyncList *converters_seekdetectors = osync_format_env_find_converters(env, osync_converter_get_sourceformat(converter), osync_converter_get_targetformat(converter));
	for(cd = converters_seekdetectors; cd ; cd = cd->next) {
		OSyncFormatConverter *converter_seekdetectors = cd->data;
		if ( converter_seekdetectors && (osync_converter_get_type(converter_seekdetectors) != OSYNC_CONVERTER_DETECTOR) ) {
			osync_trace(TRACE_INTERNAL, "Found non detector adhoc converter . Pairing detector with the non detector converter.");
			has_nondetector = TRUE;
			break;
		}
	}
	if (has_nondetector) {
		// Skip the detector : it will be handled later on when processing the non detector converter
		if ( osync_converter_get_type(converter) == OSYNC_CONVERTER_DETECTOR )
			return FALSE;

		// Looking after detector for adhoc converter
		OSyncList *converters_sameformat = osync_format_env_find_converters(env, osync_converter_get_sourceformat(converter), osync_converter_get_targetformat(converter));
		for(cs = converters_sameformat; cs ; cs = cs->next) {
			OSyncFormatConverter *converter_sameformat = cs->data;
			if ( converter_sameformat && (osync_converter_get_type(converter_sameformat) == OSYNC_CONVERTER_DETECTOR) ) {
				has_detector = TRUE;
				osync_trace(TRACE_INTERNAL, "detector found");
				if(osync_converter_detect(converter_sameformat, ve->data)) {
					detector_success = TRUE;
					osync_trace(TRACE_INTERNAL, "Invoked detector for converter from %s to %s: TRUE", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)));
				} else {
					osync_trace(TRACE_INTERNAL, "Invoked detector for converter from %s to %s: FALSE", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)));
				}
			}
		}
		if (has_detector)
			if (!detector_success)
				return FALSE;
	} else {
		osync_trace(TRACE_INTERNAL, "alone detector found");
		if(osync_converter_detect(converter, ve->data)) {
			osync_trace(TRACE_INTERNAL, "Invoked detector for converter from %s to %s: TRUE", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)));
			return TRUE;

		} else {
			osync_trace(TRACE_INTERNAL, "Invoked detector for converter from %s to %s: FALSE", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)));
			return FALSE;
		}
	}

	return TRUE;
}

/** Returns a neighbour of the vertice ve
 *
 * Returns a new reference to the vertice. The reference
 * should be dropped using deref_vertice(), later.
 */
static vertice *_get_next_vertice_neighbour(OSyncFormatEnv *env, conv_tree *tree, vertice *ve, OSyncError **error)
{
	GList *c = NULL;
	OSyncFormatConverter *converter = NULL;
	OSyncObjFormat *fmt_target = NULL;
	vertice *neigh = NULL;
	const char *source_objtype = NULL;
	const char *target_objtype = NULL;
	
	osync_trace(TRACE_ENTRY, "%s(%p, %p, %p)", __func__, env, tree, ve);
	
	/* Ok. we need to get the next valid neighbour to our input vertice.
	 * Valid neighbours are the once that are reachable by a conversion. So
	 * we now go through all converters and check if they are valid */
	for (c = tree->unused; c; c = c->next) {
		converter = c->data;
		fmt_target = osync_converter_get_targetformat(converter);
		
		/* Check only valid converters, from the right format */
		if (!osync_objformat_is_equal(osync_converter_get_sourceformat(converter), ve->format))
			continue;

		/* Only validate with the help of detectors, if data is
		   available to run a detector on it. */
		if (osync_data_has_data(ve->data) 
			&& !_validate_path_with_detector(ve, env, converter))
			continue;

		/* Remove the converter from the unused list */
		tree->unused = g_list_remove(tree->unused, converter);

		/* Allocate the new neighbour */
		neigh = _vertice_new(error);
		if (!neigh)
			goto error;
		
		neigh->format = fmt_target;
		neigh->path = g_list_copy(ve->path);
		neigh->path = g_list_append(neigh->path, converter);
	
		/* Distance calculation */
		neigh->conversions = ve->conversions + 1;
		
		neigh->losses = ve->losses;
		if (osync_converter_get_type(converter) == OSYNC_CONVERTER_DECAP)
			neigh->losses++;
		
		neigh->objtype_changes = ve->objtype_changes;
		
		OSyncObjFormat *sourceformat = osync_converter_get_sourceformat(converter);
		OSyncObjFormat *targetformat = osync_converter_get_targetformat(converter);
		
		source_objtype = osync_objformat_get_objtype(sourceformat);
		target_objtype = osync_objformat_get_objtype(targetformat);
		if (strcmp(source_objtype, target_objtype))
			neigh->objtype_changes++;

		osync_trace(TRACE_EXIT, "%s: %p (converter from %s to %s) objtype changes : %i losses : %i", __func__, neigh, osync_objformat_get_name(sourceformat), osync_objformat_get_name(targetformat), neigh->objtype_changes, neigh->losses);
		return neigh;
	}
	
	osync_trace(TRACE_EXIT, "%s: None found", __func__);
	return NULL;

error:
	osync_trace(TRACE_EXIT_ERROR, "%s: %s", __func__, osync_error_print(error));
	return NULL;
}

static void _free_tree(conv_tree *tree)
{
	/* Remove the remaining references on the search queue */
	g_list_foreach(tree->search, (GFunc)_vertice_unref, NULL);
	
	g_list_free(tree->unused);
	g_list_free(tree->search);
	g_free(tree);
}

/** Search for the shortest path of conversions to one or more formats
 *
 * This function search for the shortest path of conversions
 * that can be made to a change, considering possible detections
 * that may be necessary. The target is given by a function
 * that check if a given format is a 'target vertice' or not. The
 * function is used to allow the search path code to be used
 * to search for 'objtype detection', search for the path
 * for an available sink for a format, and maybe other uses.
 *
 * There is a limitation however. To prevent
 * 
 * The list returned on path_edges should be freed by the caller.
 *
 * Note: NEVER use the detection/conversion functions on
 *       CHANGE_DELETED changes. Converting and detecting data
 *       on changes that have no data doesn't make sense
 *
 * @param env Pointer to a OSyncFormatEnv environment
 * @see osync_conv_convert_fn(), osync_change_convert(),
 *      osync_conv_convert_fmtlist(), osync_change_convert_member_sink()
 *
 * @see target_fn_fmtlist(), target_fn_fmtnames(),
 *      target_fn_simple(), target_fn_fmtname(),
 *      target_fn_membersink(), target_fn_no_any()
 */
static OSyncFormatConverterPath *_osync_format_env_find_path_fn(OSyncFormatEnv *env, OSyncData *sourcedata, OSyncPathTargetFn target_fn, const void *fndata, OSyncError **error)
{
	vertice *result = NULL;
	vertice *neighbour = NULL;
	OSyncFormatConverterPath *path = NULL;
	conv_tree *tree = NULL;
	vertice *begin = NULL;
	GList *e;
	
	osync_trace(TRACE_ENTRY, "%s(%p, %p, %p, %p, %p)", __func__, env, sourcedata, target_fn, fndata, error);
	osync_assert(env);
	osync_assert(sourcedata);
	osync_assert(target_fn);
	
	//Vertice = Spitze = Format
	//edge = Kante = Converter

	/* Optimization: check if the format is already valid */
	if (target_fn(fndata, osync_data_get_objformat(sourcedata))) {
		path = osync_converter_path_new(error);
		if (!path)
			goto error;
		
		osync_trace(TRACE_EXIT, "%s: Target already valid", __func__);
		return path;
	}

	/* Make a new search tree */
	tree = osync_try_malloc0(sizeof(conv_tree), error);
	if (!tree)
		goto error;
	tree->unused = g_list_copy(env->converters);
	
	/* We make our starting point (which is the current format of the 
	 * change of course */
	begin = _vertice_new(error);
	if (!begin)
		goto error_free_tree;
	
	begin->format = osync_data_get_objformat(sourcedata);
	begin->path = NULL;
	
	tree->search = g_list_append(NULL, begin);
	
	/* While there are still vertices in our
	 * search queue */
	while (g_list_length(tree->search)) {
		/* Get the first vertice from the search queue
		 * and remove it from the queue */
		vertice *current = tree->search->data;
		tree->search = g_list_remove(tree->search, current);
		
		osync_trace(TRACE_INTERNAL, "Next vertice : %s.", osync_objformat_get_name(current->format));	
		/* Check if we have reached a target format */
		if (target_fn(fndata, current->format)) {
			osync_trace(TRACE_INTERNAL, "Target %s found", osync_objformat_get_name(current->format));
			/* Done. return the result */
			result = current;
			break;
		}
		
		/* Optimitazion:
		 * Check if saved result is equal to current regarding losses, objtype_changes
		 * and conversions. If yes, we can skip further searches and break here */
		if (result) {
			if (result->losses <= current->losses && result->objtype_changes <= current->objtype_changes && result->conversions <= current->conversions) {
				osync_trace(TRACE_INTERNAL, "Target %s found in queue", osync_objformat_get_name(result->format));
				tree->search = g_list_remove(tree->search, result);
				break;
			} else {
				result = NULL;
			}
		}

		/* If we dont have reached a target, we look at our neighbours */
		osync_trace(TRACE_INTERNAL, "Looking at %s's neighbours.", osync_objformat_get_name(current->format));
		current->data = osync_data_clone(sourcedata, error);

		OSyncFormatConverterPath *path_tmp = osync_converter_path_new(error);
		if (!path_tmp)
			goto error;
		
		for (e = current->path; e; e = e->next) {
			OSyncFormatConverter *edge = e->data;
			osync_converter_path_add_edge(path_tmp, edge);
		}
		if (!(osync_format_env_convert(env, path_tmp, current->data, error))) {
			osync_trace(TRACE_INTERNAL, "osync format env convert on this path failed - skipping the conversion");
			continue;
		}
		osync_converter_path_unref(path_tmp);

		while ((neighbour = _get_next_vertice_neighbour(env, tree, current, error))) {
			/* We found a neighbour and insert it sorted in our search queue */
			osync_trace(TRACE_INTERNAL, "%s's neighbour : %s", osync_objformat_get_name(current->format), osync_objformat_get_name(neighbour->format));<commit_msg>Removing heavy check for conversion validity. We'll keep our converter clean and this will let us forget about this heavy check of the conversion path at each build of it.<commit_after>/*
 * libopensync - A synchronization framework
 * Copyright (C) 2004-2005  <NAME> <<EMAIL>>
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 * 
 */
 
#include "opensync.h"
#include "opensync_internals.h"

#include "opensync-module.h"
#include "opensync-data.h"
#include "opensync-format.h"
#include "opensync_format_env_internals.h"

/*! @brief Loads the modules from a given directory
 * 
 * Loads all modules from a directory into a osync environment
 * 
 * @param env Pointer to a OSyncFormatEnv environment
 * @param path The path where to look for plugins, NULL for the default sync module directory
 * @param must_exist If set to TRUE, this function will return an error if the directory does not exist
 * @param error Pointer to a error struct to return an error
 * @returns TRUE on success, FALSE otherwise
 * 
 */
static osync_bool _osync_format_env_load_modules(OSyncFormatEnv *env, const char *path, osync_bool must_exist, OSyncError **error)
{
	GDir *dir = NULL;
	GError *gerror = NULL;
	char *filename = NULL;
	OSyncModule *module = NULL;
	const gchar *de = NULL;
	GList *m = NULL;
	
	osync_trace(TRACE_ENTRY, "%s(%p, %s, %i, %p)", __func__, env, path, must_exist, error);
	osync_assert(env);
	osync_assert(path);
	
	//Load all available shared libraries (plugins)
	if (!g_file_test(path, G_FILE_TEST_IS_DIR)) {
		if (must_exist) {
			osync_error_set(error, OSYNC_ERROR_GENERIC, "Path is not loadable");
			goto error;
		} else {
			osync_trace(TRACE_EXIT, "%s: Directory does not exist (non-fatal)", __func__);
			return TRUE;
		}
	}
	
	dir = g_dir_open(path, 0, &gerror);
	if (!dir) {
		osync_error_set(error, OSYNC_ERROR_IO_ERROR, "Unable to open directory %s: %s", path, gerror->message);
		g_error_free(gerror);
		goto error;
	}
	
	while ((de = g_dir_read_name(dir))) {
		filename = g_strdup_printf ("%s%c%s", path, G_DIR_SEPARATOR, de);
		
		if (!g_file_test(filename, G_FILE_TEST_IS_REGULAR) || !g_pattern_match_simple("*."G_MODULE_SUFFIX, filename)) {
			g_free(filename);
			continue;
		}
		
		module = osync_module_new(error);
		if (!module)
			goto error_free_filename;
		
		if (!osync_module_load(module, filename, error)) {
			osync_trace(TRACE_INTERNAL, "Unable to load module %s: %s", filename, osync_error_print(error));
			osync_error_unref(error);
			osync_module_free(module);
			g_free(filename);
			continue;
		}
		
		if (!osync_module_check(module, error)) {
			if (osync_error_is_set(error)) {
				osync_trace(TRACE_INTERNAL, "Module check error for %s: %s", filename, osync_error_print(error));
				osync_error_unref(error);
			}
			osync_module_free(module);
			g_free(filename);
			continue;
		}
	
		if (!osync_module_get_format_info(module, env, error)) {
			if (osync_error_is_set(error)) {
				osync_trace(TRACE_INTERNAL, "Module get format error for %s: %s", filename, osync_error_print(error));
				osync_error_unref(error);
			}
			osync_module_free(module);
			g_free(filename);
			continue;
		}
		
		env->modules = g_list_append(env->modules, module);
		
		g_free(filename);
	}
	
	g_dir_close(dir);
	
	/* Load the converters, filters, etc */
	for (m = env->modules; m; m = m->next) {
		module = m->data;
		if (!osync_module_get_conversion_info(module, env, error)) {
			osync_trace(TRACE_INTERNAL, "Module get conversion error %s", osync_error_print(error));
			osync_error_unref(error);
		}
	}
	
	osync_trace(TRACE_EXIT, "%s", __func__);
	return TRUE;

error_free_filename:
	g_free(filename);
	g_dir_close(dir);
error:
	osync_trace(TRACE_EXIT_ERROR, "%s: %s", __func__, osync_error_print(error));
	return FALSE;
}

/** Compare the distance of two vertices
 *
 * First, try to minimize the losses. Then,
 * try to minimize the conversions between
 * different objtypes. Then, try to minimize
 * the total number of conversions.
 */
static int _compare_vertice_distance(const void *a, const void *b)
{
	const vertice *va = a;
	const vertice *vb = b;
	if (va->losses < vb->losses)
		return -1;
	else if (va->losses > vb->losses)
		return 1;
	else if (va->objtype_changes < vb->objtype_changes)
		return -1;
	else if (va->objtype_changes > vb->objtype_changes)
		return 1;
	else if (va->conversions < vb->conversions)
		return -1;
	else if (va->conversions > vb->conversions)
		return 1;
	else
		return 0;
}

/** Function used on a path search for a OSyncList of OSyncObjFormatSinks 
 *
 * @see osync_conv_find_path_fn(), osync_change_convert_fmtnames()
 */
static osync_bool _target_fn_format_sinks(const void *data, OSyncObjFormat *fmt)
{
	OSyncList *f, *formats = (OSyncList *) data;
	for (f = formats; f; f = f->next) {
		OSyncObjFormatSink *format_sink = f->data;
		const char *format = osync_objformat_sink_get_objformat(format_sink);
		/*if (osync_objformat_is_equal(fmt, format))*/
		if (!strcmp(format, osync_objformat_get_name(fmt)))
			/* Found */
			return TRUE;
	}

	/* Not found */
	return FALSE;
}

/** Function used on path searchs for a single format
 *
 * @see osync_conv_find_path_fn(), osync_change_convert()
 */
static osync_bool _target_fn_simple(const void *data, OSyncObjFormat *fmt)
{
	OSyncObjFormat *target = (OSyncObjFormat *)data;
	return osync_objformat_is_equal(target, fmt);
}

static vertice *_vertice_new(OSyncError **error)
{
	vertice *v = osync_try_malloc0(sizeof(vertice), error);
	if (!v)
		return NULL;

	v->ref_count = 1;

	return v;
}

/** Increment a vertice reference count */
static vertice *_vertice_ref(vertice *vertice)
{
	osync_assert(vertice);
	
	g_atomic_int_inc(&(vertice->ref_count));

	return vertice;
}

/** Dereference a vertice
 */
static void _vertice_unref(vertice *vertice)
{
	osync_assert(vertice);
		
	if (g_atomic_int_dec_and_test(&(vertice->ref_count))) {

		g_list_free(vertice->path);

		if(vertice->data)
			osync_data_unref(vertice->data);

		g_free(vertice);
	}
}

static osync_bool _validate_path_with_detector(vertice *ve, OSyncFormatEnv *env, OSyncFormatConverter *converter) {

	// check if a detector validate this path
	OSyncList *cs = NULL;
	OSyncList *cd = NULL;
	osync_bool has_detector = FALSE;
	osync_bool has_nondetector = FALSE;
	osync_bool detector_success = FALSE;
	osync_trace(TRACE_INTERNAL, "Converter %s to %s type %i", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)), osync_converter_get_type(converter));

	// Looking after detector without adhoc converter
	OSyncList *converters_seekdetectors = osync_format_env_find_converters(env, osync_converter_get_sourceformat(converter), osync_converter_get_targetformat(converter));
	for(cd = converters_seekdetectors; cd ; cd = cd->next) {
		OSyncFormatConverter *converter_seekdetectors = cd->data;
		if ( converter_seekdetectors && (osync_converter_get_type(converter_seekdetectors) != OSYNC_CONVERTER_DETECTOR) ) {
			osync_trace(TRACE_INTERNAL, "Found non detector adhoc converter . Pairing detector with the non detector converter.");
			has_nondetector = TRUE;
			break;
		}
	}
	if (has_nondetector) {
		// Skip the detector : it will be handled later on when processing the non detector converter
		if ( osync_converter_get_type(converter) == OSYNC_CONVERTER_DETECTOR )
			return FALSE;

		// Looking after detector for adhoc converter
		OSyncList *converters_sameformat = osync_format_env_find_converters(env, osync_converter_get_sourceformat(converter), osync_converter_get_targetformat(converter));
		for(cs = converters_sameformat; cs ; cs = cs->next) {
			OSyncFormatConverter *converter_sameformat = cs->data;
			if ( converter_sameformat && (osync_converter_get_type(converter_sameformat) == OSYNC_CONVERTER_DETECTOR) ) {
				has_detector = TRUE;
				osync_trace(TRACE_INTERNAL, "detector found");
				if(osync_converter_detect(converter_sameformat, ve->data)) {
					detector_success = TRUE;
					osync_trace(TRACE_INTERNAL, "Invoked detector for converter from %s to %s: TRUE", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)));
				} else {
					osync_trace(TRACE_INTERNAL, "Invoked detector for converter from %s to %s: FALSE", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)));
				}
			}
		}
		if (has_detector)
			if (!detector_success)
				return FALSE;
	} else {
		osync_trace(TRACE_INTERNAL, "alone detector found");
		if(osync_converter_detect(converter, ve->data)) {
			osync_trace(TRACE_INTERNAL, "Invoked detector for converter from %s to %s: TRUE", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)));
			return TRUE;

		} else {
			osync_trace(TRACE_INTERNAL, "Invoked detector for converter from %s to %s: FALSE", osync_objformat_get_name(osync_converter_get_sourceformat(converter)), osync_objformat_get_name(osync_converter_get_targetformat(converter)));
			return FALSE;
		}
	}

	return TRUE;
}

/** Returns a neighbour of the vertice ve
 *
 * Returns a new reference to the vertice. The reference
 * should be dropped using deref_vertice(), later.
 */
static vertice *_get_next_vertice_neighbour(OSyncFormatEnv *env, conv_tree *tree, vertice *ve, OSyncError **error)
{
	GList *c = NULL;
	OSyncFormatConverter *converter = NULL;
	OSyncObjFormat *fmt_target = NULL;
	vertice *neigh = NULL;
	const char *source_objtype = NULL;
	const char *target_objtype = NULL;
	
	osync_trace(TRACE_ENTRY, "%s(%p, %p, %p)", __func__, env, tree, ve);
	
	/* Ok. we need to get the next valid neighbour to our input vertice.
	 * Valid neighbours are the once that are reachable by a conversion. So
	 * we now go through all converters and check if they are valid */
	for (c = tree->unused; c; c = c->next) {
		converter = c->data;
		fmt_target = osync_converter_get_targetformat(converter);
		
		/* Check only valid converters, from the right format */
		if (!osync_objformat_is_equal(osync_converter_get_sourceformat(converter), ve->format))
			continue;

		/* Only validate with the help of detectors, if data is
		   available to run a detector on it. */
		if (osync_data_has_data(ve->data) 
			&& !_validate_path_with_detector(ve, env, converter))
			continue;

		/* Remove the converter from the unused list */
		tree->unused = g_list_remove(tree->unused, converter);

		/* Allocate the new neighbour */
		neigh = _vertice_new(error);
		if (!neigh)
			goto error;
		
		neigh->format = fmt_target;
		neigh->path = g_list_copy(ve->path);
		neigh->path = g_list_append(neigh->path, converter);
	
		/* Distance calculation */
		neigh->conversions = ve->conversions + 1;
		
		neigh->losses = ve->losses;
		if (osync_converter_get_type(converter) == OSYNC_CONVERTER_DECAP)
			neigh->losses++;
		
		neigh->objtype_changes = ve->objtype_changes;
		
		OSyncObjFormat *sourceformat = osync_converter_get_sourceformat(converter);
		OSyncObjFormat *targetformat = osync_converter_get_targetformat(converter);
		
		source_objtype = osync_objformat_get_objtype(sourceformat);
		target_objtype = osync_objformat_get_objtype(targetformat);
		if (strcmp(source_objtype, target_objtype))
			neigh->objtype_changes++;

		osync_trace(TRACE_EXIT, "%s: %p (converter from %s to %s) objtype changes : %i losses : %i", __func__, neigh, osync_objformat_get_name(sourceformat), osync_objformat_get_name(targetformat), neigh->objtype_changes, neigh->losses);
		return neigh;
	}
	
	osync_trace(TRACE_EXIT, "%s: None found", __func__);
	return NULL;

error:
	osync_trace(TRACE_EXIT_ERROR, "%s: %s", __func__, osync_error_print(error));
	return NULL;
}

static void _free_tree(conv_tree *tree)
{
	/* Remove the remaining references on the search queue */
	g_list_foreach(tree->search, (GFunc)_vertice_unref, NULL);
	
	g_list_free(tree->unused);
	g_list_free(tree->search);
	g_free(tree);
}

/** Search for the shortest path of conversions to one or more formats
 *
 * This function search for the shortest path of conversions
 * that can be made to a change, considering possible detections
 * that may be necessary. The target is given by a function
 * that check if a given format is a 'target vertice' or not. The
 * function is used to allow the search path code to be used
 * to search for 'objtype detection', search for the path
 * for an available sink for a format, and maybe other uses.
 *
 * There is a limitation however. To prevent
 * 
 * The list returned on path_edges should be freed by the caller.
 *
 * Note: NEVER use the detection/conversion functions on
 *       CHANGE_DELETED changes. Converting and detecting data
 *       on changes that have no data doesn't make sense
 *
 * @param env Pointer to a OSyncFormatEnv environment
 * @see osync_conv_convert_fn(), osync_change_convert(),
 *      osync_conv_convert_fmtlist(), osync_change_convert_member_sink()
 *
 * @see target_fn_fmtlist(), target_fn_fmtnames(),
 *      target_fn_simple(), target_fn_fmtname(),
 *      target_fn_membersink(), target_fn_no_any()
 */
static OSyncFormatConverterPath *_osync_format_env_find_path_fn(OSyncFormatEnv *env, OSyncData *sourcedata, OSyncPathTargetFn target_fn, const void *fndata, OSyncError **error)
{
	vertice *result = NULL;
	vertice *neighbour = NULL;
	OSyncFormatConverterPath *path = NULL;
	conv_tree *tree = NULL;
	vertice *begin = NULL;
	GList *e;
	
	osync_trace(TRACE_ENTRY, "%s(%p, %p, %p, %p, %p)", __func__, env, sourcedata, target_fn, fndata, error);
	osync_assert(env);
	osync_assert(sourcedata);
	osync_assert(target_fn);
	
	//Vertice = Spitze = Format
	//edge = Kante = Converter

	/* Optimization: check if the format is already valid */
	if (target_fn(fndata, osync_data_get_objformat(sourcedata))) {
		path = osync_converter_path_new(error);
		if (!path)
			goto error;
		
		osync_trace(TRACE_EXIT, "%s: Target already valid", __func__);
		return path;
	}

	/* Make a new search tree */
	tree = osync_try_malloc0(sizeof(conv_tree), error);
	if (!tree)
		goto error;
	tree->unused = g_list_copy(env->converters);
	
	/* We make our starting point (which is the current format of the 
	 * change of course */
	begin = _vertice_new(error);
	if (!begin)
		goto error_free_tree;
	
	begin->format = osync_data_get_objformat(sourcedata);
	begin->path = NULL;
	
	tree->search = g_list_append(NULL, begin);
	
	/* While there are still vertices in our
	 * search queue */
	while (g_list_length(tree->search)) {
		/* Get the first vertice from the search queue
		 * and remove it from the queue */
		vertice *current = tree->search->data;
		tree->search = g_list_remove(tree->search, current);
		
		osync_trace(TRACE_INTERNAL, "Next vertice : %s.", osync_objformat_get_name(current->format));	
		/* Check if we have reached a target format */
		if (target_fn(fndata, current->format)) {
			osync_trace(TRACE_INTERNAL, "Target %s found", osync_objformat_get_name(current->format));
			/* Done. return the result */
			result = current;
			break;
		}
		
		/* Optimitazion:
		 * Check if saved result is equal to current regarding losses, objtype_changes
		 * and conversions. If yes, we can skip further searches and break here */
		if (result) {
			if (result->losses <= current->losses && result->objtype_changes <= current->objtype_changes && result->conversions <= current->conversions) {
				osync_trace(TRACE_INTERNAL, "Target %s found in queue", osync_objformat_get_name(result->format));
				tree->search = g_list_remove(tree->search, result);
				break;
			} else {
				result = NULL;
			}
		}

		/* If we dont have reached a target, we look at our neighbours */
		osync_trace(TRACE_INTERNAL, "Looking at %s's neighbours.", osync_objformat_get_name(current->format));
		current->data = osync_data_clone(sourcedata, error);

		while ((neighbour = _get_next_vertice_neighbour(env, tree, current, error))) {
			/* We found a neighbour and insert it sorted in our search queue */
			osync_trace(TRACE_INTERNAL, "%s's neighbour : %s", osync_objformat_get_name(current->format), osync_objformat_get_name(neighbour->format));
{'fraction_non_alphanumeric': 0.10686170837739396, 'fraction_numerical': 0.0021149101163200562, 'mean_word_length': 4.875906109768726, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 185, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5985312', 'n_tokens_mistral': 12321, 'n_tokens_neox': 11397, 'n_words': 3065}