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