test-driver.c
author Kristian H?gsberg <krh@redhat.com>
Mon Jun 09 12:47:37 2008 -0400 (2008-06-09)
changeset 230 c1e2aed8dd07
parent 210 c78f677d96b8
permissions -rw-r--r--
Rewrite depsolver to use a series of passes over all packages.

The big change is that we follow one step of the depedency chain for
each package to resolve in each iteration, and repeat until there are
no more possible moves. In contrast the old depsolver would try to
follow the dependency chain completely for one package at a time.

This new approach is simpler and faster, and at the same time more
roboust. Instead of knowing how one newly installed package may
affect other packages (obsoleting, pulling in new packages etc), the
new algorithm just looks at the total list of requires, provides,
obsoletes and conflicts after installing new packages.
krh@80
     1
#include <stdio.h>
krh@80
     2
#include <string.h>
krh@80
     3
#include <stdarg.h>
krh@80
     4
#include <unistd.h>
krh@80
     5
#include <fcntl.h>
krh@80
     6
#include <errno.h>
krh@80
     7
#include <expat.h>
krh@80
     8
krh@80
     9
#include "razor.h"
krh@80
    10
krh@80
    11
#define XML_BUFFER_SIZE 4096
krh@80
    12
krh@80
    13
static void
krh@80
    14
parse_xml_file(const char *filename,
krh@80
    15
	       XML_StartElementHandler start,
krh@80
    16
	       XML_EndElementHandler end,
krh@80
    17
	       void *data)
krh@80
    18
{
krh@80
    19
	XML_Parser parser;
krh@80
    20
	char *buffer;
krh@80
    21
	int fd, len, err;
krh@80
    22
krh@80
    23
	parser = XML_ParserCreate(NULL);
krh@80
    24
	XML_SetElementHandler(parser, start, end);
krh@80
    25
	XML_SetUserData(parser, data);
krh@80
    26
krh@80
    27
	fd = open(filename, O_RDONLY);
krh@80
    28
	if (fd < 0) {
krh@92
    29
		fprintf(stderr, "failed to open %s: %m\n", filename);
krh@80
    30
		exit(-1);
krh@80
    31
	}
krh@80
    32
danw@137
    33
	while (1) {
danw@137
    34
		buffer = XML_GetBuffer(parser, XML_BUFFER_SIZE);
danw@137
    35
		len = read(fd, buffer, XML_BUFFER_SIZE);
danw@137
    36
		if (len == 0)
danw@137
    37
			break;
krh@80
    38
		err = XML_ParseBuffer(parser, len, len == 0);
krh@80
    39
		if (err == XML_STATUS_ERROR) {
krh@80
    40
			fprintf(stderr, "parse error at line %lu:\n%s\n",
krh@80
    41
				XML_GetCurrentLineNumber(parser),
krh@80
    42
				XML_ErrorString(XML_GetErrorCode(parser)));
krh@80
    43
			exit(-1);
krh@80
    44
		}
krh@80
    45
	}
krh@80
    46
krh@80
    47
	if (fd < 0) {
krh@80
    48
		fprintf(stderr, "read: %m\n");
krh@80
    49
		exit(-1);
krh@80
    50
	}
krh@80
    51
krh@80
    52
	close(fd);
krh@80
    53
}
krh@80
    54
danw@125
    55
struct test_context {
danw@125
    56
	struct razor_set *system_set, *repo_set, *result_set;
krh@80
    57
krh@80
    58
	struct razor_importer *importer;
danw@125
    59
	struct razor_set **importer_set;
danw@125
    60
danw@137
    61
	struct razor_transaction *trans;
danw@137
    62
danw@125
    63
	char *install_pkgs[3], *remove_pkgs[3];
danw@125
    64
	int n_install_pkgs, n_remove_pkgs;
danw@125
    65
krh@190
    66
	int unsat;
danw@154
    67
	int in_result;
danw@137
    68
danw@154
    69
	int debug, errors;
krh@80
    70
};
krh@80
    71
krh@80
    72
static void
krh@80
    73
get_atts(const char **atts, ...)
krh@80
    74
{
krh@80
    75
	va_list ap;
krh@80
    76
	const char *name, **ptr;
krh@80
    77
	int i;
krh@80
    78
krh@80
    79
	va_start(ap, atts);
krh@80
    80
	while (name = va_arg(ap, const char *), name != NULL) {
krh@80
    81
		ptr = va_arg(ap, const char **);
krh@92
    82
		*ptr = NULL;
krh@80
    83
		for (i = 0; atts[i]; i += 2) {
krh@80
    84
			if (strcmp(atts[i], name) == 0)
krh@80
    85
				*ptr = atts[i + 1];
krh@80
    86
		}
krh@80
    87
	}
krh@80
    88
	va_end(ap);
krh@80
    89
}
krh@80
    90
