#!/usr/bin/env python

import codecs, re, subprocess, sys
from os import path

def isFiles(k):
  return any(map(k.endswith, [
    '_DATA',
    '_HEADERS',
    '_JAVA',
    '_LIBRARIES',
    '_LISP',
    '_LTLIBRARIES',
    '_MANS',
    '_PROGRAMS',
    '_PYTHON',
    '_SCRIPTS',
    '_SOURCES',
    '_TEXINFOS']))

def isDist(k):
  return any(map(k.endswith, [
    '_HEADERS',
    '_SOURCES']))

def key(filename):

  parts = filename.split('/')
  for i in range(len(parts)):

    filename = parts[i].lower()
    stem, extension = path.splitext(filename)

    stem = stem.replace('.', '').split('_')
    parts[i] = ''.join(filter(lambda word: len(word) > 1, stem)), extension, filter(lambda word: len(word) == 1, stem)

  parts.insert(-1, ())

  return parts

class Definition:
  def __init__(ctx, automakeFile, conditional, comment, k, operator, v, after):

    ctx.automakeFile = automakeFile
    ctx.conditional = conditional
    ctx.comment = comment
    ctx.k = k
    ctx.operator = operator
    ctx.v = v
    ctx.after = after

  def updateSubdirs(ctx):
    v = ctx.v

    v = v.replace('\\\n', '')
    v = v.replace('\\#', '#')

    ctx.parts = re.compile('(?<![^\t ])(\$\(.+?\))(?![^\t ])').split(v)

    union = set()
    for variable in ctx.parts[1::2]:

      k = variable[2:-1]
      if k in ctx.automakeFile.variables:
        for definition in ctx.automakeFile.variables[k]:
          union |= definition.updateSubdirs()

    prefixes = set(filename + '/' for filename in union)
    union.update(ctx.parts[1::2])

    for i in reversed(range(0, len(ctx.parts), 2)):

      subParts = []
      for original in ctx.parts[i].split():

        expanded = ctx.automakeFile.expand(original)
        filename = path.join(path.dirname(ctx.automakeFile.filename), expanded).lstrip('/')

        if filename + '/' not in prefixes and not any(map(filename.startswith, prefixes)):

          union.add(filename)
          prefixes.add(filename + '/')

          subParts.append(original)

      ctx.parts[i:i + 1] = subParts

    return union

  def updateFiles(ctx, files):
    v = ctx.v

    v = v.replace('\\\n', '')
    v = v.replace('\\#', '#')

    ctx.parts = re.compile('(?<![^\t ])(\$\(.+?\))(?![^\t ])').split(v)

    union = set()
    for variable in ctx.parts[1::2]:

      k = variable[2:-1]
      if k in ctx.automakeFile.variables:
        for definition in ctx.automakeFile.variables[k]:
          union |= definition.updateFiles(files)

    prefixes = set(filename + '/' for filename in union)
    union.update(ctx.parts[1::2])

    for i in reversed(range(0, len(ctx.parts), 2)):

      subParts = []
      for original in ctx.parts[i].split():

        expanded = ctx.automakeFile.expand(original)
        filename = path.join(path.dirname(ctx.automakeFile.filename), expanded).lstrip('/')

        if filename + '/' not in prefixes and (not any(map(filename.startswith, prefixes)) if filename in files else re.compile('[^0-9@A-Z_a-z]').sub('_', expanded) + '_SOURCES' in ctx.automakeFile.variables or expanded in ctx.automakeFile.targets):

          union.add(filename)
          prefixes.add(filename + '/')

          subParts.append(original)

      ctx.parts[i:i + 1] = subParts

    #ctx.parts.sort(key=key)

    return union

  def updateExtra(ctx, files):
    v = ctx.v

    v = v.replace('\\\n', '')
    v = v.replace('\\#', '#')

    ctx.parts = re.compile('(?<![^\t ])(\$\(.+?\))(?![^\t ])').split(v)

    union = set()
    for variable in ctx.parts[1::2]:

      k = variable[2:-1]
      if not isFiles(k) and k in ctx.automakeFile.variables:
        for definition in ctx.automakeFile.variables[k]:
          union |= definition.updateFiles(files)

    prefixes = set(filename + '/' for filename in union)
    union.update(ctx.parts[1::2])

    for i in reversed(range(len(ctx.parts))):
      if i % 2:

        k = ctx.parts[i][2:-1]
        if isFiles(k):
          del ctx.parts[i]

      else:

        subParts = []
        for original in ctx.parts[i].split():

          expanded = ctx.automakeFile.expand(original)
          filename = path.join(path.dirname(ctx.automakeFile.filename), expanded).lstrip('/')

          if filename + '/' not in prefixes and (not any(map(filename.startswith, prefixes)) if filename in files else re.compile('[^0-9@A-Z_a-z]').sub('_', expanded) + '_SOURCES' in ctx.automakeFile.variables or expanded in ctx.automakeFile.targets):

            union.add(filename)
            prefixes.add(filename + '/')

            subParts.append(original)

        ctx.parts[i:i + 1] = subParts

    return union

  def output(ctx):

    comment = ctx.comment
    v = ctx.v

    newline = ' \\\n' + '  ' * (ctx.conditional + 1)
    if hasattr(ctx, 'parts'):# or not any(map(ctx.k.endswith, ['FLAGS', '_LDADD', '_LIBADD'])) and not v.startswith('`'):
      if hasattr(ctx, 'parts'):
        v = ctx.parts

      else:

        v = v.replace('\\\n', '')
        v = re.compile('[\t ]+').sub(' ', ' ' + v)
        v = re.compile('-[^\t ]*[\t ]+[^\t -][^\t ]*|[^\t ]+').findall(v)

      #if len(v) > 1:
      if v and '\\\n' in ctx.v if ctx.v else len(v) > 1:
        v = newline + newline.join(v)

        #comment = '\n' + comment
        #v += '\n'

      elif v:

        #v, = v
        #v = ' ' + v
        v = ' ' + ' '.join(v)

      elif ctx.k == 'EXTRA_DIST':
        return comment

      else:
        v = ''

    elif v:
      #if v.startswith('\\\n'):
      #  if '\\\n' not in v[2:]:
      #    v = v[2:]

      v = re.compile('[\t ]+').sub(' ', ' ' + v).rstrip()
      v = re.compile('[\t ]*\\\\\n[\t ]*').sub(newline, v)

    if ctx.after:
      v += '\n'

    return comment + '  ' * ctx.conditional + ctx.k + ' ' + ctx.operator + v

