Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Let's say I wanted to create a Java List<String> (see spec) implementation that uses a complex subsystem, such as a database or file system, for its store so that it acts as a persistent collection rather than an in-memory one.

So here's a skeleton implementation:

class DbBackedList implements List<String> {
  private DbBackedList() {}
  /** Returns a list, possibly non-empty */
  public static getList() { return new DbBackedList(); }
  public String get(int index) {
    return Db.getTable().getRow(i).asString();  // may throw DbExceptions!
  }
  // add(String), add(int, String), etc. ...
}

My problem lies with the fact that the underlying DB API may encounter connection errors that are not specified in the List interface that it should throw.

My problem is whether this violates Liskov's Substitution Principle (LSP).

In his paper on LSP, Bob Martin actually gives an example of a PersistentSet that violates LSP. The difference is that his newly-specified Exception there is determined by the inserted value and so is strengthening the precondition. In my case the connection/read error is unpredictable and due to external factors and so is not technically a new precondition, merely an error of circumstance, perhaps like OutOfMemoryError which can occur even when unspecified.

In normal circumstances, the new Error/Exception might never be thrown. (The caller could catch if it is aware of the possibility, just as a memory-restricted Java program might specifically catch OOME.)

Is this therefore a valid argument for throwing an extra error and can I still claim to be a valid java.util.List (or pick your SDK/language/collection in general) and not in violation of LSP?

Edit: This argument might be more palatable if you consider a FileBackedList (more reliable "connection") rather than a DbBackedList.

If this does indeed violate LSP and thus not practically usable, I have provided two less-palatable alternative solutions as answers that you can comment on, see below.


Footnote: Use Cases

In the simplest case, the goal is to provide a familiar interface for cases when (say) a database is just being used as a persistent list, and allow regular List operations such as search, subList and iteration.

Another, more adventurous, use-case is as a slot-in replacement for libraries that work with basic Lists, e.g if we have a third-party task queue that usually works with a plain List:
new TaskWorkQueue(new ArrayList<String>()).start() which is susceptible to losing all it's queue in event of a crash, if we just replace this with:
new TaskWorkQueue(new DbBackedList()).start() we get a instant persistence and the ability to share the tasks amongst more than one machine.

