#4169

Committed 14 Nov 2024 02:51PM UTC coverage: 61.2% (+0.02%) from 61.184%

Build # #4169

Build Type

push

github

Committed by

adangel

Commit Message

[java] Fix inference dependency issue with nested lambdas (#5325)

Merge pull request #5325 from oowekyala:typeres-fix-inference-issue

Run Details

17440 of 28027 branches covered (62.23%)

Branch coverage included in aggregate %.

54 of 81 new or added lines in 5 files covered. (66.67%)

2 existing lines in 1 file now uncovered.

39235 of 64579 relevant lines covered (60.76%)

0.61 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

90.88

/pmd-java/src/main/java/net/sourceforge/pmd/lang/java/types/internal/infer/InferenceContext.java

/*
 * BSD-style license; for more info see http://pmd.sourceforge.net/license.html
 */

package net.sourceforge.pmd.lang.java.types.internal.infer;


import static net.sourceforge.pmd.lang.java.types.TypeOps.asList;
import static net.sourceforge.pmd.util.CollectionUtil.intersect;

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.function.Supplier;

import org.checkerframework.checker.nullness.qual.NonNull;
import org.checkerframework.checker.nullness.qual.Nullable;

import net.sourceforge.pmd.lang.java.types.JClassType;
import net.sourceforge.pmd.lang.java.types.JMethodSig;
import net.sourceforge.pmd.lang.java.types.JTypeMirror;
import net.sourceforge.pmd.lang.java.types.JTypeVar;
import net.sourceforge.pmd.lang.java.types.JTypeVisitable;
import net.sourceforge.pmd.lang.java.types.SubstVar;
import net.sourceforge.pmd.lang.java.types.Substitution;
import net.sourceforge.pmd.lang.java.types.TypeOps;
import net.sourceforge.pmd.lang.java.types.TypeSystem;
import net.sourceforge.pmd.lang.java.types.internal.infer.ExprMirror.InvocationMirror.MethodCtDecl;
import net.sourceforge.pmd.lang.java.types.internal.infer.IncorporationAction.CheckBound;
import net.sourceforge.pmd.lang.java.types.internal.infer.IncorporationAction.PropagateAllBounds;
import net.sourceforge.pmd.lang.java.types.internal.infer.IncorporationAction.PropagateBounds;
import net.sourceforge.pmd.lang.java.types.internal.infer.IncorporationAction.SubstituteInst;
import net.sourceforge.pmd.lang.java.types.internal.infer.InferenceVar.BoundKind;
import net.sourceforge.pmd.lang.java.types.internal.infer.VarWalkStrategy.GraphWalk;
import net.sourceforge.pmd.util.CollectionUtil;

/**
 * Context of a type inference process. This object maintains a set of
 * unique inference variables. Inference variables maintain the set of
 * bounds that apply to them.
 */
final class InferenceContext {

    // ivar/ctx ids are globally unique, & repeatable in debug output if you do exactly the same run
    private static int varId = 0;
    private static int ctxId = 0;

    private final Map<InstantiationListener, Set<InferenceVar>> instantiationListeners = new HashMap<>();
    // explicit dependencies between variables for graph building
    private final Map<InferenceVar, Set<InferenceVar>> instantiationConstraints = new HashMap<>();
    // This flag is set to true when the explicit dependencies are changed,
    // or when this context adopted new ivars. This means we should interrupt
    // resolution and recompute the dependency graph between ivars, because
    // the new variables may have dependencies on existing variables, and vice versa.
    private boolean graphWasChanged = false;

    private final Set<InferenceVar> freeVars = new LinkedHashSet<>();
    private final Set<InferenceVar> inferenceVars = new LinkedHashSet<>();
    private final Deque<IncorporationAction> incorporationActions = new ArrayDeque<>();
    final TypeSystem ts;
    private final SupertypeCheckCache supertypeCheckCache;
    final TypeInferenceLogger logger;

    private Substitution mapping = Substitution.EMPTY;
    private @Nullable InferenceContext parent;
    private boolean needsUncheckedConversion;
    private final int id;

    /**
     * Create an inference context from a set of type variables to instantiate.
     * This creates inference vars and adds the initial bounds as described in
     *
     * https://docs.oracle.com/javase/specs/jls/se9/html/jls-18.html#jls-18.1.3
     *
     * under the purple rectangle.
     *
     * @param ts                  The global type system
     * @param supertypeCheckCache Super type check cache, shared by all
     *                            inference runs in the same compilation unit
     *                            (stored in {@link Infer}).
     * @param tvars               Initial tvars which will be turned
     *                            into ivars
     * @param logger              Logger for events related to ivar bounds
     */
    InferenceContext(TypeSystem ts, SupertypeCheckCache supertypeCheckCache, List<JTypeVar> tvars, TypeInferenceLogger logger) {
        this(ts, supertypeCheckCache, tvars, logger, true);
    }

    /**
     * Create an inference context from a set of type variables to instantiate.
     * This creates inference vars and may add the initial bounds as described in
     *
     * https://docs.oracle.com/javase/specs/jls/se9/html/jls-18.html#jls-18.1.3
     *
     * under the purple rectangle.
     *
     * @param ts                  The global type system
     * @param supertypeCheckCache Super type check cache, shared by all
     *                            inference runs in the same compilation unit
     *                            (stored in {@link Infer}).
     * @param tvars               Initial tvars which will be turned
     *                            into ivars
     * @param logger              Logger for events related to ivar bounds
     * @param addPrimaryBound     Whether to add the primary bound of the vars.
     */
    @SuppressWarnings("PMD.AssignmentToNonFinalStatic") // ctxId
    InferenceContext(TypeSystem ts, SupertypeCheckCache supertypeCheckCache, List<JTypeVar> tvars, TypeInferenceLogger logger, boolean addPrimaryBound) {
        this.ts = ts;
        this.supertypeCheckCache = supertypeCheckCache;
        this.logger = logger;
        this.id = ctxId++;

        for (JTypeVar p : tvars) {
            addVarImpl(p);
        }

        if (addPrimaryBound) {
            addPrimaryBounds();
        }
    }

    /**
     * Add the primary bounds for the ivars of this context. This is usually done upon construction but may be deferred
     * in some scenarios (inference of ground target type of an explicitly typed lambda).
     */
    void addPrimaryBounds() {
        for (InferenceVar ivar : inferenceVars) {
            addPrimaryBound(ivar);
        }
    }

    /**
     * Performs a shallow copy of this context, which would allow solving
     * the variables without executing listeners. Instantiation listeners
     * are not copied, and parent contexts are not copied.
     */
    public InferenceContext shallowCopy() {
        final InferenceContext copy = new InferenceContext(ts, supertypeCheckCache, Collections.emptyList(), logger);
        copy.freeVars.addAll(this.freeVars);
        copy.inferenceVars.addAll(this.inferenceVars);
        copy.incorporationActions.addAll(this.incorporationActions);
        copy.instantiationConstraints.putAll(this.instantiationConstraints);
        copy.mapping = mapping; // mapping is immutable, so we can share it safely

        return copy;
    }

    public int getId() {
        return id;
    }

    private void addPrimaryBound(InferenceVar ivar) {
        for (JTypeMirror ui : asList(ivar.getBaseVar().getUpperBound())) {
            ivar.addPrimaryBound(BoundKind.UPPER, mapToIVars(ui));
        }
    }

    /**
     * Add a variable to this context.
     */
    InferenceVar addVar(JTypeVar tvar) {
        InferenceVar ivar = addVarImpl(tvar);
        addPrimaryBound(ivar);

        for (InferenceVar otherIvar : inferenceVars) {
            // remove remaining occurrences of type params
            otherIvar.substBounds(this::mapToIVars);
        }
        return ivar;
    }

    /**
     * Add a variable to this context.
     */
    private InferenceVar addVarImpl(@NonNull JTypeVar tvar) {
        InferenceVar ivar = new InferenceVar(this, tvar, varId++);
        freeVars.add(ivar);
        inferenceVars.add(ivar);
        mapping = mapping.plus(tvar, ivar);
        return ivar;
    }

    /**
     * Replace all type variables in the given type with corresponding
     * inference vars.
     */
    JTypeMirror mapToIVars(JTypeMirror t) {
        return TypeOps.subst(t, mapping);
    }

    /**
     * Replace all type variables in the given type with corresponding
     * inference vars.
     */
    JMethodSig mapToIVars(JMethodSig t) {
        return t.subst(mapping);
    }

    /**
     * Returns true if the type mentions no free inference variables.
     * This is what the JLS calls a "proper type".
     */
    boolean isGround(JTypeVisitable t) {
        return !TypeOps.mentionsAny(t, freeVars);
    }

    /**
     * Returns true if the type mentions no free inference variables.
     */
    boolean areAllGround(Collection<? extends JTypeVisitable> ts) {
        for (JTypeVisitable t : ts) {
            if (!isGround(t)) {
                return false;
            }
        }
        return true;
    }

    Set<InferenceVar> freeVarsIn(Iterable<? extends JTypeVisitable> types) {
        Set<InferenceVar> vars = new LinkedHashSet<>();
        for (InferenceVar ivar : freeVars) {
            for (JTypeVisitable t : types) {
                if (TypeOps.mentions(t, ivar)) {
                    vars.add(ivar);
                }
            }
        }
        return vars;
    }

    Set<InferenceVar> freeVarsIn(JTypeVisitable t) {
        return freeVarsIn(Collections.singleton(t));
    }

    /**
     * Replace instantiated inference vars with their instantiation in the given type.
     */
    JTypeMirror ground(JTypeMirror t) {
        return t.subst(InferenceContext::groundSubst);
    }

    JClassType ground(JClassType t) {
        return t.subst(InferenceContext::groundSubst);
    }

    /**
     * Replace instantiated inference vars with their instantiation in the given type.
     */
    JMethodSig ground(JMethodSig t) {
        return t.subst(InferenceContext::groundSubst);
    }

    void setNeedsUncheckedConversion() {
        this.needsUncheckedConversion = true;
    }

    /**
     * Whether incorporation/solving required an unchecked conversion.
     * This means the invocation type of the overload must be erased.
     *
     * @see MethodCtDecl#needsUncheckedConversion()
     */
    boolean needsUncheckedConversion() {
        return this.needsUncheckedConversion;
    }

    SupertypeCheckCache getSupertypeCheckCache() {
        return supertypeCheckCache;
    }

    private static JTypeMirror groundSubst(SubstVar var) {
        if (var instanceof InferenceVar) {
            JTypeMirror inst = ((InferenceVar) var).getInst();
            if (inst != null) {
                return inst;
            }
        }
        return var;
    }

    /**
     * Replace instantiated inference vars with their instantiation in the given type,
     * or else replace them with a failed type.
     */
    static JMethodSig finalGround(JMethodSig t) {
        return t.subst(s -> {
            if (!(s instanceof InferenceVar)) {
                return s;
            } else {
                InferenceVar ivar = (InferenceVar) s;
                return ivar.getInst() != null ? ivar.getInst() : s.getTypeSystem().ERROR;
            }
        });
    }


    /**
     * Replace instantiated inference vars with their instantiation in the given type,
     * or else replace them with a wildcard.
     */
    static JTypeMirror groundOrWildcard(JTypeMirror t) {
        return t.subst(s -> {
            if (!(s instanceof InferenceVar)) {
                return s;
            } else {
                InferenceVar ivar = (InferenceVar) s;
                return ivar.getInst() != null ? ivar.getInst() : s.getTypeSystem().UNBOUNDED_WILD;
            }
        });
    }

    /**
     * Copy variable in this inference context to the given context
     */
    void duplicateInto(final InferenceContext that) {
        boolean changedGraph = !that.freeVars.containsAll(this.freeVars)
            || !this.instantiationConstraints.isEmpty();
        that.graphWasChanged |= changedGraph;
        that.inferenceVars.addAll(this.inferenceVars);
        that.freeVars.addAll(this.freeVars);
        that.incorporationActions.addAll(this.incorporationActions);
        that.instantiationListeners.putAll(this.instantiationListeners);
        CollectionUtil.mergeMaps(
            that.instantiationConstraints,
            this.instantiationConstraints,
            (set1, set2) -> {
                set1.addAll(set2);
                return set1;
            });

        this.parent = that;

        // propagate existing bounds into the new context
        for (InferenceVar freeVar : this.freeVars) {
            that.incorporationActions.add(new PropagateAllBounds(freeVar));
        }
    }


    // The `from` ivars depend on the `dependencies` ivars for resolution.
    void addInstantiationDependencies(Set<? extends InferenceVar> from, Set<? extends InferenceVar> dependencies) {
        if (from.isEmpty()) {
            return;
        }
        Set<InferenceVar> outputVars = new HashSet<>(dependencies);
        outputVars.removeAll(from);
        if (outputVars.isEmpty()) {
            return;
        }
        for (InferenceVar inputVar : from) {
            logger.ivarDependencyRegistered(this, inputVar, outputVars);
            instantiationConstraints.merge(inputVar, outputVars, (o1, o2) -> {
                o2 = new LinkedHashSet<>(o2);
                o2.addAll(o1);
                return o2;
            });
        }
    }

    Map<InferenceVar, Set<InferenceVar>> getInstantiationDependencies() {
        return instantiationConstraints;
    }

    void addInstantiationListener(Set<? extends JTypeMirror> relevantTypes, InstantiationListener listener) {
        Set<InferenceVar> free = freeVarsIn(relevantTypes);
        if (free.isEmpty()) {
            listener.onInstantiation(this);
            return;
        }
        instantiationListeners.put(listener, free);
    }

    /**
     * Call the listeners registered with {@link #addInstantiationListener(Set, InstantiationListener)}.
     * Listeners are used to perform deferred checks, like checking
     * compatibility of a formal parameter with an expression when the
     * formal parameter is not ground.
     */
    void callListeners() {
        if (instantiationListeners.isEmpty()) {
            return;
        }
        Set<InferenceVar> solved = new LinkedHashSet<>(inferenceVars);
        solved.removeAll(freeVars);


        for (Entry<InstantiationListener, Set<InferenceVar>> entry : new LinkedHashSet<>(instantiationListeners.entrySet())) {
            if (solved.containsAll(entry.getValue())) {
                try {
                    entry.getKey().onInstantiation(this);
                } catch (ResolutionFailedException ignored) {
                    // that is a compile-time error, but that
                    // shouldn't affect PMD

                    // This can happen eg when an assertion fails in a
                    // subcontext that depends on this one, which is waiting
                    // for more inference to happen

                    // TODO investigate
                } catch (Exception e) {
                    e.printStackTrace();
                } finally {
                    instantiationListeners.remove(entry.getKey());
                }
            }
        }
    }

    Set<InferenceVar> getFreeVars() {
        return Collections.unmodifiableSet(freeVars);
    }

    private void onVarInstantiated(InferenceVar ivar) {
        if (parent != null) {
            parent.onVarInstantiated(ivar);
            return;
        }

        logger.ivarInstantiated(this, ivar, ivar.getInst());

        incorporationActions.addFirst(new SubstituteInst(ivar, ivar.getInst()) {
            @Override
            public void apply(InferenceContext ctx) {
                freeVars.removeIf(it -> it.getInst() != null);
                super.apply(ctx);
            }
        });
    }


    void onBoundAdded(InferenceVar ivar, BoundKind kind, JTypeMirror bound, boolean isPrimary) {
        // guard against α <: Object
        // all variables have it, it's useless to propagate it
        if (kind != BoundKind.UPPER || bound != ts.OBJECT) { // NOPMD CompareObjectsWithEquals
            if (parent != null) {
                parent.onBoundAdded(ivar, kind, bound, isPrimary);
                return;
            }

            logger.boundAdded(this, ivar, kind, bound, isPrimary);

            incorporationActions.add(new CheckBound(ivar, kind, bound));
            incorporationActions.add(new PropagateBounds(ivar, kind, bound));
        }
    }

    void onIvarMerged(InferenceVar prev, InferenceVar delegate) {
        if (parent != null) {
            parent.onIvarMerged(prev, delegate);
            return;
        }

        logger.ivarMerged(this, prev, delegate);

        mapping = mapping.plus(prev.getBaseVar(), delegate);
        incorporationActions.addFirst(new SubstituteInst(prev, delegate));
    }

    /**
     * Runs the incorporation hooks registered for the free vars.
     *
     * @throws ResolutionFailedException If some propagated bounds are incompatible
     */
    void incorporate() {
        if (incorporationActions.isEmpty()) {
            return;
        }

        IncorporationAction hook = incorporationActions.pollFirst();
        while (hook != null) {

            if (hook.doApplyToInstVar || hook.ivar.getInst() == null) {
                hook.apply(this);
            }

            hook = incorporationActions.pollFirst();
        }
    }

    /**
     * @throws ResolutionFailedException Because it calls {@link #incorporate()}
     */
    void solve() {
        solve(false);
    }

    boolean solve(boolean onlyBoundedVars) {
        return solve(() -> new GraphWalk(this, onlyBoundedVars));
    }

    /**
     * Solve a single var, this does not solve its dependencies, so that
     * if some bounds are not ground, instantiation will be wrong.
     */
    void solve(InferenceVar var) {
        solve(new GraphWalk(var));
    }


    private boolean solve(Supplier<VarWalkStrategy> newWalker) {
        VarWalkStrategy strategy = newWalker.get();
        while (strategy != null) {
            if (solve(strategy)) {
                break;
            }
            strategy = newWalker.get();
        }
        return freeVars.isEmpty();
    }


    /**
     * This returns true if solving the VarWalkStrategy succeeded entirely.
     * Resolution can be interrupted early to account for new ivars and dependencies,
     * which may change the graph dependencies. In this case this method returns
     * false, we recompute the graph with the new ivars and dependencies, and
     * we try again to make progress.
     */
    private boolean solve(VarWalkStrategy walker) {
        incorporate();

        while (walker.hasNext()) {

            Set<InferenceVar> varsToSolve = walker.next();

            boolean progress = true;
            //repeat until all variables are solved
            outer:
            while (!intersect(freeVars, varsToSolve).isEmpty() && progress) {
                if (graphWasChanged) {
                    graphWasChanged = false;
                    logger.contextDependenciesChanged(this);
                    return false;
                }

                progress = false;
                for (List<ReductionStep> wave : ReductionStep.WAVES) {
                    if (solveBatchProgressed(varsToSolve, wave)) {
                        incorporate();
                        progress = true;
                        callListeners();
                        continue outer;
                    }
                }
            }
        }
        return true;
    }

    /**
     * Tries to solve as much of varsToSolve as possible using some reduction steps.
     * Returns the set of solved variables during this step.
     */
    private boolean solveBatchProgressed(Set<InferenceVar> varsToSolve, List<ReductionStep> wave) {
        for (InferenceVar ivar : intersect(varsToSolve, freeVars)) {
            for (ReductionStep step : wave) {
                if (step.accepts(ivar, this)) {
                    ivar.setInst(step.solve(ivar, this));
                    onVarInstantiated(ivar);
                    return true;
                }
            }
        }

        return false;
    }

    public boolean isEmpty() {
        return inferenceVars.isEmpty();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("Inference context " + getId()).append('\n');
        for (InferenceVar ivar : inferenceVars) {
            sb.append(ivar);
            if (ivar.getInst() != null) {
                sb.append(" := ").append(ivar.getInst()).append('\n');
            } else {
                ivar.formatBounds(sb).append('\n');
            }
        }

        return sb.toString();
    }

    /** A callback called when a set of variables have been solved. */
    public interface InstantiationListener {

        /**
         * Called when the set of dependencies provided to {@link #addInstantiationListener(Set, InstantiationListener)}
         * have been solved. The parameter is not necessarily the context
         * on which this has been registered, because contexts adopt the
         * inference variables of their children in some cases, to solve
         * them together. Use {@link #ground(JClassType)} with the context
         * parameter, not the context on which the callback was registered.
         */
        void onInstantiation(InferenceContext solvedCtx);

    }
}

1	/*
2	* BSD-style license; for more info see http://pmd.sourceforge.net/license.html
3	*/
4
5	package net.sourceforge.pmd.lang.java.types.internal.infer;
6
7
8	import static net.sourceforge.pmd.lang.java.types.TypeOps.asList;
9	import static net.sourceforge.pmd.util.CollectionUtil.intersect;
10
11	import java.util.ArrayDeque;
12	import java.util.Collection;
13	import java.util.Collections;
14	import java.util.Deque;
15	import java.util.HashMap;
16	import java.util.HashSet;
17	import java.util.LinkedHashSet;
18	import java.util.List;
19	import java.util.Map;
20	import java.util.Map.Entry;
21	import java.util.Set;
22	import java.util.function.Supplier;
23
24	import org.checkerframework.checker.nullness.qual.NonNull;
25	import org.checkerframework.checker.nullness.qual.Nullable;
26
27	import net.sourceforge.pmd.lang.java.types.JClassType;
28	import net.sourceforge.pmd.lang.java.types.JMethodSig;
29	import net.sourceforge.pmd.lang.java.types.JTypeMirror;
30	import net.sourceforge.pmd.lang.java.types.JTypeVar;
31	import net.sourceforge.pmd.lang.java.types.JTypeVisitable;
32	import net.sourceforge.pmd.lang.java.types.SubstVar;
33	import net.sourceforge.pmd.lang.java.types.Substitution;
34	import net.sourceforge.pmd.lang.java.types.TypeOps;
35	import net.sourceforge.pmd.lang.java.types.TypeSystem;
36	import net.sourceforge.pmd.lang.java.types.internal.infer.ExprMirror.InvocationMirror.MethodCtDecl;
37	import net.sourceforge.pmd.lang.java.types.internal.infer.IncorporationAction.CheckBound;
38	import net.sourceforge.pmd.lang.java.types.internal.infer.IncorporationAction.PropagateAllBounds;
39	import net.sourceforge.pmd.lang.java.types.internal.infer.IncorporationAction.PropagateBounds;
40	import net.sourceforge.pmd.lang.java.types.internal.infer.IncorporationAction.SubstituteInst;
41	import net.sourceforge.pmd.lang.java.types.internal.infer.InferenceVar.BoundKind;
42	import net.sourceforge.pmd.lang.java.types.internal.infer.VarWalkStrategy.GraphWalk;
43	import net.sourceforge.pmd.util.CollectionUtil;
44
45	/**
46	* Context of a type inference process. This object maintains a set of
47	* unique inference variables. Inference variables maintain the set of
48	* bounds that apply to them.
49	*/
50	final class InferenceContext {
51
52	// ivar/ctx ids are globally unique, & repeatable in debug output if you do exactly the same run
53	private static int varId = 0;	1✔
54	private static int ctxId = 0;	1✔
55
56	private final Map<InstantiationListener, Set<InferenceVar>> instantiationListeners = new HashMap<>();	1✔
57	// explicit dependencies between variables for graph building
58	private final Map<InferenceVar, Set<InferenceVar>> instantiationConstraints = new HashMap<>();	1✔
59	// This flag is set to true when the explicit dependencies are changed,
60	// or when this context adopted new ivars. This means we should interrupt
61	// resolution and recompute the dependency graph between ivars, because
62	// the new variables may have dependencies on existing variables, and vice versa.
63	private boolean graphWasChanged = false;	1✔
64
65	private final Set<InferenceVar> freeVars = new LinkedHashSet<>();	1✔
66	private final Set<InferenceVar> inferenceVars = new LinkedHashSet<>();	1✔
67	private final Deque<IncorporationAction> incorporationActions = new ArrayDeque<>();	1✔
68	final TypeSystem ts;
69	private final SupertypeCheckCache supertypeCheckCache;
70	final TypeInferenceLogger logger;
71
72	private Substitution mapping = Substitution.EMPTY;	1✔
73	private @Nullable InferenceContext parent;
74	private boolean needsUncheckedConversion;
75	private final int id;
76
77	/**
78	* Create an inference context from a set of type variables to instantiate.
79	* This creates inference vars and adds the initial bounds as described in
80	*
81	* https://docs.oracle.com/javase/specs/jls/se9/html/jls-18.html#jls-18.1.3
82	*
83	* under the purple rectangle.
84	*
85	* @param ts The global type system
86	* @param supertypeCheckCache Super type check cache, shared by all
87	* inference runs in the same compilation unit
88	* (stored in {@link Infer}).
89	* @param tvars Initial tvars which will be turned
90	* into ivars
91	* @param logger Logger for events related to ivar bounds
92	*/
93	InferenceContext(TypeSystem ts, SupertypeCheckCache supertypeCheckCache, List<JTypeVar> tvars, TypeInferenceLogger logger) {
94	this(ts, supertypeCheckCache, tvars, logger, true);	1✔
95	}	1✔
96
97	/**
98	* Create an inference context from a set of type variables to instantiate.
99	* This creates inference vars and may add the initial bounds as described in
100	*
101	* https://docs.oracle.com/javase/specs/jls/se9/html/jls-18.html#jls-18.1.3
102	*
103	* under the purple rectangle.
104	*
105	* @param ts The global type system
106	* @param supertypeCheckCache Super type check cache, shared by all
107	* inference runs in the same compilation unit
108	* (stored in {@link Infer}).
109	* @param tvars Initial tvars which will be turned
110	* into ivars
111	* @param logger Logger for events related to ivar bounds
112	* @param addPrimaryBound Whether to add the primary bound of the vars.
113	*/
114	@SuppressWarnings("PMD.AssignmentToNonFinalStatic") // ctxId
115	InferenceContext(TypeSystem ts, SupertypeCheckCache supertypeCheckCache, List<JTypeVar> tvars, TypeInferenceLogger logger, boolean addPrimaryBound) {	1✔
116	this.ts = ts;	1✔
117	this.supertypeCheckCache = supertypeCheckCache;	1✔
118	this.logger = logger;	1✔
119	this.id = ctxId++;	1✔
120
121	for (JTypeVar p : tvars) {	1✔
122	addVarImpl(p);	1✔
123	}	1✔
124
125	if (addPrimaryBound) {	1✔
126	addPrimaryBounds();	1✔
127	}
128	}	1✔
129
130	/**
131	* Add the primary bounds for the ivars of this context. This is usually done upon construction but may be deferred
132	* in some scenarios (inference of ground target type of an explicitly typed lambda).
133	*/
134	void addPrimaryBounds() {
135	for (InferenceVar ivar : inferenceVars) {	1✔
136	addPrimaryBound(ivar);	1✔
137	}	1✔
138	}	1✔
139
140	/**
141	* Performs a shallow copy of this context, which would allow solving
142	* the variables without executing listeners. Instantiation listeners
143	* are not copied, and parent contexts are not copied.
144	*/
145	public InferenceContext shallowCopy() {
146	final InferenceContext copy = new InferenceContext(ts, supertypeCheckCache, Collections.emptyList(), logger);	1✔
147	copy.freeVars.addAll(this.freeVars);	1✔
148	copy.inferenceVars.addAll(this.inferenceVars);	1✔
149	copy.incorporationActions.addAll(this.incorporationActions);	1✔
150	copy.instantiationConstraints.putAll(this.instantiationConstraints);	1✔
151	copy.mapping = mapping; // mapping is immutable, so we can share it safely	1✔
152
153	return copy;	1✔
154	}
155
156	public int getId() {
157	return id;	×
158	}
159
160	private void addPrimaryBound(InferenceVar ivar) {
161	for (JTypeMirror ui : asList(ivar.getBaseVar().getUpperBound())) {	1✔
162	ivar.addPrimaryBound(BoundKind.UPPER, mapToIVars(ui));	1✔
163	}	1✔
164	}	1✔
165
166	/**
167	* Add a variable to this context.
168	*/
169	InferenceVar addVar(JTypeVar tvar) {
170	InferenceVar ivar = addVarImpl(tvar);	1✔
171	addPrimaryBound(ivar);	1✔
172
173	for (InferenceVar otherIvar : inferenceVars) {	1✔
174	// remove remaining occurrences of type params
175	otherIvar.substBounds(this::mapToIVars);	1✔
176	}	1✔
177	return ivar;	1✔
178	}
179
180	/**
181	* Add a variable to this context.
182	*/
183	private InferenceVar addVarImpl(@NonNull JTypeVar tvar) {
184	InferenceVar ivar = new InferenceVar(this, tvar, varId++);	1✔
185	freeVars.add(ivar);	1✔
186	inferenceVars.add(ivar);	1✔
187	mapping = mapping.plus(tvar, ivar);	1✔
188	return ivar;	1✔
189	}
190
191	/**
192	* Replace all type variables in the given type with corresponding
193	* inference vars.
194	*/
195	JTypeMirror mapToIVars(JTypeMirror t) {
196	return TypeOps.subst(t, mapping);	1✔
197	}
198
199	/**
200	* Replace all type variables in the given type with corresponding
201	* inference vars.
202	*/
203	JMethodSig mapToIVars(JMethodSig t) {
204	return t.subst(mapping);	1✔
205	}
206
207	/**
208	* Returns true if the type mentions no free inference variables.
209	* This is what the JLS calls a "proper type".
210	*/
211	boolean isGround(JTypeVisitable t) {
212	return !TypeOps.mentionsAny(t, freeVars);	1✔
213	}
214
215	/**
216	* Returns true if the type mentions no free inference variables.
217	*/
218	boolean areAllGround(Collection<? extends JTypeVisitable> ts) {
219	for (JTypeVisitable t : ts) {	1✔
220	if (!isGround(t)) {	1✔
221	return false;	1✔
222	}
223	}	1✔
224	return true;	1✔
225	}
226
227	Set<InferenceVar> freeVarsIn(Iterable<? extends JTypeVisitable> types) {
228	Set<InferenceVar> vars = new LinkedHashSet<>();	1✔
229	for (InferenceVar ivar : freeVars) {	1✔
230	for (JTypeVisitable t : types) {	1✔
231	if (TypeOps.mentions(t, ivar)) {	1✔
232	vars.add(ivar);	1✔
233	}
234	}	1✔
235	}	1✔
236	return vars;	1✔
237	}
238
239	Set<InferenceVar> freeVarsIn(JTypeVisitable t) {
240	return freeVarsIn(Collections.singleton(t));	1✔
241	}
242
243	/**
244	* Replace instantiated inference vars with their instantiation in the given type.
245	*/
246	JTypeMirror ground(JTypeMirror t) {
247	return t.subst(InferenceContext::groundSubst);	1✔
248	}
249
250	JClassType ground(JClassType t) {
251	return t.subst(InferenceContext::groundSubst);	1✔
252	}
253
254	/**
255	* Replace instantiated inference vars with their instantiation in the given type.
256	*/
257	JMethodSig ground(JMethodSig t) {
258	return t.subst(InferenceContext::groundSubst);	1✔
259	}
260
261	void setNeedsUncheckedConversion() {
262	this.needsUncheckedConversion = true;	1✔
263	}	1✔
264
265	/**
266	* Whether incorporation/solving required an unchecked conversion.
267	* This means the invocation type of the overload must be erased.
268	*
269	* @see MethodCtDecl#needsUncheckedConversion()
270	*/
271	boolean needsUncheckedConversion() {
272	return this.needsUncheckedConversion;	1✔
273	}
274
275	SupertypeCheckCache getSupertypeCheckCache() {
276	return supertypeCheckCache;	1✔
277	}
278
279	private static JTypeMirror groundSubst(SubstVar var) {
280	if (var instanceof InferenceVar) {	1✔
281	JTypeMirror inst = ((InferenceVar) var).getInst();	1✔
282	if (inst != null) {	1✔
283	return inst;	1✔
284	}
285	}
286	return var;	1✔
287	}
288
289	/**
290	* Replace instantiated inference vars with their instantiation in the given type,
291	* or else replace them with a failed type.
292	*/
293	static JMethodSig finalGround(JMethodSig t) {
294	return t.subst(s -> {	1✔
295	if (!(s instanceof InferenceVar)) {	1✔
296	return s;	1✔
297	} else {
298	InferenceVar ivar = (InferenceVar) s;	1✔
299	return ivar.getInst() != null ? ivar.getInst() : s.getTypeSystem().ERROR;	1!
300	}
301	});
302	}
303
304
305	/**
306	* Replace instantiated inference vars with their instantiation in the given type,
307	* or else replace them with a wildcard.
308	*/
309	static JTypeMirror groundOrWildcard(JTypeMirror t) {
310	return t.subst(s -> {	1✔
311	if (!(s instanceof InferenceVar)) {	1!
312	return s;	×
313	} else {
314	InferenceVar ivar = (InferenceVar) s;	1✔
315	return ivar.getInst() != null ? ivar.getInst() : s.getTypeSystem().UNBOUNDED_WILD;	1✔
316	}
317	});
318	}
319
320	/**
321	* Copy variable in this inference context to the given context
322	*/
323	void duplicateInto(final InferenceContext that) {
324	boolean changedGraph = !that.freeVars.containsAll(this.freeVars)	1!
325	\|\| !this.instantiationConstraints.isEmpty();	1!
326	that.graphWasChanged \|= changedGraph;	1✔
327	that.inferenceVars.addAll(this.inferenceVars);	1✔
328	that.freeVars.addAll(this.freeVars);	1✔
329	that.incorporationActions.addAll(this.incorporationActions);	1✔
330	that.instantiationListeners.putAll(this.instantiationListeners);	1✔
331	CollectionUtil.mergeMaps(	1✔
332	that.instantiationConstraints,
333	this.instantiationConstraints,
334	(set1, set2) -> {
NEW 335	set1.addAll(set2);	×
NEW 336	return set1;	×
337	});
338
339	this.parent = that;	1✔
340
341	// propagate existing bounds into the new context
342	for (InferenceVar freeVar : this.freeVars) {	1✔
343	that.incorporationActions.add(new PropagateAllBounds(freeVar));	1✔
344	}	1✔
345	}	1✔
346
347
348	// The `from` ivars depend on the `dependencies` ivars for resolution.
349	void addInstantiationDependencies(Set<? extends InferenceVar> from, Set<? extends InferenceVar> dependencies) {
350	if (from.isEmpty()) {	1✔
351	return;	1✔
352	}
353	Set<InferenceVar> outputVars = new HashSet<>(dependencies);	1✔
354	outputVars.removeAll(from);	1✔
355	if (outputVars.isEmpty()) {	1✔
356	return;	1✔
357	}
358	for (InferenceVar inputVar : from) {	1✔
359	logger.ivarDependencyRegistered(this, inputVar, outputVars);	1✔
360	instantiationConstraints.merge(inputVar, outputVars, (o1, o2) -> {	1✔
361	o2 = new LinkedHashSet<>(o2);	1✔
362	o2.addAll(o1);	1✔
363	return o2;	1✔
364	});
365	}	1✔
366	}	1✔
367
368	Map<InferenceVar, Set<InferenceVar>> getInstantiationDependencies() {
369	return instantiationConstraints;	1✔
370	}
371
372	void addInstantiationListener(Set<? extends JTypeMirror> relevantTypes, InstantiationListener listener) {
373	Set<InferenceVar> free = freeVarsIn(relevantTypes);	1✔
374	if (free.isEmpty()) {	1✔
375	listener.onInstantiation(this);	1✔
376	return;	1✔
377	}
378	instantiationListeners.put(listener, free);	1✔
379	}	1✔
380
381	/**
382	* Call the listeners registered with {@link #addInstantiationListener(Set, InstantiationListener)}.
383	* Listeners are used to perform deferred checks, like checking
384	* compatibility of a formal parameter with an expression when the
385	* formal parameter is not ground.
386	*/
387	void callListeners() {
388	if (instantiationListeners.isEmpty()) {	1✔
389	return;	1✔
390	}
391	Set<InferenceVar> solved = new LinkedHashSet<>(inferenceVars);	1✔
392	solved.removeAll(freeVars);	1✔
393
394
395	for (Entry<InstantiationListener, Set<InferenceVar>> entry : new LinkedHashSet<>(instantiationListeners.entrySet())) {	1✔
396	if (solved.containsAll(entry.getValue())) {	1✔
397	try {
398	entry.getKey().onInstantiation(this);	1✔
399	} catch (ResolutionFailedException ignored) {	1✔
400	// that is a compile-time error, but that
401	// shouldn't affect PMD
402
403	// This can happen eg when an assertion fails in a
404	// subcontext that depends on this one, which is waiting
405	// for more inference to happen
406
407	// TODO investigate
408	} catch (Exception e) {	×
409	e.printStackTrace();	×
410	} finally {
411	instantiationListeners.remove(entry.getKey());	1✔
412	}
413	}
414	}	1✔
415	}	1✔
416
417	Set<InferenceVar> getFreeVars() {
418	return Collections.unmodifiableSet(freeVars);	1✔
419	}
420
421	private void onVarInstantiated(InferenceVar ivar) {
422	if (parent != null) {	1!
423	parent.onVarInstantiated(ivar);	×
424	return;	×
425	}
426
427	logger.ivarInstantiated(this, ivar, ivar.getInst());	1✔
428
429	incorporationActions.addFirst(new SubstituteInst(ivar, ivar.getInst()) {	1✔
430	@Override
431	public void apply(InferenceContext ctx) {
432	freeVars.removeIf(it -> it.getInst() != null);	1✔
433	super.apply(ctx);	1✔
434	}	1✔
435	});
436	}	1✔
437
438
439	void onBoundAdded(InferenceVar ivar, BoundKind kind, JTypeMirror bound, boolean isPrimary) {
440	// guard against α <: Object
441	// all variables have it, it's useless to propagate it
442	if (kind != BoundKind.UPPER \|\| bound != ts.OBJECT) { // NOPMD CompareObjectsWithEquals	1✔
443	if (parent != null) {	1✔
444	parent.onBoundAdded(ivar, kind, bound, isPrimary);	1✔
445	return;	1✔
446	}
447
448	logger.boundAdded(this, ivar, kind, bound, isPrimary);	1✔
449
450	incorporationActions.add(new CheckBound(ivar, kind, bound));	1✔
451	incorporationActions.add(new PropagateBounds(ivar, kind, bound));	1✔
452	}
453	}	1✔
454
455	void onIvarMerged(InferenceVar prev, InferenceVar delegate) {
456	if (parent != null) {	1✔
457	parent.onIvarMerged(prev, delegate);	1✔
458	return;	1✔
459	}
460
461	logger.ivarMerged(this, prev, delegate);	1✔
462
463	mapping = mapping.plus(prev.getBaseVar(), delegate);	1✔
464	incorporationActions.addFirst(new SubstituteInst(prev, delegate));	1✔
465	}	1✔
466
467	/**
468	* Runs the incorporation hooks registered for the free vars.
469	*
470	* @throws ResolutionFailedException If some propagated bounds are incompatible
471	*/
472	void incorporate() {
473	if (incorporationActions.isEmpty()) {	1✔
474	return;	1✔
475	}
476
477	IncorporationAction hook = incorporationActions.pollFirst();	1✔
478	while (hook != null) {	1✔
479
480	if (hook.doApplyToInstVar \|\| hook.ivar.getInst() == null) {	1✔
481	hook.apply(this);	1✔
482	}
483
484	hook = incorporationActions.pollFirst();	1✔
485	}
486	}	1✔
487
488	/**
489	* @throws ResolutionFailedException Because it calls {@link #incorporate()}
490	*/
491	void solve() {
492	solve(false);	1✔
493	}	1✔
494
495	boolean solve(boolean onlyBoundedVars) {
496	return solve(() -> new GraphWalk(this, onlyBoundedVars));	1✔
497	}
498
499	/**
500	* Solve a single var, this does not solve its dependencies, so that
501	* if some bounds are not ground, instantiation will be wrong.
502	*/
503	void solve(InferenceVar var) {
504	solve(new GraphWalk(var));	×
505	}	×
506
507
508	private boolean solve(Supplier<VarWalkStrategy> newWalker) {
509	VarWalkStrategy strategy = newWalker.get();	1✔
510	while (strategy != null) {	1!
511	if (solve(strategy)) {	1✔
512	break;	1✔
513	}
514	strategy = newWalker.get();	1✔
515	}
516	return freeVars.isEmpty();	1✔
517	}
518
519
520	/**
521	* This returns true if solving the VarWalkStrategy succeeded entirely.
522	* Resolution can be interrupted early to account for new ivars and dependencies,
523	* which may change the graph dependencies. In this case this method returns
524	* false, we recompute the graph with the new ivars and dependencies, and
525	* we try again to make progress.
526	*/
527	private boolean solve(VarWalkStrategy walker) {
528	incorporate();	1✔
529
530	while (walker.hasNext()) {	1✔
531
532	Set<InferenceVar> varsToSolve = walker.next();	1✔
533
534	boolean progress = true;	1✔
535	//repeat until all variables are solved
536	outer:
537	while (!intersect(freeVars, varsToSolve).isEmpty() && progress) {	1✔
538	if (graphWasChanged) {	1✔
539	graphWasChanged = false;	1✔
540	logger.contextDependenciesChanged(this);	1✔
541	return false;	1✔
542	}
543
544	progress = false;	1✔
545	for (List<ReductionStep> wave : ReductionStep.WAVES) {	1✔
546	if (solveBatchProgressed(varsToSolve, wave)) {	1✔
547	incorporate();	1✔
548	progress = true;	1✔
549	callListeners();	1✔
550	continue outer;	1✔
551	}
552	}	1✔
553	}
554	}	1✔
555	return true;	1✔
556	}
557
558	/**
559	* Tries to solve as much of varsToSolve as possible using some reduction steps.
560	* Returns the set of solved variables during this step.
561	*/
562	private boolean solveBatchProgressed(Set<InferenceVar> varsToSolve, List<ReductionStep> wave) {
563	for (InferenceVar ivar : intersect(varsToSolve, freeVars)) {	1✔
564	for (ReductionStep step : wave) {	1✔
565	if (step.accepts(ivar, this)) {	1✔
566	ivar.setInst(step.solve(ivar, this));	1✔
567	onVarInstantiated(ivar);	1✔
568	return true;	1✔
569	}
570	}	1✔
571	}	1✔
572
573	return false;	1✔
574	}
575
576	public boolean isEmpty() {
577	return inferenceVars.isEmpty();	1✔
578	}
579
580	@Override
581	public String toString() {
582	StringBuilder sb = new StringBuilder("Inference context " + getId()).append('\n');	×
583	for (InferenceVar ivar : inferenceVars) {	×
584	sb.append(ivar);	×
585	if (ivar.getInst() != null) {	×
586	sb.append(" := ").append(ivar.getInst()).append('\n');	×
587	} else {
588	ivar.formatBounds(sb).append('\n');	×
589	}
590	}	×
591
592	return sb.toString();	×
593	}
594
595	/** A callback called when a set of variables have been solved. */
596	public interface InstantiationListener {
597
598	/**
599	* Called when the set of dependencies provided to {@link #addInstantiationListener(Set, InstantiationListener)}
600	* have been solved. The parameter is not necessarily the context
601	* on which this has been registered, because contexts adopt the
602	* inference variables of their children in some cases, to solve
603	* them together. Use {@link #ground(JClassType)} with the context
604	* parameter, not the context on which the callback was registered.
605	*/
606	void onInstantiation(InferenceContext solvedCtx);
607
608	}
609	}

pmd / pmd / #4169

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous