[Notes] [Git][BuildStream/buildstream][bschubert/rework-sort] fixup! fixup! Add reverse dependencies in the LoadElement

[Benjamin Schubert <gitlab mg gitlab com>]

Title: GitLab

Benjamin Schubert pushed to branch bschubert/rework-sort at BuildStream / buildstream

Commits:

• 6d1a4608
  by Benjamin Schubert at 2019-02-04T09:48:13Z

  fixup! fixup! Add reverse dependencies in the LoadElement
  

4 changed files:

• buildstream/_cachekey.py
• buildstream/_loader/loadelement.py
• buildstream/_loader/loader.py
• buildstream/_loader/metaelement.py

Changes:

buildstream/_cachekey.py

---

...	...	@@ -18,8 +18,10 @@
18	18	# Tristan Van Berkom <tristan vanberkom codethink co uk>
19	19
20	20
	21	+import json
21	22	import hashlib
22	23	import pickle
	24	+import pprint
23	25
24	26	from . import _yaml
25	27
...	...	@@ -39,4 +41,12 @@ from . import _yaml
39	41	def generate_key(value):
40	42	ordered = _yaml.node_sanitize(value)
41	43	string = pickle.dumps(ordered)
	44	+
	45	+ with open("data.ordered", "a") as fp:
	46	+ ordered = json.loads(json.dumps(ordered))
	47	+ ordered.pop("environment", None)
	48	+ ordered.pop("public", None)
	49	+ # ordered.pop("public")
	50	+ fp.write(pprint.pformat(ordered, indent=1) + "\n\n")
	51	+
42	52	return hashlib.sha256(string).hexdigest()

buildstream/_loader/loadelement.py

---

...	...	@@ -64,7 +64,9 @@ class LoadElement():
64	64	self.name = filename # The element name
65	65	self.full_name = None # The element full name (with associated junction)
66	66	self.visited = False
67		-
	67	+ self.tried_visit = False
	68	+ self.in_pipeline = False
	69	+ self.__on_visit = []
68	70	#
69	71	# Private members
70	72	#
...	...	@@ -96,6 +98,13 @@ class LoadElement():
96	98	def junction(self):
97	99	return self._loader.project.junction
98	100
	101	+ def on_visit(self, func):
	102	+ self.__on_visit.append(func)
	103	+
	104	+ def visit(self, meta_element):
	105	+ for func in self.__on_visit:
	106	+ func(meta_element)
	107	+
99	108	# reverse_dependencies()
100	109	#
101	110	# Iterable over the Element's reverse dependencies
...	...	@@ -116,41 +125,41 @@ class LoadElement():
116	125	# unbreakable circles of dependencies
117	126	self.__reverse_dependencies.append(weakref.proxy(element))
118	127
119		- # depends():
120		- #
121		- # Checks if this element depends on another element, directly
122		- # or indirectly.
123		- #
124		- # Args:
125		- # other (LoadElement): Another LoadElement
126		- #
127		- # Returns:
128		- # (bool): True if this LoadElement depends on 'other'
129		- #
130		- def depends(self, other):
131		- self._ensure_depends_cache()
132		- return self._dep_cache.get(other.full_name) is not None
133		-
134		- ###########################################
135		- # Private Methods #
136		- ###########################################
137		- def _ensure_depends_cache(self):
138		-
139		- if self._dep_cache:
140		- return
141		-
142		- self._dep_cache = {}
143		- for dep in self.dependencies:
144		- elt = dep.element
145		-
146		- # Ensure the cache of the element we depend on
147		- elt._ensure_depends_cache()
148		-
149		- # We depend on this element
150		- self._dep_cache[elt.full_name] = True
151		-
152		- # And we depend on everything this element depends on
153		- self._dep_cache.update(elt._dep_cache)
	128	+ # # depends():
	129	+ # #
	130	+ # # Checks if this element depends on another element, directly
	131	+ # # or indirectly.
	132	+ # #
	133	+ # # Args:
	134	+ # # other (LoadElement): Another LoadElement
	135	+ # #
	136	+ # # Returns:
	137	+ # # (bool): True if this LoadElement depends on 'other'
	138	+ # #
	139	+ # def depends(self, other):
	140	+ # self._ensure_depends_cache()
	141	+ # return self._dep_cache.get(other.full_name) is not None
	142	+
	143	+ # ###########################################
	144	+ # # Private Methods #
	145	+ # ###########################################
	146	+ # def _ensure_depends_cache(self):
	147	+
	148	+ # if self._dep_cache:
	149	+ # return
	150	+
	151	+ # self._dep_cache = {}
	152	+ # for dep in self.dependencies:
	153	+ # elt = dep.element
	154	+
	155	+ # # Ensure the cache of the element we depend on
	156	+ # elt._ensure_depends_cache()
	157	+
	158	+ # # We depend on this element
	159	+ # self._dep_cache[elt.full_name] = True
	160	+
	161	+ # # And we depend on everything this element depends on
	162	+ # self._dep_cache.update(elt._dep_cache)
