Pád aplikace při řazení v tabulce

Před nějakou dobou jsem řešil zajímavý programátorský problém: aplikace přestala reagovat při opakovaném řazení tabulky s výsledky. Překvapila mne nejen chyba jako taková, ale hlavně její příčina. Vždyť tohle přece nemůže nastat!

Jednalo se o desktopovou aplikaci běžící pod MS Windows naprogramovanou v jazyce Java s využitím knihoven SWT.

Odhalení chyby

Při odhalování chyby se ukázalo jako výhoda, že tester prováděl při testování průběžné snímání obrazovky a jako popis chyby přiložil výsledné video. O co šlo: tester provedl nastavení a spustil měření. To je dlouhodobý proces, takže při čekání na výsledek "si tester začal hrát," přičemž víceméně náhodně klikal na řazení tabulky s výsledky. Tímto "hraním si" však chybu odhalil, ale mně nějakou dobu trvalo, než jsem stanovil jednoznačný postup pro reprodukci. Při standardním testování a při vývoji se totiž chyba neprojevila.

Při analýze jsem zjistil, že pád aplikace byl způsoben následující výjimkou:

Exception in thread "main" java.lang.IllegalArgumentException: 
                                   Comparison method violates its general contract!
	at java.util.TimSort.mergeLo(Unknown Source)
	at java.util.TimSort.mergeAt(Unknown Source)
	at java.util.TimSort.mergeCollapse(Unknown Source)
	at java.util.TimSort.sort(Unknown Source)
	at java.util.TimSort.sort(Unknown Source)
	at java.util.Arrays.sort(Unknown Source)
	at org.eclipse.jface.viewers.ViewerComparator.sort(ViewerComparator.java:185)
	at org.eclipse.jface.viewers.StructuredViewer.getSortedChildren(StructuredViewer.java:1050)
	at org.eclipse.jface.viewers.AbstractTableViewer.internalRefreshAll(AbstractTableViewer.java:701)
	at org.eclipse.jface.viewers.AbstractTableViewer.internalRefresh(AbstractTableViewer.java:649)
	at org.eclipse.jface.viewers.StructuredViewer$8.run(StructuredViewer.java:1514)
	at org.eclipse.jface.viewers.StructuredViewer.preservingSelection(StructuredViewer.java:1422)
	at org.eclipse.jface.viewers.StructuredViewer.preservingSelection(StructuredViewer.java:1383)
	at org.eclipse.jface.viewers.StructuredViewer.refresh(StructuredViewer.java:1512)
	at org.eclipse.jface.viewers.ColumnViewer.refresh(ColumnViewer.java:548)
	at org.eclipse.jface.viewers.StructuredViewer.refresh(StructuredViewer.java:1469)
	...

To znamená, že při definici metody pro porovnávání prvků tabulky byl někde porušen obecný kontrakt pro porovnávání, tj. a = a, a pokud a < b, musí zároveň platit, že b > a. Na první pohled samozřejmost, ale...

Analýza chyby

Původní myšlenku, že v průběhu řazení došlo zároveň k aktualizaci výsledku, jsem zamítnul, jednak na základě experimentů, jednak na základě faktu, že modifikaci GUI v SWT může provádět pouze GUI vlákno, které je dobře synchronizované, tudíž souběh požadavků na řazení a na aktualizaci tabulky je prakticky vyloučen.

Chyba tedy musela být v implementaci metody ViewerComparator.compare(...). Řazení mělo velmi specifické požadavky (referenční carrier vždy nahoře, pak měřené, pak neměřené atd.), což bylo nutno při implementaci porovnávání zohlednit. A protože ani code review chybu neodhalil, rozhodl jsem se provést následující experiment.

Při výskytu výjimky jsem si nechal všechny prvky tabulky vyexportovat do Excelu jako matici, kde řádky a sloupce odpovídaly jednotlivým prvkům a jednotlivá pole v tabulce zobrazovala výsledek vzájemného porovnávání. Výsledná matice vypadala přibližně takto:

	A	B	C	D	E
A	1	1	1	-1	1
B	1	1	-1	1	1
C	1	-1	-1	-1	1
D	1	-1	-1	1	-1
E	-1	1	1	1	1

Původní motivace experimentu byla provést kontrolu správnosti výsledků jednotlivých porovnání. První pohled na matici však odhalil zásadní problém: matice by měla být antisymetrická, tj. v hlavní diagonále nuly, a pokud je v poli nad hlavní diagonálou hodnota 1, měla by být v odpovídajícím poli pod diagonálou hodnota -1, a naopak. Což na první pohled neplatí. Příčina chyby je tedy jednoznačná: špatná implementace ViewerComparator.compare(...).

Řešení

Aby bylo možno vyhovět specifickým požadavkům na řazení a zároveň aby mohl být snadno splnitelný obecný kontrakt pro porovnávání, rozhodl jsem se pro změnu implementace porovnávání následujícím způsobem: zavedl jsem "virtuální sloupec" kategorie. Prvky v tabulce byly na základě svých atributů zařazeny do kategorií. Při řazení pak byly prvky seřazeny nejprve podle kategorie a až v rámci jednotlivých kategorií byly seřazeny podle hodnoty.

Kromě vlastního řešení problému s pádem aplikace byla nová implementace i jednodušší a přehlednější, což se projevilo i snadnější implementací zavedení nové kategorie.

Inspirací pro řešení byla implementace ViewerComparator.compare(...), přestože v podobě, jak byla původně navržena a implementována, nešla úplně použít.