/[jscoverage]/trunk/js/jsregexp.cpp
ViewVC logotype

Diff of /trunk/js/jsregexp.cpp

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 398 by siliconforks, Thu Oct 23 19:03:33 2008 UTC revision 399 by siliconforks, Tue Dec 9 03:37:47 2008 UTC
# Line 51  Line 51 
51  #include "jsapi.h"  #include "jsapi.h"
52  #include "jsarray.h"  #include "jsarray.h"
53  #include "jsatom.h"  #include "jsatom.h"
54    #include "jsbuiltins.h"
55  #include "jscntxt.h"  #include "jscntxt.h"
56  #include "jsversion.h"  #include "jsversion.h"
57  #include "jsfun.h"  #include "jsfun.h"
# Line 65  Line 66 
66  #include "jsscope.h"  #include "jsscope.h"
67  #include "jsstr.h"  #include "jsstr.h"
68    
69    #ifdef JS_TRACER
70    #include "jstracer.h"
71    using namespace avmplus;
72    using namespace nanojit;
73    
74    /*
75     * FIXME  Duplicated with jstracer.cpp, doing it this way for now
76     *        to keep it private to files that need it.
77     */
78    #ifdef JS_JIT_SPEW
79    static bool verbose_debug = getenv("TRACEMONKEY") && strstr(getenv("TRACEMONKEY"), "verbose");
80    #define debug_only_v(x) if (verbose_debug) { x; }
81    #else
82    #define debug_only_v(x)
83    #endif
84    #endif
85    
86  typedef enum REOp {  typedef enum REOp {
87  #define REOP_DEF(opcode, name) opcode,  #define REOP_DEF(opcode, name) opcode,
88  #include "jsreops.tbl"  #include "jsreops.tbl"
# Line 1600  Line 1618 
1618      return JS_TRUE;      return JS_TRUE;
1619  }  }
1620    
1621    /* Copy the charset data from a character class node to the charset list
1622     * in the regexp object. */
1623    static JS_ALWAYS_INLINE RECharSet *
1624    InitNodeCharSet(JSRegExp *re, RENode *node)
1625    {
1626        RECharSet *charSet = &re->classList[node->u.ucclass.index];
1627        charSet->converted = JS_FALSE;
1628        charSet->length = node->u.ucclass.bmsize;
1629        charSet->u.src.startIndex = node->u.ucclass.startIndex;
1630        charSet->u.src.length = node->u.ucclass.kidlen;
1631        charSet->sense = node->u.ucclass.sense;
1632        return charSet;
1633    }
1634    
1635  /*  /*
1636   * Generate bytecode for the tree rooted at t using an explicit stack instead   * Generate bytecode for the tree rooted at t using an explicit stack instead
1637   * of recursion.   * of recursion.
# Line 1609  Line 1641 
1641                 jsbytecode *pc, RENode *t)                 jsbytecode *pc, RENode *t)
1642  {  {
1643      EmitStateStackEntry *emitStateSP, *emitStateStack;      EmitStateStackEntry *emitStateSP, *emitStateStack;
     RECharSet *charSet;  
1644      REOp op;      REOp op;
1645    
1646      if (treeDepth == 0) {      if (treeDepth == 0) {
# Line 1899  Line 1930 
1930              if (!t->u.ucclass.sense)              if (!t->u.ucclass.sense)
1931                  pc[-1] = REOP_NCLASS;                  pc[-1] = REOP_NCLASS;
1932              pc = WriteCompactIndex(pc, t->u.ucclass.index);              pc = WriteCompactIndex(pc, t->u.ucclass.index);
1933              charSet = &re->classList[t->u.ucclass.index];              InitNodeCharSet(re, t);
             charSet->converted = JS_FALSE;  
             charSet->length = t->u.ucclass.bmsize;  
             charSet->u.src.startIndex = t->u.ucclass.startIndex;  
             charSet->u.src.length = t->u.ucclass.kidlen;  
             charSet->sense = t->u.ucclass.sense;  
1934              break;              break;
1935    
1936            default:            default:
# Line 1934  Line 1960 
1960      goto cleanup;      goto cleanup;
1961  }  }
1962    
1963    #ifdef JS_TRACER
1964    typedef List<LIns*, LIST_NonGCObjects> LInsList;
1965    
1966    /* Dummy GC for nanojit placement new. */
1967    static GC gc;
1968    
1969    class RegExpNativeCompiler {
1970     private:
1971        JSRegExp*        re;   /* Careful: not fully initialized */
1972        CompilerState*   cs;   /* RegExp to compile */
1973        Fragment*        fragment;
1974        LirWriter*       lir;
1975    
1976        LIns*            state;
1977        LIns*            gdata;
1978        LIns*            cpend;
1979    
1980        JSBool isCaseInsensitive() const { return cs->flags & JSREG_FOLD; }
1981    
1982        void targetCurrentPoint(LIns* ins) { ins->target(lir->ins0(LIR_label)); }
1983    
1984        void targetCurrentPoint(LInsList& fails)
1985        {
1986            LIns* fail = lir->ins0(LIR_label);
1987            for (size_t i = 0; i < fails.size(); ++i) {
1988                fails[i]->target(fail);
1989            }
1990            fails.clear();
1991        }
1992    
1993        /*
1994         * These functions return the new position after their match operation,
1995         * or NULL if there was an error.
1996         */
1997        LIns* compileEmpty(RENode* node, LIns* pos, LInsList& fails)
1998        {
1999            return pos;
2000        }
2001    
2002        LIns* compileFlatSingleChar(RENode* node, LIns* pos, LInsList& fails)
2003        {
2004            /*
2005             * Fast case-insensitive test for ASCII letters: convert text
2006             * char to lower case by bit-or-ing in 32 and compare.
2007             */
2008            JSBool useFastCI = JS_FALSE;
2009            jschar ch = node->u.flat.chr; /* char to test for */
2010            jschar ch2 = ch;              /* 2nd char to test for if ci */
2011            if (cs->flags & JSREG_FOLD) {
2012                if (L'A' <= ch && ch <= L'Z' || L'a' <= ch || ch <= L'z') {
2013                    ch |= 32;
2014                    ch2 = ch;
2015                    useFastCI = JS_TRUE;
2016                } else if (JS_TOLOWER(ch) != ch) {
2017                    ch2 = JS_TOLOWER(ch);
2018                    ch = JS_TOUPPER(ch);
2019                }
2020            }
2021    
2022            LIns* to_fail = lir->insBranch(LIR_jf, lir->ins2(LIR_lt, pos, cpend), 0);
2023            fails.add(to_fail);
2024            LIns* text_ch = lir->insLoad(LIR_ldcs, pos, lir->insImm(0));
2025            LIns* comp_ch = useFastCI ?
2026                lir->ins2(LIR_or, text_ch, lir->insImm(32)) :
2027                text_ch;
2028            if (ch == ch2) {
2029                fails.add(lir->insBranch(LIR_jf, lir->ins2(LIR_eq, comp_ch, lir->insImm(ch)), 0));
2030            } else {
2031                LIns* to_ok = lir->insBranch(LIR_jt, lir->ins2(LIR_eq, comp_ch, lir->insImm(ch)), 0);
2032                fails.add(lir->insBranch(LIR_jf, lir->ins2(LIR_eq, comp_ch, lir->insImm(ch2)), 0));
2033                targetCurrentPoint(to_ok);
2034            }
2035    
2036            return lir->ins2(LIR_piadd, pos, lir->insImm(2));
2037        }
2038    
2039        LIns* compileClass(RENode* node, LIns* pos, LInsList& fails)
2040        {
2041            if (!node->u.ucclass.sense)
2042                return JS_FALSE;
2043    
2044            RECharSet* charSet = InitNodeCharSet(re, node);
2045            LIns* to_fail = lir->insBranch(LIR_jf, lir->ins2(LIR_lt, pos, cpend), 0);
2046            fails.add(to_fail);
2047            LIns* text_ch = lir->insLoad(LIR_ldcs, pos, lir->insImm(0));
2048            fails.add(lir->insBranch(LIR_jf, lir->ins2(LIR_le, text_ch, lir->insImm(charSet->length)), 0));
2049            LIns* byteIndex = lir->ins2(LIR_rsh, text_ch, lir->insImm(3));
2050            LIns* bitmap = lir->insLoad(LIR_ld, lir->insImmPtr(charSet), (int) offsetof(RECharSet, u.bits));
2051            LIns* byte = lir->insLoad(LIR_ldcb, lir->ins2(LIR_piadd, bitmap, byteIndex), (int) 0);
2052            LIns* bitMask = lir->ins2(LIR_lsh, lir->insImm(1),
2053                                   lir->ins2(LIR_and, text_ch, lir->insImm(0x7)));
2054            LIns* test = lir->ins2(LIR_eq, lir->ins2(LIR_and, byte, bitMask), lir->insImm(0));
2055            
2056            LIns* to_next = lir->insBranch(LIR_jt, test, 0);
2057            fails.add(to_next);
2058            return lir->ins2(LIR_piadd, pos, lir->insImm(2));
2059        }
2060    
2061        LIns* compileAlt(RENode* node, LIns* pos, LInsList& fails)
2062        {
2063            LInsList kidFails(NULL);
2064            if (!compileNode((RENode *) node->kid, pos, kidFails))
2065                return JS_FALSE;
2066            if (!compileNode(node->next, pos, kidFails))
2067                return JS_FALSE;
2068    
2069            targetCurrentPoint(kidFails);
2070            if (!compileNode(node->u.altprereq.kid2, pos, fails))
2071                return JS_FALSE;
2072            /*
2073             * Disable compilation for any regexp where something follows an
2074             * alternation. To make this work, we need to redesign to either
2075             * (a) pass around continuations so we know the right place to go
2076             * when we logically return, or (b) generate explicit backtracking
2077             * code.
2078             */
2079            if (node->next)
2080                return JS_FALSE;
2081            return pos;
2082        }
2083    
2084        JSBool compileNode(RENode* node, LIns* pos, LInsList& fails)
2085        {
2086            for (; node; node = node->next) {
2087                if (fragment->lirbuf->outOmem())
2088                    return JS_FALSE;
2089    
2090                switch (node->op) {
2091                case REOP_EMPTY:
2092                    pos = compileEmpty(node, pos, fails);
2093                    break;
2094                case REOP_FLAT:
2095                    if (node->u.flat.length != 1)
2096                        return JS_FALSE;
2097                    pos = compileFlatSingleChar(node, pos, fails);
2098                    break;
2099                case REOP_ALT:
2100                case REOP_ALTPREREQ:
2101                    pos = compileAlt(node, pos, fails);
2102                    break;
2103                case REOP_CLASS:
2104                    pos = compileClass(node, pos, fails);
2105                    break;
2106                default:
2107                    return JS_FALSE;
2108                }
2109                if (!pos)
2110                    return JS_FALSE;
2111            }
2112    
2113            lir->insStorei(pos, state, (int) offsetof(REMatchState, cp));
2114            lir->ins1(LIR_ret, state);
2115            return JS_TRUE;
2116        }
2117    
2118        JSBool compileSticky(RENode* root, LIns* start)
2119        {
2120            LInsList fails(NULL);
2121            if (!compileNode(root, start, fails))
2122                return JS_FALSE;
2123            targetCurrentPoint(fails);
2124            lir->ins1(LIR_ret, lir->insImm(0));
2125            return JS_TRUE;
2126        }
2127    
2128        JSBool compileAnchoring(RENode* root, LIns* start)
2129        {
2130            /* Even at the end, the empty regexp would match. */
2131            LIns* to_next = lir->insBranch(LIR_jf,
2132                                           lir->ins2(LIR_le, start, cpend), 0);
2133            LInsList fails(NULL);
2134            if (!compileNode(root, start, fails))
2135                return JS_FALSE;
2136    
2137            targetCurrentPoint(to_next);
2138            lir->ins1(LIR_ret, lir->insImm(0));
2139            
2140            targetCurrentPoint(fails);
2141            lir->insStorei(lir->ins2(LIR_piadd, start, lir->insImm(2)), gdata,
2142                           (int) offsetof(REGlobalData, skipped));
2143            
2144            return JS_TRUE;
2145        }
2146    
2147        inline LIns*
2148        addName(LirBuffer* lirbuf, LIns* ins, const char* name)
2149        {
2150            debug_only_v(lirbuf->names->addName(ins, name);)
2151            return ins;
2152        }
2153    
2154     public:
2155        RegExpNativeCompiler(JSRegExp *re, CompilerState *cs)
2156            : re(re), cs(cs), fragment(NULL) {  }
2157    
2158        JSBool compile(JSContext* cx)
2159        {
2160            GuardRecord* guard;
2161            LIns* skip;
2162            LIns* start;
2163            bool oom = false;
2164            
2165            Fragmento* fragmento = JS_TRACE_MONITOR(cx).reFragmento;
2166            fragment = fragmento->getLoop(re);
2167            if (!fragment) {
2168                fragment = fragmento->getAnchor(re);
2169                fragment->lirbuf = new (&gc) LirBuffer(fragmento, NULL);
2170                /* Scary: required to have the onDestroy method delete the lirbuf. */
2171                fragment->root = fragment;
2172            }
2173            LirBuffer* lirbuf = fragment->lirbuf;
2174            LirBufWriter* lirb;
2175            if (lirbuf->outOmem()) goto fail2;
2176            /* FIXME Use bug 463260 smart pointer when available. */
2177            lir = lirb = new (&gc) LirBufWriter(lirbuf);
2178    
2179            /* FIXME Use bug 463260 smart pointer when available. */
2180            debug_only_v(fragment->lirbuf->names = new (&gc) LirNameMap(&gc, NULL, fragmento->labels);)
2181            /* FIXME Use bug 463260 smart pointer when available. */
2182            debug_only_v(lir = new (&gc) VerboseWriter(&gc, lir, lirbuf->names);)
2183    
2184            lir->ins0(LIR_start);
2185            lirbuf->state = state = addName(lirbuf, lir->insParam(0, 0), "state");
2186            lirbuf->param1 = gdata = addName(lirbuf, lir->insParam(1, 0), "gdata");
2187            start = addName(lirbuf, lir->insLoad(LIR_ldp, lirbuf->param1, (int) offsetof(REGlobalData, skipped)), "start");
2188            cpend = addName(lirbuf, lir->insLoad(LIR_ldp, lirbuf->param1, offsetof(REGlobalData, cpend)), "cpend");
2189    
2190            if (cs->flags & JSREG_STICKY) {
2191                if (!compileSticky(cs->result, start)) goto fail;
2192            } else {
2193                if (!compileAnchoring(cs->result, start)) goto fail;
2194            }
2195    
2196            /* Create fake guard record for loop edge. */
2197            skip = lirb->skip(sizeof(GuardRecord) + sizeof(SideExit));
2198            guard = (GuardRecord *) skip->payload();
2199            memset(guard, 0, sizeof(*guard));
2200            guard->exit = (SideExit *) guard+1;
2201            guard->exit->target = fragment;
2202            fragment->lastIns = lir->insGuard(LIR_loop, lir->insImm(1), skip);
2203    
2204            ::compile(fragmento->assm(), fragment);
2205            if (fragmento->assm()->error() != nanojit::None) {
2206                oom = fragmento->assm()->error() == nanojit::OutOMem;
2207                goto fail;
2208            }
2209    
2210            delete lirb;
2211            debug_only_v(delete lir;)
2212            return JS_TRUE;
2213        fail:
2214            delete lirb;
2215            debug_only_v(delete lir;)
2216        fail2:
2217            if (lirbuf->outOmem() || oom)
2218                fragmento->clearFrags();
2219            return JS_FALSE;
2220        }
2221    };
2222    
2223    static inline JSBool
2224    js_CompileRegExpToNative(JSContext *cx, JSRegExp *re, CompilerState *cs)
2225    {
2226        RegExpNativeCompiler rc(re, cs);
2227        return rc.compile(cx);
2228    }
2229    #endif
2230    
2231  JSRegExp *  JSRegExp *
2232  js_NewRegExp(JSContext *cx, JSTokenStream *ts,  js_NewRegExp(JSContext *cx, JSTokenStream *ts,
# Line 1981  Line 2274 
2274          if (!ParseRegExp(&state))          if (!ParseRegExp(&state))
2275              goto out;              goto out;
2276      }      }
2277    
2278      resize = offsetof(JSRegExp, program) + state.progLength + 1;      resize = offsetof(JSRegExp, program) + state.progLength + 1;
2279      re = (JSRegExp *) JS_malloc(cx, resize);      re = (JSRegExp *) JS_malloc(cx, resize);
2280      if (!re)      if (!re)
# Line 2002  Line 2296 
2296      } else {      } else {
2297          re->classList = NULL;          re->classList = NULL;
2298      }      }
2299    
2300    #ifdef JS_TRACER
2301        /*
2302         * Try compiling the native code version. For the time being we also
2303         * compile the bytecode version in case we evict the native code
2304         * version from the code cache.
2305         */
2306        if (TRACING_ENABLED(cx))
2307            js_CompileRegExpToNative(cx, re, &state);
2308    #endif
2309        /* Compile the bytecode version. */
2310      endPC = EmitREBytecode(&state, re, state.treeDepth, re->program, state.result);      endPC = EmitREBytecode(&state, re, state.treeDepth, re->program, state.result);
2311      if (!endPC) {      if (!endPC) {
2312          js_DestroyRegExp(cx, re);          js_DestroyRegExp(cx, re);
# Line 2014  Line 2319 
2319       * This is safe since no pointers to newly parsed regexp or its parts       * This is safe since no pointers to newly parsed regexp or its parts
2320       * besides re exist here.       * besides re exist here.
2321       */       */
2322    #if 0
2323        /*
2324         * FIXME: Until bug 464866 is fixed, we can't move the re object so
2325         * don't shrink it for now.
2326         */
2327      if ((size_t)(endPC - re->program) != state.progLength + 1) {      if ((size_t)(endPC - re->program) != state.progLength + 1) {
2328          JSRegExp *tmp;          JSRegExp *tmp;
2329          JS_ASSERT((size_t)(endPC - re->program) < state.progLength + 1);          JS_ASSERT((size_t)(endPC - re->program) < state.progLength + 1);
# Line 2022  Line 2332 
2332          if (tmp)          if (tmp)
2333              re = tmp;              re = tmp;
2334      }      }
2335    #endif    
2336    
2337      re->flags = flags;      re->flags = flags;
2338      re->parenCount = state.parenCount;      re->parenCount = state.parenCount;
# Line 2537  Line 2848 
2848  js_DestroyRegExp(JSContext *cx, JSRegExp *re)  js_DestroyRegExp(JSContext *cx, JSRegExp *re)
2849  {  {
2850      if (JS_ATOMIC_DECREMENT(&re->nrefs) == 0) {      if (JS_ATOMIC_DECREMENT(&re->nrefs) == 0) {
2851    #ifdef JS_TRACER
2852            /* Don't reuse this compiled code for some new regexp at same addr. */
2853            Fragment* fragment = JS_TRACE_MONITOR(cx).reFragmento->getLoop(re);
2854            if (fragment)
2855                fragment->blacklist();
2856    #endif
2857          if (re->classList) {          if (re->classList) {
2858              uintN i;              uintN i;
2859              for (i = 0; i < re->classCount; i++) {              for (i = 0; i < re->classCount; i++) {
# Line 3343  Line 3660 
3660      const jschar *cp = x->cp;      const jschar *cp = x->cp;
3661      const jschar *cp2;      const jschar *cp2;
3662      uintN j;      uintN j;
3663    #ifdef JS_TRACER
3664        Fragment *fragment;
3665    
3666        /* Run with native regexp if possible. */
3667        if (TRACING_ENABLED(gData->cx) &&
3668            ((fragment = JS_TRACE_MONITOR(gData->cx).reFragmento->getLoop(gData->regexp)) != NULL)
3669            && fragment->code() && !fragment->isBlacklisted()) {
3670            union { NIns *code; REMatchState* (FASTCALL *func)(void*, void*); } u;
3671            u.code = fragment->code();
3672            REMatchState *lr;
3673            gData->skipped = (ptrdiff_t) x->cp;
3674    
3675            debug_only_v(printf("entering REGEXP trace at %s:%u@%u, code: %p\n",
3676                                gData->cx->fp->script->filename,
3677                                js_FramePCToLineNumber(gData->cx, gData->cx->fp),
3678                                FramePCOffset(gData->cx->fp),
3679                                fragment->code()););
3680    
3681    #if defined(JS_NO_FASTCALL) && defined(NANOJIT_IA32)
3682            SIMULATE_FASTCALL(lr, x, gData, u.func);
3683    #else
3684            lr = u.func(x, gData);
3685    #endif
3686    
3687            debug_only_v(printf("leaving REGEXP trace\n"));
3688    
3689            gData->skipped = ((const jschar *) gData->skipped) - cp;
3690            return lr;
3691        }
3692    #endif
3693      /*      /*
3694       * Have to include the position beyond the last character       * Have to include the position beyond the last character
3695       * in order to detect end-of-input/line condition.       * in order to detect end-of-input/line condition.
# Line 4273  Line 4619 
4619      return JS_TRUE;      return JS_TRUE;
4620  }  }
4621    
4622    #ifdef JS_TRACER
4623    static jsint FASTCALL
4624    Regexp_p_test(JSContext* cx, JSObject* regexp, JSString* str)
4625    {
4626        jsval vp[3] = { JSVAL_NULL, OBJECT_TO_JSVAL(regexp), STRING_TO_JSVAL(str) };
4627        if (!regexp_exec_sub(cx, regexp, 1, vp + 2, JS_TRUE, vp))
4628            return JSVAL_TO_BOOLEAN(JSVAL_VOID);
4629        return *vp == JSVAL_TRUE;
4630    }
4631    
4632    JS_DEFINE_TRCINFO_1(regexp_test,
4633        (3, (static, BOOL_FAIL, Regexp_p_test, CONTEXT, THIS, STRING,  1, 1)))
4634    
4635    #endif
4636    
4637  static JSFunctionSpec regexp_methods[] = {  static JSFunctionSpec regexp_methods[] = {
4638  #if JS_HAS_TOSOURCE  #if JS_HAS_TOSOURCE
4639      JS_FN(js_toSource_str,  regexp_toString,    0,0),      JS_FN(js_toSource_str,  regexp_toString,    0,0),
# Line 4280  Line 4641 
4641      JS_FN(js_toString_str,  regexp_toString,    0,0),      JS_FN(js_toString_str,  regexp_toString,    0,0),
4642      JS_FN("compile",        regexp_compile,     2,0),      JS_FN("compile",        regexp_compile,     2,0),
4643      JS_FN("exec",           regexp_exec,        1,0),      JS_FN("exec",           regexp_exec,        1,0),
4644      JS_FN("test",           regexp_test,        1,0),      JS_TN("test",           regexp_test,        1,0, regexp_test_trcinfo),
4645      JS_FS_END      JS_FS_END
4646  };  };
4647    

Legend:
Removed from v.398  
changed lines
  Added in v.399

  ViewVC Help
Powered by ViewVC 1.1.24