fusesoc icon indicating copy to clipboard operation
fusesoc copied to clipboard

Iterative dependency resolution

Open imphil opened this issue 5 years ago • 0 comments

FuseSoC currently does one (and after #391 two) dependency resolution runs, and expects to be able to fully resolve all dependencies in that run.

With generators adding dynamicity to the picture, we should be looking into an iterative dependency resolution as long as new information becomes available.

What I'm looking for is an algorithm like this:

core_db = collect_core_files()
dep_tree = solve_dependency_tree(core_db, entrypoint)

while (True):
	# Perform all operations which might produce new cores
	changed = False
	generators = get_generator_list(dep_tree)
	for g in generators: 
		new_cores = run_generator_and_get_new_cores(g)
		if new_cores:
			core_db += new_cores
			changed = True	

	# In the future: Expand to look at certain remote locations for new cores
	
	# Resolve dependency tree again to take new information into account.
	dep_tree_before = dep_tree
	dep_tree = solve_dependency_tree(core_db, entrypoint)
	if dep_tree_before == dep_tree:
		break

if not is_completely_resolved(dep_tree):
	exit("Unable to resolve all dependencies.")

This algorithm isn't guaranteed to stabilize, so we need to add additional exit conditions, e.g. abort after n tries. Equally, there is room for some optimization (e.g. avoid the second resolution if generators didn't produce new cores).

Use cases for this new approach:

  • Cores can depend on cores which are produced by a generator, but don't exist anywhere else. This is actually something we're likely to need in OpenTitan, and effectively solves #235 through generators (more on that once I've finished thinking about it).
  • We can expand the search scope step-by-step. For example: First, only search local cores, then also search cores in a certain remote location (librecores!). This will keep dependency resolution fast for local use cases.

imphil avatar Nov 26 '20 16:11 imphil