syzygy/build/gitdeps.py

# Copyright 2014 Google Inc. All Rights Reserved.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""A utility script for checking out subdirectories of many GIT repositories
to specified locations, like is possible with SVN and gclient. This uses a
combination of GIT, sparse-checkout, shallow-clone and filesystem junctions.

For each dependency in a 'gitdeps' file this script will checkout one
subdirectory of one repository into a specified location. The input is as
follows:

- The user specifies a local destination for the checkout.
- The user specifies a source repository.
- The user specifies a list of subdirectories of the repository to get.
- The user specifies a revision.

The checkout works as follows:

- An empty git checkout is initialized in the cache directory. This will be
  in a subfolder with an essentially random name.
- The specified repository is added as a remote to that repo.
- A sparse-checkout directive is added to select only the desired
  subdirectories.
- The repository is cloned using a depth of 1 (no history, only the actual
  contents of the desired revision).
- The destination directories are created as junctions pointing to the
  desired subdirectory of the checkout in the cache directory.

The script maintains its state in the root of the cache directory, allowing it
to reuse checkout directories when possible.
"""

import ast
import glob
import hashlib
import logging
import optparse
import os
import random
import re
import subprocess
import threading


_LOGGER = logging.getLogger(os.path.basename(__file__))


# Matches a SHA1 hash used as a git revision.
_GIT_SHA1_RE = re.compile('^[A-Fa-f0-9]{40}$')


def _ParseCommandLine():
  """Parses the command-line and returns an options structure."""
  option_parser = optparse.OptionParser()
  option_parser.add_option('--cache-dir', type='string',
      default='.gitdeps-cache',
      help='The directory to be used for storing cache files. Defaults to '
           '.gitdeps-cache in the current working directory.')
  option_parser.add_option('--output-dir', type='string', default='.',
      help='The directory to be used as the root of all output. Defaults to '
           'the current working directory.')
  option_parser.add_option('--dry-run', action='store_true', default=False,
      help='If true then will simply list actions that would be performed.')
  option_parser.add_option('--force', action='store_true', default=False,
      help='If true then will force the checkout to be completely rebuilt.')
  option_parser.add_option('--verbose', dest='log_level', action='store_const',
      default=logging.INFO, const=logging.DEBUG,
      help='Enables verbose logging.')
  option_parser.add_option('--quiet', dest='log_level', action='store_const',
      default=logging.INFO, const=logging.ERROR,
      help='Disables all output except for errors.')

  options, args = option_parser.parse_args()

  # Configure logging.
  logging.basicConfig(level=options.log_level)

  # Set default values.
  if not args:
    # Default to checking for a file in the current working directory.
    _LOGGER.info('Defaulting to using GITDEPS in current working directory.')
    args = ['GITDEPS']

  # Validate arguments and options.
  if not os.path.isdir(options.output_dir):
    option_parser.error('Output directory does not exist: %s' %
        options.output_dir)
  for path in args:
    if not os.path.exists(path):
      option_parser.error('Missing dependency file: %s' % path)

  # Normalize local paths for prettier output.
  options.cache_dir = os.path.normpath(os.path.abspath(options.cache_dir))
  options.output_dir = os.path.normpath(os.path.abspath(options.output_dir))

  return options, args


class RepoOptions(object):
  """Light object used for shuttling around information about a dependency."""

  def __init__(self):
    self.repository = None
    self.revision = None
    self.output_dir = None
    self.remote_dirs = []
    self.deps_file = None
    self.checkout_dir = None
    self.recurse = False

  def __str__(self):
    """Stringifies this object for debugging."""
    return ('RepoOptions(repository=%s, revision=%s, output_dir=%s, '
            'remote_dirs=%s, deps_file=%s, checkout_dir=%s, recurse=%s)') % (
                self.repository.__repr__(),
                self.revision.__repr__(),
                self.output_dir.__repr__(),
                self.remote_dirs.__repr__(),
                self.deps_file.__repr__(),
                self.checkout_dir.__repr__(),
                self.recurse.__repr__())


def _ParseRepoOptions(cache_dir, root_output_dir, deps_file_path, key, value):
  """Given the |root_output_dir| specified on the command line, a |key| and
  |value| pair from a GITDEPS file, and the path of the deps file, generates
  a corresponding RepoOptions object. The |key| is the output path of the
  checkout relative to |root_output_dir|, and |value| consists of a
  (repository URL, remote directory, revision hash) tuple. This can raise an
  Exception on failure.
  """
  bad = False
  if ((type(value) != list and type(value) != tuple) or len(value) < 3 or
      len(value) > 4 or (type(value[1]) != list and type(value[1]) != tuple)):
    bad = True
  if len(value) == 4 and type(value[3]) != dict:
    bad = True
  if bad:
    _LOGGER.error('Invalid dependency tuple: %s', value)
    raise Exception()

  # Always use lowercase SHA1 hashes for consistency.
  refspec = value[2]
  if _GIT_SHA1_RE.match(refspec):
    refspec = refspec.lower()

  repo_options = RepoOptions()
  repo_options.output_dir = os.path.normpath(os.path.abspath(os.path.join(
      root_output_dir, key)))
  repo_options.repository = value[0]
  repo_options.remote_dirs = value[1]
  repo_options.revision = refspec
  repo_options.deps_file = deps_file_path

  # Parse additional options.
  if len(value) > 3:
    repo_options.recurse = value[3].get('recurse', False) == True

  # Create a unique name for the checkout in the cache directory. Make the
  # output directory relative to the cache directory so that they can be
  # moved around together.
  output_dir_rel = os.path.relpath(repo_options.output_dir,
                                   root_output_dir).lower()
  if output_dir_rel.startswith('..'):
    raise Exception('Invalid output directory: %s' % key)
  n = hashlib.md5(output_dir_rel).hexdigest()
  repo_options.checkout_dir = os.path.abspath(os.path.join(cache_dir, n, 'src'))

  return repo_options


def _EnsureDirectoryExists(path, comment_name, dry_run):
  """Ensures that the given |path| exists. Only actually creates the directory
  if |dry_run| is False. |comment_name| is used during logging of this
  operation.
  """
  if not comment_name:
    comment_name += ' '
  else:
    comment_name = ''
  if not os.path.exists(path):
    _LOGGER.debug('Creating %sdirectory: %s', comment_name, path)
    if not dry_run:
      os.makedirs(path)


def _GetCasedFilename(filename):
  """Returns the full case-sensitive filename for the given |filename|. If the
  path does not exist, returns the original |filename| as is.
  """
  pattern = '%s[%s]' % (filename[:-1], filename[-1])
  filenames = glob.glob(pattern)
  if not filenames:
    return filename
  return filenames[0]


def _Shell(*cmd, **kw):
  """Runs |cmd|, returns the results from Popen(cmd).communicate(). Additional
  keyword arguments are passed on to subprocess.Popen. If |stdout| and |stderr|
  are not specified, they default to subprocess.PIPE. If |dry_run| is not
  specified it defaults to True. The command is only actually run if |dry_run|
  is False. This can raise a RuntimeError on failure.
  """
  if 'cwd' in kw:
    _LOGGER.debug('Executing %s in "%s".', cmd, kw['cwd'])
  else:
    _LOGGER.debug('Executing %s.', cmd)
  if kw.get('dry_run', True):
    return ('', '')
  kw.pop('dry_run', None)
  dump_on_error = kw.pop('dump_on_error', False)

  kw['shell'] = True
  kw.setdefault('stdout', subprocess.PIPE)
  kw.setdefault('stderr', subprocess.PIPE)
  prog = subprocess.Popen(cmd, **kw)

  stdout, stderr = prog.communicate()
  if prog.returncode != 0:
    if dump_on_error:
      print stdout
      print stderr
    raise RuntimeError('Command "%s" returned %d.' % (cmd, prog.returncode))
  return (stdout, stderr)


def _IsGitCheckoutRoot(path):
  """Return true if the given |path| is the root of a git checkout."""
  return os.path.exists(os.path.join(path, '.git'))


# Matches a GIT config file section header, and grabs the name of the section
# in the first group. Used by _GetGitOrigin.
_GIT_CONFIG_SECTION_RE = re.compile(r'^\s*\[(.*?)\]\s*$')
# Matches the URL line from a 'remote' section of a GIT config. Used by
# _GetGitOrigin.
_GIT_CONFIG_REMOTE_URL_RE = re.compile(r'^\s*url\s*=\s*(.*?)\s*$')


def _GetGitOrigin(path):
  """Returns the URL of the 'origin' remote for the git repo in |path|. Returns
  None if the 'origin' remote doesn't exist. Raises an IOError if |path| doesn't
  exist or is not a git repo.
  """
  section = None
  for line in open(os.path.join(path, '.git', 'config'), 'rb'):
    m = _GIT_CONFIG_SECTION_RE.match(line)
    if m:
      section = m.group(1)
      continue

    # We only care about the 'origin' configuration.
    if section != 'remote "origin"':
      continue

    m = _GIT_CONFIG_REMOTE_URL_RE.match(line)
    if m:
      return m.group(1).strip()

  return None


def _GetGitHead(path):
  """Returns the hash of the head of the git repo in |path|. Raises an IOError
  if |path| doesn't exist or is not a git repo.
  """
  return open(os.path.join(path, '.git', 'HEAD'), 'rb').read().strip()


def _NormalizeGitPath(path):
  """Given a |path| in a GIT repository (relative to its root), normalizes it so
  it will match only that exact path in a sparse checkout.
  """
  path = path.strip()
  if not path.startswith('/'):
    path = '/' + path
  if not path.endswith('/'):
    path += '/'
  return path


def _RenameCheckout(path, dry_run):
  """Renames the checkout in |path| so that it can be subsequently deleted.
  Only actually does the work if |dry_run| is False. Returns the path of the
  renamed checkout directory. Raises an Exception on failure.
  """

  def _RenameCheckoutImpl(path, dry_run):
    if dry_run:
      return path + '-old-dryrun'
    attempts = 0
    while attempts < 10:
      newpath = '%s-old-%04d' % (path, random.randint(0, 999))
      try:
        os.rename(path, newpath)
        return newpath
      except WindowsError:
        attempts += 1
    raise Exception('Unable to rename checkout directory: %s' % path)

  newpath = _RenameCheckoutImpl(path, dry_run)
  _LOGGER.debug('Renamed checkout directory: %s', newpath)
  return newpath


def _DeleteCheckout(path, dry_run):
  """Deletes the checkout in |path|. Only actually deletes the checkout if
  |dry_run| is False.
  """
  _LOGGER.info('Deleting checkout directory: %s', path)
  if dry_run:
    return
  _Shell('rmdir', '/S', '/Q', path, dry_run=False)


def _GenerateSparseCheckoutPathAndContents(repo):
  """Generates the path to the sparse checkout file, and the desired
  contents. Returns a tuple of (path, contents). |repo| is a RepoOptions object.
  """
  sparse_file = os.path.join(repo.checkout_dir, '.git', 'info',
                             'sparse-checkout')
  if not repo.remote_dirs:
    contents = '*\n'
  else:
    contents = ''.join(_NormalizeGitPath(dir) + '\n'
                       for dir in repo.remote_dirs)
  return (sparse_file, contents)


def _HasValidSparseCheckoutConfig(repo):
  """Determines if the GIT repo in |path| has a valid sparse-checkout
  configuration as configured by the RepoOptions |repo|. Returns True or False.
  """
  (sparse_file, contents) = _GenerateSparseCheckoutPathAndContents(repo)
  try:
    if open(sparse_file, 'rb').read() == contents:
      return True
    return False
  except IOError:
    return False


def _CreateCheckout(path, repo, dry_run):
  """Creates a checkout in the provided |path|. The |path| must not already
  exist. Uses the repository configuration from the provided |repo| RepoOptions
  object. Only actually creates the checkout if |dry_run| is false.
  """
  # We expect the directory not to exist, as this is a fresh checkout we are
  # creating.
  if not dry_run:
    if os.path.exists(path):
      raise Exception('Checkout directory already exists: %s' % path)

  _LOGGER.info('Creating checkout directory: %s', path)
  if not dry_run:
    os.makedirs(path)

  _LOGGER.debug('Initializing the checkout.')
  _Shell('git', 'init', cwd=path, dry_run=dry_run)
  _Shell('git', 'remote', 'add', 'origin', repo.repository, cwd=path,
         dry_run=dry_run)
  _Shell('git', 'config', 'core.sparsecheckout', 'true', cwd=path,
         dry_run=dry_run)
  if not dry_run:
    _LOGGER.debug('Creating sparse checkout configuration file for '
                  'directory: %s', repo.remote_dirs)
    if not dry_run:
      (path, contents) = _GenerateSparseCheckoutPathAndContents(repo)
      with open(path, 'wb') as io:
        io.write(contents)


def _UpdateCheckout(path, repo, dry_run):
  """Updates a GIT checkout in |path| by pulling down a specific revision
  from it, as configured by RepoOptions |repo|. Only actually runs if
  |dry_run| is False.
  """
  try:
    # Try a checkout first. If this fails then we'll actually need to fetch
    # the revision.
    _LOGGER.info('Trying to checkout revision %s.', repo.revision)
    _Shell('git', 'checkout', repo.revision, cwd=path,
          dry_run=dry_run)
    return
  except RuntimeError:
    pass

  # Fetch the revision and then check it out. Let output go to screen rather
  # than be buffered.
  _LOGGER.info('Fetching and checking out revision %s.', repo.revision)
  _Shell('git', 'fetch', '--depth=1', 'origin', repo.revision,
         cwd=path, dry_run=dry_run, stdout=None, stderr=None)
  _Shell('git', 'checkout', repo.revision, cwd=path,
         dry_run=dry_run, stdout=None, stderr=None)


# Used by _GetJunctionInfo to extract information about junctions.
_DIR_JUNCTION_RE = re.compile(r'^.*<JUNCTION>\s+(.+)\s+\[(.+)\]$')


# TODO(chrisha): This is ugly, and there has to be a better way!
def _GetJunctionInfo(junction):
  """Returns the target of a junction, if it exists, None otherwise."""
  dirname = os.path.dirname(junction)
  basename = os.path.basename(junction)
  try:
    stdout, dummy_stderr = _Shell('dir', '/AL', '/N', dirname, dry_run=False)
  except RuntimeError:
    return

  lines = stdout.splitlines(False)
  for line in stdout.splitlines(False):
    m = _DIR_JUNCTION_RE.match(line)
    if not m:
      continue
    if m.group(1).lower() == basename.lower():
      return m.group(2)

  return None


def _EnsureJunction(cache_dir, target_dir, options, repo):
  """Ensures that the appropriate junction exists from the configured output
  directory to the specified sub-directory of the GIT checkout.
  """
  # Ensure that the target directory was created.
  target_cache_dir = _GetCasedFilename(os.path.normpath(
      os.path.join(cache_dir, target_dir)))
  if not options.dry_run and not os.path.isdir(target_cache_dir):
    raise Exception('Checkout does not contain the desired remote folder.')

  # Ensure the parent directory exists before checking if the junction needs to
  # be created.
  output_dir = os.path.normpath(os.path.join(repo.output_dir, target_dir))
  _EnsureDirectoryExists(
      os.path.dirname(output_dir), 'junction', options.dry_run)

  # Determine if the link needs to be created.
  create_link = True
  if os.path.exists(output_dir):
    dest = _GetJunctionInfo(output_dir)

    # If the junction is valid nothing needs to be done. If it points to the
    # wrong place or isn't a junction then delete it and let it be remade.
    if dest == target_cache_dir:
      _LOGGER.debug('Junction is up to date.')
      create_link = False
    else:
      if dest:
        _LOGGER.info('Erasing existing junction: %s', output_dir)
      else:
        _LOGGER.info('Deleting existing directory: %s', output_dir)
      _Shell('rmdir', '/S', '/Q', output_dir, dry_run=options.dry_run)

  if create_link:
    _LOGGER.info('Creating output junction: %s', output_dir)
    _Shell('mklink', '/J', output_dir, target_cache_dir,
           dry_run=options.dry_run)


def _InstallRepository(options, repo):
  """Installs a repository as configured by the options. Assumes that the
  specified cache directory already exists.

  Returns True if the checkout was modified, False otherwise.
  """

  _LOGGER.debug('Processing directories "%s" from repository "%s".',
                repo.remote_dirs, repo.repository)

  # Ensure the output directory's *parent* exists.
  output_dirname = os.path.dirname(repo.output_dir)
  output_basename = os.path.basename(repo.output_dir)
  _EnsureDirectoryExists(output_dirname, 'output', options.dry_run)

  # Get the properly cased names for the output directories.
  output_dirname = _GetCasedFilename(output_dirname)
  repo.output_dir = os.path.join(output_dirname, output_basename)

  # These are the 3 basic steps that need to occur. Depending on the state of
  # the checkout we may not need to perform all of them. We assume initially
  # that everything needs to be done, unless proven otherwise.
  create_checkout = True
  update_checkout = True

  # If the cache directory exists then lookup the repo and the revision and see
  # what needs to be updated.
  threads = []
  if os.path.exists(repo.checkout_dir):
    keep_cache_dir = False

    # Only run these checks if we're not in 'force' mode. Otherwise, we
    # deliberately turf the cache directory and start from scratch.
    if not options.force and _IsGitCheckoutRoot(repo.checkout_dir):
      # Get the repo origin.
      repo_url = _GetGitOrigin(repo.checkout_dir)
      if (repo_url == repo.repository and
          _HasValidSparseCheckoutConfig(repo)):
        _LOGGER.debug('Checkout is for correct repository and subdirectory.')
        keep_cache_dir = True
        create_checkout = False

        # Get the checked out revision.
        revhash = _GetGitHead(repo.checkout_dir)
        if revhash == repo.revision:
          _LOGGER.debug('Checkout is already up to date.')
          update_checkout = False

    if not keep_cache_dir:
      # The old checkout directory is renamed and erased in a separate thread
      # so that the new checkout can start immediately.
      _LOGGER.info('Erasing stale checkout directory: %s', repo.checkout_dir)

      # Any existing junctions to this repo must be removed otherwise the
      # rename may fail.
      for d in repo.remote_dirs:
        j = os.path.abspath(os.path.join(repo.output_dir, d))
        _RemoveOrphanedJunction(options, j)

      newpath = _RenameCheckout(repo.checkout_dir, options.dry_run)
      thread = threading.Thread(target=_DeleteCheckout,
                                args=(newpath, options.dry_run))
      threads.append(thread)
      thread.start()

  # Create and update the checkout as necessary.
  if create_checkout:
    _CreateCheckout(repo.checkout_dir, repo, options.dry_run)
  else:
    _LOGGER.debug('Reusing checkout directory: %s', repo.checkout_dir)
  if update_checkout:
    _UpdateCheckout(repo.checkout_dir, repo, options.dry_run)

  # Ensure the junctions exists.
  if repo.remote_dirs:
    for remote_dir in repo.remote_dirs:
      _EnsureJunction(repo.checkout_dir, remote_dir, options, repo)
  else:
    _EnsureJunction(repo.checkout_dir, '', options, repo)

  # Join any worker threads that are ongoing.
  for thread in threads:
    thread.join()

  # Return True if any modifications were made.
  return create_checkout or update_checkout


def _WriteIfChanged(path, contents, dry_run):
  if os.path.exists(path):
    d = open(path, 'rb').read()
    if d == contents:
      _LOGGER.debug('Contents unchanged, not writing file: %s', path)
      return

  _LOGGER.info('Writing file: %s', path)
  if not dry_run:
    open(path, 'wb').write(contents)


def _RecurseRepository(options, repo):
  """Recursively follows dependencies in the given repository."""
  # Only run if there's an appropriate DEPS file.
  deps = os.path.isfile(os.path.join(repo.checkout_dir, 'DEPS'))
  gitdeps = os.path.isfile(os.path.join(repo.checkout_dir, '.DEPS.git'))
  if not deps and not gitdeps:
    _LOGGER.debug('No deps file found in repository: %s', repo.repository)
    return

  # Generate the .gclient solution file.
  cache_dir = os.path.dirname(os.path.abspath(repo.checkout_dir))
  gclient_file = os.path.join(cache_dir, '.gclient')
  deps_file = 'DEPS'
  if gitdeps:
    deps_file = '.DEPS.git'
  solutions = [
    {
      'name': 'src',
      'url': repo.repository,
      'managed': False,
      'custom_deps': [],
      'deps_file': deps_file,
      'safesync_url': '',
    }
  ]
  solutions = 'solutions=%s' % solutions.__repr__()
  _WriteIfChanged(gclient_file, solutions, options.dry_run)

  # Invoke 'gclient' on the sub-repository.
  _Shell('gclient', 'sync', cwd=repo.checkout_dir, dry_run=options.dry_run)


def _FindGlobalVariableInAstTree(tree, name, functions=None):
  """Finds and evaluates to global assignment of the variables |name| in the
  AST |tree|. Will allow the evaluations of some functions as defined in
  |functions|.
  """
  if functions is None:
    functions = {}

  class FunctionEvaluator(ast.NodeTransformer):
    """A tree transformer that evaluates permitted functions."""

    def visit_BinOp(self, binop_node):
      """Is called for BinOp nodes. We only support string additions."""
      if type(binop_node.op) != ast.Add:
        return binop_node
      left = ast.literal_eval(self.visit(binop_node.left))
      right = ast.literal_eval(self.visit(binop_node.right))
      value = left + right
      new_node = ast.Str(s=value)
      new_node = ast.copy_location(new_node, binop_node)
      return new_node

    def visit_Call(self, call_node):
      """Evaluates function calls that return a single string as output."""
      func_name = call_node.func.id
      if func_name not in functions:
        return call_node
      func = functions[func_name]

      # Evaluate the arguments. We don't care about starargs, keywords or
      # kwargs.
      args = [ast.literal_eval(self.visit(arg)) for arg in
                  call_node.args]

      # Now evaluate the function.
      value = func(*args)
      new_node = ast.Str(s=value)
      new_node = ast.copy_location(new_node, call_node)
      return new_node

  # Look for assignment nodes.
  for node in tree.body:
    if type(node) != ast.Assign:
      continue
    # Look for assignment in the 'store' context, to a variable with
    # the given name.
    for target in node.targets:
      if type(target) != ast.Name:
        continue
      if type(target.ctx) != ast.Store:
        continue
      if target.id == name:
        value = FunctionEvaluator().visit(node.value)
        value = ast.fix_missing_locations(value)
        value = ast.literal_eval(value)
        return value


def _ParseDepsFile(path):
  """Parsed a DEPS-like file at the given |path|."""
  # Utility function for performing variable expansions.
  vars_dict = {}
  def _Var(s):
    return vars_dict[s]

  contents = open(path, 'rb').read()
  tree = ast.parse(contents, path)
  vars_dict = _FindGlobalVariableInAstTree(tree, 'vars')
  deps_dict = _FindGlobalVariableInAstTree(
      tree, 'deps', functions={'Var': _Var})
  return deps_dict


def _RemoveFile(options, path):
  """Removes the provided file. If it doesn't exist, raises an Exception."""
  _LOGGER.debug('Removing file: %s', path)
  if not os.path.isfile(path):
    raise Exception('Path does not exist: %s' % path)

  if not options.dry_run:
    os.remove(path)


