Joseph D. Darcy's Sun Weblog

Thursday October 02, 2008

OpenJDK 6: Logistics of Partial Merge with 6u10

A large fraction of my work for OpenJDK 6 build 12 was porting all of the cumulative fixes in selected areas of the 6u10 code base into OpenJDK 6. Internally, like the forest of Mercurial repositories of JDK 7, the code base of OpenJDK 6 is composed of a set of teamware workspaces for different areas: cobra, hotspot, jaxp, jaxws, jdk, and langtools. Previously, the non-HotSpot code lived in a single "j2se" workspace which was split as part of the JDK 7 transition to Mercurial. I worked on merging in the fixes from the corba, jaxp, jaxws, and langtools areas. Jon helped with langtools too.

A variety of techniques were used to first find the fixes in the 6 update train that were absent in the OpenJDK 6 code base and then apply them as appropriate. The three basic strategies were:

• Examining the bug database to find bugs fixed in some 6 update release but not in OpenJDK 6. Patches implementing those fixes could then be applied.

• Teamware bringover and merge. The teamware bringover command pulls down changes from the parent workspace; per-file SCCS histories track changes and are used to identify any merge conflicts that need to be resolved.

• Raw diffs of source files. Crude, but sometimes effective with the right preprocessing.

There were various complications using these techniques. Not all areas follow the same bug database practices so using the bug database alone was not sufficient. Standard practice for maintaining JDK code is to have each SCCS delta tagged with a set of bug numbers (or tagged as a merge or a copyright update) and to not add empty deltas when the code has not changed. However, some areas of the JDK, jaxws in particular, are effectively maintained externally and only occasionally synced. In those cases, this SCCS discipline is not necessary followed, rendering a teamware merge operation ineffective since many files will have spurious conflicts. However, even in areas where standard practices are followed, a simple teamware bringover and merge may not suffice. For example, a file may have been removed from OpenJDK 6 but not removed from the 6 update train; a simple bringover would recreate the file. Raw diffs of source files can also be informative, but some preprocessing is needed to bring both code bases to a common format.

Compared to the 6 update train, as part of open sourcing and in preparation for transition to Mercurial, the OpenJDK 6 code base has undergone a number of pervasive transformations. On a file level:

• (generally) a GPL license is used instead of the Sun TLDA

• SCCS keywords have been purged

• whitespace has been normalized, tabs replaced by spaces and source files end with a newline

Therefore, to compute a meaningful raw diff, each of these transformations needs to be applied to the 6 update source or undone from the OpenJDK 6 source; although diff -w can bridge inconsistent whitespace conventions of course. However, even after being brought to a common format, since OpenJDK 6 is a backward branch from JDK 7, certain refactorings are present in the OpenJDK 6 train but absent from the 6 update train, obscuring both teamware-based and diff-based file comparisons. On a workspace level, the 6 update releases still use a monolithic j2se workspace in contrast to the split component workspaces in OpenJDK 6. Consequently, the contents of some subdirectories are now spread to multiple areas, further complicating bringover logistics.

The initial approach to evaluate merging in changes to each OpenJDK 6 component workspace was to:

1. Generate a list of source and test directories of the component workspace. (The make directories were excluded from consideration in the merge attempt since the workspace split fundamentally changed the makefile structure.)

2. Do a trial bringover -n of those directories from a 6u10 workspace. A workspace has a "biological parent" which gives birth to it; however, a bringover can use a different parent for comparison purposes instead. In this case, for the merge operation I used the 6u10 j2se workspace to be a temporary adoptive parent of my OpenJDK 6 component workspace. However, the eventual results of the merge would be committed to the biological parent OpenJDK 6 workspace.

3. Refine the directory list to avoid including spurious files.

4. Evaluate the utility of the bringover results in terms of merging files and generating conflicts.

While this procedure provided useful information, a simple bringover from 6u10 into OpenJDK 6 was never sufficient to properly capture the set of fixes without introducing other sorts of regressions, such as open source related file and license cleanup. On a per component workspace basis, those complications were:

• corba: Generally the bringover from corba went very smoothly; there were only 12 conflicting files and 8 new files that would be created. However, none of the 8 new files ended up being added to the OpenJDK 6 corba workspace; four the new files now live in the jdk workspace after the workspace split and the other four were unneeded binary files previously removed from the workspace in preparation for open sourcing. Resolving the actual file conflicts was straightforward and the fixes for eight bugs were brought over. After the merge, the OpenJDK 6 corba workspace had only a slightly different structure than in 6u10 since the OpenJDK 6 corba was changed to no longer require a scheme interpreter during the build!

• jaxp: In several dozen directories, there were about 30 conflicting files and two new files that would be created. Many of the differences were small, such as purging of SCCS keywords in OpenJDK 6. Where an SCCS keyword was purged, the purge was kept in the merged result; likewise licensing refinements and cleanups in OpenJDK 6 were also preserved in the merge. However, all changes that affected the semantics of the running code were brought in from 6u10. In summary, for the 30 or so conflicting files, generally the code matches the code in 6u10 and the license matches the license in OpenJDK 6. In previous syncs with the JDK, jaxp didn't always follow bug database discipline so a marker merge bug was created to supplement the known fix that was brought over. One of the files that would have been created was previously removed in JDK 7 so it was not resurrected and the other potential new file was not necessary and thus not created either.

• jaxws: The jaxws code is externally maintained and occasionally synced; however, standard teamware delta practices are not followed, resulting in thousands of spurious merge conflicts being reported on a bringover. Therefore, by using a script that stripped off the leading comment in a file (removing license differences) and normalized whitespace, transformed versions of the OpenJDK 6 and 6u10 jaxws sources in a common format could be compared. The only nontrivial differences were for the upgrade to JAF 1.1.1. Other than difficulties getting the tests for these changes to work in jprt, incorporating the fixes was straightforward. In addition, the jaxws team verified no other fixes went into 6u10 that were not already present in OpenJDK 6 (the same security fixes had been applied independently to both releases).

• langtools: The javac in OpenJDK 6 inherited a number of restructuring changes from JDK 7 that permeated the code, limiting the effectiveness of both teamware-based and source-file based comparisons to find true differences. Instead, queries on the bug database were used to identify bugs fixed in some 6 update release, but not in OpenJDK 6. Finding the effective set of bugs fixed in OpenJDK 6 compared to the originally shipped JDK 6 was computed as:

  • The bugs fixed in JDK 7 before the backward branch to create OpenJDK 6.

  • PLUS bugs directly fixed in OpenJDK 6 since the inception of its workspaces.

  • MINUS any "antibugs" that were annihilated in OpenJDK 6. An antibug is a change from JDK 7 that is inappropriate for a Java SE 6 implementation, such as OpenJDK 6, that is fixed by undoing the change. For example, a change in JDK 7 that added a class or method in the java.* or javax.* namespaces is inappropriate for a Java SE 6 implementation and must be removed for Java SE 6 conformance.

  The set of bugs cumulatively fixed in 6u10 is just a union of the bugs fixed in each update release up to and including 6u10: 6u1, 6u2, 6u3, 6u4, 6u5, 6u6, 6u7, and 6u10. In the end, the patches for about five groups of langtools bugs needed to the applied.

When reviewing the changes to corba, jaxp, and jaxws, two sets of webrevs were generated, one comparing the merge result against 6u10 and another comparing the merge result against OpenJDK 6. Each was important to fully verify the correctness of the change both in terms of licensing and semantics.

Friday September 12, 2008

OpenJDK 6: Some regression test results for b12

Running with jtreg flags -a -ignore:quiet, the basic regression test results on Linux for OpenJDK 6 build 12 are:

• HotSpot, 5 tests pass.

• Langtools, 1,346 tests pass, 2 tests fail.

• JDK, 2,985 tests pass, 36 tests fail, 4 tests have errors.

For langtools, from the previous build a few new (passing) tests were added and @ignore tests were really ignored; using jtdiff, part of the jtreg package to compute the differences of the tests results:

0: ./b11-langtools/summary.txt  pass: 1,341; fail: 2; error: 6
1: ./b12-langtools/summary.txt  pass: 1,346; fail: 2

0      1      Test
---    pass   tools/javac/6176978/T6176978.java
---    pass   tools/javac/6627362/T6627362.java
error  ---    tools/javac/T6405099.java
error  ---    tools/javac/api/T6306137.java
error  ---    tools/javac/api/T6397104.java
error  ---    tools/javac/api/TestJavacTaskScanner.java
error  ---    tools/javac/code/ArrayClone.java
---    pass   tools/javac/enum/T6509042.java
error  ---    tools/javac/generics/inference/6365166/NewTest.java
---    pass   tools/javac/staticImport/6665223/T6665223.java
---    pass   tools/javac/synthesize/Main.java

11 differences

Also for the jdk area, some new passing tests were added and the -ignore:quiet option prevents some tests that knowingly produce an error result from running. The few new failures warrant a bit of investigation.

0: b11-jdk/summary.txt  pass: 2,989; fail: 32; error: 22
1: b12-jdk/summary.txt  pass: 2,985; fail: 36; error: 4

0      1      Test
error  ---    com/sun/crypto/provider/Cipher/DES/PerformanceTest.java
pass   ---    com/sun/org/apache/xml/internal/security/exceptions/LocaleTest.java
pass   ---    com/sun/org/apache/xml/internal/security/transforms/ClassLoaderTest.java
error  ---    com/sun/security/auth/callback/DialogCallbackHandler/Default.java
error  ---    com/sun/security/auth/callback/TextCallbackHandler/Default.java
error  ---    com/sun/security/sasl/gsskerb/AuthOnly.java
error  ---    com/sun/security/sasl/gsskerb/ConfSecurityLayer.java
error  ---    com/sun/security/sasl/gsskerb/NoSecurityLayer.java
pass   fail   java/awt/Focus/DeiconifiedFrameLoosesFocus/DeiconifiedFrameLoosesFocus.html
fail   pass   java/awt/Focus/FrameMinimizeTest/FrameMinimizeTest.java
pass   fail   java/awt/TextArea/UsingWithMouse/SelectionAutoscrollTest.html
---    pass   java/awt/Window/PropertyChangeListenerLockSerialization/PropertyChangeListenerLockSerialization.java
error  ---    java/io/SystemInAvailable.java
error  ---    java/lang/instrument/TransformerManagementThreadRemoveTests.java
error  ---    java/lang/management/ThreadMXBean/SynchronizationStatistics.java
fail   pass   java/nio/channels/SocketChannel/Connect.java
pass   ---    java/rmi/activation/Activatable/checkActivateRef/CheckActivateRef.java
error  ---    java/util/AbstractList/CheckForComodification.java
---    pass   java/util/EnumSet/BogusEnumSet.java
error  ---    java/util/zip/3GBZipFiles.sh
fail   ---    javax/management/Introspector/LegacyIntrospectorTest.java
error  ---    javax/management/remote/mandatory/URLTest.java
error  ---    javax/security/auth/kerberos/KerberosHashEqualsTest.java
---    pass   javax/sound/midi/Gervill/DLSSoundbankReader/TestGetSoundbankFile.java
---    pass   javax/sound/midi/Gervill/DLSSoundbankReader/TestGetSoundbankInputStream.java
---    pass   javax/sound/midi/Gervill/DLSSoundbankReader/TestGetSoundbankInputStream2.java
---    pass   javax/sound/midi/Gervill/DLSSoundbankReader/TestGetSoundbankUrl.java
---    pass   javax/sound/midi/Gervill/SF2SoundbankReader/TestGetSoundbankFile.java
---    pass   javax/sound/midi/Gervill/SF2SoundbankReader/TestGetSoundbankInputStream.java
---    pass   javax/sound/midi/Gervill/SF2SoundbankReader/TestGetSoundbankInputStream2.java
---    pass   javax/sound/midi/Gervill/SF2SoundbankReader/TestGetSoundbankUrl.java
fail   pass   javax/swing/JColorChooser/Test6541987.java
pass   ---    javax/xml/crypto/dsig/GenerationTests.java
pass   ---    javax/xml/crypto/dsig/ValidationTests.java
pass   ---    javax/xml/crypto/dsig/keyinfo/KeyInfo/Marshal.java
pass   ---    sun/net/idn/PunycodeTest.java
pass   ---    sun/net/idn/TestStringPrep.java
pass   ---    sun/security/pkcs11/ec/TestCurves.java
error  ---    sun/security/provider/PolicyFile/GrantAllPermToExtWhenNoPolicy.java
error  ---    sun/security/provider/PolicyParser/ExtDirs.java
error  ---    sun/security/provider/PolicyParser/ExtDirsChange.java
error  ---    sun/security/provider/PolicyParser/ExtDirsDefaultPolicy.java
error  ---    sun/security/provider/PolicyParser/PrincipalExpansionError.java
pass   fail   sun/tools/jps/jps-Defaults.sh
pass   fail   sun/tools/jps/jps-l_1.sh
pass   fail   sun/tools/jstatd/jstatdDefaults.sh
pass   fail   sun/tools/jstatd/jstatdExternalRegistry.sh
pass   fail   sun/tools/jstatd/jstatdPort.sh
pass   fail   sun/tools/jstatd/jstatdServerName.sh

49 differences

I did a quick trial run of the regression tests on windows too, but my new cygwin installs seems to be missing a few pieces and many of the shell tests fail. I assume most of those failures are spurious, so I'll wait until the cygwin install seems configured properly before rerunning and posting windows results.

OpenJDK 6: Sources for b12 published

On September 12, the OpenJDK 6 b12 source bundle was published. Changes of note in this build:

• An updated version of Gervill is included (6717691, 6740210).

• Functionality of several IcedTea patches which correct JCK failures have been applied (6735154, 6733501).

• I've ported fixes from the forthcoming 6u10 release in a subset of the component workspaces to OpenJDK 6:

  • corba (6372405, 5104239, 6191561, 6486322, 6465377, 6553303, 6372405, 6438259)

  • jaxp (6573268, 6738894)

  • jaxws (6538484, 6699090)

  • langtools (6627362, 6627364, 6627366, 6176978)

• Incorporation of various build fixes, including the gcc ciTypeFlow.cpp issue (6732815, 6734545, 6590549, 6720240, 6548261, 6681798, 6741642).

• A few more legal notices were corrected (6635663, 6719182).

• Configuration information for some networking tests can now be provided as a properties files specified on the jtreg command line; see the source for jdk/test/TestEnv.java for details (6720349).

• Assorted other fixes (6681889, 6739302, 6730743).

While the changes in this build have corrected a number of JCK 6b test failures, a handful of tests still fail; eliminating those few remaining failures is a goal for the next build or two. (JCK 6b was released several months ago and has now replaced JCK 6a as the relevant test suite to pass for Java SE 6 compatibility.)

