I've thought about this a bit, though not to the point of creating a design,
much less building prototypes.  It seems to me that this approach is worth
investigating:

1. The interface of each class C in the system needs to be captured and
stored persistently, where "interface" means method signatures, field
definitions, and constant values.  Superclass name too, to cover the changes
that can occur if what C inherits changes.

2. Dependencies also need to be captured and stored persistently.  This will
be information of the form:

   . Class D depends on (some feature of) the interface of class C

3. Whenever a class is compiled successfully:

A. Its new interface is constructed.
B. Changes to the previous interface are computed, and all classes dependent
upon something that changed arerked invalid (except for other classes
compiled by the same invocation of javac, of course -- they're up to date
and will be marked valid).
C. Its new dependencies are calculated.
D. Its stored interface and dependencies are updated.
E. It marked valid

4. Whenever a group of Java files is to be rebuilt, e.g. by Ant's <javac>
task, any classes marked invalid in step 3 are recompiled, in addition to
classes that are not up-to-date with their source files.

Notes:
"Class" is used a bit ambiguously above, sometimes to mean a .class file,
sometimes to mean all of the .class files built from a single source file.
Clearly if A$Inner depends upon B, it's A that's marked invalid when B
changes.

The obvious outstanding problems with the above are:

A. How granular should the dependency information be?  If it's simply "A
depends on B", there will be a lot of unnecessary recompilations.  If it's
"A depends separately on the following 20 method calls it makes to B", there
will be a vast amount of dependency information stored, updated, and
checked.  I have no intuition for where the sweet spot lies.

B. How to generate the dependency information.  I presume it can be
calculated from .class file analysis, but I haven't verified this in detail,
nor do I know how expensive that would be.  It would be awfully nice if
javac would generate it for us, but it doesn't.

C. How to represent the dependency "C calls a method on an instance of D
that's inherited from E".  I think all of this information is required: if
the method definition changes, it will change in E, but we also need to mark
C invalid if D is reparented.

Inheritance adds some wrinkles. If Sub overrides a method it inherits from
Super, that doesn't really change its interface.  Classes which previously
called Sub.meth() don't have to be recompiled.  On the other hand, if Sub
defines a field that hides a field defined in Super, classes that accessed
Super.field should be marked invalid.

Overloads add some more wrinkles.  If a new overload is added, methods that
called the existing overloads and might now call the new one need to be
recompiled.  For practical purposes, it should be fine to recompiled callers
to any of the previous overloads, even if they're wholly disjoint.

When a class is reparented, it probably makes more sense to mark all of its
dependents invalid, rather than to try to calculate exactly what changed.
Note that changing the interfaces an abstract class implements is a kind of
reparenting, since it can change the set of methods that the class defines.

I'm sure there are many more of these which further analysis would reveal.
One more note: this is an ideal open source project, since it could be
greatly useful to the development community and there is no money to be made
by solving it.

Is this what you want: every time a file A changes, all dependant files (B)
should be recompiled automatically? (Because, as each developper compiles his
stuff B, javac will automatically determine that the A class file is older than
the A java file and recompile it, you can't mean that.)

What would the end result of such an automatic build be in case it yields lots
of errors? (Because the dependant javas don't compile anymore; incompatible
changes needed to be introduced.)

Michael

Unfortunately, I've to accept, that my ultimate goal is unreachable,
which would have been to have a working incremental build, that would
work with just anything checked in, even if it's in some subtle way
invalid java-code (in which case it would detect and report failure).

This won't work.  There are situations, where in it's generality
nothing than a full compile can detect the error:  this is, because
any two java-files (A.java & B.java) could contain a second
(non-public) class of a common name (C).  Only compiling this A.java
and B.java in the same javac-run will detect this problem.

Also, as Mike pointed out, removing .java files is another thing,
which an incremental build cannot "correctly" deal with - it can't
remove orphaned .class-files.

I don't give up, yet.
Even if I won't find *all* possible errors incrementally, I can still
find most typical errors that way. Even interface-changes that do not
cause compile errors (which also includes changes of constants) could
still be made to be properly propagated to all dependent classes.

If javac were to add an attribute to the .class-file (containing "source"
and perhaps even the value) for each inlined foreign constant,
then third party tools (like e.g. ant) would have the necessary data
available to do dependency management.  It would still be not at all
trivial for the third party tool, but quite likely trivial on javac's
side.

Another approach could be to have javac write out .depend-files
as used in C/C++-world - quite unlikely to ever happen.

javac could also take a new option that tells it not to unconditionally
compile, but check compile-necessity for each given file. Advantage:
it actually only checks forward-dependencies.  Disadvantage: the
check could be almost as expensive as a compile (don't know, though).
This would mean, that javac would take over (and do better) some part
of ant.

One more point: a full rebuild will remove class files generated from source
files that have been deleted.  Very few build systems do this for
incremental builds, even though it's not particularly difficult.

how about a rule like this.

Your central compile server is notified on checkin.  It does a
checkout.  It looks for the string "public static final".  If it sees
it is redoes a clean compile, in not, incremental.

This is different from doing the compiles at the client machines since
it is triggered as soon as possible.  Client compiles would not be
triggered till much later, when someone does a checkout.  

The server can serve the most recent coherent source/object, just the
deltas. This is almost instantaneous so the extra time to clean
compile is almost irrelevant.  When you compile on a client machine,
you have to wait. Further the time to compile is longer on the client
since the client machines are not as powerful.