def _RemoveOrphanedJunction(options, junction):
  """Removes an orphaned junction at the path |junction|. If the path doesn't
  exist or is not a junction, raises an Exception.
  """
  _LOGGER.debug('Removing orphaned junction: %s', junction)
  absdir = os.path.join(options.output_dir, junction)
  if not os.path.exists(absdir):
    _LOGGER.debug('Junction path does not exist, ignoring.')
    return
  if not _GetJunctionInfo(absdir):
    _LOGGER.error('Path is not a junction: %s', absdir)
    raise Exception()
  _Shell('rmdir', '/S', '/Q', absdir, dry_run=options.dry_run)

  reldir = os.path.dirname(junction)
  while reldir:
    absdir = os.path.join(options.output_dir, reldir)
    if os.listdir(absdir):
      return
    _LOGGER.debug('Removing empty parent directory of junction: %s', absdir)
    _Shell('rmdir', '/S', '/Q', absdir, dry_run=options.dry_run)
    reldir = os.path.dirname(reldir)


def _GetCacheDirEntryVersion(path):
  """Returns the version of the cache directory entry, -1 if invalid."""

  git = os.path.join(path, '.git')
  src = os.path.join(path, 'src')
  gclient = os.path.join(path, '.gclient')

  # Version 0 contains a '.git' directory and no '.gclient' entry.
  if os.path.isdir(git):
    if os.path.exists(gclient):
      return -1
    return 0

  # Version 1 contains a 'src' directory and no '.git' entry.
  if os.path.isdir(src):
    if os.path.exists(git):
      return -1
    return 1