154	163
155	164
156	165	# _extract_depends_from_node():

buildstream/_loader/loader.py

---

...	...	@@ -19,8 +19,8 @@
19	19
20	20	import os
21	21	from functools import cmp_to_key
22		-from collections import defaultdict, deque
23		-from collections.abc import Mapping
	22	+from collections import defaultdict, deque, Mapping
	23	+from operator import attrgetter
24	24	import tempfile
25	25	import shutil
26	26
...	...	@@ -153,15 +153,17 @@ class Loader():
153	153	ret = loader._collect_elements(target_elements)
154	154	profile_end(Topics.COLLECT_ELEMENTS, key)
155	155
156		- print("#" * 60)
157		- for e in ret:
158		- print(e.name)
159		- print("dependencies:")
160		- for d in e.dependencies:
161		- print("\t", d.name)
162		- print("build deps:")
163		- for d in e.build_dependencies:
164		- print("\t", d.name)
	156	+ # print("#" * 60)
	157	+ # for element in self._meta_elements.values():
	158	+ # print(element.name)
	159	+ # for bdep in element.build_dependencies:
	160	+ # print("\t", bdep.name)
	161	+ # for dep in element.dependencies:
	162	+ # print("\t", dep.name)
	163	+ # print("RET")
	164	+ # print([e.name for e in ret])
	165	+ # print("#" * 60)
	166	+
165	167
166	168	return ret
167	169
...	...	@@ -333,75 +335,6 @@ class Loader():
333	335	# Eliminate duplicate paths
334	336	validated[element] = True
335	337
336		- # _sort_dependencies():
337		- #
338		- # Sort dependencies of each element by their dependencies,
339		- # so that direct dependencies which depend on other direct
340		- # dependencies (directly or indirectly) appear later in the
341		- # list.
342		- #
343		- # This avoids the need for performing multiple topological
344		- # sorts throughout the build process.
345		- #
346		- # Args:
347		- # element (LoadElement): The element to sort
348		- #
349		- def _sort_dependencies(self, element, visited=None):
350		- if visited is None:
351		- visited = set()
352		-
353		- if element in visited:
354		- return
355		-
356		- for dep in element.dependencies:
357		- dep.element._loader._sort_dependencies(dep.element, visited=visited)
358		-
359		- def dependency_cmp(dep_a, dep_b):
360		- element_a = dep_a.element
361		- element_b = dep_b.element
362		-
363		- # Sort on inter element dependency first
364		- if element_a.depends(element_b):
365		- return 1
366		- elif element_b.depends(element_a):
367		- return -1
368		-
369		- # If there are no inter element dependencies, place
370		- # runtime only dependencies last
371		- if dep_a.dep_type != dep_b.dep_type:
372		- if dep_a.dep_type == Symbol.RUNTIME:
373		- return 1
374		- elif dep_b.dep_type == Symbol.RUNTIME:
375		- return -1
376		-
377		- # All things being equal, string comparison.
378		- if element_a.name > element_b.name:
379		- return 1
380		- elif element_a.name < element_b.name:
381		- return -1
382		-
383		- # Sort local elements before junction elements
384		- # and use string comparison between junction elements
385		- if element_a.junction and element_b.junction:
386		- if element_a.junction > element_b.junction:
387		- return 1
388		- elif element_a.junction < element_b.junction:
389		- return -1
390		- elif element_a.junction:
391		- return -1
392		- elif element_b.junction:
393		- return 1
394		-
395		- # This wont ever happen
396		- return 0
397		-
398		- # Now dependency sort, we ensure that if any direct dependency
399		- # directly or indirectly depends on another direct dependency,
400		- # it is found later in the list.
401		- element.dependencies.sort(key=cmp_to_key(dependency_cmp))
402		-
403		- visited.add(element)
404		-
405	338	# _collect_element()
406	339	#
407	340	# Collect the toplevel elements we have
...	...	@@ -454,19 +387,10 @@ class Loader():
454	387	# Cache it now, make sure it's already there before recursing
455	388	self._meta_elements[element.name] = meta_element
456	389
457		- # # Descend
458		- # for dep in element.dependencies:
459		- # loader = dep.element._loader
460		- # meta_dep = loader._collect_element(dep.element)
461		- # if dep.dep_type != 'runtime':
462		- # meta_element.build_dependencies.append(meta_dep)
463		- # if dep.dep_type != 'build':
464		- # meta_element.dependencies.append(meta_dep)
465		-
466	390	return meta_element
467	391
468	392	def _collect_elements(self, elements):
469		- elements_to_load = deque(elements)
	393	+ elements_to_load = deque(reversed(elements))
