cargo2ebuild: Use CROS_RUST_REMOVE_TARGET_CFG when possible.

This is a fairly extensive overhaul that adds a dependency graph model
that handles reusing system ebuilds when possible.

Additional changes:
* Added logging and verbosity flags.
* -X add for upgrading crates when system versions would already work.
* -x apply to empty crates.
* default values added to most parameters.
* Added error messages for cases that require user changes.
* Features are not tracked to determine if optional dependencies
  should not be empty.
* Switched DESCRIPTION and HOMEPAGE to single quotes to prevent
  unintended variable expansion or sub-shell execution.

BUG=chromium:1182669
TEST=manual testing

Change-Id: I53eab1af0c2bc6321155dcedb96c622a2d59d532
Reviewed-on: https://chromium-review.googlesource.com/c/chromiumos/platform/dev-util/+/2867124
Reviewed-by: Abhishek Pandit-Subedi <abhishekpandit@chromium.org>
Commit-Queue: Allen Webb <allenwebb@google.com>
Tested-by: Allen Webb <allenwebb@google.com>
diff --git a/contrib/cargo2ebuild.py b/contrib/cargo2ebuild.py
index c07836c..a413e05 100755
--- a/contrib/cargo2ebuild.py
+++ b/contrib/cargo2ebuild.py
@@ -9,9 +9,12 @@
 """
 
 import argparse
+from collections import defaultdict
 from datetime import datetime
 import json
+import logging
 import os
+from pprint import pprint
 import re
 import shutil
 import subprocess
@@ -31,17 +34,17 @@
 #   dependencies: Ebuild compatible dependency string.
 #   autogen_notice: Autogenerated notification string.
 EBUILD_TEMPLATE = (
-"""# Copyright {copyright_year} The Chromium OS Authors. All rights reserved.
+  """# Copyright {copyright_year} The Chromium OS Authors. All rights reserved.
 # Distributed under the terms of the GNU General Public License v2
 
 EAPI="7"
 
-CROS_RUST_REMOVE_DEV_DEPS=1
+CROS_RUST_REMOVE_DEV_DEPS=1{remove_target_var}
 
 inherit cros-rust
 
-DESCRIPTION="{description}"
-HOMEPAGE="{homepage}"
+DESCRIPTION='{description}'
+HOMEPAGE='{homepage}'
 SRC_URI="https://crates.io/api/v1/crates/${{PN}}/${{PV}}/download -> ${{P}}.crate"
 
 LICENSE="{license}"
@@ -56,7 +59,7 @@
 #   crate_features: Features to add to this empty crate.
 #   autogen_notice: Autogenerated notification string.
 EMPTY_CRATE = (
-"""# Copyright {copyright_year} The Chromium OS Authors. All rights reserved.
+  """# Copyright {copyright_year} The Chromium OS Authors. All rights reserved.
 # Distributed under the terms of the GNU General Public License v2
 
 EAPI="7"
@@ -77,6 +80,7 @@
 LICENSES = {
     'Apache-2.0': 'Apache-2.0',
     'MIT': 'MIT',
+    'BSD-2-Clause': 'BSD-2',
     'BSD-3-Clause': 'BSD',
     '0BSD': '0BSD',
     'ISC': 'ISC',
@@ -90,11 +94,541 @@
     '([+\\-].*)?$'  # Any semver values beyond patch version
 )
 
+EBUILD_RE = (
+    '^(?P<name>[-a-zA-Z0-9_]+)?'  # Ebuild name
+    '-(?P<version>[0-9]+(.[0-9]+)?(.[0-9]+)?)'
+    '([-_].*)?\\.ebuild$'  # Any semver values beyond patch version
+)
+
+FEATURES_RE = (
+    '^CROS_RUST_EMPTY_CRATE_FEATURES=\\('
+    '(?P<features>([^)]|$)*)'  # Features array
+    '\\)'
+)
+
+DEP_GRAPH_ROOT = '*root*'
+
 
 class VersionParseError(Exception):
     """Error that is returned when parsing a version fails."""
 
 
+class VersionRange:
+    """Represents a range of Rust crate versions."""
+    @staticmethod
+    def from_str(value):
+        """Generate a VersionRange from a crate requirement string."""
+        if value == '*':
+            return VersionRange(v_min=(0, 0, 0))
+
+        v_min = None
+        v_min_inclusive = True
+        v_max = None
+        v_max_inclusive = False
+
+        # Handle a pair of constraints.
+        parts = value.split(', ')
+        if len(parts) == 2:
+            for part in parts:
+                if part.startswith('>='):
+                    dep, major, minor, patch = version_to_tuple(part[2:], missing=0)
+                    v_min = (major, minor, patch)
+                elif part.startswith('<='):
+                    v_max_inclusive = True
+                    dep, major, minor, patch = version_to_tuple(part[2:], missing=0)
+                    v_max = (major, minor, patch)
+                elif part.startswith('>'):
+                    v_min_inclusive = False
+                    dep, major, minor, patch = version_to_tuple(part[1:], missing=0)
+                    v_min = (major, minor, patch)
+                elif part.startswith('<'):
+                    dep, major, minor, patch = version_to_tuple(part[1:], missing=0)
+                    v_max = (major, minor, patch)
+                if v_max and v_min and v_max < v_min:
+                    raise VersionParseError
+        # We are not going to worry about more than two constraints until we see it.
+        elif len(parts) != 1:
+            raise VersionParseError(
+                'Version constraint has more than two parts: {}'.format(parts))
+        # Handle the typical case of a single constraint operator.
+        else:
+            dep, major, minor, patch = version_to_tuple(value, missing=-1)
+            v_min = (major, minor, patch)
+
+            if dep == '=':
+                v_max = v_min
+                v_max_inclusive = True
+            elif dep == '~':
+                major = max(v_min[0], 0)
+                minor = max(v_min[1], 0)
+                patch = max(v_min[2], 0)
+                if v_min[0] < 0:
+                    raise VersionParseError(
+                        'The ~ constraint operator requires a major version: {}'.format(value))
+                if v_min[1] < 0:
+                    v_max = (major + 1, 0, 0)
+                elif v_min[2] < 0:
+                    v_max = (0, minor + 1, 0)
+                else:
+                    v_max_inclusive = True
+                    v_max = (major, minor, patch)
+                v_min = (major, minor, patch)
+            elif dep and dep != '^':
+                raise VersionParseError('Unrecognized operator: "{}"'.format(dep))
+            else:
+                major = max(v_min[0], 0)
+                minor = max(v_min[1], 0)
+                patch = max(v_min[2], 0)
+
+                v_min = (major, minor, patch)
+                if major > 0:
+                    v_max = (major + 1, 0, 0)
+                elif minor > 0:
+                    v_max = (0, minor + 1, 0)
+                else:
+                    v_max_inclusive = True
+                    v_max = v_min
+
+        return VersionRange(v_min=v_min, v_min_inclusive=v_min_inclusive, v_max=v_max,
+                            v_max_inclusive=v_max_inclusive)
+
+    def __init__(self, v_min=None, v_min_inclusive=True, v_max=None, v_max_inclusive=False):
+        self.min = v_min
+        self.min_inclusive = v_min_inclusive
+        self.max = v_max
+        self.max_inclusive = v_max_inclusive
+
+    def contains(self, version):
+        """Returns `True` if version is inside the range; `False` otherwise.
+
+        Args:
+            version: Can be either a tuple of integers (major, minor, patch) or a string that will be converted to a
+                tuple of integers. Trailing characters will be removed from the version (e.g. "+openssl-1.0.1").
+        """
+        if isinstance(version, str):
+            try:
+                filtered_version = re.sub(r'([0-9]+\.[0-9]+\.[0-9]+)[^0-9].*$', r'\1', version)
+                if filtered_version != version:
+                    logging.warning('Filtered version "%s" to "%s"', version, filtered_version)
+                version = tuple([int(a) for a in filtered_version.split('.')])
+            except Exception as e:
+                print(version)
+                raise e
+
+        if self.min:
+            if self.min_inclusive:
+                if self.min > version:
+                    return False
+            elif self.min >= version:
+                return False
+        if self.max:
+            if self.max_inclusive:
+                if self.max < version:
+                    return False
+            elif self.max <= version:
+                return False
+        return True
+
+    def to_ebuild_str(self, category_and_name):
+        """Return an ebuild DEPEND entry equivalent to the range.
+
+        Args:
+            category_and_name: A string of the form 'dev-rust/crate-name' where 'dev-rust' is the category and
+                'crate-name' is the name of the ebuild.
+
+        Returns:
+            A string that can be used in an ebuild's DEPEND field.
+        """
+        if not self.min or self.min == (0, 0, 0) and not self.max:
+            return '{}:='.format(category_and_name)
+
+        min_bound = '>=' if self.min_inclusive else '>'
+        max_bound = '<=' if self.max_inclusive else '<'
+        if not self.max:
+            return '{}{}-{}.{}.{}:='.format(min_bound, category_and_name, self.min[0], self.min[1],
+                                            self.min[2])
+
+        for x in range(len(self.min)):
+            if self.min[x] != self.max[x]:
+                break
+        else:
+            # We want to allow revisions other than -r0, so use `~` instead of `=`.
+            return '~{}-{}.{}.{}:='.format(category_and_name, self.min[0], self.min[1],
+                                           self.min[2])
+
+        if self.min_inclusive and not self.max_inclusive and self.min[x] + 1 == self.max[x]:
+            if x == 0 and self.min[1] == 0 and self.min[2] == 0:
+                return '={}-{}*:='.format(category_and_name, self.min[0])
+            if x == 1 and self.min[2] == 0:
+                return '={}-{}.{}*:='.format(category_and_name, self.min[0], self.min[1])
+
+        return '{0}{1}-{2}.{3}.{4}:= {5}{1}-{6}.{7}.{8}'.format(
+            min_bound, category_and_name, self.min[0], self.min[1], self.min[2],
+            max_bound, self.max[0], self.max[1], self.max[2])
+
+
+class DepGraphNode:
+    """A node in the dep-graph for a specific version of a package used by DepGraph."""
+    def __init__(self, package):
+        self.package = package
+        self.dependencies = []
+
+    def __repr__(self):
+        return '{}'.format([(a['name'], a['req']) for a in self.dependencies])
+
+    def add_dependency(self, dep):
+        """Adds a dependency to the list."""
+        self.dependencies.append(dep)
+
+
+class DepGraph:
+    """A model of the dependency relationships between crates.
+
+    The functionality this provides over using the Cargo metadata directly is:
+    * Filtering based on cros-rust.eclass features.
+    * Tracking of system ebuilds for detecting edge cases such as:
+        * Already fulfilled dependencies.
+        * Optional crates that would replace or supersede non-empty ebuilds.
+        * Empty crates that are missing definitions for required features.
+    """
+    def __init__(self):
+        # name -> version -> DepGraphNode
+        self.graph = defaultdict(dict)
+
+        # name -> version -> None or [features]
+        self.system_crates = defaultdict(dict)
+
+        # The crate that will be initially checked when flattening the depgraph into a list of required and optional
+        # crates.
+        self.root = None
+
+    def add_package(self, package):
+        """Add a crate to the dependency graph from a parsed metadata.json generated by cargo.
+
+        Args:
+            package: A parsed package from the Cargo metadata.
+
+        Returns:
+            filter_target: True if CROS_RUST_REMOVE_TARGET_CFG=1 should be set in the ebuild.
+            deps: A list of dependencies from the Cargo metadata JSON that still apply after filtering.
+        """
+        dependencies = package['dependencies']
+
+        # Check if there are target specific dependencies and if so if they can be handled by
+        # CROS_RUST_REMOVE_TARGET_CFG. This requires that there not be complicated cfg blocks since the cros-rust eclass
+        # only applies simplistic filtering.
+        has_filterable_target = False
+        has_unfilterable_target = False
+        for dep in dependencies:
+            # Skip all dev dependencies. We will still handle normal and build deps.
+            if dep.get('kind', None) == 'dev':
+                continue
+
+            target = dep.get('target', None)
+            if target is None:
+                continue
+
+            if target_applies_to_chromeos(target):
+                continue
+
+            if not target_is_filterable(target):
+                logging.debug('target "%s" is unfilterable.', target)
+                has_unfilterable_target = True
+            else:
+                has_filterable_target = True
+        if has_unfilterable_target:
+            logging.warning('"%s-%s" might benefit from better target specific dependency filtering',
+                            package['name'], package['version'])
+        filter_target = has_filterable_target and not has_unfilterable_target
+
+        graph_node = DepGraphNode(package)
+        self.graph[package['name']][package['version']] = graph_node
+
+        # Check each dependency and add it if it is relevant to Chrome OS.
+        deps = []
+        for dep in dependencies:
+            # Skip all dev dependencies. We will still handle normal and build deps.
+            if dep.get('kind', None) == 'dev':
+                continue
+
+            # Skip filterable configuration dependant dependencies.
+            target = dep.get('target', None)
+            if filter_target and target is not None and not target_applies_to_chromeos(target):
+                continue
+
+            graph_node.add_dependency(dep)
+            deps.append(dep)
+        return filter_target, deps
+
+    def find_system_crates(self, target_dir, names=None):
+        """Take note of crates already present in the target directory.
+
+        Args:
+            target_dir: The overlay directory where the ebuilds exist.
+            names: A list of package names to check. If unspecified all the crates present in the DepGraph are checked.
+        """
+        if names is None:
+            names = self.graph
+
+        for name in names:
+            # Skip if we have already done this crate.
+            if name in self.system_crates:
+                continue
+            available = self.system_crates[name]
+
+            # Check if an empty package already has a non-empty ebuild.
+            ebuild_target_dir = get_ebuild_dir(name, target_dir)
+
+            # Find all ebuilds in ebuild_target dir and if they have
+            # CROS_RUST_EMPTY_CRATE in them, check if features are set.
+            for root, _, files in os.walk(ebuild_target_dir):
+                files.sort()
+                for efile in files:
+                    if not efile.endswith('.ebuild'):
+                        continue
+                    efile_path = os.path.join(root, efile)
+
+                    m = re.match(EBUILD_RE, efile)
+                    if not m or m.group('name') != name:
+                        logging.warning("Found misplaced ebuild: '%s'.", efile_path)
+                        continue
+
+                    version = m.group('version')
+
+                    with open(efile_path, 'r') as ebuild:
+                        contents = ebuild.read()
+                        if 'CROS_RUST_EMPTY_CRATE' not in contents:
+                            features = None
+                        else:
+                            m = re.search(FEATURES_RE, contents, re.MULTILINE)
+                            if m:
+                                sanitized = re.sub('[^a-zA-Z0-9_ \t\n-]+', '', m.group('features'))
+                                features = set(a.strip() for a in sanitized.split() if a)
+                            else:
+                                features = set()
+                    logging.debug("Found ebuild: '%s'.", efile_path[len(target_dir):])
+                    available[version] = features
+
+    def set_root(self, package):
+        """Set the root of the dependency graph used when flattening the graph into a list of dependencies."""
+        self.root = package
+
+    def resolve_version_range(self, name, version_range):
+        """Find a dependency graph entry that fits the constraints.
+
+        Optional dependencies often are not found, so the minimum version in version_range is returned in those cases.
+
+        Args:
+            name: crate name
+            version_range: A VersionRange used to match against crate versions.
+
+        Returns:
+            version: Returns the version of the match or the minimum matching version if no match is found.
+            node: None if no match is found otherwise returns the DepGraphNode of the match.
+        """
+        for version, node in self.graph[name].items():
+            if version_range.contains(version):
+                return version, node
+        if not version_range.min:
+            return '0.0.0', None
+        return '.'.join(map(str, version_range.min)), None
+
+    def check_dependencies(self, args, package, features, optional, features_only=False):
+        """Check the dependencies of a specified package with the specified features enabled.
+
+        Args:
+            args: The command line flags set for cargo2ebuild.
+            package: A parsed package from the Cargo metadata.
+            features: A set containing the enabled features for this package. This will be expanded by the function to
+                include any additional features implied by the original set of features (e.g. if default is set, all the
+                default features will be added).
+            optional: A dictionary of sets to which any new optional dependencies are added. It has the format:
+                (package_name, package_version): set()
+                where the set contains the required features.
+            features_only: If True, this function only checks the optional dependencies for ones that are enabled if
+                the features specified by `features` are enabled.
+
+        Returns:
+            A list of (package_name, package_version) that are required by the specified package with the specified
+            features enabled.
+        """
+        name = package['name']
+        version = package['version']
+        node = self.graph[name][version]
+
+        enabled_optional_deps = get_feature_dependencies(package, features)
+
+        new_required = []
+        for dep in node.dependencies:
+            dep_name = dep['name']
+            if features_only and dep_name not in enabled_optional_deps:
+                continue
+            req = VersionRange.from_str(dep['req'])
+            dep_version, dep_node = self.resolve_version_range(dep_name, req)
+            identifier = (dep_name, dep_version)
+
+            dep_features = set(dep['features'])
+            if dep_node and dep.get('uses_default_features', False):
+                dep_features.add('default')
+
+            is_required = not dep.get('optional', False) or dep_name in enabled_optional_deps
+            if dep_name in enabled_optional_deps:
+                if not features_only:
+                    logging.info('Optional dependency required by feature: "%s-%s"', dep_name, dep_version)
+                dep_features.update(enabled_optional_deps[dep_name])
+
+            found = False
+            sys_version = None
+            repl_versions = []
+            if dep_name not in self.system_crates:
+                self.find_system_crates(args.target_dir, names=[dep_name])
+            for sys_version, sys_features in self.system_crates[dep_name].items():
+                sys_crate_is_empty = sys_features is not None
+                missing_features = dep_features.difference(sys_features) if sys_crate_is_empty else set()
+                if not args.overwrite_existing_ebuilds and sys_version == dep_version:
+                    if sys_crate_is_empty:
+                        if is_required:
+                            logging.error('Empty crate "%s-%s" should be replaced with full version.',
+                                          dep_name, dep_version)
+                        elif missing_features:
+                            logging.error('Empty crate "%s-%s" has missing features: %s.',
+                                          dep_name, dep_version, missing_features)
+                    found = True
+                    break
+                if not sys_crate_is_empty and req.contains(sys_version):
+                    if not args.no_substitute or (not is_required and dep_node is None):
+                        found = True
+                        break
+                if VersionRange.from_str('^{}'.format(sys_version)).contains(dep_version):
+                    if sys_crate_is_empty:
+                        dep_features.update(sys_features)
+                    else:
+                        repl_versions.append(sys_version)
+            if found and not features_only:
+                logging.debug('Using system crate: "%s-%s".', dep_name, sys_version)
+                continue
+
+            if is_required:
+                if dep_node is None:
+                    logging.error('Required crate "%s" "%s" not in dep-graph. It will be omitted.',
+                                  dep_name, dep['req'])
+                else:
+                    logging.debug('New crate required: "%s-%s".', dep_name, dep_version)
+                    new_required.append((dep_node.package, dep_features))
+            else:
+                # If the empty crate would replace a non-empty version of the same crate, treat it as required.
+                if repl_versions:
+                    if dep_node is not None:
+                        logging.info('Empty crate for "%s-%s" would replace non-empty versions %s. '
+                                     'Upgrading to non-empty.', dep_name, dep_version, repl_versions)
+                        new_required.append((dep_node.package, dep_features))
+                    else:
+                        logging.error('Required crate "%s-%s" not in metadata. Fix: add it to Cargo.toml',
+                                      dep_name, dep_version)
+                else:
+                    logging.debug('New optional crate required: "%s-%s".', dep_name, dep_version)
+                    # Include all features supported by the crate.
+                    if dep_node is not None:
+                        dep_features = dep_node.package['features'].keys()
+                    optional[identifier].update(dep_features if features else ())
+        return new_required
+
+    def flatten(self, args):
+        """Flatten the dependency graph into a list of required and optional crates.
+
+        Returns:
+            Two dictionaries that map tuples of package names and versions to sets of features:
+                (name, version) -> set(features)
+            The first dictionary contains the required crates with their required features, while the second contains
+            the optional crates, versions, and their features.
+        """
+        # (name, version) -> set(features)
+        required = defaultdict(set)
+        optional = defaultdict(set)
+        remaining = [(self.root, {'default'})]
+        while remaining:
+            to_check, features = remaining.pop(0)
+            name = to_check['name']
+            version = to_check['version']
+
+            identifier = (name, version)
+            if identifier in required:
+                features_to_enable = features.difference(required[identifier])
+                if not features_to_enable:
+                    continue
+                logging.debug('Extending dependencies for "%s-%s" to include features: "%s"',
+                              name, version, features_to_enable)
+                remaining.extend(self.check_dependencies(args, to_check, features_to_enable, optional,
+                                                         features_only=True))
+            else:
+                logging.debug('Resolving dependencies for "%s-%s".', name, version)
+                remaining.extend(self.check_dependencies(args, to_check, features, optional))
+            required[identifier].update(features)
+
+        return dict(required), {a: b for a, b in optional.items() if a not in required}
+
+
+def target_applies_to_chromeos(target):
+    """Return true if the target would be accepted by the cros-rust eclass."""
+    return (
+            target.startswith('cfg(unix') or
+            target.startswith('cfg(linux') or
+            target.startswith('cfg(not(windows)') or
+            '-linux-gnu' in target
+    )
+
+
+def target_is_filterable(target):
+    """Checks to see if the cros-rust eclass would probably handle this target properly.
+
+    Returns:
+        False if the Cargo.toml target configuration block would not be accepted by the cros-rust eclass, but is probably needed.
+    """
+    if target_applies_to_chromeos(target):
+        return True
+    if 'unix' in target or 'linux' in target or 'not(' in target:
+        return False
+    return True
+
+
+def get_feature_dependencies(package, features):
+    """Expand the features set to include implied features and return the enabled optional dependencies.
+
+    Args:
+        package: A parsed package from the Cargo metadata.
+        features: A set() of features that is expanded to include any additional dependencies implied by the original
+            set of features.
+
+    Returns:
+        A dictionary that maps crate names to the required features for the specific crate.
+        Note: that no version is supplied; it must be obtained by finding the named dependency in the package's
+        optional dependency requirements.
+    """
+    feature_list = list(features)
+    enabled_deps = defaultdict(set)
+    lookup = package.get('features', {})
+    for feature in feature_list:
+        if feature not in lookup:
+            if feature != 'default':
+                logging.error('Requested feature "%s" not listed in crate "%s".',
+                              feature, package['name'])
+            continue
+        for dep in lookup[feature]:
+            # Check if it is a feature instead of a dependency.
+            if dep in lookup:
+                if dep not in features:
+                    feature_list.append(dep)
+                    features.add(dep)
+                continue
+            parts = dep.split('/')
+
+            # This creates an empty set if there is not one already.
+            entry = enabled_deps[parts[0]]
+            if len(parts) > 1:
+                entry.add(parts[1])
+    return dict(enabled_deps)
+
+
 def prepare_staging(args):
     """Prepare staging directory."""
     sdir = args.staging_dir
@@ -128,10 +662,10 @@
 def get_clean_crate_name(package):
     """Clean up crate name to {name}-{major}.{minor}.{patch}."""
     return '{}-{}.crate'.format(package['name'],
-                                get_clean_package_version(package))
+                                get_clean_package_version(package['version']))
 
 
-def version_to_tuple(name, version, missing=-1):
+def version_to_tuple(version, missing=-1):
     """Extract dependency type and semver from a given version string."""
     def version_to_int(num):
         if not num or num == '*':
@@ -140,7 +674,6 @@
 
     m = re.match(VERSION_RE, version)
     if not m:
-        print('{} failed to parse dep version: {}'.format(name, version))
         raise VersionParseError
 
     dep = m.group('dep')
@@ -159,26 +692,30 @@
     elif not dep:
         dep = '^'
 
-    return (dep, major, minor, patch)
+    return dep, major, minor, patch
 
 
-def get_clean_package_version(package):
+def get_clean_package_version(version):
     """Get package version in the format {major}.{minor}.{patch}."""
-    (_, major, minor, patch) = version_to_tuple(package['name'],
-                                                package['version'],
-                                                missing=0)
+    (_, major, minor, patch) = version_to_tuple(version, missing=0)
     return '{}.{}.{}'.format(major, minor, patch)
 
 
-def get_ebuild_path(package, staging_dir, make_dir=False):
+def get_ebuild_dir(name, staging_dir):
+    """Get the directory that contains specific ebuilds."""
+    return os.path.join(staging_dir, 'dev-rust', name)
+
+
+def get_ebuild_path(name, version, staging_dir, make_dir=False):
     """Get path to ebuild in given directory."""
+    ebuild_dir = get_ebuild_dir(name, staging_dir)
+
     ebuild_path = os.path.join(
-        staging_dir, 'dev-rust', package['name'],
-        '{}-{}.ebuild'.format(package['name'],
-                              get_clean_package_version(package)))
+        ebuild_dir,
+        '{}-{}.ebuild'.format(name, get_clean_package_version(version)))
 
     if make_dir:
-        os.makedirs(os.path.dirname(ebuild_path), exist_ok=True)
+        os.makedirs(ebuild_dir, exist_ok=True)
 
     return ebuild_path
 
@@ -192,20 +729,20 @@
     if os.path.isfile(crate_path):
         return
 
-    ret = subprocess.run(['curl', '-L', dl_uri, '-o', crate_path],
-                   stdout=subprocess.DEVNULL,
-                   stderr=subprocess.DEVNULL).returncode
+    ret = subprocess.run(
+        ['curl', '-L', dl_uri, '-o', crate_path],
+        stdout=subprocess.DEVNULL,
+        stderr=subprocess.DEVNULL).returncode
 
     if ret:
-        print('{} failed to download: {}'.format(dl_uri, ret))
+        logging.error('Failed to download "%s": %s', dl_uri, ret)
 
 
 def get_description(package):
     """Get a description of the crate from metadata."""
-    # pylint: disable=invalid-string-quote
     if package.get('description', None):
-        desc = package['description'].replace('`', '\'').replace('"', '\'')
-        return desc.rstrip('\n')
+        desc = re.sub("[`']", '"', package['description'])
+        return desc.strip()
 
     return ''
 
@@ -224,15 +761,14 @@
     has_or = ' OR ' in cargo_license
     delim = ' OR ' if has_or else '/'
 
-    found = cargo_license.split(delim)
+    found = [a.strip() for a in cargo_license.split(delim) if a]
     licenses_or = []
     for f in found:
         if f in LICENSES:
             licenses_or.append(LICENSES[f])
 
     if not licenses_or:
-        print('{} is missing an appropriate license: {}'.format(
-            package['name'], license))
+        logging.error('"%s" is missing an appropriate license: "%s"', package['name'], cargo_license)
         return "$(die 'Please replace with appropriate license')"
 
     if len(licenses_or) > 1:
@@ -243,108 +779,58 @@
     return lstr
 
 
-def convert_dependencies(dependencies, package, optional_packages):
-    """Convert dependencies from metadata into the ebuild format."""
-    def caret_to_ebuild(info):
-        prefix = '>=dev-rust/{name}-{major}.{minor}.{patch}:='.format(**info)
-        suffix = '<dev-rust/{name}-{major_1}'.format(**info)
-
-        if info['minor'] == -1:
-            prefix = '>=dev-rust/{name}-{major}:='.format(**info)
-        elif info['patch'] == -1:
-            prefix = '>=dev-rust/{name}-{major}.{minor}:='.format(**info)
-
-        if info['major'] == 0:
-            suffix = '<dev-rust/{name}-{major}.{minor_1}'.format(**info)
-
-        return '{} {}'.format(prefix, suffix)
-
-    def tilde_to_ebuild(info):
-        prefix = '>=dev-rust/{name}-{major}.{minor}.{patch}:='.format(**info)
-        suffix = '<dev-rust/{name}-{major}.{minor_1}'.format(**info)
-        ebuild = '{} {}'.format(prefix, suffix)
-
-        if info['minor'] == -1:
-            ebuild = '=dev-rust/{name}-{major}*:='.format(**info)
-        elif info['patch'] == -1:
-            ebuild = '=dev-rust/{name}-{major}.{minor}*:='.format(**info)
-
-        return ebuild
-
-    def dep_to_ebuild(name, dep_type, major, minor, patch):
-        info = {
-            'name': name,
-            'major': major,
-            'minor': minor,
-            'patch': patch,
-            'major_1': major + 1,
-            'minor_1': minor + 1,
-            'patch_1': patch + 1
-        }
-
-        if dep_type == '^':
-            return caret_to_ebuild(info)
-        if dep_type == '~':
-            return tilde_to_ebuild(info)
-
-        # Remaining dep type is =
-        return '=dev-rust/{name}-{major}.{minor}.{patch}:='.format(**info)
-
+def convert_dependencies(dependencies, filter_target=False):
+    """Convert crate dependencies to ebuild dependencies."""
     deps = []
     for dep in dependencies:
-        # Skip all dev dependencies. We will still handle normal and build deps.
-        if dep.get('kind', None) == 'dev':
-            continue
-
-        # Optional dependencies get empty packages created
-        if dep.get('optional', None):
-            optional_packages[dep['name']] = {
-                    'name': dep['name'],
-                    'version': dep['req'],
-                    'features': dep['features'],
-            }
-
         # Convert version requirement to ebuild DEPEND.
         try:
             # Convert requirement to version tuple
-            (deptype, major, minor, patch) = version_to_tuple(dep['name'], dep['req'])
-            ebuild = dep_to_ebuild(dep['name'], deptype, major, minor, patch)
-            deps.append('\t{}'.format(ebuild))
+            bounds = (
+                VersionRange.from_str(dep['req'])
+                            .to_ebuild_str('dev-rust/{}'.format(dep['name']))
+            )
+            deps.append('\t{}'.format(bounds))
         except VersionParseError:
+            logging.error('Failed to parse dep version for "%s": %s',
+                          dep['name'], dep['req'], exc_info=True)
             # Rarely dependencies look something like ">=0.6, <0.8"
-            deps.append("\t$(die 'Please replace with proper DEPEND: {} = {}')".format(dep['name'], dep['req']))
+            deps.append("\t$(die 'Please replace with proper DEPEND: {} = {}')".format(
+                dep['name'], dep['req']))
 
+    remove_target_var = '\nCROS_RUST_REMOVE_TARGET_CFG=1' if filter_target else ''
     if not deps:
-        return ''
+        return '', remove_target_var
 
     # Add DEPEND= into template with all dependencies
     # RDEPEND="${DEPEND}" required for race in cros-rust
     fmtstring = 'DEPEND="\n{}\n"\nRDEPEND="${{DEPEND}}"\n'
-    return fmtstring.format('\n'.join(deps))
+    return fmtstring.format('\n'.join(deps)), remove_target_var
 
 
-def package_ebuild(package, ebuild_dir, optional_packages):
+def package_ebuild(package, ebuild_dir, crate_dependencies, filter_target):
     """Create ebuild from metadata and write to ebuild directory."""
-    ebuild_path = get_ebuild_path(package, ebuild_dir, make_dir=True)
+    logging.debug('Processing "%s-%s"', package['name'], package['version'])
+    ebuild_path = get_ebuild_path(package['name'], package['version'], ebuild_dir, make_dir=True)
 
     autogen_notice = AUTOGEN_NOTICE
 
     # Check if version matches clean version or modify the autogen notice
-    if package['version'] != get_clean_package_version(package):
+    if package['version'] != get_clean_package_version(package['version']):
         autogen_notice = '\n'.join([
             autogen_notice,
             '# ${{PV}} was changed from the original {}'.format(
                 package['version'])
         ])
 
-    dependencies = convert_dependencies(package['dependencies'], package,
-                                        optional_packages)
+    (ebuild_dependencies, remove_target_var) = convert_dependencies(crate_dependencies, filter_target)
     template_info = {
         'copyright_year': datetime.now().year,
+        'remove_target_var': remove_target_var,
         'description': get_description(package),
         'homepage': get_homepage(package),
         'license': convert_license(package['license'], package),
-        'dependencies': dependencies,
+        'dependencies': ebuild_dependencies,
         'autogen_notice': autogen_notice,
     }
 
@@ -365,53 +851,66 @@
     ]).returncode
 
     if ret:
-        print('{} failed to upload to chromeos-localmirror: {}'.format(
-            crate_name, ret))
+        logging.error('Failed to upload "%s" to chromeos-localmirror: %s', crate_name, ret)
 
 
-def update_ebuild(package, args, ebuild_dir, target_dir):
+def update_ebuild(package, args):
     """Update ebuild with generated one and generate MANIFEST."""
-    ebuild_src = get_ebuild_path(package, ebuild_dir)
-    ebuild_dest = get_ebuild_path(package, target_dir, make_dir=True)
+    staging_dir = args.staging_dir
+    ebuild_dir = os.path.join(staging_dir, 'ebuild')
+    target_dir = args.target_dir
+    ebuild_src = get_ebuild_path(package['name'], package['version'], ebuild_dir)
+    ebuild_dest = get_ebuild_path(package['name'], package['version'], target_dir, make_dir=True)
 
-    # Do not overwrite existing ebuilds unless explicity asked to.
+    # TODO make this aware of the revision numbers of existing versions
+    # when doing a replacement.
+
+    # Do not overwrite existing ebuilds unless explicitly asked to.
     if args.overwrite_existing_ebuilds or not os.path.exists(ebuild_dest):
         shutil.copy(ebuild_src, ebuild_dest)
+        upload_gsutil(package, staging_dir, no_upload=args.no_upload)
     else:
-        print('ebuild {} already exists, skipping.'.format(ebuild_dest))
+        logging.info('ebuild %s already exists, skipping.', ebuild_dest)
 
     # Generate manifest w/ ebuild digest
     ret = subprocess.run(['ebuild', ebuild_dest, 'digest']).returncode
     if ret:
-        print('ebuild {} digest failed: {}'.format(ebuild_dest, ret))
+        logging.error('ebuild %s digest failed: %s', ebuild_dest, ret)
 
 
-def process_package(package, args, optional_packages):
-    """Process each package listed in the metadata."""
-    staging_dir = args.staging_dir
+def process_package(package, staging_dir, dep_graph):
+    """Process each package listed in the metadata.
+
+    This includes following:
+    * Setting the package as the root of the dep graph if it is included by source (rather than from crates.io).
+    * Adding the package to the the dep_graph.
+    * Downloading the crate file, so it can be potentially uploaded to localmirror.
+    * Generating an ebuild for the crate in the staging directory.
+    """
     ebuild_dir = os.path.join(staging_dir, 'ebuild')
-    target_dir = args.target_dir
+
+    # Add the user submitted package to the set of required packages.
+    if package.get('source', None) is None:
+        dep_graph.set_root(package)
+    filter_target, crate_dependencies = dep_graph.add_package(package)
 
     download_package(package, staging_dir)
-    package_ebuild(package, ebuild_dir, optional_packages)
+    package_ebuild(package, ebuild_dir, crate_dependencies, filter_target)
 
-    if not args.dry_run and package['name'] not in args.skip:
-        upload_gsutil(package, staging_dir, no_upload=args.no_upload)
-        update_ebuild(package, args, ebuild_dir, target_dir)
 
-def process_empty_package(empty_package, args):
+def process_empty_package(name, version, features, args):
     """Process packages that should generate empty ebuilds."""
     staging_dir = args.staging_dir
     ebuild_dir = os.path.join(staging_dir, 'ebuild')
     target_dir = args.target_dir
 
-    ebuild_src = get_ebuild_path(empty_package, ebuild_dir, make_dir=True)
-    ebuild_dest = get_ebuild_path(empty_package, target_dir, make_dir=True)
+    ebuild_src = get_ebuild_path(name, version, ebuild_dir, make_dir=True)
+    ebuild_dest = get_ebuild_path(name, version, target_dir, make_dir=True)
 
     crate_features = ''
-    if empty_package.get('features', None):
+    if features:
         crate_features = 'CROS_RUST_EMPTY_CRATE_FEATURES=( {} )'.format(
-            ' '.join(['"{}"'.format(x) for x in empty_package['features']]))
+            ' '.join(['"{}"'.format(x) for x in features]))
 
     template_info = {
         'copyright_year': datetime.now().year,
@@ -419,52 +918,66 @@
         'autogen_notice': AUTOGEN_NOTICE,
     }
 
+    logging.debug('Writing empty crate: %s', ebuild_src)
     with open(ebuild_src, 'w') as ebuild:
         ebuild.write(EMPTY_CRATE.format(**template_info))
 
-    if not args.dry_run and empty_package['name'] not in args.skip:
+    # Do not overwrite existing ebuilds unless explicitly asked to.
+    if not args.overwrite_existing_ebuilds and os.path.exists(ebuild_dest):
+        logging.info('ebuild %s already exists, skipping.', ebuild_dest)
+        return
+
+    if not args.dry_run and name not in args.skip:
         shutil.copy(ebuild_src, ebuild_dest)
 
-def check_if_package_is_required(empty_package, args):
-    """Check if an empty package already has a non-empty ebuild."""
-    ebuild_dest = get_ebuild_path(empty_package, args.target_dir, make_dir=False)
-    ebuild_target_dir = os.path.dirname(ebuild_dest)
-
-    # Find all ebuilds in ebuild_target dir and confirm they have
-    # CROS_RUST_EMPTY_CRATE in them. If they do not, they need to be manually
-    # handled.
-    for root, _, files in os.walk(ebuild_target_dir):
-        for efile in files:
-            if not efile.endswith('.ebuild'):
-                continue
-
-            with open(os.path.join(root, efile), 'r') as ebuild:
-                if 'CROS_RUST_EMPTY_CRATE' not in ebuild.read():
-                    print('{} was not an empty crate.'.format(efile))
-                    return True
-
-    return False
 
 def main(argv):
     """Convert dependencies from Cargo.toml into ebuilds."""
     args = parse_args(argv)
 
+    logging_kwargs = {'stream': sys.stderr, 'format': '%(levelname)s: %(message)s'}
+    if args.verbose > 1:
+        logging_kwargs['level'] = logging.DEBUG
+    elif args.verbose > 0:
+        logging_kwargs['level'] = logging.INFO
+    else:
+        logging_kwargs['level'] = logging.WARNING
+    logging.basicConfig(**logging_kwargs)
+
     prepare_staging(args)
 
-    processed_packages = {}
-    optional_packages = {}
+    dep_graph = DepGraph()
     metadata = load_metadata(args.manifest_path)
     for p in metadata['packages']:
-        process_package(p, args, optional_packages)
-        processed_packages[p['name']] = True
+        process_package(p, args.staging_dir, dep_graph)
 
-    for key in optional_packages:
-        try:
-            if key not in processed_packages and not check_if_package_is_required(
-                    optional_packages[key], args):
-                process_empty_package(optional_packages[key], args)
-        except VersionParseError:
-            print('{} has a malformed version'.format(key))
+    dep_graph.find_system_crates(args.target_dir)
+
+    required_packages, optional_packages = dep_graph.flatten(args)
+    if args.verbose > 2:
+        print('Dependency graph:')
+        pprint(dict(dep_graph.graph))
+        print('System versions:')
+        pprint(dict(dep_graph.system_crates))
+    print('Required versions:')
+    pprint(required_packages)
+    print('Optional versions:')
+    pprint(optional_packages)
+
+    for (name, version), features in optional_packages.items():
+        process_empty_package(name, version, features, args)
+
+    if not args.dry_run:
+        for p in metadata['packages']:
+            if p['name'] in args.skip:
+                continue
+            identifier = (p['name'], p['version'])
+            if identifier in required_packages:
+                update_ebuild(p, args)
+        display_dir = args.target_dir
+    else:
+        display_dir = '/'.join((args.staging_dir, 'ebuild'))
+    print('Generated ebuilds can be found in: {}'.format(display_dir))
 
 
 def parse_args(argv):
@@ -473,7 +986,7 @@
     parser.add_argument(
         '-s',
         '--staging-dir',
-        required=True,
+        default='/tmp/cargo2ebuild-staging',
         help='Staging directory for temporary and generated files')
 
     parser.add_argument(
@@ -484,6 +997,7 @@
 
     parser.add_argument('-t',
                         '--target-dir',
+                        default='/mnt/host/source/src/third_party/chromiumos-overlay',
                         help='Path to chromiumos-overlay')
 
     parser.add_argument('-k',
@@ -494,12 +1008,23 @@
                         '--no-upload',
                         action='store_true',
                         help='Skip uploading crates to distfiles')
+    parser.add_argument('-X',
+                        '--no-substitute',
+                        action='store_true',
+                        help='Do not substitute system versions for required crates')
     parser.add_argument('-x',
                         '--overwrite-existing-ebuilds',
                         action='store_true',
-                        help='Skip uploading crates to distfiles')
+                        help='If an ebuild already exists, overwrite it.')
+    parser.add_argument('-v',
+                        '--verbose',
+                        action='count',
+                        default=0,
+                        help='Enable verbose logging')
 
     parser.add_argument('manifest_path',
+                        nargs='?',
+                        default='./Cargo.toml',
                         help='Cargo.toml used to generate ebuilds.')
 
     args = parser.parse_args(argv)