def _GetCacheDirEntries(cache_dir):
  """Returns the list of entries in the given |cache_dir|."""
  entries = []
  for path in os.listdir(cache_dir):
    if not re.match('^[a-z0-9]{32}$', path):
      continue
    entries.append(path)
  return entries


def _GetCacheDirVersion(cache_dir):
  """Returns the version of the cache directory."""
  # If it doesn't exist then it's clearly the latest version.
  if not os.path.exists(cache_dir):
    return 1

  cache_version = None
  for path in _GetCacheDirEntries(cache_dir):
    repo = os.path.join(cache_dir, path)
    if not os.path.isdir(repo):
      return -1

    entry_version = _GetCacheDirEntryVersion(repo)
    if entry_version == -1:
      return -1

    if cache_version == None:
      cache_version = entry_version
    else:
      if cache_version != entry_version:
        return -1

  # If there are no entries in the cache it may as well be the latest version.
  if cache_version is None:
    return 1

  return cache_version


def _GetJunctionStatePath(options):
  """Returns the junction state file path."""
  return os.path.join(options.cache_dir, '.gitdeps_junctions')


def _ReadJunctions(options):
  """Reads the list of junctions as a dictionary."""
  state_path = _GetJunctionStatePath(options)
  old_junctions = {}
  if os.path.exists(state_path):
    _LOGGER.debug('Loading list of existing junctions.')
    for j in open(state_path, 'rb'):
      old_junctions[j.strip()] = True

  return old_junctions


