Add Script.prototype.getAllOffsets and getLineOffsets.
authorJason Orendorff <jorendorff@mozilla.com>
Tue, 28 Jun 2011 14:46:00 -0500
changeset 74488 9ed67a5d4e917fab856aabd656129bed4ab81dbb
parent 74487 9545334d35a31dff3abd1f8ec6c624daa18067fe
child 74489 2cc9d8a133bc33a0202ec8dcdcd1b85b3df5eb9d
push id2
push userbsmedberg@mozilla.com
push dateFri, 19 Aug 2011 14:38:13 +0000
milestone7.0a1
Add Script.prototype.getAllOffsets and getLineOffsets.
js/src/js.msg
js/src/jsarray.cpp
js/src/jsdbg.cpp
js/src/jsobj.h
js/src/jsopcode.h
--- a/js/src/js.msg
+++ b/js/src/js.msg
@@ -354,8 +354,9 @@ MSG_DEF(JSMSG_CCW_REQUIRED,           27
 MSG_DEF(JSMSG_DEBUG_BAD_RESUMPTION,   272, 0, JSEXN_TYPEERR, "debugger resumption value must be undefined, {throw: val}, {return: val}, or null")
 MSG_DEF(JSMSG_ASSIGN_FUNCTION_OR_NULL, 273, 1, JSEXN_TYPEERR, "value assigned to {0} must be a function or null")
 MSG_DEF(JSMSG_DEBUG_NOT_LIVE,         274, 1, JSEXN_ERR, "{0} is not live")
 MSG_DEF(JSMSG_DEBUG_OBJECT_WRONG_OWNER, 275, 0, JSEXN_TYPEERR, "Debug.Object belongs to a different Debug")
 MSG_DEF(JSMSG_DEBUG_OBJECT_PROTO,     276, 0, JSEXN_TYPEERR, "Debug.Object.prototype is not a valid Debug.Object")
 MSG_DEF(JSMSG_DEBUG_LOOP,             277, 0, JSEXN_TYPEERR, "cannot debug an object in same compartment as debugger or a compartment that is already debugging the debugger")
 MSG_DEF(JSMSG_DEBUG_NOT_IDLE,         278, 0, JSEXN_ERR, "can't start debugging: a debuggee script is on the stack")
 MSG_DEF(JSMSG_DEBUG_BAD_OFFSET,       279, 0, JSEXN_TYPEERR, "invalid script offset")
+MSG_DEF(JSMSG_DEBUG_BAD_LINE,         280, 0, JSEXN_TYPEERR, "invalid line number")
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -336,16 +336,42 @@ IndexToId(JSContext* cx, JSObject* obj, 
         if (hole && JSID_IS_VOID(*idp))
             *hole = JS_TRUE;
         return JS_TRUE;
     }
 
     return ReallyBigIndexToId(cx, index, idp);
 }
 
+bool
+JSObject::arrayGetOwnDataElement(JSContext *cx, size_t i, Value *vp)
+{
+    JS_ASSERT(isArray());
+
+    if (isDenseArray()) {
+        if (i >= getArrayLength())
+            vp->setMagic(JS_ARRAY_HOLE);
+        else
+            *vp = getDenseArrayElement(uint32(i));
+        return true;
+    }
+
+    JSBool hole;
+    jsid id;
+    if (!IndexToId(cx, this, i, &hole, &id))
+        return false;
+
+    const Shape *shape = nativeLookup(id);
+    if (!shape || !shape->isDataDescriptor())
+        vp->setMagic(JS_ARRAY_HOLE);
+    else
+        *vp = getSlot(shape->slot);
+    return true;
+}
+
 /*
  * If the property at the given index exists, get its value into location
  * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
  * to JSVAL_VOID. This function assumes that the location pointed by vp is
  * properly rooted and can be used as GC-protected storage for temporaries.
  */
 static JSBool
 GetElement(JSContext *cx, JSObject *obj, jsdouble index, JSBool *hole, Value *vp)
