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