The Navigame

Just a week remains until the New Year 2012 comes. The last year was the first one we at Luxoft have been able to make the maximum contribution to the development of the next-generation car navigation system which we are working on since 2008. The most prominent thing is the complete responsibility for the production chain, of course. At the same time the software products we are developing have matured a lot - thanks to all my colleagues, past and present.

As I really appreciate what our guys have done and are doing and at the same time I want to remember and cherish the good time we had in 2011, I decided to write a simple computer game on how we work. So, meet The Navigame:

After some trials and errors I decided to make it looking like a paper sketch (most likely soon I'll assemble a new version with enhanced graphics which I've asked my friend for). The good thing is that here I've finally found an application for the TTF-font I created two years ago.

The goal of the game is to develop the navigation system and to compile digital maps - as much as possible. For this you have a pool of skilled developers and map production engineers which can be assigned different tasks. There are developers who create the navigation software and production engineers who build the maps using the map compiler which is a part of navigation. The more the navigation system is feature-complete, the bigger maps can be handled with it. There are also some athmospheric features like customer PM or developers' curses. You basically should (a) finish the navigation development, (b) fulfil the map production plan and (c) earn as much money as possible.

To all people we worked with during the last 2-3 years: there are good chances that you find yourself inside the game - so give it a try :)


The source code, readme and binary download are available on Github at https://github.com/sborodavkin/navigame. It is required to have JRE installed as the game is developed in Java using Slick and LWJGL.

All contributions and feedback are warmly welcome.

Crow 1.1.0 released

Несмотря на то, что все фичи к релизу были подготовлены уже давно, акт выпуска новой версии произошел только сегодня.

Скачать можно отсюда.

В релиз 1.1.0 были включены 5 новых фич:

• 3364079 Export Traceability Matrix to Excel
• любой Traceability Report теперь можно сохранить в Excel-файл. Используется библиотека Apache POI.
• 3313584 Add filtering capabilities to Traceabilty tab
•  в окно "добавить трассировку" были добавлены текстовые поля для динамического поиска нужных элементов. Выглядит это так:

• 3300468 Filter Perforce changelists by description
•  аналогично предыдущей фиче, в окне добавления Perforce changelists теперь можно делать дополнительную фильтрацию по описанию:

• 3294913 Support new trace type DD2TRS
• несмотря на то, что ASPICE запрещает прямую трассировку TRS на детальный дизайн, бывают ситуации, когда описание архитектуры недоступно, и в этом случае установить необходимые трассы нельзя. Поэтому был добавлен новый тип связи, позволяющий трейсить TRS непосредственно на детальный дизайн и обратно.
• 2946382 Mark some CRS as "should not be traced"
• иногда в базе CRS есть отклоненные (rejected) или устаревшие требования, которые намеренно не покрыты TRSами, дизайном, кодом и т.д. Чтобы в отчете о трассировке эти CRS не светились красным цветом, появилась возможность обозначать их как "не трассируемые". В отчете это выглядит, например, вот так:

За реализацию фильтров и нового типа трассировки отдельное спасибо Саше Кондратюку!

Приятной работы!

Кстати, в этом релизе мы попробовали CodeStriker - бесплатный инструмент для проведения peer code review. По сравнению с Crucible - ужасно: неудобный интерфейс, корявое отображение исходников, для просмотра комментариев необходимо кликать на закладки (нет режима отображения кода вместе с комментариями).

Смешной код

Несколько смешных участков кода из нескольких проектов:

1. Магический скрипт

private final String magicScript = "\nif(8==8)return;";

2. Глубокая иерархия

public void dragEnter(DropTargetDragEvent arg0) {                                                            
   ((DropTargetListener)getParent().getParent().getParent()
      .getParent().getParent()).dragEnter(arg0);        
}                                                                                                            
                                                                                                             
public void dragExit(DropTargetEvent arg0) {                                                                 
   ((DropTargetListener)getParent().getParent().getParent()
      .getParent().getParent()).dragExit(arg0);         
                                                                                                             
}                                                                                                            
                                                                                                             
public void dragOver(DropTargetDragEvent arg0) {                                                             
   ((DropTargetListener)getParent().getParent().getParent()
      .getParent().getParent()).dragOver(arg0);         
                                                                                                             
}                                                                                                            
                                                                                                             
public void drop(DropTargetDropEvent arg0) {                                                                 
   ((DropTargetListener)getParent().getParent().getParent()
      .getParent().getParent()).drop(arg0);             
}                                                                                                            
                                                                                                             
