1/*
2 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.  Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26package jdk.nashorn.internal.codegen;
27
28import static jdk.nashorn.internal.runtime.logging.DebugLogger.quote;
29
30import java.util.HashMap;
31import java.util.HashSet;
32import java.util.Iterator;
33import java.util.Map;
34import java.util.Set;
35import jdk.nashorn.internal.ir.Block;
36import jdk.nashorn.internal.ir.FunctionNode;
37import jdk.nashorn.internal.ir.IdentNode;
38import jdk.nashorn.internal.ir.LexicalContext;
39import jdk.nashorn.internal.ir.Node;
40import jdk.nashorn.internal.ir.Symbol;
41import jdk.nashorn.internal.ir.WithNode;
42import jdk.nashorn.internal.ir.visitor.SimpleNodeVisitor;
43import jdk.nashorn.internal.runtime.Context;
44import jdk.nashorn.internal.runtime.RecompilableScriptFunctionData;
45import jdk.nashorn.internal.runtime.logging.DebugLogger;
46import jdk.nashorn.internal.runtime.logging.Loggable;
47import jdk.nashorn.internal.runtime.logging.Logger;
48
49/**
50 * Establishes depth of scope for non local symbols at the start of method.
51 * If this is a recompilation, the previous data from eager compilation is
52 * stored in the RecompilableScriptFunctionData and is transferred to the
53 * FunctionNode being compiled
54 */
55@Logger(name="scopedepths")
56final class FindScopeDepths extends SimpleNodeVisitor implements Loggable {
57
58    private final Compiler compiler;
59    private final Map<Integer, Map<Integer, RecompilableScriptFunctionData>> fnIdToNestedFunctions = new HashMap<>();
60    private final Map<Integer, Map<String, Integer>> externalSymbolDepths = new HashMap<>();
61    private final Map<Integer, Set<String>> internalSymbols = new HashMap<>();
62    private final Set<Block> withBodies = new HashSet<>();
63
64    private final DebugLogger log;
65
66    private int dynamicScopeCount;
67
68    FindScopeDepths(final Compiler compiler) {
69        this.compiler = compiler;
70        this.log      = initLogger(compiler.getContext());
71    }
72
73    @Override
74    public DebugLogger getLogger() {
75        return log;
76    }
77
78    @Override
79    public DebugLogger initLogger(final Context context) {
80        return context.getLogger(this.getClass());
81    }
82
83    static int findScopesToStart(final LexicalContext lc, final FunctionNode fn, final Block block) {
84        final Block bodyBlock = findBodyBlock(lc, fn, block);
85        final Iterator<Block> iter = lc.getBlocks(block);
86        Block b = iter.next();
87        int scopesToStart = 0;
88        while (true) {
89            if (b.needsScope()) {
90                scopesToStart++;
91            }
92            if (b == bodyBlock) {
93                break;
94            }
95            b = iter.next();
96        }
97        return scopesToStart;
98    }
99
100    static int findInternalDepth(final LexicalContext lc, final FunctionNode fn, final Block block, final Symbol symbol) {
101        final Block bodyBlock = findBodyBlock(lc, fn, block);
102        final Iterator<Block> iter = lc.getBlocks(block);
103        Block b = iter.next();
104        int scopesToStart = 0;
105        while (true) {
106            if (definedInBlock(b, symbol)) {
107                return scopesToStart;
108            }
109            if (b.needsScope()) {
110                scopesToStart++;
111            }
112            if (b == bodyBlock) {
113                break; //don't go past body block, but process it
114            }
115            b = iter.next();
116        }
117        return -1;
118    }
119
120    private static boolean definedInBlock(final Block block, final Symbol symbol) {
121        if (symbol.isGlobal()) {
122            //globals cannot be defined anywhere else
123
124            return block.isGlobalScope();
125        }
126        return block.getExistingSymbol(symbol.getName()) == symbol;
127    }
128
129    static Block findBodyBlock(final LexicalContext lc, final FunctionNode fn, final Block block) {
130        final Iterator<Block> iter = lc.getBlocks(block);
131        while (iter.hasNext()) {
132            final Block next = iter.next();
133            if (fn.getBody() == next) {
134                return next;
135            }
136        }
137        return null;
138    }
139
140    private static Block findGlobalBlock(final LexicalContext lc, final Block block) {
141        final Iterator<Block> iter = lc.getBlocks(block);
142        Block globalBlock = null;
143        while (iter.hasNext()) {
144            globalBlock = iter.next();
145        }
146        return globalBlock;
147    }
148
149    private static boolean isDynamicScopeBoundary(final FunctionNode fn) {
150        return fn.needsDynamicScope();
151    }
152
153    private boolean isDynamicScopeBoundary(final Block block) {
154        return withBodies.contains(block);
155    }
156
157    @Override
158    public boolean enterFunctionNode(final FunctionNode functionNode) {
159        if (compiler.isOnDemandCompilation()) {
160            return true;
161        }
162
163        if (isDynamicScopeBoundary(functionNode)) {
164            increaseDynamicScopeCount(functionNode);
165        }
166
167        final int fnId = functionNode.getId();
168        Map<Integer, RecompilableScriptFunctionData> nestedFunctions = fnIdToNestedFunctions.get(fnId);
169        if (nestedFunctions == null) {
170            nestedFunctions = new HashMap<>();
171            fnIdToNestedFunctions.put(fnId, nestedFunctions);
172        }
173
174        return true;
175    }
176
177    //external symbols hold the scope depth of sc11 from global at the start of the method
178    @Override
179    public Node leaveFunctionNode(final FunctionNode functionNode) {
180        final String name = functionNode.getName();
181        FunctionNode newFunctionNode = functionNode;
182        if (compiler.isOnDemandCompilation()) {
183            final RecompilableScriptFunctionData data = compiler.getScriptFunctionData(newFunctionNode.getId());
184            if (data.inDynamicContext()) {
185                log.fine("Reviving scriptfunction ", quote(name), " as defined in previous (now lost) dynamic scope.");
186                newFunctionNode = newFunctionNode.setInDynamicContext(lc);
187            }
188            if (newFunctionNode == lc.getOutermostFunction() && !newFunctionNode.hasApplyToCallSpecialization()) {
189                data.setCachedAst(newFunctionNode);
190            }
191            return newFunctionNode;
192        }
193
194        if (inDynamicScope()) {
195            log.fine("Tagging ", quote(name), " as defined in dynamic scope");
196            newFunctionNode = newFunctionNode.setInDynamicContext(lc);
197        }
198
199        //create recompilable scriptfunctiondata
200        final int fnId = newFunctionNode.getId();
201        final Map<Integer, RecompilableScriptFunctionData> nestedFunctions = fnIdToNestedFunctions.remove(fnId);
202
203        assert nestedFunctions != null;
204        // Generate the object class and property map in case this function is ever used as constructor
205        final RecompilableScriptFunctionData data = new RecompilableScriptFunctionData(
206                newFunctionNode,
207                compiler.getCodeInstaller(),
208                ObjectClassGenerator.createAllocationStrategy(newFunctionNode.getThisProperties(), compiler.getContext().useDualFields()),
209                nestedFunctions,
210                externalSymbolDepths.get(fnId),
211                internalSymbols.get(fnId));
212
213        if (lc.getOutermostFunction() != newFunctionNode) {
214            final FunctionNode parentFn = lc.getParentFunction(newFunctionNode);
215            if (parentFn != null) {
216                fnIdToNestedFunctions.get(parentFn.getId()).put(fnId, data);
217            }
218        } else {
219            compiler.setData(data);
220        }
221
222        if (isDynamicScopeBoundary(functionNode)) {
223            decreaseDynamicScopeCount(functionNode);
224        }
225
226        return newFunctionNode;
227    }
228
229    private boolean inDynamicScope() {
230        return dynamicScopeCount > 0;
231    }
232
233    private void increaseDynamicScopeCount(final Node node) {
234        assert dynamicScopeCount >= 0;
235        ++dynamicScopeCount;
236        if (log.isEnabled()) {
237            log.finest(quote(lc.getCurrentFunction().getName()), " ++dynamicScopeCount = ", dynamicScopeCount, " at: ", node, node.getClass());
238        }
239    }
240
241    private void decreaseDynamicScopeCount(final Node node) {
242        --dynamicScopeCount;
243        assert dynamicScopeCount >= 0;
244        if (log.isEnabled()) {
245            log.finest(quote(lc.getCurrentFunction().getName()), " --dynamicScopeCount = ", dynamicScopeCount, " at: ", node, node.getClass());
246        }
247    }
248
249    @Override
250    public boolean enterWithNode(final WithNode node) {
251        withBodies.add(node.getBody());
252        return true;
253    }
254
255    @Override
256    public boolean enterBlock(final Block block) {
257        if (compiler.isOnDemandCompilation()) {
258            return true;
259        }
260
261        if (isDynamicScopeBoundary(block)) {
262            increaseDynamicScopeCount(block);
263        }
264
265        if (!lc.isFunctionBody()) {
266            return true;
267        }
268
269        //the below part only happens on eager compilation when we have the entire hierarchy
270        //block is a function body
271        final FunctionNode fn = lc.getCurrentFunction();
272
273        //get all symbols that are referenced inside this function body
274        final Set<Symbol> symbols = new HashSet<>();
275        block.accept(new SimpleNodeVisitor() {
276            @Override
277            public boolean enterIdentNode(final IdentNode identNode) {
278                final Symbol symbol = identNode.getSymbol();
279                if (symbol != null && symbol.isScope()) {
280                    //if this is an internal symbol, skip it.
281                    symbols.add(symbol);
282                }
283                return true;
284            }
285        });
286
287        final Map<String, Integer> internals = new HashMap<>();
288
289        final Block globalBlock = findGlobalBlock(lc, block);
290        final Block bodyBlock   = findBodyBlock(lc, fn, block);
291
292        assert globalBlock != null;
293        assert bodyBlock   != null;
294
295        for (final Symbol symbol : symbols) {
296            Iterator<Block> iter;
297
298            final int internalDepth = findInternalDepth(lc, fn, block, symbol);
299            final boolean internal = internalDepth >= 0;
300            if (internal) {
301                internals.put(symbol.getName(), internalDepth);
302            }
303
304            // if not internal, we have to continue walking until we reach the top. We
305            // start outside the body and each new scope adds a depth count. When we
306            // find the symbol, we store its depth count
307            if (!internal) {
308                int depthAtStart = 0;
309                //not internal - keep looking.
310                iter = lc.getAncestorBlocks(bodyBlock);
311                while (iter.hasNext()) {
312                    final Block b2 = iter.next();
313                    if (definedInBlock(b2, symbol)) {
314                        addExternalSymbol(fn, symbol, depthAtStart);
315                        break;
316                    }
317                    if (b2.needsScope()) {
318                        depthAtStart++;
319                    }
320                }
321            }
322        }
323
324        addInternalSymbols(fn, internals.keySet());
325
326        if (log.isEnabled()) {
327            log.info(fn.getName() + " internals=" + internals + " externals=" + externalSymbolDepths.get(fn.getId()));
328        }
329
330        return true;
331    }
332
333    @Override
334    public Node leaveBlock(final Block block) {
335        if (compiler.isOnDemandCompilation()) {
336            return block;
337        }
338        if (isDynamicScopeBoundary(block)) {
339            decreaseDynamicScopeCount(block);
340        }
341        return block;
342    }
343
344    private void addInternalSymbols(final FunctionNode functionNode, final Set<String> symbols) {
345        final int fnId = functionNode.getId();
346        assert internalSymbols.get(fnId) == null || internalSymbols.get(fnId).equals(symbols); //e.g. cloned finally block
347        internalSymbols.put(fnId, symbols);
348    }
349
350    private void addExternalSymbol(final FunctionNode functionNode, final Symbol symbol, final int depthAtStart) {
351        final int fnId = functionNode.getId();
352        Map<String, Integer> depths = externalSymbolDepths.get(fnId);
353        if (depths == null) {
354            depths = new HashMap<>();
355            externalSymbolDepths.put(fnId, depths);
356        }
357        depths.put(symbol.getName(), depthAtStart);
358    }
359
360}
361