Graphs: immutable/unmodifiable operations should consistently throw UOE whether or not data would actually change

[perceptron8]

I know that may be several other options for the semantics besides mentioned at https://github.com/google/guava/wiki/GraphsExplained#accessor-behavior, and that "generally using" one of them is not a strict guarantee of any kind, nevertheless behavior, that I've encountered today, surprised me a lot.

Accessor behavior

For accessors that return a collection, there are several options for the semantics, including:

(...) 2. Collection is an unmodifiable view (e.g. Collections.unmodifiableSet()): attempts to modify the collection in any way will throw an exception [emphasis added], and modifications to the graph will be reflected in the collection. (...)

(...); as of this writing, the built-in implementations generally use (2).

My general impression was that ImmutableGraph.nodes(), ImmutableGraph.edges() and other views should behave as if they were Collections.unmodifiableSet(). This is not always true as I will show.

@Test
public void emptyNodesAreUnmodifiable() {
	ImmutableGraph<?> graph = GraphBuilder.undirected().immutable().build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.nodes().clear(); });
}

@Test
public void nonEmptyNodesAreUnmodifiable() {
	ImmutableGraph<?> graph = GraphBuilder.undirected().immutable().addNode(1).build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.nodes().clear(); });
}

@Test
public void emptyEdgesAreUnmodifiable() {
	ImmutableGraph<?> graph = GraphBuilder.undirected().immutable().build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.edges().clear(); });
}

@Test
public void nonEmptyEdgesAreUnmodifiable() {
	ImmutableGraph<?> graph = GraphBuilder.undirected().immutable().putEdge(1, 2).build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.edges().clear(); });
}

Two of the above are failing: emptyNodesAreUnmodifiable() and emptyEdgesAreUnmodifiable().

Nothing happens when clear() is being invoked on empty view. I believe this is indeed an attempt to modify the collection, so UnsupportedOperationException should be thrown.

If you would like to make some changes, please remember about remove* and retainAll methods.

---

Probably related discussion on even stronger guarantees: #3480

[perceptron8]

It's the same for other views returned by ImmutableGraph. All of the following tests are failing.

@Test
public void emptyPredecessorsAreUnmodifiable() {
	ImmutableGraph<Integer> graph = GraphBuilder.directed().<Integer>nodeOrder(ElementOrder.unordered()).immutable().addNode(1).build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.predecessors(1).clear(); });
}

@Test
public void emptySuccessorsAreUnmodifiable() {
	ImmutableGraph<Integer> graph = GraphBuilder.directed().<Integer>nodeOrder(ElementOrder.unordered()).immutable().addNode(1).build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.successors(1).clear(); });
}

@Test
public void emptyAdjacentNodesAreUnmodifiable() {
	ImmutableGraph<Integer> graph = GraphBuilder.directed().<Integer>nodeOrder(ElementOrder.unordered()).immutable().addNode(1).build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.adjacentNodes(1).clear(); });
}

@Test
public void emptyIncidentEdgesAreUnmodifiable() {
	ImmutableGraph<Integer> graph = GraphBuilder.undirected().<Integer>immutable().addNode(1).build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.incidentEdges(1).clear(); });
}

Sometimes it depends if graph is directed or not, or what element order it uses. It seems that the problem results from the use of anonymous AbstractSets in most of views implementations. The most obvious (naive maybe?) solution would be to override all of the view-related accessors in ImmutableGraph and wrap sets returned by superclasses with Collections.unmodifiableSet().

The same problem likely applies to all (?) ImmutableValueGraph and ImmutableNetwork views, e.g. nodes().

@Test
public void emptyValueGraphNodesAreUnmodifiable() {
	ImmutableValueGraph<?, ?> graph = ValueGraphBuilder.undirected().immutable().build();
	assertThrows(UnsupportedOperationException.class, () -> { graph.nodes().clear(); });
}
	
@Test
public void emptyNetworkNodesAreUnmodifiable() {
	ImmutableNetwork<?, ?> network = NetworkBuilder.undirected().immutable().build();
	assertThrows(UnsupportedOperationException.class, () -> { network.nodes().clear(); });
}

[kevinb9n]

Even for collections, this has always been a philosophical gray area. The general specification for remove, for example, is really "remove IF found". The general dictionary meanings of "immutable" and "unmodifiable" are about preventing actual change to the data.

java.util.Collection has this to say: "These methods may, but are not required to, throw an UnsupportedOperationException if the invocation would have no effect on the collection."

And re: graphs, the text that you boldfaced is perfectly accurate depending on whether one considers it an actual "attempt" to modify data or not.

With that said, I do think that the behavior you're asking for is slightly better. It's better to always fail on a "structurally" invalid request even though it "just happened to be harmless" in these particular circumstances. Not doing so can create a "time bomb" in the code.

[jrtom]

Somehow I overlooked this issue while I was still at Google; oops. A few quick thoughts:

(1) Since @perceptron8 filed this issue, the documented behavior for the accessor methods has been updated to state simply that

For Guava 33.1.0+, all implementations of the graph types are contractually required to return unmodifiable views that become invalid if their arguments are removed from the graph.

(That is, Guava is no longer saying that other behaviors are contractually OK for implementations of the common.graph interfaces.)

(2) Anyone that's trying to modify any common.graph graph by modifying those Sets is going to have a bad time: the implementations don't listen for modifications to those Sets, and so if they could be modified, the implementations' internal data structures would become inconsistent.

(3) For these reasons among others, I tend to agree with @kevinb9n: while the existing behavior is technically correct (UOE is not required to be thrown), it's better to throw if someone tries to modify those sets. And because of (2), arguably we ought to be throwing for attempts to modify any of the returned view Sets, not just the ones provided by the Immutable* classes.