--- a/js/src/jsdbg.cpp
+++ b/js/src/jsdbg.cpp
@@ -43,16 +43,17 @@
 #include "jsapi.h"
 #include "jscntxt.h"
 #include "jsemit.h"
 #include "jsgcmark.h"
 #include "jsobj.h"
 #include "jswrapper.h"
 #include "jsinterpinlines.h"
 #include "jsobjinlines.h"
+#include "jsopcodeinlines.h"
 #include "vm/Stack-inl.h"
 
 using namespace js;
 
 
 // === Forward declarations
 
 extern Class DebugFrame_class;
@@ -175,18 +176,18 @@ Debug::~Debug()
     JS_ASSERT(object->compartment()->rt->gcRunning);
     JS_REMOVE_LINK(&link);
 }
 
 bool
 Debug::init(JSContext *cx)
 {
     bool ok = (frames.init() &&
-               objects.init() && 
-               debuggees.init() && 
+               objects.init() &&
+               debuggees.init() &&
                heldScripts.init() &&
                evalScripts.init());
     if (!ok)
         js_ReportOutOfMemory(cx);
     return ok;
 }
 
 JS_STATIC_ASSERT(uintN(JSSLOT_DEBUGFRAME_OWNER) == uintN(JSSLOT_DEBUGOBJECT_OWNER));
@@ -385,17 +386,17 @@ Debug::parseResumptionValue(AutoCompartm
     jsid throwId = ATOM_TO_JSID(cx->runtime->atomState.throwAtom);
     bool okResumption = rv.isObject();
     if (okResumption) {
         obj = &rv.toObject();
         okResumption = obj->isObject();
     }
     if (okResumption) {
         shape = obj->lastProperty();
-        okResumption = shape->previous() && 
+        okResumption = shape->previous() &&
              !shape->previous()->previous() &&
              (shape->propid == returnId || shape->propid == throwId) &&
              shape->isDataDescriptor();
     }
     if (!okResumption) {
         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_DEBUG_BAD_RESUMPTION);
         return handleUncaughtException(ac, vp, callHook);
     }
@@ -1246,17 +1247,17 @@ DebugScript_checkThis(JSContext *cx, Val
         return NULL;
     }
 
     if (checkLive && !GetScriptReferent(thisobj)) {
         JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_DEBUG_NOT_LIVE,
                              "Debug.Script", fnname, "script");
         return NULL;
     }
-    
+
     return thisobj;
 }
 
 #define THIS_DEBUGSCRIPT_SCRIPT_NEEDLIVE(cx, vp, fnname, obj, script, checkLive)    \
     JSObject *obj = DebugScript_checkThis(cx, vp, fnname, checkLive);               \
     if (!obj)                                                                       \
         return false;                                                               \
     JSScript *script = GetScriptReferent(obj)
@@ -1302,29 +1303,277 @@ DebugScript_getOffsetLine(JSContext *cx,
     size_t offset;
     if (!ScriptOffset(cx, script, vp[2], &offset))
         return false;
     uintN lineno = JS_PCToLineNumber(cx, script, script->code + offset);
     vp->setNumber(lineno);
     return true;
 }
 
