Contract of Collection.contains violated in AbstractBaseGraph.edges

[h908714124]

Let p be an EndpointPair<Integer>. The method AbstractBaseGraph#edges can return a Set<EndpointPair<Integer>> edges for which edges.contains(p) is true, but e.equals(p) is false for each element e. This violates the contract of java.util.Collection#contains:

Returns true if this collection contains the specified element. More formally, returns true if and only if this collection contains at least one element e such that Objects.equals(o, e).

Note the failing assertion in the following test:

@Test
public void contains_contract_violated() {
    MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().build();
    undirectedGraph.putEdge(1, 2);
    Set<EndpointPair<Integer>> edges = undirectedGraph.edges();
    EndpointPair<Integer> ordered = EndpointPair.ordered(1, 2);
    Assertions.assertTrue(edges.contains(ordered));
    Assertions.assertTrue(edges.stream().anyMatch(ordered::equals)); // fails
}

[h908714124]

The Graph implementation that is returned by AbstractNetwork#asGraph has a similar problem. Note that this anonymous inner class does not extend AbstractBaseGraph.

@Test
public void network_asGraph_similar_issue() {
    MutableNetwork<Integer, String> network = NetworkBuilder.undirected()
            .build();
    network.addEdge(1, 2, "1-2");
    Graph<Integer> graph = network.asGraph();
    Set<EndpointPair<Integer>> edges = graph.edges();
    EndpointPair<Integer> ordered = EndpointPair.ordered(1, 2);
    Assertions.assertTrue(edges.contains(ordered));
    Assertions.assertTrue(edges.stream().anyMatch(ordered::equals)); // fails
}

[jbduncan]

I've investigated this a bit out of interest, and I think the problem is that AbstractBaseGraph#edges returns a custom set with an unusual contains implementation.

guava/guava/src/com/google/common/graph/AbstractBaseGraph.java

Lines 86 to 96 in 448e326

	@SuppressWarnings("unchecked")
	@Override
	public boolean contains(@CheckForNull Object obj) {
	if (!(obj instanceof EndpointPair)) {
	return false;
	}
	EndpointPair<?> endpointPair = (EndpointPair<?>) obj;
	return isOrderingCompatible(endpointPair)
	&& nodes().contains(endpointPair.nodeU())
	&& successors((N) endpointPair.nodeU()).contains(endpointPair.nodeV());
	}

Specifically, it uses a custom method: isOrderingCompatible, which compares the ordering of a given EndpointPair differently to EndpointPair#equals.

guava/guava/src/com/google/common/graph/AbstractBaseGraph.java

Lines 180 to 182 in 448e326

	protected final boolean isOrderingCompatible(EndpointPair<?> endpoints) {
	return endpoints.isOrdered() || !this.isDirected();
	}

By comparison, here's the javadoc for EndpointPair#equals.

guava/guava/src/com/google/common/graph/EndpointPair.java

Lines 131 to 137 in 448e326

	/**
	* Two ordered {@link EndpointPair}s are equal if their {@link #source()} and {@link #target()}
	* are equal. Two unordered {@link EndpointPair}s are equal if they contain the same nodes. An
	* ordered {@link EndpointPair} is never equal to an unordered {@link EndpointPair}.
	*/
	@Override
	public abstract boolean equals(@CheckForNull Object obj);

[jbduncan]

For clarity, I've investigated GraphBuilder.undirected(), but not NetworkBuilder.undirected().

[jbduncan]

I suppose the next question is: is this difference to the Collection#contains contract intended?

I can see an advantage to the current approach. It allows all these assertions to pass:

  @Test
  public void test1() {
    MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().build();
    undirectedGraph.putEdge(1, 2);
    assertThat(undirectedGraph.edges().contains(EndpointPair.ordered(1, 2))).isTrue(); // passes
    assertThat(undirectedGraph.edges().contains(EndpointPair.ordered(2, 1))).isTrue(); // passes
    assertThat(undirectedGraph.edges().contains(EndpointPair.unordered(1, 2))).isTrue(); // passes
    assertThat(undirectedGraph.edges().contains(EndpointPair.unordered(2, 1))).isTrue(); // passes
  } 

By comparison, using EndpointPair#equals:

  @Test
  public void test2() {
    MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().build();
    undirectedGraph.putEdge(1, 2);
    EndpointPair<Integer> undirectedEdge = undirectedGraph.edges().iterator().next();
    assertThat(undirectedEdge.equals(EndpointPair.ordered(1, 2))).isTrue(); // fails
    assertThat(undirectedEdge.equals(EndpointPair.ordered(2, 1))).isTrue(); // fails
    assertThat(undirectedEdge.equals(EndpointPair.unordered(1, 2))).isTrue(); // passes
    assertThat(undirectedEdge.equals(EndpointPair.unordered(2, 1))).isTrue(); // passes
  }

@jrtom Do you have any thoughts on this? I hope you don't mind me including you in this discussion.

[cpovirk]

I haven't been involved in this, but it was interesting enough that I skimmed through the history.

It looks like this used to be "correct" but was pretty explicitly "broken" by a subsequent change. The change was definitely intended to make different EndpointPair instances more easily interchangeable, so it was "intentional" in some sense, but I'm not sure that contains behavior specifically came up in the discussion, as I think there were many methods involved.

I would default to saying that this is "wrong," but there have been so many tricky tradeoffs involved in the design of common.graph that I can easily imagine that this ends up being a lesser evil.