public void dropActionChanged(DropTargetDragEvent arg0) {                                                    
   ((DropTargetListener)getParent().getParent().getParent()
      .getParent().getParent()).dropActionChanged(arg0);
}                                                                                    

3. Магические вычисления

int ww0 = getWidth() ;//- 40;                          
int hh0 = getHeight();// - 40;                         
int sz = Math.min(ww0, hh0);                           
                                                       
sz = sz/4*3;                                           
                                                       
                                                       
int y0 = (hh0 - sz) / 2;                               
                                                       
                                                       
                                                       
int x0 = 0;                                            
int h = sz / 2;                                        
int dh = sz / 4;                                       
                                                       
int y = y0 + h;                                        
                                                       
int hh = (int)Math.sqrt(h*h - h*h/4);                  
y0 = y - hh;                                           
                                                       
                                                       
Rectangle rect = new Rectangle(x0, y0 , sz,  hh + hh );
                                                       
int arrX[] = {x0 + dh, x0 + 3*dh, x0 + sz,             
              x0 + 3*dh   , x0 + dh, x0};              
int arrY[] = {y0 , y0 , y ,                            
               y0 + hh + hh, y0 + hh + hh, y};         
                                                       
Polygon poly = new Polygon(arrX, arrY, 6);             
                                                       
return poly;                                           

CROW: Control the Development Workflow

Начало истории - см. здесь.

Сегодня выложил на SourceForge.net исходники и snapshot-релиз своего нового Java-проекта CROW (Control the development workflow).

CROW - это ASPICE-совместимая система, предназначенная для управления и мониторинга:

• требований заказчика
• технических требований
• описания архитектуры
• детального дизайна
• ревизий кода в системе версионного контроля
• тестов

В настоящее время программа позволяет:

• добавлять/удалять/редактировать все артефакты, перечисленные выше
• устанавливать зависимости между ними (например, "changelist #800 реализует техническое требование REQ-007-DAT-DragAndDrop, которое описывает требование заказчика Support drag&drop of DAT-files")
• строить матрицу трассировки (RTM, Requirements Traceability Matrix), показывающую описанные выше отношения, в т.ч. транзитивные, т.е. связь между CRS и тестом через код, детальный дизайн, архитектуру и TRS программа вам покажет)
• создавать метки и присваивать их различным артефактам, что позволяет определять и фиксировать т.н. baseline для требований, ревизий, тестов и пр.
  

Немного о реализации:

• JRE 1.6, в более старых не тестировал и не хочу.
  
• GUI в виде Swing-клиента. Пишу для Windows, но в Linux тоже проверял - явных косяков нет.
• База - через Hibernate. В текущей реализации используется PostgreSQL.
• Использую docking framework VLDocking, чтобы все окошки можно было перетаскивать как нравится.
• Пишу все сам, тестировщиков также нет. Добровольцы призываются!
  

Адрес проекта на SourceForge - http://sourceforge.net/projects/opencrow/.

Баг в JTable: теряется множественный selection при начале DnD

Пишу класс, перегружающий JTable, и снова вижу баг, который видел еще под JRE 1.4.2 году в 2006-м.

Ссылка на баг: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6195469.

Ошибка заключается в том, что, если в JTable выделить несколько ячеек и попытаться их перетащить (drag & drop), то, сразу же после нажатия кнопки мыши, selection сбрасывается со всех ячеек, кроме той, на которую непосредстенно нажали.

Воркараунд, приведенный по ссылке выше, по крайней мере в 1.6 не работает. Поэтому выкладываю свой класс FixedTableUI, которым можно подменить тот класс, который предлагается в воркараунде. Работает с 1.4 по 1.6 включительно:

   /**
    * This internal helper class helps to solve two bugs:
    * The first is disable row selection with mouse drag
    * The second is allow handling of multiple selected rows without need to
    * hold a Shift key.
    */   
   private class FixedTableUI extends BasicTableUI {
      private MouseInputHandler handler = new MouseInputHandler() {
         
         private boolean isShiftDownInMousePressed = false;

         
         public void mouseDragged(MouseEvent e) {
            // Do nothing here!
         }
         
         public void mousePressed(MouseEvent e) {
            isShiftDownInMousePressed = e.isShiftDown();             
            int row = rowAtPoint(e.getPoint());
            if (!getSelectionModel().isSelectedIndex(row)) {
               super.mousePressed(e);
            } else {                
               if (e.isControlDown()) {
                  if (getSelectionModel().isSelectedIndex(row)) {
                     getSelectionModel().removeSelectionInterval(row, row);
                  }
               }
            }
         }
         
         public void mouseReleased(MouseEvent e) {
            super.mouseReleased(e);
            int row = rowAtPoint(e.getPoint());
            int col = columnAtPoint(e.getPoint());
            int[] selRows = getSelectedRows();
            if (selRows.length > 0) {
               if (!e.isControlDown() && !e.isShiftDown() &&
                     !isShiftDownInMousePressed) {             
                  getSelectionModel().setSelectionInterval(row, row);
               }
            }
         }
      };
      
      protected MouseInputListener createMouseInputListener() {
         return handler;
      }     
   }

