I don’t see any way to “lock down the interface to a class” in your code, but I do think you need to consider two things:

1. Your clients would still need to re-compile their code, even though the client source code doesn’t have to change: invoking a method on an interface uses a different bytecode operation then invoking a method on an instance.
2. What would prevent your coworkers from creating a class in the trusted package and invoking the constructor there?

Creating an interface is the best solution to your problem, and your only arguments against them are:

• You won’t ever have multiple implementations (YAGNI)

  What I really want is the freedom to add that Interface and alternate implementations later if needed.

  Interfaces are not just for switching implementations at run-time. Giving yourself ability to change the implementation behind an API without having to change client code is a valid reason to define a capital-I interface.

• Your fellow developers find it difficult to navigate to implementations

  (…) it annoys developers who like to be able to click on code and go right to the implementation not the Interface

  It’s trivially easy to navigate to implementations of a given method call in Eclipse: hold Ctrl and hover over the method call; a dropdown will appear with the Open Implementation option.

  I haven’t used IntelliJ in a while, but you can do it similarly there.

Don’t give up on interfaces so easily. Solving your problem is one of their primary benefits.

The correct solution is to use a combination of interfaces and simple factories. This is the general direction you are going, and is the correct way to go. To make this simpler, let’s use the analogy of fruit. (The names are a lot shorter.)

We have a Fruit interface, which is in our trusted package:

package trusted;

public interface Fruit
{
    public void nomnom();
}

We have a single implementation of Fruit, Apple. We want the end user to be able to have Apples, but not be able to directly instantiate an Apple:

package trusted;

final class Apple implements Fruit
{
    @Override
    public void nomnom() {
        System.out.println(nom3() + ", apple!");
    }

    /* Not in Fruit */
    public String nom3() {
        return "Nom, nom, nom";
    }
}

Apple is also in the trusted package. First, we note that Apple doesn’t have a visibility modifier (public, private, etc.). This means that Apple has the default visibility, which just so happens to be akin to package-private. This means only classes in trusted can access anything about Apple. Outside of trusted, Apple cannot be instantiated (even if it provides a public constructor!), and cannot have any static methods called on it. No one can know anything about Apple. This creates a small problem in that we want clients to be able to get an Apple if they want a Fruit. They cannot directly create one, so we need to provide a FruitFactory with public visibility inside the trusted package:

package trusted;

public class FruitFactory
{
    /* This could also be an instance method */
    public static Fruit getFruit() {
        return new Apple();
    }
}

Now we have a way to get a Fruit (an Apple in this case) without exposing the implementation of Apple. We can see that in action:

package untrusted;

import trusted.*;

public class Main
{
    public static void main(String[] args) {
        Fruit f = FruitFactory.getFruit();
        f.nomnom();
    }
}

And everything works! We can get a Fruit without hassle. If we try to instantiate or access Apple directly in any way from outside trusted, we get a compiler error.

Now say we’ve come up with the newest and greatest in fruit technology, Orange. Since Apple is now old hat, we’re going to give everyone Orange from our factory instead. First, Orange:

package trusted;

final class Orange implements Fruit
{
    @Override
    public void nomnom() {
        System.out.println("Nom nom nom, orange!");
    }
}

And now, all the changes we have to make to get everyone on the Orange bandwagon:

package trusted;

public class FruitFactory
{
    public static Fruit getFruit() {
        return new Orange();
    }
}

Done. Notice that nothing outside of trusted had to change. We didn’t touch Main. We didn’t even touch Apple. We added Orange, and changed the factory class (the only non-open-closed change, but highly localized and isolated). It still all compiles just fine because we’ve had them program to the Fruit interface rather than the Apple implementation. All they need to know is to use the FruitFactory to get a Fruit, and don’t worry about the rest (the implementation details).

Notice that, because we are now programming to an interface, we don’t need to know what the implementation looks like. We should be able to build a client completely by looking only at the Fruit interface, and never at Apple or Orange.

I said that you should definitely use interfaces, and not try to “fake” an interface as a class then try to change it later. There are a number of reasons for this:

1. If you start with a class, you may end up writing it in such a way that the API is implementation-dependent. Writing an Interface (big-I), without having any implementation in front of you, frees you from thinking about how you are going to do something. Instead you focus on what you want to do.
2. Writing Interfaces allows you to publish the least amount of information necessary. Interfaces don’t carry any implementation, so when you publish it to the rest of your team, all they know is the published API. If you publish an implemented class, it may have a larger API than you intend (note nom3 in Apple, which we’d want to keep hidden), and once others start to depend on those extras, you can never change them, even if you only intended them to be implementation details. A published implementation may also have certain characteristics (performance, etc.) that may not be intrinsic to the API. Others may optimize for that implementation, only to run into trouble when you come out with something new.
3. By publishing the least amount necessary, you gain freedom. You’re always going to need freedom. With a private API, you have the freedom to just make a change, but since all your APIs are essentially published, you need to reserve as much freedom as you can get. Need to swap out an implementation at compile time (like our Apples and Oranges)? No problem. Need to switch out an implementation at runtime? No problem, just have our factory figure out what is needed and give that. Need to implement a feature that requires using another pattern, like decorator or adapter? No problem. Just implement the interface around whatever implementation you need. You don’t need to juggle a class-into-an-interface refactoring later, meaning you can be more open-closed as well.

You seem very concerned to make sure that others are technically incapable of using your components in unexpected ways. This accomplishes that, but remember that a determined person will always find a way to circumvent whatever you try to do, even to their own detriment. Document the easy path, show why it is the best. Most people will take the easiest path you provide, and you can sleep soundly.

First I take program to an interface to mean more of programming to a contract rather than
programming to a literal Java interface. Contracts can be implemented in classes or interfaces (or even functions).

I want to take advantage of this lack of distinction. I also want to
interpret the principle “program to an interface” to mean, “I
shouldn’t be able to tell if any client code (using code) is working
with a java Interface or a java Class”. So much so, that later someone
could swap out the class for a java interface with the same name and
no client code would need to be touched. That may seem overly strict
and not exactly what was meant by these design principles (which try
to be ignorant of java’s particular quirks) but I’d love to pull it
off.

We run into a similar issue at my workplace. When everything has an interface, I lose sight of what has multiple implementations and what doesn’t. I might not care about things that do have several implementations when writing code. But I might care when reading code or debugging code.

There are several potential problems with using classes first and refactoring to an interface.

One of the problems I can see is exposing too many public or package (default) access level methods. If the client can use public or package protected methods that aren’t part of the interface, you can’t guarantee that you can safely swap an interface in place for the class.

Theoretically a class is serving the purpose of an interface would if it only exposes methods to the outside that would be present in the interface. If you can be strict with your classes and only expose methods that would be in the interface, then I fail to see how you couldn’t swap them out.

Another problem would be a client using direct construction of the class.
However an interface doesn’t prevent me from doing this:

 Foo bar = new DefaultFoo();

In order to truly be able to swap instances in and out, you would need Dependency Injection of some flavor. Also, you may still need to modify client code if you create multiple implementations. Something has to know if you wanted a FancyFoo or a PlainFoo for this client.

A final concern would be if the class really implemented more than 1 interface. You’ll find it a lot harder to swap an interface for a class if you have a Frobnicator that implements both the Foo and Bar interfaces. Clients using Frobnicator might be calling Bar functionality when they only needed a Foo, and vice versa.