1 /*
   2  * Copyright (c) 2010, 2019, 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 
  26 package jdk.nashorn.internal.runtime;
  27 
  28 import static jdk.nashorn.internal.lookup.Lookup.MH;
  29 
  30 import java.io.IOException;
  31 import java.io.ObjectOutputStream;
  32 import java.io.Serializable;
  33 import java.lang.invoke.MethodHandle;
  34 import java.lang.invoke.MethodHandles;
  35 import java.lang.invoke.MethodType;
  36 import java.lang.ref.Reference;
  37 import java.lang.ref.SoftReference;
  38 import java.util.Collection;
  39 import java.util.Collections;
  40 import java.util.HashSet;
  41 import java.util.IdentityHashMap;
  42 import java.util.Map;
  43 import java.util.Set;
  44 import java.util.TreeMap;
  45 import java.util.concurrent.ExecutorService;
  46 import java.util.concurrent.LinkedBlockingDeque;
  47 import java.util.concurrent.ThreadPoolExecutor;
  48 import java.util.concurrent.TimeUnit;
  49 import jdk.nashorn.internal.codegen.Compiler;
  50 import jdk.nashorn.internal.codegen.Compiler.CompilationPhases;
  51 import jdk.nashorn.internal.codegen.CompilerConstants;
  52 import jdk.nashorn.internal.codegen.FunctionSignature;
  53 import jdk.nashorn.internal.codegen.Namespace;
  54 import jdk.nashorn.internal.codegen.OptimisticTypesPersistence;
  55 import jdk.nashorn.internal.codegen.TypeMap;
  56 import jdk.nashorn.internal.codegen.types.Type;
  57 import jdk.nashorn.internal.ir.Block;
  58 import jdk.nashorn.internal.ir.ForNode;
  59 import jdk.nashorn.internal.ir.FunctionNode;
  60 import jdk.nashorn.internal.ir.IdentNode;
  61 import jdk.nashorn.internal.ir.LexicalContext;
  62 import jdk.nashorn.internal.ir.Node;
  63 import jdk.nashorn.internal.ir.SwitchNode;
  64 import jdk.nashorn.internal.ir.Symbol;
  65 import jdk.nashorn.internal.ir.TryNode;
  66 import jdk.nashorn.internal.ir.visitor.SimpleNodeVisitor;
  67 import jdk.nashorn.internal.objects.Global;
  68 import jdk.nashorn.internal.parser.Parser;
  69 import jdk.nashorn.internal.parser.Token;
  70 import jdk.nashorn.internal.parser.TokenType;
  71 import jdk.nashorn.internal.runtime.linker.NameCodec;
  72 import jdk.nashorn.internal.runtime.logging.DebugLogger;
  73 import jdk.nashorn.internal.runtime.logging.Loggable;
  74 import jdk.nashorn.internal.runtime.logging.Logger;
  75 import jdk.nashorn.internal.runtime.options.Options;
  76 /**
  77  * This is a subclass that represents a script function that may be regenerated,
  78  * for example with specialization based on call site types, or lazily generated.
  79  * The common denominator is that it can get new invokers during its lifespan,
  80  * unlike {@code FinalScriptFunctionData}
  81  */
  82 @Logger(name="recompile")
  83 public final class RecompilableScriptFunctionData extends ScriptFunctionData implements Loggable {
  84     /** Prefix used for all recompiled script classes */
  85     public static final String RECOMPILATION_PREFIX = "Recompilation$";
  86 
  87     private static final ExecutorService astSerializerExecutorService = createAstSerializerExecutorService();
  88 
  89     /** Unique function node id for this function node */
  90     private final int functionNodeId;
  91 
  92     private final String functionName;
  93 
  94     /** The line number where this function begins. */
  95     private final int lineNumber;
  96 
  97     /** Source from which FunctionNode was parsed. */
  98     private transient Source source;
  99 
 100     /**
 101      * Cached form of the AST. Either a {@code SerializedAst} object used by split functions as they can't be
 102      * reparsed from source, or a soft reference to a {@code FunctionNode} for other functions (it is safe
 103      * to be cleared as they can be reparsed).
 104      */
 105     private volatile transient Object cachedAst;
 106 
 107     /** Token of this function within the source. */
 108     private final long token;
 109 
 110     /**
 111      * Represents the allocation strategy (property map, script object class, and method handle) for when
 112      * this function is used as a constructor. Note that majority of functions (those not setting any this.*
 113      * properties) will share a single canonical "default strategy" instance.
 114      */
 115     private final AllocationStrategy allocationStrategy;
 116 
 117     /**
 118      * Opaque object representing parser state at the end of the function. Used when reparsing outer function
 119      * to help with skipping parsing inner functions.
 120      */
 121     @SuppressWarnings("serial") // Not statically typed as Serializable
 122     private final Object endParserState;
 123 
 124     /** Code installer used for all further recompilation/specialization of this ScriptFunction */
 125     private transient CodeInstaller installer;
 126 
 127     @SuppressWarnings("serial") // Not statically typed as Serializable
 128     private final Map<Integer, RecompilableScriptFunctionData> nestedFunctions;
 129 
 130     /** Id to parent function if one exists */
 131     private RecompilableScriptFunctionData parent;
 132 
 133     /** Copy of the {@link FunctionNode} flags. */
 134     private final int functionFlags;
 135 
 136     private static final MethodHandles.Lookup LOOKUP = MethodHandles.lookup();
 137 
 138     private transient DebugLogger log;
 139 
 140     @SuppressWarnings("serial") // Not statically typed as Serializable
 141     private final Map<String, Integer> externalScopeDepths;
 142 
 143     @SuppressWarnings("serial") // Not statically typed as Serializable
 144     private final Set<String> internalSymbols;
 145 
 146     private static final int GET_SET_PREFIX_LENGTH = "*et ".length();
 147 
 148     private static final long serialVersionUID = 4914839316174633726L;
 149 
 150     /**
 151      * Constructor - public as scripts use it
 152      *
 153      * @param functionNode        functionNode that represents this function code
 154      * @param installer           installer for code regeneration versions of this function
 155      * @param allocationStrategy  strategy for the allocation behavior when this function is used as a constructor
 156      * @param nestedFunctions     nested function map
 157      * @param externalScopeDepths external scope depths
 158      * @param internalSymbols     internal symbols to method, defined in its scope
 159      */
 160     public RecompilableScriptFunctionData(
 161         final FunctionNode functionNode,
 162         final CodeInstaller installer,
 163         final AllocationStrategy allocationStrategy,
 164         final Map<Integer, RecompilableScriptFunctionData> nestedFunctions,
 165         final Map<String, Integer> externalScopeDepths,
 166         final Set<String> internalSymbols) {
 167 
 168         super(functionName(functionNode),
 169               Math.min(functionNode.getParameters().size(), MAX_ARITY),
 170               getDataFlags(functionNode));
 171 
 172         this.functionName        = functionNode.getName();
 173         this.lineNumber          = functionNode.getLineNumber();
 174         this.functionFlags       = functionNode.getFlags() | (functionNode.needsCallee() ? FunctionNode.NEEDS_CALLEE : 0);
 175         this.functionNodeId      = functionNode.getId();
 176         this.source              = functionNode.getSource();
 177         this.endParserState      = functionNode.getEndParserState();
 178         this.token               = tokenFor(functionNode);
 179         this.installer           = installer;
 180         this.allocationStrategy  = allocationStrategy;
 181         this.nestedFunctions     = smallMap(nestedFunctions);
 182         this.externalScopeDepths = smallMap(externalScopeDepths);
 183         this.internalSymbols     = smallSet(new HashSet<>(internalSymbols));
 184 
 185         for (final RecompilableScriptFunctionData nfn : nestedFunctions.values()) {
 186             assert nfn.getParent() == null;
 187             nfn.setParent(this);
 188         }
 189 
 190         createLogger();
 191     }
 192 
 193     private static <K, V> Map<K, V> smallMap(final Map<K, V> map) {
 194         if (map == null || map.isEmpty()) {
 195             return Collections.emptyMap();
 196         } else if (map.size() == 1) {
 197             final Map.Entry<K, V> entry = map.entrySet().iterator().next();
 198             return Collections.singletonMap(entry.getKey(), entry.getValue());
 199         } else {
 200             return map;
 201         }
 202     }
 203 
 204     private static <T> Set<T> smallSet(final Set<T> set) {
 205         if (set == null || set.isEmpty()) {
 206             return Collections.emptySet();
 207         } else if (set.size() == 1) {
 208             return Collections.singleton(set.iterator().next());
 209         } else {
 210             return set;
 211         }
 212     }
 213 
 214     @Override
 215     public DebugLogger getLogger() {
 216         return log;
 217     }
 218 
 219     @Override
 220     public DebugLogger initLogger(final Context ctxt) {
 221         return ctxt.getLogger(this.getClass());
 222     }
 223 
 224     /**
 225      * Check if a symbol is internally defined in a function. For example
 226      * if "undefined" is internally defined in the outermost program function,
 227      * it has not been reassigned or overridden and can be optimized
 228      *
 229      * @param symbolName symbol name
 230      * @return true if symbol is internal to this ScriptFunction
 231      */
 232 
 233     public boolean hasInternalSymbol(final String symbolName) {
 234         return internalSymbols.contains(symbolName);
 235     }
 236 
 237     /**
 238      * Return the external symbol table
 239      * @param symbolName symbol name
 240      * @return the external symbol table with proto depths
 241      */
 242     public int getExternalSymbolDepth(final String symbolName) {
 243         final Integer depth = externalScopeDepths.get(symbolName);
 244         return depth == null ? -1 : depth;
 245     }
 246 
 247     /**
 248      * Returns the names of all external symbols this function uses.
 249      * @return the names of all external symbols this function uses.
 250      */
 251     public Set<String> getExternalSymbolNames() {
 252         return Collections.unmodifiableSet(externalScopeDepths.keySet());
 253     }
 254 
 255     /**
 256      * Returns the opaque object representing the parser state at the end of this function's body, used to
 257      * skip parsing this function when reparsing its containing outer function.
 258      * @return the object representing the end parser state
 259      */
 260     public Object getEndParserState() {
 261         return endParserState;
 262     }
 263 
 264     /**
 265      * Get the parent of this RecompilableScriptFunctionData. If we are
 266      * a nested function, we have a parent. Note that "null" return value
 267      * can also mean that we have a parent but it is unknown, so this can
 268      * only be used for conservative assumptions.
 269      * @return parent data, or null if non exists and also null IF UNKNOWN.
 270      */
 271     public RecompilableScriptFunctionData getParent() {
 272         return parent;
 273     }
 274 
 275     void setParent(final RecompilableScriptFunctionData parent) {
 276         this.parent = parent;
 277     }
 278 
 279     @Override
 280     String toSource() {
 281         if (source != null && token != 0) {
 282             return source.getString(Token.descPosition(token), Token.descLength(token));
 283         }
 284 
 285         return "function " + (name == null ? "" : name) + "() { [native code] }";
 286     }
 287 
 288     /**
 289      * Initialize transient fields on deserialized instances
 290      *
 291      * @param src source
 292      * @param inst code installer
 293      */
 294     public void initTransients(final Source src, final CodeInstaller inst) {
 295         if (this.source == null && this.installer == null) {
 296             this.source    = src;
 297             this.installer = inst;
 298             for (final RecompilableScriptFunctionData nested : nestedFunctions.values()) {
 299                 nested.initTransients(src, inst);
 300             }
 301         } else if (this.source != src || !this.installer.isCompatibleWith(inst)) {
 302             // Existing values must be same as those passed as parameters
 303             throw new IllegalArgumentException();
 304         }
 305     }
 306 
 307     @Override
 308     public String toString() {
 309         return super.toString() + '@' + functionNodeId;
 310     }
 311 
 312     @Override
 313     public String toStringVerbose() {
 314         final StringBuilder sb = new StringBuilder();
 315 
 316         sb.append("fnId=").append(functionNodeId).append(' ');
 317 
 318         if (source != null) {
 319             sb.append(source.getName())
 320                 .append(':')
 321                 .append(lineNumber)
 322                 .append(' ');
 323         }
 324 
 325         return sb.toString() + super.toString();
 326     }
 327 
 328     @Override
 329     public String getFunctionName() {
 330         return functionName;
 331     }
 332 
 333     @Override
 334     public boolean inDynamicContext() {
 335         return getFunctionFlag(FunctionNode.IN_DYNAMIC_CONTEXT);
 336     }
 337 
 338     private static String functionName(final FunctionNode fn) {
 339         if (fn.isAnonymous()) {
 340             return "";
 341         }
 342         final FunctionNode.Kind kind = fn.getKind();
 343         if (kind == FunctionNode.Kind.GETTER || kind == FunctionNode.Kind.SETTER) {
 344             final String name = NameCodec.decode(fn.getIdent().getName());
 345             return name.substring(GET_SET_PREFIX_LENGTH);
 346         }
 347         return fn.getIdent().getName();
 348     }
 349 
 350     private static long tokenFor(final FunctionNode fn) {
 351         final int  position  = Token.descPosition(fn.getFirstToken());
 352         final long lastToken = Token.withDelimiter(fn.getLastToken());
 353         // EOL uses length field to store the line number
 354         final int  length    = Token.descPosition(lastToken) - position + (Token.descType(lastToken) == TokenType.EOL ? 0 : Token.descLength(lastToken));
 355 
 356         return Token.toDesc(TokenType.FUNCTION, position, length);
 357     }
 358 
 359     private static int getDataFlags(final FunctionNode functionNode) {
 360         int flags = IS_CONSTRUCTOR;
 361         if (functionNode.isStrict()) {
 362             flags |= IS_STRICT;
 363         }
 364         if (functionNode.needsCallee()) {
 365             flags |= NEEDS_CALLEE;
 366         }
 367         if (functionNode.usesThis() || functionNode.hasEval()) {
 368             flags |= USES_THIS;
 369         }
 370         if (functionNode.isVarArg()) {
 371             flags |= IS_VARIABLE_ARITY;
 372         }
 373         if (functionNode.getKind() == FunctionNode.Kind.GETTER || functionNode.getKind() == FunctionNode.Kind.SETTER) {
 374             flags |= IS_PROPERTY_ACCESSOR;
 375         }
 376         if (functionNode.isMethod() || functionNode.isClassConstructor()) {
 377             flags |= IS_ES6_METHOD;
 378         }
 379         return flags;
 380     }
 381 
 382     @Override
 383     PropertyMap getAllocatorMap(final ScriptObject prototype) {
 384         return allocationStrategy.getAllocatorMap(prototype);
 385     }
 386 
 387     @Override
 388     ScriptObject allocate(final PropertyMap map) {
 389         return allocationStrategy.allocate(map);
 390     }
 391 
 392     FunctionNode reparse() {
 393         final FunctionNode cachedFunction = getCachedAst();
 394         if (cachedFunction != null) {
 395             assert cachedFunction.isCached();
 396             return cachedFunction;
 397         }
 398 
 399         final int descPosition = Token.descPosition(token);
 400         final Context context = Context.getContextTrusted();
 401         final Parser parser = new Parser(
 402             context.getEnv(),
 403             source,
 404             new Context.ThrowErrorManager(),
 405             isStrict(),
 406             // source starts at line 0, so even though lineNumber is the correct declaration line, back off
 407             // one to make it exclusive
 408             lineNumber - 1,
 409             context.getLogger(Parser.class));
 410 
 411         if (getFunctionFlag(FunctionNode.IS_ANONYMOUS)) {
 412             parser.setFunctionName(functionName);
 413         }
 414         parser.setReparsedFunction(this);
 415 
 416         final FunctionNode program = parser.parse(CompilerConstants.PROGRAM.symbolName(), descPosition,
 417                 Token.descLength(token), flags);
 418         // Parser generates a program AST even if we're recompiling a single function, so when we are only
 419         // recompiling a single function, extract it from the program.
 420         return (isProgram() ? program : extractFunctionFromScript(program)).setName(null, functionName);
 421     }
 422 
 423     private FunctionNode getCachedAst() {
 424         final Object lCachedAst = cachedAst;
 425         // Are we softly caching the AST?
 426         if (lCachedAst instanceof Reference<?>) {
 427             final FunctionNode fn = (FunctionNode)((Reference<?>)lCachedAst).get();
 428             if (fn != null) {
 429                 // Yes we are - this is fast
 430                 return cloneSymbols(fn);
 431             }
 432         // Are we strongly caching a serialized AST (for split functions only)?
 433         } else if (lCachedAst instanceof SerializedAst) {
 434             final SerializedAst serializedAst = (SerializedAst)lCachedAst;
 435             // Even so, are we also softly caching the AST?
 436             final FunctionNode cachedFn = serializedAst.cachedAst == null ? null : serializedAst.cachedAst.get();
 437             if (cachedFn != null) {
 438                 // Yes we are - this is fast
 439                 return cloneSymbols(cachedFn);
 440             }
 441             final FunctionNode deserializedFn = deserialize(serializedAst.serializedAst);
 442             // Softly cache after deserialization, maybe next time we won't need to deserialize
 443             serializedAst.cachedAst = new SoftReference<>(deserializedFn);
 444             return deserializedFn;
 445         }
 446         // No cached representation; return null for reparsing
 447         return null;
 448     }
 449 
 450     /**
 451      * Sets the AST to cache in this function
 452      * @param astToCache the new AST to cache
 453      */
 454     public void setCachedAst(final FunctionNode astToCache) {
 455         assert astToCache.getId() == functionNodeId; // same function
 456         assert !(cachedAst instanceof SerializedAst); // Can't overwrite serialized AST
 457 
 458         final boolean isSplit = astToCache.isSplit();
 459         // If we're caching a split function, we're doing it in the eager pass, hence there can be no other
 460         // cached representation already. In other words, isSplit implies cachedAst == null.
 461         assert !isSplit || cachedAst == null; //
 462 
 463         final FunctionNode symbolClonedAst = cloneSymbols(astToCache);
 464         final Reference<FunctionNode> ref = new SoftReference<>(symbolClonedAst);
 465         cachedAst = ref;
 466 
 467         // Asynchronously serialize split functions.
 468         if (isSplit) {
 469             astSerializerExecutorService.execute(() -> {
 470                 cachedAst = new SerializedAst(symbolClonedAst, ref);
 471             });
 472         }
 473     }
 474 
 475     /**
 476      * Creates the AST serializer executor service used for in-memory serialization of split functions' ASTs.
 477      * It is created with an unbounded queue (so it can queue any number of pending tasks). Its core and max
 478      * threads is the same, but they are all allowed to time out so when there's no work, they can all go
 479      * away. The threads will be daemons, and they will time out if idle for a minute. Their priority is also
 480      * slightly lower than normal priority as we'd prefer the CPU to keep running the program; serializing
 481      * split function is a memory conservation measure (it allows us to release the AST), it can wait a bit.
 482      * @return an executor service with above described characteristics.
 483      */
 484     private static ExecutorService createAstSerializerExecutorService() {
 485         final int threads = Math.max(1, Options.getIntProperty("nashorn.serialize.threads", Runtime.getRuntime().availableProcessors() / 2));
 486         final ThreadPoolExecutor service = new ThreadPoolExecutor(threads, threads, 1, TimeUnit.MINUTES, new LinkedBlockingDeque<>(),
 487             (r) -> {
 488                 final Thread t = new Thread(r, "Nashorn AST Serializer");
 489                 t.setDaemon(true);
 490                 t.setPriority(Thread.NORM_PRIORITY - 1);
 491                 return t;
 492             });
 493         service.allowCoreThreadTimeOut(true);
 494         return service;
 495     }
 496 
 497     /**
 498      * A tuple of a serialized AST and a soft reference to a deserialized AST. This is used to cache split
 499      * functions. Since split functions are altered from their source form, they can't be reparsed from
 500      * source. While we could just use the {@code byte[]} representation in {@link RecompilableScriptFunctionData#cachedAst}
 501      * we're using this tuple instead to also keep a deserialized AST around in memory to cut down on
 502      * deserialization costs.
 503      */
 504     private static class SerializedAst implements Serializable {
 505         private final byte[] serializedAst;
 506         private volatile transient Reference<FunctionNode> cachedAst;
 507 
 508         private static final long serialVersionUID = 1L;
 509 
 510         SerializedAst(final FunctionNode fn, final Reference<FunctionNode> cachedAst) {
 511             this.serializedAst = AstSerializer.serialize(fn);
 512             this.cachedAst = cachedAst;
 513         }
 514     }
 515 
 516     private FunctionNode deserialize(final byte[] serializedAst) {
 517         final ScriptEnvironment env = installer.getContext().getEnv();
 518         final Timing timing = env._timing;
 519         final long t1 = System.nanoTime();
 520         try {
 521             return AstDeserializer.deserialize(serializedAst).initializeDeserialized(source, new Namespace(env.getNamespace()));
 522         } finally {
 523             timing.accumulateTime("'Deserialize'", System.nanoTime() - t1);
 524         }
 525     }
 526 
 527     private FunctionNode cloneSymbols(final FunctionNode fn) {
 528         final IdentityHashMap<Symbol, Symbol> symbolReplacements = new IdentityHashMap<>();
 529         final boolean cached = fn.isCached();
 530         // blockDefinedSymbols is used to re-mark symbols defined outside the function as global. We only
 531         // need to do this when we cache an eagerly parsed function (which currently means a split one, as we
 532         // don't cache non-split functions from the eager pass); those already cached, or those not split
 533         // don't need this step.
 534         final Set<Symbol> blockDefinedSymbols = fn.isSplit() && !cached ? Collections.newSetFromMap(new IdentityHashMap<>()) : null;
 535         FunctionNode newFn = (FunctionNode)fn.accept(new SimpleNodeVisitor() {
 536             private Symbol getReplacement(final Symbol original) {
 537                 if (original == null) {
 538                     return null;
 539                 }
 540                 final Symbol existingReplacement = symbolReplacements.get(original);
 541                 if (existingReplacement != null) {
 542                     return existingReplacement;
 543                 }
 544                 final Symbol newReplacement = original.clone();
 545                 symbolReplacements.put(original, newReplacement);
 546                 return newReplacement;
 547             }
 548 
 549             @Override
 550             public Node leaveIdentNode(final IdentNode identNode) {
 551                 final Symbol oldSymbol = identNode.getSymbol();
 552                 if (oldSymbol != null) {
 553                     final Symbol replacement = getReplacement(oldSymbol);
 554                     return identNode.setSymbol(replacement);
 555                 }
 556                 return identNode;
 557             }
 558 
 559             @Override
 560             public Node leaveForNode(final ForNode forNode) {
 561                 return ensureUniqueLabels(forNode.setIterator(lc, getReplacement(forNode.getIterator())));
 562             }
 563 
 564             @Override
 565             public Node leaveSwitchNode(final SwitchNode switchNode) {
 566                 return ensureUniqueLabels(switchNode.setTag(lc, getReplacement(switchNode.getTag())));
 567             }
 568 
 569             @Override
 570             public Node leaveTryNode(final TryNode tryNode) {
 571                 return ensureUniqueLabels(tryNode.setException(lc, getReplacement(tryNode.getException())));
 572             }
 573 
 574             @Override
 575             public boolean enterBlock(final Block block) {
 576                 for(final Symbol symbol: block.getSymbols()) {
 577                     final Symbol replacement = getReplacement(symbol);
 578                     if (blockDefinedSymbols != null) {
 579                         blockDefinedSymbols.add(replacement);
 580                     }
 581                 }
 582                 return true;
 583             }
 584 
 585             @Override
 586             public Node leaveBlock(final Block block) {
 587                 return ensureUniqueLabels(block.replaceSymbols(lc, symbolReplacements));
 588             }
 589 
 590             @Override
 591             public Node leaveFunctionNode(final FunctionNode functionNode) {
 592                 return functionNode.setParameters(lc, functionNode.visitParameters(this));
 593             }
 594 
 595             @Override
 596             protected Node leaveDefault(final Node node) {
 597                 return ensureUniqueLabels(node);
 598             };
 599 
 600             private Node ensureUniqueLabels(final Node node) {
 601                 // If we're returning a cached AST, we must also ensure unique labels
 602                 return cached ? node.ensureUniqueLabels(lc) : node;
 603             }
 604         });
 605 
 606         if (blockDefinedSymbols != null) {
 607             // Mark all symbols not defined in blocks as globals
 608             Block newBody = null;
 609             for(final Symbol symbol: symbolReplacements.values()) {
 610                 if(!blockDefinedSymbols.contains(symbol)) {
 611                     assert symbol.isScope(); // must be scope
 612                     assert externalScopeDepths.containsKey(symbol.getName()); // must be known to us as an external
 613                     // Register it in the function body symbol table as a new global symbol
 614                     symbol.setFlags((symbol.getFlags() & ~Symbol.KINDMASK) | Symbol.IS_GLOBAL);
 615                     if (newBody == null) {
 616                         newBody = newFn.getBody().copyWithNewSymbols();
 617                         newFn = newFn.setBody(null, newBody);
 618                     }
 619                     assert newBody.getExistingSymbol(symbol.getName()) == null; // must not be defined in the body already
 620                     newBody.putSymbol(symbol);
 621                 }
 622             }
 623         }
 624         return newFn.setCached(null);
 625     }
 626 
 627     private boolean getFunctionFlag(final int flag) {
 628         return (functionFlags & flag) != 0;
 629     }
 630 
 631     private boolean isProgram() {
 632         return getFunctionFlag(FunctionNode.IS_PROGRAM);
 633     }
 634 
 635     TypeMap typeMap(final MethodType fnCallSiteType) {
 636         if (fnCallSiteType == null) {
 637             return null;
 638         }
 639 
 640         if (CompiledFunction.isVarArgsType(fnCallSiteType)) {
 641             return null;
 642         }
 643 
 644         return new TypeMap(functionNodeId, explicitParams(fnCallSiteType), needsCallee());
 645     }
 646 
 647     private static ScriptObject newLocals(final ScriptObject runtimeScope) {
 648         final ScriptObject locals = Global.newEmptyInstance();
 649         locals.setProto(runtimeScope);
 650         return locals;
 651     }
 652 
 653     private Compiler getCompiler(final FunctionNode fn, final MethodType actualCallSiteType, final ScriptObject runtimeScope) {
 654         return getCompiler(fn, actualCallSiteType, newLocals(runtimeScope), null, null);
 655     }
 656 
 657     /**
 658      * Returns a code installer for installing new code. If we're using either optimistic typing or loader-per-compile,
 659      * then asks for a code installer with a new class loader; otherwise just uses the current installer. We use
 660      * a new class loader with optimistic typing so that deoptimized code can get reclaimed by GC.
 661      * @return a code installer for installing new code.
 662      */
 663     private CodeInstaller getInstallerForNewCode() {
 664         final ScriptEnvironment env = installer.getContext().getEnv();
 665         return env._optimistic_types || env._loader_per_compile ? installer.getOnDemandCompilationInstaller() : installer;
 666     }
 667 
 668     Compiler getCompiler(final FunctionNode functionNode, final MethodType actualCallSiteType,
 669             final ScriptObject runtimeScope, final Map<Integer, Type> invalidatedProgramPoints,
 670             final int[] continuationEntryPoints) {
 671         final TypeMap typeMap = typeMap(actualCallSiteType);
 672         final Type[] paramTypes = typeMap == null ? null : typeMap.getParameterTypes(functionNodeId);
 673         final Object typeInformationFile = OptimisticTypesPersistence.getLocationDescriptor(source, functionNodeId, paramTypes);
 674         return Compiler.forOnDemandCompilation(
 675                 getInstallerForNewCode(),
 676                 functionNode.getSource(),  // source
 677                 isStrict() | functionNode.isStrict(), // is strict
 678                 this,       // compiledFunction, i.e. this RecompilableScriptFunctionData
 679                 typeMap,    // type map
 680                 getEffectiveInvalidatedProgramPoints(invalidatedProgramPoints, typeInformationFile), // invalidated program points
 681                 typeInformationFile,
 682                 continuationEntryPoints, // continuation entry points
 683                 runtimeScope); // runtime scope
 684     }
 685 
 686     /**
 687      * If the function being compiled already has its own invalidated program points map, use it. Otherwise, attempt to
 688      * load invalidated program points map from the persistent type info cache.
 689      * @param invalidatedProgramPoints the function's current invalidated program points map. Null if the function
 690      * doesn't have it.
 691      * @param typeInformationFile the object describing the location of the persisted type information.
 692      * @return either the existing map, or a loaded map from the persistent type info cache, or a new empty map if
 693      * neither an existing map or a persistent cached type info is available.
 694      */
 695     @SuppressWarnings("unused")
 696     private static Map<Integer, Type> getEffectiveInvalidatedProgramPoints(
 697             final Map<Integer, Type> invalidatedProgramPoints, final Object typeInformationFile) {
 698         if(invalidatedProgramPoints != null) {
 699             return invalidatedProgramPoints;
 700         }
 701         final Map<Integer, Type> loadedProgramPoints = OptimisticTypesPersistence.load(typeInformationFile);
 702         return loadedProgramPoints != null ? loadedProgramPoints : new TreeMap<Integer, Type>();
 703     }
 704 
 705     private FunctionInitializer compileTypeSpecialization(final MethodType actualCallSiteType, final ScriptObject runtimeScope, final boolean persist) {
 706         // We're creating an empty script object for holding local variables. AssignSymbols will populate it with
 707         // explicit Undefined values for undefined local variables (see AssignSymbols#defineSymbol() and
 708         // CompilationEnvironment#declareLocalSymbol()).
 709 
 710         if (log.isEnabled()) {
 711             log.info("Parameter type specialization of '", functionName, "' signature: ", actualCallSiteType);
 712         }
 713 
 714         final boolean persistentCache = persist && usePersistentCodeCache();
 715         String cacheKey = null;
 716         if (persistentCache) {
 717             final TypeMap typeMap = typeMap(actualCallSiteType);
 718             final Type[] paramTypes = typeMap == null ? null : typeMap.getParameterTypes(functionNodeId);
 719             cacheKey = CodeStore.getCacheKey(functionNodeId, paramTypes);
 720             final CodeInstaller newInstaller = getInstallerForNewCode();
 721             final StoredScript script = newInstaller.loadScript(source, cacheKey);
 722 
 723             if (script != null) {
 724                 Compiler.updateCompilationId(script.getCompilationId());
 725                 return script.installFunction(this, newInstaller);
 726             }
 727         }
 728 
 729         final FunctionNode fn = reparse();
 730         final Compiler compiler = getCompiler(fn, actualCallSiteType, runtimeScope);
 731         final FunctionNode compiledFn = compiler.compile(fn,
 732                 fn.isCached() ? CompilationPhases.COMPILE_ALL_CACHED : CompilationPhases.COMPILE_ALL);
 733 
 734         if (persist && !compiledFn.hasApplyToCallSpecialization()) {
 735             compiler.persistClassInfo(cacheKey, compiledFn);
 736         }
 737         return new FunctionInitializer(compiledFn, compiler.getInvalidatedProgramPoints());
 738     }
 739 
 740     boolean usePersistentCodeCache() {
 741         return installer != null && installer.getContext().getEnv()._persistent_cache;
 742     }
 743 
 744     private MethodType explicitParams(final MethodType callSiteType) {
 745         if (CompiledFunction.isVarArgsType(callSiteType)) {
 746             return null;
 747         }
 748 
 749         final MethodType noCalleeThisType = callSiteType.dropParameterTypes(0, 2); // (callee, this) is always in call site type
 750         final int callSiteParamCount = noCalleeThisType.parameterCount();
 751 
 752         // Widen parameters of reference types to Object as we currently don't care for specialization among reference
 753         // types. E.g. call site saying (ScriptFunction, Object, String) should still link to (ScriptFunction, Object, Object)
 754         final Class<?>[] paramTypes = noCalleeThisType.parameterArray();
 755         boolean changed = false;
 756         for (int i = 0; i < paramTypes.length; ++i) {
 757             final Class<?> paramType = paramTypes[i];
 758             if (!(paramType.isPrimitive() || paramType == Object.class)) {
 759                 paramTypes[i] = Object.class;
 760                 changed = true;
 761             }
 762         }
 763         final MethodType generalized = changed ? MethodType.methodType(noCalleeThisType.returnType(), paramTypes) : noCalleeThisType;
 764 
 765         if (callSiteParamCount < getArity()) {
 766             return generalized.appendParameterTypes(Collections.<Class<?>>nCopies(getArity() - callSiteParamCount, Object.class));
 767         }
 768         return generalized;
 769     }
 770 
 771     private FunctionNode extractFunctionFromScript(final FunctionNode script) {
 772         final Set<FunctionNode> fns = new HashSet<>();
 773         script.getBody().accept(new SimpleNodeVisitor() {
 774             @Override
 775             public boolean enterFunctionNode(final FunctionNode fn) {
 776                 fns.add(fn);
 777                 return false;
 778             }
 779         });
 780         assert fns.size() == 1 : "got back more than one method in recompilation";
 781         final FunctionNode f = fns.iterator().next();
 782         assert f.getId() == functionNodeId;
 783         if (!getFunctionFlag(FunctionNode.IS_DECLARED) && f.isDeclared()) {
 784             return f.clearFlag(null, FunctionNode.IS_DECLARED);
 785         }
 786         return f;
 787     }
 788 
 789     private void logLookup(final boolean shouldLog, final MethodType targetType) {
 790         if (shouldLog && log.isEnabled()) {
 791             log.info("Looking up ", DebugLogger.quote(functionName), " type=", targetType);
 792         }
 793     }
 794 
 795     private MethodHandle lookup(final FunctionInitializer fnInit, final boolean shouldLog) {
 796         final MethodType type = fnInit.getMethodType();
 797         logLookup(shouldLog, type);
 798         return lookupCodeMethod(fnInit.getCode(), type);
 799     }
 800 
 801     MethodHandle lookup(final FunctionNode fn) {
 802         final MethodType type = new FunctionSignature(fn).getMethodType();
 803         logLookup(true, type);
 804         return lookupCodeMethod(fn.getCompileUnit().getCode(), type);
 805     }
 806 
 807     MethodHandle lookupCodeMethod(final Class<?> codeClass, final MethodType targetType) {
 808         return MH.findStatic(LOOKUP, codeClass, functionName, targetType);
 809     }
 810 
 811     /**
 812      * Initializes this function data with the eagerly generated version of the code. This method can only be invoked
 813      * by the compiler internals in Nashorn and is public for implementation reasons only. Attempting to invoke it
 814      * externally will result in an exception.
 815      *
 816      * @param functionNode FunctionNode for this data
 817      */
 818     public void initializeCode(final FunctionNode functionNode) {
 819         // Since the method is public, we double-check that we aren't invoked with an inappropriate compile unit.
 820         if (!code.isEmpty() || functionNode.getId() != functionNodeId || !functionNode.getCompileUnit().isInitializing(this, functionNode)) {
 821             throw new IllegalStateException(name);
 822         }
 823         addCode(lookup(functionNode), null, null, functionNode.getFlags());
 824     }
 825 
 826     /**
 827      * Initializes this function with the given function code initializer.
 828      * @param initializer function code initializer
 829      */
 830     void initializeCode(final FunctionInitializer initializer) {
 831         addCode(lookup(initializer, true), null, null, initializer.getFlags());
 832     }
 833 
 834     private CompiledFunction addCode(final MethodHandle target, final Map<Integer, Type> invalidatedProgramPoints,
 835                                      final MethodType callSiteType, final int fnFlags) {
 836         final CompiledFunction cfn = new CompiledFunction(target, this, invalidatedProgramPoints, callSiteType, fnFlags);
 837         assert noDuplicateCode(cfn) : "duplicate code";
 838         code.add(cfn);
 839         return cfn;
 840     }
 841 
 842     /**
 843      * Add code with specific call site type. It will adapt the type of the looked up method handle to fit the call site
 844      * type. This is necessary because even if we request a specialization that takes an "int" parameter, we might end
 845      * up getting one that takes a "double" etc. because of internal function logic causes widening (e.g. assignment of
 846      * a wider value to the parameter variable). However, we use the method handle type for matching subsequent lookups
 847      * for the same specialization, so we must adapt the handle to the expected type.
 848      * @param fnInit the function
 849      * @param callSiteType the call site type
 850      * @return the compiled function object, with its type matching that of the call site type.
 851      */
 852     private CompiledFunction addCode(final FunctionInitializer fnInit, final MethodType callSiteType) {
 853         if (isVariableArity()) {
 854             return addCode(lookup(fnInit, true), fnInit.getInvalidatedProgramPoints(), callSiteType, fnInit.getFlags());
 855         }
 856 
 857         final MethodHandle handle = lookup(fnInit, true);
 858         final MethodType fromType = handle.type();
 859         MethodType toType = needsCallee(fromType) ? callSiteType.changeParameterType(0, ScriptFunction.class) : callSiteType.dropParameterTypes(0, 1);
 860         toType = toType.changeReturnType(fromType.returnType());
 861 
 862         final int toCount = toType.parameterCount();
 863         final int fromCount = fromType.parameterCount();
 864         final int minCount = Math.min(fromCount, toCount);
 865         for(int i = 0; i < minCount; ++i) {
 866             final Class<?> fromParam = fromType.parameterType(i);
 867             final Class<?>   toParam =   toType.parameterType(i);
 868             // If method has an Object parameter, but call site had String, preserve it as Object. No need to narrow it
 869             // artificially. Note that this is related to how CompiledFunction.matchesCallSite() works, specifically
 870             // the fact that various reference types compare to equal (see "fnType.isEquivalentTo(csType)" there).
 871             if (fromParam != toParam && !fromParam.isPrimitive() && !toParam.isPrimitive()) {
 872                 assert fromParam.isAssignableFrom(toParam);
 873                 toType = toType.changeParameterType(i, fromParam);
 874             }
 875         }
 876         if (fromCount > toCount) {
 877             toType = toType.appendParameterTypes(fromType.parameterList().subList(toCount, fromCount));
 878         } else if (fromCount < toCount) {
 879             toType = toType.dropParameterTypes(fromCount, toCount);
 880         }
 881 
 882         return addCode(lookup(fnInit, false).asType(toType), fnInit.getInvalidatedProgramPoints(), callSiteType, fnInit.getFlags());
 883     }
 884 
 885     /**
 886      * Returns the return type of a function specialization for particular parameter types.<br>
 887      * <b>Be aware that the way this is implemented, it forces full materialization (compilation and installation) of
 888      * code for that specialization.</b>
 889      * @param callSiteType the parameter types at the call site. It must include the mandatory {@code callee} and
 890      * {@code this} parameters, so it needs to start with at least {@code ScriptFunction.class} and
 891      * {@code Object.class} class. Since the return type of the function is calculated from the code itself, it is
 892      * irrelevant and should be set to {@code Object.class}.
 893      * @param runtimeScope a current runtime scope. Can be null but when it's present it will be used as a source of
 894      * current runtime values that can improve the compiler's type speculations (and thus reduce the need for later
 895      * recompilations) if the specialization is not already present and thus needs to be freshly compiled.
 896      * @return the return type of the function specialization.
 897      */
 898     public Class<?> getReturnType(final MethodType callSiteType, final ScriptObject runtimeScope) {
 899         return getBest(callSiteType, runtimeScope, CompiledFunction.NO_FUNCTIONS).type().returnType();
 900     }
 901 
 902     @Override
 903     synchronized CompiledFunction getBest(final MethodType callSiteType, final ScriptObject runtimeScope, final Collection<CompiledFunction> forbidden, final boolean linkLogicOkay) {
 904         assert isValidCallSite(callSiteType) : callSiteType;
 905 
 906         CompiledFunction existingBest = pickFunction(callSiteType, false);
 907         if (existingBest == null) {
 908             existingBest = pickFunction(callSiteType, true); // try vararg last
 909         }
 910         if (existingBest == null) {
 911             existingBest = addCode(compileTypeSpecialization(callSiteType, runtimeScope, true), callSiteType);
 912         }
 913 
 914         assert existingBest != null;
 915 
 916         //if the best one is an apply to call, it has to match the callsite exactly
 917         //or we need to regenerate
 918         if (existingBest.isApplyToCall()) {
 919             final CompiledFunction best = lookupExactApplyToCall(callSiteType);
 920             if (best != null) {
 921                 return best;
 922             }
 923 
 924             // special case: we had an apply to call, but we failed to make it fit.
 925             // Try to generate a specialized one for this callsite. It may
 926             // be another apply to call specialization, or it may not, but whatever
 927             // it is, it is a specialization that is guaranteed to fit
 928             existingBest = addCode(compileTypeSpecialization(callSiteType, runtimeScope, false), callSiteType);
 929         }
 930 
 931         return existingBest;
 932     }
 933 
 934     @Override
 935     public boolean needsCallee() {
 936         return getFunctionFlag(FunctionNode.NEEDS_CALLEE);
 937     }
 938 
 939     /**
 940      * Returns the {@link FunctionNode} flags associated with this function data.
 941      * @return the {@link FunctionNode} flags associated with this function data.
 942      */
 943     public int getFunctionFlags() {
 944         return functionFlags;
 945     }
 946 
 947     @Override
 948     MethodType getGenericType() {
 949         // 2 is for (callee, this)
 950         if (isVariableArity()) {
 951             return MethodType.genericMethodType(2, true);
 952         }
 953         return MethodType.genericMethodType(2 + getArity());
 954     }
 955 
 956     /**
 957      * Return the function node id.
 958      * @return the function node id
 959      */
 960     public int getFunctionNodeId() {
 961         return functionNodeId;
 962     }
 963 
 964     /**
 965      * Get the source for the script
 966      * @return source
 967      */
 968     public Source getSource() {
 969         return source;
 970     }
 971 
 972     /**
 973      * Return a script function data based on a function id, either this function if
 974      * the id matches or a nested function based on functionId. This goes down into
 975      * nested functions until all leaves are exhausted.
 976      *
 977      * @param functionId function id
 978      * @return script function data or null if invalid id
 979      */
 980     public RecompilableScriptFunctionData getScriptFunctionData(final int functionId) {
 981         if (functionId == functionNodeId) {
 982             return this;
 983         }
 984         RecompilableScriptFunctionData data;
 985 
 986         data = nestedFunctions == null ? null : nestedFunctions.get(functionId);
 987         if (data != null) {
 988             return data;
 989         }
 990         for (final RecompilableScriptFunctionData ndata : nestedFunctions.values()) {
 991             data = ndata.getScriptFunctionData(functionId);
 992             if (data != null) {
 993                 return data;
 994             }
 995         }
 996         return null;
 997     }
 998 
 999     /**
1000      * Check whether a certain name is a global symbol, i.e. only exists as defined
1001      * in outermost scope and not shadowed by being parameter or assignment in inner
1002      * scopes
1003      *
1004      * @param functionNode function node to check
1005      * @param symbolName symbol name
1006      * @return true if global symbol
1007      */
1008     public boolean isGlobalSymbol(final FunctionNode functionNode, final String symbolName) {
1009         RecompilableScriptFunctionData data = getScriptFunctionData(functionNode.getId());
1010         assert data != null;
1011 
1012         do {
1013             if (data.hasInternalSymbol(symbolName)) {
1014                 return false;
1015             }
1016             data = data.getParent();
1017         } while(data != null);
1018 
1019         return true;
1020     }
1021 
1022     /**
1023      * Restores the {@link #getFunctionFlags()} flags to a function node. During on-demand compilation, we might need
1024      * to restore flags to a function node that was otherwise not subjected to a full compile pipeline (e.g. its parse
1025      * was skipped, or it's a nested function of a deserialized function.
1026      * @param lc current lexical context
1027      * @param fn the function node to restore flags onto
1028      * @return the transformed function node
1029      */
1030     public FunctionNode restoreFlags(final LexicalContext lc, final FunctionNode fn) {
1031         assert fn.getId() == functionNodeId;
1032         FunctionNode newFn = fn.setFlags(lc, functionFlags);
1033         // This compensates for missing markEval() in case the function contains an inner function
1034         // that contains eval(), that now we didn't discover since we skipped the inner function.
1035         if (newFn.hasNestedEval()) {
1036             assert newFn.hasScopeBlock();
1037             newFn = newFn.setBody(lc, newFn.getBody().setNeedsScope(null));
1038         }
1039         return newFn;
1040     }
1041 
1042     // Make sure code does not contain a compiled function with the same signature as compiledFunction
1043     private boolean noDuplicateCode(final CompiledFunction compiledFunction) {
1044         for (final CompiledFunction cf : code) {
1045             if (cf.type().equals(compiledFunction.type())) {
1046                 return false;
1047             }
1048         }
1049         return true;
1050     }
1051 
1052     private void writeObject(final ObjectOutputStream out) throws IOException {
1053         final Object localCachedAst = cachedAst;
1054         out.defaultWriteObject();
1055         // We need to persist SerializedAst for split functions as they can't reparse the source code.
1056         if (localCachedAst instanceof SerializedAst) {
1057             out.writeObject(localCachedAst);
1058         } else {
1059             out.writeObject(null);
1060         }
1061     }
1062 
1063     private void readObject(final java.io.ObjectInputStream in) throws IOException, ClassNotFoundException {
1064         in.defaultReadObject();
1065         cachedAst = in.readObject();
1066         createLogger();
1067     }
1068 
1069     private void createLogger() {
1070         log = initLogger(Context.getContextTrusted());
1071     }
1072 }