java.io.tmpdir в Windows и Linux

Только что попробовал запустить в Убунту программу, разработанную под Windows. Ну что сказать - был удивлен.

System.getProperty("java.io.tmpdir") в Windows возвращает что-то наподобие:

C:\Windows\Temp\

А в Linux мне приходит вот что:

/tmp

Обратите внимание - в первом случае завершающий слеш есть, а во втором - нет, что требует дополнительной проверки в коде.

"Java: написано однажды - тестируем везде" (c)

JTabbedPane и фокус в ней

Сегодня нашел новый (для меня, разумеется) баг в Swing. Проблема заключается в том, что если на панели есть JTabbedPane, а в ней лежит компонент, который должен получить фокус после того, как происходит переключение на соответствующий таб, то фокус этот он не получит.

Вот неработающий код:

tabPane.addChangeListener(new ChangeListener() {
  public void stateChanged(ChangeEvent e) {
    txtName.requestFocusInWindow();
  }    
});

Баг #5089436 (а ему уже около 5 лет) предлагает воркэраунд, связанный с обрамлением вызова requestFocusInWindow() в  invokeLater():

tabPane.addChangeListener(new ChangeListener() {
  public void stateChanged(ChangeEvent e) {
    EventQueue.invokeLater(new Runnable() {    
      public void run() {
        txtName.requestFocusInWindow();
      });
  }    
});

А в остальном Свинг по-прежнему хорош.

На пути к оптимизации

Только что наткнулся на такой вот участок кода в нашем приложении:

// This method produces a HUGE overhead
//TreeNodesUpdater.updateComponentTreeUI(this);
  
// This works, but cuts end part of lines in bold (produces "...")
/*this.invalidate();
this.validate();
this.repaint();*/
  
// So, we just switch the renderer to null and back to the original one,
// which revalidates the sizes
setCellRenderer(null);
TreeCellRenderer renderer = createCellRenderer();

setCellRenderer(renderer); 

А за каждой из этих строчек - целая история...

Война подчеркивания и дефиса: разные стандарты именования в Maven и Eclipse PDE

В одном из наших Eclipse-проектов сборка происходит следующим образом:

1. Сначала мы собираем target-платформу для системы uDig (user-friendly Internet GIS) - набор OSGi-bundles. Состоит она из:

• GeoAPI и ее зависимостей
• GeoTools и ее зависимостей
  

Сборка GeoAPI и GeoTools выпоняется с помощью Apache Maven, который автоматически скачивает нужные зависимости с прописанных репозиториев, запускает компилятор, генерирует MANIFEST.MF для OSGi-бандлов - короче, делает все. В результате мы имеем папку с набором JAR-файлов примерно следующего содержания:
...
java3d.osgi.vecmath-1.3.1.jar
javax.media.jai.osgi.jai_imageio-1.1.0.jar
net.opengis.ows-2.6.0-SNAPSHOT.jar
...

Эта папка - не что иное, как target platform для компиляции uDig, которая делается через PDE.

2. Мы запускаем Eclispe PDE batch build и компилируем uDig. В результате мы получаем продукт uDig, в папке plugins которого, среди прочих, оказываются уже такие файлы:
...
java3d.osgi.vecmath_1.3.1.jar
javax.media.jai.osgi.jai_imageio_1.1.0.jar
net.opengis.ows_2.6.0_SNAPSHOT.jar
...

Первый вывод уже очевиден:

Maven использует "-" (дефис) для отделения номера версии от имени бандла, в то время как PDE использует для этого "_" (подчеркивание)

3. Для того, чтобы собрать наш проект, нам нужна платформа в составе:

• OSGi-бандлы из папки plugins системы uDig
• наши проприетарные модули и их зависимости
  

Причем сборка второго пункта также выполняется с помощью Maven. Соответственно, нам очень удобно использовать модули, уже находящиеся в локальном m2-репозитории - такие, как, например, java3d.osgi.vecmath-1.3.1.jar. Однако, когда мы пытаемся добавить к нашим плагинам плагины из uDig, начинаются проблемы, поскольку в uDig, как мы помним, соответствующая библиотека называется уже java3d.osgi.vecmath_1.3.1.jar (подчеркивание вместо дефиса). Поэтому в результате простого копирования файлов получаем следующую картину:
...
java3d.osgi.vecmath_1.3.1.jar
java3d.osgi.vecmath-1.3.1.jar
javax.media.jai.osgi.jai_imageio_1.1.0.jar
javax.media.jai.osgi.jai_imageio-1.1.0.jar
net.opengis.ows_2.6.0_SNAPSHOT.jar
net.opengis.ows_2.6.0-SNAPSHOT.jar
...
Т.е. набор идентичных по смылу OSGi-бандлов, но продублированных в файлах с разными именами.

Пока что, чтобы решить эту проблему, я стал используюVBS-скрипт, который переименовывает файлы по заданному регулярному выражению с тем, чтобы заменить подчеркивание на дефис. Хотя, наверное, нужно делать это прямо в PDE-сборке и заменять наоборот - дефис на подчеркивание...

А война дефиса и подчеркивания, между прочим, разгорелась нешуточная. В мейл-листах Maven утверждают, что единственно верный разделитель - это дефис. Эклипс пока что понимает только подчеркивание, хотя в 3.5 обещают это исправить (в 3.5 М4, вроде, уже вставили соответствующий патч).

Как JComboBox всех зарулил

И снова Swing, и снова баг - на этот раз в JComboBox. Состоит в следующем:


JComboBox box = new JComboBox();
box.addItem("x");
box.addItem("x");
box.setSelectedIndex(1);
System.out.println(box.getSelectedIndex())


Этот код напечатает в консоль не 1, как ожидалось, а 0. Баг состоит в том, что метод getSelectedIndex() возвращает индекс первого попавшегося элемента, равного селектированному, причем сравнение выполняется методом equals().

В развернувшейся бурной дискуссии сотрудники Sun пытаются доказать, что данное поведение корректно, поскольку оба элемента x равны. Лично я не согласен: так мог бы вести себя метод getSelectedItem(), но от getSelectedIndex() я бы ожидал возврат выбранного индекса , а не какого-нибудь другого.

Багу #4133743 уже более 10-ти лет. Интересно состояние данного тикета: "11-Closed, Not a Defect, bug". :))

pnuts drives me crazy

Пишу на pnuts. pnuts - это скриптовый язык, мы активно его используем.

Короче, объявляю класс. Когда я для какого-то из его полей объявляю cеттер, а впоследствии вызываю его, то чудный пи-натсовый интерпретатор вываливается со StackOverflowError:

java.lang.StackOverflowError
at java.lang.String.indexOf(Unknown Source)
at java.lang.ClassLoader.checkName(Unknown Source)
at java.lang.ClassLoader.findLoadedClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at sun.misc.Launcher$AppClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at java.lang.ClassLoader.loadClassInternal(Unknown Source)
at sun.reflect.GeneratedMethodAccessor63.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at pnuts.lang.Runtime.setBeanProperty(Runtime.java:3066)
at pnuts.lang.JavaBeansConfiguration.setBeanProperty(JavaBeansConfiguration.java:154)
at pnuts.lang.JavaBeansConfiguration.putField(JavaBeansConfiguration.java:136)
at pnuts.lang.Java2Configuration.putField(Java2Configuration.java:101)
at pnuts.lang.Runtime.putField(Runtime.java:547)
at _pnuts_$2.exec(Unknown Source)
at pnuts.lang.PnutsFunction.exec(PnutsFunction.java:294)
at pnuts.lang.PnutsFunction.call(PnutsFunction.java:232)
at SamePOI.setDistance(Unknown Source)
at sun.reflect.GeneratedMethodAccessor63.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at pnuts.lang.Runtime.setBeanProperty(Runtime.java:3066)
at pnuts.lang.JavaBeansConfiguration.setBeanProperty(JavaBeansConfiguration.java:154)
at pnuts.lang.JavaBeansConfiguration.putField(JavaBeansConfiguration.java:136)
at pnuts.lang.Java2Configuration.putField(Java2Configuration.java:101)
at pnuts.lang.Runtime.putField(Runtime.java:547)
at _pnuts_$2.exec(Unknown Source)
... и т.д.


А если присваивать полю значение непосредственно снаружи, то все работает!

Сеттер имеет вполне типичный вид:

void setDistance(int d) {
this.distance = d
}

В чем проблема - ума не приложу! И с геттером, кстати, та же фигня :(

UPD 18:12 А вот еще что раздражает: длинные заголовки методов класса можно разбивать только так:

void myMethod(int param1, String
param2, bool param3)

Т.е. перевод строки можно ставить ТОЛЬКО между типом и параметром. Так работать не будет:

void myMethod(int param1,
String param2, bool param3)

Я специально взял отсюда и расковырял грамматику языка, чтобы убедиться, что так оно и есть:

TypedParamList = "(" ( ")" | TypedParam ("," TypedParam  )* ")" ) ;
TypedParam = Param | ClassName Param ;
Param = Eol IDENTIFIER Eol ;

Т.е., если указываем ClassName, то Eol может следовать только сразу после него, либо (что еще страннее), ПЕРЕД запятой. Но не после. Т.е. так тоже будет работать:

void myMethod(int param1
,String param2, bool param3)

Вот так и проходит рабочее время))

