"""Platform independant processing of parallel blocks.
"""

import sys, re, string, types
import crymp

class Job:
  """Class representing a high-level abstraction of a parallelizable job.
  """

  job_map = { }
  job_id_counter = 0

  def __init__(self, element):
    """Constructor.

    :Parameters:
      - `element`: The parallelizable element to be executed by the job.  This
	is an instance of one of the following classes: PSection, PLoop,
	PLocal.
    """

    if (not isinstance(element, crymp.parse.PSection)
	and not isinstance(element, crymp.parse.PLoop)
	and not isinstance(element, crymp.parse.PLocal)):
      raise TypeError, 'element'

    self.element = element
    self.name = element.name
    self.line = element.line
    self.id = Job.job_id_counter
    self.is_tail = False
    Job.job_id_counter += 1
    Job.job_map[element] = self
    self.waitfor = [ ]
    self.depending = [ ]
    priority = element.annotation['priority']
    if priority is not None:
      try:
        priority = int(priority)
      except:
        crymp.warning(crymp.loc(element.block.filename, element.block.line)
	    + 'Bad priority value ' + repr(priority))
	priority = 0
    else:
      priority = 0
    self.priority = priority
    element.priority = priority

  def add_waitfor(self, job):
    if not isinstance(job, Job): raise TypeError, 'job'

    assert job not in self.waitfor
    self.waitfor.append(job)
    job.depending.append(self)

  def add_depending(self, job):
    if not isinstance(job, Job): raise TypeError, 'job'

    assert job not in self.depending
    self.depending.append(job)
    job.waitfor.append(self)

  def setup_deps(self, element):
    """Setup the job dependencies by traversing the dependencies of the
    specified element.

    This is a recursive process, starting with the element assoicated with the
    job.

    :Parameters:
      - `element`: The element assoicated with the job.
    """

    for dependency in element.waitfor:
      if (isinstance(dependency, crymp.parse.PLoop)
	  or isinstance(dependency, crymp.parse.PSection)
	  or isinstance(dependency, crymp.parse.PLocal)):
	assert dependency in Job.job_map
	self.add_waitfor(Job.job_map[dependency])
      elif isinstance(dependency, crymp.parse.PBarrier):
        self.setup_deps(dependency)
      else:
	raise RuntimeError, 'Unexpected dependency ' + repr(dependency)

  def get_context(self, parent_context):
    """Get a context for the called job.

    :Parameters:
      - `parent_context`: The parent context.
    """

    return crymp.Context(
	{ 'job': self },
	self.element.get_context(parent_context))

  def get_decl(self, skel, context, scope):
    """Get the declaration(s) for the job.

    :Parameters:
      - `skel`: The skeleton to be used for expanding the job code.
      - `context`: The context of the containing parallel block.
      - `scope`: The evaluation scope (i.e. the class that the returned
	declaration is added to).  This is either 'shared' or 'local'.

    :Return:
      The method returns the declaration code (at indent level 0).
    """

    job_decl = None
    if crymp.Options.driver == crymp.Options.DRIVER_SINGLECORE:
      job_decl = crymp.singlecore.job_decl(self, skel, context, scope)
    elif crymp.Options.driver == crymp.Options.DRIVER_MULTICORE:
      job_decl = crymp.multicore.job_decl(self, skel, context, scope)
    elif crymp.Options.driver == crymp.Options.DRIVER_PS3:
      job_decl = crymp.ps3.job_decl(self, skel, context, scope)
    else:
      raise ValueError
    return job_decl

  def get_def(self, skel, context, scope):
    """Get the definition(s) for the job.

    :Parameters:
      - `skel`: The skeleton to be used for expanding the job code.
      - `context`: The context of the containing parallel block.
      - `scope`: The evaluation scope (i.e. the class that the returned
	declaration is added to).  This is either 'shared' or 'local'.

    :Return:
      The method returns the definition code (at indent level 0).
    """

    job_def = None
    if crymp.Options.driver == crymp.Options.DRIVER_SINGLECORE:
      job_def = crymp.singlecore.job_def(self, skel, context, scope)
    elif crymp.Options.driver == crymp.Options.DRIVER_MULTICORE:
      job_def = crymp.multicore.job_def(self, skel, context, scope)
    elif crymp.Options.driver == crymp.Options.DRIVER_PS3:
      job_def = crymp.ps3.job_def(self, skel, context, scope)
    else:
      raise ValueError
    return job_def

  def get_deps(self, prefix):
    """Get the dependencies of the job.

    This is a comma separated list of job IDs.  The specified prefix is
    prepended to every job ID.

    :Parameters:
      - `prefix`: The job ID prefix.

    :Return:
      The dependencies list, represented as a comma separated string.
    """

    s = None
    for job in self.waitfor:
      if s is None:
	s = prefix + str(job.id)
      else:
	s += ', ' + prefix + str(job.id)
    return s

  def __str__(self):
    s = crymp.parse.indent() + '<Job>\n'
    crymp.Options.output_indent += 1
    s += crymp.parse.indent() + 'id = ' + str(self.id) + '\n'
    s += crymp.parse.indent() + 'name = ' + repr(self.name) + '\n'
    s += crymp.parse.indent() + 'priority = ' + repr(self.priority) + '\n'
    s += crymp.parse.indent() + 'waitfor = [ '
    comma = ''
    for job in self.waitfor:
      s += comma + str(job.id)
      comma = ', '
    if len(self.waitfor) > 0: s += ' '
    s += ']\n'
    s += crymp.parse.indent() + 'depending = [ '
    comma = ''
    for job in self.depending:
      s += comma + str(job.id)
      comma = ', '
    s += ']\n'
    s += str(self.element) + '\n'
    crymp.Options.output_indent -= 1
    s += crymp.parse.indent() + '</Job>\n'
    return s

  def __repr__(self): return str(self)

