001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 *  Unless required by applicable law or agreed to in writing, software
012 *  distributed under the License is distributed on an "AS IS" BASIS,
013 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 *  See the License for the specific language governing permissions and
015 *  limitations under the License.
016 *
017 */
018package org.apache.bcel.verifier.structurals;
019
020import java.util.ArrayList;
021import java.util.HashMap;
022import java.util.HashSet;
023import java.util.List;
024import java.util.Map;
025import java.util.Set;
026
027import org.apache.bcel.generic.ASTORE;
028import org.apache.bcel.generic.ATHROW;
029import org.apache.bcel.generic.BranchInstruction;
030import org.apache.bcel.generic.CodeExceptionGen;
031import org.apache.bcel.generic.GotoInstruction;
032import org.apache.bcel.generic.IndexedInstruction;
033import org.apache.bcel.generic.Instruction;
034import org.apache.bcel.generic.InstructionHandle;
035import org.apache.bcel.generic.JsrInstruction;
036import org.apache.bcel.generic.LocalVariableInstruction;
037import org.apache.bcel.generic.MethodGen;
038import org.apache.bcel.generic.RET;
039import org.apache.bcel.generic.ReturnInstruction;
040import org.apache.bcel.generic.Select;
041import org.apache.bcel.verifier.exc.AssertionViolatedException;
042import org.apache.bcel.verifier.exc.StructuralCodeConstraintException;
043
044/**
045 * Instances of this class contain information about the subroutines found in a code array of a method. This
046 * implementation considers the top-level (the instructions reachable without a JSR or JSR_W starting off from the first
047 * instruction in a code array of a method) being a special subroutine; see getTopLevel() for that. Please note that the
048 * definition of subroutines in the Java Virtual Machine Specification, Second Edition is somewhat incomplete.
049 * Therefore, JustIce uses an own, more rigid notion. Basically, a subroutine is a piece of code that starts at the
050 * target of a JSR of JSR_W instruction and ends at a corresponding RET instruction. Note also that the control flow of
051 * a subroutine may be complex and non-linear; and that subroutines may be nested. JustIce also mandates subroutines not
052 * to be protected by exception handling code (for the sake of control flow predictability). To understand JustIce's
053 * notion of subroutines, please read
054 *
055 * TODO: refer to the paper.
056 *
057 * @see #getTopLevel()
058 */
059public class Subroutines {
060    // Node coloring constants
061    private enum ColourConstants {
062        WHITE, GRAY, BLACK
063    }
064
065    /**
066     * This inner class implements the Subroutine interface.
067     */
068    private class SubroutineImpl implements Subroutine {
069        /**
070         * UNSET, a symbol for an uninitialized localVariable field. This is used for the "top-level" Subroutine; i.e. no
071         * subroutine.
072         */
073        private static final int UNSET = -1;
074
075        private final SubroutineImpl[] EMPTY_ARRAY = {};
076
077        /**
078         * The Local Variable slot where the first instruction of this subroutine (an ASTORE) stores the JsrInstruction's
079         * ReturnAddress in and the RET of this subroutine operates on.
080         */
081        private int localVariable = UNSET;
082
083        /** The instructions that belong to this subroutine. */
084        private final Set<InstructionHandle> instructions = new HashSet<>(); // Elements: InstructionHandle
085
086        /**
087         * The JSR or JSR_W instructions that define this subroutine by targeting it.
088         */
089        private final Set<InstructionHandle> theJSRs = new HashSet<>();
090
091        /**
092         * The RET instruction that leaves this subroutine.
093         */
094        private InstructionHandle theRET;
095
096        /**
097         * The default constructor.
098         */
099        public SubroutineImpl() {
100        }
101
102        /**
103         * A recursive helper method for getRecursivelyAccessedLocalsIndices().
104         *
105         * @see #getRecursivelyAccessedLocalsIndices()
106         */
107        private void _getRecursivelyAccessedLocalsIndicesHelper(final Set<Integer> set, final Subroutine[] subs) {
108            for (final Subroutine sub : subs) {
109                final int[] lvs = sub.getAccessedLocalsIndices();
110                for (final int lv : lvs) {
111                    set.add(Integer.valueOf(lv));
112                }
113                if (sub.subSubs().length != 0) {
114                    _getRecursivelyAccessedLocalsIndicesHelper(set, sub.subSubs());
115                }
116            }
117        }
118
119        /**
120         * Adds a new JSR or JSR_W that has this subroutine as its target.
121         */
122        public void addEnteringJsrInstruction(final InstructionHandle jsrInst) {
123            if (jsrInst == null || !(jsrInst.getInstruction() instanceof JsrInstruction)) {
124                throw new AssertionViolatedException("Expecting JsrInstruction InstructionHandle.");
125            }
126            if (localVariable == UNSET) {
127                throw new AssertionViolatedException("Set the localVariable first!");
128            }
129            // Something is wrong when an ASTORE is targeted that does not operate on the same local variable than the rest of the
130            // JsrInstruction-targets and the RET.
131            // (We don't know out leader here so we cannot check if we're really targeted!)
132            if (localVariable != ((ASTORE) ((JsrInstruction) jsrInst.getInstruction()).getTarget().getInstruction()).getIndex()) {
133                throw new AssertionViolatedException("Setting a wrong JsrInstruction.");
134            }
135            theJSRs.add(jsrInst);
136        }
137
138        /*
139         * Adds an instruction to this subroutine. All instructions must have been added before invoking setLeavingRET().
140         *
141         * @see #setLeavingRET
142         */
143        void addInstruction(final InstructionHandle ih) {
144            if (theRET != null) {
145                throw new AssertionViolatedException("All instructions must have been added before invoking setLeavingRET().");
146            }
147            instructions.add(ih);
148        }
149
150        /*
151         * Refer to the Subroutine interface for documentation.
152         */
153        @Override
154        public boolean contains(final InstructionHandle inst) {
155            return instructions.contains(inst);
156        }
157
158        /*
159         * Satisfies Subroutine.getAccessedLocalIndices().
160         */
161        @Override
162        public int[] getAccessedLocalsIndices() {
163            // TODO: Implement caching.
164            final Set<Integer> acc = new HashSet<>();
165            if (theRET == null && this != getTopLevel()) {
166                throw new AssertionViolatedException("This subroutine object must be built up completely before calculating accessed locals.");
167            }
168            {
169                for (final InstructionHandle ih : instructions) {
170                    // RET is not a LocalVariableInstruction in the current version of BCEL.
171                    if (ih.getInstruction() instanceof LocalVariableInstruction || ih.getInstruction() instanceof RET) {
172                        final int idx = ((IndexedInstruction) ih.getInstruction()).getIndex();
173                        acc.add(Integer.valueOf(idx));
174                        // LONG? DOUBLE?.
175                        try {
176                            // LocalVariableInstruction instances are typed without the need to look into
177                            // the constant pool.
178                            if (ih.getInstruction() instanceof LocalVariableInstruction) {
179                                final int s = ((LocalVariableInstruction) ih.getInstruction()).getType(null).getSize();
180                                if (s == 2) {
181                                    acc.add(Integer.valueOf(idx + 1));
182                                }
183                            }
184                        } catch (final RuntimeException re) {
185                            throw new AssertionViolatedException("BCEL did not like NULL as a ConstantPoolGen object.", re);
186                        }
187                    }
188                }
189            }
190
191            {
192                final int[] ret = new int[acc.size()];
193                int j = -1;
194                for (final Integer accessedLocal : acc) {
195                    j++;
196                    ret[j] = accessedLocal.intValue();
197                }
198                return ret;
199            }
200        }
201
202        /*
203         * Refer to the Subroutine interface for documentation.
204         */
205        @Override
206        public InstructionHandle[] getEnteringJsrInstructions() {
207            if (this == getTopLevel()) {
208                throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine.");
209            }
210            return theJSRs.toArray(InstructionHandle.EMPTY_ARRAY);
211        }
212
213        /*
214         * Refer to the Subroutine interface for documentation.
215         */
216        @Override
217        public InstructionHandle[] getInstructions() {
218            return instructions.toArray(InstructionHandle.EMPTY_ARRAY);
219        }
220
221        /*
222         * Refer to the Subroutine interface for documentation.
223         */
224        @Override
225        public InstructionHandle getLeavingRET() {
226            if (this == getTopLevel()) {
227                throw new AssertionViolatedException("getLeavingRET() called on top level pseudo-subroutine.");
228            }
229            return theRET;
230        }
231
232        /* Satisfies Subroutine.getRecursivelyAccessedLocalsIndices(). */
233        @Override
234        public int[] getRecursivelyAccessedLocalsIndices() {
235            final Set<Integer> s = new HashSet<>();
236            final int[] lvs = getAccessedLocalsIndices();
237            for (final int lv : lvs) {
238                s.add(Integer.valueOf(lv));
239            }
240            _getRecursivelyAccessedLocalsIndicesHelper(s, this.subSubs());
241            final int[] ret = new int[s.size()];
242            int j = -1;
243            for (final Integer index : s) {
244                j++;
245                ret[j] = index.intValue();
246            }
247            return ret;
248        }
249
250        /**
251         * Sets the leaving RET instruction. Must be invoked after all instructions are added. Must not be invoked for top-level
252         * 'subroutine'.
253         */
254        void setLeavingRET() {
255            if (localVariable == UNSET) {
256                throw new AssertionViolatedException("setLeavingRET() called for top-level 'subroutine' or forgot to set local variable first.");
257            }
258            InstructionHandle ret = null;
259            for (final InstructionHandle actual : instructions) {
260                if (actual.getInstruction() instanceof RET) {
261                    if (ret != null) {
262                        throw new StructuralCodeConstraintException("Subroutine with more then one RET detected: '" + ret + "' and '" + actual + "'.");
263                    }
264                    ret = actual;
265                }
266            }
267            if (ret == null) {
268                throw new StructuralCodeConstraintException("Subroutine without a RET detected.");
269            }
270            if (((RET) ret.getInstruction()).getIndex() != localVariable) {
271                throw new StructuralCodeConstraintException(
272                    "Subroutine uses '" + ret + "' which does not match the correct local variable '" + localVariable + "'.");
273            }
274            theRET = ret;
275        }
276
277        /*
278         * Sets the local variable slot the ASTORE that is targeted by the JsrInstructions of this subroutine operates on. This
279         * subroutine's RET operates on that same local variable slot, of course.
280         */
281        void setLocalVariable(final int i) {
282            if (localVariable != UNSET) {
283                throw new AssertionViolatedException("localVariable set twice.");
284            }
285            localVariable = i;
286        }
287
288        /*
289         * Satisfies Subroutine.subSubs().
290         */
291        @Override
292        public Subroutine[] subSubs() {
293            final Set<Subroutine> h = new HashSet<>();
294
295            for (final InstructionHandle ih : instructions) {
296                final Instruction inst = ih.getInstruction();
297                if (inst instanceof JsrInstruction) {
298                    final InstructionHandle targ = ((JsrInstruction) inst).getTarget();
299                    h.add(getSubroutine(targ));
300                }
301            }
302            return h.toArray(EMPTY_ARRAY);
303        }
304
305        /**
306         * Returns a String representation of this object, merely for debugging purposes. (Internal) Warning: Verbosity on a
307         * problematic subroutine may cause stack overflow errors due to recursive subSubs() calls. Don't use this, then.
308         */
309        @Override
310        public String toString() {
311            final StringBuilder ret = new StringBuilder();
312            ret.append("Subroutine: Local variable is '").append(localVariable);
313            ret.append("', JSRs are '").append(theJSRs);
314            ret.append("', RET is '").append(theRET);
315            ret.append("', Instructions: '").append(instructions).append("'.");
316
317            ret.append(" Accessed local variable slots: '");
318            int[] alv = getAccessedLocalsIndices();
319            for (final int element : alv) {
320                ret.append(element);
321                ret.append(" ");
322            }
323            ret.append("'.");
324
325            ret.append(" Recursively (via subsub...routines) accessed local variable slots: '");
326            alv = getRecursivelyAccessedLocalsIndices();
327            for (final int element : alv) {
328                ret.append(element);
329                ret.append(" ");
330            }
331            ret.append("'.");
332
333            return ret.toString();
334        }
335
336    }// end Inner Class SubrouteImpl
337
338    /**
339     * A utility method that calculates the successors of a given InstructionHandle <B>in the same subroutine</B>. That
340     * means, a RET does not have any successors as defined here. A JsrInstruction has its physical successor as its
341     * successor (opposed to its target) as defined here.
342     */
343    private static InstructionHandle[] getSuccessors(final InstructionHandle instruction) {
344        final InstructionHandle[] single = new InstructionHandle[1];
345
346        final Instruction inst = instruction.getInstruction();
347
348        // Terminates method normally.
349        // Terminates method abnormally, because JustIce mandates
350        // subroutines not to be protected by exception handlers.
351        if (inst instanceof RET || inst instanceof ReturnInstruction || inst instanceof ATHROW) {
352            return InstructionHandle.EMPTY_ARRAY;
353        }
354
355        // See method comment.
356        if (inst instanceof JsrInstruction) {
357            single[0] = instruction.getNext();
358            return single;
359        }
360
361        if (inst instanceof GotoInstruction) {
362            single[0] = ((GotoInstruction) inst).getTarget();
363            return single;
364        }
365
366        if (inst instanceof BranchInstruction) {
367            if (inst instanceof Select) {
368                // BCEL's getTargets() returns only the non-default targets,
369                // thanks to Eli Tilevich for reporting.
370                final InstructionHandle[] matchTargets = ((Select) inst).getTargets();
371                final InstructionHandle[] ret = new InstructionHandle[matchTargets.length + 1];
372                ret[0] = ((Select) inst).getTarget();
373                System.arraycopy(matchTargets, 0, ret, 1, matchTargets.length);
374                return ret;
375            }
376            final InstructionHandle[] pair = new InstructionHandle[2];
377            pair[0] = instruction.getNext();
378            pair[1] = ((BranchInstruction) inst).getTarget();
379            return pair;
380        }
381
382        // default case: Fall through.
383        single[0] = instruction.getNext();
384        return single;
385    }
386
387    /**
388     * The map containing the subroutines found. Key: InstructionHandle of the leader of the subroutine. Elements:
389     * SubroutineImpl objects.
390     */
391    private final Map<InstructionHandle, Subroutine> subroutines = new HashMap<>();
392
393    /**
394     * This is referring to a special subroutine, namely the top level. This is not really a subroutine but we use it to
395     * distinguish between top level instructions and unreachable instructions.
396     */
397    // CHECKSTYLE:OFF
398    public final Subroutine TOPLEVEL; // TODO can this be made private?
399    // CHECKSTYLE:ON
400
401    /**
402     * Constructor.
403     *
404     * @param mg A MethodGen object representing method to create the Subroutine objects of. Assumes that JustIce strict
405     *        checks are needed.
406     */
407    public Subroutines(final MethodGen mg) {
408        this(mg, true);
409    }
410
411    /**
412     * Constructor.
413     *
414     * @param mg A MethodGen object representing method to create the Subroutine objects of.
415     * @param enableJustIceCheck whether to enable additional JustIce checks
416     * @since 6.0
417     */
418    public Subroutines(final MethodGen mg, final boolean enableJustIceCheck) {
419        final InstructionHandle[] all = mg.getInstructionList().getInstructionHandles();
420        final CodeExceptionGen[] handlers = mg.getExceptionHandlers();
421
422        // Define our "Toplevel" fake subroutine.
423        TOPLEVEL = new SubroutineImpl();
424
425        // Calculate "real" subroutines.
426        final Set<InstructionHandle> sub_leaders = new HashSet<>(); // Elements: InstructionHandle
427        for (final InstructionHandle element : all) {
428            final Instruction inst = element.getInstruction();
429            if (inst instanceof JsrInstruction) {
430                sub_leaders.add(((JsrInstruction) inst).getTarget());
431            }
432        }
433
434        // Build up the database.
435        for (final InstructionHandle astore : sub_leaders) {
436            final SubroutineImpl sr = new SubroutineImpl();
437            sr.setLocalVariable(((ASTORE) astore.getInstruction()).getIndex());
438            subroutines.put(astore, sr);
439        }
440
441        // Fake it a bit. We want a virtual "TopLevel" subroutine.
442        subroutines.put(all[0], TOPLEVEL);
443        sub_leaders.add(all[0]);
444
445        // Tell the subroutines about their JsrInstructions.
446        // Note that there cannot be a JSR targeting the top-level
447        // since "Jsr 0" is disallowed in Pass 3a.
448        // Instructions shared by a subroutine and the toplevel are
449        // disallowed and checked below, after the BFS.
450        for (final InstructionHandle element : all) {
451            final Instruction inst = element.getInstruction();
452            if (inst instanceof JsrInstruction) {
453                final InstructionHandle leader = ((JsrInstruction) inst).getTarget();
454                ((SubroutineImpl) getSubroutine(leader)).addEnteringJsrInstruction(element);
455            }
456        }
457
458        // Now do a BFS from every subroutine leader to find all the
459        // instructions that belong to a subroutine.
460        // we don't want to assign an instruction to two or more Subroutine objects.
461        final Set<InstructionHandle> instructions_assigned = new HashSet<>();
462
463        // Graph coloring. Key: InstructionHandle, Value: ColourConstants enum .
464        final Map<InstructionHandle, ColourConstants> colors = new HashMap<>();
465
466        final List<InstructionHandle> qList = new ArrayList<>();
467        for (final InstructionHandle actual : sub_leaders) {
468            // Do some BFS with "actual" as the root of the graph.
469            // Init colors
470            for (final InstructionHandle element : all) {
471                colors.put(element, ColourConstants.WHITE);
472            }
473            colors.put(actual, ColourConstants.GRAY);
474            // Init Queue
475
476            qList.clear();
477            qList.add(actual); // add(Obj) adds to the end, remove(0) removes from the start.
478
479            /*
480             * BFS ALGORITHM MODIFICATION: Start out with multiple "root" nodes, as exception handlers are starting points of
481             * top-level code, too. [why top-level? TODO: Refer to the special JustIce notion of subroutines.]
482             */
483            if (actual == all[0]) {
484                for (final CodeExceptionGen handler : handlers) {
485                    colors.put(handler.getHandlerPC(), ColourConstants.GRAY);
486                    qList.add(handler.getHandlerPC());
487                }
488            }
489            /* CONTINUE NORMAL BFS ALGORITHM */
490
491            // Loop until Queue is empty
492            while (!qList.isEmpty()) {
493                final InstructionHandle u = qList.remove(0);
494                final InstructionHandle[] successors = getSuccessors(u);
495                for (final InstructionHandle successor : successors) {
496                    if (colors.get(successor) == ColourConstants.WHITE) {
497                        colors.put(successor, ColourConstants.GRAY);
498                        qList.add(successor);
499                    }
500                }
501                colors.put(u, ColourConstants.BLACK);
502            }
503            // BFS ended above.
504            for (final InstructionHandle element : all) {
505                if (colors.get(element) == ColourConstants.BLACK) {
506                    ((SubroutineImpl) (actual == all[0] ? getTopLevel() : getSubroutine(actual))).addInstruction(element);
507                    if (instructions_assigned.contains(element)) {
508                        throw new StructuralCodeConstraintException(
509                            "Instruction '" + element + "' is part of more than one subroutine (or of the top level and a subroutine).");
510                    }
511                    instructions_assigned.add(element);
512                }
513            }
514            if (actual != all[0]) {// If we don't deal with the top-level 'subroutine'
515                ((SubroutineImpl) getSubroutine(actual)).setLeavingRET();
516            }
517        }
518
519        if (enableJustIceCheck) {
520            // Now make sure no instruction of a Subroutine is protected by exception handling code
521            // as is mandated by JustIces notion of subroutines.
522            for (final CodeExceptionGen handler : handlers) {
523                InstructionHandle _protected = handler.getStartPC();
524                while (_protected != handler.getEndPC().getNext()) {
525                    // Note the inclusive/inclusive notation of "generic API" exception handlers!
526                    for (final Subroutine sub : subroutines.values()) {
527                        if (sub != subroutines.get(all[0]) && sub.contains(_protected)) {
528                            throw new StructuralCodeConstraintException("Subroutine instruction '" + _protected + "' is protected by an exception handler, '"
529                                + handler + "'. This is forbidden by the JustIce verifier due to its clear definition of subroutines.");
530                        }
531                    }
532                    _protected = _protected.getNext();
533                }
534            }
535        }
536
537        // Now make sure no subroutine is calling a subroutine
538        // that uses the same local variable for the RET as themselves
539        // (recursively).
540        // This includes that subroutines may not call themselves
541        // recursively, even not through intermediate calls to other
542        // subroutines.
543        noRecursiveCalls(getTopLevel(), new HashSet<>());
544
545    }
546
547    /**
548     * Returns the Subroutine object associated with the given leader (that is, the first instruction of the subroutine).
549     * You must not use this to get the top-level instructions modeled as a Subroutine object.
550     *
551     * @see #getTopLevel()
552     */
553    public Subroutine getSubroutine(final InstructionHandle leader) {
554        final Subroutine ret = subroutines.get(leader);
555
556        if (ret == null) {
557            throw new AssertionViolatedException("Subroutine requested for an InstructionHandle that is not a leader of a subroutine.");
558        }
559
560        if (ret == TOPLEVEL) {
561            throw new AssertionViolatedException("TOPLEVEL special subroutine requested; use getTopLevel().");
562        }
563
564        return ret;
565    }
566
567    /**
568     * For easy handling, the piece of code that is <B>not</B> a subroutine, the top-level, is also modeled as a Subroutine
569     * object. It is a special Subroutine object where <B>you must not invoke getEnteringJsrInstructions() or
570     * getLeavingRET()</B>.
571     *
572     * @see Subroutine#getEnteringJsrInstructions()
573     * @see Subroutine#getLeavingRET()
574     */
575    public Subroutine getTopLevel() {
576        return TOPLEVEL;
577    }
578
579    /**
580     * This (recursive) utility method makes sure that no subroutine is calling a subroutine that uses the same local
581     * variable for the RET as themselves (recursively). This includes that subroutines may not call themselves recursively,
582     * even not through intermediate calls to other subroutines.
583     *
584     * @throws StructuralCodeConstraintException if the above constraint is not satisfied.
585     */
586    private void noRecursiveCalls(final Subroutine sub, final Set<Integer> set) {
587        final Subroutine[] subs = sub.subSubs();
588
589        for (final Subroutine sub2 : subs) {
590            final int index = ((RET) sub2.getLeavingRET().getInstruction()).getIndex();
591
592            if (!set.add(Integer.valueOf(index))) {
593                // Don't use toString() here because of possibly infinite recursive subSubs() calls then.
594                final SubroutineImpl si = (SubroutineImpl) sub2;
595                throw new StructuralCodeConstraintException("Subroutine with local variable '" + si.localVariable + "', JSRs '" + si.theJSRs + "', RET '"
596                    + si.theRET + "' is called by a subroutine which uses the same local variable index as itself; maybe even a recursive call?"
597                    + " JustIce's clean definition of a subroutine forbids both.");
598            }
599
600            noRecursiveCalls(sub2, set);
601
602            set.remove(Integer.valueOf(index));
603        }
604    }
605
606    /**
607     * Returns the subroutine object associated with the given instruction. This is a costly operation, you should consider
608     * using getSubroutine(InstructionHandle). Returns 'null' if the given InstructionHandle lies in so-called 'dead code',
609     * i.e. code that can never be executed.
610     *
611     * @see #getSubroutine(InstructionHandle)
612     * @see #getTopLevel()
613     */
614    public Subroutine subroutineOf(final InstructionHandle any) {
615        for (final Subroutine s : subroutines.values()) {
616            if (s.contains(any)) {
617                return s;
618            }
619        }
620        System.err.println("DEBUG: Please verify '" + any.toString(true) + "' lies in dead code.");
621        return null;
622        // throw new AssertionViolatedException("No subroutine for InstructionHandle found (DEAD CODE?).");
623    }
624
625    /**
626     * Returns a String representation of this object; merely for debugging puposes.
627     */
628    @Override
629    public String toString() {
630        return "---\n" + subroutines + "\n---\n";
631    }
632}