Еще один баг от Swing

Только что еще один Свинговый баг побороли. На одной из ~10 машин, где работает наша программа, запуск диалога выбора файлов JFileChooser занимает примерно полминуты (ну о-о-очень долго, если честно). Кроме того, переход в любую папку также отбирает несколько секунд. Windows XP SP2 стоит, последние обновления, все дела... А на других машинах - все хорошо.

После непродолжительного копания, наткнулся на описание Java-Sun bug #5050516. Оказывается, на некоторых системах такое поведение вызывается поддержкой Windows Compressed Folders. После того, как отключили ее командой

regsvr32 /u %windir%\system32\zipfldr.dll,

все заработало быстро и правильно.

Багу больше 4х лет. В jdk 1.6 он еще живет. Вроде, исправили в седьмом, но я не проверял))

YourKit

Открыл для себя замечательный профилировщик (он же профайлер) - называется YourKit. Умеет профилировать и CPU, и память, и потоки, и дедлоки... А, во, еще имеет плагин для Eclipse, позволяющий запускать профайлинг прямо оттуда.

Не, я реально в восторге! Только что с его помощью выяснил, почему в одном из наших продуктов не высвобождалась память при закрытии старого документа и открытии нового. Наш обработчик тултипов хранил ссылку на TableColumn, который хранил ссылку на объект SwingPropertyChangeSupport, у которого в списке маус-моушн-лиснеров зачем-то хранилась DefaultTableModel. Из-за этой "лишней" ссылки на данные GC никогда их реально и не прибивал... Ну, блин, Swing!!! А YourKit все сразу показал - и самые большие объекты в памяти, и ссылки на них.

