1 /* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2  * This Source Code Form is subject to the terms of the Mozilla Public
3  * License, v. 2.0. If a copy of the MPL was not distributed with this
4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 
6 #include "gfxSkipChars.h"
7 #include "mozilla/BinarySearch.h"
8 
9 struct SkippedRangeStartComparator
10 {
11     const uint32_t mOffset;
12     explicit SkippedRangeStartComparator(const uint32_t aOffset) : mOffset(aOffset) {}
13     int operator()(const gfxSkipChars::SkippedRange& aRange) const {
14         return (mOffset < aRange.Start()) ? -1 : 1;
15     }
16 };
17 
18 void
19 gfxSkipCharsIterator::SetOriginalOffset(int32_t aOffset)
20 {
21     aOffset += mOriginalStringToSkipCharsOffset;
22     if (MOZ_UNLIKELY(uint32_t(aOffset) > mSkipChars->mCharCount)) {
23         gfxCriticalError() <<
24             "invalid offset " << aOffset <<
25             " for gfxSkipChars length " << mSkipChars->mCharCount;
26         aOffset = mSkipChars->mCharCount;
27     }
28 
29     mOriginalStringOffset = aOffset;
30 
31     const uint32_t rangeCount = mSkipChars->mRanges.Length();
32     if (rangeCount == 0) {
33         mSkippedStringOffset = aOffset;
34         return;
35     }
36 
37     // at start of string?
38     if (aOffset == 0) {
39         mSkippedStringOffset = 0;
40         mCurrentRangeIndex =
41             rangeCount && mSkipChars->mRanges[0].Start() == 0 ? 0 : -1;
42         return;
43     }
44 
45     // find the range that includes or precedes aOffset
46     const nsTArray<gfxSkipChars::SkippedRange>& ranges = mSkipChars->mRanges;
47     size_t idx;
48     mozilla::BinarySearchIf(ranges, 0, rangeCount,
49                             SkippedRangeStartComparator(aOffset),
50                             &idx);
51 
52     if (idx == rangeCount) {
53         mCurrentRangeIndex = rangeCount - 1;
54     } else if (uint32_t(aOffset) < ranges[idx].Start()) {
55         mCurrentRangeIndex = idx - 1;
56         if (mCurrentRangeIndex == -1) {
57             mSkippedStringOffset = aOffset;
58             return;
59         }
60     } else {
61         mCurrentRangeIndex = idx;
62     }
63 
64     const gfxSkipChars::SkippedRange& r = ranges[mCurrentRangeIndex];
65     if (uint32_t(aOffset) < r.End()) {
66         mSkippedStringOffset = r.SkippedOffset();
67         return;
68     }
69 
70     mSkippedStringOffset = aOffset - r.NextDelta();
71 }
72 
73 struct SkippedRangeOffsetComparator
74 {
75     const uint32_t mOffset;
76     explicit SkippedRangeOffsetComparator(const uint32_t aOffset) : mOffset(aOffset) {}
77     int operator()(const gfxSkipChars::SkippedRange& aRange) const {
78         return (mOffset < aRange.SkippedOffset()) ? -1 : 1;
79     }
80 };
81 
82 void
83 gfxSkipCharsIterator::SetSkippedOffset(uint32_t aOffset)
84 {
85     NS_ASSERTION((mSkipChars->mRanges.IsEmpty() &&
86                   aOffset <= mSkipChars->mCharCount) ||
87                  (aOffset <= mSkipChars->LastRange().SkippedOffset() +
88                                  mSkipChars->mCharCount -
89                                  mSkipChars->LastRange().End()),
90                  "Invalid skipped offset");
91     mSkippedStringOffset = aOffset;
92 
93     uint32_t rangeCount = mSkipChars->mRanges.Length();
94     if (rangeCount == 0) {
95         mOriginalStringOffset = aOffset;
96         return;
97     }
98 
99     const nsTArray<gfxSkipChars::SkippedRange>& ranges = mSkipChars->mRanges;
100     size_t idx;
101     mozilla::BinarySearchIf(ranges, 0, rangeCount,
102                             SkippedRangeOffsetComparator(aOffset),
103                             &idx);
104 
105     if (idx == rangeCount) {
106         mCurrentRangeIndex = rangeCount - 1;
107     } else if (aOffset < ranges[idx].SkippedOffset()) {
108         mCurrentRangeIndex = idx - 1;
109         if (mCurrentRangeIndex == -1) {
110             mOriginalStringOffset = aOffset;
111             return;
112         }
113     } else {
114         mCurrentRangeIndex = idx;
115     }
116 
117     const gfxSkipChars::SkippedRange& r = ranges[mCurrentRangeIndex];
118     mOriginalStringOffset = r.End() + aOffset - r.SkippedOffset();
119 }
120 
121 bool
122 gfxSkipCharsIterator::IsOriginalCharSkipped(int32_t* aRunLength) const
123 {
124     if (mCurrentRangeIndex == -1) {
125         // we're before the first skipped range (if any)
126         if (aRunLength) {
127             uint32_t end = mSkipChars->mRanges.IsEmpty() ?
128                 mSkipChars->mCharCount : mSkipChars->mRanges[0].Start();
129             *aRunLength = end - mOriginalStringOffset;
130         }
131         return mSkipChars->mCharCount == uint32_t(mOriginalStringOffset);
132     }
133 
134     const gfxSkipChars::SkippedRange& range =
135         mSkipChars->mRanges[mCurrentRangeIndex];
136 
137     if (uint32_t(mOriginalStringOffset) < range.End()) {
138         if (aRunLength) {
139             *aRunLength = range.End() - mOriginalStringOffset;
140         }
141         return true;
142     }
143 
144     if (aRunLength) {
145         uint32_t end =
146             uint32_t(mCurrentRangeIndex) + 1 < mSkipChars->mRanges.Length() ?
147                 mSkipChars->mRanges[mCurrentRangeIndex + 1].Start() :
148                 mSkipChars->mCharCount;
149         *aRunLength = end - mOriginalStringOffset;
150     }
151 
152     return mSkipChars->mCharCount == uint32_t(mOriginalStringOffset);
153 }
154