DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (27a812186ff4)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef vm_MatchPairs_h
#define vm_MatchPairs_h

#include "jsalloc.h"

#include "ds/LifoAlloc.h"
#include "js/Vector.h"

/*
 * RegExp match results are succinctly represented by pairs of integer
 * indices delimiting (start, limit] segments of the input string.
 *
 * The pair count for a given RegExp match is the capturing parentheses
 * count plus one for the "0 capturing paren" whole text match.
 */

namespace js {

struct MatchPair
{
    int start;
    int limit;

    MatchPair()
      : start(-1), limit(-1)
    { }

    MatchPair(int start, int limit)
      : start(start), limit(limit)
    { }

    size_t length()      const { JS_ASSERT(!isUndefined()); return limit - start; }
    bool isEmpty()       const { return length() == 0; }
    bool isUndefined()   const { return start < 0; }

    void displace(size_t amount) {
        start += (start < 0) ? 0 : amount;
        limit += (limit < 0) ? 0 : amount;
    }

    inline bool check() const {
        JS_ASSERT(limit >= start);
        JS_ASSERT_IF(start < 0, start == -1);
        JS_ASSERT_IF(limit < 0, limit == -1);
        return true;
    }
};

/* Base class for RegExp execution output. */
class MatchPairs
{
  protected:
    size_t     pairCount_;   /* Length of pairs_. */
    MatchPair* pairs_;       /* Raw pointer into an allocated MatchPair buffer. */

  protected:
    /* Not used directly: use ScopedMatchPairs or VectorMatchPairs. */
    MatchPairs()
      : pairCount_(0), pairs_(nullptr)
    { }

  protected:
    /* Functions used by friend classes. */
    friend class RegExpShared;
    friend class RegExpStatics;

    /* MatchPair buffer allocator: set pairs_ and pairCount_. */
    virtual bool allocOrExpandArray(size_t pairCount) = 0;

    bool initArray(size_t pairCount);
    bool initArrayFrom(MatchPairs& copyFrom);
    void forgetArray() { pairs_ = nullptr; }

    void displace(size_t disp);
    void checkAgainst(size_t inputLength) {
#ifdef DEBUG
        for (size_t i = 0; i < pairCount_; i++) {
            const MatchPair& p = pair(i);
            JS_ASSERT(p.check());
            if (p.isUndefined())
                continue;
            JS_ASSERT(size_t(p.limit) <= inputLength);
        }
#endif
    }

  public:
    /* Querying functions in the style of RegExpStatics. */
    bool   empty() const           { return pairCount_ == 0; }
    size_t pairCount() const       { JS_ASSERT(pairCount_ > 0); return pairCount_; }
    size_t parenCount() const      { return pairCount_ - 1; }

  public:
    unsigned* rawBuf() const { return reinterpret_cast<unsigned*>(pairs_); }
    size_t length() const { return pairCount_; }

    /* Pair accessors. */
    const MatchPair& pair(size_t i) const {
        JS_ASSERT(pairCount_ && i < pairCount_);
        JS_ASSERT(pairs_);
        return pairs_[i];
    }

    const MatchPair& operator[](size_t i) const { return pair(i); }
};

/* MatchPairs allocated into temporary storage, removed when out of scope. */
class ScopedMatchPairs : public MatchPairs
{
    LifoAllocScope lifoScope_;

  public:
    /* Constructs an implicit LifoAllocScope. */
    ScopedMatchPairs(LifoAlloc* lifoAlloc)
      : lifoScope_(lifoAlloc)
    { }

    const MatchPair& operator[](size_t i) const { return pair(i); }

  protected:
    bool allocOrExpandArray(size_t pairCount);
};

/*
 * MatchPairs allocated into permanent storage, for RegExpStatics.
 * The Vector of MatchPairs is reusable by Vector expansion.
 */
class VectorMatchPairs : public MatchPairs
{
    Vector<MatchPair, 10, SystemAllocPolicy> vec_;

  public:
    VectorMatchPairs() {
        vec_.clear();
    }

    const MatchPair& operator[](size_t i) const { return pair(i); }

  protected:
    friend class RegExpStatics;
    bool allocOrExpandArray(size_t pairCount);
};

/*
 * Passes either MatchPair or MatchPairs through ExecuteRegExp()
 * to avoid duplication of generic code.
 */
struct MatchConduit
{
    union {
        MatchPair* pair;
        MatchPairs* pairs;
    } u;
    bool isPair;

    explicit MatchConduit(MatchPair* pair) {
        isPair = true;
        u.pair = pair;
    }
    explicit MatchConduit(MatchPairs* pairs) {
        isPair = false;
        u.pairs = pairs;
    }
};

} /* namespace js */

#endif /* vm_MatchPairs_h */