#!/usr/bin/python
# Copyright (c) 2012 The Native Client Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.

import os
import re
import sys

"""Header Scanner.

This module will scan a set of input sources for include dependencies.  Use
the command-line switch -Ixxxx to add include paths.  All filenames and paths
are expected and returned with POSIX separators.
"""


debug = False


def DebugPrint(txt):
  if debug: print txt


class PathConverter(object):
  """PathConverter does path manipulates using Posix style pathnames.

  Regardless of the native path type, all inputs and outputs to the path
  functions are with POSIX style separators.
  """
  def ToNativePath(self, pathname):
    return os.path.sep.join(pathname.split('/'))

  def ToPosixPath(self, pathname):
    return '/'.join(pathname.split(os.path.sep))

  def isfile(self, pathname):
    ospath = self.ToNativePath(pathname)
    return os.path.isfile(ospath)

  def getcwd(self):
    return self.ToPosixPath(os.getcwd())

  def isabs(self, pathname):
    ospath = self.ToNativePath(pathname)
    return os.path.isabs(ospath)

  def isdir(self, pathname):
    ospath = self.ToNativePath(pathname)
    return os.path.isdir(ospath)

  def open(self, pathname):
    ospath = self.ToNativePath(pathname)
    return open(ospath)

  def abspath(self, pathname):
    ospath = self.ToNativePath(pathname)
    ospath = os.path.abspath(ospath)
    return self.ToPosixPath(ospath)

  def dirname(self, pathname):
    ospath = self.ToNativePath(pathname)
    ospath = os.path.dirname(ospath)
    return self.ToPosixPath(ospath)


filename_to_relative_cache = {}  # (filepath, basepath) -> relpath
findfile_cache = {}  # (tuple(searchdirs), cwd, file) -> filename/None
pathisfile_cache = {}  # abspath -> boolean, works because fs is static
                       # during a run.


class Resolver(object):
  """Resolver finds and generates relative paths for include files.

  The Resolver object provides a mechanism to to find and convert a source or
  include filename into a relative path based on provided search paths.  All
  paths use POSIX style separator.
  """
  def __init__(self, pathobj=PathConverter()):
    self.search_dirs = []
    self.pathobj = pathobj
    self.cwd = self.pathobj.getcwd()
    self.offs = len(self.cwd)

  def AddOneDirectory(self, pathname):
    """Add an include search path."""
    pathname = self.pathobj.abspath(pathname)
    DebugPrint('Adding DIR: %s' % pathname)
    if pathname not in self.search_dirs:
      if self.pathobj.isdir(pathname):
        self.search_dirs.append(pathname)
      else:
        # We can end up here when using the gyp generator analyzer. To avoid
        # spamming only log if debug enabled.
        DebugPrint('Not a directory: %s\n' % pathname)
        return False
    return True

  def RemoveOneDirectory(self, pathname):
    """Remove an include search path."""
    pathname = self.pathobj.abspath(pathname)
    DebugPrint('Removing DIR: %s' % pathname)
    if pathname in self.search_dirs:
      self.search_dirs.remove(pathname)
    return True

  def AddDirectories(self, pathlist):
    """Add list of space separated directories."""
    failed = False
    dirlist = ' '.join(pathlist)
    for dirname in dirlist.split(' '):
      if not self.AddOneDirectory(dirname):
        failed = True
    return not failed

  def GetDirectories(self):
    return self.search_dirs

  def RealToRelative(self, filepath, basepath):
    """Returns a relative path from an absolute basepath and filepath."""
    cache_key = (filepath, basepath)
    cache_result = None
    if cache_key in filename_to_relative_cache:
      cache_result = filename_to_relative_cache[cache_key]
      return cache_result
    def SlowRealToRelative(filepath, basepath):
      path_parts = filepath.split('/')
      base_parts = basepath.split('/')
      while path_parts and base_parts and path_parts[0] == base_parts[0]:
        path_parts = path_parts[1:]
        base_parts = base_parts[1:]
      rel_parts = ['..'] * len(base_parts) + path_parts
      rel_path = '/'.join(rel_parts)
      return rel_path
    rel_path = SlowRealToRelative(filepath, basepath)
    filename_to_relative_cache[cache_key] = rel_path
    return rel_path

  def FilenameToRelative(self, filepath):
    """Returns a relative path from CWD to filepath."""
    filepath = self.pathobj.abspath(filepath)
    basepath = self.cwd
    return self.RealToRelative(filepath, basepath)

  def FindFile(self, filename):
    """Search for <filename> across the search directories, if the path is not
       absolute.  Return the filepath relative to the CWD or None. """
    cache_key = (tuple(self.search_dirs), self.cwd, filename)
    if cache_key in findfile_cache:
      cache_result = findfile_cache[cache_key]
      return cache_result
    result = None
    def isfile(absname):
      res = pathisfile_cache.get(absname)
      if res is None:
        res = self.pathobj.isfile(absname)
        pathisfile_cache[absname] = res
      return res

    if self.pathobj.isabs(filename):
      if isfile(filename):
        result = self.FilenameToRelative(filename)
    else:
      for pathname in self.search_dirs:
        fullname = '%s/%s' % (pathname, filename)
        if isfile(fullname):
          result = self.FilenameToRelative(fullname)
          break
    findfile_cache[cache_key] = result
    return result


