软件的脆弱：从二分法查找的BUG说开去

大概是在去年的七月份左右，我首先在 javalobby 上看到这篇。当时也无比震惊，因为JDK (1.5及之前的版本) 中 Arrays.binarySearch(int[] a, int key) 及 Collections.binarySearch(int[] a, int key) (其调用indexedBinarySearch) 存在一个在业界隐藏了几十年的BUG，而这两个方法的作者恰恰是两位高人实现：

* @author Josh Bloch
* @author Neal Gafter

我想在Java 领域呆的比较长的开发者应该会有所耳闻吧，Josh Bloch 被称之为 "Java 之母"（虽然他是一位男性），因为 java collection 框架，java.math, 泛型 及《Effective Java Programming Language Guide》都出自他之手；而 Neal Gafter 则是 我们每天都用的JAVA编译器 Javac 的实现者。


我们先看有问题的代码:

public static int binarySearch(int[] a, int key) {
int low = 0;
int high = a.length-1;

while (low <= high) {              
int mid = (low + high) >> 1;
int midVal = a[mid];

if (midVal < low =" mid"> key)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1);  // key not found.
}

有问题的代码是这一行：

int mid = (low + high) >> 1;　

大家知道，其等价于：

int mid =(low + high) / 2;

问题是在 low 和 high 都很大时，比如数组的元素达到 2^30 时，low + high 将超过整数的最大值 2^31 -1，此时将造成溢流，溢流后得到的 mid 为负值。

正确的实现应该为：

             int mid = low + ((high - low) / 2);

或者更加清楚地使用Java的无符号右移操作符:

            int mid = (low + high) >>> 1;

虽然这个问题目前得到解决，我们就能断定这十几行程序就准确无误吗？
但连以上两位作者目前也还表示怀疑。
从行内得知，第一个二分法算法是1946年出现的，而当时被认为“无误”的实现到1962年才出现（也就是说以上十几行代码是经过十几年才得到的）。因为当时的数据量不可能逼近 2 ^ 30的数量级，所以直到去年这个BUG被提交到 Java 的 Bug 库中。可想人类的思维是有缺陷的。

目前，对于搜索引擎，基因工程领域，这一数量级应该是少见多怪了，所以如果你工作的领域需要处理大量的数据时，请使用 JDK 6.0

顺便提一句，对于C的实现，可以采用如下实现：

mid = ((unsigned) (low + high)) >> 1;

看到这样的情况，作为程序员，我们应该时刻警惕、保持低调！

NetBeans 5.5.1 发布了

在我们大谈特谈 NetBeans 6.0 时，一个中间版本 5.5.1 出来了。
也许是因为6.0 引入了太多的新功能，致使开发周期比以往稍显长些。所以这个中间版本主要是为了跟进最新的产品线：

• 支持Java EE 5 Application Server 9.1 (GlassFish v2)
• 支持Windows Vista
• C/C++ Pack 有很大的提升（这可是我亲自感受到的耶)
  
• 还有我们可能不大关心的，但却是目前最完善的，支持J2ME Wireless Toolkit, version 2.5.1　平台

感兴趣的话，到这里下载！

不过，过不了多久，它将被 NetBeans 6.0 所取代的，也许就在秋天！

NetBeans6 功能介绍: 布置 declaration View 和 Javadoc View

此篇文章介绍一个在 NetBeans 6 中同时查看鼠标指针处的源代码和
Javadoc (不再Go to Source .../ Show JavaDoc)

1. 首先打开它们：Window | Other | Declaration View 和 Window | Other | Javadoc View, 它们都被搁浅在 Output 窗口的位置，但此时只能看到一个窗口的内容，因为无论切换到其中的任何一个，它们都占据整个下端窗口。如下：



2. 我们要将它们分开，点击其中任一窗口的上方（类似标题栏区域），按住不放，将其拖向左侧（或右侧也可），当出现一个红色的方框后释放，如下：



释放后的效果如下：




这些位置会被记录下来，只要你在设置之后正常退出了。在下次启动 NetBeans 后，你可以看到同样的布局。

