solver_util: init

12 files changed, 115 insertions, 23 deletions

diff --git a/flake.nix b/flake.nix
index ab78426..2659b41 100644
--- a/flake.nix
+++ b/flake.nix
@@ -27,6 +27,7 @@
 
             buildInputs = with pkgs; [
               jq
+              highs
               cjson
               nix-eval-jobs
 
@@ -63,7 +64,7 @@
             ];
             buildInputs = with pkgs; [
               cjson
-              nix-eval-jobs
+              highs
             ];
 
             postInstall = ''
diff --git a/include/jobs.h b/include/jobs.h
index 7390306..54152cf 100644
--- a/include/jobs.h
+++ b/include/jobs.h
@@ -9,20 +9,23 @@ struct output {
 };
 
 struct job {
-	char *name, *drv_path, *attr;
+	char *name, *drv_path, *nix_attr_name;
 	bool scheduled;
 	bool insubstituters;
-
 	size_t outputs_size, outputs_filled;
 	struct output **outputs;
 
+	/* DAG */
 	size_t deps_size, deps_filled;
 	struct job **deps;
-
 	size_t parents_size, parents_filled;
 	struct job **parents;
 
+	/* queue */
 	CIRCLEQ_ENTRY(job) clist;
+
+	/* solver */
+	ssize_t id;
 };
 CIRCLEQ_HEAD(job_clist, job);
 
