def compute_classpath_entries(cls, targets, classpath_products, extra_classpath_tuples, confs):
    """Return the list of classpath entries for a classpath covering the passed targets.

    Filters and adds paths from extra_classpath_tuples to the end of the resulting list.

    :param targets: The targets to generate a classpath for.
    :param ClasspathProducts classpath_products: Product containing classpath elements.
    :param extra_classpath_tuples: Additional classpath entries as tuples of
      (string, ClasspathEntry).
    :param confs: The list of confs for use by this classpath.
    :returns: The classpath entries as a list of path elements.
    :rtype: list of ClasspathEntry
    """
    classpath_iter = cls._classpath_iter(
      classpath_products.get_classpath_entries_for_targets(targets),
      confs=confs,
    )
    total_classpath = OrderedSet(classpath_iter)

    filtered_extra_classpath_iter = cls._filtered_classpath_by_confs_iter(
      extra_classpath_tuples,
      confs,
    )
    extra_classpath_iter = cls._entries_iter(filtered_extra_classpath_iter)
    total_classpath.update(extra_classpath_iter)
    return list(total_classpath)

 def get_jars_for_ivy_module(self, jar):
   ref = IvyModuleRef(jar.org, jar.name, jar.rev)
   deps = OrderedSet()
   for dep in self.deps_by_caller.get(ref, []):
     deps.add(dep)
     deps.update(self.get_jars_for_ivy_module(dep))
   return deps

  def execute_codegen(self, target, target_workdir):
    sources_by_base = self._calculate_sources(target)
    sources = target.sources_relative_to_buildroot()

    bases = OrderedSet(sources_by_base.keys())
    bases.update(self._proto_path_imports([target]))

    gen_flag = '--java_out'

    gen = '{0}={1}'.format(gen_flag, target_workdir)

    args = [self.protobuf_binary, gen]

    if self.plugins:
      for plugin in self.plugins:
        args.append("--{0}_out={1}".format(plugin, target_workdir))

    for base in bases:
      args.append('--proto_path={0}'.format(base))

    args.extend(sources)

    # Tack on extra path entries. These can be used to find protoc plugins
    protoc_environ = os.environ.copy()
    if self._extra_paths:
      protoc_environ['PATH'] = os.pathsep.join(self._extra_paths
                                               + protoc_environ['PATH'].split(os.pathsep))

    self.context.log.debug('Executing: {0}'.format('\\\n  '.join(args)))
    process = subprocess.Popen(args, env=protoc_environ)
    result = process.wait()
    if result != 0:
      raise TaskError('{0} ... exited non-zero ({1})'.format(self.protobuf_binary, result))

  def to_jar_dependencies(relative_to, jar_library_specs, build_graph):
    """Convenience method to resolve a list of specs to JarLibraries and return its jars attributes.

    Expects that the jar_libraries are declared relative to this target.

    :API: public

    :param Address relative_to: address target that references jar_library_specs, for
      error messages
    :param list jar_library_specs: string specs to JavaLibrary targets. Note, this list should be returned
      by the caller's traversable_specs() implementation to make sure that the jar_dependency jars
      have been added to the build graph.
    :param BuildGraph build_graph: build graph instance used to search for specs
    :return: list of JarDependency instances represented by the library_specs
    """
    jar_deps = OrderedSet()
    for spec in jar_library_specs:
      if not isinstance(spec, string_types):
        raise JarLibrary.ExpectedAddressError(
          "{address}: expected imports to contain string addresses, got {found_class}."
          .format(address=relative_to.spec,
                  found_class=type(spec).__name__))

      lookup = Address.parse(spec, relative_to=relative_to.spec_path)
      target = build_graph.get_target(lookup)
      if not isinstance(target, JarLibrary):
        raise JarLibrary.WrongTargetTypeError(
          "{address}: expected {spec} to be jar_library target type, got {found_class}"
          .format(address=relative_to.spec,
                  spec=spec,
                  found_class=type(target).__name__))
      jar_deps.update(target.jar_dependencies)

    return list(jar_deps)

 def _create_java_target(self, target, dependees):
   genfiles = []
   for source in target.sources_relative_to_source_root():
     path = os.path.join(target.target_base, source)
     genfiles.extend(self.calculate_genfiles(path, source).get('java', []))
   spec_path = os.path.relpath(self.java_out, get_buildroot())
   address = SyntheticAddress(spec_path, target.id)
   deps = OrderedSet(self.javadeps)
   import_jars = target.imported_jars
   jars_tgt = self.context.add_new_target(SyntheticAddress(spec_path, target.id+str('-rjars')),
                                          JarLibrary,
                                          jars=import_jars,
                                          derived_from=target)
   # Add in the 'spec-rjars' target, which contains all the JarDependency targets passed in via the
   # imports parameter. Each of these jars is expected to contain .proto files bundled together
   # with their .class files.
   deps.add(jars_tgt)
   tgt = self.context.add_new_target(address,
                                     JavaLibrary,
                                     derived_from=target,
                                     sources=genfiles,
                                     provides=target.provides,
                                     dependencies=deps,
                                     excludes=target.payload.get_field_value('excludes'))
   for dependee in dependees:
     dependee.inject_dependency(tgt.address)
   return tgt

  def ancestors(self):
    """Returns all BUILD files in ancestor directories of this BUILD file's parent directory."""

    def find_parent(dir):
      parent = os.path.dirname(dir)
      for parent_buildfile in BuildFile._get_all_build_files(parent):
        buildfile = os.path.join(parent, parent_buildfile)
        if os.path.exists(buildfile) and not os.path.isdir(buildfile):
          return parent, BuildFile.from_cache(self.root_dir,
                                              os.path.relpath(buildfile, self.root_dir))
      return parent, None

    parent_buildfiles = OrderedSet()

    def is_root(path):
      return os.path.abspath(self.root_dir) == os.path.abspath(path)

    parentdir = os.path.dirname(self.full_path)
    visited = set()
    while parentdir not in visited and not is_root(parentdir):
      visited.add(parentdir)
      parentdir, buildfile = find_parent(parentdir)
      if buildfile:
        parent_buildfiles.update(buildfile.family())

    return parent_buildfiles

  def execute(self):
    targets = self.context.targets()
    for conf in self.confs:
      outpath = os.path.join(self.workdir, '%s.%s.provides' %
                             (self.ivy_utils.identify(targets)[1], conf))
      if self.transitive:
        outpath += '.transitive'
      ivyinfo = self.ivy_utils.parse_xml_report(self.context.target_roots, conf)
      jar_paths = OrderedSet()
      for root in self.target_roots:
        jar_paths.update(self.get_jar_paths(ivyinfo, root, conf))

      with open(outpath, 'w') as outfile:
        def do_write(s):
          outfile.write(s)
          if self.also_write_to_stdout:
            sys.stdout.write(s)
        for jar in jar_paths:
          do_write('# from jar %s\n' % jar)
          for line in self.list_jar(jar):
            if line.endswith('.class'):
              class_name = line[:-6].replace('/', '.')
              do_write(class_name)
              do_write('\n')
      print('Wrote provides information to %s' % outpath)

 def create_geninfo(key):
   gen_info = context.config.getdict('thrift-gen', key)
   gen = gen_info['gen']
   deps = OrderedSet()
   for dep in gen_info['deps']:
     deps.update(context.resolve(dep))
   return ThriftGen.GenInfo(gen, deps)

  def bundle(self, app):
    """Create a self-contained application bundle.

    The bundle will contain the target classes, dependencies and resources.
    """
    assert(isinstance(app, BundleCreate.App))

    def verbose_symlink(src, dst):
      try:
        os.symlink(src, dst)
      except OSError as e:
        self.context.log.error("Unable to create symlink: {0} -> {1}".format(src, dst))
        raise e

    bundle_dir = os.path.join(self._outdir, '%s-bundle' % app.basename)
    self.context.log.info('creating %s' % os.path.relpath(bundle_dir, get_buildroot()))

    safe_mkdir(bundle_dir, clean=True)

    classpath = OrderedSet()
    # If creating a deployjar, we add the external dependencies to the bundle as
    # loose classes, and have no classpath. Otherwise we add the external dependencies
    # to the bundle as jars in a libs directory.
    if not self._create_deployjar:
      lib_dir = os.path.join(bundle_dir, 'libs')
      os.mkdir(lib_dir)

      jarmap = self.context.products.get('jars')

      def add_jars(target):
        generated = jarmap.get(target)
        if generated:
          for base_dir, internal_jars in generated.items():
            for internal_jar in internal_jars:
              verbose_symlink(os.path.join(base_dir, internal_jar), os.path.join(lib_dir, internal_jar))
              classpath.add(internal_jar)

      app.binary.walk(add_jars, lambda t: t != app.binary)

      # Add external dependencies to the bundle.
      for basedir, external_jar in self.list_external_jar_dependencies(app.binary):
        path = os.path.join(basedir, external_jar)
        verbose_symlink(path, os.path.join(lib_dir, external_jar))
        classpath.add(external_jar)

    bundle_jar = os.path.join(bundle_dir, '%s.jar' % app.binary.basename)

    with self.monolithic_jar(app.binary, bundle_jar,
                             with_external_deps=self._create_deployjar) as jar:
      self.add_main_manifest_entry(jar, app.binary)
      if classpath:
        jar.classpath([os.path.join('libs', jar) for jar in classpath])

    for bundle in app.bundles:
      for path, relpath in bundle.filemap.items():
        bundle_path = os.path.join(bundle_dir, relpath)
        safe_mkdir(os.path.dirname(bundle_path))
        verbose_symlink(path, bundle_path)

    return bundle_dir

  def _detect_cycle(self, src, dest):
    """Given a src and a dest, each of which _might_ already exist in the graph, detect cycles.

    Return a path of Nodes that describe the cycle, or None.
    """
    path = OrderedSet()
    walked = set()
    def _walk(node):
      if node in path:
        return tuple(path) + (node,)
      if node in walked:
        return None
      path.add(node)
      walked.add(node)

      for dep in self.dependencies_of(node):
        found = _walk(dep)
        if found is not None:
          return found
      path.discard(node)
      return None

    # Initialize the path with src (since the edge from src->dest may not actually exist), and
    # then walk from the dest.
    path.update([src])
    return _walk(dest)

  def _create_doc_target(self):
    all_sources = []
    all_deps = OrderedSet()
    for target in self.targets:
      if not self.only_provides or is_exported(target):
        for source in target.sources:
          source_path = os.path.join(self.java_src_prefix, source)
          if os.path.exists(source_path):
            all_sources.append(source_path)
          else:
            print "skipping %s" % source_path

          for jar_dep in target.jar_dependencies:
            if jar_dep.rev:
              all_deps.add(copy(jar_dep).intransitive())

    def create_meta_target():
      return JavaLibrary('pants.doc.deps',
                         all_sources,
                         provides = None,
                         dependencies = all_deps,
                         excludes = None,
                         resources = None,
                         binary_resources = None,
                         deployjar = False,
                         buildflags = None,
                         is_meta = True)

    # TODO(John Sirois): Find a better way to do_in_context when we don't care about the context
    return list(self.targets)[0].do_in_context(create_meta_target)

  def _compute_sources(self, target):
    relative_sources = OrderedSet()
    source_roots = OrderedSet()

    def capture_and_relativize_to_source_root(source):
      source_root = self.context.source_roots.find_by_path(source)
      if not source_root:
        source_root = self.context.source_roots.find(target)
      source_roots.add(source_root.path)
      return fast_relpath(source, source_root.path)

    if target.payload.get_field_value('ordered_sources'):
      # Re-match the filespecs against the sources in order to apply them in the literal order
      # they were specified in.
      filespec = target.globs_relative_to_buildroot()
      excludes = filespec.get('excludes', [])
      for filespec in filespec.get('globs', []):
        sources = [s for s in target.sources_relative_to_buildroot()
                   if globs_matches([s], [filespec], excludes)]
        if len(sources) != 1:
          raise TargetDefinitionException(
              target,
              'With `ordered_sources=True`, expected one match for each file literal, '
              'but got: {} for literal `{}`.'.format(sources, filespec)
            )
        relative_sources.add(capture_and_relativize_to_source_root(sources[0]))
    else:
      # Otherwise, use the default (unspecified) snapshot ordering.
      for source in target.sources_relative_to_buildroot():
        relative_sources.add(capture_and_relativize_to_source_root(source))
    return relative_sources, source_roots

    def execute_codegen(self, target, target_workdir):
        sources_by_base = self._calculate_sources(target)
        sources = target.sources_relative_to_buildroot()

        bases = OrderedSet(sources_by_base.keys())
        bases.update(self._proto_path_imports([target]))

        gen_flag = "--java_out"

        gen = "{0}={1}".format(gen_flag, target_workdir)

        args = [self.protobuf_binary, gen]

        if self.plugins:
            for plugin in self.plugins:
                args.append("--{0}_out={1}".format(plugin, target_workdir))

        for base in bases:
            args.append("--proto_path={0}".format(base))

        args.extend(sources)

        # Tack on extra path entries. These can be used to find protoc plugins
        protoc_environ = os.environ.copy()
        if self._extra_paths:
            protoc_environ["PATH"] = os.pathsep.join(self._extra_paths + protoc_environ["PATH"].split(os.pathsep))

        # Note: The test_source_ordering integration test scrapes this output, so modify it with care.
        self.context.log.debug("Executing: {0}".format("\\\n  ".join(args)))
        with self.context.new_workunit(name="protoc", labels=[WorkUnitLabel.TOOL], cmd=" ".join(args)) as workunit:
            result = subprocess.call(
                args, env=protoc_environ, stdout=workunit.output("stdout"), stderr=workunit.output("stderr")
            )
            if result != 0:
                raise TaskError("{} ... exited non-zero ({})".format(self.protobuf_binary, result))

  def get_resolved_jars_for_jar_library(self, jar_library, memo=None):
    """Collects jars for the passed jar_library.

    Because artifacts are only fetched for the "winning" version of a module, the artifacts
    will not always represent the version originally declared by the library.

    This method is transitive within the library's jar_dependencies, but will NOT
    walk into its non-jar dependencies.

    :param jar_library A JarLibrary to collect the transitive artifacts for.
    :param memo see `traverse_dependency_graph`
    :returns: all the artifacts for all of the jars in this library, including transitive deps
    :rtype: list of str
    """
    def to_resolved_jar(jar_module_ref, artifact_path):
      return ResolvedJar(coordinate=M2Coordinate(org=jar_module_ref.org, name=jar_module_ref.name,
                                                 rev=jar_module_ref.rev,
                                                 classifier=jar_module_ref.classifier),
                         cache_path=artifact_path
      )
    resolved_jars = OrderedSet()
    def create_collection(dep):
      return OrderedSet([dep])
    for jar in jar_library.jar_dependencies:
      for classifier in jar.artifact_classifiers:
        jar_module_ref = IvyModuleRef(jar.org, jar.name, jar.rev, classifier)
        for module_ref in self.traverse_dependency_graph(jar_module_ref, create_collection, memo):
          for artifact_path in self._artifacts_by_ref[module_ref.unversioned]:
            resolved_jars.add(to_resolved_jar(jar_module_ref, artifact_path))
    return resolved_jars

 def get_transitive_jars(jar_lib):
   if not ivy_info:
     return OrderedSet()
   transitive_jars = OrderedSet()
   for jar in jar_lib.jar_dependencies:
     transitive_jars.update(ivy_info.get_jars_for_ivy_module(jar))
   return transitive_jars

  def get_artifacts_for_jar_library(self, jar_library, memo=None):
    """Collects IvyArtifact instances for the passed jar_library.

    Because artifacts are only fetched for the "winning" version of a module, the artifacts
    will not always represent the version originally declared by the library.

    This method is transitive within the library's jar_dependencies, but will NOT
    walk into its non-jar dependencies.

    :param jar_library A JarLibrary to collect the transitive artifacts for.
    :param memo see `traverse_dependency_graph`
    """
    artifacts = OrderedSet()
    def create_collection(dep):
      return OrderedSet([dep])
    for jar in jar_library.jar_dependencies:
      jar_module_ref = IvyModuleRef(jar.org, jar.name, jar.rev)
      valid_classifiers = jar.artifact_classifiers
      artifacts_for_jar = []
      for module_ref in self.traverse_dependency_graph(jar_module_ref, create_collection, memo):
        artifacts_for_jar.extend(
          artifact for artifact in self._artifacts_by_ref[module_ref.unversioned]
          if artifact.classifier in valid_classifiers
        )

      artifacts.update(artifacts_for_jar)
    return artifacts

    def transitive_subgraph_of_addresses_bfs(self, addresses, predicate=None, leveled_predicate=None):
        """Returns the transitive dependency closure of `addresses` using BFS.

    :API: public

    :param list<Address> addresses: The closure of `addresses` will be walked.
    :param function predicate: If this parameter is not given, no Targets will be filtered
      out of the closure.  If it is given, any Target which fails the predicate will not be
      walked, nor will its dependencies.  Thus predicate effectively trims out any subgraph
      that would only be reachable through Targets that fail the predicate.
    :param function leveled_predicate: Behaves identically to predicate, but takes the depth of the
      target in the search tree as a second parameter, and it is checked just before a dependency is
      expanded.
    """
        ordered_closure = OrderedSet()
        # Use the DepthAgnosticWalk if we can, because DepthAwareWalk does a bit of extra work that can
        # slow things down by few millis.
        walker = self.DepthAwareWalk if leveled_predicate else self.DepthAgnosticWalk
        walk = walker()
        to_walk = deque((0, addr) for addr in addresses)
        while len(to_walk) > 0:
            level, address = to_walk.popleft()
            target = self._target_by_address[address]
            if not walk.expand_once(target, level):
                continue
            if predicate and not predicate(target):
                continue
            if walk.do_work_once(target):
                ordered_closure.add(target)
            for addr in self._target_dependencies_by_address[address]:
                if not leveled_predicate or leveled_predicate(self._target_by_address[addr], level):
                    to_walk.append((level + 1, addr))
        return ordered_closure

 def _flatten_type_constraints(self, selection_products):
   type_constraints = filter(lambda o: isinstance(o, Exactly), selection_products)
   non_type_constraints = filter(lambda o: not isinstance(o, Exactly), selection_products)
   flattened_products = OrderedSet(non_type_constraints)
   for t in type_constraints:
     flattened_products.update(t.types)
   return flattened_products

  def targets(self, predicate=None, postorder=False):
    """Selects targets in-play in this run from the target roots and their transitive dependencies.

    Also includes any new synthetic targets created from the target roots or their transitive
    dependencies during the course of the run.

    :API: public

    :param predicate: If specified, the predicate will be used to narrow the scope of targets
                      returned.
    :param bool postorder: `True` to gather transitive dependencies with a postorder traversal;
                          `False` or preorder by default.
    :returns: A list of matching targets.
    """
    target_set = self._collect_targets(self.target_roots, postorder=postorder)

    synthetics = OrderedSet()
    for synthetic_address in self.build_graph.synthetic_addresses:
      if self.build_graph.get_concrete_derived_from(synthetic_address) in target_set:
        synthetics.add(self.build_graph.get_target(synthetic_address))

    synthetic_set = self._collect_targets(synthetics, postorder=postorder)

    target_set.update(synthetic_set)

    return filter(predicate, target_set)

 def dependents_of_addresses(self, addresses):
   """Given an iterable of addresses, yield all of those addresses dependents."""
   seen = OrderedSet(addresses)
   for address in addresses:
     seen.update(self._dependent_address_map[address])
     seen.update(self._implicit_dependent_address_map[address])
   return seen