def _Rename(src, dst, dry_run):
  _LOGGER.debug('Renaming "%s" to "%s".', src, dst)
  if not dry_run:
    os.rename(src, dst)


def _UpgradeCacheDir(options):
  """Upgrades the cache directory format to the most modern layout.

  Returns true on success, false otherwise.
  """
  cache_version = _GetCacheDirVersion(options.cache_dir)
  if cache_version == 1:
    _LOGGER.debug('No cache directory upgrade required.')
    return

  _LOGGER.debug('Upgrading cache directory from version 0 to 1.')

  _LOGGER.debug('Removing all junctions.')
  junctions = _ReadJunctions(options).keys()
  junctions = sorted(junctions, key=lambda j: len(j), reverse=True)
  for junction in junctions:
    _RemoveOrphanedJunction(options, junction)
  _RemoveFile(options, _GetJunctionStatePath(options))

  for entry in _GetCacheDirEntries(options.cache_dir):
    _LOGGER.debug('Upgrading cache entry "%s".', entry)
    tmp_entry = os.path.abspath(os.path.join(
        options.cache_dir,
        'TMP%d-%04d' % (os.getpid(), random.randint(0, 999))))
    abs_entry = os.path.abspath(os.path.join(options.cache_dir, entry))
    src = os.path.join(abs_entry, 'src')
    _Rename(abs_entry, tmp_entry, options.dry_run)
    _EnsureDirectoryExists(abs_entry, 'cache entry', options.dry_run)
    _Rename(tmp_entry, src, options.dry_run)

  if options.dry_run:
    _LOGGER.debug('Cache needs upgrading, unable to further simulate dry-run.')
    raise Exception("")