@@ -37,7 +40,7 @@ typedef enum {
 int job_read(FILE *stream, struct job **jobs);
 
 /* Spawns nix-eval-jobs and connects its stdout to stream */
-int jobs_init(FILE **stream, const char *expr);
+int jobs_init(FILE **stream, char *expr);
 void job_free(struct job *j);
 int job_parents_list_insert(struct job *job, struct job *parent);
 void job_deps_list_rm(struct job *job, struct job *dep);
diff --git a/include/queue.h b/include/queue.h
index 4aca54b..fee5bb3 100644
--- a/include/queue.h
+++ b/include/queue.h
@@ -5,6 +5,7 @@
 
 #include "htab.h"
 #include "jobs.h"
+#include "solver_util.h"
 
 #ifndef QUEUE_H
 
@@ -16,6 +17,7 @@ typedef enum {
 struct queue {
 	struct job_clist jobs;
 	struct htab *htab;
+	struct job_ids *job_ids;
 	sem_t sem;
 	queue_state_t state;
 	pthread_mutex_t mutex;
diff --git a/include/solver_util.h b/include/solver_util.h
new file mode 100644
index 0000000..99d5fcd
--- /dev/null
+++ b/include/solver_util.h
@@ -0,0 +1,11 @@
+#include "jobs.h"
+
+#ifndef SOLVER_UTIL_H
+
+struct job_ids {
+	struct job **jobs;
+	ssize_t filled, size;
+};
+
+#define SOLVER_UTIL_H
+#endif
diff --git a/meson.build b/meson.build
index e5290f8..2bad179 100644
--- a/meson.build
+++ b/meson.build
@@ -19,6 +19,7 @@ add_project_arguments(
 )
 
 cjson_dep = dependency('libcjson')
+highs_dep = dependency('highs')
 evanix_inc = include_directories('include')
 
 if get_option('build-python')
diff --git a/python-package.nix b/python-package.nix
index a422052..648899e 100644
--- a/python-package.nix
+++ b/python-package.nix
@@ -6,6 +6,7 @@
   pkg-config,
   makeWrapper,
   cjson,
+  highs,
 }:
 
 buildPythonPackage {
@@ -36,6 +37,6 @@ buildPythonPackage {
   ];
   buildInputs = [
     cjson
-    # nix-eval-jobs
+    highs
   ];
 }
diff --git a/src/build.c b/src/build.c
index 87238e9..30a821a 100644
--- a/src/build.c
+++ b/src/build.c
@@ -1,8 +1,8 @@
 #include <errno.h>
+#include <limits.h>
 #include <pthread.h>
 #include <stdbool.h>
 #include <stdlib.h>
-#include <limits.h>
 #include <string.h>
 
 #include "build.h"
@@ -54,8 +54,9 @@ static int build(struct queue *queue)
 	if (ret < 0)
 		return ret;
 
-	if (job->attr) {
-		ret = snprintf(out_link, sizeof(out_link), "result-%s", job->attr);
+	if (job->nix_attr_name) {
+		ret = snprintf(out_link, sizeof(out_link), "result-%s",
+			       job->nix_attr_name);
 		if (ret < 0 || (size_t)ret > sizeof(out_link)) {
 			ret = -ENAMETOOLONG;
 			print_err("%s", strerror(-ret));
diff --git a/src/evanix-py.c b/src/evanix-py.c
index c010e27..1ee2ec0 100644
--- a/src/evanix-py.c
+++ b/src/evanix-py.c
@@ -8,7 +8,4 @@ static struct PyModuleDef module = {
 	PyModuleDef_HEAD_INIT, "evanix", NULL, -1, methods,
 };
 
-PyMODINIT_FUNC PyInit_evanix(void)
-{
-	return PyModule_Create(&module);
-}
+PyMODINIT_FUNC PyInit_evanix(void) { return PyModule_Create(&module); }
diff --git a/src/jobs.c b/src/jobs.c
index 7851fef..04afa4a 100644
--- a/src/jobs.c
+++ b/src/jobs.c
@@ -1,8 +1,8 @@
 #include <errno.h>
-#include <unistd.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <unistd.h>
 
 #include <cjson/cJSON.h>
 
@@ -352,12 +352,12 @@ void job_free(struct job *job)
 
 	free(job->drv_path);
 	free(job->name);
-	free(job->attr);
+	free(job->nix_attr_name);
 	free(job);
 }
 
-static int job_new(struct job **j, char *name, char *drv_path,
-		   char *attr, struct job *parent)
+static int job_new(struct job **j, char *name, char *drv_path, char *attr,
+		   struct job *parent)
 {
 	struct job *job;
 	int ret = 0;
@@ -368,6 +368,7 @@ static int job_new(struct job **j, char *name, char *drv_path,
 		return -errno;
 	}
 	job->scheduled = false;
+	job->id = -1;
 
 	job->outputs_size = 0;
 	job->outputs_filled = 0;
@@ -382,14 +383,14 @@ static int job_new(struct job **j, char *name, char *drv_path,
 	job->parents = NULL;
 
 	if (attr != NULL) {
-		job->attr = strdup(attr);
-		if (job->attr == NULL) {
+		job->nix_attr_name = strdup(attr);
+		if (job->nix_attr_name == NULL) {
 			print_err("%s", strerror(errno));
 			ret = -errno;
 			goto out_free_job;
 		}
 	} else {
-		job->attr = NULL;
+		job->nix_attr_name = NULL;
 	}
 
 	if (name != NULL) {
@@ -424,7 +425,7 @@ out_free_name:
 		free(job->name);
 out_free_attr:
 	if (ret < 0)
-		free(job->attr);
+		free(job->nix_attr_name);
 out_free_job:
 	if (ret < 0)
 		free(job);
@@ -434,7 +435,7 @@ out_free_job:
 	return ret;
 }
 
-int jobs_init(FILE **stream, const char *expr)
+int jobs_init(FILE **stream, char *expr)
 {
 	size_t argindex;
 	char *args[6];
diff --git a/src/meson.build b/src/meson.build
index ea955bc..7a42999 100644
--- a/src/meson.build
+++ b/src/meson.build
@@ -7,10 +7,11 @@ e = executable(
 		'queue.c',
 		'build.c',
 		'htab.c',
+		'solver_util.c',
 	],
 
 	include_directories: evanix_inc,
-	dependencies: cjson_dep,
+	dependencies: [ cjson_dep, highs_dep ],
 	install: true,
 )
 
diff --git a/src/queue.c b/src/queue.c
index 3a7ca52..75a3e14 100644
--- a/src/queue.c
+++ b/src/queue.c
@@ -221,6 +221,7 @@ int queue_thread_new(struct queue_thread **queue_thread, FILE *stream)
 		ret = -errno;
 		goto out_free_qt;
 	}
+	qt->queue->job_ids = NULL;
 	qt->queue->state = Q_SEM_WAIT;
 	ret = sem_init(&qt->queue->sem, 0, 0);
 	if (ret < 0) {
diff --git a/src/solver_util.c b/src/solver_util.c
new file mode 100644
index 0000000..9efb65a
--- /dev/null
+++ b/src/solver_util.c
@@ -0,0 +1,72 @@
+#include <errno.h>
+#include <queue.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "jobs.h"
+#include "solver_util.h"
+#include "util.h"
+
+static int dag_id_assign(struct job *j, struct job_ids *job_ids)
+{
+	size_t newsize;
+	void *ret;
+
+	if (j->id >= 0)
+		return 0;
+
+	for (size_t i = 0; i < j->deps_filled; i++)
+		return dag_id_assign(j->deps[i], job_ids);
+
+	if (job_ids->size < job_ids->filled) {
+		j->id = job_ids->filled++;
+		job_ids->jobs[j->id] = j;
+		return 0;
+	}
+
+	newsize = job_ids->size == 0 ? 2 : job_ids->size * 2;
+	ret = realloc(job_ids->jobs, newsize * sizeof(*job_ids->jobs));
+	if (ret == NULL) {
+		print_err("%s", strerror(errno));
+		return -errno;
+	}
+	job_ids->jobs = ret;
+
+	j->id = job_ids->filled++;
+	job_ids->jobs[j->id] = j;
+
+	return 0;
+}
+
+int queue_id_assign(struct job_clist *q, struct job_ids **job_ids)
+{
+	struct job_ids *ji;
+	struct job *j;
+	int ret;
+
+	ji = malloc(sizeof(*ji));
+	if (ji == NULL) {
+		print_err("%s", strerror(errno));
+		return -errno;
+	}
+	ji->jobs = NULL;
+	ji->size = 0;
+	ji->filled = 0;
+
+	CIRCLEQ_FOREACH (j, q, clist) {
+		ret = dag_id_assign(j, ji);
+		if (ret < 0) {
+			goto out_free_js;
+		}
+	}
+
+out_free_js:
+	if (ret < 0) {
+		free(ji->jobs);
+		free(ji);
+	} else {
+		*job_ids = ji;
+	}
+
+	return ret;
+}