• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

wurstscript / WurstScript / 220

22 Nov 2023 12:57PM UTC coverage: 62.564% (-0.04%) from 62.602%
220

Pull #1081

circleci

Frotty
Update MapRequest.java
Pull Request #1081: More performance improvements

17307 of 27663 relevant lines covered (62.56%)

0.63 hits per line

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

97.93
de.peeeq.wurstscript/src/main/java/de/peeeq/wurstscript/translation/imtranslation/CyclicFunctionRemover.java
1
package de.peeeq.wurstscript.translation.imtranslation;
2

3
import com.google.common.collect.ImmutableList;
4
import com.google.common.collect.Lists;
5
import com.google.common.collect.Maps;
6
import de.peeeq.datastructures.GraphInterpreter;
7
import de.peeeq.wurstio.TimeTaker;
8
import de.peeeq.wurstscript.WurstOperator;
9
import de.peeeq.wurstscript.jassIm.*;
10
import de.peeeq.wurstscript.types.WurstTypeInt;
11

12
import java.util.*;
13
import java.util.concurrent.atomic.AtomicReference;
14

15
/**
16
 * Removes cyclic functions from a program
17
 * by putting cyclic functions into one big function
18
 */
19
public class CyclicFunctionRemover {
20

21

22
    private ImProg prog;
23
    private TimeTaker timeTaker;
24
    private ImTranslator tr;
25
    private ImFuncGraph graph;
26

27
    public CyclicFunctionRemover(ImTranslator tr, ImProg prog, TimeTaker timeTaker) {
1✔
28
        this.tr = tr;
1✔
29
        this.prog = prog;
1✔
30
        this.timeTaker = timeTaker;
1✔
31
        this.graph = new ImFuncGraph();
1✔
32
    }
1✔
33

34
    public void work() {
35
        tr.calculateCallRelationsAndUsedVariables();
1✔
36
        AtomicReference<Set<Set<ImFunction>>> components = new AtomicReference<>();
1✔
37
        timeTaker.measure("finding cycles", () -> components.set(graph.findStronglyConnectedComponents(prog.getFunctions())));
1✔
38

39
        timeTaker.measure("removing cycles", () -> removeCycles(components));
1✔
40
    }
1✔
41

42
    private void removeCycles(AtomicReference<Set<Set<ImFunction>>> components) {
43
        for (Set<ImFunction> component : components.get()) {
1✔
44
            if (component.size() > 1) {
1✔
45
                removeCycle(ImmutableList.copyOf(component), component);
1✔
46
            }
47
        }
1✔
48
    }
1✔
49

50
    private void removeCycle(List<ImFunction> funcs, Set<ImFunction> funcSet) {
51
        List<ImVar> newParameters = Lists.newArrayList();
1✔
52
        Map<ImVar, ImVar> oldToNewVar = Maps.newLinkedHashMap();
1✔
53

54
        calculateNewParameters(funcs, newParameters, oldToNewVar);
1✔
55

56
        de.peeeq.wurstscript.ast.Element trace = funcs.get(0).getTrace();
1✔
57

58
        ImVar choiceVar = JassIm.ImVar(trace, WurstTypeInt.instance().imTranslateType(tr), "funcChoice", false);
1✔
59

60
        List<FunctionFlag> flags = Lists.newArrayList();
1✔
61

62
        ImFunction newFunc = JassIm.ImFunction(trace, makeName(funcs), JassIm.ImTypeVars(), JassIm.ImVars(), JassIm.ImVoid(), JassIm.ImVars(), JassIm.ImStmts(), flags);
1✔
63
        prog.getFunctions().add(newFunc);
1✔
64
        newFunc.getParameters().add(choiceVar);
1✔
65
        newFunc.getParameters().addAll(newParameters);
1✔
66

67
        ImStmts stmts = newFunc.getBody();
1✔
68

69
        for (int i = 0; i < funcs.size(); i++) {
1✔
70
            ImFunction f = funcs.get(i);
1✔
71
            ImStmts thenBlock = JassIm.ImStmts();
1✔
72

73
            // add body
74
            thenBlock.addAll(f.getBody().removeAll());
1✔
75
            // addLocals
76
            newFunc.getLocals().addAll(f.getLocals().removeAll());
1✔
77

78
            replaceVars(thenBlock, oldToNewVar);
1✔
79

80
            if (!(f.getReturnType() instanceof ImVoid)) {
1✔
81
                replaceReturn(thenBlock, f.getReturnType());
1✔
82
            }
83

84
            ImStmts elseBlock = JassIm.ImStmts();
1✔
85
            stmts.add(JassIm.ImIf(trace,
1✔
86
                    JassIm.ImOperatorCall(WurstOperator.EQ,
1✔
87
                            JassIm.ImExprs(JassIm.ImVarAccess(choiceVar), JassIm.ImIntVal(i))),
1✔
88
                    thenBlock,
89
                    elseBlock));
90
            stmts = elseBlock;
1✔
91
        }
92

93
        Map<ImFunction, Integer> funcToIndex = new HashMap<>();
1✔
94
        for (int i = 0; i < funcs.size(); i++) {
1✔
95
            funcToIndex.put(funcs.get(i), i);
1✔
96
        }
97
        replaceCalls(funcSet, funcToIndex, newFunc, oldToNewVar, prog);
1✔
98

99
        for (ImFunction e : Lists.newArrayList(tr.getCalledFunctions().keys())) {
1✔
100
            Collection<ImFunction> called = tr.getCalledFunctions().get(e);
1✔
101
            called.removeAll(funcs);
1✔
102
        }
1✔
103

104
        // remove the old funcs
105
        prog.getFunctions().removeAll(funcs);
1✔
106
//                System.out.println("----------------------------------");
107
//                System.out.println(prog.toString());
108
//                System.out.println("----------------------------------");
109
    }
1✔
110

111
    private void replaceVars(Element e, Map<ImVar, ImVar> oldToNewVar) {
112
        // process children
113
        for (int i = 0; i < e.size(); i++) {
1✔
114
            replaceVars(e.get(i), oldToNewVar);
1✔
115
        }
116

117
        if (e instanceof ImVarAccess) {
1✔
118
            ImVarAccess va = (ImVarAccess) e;
1✔
119
            ImVar newVar = oldToNewVar.get(va.getVar());
1✔
120
            if (newVar != null) {
1✔
121
                va.setVar(newVar);
1✔
122
            }
123
        }
124
    }
1✔
125

126

127
    private void replaceCalls(Set<ImFunction> funcSet, Map<ImFunction, Integer> funcToIndex, ImFunction newFunc, Map<ImVar, ImVar> oldToNewVar, Element e) {
128
        List<Element> relevant = new ArrayList<>();
1✔
129
        e.accept(new Element.DefaultVisitor() {
1✔
130
            @Override
131
            public void visit(ImFuncRef imFuncRef) {
132
                super.visit(imFuncRef);
1✔
133
                relevant.add(imFuncRef);
1✔
134
            }
1✔
135

136
            @Override
137
            public void visit(ImFunctionCall imFunctionCall) {
138
                super.visit(imFunctionCall);
1✔
139
                relevant.add(imFunctionCall);
1✔
140
            }
1✔
141
        });
142
        relevant.parallelStream().forEach(relevantElem -> {
1✔
143
            if (relevantElem instanceof ImFuncRef) {
1✔
144
                replaceImFuncRef(funcSet, funcToIndex, newFunc, oldToNewVar, (ImFuncRef) relevantElem);
1✔
145
            } else if (relevantElem instanceof ImFunctionCall) {
1✔
146
                replaceImFunctionCall(funcSet, funcToIndex, newFunc, oldToNewVar, (ImFunctionCall) relevantElem);
1✔
147
            }
148
        });
1✔
149
    }
1✔
150

151
    private void replaceImFuncRef(Set<ImFunction> funcSet, Map<ImFunction, Integer> funcToIndex, ImFunction newFunc, Map<ImVar, ImVar> oldToNewVar, ImFuncRef e) {
152
        ImFuncRef fr = e;
1✔
153
        ImFunction f = fr.getFunc();
1✔
154
        if (funcSet.contains(f)) {
1✔
155

156
            ImFunction proxyFunc = JassIm.ImFunction(f.attrTrace(), f.getName() + "_proxy", JassIm.ImTypeVars(), f.getParameters().copy(), (ImType) f.getReturnType().copy(), JassIm.ImVars(), JassIm.ImStmts(), Collections.<FunctionFlag>emptyList());
1✔
157
            prog.getFunctions().add(proxyFunc);
1✔
158

159
            ImExprs arguments = JassIm.ImExprs();
1✔
160
            for (ImVar p : proxyFunc.getParameters()) {
1✔
161
                arguments.add(JassIm.ImVarAccess(p));
×
162
            }
×
163

164
            ImFunctionCall call = JassIm.ImFunctionCall(fr.attrTrace(), f, JassIm.ImTypeArguments(), arguments, true, CallType.NORMAL);
1✔
165

166
            if (f.getReturnType() instanceof ImVoid) {
1✔
167
                proxyFunc.getBody().add(call);
×
168
            } else {
169
                proxyFunc.getBody().add(JassIm.ImReturn(proxyFunc.getTrace(), call));
1✔
170
            }
171
            // rewrite the proxy call:
172
            replaceCalls(funcSet, funcToIndex, newFunc, oldToNewVar, call);
1✔
173
            // change the funcref to use the proxy
174
            fr.setFunc(proxyFunc);
1✔
175
        }
176
    }
1✔
177

178
    private void replaceImFunctionCall(Set<ImFunction> funcSet, Map<ImFunction, Integer> funcToIndex, ImFunction newFunc, Map<ImVar, ImVar> oldToNewVar, ImFunctionCall e) {
179
        ImFunctionCall fc = e;
1✔
180
        ImFunction oldFunc = fc.getFunc();
1✔
181
        if (funcSet.contains(oldFunc)) {
1✔
182

183
            ImExprs arguments = JassIm.ImExprs();
1✔
184

185
            // first argument is the choice index
186
            arguments.add(JassIm.ImIntVal(funcToIndex.get(oldFunc)));
1✔
187

188
            // now for the actual arguments
189
            List<ImExpr> oldArgs = fc.getArguments().removeAll();
1✔
190
            int pos = 0;
1✔
191
            for (int i = 1; i < newFunc.getParameters().size(); i++) {
1✔
192
                ImVar p = newFunc.getParameters().get(i);
1✔
193
                if (pos < oldArgs.size() && oldToNewVar.get(oldFunc.getParameters().get(pos)) == p) {
1✔
194
                    arguments.add(oldArgs.get(pos));
1✔
195
                    pos++;
1✔
196
                } else {
197
                    // use default value
198
                    arguments.add(tr.getDefaultValueForJassType(p.getType()));
1✔
199
                }
200
            }
201

202

203
            ImFunctionCall newCall = JassIm.ImFunctionCall(fc.getTrace(), newFunc, JassIm.ImTypeArguments(), arguments, true, CallType.NORMAL);
1✔
204

205
            Element ret;
206
            if (oldFunc.getReturnType() instanceof ImVoid) {
1✔
207
                ret = newCall;
1✔
208
            } else {
209
                // if there is a return value, use the temporary return value
210
                ret = JassIm.ImStatementExpr(JassIm.ImStmts(newCall), JassIm.ImVarAccess(getTempReturnVar(oldFunc.getReturnType())));
1✔
211
            }
212
            fc.replaceBy(ret);
1✔
213

214
        }
215
    }
1✔
216

217
    private void replaceReturn(Element e, ImType returnType) {
218
        // process children
219
        for (int i = 0; i < e.size(); i++) {
1✔
220
            replaceReturn(e.get(i), returnType);
1✔
221
        }
222

223

224
        if (e instanceof ImReturn) {
1✔
225
            ImReturn r = (ImReturn) e;
1✔
226

227
            ImExprOpt returnValue = r.getReturnValue();
1✔
228
            returnValue.setParent(null);
1✔
229
            ImStmts stmts = JassIm.ImStmts(
1✔
230
                    JassIm.ImSet(r.getTrace(), JassIm.ImVarAccess(getTempReturnVar(returnType)), (ImExpr) returnValue),
1✔
231
                    JassIm.ImReturn(r.getTrace(), JassIm.ImNoExpr())
1✔
232
            );
233
            r.replaceBy(ImHelper.statementExprVoid(stmts));
1✔
234
        }
235

236
    }
1✔
237

238
    private Map<String, ImVar> tempReturnVars = Maps.newLinkedHashMap();
1✔
239

240
    private ImVar getTempReturnVar(ImType t) {
241
        String typeName = t.translateType();
1✔
242
        ImVar r = tempReturnVars.get(typeName);
1✔
243
        if (r == null) {
1✔
244
            r = JassIm.ImVar(t.attrTrace(), t, "tempReturn_" + typeName, false);
1✔
245
            prog.getGlobals().add(r);
1✔
246
            tempReturnVars.put(typeName, r);
1✔
247
        }
248
        return r;
1✔
249
    }
250

251
    private String makeName(List<ImFunction> funcs) {
252
        return "cyc_" + funcs.get(0).getName();
1✔
253
    }
254

255
    private void calculateNewParameters(List<ImFunction> funcs,
256
                                        List<ImVar> newParameters, Map<ImVar, ImVar> oldToNewVar) {
257
        for (ImFunction f : funcs) {
1✔
258
            int pos = 0;
1✔
259
            withNextParameter:
260
            for (ImVar v : f.getParameters()) {
1✔
261
                // first check if we can reuse a parameter from the newParameters
262
                for (int i = pos; i < newParameters.size(); i++) {
1✔
263
                    if (newParameters.get(i).getType().translateType().equals(v.getType().translateType())) {
1✔
264
                        // found a var we can reuse
265
                        oldToNewVar.put(v, newParameters.get(i));
1✔
266
                        pos = i + 1;
1✔
267
                        continue withNextParameter;
1✔
268
                    }
269
                }
270
                // otherwise, we have to create a new var:
271
                ImVar newVar = JassIm.ImVar(v.getTrace(), (ImType) v.getType().copy(), v.getName(), false);
1✔
272
                oldToNewVar.put(v, newVar);
1✔
273
                newParameters.add(newVar);
1✔
274
                pos = newParameters.size() + 1;
1✔
275
            }
1✔
276
        }
1✔
277
    }
1✔
278

279
    class ImFuncGraph extends GraphInterpreter<ImFunction> {
1✔
280

281
        @Override
282
        protected Collection<ImFunction> getIncidentNodes(ImFunction f) {
283
            return tr.getCalledFunctions().get(f);
1✔
284
        }
285

286
    }
287

288

289
}
290

291

STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc