Repository: pypa/pip

Issue:
A git-based package conflicts with itself if it's also a dependency of another package being installed
### Description

A conflict occurs when trying to install packages based on the `requirements.txt` file which has a git-based package and another package that has the same git-based package as a dependency. It happens even if there are no git revisions specified.

What's more, it means that if a git-based package with a git-based dependency is installed, then the `pip freeze` output is unusable because of this conflict. The example of such a package is https://github.com/QuickLogic-Corp/quicklogic-fasm with [its `install_requires`](https://github.com/QuickLogic-Corp/quicklogic-fasm/blob/b86a3f926c84f96e32e6dc51e0679a42d0f98063/setup.py#L23):
```
    install_requires = [
        'fasm @ git+https://github.com/symbiflow/fasm#egg=fasm',
        'fasm-utils @ git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils#egg=fasm-utils'
    ],
```

With such a package installed, the output of `pip freeze` can't be used successfully in `pip install -r`.

### Expected behavior

Packages should be successfully installed.

The conflict is only reasonable if git revisions are specified for the same git-based package and are different. For example, if after resolving dependencies it turns out such packages are going to be installed:
```
fasm-utils @ git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils@REVISION
fasm-utils @ git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils@ANOTHER_REVISION
```
but if only one specifies a revision it should be compatible with a package without a revision specified.

### pip version

21.1.1

### Python version

3.7 / 3.9

### OS

Linux

### How to Reproduce

```
python3 -m pip install git+https://github.com/QuickLogic-Corp/quicklogic-fasm
python3 -m pip freeze >requirements.txt
python3 -m pip uninstall quicklogic-fasm fasm fasm-utils
python3 -m pip install -r requirements.txt
```
but also without git revisions it doesn't work:
```
python3 -m pip install git+https://github.com/QuickLogic-Corp/quicklogic-fasm
python3 -m pip freeze | sed 's#@[^ ]\+##g' >requirements-without-revisions.txt
python3 -m pip uninstall quicklogic-fasm fasm fasm-utils
pip install -r requirements-without-revisions.txt
```

### Output

```sh-session
root@5a910819b958:/# pip install -r requirements.txt 
Collecting fasm@ git+https://github.com/symbiflow/fasm@99f199f9e32fd30c8adffcc73c13caf95a951c35
  Cloning https://github.com/symbiflow/fasm (to revision 99f199f9e32fd30c8adffcc73c13caf95a951c35) to /tmp/pip-install-31i9zc00/fasm_389620f524324d759e68423b3f833b59
  Running command git clone -q https://github.com/symbiflow/fasm /tmp/pip-install-31i9zc00/fasm_389620f524324d759e68423b3f833b59
  Running command git rev-parse -q --verify 'sha^99f199f9e32fd30c8adffcc73c13caf95a951c35'
  Running command git fetch -q https://github.com/symbiflow/fasm 99f199f9e32fd30c8adffcc73c13caf95a951c35
  Running command git submodule update --init --recursive -q
  Installing build dependencies ... done
  Getting requirements to build wheel ... done
    Preparing wheel metadata ... done
Collecting fasm-utils@ git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils@3d6a375ddb6b55aaa5a59d99e44a207d4c18709f
  Cloning https://github.com/QuickLogic-Corp/quicklogic-fasm-utils (to revision 3d6a375ddb6b55aaa5a59d99e44a207d4c18709f) to /tmp/pip-install-31i9zc00/fasm-utils_77d8f9716d15454fbb4dec7204d8caaa
  Running command git clone -q https://github.com/QuickLogic-Corp/quicklogic-fasm-utils /tmp/pip-install-31i9zc00/fasm-utils_77d8f9716d15454fbb4dec7204d8caaa
  Running command git rev-parse -q --verify 'sha^3d6a375ddb6b55aaa5a59d99e44a207d4c18709f'
  Running command git fetch -q https://github.com/QuickLogic-Corp/quicklogic-fasm-utils 3d6a375ddb6b55aaa5a59d99e44a207d4c18709f
Collecting quicklogic-fasm@ git+https://github.com/QuickLogic-Corp/quicklogic-fasm@b86a3f926c84f96e32e6dc51e0679a42d0f98063
  Cloning https://github.com/QuickLogic-Corp/quicklogic-fasm (to revision b86a3f926c84f96e32e6dc51e0679a42d0f98063) to /tmp/pip-install-31i9zc00/quicklogic-fasm_907a7665943043c0909a3200aee79f10
  Running command git clone -q https://github.com/QuickLogic-Corp/quicklogic-fasm /tmp/pip-install-31i9zc00/quicklogic-fasm_907a7665943043c0909a3200aee79f10
  Running command git rev-parse -q --verify 'sha^b86a3f926c84f96e32e6dc51e0679a42d0f98063'
  Running command git fetch -q https://github.com/QuickLogic-Corp/quicklogic-fasm b86a3f926c84f96e32e6dc51e0679a42d0f98063
  Running command git submodule update --init --recursive -q
Requirement already satisfied: Arpeggio==1.10.2 in /usr/local/lib/python3.9/dist-packages (from -r requirements.txt (line 1)) (1.10.2)
Requirement already satisfied: textX==2.3.0 in /usr/local/lib/python3.9/dist-packages (from -r requirements.txt (line 5)) (2.3.0)
Collecting fasm-utils@ git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils#egg=fasm-utils
  Cloning https://github.com/QuickLogic-Corp/quicklogic-fasm-utils to /tmp/pip-install-31i9zc00/fasm-utils_ad67eecd460a46f2878c8cb548170041
  Running command git clone -q https://github.com/QuickLogic-Corp/quicklogic-fasm-utils /tmp/pip-install-31i9zc00/fasm-utils_ad67eecd460a46f2878c8cb548170041
Collecting fasm@ git+https://github.com/symbiflow/fasm#egg=fasm
  Cloning https://github.com/symbiflow/fasm to /tmp/pip-install-31i9zc00/fasm_284e261cc2924e599dcf7ec899bef64e
  Running command git clone -q https://github.com/symbiflow/fasm /tmp/pip-install-31i9zc00/fasm_284e261cc2924e599dcf7ec899bef64e
  Running command git submodule update --init --recursive -q
  Installing build dependencies ... done
  Getting requirements to build wheel ... done
    Preparing wheel metadata ... done
INFO: pip is looking at multiple versions of fasm-utils to determine which version is compatible with other requirements. This could take a while.
INFO: pip is looking at multiple versions of fasm to determine which version is compatible with other requirements. This could take a while.
ERROR: Cannot install -r requirements.txt (line 4) and fasm-utils 0.0.1 (from git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils@3d6a375ddb6b55aaa5a59d99e44a207d4c18709f) because these package versions have conflicting dependencies.

The conflict is caused by:
    The user requested fasm-utils 0.0.1 (from git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils@3d6a375ddb6b55aaa5a59d99e44a207d4c18709f)
    quicklogic-fasm 0.0.1 depends on fasm-utils 0.0.1 (from git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils#egg=fasm-utils)

To fix this you could try to:
1. loosen the range of package versions you've specified
2. remove package versions to allow pip attempt to solve the dependency conflict

ERROR: ResolutionImpossible: for help visit https://pip.pypa.io/en/latest/user_guide/#fixing-conflicting-dependencies



Without git revisions in `requirements.txt` the conflict information makes even less sense:

The conflict is caused by:
    The user requested fasm-utils 0.0.1 (from git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils)
    quicklogic-fasm 0.0.1 depends on fasm-utils 0.0.1 (from git+https://github.com/QuickLogic-Corp/quicklogic-fasm-utils#egg=fasm-utils)
```


### Code of Conduct

