[Notes] [Git][BuildStream/buildstream][bschubert/rework-sort] Try another approach

[Benjamin Schubert <gitlab mg gitlab com>]

Title: GitLab

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

Commits:

• 4706ffa7
  by Benjamin Schubert at 2019-02-05T12:14:31Z

  Try another approach
  

1 changed file:

• buildstream/_loader/loader.py

Changes:

buildstream/_loader/loader.py

---

...	...	@@ -390,6 +390,34 @@ class Loader():
390	390	return meta_element
391	391
392	392	def _collect_elements(self, elements):
	393	+ all_elements = set()
	394	+ elements_to_process = set(elements)
	395	+
	396	+ while elements_to_process:
	397	+ element = elements_to_process.pop()
	398	+ all_elements.add(element)
	399	+ elements_to_process.update([d.element for d in element.dependencies])
	400	+
	401	+ def sorter(element_a, element_b):
	402	+ if element_a.name > element_b.name:
	403	+ return 1
	404	+ elif element_a.name < element_b.name:
	405	+ return -1
	406	+
	407	+ # Sort local elements before junction elements
	408	+ # and use string comparison between junction elements
	409	+ if element_a.junction and element_b.junction:
	410	+ if element_a.junction > element_b.junction:
	411	+ return 1
	412	+ elif element_a.junction < element_b.junction:
	413	+ return -1
	414	+ elif element_a.junction:
	415	+ return -1
	416	+ elif element_b.junction:
	417	+ return 1
	418	+
	419	+ raise Exception("Impossible")
	420	+
393	421	def compare_unprocessed(dep_a, dep_b):
394	422	if dep_a.dep_type != dep_b.dep_type:
395	423	if dep_a.dep_type == Symbol.RUNTIME:
...	...	@@ -420,54 +448,166 @@ class Loader():
420	448
421	449	return 0
422	450
423		- def not_visited(element):
424		- return not element.visited
	451	+ def not_visited(dep):
	452	+ return not dep.element.visited
425	453
426		- elements_to_load = deque(elements)
	454	+ all_elements = deque(sorted(all_elements, key=cmp_to_key(sorter)))
427	455
428		- for element in elements_to_load:
429		- element.in_pipeline = True
	456	+ # print([e.full_name for e in all_elements])
430	457
431		- while elements_to_load:
432		- element = elements_to_load.pop()
	458	+ for _ in range(len(all_elements)):
	459	+ current = all_elements.popleft()
433	460
434		- if element.visited:
435		- continue
	461	+ for dep in sorted(filter(not_visited, current.dependencies)):
	462	+ dep.element.visited = True
	463	+ all_elements.append(dep.element)
	464	+
	465	+ current.visited = True
	466	+ all_elements.append(current)
436	467
437		- if any(filter(not_visited, element.reverse_dependencies)):
438		- # We will want to treat this item as soon as possible.
439		- # Mark it as already seen
440		- element.tried_visit = True
441		- element.in_pipeline = False
	468	+ for _ in range(len(all_elements)):
	469	+ current = all_elements.popleft()
	470	+ if not current.visited:
442	471	continue
443	472
444		- element.visited = True
445		- meta_element = element._loader._collect_element(element)
446		- element.visit(meta_element)
	473	+ current.visited = False
	474	+ all_elements.append(current)
	475	+
	476	+ # print([e.full_name for e in all_elements])
447	477
448		- pq = deque()
	478	+ for element in all_elements:
	479	+ # print("#" * 60)
	480	+ # print("Treating", element.full_name)
	481	+ # print("With deps:", [e.element.full_name for e in element.dependencies])
449	482
450		- for dep in sorted(element.dependencies, key=cmp_to_key(compare_unprocessed), reverse=True):
	483	+ meta_element = element._loader._collect_element(element)
	484	+
	485	+ for dep in element.dependencies:
	486	+ dependency = dep.element._loader._meta_elements[dep.element.name]
451	487	if dep.dep_type != Symbol.RUNTIME:
452		- dep.element.on_visit(meta_element.build_dependencies.append)
	488	+ meta_element.build_dependencies.append(dependency)
453	489	if dep.dep_type != Symbol.BUILD:
454		- dep.element.on_visit(meta_element.dependencies.append)
	490	+ meta_element.dependencies.append(dependency)
455	491
456		- if not dep.element.in_pipeline:
457		- if dep.element.tried_visit:
458		- # This element has already been requested, we should treat
459		- # it as soon as possible
460		- pq.appendleft(dep.element)
461		- else:
462		- elements_to_load.appendleft(dep.element)
	492	+ for element in self._meta_elements.values():
	493	+ element.build_dependencies.sort(key=attrgetter("index"))
	494	+ element.dependencies.sort(key=attrgetter("index"))
