SAT problém v typové inferenci

Věděli jste, že Java generika mohou pro kompilátor představovat SAT problém? A že v důsledku toho může být čas kompilace exponenciální? Mě by to ani nenapadlo do chvíle, kdy jsem začal zjišťovat proč build jednoho z našich menších modulů trvá abnormálních pět minut.

Hlavní podezřelý byl jasný, protože to byl jediný modul, kde jsem ve velkém použil v testech Hamcrest matchery a build mrznul právě při kompilaci testů. Ano, při kompilaci! Chápal bych, kdyby build zdržoval běh špatně napsaných testů, ale kompilace? Jak se vlastně debuguje kompilátor?

Protože jsem rozhodně nechtěl buildovat vlastní OpenJDK, zkusil jsem to nejdřív intuicí. Ta mi napovídala, že problém se bude nějak týkat jednoho mého vlastního matcheru, který ‎matchoval zadaný atribut objektu generického typu. Hamcrest nabízí podobný matcher, ale ten není silně typový a mně připadalo, že by to s generiky a lambdami šlo napsat mnohem lépe. A taky že ano:

public class MyMatcher<T, U> extends BaseMatcher<T>{
	private Function<T, U> getter;
	private Matcher<U> matcher;

	public MyMatcher(Function<T, U> getter, Matcher<U> matcher) {
		this.getter = getter;
		this.matcher = matcher;
	}

	public boolean matches(Object item) {
		return matcher.matches(getter.apply((T) item));
	}

	public static <T, U> Matcher<T> attribute(Function<T, U> getter, Matcher<U> matcher) {
		return new MyMatcher<T, U>(getter, matcher);
	}

S tímto matcherem šlo ‎validovat košaté a hluboké objektové stromy bez jakýchkoli pomocných proměnných, cyklů nebo nekonečných getter řetězů a nullchecků. Všechny typové informace se zachovávaly v postupně se zanořujícím kontextu volání mého matcheru, takže refaktoring a jiné výhody typového systému zůstaly zachované i‎ v testech:

@Test
public void testApp() {
	Foo foo = new Foo();
	foo.setText("ahoj");
	Bar bar = new Bar();
	bar.setText("nazdar");
	bar.setAnotherText("čau");
	foo.setBar(bar);
    assertThat(foo, allOf(
    		attribute(Foo::getBar, allOf(
    				attribute(Bar::getText, is("nazdar")),
    				attribute(Bar::getAnotherText, is("čau")))),
    		attribute(Foo::getText, is("ahoj"))));
}

Obzvlášť si všimněte, jak je použití matcheru ‎úsporné a elegantní díky inferenci generik u návratového typu zanořovaných funkcí. Ale to se bohužel ukázalo jako onen‎ kámen úrazu. Chvilka googlování odhalila, že nejsem sám, kdo má s inferencí generik ve složitých výrazech problém. A že už je na to v JDK založen issue, resp. několik příbuzných issue.

Rozšíření inference i na návratové typy je poměrně nová featura Javy‎, takže by člověk předpokládal, že to je jen nedospělostí implementace a chyba bude brzy opravena, ale ono je to složitější. Klíč k pochopení leží v kapitole “Dependencies” odkazovaného JEPu:

This work depends on the Project Lambda JEP – Project Lambda requires a novel way of type-inference, called target-typing inference, that is used to infer the type of the formals of a lambda expression from the context in which the lambda expression is used. Part of this work (inference in method context) is simply a generalization of the approach exploited in project lambda.

Převzetím strategie inference z lambd totiž Java přebrala i její problémy, které hezky polopatě popsali přátelé z .NET: Aby kompilátor mohl inferovat datový typ, musí vyřešit SAT problém. Turing-úplnost typového systému tedy není bug, ale feature. Tomu říkám hustokrutopřísnost.

Jojo, Java nám dospívá a začíná se potýkat s problémy dospělosti.