这个截图中显示的是　Integer.toHexString　方法的 Javadoc 和 实现源码。


(期待下一篇)

SwingWorker for you

想必大家已经知道 SwingWorker 已经加入到了 javax.swing 包中了。它的前身经过好几个阶段改进的，如果你阅读网上的例子就会发现你阅读的例子跟你下载的包不兼容。
SwingWorker 在被正式加入到JDK6中之前叫做：org.jdesktop.swingworker.SwingWorker.java, 除了这个类之外，还包括 org.jdesktop.swingworker.AccumulativeRunnable.java 和 org.jdesktop.swingworker.SwingPropertyChangeSupport.java. 我并不打算深入介绍这几个类的源码，而是利用实际的例子来描述 SwingWorker 给 GUI 程序带来的便利。

如果写过GUI程序的开发者肯定对界面的响应度及界面冻结会有所了解。首先我得说明的是，这个问题并不是SWING特有的，所有的GUI框架如果没有处理 好都会存在这种问题，举例来说，
1. 在网络不好的环境下，在 windows 的文件浏览器中请求一个FTP地址或任何服务器的地址时，我们可以看到“灰块”（所谓灰块，是由于界面元素刷新队列被某个长时间的任务给阻塞，造成本该立 即刷新的界面得不到处理，显示出来的效果就是一块被扯得扭曲了的区域。）
2. 用过 PLSQL Developer 的开发者肯定也体会过屏幕冻结的感受吧。


费话少说，进入我们的 SwingWorker 之旅。

SwingWorker有几个重要的概念：