463	495
464		- dep.element.in_pipeline = True
465	496
466		- elements_to_load.extend(pq)
467	497
468		- for element in self._meta_elements.values():
469		- element.build_dependencies.sort(key=attrgetter("index"), reverse=True)
470		- element.dependencies.sort(key=attrgetter("index"), reverse=True)
	498	+
	499	+
	500	+
	501	+
	502	+
	503	+
	504	+
	505	+
	506	+
	507	+ # def compare_unprocessed(dep_a, dep_b):
	508	+ # if dep_a.dep_type != dep_b.dep_type:
	509	+ # if dep_a.dep_type == Symbol.RUNTIME:
	510	+ # return 1
	511	+ # if dep_b.dep_type == Symbol.RUNTIME:
	512	+ # return -1
	513	+
	514	+ # element_a = dep_a.element
	515	+ # element_b = dep_b.element
	516	+
	517	+ # # All things being equal, string comparison.
	518	+ # if element_a.name > element_b.name:
	519	+ # return 1
	520	+ # elif element_a.name < element_b.name:
	521	+ # return -1
	522	+
	523	+ # # Sort local elements before junction elements
	524	+ # # and use string comparison between junction elements
	525	+ # if element_a.junction and element_b.junction:
	526	+ # if element_a.junction > element_b.junction:
	527	+ # return 1
	528	+ # elif element_a.junction < element_b.junction:
	529	+ # return -1
	530	+ # elif element_a.junction:
	531	+ # return -1
	532	+ # elif element_b.junction:
	533	+ # return 1
	534	+
	535	+ # return 0
	536	+
	537	+ # def not_visited(element):
	538	+ # return not element.visited
	539	+
	540	+ # next_iteration = list([e for e in elements if not len(list(e.reverse_dependencies))])
	541	+ # counter = 0
	542	+
	543	+ # while next_iteration:
	544	+ # counter += 1
	545	+ # current_iteration = next_iteration
	546	+ # next_iteration = []
	547	+
	548	+ # print("Iteration", counter, ":", [e.name for e in current_iteration])
	549	+
	550	+ # for element in sorted(current_iteration, key=cmp_to_key(compare_unprocessed)):
	551	+ # element.visited = True
	552	+ # meta_element = element._loader._collect_element(element)
	553	+ # element.visit(meta_element)
	554	+
	555	+ # for dep in element.dependencies:
	556	+ # if dep.dep_type != Symbol.RUNTIME:
	557	+ # dep.element.on_visit(meta_element.build_dependencies.append)
	558	+ # if dep.dep_type != Symbol.BUILD:
	559	+ # dep.element.on_visit(meta_element.dependencies.append)
	560	+
	561	+ # if not any(filter(not_visited, dep.element.reverse_dependencies)):
	562	+ # next_iteration.append(dep.element)
	563	+
	564	+
	565	+
	566	+ # for element in elements_to_load:
	567	+ # element.in_pipeline = True
	568	+
	569	+ # element = elements_to_load.pop()
	570	+
	571	+ # # if element.visited:
	572	+ # # continue
	573	+
	574	+ # # if any(filter(not_visited, element.reverse_dependencies)):
	575	+ # # # We will want to treat this item as soon as possible.
	576	+ # # # Mark it as already seen
	577	+ # # element.tried_visit = True
	578	+ # # element.in_pipeline = False
	579	+ # # continue
	580	+
	581	+ # element.visited = True
	582	+ # meta_element = element._loader._collect_element(element)
	583	+ # element.visit(meta_element)
	584	+
	585	+ # # pq = deque()
	586	+
	587	+ # for dep in sorted(element.dependencies, key=cmp_to_key(compare_unprocessed)):
	588	+ # if dep.dep_type != Symbol.RUNTIME:
	589	+ # dep.element.on_visit(meta_element.build_dependencies.append)
	590	+ # if dep.dep_type != Symbol.BUILD:
	591	+ # dep.element.on_visit(meta_element.dependencies.append)
	592	+
	593	+
	594	+ # elements_to_load.appendleft(dep.element)
	595	+
	596	+ # # if not dep.element.in_pipeline:
	597	+ # # # if dep.element.tried_visit:
	598	+ # # # # This element has already been requested, we should treat
	599	+ # # # # it as soon as possible
	600	+ # # # pq.appendleft(dep.element)
	601	+ # # else:
	602	+ # # elements_to_load.appendleft(dep.element)
	603	+
	604	+ # # dep.element.in_pipeline = True
	605	+
	606	+ # # elements_to_load.extend(pq)
	607	+
	608	+ # for element in self._meta_elements.values():
	609	+ # element.build_dependencies.sort(key=attrgetter("index"), reverse=True)
	610	+ # element.dependencies.sort(key=attrgetter("index"), reverse=True)
471	611
472	612	ret = [self._collect_element(e) for e in elements]
473	613

—
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.