1 files changed, 139 insertions, 0 deletions
diff --git a/bestflags/generation.py b/bestflags/generation.py
new file mode 100644
index 00000000..67c379f5
--- /dev/null
+++ b/bestflags/generation.py
@@ -0,0 +1,139 @@
+# Copyright (c) 2013 The Chromium OS Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+"""A generation of a set of tasks.
+
+Part of the Chrome build flags optimization.
+
+This module contains the base generation class. This class contains the tasks of
+this current generation. The generation will not evolve to the next generation
+until all the tasks in this generation are done executing. It also contains a
+set of tasks that could potentially be used to generate the next generation,
+e.g., in the genetic algorithm, a set of good species will be kept to evolve to
+the successive generations. For the hill climbing algorithm example, the
+candidate_pool will contain a current task t being evaluated and the exe_set
+will contains all the task t's neighbor.
+"""
+
+__author__ = 'yuhenglong@google.com (Yuheng Long)'
+
+
+class NoneOverridingError(Exception):
+  """Define an Exception class for subclasses not overriding certain methods."""
+  pass
+
+
+class Generation(object):
+  """A generation of a framework run.
+
+  The base class of generation. Concrete subclasses, e.g., GAGeneration should
+  override the Next and IsImproved method to implement algorithm specific
+  applications.
+  """
+
+  def __init__(self, exe_set, candidate_pool):
+    """Set up the tasks set of this generation.
+
+    Args:
+      exe_set: A set of tasks to be run.
+      candidate_pool: A set of tasks to be considered to be used to generate the
+        next generation.
+    """
+
+    self._exe_set = exe_set
+    self._candidate_pool = candidate_pool
+
+    # Keeping the record of how many tasks are pending. Pending tasks are the
+    # ones that have been sent out to the next stage for execution but have not
+    # finished. A generation is not ready for the reproduction of the new
+    # generations until all its pending tasks have been executed.
+    self._pending = len(exe_set)
+
+  def CandidatePool(self):
+    """Return the candidate tasks of this generation."""
+
+    return self._candidate_pool
+
+  def Pool(self):
+    """Return the task set of this generation."""
+
+    return self._exe_set
+
+  def Done(self):
+    """All the tasks in this generation are done.
+
+    Returns:
+      True if all the tasks have been executed. That is the number of pending
+      task is 0.
+    """
+
+    return self._pending == 0
+
+  def UpdateTask(self, task):
+    """Match a task t in this generation that is equal to the input task.
+
+    This method is called when the input task has just finished execution. This
+    method finds out whether there is a pending task t in the current generation
+    that is the same as the input task. Two tasks are the same if their flag
+    options are the same. A task is pending if it has not been performed.
+    If there is a pending task t that matches the input task, task t will be
+    substituted with the input task in this generation. In that case, the input
+    task, as well as its build and test results encapsulated in the task, will
+    be stored in the current generation. These results could be used to produce
+    the next generation.
+    If there is a match, the current generation will have one less pending task.
+    When there is no pending task, the generation can be used to produce the
+    next generation.
+    The caller of this function is responsible for not calling this method on
+    the same task more than once.
+
+    Args:
+      task: A task that has its results ready.
+
+    Returns:
+      Whether the input task belongs to this generation.
+    """
+
+    # If there is a match, the input task belongs to this generation.
+    if task not in self._exe_set:
+      return False
+
+    # Remove the place holder task in this generation and store the new input
+    # task and its result.
+    self._exe_set.remove(task)
+    self._exe_set.add(task)
+
+    # The current generation will have one less task to wait on.
+    self._pending -= 1
+
+    assert self._pending >= 0
+
+    return True
+
+  def IsImproved(self):
+    """True if this generation has improvement upon its parent generation.
+
+    Raises:
+      NoneOverridingError: The subclass should override this method.
+    """
+    raise NoneOverridingError('Must be implemented by child class')
+
+  def Next(self, _):
+    """Calculate the next generation.
+
+    This is the core of the framework implementation. It must be overridden by
+    the concrete subclass to implement algorithm specific generations.
+
+    Args:
+      _: A set of tasks that have been generated before. The overridden method
+        in the subclasses can use this so as not to generate task that has been
+        generated before.
+
+    Returns:
+      A set of new generations.
+
+    Raises:
+      NoneOverridingError: The subclass should override this method.
+    """
+
+    raise NoneOverridingError('Must be implemented by child class')