In either case, we could either handle connection/read exceptions that are thrown, perhaps retrying the connection/read first, or allow them to throw and crash the program (e.g. if we can't change the TaskWorkQueue code).

share|improve this question
    
What will happen if a user tries to do things to your list like removing items or sorting it? –  Brian Nov 11 '13 at 15:22
    
It will behave as expected: remove the item from the underlying storage (assuming it implements remove() instead of throwing UnsupportedOperationException), or sort the entire thing respectively. –  Motti Strom Nov 11 '13 at 15:50
    
Since every call to get is calling DB.getTable(), that implies that sorting is impacting the underlying Database. I'm a bit leery of the implications. –  Brian Nov 11 '13 at 16:29
    
Fair enough, but if you wanted a sorted collection, I would recommend my wonderful (and hypothetical) DbBackedSortedSet instead (which may rely on the DB's sorted indexes) :) You shouldn't just sort any list anyway without understanding the implementation, e.g. sorting a LinkedList is expensive in either time or memory. –  Motti Strom Nov 11 '13 at 17:18
    
My point was that your choice is either A) The order of your List isn't maintained or B) Sorting your list impacts the database. Choice A is a direct violation of LSP, since, per the documentation, List<E> is "An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted." Choice B might not violate LSP, but it seems a bit odd. The answers are ignoring add(int index, E element), since you didn't mention it. –  Brian Nov 11 '13 at 17:34

4 Answers 4

The reason why his example is a violation of LSP is not because of the exception per se, it is the reason for the exception -- it is changing the contract.

A simpler, but more contrived example -- you have a List of ints, you decide you want to use it for a list of elementary grades completed, with a check to make sure that the numbers are within the required range, so you subclass ListInt as ListIntElementary. ListIntElementary violates LSP.

You, on the other hand, have real world constraints that wouldn't apply to the base class, but your subclass can algorithmically be used anywhere the base class can, it accepts all acceptable inputs, returns only acceptable values. Exceptions are neither input nor output in the LSP sense.

A new exception or new cause for an old exception (if you can find one that maps cleanly) is an implementation detail, not a violation of LSP. It may mean that in practice that it is unsuitable as a replacement for the base class, but in theory once created, it can be used everywhere that the base class can be used.

In short, this is fine.

share|improve this answer
1  
+1 don't worry too much about the LSP. The additional exception is truly exceptional, ie, there is nothing the client code can do anyway. Certainly don't make your code more complicated just because of this. If you really really must (I add this only for completeness), you have another option: throw a (subtype of) error, any error may occur at any time. –  Cephalopod Nov 10 '13 at 20:16
    
@Arian It'd be better to not conflate lists with database access. They have nothing to do with each other. –  Doval Apr 10 at 12:13

To start with, your DBException hardly qualifies as Error:

subclasses of Error... are abnormal conditions that should never occur.

Note also that if you expect DBException to be thrown in overridden get, it must be unchecked one. Otherwise, your code won't compile, per JLS 8.4.8.3. Requirements in Overriding and Hiding:

A method that overrides or hides another method, including methods that implement abstract methods defined in interfaces, may not be declared to throw more checked exceptions than the overridden or hidden method...


With above said, it looks like yes, it would violate LSP - because as a user of Java Collections Framework, I would not expect List.get to throw runtime exception for any kind problem other than "programming mistakes", that is for something that is possible to avoid by changing the code (note, no matter how you change code, database connection won't be guaranteed).

If you look at the IndexOutOfBoundsException specified for List.get, it reads like one that programmer can avoid by preliminary bounds check:

if the index is out of range (index < 0 || index >= size())

Another runtime exception documented for Collections, including List, is ConcurrentModificationException and per API docs, it is also expected to be dealt with by correcting the code that caused it:

ConcurrentModificationException should be used only to detect bugs.

More detailed explanation for what I expect is provided in JCF Design FAQ. It addresses UnsupportedOperationException, but if you take a look at prior examples of IOOBE and CME, the reasoning fits these as well:

Won't programmers have to surround any code that calls optional operations with a try-catch clause in case they throw an UnsupportedOperationException?

It was never our intention that programs should catch these exceptions: that's why they're unchecked (runtime) exceptions. They should only arise as a result of programming errors, in which case, your program will halt due to the uncaught exception.


Suming up, if I wanted to expose database backed data as List (or any Collection for that matter) in a way that would be least confusing for users of my API, I would probably wrap that data into some helper object that would expose DB related exceptions only when used "outside" of collection context - that is, when client code would try to access the data expected to be stored "inside" the wrapper, not when collections of wrappers are carried over the client code.

For a concrete example how this could be done, take a look at java.util.concurrent.Future which wraps results of an asynchronous computation in a way that doesn't expose "internal", wrapped exceptions when carried over in collections.

share|improve this answer
    
Yes, that was roughly my alternative in the answer I self-posted (DbString). Would you consider it still a violation of LSP if the DbException was thrown as an IndexOutOfBoundsException? Also, if it wasn't a database, but an in-memory store that very occasionally may fail, would you still not consider it an Error? –  Motti Strom Nov 11 '13 at 14:18
    
@MottiStrom your DbString looks OK, I'd maybe only use name get instead of getString - following the naming used in Future API. Masquerading (subclassing) DbException as IOOBE would likely violate LSP - as I mentioned, IOOBE is generally expected to be something one can avoid by checking index, but DbException isn't like that. As for in-memory store, throwing Error for it is definitely worth considering (note how reasoning about db connection doesn't apply to it anymore). –  gnat Nov 11 '13 at 14:30
    
Btw instead of subclassing, it could wrap i.e. throw new IOOBE(dbException) but fair enough, that's not necessarily in the spirit of the precondition. Your quote of the Error doc is from the paragraph about when to declare the error in a @throws clause. The first para says "Most such errors are abnormal conditions". Even with your reading of Error, it's hard to say definitively whether a rare error thrown by reliable database (call that a new precondition for LSP's sake) is that much more abnormal than an occasionally-failing in-memory store. What would you say to a FileBackedList? –  Motti Strom Nov 11 '13 at 17:23
1  
@MottiStrom: while I don't consider the original scenario a violation, I would consider the IndexOutOfBounds usage a violation -- you are changing the semantics of the exception. The purpose of an exception is to allow the caller to recover from a failure, you are telling it to try to recover from the wrong failure. How it attempts to recover from this incorrct error could cause additional errors or data loss. –  jmoreno Nov 11 '13 at 18:02

The LSP basically says the answer to "Will code that correctly uses this interface do the wrong thing if used with your implementation of it?" should be no. Throwing new and different exceptions may cause code that thought it was handling all exceptions to fail when a new and unexpected exceptions show up. If it is possible to map exceptions to ones already provided by the interface then that is a possible path to go down, but they have to map cleanly in the intent they are trying to communicate though. You don't want to map to a fatal error from a nonfatal error and vice versa.

share|improve this answer

If LSP is unquestionably being violated, I could instead introduced a Option Type class that the List nominally stores and returns, which encapsulates the return types and any errors in retrieval.

/**
 * Wraps a String for writing or reading from a database.
 */
interface DbString {
  public DbString(String str) { /* ... */ }
  /** @returns the String, or "" if hasError() returns true */
  public String() getString();
  /** @returns true if there was an error in retrieving the string */
  public boolean hasError();
}

/**
 * A list of DbStrings
 */
class DbBackedList implements List<DbString> {
  // .. as before

  public DbString get(int index) {
    return Db.getConnection.getTable().getRow(i).asString();  // may throw!
  }

  // add(DbString), add(int, DbString), etc. ...
}

Usage is similar to regular lists.

List<String> l = new DbBackedList();
l.add(new DbString("foo"));
assertFalse(a.get(0).hasError());
assertEquals("foo", a.get(0).getString());

At this point, though, it's arguably easier to create a new interface from scratch and not retrofit an existing one, however we lose some of the apparent familiarity with the List interface. If we want to provide other collections, such as Set or Map we will then have to create new interfaces for each of them.

share|improve this answer
    
note that getString can be declared to throw your DbException, because this method isn't bound by List contract. I'd do just that, in order to ensure behavior even in case if client code ignores or forgets to check hasError value. Wrt hasError, I'd maybe drop that method, unless there is a clear solid need to have a check like that –  gnat Nov 11 '13 at 16:32
    
Ok, but consider that the hasError() approach makes it clear that the exception has already occurred, and is not caused by the getString() call itself. If hasError() is true we could make getString() return the empty String ("") just to avoid NPEs. But but let's not get too much into Java-isms or alternative designs as this solution doesn't allow a slot-in replacement for List, which is one of the use cases or the direct List<String> implementation. –  Motti Strom Nov 11 '13 at 18:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.