Internally, the code for OpenJDK 6 is split into teamware workspaces with a similar structure to the JDK 7 Mercurial repositories (corba, jaxp, jaxws, langtools, jdk, etc.). For a subset of these component workspaces, I've brought over the fixes in corresponding areas from 6u10. OpenJDK 6 build 12 will be one of the last teamware-based OpenJDK 6 build before we transition to a public Mercurial repository. Around the time of the Mercurial transition we will also upgrade the HotSpot in OpenJDK 6 from HotSpot 10 to HotSpot 11; HotSpot 11 is also being used in 6u10. From that point on, the same HotSpot sources will be used for both OpenJDK 6 and the 6 update releases.

I expect build 13 within a few weeks with the Mercurial repositories to follow a few weeks after that.

Wednesday August 20, 2008

OpenJDK 6: Some more regression test results for b11

To address a configuration issue with the previously reported regression tests results for OpenJDK 6 b11, I reran the jdk tests with the display set to a virtual framebuffer and 77 more tests pass. In summary now:

• JDK, 2,989 tests pass, 32 tests fail, 22 tests have errors.

Note that the jtdiff command, included as part of jtreg, can be used to compare the output of different regression test runs.

Thursday July 17, 2008

OpenJDK 6: Some regression test results for b11

For comparison purposes, I've uploaded the results of the automated regression tests (-a option to jtreg) from the OpenJDK 6 build 11 source bundle run against a Sun-internal Linux build:

• HotSpot, 5 tests pass.

• Langtools, 1,349 tests pass, 2 tests fail, 6 tests have errors.

• JDK, 2,912 tests pass, 109 tests fail, 22 tests have errors.

I ran the tests remotely and didn't set a usable display so about 72 of the JDK failures are from the AWT tests not having a display; I'll rerun the affected tests and verify they will pass as expected. At least one of the langtools failures seems to be from an overly zealous version check that should be modified.

I've also ran tests on a Solaris SPARC system; the HotSpot and langtools results were identical and there were a few differences in the JDK results.

Tuesday July 15, 2008

OpenJDK 6: Sources for b11 published

On July 15, the OpenJDK 6 b11 source bundle was published.

This source bundle includes:

• All the relevant JDK security fixes that recently went out. More information about these changes is available from the Sun Alerts linked to from one of Sun's security pages. Some of the security fixes only affect closed code or areas otherwise not open sourced as part of OpenJDK 6 so not all the security fixes are reflected in the source bundle.

• Ports of existing fixes in various areas. In HotSpot, fixes from previous 6 update releases (6497639, 6623167, 6623167, 6497639, 6599425), a build issue (6681796), and a fix for an Eclipse crash (6614100). In the libraries, there were fixes for graphics (6691328, 6608764, 6624717) and monitoring (6685178).

• Changes to address various of the previously raised concerns on licensing/copyright and binary artifacts. First, I applied Andrew John Hughes's fix to remove jscheme.jar (6695776). Next, Kelly and Iris have fixed many other licensing and binary artifact issues (6565364, 6705945, 6601384, 6601377, 6713083, 6695777 6710791).

• Miscellaneous other fixes cleaning up regression tests (6621691, 6596323, 6710579) and other matters (6717575, 6665028, 6589868).

I'm in the process of updating the Gervill sound engine in OpenJDK 6 to the current version; that work will be complete by build 12. In the meantime, as an initial step the spacing of the source code has been normalized (6717694).

I'd expect b12 to be available within two weeks; besides the Gervill work, a few more licensing/artifact fixes may be included too. Going forward, I plan to get the OpenJDK 6 sources into a public Mercurial repository by the end of the summer; that will allow fixes put there to be shared more quickly and should also allow more work to go on directly in the upstream code base.

Thursday June 19, 2008

OpenJDK 6: Congratulations to IcedTea and Red Hat

Congratulations to the IcedTea project and Red Hat for producing an OpenJDK binary in Fedora 9 that passes the Java SE TCK!

We'll continue working on getting the remaining fixes needed to achieve this incorporated directly into OpenJDK 6 too.

Friday June 13, 2008

Cheesy X-rays

When flying recently, I was slightly concerned after when my carry on bag was selected for extra scrutiny after going through the X-ray machine; the culprit: cheese. I was bringing back four bars of 1 ¾" × 1 ¾" × 6" cheese I haven't been able to find in California. My bag also had some batteries and electronics in it. The cheese packaging was swabbed and analyzed and I went on my way. I thought this was a little silly, but I moderated my view when I was catching up on back issues of Science News during the flight and read an article that said cheese and plastic explosives can look the same under X rays. The new and improved X-ray system being discussed will be able to tell apart C4 and four cheese!

OpenJDK 6: Sources for b10 published

On May 30, the OpenJDK 6 b10 source bundle was published. Notable fixes in this build include:

• Clarifications and corrections to the build instructions (6644659, 6682167, 6563616, 6611685, 6597857)

• Fixes related to building cryptography (6683078, 6644659)

• 2D bug fixes (6604044, 6636469), including a fix from Andrew Haley and Keith Seitz of Red Hat to correct color management related regression and JCK failures (6523403).

• Replacing the encumbered sound engine with Gervill (6702956)

• Updating time zone data to 2008c (6707643)

• Collections fixes (6691185, 6691215)

• Start of addressing the copyright/licensing concerns raised by Debian (6695553, 6703931)

• Deleting or modifying regression tests to be more appropriate for OpenJDK (6673853, 6602426, 6704655, 6705893)

With the removal of the binary plug for sound, the only remaining plug in OpenJDK 6 is for SNMP support. Work continues to address the remaining copyright and licensing concerns in the code base. Some regression tests, such as those in networking and javax.script, should probably be modified to more easily accept configuration options without having to modify the source of the tests; discussion on how best to do that has started.

Tuesday May 27, 2008

Indiana Jones: Ants aren't like scorpions!

There have been many years and many miles since Indiana Jones and the Last Crusade, and after seeing Indiana Jones and the Kingdom of the Crystal Skull this weekend, I think the franchise is a little worse for wear. In the opening action sequence, I was was surprised to learn Soviet gunpowder in the 1950's apparently included iron filings in addition to sulfur, charcoal and potassium nitrate since the powder was magnetic! Somewhere in editing, I'm convinced the line "Ants aren't like scorpions!" must have been deleted, a line I hope will be added back for the DVD edition.

Friday May 16, 2008

A Twisty Maze of Little Molieres

Described as the French "Shakespeare in Love," I watched the film "Molière" about the famous but new-to-me 17^th century French playwright and one verbal exchange stuck with me. The exchange is described in the wikipedia article about Molière:

In Le Bourgeois Gentilhomme, the title character, M. Jourdain, composes a love note as follows: "Beautiful marchioness, your beautiful eyes make me die from love" ("Belle marquise, vos beaux yeux me font mourir d'amour"). He then asks his philosophy teacher to rephrase the sentence which he does by shuffling the words in nearly every single way ("Beautiful marchioness, from love," etc.). M. Jourdain then asks which phrasing is best and the teacher promptly replies that the first is best. The phrase "Belle marquise..." is now used to indicate that two different sentences mean the same thing.

I was immediately reminded of the Adventure game's many variants of "A twisty maze of little passages, all different." Exploring the space of combinatorial permutations has had recognized literary value for longer than I thought!

Wednesday May 14, 2008

JavaOne: Writing the next great Java book

