1# Copyright 2013 The ChromiumOS Authors 2# Use of this source code is governed by a BSD-style license that can be 3# found in the LICENSE file. 4"""A generation of a set of tasks. 5 6Part of the Chrome build flags optimization. 7 8This module contains the base generation class. This class contains the tasks of 9this current generation. The generation will not evolve to the next generation 10until all the tasks in this generation are done executing. It also contains a 11set of tasks that could potentially be used to generate the next generation, 12e.g., in the genetic algorithm, a set of good species will be kept to evolve to 13the successive generations. For the hill climbing algorithm example, the 14candidate_pool will contain a current task t being evaluated and the exe_set 15will contains all the task t's neighbor. 16""" 17 18__author__ = "[email protected] (Yuheng Long)" 19 20 21class NoneOverridingError(Exception): 22 """Define an Exception class for subclasses not overriding certain methods.""" 23 24 pass 25 26 27class Generation(object): 28 """A generation of a framework run. 29 30 The base class of generation. Concrete subclasses, e.g., GAGeneration should 31 override the Next and IsImproved method to implement algorithm specific 32 applications. 33 """ 34 35 def __init__(self, exe_set, candidate_pool): 36 """Set up the tasks set of this generation. 37 38 Args: 39 exe_set: A set of tasks to be run. 40 candidate_pool: A set of tasks to be considered to be used to generate the 41 next generation. 42 """ 43 44 self._exe_set = exe_set 45 self._candidate_pool = candidate_pool 46 47 # Keeping the record of how many tasks are pending. Pending tasks are the 48 # ones that have been sent out to the next stage for execution but have not 49 # finished. A generation is not ready for the reproduction of the new 50 # generations until all its pending tasks have been executed. 51 self._pending = len(exe_set) 52 53 def CandidatePool(self): 54 """Return the candidate tasks of this generation.""" 55 56 return self._candidate_pool 57 58 def Pool(self): 59 """Return the task set of this generation.""" 60 61 return self._exe_set 62 63 def Done(self): 64 """All the tasks in this generation are done. 65 66 Returns: 67 True if all the tasks have been executed. That is the number of pending 68 task is 0. 69 """ 70 71 return self._pending == 0 72 73 def UpdateTask(self, task): 74 """Match a task t in this generation that is equal to the input task. 75 76 This method is called when the input task has just finished execution. This 77 method finds out whether there is a pending task t in the current generation 78 that is the same as the input task. Two tasks are the same if their flag 79 options are the same. A task is pending if it has not been performed. 80 If there is a pending task t that matches the input task, task t will be 81 substituted with the input task in this generation. In that case, the input 82 task, as well as its build and test results encapsulated in the task, will 83 be stored in the current generation. These results could be used to produce 84 the next generation. 85 If there is a match, the current generation will have one less pending task. 86 When there is no pending task, the generation can be used to produce the 87 next generation. 88 The caller of this function is responsible for not calling this method on 89 the same task more than once. 90 91 Args: 92 task: A task that has its results ready. 93 94 Returns: 95 Whether the input task belongs to this generation. 96 """ 97 98 # If there is a match, the input task belongs to this generation. 99 if task not in self._exe_set: 100 return False 101 102 # Remove the place holder task in this generation and store the new input 103 # task and its result. 104 self._exe_set.remove(task) 105 self._exe_set.add(task) 106 107 # The current generation will have one less task to wait on. 108 self._pending -= 1 109 110 assert self._pending >= 0 111 112 return True 113 114 def IsImproved(self): 115 """True if this generation has improvement upon its parent generation. 116 117 Raises: 118 NoneOverridingError: The subclass should override this method. 119 """ 120 raise NoneOverridingError("Must be implemented by child class") 121 122 def Next(self, _): 123 """Calculate the next generation. 124 125 This is the core of the framework implementation. It must be overridden by 126 the concrete subclass to implement algorithm specific generations. 127 128 Args: 129 _: A set of tasks that have been generated before. The overridden method 130 in the subclasses can use this so as not to generate task that has been 131 generated before. 132 133 Returns: 134 A set of new generations. 135 136 Raises: 137 NoneOverridingError: The subclass should override this method. 138 """ 139 140 raise NoneOverridingError("Must be implemented by child class") 141