class Rule:
  def __init__(ctx, comment, targets, colon, prerequisites, recipe, after):

    ctx.comment = comment
    ctx.targets = targets
    ctx.colon = colon
    ctx.prerequisites = prerequisites
    ctx.recipe = recipe
    ctx.after = after

  def output(ctx):

    comment = ctx.comment
    prerequisites = ctx.prerequisites
    recipe = ctx.recipe

    if prerequisites:
      prerequisites = ' ' + prerequisites

    comment = '\n' + comment

    if ctx.after:
      recipe += '\n'

    return comment + ' '.join(ctx.targets) + ctx.colon + prerequisites + recipe

class Directive:
  def __init__(ctx, conditional, comment, directive, after):

    ctx.conditional = conditional
    ctx.comment = comment
    ctx.directive = directive
    ctx.after = after

  def output(ctx):
    directive = ' '.join(ctx.directive)

    if ctx.after:
      directive += '\n'

    return ctx.comment + '  ' * ctx.conditional + directive

class AutomakeFile:
  def __init__(ctx, filename):
    ctx.filename = filename

    contents = codecs.open(ctx.filename + '.am', 'r', 'utf-8').read()
    ctx.parts = re.compile('''
      \A((?:\#.*\\n)*) # Header
      |
      ((?:[\t ]*\#[\t ].*\\n+)*) # Comment
      ^
      (?:
        [\t ]*([0-9A-Z_a-z]+)[\t ]*(\+?=)[\t ]*(.*(?:(?<=\\\)\\n.*)*) # Definition
        |
        ([- $().0-9A-Z_a-z]+)[\t ]*(::?)[\t ]*(.*)((?:\\n+\\t.*)*) # Rule
        |
        (.+) # Directive
      )
      (\\n\\n)? # After''',
      re.MULTILINE | re.VERBOSE).findall(contents)

    ctx.header, _, _, _, _, _, _, _, _, _, _ = ctx.parts.pop(0)

    ctx.variables = {}
    ctx.targets = set()

    conditional = 0
    for i in range(len(ctx.parts)):

      _, comment, k, operator, v, targets, colon, prerequisites, recipe, directive, after = ctx.parts[i]
      if k:
        v = re.compile('\${(.+?)}').sub('$(\\1)', v)

        definition = ctx.parts[i] = Definition(
          ctx,
          conditional,
          comment,
          k,
          operator,
          v,
          after)

        if k.startswith('dist_'):
          k = k[5:]

        if k in ctx.variables:
          ctx.variables[k].append(definition)

        else:
          ctx.variables[k] = [definition]

      elif targets:
        targets = targets.split()

        ctx.parts[i] = Rule(
          comment,
          targets,
          colon,
          prerequisites,
          recipe,
          after)

        ctx.targets.update(targets)

      else:

        directive = directive.split(None, 1)
        if directive[0] == 'endif':
          conditional -= 1

        ctx.parts[i] = Directive(
          conditional,
          comment,
          directive,
          after)

        if directive[0] == 'else':
          ctx.parts[i].conditional -= 1

        elif directive[0] == 'if':
          conditional += 1

        elif directive[0] == 'include':

          filename, = directive[1:]
          allExtra.discard(path.join(path.dirname(ctx.filename), ctx.expand(filename)).lstrip('/'))

    for k in 'SUBDIRS', 'DIST_SUBDIRS':
      if k in ctx.variables:

        union = set()
        for definition in ctx.variables[k]:
          union |= definition.updateSubdirs()

    disconnectedSubdirs = allSubdirs[ctx.filename] = set([ctx])
    if 'SUBDIRS' in ctx.variables or 'DIST_SUBDIRS' in ctx.variables:
      for filename in union:

        filename = path.join(filename, 'Makefile')
        if filename in configFiles and filename + '.am' in files:
          if filename not in allSubdirs:
            AutomakeFile(filename)

          for automakeFile in allSubdirs[filename]:

            disconnectedSubdirs |= allSubdirs[automakeFile.filename]
            allSubdirs[automakeFile.filename] = disconnectedSubdirs

  def repl(ctx, match):

    k = match.group(0)[2:-1]
    if k == 'top_srcdir':
      return

    definition, = ctx.variables[k]
    definition.v = path.normpath(definition.v)

    return ctx.expand(definition.v)

  def expand(ctx, original):
    return re.compile('\$\(.+?\)').sub(ctx.repl, original)

  def update(ctx):
    for k in ctx.variables:
      if isFiles(k):
        for definition in ctx.variables[k]:
          union = definition.updateFiles(files)

          if isDist(k) or union and not union.isdisjoint(allExtra):
            if not isDist(k):
              definition.k = 'dist_' + k

            disconnectedExtra.difference_update(union)

  def output(ctx):

    prefixes = [path.dirname(automakeFile.filename) + '/' for automakeFile in disconnectedSubdirs]
    if path.dirname(ctx.filename):
      prefixes = filter(lambda filename: len(filename) > len(path.dirname(ctx.filename)) + 1 and filename.startswith(path.dirname(ctx.filename) + '/'), prefixes)

    myExtra = set(filter(lambda filename: (not path.dirname(ctx.filename) or filename.startswith(path.dirname(ctx.filename) + '/')) and not any(map(filename.startswith, prefixes)), disconnectedExtra))
    if 'EXTRA_DIST' in ctx.variables:

      union = set()
      for definition in ctx.variables['EXTRA_DIST']:
        union |= definition.updateExtra(myExtra)

      myExtra -= union

    if path.dirname(ctx.filename):
      myExtra = set(filename[len(path.dirname(ctx.filename)) + 1:] for filename in myExtra)

    if 'EXTRA_DIST' in ctx.variables:

      unconditional = filter(lambda definition: not definition.conditional, ctx.variables['EXTRA_DIST'])
      if unconditional:

        definition, = unconditional
        definition.parts += myExtra

    if 'EXTRA_DIST' not in ctx.variables or not unconditional:

      definition = Definition(
        ctx,
        0,
        '',
        'EXTRA_DIST',
        '=',
        None,
        True)
      definition.parts = myExtra

      ctx.parts.insert(0, definition)
      ctx.variables['EXTRA_DIST'] = [definition]

    for definition in ctx.variables['EXTRA_DIST']:

      parts = {}
      for filename in definition.parts:

        dirname = filename.split('/', 1)[0]
        if dirname in parts:
          parts[dirname].append(filename)

        else:
          parts[dirname] = [filename]

      for dirname in parts:
        if len(parts[dirname]) > 1:
          parts[dirname] = path.dirname(path.commonprefix(parts[dirname])) + '/'

        else:

          parts[dirname], = parts[dirname]
          if parts[dirname].endswith('/.gitignore'):
            parts[dirname] = parts[dirname][:-10]

      parts = parts.values()
      parts.sort(key=key)
      parts = map(path.normpath, parts)

      definition.parts = parts

    contents = ctx.header + '\n' + '\n'.join(piece.output() for piece in ctx.parts)
    contents = re.compile('\n{2,}').sub('\n\n', contents).rstrip() + '\n'

    return contents

