ceph/src/civetweb/src/third_party/duktape-1.3.0/src-separate/duk_hobject_pc2line.c

   1 /*
   2  *  Helpers for creating and querying pc2line debug data, which
   3  *  converts a bytecode program counter to a source line number.
   4  *
   5  *  The run-time pc2line data is bit-packed, and documented in:
   6  *
   7  *    doc/function-objects.rst
   8  */
   9
  10 #include "duk_internal.h"
  11
  12 #if defined(DUK_USE_PC2LINE)
  13
  14 /* Generate pc2line data for an instruction sequence, leaving a buffer on stack top. */
  15 DUK_INTERNAL void duk_hobject_pc2line_pack(duk_hthread *thr, duk_compiler_instr *instrs, duk_uint_fast32_t length) {
  16         duk_context *ctx = (duk_context *) thr;
  17         duk_hbuffer_dynamic *h_buf;
  18         duk_bitencoder_ctx be_ctx_alloc;
  19         duk_bitencoder_ctx *be_ctx = &be_ctx_alloc;
  20         duk_uint32_t *hdr;
  21         duk_size_t new_size;
  22         duk_uint_fast32_t num_header_entries;
  23         duk_uint_fast32_t curr_offset;
  24         duk_int_fast32_t curr_line, next_line, diff_line;
  25         duk_uint_fast32_t curr_pc;
  26         duk_uint_fast32_t hdr_index;
  27
  28         DUK_ASSERT(length <= DUK_COMPILER_MAX_BYTECODE_LENGTH);
  29
  30         /* XXX: add proper spare handling to dynamic buffer, to minimize
  31          * reallocs; currently there is no spare at all.
  32          */
  33
  34         num_header_entries = (length + DUK_PC2LINE_SKIP - 1) / DUK_PC2LINE_SKIP;
  35         curr_offset = (duk_uint_fast32_t) (sizeof(duk_uint32_t) + num_header_entries * sizeof(duk_uint32_t) * 2);
  36
  37         duk_push_dynamic_buffer(ctx, (duk_size_t) curr_offset);
  38         h_buf = (duk_hbuffer_dynamic *) duk_get_hbuffer(ctx, -1);
  39         DUK_ASSERT(h_buf != NULL);
  40         DUK_ASSERT(DUK_HBUFFER_HAS_DYNAMIC(h_buf) && !DUK_HBUFFER_HAS_EXTERNAL(h_buf));
  41
  42         hdr = (duk_uint32_t *) DUK_HBUFFER_DYNAMIC_GET_DATA_PTR(thr->heap, h_buf);
  43         DUK_ASSERT(hdr != NULL);
  44         hdr[0] = (duk_uint32_t) length;  /* valid pc range is [0, length[ */
  45
  46         curr_pc = 0U;
  47         while (curr_pc < length) {
  48                 new_size = (duk_size_t) (curr_offset + DUK_PC2LINE_MAX_DIFF_LENGTH);
  49                 duk_hbuffer_resize(thr, h_buf, new_size);
  50
  51                 hdr = (duk_uint32_t *) DUK_HBUFFER_DYNAMIC_GET_DATA_PTR(thr->heap, h_buf);
  52                 DUK_ASSERT(hdr != NULL);
  53                 DUK_ASSERT(curr_pc < length);
  54                 hdr_index = 1 + (curr_pc / DUK_PC2LINE_SKIP) * 2;
  55                 curr_line = (duk_int_fast32_t) instrs[curr_pc].line;
  56                 hdr[hdr_index + 0] = (duk_uint32_t) curr_line;
  57                 hdr[hdr_index + 1] = (duk_uint32_t) curr_offset;
  58
  59 #if 0
  60                 DUK_DDD(DUK_DDDPRINT("hdr[%ld]: pc=%ld line=%ld offset=%ld",
  61                                      (long) (curr_pc / DUK_PC2LINE_SKIP),
  62                                      (long) curr_pc,
  63                                      (long) hdr[hdr_index + 0],
  64                                      (long) hdr[hdr_index + 1]));
  65 #endif
  66
  67                 DUK_MEMZERO(be_ctx, sizeof(*be_ctx));
  68                 be_ctx->data = ((duk_uint8_t *) hdr) + curr_offset;
  69                 be_ctx->length = (duk_size_t) DUK_PC2LINE_MAX_DIFF_LENGTH;
  70
  71                 for (;;) {
  72                         curr_pc++;
  73                         if ( ((curr_pc % DUK_PC2LINE_SKIP) == 0) ||  /* end of diff run */
  74                              (curr_pc >= length) ) {                 /* end of bytecode */
  75                                 break;
  76                         }
  77                         DUK_ASSERT(curr_pc < length);
  78                         next_line = (duk_int32_t) instrs[curr_pc].line;
  79                         diff_line = next_line - curr_line;
  80
  81 #if 0
  82                         DUK_DDD(DUK_DDDPRINT("curr_line=%ld, next_line=%ld -> diff_line=%ld",
  83                                              (long) curr_line, (long) next_line, (long) diff_line));
  84 #endif
  85
  86                         if (diff_line == 0) {
  87                                 /* 0 */
  88                                 duk_be_encode(be_ctx, 0, 1);
  89                         } else if (diff_line >= 1 && diff_line <= 4) {
  90                                 /* 1 0 <2 bits> */
  91                                 duk_be_encode(be_ctx, (0x02 << 2) + (diff_line - 1), 4);
  92                         } else if (diff_line >= -0x80 && diff_line <= 0x7f) {
  93                                 /* 1 1 0 <8 bits> */
  94                                 DUK_ASSERT(diff_line + 0x80 >= 0 && diff_line + 0x80 <= 0xff);
  95                                 duk_be_encode(be_ctx, (0x06 << 8) + (diff_line + 0x80), 11);
  96                         } else {
  97                                 /* 1 1 1 <32 bits>
  98                                  * Encode in two parts to avoid bitencode 24-bit limitation
  99                                  */
 100                                 duk_be_encode(be_ctx, (0x07 << 16) + ((next_line >> 16) & 0xffffU), 19);
 101                                 duk_be_encode(be_ctx, next_line & 0xffffU, 16);
 102                         }
 103
 104                         curr_line = next_line;
 105                 }
 106
 107                 duk_be_finish(be_ctx);
 108                 DUK_ASSERT(!be_ctx->truncated);
 109
 110                 /* be_ctx->offset == length of encoded bitstream */
 111                 curr_offset += (duk_uint_fast32_t) be_ctx->offset;
 112         }
 113
 114         /* compact */
 115         new_size = (duk_size_t) curr_offset;
 116         duk_hbuffer_resize(thr, h_buf, new_size);
 117
 118         (void) duk_to_fixed_buffer(ctx, -1, NULL);
 119
 120         DUK_DDD(DUK_DDDPRINT("final pc2line data: pc_limit=%ld, length=%ld, %lf bits/opcode --> %!ixT",
 121                              (long) length, (long) new_size, (double) new_size * 8.0 / (double) length,
 122                              (duk_tval *) duk_get_tval(ctx, -1)));
 123 }
 124
 125 /* PC is unsigned.  If caller does PC arithmetic and gets a negative result,
 126  * it will map to a large PC which is out of bounds and causes a zero to be
 127  * returned.
 128  */
 129 DUK_LOCAL duk_uint_fast32_t duk__hobject_pc2line_query_raw(duk_hthread *thr, duk_hbuffer_fixed *buf, duk_uint_fast32_t pc) {
 130         duk_bitdecoder_ctx bd_ctx_alloc;
 131         duk_bitdecoder_ctx *bd_ctx = &bd_ctx_alloc;
 132         duk_uint32_t *hdr;
 133         duk_uint_fast32_t start_offset;
 134         duk_uint_fast32_t pc_limit;
 135         duk_uint_fast32_t hdr_index;
 136         duk_uint_fast32_t pc_base;
 137         duk_uint_fast32_t n;
 138         duk_uint_fast32_t curr_line;
 139
 140         DUK_ASSERT(buf != NULL);
 141         DUK_ASSERT(!DUK_HBUFFER_HAS_DYNAMIC((duk_hbuffer *) buf) && !DUK_HBUFFER_HAS_EXTERNAL((duk_hbuffer *) buf));
 142         DUK_UNREF(thr);
 143
 144         /*
 145          *  Use the index in the header to find the right starting point
 146          */
 147
 148         hdr_index = pc / DUK_PC2LINE_SKIP;
 149         pc_base = hdr_index * DUK_PC2LINE_SKIP;
 150         n = pc - pc_base;
 151
 152         if (DUK_HBUFFER_FIXED_GET_SIZE(buf) <= sizeof(duk_uint32_t)) {
 153                 DUK_DD(DUK_DDPRINT("pc2line lookup failed: buffer is smaller than minimal header"));
 154                 goto error;
 155         }
 156
 157         hdr = (duk_uint32_t *) (void *) DUK_HBUFFER_FIXED_GET_DATA_PTR(thr->heap, buf);
 158         pc_limit = hdr[0];
 159         if (pc >= pc_limit) {
 160                 /* Note: pc is unsigned and cannot be negative */
 161                 DUK_DD(DUK_DDPRINT("pc2line lookup failed: pc out of bounds (pc=%ld, limit=%ld)",
 162                                    (long) pc, (long) pc_limit));
 163                 goto error;
 164         }
 165
 166         curr_line = hdr[1 + hdr_index * 2];
 167         start_offset = hdr[1 + hdr_index * 2 + 1];
 168         if ((duk_size_t) start_offset > DUK_HBUFFER_FIXED_GET_SIZE(buf)) {
 169                 DUK_DD(DUK_DDPRINT("pc2line lookup failed: start_offset out of bounds (start_offset=%ld, buffer_size=%ld)",
 170                                    (long) start_offset, (long) DUK_HBUFFER_GET_SIZE((duk_hbuffer *) buf)));
 171                 goto error;
 172         }
 173
 174         /*
 175          *  Iterate the bitstream (line diffs) until PC is reached
 176          */
 177
 178         DUK_MEMZERO(bd_ctx, sizeof(*bd_ctx));
 179         bd_ctx->data = ((duk_uint8_t *) hdr) + start_offset;
 180         bd_ctx->length = (duk_size_t) (DUK_HBUFFER_FIXED_GET_SIZE(buf) - start_offset);
 181
 182 #if 0
 183         DUK_DDD(DUK_DDDPRINT("pc2line lookup: pc=%ld -> hdr_index=%ld, pc_base=%ld, n=%ld, start_offset=%ld",
 184                              (long) pc, (long) hdr_index, (long) pc_base, (long) n, (long) start_offset));
 185 #endif
 186
 187         while (n > 0) {
 188 #if 0
 189                 DUK_DDD(DUK_DDDPRINT("lookup: n=%ld, curr_line=%ld", (long) n, (long) curr_line));
 190 #endif
 191
 192                 if (duk_bd_decode_flag(bd_ctx)) {
 193                         if (duk_bd_decode_flag(bd_ctx)) {
 194                                 if (duk_bd_decode_flag(bd_ctx)) {
 195                                         /* 1 1 1 <32 bits> */
 196                                         duk_uint_fast32_t t;
 197                                         t = duk_bd_decode(bd_ctx, 16);  /* workaround: max nbits = 24 now */
 198                                         t = (t << 16) + duk_bd_decode(bd_ctx, 16);
 199                                         curr_line = t;
 200                                 } else {
 201                                         /* 1 1 0 <8 bits> */
 202                                         duk_uint_fast32_t t;
 203                                         t = duk_bd_decode(bd_ctx, 8);
 204                                         curr_line = curr_line + t - 0x80;
 205                                 }
 206                         } else {
 207                                 /* 1 0 <2 bits> */
 208                                 duk_uint_fast32_t t;
 209                                 t = duk_bd_decode(bd_ctx, 2);
 210                                 curr_line = curr_line + t + 1;
 211                         }
 212                 } else {
 213                         /* 0: no change */
 214                 }
 215
 216                 n--;
 217         }
 218
 219         DUK_DDD(DUK_DDDPRINT("pc2line lookup result: pc %ld -> line %ld", (long) pc, (long) curr_line));
 220         return curr_line;
 221
 222  error:
 223         DUK_D(DUK_DPRINT("pc2line conversion failed for pc=%ld", (long) pc));
 224         return 0;
 225 }
 226
 227 DUK_INTERNAL duk_uint_fast32_t duk_hobject_pc2line_query(duk_context *ctx, duk_idx_t idx_func, duk_uint_fast32_t pc) {
 228         duk_hbuffer_fixed *pc2line;
 229         duk_uint_fast32_t line;
 230
 231         /* XXX: now that pc2line is used by the debugger quite heavily in
 232          * checked execution, this should be optimized to avoid value stack
 233          * and perhaps also implement some form of pc2line caching (see
 234          * future work in debugger.rst).
 235          */
 236
 237         duk_get_prop_stridx(ctx, idx_func, DUK_STRIDX_INT_PC2LINE);
 238         pc2line = (duk_hbuffer_fixed *) duk_get_hbuffer(ctx, -1);
 239         if (pc2line != NULL) {
 240                 DUK_ASSERT(!DUK_HBUFFER_HAS_DYNAMIC((duk_hbuffer *) pc2line) && !DUK_HBUFFER_HAS_EXTERNAL((duk_hbuffer *) pc2line));
 241                 line = duk__hobject_pc2line_query_raw((duk_hthread *) ctx, pc2line, (duk_uint_fast32_t) pc);
 242         } else {
 243                 line = 0;
 244         }
 245         duk_pop(ctx);
 246
 247         return line;
 248 }
 249
 250 #endif  /* DUK_USE_PC2LINE */