- [X] I agree to follow the [PSF Code of Conduct](https://www.python.org/psf/conduct/).

Discussion:
uranusjr: Still hoping someone could take a look. I detailed the logic in the docstring, a brief browse would be much appreciated.

Patch:
diff --git a/news/10002.feature.rst b/news/10002.feature.rst
new file mode 100644
index 000000000..b55d8577e
--- /dev/null
+++ b/news/10002.feature.rst
@@ -0,0 +1,7 @@
+New resolver: Loosen URL comparison logic when checking for direct URL reference
+equivalency. The logic includes the following notable characteristics:
+
+* The authentication part of the URL is explicitly ignored.
+* Most of the fragment part, including ``egg=``, is explicitly ignored. Only
+  ``subdirectory=`` and hash values (e.g. ``sha256=``) are kept.
+* The query part of the URL is parsed to allow ordering differences.
diff --git a/src/pip/_internal/models/link.py b/src/pip/_internal/models/link.py
index 411cfb624..770bdd304 100644
--- a/src/pip/_internal/models/link.py
+++ b/src/pip/_internal/models/link.py
@@ -1,8 +1,10 @@
+import functools
+import logging
 import os
 import posixpath
 import re
 import urllib.parse
-from typing import TYPE_CHECKING, Optional, Tuple, Union
+from typing import TYPE_CHECKING, Dict, List, NamedTuple, Optional, Tuple, Union
 
 from pip._internal.utils.filetypes import WHEEL_EXTENSION
 from pip._internal.utils.hashes import Hashes
@@ -17,6 +19,11 @@ from pip._internal.utils.urls import path_to_url, url_to_path
 if TYPE_CHECKING:
     from pip._internal.index.collector import HTMLPage
 
+logger = logging.getLogger(__name__)
+
+
+_SUPPORTED_HASHES = ("sha1", "sha224", "sha384", "sha256", "sha512", "md5")
+
 
 class Link(KeyBasedCompareMixin):
     """Represents a parsed link from a Package Index's simple URL
@@ -159,7 +166,7 @@ class Link(KeyBasedCompareMixin):
         return match.group(1)
 
     _hash_re = re.compile(
-        r'(sha1|sha224|sha384|sha256|sha512|md5)=([a-f0-9]+)'
+        r'({choices})=([a-f0-9]+)'.format(choices="|".join(_SUPPORTED_HASHES))
     )
 
     @property
@@ -218,6 +225,61 @@ class Link(KeyBasedCompareMixin):
         return hashes.is_hash_allowed(self.hash_name, hex_digest=self.hash)
 
 
-# TODO: Relax this comparison logic to ignore, for example, fragments.
+class _CleanResult(NamedTuple):
+    """Convert link for equivalency check.
+
+    This is used in the resolver to check whether two URL-specified requirements
+    likely point to the same distribution and can be considered equivalent. This
+    equivalency logic avoids comparing URLs literally, which can be too strict
+    (e.g. "a=1&b=2" vs "b=2&a=1") and produce conflicts unexpecting to users.
+
+    Currently this does three things:
+
+    1. Drop the basic auth part. This is technically wrong since a server can
+       serve different content based on auth, but if it does that, it is even
+       impossible to guarantee two URLs without auth are equivalent, since
+       the user can input different auth information when prompted. So the
+       practical solution is to assume the auth doesn't affect the response.
+    2. Parse the query to avoid the ordering issue. Note that ordering under the
+       same key in the query are NOT cleaned; i.e. "a=1&a=2" and "a=2&a=1" are
+       still considered different.
+    3. Explicitly drop most of the fragment part, except ``subdirectory=`` and
+       hash values, since it should have no impact the downloaded content. Note
+       that this drops the "egg=" part historically used to denote the requested
+       project (and extras), which is wrong in the strictest sense, but too many
+       people are supplying it inconsistently to cause superfluous resolution
+       conflicts, so we choose to also ignore them.
+    """
+
+    parsed: urllib.parse.SplitResult
+    query: Dict[str, List[str]]
+    subdirectory: str
+    hashes: Dict[str, str]
+
+    @classmethod
+    def from_link(cls, link: Link) -> "_CleanResult":
+        parsed = link._parsed_url
+        netloc = parsed.netloc.rsplit("@", 1)[-1]
+        fragment = urllib.parse.parse_qs(parsed.fragment)
+        if "egg" in fragment:
+            logger.debug("Ignoring egg= fragment in %s", link)
+        try:
+            # If there are multiple subdirectory values, use the first one.
+            # This matches the behavior of Link.subdirectory_fragment.
+            subdirectory = fragment["subdirectory"][0]
+        except (IndexError, KeyError):
+            subdirectory = ""
+        # If there are multiple hash values under the same algorithm, use the
+        # first one. This matches the behavior of Link.hash_value.
+        hashes = {k: fragment[k][0] for k in _SUPPORTED_HASHES if k in fragment}
+        return cls(
+            parsed=parsed._replace(netloc=netloc, query="", fragment=""),
+            query=urllib.parse.parse_qs(parsed.query),
+            subdirectory=subdirectory,
+            hashes=hashes,
+        )
+
+
+@functools.lru_cache(maxsize=None)
 def links_equivalent(link1: Link, link2: Link) -> bool:
-    return link1 == link2
+    return _CleanResult.from_link(link1) == _CleanResult.from_link(link2)


Test patch:
diff --git a/tests/functional/test_install_reqs.py b/tests/functional/test_install_reqs.py
index d8de6248b..6df489275 100644
--- a/tests/functional/test_install_reqs.py
+++ b/tests/functional/test_install_reqs.py
@@ -423,7 +423,7 @@ def test_constraints_constrain_to_local(script, data, resolver_variant):
     assert 'Running setup.py install for singlemodule' in result.stdout
 
 
-def test_constrained_to_url_install_same_url(script, data, resolver_variant):
+def test_constrained_to_url_install_same_url(script, data):
     to_install = data.src.joinpath("singlemodule")
     constraints = path_to_url(to_install) + "#egg=singlemodule"
     script.scratch_path.joinpath("constraints.txt").write_text(constraints)
@@ -431,17 +431,8 @@ def test_constrained_to_url_install_same_url(script, data, resolver_variant):
         'install', '--no-index', '-f', data.find_links, '-c',
         script.scratch_path / 'constraints.txt', to_install,
         allow_stderr_warning=True,
-        expect_error=(resolver_variant == "2020-resolver"),
     )
-    if resolver_variant == "2020-resolver":
-        assert 'Cannot install singlemodule 0.0.1' in result.stderr, str(result)
-        assert (
-            'because these package versions have conflicting dependencies.'
-            in result.stderr
-        ), str(result)
-    else:
-        assert ('Running setup.py install for singlemodule'
-                in result.stdout), str(result)
+    assert 'Running setup.py install for singlemodule' in result.stdout, str(result)
 
 
 def test_double_install_spurious_hash_mismatch(
diff --git a/tests/functional/test_new_resolver.py b/tests/functional/test_new_resolver.py
index 74191dbf3..5cc820453 100644
--- a/tests/functional/test_new_resolver.py
+++ b/tests/functional/test_new_resolver.py
@@ -1777,6 +1777,96 @@ def test_new_resolver_avoids_incompatible_wheel_tags_in_constraint_url(
     assert_not_installed(script, "dep")
 
 
+@pytest.mark.parametrize(
+    "suffixes_equivalent, depend_suffix, request_suffix",
+    [
+        pytest.param(
+            True,
+            "#egg=foo",
+            "",
+            id="drop-depend-egg",
+        ),
+        pytest.param(
+            True,
+            "",
+            "#egg=foo",
+            id="drop-request-egg",
+        ),
+        pytest.param(
+            True,
+            "#subdirectory=bar&egg=foo",
+            "#subdirectory=bar&egg=bar",
+            id="drop-egg-only",
+        ),
+        pytest.param(
+            True,
+            "#subdirectory=bar&egg=foo",
+            "#egg=foo&subdirectory=bar",
+            id="fragment-ordering",
+        ),
+        pytest.param(
+            True,
+            "?a=1&b=2",
+            "?b=2&a=1",
+            id="query-opordering",
+        ),
+        pytest.param(
+            False,
+            "#sha512=1234567890abcdef",
+            "#sha512=abcdef1234567890",
+            id="different-keys",
+        ),
+        pytest.param(
+            False,
+            "#sha512=1234567890abcdef",
+            "#md5=1234567890abcdef",
+            id="different-values",
+        ),
+        pytest.param(
+            False,
+            "#subdirectory=bar&egg=foo",
+            "#subdirectory=rex",
+            id="drop-egg-still-different",
+        ),
+    ],
+)
+def test_new_resolver_direct_url_equivalent(
+    tmp_path,
+    script,
+    suffixes_equivalent,
+    depend_suffix,
+    request_suffix,
+):
+    pkga = create_basic_wheel_for_package(script, name="pkga", version="1")
+    pkgb = create_basic_wheel_for_package(
+        script,
+        name="pkgb",
+        version="1",
+        depends=[f"pkga@{path_to_url(pkga)}{depend_suffix}"],
+    )
+
+    # Make pkgb visible via --find-links, but not pkga.
+    find_links = tmp_path.joinpath("find_links")
+    find_links.mkdir()
+    with open(pkgb, "rb") as f:
+        find_links.joinpath(pkgb.name).write_bytes(f.read())
+
+    # Install pkgb from --find-links, and pkga directly but from a different
+    # URL suffix as specified in pkgb. This should work!
+    script.pip(
+        "install",
+        "--no-cache-dir", "--no-index",
+        "--find-links", str(find_links),
+        f"{path_to_url(pkga)}{request_suffix}", "pkgb",
+        expect_error=(not suffixes_equivalent),
+    )
+
+    if suffixes_equivalent:
+        assert_installed(script, pkga="1", pkgb="1")
+    else:
+        assert_not_installed(script, "pkga", "pkgb")
+
+
 def test_new_resolver_direct_url_with_extras(tmp_path, script):
     pkg1 = create_basic_wheel_for_package(script, name="pkg1", version="1")
     pkg2 = create_basic_wheel_for_package(
diff --git a/tests/unit/test_link.py b/tests/unit/test_link.py
index a9e75e38b..77f569333 100644
--- a/tests/unit/test_link.py
+++ b/tests/unit/test_link.py
@@ -1,6 +1,6 @@
 import pytest
 
-from pip._internal.models.link import Link
+from pip._internal.models.link import Link, links_equivalent
 from pip._internal.utils.hashes import Hashes
 
 
@@ -138,3 +138,56 @@ class TestLink:
     def test_is_vcs(self, url, expected):
         link = Link(url)
         assert link.is_vcs is expected
+
+
+@pytest.mark.parametrize(
+    "url1, url2",
+    [
+        pytest.param(
+            "https://example.com/foo#egg=foo",
+            "https://example.com/foo",
+            id="drop-egg",
+        ),
+        pytest.param(
+            "https://example.com/foo#subdirectory=bar&egg=foo",
+            "https://example.com/foo#subdirectory=bar&egg=bar",
+            id="drop-egg-only",
+        ),
+        pytest.param(
+            "https://example.com/foo#subdirectory=bar&egg=foo",
+            "https://example.com/foo#egg=foo&subdirectory=bar",
+            id="fragment-ordering",
+        ),
+        pytest.param(
+            "https://example.com/foo?a=1&b=2",
+            "https://example.com/foo?b=2&a=1",
+            id="query-opordering",
+        ),
+    ],
+)
+def test_links_equivalent(url1, url2):
+    assert links_equivalent(Link(url1), Link(url2))
+
+
+@pytest.mark.parametrize(
+    "url1, url2",
+    [
+        pytest.param(
+            "https://example.com/foo#sha512=1234567890abcdef",
+            "https://example.com/foo#sha512=abcdef1234567890",
+            id="different-keys",
+        ),
+        pytest.param(
+            "https://example.com/foo#sha512=1234567890abcdef",
+            "https://example.com/foo#md5=1234567890abcdef",
+            id="different-values",
+        ),
+        pytest.param(
+            "https://example.com/foo#subdirectory=bar&egg=foo",
+            "https://example.com/foo#subdirectory=rex",
+            id="drop-egg-still-different",
+        ),
+    ],
+)
+def test_links_equivalent_false(url1, url2):
+    assert not links_equivalent(Link(url1), Link(url2))