danw@125
    91
static enum razor_version_relation
danw@125
    92
parse_relation (const char *rel_str)
krh@80
    93
{
danw@125
    94
	if (!rel_str)
danw@125
    95
		return -1;
danw@137
    96
	if (rel_str[0] == 'L')
danw@137
    97
		return rel_str[1] == 'E' ? RAZOR_VERSION_LESS_OR_EQUAL : RAZOR_VERSION_LESS;
danw@137
    98
	else if (rel_str[0] == 'G')
danw@137
    99
		return rel_str[1] == 'E' ? RAZOR_VERSION_GREATER_OR_EQUAL : RAZOR_VERSION_GREATER;
danw@137
   100
	else if (rel_str[0] == 'E' || rel_str[1] == 'Q')
danw@125
   101
		return RAZOR_VERSION_EQUAL;
danw@125
   102
	else
danw@125
   103
		return -1;
krh@80
   104
}
krh@80
   105
krh@80
   106
static void
danw@125
   107
start_test(struct test_context *ctx, const char **atts)
krh@80
   108
{
danw@125
   109
	const char *name = NULL;
krh@80
   110
danw@125
   111
	get_atts(atts, "name", &name, NULL);
danw@125
   112
	if (!name) {
danw@125
   113
		fprintf(stderr, "Test with no name\n");
danw@125
   114
		exit(1);
danw@125
   115
	}
danw@125
   116
	printf("%s\n", name);
danw@125
   117
}
danw@125
   118
danw@125
   119
static void
danw@125
   120
end_test(struct test_context *ctx)
danw@125
   121
{
danw@125
   122
	if (ctx->system_set) {
danw@125
   123
		razor_set_destroy(ctx->system_set);
danw@125
   124
		ctx->system_set = NULL;
danw@125
   125
	}
danw@125
   126
	if (ctx->repo_set) {
danw@125
   127
		razor_set_destroy(ctx->repo_set);
danw@125
   128
		ctx->repo_set = NULL;
danw@125
   129
	}
danw@125
   130
	if (ctx->result_set) {
danw@125
   131
		razor_set_destroy(ctx->result_set);
danw@125
   132
		ctx->result_set = NULL;
krh@80
   133
	}
danw@137
   134
	if (ctx->trans) {
danw@137
   135
		razor_transaction_destroy(ctx->trans);
danw@137
   136
		ctx->trans = NULL;
danw@137
   137
	}
krh@80
   138
}
krh@80
   139
krh@80
   140
static void
danw@125
   141
start_set(struct test_context *ctx, const char **atts)
krh@80
   142
{
danw@125
   143
	const char *name = NULL;
krh@80
   144
danw@125
   145
	ctx->importer = razor_importer_new();
danw@125
   146
	get_atts(atts, "name", &name, NULL);
danw@125
   147
	if (!name)
danw@125
   148
		ctx->importer_set = &ctx->result_set;
danw@125
   149
	else if (!strcmp(name, "system"))
danw@125
   150
		ctx->importer_set = &ctx->system_set;
danw@125
   151
	else if (!strcmp(name, "repo"))
danw@125
   152
		ctx->importer_set = &ctx->repo_set;
danw@125
   153
	else {
danw@125
   154
		fprintf(stderr, "  bad set name '%s'\n", name);
danw@125
   155
		exit(1);
krh@92
   156
	}
krh@92
   157
}
krh@92
   158
krh@92
   159
static void
danw@125
   160
end_set(struct test_context *ctx)
krh@92
   161
{
danw@125
   162
	*ctx->importer_set = razor_importer_finish(ctx->importer);
danw@125
   163
	ctx->importer = NULL;
danw@125
   164
}
krh@92
   165
danw@125
   166
static void
danw@125
   167
start_package(struct test_context *ctx, const char **atts)
danw@125
   168
{
danw@125
   169
	const char *name = NULL, *version = NULL, *arch = NULL;
danw@125
   170
krh@192
   171
	get_atts(atts, "name", &name,
krh@192
   172
		 "version", &version,
krh@192
   173
		 "arch", &arch,
krh@192
   174
		 NULL);
krh@192
   175
danw@125
   176
	if (!name) {
danw@125
   177
		fprintf(stderr, "  package with no name\n");
danw@125
   178
		exit(1);
krh@92
   179
	}
krh@92
   180
krh@192
   181
	razor_importer_begin_package(ctx->importer, name, version, arch);
danw@125
   182
	razor_importer_add_property(ctx->importer, name,
danw@125
   183
				    RAZOR_VERSION_EQUAL, version,
danw@125
   184
				    RAZOR_PROPERTY_PROVIDES);
danw@125
   185
}
danw@125
   186