def LoadFile(filename):
  # Catch cases where the file does not exist
  try:
    fd = PathConverter().open(filename)
  except IOError:
    DebugPrint('Exception on file: %s' % filename)
    return ''
  # Go ahead and throw if you fail to read
  return fd.read()


scan_cache = {}  # cache (abs_filename -> include_list)


class Scanner(object):
  """Scanner searches for '#include' to find dependencies."""

  def __init__(self, loader=None):
    regex = r'^\s*\#[ \t]*include[ \t]*[<"]([^>"]+)[>"]'
    self.parser = re.compile(regex, re.M)
    self.loader = loader
    if not loader:
      self.loader = LoadFile

  def ScanData(self, data):
    """Generate a list of includes from this text block."""
    return self.parser.findall(data)

  def ScanFile(self, filename):
    """Generate a list of includes from this filename."""
    abs_filename = os.path.abspath(filename)
    if abs_filename in scan_cache:
      return scan_cache[abs_filename]
    includes = self.ScanData(self.loader(filename))
    scan_cache[abs_filename] = includes
    DebugPrint('Source %s contains:\n\t%s' % (filename, '\n\t'.join(includes)))
    return includes


class WorkQueue(object):
  """WorkQueue contains the list of files to be scanned.

  WorkQueue contains provides a queue of files to be processed.  The scanner
  will attempt to push new items into the queue, which will be ignored if the
  item is already in the queue.  If the item is new, it will be added to the
  work list, which is drained by the scanner.
  """
  def __init__(self, resolver, scanner=Scanner()):
    self.added_set = set()
    self.todo_list = list()
    self.scanner = scanner
    self.resolver = resolver

  def PushIfNew(self, filename):
    """Add this dependency to the list of not already there."""
    DebugPrint('Adding %s' % filename)
    resolved_name = self.resolver.FindFile(filename)
    if not resolved_name:
      DebugPrint('Failed to resolve %s' % filename)
      return
    DebugPrint('Resolvd as %s' % resolved_name)
    if resolved_name in self.added_set:
      return
    self.todo_list.append(resolved_name)
    self.added_set.add(resolved_name)

  def PopIfAvail(self):
    """Fetch the next dependency to search."""
    if not self.todo_list:
      return None
    return self.todo_list.pop()

  def Run(self):
    """Search through the available dependencies until the list becomes empty.
      The list must be primed with one or more source files to search."""
    scan_name = self.PopIfAvail()
    while scan_name:
      includes = self.scanner.ScanFile(scan_name)
      # Add the directory of the current scanned file for resolving includes
      # while processing includes for this file.
      scan_dir = PathConverter().dirname(scan_name)
      added_dir = not self.resolver.AddOneDirectory(scan_dir)
      for include_file in includes:
        self.PushIfNew(include_file)
      if added_dir:
        self.resolver.RemoveOneDirectory(scan_dir)
      scan_name = self.PopIfAvail()
    return sorted(self.added_set)


def DoMain(argv):
  """Entry point used by gyp's pymod_do_main feature."""
  global debug

  resolver = Resolver()
  files = []

  arg_type = ''
  for arg in argv:
    if arg in ['-I', '-S']:
      arg_type = arg
    elif arg == '-D':
      debug = True
    elif arg_type == '-I':
      # Skip generated include directories. These files may not exist and
      # there should be explicit dependency on the target that generates
      # these files.
      if arg.startswith('$!PRODUCT_DIR'):
        continue
      resolver.AddDirectories([arg])
    elif arg_type == '-S':
      files.append(arg)

  workQ = WorkQueue(resolver)
  for filename in files:
    workQ.PushIfNew(filename)

  sorted_list = workQ.Run()
  return '\n'.join(sorted_list) + '\n'


def Main():
  result = DoMain(sys.argv[1:])
  sys.stdout.write(result)


if __name__ == '__main__':
  Main()