Catching up post-JavaOne, I was glad to have gone a bit outside my usual core Java SE track sessions on Thursday evening by attending "Writing the Next Great Java™ Technology Book." Moderated by book editor Greg Doench, the panel of distinguished authors, Brian Goetz, Josh Bloch, Kathy Sierra, and Bert Bates, gave advice ranging from why to start writing a book to how to complete one. Below are my recollections of the bof.

Brian advised to treat writing a book like running a software release, including version control over the text and code samples, as well as automated building and testing of any code. Brian's quote from Churchill,

Writing a book is an adventure. To begin with, it is a toy and an amusement; then it becomes a mistress, and then it becomes a master, and then a tyrant. The last phase is that just as you are about to be reconciled to your servitude, you kill the monster, and fling him out to the public.

—Winston Churchill

certainly rang true for me in scaled down ways for some of the writing and other projects I've done. (I have many partially written blog entries, some over a year old; the toy stage doesn't last very long!) Brian also gave a warning on the scope writing a book: it will take twice as long as you think it will; there is a substantial amount of editing and revising even when the book is seemingly near completion.

Josh spoke of the importance of passion for the subject matter and knowing what you want to say. Additionally, he thought it was essential to have a diverse slate of reviewers who were representative of the book's audience; for example, one of the early readers of "Effective Java" was the teenaged son of the Java series editor. Good reviewers need a willingness to let the author know when the book is incorrect or needs improvement. To Josh, Strunk and White remains a model of clarity. He also explained how threats from family members can be a helpful motivation to finish a book!

I've read books by Brian and Josh, but I haven't read Kathy and Bert's "Head First Java," which takes a less traditional, more graphical, approach to technical writing. Bert listed a number of books, including What the Best College Teachers Do and Efficiency in Learning, as having important insights to help manage the cognitive load of readers. Kathy only used one slide, but had the audience do several interactive exercises, including staring down our nearest neighbor. (With our forward facing eyes, people are predators; facing down a full room of predators tickles the innate "fight or flight" response :-) She described most technical books as providing an "I suck." experience for the reader, an experience they didn't want to encourage in "Head First." Part of reducing the likelihood of suckage comes from skillfully leaving things out. However, books should strive for a high-resolution experience; in a California-sensitive analogy, many don't regard wine as merely a binary red/white beverage. For Kathy, a goal of a technical books is for the reader's reaction to not be about the author or the book itself, but rather the difference made to the reader.

Besides books, I think the panel's advice is useful for other forms of writing too, having strong reviewers and keeping a concern for your reader are broadly applicable, and I'll keep their suggestions in mind for my future blogging.

Monday May 12, 2008

API Design: Interfaces versus Abstract Classes

Jake Gittes: Why are you doing it?
How much better can you eat?
What can you buy that you can't already afford?
Noah Cross: The future, Mr. Gitts, the future.
—Chinatown

Quoting, Effective Java, first edition, Item 16: Prefer Interfaces to abstract classes

To summarize, an interface is generally the best way to define a type that permits multiple implementations. An exception to this rule is the case where ease of evolution is deemed more important than flexibility and power.

As discussed in that item, the ease of evolution of abstract classes comes from the ability to add new methods having "reasonable default implementations" without almost surely causing source of all existing subtypes to no longer compile. The flexibility and power of interfaces involve ease of retrofitting to existing classes, allowing nonhierarchical type relations, and so on. An additional benefit of interfaces is the ability to use dynamic proxies; one notable use of dynamic proxies is creating the annotation objects returned at runtime by getAnnotation. One potential difference not worth considering with modern virtual machines is the speed difference between invoking a method on an interface versus invoking a method on a class.

While there is a sound rationale backing the conventional wisdom, in my estimation the compatible evolution advantages of abstract classes are smaller than they appear at first, further tipping the balance in favor of using interfaces in more situations.

The two alternatives to be considered to define the initial desired type abstraction are:

• Declare an interface.

• Declare an abstract class, all of whose initial methods are public and abstract.

In neither case are fields being defined. In both cases a skeletal abstract implementation class, like java.util.AbstractList, could be used to share implementation code. If the type abstraction is defined by an abstract class, the skeletal class and abstract class might be able to be combined, saving a type compared to the pair of an interface plus a skeletal class. However, forcing all implementations to be based on the same skeletal class may be awkward. Interfaces can easily have multiple independent skeletal helper classes. Subclasses can blunt inheritance issues by using an intermediate subclass to abstract-ify any problematic implementations from the parent.

Table 1 outlines the different kinds of compatibility impacts, source, binary, and behavioral, from adding a method to an interface and an abstract class. The effects of adding a method to an abstract class depend on whether or not the added method is abstract or has an implementation. For the purposes of discussion, we will assume the method does have an implementation (otherwise, there would be no advantage to using an abstract class).

Technically, adding a method to an interface and adding a method to an abstract class are both binary compatible since programs using those types will continue to link. However, in the case of an interface type, if a program calls the new method on an existing implementation of the interface (unless the implementation presciently had a method with a matching signature declared), an AbstractMethodError will be thrown, which is an awkward situation to recover from. Also, for the call to the new interface method to work on an existing implementor of the old interface, the method in the implementor must be an exact match, signature and return type, for the added method; if the return type in the implementor is a subtype of the added method, a covariant return, a recompile of the implementor is needed to create the bridge method joining the method from the interface with the method declared in the class.

Adding a method to an interface has a wide range of possible source compatibility effects on existing code. It is possible that an implementation anticipated future developments and already has a method matching the newly added method. In that case, adding the method is binary-preserving source compatible with that particular class. Of course in general it is much more likely that existing implementations do not already have the new method, in which case they won't compile against the modified interface declaration. Therefore, the worst possible outcome is that existing implementations will stop compiling after the method is added to the interface; this worst case outcome is also the most likely outcome in the absence of other information.

Adding a concrete method to an abstract class also has a range of source compatibility outcomes. If no existing extending class has a method with the new name, there is no conflict and the addition is binary-preserving source compatible given the set of actual programs. If not the expected outcome, this is certainly the hoped for outcome of adding a method to an abstract class! However, it is possible existing subclass already declare a method with the new name. If the parameter types match but the return types conflict, existing subclasses will stop compiling after the method is added. If the parameter types are not the same, an overloading situation is introduced or expanded. This can change method resolution of call sites using the existing subclass, which may or may not lead to behaviorally equivalent class files since different methods might be called. One technique to avoid changing resolution at existing call sites is for the new method to include in its parameter list a new type added at the same time as the method. If the new type is not related to existing types, then no method in an existing subclass will interact with the new method during method resolution. Therefore, the worst possible outcome is that some existing subclasses will stop compiling after the method is added to the abstract class; this can be avoided depending on the parameter list of the new method, at the potential cost of introducing new overloadings that change existing method resolution.

Not counting introspective operations like core reflection, adding methods to an interface or abstract class does not have much direct appreciable behavioral compatibility impact because adding methods doesn't directly affect the code run by existing clients of the class. If an abstract class were not at the conceptual root of a type hierarchy, adding a concrete method could intercept calls to a method with the same signature in the superclass. However, if the children of an abstract superclass already have a concrete implementation for the newly added method, existing calls to the children's method would not be intercepted by the method added in the superclass.

Since adding a method to an interface or an abstract class is binary compatibly and in both cases the worst case source compatibility outcome is breaking compilation of existing subtypes, any evolution advantage of abstract classes hinges on the ability to have a reasonable default implementation for new methods. But what can such a new method implementation really do? Some viable options are:

• Throw new UnsupportedOperationException or some other exception.

