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.