DebugInfoDecoder.java revision 579d7739c53a2707ad711a2d2cae46d7d782f061 
1/*
2 * Copyright (C) 2007 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.dx.dex.file;
18
19import com.android.dx.dex.code.DalvCode;
20import com.android.dx.dex.code.DalvInsnList;
21import com.android.dx.dex.code.LocalList;
22import com.android.dx.dex.code.PositionList;
23import com.android.dx.rop.cst.CstMethodRef;
24import com.android.dx.rop.cst.CstString;
25import com.android.dx.rop.type.Prototype;
26import com.android.dx.rop.type.StdTypeList;
27import com.android.dx.rop.type.Type;
28import com.android.dx.util.ByteArrayByteInput;
29import com.android.dx.util.ByteInput;
30import com.android.dx.util.ExceptionWithContext;
31
32import com.android.dx.util.Leb128Utils;
33import java.io.IOException;
34import java.util.ArrayList;
35import java.util.List;
36
37import static com.android.dx.dex.file.DebugInfoConstants.*;
38
39/**
40 * A decoder for the dex debug info state machine format.
41 * This code exists mostly as a reference implementation and test for
42 * for the {@code DebugInfoEncoder}
43 */
44public class DebugInfoDecoder {
45    /** encoded debug info */
46    private final byte[] encoded;
47
48    /** positions decoded */
49    private final ArrayList<PositionEntry> positions;
50
51    /** locals decoded */
52    private final ArrayList<LocalEntry> locals;
53
54    /** size of code block in code units */
55    private final int codesize;
56
57    /** indexed by register, the last local variable live in a reg */
58    private final LocalEntry[] lastEntryForReg;
59
60    /** method descriptor of method this debug info is for */
61    private final Prototype desc;
62
63    /** true if method is static */
64    private final boolean isStatic;
65
66    /** dex file this debug info will be stored in */
67    private final DexFile file;
68
69    /**
70     * register size, in register units, of the register space
71     * used by this method
72     */
73    private final int regSize;
74
75    /** current decoding state: line number */
76    private int line = 1;
77
78    /** current decoding state: bytecode address */
79    private int address = 0;
80
81    /** string index of the string "this" */
82    private final int thisStringIdx;
83
84    /**
85     * Constructs an instance.
86     *
87     * @param encoded encoded debug info
88     * @param codesize size of code block in code units
89     * @param regSize register size, in register units, of the register space
90     * used by this method
91     * @param isStatic true if method is static
92     * @param ref method descriptor of method this debug info is for
93     * @param file dex file this debug info will be stored in
94     */
95    DebugInfoDecoder(byte[] encoded, int codesize, int regSize,
96            boolean isStatic, CstMethodRef ref, DexFile file) {
97        if (encoded == null) {
98            throw new NullPointerException("encoded == null");
99        }
100
101        this.encoded = encoded;
102        this.isStatic = isStatic;
103        this.desc = ref.getPrototype();
104        this.file = file;
105        this.regSize = regSize;
106
107        positions = new ArrayList<PositionEntry>();
108        locals = new ArrayList<LocalEntry>();
109        this.codesize = codesize;
110        lastEntryForReg = new LocalEntry[regSize];
111
112        int idx = -1;
113
114        try {
115            idx = file.getStringIds().indexOf(new CstString("this"));
116        } catch (IllegalArgumentException ex) {
117            /*
118             * Silently tolerate not finding "this". It just means that
119             * no method has local variable info that looks like
120             * a standard instance method.
121             */
122        }
123
124        thisStringIdx = idx;
125    }
126
127    /**
128     * An entry in the resulting postions table
129     */
130    static private class PositionEntry {
131        /** bytecode address */
132        public int address;
133
134        /** line number */
135        public int line;
136
137        public PositionEntry(int address, int line) {
138            this.address = address;
139            this.line = line;
140        }
141    }
142
143    /**
144     * An entry in the resulting locals table
145     */
146    static private class LocalEntry {
147        /** address of event */
148        public int address;
149
150        /** {@code true} iff it's a local start */
151        public boolean isStart;
152
153        /** register number */
154        public int reg;
155
156        /** index of name in strings table */
157        public int nameIndex;
158
159        /** index of type in types table */
160        public int typeIndex;
161
162        /** index of type signature in strings table */
163        public int signatureIndex;
164
165        public LocalEntry(int address, boolean isStart, int reg, int nameIndex,
166                int typeIndex, int signatureIndex) {
167            this.address        = address;
168            this.isStart        = isStart;
169            this.reg            = reg;
170            this.nameIndex      = nameIndex;
171            this.typeIndex      = typeIndex;
172            this.signatureIndex = signatureIndex;
173        }
174
175        public String toString() {
176            return String.format("[%x %s v%d %04x %04x %04x]",
177                    address, isStart ? "start" : "end", reg,
178                    nameIndex, typeIndex, signatureIndex);
179        }
180    }
181
182    /**
183     * Gets the decoded positions list.
184     * Valid after calling {@code decode}.
185     *
186     * @return positions list in ascending address order.
187     */
188    public List<PositionEntry> getPositionList() {
189        return positions;
190    }
191
192    /**
193     * Gets the decoded locals list, in ascending start-address order.
194     * Valid after calling {@code decode}.
195     *
196     * @return locals list in ascending address order.
197     */
198    public List<LocalEntry> getLocals() {
199        return locals;
200    }
201
202    /**
203     * Decodes the debug info sequence.
204     */
205    public void decode() {
206        try {
207            decode0();
208        } catch (Exception ex) {
209            throw ExceptionWithContext.withContext(ex,
210                    "...while decoding debug info");
211        }
212    }
213
214    /**
215     * Reads a string index. String indicies are offset by 1, and a 0 value
216     * in the stream (-1 as returned by this method) means "null"
217     *
218     * @return index into file's string ids table, -1 means null
219     * @throws IOException
220     */
221    private int readStringIndex(ByteInput bs) throws IOException {
222        int offsetIndex = Leb128Utils.readUnsignedLeb128(bs);
223
224        return offsetIndex - 1;
225    }
226
227    /**
228     * Gets the register that begins the method's parameter range (including
229     * the 'this' parameter for non-static methods). The range continues until
230     * {@code regSize}
231     *
232     * @return register as noted above.
233     */
234    private int getParamBase() {
235        return regSize
236                - desc.getParameterTypes().getWordCount() - (isStatic? 0 : 1);
237    }
238
239    private void decode0() throws IOException {
240        ByteInput bs = new ByteArrayByteInput(encoded);
241
242        line = Leb128Utils.readUnsignedLeb128(bs);
243        int szParams = Leb128Utils.readUnsignedLeb128(bs);
244        StdTypeList params = desc.getParameterTypes();
245        int curReg = getParamBase();
246
247        if (szParams != params.size()) {
248            throw new RuntimeException(
249                    "Mismatch between parameters_size and prototype");
250        }
251
252        if (!isStatic) {
253            // Start off with implicit 'this' entry
254            LocalEntry thisEntry =
255                new LocalEntry(0, true, curReg, thisStringIdx, 0, 0);
256            locals.add(thisEntry);
257            lastEntryForReg[curReg] = thisEntry;
258            curReg++;
259        }
260
261        for (int i = 0; i < szParams; i++) {
262            Type paramType = params.getType(i);
263            LocalEntry le;
264
265            int nameIdx = readStringIndex(bs);
266
267            if (nameIdx == -1) {
268                /*
269                 * Unnamed parameter; often but not always filled in by an
270                 * extended start op after the prologue
271                 */
272                le = new LocalEntry(0, true, curReg, -1, 0, 0);
273            } else {
274                // TODO: Final 0 should be idx of paramType.getDescriptor().
275                le = new LocalEntry(0, true, curReg, nameIdx, 0, 0);
276            }
277
278            locals.add(le);
279            lastEntryForReg[curReg] = le;
280            curReg += paramType.getCategory();
281        }
282
283        for (;;) {
284            int opcode = bs.readByte() & 0xff;
285
286            switch (opcode) {
287                case DBG_START_LOCAL: {
288                    int reg = Leb128Utils.readUnsignedLeb128(bs);
289                    int nameIdx = readStringIndex(bs);
290                    int typeIdx = readStringIndex(bs);
291                    LocalEntry le = new LocalEntry(
292                            address, true, reg, nameIdx, typeIdx, 0);
293
294                    locals.add(le);
295                    lastEntryForReg[reg] = le;
296                }
297                break;
298
299                case DBG_START_LOCAL_EXTENDED: {
300                    int reg = Leb128Utils.readUnsignedLeb128(bs);
301                    int nameIdx = readStringIndex(bs);
302                    int typeIdx = readStringIndex(bs);
303                    int sigIdx = readStringIndex(bs);
304                    LocalEntry le = new LocalEntry(
305                            address, true, reg, nameIdx, typeIdx, sigIdx);
306
307                    locals.add(le);
308                    lastEntryForReg[reg] = le;
309                }
310                break;
311
312                case DBG_RESTART_LOCAL: {
313                    int reg = Leb128Utils.readUnsignedLeb128(bs);
314                    LocalEntry prevle;
315                    LocalEntry le;
316
317                    try {
318                        prevle = lastEntryForReg[reg];
319
320                        if (prevle.isStart) {
321                            throw new RuntimeException("nonsensical "
322                                    + "RESTART_LOCAL on live register v"
323                                    + reg);
324                        }
325
326                        le = new LocalEntry(address, true, reg,
327                                prevle.nameIndex, prevle.typeIndex, 0);
328                    } catch (NullPointerException ex) {
329                        throw new RuntimeException(
330                                "Encountered RESTART_LOCAL on new v" + reg);
331                    }
332
333                    locals.add(le);
334                    lastEntryForReg[reg] = le;
335                }
336                break;
337
338                case DBG_END_LOCAL: {
339                    int reg = Leb128Utils.readUnsignedLeb128(bs);
340                    LocalEntry prevle;
341                    LocalEntry le;
342
343                    try {
344                        prevle = lastEntryForReg[reg];
345
346                        if (!prevle.isStart) {
347                            throw new RuntimeException("nonsensical "
348                                    + "END_LOCAL on dead register v" + reg);
349                        }
350
351                        le = new LocalEntry(address, false, reg,
352                                prevle.nameIndex, prevle.typeIndex,
353                                prevle.signatureIndex);
354                    } catch (NullPointerException ex) {
355                        throw new RuntimeException(
356                                "Encountered END_LOCAL on new v" + reg);
357                    }
358
359                    locals.add(le);
360                    lastEntryForReg[reg] = le;
361                }
362                break;
363
364                case DBG_END_SEQUENCE:
365                    // all done
366                return;
367
368                case DBG_ADVANCE_PC:
369                    address += Leb128Utils.readUnsignedLeb128(bs);
370                break;
371
372                case DBG_ADVANCE_LINE:
373                    line += Leb128Utils.readSignedLeb128(bs);
374                break;
375
376                case DBG_SET_PROLOGUE_END:
377                    //TODO do something with this.
378                break;
379
380                case DBG_SET_EPILOGUE_BEGIN:
381                    //TODO do something with this.
382                break;
383
384                case DBG_SET_FILE:
385                    //TODO do something with this.
386                break;
387
388                default:
389                    if (opcode < DBG_FIRST_SPECIAL) {
390                        throw new RuntimeException(
391                                "Invalid extended opcode encountered "
392                                        + opcode);
393                    }
394
395                    int adjopcode = opcode - DBG_FIRST_SPECIAL;
396
397                    address += adjopcode / DBG_LINE_RANGE;
398                    line += DBG_LINE_BASE + (adjopcode % DBG_LINE_RANGE);
399
400                    positions.add(new PositionEntry(address, line));
401                break;
402
403            }
404        }
405    }
406
407    /**
408     * Validates an encoded debug info stream against data used to encode it,
409     * throwing an exception if they do not match. Used to validate the
410     * encoder.
411     *
412     * @param info encoded debug info
413     * @param file {@code non-null;} file to refer to during decoding
414     * @param ref {@code non-null;} method whose info is being decoded
415     * @param code {@code non-null;} original code object that was encoded
416     * @param isStatic whether the method is static
417     */
418    public static void validateEncode(byte[] info, DexFile file,
419            CstMethodRef ref, DalvCode code, boolean isStatic) {
420        PositionList pl = code.getPositions();
421        LocalList ll = code.getLocals();
422        DalvInsnList insns = code.getInsns();
423        int codeSize = insns.codeSize();
424        int countRegisters = insns.getRegistersSize();
425
426        try {
427            validateEncode0(info, codeSize, countRegisters,
428                    isStatic, ref, file, pl, ll);
429        } catch (RuntimeException ex) {
430            System.err.println("instructions:");
431            insns.debugPrint(System.err, "  ", true);
432            System.err.println("local list:");
433            ll.debugPrint(System.err, "  ");
434            throw ExceptionWithContext.withContext(ex,
435                    "while processing " + ref.toHuman());
436        }
437    }
438
439    private static void validateEncode0(byte[] info, int codeSize,
440            int countRegisters, boolean isStatic, CstMethodRef ref,
441            DexFile file, PositionList pl, LocalList ll) {
442        DebugInfoDecoder decoder
443                = new DebugInfoDecoder(info, codeSize, countRegisters,
444                    isStatic, ref, file);
445
446        decoder.decode();
447
448        /*
449         * Go through the decoded position entries, matching up
450         * with original entries.
451         */
452
453        List<PositionEntry> decodedEntries = decoder.getPositionList();
454
455        if (decodedEntries.size() != pl.size()) {
456            throw new RuntimeException(
457                    "Decoded positions table not same size was "
458                    + decodedEntries.size() + " expected " + pl.size());
459        }
460
461        for (PositionEntry entry : decodedEntries) {
462            boolean found = false;
463            for (int i = pl.size() - 1; i >= 0; i--) {
464                PositionList.Entry ple = pl.get(i);
465
466                if (entry.line == ple.getPosition().getLine()
467                        && entry.address == ple.getAddress()) {
468                    found = true;
469                    break;
470                }
471            }
472
473            if (!found) {
474                throw new RuntimeException ("Could not match position entry: "
475                        + entry.address + ", " + entry.line);
476            }
477        }
478
479        /*
480         * Go through the original local list, in order, matching up
481         * with decoded entries.
482         */
483
484        List<LocalEntry> decodedLocals = decoder.getLocals();
485        int thisStringIdx = decoder.thisStringIdx;
486        int decodedSz = decodedLocals.size();
487        int paramBase = decoder.getParamBase();
488
489        /*
490         * Preflight to fill in any parameters that were skipped in
491         * the prologue (including an implied "this") but then
492         * identified by full signature.
493         */
494        for (int i = 0; i < decodedSz; i++) {
495            LocalEntry entry = decodedLocals.get(i);
496            int idx = entry.nameIndex;
497
498            if ((idx < 0) || (idx == thisStringIdx)) {
499                for (int j = i + 1; j < decodedSz; j++) {
500                    LocalEntry e2 = decodedLocals.get(j);
501                    if (e2.address != 0) {
502                        break;
503                    }
504                    if ((entry.reg == e2.reg) && e2.isStart) {
505                        decodedLocals.set(i, e2);
506                        decodedLocals.remove(j);
507                        decodedSz--;
508                        break;
509                    }
510                }
511            }
512        }
513
514        int origSz = ll.size();
515        int decodeAt = 0;
516        boolean problem = false;
517
518        for (int i = 0; i < origSz; i++) {
519            LocalList.Entry origEntry = ll.get(i);
520
521            if (origEntry.getDisposition()
522                    == LocalList.Disposition.END_REPLACED) {
523                /*
524                 * The encoded list doesn't represent replacements, so
525                 * ignore them for the sake of comparison.
526                 */
527                continue;
528            }
529
530            LocalEntry decodedEntry;
531
532            do {
533                decodedEntry = decodedLocals.get(decodeAt);
534                if (decodedEntry.nameIndex >= 0) {
535                    break;
536                }
537                /*
538                 * A negative name index means this is an anonymous
539                 * parameter, and we shouldn't expect to see it in the
540                 * original list. So, skip it.
541                 */
542                decodeAt++;
543            } while (decodeAt < decodedSz);
544
545            int decodedAddress = decodedEntry.address;
546
547            if (decodedEntry.reg != origEntry.getRegister()) {
548                System.err.println("local register mismatch at orig " + i +
549                        " / decoded " + decodeAt);
550                problem = true;
551                break;
552            }
553
554            if (decodedEntry.isStart != origEntry.isStart()) {
555                System.err.println("local start/end mismatch at orig " + i +
556                        " / decoded " + decodeAt);
557                problem = true;
558                break;
559            }
560
561            /*
562             * The secondary check here accounts for the fact that a
563             * parameter might not be marked as starting at 0 in the
564             * original list.
565             */
566            if ((decodedAddress != origEntry.getAddress())
567                    && !((decodedAddress == 0)
568                            && (decodedEntry.reg >= paramBase))) {
569                System.err.println("local address mismatch at orig " + i +
570                        " / decoded " + decodeAt);
571                problem = true;
572                break;
573            }
574
575            decodeAt++;
576        }
577
578        if (problem) {
579            System.err.println("decoded locals:");
580            for (LocalEntry e : decodedLocals) {
581                System.err.println("  " + e);
582            }
583            throw new RuntimeException("local table problem");
584        }
585    }
586}
587