danw@125
   187
static void
danw@125
   188
end_package(struct test_context *ctx)
danw@125
   189
{
danw@125
   190
	razor_importer_finish_package(ctx->importer);
danw@125
   191
}
danw@125
   192
danw@125
   193
static void
danw@137
   194
add_property(struct test_context *ctx, enum razor_property_type type, const char *name, enum razor_version_relation rel, const char *version)
danw@137
   195
{
danw@137
   196
	razor_importer_add_property(ctx->importer, name,
danw@137
   197
				    rel, version, type);
danw@137
   198
}
danw@137
   199
danw@137
   200
static void
krh@190
   201
check_unsatisfiable_property(struct test_context *ctx,
krh@190
   202
			     enum razor_property_type type,
krh@190
   203
			     const char *name,
krh@190
   204
			     enum razor_version_relation rel,
krh@190
   205
			     const char *version)
danw@137
   206
{
krh@230
   207
	static const char *relation_string[] = { "<", "<=", "=", ">=", ">" };
krh@230
   208
danw@137
   209
	if (!version)
danw@137
   210
		version = "";
danw@137
   211
krh@190
   212
	if (razor_transaction_unsatisfied_property(ctx->trans,
krh@230
   213
						   name, rel, version, type))
danw@137
   214
		return;
danw@137
   215
danw@137
   216
	fprintf(stderr, "  didn't get unsatisfiable '%s %s %s'\n",
krh@230
   217
		name, relation_string[rel], version);
danw@154
   218
	ctx->errors++;
danw@137
   219
}
danw@137
   220
danw@137
   221
static void
danw@125
   222
start_property(struct test_context *ctx, enum razor_property_type type, const char **atts)
danw@125
   223
{
danw@125
   224
	const char *name = NULL, *rel_str = NULL, *version = NULL;
danw@125
   225
	enum razor_version_relation rel;
danw@125
   226
danw@137
   227
	get_atts(atts, "name", &name, "relation", &rel_str, "version", &version, NULL);
danw@125
   228
	if (name == NULL) {
danw@125
   229
		fprintf(stderr, "  no name specified for property\n");
danw@125
   230
		exit(1);
danw@125
   231
	}
danw@125
   232
	if (version) {
danw@125
   233
		rel = parse_relation(rel_str);
danw@125
   234
		if (rel == -1) {
danw@125
   235
			fprintf(stderr, "  bad or missing version relation for property %s\n", name);
danw@125
   236
			exit(1);
krh@92
   237
		}
danw@125
   238
	} else
danw@125
   239
		rel = RAZOR_VERSION_EQUAL;
danw@125
   240
	
danw@137
   241
	if (ctx->unsat)
danw@137
   242
		check_unsatisfiable_property(ctx, type, name, rel, version);
danw@137
   243
	else
danw@137
   244
		add_property(ctx, type, name, rel, version);
danw@125
   245
}
krh@92
   246
danw@125
   247
static void
danw@125
   248
start_transaction(struct test_context *ctx, const char **atts)
danw@125
   249
{
danw@125
   250
	ctx->n_install_pkgs = 0;
danw@125
   251
	ctx->n_remove_pkgs = 0;
danw@125
   252
}
danw@125
   253
danw@125
   254
static void
danw@125
   255
end_transaction(struct test_context *ctx)
danw@125
   256
{
krh@208
   257
	struct razor_package *pkg;
krh@208
   258
	int errors, i;
krh@190
   259
krh@208
   260
	ctx->trans = razor_transaction_create(ctx->system_set, ctx->repo_set);
krh@208
   261
	for (i = 0; i < ctx->n_install_pkgs; i++) {
krh@208
   262
		pkg = razor_set_get_package(ctx->repo_set,
krh@208
   263
					    ctx->install_pkgs[i]);
krh@208
   264
		razor_transaction_install_package(ctx->trans, pkg);
krh@208
   265
	}		
krh@208
   266
	for (i = 0; i < ctx->n_remove_pkgs; i++) {
krh@208
   267
		pkg = razor_set_get_package(ctx->repo_set,
krh@208
   268
					    ctx->remove_pkgs[i]);
krh@208
   269
		razor_transaction_remove_package(ctx->trans, pkg);
krh@208
   270
	}		
krh@208
   271
krh@210
   272
	errors = razor_transaction_resolve(ctx->trans);
krh@190
   273
	printf("\n");
danw@125
   274
danw@125
   275
	while (ctx->n_install_pkgs--)
danw@125
   276
		free(ctx->install_pkgs[ctx->n_install_pkgs]);
danw@125
   277
	while (ctx->n_remove_pkgs--)
danw@125
   278
		free(ctx->remove_pkgs[ctx->n_remove_pkgs]);
danw@137
   279
krh@190
   280
	if (!errors) {
danw@137
   281
		struct razor_set *new;
krh@196
   282
		new = razor_transaction_finish(ctx->trans);
danw@137
   283
		ctx->system_set = new;
danw@137
   284
	}
danw@125
   285
}
danw@125
   286
