A suggestion for Declarative Shadow Variables

[GUIpsp]

Although this feature is well-written and very welcome, I think there are some directions you could consider exploring before release. For context, I'm an optimisation algorithm developer at Dots & Lines. However, my background is in programming languages. As such, everywhere I look I see opportunities for a compiler.

It's very easy for me (aka, it happened to me multiple times) to forget to update the dependency information when the implementation is updated during development. To minimise this, I propose the following:

Inferring data dependencies

While bringing the variable dependencies declaration closer to the listener implementation (this feature) helps keep both in sync, nothing beats not having to write the dependencies in the first place. Thus, I see a huge opportunity of inferring the data dependencies straight from the bytecode.

I am aware that not all functions are easy to analyse. A first implementation of this analysis would probably bail out on any kind of backwards control flow (loops). But the restrictions you already place on these listeners (for example, they can't mutate the solution other than by returning the new value) makes for a simpler analysis.

Not having to write the data dependencies makes specifying them incorrectly impossible - and for functions that the analysis does not cover, the user can fall back to specifying them manually as is currently required.

That is, where you currently:

@PlanningEntity
public class Job {
 @PlanningVariable
    private LocalDate startDate;
    private int durationInDays;

 @ShadowVariable(supplierName="endDateSupplier")
    private LocalDate endDate;

 @ShadowSources("startDate")
    public LocalDate endDateSupplier() {
        if (startDate == null) {
            return null;
         } else {
                    return startDate.plusDays(durationInDays);
         }
   }
}

I propose you should be able to write:

@PlanningEntity
public class Job {
 @PlanningVariable
    private LocalDate startDate;
    private int durationInDays;

 @ShadowVariable(supplierName="endDateSupplier")
    private LocalDate endDate;

 @ShadowSources() // dependency on startDate automatically inferred
    public LocalDate endDateSupplier() {
        if (startDate == null) {
            return null;
 } else {
            return startDate.plusDays(durationInDays);
         }
   }
}

If you do decide to accept this suggestion, I think you should prioritize correctness over completeness (that is, analysing functions correctly, rather than analysing every function). This ensures that the user can trust the analysis and that you can slowly expand the functions you can correctly analyse without changing observable behavior.

Thanks for the attention and looking forward to your comments
Espada

[triceo]

Hello @GUIpsp!

You are spot on in that it would be nice to infer the sources, as opposed to having the user specify them. This is indeed a major opportunity for user error. And what you are proposing is indeed possible.

At the same time, I worry that this would replace a relatively easily detectable issue on the user side for a cryptic problem on the solver side, which is hard to reproduce or even notice. (It is "magic" that happens in the background, the user isn't even aware of it.) I am not fundamentally opposed to it, but I don't see us looking into this any time soon.

Considering that this can be added at any point in time in the future, even if the API is already stable, maybe it's an opportunity for a community contribution? PRs are welcome! ;-) The way to do this in a backwards-compatible manner would be to make the sources optional, which won't break anyone who decides to specify them, in which case the feature would be disabled.

[Christopher-Chianelli]

There are several major issues with this proposal:

• In order to determine what variables are used, we need global bytecode information. Consider the classes:

public class Utility {
    public static double calculateArrivalTime(Visit from, Visit to) {
        return from.endTime.plus(from.travelTimeTo(to));
   }
}

@PlanningEntity
public class Visit {
    @PreviousElementShadowVariable
    Visit previous;
    
    @ShadowVariable(supplierName="startTimeSupplier")
    LocalDateTime startTime;

    @ShadowVariable(supplierName="endTimeSupplier")
    LocalDateTime endTime;

    @ShadowSources()
    public LocalDateTime startTimeSupplier() {
        return Utility.calculateArrivalTime(previous, this);
    }

    @ShadowSources()
    public LocalDateTime endTimeSupplier() {
        // ...
    }
}

In this example, startTime depends on previous.endTime, but you cannot discover that from only reading Visit.startTimeSupplier bytecode; you must also read Utility.calculateArrivalTime bytecode (and do inference based on the arguments passed to it).

• Class bytecode is not always available; for instance, classes defined in custom classloaders.
• There is no guarantee that a given Java function always compile to the same bytecode. This mean we cannot not rely on pure pattern matching in order to discover the dependencies. That being said, Java bytecode is relatively stable (unlike CPython). Moreover, the bytecode might not correspond to a Java class (as an example, we currently translate CPython bytecode to Java bytecode, see https://timefold.ai/blog/java-vs-python-speed for details).

It would be nice, but it would involve too much magic IMO, even if we limit it by banning virtual calls/unknown operations.

[GUIpsp]

Hello, thank you both for your replies.

In order to determine what variables are used, we need global bytecode information.

This is correct, if you want to follow calls, you need to analyse call targets. However, I see no issue with this. I would rather the analyser do it then my own (buggy and faulty) head. The analysis is still relatively composable.

Class bytecode is not always available; for instance, classes defined in custom classloaders.

For trickier cases, as far as I am aware, there is no way to load classes while bypassing the instrumentation API. For the normal case, the class files are findable as a resource.

Then there is Graal. As far as I understand it, there is already some compile-time generation happening for gizmo on graal, so I assume this would not be a problem.

There is no guarantee that a given Java function always compile to the same bytecode.

Yeah, I am aware of this. However, pattern matching seems to me like it would be superfluous. We don't really need to recover structured control flow, and indeed, I think this would be flaky.

However, the types of dependencies allowed by the declarative shadow variables (and thus, that we have to "recover") are compact. For example, we don't need to recover the exact conditional structure of the program - if there is a path to an access, it must be a dependency. We don't need to recover the structure of a for-each over an array, as we only care that it is accessed (aaload), not which accesses actually happen.

I am conscious of the fact that there must always be an escape hatch (the halting problem rears its head from time to time). I think this analysis should always be correct but will never be able to be complete. But if it prevents me from making a mistake 70% of the time, it's a good feature!

Espada