Зараза, к сожалению, платная, но обладает 15-дневным пробным ключом активации. Очень рекомендую попробовать! Ведь как приятно, после дня мучений, увидеть такой замечательный график:

Баг в Swing: редактирование ячейки JTable отменяется при ресайзе столбца

Я всегда говорил, что разработка под Swing сродни ходьбе по минному полю - никогда не знаешь, под какой ногой рванет в следующую минуту.

Сегодня (в который раз!) рванула JTable. Я напоролся на баг, который заключается в следующем: если начать ресайзить столбец таблицы в процессе редактирования ее ячейки, то введенный во время редактирования текст исчезает - вместо него возникает предыдущее значение.

Вот так вот. Багу #4330950 уже почти восемь лет.

Интересно было почитать комментарии к нему на сайте Sun:

• 17 июня 2002 г.: можете пообещать, что это будет исправлено в 1.4.1?
  
• 6 августа 2005 г.: это должно быт обязательно исправлено в Java 6!
  26 июня 2007 г.: проблема все еще жива в j2se 1.6.1!

В этот раз workaround нашелся. Там же, по ссылке, в комментах добрые люди советуют, что надо делать. Спасибо им за это!

Java Multi-Level Undo Technique (Reflection API)

1. Overview

The best examples of the end-user software leave absolutely no doubt that undo capability is not an option ever more. Currently every application that can alter existing data has to support undo and redo operations, which allow to cancel the changes made by user and to repeat them again as needed. As user knows that he can eliminate carelessly changes at any time, his work becomes more comfortable and the software is considered reliable and predictable.

For some reasons, still many applications support only limited undo/redo capabilities, allowing canceling and repeating only single operation. There is no need to prove that multi-level undo is much better. In this article I'm going to show that implementing multi-level undo in Java is easy, requires minimal amount of changes in your existing code and can be separated to reuse the approach in future. The top of the iceberg is already well-known to the developers who have had an experience with programming for Mac OS X using Cocoa framework which has the NSUndoManager class utilizing a similar technique.