danw@125
   287
static void
danw@125
   288
start_install_or_update(struct test_context *ctx, const char **atts)
danw@125
   289
{
danw@125
   290
	const char *name = NULL;
danw@125
   291
danw@125
   292
	get_atts(atts, "name", &name, NULL);
danw@125
   293
	if (!name) {
danw@125
   294
		fprintf(stderr, "  install/update with no name\n");
danw@125
   295
		exit(1);
danw@125
   296
	}
danw@125
   297
danw@125
   298
	ctx->install_pkgs[ctx->n_install_pkgs++] = strdup(name);
danw@125
   299
}
danw@125
   300
danw@125
   301
static void
danw@125
   302
start_remove(struct test_context *ctx, const char **atts)
danw@125
   303
{
danw@125
   304
	const char *name = NULL;
danw@125
   305
danw@125
   306
	get_atts(atts, "name", &name, NULL);
danw@125
   307
	if (!name) {
danw@125
   308
		fprintf(stderr, "  remove with no name\n");
danw@125
   309
		exit(1);
danw@125
   310
	}
danw@125
   311
danw@125
   312
	ctx->remove_pkgs[ctx->n_remove_pkgs++] = strdup(name);
danw@125
   313
}
danw@125
   314
danw@125
   315
static void
danw@125
   316
start_result(struct test_context *ctx, const char **atts)
danw@125
   317
{
danw@125
   318
	ctx->in_result = 1;
danw@125
   319
}
danw@125
   320
danw@125
   321
static void
danw@125
   322
diff_callback(const char *name,
krh@192
   323
	      const char *old_version,
krh@192
   324
	      const char *new_version,
krh@192
   325
	      const char *arch,
danw@125
   326
	      void *data)
danw@125
   327
{
danw@125
   328
	struct test_context *ctx = data;
danw@125
   329
danw@154
   330
	ctx->errors++;
danw@125
   331
	if (old_version) {
danw@125
   332
		fprintf(stderr, "  result set should not contain %s %s\n",
danw@125
   333
			name, old_version);
danw@125
   334
	} else {
danw@125
   335
		fprintf(stderr, "  result set should contain %s %s\n",
danw@125
   336
			name, new_version);
krh@92
   337
	}
krh@92
   338
}
krh@92
   339
krh@92
   340
static void
danw@125
   341
end_result(struct test_context *ctx)
krh@92
   342
{
danw@125
   343
	ctx->in_result = 0;
krh@92
   344
danw@131
   345
	if (ctx->result_set) {
danw@131
   346
		if (!ctx->system_set)
danw@131
   347
			ctx->system_set = razor_set_create();
danw@125
   348
		razor_set_diff(ctx->system_set, ctx->result_set,
danw@125
   349
			       diff_callback, ctx);
krh@92
   350
	}
krh@92
   351
}
krh@92
   352
krh@92
   353
static void
danw@131
   354
start_unsatisfiable(struct test_context *ctx, const char **atts)
krh@92
   355
{
danw@137
   356
	if (ctx->result_set) {
danw@131
   357
		fprintf(stderr, "Expected to fail, but didn't\n");
danw@131
   358
		exit(1);
danw@131
   359
	}
danw@131
   360
krh@190
   361
	ctx->unsat = 1;
danw@125
   362
}
krh@92
   363
danw@125
   364
static void
danw@131
   365
end_unsatisfiable(struct test_context *ctx)
danw@125
   366
{
krh@190
   367
	ctx->unsat = 0;
krh@92
   368
}
krh@92
   369
krh@92
   370
static void
krh@92
   371