• Call existing methods on the abstract class.

• A no-op method.

(Other sorts of behavior could potentially be added to skeletal classes, but those classes aren't an alternative to interfaces.) Adding a default implementation that throws an exception isn't necessarily very useful; throwing AbstractMethodError would mimic adding a method to an interface! If the functionality of the new method can be expressed in terms of existing methods on the abstract class, the new method could also be written as convenience static method in a helper class. In that case, the convenience method could just as easily be written in terms of methods on an interface instead. Proposals for extension methods would add syntactic support for this helper class pattern. A no-op method could be added to optionally advise subclasses to some condition or event, but it would have no useful effect on existing subclasses. While it is straightforward to add simple concrete methods to an abstract class, with sufficient advance planning, such methods could also be automatically added to implementations of an interface at compile time.

Starting in JDK 6, Java compilers must support standardized annotation processing. Annotation processing is a general meta-programming framework not directly tied to annotations. Before annotation processing, the types being compiled can be incomplete, including references to types to be generated during annotation processing. The to-be-generated types can include the superclass of a class being compiled. Supporting the generation of superclasses is a very powerful technique for modifying the semantics of the child class. In this case, a class implementing an interface expected to change in the future could refer to a private superclass. With the original definition of the interface, the superclass would be empty. However, when methods were added to the interface, the annotation processor could generate implementations of those methods in the superclass. This would have the effect of adding the new methods to the class at compile time. Annotations could drive what the synthesized implementation actually did, such as throw an exception or a no-op.

Compared to adding methods to an interface, adding concrete methods to an abstract class seems to be much more compatible. However, both operations are binary compatible, and while adding a method to an abstract class usually has a better "average" impact on existing subtypes, the worst possible impact is the same, breaking the compilation of existing code. As for the functionality that can be added in a concrete method, convenience methods can be put in separate class and the other sorts of limited functionality methods that can readily be added could also be generated via annotation processing for implementors of an interface. Therefore, the practical evolutionary benefits of using an abstract class rather than an interface should be considered carefully since interfaces may still be a better choice when limited evolution is anticipated.

Thursday May 08, 2008

JavaOne: Java + You = ...

In this year's JavaOne pavilion, you can get shirt's printed with your own answer to this year's conference theme posed as a question

JAVA + YOU = ?

While "JAVAYOU" would be a string-centric programmatic answer, with my floating-point czar hat on, my answer to this summation is "K9K4", which I computed with the following program:

public class JavaPlusYouSum {
    private static final String JAVA = "JAVA";
    private static final String YOU  = "YOU";
    private static final int RADIX = 36;

    public static void main(String... args) {
	int sum =
	    Integer.parseInt(JAVA, RADIX) +
	    Integer.parseInt(YOU, RADIX);
	
	System.out.printf(JAVA + " + " + YOU + " = " + 
			  Integer.toString(sum, RADIX));
    }
}

However, I'm confident less numerical answers will be more useful and satisfying in most contexts :-)

Thursday May 01, 2008

OpenJDK: jtreg and regression tests

Huzzah! Through the dedicated efforts of Jon and others, jtreg is now open sourced! The jtreg program is the test harness used to run the regression tests that come with the JDK sources.

The JCK tests verify properties that should be true of all implementations of a given Java SE specification. The JDK regression tests are different; while many of them test properties that should be true of all implementations, some regression tests look at properties we want to be true of our JDK implementation but are not strictly required by the specification. Therefore, while a failing regression test most likely indicates a problem, in some cases the failure may not be a correctness issue per se. This situation is certainly feasible with ports of the JDK to operating systems sufficiently different than windows, Solaris, and Linux; shell tests are especially susceptible to those OS differences. Creating new shell tests should be avoided if possible and the porting effort may include updating regression tests to make them aware of the new platform.

Friday April 25, 2008

Test where the failures are likely to be

There is a old joke about walking along one night and coming across someone looking down underneath a streetlight for lost keys. Stopping to help look, after a minute or two of searching you remark, "Your keys don't seem to be here. Where did you drop them?" "Well, I dropped them over in that ally, but it's way too dark to look there!"

While at Berkeley, one of the lessons I learned from Professor Kahan was "test where the failures are likely to be, ", which he stated much more mathematically as "seeking the singularly points of analytic functions." Especially for numerical applications, the tricky inputs to the code can differ markedly from algorithm to algorithm. For example, this was the underlying reason the Pentium fdiv bug was not caught sooner. A new SRT divider algorithm was being used and while billions and billions of existing tests were run and looking fine, new tests targeting the new algorithm were apparently not written. After learning of the general problem, Professor Kahan was able to write a short test program that probed at likely failure points, boundaries in a lookup table, and found incorrect quotients after executing for under a minute.

I keep Professor Kahan's advice in mind went writing regression tests for my JDK work, especially on numerics. At least on occasion, this methodology has flagged a bug unrelated to the code at hand. Tests I wrote for an initially internal "getExponent" method on floating-point numbers included checking adjacent floating-point values around each transition to the next exponent; the lucky by-catch of this was a HotSpot bug which was then corrected. From a code coverage perspective testing at every exponent value is not needed since the code executed is the same, but such thoroughness helps provide robustness against other kinds of failures and didn't take much more time or code in this case.

While the mathematics behind certain math library tests can be quite sophisticated, in some ways the structure of their input is relatively simple compared to, say, the set of legal strings to a Java compiler. In the worst case, for a single-argument floating-point method an exhaustive test "just" has to make sure each of the 2³² or 2⁶⁴ possible inputs has the proper value. The set of possible Java programs is much, much larger and categorizing the set of notable transition points can be challenging, but looking for likely failures is still applicable and worthwhile as one aspect of testing.

Monday April 21, 2008

Compatibly Evolving BigDecimal

Back in JDK 5, JSR 13 added true floating-point arithmetic to BigDecimal, which involved many new methods and constructors along with new supporting classes in the java.math package. I was actively involved in the JSR 13 expert group and integrated the code into the JDK. These changes had some surprising compatibility impacts which can be classified according to their source, binary, and behavioral effects.

The numerical values representable in BigDecimal are (unscaledValue × 10^-scale) where unscaledValue is a BigInteger and scale is a 32-bit integer. Before Java SE 5, scale was constrained to be positive or zero (in other words, 10 raised to a negative or zero exponent) and JSR 13 removed this restriction to allow any integer exponent. Consequently, prior to JSR 13 BigDecimal integral values with trailing zeros had to have them explicitly represented; for example the value one million had to be stored as (1,000,000 × 10⁰) rather than (1 × 10⁶) or (10 × 10⁵), etc. One behavioral consequence of JSR 13 was that all the methods operating on BigDecimal values understand and accept numbers without the old exponent restriction.

The new API elements added by JSR 13 are listed in table 1; the additions will be examined under each kind of compatibility.

Binary Compatibility

Adding new public methods and constructors, even ones that overload existing names is binary compatible. Adding public static final fields is binary compatible, meaning existing clients of the library will continue to link. However, there is a possible complication here since BigDecimal is not final and since it has public constructors, it can be subclassed. (As discussed in Effective Java, Item 13, Favor Immutability, this was a design oversight when the class was written.) Adding fields to classes can be binary incompatible, but the needed combination of circumstances does not arise in this case. Therefore, individually and as a whole, the BigDecimal API additions are binary compatible.

Source Compatibility

For source compatibility, we can distinguish between clients of a types and extenders/implementors of a type; certain changes can inconvenience extenders/implementors but not clients.

Adding the public static final fields is binary-preserving source compatible. If a subclass, say MyDecimal, already has a field with the same name as a field being added to BigDecimal, the existing declaration in MyDecimal hides the new declaration in the parent class BigDecimal. Therefore, existing uses of, say, MyDecimal.TEN, would continue to resolve to the same binary name.

Since constructors are not inherited and all the new constructors are public rather than protected, just the uses of constructors in clients needs to be considered; there are no distinct special issues for subclasses. The constructors in BigDecimal during Java SE 1.4.x, the platform version immediately predating JSR 13, are listed in table 2.

To assess the source compatibility impact, we can compare the new constructors with the old constructors and see if any possible overload resolutions would change, including the possibility of stopping an existing compilation by removing the existence of a most specific method. Of the twelve new constructors, ten are clearly not problematic and binary-preserving source compatible; the ten either have more parameters than the existing constructors or are not applicable to the same invocations, see table 3. For example, eight of the new constructors have the new type MathContext as a parameter. Because of primitive subtyping the other two new constructors, BigDecimal(int val) and BigDecimal(long val) are both applicable to and more specific than invocations that would previously resolve to BigDecimal(double val). Therefore, adding these two new constructors is not binary-preserving source compatible because a different constructor can be resolved for the same existing source code, code with one-argument calls to a BigDecimal constructor where the argument is a primitive type. These two constructors need a secondary screening to assess their behavioral equivalence.

Before JDK 5, the expressions BigDecimal(123) and BigDecimal(123L) in source code would resolve to a call to BigDecimal(double); as part of that resolution primitive widening conversion converts the argument expression to double before the constructor is invoked. All int values are exactly representable as double and the double constructor when given an integral value will return a BigDecimal with the numerical value in question and a scale of zero. The new int constructor will also return a BigDecimal with the numerical value of the argument and a scale of zero. Therefore, adding the int constructor will result in behavioral equivalent programs; although the new constructor will cause some invocations to resolve to a different constructor, calling the other constructor will still always result in an equivalent, bd1.equals(bd2)==true, BigDecimal. However, the new long constructor does not have behavioral equivalence for all values. Some long values are not exactly representable in double and the old long → double conversion can silently lose precision. For example, printing the value of (new BigDecimal(Long.MAX_VALUE)) gives
9223372036854775808
under JDK 1.4.2 but
9223372036854775807
under JDK 5. More dramatically, printing (new BigDecimal(0x4000000000000200L)) gives
4611686018427387904
under JDK 1.4.2 but
4611686018427388416
under JDK 5. While the new behavior is "better" in the sense of exactly capturing the long argument value, it is a subtle change to existing source code. Strictly speaking, among the spectrum of different source compatibility levels, adding this constructor only preserves the weakest property, maintaining the ability to compile. Since the resolution of constructors in existing code is changed, adding this constructor is not binary-preserving source compatible, nor is it behaviorally equivalent since a different BigDecimal will be returned for some inputs. Since the class already had a static factory method with a long parameter that would convert values exactly, the long constructor did not need to be added to exactly get a BigDecimal with a long's value in a single operation.

Partially because of the unintentional, if beneficial, change in source meaning as well as some of the usual reasons (possibility to cache, etc.), in retrospect I think it would have been preferable for the functionality of all twelve new constructors to be provided through static factories instead. (While not directly applicable in BigDecimal, in general even if constructors aren't considered harmful, static factories can have better generics support.

A similar analysis can be undertaken for all the new methods. Additionally, since subclasses are possible, inheritance conflicts need to be considered too. Note that the new methods taking MathContext and RoundingMode parameters cannot conflict with existing methods in subclasses so all those additions are binary-preserving source compatible. However, if all the parameters of a new method are existing types, a subclass could potentially have a conflicting method with an unrelated return type. For example, MyDecimal could have a (strange) public double divide(BigDecimal divisor) method which would conflict with the addition of public BigDecimal divide(BigDecimal divisor). While BigDecimal generally shouldn't be subclassed, the addition of some of these new methods could prevent existing subclasses from compiling, yet another reason to favor composition over inheritance.

Behavioral Compatibility

In terms of evolving the behavior of existing methods after introducing the expanded exponent range, the main issues were the behavior of arithmetic operations and text ↔ BigDecimal conversion operations; the latter would prove to be unexpectedly troublesome.

As summarized in table 4, the behavior of arithmetic operations was quite compatible with a number of strong invariants. Given input values a1 and b1 representable under the old system, and given an existing method, say add, and its result c1, in the old and new BigDecimal if the inputs to an operation are .equals, same numerical value and same representation, then the output is exactly equivalent too, same numerical value with the same representation. More generally, in the old and new BigDecimal if the inputs to an operation satisfy the weaker property of being compareTo() == 0, meaning they have same numerical value but with a possibly different representation, then the output will be numerically equal, but possibly with a different representation.

A main advantage of decimal arithmetic over binary arithmetic is what-you-see-is-what-you-get for input and output values, the complicated vagaries of binary ↔ decimal conversion can be avoided and exact computation can be straightforward. Therefore, when removing the restriction on exponent values, being able to have a textual representation that readily mapped to all possible unscaled value and exponent pairs was paramount to make the new arithmetic usable. Before JSR 13, the toString method did not use exponential notation, all leading and trailing zeros were explicit. For fractional values, the length of the output grew linearly with the size of the exponent, as well as the number of digits of precision. Conversely, without negative exponents, the internal representation and string output of integer-valued BigDecimal numbers grew with the magnitude of the number, even when it was inherently low-precision. To take advantage of the new unrestricted exponent range, a textual notation was needed that allowed the positive or negative exponent to be recovered; this was accomplished by changing to using scientific notation in the toString output. When converting from text to BigDecimal, a positive exponent could be reconstructed from integer values that previously would have been forced to have a zero exponent. However, the new output was legal input to the old constructors, so similar properties similar to the old and new arithmetic behavior applied:

• Within a given release, BigDecimal(bd.toString()).equals(bd) == true, meaning converting to and from a string preserves numerical value and representation.

• toString output from the old BigDecimal converted by the new BigDecimal yields a result equivalent to the old value.

• New toString output converted by the old BigDecimal yields:

  • An equivalent result when the exponent is negative.

  • A numerical equal result when the exponent is positive (representation may differ).

If needed, in the new BigDecimal on textual input the old semantics on exponents is easy to code:

BigDecimal bd = new BigDecimal(myString);
if (bd.scale() < 0)
  bd = bd.setScale(0);

and a toPlainString method was added to provide the old-style output when needed.

Staying within the realm of old and new BigDecimal versions, these arrangements solidly preserve a very reasonable kind of behavioral compatibility, numerical value and representation are kept constant when possible, otherwise, numerical value is preserved possibly with a different representation. Backwards serial compatibility is slightly weaker; rather than being converted to exponent-zero values as done for textual inputs, new serial streams holding positive exponents are rejected by old BigDecimal implementations. Unfortunately, despite these consistencies across JDK versions, some users of BigDecimal still ran into compatibility issues from the textual output changes made by JSR 13.

A common use for BigDecimal is interfacing to databases and while the new scientific notation was legal input to the old BigDecimal string constructors, scientific notation was not legal notation to databases. The addition of the toPlainString method did not help the situation without recompiling the source of the application in question; such recompilation could be unwanted since it would tie the application to JDK 5 with the new method. Other unpalatable workarounds include subclassing BigDecimal to enforce the old toString behavior or using reflection to see if the toPlainString method is available to call to avoid introducing a hard dependency on the new method.

While the changes in textual input and output of BigDecimal were reasonable in the context of direct Java compatibility, the expert group underestimated the behavioral compatibility impact of these change when dealing with databases. While the changes remain justifiable in terms of supporting the new values, if the compatibility cost were known, the expert group could have and should have worked with database vendors to mitigate the migration cost associated with this change.

Conclusion

Fully understanding the compatibility impact of changes is subtle and shortcomings are quick to lead to user anger. Merely maintaining binary compatibility is not sufficient for many purposes. Following good coding guidelines from the beginning can pay silent rewards when later evolving the class by reducing the space of possible concerns.

Acknowledgments

Alex provided helpful comments on a draft of this entry.

Further Reading

1. Joseph D. Darcy and Mike Cowlishaw, JavaOne 2004 BOF 1638, Big News for BigDecimal,

2. Be careful when you are using Oracle and Java 5

3. BigDecimal and JDBC since Java 5.0

4. Java 5 BigDecimal.toString() and Oracle 10g jdbc

Thursday April 17, 2008

Kinds of Compatibility: Source, Binary, and Behavioral

Every change is an incompatible change. A risk/benefit analysis is always required.
—Martin Buchholz
Veteran JDK Engineer

When evolving the JDK, compatibility concerns are taken very seriously. However, different standards are applied to evolving various aspects of the platform. From a certain point of view, it is true that any observable difference could potentially cause some unknown application to break. Indeed, just changing the reported version number is incompatible in this sense because, for example, a JNLP file can refuse to run an application on later versions of the platform. Therefore, since not making any changes at all is clearly not viable for evolving the platform, changes need to be evaluated against and managed according to a variety of compatibility contracts.

For Java programs, there are three main categories of compatibility:

1. Source: Source compatibility concerns translating Java source code into class files.

2. Binary: Binary compatibility is defined in The Java Language Specification as preserving the ability to link without error.

3. Behavioral: Behavioral compatibility includes the semantics of the code that is executed at runtime.

Note that non-source compatibility is sometimes colloquially referred to as "binary compatibility." Such usage is incorrect since the JLS spends an entire chapter precisely defining the term binary compatibility; often behavioral compatibility is the intended notion instead.

There are many other observable aspects of the JDK not related to Java programs, such as file layout, etc. Those will not be further discussed in this note.

The basic challenge of compatibility is the difficulty of finding and modifying all the software and systems impacted by a change. In a closed-world scenario where all the clients of an API are known and can in principle be simultaneously changed, introducing "incompatible" changes is just a matter of being able to coordinate the engineering necessary to evaporate the liquid in a small body of water, perhaps only a puddle or pot on a stove. In contrast, for APIs that are used as widely as the JDK, rigorously finding all the possible programs impacted by an incompatible change is as impractical as boiling the oceans, so evolving such APIs is quite constrained by comparison.

Generally, we will consider whether a program P is compatible is some fashion (or not) with respect to two versions of a library L₁ and L₂ that differ in some way. (We will not consider the compatibility impact of such changes to independent implementers of L.) Sometimes only a particular program is of interest; is the change from L₁ to L₂ compatible with this program? When evaluating how the platform should evolve, a broader consideration of the programs of concern is used. For example, does the change from L₁ to L₂ cause a problem for any program that currently exists? If so, what fraction of existing programs is affected? Finally, the broadest consideration is does the change affect any program that could exist? Often once a platform version is released, the latter two notions are similar because imperfect knowledge about the set of actual programs means it can be more tractable to consider the worst possible outcome for any potential program rather than estimate the impact over actual programs. Stated more formally, depending on the change being considered, judging the change based on the worst possible outcome for any program is more appropriate than judging based on some other kind of norm of the disruption over the space of known programs.

Generally each kind of compatibility has both positive and negative aspects; that is, the positive aspect keeping things that "work" working and the negative aspect of keeping things that "don't work" not working. For example, the TCK tests for Java compilers include both positive tests of programs that must be accepted and negative tests of programs that must be rejected. In many circumstances, preserving or expanding the positive behavior is more acceptable and important than maintaining the negative behavior and we will focus on positive compatibility in this entry.

In terms of relative severity, source compatibility problems are usually the mildest since there are often straightforward workarounds, such as adjusting import statements or switching to fully qualified names. Gradations of source compatibility are identified and discussed below. Behavioral compatibility problems can have a range of impacts while true binary compatibility issues are problematic since linking is prevented.

Source Compatibility

The basic job of any linker or loader is simple: It binds more abstract names to more concrete names, which permits programmers to write code using the more abstract names. (Linkers and Loaders)

A Java compiler's job also includes mapping more abstract names to more concrete ones, specifically mapping simple and qualified names appearing in source code into binary names in class files. Source compatibility concerns this mapping of source code into class files, not only whether or not such a mapping is possible, but also whether or not the resulting class files are suitable. Source compatibility is influenced by changing the set of types available during compilation, such as adding a new class, as well as changes within existing types themselves, such as adding an overloaded method. There is a large set of possible changes to classes and interfaces examined for their binary compatibility impact. All these changes could also be classified according to their source compatibility repercussions, but only a few of kinds of changes will be analyzed below.

The most rudimentary kind of positive source compatibility is whether code that compiles against L₁ will continue to compile against L₂; however, that is not the entirety of the space of concerns since the class file resulting from compilation might not be equivalent. Java source code often uses simple names for types; using information about imports, the compiler will interpret these simple names and transform them into binary names for use in the resulting class file(s). In a class file, the binary name of an entity (along with its signature in the case of methods and constructors) serves as the unique, universal identifier to allow the entity to be referenced. So different degrees of source compatibility can be identified:

• Does the code still compile (or not compile)?

• If the code still compiles, do all the names resolve to the same binary names in the class file?

• If the code still compiles and the names do not all resolve to the same binary names, does a behaviorally equivalent class file result?

Whether or not a program is valid can also be affected by language changes. Usually previously invalid program are made valid, as when generics were added, but sometimes existing programs are rendered invalid, as when keywords were added (strictfp, assert, and enum). The version number of the resulting class file is also an external compatibility issue of sorts since that affects which platform versions the code can be run on.

Full source compatibility with any existing program is usually not achievable because of * imports. For example, consider L₁ with packages foo and bar where foo includes the class Quux. Then L₂ adds class bar.Quux. This program

import foo.*;
import bar.*;

public class HelloQuux {
    public static void main(String... args) {
	Object o = Quux.class;
	System.out.println("Hello " + o.toString());
    }
}

will compile under L₁ but not under L₂ since the name "Quux" is now ambiguous as reported by javac:

HelloQuux.java:6: reference to Quux is ambiguous, both class bar.Quux in bar and
 class foo.Quux in foo match
        Object o = Quux.class;
                   ^
1 error

An adversarial program could almost always include * imports that conflict with a given library.¹ Therefore, judging source compatibility by requiring all possible programs to compile is an overly restrictive criterion. However, when naming their types, API designers should not reuse "String", "Object", and other names of core classes from packages like java.lang and java.util to avoid this kind of annoying name conflict.

Due to the * import wrinkle, a more reasonable definition of source compatibility considers programs transformed to only use fully qualified names. Let FQN(P, L) be program P where each name is replaced by its fully qualified form in the context of libraries L. Call such a library transformation from L₁ to L₂ binary-preserving source compatible with source program P if FQN(P, L₁) equals FQN(P, L₂). This is a strict form of source compatibility that will usually result in class files for P using the same binary names when compiled against both versions of the library. Class files with the same binary names will result when each type has a distinct fully qualified name. Multiple types can have the same fully qualified name but differing binary names; those cases do not arise when the standard naming conventions are being followed.²

Adding overloaded methods has the potential to change method resolution and thus change the signatures of the method call sites in the resulting class file. Whether or not such a change is problematic with respect to source compatibility depends on what semantics are required and how the different overloaded methods operate on the same inputs, which interacts with behavioral equivalence notions. Assume class C originally has a method void m(T t) and then an overload void m(S s) is added. Some cases of interest include:

• S and T are both reference types:

  • If there is no typing relationship between S and T, overload resolution will not be affected.

  • If there is a typing relationship between S and T, such as T is a subtype of S, call sites in existing source may now resolve to the new method. Well-written programs will follow the Liskov substitution principle and C will do "the same" operation on the argument no matter which overloaded method is called. Less than well-written programs may fail to follow this principle.

• S and T are both primitive types: By extension, if a numerical value can be represented in multiple primitive types, overloaded methods taking a type with that value should usually perform an equivalent operation. However, the silent loss of precision in primitive widening conversion can affect the actual value that gets passed to an overloaded method.

  Concretely, consider class C with methods m(int) and m(double). The call site "m(123L)" will undergo primitive widening conversion, converting the argument value to double before m(double) is called. Now if m(long) is added to C, the call site will resolve to the new method. Even assuming each m method does an equivalent operation when passed a numerically equal value, there can still be differences after the third method is added since some long values lose precision when converted to double, for example, Long.MAX_VALUE. Therefore, a client when compiled against the two version of C can have different runtime behavior even if each m method behaves reasonably. This kind of subtle change in overloading behavior occurred with the addition of a BigDecimal constructor taking as long as part of JSR 13

• One of S and T is a reference type, the other is primitive: Before generics were added to the language, two methods which differed in the primitive/reference status of the i^th parameter could not possibly be applicable to the same arguments. But, along with generics came boxing and unboxing conversions that can map, for example, a value of an int primitive type to a java.lang.Integer object with a reference type, and vice versa. These mapping have the potential to introduce ambiguities in method resolution such that adding a method could introduce an ambiguity that prevented previously valid code from compiling; however, the rules for method invocation expressions were updated to avoid such potential ambiguities from boxing/unboxing as well as var-args.

If a new method cannot change resolution, then it is a binary-preserving source transformation. If a new method can change resolution, if the different class file that results has acceptably similar behavior, the change may still be acceptable, while changing resolution in such a way that does not preserve semantics is likely problematic. Changing a library in such a way that current clients no longer compile is seldom appropriate.

Binary Compatibility

JLSv3 §13.2 What Binary Compatibility Is and Is Not
A change to a type is binary compatible with (equivalently, does not break binary compatibility with) preexisting binaries if preexisting binaries that previously linked without error will continue to link without error.

The JLS defines binary compatibility strictly according to linkage; it P links with L₁ and continues to link with L₂, the change made in L₂ is binary compatible. The runtime behavior after linking is not included in binary compatibility:

JLSv3 13.4.22 Method and Constructor Body
Changes to the body of a method or constructor do not break [binary] compatibility with pre-existing binaries.

As an extreme example, if the body of a method is changed to throw an error instead of compute a useful result, while the change is certainly a compatibility issue, it is not a binary compatibility issue since client classes would continue to link. Also, it is not a binary compatibility issue to add methods to an interface. Class files compiled against the old version of the interface will still link against the new interface despite the class not having an implementation of the new method. If the new method is called at runtime, an AbstractMethodError is thrown; if the new method is not called, the existing methods can be used without incident. (Adding a method to an interface is a source incompatibility that can break compilation though.)

A design requirement from the addition of generics via JSR 14 was migration compatibility. Migration compatibility requires that a library can be generified and existing (nongeneric) clients can continue to compile and link against the generic version. Meeting this constraint led to the use of erasure, a controversial aspect of the generics design. During JSR 14, it was not known how to add generics in a way that supported both reification and migration compatibility; future work might address this shortcoming.

Behavioral Compatibility

Intuitively, behavioral compatibility should mean that with the same inputs program P does "the same" or an "equivalent" operation under different versions of libraries or the platform. Defining equivalence can be a bit involved; for example, even just defining a proper equals method in a class can be nontrivial. In this case, to formalize this concept would require an operational semantics for the JVM for the aspects of the system a program was interested in. For example, there is a fundamental difference in visible changes between programs that introspect on the system and those that do not. Examples of introspection include calling core reflection, relying on stack trace output, using timing measurements to influence code execution, and so on. For programs that do not use, say, core reflection, changes to the structure of libraries, such as adding new public methods, is entirely transparent. In contrast, a (poorly behaved) program could use reflection to look up the set of public methods on a library class and throw an exception if any unexpected methods were present. A tricky program could even make decisions based on information like a timing side channel. For example, two threads could repeatedly run different operations and make some indication of progress, for example, incrementing an atomic counter, and the relative rates of progress could be compared. If the ratio is over a certain threshold, some unrelated action could be taken, or not. This allows a program to create a dependence on the optimization capabilities of a particular JVM, which is generally outside a reasonable behavioral compatibility contract.

The evolution of a library is constrained by the library's contract included in its specification; for final classes this contract doesn't usually include a prohibition of adding new public methods! While an end-user may not care why a program does not work with a newer version of a library, what contracts are being followed or broken should determine which party has the onus for fixing the problem. That said, there are times in evolving the JDK when differences are found between the specified behavior and the actual behavior (for example 4707389, 6365176). The two basic approaches to fixing these bugs are to change the implementation to match the specified behavior or to change the specification (in a platform release) to match the implementation's (perhaps long-standing) behavior; often the latter option is chosen since it has a lower de facto impact on behavioral compatibility.

Case Study

Consider two versions of a simple enum representing the crew of the USS Enterprise, one for the first season:

public enum StarTrekCast {
    JAMES_T_KIRK("Jim"),
    LEONARD_MCCOY("Bones"),
    JANICE_RAND("Yeoman Rand"),
    MONTGOMERY_SCOTT("Scotty"),
    SPOCK("Spock"),
    HIKARU_SULU("Sulu"),
    UHURA("Uhura"); // Any first name for Uhura is non-canon.

    private String nickname;
    StarTrekCast(String nickname) {
	this.nickname=nickname;
    }

    public String nickname() { return nickname;}
}

and another for the second season:

public enum StarTrekCast {
    JAMES_T_KIRK("Jim"),
    SPOCK("Spock"),
    MONTGOMERY_SCOTT("Scotty"),
    LEONARD_MCCOY("Bones"),
    /* JANICE_RAND("Yeoman Rand"), */ // Only in 8 episodes!
    HIKARU_SULU("Sulu"),
    PAVEL_CHEKOV("Chekov"), // Introduced in season 2.
    UHURA("Uhura"); // Any first name for Uhura is non-canon.

    private String nickname;
    StarTrekCast(String nickname) {
	this.nickname=nickname;
    }

    public String nickname() { return nickname;}
}

Compared to the first reason, the second season:

1. Deletes yeoman Janice Rand

2. Adds Pavel Chekov

3. Reorders Bones, Scotty, and Spock to better reflect the order of who commands the ship if the Captain and others are unavailable.

These changes have varying source, binary, and behavioral compatibility effects:

1. Dele