fusesoc
fusesoc copied to clipboard
Iterative dependency resolution
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.