def process(block):
  """Platform independant processing.

  - Organize the code fragments within the parallel block into jobs.  The
    jobs form a directed graph, the edges of the graph represent the job
    dependencies.  The edge information is stored reduntantly in both jobs
    of a dependency relation.
  - Identify tail jobs, i.e. jobs with no incoming dependency link (i.e. no
    other jobs depending).
  - Create a topologically sorted array of jobs with high priority jobs listed
    first (if possible).

  The function will set the 'jobs' property of the specified block to the
  sorted list of job objects.  The architecure dependant output drivers will
  pick up the job list for further processing.  Tail jobs are identified by
  the 'is_tail' property.  (These are the jobs with no dependant jobs.)
  """

  if not isinstance(block, crymp.parse.PBlock): raise TypeError, 'block'

  # Build the job list and setup dependencies.
  job_list = [ ]
  for loop in block.loops:
    job_list.append(Job(loop))
  for section in block.sections:
    job_list.append(Job(section))
  for local in block.locals:
    job_list.append(Job(local))
  for job in job_list:
    job.setup_deps(job.element)

  # Pre-sort the dependencies by line number.  This is useful because the
  # priority sub-sorting below is stable, so the declaration order will be
  # retained whenever possible.
  job_list.sort(cmp = lambda x, y: x.line - y.line)

  # Do a topological sort using priority for sub-sorting.
  # The code below is kept as simple as possible at the cost of performance.
  # This should not be a problem because dependency graphs will be very tiny
  # in practice.
  sorted_job_list = [ ]
  while len(job_list) > len(sorted_job_list):
    # Get the list of candidates for appending to the sorted list.
    candidates = [ ]
    for job in job_list:
      is_candidate = True
      if job in sorted_job_list:
	is_candidate = False
      else:
	for waitfor_job in job.waitfor:
	  if waitfor_job not in sorted_job_list:
	    is_candidate = False
	    break
      if is_candidate:
	candidates.append(job)
    # If there are no candidates, then there must be a circular dependency
    # somewhere in the parallel block.
    if len(candidates) == 0:
      block = job.element.block
      crymp.error(crymp.loc(block.filename, job.element.line)
	  + 'Circular dependency')
      sys.exit(1)
    # Sort candidates by priority, highest priority first.  The sort operation
    # is stable.
    candidates.sort(
	cmp = lambda x, y: x.priority - y.priority,
	reverse = True)
    sorted_job_list.extend(candidates)

  block.jobs = sorted_job_list

  # Mark tail jobs.
  for job in block.jobs:
    if len(job.depending) == 0: job.is_tail = True