1. 初始线程(Initial threads) 一般来讲是应用的主线程 (运行main 方法的那个线程）　
2. 工作者线程(Worker Thread) 在主线程中生成的，用于执行那些长时间操作的线程
3. 事件调度线程(Event Dispath Thread) 所有界面相关的行为都应该在这个线程进行，并且一定要保持快速的响应。

如下图是利用 NetBeans Profile 监控到线程：

• main - 初始线程
• Our Swingworker #1 - 工作者线程
• AWT-Envent-Queue-0 事件调度线程
• 其它的线程不在我们感兴趣之列

我们要记住的是:

• 所有长时间的操作都不应该放在事件调度线程(EDT-Event Dispatch Thread，专门用来处理与界面响应相关的操作)中，否则界面在这段时间内将变得无法响应。
• 所有对SWING组件的更新（在其已经被显示出去后）都应当通过EDT来访问，否则有可能造成线程死锁或界面根本没有反映作出的更改。

不要被前面这几段弄晕了，只要弄清楚了 Swing 的线程体系，其实大部分工作JDK 已经为你做好了。我们所要做的就是按照范例实现我们的代码。这样就肯定安全可靠。


我们的例子是一个登录界面，这个界面要求输入用户名与密码，然后点击登录，正常情况下将与中心数据库进行通信。但考虑到文章的长度，我们将使用 Thread.sleep 来演示和长时间的网络操作。

最终的界面将如下所示，我们这里也不介绍怎样制作界面(是的，我的确是使用 NetBeans 的 Gui Builder 来制作的，但使用了一个自定义的 JImagePanel)




如果阅读过别人的代码或自己认真写过SWING方面的代码，在没有使用 SwingWorker 的 GUI 工程中，一定会有如下代码：

    java.awt.EventQueue.invokeLater(new Runnable() {
        public void run() {
            // 长时间的操作
        }
    });

这样做的目的就是为了使长时间的操作在另外的线程中运行。

为了使用面象对象的方式来处理这种行为，我们现在使用 SwingWorker。下面是我们的例子的代码:

import org.jdesktop.swingworker.SwingWorker;
import org.pprun.interviewofprologic.db.domain.UserBusinessDelegate;

/**
* Worker thread for login operation.
* @author pprun
*/
public class LoginSwingWorker extends SwingWorker {
private String username;
private char[] password;

private Exception exception;

/** Creates a new instance of LoginSwingWorker */
public LoginSwingWorker(String aUserName, char[] aPassword) {
this.username = aUserName;
this.password = aPassword;
}

/**
* 所有的后台操作都在这里，如果要动态将处理的数据发出去的话（比如数据库查询的应用），
* 可以在这里调用 publish 方法.
*/
@Override
protected Boolean doInBackground() throws Exception {
try {
    // 我们注释掉了这段代码，取而代之以假想的 Thread.sleep
    // UserBusinessDelegate cbd = UserBusinessDelegate.getInstance();
    // final boolean result = cbd.login(username, password);

    //return result;

    try {
        Thread.sleep(5000);

    } catch (InterruptedException interruptedException) {
        interruptedException.printStackTrace();
    }

        return true; // 如果想看看登录失败时的效果，return false;

} catch( Exception anyException ) {
    exception = anyException;
    throw exception;
}
}


/**
* Returns the exception thrown by the method doInBackground, if any, or
* null if no exception was generated.
* @return The exception generated by the call to doInBackground, or null
*  if no exception was generated.
*/
public Exception getDoInBackgroundException() {
return exception;
}
}

在触发端，点击 Ok 按钮时：

private void okJButtonActionPerformed(java.awt.event.ActionEvent evt) {                                 
    // ...

    loginSwingworker = new LoginSwingWorker(username, password);

    loginSwingworker.addPropertyChangeListener(this);
    loginSwingworker.execute();

      // ...
}

属性改变监听器的实现方法，监听在 SwingWorker 中的改变：

public void propertyChange(PropertyChangeEvent pce) {
if (pce.getSource() == loginSwingworker) {
    // property change event coming from the loginSwingworker
    if (pce.getPropertyName().equals("state") &&
            loginSwingworker.getState() == SwingWorker.StateValue.DONE ) {
        // loginSwingWorker 完成，但有可能抛出异常
        loginSwingworker.removePropertyChangeListener( this );
        if (loginSwingworker.getDoInBackgroundException() != null ) {
                 // 抛出异常
            if (true) {
                infoJLabel.setText("Error in login!");
            } else {
       
                infoJLabel.setText("Error in login!");
            }
        }

    } else if (loginSwingworker.isCancelled()) {
        // loginSwingowrker 被取消时的代码
}
}

关于在 Swing 中使用并发的详细资料，参见 Concurrency in Swing

体验更多 NetBeans 的新功能

不喜欢 NetBeans 的开发者往往指出 NetBeans 没有这个功能，没有那个功能。无可厚非，当时他们是对的，但随着时间的推移，现在也许错了：

1. Last Edit （是近更改按钮，带星号的那个），将你带到最近更改的地方




2. Diff SideBar (差异侧条), 根据所在行代码是增加、更改还是删除，在侧条中显示不同的小条，右击可以使用进一步的功能



3. JUnit4 支持（也就是现在可以使用基于 JDK 5 Annotation 的单元测试了）




4. Find/Replace in Project (全工程范围内搜索)，是的，这个功能我真的也非常需要:
看到左下方的"Replace" 按钮了吗？
值得注意的是，这个功能在 M9 中被屏蔽了，但在每日构建的版本中可以使用。

另外，大部分初次使用NetBeans 的开发者，不知道更改“自动完成弹出窗口”的键绑定，因为最常用的"Ctrl + 空格" 是不可工作的，因为在中文操作系统中被绑定到输入法的切换了。所以我一般把它改成 'Ctrl + Enter' , 如下进行：

1. Tools | Options -> Keymap -> Other
2. 找到 Show Code Completion Popup, 选中它，点击Add...
3. 按下任何所你希望的键序列，但是如果直接按 Ctrl + Enter 的话，系统提示这个组合键已经被绑定到 Split Line，所以如果我们要使用这个组合键的话，要先把它与 Split Line 解除绑定
4. 在 Show Code completion Popup 下方第六个即是　Split Line, 选中它，点击移除。你可以为这个功能提供另外的组合键，如果经常使用这一功能的话。
5. 然后，按照上述把"Ctrl + Enter " 加到 Show Code Completion Popup 中去。

(期待下一篇)