generation.py revision 057ad5c77ef0ea44ee260718eb6d30afef2f7f83 
1# Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
2# Use of this source code is governed by a BSD-style license that can be
3# found in the LICENSE file.
4
5"""A generation of a set of tasks.
6
7Part of the Chrome build flags optimization.
8
9This module contains the base generation class. This class contains the tasks of
10this current generation. The generation will not evolve to the next generation
11until all the tasks in this generation are done executing. It also contains a
12set of tasks that could potentially be used to generate the next generation,
13e.g., in the genetic algorithm, a set of good species will be kept to evolve to
14the successive generations. For the hill climbing algorithm example, the
15candidate_pool will contain a current task t being evaluated and the exe_pool
16will contains all the task t's neighbor.
17"""
18
19__author__ = 'yuhenglong@google.com (Yuheng Long)'
20
21
22class NoneOverridingError(Exception):
23  """Define an Exception class for subclasses not overriding certain methods."""
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 Improve method to implement algorithm specific
32  applications.
33  """
34
35  def __init__(self, exe_pool, candidate_pool):
36    """Set up the tasks set of this generation.
37
38    Args:
39      exe_pool: 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_pool = exe_pool
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_pool)
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_pool
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_pool:
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_pool.remove(task)
105    self._exe_pool.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 Improve(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