470	394
471	395	def compare_unprocessed(dep_a, dep_b):
472	396	if dep_a.dep_type != dep_b.dep_type:
...	...	@@ -498,150 +422,44 @@ class Loader():
498	422
499	423	return 0
500	424
501		- print("#" * 60)
	425	+ def not_visited(element):
	426	+ return not element.visited
502	427
503	428	while elements_to_load:
504		- print([e.name for e in elements_to_load])
505	429	element = elements_to_load.popleft()
506	430
507		- print("Treating", element.name)
508		-
509		- if element.visited:
510		- print("\tAlready visited")
511		- continue
512		-
513		- unprocessed_dependencies = [
514		- dep
515		- for dep in element.dependencies
516		- if dep.element.visited is False
517		- ]
518		-
519		- if unprocessed_dependencies:
520		- print("\tUnprocessed deps:", [e.element.name for e in unprocessed_dependencies])
521		- elements_to_load.appendleft(element)
522		- elements_to_load.extendleft(
523		- dep.element
524		- for dep in sorted(unprocessed_dependencies, key=cmp_to_key(compare_unprocessed), reverse=True)
525		- )
	431	+ if any(filter(not_visited, element.reverse_dependencies)):
	432	+ # We will want to treat this item as soon as possible.
	433	+ # Mark it as already seen
	434	+ element.tried_visit = True
526	435	continue
527	436
528	437	element.visited = True
529	438	meta_element = element._loader._collect_element(element)
	439	+ element.visit(meta_element)
530	440
531		- for dep in element.dependencies:
532		- print("\tElement has dependency:", dep.element.name)
533		- meta_dep = dep.element._loader._collect_element(dep.element)
534		-
	441	+ for dep in sorted(element.dependencies, key=cmp_to_key(compare_unprocessed), reverse=True):
535	442	if dep.dep_type != Symbol.RUNTIME:
536		- meta_element.build_dependencies.append(meta_dep)
	443	+ dep.element.on_visit(meta_element.build_dependencies.append)
537	444	if dep.dep_type != Symbol.BUILD:
538		- meta_element.dependencies.append(meta_dep)
	445	+ dep.element.on_visit(meta_element.dependencies.append)
539	446
540		- from operator import attrgetter
541		- meta_element.build_dependencies.sort(key=attrgetter("index"))
542		- meta_element.dependencies.sort(key=attrgetter("index"))
	447	+ if not element.in_pipeline:
	448	+ if dep.element.tried_visit:
	449	+ # This element has already been requested, we should treat
	450	+ # it as soon as possible
	451	+ elements_to_load.appendleft(dep.element)
	452	+ else:
	453	+ elements_to_load.append(dep.element)
	454	+
	455	+ for element in self._meta_elements.values():
	456	+ element.build_dependencies.sort(key=attrgetter("index"), reverse=True)
	457	+ element.dependencies.sort(key=attrgetter("index"), reverse=True)