[cpovirk]

I'm able to change isOrderingCompatible to endpoints.isOrdered() == this.isDirected() without breaking anything in Google's codebase except our own tests. That's still not to say that we should do that, just that a lot of breakages would have been practically prevented us from changing the behavior.

[h908714124]

There's an interesting method in TestUtil.
Seems like the original intention was to implement Set according to specs:

/**
 * In some cases our graph implementations return custom sets that define their own size() and
 * contains(). Verify that these sets are consistent with the elements of their iterator.
 */
static <T> Set<T> sanityCheckSet(Set<T> set) {
    assertThat(set).hasSize(Iterators.size(set.iterator()));
    for (Object element : set) {
        assertThat(set).contains(element);
    }
    assertThat(set).doesNotContain(new Object());
    assertThat(set).isEqualTo(Util.setOf(set));
    return set;
}

[jrtom]

@h908714124 thanks for the catch. This is a bug. It arose from a bug fix, but @cpovirk is correct that the behavior of contains() didn't specifically come up in the review (@cpovirk, the API review which led to this change included "endpoint ordering mismatches" in the title if you want to look it up).

@jbduncan thanks for the analysis; you are correct about the cause.

The original review was about fixing undefined behavior for mutations involving the case where someone added an unordered EndpointPair to a directed graph (the behavior is undefined, because the assignment of “nodeU” and “nodeV” to the endpoints is arbitrary).

Unfortunately, I think that I got a bit too cute with the solution (and I don't think any of the reviewers noticed the problem). Technically adding an ordered edge <u, v> to an undirected graph is...not invalid, because the graph can simply ignore the directionality of the endpoints. Our mistake was that we should not have (implicitly) concluded that you can say that the resultant graph contains a directed edge <u, v> if there is an undirected edge connecting u and v.

As @h908714124 pointed out, we should not have defined contains() in such a way as to be inconsistent with equals() (that's clearly a violation of the Set contract as well as being weird) and it is also clear that an unordered EndpointPair should never be equal to an ordered EndpointPair. Therefore we need to fix the contains() behavior.

@cpovirk, since you've apparently already identified the failing tests (which implies that you have a CL with this change), I'd be happy to review a fix for this. Otherwise I'll try to get to it.

[cpovirk]

Sadly, I have a CL that blindly changes how isOrderingCompatible works (CL 417851751), not one that targets the behavior in edges. Maybe the real fix is as simple as changing the edges method's call to isOrderingCompatible. But I am happy to leave that to you to maybe get to sometime... :)

[jrtom]

You're right that we can't simply change how isOrderingCompatible works because the semantics (as conceived in that API review) are different for mutation and for edges.contains(), as noted above.

This method is also used for hasEdgeConnecting():

@Override
  public boolean hasEdgeConnecting(EndpointPair<N> endpoints) {
    checkNotNull(endpoints);
    if (!isOrderingCompatible(endpoints)) {
      return false;
    }
    N nodeU = endpoints.nodeU();
    N nodeV = endpoints.nodeV();
    return nodes().contains(nodeU) && successors(nodeU).contains(nodeV);
  }

whose contract specifies:

/**
   * Returns true if there is an edge that directly connects {@code endpoints} (in the order, if
   * any, specified by {@code endpoints}). This is equivalent to {@code
   * edges().contains(endpoints)}.

This implies that the semantic change needed for edges().contains() would also need to apply to hasEdgeConnecting(). This would leave Mutable*.{add,put}Edge() as the only place where one can supply an ordered edge to an undirected graph and have it "work".

At that point, I'm not 100% sure whether it makes sense to continue special-casing mutations in that way. Would be interested in hearing other opinions on this.

[jbduncan]

Do Google's internal search tools allow queries like the following?

How much code do we have like graph.edges().contains(endpointPair) or graph.putEdge(endpointPair), where graph is an instance of Graph, ValueGraph or Network, and graph.isDirected() != endpointPair.isOrdered()?

If so, I think this would allow the potential disruption of any change to be measured.

Otherwise, my gut feeling is for directedGraph.edges().contains(undirectedEndpointPair) to always be false, and for directedGraph.putEdge(undirectedEndpointPair) to never "work".

[jrtom]

Thanks, @jbduncan.

How much code do we have like graph.edges().contains(endpointPair) or graph.putEdge(endpointPair), where graph is an instance of Graph, ValueGraph or Network, and graph.isDirected() != endpointPair.isOrdered()?

As far as I can tell, neither of these cases exist in Google's code base. However, that doesn't tell us whether they exist in the rest of the world. :)

Otherwise, my gut feeling is for directedGraph.edges().contains(undirectedEndpointPair) to always be false

I think we've settled on this change: that was the original subject of this issue, and I agree that we need to not violate the Set.contains() contract. Since we have an existing contract for hasEdgeConnecting() that requires that it be consistent with edges().contains(), that means that behavior needs to change as well.

and for directedGraph.putEdge(undirectedEndpointPair) to never "work".

This is the remaining question, yes. :)

[jrtom]

Fix applied above per #6058.

The practical results:

• It is no longer legal to add directed edges to undirected graphs (they will now not be silently interpreted as undirected, but will instead throw an IllegalArgumentException).
• Undirected graphs will no longer (improperly) report that they contain any directed edges.

As a result, all ordering/directionality mismatches are handled identically, rather than allowing undirected graphs to be more permissive than directed graphs.