Benjamin Schubert pushed to branch bschubert/optimize-sort at BuildStream / buildstream
Commits:
-
897ae570
by Benjamin Schubert at 2019-01-30T17:38:27Z
4 changed files:
- buildstream/_loader/loadelement.py
- buildstream/_loader/loader.py
- buildstream/_loader/types.py
- buildstream/_profile.py
Changes:
| ... | ... | @@ -81,42 +81,6 @@ class LoadElement(): |
| 81 | 81 |
# Extract the Dependencies
|
| 82 | 82 |
self.deps = _extract_depends_from_node(self.node, loader=self._loader)
|
| 83 | 83 |
|
| 84 |
- # depends():
|
|
| 85 |
- #
|
|
| 86 |
- # Checks if this element depends on another element, directly
|
|
| 87 |
- # or indirectly.
|
|
| 88 |
- #
|
|
| 89 |
- # Args:
|
|
| 90 |
- # other (LoadElement): Another LoadElement
|
|
| 91 |
- #
|
|
| 92 |
- # Returns:
|
|
| 93 |
- # (bool): True if this LoadElement depends on 'other'
|
|
| 94 |
- #
|
|
| 95 |
- def depends(self, other):
|
|
| 96 |
- self._ensure_depends_cache()
|
|
| 97 |
- return self._dep_cache.get(other.full_name) is not None
|
|
| 98 |
- |
|
| 99 |
- ###########################################
|
|
| 100 |
- # Private Methods #
|
|
| 101 |
- ###########################################
|
|
| 102 |
- def _ensure_depends_cache(self):
|
|
| 103 |
- |
|
| 104 |
- if self._dep_cache:
|
|
| 105 |
- return
|
|
| 106 |
- |
|
| 107 |
- self._dep_cache = {}
|
|
| 108 |
- for dep in self.deps:
|
|
| 109 |
- elt = self._loader.get_element_for_dep(dep)
|
|
| 110 |
- |
|
| 111 |
- # Ensure the cache of the element we depend on
|
|
| 112 |
- elt._ensure_depends_cache()
|
|
| 113 |
- |
|
| 114 |
- # We depend on this element
|
|
| 115 |
- self._dep_cache[elt.full_name] = True
|
|
| 116 |
- |
|
| 117 |
- # And we depend on everything this element depends on
|
|
| 118 |
- self._dep_cache.update(elt._dep_cache)
|
|
| 119 |
- |
|
| 120 | 84 |
|
| 121 | 85 |
# _extract_depends_from_node():
|
| 122 | 86 |
#
|
| ... | ... | @@ -149,12 +149,9 @@ class Loader(): |
| 149 | 149 |
# Sort direct dependencies of elements by their dependency ordering
|
| 150 | 150 |
#
|
| 151 | 151 |
for target in targets:
|
| 152 |
- profile_start(Topics.SORT_DEPENDENCIES, target)
|
|
| 153 |
- junction, name, loader = self._parse_name(target, rewritable, ticker,
|
|
| 154 |
- fetch_subprojects=fetch_subprojects)
|
|
| 155 |
- #loader._sort_dependencies(name)
|
|
| 156 |
- profile_end(Topics.SORT_DEPENDENCIES, target)
|
|
| 157 |
- # Finally, wrap what we have into LoadElements and return the target
|
|
| 152 |
+ _junction, name, loader = self._parse_name(target, rewritable, ticker,
|
|
| 153 |
+ fetch_subprojects=fetch_subprojects)
|
|
| 154 |
+ # Wrap what we have into LoadElements and return the target
|
|
| 158 | 155 |
#
|
| 159 | 156 |
ret.append(loader._collect_element(name))
|
| 160 | 157 |
|
| ... | ... | @@ -297,9 +294,6 @@ class Loader(): |
| 297 | 294 |
raise SystemExit("Can't order stuff")
|
| 298 | 295 |
|
| 299 | 296 |
# Load all dependency files for the new LoadElement
|
| 300 |
- ### FIXME: HERE WE CODE
|
|
| 301 |
- ###
|
|
| 302 |
- ###
|
|
| 303 | 297 |
for dep in sorted(element.deps, key=cmp_to_key(sort_deps)):
|
| 304 | 298 |
if dep.junction:
|
| 305 | 299 |
self._load_file(dep.junction, rewritable, ticker, fetch_subprojects, yaml_cache)
|
| ... | ... | @@ -380,82 +374,6 @@ class Loader(): |
| 380 | 374 |
# Eliminate duplicate paths
|
| 381 | 375 |
validated[element_name] = True
|
| 382 | 376 |
|
| 383 |
- # _sort_dependencies():
|
|
| 384 |
- #
|
|
| 385 |
- # Sort dependencies of each element by their dependencies,
|
|
| 386 |
- # so that direct dependencies which depend on other direct
|
|
| 387 |
- # dependencies (directly or indirectly) appear later in the
|
|
| 388 |
- # list.
|
|
| 389 |
- #
|
|
| 390 |
- # This avoids the need for performing multiple topological
|
|
| 391 |
- # sorts throughout the build process.
|
|
| 392 |
- #
|
|
| 393 |
- # Args:
|
|
| 394 |
- # element_name (str): The element-path relative element name to sort
|
|
| 395 |
- #
|
|
| 396 |
- def _sort_dependencies(self, element_name, visited=None):
|
|
| 397 |
- if visited is None:
|
|
| 398 |
- visited = {}
|
|
| 399 |
- |
|
| 400 |
- element = self._elements[element_name]
|
|
| 401 |
- |
|
| 402 |
- # element name must be unique across projects
|
|
| 403 |
- # to be usable as key for the visited dict
|
|
| 404 |
- element_name = element.full_name
|
|
| 405 |
- |
|
| 406 |
- if visited.get(element_name) is not None:
|
|
| 407 |
- return
|
|
| 408 |
- |
|
| 409 |
- for dep in element.deps:
|
|
| 410 |
- loader = self._get_loader_for_dep(dep)
|
|
| 411 |
- loader._sort_dependencies(dep.name, visited=visited)
|
|
| 412 |
- |
|
| 413 |
- def dependency_cmp(dep_a, dep_b):
|
|
| 414 |
- element_a = self.get_element_for_dep(dep_a)
|
|
| 415 |
- element_b = self.get_element_for_dep(dep_b)
|
|
| 416 |
- |
|
| 417 |
- # Sort on inter element dependency first
|
|
| 418 |
- if element_a.depends(element_b):
|
|
| 419 |
- return 1
|
|
| 420 |
- elif element_b.depends(element_a):
|
|
| 421 |
- return -1
|
|
| 422 |
- |
|
| 423 |
- # If there are no inter element dependencies, place
|
|
| 424 |
- # runtime only dependencies last
|
|
| 425 |
- if dep_a.dep_type != dep_b.dep_type:
|
|
| 426 |
- if dep_a.dep_type == Symbol.RUNTIME:
|
|
| 427 |
- return 1
|
|
| 428 |
- elif dep_b.dep_type == Symbol.RUNTIME:
|
|
| 429 |
- return -1
|
|
| 430 |
- |
|
| 431 |
- # All things being equal, string comparison.
|
|
| 432 |
- if dep_a.name > dep_b.name:
|
|
| 433 |
- return 1
|
|
| 434 |
- elif dep_a.name < dep_b.name:
|
|
| 435 |
- return -1
|
|
| 436 |
- |
|
| 437 |
- # Sort local elements before junction elements
|
|
| 438 |
- # and use string comparison between junction elements
|
|
| 439 |
- if dep_a.junction and dep_b.junction:
|
|
| 440 |
- if dep_a.junction > dep_b.junction:
|
|
| 441 |
- return 1
|
|
| 442 |
- elif dep_a.junction < dep_b.junction:
|
|
| 443 |
- return -1
|
|
| 444 |
- elif dep_a.junction:
|
|
| 445 |
- return -1
|
|
| 446 |
- elif dep_b.junction:
|
|
| 447 |
- return 1
|
|
| 448 |
- |
|
| 449 |
- # This wont ever happen
|
|
| 450 |
- return 0
|
|
| 451 |
- |
|
| 452 |
- # Now dependency sort, we ensure that if any direct dependency
|
|
| 453 |
- # directly or indirectly depends on another direct dependency,
|
|
| 454 |
- # it is found later in the list.
|
|
| 455 |
- element.deps.sort(key=cmp_to_key(dependency_cmp))
|
|
| 456 |
- |
|
| 457 |
- visited[element_name] = True
|
|
| 458 |
- |
|
| 459 | 377 |
# _collect_element()
|
| 460 | 378 |
#
|
| 461 | 379 |
# Collect the toplevel elements we have
|
| ... | ... | @@ -63,7 +63,11 @@ class Dependency(): |
| 63 | 63 |
self.dep_type = dep_type
|
| 64 | 64 |
self.junction = junction
|
| 65 | 65 |
self.provenance = provenance
|
| 66 |
+ self._index = None
|
|
| 66 | 67 |
|
| 67 | 68 |
@property
|
| 68 | 69 |
def index(self):
|
| 69 |
- return self.loader.get_element_for_dep(self).index
|
|
| 70 |
+ """Get the index of the load element to which this dependency refers."""
|
|
| 71 |
+ if self._index is None:
|
|
| 72 |
+ self._index = self.loader.get_element_for_dep(self).index
|
|
| 73 |
+ return self._index
|
| ... | ... | @@ -43,7 +43,6 @@ initialized = False |
| 43 | 43 |
# The special 'all' value will enable all profiles.
|
| 44 | 44 |
class Topics():
|
| 45 | 45 |
CIRCULAR_CHECK = 'circ-dep-check'
|
| 46 |
- SORT_DEPENDENCIES = 'sort-deps'
|
|
| 47 | 46 |
LOAD_LOADER = 'load-loader'
|
| 48 | 47 |
LOAD_CONTEXT = 'load-context'
|
| 49 | 48 |
LOAD_PROJECT = 'load-project'
|