543	458
544	459	ret = [self._collect_element(e) for e in elements]
545	460
546		- print("RETURN:", [e.name for e in ret])
547	461	return ret
548	462
549		- # levels = defaultdict(list)
550		-
551		- # while elements_to_load:
552		- # print("#" * 60)
553		- # print([e.name for e in elements_to_load])
554		- # element = elements_to_load.popleft()
555		- # print("Treating element", element.name)
556		-
557		- # if element.level is not None: # This node has already been treated
558		- # print("Element", element.name, "already treated with level", element.level)
559		- # continue
560		-
561		- # unprocessed_reverse_dependencies = [
562		- # rdep
563		- # for rdep in element.reverse_dependencies
564		- # if rdep.level is None
565		- # ]
566		-
567		- # if unprocessed_reverse_dependencies:
568		- # print("Element has unprocessed reverse dependencies:", [e.name for e in unprocessed_reverse_dependencies])
569		- # elements_to_load.appendleft(element)
570		- # elements_to_load.extendleft(unprocessed_reverse_dependencies)
571		- # continue
572		-
573		- # element.level = 1 + max((e.level for e in element.reverse_dependencies), default=0)
574		- # levels[element.level].append(element)
575		- # print("Element level is", element.level)
576		- # print("Levels: ", {
577		- # key: [e.name for e in value]
578		- # for key, value in levels.items()
579		- # })
580		-
581		- # def sort_by_dep_type(dep_a, dep_b):
582		- # if dep_a.dep_type != dep_b.dep_type:
583		- # if dep_a.dep_type == Symbol.RUNTIME:
584		- # return 1
585		- # if dep_b.dep_type == Symbol.RUNTIME:
586		- # return -1
587		-
588		- # element_a = dep_a.element
589		- # element_b = dep_b.element
590		-
591		- # # All things being equal, string comparison.
592		- # if element_a.name > element_b.name:
593		- # return 1
594		- # elif element_a.name < element_b.name:
595		- # return -1
596		-
597		- # # Sort local elements before junction elements
598		- # # and use string comparison between junction elements
599		- # if element_a.junction and element_b.junction:
600		- # if element_a.junction > element_b.junction:
601		- # return 1
602		- # elif element_a.junction < element_b.junction:
603		- # return -1
604		- # elif element_a.junction:
605		- # return -1
606		- # elif element_b.junction:
607		- # return 1
608		-
609		- # return 0
610		-
611		- # elements_to_load.extend(
612		- # dep.element
613		- # for dep in sorted(element.dependencies, key=cmp_to_key(sort_by_dep_type))
614		- # )
615		-
616		- # ret = []
617		-
618		- # from operator import attrgetter
619		-
620		- # print("Sorting levels")
621		-
622		- # for _level in sorted(levels.keys(), reverse=True):
623		- # print("## Treating level", _level)
624		- # for element in levels[_level]:
625		- # print("\t## Element", element.name)
626		- # meta_element = self._collect_element(element)
627		-
628		- # for dep in element.dependencies:
629		- # meta_dep = self._collect_element(dep.element)
630		-
631		- # if dep.dep_type != Symbol.RUNTIME:
632		- # meta_element.build_dependencies.append(meta_dep)
633		- # if dep.dep_type != Symbol.BUILD:
634		- # meta_element.dependencies.append(meta_dep)
635		-
636		- # meta_element.build_dependencies.sort(key=attrgetter("index"))
637		- # meta_element.dependencies.sort(key=attrgetter("index"))
638		-
639		- # if _level == 1:
640		- # ret.append(meta_element)
641		-
642		- # return ret
643		-
644		-
645	463	# _get_loader():
646	464	#
647	465	# Return loader for specified junction

buildstream/_loader/metaelement.py

---

...	...	@@ -17,6 +17,7 @@
17	17	# Authors:
18	18	# Tristan Van Berkom <tristan vanberkom codethink co uk>
19	19
	20	+from collections import deque
20	21	import itertools
21	22
22	23

—
View it on GitLab.
You're receiving this email because of your account on gitlab.com. If you'd like to receive fewer emails, you can adjust your notification settings.