The article is divided into sections describing the approach. In the next section, “Introduction to Java Reflection API”, a very brief description of things is given. If you are already familiar with reflection, you can skip this and move on to the next section, “Implementing basic undo/redo handling”. The last one, “Tuning the undo engine”, is devoted to improving the solution. After it, the conclusions and some tips on how to continue are given.

2. Introduction to Java Reflection API

The reflection library gives you a rich instrumentation to work with your Java code dynamically. For example, if a new class is added to the application during development, it is possible to organize a set of requests to get know the features of that class. Saying more generally, reflection is a way that a program can use to know about itself. Among the possibilities opened with it, are:

• analyzing the features of the classes during the runtime
  
• checking the object state during the runtime by getting the information about its fields and the values contained there
  
• using the Method instances that work similar to the pointers to functions in languages like C++, etc.
  

Consider, for example, a class with rather strange name: Class (java.lang.Class, to be more precise). The instance of the class Class is an object describing the particular properties of a particular class. Here is an example:

public abstract class Shape { . . . }

public class Circle extends Shape { . . . }

public class Square extends Shape { . . . }

. . .

Shape s;

. . .

Class c = s.getClass();

System.out.println(c.getName() + " " + s.toString());

The last operator can print the line “Circle radius=10”, if s is a Circle instance, or “Square side=5”, if s is a Square instance.

Now you can do whatever you want. Imagine that you don’t know the exact class of s, but it is necessary to create another instance of the same class. The following call is the solution:

Shape s1 = s.getClass().newInstance();

Here the default constructor is used to initialize s1. If there is no default constructor for the class, an exception is thrown.

You can extend your knowledge about reflection by checking out the classes Field, Method and Constructor in the java.lang.reflect package. Summing up, the key feature of reflection is the ability to instantiate and work with some entities that are the parts of the application, be it a class, its constructor, a field or its modifier, etc. Actually, the possibility to refer to a class method as to an instance of the Method class is the core of the proposed undo technique. Now we are ready to begin implementing undo mechanism.

3. Implementing basic undo/redo handling

Primarily, undo support is heavily based on using the LIFO queue (stack), as the last performed operation has to be undone first. So, it is obvious that the class being developed, let’s call it UndoManager, will have undoStack as its member. Let’s start from the following code:

public class Pair {
      public Object first;
      public Object second;

      public Pair(Object f, Object s) {
            first = f;
            second = s;
      }
}

public class UndoManager {
      private Stack undoStack = null;
      private Object target = null;

      public UndoManager(Object forWhom) {
            undoStack = new Stack(); 
            target = forWhom;
      }

      public void addInvocation(Method method, Object[] args) {
            Pair p = new Pair(method, args);
            undoStack.push(p);
      }

      public boolean canUndo() {
            return (undoStack.size() > 0);
      }

      public void undo() {
            if (!canUndo()) {
                  return;
            }
            Object obj = undoStack.pop();
            if (obj instanceof Pair) {   
                  Pair p = (Pair)obj;
                  invokeCommand(p);
            }
      }

      protected void invokeCommand(Pair p) {
            Method method = (Method)p.first;
            Object[] args = (Object[])p.second;
            try {
                  method.invoke(target, args);
                  return;       
            } catch (Exception ex) {
                  System.err.println("Cannot undo " + method.getName());
                  ex.printStackTrace();
                  return;
            }
      }
}

Here class Pair is a helper which simply allows storing two objects together. The undo is actually performed by an UndoManager instance. As it is shown, it is necessary to pass the target object to its constructor. Target object is the instance responsible for making the actions and organizing the undo workflow.

To add a method invocation to UndoManager, it is necessary to call method addInvocation(Method method, Object[] args), where method is target object’s method that will be called during undo; args is an array of arguments that will be passed to method. addInvocation simply stores the given method and its arguments into a Pair instance in the undo stack.

When the method undo() is called, the following happens. The last Pair is popped from the undo stack, and the target object’s appropriate method with its arguments is executed. Of course, an exception is thrown when something goes wrong.

Actually, this is all for undo. However, additional efforts are needed to support redo. As you can see, after the method is undone, it simply disappears and thus cannot be redone:

public void undo() {
      . . .
      Object obj = undoStack.pop();
      . . .
}

To redo this method later, it is needed to store it somewhere. The right place to do so is another stack called redoStack. For example, after the sequence of methods A B C has been executed, the undoStack contains the C B A sequence (C will be executed first during undo). If we put each method being undone to the redoStack, then it will contain the sequence A B C again. Undo stack has reverse order, redo stack has direct order – this is what we need.