def main():
  options, args = _ParseCommandLine()

  # Upgrade the cache directory if necessary.
  _UpgradeCacheDir(options)

  # Ensure the cache directory exists and get the full properly cased path to
  # it.
  _EnsureDirectoryExists(options.cache_dir, 'cache', options.dry_run)
  options.cache_dir = _GetCasedFilename(options.cache_dir)

  # Read junctions that have been written in previous runs.
  state_path = _GetJunctionStatePath(options)
  old_junctions = _ReadJunctions(options)

  # Parse each deps file in order, and extract the dependencies, looking for
  # conflicts in the output directories.
  output_dirs = {}
  all_deps = []
  for deps_file in args:
    deps = _ParseDepsFile(deps_file)
    for key, value in deps.iteritems():
      repo_options = _ParseRepoOptions(
          options.cache_dir, options.output_dir, deps_file, key, value)
      if repo_options.output_dir in output_dirs:
        other_repo_options = output_dirs[repo_options.output_dir]
        _LOGGER.error('Conflicting output directory: %s',
                      repo_options.output_dir)
        _LOGGER.error('First specified in file: %s',
                      other_repo_options.deps_file)
        _LOGGER.error('And then specified in file: %s', repo_options.deps_file)
      output_dirs[repo_options.output_dir] = repo_options
      all_deps.append(repo_options)
  output_dirs = {}

  # Handle each dependency, in order of shortest path names first. This ensures
  # that nested dependencies are handled properly.
  checkout_dirs = {}
  deps = sorted(all_deps, key=lambda x: len(x.deps_file))
  junctions = []
  for repo in all_deps:
    changes_made = _InstallRepository(options, repo)
    checkout_dirs[repo.checkout_dir] = changes_made

    new_junction_dirs = repo.remote_dirs if repo.remote_dirs else ['']
    for new_junction_dir in new_junction_dirs:
      junction = os.path.relpath(
          os.path.join(repo.output_dir, new_junction_dir),
          options.output_dir)
      old_junctions.pop(junction, None)
      # Write each junction as we create it. This allows for recovery from
      # partial runs.
      if not options.dry_run:
        open(state_path, 'ab').write(junction + '\n')
        junctions.append(junction)

  # Clean up orphaned junctions if there are any.
  if old_junctions:
    _LOGGER.debug('Removing orphaned junctions.')
    for j in old_junctions.iterkeys():
      _RemoveOrphanedJunction(options, j)

  # Output the final list of junctions.
  _LOGGER.debug('Writing final list of junctions.')
  if not options.dry_run:
    with open(state_path, 'wb') as io:
      for j in sorted(junctions):
        io.write(j)
        io.write('\n')

  # Iterate all directories in the cache directory. Any that we didn't
  # specifically create or update should be cleaned up. Do this in parallel
  # so things are cleaned up as soon as possible.
  threads = []
  for path in glob.glob(os.path.join(options.cache_dir, '*')):
    if os.path.join(path, 'src') not in checkout_dirs:
      _LOGGER.debug('Erasing orphaned checkout directory: %s', path)
      thread = threading.Thread(target=_DeleteCheckout,
                                args=(path, options.dry_run))
      threads.append(thread)
      thread.start()
  for thread in threads:
    thread.join()

  # Recursively process other dependencies.
  for repo in all_deps:
    if not repo.recurse:
      continue
    if not checkout_dirs[repo.checkout_dir] and not options.force:
      continue
    _RecurseRepository(options, repo)

  return


if __name__ == '__main__':
  main()