nodist, = sys.argv[1:]

stdout, _ = subprocess.Popen(['git', 'ls-files'], stdout=subprocess.PIPE).communicate()
files = set(stdout.splitlines())

contents = codecs.open(nodist, 'r', 'utf-8').read()
contents = re.compile('#.*').sub('', contents)
nodist = contents.splitlines()

prefixes = set(filename.lstrip('/') + '/' for filename in nodist if '/' in filename)

stdout, _ = subprocess.Popen(['automake', '--help'], stdout=subprocess.PIPE).communicate()
match = re.compile('(?<=Files which are automatically distributed, if found:)(?:\n .+)+').search(stdout)

nodist = set(filter(lambda filename: '/' not in filename, nodist) + match.group(0).split())

allExtra = set(filter(lambda filename: path.basename(filename) not in nodist and filename + '/' not in prefixes and not any(map(filename.startswith, prefixes)), files))

contents = codecs.open('configure.ac', 'r', 'utf-8').read()

configFiles = re.compile('\\bAC_CONFIG_FILES\(\[(.+?)]\)', re.DOTALL).findall(contents)
configFiles = set('\n'.join(configFiles).split())

allExtra.difference_update(filename + '.in' for filename in configFiles)
allExtra.difference_update(filename + '.am' for filename in configFiles)

match = re.compile('\\bAC_CONFIG_MACRO_DIR\(\[(.+?)]\)').search(contents)

contents, _ = subprocess.Popen(['aclocal', '-I', match.group(1), '--output', '-'], stdout=subprocess.PIPE).communicate()
allExtra.difference_update(re.compile('\\bm4_include\(\[(.+?)]\)').findall(contents))

allSubdirs = {}
for filename in configFiles:
  if filename not in allSubdirs and filename + '.am' in files:
    AutomakeFile(filename)

files |= configFiles

while allSubdirs:

  disconnectedSubdirs = allSubdirs.values()[0]
  for automakeFile in disconnectedSubdirs:
    del allSubdirs[automakeFile.filename]

  disconnectedExtra = set(allExtra)
  map(AutomakeFile.update, disconnectedSubdirs)

  for automakeFile in disconnectedSubdirs:

    contents = automakeFile.output()
    codecs.open(automakeFile.filename + '.am', 'w', 'utf-8').write(contents)