The changes to UndoManager class are the following:

. . .
private Stack redoStack = null;
. . .
public UndoManager(Object forWhom) {
      . . .
      redoStack = new Stack();
      . . .
}
. . .
public boolean canRedo() {
      return (redoStack.size() > 0);
}
. . .
public void redo() {
      if (!canRedo()) {
            return;
      }
      Object obj = redoStack.pop();
      if (obj instanceof Pair) {      
            Pair p = (Pair)obj;
            invokeCommand(p);
      }
}

Attentive reader will notice that there is no way to fill redoStack. Seems it remains empty all the time. So, it is time to talk about the organization of the target object. Does it have to meet some special requirements? Let’s start with example:

public class MyClass {

     private String value;

     public MyClass() {
          value = "";
     }

     public String getValue() {
          return value;
     }

     public void setValue(String s) {
          value = s;
     }
}

Let’s imagine that we need to support undo/redo for the method setValue(String s). Of course, first we need to provide MyClass with its own UndoManager instance. Second, the setValue() method has to be changed to the following:

public void setValue(String s) {
      try {
            // Get the method as an instance
            Method m = this.getClass().getDeclaredMethod(
                  "setValue",
                  new Class[]{String.class}
            );
            // Get the current value
            Object[] args = new Object[]{getValue()};
            // Add it to the undo manager
            undoManager.addInvocation(m, args);
      } catch (Exception e) {
            // . . .
      }

      // Modify value
      value = s;
}

In the added try-catch block we first get the reference to the method, then save the current value and add this data to the undo manager. Afterwards it is safe to modify the value: when we call undoManager.undo(), the method setValue() will be invoked with the previous value as an argument, so that it will be restored.

That’s nice, isn’t it? Let’s look at the sample sequence of events:

1. We call setValue("A"). The invocation setValue("") is added to the undo manager.
   
2. The new value is set.
   
3. We call undo(), during which the undo manager makes the setValue("") invocation that restores the old (empty) value and… adds invocation setValue("A") to the undo manager!
   

So, there are actually two sources for the undoManager.addInvocation() execution: the method setValue() (or, saying more generally, the undo invocation method, call A) and, the undoManager.undo() method, call B. If call A is the place where a method invocation should be added to the undo stack, then call B is the place to add invocation to the redo stack. This approach can be implemented by providing the boolean variable isUndoing to the UndoManager class. It should be set in the undo() method like:

public void undo() {
      isUndoing = true;
      . . .
      isUndoing = false;
}

As we have found out, there will be an addInvocation() call, caused by the organization of the method being undone, inside the undo() method. Now it becomes clear how the UndoManager’s addInvocation() method should look:

public void addInvocation(Method method, Object[] args) {
      Pair p = new Pair(method, args);
      if (isUndoing) {
            redoStack.push(p);
      } else {
            undoStack.push(p);
      }
}

Now we have both undo and redo. Also we know how to organize the undo invocation methods in the target class. The last section of the article is devoted to improving the approach.

4. Tuning the undo engine

There are still two things to be done. First: sometimes it is needed to clear the redo stack. For example, we have executed operations A, B, C and D. Afterwards we have undone D and C. Now the undo stack contains B and A, and the redo stack contains C and D. If now we execute some different operation E, then the true history of operations will be A, B, E. However, C and D are still stored in the redo stack – in this case it should be cleared. The rule is the following: redo stack should be cleared each time when a method invocation is added to the undo manager, if it is not in undoing or redoing state. Such a check must be done in the addInvocation() method.

The second thing: it is often needed to group undo/redo operations to execute multiple of them in a single undo or redo step. For example, if you type the word “peace” in your favorite text editor, then you probably expect that the whole word will disappear when you press the undo button on its toolbar, not only the last letter of it. To do so, we may add yet another stack to the UndoManager class (let’s call it groupStack) that will collect undo operations to group. Also it is needed to add the boolean variable, isUndoGroupOpened, and to create the following methods:

public void beginUndoGroup() {
      if (isUndoGroupOpened == true) {
            throw new IllegalStateException("beginUndoGroup() call while undo group is already opened");
      }
      isUndoGroupOpened = true;
}

public void endUndoGroup() {

      if (isUndoGroupOpened == false) {

            throw new IllegalStateException("endUndoGroup() call without matching beginUndoGroup()");
      }
      ArrayList actions = new ArrayList(groupStack);
      if (isUndoing) {
            redoStack.push(actions);
      } else {
            undoStack.push(actions);          
      }
      isUndoGroupOpened = false;
      groupStack.clear();
}