start_test_element(void *data, const char *element, const char **atts)
krh@92
   372
{
krh@92
   373
	struct test_context *ctx = data;
krh@92
   374
danw@125
   375
	if (strcmp(element, "tests") == 0) {
danw@125
   376
		;
danw@125
   377
	} else if (strcmp(element, "test") == 0) {
danw@125
   378
		start_test(ctx, atts);
danw@125
   379
	} else if (strcmp(element, "set") == 0) {
danw@125
   380
		start_set(ctx, atts);
danw@125
   381
	} else if (strcmp(element, "transaction") == 0) {
danw@125
   382
		start_transaction(ctx, atts);
danw@125
   383
	} else if (strcmp(element, "install") == 0) {
danw@125
   384
		start_install_or_update(ctx, atts);
danw@125
   385
	} else if (strcmp(element, "install") == 0) {
danw@125
   386
		start_install_or_update(ctx, atts);
danw@125
   387
	} else if (strcmp(element, "remove") == 0) {
danw@125
   388
		start_remove(ctx, atts);
danw@125
   389
	} else if (strcmp(element, "result") == 0) {
danw@125
   390
		start_result(ctx, atts);
danw@131
   391
	} else if (strcmp(element, "unsatisfiable") == 0) {
danw@131
   392
		start_unsatisfiable(ctx, atts);
krh@92
   393
	} else if (strcmp(element, "package") == 0) {
danw@125
   394
		start_package(ctx, atts);
krh@92
   395
	} else if (strcmp(element, "requires") == 0) {
danw@125
   396
		start_property(ctx, RAZOR_PROPERTY_REQUIRES, atts);
krh@92
   397
	} else if (strcmp(element, "provides") == 0) {
danw@125
   398
		start_property(ctx, RAZOR_PROPERTY_PROVIDES, atts);
krh@92
   399
	} else if (strcmp(element, "conflicts") == 0) {
danw@125
   400
		start_property(ctx, RAZOR_PROPERTY_CONFLICTS, atts);
krh@92
   401
	} else if (strcmp(element, "obsoletes") == 0) {
danw@125
   402
		start_property(ctx, RAZOR_PROPERTY_OBSOLETES, atts);
danw@125
   403
	} else {
danw@125
   404
		fprintf(stderr, "Unrecognized element '%s'\n", element);
danw@125
   405
		exit(1);
krh@92
   406
	}
krh@92
   407
}
krh@92
   408
krh@92
   409
static void
krh@92
   410
end_test_element (void *data, const char *element)
krh@92
   411
{
krh@92
   412
	struct test_context *ctx = data;
krh@92
   413
danw@125
   414
	if (strcmp(element, "test") == 0) {
danw@125
   415
		end_test(ctx);
danw@125
   416
	} else if (strcmp(element, "set") == 0) {
danw@125
   417
		end_set(ctx);
danw@125
   418
	} else if (strcmp(element, "package") == 0) {
danw@125
   419
		end_package(ctx);
danw@125
   420
	} else if (strcmp(element, "transaction") == 0) {
danw@125
   421
		end_transaction(ctx);
danw@125
   422
	} else if (strcmp(element, "result") == 0) {
danw@125
   423
		end_result(ctx);
danw@131
   424
	} else if (strcmp(element, "unsatisfiable") == 0) {
danw@131
   425
		end_unsatisfiable(ctx);
danw@125
   426
	}
krh@92
   427
}
krh@92
   428
krh@80
   429
int main(int argc, char *argv[])
krh@80
   430
{
krh@80
   431
	struct test_context ctx;
danw@137
   432
	const char *test_file;
krh@80
   433
danw@137
   434
	memset(&ctx, 0, sizeof ctx);
danw@137
   435
danw@137
   436
	if (argc > 3) {
danw@137
   437
		fprintf(stderr, "usage: %s [-d] [TESTS-FILE]\n", argv[0]);
krh@80
   438
		exit(-1);			
krh@80
   439
	}
krh@80
   440
danw@137
   441
	if (argc >= 2 && !strcmp (argv[1], "-d")) {
danw@137
   442
		ctx.debug = 1;
danw@137
   443
		argc--;
danw@137
   444
		argv++;
danw@137
   445
	}
danw@137
   446
	if (argc == 2)
danw@137
   447
		test_file = argv[1];
danw@137
   448
	else
danw@137
   449
		test_file = "test.xml";
danw@137
   450
danw@137
   451
	parse_xml_file(test_file, start_test_element, end_test_element, &ctx);
krh@80
   452
danw@154
   453
	if (ctx.errors) {
danw@154
   454
		fprintf(stderr, "\n%d errors\n", ctx.errors);
danw@154
   455
		return 1;
danw@154
   456
	} else
danw@154
   457
		return 0;
krh@80
   458
}