+class BytecodeRangeWithLineNumbers : private BytecodeRange
+{
+  public:
+    using BytecodeRange::empty;
+    using BytecodeRange::frontPC;
+    using BytecodeRange::frontOpcode;
+    using BytecodeRange::frontOffset;
+
+    BytecodeRangeWithLineNumbers(JSContext *cx, JSScript *script)
+      : BytecodeRange(cx, script), lineno(script->lineno), sn(script->notes()), snpc(script->code) {
+        if (!SN_IS_TERMINATOR(sn))
+            snpc += SN_DELTA(sn);
+        updateLine();
+    }
+
+    void popFront() {
+        BytecodeRange::popFront();
+        if (!empty())
+            updateLine();
+    }
+
+    size_t frontLineNumber() const { return lineno; }
+
+  private:
+    void updateLine() {
+        // Determine the current line number by reading all source notes up to
+        // and including the current offset.
+        while (!SN_IS_TERMINATOR(sn) && snpc <= frontPC()) {
+            JSSrcNoteType type = (JSSrcNoteType) SN_TYPE(sn);
+            if (type == SRC_SETLINE)
+                lineno = size_t(js_GetSrcNoteOffset(sn, 0));
+            else if (type == SRC_NEWLINE)
+                lineno++;
+
+            sn = SN_NEXT(sn);
+            snpc += SN_DELTA(sn);
+        }
+    }
+
+    size_t lineno;
+    jssrcnote *sn;
+    jsbytecode *snpc;
+};
+
+static const size_t NoEdges = -1;
+static const size_t MultipleEdges = -2;
+
+/*
+ * FlowGraphSummary::populate(cx, script) computes a summary of script's
+ * control flow graph used by DebugScript_{getAllOffsets,getLineOffsets}.
+ *
+ * jumpData[offset] is:
+ *   - NoEdges if offset isn't the offset of an instruction, or if the
+ *     instruction is apparently unreachable;
+ *   - MultipleEdges if you can arrive at that instruction from
+ *     instructions on multiple different lines OR it's the first
+ *     instruction of the script;
+ *   - otherwise, the (unique) line number of all instructions that can
+ *     precede the instruction at offset.
+ *
+ * The generated graph does not contain edges for JSOP_RETSUB, which appears at
+ * the end of finally blocks. The algorithm that uses this information works
+ * anyway, because in non-exception cases, JSOP_RETSUB always returns to a
+ * !FlowsIntoNext instruction (JSOP_GOTO/GOTOX or JSOP_RETRVAL) which generates
+ * an edge if needed.
+ */
+class FlowGraphSummary : public Vector<size_t> {
+  public:
+    typedef Vector<size_t> Base;
+    FlowGraphSummary(JSContext *cx) : Base(cx) {}
+
+    void addEdge(size_t sourceLine, size_t targetOffset) {
+        FlowGraphSummary &self = *this;
+        if (self[targetOffset] == NoEdges)
+            self[targetOffset] = sourceLine;
+        else if (self[targetOffset] != sourceLine)
+            self[targetOffset] = MultipleEdges;
+    }
+
+    void addEdgeFromAnywhere(size_t targetOffset) {
+        (*this)[targetOffset] = MultipleEdges;
+    }
+
+    bool populate(JSContext *cx, JSScript *script) {
+        if (!growBy(script->length))
+            return false;
+        FlowGraphSummary &self = *this;
+        self[0] = MultipleEdges;
+        for (size_t i = 1; i < script->length; i++)
+            self[i] = NoEdges;
+
+        size_t prevLine = script->lineno;
+        JSOp prevOp = JSOP_NOP;
+        for (BytecodeRangeWithLineNumbers r(cx, script); !r.empty(); r.popFront()) {
+            size_t lineno = r.frontLineNumber();
+            JSOp op = r.frontOpcode();
+
+            if (FlowsIntoNext(prevOp))
+                addEdge(prevLine, r.frontOffset());
+
+            if (js_CodeSpec[op].type() == JOF_JUMP) {
+                addEdge(lineno, r.frontOffset() + GET_JUMP_OFFSET(r.frontPC()));
+            } else if (js_CodeSpec[op].type() == JOF_JUMPX) {
+                addEdge(lineno, r.frontOffset() + GET_JUMPX_OFFSET(r.frontPC()));
+            } else if (op == JSOP_TABLESWITCH || op == JSOP_TABLESWITCHX ||
+                       op == JSOP_LOOKUPSWITCH || op == JSOP_LOOKUPSWITCHX) {
+                bool table = op == JSOP_TABLESWITCH || op == JSOP_TABLESWITCHX;
+                bool big = op == JSOP_TABLESWITCHX || op == JSOP_LOOKUPSWITCHX;
+
+                jsbytecode *pc = r.frontPC();
+                size_t offset = r.frontOffset();
+                ptrdiff_t step = big ? JUMPX_OFFSET_LEN : JUMP_OFFSET_LEN;
+                size_t defaultOffset = offset + (big ? GET_JUMPX_OFFSET(pc) : GET_JUMP_OFFSET(pc));
+                pc += step;
+                addEdge(lineno, defaultOffset);
+
+                jsint ncases;
+                if (table) {
+                    jsint low = GET_JUMP_OFFSET(pc);
+                    pc += JUMP_OFFSET_LEN;
+                    ncases = GET_JUMP_OFFSET(pc) - low + 1;
+                    pc += JUMP_OFFSET_LEN;
+                } else {
+                    ncases = (jsint) GET_UINT16(pc);
+                    pc += UINT16_LEN;
+                    JS_ASSERT(ncases > 0);
+                }
+
+                for (jsint i = 0; i < ncases; i++) {
+                    if (!table)
+                        pc += INDEX_LEN;
+                    size_t target = offset + (big ? GET_JUMPX_OFFSET(pc) : GET_JUMP_OFFSET(pc));
+                    addEdge(lineno, target);
+                    pc += step;
+                }
+            }
+
+            prevOp = op;
+            prevLine = lineno;
+        }
+
+
+        return true;
+    }
+};
+
+static JSBool
+DebugScript_getAllOffsets(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_DEBUGSCRIPT_LIVE_SCRIPT(cx, vp, "getAllOffsets", obj, script);
+
+    // First pass: determine which offsets in this script are jump targets and
+    // which line numbers jump to them.
+    FlowGraphSummary flowData(cx);
+    if (!flowData.populate(cx, script))
+        return false;
+
+    // Second pass: build the result array.
+    JSObject *result = NewDenseEmptyArray(cx);
+    if (!result)
+        return false;
+    for (BytecodeRangeWithLineNumbers r(cx, script); !r.empty(); r.popFront()) {
+        size_t offset = r.frontOffset();
+        size_t lineno = r.frontLineNumber();
+
+        // Make a note, if the current instruction is an entry point for the current line.
+        if (flowData[offset] != NoEdges && flowData[offset] != lineno) {
+            // Get the offsets array for this line.
+            JSObject *offsets;
+            Value offsetsv;
+            if (!result->arrayGetOwnDataElement(cx, lineno, &offsetsv))
+                return false;
+
+            jsid id;
+            if (offsetsv.isObject()) {
+                offsets = &offsetsv.toObject();
+            } else {
+                JS_ASSERT(offsetsv.isMagic(JS_ARRAY_HOLE));
+
+                // Create an empty offsets array for this line.
+                // Store it in the result array.
+                offsets = NewDenseEmptyArray(cx);
+                if (!offsets ||
+                    !ValueToId(cx, NumberValue(lineno), &id) ||
+                    !result->defineProperty(cx, id, ObjectValue(*offsets)))
+                {
+                    return false;
+                }
+            }
+
+            // Append the current offset to the offsets array.
+            if (!js_ArrayCompPush(cx, offsets, NumberValue(offset)))
+                return false;
+        }
+    }
+
+    vp->setObject(*result);
+    return true;
+}
+
+static JSBool
+DebugScript_getLineOffsets(JSContext *cx, uintN argc, Value *vp)
+{
+    THIS_DEBUGSCRIPT_LIVE_SCRIPT(cx, vp, "getAllOffsets", obj, script);
+    REQUIRE_ARGC("Debug.Script.getLineOffsets", 1);
+
+    // Parse lineno argument.
+    size_t lineno;
+    bool ok = false;
+    if (vp[2].isNumber()) {
+        jsdouble d = vp[2].toNumber();
+        lineno = size_t(d);
+        ok = (lineno == d);
+    }
+    if (!ok) {
+        JS_ReportErrorNumber(cx,  js_GetErrorMessage, NULL, JSMSG_DEBUG_BAD_LINE);
+        return false;
+    }
+
+    // First pass: determine which offsets in this script are jump targets and
+    // which line numbers jump to them.
+    FlowGraphSummary flowData(cx);
+    if (!flowData.populate(cx, script))
+        return false;
+
+    // Second pass: build the result array.
+    JSObject *result = NewDenseEmptyArray(cx);
+    if (!result)
+        return false;
+    for (BytecodeRangeWithLineNumbers r(cx, script); !r.empty(); r.popFront()) {
+        size_t offset = r.frontOffset();
+
+        // If the op at offset is an entry point, append offset to result.
+        if (r.frontLineNumber() == lineno &&
+            flowData[offset] != NoEdges &&
+            flowData[offset] != lineno)
+        {
+            if (!js_ArrayCompPush(cx, result, NumberValue(offset)))
+                return false;
+        }
+    }
+
+    vp->setObject(*result);
+    return true;
+}
+
 static JSBool
 DebugScript_construct(JSContext *cx, uintN argc, Value *vp)
 {
     JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_NO_CONSTRUCTOR, "Debug.Script");
     return false;
 }
 
 static JSPropertySpec DebugScript_properties[] = {
     JS_PSG("live", DebugScript_getLive, 0),
     JS_PS_END
 };
 
 static JSFunctionSpec DebugScript_methods[] = {
+    JS_FN("getAllOffsets", DebugScript_getAllOffsets, 0, 0),
+    JS_FN("getLineOffsets", DebugScript_getLineOffsets, 1, 0),
     JS_FN("getOffsetLine", DebugScript_getOffsetLine, 0, 0),
     JS_FS_END
 };
 
 
 // === Debug.Frame
 
 Class DebugFrame_class = {
@@ -1865,17 +2114,17 @@ DebugObject_getName(JSContext *cx, uintN
         return true;
     }
 
     JSString *name = obj->getFunctionPrivate()->atom;
     if (!name) {
         vp->setUndefined();
         return true;
     }
-        
+
     vp->setString(name);
     return dbg->wrapDebuggeeValue(cx, vp);
 }
 
 static JSBool
 DebugObject_getParameterNames(JSContext *cx, uintN argc, Value *vp)
 {
     THIS_DEBUGOBJECT_REFERENT(cx, vp, "get parameterNames", obj);
--- a/js/src/jsobj.h
+++ b/js/src/jsobj.h
@@ -804,16 +804,23 @@ struct JSObject : js::gc::Cell {
     /*
      * Check if after growing the dense array will be too sparse.
      * newElementsHint is an estimated number of elements to be added.
      */
     bool willBeSparseDenseArray(uintN requiredCapacity, uintN newElementsHint);
 
     JSBool makeDenseArraySlow(JSContext *cx);
 
+    /*
+     * If this array object has a data property with index i, set *vp to its
+     * value and return true. If not, do vp->setMagic(JS_ARRAY_HOLE) and return
+     * true. On OOM, report it and return false.
+     */
+    bool arrayGetOwnDataElement(JSContext *cx, size_t i, js::Value *vp);
+
   public:
     inline js::ArgumentsObject *asArguments();
     inline js::NormalArgumentsObject *asNormalArguments();
     inline js::StrictArgumentsObject *asStrictArguments();
 
   private:
     /*
      * Reserved slot structure for Call objects:
--- a/js/src/jsopcode.h
+++ b/js/src/jsopcode.h
@@ -540,16 +540,24 @@ extern bool
 CallResultEscapes(jsbytecode *pc);
 
 extern size_t
 GetBytecodeLength(JSContext *cx, JSScript *script, jsbytecode *pc);
 
 extern bool
 IsValidBytecodeOffset(JSContext *cx, JSScript *script, size_t offset);
 
+inline bool
+FlowsIntoNext(JSOp op)
+{
+    // JSOP_YIELD is considered to flow into the next instruction, like JSOP_CALL.
+    return op != JSOP_STOP && op != JSOP_RETURN && op != JSOP_RETRVAL && op != JSOP_THROW &&
+           op != JSOP_GOTO && op != JSOP_GOTOX && op != JSOP_RETSUB;
+}
+
 }
 #endif
 
 #if defined(DEBUG) && defined(__cplusplus)
 /*
  * Disassemblers, for debugging only.
  */
 extern JS_FRIEND_API(JSBool)