The undo group, when closed, will be stored in the corresponding stack as an ArrayList. Now, inside the undo()/redo() methods, it is possible to track this situation and perform all operations in the ArrayList at a time.

The complete source code of the resulting UndoManager class is the following:

import java.lang.reflect.Method;
import java.util.*;

public class UndoManager {
      private Stack undoStack = null;    
      private Stack redoStack = null;
      private Object target = null;
      private boolean isUndoGroupOpened;
      private Stack groupStack = null;
      private boolean isUndoing;
      private boolean isRedoing;
      
      public UndoManager(Object forWhom) {
            undoStack = new Stack();
            redoStack = new Stack();
            groupStack = new Stack();
            target = forWhom;
            isUndoGroupOpened = false;
            isUndoing = false;
            isRedoing = false;
      }      

      public void addInvocation(Method method, Object[] args) {        
            if (!isUndoing && !isRedoing) {                
                  redoStack.clear();
            }           

            Pair p = new Pair(method, args);
            if (isUndoGroupOpened) {
                  groupStack.push(p);
            } else {
                  if (isUndoing) {                   
                        redoStack.push(p);
                  } else {
                        undoStack.push(p);
                  }                                  
            }           
      }

      public void beginUndoGroup() {
            if (isUndoGroupOpened == true) {
                  throw new IllegalStateException("beginUndoGroup() while " +
                        "undo group is already opened");
            }
            isUndoGroupOpened = true;
      }

      public void endUndoGroup() {
            if (isUndoGroupOpened == false) {
                  throw new IllegalStateException("endUndoGroup() without " +
                        "matching beginUndoGroup()");
            }

            ArrayList actions = new ArrayList(groupStack);
            if (isUndoing) {
                  redoStack.push(actions);
            } else {
                  undoStack.push(actions);           
            }
            isUndoGroupOpened = false;
            groupStack.clear();
      }

      public boolean canUndo() {
            return (undoStack.size() > 0);
      }     

      public boolean canRedo() {
            return (redoStack.size() > 0);
      }
       
      public void undo() {
            if (!canUndo()) {
                  return;
            }

            if (isUndoing || isRedoing) {
                  throw new IllegalStateException();
            }
            isUndoing = true;
            Object obj = undoStack.pop();
            if (obj instanceof Pair) {   
                  // Plain undo
                  Pair p = (Pair)obj;
                  invokeCommand(p);
            } else if (obj instanceof ArrayList) {
                  // Undo group
                  beginUndoGroup();
                  ArrayList actions = (ArrayList)obj;
                  for (int i = actions.size() - 1; i >= 0; i--) {
                        Pair p = (Pair)actions.get(i);
                        invokeCommand(p);
                  }
                  endUndoGroup();
            }
            isUndoing = false;
      }

      protected void invokeCommand(Pair p) {
            Method method = (Method)p.first;
            Object[] args = (Object[])p.second;
            try {
                  method.invoke(target, args);       
                  return;                 
            } catch (Exception ex) {
                  System.err.println("Cannot undo method " + method.getName());
                  ex.printStackTrace();
                  return;
            }
      }

      public void redo() {
            if (!canRedo()) {
                  return;
            }
            if (isUndoing || isRedoing) {
                  throw new IllegalStateException();
            }
            isRedoing = true;
            Object obj = redoStack.pop();
            if (obj instanceof Pair) {               
                  // Plain redo
                  Pair p = (Pair)obj;
                  invokeCommand(p);
            } else if (obj instanceof ArrayList) {
                  // Redo group
                  beginUndoGroup();
                  ArrayList actions = (ArrayList)obj;
                  for (int i = actions.size() - 1; i >= 0; i--) {
                        Pair p = (Pair)actions.get(i);
                        invokeCommand(p);
                  }
                  endUndoGroup();
            }
            isRedoing = false;
      }
}

4. Conclusions

The described approach helps to implement undo/redo functionality in your Java application fast and easy. This solution is different from the traditional way, where the design pattern Command is often used. Using reflection for undo is better as it doesn’t require the objects to implement some special interfaces. The only requirement for the undo method is to store its invocation with the previous arguments in the undo manager.

The further improvement of the proposed technique may be an effort to make it run safely in a multithreaded environment. Also, it is still possible to simplify the changes needed for undo methods and to improve the error handling. However, such a technique remains simple, can be provided without big changes to the existing code, and thus helps to get the desired results faster.